]> git.proxmox.com Git - rustc.git/blob - src/librustc_trans/trans/assert_dep_graph.rs
Imported Upstream version 1.8.0+dfsg1
[rustc.git] / src / librustc_trans / trans / assert_dep_graph.rs
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
16 //! exist in the graph. We report errors on each
17 //! `rustc_if_this_changed` annotation. If a path exists in all
18 //! cases, then we would report "all path(s) exist". Otherwise, we
19 //! report: "no path to `foo`" for each case where no path exists.
20 //! `compile-fail` tests can then be used to check when paths exist or
21 //! do not.
22 //!
23 //! The full form of the `rustc_if_this_changed` annotation is
24 //! `#[rustc_if_this_changed(id)]`. The `"id"` is optional and
25 //! defaults to `"id"` if omitted.
26 //!
27 //! Example:
28 //!
29 //! ```
30 //! #[rustc_if_this_changed]
31 //! fn foo() { }
32 //!
33 //! #[rustc_then_this_would_need("trans")] //~ ERROR no path from `foo`
34 //! fn bar() { }
35 //!
36 //! #[rustc_then_this_would_need("trans")] //~ ERROR OK
37 //! fn baz() { foo(); }
38 //! ```
39
40 use graphviz as dot;
41 use rustc::dep_graph::{DepGraphQuery, DepNode};
42 use rustc::middle::def_id::DefId;
43 use rustc::middle::ty;
44 use rustc_data_structures::fnv::{FnvHashMap, FnvHashSet};
45 use rustc_data_structures::graph::{Direction, INCOMING, OUTGOING, NodeIndex};
46 use rustc_front::hir;
47 use rustc_front::intravisit::Visitor;
48 use graphviz::IntoCow;
49 use std::env;
50 use std::fs::File;
51 use std::io::Write;
52 use syntax::ast;
53 use syntax::attr::AttrMetaMethods;
54 use syntax::codemap::Span;
55 use syntax::parse::token::InternedString;
56
57 const IF_THIS_CHANGED: &'static str = "rustc_if_this_changed";
58 const THEN_THIS_WOULD_NEED: &'static str = "rustc_then_this_would_need";
59 const ID: &'static str = "id";
60
61 pub fn assert_dep_graph(tcx: &ty::ctxt) {
62 let _ignore = tcx.dep_graph.in_ignore();
63
64 if tcx.sess.opts.dump_dep_graph {
65 dump_graph(tcx);
66 }
67
68 // Find annotations supplied by user (if any).
69 let (if_this_changed, then_this_would_need) = {
70 let mut visitor = IfThisChanged { tcx: tcx,
71 if_this_changed: FnvHashMap(),
72 then_this_would_need: FnvHashMap() };
73 tcx.map.krate().visit_all_items(&mut visitor);
74 (visitor.if_this_changed, visitor.then_this_would_need)
75 };
76
77 // Check paths.
78 check_paths(tcx, &if_this_changed, &then_this_would_need);
79 }
80
81 type SourceHashMap = FnvHashMap<InternedString,
82 FnvHashSet<(Span, DefId, DepNode)>>;
83 type TargetHashMap = FnvHashMap<InternedString,
84 FnvHashSet<(Span, InternedString, ast::NodeId, DepNode)>>;
85
86 struct IfThisChanged<'a, 'tcx:'a> {
87 tcx: &'a ty::ctxt<'tcx>,
88 if_this_changed: SourceHashMap,
89 then_this_would_need: TargetHashMap,
90 }
91
92 impl<'a, 'tcx> IfThisChanged<'a, 'tcx> {
93 fn process_attrs(&mut self, node_id: ast::NodeId, def_id: DefId) {
94 for attr in self.tcx.get_attrs(def_id).iter() {
95 if attr.check_name(IF_THIS_CHANGED) {
96 let mut id = None;
97 for meta_item in attr.meta_item_list().unwrap_or_default() {
98 match meta_item.node {
99 ast::MetaItemKind::Word(ref s) if id.is_none() => id = Some(s.clone()),
100 _ => {
101 self.tcx.sess.span_err(
102 meta_item.span,
103 &format!("unexpected meta-item {:?}", meta_item.node));
104 }
105 }
106 }
107 let id = id.unwrap_or(InternedString::new(ID));
108 self.if_this_changed.entry(id)
109 .or_insert(FnvHashSet())
110 .insert((attr.span, def_id, DepNode::Hir(def_id)));
111 } else if attr.check_name(THEN_THIS_WOULD_NEED) {
112 let mut dep_node_interned = None;
113 let mut id = None;
114 for meta_item in attr.meta_item_list().unwrap_or_default() {
115 match meta_item.node {
116 ast::MetaItemKind::Word(ref s) if dep_node_interned.is_none() =>
117 dep_node_interned = Some(s.clone()),
118 ast::MetaItemKind::Word(ref s) if id.is_none() =>
119 id = Some(s.clone()),
120 _ => {
121 self.tcx.sess.span_err(
122 meta_item.span,
123 &format!("unexpected meta-item {:?}", meta_item.node));
124 }
125 }
126 }
127 let dep_node_str = dep_node_interned.as_ref().map(|s| &**s);
128 macro_rules! match_depnode_name {
129 ($input:expr, $def_id:expr, match { $($variant:ident,)* } else $y:expr) => {
130 match $input {
131 $(Some(stringify!($variant)) => DepNode::$variant($def_id),)*
132 _ => $y
133 }
134 }
135 }
136 let dep_node = match_depnode_name! {
137 dep_node_str, def_id, match {
138 CollectItem,
139 BorrowCheck,
140 TransCrateItem,
141 TypeckItemType,
142 TypeckItemBody,
143 ImplOrTraitItems,
144 ItemSignature,
145 FieldTy,
146 TraitItemDefIds,
147 InherentImpls,
148 ImplItems,
149 TraitImpls,
150 ReprHints,
151 } else {
152 self.tcx.sess.span_fatal(
153 attr.span,
154 &format!("unrecognized DepNode variant {:?}", dep_node_str));
155 }
156 };
157 let id = id.unwrap_or(InternedString::new(ID));
158 self.then_this_would_need
159 .entry(id)
160 .or_insert(FnvHashSet())
161 .insert((attr.span, dep_node_interned.clone().unwrap(), node_id, dep_node));
162 }
163 }
164 }
165 }
166
167 impl<'a, 'tcx> Visitor<'tcx> for IfThisChanged<'a, 'tcx> {
168 fn visit_item(&mut self, item: &'tcx hir::Item) {
169 let def_id = self.tcx.map.local_def_id(item.id);
170 self.process_attrs(item.id, def_id);
171 }
172 }
173
174 fn check_paths(tcx: &ty::ctxt,
175 if_this_changed: &SourceHashMap,
176 then_this_would_need: &TargetHashMap)
177 {
178 // Return early here so as not to construct the query, which is not cheap.
179 if if_this_changed.is_empty() {
180 return;
181 }
182 let query = tcx.dep_graph.query();
183 for (id, sources) in if_this_changed {
184 let targets = match then_this_would_need.get(id) {
185 Some(targets) => targets,
186 None => {
187 for &(source_span, _, _) in sources.iter().take(1) {
188 tcx.sess.span_err(
189 source_span,
190 &format!("no targets for id `{}`", id));
191 }
192 continue;
193 }
194 };
195
196 for &(_, source_def_id, source_dep_node) in sources {
197 let dependents = query.dependents(source_dep_node);
198 for &(target_span, ref target_pass, _, ref target_dep_node) in targets {
199 if !dependents.contains(&target_dep_node) {
200 tcx.sess.span_err(
201 target_span,
202 &format!("no path from `{}` to `{}`",
203 tcx.item_path_str(source_def_id),
204 target_pass));
205 } else {
206 tcx.sess.span_err(
207 target_span,
208 &format!("OK"));
209 }
210 }
211 }
212 }
213 }
214
215 fn dump_graph(tcx: &ty::ctxt) {
216 let path: String = env::var("RUST_DEP_GRAPH").unwrap_or_else(|_| format!("dep_graph"));
217 let query = tcx.dep_graph.query();
218
219 let nodes = match env::var("RUST_DEP_GRAPH_FILTER") {
220 Ok(string) => {
221 // Expect one of: "-> target", "source -> target", or "source ->".
222 let parts: Vec<_> = string.split("->").collect();
223 if parts.len() > 2 {
224 panic!("Invalid RUST_DEP_GRAPH_FILTER: expected '[source] -> [target]'");
225 }
226 let sources = node_set(&query, &parts[0]);
227 let targets = node_set(&query, &parts[1]);
228 filter_nodes(&query, &sources, &targets)
229 }
230 Err(_) => {
231 query.nodes()
232 .into_iter()
233 .collect()
234 }
235 };
236 let edges = filter_edges(&query, &nodes);
237
238 { // dump a .txt file with just the edges:
239 let txt_path = format!("{}.txt", path);
240 let mut file = File::create(&txt_path).unwrap();
241 for &(source, target) in &edges {
242 write!(file, "{:?} -> {:?}\n", source, target).unwrap();
243 }
244 }
245
246 { // dump a .dot file in graphviz format:
247 let dot_path = format!("{}.dot", path);
248 let mut v = Vec::new();
249 dot::render(&GraphvizDepGraph(nodes, edges), &mut v).unwrap();
250 File::create(&dot_path).and_then(|mut f| f.write_all(&v)).unwrap();
251 }
252 }
253
254 pub struct GraphvizDepGraph(FnvHashSet<DepNode>, Vec<(DepNode, DepNode)>);
255
256 impl<'a, 'tcx> dot::GraphWalk<'a, DepNode, (DepNode, DepNode)> for GraphvizDepGraph {
257 fn nodes(&self) -> dot::Nodes<DepNode> {
258 let nodes: Vec<_> = self.0.iter().cloned().collect();
259 nodes.into_cow()
260 }
261 fn edges(&self) -> dot::Edges<(DepNode, DepNode)> {
262 self.1[..].into_cow()
263 }
264 fn source(&self, edge: &(DepNode, DepNode)) -> DepNode {
265 edge.0
266 }
267 fn target(&self, edge: &(DepNode, DepNode)) -> DepNode {
268 edge.1
269 }
270 }
271
272 impl<'a, 'tcx> dot::Labeller<'a, DepNode, (DepNode, DepNode)> for GraphvizDepGraph {
273 fn graph_id(&self) -> dot::Id {
274 dot::Id::new("DependencyGraph").unwrap()
275 }
276 fn node_id(&self, n: &DepNode) -> dot::Id {
277 let s: String =
278 format!("{:?}", n).chars()
279 .map(|c| if c == '_' || c.is_alphanumeric() { c } else { '_' })
280 .collect();
281 debug!("n={:?} s={:?}", n, s);
282 dot::Id::new(s).unwrap()
283 }
284 fn node_label(&self, n: &DepNode) -> dot::LabelText {
285 dot::LabelText::label(format!("{:?}", n))
286 }
287 }
288
289 // Given an optional filter like `"x,y,z"`, returns either `None` (no
290 // filter) or the set of nodes whose labels contain all of those
291 // substrings.
292 fn node_set(query: &DepGraphQuery, filter: &str) -> Option<FnvHashSet<DepNode>> {
293 debug!("node_set(filter={:?})", filter);
294
295 if filter.trim().is_empty() {
296 return None;
297 }
298
299 let filters: Vec<&str> = filter.split("&").map(|s| s.trim()).collect();
300
301 debug!("node_set: filters={:?}", filters);
302
303 Some(query.nodes()
304 .into_iter()
305 .filter(|n| {
306 let s = format!("{:?}", n);
307 filters.iter().all(|f| s.contains(f))
308 })
309 .collect())
310 }
311
312 fn filter_nodes(query: &DepGraphQuery,
313 sources: &Option<FnvHashSet<DepNode>>,
314 targets: &Option<FnvHashSet<DepNode>>)
315 -> FnvHashSet<DepNode>
316 {
317 if let &Some(ref sources) = sources {
318 if let &Some(ref targets) = targets {
319 walk_between(query, sources, targets)
320 } else {
321 walk_nodes(query, sources, OUTGOING)
322 }
323 } else if let &Some(ref targets) = targets {
324 walk_nodes(query, targets, INCOMING)
325 } else {
326 query.nodes().into_iter().collect()
327 }
328 }
329
330 fn walk_nodes(query: &DepGraphQuery,
331 starts: &FnvHashSet<DepNode>,
332 direction: Direction)
333 -> FnvHashSet<DepNode>
334 {
335 let mut set = FnvHashSet();
336 for start in starts {
337 debug!("walk_nodes: start={:?} outgoing?={:?}", start, direction == OUTGOING);
338 if set.insert(*start) {
339 let mut stack = vec![query.indices[start]];
340 while let Some(index) = stack.pop() {
341 for (_, edge) in query.graph.adjacent_edges(index, direction) {
342 let neighbor_index = edge.source_or_target(direction);
343 let neighbor = query.graph.node_data(neighbor_index);
344 if set.insert(*neighbor) {
345 stack.push(neighbor_index);
346 }
347 }
348 }
349 }
350 }
351 set
352 }
353
354 fn walk_between(query: &DepGraphQuery,
355 sources: &FnvHashSet<DepNode>,
356 targets: &FnvHashSet<DepNode>)
357 -> FnvHashSet<DepNode>
358 {
359 // This is a bit tricky. We want to include a node only if it is:
360 // (a) reachable from a source and (b) will reach a target. And we
361 // have to be careful about cycles etc. Luckily efficiency is not
362 // a big concern!
363
364 #[derive(Copy, Clone, PartialEq)]
365 enum State { Undecided, Deciding, Included, Excluded }
366
367 let mut node_states = vec![State::Undecided; query.graph.len_nodes()];
368
369 for &target in targets {
370 node_states[query.indices[&target].0] = State::Included;
371 }
372
373 for source in sources.iter().map(|n| query.indices[n]) {
374 recurse(query, &mut node_states, source);
375 }
376
377 return query.nodes()
378 .into_iter()
379 .filter(|n| {
380 let index = query.indices[n];
381 node_states[index.0] == State::Included
382 })
383 .collect();
384
385 fn recurse(query: &DepGraphQuery,
386 node_states: &mut [State],
387 node: NodeIndex)
388 -> bool
389 {
390 match node_states[node.0] {
391 // known to reach a target
392 State::Included => return true,
393
394 // known not to reach a target
395 State::Excluded => return false,
396
397 // backedge, not yet known, say false
398 State::Deciding => return false,
399
400 State::Undecided => { }
401 }
402
403 node_states[node.0] = State::Deciding;
404
405 for neighbor_index in query.graph.successor_nodes(node) {
406 if recurse(query, node_states, neighbor_index) {
407 node_states[node.0] = State::Included;
408 }
409 }
410
411 // if we didn't find a path to target, then set to excluded
412 if node_states[node.0] == State::Deciding {
413 node_states[node.0] = State::Excluded;
414 false
415 } else {
416 assert!(node_states[node.0] == State::Included);
417 true
418 }
419 }
420 }
421
422 fn filter_edges(query: &DepGraphQuery,
423 nodes: &FnvHashSet<DepNode>)
424 -> Vec<(DepNode, DepNode)>
425 {
426 query.edges()
427 .into_iter()
428 .filter(|&(source, target)| nodes.contains(&source) && nodes.contains(&target))
429 .collect()
430 }