Rollup merge of #140305 - compiler-errors:coerce-loop, r=lcnr

Track per-obligation recursion depth only if there is inference in the new solver

Track how many times an obligation has been processed in the fulfillment context by reusing its recursion depth, and only overflow if a singular (root) goal hits the limit.

This also fixes a (probably theoretical at this point) problem where we don't detect pseudo-hangs across `select_where_possible` calls.

fixes https://github.com/rust-lang/trait-system-refactor-initiative/issues/186

r? lcnr

2 files changed, 46 insertions, 8 deletions

diff --git a/compiler/rustc_trait_selection/src/solve/fulfill.rs b/compiler/rustc_trait_selection/src/solve/fulfill.rs
index 848d0646d00..1f4fa5aac10 100644
--- a/compiler/rustc_trait_selection/src/solve/fulfill.rs
+++ b/compiler/rustc_trait_selection/src/solve/fulfill.rs
@@ -163,15 +163,15 @@ where
     fn select_where_possible(&mut self, infcx: &InferCtxt<'tcx>) -> Vec<E> {
         assert_eq!(self.usable_in_snapshot, infcx.num_open_snapshots());
         let mut errors = Vec::new();
-        for i in 0.. {
-            if !infcx.tcx.recursion_limit().value_within_limit(i) {
-                self.obligations.on_fulfillment_overflow(infcx);
-                // Only return true errors that we have accumulated while processing.
-                return errors;
-            }
-
+        loop {
             let mut has_changed = false;
-            for obligation in self.obligations.drain_pending(|_| true) {
+            for mut obligation in self.obligations.drain_pending(|_| true) {
+                if !infcx.tcx.recursion_limit().value_within_limit(obligation.recursion_depth) {
+                    self.obligations.on_fulfillment_overflow(infcx);
+                    // Only return true errors that we have accumulated while processing.
+                    return errors;
+                }
+
                 let goal = obligation.as_goal();
                 let result = <&SolverDelegate<'tcx>>::from(infcx)
                     .evaluate_root_goal(goal, GenerateProofTree::No, obligation.cause.span)
@@ -189,6 +189,13 @@ where
                 };
 
                 if changed == HasChanged::Yes {
+                    // We increment the recursion depth here to track the number of times
+                    // this goal has resulted in inference progress. This doesn't precisely
+                    // model the way that we track recursion depth in the old solver due
+                    // to the fact that we only process root obligations, but it is a good
+                    // approximation and should only result in fulfillment overflow in
+                    // pathological cases.
+                    obligation.recursion_depth += 1;
                     has_changed = true;
                 }
 
diff --git a/tests/ui/traits/next-solver/coerce-depth.rs b/tests/ui/traits/next-solver/coerce-depth.rs
new file mode 100644
index 00000000000..c8fc3fcab59
--- /dev/null
+++ b/tests/ui/traits/next-solver/coerce-depth.rs
@@ -0,0 +1,31 @@
+//@ check-pass
+//@ compile-flags: -Znext-solver
+
+// Ensure that a stack of coerce predicates doesn't end up overflowing when they get procesed
+// in *reverse* order, which may require O(N) iterations of the fulfillment loop.
+
+#![recursion_limit = "16"]
+
+fn main() {
+    match 0 {
+        0 => None,
+        1 => None,
+        2 => None,
+        3 => None,
+        4 => None,
+        5 => None,
+        6 => None,
+        7 => None,
+        8 => None,
+        9 => None,
+        10 => None,
+        11 => None,
+        12 => None,
+        13 => None,
+        14 => None,
+        15 => None,
+        16 => None,
+        17 => None,
+        _ => Some(1u32),
+    };
+}