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