src/librustc_data_structures/graph/implementation/mod.rs

   1 //! A graph module for use in dataflow, region resolution, and elsewhere.
   2 //!
   3 //! # Interface details
   4 //!
   5 //! You customize the graph by specifying a "node data" type `N` and an
   6 //! "edge data" type `E`. You can then later gain access (mutable or
   7 //! immutable) to these "user-data" bits. Currently, you can only add
   8 //! nodes or edges to the graph. You cannot remove or modify them once
   9 //! added. This could be changed if we have a need.
  10 //!
  11 //! # Implementation details
  12 //!
  13 //! The main tricky thing about this code is the way that edges are
  14 //! stored. The edges are stored in a central array, but they are also
  15 //! threaded onto two linked lists for each node, one for incoming edges
  16 //! and one for outgoing edges. Note that every edge is a member of some
  17 //! incoming list and some outgoing list. Basically you can load the
  18 //! first index of the linked list from the node data structures (the
  19 //! field `first_edge`) and then, for each edge, load the next index from
  20 //! the field `next_edge`). Each of those fields is an array that should
  21 //! be indexed by the direction (see the type `Direction`).
  22
  23 use crate::bit_set::BitSet;
  24 use crate::snapshot_vec::{SnapshotVec, SnapshotVecDelegate};
  25 use std::fmt::Debug;
  26 use std::usize;
  27
  28 #[cfg(test)]
  29 mod tests;
  30
  31 pub struct Graph<N, E> {
  32     nodes: SnapshotVec<Node<N>>,
  33     edges: SnapshotVec<Edge<E>>,
  34 }
  35
  36 pub struct Node<N> {
  37     first_edge: [EdgeIndex; 2], // see module comment
  38     pub data: N,
  39 }
  40
  41 #[derive(Debug)]
  42 pub struct Edge<E> {
  43     next_edge: [EdgeIndex; 2], // see module comment
  44     source: NodeIndex,
  45     target: NodeIndex,
  46     pub data: E,
  47 }
  48
  49 impl<N> SnapshotVecDelegate for Node<N> {
  50     type Value = Node<N>;
  51     type Undo = ();
  52
  53     fn reverse(_: &mut Vec<Node<N>>, _: ()) {}
  54 }
  55
  56 impl<N> SnapshotVecDelegate for Edge<N> {
  57     type Value = Edge<N>;
  58     type Undo = ();
  59
  60     fn reverse(_: &mut Vec<Edge<N>>, _: ()) {}
  61 }
  62
  63 #[derive(Copy, Clone, PartialEq, Eq, Debug, Hash)]
  64 pub struct NodeIndex(pub usize);
  65
  66 #[derive(Copy, Clone, PartialEq, Eq, Debug, Hash)]
  67 pub struct EdgeIndex(pub usize);
  68
  69 pub const INVALID_EDGE_INDEX: EdgeIndex = EdgeIndex(usize::MAX);
  70
  71 // Use a private field here to guarantee no more instances are created:
  72 #[derive(Copy, Clone, Debug, PartialEq)]
  73 pub struct Direction {
  74     repr: usize,
  75 }
  76
  77 pub const OUTGOING: Direction = Direction { repr: 0 };
  78
  79 pub const INCOMING: Direction = Direction { repr: 1 };
  80
  81 impl NodeIndex {
  82     /// Returns unique ID (unique with respect to the graph holding associated node).
  83     pub fn node_id(self) -> usize {
  84         self.0
  85     }
  86 }
  87
  88 impl<N: Debug, E: Debug> Graph<N, E> {
  89     pub fn new() -> Graph<N, E> {
  90         Graph {
  91             nodes: SnapshotVec::new(),
  92             edges: SnapshotVec::new(),
  93         }
  94     }
  95
  96     pub fn with_capacity(nodes: usize, edges: usize) -> Graph<N, E> {
  97         Graph {
  98             nodes: SnapshotVec::with_capacity(nodes),
  99             edges: SnapshotVec::with_capacity(edges),
 100         }
 101     }
 102
 103     // # Simple accessors
 104
 105     #[inline]
 106     pub fn all_nodes(&self) -> &[Node<N>] {
 107         &self.nodes
 108     }
 109
 110     #[inline]
 111     pub fn len_nodes(&self) -> usize {
 112         self.nodes.len()
 113     }
 114
 115     #[inline]
 116     pub fn all_edges(&self) -> &[Edge<E>] {
 117         &self.edges
 118     }
 119
 120     #[inline]
 121     pub fn len_edges(&self) -> usize {
 122         self.edges.len()
 123     }
 124
 125     // # Node construction
 126
 127     pub fn next_node_index(&self) -> NodeIndex {
 128         NodeIndex(self.nodes.len())
 129     }
 130
 131     pub fn add_node(&mut self, data: N) -> NodeIndex {
 132         let idx = self.next_node_index();
 133         self.nodes.push(Node {
 134             first_edge: [INVALID_EDGE_INDEX, INVALID_EDGE_INDEX],
 135             data,
 136         });
 137         idx
 138     }
 139
 140     pub fn mut_node_data(&mut self, idx: NodeIndex) -> &mut N {
 141         &mut self.nodes[idx.0].data
 142     }
 143
 144     pub fn node_data(&self, idx: NodeIndex) -> &N {
 145         &self.nodes[idx.0].data
 146     }
 147
 148     pub fn node(&self, idx: NodeIndex) -> &Node<N> {
 149         &self.nodes[idx.0]
 150     }
 151
 152     // # Edge construction and queries
 153
 154     pub fn next_edge_index(&self) -> EdgeIndex {
 155         EdgeIndex(self.edges.len())
 156     }
 157
 158     pub fn add_edge(&mut self, source: NodeIndex, target: NodeIndex, data: E) -> EdgeIndex {
 159         debug!("graph: add_edge({:?}, {:?}, {:?})", source, target, data);
 160
 161         let idx = self.next_edge_index();
 162
 163         // read current first of the list of edges from each node
 164         let source_first = self.nodes[source.0].first_edge[OUTGOING.repr];
 165         let target_first = self.nodes[target.0].first_edge[INCOMING.repr];
 166
 167         // create the new edge, with the previous firsts from each node
 168         // as the next pointers
 169         self.edges.push(Edge {
 170             next_edge: [source_first, target_first],
 171             source,
 172             target,
 173             data,
 174         });
 175
 176         // adjust the firsts for each node target be the next object.
 177         self.nodes[source.0].first_edge[OUTGOING.repr] = idx;
 178         self.nodes[target.0].first_edge[INCOMING.repr] = idx;
 179
 180         idx
 181     }
 182
 183     pub fn edge(&self, idx: EdgeIndex) -> &Edge<E> {
 184         &self.edges[idx.0]
 185     }
 186
 187     // # Iterating over nodes, edges
 188
 189     pub fn enumerated_nodes(&self) -> impl Iterator<Item = (NodeIndex, &Node<N>)> {
 190         self.nodes
 191             .iter()
 192             .enumerate()
 193             .map(|(idx, n)| (NodeIndex(idx), n))
 194     }
 195
 196     pub fn enumerated_edges(&self) -> impl Iterator<Item = (EdgeIndex, &Edge<E>)> {
 197         self.edges
 198             .iter()
 199             .enumerate()
 200             .map(|(idx, e)| (EdgeIndex(idx), e))
 201     }
 202
 203     pub fn each_node<'a>(&'a self, mut f: impl FnMut(NodeIndex, &'a Node<N>) -> bool) -> bool {
 204         //! Iterates over all edges defined in the graph.
 205         self.enumerated_nodes()
 206             .all(|(node_idx, node)| f(node_idx, node))
 207     }
 208
 209     pub fn each_edge<'a>(&'a self, mut f: impl FnMut(EdgeIndex, &'a Edge<E>) -> bool) -> bool {
 210         //! Iterates over all edges defined in the graph
 211         self.enumerated_edges()
 212             .all(|(edge_idx, edge)| f(edge_idx, edge))
 213     }
 214
 215     pub fn outgoing_edges(&self, source: NodeIndex) -> AdjacentEdges<'_, N, E> {
 216         self.adjacent_edges(source, OUTGOING)
 217     }
 218
 219     pub fn incoming_edges(&self, source: NodeIndex) -> AdjacentEdges<'_, N, E> {
 220         self.adjacent_edges(source, INCOMING)
 221     }
 222
 223     pub fn adjacent_edges(
 224         &self,
 225         source: NodeIndex,
 226         direction: Direction
 227     ) -> AdjacentEdges<'_, N, E> {
 228         let first_edge = self.node(source).first_edge[direction.repr];
 229         AdjacentEdges {
 230             graph: self,
 231             direction,
 232             next: first_edge,
 233         }
 234     }
 235
 236     pub fn successor_nodes<'a>(
 237         &'a self,
 238         source: NodeIndex,
 239     ) -> impl Iterator<Item = NodeIndex> + 'a {
 240         self.outgoing_edges(source).targets()
 241     }
 242
 243     pub fn predecessor_nodes<'a>(
 244         &'a self,
 245         target: NodeIndex,
 246     ) -> impl Iterator<Item = NodeIndex> + 'a {
 247         self.incoming_edges(target).sources()
 248     }
 249
 250     pub fn depth_traverse(
 251         &self,
 252         start: NodeIndex,
 253         direction: Direction,
 254     ) -> DepthFirstTraversal<'_, N, E> {
 255         DepthFirstTraversal::with_start_node(self, start, direction)
 256     }
 257
 258     pub fn nodes_in_postorder(
 259         &self,
 260         direction: Direction,
 261         entry_node: NodeIndex,
 262     ) -> Vec<NodeIndex> {
 263         let mut visited = BitSet::new_empty(self.len_nodes());
 264         let mut stack = vec![];
 265         let mut result = Vec::with_capacity(self.len_nodes());
 266         let mut push_node = |stack: &mut Vec<_>, node: NodeIndex| {
 267             if visited.insert(node.0) {
 268                 stack.push((node, self.adjacent_edges(node, direction)));
 269             }
 270         };
 271
 272         for node in Some(entry_node)
 273             .into_iter()
 274             .chain(self.enumerated_nodes().map(|(node, _)| node))
 275         {
 276             push_node(&mut stack, node);
 277             while let Some((node, mut iter)) = stack.pop() {
 278                 if let Some((_, child)) = iter.next() {
 279                     let target = child.source_or_target(direction);
 280                     // the current node needs more processing, so
 281                     // add it back to the stack
 282                     stack.push((node, iter));
 283                     // and then push the new node
 284                     push_node(&mut stack, target);
 285                 } else {
 286                     result.push(node);
 287                 }
 288             }
 289         }
 290
 291         assert_eq!(result.len(), self.len_nodes());
 292         result
 293     }
 294 }
 295
 296 // # Iterators
 297
 298 pub struct AdjacentEdges<'g, N, E> {
 299     graph: &'g Graph<N, E>,
 300     direction: Direction,
 301     next: EdgeIndex,
 302 }
 303
 304 impl<'g, N: Debug, E: Debug> AdjacentEdges<'g, N, E> {
 305     fn targets(self) -> impl Iterator<Item = NodeIndex> + 'g {
 306         self.into_iter().map(|(_, edge)| edge.target)
 307     }
 308
 309     fn sources(self) -> impl Iterator<Item = NodeIndex> + 'g {
 310         self.into_iter().map(|(_, edge)| edge.source)
 311     }
 312 }
 313
 314 impl<'g, N: Debug, E: Debug> Iterator for AdjacentEdges<'g, N, E> {
 315     type Item = (EdgeIndex, &'g Edge<E>);
 316
 317     fn next(&mut self) -> Option<(EdgeIndex, &'g Edge<E>)> {
 318         let edge_index = self.next;
 319         if edge_index == INVALID_EDGE_INDEX {
 320             return None;
 321         }
 322
 323         let edge = self.graph.edge(edge_index);
 324         self.next = edge.next_edge[self.direction.repr];
 325         Some((edge_index, edge))
 326     }
 327
 328     fn size_hint(&self) -> (usize, Option<usize>) {
 329         // At most, all the edges in the graph.
 330         (0, Some(self.graph.len_edges()))
 331     }
 332 }
 333
 334 pub struct DepthFirstTraversal<'g, N, E> {
 335     graph: &'g Graph<N, E>,
 336     stack: Vec<NodeIndex>,
 337     visited: BitSet<usize>,
 338     direction: Direction,
 339 }
 340
 341 impl<'g, N: Debug, E: Debug> DepthFirstTraversal<'g, N, E> {
 342     pub fn with_start_node(
 343         graph: &'g Graph<N, E>,
 344         start_node: NodeIndex,
 345         direction: Direction,
 346     ) -> Self {
 347         let mut visited = BitSet::new_empty(graph.len_nodes());
 348         visited.insert(start_node.node_id());
 349         DepthFirstTraversal {
 350             graph,
 351             stack: vec![start_node],
 352             visited,
 353             direction,
 354         }
 355     }
 356
 357     fn visit(&mut self, node: NodeIndex) {
 358         if self.visited.insert(node.node_id()) {
 359             self.stack.push(node);
 360         }
 361     }
 362 }
 363
 364 impl<'g, N: Debug, E: Debug> Iterator for DepthFirstTraversal<'g, N, E> {
 365     type Item = NodeIndex;
 366
 367     fn next(&mut self) -> Option<NodeIndex> {
 368         let next = self.stack.pop();
 369         if let Some(idx) = next {
 370             for (_, edge) in self.graph.adjacent_edges(idx, self.direction) {
 371                 let target = edge.source_or_target(self.direction);
 372                 self.visit(target);
 373             }
 374         }
 375         next
 376     }
 377
 378     fn size_hint(&self) -> (usize, Option<usize>) {
 379         // We will visit every node in the graph exactly once.
 380         let remaining = self.graph.len_nodes() - self.visited.count();
 381         (remaining, Some(remaining))
 382     }
 383 }
 384
 385 impl<'g, N: Debug, E: Debug> ExactSizeIterator for DepthFirstTraversal<'g, N, E> {}
 386
 387 impl<E> Edge<E> {
 388     pub fn source(&self) -> NodeIndex {
 389         self.source
 390     }
 391
 392     pub fn target(&self) -> NodeIndex {
 393         self.target
 394     }
 395
 396     pub fn source_or_target(&self, direction: Direction) -> NodeIndex {
 397         if direction == OUTGOING {
 398             self.target
 399         } else {
 400             self.source
 401         }
 402     }
 403 }