src/librustc_incremental/assert_dep_graph.rs

   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.
   4 //
   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.
  10
  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 codegen, 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
  20 //! loaded from disk.
  21 //!
  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.
  27 //!
  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.
  32 //!
  33 //! Example:
  34 //!
  35 //! ```
  36 //! #[rustc_if_this_changed(Hir)]
  37 //! fn foo() { }
  38 //!
  39 //! #[rustc_then_this_would_need(codegen)] //~ ERROR no path from `foo`
  40 //! fn bar() { }
  41 //!
  42 //! #[rustc_then_this_would_need(codegen)] //~ ERROR OK
  43 //! fn baz() { foo(); }
  44 //! ```
  45
  46 use graphviz as dot;
  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::implementation::{
  53     Direction, INCOMING, OUTGOING, NodeIndex
  54 };
  55 use rustc::hir;
  56 use rustc::hir::intravisit::{self, NestedVisitorMap, Visitor};
  57 use rustc::ich::{ATTR_IF_THIS_CHANGED, ATTR_THEN_THIS_WOULD_NEED};
  58 use graphviz::IntoCow;
  59 use std::env;
  60 use std::fs::{self, File};
  61 use std::io::Write;
  62 use syntax::ast;
  63 use syntax_pos::Span;
  64
  65 pub fn assert_dep_graph<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>) {
  66     tcx.dep_graph.with_ignore(|| {
  67         if tcx.sess.opts.debugging_opts.dump_dep_graph {
  68             dump_graph(tcx);
  69         }
  70
  71         // if the `rustc_attrs` feature is not enabled, then the
  72         // attributes we are interested in cannot be present anyway, so
  73         // skip the walk.
  74         if !tcx.features().rustc_attrs {
  75             return;
  76         }
  77
  78         // Find annotations supplied by user (if any).
  79         let (if_this_changed, then_this_would_need) = {
  80             let mut visitor = IfThisChanged { tcx,
  81                                             if_this_changed: vec![],
  82                                             then_this_would_need: vec![] };
  83             visitor.process_attrs(ast::CRATE_NODE_ID, &tcx.hir.krate().attrs);
  84             tcx.hir.krate().visit_all_item_likes(&mut visitor.as_deep_visitor());
  85             (visitor.if_this_changed, visitor.then_this_would_need)
  86         };
  87
  88         if !if_this_changed.is_empty() || !then_this_would_need.is_empty() {
  89             assert!(tcx.sess.opts.debugging_opts.query_dep_graph,
  90                     "cannot use the `#[{}]` or `#[{}]` annotations \
  91                     without supplying `-Z query-dep-graph`",
  92                     ATTR_IF_THIS_CHANGED, ATTR_THEN_THIS_WOULD_NEED);
  93         }
  94
  95         // Check paths.
  96         check_paths(tcx, &if_this_changed, &then_this_would_need);
  97     })
  98 }
  99
 100 type Sources = Vec<(Span, DefId, DepNode)>;
 101 type Targets = Vec<(Span, ast::Name, ast::NodeId, DepNode)>;
 102
 103 struct IfThisChanged<'a, 'tcx:'a> {
 104     tcx: TyCtxt<'a, 'tcx, 'tcx>,
 105     if_this_changed: Sources,
 106     then_this_would_need: Targets,
 107 }
 108
 109 impl<'a, 'tcx> IfThisChanged<'a, 'tcx> {
 110     fn argument(&self, attr: &ast::Attribute) -> Option<ast::Name> {
 111         let mut value = None;
 112         for list_item in attr.meta_item_list().unwrap_or_default() {
 113             match list_item.word() {
 114                 Some(word) if value.is_none() =>
 115                     value = Some(word.name()),
 116                 _ =>
 117                     // FIXME better-encapsulate meta_item (don't directly access `node`)
 118                     span_bug!(list_item.span(), "unexpected meta-item {:?}", list_item.node),
 119             }
 120         }
 121         value
 122     }
 123
 124     fn process_attrs(&mut self, node_id: ast::NodeId, attrs: &[ast::Attribute]) {
 125         let def_id = self.tcx.hir.local_def_id(node_id);
 126         let def_path_hash = self.tcx.def_path_hash(def_id);
 127         for attr in attrs {
 128             if attr.check_name(ATTR_IF_THIS_CHANGED) {
 129                 let dep_node_interned = self.argument(attr);
 130                 let dep_node = match dep_node_interned {
 131                     None => def_path_hash.to_dep_node(DepKind::Hir),
 132                     Some(n) => {
 133                         match DepNode::from_label_string(&n.as_str(), def_path_hash) {
 134                             Ok(n) => n,
 135                             Err(()) => {
 136                                 self.tcx.sess.span_fatal(
 137                                     attr.span,
 138                                     &format!("unrecognized DepNode variant {:?}", n));
 139                             }
 140                         }
 141                     }
 142                 };
 143                 self.if_this_changed.push((attr.span, def_id, dep_node));
 144             } else if attr.check_name(ATTR_THEN_THIS_WOULD_NEED) {
 145                 let dep_node_interned = self.argument(attr);
 146                 let dep_node = match dep_node_interned {
 147                     Some(n) => {
 148                         match DepNode::from_label_string(&n.as_str(), def_path_hash) {
 149                             Ok(n) => n,
 150                             Err(()) => {
 151                                 self.tcx.sess.span_fatal(
 152                                     attr.span,
 153                                     &format!("unrecognized DepNode variant {:?}", n));
 154                             }
 155                         }
 156                     }
 157                     None => {
 158                         self.tcx.sess.span_fatal(
 159                             attr.span,
 160                             "missing DepNode variant");
 161                     }
 162                 };
 163                 self.then_this_would_need.push((attr.span,
 164                                                 dep_node_interned.unwrap(),
 165                                                 node_id,
 166                                                 dep_node));
 167             }
 168         }
 169     }
 170 }
 171
 172 impl<'a, 'tcx> Visitor<'tcx> for IfThisChanged<'a, 'tcx> {
 173     fn nested_visit_map<'this>(&'this mut self) -> NestedVisitorMap<'this, 'tcx> {
 174         NestedVisitorMap::OnlyBodies(&self.tcx.hir)
 175     }
 176
 177     fn visit_item(&mut self, item: &'tcx hir::Item) {
 178         self.process_attrs(item.id, &item.attrs);
 179         intravisit::walk_item(self, item);
 180     }
 181
 182     fn visit_trait_item(&mut self, trait_item: &'tcx hir::TraitItem) {
 183         self.process_attrs(trait_item.id, &trait_item.attrs);
 184         intravisit::walk_trait_item(self, trait_item);
 185     }
 186
 187     fn visit_impl_item(&mut self, impl_item: &'tcx hir::ImplItem) {
 188         self.process_attrs(impl_item.id, &impl_item.attrs);
 189         intravisit::walk_impl_item(self, impl_item);
 190     }
 191
 192     fn visit_struct_field(&mut self, s: &'tcx hir::StructField) {
 193         self.process_attrs(s.id, &s.attrs);
 194         intravisit::walk_struct_field(self, s);
 195     }
 196 }
 197
 198 fn check_paths<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
 199                          if_this_changed: &Sources,
 200                          then_this_would_need: &Targets)
 201 {
 202     // Return early here so as not to construct the query, which is not cheap.
 203     if if_this_changed.is_empty() {
 204         for &(target_span, _, _, _) in then_this_would_need {
 205             tcx.sess.span_err(
 206                 target_span,
 207                 "no #[rustc_if_this_changed] annotation detected");
 208
 209         }
 210         return;
 211     }
 212     let query = tcx.dep_graph.query();
 213     for &(_, source_def_id, ref source_dep_node) in if_this_changed {
 214         let dependents = query.transitive_predecessors(source_dep_node);
 215         for &(target_span, ref target_pass, _, ref target_dep_node) in then_this_would_need {
 216             if !dependents.contains(&target_dep_node) {
 217                 tcx.sess.span_err(
 218                     target_span,
 219                     &format!("no path from `{}` to `{}`",
 220                              tcx.item_path_str(source_def_id),
 221                              target_pass));
 222             } else {
 223                 tcx.sess.span_err(
 224                     target_span,
 225                     "OK");
 226             }
 227         }
 228     }
 229 }
 230
 231 fn dump_graph(tcx: TyCtxt) {
 232     let path: String = env::var("RUST_DEP_GRAPH").unwrap_or_else(|_| format!("dep_graph"));
 233     let query = tcx.dep_graph.query();
 234
 235     let nodes = match env::var("RUST_DEP_GRAPH_FILTER") {
 236         Ok(string) => {
 237             // Expect one of: "-> target", "source -> target", or "source ->".
 238             let edge_filter = EdgeFilter::new(&string).unwrap_or_else(|e| {
 239                 bug!("invalid filter: {}", e)
 240             });
 241             let sources = node_set(&query, &edge_filter.source);
 242             let targets = node_set(&query, &edge_filter.target);
 243             filter_nodes(&query, &sources, &targets)
 244         }
 245         Err(_) => {
 246             query.nodes()
 247                  .into_iter()
 248                  .collect()
 249         }
 250     };
 251     let edges = filter_edges(&query, &nodes);
 252
 253     { // dump a .txt file with just the edges:
 254         let txt_path = format!("{}.txt", path);
 255         let mut file = File::create(&txt_path).unwrap();
 256         for &(ref source, ref target) in &edges {
 257             write!(file, "{:?} -> {:?}\n", source, target).unwrap();
 258         }
 259     }
 260
 261     { // dump a .dot file in graphviz format:
 262         let dot_path = format!("{}.dot", path);
 263         let mut v = Vec::new();
 264         dot::render(&GraphvizDepGraph(nodes, edges), &mut v).unwrap();
 265         fs::write(dot_path, v).unwrap();
 266     }
 267 }
 268
 269 pub struct GraphvizDepGraph<'q>(FxHashSet<&'q DepNode>,
 270                                 Vec<(&'q DepNode, &'q DepNode)>);
 271
 272 impl<'a, 'tcx, 'q> dot::GraphWalk<'a> for GraphvizDepGraph<'q> {
 273     type Node = &'q DepNode;
 274     type Edge = (&'q DepNode, &'q DepNode);
 275     fn nodes(&self) -> dot::Nodes<&'q DepNode> {
 276         let nodes: Vec<_> = self.0.iter().cloned().collect();
 277         nodes.into_cow()
 278     }
 279     fn edges(&self) -> dot::Edges<(&'q DepNode, &'q DepNode)> {
 280         self.1[..].into_cow()
 281     }
 282     fn source(&self, edge: &(&'q DepNode, &'q DepNode)) -> &'q DepNode {
 283         edge.0
 284     }
 285     fn target(&self, edge: &(&'q DepNode, &'q DepNode)) -> &'q DepNode {
 286         edge.1
 287     }
 288 }
 289
 290 impl<'a, 'tcx, 'q> dot::Labeller<'a> for GraphvizDepGraph<'q> {
 291     type Node = &'q DepNode;
 292     type Edge = (&'q DepNode, &'q DepNode);
 293     fn graph_id(&self) -> dot::Id {
 294         dot::Id::new("DependencyGraph").unwrap()
 295     }
 296     fn node_id(&self, n: &&'q DepNode) -> dot::Id {
 297         let s: String =
 298             format!("{:?}", n).chars()
 299                               .map(|c| if c == '_' || c.is_alphanumeric() { c } else { '_' })
 300                               .collect();
 301         debug!("n={:?} s={:?}", n, s);
 302         dot::Id::new(s).unwrap()
 303     }
 304     fn node_label(&self, n: &&'q DepNode) -> dot::LabelText {
 305         dot::LabelText::label(format!("{:?}", n))
 306     }
 307 }
 308
 309 // Given an optional filter like `"x,y,z"`, returns either `None` (no
 310 // filter) or the set of nodes whose labels contain all of those
 311 // substrings.
 312 fn node_set<'q>(query: &'q DepGraphQuery, filter: &DepNodeFilter)
 313                 -> Option<FxHashSet<&'q DepNode>>
 314 {
 315     debug!("node_set(filter={:?})", filter);
 316
 317     if filter.accepts_all() {
 318         return None;
 319     }
 320
 321     Some(query.nodes().into_iter().filter(|n| filter.test(n)).collect())
 322 }
 323
 324 fn filter_nodes<'q>(query: &'q DepGraphQuery,
 325                     sources: &Option<FxHashSet<&'q DepNode>>,
 326                     targets: &Option<FxHashSet<&'q DepNode>>)
 327                     -> FxHashSet<&'q DepNode>
 328 {
 329     if let &Some(ref sources) = sources {
 330         if let &Some(ref targets) = targets {
 331             walk_between(query, sources, targets)
 332         } else {
 333             walk_nodes(query, sources, OUTGOING)
 334         }
 335     } else if let &Some(ref targets) = targets {
 336         walk_nodes(query, targets, INCOMING)
 337     } else {
 338         query.nodes().into_iter().collect()
 339     }
 340 }
 341
 342 fn walk_nodes<'q>(query: &'q DepGraphQuery,
 343                   starts: &FxHashSet<&'q DepNode>,
 344                   direction: Direction)
 345                   -> FxHashSet<&'q DepNode>
 346 {
 347     let mut set = FxHashSet();
 348     for &start in starts {
 349         debug!("walk_nodes: start={:?} outgoing?={:?}", start, direction == OUTGOING);
 350         if set.insert(start) {
 351             let mut stack = vec![query.indices[start]];
 352             while let Some(index) = stack.pop() {
 353                 for (_, edge) in query.graph.adjacent_edges(index, direction) {
 354                     let neighbor_index = edge.source_or_target(direction);
 355                     let neighbor = query.graph.node_data(neighbor_index);
 356                     if set.insert(neighbor) {
 357                         stack.push(neighbor_index);
 358                     }
 359                 }
 360             }
 361         }
 362     }
 363     set
 364 }
 365
 366 fn walk_between<'q>(query: &'q DepGraphQuery,
 367                     sources: &FxHashSet<&'q DepNode>,
 368                     targets: &FxHashSet<&'q DepNode>)
 369                     -> FxHashSet<&'q DepNode>
 370 {
 371     // This is a bit tricky. We want to include a node only if it is:
 372     // (a) reachable from a source and (b) will reach a target. And we
 373     // have to be careful about cycles etc.  Luckily efficiency is not
 374     // a big concern!
 375
 376     #[derive(Copy, Clone, PartialEq)]
 377     enum State { Undecided, Deciding, Included, Excluded }
 378
 379     let mut node_states = vec![State::Undecided; query.graph.len_nodes()];
 380
 381     for &target in targets {
 382         node_states[query.indices[target].0] = State::Included;
 383     }
 384
 385     for source in sources.iter().map(|&n| query.indices[n]) {
 386         recurse(query, &mut node_states, source);
 387     }
 388
 389     return query.nodes()
 390                 .into_iter()
 391                 .filter(|&n| {
 392                     let index = query.indices[n];
 393                     node_states[index.0] == State::Included
 394                 })
 395                 .collect();
 396
 397     fn recurse(query: &DepGraphQuery,
 398                node_states: &mut [State],
 399                node: NodeIndex)
 400                -> bool
 401     {
 402         match node_states[node.0] {
 403             // known to reach a target
 404             State::Included => return true,
 405
 406             // known not to reach a target
 407             State::Excluded => return false,
 408
 409             // backedge, not yet known, say false
 410             State::Deciding => return false,
 411
 412             State::Undecided => { }
 413         }
 414
 415         node_states[node.0] = State::Deciding;
 416
 417         for neighbor_index in query.graph.successor_nodes(node) {
 418             if recurse(query, node_states, neighbor_index) {
 419                 node_states[node.0] = State::Included;
 420             }
 421         }
 422
 423         // if we didn't find a path to target, then set to excluded
 424         if node_states[node.0] == State::Deciding {
 425             node_states[node.0] = State::Excluded;
 426             false
 427         } else {
 428             assert!(node_states[node.0] == State::Included);
 429             true
 430         }
 431     }
 432 }
 433
 434 fn filter_edges<'q>(query: &'q DepGraphQuery,
 435                     nodes: &FxHashSet<&'q DepNode>)
 436                     -> Vec<(&'q DepNode, &'q DepNode)>
 437 {
 438     query.edges()
 439          .into_iter()
 440          .filter(|&(source, target)| nodes.contains(source) && nodes.contains(target))
 441          .collect()
 442 }