1 // Copyright 2012-2015 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
11 //! This pass is only used for the UNIT TESTS and DEBUGGING NEEDS
12 //! around dependency graph construction. It serves two purposes; it
13 //! will dump graphs in graphviz form to disk, and it searches for
14 //! `#[rustc_if_this_changed]` and `#[rustc_then_this_would_need]`
15 //! annotations. These annotations can be used to test whether paths
16 //! exist in the graph. These checks run after trans, so they view the
17 //! the final state of the dependency graph. Note that there are
18 //! similar assertions found in `persist::dirty_clean` which check the
19 //! **initial** state of the dependency graph, just after it has been
22 //! In this code, we report errors on each `rustc_if_this_changed`
23 //! annotation. If a path exists in all cases, then we would report
24 //! "all path(s) exist". Otherwise, we report: "no path to `foo`" for
25 //! each case where no path exists. `compile-fail` tests can then be
26 //! used to check when paths exist or do not.
28 //! The full form of the `rustc_if_this_changed` annotation is
29 //! `#[rustc_if_this_changed(id)]`. The `"id"` is optional and
30 //! defaults to `"id"` if omitted.
35 //! #[rustc_if_this_changed]
38 //! #[rustc_then_this_would_need("trans")] //~ ERROR no path from `foo`
41 //! #[rustc_then_this_would_need("trans")] //~ ERROR OK
42 //! fn baz() { foo(); }
46 use rustc::dep_graph::{DepGraphQuery, DepNode};
47 use rustc::dep_graph::debug::{DepNodeFilter, EdgeFilter};
48 use rustc::hir::def_id::DefId;
49 use rustc::ty::TyCtxt;
50 use rustc_data_structures::fnv::{FnvHashMap, FnvHashSet};
51 use rustc_data_structures::graph::{Direction, INCOMING, OUTGOING, NodeIndex};
53 use rustc::hir::intravisit::Visitor;
54 use graphviz::IntoCow;
59 use syntax::parse::token::InternedString;
62 const IF_THIS_CHANGED: &'static str = "rustc_if_this_changed";
63 const THEN_THIS_WOULD_NEED: &'static str = "rustc_then_this_would_need";
64 const ID: &'static str = "id";
66 pub fn assert_dep_graph<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>) {
67 let _ignore = tcx.dep_graph.in_ignore();
69 if tcx.sess.opts.debugging_opts.dump_dep_graph {
73 // if the `rustc_attrs` feature is not enabled, then the
74 // attributes we are interested in cannot be present anyway, so
76 if !tcx.sess.features.borrow().rustc_attrs {
80 // Find annotations supplied by user (if any).
81 let (if_this_changed, then_this_would_need) = {
82 let mut visitor = IfThisChanged { tcx: tcx,
83 if_this_changed: FnvHashMap(),
84 then_this_would_need: FnvHashMap() };
85 tcx.map.krate().visit_all_items(&mut visitor);
86 (visitor.if_this_changed, visitor.then_this_would_need)
89 if !if_this_changed.is_empty() || !then_this_would_need.is_empty() {
90 assert!(tcx.sess.opts.debugging_opts.query_dep_graph,
91 "cannot use the `#[{}]` or `#[{}]` annotations \
92 without supplying `-Z query-dep-graph`",
93 IF_THIS_CHANGED, THEN_THIS_WOULD_NEED);
97 check_paths(tcx, &if_this_changed, &then_this_would_need);
101 FnvHashMap<InternedString,
102 FnvHashSet<(Span, DefId, DepNode<DefId>)>>;
104 FnvHashMap<InternedString,
105 FnvHashSet<(Span, InternedString, ast::NodeId, DepNode<DefId>)>>;
107 struct IfThisChanged<'a, 'tcx:'a> {
108 tcx: TyCtxt<'a, 'tcx, 'tcx>,
109 if_this_changed: SourceHashMap,
110 then_this_would_need: TargetHashMap,
113 impl<'a, 'tcx> IfThisChanged<'a, 'tcx> {
114 fn process_attrs(&mut self, node_id: ast::NodeId, def_id: DefId) {
115 for attr in self.tcx.get_attrs(def_id).iter() {
116 if attr.check_name(IF_THIS_CHANGED) {
118 for list_item in attr.meta_item_list().unwrap_or_default() {
119 match list_item.word() {
120 Some(word) if id.is_none() => {
121 id = Some(word.name().clone())
124 // FIXME better-encapsulate meta_item (don't directly access `node`)
125 span_bug!(list_item.span(), "unexpected list-item {:?}", list_item.node)
130 let id = id.unwrap_or(InternedString::new(ID));
131 self.if_this_changed.entry(id)
132 .or_insert(FnvHashSet())
133 .insert((attr.span, def_id, DepNode::Hir(def_id)));
134 } else if attr.check_name(THEN_THIS_WOULD_NEED) {
135 let mut dep_node_interned = None;
137 for list_item in attr.meta_item_list().unwrap_or_default() {
138 match list_item.word() {
139 Some(word) if dep_node_interned.is_none() => {
140 dep_node_interned = Some(word.name().clone());
142 Some(word) if id.is_none() => {
143 id = Some(word.name().clone())
146 // FIXME better-encapsulate meta_item (don't directly access `node`)
147 span_bug!(list_item.span(), "unexpected meta-item {:?}", list_item.node)
152 let dep_node = match dep_node_interned {
154 match DepNode::from_label_string(&n[..], def_id) {
157 self.tcx.sess.span_fatal(
159 &format!("unrecognized DepNode variant {:?}", n));
164 self.tcx.sess.span_fatal(
166 &format!("missing DepNode variant"));
169 let id = id.unwrap_or(InternedString::new(ID));
170 self.then_this_would_need
172 .or_insert(FnvHashSet())
173 .insert((attr.span, dep_node_interned.clone().unwrap(), node_id, dep_node));
179 impl<'a, 'tcx> Visitor<'tcx> for IfThisChanged<'a, 'tcx> {
180 fn visit_item(&mut self, item: &'tcx hir::Item) {
181 let def_id = self.tcx.map.local_def_id(item.id);
182 self.process_attrs(item.id, def_id);
186 fn check_paths<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
187 if_this_changed: &SourceHashMap,
188 then_this_would_need: &TargetHashMap)
190 // Return early here so as not to construct the query, which is not cheap.
191 if if_this_changed.is_empty() {
194 let query = tcx.dep_graph.query();
195 for (id, sources) in if_this_changed {
196 let targets = match then_this_would_need.get(id) {
197 Some(targets) => targets,
199 for &(source_span, _, _) in sources.iter().take(1) {
202 &format!("no targets for id `{}`", id));
208 for &(_, source_def_id, ref source_dep_node) in sources {
209 let dependents = query.transitive_successors(source_dep_node);
210 for &(target_span, ref target_pass, _, ref target_dep_node) in targets {
211 if !dependents.contains(&target_dep_node) {
214 &format!("no path from `{}` to `{}`",
215 tcx.item_path_str(source_def_id),
227 fn dump_graph(tcx: TyCtxt) {
228 let path: String = env::var("RUST_DEP_GRAPH").unwrap_or_else(|_| format!("dep_graph"));
229 let query = tcx.dep_graph.query();
231 let nodes = match env::var("RUST_DEP_GRAPH_FILTER") {
233 // Expect one of: "-> target", "source -> target", or "source ->".
234 let edge_filter = EdgeFilter::new(&string).unwrap_or_else(|e| {
235 bug!("invalid filter: {}", e)
237 let sources = node_set(&query, &edge_filter.source);
238 let targets = node_set(&query, &edge_filter.target);
239 filter_nodes(&query, &sources, &targets)
247 let edges = filter_edges(&query, &nodes);
249 { // dump a .txt file with just the edges:
250 let txt_path = format!("{}.txt", path);
251 let mut file = File::create(&txt_path).unwrap();
252 for &(ref source, ref target) in &edges {
253 write!(file, "{:?} -> {:?}\n", source, target).unwrap();
257 { // dump a .dot file in graphviz format:
258 let dot_path = format!("{}.dot", path);
259 let mut v = Vec::new();
260 dot::render(&GraphvizDepGraph(nodes, edges), &mut v).unwrap();
261 File::create(&dot_path).and_then(|mut f| f.write_all(&v)).unwrap();
265 pub struct GraphvizDepGraph<'q>(FnvHashSet<&'q DepNode<DefId>>,
266 Vec<(&'q DepNode<DefId>, &'q DepNode<DefId>)>);
268 impl<'a, 'tcx, 'q> dot::GraphWalk<'a> for GraphvizDepGraph<'q> {
269 type Node = &'q DepNode<DefId>;
270 type Edge = (&'q DepNode<DefId>, &'q DepNode<DefId>);
271 fn nodes(&self) -> dot::Nodes<&'q DepNode<DefId>> {
272 let nodes: Vec<_> = self.0.iter().cloned().collect();
275 fn edges(&self) -> dot::Edges<(&'q DepNode<DefId>, &'q DepNode<DefId>)> {
276 self.1[..].into_cow()
278 fn source(&self, edge: &(&'q DepNode<DefId>, &'q DepNode<DefId>)) -> &'q DepNode<DefId> {
281 fn target(&self, edge: &(&'q DepNode<DefId>, &'q DepNode<DefId>)) -> &'q DepNode<DefId> {
286 impl<'a, 'tcx, 'q> dot::Labeller<'a> for GraphvizDepGraph<'q> {
287 type Node = &'q DepNode<DefId>;
288 type Edge = (&'q DepNode<DefId>, &'q DepNode<DefId>);
289 fn graph_id(&self) -> dot::Id {
290 dot::Id::new("DependencyGraph").unwrap()
292 fn node_id(&self, n: &&'q DepNode<DefId>) -> dot::Id {
294 format!("{:?}", n).chars()
295 .map(|c| if c == '_' || c.is_alphanumeric() { c } else { '_' })
297 debug!("n={:?} s={:?}", n, s);
298 dot::Id::new(s).unwrap()
300 fn node_label(&self, n: &&'q DepNode<DefId>) -> dot::LabelText {
301 dot::LabelText::label(format!("{:?}", n))
305 // Given an optional filter like `"x,y,z"`, returns either `None` (no
306 // filter) or the set of nodes whose labels contain all of those
308 fn node_set<'q>(query: &'q DepGraphQuery<DefId>, filter: &DepNodeFilter)
309 -> Option<FnvHashSet<&'q DepNode<DefId>>>
311 debug!("node_set(filter={:?})", filter);
313 if filter.accepts_all() {
317 Some(query.nodes().into_iter().filter(|n| filter.test(n)).collect())
320 fn filter_nodes<'q>(query: &'q DepGraphQuery<DefId>,
321 sources: &Option<FnvHashSet<&'q DepNode<DefId>>>,
322 targets: &Option<FnvHashSet<&'q DepNode<DefId>>>)
323 -> FnvHashSet<&'q DepNode<DefId>>
325 if let &Some(ref sources) = sources {
326 if let &Some(ref targets) = targets {
327 walk_between(query, sources, targets)
329 walk_nodes(query, sources, OUTGOING)
331 } else if let &Some(ref targets) = targets {
332 walk_nodes(query, targets, INCOMING)
334 query.nodes().into_iter().collect()
338 fn walk_nodes<'q>(query: &'q DepGraphQuery<DefId>,
339 starts: &FnvHashSet<&'q DepNode<DefId>>,
340 direction: Direction)
341 -> FnvHashSet<&'q DepNode<DefId>>
343 let mut set = FnvHashSet();
344 for &start in starts {
345 debug!("walk_nodes: start={:?} outgoing?={:?}", start, direction == OUTGOING);
346 if set.insert(start) {
347 let mut stack = vec![query.indices[start]];
348 while let Some(index) = stack.pop() {
349 for (_, edge) in query.graph.adjacent_edges(index, direction) {
350 let neighbor_index = edge.source_or_target(direction);
351 let neighbor = query.graph.node_data(neighbor_index);
352 if set.insert(neighbor) {
353 stack.push(neighbor_index);
362 fn walk_between<'q>(query: &'q DepGraphQuery<DefId>,
363 sources: &FnvHashSet<&'q DepNode<DefId>>,
364 targets: &FnvHashSet<&'q DepNode<DefId>>)
365 -> FnvHashSet<&'q DepNode<DefId>>
367 // This is a bit tricky. We want to include a node only if it is:
368 // (a) reachable from a source and (b) will reach a target. And we
369 // have to be careful about cycles etc. Luckily efficiency is not
372 #[derive(Copy, Clone, PartialEq)]
373 enum State { Undecided, Deciding, Included, Excluded }
375 let mut node_states = vec![State::Undecided; query.graph.len_nodes()];
377 for &target in targets {
378 node_states[query.indices[target].0] = State::Included;
381 for source in sources.iter().map(|&n| query.indices[n]) {
382 recurse(query, &mut node_states, source);
388 let index = query.indices[n];
389 node_states[index.0] == State::Included
393 fn recurse(query: &DepGraphQuery<DefId>,
394 node_states: &mut [State],
398 match node_states[node.0] {
399 // known to reach a target
400 State::Included => return true,
402 // known not to reach a target
403 State::Excluded => return false,
405 // backedge, not yet known, say false
406 State::Deciding => return false,
408 State::Undecided => { }
411 node_states[node.0] = State::Deciding;
413 for neighbor_index in query.graph.successor_nodes(node) {
414 if recurse(query, node_states, neighbor_index) {
415 node_states[node.0] = State::Included;
419 // if we didn't find a path to target, then set to excluded
420 if node_states[node.0] == State::Deciding {
421 node_states[node.0] = State::Excluded;
424 assert!(node_states[node.0] == State::Included);
430 fn filter_edges<'q>(query: &'q DepGraphQuery<DefId>,
431 nodes: &FnvHashSet<&'q DepNode<DefId>>)
432 -> Vec<(&'q DepNode<DefId>, &'q DepNode<DefId>)>
436 .filter(|&(source, target)| nodes.contains(source) && nodes.contains(target))