Don't rerun goals if none of its vars have changed

10 files changed, 290 insertions, 88 deletions

diff --git a/compiler/rustc_infer/src/infer/context.rs b/compiler/rustc_infer/src/infer/context.rs
index 359b9da11ce..173d47493c5 100644
--- a/compiler/rustc_infer/src/infer/context.rs
+++ b/compiler/rustc_infer/src/infer/context.rs
@@ -89,6 +89,57 @@ impl<'tcx> rustc_type_ir::InferCtxtLike for InferCtxt<'tcx> {
         self.inner.borrow_mut().unwrap_region_constraints().opportunistic_resolve_var(self.tcx, vid)
     }
 
+    fn is_changed_arg(&self, arg: ty::GenericArg<'tcx>) -> bool {
+        match arg.unpack() {
+            ty::GenericArgKind::Lifetime(_) => {
+                // Lifetimes should not change affect trait selection.
+                false
+            }
+            ty::GenericArgKind::Type(ty) => {
+                if let ty::Infer(infer_ty) = *ty.kind() {
+                    match infer_ty {
+                        ty::InferTy::TyVar(vid) => {
+                            !self.probe_ty_var(vid).is_err_and(|_| self.root_var(vid) == vid)
+                        }
+                        ty::InferTy::IntVar(vid) => {
+                            let mut inner = self.inner.borrow_mut();
+                            !matches!(
+                                inner.int_unification_table().probe_value(vid),
+                                ty::IntVarValue::Unknown
+                                    if inner.int_unification_table().find(vid) == vid
+                            )
+                        }
+                        ty::InferTy::FloatVar(vid) => {
+                            let mut inner = self.inner.borrow_mut();
+                            !matches!(
+                                inner.float_unification_table().probe_value(vid),
+                                ty::FloatVarValue::Unknown
+                                    if inner.float_unification_table().find(vid) == vid
+                            )
+                        }
+                        ty::InferTy::FreshTy(_)
+                        | ty::InferTy::FreshIntTy(_)
+                        | ty::InferTy::FreshFloatTy(_) => true,
+                    }
+                } else {
+                    true
+                }
+            }
+            ty::GenericArgKind::Const(ct) => {
+                if let ty::ConstKind::Infer(infer_ct) = ct.kind() {
+                    match infer_ct {
+                        ty::InferConst::Var(vid) => !self
+                            .probe_const_var(vid)
+                            .is_err_and(|_| self.root_const_var(vid) == vid),
+                        ty::InferConst::Fresh(_) => true,
+                    }
+                } else {
+                    true
+                }
+            }
+        }
+    }
+
     fn next_region_infer(&self) -> ty::Region<'tcx> {
         self.next_region_var(RegionVariableOrigin::MiscVariable(DUMMY_SP))
     }
diff --git a/compiler/rustc_infer/src/infer/opaque_types/table.rs b/compiler/rustc_infer/src/infer/opaque_types/table.rs
index 46752840e1b..ab65da3913d 100644
--- a/compiler/rustc_infer/src/infer/opaque_types/table.rs
+++ b/compiler/rustc_infer/src/infer/opaque_types/table.rs
@@ -24,6 +24,12 @@ pub struct OpaqueTypeStorageEntries {
     duplicate_entries: usize,
 }
 
+impl rustc_type_ir::inherent::OpaqueTypeStorageEntries for OpaqueTypeStorageEntries {
+    fn needs_reevaluation(self, canonicalized: usize) -> bool {
+        self.opaque_types != canonicalized
+    }
+}
+
 impl<'tcx> OpaqueTypeStorage<'tcx> {
     #[instrument(level = "debug")]
     pub(crate) fn remove(
diff --git a/compiler/rustc_next_trait_solver/src/solve/eval_ctxt/canonical.rs b/compiler/rustc_next_trait_solver/src/solve/eval_ctxt/canonical.rs
index 455a178595b..66d4cd23112 100644
--- a/compiler/rustc_next_trait_solver/src/solve/eval_ctxt/canonical.rs
+++ b/compiler/rustc_next_trait_solver/src/solve/eval_ctxt/canonical.rs
@@ -53,10 +53,10 @@ where
 {
     /// Canonicalizes the goal remembering the original values
     /// for each bound variable.
-    pub(super) fn canonicalize_goal<T: TypeFoldable<I>>(
+    pub(super) fn canonicalize_goal(
         &self,
-        goal: Goal<I, T>,
-    ) -> (Vec<I::GenericArg>, CanonicalInput<I, T>) {
+        goal: Goal<I, I::Predicate>,
+    ) -> (Vec<I::GenericArg>, CanonicalInput<I, I::Predicate>) {
         // We only care about one entry per `OpaqueTypeKey` here,
         // so we only canonicalize the lookup table and ignore
         // duplicate entries.
@@ -130,7 +130,12 @@ where
                     if goals.is_empty() {
                         assert!(matches!(goals_certainty, Certainty::Yes));
                     }
-                    (Certainty::Yes, NestedNormalizationGoals(goals))
+                    (
+                        Certainty::Yes,
+                        NestedNormalizationGoals(
+                            goals.into_iter().map(|(s, g, _)| (s, g)).collect(),
+                        ),
+                    )
                 }
                 _ => {
                     let certainty = shallow_certainty.and(goals_certainty);
@@ -272,7 +277,7 @@ where
     pub(super) fn instantiate_and_apply_query_response(
         &mut self,
         param_env: I::ParamEnv,
-        original_values: Vec<I::GenericArg>,
+        original_values: &[I::GenericArg],
         response: CanonicalResponse<I>,
     ) -> (NestedNormalizationGoals<I>, Certainty) {
         let instantiation = Self::compute_query_response_instantiation_values(
diff --git a/compiler/rustc_next_trait_solver/src/solve/eval_ctxt/mod.rs b/compiler/rustc_next_trait_solver/src/solve/eval_ctxt/mod.rs
index dfabb94ebfc..d8a97724e81 100644
--- a/compiler/rustc_next_trait_solver/src/solve/eval_ctxt/mod.rs
+++ b/compiler/rustc_next_trait_solver/src/solve/eval_ctxt/mod.rs
@@ -22,8 +22,9 @@ use crate::delegate::SolverDelegate;
 use crate::solve::inspect::{self, ProofTreeBuilder};
 use crate::solve::search_graph::SearchGraph;
 use crate::solve::{
-    CanonicalInput, Certainty, FIXPOINT_STEP_LIMIT, Goal, GoalEvaluationKind, GoalSource,
-    HasChanged, NestedNormalizationGoals, NoSolution, QueryInput, QueryResult,
+    CanonicalInput, Certainty, FIXPOINT_STEP_LIMIT, Goal, GoalEvaluation, GoalEvaluationKind,
+    GoalSource, GoalStalledOn, HasChanged, NestedNormalizationGoals, NoSolution, QueryInput,
+    QueryResult,
 };
 
 pub(super) mod canonical;
@@ -115,7 +116,7 @@ where
 
     pub(super) search_graph: &'a mut SearchGraph<D>,
 
-    nested_goals: Vec<(GoalSource, Goal<I, I::Predicate>)>,
+    nested_goals: Vec<(GoalSource, Goal<I, I::Predicate>, Option<GoalStalledOn<I>>)>,
 
     pub(super) origin_span: I::Span,
 
@@ -147,8 +148,9 @@ pub trait SolverDelegateEvalExt: SolverDelegate {
         goal: Goal<Self::Interner, <Self::Interner as Interner>::Predicate>,
         generate_proof_tree: GenerateProofTree,
         span: <Self::Interner as Interner>::Span,
+        stalled_on: Option<GoalStalledOn<Self::Interner>>,
     ) -> (
-        Result<(HasChanged, Certainty), NoSolution>,
+        Result<GoalEvaluation<Self::Interner>, NoSolution>,
         Option<inspect::GoalEvaluation<Self::Interner>>,
     );
 
@@ -171,8 +173,12 @@ pub trait SolverDelegateEvalExt: SolverDelegate {
         &self,
         goal: Goal<Self::Interner, <Self::Interner as Interner>::Predicate>,
         generate_proof_tree: GenerateProofTree,
+        stalled_on: Option<GoalStalledOn<Self::Interner>>,
     ) -> (
-        Result<(NestedNormalizationGoals<Self::Interner>, HasChanged, Certainty), NoSolution>,
+        Result<
+            (NestedNormalizationGoals<Self::Interner>, GoalEvaluation<Self::Interner>),
+            NoSolution,
+        >,
         Option<inspect::GoalEvaluation<Self::Interner>>,
     );
 }
@@ -188,9 +194,10 @@ where
         goal: Goal<I, I::Predicate>,
         generate_proof_tree: GenerateProofTree,
         span: I::Span,
-    ) -> (Result<(HasChanged, Certainty), NoSolution>, Option<inspect::GoalEvaluation<I>>) {
+        stalled_on: Option<GoalStalledOn<I>>,
+    ) -> (Result<GoalEvaluation<I>, NoSolution>, Option<inspect::GoalEvaluation<I>>) {
         EvalCtxt::enter_root(self, self.cx().recursion_limit(), generate_proof_tree, span, |ecx| {
-            ecx.evaluate_goal(GoalEvaluationKind::Root, GoalSource::Misc, goal)
+            ecx.evaluate_goal(GoalEvaluationKind::Root, GoalSource::Misc, goal, stalled_on)
         })
     }
 
@@ -201,7 +208,7 @@ where
     ) -> bool {
         self.probe(|| {
             EvalCtxt::enter_root(self, root_depth, GenerateProofTree::No, I::Span::dummy(), |ecx| {
-                ecx.evaluate_goal(GoalEvaluationKind::Root, GoalSource::Misc, goal)
+                ecx.evaluate_goal(GoalEvaluationKind::Root, GoalSource::Misc, goal, None)
             })
             .0
         })
@@ -213,8 +220,9 @@ where
         &self,
         goal: Goal<I, I::Predicate>,
         generate_proof_tree: GenerateProofTree,
+        stalled_on: Option<GoalStalledOn<I>>,
     ) -> (
-        Result<(NestedNormalizationGoals<I>, HasChanged, Certainty), NoSolution>,
+        Result<(NestedNormalizationGoals<I>, GoalEvaluation<I>), NoSolution>,
         Option<inspect::GoalEvaluation<I>>,
     ) {
         EvalCtxt::enter_root(
@@ -222,7 +230,9 @@ where
             self.cx().recursion_limit(),
             generate_proof_tree,
             I::Span::dummy(),
-            |ecx| ecx.evaluate_goal_raw(GoalEvaluationKind::Root, GoalSource::Misc, goal),
+            |ecx| {
+                ecx.evaluate_goal_raw(GoalEvaluationKind::Root, GoalSource::Misc, goal, stalled_on)
+            },
         )
     }
 }
@@ -447,11 +457,12 @@ where
         goal_evaluation_kind: GoalEvaluationKind,
         source: GoalSource,
         goal: Goal<I, I::Predicate>,
-    ) -> Result<(HasChanged, Certainty), NoSolution> {
-        let (normalization_nested_goals, has_changed, certainty) =
-            self.evaluate_goal_raw(goal_evaluation_kind, source, goal)?;
+        stalled_on: Option<GoalStalledOn<I>>,
+    ) -> Result<GoalEvaluation<I>, NoSolution> {
+        let (normalization_nested_goals, goal_evaluation) =
+            self.evaluate_goal_raw(goal_evaluation_kind, source, goal, stalled_on)?;
         assert!(normalization_nested_goals.is_empty());
-        Ok((has_changed, certainty))
+        Ok(goal_evaluation)
     }
 
     /// Recursively evaluates `goal`, returning the nested goals in case
@@ -466,7 +477,29 @@ where
         goal_evaluation_kind: GoalEvaluationKind,
         source: GoalSource,
         goal: Goal<I, I::Predicate>,
-    ) -> Result<(NestedNormalizationGoals<I>, HasChanged, Certainty), NoSolution> {
+        stalled_on: Option<GoalStalledOn<I>>,
+    ) -> Result<(NestedNormalizationGoals<I>, GoalEvaluation<I>), NoSolution> {
+        // If we have run this goal before, and it was stalled, check that any of the goal's
+        // args have changed. Otherwise, we don't need to re-run the goal because it'll remain
+        // stalled, since it'll canonicalize the same way and evaluation is pure.
+        if let Some(stalled_on) = stalled_on {
+            if !stalled_on.stalled_vars.iter().any(|value| self.delegate.is_changed_arg(*value))
+                && !self
+                    .delegate
+                    .opaque_types_storage_num_entries()
+                    .needs_reevaluation(stalled_on.num_opaques)
+            {
+                return Ok((
+                    NestedNormalizationGoals::empty(),
+                    GoalEvaluation {
+                        certainty: Certainty::Maybe(stalled_on.stalled_cause),
+                        has_changed: HasChanged::No,
+                        stalled_on: Some(stalled_on),
+                    },
+                ));
+            }
+        }
+
         let (orig_values, canonical_goal) = self.canonicalize_goal(goal);
         let mut goal_evaluation =
             self.inspect.new_goal_evaluation(goal, &orig_values, goal_evaluation_kind);
@@ -489,7 +522,7 @@ where
             if !has_only_region_constraints(response) { HasChanged::Yes } else { HasChanged::No };
 
         let (normalization_nested_goals, certainty) =
-            self.instantiate_and_apply_query_response(goal.param_env, orig_values, response);
+            self.instantiate_and_apply_query_response(goal.param_env, &orig_values, response);
         self.inspect.goal_evaluation(goal_evaluation);
 
         // FIXME: We previously had an assert here that checked that recomputing
@@ -502,7 +535,42 @@ where
         // Once we have decided on how to handle trait-system-refactor-initiative#75,
         // we should re-add an assert here.
 
-        Ok((normalization_nested_goals, has_changed, certainty))
+        let stalled_on = match certainty {
+            Certainty::Yes => None,
+            Certainty::Maybe(stalled_cause) => match has_changed {
+                // FIXME: We could recompute a *new* set of stalled variables by walking
+                // through the orig values, resolving, and computing the root vars of anything
+                // that is not resolved. Only when *these* have changed is it meaningful
+                // to recompute this goal.
+                HasChanged::Yes => None,
+                HasChanged::No => {
+                    // Remove the unconstrained RHS arg, which is expected to have changed.
+                    let mut stalled_vars = orig_values;
+                    if let Some(normalizes_to) = goal.predicate.as_normalizes_to() {
+                        let normalizes_to = normalizes_to.skip_binder();
+                        let rhs_arg: I::GenericArg = normalizes_to.term.into();
+                        let idx = stalled_vars
+                            .iter()
+                            .rposition(|arg| *arg == rhs_arg)
+                            .expect("expected unconstrained arg");
+                        stalled_vars.swap_remove(idx);
+                    }
+
+                    Some(GoalStalledOn {
+                        num_opaques: canonical_goal
+                            .canonical
+                            .value
+                            .predefined_opaques_in_body
+                            .opaque_types
+                            .len(),
+                        stalled_vars,
+                        stalled_cause,
+                    })
+                }
+            },
+        };
+
+        Ok((normalization_nested_goals, GoalEvaluation { certainty, has_changed, stalled_on }))
     }
 
     fn compute_goal(&mut self, goal: Goal<I, I::Predicate>) -> QueryResult<I> {
@@ -602,7 +670,7 @@ where
         let cx = self.cx();
         // If this loop did not result in any progress, what's our final certainty.
         let mut unchanged_certainty = Some(Certainty::Yes);
-        for (source, goal) in mem::take(&mut self.nested_goals) {
+        for (source, goal, stalled_on) in mem::take(&mut self.nested_goals) {
             if let Some(has_changed) = self.delegate.compute_goal_fast_path(goal, self.origin_span)
             {
                 if matches!(has_changed, HasChanged::Yes) {
@@ -630,11 +698,18 @@ where
                 let unconstrained_goal =
                     goal.with(cx, ty::NormalizesTo { alias: pred.alias, term: unconstrained_rhs });
 
-                let (NestedNormalizationGoals(nested_goals), _, certainty) =
-                    self.evaluate_goal_raw(GoalEvaluationKind::Nested, source, unconstrained_goal)?;
+                let (
+                    NestedNormalizationGoals(nested_goals),
+                    GoalEvaluation { certainty, stalled_on, has_changed: _ },
+                ) = self.evaluate_goal_raw(
+                    GoalEvaluationKind::Nested,
+                    source,
+                    unconstrained_goal,
+                    stalled_on,
+                )?;
                 // Add the nested goals from normalization to our own nested goals.
                 trace!(?nested_goals);
-                self.nested_goals.extend(nested_goals);
+                self.nested_goals.extend(nested_goals.into_iter().map(|(s, g)| (s, g, None)));
 
                 // Finally, equate the goal's RHS with the unconstrained var.
                 //
@@ -660,6 +735,8 @@ where
                 // 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!
+                // FIXME: Do we need to eagerly resolve here? Or should we check
+                // if the cache key has any changed vars?
                 let with_resolved_vars = self.resolve_vars_if_possible(goal);
                 if pred.alias != goal.predicate.as_normalizes_to().unwrap().skip_binder().alias {
                     unchanged_certainty = None;
@@ -668,13 +745,13 @@ where
                 match certainty {
                     Certainty::Yes => {}
                     Certainty::Maybe(_) => {
-                        self.nested_goals.push((source, with_resolved_vars));
+                        self.nested_goals.push((source, with_resolved_vars, stalled_on));
                         unchanged_certainty = unchanged_certainty.map(|c| c.and(certainty));
                     }
                 }
             } else {
-                let (has_changed, certainty) =
-                    self.evaluate_goal(GoalEvaluationKind::Nested, source, goal)?;
+                let GoalEvaluation { certainty, has_changed, stalled_on } =
+                    self.evaluate_goal(GoalEvaluationKind::Nested, source, goal, stalled_on)?;
                 if has_changed == HasChanged::Yes {
                     unchanged_certainty = None;
                 }
@@ -682,7 +759,7 @@ where
                 match certainty {
                     Certainty::Yes => {}
                     Certainty::Maybe(_) => {
-                        self.nested_goals.push((source, goal));
+                        self.nested_goals.push((source, goal, stalled_on));
                         unchanged_certainty = unchanged_certainty.map(|c| c.and(certainty));
                     }
                 }
@@ -706,7 +783,7 @@ where
         goal.predicate =
             goal.predicate.fold_with(&mut ReplaceAliasWithInfer::new(self, source, goal.param_env));
         self.inspect.add_goal(self.delegate, self.max_input_universe, source, goal);
-        self.nested_goals.push((source, goal));
+        self.nested_goals.push((source, goal, None));
     }
 
     #[instrument(level = "trace", skip(self, goals))]
diff --git a/compiler/rustc_next_trait_solver/src/solve/mod.rs b/compiler/rustc_next_trait_solver/src/solve/mod.rs
index 2a641807154..a7a984181d7 100644
--- a/compiler/rustc_next_trait_solver/src/solve/mod.rs
+++ b/compiler/rustc_next_trait_solver/src/solve/mod.rs
@@ -21,6 +21,7 @@ mod project_goals;
 mod search_graph;
 mod trait_goals;
 
+use derive_where::derive_where;
 use rustc_type_ir::inherent::*;
 pub use rustc_type_ir::solve::*;
 use rustc_type_ir::{self as ty, Interner, TypingMode};
@@ -369,3 +370,21 @@ fn response_no_constraints_raw<I: Interner>(
         },
     }
 }
+
+/// The result of evaluating a goal.
+pub struct GoalEvaluation<I: Interner> {
+    pub certainty: Certainty,
+    pub has_changed: HasChanged,
+    /// If the [`Certainty`] was `Maybe`, then keep track of whether the goal has changed
+    /// before rerunning it.
+    pub stalled_on: Option<GoalStalledOn<I>>,
+}
+
+/// The conditions that must change for a goal to warrant
+#[derive_where(Clone, Debug; I: Interner)]
+pub struct GoalStalledOn<I: Interner> {
+    pub num_opaques: usize,
+    pub stalled_vars: Vec<I::GenericArg>,
+    /// The cause that will be returned on subsequent evaluations if this goal remains stalled.
+    pub stalled_cause: MaybeCause,
+}
diff --git a/compiler/rustc_trait_selection/src/solve/fulfill.rs b/compiler/rustc_trait_selection/src/solve/fulfill.rs
index aa3be43fcd1..d273703a9b1 100644
--- a/compiler/rustc_trait_selection/src/solve/fulfill.rs
+++ b/compiler/rustc_trait_selection/src/solve/fulfill.rs
@@ -13,8 +13,11 @@ use rustc_middle::ty::{
     self, DelayedSet, Ty, TyCtxt, TypeSuperVisitable, TypeVisitable, TypeVisitor, TypingMode,
 };
 use rustc_next_trait_solver::delegate::SolverDelegate as _;
-use rustc_next_trait_solver::solve::{GenerateProofTree, HasChanged, SolverDelegateEvalExt as _};
+use rustc_next_trait_solver::solve::{
+    GenerateProofTree, GoalEvaluation, GoalStalledOn, HasChanged, SolverDelegateEvalExt as _,
+};
 use rustc_span::Span;
+use thin_vec::ThinVec;
 use tracing::instrument;
 
 use self::derive_errors::*;
@@ -25,6 +28,10 @@ use crate::traits::{FulfillmentError, ScrubbedTraitError};
 
 mod derive_errors;
 
+// FIXME: Do we need to use a `ThinVec` here?
+type PendingObligations<'tcx> =
+    ThinVec<(PredicateObligation<'tcx>, Option<GoalStalledOn<TyCtxt<'tcx>>>)>;
+
 /// A trait engine using the new trait solver.
 ///
 /// This is mostly identical to how `evaluate_all` works inside of the
@@ -54,13 +61,17 @@ struct ObligationStorage<'tcx> {
     /// We cannot eagerly return these as error so we instead store them here
     /// to avoid recomputing them each time `select_where_possible` is called.
     /// This also allows us to return the correct `FulfillmentError` for them.
-    overflowed: PredicateObligations<'tcx>,
-    pending: PredicateObligations<'tcx>,
+    overflowed: Vec<PredicateObligation<'tcx>>,
+    pending: PendingObligations<'tcx>,
 }
 
 impl<'tcx> ObligationStorage<'tcx> {
-    fn register(&mut self, obligation: PredicateObligation<'tcx>) {
-        self.pending.push(obligation);
+    fn register(
+        &mut self,
+        obligation: PredicateObligation<'tcx>,
+        stalled_on: Option<GoalStalledOn<TyCtxt<'tcx>>>,
+    ) {
+        self.pending.push((obligation, stalled_on));
     }
 
     fn has_pending_obligations(&self) -> bool {
@@ -68,7 +79,8 @@ impl<'tcx> ObligationStorage<'tcx> {
     }
 
     fn clone_pending(&self) -> PredicateObligations<'tcx> {
-        let mut obligations = self.pending.clone();
+        let mut obligations: PredicateObligations<'tcx> =
+            self.pending.iter().map(|(o, _)| o.clone()).collect();
         obligations.extend(self.overflowed.iter().cloned());
         obligations
     }
@@ -76,8 +88,9 @@ impl<'tcx> ObligationStorage<'tcx> {
     fn drain_pending(
         &mut self,
         cond: impl Fn(&PredicateObligation<'tcx>) -> bool,
-    ) -> PredicateObligations<'tcx> {
-        let (unstalled, pending) = mem::take(&mut self.pending).into_iter().partition(cond);
+    ) -> PendingObligations<'tcx> {
+        let (unstalled, pending) =
+            mem::take(&mut self.pending).into_iter().partition(|(o, _)| cond(o));
         self.pending = pending;
         unstalled
     }
@@ -90,13 +103,21 @@ impl<'tcx> ObligationStorage<'tcx> {
             // we were to do another step of `select_where_possible`, which goals would
             // change.
             // FIXME: <https://github.com/Gankra/thin-vec/pull/66> is merged, this can be removed.
-            self.overflowed.extend(ExtractIf::new(&mut self.pending, |o| {
-                let goal = o.as_goal();
-                let result = <&SolverDelegate<'tcx>>::from(infcx)
-                    .evaluate_root_goal(goal, GenerateProofTree::No, o.cause.span)
-                    .0;
-                matches!(result, Ok((HasChanged::Yes, _)))
-            }));
+            self.overflowed.extend(
+                ExtractIf::new(&mut self.pending, |(o, stalled_on)| {
+                    let goal = o.as_goal();
+                    let result = <&SolverDelegate<'tcx>>::from(infcx)
+                        .evaluate_root_goal(
+                            goal,
+                            GenerateProofTree::No,
+                            o.cause.span,
+                            stalled_on.take(),
+                        )
+                        .0;
+                    matches!(result, Ok(GoalEvaluation { has_changed: HasChanged::Yes, .. }))
+                })
+                .map(|(o, _)| o),
+            );
         })
     }
 }
@@ -119,11 +140,11 @@ impl<'tcx, E: 'tcx> FulfillmentCtxt<'tcx, E> {
         &self,
         infcx: &InferCtxt<'tcx>,
         obligation: &PredicateObligation<'tcx>,
-        result: &Result<(HasChanged, Certainty), NoSolution>,
+        result: &Result<GoalEvaluation<TyCtxt<'tcx>>, NoSolution>,
     ) {
         if let Some(inspector) = infcx.obligation_inspector.get() {
             let result = match result {
-                Ok((_, c)) => Ok(*c),
+                Ok(GoalEvaluation { certainty, .. }) => Ok(*certainty),
                 Err(NoSolution) => Err(NoSolution),
             };
             (inspector)(infcx, &obligation, result);
@@ -142,14 +163,14 @@ where
         obligation: PredicateObligation<'tcx>,
     ) {
         assert_eq!(self.usable_in_snapshot, infcx.num_open_snapshots());
-        self.obligations.register(obligation);
+        self.obligations.register(obligation, None);
     }
 
     fn collect_remaining_errors(&mut self, infcx: &InferCtxt<'tcx>) -> Vec<E> {
         self.obligations
             .pending
             .drain(..)
-            .map(|obligation| NextSolverError::Ambiguity(obligation))
+            .map(|(obligation, _)| NextSolverError::Ambiguity(obligation))
             .chain(
                 self.obligations
                     .overflowed
@@ -164,8 +185,8 @@ where
         assert_eq!(self.usable_in_snapshot, infcx.num_open_snapshots());
         let mut errors = Vec::new();
         loop {
-            let mut has_changed = false;
-            for mut obligation in self.obligations.drain_pending(|_| true) {
+            let mut any_changed = false;
+            for (mut obligation, stalled_on) in self.obligations.drain_pending(|_| true) {
                 if !infcx.tcx.recursion_limit().value_within_limit(obligation.recursion_depth) {
                     self.obligations.on_fulfillment_overflow(infcx);
                     // Only return true errors that we have accumulated while processing.
@@ -177,15 +198,20 @@ where
                 if let Some(fast_path_has_changed) =
                     delegate.compute_goal_fast_path(goal, obligation.cause.span)
                 {
-                    has_changed |= matches!(fast_path_has_changed, HasChanged::Yes);
+                    any_changed |= matches!(fast_path_has_changed, HasChanged::Yes);
                     continue;
                 }
 
                 let result = delegate
-                    .evaluate_root_goal(goal, GenerateProofTree::No, obligation.cause.span)
+                    .evaluate_root_goal(
+                        goal,
+                        GenerateProofTree::No,
+                        obligation.cause.span,
+                        stalled_on,
+                    )
                     .0;
                 self.inspect_evaluated_obligation(infcx, &obligation, &result);
-                let (changed, certainty) = match result {
+                let GoalEvaluation { certainty, has_changed, stalled_on } = match result {
                     Ok(result) => result,
                     Err(NoSolution) => {
                         errors.push(E::from_solver_error(
@@ -196,7 +222,7 @@ where
                     }
                 };
 
-                if changed == HasChanged::Yes {
+                if has_changed == HasChanged::Yes {
                     // We increment the recursion depth here to track the number of times
                     // this goal has resulted in inference progress. This doesn't precisely
                     // model the way that we track recursion depth in the old solver due
@@ -204,16 +230,16 @@ where
                     // approximation and should only result in fulfillment overflow in
                     // pathological cases.
                     obligation.recursion_depth += 1;
-                    has_changed = true;
+                    any_changed = true;
                 }
 
                 match certainty {
                     Certainty::Yes => {}
-                    Certainty::Maybe(_) => self.obligations.register(obligation),
+                    Certainty::Maybe(_) => self.obligations.register(obligation, stalled_on),
                 }
             }
 
-            if !has_changed {
+            if !any_changed {
                 break;
             }
         }
@@ -247,20 +273,24 @@ where
             return Default::default();
         }
 
-        self.obligations.drain_pending(|obl| {
-            infcx.probe(|_| {
-                infcx
-                    .visit_proof_tree(
-                        obl.as_goal(),
-                        &mut StalledOnCoroutines {
-                            stalled_generators,
-                            span: obl.cause.span,
-                            cache: Default::default(),
-                        },
-                    )
-                    .is_break()
+        self.obligations
+            .drain_pending(|obl| {
+                infcx.probe(|_| {
+                    infcx
+                        .visit_proof_tree(
+                            obl.as_goal(),
+                            &mut StalledOnCoroutines {
+                                stalled_generators,
+                                span: obl.cause.span,
+                                cache: Default::default(),
+                            },
+                        )
+                        .is_break()
+                })
             })
-        })
+            .into_iter()
+            .map(|(o, _)| o)
+            .collect()
     }
 }
 
diff --git a/compiler/rustc_trait_selection/src/solve/fulfill/derive_errors.rs b/compiler/rustc_trait_selection/src/solve/fulfill/derive_errors.rs
index f64cd5ffebe..1c9d69da322 100644
--- a/compiler/rustc_trait_selection/src/solve/fulfill/derive_errors.rs
+++ b/compiler/rustc_trait_selection/src/solve/fulfill/derive_errors.rs
@@ -11,7 +11,9 @@ use rustc_middle::traits::query::NoSolution;
 use rustc_middle::ty::error::{ExpectedFound, TypeError};
 use rustc_middle::ty::{self, Ty, TyCtxt};
 use rustc_middle::{bug, span_bug};
-use rustc_next_trait_solver::solve::{GenerateProofTree, SolverDelegateEvalExt as _};
+use rustc_next_trait_solver::solve::{
+    GenerateProofTree, GoalEvaluation, SolverDelegateEvalExt as _,
+};
 use tracing::{instrument, trace};
 
 use crate::solve::delegate::SolverDelegate;
@@ -93,19 +95,21 @@ pub(super) fn fulfillment_error_for_stalled<'tcx>(
                 root_obligation.as_goal(),
                 GenerateProofTree::No,
                 root_obligation.cause.span,
+                None,
             )
             .0
         {
-            Ok((_, Certainty::Maybe(MaybeCause::Ambiguity))) => {
+            Ok(GoalEvaluation { certainty: Certainty::Maybe(MaybeCause::Ambiguity), .. }) => {
                 (FulfillmentErrorCode::Ambiguity { overflow: None }, true)
             }
-            Ok((
-                _,
-                Certainty::Maybe(MaybeCause::Overflow {
-                    suggest_increasing_limit,
-                    keep_constraints: _,
-                }),
-            )) => (
+            Ok(GoalEvaluation {
+                certainty:
+                    Certainty::Maybe(MaybeCause::Overflow {
+                        suggest_increasing_limit,
+                        keep_constraints: _,
+                    }),
+                ..
+            }) => (
                 FulfillmentErrorCode::Ambiguity { overflow: Some(suggest_increasing_limit) },
                 // Don't look into overflows because we treat overflows weirdly anyways.
                 // We discard the inference constraints from overflowing goals, so
@@ -115,7 +119,7 @@ pub(super) fn fulfillment_error_for_stalled<'tcx>(
                 // FIXME: We should probably just look into overflows here.
                 false,
             ),
-            Ok((_, Certainty::Yes)) => {
+            Ok(GoalEvaluation { certainty: Certainty::Yes, .. }) => {
                 bug!(
                     "did not expect successful goal when collecting ambiguity errors for `{:?}`",
                     infcx.resolve_vars_if_possible(root_obligation.predicate),
diff --git a/compiler/rustc_trait_selection/src/solve/inspect/analyse.rs b/compiler/rustc_trait_selection/src/solve/inspect/analyse.rs
index 9795655e842..49a8b363b0a 100644
--- a/compiler/rustc_trait_selection/src/solve/inspect/analyse.rs
+++ b/compiler/rustc_trait_selection/src/solve/inspect/analyse.rs
@@ -219,8 +219,8 @@ impl<'a, 'tcx> InspectCandidate<'a, 'tcx> {
                 // building their proof tree, the expected term was unconstrained, but when
                 // instantiating the candidate it is already constrained to the result of another
                 // candidate.
-                let proof_tree =
-                    infcx.probe(|_| infcx.evaluate_root_goal_raw(goal, GenerateProofTree::Yes).1);
+                let proof_tree = infcx
+                    .probe(|_| infcx.evaluate_root_goal_raw(goal, GenerateProofTree::Yes, None).1);
                 InspectGoal::new(
                     infcx,
                     self.goal.depth + 1,
@@ -236,7 +236,7 @@ impl<'a, 'tcx> InspectCandidate<'a, 'tcx> {
                 // constraints, we get an ICE if we already applied the constraints
                 // from the chosen candidate.
                 let proof_tree = infcx
-                    .probe(|_| infcx.evaluate_root_goal(goal, GenerateProofTree::Yes, span).1)
+                    .probe(|_| infcx.evaluate_root_goal(goal, GenerateProofTree::Yes, span, None).1)
                     .unwrap();
                 InspectGoal::new(infcx, self.goal.depth + 1, proof_tree, None, source)
             }
@@ -442,6 +442,7 @@ impl<'tcx> InferCtxt<'tcx> {
             goal,
             GenerateProofTree::Yes,
             visitor.span(),
+            None,
         );
         let proof_tree = proof_tree.unwrap();
         visitor.visit_goal(&InspectGoal::new(self, depth, proof_tree, None, GoalSource::Misc))
diff --git a/compiler/rustc_type_ir/src/infer_ctxt.rs b/compiler/rustc_type_ir/src/infer_ctxt.rs
index c1490762117..2bc12d0a23b 100644
--- a/compiler/rustc_type_ir/src/infer_ctxt.rs
+++ b/compiler/rustc_type_ir/src/infer_ctxt.rs
@@ -1,11 +1,10 @@
-use std::fmt::Debug;
-
 use derive_where::derive_where;
 #[cfg(feature = "nightly")]
 use rustc_macros::{Decodable_NoContext, Encodable_NoContext, HashStable_NoContext};
 use rustc_type_ir_macros::{TypeFoldable_Generic, TypeVisitable_Generic};
 
 use crate::fold::TypeFoldable;
+use crate::inherent::*;
 use crate::relate::RelateResult;
 use crate::relate::combine::PredicateEmittingRelation;
 use crate::{self as ty, Interner};
@@ -168,6 +167,8 @@ pub trait InferCtxtLike: Sized {
         vid: ty::RegionVid,
     ) -> <Self::Interner as Interner>::Region;
 
+    fn is_changed_arg(&self, arg: <Self::Interner as Interner>::GenericArg) -> bool;
+
     fn next_region_infer(&self) -> <Self::Interner as Interner>::Region;
     fn next_ty_infer(&self) -> <Self::Interner as Interner>::Ty;
     fn next_const_infer(&self) -> <Self::Interner as Interner>::Const;
@@ -248,7 +249,7 @@ pub trait InferCtxtLike: Sized {
         span: <Self::Interner as Interner>::Span,
     );
 
-    type OpaqueTypeStorageEntries: Debug + Copy + Default;
+    type OpaqueTypeStorageEntries: OpaqueTypeStorageEntries;
     fn opaque_types_storage_num_entries(&self) -> Self::OpaqueTypeStorageEntries;
     fn clone_opaque_types_lookup_table(
         &self,
diff --git a/compiler/rustc_type_ir/src/inherent.rs b/compiler/rustc_type_ir/src/inherent.rs
index ee4a8096462..dde55effc3d 100644
--- a/compiler/rustc_type_ir/src/inherent.rs
+++ b/compiler/rustc_type_ir/src/inherent.rs
@@ -297,6 +297,7 @@ pub trait GenericArg<I: Interner<GenericArg = Self>>:
     + From<I::Ty>
     + From<I::Region>
     + From<I::Const>
+    + From<I::Term>
 {
     fn as_term(&self) -> Option<I::Term> {
         match self.kind() {
@@ -596,6 +597,13 @@ pub trait Span<I: Interner>: Copy + Debug + Hash + Eq + TypeFoldable<I> {
     fn dummy() -> Self;
 }
 
+pub trait OpaqueTypeStorageEntries: Debug + Copy + Default {
+    /// Whether the number of opaques has changed in a way that necessitates
+    /// reevaluating a goal. For now, this is only when the number of non-duplicated
+    /// entries changed.
+    fn needs_reevaluation(self, canonicalized: usize) -> bool;
+}
+
 pub trait SliceLike: Sized + Copy {
     type Item: Copy;
     type IntoIter: Iterator<Item = Self::Item> + DoubleEndedIterator;