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::{DepGraphQuery, DepNode, DepKind};
  38 use rustc::dep_graph::debug::{DepNodeFilter, EdgeFilter};
  39 use rustc::hir::def_id::DefId;
  40 use rustc::ty::TyCtxt;
  41 use rustc_data_structures::fx::FxHashSet;
  42 use rustc_data_structures::graph::implementation::{
  43     Direction, INCOMING, OUTGOING, NodeIndex
  44 };
  45 use rustc::hir;
  46 use rustc::hir::intravisit::{self, NestedVisitorMap, Visitor};
  47 use rustc::ich::{ATTR_IF_THIS_CHANGED, ATTR_THEN_THIS_WOULD_NEED};
  48 use std::env;
  49 use std::fs::{self, File};
  50 use std::io::Write;
  51 use syntax::ast;
  52 use syntax_pos::Span;
  53
  54 pub fn assert_dep_graph<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>) {
  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 = IfThisChanged { tcx,
  70                                             if_this_changed: vec![],
  71                                             then_this_would_need: vec![] };
  72             visitor.process_attrs(ast::CRATE_NODE_ID, &tcx.hir().krate().attrs);
  73             tcx.hir().krate().visit_all_item_likes(&mut visitor.as_deep_visitor());
  74             (visitor.if_this_changed, visitor.then_this_would_need)
  75         };
  76
  77         if !if_this_changed.is_empty() || !then_this_would_need.is_empty() {
  78             assert!(tcx.sess.opts.debugging_opts.query_dep_graph,
  79                     "cannot use the `#[{}]` or `#[{}]` annotations \
  80                     without supplying `-Z query-dep-graph`",
  81                     ATTR_IF_THIS_CHANGED, ATTR_THEN_THIS_WOULD_NEED);
  82         }
  83
  84         // Check paths.
  85         check_paths(tcx, &if_this_changed, &then_this_would_need);
  86     })
  87 }
  88
  89 type Sources = Vec<(Span, DefId, DepNode)>;
  90 type Targets = Vec<(Span, ast::Name, ast::NodeId, DepNode)>;
  91
  92 struct IfThisChanged<'a, 'tcx:'a> {
  93     tcx: TyCtxt<'a, 'tcx, 'tcx>,
  94     if_this_changed: Sources,
  95     then_this_would_need: Targets,
  96 }
  97
  98 impl<'a, 'tcx> IfThisChanged<'a, 'tcx> {
  99     fn argument(&self, attr: &ast::Attribute) -> Option<ast::Name> {
 100         let mut value = None;
 101         for list_item in attr.meta_item_list().unwrap_or_default() {
 102             match list_item.word() {
 103                 Some(word) if value.is_none() =>
 104                     value = Some(word.name()),
 105                 _ =>
 106                     // FIXME better-encapsulate meta_item (don't directly access `node`)
 107                     span_bug!(list_item.span(), "unexpected meta-item {:?}", list_item.node),
 108             }
 109         }
 110         value
 111     }
 112
 113     fn process_attrs(&mut self, node_id: ast::NodeId, attrs: &[ast::Attribute]) {
 114         let def_id = self.tcx.hir().local_def_id(node_id);
 115         let def_path_hash = self.tcx.def_path_hash(def_id);
 116         for attr in attrs {
 117             if attr.check_name(ATTR_IF_THIS_CHANGED) {
 118                 let dep_node_interned = self.argument(attr);
 119                 let dep_node = match dep_node_interned {
 120                     None => def_path_hash.to_dep_node(DepKind::Hir),
 121                     Some(n) => {
 122                         match DepNode::from_label_string(&n.as_str(), def_path_hash) {
 123                             Ok(n) => n,
 124                             Err(()) => {
 125                                 self.tcx.sess.span_fatal(
 126                                     attr.span,
 127                                     &format!("unrecognized DepNode variant {:?}", n));
 128                             }
 129                         }
 130                     }
 131                 };
 132                 self.if_this_changed.push((attr.span, def_id, dep_node));
 133             } else if attr.check_name(ATTR_THEN_THIS_WOULD_NEED) {
 134                 let dep_node_interned = self.argument(attr);
 135                 let dep_node = match dep_node_interned {
 136                     Some(n) => {
 137                         match DepNode::from_label_string(&n.as_str(), def_path_hash) {
 138                             Ok(n) => n,
 139                             Err(()) => {
 140                                 self.tcx.sess.span_fatal(
 141                                     attr.span,
 142                                     &format!("unrecognized DepNode variant {:?}", n));
 143                             }
 144                         }
 145                     }
 146                     None => {
 147                         self.tcx.sess.span_fatal(
 148                             attr.span,
 149                             "missing DepNode variant");
 150                     }
 151                 };
 152                 self.then_this_would_need.push((attr.span,
 153                                                 dep_node_interned.unwrap(),
 154                                                 node_id,
 155                                                 dep_node));
 156             }
 157         }
 158     }
 159 }
 160
 161 impl<'a, 'tcx> Visitor<'tcx> for IfThisChanged<'a, 'tcx> {
 162     fn nested_visit_map<'this>(&'this mut self) -> NestedVisitorMap<'this, 'tcx> {
 163         NestedVisitorMap::OnlyBodies(&self.tcx.hir())
 164     }
 165
 166     fn visit_item(&mut self, item: &'tcx hir::Item) {
 167         self.process_attrs(item.id, &item.attrs);
 168         intravisit::walk_item(self, item);
 169     }
 170
 171     fn visit_trait_item(&mut self, trait_item: &'tcx hir::TraitItem) {
 172         self.process_attrs(trait_item.id, &trait_item.attrs);
 173         intravisit::walk_trait_item(self, trait_item);
 174     }
 175
 176     fn visit_impl_item(&mut self, impl_item: &'tcx hir::ImplItem) {
 177         self.process_attrs(impl_item.id, &impl_item.attrs);
 178         intravisit::walk_impl_item(self, impl_item);
 179     }
 180
 181     fn visit_struct_field(&mut self, s: &'tcx hir::StructField) {
 182         self.process_attrs(s.id, &s.attrs);
 183         intravisit::walk_struct_field(self, s);
 184     }
 185 }
 186
 187 fn check_paths<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
 188                          if_this_changed: &Sources,
 189                          then_this_would_need: &Targets)
 190 {
 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(
 195                 target_span,
 196                 "no #[rustc_if_this_changed] annotation detected");
 197
 198         }
 199         return;
 200     }
 201     let query = tcx.dep_graph.query();
 202     for &(_, source_def_id, ref source_dep_node) in if_this_changed {
 203         let dependents = query.transitive_predecessors(source_dep_node);
 204         for &(target_span, ref target_pass, _, ref target_dep_node) in then_this_would_need {
 205             if !dependents.contains(&target_dep_node) {
 206                 tcx.sess.span_err(
 207                     target_span,
 208                     &format!("no path from `{}` to `{}`",
 209                              tcx.item_path_str(source_def_id),
 210                              target_pass));
 211             } else {
 212                 tcx.sess.span_err(
 213                     target_span,
 214                     "OK");
 215             }
 216         }
 217     }
 218 }
 219
 220 fn dump_graph(tcx: TyCtxt<'_, '_, '_>) {
 221     let path: String = env::var("RUST_DEP_GRAPH").unwrap_or_else(|_| "dep_graph".to_string());
 222     let query = tcx.dep_graph.query();
 223
 224     let nodes = match env::var("RUST_DEP_GRAPH_FILTER") {
 225         Ok(string) => {
 226             // Expect one of: "-> target", "source -> target", or "source ->".
 227             let edge_filter = EdgeFilter::new(&string).unwrap_or_else(|e| {
 228                 bug!("invalid filter: {}", e)
 229             });
 230             let sources = node_set(&query, &edge_filter.source);
 231             let targets = node_set(&query, &edge_filter.target);
 232             filter_nodes(&query, &sources, &targets)
 233         }
 234         Err(_) => {
 235             query.nodes()
 236                  .into_iter()
 237                  .collect()
 238         }
 239     };
 240     let edges = filter_edges(&query, &nodes);
 241
 242     { // dump a .txt file with just the edges:
 243         let txt_path = format!("{}.txt", path);
 244         let mut file = File::create(&txt_path).unwrap();
 245         for &(ref source, ref target) in &edges {
 246             write!(file, "{:?} -> {:?}\n", source, target).unwrap();
 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>,
 259                                 Vec<(&'q DepNode, &'q DepNode)>);
 260
 261 impl<'a, 'tcx, 'q> dot::GraphWalk<'a> for GraphvizDepGraph<'q> {
 262     type Node = &'q DepNode;
 263     type Edge = (&'q DepNode, &'q DepNode);
 264     fn nodes(&self) -> dot::Nodes<'_, &'q DepNode> {
 265         let nodes: Vec<_> = self.0.iter().cloned().collect();
 266         nodes.into()
 267     }
 268     fn edges(&self) -> dot::Edges<'_, (&'q DepNode, &'q DepNode)> {
 269         self.1[..].into()
 270     }
 271     fn source(&self, edge: &(&'q DepNode, &'q DepNode)) -> &'q DepNode {
 272         edge.0
 273     }
 274     fn target(&self, edge: &(&'q DepNode, &'q DepNode)) -> &'q DepNode {
 275         edge.1
 276     }
 277 }
 278
 279 impl<'a, 'tcx, 'q> dot::Labeller<'a> for GraphvizDepGraph<'q> {
 280     type Node = &'q DepNode;
 281     type Edge = (&'q DepNode, &'q DepNode);
 282     fn graph_id(&self) -> dot::Id<'_> {
 283         dot::Id::new("DependencyGraph").unwrap()
 284     }
 285     fn node_id(&self, n: &&'q DepNode) -> dot::Id<'_> {
 286         let s: String =
 287             format!("{:?}", n).chars()
 288                               .map(|c| if c == '_' || c.is_alphanumeric() { c } else { '_' })
 289                               .collect();
 290         debug!("n={:?} s={:?}", n, s);
 291         dot::Id::new(s).unwrap()
 292     }
 293     fn node_label(&self, n: &&'q DepNode) -> dot::LabelText<'_> {
 294         dot::LabelText::label(format!("{:?}", n))
 295     }
 296 }
 297
 298 // Given an optional filter like `"x,y,z"`, returns either `None` (no
 299 // filter) or the set of nodes whose labels contain all of those
 300 // substrings.
 301 fn node_set<'q>(query: &'q DepGraphQuery, filter: &DepNodeFilter)
 302                 -> Option<FxHashSet<&'q DepNode>>
 303 {
 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>(query: &'q DepGraphQuery,
 314                     sources: &Option<FxHashSet<&'q DepNode>>,
 315                     targets: &Option<FxHashSet<&'q DepNode>>)
 316                     -> FxHashSet<&'q DepNode>
 317 {
 318     if let &Some(ref sources) = sources {
 319         if let &Some(ref targets) = targets {
 320             walk_between(query, sources, targets)
 321         } else {
 322             walk_nodes(query, sources, OUTGOING)
 323         }
 324     } else if let &Some(ref targets) = targets {
 325         walk_nodes(query, targets, INCOMING)
 326     } else {
 327         query.nodes().into_iter().collect()
 328     }
 329 }
 330
 331 fn walk_nodes<'q>(query: &'q DepGraphQuery,
 332                   starts: &FxHashSet<&'q DepNode>,
 333                   direction: Direction)
 334                   -> FxHashSet<&'q DepNode>
 335 {
 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>(query: &'q DepGraphQuery,
 356                     sources: &FxHashSet<&'q DepNode>,
 357                     targets: &FxHashSet<&'q DepNode>)
 358                     -> FxHashSet<&'q DepNode>
 359 {
 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 { Undecided, Deciding, Included, Excluded }
 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.nodes()
 379                 .into_iter()
 380                 .filter(|&n| {
 381                     let index = query.indices[n];
 382                     node_states[index.0] == State::Included
 383                 })
 384                 .collect();
 385
 386     fn recurse(query: &DepGraphQuery,
 387                node_states: &mut [State],
 388                node: NodeIndex)
 389                -> bool
 390     {
 391         match node_states[node.0] {
 392             // known to reach a target
 393             State::Included => return true,
 394
 395             // known not to reach a target
 396             State::Excluded => return false,
 397
 398             // backedge, not yet known, say false
 399             State::Deciding => return false,
 400
 401             State::Undecided => { }
 402         }
 403
 404         node_states[node.0] = State::Deciding;
 405
 406         for neighbor_index in query.graph.successor_nodes(node) {
 407             if recurse(query, node_states, neighbor_index) {
 408                 node_states[node.0] = State::Included;
 409             }
 410         }
 411
 412         // if we didn't find a path to target, then set to excluded
 413         if node_states[node.0] == State::Deciding {
 414             node_states[node.0] = State::Excluded;
 415             false
 416         } else {
 417             assert!(node_states[node.0] == State::Included);
 418             true
 419         }
 420     }
 421 }
 422
 423 fn filter_edges<'q>(query: &'q DepGraphQuery,
 424                     nodes: &FxHashSet<&'q DepNode>)
 425                     -> Vec<(&'q DepNode, &'q DepNode)>
 426 {
 427     query.edges()
 428          .into_iter()
 429          .filter(|&(source, target)| nodes.contains(source) && nodes.contains(target))
 430          .collect()
 431 }