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