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("foo")]`, which will report a
30 //! source node of `foo(def_id)`. The `"foo"` is optional and
31 //! defaults to `"Hir"` if omitted.
36 //! #[rustc_if_this_changed(Hir)]
39 //! #[rustc_then_this_would_need(trans)] //~ ERROR no path from `foo`
42 //! #[rustc_then_this_would_need(trans)] //~ ERROR OK
43 //! fn baz() { foo(); }
47 use rustc::dep_graph::{DepGraphQuery, DepNode, DepKind};
48 use rustc::dep_graph::debug::{DepNodeFilter, EdgeFilter};
49 use rustc::hir::def_id::DefId;
50 use rustc::ty::TyCtxt;
51 use rustc_data_structures::fx::FxHashSet;
52 use rustc_data_structures::graph::{Direction, INCOMING, OUTGOING, NodeIndex};
54 use rustc::hir::intravisit::{self, NestedVisitorMap, Visitor};
55 use rustc::ich::{ATTR_IF_THIS_CHANGED, ATTR_THEN_THIS_WOULD_NEED};
56 use graphviz::IntoCow;
63 pub fn assert_dep_graph<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>) {
64 let _ignore = tcx.dep_graph.in_ignore();
66 if tcx.sess.opts.debugging_opts.dump_dep_graph {
70 // if the `rustc_attrs` feature is not enabled, then the
71 // attributes we are interested in cannot be present anyway, so
73 if !tcx.sess.features.borrow().rustc_attrs {
77 // Find annotations supplied by user (if any).
78 let (if_this_changed, then_this_would_need) = {
79 let mut visitor = IfThisChanged { tcx: tcx,
80 if_this_changed: vec![],
81 then_this_would_need: vec![] };
82 visitor.process_attrs(ast::CRATE_NODE_ID, &tcx.hir.krate().attrs);
83 tcx.hir.krate().visit_all_item_likes(&mut visitor.as_deep_visitor());
84 (visitor.if_this_changed, visitor.then_this_would_need)
87 if !if_this_changed.is_empty() || !then_this_would_need.is_empty() {
88 assert!(tcx.sess.opts.debugging_opts.query_dep_graph,
89 "cannot use the `#[{}]` or `#[{}]` annotations \
90 without supplying `-Z query-dep-graph`",
91 ATTR_IF_THIS_CHANGED, ATTR_THEN_THIS_WOULD_NEED);
95 check_paths(tcx, &if_this_changed, &then_this_would_need);
98 type Sources = Vec<(Span, DefId, DepNode)>;
99 type Targets = Vec<(Span, ast::Name, ast::NodeId, DepNode)>;
101 struct IfThisChanged<'a, 'tcx:'a> {
102 tcx: TyCtxt<'a, 'tcx, 'tcx>,
103 if_this_changed: Sources,
104 then_this_would_need: Targets,
107 impl<'a, 'tcx> IfThisChanged<'a, 'tcx> {
108 fn argument(&self, attr: &ast::Attribute) -> Option<ast::Name> {
109 let mut value = None;
110 for list_item in attr.meta_item_list().unwrap_or_default() {
111 match list_item.word() {
112 Some(word) if value.is_none() =>
113 value = Some(word.name().clone()),
115 // FIXME better-encapsulate meta_item (don't directly access `node`)
116 span_bug!(list_item.span(), "unexpected meta-item {:?}", list_item.node),
122 fn process_attrs(&mut self, node_id: ast::NodeId, attrs: &[ast::Attribute]) {
123 let def_id = self.tcx.hir.local_def_id(node_id);
124 let def_path_hash = self.tcx.def_path_hash(def_id);
126 if attr.check_name(ATTR_IF_THIS_CHANGED) {
127 let dep_node_interned = self.argument(attr);
128 let dep_node = match dep_node_interned {
129 None => def_path_hash.to_dep_node(DepKind::Hir),
131 match DepNode::from_label_string(&n.as_str(), def_path_hash) {
134 self.tcx.sess.span_fatal(
136 &format!("unrecognized DepNode variant {:?}", n));
141 self.if_this_changed.push((attr.span, def_id, dep_node));
142 } else if attr.check_name(ATTR_THEN_THIS_WOULD_NEED) {
143 let dep_node_interned = self.argument(attr);
144 let dep_node = match dep_node_interned {
146 match DepNode::from_label_string(&n.as_str(), def_path_hash) {
149 self.tcx.sess.span_fatal(
151 &format!("unrecognized DepNode variant {:?}", n));
156 self.tcx.sess.span_fatal(
158 "missing DepNode variant");
161 self.then_this_would_need.push((attr.span,
162 dep_node_interned.unwrap(),
170 impl<'a, 'tcx> Visitor<'tcx> for IfThisChanged<'a, 'tcx> {
171 fn nested_visit_map<'this>(&'this mut self) -> NestedVisitorMap<'this, 'tcx> {
172 NestedVisitorMap::OnlyBodies(&self.tcx.hir)
175 fn visit_item(&mut self, item: &'tcx hir::Item) {
176 self.process_attrs(item.id, &item.attrs);
177 intravisit::walk_item(self, item);
180 fn visit_trait_item(&mut self, trait_item: &'tcx hir::TraitItem) {
181 self.process_attrs(trait_item.id, &trait_item.attrs);
182 intravisit::walk_trait_item(self, trait_item);
185 fn visit_impl_item(&mut self, impl_item: &'tcx hir::ImplItem) {
186 self.process_attrs(impl_item.id, &impl_item.attrs);
187 intravisit::walk_impl_item(self, impl_item);
190 fn visit_struct_field(&mut self, s: &'tcx hir::StructField) {
191 self.process_attrs(s.id, &s.attrs);
192 intravisit::walk_struct_field(self, s);
196 fn check_paths<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
197 if_this_changed: &Sources,
198 then_this_would_need: &Targets)
200 // Return early here so as not to construct the query, which is not cheap.
201 if if_this_changed.is_empty() {
202 for &(target_span, _, _, _) in then_this_would_need {
205 "no #[rustc_if_this_changed] annotation detected");
210 let query = tcx.dep_graph.query();
211 for &(_, source_def_id, ref source_dep_node) in if_this_changed {
212 let dependents = query.transitive_successors(source_dep_node);
213 for &(target_span, ref target_pass, _, ref target_dep_node) in then_this_would_need {
214 if !dependents.contains(&target_dep_node) {
217 &format!("no path from `{}` to `{}`",
218 tcx.item_path_str(source_def_id),
229 fn dump_graph(tcx: TyCtxt) {
230 let path: String = env::var("RUST_DEP_GRAPH").unwrap_or_else(|_| format!("dep_graph"));
231 let query = tcx.dep_graph.query();
233 let nodes = match env::var("RUST_DEP_GRAPH_FILTER") {
235 // Expect one of: "-> target", "source -> target", or "source ->".
236 let edge_filter = EdgeFilter::new(&string).unwrap_or_else(|e| {
237 bug!("invalid filter: {}", e)
239 let sources = node_set(&query, &edge_filter.source);
240 let targets = node_set(&query, &edge_filter.target);
241 filter_nodes(&query, &sources, &targets)
249 let edges = filter_edges(&query, &nodes);
251 { // dump a .txt file with just the edges:
252 let txt_path = format!("{}.txt", path);
253 let mut file = File::create(&txt_path).unwrap();
254 for &(ref source, ref target) in &edges {
255 write!(file, "{:?} -> {:?}\n", source, target).unwrap();
259 { // dump a .dot file in graphviz format:
260 let dot_path = format!("{}.dot", path);
261 let mut v = Vec::new();
262 dot::render(&GraphvizDepGraph(nodes, edges), &mut v).unwrap();
263 File::create(&dot_path).and_then(|mut f| f.write_all(&v)).unwrap();
267 pub struct GraphvizDepGraph<'q>(FxHashSet<&'q DepNode>,
268 Vec<(&'q DepNode, &'q DepNode)>);
270 impl<'a, 'tcx, 'q> dot::GraphWalk<'a> for GraphvizDepGraph<'q> {
271 type Node = &'q DepNode;
272 type Edge = (&'q DepNode, &'q DepNode);
273 fn nodes(&self) -> dot::Nodes<&'q DepNode> {
274 let nodes: Vec<_> = self.0.iter().cloned().collect();
277 fn edges(&self) -> dot::Edges<(&'q DepNode, &'q DepNode)> {
278 self.1[..].into_cow()
280 fn source(&self, edge: &(&'q DepNode, &'q DepNode)) -> &'q DepNode {
283 fn target(&self, edge: &(&'q DepNode, &'q DepNode)) -> &'q DepNode {
288 impl<'a, 'tcx, 'q> dot::Labeller<'a> for GraphvizDepGraph<'q> {
289 type Node = &'q DepNode;
290 type Edge = (&'q DepNode, &'q DepNode);
291 fn graph_id(&self) -> dot::Id {
292 dot::Id::new("DependencyGraph").unwrap()
294 fn node_id(&self, n: &&'q DepNode) -> dot::Id {
296 format!("{:?}", n).chars()
297 .map(|c| if c == '_' || c.is_alphanumeric() { c } else { '_' })
299 debug!("n={:?} s={:?}", n, s);
300 dot::Id::new(s).unwrap()
302 fn node_label(&self, n: &&'q DepNode) -> dot::LabelText {
303 dot::LabelText::label(format!("{:?}", n))
307 // Given an optional filter like `"x,y,z"`, returns either `None` (no
308 // filter) or the set of nodes whose labels contain all of those
310 fn node_set<'q>(query: &'q DepGraphQuery, filter: &DepNodeFilter)
311 -> Option<FxHashSet<&'q DepNode>>
313 debug!("node_set(filter={:?})", filter);
315 if filter.accepts_all() {
319 Some(query.nodes().into_iter().filter(|n| filter.test(n)).collect())
322 fn filter_nodes<'q>(query: &'q DepGraphQuery,
323 sources: &Option<FxHashSet<&'q DepNode>>,
324 targets: &Option<FxHashSet<&'q DepNode>>)
325 -> FxHashSet<&'q DepNode>
327 if let &Some(ref sources) = sources {
328 if let &Some(ref targets) = targets {
329 walk_between(query, sources, targets)
331 walk_nodes(query, sources, OUTGOING)
333 } else if let &Some(ref targets) = targets {
334 walk_nodes(query, targets, INCOMING)
336 query.nodes().into_iter().collect()
340 fn walk_nodes<'q>(query: &'q DepGraphQuery,
341 starts: &FxHashSet<&'q DepNode>,
342 direction: Direction)
343 -> FxHashSet<&'q DepNode>
345 let mut set = FxHashSet();
346 for &start in starts {
347 debug!("walk_nodes: start={:?} outgoing?={:?}", start, direction == OUTGOING);
348 if set.insert(start) {
349 let mut stack = vec![query.indices[start]];
350 while let Some(index) = stack.pop() {
351 for (_, edge) in query.graph.adjacent_edges(index, direction) {
352 let neighbor_index = edge.source_or_target(direction);
353 let neighbor = query.graph.node_data(neighbor_index);
354 if set.insert(neighbor) {
355 stack.push(neighbor_index);
364 fn walk_between<'q>(query: &'q DepGraphQuery,
365 sources: &FxHashSet<&'q DepNode>,
366 targets: &FxHashSet<&'q DepNode>)
367 -> FxHashSet<&'q DepNode>
369 // This is a bit tricky. We want to include a node only if it is:
370 // (a) reachable from a source and (b) will reach a target. And we
371 // have to be careful about cycles etc. Luckily efficiency is not
374 #[derive(Copy, Clone, PartialEq)]
375 enum State { Undecided, Deciding, Included, Excluded }
377 let mut node_states = vec![State::Undecided; query.graph.len_nodes()];
379 for &target in targets {
380 node_states[query.indices[target].0] = State::Included;
383 for source in sources.iter().map(|&n| query.indices[n]) {
384 recurse(query, &mut node_states, source);
390 let index = query.indices[n];
391 node_states[index.0] == State::Included
395 fn recurse(query: &DepGraphQuery,
396 node_states: &mut [State],
400 match node_states[node.0] {
401 // known to reach a target
402 State::Included => return true,
404 // known not to reach a target
405 State::Excluded => return false,
407 // backedge, not yet known, say false
408 State::Deciding => return false,
410 State::Undecided => { }
413 node_states[node.0] = State::Deciding;
415 for neighbor_index in query.graph.successor_nodes(node) {
416 if recurse(query, node_states, neighbor_index) {
417 node_states[node.0] = State::Included;
421 // if we didn't find a path to target, then set to excluded
422 if node_states[node.0] == State::Deciding {
423 node_states[node.0] = State::Excluded;
426 assert!(node_states[node.0] == State::Included);
432 fn filter_edges<'q>(query: &'q DepGraphQuery,
433 nodes: &FxHashSet<&'q DepNode>)
434 -> Vec<(&'q DepNode, &'q DepNode)>
438 .filter(|&(source, target)| nodes.contains(source) && nodes.contains(target))