diff options
18 files changed, 89 insertions, 193 deletions
diff --git a/compiler/rustc_borrowck/src/constraints/graph.rs b/compiler/rustc_borrowck/src/constraints/graph.rs index 8b7d9ec2cd6..540b466560c 100644 --- a/compiler/rustc_borrowck/src/constraints/graph.rs +++ b/compiler/rustc_borrowck/src/constraints/graph.rs @@ -216,23 +216,14 @@ impl<'s, 'tcx, D: ConstraintGraphDirection> Iterator for Successors<'s, 'tcx, D> impl<'s, 'tcx, D: ConstraintGraphDirection> graph::DirectedGraph for RegionGraph<'s, 'tcx, D> { type Node = RegionVid; -} -impl<'s, 'tcx, D: ConstraintGraphDirection> graph::WithNumNodes for RegionGraph<'s, 'tcx, D> { fn num_nodes(&self) -> usize { self.constraint_graph.first_constraints.len() } } -impl<'s, 'tcx, D: ConstraintGraphDirection> graph::WithSuccessors for RegionGraph<'s, 'tcx, D> { - fn successors(&self, node: Self::Node) -> <Self as graph::GraphSuccessors<'_>>::Iter { +impl<'s, 'tcx, D: ConstraintGraphDirection> graph::Successors for RegionGraph<'s, 'tcx, D> { + fn successors(&self, node: Self::Node) -> impl Iterator<Item = Self::Node> { self.outgoing_regions(node) } } - -impl<'s, 'tcx, D: ConstraintGraphDirection> graph::GraphSuccessors<'_> - for RegionGraph<'s, 'tcx, D> -{ - type Item = RegionVid; - type Iter = Successors<'s, 'tcx, D>; -} diff --git a/compiler/rustc_borrowck/src/dataflow.rs b/compiler/rustc_borrowck/src/dataflow.rs index bc5bd787956..ec7d4582a60 100644 --- a/compiler/rustc_borrowck/src/dataflow.rs +++ b/compiler/rustc_borrowck/src/dataflow.rs @@ -1,5 +1,5 @@ use rustc_data_structures::fx::FxIndexMap; -use rustc_data_structures::graph::WithSuccessors; +use rustc_data_structures::graph; use rustc_index::bit_set::BitSet; use rustc_middle::mir::{ self, BasicBlock, Body, CallReturnPlaces, Location, Place, TerminatorEdges, @@ -262,7 +262,7 @@ impl<'tcx> PoloniusOutOfScopePrecomputer<'_, 'tcx> { // We first handle the cases where the loan doesn't go out of scope, depending on the issuing // region's successors. - for successor in self.regioncx.region_graph().depth_first_search(issuing_region) { + for successor in graph::depth_first_search(&self.regioncx.region_graph(), issuing_region) { // 1. Via applied member constraints // // The issuing region can flow into the choice regions, and they are either: diff --git a/compiler/rustc_borrowck/src/region_infer/reverse_sccs.rs b/compiler/rustc_borrowck/src/region_infer/reverse_sccs.rs index f94001de357..97ddc45ee47 100644 --- a/compiler/rustc_borrowck/src/region_infer/reverse_sccs.rs +++ b/compiler/rustc_borrowck/src/region_infer/reverse_sccs.rs @@ -1,8 +1,8 @@ use crate::constraints::ConstraintSccIndex; use crate::RegionInferenceContext; use rustc_data_structures::fx::{FxIndexMap, FxIndexSet}; +use rustc_data_structures::graph; use rustc_data_structures::graph::vec_graph::VecGraph; -use rustc_data_structures::graph::WithSuccessors; use rustc_middle::ty::RegionVid; use std::ops::Range; @@ -23,8 +23,7 @@ impl ReverseSccGraph { scc0: ConstraintSccIndex, ) -> impl Iterator<Item = RegionVid> + 'a { let mut duplicates = FxIndexSet::default(); - self.graph - .depth_first_search(scc0) + graph::depth_first_search(&self.graph, scc0) .flat_map(move |scc1| { self.scc_regions .get(&scc1) diff --git a/compiler/rustc_borrowck/src/type_check/liveness/trace.rs b/compiler/rustc_borrowck/src/type_check/liveness/trace.rs index 8bdefdfc0ac..6cc0e67c0f8 100644 --- a/compiler/rustc_borrowck/src/type_check/liveness/trace.rs +++ b/compiler/rustc_borrowck/src/type_check/liveness/trace.rs @@ -1,5 +1,4 @@ use rustc_data_structures::fx::{FxIndexMap, FxIndexSet}; -use rustc_data_structures::graph::WithSuccessors; use rustc_index::bit_set::BitSet; use rustc_index::interval::IntervalSet; use rustc_infer::infer::canonical::QueryRegionConstraints; @@ -64,7 +63,10 @@ pub(super) fn trace<'mir, 'tcx>( // Traverse each issuing region's constraints, and record the loan as flowing into the // outlived region. for (loan, issuing_region_data) in borrow_set.iter_enumerated() { - for succ in region_graph.depth_first_search(issuing_region_data.region) { + for succ in rustc_data_structures::graph::depth_first_search( + ®ion_graph, + issuing_region_data.region, + ) { // We don't need to mention that a loan flows into its issuing region. if succ == issuing_region_data.region { continue; diff --git a/compiler/rustc_data_structures/src/graph/iterate/mod.rs b/compiler/rustc_data_structures/src/graph/iterate/mod.rs index 9eb4b5278c0..7a77f2c0dbb 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, StartNode, Successors}; 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 + 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 + WithNumNodes>( +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 + WithNumNodes>( result } -fn post_order_walk<G: DirectedGraph + WithSuccessors + WithNumNodes>( +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 + WithNumNodes>( } } -pub fn reverse_post_order<G: DirectedGraph + WithSuccessors + WithNumNodes>( +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 + WithNumNodes>( /// A "depth-first search" iterator for a directed graph. pub struct DepthFirstSearch<'graph, G> where - G: ?Sized + DirectedGraph + WithNumNodes + 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 + WithNumNodes + 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 + WithNumNodes + 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 + WithNumNodes + 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 + WithNumNodes + 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 + WithNumNodes + 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 + WithNumNodes + WithSuccessors + WithStartNode, + G: ?Sized + DirectedGraph + Successors + StartNode, { /// 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..3ae3023a91b 100644 --- a/compiler/rustc_data_structures/src/graph/mod.rs +++ b/compiler/rustc_data_structures/src/graph/mod.rs @@ -12,70 +12,43 @@ mod tests; pub trait DirectedGraph { type Node: Idx; -} -pub trait WithNumNodes: DirectedGraph { fn num_nodes(&self) -> usize; } -pub trait WithNumEdges: DirectedGraph { +pub trait NumEdges: 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).with_start_node(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 { +pub trait StartNode: DirectedGraph { fn start_node(&self) -> Self::Node; } -pub trait ControlFlowGraph: - DirectedGraph + WithStartNode + WithPredecessors + WithSuccessors + WithNumNodes -{ - // convenient trait +pub trait Successors: DirectedGraph { + fn successors(&self, node: Self::Node) -> impl Iterator<Item = Self::Node>; } -impl<T> ControlFlowGraph for T where - T: DirectedGraph + WithStartNode + WithPredecessors + WithSuccessors + WithNumNodes -{ +pub trait Predecessors: DirectedGraph { + fn predecessors(&self, node: Self::Node) -> impl Iterator<Item = Self::Node>; } +/// Alias for [`DirectedGraph`] + [`StartNode`] + [`Predecessors`] + [`Successors`]. +pub trait ControlFlowGraph: DirectedGraph + StartNode + Predecessors + Successors {} +impl<T> ControlFlowGraph for T where T: DirectedGraph + StartNode + 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 + WithNumNodes, + G: ?Sized + DirectedGraph + StartNode + Successors, { iterate::TriColorDepthFirstSearch::new(graph) .run_from_start(&mut iterate::CycleDetector) .is_some() } + +pub fn depth_first_search<G>(graph: &G, from: G::Node) -> iterate::DepthFirstSearch<'_, G> +where + G: ?Sized + Successors, +{ + iterate::DepthFirstSearch::new(graph).with_start_node(from) +} diff --git a/compiler/rustc_data_structures/src/graph/reference.rs b/compiler/rustc_data_structures/src/graph/reference.rs index c259fe56c15..7a487552f53 100644 --- a/compiler/rustc_data_structures/src/graph/reference.rs +++ b/compiler/rustc_data_structures/src/graph/reference.rs @@ -2,38 +2,26 @@ 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 { +impl<'graph, G: StartNode> StartNode 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 { +impl<'graph, G: Successors> Successors for &'graph G { + fn successors(&self, node: Self::Node) -> impl Iterator<Item = Self::Node> { (**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 { + fn predecessors(&self, node: Self::Node) -> impl Iterator<Item = Self::Node> { (**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 b54d75f7ed7..5021e5e8fc0 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, NumEdges, Successors}; 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> + Successors)) -> Self { SccsConstruction::construct(graph) } @@ -89,30 +89,22 @@ 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> NumEdges for Sccs<N, S> { fn num_edges(&self) -> usize { self.scc_data.all_successors.len() } } -impl<'graph, 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 + Ord> WithSuccessors for Sccs<N, S> { - fn successors(&self, node: S) -> <Self as GraphSuccessors<'_>>::Iter { +impl<N: Idx, S: Idx + Ord> Successors for Sccs<N, S> { + fn successors(&self, node: S) -> impl Iterator<Item = Self::Node> { self.successors(node).iter().cloned() } } @@ -158,7 +150,7 @@ impl<S: Idx> SccData<S> { } } -struct SccsConstruction<'c, G: DirectedGraph + WithNumNodes + 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 @@ -218,7 +210,7 @@ enum WalkReturn<S> { impl<'c, G, S> SccsConstruction<'c, G, S> where - G: DirectedGraph + WithNumNodes + 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 7f4ef906b36..85c2703cc25 100644 --- a/compiler/rustc_data_structures/src/graph/tests.rs +++ b/compiler/rustc_data_structures/src/graph/tests.rs @@ -1,7 +1,5 @@ use crate::fx::FxHashMap; use std::cmp::max; -use std::iter; -use std::slice; use super::*; @@ -36,38 +34,26 @@ impl TestGraph { impl DirectedGraph for TestGraph { type Node = usize; -} -impl WithStartNode for TestGraph { - fn start_node(&self) -> usize { - self.start_node + fn num_nodes(&self) -> usize { + self.num_nodes } } -impl WithNumNodes for TestGraph { - fn num_nodes(&self) -> usize { - self.num_nodes +impl StartNode for TestGraph { + fn start_node(&self) -> usize { + self.start_node } } -impl WithPredecessors for TestGraph { - fn predecessors(&self, node: usize) -> <Self as GraphPredecessors<'_>>::Iter { +impl Predecessors for TestGraph { + fn predecessors(&self, node: usize) -> impl Iterator<Item = Self::Node> { self.predecessors[&node].iter().cloned() } } -impl WithSuccessors for TestGraph { - fn successors(&self, node: usize) -> <Self as GraphSuccessors<'_>>::Iter { +impl Successors for TestGraph { + fn successors(&self, node: usize) -> impl Iterator<Item = Self::Node> { 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 00f6266ce1d..26c86469fad 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, NumEdges, Successors}; use rustc_index::{Idx, IndexVec}; #[cfg(test)] @@ -80,28 +80,20 @@ 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 } } -impl<N: Idx> WithNumEdges for VecGraph<N> { +impl<N: Idx> NumEdges for VecGraph<N> { fn num_edges(&self) -> usize { self.edge_targets.len() } } -impl<'graph, N: Idx> GraphSuccessors<'graph> for VecGraph<N> { - type Item = 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 { +impl<N: Idx + Ord> Successors for VecGraph<N> { + fn successors(&self, node: N) -> impl Iterator<Item = Self::Node> { 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 index 7c866da6009..87c8d25f094 100644 --- a/compiler/rustc_data_structures/src/graph/vec_graph/tests.rs +++ b/compiler/rustc_data_structures/src/graph/vec_graph/tests.rs @@ -1,3 +1,5 @@ +use crate::graph; + use super::*; fn create_graph() -> VecGraph<usize> { @@ -37,6 +39,6 @@ fn successors() { #[test] fn dfs() { let graph = create_graph(); - let dfs: Vec<_> = graph.depth_first_search(0).collect(); + let dfs: Vec<_> = graph::depth_first_search(&graph, 0).collect(); assert_eq!(dfs, vec![0, 1, 3, 4, 2]); } diff --git a/compiler/rustc_hir_typeck/src/fallback.rs b/compiler/rustc_hir_typeck/src/fallback.rs index fe1e4e74973..69399b50695 100644 --- a/compiler/rustc_hir_typeck/src/fallback.rs +++ b/compiler/rustc_hir_typeck/src/fallback.rs @@ -1,7 +1,6 @@ use crate::FnCtxt; use rustc_data_structures::{ - graph::WithSuccessors, - graph::{iterate::DepthFirstSearch, vec_graph::VecGraph}, + graph::{self, iterate::DepthFirstSearch, vec_graph::VecGraph}, unord::{UnordBag, UnordMap, UnordSet}, }; use rustc_infer::infer::{DefineOpaqueTypes, InferOk}; @@ -300,7 +299,7 @@ impl<'tcx> FnCtxt<'_, 'tcx> { debug!( "calculate_diverging_fallback: root_vid={:?} reaches {:?}", root_vid, - coercion_graph.depth_first_search(root_vid).collect::<Vec<_>>() + graph::depth_first_search(&coercion_graph, root_vid).collect::<Vec<_>>() ); // drain the iterator to visit all nodes reachable from this node @@ -342,8 +341,7 @@ impl<'tcx> FnCtxt<'_, 'tcx> { for &diverging_vid in &diverging_vids { let diverging_ty = Ty::new_var(self.tcx, diverging_vid); let root_vid = self.root_var(diverging_vid); - let can_reach_non_diverging = coercion_graph - .depth_first_search(root_vid) + let can_reach_non_diverging = graph::depth_first_search(&coercion_graph, root_vid) .any(|n| roots_reachable_from_non_diverging.visited(n)); let infer_var_infos: UnordBag<_> = self diff --git a/compiler/rustc_middle/src/mir/basic_blocks.rs b/compiler/rustc_middle/src/mir/basic_blocks.rs index 3ecd5b9cd34..1086d647721 100644 --- a/compiler/rustc_middle/src/mir/basic_blocks.rs +++ b/compiler/rustc_middle/src/mir/basic_blocks.rs @@ -1,5 +1,5 @@ use crate::mir::traversal::Postorder; -use crate::mir::{BasicBlock, BasicBlockData, Successors, Terminator, TerminatorKind, START_BLOCK}; +use crate::mir::{BasicBlock, BasicBlockData, Terminator, TerminatorKind, START_BLOCK}; use rustc_data_structures::fx::FxHashMap; use rustc_data_structures::graph; @@ -141,42 +141,30 @@ impl<'tcx> std::ops::Deref for BasicBlocks<'tcx> { impl<'tcx> graph::DirectedGraph for BasicBlocks<'tcx> { type Node = BasicBlock; -} -impl<'tcx> graph::WithNumNodes for BasicBlocks<'tcx> { #[inline] fn num_nodes(&self) -> usize { self.basic_blocks.len() } } -impl<'tcx> graph::WithStartNode for BasicBlocks<'tcx> { +impl<'tcx> graph::StartNode for BasicBlocks<'tcx> { #[inline] fn start_node(&self) -> Self::Node { START_BLOCK } } -impl<'tcx> graph::WithSuccessors for BasicBlocks<'tcx> { +impl<'tcx> graph::Successors for BasicBlocks<'tcx> { #[inline] - fn successors(&self, node: Self::Node) -> <Self as graph::GraphSuccessors<'_>>::Iter { + fn successors(&self, node: Self::Node) -> impl Iterator<Item = Self::Node> { self.basic_blocks[node].terminator().successors() } } -impl<'a, 'b> graph::GraphSuccessors<'b> for BasicBlocks<'a> { - type Item = BasicBlock; - type Iter = Successors<'b>; -} - -impl<'tcx, 'graph> graph::GraphPredecessors<'graph> for BasicBlocks<'tcx> { - type Item = BasicBlock; - type Iter = std::iter::Copied<std::slice::Iter<'graph, BasicBlock>>; -} - -impl<'tcx> graph::WithPredecessors for BasicBlocks<'tcx> { +impl<'tcx> graph::Predecessors for BasicBlocks<'tcx> { #[inline] - fn predecessors(&self, node: Self::Node) -> <Self as graph::GraphPredecessors<'_>>::Iter { + fn predecessors(&self, node: Self::Node) -> impl Iterator<Item = Self::Node> { self.predecessors()[node].iter().copied() } } diff --git a/compiler/rustc_middle/src/mir/generic_graphviz.rs b/compiler/rustc_middle/src/mir/generic_graphviz.rs index 299b50525cb..809d4cdce8d 100644 --- a/compiler/rustc_middle/src/mir/generic_graphviz.rs +++ b/compiler/rustc_middle/src/mir/generic_graphviz.rs @@ -5,7 +5,7 @@ use std::io::{self, Write}; pub struct GraphvizWriter< 'a, - G: graph::DirectedGraph + graph::WithSuccessors + graph::WithStartNode + graph::WithNumNodes, + G: graph::DirectedGraph + graph::Successors + graph::StartNode, NodeContentFn: Fn(<G as graph::DirectedGraph>::Node) -> Vec<String>, EdgeLabelsFn: Fn(<G as graph::DirectedGraph>::Node) -> Vec<String>, > { @@ -19,7 +19,7 @@ pub struct GraphvizWriter< impl< 'a, - G: graph::DirectedGraph + graph::WithSuccessors + graph::WithStartNode + graph::WithNumNodes, + G: graph::DirectedGraph + graph::Successors + graph::StartNode, NodeContentFn: Fn(<G as graph::DirectedGraph>::Node) -> Vec<String>, EdgeLabelsFn: Fn(<G as graph::DirectedGraph>::Node) -> Vec<String>, > GraphvizWriter<'a, G, NodeContentFn, EdgeLabelsFn> diff --git a/compiler/rustc_mir_transform/src/coverage/counters.rs b/compiler/rustc_mir_transform/src/coverage/counters.rs index 69dc4f2ddea..6e73a476421 100644 --- a/compiler/rustc_mir_transform/src/coverage/counters.rs +++ b/compiler/rustc_mir_transform/src/coverage/counters.rs @@ -2,7 +2,7 @@ use std::fmt::{self, Debug}; use rustc_data_structures::captures::Captures; use rustc_data_structures::fx::FxHashMap; -use rustc_data_structures::graph::WithNumNodes; +use rustc_data_structures::graph::DirectedGraph; use rustc_index::IndexVec; use rustc_middle::mir::coverage::{CounterId, CovTerm, Expression, ExpressionId, Op}; diff --git a/compiler/rustc_mir_transform/src/coverage/graph.rs b/compiler/rustc_mir_transform/src/coverage/graph.rs index ed8c4d8283d..1895735ab35 100644 --- a/compiler/rustc_mir_transform/src/coverage/graph.rs +++ b/compiler/rustc_mir_transform/src/coverage/graph.rs @@ -1,7 +1,7 @@ use rustc_data_structures::captures::Captures; use rustc_data_structures::fx::FxHashSet; use rustc_data_structures::graph::dominators::{self, Dominators}; -use rustc_data_structures::graph::{self, GraphSuccessors, WithNumNodes, WithStartNode}; +use rustc_data_structures::graph::{self, DirectedGraph, StartNode}; use rustc_index::bit_set::BitSet; use rustc_index::IndexVec; use rustc_middle::mir::{self, BasicBlock, Terminator, TerminatorKind}; @@ -193,16 +193,14 @@ impl IndexMut<BasicCoverageBlock> for CoverageGraph { impl graph::DirectedGraph for CoverageGraph { type Node = BasicCoverageBlock; -} -impl graph::WithNumNodes for CoverageGraph { #[inline] fn num_nodes(&self) -> usize { self.bcbs.len() } } -impl graph::WithStartNode for CoverageGraph { +impl graph::StartNode for CoverageGraph { #[inline] fn start_node(&self) -> Self::Node { self.bcb_from_bb(mir::START_BLOCK) @@ -210,28 +208,16 @@ impl graph::WithStartNode for CoverageGraph { } } -type BcbSuccessors<'graph> = std::slice::Iter<'graph, BasicCoverageBlock>; - -impl<'graph> graph::GraphSuccessors<'graph> for CoverageGraph { - type Item = BasicCoverageBlock; - type Iter = std::iter::Cloned<BcbSuccessors<'graph>>; -} - -impl graph::WithSuccessors for CoverageGraph { +impl graph::Successors for CoverageGraph { #[inline] - fn successors(&self, node: Self::Node) -> <Self as GraphSuccessors<'_>>::Iter { + fn successors(&self, node: Self::Node) -> impl Iterator<Item = Self::Node> { self.successors[node].iter().cloned() } } -impl<'graph> graph::GraphPredecessors<'graph> for CoverageGraph { - type Item = BasicCoverageBlock; - type Iter = std::iter::Copied<std::slice::Iter<'graph, BasicCoverageBlock>>; -} - -impl graph::WithPredecessors for CoverageGraph { +impl graph::Predecessors for CoverageGraph { #[inline] - fn predecessors(&self, node: Self::Node) -> <Self as graph::GraphPredecessors<'_>>::Iter { + fn predecessors(&self, node: Self::Node) -> impl Iterator<Item = Self::Node> { self.predecessors[node].iter().copied() } } diff --git a/compiler/rustc_mir_transform/src/coverage/spans.rs b/compiler/rustc_mir_transform/src/coverage/spans.rs index 672de1fbe60..03ede886688 100644 --- a/compiler/rustc_mir_transform/src/coverage/spans.rs +++ b/compiler/rustc_mir_transform/src/coverage/spans.rs @@ -1,4 +1,4 @@ -use rustc_data_structures::graph::WithNumNodes; +use rustc_data_structures::graph::DirectedGraph; use rustc_index::bit_set::BitSet; use rustc_middle::mir; use rustc_span::{BytePos, Span}; diff --git a/compiler/rustc_mir_transform/src/coverage/tests.rs b/compiler/rustc_mir_transform/src/coverage/tests.rs index 569998de35e..cf1a2b399f9 100644 --- a/compiler/rustc_mir_transform/src/coverage/tests.rs +++ b/compiler/rustc_mir_transform/src/coverage/tests.rs @@ -28,8 +28,7 @@ use super::counters; use super::graph::{self, BasicCoverageBlock}; use itertools::Itertools; -use rustc_data_structures::graph::WithNumNodes; -use rustc_data_structures::graph::WithSuccessors; +use rustc_data_structures::graph::{DirectedGraph, Successors}; use rustc_index::{Idx, IndexVec}; use rustc_middle::mir::*; use rustc_middle::ty; |