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.
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 //! A graph module for use in dataflow, region resolution, and elsewhere.
13 //! # Interface details
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.
21 //! # Implementation details
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`).
33 use bitvec
::BitVector
;
34 use std
::fmt
::{Formatter, Error, Debug}
;
36 use snapshot_vec
::{SnapshotVec, SnapshotVecDelegate}
;
41 pub struct Graph
<N
, E
> {
42 nodes
: SnapshotVec
<Node
<N
>>,
43 edges
: SnapshotVec
<Edge
<E
>>,
47 first_edge
: [EdgeIndex
; 2], // see module comment
52 next_edge
: [EdgeIndex
; 2], // see module comment
58 impl<N
> SnapshotVecDelegate
for Node
<N
> {
62 fn reverse(_
: &mut Vec
<Node
<N
>>, _
: ()) {}
65 impl<N
> SnapshotVecDelegate
for Edge
<N
> {
69 fn reverse(_
: &mut Vec
<Edge
<N
>>, _
: ()) {}
72 impl<E
: Debug
> Debug
for Edge
<E
> {
73 fn fmt(&self, f
: &mut Formatter
) -> Result
<(), Error
> {
75 "Edge {{ next_edge: [{:?}, {:?}], source: {:?}, target: {:?}, data: {:?} }}",
84 #[derive(Copy, Clone, PartialEq, Eq, Debug, Hash)]
85 pub struct NodeIndex(pub usize);
87 #[derive(Copy, Clone, PartialEq, Eq, Debug, Hash)]
88 pub struct EdgeIndex(pub usize);
90 pub const INVALID_EDGE_INDEX
: EdgeIndex
= EdgeIndex(usize::MAX
);
92 // Use a private field here to guarantee no more instances are created:
93 #[derive(Copy, Clone, Debug, PartialEq)]
94 pub struct Direction
{
98 pub const OUTGOING
: Direction
= Direction { repr: 0 }
;
100 pub const INCOMING
: Direction
= Direction { repr: 1 }
;
103 /// Returns unique id (unique with respect to the graph holding associated node).
104 pub fn node_id(&self) -> usize {
110 /// Returns unique id (unique with respect to the graph holding associated edge).
111 pub fn edge_id(&self) -> usize {
116 impl<N
: Debug
, E
: Debug
> Graph
<N
, E
> {
117 pub fn new() -> Graph
<N
, E
> {
119 nodes
: SnapshotVec
::new(),
120 edges
: SnapshotVec
::new(),
124 // # Simple accessors
127 pub fn all_nodes(&self) -> &[Node
<N
>] {
132 pub fn len_nodes(&self) -> usize {
137 pub fn all_edges(&self) -> &[Edge
<E
>] {
142 pub fn len_edges(&self) -> usize {
146 // # Node construction
148 pub fn next_node_index(&self) -> NodeIndex
{
149 NodeIndex(self.nodes
.len())
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
],
161 pub fn mut_node_data(&mut self, idx
: NodeIndex
) -> &mut N
{
162 &mut self.nodes
[idx
.0].data
165 pub fn node_data(&self, idx
: NodeIndex
) -> &N
{
166 &self.nodes
[idx
.0].data
169 pub fn node(&self, idx
: NodeIndex
) -> &Node
<N
> {
173 // # Edge construction and queries
175 pub fn next_edge_index(&self) -> EdgeIndex
{
176 EdgeIndex(self.edges
.len())
179 pub fn add_edge(&mut self, source
: NodeIndex
, target
: NodeIndex
, data
: E
) -> EdgeIndex
{
180 debug
!("graph: add_edge({:?}, {:?}, {:?})", source
, target
, data
);
182 let idx
= self.next_edge_index();
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
];
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
],
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
;
204 pub fn mut_edge_data(&mut self, idx
: EdgeIndex
) -> &mut E
{
205 &mut self.edges
[idx
.0].data
208 pub fn edge_data(&self, idx
: EdgeIndex
) -> &E
{
209 &self.edges
[idx
.0].data
212 pub fn edge(&self, idx
: EdgeIndex
) -> &Edge
<E
> {
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.
221 self.nodes
[node
.0].first_edge
[dir
.repr
]
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.
229 self.edges
[edge
.0].next_edge
[dir
.repr
]
232 // # Iterating over nodes, edges
234 pub fn each_node
<'a
, F
>(&'a
self, mut f
: F
) -> bool
235 where F
: FnMut(NodeIndex
, &'a Node
<N
>) -> bool
237 //! Iterates over all edges defined in the graph.
238 self.nodes
.iter().enumerate().all(|(i
, node
)| f(NodeIndex(i
), node
))
241 pub fn each_edge
<'a
, F
>(&'a
self, mut f
: F
) -> bool
242 where F
: FnMut(EdgeIndex
, &'a Edge
<E
>) -> bool
244 //! Iterates over all edges defined in the graph
245 self.edges
.iter().enumerate().all(|(i
, edge
)| f(EdgeIndex(i
), edge
))
248 pub fn outgoing_edges(&self, source
: NodeIndex
) -> AdjacentEdges
<N
, E
> {
249 self.adjacent_edges(source
, OUTGOING
)
252 pub fn incoming_edges(&self, source
: NodeIndex
) -> AdjacentEdges
<N
, E
> {
253 self.adjacent_edges(source
, INCOMING
)
256 pub fn adjacent_edges(&self, source
: NodeIndex
, direction
: Direction
) -> AdjacentEdges
<N
, E
> {
257 let first_edge
= self.node(source
).first_edge
[direction
.repr
];
260 direction
: direction
,
265 pub fn successor_nodes(&self, source
: NodeIndex
) -> AdjacentTargets
<N
, E
> {
266 self.outgoing_edges(source
).targets()
269 pub fn predecessor_nodes(&self, target
: NodeIndex
) -> AdjacentSources
<N
, E
> {
270 self.incoming_edges(target
).sources()
273 // # Fixed-point iteration
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
281 pub fn iterate_until_fixed_point
<'a
, F
>(&'a
self, mut op
: F
)
282 where F
: FnMut(usize, EdgeIndex
, &'a Edge
<E
>) -> bool
284 let mut iteration
= 0;
285 let mut changed
= true;
289 for (i
, edge
) in self.edges
.iter().enumerate() {
290 changed
|= op(iteration
, EdgeIndex(i
), edge
);
295 pub fn depth_traverse
<'a
>(&'a
self, start
: NodeIndex
) -> DepthFirstTraversal
<'a
, N
, E
> {
296 DepthFirstTraversal
{
299 visited
: BitVector
::new(self.nodes
.len()),
306 pub struct AdjacentEdges
<'g
, N
, E
>
310 graph
: &'g Graph
<N
, E
>,
311 direction
: Direction
,
315 impl<'g
, N
, E
> AdjacentEdges
<'g
, N
, E
> {
316 fn targets(self) -> AdjacentTargets
<'g
, N
, E
> {
317 AdjacentTargets { edges: self }
320 fn sources(self) -> AdjacentSources
<'g
, N
, E
> {
321 AdjacentSources { edges: self }
325 impl<'g
, N
: Debug
, E
: Debug
> Iterator
for AdjacentEdges
<'g
, N
, E
> {
326 type Item
= (EdgeIndex
, &'g Edge
<E
>);
328 fn next(&mut self) -> Option
<(EdgeIndex
, &'g Edge
<E
>)> {
329 let edge_index
= self.next
;
330 if edge_index
== INVALID_EDGE_INDEX
{
334 let edge
= self.graph
.edge(edge_index
);
335 self.next
= edge
.next_edge
[self.direction
.repr
];
336 Some((edge_index
, edge
))
340 pub struct AdjacentTargets
<'g
, N
: 'g
, E
: 'g
>
344 edges
: AdjacentEdges
<'g
, N
, E
>,
347 impl<'g
, N
: Debug
, E
: Debug
> Iterator
for AdjacentTargets
<'g
, N
, E
> {
348 type Item
= NodeIndex
;
350 fn next(&mut self) -> Option
<NodeIndex
> {
351 self.edges
.next().map(|(_
, edge
)| edge
.target
)
355 pub struct AdjacentSources
<'g
, N
: 'g
, E
: 'g
>
359 edges
: AdjacentEdges
<'g
, N
, E
>,
362 impl<'g
, N
: Debug
, E
: Debug
> Iterator
for AdjacentSources
<'g
, N
, E
> {
363 type Item
= NodeIndex
;
365 fn next(&mut self) -> Option
<NodeIndex
> {
366 self.edges
.next().map(|(_
, edge
)| edge
.source
)
370 pub struct DepthFirstTraversal
<'g
, N
: 'g
, E
: 'g
> {
371 graph
: &'g Graph
<N
, E
>,
372 stack
: Vec
<NodeIndex
>,
376 impl<'g
, N
: Debug
, E
: Debug
> Iterator
for DepthFirstTraversal
<'g
, N
, E
> {
377 type Item
= NodeIndex
;
379 fn next(&mut self) -> Option
<NodeIndex
> {
380 while let Some(idx
) = self.stack
.pop() {
381 if !self.visited
.insert(idx
.node_id()) {
385 for (_
, edge
) in self.graph
.outgoing_edges(idx
) {
386 if !self.visited
.contains(edge
.target().node_id()) {
387 self.stack
.push(edge
.target());
398 pub fn each_edge_index
<F
>(max_edge_index
: EdgeIndex
, mut f
: F
)
399 where F
: FnMut(EdgeIndex
) -> bool
402 let n
= max_edge_index
.0;
404 if !f(EdgeIndex(i
)) {
412 pub fn source(&self) -> NodeIndex
{
416 pub fn target(&self) -> NodeIndex
{
420 pub fn source_or_target(&self, direction
: Direction
) -> NodeIndex
{
421 if direction
== OUTGOING
{