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