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