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
   4 use super::{DepKind, DepNode};
   5
   6 pub struct DepGraphQuery<K> {
   7     pub graph: Graph<DepNode<K>, ()>,
   8     pub indices: FxHashMap<DepNode<K>, NodeIndex>,
   9 }
  10
  11 impl<K: DepKind> DepGraphQuery<K> {
  12     pub fn new(
  13         nodes: &[DepNode<K>],
  14         edge_list_indices: &[(usize, usize)],
  15         edge_list_data: &[usize],
  16     ) -> DepGraphQuery<K> {
  17         let mut graph = Graph::with_capacity(nodes.len(), edge_list_data.len());
  18         let mut indices = FxHashMap::default();
  19         for node in nodes {
  20             indices.insert(*node, graph.add_node(*node));
  21         }
  22
  23         for (source, &(start, end)) in edge_list_indices.iter().enumerate() {
  24             for &target in &edge_list_data[start..end] {
  25                 let source = indices[&nodes[source]];
  26                 let target = indices[&nodes[target]];
  27                 graph.add_edge(source, target, ());
  28             }
  29         }
  30
  31         DepGraphQuery { graph, indices }
  32     }
  33
  34     pub fn nodes(&self) -> Vec<&DepNode<K>> {
  35         self.graph.all_nodes().iter().map(|n| &n.data).collect()
  36     }
  37
  38     pub fn edges(&self) -> Vec<(&DepNode<K>, &DepNode<K>)> {
  39         self.graph
  40             .all_edges()
  41             .iter()
  42             .map(|edge| (edge.source(), edge.target()))
  43             .map(|(s, t)| (self.graph.node_data(s), self.graph.node_data(t)))
  44             .collect()
  45     }
  46
  47     fn reachable_nodes(&self, node: &DepNode<K>, direction: Direction) -> Vec<&DepNode<K>> {
  48         if let Some(&index) = self.indices.get(node) {
  49             self.graph.depth_traverse(index, direction).map(|s| self.graph.node_data(s)).collect()
  50         } else {
  51             vec![]
  52         }
  53     }
  54
  55     /// All nodes that can reach `node`.
  56     pub fn transitive_predecessors(&self, node: &DepNode<K>) -> Vec<&DepNode<K>> {
  57         self.reachable_nodes(node, INCOMING)
  58     }
  59 }