]> git.proxmox.com Git - rustc.git/blame - src/librustc/dep_graph/query.rs
Imported Upstream version 1.9.0+dfsg1
[rustc.git] / src / librustc / dep_graph / query.rs
CommitLineData
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
11use rustc_data_structures::fnv::FnvHashMap;
12use rustc_data_structures::graph::{Graph, NodeIndex};
54a0048b
SL
13use std::fmt::Debug;
14use std::hash::Hash;
9cc50fc6
SL
15
16use super::DepNode;
17
54a0048b
SL
18pub 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
23impl<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}