]>
Commit | Line | Data |
---|---|---|
9cc50fc6 SL |
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::fnv::FnvHashMap; | |
12 | use rustc_data_structures::graph::{Graph, NodeIndex}; | |
54a0048b SL |
13 | use std::fmt::Debug; |
14 | use std::hash::Hash; | |
9cc50fc6 SL |
15 | |
16 | use super::DepNode; | |
17 | ||
54a0048b SL |
18 | pub struct DepGraphQuery<D: Clone + Debug + Hash + Eq> { |
19 | pub graph: Graph<DepNode<D>, ()>, | |
20 | pub indices: FnvHashMap<DepNode<D>, NodeIndex>, | |
9cc50fc6 SL |
21 | } |
22 | ||
54a0048b SL |
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> { | |
9cc50fc6 SL |
27 | let mut graph = Graph::new(); |
28 | let mut indices = FnvHashMap(); | |
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 | ||
54a0048b SL |
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>> { | |
9cc50fc6 SL |
51 | self.graph.all_nodes() |
52 | .iter() | |
53 | .map(|n| n.data.clone()) | |
54 | .collect() | |
55 | } | |
56 | ||
54a0048b | 57 | pub fn edges(&self) -> Vec<(DepNode<D>,DepNode<D>)> { |
9cc50fc6 SL |
58 | self.graph.all_edges() |
59 | .iter() | |
60 | .map(|edge| (edge.source(), edge.target())) | |
54a0048b SL |
61 | .map(|(s, t)| (self.graph.node_data(s).clone(), |
62 | self.graph.node_data(t).clone())) | |
9cc50fc6 SL |
63 | .collect() |
64 | } | |
65 | ||
66 | /// All nodes reachable from `node`. In other words, things that | |
67 | /// will have to be recomputed if `node` changes. | |
54a0048b | 68 | pub fn transitive_dependents(&self, node: DepNode<D>) -> Vec<DepNode<D>> { |
9cc50fc6 SL |
69 | if let Some(&index) = self.indices.get(&node) { |
70 | self.graph.depth_traverse(index) | |
54a0048b SL |
71 | .map(|s| self.graph.node_data(s).clone()) |
72 | .collect() | |
73 | } else { | |
74 | vec![] | |
75 | } | |
76 | } | |
77 | ||
78 | /// Just the outgoing edges from `node`. | |
79 | pub fn immediate_dependents(&self, node: DepNode<D>) -> Vec<DepNode<D>> { | |
80 | if let Some(&index) = self.indices.get(&node) { | |
81 | self.graph.successor_nodes(index) | |
82 | .map(|s| self.graph.node_data(s).clone()) | |
9cc50fc6 SL |
83 | .collect() |
84 | } else { | |
85 | vec![] | |
86 | } | |
87 | } | |
88 | } |