]> git.proxmox.com Git - rustc.git/blob - src/librustc_data_structures/graph/mod.rs
Imported Upstream version 1.9.0+dfsg1
[rustc.git] / src / librustc_data_structures / graph / mod.rs
1 // Copyright 2012-2014 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 //! A graph module for use in dataflow, region resolution, and elsewhere.
12 //!
13 //! # Interface details
14 //!
15 //! You customize the graph by specifying a "node data" type `N` and an
16 //! "edge data" type `E`. You can then later gain access (mutable or
17 //! immutable) to these "user-data" bits. Currently, you can only add
18 //! nodes or edges to the graph. You cannot remove or modify them once
19 //! added. This could be changed if we have a need.
20 //!
21 //! # Implementation details
22 //!
23 //! The main tricky thing about this code is the way that edges are
24 //! stored. The edges are stored in a central array, but they are also
25 //! threaded onto two linked lists for each node, one for incoming edges
26 //! and one for outgoing edges. Note that every edge is a member of some
27 //! incoming list and some outgoing list. Basically you can load the
28 //! first index of the linked list from the node data structures (the
29 //! field `first_edge`) and then, for each edge, load the next index from
30 //! the field `next_edge`). Each of those fields is an array that should
31 //! be indexed by the direction (see the type `Direction`).
32
33 use bitvec::BitVector;
34 use std::fmt::{Formatter, Error, Debug};
35 use std::usize;
36 use snapshot_vec::{SnapshotVec, SnapshotVecDelegate};
37
38 #[cfg(test)]
39 mod tests;
40
41 pub struct Graph<N, E> {
42 nodes: SnapshotVec<Node<N>>,
43 edges: SnapshotVec<Edge<E>>,
44 }
45
46 pub struct Node<N> {
47 first_edge: [EdgeIndex; 2], // see module comment
48 pub data: N,
49 }
50
51 pub struct Edge<E> {
52 next_edge: [EdgeIndex; 2], // see module comment
53 source: NodeIndex,
54 target: NodeIndex,
55 pub data: E,
56 }
57
58 impl<N> SnapshotVecDelegate for Node<N> {
59 type Value = Node<N>;
60 type Undo = ();
61
62 fn reverse(_: &mut Vec<Node<N>>, _: ()) {}
63 }
64
65 impl<N> SnapshotVecDelegate for Edge<N> {
66 type Value = Edge<N>;
67 type Undo = ();
68
69 fn reverse(_: &mut Vec<Edge<N>>, _: ()) {}
70 }
71
72 impl<E: Debug> Debug for Edge<E> {
73 fn fmt(&self, f: &mut Formatter) -> Result<(), Error> {
74 write!(f,
75 "Edge {{ next_edge: [{:?}, {:?}], source: {:?}, target: {:?}, data: {:?} }}",
76 self.next_edge[0],
77 self.next_edge[1],
78 self.source,
79 self.target,
80 self.data)
81 }
82 }
83
84 #[derive(Copy, Clone, PartialEq, Eq, Debug, Hash)]
85 pub struct NodeIndex(pub usize);
86
87 #[derive(Copy, Clone, PartialEq, Eq, Debug, Hash)]
88 pub struct EdgeIndex(pub usize);
89
90 pub const INVALID_EDGE_INDEX: EdgeIndex = EdgeIndex(usize::MAX);
91
92 // Use a private field here to guarantee no more instances are created:
93 #[derive(Copy, Clone, Debug, PartialEq)]
94 pub struct Direction {
95 repr: usize,
96 }
97
98 pub const OUTGOING: Direction = Direction { repr: 0 };
99
100 pub const INCOMING: Direction = Direction { repr: 1 };
101
102 impl NodeIndex {
103 /// Returns unique id (unique with respect to the graph holding associated node).
104 pub fn node_id(&self) -> usize {
105 self.0
106 }
107 }
108
109 impl EdgeIndex {
110 /// Returns unique id (unique with respect to the graph holding associated edge).
111 pub fn edge_id(&self) -> usize {
112 self.0
113 }
114 }
115
116 impl<N: Debug, E: Debug> Graph<N, E> {
117 pub fn new() -> Graph<N, E> {
118 Graph {
119 nodes: SnapshotVec::new(),
120 edges: SnapshotVec::new(),
121 }
122 }
123
124 // # Simple accessors
125
126 #[inline]
127 pub fn all_nodes(&self) -> &[Node<N>] {
128 &self.nodes
129 }
130
131 #[inline]
132 pub fn len_nodes(&self) -> usize {
133 self.nodes.len()
134 }
135
136 #[inline]
137 pub fn all_edges(&self) -> &[Edge<E>] {
138 &self.edges
139 }
140
141 #[inline]
142 pub fn len_edges(&self) -> usize {
143 self.edges.len()
144 }
145
146 // # Node construction
147
148 pub fn next_node_index(&self) -> NodeIndex {
149 NodeIndex(self.nodes.len())
150 }
151
152 pub fn add_node(&mut self, data: N) -> NodeIndex {
153 let idx = self.next_node_index();
154 self.nodes.push(Node {
155 first_edge: [INVALID_EDGE_INDEX, INVALID_EDGE_INDEX],
156 data: data,
157 });
158 idx
159 }
160
161 pub fn mut_node_data(&mut self, idx: NodeIndex) -> &mut N {
162 &mut self.nodes[idx.0].data
163 }
164
165 pub fn node_data(&self, idx: NodeIndex) -> &N {
166 &self.nodes[idx.0].data
167 }
168
169 pub fn node(&self, idx: NodeIndex) -> &Node<N> {
170 &self.nodes[idx.0]
171 }
172
173 // # Edge construction and queries
174
175 pub fn next_edge_index(&self) -> EdgeIndex {
176 EdgeIndex(self.edges.len())
177 }
178
179 pub fn add_edge(&mut self, source: NodeIndex, target: NodeIndex, data: E) -> EdgeIndex {
180 debug!("graph: add_edge({:?}, {:?}, {:?})", source, target, data);
181
182 let idx = self.next_edge_index();
183
184 // read current first of the list of edges from each node
185 let source_first = self.nodes[source.0].first_edge[OUTGOING.repr];
186 let target_first = self.nodes[target.0].first_edge[INCOMING.repr];
187
188 // create the new edge, with the previous firsts from each node
189 // as the next pointers
190 self.edges.push(Edge {
191 next_edge: [source_first, target_first],
192 source: source,
193 target: target,
194 data: data,
195 });
196
197 // adjust the firsts for each node target be the next object.
198 self.nodes[source.0].first_edge[OUTGOING.repr] = idx;
199 self.nodes[target.0].first_edge[INCOMING.repr] = idx;
200
201 return idx;
202 }
203
204 pub fn mut_edge_data(&mut self, idx: EdgeIndex) -> &mut E {
205 &mut self.edges[idx.0].data
206 }
207
208 pub fn edge_data(&self, idx: EdgeIndex) -> &E {
209 &self.edges[idx.0].data
210 }
211
212 pub fn edge(&self, idx: EdgeIndex) -> &Edge<E> {
213 &self.edges[idx.0]
214 }
215
216 pub fn first_adjacent(&self, node: NodeIndex, dir: Direction) -> EdgeIndex {
217 //! Accesses the index of the first edge adjacent to `node`.
218 //! This is useful if you wish to modify the graph while walking
219 //! the linked list of edges.
220
221 self.nodes[node.0].first_edge[dir.repr]
222 }
223
224 pub fn next_adjacent(&self, edge: EdgeIndex, dir: Direction) -> EdgeIndex {
225 //! Accesses the next edge in a given direction.
226 //! This is useful if you wish to modify the graph while walking
227 //! the linked list of edges.
228
229 self.edges[edge.0].next_edge[dir.repr]
230 }
231
232 // # Iterating over nodes, edges
233
234 pub fn each_node<'a, F>(&'a self, mut f: F) -> bool
235 where F: FnMut(NodeIndex, &'a Node<N>) -> bool
236 {
237 //! Iterates over all edges defined in the graph.
238 self.nodes.iter().enumerate().all(|(i, node)| f(NodeIndex(i), node))
239 }
240
241 pub fn each_edge<'a, F>(&'a self, mut f: F) -> bool
242 where F: FnMut(EdgeIndex, &'a Edge<E>) -> bool
243 {
244 //! Iterates over all edges defined in the graph
245 self.edges.iter().enumerate().all(|(i, edge)| f(EdgeIndex(i), edge))
246 }
247
248 pub fn outgoing_edges(&self, source: NodeIndex) -> AdjacentEdges<N, E> {
249 self.adjacent_edges(source, OUTGOING)
250 }
251
252 pub fn incoming_edges(&self, source: NodeIndex) -> AdjacentEdges<N, E> {
253 self.adjacent_edges(source, INCOMING)
254 }
255
256 pub fn adjacent_edges(&self, source: NodeIndex, direction: Direction) -> AdjacentEdges<N, E> {
257 let first_edge = self.node(source).first_edge[direction.repr];
258 AdjacentEdges {
259 graph: self,
260 direction: direction,
261 next: first_edge,
262 }
263 }
264
265 pub fn successor_nodes(&self, source: NodeIndex) -> AdjacentTargets<N, E> {
266 self.outgoing_edges(source).targets()
267 }
268
269 pub fn predecessor_nodes(&self, target: NodeIndex) -> AdjacentSources<N, E> {
270 self.incoming_edges(target).sources()
271 }
272
273 // # Fixed-point iteration
274 //
275 // A common use for graphs in our compiler is to perform
276 // fixed-point iteration. In this case, each edge represents a
277 // constraint, and the nodes themselves are associated with
278 // variables or other bitsets. This method facilitates such a
279 // computation.
280
281 pub fn iterate_until_fixed_point<'a, F>(&'a self, mut op: F)
282 where F: FnMut(usize, EdgeIndex, &'a Edge<E>) -> bool
283 {
284 let mut iteration = 0;
285 let mut changed = true;
286 while changed {
287 changed = false;
288 iteration += 1;
289 for (i, edge) in self.edges.iter().enumerate() {
290 changed |= op(iteration, EdgeIndex(i), edge);
291 }
292 }
293 }
294
295 pub fn depth_traverse<'a>(&'a self, start: NodeIndex) -> DepthFirstTraversal<'a, N, E> {
296 DepthFirstTraversal {
297 graph: self,
298 stack: vec![start],
299 visited: BitVector::new(self.nodes.len()),
300 }
301 }
302 }
303
304 // # Iterators
305
306 pub struct AdjacentEdges<'g, N, E>
307 where N: 'g,
308 E: 'g
309 {
310 graph: &'g Graph<N, E>,
311 direction: Direction,
312 next: EdgeIndex,
313 }
314
315 impl<'g, N, E> AdjacentEdges<'g, N, E> {
316 fn targets(self) -> AdjacentTargets<'g, N, E> {
317 AdjacentTargets { edges: self }
318 }
319
320 fn sources(self) -> AdjacentSources<'g, N, E> {
321 AdjacentSources { edges: self }
322 }
323 }
324
325 impl<'g, N: Debug, E: Debug> Iterator for AdjacentEdges<'g, N, E> {
326 type Item = (EdgeIndex, &'g Edge<E>);
327
328 fn next(&mut self) -> Option<(EdgeIndex, &'g Edge<E>)> {
329 let edge_index = self.next;
330 if edge_index == INVALID_EDGE_INDEX {
331 return None;
332 }
333
334 let edge = self.graph.edge(edge_index);
335 self.next = edge.next_edge[self.direction.repr];
336 Some((edge_index, edge))
337 }
338 }
339
340 pub struct AdjacentTargets<'g, N: 'g, E: 'g>
341 where N: 'g,
342 E: 'g
343 {
344 edges: AdjacentEdges<'g, N, E>,
345 }
346
347 impl<'g, N: Debug, E: Debug> Iterator for AdjacentTargets<'g, N, E> {
348 type Item = NodeIndex;
349
350 fn next(&mut self) -> Option<NodeIndex> {
351 self.edges.next().map(|(_, edge)| edge.target)
352 }
353 }
354
355 pub struct AdjacentSources<'g, N: 'g, E: 'g>
356 where N: 'g,
357 E: 'g
358 {
359 edges: AdjacentEdges<'g, N, E>,
360 }
361
362 impl<'g, N: Debug, E: Debug> Iterator for AdjacentSources<'g, N, E> {
363 type Item = NodeIndex;
364
365 fn next(&mut self) -> Option<NodeIndex> {
366 self.edges.next().map(|(_, edge)| edge.source)
367 }
368 }
369
370 pub struct DepthFirstTraversal<'g, N: 'g, E: 'g> {
371 graph: &'g Graph<N, E>,
372 stack: Vec<NodeIndex>,
373 visited: BitVector,
374 }
375
376 impl<'g, N: Debug, E: Debug> Iterator for DepthFirstTraversal<'g, N, E> {
377 type Item = NodeIndex;
378
379 fn next(&mut self) -> Option<NodeIndex> {
380 while let Some(idx) = self.stack.pop() {
381 if !self.visited.insert(idx.node_id()) {
382 continue;
383 }
384
385 for (_, edge) in self.graph.outgoing_edges(idx) {
386 if !self.visited.contains(edge.target().node_id()) {
387 self.stack.push(edge.target());
388 }
389 }
390
391 return Some(idx);
392 }
393
394 return None;
395 }
396 }
397
398 pub fn each_edge_index<F>(max_edge_index: EdgeIndex, mut f: F)
399 where F: FnMut(EdgeIndex) -> bool
400 {
401 let mut i = 0;
402 let n = max_edge_index.0;
403 while i < n {
404 if !f(EdgeIndex(i)) {
405 return;
406 }
407 i += 1;
408 }
409 }
410
411 impl<E> Edge<E> {
412 pub fn source(&self) -> NodeIndex {
413 self.source
414 }
415
416 pub fn target(&self) -> NodeIndex {
417 self.target
418 }
419
420 pub fn source_or_target(&self, direction: Direction) -> NodeIndex {
421 if direction == OUTGOING {
422 self.target
423 } else {
424 self.source
425 }
426 }
427 }