Auto merge of #117278 - lcnr:try-normalize-ty, r=compiler-errors

new solver normalization improvements

cool beans

At the core of this PR is a `try_normalize_ty` which stops for rigid aliases by using `commit_if_ok`.

Reworks alias-relate to fully normalize both the lhs and rhs and then equate the resulting rigid (or inference) types. This fixes https://github.com/rust-lang/trait-system-refactor-initiative/issues/68 by avoiding the exponential blowup. Also supersedes #116369 by only defining opaque types if the hidden type is rigid.

I removed the stability check in `EvalCtxt::evaluate_goal` due to https://github.com/rust-lang/trait-system-refactor-initiative/issues/75. While I personally have opinions on how to fix it, that still requires further t-types/`@nikomatsakis` buy-in, so I removed that for now. Once we've decided on our approach there, we can revert this commit.

r? `@compiler-errors`

13 files changed, 319 insertions, 291 deletions

diff --git a/compiler/rustc_middle/src/traits/solve/inspect.rs b/compiler/rustc_middle/src/traits/solve/inspect.rs
index a5916c4ab85..7883cd338be 100644
--- a/compiler/rustc_middle/src/traits/solve/inspect.rs
+++ b/compiler/rustc_middle/src/traits/solve/inspect.rs
@@ -122,6 +122,8 @@ pub enum ProbeStep<'tcx> {
     /// used whenever there are multiple candidates to prove the
     /// current goalby .
     NestedProbe(Probe<'tcx>),
+    CommitIfOkStart,
+    CommitIfOkSuccess,
 }
 
 /// What kind of probe we're in. In case the probe represents a candidate, or
@@ -142,6 +144,9 @@ pub enum ProbeKind<'tcx> {
     /// Used in the probe that wraps normalizing the non-self type for the unsize
     /// trait, which is also structurally matched on.
     UnsizeAssembly,
+    /// A call to `EvalCtxt::commit_if_ok` which failed, causing the work
+    /// to be discarded.
+    CommitIfOk,
     /// During upcasting from some source object to target object type, used to
     /// do a probe to find out what projection type(s) may be used to prove that
     /// the source type upholds all of the target type's object bounds.
diff --git a/compiler/rustc_middle/src/traits/solve/inspect/format.rs b/compiler/rustc_middle/src/traits/solve/inspect/format.rs
index 4b73d8e41a1..ab9e0283918 100644
--- a/compiler/rustc_middle/src/traits/solve/inspect/format.rs
+++ b/compiler/rustc_middle/src/traits/solve/inspect/format.rs
@@ -109,6 +109,9 @@ impl<'a, 'b> ProofTreeFormatter<'a, 'b> {
             ProbeKind::UpcastProjectionCompatibility => {
                 writeln!(self.f, "PROBING FOR PROJECTION COMPATIBILITY FOR UPCASTING:")
             }
+            ProbeKind::CommitIfOk => {
+                writeln!(self.f, "COMMIT_IF_OK:")
+            }
             ProbeKind::MiscCandidate { name, result } => {
                 writeln!(self.f, "CANDIDATE {name}: {result:?}")
             }
@@ -123,6 +126,8 @@ impl<'a, 'b> ProofTreeFormatter<'a, 'b> {
                     ProbeStep::AddGoal(goal) => writeln!(this.f, "ADDED GOAL: {goal:?}")?,
                     ProbeStep::EvaluateGoals(eval) => this.format_added_goals_evaluation(eval)?,
                     ProbeStep::NestedProbe(probe) => this.format_probe(probe)?,
+                    ProbeStep::CommitIfOkStart => writeln!(this.f, "COMMIT_IF_OK START")?,
+                    ProbeStep::CommitIfOkSuccess => writeln!(this.f, "COMMIT_IF_OK SUCCESS")?,
                 }
             }
             Ok(())
diff --git a/compiler/rustc_middle/src/ty/sty.rs b/compiler/rustc_middle/src/ty/sty.rs
index 2b1e57f5871..060952a9334 100644
--- a/compiler/rustc_middle/src/ty/sty.rs
+++ b/compiler/rustc_middle/src/ty/sty.rs
@@ -1245,6 +1245,28 @@ impl<'tcx> AliasTy<'tcx> {
         }
     }
 
+    /// Whether this alias type is an opaque.
+    pub fn is_opaque(self, tcx: TyCtxt<'tcx>) -> bool {
+        matches!(self.opt_kind(tcx), Some(ty::AliasKind::Opaque))
+    }
+
+    /// FIXME: rename `AliasTy` to `AliasTerm` and always handle
+    /// constants. This function can then be removed.
+    pub fn opt_kind(self, tcx: TyCtxt<'tcx>) -> Option<ty::AliasKind> {
+        match tcx.def_kind(self.def_id) {
+            DefKind::AssocTy
+                if let DefKind::Impl { of_trait: false } =
+                    tcx.def_kind(tcx.parent(self.def_id)) =>
+            {
+                Some(ty::Inherent)
+            }
+            DefKind::AssocTy => Some(ty::Projection),
+            DefKind::OpaqueTy => Some(ty::Opaque),
+            DefKind::TyAlias => Some(ty::Weak),
+            _ => None,
+        }
+    }
+
     pub fn to_ty(self, tcx: TyCtxt<'tcx>) -> Ty<'tcx> {
         Ty::new_alias(tcx, self.kind(tcx), self)
     }
diff --git a/compiler/rustc_trait_selection/src/solve/alias_relate.rs b/compiler/rustc_trait_selection/src/solve/alias_relate.rs
index f7031c5f493..739bbe929b3 100644
--- a/compiler/rustc_trait_selection/src/solve/alias_relate.rs
+++ b/compiler/rustc_trait_selection/src/solve/alias_relate.rs
@@ -11,18 +11,12 @@
 //! * bidirectional-normalizes-to: If `A` and `B` are both projections, and both
 //!   may apply, then we can compute the "intersection" of both normalizes-to by
 //!   performing them together. This is used specifically to resolve ambiguities.
-use super::{EvalCtxt, SolverMode};
+use super::EvalCtxt;
+use rustc_infer::infer::DefineOpaqueTypes;
 use rustc_infer::traits::query::NoSolution;
 use rustc_middle::traits::solve::{Certainty, Goal, QueryResult};
 use rustc_middle::ty;
 
-/// We may need to invert the alias relation direction if dealing an alias on the RHS.
-#[derive(Debug)]
-enum Invert {
-    No,
-    Yes,
-}
-
 impl<'tcx> EvalCtxt<'_, 'tcx> {
     #[instrument(level = "debug", skip(self), ret)]
     pub(super) fn compute_alias_relate_goal(
@@ -31,187 +25,130 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
     ) -> QueryResult<'tcx> {
         let tcx = self.tcx();
         let Goal { param_env, predicate: (lhs, rhs, direction) } = goal;
-        if lhs.is_infer() || rhs.is_infer() {
-            bug!(
-                "`AliasRelate` goal with an infer var on lhs or rhs which should have been instantiated"
-            );
-        }
-
-        match (lhs.to_alias_ty(tcx), rhs.to_alias_ty(tcx)) {
-            (None, None) => bug!("`AliasRelate` goal without an alias on either lhs or rhs"),
 
-            // RHS is not a projection, only way this is true is if LHS normalizes-to RHS
-            (Some(alias_lhs), None) => self.assemble_normalizes_to_candidate(
-                param_env,
-                alias_lhs,
-                rhs,
-                direction,
-                Invert::No,
-            ),
+        let Some(lhs) = self.try_normalize_term(param_env, lhs)? else {
+            return self.evaluate_added_goals_and_make_canonical_response(Certainty::OVERFLOW);
+        };
 
-            // LHS is not a projection, only way this is true is if RHS normalizes-to LHS
-            (None, Some(alias_rhs)) => self.assemble_normalizes_to_candidate(
-                param_env,
-                alias_rhs,
-                lhs,
-                direction,
-                Invert::Yes,
-            ),
+        let Some(rhs) = self.try_normalize_term(param_env, rhs)? else {
+            return self.evaluate_added_goals_and_make_canonical_response(Certainty::OVERFLOW);
+        };
 
-            (Some(alias_lhs), Some(alias_rhs)) => {
-                debug!("both sides are aliases");
+        let variance = match direction {
+            ty::AliasRelationDirection::Equate => ty::Variance::Invariant,
+            ty::AliasRelationDirection::Subtype => ty::Variance::Covariant,
+        };
 
-                let mut candidates = Vec::new();
-                // LHS normalizes-to RHS
-                candidates.extend(self.assemble_normalizes_to_candidate(
-                    param_env,
-                    alias_lhs,
-                    rhs,
-                    direction,
-                    Invert::No,
-                ));
-                // RHS normalizes-to RHS
-                candidates.extend(self.assemble_normalizes_to_candidate(
-                    param_env,
-                    alias_rhs,
-                    lhs,
-                    direction,
-                    Invert::Yes,
-                ));
-                // Relate via args
-                candidates.extend(
-                    self.assemble_subst_relate_candidate(
-                        param_env, alias_lhs, alias_rhs, direction,
-                    ),
-                );
-                debug!(?candidates);
+        match (lhs.to_alias_ty(tcx), rhs.to_alias_ty(tcx)) {
+            (None, None) => {
+                self.relate(param_env, lhs, variance, rhs)?;
+                self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
+            }
 
-                if let Some(merged) = self.try_merge_responses(&candidates) {
-                    Ok(merged)
+            (Some(alias), None) => {
+                if rhs.is_infer() {
+                    self.relate(param_env, lhs, variance, rhs)?;
+                    self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
+                } else if alias.is_opaque(tcx) {
+                    self.define_opaque(param_env, alias, rhs)
                 } else {
-                    // When relating two aliases and we have ambiguity, if both
-                    // aliases can be normalized to something, we prefer
-                    // "bidirectionally normalizing" both of them within the same
-                    // candidate.
-                    //
-                    // See <https://github.com/rust-lang/trait-system-refactor-initiative/issues/25>.
-                    //
-                    // As this is incomplete, we must not do so during coherence.
-                    match self.solver_mode() {
-                        SolverMode::Normal => {
-                            if let Ok(bidirectional_normalizes_to_response) = self
-                                .assemble_bidirectional_normalizes_to_candidate(
-                                    param_env, lhs, rhs, direction,
-                                )
-                            {
-                                Ok(bidirectional_normalizes_to_response)
-                            } else {
-                                self.flounder(&candidates)
-                            }
-                        }
-                        SolverMode::Coherence => self.flounder(&candidates),
-                    }
+                    Err(NoSolution)
                 }
             }
+            (None, Some(alias)) => {
+                if lhs.is_infer() {
+                    self.relate(param_env, lhs, variance, rhs)?;
+                    self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
+                } else if alias.is_opaque(tcx) {
+                    self.define_opaque(param_env, alias, lhs)
+                } else {
+                    Err(NoSolution)
+                }
+            }
+
+            (Some(alias_lhs), Some(alias_rhs)) => {
+                self.relate_rigid_alias_or_opaque(param_env, alias_lhs, variance, alias_rhs)
+            }
         }
     }
 
-    #[instrument(level = "debug", skip(self), ret)]
-    fn assemble_normalizes_to_candidate(
+    /// Normalize the `term` to equate it later. This does not define opaque types.
+    #[instrument(level = "debug", skip(self, param_env), ret)]
+    fn try_normalize_term(
         &mut self,
         param_env: ty::ParamEnv<'tcx>,
-        alias: ty::AliasTy<'tcx>,
-        other: ty::Term<'tcx>,
-        direction: ty::AliasRelationDirection,
-        invert: Invert,
-    ) -> QueryResult<'tcx> {
-        self.probe_misc_candidate("normalizes-to").enter(|ecx| {
-            ecx.normalizes_to_inner(param_env, alias, other, direction, invert)?;
-            ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
-        })
+        term: ty::Term<'tcx>,
+    ) -> Result<Option<ty::Term<'tcx>>, NoSolution> {
+        match term.unpack() {
+            ty::TermKind::Ty(ty) => {
+                // We do no define opaque types here but instead do so in `relate_rigid_alias_or_opaque`.
+                Ok(self
+                    .try_normalize_ty_recur(param_env, DefineOpaqueTypes::No, 0, ty)
+                    .map(Into::into))
+            }
+            ty::TermKind::Const(_) => {
+                if let Some(alias) = term.to_alias_ty(self.tcx()) {
+                    let term = self.next_term_infer_of_kind(term);
+                    self.add_goal(Goal::new(
+                        self.tcx(),
+                        param_env,
+                        ty::ProjectionPredicate { projection_ty: alias, term },
+                    ));
+                    self.try_evaluate_added_goals()?;
+                    Ok(Some(self.resolve_vars_if_possible(term)))
+                } else {
+                    Ok(Some(term))
+                }
+            }
+        }
     }
 
-    // Computes the normalizes-to branch, with side-effects. This must be performed
-    // in a probe in order to not taint the evaluation context.
-    fn normalizes_to_inner(
+    fn define_opaque(
         &mut self,
         param_env: ty::ParamEnv<'tcx>,
-        alias: ty::AliasTy<'tcx>,
-        other: ty::Term<'tcx>,
-        direction: ty::AliasRelationDirection,
-        invert: Invert,
-    ) -> Result<(), NoSolution> {
-        let other = match direction {
-            // This is purely an optimization. No need to instantiate a new
-            // infer var and equate the RHS to it.
-            ty::AliasRelationDirection::Equate => other,
-
-            // Instantiate an infer var and subtype our RHS to it, so that we
-            // properly represent a subtype relation between the LHS and RHS
-            // of the goal.
-            ty::AliasRelationDirection::Subtype => {
-                let fresh = self.next_term_infer_of_kind(other);
-                let (sub, sup) = match invert {
-                    Invert::No => (fresh, other),
-                    Invert::Yes => (other, fresh),
-                };
-                self.sub(param_env, sub, sup)?;
-                fresh
-            }
-        };
+        opaque: ty::AliasTy<'tcx>,
+        term: ty::Term<'tcx>,
+    ) -> QueryResult<'tcx> {
         self.add_goal(Goal::new(
             self.tcx(),
             param_env,
-            ty::ProjectionPredicate { projection_ty: alias, term: other },
+            ty::ProjectionPredicate { projection_ty: opaque, term },
         ));
-
-        Ok(())
+        self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
     }
 
-    fn assemble_subst_relate_candidate(
+    fn relate_rigid_alias_or_opaque(
         &mut self,
         param_env: ty::ParamEnv<'tcx>,
-        alias_lhs: ty::AliasTy<'tcx>,
-        alias_rhs: ty::AliasTy<'tcx>,
-        direction: ty::AliasRelationDirection,
+        lhs: ty::AliasTy<'tcx>,
+        variance: ty::Variance,
+        rhs: ty::AliasTy<'tcx>,
     ) -> QueryResult<'tcx> {
-        self.probe_misc_candidate("args relate").enter(|ecx| {
-            match direction {
-                ty::AliasRelationDirection::Equate => {
-                    ecx.eq(param_env, alias_lhs, alias_rhs)?;
-                }
-                ty::AliasRelationDirection::Subtype => {
-                    ecx.sub(param_env, alias_lhs, alias_rhs)?;
-                }
-            }
+        let tcx = self.tcx();
+        let mut candidates = vec![];
+        if lhs.is_opaque(tcx) {
+            candidates.extend(
+                self.probe_misc_candidate("define-lhs-opaque")
+                    .enter(|ecx| ecx.define_opaque(param_env, lhs, rhs.to_ty(tcx).into())),
+            );
+        }
 
-            ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
-        })
-    }
+        if rhs.is_opaque(tcx) {
+            candidates.extend(
+                self.probe_misc_candidate("define-rhs-opaque")
+                    .enter(|ecx| ecx.define_opaque(param_env, rhs, lhs.to_ty(tcx).into())),
+            );
+        }
 
-    fn assemble_bidirectional_normalizes_to_candidate(
-        &mut self,
-        param_env: ty::ParamEnv<'tcx>,
-        lhs: ty::Term<'tcx>,
-        rhs: ty::Term<'tcx>,
-        direction: ty::AliasRelationDirection,
-    ) -> QueryResult<'tcx> {
-        self.probe_misc_candidate("bidir normalizes-to").enter(|ecx| {
-            ecx.normalizes_to_inner(
-                param_env,
-                lhs.to_alias_ty(ecx.tcx()).unwrap(),
-                rhs,
-                direction,
-                Invert::No,
-            )?;
-            ecx.normalizes_to_inner(
-                param_env,
-                rhs.to_alias_ty(ecx.tcx()).unwrap(),
-                lhs,
-                direction,
-                Invert::Yes,
-            )?;
+        candidates.extend(self.probe_misc_candidate("args-relate").enter(|ecx| {
+            ecx.relate(param_env, lhs, variance, rhs)?;
             ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
-        })
+        }));
+
+        if let Some(result) = self.try_merge_responses(&candidates) {
+            Ok(result)
+        } else {
+            self.flounder(&candidates)
+        }
     }
 }
diff --git a/compiler/rustc_trait_selection/src/solve/assembly/mod.rs b/compiler/rustc_trait_selection/src/solve/assembly/mod.rs
index 27d2bdead83..13d7ebe1db0 100644
--- a/compiler/rustc_trait_selection/src/solve/assembly/mod.rs
+++ b/compiler/rustc_trait_selection/src/solve/assembly/mod.rs
@@ -352,7 +352,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
         let &ty::Alias(_, projection_ty) = goal.predicate.self_ty().kind() else { return };
 
         candidates.extend(self.probe(|_| ProbeKind::NormalizedSelfTyAssembly).enter(|ecx| {
-            if num_steps < ecx.local_overflow_limit() {
+            if tcx.recursion_limit().value_within_limit(num_steps) {
                 let normalized_ty = ecx.next_ty_infer();
                 let normalizes_to_goal = goal.with(
                     tcx,
@@ -864,23 +864,18 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
 
         let result = self.probe_misc_candidate("coherence unknowable").enter(|ecx| {
             let trait_ref = goal.predicate.trait_ref(tcx);
-
             #[derive(Debug)]
-            enum FailureKind {
-                Overflow,
-                NoSolution(NoSolution),
-            }
+            struct Overflow;
             let lazily_normalize_ty = |ty| match ecx.try_normalize_ty(goal.param_env, ty) {
-                Ok(Some(ty)) => Ok(ty),
-                Ok(None) => Err(FailureKind::Overflow),
-                Err(e) => Err(FailureKind::NoSolution(e)),
+                Some(ty) => Ok(ty),
+                None => Err(Overflow),
             };
 
             match coherence::trait_ref_is_knowable(tcx, trait_ref, lazily_normalize_ty) {
-                Err(FailureKind::Overflow) => {
+                Err(Overflow) => {
                     ecx.evaluate_added_goals_and_make_canonical_response(Certainty::OVERFLOW)
                 }
-                Err(FailureKind::NoSolution(NoSolution)) | Ok(Ok(())) => Err(NoSolution),
+                Ok(Ok(())) => Err(NoSolution),
                 Ok(Err(_)) => {
                     ecx.evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS)
                 }
diff --git a/compiler/rustc_trait_selection/src/solve/eval_ctxt/commit_if_ok.rs b/compiler/rustc_trait_selection/src/solve/eval_ctxt/commit_if_ok.rs
new file mode 100644
index 00000000000..c47152c601c
--- /dev/null
+++ b/compiler/rustc_trait_selection/src/solve/eval_ctxt/commit_if_ok.rs
@@ -0,0 +1,45 @@
+use super::EvalCtxt;
+use crate::solve::inspect;
+use rustc_middle::traits::query::NoSolution;
+
+impl<'a, 'tcx> EvalCtxt<'a, 'tcx> {
+    pub(in crate::solve) fn commit_if_ok<T>(
+        &mut self,
+        f: impl FnOnce(&mut EvalCtxt<'_, 'tcx>) -> Result<T, NoSolution>,
+    ) -> Result<T, NoSolution> {
+        let mut nested_ecx = EvalCtxt {
+            infcx: self.infcx,
+            variables: self.variables,
+            var_values: self.var_values,
+            predefined_opaques_in_body: self.predefined_opaques_in_body,
+            max_input_universe: self.max_input_universe,
+            search_graph: self.search_graph,
+            nested_goals: self.nested_goals.clone(),
+            tainted: self.tainted,
+            inspect: self.inspect.new_probe(),
+        };
+
+        let result = nested_ecx.infcx.commit_if_ok(|_| f(&mut nested_ecx));
+        if result.is_ok() {
+            let EvalCtxt {
+                infcx: _,
+                variables: _,
+                var_values: _,
+                predefined_opaques_in_body: _,
+                max_input_universe: _,
+                search_graph: _,
+                nested_goals,
+                tainted,
+                inspect,
+            } = nested_ecx;
+            self.nested_goals = nested_goals;
+            self.tainted = tainted;
+            self.inspect.integrate_snapshot(inspect);
+        } else {
+            nested_ecx.inspect.probe_kind(inspect::ProbeKind::CommitIfOk);
+            self.inspect.finish_probe(nested_ecx.inspect);
+        }
+
+        result
+    }
+}
diff --git a/compiler/rustc_trait_selection/src/solve/eval_ctxt/mod.rs b/compiler/rustc_trait_selection/src/solve/eval_ctxt/mod.rs
index 583eb9f96a9..23ce0a301ce 100644
--- a/compiler/rustc_trait_selection/src/solve/eval_ctxt/mod.rs
+++ b/compiler/rustc_trait_selection/src/solve/eval_ctxt/mod.rs
@@ -34,6 +34,7 @@ use super::{search_graph::SearchGraph, Goal};
 pub use select::InferCtxtSelectExt;
 
 mod canonical;
+mod commit_if_ok;
 mod probe;
 mod select;
 
@@ -332,7 +333,6 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> {
         let (orig_values, canonical_goal) = self.canonicalize_goal(goal);
         let mut goal_evaluation =
             self.inspect.new_goal_evaluation(goal, &orig_values, goal_evaluation_kind);
-        let encountered_overflow = self.search_graph.encountered_overflow();
         let canonical_response = EvalCtxt::evaluate_canonical_goal(
             self.tcx(),
             self.search_graph,
@@ -367,75 +367,19 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> {
             bug!("an unchanged goal shouldn't have any side-effects on instantiation");
         }
 
-        // Check that rerunning this query with its inference constraints applied
-        // doesn't result in new inference constraints and has the same result.
+        // FIXME: We previously had an assert here that checked that recomputing
+        // a goal after applying its constraints did not change its response.
         //
-        // If we have projection goals like `<T as Trait>::Assoc == u32` we recursively
-        // call `exists<U> <T as Trait>::Assoc == U` to enable better caching. This goal
-        // could constrain `U` to `u32` which would cause this check to result in a
-        // solver cycle.
-        if cfg!(debug_assertions)
-            && has_changed
-            && !matches!(
-                goal_evaluation_kind,
-                GoalEvaluationKind::Nested { is_normalizes_to_hack: IsNormalizesToHack::Yes }
-            )
-            && !self.search_graph.in_cycle()
-        {
-            // The nested evaluation has to happen with the original state
-            // of `encountered_overflow`.
-            let from_original_evaluation =
-                self.search_graph.reset_encountered_overflow(encountered_overflow);
-            self.check_evaluate_goal_stable_result(goal, canonical_goal, canonical_response);
-            // In case the evaluation was unstable, we manually make sure that this
-            // debug check does not influence the result of the parent goal.
-            self.search_graph.reset_encountered_overflow(from_original_evaluation);
-        }
+        // This assert was removed as it did not hold for goals constraining
+        // an inference variable to a recursive alias, e.g. in
+        // tests/ui/traits/new-solver/overflow/recursive-self-normalization.rs.
+        //
+        // Once we have decided on how to handle trait-system-refactor-initiative#75,
+        // we should re-add an assert here.
 
         Ok((has_changed, certainty, nested_goals))
     }
 
-    fn check_evaluate_goal_stable_result(
-        &mut self,
-        goal: Goal<'tcx, ty::Predicate<'tcx>>,
-        original_input: CanonicalInput<'tcx>,
-        original_result: CanonicalResponse<'tcx>,
-    ) {
-        let (_orig_values, canonical_goal) = self.canonicalize_goal(goal);
-        let result = EvalCtxt::evaluate_canonical_goal(
-            self.tcx(),
-            self.search_graph,
-            canonical_goal,
-            // FIXME(-Ztrait-solver=next): we do not track what happens in `evaluate_canonical_goal`
-            &mut ProofTreeBuilder::new_noop(),
-        );
-
-        macro_rules! fail {
-            ($msg:expr) => {{
-                let msg = $msg;
-                warn!(
-                    "unstable result: {msg}\n\
-                    original goal: {original_input:?},\n\
-                    original result: {original_result:?}\n\
-                    re-canonicalized goal: {canonical_goal:?}\n\
-                    second response: {result:?}"
-                );
-                return;
-            }};
-        }
-
-        let Ok(new_canonical_response) = result else { fail!("second response was error") };
-        // We only check for modulo regions as we convert all regions in
-        // the input to new existentials, even if they're expected to be
-        // `'static` or a placeholder region.
-        if !new_canonical_response.value.var_values.is_identity_modulo_regions() {
-            fail!("additional constraints from second response")
-        }
-        if original_result.value.certainty != new_canonical_response.value.certainty {
-            fail!("unstable certainty")
-        }
-    }
-
     fn compute_goal(&mut self, goal: Goal<'tcx, ty::Predicate<'tcx>>) -> QueryResult<'tcx> {
         let Goal { param_env, predicate } = goal;
         let kind = predicate.kind();
@@ -750,6 +694,26 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
             })
     }
 
+    #[instrument(level = "debug", skip(self, param_env), ret)]
+    pub(super) fn relate<T: ToTrace<'tcx>>(
+        &mut self,
+        param_env: ty::ParamEnv<'tcx>,
+        lhs: T,
+        variance: ty::Variance,
+        rhs: T,
+    ) -> Result<(), NoSolution> {
+        self.infcx
+            .at(&ObligationCause::dummy(), param_env)
+            .relate(DefineOpaqueTypes::No, lhs, variance, rhs)
+            .map(|InferOk { value: (), obligations }| {
+                self.add_goals(obligations.into_iter().map(|o| o.into()));
+            })
+            .map_err(|e| {
+                debug!(?e, "failed to relate");
+                NoSolution
+            })
+    }
+
     /// Equates two values returning the nested goals without adding them
     /// to the nested goals of the `EvalCtxt`.
     ///
diff --git a/compiler/rustc_trait_selection/src/solve/inspect/analyse.rs b/compiler/rustc_trait_selection/src/solve/inspect/analyse.rs
index 951080ac61a..5752d49ed2c 100644
--- a/compiler/rustc_trait_selection/src/solve/inspect/analyse.rs
+++ b/compiler/rustc_trait_selection/src/solve/inspect/analyse.rs
@@ -120,7 +120,6 @@ impl<'a, 'tcx> InspectGoal<'a, 'tcx> {
         for step in &probe.steps {
             match step {
                 &inspect::ProbeStep::AddGoal(goal) => nested_goals.push(goal),
-                inspect::ProbeStep::EvaluateGoals(_) => (),
                 inspect::ProbeStep::NestedProbe(ref probe) => {
                     // Nested probes have to prove goals added in their parent
                     // but do not leak them, so we truncate the added goals
@@ -129,13 +128,17 @@ impl<'a, 'tcx> InspectGoal<'a, 'tcx> {
                     self.candidates_recur(candidates, nested_goals, probe);
                     nested_goals.truncate(num_goals);
                 }
+                inspect::ProbeStep::EvaluateGoals(_)
+                | inspect::ProbeStep::CommitIfOkStart
+                | inspect::ProbeStep::CommitIfOkSuccess => (),
             }
         }
 
         match probe.kind {
             inspect::ProbeKind::NormalizedSelfTyAssembly
             | inspect::ProbeKind::UnsizeAssembly
-            | inspect::ProbeKind::UpcastProjectionCompatibility => (),
+            | inspect::ProbeKind::UpcastProjectionCompatibility
+            | inspect::ProbeKind::CommitIfOk => (),
             // We add a candidate for the root evaluation if there
             // is only one way to prove a given goal, e.g. for `WellFormed`.
             //
diff --git a/compiler/rustc_trait_selection/src/solve/inspect/build.rs b/compiler/rustc_trait_selection/src/solve/inspect/build.rs
index 088455b38cb..0d46df44c91 100644
--- a/compiler/rustc_trait_selection/src/solve/inspect/build.rs
+++ b/compiler/rustc_trait_selection/src/solve/inspect/build.rs
@@ -219,6 +219,8 @@ enum WipProbeStep<'tcx> {
     AddGoal(inspect::CanonicalState<'tcx, Goal<'tcx, ty::Predicate<'tcx>>>),
     EvaluateGoals(WipAddedGoalsEvaluation<'tcx>),
     NestedProbe(WipProbe<'tcx>),
+    CommitIfOkStart,
+    CommitIfOkSuccess,
 }
 
 impl<'tcx> WipProbeStep<'tcx> {
@@ -227,6 +229,8 @@ impl<'tcx> WipProbeStep<'tcx> {
             WipProbeStep::AddGoal(goal) => inspect::ProbeStep::AddGoal(goal),
             WipProbeStep::EvaluateGoals(eval) => inspect::ProbeStep::EvaluateGoals(eval.finalize()),
             WipProbeStep::NestedProbe(probe) => inspect::ProbeStep::NestedProbe(probe.finalize()),
+            WipProbeStep::CommitIfOkStart => inspect::ProbeStep::CommitIfOkStart,
+            WipProbeStep::CommitIfOkSuccess => inspect::ProbeStep::CommitIfOkSuccess,
         }
     }
 }
@@ -459,6 +463,29 @@ impl<'tcx> ProofTreeBuilder<'tcx> {
         }
     }
 
+    /// Used by `EvalCtxt::commit_if_ok` to flatten the work done inside
+    /// of the probe into the parent.
+    pub fn integrate_snapshot(&mut self, probe: ProofTreeBuilder<'tcx>) {
+        if let Some(this) = self.as_mut() {
+            match (this, *probe.state.unwrap()) {
+                (
+                    DebugSolver::Probe(WipProbe { steps, .. })
+                    | DebugSolver::GoalEvaluationStep(WipGoalEvaluationStep {
+                        evaluation: WipProbe { steps, .. },
+                        ..
+                    }),
+                    DebugSolver::Probe(probe),
+                ) => {
+                    steps.push(WipProbeStep::CommitIfOkStart);
+                    assert_eq!(probe.kind, None);
+                    steps.extend(probe.steps);
+                    steps.push(WipProbeStep::CommitIfOkSuccess);
+                }
+                _ => unreachable!(),
+            }
+        }
+    }
+
     pub fn new_evaluate_added_goals(&mut self) -> ProofTreeBuilder<'tcx> {
         self.nested(|| WipAddedGoalsEvaluation { evaluations: vec![], result: None })
     }
diff --git a/compiler/rustc_trait_selection/src/solve/mod.rs b/compiler/rustc_trait_selection/src/solve/mod.rs
index dba5369fa0f..65d061ab3f4 100644
--- a/compiler/rustc_trait_selection/src/solve/mod.rs
+++ b/compiler/rustc_trait_selection/src/solve/mod.rs
@@ -16,13 +16,14 @@
 //! about it on zulip.
 use rustc_hir::def_id::DefId;
 use rustc_infer::infer::canonical::{Canonical, CanonicalVarValues};
+use rustc_infer::infer::DefineOpaqueTypes;
 use rustc_infer::traits::query::NoSolution;
 use rustc_middle::infer::canonical::CanonicalVarInfos;
 use rustc_middle::traits::solve::{
     CanonicalResponse, Certainty, ExternalConstraintsData, Goal, IsNormalizesToHack, QueryResult,
     Response,
 };
-use rustc_middle::ty::{self, Ty, TyCtxt, UniverseIndex};
+use rustc_middle::ty::{self, OpaqueTypeKey, Ty, TyCtxt, UniverseIndex};
 use rustc_middle::ty::{
     CoercePredicate, RegionOutlivesPredicate, SubtypePredicate, TypeOutlivesPredicate,
 };
@@ -297,25 +298,62 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
     fn try_normalize_ty(
         &mut self,
         param_env: ty::ParamEnv<'tcx>,
-        mut ty: Ty<'tcx>,
-    ) -> Result<Option<Ty<'tcx>>, NoSolution> {
-        for _ in 0..self.local_overflow_limit() {
-            let ty::Alias(_, projection_ty) = *ty.kind() else {
-                return Ok(Some(ty));
-            };
-
-            let normalized_ty = self.next_ty_infer();
+        ty: Ty<'tcx>,
+    ) -> Option<Ty<'tcx>> {
+        self.try_normalize_ty_recur(param_env, DefineOpaqueTypes::Yes, 0, ty)
+    }
+
+    fn try_normalize_ty_recur(
+        &mut self,
+        param_env: ty::ParamEnv<'tcx>,
+        define_opaque_types: DefineOpaqueTypes,
+        depth: usize,
+        ty: Ty<'tcx>,
+    ) -> Option<Ty<'tcx>> {
+        if !self.tcx().recursion_limit().value_within_limit(depth) {
+            return None;
+        }
+
+        let ty::Alias(kind, projection_ty) = *ty.kind() else {
+            return Some(ty);
+        };
+
+        // We do no always define opaque types eagerly to allow non-defining uses in the defining scope.
+        if let (DefineOpaqueTypes::No, ty::AliasKind::Opaque) = (define_opaque_types, kind) {
+            if let Some(def_id) = projection_ty.def_id.as_local() {
+                if self
+                    .unify_existing_opaque_tys(
+                        param_env,
+                        OpaqueTypeKey { def_id, args: projection_ty.args },
+                        self.next_ty_infer(),
+                    )
+                    .is_empty()
+                {
+                    return Some(ty);
+                }
+            }
+        }
+
+        // FIXME(@lcnr): If the normalization of the alias adds an inference constraint which
+        // causes a previously added goal to fail, then we treat the alias as rigid.
+        //
+        // These feels like a potential issue, I should look into writing some tests here
+        // and then probably changing `commit_if_ok` to not inherit the parent goals.
+        match self.commit_if_ok(|this| {
+            let normalized_ty = this.next_ty_infer();
             let normalizes_to_goal = Goal::new(
-                self.tcx(),
+                this.tcx(),
                 param_env,
                 ty::ProjectionPredicate { projection_ty, term: normalized_ty.into() },
             );
-            self.add_goal(normalizes_to_goal);
-            self.try_evaluate_added_goals()?;
-            ty = self.resolve_vars_if_possible(normalized_ty);
+            this.add_goal(normalizes_to_goal);
+            this.try_evaluate_added_goals()?;
+            let ty = this.resolve_vars_if_possible(normalized_ty);
+            Ok(this.try_normalize_ty_recur(param_env, define_opaque_types, depth + 1, ty))
+        }) {
+            Ok(ty) => ty,
+            Err(NoSolution) => Some(ty),
         }
-
-        Ok(None)
     }
 }
 
diff --git a/compiler/rustc_trait_selection/src/solve/project_goals/opaques.rs b/compiler/rustc_trait_selection/src/solve/project_goals/opaques.rs
index ebd129f32b9..1fde129c3a0 100644
--- a/compiler/rustc_trait_selection/src/solve/project_goals/opaques.rs
+++ b/compiler/rustc_trait_selection/src/solve/project_goals/opaques.rs
@@ -44,6 +44,10 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
                 // Prefer opaques registered already.
                 let opaque_type_key =
                     ty::OpaqueTypeKey { def_id: opaque_ty_def_id, args: opaque_ty.args };
+                // FIXME: This also unifies the previous hidden type with the expected.
+                //
+                // If that fails, we insert `expected` as a new hidden type instead of
+                // eagerly emitting an error.
                 let matches =
                     self.unify_existing_opaque_tys(goal.param_env, opaque_type_key, expected);
                 if !matches.is_empty() {
@@ -53,6 +57,23 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
                         return self.flounder(&matches);
                     }
                 }
+
+                let expected = match self.try_normalize_ty(goal.param_env, expected) {
+                    Some(ty) => {
+                        if ty.is_ty_var() {
+                            return self.evaluate_added_goals_and_make_canonical_response(
+                                Certainty::AMBIGUOUS,
+                            );
+                        } else {
+                            ty
+                        }
+                    }
+                    None => {
+                        return self
+                            .evaluate_added_goals_and_make_canonical_response(Certainty::OVERFLOW);
+                    }
+                };
+
                 // Otherwise, define a new opaque type
                 self.insert_hidden_type(opaque_type_key, goal.param_env, expected)?;
                 self.add_item_bounds_for_hidden_type(
diff --git a/compiler/rustc_trait_selection/src/solve/search_graph.rs b/compiler/rustc_trait_selection/src/solve/search_graph.rs
index 7ffa1d7d319..68f81a05536 100644
--- a/compiler/rustc_trait_selection/src/solve/search_graph.rs
+++ b/compiler/rustc_trait_selection/src/solve/search_graph.rs
@@ -110,39 +110,6 @@ impl<'tcx> SearchGraph<'tcx> {
         self.stack.is_empty()
     }
 
-    /// Whether we're currently in a cycle. This should only be used
-    /// for debug assertions.
-    pub(super) fn in_cycle(&self) -> bool {
-        if let Some(stack_depth) = self.stack.last_index() {
-            // Either the current goal on the stack is the root of a cycle
-            // or it depends on a goal with a lower depth.
-            self.stack[stack_depth].has_been_used
-                || self.stack[stack_depth].cycle_root_depth != stack_depth
-        } else {
-            false
-        }
-    }
-
-    /// Fetches whether the current goal encountered overflow.
-    ///
-    /// This should only be used for the check in `evaluate_goal`.
-    pub(super) fn encountered_overflow(&self) -> bool {
-        if let Some(last) = self.stack.raw.last() { last.encountered_overflow } else { false }
-    }
-
-    /// Resets `encountered_overflow` of the current goal.
-    ///
-    /// This should only be used for the check in `evaluate_goal`.
-    pub(super) fn reset_encountered_overflow(&mut self, encountered_overflow: bool) -> bool {
-        if let Some(last) = self.stack.raw.last_mut() {
-            let prev = last.encountered_overflow;
-            last.encountered_overflow = encountered_overflow;
-            prev
-        } else {
-            false
-        }
-    }
-
     /// Returns the remaining depth allowed for nested goals.
     ///
     /// This is generally simply one less than the current depth.
diff --git a/compiler/rustc_trait_selection/src/solve/trait_goals.rs b/compiler/rustc_trait_selection/src/solve/trait_goals.rs
index 84baec4ff4c..0f30b49314b 100644
--- a/compiler/rustc_trait_selection/src/solve/trait_goals.rs
+++ b/compiler/rustc_trait_selection/src/solve/trait_goals.rs
@@ -469,7 +469,7 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> {
             let a_ty = goal.predicate.self_ty();
             // We need to normalize the b_ty since it's destructured as a `dyn Trait`.
             let Some(b_ty) =
-                ecx.try_normalize_ty(goal.param_env, goal.predicate.trait_ref.args.type_at(1))?
+                ecx.try_normalize_ty(goal.param_env, goal.predicate.trait_ref.args.type_at(1))
             else {
                 return ecx.evaluate_added_goals_and_make_canonical_response(Certainty::OVERFLOW);
             };
@@ -536,9 +536,8 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> {
             let b_ty = match ecx
                 .try_normalize_ty(goal.param_env, goal.predicate.trait_ref.args.type_at(1))
             {
-                Ok(Some(b_ty)) => b_ty,
-                Ok(None) => return vec![misc_candidate(ecx, Certainty::OVERFLOW)],
-                Err(_) => return vec![],
+                Some(b_ty) => b_ty,
+                None => return vec![misc_candidate(ecx, Certainty::OVERFLOW)],
             };
 
             let goal = goal.with(ecx.tcx(), (a_ty, b_ty));