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