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