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
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.
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.
26 //! #[rustc_if_this_changed(Hir)]
29 //! #[rustc_then_this_would_need(codegen)] //~ ERROR no path from `foo`
32 //! #[rustc_then_this_would_need(codegen)] //~ ERROR OK
33 //! fn baz() { foo(); }
37 use rustc_data_structures::fx::FxHashSet;
38 use rustc_data_structures::graph::implementation::{Direction, NodeIndex, INCOMING, OUTGOING};
39 use rustc_graphviz as dot;
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,
46 use rustc_middle::hir::map::Map;
47 use rustc_middle::ty::TyCtxt;
48 use rustc_span::symbol::{sym, Symbol};
52 use std::fs::{self, File};
53 use std::io::{BufWriter, Write};
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);
61 if !tcx.sess.opts.debugging_opts.query_dep_graph {
65 // if the `rustc_attrs` feature is not enabled, then the
66 // attributes we are interested in cannot be present anyway, so
68 if !tcx.features().rustc_attrs {
72 // Find annotations supplied by user (if any).
73 let (if_this_changed, then_this_would_need) = {
75 IfThisChanged { tcx, if_this_changed: vec![], then_this_would_need: vec![] };
76 visitor.process_attrs(hir::CRATE_HIR_ID);
77 tcx.hir().krate().visit_all_item_likes(&mut visitor.as_deep_visitor());
78 (visitor.if_this_changed, visitor.then_this_would_need)
81 if !if_this_changed.is_empty() || !then_this_would_need.is_empty() {
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
92 check_paths(tcx, &if_this_changed, &then_this_would_need);
96 type Sources = Vec<(Span, DefId, DepNode)>;
97 type Targets = Vec<(Span, Symbol, hir::HirId, DepNode)>;
99 struct IfThisChanged<'tcx> {
101 if_this_changed: Sources,
102 then_this_would_need: Targets,
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),
112 // FIXME better-encapsulate meta_item (don't directly access `node`)
114 span_bug!(list_item.span(), "unexpected meta-item {:?}", list_item)
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);
126 if self.tcx.sess.check_name(attr, sym::rustc_if_this_changed) {
127 let dep_node_interned = self.argument(attr);
128 let dep_node = match dep_node_interned {
129 None => DepNode::from_def_path_hash(def_path_hash, DepKind::hir_owner),
130 Some(n) => match DepNode::from_label_string(&n.as_str(), def_path_hash) {
133 self.tcx.sess.span_fatal(
135 &format!("unrecognized DepNode variant {:?}", n),
140 self.if_this_changed.push((attr.span, def_id.to_def_id(), dep_node));
141 } else if self.tcx.sess.check_name(attr, sym::rustc_then_this_would_need) {
142 let dep_node_interned = self.argument(attr);
143 let dep_node = match dep_node_interned {
144 Some(n) => match DepNode::from_label_string(&n.as_str(), def_path_hash) {
147 self.tcx.sess.span_fatal(
149 &format!("unrecognized DepNode variant {:?}", n),
154 self.tcx.sess.span_fatal(attr.span, "missing DepNode variant");
157 self.then_this_would_need.push((
159 dep_node_interned.unwrap(),
168 impl Visitor<'tcx> for IfThisChanged<'tcx> {
169 type Map = Map<'tcx>;
171 fn nested_visit_map(&mut self) -> NestedVisitorMap<Self::Map> {
172 NestedVisitorMap::OnlyBodies(self.tcx.hir())
175 fn visit_item(&mut self, item: &'tcx hir::Item<'tcx>) {
176 self.process_attrs(item.hir_id());
177 intravisit::walk_item(self, item);
180 fn visit_trait_item(&mut self, trait_item: &'tcx hir::TraitItem<'tcx>) {
181 self.process_attrs(trait_item.hir_id());
182 intravisit::walk_trait_item(self, trait_item);
185 fn visit_impl_item(&mut self, impl_item: &'tcx hir::ImplItem<'tcx>) {
186 self.process_attrs(impl_item.hir_id());
187 intravisit::walk_impl_item(self, impl_item);
190 fn visit_field_def(&mut self, s: &'tcx hir::FieldDef<'tcx>) {
191 self.process_attrs(s.hir_id);
192 intravisit::walk_field_def(self, s);
196 fn check_paths<'tcx>(tcx: TyCtxt<'tcx>, if_this_changed: &Sources, then_this_would_need: &Targets) {
197 // Return early here so as not to construct the query, which is not cheap.
198 if if_this_changed.is_empty() {
199 for &(target_span, _, _, _) in then_this_would_need {
200 tcx.sess.span_err(target_span, "no `#[rustc_if_this_changed]` annotation detected");
204 tcx.dep_graph.with_query(|query| {
205 for &(_, source_def_id, ref source_dep_node) in if_this_changed {
206 let dependents = query.transitive_predecessors(source_dep_node);
207 for &(target_span, ref target_pass, _, ref target_dep_node) in then_this_would_need {
208 if !dependents.contains(&target_dep_node) {
212 "no path from `{}` to `{}`",
213 tcx.def_path_str(source_def_id),
218 tcx.sess.span_err(target_span, "OK");
225 fn dump_graph(query: &DepGraphQuery) {
226 let path: String = env::var("RUST_DEP_GRAPH").unwrap_or_else(|_| "dep_graph".to_string());
228 let nodes = match env::var("RUST_DEP_GRAPH_FILTER") {
230 // Expect one of: "-> target", "source -> target", or "source ->".
232 EdgeFilter::new(&string).unwrap_or_else(|e| bug!("invalid filter: {}", e));
233 let sources = node_set(&query, &edge_filter.source);
234 let targets = node_set(&query, &edge_filter.target);
235 filter_nodes(&query, &sources, &targets)
237 Err(_) => query.nodes().into_iter().collect(),
239 let edges = filter_edges(&query, &nodes);
242 // dump a .txt file with just the edges:
243 let txt_path = format!("{}.txt", path);
244 let mut file = BufWriter::new(File::create(&txt_path).unwrap());
245 for &(ref source, ref target) in &edges {
246 write!(file, "{:?} -> {:?}\n", source, target).unwrap();
251 // dump a .dot file in graphviz format:
252 let dot_path = format!("{}.dot", path);
253 let mut v = Vec::new();
254 dot::render(&GraphvizDepGraph(nodes, edges), &mut v).unwrap();
255 fs::write(dot_path, v).unwrap();
259 pub struct GraphvizDepGraph<'q>(FxHashSet<&'q DepNode>, Vec<(&'q DepNode, &'q DepNode)>);
261 impl<'a, '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();
268 fn edges(&self) -> dot::Edges<'_, (&'q DepNode, &'q DepNode)> {
271 fn source(&self, edge: &(&'q DepNode, &'q DepNode)) -> &'q DepNode {
274 fn target(&self, edge: &(&'q DepNode, &'q DepNode)) -> &'q DepNode {
279 impl<'a, '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()
285 fn node_id(&self, n: &&'q DepNode) -> dot::Id<'_> {
286 let s: String = format!("{:?}", n)
288 .map(|c| if c == '_' || c.is_alphanumeric() { c } else { '_' })
290 debug!("n={:?} s={:?}", n, s);
291 dot::Id::new(s).unwrap()
293 fn node_label(&self, n: &&'q DepNode) -> dot::LabelText<'_> {
294 dot::LabelText::label(format!("{:?}", n))
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
302 query: &'q DepGraphQuery,
303 filter: &DepNodeFilter,
304 ) -> Option<FxHashSet<&'q DepNode>> {
305 debug!("node_set(filter={:?})", filter);
307 if filter.accepts_all() {
311 Some(query.nodes().into_iter().filter(|n| filter.test(n)).collect())
315 query: &'q DepGraphQuery,
316 sources: &Option<FxHashSet<&'q DepNode>>,
317 targets: &Option<FxHashSet<&'q DepNode>>,
318 ) -> FxHashSet<&'q DepNode> {
319 if let Some(sources) = sources {
320 if let Some(targets) = targets {
321 walk_between(query, sources, targets)
323 walk_nodes(query, sources, OUTGOING)
325 } else if let Some(targets) = targets {
326 walk_nodes(query, targets, INCOMING)
328 query.nodes().into_iter().collect()
333 query: &'q DepGraphQuery,
334 starts: &FxHashSet<&'q DepNode>,
335 direction: Direction,
336 ) -> FxHashSet<&'q DepNode> {
337 let mut set = FxHashSet::default();
338 for &start in starts {
339 debug!("walk_nodes: start={:?} outgoing?={:?}", start, direction == OUTGOING);
340 if set.insert(start) {
341 let mut stack = vec![query.indices[start]];
342 while let Some(index) = stack.pop() {
343 for (_, edge) in query.graph.adjacent_edges(index, direction) {
344 let neighbor_index = edge.source_or_target(direction);
345 let neighbor = query.graph.node_data(neighbor_index);
346 if set.insert(neighbor) {
347 stack.push(neighbor_index);
357 query: &'q DepGraphQuery,
358 sources: &FxHashSet<&'q DepNode>,
359 targets: &FxHashSet<&'q DepNode>,
360 ) -> FxHashSet<&'q DepNode> {
361 // This is a bit tricky. We want to include a node only if it is:
362 // (a) reachable from a source and (b) will reach a target. And we
363 // have to be careful about cycles etc. Luckily efficiency is not
366 #[derive(Copy, Clone, PartialEq)]
374 let mut node_states = vec![State::Undecided; query.graph.len_nodes()];
376 for &target in targets {
377 node_states[query.indices[target].0] = State::Included;
380 for source in sources.iter().map(|&n| query.indices[n]) {
381 recurse(query, &mut node_states, source);
388 let index = query.indices[n];
389 node_states[index.0] == State::Included
393 fn recurse(query: &DepGraphQuery, node_states: &mut [State], node: NodeIndex) -> bool {
394 match node_states[node.0] {
395 // known to reach a target
396 State::Included => return true,
398 // known not to reach a target
399 State::Excluded => return false,
401 // backedge, not yet known, say false
402 State::Deciding => return false,
404 State::Undecided => {}
407 node_states[node.0] = State::Deciding;
409 for neighbor_index in query.graph.successor_nodes(node) {
410 if recurse(query, node_states, neighbor_index) {
411 node_states[node.0] = State::Included;
415 // if we didn't find a path to target, then set to excluded
416 if node_states[node.0] == State::Deciding {
417 node_states[node.0] = State::Excluded;
420 assert!(node_states[node.0] == State::Included);
427 query: &'q DepGraphQuery,
428 nodes: &FxHashSet<&'q DepNode>,
429 ) -> Vec<(&'q DepNode, &'q DepNode)> {
433 .filter(|&(source, target)| nodes.contains(source) && nodes.contains(target))