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.
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.
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
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.
30 //! #[rustc_if_this_changed]
33 //! #[rustc_then_this_would_need("trans")] //~ ERROR no path from `foo`
36 //! #[rustc_then_this_would_need("trans")] //~ ERROR OK
37 //! fn baz() { foo(); }
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}
;
47 use rustc_front
::intravisit
::Visitor
;
48 use graphviz
::IntoCow
;
53 use syntax
::attr
::AttrMetaMethods
;
54 use syntax
::codemap
::Span
;
55 use syntax
::parse
::token
::InternedString
;
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";
61 pub fn assert_dep_graph(tcx
: &ty
::ctxt
) {
62 let _ignore
= tcx
.dep_graph
.in_ignore();
64 if tcx
.sess
.opts
.dump_dep_graph
{
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
)
78 check_paths(tcx
, &if_this_changed
, &then_this_would_need
);
81 type SourceHashMap
= FnvHashMap
<InternedString
,
82 FnvHashSet
<(Span
, DefId
, DepNode
)>>;
83 type TargetHashMap
= FnvHashMap
<InternedString
,
84 FnvHashSet
<(Span
, InternedString
, ast
::NodeId
, DepNode
)>>;
86 struct IfThisChanged
<'a
, 'tcx
:'a
> {
87 tcx
: &'a ty
::ctxt
<'tcx
>,
88 if_this_changed
: SourceHashMap
,
89 then_this_would_need
: TargetHashMap
,
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
) {
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()),
101 self.tcx
.sess
.span_err(
103 &format
!("unexpected meta-item {:?}", meta_item
.node
));
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
;
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()),
121 self.tcx
.sess
.span_err(
123 &format
!("unexpected meta-item {:?}", meta_item
.node
));
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
) => {
131 $
(Some(stringify
!($variant
)) => DepNode
::$
variant($def_id
),)*
136 let dep_node
= match_depnode_name
! {
137 dep_node_str
, def_id
, match {
152 self.tcx
.sess
.span_fatal(
154 &format
!("unrecognized DepNode variant {:?}", dep_node_str
));
157 let id
= id
.unwrap_or(InternedString
::new(ID
));
158 self.then_this_would_need
160 .or_insert(FnvHashSet())
161 .insert((attr
.span
, dep_node_interned
.clone().unwrap(), node_id
, dep_node
));
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
);
174 fn check_paths(tcx
: &ty
::ctxt
,
175 if_this_changed
: &SourceHashMap
,
176 then_this_would_need
: &TargetHashMap
)
178 // Return early here so as not to construct the query, which is not cheap.
179 if if_this_changed
.is_empty() {
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
,
187 for &(source_span
, _
, _
) in sources
.iter().take(1) {
190 &format
!("no targets for id `{}`", id
));
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
) {
202 &format
!("no path from `{}` to `{}`",
203 tcx
.item_path_str(source_def_id
),
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();
219 let nodes
= match env
::var("RUST_DEP_GRAPH_FILTER") {
221 // Expect one of: "-> target", "source -> target", or "source ->".
222 let parts
: Vec
<_
> = string
.split("->").collect();
224 panic
!("Invalid RUST_DEP_GRAPH_FILTER: expected '[source] -> [target]'");
226 let sources
= node_set(&query
, &parts
[0]);
227 let targets
= node_set(&query
, &parts
[1]);
228 filter_nodes(&query
, &sources
, &targets
)
236 let edges
= filter_edges(&query
, &nodes
);
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();
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();
254 pub struct GraphvizDepGraph(FnvHashSet
<DepNode
>, Vec
<(DepNode
, DepNode
)>);
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();
261 fn edges(&self) -> dot
::Edges
<(DepNode
, DepNode
)> {
262 self.1[..].into_cow()
264 fn source(&self, edge
: &(DepNode
, DepNode
)) -> DepNode
{
267 fn target(&self, edge
: &(DepNode
, DepNode
)) -> DepNode
{
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()
276 fn node_id(&self, n
: &DepNode
) -> dot
::Id
{
278 format
!("{:?}", n
).chars()
279 .map(|c
| if c
== '_'
|| c
.is_alphanumeric() { c }
else { '_' }
)
281 debug
!("n={:?} s={:?}", n
, s
);
282 dot
::Id
::new(s
).unwrap()
284 fn node_label(&self, n
: &DepNode
) -> dot
::LabelText
{
285 dot
::LabelText
::label(format
!("{:?}", n
))
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
292 fn node_set(query
: &DepGraphQuery
, filter
: &str) -> Option
<FnvHashSet
<DepNode
>> {
293 debug
!("node_set(filter={:?})", filter
);
295 if filter
.trim().is_empty() {
299 let filters
: Vec
<&str> = filter
.split("&").map(|s
| s
.trim()).collect();
301 debug
!("node_set: filters={:?}", filters
);
306 let s
= format
!("{:?}", n
);
307 filters
.iter().all(|f
| s
.contains(f
))
312 fn filter_nodes(query
: &DepGraphQuery
,
313 sources
: &Option
<FnvHashSet
<DepNode
>>,
314 targets
: &Option
<FnvHashSet
<DepNode
>>)
315 -> FnvHashSet
<DepNode
>
317 if let &Some(ref sources
) = sources
{
318 if let &Some(ref targets
) = targets
{
319 walk_between(query
, sources
, targets
)
321 walk_nodes(query
, sources
, OUTGOING
)
323 } else if let &Some(ref targets
) = targets
{
324 walk_nodes(query
, targets
, INCOMING
)
326 query
.nodes().into_iter().collect()
330 fn walk_nodes(query
: &DepGraphQuery
,
331 starts
: &FnvHashSet
<DepNode
>,
332 direction
: Direction
)
333 -> FnvHashSet
<DepNode
>
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
);
354 fn walk_between(query
: &DepGraphQuery
,
355 sources
: &FnvHashSet
<DepNode
>,
356 targets
: &FnvHashSet
<DepNode
>)
357 -> FnvHashSet
<DepNode
>
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
364 #[derive(Copy, Clone, PartialEq)]
365 enum State { Undecided, Deciding, Included, Excluded }
367 let mut node_states
= vec
![State
::Undecided
; query
.graph
.len_nodes()];
369 for &target
in targets
{
370 node_states
[query
.indices
[&target
].0] = State
::Included
;
373 for source
in sources
.iter().map(|n
| query
.indices
[n
]) {
374 recurse(query
, &mut node_states
, source
);
380 let index
= query
.indices
[n
];
381 node_states
[index
.0] == State
::Included
385 fn recurse(query
: &DepGraphQuery
,
386 node_states
: &mut [State
],
390 match node_states
[node
.0] {
391 // known to reach a target
392 State
::Included
=> return true,
394 // known not to reach a target
395 State
::Excluded
=> return false,
397 // backedge, not yet known, say false
398 State
::Deciding
=> return false,
400 State
::Undecided
=> { }
403 node_states
[node
.0] = State
::Deciding
;
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
;
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
;
416 assert
!(node_states
[node
.0] == State
::Included
);
422 fn filter_edges(query
: &DepGraphQuery
,
423 nodes
: &FnvHashSet
<DepNode
>)
424 -> Vec
<(DepNode
, DepNode
)>
428 .filter(|&(source
, target
)| nodes
.contains(&source
) && nodes
.contains(&target
))