diff options
Diffstat (limited to 'compiler/rustc_data_structures/src')
6 files changed, 53 insertions, 88 deletions
diff --git a/compiler/rustc_data_structures/src/graph/iterate/mod.rs b/compiler/rustc_data_structures/src/graph/iterate/mod.rs index c46fdb4e4f7..3ead608cd0b 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, WithStartNode, WithSuccessors}; +use super::{DirectedGraph, Successors, WithStartNode}; 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>( +pub fn post_order_from<G: DirectedGraph + Successors>( 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>( +pub fn post_order_from_to<G: DirectedGraph + Successors>( graph: &G, start_node: G::Node, end_node: Option<G::Node>, @@ -27,7 +27,7 @@ pub fn post_order_from_to<G: DirectedGraph + WithSuccessors>( result } -fn post_order_walk<G: DirectedGraph + WithSuccessors>( +fn post_order_walk<G: DirectedGraph + Successors>( graph: &G, node: G::Node, result: &mut Vec<G::Node>, @@ -60,7 +60,7 @@ fn post_order_walk<G: DirectedGraph + WithSuccessors>( } } -pub fn reverse_post_order<G: DirectedGraph + WithSuccessors>( +pub fn reverse_post_order<G: DirectedGraph + Successors>( graph: &G, start_node: G::Node, ) -> Vec<G::Node> { @@ -72,7 +72,7 @@ pub fn reverse_post_order<G: DirectedGraph + WithSuccessors>( /// A "depth-first search" iterator for a directed graph. pub struct DepthFirstSearch<'graph, G> where - G: ?Sized + DirectedGraph + WithSuccessors, + G: ?Sized + DirectedGraph + Successors, { graph: &'graph G, stack: Vec<G::Node>, @@ -81,7 +81,7 @@ where impl<'graph, G> DepthFirstSearch<'graph, G> where - G: ?Sized + DirectedGraph + WithSuccessors, + G: ?Sized + DirectedGraph + Successors, { 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 + WithSuccessors, + G: ?Sized + DirectedGraph + Successors, { 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 + WithSuccessors, + G: ?Sized + DirectedGraph + Successors, { 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 + WithSuccessors, + G: ?Sized + DirectedGraph + Successors, { graph: &'graph G, stack: Vec<Event<G::Node>>, @@ -211,7 +211,7 @@ where impl<'graph, G> TriColorDepthFirstSearch<'graph, G> where - G: ?Sized + DirectedGraph + WithSuccessors, + G: ?Sized + DirectedGraph + Successors, { pub fn new(graph: &'graph G) -> Self { TriColorDepthFirstSearch { @@ -278,7 +278,7 @@ where impl<G> TriColorDepthFirstSearch<'_, G> where - G: ?Sized + DirectedGraph + WithSuccessors + WithStartNode, + G: ?Sized + DirectedGraph + Successors + 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 853b8f1775e..ef1dac1509e 100644 --- a/compiler/rustc_data_structures/src/graph/mod.rs +++ b/compiler/rustc_data_structures/src/graph/mod.rs @@ -20,55 +20,40 @@ 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; +pub trait Successors: DirectedGraph { + type Successors<'g>: Iterator<Item = Self::Node> + where + Self: 'g; + + fn successors(&self, node: Self::Node) -> Self::Successors<'_>; fn depth_first_search(&self, from: Self::Node) -> iterate::DepthFirstSearch<'_, Self> { iterate::DepthFirstSearch::new(self).with_start_node(from) } } -#[allow(unused_lifetimes)] -pub trait GraphSuccessors<'graph> { - type Item; - type Iter: Iterator<Item = Self::Item>; -} +pub trait Predecessors: DirectedGraph { + type Predecessors<'g>: Iterator<Item = Self::Node> + where + Self: 'g; -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>; + fn predecessors(&self, node: Self::Node) -> Self::Predecessors<'_>; } pub trait WithStartNode: DirectedGraph { fn start_node(&self) -> Self::Node; } -pub trait ControlFlowGraph: - DirectedGraph + WithStartNode + WithPredecessors + WithSuccessors -{ +pub trait ControlFlowGraph: DirectedGraph + WithStartNode + Predecessors + Successors { // convenient trait } -impl<T> ControlFlowGraph for T where - T: DirectedGraph + WithStartNode + WithPredecessors + WithSuccessors -{ -} +impl<T> ControlFlowGraph for T where T: DirectedGraph + WithStartNode + Predecessors + Successors {} /// 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, + G: ?Sized + DirectedGraph + WithStartNode + Successors, { 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 d15513c95db..fb4868f0d47 100644 --- a/compiler/rustc_data_structures/src/graph/reference.rs +++ b/compiler/rustc_data_structures/src/graph/reference.rs @@ -14,24 +14,18 @@ impl<'graph, G: WithStartNode> WithStartNode for &'graph G { } } -impl<'graph, G: WithSuccessors> WithSuccessors for &'graph G { - fn successors(&self, node: Self::Node) -> <Self as GraphSuccessors<'_>>::Iter { +impl<'graph, G: Successors> Successors for &'graph G { + type Successors<'g> = G::Successors<'g> where 'graph: 'g; + + fn successors(&self, node: Self::Node) -> Self::Successors<'_> { (**self).successors(node) } } -impl<'graph, G: WithPredecessors> WithPredecessors for &'graph G { - fn predecessors(&self, node: Self::Node) -> <Self as GraphPredecessors<'_>>::Iter { +impl<'graph, G: Predecessors> Predecessors for &'graph G { + type Predecessors<'g> = G::Predecessors<'g> where 'graph: 'g; + + fn predecessors(&self, node: Self::Node) -> Self::Predecessors<'_> { (**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 index a9967c2ecbb..f8f2f3cf0ce 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, WithSuccessors}; +use crate::graph::{DirectedGraph, Successors, WithNumEdges}; 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> + WithSuccessors)) -> Self { + pub fn new(graph: &(impl DirectedGraph<Node = N> + Successors)) -> Self { SccsConstruction::construct(graph) } @@ -103,14 +103,10 @@ impl<N: Idx, S: Idx + Ord> WithNumEdges for Sccs<N, S> { } } -impl<'graph, N: Idx, S: Idx> GraphSuccessors<'graph> for Sccs<N, S> { - type Item = S; +impl<N: Idx, S: Idx + Ord> Successors for Sccs<N, S> { + type Successors<'g> = std::iter::Cloned<std::slice::Iter<'g, S>>; - type Iter = std::iter::Cloned<std::slice::Iter<'graph, S>>; -} - -impl<N: Idx, S: Idx + Ord> WithSuccessors for Sccs<N, S> { - fn successors(&self, node: S) -> <Self as GraphSuccessors<'_>>::Iter { + fn successors(&self, node: S) -> Self::Successors<'_> { self.successors(node).iter().cloned() } } @@ -156,7 +152,7 @@ impl<S: Idx> SccData<S> { } } -struct SccsConstruction<'c, G: DirectedGraph + WithSuccessors, S: Idx> { +struct SccsConstruction<'c, G: DirectedGraph + Successors, S: Idx> { graph: &'c G, /// The state of each node; used during walk to record the stack @@ -216,7 +212,7 @@ enum WalkReturn<S> { impl<'c, G, S> SccsConstruction<'c, G, S> where - G: DirectedGraph + WithSuccessors, + G: DirectedGraph + Successors, 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 df58b965ccf..9cd8261be6c 100644 --- a/compiler/rustc_data_structures/src/graph/tests.rs +++ b/compiler/rustc_data_structures/src/graph/tests.rs @@ -48,24 +48,18 @@ impl WithStartNode for TestGraph { } } -impl WithPredecessors for TestGraph { - fn predecessors(&self, node: usize) -> <Self as GraphPredecessors<'_>>::Iter { +impl Predecessors for TestGraph { + type Predecessors<'g> = iter::Cloned<slice::Iter<'g, usize>>; + + fn predecessors(&self, node: usize) -> Self::Predecessors<'_> { self.predecessors[&node].iter().cloned() } } -impl WithSuccessors for TestGraph { - fn successors(&self, node: usize) -> <Self as GraphSuccessors<'_>>::Iter { +impl Successors for TestGraph { + type Successors<'g> = iter::Cloned<slice::Iter<'g, usize>>; + + fn successors(&self, node: usize) -> Self::Successors<'_> { 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 index 79efe3fb8e0..8b75fd9f633 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, WithSuccessors}; +use crate::graph::{DirectedGraph, Successors, WithNumEdges}; use rustc_index::{Idx, IndexVec}; #[cfg(test)] @@ -92,14 +92,10 @@ impl<N: Idx> WithNumEdges for VecGraph<N> { } } -impl<'graph, N: Idx> GraphSuccessors<'graph> for VecGraph<N> { - type Item = N; +impl<N: Idx + Ord> Successors for VecGraph<N> { + type Successors<'g> = std::iter::Cloned<std::slice::Iter<'g, N>>; - type Iter = std::iter::Cloned<std::slice::Iter<'graph, N>>; -} - -impl<N: Idx + Ord> WithSuccessors for VecGraph<N> { - fn successors(&self, node: N) -> <Self as GraphSuccessors<'_>>::Iter { + fn successors(&self, node: N) -> Self::Successors<'_> { self.successors(node).iter().cloned() } } |