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     // # Simple accessors
 118
 119     #[inline]
 120     pub fn all_nodes(&self) -> &[Node<N>] {
 121         &self.nodes
 122     }
 123
 124     #[inline]
 125     pub fn len_nodes(&self) -> usize {
 126         self.nodes.len()
 127     }
 128
 129     #[inline]
 130     pub fn all_edges(&self) -> &[Edge<E>] {
 131         &self.edges
 132     }
 133
 134     #[inline]
 135     pub fn len_edges(&self) -> usize {
 136         self.edges.len()
 137     }
 138
 139     // # Node construction
 140
 141     pub fn next_node_index(&self) -> NodeIndex {
 142         NodeIndex(self.nodes.len())
 143     }
 144
 145     pub fn add_node(&mut self, data: N) -> NodeIndex {
 146         let idx = self.next_node_index();
 147         self.nodes.push(Node {
 148             first_edge: [INVALID_EDGE_INDEX, INVALID_EDGE_INDEX],
 149             data,
 150         });
 151         idx
 152     }
 153
 154     pub fn mut_node_data(&mut self, idx: NodeIndex) -> &mut N {
 155         &mut self.nodes[idx.0].data
 156     }
 157
 158     pub fn node_data(&self, idx: NodeIndex) -> &N {
 159         &self.nodes[idx.0].data
 160     }
 161
 162     pub fn node(&self, idx: NodeIndex) -> &Node<N> {
 163         &self.nodes[idx.0]
 164     }
 165
 166     // # Edge construction and queries
 167
 168     pub fn next_edge_index(&self) -> EdgeIndex {
 169         EdgeIndex(self.edges.len())
 170     }
 171
 172     pub fn add_edge(&mut self, source: NodeIndex, target: NodeIndex, data: E) -> EdgeIndex {
 173         debug!("graph: add_edge({:?}, {:?}, {:?})", source, target, data);
 174
 175         let idx = self.next_edge_index();
 176
 177         // read current first of the list of edges from each node
 178         let source_first = self.nodes[source.0].first_edge[OUTGOING.repr];
 179         let target_first = self.nodes[target.0].first_edge[INCOMING.repr];
 180
 181         // create the new edge, with the previous firsts from each node
 182         // as the next pointers
 183         self.edges.push(Edge {
 184             next_edge: [source_first, target_first],
 185             source,
 186             target,
 187             data,
 188         });
 189
 190         // adjust the firsts for each node target be the next object.
 191         self.nodes[source.0].first_edge[OUTGOING.repr] = idx;
 192         self.nodes[target.0].first_edge[INCOMING.repr] = idx;
 193
 194         return idx;
 195     }
 196
 197     pub fn edge(&self, idx: EdgeIndex) -> &Edge<E> {
 198         &self.edges[idx.0]
 199     }
 200
 201     // # Iterating over nodes, edges
 202
 203     pub fn enumerated_nodes(&self) -> EnumeratedNodes<N> {
 204         EnumeratedNodes {
 205             iter: self.nodes.iter().enumerate()
 206         }
 207     }
 208
 209     pub fn enumerated_edges(&self) -> EnumeratedEdges<E> {
 210         EnumeratedEdges {
 211             iter: self.edges.iter().enumerate()
 212         }
 213     }
 214
 215     pub fn each_node<'a, F>(&'a self, mut f: F) -> bool
 216         where F: FnMut(NodeIndex, &'a Node<N>) -> bool
 217     {
 218         //! Iterates over all edges defined in the graph.
 219         self.enumerated_nodes().all(|(node_idx, node)| f(node_idx, node))
 220     }
 221
 222     pub fn each_edge<'a, F>(&'a self, mut f: F) -> bool
 223         where F: FnMut(EdgeIndex, &'a Edge<E>) -> bool
 224     {
 225         //! Iterates over all edges defined in the graph
 226         self.enumerated_edges().all(|(edge_idx, edge)| f(edge_idx, edge))
 227     }
 228
 229     pub fn outgoing_edges(&self, source: NodeIndex) -> AdjacentEdges<N, E> {
 230         self.adjacent_edges(source, OUTGOING)
 231     }
 232
 233     pub fn incoming_edges(&self, source: NodeIndex) -> AdjacentEdges<N, E> {
 234         self.adjacent_edges(source, INCOMING)
 235     }
 236
 237     pub fn adjacent_edges(&self, source: NodeIndex, direction: Direction) -> AdjacentEdges<N, E> {
 238         let first_edge = self.node(source).first_edge[direction.repr];
 239         AdjacentEdges {
 240             graph: self,
 241             direction,
 242             next: first_edge,
 243         }
 244     }
 245
 246     pub fn successor_nodes(&self, source: NodeIndex) -> AdjacentTargets<N, E> {
 247         self.outgoing_edges(source).targets()
 248     }
 249
 250     pub fn predecessor_nodes(&self, target: NodeIndex) -> AdjacentSources<N, E> {
 251         self.incoming_edges(target).sources()
 252     }
 253
 254     pub fn depth_traverse<'a>(&'a self,
 255                               start: NodeIndex,
 256                               direction: Direction)
 257                               -> DepthFirstTraversal<'a, N, E> {
 258         DepthFirstTraversal::with_start_node(self, start, direction)
 259     }
 260
 261     pub fn nodes_in_postorder<'a>(&'a self,
 262                                   direction: Direction,
 263                                   entry_node: NodeIndex)
 264                                   -> Vec<NodeIndex>
 265     {
 266         let mut visited = BitVector::new(self.len_nodes());
 267         let mut stack = vec![];
 268         let mut result = Vec::with_capacity(self.len_nodes());
 269         let mut push_node = |stack: &mut Vec<_>, node: NodeIndex| {
 270             if visited.insert(node.0) {
 271                 stack.push((node, self.adjacent_edges(node, direction)));
 272             }
 273         };
 274
 275         for node in Some(entry_node).into_iter()
 276             .chain(self.enumerated_nodes().map(|(node, _)| node))
 277         {
 278             push_node(&mut stack, node);
 279             while let Some((node, mut iter)) = stack.pop() {
 280                 if let Some((_, child)) = iter.next() {
 281                     let target = child.source_or_target(direction);
 282                     // the current node needs more processing, so
 283                     // add it back to the stack
 284                     stack.push((node, iter));
 285                     // and then push the new node
 286                     push_node(&mut stack, target);
 287                 } else {
 288                     result.push(node);
 289                 }
 290             }
 291         }
 292
 293         assert_eq!(result.len(), self.len_nodes());
 294         result
 295     }
 296 }
 297
 298 // # Iterators
 299
 300 pub struct EnumeratedNodes<'g, N>
 301     where N: 'g,
 302 {
 303     iter: ::std::iter::Enumerate<::std::slice::Iter<'g, Node<N>>>
 304 }
 305
 306 impl<'g, N: Debug> Iterator for EnumeratedNodes<'g, N> {
 307     type Item = (NodeIndex, &'g Node<N>);
 308
 309     fn next(&mut self) -> Option<(NodeIndex, &'g Node<N>)> {
 310         self.iter.next().map(|(idx, n)| (NodeIndex(idx), n))
 311     }
 312 }
 313
 314 pub struct EnumeratedEdges<'g, E>
 315     where E: 'g,
 316 {
 317     iter: ::std::iter::Enumerate<::std::slice::Iter<'g, Edge<E>>>
 318 }
 319
 320 impl<'g, E: Debug> Iterator for EnumeratedEdges<'g, E> {
 321     type Item = (EdgeIndex, &'g Edge<E>);
 322
 323     fn next(&mut self) -> Option<(EdgeIndex, &'g Edge<E>)> {
 324         self.iter.next().map(|(idx, e)| (EdgeIndex(idx), e))
 325     }
 326 }
 327
 328 pub struct AdjacentEdges<'g, N, E>
 329     where N: 'g,
 330           E: 'g
 331 {
 332     graph: &'g Graph<N, E>,
 333     direction: Direction,
 334     next: EdgeIndex,
 335 }
 336
 337 impl<'g, N, E> AdjacentEdges<'g, N, E> {
 338     fn targets(self) -> AdjacentTargets<'g, N, E> {
 339         AdjacentTargets { edges: self }
 340     }
 341
 342     fn sources(self) -> AdjacentSources<'g, N, E> {
 343         AdjacentSources { edges: self }
 344     }
 345 }
 346
 347 impl<'g, N: Debug, E: Debug> Iterator for AdjacentEdges<'g, N, E> {
 348     type Item = (EdgeIndex, &'g Edge<E>);
 349
 350     fn next(&mut self) -> Option<(EdgeIndex, &'g Edge<E>)> {
 351         let edge_index = self.next;
 352         if edge_index == INVALID_EDGE_INDEX {
 353             return None;
 354         }
 355
 356         let edge = self.graph.edge(edge_index);
 357         self.next = edge.next_edge[self.direction.repr];
 358         Some((edge_index, edge))
 359     }
 360 }
 361
 362 pub struct AdjacentTargets<'g, N, E>
 363     where N: 'g,
 364           E: 'g
 365 {
 366     edges: AdjacentEdges<'g, N, E>,
 367 }
 368
 369 impl<'g, N: Debug, E: Debug> Iterator for AdjacentTargets<'g, N, E> {
 370     type Item = NodeIndex;
 371
 372     fn next(&mut self) -> Option<NodeIndex> {
 373         self.edges.next().map(|(_, edge)| edge.target)
 374     }
 375 }
 376
 377 pub struct AdjacentSources<'g, N, E>
 378     where N: 'g,
 379           E: 'g
 380 {
 381     edges: AdjacentEdges<'g, N, E>,
 382 }
 383
 384 impl<'g, N: Debug, E: Debug> Iterator for AdjacentSources<'g, N, E> {
 385     type Item = NodeIndex;
 386
 387     fn next(&mut self) -> Option<NodeIndex> {
 388         self.edges.next().map(|(_, edge)| edge.source)
 389     }
 390 }
 391
 392 pub struct DepthFirstTraversal<'g, N, E>
 393     where N: 'g,
 394           E: 'g
 395 {
 396     graph: &'g Graph<N, E>,
 397     stack: Vec<NodeIndex>,
 398     visited: BitVector,
 399     direction: Direction,
 400 }
 401
 402 impl<'g, N: Debug, E: Debug> DepthFirstTraversal<'g, N, E> {
 403     pub fn with_start_node(graph: &'g Graph<N, E>,
 404                            start_node: NodeIndex,
 405                            direction: Direction)
 406                            -> Self {
 407         let mut visited = BitVector::new(graph.len_nodes());
 408         visited.insert(start_node.node_id());
 409         DepthFirstTraversal {
 410             graph,
 411             stack: vec![start_node],
 412             visited,
 413             direction,
 414         }
 415     }
 416
 417     fn visit(&mut self, node: NodeIndex) {
 418         if self.visited.insert(node.node_id()) {
 419             self.stack.push(node);
 420         }
 421     }
 422 }
 423
 424 impl<'g, N: Debug, E: Debug> Iterator for DepthFirstTraversal<'g, N, E> {
 425     type Item = NodeIndex;
 426
 427     fn next(&mut self) -> Option<NodeIndex> {
 428         let next = self.stack.pop();
 429         if let Some(idx) = next {
 430             for (_, edge) in self.graph.adjacent_edges(idx, self.direction) {
 431                 let target = edge.source_or_target(self.direction);
 432                 self.visit(target);
 433             }
 434         }
 435         next
 436     }
 437 }
 438
 439 impl<E> Edge<E> {
 440     pub fn source(&self) -> NodeIndex {
 441         self.source
 442     }
 443
 444     pub fn target(&self) -> NodeIndex {
 445         self.target
 446     }
 447
 448     pub fn source_or_target(&self, direction: Direction) -> NodeIndex {
 449         if direction == OUTGOING {
 450             self.target
 451         } else {
 452             self.source
 453         }
 454     }
 455 }