src/librustc_incremental/assert_dep_graph.rs

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