rustc_query_system/dep_graph/
query.rs

Help
1use rustc_data_structures::fx::FxHashMap;
2use rustc_data_structures::graph::implementation::{Direction, Graph, INCOMING, NodeIndex};
3use rustc_index::IndexVec;
4
5use super::{DepNode, DepNodeIndex};
6
7pub struct DepGraphQuery {
8    pub graph: Graph<DepNode, ()>,
9    pub indices: FxHashMap<DepNode, NodeIndex>,
10    pub dep_index_to_index: IndexVec<DepNodeIndex, Option<NodeIndex>>,
11}
12
13impl DepGraphQuery {
14    pub fn new(prev_node_count: usize) -> DepGraphQuery {
15        let node_count = prev_node_count + prev_node_count / 4;
16        let edge_count = 6 * node_count;
17
18        let graph = Graph::with_capacity(node_count, edge_count);
19        let indices = FxHashMap::default();
20        let dep_index_to_index = IndexVec::new();
21
22        DepGraphQuery { graph, indices, dep_index_to_index }
23    }
24
25    pub fn push(&mut self, index: DepNodeIndex, node: DepNode, edges: &[DepNodeIndex]) {
26        let source = self.graph.add_node(node);
27        self.dep_index_to_index.insert(index, source);
28        self.indices.insert(node, source);
29
30        for &target in edges.iter() {
31            let target = self.dep_index_to_index[target];
32            // We may miss the edges that are pushed while the `DepGraphQuery` is being accessed.
33            // Skip them to issues.
34            if let Some(target) = target {
35                self.graph.add_edge(source, target, ());
36            }
37        }
38    }
39
40    pub fn nodes(&self) -> Vec<&DepNode> {
41        self.graph.all_nodes().iter().map(|n| &n.data).collect()
42    }
43
44    pub fn edges(&self) -> Vec<(&DepNode, &DepNode)> {
45        self.graph
46            .all_edges()
47            .iter()
48            .map(|edge| (edge.source(), edge.target()))
49            .map(|(s, t)| (self.graph.node_data(s), self.graph.node_data(t)))
50            .collect()
51    }
52
53    fn reachable_nodes(&self, node: &DepNode, direction: Direction) -> Vec<&DepNode> {
54        if let Some(&index) = self.indices.get(node) {
55            self.graph.depth_traverse(index, direction).map(|s| self.graph.node_data(s)).collect()
56        } else {
57            vec![]
58        }
59    }
60
61    /// All nodes that can reach `node`.
62    pub fn transitive_predecessors(&self, node: &DepNode) -> Vec<&DepNode> {
63        self.reachable_nodes(node, INCOMING)
64    }
65}
rustc_query_system/dep_graph/query.rs

rustc_query_system/dep_graph/
query.rs
