diff options
Diffstat (limited to 'compiler/rustc_data_structures/src/graph')
6 files changed, 27 insertions, 40 deletions
diff --git a/compiler/rustc_data_structures/src/graph/iterate/mod.rs b/compiler/rustc_data_structures/src/graph/iterate/mod.rs index 9eb4b5278c0..c46fdb4e4f7 100644 --- a/compiler/rustc_data_structures/src/graph/iterate/mod.rs +++ b/compiler/rustc_data_structures/src/graph/iterate/mod.rs @@ -1,4 +1,4 @@ -use super::{DirectedGraph, WithNumNodes, WithStartNode, WithSuccessors}; +use super::{DirectedGraph, WithStartNode, WithSuccessors}; use rustc_index::bit_set::BitSet; use rustc_index::{IndexSlice, IndexVec}; use std::ops::ControlFlow; @@ -6,14 +6,14 @@ use std::ops::ControlFlow; #[cfg(test)] mod tests; -pub fn post_order_from<G: DirectedGraph + WithSuccessors + WithNumNodes>( +pub fn post_order_from<G: DirectedGraph + WithSuccessors>( 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>( +pub fn post_order_from_to<G: DirectedGraph + WithSuccessors>( graph: &G, start_node: G::Node, end_node: Option<G::Node>, @@ -27,7 +27,7 @@ pub fn post_order_from_to<G: DirectedGraph + WithSuccessors + WithNumNodes>( result } -fn post_order_walk<G: DirectedGraph + WithSuccessors + WithNumNodes>( +fn post_order_walk<G: DirectedGraph + WithSuccessors>( graph: &G, node: G::Node, result: &mut Vec<G::Node>, @@ -60,7 +60,7 @@ fn post_order_walk<G: DirectedGraph + WithSuccessors + WithNumNodes>( } } -pub fn reverse_post_order<G: DirectedGraph + WithSuccessors + WithNumNodes>( +pub fn reverse_post_order<G: DirectedGraph + WithSuccessors>( graph: &G, start_node: G::Node, ) -> Vec<G::Node> { @@ -72,7 +72,7 @@ pub fn reverse_post_order<G: DirectedGraph + WithSuccessors + WithNumNodes>( /// A "depth-first search" iterator for a directed graph. pub struct DepthFirstSearch<'graph, G> where - G: ?Sized + DirectedGraph + WithNumNodes + WithSuccessors, + G: ?Sized + DirectedGraph + WithSuccessors, { graph: &'graph G, stack: Vec<G::Node>, @@ -81,7 +81,7 @@ where impl<'graph, G> DepthFirstSearch<'graph, G> where - G: ?Sized + DirectedGraph + WithNumNodes + WithSuccessors, + G: ?Sized + DirectedGraph + WithSuccessors, { pub fn new(graph: &'graph G) -> Self { Self { graph, stack: vec![], visited: BitSet::new_empty(graph.num_nodes()) } @@ -127,7 +127,7 @@ where impl<G> std::fmt::Debug for DepthFirstSearch<'_, G> where - G: ?Sized + DirectedGraph + WithNumNodes + WithSuccessors, + G: ?Sized + DirectedGraph + WithSuccessors, { fn fmt(&self, fmt: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { let mut f = fmt.debug_set(); @@ -140,7 +140,7 @@ where impl<G> Iterator for DepthFirstSearch<'_, G> where - G: ?Sized + DirectedGraph + WithNumNodes + WithSuccessors, + G: ?Sized + DirectedGraph + WithSuccessors, { type Item = G::Node; @@ -201,7 +201,7 @@ struct Event<N> { /// [CLR]: https://en.wikipedia.org/wiki/Introduction_to_Algorithms pub struct TriColorDepthFirstSearch<'graph, G> where - G: ?Sized + DirectedGraph + WithNumNodes + WithSuccessors, + G: ?Sized + DirectedGraph + WithSuccessors, { graph: &'graph G, stack: Vec<Event<G::Node>>, @@ -211,7 +211,7 @@ where impl<'graph, G> TriColorDepthFirstSearch<'graph, G> where - G: ?Sized + DirectedGraph + WithNumNodes + WithSuccessors, + G: ?Sized + DirectedGraph + WithSuccessors, { pub fn new(graph: &'graph G) -> Self { TriColorDepthFirstSearch { @@ -278,7 +278,7 @@ where impl<G> TriColorDepthFirstSearch<'_, G> where - G: ?Sized + DirectedGraph + WithNumNodes + WithSuccessors + WithStartNode, + G: ?Sized + DirectedGraph + WithSuccessors + WithStartNode, { /// Performs a depth-first search, starting from `G::start_node()`. /// diff --git a/compiler/rustc_data_structures/src/graph/mod.rs b/compiler/rustc_data_structures/src/graph/mod.rs index e06ab2fe36b..853b8f1775e 100644 --- a/compiler/rustc_data_structures/src/graph/mod.rs +++ b/compiler/rustc_data_structures/src/graph/mod.rs @@ -12,9 +12,7 @@ mod tests; pub trait DirectedGraph { type Node: Idx; -} -pub trait WithNumNodes: DirectedGraph { fn num_nodes(&self) -> usize; } @@ -28,10 +26,7 @@ where { fn successors(&self, node: Self::Node) -> <Self as GraphSuccessors<'_>>::Iter; - fn depth_first_search(&self, from: Self::Node) -> iterate::DepthFirstSearch<'_, Self> - where - Self: WithNumNodes, - { + fn depth_first_search(&self, from: Self::Node) -> iterate::DepthFirstSearch<'_, Self> { iterate::DepthFirstSearch::new(self).with_start_node(from) } } @@ -60,20 +55,20 @@ pub trait WithStartNode: DirectedGraph { } pub trait ControlFlowGraph: - DirectedGraph + WithStartNode + WithPredecessors + WithSuccessors + WithNumNodes + DirectedGraph + WithStartNode + WithPredecessors + WithSuccessors { // convenient trait } impl<T> ControlFlowGraph for T where - T: DirectedGraph + WithStartNode + WithPredecessors + WithSuccessors + WithNumNodes + T: DirectedGraph + WithStartNode + WithPredecessors + WithSuccessors { } /// 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, + G: ?Sized + DirectedGraph + WithStartNode + WithSuccessors, { iterate::TriColorDepthFirstSearch::new(graph) .run_from_start(&mut iterate::CycleDetector) diff --git a/compiler/rustc_data_structures/src/graph/reference.rs b/compiler/rustc_data_structures/src/graph/reference.rs index c259fe56c15..d15513c95db 100644 --- a/compiler/rustc_data_structures/src/graph/reference.rs +++ b/compiler/rustc_data_structures/src/graph/reference.rs @@ -2,9 +2,7 @@ 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() } diff --git a/compiler/rustc_data_structures/src/graph/scc/mod.rs b/compiler/rustc_data_structures/src/graph/scc/mod.rs index b54d75f7ed7..a9967c2ecbb 100644 --- a/compiler/rustc_data_structures/src/graph/scc/mod.rs +++ b/compiler/rustc_data_structures/src/graph/scc/mod.rs @@ -7,7 +7,7 @@ use crate::fx::FxHashSet; use crate::graph::vec_graph::VecGraph; -use crate::graph::{DirectedGraph, GraphSuccessors, WithNumEdges, WithNumNodes, WithSuccessors}; +use crate::graph::{DirectedGraph, GraphSuccessors, WithNumEdges, WithSuccessors}; use rustc_index::{Idx, IndexSlice, IndexVec}; use std::ops::Range; @@ -39,7 +39,7 @@ pub struct SccData<S: Idx> { } impl<N: Idx, S: Idx + Ord> Sccs<N, S> { - pub fn new(graph: &(impl DirectedGraph<Node = N> + WithNumNodes + WithSuccessors)) -> Self { + pub fn new(graph: &(impl DirectedGraph<Node = N> + WithSuccessors)) -> Self { SccsConstruction::construct(graph) } @@ -89,17 +89,15 @@ impl<N: Idx, S: Idx + Ord> Sccs<N, S> { } } -impl<N: Idx, S: Idx> DirectedGraph for Sccs<N, S> { +impl<N: Idx, S: Idx + Ord> DirectedGraph for Sccs<N, S> { type Node = S; -} -impl<N: Idx, S: Idx + Ord> WithNumNodes for Sccs<N, S> { fn num_nodes(&self) -> usize { self.num_sccs() } } -impl<N: Idx, S: Idx> WithNumEdges for Sccs<N, S> { +impl<N: Idx, S: Idx + Ord> WithNumEdges for Sccs<N, S> { fn num_edges(&self) -> usize { self.scc_data.all_successors.len() } @@ -158,7 +156,7 @@ impl<S: Idx> SccData<S> { } } -struct SccsConstruction<'c, G: DirectedGraph + WithNumNodes + WithSuccessors, S: Idx> { +struct SccsConstruction<'c, G: DirectedGraph + WithSuccessors, S: Idx> { graph: &'c G, /// The state of each node; used during walk to record the stack @@ -218,7 +216,7 @@ enum WalkReturn<S> { impl<'c, G, S> SccsConstruction<'c, G, S> where - G: DirectedGraph + WithNumNodes + WithSuccessors, + G: DirectedGraph + WithSuccessors, S: Idx, { /// Identifies SCCs in the graph `G` and computes the resulting diff --git a/compiler/rustc_data_structures/src/graph/tests.rs b/compiler/rustc_data_structures/src/graph/tests.rs index 7f4ef906b36..df58b965ccf 100644 --- a/compiler/rustc_data_structures/src/graph/tests.rs +++ b/compiler/rustc_data_structures/src/graph/tests.rs @@ -36,6 +36,10 @@ impl TestGraph { impl DirectedGraph for TestGraph { type Node = usize; + + fn num_nodes(&self) -> usize { + self.num_nodes + } } impl WithStartNode for TestGraph { @@ -44,12 +48,6 @@ impl WithStartNode for TestGraph { } } -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() diff --git a/compiler/rustc_data_structures/src/graph/vec_graph/mod.rs b/compiler/rustc_data_structures/src/graph/vec_graph/mod.rs index 00f6266ce1d..79efe3fb8e0 100644 --- a/compiler/rustc_data_structures/src/graph/vec_graph/mod.rs +++ b/compiler/rustc_data_structures/src/graph/vec_graph/mod.rs @@ -1,4 +1,4 @@ -use crate::graph::{DirectedGraph, GraphSuccessors, WithNumEdges, WithNumNodes, WithSuccessors}; +use crate::graph::{DirectedGraph, GraphSuccessors, WithNumEdges, WithSuccessors}; use rustc_index::{Idx, IndexVec}; #[cfg(test)] @@ -80,9 +80,7 @@ impl<N: Idx + Ord> VecGraph<N> { 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 } |