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