]>
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, FnvHashSet}; | |
54a0048b SL |
12 | use std::fmt::Debug; |
13 | use std::hash::Hash; | |
9cc50fc6 SL |
14 | use super::{DepGraphQuery, DepNode}; |
15 | ||
54a0048b SL |
16 | pub struct DepGraphEdges<D: Clone + Debug + Eq + Hash> { |
17 | nodes: Vec<DepNode<D>>, | |
18 | indices: FnvHashMap<DepNode<D>, IdIndex>, | |
9cc50fc6 SL |
19 | edges: FnvHashSet<(IdIndex, IdIndex)>, |
20 | open_nodes: Vec<OpenNode>, | |
21 | } | |
22 | ||
23 | #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)] | |
24 | struct IdIndex { | |
25 | index: u32 | |
26 | } | |
27 | ||
28 | impl IdIndex { | |
29 | fn new(v: usize) -> IdIndex { | |
30 | assert!((v & 0xFFFF_FFFF) == v); | |
31 | IdIndex { index: v as u32 } | |
32 | } | |
33 | ||
34 | fn index(self) -> usize { | |
35 | self.index as usize | |
36 | } | |
37 | } | |
38 | ||
39 | #[derive(Clone, Debug, PartialEq)] | |
40 | enum OpenNode { | |
41 | Node(IdIndex), | |
42 | Ignore, | |
43 | } | |
44 | ||
54a0048b SL |
45 | impl<D: Clone + Debug + Eq + Hash> DepGraphEdges<D> { |
46 | pub fn new() -> DepGraphEdges<D> { | |
9cc50fc6 SL |
47 | DepGraphEdges { |
48 | nodes: vec![], | |
49 | indices: FnvHashMap(), | |
50 | edges: FnvHashSet(), | |
51 | open_nodes: Vec::new() | |
52 | } | |
53 | } | |
54 | ||
54a0048b SL |
55 | fn id(&self, index: IdIndex) -> DepNode<D> { |
56 | self.nodes[index.index()].clone() | |
9cc50fc6 SL |
57 | } |
58 | ||
59 | /// Creates a node for `id` in the graph. | |
54a0048b | 60 | fn make_node(&mut self, id: DepNode<D>) -> IdIndex { |
9cc50fc6 SL |
61 | if let Some(&i) = self.indices.get(&id) { |
62 | return i; | |
63 | } | |
64 | ||
65 | let index = IdIndex::new(self.nodes.len()); | |
66 | self.nodes.push(id.clone()); | |
67 | self.indices.insert(id, index); | |
68 | index | |
69 | } | |
70 | ||
71 | /// Top of the stack of open nodes. | |
72 | fn current_node(&self) -> Option<OpenNode> { | |
73 | self.open_nodes.last().cloned() | |
74 | } | |
75 | ||
76 | pub fn push_ignore(&mut self) { | |
77 | self.open_nodes.push(OpenNode::Ignore); | |
78 | } | |
79 | ||
80 | pub fn pop_ignore(&mut self) { | |
81 | let popped_node = self.open_nodes.pop().unwrap(); | |
82 | assert_eq!(popped_node, OpenNode::Ignore); | |
83 | } | |
84 | ||
54a0048b | 85 | pub fn push_task(&mut self, key: DepNode<D>) { |
9cc50fc6 SL |
86 | let top_node = self.current_node(); |
87 | ||
88 | let new_node = self.make_node(key); | |
89 | self.open_nodes.push(OpenNode::Node(new_node)); | |
90 | ||
91 | // if we are in the midst of doing task T, then this new task | |
92 | // N is a subtask of T, so add an edge N -> T. | |
93 | if let Some(top_node) = top_node { | |
94 | self.add_edge_from_open_node(top_node, |t| (new_node, t)); | |
95 | } | |
96 | } | |
97 | ||
54a0048b | 98 | pub fn pop_task(&mut self, key: DepNode<D>) { |
9cc50fc6 SL |
99 | let popped_node = self.open_nodes.pop().unwrap(); |
100 | assert_eq!(OpenNode::Node(self.indices[&key]), popped_node); | |
101 | } | |
102 | ||
103 | /// Indicates that the current task `C` reads `v` by adding an | |
104 | /// edge from `v` to `C`. If there is no current task, panics. If | |
105 | /// you want to suppress this edge, use `ignore`. | |
54a0048b | 106 | pub fn read(&mut self, v: DepNode<D>) { |
9cc50fc6 SL |
107 | let source = self.make_node(v); |
108 | self.add_edge_from_current_node(|current| (source, current)) | |
109 | } | |
110 | ||
111 | /// Indicates that the current task `C` writes `v` by adding an | |
112 | /// edge from `C` to `v`. If there is no current task, panics. If | |
113 | /// you want to suppress this edge, use `ignore`. | |
54a0048b | 114 | pub fn write(&mut self, v: DepNode<D>) { |
9cc50fc6 SL |
115 | let target = self.make_node(v); |
116 | self.add_edge_from_current_node(|current| (current, target)) | |
117 | } | |
118 | ||
119 | /// Invoke `add_edge_from_open_node` with the top of the stack, or | |
120 | /// panic if stack is empty. | |
121 | fn add_edge_from_current_node<OP>(&mut self, | |
122 | op: OP) | |
123 | where OP: FnOnce(IdIndex) -> (IdIndex, IdIndex) | |
124 | { | |
125 | match self.current_node() { | |
126 | Some(open_node) => self.add_edge_from_open_node(open_node, op), | |
54a0048b | 127 | None => bug!("no current node, cannot add edge into dependency graph") |
9cc50fc6 SL |
128 | } |
129 | } | |
130 | ||
131 | /// Adds an edge to or from the `open_node`, assuming `open_node` | |
132 | /// is not `Ignore`. The direction of the edge is determined by | |
133 | /// the closure `op` --- we pass as argument the open node `n`, | |
134 | /// and the closure returns a (source, target) tuple, which should | |
135 | /// include `n` in one spot or another. | |
136 | fn add_edge_from_open_node<OP>(&mut self, | |
137 | open_node: OpenNode, | |
138 | op: OP) | |
139 | where OP: FnOnce(IdIndex) -> (IdIndex, IdIndex) | |
140 | { | |
141 | let (source, target) = match open_node { | |
142 | OpenNode::Node(n) => op(n), | |
143 | OpenNode::Ignore => { return; } | |
144 | }; | |
145 | ||
146 | // ignore trivial self edges, which are not very interesting | |
147 | if source == target { | |
148 | return; | |
149 | } | |
150 | ||
151 | if self.edges.insert((source, target)) { | |
152 | debug!("adding edge from {:?} to {:?}", | |
153 | self.id(source), | |
154 | self.id(target)); | |
155 | } | |
156 | } | |
157 | ||
54a0048b | 158 | pub fn query(&self) -> DepGraphQuery<D> { |
9cc50fc6 SL |
159 | let edges: Vec<_> = self.edges.iter() |
160 | .map(|&(i, j)| (self.id(i), self.id(j))) | |
161 | .collect(); | |
162 | DepGraphQuery::new(&self.nodes, &edges) | |
163 | } | |
164 | } |