Make `depth_first_search` into a standalone function

Does not necessarily change much, but we never overwrite it, so I see no reason
for it to be in the `Successors` trait. (+we already have a similar `is_cyclic`)

6 files changed, 21 insertions, 17 deletions

diff --git a/compiler/rustc_borrowck/src/dataflow.rs b/compiler/rustc_borrowck/src/dataflow.rs
index c185986a7d8..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::Successors;
+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 7d7a3c09370..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::Successors;
 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 5b92dca430f..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::Successors;
 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(
+                &region_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/mod.rs b/compiler/rustc_data_structures/src/graph/mod.rs
index 189474395ee..61bee2ee0bb 100644
--- a/compiler/rustc_data_structures/src/graph/mod.rs
+++ b/compiler/rustc_data_structures/src/graph/mod.rs
@@ -30,10 +30,6 @@ pub trait Successors: DirectedGraph {
         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)
-    }
 }
 
 pub trait Predecessors: DirectedGraph {
@@ -57,3 +53,10 @@ where
         .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/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 4efedb4a4a6..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::Successors,
-    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