Auto merge of #56722 - Aaron1011:fix/blanket-eval-overflow, r=nikomatsakis

Fix stack overflow when finding blanket impls

Currently, SelectionContext tries to prevent stack overflow by keeping
track of the current recursion depth. However, this depth tracking is
only used when performing normal section (which includes confirmation).
No such tracking is performed for evaluate_obligation_recursively, which
can allow a stack overflow to occur.

To fix this, this commit tracks the current predicate evaluation depth.
This is done separately from the existing obligation depth tracking:
an obligation overflow can occur across multiple calls to 'select' (e.g.
when fulfilling a trait), while a predicate evaluation overflow can only
happen as a result of a deep recursive call stack.

Fixes #56701

I've re-used `tcx.sess.recursion_limit` when checking for predication evaluation overflows. This is such a weird corner case that I don't believe it's necessary to have a separate setting controlling the maximum depth.

7 files changed, 41 insertions, 10 deletions

diff --git a/src/test/run-pass/weird-exprs.rs b/src/test/run-pass/weird-exprs.rs
index 6d0c5c11732..7ce7e29e872 100644
--- a/src/test/run-pass/weird-exprs.rs
+++ b/src/test/run-pass/weird-exprs.rs
@@ -4,7 +4,7 @@
 #![allow(unused_parens)]
 // compile-flags: -Z borrowck=compare
 
-#![recursion_limit = "128"]
+#![recursion_limit = "256"]
 
 use std::cell::Cell;
 use std::mem::swap;
diff --git a/src/test/rustdoc/issue-56701.rs b/src/test/rustdoc/issue-56701.rs
new file mode 100644
index 00000000000..6fb30a4ff4c
--- /dev/null
+++ b/src/test/rustdoc/issue-56701.rs
@@ -0,0 +1,34 @@
+// This shouldn't cause a stack overflow when rustdoc is run
+
+use std::ops::Deref;
+use std::ops::DerefMut;
+
+pub trait SimpleTrait {
+    type SimpleT;
+}
+
+impl<Inner: SimpleTrait, Outer: Deref<Target = Inner>> SimpleTrait for Outer {
+    type SimpleT = Inner::SimpleT;
+}
+
+pub trait AnotherTrait {
+    type AnotherT;
+}
+
+impl<T, Simple: SimpleTrait<SimpleT = Vec<T>>> AnotherTrait for Simple {
+    type AnotherT = T;
+}
+
+pub struct Unrelated<Inner, UnrelatedT: DerefMut<Target = Vec<Inner>>>(UnrelatedT);
+
+impl<Inner, UnrelatedT: DerefMut<Target = Vec<Inner>>> Deref for Unrelated<Inner, UnrelatedT> {
+    type Target = Vec<Inner>;
+
+    fn deref(&self) -> &Self::Target {
+        &self.0
+    }
+}
+
+
+pub fn main() { }
+
diff --git a/src/test/ui/did_you_mean/recursion_limit.stderr b/src/test/ui/did_you_mean/recursion_limit.stderr
index 08947fd7fdc..0738c3f65b9 100644
--- a/src/test/ui/did_you_mean/recursion_limit.stderr
+++ b/src/test/ui/did_you_mean/recursion_limit.stderr
@@ -1,11 +1,10 @@
-error[E0275]: overflow evaluating the requirement `K: std::marker::Send`
+error[E0275]: overflow evaluating the requirement `J: std::marker::Send`
   --> $DIR/recursion_limit.rs:34:5
    |
 LL |     is_send::<A>(); //~ ERROR overflow evaluating the requirement
    |     ^^^^^^^^^^^^
    |
    = help: consider adding a `#![recursion_limit="20"]` attribute to your crate
-   = note: required because it appears within the type `J`
    = note: required because it appears within the type `I`
    = note: required because it appears within the type `H`
    = note: required because it appears within the type `G`
diff --git a/src/test/ui/error-codes/E0055.rs b/src/test/ui/error-codes/E0055.rs
index a3ade92d24f..b525575d98d 100644
--- a/src/test/ui/error-codes/E0055.rs
+++ b/src/test/ui/error-codes/E0055.rs
@@ -1,4 +1,4 @@
-#![recursion_limit="2"]
+#![recursion_limit="5"]
 struct Foo;
 
 impl Foo {
@@ -7,7 +7,7 @@ impl Foo {
 
 fn main() {
     let foo = Foo;
-    let ref_foo = &&Foo;
+    let ref_foo = &&&&&Foo;
     ref_foo.foo();
     //~^ ERROR E0055
 }
diff --git a/src/test/ui/error-codes/E0055.stderr b/src/test/ui/error-codes/E0055.stderr
index cd2bd923d5a..d06566ffbe9 100644
--- a/src/test/ui/error-codes/E0055.stderr
+++ b/src/test/ui/error-codes/E0055.stderr
@@ -4,7 +4,7 @@ error[E0055]: reached the recursion limit while auto-dereferencing `Foo`
 LL |     ref_foo.foo();
    |             ^^^ deref recursion limit reached
    |
-   = help: consider adding a `#![recursion_limit="4"]` attribute to your crate
+   = help: consider adding a `#![recursion_limit="10"]` attribute to your crate
 
 error: aborting due to previous error
 
diff --git a/src/test/ui/error-codes/E0275.stderr b/src/test/ui/error-codes/E0275.stderr
index 817b4828cc4..f2b0f392bc8 100644
--- a/src/test/ui/error-codes/E0275.stderr
+++ b/src/test/ui/error-codes/E0275.stderr
@@ -1,11 +1,10 @@
-error[E0275]: overflow evaluating the requirement `Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<T>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>: std::marker::Sized`
+error[E0275]: overflow evaluating the requirement `Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<T>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>: Foo`
   --> $DIR/E0275.rs:5:1
    |
 LL | impl<T> Foo for T where Bar<T>: Foo {} //~ ERROR E0275
    | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    |
    = help: consider adding a `#![recursion_limit="128"]` attribute to your crate
-   = note: required because of the requirements on the impl of `Foo` for `Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<T>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>`
    = note: required because of the requirements on the impl of `Foo` for `Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<T>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>`
    = note: required because of the requirements on the impl of `Foo` for `Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<T>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>`
    = note: required because of the requirements on the impl of `Foo` for `Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<Bar<T>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>`
diff --git a/src/test/ui/issues/issue-20413.stderr b/src/test/ui/issues/issue-20413.stderr
index 20e57583f1d..1c353fec8aa 100644
--- a/src/test/ui/issues/issue-20413.stderr
+++ b/src/test/ui/issues/issue-20413.stderr
@@ -6,7 +6,7 @@ LL | struct NoData<T>;
    |
    = help: consider removing `T` or using a marker such as `std::marker::PhantomData`
 
-error[E0275]: overflow evaluating the requirement `NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<T>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>: std::marker::Sized`
+error[E0275]: overflow evaluating the requirement `NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<T>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>: Foo`
   --> $DIR/issue-20413.rs:8:1
    |
 LL | / impl<T> Foo for T where NoData<T>: Foo {
@@ -18,7 +18,6 @@ LL | | }
    | |_^
    |
    = help: consider adding a `#![recursion_limit="128"]` attribute to your crate
-   = note: required because of the requirements on the impl of `Foo` for `NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<T>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>`
    = note: required because of the requirements on the impl of `Foo` for `NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<T>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>`
    = note: required because of the requirements on the impl of `Foo` for `NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<T>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>`
    = note: required because of the requirements on the impl of `Foo` for `NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<NoData<T>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>`