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, "Edge {{ next_edge: [{:?}, {:?}], source: {:?}, target: {:?}, data: {:?} }}",
  75                self.next_edge[0], self.next_edge[1], self.source,
  76                self.target, self.data)
  77     }
  78 }
  79
  80 #[derive(Copy, Clone, PartialEq, Debug)]
  81 pub struct NodeIndex(pub usize);
  82
  83 #[derive(Copy, Clone, PartialEq, Debug)]
  84 pub struct EdgeIndex(pub usize);
  85
  86 pub const INVALID_EDGE_INDEX: EdgeIndex = EdgeIndex(usize::MAX);
  87
  88 // Use a private field here to guarantee no more instances are created:
  89 #[derive(Copy, Clone, Debug)]
  90 pub struct Direction { repr: usize }
  91
  92 pub const OUTGOING: Direction = Direction { repr: 0 };
  93
  94 pub const INCOMING: Direction = Direction { repr: 1 };
  95
  96 impl NodeIndex {
  97     /// Returns unique id (unique with respect to the graph holding associated node).
  98     pub fn node_id(&self) -> usize { self.0 }
  99 }
 100
 101 impl EdgeIndex {
 102     /// Returns unique id (unique with respect to the graph holding associated edge).
 103     pub fn edge_id(&self) -> usize { self.0 }
 104 }
 105
 106 impl<N:Debug,E:Debug> Graph<N,E> {
 107     pub fn new() -> Graph<N,E> {
 108         Graph {
 109             nodes: SnapshotVec::new(),
 110             edges: SnapshotVec::new(),
 111         }
 112     }
 113
 114     ///////////////////////////////////////////////////////////////////////////
 115     // Simple accessors
 116
 117     #[inline]
 118     pub fn all_nodes<'a>(&'a self) -> &'a [Node<N>] {
 119         &self.nodes
 120     }
 121
 122     #[inline]
 123     pub fn all_edges<'a>(&'a self) -> &'a [Edge<E>] {
 124         &self.edges
 125     }
 126
 127     ///////////////////////////////////////////////////////////////////////////
 128     // Node construction
 129
 130     pub fn next_node_index(&self) -> NodeIndex {
 131         NodeIndex(self.nodes.len())
 132     }
 133
 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],
 138             data: data
 139         });
 140         idx
 141     }
 142
 143     pub fn mut_node_data<'a>(&'a mut self, idx: NodeIndex) -> &'a mut N {
 144         &mut self.nodes[idx.0].data
 145     }
 146
 147     pub fn node_data<'a>(&'a self, idx: NodeIndex) -> &'a N {
 148         &self.nodes[idx.0].data
 149     }
 150
 151     pub fn node<'a>(&'a self, idx: NodeIndex) -> &'a Node<N> {
 152         &self.nodes[idx.0]
 153     }
 154
 155     ///////////////////////////////////////////////////////////////////////////
 156     // Edge construction and queries
 157
 158     pub fn next_edge_index(&self) -> EdgeIndex {
 159         EdgeIndex(self.edges.len())
 160     }
 161
 162     pub fn add_edge(&mut self,
 163                     source: NodeIndex,
 164                     target: NodeIndex,
 165                     data: E) -> EdgeIndex {
 166         debug!("graph: add_edge({:?}, {:?}, {:?})", source, target, data);
 167
 168         let idx = self.next_edge_index();
 169
 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];
 175
 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],
 180             source: source,
 181             target: target,
 182             data: data
 183         });
 184
 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;
 188
 189         return idx;
 190     }
 191
 192     pub fn mut_edge_data<'a>(&'a mut self, idx: EdgeIndex) -> &'a mut E {
 193         &mut self.edges[idx.0].data
 194     }
 195
 196     pub fn edge_data<'a>(&'a self, idx: EdgeIndex) -> &'a E {
 197         &self.edges[idx.0].data
 198     }
 199
 200     pub fn edge<'a>(&'a self, idx: EdgeIndex) -> &'a Edge<E> {
 201         &self.edges[idx.0]
 202     }
 203
 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.
 208
 209         self.nodes[node.0].first_edge[dir.repr]
 210     }
 211
 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.
 216
 217         self.edges[edge.0].next_edge[dir.repr]
 218     }
 219
 220     ///////////////////////////////////////////////////////////////////////////
 221     // Iterating over nodes, edges
 222
 223     pub fn each_node<'a, F>(&'a self, mut f: F) -> bool where
 224         F: FnMut(NodeIndex, &'a Node<N>) -> bool,
 225     {
 226         //! Iterates over all edges defined in the graph.
 227         self.nodes.iter().enumerate().all(|(i, node)| f(NodeIndex(i), node))
 228     }
 229
 230     pub fn each_edge<'a, F>(&'a self, mut f: F) -> bool where
 231         F: FnMut(EdgeIndex, &'a Edge<E>) -> bool,
 232     {
 233         //! Iterates over all edges defined in the graph
 234         self.edges.iter().enumerate().all(|(i, edge)| f(EdgeIndex(i), edge))
 235     }
 236
 237     pub fn outgoing_edges(&self, source: NodeIndex) -> AdjacentEdges<N,E> {
 238         self.adjacent_edges(source, OUTGOING)
 239     }
 240
 241     pub fn incoming_edges(&self, source: NodeIndex) -> AdjacentEdges<N,E> {
 242         self.adjacent_edges(source, INCOMING)
 243     }
 244
 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 }
 248     }
 249
 250     pub fn successor_nodes<'a>(&'a self, source: NodeIndex) -> AdjacentTargets<N,E> {
 251         self.outgoing_edges(source).targets()
 252     }
 253
 254     pub fn predecessor_nodes<'a>(&'a self, target: NodeIndex) -> AdjacentSources<N,E> {
 255         self.incoming_edges(target).sources()
 256     }
 257
 258     ///////////////////////////////////////////////////////////////////////////
 259     // Fixed-point iteration
 260     //
 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
 265     // computation.
 266
 267     pub fn iterate_until_fixed_point<'a, F>(&'a self, mut op: F) where
 268         F: FnMut(usize, EdgeIndex, &'a Edge<E>) -> bool,
 269     {
 270         let mut iteration = 0;
 271         let mut changed = true;
 272         while changed {
 273             changed = false;
 274             iteration += 1;
 275             for (i, edge) in self.edges.iter().enumerate() {
 276                 changed |= op(iteration, EdgeIndex(i), edge);
 277             }
 278         }
 279     }
 280
 281     pub fn depth_traverse<'a>(&'a self, start: NodeIndex) -> DepthFirstTraversal<'a, N, E>  {
 282         DepthFirstTraversal {
 283             graph: self,
 284             stack: vec![start],
 285             visited: BitVector::new(self.nodes.len()),
 286         }
 287     }
 288 }
 289
 290 ///////////////////////////////////////////////////////////////////////////
 291 // Iterators
 292
 293 pub struct AdjacentEdges<'g,N,E>
 294     where N:'g, E:'g
 295 {
 296     graph: &'g Graph<N, E>,
 297     direction: Direction,
 298     next: EdgeIndex,
 299 }
 300
 301 impl<'g,N,E> AdjacentEdges<'g,N,E> {
 302     fn targets(self) -> AdjacentTargets<'g,N,E> {
 303         AdjacentTargets { edges: self }
 304     }
 305
 306     fn sources(self) -> AdjacentSources<'g,N,E> {
 307         AdjacentSources { edges: self }
 308     }
 309 }
 310
 311 impl<'g, N:Debug, E:Debug> Iterator for AdjacentEdges<'g, N, E> {
 312     type Item = (EdgeIndex, &'g Edge<E>);
 313
 314     fn next(&mut self) -> Option<(EdgeIndex, &'g Edge<E>)> {
 315         let edge_index = self.next;
 316         if edge_index == INVALID_EDGE_INDEX {
 317             return None;
 318         }
 319
 320         let edge = self.graph.edge(edge_index);
 321         self.next = edge.next_edge[self.direction.repr];
 322         Some((edge_index, edge))
 323     }
 324 }
 325
 326 pub struct AdjacentTargets<'g,N:'g,E:'g>
 327     where N:'g, E:'g
 328 {
 329     edges: AdjacentEdges<'g,N,E>,
 330 }
 331
 332 impl<'g, N:Debug, E:Debug> Iterator for AdjacentTargets<'g, N, E> {
 333     type Item = NodeIndex;
 334
 335     fn next(&mut self) -> Option<NodeIndex> {
 336         self.edges.next().map(|(_, edge)| edge.target)
 337     }
 338 }
 339
 340 pub struct AdjacentSources<'g,N:'g,E:'g>
 341     where N:'g, E:'g
 342 {
 343     edges: AdjacentEdges<'g,N,E>,
 344 }
 345
 346 impl<'g, N:Debug, E:Debug> Iterator for AdjacentSources<'g, N, E> {
 347     type Item = NodeIndex;
 348
 349     fn next(&mut self) -> Option<NodeIndex> {
 350         self.edges.next().map(|(_, edge)| edge.source)
 351     }
 352 }
 353
 354 pub struct DepthFirstTraversal<'g, N:'g, E:'g> {
 355     graph: &'g Graph<N, E>,
 356     stack: Vec<NodeIndex>,
 357     visited: BitVector
 358 }
 359
 360 impl<'g, N:Debug, E:Debug> Iterator for DepthFirstTraversal<'g, N, E> {
 361     type Item = NodeIndex;
 362
 363     fn next(&mut self) -> Option<NodeIndex> {
 364         while let Some(idx) = self.stack.pop() {
 365             if !self.visited.insert(idx.node_id()) {
 366                 continue;
 367             }
 368
 369             for (_, edge) in self.graph.outgoing_edges(idx) {
 370                 if !self.visited.contains(edge.target().node_id()) {
 371                     self.stack.push(edge.target());
 372                 }
 373             }
 374
 375             return Some(idx);
 376         }
 377
 378         return None;
 379     }
 380 }
 381
 382 pub fn each_edge_index<F>(max_edge_index: EdgeIndex, mut f: F) where
 383     F: FnMut(EdgeIndex) -> bool,
 384 {
 385     let mut i = 0;
 386     let n = max_edge_index.0;
 387     while i < n {
 388         if !f(EdgeIndex(i)) {
 389             return;
 390         }
 391         i += 1;
 392     }
 393 }
 394
 395 impl<E> Edge<E> {
 396     pub fn source(&self) -> NodeIndex {
 397         self.source
 398     }
 399
 400     pub fn target(&self) -> NodeIndex {
 401         self.target
 402     }
 403 }