From 0d5fc9bf584f0e8700f0c3d2854bb6c70453f624 Mon Sep 17 00:00:00 2001 From: Maybe Waffle Date: Sun, 14 Apr 2024 15:40:26 +0000 Subject: Merge `{With,Graph}{Successors,Predecessors}` into `{Successors,Predecessors}` Now with GAT! --- .../rustc_data_structures/src/graph/iterate/mod.rs | 24 ++++++------ compiler/rustc_data_structures/src/graph/mod.rs | 43 +++++++--------------- .../rustc_data_structures/src/graph/reference.rs | 22 ++++------- .../rustc_data_structures/src/graph/scc/mod.rs | 18 ++++----- compiler/rustc_data_structures/src/graph/tests.rs | 22 ++++------- .../src/graph/vec_graph/mod.rs | 12 ++---- 6 files changed, 53 insertions(+), 88 deletions(-) (limited to 'compiler/rustc_data_structures/src') 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( +pub fn post_order_from( graph: &G, start_node: G::Node, ) -> Vec { post_order_from_to(graph, start_node, None) } -pub fn post_order_from_to( +pub fn post_order_from_to( graph: &G, start_node: G::Node, end_node: Option, @@ -27,7 +27,7 @@ pub fn post_order_from_to( result } -fn post_order_walk( +fn post_order_walk( graph: &G, node: G::Node, result: &mut Vec, @@ -60,7 +60,7 @@ fn post_order_walk( } } -pub fn reverse_post_order( +pub fn reverse_post_order( graph: &G, start_node: G::Node, ) -> Vec { @@ -72,7 +72,7 @@ pub fn reverse_post_order( /// 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, @@ -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 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 Iterator for DepthFirstSearch<'_, G> where - G: ?Sized + DirectedGraph + WithSuccessors, + G: ?Sized + DirectedGraph + Successors, { type Item = G::Node; @@ -201,7 +201,7 @@ struct Event { /// [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>, @@ -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 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 = ::Node>, -{ - fn successors(&self, node: Self::Node) -> >::Iter; +pub trait Successors: DirectedGraph { + type Successors<'g>: Iterator + 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; -} +pub trait Predecessors: DirectedGraph { + type Predecessors<'g>: Iterator + where + Self: 'g; -pub trait WithPredecessors: DirectedGraph -where - Self: for<'graph> GraphPredecessors<'graph, Item = ::Node>, -{ - fn predecessors(&self, node: Self::Node) -> >::Iter; -} - -#[allow(unused_lifetimes)] -pub trait GraphPredecessors<'graph> { - type Item; - type Iter: Iterator; + 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 ControlFlowGraph for T where - T: DirectedGraph + WithStartNode + WithPredecessors + WithSuccessors -{ -} +impl 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(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) -> >::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) -> >::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 = >::Iter; -} - -impl<'iter, 'graph, G: WithSuccessors> GraphSuccessors<'iter> for &'graph G { - type Item = G::Node; - type 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 { } impl Sccs { - pub fn new(graph: &(impl DirectedGraph + WithSuccessors)) -> Self { + pub fn new(graph: &(impl DirectedGraph + Successors)) -> Self { SccsConstruction::construct(graph) } @@ -103,14 +103,10 @@ impl WithNumEdges for Sccs { } } -impl<'graph, N: Idx, S: Idx> GraphSuccessors<'graph> for Sccs { - type Item = S; +impl Successors for Sccs { + type Successors<'g> = std::iter::Cloned>; - type Iter = std::iter::Cloned>; -} - -impl WithSuccessors for Sccs { - fn successors(&self, node: S) -> >::Iter { + fn successors(&self, node: S) -> Self::Successors<'_> { self.successors(node).iter().cloned() } } @@ -156,7 +152,7 @@ impl SccData { } } -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 { 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) -> >::Iter { +impl Predecessors for TestGraph { + type Predecessors<'g> = iter::Cloned>; + + fn predecessors(&self, node: usize) -> Self::Predecessors<'_> { self.predecessors[&node].iter().cloned() } } -impl WithSuccessors for TestGraph { - fn successors(&self, node: usize) -> >::Iter { +impl Successors for TestGraph { + type Successors<'g> = iter::Cloned>; + + 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>; -} - -impl<'graph> GraphSuccessors<'graph> for TestGraph { - type Item = usize; - type Iter = 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 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 WithNumEdges for VecGraph { } } -impl<'graph, N: Idx> GraphSuccessors<'graph> for VecGraph { - type Item = N; +impl Successors for VecGraph { + type Successors<'g> = std::iter::Cloned>; - type Iter = std::iter::Cloned>; -} - -impl WithSuccessors for VecGraph { - fn successors(&self, node: N) -> >::Iter { + fn successors(&self, node: N) -> Self::Successors<'_> { self.successors(node).iter().cloned() } } -- cgit 1.4.1-3-g733a5