Auto merge of #122791 - compiler-errors:make-coinductive-always, r=lcnr

Make inductive cycles always ambiguous

 This makes inductive cycles always result in ambiguity rather than be treated like a stack-dependent error.

This has some  interactions with specialization, and so breaks a few UI tests that I don't agree should've ever worked in the first place, and also breaks a handful of crates in a way that I don't believe is a problem.

On the bright side, it puts us in a better spot when it comes to eventually enabling coinduction everywhere.

## Results

This was cratered in https://github.com/rust-lang/rust/pull/116494#issuecomment-2008657494, which boils down to two regressions:
* `lu_packets` - This code should have never compiled in the first place. More below.
* **ALL** other regressions are due to `commit_verify@0.11.0-beta.1` (edit: and `commit_verify@0.10.x`) - This actually seems to be fixed in version `0.11.0-beta.5`, which is the *most* up to date version, but it's still prerelease on crates.io so I don't think cargo ends up picking `beta.5` when building dependent crates.

### `lu_packets`

Firstly, this crate uses specialization, so I think it's automatically worth breaking. However, I've minimized [the regression](https://crater-reports.s3.amazonaws.com/pr-116494-3/try%23d614ed876e31a5f3ad1d0fbf848fcdab3a29d1d8/gh/lcdr.lu_packets/log.txt) to:

```rust
// Upstream crate
pub trait Serialize {}
impl Serialize for &() {}
impl<S> Serialize for &[S] where for<'a> &'a S: Serialize {}

// ----------------------------------------------------------------------- //

// Downstream crate
#![feature(specialization)]
#![allow(incomplete_features, unused)]

use upstream::Serialize;

trait Replica {
    fn serialize();
}

impl<T> Replica for T {
    default fn serialize() {}
}

impl<T> Replica for Option<T>
where
    for<'a> &'a T: Serialize,
{
    fn serialize() {}
}
```

Specifically this fails when computing the specialization graph for the `downstream` crate.

The code ends up cycling on `&[?0]: Serialize` when we equate `&?0 = &[?1]` during impl matching, which ends up needing to prove `&[?1]: Serialize`, which since cycles are treated like ambiguity, ends up in a **fatal overflow**. For some reason this requires two crates, squashing them into one crate doesn't work.

Side-note: This code is subtly order dependent. When minimizing, I ended up having the code start failing on `nightly` very easily after removing and reordering impls. This seems to me all the more reason to remove this behavior altogether.

## Side-note: Item Bounds (edit: this was fixed independently in #121123)

Due to the changes in #120584 where we now consider an alias's item bounds *and* all the item bounds of the alias's nested self type aliases, I've had to add e6b64c61941120f734657106ae2479d05b463197 which is a hack to make sure we're not eagerly normalizing bounds that have nothing to do with the predicate we're trying to solve, and which result in.

This is fixed in a more principled way in #121123.

---

r? lcnr for an initial review

3 files changed, 5 insertions, 42 deletions

diff --git a/compiler/rustc_trait_selection/src/infer.rs b/compiler/rustc_trait_selection/src/infer.rs
index f694dd00703..7056288e758 100644
--- a/compiler/rustc_trait_selection/src/infer.rs
+++ b/compiler/rustc_trait_selection/src/infer.rs
@@ -49,8 +49,7 @@ impl<'tcx> InferCtxt<'tcx> {
     /// - the parameter environment
     ///
     /// Invokes `evaluate_obligation`, so in the event that evaluating
-    /// `Ty: Trait` causes overflow, EvaluatedToErrStackDependent
-    /// (or EvaluatedToAmbigStackDependent) will be returned.
+    /// `Ty: Trait` causes overflow, EvaluatedToAmbigStackDependent will be returned.
     #[instrument(level = "debug", skip(self, params), ret)]
     fn type_implements_trait(
         &self,
diff --git a/compiler/rustc_trait_selection/src/traits/coherence.rs b/compiler/rustc_trait_selection/src/traits/coherence.rs
index 2712ba19451..6e768b23ef8 100644
--- a/compiler/rustc_trait_selection/src/traits/coherence.rs
+++ b/compiler/rustc_trait_selection/src/traits/coherence.rs
@@ -210,7 +210,7 @@ fn overlap<'tcx>(
         .intercrate(true)
         .with_next_trait_solver(tcx.next_trait_solver_in_coherence())
         .build();
-    let selcx = &mut SelectionContext::with_treat_inductive_cycle_as_ambig(&infcx);
+    let selcx = &mut SelectionContext::new(&infcx);
     if track_ambiguity_causes.is_yes() {
         selcx.enable_tracking_intercrate_ambiguity_causes();
     }
diff --git a/compiler/rustc_trait_selection/src/traits/select/mod.rs b/compiler/rustc_trait_selection/src/traits/select/mod.rs
index 084f7b1a8c2..3fbe8e39d1e 100644
--- a/compiler/rustc_trait_selection/src/traits/select/mod.rs
+++ b/compiler/rustc_trait_selection/src/traits/select/mod.rs
@@ -126,8 +126,6 @@ pub struct SelectionContext<'cx, 'tcx> {
     /// policy. In essence, canonicalized queries need their errors propagated
     /// rather than immediately reported because we do not have accurate spans.
     query_mode: TraitQueryMode,
-
-    treat_inductive_cycle: TreatInductiveCycleAs,
 }
 
 // A stack that walks back up the stack frame.
@@ -208,27 +206,6 @@ enum BuiltinImplConditions<'tcx> {
     Ambiguous,
 }
 
-#[derive(Copy, Clone)]
-pub enum TreatInductiveCycleAs {
-    /// This is the previous behavior, where `Recur` represents an inductive
-    /// cycle that is known not to hold. This is not forwards-compatible with
-    /// coinduction, and will be deprecated. This is the default behavior
-    /// of the old trait solver due to back-compat reasons.
-    Recur,
-    /// This is the behavior of the new trait solver, where inductive cycles
-    /// are treated as ambiguous and possibly holding.
-    Ambig,
-}
-
-impl From<TreatInductiveCycleAs> for EvaluationResult {
-    fn from(treat: TreatInductiveCycleAs) -> EvaluationResult {
-        match treat {
-            TreatInductiveCycleAs::Ambig => EvaluatedToAmbigStackDependent,
-            TreatInductiveCycleAs::Recur => EvaluatedToErrStackDependent,
-        }
-    }
-}
-
 impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
     pub fn new(infcx: &'cx InferCtxt<'tcx>) -> SelectionContext<'cx, 'tcx> {
         SelectionContext {
@@ -236,19 +213,6 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
             freshener: infcx.freshener(),
             intercrate_ambiguity_causes: None,
             query_mode: TraitQueryMode::Standard,
-            treat_inductive_cycle: TreatInductiveCycleAs::Recur,
-        }
-    }
-
-    pub fn with_treat_inductive_cycle_as_ambig(
-        infcx: &'cx InferCtxt<'tcx>,
-    ) -> SelectionContext<'cx, 'tcx> {
-        // Should be executed in a context where caching is disabled,
-        // otherwise the cache is poisoned with the temporary result.
-        assert!(infcx.intercrate);
-        SelectionContext {
-            treat_inductive_cycle: TreatInductiveCycleAs::Ambig,
-            ..SelectionContext::new(infcx)
         }
     }
 
@@ -756,7 +720,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                                 stack.update_reached_depth(stack_arg.1);
                                 return Ok(EvaluatedToOk);
                             } else {
-                                return Ok(self.treat_inductive_cycle.into());
+                                return Ok(EvaluatedToAmbigStackDependent);
                             }
                         }
                         return Ok(EvaluatedToOk);
@@ -875,7 +839,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                             }
                         }
                         ProjectAndUnifyResult::FailedNormalization => Ok(EvaluatedToAmbig),
-                        ProjectAndUnifyResult::Recursive => Ok(self.treat_inductive_cycle.into()),
+                        ProjectAndUnifyResult::Recursive => Ok(EvaluatedToAmbigStackDependent),
                         ProjectAndUnifyResult::MismatchedProjectionTypes(_) => Ok(EvaluatedToErr),
                     }
                 }
@@ -1180,7 +1144,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                 Some(EvaluatedToOk)
             } else {
                 debug!("evaluate_stack --> recursive, inductive");
-                Some(self.treat_inductive_cycle.into())
+                Some(EvaluatedToAmbigStackDependent)
             }
         } else {
             None