src/librustc/dep_graph/query.rs

   1 // Copyright 2012-2015 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 use rustc_data_structures::fx::FxHashMap;
  12 use rustc_data_structures::graph::{Direction, INCOMING, Graph, NodeIndex, OUTGOING};
  13
  14 use super::DepNode;
  15
  16 pub struct DepGraphQuery {
  17     pub graph: Graph<DepNode, ()>,
  18     pub indices: FxHashMap<DepNode, NodeIndex>,
  19 }
  20
  21 impl DepGraphQuery {
  22     pub fn new(nodes: &[DepNode],
  23                edges: &[(DepNode, DepNode)])
  24                -> DepGraphQuery {
  25         let mut graph = Graph::new();
  26         let mut indices = FxHashMap();
  27         for node in nodes {
  28             indices.insert(node.clone(), graph.next_node_index());
  29             graph.add_node(node.clone());
  30         }
  31
  32         for &(ref source, ref target) in edges {
  33             let source = indices[source];
  34             let target = indices[target];
  35             graph.add_edge(source, target, ());
  36         }
  37
  38         DepGraphQuery {
  39             graph,
  40             indices,
  41         }
  42     }
  43
  44     pub fn contains_node(&self, node: &DepNode) -> bool {
  45         self.indices.contains_key(&node)
  46     }
  47
  48     pub fn nodes(&self) -> Vec<&DepNode> {
  49         self.graph.all_nodes()
  50                   .iter()
  51                   .map(|n| &n.data)
  52                   .collect()
  53     }
  54
  55     pub fn edges(&self) -> Vec<(&DepNode,&DepNode)> {
  56         self.graph.all_edges()
  57                   .iter()
  58                   .map(|edge| (edge.source(), edge.target()))
  59                   .map(|(s, t)| (self.graph.node_data(s),
  60                                  self.graph.node_data(t)))
  61                   .collect()
  62     }
  63
  64     fn reachable_nodes(&self, node: &DepNode, direction: Direction) -> Vec<&DepNode> {
  65         if let Some(&index) = self.indices.get(node) {
  66             self.graph.depth_traverse(index, direction)
  67                       .map(|s| self.graph.node_data(s))
  68                       .collect()
  69         } else {
  70             vec![]
  71         }
  72     }
  73
  74     /// All nodes reachable from `node`. In other words, things that
  75     /// will have to be recomputed if `node` changes.
  76     pub fn transitive_successors(&self, node: &DepNode) -> Vec<&DepNode> {
  77         self.reachable_nodes(node, OUTGOING)
  78     }
  79
  80     /// All nodes that can reach `node`.
  81     pub fn transitive_predecessors(&self, node: &DepNode) -> Vec<&DepNode> {
  82         self.reachable_nodes(node, INCOMING)
  83     }
  84
  85     /// Just the outgoing edges from `node`.
  86     pub fn immediate_successors(&self, node: &DepNode) -> Vec<&DepNode> {
  87         if let Some(&index) = self.indices.get(&node) {
  88             self.graph.successor_nodes(index)
  89                       .map(|s| self.graph.node_data(s))
  90                       .collect()
  91         } else {
  92             vec![]
  93         }
  94     }
  95 }