Rollup merge of #122687 - lcnr:normalizes-to-emit-nested-goals, r=compiler-errors

`NormalizesTo`: return nested goals to caller

Fixes the regression of `paperclip-core`. see https://hackmd.io/IsVAafiOTAaPIFcUxRJufw for more details.

r? ```@compiler-errors```

14 files changed, 189 insertions, 156 deletions

diff --git a/compiler/rustc_trait_selection/src/solve/alias_relate.rs b/compiler/rustc_trait_selection/src/solve/alias_relate.rs
index 67657c81cf6..e081a9100e2 100644
--- a/compiler/rustc_trait_selection/src/solve/alias_relate.rs
+++ b/compiler/rustc_trait_selection/src/solve/alias_relate.rs
@@ -21,8 +21,9 @@
 //! However, if `?fresh_var` ends up geteting equated to another type, we retry the
 //! `NormalizesTo` goal, at which point the opaque is actually defined.
 
-use super::{EvalCtxt, GoalSource};
+use super::EvalCtxt;
 use rustc_infer::traits::query::NoSolution;
+use rustc_infer::traits::solve::GoalSource;
 use rustc_middle::traits::solve::{Certainty, Goal, QueryResult};
 use rustc_middle::ty::{self, Ty};
 
@@ -121,10 +122,11 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
             ty::TermKind::Const(_) => {
                 if let Some(alias) = term.to_alias_ty(self.tcx()) {
                     let term = self.next_term_infer_of_kind(term);
-                    self.add_goal(
-                        GoalSource::Misc,
-                        Goal::new(self.tcx(), param_env, ty::NormalizesTo { alias, term }),
-                    );
+                    self.add_normalizes_to_goal(Goal::new(
+                        self.tcx(),
+                        param_env,
+                        ty::NormalizesTo { alias, term },
+                    ));
                     self.try_evaluate_added_goals()?;
                     Ok(Some(self.resolve_vars_if_possible(term)))
                 } else {
@@ -145,18 +147,25 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
             return None;
         }
 
-        let ty::Alias(_, alias) = *ty.kind() else {
+        let ty::Alias(kind, alias) = *ty.kind() else {
             return Some(ty);
         };
 
         match self.commit_if_ok(|this| {
+            let tcx = this.tcx();
             let normalized_ty = this.next_ty_infer();
-            let normalizes_to_goal = Goal::new(
-                this.tcx(),
-                param_env,
-                ty::NormalizesTo { alias, term: normalized_ty.into() },
-            );
-            this.add_goal(GoalSource::Misc, normalizes_to_goal);
+            let normalizes_to = ty::NormalizesTo { alias, term: normalized_ty.into() };
+            match kind {
+                ty::AliasKind::Opaque => {
+                    // HACK: Unlike for associated types, `normalizes-to` for opaques
+                    // is currently not treated as a function. We do not erase the
+                    // expected term.
+                    this.add_goal(GoalSource::Misc, Goal::new(tcx, param_env, normalizes_to));
+                }
+                ty::AliasKind::Projection | ty::AliasKind::Inherent | ty::AliasKind::Weak => {
+                    this.add_normalizes_to_goal(Goal::new(tcx, param_env, normalizes_to))
+                }
+            }
             this.try_evaluate_added_goals()?;
             Ok(this.resolve_vars_if_possible(normalized_ty))
         }) {
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 251b0a193f1..619435d2e8d 100644
--- a/compiler/rustc_trait_selection/src/solve/eval_ctxt/canonical.rs
+++ b/compiler/rustc_trait_selection/src/solve/eval_ctxt/canonical.rs
@@ -9,6 +9,7 @@
 //!
 //! [c]: https://rustc-dev-guide.rust-lang.org/solve/canonicalization.html
 use super::{CanonicalInput, Certainty, EvalCtxt, Goal};
+use crate::solve::eval_ctxt::NestedGoals;
 use crate::solve::{
     inspect, response_no_constraints_raw, CanonicalResponse, QueryResult, Response,
 };
@@ -19,6 +20,7 @@ use rustc_infer::infer::canonical::CanonicalVarValues;
 use rustc_infer::infer::canonical::{CanonicalExt, QueryRegionConstraints};
 use rustc_infer::infer::resolve::EagerResolver;
 use rustc_infer::infer::{InferCtxt, InferOk};
+use rustc_infer::traits::solve::NestedNormalizationGoals;
 use rustc_middle::infer::canonical::Canonical;
 use rustc_middle::traits::query::NoSolution;
 use rustc_middle::traits::solve::{
@@ -28,6 +30,7 @@ use rustc_middle::traits::ObligationCause;
 use rustc_middle::ty::{self, BoundVar, GenericArgKind, Ty, TyCtxt, TypeFoldable};
 use rustc_next_trait_solver::canonicalizer::{CanonicalizeMode, Canonicalizer};
 use rustc_span::DUMMY_SP;
+use std::assert_matches::assert_matches;
 use std::iter;
 use std::ops::Deref;
 
@@ -93,13 +96,31 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
             previous call to `try_evaluate_added_goals!`"
         );
 
-        let certainty = certainty.unify_with(goals_certainty);
-
-        let var_values = self.var_values;
-        let external_constraints = self.compute_external_query_constraints()?;
-
+        // When normalizing, we've replaced the expected term with an unconstrained
+        // inference variable. This means that we dropped information which could
+        // have been important. We handle this by instead returning the nested goals
+        // to the caller, where they are then handled.
+        //
+        // As we return all ambiguous nested goals, we can ignore the certainty returned
+        // by `try_evaluate_added_goals()`.
+        let (certainty, normalization_nested_goals) = if self.is_normalizes_to_goal {
+            let NestedGoals { normalizes_to_goals, goals } = std::mem::take(&mut self.nested_goals);
+            if cfg!(debug_assertions) {
+                assert!(normalizes_to_goals.is_empty());
+                if goals.is_empty() {
+                    assert_matches!(goals_certainty, Certainty::Yes);
+                }
+            }
+            (certainty, NestedNormalizationGoals(goals))
+        } else {
+            let certainty = certainty.unify_with(goals_certainty);
+            (certainty, NestedNormalizationGoals::empty())
+        };
+
+        let external_constraints =
+            self.compute_external_query_constraints(normalization_nested_goals)?;
         let (var_values, mut external_constraints) =
-            (var_values, external_constraints).fold_with(&mut EagerResolver::new(self.infcx));
+            (self.var_values, external_constraints).fold_with(&mut EagerResolver::new(self.infcx));
         // Remove any trivial region constraints once we've resolved regions
         external_constraints
             .region_constraints
@@ -146,6 +167,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
     #[instrument(level = "debug", skip(self), ret)]
     fn compute_external_query_constraints(
         &self,
+        normalization_nested_goals: NestedNormalizationGoals<'tcx>,
     ) -> Result<ExternalConstraintsData<'tcx>, NoSolution> {
         // We only check for leaks from universes which were entered inside
         // of the query.
@@ -176,7 +198,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
             self.predefined_opaques_in_body.opaque_types.iter().all(|(pa, _)| pa != a)
         });
 
-        Ok(ExternalConstraintsData { region_constraints, opaque_types })
+        Ok(ExternalConstraintsData { region_constraints, opaque_types, normalization_nested_goals })
     }
 
     /// After calling a canonical query, we apply the constraints returned
@@ -185,13 +207,14 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
     /// This happens in three steps:
     /// - we instantiate the bound variables of the query response
     /// - we unify the `var_values` of the response with the `original_values`
-    /// - we apply the `external_constraints` returned by the query
+    /// - we apply the `external_constraints` returned by the query, returning
+    ///   the `normalization_nested_goals`
     pub(super) fn instantiate_and_apply_query_response(
         &mut self,
         param_env: ty::ParamEnv<'tcx>,
         original_values: Vec<ty::GenericArg<'tcx>>,
         response: CanonicalResponse<'tcx>,
-    ) -> Certainty {
+    ) -> (NestedNormalizationGoals<'tcx>, Certainty) {
         let instantiation = Self::compute_query_response_instantiation_values(
             self.infcx,
             &original_values,
@@ -203,11 +226,14 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
 
         Self::unify_query_var_values(self.infcx, param_env, &original_values, var_values);
 
-        let ExternalConstraintsData { region_constraints, opaque_types } =
-            external_constraints.deref();
+        let ExternalConstraintsData {
+            region_constraints,
+            opaque_types,
+            normalization_nested_goals,
+        } = external_constraints.deref();
         self.register_region_constraints(region_constraints);
         self.register_new_opaque_types(param_env, opaque_types);
-        certainty
+        (normalization_nested_goals.clone(), certainty)
     }
 
     /// This returns the canoncial variable values to instantiate the bound variables of
diff --git a/compiler/rustc_trait_selection/src/solve/eval_ctxt/commit_if_ok.rs b/compiler/rustc_trait_selection/src/solve/eval_ctxt/commit_if_ok.rs
index 67b6801059a..c8f9a461adf 100644
--- a/compiler/rustc_trait_selection/src/solve/eval_ctxt/commit_if_ok.rs
+++ b/compiler/rustc_trait_selection/src/solve/eval_ctxt/commit_if_ok.rs
@@ -11,6 +11,7 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> {
             infcx: self.infcx,
             variables: self.variables,
             var_values: self.var_values,
+            is_normalizes_to_goal: self.is_normalizes_to_goal,
             predefined_opaques_in_body: self.predefined_opaques_in_body,
             max_input_universe: self.max_input_universe,
             search_graph: self.search_graph,
@@ -25,6 +26,7 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> {
                 infcx: _,
                 variables: _,
                 var_values: _,
+                is_normalizes_to_goal: _,
                 predefined_opaques_in_body: _,
                 max_input_universe: _,
                 search_graph: _,
diff --git a/compiler/rustc_trait_selection/src/solve/eval_ctxt/mod.rs b/compiler/rustc_trait_selection/src/solve/eval_ctxt/mod.rs
index a4ee0e03e65..a0fe6eca0fc 100644
--- a/compiler/rustc_trait_selection/src/solve/eval_ctxt/mod.rs
+++ b/compiler/rustc_trait_selection/src/solve/eval_ctxt/mod.rs
@@ -7,14 +7,14 @@ use rustc_infer::infer::{
     BoundRegionConversionTime, DefineOpaqueTypes, InferCtxt, InferOk, TyCtxtInferExt,
 };
 use rustc_infer::traits::query::NoSolution;
-use rustc_infer::traits::solve::MaybeCause;
+use rustc_infer::traits::solve::{MaybeCause, NestedNormalizationGoals};
 use rustc_infer::traits::ObligationCause;
 use rustc_middle::infer::canonical::CanonicalVarInfos;
 use rustc_middle::infer::unify_key::{ConstVariableOrigin, ConstVariableOriginKind};
 use rustc_middle::traits::solve::inspect;
 use rustc_middle::traits::solve::{
-    CanonicalInput, CanonicalResponse, Certainty, IsNormalizesToHack, PredefinedOpaques,
-    PredefinedOpaquesData, QueryResult,
+    CanonicalInput, CanonicalResponse, Certainty, PredefinedOpaques, PredefinedOpaquesData,
+    QueryResult,
 };
 use rustc_middle::traits::specialization_graph;
 use rustc_middle::ty::{
@@ -61,6 +61,14 @@ pub struct EvalCtxt<'a, 'tcx> {
     /// The variable info for the `var_values`, only used to make an ambiguous response
     /// with no constraints.
     variables: CanonicalVarInfos<'tcx>,
+    /// Whether we're currently computing a `NormalizesTo` goal. Unlike other goals,
+    /// `NormalizesTo` goals act like functions with the expected term always being
+    /// fully unconstrained. This would weaken inference however, as the nested goals
+    /// never get the inference constraints from the actual normalized-to type. Because
+    /// of this we return any ambiguous nested goals from `NormalizesTo` to the caller
+    /// when then adds these to its own context. The caller is always an `AliasRelate`
+    /// goal so this never leaks out of the solver.
+    is_normalizes_to_goal: bool,
     pub(super) var_values: CanonicalVarValues<'tcx>,
 
     predefined_opaques_in_body: PredefinedOpaques<'tcx>,
@@ -91,9 +99,9 @@ pub struct EvalCtxt<'a, 'tcx> {
     pub(super) inspect: ProofTreeBuilder<'tcx>,
 }
 
-#[derive(Debug, Clone)]
+#[derive(Default, Debug, Clone)]
 pub(super) struct NestedGoals<'tcx> {
-    /// This normalizes-to goal that is treated specially during the evaluation
+    /// These normalizes-to goals are 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.
@@ -101,26 +109,24 @@ pub(super) struct NestedGoals<'tcx> {
     /// 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::NormalizesTo<'tcx>>>,
+    /// Forgetting to replace the RHS with a fresh inference variable when we evaluate
+    /// this goal results in an ICE..
+    pub(super) normalizes_to_goals: Vec<Goal<'tcx, ty::NormalizesTo<'tcx>>>,
     /// The rest of the goals which have not yet processed or remain ambiguous.
     pub(super) goals: Vec<(GoalSource, Goal<'tcx, ty::Predicate<'tcx>>)>,
 }
 
 impl<'tcx> NestedGoals<'tcx> {
     pub(super) fn new() -> Self {
-        Self { normalizes_to_hack_goal: None, goals: Vec::new() }
+        Self { normalizes_to_goals: Vec::new(), goals: Vec::new() }
     }
 
     pub(super) fn is_empty(&self) -> bool {
-        self.normalizes_to_hack_goal.is_none() && self.goals.is_empty()
+        self.normalizes_to_goals.is_empty() && self.goals.is_empty()
     }
 
     pub(super) fn extend(&mut self, other: NestedGoals<'tcx>) {
-        assert_eq!(other.normalizes_to_hack_goal, None);
+        self.normalizes_to_goals.extend(other.normalizes_to_goals);
         self.goals.extend(other.goals)
     }
 }
@@ -155,6 +161,10 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> {
         self.search_graph.solver_mode()
     }
 
+    pub(super) fn set_is_normalizes_to_goal(&mut self) {
+        self.is_normalizes_to_goal = true;
+    }
+
     /// Creates a root evaluation context and search graph. This should only be
     /// used from outside of any evaluation, and other methods should be preferred
     /// over using this manually (such as [`InferCtxtEvalExt::evaluate_root_goal`]).
@@ -167,8 +177,8 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> {
         let mut search_graph = search_graph::SearchGraph::new(mode);
 
         let mut ecx = EvalCtxt {
-            search_graph: &mut search_graph,
             infcx,
+            search_graph: &mut search_graph,
             nested_goals: NestedGoals::new(),
             inspect: ProofTreeBuilder::new_maybe_root(infcx.tcx, generate_proof_tree),
 
@@ -180,6 +190,7 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> {
             max_input_universe: ty::UniverseIndex::ROOT,
             variables: ty::List::empty(),
             var_values: CanonicalVarValues::dummy(),
+            is_normalizes_to_goal: false,
             tainted: Ok(()),
         };
         let result = f(&mut ecx);
@@ -233,6 +244,7 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> {
             infcx,
             variables: canonical_input.variables,
             var_values,
+            is_normalizes_to_goal: false,
             predefined_opaques_in_body: input.predefined_opaques_in_body,
             max_input_universe: canonical_input.max_universe,
             search_graph,
@@ -319,6 +331,27 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> {
         source: GoalSource,
         goal: Goal<'tcx, ty::Predicate<'tcx>>,
     ) -> Result<(bool, Certainty), NoSolution> {
+        let (normalization_nested_goals, has_changed, certainty) =
+            self.evaluate_goal_raw(goal_evaluation_kind, source, goal)?;
+        assert!(normalization_nested_goals.is_empty());
+        Ok((has_changed, certainty))
+    }
+
+    /// Recursively evaluates `goal`, returning the nested goals in case
+    /// the nested goal is a `NormalizesTo` goal.
+    ///
+    /// As all other goal kinds do not return any nested goals and
+    /// `NormalizesTo` is only used by `AliasRelate`, all other callsites
+    /// should use [`EvalCtxt::evaluate_goal`] which discards that empty
+    /// storage.
+    // FIXME(-Znext-solver=coinduction): `_source` is currently unused but will
+    // be necessary once we implement the new coinduction approach.
+    fn evaluate_goal_raw(
+        &mut self,
+        goal_evaluation_kind: GoalEvaluationKind,
+        _source: GoalSource,
+        goal: Goal<'tcx, ty::Predicate<'tcx>>,
+    ) -> Result<(NestedNormalizationGoals<'tcx>, bool, Certainty), NoSolution> {
         let (orig_values, canonical_goal) = self.canonicalize_goal(goal);
         let mut goal_evaluation =
             self.inspect.new_goal_evaluation(goal, &orig_values, goal_evaluation_kind);
@@ -336,12 +369,12 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> {
             Ok(response) => response,
         };
 
-        let (certainty, has_changed) = self.instantiate_response_discarding_overflow(
-            goal.param_env,
-            source,
-            orig_values,
-            canonical_response,
-        );
+        let (normalization_nested_goals, certainty, has_changed) = self
+            .instantiate_response_discarding_overflow(
+                goal.param_env,
+                orig_values,
+                canonical_response,
+            );
         self.inspect.goal_evaluation(goal_evaluation);
         // FIXME: We previously had an assert here that checked that recomputing
         // a goal after applying its constraints did not change its response.
@@ -353,47 +386,25 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> {
         // Once we have decided on how to handle trait-system-refactor-initiative#75,
         // we should re-add an assert here.
 
-        Ok((has_changed, certainty))
+        Ok((normalization_nested_goals, has_changed, certainty))
     }
 
     fn instantiate_response_discarding_overflow(
         &mut self,
         param_env: ty::ParamEnv<'tcx>,
-        source: GoalSource,
         original_values: Vec<ty::GenericArg<'tcx>>,
         response: CanonicalResponse<'tcx>,
-    ) -> (Certainty, bool) {
-        // The old solver did not evaluate nested goals when normalizing.
-        // It returned the selection constraints allowing a `Projection`
-        // obligation to not hold in coherence while avoiding the fatal error
-        // from overflow.
-        //
-        // We match this behavior here by considering all constraints
-        // from nested goals which are not from where-bounds. We will already
-        // need to track which nested goals are required by impl where-bounds
-        // for coinductive cycles, so we simply reuse that here.
-        //
-        // While we could consider overflow constraints in more cases, this should
-        // not be necessary for backcompat and results in better perf. It also
-        // avoids a potential inconsistency which would otherwise require some
-        // tracking for root goals as well. See #119071 for an example.
-        let keep_overflow_constraints = || {
-            self.search_graph.current_goal_is_normalizes_to()
-                && source != GoalSource::ImplWhereBound
-        };
-
-        if let Certainty::Maybe(MaybeCause::Overflow { .. }) = response.value.certainty
-            && !keep_overflow_constraints()
-        {
-            return (response.value.certainty, false);
+    ) -> (NestedNormalizationGoals<'tcx>, Certainty, bool) {
+        if let Certainty::Maybe(MaybeCause::Overflow { .. }) = response.value.certainty {
+            return (NestedNormalizationGoals::empty(), response.value.certainty, false);
         }
 
         let has_changed = !response.value.var_values.is_identity_modulo_regions()
             || !response.value.external_constraints.opaque_types.is_empty();
 
-        let certainty =
+        let (normalization_nested_goals, certainty) =
             self.instantiate_and_apply_query_response(param_env, original_values, response);
-        (certainty, has_changed)
+        (normalization_nested_goals, certainty, has_changed)
     }
 
     fn compute_goal(&mut self, goal: Goal<'tcx, ty::Predicate<'tcx>>) -> QueryResult<'tcx> {
@@ -496,7 +507,7 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> {
     /// Goals for the next step get directly added to the nested goals of the `EvalCtxt`.
     fn evaluate_added_goals_step(&mut self) -> Result<Option<Certainty>, NoSolution> {
         let tcx = self.tcx();
-        let mut goals = core::mem::replace(&mut self.nested_goals, NestedGoals::new());
+        let mut goals = core::mem::take(&mut self.nested_goals);
 
         self.inspect.evaluate_added_goals_loop_start();
 
@@ -508,7 +519,7 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> {
 
         // If this loop did not result in any progress, what's our final certainty.
         let mut unchanged_certainty = Some(Certainty::Yes);
-        if let Some(goal) = goals.normalizes_to_hack_goal.take() {
+        for goal in goals.normalizes_to_goals {
             // Replace the goal with an unconstrained infer var, so the
             // RHS does not affect projection candidate assembly.
             let unconstrained_rhs = self.next_term_infer_of_kind(goal.predicate.term);
@@ -517,11 +528,13 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> {
                 ty::NormalizesTo { alias: goal.predicate.alias, term: unconstrained_rhs },
             );
 
-            let (_, certainty) = self.evaluate_goal(
-                GoalEvaluationKind::Nested { is_normalizes_to_hack: IsNormalizesToHack::Yes },
+            let (NestedNormalizationGoals(nested_goals), _, certainty) = self.evaluate_goal_raw(
+                GoalEvaluationKind::Nested,
                 GoalSource::Misc,
                 unconstrained_goal,
             )?;
+            // Add the nested goals from normalization to our own nested goals.
+            goals.goals.extend(nested_goals);
 
             // Finally, equate the goal's RHS with the unconstrained var.
             // We put the nested goals from this into goals instead of
@@ -536,27 +549,23 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> {
             // 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.alias != self.resolve_vars_if_possible(goal.predicate.alias) {
+            let with_resolved_vars = self.resolve_vars_if_possible(goal);
+            if goal.predicate.alias != with_resolved_vars.predicate.alias {
                 unchanged_certainty = None;
             }
 
             match certainty {
                 Certainty::Yes => {}
                 Certainty::Maybe(_) => {
-                    // We need to resolve vars here so that we correctly
-                    // deal with `has_changed` in the next iteration.
-                    self.set_normalizes_to_hack_goal(self.resolve_vars_if_possible(goal));
+                    self.nested_goals.normalizes_to_goals.push(with_resolved_vars);
                     unchanged_certainty = unchanged_certainty.map(|c| c.unify_with(certainty));
                 }
             }
         }
 
-        for (source, goal) in goals.goals.drain(..) {
-            let (has_changed, certainty) = self.evaluate_goal(
-                GoalEvaluationKind::Nested { is_normalizes_to_hack: IsNormalizesToHack::No },
-                source,
-                goal,
-            )?;
+        for (source, goal) in goals.goals {
+            let (has_changed, certainty) =
+                self.evaluate_goal(GoalEvaluationKind::Nested, source, goal)?;
             if has_changed {
                 unchanged_certainty = None;
             }
diff --git a/compiler/rustc_trait_selection/src/solve/eval_ctxt/probe.rs b/compiler/rustc_trait_selection/src/solve/eval_ctxt/probe.rs
index 91fd48807a4..5b1124e8b9f 100644
--- a/compiler/rustc_trait_selection/src/solve/eval_ctxt/probe.rs
+++ b/compiler/rustc_trait_selection/src/solve/eval_ctxt/probe.rs
@@ -24,6 +24,7 @@ where
             infcx: outer_ecx.infcx,
             variables: outer_ecx.variables,
             var_values: outer_ecx.var_values,
+            is_normalizes_to_goal: outer_ecx.is_normalizes_to_goal,
             predefined_opaques_in_body: outer_ecx.predefined_opaques_in_body,
             max_input_universe: outer_ecx.max_input_universe,
             search_graph: outer_ecx.search_graph,
diff --git a/compiler/rustc_trait_selection/src/solve/eval_ctxt/select.rs b/compiler/rustc_trait_selection/src/solve/eval_ctxt/select.rs
index 3262d64cb7d..e0c7804b6db 100644
--- a/compiler/rustc_trait_selection/src/solve/eval_ctxt/select.rs
+++ b/compiler/rustc_trait_selection/src/solve/eval_ctxt/select.rs
@@ -58,12 +58,13 @@ impl<'tcx> InferCtxt<'tcx> {
                 }
 
                 let candidate = candidates.pop().unwrap();
-                let certainty = ecx.instantiate_and_apply_query_response(
-                    trait_goal.param_env,
-                    orig_values,
-                    candidate.result,
-                );
-
+                let (normalization_nested_goals, certainty) = ecx
+                    .instantiate_and_apply_query_response(
+                        trait_goal.param_env,
+                        orig_values,
+                        candidate.result,
+                    );
+                assert!(normalization_nested_goals.is_empty());
                 Ok(Some((candidate, certainty)))
             });
 
diff --git a/compiler/rustc_trait_selection/src/solve/inspect/analyse.rs b/compiler/rustc_trait_selection/src/solve/inspect/analyse.rs
index 9e3e6a4676e..cfec2e9bbf3 100644
--- a/compiler/rustc_trait_selection/src/solve/inspect/analyse.rs
+++ b/compiler/rustc_trait_selection/src/solve/inspect/analyse.rs
@@ -70,7 +70,19 @@ impl<'a, 'tcx> InspectCandidate<'a, 'tcx> {
                     instantiated_goals.push(goal);
                 }
 
-                for &goal in &instantiated_goals {
+                for goal in instantiated_goals.iter().copied() {
+                    // We need to be careful with `NormalizesTo` goals as the
+                    // expected term has to be replaced with an unconstrained
+                    // inference variable.
+                    if let Some(kind) = goal.predicate.kind().no_bound_vars()
+                        && let ty::PredicateKind::NormalizesTo(predicate) = kind
+                        && !predicate.alias.is_opaque(infcx.tcx)
+                    {
+                        // FIXME: We currently skip these goals as
+                        // `fn evaluate_root_goal` ICEs if there are any
+                        // `NestedNormalizationGoals`.
+                        continue;
+                    };
                     let (_, proof_tree) = infcx.evaluate_root_goal(goal, GenerateProofTree::Yes);
                     let proof_tree = proof_tree.unwrap();
                     try_visit!(visitor.visit_goal(&InspectGoal::new(
diff --git a/compiler/rustc_trait_selection/src/solve/inspect/build.rs b/compiler/rustc_trait_selection/src/solve/inspect/build.rs
index f7b310a7abe..4da999f2406 100644
--- a/compiler/rustc_trait_selection/src/solve/inspect/build.rs
+++ b/compiler/rustc_trait_selection/src/solve/inspect/build.rs
@@ -7,7 +7,7 @@ use std::mem;
 
 use rustc_middle::traits::query::NoSolution;
 use rustc_middle::traits::solve::{
-    CanonicalInput, Certainty, Goal, GoalSource, IsNormalizesToHack, QueryInput, QueryResult,
+    CanonicalInput, Certainty, Goal, GoalSource, QueryInput, QueryResult,
 };
 use rustc_middle::ty::{self, TyCtxt};
 use rustc_session::config::DumpSolverProofTree;
@@ -97,9 +97,7 @@ impl<'tcx> WipGoalEvaluation<'tcx> {
                 WipGoalEvaluationKind::Root { orig_values } => {
                     inspect::GoalEvaluationKind::Root { orig_values }
                 }
-                WipGoalEvaluationKind::Nested { is_normalizes_to_hack } => {
-                    inspect::GoalEvaluationKind::Nested { is_normalizes_to_hack }
-                }
+                WipGoalEvaluationKind::Nested => inspect::GoalEvaluationKind::Nested,
             },
             evaluation: self.evaluation.unwrap().finalize(),
         }
@@ -109,7 +107,7 @@ impl<'tcx> WipGoalEvaluation<'tcx> {
 #[derive(Eq, PartialEq, Debug)]
 pub(in crate::solve) enum WipGoalEvaluationKind<'tcx> {
     Root { orig_values: Vec<ty::GenericArg<'tcx>> },
-    Nested { is_normalizes_to_hack: IsNormalizesToHack },
+    Nested,
 }
 
 #[derive(Eq, PartialEq)]
@@ -305,9 +303,7 @@ impl<'tcx> ProofTreeBuilder<'tcx> {
                 solve::GoalEvaluationKind::Root => {
                     WipGoalEvaluationKind::Root { orig_values: orig_values.to_vec() }
                 }
-                solve::GoalEvaluationKind::Nested { is_normalizes_to_hack } => {
-                    WipGoalEvaluationKind::Nested { is_normalizes_to_hack }
-                }
+                solve::GoalEvaluationKind::Nested => WipGoalEvaluationKind::Nested,
             },
             evaluation: None,
         })
@@ -419,6 +415,17 @@ impl<'tcx> ProofTreeBuilder<'tcx> {
         }
     }
 
+    pub fn add_normalizes_to_goal(
+        ecx: &mut EvalCtxt<'_, 'tcx>,
+        goal: Goal<'tcx, ty::NormalizesTo<'tcx>>,
+    ) {
+        if ecx.inspect.is_noop() {
+            return;
+        }
+
+        Self::add_goal(ecx, GoalSource::Misc, goal.with(ecx.tcx(), goal.predicate));
+    }
+
     pub fn add_goal(
         ecx: &mut EvalCtxt<'_, 'tcx>,
         source: GoalSource,
diff --git a/compiler/rustc_trait_selection/src/solve/mod.rs b/compiler/rustc_trait_selection/src/solve/mod.rs
index 0bf28f520a4..8294a8a67b1 100644
--- a/compiler/rustc_trait_selection/src/solve/mod.rs
+++ b/compiler/rustc_trait_selection/src/solve/mod.rs
@@ -18,8 +18,7 @@ use rustc_infer::infer::canonical::{Canonical, CanonicalVarValues};
 use rustc_infer::traits::query::NoSolution;
 use rustc_middle::infer::canonical::CanonicalVarInfos;
 use rustc_middle::traits::solve::{
-    CanonicalResponse, Certainty, ExternalConstraintsData, Goal, GoalSource, IsNormalizesToHack,
-    QueryResult, Response,
+    CanonicalResponse, Certainty, ExternalConstraintsData, Goal, GoalSource, QueryResult, Response,
 };
 use rustc_middle::ty::{self, AliasRelationDirection, Ty, TyCtxt, UniverseIndex};
 use rustc_middle::ty::{
@@ -69,7 +68,7 @@ enum SolverMode {
 #[derive(Debug, Copy, Clone, PartialEq, Eq)]
 enum GoalEvaluationKind {
     Root,
-    Nested { is_normalizes_to_hack: IsNormalizesToHack },
+    Nested,
 }
 
 #[extension(trait CanonicalResponseExt)]
@@ -202,12 +201,9 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> {
 
 impl<'tcx> EvalCtxt<'_, 'tcx> {
     #[instrument(level = "debug", skip(self))]
-    fn set_normalizes_to_hack_goal(&mut self, goal: Goal<'tcx, ty::NormalizesTo<'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);
+    fn add_normalizes_to_goal(&mut self, goal: Goal<'tcx, ty::NormalizesTo<'tcx>>) {
+        inspect::ProofTreeBuilder::add_normalizes_to_goal(self, goal);
+        self.nested_goals.normalizes_to_goals.push(goal);
     }
 
     #[instrument(level = "debug", skip(self))]
diff --git a/compiler/rustc_trait_selection/src/solve/normalizes_to/anon_const.rs b/compiler/rustc_trait_selection/src/solve/normalizes_to/anon_const.rs
index 911462f4b9a..37d56452893 100644
--- a/compiler/rustc_trait_selection/src/solve/normalizes_to/anon_const.rs
+++ b/compiler/rustc_trait_selection/src/solve/normalizes_to/anon_const.rs
@@ -16,7 +16,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
                 .no_bound_vars()
                 .expect("const ty should not rely on other generics"),
         ) {
-            self.eq(goal.param_env, normalized_const, goal.predicate.term.ct().unwrap())?;
+            self.instantiate_normalizes_to_term(goal, normalized_const.into());
             self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
         } else {
             self.evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS)
diff --git a/compiler/rustc_trait_selection/src/solve/normalizes_to/inherent.rs b/compiler/rustc_trait_selection/src/solve/normalizes_to/inherent.rs
index 52d2fe1e3ec..d60490bce44 100644
--- a/compiler/rustc_trait_selection/src/solve/normalizes_to/inherent.rs
+++ b/compiler/rustc_trait_selection/src/solve/normalizes_to/inherent.rs
@@ -16,7 +16,6 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
     ) -> QueryResult<'tcx> {
         let tcx = self.tcx();
         let inherent = goal.predicate.alias;
-        let expected = goal.predicate.term.ty().expect("inherent consts are treated separately");
 
         let impl_def_id = tcx.parent(inherent.def_id);
         let impl_args = self.fresh_args_for_item(impl_def_id);
@@ -30,12 +29,6 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
 
         // Equate IAT with the RHS of the project goal
         let inherent_args = inherent.rebase_inherent_args_onto_impl(impl_args, tcx);
-        self.eq(
-            goal.param_env,
-            expected,
-            tcx.type_of(inherent.def_id).instantiate(tcx, inherent_args),
-        )
-        .expect("expected goal term to be fully unconstrained");
 
         // Check both where clauses on the impl and IAT
         //
@@ -51,6 +44,8 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
                 .map(|(pred, _)| goal.with(tcx, pred)),
         );
 
+        let normalized = tcx.type_of(inherent.def_id).instantiate(tcx, inherent_args);
+        self.instantiate_normalizes_to_term(goal, normalized.into());
         self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
     }
 }
diff --git a/compiler/rustc_trait_selection/src/solve/normalizes_to/mod.rs b/compiler/rustc_trait_selection/src/solve/normalizes_to/mod.rs
index a45c1c34410..d24bec5a766 100644
--- a/compiler/rustc_trait_selection/src/solve/normalizes_to/mod.rs
+++ b/compiler/rustc_trait_selection/src/solve/normalizes_to/mod.rs
@@ -31,32 +31,19 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
         goal: Goal<'tcx, NormalizesTo<'tcx>>,
     ) -> QueryResult<'tcx> {
         let def_id = goal.predicate.def_id();
+        let def_kind = self.tcx().def_kind(def_id);
+        match def_kind {
+            DefKind::OpaqueTy => return self.normalize_opaque_type(goal),
+            _ => self.set_is_normalizes_to_goal(),
+        }
+
+        debug_assert!(self.term_is_fully_unconstrained(goal));
         match self.tcx().def_kind(def_id) {
             DefKind::AssocTy | DefKind::AssocConst => {
                 match self.tcx().associated_item(def_id).container {
                     ty::AssocItemContainer::TraitContainer => {
-                        // To only compute normalization once for each projection we only
-                        // assemble normalization candidates if the expected term is an
-                        // unconstrained inference variable.
-                        //
-                        // Why: For better cache hits, since if we have an unconstrained RHS then
-                        // there are only as many cache keys as there are (canonicalized) alias
-                        // types in each normalizes-to goal. This also weakens inference in a
-                        // forwards-compatible way so we don't use the value of the RHS term to
-                        // affect candidate assembly for projections.
-                        //
-                        // 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, since we're piggybacking off of regular
-                        // goal caching.
-                        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)
-                        }
+                        let candidates = self.assemble_and_evaluate_candidates(goal);
+                        self.merge_candidates(candidates)
                     }
                     ty::AssocItemContainer::ImplContainer => {
                         self.normalize_inherent_associated_type(goal)
@@ -64,9 +51,8 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
                 }
             }
             DefKind::AnonConst => self.normalize_anon_const(goal),
-            DefKind::OpaqueTy => self.normalize_opaque_type(goal),
             DefKind::TyAlias => self.normalize_weak_type(goal),
-            kind => bug!("unknown DefKind {} in projection goal: {goal:#?}", kind.descr(def_id)),
+            kind => bug!("unknown DefKind {} in normalizes-to goal: {goal:#?}", kind.descr(def_id)),
         }
     }
 
diff --git a/compiler/rustc_trait_selection/src/solve/normalizes_to/weak_types.rs b/compiler/rustc_trait_selection/src/solve/normalizes_to/weak_types.rs
index 9f91c02c1ab..13af5068b6c 100644
--- a/compiler/rustc_trait_selection/src/solve/normalizes_to/weak_types.rs
+++ b/compiler/rustc_trait_selection/src/solve/normalizes_to/weak_types.rs
@@ -15,10 +15,6 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
     ) -> QueryResult<'tcx> {
         let tcx = self.tcx();
         let weak_ty = goal.predicate.alias;
-        let expected = goal.predicate.term.ty().expect("no such thing as a const alias");
-
-        let actual = tcx.type_of(weak_ty.def_id).instantiate(tcx, weak_ty.args);
-        self.eq(goal.param_env, expected, actual)?;
 
         // Check where clauses
         self.add_goals(
@@ -30,6 +26,9 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
                 .map(|pred| goal.with(tcx, pred)),
         );
 
+        let actual = tcx.type_of(weak_ty.def_id).instantiate(tcx, weak_ty.args);
+        self.instantiate_normalizes_to_term(goal, actual.into());
+
         self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
     }
 }
diff --git a/compiler/rustc_trait_selection/src/solve/search_graph.rs b/compiler/rustc_trait_selection/src/solve/search_graph.rs
index 07a8aca85a0..a48b2f2478b 100644
--- a/compiler/rustc_trait_selection/src/solve/search_graph.rs
+++ b/compiler/rustc_trait_selection/src/solve/search_graph.rs
@@ -10,7 +10,6 @@ use rustc_index::IndexVec;
 use rustc_middle::dep_graph::dep_kinds;
 use rustc_middle::traits::solve::CacheData;
 use rustc_middle::traits::solve::{CanonicalInput, Certainty, EvaluationCache, QueryResult};
-use rustc_middle::ty;
 use rustc_middle::ty::TyCtxt;
 use rustc_session::Limit;
 use std::mem;
@@ -175,15 +174,6 @@ impl<'tcx> SearchGraph<'tcx> {
         }
     }
 
-    pub(super) fn current_goal_is_normalizes_to(&self) -> bool {
-        self.stack.raw.last().map_or(false, |e| {
-            matches!(
-                e.input.value.goal.predicate.kind().skip_binder(),
-                ty::PredicateKind::NormalizesTo(..)
-            )
-        })
-    }
-
     /// Returns the remaining depth allowed for nested goals.
     ///
     /// This is generally simply one less than the current depth.