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