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
6 //! exist in the graph. These checks run after codegen, so they view the
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
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
15 //! each case where no path exists. `ui` tests can then be
16 //! used to check when paths exist or do not.
18 //! The full form of the `rustc_if_this_changed` annotation is
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.
26 //! #[rustc_if_this_changed(Hir)]
29 //! #[rustc_then_this_would_need(codegen)] //~ ERROR no path from `foo`
32 //! #[rustc_then_this_would_need(codegen)] //~ ERROR OK
33 //! fn baz() { foo(); }
37 use rustc_data_structures
::fx
::FxHashSet
;
38 use rustc_data_structures
::graph
::implementation
::{Direction, NodeIndex, INCOMING, OUTGOING}
;
39 use rustc_graphviz
as dot
;
41 use rustc_hir
::def_id
::DefId
;
42 use rustc_hir
::intravisit
::{self, NestedVisitorMap, Visitor}
;
43 use rustc_middle
::dep_graph
::{
44 DepGraphQuery
, DepKind
, DepNode
, DepNodeExt
, DepNodeFilter
, EdgeFilter
,
46 use rustc_middle
::hir
::map
::Map
;
47 use rustc_middle
::ty
::TyCtxt
;
48 use rustc_span
::symbol
::{sym, Symbol}
;
52 use std
::fs
::{self, File}
;
53 use std
::io
::{BufWriter, Write}
;
55 #[allow(missing_docs)]
56 pub fn assert_dep_graph(tcx
: TyCtxt
<'_
>) {
57 tcx
.dep_graph
.with_ignore(|| {
58 if tcx
.sess
.opts
.debugging_opts
.dump_dep_graph
{
59 tcx
.dep_graph
.with_query(dump_graph
);
62 if !tcx
.sess
.opts
.debugging_opts
.query_dep_graph
{
66 // if the `rustc_attrs` feature is not enabled, then the
67 // attributes we are interested in cannot be present anyway, so
69 if !tcx
.features().rustc_attrs
{
73 // Find annotations supplied by user (if any).
74 let (if_this_changed
, then_this_would_need
) = {
76 IfThisChanged { tcx, if_this_changed: vec![], then_this_would_need: vec![] }
;
77 visitor
.process_attrs(hir
::CRATE_HIR_ID
);
78 tcx
.hir().visit_all_item_likes(&mut visitor
.as_deep_visitor());
79 (visitor
.if_this_changed
, visitor
.then_this_would_need
)
82 if !if_this_changed
.is_empty() || !then_this_would_need
.is_empty() {
84 tcx
.sess
.opts
.debugging_opts
.query_dep_graph
,
85 "cannot use the `#[{}]` or `#[{}]` annotations \
86 without supplying `-Z query-dep-graph`",
87 sym
::rustc_if_this_changed
,
88 sym
::rustc_then_this_would_need
93 check_paths(tcx
, &if_this_changed
, &then_this_would_need
);
97 type Sources
= Vec
<(Span
, DefId
, DepNode
)>;
98 type Targets
= Vec
<(Span
, Symbol
, hir
::HirId
, DepNode
)>;
100 struct IfThisChanged
<'tcx
> {
102 if_this_changed
: Sources
,
103 then_this_would_need
: Targets
,
106 impl<'tcx
> IfThisChanged
<'tcx
> {
107 fn argument(&self, attr
: &ast
::Attribute
) -> Option
<Symbol
> {
108 let mut value
= None
;
109 for list_item
in attr
.meta_item_list().unwrap_or_default() {
110 match list_item
.ident() {
111 Some(ident
) if list_item
.is_word() && value
.is_none() => value
= Some(ident
.name
),
113 // FIXME better-encapsulate meta_item (don't directly access `node`)
115 span_bug
!(list_item
.span(), "unexpected meta-item {:?}", list_item
)
122 fn process_attrs(&mut self, hir_id
: hir
::HirId
) {
123 let def_id
= self.tcx
.hir().local_def_id(hir_id
);
124 let def_path_hash
= self.tcx
.def_path_hash(def_id
.to_def_id());
125 let attrs
= self.tcx
.hir().attrs(hir_id
);
127 if attr
.has_name(sym
::rustc_if_this_changed
) {
128 let dep_node_interned
= self.argument(attr
);
129 let dep_node
= match dep_node_interned
{
131 DepNode
::from_def_path_hash(self.tcx
, def_path_hash
, DepKind
::hir_owner
)
134 match DepNode
::from_label_string(self.tcx
, n
.as_str(), def_path_hash
) {
137 self.tcx
.sess
.span_fatal(
139 &format
!("unrecognized DepNode variant {:?}", n
),
145 self.if_this_changed
.push((attr
.span
, def_id
.to_def_id(), dep_node
));
146 } else if attr
.has_name(sym
::rustc_then_this_would_need
) {
147 let dep_node_interned
= self.argument(attr
);
148 let dep_node
= match dep_node_interned
{
150 match DepNode
::from_label_string(self.tcx
, n
.as_str(), def_path_hash
) {
153 self.tcx
.sess
.span_fatal(
155 &format
!("unrecognized DepNode variant {:?}", n
),
161 self.tcx
.sess
.span_fatal(attr
.span
, "missing DepNode variant");
164 self.then_this_would_need
.push((
166 dep_node_interned
.unwrap(),
175 impl<'tcx
> Visitor
<'tcx
> for IfThisChanged
<'tcx
> {
176 type Map
= Map
<'tcx
>;
178 fn nested_visit_map(&mut self) -> NestedVisitorMap
<Self::Map
> {
179 NestedVisitorMap
::OnlyBodies(self.tcx
.hir())
182 fn visit_item(&mut self, item
: &'tcx hir
::Item
<'tcx
>) {
183 self.process_attrs(item
.hir_id());
184 intravisit
::walk_item(self, item
);
187 fn visit_trait_item(&mut self, trait_item
: &'tcx hir
::TraitItem
<'tcx
>) {
188 self.process_attrs(trait_item
.hir_id());
189 intravisit
::walk_trait_item(self, trait_item
);
192 fn visit_impl_item(&mut self, impl_item
: &'tcx hir
::ImplItem
<'tcx
>) {
193 self.process_attrs(impl_item
.hir_id());
194 intravisit
::walk_impl_item(self, impl_item
);
197 fn visit_field_def(&mut self, s
: &'tcx hir
::FieldDef
<'tcx
>) {
198 self.process_attrs(s
.hir_id
);
199 intravisit
::walk_field_def(self, s
);
203 fn check_paths
<'tcx
>(tcx
: TyCtxt
<'tcx
>, if_this_changed
: &Sources
, then_this_would_need
: &Targets
) {
204 // Return early here so as not to construct the query, which is not cheap.
205 if if_this_changed
.is_empty() {
206 for &(target_span
, _
, _
, _
) in then_this_would_need
{
207 tcx
.sess
.span_err(target_span
, "no `#[rustc_if_this_changed]` annotation detected");
211 tcx
.dep_graph
.with_query(|query
| {
212 for &(_
, source_def_id
, ref source_dep_node
) in if_this_changed
{
213 let dependents
= query
.transitive_predecessors(source_dep_node
);
214 for &(target_span
, ref target_pass
, _
, ref target_dep_node
) in then_this_would_need
{
215 if !dependents
.contains(&target_dep_node
) {
219 "no path from `{}` to `{}`",
220 tcx
.def_path_str(source_def_id
),
225 tcx
.sess
.span_err(target_span
, "OK");
232 fn dump_graph(query
: &DepGraphQuery
) {
233 let path
: String
= env
::var("RUST_DEP_GRAPH").unwrap_or_else(|_
| "dep_graph".to_string());
235 let nodes
= match env
::var("RUST_DEP_GRAPH_FILTER") {
237 // Expect one of: "-> target", "source -> target", or "source ->".
239 EdgeFilter
::new(&string
).unwrap_or_else(|e
| bug
!("invalid filter: {}", e
));
240 let sources
= node_set(&query
, &edge_filter
.source
);
241 let targets
= node_set(&query
, &edge_filter
.target
);
242 filter_nodes(&query
, &sources
, &targets
)
244 Err(_
) => query
.nodes().into_iter().collect(),
246 let edges
= filter_edges(&query
, &nodes
);
249 // dump a .txt file with just the edges:
250 let txt_path
= format
!("{}.txt", path
);
251 let mut file
= BufWriter
::new(File
::create(&txt_path
).unwrap());
252 for &(ref source
, ref target
) in &edges
{
253 write
!(file
, "{:?} -> {:?}\n", source
, target
).unwrap();
258 // dump a .dot file in graphviz format:
259 let dot_path
= format
!("{}.dot", path
);
260 let mut v
= Vec
::new();
261 dot
::render(&GraphvizDepGraph(nodes
, edges
), &mut v
).unwrap();
262 fs
::write(dot_path
, v
).unwrap();
266 #[allow(missing_docs)]
267 pub struct GraphvizDepGraph
<'q
>(FxHashSet
<&'q DepNode
>, Vec
<(&'q DepNode
, &'q DepNode
)>);
269 impl<'a
, 'q
> dot
::GraphWalk
<'a
> for GraphvizDepGraph
<'q
> {
270 type Node
= &'q DepNode
;
271 type Edge
= (&'q DepNode
, &'q DepNode
);
272 fn nodes(&self) -> dot
::Nodes
<'_
, &'q DepNode
> {
273 let nodes
: Vec
<_
> = self.0.iter
().cloned().collect();
276 fn edges(&self) -> dot
::Edges
<'_
, (&'q DepNode
, &'q DepNode
)> {
279 fn source(&self, edge
: &(&'q DepNode
, &'q DepNode
)) -> &'q DepNode
{
282 fn target(&self, edge
: &(&'q DepNode
, &'q DepNode
)) -> &'q DepNode
{
287 impl<'a
, 'q
> dot
::Labeller
<'a
> for GraphvizDepGraph
<'q
> {
288 type Node
= &'q DepNode
;
289 type Edge
= (&'q DepNode
, &'q DepNode
);
290 fn graph_id(&self) -> dot
::Id
<'_
> {
291 dot
::Id
::new("DependencyGraph").unwrap()
293 fn node_id(&self, n
: &&'q DepNode
) -> dot
::Id
<'_
> {
294 let s
: String
= format
!("{:?}", n
)
296 .map(|c
| if c
== '_'
|| c
.is_alphanumeric() { c }
else { '_' }
)
298 debug
!("n={:?} s={:?}", n
, s
);
299 dot
::Id
::new(s
).unwrap()
301 fn node_label(&self, n
: &&'q DepNode
) -> dot
::LabelText
<'_
> {
302 dot
::LabelText
::label(format
!("{:?}", n
))
306 // Given an optional filter like `"x,y,z"`, returns either `None` (no
307 // filter) or the set of nodes whose labels contain all of those
310 query
: &'q DepGraphQuery
,
311 filter
: &DepNodeFilter
,
312 ) -> 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())
323 query
: &'q DepGraphQuery
,
324 sources
: &Option
<FxHashSet
<&'q DepNode
>>,
325 targets
: &Option
<FxHashSet
<&'q DepNode
>>,
326 ) -> FxHashSet
<&'q DepNode
> {
327 if let Some(sources
) = sources
{
328 if let Some(targets
) = targets
{
329 walk_between(query
, sources
, targets
)
331 walk_nodes(query
, sources
, OUTGOING
)
333 } else if let Some(targets
) = targets
{
334 walk_nodes(query
, targets
, INCOMING
)
336 query
.nodes().into_iter().collect()
341 query
: &'q DepGraphQuery
,
342 starts
: &FxHashSet
<&'q DepNode
>,
343 direction
: Direction
,
344 ) -> FxHashSet
<&'q DepNode
> {
345 let mut set
= FxHashSet
::default();
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
);
365 query
: &'q DepGraphQuery
,
366 sources
: &FxHashSet
<&'q DepNode
>,
367 targets
: &FxHashSet
<&'q DepNode
>,
368 ) -> 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)]
382 let mut node_states
= vec
![State
::Undecided
; query
.graph
.len_nodes()];
384 for &target
in targets
{
385 node_states
[query
.indices
[target
].0] = State
::Included
;
388 for source
in sources
.iter().map(|&n
| query
.indices
[n
]) {
389 recurse(query
, &mut node_states
, source
);
396 let index
= query
.indices
[n
];
397 node_states
[index
.0] == State
::Included
401 fn recurse(query
: &DepGraphQuery
, node_states
: &mut [State
], node
: NodeIndex
) -> bool
{
402 match node_states
[node
.0] {
403 // known to reach a target
404 State
::Included
=> return true,
406 // known not to reach a target
407 State
::Excluded
=> return false,
409 // backedge, not yet known, say false
410 State
::Deciding
=> return false,
412 State
::Undecided
=> {}
415 node_states
[node
.0] = State
::Deciding
;
417 for neighbor_index
in query
.graph
.successor_nodes(node
) {
418 if recurse(query
, node_states
, neighbor_index
) {
419 node_states
[node
.0] = State
::Included
;
423 // if we didn't find a path to target, then set to excluded
424 if node_states
[node
.0] == State
::Deciding
{
425 node_states
[node
.0] = State
::Excluded
;
428 assert
!(node_states
[node
.0] == State
::Included
);
435 query
: &'q DepGraphQuery
,
436 nodes
: &FxHashSet
<&'q DepNode
>,
437 ) -> Vec
<(&'q DepNode
, &'q DepNode
)> {
441 .filter(|&(source
, target
)| nodes
.contains(source
) && nodes
.contains(target
))