]>
Commit | Line | Data |
---|---|---|
9cc50fc6 SL |
1 | // Copyright 2012-2015 The Rust Project Developers. See the COPYRIGHT |
2 | // file at the top-level directory of this distribution and at | |
3 | // http://rust-lang.org/COPYRIGHT. | |
4 | // | |
5 | // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or | |
6 | // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license | |
7 | // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your | |
8 | // option. This file may not be copied, modified, or distributed | |
9 | // except according to those terms. | |
10 | ||
11 | //! This pass is only used for the UNIT TESTS and DEBUGGING NEEDS | |
12 | //! around dependency graph construction. It serves two purposes; it | |
13 | //! will dump graphs in graphviz form to disk, and it searches for | |
14 | //! `#[rustc_if_this_changed]` and `#[rustc_then_this_would_need]` | |
15 | //! annotations. These annotations can be used to test whether paths | |
54a0048b SL |
16 | //! exist in the graph. These checks run after trans, so they view the |
17 | //! the final state of the dependency graph. Note that there are | |
18 | //! similar assertions found in `persist::dirty_clean` which check the | |
19 | //! **initial** state of the dependency graph, just after it has been | |
20 | //! loaded from disk. | |
21 | //! | |
22 | //! In this code, we report errors on each `rustc_if_this_changed` | |
23 | //! annotation. If a path exists in all cases, then we would report | |
24 | //! "all path(s) exist". Otherwise, we report: "no path to `foo`" for | |
25 | //! each case where no path exists. `compile-fail` tests can then be | |
26 | //! used to check when paths exist or do not. | |
9cc50fc6 SL |
27 | //! |
28 | //! The full form of the `rustc_if_this_changed` annotation is | |
9e0c209e SL |
29 | //! `#[rustc_if_this_changed("foo")]`, which will report a |
30 | //! source node of `foo(def_id)`. The `"foo"` is optional and | |
31 | //! defaults to `"Hir"` if omitted. | |
9cc50fc6 SL |
32 | //! |
33 | //! Example: | |
34 | //! | |
35 | //! ``` | |
9e0c209e | 36 | //! #[rustc_if_this_changed(Hir)] |
9cc50fc6 SL |
37 | //! fn foo() { } |
38 | //! | |
9e0c209e | 39 | //! #[rustc_then_this_would_need(trans)] //~ ERROR no path from `foo` |
9cc50fc6 SL |
40 | //! fn bar() { } |
41 | //! | |
9e0c209e | 42 | //! #[rustc_then_this_would_need(trans)] //~ ERROR OK |
9cc50fc6 SL |
43 | //! fn baz() { foo(); } |
44 | //! ``` | |
45 | ||
46 | use graphviz as dot; | |
041b39d2 | 47 | use rustc::dep_graph::{DepGraphQuery, DepNode, DepKind}; |
a7813a04 | 48 | use rustc::dep_graph::debug::{DepNodeFilter, EdgeFilter}; |
54a0048b SL |
49 | use rustc::hir::def_id::DefId; |
50 | use rustc::ty::TyCtxt; | |
476ff2be | 51 | use rustc_data_structures::fx::FxHashSet; |
9cc50fc6 | 52 | use rustc_data_structures::graph::{Direction, INCOMING, OUTGOING, NodeIndex}; |
54a0048b | 53 | use rustc::hir; |
7cac9316 | 54 | use rustc::hir::intravisit::{self, NestedVisitorMap, Visitor}; |
cc61c64b | 55 | use rustc::ich::{ATTR_IF_THIS_CHANGED, ATTR_THEN_THIS_WOULD_NEED}; |
9cc50fc6 SL |
56 | use graphviz::IntoCow; |
57 | use std::env; | |
58 | use std::fs::File; | |
59 | use std::io::Write; | |
60 | use syntax::ast; | |
3157f602 | 61 | use syntax_pos::Span; |
9cc50fc6 | 62 | |
a7813a04 | 63 | pub fn assert_dep_graph<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>) { |
9cc50fc6 SL |
64 | let _ignore = tcx.dep_graph.in_ignore(); |
65 | ||
54a0048b | 66 | if tcx.sess.opts.debugging_opts.dump_dep_graph { |
9cc50fc6 SL |
67 | dump_graph(tcx); |
68 | } | |
69 | ||
5bcae85e SL |
70 | // if the `rustc_attrs` feature is not enabled, then the |
71 | // attributes we are interested in cannot be present anyway, so | |
72 | // skip the walk. | |
73 | if !tcx.sess.features.borrow().rustc_attrs { | |
74 | return; | |
75 | } | |
76 | ||
9cc50fc6 SL |
77 | // Find annotations supplied by user (if any). |
78 | let (if_this_changed, then_this_would_need) = { | |
3b2f2976 | 79 | let mut visitor = IfThisChanged { tcx, |
9e0c209e SL |
80 | if_this_changed: vec![], |
81 | then_this_would_need: vec![] }; | |
32a655c1 | 82 | visitor.process_attrs(ast::CRATE_NODE_ID, &tcx.hir.krate().attrs); |
7cac9316 | 83 | tcx.hir.krate().visit_all_item_likes(&mut visitor.as_deep_visitor()); |
9cc50fc6 SL |
84 | (visitor.if_this_changed, visitor.then_this_would_need) |
85 | }; | |
86 | ||
54a0048b SL |
87 | if !if_this_changed.is_empty() || !then_this_would_need.is_empty() { |
88 | assert!(tcx.sess.opts.debugging_opts.query_dep_graph, | |
89 | "cannot use the `#[{}]` or `#[{}]` annotations \ | |
90 | without supplying `-Z query-dep-graph`", | |
9e0c209e | 91 | ATTR_IF_THIS_CHANGED, ATTR_THEN_THIS_WOULD_NEED); |
54a0048b SL |
92 | } |
93 | ||
9cc50fc6 SL |
94 | // Check paths. |
95 | check_paths(tcx, &if_this_changed, &then_this_would_need); | |
96 | } | |
97 | ||
041b39d2 XL |
98 | type Sources = Vec<(Span, DefId, DepNode)>; |
99 | type Targets = Vec<(Span, ast::Name, ast::NodeId, DepNode)>; | |
9cc50fc6 SL |
100 | |
101 | struct IfThisChanged<'a, 'tcx:'a> { | |
a7813a04 | 102 | tcx: TyCtxt<'a, 'tcx, 'tcx>, |
9e0c209e SL |
103 | if_this_changed: Sources, |
104 | then_this_would_need: Targets, | |
9cc50fc6 SL |
105 | } |
106 | ||
107 | impl<'a, 'tcx> IfThisChanged<'a, 'tcx> { | |
476ff2be | 108 | fn argument(&self, attr: &ast::Attribute) -> Option<ast::Name> { |
9e0c209e SL |
109 | let mut value = None; |
110 | for list_item in attr.meta_item_list().unwrap_or_default() { | |
111 | match list_item.word() { | |
112 | Some(word) if value.is_none() => | |
113 | value = Some(word.name().clone()), | |
114 | _ => | |
115 | // FIXME better-encapsulate meta_item (don't directly access `node`) | |
116 | span_bug!(list_item.span(), "unexpected meta-item {:?}", list_item.node), | |
117 | } | |
118 | } | |
119 | value | |
120 | } | |
121 | ||
122 | fn process_attrs(&mut self, node_id: ast::NodeId, attrs: &[ast::Attribute]) { | |
32a655c1 | 123 | let def_id = self.tcx.hir.local_def_id(node_id); |
041b39d2 | 124 | let def_path_hash = self.tcx.def_path_hash(def_id); |
9e0c209e SL |
125 | for attr in attrs { |
126 | if attr.check_name(ATTR_IF_THIS_CHANGED) { | |
127 | let dep_node_interned = self.argument(attr); | |
128 | let dep_node = match dep_node_interned { | |
041b39d2 | 129 | None => def_path_hash.to_dep_node(DepKind::Hir), |
476ff2be | 130 | Some(n) => { |
041b39d2 | 131 | match DepNode::from_label_string(&n.as_str(), def_path_hash) { |
9e0c209e SL |
132 | Ok(n) => n, |
133 | Err(()) => { | |
134 | self.tcx.sess.span_fatal( | |
135 | attr.span, | |
136 | &format!("unrecognized DepNode variant {:?}", n)); | |
137 | } | |
138 | } | |
9cc50fc6 | 139 | } |
9e0c209e SL |
140 | }; |
141 | self.if_this_changed.push((attr.span, def_id, dep_node)); | |
142 | } else if attr.check_name(ATTR_THEN_THIS_WOULD_NEED) { | |
143 | let dep_node_interned = self.argument(attr); | |
54a0048b | 144 | let dep_node = match dep_node_interned { |
476ff2be | 145 | Some(n) => { |
041b39d2 | 146 | match DepNode::from_label_string(&n.as_str(), def_path_hash) { |
54a0048b SL |
147 | Ok(n) => n, |
148 | Err(()) => { | |
149 | self.tcx.sess.span_fatal( | |
150 | attr.span, | |
151 | &format!("unrecognized DepNode variant {:?}", n)); | |
152 | } | |
9cc50fc6 SL |
153 | } |
154 | } | |
54a0048b | 155 | None => { |
9cc50fc6 SL |
156 | self.tcx.sess.span_fatal( |
157 | attr.span, | |
7cac9316 | 158 | "missing DepNode variant"); |
9cc50fc6 SL |
159 | } |
160 | }; | |
9e0c209e | 161 | self.then_this_would_need.push((attr.span, |
476ff2be | 162 | dep_node_interned.unwrap(), |
9e0c209e SL |
163 | node_id, |
164 | dep_node)); | |
9cc50fc6 SL |
165 | } |
166 | } | |
167 | } | |
168 | } | |
169 | ||
7cac9316 XL |
170 | impl<'a, 'tcx> Visitor<'tcx> for IfThisChanged<'a, 'tcx> { |
171 | fn nested_visit_map<'this>(&'this mut self) -> NestedVisitorMap<'this, 'tcx> { | |
172 | NestedVisitorMap::OnlyBodies(&self.tcx.hir) | |
173 | } | |
174 | ||
9cc50fc6 | 175 | fn visit_item(&mut self, item: &'tcx hir::Item) { |
9e0c209e | 176 | self.process_attrs(item.id, &item.attrs); |
7cac9316 | 177 | intravisit::walk_item(self, item); |
9cc50fc6 | 178 | } |
476ff2be | 179 | |
32a655c1 SL |
180 | fn visit_trait_item(&mut self, trait_item: &'tcx hir::TraitItem) { |
181 | self.process_attrs(trait_item.id, &trait_item.attrs); | |
7cac9316 | 182 | intravisit::walk_trait_item(self, trait_item); |
32a655c1 SL |
183 | } |
184 | ||
476ff2be SL |
185 | fn visit_impl_item(&mut self, impl_item: &'tcx hir::ImplItem) { |
186 | self.process_attrs(impl_item.id, &impl_item.attrs); | |
7cac9316 XL |
187 | intravisit::walk_impl_item(self, impl_item); |
188 | } | |
189 | ||
190 | fn visit_struct_field(&mut self, s: &'tcx hir::StructField) { | |
191 | self.process_attrs(s.id, &s.attrs); | |
192 | intravisit::walk_struct_field(self, s); | |
476ff2be | 193 | } |
9cc50fc6 SL |
194 | } |
195 | ||
a7813a04 | 196 | fn check_paths<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, |
9e0c209e SL |
197 | if_this_changed: &Sources, |
198 | then_this_would_need: &Targets) | |
9cc50fc6 SL |
199 | { |
200 | // Return early here so as not to construct the query, which is not cheap. | |
201 | if if_this_changed.is_empty() { | |
9e0c209e SL |
202 | for &(target_span, _, _, _) in then_this_would_need { |
203 | tcx.sess.span_err( | |
204 | target_span, | |
7cac9316 | 205 | "no #[rustc_if_this_changed] annotation detected"); |
9e0c209e SL |
206 | |
207 | } | |
9cc50fc6 SL |
208 | return; |
209 | } | |
210 | let query = tcx.dep_graph.query(); | |
9e0c209e | 211 | for &(_, source_def_id, ref source_dep_node) in if_this_changed { |
ea8adc8c | 212 | let dependents = query.transitive_predecessors(source_dep_node); |
9e0c209e SL |
213 | for &(target_span, ref target_pass, _, ref target_dep_node) in then_this_would_need { |
214 | if !dependents.contains(&target_dep_node) { | |
215 | tcx.sess.span_err( | |
216 | target_span, | |
217 | &format!("no path from `{}` to `{}`", | |
218 | tcx.item_path_str(source_def_id), | |
219 | target_pass)); | |
220 | } else { | |
221 | tcx.sess.span_err( | |
222 | target_span, | |
7cac9316 | 223 | "OK"); |
9cc50fc6 SL |
224 | } |
225 | } | |
226 | } | |
227 | } | |
228 | ||
a7813a04 | 229 | fn dump_graph(tcx: TyCtxt) { |
9cc50fc6 SL |
230 | let path: String = env::var("RUST_DEP_GRAPH").unwrap_or_else(|_| format!("dep_graph")); |
231 | let query = tcx.dep_graph.query(); | |
232 | ||
233 | let nodes = match env::var("RUST_DEP_GRAPH_FILTER") { | |
234 | Ok(string) => { | |
235 | // Expect one of: "-> target", "source -> target", or "source ->". | |
a7813a04 XL |
236 | let edge_filter = EdgeFilter::new(&string).unwrap_or_else(|e| { |
237 | bug!("invalid filter: {}", e) | |
238 | }); | |
239 | let sources = node_set(&query, &edge_filter.source); | |
240 | let targets = node_set(&query, &edge_filter.target); | |
9cc50fc6 SL |
241 | filter_nodes(&query, &sources, &targets) |
242 | } | |
243 | Err(_) => { | |
244 | query.nodes() | |
245 | .into_iter() | |
246 | .collect() | |
247 | } | |
248 | }; | |
249 | let edges = filter_edges(&query, &nodes); | |
250 | ||
251 | { // dump a .txt file with just the edges: | |
252 | let txt_path = format!("{}.txt", path); | |
253 | let mut file = File::create(&txt_path).unwrap(); | |
3157f602 | 254 | for &(ref source, ref target) in &edges { |
9cc50fc6 SL |
255 | write!(file, "{:?} -> {:?}\n", source, target).unwrap(); |
256 | } | |
257 | } | |
258 | ||
259 | { // dump a .dot file in graphviz format: | |
260 | let dot_path = format!("{}.dot", path); | |
261 | let mut v = Vec::new(); | |
262 | dot::render(&GraphvizDepGraph(nodes, edges), &mut v).unwrap(); | |
263 | File::create(&dot_path).and_then(|mut f| f.write_all(&v)).unwrap(); | |
264 | } | |
265 | } | |
266 | ||
041b39d2 XL |
267 | pub struct GraphvizDepGraph<'q>(FxHashSet<&'q DepNode>, |
268 | Vec<(&'q DepNode, &'q DepNode)>); | |
9cc50fc6 | 269 | |
3157f602 | 270 | impl<'a, 'tcx, 'q> dot::GraphWalk<'a> for GraphvizDepGraph<'q> { |
041b39d2 XL |
271 | type Node = &'q DepNode; |
272 | type Edge = (&'q DepNode, &'q DepNode); | |
273 | fn nodes(&self) -> dot::Nodes<&'q DepNode> { | |
9cc50fc6 SL |
274 | let nodes: Vec<_> = self.0.iter().cloned().collect(); |
275 | nodes.into_cow() | |
276 | } | |
041b39d2 | 277 | fn edges(&self) -> dot::Edges<(&'q DepNode, &'q DepNode)> { |
9cc50fc6 SL |
278 | self.1[..].into_cow() |
279 | } | |
041b39d2 | 280 | fn source(&self, edge: &(&'q DepNode, &'q DepNode)) -> &'q DepNode { |
9cc50fc6 SL |
281 | edge.0 |
282 | } | |
041b39d2 | 283 | fn target(&self, edge: &(&'q DepNode, &'q DepNode)) -> &'q DepNode { |
9cc50fc6 SL |
284 | edge.1 |
285 | } | |
286 | } | |
287 | ||
3157f602 | 288 | impl<'a, 'tcx, 'q> dot::Labeller<'a> for GraphvizDepGraph<'q> { |
041b39d2 XL |
289 | type Node = &'q DepNode; |
290 | type Edge = (&'q DepNode, &'q DepNode); | |
9cc50fc6 SL |
291 | fn graph_id(&self) -> dot::Id { |
292 | dot::Id::new("DependencyGraph").unwrap() | |
293 | } | |
041b39d2 | 294 | fn node_id(&self, n: &&'q DepNode) -> dot::Id { |
9cc50fc6 SL |
295 | let s: String = |
296 | format!("{:?}", n).chars() | |
297 | .map(|c| if c == '_' || c.is_alphanumeric() { c } else { '_' }) | |
298 | .collect(); | |
299 | debug!("n={:?} s={:?}", n, s); | |
300 | dot::Id::new(s).unwrap() | |
301 | } | |
041b39d2 | 302 | fn node_label(&self, n: &&'q DepNode) -> dot::LabelText { |
9cc50fc6 SL |
303 | dot::LabelText::label(format!("{:?}", n)) |
304 | } | |
305 | } | |
306 | ||
307 | // Given an optional filter like `"x,y,z"`, returns either `None` (no | |
308 | // filter) or the set of nodes whose labels contain all of those | |
309 | // substrings. | |
041b39d2 XL |
310 | fn node_set<'q>(query: &'q DepGraphQuery, filter: &DepNodeFilter) |
311 | -> Option<FxHashSet<&'q DepNode>> | |
54a0048b | 312 | { |
9cc50fc6 SL |
313 | debug!("node_set(filter={:?})", filter); |
314 | ||
a7813a04 | 315 | if filter.accepts_all() { |
9cc50fc6 SL |
316 | return None; |
317 | } | |
318 | ||
a7813a04 | 319 | Some(query.nodes().into_iter().filter(|n| filter.test(n)).collect()) |
9cc50fc6 SL |
320 | } |
321 | ||
041b39d2 XL |
322 | fn filter_nodes<'q>(query: &'q DepGraphQuery, |
323 | sources: &Option<FxHashSet<&'q DepNode>>, | |
324 | targets: &Option<FxHashSet<&'q DepNode>>) | |
325 | -> FxHashSet<&'q DepNode> | |
9cc50fc6 SL |
326 | { |
327 | if let &Some(ref sources) = sources { | |
328 | if let &Some(ref targets) = targets { | |
329 | walk_between(query, sources, targets) | |
330 | } else { | |
331 | walk_nodes(query, sources, OUTGOING) | |
332 | } | |
333 | } else if let &Some(ref targets) = targets { | |
334 | walk_nodes(query, targets, INCOMING) | |
335 | } else { | |
336 | query.nodes().into_iter().collect() | |
337 | } | |
338 | } | |
339 | ||
041b39d2 XL |
340 | fn walk_nodes<'q>(query: &'q DepGraphQuery, |
341 | starts: &FxHashSet<&'q DepNode>, | |
3157f602 | 342 | direction: Direction) |
041b39d2 | 343 | -> FxHashSet<&'q DepNode> |
9cc50fc6 | 344 | { |
476ff2be | 345 | let mut set = FxHashSet(); |
3157f602 | 346 | for &start in starts { |
9cc50fc6 | 347 | debug!("walk_nodes: start={:?} outgoing?={:?}", start, direction == OUTGOING); |
3157f602 | 348 | if set.insert(start) { |
9cc50fc6 SL |
349 | let mut stack = vec![query.indices[start]]; |
350 | while let Some(index) = stack.pop() { | |
351 | for (_, edge) in query.graph.adjacent_edges(index, direction) { | |
352 | let neighbor_index = edge.source_or_target(direction); | |
353 | let neighbor = query.graph.node_data(neighbor_index); | |
3157f602 | 354 | if set.insert(neighbor) { |
9cc50fc6 SL |
355 | stack.push(neighbor_index); |
356 | } | |
357 | } | |
358 | } | |
359 | } | |
360 | } | |
361 | set | |
362 | } | |
363 | ||
041b39d2 XL |
364 | fn walk_between<'q>(query: &'q DepGraphQuery, |
365 | sources: &FxHashSet<&'q DepNode>, | |
366 | targets: &FxHashSet<&'q DepNode>) | |
367 | -> FxHashSet<&'q DepNode> | |
9cc50fc6 SL |
368 | { |
369 | // This is a bit tricky. We want to include a node only if it is: | |
370 | // (a) reachable from a source and (b) will reach a target. And we | |
371 | // have to be careful about cycles etc. Luckily efficiency is not | |
372 | // a big concern! | |
373 | ||
374 | #[derive(Copy, Clone, PartialEq)] | |
375 | enum State { Undecided, Deciding, Included, Excluded } | |
376 | ||
377 | let mut node_states = vec![State::Undecided; query.graph.len_nodes()]; | |
378 | ||
379 | for &target in targets { | |
3157f602 | 380 | node_states[query.indices[target].0] = State::Included; |
9cc50fc6 SL |
381 | } |
382 | ||
3157f602 | 383 | for source in sources.iter().map(|&n| query.indices[n]) { |
9cc50fc6 SL |
384 | recurse(query, &mut node_states, source); |
385 | } | |
386 | ||
387 | return query.nodes() | |
388 | .into_iter() | |
3157f602 | 389 | .filter(|&n| { |
9cc50fc6 SL |
390 | let index = query.indices[n]; |
391 | node_states[index.0] == State::Included | |
392 | }) | |
393 | .collect(); | |
394 | ||
041b39d2 | 395 | fn recurse(query: &DepGraphQuery, |
9cc50fc6 SL |
396 | node_states: &mut [State], |
397 | node: NodeIndex) | |
398 | -> bool | |
399 | { | |
400 | match node_states[node.0] { | |
401 | // known to reach a target | |
402 | State::Included => return true, | |
403 | ||
404 | // known not to reach a target | |
405 | State::Excluded => return false, | |
406 | ||
407 | // backedge, not yet known, say false | |
408 | State::Deciding => return false, | |
409 | ||
410 | State::Undecided => { } | |
411 | } | |
412 | ||
413 | node_states[node.0] = State::Deciding; | |
414 | ||
415 | for neighbor_index in query.graph.successor_nodes(node) { | |
416 | if recurse(query, node_states, neighbor_index) { | |
417 | node_states[node.0] = State::Included; | |
418 | } | |
419 | } | |
420 | ||
421 | // if we didn't find a path to target, then set to excluded | |
422 | if node_states[node.0] == State::Deciding { | |
423 | node_states[node.0] = State::Excluded; | |
424 | false | |
425 | } else { | |
426 | assert!(node_states[node.0] == State::Included); | |
427 | true | |
428 | } | |
429 | } | |
430 | } | |
431 | ||
041b39d2 XL |
432 | fn filter_edges<'q>(query: &'q DepGraphQuery, |
433 | nodes: &FxHashSet<&'q DepNode>) | |
434 | -> Vec<(&'q DepNode, &'q DepNode)> | |
9cc50fc6 SL |
435 | { |
436 | query.edges() | |
437 | .into_iter() | |
3157f602 | 438 | .filter(|&(source, target)| nodes.contains(source) && nodes.contains(target)) |
9cc50fc6 SL |
439 | .collect() |
440 | } |