compiler/rustc_query_system/src/dep_graph/query.rs

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