evaluate: improve and fix recursion depth handling

9 files changed, 60 insertions, 95 deletions

diff --git a/compiler/rustc_infer/src/traits/mod.rs b/compiler/rustc_infer/src/traits/mod.rs
index 77c67c14ecc..dd9b2e548c7 100644
--- a/compiler/rustc_infer/src/traits/mod.rs
+++ b/compiler/rustc_infer/src/traits/mod.rs
@@ -8,6 +8,8 @@ mod project;
 mod structural_impls;
 pub mod util;
 
+use std::cmp;
+
 use hir::def_id::LocalDefId;
 use rustc_hir as hir;
 use rustc_middle::ty::error::{ExpectedFound, TypeError};
@@ -139,6 +141,14 @@ impl<'tcx, O> Obligation<'tcx, O> {
         Self::with_depth(tcx, cause, 0, param_env, predicate)
     }
 
+    /// We often create nested obligations without setting the correct depth.
+    ///
+    /// To deal with this evaluate and fulfill explicitly update the depth
+    /// of nested obligations using this function.
+    pub fn set_depth_from_parent(&mut self, parent_depth: usize) {
+        self.recursion_depth = cmp::max(parent_depth + 1, self.recursion_depth);
+    }
+
     pub fn with_depth(
         tcx: TyCtxt<'tcx>,
         cause: ObligationCause<'tcx>,
diff --git a/compiler/rustc_trait_selection/src/traits/select/mod.rs b/compiler/rustc_trait_selection/src/traits/select/mod.rs
index d9b2b7dbe16..b8758ad9323 100644
--- a/compiler/rustc_trait_selection/src/traits/select/mod.rs
+++ b/compiler/rustc_trait_selection/src/traits/select/mod.rs
@@ -595,7 +595,8 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
             self.evaluate_predicates_recursively_in_new_solver(predicates)
         } else {
             let mut result = EvaluatedToOk;
-            for obligation in predicates {
+            for mut obligation in predicates {
+                obligation.set_depth_from_parent(stack.depth());
                 let eval = self.evaluate_predicate_recursively(stack, obligation.clone())?;
                 if let EvaluatedToErr = eval {
                     // fast-path - EvaluatedToErr is the top of the lattice,
@@ -661,12 +662,8 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                     let p = bound_predicate.rebind(p);
                     // Does this code ever run?
                     match self.infcx.subtype_predicate(&obligation.cause, obligation.param_env, p) {
-                        Ok(Ok(InferOk { mut obligations, .. })) => {
-                            self.add_depth(obligations.iter_mut(), obligation.recursion_depth);
-                            self.evaluate_predicates_recursively(
-                                previous_stack,
-                                obligations.into_iter(),
-                            )
+                        Ok(Ok(InferOk { obligations, .. })) => {
+                            self.evaluate_predicates_recursively(previous_stack, obligations)
                         }
                         Ok(Err(_)) => Ok(EvaluatedToErr),
                         Err(..) => Ok(EvaluatedToAmbig),
@@ -677,12 +674,8 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                     let p = bound_predicate.rebind(p);
                     // Does this code ever run?
                     match self.infcx.coerce_predicate(&obligation.cause, obligation.param_env, p) {
-                        Ok(Ok(InferOk { mut obligations, .. })) => {
-                            self.add_depth(obligations.iter_mut(), obligation.recursion_depth);
-                            self.evaluate_predicates_recursively(
-                                previous_stack,
-                                obligations.into_iter(),
-                            )
+                        Ok(Ok(InferOk { obligations, .. })) => {
+                            self.evaluate_predicates_recursively(previous_stack, obligations)
                         }
                         Ok(Err(_)) => Ok(EvaluatedToErr),
                         Err(..) => Ok(EvaluatedToAmbig),
@@ -755,9 +748,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                         arg,
                         obligation.cause.span,
                     ) {
-                        Some(mut obligations) => {
-                            self.add_depth(obligations.iter_mut(), obligation.recursion_depth);
-
+                        Some(obligations) => {
                             cache.wf_args.borrow_mut().push((arg, previous_stack.depth()));
                             let result =
                                 self.evaluate_predicates_recursively(previous_stack, obligations);
@@ -826,10 +817,14 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                                     }
                                 }
 
-                                self.add_depth(
-                                    subobligations.iter_mut(),
-                                    obligation.recursion_depth,
-                                );
+                                // Need to explicitly set the depth of nested goals here as
+                                // projection obligations can cycle by themselves and in
+                                // `evaluate_predicates_recursively` we only add the depth
+                                // for parent trait goals because only these get added to the
+                                // `TraitObligationStackList`.
+                                for subobligation in subobligations.iter_mut() {
+                                    subobligation.set_depth_from_parent(obligation.recursion_depth);
+                                }
                                 let res = self.evaluate_predicates_recursively(
                                     previous_stack,
                                     subobligations,
@@ -909,38 +904,28 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                                 if a.def.did == b.def.did
                                     && tcx.def_kind(a.def.did) == DefKind::AssocConst =>
                             {
-                                if let Ok(new_obligations) = self
+                                if let Ok(InferOk { obligations, value: () }) = self
                                     .infcx
                                     .at(&obligation.cause, obligation.param_env)
                                     .trace(c1, c2)
                                     .eq(DefineOpaqueTypes::No, a.substs, b.substs)
                                 {
-                                    let mut obligations = new_obligations.obligations;
-                                    self.add_depth(
-                                        obligations.iter_mut(),
-                                        obligation.recursion_depth,
-                                    );
                                     return self.evaluate_predicates_recursively(
                                         previous_stack,
-                                        obligations.into_iter(),
+                                        obligations,
                                     );
                                 }
                             }
                             (_, Unevaluated(_)) | (Unevaluated(_), _) => (),
                             (_, _) => {
-                                if let Ok(new_obligations) = self
+                                if let Ok(InferOk { obligations, value: () }) = self
                                     .infcx
                                     .at(&obligation.cause, obligation.param_env)
                                     .eq(DefineOpaqueTypes::No, c1, c2)
                                 {
-                                    let mut obligations = new_obligations.obligations;
-                                    self.add_depth(
-                                        obligations.iter_mut(),
-                                        obligation.recursion_depth,
-                                    );
                                     return self.evaluate_predicates_recursively(
                                         previous_stack,
-                                        obligations.into_iter(),
+                                        obligations,
                                     );
                                 }
                             }
@@ -1366,24 +1351,6 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
         self.infcx.evaluation_cache.insert((param_env, trait_pred), dep_node, result);
     }
 
-    /// For various reasons, it's possible for a subobligation
-    /// to have a *lower* recursion_depth than the obligation used to create it.
-    /// Projection sub-obligations may be returned from the projection cache,
-    /// which results in obligations with an 'old' `recursion_depth`.
-    /// Additionally, methods like `InferCtxt.subtype_predicate` produce
-    /// subobligations without taking in a 'parent' depth, causing the
-    /// generated subobligations to have a `recursion_depth` of `0`.
-    ///
-    /// To ensure that obligation_depth never decreases, we force all subobligations
-    /// to have at least the depth of the original obligation.
-    fn add_depth<T: 'cx, I: Iterator<Item = &'cx mut Obligation<'tcx, T>>>(
-        &self,
-        it: I,
-        min_depth: usize,
-    ) {
-        it.for_each(|o| o.recursion_depth = cmp::max(min_depth, o.recursion_depth) + 1);
-    }
-
     fn check_recursion_depth<T>(
         &self,
         depth: usize,
diff --git a/tests/ui/associated-consts/issue-93775.rs b/tests/ui/associated-consts/issue-93775.rs
index 7a007b732de..db788fe6e6a 100644
--- a/tests/ui/associated-consts/issue-93775.rs
+++ b/tests/ui/associated-consts/issue-93775.rs
@@ -3,7 +3,7 @@
 
 // Regression for #93775, needs build-pass to test it.
 
-#![recursion_limit = "1000"]
+#![recursion_limit = "1001"]
 
 use std::marker::PhantomData;
 
diff --git a/tests/ui/did_you_mean/recursion_limit.stderr b/tests/ui/did_you_mean/recursion_limit.stderr
index 247fe4b5b07..70e49566ac0 100644
--- a/tests/ui/did_you_mean/recursion_limit.stderr
+++ b/tests/ui/did_you_mean/recursion_limit.stderr
@@ -1,15 +1,10 @@
-error[E0275]: overflow evaluating the requirement `K: Send`
+error[E0275]: overflow evaluating the requirement `J: Send`
   --> $DIR/recursion_limit.rs:34:5
    |
 LL |     is_send::<A>();
    |     ^^^^^^^^^^^^
    |
    = help: consider increasing the recursion limit by adding a `#![recursion_limit = "20"]` attribute to your crate (`recursion_limit`)
-note: required because it appears within the type `J`
-  --> $DIR/recursion_limit.rs:24:9
-   |
-LL | link! { J, K }
-   |         ^
 note: required because it appears within the type `I`
   --> $DIR/recursion_limit.rs:23:9
    |
diff --git a/tests/ui/error-codes/E0275.stderr b/tests/ui/error-codes/E0275.stderr
index cf9a7f69bfb..03c37d6f0e1 100644
--- a/tests/ui/error-codes/E0275.stderr
+++ b/tests/ui/error-codes/E0275.stderr
@@ -11,7 +11,7 @@ note: required for `Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<
 LL | impl<T> Foo for T where Bar<T>: Foo {}
    |         ^^^     ^               --- unsatisfied trait bound introduced here
    = note: the full type name has been written to '$TEST_BUILD_DIR/error-codes/E0275/E0275.long-type-hash.txt'
-   = note: 127 redundant requirements hidden
+   = note: 126 redundant requirements hidden
    = note: required for `Bar<T>` to implement `Foo`
 
 error: aborting due to previous error
diff --git a/tests/ui/issues/issue-20413.stderr b/tests/ui/issues/issue-20413.stderr
index 202e8463145..8891a26784e 100644
--- a/tests/ui/issues/issue-20413.stderr
+++ b/tests/ui/issues/issue-20413.stderr
@@ -20,51 +20,51 @@ note: required for `NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoDa
 LL | impl<T> Foo for T where NoData<T>: Foo {
    |         ^^^     ^                  --- unsatisfied trait bound introduced here
    = note: the full type name has been written to '$TEST_BUILD_DIR/issues/issue-20413/issue-20413.long-type-hash.txt'
-   = note: 127 redundant requirements hidden
+   = note: 126 redundant requirements hidden
    = note: required for `NoData<T>` to implement `Foo`
 
-error[E0275]: overflow evaluating the requirement `EvenLessData<AlmostNoData<EvenLessData<AlmostNoData<EvenLessData<AlmostNoData<EvenLessData<...>>>>>>>: Baz`
+error[E0275]: overflow evaluating the requirement `AlmostNoData<EvenLessData<AlmostNoData<EvenLessData<AlmostNoData<EvenLessData<AlmostNoData<...>>>>>>>: Bar`
   --> $DIR/issue-20413.rs:28:42
    |
 LL | impl<T> Bar for T where EvenLessData<T>: Baz {
    |                                          ^^^
    |
    = help: consider increasing the recursion limit by adding a `#![recursion_limit = "256"]` attribute to your crate (`issue_20413`)
-note: required for `AlmostNoData<EvenLessData<AlmostNoData<EvenLessData<AlmostNoData<EvenLessData<AlmostNoData<...>>>>>>>` to implement `Bar`
-  --> $DIR/issue-20413.rs:28:9
-   |
-LL | impl<T> Bar for T where EvenLessData<T>: Baz {
-   |         ^^^     ^                        --- unsatisfied trait bound introduced here
-   = note: the full type name has been written to '$TEST_BUILD_DIR/issues/issue-20413/issue-20413.long-type-hash.txt'
 note: required for `EvenLessData<AlmostNoData<EvenLessData<AlmostNoData<EvenLessData<AlmostNoData<EvenLessData<...>>>>>>>` to implement `Baz`
   --> $DIR/issue-20413.rs:35:9
    |
 LL | impl<T> Baz for T where AlmostNoData<T>: Bar {
    |         ^^^     ^                        --- unsatisfied trait bound introduced here
    = note: the full type name has been written to '$TEST_BUILD_DIR/issues/issue-20413/issue-20413.long-type-hash.txt'
-   = note: 126 redundant requirements hidden
+note: required for `AlmostNoData<EvenLessData<AlmostNoData<EvenLessData<AlmostNoData<EvenLessData<AlmostNoData<...>>>>>>>` to implement `Bar`
+  --> $DIR/issue-20413.rs:28:9
+   |
+LL | impl<T> Bar for T where EvenLessData<T>: Baz {
+   |         ^^^     ^                        --- unsatisfied trait bound introduced here
+   = note: the full type name has been written to '$TEST_BUILD_DIR/issues/issue-20413/issue-20413.long-type-hash.txt'
+   = note: 125 redundant requirements hidden
    = note: required for `EvenLessData<T>` to implement `Baz`
 
-error[E0275]: overflow evaluating the requirement `AlmostNoData<EvenLessData<AlmostNoData<EvenLessData<AlmostNoData<EvenLessData<AlmostNoData<...>>>>>>>: Bar`
+error[E0275]: overflow evaluating the requirement `EvenLessData<AlmostNoData<EvenLessData<AlmostNoData<EvenLessData<AlmostNoData<EvenLessData<...>>>>>>>: Baz`
   --> $DIR/issue-20413.rs:35:42
    |
 LL | impl<T> Baz for T where AlmostNoData<T>: Bar {
    |                                          ^^^
    |
    = help: consider increasing the recursion limit by adding a `#![recursion_limit = "256"]` attribute to your crate (`issue_20413`)
-note: required for `EvenLessData<AlmostNoData<EvenLessData<AlmostNoData<EvenLessData<AlmostNoData<EvenLessData<...>>>>>>>` to implement `Baz`
-  --> $DIR/issue-20413.rs:35:9
-   |
-LL | impl<T> Baz for T where AlmostNoData<T>: Bar {
-   |         ^^^     ^                        --- unsatisfied trait bound introduced here
-   = note: the full type name has been written to '$TEST_BUILD_DIR/issues/issue-20413/issue-20413.long-type-hash.txt'
 note: required for `AlmostNoData<EvenLessData<AlmostNoData<EvenLessData<AlmostNoData<EvenLessData<AlmostNoData<...>>>>>>>` to implement `Bar`
   --> $DIR/issue-20413.rs:28:9
    |
 LL | impl<T> Bar for T where EvenLessData<T>: Baz {
    |         ^^^     ^                        --- unsatisfied trait bound introduced here
    = note: the full type name has been written to '$TEST_BUILD_DIR/issues/issue-20413/issue-20413.long-type-hash.txt'
-   = note: 126 redundant requirements hidden
+note: required for `EvenLessData<AlmostNoData<EvenLessData<AlmostNoData<EvenLessData<AlmostNoData<EvenLessData<...>>>>>>>` to implement `Baz`
+  --> $DIR/issue-20413.rs:35:9
+   |
+LL | impl<T> Baz for T where AlmostNoData<T>: Bar {
+   |         ^^^     ^                        --- unsatisfied trait bound introduced here
+   = note: the full type name has been written to '$TEST_BUILD_DIR/issues/issue-20413/issue-20413.long-type-hash.txt'
+   = note: 125 redundant requirements hidden
    = note: required for `AlmostNoData<T>` to implement `Bar`
 
 error: aborting due to 4 previous errors
diff --git a/tests/ui/traits/cycle-cache-err-60010.stderr b/tests/ui/traits/cycle-cache-err-60010.stderr
index eeee997608e..2ff16b4af38 100644
--- a/tests/ui/traits/cycle-cache-err-60010.stderr
+++ b/tests/ui/traits/cycle-cache-err-60010.stderr
@@ -1,22 +1,9 @@
-error[E0275]: overflow evaluating the requirement `SalsaStorage: RefUnwindSafe`
+error[E0275]: overflow evaluating the requirement `RootDatabase: RefUnwindSafe`
   --> $DIR/cycle-cache-err-60010.rs:27:13
    |
 LL |     _parse: <ParseQuery as Query<RootDatabase>>::Data,
    |             ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    |
-   = note: required because it appears within the type `PhantomData<SalsaStorage>`
-   = note: required because it appears within the type `Unique<SalsaStorage>`
-   = note: required because it appears within the type `Box<SalsaStorage>`
-note: required because it appears within the type `Runtime<RootDatabase>`
-  --> $DIR/cycle-cache-err-60010.rs:23:8
-   |
-LL | struct Runtime<DB: Database> {
-   |        ^^^^^^^
-note: required because it appears within the type `RootDatabase`
-  --> $DIR/cycle-cache-err-60010.rs:20:8
-   |
-LL | struct RootDatabase {
-   |        ^^^^^^^^^^^^
 note: required for `RootDatabase` to implement `SourceDatabase`
   --> $DIR/cycle-cache-err-60010.rs:44:9
    |
diff --git a/tests/ui/traits/issue-91949-hangs-on-recursion.rs b/tests/ui/traits/issue-91949-hangs-on-recursion.rs
index 6474b2b38e1..4eca643a92d 100644
--- a/tests/ui/traits/issue-91949-hangs-on-recursion.rs
+++ b/tests/ui/traits/issue-91949-hangs-on-recursion.rs
@@ -1,6 +1,6 @@
 // build-fail
 // compile-flags: -Zinline-mir=no
-// error-pattern: overflow evaluating the requirement `(): Sized`
+// error-pattern: overflow evaluating the requirement `<std::iter::Empty<()> as Iterator>::Item == ()`
 // error-pattern: function cannot return without recursing
 // normalize-stderr-test: "long-type-\d+" -> "long-type-hash"
 
diff --git a/tests/ui/traits/issue-91949-hangs-on-recursion.stderr b/tests/ui/traits/issue-91949-hangs-on-recursion.stderr
index 1f18c5daf66..144990d50f0 100644
--- a/tests/ui/traits/issue-91949-hangs-on-recursion.stderr
+++ b/tests/ui/traits/issue-91949-hangs-on-recursion.stderr
@@ -12,11 +12,17 @@ LL |       recurse(IteratorOfWrapped(elements).map(|t| t.0))
    = help: a `loop` may express intention better if this is on purpose
    = note: `#[warn(unconditional_recursion)]` on by default
 
-error[E0275]: overflow evaluating the requirement `(): Sized`
+error[E0275]: overflow evaluating the requirement `<std::iter::Empty<()> as Iterator>::Item == ()`
    |
    = help: consider increasing the recursion limit by adding a `#![recursion_limit = "512"]` attribute to your crate (`issue_91949_hangs_on_recursion`)
-   = note: required for `std::iter::Empty<()>` to implement `Iterator`
-   = note: 171 redundant requirements hidden
+note: required for `IteratorOfWrapped<(), std::iter::Empty<()>>` to implement `Iterator`
+  --> $DIR/issue-91949-hangs-on-recursion.rs:16:32
+   |
+LL | impl<T, I: Iterator<Item = T>> Iterator for IteratorOfWrapped<T, I> {
+   |                     --------   ^^^^^^^^     ^^^^^^^^^^^^^^^^^^^^^^^
+   |                     |
+   |                     unsatisfied trait bound introduced here
+   = note: 256 redundant requirements hidden
    = note: required for `IteratorOfWrapped<(), Map<IteratorOfWrapped<(), Map<IteratorOfWrapped<(), Map<..., ...>>, ...>>, ...>>` to implement `Iterator`
    = note: the full type name has been written to '$TEST_BUILD_DIR/traits/issue-91949-hangs-on-recursion/issue-91949-hangs-on-recursion.long-type-hash.txt'