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