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<N: Debug, E: Debug> Graph<N, E> {
 110     pub fn new() -> Graph<N, E> {
 111         Graph {
 112             nodes: SnapshotVec::new(),
 113             edges: SnapshotVec::new(),
 114         }
 115     }
 116
 117     pub fn with_capacity(nodes: usize, edges: usize) -> Graph<N, E> {
 118         Graph {
 119             nodes: SnapshotVec::with_capacity(nodes),
 120             edges: SnapshotVec::with_capacity(edges),
 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,
 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,
 193             target,
 194             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 edge(&self, idx: EdgeIndex) -> &Edge<E> {
 205         &self.edges[idx.0]
 206     }
 207
 208     // # Iterating over nodes, edges
 209
 210     pub fn enumerated_nodes(&self) -> EnumeratedNodes<N> {
 211         EnumeratedNodes {
 212             iter: self.nodes.iter().enumerate()
 213         }
 214     }
 215
 216     pub fn enumerated_edges(&self) -> EnumeratedEdges<E> {
 217         EnumeratedEdges {
 218             iter: self.edges.iter().enumerate()
 219         }
 220     }
 221
 222     pub fn each_node<'a, F>(&'a self, mut f: F) -> bool
 223         where F: FnMut(NodeIndex, &'a Node<N>) -> bool
 224     {
 225         //! Iterates over all edges defined in the graph.
 226         self.enumerated_nodes().all(|(node_idx, node)| f(node_idx, node))
 227     }
 228
 229     pub fn each_edge<'a, F>(&'a self, mut f: F) -> bool
 230         where F: FnMut(EdgeIndex, &'a Edge<E>) -> bool
 231     {
 232         //! Iterates over all edges defined in the graph
 233         self.enumerated_edges().all(|(edge_idx, edge)| f(edge_idx, edge))
 234     }
 235
 236     pub fn outgoing_edges(&self, source: NodeIndex) -> AdjacentEdges<N, E> {
 237         self.adjacent_edges(source, OUTGOING)
 238     }
 239
 240     pub fn incoming_edges(&self, source: NodeIndex) -> AdjacentEdges<N, E> {
 241         self.adjacent_edges(source, INCOMING)
 242     }
 243
 244     pub fn adjacent_edges(&self, source: NodeIndex, direction: Direction) -> AdjacentEdges<N, E> {
 245         let first_edge = self.node(source).first_edge[direction.repr];
 246         AdjacentEdges {
 247             graph: self,
 248             direction,
 249             next: first_edge,
 250         }
 251     }
 252
 253     pub fn successor_nodes(&self, source: NodeIndex) -> AdjacentTargets<N, E> {
 254         self.outgoing_edges(source).targets()
 255     }
 256
 257     pub fn predecessor_nodes(&self, target: NodeIndex) -> AdjacentSources<N, E> {
 258         self.incoming_edges(target).sources()
 259     }
 260
 261     pub fn depth_traverse<'a>(&'a self,
 262                               start: NodeIndex,
 263                               direction: Direction)
 264                               -> DepthFirstTraversal<'a, N, E> {
 265         DepthFirstTraversal::with_start_node(self, start, direction)
 266     }
 267
 268     pub fn nodes_in_postorder<'a>(&'a self,
 269                                   direction: Direction,
 270                                   entry_node: NodeIndex)
 271                                   -> Vec<NodeIndex>
 272     {
 273         let mut visited = BitVector::new(self.len_nodes());
 274         let mut stack = vec![];
 275         let mut result = Vec::with_capacity(self.len_nodes());
 276         let mut push_node = |stack: &mut Vec<_>, node: NodeIndex| {
 277             if visited.insert(node.0) {
 278                 stack.push((node, self.adjacent_edges(node, direction)));
 279             }
 280         };
 281
 282         for node in Some(entry_node).into_iter()
 283             .chain(self.enumerated_nodes().map(|(node, _)| node))
 284         {
 285             push_node(&mut stack, node);
 286             while let Some((node, mut iter)) = stack.pop() {
 287                 if let Some((_, child)) = iter.next() {
 288                     let target = child.source_or_target(direction);
 289                     // the current node needs more processing, so
 290                     // add it back to the stack
 291                     stack.push((node, iter));
 292                     // and then push the new node
 293                     push_node(&mut stack, target);
 294                 } else {
 295                     result.push(node);
 296                 }
 297             }
 298         }
 299
 300         assert_eq!(result.len(), self.len_nodes());
 301         result
 302     }
 303 }
 304
 305 // # Iterators
 306
 307 pub struct EnumeratedNodes<'g, N>
 308     where N: 'g,
 309 {
 310     iter: ::std::iter::Enumerate<::std::slice::Iter<'g, Node<N>>>
 311 }
 312
 313 impl<'g, N: Debug> Iterator for EnumeratedNodes<'g, N> {
 314     type Item = (NodeIndex, &'g Node<N>);
 315
 316     fn next(&mut self) -> Option<(NodeIndex, &'g Node<N>)> {
 317         self.iter.next().map(|(idx, n)| (NodeIndex(idx), n))
 318     }
 319 }
 320
 321 pub struct EnumeratedEdges<'g, E>
 322     where E: 'g,
 323 {
 324     iter: ::std::iter::Enumerate<::std::slice::Iter<'g, Edge<E>>>
 325 }
 326
 327 impl<'g, E: Debug> Iterator for EnumeratedEdges<'g, E> {
 328     type Item = (EdgeIndex, &'g Edge<E>);
 329
 330     fn next(&mut self) -> Option<(EdgeIndex, &'g Edge<E>)> {
 331         self.iter.next().map(|(idx, e)| (EdgeIndex(idx), e))
 332     }
 333 }
 334
 335 pub struct AdjacentEdges<'g, N, E>
 336     where N: 'g,
 337           E: 'g
 338 {
 339     graph: &'g Graph<N, E>,
 340     direction: Direction,
 341     next: EdgeIndex,
 342 }
 343
 344 impl<'g, N, E> AdjacentEdges<'g, N, E> {
 345     fn targets(self) -> AdjacentTargets<'g, N, E> {
 346         AdjacentTargets { edges: self }
 347     }
 348
 349     fn sources(self) -> AdjacentSources<'g, N, E> {
 350         AdjacentSources { edges: self }
 351     }
 352 }
 353
 354 impl<'g, N: Debug, E: Debug> Iterator for AdjacentEdges<'g, N, E> {
 355     type Item = (EdgeIndex, &'g Edge<E>);
 356
 357     fn next(&mut self) -> Option<(EdgeIndex, &'g Edge<E>)> {
 358         let edge_index = self.next;
 359         if edge_index == INVALID_EDGE_INDEX {
 360             return None;
 361         }
 362
 363         let edge = self.graph.edge(edge_index);
 364         self.next = edge.next_edge[self.direction.repr];
 365         Some((edge_index, edge))
 366     }
 367 }
 368
 369 pub struct AdjacentTargets<'g, N, E>
 370     where N: 'g,
 371           E: 'g
 372 {
 373     edges: AdjacentEdges<'g, N, E>,
 374 }
 375
 376 impl<'g, N: Debug, E: Debug> Iterator for AdjacentTargets<'g, N, E> {
 377     type Item = NodeIndex;
 378
 379     fn next(&mut self) -> Option<NodeIndex> {
 380         self.edges.next().map(|(_, edge)| edge.target)
 381     }
 382 }
 383
 384 pub struct AdjacentSources<'g, N, E>
 385     where N: 'g,
 386           E: 'g
 387 {
 388     edges: AdjacentEdges<'g, N, E>,
 389 }
 390
 391 impl<'g, N: Debug, E: Debug> Iterator for AdjacentSources<'g, N, E> {
 392     type Item = NodeIndex;
 393
 394     fn next(&mut self) -> Option<NodeIndex> {
 395         self.edges.next().map(|(_, edge)| edge.source)
 396     }
 397 }
 398
 399 pub struct DepthFirstTraversal<'g, N, E>
 400     where N: 'g,
 401           E: 'g
 402 {
 403     graph: &'g Graph<N, E>,
 404     stack: Vec<NodeIndex>,
 405     visited: BitVector,
 406     direction: Direction,
 407 }
 408
 409 impl<'g, N: Debug, E: Debug> DepthFirstTraversal<'g, N, E> {
 410     pub fn with_start_node(graph: &'g Graph<N, E>,
 411                            start_node: NodeIndex,
 412                            direction: Direction)
 413                            -> Self {
 414         let mut visited = BitVector::new(graph.len_nodes());
 415         visited.insert(start_node.node_id());
 416         DepthFirstTraversal {
 417             graph,
 418             stack: vec![start_node],
 419             visited,
 420             direction,
 421         }
 422     }
 423
 424     fn visit(&mut self, node: NodeIndex) {
 425         if self.visited.insert(node.node_id()) {
 426             self.stack.push(node);
 427         }
 428     }
 429 }
 430
 431 impl<'g, N: Debug, E: Debug> Iterator for DepthFirstTraversal<'g, N, E> {
 432     type Item = NodeIndex;
 433
 434     fn next(&mut self) -> Option<NodeIndex> {
 435         let next = self.stack.pop();
 436         if let Some(idx) = next {
 437             for (_, edge) in self.graph.adjacent_edges(idx, self.direction) {
 438                 let target = edge.source_or_target(self.direction);
 439                 self.visit(target);
 440             }
 441         }
 442         next
 443     }
 444 }
 445
 446 impl<E> Edge<E> {
 447     pub fn source(&self) -> NodeIndex {
 448         self.source
 449     }
 450
 451     pub fn target(&self) -> NodeIndex {
 452         self.target
 453     }
 454
 455     pub fn source_or_target(&self, direction: Direction) -> NodeIndex {
 456         if direction == OUTGOING {
 457             self.target
 458         } else {
 459             self.source
 460         }
 461     }
 462 }