src/librustc/dep_graph/query.rs

   1 use rustc_data_structures::fx::FxHashMap;
   2 use rustc_data_structures::graph::implementation::{
   3     Direction, Graph, NodeIndex, INCOMING, OUTGOING,
   4 };
   5
   6 use super::DepNode;
   7
   8 pub struct DepGraphQuery {
   9     pub graph: Graph<DepNode, ()>,
  10     pub indices: FxHashMap<DepNode, NodeIndex>,
  11 }
  12
  13 impl DepGraphQuery {
  14     pub fn new(nodes: &[DepNode], edges: &[(DepNode, DepNode)]) -> DepGraphQuery {
  15         let mut graph = Graph::with_capacity(nodes.len(), edges.len());
  16         let mut indices = FxHashMap::default();
  17         for node in nodes {
  18             indices.insert(node.clone(), graph.add_node(node.clone()));
  19         }
  20
  21         for &(ref source, ref target) in edges {
  22             let source = indices[source];
  23             let target = indices[target];
  24             graph.add_edge(source, target, ());
  25         }
  26
  27         DepGraphQuery { graph, indices }
  28     }
  29
  30     pub fn contains_node(&self, node: &DepNode) -> bool {
  31         self.indices.contains_key(&node)
  32     }
  33
  34     pub fn nodes(&self) -> Vec<&DepNode> {
  35         self.graph.all_nodes().iter().map(|n| &n.data).collect()
  36     }
  37
  38     pub fn edges(&self) -> Vec<(&DepNode, &DepNode)> {
  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, direction: Direction) -> Vec<&DepNode> {
  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 reachable from `node`. In other words, things that
  56     /// will have to be recomputed if `node` changes.
  57     pub fn transitive_successors(&self, node: &DepNode) -> Vec<&DepNode> {
  58         self.reachable_nodes(node, OUTGOING)
  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
  66     /// Just the outgoing edges from `node`.
  67     pub fn immediate_successors(&self, node: &DepNode) -> Vec<&DepNode> {
  68         if let Some(&index) = self.indices.get(&node) {
  69             self.graph.successor_nodes(index).map(|s| self.graph.node_data(s)).collect()
  70         } else {
  71             vec![]
  72         }
  73     }
  74 }