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