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.
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.
11 use rustc_data_structures::fx::{FxHashMap, FxHashSet};
12 use super::{DepGraphQuery, DepNode};
14 pub struct DepGraphEdges {
16 indices: FxHashMap<DepNode, IdIndex>,
17 edges: FxHashSet<(IdIndex, IdIndex)>,
18 open_nodes: Vec<OpenNode>,
21 #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
27 fn new(v: usize) -> IdIndex {
28 assert!((v & 0xFFFF_FFFF) == v);
29 IdIndex { index: v as u32 }
32 fn index(self) -> usize {
37 #[derive(Clone, Debug, PartialEq)]
44 pub fn new() -> DepGraphEdges {
49 open_nodes: Vec::new()
53 fn id(&self, index: IdIndex) -> DepNode {
54 self.nodes[index.index()].clone()
57 /// Creates a node for `id` in the graph.
58 fn make_node(&mut self, id: DepNode) -> IdIndex {
59 if let Some(&i) = self.indices.get(&id) {
63 let index = IdIndex::new(self.nodes.len());
64 self.nodes.push(id.clone());
65 self.indices.insert(id, index);
69 /// Top of the stack of open nodes.
70 fn current_node(&self) -> Option<OpenNode> {
71 self.open_nodes.last().cloned()
74 pub fn push_ignore(&mut self) {
75 self.open_nodes.push(OpenNode::Ignore);
78 pub fn pop_ignore(&mut self) {
79 let popped_node = self.open_nodes.pop().unwrap();
80 assert_eq!(popped_node, OpenNode::Ignore);
83 pub fn push_task(&mut self, key: DepNode) {
84 let top_node = self.current_node();
86 let new_node = self.make_node(key);
87 self.open_nodes.push(OpenNode::Node(new_node));
89 // if we are in the midst of doing task T, then this new task
90 // N is a subtask of T, so add an edge N -> T.
91 if let Some(top_node) = top_node {
92 self.add_edge_from_open_node(top_node, |t| (new_node, t));
96 pub fn pop_task(&mut self, key: DepNode) {
97 let popped_node = self.open_nodes.pop().unwrap();
98 assert_eq!(OpenNode::Node(self.indices[&key]), popped_node);
101 /// Indicates that the current task `C` reads `v` by adding an
102 /// edge from `v` to `C`. If there is no current task, has no
103 /// effect. Note that *reading* from tracked state is harmless if
104 /// you are not in a task; what is bad is *writing* to tracked
105 /// state (and leaking data that you read into a tracked task).
106 pub fn read(&mut self, v: DepNode) {
107 if self.current_node().is_some() {
108 let source = self.make_node(v);
109 self.add_edge_from_current_node(|current| (source, current))
113 /// Indicates that the current task `C` writes `v` by adding an
114 /// edge from `C` to `v`. If there is no current task, panics. If
115 /// you want to suppress this edge, use `ignore`.
116 pub fn write(&mut self, v: DepNode) {
117 let target = self.make_node(v);
118 self.add_edge_from_current_node(|current| (current, target))
121 /// Invoke `add_edge_from_open_node` with the top of the stack, or
122 /// panic if stack is empty.
123 fn add_edge_from_current_node<OP>(&mut self,
125 where OP: FnOnce(IdIndex) -> (IdIndex, IdIndex)
127 match self.current_node() {
128 Some(open_node) => self.add_edge_from_open_node(open_node, op),
129 None => bug!("no current node, cannot add edge into dependency graph")
133 /// Adds an edge to or from the `open_node`, assuming `open_node`
134 /// is not `Ignore`. The direction of the edge is determined by
135 /// the closure `op` --- we pass as argument the open node `n`,
136 /// and the closure returns a (source, target) tuple, which should
137 /// include `n` in one spot or another.
138 fn add_edge_from_open_node<OP>(&mut self,
141 where OP: FnOnce(IdIndex) -> (IdIndex, IdIndex)
143 let (source, target) = match open_node {
144 OpenNode::Node(n) => op(n),
145 OpenNode::Ignore => { return; }
148 // ignore trivial self edges, which are not very interesting
149 if source == target {
153 if self.edges.insert((source, target)) {
154 debug!("adding edge from {:?} to {:?}",
160 pub fn query(&self) -> DepGraphQuery {
161 let edges: Vec<_> = self.edges.iter()
162 .map(|&(i, j)| (self.id(i), self.id(j)))
164 DepGraphQuery::new(&self.nodes, &edges)