]> git.proxmox.com Git - rustc.git/blame - src/librustc/dep_graph/edges.rs
Imported Upstream version 1.9.0+dfsg1
[rustc.git] / src / librustc / dep_graph / edges.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, FnvHashSet};
54a0048b
SL
12use std::fmt::Debug;
13use std::hash::Hash;
9cc50fc6
SL
14use super::{DepGraphQuery, DepNode};
15
54a0048b
SL
16pub 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)]
24struct IdIndex {
25 index: u32
26}
27
28impl 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)]
40enum OpenNode {
41 Node(IdIndex),
42 Ignore,
43}
44
54a0048b
SL
45impl<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}