rustc_middle/dep_graph/
query.rs

1use rustc_data_structures::fx::FxHashMap;
2use rustc_data_structures::graph::linked_graph::{Direction, INCOMING, LinkedGraph, NodeIndex};
3use rustc_index::IndexVec;
4
5use super::{DepNode, DepNodeIndex};
6
7pub struct DepGraphQuery {
8    pub graph: LinkedGraph<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 = LinkedGraph::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            // We may miss the edges that are pushed while the `DepGraphQuery` is being accessed.
32            // Skip them to issues.
33            if let Some(&Some(target)) = self.dep_index_to_index.get(target) {
34                self.graph.add_edge(source, target, ());
35            }
36        }
37    }
38
39    pub fn nodes(&self) -> Vec<&DepNode> {
40        self.graph.all_nodes().iter().map(|n| &n.data).collect()
41    }
42
43    pub fn edges(&self) -> Vec<(&DepNode, &DepNode)> {
44        self.graph
45            .all_edges()
46            .iter()
47            .map(|edge| (edge.source(), edge.target()))
48            .map(|(s, t)| (self.graph.node_data(s), self.graph.node_data(t)))
49            .collect()
50    }
51
52    fn reachable_nodes(&self, node: &DepNode, direction: Direction) -> Vec<&DepNode> {
53        if let Some(&index) = self.indices.get(node) {
54            self.graph.depth_traverse(index, direction).map(|s| self.graph.node_data(s)).collect()
55        } else {
56            ::alloc::vec::Vec::new()vec![]
57        }
58    }
59
60    /// All nodes that can reach `node`.
61    pub fn transitive_predecessors(&self, node: &DepNode) -> Vec<&DepNode> {
62        self.reachable_nodes(node, INCOMING)
63    }
64}
rustc_middle/dep_graph/query.rs

rustc_middle/dep_graph/
query.rs
