Prevent caching projections in the case of cycles

When normalizing a projection which results in a cycle, we would
cache the result of `project_type` without the nested obligations
(because they're not needed for inference). This would result in
the nested obligations only being handled once in fulfill, which
would avoid the cycle error.

Fixes #79714, a regresion from #79305 caused by the removal of
`get_paranoid_cache_value_obligation`.

11 files changed, 150 insertions, 21 deletions

diff --git a/compiler/rustc_infer/src/traits/project.rs b/compiler/rustc_infer/src/traits/project.rs
index 65284bcee91..33bddf1dedc 100644
--- a/compiler/rustc_infer/src/traits/project.rs
+++ b/compiler/rustc_infer/src/traits/project.rs
@@ -90,6 +90,7 @@ impl ProjectionCacheKey<'tcx> {
 pub enum ProjectionCacheEntry<'tcx> {
     InProgress,
     Ambiguous,
+    Recur,
     Error,
     NormalizedTy(NormalizedTy<'tcx>),
 }
@@ -143,7 +144,12 @@ impl<'tcx> ProjectionCache<'_, 'tcx> {
             "ProjectionCacheEntry::insert_ty: adding cache entry: key={:?}, value={:?}",
             key, value
         );
-        let fresh_key = self.map().insert(key, ProjectionCacheEntry::NormalizedTy(value));
+        let mut map = self.map();
+        if let Some(ProjectionCacheEntry::Recur) = map.get(&key) {
+            debug!("Not overwriting Recur");
+            return;
+        }
+        let fresh_key = map.insert(key, ProjectionCacheEntry::NormalizedTy(value));
         assert!(!fresh_key, "never started projecting `{:?}`", key);
     }
 
@@ -197,6 +203,14 @@ impl<'tcx> ProjectionCache<'_, 'tcx> {
         assert!(!fresh, "never started projecting `{:?}`", key);
     }
 
+    /// Indicates that while trying to normalize `key`, `key` was required to
+    /// be normalized again. Selection or evaluation should eventually report
+    /// an error here.
+    pub fn recur(&mut self, key: ProjectionCacheKey<'tcx>) {
+        let fresh = self.map().insert(key, ProjectionCacheEntry::Recur);
+        assert!(!fresh, "never started projecting `{:?}`", key);
+    }
+
     /// Indicates that trying to normalize `key` resulted in
     /// error.
     pub fn error(&mut self, key: ProjectionCacheKey<'tcx>) {
diff --git a/compiler/rustc_trait_selection/src/traits/project.rs b/compiler/rustc_trait_selection/src/traits/project.rs
index 7fa070caa27..fa0526445c1 100644
--- a/compiler/rustc_trait_selection/src/traits/project.rs
+++ b/compiler/rustc_trait_selection/src/traits/project.rs
@@ -496,12 +496,6 @@ fn opt_normalize_projection_type<'a, 'b, 'tcx>(
             return Ok(None);
         }
         Err(ProjectionCacheEntry::InProgress) => {
-            // If while normalized A::B, we are asked to normalize
-            // A::B, just return A::B itself. This is a conservative
-            // answer, in the sense that A::B *is* clearly equivalent
-            // to A::B, though there may be a better value we can
-            // find.
-
             // Under lazy normalization, this can arise when
             // bootstrapping.  That is, imagine an environment with a
             // where-clause like `A::B == u32`. Now, if we are asked
@@ -512,6 +506,14 @@ fn opt_normalize_projection_type<'a, 'b, 'tcx>(
 
             debug!("found cache entry: in-progress");
 
+            // Cache that normalizing this projection resulted in a cycle. This
+            // should ensure that, unless this happens within a snapshot that's
+            // rolled back, fulfillment or evaluation will notice the cycle.
+
+            infcx.inner.borrow_mut().projection_cache().recur(cache_key);
+            return Err(InProgress);
+        }
+        Err(ProjectionCacheEntry::Recur) => {
             return Err(InProgress);
         }
         Err(ProjectionCacheEntry::NormalizedTy(ty)) => {
diff --git a/compiler/rustc_trait_selection/src/traits/select/mod.rs b/compiler/rustc_trait_selection/src/traits/select/mod.rs
index f1c86eab095..a8f81445b03 100644
--- a/compiler/rustc_trait_selection/src/traits/select/mod.rs
+++ b/compiler/rustc_trait_selection/src/traits/select/mod.rs
@@ -291,6 +291,10 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
         self.infcx.tcx
     }
 
+    pub(super) fn query_mode(&self) -> TraitQueryMode {
+        self.query_mode
+    }
+
     ///////////////////////////////////////////////////////////////////////////
     // Selection
     //
diff --git a/src/test/ui/associated-types/defaults-cyclic-fail-1.rs b/src/test/ui/associated-types/defaults-cyclic-fail-1.rs
index afb2b3df716..61ef013236e 100644
--- a/src/test/ui/associated-types/defaults-cyclic-fail-1.rs
+++ b/src/test/ui/associated-types/defaults-cyclic-fail-1.rs
@@ -24,13 +24,13 @@ impl Tr for u32 {
 // ...but not in an impl that redefines one of the types.
 impl Tr for bool {
     type A = Box<Self::B>;
-    //~^ ERROR type mismatch resolving `<bool as Tr>::B == _`
+    //~^ ERROR overflow evaluating the requirement `<bool as Tr>::B == _`
 }
 // (the error is shown twice for some reason)
 
 impl Tr for usize {
     type B = &'static Self::A;
-    //~^ ERROR type mismatch resolving `<usize as Tr>::A == _`
+    //~^ ERROR overflow evaluating the requirement `<usize as Tr>::A == _`
 }
 
 fn main() {
diff --git a/src/test/ui/associated-types/defaults-cyclic-fail-1.stderr b/src/test/ui/associated-types/defaults-cyclic-fail-1.stderr
index ae7150d47ca..5e98520b411 100644
--- a/src/test/ui/associated-types/defaults-cyclic-fail-1.stderr
+++ b/src/test/ui/associated-types/defaults-cyclic-fail-1.stderr
@@ -1,15 +1,15 @@
-error[E0271]: type mismatch resolving `<bool as Tr>::B == _`
+error[E0275]: overflow evaluating the requirement `<bool as Tr>::B == _`
   --> $DIR/defaults-cyclic-fail-1.rs:26:5
    |
 LL |     type A = Box<Self::B>;
-   |     ^^^^^^^^^^^^^^^^^^^^^^ cyclic type of infinite size
+   |     ^^^^^^^^^^^^^^^^^^^^^^
 
-error[E0271]: type mismatch resolving `<usize as Tr>::A == _`
+error[E0275]: overflow evaluating the requirement `<usize as Tr>::A == _`
   --> $DIR/defaults-cyclic-fail-1.rs:32:5
    |
 LL |     type B = &'static Self::A;
-   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^ cyclic type of infinite size
+   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^
 
 error: aborting due to 2 previous errors
 
-For more information about this error, try `rustc --explain E0271`.
+For more information about this error, try `rustc --explain E0275`.
diff --git a/src/test/ui/associated-types/defaults-cyclic-fail-2.rs b/src/test/ui/associated-types/defaults-cyclic-fail-2.rs
index ba4bb0d5a29..e91c9f2d29a 100644
--- a/src/test/ui/associated-types/defaults-cyclic-fail-2.rs
+++ b/src/test/ui/associated-types/defaults-cyclic-fail-2.rs
@@ -25,13 +25,13 @@ impl Tr for u32 {
 
 impl Tr for bool {
     type A = Box<Self::B>;
-    //~^ ERROR type mismatch resolving `<bool as Tr>::B == _`
+    //~^ ERROR overflow evaluating the requirement `<bool as Tr>::B == _`
 }
 // (the error is shown twice for some reason)
 
 impl Tr for usize {
     type B = &'static Self::A;
-    //~^ ERROR type mismatch resolving `<usize as Tr>::A == _`
+    //~^ ERROR overflow evaluating the requirement `<usize as Tr>::A == _`
 }
 
 fn main() {
diff --git a/src/test/ui/associated-types/defaults-cyclic-fail-2.stderr b/src/test/ui/associated-types/defaults-cyclic-fail-2.stderr
index 0dfbac2dec5..c538805f858 100644
--- a/src/test/ui/associated-types/defaults-cyclic-fail-2.stderr
+++ b/src/test/ui/associated-types/defaults-cyclic-fail-2.stderr
@@ -1,15 +1,15 @@
-error[E0271]: type mismatch resolving `<bool as Tr>::B == _`
+error[E0275]: overflow evaluating the requirement `<bool as Tr>::B == _`
   --> $DIR/defaults-cyclic-fail-2.rs:27:5
    |
 LL |     type A = Box<Self::B>;
-   |     ^^^^^^^^^^^^^^^^^^^^^^ cyclic type of infinite size
+   |     ^^^^^^^^^^^^^^^^^^^^^^
 
-error[E0271]: type mismatch resolving `<usize as Tr>::A == _`
+error[E0275]: overflow evaluating the requirement `<usize as Tr>::A == _`
   --> $DIR/defaults-cyclic-fail-2.rs:33:5
    |
 LL |     type B = &'static Self::A;
-   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^ cyclic type of infinite size
+   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^
 
 error: aborting due to 2 previous errors
 
-For more information about this error, try `rustc --explain E0271`.
+For more information about this error, try `rustc --explain E0275`.
diff --git a/src/test/ui/associated-types/impl-wf-cycle-1.rs b/src/test/ui/associated-types/impl-wf-cycle-1.rs
new file mode 100644
index 00000000000..ba074210a2b
--- /dev/null
+++ b/src/test/ui/associated-types/impl-wf-cycle-1.rs
@@ -0,0 +1,29 @@
+// Regression test for #79714
+
+trait Baz {}
+impl Baz for () {}
+impl<T> Baz for (T,) {}
+
+trait Fiz {}
+impl Fiz for bool {}
+
+trait Grault {
+    type A;
+    type B;
+}
+
+impl<T: Grault> Grault for (T,)
+where
+    Self::A: Baz,
+    Self::B: Fiz,
+{
+    type A = ();
+    //~^ ERROR overflow evaluating the requirement `<(T,) as Grault>::A == _`
+    type B = bool;
+    //~^ ERROR overflow evaluating the requirement `<(T,) as Grault>::A == _`
+}
+//~^^^^^^^^^^ ERROR overflow evaluating the requirement `<(T,) as Grault>::A == _`
+
+fn main() {
+    let x: <(_,) as Grault>::A = ();
+}
diff --git a/src/test/ui/associated-types/impl-wf-cycle-1.stderr b/src/test/ui/associated-types/impl-wf-cycle-1.stderr
new file mode 100644
index 00000000000..82328048c99
--- /dev/null
+++ b/src/test/ui/associated-types/impl-wf-cycle-1.stderr
@@ -0,0 +1,39 @@
+error[E0275]: overflow evaluating the requirement `<(T,) as Grault>::A == _`
+  --> $DIR/impl-wf-cycle-1.rs:15:1
+   |
+LL | / impl<T: Grault> Grault for (T,)
+LL | | where
+LL | |     Self::A: Baz,
+LL | |     Self::B: Fiz,
+...  |
+LL | |
+LL | | }
+   | |_^
+   |
+   = note: required because of the requirements on the impl of `Grault` for `(T,)`
+   = note: 1 redundant requirements hidden
+   = note: required because of the requirements on the impl of `Grault` for `(T,)`
+
+error[E0275]: overflow evaluating the requirement `<(T,) as Grault>::A == _`
+  --> $DIR/impl-wf-cycle-1.rs:20:5
+   |
+LL |     type A = ();
+   |     ^^^^^^^^^^^^
+   |
+   = note: required because of the requirements on the impl of `Grault` for `(T,)`
+   = note: 1 redundant requirements hidden
+   = note: required because of the requirements on the impl of `Grault` for `(T,)`
+
+error[E0275]: overflow evaluating the requirement `<(T,) as Grault>::A == _`
+  --> $DIR/impl-wf-cycle-1.rs:22:5
+   |
+LL |     type B = bool;
+   |     ^^^^^^^^^^^^^^
+   |
+   = note: required because of the requirements on the impl of `Grault` for `(T,)`
+   = note: 1 redundant requirements hidden
+   = note: required because of the requirements on the impl of `Grault` for `(T,)`
+
+error: aborting due to 3 previous errors
+
+For more information about this error, try `rustc --explain E0275`.
diff --git a/src/test/ui/associated-types/impl-wf-cycle-2.rs b/src/test/ui/associated-types/impl-wf-cycle-2.rs
new file mode 100644
index 00000000000..6fccc54f229
--- /dev/null
+++ b/src/test/ui/associated-types/impl-wf-cycle-2.rs
@@ -0,0 +1,16 @@
+// Regression test for #79714
+
+trait Grault {
+    type A;
+}
+
+impl<T: Grault> Grault for (T,)
+where
+    Self::A: Copy,
+{
+    type A = ();
+    //~^ ERROR overflow evaluating the requirement `<(T,) as Grault>::A == _`
+}
+//~^^^^^^^ ERROR overflow evaluating the requirement `<(T,) as Grault>::A == _`
+
+fn main() {}
diff --git a/src/test/ui/associated-types/impl-wf-cycle-2.stderr b/src/test/ui/associated-types/impl-wf-cycle-2.stderr
new file mode 100644
index 00000000000..5cd18a33adf
--- /dev/null
+++ b/src/test/ui/associated-types/impl-wf-cycle-2.stderr
@@ -0,0 +1,25 @@
+error[E0275]: overflow evaluating the requirement `<(T,) as Grault>::A == _`
+  --> $DIR/impl-wf-cycle-2.rs:7:1
+   |
+LL | / impl<T: Grault> Grault for (T,)
+LL | | where
+LL | |     Self::A: Copy,
+LL | | {
+LL | |     type A = ();
+LL | |
+LL | | }
+   | |_^
+   |
+   = note: required because of the requirements on the impl of `Grault` for `(T,)`
+
+error[E0275]: overflow evaluating the requirement `<(T,) as Grault>::A == _`
+  --> $DIR/impl-wf-cycle-2.rs:11:5
+   |
+LL |     type A = ();
+   |     ^^^^^^^^^^^^
+   |
+   = note: required because of the requirements on the impl of `Grault` for `(T,)`
+
+error: aborting due to 2 previous errors
+
+For more information about this error, try `rustc --explain E0275`.