diff options
Diffstat (limited to 'compiler/rustc_data_structures/src/graph')
13 files changed, 1851 insertions, 0 deletions
diff --git a/compiler/rustc_data_structures/src/graph/dominators/mod.rs b/compiler/rustc_data_structures/src/graph/dominators/mod.rs new file mode 100644 index 00000000000..438a0d0c6ff --- /dev/null +++ b/compiler/rustc_data_structures/src/graph/dominators/mod.rs @@ -0,0 +1,134 @@ +//! Finding the dominators in a control-flow graph. +//! +//! Algorithm based on Keith D. Cooper, Timothy J. Harvey, and Ken Kennedy, +//! "A Simple, Fast Dominance Algorithm", +//! Rice Computer Science TS-06-33870, +//! <https://www.cs.rice.edu/~keith/EMBED/dom.pdf>. + +use super::iterate::reverse_post_order; +use super::ControlFlowGraph; +use rustc_index::vec::{Idx, IndexVec}; +use std::borrow::BorrowMut; + +#[cfg(test)] +mod tests; + +pub fn dominators<G: ControlFlowGraph>(graph: G) -> Dominators<G::Node> { + let start_node = graph.start_node(); + let rpo = reverse_post_order(&graph, start_node); + dominators_given_rpo(graph, &rpo) +} + +fn dominators_given_rpo<G: ControlFlowGraph + BorrowMut<G>>( + mut graph: G, + rpo: &[G::Node], +) -> Dominators<G::Node> { + let start_node = graph.borrow().start_node(); + assert_eq!(rpo[0], start_node); + + // compute the post order index (rank) for each node + let mut post_order_rank: IndexVec<G::Node, usize> = + (0..graph.borrow().num_nodes()).map(|_| 0).collect(); + for (index, node) in rpo.iter().rev().cloned().enumerate() { + post_order_rank[node] = index; + } + + let mut immediate_dominators: IndexVec<G::Node, Option<G::Node>> = + (0..graph.borrow().num_nodes()).map(|_| None).collect(); + immediate_dominators[start_node] = Some(start_node); + + let mut changed = true; + while changed { + changed = false; + + for &node in &rpo[1..] { + let mut new_idom = None; + for pred in graph.borrow_mut().predecessors(node) { + if immediate_dominators[pred].is_some() { + // (*) dominators for `pred` have been calculated + new_idom = Some(if let Some(new_idom) = new_idom { + intersect(&post_order_rank, &immediate_dominators, new_idom, pred) + } else { + pred + }); + } + } + + if new_idom != immediate_dominators[node] { + immediate_dominators[node] = new_idom; + changed = true; + } + } + } + + Dominators { post_order_rank, immediate_dominators } +} + +fn intersect<Node: Idx>( + post_order_rank: &IndexVec<Node, usize>, + immediate_dominators: &IndexVec<Node, Option<Node>>, + mut node1: Node, + mut node2: Node, +) -> Node { + while node1 != node2 { + while post_order_rank[node1] < post_order_rank[node2] { + node1 = immediate_dominators[node1].unwrap(); + } + + while post_order_rank[node2] < post_order_rank[node1] { + node2 = immediate_dominators[node2].unwrap(); + } + } + + node1 +} + +#[derive(Clone, Debug)] +pub struct Dominators<N: Idx> { + post_order_rank: IndexVec<N, usize>, + immediate_dominators: IndexVec<N, Option<N>>, +} + +impl<Node: Idx> Dominators<Node> { + pub fn is_reachable(&self, node: Node) -> bool { + self.immediate_dominators[node].is_some() + } + + pub fn immediate_dominator(&self, node: Node) -> Node { + assert!(self.is_reachable(node), "node {:?} is not reachable", node); + self.immediate_dominators[node].unwrap() + } + + pub fn dominators(&self, node: Node) -> Iter<'_, Node> { + assert!(self.is_reachable(node), "node {:?} is not reachable", node); + Iter { dominators: self, node: Some(node) } + } + + pub fn is_dominated_by(&self, node: Node, dom: Node) -> bool { + // FIXME -- could be optimized by using post-order-rank + self.dominators(node).any(|n| n == dom) + } +} + +pub struct Iter<'dom, Node: Idx> { + dominators: &'dom Dominators<Node>, + node: Option<Node>, +} + +impl<'dom, Node: Idx> Iterator for Iter<'dom, Node> { + type Item = Node; + + fn next(&mut self) -> Option<Self::Item> { + if let Some(node) = self.node { + let dom = self.dominators.immediate_dominator(node); + if dom == node { + self.node = None; // reached the root + } else { + self.node = Some(dom); + } + Some(node) + } else { + None + } + } +} diff --git a/compiler/rustc_data_structures/src/graph/dominators/tests.rs b/compiler/rustc_data_structures/src/graph/dominators/tests.rs new file mode 100644 index 00000000000..1160df5186b --- /dev/null +++ b/compiler/rustc_data_structures/src/graph/dominators/tests.rs @@ -0,0 +1,34 @@ +use super::*; + +use super::super::tests::TestGraph; + +#[test] +fn diamond() { + let graph = TestGraph::new(0, &[(0, 1), (0, 2), (1, 3), (2, 3)]); + + let dominators = dominators(&graph); + let immediate_dominators = &dominators.immediate_dominators; + assert_eq!(immediate_dominators[0], Some(0)); + assert_eq!(immediate_dominators[1], Some(0)); + assert_eq!(immediate_dominators[2], Some(0)); + assert_eq!(immediate_dominators[3], Some(0)); +} + +#[test] +fn paper() { + // example from the paper: + let graph = TestGraph::new( + 6, + &[(6, 5), (6, 4), (5, 1), (4, 2), (4, 3), (1, 2), (2, 3), (3, 2), (2, 1)], + ); + + let dominators = dominators(&graph); + let immediate_dominators = &dominators.immediate_dominators; + assert_eq!(immediate_dominators[0], None); // <-- note that 0 is not in graph + assert_eq!(immediate_dominators[1], Some(6)); + assert_eq!(immediate_dominators[2], Some(6)); + assert_eq!(immediate_dominators[3], Some(6)); + assert_eq!(immediate_dominators[4], Some(6)); + assert_eq!(immediate_dominators[5], Some(6)); + assert_eq!(immediate_dominators[6], Some(6)); +} diff --git a/compiler/rustc_data_structures/src/graph/implementation/mod.rs b/compiler/rustc_data_structures/src/graph/implementation/mod.rs new file mode 100644 index 00000000000..1aa7ac024d9 --- /dev/null +++ b/compiler/rustc_data_structures/src/graph/implementation/mod.rs @@ -0,0 +1,366 @@ +//! 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 crate::snapshot_vec::{SnapshotVec, SnapshotVecDelegate}; +use rustc_index::bit_set::BitSet; +use std::fmt::Debug; + +#[cfg(test)] +mod tests; + +pub struct Graph<N, E> { + nodes: SnapshotVec<Node<N>>, + edges: SnapshotVec<Edge<E>>, +} + +pub struct Node<N> { + first_edge: [EdgeIndex; 2], // see module comment + pub data: N, +} + +#[derive(Debug)] +pub struct Edge<E> { + next_edge: [EdgeIndex; 2], // see module comment + source: NodeIndex, + target: NodeIndex, + pub data: E, +} + +impl<N> SnapshotVecDelegate for Node<N> { + type Value = Node<N>; + type Undo = (); + + fn reverse(_: &mut Vec<Node<N>>, _: ()) {} +} + +impl<N> SnapshotVecDelegate for Edge<N> { + type Value = Edge<N>; + type Undo = (); + + fn reverse(_: &mut Vec<Edge<N>>, _: ()) {} +} + +#[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<N: Debug, E: Debug> Graph<N, E> { + pub fn new() -> Graph<N, E> { + Graph { nodes: SnapshotVec::new(), edges: SnapshotVec::new() } + } + + pub fn with_capacity(nodes: usize, edges: usize) -> Graph<N, E> { + Graph { nodes: SnapshotVec::with_capacity(nodes), edges: SnapshotVec::with_capacity(edges) } + } + + // # Simple accessors + + #[inline] + pub fn all_nodes(&self) -> &[Node<N>] { + &self.nodes + } + + #[inline] + pub fn len_nodes(&self) -> usize { + self.nodes.len() + } + + #[inline] + pub fn all_edges(&self) -> &[Edge<E>] { + &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<N> { + &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<E> { + &self.edges[idx.0] + } + + // # Iterating over nodes, edges + + pub fn enumerated_nodes(&self) -> impl Iterator<Item = (NodeIndex, &Node<N>)> { + self.nodes.iter().enumerate().map(|(idx, n)| (NodeIndex(idx), n)) + } + + pub fn enumerated_edges(&self) -> impl Iterator<Item = (EdgeIndex, &Edge<E>)> { + self.edges.iter().enumerate().map(|(idx, e)| (EdgeIndex(idx), e)) + } + + pub fn each_node<'a>(&'a self, mut f: impl FnMut(NodeIndex, &'a Node<N>) -> 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<E>) -> 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<'a>( + &'a self, + source: NodeIndex, + ) -> impl Iterator<Item = NodeIndex> + 'a { + self.outgoing_edges(source).targets() + } + + pub fn predecessor_nodes<'a>( + &'a self, + target: NodeIndex, + ) -> impl Iterator<Item = NodeIndex> + 'a { + 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<NodeIndex> { + let mut visited = BitSet::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<N, E>, + direction: Direction, + next: EdgeIndex, +} + +impl<'g, N: Debug, E: Debug> AdjacentEdges<'g, N, E> { + fn targets(self) -> impl Iterator<Item = NodeIndex> + 'g { + self.map(|(_, edge)| edge.target) + } + + fn sources(self) -> impl Iterator<Item = NodeIndex> + 'g { + self.map(|(_, edge)| edge.source) + } +} + +impl<'g, N: Debug, E: Debug> Iterator for AdjacentEdges<'g, N, E> { + type Item = (EdgeIndex, &'g Edge<E>); + + fn next(&mut self) -> Option<(EdgeIndex, &'g Edge<E>)> { + 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<usize>) { + // At most, all the edges in the graph. + (0, Some(self.graph.len_edges())) + } +} + +pub struct DepthFirstTraversal<'g, N, E> { + graph: &'g Graph<N, E>, + stack: Vec<NodeIndex>, + visited: BitSet<usize>, + direction: Direction, +} + +impl<'g, N: Debug, E: Debug> DepthFirstTraversal<'g, N, E> { + pub fn with_start_node( + graph: &'g Graph<N, E>, + start_node: NodeIndex, + direction: Direction, + ) -> Self { + let mut visited = BitSet::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<NodeIndex> { + 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<usize>) { + // 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<E> Edge<E> { + 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 new file mode 100644 index 00000000000..e4e4d0d44ba --- /dev/null +++ b/compiler/rustc_data_structures/src/graph/implementation/tests.rs @@ -0,0 +1,131 @@ +use crate::graph::implementation::*; +use std::fmt::Debug; + +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<N: PartialEq + Debug, E: PartialEq + Debug>( + graph: &Graph<N, E>, + 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] { + (ref e, ref 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] { + (ref e, ref 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/iterate/mod.rs b/compiler/rustc_data_structures/src/graph/iterate/mod.rs new file mode 100644 index 00000000000..64ff6130ddf --- /dev/null +++ b/compiler/rustc_data_structures/src/graph/iterate/mod.rs @@ -0,0 +1,296 @@ +use super::{DirectedGraph, WithNumNodes, WithStartNode, WithSuccessors}; +use rustc_index::bit_set::BitSet; +use rustc_index::vec::IndexVec; + +#[cfg(test)] +mod tests; + +pub fn post_order_from<G: DirectedGraph + WithSuccessors + WithNumNodes>( + graph: &G, + start_node: G::Node, +) -> Vec<G::Node> { + post_order_from_to(graph, start_node, None) +} + +pub fn post_order_from_to<G: DirectedGraph + WithSuccessors + WithNumNodes>( + graph: &G, + start_node: G::Node, + end_node: Option<G::Node>, +) -> Vec<G::Node> { + let mut visited: IndexVec<G::Node, bool> = IndexVec::from_elem_n(false, graph.num_nodes()); + let mut result: Vec<G::Node> = Vec::with_capacity(graph.num_nodes()); + if let Some(end_node) = end_node { + visited[end_node] = true; + } + post_order_walk(graph, start_node, &mut result, &mut visited); + result +} + +fn post_order_walk<G: DirectedGraph + WithSuccessors + WithNumNodes>( + graph: &G, + node: G::Node, + result: &mut Vec<G::Node>, + visited: &mut IndexVec<G::Node, bool>, +) { + if visited[node] { + return; + } + visited[node] = true; + + for successor in graph.successors(node) { + post_order_walk(graph, successor, result, visited); + } + + result.push(node); +} + +pub fn reverse_post_order<G: DirectedGraph + WithSuccessors + WithNumNodes>( + graph: &G, + start_node: G::Node, +) -> Vec<G::Node> { + let mut vec = post_order_from(graph, start_node); + vec.reverse(); + vec +} + +/// A "depth-first search" iterator for a directed graph. +pub struct DepthFirstSearch<'graph, G> +where + G: ?Sized + DirectedGraph + WithNumNodes + WithSuccessors, +{ + graph: &'graph G, + stack: Vec<G::Node>, + visited: BitSet<G::Node>, +} + +impl<G> DepthFirstSearch<'graph, G> +where + G: ?Sized + DirectedGraph + WithNumNodes + WithSuccessors, +{ + pub fn new(graph: &'graph G, start_node: G::Node) -> Self { + Self { graph, stack: vec![start_node], visited: BitSet::new_empty(graph.num_nodes()) } + } +} + +impl<G> Iterator for DepthFirstSearch<'_, G> +where + G: ?Sized + DirectedGraph + WithNumNodes + WithSuccessors, +{ + type Item = G::Node; + + fn next(&mut self) -> Option<G::Node> { + let DepthFirstSearch { stack, visited, graph } = self; + let n = stack.pop()?; + stack.extend(graph.successors(n).filter(|&m| visited.insert(m))); + Some(n) + } +} + +/// Allows searches to terminate early with a value. +#[derive(Clone, Copy, Debug)] +pub enum ControlFlow<T> { + Break(T), + Continue, +} + +/// The status of a node in the depth-first search. +/// +/// See the documentation of `TriColorDepthFirstSearch` to see how a node's status is updated +/// during DFS. +#[derive(Clone, Copy, Debug, PartialEq, Eq)] +pub enum NodeStatus { + /// This node has been examined by the depth-first search but is not yet `Settled`. + /// + /// Also referred to as "gray" or "discovered" nodes in [CLR]. + /// + /// [CLR]: https://en.wikipedia.org/wiki/Introduction_to_Algorithms + Visited, + + /// This node and all nodes reachable from it have been examined by the depth-first search. + /// + /// Also referred to as "black" or "finished" nodes in [CLR]. + /// + /// [CLR]: https://en.wikipedia.org/wiki/Introduction_to_Algorithms + Settled, +} + +struct Event<N> { + node: N, + becomes: NodeStatus, +} + +/// A depth-first search that also tracks when all successors of a node have been examined. +/// +/// This is based on the DFS described in [Introduction to Algorithms (1st ed.)][CLR], hereby +/// referred to as **CLR**. However, we use the terminology in [`NodeStatus`] above instead of +/// "discovered"/"finished" or "white"/"grey"/"black". Each node begins the search with no status, +/// becomes `Visited` when it is first examined by the DFS and is `Settled` when all nodes +/// reachable from it have been examined. This allows us to differentiate between "tree", "back" +/// and "forward" edges (see [`TriColorVisitor::node_examined`]). +/// +/// Unlike the pseudocode in [CLR], this implementation is iterative and does not use timestamps. +/// We accomplish this by storing `Event`s on the stack that result in a (possible) state change +/// for each node. A `Visited` event signifies that we should examine this node if it has not yet +/// been `Visited` or `Settled`. When a node is examined for the first time, we mark it as +/// `Visited` and push a `Settled` event for it on stack followed by `Visited` events for all of +/// its predecessors, scheduling them for examination. Multiple `Visited` events for a single node +/// may exist on the stack simultaneously if a node has multiple predecessors, but only one +/// `Settled` event will ever be created for each node. After all `Visited` events for a node's +/// successors have been popped off the stack (as well as any new events triggered by visiting +/// those successors), we will pop off that node's `Settled` event. +/// +/// [CLR]: https://en.wikipedia.org/wiki/Introduction_to_Algorithms +/// [`NodeStatus`]: ./enum.NodeStatus.html +/// [`TriColorVisitor::node_examined`]: ./trait.TriColorVisitor.html#method.node_examined +pub struct TriColorDepthFirstSearch<'graph, G> +where + G: ?Sized + DirectedGraph + WithNumNodes + WithSuccessors, +{ + graph: &'graph G, + stack: Vec<Event<G::Node>>, + visited: BitSet<G::Node>, + settled: BitSet<G::Node>, +} + +impl<G> TriColorDepthFirstSearch<'graph, G> +where + G: ?Sized + DirectedGraph + WithNumNodes + WithSuccessors, +{ + pub fn new(graph: &'graph G) -> Self { + TriColorDepthFirstSearch { + graph, + stack: vec![], + visited: BitSet::new_empty(graph.num_nodes()), + settled: BitSet::new_empty(graph.num_nodes()), + } + } + + /// Performs a depth-first search, starting from the given `root`. + /// + /// This won't visit nodes that are not reachable from `root`. + pub fn run_from<V>(mut self, root: G::Node, visitor: &mut V) -> Option<V::BreakVal> + where + V: TriColorVisitor<G>, + { + use NodeStatus::{Settled, Visited}; + + self.stack.push(Event { node: root, becomes: Visited }); + + loop { + match self.stack.pop()? { + Event { node, becomes: Settled } => { + let not_previously_settled = self.settled.insert(node); + assert!(not_previously_settled, "A node should be settled exactly once"); + if let ControlFlow::Break(val) = visitor.node_settled(node) { + return Some(val); + } + } + + Event { node, becomes: Visited } => { + let not_previously_visited = self.visited.insert(node); + let prior_status = if not_previously_visited { + None + } else if self.settled.contains(node) { + Some(Settled) + } else { + Some(Visited) + }; + + if let ControlFlow::Break(val) = visitor.node_examined(node, prior_status) { + return Some(val); + } + + // If this node has already been examined, we are done. + if prior_status.is_some() { + continue; + } + + // Otherwise, push a `Settled` event for this node onto the stack, then + // schedule its successors for examination. + self.stack.push(Event { node, becomes: Settled }); + for succ in self.graph.successors(node) { + if !visitor.ignore_edge(node, succ) { + self.stack.push(Event { node: succ, becomes: Visited }); + } + } + } + } + } + } +} + +impl<G> TriColorDepthFirstSearch<'graph, G> +where + G: ?Sized + DirectedGraph + WithNumNodes + WithSuccessors + WithStartNode, +{ + /// Performs a depth-first search, starting from `G::start_node()`. + /// + /// This won't visit nodes that are not reachable from the start node. + pub fn run_from_start<V>(self, visitor: &mut V) -> Option<V::BreakVal> + where + V: TriColorVisitor<G>, + { + let root = self.graph.start_node(); + self.run_from(root, visitor) + } +} + +/// What to do when a node is examined or becomes `Settled` during DFS. +pub trait TriColorVisitor<G> +where + G: ?Sized + DirectedGraph, +{ + /// The value returned by this search. + type BreakVal; + + /// Called when a node is examined by the depth-first search. + /// + /// By checking the value of `prior_status`, this visitor can determine whether the edge + /// leading to this node was a tree edge (`None`), forward edge (`Some(Settled)`) or back edge + /// (`Some(Visited)`). For a full explanation of each edge type, see the "Depth-first Search" + /// chapter in [CLR] or [wikipedia]. + /// + /// If you want to know *both* nodes linked by each edge, you'll need to modify + /// `TriColorDepthFirstSearch` to store a `source` node for each `Visited` event. + /// + /// [wikipedia]: https://en.wikipedia.org/wiki/Depth-first_search#Output_of_a_depth-first_search + /// [CLR]: https://en.wikipedia.org/wiki/Introduction_to_Algorithms + fn node_examined( + &mut self, + _node: G::Node, + _prior_status: Option<NodeStatus>, + ) -> ControlFlow<Self::BreakVal> { + ControlFlow::Continue + } + + /// Called after all nodes reachable from this one have been examined. + fn node_settled(&mut self, _node: G::Node) -> ControlFlow<Self::BreakVal> { + ControlFlow::Continue + } + + /// Behave as if no edges exist from `source` to `target`. + fn ignore_edge(&mut self, _source: G::Node, _target: G::Node) -> bool { + false + } +} + +/// This `TriColorVisitor` looks for back edges in a graph, which indicate that a cycle exists. +pub struct CycleDetector; + +impl<G> TriColorVisitor<G> for CycleDetector +where + G: ?Sized + DirectedGraph, +{ + type BreakVal = (); + + fn node_examined( + &mut self, + _node: G::Node, + prior_status: Option<NodeStatus>, + ) -> ControlFlow<Self::BreakVal> { + match prior_status { + Some(NodeStatus::Visited) => ControlFlow::Break(()), + _ => ControlFlow::Continue, + } + } +} diff --git a/compiler/rustc_data_structures/src/graph/iterate/tests.rs b/compiler/rustc_data_structures/src/graph/iterate/tests.rs new file mode 100644 index 00000000000..0e038e88b22 --- /dev/null +++ b/compiler/rustc_data_structures/src/graph/iterate/tests.rs @@ -0,0 +1,22 @@ +use super::super::tests::TestGraph; + +use super::*; + +#[test] +fn diamond_post_order() { + let graph = TestGraph::new(0, &[(0, 1), (0, 2), (1, 3), (2, 3)]); + + let result = post_order_from(&graph, 0); + assert_eq!(result, vec![3, 1, 2, 0]); +} + +#[test] +fn is_cyclic() { + use super::super::is_cyclic; + + let diamond_acyclic = TestGraph::new(0, &[(0, 1), (0, 2), (1, 3), (2, 3)]); + let diamond_cyclic = TestGraph::new(0, &[(0, 1), (1, 2), (2, 3), (3, 0)]); + + assert!(!is_cyclic(&diamond_acyclic)); + assert!(is_cyclic(&diamond_cyclic)); +} diff --git a/compiler/rustc_data_structures/src/graph/mod.rs b/compiler/rustc_data_structures/src/graph/mod.rs new file mode 100644 index 00000000000..e0903e43241 --- /dev/null +++ b/compiler/rustc_data_structures/src/graph/mod.rs @@ -0,0 +1,86 @@ +use rustc_index::vec::Idx; + +pub mod dominators; +pub mod implementation; +pub mod iterate; +mod reference; +pub mod scc; +pub mod vec_graph; + +#[cfg(test)] +mod tests; + +pub trait DirectedGraph { + type Node: Idx; +} + +pub trait WithNumNodes: DirectedGraph { + fn num_nodes(&self) -> usize; +} + +pub trait WithNumEdges: DirectedGraph { + fn num_edges(&self) -> usize; +} + +pub trait WithSuccessors: DirectedGraph +where + Self: for<'graph> GraphSuccessors<'graph, Item = <Self as DirectedGraph>::Node>, +{ + fn successors(&self, node: Self::Node) -> <Self as GraphSuccessors<'_>>::Iter; + + fn depth_first_search(&self, from: Self::Node) -> iterate::DepthFirstSearch<'_, Self> + where + Self: WithNumNodes, + { + iterate::DepthFirstSearch::new(self, from) + } +} + +#[allow(unused_lifetimes)] +pub trait GraphSuccessors<'graph> { + type Item; + type Iter: Iterator<Item = Self::Item>; +} + +pub trait WithPredecessors: DirectedGraph +where + Self: for<'graph> GraphPredecessors<'graph, Item = <Self as DirectedGraph>::Node>, +{ + fn predecessors(&self, node: Self::Node) -> <Self as GraphPredecessors<'_>>::Iter; +} + +#[allow(unused_lifetimes)] +pub trait GraphPredecessors<'graph> { + type Item; + type Iter: Iterator<Item = Self::Item>; +} + +pub trait WithStartNode: DirectedGraph { + fn start_node(&self) -> Self::Node; +} + +pub trait ControlFlowGraph: + DirectedGraph + WithStartNode + WithPredecessors + WithStartNode + WithSuccessors + WithNumNodes +{ + // convenient trait +} + +impl<T> ControlFlowGraph for T where + T: DirectedGraph + + WithStartNode + + WithPredecessors + + WithStartNode + + WithSuccessors + + WithNumNodes +{ +} + +/// Returns `true` if the graph has a cycle that is reachable from the start node. +pub fn is_cyclic<G>(graph: &G) -> bool +where + G: ?Sized + DirectedGraph + WithStartNode + WithSuccessors + WithNumNodes, +{ + iterate::TriColorDepthFirstSearch::new(graph) + .run_from_start(&mut iterate::CycleDetector) + .is_some() +} diff --git a/compiler/rustc_data_structures/src/graph/reference.rs b/compiler/rustc_data_structures/src/graph/reference.rs new file mode 100644 index 00000000000..c259fe56c15 --- /dev/null +++ b/compiler/rustc_data_structures/src/graph/reference.rs @@ -0,0 +1,39 @@ +use super::*; + +impl<'graph, G: DirectedGraph> DirectedGraph for &'graph G { + type Node = G::Node; +} + +impl<'graph, G: WithNumNodes> WithNumNodes for &'graph G { + fn num_nodes(&self) -> usize { + (**self).num_nodes() + } +} + +impl<'graph, G: WithStartNode> WithStartNode for &'graph G { + fn start_node(&self) -> Self::Node { + (**self).start_node() + } +} + +impl<'graph, G: WithSuccessors> WithSuccessors for &'graph G { + fn successors(&self, node: Self::Node) -> <Self as GraphSuccessors<'_>>::Iter { + (**self).successors(node) + } +} + +impl<'graph, G: WithPredecessors> WithPredecessors for &'graph G { + fn predecessors(&self, node: Self::Node) -> <Self as GraphPredecessors<'_>>::Iter { + (**self).predecessors(node) + } +} + +impl<'iter, 'graph, G: WithPredecessors> GraphPredecessors<'iter> for &'graph G { + type Item = G::Node; + type Iter = <G as GraphPredecessors<'iter>>::Iter; +} + +impl<'iter, 'graph, G: WithSuccessors> GraphSuccessors<'iter> for &'graph G { + type Item = G::Node; + type Iter = <G as GraphSuccessors<'iter>>::Iter; +} diff --git a/compiler/rustc_data_structures/src/graph/scc/mod.rs b/compiler/rustc_data_structures/src/graph/scc/mod.rs new file mode 100644 index 00000000000..2db8e466e11 --- /dev/null +++ b/compiler/rustc_data_structures/src/graph/scc/mod.rs @@ -0,0 +1,380 @@ +//! Routine to compute the strongly connected components (SCCs) of a graph. +//! +//! Also computes as the resulting DAG if each SCC is replaced with a +//! node in the graph. This uses [Tarjan's algorithm]( +//! https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm) +//! that completes in *O(n)* time. + +use crate::fx::FxHashSet; +use crate::graph::vec_graph::VecGraph; +use crate::graph::{DirectedGraph, GraphSuccessors, WithNumEdges, WithNumNodes, WithSuccessors}; +use rustc_index::vec::{Idx, IndexVec}; +use std::ops::Range; + +#[cfg(test)] +mod tests; + +/// Strongly connected components (SCC) of a graph. The type `N` is +/// the index type for the graph nodes and `S` is the index type for +/// the SCCs. We can map from each node to the SCC that it +/// participates in, and we also have the successors of each SCC. +pub struct Sccs<N: Idx, S: Idx> { + /// For each node, what is the SCC index of the SCC to which it + /// belongs. + scc_indices: IndexVec<N, S>, + + /// Data about each SCC. + scc_data: SccData<S>, +} + +struct SccData<S: Idx> { + /// For each SCC, the range of `all_successors` where its + /// successors can be found. + ranges: IndexVec<S, Range<usize>>, + + /// Contains the successors for all the Sccs, concatenated. The + /// range of indices corresponding to a given SCC is found in its + /// SccData. + all_successors: Vec<S>, +} + +impl<N: Idx, S: Idx> Sccs<N, S> { + pub fn new(graph: &(impl DirectedGraph<Node = N> + WithNumNodes + WithSuccessors)) -> Self { + SccsConstruction::construct(graph) + } + + /// Returns the number of SCCs in the graph. + pub fn num_sccs(&self) -> usize { + self.scc_data.len() + } + + /// Returns an iterator over the SCCs in the graph. + /// + /// The SCCs will be iterated in **dependency order** (or **post order**), + /// meaning that if `S1 -> S2`, we will visit `S2` first and `S1` after. + /// This is convenient when the edges represent dependencies: when you visit + /// `S1`, the value for `S2` will already have been computed. + pub fn all_sccs(&self) -> impl Iterator<Item = S> { + (0..self.scc_data.len()).map(S::new) + } + + /// Returns the SCC to which a node `r` belongs. + pub fn scc(&self, r: N) -> S { + self.scc_indices[r] + } + + /// Returns the successors of the given SCC. + pub fn successors(&self, scc: S) -> &[S] { + self.scc_data.successors(scc) + } + + /// Construct the reverse graph of the SCC graph. + pub fn reverse(&self) -> VecGraph<S> { + VecGraph::new( + self.num_sccs(), + self.all_sccs() + .flat_map(|source| { + self.successors(source).iter().map(move |&target| (target, source)) + }) + .collect(), + ) + } +} + +impl<N: Idx, S: Idx> DirectedGraph for Sccs<N, S> { + type Node = S; +} + +impl<N: Idx, S: Idx> WithNumNodes for Sccs<N, S> { + fn num_nodes(&self) -> usize { + self.num_sccs() + } +} + +impl<N: Idx, S: Idx> WithNumEdges for Sccs<N, S> { + fn num_edges(&self) -> usize { + self.scc_data.all_successors.len() + } +} + +impl<N: Idx, S: Idx> GraphSuccessors<'graph> for Sccs<N, S> { + type Item = S; + + type Iter = std::iter::Cloned<std::slice::Iter<'graph, S>>; +} + +impl<N: Idx, S: Idx> WithSuccessors for Sccs<N, S> { + fn successors(&self, node: S) -> <Self as GraphSuccessors<'_>>::Iter { + self.successors(node).iter().cloned() + } +} + +impl<S: Idx> SccData<S> { + /// Number of SCCs, + fn len(&self) -> usize { + self.ranges.len() + } + + /// Returns the successors of the given SCC. + fn successors(&self, scc: S) -> &[S] { + // Annoyingly, `range` does not implement `Copy`, so we have + // to do `range.start..range.end`: + let range = &self.ranges[scc]; + &self.all_successors[range.start..range.end] + } + + /// Creates a new SCC with `successors` as its successors and + /// returns the resulting index. + fn create_scc(&mut self, successors: impl IntoIterator<Item = S>) -> S { + // Store the successors on `scc_successors_vec`, remembering + // the range of indices. + let all_successors_start = self.all_successors.len(); + self.all_successors.extend(successors); + let all_successors_end = self.all_successors.len(); + + debug!( + "create_scc({:?}) successors={:?}", + self.ranges.len(), + &self.all_successors[all_successors_start..all_successors_end], + ); + + self.ranges.push(all_successors_start..all_successors_end) + } +} + +struct SccsConstruction<'c, G: DirectedGraph + WithNumNodes + WithSuccessors, S: Idx> { + graph: &'c G, + + /// The state of each node; used during walk to record the stack + /// and after walk to record what cycle each node ended up being + /// in. + node_states: IndexVec<G::Node, NodeState<G::Node, S>>, + + /// The stack of nodes that we are visiting as part of the DFS. + node_stack: Vec<G::Node>, + + /// The stack of successors: as we visit a node, we mark our + /// position in this stack, and when we encounter a successor SCC, + /// we push it on the stack. When we complete an SCC, we can pop + /// everything off the stack that was found along the way. + successors_stack: Vec<S>, + + /// A set used to strip duplicates. As we accumulate successors + /// into the successors_stack, we sometimes get duplicate entries. + /// We use this set to remove those -- we also keep its storage + /// around between successors to amortize memory allocation costs. + duplicate_set: FxHashSet<S>, + + scc_data: SccData<S>, +} + +#[derive(Copy, Clone, Debug)] +enum NodeState<N, S> { + /// This node has not yet been visited as part of the DFS. + /// + /// After SCC construction is complete, this state ought to be + /// impossible. + NotVisited, + + /// This node is currently being walk as part of our DFS. It is on + /// the stack at the depth `depth`. + /// + /// After SCC construction is complete, this state ought to be + /// impossible. + BeingVisited { depth: usize }, + + /// Indicates that this node is a member of the given cycle. + InCycle { scc_index: S }, + + /// Indicates that this node is a member of whatever cycle + /// `parent` is a member of. This state is transient: whenever we + /// see it, we try to overwrite it with the current state of + /// `parent` (this is the "path compression" step of a union-find + /// algorithm). + InCycleWith { parent: N }, +} + +#[derive(Copy, Clone, Debug)] +enum WalkReturn<S> { + Cycle { min_depth: usize }, + Complete { scc_index: S }, +} + +impl<'c, G, S> SccsConstruction<'c, G, S> +where + G: DirectedGraph + WithNumNodes + WithSuccessors, + S: Idx, +{ + /// Identifies SCCs in the graph `G` and computes the resulting + /// DAG. This uses a variant of [Tarjan's + /// algorithm][wikipedia]. The high-level summary of the algorithm + /// is that we do a depth-first search. Along the way, we keep a + /// stack of each node whose successors are being visited. We + /// track the depth of each node on this stack (there is no depth + /// if the node is not on the stack). When we find that some node + /// N with depth D can reach some other node N' with lower depth + /// D' (i.e., D' < D), we know that N, N', and all nodes in + /// between them on the stack are part of an SCC. + /// + /// [wikipedia]: https://bit.ly/2EZIx84 + fn construct(graph: &'c G) -> Sccs<G::Node, S> { + let num_nodes = graph.num_nodes(); + + let mut this = Self { + graph, + node_states: IndexVec::from_elem_n(NodeState::NotVisited, num_nodes), + node_stack: Vec::with_capacity(num_nodes), + successors_stack: Vec::new(), + scc_data: SccData { ranges: IndexVec::new(), all_successors: Vec::new() }, + duplicate_set: FxHashSet::default(), + }; + + let scc_indices = (0..num_nodes) + .map(G::Node::new) + .map(|node| match this.walk_node(0, node) { + WalkReturn::Complete { scc_index } => scc_index, + WalkReturn::Cycle { min_depth } => { + panic!("`walk_node(0, {:?})` returned cycle with depth {:?}", node, min_depth) + } + }) + .collect(); + + Sccs { scc_indices, scc_data: this.scc_data } + } + + /// Visits a node during the DFS. We first examine its current + /// state -- if it is not yet visited (`NotVisited`), we can push + /// it onto the stack and start walking its successors. + /// + /// If it is already on the DFS stack it will be in the state + /// `BeingVisited`. In that case, we have found a cycle and we + /// return the depth from the stack. + /// + /// Otherwise, we are looking at a node that has already been + /// completely visited. We therefore return `WalkReturn::Complete` + /// with its associated SCC index. + fn walk_node(&mut self, depth: usize, node: G::Node) -> WalkReturn<S> { + debug!("walk_node(depth = {:?}, node = {:?})", depth, node); + match self.find_state(node) { + NodeState::InCycle { scc_index } => WalkReturn::Complete { scc_index }, + + NodeState::BeingVisited { depth: min_depth } => WalkReturn::Cycle { min_depth }, + + NodeState::NotVisited => self.walk_unvisited_node(depth, node), + + NodeState::InCycleWith { parent } => panic!( + "`find_state` returned `InCycleWith({:?})`, which ought to be impossible", + parent + ), + } + } + + /// Fetches the state of the node `r`. If `r` is recorded as being + /// in a cycle with some other node `r2`, then fetches the state + /// of `r2` (and updates `r` to reflect current result). This is + /// basically the "find" part of a standard union-find algorithm + /// (with path compression). + fn find_state(&mut self, r: G::Node) -> NodeState<G::Node, S> { + debug!("find_state(r = {:?} in state {:?})", r, self.node_states[r]); + match self.node_states[r] { + NodeState::InCycle { scc_index } => NodeState::InCycle { scc_index }, + NodeState::BeingVisited { depth } => NodeState::BeingVisited { depth }, + NodeState::NotVisited => NodeState::NotVisited, + NodeState::InCycleWith { parent } => { + let parent_state = self.find_state(parent); + debug!("find_state: parent_state = {:?}", parent_state); + match parent_state { + NodeState::InCycle { .. } => { + self.node_states[r] = parent_state; + parent_state + } + + NodeState::BeingVisited { depth } => { + self.node_states[r] = + NodeState::InCycleWith { parent: self.node_stack[depth] }; + parent_state + } + + NodeState::NotVisited | NodeState::InCycleWith { .. } => { + panic!("invalid parent state: {:?}", parent_state) + } + } + } + } + } + + /// Walks a node that has never been visited before. + fn walk_unvisited_node(&mut self, depth: usize, node: G::Node) -> WalkReturn<S> { + debug!("walk_unvisited_node(depth = {:?}, node = {:?})", depth, node); + + debug_assert!(match self.node_states[node] { + NodeState::NotVisited => true, + _ => false, + }); + + // Push `node` onto the stack. + self.node_states[node] = NodeState::BeingVisited { depth }; + self.node_stack.push(node); + + // Walk each successor of the node, looking to see if any of + // them can reach a node that is presently on the stack. If + // so, that means they can also reach us. + let mut min_depth = depth; + let mut min_cycle_root = node; + let successors_len = self.successors_stack.len(); + for successor_node in self.graph.successors(node) { + debug!("walk_unvisited_node: node = {:?} successor_ode = {:?}", node, successor_node); + match self.walk_node(depth + 1, successor_node) { + WalkReturn::Cycle { min_depth: successor_min_depth } => { + // Track the minimum depth we can reach. + assert!(successor_min_depth <= depth); + if successor_min_depth < min_depth { + debug!( + "walk_unvisited_node: node = {:?} successor_min_depth = {:?}", + node, successor_min_depth + ); + min_depth = successor_min_depth; + min_cycle_root = successor_node; + } + } + + WalkReturn::Complete { scc_index: successor_scc_index } => { + // Push the completed SCC indices onto + // the `successors_stack` for later. + debug!( + "walk_unvisited_node: node = {:?} successor_scc_index = {:?}", + node, successor_scc_index + ); + self.successors_stack.push(successor_scc_index); + } + } + } + + // Completed walk, remove `node` from the stack. + let r = self.node_stack.pop(); + debug_assert_eq!(r, Some(node)); + + // If `min_depth == depth`, then we are the root of the + // cycle: we can't reach anyone further down the stack. + if min_depth == depth { + // Note that successor stack may have duplicates, so we + // want to remove those: + let deduplicated_successors = { + let duplicate_set = &mut self.duplicate_set; + duplicate_set.clear(); + self.successors_stack + .drain(successors_len..) + .filter(move |&i| duplicate_set.insert(i)) + }; + let scc_index = self.scc_data.create_scc(deduplicated_successors); + self.node_states[node] = NodeState::InCycle { scc_index }; + WalkReturn::Complete { scc_index } + } else { + // We are not the head of the cycle. Return back to our + // caller. They will take ownership of the + // `self.successors` data that we pushed. + self.node_states[node] = NodeState::InCycleWith { parent: min_cycle_root }; + WalkReturn::Cycle { min_depth } + } + } +} diff --git a/compiler/rustc_data_structures/src/graph/scc/tests.rs b/compiler/rustc_data_structures/src/graph/scc/tests.rs new file mode 100644 index 00000000000..1d5f46ebab1 --- /dev/null +++ b/compiler/rustc_data_structures/src/graph/scc/tests.rs @@ -0,0 +1,141 @@ +use super::*; +use crate::graph::tests::TestGraph; + +#[test] +fn diamond() { + let graph = TestGraph::new(0, &[(0, 1), (0, 2), (1, 3), (2, 3)]); + let sccs: Sccs<_, usize> = Sccs::new(&graph); + assert_eq!(sccs.num_sccs(), 4); + assert_eq!(sccs.num_sccs(), 4); +} + +#[test] +fn test_big_scc() { + // The order in which things will be visited is important to this + // test. + // + // We will visit: + // + // 0 -> 1 -> 2 -> 0 + // + // and at this point detect a cycle. 2 will return back to 1 which + // will visit 3. 3 will visit 2 before the cycle is complete, and + // hence it too will return a cycle. + + /* + +-> 0 + | | + | v + | 1 -> 3 + | | | + | v | + +-- 2 <--+ + */ + let graph = TestGraph::new(0, &[(0, 1), (1, 2), (1, 3), (2, 0), (3, 2)]); + let sccs: Sccs<_, usize> = Sccs::new(&graph); + assert_eq!(sccs.num_sccs(), 1); +} + +#[test] +fn test_three_sccs() { + /* + 0 + | + v + +-> 1 3 + | | | + | v | + +-- 2 <--+ + */ + let graph = TestGraph::new(0, &[(0, 1), (1, 2), (2, 1), (3, 2)]); + let sccs: Sccs<_, usize> = Sccs::new(&graph); + assert_eq!(sccs.num_sccs(), 3); + assert_eq!(sccs.scc(0), 1); + assert_eq!(sccs.scc(1), 0); + assert_eq!(sccs.scc(2), 0); + assert_eq!(sccs.scc(3), 2); + assert_eq!(sccs.successors(0), &[]); + assert_eq!(sccs.successors(1), &[0]); + assert_eq!(sccs.successors(2), &[0]); +} + +#[test] +fn test_find_state_2() { + // The order in which things will be visited is important to this + // test. It tests part of the `find_state` behavior. Here is the + // graph: + // + // + // /----+ + // 0 <--+ | + // | | | + // v | | + // +-> 1 -> 3 4 + // | | | + // | v | + // +-- 2 <----+ + + let graph = TestGraph::new(0, &[(0, 1), (0, 4), (1, 2), (1, 3), (2, 1), (3, 0), (4, 2)]); + + // For this graph, we will start in our DFS by visiting: + // + // 0 -> 1 -> 2 -> 1 + // + // and at this point detect a cycle. The state of 2 will thus be + // `InCycleWith { 1 }`. We will then visit the 1 -> 3 edge, which + // will attempt to visit 0 as well, thus going to the state + // `InCycleWith { 0 }`. Finally, node 1 will complete; the lowest + // depth of any successor was 3 which had depth 0, and thus it + // will be in the state `InCycleWith { 3 }`. + // + // When we finally traverse the `0 -> 4` edge and then visit node 2, + // the states of the nodes are: + // + // 0 BeingVisited { 0 } + // 1 InCycleWith { 3 } + // 2 InCycleWith { 1 } + // 3 InCycleWith { 0 } + // + // and hence 4 will traverse the links, finding an ultimate depth of 0. + // If will also collapse the states to the following: + // + // 0 BeingVisited { 0 } + // 1 InCycleWith { 3 } + // 2 InCycleWith { 1 } + // 3 InCycleWith { 0 } + + let sccs: Sccs<_, usize> = Sccs::new(&graph); + assert_eq!(sccs.num_sccs(), 1); + assert_eq!(sccs.scc(0), 0); + assert_eq!(sccs.scc(1), 0); + assert_eq!(sccs.scc(2), 0); + assert_eq!(sccs.scc(3), 0); + assert_eq!(sccs.scc(4), 0); + assert_eq!(sccs.successors(0), &[]); +} + +#[test] +fn test_find_state_3() { + /* + /----+ + 0 <--+ | + | | | + v | | + +-> 1 -> 3 4 5 + | | | | + | v | | + +-- 2 <----+-+ + */ + let graph = + TestGraph::new(0, &[(0, 1), (0, 4), (1, 2), (1, 3), (2, 1), (3, 0), (4, 2), (5, 2)]); + let sccs: Sccs<_, usize> = Sccs::new(&graph); + assert_eq!(sccs.num_sccs(), 2); + assert_eq!(sccs.scc(0), 0); + assert_eq!(sccs.scc(1), 0); + assert_eq!(sccs.scc(2), 0); + assert_eq!(sccs.scc(3), 0); + assert_eq!(sccs.scc(4), 0); + assert_eq!(sccs.scc(5), 1); + assert_eq!(sccs.successors(0), &[]); + assert_eq!(sccs.successors(1), &[0]); +} diff --git a/compiler/rustc_data_structures/src/graph/tests.rs b/compiler/rustc_data_structures/src/graph/tests.rs new file mode 100644 index 00000000000..7f4ef906b36 --- /dev/null +++ b/compiler/rustc_data_structures/src/graph/tests.rs @@ -0,0 +1,73 @@ +use crate::fx::FxHashMap; +use std::cmp::max; +use std::iter; +use std::slice; + +use super::*; + +pub struct TestGraph { + num_nodes: usize, + start_node: usize, + successors: FxHashMap<usize, Vec<usize>>, + predecessors: FxHashMap<usize, Vec<usize>>, +} + +impl TestGraph { + pub fn new(start_node: usize, edges: &[(usize, usize)]) -> Self { + let mut graph = TestGraph { + num_nodes: start_node + 1, + start_node, + successors: FxHashMap::default(), + predecessors: FxHashMap::default(), + }; + for &(source, target) in edges { + graph.num_nodes = max(graph.num_nodes, source + 1); + graph.num_nodes = max(graph.num_nodes, target + 1); + graph.successors.entry(source).or_default().push(target); + graph.predecessors.entry(target).or_default().push(source); + } + for node in 0..graph.num_nodes { + graph.successors.entry(node).or_default(); + graph.predecessors.entry(node).or_default(); + } + graph + } +} + +impl DirectedGraph for TestGraph { + type Node = usize; +} + +impl WithStartNode for TestGraph { + fn start_node(&self) -> usize { + self.start_node + } +} + +impl WithNumNodes for TestGraph { + fn num_nodes(&self) -> usize { + self.num_nodes + } +} + +impl WithPredecessors for TestGraph { + fn predecessors(&self, node: usize) -> <Self as GraphPredecessors<'_>>::Iter { + self.predecessors[&node].iter().cloned() + } +} + +impl WithSuccessors for TestGraph { + fn successors(&self, node: usize) -> <Self as GraphSuccessors<'_>>::Iter { + self.successors[&node].iter().cloned() + } +} + +impl<'graph> GraphPredecessors<'graph> for TestGraph { + type Item = usize; + type Iter = iter::Cloned<slice::Iter<'graph, usize>>; +} + +impl<'graph> GraphSuccessors<'graph> for TestGraph { + type Item = usize; + type Iter = iter::Cloned<slice::Iter<'graph, usize>>; +} diff --git a/compiler/rustc_data_structures/src/graph/vec_graph/mod.rs b/compiler/rustc_data_structures/src/graph/vec_graph/mod.rs new file mode 100644 index 00000000000..064467174ca --- /dev/null +++ b/compiler/rustc_data_structures/src/graph/vec_graph/mod.rs @@ -0,0 +1,107 @@ +use crate::graph::{DirectedGraph, GraphSuccessors, WithNumEdges, WithNumNodes, WithSuccessors}; +use rustc_index::vec::{Idx, IndexVec}; + +#[cfg(test)] +mod tests; + +pub struct VecGraph<N: Idx> { + /// Maps from a given node to an index where the set of successors + /// for that node starts. The index indexes into the `edges` + /// vector. To find the range for a given node, we look up the + /// start for that node and then the start for the next node + /// (i.e., with an index 1 higher) and get the range between the + /// two. This vector always has an extra entry so that this works + /// even for the max element. + node_starts: IndexVec<N, usize>, + + edge_targets: Vec<N>, +} + +impl<N: Idx> VecGraph<N> { + pub fn new(num_nodes: usize, mut edge_pairs: Vec<(N, N)>) -> Self { + // Sort the edges by the source -- this is important. + edge_pairs.sort(); + + let num_edges = edge_pairs.len(); + + // Store the *target* of each edge into `edge_targets`. + let edge_targets: Vec<N> = edge_pairs.iter().map(|&(_, target)| target).collect(); + + // Create the *edge starts* array. We are iterating over over + // the (sorted) edge pairs. We maintain the invariant that the + // length of the `node_starts` arary is enough to store the + // current source node -- so when we see that the source node + // for an edge is greater than the current length, we grow the + // edge-starts array by just enough. + let mut node_starts = IndexVec::with_capacity(num_edges); + for (index, &(source, _)) in edge_pairs.iter().enumerate() { + // If we have a list like `[(0, x), (2, y)]`: + // + // - Start out with `node_starts` of `[]` + // - Iterate to `(0, x)` at index 0: + // - Push one entry because `node_starts.len()` (0) is <= the source (0) + // - Leaving us with `node_starts` of `[0]` + // - Iterate to `(2, y)` at index 1: + // - Push one entry because `node_starts.len()` (1) is <= the source (2) + // - Push one entry because `node_starts.len()` (2) is <= the source (2) + // - Leaving us with `node_starts` of `[0, 1, 1]` + // - Loop terminates + while node_starts.len() <= source.index() { + node_starts.push(index); + } + } + + // Pad out the `node_starts` array so that it has `num_nodes + + // 1` entries. Continuing our example above, if `num_nodes` is + // be `3`, we would push one more index: `[0, 1, 1, 2]`. + // + // Interpretation of that vector: + // + // [0, 1, 1, 2] + // ---- range for N=2 + // ---- range for N=1 + // ---- range for N=0 + while node_starts.len() <= num_nodes { + node_starts.push(edge_targets.len()); + } + + assert_eq!(node_starts.len(), num_nodes + 1); + + Self { node_starts, edge_targets } + } + + /// Gets the successors for `source` as a slice. + pub fn successors(&self, source: N) -> &[N] { + let start_index = self.node_starts[source]; + let end_index = self.node_starts[source.plus(1)]; + &self.edge_targets[start_index..end_index] + } +} + +impl<N: Idx> DirectedGraph for VecGraph<N> { + type Node = N; +} + +impl<N: Idx> WithNumNodes for VecGraph<N> { + fn num_nodes(&self) -> usize { + self.node_starts.len() - 1 + } +} + +impl<N: Idx> WithNumEdges for VecGraph<N> { + fn num_edges(&self) -> usize { + self.edge_targets.len() + } +} + +impl<N: Idx> GraphSuccessors<'graph> for VecGraph<N> { + type Item = N; + + type Iter = std::iter::Cloned<std::slice::Iter<'graph, N>>; +} + +impl<N: Idx> WithSuccessors for VecGraph<N> { + fn successors(&self, node: N) -> <Self as GraphSuccessors<'_>>::Iter { + self.successors(node).iter().cloned() + } +} diff --git a/compiler/rustc_data_structures/src/graph/vec_graph/tests.rs b/compiler/rustc_data_structures/src/graph/vec_graph/tests.rs new file mode 100644 index 00000000000..c8f97926717 --- /dev/null +++ b/compiler/rustc_data_structures/src/graph/vec_graph/tests.rs @@ -0,0 +1,42 @@ +use super::*; + +fn create_graph() -> VecGraph<usize> { + // Create a simple graph + // + // 5 + // | + // V + // 0 --> 1 --> 2 + // | + // v + // 3 --> 4 + // + // 6 + + VecGraph::new(7, vec![(0, 1), (1, 2), (1, 3), (3, 4), (5, 1)]) +} + +#[test] +fn num_nodes() { + let graph = create_graph(); + assert_eq!(graph.num_nodes(), 7); +} + +#[test] +fn successors() { + let graph = create_graph(); + assert_eq!(graph.successors(0), &[1]); + assert_eq!(graph.successors(1), &[2, 3]); + assert_eq!(graph.successors(2), &[]); + assert_eq!(graph.successors(3), &[4]); + assert_eq!(graph.successors(4), &[]); + assert_eq!(graph.successors(5), &[1]); + assert_eq!(graph.successors(6), &[]); +} + +#[test] +fn dfs() { + let graph = create_graph(); + let dfs: Vec<_> = graph.depth_first_search(0).collect(); + assert_eq!(dfs, vec![0, 1, 3, 4, 2]); +} |