]>
Commit | Line | Data |
---|---|---|
9cc50fc6 SL |
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 | |
94b46f34 | 6 | //! exist in the graph. These checks run after codegen, so they view the |
54a0048b SL |
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 | |
9fa01778 | 15 | //! each case where no path exists. `compile-fail` tests can then be |
54a0048b | 16 | //! used to check when paths exist or do not. |
9cc50fc6 SL |
17 | //! |
18 | //! The full form of the `rustc_if_this_changed` annotation is | |
9e0c209e SL |
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. | |
9cc50fc6 SL |
22 | //! |
23 | //! Example: | |
24 | //! | |
25 | //! ``` | |
9e0c209e | 26 | //! #[rustc_if_this_changed(Hir)] |
9cc50fc6 SL |
27 | //! fn foo() { } |
28 | //! | |
94b46f34 | 29 | //! #[rustc_then_this_would_need(codegen)] //~ ERROR no path from `foo` |
9cc50fc6 SL |
30 | //! fn bar() { } |
31 | //! | |
94b46f34 | 32 | //! #[rustc_then_this_would_need(codegen)] //~ ERROR OK |
9cc50fc6 SL |
33 | //! fn baz() { foo(); } |
34 | //! ``` | |
35 | ||
36 | use graphviz as dot; | |
041b39d2 | 37 | use rustc::dep_graph::{DepGraphQuery, DepNode, DepKind}; |
a7813a04 | 38 | use rustc::dep_graph::debug::{DepNodeFilter, EdgeFilter}; |
54a0048b SL |
39 | use rustc::hir::def_id::DefId; |
40 | use rustc::ty::TyCtxt; | |
476ff2be | 41 | use rustc_data_structures::fx::FxHashSet; |
8faf50e0 XL |
42 | use rustc_data_structures::graph::implementation::{ |
43 | Direction, INCOMING, OUTGOING, NodeIndex | |
44 | }; | |
54a0048b | 45 | use rustc::hir; |
7cac9316 | 46 | use rustc::hir::intravisit::{self, NestedVisitorMap, Visitor}; |
cc61c64b | 47 | use rustc::ich::{ATTR_IF_THIS_CHANGED, ATTR_THEN_THIS_WOULD_NEED}; |
9cc50fc6 | 48 | use std::env; |
2c00a5a8 | 49 | use std::fs::{self, File}; |
9cc50fc6 SL |
50 | use std::io::Write; |
51 | use syntax::ast; | |
3157f602 | 52 | use syntax_pos::Span; |
9cc50fc6 | 53 | |
a7813a04 | 54 | pub fn assert_dep_graph<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>) { |
2c00a5a8 XL |
55 | tcx.dep_graph.with_ignore(|| { |
56 | if tcx.sess.opts.debugging_opts.dump_dep_graph { | |
57 | dump_graph(tcx); | |
58 | } | |
9cc50fc6 | 59 | |
2c00a5a8 XL |
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. | |
0531ce1d | 63 | if !tcx.features().rustc_attrs { |
2c00a5a8 XL |
64 | return; |
65 | } | |
5bcae85e | 66 | |
2c00a5a8 XL |
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![] }; | |
532ac7d7 | 72 | visitor.process_attrs(hir::CRATE_HIR_ID, &tcx.hir().krate().attrs); |
0731742a | 73 | tcx.hir().krate().visit_all_item_likes(&mut visitor.as_deep_visitor()); |
2c00a5a8 XL |
74 | (visitor.if_this_changed, visitor.then_this_would_need) |
75 | }; | |
9cc50fc6 | 76 | |
2c00a5a8 XL |
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 | } | |
54a0048b | 83 | |
2c00a5a8 XL |
84 | // Check paths. |
85 | check_paths(tcx, &if_this_changed, &then_this_would_need); | |
86 | }) | |
9cc50fc6 SL |
87 | } |
88 | ||
041b39d2 | 89 | type Sources = Vec<(Span, DefId, DepNode)>; |
532ac7d7 | 90 | type Targets = Vec<(Span, ast::Name, hir::HirId, DepNode)>; |
9cc50fc6 SL |
91 | |
92 | struct IfThisChanged<'a, 'tcx:'a> { | |
a7813a04 | 93 | tcx: TyCtxt<'a, 'tcx, 'tcx>, |
9e0c209e SL |
94 | if_this_changed: Sources, |
95 | then_this_would_need: Targets, | |
9cc50fc6 SL |
96 | } |
97 | ||
98 | impl<'a, 'tcx> IfThisChanged<'a, 'tcx> { | |
476ff2be | 99 | fn argument(&self, attr: &ast::Attribute) -> Option<ast::Name> { |
9e0c209e SL |
100 | let mut value = None; |
101 | for list_item in attr.meta_item_list().unwrap_or_default() { | |
9fa01778 XL |
102 | match list_item.ident() { |
103 | Some(ident) if list_item.is_word() && value.is_none() => | |
104 | value = Some(ident.name), | |
9e0c209e SL |
105 | _ => |
106 | // FIXME better-encapsulate meta_item (don't directly access `node`) | |
532ac7d7 | 107 | span_bug!(list_item.span(), "unexpected meta-item {:?}", list_item), |
9e0c209e SL |
108 | } |
109 | } | |
110 | value | |
111 | } | |
112 | ||
532ac7d7 XL |
113 | fn process_attrs(&mut self, hir_id: hir::HirId, attrs: &[ast::Attribute]) { |
114 | let def_id = self.tcx.hir().local_def_id_from_hir_id(hir_id); | |
041b39d2 | 115 | let def_path_hash = self.tcx.def_path_hash(def_id); |
9e0c209e SL |
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 { | |
041b39d2 | 120 | None => def_path_hash.to_dep_node(DepKind::Hir), |
476ff2be | 121 | Some(n) => { |
041b39d2 | 122 | match DepNode::from_label_string(&n.as_str(), def_path_hash) { |
9e0c209e SL |
123 | Ok(n) => n, |
124 | Err(()) => { | |
125 | self.tcx.sess.span_fatal( | |
126 | attr.span, | |
127 | &format!("unrecognized DepNode variant {:?}", n)); | |
128 | } | |
129 | } | |
9cc50fc6 | 130 | } |
9e0c209e SL |
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); | |
54a0048b | 135 | let dep_node = match dep_node_interned { |
476ff2be | 136 | Some(n) => { |
041b39d2 | 137 | match DepNode::from_label_string(&n.as_str(), def_path_hash) { |
54a0048b SL |
138 | Ok(n) => n, |
139 | Err(()) => { | |
140 | self.tcx.sess.span_fatal( | |
141 | attr.span, | |
142 | &format!("unrecognized DepNode variant {:?}", n)); | |
143 | } | |
9cc50fc6 SL |
144 | } |
145 | } | |
54a0048b | 146 | None => { |
9cc50fc6 SL |
147 | self.tcx.sess.span_fatal( |
148 | attr.span, | |
7cac9316 | 149 | "missing DepNode variant"); |
9cc50fc6 SL |
150 | } |
151 | }; | |
9e0c209e | 152 | self.then_this_would_need.push((attr.span, |
476ff2be | 153 | dep_node_interned.unwrap(), |
532ac7d7 | 154 | hir_id, |
9e0c209e | 155 | dep_node)); |
9cc50fc6 SL |
156 | } |
157 | } | |
158 | } | |
159 | } | |
160 | ||
7cac9316 XL |
161 | impl<'a, 'tcx> Visitor<'tcx> for IfThisChanged<'a, 'tcx> { |
162 | fn nested_visit_map<'this>(&'this mut self) -> NestedVisitorMap<'this, 'tcx> { | |
0731742a | 163 | NestedVisitorMap::OnlyBodies(&self.tcx.hir()) |
7cac9316 XL |
164 | } |
165 | ||
9cc50fc6 | 166 | fn visit_item(&mut self, item: &'tcx hir::Item) { |
532ac7d7 | 167 | self.process_attrs(item.hir_id, &item.attrs); |
7cac9316 | 168 | intravisit::walk_item(self, item); |
9cc50fc6 | 169 | } |
476ff2be | 170 | |
32a655c1 | 171 | fn visit_trait_item(&mut self, trait_item: &'tcx hir::TraitItem) { |
532ac7d7 | 172 | self.process_attrs(trait_item.hir_id, &trait_item.attrs); |
7cac9316 | 173 | intravisit::walk_trait_item(self, trait_item); |
32a655c1 SL |
174 | } |
175 | ||
476ff2be | 176 | fn visit_impl_item(&mut self, impl_item: &'tcx hir::ImplItem) { |
532ac7d7 | 177 | self.process_attrs(impl_item.hir_id, &impl_item.attrs); |
7cac9316 XL |
178 | intravisit::walk_impl_item(self, impl_item); |
179 | } | |
180 | ||
181 | fn visit_struct_field(&mut self, s: &'tcx hir::StructField) { | |
532ac7d7 | 182 | self.process_attrs(s.hir_id, &s.attrs); |
7cac9316 | 183 | intravisit::walk_struct_field(self, s); |
476ff2be | 184 | } |
9cc50fc6 SL |
185 | } |
186 | ||
a7813a04 | 187 | fn check_paths<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, |
9e0c209e SL |
188 | if_this_changed: &Sources, |
189 | then_this_would_need: &Targets) | |
9cc50fc6 SL |
190 | { |
191 | // Return early here so as not to construct the query, which is not cheap. | |
192 | if if_this_changed.is_empty() { | |
9e0c209e SL |
193 | for &(target_span, _, _, _) in then_this_would_need { |
194 | tcx.sess.span_err( | |
195 | target_span, | |
7cac9316 | 196 | "no #[rustc_if_this_changed] annotation detected"); |
9e0c209e SL |
197 | |
198 | } | |
9cc50fc6 SL |
199 | return; |
200 | } | |
201 | let query = tcx.dep_graph.query(); | |
9e0c209e | 202 | for &(_, source_def_id, ref source_dep_node) in if_this_changed { |
ea8adc8c | 203 | let dependents = query.transitive_predecessors(source_dep_node); |
9e0c209e SL |
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 `{}`", | |
532ac7d7 | 209 | tcx.def_path_str(source_def_id), |
9e0c209e SL |
210 | target_pass)); |
211 | } else { | |
212 | tcx.sess.span_err( | |
213 | target_span, | |
7cac9316 | 214 | "OK"); |
9cc50fc6 SL |
215 | } |
216 | } | |
217 | } | |
218 | } | |
219 | ||
9fa01778 | 220 | fn dump_graph(tcx: TyCtxt<'_, '_, '_>) { |
8faf50e0 | 221 | let path: String = env::var("RUST_DEP_GRAPH").unwrap_or_else(|_| "dep_graph".to_string()); |
9cc50fc6 SL |
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 ->". | |
a7813a04 XL |
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); | |
9cc50fc6 SL |
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(); | |
3157f602 | 245 | for &(ref source, ref target) in &edges { |
9cc50fc6 SL |
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(); | |
2c00a5a8 | 254 | fs::write(dot_path, v).unwrap(); |
9cc50fc6 SL |
255 | } |
256 | } | |
257 | ||
041b39d2 XL |
258 | pub struct GraphvizDepGraph<'q>(FxHashSet<&'q DepNode>, |
259 | Vec<(&'q DepNode, &'q DepNode)>); | |
9cc50fc6 | 260 | |
3157f602 | 261 | impl<'a, 'tcx, 'q> dot::GraphWalk<'a> for GraphvizDepGraph<'q> { |
041b39d2 XL |
262 | type Node = &'q DepNode; |
263 | type Edge = (&'q DepNode, &'q DepNode); | |
9fa01778 | 264 | fn nodes(&self) -> dot::Nodes<'_, &'q DepNode> { |
9cc50fc6 | 265 | let nodes: Vec<_> = self.0.iter().cloned().collect(); |
0bf4aa26 | 266 | nodes.into() |
9cc50fc6 | 267 | } |
9fa01778 | 268 | fn edges(&self) -> dot::Edges<'_, (&'q DepNode, &'q DepNode)> { |
0bf4aa26 | 269 | self.1[..].into() |
9cc50fc6 | 270 | } |
041b39d2 | 271 | fn source(&self, edge: &(&'q DepNode, &'q DepNode)) -> &'q DepNode { |
9cc50fc6 SL |
272 | edge.0 |
273 | } | |
041b39d2 | 274 | fn target(&self, edge: &(&'q DepNode, &'q DepNode)) -> &'q DepNode { |
9cc50fc6 SL |
275 | edge.1 |
276 | } | |
277 | } | |
278 | ||
3157f602 | 279 | impl<'a, 'tcx, 'q> dot::Labeller<'a> for GraphvizDepGraph<'q> { |
041b39d2 XL |
280 | type Node = &'q DepNode; |
281 | type Edge = (&'q DepNode, &'q DepNode); | |
9fa01778 | 282 | fn graph_id(&self) -> dot::Id<'_> { |
9cc50fc6 SL |
283 | dot::Id::new("DependencyGraph").unwrap() |
284 | } | |
9fa01778 | 285 | fn node_id(&self, n: &&'q DepNode) -> dot::Id<'_> { |
9cc50fc6 SL |
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 | } | |
9fa01778 | 293 | fn node_label(&self, n: &&'q DepNode) -> dot::LabelText<'_> { |
9cc50fc6 SL |
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. | |
041b39d2 XL |
301 | fn node_set<'q>(query: &'q DepGraphQuery, filter: &DepNodeFilter) |
302 | -> Option<FxHashSet<&'q DepNode>> | |
54a0048b | 303 | { |
9cc50fc6 SL |
304 | debug!("node_set(filter={:?})", filter); |
305 | ||
a7813a04 | 306 | if filter.accepts_all() { |
9cc50fc6 SL |
307 | return None; |
308 | } | |
309 | ||
a7813a04 | 310 | Some(query.nodes().into_iter().filter(|n| filter.test(n)).collect()) |
9cc50fc6 SL |
311 | } |
312 | ||
041b39d2 XL |
313 | fn filter_nodes<'q>(query: &'q DepGraphQuery, |
314 | sources: &Option<FxHashSet<&'q DepNode>>, | |
315 | targets: &Option<FxHashSet<&'q DepNode>>) | |
316 | -> FxHashSet<&'q DepNode> | |
9cc50fc6 SL |
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 | ||
041b39d2 XL |
331 | fn walk_nodes<'q>(query: &'q DepGraphQuery, |
332 | starts: &FxHashSet<&'q DepNode>, | |
3157f602 | 333 | direction: Direction) |
041b39d2 | 334 | -> FxHashSet<&'q DepNode> |
9cc50fc6 | 335 | { |
0bf4aa26 | 336 | let mut set = FxHashSet::default(); |
3157f602 | 337 | for &start in starts { |
9cc50fc6 | 338 | debug!("walk_nodes: start={:?} outgoing?={:?}", start, direction == OUTGOING); |
3157f602 | 339 | if set.insert(start) { |
9cc50fc6 SL |
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); | |
3157f602 | 345 | if set.insert(neighbor) { |
9cc50fc6 SL |
346 | stack.push(neighbor_index); |
347 | } | |
348 | } | |
349 | } | |
350 | } | |
351 | } | |
352 | set | |
353 | } | |
354 | ||
041b39d2 XL |
355 | fn walk_between<'q>(query: &'q DepGraphQuery, |
356 | sources: &FxHashSet<&'q DepNode>, | |
357 | targets: &FxHashSet<&'q DepNode>) | |
358 | -> FxHashSet<&'q DepNode> | |
9cc50fc6 SL |
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 { | |
3157f602 | 371 | node_states[query.indices[target].0] = State::Included; |
9cc50fc6 SL |
372 | } |
373 | ||
3157f602 | 374 | for source in sources.iter().map(|&n| query.indices[n]) { |
9cc50fc6 SL |
375 | recurse(query, &mut node_states, source); |
376 | } | |
377 | ||
378 | return query.nodes() | |
379 | .into_iter() | |
3157f602 | 380 | .filter(|&n| { |
9cc50fc6 SL |
381 | let index = query.indices[n]; |
382 | node_states[index.0] == State::Included | |
383 | }) | |
384 | .collect(); | |
385 | ||
041b39d2 | 386 | fn recurse(query: &DepGraphQuery, |
9cc50fc6 SL |
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 | ||
041b39d2 XL |
423 | fn filter_edges<'q>(query: &'q DepGraphQuery, |
424 | nodes: &FxHashSet<&'q DepNode>) | |
425 | -> Vec<(&'q DepNode, &'q DepNode)> | |
9cc50fc6 SL |
426 | { |
427 | query.edges() | |
428 | .into_iter() | |
3157f602 | 429 | .filter(|&(source, target)| nodes.contains(source) && nodes.contains(target)) |
9cc50fc6 SL |
430 | .collect() |
431 | } |