Merging upstream version 1.71.1+dfsg1.

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

12 files changed, 728 insertions, 267 deletions

diff --git a/compiler/rustc_trait_selection/src/solve/assembly/mod.rs b/compiler/rustc_trait_selection/src/solve/assembly/mod.rs
index 10d817f75..f32ff0442 100644
--- a/compiler/rustc_trait_selection/src/solve/assembly/mod.rs
+++ b/compiler/rustc_trait_selection/src/solve/assembly/mod.rs
@@ -2,12 +2,12 @@
 
 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;
+use rustc_infer::traits::Reveal;
 use rustc_middle::traits::solve::{CanonicalResponse, Certainty, Goal, MaybeCause, QueryResult};
 use rustc_middle::ty::fast_reject::TreatProjections;
 use rustc_middle::ty::TypeFoldable;
@@ -51,7 +51,7 @@ pub(super) enum CandidateSource {
     BuiltinImpl,
     /// An assumption from the environment.
     ///
-    /// More precicely we've used the `n-th` assumption in the `param_env`.
+    /// More precisely we've used the `n-th` assumption in the `param_env`.
     ///
     /// ## Examples
     ///
@@ -87,7 +87,9 @@ pub(super) enum CandidateSource {
 }
 
 /// Methods used to assemble candidates for either trait or projection goals.
-pub(super) trait GoalKind<'tcx>: TypeFoldable<TyCtxt<'tcx>> + Copy + Eq {
+pub(super) trait GoalKind<'tcx>:
+    TypeFoldable<TyCtxt<'tcx>> + Copy + Eq + std::fmt::Display
+{
     fn self_ty(self) -> Ty<'tcx>;
 
     fn trait_ref(self, tcx: TyCtxt<'tcx>) -> ty::TraitRef<'tcx>;
@@ -96,6 +98,17 @@ pub(super) trait GoalKind<'tcx>: TypeFoldable<TyCtxt<'tcx>> + Copy + Eq {
 
     fn trait_def_id(self, tcx: TyCtxt<'tcx>) -> DefId;
 
+    // Try equating an assumption predicate against a goal's predicate. If it
+    // holds, then execute the `then` callback, which should do any additional
+    // work, then produce a response (typically by executing
+    // [`EvalCtxt::evaluate_added_goals_and_make_canonical_response`]).
+    fn probe_and_match_goal_against_assumption(
+        ecx: &mut EvalCtxt<'_, 'tcx>,
+        goal: Goal<'tcx, Self>,
+        assumption: ty::Predicate<'tcx>,
+        then: impl FnOnce(&mut EvalCtxt<'_, 'tcx>) -> QueryResult<'tcx>,
+    ) -> QueryResult<'tcx>;
+
     // Consider a clause, which consists of a "assumption" and some "requirements",
     // to satisfy a goal. If the requirements hold, then attempt to satisfy our
     // goal by equating it with the assumption.
@@ -104,7 +117,26 @@ pub(super) trait GoalKind<'tcx>: TypeFoldable<TyCtxt<'tcx>> + Copy + Eq {
         goal: Goal<'tcx, Self>,
         assumption: ty::Predicate<'tcx>,
         requirements: impl IntoIterator<Item = Goal<'tcx, ty::Predicate<'tcx>>>,
-    ) -> QueryResult<'tcx>;
+    ) -> QueryResult<'tcx> {
+        Self::probe_and_match_goal_against_assumption(ecx, goal, assumption, |ecx| {
+            ecx.add_goals(requirements);
+            ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
+        })
+    }
+
+    /// Consider a bound originating from the item bounds of an alias. For this we
+    /// require that the well-formed requirements of the self type of the goal
+    /// are "satisfied from the param-env".
+    /// See [`EvalCtxt::validate_alias_bound_self_from_param_env`].
+    fn consider_alias_bound_candidate(
+        ecx: &mut EvalCtxt<'_, 'tcx>,
+        goal: Goal<'tcx, Self>,
+        assumption: ty::Predicate<'tcx>,
+    ) -> QueryResult<'tcx> {
+        Self::probe_and_match_goal_against_assumption(ecx, goal, assumption, |ecx| {
+            ecx.validate_alias_bound_self_from_param_env(goal)
+        })
+    }
 
     // Consider a clause specifically for a `dyn Trait` self type. This requires
     // additionally checking all of the supertraits and object bounds to hold,
@@ -113,7 +145,25 @@ pub(super) trait GoalKind<'tcx>: TypeFoldable<TyCtxt<'tcx>> + Copy + Eq {
         ecx: &mut EvalCtxt<'_, 'tcx>,
         goal: Goal<'tcx, Self>,
         assumption: ty::Predicate<'tcx>,
-    ) -> QueryResult<'tcx>;
+    ) -> QueryResult<'tcx> {
+        Self::probe_and_match_goal_against_assumption(ecx, goal, assumption, |ecx| {
+            let tcx = ecx.tcx();
+            let ty::Dynamic(bounds, _, _) = *goal.predicate.self_ty().kind() else {
+                    bug!("expected object type in `consider_object_bound_candidate`");
+                };
+            ecx.add_goals(
+                structural_traits::predicates_for_object_candidate(
+                    &ecx,
+                    goal.param_env,
+                    goal.predicate.trait_ref(tcx),
+                    bounds,
+                )
+                .into_iter()
+                .map(|pred| goal.with(tcx, pred)),
+            );
+            ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
+        })
+    }
 
     fn consider_impl_candidate(
         ecx: &mut EvalCtxt<'_, 'tcx>,
@@ -241,7 +291,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
 
         // HACK: `_: Trait` is ambiguous, because it may be satisfied via a builtin rule,
         // object bound, alias bound, etc. We are unable to determine this until we can at
-        // least structually resolve the type one layer.
+        // least structurally resolve the type one layer.
         if goal.predicate.self_ty().is_ty_var() {
             return vec![Candidate {
                 source: CandidateSource::BuiltinImpl,
@@ -282,8 +332,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
         candidates: &mut Vec<Candidate<'tcx>>,
     ) {
         let tcx = self.tcx();
-        // FIXME: We also have to normalize opaque types, not sure where to best fit that in.
-        let &ty::Alias(ty::Projection, projection_ty) = goal.predicate.self_ty().kind() else {
+        let &ty::Alias(_, projection_ty) = goal.predicate.self_ty().kind() else {
             return
         };
 
@@ -305,8 +354,11 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
                         }),
                     );
                     ecx.add_goal(normalizes_to_goal);
-                    let _ = ecx.try_evaluate_added_goals()?;
+                    let _ = ecx.try_evaluate_added_goals().inspect_err(|_| {
+                        debug!("self type normalization failed");
+                    })?;
                     let normalized_ty = ecx.resolve_vars_if_possible(normalized_ty);
+                    debug!(?normalized_ty, "self type normalized");
                     // 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.
@@ -455,15 +507,17 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
             | ty::Param(_)
             | ty::Placeholder(..)
             | ty::Infer(ty::IntVar(_) | ty::FloatVar(_))
+            | ty::Alias(ty::Inherent, _)
             | ty::Error(_) => return,
             ty::Infer(ty::TyVar(_) | ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_))
             | ty::Bound(..) => bug!("unexpected self type for `{goal:?}`"),
-            ty::Alias(_, alias_ty) => alias_ty,
+            // Excluding IATs here as they don't have meaningful item bounds.
+            ty::Alias(ty::Projection | ty::Opaque, alias_ty) => alias_ty,
         };
 
         for assumption in self.tcx().item_bounds(alias_ty.def_id).subst(self.tcx(), alias_ty.substs)
         {
-            match G::consider_implied_clause(self, goal, assumption, []) {
+            match G::consider_alias_bound_candidate(self, goal, assumption) {
                 Ok(result) => {
                     candidates.push(Candidate { source: CandidateSource::AliasBound, result })
                 }
@@ -472,6 +526,105 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
         }
     }
 
+    /// Check that we are allowed to use an alias bound originating from the self
+    /// type of this goal. This means something different depending on the self type's
+    /// alias kind.
+    ///
+    /// * Projection: Given a goal with a self type such as `<Ty as Trait>::Assoc`,
+    /// we require that the bound `Ty: Trait` can be proven using either a nested alias
+    /// bound candidate, or a param-env candidate.
+    ///
+    /// * Opaque: The param-env must be in `Reveal::UserFacing` mode. Otherwise,
+    /// the goal should be proven by using the hidden type instead.
+    #[instrument(level = "debug", skip(self), ret)]
+    pub(super) fn validate_alias_bound_self_from_param_env<G: GoalKind<'tcx>>(
+        &mut self,
+        goal: Goal<'tcx, G>,
+    ) -> QueryResult<'tcx> {
+        match *goal.predicate.self_ty().kind() {
+            ty::Alias(ty::Projection, projection_ty) => {
+                let mut param_env_candidates = vec![];
+                let self_trait_ref = projection_ty.trait_ref(self.tcx());
+
+                if self_trait_ref.self_ty().is_ty_var() {
+                    return self
+                        .evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS);
+                }
+
+                let trait_goal: Goal<'_, ty::TraitPredicate<'tcx>> = goal.with(
+                    self.tcx(),
+                    ty::TraitPredicate {
+                        trait_ref: self_trait_ref,
+                        constness: ty::BoundConstness::NotConst,
+                        polarity: ty::ImplPolarity::Positive,
+                    },
+                );
+
+                self.assemble_param_env_candidates(trait_goal, &mut param_env_candidates);
+                // FIXME: We probably need some sort of recursion depth check here.
+                // Can't come up with an example yet, though, and the worst case
+                // we can have is a compiler stack overflow...
+                self.assemble_alias_bound_candidates(trait_goal, &mut param_env_candidates);
+
+                // FIXME: We must also consider alias-bound candidates for a peculiar
+                // class of built-in candidates that I'll call "defaulted" built-ins.
+                //
+                // For example, we always know that `T: Pointee` is implemented, but
+                // we do not always know what `<T as Pointee>::Metadata` actually is,
+                // similar to if we had a user-defined impl with a `default type ...`.
+                // For these traits, since we're not able to always normalize their
+                // associated types to a concrete type, we must consider their alias bounds
+                // instead, so we can prove bounds such as `<T as Pointee>::Metadata: Copy`.
+                self.assemble_alias_bound_candidates_for_builtin_impl_default_items(
+                    trait_goal,
+                    &mut param_env_candidates,
+                );
+
+                self.merge_candidates(param_env_candidates)
+            }
+            ty::Alias(ty::Opaque, _opaque_ty) => match goal.param_env.reveal() {
+                Reveal::UserFacing => {
+                    self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
+                }
+                Reveal::All => return Err(NoSolution),
+            },
+            _ => bug!("only expected to be called on alias tys"),
+        }
+    }
+
+    /// Assemble a subset of builtin impl candidates for a class of candidates called
+    /// "defaulted" built-in traits.
+    ///
+    /// For example, we always know that `T: Pointee` is implemented, but we do not
+    /// always know what `<T as Pointee>::Metadata` actually is! See the comment in
+    /// [`EvalCtxt::validate_alias_bound_self_from_param_env`] for more detail.
+    #[instrument(level = "debug", skip_all)]
+    fn assemble_alias_bound_candidates_for_builtin_impl_default_items<G: GoalKind<'tcx>>(
+        &mut self,
+        goal: Goal<'tcx, G>,
+        candidates: &mut Vec<Candidate<'tcx>>,
+    ) {
+        let lang_items = self.tcx().lang_items();
+        let trait_def_id = goal.predicate.trait_def_id(self.tcx());
+
+        // You probably shouldn't add anything to this list unless you
+        // know what you're doing.
+        let result = if lang_items.pointee_trait() == Some(trait_def_id) {
+            G::consider_builtin_pointee_candidate(self, goal)
+        } else if lang_items.discriminant_kind_trait() == Some(trait_def_id) {
+            G::consider_builtin_discriminant_kind_candidate(self, goal)
+        } else {
+            Err(NoSolution)
+        };
+
+        match result {
+            Ok(result) => {
+                candidates.push(Candidate { source: CandidateSource::BuiltinImpl, result })
+            }
+            Err(NoSolution) => (),
+        }
+    }
+
     #[instrument(level = "debug", skip_all)]
     fn assemble_object_bound_candidates<G: GoalKind<'tcx>>(
         &mut self,
@@ -590,13 +743,18 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
             SolverMode::Normal => {
                 let param_env_responses = candidates
                     .iter()
-                    .filter(|c| matches!(c.source, CandidateSource::ParamEnv(_)))
+                    .filter(|c| {
+                        matches!(
+                            c.source,
+                            CandidateSource::ParamEnv(_) | CandidateSource::AliasBound
+                        )
+                    })
                     .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);
-                    }
+                    // We strongly prefer alias and param-env bounds here, even if they affect inference.
+                    // See https://github.com/rust-lang/trait-system-refactor-initiative/issues/11.
+                    return Ok(result);
                 }
             }
         }
diff --git a/compiler/rustc_trait_selection/src/solve/assembly/structural_traits.rs b/compiler/rustc_trait_selection/src/solve/assembly/structural_traits.rs
index 1a566e87d..0ede32c75 100644
--- a/compiler/rustc_trait_selection/src/solve/assembly/structural_traits.rs
+++ b/compiler/rustc_trait_selection/src/solve/assembly/structural_traits.rs
@@ -33,7 +33,7 @@ pub(in crate::solve) fn instantiate_constituent_tys_for_auto_trait<'tcx>(
         ty::Dynamic(..)
         | ty::Param(..)
         | ty::Foreign(..)
-        | ty::Alias(ty::Projection, ..)
+        | ty::Alias(ty::Projection | ty::Inherent, ..)
         | ty::Placeholder(..)
         | ty::Bound(..)
         | ty::Infer(_) => {
@@ -91,14 +91,15 @@ pub(in crate::solve) fn replace_erased_lifetimes_with_bound_vars<'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 ty = tcx.fold_regions(ty, |r, current_depth| match r.kind() {
+        ty::ReErased => {
             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);
+            tcx.mk_re_late_bound(current_depth, br)
         }
-        r
+        // All free regions should be erased here.
+        r => bug!("unexpected region: {r:?}"),
     });
     let bound_vars = tcx.mk_bound_variable_kinds_from_iter(
         (0..counter).map(|_| ty::BoundVariableKind::Region(ty::BrAnon(None))),
diff --git a/compiler/rustc_trait_selection/src/solve/canonicalize.rs b/compiler/rustc_trait_selection/src/solve/canonicalize.rs
index 976849696..ff4bff10c 100644
--- a/compiler/rustc_trait_selection/src/solve/canonicalize.rs
+++ b/compiler/rustc_trait_selection/src/solve/canonicalize.rs
@@ -69,7 +69,7 @@ impl<'a, 'tcx> Canonicalizer<'a, 'tcx> {
         };
 
         let value = value.fold_with(&mut canonicalizer);
-        assert!(!value.needs_infer());
+        assert!(!value.has_infer());
         assert!(!value.has_placeholders());
 
         let (max_universe, variables) = canonicalizer.finalize();
diff --git a/compiler/rustc_trait_selection/src/solve/eval_ctxt.rs b/compiler/rustc_trait_selection/src/solve/eval_ctxt.rs
index c29b5b04e..f91c67277 100644
--- a/compiler/rustc_trait_selection/src/solve/eval_ctxt.rs
+++ b/compiler/rustc_trait_selection/src/solve/eval_ctxt.rs
@@ -1,14 +1,19 @@
-use rustc_hir::def_id::DefId;
+use rustc_hir::def_id::{DefId, LocalDefId};
 use rustc_infer::infer::at::ToTrace;
 use rustc_infer::infer::canonical::CanonicalVarValues;
 use rustc_infer::infer::type_variable::{TypeVariableOrigin, TypeVariableOriginKind};
 use rustc_infer::infer::{
-    DefineOpaqueTypes, InferCtxt, InferOk, LateBoundRegionConversionTime, TyCtxtInferExt,
+    DefineOpaqueTypes, InferCtxt, InferOk, LateBoundRegionConversionTime, RegionVariableOrigin,
+    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::traits::solve::{
+    CanonicalInput, CanonicalResponse, Certainty, MaybeCause, PredefinedOpaques,
+    PredefinedOpaquesData, QueryResult,
+};
+use rustc_middle::traits::DefiningAnchor;
 use rustc_middle::ty::{
     self, Ty, TyCtxt, TypeFoldable, TypeSuperVisitable, TypeVisitable, TypeVisitableExt,
     TypeVisitor,
@@ -43,6 +48,9 @@ pub struct EvalCtxt<'a, 'tcx> {
     infcx: &'a InferCtxt<'tcx>,
 
     pub(super) var_values: CanonicalVarValues<'tcx>,
+
+    predefined_opaques_in_body: PredefinedOpaques<'tcx>,
+
     /// The highest universe index nameable by the caller.
     ///
     /// When we enter a new binder inside of the query we create new universes
@@ -57,6 +65,14 @@ pub struct EvalCtxt<'a, 'tcx> {
     pub(super) search_graph: &'a mut SearchGraph<'tcx>,
 
     pub(super) nested_goals: NestedGoals<'tcx>,
+
+    // Has this `EvalCtxt` errored out with `NoSolution` in `try_evaluate_added_goals`?
+    //
+    // If so, then it can no longer be used to make a canonical query response,
+    // since subsequent calls to `try_evaluate_added_goals` have possibly dropped
+    // ambiguous goals. Instead, a probe needs to be introduced somewhere in the
+    // evaluation code.
+    tainted: Result<(), NoSolution>,
 }
 
 #[derive(Debug, Copy, Clone, PartialEq, Eq)]
@@ -117,10 +133,16 @@ impl<'tcx> InferCtxtEvalExt<'tcx> for InferCtxt<'tcx> {
         let mut ecx = EvalCtxt {
             search_graph: &mut search_graph,
             infcx: self,
+            // Only relevant when canonicalizing the response,
+            // which we don't do within this evaluation context.
+            predefined_opaques_in_body: self
+                .tcx
+                .mk_predefined_opaques_in_body(PredefinedOpaquesData::default()),
             // Only relevant when canonicalizing the response.
             max_input_universe: ty::UniverseIndex::ROOT,
             var_values: CanonicalVarValues::dummy(),
             nested_goals: NestedGoals::new(),
+            tainted: Ok(()),
         };
         let result = ecx.evaluate_goal(IsNormalizesToHack::No, goal);
 
@@ -152,28 +174,53 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> {
     fn evaluate_canonical_goal(
         tcx: TyCtxt<'tcx>,
         search_graph: &'a mut search_graph::SearchGraph<'tcx>,
-        canonical_goal: CanonicalGoal<'tcx>,
+        canonical_input: CanonicalInput<'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| {
+        search_graph.with_new_goal(tcx, canonical_input, |search_graph| {
             let intercrate = match search_graph.solver_mode() {
                 SolverMode::Normal => false,
                 SolverMode::Coherence => true,
             };
-            let (ref infcx, goal, var_values) = tcx
+            let (ref infcx, input, var_values) = tcx
                 .infer_ctxt()
                 .intercrate(intercrate)
-                .build_with_canonical(DUMMY_SP, &canonical_goal);
+                .with_opaque_type_inference(canonical_input.value.anchor)
+                .build_with_canonical(DUMMY_SP, &canonical_input);
+
+            for &(a, b) in &input.predefined_opaques_in_body.opaque_types {
+                let InferOk { value: (), obligations } = infcx
+                    .register_hidden_type_in_new_solver(a, input.goal.param_env, b)
+                    .expect("expected opaque type instantiation to succeed");
+                // We're only registering opaques already defined by the caller,
+                // so we're not responsible for proving that they satisfy their
+                // item bounds, unless we use them in a normalizes-to goal,
+                // which is handled in `EvalCtxt::unify_existing_opaque_tys`.
+                let _ = obligations;
+            }
             let mut ecx = EvalCtxt {
                 infcx,
                 var_values,
-                max_input_universe: canonical_goal.max_universe,
+                predefined_opaques_in_body: input.predefined_opaques_in_body,
+                max_input_universe: canonical_input.max_universe,
                 search_graph,
                 nested_goals: NestedGoals::new(),
+                tainted: Ok(()),
             };
-            ecx.compute_goal(goal)
+
+            let result = ecx.compute_goal(input.goal);
+
+            // When creating a query response we clone the opaque type constraints
+            // instead of taking them. This would cause an ICE here, since we have
+            // assertions against dropping an `InferCtxt` without taking opaques.
+            // FIXME: Once we remove support for the old impl we can remove this.
+            if input.anchor != DefiningAnchor::Error {
+                let _ = infcx.take_opaque_types();
+            }
+
+            result
         })
     }
 
@@ -188,7 +235,8 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> {
         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 has_changed = !canonical_response.value.var_values.is_identity()
+            || !canonical_response.value.external_constraints.opaque_types.is_empty();
         let (certainty, nested_goals) = self.instantiate_and_apply_query_response(
             goal.param_env,
             orig_values,
@@ -213,18 +261,20 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> {
         {
             debug!("rerunning goal to check result is stable");
             let (_orig_values, canonical_goal) = self.canonicalize_goal(goal);
-            let canonical_response =
+            let new_canonical_response =
                 EvalCtxt::evaluate_canonical_goal(self.tcx(), self.search_graph, canonical_goal)?;
-            if !canonical_response.value.var_values.is_identity() {
+            if !new_canonical_response.value.var_values.is_identity() {
                 bug!(
                     "unstable result: re-canonicalized goal={canonical_goal:#?} \
-                     response={canonical_response:#?}"
+                    first_response={canonical_response:#?} \
+                    second_response={new_canonical_response:#?}"
                 );
             }
-            if certainty != canonical_response.value.certainty {
+            if certainty != new_canonical_response.value.certainty {
                 bug!(
                     "unstable certainty: {certainty:#?} re-canonicalized goal={canonical_goal:#?} \
-                     response={canonical_response:#?}"
+                     first_response={canonical_response:#?} \
+                     second_response={new_canonical_response:#?}"
                 );
             }
         }
@@ -391,6 +441,10 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> {
             },
         );
 
+        if response.is_err() {
+            self.tainted = Err(NoSolution);
+        }
+
         self.nested_goals = goals;
         response
     }
@@ -401,9 +455,11 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
         let mut ecx = EvalCtxt {
             infcx: self.infcx,
             var_values: self.var_values,
+            predefined_opaques_in_body: self.predefined_opaques_in_body,
             max_input_universe: self.max_input_universe,
             search_graph: self.search_graph,
             nested_goals: self.nested_goals.clone(),
+            tainted: self.tainted,
         };
         self.infcx.probe(|_| f(&mut ecx))
     }
@@ -419,6 +475,10 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
         })
     }
 
+    pub(super) fn next_region_infer(&self) -> ty::Region<'tcx> {
+        self.infcx.next_region_var(RegionVariableOrigin::MiscVariable(DUMMY_SP))
+    }
+
     pub(super) fn next_const_infer(&self, ty: Ty<'tcx>) -> ty::Const<'tcx> {
         self.infcx.next_const_var(
             ty,
@@ -649,7 +709,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
         // 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),
+            src_and_dst,
             scope,
             assume,
         ) {
@@ -660,4 +720,56 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
             | rustc_transmute::Answer::IfAny(_) => Err(NoSolution),
         }
     }
+
+    pub(super) fn can_define_opaque_ty(&mut self, def_id: LocalDefId) -> bool {
+        self.infcx.opaque_type_origin(def_id).is_some()
+    }
+
+    pub(super) fn register_opaque_ty(
+        &mut self,
+        a: ty::OpaqueTypeKey<'tcx>,
+        b: Ty<'tcx>,
+        param_env: ty::ParamEnv<'tcx>,
+    ) -> Result<(), NoSolution> {
+        let InferOk { value: (), obligations } =
+            self.infcx.register_hidden_type_in_new_solver(a, param_env, b)?;
+        self.add_goals(obligations.into_iter().map(|obligation| obligation.into()));
+        Ok(())
+    }
+
+    // Do something for each opaque/hidden pair defined with `def_id` in the
+    // current inference context.
+    pub(super) fn unify_existing_opaque_tys(
+        &mut self,
+        param_env: ty::ParamEnv<'tcx>,
+        key: ty::OpaqueTypeKey<'tcx>,
+        ty: Ty<'tcx>,
+    ) -> Vec<CanonicalResponse<'tcx>> {
+        // FIXME: Super inefficient to be cloning this...
+        let opaques = self.infcx.clone_opaque_types_for_query_response();
+
+        let mut values = vec![];
+        for (candidate_key, candidate_ty) in opaques {
+            if candidate_key.def_id != key.def_id {
+                continue;
+            }
+            values.extend(self.probe(|ecx| {
+                for (a, b) in std::iter::zip(candidate_key.substs, key.substs) {
+                    ecx.eq(param_env, a, b)?;
+                }
+                ecx.eq(param_env, candidate_ty, ty)?;
+                let mut obl = vec![];
+                ecx.infcx.add_item_bounds_for_hidden_type(
+                    candidate_key,
+                    ObligationCause::dummy(),
+                    param_env,
+                    candidate_ty,
+                    &mut obl,
+                );
+                ecx.add_goals(obl.into_iter().map(Into::into));
+                ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
+            }));
+        }
+        values
+    }
 }
diff --git a/compiler/rustc_trait_selection/src/solve/eval_ctxt/canonical.rs b/compiler/rustc_trait_selection/src/solve/eval_ctxt/canonical.rs
index ada868705..fdb209fbf 100644
--- a/compiler/rustc_trait_selection/src/solve/eval_ctxt/canonical.rs
+++ b/compiler/rustc_trait_selection/src/solve/eval_ctxt/canonical.rs
@@ -8,15 +8,19 @@
 /// section of the [rustc-dev-guide][c].
 ///
 /// [c]: https://rustc-dev-guide.rust-lang.org/solve/canonicalization.html
-use super::{CanonicalGoal, Certainty, EvalCtxt, Goal};
+use super::{CanonicalInput, Certainty, EvalCtxt, Goal};
 use crate::solve::canonicalize::{CanonicalizeMode, Canonicalizer};
 use crate::solve::{CanonicalResponse, QueryResult, Response};
+use rustc_index::IndexVec;
 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::infer::InferOk;
 use rustc_middle::traits::query::NoSolution;
-use rustc_middle::traits::solve::{ExternalConstraints, ExternalConstraintsData};
-use rustc_middle::ty::{self, GenericArgKind};
+use rustc_middle::traits::solve::{
+    ExternalConstraints, ExternalConstraintsData, MaybeCause, PredefinedOpaquesData, QueryInput,
+};
+use rustc_middle::ty::{self, BoundVar, GenericArgKind, Ty};
 use rustc_span::DUMMY_SP;
 use std::iter;
 use std::ops::Deref;
@@ -27,13 +31,21 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
     pub(super) fn canonicalize_goal(
         &self,
         goal: Goal<'tcx, ty::Predicate<'tcx>>,
-    ) -> (Vec<ty::GenericArg<'tcx>>, CanonicalGoal<'tcx>) {
+    ) -> (Vec<ty::GenericArg<'tcx>>, CanonicalInput<'tcx>) {
         let mut orig_values = Default::default();
         let canonical_goal = Canonicalizer::canonicalize(
             self.infcx,
             CanonicalizeMode::Input,
             &mut orig_values,
-            goal,
+            QueryInput {
+                goal,
+                anchor: self.infcx.defining_use_anchor,
+                predefined_opaques_in_body: self.tcx().mk_predefined_opaques_in_body(
+                    PredefinedOpaquesData {
+                        opaque_types: self.infcx.clone_opaque_types_for_query_response(),
+                    },
+                ),
+            },
         );
         (orig_values, canonical_goal)
     }
@@ -50,11 +62,36 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
         certainty: Certainty,
     ) -> QueryResult<'tcx> {
         let goals_certainty = self.try_evaluate_added_goals()?;
+        assert_eq!(
+            self.tainted,
+            Ok(()),
+            "EvalCtxt is tainted -- nested goals may have been dropped in a \
+            previous call to `try_evaluate_added_goals!`"
+        );
+
         let certainty = certainty.unify_with(goals_certainty);
 
-        let external_constraints = self.compute_external_query_constraints()?;
+        let response = match certainty {
+            Certainty::Yes | Certainty::Maybe(MaybeCause::Ambiguity) => {
+                let external_constraints = self.compute_external_query_constraints()?;
+                Response { var_values: self.var_values, external_constraints, certainty }
+            }
+            Certainty::Maybe(MaybeCause::Overflow) => {
+                // If we have overflow, it's probable that we're substituting a type
+                // into itself infinitely and any partial substitutions in the query
+                // response are probably not useful anyways, so just return an empty
+                // query response.
+                //
+                // This may prevent us from potentially useful inference, e.g.
+                // 2 candidates, one ambiguous and one overflow, which both
+                // have the same inference constraints.
+                //
+                // Changing this to retain some constraints in the future
+                // won't be a breaking change, so this is good enough for now.
+                return Ok(self.make_ambiguous_response_no_constraints(MaybeCause::Overflow));
+            }
+        };
 
-        let response = Response { var_values: self.var_values, external_constraints, certainty };
         let canonical = Canonicalizer::canonicalize(
             self.infcx,
             CanonicalizeMode::Response { max_input_universe: self.max_input_universe },
@@ -64,6 +101,40 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
         Ok(canonical)
     }
 
+    /// Constructs a totally unconstrained, ambiguous response to a goal.
+    ///
+    /// Take care when using this, since often it's useful to respond with
+    /// ambiguity but return constrained variables to guide inference.
+    pub(in crate::solve) fn make_ambiguous_response_no_constraints(
+        &self,
+        maybe_cause: MaybeCause,
+    ) -> CanonicalResponse<'tcx> {
+        let unconstrained_response = Response {
+            var_values: CanonicalVarValues {
+                var_values: self.tcx().mk_substs_from_iter(self.var_values.var_values.iter().map(
+                    |arg| -> ty::GenericArg<'tcx> {
+                        match arg.unpack() {
+                            GenericArgKind::Lifetime(_) => self.next_region_infer().into(),
+                            GenericArgKind::Type(_) => self.next_ty_infer().into(),
+                            GenericArgKind::Const(ct) => self.next_const_infer(ct.ty()).into(),
+                        }
+                    },
+                )),
+            },
+            external_constraints: self
+                .tcx()
+                .mk_external_constraints(ExternalConstraintsData::default()),
+            certainty: Certainty::Maybe(maybe_cause),
+        };
+
+        Canonicalizer::canonicalize(
+            self.infcx,
+            CanonicalizeMode::Response { max_input_universe: self.max_input_universe },
+            &mut Default::default(),
+            unconstrained_response,
+        )
+    }
+
     #[instrument(level = "debug", skip(self), ret)]
     fn compute_external_query_constraints(&self) -> Result<ExternalConstraints<'tcx>, NoSolution> {
         // Cannot use `take_registered_region_obligations` as we may compute the response
@@ -78,7 +149,13 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
                 region_constraints,
             )
         });
-        let opaque_types = self.infcx.clone_opaque_types_for_query_response();
+
+        let mut opaque_types = self.infcx.clone_opaque_types_for_query_response();
+        // Only return opaque type keys for newly-defined opaques
+        opaque_types.retain(|(a, _)| {
+            self.predefined_opaques_in_body.opaque_types.iter().all(|(pa, _)| pa != a)
+        });
+
         Ok(self
             .tcx()
             .mk_external_constraints(ExternalConstraintsData { region_constraints, opaque_types }))
@@ -104,10 +181,10 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
 
         let nested_goals = self.unify_query_var_values(param_env, &original_values, var_values)?;
 
-        // FIXME: implement external constraints.
-        let ExternalConstraintsData { region_constraints, opaque_types: _ } =
+        let ExternalConstraintsData { region_constraints, opaque_types } =
             external_constraints.deref();
         self.register_region_constraints(region_constraints);
+        self.register_opaque_types(param_env, opaque_types)?;
 
         Ok((certainty, nested_goals))
     }
@@ -139,25 +216,25 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
         //
         // We therefore instantiate the existential variable in the canonical response with the
         // inference variable of the input right away, which is more performant.
-        let mut opt_values = vec![None; response.variables.len()];
+        let mut opt_values = IndexVec::from_elem_n(None, response.variables.len());
         for (original_value, result_value) in iter::zip(original_values, var_values.var_values) {
             match result_value.unpack() {
                 GenericArgKind::Type(t) => {
                     if let &ty::Bound(debruijn, b) = t.kind() {
                         assert_eq!(debruijn, ty::INNERMOST);
-                        opt_values[b.var.index()] = Some(*original_value);
+                        opt_values[b.var] = Some(*original_value);
                     }
                 }
                 GenericArgKind::Lifetime(r) => {
                     if let ty::ReLateBound(debruijn, br) = *r {
                         assert_eq!(debruijn, ty::INNERMOST);
-                        opt_values[br.var.index()] = Some(*original_value);
+                        opt_values[br.var] = Some(*original_value);
                     }
                 }
                 GenericArgKind::Const(c) => {
-                    if let ty::ConstKind::Bound(debrujin, b) = c.kind() {
-                        assert_eq!(debrujin, ty::INNERMOST);
-                        opt_values[b.index()] = Some(*original_value);
+                    if let ty::ConstKind::Bound(debruijn, b) = c.kind() {
+                        assert_eq!(debruijn, ty::INNERMOST);
+                        opt_values[b] = Some(*original_value);
                     }
                 }
             }
@@ -176,11 +253,11 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
                     // As an optimization we sometimes avoid creating a new inference variable here.
                     //
                     // All new inference variables we create start out in the current universe of the caller.
-                    // This is conceptionally wrong as these inference variables would be able to name
+                    // This is conceptually wrong as these inference variables would be able to name
                     // more placeholders then they should be able to. However the inference variables have
                     // to "come from somewhere", so by equating them with the original values of the caller
                     // later on, we pull them down into their correct universe again.
-                    if let Some(v) = opt_values[index] {
+                    if let Some(v) = opt_values[BoundVar::from_usize(index)] {
                         v
                     } else {
                         self.infcx.instantiate_canonical_var(DUMMY_SP, info, |_| prev_universe)
@@ -227,4 +304,19 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
             let _ = member_constraint;
         }
     }
+
+    fn register_opaque_types(
+        &mut self,
+        param_env: ty::ParamEnv<'tcx>,
+        opaque_types: &[(ty::OpaqueTypeKey<'tcx>, Ty<'tcx>)],
+    ) -> Result<(), NoSolution> {
+        for &(a, b) in opaque_types {
+            let InferOk { value: (), obligations } =
+                self.infcx.register_hidden_type_in_new_solver(a, param_env, b)?;
+            // It's sound to drop these obligations, since the normalizes-to goal
+            // is responsible for proving these obligations.
+            let _ = obligations;
+        }
+        Ok(())
+    }
 }
diff --git a/compiler/rustc_trait_selection/src/solve/fulfill.rs b/compiler/rustc_trait_selection/src/solve/fulfill.rs
index 32bd10f0b..4a403196c 100644
--- a/compiler/rustc_trait_selection/src/solve/fulfill.rs
+++ b/compiler/rustc_trait_selection/src/solve/fulfill.rs
@@ -133,12 +133,14 @@ impl<'tcx> TraitEngine<'tcx> for FulfillmentCtxt<'tcx> {
                                 | ty::PredicateKind::ObjectSafe(_)
                                 | ty::PredicateKind::ClosureKind(_, _, _)
                                 | ty::PredicateKind::ConstEvaluatable(_)
-                                | ty::PredicateKind::TypeWellFormedFromEnv(_)
                                 | ty::PredicateKind::Ambiguous => {
                                     FulfillmentErrorCode::CodeSelectionError(
                                         SelectionError::Unimplemented,
                                     )
                                 }
+                                ty::PredicateKind::TypeWellFormedFromEnv(_) => {
+                                    bug!("unexpected goal: {goal:?}")
+                                }
                             },
                             root_obligation: obligation,
                         });
diff --git a/compiler/rustc_trait_selection/src/solve/mod.rs b/compiler/rustc_trait_selection/src/solve/mod.rs
index 19bcbd461..56a254d9c 100644
--- a/compiler/rustc_trait_selection/src/solve/mod.rs
+++ b/compiler/rustc_trait_selection/src/solve/mod.rs
@@ -24,6 +24,7 @@ mod assembly;
 mod canonicalize;
 mod eval_ctxt;
 mod fulfill;
+mod opaques;
 mod project_goals;
 mod search_graph;
 mod trait_goals;
@@ -212,7 +213,7 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> {
             );
         }
 
-        match (lhs.to_projection_term(tcx), rhs.to_projection_term(tcx)) {
+        match (lhs.to_alias_ty(tcx), rhs.to_alias_ty(tcx)) {
             (None, None) => bug!("`AliasRelate` goal without an alias on either lhs or rhs"),
 
             // RHS is not a projection, only way this is true is if LHS normalizes-to RHS
@@ -230,44 +231,60 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> {
 
                 let mut candidates = Vec::new();
                 // LHS normalizes-to RHS
-                candidates.extend(
-                    evaluate_normalizes_to(self, alias_lhs, rhs, direction, Invert::No).ok(),
-                );
+                candidates.extend(evaluate_normalizes_to(
+                    self,
+                    alias_lhs,
+                    rhs,
+                    direction,
+                    Invert::No,
+                ));
                 // RHS normalizes-to RHS
-                candidates.extend(
-                    evaluate_normalizes_to(self, alias_rhs, lhs, direction, Invert::Yes).ok(),
-                );
+                candidates.extend(evaluate_normalizes_to(
+                    self,
+                    alias_rhs,
+                    lhs,
+                    direction,
+                    Invert::Yes,
+                ));
                 // 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)?;
-                            }
+                let subst_relate_response = 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(),
-                );
+                    ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
+                });
+                candidates.extend(subst_relate_response);
                 debug!(?candidates);
 
                 if let Some(merged) = self.try_merge_responses(&candidates) {
                     Ok(merged)
                 } else {
-                    self.flounder(&candidates)
+                    // When relating two aliases and we have ambiguity, we prefer
+                    // relating the generic arguments of the aliases over normalizing
+                    // them. This is necessary for inference during typeck.
+                    //
+                    // As this is incomplete, we must not do so during coherence.
+                    match (self.solver_mode(), subst_relate_response) {
+                        (SolverMode::Normal, Ok(response)) => Ok(response),
+                        (SolverMode::Normal, Err(NoSolution)) | (SolverMode::Coherence, _) => {
+                            self.flounder(&candidates)
+                        }
+                    }
                 }
             }
         }
@@ -340,17 +357,17 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
         if responses.is_empty() {
             return Err(NoSolution);
         }
-        let certainty = responses.iter().fold(Certainty::AMBIGUOUS, |certainty, response| {
-            certainty.unify_with(response.value.certainty)
-        });
-
-        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:?}");
-        }
+
+        let Certainty::Maybe(maybe_cause) = responses.iter().fold(
+            Certainty::AMBIGUOUS,
+            |certainty, response| {
+                certainty.unify_with(response.value.certainty)
+            },
+        ) else {
+            bug!("expected flounder response to be ambiguous")
+        };
+
+        Ok(self.make_ambiguous_response_no_constraints(maybe_cause))
     }
 }
 
diff --git a/compiler/rustc_trait_selection/src/solve/opaques.rs b/compiler/rustc_trait_selection/src/solve/opaques.rs
new file mode 100644
index 000000000..a5de4ddee
--- /dev/null
+++ b/compiler/rustc_trait_selection/src/solve/opaques.rs
@@ -0,0 +1,67 @@
+use rustc_middle::traits::query::NoSolution;
+use rustc_middle::traits::solve::{Certainty, Goal, QueryResult};
+use rustc_middle::traits::Reveal;
+use rustc_middle::ty;
+use rustc_middle::ty::util::NotUniqueParam;
+
+use super::{EvalCtxt, SolverMode};
+
+impl<'tcx> EvalCtxt<'_, 'tcx> {
+    pub(super) fn normalize_opaque_type(
+        &mut self,
+        goal: Goal<'tcx, ty::ProjectionPredicate<'tcx>>,
+    ) -> QueryResult<'tcx> {
+        let tcx = self.tcx();
+        let opaque_ty = goal.predicate.projection_ty;
+        let expected = goal.predicate.term.ty().expect("no such thing as an opaque const");
+
+        match (goal.param_env.reveal(), self.solver_mode()) {
+            (Reveal::UserFacing, SolverMode::Normal) => {
+                let Some(opaque_ty_def_id) = opaque_ty.def_id.as_local() else {
+                    return Err(NoSolution);
+                };
+                let opaque_ty =
+                    ty::OpaqueTypeKey { def_id: opaque_ty_def_id, substs: opaque_ty.substs };
+                // FIXME: at some point we should call queries without defining
+                // new opaque types but having the existing opaque type definitions.
+                // This will require moving this below "Prefer opaques registered already".
+                if !self.can_define_opaque_ty(opaque_ty_def_id) {
+                    return Err(NoSolution);
+                }
+                // FIXME: This may have issues when the substs contain aliases...
+                match self.tcx().uses_unique_placeholders_ignoring_regions(opaque_ty.substs) {
+                    Err(NotUniqueParam::NotParam(param)) if param.is_non_region_infer() => {
+                        return self.evaluate_added_goals_and_make_canonical_response(
+                            Certainty::AMBIGUOUS,
+                        );
+                    }
+                    Err(_) => {
+                        return Err(NoSolution);
+                    }
+                    Ok(()) => {}
+                }
+                // Prefer opaques registered already.
+                let matches = self.unify_existing_opaque_tys(goal.param_env, opaque_ty, expected);
+                if !matches.is_empty() {
+                    if let Some(response) = self.try_merge_responses(&matches) {
+                        return Ok(response);
+                    } else {
+                        return self.flounder(&matches);
+                    }
+                }
+                // Otherwise, define a new opaque type
+                self.register_opaque_ty(opaque_ty, expected, goal.param_env)?;
+                self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
+            }
+            (Reveal::UserFacing, SolverMode::Coherence) => {
+                self.evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS)
+            }
+            (Reveal::All, _) => {
+                // FIXME: Add an assertion that opaque type storage is empty.
+                let actual = tcx.type_of(opaque_ty.def_id).subst(tcx, opaque_ty.substs);
+                self.eq(goal.param_env, expected, actual)?;
+                self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
+            }
+        }
+    }
+}
diff --git a/compiler/rustc_trait_selection/src/solve/project_goals.rs b/compiler/rustc_trait_selection/src/solve/project_goals.rs
index 14cb43b89..7d7dfa2c8 100644
--- a/compiler/rustc_trait_selection/src/solve/project_goals.rs
+++ b/compiler/rustc_trait_selection/src/solve/project_goals.rs
@@ -22,19 +22,25 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
         &mut self,
         goal: Goal<'tcx, ProjectionPredicate<'tcx>>,
     ) -> QueryResult<'tcx> {
-        // To only compute normalization once for each projection we only
-        // normalize if the expected term is an unconstrained inference variable.
-        //
-        // E.g. for `<T as Trait>::Assoc == u32` we recursively compute the goal
-        // `exists<U> <T as Trait>::Assoc == U` and then take the resulting type for
-        // `U` and equate it with `u32`. This means that we don't need a separate
-        // projection cache in the solver.
-        if self.term_is_fully_unconstrained(goal) {
-            let candidates = self.assemble_and_evaluate_candidates(goal);
-            self.merge_candidates(candidates)
-        } else {
-            self.set_normalizes_to_hack_goal(goal);
-            self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
+        match goal.predicate.projection_ty.kind(self.tcx()) {
+            ty::AliasKind::Projection => {
+                // To only compute normalization once for each projection we only
+                // normalize if the expected term is an unconstrained inference variable.
+                //
+                // E.g. for `<T as Trait>::Assoc == u32` we recursively compute the goal
+                // `exists<U> <T as Trait>::Assoc == U` and then take the resulting type for
+                // `U` and equate it with `u32`. This means that we don't need a separate
+                // projection cache in the solver.
+                if self.term_is_fully_unconstrained(goal) {
+                    let candidates = self.assemble_and_evaluate_candidates(goal);
+                    self.merge_candidates(candidates)
+                } else {
+                    self.set_normalizes_to_hack_goal(goal);
+                    self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
+                }
+            }
+            ty::AliasKind::Opaque => self.normalize_opaque_type(goal),
+            ty::AliasKind::Inherent => bug!("IATs not supported here yet"),
         }
     }
 }
@@ -56,11 +62,11 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> {
         self.trait_def_id(tcx)
     }
 
-    fn consider_implied_clause(
+    fn probe_and_match_goal_against_assumption(
         ecx: &mut EvalCtxt<'_, 'tcx>,
         goal: Goal<'tcx, Self>,
         assumption: ty::Predicate<'tcx>,
-        requirements: impl IntoIterator<Item = Goal<'tcx, ty::Predicate<'tcx>>>,
+        then: impl FnOnce(&mut EvalCtxt<'_, 'tcx>) -> QueryResult<'tcx>,
     ) -> QueryResult<'tcx> {
         if let Some(poly_projection_pred) = assumption.to_opt_poly_projection_pred()
             && poly_projection_pred.projection_def_id() == goal.predicate.def_id()
@@ -73,49 +79,9 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> {
                     goal.predicate.projection_ty,
                     assumption_projection_pred.projection_ty,
                 )?;
-                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)
-        }
-    }
-
-    fn consider_object_bound_candidate(
-        ecx: &mut EvalCtxt<'_, 'tcx>,
-        goal: Goal<'tcx, Self>,
-        assumption: ty::Predicate<'tcx>,
-    ) -> QueryResult<'tcx> {
-        if let Some(poly_projection_pred) = assumption.to_opt_poly_projection_pred()
-            && 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);
-                ecx.eq(
-                    goal.param_env,
-                    goal.predicate.projection_ty,
-                    assumption_projection_pred.projection_ty,
-                )?;
-
-                let ty::Dynamic(bounds, _, _) = *goal.predicate.self_ty().kind() else {
-                    bug!("expected object type in `consider_object_bound_candidate`");
-                };
-                ecx.add_goals(
-                    structural_traits::predicates_for_object_candidate(
-                        &ecx,
-                        goal.param_env,
-                        goal.predicate.projection_ty.trait_ref(tcx),
-                        bounds,
-                    )
-                    .into_iter()
-                    .map(|pred| goal.with(tcx, pred)),
-                );
-                ecx.eq(goal.param_env, goal.predicate.term, assumption_projection_pred.term)?;
-                ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
+                ecx.eq(goal.param_env, goal.predicate.term, assumption_projection_pred.term)
+                    .expect("expected goal term to be fully unconstrained");
+                then(ecx)
             })
         } else {
             Err(NoSolution)
@@ -164,10 +130,24 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> {
             };
 
             if !assoc_def.item.defaultness(tcx).has_value() {
-                tcx.sess.delay_span_bug(
+                let guar = tcx.sess.delay_span_bug(
                     tcx.def_span(assoc_def.item.def_id),
                     "missing value for assoc item in impl",
                 );
+                let error_term = match assoc_def.item.kind {
+                    ty::AssocKind::Const => tcx
+                        .const_error(
+                            tcx.type_of(goal.predicate.def_id())
+                                .subst(tcx, goal.predicate.projection_ty.substs),
+                            guar,
+                        )
+                        .into(),
+                    ty::AssocKind::Type => tcx.ty_error(guar).into(),
+                    ty::AssocKind::Fn => unreachable!(),
+                };
+                ecx.eq(goal.param_env, goal.predicate.term, error_term)
+                    .expect("expected goal term to be fully unconstrained");
+                return ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes);
             }
 
             // Getting the right substitutions here is complex, e.g. given:
@@ -198,7 +178,7 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> {
             let term: ty::EarlyBinder<ty::Term<'tcx>> = if is_const {
                 let identity_substs =
                     ty::InternalSubsts::identity_for_item(tcx, assoc_def.item.def_id);
-                let did = ty::WithOptConstParam::unknown(assoc_def.item.def_id);
+                let did = assoc_def.item.def_id;
                 let kind =
                     ty::ConstKind::Unevaluated(ty::UnevaluatedConst::new(did, identity_substs));
                 ty.map_bound(|ty| tcx.mk_const(kind, ty).into())
@@ -206,7 +186,8 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> {
                 ty.map_bound(|ty| ty.into())
             };
 
-            ecx.eq(goal.param_env, goal.predicate.term, term.subst(tcx, substs))?;
+            ecx.eq(goal.param_env, goal.predicate.term, term.subst(tcx, substs))
+                .expect("expected goal term to be fully unconstrained");
             ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
         })
     }
@@ -271,8 +252,9 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> {
                         .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]));
+        let output_is_sized_pred = tupled_inputs_and_output.map_bound(|(_, output)| {
+            ty::TraitRef::from_lang_item(tcx, LangItem::Sized, DUMMY_SP, [output])
+        });
 
         let pred = tupled_inputs_and_output
             .map_bound(|(inputs, output)| ty::ProjectionPredicate {
@@ -330,10 +312,12 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> {
 
                 ty::Alias(_, _) | ty::Param(_) | ty::Placeholder(..) => {
                     // FIXME(ptr_metadata): It would also be possible to return a `Ok(Ambig)` with no constraints.
-                    let sized_predicate = ty::Binder::dummy(tcx.at(DUMMY_SP).mk_trait_ref(
+                    let sized_predicate = ty::TraitRef::from_lang_item(
+                        tcx,
                         LangItem::Sized,
+                        DUMMY_SP,
                         [ty::GenericArg::from(goal.predicate.self_ty())],
-                    ));
+                    );
                     ecx.add_goal(goal.with(tcx, sized_predicate));
                     tcx.types.unit
                 }
@@ -375,7 +359,8 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> {
                 ),
             };
 
-            ecx.eq(goal.param_env, goal.predicate.term, metadata_ty.into())?;
+            ecx.eq(goal.param_env, goal.predicate.term, metadata_ty.into())
+                .expect("expected goal term to be fully unconstrained");
             ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
         })
     }
@@ -513,7 +498,8 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> {
         };
 
         ecx.probe(|ecx| {
-            ecx.eq(goal.param_env, goal.predicate.term, discriminant_ty.into())?;
+            ecx.eq(goal.param_env, goal.predicate.term, discriminant_ty.into())
+                .expect("expected goal term to be fully unconstrained");
             ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
         })
     }
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 d1b4fa554..56f126e91 100644
--- a/compiler/rustc_trait_selection/src/solve/search_graph/cache.rs
+++ b/compiler/rustc_trait_selection/src/solve/search_graph/cache.rs
@@ -10,8 +10,8 @@
 //! before then or if I still haven't done that before January 2023.
 use super::StackDepth;
 use rustc_data_structures::fx::FxHashMap;
-use rustc_index::vec::IndexVec;
-use rustc_middle::traits::solve::{CanonicalGoal, QueryResult};
+use rustc_index::IndexVec;
+use rustc_middle::traits::solve::{CanonicalInput, QueryResult};
 
 rustc_index::newtype_index! {
     pub struct EntryIndex {}
@@ -34,7 +34,7 @@ pub(super) struct ProvisionalEntry<'tcx> {
 
     // The goal for this entry. Should always be equal to the corresponding goal
     // in the lookup table.
-    pub(super) goal: CanonicalGoal<'tcx>,
+    pub(super) input: CanonicalInput<'tcx>,
 }
 
 pub(super) struct ProvisionalCache<'tcx> {
@@ -42,7 +42,7 @@ pub(super) struct ProvisionalCache<'tcx> {
     // FIXME: This is only used to quickly check whether a given goal
     // is in the cache. We should experiment with using something like
     // `SsoHashSet` here because in most cases there are only a few entries.
-    pub(super) lookup_table: FxHashMap<CanonicalGoal<'tcx>, EntryIndex>,
+    pub(super) lookup_table: FxHashMap<CanonicalInput<'tcx>, EntryIndex>,
 }
 
 impl<'tcx> ProvisionalCache<'tcx> {
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 050269fa9..19e4b2300 100644
--- a/compiler/rustc_trait_selection/src/solve/search_graph/mod.rs
+++ b/compiler/rustc_trait_selection/src/solve/search_graph/mod.rs
@@ -6,9 +6,9 @@ pub(super) use overflow::OverflowHandler;
 use self::cache::ProvisionalEntry;
 use cache::ProvisionalCache;
 use overflow::OverflowData;
-use rustc_index::vec::IndexVec;
+use rustc_index::IndexVec;
 use rustc_middle::dep_graph::DepKind;
-use rustc_middle::traits::solve::{CanonicalGoal, Certainty, MaybeCause, QueryResult};
+use rustc_middle::traits::solve::{CanonicalInput, Certainty, MaybeCause, QueryResult};
 use rustc_middle::ty::TyCtxt;
 use std::{collections::hash_map::Entry, mem};
 
@@ -19,7 +19,7 @@ rustc_index::newtype_index! {
 }
 
 struct StackElem<'tcx> {
-    goal: CanonicalGoal<'tcx>,
+    input: CanonicalInput<'tcx>,
     has_been_used: bool,
 }
 
@@ -77,7 +77,7 @@ impl<'tcx> SearchGraph<'tcx> {
             }
 
             // ...or it depends on a goal with a lower depth.
-            let current_goal = self.stack[stack_depth].goal;
+            let current_goal = self.stack[stack_depth].input;
             let entry_index = self.provisional_cache.lookup_table[&current_goal];
             self.provisional_cache.entries[entry_index].depth != stack_depth
         } else {
@@ -92,20 +92,20 @@ impl<'tcx> SearchGraph<'tcx> {
     fn try_push_stack(
         &mut self,
         tcx: TyCtxt<'tcx>,
-        goal: CanonicalGoal<'tcx>,
+        input: CanonicalInput<'tcx>,
     ) -> Result<(), QueryResult<'tcx>> {
         // Look at the provisional cache to check for cycles.
         let cache = &mut self.provisional_cache;
-        match cache.lookup_table.entry(goal) {
+        match cache.lookup_table.entry(input) {
             // No entry, simply push this goal on the stack after dealing with overflow.
             Entry::Vacant(v) => {
                 if self.overflow_data.has_overflow(self.stack.len()) {
-                    return Err(self.deal_with_overflow(tcx, goal));
+                    return Err(self.deal_with_overflow(tcx, input));
                 }
 
-                let depth = self.stack.push(StackElem { goal, has_been_used: false });
-                let response = super::response_no_constraints(tcx, goal, Certainty::Yes);
-                let entry_index = cache.entries.push(ProvisionalEntry { response, depth, goal });
+                let depth = self.stack.push(StackElem { input, has_been_used: false });
+                let response = super::response_no_constraints(tcx, input, Certainty::Yes);
+                let entry_index = cache.entries.push(ProvisionalEntry { response, depth, input });
                 v.insert(entry_index);
                 Ok(())
             }
@@ -135,13 +135,13 @@ impl<'tcx> SearchGraph<'tcx> {
                 // the stack is enough.
                 if self.stack.raw[stack_depth.index()..]
                     .iter()
-                    .all(|g| g.goal.value.predicate.is_coinductive(tcx))
+                    .all(|g| g.input.value.goal.predicate.is_coinductive(tcx))
                 {
                     Err(cache.provisional_result(entry_index))
                 } else {
                     Err(super::response_no_constraints(
                         tcx,
-                        goal,
+                        input,
                         Certainty::Maybe(MaybeCause::Overflow),
                     ))
                 }
@@ -161,18 +161,18 @@ 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, actual_goal), ret)]
+    #[instrument(level = "debug", skip(self, actual_input), ret)]
     fn try_finalize_goal(
         &mut self,
-        actual_goal: CanonicalGoal<'tcx>,
+        actual_input: CanonicalInput<'tcx>,
         response: QueryResult<'tcx>,
     ) -> bool {
         let stack_elem = self.stack.pop().unwrap();
-        let StackElem { goal, has_been_used } = stack_elem;
-        assert_eq!(goal, actual_goal);
+        let StackElem { input, has_been_used } = stack_elem;
+        assert_eq!(input, actual_input);
 
         let cache = &mut self.provisional_cache;
-        let provisional_entry_index = *cache.lookup_table.get(&goal).unwrap();
+        let provisional_entry_index = *cache.lookup_table.get(&input).unwrap();
         let provisional_entry = &mut cache.entries[provisional_entry_index];
         // We eagerly update the response in the cache here. If we have to reevaluate
         // this goal we use the new response when hitting a cycle, and we definitely
@@ -194,7 +194,7 @@ impl<'tcx> SearchGraph<'tcx> {
             cache.entries.truncate(provisional_entry_index.index() + 1);
 
             // ...and finally push our goal back on the stack and reevaluate it.
-            self.stack.push(StackElem { goal, has_been_used: false });
+            self.stack.push(StackElem { input, has_been_used: false });
             false
         } else {
             true
@@ -204,17 +204,17 @@ impl<'tcx> SearchGraph<'tcx> {
     pub(super) fn with_new_goal(
         &mut self,
         tcx: TyCtxt<'tcx>,
-        canonical_goal: CanonicalGoal<'tcx>,
+        canonical_input: CanonicalInput<'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");
+            if let Some(result) = tcx.new_solver_evaluation_cache.get(&canonical_input, tcx) {
+                debug!(?canonical_input, ?result, "cache hit");
                 return result;
             }
         }
 
-        match self.try_push_stack(tcx, canonical_goal) {
+        match self.try_push_stack(tcx, canonical_input) {
             Ok(()) => {}
             // Our goal is already on the stack, eager return.
             Err(response) => return response,
@@ -226,19 +226,19 @@ impl<'tcx> SearchGraph<'tcx> {
         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 result = this.deal_with_overflow(tcx, canonical_input);
                     let _ = this.stack.pop().unwrap();
                     result
                 },
                 |this| {
                     let result = loop_body(this);
-                    this.try_finalize_goal(canonical_goal, result).then(|| result)
+                    this.try_finalize_goal(canonical_input, result).then(|| result)
                 },
             )
         });
 
         let cache = &mut self.provisional_cache;
-        let provisional_entry_index = *cache.lookup_table.get(&canonical_goal).unwrap();
+        let provisional_entry_index = *cache.lookup_table.get(&canonical_input).unwrap();
         let provisional_entry = &mut cache.entries[provisional_entry_index];
         let depth = provisional_entry.depth;
 
@@ -254,13 +254,13 @@ impl<'tcx> SearchGraph<'tcx> {
             // 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);
+                let actual_index = cache.lookup_table.remove(&entry.input);
                 debug_assert_eq!(Some(i), actual_index);
                 debug_assert!(entry.depth == depth);
             }
 
             let current_goal = cache.entries.pop().unwrap();
-            let actual_index = cache.lookup_table.remove(&current_goal.goal);
+            let actual_index = cache.lookup_table.remove(&current_goal.input);
             debug_assert_eq!(Some(provisional_entry_index), actual_index);
             debug_assert!(current_goal.depth == depth);
 
@@ -274,7 +274,7 @@ impl<'tcx> SearchGraph<'tcx> {
             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,
+                    current_goal.input,
                     dep_node,
                     current_goal.response,
                 );
diff --git a/compiler/rustc_trait_selection/src/solve/trait_goals.rs b/compiler/rustc_trait_selection/src/solve/trait_goals.rs
index abd11a15a..f722f2813 100644
--- a/compiler/rustc_trait_selection/src/solve/trait_goals.rs
+++ b/compiler/rustc_trait_selection/src/solve/trait_goals.rs
@@ -78,16 +78,17 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> {
         })
     }
 
-    fn consider_implied_clause(
+    fn probe_and_match_goal_against_assumption(
         ecx: &mut EvalCtxt<'_, 'tcx>,
         goal: Goal<'tcx, Self>,
         assumption: ty::Predicate<'tcx>,
-        requirements: impl IntoIterator<Item = Goal<'tcx, ty::Predicate<'tcx>>>,
+        then: impl FnOnce(&mut EvalCtxt<'_, 'tcx>) -> QueryResult<'tcx>,
     ) -> QueryResult<'tcx> {
         if let Some(poly_trait_pred) = assumption.to_opt_poly_trait_pred()
             && poly_trait_pred.def_id() == goal.predicate.def_id()
+            && poly_trait_pred.polarity() == goal.predicate.polarity
         {
-            // FIXME: Constness and polarity
+            // FIXME: Constness
             ecx.probe(|ecx| {
                 let assumption_trait_pred =
                     ecx.instantiate_binder_with_infer(poly_trait_pred);
@@ -96,57 +97,21 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> {
                     goal.predicate.trait_ref,
                     assumption_trait_pred.trait_ref,
                 )?;
-                ecx.add_goals(requirements);
-                ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
+                then(ecx)
             })
         } else {
             Err(NoSolution)
         }
     }
 
-    fn consider_object_bound_candidate(
+    fn consider_auto_trait_candidate(
         ecx: &mut EvalCtxt<'_, 'tcx>,
         goal: Goal<'tcx, Self>,
-        assumption: ty::Predicate<'tcx>,
     ) -> QueryResult<'tcx> {
-        if let Some(poly_trait_pred) = assumption.to_opt_poly_trait_pred()
-            && poly_trait_pred.def_id() == goal.predicate.def_id()
-        {
-            // FIXME: Constness and polarity
-            ecx.probe(|ecx| {
-                let assumption_trait_pred =
-                    ecx.instantiate_binder_with_infer(poly_trait_pred);
-                ecx.eq(
-                    goal.param_env,
-                    goal.predicate.trait_ref,
-                    assumption_trait_pred.trait_ref,
-                )?;
-
-                let tcx = ecx.tcx();
-                let ty::Dynamic(bounds, _, _) = *goal.predicate.self_ty().kind() else {
-                    bug!("expected object type in `consider_object_bound_candidate`");
-                };
-                ecx.add_goals(
-                    structural_traits::predicates_for_object_candidate(
-                        &ecx,
-                        goal.param_env,
-                        goal.predicate.trait_ref,
-                        bounds,
-                    )
-                    .into_iter()
-                    .map(|pred| goal.with(tcx, pred)),
-                );
-                ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
-            })
-        } else {
-            Err(NoSolution)
+        if goal.predicate.polarity != ty::ImplPolarity::Positive {
+            return Err(NoSolution);
         }
-    }
 
-    fn consider_auto_trait_candidate(
-        ecx: &mut EvalCtxt<'_, 'tcx>,
-        goal: Goal<'tcx, Self>,
-    ) -> QueryResult<'tcx> {
         if let Some(result) = ecx.disqualify_auto_trait_candidate_due_to_possible_impl(goal) {
             return result;
         }
@@ -161,6 +126,10 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> {
         ecx: &mut EvalCtxt<'_, 'tcx>,
         goal: Goal<'tcx, Self>,
     ) -> QueryResult<'tcx> {
+        if goal.predicate.polarity != ty::ImplPolarity::Positive {
+            return Err(NoSolution);
+        }
+
         let tcx = ecx.tcx();
 
         ecx.probe(|ecx| {
@@ -176,6 +145,10 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> {
         ecx: &mut EvalCtxt<'_, 'tcx>,
         goal: Goal<'tcx, Self>,
     ) -> QueryResult<'tcx> {
+        if goal.predicate.polarity != ty::ImplPolarity::Positive {
+            return Err(NoSolution);
+        }
+
         ecx.probe_and_evaluate_goal_for_constituent_tys(
             goal,
             structural_traits::instantiate_constituent_tys_for_sized_trait,
@@ -186,6 +159,10 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> {
         ecx: &mut EvalCtxt<'_, 'tcx>,
         goal: Goal<'tcx, Self>,
     ) -> QueryResult<'tcx> {
+        if goal.predicate.polarity != ty::ImplPolarity::Positive {
+            return Err(NoSolution);
+        }
+
         ecx.probe_and_evaluate_goal_for_constituent_tys(
             goal,
             structural_traits::instantiate_constituent_tys_for_copy_clone_trait,
@@ -196,14 +173,22 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> {
         ecx: &mut EvalCtxt<'_, 'tcx>,
         goal: Goal<'tcx, Self>,
     ) -> QueryResult<'tcx> {
-        if goal.predicate.self_ty().has_non_region_infer() {
-            return ecx.evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS);
+        if goal.predicate.polarity != ty::ImplPolarity::Positive {
+            return Err(NoSolution);
         }
 
+        // The regions of a type don't affect the size of the type
         let tcx = ecx.tcx();
-        let self_ty = tcx.erase_regions(goal.predicate.self_ty());
+        // We should erase regions from both the param-env and type, since both
+        // may have infer regions. Specifically, after canonicalizing and instantiating,
+        // early bound regions turn into region vars in both the new and old solver.
+        let key = tcx.erase_regions(goal.param_env.and(goal.predicate.self_ty()));
+        // But if there are inference variables, we have to wait until it's resolved.
+        if key.has_non_region_infer() {
+            return ecx.evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS);
+        }
 
-        if let Ok(layout) = tcx.layout_of(goal.param_env.and(self_ty))
+        if let Ok(layout) = tcx.layout_of(key)
             && layout.layout.is_pointer_like(&tcx.data_layout)
         {
             // FIXME: We could make this faster by making a no-constraints response
@@ -217,6 +202,10 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> {
         ecx: &mut EvalCtxt<'_, 'tcx>,
         goal: Goal<'tcx, Self>,
     ) -> QueryResult<'tcx> {
+        if goal.predicate.polarity != ty::ImplPolarity::Positive {
+            return Err(NoSolution);
+        }
+
         if let ty::FnPtr(..) = goal.predicate.self_ty().kind() {
             ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
         } else {
@@ -229,6 +218,10 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> {
         goal: Goal<'tcx, Self>,
         goal_kind: ty::ClosureKind,
     ) -> QueryResult<'tcx> {
+        if goal.predicate.polarity != ty::ImplPolarity::Positive {
+            return Err(NoSolution);
+        }
+
         let tcx = ecx.tcx();
         let tupled_inputs_and_output =
             match structural_traits::extract_tupled_inputs_and_output_from_callable(
@@ -242,12 +235,13 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> {
                         .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]));
+        let output_is_sized_pred = tupled_inputs_and_output.map_bound(|(_, output)| {
+            ty::TraitRef::from_lang_item(tcx, LangItem::Sized, DUMMY_SP, [output])
+        });
 
         let pred = tupled_inputs_and_output
             .map_bound(|(inputs, _)| {
-                tcx.mk_trait_ref(goal.predicate.def_id(), [goal.predicate.self_ty(), inputs])
+                ty::TraitRef::new(tcx, goal.predicate.def_id(), [goal.predicate.self_ty(), inputs])
             })
             .to_predicate(tcx);
         // A built-in `Fn` impl only holds if the output is sized.
@@ -259,6 +253,10 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> {
         ecx: &mut EvalCtxt<'_, 'tcx>,
         goal: Goal<'tcx, Self>,
     ) -> QueryResult<'tcx> {
+        if goal.predicate.polarity != ty::ImplPolarity::Positive {
+            return Err(NoSolution);
+        }
+
         if let ty::Tuple(..) = goal.predicate.self_ty().kind() {
             ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
         } else {
@@ -268,8 +266,12 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> {
 
     fn consider_builtin_pointee_candidate(
         ecx: &mut EvalCtxt<'_, 'tcx>,
-        _goal: Goal<'tcx, Self>,
+        goal: Goal<'tcx, Self>,
     ) -> QueryResult<'tcx> {
+        if goal.predicate.polarity != ty::ImplPolarity::Positive {
+            return Err(NoSolution);
+        }
+
         ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
     }
 
@@ -277,6 +279,10 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> {
         ecx: &mut EvalCtxt<'_, 'tcx>,
         goal: Goal<'tcx, Self>,
     ) -> QueryResult<'tcx> {
+        if goal.predicate.polarity != ty::ImplPolarity::Positive {
+            return Err(NoSolution);
+        }
+
         let ty::Generator(def_id, _, _) = *goal.predicate.self_ty().kind() else {
             return Err(NoSolution);
         };
@@ -297,6 +303,10 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> {
         ecx: &mut EvalCtxt<'_, 'tcx>,
         goal: Goal<'tcx, Self>,
     ) -> QueryResult<'tcx> {
+        if goal.predicate.polarity != ty::ImplPolarity::Positive {
+            return Err(NoSolution);
+        }
+
         let self_ty = goal.predicate.self_ty();
         let ty::Generator(def_id, substs, _) = *self_ty.kind() else {
             return Err(NoSolution);
@@ -312,10 +322,8 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> {
         Self::consider_implied_clause(
             ecx,
             goal,
-            ty::Binder::dummy(
-                tcx.mk_trait_ref(goal.predicate.def_id(), [self_ty, generator.resume_ty()]),
-            )
-            .to_predicate(tcx),
+            ty::TraitRef::new(tcx, goal.predicate.def_id(), [self_ty, generator.resume_ty()])
+                .to_predicate(tcx),
             // Technically, we need to check that the generator types are Sized,
             // but that's already proven by the generator being WF.
             [],
@@ -326,6 +334,10 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> {
         ecx: &mut EvalCtxt<'_, 'tcx>,
         goal: Goal<'tcx, Self>,
     ) -> QueryResult<'tcx> {
+        if goal.predicate.polarity != ty::ImplPolarity::Positive {
+            return Err(NoSolution);
+        }
+
         let tcx = ecx.tcx();
         let a_ty = goal.predicate.self_ty();
         let b_ty = goal.predicate.trait_ref.substs.type_at(1);
@@ -346,7 +358,7 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> {
                     // Can only unsize to an object-safe type
                     if data
                         .principal_def_id()
-                        .map_or(false, |def_id| !tcx.check_is_object_safe(def_id))
+                        .is_some_and(|def_id| !tcx.check_is_object_safe(def_id))
                     {
                         return Err(NoSolution);
                     }
@@ -360,9 +372,7 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> {
                         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]))),
-                    );
+                    ecx.add_goal(goal.with(tcx, ty::TraitRef::new(tcx, 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))),
@@ -411,9 +421,7 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> {
                     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]),
-                        ),
+                        ty::TraitRef::new(tcx, goal.predicate.def_id(), [a_tail_ty, b_tail_ty]),
                     ));
                     ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
                 }
@@ -432,9 +440,7 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> {
                     // Similar to ADTs, require that the rest of the fields are equal.
                     ecx.add_goal(goal.with(
                         tcx,
-                        ty::Binder::dummy(
-                            tcx.mk_trait_ref(goal.predicate.def_id(), [*a_last_ty, *b_last_ty]),
-                        ),
+                        ty::TraitRef::new(tcx, goal.predicate.def_id(), [*a_last_ty, *b_last_ty]),
                     ));
                     ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
                 }
@@ -447,6 +453,10 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> {
         ecx: &mut EvalCtxt<'_, 'tcx>,
         goal: Goal<'tcx, Self>,
     ) -> Vec<CanonicalResponse<'tcx>> {
+        if goal.predicate.polarity != ty::ImplPolarity::Positive {
+            return vec![];
+        }
+
         let tcx = ecx.tcx();
 
         let a_ty = goal.predicate.self_ty();
@@ -521,8 +531,12 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> {
 
     fn consider_builtin_discriminant_kind_candidate(
         ecx: &mut EvalCtxt<'_, 'tcx>,
-        _goal: Goal<'tcx, Self>,
+        goal: Goal<'tcx, Self>,
     ) -> QueryResult<'tcx> {
+        if goal.predicate.polarity != ty::ImplPolarity::Positive {
+            return Err(NoSolution);
+        }
+
         // `DiscriminantKind` is automatically implemented for every type.
         ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
     }
@@ -531,6 +545,10 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> {
         ecx: &mut EvalCtxt<'_, 'tcx>,
         goal: Goal<'tcx, Self>,
     ) -> QueryResult<'tcx> {
+        if goal.predicate.polarity != ty::ImplPolarity::Positive {
+            return Err(NoSolution);
+        }
+
         if !goal.param_env.is_const() {
             // `Destruct` is automatically implemented for every type in
             // non-const environments.
@@ -545,6 +563,10 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> {
         ecx: &mut EvalCtxt<'_, 'tcx>,
         goal: Goal<'tcx, Self>,
     ) -> QueryResult<'tcx> {
+        if goal.predicate.polarity != ty::ImplPolarity::Positive {
+            return Err(NoSolution);
+        }
+
         // `rustc_transmute` does not have support for type or const params
         if goal.has_non_region_placeholders() {
             return Err(NoSolution);
@@ -591,12 +613,12 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
                 Some(self.evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS))
             }
 
-            // These types cannot be structurally decomposed into constitutent
+            // These types cannot be structurally decomposed into constituent
             // types, and therefore have no built-in auto impl.
             ty::Dynamic(..)
             | ty::Param(..)
             | ty::Foreign(..)
-            | ty::Alias(ty::Projection, ..)
+            | ty::Alias(ty::Projection | ty::Inherent, ..)
             | ty::Placeholder(..) => Some(Err(NoSolution)),
 
             ty::Infer(_) | ty::Bound(_, _) => bug!("unexpected type `{self_ty}`"),
@@ -645,12 +667,16 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
             // 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(
+                let mut disqualifying_impl = None;
+                self.tcx().for_each_relevant_impl_treating_projections(
                     goal.predicate.def_id(),
                     goal.predicate.self_ty(),
                     TreatProjections::NextSolverLookup,
-                    Some,
-                ) {
+                    |impl_def_id| {
+                        disqualifying_impl = Some(impl_def_id);
+                    },
+                );
+                if let Some(def_id) = disqualifying_impl {
                     debug!(?def_id, ?goal, "disqualified auto-trait implementation");
                     // No need to actually consider the candidate here,
                     // since we do that in `consider_impl_candidate`.