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> {
74 write!(f, "Edge {{ next_edge: [{:?}, {:?}], source: {:?}, target: {:?}, data: {:?} }}",
75 self.next_edge[0], self.next_edge[1], self.source,
76 self.target, self.data)
80 #[derive(Copy, Clone, PartialEq, Debug)]
81 pub struct NodeIndex(pub usize);
83 #[derive(Copy, Clone, PartialEq, Debug)]
84 pub struct EdgeIndex(pub usize);
86 pub const INVALID_EDGE_INDEX: EdgeIndex = EdgeIndex(usize::MAX);
88 // Use a private field here to guarantee no more instances are created:
89 #[derive(Copy, Clone, Debug)]
90 pub struct Direction { repr: usize }
92 pub const OUTGOING: Direction = Direction { repr: 0 };
94 pub const INCOMING: Direction = Direction { repr: 1 };
97 /// Returns unique id (unique with respect to the graph holding associated node).
98 pub fn node_id(&self) -> usize { self.0 }
102 /// Returns unique id (unique with respect to the graph holding associated edge).
103 pub fn edge_id(&self) -> usize { self.0 }
106 impl<N:Debug,E:Debug> Graph<N,E> {
107 pub fn new() -> Graph<N,E> {
109 nodes: SnapshotVec::new(),
110 edges: SnapshotVec::new(),
114 ///////////////////////////////////////////////////////////////////////////
118 pub fn all_nodes<'a>(&'a self) -> &'a [Node<N>] {
123 pub fn all_edges<'a>(&'a self) -> &'a [Edge<E>] {
127 ///////////////////////////////////////////////////////////////////////////
130 pub fn next_node_index(&self) -> NodeIndex {
131 NodeIndex(self.nodes.len())
134 pub fn add_node(&mut self, data: N) -> NodeIndex {
135 let idx = self.next_node_index();
136 self.nodes.push(Node {
137 first_edge: [INVALID_EDGE_INDEX, INVALID_EDGE_INDEX],
143 pub fn mut_node_data<'a>(&'a mut self, idx: NodeIndex) -> &'a mut N {
144 &mut self.nodes[idx.0].data
147 pub fn node_data<'a>(&'a self, idx: NodeIndex) -> &'a N {
148 &self.nodes[idx.0].data
151 pub fn node<'a>(&'a self, idx: NodeIndex) -> &'a Node<N> {
155 ///////////////////////////////////////////////////////////////////////////
156 // Edge construction and queries
158 pub fn next_edge_index(&self) -> EdgeIndex {
159 EdgeIndex(self.edges.len())
162 pub fn add_edge(&mut self,
165 data: E) -> EdgeIndex {
166 debug!("graph: add_edge({:?}, {:?}, {:?})", source, target, data);
168 let idx = self.next_edge_index();
170 // read current first of the list of edges from each node
171 let source_first = self.nodes[source.0]
172 .first_edge[OUTGOING.repr];
173 let target_first = self.nodes[target.0]
174 .first_edge[INCOMING.repr];
176 // create the new edge, with the previous firsts from each node
177 // as the next pointers
178 self.edges.push(Edge {
179 next_edge: [source_first, target_first],
185 // adjust the firsts for each node target be the next object.
186 self.nodes[source.0].first_edge[OUTGOING.repr] = idx;
187 self.nodes[target.0].first_edge[INCOMING.repr] = idx;
192 pub fn mut_edge_data<'a>(&'a mut self, idx: EdgeIndex) -> &'a mut E {
193 &mut self.edges[idx.0].data
196 pub fn edge_data<'a>(&'a self, idx: EdgeIndex) -> &'a E {
197 &self.edges[idx.0].data
200 pub fn edge<'a>(&'a self, idx: EdgeIndex) -> &'a Edge<E> {
204 pub fn first_adjacent(&self, node: NodeIndex, dir: Direction) -> EdgeIndex {
205 //! Accesses the index of the first edge adjacent to `node`.
206 //! This is useful if you wish to modify the graph while walking
207 //! the linked list of edges.
209 self.nodes[node.0].first_edge[dir.repr]
212 pub fn next_adjacent(&self, edge: EdgeIndex, dir: Direction) -> EdgeIndex {
213 //! Accesses the next edge in a given direction.
214 //! This is useful if you wish to modify the graph while walking
215 //! the linked list of edges.
217 self.edges[edge.0].next_edge[dir.repr]
220 ///////////////////////////////////////////////////////////////////////////
221 // Iterating over nodes, edges
223 pub fn each_node<'a, F>(&'a self, mut f: F) -> bool where
224 F: FnMut(NodeIndex, &'a Node<N>) -> bool,
226 //! Iterates over all edges defined in the graph.
227 self.nodes.iter().enumerate().all(|(i, node)| f(NodeIndex(i), node))
230 pub fn each_edge<'a, F>(&'a self, mut f: F) -> bool where
231 F: FnMut(EdgeIndex, &'a Edge<E>) -> bool,
233 //! Iterates over all edges defined in the graph
234 self.edges.iter().enumerate().all(|(i, edge)| f(EdgeIndex(i), edge))
237 pub fn outgoing_edges(&self, source: NodeIndex) -> AdjacentEdges<N,E> {
238 self.adjacent_edges(source, OUTGOING)
241 pub fn incoming_edges(&self, source: NodeIndex) -> AdjacentEdges<N,E> {
242 self.adjacent_edges(source, INCOMING)
245 pub fn adjacent_edges(&self, source: NodeIndex, direction: Direction) -> AdjacentEdges<N,E> {
246 let first_edge = self.node(source).first_edge[direction.repr];
247 AdjacentEdges { graph: self, direction: direction, next: first_edge }
250 pub fn successor_nodes<'a>(&'a self, source: NodeIndex) -> AdjacentTargets<N,E> {
251 self.outgoing_edges(source).targets()
254 pub fn predecessor_nodes<'a>(&'a self, target: NodeIndex) -> AdjacentSources<N,E> {
255 self.incoming_edges(target).sources()
258 ///////////////////////////////////////////////////////////////////////////
259 // Fixed-point iteration
261 // A common use for graphs in our compiler is to perform
262 // fixed-point iteration. In this case, each edge represents a
263 // constraint, and the nodes themselves are associated with
264 // variables or other bitsets. This method facilitates such a
267 pub fn iterate_until_fixed_point<'a, F>(&'a self, mut op: F) where
268 F: FnMut(usize, EdgeIndex, &'a Edge<E>) -> bool,
270 let mut iteration = 0;
271 let mut changed = true;
275 for (i, edge) in self.edges.iter().enumerate() {
276 changed |= op(iteration, EdgeIndex(i), edge);
281 pub fn depth_traverse<'a>(&'a self, start: NodeIndex) -> DepthFirstTraversal<'a, N, E> {
282 DepthFirstTraversal {
285 visited: BitVector::new(self.nodes.len()),
290 ///////////////////////////////////////////////////////////////////////////
293 pub struct AdjacentEdges<'g,N,E>
296 graph: &'g Graph<N, E>,
297 direction: Direction,
301 impl<'g,N,E> AdjacentEdges<'g,N,E> {
302 fn targets(self) -> AdjacentTargets<'g,N,E> {
303 AdjacentTargets { edges: self }
306 fn sources(self) -> AdjacentSources<'g,N,E> {
307 AdjacentSources { edges: self }
311 impl<'g, N:Debug, E:Debug> Iterator for AdjacentEdges<'g, N, E> {
312 type Item = (EdgeIndex, &'g Edge<E>);
314 fn next(&mut self) -> Option<(EdgeIndex, &'g Edge<E>)> {
315 let edge_index = self.next;
316 if edge_index == INVALID_EDGE_INDEX {
320 let edge = self.graph.edge(edge_index);
321 self.next = edge.next_edge[self.direction.repr];
322 Some((edge_index, edge))
326 pub struct AdjacentTargets<'g,N:'g,E:'g>
329 edges: AdjacentEdges<'g,N,E>,
332 impl<'g, N:Debug, E:Debug> Iterator for AdjacentTargets<'g, N, E> {
333 type Item = NodeIndex;
335 fn next(&mut self) -> Option<NodeIndex> {
336 self.edges.next().map(|(_, edge)| edge.target)
340 pub struct AdjacentSources<'g,N:'g,E:'g>
343 edges: AdjacentEdges<'g,N,E>,
346 impl<'g, N:Debug, E:Debug> Iterator for AdjacentSources<'g, N, E> {
347 type Item = NodeIndex;
349 fn next(&mut self) -> Option<NodeIndex> {
350 self.edges.next().map(|(_, edge)| edge.source)
354 pub struct DepthFirstTraversal<'g, N:'g, E:'g> {
355 graph: &'g Graph<N, E>,
356 stack: Vec<NodeIndex>,
360 impl<'g, N:Debug, E:Debug> Iterator for DepthFirstTraversal<'g, N, E> {
361 type Item = NodeIndex;
363 fn next(&mut self) -> Option<NodeIndex> {
364 while let Some(idx) = self.stack.pop() {
365 if !self.visited.insert(idx.node_id()) {
369 for (_, edge) in self.graph.outgoing_edges(idx) {
370 if !self.visited.contains(edge.target().node_id()) {
371 self.stack.push(edge.target());
382 pub fn each_edge_index<F>(max_edge_index: EdgeIndex, mut f: F) where
383 F: FnMut(EdgeIndex) -> bool,
386 let n = max_edge_index.0;
388 if !f(EdgeIndex(i)) {
396 pub fn source(&self) -> NodeIndex {
400 pub fn target(&self) -> NodeIndex {