Prepopulate opaques in canonical input

7 files changed, 170 insertions, 77 deletions

diff --git a/compiler/rustc_trait_selection/src/solve/assembly/mod.rs b/compiler/rustc_trait_selection/src/solve/assembly/mod.rs
index d14e6244f7d..4e06832e65b 100644
--- a/compiler/rustc_trait_selection/src/solve/assembly/mod.rs
+++ b/compiler/rustc_trait_selection/src/solve/assembly/mod.rs
@@ -333,8 +333,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
         };
 
@@ -356,8 +355,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.
diff --git a/compiler/rustc_trait_selection/src/solve/eval_ctxt.rs b/compiler/rustc_trait_selection/src/solve/eval_ctxt.rs
index 63a73f8d50d..bd83666eb1e 100644
--- a/compiler/rustc_trait_selection/src/solve/eval_ctxt.rs
+++ b/compiler/rustc_trait_selection/src/solve/eval_ctxt.rs
@@ -9,7 +9,10 @@ use rustc_infer::infer::{
 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, Certainty, MaybeCause, PredefinedOpaques, PredefinedOpaquesData, QueryResult,
+};
+use rustc_middle::traits::DefiningAnchor;
 use rustc_middle::ty::{
     self, Ty, TyCtxt, TypeFoldable, TypeSuperVisitable, TypeVisitable, TypeVisitableExt,
     TypeVisitor,
@@ -44,6 +47,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
@@ -126,6 +132,11 @@ 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(),
@@ -162,29 +173,59 @@ 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
+                    .handle_opaque_type(
+                        tcx.mk_opaque(a.def_id.to_def_id(), a.substs),
+                        b,
+                        true,
+                        &ObligationCause::dummy(),
+                        input.goal.param_env,
+                    )
+                    .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
         })
     }
 
@@ -199,7 +240,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,
@@ -418,6 +460,7 @@ 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(),
@@ -682,4 +725,16 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
             | rustc_transmute::Answer::IfAny(_) => Err(NoSolution),
         }
     }
+
+    pub(super) fn handle_opaque_ty(
+        &mut self,
+        a: Ty<'tcx>,
+        b: Ty<'tcx>,
+        param_env: ty::ParamEnv<'tcx>,
+    ) -> Result<(), NoSolution> {
+        let InferOk { value: (), obligations } =
+            self.infcx.handle_opaque_type(a, b, true, &ObligationCause::dummy(), param_env)?;
+        self.add_goals(obligations.into_iter().map(|obligation| obligation.into()));
+        Ok(())
+    }
 }
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 67ad7fb4bd2..8d12c7edfe3 100644
--- a/compiler/rustc_trait_selection/src/solve/eval_ctxt/canonical.rs
+++ b/compiler/rustc_trait_selection/src/solve/eval_ctxt/canonical.rs
@@ -8,7 +8,7 @@
 /// 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;
@@ -16,8 +16,11 @@ 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_middle::traits::query::NoSolution;
-use rustc_middle::traits::solve::{ExternalConstraints, ExternalConstraintsData, MaybeCause};
-use rustc_middle::ty::{self, BoundVar, GenericArgKind};
+use rustc_middle::traits::solve::{
+    ExternalConstraints, ExternalConstraintsData, MaybeCause, PredefinedOpaquesData, QueryInput,
+};
+use rustc_middle::traits::ObligationCause;
+use rustc_middle::ty::{self, BoundVar, GenericArgKind, Ty};
 use rustc_span::DUMMY_SP;
 use std::iter;
 use std::ops::Deref;
@@ -28,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)
     }
@@ -138,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 }))
@@ -162,12 +179,13 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
         let Response { var_values, external_constraints, certainty } =
             response.substitute(self.tcx(), &substitution);
 
-        let nested_goals = self.unify_query_var_values(param_env, &original_values, var_values)?;
+        let mut 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);
+        nested_goals.extend(self.register_opaque_types(param_env, opaque_types)?);
 
         Ok((certainty, nested_goals))
     }
@@ -287,4 +305,29 @@ 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<Vec<Goal<'tcx, ty::Predicate<'tcx>>>, NoSolution> {
+        let mut nested_goals = vec![];
+        for &(a, b) in opaque_types {
+            nested_goals.extend(
+                self.infcx
+                    .handle_opaque_type(
+                        self.tcx().mk_opaque(a.def_id.to_def_id(), a.substs),
+                        b,
+                        true,
+                        &ObligationCause::dummy(),
+                        param_env,
+                    )?
+                    .into_obligations()
+                    .into_iter()
+                    .map(Goal::from),
+            );
+        }
+
+        Ok(nested_goals)
+    }
 }
diff --git a/compiler/rustc_trait_selection/src/solve/opaques.rs b/compiler/rustc_trait_selection/src/solve/opaques.rs
index 1a770459338..7d6e1647cfc 100644
--- a/compiler/rustc_trait_selection/src/solve/opaques.rs
+++ b/compiler/rustc_trait_selection/src/solve/opaques.rs
@@ -1,14 +1,13 @@
-use rustc_infer::infer::InferOk;
 use rustc_middle::traits::solve::{Certainty, Goal, QueryResult};
-use rustc_middle::traits::{ObligationCause, Reveal};
-use rustc_middle::ty::ProjectionPredicate;
+use rustc_middle::traits::Reveal;
+use rustc_middle::ty::{self};
 
 use super::{EvalCtxt, SolverMode};
 
 impl<'tcx> EvalCtxt<'_, 'tcx> {
     pub(super) fn normalize_opaque_type(
         &mut self,
-        goal: Goal<'tcx, ProjectionPredicate<'tcx>>,
+        goal: Goal<'tcx, ty::ProjectionPredicate<'tcx>>,
     ) -> QueryResult<'tcx> {
         let tcx = self.tcx();
         let opaque_ty = goal.predicate.projection_ty;
@@ -19,15 +18,8 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
                 SolverMode::Normal => self.probe(|ecx| {
                     // FIXME: Check that the usage is "defining" (all free params), otherwise bail.
                     // FIXME: This should probably just check the anchor directly
-                    let InferOk { value: (), obligations } = self.infcx.handle_opaque_type(
-                        expected,
-                        tcx.mk_opaque(opaque_ty.def_id, opaque_ty.substs),
-                        true,
-                        &ObligationCause::dummy(),
-                        goal.param_env,
-                    )?;
-                    // FIXME: Need to fold these to replace the opaque ty with the expected ty.
-                    ecx.add_goals(obligations.into_iter().map(Into::into));
+                    let opaque_ty = tcx.mk_opaque(opaque_ty.def_id, opaque_ty.substs);
+                    ecx.handle_opaque_ty(expected, opaque_ty, goal.param_env)?;
                     ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
                 }),
                 SolverMode::Coherence => {
diff --git a/compiler/rustc_trait_selection/src/solve/project_goals.rs b/compiler/rustc_trait_selection/src/solve/project_goals.rs
index 248b750b3bd..7d7dfa2c837 100644
--- a/compiler/rustc_trait_selection/src/solve/project_goals.rs
+++ b/compiler/rustc_trait_selection/src/solve/project_goals.rs
@@ -22,24 +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) {
-            match goal.predicate.projection_ty.kind(self.tcx()) {
-                ty::AliasKind::Projection => {
+        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),
             }
-        } 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"),
         }
     }
 }
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 e6941af7b57..56f126e9157 100644
--- a/compiler/rustc_trait_selection/src/solve/search_graph/cache.rs
+++ b/compiler/rustc_trait_selection/src/solve/search_graph/cache.rs
@@ -11,7 +11,7 @@
 use super::StackDepth;
 use rustc_data_structures::fx::FxHashMap;
 use rustc_index::IndexVec;
-use rustc_middle::traits::solve::{CanonicalGoal, QueryResult};
+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 c1904352574..19e4b23009a 100644
--- a/compiler/rustc_trait_selection/src/solve/search_graph/mod.rs
+++ b/compiler/rustc_trait_selection/src/solve/search_graph/mod.rs
@@ -8,7 +8,7 @@ use cache::ProvisionalCache;
 use overflow::OverflowData;
 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,
                 );