src/librustc/dep_graph/query.rs

   1 use rustc_data_structures::fx::FxHashMap;
   2 use rustc_data_structures::graph::implementation::{
   3     Direction, INCOMING, Graph, NodeIndex, 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],
  15                edges: &[(DepNode, DepNode)])
  16                -> DepGraphQuery {
  17         let mut graph = Graph::with_capacity(nodes.len(), edges.len());
  18         let mut indices = FxHashMap::default();
  19         for node in nodes {
  20             indices.insert(node.clone(), graph.add_node(node.clone()));
  21         }
  22
  23         for &(ref source, ref target) in edges {
  24             let source = indices[source];
  25             let target = indices[target];
  26             graph.add_edge(source, target, ());
  27         }
  28
  29         DepGraphQuery {
  30             graph,
  31             indices,
  32         }
  33     }
  34
  35     pub fn contains_node(&self, node: &DepNode) -> bool {
  36         self.indices.contains_key(&node)
  37     }
  38
  39     pub fn nodes(&self) -> Vec<&DepNode> {
  40         self.graph.all_nodes()
  41                   .iter()
  42                   .map(|n| &n.data)
  43                   .collect()
  44     }
  45
  46     pub fn edges(&self) -> Vec<(&DepNode,&DepNode)> {
  47         self.graph.all_edges()
  48                   .iter()
  49                   .map(|edge| (edge.source(), edge.target()))
  50                   .map(|(s, t)| (self.graph.node_data(s),
  51                                  self.graph.node_data(t)))
  52                   .collect()
  53     }
  54
  55     fn reachable_nodes(&self, node: &DepNode, direction: Direction) -> Vec<&DepNode> {
  56         if let Some(&index) = self.indices.get(node) {
  57             self.graph.depth_traverse(index, direction)
  58                       .map(|s| self.graph.node_data(s))
  59                       .collect()
  60         } else {
  61             vec![]
  62         }
  63     }
  64
  65     /// All nodes reachable from `node`. In other words, things that
  66     /// will have to be recomputed if `node` changes.
  67     pub fn transitive_successors(&self, node: &DepNode) -> Vec<&DepNode> {
  68         self.reachable_nodes(node, OUTGOING)
  69     }
  70
  71     /// All nodes that can reach `node`.
  72     pub fn transitive_predecessors(&self, node: &DepNode) -> Vec<&DepNode> {
  73         self.reachable_nodes(node, INCOMING)
  74     }
  75
  76     /// Just the outgoing edges from `node`.
  77     pub fn immediate_successors(&self, node: &DepNode) -> Vec<&DepNode> {
  78         if let Some(&index) = self.indices.get(&node) {
  79             self.graph.successor_nodes(index)
  80                       .map(|s| self.graph.node_data(s))
  81                       .collect()
  82         } else {
  83             vec![]
  84         }
  85     }
  86 }