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