From 9e7fb67838ce06e418d078c4d04b0ff578bd1f43 Mon Sep 17 00:00:00 2001 From: Zalathar Date: Tue, 6 May 2025 12:54:03 +1000 Subject: Rename `graph::implementation::Graph` to `LinkedGraph` --- .../src/graph/implementation/mod.rs | 347 -------------------- .../src/graph/implementation/tests.rs | 132 -------- .../src/graph/linked_graph/mod.rs | 363 +++++++++++++++++++++ .../src/graph/linked_graph/tests.rs | 132 ++++++++ compiler/rustc_data_structures/src/graph/mod.rs | 2 +- 5 files changed, 496 insertions(+), 480 deletions(-) delete mode 100644 compiler/rustc_data_structures/src/graph/implementation/mod.rs delete mode 100644 compiler/rustc_data_structures/src/graph/implementation/tests.rs create mode 100644 compiler/rustc_data_structures/src/graph/linked_graph/mod.rs create mode 100644 compiler/rustc_data_structures/src/graph/linked_graph/tests.rs (limited to 'compiler/rustc_data_structures/src/graph') diff --git a/compiler/rustc_data_structures/src/graph/implementation/mod.rs b/compiler/rustc_data_structures/src/graph/implementation/mod.rs deleted file mode 100644 index a80365938b9..00000000000 --- a/compiler/rustc_data_structures/src/graph/implementation/mod.rs +++ /dev/null @@ -1,347 +0,0 @@ -//! A graph module for use in dataflow, region resolution, and elsewhere. -//! -//! # Interface details -//! -//! You customize the graph by specifying a "node data" type `N` and an -//! "edge data" type `E`. You can then later gain access (mutable or -//! immutable) to these "user-data" bits. Currently, you can only add -//! nodes or edges to the graph. You cannot remove or modify them once -//! added. This could be changed if we have a need. -//! -//! # Implementation details -//! -//! The main tricky thing about this code is the way that edges are -//! stored. The edges are stored in a central array, but they are also -//! threaded onto two linked lists for each node, one for incoming edges -//! and one for outgoing edges. Note that every edge is a member of some -//! incoming list and some outgoing list. Basically you can load the -//! first index of the linked list from the node data structures (the -//! field `first_edge`) and then, for each edge, load the next index from -//! the field `next_edge`). Each of those fields is an array that should -//! be indexed by the direction (see the type `Direction`). - -use std::fmt::Debug; - -use rustc_index::bit_set::DenseBitSet; -use tracing::debug; - -#[cfg(test)] -mod tests; - -pub struct Graph { - nodes: Vec>, - edges: Vec>, -} - -pub struct Node { - first_edge: [EdgeIndex; 2], // see module comment - pub data: N, -} - -#[derive(Debug)] -pub struct Edge { - next_edge: [EdgeIndex; 2], // see module comment - source: NodeIndex, - target: NodeIndex, - pub data: E, -} - -#[derive(Copy, Clone, PartialEq, Debug)] -pub struct NodeIndex(pub usize); - -#[derive(Copy, Clone, PartialEq, Debug)] -pub struct EdgeIndex(pub usize); - -pub const INVALID_EDGE_INDEX: EdgeIndex = EdgeIndex(usize::MAX); - -// Use a private field here to guarantee no more instances are created: -#[derive(Copy, Clone, Debug, PartialEq)] -pub struct Direction { - repr: usize, -} - -pub const OUTGOING: Direction = Direction { repr: 0 }; - -pub const INCOMING: Direction = Direction { repr: 1 }; - -impl NodeIndex { - /// Returns unique ID (unique with respect to the graph holding associated node). - pub fn node_id(self) -> usize { - self.0 - } -} - -impl Graph { - pub fn new() -> Graph { - Graph { nodes: Vec::new(), edges: Vec::new() } - } - - pub fn with_capacity(nodes: usize, edges: usize) -> Graph { - Graph { nodes: Vec::with_capacity(nodes), edges: Vec::with_capacity(edges) } - } - - // # Simple accessors - - #[inline] - pub fn all_nodes(&self) -> &[Node] { - &self.nodes - } - - #[inline] - pub fn len_nodes(&self) -> usize { - self.nodes.len() - } - - #[inline] - pub fn all_edges(&self) -> &[Edge] { - &self.edges - } - - #[inline] - pub fn len_edges(&self) -> usize { - self.edges.len() - } - - // # Node construction - - pub fn next_node_index(&self) -> NodeIndex { - NodeIndex(self.nodes.len()) - } - - pub fn add_node(&mut self, data: N) -> NodeIndex { - let idx = self.next_node_index(); - self.nodes.push(Node { first_edge: [INVALID_EDGE_INDEX, INVALID_EDGE_INDEX], data }); - idx - } - - pub fn mut_node_data(&mut self, idx: NodeIndex) -> &mut N { - &mut self.nodes[idx.0].data - } - - pub fn node_data(&self, idx: NodeIndex) -> &N { - &self.nodes[idx.0].data - } - - pub fn node(&self, idx: NodeIndex) -> &Node { - &self.nodes[idx.0] - } - - // # Edge construction and queries - - pub fn next_edge_index(&self) -> EdgeIndex { - EdgeIndex(self.edges.len()) - } - - pub fn add_edge(&mut self, source: NodeIndex, target: NodeIndex, data: E) -> EdgeIndex { - debug!("graph: add_edge({:?}, {:?}, {:?})", source, target, data); - - let idx = self.next_edge_index(); - - // read current first of the list of edges from each node - let source_first = self.nodes[source.0].first_edge[OUTGOING.repr]; - let target_first = self.nodes[target.0].first_edge[INCOMING.repr]; - - // create the new edge, with the previous firsts from each node - // as the next pointers - self.edges.push(Edge { next_edge: [source_first, target_first], source, target, data }); - - // adjust the firsts for each node target be the next object. - self.nodes[source.0].first_edge[OUTGOING.repr] = idx; - self.nodes[target.0].first_edge[INCOMING.repr] = idx; - - idx - } - - pub fn edge(&self, idx: EdgeIndex) -> &Edge { - &self.edges[idx.0] - } - - // # Iterating over nodes, edges - - pub fn enumerated_nodes(&self) -> impl Iterator)> { - self.nodes.iter().enumerate().map(|(idx, n)| (NodeIndex(idx), n)) - } - - pub fn enumerated_edges(&self) -> impl Iterator)> { - self.edges.iter().enumerate().map(|(idx, e)| (EdgeIndex(idx), e)) - } - - pub fn each_node<'a>(&'a self, mut f: impl FnMut(NodeIndex, &'a Node) -> bool) -> bool { - //! Iterates over all edges defined in the graph. - self.enumerated_nodes().all(|(node_idx, node)| f(node_idx, node)) - } - - pub fn each_edge<'a>(&'a self, mut f: impl FnMut(EdgeIndex, &'a Edge) -> bool) -> bool { - //! Iterates over all edges defined in the graph - self.enumerated_edges().all(|(edge_idx, edge)| f(edge_idx, edge)) - } - - pub fn outgoing_edges(&self, source: NodeIndex) -> AdjacentEdges<'_, N, E> { - self.adjacent_edges(source, OUTGOING) - } - - pub fn incoming_edges(&self, source: NodeIndex) -> AdjacentEdges<'_, N, E> { - self.adjacent_edges(source, INCOMING) - } - - pub fn adjacent_edges( - &self, - source: NodeIndex, - direction: Direction, - ) -> AdjacentEdges<'_, N, E> { - let first_edge = self.node(source).first_edge[direction.repr]; - AdjacentEdges { graph: self, direction, next: first_edge } - } - - pub fn successor_nodes(&self, source: NodeIndex) -> impl Iterator { - self.outgoing_edges(source).targets() - } - - pub fn predecessor_nodes(&self, target: NodeIndex) -> impl Iterator { - self.incoming_edges(target).sources() - } - - pub fn depth_traverse( - &self, - start: NodeIndex, - direction: Direction, - ) -> DepthFirstTraversal<'_, N, E> { - DepthFirstTraversal::with_start_node(self, start, direction) - } - - pub fn nodes_in_postorder( - &self, - direction: Direction, - entry_node: NodeIndex, - ) -> Vec { - let mut visited = DenseBitSet::new_empty(self.len_nodes()); - let mut stack = vec![]; - let mut result = Vec::with_capacity(self.len_nodes()); - let mut push_node = |stack: &mut Vec<_>, node: NodeIndex| { - if visited.insert(node.0) { - stack.push((node, self.adjacent_edges(node, direction))); - } - }; - - for node in - Some(entry_node).into_iter().chain(self.enumerated_nodes().map(|(node, _)| node)) - { - push_node(&mut stack, node); - while let Some((node, mut iter)) = stack.pop() { - if let Some((_, child)) = iter.next() { - let target = child.source_or_target(direction); - // the current node needs more processing, so - // add it back to the stack - stack.push((node, iter)); - // and then push the new node - push_node(&mut stack, target); - } else { - result.push(node); - } - } - } - - assert_eq!(result.len(), self.len_nodes()); - result - } -} - -// # Iterators - -pub struct AdjacentEdges<'g, N, E> { - graph: &'g Graph, - direction: Direction, - next: EdgeIndex, -} - -impl<'g, N: Debug, E: Debug> AdjacentEdges<'g, N, E> { - fn targets(self) -> impl Iterator { - self.map(|(_, edge)| edge.target) - } - - fn sources(self) -> impl Iterator { - self.map(|(_, edge)| edge.source) - } -} - -impl<'g, N: Debug, E: Debug> Iterator for AdjacentEdges<'g, N, E> { - type Item = (EdgeIndex, &'g Edge); - - fn next(&mut self) -> Option<(EdgeIndex, &'g Edge)> { - let edge_index = self.next; - if edge_index == INVALID_EDGE_INDEX { - return None; - } - - let edge = self.graph.edge(edge_index); - self.next = edge.next_edge[self.direction.repr]; - Some((edge_index, edge)) - } - - fn size_hint(&self) -> (usize, Option) { - // At most, all the edges in the graph. - (0, Some(self.graph.len_edges())) - } -} - -pub struct DepthFirstTraversal<'g, N, E> { - graph: &'g Graph, - stack: Vec, - visited: DenseBitSet, - direction: Direction, -} - -impl<'g, N: Debug, E: Debug> DepthFirstTraversal<'g, N, E> { - pub fn with_start_node( - graph: &'g Graph, - start_node: NodeIndex, - direction: Direction, - ) -> Self { - let mut visited = DenseBitSet::new_empty(graph.len_nodes()); - visited.insert(start_node.node_id()); - DepthFirstTraversal { graph, stack: vec![start_node], visited, direction } - } - - fn visit(&mut self, node: NodeIndex) { - if self.visited.insert(node.node_id()) { - self.stack.push(node); - } - } -} - -impl<'g, N: Debug, E: Debug> Iterator for DepthFirstTraversal<'g, N, E> { - type Item = NodeIndex; - - fn next(&mut self) -> Option { - let next = self.stack.pop(); - if let Some(idx) = next { - for (_, edge) in self.graph.adjacent_edges(idx, self.direction) { - let target = edge.source_or_target(self.direction); - self.visit(target); - } - } - next - } - - fn size_hint(&self) -> (usize, Option) { - // We will visit every node in the graph exactly once. - let remaining = self.graph.len_nodes() - self.visited.count(); - (remaining, Some(remaining)) - } -} - -impl<'g, N: Debug, E: Debug> ExactSizeIterator for DepthFirstTraversal<'g, N, E> {} - -impl Edge { - pub fn source(&self) -> NodeIndex { - self.source - } - - pub fn target(&self) -> NodeIndex { - self.target - } - - pub fn source_or_target(&self, direction: Direction) -> NodeIndex { - if direction == OUTGOING { self.target } else { self.source } - } -} diff --git a/compiler/rustc_data_structures/src/graph/implementation/tests.rs b/compiler/rustc_data_structures/src/graph/implementation/tests.rs deleted file mode 100644 index 32a6d9ec881..00000000000 --- a/compiler/rustc_data_structures/src/graph/implementation/tests.rs +++ /dev/null @@ -1,132 +0,0 @@ -use tracing::debug; - -use crate::graph::implementation::*; - -type TestGraph = Graph<&'static str, &'static str>; - -fn create_graph() -> TestGraph { - let mut graph = Graph::new(); - - // Create a simple graph - // - // F - // | - // V - // A --> B --> C - // | ^ - // v | - // D --> E - - let a = graph.add_node("A"); - let b = graph.add_node("B"); - let c = graph.add_node("C"); - let d = graph.add_node("D"); - let e = graph.add_node("E"); - let f = graph.add_node("F"); - - graph.add_edge(a, b, "AB"); - graph.add_edge(b, c, "BC"); - graph.add_edge(b, d, "BD"); - graph.add_edge(d, e, "DE"); - graph.add_edge(e, c, "EC"); - graph.add_edge(f, b, "FB"); - - return graph; -} - -#[test] -fn each_node() { - let graph = create_graph(); - let expected = ["A", "B", "C", "D", "E", "F"]; - graph.each_node(|idx, node| { - assert_eq!(&expected[idx.0], graph.node_data(idx)); - assert_eq!(expected[idx.0], node.data); - true - }); -} - -#[test] -fn each_edge() { - let graph = create_graph(); - let expected = ["AB", "BC", "BD", "DE", "EC", "FB"]; - graph.each_edge(|idx, edge| { - assert_eq!(expected[idx.0], edge.data); - true - }); -} - -fn test_adjacent_edges( - graph: &Graph, - start_index: NodeIndex, - start_data: N, - expected_incoming: &[(E, N)], - expected_outgoing: &[(E, N)], -) { - assert!(graph.node_data(start_index) == &start_data); - - let mut counter = 0; - for (edge_index, edge) in graph.incoming_edges(start_index) { - assert!(counter < expected_incoming.len()); - debug!( - "counter={:?} expected={:?} edge_index={:?} edge={:?}", - counter, expected_incoming[counter], edge_index, edge - ); - match &expected_incoming[counter] { - (e, n) => { - assert!(e == &edge.data); - assert!(n == graph.node_data(edge.source())); - assert!(start_index == edge.target); - } - } - counter += 1; - } - assert_eq!(counter, expected_incoming.len()); - - let mut counter = 0; - for (edge_index, edge) in graph.outgoing_edges(start_index) { - assert!(counter < expected_outgoing.len()); - debug!( - "counter={:?} expected={:?} edge_index={:?} edge={:?}", - counter, expected_outgoing[counter], edge_index, edge - ); - match &expected_outgoing[counter] { - (e, n) => { - assert!(e == &edge.data); - assert!(start_index == edge.source); - assert!(n == graph.node_data(edge.target)); - } - } - counter += 1; - } - assert_eq!(counter, expected_outgoing.len()); -} - -#[test] -fn each_adjacent_from_a() { - let graph = create_graph(); - test_adjacent_edges(&graph, NodeIndex(0), "A", &[], &[("AB", "B")]); -} - -#[test] -fn each_adjacent_from_b() { - let graph = create_graph(); - test_adjacent_edges( - &graph, - NodeIndex(1), - "B", - &[("FB", "F"), ("AB", "A")], - &[("BD", "D"), ("BC", "C")], - ); -} - -#[test] -fn each_adjacent_from_c() { - let graph = create_graph(); - test_adjacent_edges(&graph, NodeIndex(2), "C", &[("EC", "E"), ("BC", "B")], &[]); -} - -#[test] -fn each_adjacent_from_d() { - let graph = create_graph(); - test_adjacent_edges(&graph, NodeIndex(3), "D", &[("BD", "B")], &[("DE", "E")]); -} diff --git a/compiler/rustc_data_structures/src/graph/linked_graph/mod.rs b/compiler/rustc_data_structures/src/graph/linked_graph/mod.rs new file mode 100644 index 00000000000..ecb0095626b --- /dev/null +++ b/compiler/rustc_data_structures/src/graph/linked_graph/mod.rs @@ -0,0 +1,363 @@ +//! See [`LinkedGraph`]. +//! +//! # Interface details +//! +//! You customize the graph by specifying a "node data" type `N` and an +//! "edge data" type `E`. You can then later gain access (mutable or +//! immutable) to these "user-data" bits. Currently, you can only add +//! nodes or edges to the graph. You cannot remove or modify them once +//! added. This could be changed if we have a need. +//! +//! # Implementation details +//! +//! The main tricky thing about this code is the way that edges are +//! stored. The edges are stored in a central array, but they are also +//! threaded onto two linked lists for each node, one for incoming edges +//! and one for outgoing edges. Note that every edge is a member of some +//! incoming list and some outgoing list. Basically you can load the +//! first index of the linked list from the node data structures (the +//! field `first_edge`) and then, for each edge, load the next index from +//! the field `next_edge`). Each of those fields is an array that should +//! be indexed by the direction (see the type `Direction`). + +use std::fmt::Debug; + +use rustc_index::bit_set::DenseBitSet; +use tracing::debug; + +#[cfg(test)] +mod tests; + +/// A concrete graph implementation that supports: +/// - Nodes and/or edges labelled with custom data types (`N` and `E` respectively). +/// - Incremental addition of new nodes/edges (but not removal). +/// - Flat storage of node/edge data in a pair of vectors. +/// - Iteration over any node's out-edges or in-edges, via linked lists +/// threaded through the node/edge data. +/// +/// # Caution +/// This is an older graph implementation that is still used by some pieces +/// of diagnostic/debugging code. New code that needs a graph data structure +/// should consider using `VecGraph` instead, or implementing its own +/// special-purpose graph with the specific features needed. +/// +/// This graph implementation predates the later [graph traits](crate::graph), +/// and does not implement those traits, so it has its own implementations of a +/// few basic graph algorithms. +pub struct LinkedGraph { + nodes: Vec>, + edges: Vec>, +} + +pub struct Node { + first_edge: [EdgeIndex; 2], // see module comment + pub data: N, +} + +#[derive(Debug)] +pub struct Edge { + next_edge: [EdgeIndex; 2], // see module comment + source: NodeIndex, + target: NodeIndex, + pub data: E, +} + +#[derive(Copy, Clone, PartialEq, Debug)] +pub struct NodeIndex(pub usize); + +#[derive(Copy, Clone, PartialEq, Debug)] +pub struct EdgeIndex(pub usize); + +pub const INVALID_EDGE_INDEX: EdgeIndex = EdgeIndex(usize::MAX); + +// Use a private field here to guarantee no more instances are created: +#[derive(Copy, Clone, Debug, PartialEq)] +pub struct Direction { + repr: usize, +} + +pub const OUTGOING: Direction = Direction { repr: 0 }; + +pub const INCOMING: Direction = Direction { repr: 1 }; + +impl NodeIndex { + /// Returns unique ID (unique with respect to the graph holding associated node). + pub fn node_id(self) -> usize { + self.0 + } +} + +impl LinkedGraph { + pub fn new() -> Self { + Self { nodes: Vec::new(), edges: Vec::new() } + } + + pub fn with_capacity(nodes: usize, edges: usize) -> Self { + Self { nodes: Vec::with_capacity(nodes), edges: Vec::with_capacity(edges) } + } + + // # Simple accessors + + #[inline] + pub fn all_nodes(&self) -> &[Node] { + &self.nodes + } + + #[inline] + pub fn len_nodes(&self) -> usize { + self.nodes.len() + } + + #[inline] + pub fn all_edges(&self) -> &[Edge] { + &self.edges + } + + #[inline] + pub fn len_edges(&self) -> usize { + self.edges.len() + } + + // # Node construction + + pub fn next_node_index(&self) -> NodeIndex { + NodeIndex(self.nodes.len()) + } + + pub fn add_node(&mut self, data: N) -> NodeIndex { + let idx = self.next_node_index(); + self.nodes.push(Node { first_edge: [INVALID_EDGE_INDEX, INVALID_EDGE_INDEX], data }); + idx + } + + pub fn mut_node_data(&mut self, idx: NodeIndex) -> &mut N { + &mut self.nodes[idx.0].data + } + + pub fn node_data(&self, idx: NodeIndex) -> &N { + &self.nodes[idx.0].data + } + + pub fn node(&self, idx: NodeIndex) -> &Node { + &self.nodes[idx.0] + } + + // # Edge construction and queries + + pub fn next_edge_index(&self) -> EdgeIndex { + EdgeIndex(self.edges.len()) + } + + pub fn add_edge(&mut self, source: NodeIndex, target: NodeIndex, data: E) -> EdgeIndex { + debug!("graph: add_edge({:?}, {:?}, {:?})", source, target, data); + + let idx = self.next_edge_index(); + + // read current first of the list of edges from each node + let source_first = self.nodes[source.0].first_edge[OUTGOING.repr]; + let target_first = self.nodes[target.0].first_edge[INCOMING.repr]; + + // create the new edge, with the previous firsts from each node + // as the next pointers + self.edges.push(Edge { next_edge: [source_first, target_first], source, target, data }); + + // adjust the firsts for each node target be the next object. + self.nodes[source.0].first_edge[OUTGOING.repr] = idx; + self.nodes[target.0].first_edge[INCOMING.repr] = idx; + + idx + } + + pub fn edge(&self, idx: EdgeIndex) -> &Edge { + &self.edges[idx.0] + } + + // # Iterating over nodes, edges + + pub fn enumerated_nodes(&self) -> impl Iterator)> { + self.nodes.iter().enumerate().map(|(idx, n)| (NodeIndex(idx), n)) + } + + pub fn enumerated_edges(&self) -> impl Iterator)> { + self.edges.iter().enumerate().map(|(idx, e)| (EdgeIndex(idx), e)) + } + + pub fn each_node<'a>(&'a self, mut f: impl FnMut(NodeIndex, &'a Node) -> bool) -> bool { + //! Iterates over all edges defined in the graph. + self.enumerated_nodes().all(|(node_idx, node)| f(node_idx, node)) + } + + pub fn each_edge<'a>(&'a self, mut f: impl FnMut(EdgeIndex, &'a Edge) -> bool) -> bool { + //! Iterates over all edges defined in the graph + self.enumerated_edges().all(|(edge_idx, edge)| f(edge_idx, edge)) + } + + pub fn outgoing_edges(&self, source: NodeIndex) -> AdjacentEdges<'_, N, E> { + self.adjacent_edges(source, OUTGOING) + } + + pub fn incoming_edges(&self, source: NodeIndex) -> AdjacentEdges<'_, N, E> { + self.adjacent_edges(source, INCOMING) + } + + pub fn adjacent_edges( + &self, + source: NodeIndex, + direction: Direction, + ) -> AdjacentEdges<'_, N, E> { + let first_edge = self.node(source).first_edge[direction.repr]; + AdjacentEdges { graph: self, direction, next: first_edge } + } + + pub fn successor_nodes(&self, source: NodeIndex) -> impl Iterator { + self.outgoing_edges(source).targets() + } + + pub fn predecessor_nodes(&self, target: NodeIndex) -> impl Iterator { + self.incoming_edges(target).sources() + } + + pub fn depth_traverse( + &self, + start: NodeIndex, + direction: Direction, + ) -> DepthFirstTraversal<'_, N, E> { + DepthFirstTraversal::with_start_node(self, start, direction) + } + + pub fn nodes_in_postorder( + &self, + direction: Direction, + entry_node: NodeIndex, + ) -> Vec { + let mut visited = DenseBitSet::new_empty(self.len_nodes()); + let mut stack = vec![]; + let mut result = Vec::with_capacity(self.len_nodes()); + let mut push_node = |stack: &mut Vec<_>, node: NodeIndex| { + if visited.insert(node.0) { + stack.push((node, self.adjacent_edges(node, direction))); + } + }; + + for node in + Some(entry_node).into_iter().chain(self.enumerated_nodes().map(|(node, _)| node)) + { + push_node(&mut stack, node); + while let Some((node, mut iter)) = stack.pop() { + if let Some((_, child)) = iter.next() { + let target = child.source_or_target(direction); + // the current node needs more processing, so + // add it back to the stack + stack.push((node, iter)); + // and then push the new node + push_node(&mut stack, target); + } else { + result.push(node); + } + } + } + + assert_eq!(result.len(), self.len_nodes()); + result + } +} + +// # Iterators + +pub struct AdjacentEdges<'g, N, E> { + graph: &'g LinkedGraph, + direction: Direction, + next: EdgeIndex, +} + +impl<'g, N: Debug, E: Debug> AdjacentEdges<'g, N, E> { + fn targets(self) -> impl Iterator { + self.map(|(_, edge)| edge.target) + } + + fn sources(self) -> impl Iterator { + self.map(|(_, edge)| edge.source) + } +} + +impl<'g, N: Debug, E: Debug> Iterator for AdjacentEdges<'g, N, E> { + type Item = (EdgeIndex, &'g Edge); + + fn next(&mut self) -> Option<(EdgeIndex, &'g Edge)> { + let edge_index = self.next; + if edge_index == INVALID_EDGE_INDEX { + return None; + } + + let edge = self.graph.edge(edge_index); + self.next = edge.next_edge[self.direction.repr]; + Some((edge_index, edge)) + } + + fn size_hint(&self) -> (usize, Option) { + // At most, all the edges in the graph. + (0, Some(self.graph.len_edges())) + } +} + +pub struct DepthFirstTraversal<'g, N, E> { + graph: &'g LinkedGraph, + stack: Vec, + visited: DenseBitSet, + direction: Direction, +} + +impl<'g, N: Debug, E: Debug> DepthFirstTraversal<'g, N, E> { + pub fn with_start_node( + graph: &'g LinkedGraph, + start_node: NodeIndex, + direction: Direction, + ) -> Self { + let mut visited = DenseBitSet::new_empty(graph.len_nodes()); + visited.insert(start_node.node_id()); + DepthFirstTraversal { graph, stack: vec![start_node], visited, direction } + } + + fn visit(&mut self, node: NodeIndex) { + if self.visited.insert(node.node_id()) { + self.stack.push(node); + } + } +} + +impl<'g, N: Debug, E: Debug> Iterator for DepthFirstTraversal<'g, N, E> { + type Item = NodeIndex; + + fn next(&mut self) -> Option { + let next = self.stack.pop(); + if let Some(idx) = next { + for (_, edge) in self.graph.adjacent_edges(idx, self.direction) { + let target = edge.source_or_target(self.direction); + self.visit(target); + } + } + next + } + + fn size_hint(&self) -> (usize, Option) { + // We will visit every node in the graph exactly once. + let remaining = self.graph.len_nodes() - self.visited.count(); + (remaining, Some(remaining)) + } +} + +impl<'g, N: Debug, E: Debug> ExactSizeIterator for DepthFirstTraversal<'g, N, E> {} + +impl Edge { + pub fn source(&self) -> NodeIndex { + self.source + } + + pub fn target(&self) -> NodeIndex { + self.target + } + + pub fn source_or_target(&self, direction: Direction) -> NodeIndex { + if direction == OUTGOING { self.target } else { self.source } + } +} diff --git a/compiler/rustc_data_structures/src/graph/linked_graph/tests.rs b/compiler/rustc_data_structures/src/graph/linked_graph/tests.rs new file mode 100644 index 00000000000..357aa81a57c --- /dev/null +++ b/compiler/rustc_data_structures/src/graph/linked_graph/tests.rs @@ -0,0 +1,132 @@ +use tracing::debug; + +use super::{Debug, LinkedGraph, NodeIndex}; + +type TestGraph = LinkedGraph<&'static str, &'static str>; + +fn create_graph() -> TestGraph { + let mut graph = LinkedGraph::new(); + + // Create a simple graph + // + // F + // | + // V + // A --> B --> C + // | ^ + // v | + // D --> E + + let a = graph.add_node("A"); + let b = graph.add_node("B"); + let c = graph.add_node("C"); + let d = graph.add_node("D"); + let e = graph.add_node("E"); + let f = graph.add_node("F"); + + graph.add_edge(a, b, "AB"); + graph.add_edge(b, c, "BC"); + graph.add_edge(b, d, "BD"); + graph.add_edge(d, e, "DE"); + graph.add_edge(e, c, "EC"); + graph.add_edge(f, b, "FB"); + + return graph; +} + +#[test] +fn each_node() { + let graph = create_graph(); + let expected = ["A", "B", "C", "D", "E", "F"]; + graph.each_node(|idx, node| { + assert_eq!(&expected[idx.0], graph.node_data(idx)); + assert_eq!(expected[idx.0], node.data); + true + }); +} + +#[test] +fn each_edge() { + let graph = create_graph(); + let expected = ["AB", "BC", "BD", "DE", "EC", "FB"]; + graph.each_edge(|idx, edge| { + assert_eq!(expected[idx.0], edge.data); + true + }); +} + +fn test_adjacent_edges( + graph: &LinkedGraph, + start_index: NodeIndex, + start_data: N, + expected_incoming: &[(E, N)], + expected_outgoing: &[(E, N)], +) { + assert!(graph.node_data(start_index) == &start_data); + + let mut counter = 0; + for (edge_index, edge) in graph.incoming_edges(start_index) { + assert!(counter < expected_incoming.len()); + debug!( + "counter={:?} expected={:?} edge_index={:?} edge={:?}", + counter, expected_incoming[counter], edge_index, edge + ); + match &expected_incoming[counter] { + (e, n) => { + assert!(e == &edge.data); + assert!(n == graph.node_data(edge.source())); + assert!(start_index == edge.target); + } + } + counter += 1; + } + assert_eq!(counter, expected_incoming.len()); + + let mut counter = 0; + for (edge_index, edge) in graph.outgoing_edges(start_index) { + assert!(counter < expected_outgoing.len()); + debug!( + "counter={:?} expected={:?} edge_index={:?} edge={:?}", + counter, expected_outgoing[counter], edge_index, edge + ); + match &expected_outgoing[counter] { + (e, n) => { + assert!(e == &edge.data); + assert!(start_index == edge.source); + assert!(n == graph.node_data(edge.target)); + } + } + counter += 1; + } + assert_eq!(counter, expected_outgoing.len()); +} + +#[test] +fn each_adjacent_from_a() { + let graph = create_graph(); + test_adjacent_edges(&graph, NodeIndex(0), "A", &[], &[("AB", "B")]); +} + +#[test] +fn each_adjacent_from_b() { + let graph = create_graph(); + test_adjacent_edges( + &graph, + NodeIndex(1), + "B", + &[("FB", "F"), ("AB", "A")], + &[("BD", "D"), ("BC", "C")], + ); +} + +#[test] +fn each_adjacent_from_c() { + let graph = create_graph(); + test_adjacent_edges(&graph, NodeIndex(2), "C", &[("EC", "E"), ("BC", "B")], &[]); +} + +#[test] +fn each_adjacent_from_d() { + let graph = create_graph(); + test_adjacent_edges(&graph, NodeIndex(3), "D", &[("BD", "B")], &[("DE", "E")]); +} diff --git a/compiler/rustc_data_structures/src/graph/mod.rs b/compiler/rustc_data_structures/src/graph/mod.rs index 4a1e5db6768..20416b472b2 100644 --- a/compiler/rustc_data_structures/src/graph/mod.rs +++ b/compiler/rustc_data_structures/src/graph/mod.rs @@ -1,8 +1,8 @@ use rustc_index::Idx; pub mod dominators; -pub mod implementation; pub mod iterate; +pub mod linked_graph; mod reference; pub mod reversed; pub mod scc; -- cgit 1.4.1-3-g733a5