src/librustc_data_structures/graph/implementation/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 bit_set::BitSet;
  34 use std::fmt::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 #[derive(Debug)]
  52 pub struct Edge<E> {
  53     next_edge: [EdgeIndex; 2], // see module comment
  54     source: NodeIndex,
  55     target: NodeIndex,
  56     pub data: E,
  57 }
  58
  59 impl<N> SnapshotVecDelegate for Node<N> {
  60     type Value = Node<N>;
  61     type Undo = ();
  62
  63     fn reverse(_: &mut Vec<Node<N>>, _: ()) {}
  64 }
  65
  66 impl<N> SnapshotVecDelegate for Edge<N> {
  67     type Value = Edge<N>;
  68     type Undo = ();
  69
  70     fn reverse(_: &mut Vec<Edge<N>>, _: ()) {}
  71 }
  72
  73 #[derive(Copy, Clone, PartialEq, Eq, Debug, Hash)]
  74 pub struct NodeIndex(pub usize);
  75
  76 #[derive(Copy, Clone, PartialEq, Eq, Debug, Hash)]
  77 pub struct EdgeIndex(pub usize);
  78
  79 pub const INVALID_EDGE_INDEX: EdgeIndex = EdgeIndex(usize::MAX);
  80
  81 // Use a private field here to guarantee no more instances are created:
  82 #[derive(Copy, Clone, Debug, PartialEq)]
  83 pub struct Direction {
  84     repr: usize,
  85 }
  86
  87 pub const OUTGOING: Direction = Direction { repr: 0 };
  88
  89 pub const INCOMING: Direction = Direction { repr: 1 };
  90
  91 impl NodeIndex {
  92     /// Returns unique id (unique with respect to the graph holding associated node).
  93     pub fn node_id(self) -> usize {
  94         self.0
  95     }
  96 }
  97
  98 impl<N: Debug, E: Debug> Graph<N, E> {
  99     pub fn new() -> Graph<N, E> {
 100         Graph {
 101             nodes: SnapshotVec::new(),
 102             edges: SnapshotVec::new(),
 103         }
 104     }
 105
 106     pub fn with_capacity(nodes: usize, edges: usize) -> Graph<N, E> {
 107         Graph {
 108             nodes: SnapshotVec::with_capacity(nodes),
 109             edges: SnapshotVec::with_capacity(edges),
 110         }
 111     }
 112
 113     // # Simple accessors
 114
 115     #[inline]
 116     pub fn all_nodes(&self) -> &[Node<N>] {
 117         &self.nodes
 118     }
 119
 120     #[inline]
 121     pub fn len_nodes(&self) -> usize {
 122         self.nodes.len()
 123     }
 124
 125     #[inline]
 126     pub fn all_edges(&self) -> &[Edge<E>] {
 127         &self.edges
 128     }
 129
 130     #[inline]
 131     pub fn len_edges(&self) -> usize {
 132         self.edges.len()
 133     }
 134
 135     // # Node construction
 136
 137     pub fn next_node_index(&self) -> NodeIndex {
 138         NodeIndex(self.nodes.len())
 139     }
 140
 141     pub fn add_node(&mut self, data: N) -> NodeIndex {
 142         let idx = self.next_node_index();
 143         self.nodes.push(Node {
 144             first_edge: [INVALID_EDGE_INDEX, INVALID_EDGE_INDEX],
 145             data,
 146         });
 147         idx
 148     }
 149
 150     pub fn mut_node_data(&mut self, idx: NodeIndex) -> &mut N {
 151         &mut self.nodes[idx.0].data
 152     }
 153
 154     pub fn node_data(&self, idx: NodeIndex) -> &N {
 155         &self.nodes[idx.0].data
 156     }
 157
 158     pub fn node(&self, idx: NodeIndex) -> &Node<N> {
 159         &self.nodes[idx.0]
 160     }
 161
 162     // # Edge construction and queries
 163
 164     pub fn next_edge_index(&self) -> EdgeIndex {
 165         EdgeIndex(self.edges.len())
 166     }
 167
 168     pub fn add_edge(&mut self, source: NodeIndex, target: NodeIndex, data: E) -> EdgeIndex {
 169         debug!("graph: add_edge({:?}, {:?}, {:?})", source, target, data);
 170
 171         let idx = self.next_edge_index();
 172
 173         // read current first of the list of edges from each node
 174         let source_first = self.nodes[source.0].first_edge[OUTGOING.repr];
 175         let target_first = self.nodes[target.0].first_edge[INCOMING.repr];
 176
 177         // create the new edge, with the previous firsts from each node
 178         // as the next pointers
 179         self.edges.push(Edge {
 180             next_edge: [source_first, target_first],
 181             source,
 182             target,
 183             data,
 184         });
 185
 186         // adjust the firsts for each node target be the next object.
 187         self.nodes[source.0].first_edge[OUTGOING.repr] = idx;
 188         self.nodes[target.0].first_edge[INCOMING.repr] = idx;
 189
 190         idx
 191     }
 192
 193     pub fn edge(&self, idx: EdgeIndex) -> &Edge<E> {
 194         &self.edges[idx.0]
 195     }
 196
 197     // # Iterating over nodes, edges
 198
 199     pub fn enumerated_nodes(&self) -> impl Iterator<Item = (NodeIndex, &Node<N>)> {
 200         self.nodes
 201             .iter()
 202             .enumerate()
 203             .map(|(idx, n)| (NodeIndex(idx), n))
 204     }
 205
 206     pub fn enumerated_edges(&self) -> impl Iterator<Item = (EdgeIndex, &Edge<E>)> {
 207         self.edges
 208             .iter()
 209             .enumerate()
 210             .map(|(idx, e)| (EdgeIndex(idx), e))
 211     }
 212
 213     pub fn each_node<'a>(&'a self, mut f: impl FnMut(NodeIndex, &'a Node<N>) -> bool) -> bool {
 214         //! Iterates over all edges defined in the graph.
 215         self.enumerated_nodes()
 216             .all(|(node_idx, node)| f(node_idx, node))
 217     }
 218
 219     pub fn each_edge<'a>(&'a self, mut f: impl FnMut(EdgeIndex, &'a Edge<E>) -> bool) -> bool {
 220         //! Iterates over all edges defined in the graph
 221         self.enumerated_edges()
 222             .all(|(edge_idx, edge)| f(edge_idx, edge))
 223     }
 224
 225     pub fn outgoing_edges(&self, source: NodeIndex) -> AdjacentEdges<N, E> {
 226         self.adjacent_edges(source, OUTGOING)
 227     }
 228
 229     pub fn incoming_edges(&self, source: NodeIndex) -> AdjacentEdges<N, E> {
 230         self.adjacent_edges(source, INCOMING)
 231     }
 232
 233     pub fn adjacent_edges(&self, source: NodeIndex, direction: Direction) -> AdjacentEdges<N, E> {
 234         let first_edge = self.node(source).first_edge[direction.repr];
 235         AdjacentEdges {
 236             graph: self,
 237             direction,
 238             next: first_edge,
 239         }
 240     }
 241
 242     pub fn successor_nodes<'a>(
 243         &'a self,
 244         source: NodeIndex,
 245     ) -> impl Iterator<Item = NodeIndex> + 'a {
 246         self.outgoing_edges(source).targets()
 247     }
 248
 249     pub fn predecessor_nodes<'a>(
 250         &'a self,
 251         target: NodeIndex,
 252     ) -> impl Iterator<Item = NodeIndex> + 'a {
 253         self.incoming_edges(target).sources()
 254     }
 255
 256     pub fn depth_traverse<'a>(
 257         &'a self,
 258         start: NodeIndex,
 259         direction: Direction,
 260     ) -> DepthFirstTraversal<'a, N, E> {
 261         DepthFirstTraversal::with_start_node(self, start, direction)
 262     }
 263
 264     pub fn nodes_in_postorder(
 265         &self,
 266         direction: Direction,
 267         entry_node: NodeIndex,
 268     ) -> Vec<NodeIndex> {
 269         let mut visited = BitSet::new_empty(self.len_nodes());
 270         let mut stack = vec![];
 271         let mut result = Vec::with_capacity(self.len_nodes());
 272         let mut push_node = |stack: &mut Vec<_>, node: NodeIndex| {
 273             if visited.insert(node.0) {
 274                 stack.push((node, self.adjacent_edges(node, direction)));
 275             }
 276         };
 277
 278         for node in Some(entry_node)
 279             .into_iter()
 280             .chain(self.enumerated_nodes().map(|(node, _)| node))
 281         {
 282             push_node(&mut stack, node);
 283             while let Some((node, mut iter)) = stack.pop() {
 284                 if let Some((_, child)) = iter.next() {
 285                     let target = child.source_or_target(direction);
 286                     // the current node needs more processing, so
 287                     // add it back to the stack
 288                     stack.push((node, iter));
 289                     // and then push the new node
 290                     push_node(&mut stack, target);
 291                 } else {
 292                     result.push(node);
 293                 }
 294             }
 295         }
 296
 297         assert_eq!(result.len(), self.len_nodes());
 298         result
 299     }
 300 }
 301
 302 // # Iterators
 303
 304 pub struct AdjacentEdges<'g, N, E>
 305 where
 306     N: 'g,
 307     E: 'g,
 308 {
 309     graph: &'g Graph<N, E>,
 310     direction: Direction,
 311     next: EdgeIndex,
 312 }
 313
 314 impl<'g, N: Debug, E: Debug> AdjacentEdges<'g, N, E> {
 315     fn targets(self) -> impl Iterator<Item = NodeIndex> + 'g {
 316         self.into_iter().map(|(_, edge)| edge.target)
 317     }
 318
 319     fn sources(self) -> impl Iterator<Item = NodeIndex> + 'g {
 320         self.into_iter().map(|(_, edge)| edge.source)
 321     }
 322 }
 323
 324 impl<'g, N: Debug, E: Debug> Iterator for AdjacentEdges<'g, N, E> {
 325     type Item = (EdgeIndex, &'g Edge<E>);
 326
 327     fn next(&mut self) -> Option<(EdgeIndex, &'g Edge<E>)> {
 328         let edge_index = self.next;
 329         if edge_index == INVALID_EDGE_INDEX {
 330             return None;
 331         }
 332
 333         let edge = self.graph.edge(edge_index);
 334         self.next = edge.next_edge[self.direction.repr];
 335         Some((edge_index, edge))
 336     }
 337
 338     fn size_hint(&self) -> (usize, Option<usize>) {
 339         // At most, all the edges in the graph.
 340         (0, Some(self.graph.len_edges()))
 341     }
 342 }
 343
 344 pub struct DepthFirstTraversal<'g, N, E>
 345 where
 346     N: 'g,
 347     E: 'g,
 348 {
 349     graph: &'g Graph<N, E>,
 350     stack: Vec<NodeIndex>,
 351     visited: BitSet<usize>,
 352     direction: Direction,
 353 }
 354
 355 impl<'g, N: Debug, E: Debug> DepthFirstTraversal<'g, N, E> {
 356     pub fn with_start_node(
 357         graph: &'g Graph<N, E>,
 358         start_node: NodeIndex,
 359         direction: Direction,
 360     ) -> Self {
 361         let mut visited = BitSet::new_empty(graph.len_nodes());
 362         visited.insert(start_node.node_id());
 363         DepthFirstTraversal {
 364             graph,
 365             stack: vec![start_node],
 366             visited,
 367             direction,
 368         }
 369     }
 370
 371     fn visit(&mut self, node: NodeIndex) {
 372         if self.visited.insert(node.node_id()) {
 373             self.stack.push(node);
 374         }
 375     }
 376 }
 377
 378 impl<'g, N: Debug, E: Debug> Iterator for DepthFirstTraversal<'g, N, E> {
 379     type Item = NodeIndex;
 380
 381     fn next(&mut self) -> Option<NodeIndex> {
 382         let next = self.stack.pop();
 383         if let Some(idx) = next {
 384             for (_, edge) in self.graph.adjacent_edges(idx, self.direction) {
 385                 let target = edge.source_or_target(self.direction);
 386                 self.visit(target);
 387             }
 388         }
 389         next
 390     }
 391
 392     fn size_hint(&self) -> (usize, Option<usize>) {
 393         // We will visit every node in the graph exactly once.
 394         let remaining = self.graph.len_nodes() - self.visited.count();
 395         (remaining, Some(remaining))
 396     }
 397 }
 398
 399 impl<'g, N: Debug, E: Debug> ExactSizeIterator for DepthFirstTraversal<'g, N, E> {}
 400
 401 impl<E> Edge<E> {
 402     pub fn source(&self) -> NodeIndex {
 403         self.source
 404     }
 405
 406     pub fn target(&self) -> NodeIndex {
 407         self.target
 408     }
 409
 410     pub fn source_or_target(&self, direction: Direction) -> NodeIndex {
 411         if direction == OUTGOING {
 412             self.target
 413         } else {
 414             self.source
 415         }
 416     }
 417 }