Merging upstream version 1.70.0+dfsg1.

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

12 files changed, 1580 insertions, 944 deletions

diff --git a/compiler/rustc_trait_selection/src/solve/assembly.rs b/compiler/rustc_trait_selection/src/solve/assembly/mod.rs
index dec9f8016..10d817f75 100644
--- a/compiler/rustc_trait_selection/src/solve/assembly.rs
+++ b/compiler/rustc_trait_selection/src/solve/assembly/mod.rs
@@ -1,16 +1,21 @@
 //! Code shared by trait and projection goals for candidate assembly.
 
-#[cfg(doc)]
-use super::trait_goals::structural_traits::*;
-use super::{CanonicalResponse, Certainty, EvalCtxt, Goal, MaybeCause, QueryResult};
-use itertools::Itertools;
+use super::search_graph::OverflowHandler;
+use super::{EvalCtxt, SolverMode};
+use crate::solve::CanonicalResponseExt;
+use crate::traits::coherence;
+use rustc_data_structures::fx::FxIndexSet;
 use rustc_hir::def_id::DefId;
 use rustc_infer::traits::query::NoSolution;
-use rustc_infer::traits::util::elaborate_predicates;
+use rustc_infer::traits::util::elaborate;
+use rustc_middle::traits::solve::{CanonicalResponse, Certainty, Goal, MaybeCause, QueryResult};
+use rustc_middle::ty::fast_reject::TreatProjections;
 use rustc_middle::ty::TypeFoldable;
 use rustc_middle::ty::{self, Ty, TyCtxt};
 use std::fmt::Debug;
 
+pub(super) mod structural_traits;
+
 /// A candidate is a possible way to prove a goal.
 ///
 /// It consists of both the `source`, which describes how that goal would be proven,
@@ -85,6 +90,8 @@ pub(super) enum CandidateSource {
 pub(super) trait GoalKind<'tcx>: TypeFoldable<TyCtxt<'tcx>> + Copy + Eq {
     fn self_ty(self) -> Ty<'tcx>;
 
+    fn trait_ref(self, tcx: TyCtxt<'tcx>) -> ty::TraitRef<'tcx>;
+
     fn with_self_ty(self, tcx: TyCtxt<'tcx>, self_ty: Ty<'tcx>) -> Self;
 
     fn trait_def_id(self, tcx: TyCtxt<'tcx>) -> DefId;
@@ -148,6 +155,12 @@ pub(super) trait GoalKind<'tcx>: TypeFoldable<TyCtxt<'tcx>> + Copy + Eq {
         goal: Goal<'tcx, Self>,
     ) -> QueryResult<'tcx>;
 
+    // A type is a `FnPtr` if it is of `FnPtr` type.
+    fn consider_builtin_fn_ptr_trait_candidate(
+        ecx: &mut EvalCtxt<'_, 'tcx>,
+        goal: Goal<'tcx, Self>,
+    ) -> QueryResult<'tcx>;
+
     // A callable type (a closure, fn def, or fn ptr) is known to implement the `Fn<A>`
     // family of traits where `A` is given by the signature of the type.
     fn consider_builtin_fn_trait_candidates(
@@ -207,6 +220,16 @@ pub(super) trait GoalKind<'tcx>: TypeFoldable<TyCtxt<'tcx>> + Copy + Eq {
         ecx: &mut EvalCtxt<'_, 'tcx>,
         goal: Goal<'tcx, Self>,
     ) -> QueryResult<'tcx>;
+
+    fn consider_builtin_destruct_candidate(
+        ecx: &mut EvalCtxt<'_, 'tcx>,
+        goal: Goal<'tcx, Self>,
+    ) -> QueryResult<'tcx>;
+
+    fn consider_builtin_transmute_candidate(
+        ecx: &mut EvalCtxt<'_, 'tcx>,
+        goal: Goal<'tcx, Self>,
+    ) -> QueryResult<'tcx>;
 }
 
 impl<'tcx> EvalCtxt<'_, 'tcx> {
@@ -222,7 +245,9 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
         if goal.predicate.self_ty().is_ty_var() {
             return vec![Candidate {
                 source: CandidateSource::BuiltinImpl,
-                result: self.make_canonical_response(Certainty::AMBIGUOUS).unwrap(),
+                result: self
+                    .evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS)
+                    .unwrap(),
             }];
         }
 
@@ -240,14 +265,17 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
 
         self.assemble_object_bound_candidates(goal, &mut candidates);
 
+        self.assemble_coherence_unknowable_candidates(goal, &mut candidates);
+
         candidates
     }
 
     /// If the self type of a goal is a projection, computing the relevant candidates is difficult.
     ///
     /// To deal with this, we first try to normalize the self type and add the candidates for the normalized
-    /// self type to the list of candidates in case that succeeds. Note that we can't just eagerly return in
-    /// this case as projections as self types add `
+    /// self type to the list of candidates in case that succeeds. We also have to consider candidates with the
+    /// projection as a self type as well
+    #[instrument(level = "debug", skip_all)]
     fn assemble_candidates_after_normalizing_self_ty<G: GoalKind<'tcx>>(
         &mut self,
         goal: Goal<'tcx, G>,
@@ -258,48 +286,52 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
         let &ty::Alias(ty::Projection, projection_ty) = goal.predicate.self_ty().kind() else {
             return
         };
-        self.probe(|this| {
-            let normalized_ty = this.next_ty_infer();
-            let normalizes_to_goal = goal.with(
-                tcx,
-                ty::Binder::dummy(ty::ProjectionPredicate {
-                    projection_ty,
-                    term: normalized_ty.into(),
-                }),
-            );
-            let normalization_certainty = match this.evaluate_goal(normalizes_to_goal) {
-                Ok((_, certainty)) => certainty,
-                Err(NoSolution) => return,
-            };
-            let normalized_ty = this.resolve_vars_if_possible(normalized_ty);
-
-            // NOTE: Alternatively we could call `evaluate_goal` here and only have a `Normalized` candidate.
-            // This doesn't work as long as we use `CandidateSource` in winnowing.
-            let goal = goal.with(tcx, goal.predicate.with_self_ty(tcx, normalized_ty));
-            let normalized_candidates = this.assemble_and_evaluate_candidates(goal);
-            for mut normalized_candidate in normalized_candidates {
-                normalized_candidate.result =
-                    normalized_candidate.result.unchecked_map(|mut response| {
-                        // FIXME: This currently hides overflow in the normalization step of the self type
-                        // which is probably wrong. Maybe `unify_and` should actually keep overflow as
-                        // we treat it as non-fatal anyways.
-                        response.certainty = response.certainty.unify_and(normalization_certainty);
-                        response
-                    });
-                candidates.push(normalized_candidate);
-            }
-        })
+
+        let normalized_self_candidates: Result<_, NoSolution> = self.probe(|ecx| {
+            ecx.with_incremented_depth(
+                |ecx| {
+                    let result = ecx.evaluate_added_goals_and_make_canonical_response(
+                        Certainty::Maybe(MaybeCause::Overflow),
+                    )?;
+                    Ok(vec![Candidate { source: CandidateSource::BuiltinImpl, result }])
+                },
+                |ecx| {
+                    let normalized_ty = ecx.next_ty_infer();
+                    let normalizes_to_goal = goal.with(
+                        tcx,
+                        ty::Binder::dummy(ty::ProjectionPredicate {
+                            projection_ty,
+                            term: normalized_ty.into(),
+                        }),
+                    );
+                    ecx.add_goal(normalizes_to_goal);
+                    let _ = ecx.try_evaluate_added_goals()?;
+                    let normalized_ty = ecx.resolve_vars_if_possible(normalized_ty);
+                    // NOTE: Alternatively we could call `evaluate_goal` here and only
+                    // have a `Normalized` candidate. This doesn't work as long as we
+                    // use `CandidateSource` in winnowing.
+                    let goal = goal.with(tcx, goal.predicate.with_self_ty(tcx, normalized_ty));
+                    Ok(ecx.assemble_and_evaluate_candidates(goal))
+                },
+            )
+        });
+
+        if let Ok(normalized_self_candidates) = normalized_self_candidates {
+            candidates.extend(normalized_self_candidates);
+        }
     }
 
+    #[instrument(level = "debug", skip_all)]
     fn assemble_impl_candidates<G: GoalKind<'tcx>>(
         &mut self,
         goal: Goal<'tcx, G>,
         candidates: &mut Vec<Candidate<'tcx>>,
     ) {
         let tcx = self.tcx();
-        tcx.for_each_relevant_impl(
+        tcx.for_each_relevant_impl_treating_projections(
             goal.predicate.trait_def_id(tcx),
             goal.predicate.self_ty(),
+            TreatProjections::NextSolverLookup,
             |impl_def_id| match G::consider_impl_candidate(self, goal, impl_def_id) {
                 Ok(result) => candidates
                     .push(Candidate { source: CandidateSource::Impl(impl_def_id), result }),
@@ -308,6 +340,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
         );
     }
 
+    #[instrument(level = "debug", skip_all)]
     fn assemble_builtin_impl_candidates<G: GoalKind<'tcx>>(
         &mut self,
         goal: Goal<'tcx, G>,
@@ -315,6 +348,14 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
     ) {
         let lang_items = self.tcx().lang_items();
         let trait_def_id = goal.predicate.trait_def_id(self.tcx());
+
+        // N.B. When assembling built-in candidates for lang items that are also
+        // `auto` traits, then the auto trait candidate that is assembled in
+        // `consider_auto_trait_candidate` MUST be disqualified to remain sound.
+        //
+        // Instead of adding the logic here, it's a better idea to add it in
+        // `EvalCtxt::disqualify_auto_trait_candidate_due_to_possible_impl` in
+        // `solve::trait_goals` instead.
         let result = if self.tcx().trait_is_auto(trait_def_id) {
             G::consider_auto_trait_candidate(self, goal)
         } else if self.tcx().trait_is_alias(trait_def_id) {
@@ -327,6 +368,8 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
             G::consider_builtin_copy_clone_candidate(self, goal)
         } else if lang_items.pointer_like() == Some(trait_def_id) {
             G::consider_builtin_pointer_like_candidate(self, goal)
+        } else if lang_items.fn_ptr_trait() == Some(trait_def_id) {
+            G::consider_builtin_fn_ptr_trait_candidate(self, goal)
         } else if let Some(kind) = self.tcx().fn_trait_kind_from_def_id(trait_def_id) {
             G::consider_builtin_fn_trait_candidates(self, goal, kind)
         } else if lang_items.tuple_trait() == Some(trait_def_id) {
@@ -341,6 +384,10 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
             G::consider_builtin_unsize_candidate(self, goal)
         } else if lang_items.discriminant_kind_trait() == Some(trait_def_id) {
             G::consider_builtin_discriminant_kind_candidate(self, goal)
+        } else if lang_items.destruct_trait() == Some(trait_def_id) {
+            G::consider_builtin_destruct_candidate(self, goal)
+        } else if lang_items.transmute_trait() == Some(trait_def_id) {
+            G::consider_builtin_transmute_candidate(self, goal)
         } else {
             Err(NoSolution)
         };
@@ -361,6 +408,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
         }
     }
 
+    #[instrument(level = "debug", skip_all)]
     fn assemble_param_env_candidates<G: GoalKind<'tcx>>(
         &mut self,
         goal: Goal<'tcx, G>,
@@ -376,6 +424,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
         }
     }
 
+    #[instrument(level = "debug", skip_all)]
     fn assemble_alias_bound_candidates<G: GoalKind<'tcx>>(
         &mut self,
         goal: Goal<'tcx, G>,
@@ -423,6 +472,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
         }
     }
 
+    #[instrument(level = "debug", skip_all)]
     fn assemble_object_bound_candidates<G: GoalKind<'tcx>>(
         &mut self,
         goal: Goal<'tcx, G>,
@@ -461,10 +511,25 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
         };
 
         let tcx = self.tcx();
-        for assumption in
-            elaborate_predicates(tcx, bounds.iter().map(|bound| bound.with_self_ty(tcx, self_ty)))
+        let own_bounds: FxIndexSet<_> =
+            bounds.iter().map(|bound| bound.with_self_ty(tcx, self_ty)).collect();
+        for assumption in elaborate(tcx, own_bounds.iter().copied())
+            // we only care about bounds that match the `Self` type
+            .filter_only_self()
         {
-            match G::consider_object_bound_candidate(self, goal, assumption.predicate) {
+            // FIXME: Predicates are fully elaborated in the object type's existential bounds
+            // list. We want to only consider these pre-elaborated projections, and not other
+            // projection predicates that we reach by elaborating the principal trait ref,
+            // since that'll cause ambiguity.
+            //
+            // We can remove this when we have implemented intersections in responses.
+            if assumption.to_opt_poly_projection_pred().is_some()
+                && !own_bounds.contains(&assumption)
+            {
+                continue;
+            }
+
+            match G::consider_object_bound_candidate(self, goal, assumption) {
                 Ok(result) => {
                     candidates.push(Candidate { source: CandidateSource::BuiltinImpl, result })
                 }
@@ -473,78 +538,68 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
         }
     }
 
-    #[instrument(level = "debug", skip(self), ret)]
-    pub(super) fn merge_candidates_and_discard_reservation_impls(
+    #[instrument(level = "debug", skip_all)]
+    fn assemble_coherence_unknowable_candidates<G: GoalKind<'tcx>>(
         &mut self,
-        mut candidates: Vec<Candidate<'tcx>>,
-    ) -> QueryResult<'tcx> {
-        match candidates.len() {
-            0 => return Err(NoSolution),
-            1 => return Ok(self.discard_reservation_impl(candidates.pop().unwrap()).result),
-            _ => {}
-        }
-
-        if candidates.len() > 1 {
-            let mut i = 0;
-            'outer: while i < candidates.len() {
-                for j in (0..candidates.len()).filter(|&j| i != j) {
-                    if self.trait_candidate_should_be_dropped_in_favor_of(
-                        &candidates[i],
-                        &candidates[j],
-                    ) {
-                        debug!(candidate = ?candidates[i], "Dropping candidate #{}/{}", i, candidates.len());
-                        candidates.swap_remove(i);
-                        continue 'outer;
-                    }
+        goal: Goal<'tcx, G>,
+        candidates: &mut Vec<Candidate<'tcx>>,
+    ) {
+        match self.solver_mode() {
+            SolverMode::Normal => return,
+            SolverMode::Coherence => {
+                let trait_ref = goal.predicate.trait_ref(self.tcx());
+                match coherence::trait_ref_is_knowable(self.tcx(), trait_ref) {
+                    Ok(()) => {}
+                    Err(_) => match self
+                        .evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS)
+                    {
+                        Ok(result) => candidates
+                            .push(Candidate { source: CandidateSource::BuiltinImpl, result }),
+                        // FIXME: This will be reachable at some point if we're in
+                        // `assemble_candidates_after_normalizing_self_ty` and we get a
+                        // universe error. We'll deal with it at this point.
+                        Err(NoSolution) => bug!("coherence candidate resulted in NoSolution"),
+                    },
                 }
-
-                debug!(candidate = ?candidates[i], "Retaining candidate #{}/{}", i, candidates.len());
-                i += 1;
-            }
-
-            // If there are *STILL* multiple candidates that have *different* response
-            // results, give up and report ambiguity.
-            if candidates.len() > 1 && !candidates.iter().map(|cand| cand.result).all_equal() {
-                let certainty = if candidates.iter().all(|x| {
-                    matches!(x.result.value.certainty, Certainty::Maybe(MaybeCause::Overflow))
-                }) {
-                    Certainty::Maybe(MaybeCause::Overflow)
-                } else {
-                    Certainty::AMBIGUOUS
-                };
-                return self.make_canonical_response(certainty);
             }
         }
-
-        // FIXME: What if there are >1 candidates left with the same response, and one is a reservation impl?
-        Ok(self.discard_reservation_impl(candidates.pop().unwrap()).result)
     }
 
-    fn trait_candidate_should_be_dropped_in_favor_of(
-        &self,
-        candidate: &Candidate<'tcx>,
-        other: &Candidate<'tcx>,
-    ) -> bool {
-        // FIXME: implement this
-        match (candidate.source, other.source) {
-            (CandidateSource::Impl(_), _)
-            | (CandidateSource::ParamEnv(_), _)
-            | (CandidateSource::AliasBound, _)
-            | (CandidateSource::BuiltinImpl, _) => false,
+    /// If there are multiple ways to prove a trait or projection goal, we have
+    /// to somehow try to merge the candidates into one. If that fails, we return
+    /// ambiguity.
+    #[instrument(level = "debug", skip(self), ret)]
+    pub(super) fn merge_candidates(
+        &mut self,
+        mut candidates: Vec<Candidate<'tcx>>,
+    ) -> QueryResult<'tcx> {
+        // First try merging all candidates. This is complete and fully sound.
+        let responses = candidates.iter().map(|c| c.result).collect::<Vec<_>>();
+        if let Some(result) = self.try_merge_responses(&responses) {
+            return Ok(result);
         }
-    }
 
-    fn discard_reservation_impl(&self, mut candidate: Candidate<'tcx>) -> Candidate<'tcx> {
-        if let CandidateSource::Impl(def_id) = candidate.source {
-            if let ty::ImplPolarity::Reservation = self.tcx().impl_polarity(def_id) {
-                debug!("Selected reservation impl");
-                // We assemble all candidates inside of a probe so by
-                // making a new canonical response here our result will
-                // have no constraints.
-                candidate.result = self.make_canonical_response(Certainty::AMBIGUOUS).unwrap();
+        // We then check whether we should prioritize `ParamEnv` candidates.
+        //
+        // Doing so is incomplete and would therefore be unsound during coherence.
+        match self.solver_mode() {
+            SolverMode::Coherence => (),
+            // Prioritize `ParamEnv` candidates only if they do not guide inference.
+            //
+            // This is still incomplete as we may add incorrect region bounds.
+            SolverMode::Normal => {
+                let param_env_responses = candidates
+                    .iter()
+                    .filter(|c| matches!(c.source, CandidateSource::ParamEnv(_)))
+                    .map(|c| c.result)
+                    .collect::<Vec<_>>();
+                if let Some(result) = self.try_merge_responses(&param_env_responses) {
+                    if result.has_only_region_constraints() {
+                        return Ok(result);
+                    }
+                }
             }
         }
-
-        candidate
+        self.flounder(&responses)
     }
 }
diff --git a/compiler/rustc_trait_selection/src/solve/trait_goals/structural_traits.rs b/compiler/rustc_trait_selection/src/solve/assembly/structural_traits.rs
index d7d93377c..1a566e87d 100644
--- a/compiler/rustc_trait_selection/src/solve/trait_goals/structural_traits.rs
+++ b/compiler/rustc_trait_selection/src/solve/assembly/structural_traits.rs
@@ -1,7 +1,9 @@
 use rustc_data_structures::fx::FxHashMap;
 use rustc_hir::{def_id::DefId, Movability, Mutability};
 use rustc_infer::traits::query::NoSolution;
-use rustc_middle::ty::{self, Ty, TyCtxt, TypeFoldable, TypeFolder, TypeSuperFoldable};
+use rustc_middle::ty::{
+    self, Ty, TyCtxt, TypeFoldable, TypeFolder, TypeSuperFoldable, TypeVisitableExt,
+};
 
 use crate::solve::EvalCtxt;
 
@@ -9,7 +11,7 @@ use crate::solve::EvalCtxt;
 //
 // For types with an "existential" binder, i.e. generator witnesses, we also
 // instantiate the binder with placeholders eagerly.
-pub(super) fn instantiate_constituent_tys_for_auto_trait<'tcx>(
+pub(in crate::solve) fn instantiate_constituent_tys_for_auto_trait<'tcx>(
     ecx: &EvalCtxt<'_, 'tcx>,
     ty: Ty<'tcx>,
 ) -> Result<Vec<Ty<'tcx>>, NoSolution> {
@@ -22,21 +24,19 @@ pub(super) fn instantiate_constituent_tys_for_auto_trait<'tcx>(
         | ty::FnDef(..)
         | ty::FnPtr(_)
         | ty::Error(_)
-        | ty::Infer(ty::IntVar(_) | ty::FloatVar(_))
         | ty::Never
         | ty::Char => Ok(vec![]),
 
-        // Treat this like `struct str([u8]);`
+        // Treat `str` like it's defined as `struct str([u8]);`
         ty::Str => Ok(vec![tcx.mk_slice(tcx.types.u8)]),
 
         ty::Dynamic(..)
         | ty::Param(..)
         | ty::Foreign(..)
         | ty::Alias(ty::Projection, ..)
-        | ty::Placeholder(..) => Err(NoSolution),
-
-        ty::Bound(..)
-        | ty::Infer(ty::TyVar(_) | ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_)) => {
+        | ty::Placeholder(..)
+        | ty::Bound(..)
+        | ty::Infer(_) => {
             bug!("unexpected type `{ty}`")
         }
 
@@ -60,7 +60,16 @@ pub(super) fn instantiate_constituent_tys_for_auto_trait<'tcx>(
 
         ty::GeneratorWitness(types) => Ok(ecx.instantiate_binder_with_placeholders(types).to_vec()),
 
-        ty::GeneratorWitnessMIR(..) => todo!(),
+        ty::GeneratorWitnessMIR(def_id, substs) => Ok(ecx
+            .tcx()
+            .generator_hidden_types(def_id)
+            .map(|bty| {
+                ecx.instantiate_binder_with_placeholders(replace_erased_lifetimes_with_bound_vars(
+                    tcx,
+                    bty.subst(tcx, substs),
+                ))
+            })
+            .collect()),
 
         // For `PhantomData<T>`, we pass `T`.
         ty::Adt(def, substs) if def.is_phantom_data() => Ok(vec![substs.type_at(0)]),
@@ -76,7 +85,28 @@ pub(super) fn instantiate_constituent_tys_for_auto_trait<'tcx>(
     }
 }
 
-pub(super) fn instantiate_constituent_tys_for_sized_trait<'tcx>(
+pub(in crate::solve) fn replace_erased_lifetimes_with_bound_vars<'tcx>(
+    tcx: TyCtxt<'tcx>,
+    ty: Ty<'tcx>,
+) -> ty::Binder<'tcx, Ty<'tcx>> {
+    debug_assert!(!ty.has_late_bound_regions());
+    let mut counter = 0;
+    let ty = tcx.fold_regions(ty, |mut r, current_depth| {
+        if let ty::ReErased = r.kind() {
+            let br =
+                ty::BoundRegion { var: ty::BoundVar::from_u32(counter), kind: ty::BrAnon(None) };
+            counter += 1;
+            r = tcx.mk_re_late_bound(current_depth, br);
+        }
+        r
+    });
+    let bound_vars = tcx.mk_bound_variable_kinds_from_iter(
+        (0..counter).map(|_| ty::BoundVariableKind::Region(ty::BrAnon(None))),
+    );
+    ty::Binder::bind_with_vars(ty, bound_vars)
+}
+
+pub(in crate::solve) fn instantiate_constituent_tys_for_sized_trait<'tcx>(
     ecx: &EvalCtxt<'_, 'tcx>,
     ty: Ty<'tcx>,
 ) -> Result<Vec<Ty<'tcx>>, NoSolution> {
@@ -126,7 +156,7 @@ pub(super) fn instantiate_constituent_tys_for_sized_trait<'tcx>(
     }
 }
 
-pub(super) fn instantiate_constituent_tys_for_copy_clone_trait<'tcx>(
+pub(in crate::solve) fn instantiate_constituent_tys_for_copy_clone_trait<'tcx>(
     ecx: &EvalCtxt<'_, 'tcx>,
     ty: Ty<'tcx>,
 ) -> Result<Vec<Ty<'tcx>>, NoSolution> {
@@ -178,29 +208,65 @@ pub(super) fn instantiate_constituent_tys_for_copy_clone_trait<'tcx>(
 
         ty::GeneratorWitness(types) => Ok(ecx.instantiate_binder_with_placeholders(types).to_vec()),
 
-        ty::GeneratorWitnessMIR(..) => todo!(),
+        ty::GeneratorWitnessMIR(def_id, substs) => Ok(ecx
+            .tcx()
+            .generator_hidden_types(def_id)
+            .map(|bty| {
+                ecx.instantiate_binder_with_placeholders(replace_erased_lifetimes_with_bound_vars(
+                    ecx.tcx(),
+                    bty.subst(ecx.tcx(), substs),
+                ))
+            })
+            .collect()),
     }
 }
 
 // Returns a binder of the tupled inputs types and output type from a builtin callable type.
-pub(crate) fn extract_tupled_inputs_and_output_from_callable<'tcx>(
+pub(in crate::solve) fn extract_tupled_inputs_and_output_from_callable<'tcx>(
     tcx: TyCtxt<'tcx>,
     self_ty: Ty<'tcx>,
     goal_kind: ty::ClosureKind,
 ) -> Result<Option<ty::Binder<'tcx, (Ty<'tcx>, Ty<'tcx>)>>, NoSolution> {
     match *self_ty.kind() {
-        ty::FnDef(def_id, substs) => Ok(Some(
-            tcx.fn_sig(def_id)
-                .subst(tcx, substs)
-                .map_bound(|sig| (tcx.mk_tup(sig.inputs()), sig.output())),
-        )),
-        ty::FnPtr(sig) => Ok(Some(sig.map_bound(|sig| (tcx.mk_tup(sig.inputs()), sig.output())))),
+        // keep this in sync with assemble_fn_pointer_candidates until the old solver is removed.
+        ty::FnDef(def_id, substs) => {
+            let sig = tcx.fn_sig(def_id);
+            if sig.skip_binder().is_fn_trait_compatible()
+                && tcx.codegen_fn_attrs(def_id).target_features.is_empty()
+            {
+                Ok(Some(
+                    sig.subst(tcx, substs)
+                        .map_bound(|sig| (tcx.mk_tup(sig.inputs()), sig.output())),
+                ))
+            } else {
+                Err(NoSolution)
+            }
+        }
+        // keep this in sync with assemble_fn_pointer_candidates until the old solver is removed.
+        ty::FnPtr(sig) => {
+            if sig.is_fn_trait_compatible() {
+                Ok(Some(sig.map_bound(|sig| (tcx.mk_tup(sig.inputs()), sig.output()))))
+            } else {
+                Err(NoSolution)
+            }
+        }
         ty::Closure(_, substs) => {
             let closure_substs = substs.as_closure();
             match closure_substs.kind_ty().to_opt_closure_kind() {
-                Some(closure_kind) if closure_kind.extends(goal_kind) => {}
-                None => return Ok(None),
-                _ => return Err(NoSolution),
+                // If the closure's kind doesn't extend the goal kind,
+                // then the closure doesn't implement the trait.
+                Some(closure_kind) => {
+                    if !closure_kind.extends(goal_kind) {
+                        return Err(NoSolution);
+                    }
+                }
+                // Closure kind is not yet determined, so we return ambiguity unless
+                // the expected kind is `FnOnce` as that is always implemented.
+                None => {
+                    if goal_kind != ty::ClosureKind::FnOnce {
+                        return Ok(None);
+                    }
+                }
             }
             Ok(Some(closure_substs.sig().map_bound(|sig| (sig.inputs()[0], sig.output()))))
         }
@@ -269,7 +335,13 @@ pub(crate) fn extract_tupled_inputs_and_output_from_callable<'tcx>(
 /// additional step of eagerly folding the associated types in the where
 /// clauses of the impl. In this example, that means replacing
 /// `<Self as Foo>::Bar` with `Ty` in the first impl.
-pub(crate) fn predicates_for_object_candidate<'tcx>(
+///
+// FIXME: This is only necessary as `<Self as Trait>::Assoc: ItemBound`
+// bounds in impls are trivially proven using the item bound candidates.
+// This is unsound in general and once that is fixed, we don't need to
+// normalize eagerly here. See https://github.com/lcnr/solver-woes/issues/9
+// for more details.
+pub(in crate::solve) fn predicates_for_object_candidate<'tcx>(
     ecx: &EvalCtxt<'_, 'tcx>,
     param_env: ty::ParamEnv<'tcx>,
     trait_ref: ty::TraitRef<'tcx>,
@@ -333,7 +405,7 @@ impl<'tcx> TypeFolder<TyCtxt<'tcx>> for ReplaceProjectionWith<'_, 'tcx> {
             // FIXME: Technically this folder could be fallible?
             let nested = self
                 .ecx
-                .eq(self.param_env, alias_ty, proj.projection_ty)
+                .eq_and_get_goals(self.param_env, alias_ty, proj.projection_ty)
                 .expect("expected to be able to unify goal projection with dyn's projection");
             // FIXME: Technically we could register these too..
             assert!(nested.is_empty(), "did not expect unification to have any nested goals");
diff --git a/compiler/rustc_trait_selection/src/solve/canonical/canonicalize.rs b/compiler/rustc_trait_selection/src/solve/canonicalize.rs
index c048d4a2a..976849696 100644
--- a/compiler/rustc_trait_selection/src/solve/canonical/canonicalize.rs
+++ b/compiler/rustc_trait_selection/src/solve/canonicalize.rs
@@ -13,7 +13,7 @@ use rustc_middle::ty::TypeVisitableExt;
 use rustc_middle::ty::{self, Ty};
 use rustc_middle::ty::{TypeFoldable, TypeFolder, TypeSuperFoldable};
 
-/// Whether we're canonicalizing a query input or the query reponse.
+/// Whether we're canonicalizing a query input or the query response.
 ///
 /// When canonicalizing an input we're in the context of the caller
 /// while canonicalizing the response happens in the context of the
@@ -21,7 +21,7 @@ use rustc_middle::ty::{TypeFoldable, TypeFolder, TypeSuperFoldable};
 #[derive(Debug, Clone, Copy)]
 pub enum CanonicalizeMode {
     Input,
-    /// FIXME: We currently return region constraints refering to
+    /// FIXME: We currently return region constraints referring to
     /// placeholders and inference variables from a binder instantiated
     /// inside of the query.
     ///
@@ -125,8 +125,9 @@ impl<'a, 'tcx> Canonicalizer<'a, 'tcx> {
         // - var_infos: [E0, U1, E1, U1, E1, E6, U6], curr_compressed_uv: 1, next_orig_uv: 6
         // - var_infos: [E0, U1, E1, U1, E1, E2, U2], curr_compressed_uv: 2, next_orig_uv: -
         //
-        // This algorithm runs in `O(n²)` where `n` is the number of different universe
-        // indices in the input. This should be fine as `n` is expected to be small.
+        // This algorithm runs in `O(nm)` where `n` is the number of different universe
+        // indices in the input and `m` is the number of canonical variables.
+        // This should be fine as both `n` and `m` are expected to be small.
         let mut curr_compressed_uv = ty::UniverseIndex::ROOT;
         let mut existential_in_new_uv = false;
         let mut next_orig_uv = Some(ty::UniverseIndex::ROOT);
@@ -245,42 +246,49 @@ impl<'tcx> TypeFolder<TyCtxt<'tcx>> for Canonicalizer<'_, 'tcx> {
             ty::ReError(_) => return r,
         };
 
-        let existing_bound_var = match self.canonicalize_mode {
-            CanonicalizeMode::Input => None,
-            CanonicalizeMode::Response { .. } => {
-                self.variables.iter().position(|&v| v == r.into()).map(ty::BoundVar::from)
-            }
-        };
-        let var = existing_bound_var.unwrap_or_else(|| {
-            let var = ty::BoundVar::from(self.variables.len());
-            self.variables.push(r.into());
-            self.primitive_var_infos.push(CanonicalVarInfo { kind });
-            var
-        });
-        let br = ty::BoundRegion { var, kind: BrAnon(var.as_u32(), None) };
+        let var = ty::BoundVar::from(
+            self.variables.iter().position(|&v| v == r.into()).unwrap_or_else(|| {
+                let var = self.variables.len();
+                self.variables.push(r.into());
+                self.primitive_var_infos.push(CanonicalVarInfo { kind });
+                var
+            }),
+        );
+        let br = ty::BoundRegion { var, kind: BrAnon(None) };
         self.interner().mk_re_late_bound(self.binder_index, br)
     }
 
-    fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
+    fn fold_ty(&mut self, mut t: Ty<'tcx>) -> Ty<'tcx> {
         let kind = match *t.kind() {
-            ty::Infer(ty::TyVar(vid)) => match self.infcx.probe_ty_var(vid) {
-                Ok(t) => return self.fold_ty(t),
-                Err(ui) => CanonicalVarKind::Ty(CanonicalTyVarKind::General(ui)),
-            },
-            ty::Infer(ty::IntVar(_)) => {
-                let nt = self.infcx.shallow_resolve(t);
+            ty::Infer(ty::TyVar(mut vid)) => {
+                // We need to canonicalize the *root* of our ty var.
+                // This is so that our canonical response correctly reflects
+                // any equated inference vars correctly!
+                let root_vid = self.infcx.root_var(vid);
+                if root_vid != vid {
+                    t = self.infcx.tcx.mk_ty_var(root_vid);
+                    vid = root_vid;
+                }
+
+                match self.infcx.probe_ty_var(vid) {
+                    Ok(t) => return self.fold_ty(t),
+                    Err(ui) => CanonicalVarKind::Ty(CanonicalTyVarKind::General(ui)),
+                }
+            }
+            ty::Infer(ty::IntVar(vid)) => {
+                let nt = self.infcx.opportunistic_resolve_int_var(vid);
                 if nt != t {
                     return self.fold_ty(nt);
                 } else {
                     CanonicalVarKind::Ty(CanonicalTyVarKind::Int)
                 }
             }
-            ty::Infer(ty::FloatVar(_)) => {
-                let nt = self.infcx.shallow_resolve(t);
+            ty::Infer(ty::FloatVar(vid)) => {
+                let nt = self.infcx.opportunistic_resolve_float_var(vid);
                 if nt != t {
                     return self.fold_ty(nt);
                 } else {
-                    CanonicalVarKind::Ty(CanonicalTyVarKind::Int)
+                    CanonicalVarKind::Ty(CanonicalTyVarKind::Float)
                 }
             }
             ty::Infer(ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_)) => {
@@ -289,14 +297,20 @@ impl<'tcx> TypeFolder<TyCtxt<'tcx>> for Canonicalizer<'_, 'tcx> {
             ty::Placeholder(placeholder) => match self.canonicalize_mode {
                 CanonicalizeMode::Input => CanonicalVarKind::PlaceholderTy(ty::Placeholder {
                     universe: placeholder.universe,
-                    name: BoundTyKind::Anon(self.variables.len() as u32),
+                    bound: ty::BoundTy {
+                        var: ty::BoundVar::from_usize(self.variables.len()),
+                        kind: ty::BoundTyKind::Anon,
+                    },
                 }),
                 CanonicalizeMode::Response { .. } => CanonicalVarKind::PlaceholderTy(placeholder),
             },
             ty::Param(_) => match self.canonicalize_mode {
                 CanonicalizeMode::Input => CanonicalVarKind::PlaceholderTy(ty::Placeholder {
                     universe: ty::UniverseIndex::ROOT,
-                    name: ty::BoundTyKind::Anon(self.variables.len() as u32),
+                    bound: ty::BoundTy {
+                        var: ty::BoundVar::from_usize(self.variables.len()),
+                        kind: ty::BoundTyKind::Anon,
+                    },
                 }),
                 CanonicalizeMode::Response { .. } => bug!("param ty in response: {t:?}"),
             },
@@ -334,17 +348,27 @@ impl<'tcx> TypeFolder<TyCtxt<'tcx>> for Canonicalizer<'_, 'tcx> {
                 var
             }),
         );
-        let bt = ty::BoundTy { var, kind: BoundTyKind::Anon(var.index() as u32) };
+        let bt = ty::BoundTy { var, kind: BoundTyKind::Anon };
         self.interner().mk_bound(self.binder_index, bt)
     }
 
-    fn fold_const(&mut self, c: ty::Const<'tcx>) -> ty::Const<'tcx> {
+    fn fold_const(&mut self, mut c: ty::Const<'tcx>) -> ty::Const<'tcx> {
         let kind = match c.kind() {
-            ty::ConstKind::Infer(ty::InferConst::Var(vid)) => match self.infcx.probe_const_var(vid)
-            {
-                Ok(c) => return self.fold_const(c),
-                Err(universe) => CanonicalVarKind::Const(universe, c.ty()),
-            },
+            ty::ConstKind::Infer(ty::InferConst::Var(mut vid)) => {
+                // We need to canonicalize the *root* of our const var.
+                // This is so that our canonical response correctly reflects
+                // any equated inference vars correctly!
+                let root_vid = self.infcx.root_const_var(vid);
+                if root_vid != vid {
+                    c = self.infcx.tcx.mk_const(ty::InferConst::Var(root_vid), c.ty());
+                    vid = root_vid;
+                }
+
+                match self.infcx.probe_const_var(vid) {
+                    Ok(c) => return self.fold_const(c),
+                    Err(universe) => CanonicalVarKind::Const(universe, c.ty()),
+                }
+            }
             ty::ConstKind::Infer(ty::InferConst::Fresh(_)) => {
                 bug!("fresh var during canonicalization: {c:?}")
             }
@@ -352,7 +376,7 @@ impl<'tcx> TypeFolder<TyCtxt<'tcx>> for Canonicalizer<'_, 'tcx> {
                 CanonicalizeMode::Input => CanonicalVarKind::PlaceholderConst(
                     ty::Placeholder {
                         universe: placeholder.universe,
-                        name: ty::BoundVar::from(self.variables.len()),
+                        bound: ty::BoundVar::from(self.variables.len()),
                     },
                     c.ty(),
                 ),
@@ -364,7 +388,7 @@ impl<'tcx> TypeFolder<TyCtxt<'tcx>> for Canonicalizer<'_, 'tcx> {
                 CanonicalizeMode::Input => CanonicalVarKind::PlaceholderConst(
                     ty::Placeholder {
                         universe: ty::UniverseIndex::ROOT,
-                        name: ty::BoundVar::from(self.variables.len()),
+                        bound: ty::BoundVar::from(self.variables.len()),
                     },
                     c.ty(),
                 ),
diff --git a/compiler/rustc_trait_selection/src/solve/eval_ctxt.rs b/compiler/rustc_trait_selection/src/solve/eval_ctxt.rs
index 95612674e..c29b5b04e 100644
--- a/compiler/rustc_trait_selection/src/solve/eval_ctxt.rs
+++ b/compiler/rustc_trait_selection/src/solve/eval_ctxt.rs
@@ -2,10 +2,13 @@ use rustc_hir::def_id::DefId;
 use rustc_infer::infer::at::ToTrace;
 use rustc_infer::infer::canonical::CanonicalVarValues;
 use rustc_infer::infer::type_variable::{TypeVariableOrigin, TypeVariableOriginKind};
-use rustc_infer::infer::{InferCtxt, InferOk, LateBoundRegionConversionTime};
+use rustc_infer::infer::{
+    DefineOpaqueTypes, InferCtxt, InferOk, LateBoundRegionConversionTime, TyCtxtInferExt,
+};
 use rustc_infer::traits::query::NoSolution;
 use rustc_infer::traits::ObligationCause;
 use rustc_middle::infer::unify_key::{ConstVariableOrigin, ConstVariableOriginKind};
+use rustc_middle::traits::solve::{CanonicalGoal, Certainty, MaybeCause, QueryResult};
 use rustc_middle::ty::{
     self, Ty, TyCtxt, TypeFoldable, TypeSuperVisitable, TypeVisitable, TypeVisitableExt,
     TypeVisitor,
@@ -13,12 +16,32 @@ use rustc_middle::ty::{
 use rustc_span::DUMMY_SP;
 use std::ops::ControlFlow;
 
-use super::search_graph::SearchGraph;
-use super::Goal;
+use crate::traits::specialization_graph;
+
+use super::search_graph::{self, OverflowHandler};
+use super::SolverMode;
+use super::{search_graph::SearchGraph, Goal};
+
+mod canonical;
 
 pub struct EvalCtxt<'a, 'tcx> {
-    // FIXME: should be private.
-    pub(super) infcx: &'a InferCtxt<'tcx>,
+    /// The inference context that backs (mostly) inference and placeholder terms
+    /// instantiated while solving goals.
+    ///
+    /// NOTE: The `InferCtxt` that backs the `EvalCtxt` is intentionally private,
+    /// because the `InferCtxt` is much more general than `EvalCtxt`. Methods such
+    /// as  `take_registered_region_obligations` can mess up query responses,
+    /// using `At::normalize` is totally wrong, calling `evaluate_root_goal` can
+    /// cause coinductive unsoundness, etc.
+    ///
+    /// Methods that are generally of use for trait solving are *intentionally*
+    /// re-declared through the `EvalCtxt` below, often with cleaner signatures
+    /// since we don't care about things like `ObligationCause`s and `Span`s here.
+    /// If some `InferCtxt` method is missing, please first think defensively about
+    /// the method's compatibility with this solver, or if an existing one does
+    /// the job already.
+    infcx: &'a InferCtxt<'tcx>,
+
     pub(super) var_values: CanonicalVarValues<'tcx>,
     /// The highest universe index nameable by the caller.
     ///
@@ -33,14 +56,356 @@ pub struct EvalCtxt<'a, 'tcx> {
 
     pub(super) search_graph: &'a mut SearchGraph<'tcx>,
 
-    /// This field is used by a debug assertion in [`EvalCtxt::evaluate_goal`],
-    /// see the comment in that method for more details.
-    pub in_projection_eq_hack: bool,
+    pub(super) nested_goals: NestedGoals<'tcx>,
+}
+
+#[derive(Debug, Copy, Clone, PartialEq, Eq)]
+pub(super) enum IsNormalizesToHack {
+    Yes,
+    No,
+}
+
+#[derive(Debug, Clone)]
+pub(super) struct NestedGoals<'tcx> {
+    /// This normalizes-to goal that is treated specially during the evaluation
+    /// loop. In each iteration we take the RHS of the projection, replace it with
+    /// a fresh inference variable, and only after evaluating that goal do we
+    /// equate the fresh inference variable with the actual RHS of the predicate.
+    ///
+    /// This is both to improve caching, and to avoid using the RHS of the
+    /// projection predicate to influence the normalizes-to candidate we select.
+    ///
+    /// This is not a 'real' nested goal. We must not forget to replace the RHS
+    /// with a fresh inference variable when we evaluate this goal. That can result
+    /// in a trait solver cycle. This would currently result in overflow but can be
+    /// can be unsound with more powerful coinduction in the future.
+    pub(super) normalizes_to_hack_goal: Option<Goal<'tcx, ty::ProjectionPredicate<'tcx>>>,
+    /// The rest of the goals which have not yet processed or remain ambiguous.
+    pub(super) goals: Vec<Goal<'tcx, ty::Predicate<'tcx>>>,
+}
+
+impl NestedGoals<'_> {
+    pub(super) fn new() -> Self {
+        Self { normalizes_to_hack_goal: None, goals: Vec::new() }
+    }
+
+    pub(super) fn is_empty(&self) -> bool {
+        self.normalizes_to_hack_goal.is_none() && self.goals.is_empty()
+    }
+}
+
+pub trait InferCtxtEvalExt<'tcx> {
+    /// Evaluates a goal from **outside** of the trait solver.
+    ///
+    /// Using this while inside of the solver is wrong as it uses a new
+    /// search graph which would break cycle detection.
+    fn evaluate_root_goal(
+        &self,
+        goal: Goal<'tcx, ty::Predicate<'tcx>>,
+    ) -> Result<(bool, Certainty, Vec<Goal<'tcx, ty::Predicate<'tcx>>>), NoSolution>;
+}
+
+impl<'tcx> InferCtxtEvalExt<'tcx> for InferCtxt<'tcx> {
+    #[instrument(level = "debug", skip(self), ret)]
+    fn evaluate_root_goal(
+        &self,
+        goal: Goal<'tcx, ty::Predicate<'tcx>>,
+    ) -> Result<(bool, Certainty, Vec<Goal<'tcx, ty::Predicate<'tcx>>>), NoSolution> {
+        let mode = if self.intercrate { SolverMode::Coherence } else { SolverMode::Normal };
+        let mut search_graph = search_graph::SearchGraph::new(self.tcx, mode);
+
+        let mut ecx = EvalCtxt {
+            search_graph: &mut search_graph,
+            infcx: self,
+            // Only relevant when canonicalizing the response.
+            max_input_universe: ty::UniverseIndex::ROOT,
+            var_values: CanonicalVarValues::dummy(),
+            nested_goals: NestedGoals::new(),
+        };
+        let result = ecx.evaluate_goal(IsNormalizesToHack::No, goal);
+
+        assert!(
+            ecx.nested_goals.is_empty(),
+            "root `EvalCtxt` should not have any goals added to it"
+        );
+
+        assert!(search_graph.is_empty());
+        result
+    }
+}
+
+impl<'a, 'tcx> EvalCtxt<'a, 'tcx> {
+    pub(super) fn solver_mode(&self) -> SolverMode {
+        self.search_graph.solver_mode()
+    }
+
+    /// The entry point of the solver.
+    ///
+    /// This function deals with (coinductive) cycles, overflow, and caching
+    /// and then calls [`EvalCtxt::compute_goal`] which contains the actual
+    /// logic of the solver.
+    ///
+    /// Instead of calling this function directly, use either [EvalCtxt::evaluate_goal]
+    /// if you're inside of the solver or [InferCtxtEvalExt::evaluate_root_goal] if you're
+    /// outside of it.
+    #[instrument(level = "debug", skip(tcx, search_graph), ret)]
+    fn evaluate_canonical_goal(
+        tcx: TyCtxt<'tcx>,
+        search_graph: &'a mut search_graph::SearchGraph<'tcx>,
+        canonical_goal: CanonicalGoal<'tcx>,
+    ) -> QueryResult<'tcx> {
+        // Deal with overflow, caching, and coinduction.
+        //
+        // The actual solver logic happens in `ecx.compute_goal`.
+        search_graph.with_new_goal(tcx, canonical_goal, |search_graph| {
+            let intercrate = match search_graph.solver_mode() {
+                SolverMode::Normal => false,
+                SolverMode::Coherence => true,
+            };
+            let (ref infcx, goal, var_values) = tcx
+                .infer_ctxt()
+                .intercrate(intercrate)
+                .build_with_canonical(DUMMY_SP, &canonical_goal);
+            let mut ecx = EvalCtxt {
+                infcx,
+                var_values,
+                max_input_universe: canonical_goal.max_universe,
+                search_graph,
+                nested_goals: NestedGoals::new(),
+            };
+            ecx.compute_goal(goal)
+        })
+    }
+
+    /// Recursively evaluates `goal`, returning whether any inference vars have
+    /// been constrained and the certainty of the result.
+    fn evaluate_goal(
+        &mut self,
+        is_normalizes_to_hack: IsNormalizesToHack,
+        goal: Goal<'tcx, ty::Predicate<'tcx>>,
+    ) -> Result<(bool, Certainty, Vec<Goal<'tcx, ty::Predicate<'tcx>>>), NoSolution> {
+        let (orig_values, canonical_goal) = self.canonicalize_goal(goal);
+        let canonical_response =
+            EvalCtxt::evaluate_canonical_goal(self.tcx(), self.search_graph, canonical_goal)?;
+
+        let has_changed = !canonical_response.value.var_values.is_identity();
+        let (certainty, nested_goals) = self.instantiate_and_apply_query_response(
+            goal.param_env,
+            orig_values,
+            canonical_response,
+        )?;
+
+        if !has_changed && !nested_goals.is_empty() {
+            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.
+        //
+        // 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
+            && is_normalizes_to_hack == IsNormalizesToHack::No
+            && !self.search_graph.in_cycle()
+        {
+            debug!("rerunning goal to check result is stable");
+            let (_orig_values, canonical_goal) = self.canonicalize_goal(goal);
+            let canonical_response =
+                EvalCtxt::evaluate_canonical_goal(self.tcx(), self.search_graph, canonical_goal)?;
+            if !canonical_response.value.var_values.is_identity() {
+                bug!(
+                    "unstable result: re-canonicalized goal={canonical_goal:#?} \
+                     response={canonical_response:#?}"
+                );
+            }
+            if certainty != canonical_response.value.certainty {
+                bug!(
+                    "unstable certainty: {certainty:#?} re-canonicalized goal={canonical_goal:#?} \
+                     response={canonical_response:#?}"
+                );
+            }
+        }
+
+        Ok((has_changed, certainty, nested_goals))
+    }
+
+    fn compute_goal(&mut self, goal: Goal<'tcx, ty::Predicate<'tcx>>) -> QueryResult<'tcx> {
+        let Goal { param_env, predicate } = goal;
+        let kind = predicate.kind();
+        if let Some(kind) = kind.no_bound_vars() {
+            match kind {
+                ty::PredicateKind::Clause(ty::Clause::Trait(predicate)) => {
+                    self.compute_trait_goal(Goal { param_env, predicate })
+                }
+                ty::PredicateKind::Clause(ty::Clause::Projection(predicate)) => {
+                    self.compute_projection_goal(Goal { param_env, predicate })
+                }
+                ty::PredicateKind::Clause(ty::Clause::TypeOutlives(predicate)) => {
+                    self.compute_type_outlives_goal(Goal { param_env, predicate })
+                }
+                ty::PredicateKind::Clause(ty::Clause::RegionOutlives(predicate)) => {
+                    self.compute_region_outlives_goal(Goal { param_env, predicate })
+                }
+                ty::PredicateKind::Clause(ty::Clause::ConstArgHasType(ct, ty)) => {
+                    self.compute_const_arg_has_type_goal(Goal { param_env, predicate: (ct, ty) })
+                }
+                ty::PredicateKind::Subtype(predicate) => {
+                    self.compute_subtype_goal(Goal { param_env, predicate })
+                }
+                ty::PredicateKind::Coerce(predicate) => {
+                    self.compute_coerce_goal(Goal { param_env, predicate })
+                }
+                ty::PredicateKind::ClosureKind(def_id, substs, kind) => self
+                    .compute_closure_kind_goal(Goal {
+                        param_env,
+                        predicate: (def_id, substs, kind),
+                    }),
+                ty::PredicateKind::ObjectSafe(trait_def_id) => {
+                    self.compute_object_safe_goal(trait_def_id)
+                }
+                ty::PredicateKind::WellFormed(arg) => {
+                    self.compute_well_formed_goal(Goal { param_env, predicate: arg })
+                }
+                ty::PredicateKind::Ambiguous => {
+                    self.evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS)
+                }
+                // FIXME: implement these predicates :)
+                ty::PredicateKind::ConstEvaluatable(_) | ty::PredicateKind::ConstEquate(_, _) => {
+                    self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
+                }
+                ty::PredicateKind::TypeWellFormedFromEnv(..) => {
+                    bug!("TypeWellFormedFromEnv is only used for Chalk")
+                }
+                ty::PredicateKind::AliasRelate(lhs, rhs, direction) => self
+                    .compute_alias_relate_goal(Goal {
+                        param_env,
+                        predicate: (lhs, rhs, direction),
+                    }),
+            }
+        } else {
+            let kind = self.infcx.instantiate_binder_with_placeholders(kind);
+            let goal = goal.with(self.tcx(), ty::Binder::dummy(kind));
+            self.add_goal(goal);
+            self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
+        }
+    }
+
+    // Recursively evaluates all the goals added to this `EvalCtxt` to completion, returning
+    // the certainty of all the goals.
+    #[instrument(level = "debug", skip(self))]
+    pub(super) fn try_evaluate_added_goals(&mut self) -> Result<Certainty, NoSolution> {
+        let mut goals = core::mem::replace(&mut self.nested_goals, NestedGoals::new());
+        let mut new_goals = NestedGoals::new();
+
+        let response = self.repeat_while_none(
+            |_| Ok(Certainty::Maybe(MaybeCause::Overflow)),
+            |this| {
+                let mut has_changed = Err(Certainty::Yes);
+
+                if let Some(goal) = goals.normalizes_to_hack_goal.take() {
+                    // Replace the goal with an unconstrained infer var, so the
+                    // RHS does not affect projection candidate assembly.
+                    let unconstrained_rhs = this.next_term_infer_of_kind(goal.predicate.term);
+                    let unconstrained_goal = goal.with(
+                        this.tcx(),
+                        ty::Binder::dummy(ty::ProjectionPredicate {
+                            projection_ty: goal.predicate.projection_ty,
+                            term: unconstrained_rhs,
+                        }),
+                    );
+
+                    let (_, certainty, instantiate_goals) =
+                        match this.evaluate_goal(IsNormalizesToHack::Yes, unconstrained_goal) {
+                            Ok(r) => r,
+                            Err(NoSolution) => return Some(Err(NoSolution)),
+                        };
+                    new_goals.goals.extend(instantiate_goals);
+
+                    // Finally, equate the goal's RHS with the unconstrained var.
+                    // We put the nested goals from this into goals instead of
+                    // next_goals to avoid needing to process the loop one extra
+                    // time if this goal returns something -- I don't think this
+                    // matters in practice, though.
+                    match this.eq_and_get_goals(
+                        goal.param_env,
+                        goal.predicate.term,
+                        unconstrained_rhs,
+                    ) {
+                        Ok(eq_goals) => {
+                            goals.goals.extend(eq_goals);
+                        }
+                        Err(NoSolution) => return Some(Err(NoSolution)),
+                    };
+
+                    // We only look at the `projection_ty` part here rather than
+                    // looking at the "has changed" return from evaluate_goal,
+                    // because we expect the `unconstrained_rhs` part of the predicate
+                    // to have changed -- that means we actually normalized successfully!
+                    if goal.predicate.projection_ty
+                        != this.resolve_vars_if_possible(goal.predicate.projection_ty)
+                    {
+                        has_changed = Ok(())
+                    }
+
+                    match certainty {
+                        Certainty::Yes => {}
+                        Certainty::Maybe(_) => {
+                            // We need to resolve vars here so that we correctly
+                            // deal with `has_changed` in the next iteration.
+                            new_goals.normalizes_to_hack_goal =
+                                Some(this.resolve_vars_if_possible(goal));
+                            has_changed = has_changed.map_err(|c| c.unify_with(certainty));
+                        }
+                    }
+                }
+
+                for goal in goals.goals.drain(..) {
+                    let (changed, certainty, instantiate_goals) =
+                        match this.evaluate_goal(IsNormalizesToHack::No, goal) {
+                            Ok(result) => result,
+                            Err(NoSolution) => return Some(Err(NoSolution)),
+                        };
+                    new_goals.goals.extend(instantiate_goals);
+
+                    if changed {
+                        has_changed = Ok(());
+                    }
+
+                    match certainty {
+                        Certainty::Yes => {}
+                        Certainty::Maybe(_) => {
+                            new_goals.goals.push(goal);
+                            has_changed = has_changed.map_err(|c| c.unify_with(certainty));
+                        }
+                    }
+                }
+
+                core::mem::swap(&mut new_goals, &mut goals);
+                match has_changed {
+                    Ok(()) => None,
+                    Err(certainty) => Some(Ok(certainty)),
+                }
+            },
+        );
+
+        self.nested_goals = goals;
+        response
+    }
 }
 
 impl<'tcx> EvalCtxt<'_, 'tcx> {
     pub(super) fn probe<T>(&mut self, f: impl FnOnce(&mut EvalCtxt<'_, 'tcx>) -> T) -> T {
-        self.infcx.probe(|_| f(self))
+        let mut ecx = EvalCtxt {
+            infcx: self.infcx,
+            var_values: self.var_values,
+            max_input_universe: self.max_input_universe,
+            search_graph: self.search_graph,
+            nested_goals: self.nested_goals.clone(),
+        };
+        self.infcx.probe(|_| f(&mut ecx))
     }
 
     pub(super) fn tcx(&self) -> TyCtxt<'tcx> {
@@ -61,6 +426,15 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
         )
     }
 
+    /// Returns a ty infer or a const infer depending on whether `kind` is a `Ty` or `Const`.
+    /// If `kind` is an integer inference variable this will still return a ty infer var.
+    pub(super) fn next_term_infer_of_kind(&self, kind: ty::Term<'tcx>) -> ty::Term<'tcx> {
+        match kind.unpack() {
+            ty::TermKind::Ty(_) => self.next_ty_infer().into(),
+            ty::TermKind::Const(ct) => self.next_const_infer(ct.ty()).into(),
+        }
+    }
+
     /// Is the projection predicate is of the form `exists<T> <Ty as Trait>::Assoc = T`.
     ///
     /// This is the case if the `term` is an inference variable in the innermost universe
@@ -74,7 +448,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
                 if let &ty::Infer(ty::TyVar(vid)) = ty.kind() {
                     match self.infcx.probe_ty_var(vid) {
                         Ok(value) => bug!("resolved var in query: {goal:?} {value:?}"),
-                        Err(universe) => universe == self.universe(),
+                        Err(universe) => universe == self.infcx.universe(),
                     }
                 } else {
                     false
@@ -84,7 +458,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
                 if let ty::ConstKind::Infer(ty::InferConst::Var(vid)) = ct.kind() {
                     match self.infcx.probe_const_var(vid) {
                         Ok(value) => bug!("resolved var in query: {goal:?} {value:?}"),
-                        Err(universe) => universe == self.universe(),
+                        Err(universe) => universe == self.infcx.universe(),
                     }
                 } else {
                     false
@@ -93,37 +467,42 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
         };
 
         // Guard against `<T as Trait<?0>>::Assoc = ?0>`.
-        struct ContainsTerm<'tcx> {
+        struct ContainsTerm<'a, 'tcx> {
             term: ty::Term<'tcx>,
+            infcx: &'a InferCtxt<'tcx>,
         }
-        impl<'tcx> TypeVisitor<TyCtxt<'tcx>> for ContainsTerm<'tcx> {
+        impl<'tcx> TypeVisitor<TyCtxt<'tcx>> for ContainsTerm<'_, 'tcx> {
             type BreakTy = ();
             fn visit_ty(&mut self, t: Ty<'tcx>) -> ControlFlow<Self::BreakTy> {
-                if t.needs_infer() {
-                    if ty::Term::from(t) == self.term {
-                        ControlFlow::Break(())
-                    } else {
-                        t.super_visit_with(self)
-                    }
+                if let Some(vid) = t.ty_vid()
+                    && let ty::TermKind::Ty(term) = self.term.unpack()
+                    && let Some(term_vid) = term.ty_vid()
+                    && self.infcx.root_var(vid) == self.infcx.root_var(term_vid)
+                {
+                    ControlFlow::Break(())
+                } else if t.has_non_region_infer() {
+                    t.super_visit_with(self)
                 } else {
                     ControlFlow::Continue(())
                 }
             }
 
             fn visit_const(&mut self, c: ty::Const<'tcx>) -> ControlFlow<Self::BreakTy> {
-                if c.needs_infer() {
-                    if ty::Term::from(c) == self.term {
-                        ControlFlow::Break(())
-                    } else {
-                        c.super_visit_with(self)
-                    }
+                if let ty::ConstKind::Infer(ty::InferConst::Var(vid)) = c.kind()
+                    && let ty::TermKind::Const(term) = self.term.unpack()
+                    && let ty::ConstKind::Infer(ty::InferConst::Var(term_vid)) = term.kind()
+                    && self.infcx.root_const_var(vid) == self.infcx.root_const_var(term_vid)
+                {
+                    ControlFlow::Break(())
+                } else if c.has_non_region_infer() {
+                    c.super_visit_with(self)
                 } else {
                     ControlFlow::Continue(())
                 }
             }
         }
 
-        let mut visitor = ContainsTerm { term: goal.predicate.term };
+        let mut visitor = ContainsTerm { infcx: self.infcx, term: goal.predicate.term };
 
         term_is_infer
             && goal.predicate.projection_ty.visit_with(&mut visitor).is_continue()
@@ -132,6 +511,49 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
 
     #[instrument(level = "debug", skip(self, param_env), ret)]
     pub(super) fn eq<T: ToTrace<'tcx>>(
+        &mut self,
+        param_env: ty::ParamEnv<'tcx>,
+        lhs: T,
+        rhs: T,
+    ) -> Result<(), NoSolution> {
+        self.infcx
+            .at(&ObligationCause::dummy(), param_env)
+            .eq(DefineOpaqueTypes::No, lhs, rhs)
+            .map(|InferOk { value: (), obligations }| {
+                self.add_goals(obligations.into_iter().map(|o| o.into()));
+            })
+            .map_err(|e| {
+                debug!(?e, "failed to equate");
+                NoSolution
+            })
+    }
+
+    #[instrument(level = "debug", skip(self, param_env), ret)]
+    pub(super) fn sub<T: ToTrace<'tcx>>(
+        &mut self,
+        param_env: ty::ParamEnv<'tcx>,
+        sub: T,
+        sup: T,
+    ) -> Result<(), NoSolution> {
+        self.infcx
+            .at(&ObligationCause::dummy(), param_env)
+            .sub(DefineOpaqueTypes::No, sub, sup)
+            .map(|InferOk { value: (), obligations }| {
+                self.add_goals(obligations.into_iter().map(|o| o.into()));
+            })
+            .map_err(|e| {
+                debug!(?e, "failed to subtype");
+                NoSolution
+            })
+    }
+
+    /// Equates two values returning the nested goals without adding them
+    /// to the nested goals of the `EvalCtxt`.
+    ///
+    /// If possible, try using `eq` instead which automatically handles nested
+    /// goals correctly.
+    #[instrument(level = "trace", skip(self, param_env), ret)]
+    pub(super) fn eq_and_get_goals<T: ToTrace<'tcx>>(
         &self,
         param_env: ty::ParamEnv<'tcx>,
         lhs: T,
@@ -139,7 +561,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
     ) -> Result<Vec<Goal<'tcx, ty::Predicate<'tcx>>>, NoSolution> {
         self.infcx
             .at(&ObligationCause::dummy(), param_env)
-            .eq(lhs, rhs)
+            .eq(DefineOpaqueTypes::No, lhs, rhs)
             .map(|InferOk { value: (), obligations }| {
                 obligations.into_iter().map(|o| o.into()).collect()
             })
@@ -178,7 +600,64 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
         self.infcx.fresh_substs_for_item(DUMMY_SP, def_id)
     }
 
-    pub(super) fn universe(&self) -> ty::UniverseIndex {
-        self.infcx.universe()
+    pub(super) fn translate_substs(
+        &self,
+        param_env: ty::ParamEnv<'tcx>,
+        source_impl: DefId,
+        source_substs: ty::SubstsRef<'tcx>,
+        target_node: specialization_graph::Node,
+    ) -> ty::SubstsRef<'tcx> {
+        crate::traits::translate_substs(
+            self.infcx,
+            param_env,
+            source_impl,
+            source_substs,
+            target_node,
+        )
+    }
+
+    pub(super) fn register_ty_outlives(&self, ty: Ty<'tcx>, lt: ty::Region<'tcx>) {
+        self.infcx.register_region_obligation_with_cause(ty, lt, &ObligationCause::dummy());
+    }
+
+    pub(super) fn register_region_outlives(&self, a: ty::Region<'tcx>, b: ty::Region<'tcx>) {
+        // `b : a` ==> `a <= b`
+        // (inlined from `InferCtxt::region_outlives_predicate`)
+        self.infcx.sub_regions(
+            rustc_infer::infer::SubregionOrigin::RelateRegionParamBound(DUMMY_SP),
+            b,
+            a,
+        );
+    }
+
+    /// Computes the list of goals required for `arg` to be well-formed
+    pub(super) fn well_formed_goals(
+        &self,
+        param_env: ty::ParamEnv<'tcx>,
+        arg: ty::GenericArg<'tcx>,
+    ) -> Option<impl Iterator<Item = Goal<'tcx, ty::Predicate<'tcx>>>> {
+        crate::traits::wf::unnormalized_obligations(self.infcx, param_env, arg)
+            .map(|obligations| obligations.into_iter().map(|obligation| obligation.into()))
+    }
+
+    pub(super) fn is_transmutable(
+        &self,
+        src_and_dst: rustc_transmute::Types<'tcx>,
+        scope: Ty<'tcx>,
+        assume: rustc_transmute::Assume,
+    ) -> Result<Certainty, NoSolution> {
+        // FIXME(transmutability): This really should be returning nested goals for `Answer::If*`
+        match rustc_transmute::TransmuteTypeEnv::new(self.infcx).is_transmutable(
+            ObligationCause::dummy(),
+            ty::Binder::dummy(src_and_dst),
+            scope,
+            assume,
+        ) {
+            rustc_transmute::Answer::Yes => Ok(Certainty::Yes),
+            rustc_transmute::Answer::No(_)
+            | rustc_transmute::Answer::IfTransmutable { .. }
+            | rustc_transmute::Answer::IfAll(_)
+            | rustc_transmute::Answer::IfAny(_) => Err(NoSolution),
+        }
     }
 }
diff --git a/compiler/rustc_trait_selection/src/solve/canonical/mod.rs b/compiler/rustc_trait_selection/src/solve/eval_ctxt/canonical.rs
index 8c3be8da1..ada868705 100644
--- a/compiler/rustc_trait_selection/src/solve/canonical/mod.rs
+++ b/compiler/rustc_trait_selection/src/solve/eval_ctxt/canonical.rs
@@ -8,22 +8,19 @@
 /// section of the [rustc-dev-guide][c].
 ///
 /// [c]: https://rustc-dev-guide.rust-lang.org/solve/canonicalization.html
-use self::canonicalize::{CanonicalizeMode, Canonicalizer};
 use super::{CanonicalGoal, Certainty, EvalCtxt, Goal};
-use super::{CanonicalResponse, ExternalConstraints, QueryResult, Response};
+use crate::solve::canonicalize::{CanonicalizeMode, Canonicalizer};
+use crate::solve::{CanonicalResponse, QueryResult, Response};
 use rustc_infer::infer::canonical::query_response::make_query_region_constraints;
 use rustc_infer::infer::canonical::CanonicalVarValues;
 use rustc_infer::infer::canonical::{CanonicalExt, QueryRegionConstraints};
-use rustc_infer::traits::query::NoSolution;
-use rustc_infer::traits::solve::ExternalConstraintsData;
-use rustc_infer::traits::ObligationCause;
+use rustc_middle::traits::query::NoSolution;
+use rustc_middle::traits::solve::{ExternalConstraints, ExternalConstraintsData};
 use rustc_middle::ty::{self, GenericArgKind};
 use rustc_span::DUMMY_SP;
 use std::iter;
 use std::ops::Deref;
 
-mod canonicalize;
-
 impl<'tcx> EvalCtxt<'_, 'tcx> {
     /// Canonicalizes the goal remembering the original values
     /// for each bound variable.
@@ -45,10 +42,16 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
     ///
     /// - `var_values`: a map from bound variables in the canonical goal to
     ///   the values inferred while solving the instantiated goal.
-    /// - `external_constraints`: additional constraints which aren't expressable
+    /// - `external_constraints`: additional constraints which aren't expressible
     ///   using simple unification of inference variables.
     #[instrument(level = "debug", skip(self))]
-    pub(super) fn make_canonical_response(&self, certainty: Certainty) -> QueryResult<'tcx> {
+    pub(in crate::solve) fn evaluate_added_goals_and_make_canonical_response(
+        &mut self,
+        certainty: Certainty,
+    ) -> QueryResult<'tcx> {
+        let goals_certainty = self.try_evaluate_added_goals()?;
+        let certainty = certainty.unify_with(goals_certainty);
+
         let external_constraints = self.compute_external_query_constraints()?;
 
         let response = Response { var_values: self.var_values, external_constraints, certainty };
@@ -93,24 +96,24 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
         param_env: ty::ParamEnv<'tcx>,
         original_values: Vec<ty::GenericArg<'tcx>>,
         response: CanonicalResponse<'tcx>,
-    ) -> Result<Certainty, NoSolution> {
+    ) -> Result<(Certainty, Vec<Goal<'tcx, ty::Predicate<'tcx>>>), NoSolution> {
         let substitution = self.compute_query_response_substitution(&original_values, &response);
 
         let Response { var_values, external_constraints, certainty } =
             response.substitute(self.tcx(), &substitution);
 
-        self.unify_query_var_values(param_env, &original_values, var_values)?;
+        let nested_goals = self.unify_query_var_values(param_env, &original_values, var_values)?;
 
         // FIXME: implement external constraints.
         let ExternalConstraintsData { region_constraints, opaque_types: _ } =
             external_constraints.deref();
         self.register_region_constraints(region_constraints);
 
-        Ok(certainty)
+        Ok((certainty, nested_goals))
     }
 
     /// This returns the substitutions to instantiate the bound variables of
-    /// the canonical reponse. This depends on the `original_values` for the
+    /// the canonical response. This depends on the `original_values` for the
     /// bound variables.
     fn compute_query_response_substitution(
         &self,
@@ -185,7 +188,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
                 } else {
                     // For placeholders which were already part of the input, we simply map this
                     // universal bound variable back the placeholder of the input.
-                    original_values[info.expect_anon_placeholder() as usize]
+                    original_values[info.expect_placeholder_index()]
                 }
             },
         ));
@@ -199,35 +202,22 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
         param_env: ty::ParamEnv<'tcx>,
         original_values: &[ty::GenericArg<'tcx>],
         var_values: CanonicalVarValues<'tcx>,
-    ) -> Result<(), NoSolution> {
+    ) -> Result<Vec<Goal<'tcx, ty::Predicate<'tcx>>>, NoSolution> {
         assert_eq!(original_values.len(), var_values.len());
+
+        let mut nested_goals = vec![];
         for (&orig, response) in iter::zip(original_values, var_values.var_values) {
-            // This can fail due to the occurs check, see
-            // `tests/ui/typeck/lazy-norm/equating-projection-cyclically.rs` for an example
-            // where that can happen.
-            //
-            // FIXME: To deal with #105787 I also expect us to emit nested obligations here at
-            // some point. We can figure out how to deal with this once we actually have
-            // an ICE.
-            let nested_goals = self.eq(param_env, orig, response)?;
-            assert!(nested_goals.is_empty(), "{nested_goals:?}");
+            nested_goals.extend(self.eq_and_get_goals(param_env, orig, response)?);
         }
 
-        Ok(())
+        Ok(nested_goals)
     }
 
     fn register_region_constraints(&mut self, region_constraints: &QueryRegionConstraints<'tcx>) {
         for &(ty::OutlivesPredicate(lhs, rhs), _) in &region_constraints.outlives {
             match lhs.unpack() {
-                GenericArgKind::Lifetime(lhs) => self.infcx.region_outlives_predicate(
-                    &ObligationCause::dummy(),
-                    ty::Binder::dummy(ty::OutlivesPredicate(lhs, rhs)),
-                ),
-                GenericArgKind::Type(lhs) => self.infcx.register_region_obligation_with_cause(
-                    lhs,
-                    rhs,
-                    &ObligationCause::dummy(),
-                ),
+                GenericArgKind::Lifetime(lhs) => self.register_region_outlives(lhs, rhs),
+                GenericArgKind::Type(lhs) => self.register_ty_outlives(lhs, rhs),
                 GenericArgKind::Const(_) => bug!("const outlives: {lhs:?}: {rhs:?}"),
             }
         }
diff --git a/compiler/rustc_trait_selection/src/solve/fulfill.rs b/compiler/rustc_trait_selection/src/solve/fulfill.rs
index a55b984fd..32bd10f0b 100644
--- a/compiler/rustc_trait_selection/src/solve/fulfill.rs
+++ b/compiler/rustc_trait_selection/src/solve/fulfill.rs
@@ -1,6 +1,8 @@
 use std::mem;
 
 use rustc_infer::infer::InferCtxt;
+use rustc_infer::traits::solve::MaybeCause;
+use rustc_infer::traits::Obligation;
 use rustc_infer::traits::{
     query::NoSolution, FulfillmentError, FulfillmentErrorCode, MismatchedProjectionTypes,
     PredicateObligation, SelectionError, TraitEngine,
@@ -40,13 +42,31 @@ impl<'tcx> TraitEngine<'tcx> for FulfillmentCtxt<'tcx> {
         self.obligations.push(obligation);
     }
 
-    fn collect_remaining_errors(&mut self) -> Vec<FulfillmentError<'tcx>> {
+    fn collect_remaining_errors(&mut self, infcx: &InferCtxt<'tcx>) -> Vec<FulfillmentError<'tcx>> {
         self.obligations
             .drain(..)
-            .map(|obligation| FulfillmentError {
-                obligation: obligation.clone(),
-                code: FulfillmentErrorCode::CodeAmbiguity,
-                root_obligation: obligation,
+            .map(|obligation| {
+                let code =
+                    infcx.probe(|_| match infcx.evaluate_root_goal(obligation.clone().into()) {
+                        Ok((_, Certainty::Maybe(MaybeCause::Ambiguity), _)) => {
+                            FulfillmentErrorCode::CodeAmbiguity { overflow: false }
+                        }
+                        Ok((_, Certainty::Maybe(MaybeCause::Overflow), _)) => {
+                            FulfillmentErrorCode::CodeAmbiguity { overflow: true }
+                        }
+                        Ok((_, Certainty::Yes, _)) => {
+                            bug!("did not expect successful goal when collecting ambiguity errors")
+                        }
+                        Err(_) => {
+                            bug!("did not expect selection error when collecting ambiguity errors")
+                        }
+                    });
+
+                FulfillmentError {
+                    obligation: obligation.clone(),
+                    code,
+                    root_obligation: obligation,
+                }
             })
             .collect()
     }
@@ -61,7 +81,7 @@ impl<'tcx> TraitEngine<'tcx> for FulfillmentCtxt<'tcx> {
             let mut has_changed = false;
             for obligation in mem::take(&mut self.obligations) {
                 let goal = obligation.clone().into();
-                let (changed, certainty) = match infcx.evaluate_root_goal(goal) {
+                let (changed, certainty, nested_goals) = match infcx.evaluate_root_goal(goal) {
                     Ok(result) => result,
                     Err(NoSolution) => {
                         errors.push(FulfillmentError {
@@ -73,7 +93,7 @@ impl<'tcx> TraitEngine<'tcx> for FulfillmentCtxt<'tcx> {
                                         MismatchedProjectionTypes { err: TypeError::Mismatch },
                                     )
                                 }
-                                ty::PredicateKind::AliasEq(_, _) => {
+                                ty::PredicateKind::AliasRelate(_, _, _) => {
                                     FulfillmentErrorCode::CodeProjectionError(
                                         MismatchedProjectionTypes { err: TypeError::Mismatch },
                                     )
@@ -125,7 +145,16 @@ impl<'tcx> TraitEngine<'tcx> for FulfillmentCtxt<'tcx> {
                         continue;
                     }
                 };
-
+                // Push any nested goals that we get from unifying our canonical response
+                // with our obligation onto the fulfillment context.
+                self.obligations.extend(nested_goals.into_iter().map(|goal| {
+                    Obligation::new(
+                        infcx.tcx,
+                        obligation.cause.clone(),
+                        goal.param_env,
+                        goal.predicate,
+                    )
+                }));
                 has_changed |= changed;
                 match certainty {
                     Certainty::Yes => {}
@@ -149,6 +178,6 @@ impl<'tcx> TraitEngine<'tcx> for FulfillmentCtxt<'tcx> {
         &mut self,
         _: &InferCtxt<'tcx>,
     ) -> Vec<PredicateObligation<'tcx>> {
-        unimplemented!()
+        std::mem::take(&mut self.obligations)
     }
 }
diff --git a/compiler/rustc_trait_selection/src/solve/mod.rs b/compiler/rustc_trait_selection/src/solve/mod.rs
index 57b6a4527..19bcbd461 100644
--- a/compiler/rustc_trait_selection/src/solve/mod.rs
+++ b/compiler/rustc_trait_selection/src/solve/mod.rs
@@ -9,81 +9,45 @@
 //! FIXME(@lcnr): Write that section. If you read this before then ask me
 //! about it on zulip.
 
-// FIXME: Instead of using `infcx.canonicalize_query` we have to add a new routine which
-// preserves universes and creates a unique var (in the highest universe) for each
-// appearance of a region.
-
-// FIXME: uses of `infcx.at` need to enable deferred projection equality once that's implemented.
-
-use std::mem;
-
 use rustc_hir::def_id::DefId;
 use rustc_infer::infer::canonical::{Canonical, CanonicalVarValues};
-use rustc_infer::infer::{InferCtxt, InferOk, TyCtxtInferExt};
 use rustc_infer::traits::query::NoSolution;
-use rustc_infer::traits::Obligation;
-use rustc_middle::traits::solve::{ExternalConstraints, ExternalConstraintsData};
+use rustc_middle::traits::solve::{
+    CanonicalResponse, Certainty, ExternalConstraintsData, Goal, QueryResult, Response,
+};
 use rustc_middle::ty::{self, Ty, TyCtxt};
 use rustc_middle::ty::{
-    CoercePredicate, RegionOutlivesPredicate, SubtypePredicate, ToPredicate, TypeOutlivesPredicate,
+    CoercePredicate, RegionOutlivesPredicate, SubtypePredicate, TypeOutlivesPredicate,
 };
-use rustc_span::DUMMY_SP;
-
-use crate::solve::search_graph::OverflowHandler;
-use crate::traits::ObligationCause;
 
 mod assembly;
-mod canonical;
+mod canonicalize;
 mod eval_ctxt;
 mod fulfill;
 mod project_goals;
 mod search_graph;
 mod trait_goals;
 
-pub use eval_ctxt::EvalCtxt;
+pub use eval_ctxt::{EvalCtxt, InferCtxtEvalExt};
 pub use fulfill::FulfillmentCtxt;
 
-/// A goal is a statement, i.e. `predicate`, we want to prove
-/// given some assumptions, i.e. `param_env`.
-///
-/// Most of the time the `param_env` contains the `where`-bounds of the function
-/// we're currently typechecking while the `predicate` is some trait bound.
-#[derive(Debug, PartialEq, Eq, Clone, Copy, Hash, TypeFoldable, TypeVisitable)]
-pub struct Goal<'tcx, P> {
-    param_env: ty::ParamEnv<'tcx>,
-    predicate: P,
-}
-
-impl<'tcx, P> Goal<'tcx, P> {
-    pub fn new(
-        tcx: TyCtxt<'tcx>,
-        param_env: ty::ParamEnv<'tcx>,
-        predicate: impl ToPredicate<'tcx, P>,
-    ) -> Goal<'tcx, P> {
-        Goal { param_env, predicate: predicate.to_predicate(tcx) }
-    }
-
-    /// Updates the goal to one with a different `predicate` but the same `param_env`.
-    fn with<Q>(self, tcx: TyCtxt<'tcx>, predicate: impl ToPredicate<'tcx, Q>) -> Goal<'tcx, Q> {
-        Goal { param_env: self.param_env, predicate: predicate.to_predicate(tcx) }
-    }
-}
-
-impl<'tcx, P> From<Obligation<'tcx, P>> for Goal<'tcx, P> {
-    fn from(obligation: Obligation<'tcx, P>) -> Goal<'tcx, P> {
-        Goal { param_env: obligation.param_env, predicate: obligation.predicate }
-    }
-}
-#[derive(Debug, PartialEq, Eq, Clone, Copy, Hash, TypeFoldable, TypeVisitable)]
-pub struct Response<'tcx> {
-    pub var_values: CanonicalVarValues<'tcx>,
-    /// Additional constraints returned by this query.
-    pub external_constraints: ExternalConstraints<'tcx>,
-    pub certainty: Certainty,
+#[derive(Debug, Clone, Copy)]
+enum SolverMode {
+    /// Ordinary trait solving, using everywhere except for coherence.
+    Normal,
+    /// Trait solving during coherence. There are a few notable differences
+    /// between coherence and ordinary trait solving.
+    ///
+    /// Most importantly, trait solving during coherence must not be incomplete,
+    /// i.e. return `Err(NoSolution)` for goals for which a solution exists.
+    /// This means that we must not make any guesses or arbitrary choices.
+    Coherence,
 }
 
 trait CanonicalResponseExt {
     fn has_no_inference_or_external_constraints(&self) -> bool;
+
+    fn has_only_region_constraints(&self) -> bool;
 }
 
 impl<'tcx> CanonicalResponseExt for Canonical<'tcx, Response<'tcx>> {
@@ -92,242 +56,35 @@ impl<'tcx> CanonicalResponseExt for Canonical<'tcx, Response<'tcx>> {
             && self.value.var_values.is_identity()
             && self.value.external_constraints.opaque_types.is_empty()
     }
-}
 
-#[derive(Debug, PartialEq, Eq, Clone, Copy, Hash, TypeFoldable, TypeVisitable)]
-pub enum Certainty {
-    Yes,
-    Maybe(MaybeCause),
-}
-
-impl Certainty {
-    pub const AMBIGUOUS: Certainty = Certainty::Maybe(MaybeCause::Ambiguity);
-
-    /// When proving multiple goals using **AND**, e.g. nested obligations for an impl,
-    /// use this function to unify the certainty of these goals
-    pub fn unify_and(self, other: Certainty) -> Certainty {
-        match (self, other) {
-            (Certainty::Yes, Certainty::Yes) => Certainty::Yes,
-            (Certainty::Yes, Certainty::Maybe(_)) => other,
-            (Certainty::Maybe(_), Certainty::Yes) => self,
-            (Certainty::Maybe(MaybeCause::Overflow), Certainty::Maybe(MaybeCause::Overflow)) => {
-                Certainty::Maybe(MaybeCause::Overflow)
-            }
-            // If at least one of the goals is ambiguous, hide the overflow as the ambiguous goal
-            // may still result in failure.
-            (Certainty::Maybe(MaybeCause::Ambiguity), Certainty::Maybe(_))
-            | (Certainty::Maybe(_), Certainty::Maybe(MaybeCause::Ambiguity)) => {
-                Certainty::Maybe(MaybeCause::Ambiguity)
-            }
-        }
-    }
-}
-
-/// Why we failed to evaluate a goal.
-#[derive(Debug, PartialEq, Eq, Clone, Copy, Hash, TypeFoldable, TypeVisitable)]
-pub enum MaybeCause {
-    /// We failed due to ambiguity. This ambiguity can either
-    /// be a true ambiguity, i.e. there are multiple different answers,
-    /// or we hit a case where we just don't bother, e.g. `?x: Trait` goals.
-    Ambiguity,
-    /// We gave up due to an overflow, most often by hitting the recursion limit.
-    Overflow,
-}
-
-type CanonicalGoal<'tcx, T = ty::Predicate<'tcx>> = Canonical<'tcx, Goal<'tcx, T>>;
-type CanonicalResponse<'tcx> = Canonical<'tcx, Response<'tcx>>;
-/// The result of evaluating a canonical query.
-///
-/// FIXME: We use a different type than the existing canonical queries. This is because
-/// we need to add a `Certainty` for `overflow` and may want to restructure this code without
-/// having to worry about changes to currently used code. Once we've made progress on this
-/// solver, merge the two responses again.
-pub type QueryResult<'tcx> = Result<CanonicalResponse<'tcx>, NoSolution>;
-
-pub trait InferCtxtEvalExt<'tcx> {
-    /// Evaluates a goal from **outside** of the trait solver.
-    ///
-    /// Using this while inside of the solver is wrong as it uses a new
-    /// search graph which would break cycle detection.
-    fn evaluate_root_goal(
-        &self,
-        goal: Goal<'tcx, ty::Predicate<'tcx>>,
-    ) -> Result<(bool, Certainty), NoSolution>;
-}
-
-impl<'tcx> InferCtxtEvalExt<'tcx> for InferCtxt<'tcx> {
-    fn evaluate_root_goal(
-        &self,
-        goal: Goal<'tcx, ty::Predicate<'tcx>>,
-    ) -> Result<(bool, Certainty), NoSolution> {
-        let mut search_graph = search_graph::SearchGraph::new(self.tcx);
-
-        let result = EvalCtxt {
-            search_graph: &mut search_graph,
-            infcx: self,
-            // Only relevant when canonicalizing the response.
-            max_input_universe: ty::UniverseIndex::ROOT,
-            var_values: CanonicalVarValues::dummy(),
-            in_projection_eq_hack: false,
-        }
-        .evaluate_goal(goal);
-
-        assert!(search_graph.is_empty());
-        result
+    fn has_only_region_constraints(&self) -> bool {
+        self.value.var_values.is_identity_modulo_regions()
+            && self.value.external_constraints.opaque_types.is_empty()
     }
 }
 
 impl<'a, 'tcx> EvalCtxt<'a, 'tcx> {
-    /// The entry point of the solver.
-    ///
-    /// This function deals with (coinductive) cycles, overflow, and caching
-    /// and then calls [`EvalCtxt::compute_goal`] which contains the actual
-    /// logic of the solver.
-    ///
-    /// Instead of calling this function directly, use either [EvalCtxt::evaluate_goal]
-    /// if you're inside of the solver or [InferCtxtEvalExt::evaluate_root_goal] if you're
-    /// outside of it.
-    #[instrument(level = "debug", skip(tcx, search_graph), ret)]
-    fn evaluate_canonical_goal(
-        tcx: TyCtxt<'tcx>,
-        search_graph: &'a mut search_graph::SearchGraph<'tcx>,
-        canonical_goal: CanonicalGoal<'tcx>,
-    ) -> QueryResult<'tcx> {
-        // Deal with overflow, caching, and coinduction.
-        //
-        // The actual solver logic happens in `ecx.compute_goal`.
-        search_graph.with_new_goal(tcx, canonical_goal, |search_graph| {
-            let (ref infcx, goal, var_values) =
-                tcx.infer_ctxt().build_with_canonical(DUMMY_SP, &canonical_goal);
-            let mut ecx = EvalCtxt {
-                infcx,
-                var_values,
-                max_input_universe: canonical_goal.max_universe,
-                search_graph,
-                in_projection_eq_hack: false,
-            };
-            ecx.compute_goal(goal)
-        })
-    }
-
-    /// Recursively evaluates `goal`, returning whether any inference vars have
-    /// been constrained and the certainty of the result.
-    fn evaluate_goal(
-        &mut self,
-        goal: Goal<'tcx, ty::Predicate<'tcx>>,
-    ) -> Result<(bool, Certainty), NoSolution> {
-        let (orig_values, canonical_goal) = self.canonicalize_goal(goal);
-        let canonical_response =
-            EvalCtxt::evaluate_canonical_goal(self.tcx(), self.search_graph, canonical_goal)?;
-
-        let has_changed = !canonical_response.value.var_values.is_identity();
-        let certainty = self.instantiate_and_apply_query_response(
-            goal.param_env,
-            orig_values,
-            canonical_response,
-        )?;
-
-        // Check that rerunning this query with its inference constraints applied
-        // doesn't result in new inference constraints and has the same result.
-        //
-        // 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
-            && !self.in_projection_eq_hack
-            && !self.search_graph.in_cycle()
-        {
-            let (_orig_values, canonical_goal) = self.canonicalize_goal(goal);
-            let canonical_response =
-                EvalCtxt::evaluate_canonical_goal(self.tcx(), self.search_graph, canonical_goal)?;
-            if !canonical_response.value.var_values.is_identity() {
-                bug!("unstable result: {goal:?} {canonical_goal:?} {canonical_response:?}");
-            }
-            assert_eq!(certainty, canonical_response.value.certainty);
-        }
-
-        Ok((has_changed, certainty))
-    }
-
-    fn compute_goal(&mut self, goal: Goal<'tcx, ty::Predicate<'tcx>>) -> QueryResult<'tcx> {
-        let Goal { param_env, predicate } = goal;
-        let kind = predicate.kind();
-        if let Some(kind) = kind.no_bound_vars() {
-            match kind {
-                ty::PredicateKind::Clause(ty::Clause::Trait(predicate)) => {
-                    self.compute_trait_goal(Goal { param_env, predicate })
-                }
-                ty::PredicateKind::Clause(ty::Clause::Projection(predicate)) => {
-                    self.compute_projection_goal(Goal { param_env, predicate })
-                }
-                ty::PredicateKind::Clause(ty::Clause::TypeOutlives(predicate)) => {
-                    self.compute_type_outlives_goal(Goal { param_env, predicate })
-                }
-                ty::PredicateKind::Clause(ty::Clause::RegionOutlives(predicate)) => {
-                    self.compute_region_outlives_goal(Goal { param_env, predicate })
-                }
-                ty::PredicateKind::Clause(ty::Clause::ConstArgHasType(ct, ty)) => {
-                    self.compute_const_arg_has_type_goal(Goal { param_env, predicate: (ct, ty) })
-                }
-                ty::PredicateKind::Subtype(predicate) => {
-                    self.compute_subtype_goal(Goal { param_env, predicate })
-                }
-                ty::PredicateKind::Coerce(predicate) => {
-                    self.compute_coerce_goal(Goal { param_env, predicate })
-                }
-                ty::PredicateKind::ClosureKind(def_id, substs, kind) => self
-                    .compute_closure_kind_goal(Goal {
-                        param_env,
-                        predicate: (def_id, substs, kind),
-                    }),
-                ty::PredicateKind::ObjectSafe(trait_def_id) => {
-                    self.compute_object_safe_goal(trait_def_id)
-                }
-                ty::PredicateKind::WellFormed(arg) => {
-                    self.compute_well_formed_goal(Goal { param_env, predicate: arg })
-                }
-                ty::PredicateKind::Ambiguous => self.make_canonical_response(Certainty::AMBIGUOUS),
-                // FIXME: implement these predicates :)
-                ty::PredicateKind::ConstEvaluatable(_) | ty::PredicateKind::ConstEquate(_, _) => {
-                    self.make_canonical_response(Certainty::Yes)
-                }
-                ty::PredicateKind::TypeWellFormedFromEnv(..) => {
-                    bug!("TypeWellFormedFromEnv is only used for Chalk")
-                }
-                ty::PredicateKind::AliasEq(lhs, rhs) => {
-                    self.compute_alias_eq_goal(Goal { param_env, predicate: (lhs, rhs) })
-                }
-            }
-        } else {
-            let kind = self.infcx.instantiate_binder_with_placeholders(kind);
-            let goal = goal.with(self.tcx(), ty::Binder::dummy(kind));
-            let (_, certainty) = self.evaluate_goal(goal)?;
-            self.make_canonical_response(certainty)
-        }
-    }
-
+    #[instrument(level = "debug", skip(self))]
     fn compute_type_outlives_goal(
         &mut self,
         goal: Goal<'tcx, TypeOutlivesPredicate<'tcx>>,
     ) -> QueryResult<'tcx> {
         let ty::OutlivesPredicate(ty, lt) = goal.predicate;
-        self.infcx.register_region_obligation_with_cause(ty, lt, &ObligationCause::dummy());
-        self.make_canonical_response(Certainty::Yes)
+        self.register_ty_outlives(ty, lt);
+        self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
     }
 
+    #[instrument(level = "debug", skip(self))]
     fn compute_region_outlives_goal(
         &mut self,
         goal: Goal<'tcx, RegionOutlivesPredicate<'tcx>>,
     ) -> QueryResult<'tcx> {
-        self.infcx.region_outlives_predicate(
-            &ObligationCause::dummy(),
-            ty::Binder::dummy(goal.predicate),
-        );
-        self.make_canonical_response(Certainty::Yes)
+        let ty::OutlivesPredicate(a, b) = goal.predicate;
+        self.register_region_outlives(a, b);
+        self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
     }
 
+    #[instrument(level = "debug", skip(self))]
     fn compute_coerce_goal(
         &mut self,
         goal: Goal<'tcx, CoercePredicate<'tcx>>,
@@ -342,25 +99,20 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> {
         })
     }
 
+    #[instrument(level = "debug", skip(self))]
     fn compute_subtype_goal(
         &mut self,
         goal: Goal<'tcx, SubtypePredicate<'tcx>>,
     ) -> QueryResult<'tcx> {
         if goal.predicate.a.is_ty_var() && goal.predicate.b.is_ty_var() {
-            // FIXME: Do we want to register a subtype relation between these vars?
-            // That won't actually reflect in the query response, so it seems moot.
-            self.make_canonical_response(Certainty::AMBIGUOUS)
+            self.evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS)
         } else {
-            let InferOk { value: (), obligations } = self
-                .infcx
-                .at(&ObligationCause::dummy(), goal.param_env)
-                .sub(goal.predicate.a, goal.predicate.b)?;
-            self.evaluate_all_and_make_canonical_response(
-                obligations.into_iter().map(|pred| pred.into()).collect(),
-            )
+            self.sub(goal.param_env, goal.predicate.a, goal.predicate.b)?;
+            self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
         }
     }
 
+    #[instrument(level = "debug", skip(self))]
     fn compute_closure_kind_goal(
         &mut self,
         goal: Goal<'tcx, (DefId, ty::SubstsRef<'tcx>, ty::ClosureKind)>,
@@ -369,92 +121,154 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> {
         let found_kind = substs.as_closure().kind_ty().to_opt_closure_kind();
 
         let Some(found_kind) = found_kind else {
-            return self.make_canonical_response(Certainty::AMBIGUOUS);
+            return self.evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS);
         };
         if found_kind.extends(expected_kind) {
-            self.make_canonical_response(Certainty::Yes)
+            self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
         } else {
             Err(NoSolution)
         }
     }
 
+    #[instrument(level = "debug", skip(self))]
     fn compute_object_safe_goal(&mut self, trait_def_id: DefId) -> QueryResult<'tcx> {
         if self.tcx().check_is_object_safe(trait_def_id) {
-            self.make_canonical_response(Certainty::Yes)
+            self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
         } else {
             Err(NoSolution)
         }
     }
 
+    #[instrument(level = "debug", skip(self))]
     fn compute_well_formed_goal(
         &mut self,
         goal: Goal<'tcx, ty::GenericArg<'tcx>>,
     ) -> QueryResult<'tcx> {
-        match crate::traits::wf::unnormalized_obligations(
-            self.infcx,
-            goal.param_env,
-            goal.predicate,
-        ) {
-            Some(obligations) => self.evaluate_all_and_make_canonical_response(
-                obligations.into_iter().map(|o| o.into()).collect(),
-            ),
-            None => self.make_canonical_response(Certainty::AMBIGUOUS),
+        match self.well_formed_goals(goal.param_env, goal.predicate) {
+            Some(goals) => {
+                self.add_goals(goals);
+                self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
+            }
+            None => self.evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS),
         }
     }
 
     #[instrument(level = "debug", skip(self), ret)]
-    fn compute_alias_eq_goal(
+    fn compute_alias_relate_goal(
         &mut self,
-        goal: Goal<'tcx, (ty::Term<'tcx>, ty::Term<'tcx>)>,
+        goal: Goal<'tcx, (ty::Term<'tcx>, ty::Term<'tcx>, ty::AliasRelationDirection)>,
     ) -> QueryResult<'tcx> {
         let tcx = self.tcx();
+        // We may need to invert the alias relation direction if dealing an alias on the RHS.
+        #[derive(Debug)]
+        enum Invert {
+            No,
+            Yes,
+        }
+        let evaluate_normalizes_to =
+            |ecx: &mut EvalCtxt<'_, 'tcx>, alias, other, direction, invert| {
+                let span = tracing::span!(
+                    tracing::Level::DEBUG,
+                    "compute_alias_relate_goal(evaluate_normalizes_to)",
+                    ?alias,
+                    ?other,
+                    ?direction,
+                    ?invert
+                );
+                let _enter = span.enter();
+                let result = ecx.probe(|ecx| {
+                    let other = match direction {
+                        // This is purely an optimization.
+                        ty::AliasRelationDirection::Equate => other,
+
+                        ty::AliasRelationDirection::Subtype => {
+                            let fresh = ecx.next_term_infer_of_kind(other);
+                            let (sub, sup) = match invert {
+                                Invert::No => (fresh, other),
+                                Invert::Yes => (other, fresh),
+                            };
+                            ecx.sub(goal.param_env, sub, sup)?;
+                            fresh
+                        }
+                    };
+                    ecx.add_goal(goal.with(
+                        tcx,
+                        ty::Binder::dummy(ty::ProjectionPredicate {
+                            projection_ty: alias,
+                            term: other,
+                        }),
+                    ));
+                    ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
+                });
+                debug!(?result);
+                result
+            };
 
-        let evaluate_normalizes_to = |ecx: &mut EvalCtxt<'_, 'tcx>, alias, other| {
-            debug!("evaluate_normalizes_to(alias={:?}, other={:?})", alias, other);
-            let r = ecx.probe(|ecx| {
-                let (_, certainty) = ecx.evaluate_goal(goal.with(
-                    tcx,
-                    ty::Binder::dummy(ty::ProjectionPredicate {
-                        projection_ty: alias,
-                        term: other,
-                    }),
-                ))?;
-                ecx.make_canonical_response(certainty)
-            });
-            debug!("evaluate_normalizes_to(..) -> {:?}", r);
-            r
-        };
+        let (lhs, rhs, direction) = goal.predicate;
 
-        if goal.predicate.0.is_infer() || goal.predicate.1.is_infer() {
+        if lhs.is_infer() || rhs.is_infer() {
             bug!(
-                "`AliasEq` goal with an infer var on lhs or rhs which should have been instantiated"
+                "`AliasRelate` goal with an infer var on lhs or rhs which should have been instantiated"
             );
         }
 
-        match (
-            goal.predicate.0.to_alias_term_no_opaque(tcx),
-            goal.predicate.1.to_alias_term_no_opaque(tcx),
-        ) {
-            (None, None) => bug!("`AliasEq` goal without an alias on either lhs or rhs"),
-            (Some(alias), None) => evaluate_normalizes_to(self, alias, goal.predicate.1),
-            (None, Some(alias)) => evaluate_normalizes_to(self, alias, goal.predicate.0),
-            (Some(alias_lhs), Some(alias_rhs)) => {
-                debug!("compute_alias_eq_goal: both sides are aliases");
+        match (lhs.to_projection_term(tcx), rhs.to_projection_term(tcx)) {
+            (None, None) => bug!("`AliasRelate` goal without an alias on either lhs or rhs"),
 
-                let mut candidates = Vec::with_capacity(3);
+            // RHS is not a projection, only way this is true is if LHS normalizes-to RHS
+            (Some(alias_lhs), None) => {
+                evaluate_normalizes_to(self, alias_lhs, rhs, direction, Invert::No)
+            }
+
+            // LHS is not a projection, only way this is true is if RHS normalizes-to LHS
+            (None, Some(alias_rhs)) => {
+                evaluate_normalizes_to(self, alias_rhs, lhs, direction, Invert::Yes)
+            }
 
-                // Evaluate all 3 potential candidates for the alias' being equal
-                candidates.push(evaluate_normalizes_to(self, alias_lhs, goal.predicate.1));
-                candidates.push(evaluate_normalizes_to(self, alias_rhs, goal.predicate.0));
-                candidates.push(self.probe(|this| {
-                    debug!("compute_alias_eq_goal: alias defids are equal, equating substs");
-                    let nested_goals = this.eq(goal.param_env, alias_lhs, alias_rhs)?;
-                    this.evaluate_all_and_make_canonical_response(nested_goals)
-                }));
+            (Some(alias_lhs), Some(alias_rhs)) => {
+                debug!("both sides are aliases");
+
+                let mut candidates = Vec::new();
+                // LHS normalizes-to RHS
+                candidates.extend(
+                    evaluate_normalizes_to(self, alias_lhs, rhs, direction, Invert::No).ok(),
+                );
+                // RHS normalizes-to RHS
+                candidates.extend(
+                    evaluate_normalizes_to(self, alias_rhs, lhs, direction, Invert::Yes).ok(),
+                );
+                // Relate via substs
+                candidates.extend(
+                    self.probe(|ecx| {
+                        let span = tracing::span!(
+                            tracing::Level::DEBUG,
+                            "compute_alias_relate_goal(relate_via_substs)",
+                            ?alias_lhs,
+                            ?alias_rhs,
+                            ?direction
+                        );
+                        let _enter = span.enter();
+
+                        match direction {
+                            ty::AliasRelationDirection::Equate => {
+                                ecx.eq(goal.param_env, alias_lhs, alias_rhs)?;
+                            }
+                            ty::AliasRelationDirection::Subtype => {
+                                ecx.sub(goal.param_env, alias_lhs, alias_rhs)?;
+                            }
+                        }
 
+                        ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
+                    })
+                    .ok(),
+                );
                 debug!(?candidates);
 
-                self.try_merge_responses(candidates.into_iter())
+                if let Some(merged) = self.try_merge_responses(&candidates) {
+                    Ok(merged)
+                } else {
+                    self.flounder(&candidates)
+                }
             }
         }
     }
@@ -465,99 +279,78 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> {
         goal: Goal<'tcx, (ty::Const<'tcx>, Ty<'tcx>)>,
     ) -> QueryResult<'tcx> {
         let (ct, ty) = goal.predicate;
-        let nested_goals = self.eq(goal.param_env, ct.ty(), ty)?;
-        self.evaluate_all_and_make_canonical_response(nested_goals)
+        self.eq(goal.param_env, ct.ty(), ty)?;
+        self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
     }
 }
 
 impl<'tcx> EvalCtxt<'_, 'tcx> {
-    // Recursively evaluates a list of goals to completion, returning the certainty
-    // of all of the goals.
-    fn evaluate_all(
-        &mut self,
-        mut goals: Vec<Goal<'tcx, ty::Predicate<'tcx>>>,
-    ) -> Result<Certainty, NoSolution> {
-        let mut new_goals = Vec::new();
-        self.repeat_while_none(
-            |_| Ok(Certainty::Maybe(MaybeCause::Overflow)),
-            |this| {
-                let mut has_changed = Err(Certainty::Yes);
-                for goal in goals.drain(..) {
-                    let (changed, certainty) = match this.evaluate_goal(goal) {
-                        Ok(result) => result,
-                        Err(NoSolution) => return Some(Err(NoSolution)),
-                    };
-
-                    if changed {
-                        has_changed = Ok(());
-                    }
-
-                    match certainty {
-                        Certainty::Yes => {}
-                        Certainty::Maybe(_) => {
-                            new_goals.push(goal);
-                            has_changed = has_changed.map_err(|c| c.unify_and(certainty));
-                        }
-                    }
-                }
+    #[instrument(level = "debug", skip(self))]
+    fn set_normalizes_to_hack_goal(&mut self, goal: Goal<'tcx, ty::ProjectionPredicate<'tcx>>) {
+        assert!(
+            self.nested_goals.normalizes_to_hack_goal.is_none(),
+            "attempted to set the projection eq hack goal when one already exists"
+        );
+        self.nested_goals.normalizes_to_hack_goal = Some(goal);
+    }
 
-                match has_changed {
-                    Ok(()) => {
-                        mem::swap(&mut new_goals, &mut goals);
-                        None
-                    }
-                    Err(certainty) => Some(Ok(certainty)),
-                }
-            },
-        )
+    #[instrument(level = "debug", skip(self))]
+    fn add_goal(&mut self, goal: Goal<'tcx, ty::Predicate<'tcx>>) {
+        self.nested_goals.goals.push(goal);
     }
 
-    // Recursively evaluates a list of goals to completion, making a query response.
-    //
-    // This is just a convenient way of calling [`EvalCtxt::evaluate_all`],
-    // then [`EvalCtxt::make_canonical_response`].
-    fn evaluate_all_and_make_canonical_response(
-        &mut self,
-        goals: Vec<Goal<'tcx, ty::Predicate<'tcx>>>,
-    ) -> QueryResult<'tcx> {
-        self.evaluate_all(goals).and_then(|certainty| self.make_canonical_response(certainty))
+    #[instrument(level = "debug", skip(self, goals))]
+    fn add_goals(&mut self, goals: impl IntoIterator<Item = Goal<'tcx, ty::Predicate<'tcx>>>) {
+        let current_len = self.nested_goals.goals.len();
+        self.nested_goals.goals.extend(goals);
+        debug!("added_goals={:?}", &self.nested_goals.goals[current_len..]);
     }
 
+    /// Try to merge multiple possible ways to prove a goal, if that is not possible returns `None`.
+    ///
+    /// In this case we tend to flounder and return ambiguity by calling `[EvalCtxt::flounder]`.
+    #[instrument(level = "debug", skip(self), ret)]
     fn try_merge_responses(
         &mut self,
-        responses: impl Iterator<Item = QueryResult<'tcx>>,
-    ) -> QueryResult<'tcx> {
-        let candidates = responses.into_iter().flatten().collect::<Box<[_]>>();
-
-        if candidates.is_empty() {
-            return Err(NoSolution);
+        responses: &[CanonicalResponse<'tcx>],
+    ) -> Option<CanonicalResponse<'tcx>> {
+        if responses.is_empty() {
+            return None;
         }
 
-        // FIXME(-Ztreat-solver=next): We should instead try to find a `Certainty::Yes` response with
+        // FIXME(-Ztrait-solver=next): We should instead try to find a `Certainty::Yes` response with
         // a subset of the constraints that all the other responses have.
-        let one = candidates[0];
-        if candidates[1..].iter().all(|resp| resp == &one) {
-            return Ok(one);
+        let one = responses[0];
+        if responses[1..].iter().all(|&resp| resp == one) {
+            return Some(one);
         }
 
-        if let Some(response) = candidates.iter().find(|response| {
-            response.value.certainty == Certainty::Yes
-                && response.has_no_inference_or_external_constraints()
-        }) {
-            return Ok(*response);
-        }
+        responses
+            .iter()
+            .find(|response| {
+                response.value.certainty == Certainty::Yes
+                    && response.has_no_inference_or_external_constraints()
+            })
+            .copied()
+    }
 
-        let certainty = candidates.iter().fold(Certainty::AMBIGUOUS, |certainty, response| {
-            certainty.unify_and(response.value.certainty)
+    /// If we fail to merge responses we flounder and return overflow or ambiguity.
+    #[instrument(level = "debug", skip(self), ret)]
+    fn flounder(&mut self, responses: &[CanonicalResponse<'tcx>]) -> QueryResult<'tcx> {
+        if responses.is_empty() {
+            return Err(NoSolution);
+        }
+        let certainty = responses.iter().fold(Certainty::AMBIGUOUS, |certainty, response| {
+            certainty.unify_with(response.value.certainty)
         });
-        // FIXME(-Ztrait-solver=next): We should take the intersection of the constraints on all the
-        // responses and use that for the constraints of this ambiguous response.
-        let response = self.make_canonical_response(certainty);
-        if let Ok(response) = &response {
+
+        let response = self.evaluate_added_goals_and_make_canonical_response(certainty);
+        if let Ok(response) = response {
             assert!(response.has_no_inference_or_external_constraints());
+            Ok(response)
+        } else {
+            bug!("failed to make floundered response: {responses:?}");
         }
-
-        response
     }
 }
 
diff --git a/compiler/rustc_trait_selection/src/solve/project_goals.rs b/compiler/rustc_trait_selection/src/solve/project_goals.rs
index 33c66d072..14cb43b89 100644
--- a/compiler/rustc_trait_selection/src/solve/project_goals.rs
+++ b/compiler/rustc_trait_selection/src/solve/project_goals.rs
@@ -1,24 +1,23 @@
-use crate::traits::{specialization_graph, translate_substs};
+use crate::traits::specialization_graph;
 
-use super::assembly;
-use super::trait_goals::structural_traits;
-use super::{Certainty, EvalCtxt, Goal, QueryResult};
+use super::assembly::{self, structural_traits};
+use super::EvalCtxt;
 use rustc_errors::ErrorGuaranteed;
 use rustc_hir::def::DefKind;
 use rustc_hir::def_id::DefId;
 use rustc_hir::LangItem;
-use rustc_infer::infer::InferCtxt;
 use rustc_infer::traits::query::NoSolution;
 use rustc_infer::traits::specialization_graph::LeafDef;
 use rustc_infer::traits::Reveal;
+use rustc_middle::traits::solve::{CanonicalResponse, Certainty, Goal, QueryResult};
 use rustc_middle::ty::fast_reject::{DeepRejectCtxt, TreatParams};
 use rustc_middle::ty::ProjectionPredicate;
 use rustc_middle::ty::{self, Ty, TyCtxt};
 use rustc_middle::ty::{ToPredicate, TypeVisitableExt};
 use rustc_span::{sym, DUMMY_SP};
-use std::iter;
 
 impl<'tcx> EvalCtxt<'_, 'tcx> {
+    #[instrument(level = "debug", skip(self), ret)]
     pub(super) fn compute_projection_goal(
         &mut self,
         goal: Goal<'tcx, ProjectionPredicate<'tcx>>,
@@ -32,57 +31,12 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
         // projection cache in the solver.
         if self.term_is_fully_unconstrained(goal) {
             let candidates = self.assemble_and_evaluate_candidates(goal);
-            self.merge_candidates_and_discard_reservation_impls(candidates)
+            self.merge_candidates(candidates)
         } else {
-            let predicate = goal.predicate;
-            let unconstrained_rhs = match predicate.term.unpack() {
-                ty::TermKind::Ty(_) => self.next_ty_infer().into(),
-                ty::TermKind::Const(ct) => self.next_const_infer(ct.ty()).into(),
-            };
-            let unconstrained_predicate = ty::Clause::Projection(ProjectionPredicate {
-                projection_ty: goal.predicate.projection_ty,
-                term: unconstrained_rhs,
-            });
-            let (_has_changed, normalize_certainty) = self.in_projection_eq_hack(|this| {
-                this.evaluate_goal(goal.with(this.tcx(), unconstrained_predicate))
-            })?;
-
-            let nested_eq_goals = self.eq(goal.param_env, unconstrained_rhs, predicate.term)?;
-            let eval_certainty = self.evaluate_all(nested_eq_goals)?;
-            self.make_canonical_response(normalize_certainty.unify_and(eval_certainty))
+            self.set_normalizes_to_hack_goal(goal);
+            self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
         }
     }
-
-    /// This sets a flag used by a debug assert in [`EvalCtxt::evaluate_goal`],
-    /// see the comment in that method for more details.
-    fn in_projection_eq_hack<T>(&mut self, f: impl FnOnce(&mut Self) -> T) -> T {
-        self.in_projection_eq_hack = true;
-        let result = f(self);
-        self.in_projection_eq_hack = false;
-        result
-    }
-
-    /// After normalizing the projection to `normalized_alias` with the given
-    /// `normalization_certainty`, constrain the inference variable `term` to it
-    /// and return a query response.
-    fn eq_term_and_make_canonical_response(
-        &mut self,
-        goal: Goal<'tcx, ProjectionPredicate<'tcx>>,
-        normalization_certainty: Certainty,
-        normalized_alias: impl Into<ty::Term<'tcx>>,
-    ) -> QueryResult<'tcx> {
-        // The term of our goal should be fully unconstrained, so this should never fail.
-        //
-        // It can however be ambiguous when the `normalized_alias` contains a projection.
-        let nested_goals = self
-            .eq(goal.param_env, goal.predicate.term, normalized_alias.into())
-            .expect("failed to unify with unconstrained term");
-
-        let unify_certainty =
-            self.evaluate_all(nested_goals).expect("failed to unify with unconstrained term");
-
-        self.make_canonical_response(normalization_certainty.unify_and(unify_certainty))
-    }
 }
 
 impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> {
@@ -90,6 +44,10 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> {
         self.self_ty()
     }
 
+    fn trait_ref(self, tcx: TyCtxt<'tcx>) -> ty::TraitRef<'tcx> {
+        self.projection_ty.trait_ref(tcx)
+    }
+
     fn with_self_ty(self, tcx: TyCtxt<'tcx>, self_ty: Ty<'tcx>) -> Self {
         self.with_self_ty(tcx, self_ty)
     }
@@ -110,19 +68,14 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> {
             ecx.probe(|ecx| {
                 let assumption_projection_pred =
                     ecx.instantiate_binder_with_infer(poly_projection_pred);
-                let mut nested_goals = ecx.eq(
+                ecx.eq(
                     goal.param_env,
                     goal.predicate.projection_ty,
                     assumption_projection_pred.projection_ty,
                 )?;
-                nested_goals.extend(requirements);
-                let subst_certainty = ecx.evaluate_all(nested_goals)?;
-
-                ecx.eq_term_and_make_canonical_response(
-                    goal,
-                    subst_certainty,
-                    assumption_projection_pred.term,
-                )
+                ecx.eq(goal.param_env, goal.predicate.term, assumption_projection_pred.term)?;
+                ecx.add_goals(requirements);
+                ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
             })
         } else {
             Err(NoSolution)
@@ -138,21 +91,22 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> {
             && poly_projection_pred.projection_def_id() == goal.predicate.def_id()
         {
             ecx.probe(|ecx| {
+                let tcx = ecx.tcx();
+
                 let assumption_projection_pred =
                     ecx.instantiate_binder_with_infer(poly_projection_pred);
-                let mut nested_goals = ecx.eq(
+                ecx.eq(
                     goal.param_env,
                     goal.predicate.projection_ty,
                     assumption_projection_pred.projection_ty,
                 )?;
 
-                let tcx = ecx.tcx();
                 let ty::Dynamic(bounds, _, _) = *goal.predicate.self_ty().kind() else {
                     bug!("expected object type in `consider_object_bound_candidate`");
                 };
-                nested_goals.extend(
+                ecx.add_goals(
                     structural_traits::predicates_for_object_candidate(
-                        ecx,
+                        &ecx,
                         goal.param_env,
                         goal.predicate.projection_ty.trait_ref(tcx),
                         bounds,
@@ -160,14 +114,8 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> {
                     .into_iter()
                     .map(|pred| goal.with(tcx, pred)),
                 );
-
-                let subst_certainty = ecx.evaluate_all(nested_goals)?;
-
-                ecx.eq_term_and_make_canonical_response(
-                    goal,
-                    subst_certainty,
-                    assumption_projection_pred.term,
-                )
+                ecx.eq(goal.param_env, goal.predicate.term, assumption_projection_pred.term)?;
+                ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
             })
         } else {
             Err(NoSolution)
@@ -183,10 +131,8 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> {
 
         let goal_trait_ref = goal.predicate.projection_ty.trait_ref(tcx);
         let impl_trait_ref = tcx.impl_trait_ref(impl_def_id).unwrap();
-        let drcx = DeepRejectCtxt { treat_obligation_params: TreatParams::AsPlaceholder };
-        if iter::zip(goal_trait_ref.substs, impl_trait_ref.skip_binder().substs)
-            .any(|(goal, imp)| !drcx.generic_args_may_unify(goal, imp))
-        {
+        let drcx = DeepRejectCtxt { treat_obligation_params: TreatParams::ForLookup };
+        if !drcx.substs_refs_may_unify(goal_trait_ref.substs, impl_trait_ref.skip_binder().substs) {
             return Err(NoSolution);
         }
 
@@ -194,28 +140,27 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> {
             let impl_substs = ecx.fresh_substs_for_item(impl_def_id);
             let impl_trait_ref = impl_trait_ref.subst(tcx, impl_substs);
 
-            let mut nested_goals = ecx.eq(goal.param_env, goal_trait_ref, impl_trait_ref)?;
+            ecx.eq(goal.param_env, goal_trait_ref, impl_trait_ref)?;
+
             let where_clause_bounds = tcx
                 .predicates_of(impl_def_id)
                 .instantiate(tcx, impl_substs)
                 .predicates
                 .into_iter()
                 .map(|pred| goal.with(tcx, pred));
-
-            nested_goals.extend(where_clause_bounds);
-            let match_impl_certainty = ecx.evaluate_all(nested_goals)?;
+            ecx.add_goals(where_clause_bounds);
 
             // In case the associated item is hidden due to specialization, we have to
             // return ambiguity this would otherwise be incomplete, resulting in
             // unsoundness during coherence (#105782).
             let Some(assoc_def) = fetch_eligible_assoc_item_def(
-                ecx.infcx,
+                ecx,
                 goal.param_env,
                 goal_trait_ref,
                 goal.predicate.def_id(),
                 impl_def_id
             )? else {
-                return ecx.make_canonical_response(match_impl_certainty.unify_and(Certainty::AMBIGUOUS));
+                return ecx.evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS);
             };
 
             if !assoc_def.item.defaultness(tcx).has_value() {
@@ -240,8 +185,7 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> {
                 goal_trait_ref.def_id,
                 impl_substs,
             );
-            let substs = translate_substs(
-                ecx.infcx,
+            let substs = ecx.translate_substs(
                 goal.param_env,
                 impl_def_id,
                 impl_substs_with_gat,
@@ -262,7 +206,8 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> {
                 ty.map_bound(|ty| ty.into())
             };
 
-            ecx.eq_term_and_make_canonical_response(goal, match_impl_certainty, term.subst(tcx, substs))
+            ecx.eq(goal.param_env, goal.predicate.term, term.subst(tcx, substs))?;
+            ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
         })
     }
 
@@ -301,20 +246,31 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> {
         bug!("`PointerLike` does not have an associated type: {:?}", goal);
     }
 
+    fn consider_builtin_fn_ptr_trait_candidate(
+        _ecx: &mut EvalCtxt<'_, 'tcx>,
+        goal: Goal<'tcx, Self>,
+    ) -> QueryResult<'tcx> {
+        bug!("`FnPtr` does not have an associated type: {:?}", goal);
+    }
+
     fn consider_builtin_fn_trait_candidates(
         ecx: &mut EvalCtxt<'_, 'tcx>,
         goal: Goal<'tcx, Self>,
         goal_kind: ty::ClosureKind,
     ) -> QueryResult<'tcx> {
         let tcx = ecx.tcx();
-        let Some(tupled_inputs_and_output) =
-        structural_traits::extract_tupled_inputs_and_output_from_callable(
-            tcx,
-            goal.predicate.self_ty(),
-            goal_kind,
-        )? else {
-        return ecx.make_canonical_response(Certainty::AMBIGUOUS);
-    };
+        let tupled_inputs_and_output =
+            match structural_traits::extract_tupled_inputs_and_output_from_callable(
+                tcx,
+                goal.predicate.self_ty(),
+                goal_kind,
+            )? {
+                Some(tupled_inputs_and_output) => tupled_inputs_and_output,
+                None => {
+                    return ecx
+                        .evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS);
+                }
+            };
         let output_is_sized_pred = tupled_inputs_and_output
             .map_bound(|(_, output)| tcx.at(DUMMY_SP).mk_trait_ref(LangItem::Sized, [output]));
 
@@ -378,27 +334,21 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> {
                         LangItem::Sized,
                         [ty::GenericArg::from(goal.predicate.self_ty())],
                     ));
-
-                    let (_, is_sized_certainty) =
-                        ecx.evaluate_goal(goal.with(tcx, sized_predicate))?;
-                    return ecx.eq_term_and_make_canonical_response(
-                        goal,
-                        is_sized_certainty,
-                        tcx.types.unit,
-                    );
+                    ecx.add_goal(goal.with(tcx, sized_predicate));
+                    tcx.types.unit
                 }
 
                 ty::Adt(def, substs) if def.is_struct() => {
-                    match def.non_enum_variant().fields.last() {
+                    match def.non_enum_variant().fields.raw.last() {
                         None => tcx.types.unit,
                         Some(field_def) => {
                             let self_ty = field_def.ty(tcx, substs);
-                            let new_goal = goal.with(
+                            ecx.add_goal(goal.with(
                                 tcx,
                                 ty::Binder::dummy(goal.predicate.with_self_ty(tcx, self_ty)),
-                            );
-                            let (_, certainty) = ecx.evaluate_goal(new_goal)?;
-                            return ecx.make_canonical_response(certainty);
+                            ));
+                            return ecx
+                                .evaluate_added_goals_and_make_canonical_response(Certainty::Yes);
                         }
                     }
                 }
@@ -407,12 +357,12 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> {
                 ty::Tuple(elements) => match elements.last() {
                     None => tcx.types.unit,
                     Some(&self_ty) => {
-                        let new_goal = goal.with(
+                        ecx.add_goal(goal.with(
                             tcx,
                             ty::Binder::dummy(goal.predicate.with_self_ty(tcx, self_ty)),
-                        );
-                        let (_, certainty) = ecx.evaluate_goal(new_goal)?;
-                        return ecx.make_canonical_response(certainty);
+                        ));
+                        return ecx
+                            .evaluate_added_goals_and_make_canonical_response(Certainty::Yes);
                     }
                 },
 
@@ -425,7 +375,8 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> {
                 ),
             };
 
-            ecx.eq_term_and_make_canonical_response(goal, Certainty::Yes, metadata_ty)
+            ecx.eq(goal.param_env, goal.predicate.term, metadata_ty.into())?;
+            ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
         })
     }
 
@@ -512,7 +463,7 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> {
     fn consider_builtin_dyn_upcast_candidates(
         _ecx: &mut EvalCtxt<'_, 'tcx>,
         goal: Goal<'tcx, Self>,
-    ) -> Vec<super::CanonicalResponse<'tcx>> {
+    ) -> Vec<CanonicalResponse<'tcx>> {
         bug!("`Unsize` does not have an associated type: {:?}", goal);
     }
 
@@ -520,8 +471,65 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> {
         ecx: &mut EvalCtxt<'_, 'tcx>,
         goal: Goal<'tcx, Self>,
     ) -> QueryResult<'tcx> {
-        let discriminant = goal.predicate.self_ty().discriminant_ty(ecx.tcx());
-        ecx.probe(|ecx| ecx.eq_term_and_make_canonical_response(goal, Certainty::Yes, discriminant))
+        let self_ty = goal.predicate.self_ty();
+        let discriminant_ty = match *self_ty.kind() {
+            ty::Bool
+            | ty::Char
+            | ty::Int(..)
+            | ty::Uint(..)
+            | ty::Float(..)
+            | ty::Array(..)
+            | ty::RawPtr(..)
+            | ty::Ref(..)
+            | ty::FnDef(..)
+            | ty::FnPtr(..)
+            | ty::Closure(..)
+            | ty::Infer(ty::IntVar(..) | ty::FloatVar(..))
+            | ty::Generator(..)
+            | ty::GeneratorWitness(..)
+            | ty::GeneratorWitnessMIR(..)
+            | ty::Never
+            | ty::Foreign(..)
+            | ty::Adt(_, _)
+            | ty::Str
+            | ty::Slice(_)
+            | ty::Dynamic(_, _, _)
+            | ty::Tuple(_)
+            | ty::Error(_) => self_ty.discriminant_ty(ecx.tcx()),
+
+            // We do not call `Ty::discriminant_ty` on alias, param, or placeholder
+            // types, which return `<self_ty as DiscriminantKind>::Discriminant`
+            // (or ICE in the case of placeholders). Projecting a type to itself
+            // is never really productive.
+            ty::Alias(_, _) | ty::Param(_) | ty::Placeholder(..) => {
+                return Err(NoSolution);
+            }
+
+            ty::Infer(ty::TyVar(_) | ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_))
+            | ty::Bound(..) => bug!(
+                "unexpected self ty `{:?}` when normalizing `<T as DiscriminantKind>::Discriminant`",
+                goal.predicate.self_ty()
+            ),
+        };
+
+        ecx.probe(|ecx| {
+            ecx.eq(goal.param_env, goal.predicate.term, discriminant_ty.into())?;
+            ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
+        })
+    }
+
+    fn consider_builtin_destruct_candidate(
+        _ecx: &mut EvalCtxt<'_, 'tcx>,
+        goal: Goal<'tcx, Self>,
+    ) -> QueryResult<'tcx> {
+        bug!("`Destruct` does not have an associated type: {:?}", goal);
+    }
+
+    fn consider_builtin_transmute_candidate(
+        _ecx: &mut EvalCtxt<'_, 'tcx>,
+        goal: Goal<'tcx, Self>,
+    ) -> QueryResult<'tcx> {
+        bug!("`BikeshedIntrinsicFrom` does not have an associated type: {:?}", goal)
     }
 }
 
@@ -529,15 +537,15 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> {
 ///
 /// FIXME: We should merge these 3 implementations as it's likely that they otherwise
 /// diverge.
-#[instrument(level = "debug", skip(infcx, param_env), ret)]
+#[instrument(level = "debug", skip(ecx, param_env), ret)]
 fn fetch_eligible_assoc_item_def<'tcx>(
-    infcx: &InferCtxt<'tcx>,
+    ecx: &EvalCtxt<'_, 'tcx>,
     param_env: ty::ParamEnv<'tcx>,
     goal_trait_ref: ty::TraitRef<'tcx>,
     trait_assoc_def_id: DefId,
     impl_def_id: DefId,
 ) -> Result<Option<LeafDef>, NoSolution> {
-    let node_item = specialization_graph::assoc_def(infcx.tcx, impl_def_id, trait_assoc_def_id)
+    let node_item = specialization_graph::assoc_def(ecx.tcx(), impl_def_id, trait_assoc_def_id)
         .map_err(|ErrorGuaranteed { .. }| NoSolution)?;
 
     let eligible = if node_item.is_final() {
@@ -549,7 +557,7 @@ fn fetch_eligible_assoc_item_def<'tcx>(
         // transmute checking and polymorphic MIR optimizations could
         // get a result which isn't correct for all monomorphizations.
         if param_env.reveal() == Reveal::All {
-            let poly_trait_ref = infcx.resolve_vars_if_possible(goal_trait_ref);
+            let poly_trait_ref = ecx.resolve_vars_if_possible(goal_trait_ref);
             !poly_trait_ref.still_further_specializable()
         } else {
             debug!(?node_item.item.def_id, "not eligible due to default");
diff --git a/compiler/rustc_trait_selection/src/solve/search_graph/cache.rs b/compiler/rustc_trait_selection/src/solve/search_graph/cache.rs
index 86b13c05f..d1b4fa554 100644
--- a/compiler/rustc_trait_selection/src/solve/search_graph/cache.rs
+++ b/compiler/rustc_trait_selection/src/solve/search_graph/cache.rs
@@ -8,12 +8,10 @@
 //!
 //! FIXME(@lcnr): Write that section, feel free to ping me if you need help here
 //! before then or if I still haven't done that before January 2023.
-use super::overflow::OverflowData;
 use super::StackDepth;
-use crate::solve::{CanonicalGoal, QueryResult};
 use rustc_data_structures::fx::FxHashMap;
 use rustc_index::vec::IndexVec;
-use rustc_middle::ty::TyCtxt;
+use rustc_middle::traits::solve::{CanonicalGoal, QueryResult};
 
 rustc_index::newtype_index! {
     pub struct EntryIndex {}
@@ -98,26 +96,3 @@ impl<'tcx> ProvisionalCache<'tcx> {
         self.entries[entry_index].response
     }
 }
-
-pub(super) fn try_move_finished_goal_to_global_cache<'tcx>(
-    tcx: TyCtxt<'tcx>,
-    overflow_data: &mut OverflowData,
-    stack: &IndexVec<super::StackDepth, super::StackElem<'tcx>>,
-    goal: CanonicalGoal<'tcx>,
-    response: QueryResult<'tcx>,
-) {
-    // We move goals to the global cache if we either did not hit an overflow or if it's
-    // the root goal as that will now always hit the same overflow limit.
-    //
-    // NOTE: We cannot move any non-root goals to the global cache even if their final result
-    // isn't impacted by the overflow as that goal still has unstable query dependencies
-    // because it didn't go its full depth.
-    //
-    // FIXME(@lcnr): We could still cache subtrees which are not impacted by overflow though.
-    // Tracking that info correctly isn't trivial, so I haven't implemented it for now.
-    let should_cache_globally = !overflow_data.did_overflow() || stack.is_empty();
-    if should_cache_globally {
-        // FIXME: move the provisional entry to the global cache.
-        let _ = (tcx, goal, response);
-    }
-}
diff --git a/compiler/rustc_trait_selection/src/solve/search_graph/mod.rs b/compiler/rustc_trait_selection/src/solve/search_graph/mod.rs
index c7eb8de65..050269fa9 100644
--- a/compiler/rustc_trait_selection/src/solve/search_graph/mod.rs
+++ b/compiler/rustc_trait_selection/src/solve/search_graph/mod.rs
@@ -1,15 +1,19 @@
 mod cache;
 mod overflow;
 
+pub(super) use overflow::OverflowHandler;
+
 use self::cache::ProvisionalEntry;
-use super::{CanonicalGoal, Certainty, MaybeCause, QueryResult};
-pub(super) use crate::solve::search_graph::overflow::OverflowHandler;
 use cache::ProvisionalCache;
 use overflow::OverflowData;
 use rustc_index::vec::IndexVec;
+use rustc_middle::dep_graph::DepKind;
+use rustc_middle::traits::solve::{CanonicalGoal, Certainty, MaybeCause, QueryResult};
 use rustc_middle::ty::TyCtxt;
 use std::{collections::hash_map::Entry, mem};
 
+use super::SolverMode;
+
 rustc_index::newtype_index! {
     pub struct StackDepth {}
 }
@@ -20,6 +24,7 @@ struct StackElem<'tcx> {
 }
 
 pub(super) struct SearchGraph<'tcx> {
+    mode: SolverMode,
     /// The stack of goals currently being computed.
     ///
     /// An element is *deeper* in the stack if its index is *lower*.
@@ -29,24 +34,43 @@ pub(super) struct SearchGraph<'tcx> {
 }
 
 impl<'tcx> SearchGraph<'tcx> {
-    pub(super) fn new(tcx: TyCtxt<'tcx>) -> SearchGraph<'tcx> {
+    pub(super) fn new(tcx: TyCtxt<'tcx>, mode: SolverMode) -> SearchGraph<'tcx> {
         Self {
+            mode,
             stack: Default::default(),
             overflow_data: OverflowData::new(tcx),
             provisional_cache: ProvisionalCache::empty(),
         }
     }
 
+    pub(super) fn solver_mode(&self) -> SolverMode {
+        self.mode
+    }
+
+    /// We do not use the global cache during coherence.
+    ///
+    /// The trait solver behavior is different for coherence
+    /// so we would have to add the solver mode to the cache key.
+    /// This is probably not worth it as trait solving during
+    /// coherence tends to already be incredibly fast.
+    ///
+    /// We could add another global cache for coherence instead,
+    /// but that's effort so let's only do it if necessary.
+    pub(super) fn should_use_global_cache(&self) -> bool {
+        match self.mode {
+            SolverMode::Normal => true,
+            SolverMode::Coherence => false,
+        }
+    }
+
     pub(super) fn is_empty(&self) -> bool {
-        self.stack.is_empty()
-            && self.provisional_cache.is_empty()
-            && !self.overflow_data.did_overflow()
+        self.stack.is_empty() && self.provisional_cache.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() {
+        if let Some(stack_depth) = self.stack.last_index() {
             // Either the current goal on the stack is the root of a cycle...
             if self.stack[stack_depth].has_been_used {
                 return true;
@@ -70,8 +94,6 @@ impl<'tcx> SearchGraph<'tcx> {
         tcx: TyCtxt<'tcx>,
         goal: CanonicalGoal<'tcx>,
     ) -> Result<(), QueryResult<'tcx>> {
-        // FIXME: start by checking the global cache
-
         // Look at the provisional cache to check for cycles.
         let cache = &mut self.provisional_cache;
         match cache.lookup_table.entry(goal) {
@@ -131,7 +153,7 @@ impl<'tcx> SearchGraph<'tcx> {
     /// coinductive cycles.
     ///
     /// When we encounter a coinductive cycle, we have to prove the final result of that cycle
-    /// while we are still computing that result. Because of this we continously recompute the
+    /// while we are still computing that result. Because of this we continuously recompute the
     /// cycle until the result of the previous iteration is equal to the final result, at which
     /// point we are done.
     ///
@@ -139,10 +161,9 @@ impl<'tcx> SearchGraph<'tcx> {
     /// updated the provisional cache and we have to recompute the current goal.
     ///
     /// FIXME: Refer to the rustc-dev-guide entry once it exists.
-    #[instrument(level = "debug", skip(self, tcx, actual_goal), ret)]
+    #[instrument(level = "debug", skip(self, actual_goal), ret)]
     fn try_finalize_goal(
         &mut self,
-        tcx: TyCtxt<'tcx>,
         actual_goal: CanonicalGoal<'tcx>,
         response: QueryResult<'tcx>,
     ) -> bool {
@@ -176,72 +197,90 @@ impl<'tcx> SearchGraph<'tcx> {
             self.stack.push(StackElem { goal, has_been_used: false });
             false
         } else {
-            self.try_move_finished_goal_to_global_cache(tcx, stack_elem);
             true
         }
     }
 
-    fn try_move_finished_goal_to_global_cache(
+    pub(super) fn with_new_goal(
         &mut self,
         tcx: TyCtxt<'tcx>,
-        stack_elem: StackElem<'tcx>,
-    ) {
-        let StackElem { goal, .. } = stack_elem;
+        canonical_goal: CanonicalGoal<'tcx>,
+        mut loop_body: impl FnMut(&mut Self) -> QueryResult<'tcx>,
+    ) -> QueryResult<'tcx> {
+        if self.should_use_global_cache() {
+            if let Some(result) = tcx.new_solver_evaluation_cache.get(&canonical_goal, tcx) {
+                debug!(?canonical_goal, ?result, "cache hit");
+                return result;
+            }
+        }
+
+        match self.try_push_stack(tcx, canonical_goal) {
+            Ok(()) => {}
+            // Our goal is already on the stack, eager return.
+            Err(response) => return response,
+        }
+
+        // This is for global caching, so we properly track query dependencies.
+        // Everything that affects the `Result` should be performed within this
+        // `with_anon_task` closure.
+        let (result, dep_node) = tcx.dep_graph.with_anon_task(tcx, DepKind::TraitSelect, || {
+            self.repeat_while_none(
+                |this| {
+                    let result = this.deal_with_overflow(tcx, canonical_goal);
+                    let _ = this.stack.pop().unwrap();
+                    result
+                },
+                |this| {
+                    let result = loop_body(this);
+                    this.try_finalize_goal(canonical_goal, result).then(|| result)
+                },
+            )
+        });
+
         let cache = &mut self.provisional_cache;
-        let provisional_entry_index = *cache.lookup_table.get(&goal).unwrap();
+        let provisional_entry_index = *cache.lookup_table.get(&canonical_goal).unwrap();
         let provisional_entry = &mut cache.entries[provisional_entry_index];
         let depth = provisional_entry.depth;
 
         // If not, we're done with this goal.
         //
         // Check whether that this goal doesn't depend on a goal deeper on the stack
-        // and if so, move it and all nested goals to the global cache.
+        // and if so, move it to the global cache.
         //
         // Note that if any nested goal were to depend on something deeper on the stack,
         // this would have also updated the depth of the current goal.
         if depth == self.stack.next_index() {
-            for (i, entry) in cache.entries.drain_enumerated(provisional_entry_index.index()..) {
+            // If the current goal is the head of a cycle, we drop all other
+            // cycle participants without moving them to the global cache.
+            let other_cycle_participants = provisional_entry_index.index() + 1;
+            for (i, entry) in cache.entries.drain_enumerated(other_cycle_participants..) {
                 let actual_index = cache.lookup_table.remove(&entry.goal);
                 debug_assert_eq!(Some(i), actual_index);
                 debug_assert!(entry.depth == depth);
-                cache::try_move_finished_goal_to_global_cache(
-                    tcx,
-                    &mut self.overflow_data,
-                    &self.stack,
-                    entry.goal,
-                    entry.response,
-                );
             }
-        }
-    }
 
-    pub(super) fn with_new_goal(
-        &mut self,
-        tcx: TyCtxt<'tcx>,
-        canonical_goal: CanonicalGoal<'tcx>,
-        mut loop_body: impl FnMut(&mut Self) -> QueryResult<'tcx>,
-    ) -> QueryResult<'tcx> {
-        match self.try_push_stack(tcx, canonical_goal) {
-            Ok(()) => {}
-            // Our goal is already on the stack, eager return.
-            Err(response) => return response,
+            let current_goal = cache.entries.pop().unwrap();
+            let actual_index = cache.lookup_table.remove(&current_goal.goal);
+            debug_assert_eq!(Some(provisional_entry_index), actual_index);
+            debug_assert!(current_goal.depth == depth);
+
+            // We move the root goal to the global cache if we either did not hit an overflow or if it's
+            // the root goal as that will now always hit the same overflow limit.
+            //
+            // NOTE: We cannot move any non-root goals to the global cache. When replaying the root goal's
+            // dependencies, our non-root goal may no longer appear as child of the root goal.
+            //
+            // See https://github.com/rust-lang/rust/pull/108071 for some additional context.
+            let can_cache = !self.overflow_data.did_overflow() || self.stack.is_empty();
+            if self.should_use_global_cache() && can_cache {
+                tcx.new_solver_evaluation_cache.insert(
+                    current_goal.goal,
+                    dep_node,
+                    current_goal.response,
+                );
+            }
         }
 
-        self.repeat_while_none(
-            |this| {
-                let result = this.deal_with_overflow(tcx, canonical_goal);
-                let stack_elem = this.stack.pop().unwrap();
-                this.try_move_finished_goal_to_global_cache(tcx, stack_elem);
-                result
-            },
-            |this| {
-                let result = loop_body(this);
-                if this.try_finalize_goal(tcx, canonical_goal, result) {
-                    Some(result)
-                } else {
-                    None
-                }
-            },
-        )
+        result
     }
 }
diff --git a/compiler/rustc_trait_selection/src/solve/search_graph/overflow.rs b/compiler/rustc_trait_selection/src/solve/search_graph/overflow.rs
index 56409b060..e0a2e0c5c 100644
--- a/compiler/rustc_trait_selection/src/solve/search_graph/overflow.rs
+++ b/compiler/rustc_trait_selection/src/solve/search_graph/overflow.rs
@@ -1,10 +1,11 @@
 use rustc_infer::infer::canonical::Canonical;
 use rustc_infer::traits::query::NoSolution;
+use rustc_middle::traits::solve::{Certainty, MaybeCause, QueryResult};
 use rustc_middle::ty::TyCtxt;
 use rustc_session::Limit;
 
 use super::SearchGraph;
-use crate::solve::{response_no_constraints, Certainty, EvalCtxt, MaybeCause, QueryResult};
+use crate::solve::{response_no_constraints, EvalCtxt};
 
 /// When detecting a solver overflow, we return ambiguity. Overflow can be
 /// *hidden* by either a fatal error in an **AND** or a trivial success in an **OR**.
@@ -44,7 +45,7 @@ impl OverflowData {
     /// Updating the current limit when hitting overflow.
     fn deal_with_overflow(&mut self) {
         // When first hitting overflow we reduce the overflow limit
-        // for all future goals to prevent hangs if there's an exponental
+        // for all future goals to prevent hangs if there's an exponential
         // blowup.
         self.current_limit.0 = self.default_limit.0 / 8;
     }
@@ -72,6 +73,27 @@ pub(in crate::solve) trait OverflowHandler<'tcx> {
         self.search_graph().overflow_data.deal_with_overflow();
         on_overflow(self)
     }
+
+    // Increment the `additional_depth` by one and evaluate `body`, or `on_overflow`
+    // if the depth is overflown.
+    fn with_incremented_depth<T>(
+        &mut self,
+        on_overflow: impl FnOnce(&mut Self) -> T,
+        body: impl FnOnce(&mut Self) -> T,
+    ) -> T {
+        let depth = self.search_graph().stack.len();
+        self.search_graph().overflow_data.additional_depth += 1;
+
+        let result = if self.search_graph().overflow_data.has_overflow(depth) {
+            self.search_graph().overflow_data.deal_with_overflow();
+            on_overflow(self)
+        } else {
+            body(self)
+        };
+
+        self.search_graph().overflow_data.additional_depth -= 1;
+        result
+    }
 }
 
 impl<'tcx> OverflowHandler<'tcx> for EvalCtxt<'_, 'tcx> {
diff --git a/compiler/rustc_trait_selection/src/solve/trait_goals.rs b/compiler/rustc_trait_selection/src/solve/trait_goals.rs
index 5c499c36e..abd11a15a 100644
--- a/compiler/rustc_trait_selection/src/solve/trait_goals.rs
+++ b/compiler/rustc_trait_selection/src/solve/trait_goals.rs
@@ -1,25 +1,26 @@
 //! Dealing with trait goals, i.e. `T: Trait<'a, U>`.
 
-use std::iter;
-
-use super::assembly;
-use super::{CanonicalResponse, Certainty, EvalCtxt, Goal, QueryResult};
+use super::assembly::{self, structural_traits};
+use super::{EvalCtxt, SolverMode};
 use rustc_hir::def_id::DefId;
-use rustc_hir::LangItem;
+use rustc_hir::{LangItem, Movability};
 use rustc_infer::traits::query::NoSolution;
 use rustc_infer::traits::util::supertraits;
-use rustc_middle::ty::fast_reject::{DeepRejectCtxt, TreatParams};
+use rustc_middle::traits::solve::{CanonicalResponse, Certainty, Goal, QueryResult};
+use rustc_middle::ty::fast_reject::{DeepRejectCtxt, TreatParams, TreatProjections};
 use rustc_middle::ty::{self, ToPredicate, Ty, TyCtxt};
 use rustc_middle::ty::{TraitPredicate, TypeVisitableExt};
 use rustc_span::DUMMY_SP;
 
-pub mod structural_traits;
-
 impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> {
     fn self_ty(self) -> Ty<'tcx> {
         self.self_ty()
     }
 
+    fn trait_ref(self, _: TyCtxt<'tcx>) -> ty::TraitRef<'tcx> {
+        self.trait_ref
+    }
+
     fn with_self_ty(self, tcx: TyCtxt<'tcx>, self_ty: Ty<'tcx>) -> Self {
         self.with_self_ty(tcx, self_ty)
     }
@@ -36,27 +37,44 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> {
         let tcx = ecx.tcx();
 
         let impl_trait_ref = tcx.impl_trait_ref(impl_def_id).unwrap();
-        let drcx = DeepRejectCtxt { treat_obligation_params: TreatParams::AsPlaceholder };
-        if iter::zip(goal.predicate.trait_ref.substs, impl_trait_ref.skip_binder().substs)
-            .any(|(goal, imp)| !drcx.generic_args_may_unify(goal, imp))
-        {
+        let drcx = DeepRejectCtxt { treat_obligation_params: TreatParams::ForLookup };
+        if !drcx.substs_refs_may_unify(
+            goal.predicate.trait_ref.substs,
+            impl_trait_ref.skip_binder().substs,
+        ) {
             return Err(NoSolution);
         }
 
+        let impl_polarity = tcx.impl_polarity(impl_def_id);
+        // An upper bound of the certainty of this goal, used to lower the certainty
+        // of reservation impl to ambiguous during coherence.
+        let maximal_certainty = match impl_polarity {
+            ty::ImplPolarity::Positive | ty::ImplPolarity::Negative => {
+                match impl_polarity == goal.predicate.polarity {
+                    true => Certainty::Yes,
+                    false => return Err(NoSolution),
+                }
+            }
+            ty::ImplPolarity::Reservation => match ecx.solver_mode() {
+                SolverMode::Normal => return Err(NoSolution),
+                SolverMode::Coherence => Certainty::AMBIGUOUS,
+            },
+        };
+
         ecx.probe(|ecx| {
             let impl_substs = ecx.fresh_substs_for_item(impl_def_id);
             let impl_trait_ref = impl_trait_ref.subst(tcx, impl_substs);
 
-            let mut nested_goals =
-                ecx.eq(goal.param_env, goal.predicate.trait_ref, impl_trait_ref)?;
+            ecx.eq(goal.param_env, goal.predicate.trait_ref, impl_trait_ref)?;
             let where_clause_bounds = tcx
                 .predicates_of(impl_def_id)
                 .instantiate(tcx, impl_substs)
                 .predicates
                 .into_iter()
                 .map(|pred| goal.with(tcx, pred));
-            nested_goals.extend(where_clause_bounds);
-            ecx.evaluate_all_and_make_canonical_response(nested_goals)
+            ecx.add_goals(where_clause_bounds);
+
+            ecx.evaluate_added_goals_and_make_canonical_response(maximal_certainty)
         })
     }
 
@@ -73,13 +91,13 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> {
             ecx.probe(|ecx| {
                 let assumption_trait_pred =
                     ecx.instantiate_binder_with_infer(poly_trait_pred);
-                let mut nested_goals = ecx.eq(
+                ecx.eq(
                     goal.param_env,
                     goal.predicate.trait_ref,
                     assumption_trait_pred.trait_ref,
                 )?;
-                nested_goals.extend(requirements);
-                ecx.evaluate_all_and_make_canonical_response(nested_goals)
+                ecx.add_goals(requirements);
+                ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
             })
         } else {
             Err(NoSolution)
@@ -98,7 +116,7 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> {
             ecx.probe(|ecx| {
                 let assumption_trait_pred =
                     ecx.instantiate_binder_with_infer(poly_trait_pred);
-                let mut nested_goals = ecx.eq(
+                ecx.eq(
                     goal.param_env,
                     goal.predicate.trait_ref,
                     assumption_trait_pred.trait_ref,
@@ -108,9 +126,9 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> {
                 let ty::Dynamic(bounds, _, _) = *goal.predicate.self_ty().kind() else {
                     bug!("expected object type in `consider_object_bound_candidate`");
                 };
-                nested_goals.extend(
+                ecx.add_goals(
                     structural_traits::predicates_for_object_candidate(
-                        ecx,
+                        &ecx,
                         goal.param_env,
                         goal.predicate.trait_ref,
                         bounds,
@@ -118,8 +136,7 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> {
                     .into_iter()
                     .map(|pred| goal.with(tcx, pred)),
                 );
-
-                ecx.evaluate_all_and_make_canonical_response(nested_goals)
+                ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
             })
         } else {
             Err(NoSolution)
@@ -130,18 +147,8 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> {
         ecx: &mut EvalCtxt<'_, 'tcx>,
         goal: Goal<'tcx, Self>,
     ) -> QueryResult<'tcx> {
-        // This differs from the current stable behavior and
-        // fixes #84857. Due to breakage found via crater, we
-        // currently instead lint patterns which can be used to
-        // exploit this unsoundness on stable, see #93367 for
-        // more details.
-        if let Some(def_id) = ecx.tcx().find_map_relevant_impl(
-            goal.predicate.def_id(),
-            goal.predicate.self_ty(),
-            Some,
-        ) {
-            debug!(?def_id, ?goal, "disqualified auto-trait implementation");
-            return Err(NoSolution);
+        if let Some(result) = ecx.disqualify_auto_trait_candidate_due_to_possible_impl(goal) {
+            return result;
         }
 
         ecx.probe_and_evaluate_goal_for_constituent_tys(
@@ -160,9 +167,8 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> {
             let nested_obligations = tcx
                 .predicates_of(goal.predicate.def_id())
                 .instantiate(tcx, goal.predicate.trait_ref.substs);
-            ecx.evaluate_all_and_make_canonical_response(
-                nested_obligations.predicates.into_iter().map(|p| goal.with(tcx, p)).collect(),
-            )
+            ecx.add_goals(nested_obligations.predicates.into_iter().map(|p| goal.with(tcx, p)));
+            ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
         })
     }
 
@@ -191,19 +197,28 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> {
         goal: Goal<'tcx, Self>,
     ) -> QueryResult<'tcx> {
         if goal.predicate.self_ty().has_non_region_infer() {
-            return ecx.make_canonical_response(Certainty::AMBIGUOUS);
+            return ecx.evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS);
         }
 
         let tcx = ecx.tcx();
         let self_ty = tcx.erase_regions(goal.predicate.self_ty());
 
         if let Ok(layout) = tcx.layout_of(goal.param_env.and(self_ty))
-            &&  let usize_layout = tcx.layout_of(ty::ParamEnv::empty().and(tcx.types.usize)).unwrap().layout
-            && layout.layout.size() == usize_layout.size()
-            && layout.layout.align().abi == usize_layout.align().abi
+            && layout.layout.is_pointer_like(&tcx.data_layout)
         {
             // FIXME: We could make this faster by making a no-constraints response
-            ecx.make_canonical_response(Certainty::Yes)
+            ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
+        } else {
+            Err(NoSolution)
+        }
+    }
+
+    fn consider_builtin_fn_ptr_trait_candidate(
+        ecx: &mut EvalCtxt<'_, 'tcx>,
+        goal: Goal<'tcx, Self>,
+    ) -> QueryResult<'tcx> {
+        if let ty::FnPtr(..) = goal.predicate.self_ty().kind() {
+            ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
         } else {
             Err(NoSolution)
         }
@@ -215,14 +230,18 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> {
         goal_kind: ty::ClosureKind,
     ) -> QueryResult<'tcx> {
         let tcx = ecx.tcx();
-        let Some(tupled_inputs_and_output) =
-            structural_traits::extract_tupled_inputs_and_output_from_callable(
+        let tupled_inputs_and_output =
+            match structural_traits::extract_tupled_inputs_and_output_from_callable(
                 tcx,
                 goal.predicate.self_ty(),
                 goal_kind,
-            )? else {
-            return ecx.make_canonical_response(Certainty::AMBIGUOUS);
-        };
+            )? {
+                Some(a) => a,
+                None => {
+                    return ecx
+                        .evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS);
+                }
+            };
         let output_is_sized_pred = tupled_inputs_and_output
             .map_bound(|(_, output)| tcx.at(DUMMY_SP).mk_trait_ref(LangItem::Sized, [output]));
 
@@ -241,7 +260,7 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> {
         goal: Goal<'tcx, Self>,
     ) -> QueryResult<'tcx> {
         if let ty::Tuple(..) = goal.predicate.self_ty().kind() {
-            ecx.make_canonical_response(Certainty::Yes)
+            ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
         } else {
             Err(NoSolution)
         }
@@ -251,7 +270,7 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> {
         ecx: &mut EvalCtxt<'_, 'tcx>,
         _goal: Goal<'tcx, Self>,
     ) -> QueryResult<'tcx> {
-        ecx.make_canonical_response(Certainty::Yes)
+        ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
     }
 
     fn consider_builtin_future_candidate(
@@ -271,7 +290,7 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> {
         // Async generator unconditionally implement `Future`
         // Technically, we need to check that the future output type is Sized,
         // but that's already proven by the generator being WF.
-        ecx.make_canonical_response(Certainty::Yes)
+        ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
     }
 
     fn consider_builtin_generator_candidate(
@@ -311,7 +330,7 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> {
         let a_ty = goal.predicate.self_ty();
         let b_ty = goal.predicate.trait_ref.substs.type_at(1);
         if b_ty.is_ty_var() {
-            return ecx.make_canonical_response(Certainty::AMBIGUOUS);
+            return ecx.evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS);
         }
         ecx.probe(|ecx| {
             match (a_ty.kind(), b_ty.kind()) {
@@ -320,7 +339,7 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> {
                     // Dyn upcasting is handled separately, since due to upcasting,
                     // when there are two supertraits that differ by substs, we
                     // may return more than one query response.
-                    return Err(NoSolution);
+                    Err(NoSolution)
                 }
                 // `T` -> `dyn Trait` unsizing
                 (_, &ty::Dynamic(data, region, ty::Dyn)) => {
@@ -335,29 +354,26 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> {
                     let Some(sized_def_id) = tcx.lang_items().sized_trait() else {
                         return Err(NoSolution);
                     };
-                    let nested_goals: Vec<_> = data
-                        .iter()
-                        // Check that the type implements all of the predicates of the def-id.
-                        // (i.e. the principal, all of the associated types match, and any auto traits)
-                        .map(|pred| goal.with(tcx, pred.with_self_ty(tcx, a_ty)))
-                        .chain([
-                            // The type must be Sized to be unsized.
-                            goal.with(
-                                tcx,
-                                ty::Binder::dummy(tcx.mk_trait_ref(sized_def_id, [a_ty])),
-                            ),
-                            // The type must outlive the lifetime of the `dyn` we're unsizing into.
-                            goal.with(tcx, ty::Binder::dummy(ty::OutlivesPredicate(a_ty, region))),
-                        ])
-                        .collect();
-
-                    ecx.evaluate_all_and_make_canonical_response(nested_goals)
+                    // Check that the type implements all of the predicates of the def-id.
+                    // (i.e. the principal, all of the associated types match, and any auto traits)
+                    ecx.add_goals(
+                        data.iter().map(|pred| goal.with(tcx, pred.with_self_ty(tcx, a_ty))),
+                    );
+                    // The type must be Sized to be unsized.
+                    ecx.add_goal(
+                        goal.with(tcx, ty::Binder::dummy(tcx.mk_trait_ref(sized_def_id, [a_ty]))),
+                    );
+                    // The type must outlive the lifetime of the `dyn` we're unsizing into.
+                    ecx.add_goal(
+                        goal.with(tcx, ty::Binder::dummy(ty::OutlivesPredicate(a_ty, region))),
+                    );
+                    ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
                 }
                 // `[T; n]` -> `[T]` unsizing
                 (&ty::Array(a_elem_ty, ..), &ty::Slice(b_elem_ty)) => {
                     // We just require that the element type stays the same
-                    let nested_goals = ecx.eq(goal.param_env, a_elem_ty, b_elem_ty)?;
-                    ecx.evaluate_all_and_make_canonical_response(nested_goals)
+                    ecx.eq(goal.param_env, a_elem_ty, b_elem_ty)?;
+                    ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
                 }
                 // Struct unsizing `Struct<T>` -> `Struct<U>` where `T: Unsize<U>`
                 (&ty::Adt(a_def, a_substs), &ty::Adt(b_def, b_substs))
@@ -373,6 +389,7 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> {
                     let tail_field = a_def
                         .non_enum_variant()
                         .fields
+                        .raw
                         .last()
                         .expect("expected unsized ADT to have a tail field");
                     let tail_field_ty = tcx.type_of(tail_field.did);
@@ -391,15 +408,14 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> {
 
                     // Finally, we require that `TailA: Unsize<TailB>` for the tail field
                     // types.
-                    let mut nested_goals = ecx.eq(goal.param_env, unsized_a_ty, b_ty)?;
-                    nested_goals.push(goal.with(
+                    ecx.eq(goal.param_env, unsized_a_ty, b_ty)?;
+                    ecx.add_goal(goal.with(
                         tcx,
                         ty::Binder::dummy(
                             tcx.mk_trait_ref(goal.predicate.def_id(), [a_tail_ty, b_tail_ty]),
                         ),
                     ));
-
-                    ecx.evaluate_all_and_make_canonical_response(nested_goals)
+                    ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
                 }
                 // Tuple unsizing `(.., T)` -> `(.., U)` where `T: Unsize<U>`
                 (&ty::Tuple(a_tys), &ty::Tuple(b_tys))
@@ -411,17 +427,16 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> {
                     // Substitute just the tail field of B., and require that they're equal.
                     let unsized_a_ty =
                         tcx.mk_tup_from_iter(a_rest_tys.iter().chain([b_last_ty]).copied());
-                    let mut nested_goals = ecx.eq(goal.param_env, unsized_a_ty, b_ty)?;
+                    ecx.eq(goal.param_env, unsized_a_ty, b_ty)?;
 
                     // Similar to ADTs, require that the rest of the fields are equal.
-                    nested_goals.push(goal.with(
+                    ecx.add_goal(goal.with(
                         tcx,
                         ty::Binder::dummy(
                             tcx.mk_trait_ref(goal.predicate.def_id(), [*a_last_ty, *b_last_ty]),
                         ),
                     ));
-
-                    ecx.evaluate_all_and_make_canonical_response(nested_goals)
+                    ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
                 }
                 _ => Err(NoSolution),
             }
@@ -471,12 +486,11 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> {
                 let new_a_ty = tcx.mk_dynamic(new_a_data, b_region, ty::Dyn);
 
                 // We also require that A's lifetime outlives B's lifetime.
-                let mut nested_obligations = ecx.eq(goal.param_env, new_a_ty, b_ty)?;
-                nested_obligations.push(
+                ecx.eq(goal.param_env, new_a_ty, b_ty)?;
+                ecx.add_goal(
                     goal.with(tcx, ty::Binder::dummy(ty::OutlivesPredicate(a_region, b_region))),
                 );
-
-                ecx.evaluate_all_and_make_canonical_response(nested_obligations)
+                ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
             })
         };
 
@@ -510,11 +524,145 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> {
         _goal: Goal<'tcx, Self>,
     ) -> QueryResult<'tcx> {
         // `DiscriminantKind` is automatically implemented for every type.
-        ecx.make_canonical_response(Certainty::Yes)
+        ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
+    }
+
+    fn consider_builtin_destruct_candidate(
+        ecx: &mut EvalCtxt<'_, 'tcx>,
+        goal: Goal<'tcx, Self>,
+    ) -> QueryResult<'tcx> {
+        if !goal.param_env.is_const() {
+            // `Destruct` is automatically implemented for every type in
+            // non-const environments.
+            ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
+        } else {
+            // FIXME(-Ztrait-solver=next): Implement this when we get const working in the new solver
+            Err(NoSolution)
+        }
+    }
+
+    fn consider_builtin_transmute_candidate(
+        ecx: &mut EvalCtxt<'_, 'tcx>,
+        goal: Goal<'tcx, Self>,
+    ) -> QueryResult<'tcx> {
+        // `rustc_transmute` does not have support for type or const params
+        if goal.has_non_region_placeholders() {
+            return Err(NoSolution);
+        }
+
+        // Erase regions because we compute layouts in `rustc_transmute`,
+        // which will ICE for region vars.
+        let substs = ecx.tcx().erase_regions(goal.predicate.trait_ref.substs);
+
+        let Some(assume) = rustc_transmute::Assume::from_const(
+            ecx.tcx(),
+            goal.param_env,
+            substs.const_at(3),
+        ) else {
+            return Err(NoSolution);
+        };
+
+        let certainty = ecx.is_transmutable(
+            rustc_transmute::Types { dst: substs.type_at(0), src: substs.type_at(1) },
+            substs.type_at(2),
+            assume,
+        )?;
+        ecx.evaluate_added_goals_and_make_canonical_response(certainty)
     }
 }
 
 impl<'tcx> EvalCtxt<'_, 'tcx> {
+    // Return `Some` if there is an impl (built-in or user provided) that may
+    // hold for the self type of the goal, which for coherence and soundness
+    // purposes must disqualify the built-in auto impl assembled by considering
+    // the type's constituent types.
+    fn disqualify_auto_trait_candidate_due_to_possible_impl(
+        &mut self,
+        goal: Goal<'tcx, TraitPredicate<'tcx>>,
+    ) -> Option<QueryResult<'tcx>> {
+        let self_ty = goal.predicate.self_ty();
+        match *self_ty.kind() {
+            // Stall int and float vars until they are resolved to a concrete
+            // numerical type. That's because the check for impls below treats
+            // int vars as matching any impl. Even if we filtered such impls,
+            // we probably don't want to treat an `impl !AutoTrait for i32` as
+            // disqualifying the built-in auto impl for `i64: AutoTrait` either.
+            ty::Infer(ty::IntVar(_) | ty::FloatVar(_)) => {
+                Some(self.evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS))
+            }
+
+            // These types cannot be structurally decomposed into constitutent
+            // types, and therefore have no built-in auto impl.
+            ty::Dynamic(..)
+            | ty::Param(..)
+            | ty::Foreign(..)
+            | ty::Alias(ty::Projection, ..)
+            | ty::Placeholder(..) => Some(Err(NoSolution)),
+
+            ty::Infer(_) | ty::Bound(_, _) => bug!("unexpected type `{self_ty}`"),
+
+            // Generators have one special built-in candidate, `Unpin`, which
+            // takes precedence over the structural auto trait candidate being
+            // assembled.
+            ty::Generator(_, _, movability)
+                if Some(goal.predicate.def_id()) == self.tcx().lang_items().unpin_trait() =>
+            {
+                match movability {
+                    Movability::Static => Some(Err(NoSolution)),
+                    Movability::Movable => {
+                        Some(self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes))
+                    }
+                }
+            }
+
+            // For rigid types, any possible implementation that could apply to
+            // the type (even if after unification and processing nested goals
+            // it does not hold) will disqualify the built-in auto impl.
+            //
+            // This differs from the current stable behavior and fixes #84857.
+            // Due to breakage found via crater, we currently instead lint
+            // patterns which can be used to exploit this unsoundness on stable,
+            // see #93367 for more details.
+            ty::Bool
+            | ty::Char
+            | ty::Int(_)
+            | ty::Uint(_)
+            | ty::Float(_)
+            | ty::Str
+            | ty::Array(_, _)
+            | ty::Slice(_)
+            | ty::RawPtr(_)
+            | ty::Ref(_, _, _)
+            | ty::FnDef(_, _)
+            | ty::FnPtr(_)
+            | ty::Closure(_, _)
+            | ty::Generator(_, _, _)
+            | ty::GeneratorWitness(_)
+            | ty::GeneratorWitnessMIR(_, _)
+            | ty::Never
+            | ty::Tuple(_)
+            | ty::Adt(_, _)
+            // FIXME: Handling opaques here is kinda sus. Especially because we
+            // simplify them to PlaceholderSimplifiedType.
+            | ty::Alias(ty::Opaque, _) => {
+                if let Some(def_id) = self.tcx().find_map_relevant_impl(
+                    goal.predicate.def_id(),
+                    goal.predicate.self_ty(),
+                    TreatProjections::NextSolverLookup,
+                    Some,
+                ) {
+                    debug!(?def_id, ?goal, "disqualified auto-trait implementation");
+                    // No need to actually consider the candidate here,
+                    // since we do that in `consider_impl_candidate`.
+                    return Some(Err(NoSolution));
+                } else {
+                    None
+                }
+            }
+            ty::Error(_) => None,
+        }
+    }
+
     /// Convenience function for traits that are structural, i.e. that only
     /// have nested subgoals that only change the self type. Unlike other
     /// evaluate-like helpers, this does a probe, so it doesn't need to be
@@ -524,26 +672,28 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
         goal: Goal<'tcx, TraitPredicate<'tcx>>,
         constituent_tys: impl Fn(&EvalCtxt<'_, 'tcx>, Ty<'tcx>) -> Result<Vec<Ty<'tcx>>, NoSolution>,
     ) -> QueryResult<'tcx> {
-        self.probe(|this| {
-            this.evaluate_all_and_make_canonical_response(
-                constituent_tys(this, goal.predicate.self_ty())?
+        self.probe(|ecx| {
+            ecx.add_goals(
+                constituent_tys(ecx, goal.predicate.self_ty())?
                     .into_iter()
                     .map(|ty| {
                         goal.with(
-                            this.tcx(),
-                            ty::Binder::dummy(goal.predicate.with_self_ty(this.tcx(), ty)),
+                            ecx.tcx(),
+                            ty::Binder::dummy(goal.predicate.with_self_ty(ecx.tcx(), ty)),
                         )
                     })
-                    .collect(),
-            )
+                    .collect::<Vec<_>>(),
+            );
+            ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
         })
     }
 
+    #[instrument(level = "debug", skip(self))]
     pub(super) fn compute_trait_goal(
         &mut self,
         goal: Goal<'tcx, TraitPredicate<'tcx>>,
     ) -> QueryResult<'tcx> {
         let candidates = self.assemble_and_evaluate_candidates(goal);
-        self.merge_candidates_and_discard_reservation_impls(candidates)
+        self.merge_candidates(candidates)
     }
 }