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. 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
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.
28 //! The full form of the `rustc_if_this_changed` annotation is
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.
36 //! #[rustc_if_this_changed(Hir)]
39 //! #[rustc_then_this_would_need(trans)] //~ ERROR no path from `foo`
42 //! #[rustc_then_this_would_need(trans)] //~ ERROR OK
43 //! fn baz() { foo(); }
47 use rustc
::dep_graph
::{DepGraphQuery, DepNode, DepKind}
;
48 use rustc
::dep_graph
::debug
::{DepNodeFilter, EdgeFilter}
;
49 use rustc
::hir
::def_id
::DefId
;
50 use rustc
::ty
::TyCtxt
;
51 use rustc_data_structures
::fx
::FxHashSet
;
52 use rustc_data_structures
::graph
::{Direction, INCOMING, OUTGOING, NodeIndex}
;
54 use rustc
::hir
::intravisit
::{self, NestedVisitorMap, Visitor}
;
55 use rustc
::ich
::{ATTR_IF_THIS_CHANGED, ATTR_THEN_THIS_WOULD_NEED}
;
56 use graphviz
::IntoCow
;
58 use std
::fs
::{self, File}
;
63 pub fn assert_dep_graph
<'a
, 'tcx
>(tcx
: TyCtxt
<'a
, 'tcx
, 'tcx
>) {
64 tcx
.dep_graph
.with_ignore(|| {
65 if tcx
.sess
.opts
.debugging_opts
.dump_dep_graph
{
69 // if the `rustc_attrs` feature is not enabled, then the
70 // attributes we are interested in cannot be present anyway, so
72 if !tcx
.features().rustc_attrs
{
76 // Find annotations supplied by user (if any).
77 let (if_this_changed
, then_this_would_need
) = {
78 let mut visitor
= IfThisChanged
{ tcx
,
79 if_this_changed
: vec
![],
80 then_this_would_need
: vec
![] };
81 visitor
.process_attrs(ast
::CRATE_NODE_ID
, &tcx
.hir
.krate().attrs
);
82 tcx
.hir
.krate().visit_all_item_likes(&mut visitor
.as_deep_visitor());
83 (visitor
.if_this_changed
, visitor
.then_this_would_need
)
86 if !if_this_changed
.is_empty() || !then_this_would_need
.is_empty() {
87 assert
!(tcx
.sess
.opts
.debugging_opts
.query_dep_graph
,
88 "cannot use the `#[{}]` or `#[{}]` annotations \
89 without supplying `-Z query-dep-graph`",
90 ATTR_IF_THIS_CHANGED
, ATTR_THEN_THIS_WOULD_NEED
);
94 check_paths(tcx
, &if_this_changed
, &then_this_would_need
);
98 type Sources
= Vec
<(Span
, DefId
, DepNode
)>;
99 type Targets
= Vec
<(Span
, ast
::Name
, ast
::NodeId
, DepNode
)>;
101 struct IfThisChanged
<'a
, 'tcx
:'a
> {
102 tcx
: TyCtxt
<'a
, 'tcx
, 'tcx
>,
103 if_this_changed
: Sources
,
104 then_this_would_need
: Targets
,
107 impl<'a
, 'tcx
> IfThisChanged
<'a
, 'tcx
> {
108 fn argument(&self, attr
: &ast
::Attribute
) -> Option
<ast
::Name
> {
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()),
115 // FIXME better-encapsulate meta_item (don't directly access `node`)
116 span_bug
!(list_item
.span(), "unexpected meta-item {:?}", list_item
.node
),
122 fn process_attrs(&mut self, node_id
: ast
::NodeId
, attrs
: &[ast
::Attribute
]) {
123 let def_id
= self.tcx
.hir
.local_def_id(node_id
);
124 let def_path_hash
= self.tcx
.def_path_hash(def_id
);
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
{
129 None
=> def_path_hash
.to_dep_node(DepKind
::Hir
),
131 match DepNode
::from_label_string(&n
.as_str(), def_path_hash
) {
134 self.tcx
.sess
.span_fatal(
136 &format
!("unrecognized DepNode variant {:?}", n
));
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
);
144 let dep_node
= match dep_node_interned
{
146 match DepNode
::from_label_string(&n
.as_str(), def_path_hash
) {
149 self.tcx
.sess
.span_fatal(
151 &format
!("unrecognized DepNode variant {:?}", n
));
156 self.tcx
.sess
.span_fatal(
158 "missing DepNode variant");
161 self.then_this_would_need
.push((attr
.span
,
162 dep_node_interned
.unwrap(),
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
)
175 fn visit_item(&mut self, item
: &'tcx hir
::Item
) {
176 self.process_attrs(item
.id
, &item
.attrs
);
177 intravisit
::walk_item(self, item
);
180 fn visit_trait_item(&mut self, trait_item
: &'tcx hir
::TraitItem
) {
181 self.process_attrs(trait_item
.id
, &trait_item
.attrs
);
182 intravisit
::walk_trait_item(self, trait_item
);
185 fn visit_impl_item(&mut self, impl_item
: &'tcx hir
::ImplItem
) {
186 self.process_attrs(impl_item
.id
, &impl_item
.attrs
);
187 intravisit
::walk_impl_item(self, impl_item
);
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
);
196 fn check_paths
<'a
, 'tcx
>(tcx
: TyCtxt
<'a
, 'tcx
, 'tcx
>,
197 if_this_changed
: &Sources
,
198 then_this_would_need
: &Targets
)
200 // Return early here so as not to construct the query, which is not cheap.
201 if if_this_changed
.is_empty() {
202 for &(target_span
, _
, _
, _
) in then_this_would_need
{
205 "no #[rustc_if_this_changed] annotation detected");
210 let query
= tcx
.dep_graph
.query();
211 for &(_
, source_def_id
, ref source_dep_node
) in if_this_changed
{
212 let dependents
= query
.transitive_predecessors(source_dep_node
);
213 for &(target_span
, ref target_pass
, _
, ref target_dep_node
) in then_this_would_need
{
214 if !dependents
.contains(&target_dep_node
) {
217 &format
!("no path from `{}` to `{}`",
218 tcx
.item_path_str(source_def_id
),
229 fn dump_graph(tcx
: TyCtxt
) {
230 let path
: String
= env
::var("RUST_DEP_GRAPH").unwrap_or_else(|_
| format
!("dep_graph"));
231 let query
= tcx
.dep_graph
.query();
233 let nodes
= match env
::var("RUST_DEP_GRAPH_FILTER") {
235 // Expect one of: "-> target", "source -> target", or "source ->".
236 let edge_filter
= EdgeFilter
::new(&string
).unwrap_or_else(|e
| {
237 bug
!("invalid filter: {}", e
)
239 let sources
= node_set(&query
, &edge_filter
.source
);
240 let targets
= node_set(&query
, &edge_filter
.target
);
241 filter_nodes(&query
, &sources
, &targets
)
249 let edges
= filter_edges(&query
, &nodes
);
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();
254 for &(ref source
, ref target
) in &edges
{
255 write
!(file
, "{:?} -> {:?}\n", source
, target
).unwrap();
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 fs
::write(dot_path
, v
).unwrap();
267 pub struct GraphvizDepGraph
<'q
>(FxHashSet
<&'q DepNode
>,
268 Vec
<(&'q DepNode
, &'q DepNode
)>);
270 impl<'a
, 'tcx
, 'q
> dot
::GraphWalk
<'a
> for GraphvizDepGraph
<'q
> {
271 type Node
= &'q DepNode
;
272 type Edge
= (&'q DepNode
, &'q DepNode
);
273 fn nodes(&self) -> dot
::Nodes
<&'q DepNode
> {
274 let nodes
: Vec
<_
> = self.0.iter
().cloned().collect();
277 fn edges(&self) -> dot
::Edges
<(&'q DepNode
, &'q DepNode
)> {
278 self.1[..].into_cow()
280 fn source(&self, edge
: &(&'q DepNode
, &'q DepNode
)) -> &'q DepNode
{
283 fn target(&self, edge
: &(&'q DepNode
, &'q DepNode
)) -> &'q DepNode
{
288 impl<'a
, 'tcx
, 'q
> dot
::Labeller
<'a
> for GraphvizDepGraph
<'q
> {
289 type Node
= &'q DepNode
;
290 type Edge
= (&'q DepNode
, &'q DepNode
);
291 fn graph_id(&self) -> dot
::Id
{
292 dot
::Id
::new("DependencyGraph").unwrap()
294 fn node_id(&self, n
: &&'q DepNode
) -> dot
::Id
{
296 format
!("{:?}", n
).chars()
297 .map(|c
| if c
== '_'
|| c
.is_alphanumeric() { c }
else { '_' }
)
299 debug
!("n={:?} s={:?}", n
, s
);
300 dot
::Id
::new(s
).unwrap()
302 fn node_label(&self, n
: &&'q DepNode
) -> dot
::LabelText
{
303 dot
::LabelText
::label(format
!("{:?}", n
))
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
310 fn node_set
<'q
>(query
: &'q DepGraphQuery
, filter
: &DepNodeFilter
)
311 -> Option
<FxHashSet
<&'q DepNode
>>
313 debug
!("node_set(filter={:?})", filter
);
315 if filter
.accepts_all() {
319 Some(query
.nodes().into_iter().filter(|n
| filter
.test(n
)).collect())
322 fn filter_nodes
<'q
>(query
: &'q DepGraphQuery
,
323 sources
: &Option
<FxHashSet
<&'q DepNode
>>,
324 targets
: &Option
<FxHashSet
<&'q DepNode
>>)
325 -> FxHashSet
<&'q DepNode
>
327 if let &Some(ref sources
) = sources
{
328 if let &Some(ref targets
) = targets
{
329 walk_between(query
, sources
, targets
)
331 walk_nodes(query
, sources
, OUTGOING
)
333 } else if let &Some(ref targets
) = targets
{
334 walk_nodes(query
, targets
, INCOMING
)
336 query
.nodes().into_iter().collect()
340 fn walk_nodes
<'q
>(query
: &'q DepGraphQuery
,
341 starts
: &FxHashSet
<&'q DepNode
>,
342 direction
: Direction
)
343 -> FxHashSet
<&'q DepNode
>
345 let mut set
= FxHashSet();
346 for &start
in starts
{
347 debug
!("walk_nodes: start={:?} outgoing?={:?}", start
, direction
== OUTGOING
);
348 if set
.insert(start
) {
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
);
354 if set
.insert(neighbor
) {
355 stack
.push(neighbor_index
);
364 fn walk_between
<'q
>(query
: &'q DepGraphQuery
,
365 sources
: &FxHashSet
<&'q DepNode
>,
366 targets
: &FxHashSet
<&'q DepNode
>)
367 -> FxHashSet
<&'q DepNode
>
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
374 #[derive(Copy, Clone, PartialEq)]
375 enum State { Undecided, Deciding, Included, Excluded }
377 let mut node_states
= vec
![State
::Undecided
; query
.graph
.len_nodes()];
379 for &target
in targets
{
380 node_states
[query
.indices
[target
].0] = State
::Included
;
383 for source
in sources
.iter().map(|&n
| query
.indices
[n
]) {
384 recurse(query
, &mut node_states
, source
);
390 let index
= query
.indices
[n
];
391 node_states
[index
.0] == State
::Included
395 fn recurse(query
: &DepGraphQuery
,
396 node_states
: &mut [State
],
400 match node_states
[node
.0] {
401 // known to reach a target
402 State
::Included
=> return true,
404 // known not to reach a target
405 State
::Excluded
=> return false,
407 // backedge, not yet known, say false
408 State
::Deciding
=> return false,
410 State
::Undecided
=> { }
413 node_states
[node
.0] = State
::Deciding
;
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
;
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
;
426 assert
!(node_states
[node
.0] == State
::Included
);
432 fn filter_edges
<'q
>(query
: &'q DepGraphQuery
,
433 nodes
: &FxHashSet
<&'q DepNode
>)
434 -> Vec
<(&'q DepNode
, &'q DepNode
)>
438 .filter(|&(source
, target
)| nodes
.contains(source
) && nodes
.contains(target
))