pass `sub_relations` into canonical queries

4 files changed, 71 insertions, 42 deletions

diff --git a/compiler/rustc_next_trait_solver/src/canonicalizer.rs b/compiler/rustc_next_trait_solver/src/canonicalizer.rs
index 7a8ee09650e..d42c62439f6 100644
--- a/compiler/rustc_next_trait_solver/src/canonicalizer.rs
+++ b/compiler/rustc_next_trait_solver/src/canonicalizer.rs
@@ -67,6 +67,7 @@ pub struct Canonicalizer<'a, D: SolverDelegate<Interner = I>, I: Interner> {
     variables: &'a mut Vec<I::GenericArg>,
     var_kinds: Vec<CanonicalVarKind<I>>,
     variable_lookup_table: HashMap<I::GenericArg, usize>,
+    sub_root_lookup_table: HashMap<ty::TyVid, usize>,
     binder_index: ty::DebruijnIndex,
 
     /// We only use the debruijn index during lookup. We don't need to
@@ -88,6 +89,7 @@ impl<'a, D: SolverDelegate<Interner = I>, I: Interner> Canonicalizer<'a, D, I> {
 
             variables,
             variable_lookup_table: Default::default(),
+            sub_root_lookup_table: Default::default(),
             var_kinds: Vec::new(),
             binder_index: ty::INNERMOST,
 
@@ -132,6 +134,7 @@ impl<'a, D: SolverDelegate<Interner = I>, I: Interner> Canonicalizer<'a, D, I> {
 
                         variables: &mut variables,
                         variable_lookup_table: Default::default(),
+                        sub_root_lookup_table: Default::default(),
                         var_kinds: Vec::new(),
                         binder_index: ty::INNERMOST,
 
@@ -139,6 +142,7 @@ impl<'a, D: SolverDelegate<Interner = I>, I: Interner> Canonicalizer<'a, D, I> {
                     };
                     let param_env = param_env.fold_with(&mut env_canonicalizer);
                     debug_assert_eq!(env_canonicalizer.binder_index, ty::INNERMOST);
+                    debug_assert!(env_canonicalizer.sub_root_lookup_table.is_empty());
                     CanonicalParamEnvCacheEntry {
                         param_env,
                         variable_lookup_table: env_canonicalizer.variable_lookup_table,
@@ -164,6 +168,7 @@ impl<'a, D: SolverDelegate<Interner = I>, I: Interner> Canonicalizer<'a, D, I> {
 
                 variables,
                 variable_lookup_table: Default::default(),
+                sub_root_lookup_table: Default::default(),
                 var_kinds: Vec::new(),
                 binder_index: ty::INNERMOST,
 
@@ -171,6 +176,7 @@ impl<'a, D: SolverDelegate<Interner = I>, I: Interner> Canonicalizer<'a, D, I> {
             };
             let param_env = param_env.fold_with(&mut env_canonicalizer);
             debug_assert_eq!(env_canonicalizer.binder_index, ty::INNERMOST);
+            debug_assert!(env_canonicalizer.sub_root_lookup_table.is_empty());
             (param_env, env_canonicalizer.variable_lookup_table, env_canonicalizer.var_kinds)
         }
     }
@@ -199,6 +205,7 @@ impl<'a, D: SolverDelegate<Interner = I>, I: Interner> Canonicalizer<'a, D, I> {
 
             variables,
             variable_lookup_table,
+            sub_root_lookup_table: Default::default(),
             var_kinds,
             binder_index: ty::INNERMOST,
 
@@ -265,6 +272,13 @@ impl<'a, D: SolverDelegate<Interner = I>, I: Interner> Canonicalizer<'a, D, I> {
         ty::BoundVar::from(idx)
     }
 
+    fn get_or_insert_sub_root(&mut self, vid: ty::TyVid) -> ty::BoundVar {
+        let root_vid = self.delegate.sub_root_ty_var(vid);
+        let idx =
+            *self.sub_root_lookup_table.entry(root_vid).or_insert_with(|| self.variables.len());
+        ty::BoundVar::from(idx)
+    }
+
     fn finalize(self) -> (ty::UniverseIndex, I::CanonicalVarKinds) {
         let mut var_kinds = self.var_kinds;
         // See the rustc-dev-guide section about how we deal with universes
@@ -312,16 +326,15 @@ impl<'a, D: SolverDelegate<Interner = I>, I: Interner> Canonicalizer<'a, D, I> {
                         "ty vid should have been resolved fully before canonicalization"
                     );
 
-                    match self.canonicalize_mode {
-                        CanonicalizeMode::Input { .. } => {
-                            CanonicalVarKind::Ty(ty::UniverseIndex::ROOT)
-                        }
-                        CanonicalizeMode::Response { .. } => {
-                            CanonicalVarKind::Ty(self.delegate.universe_of_ty(vid).unwrap_or_else(
-                                || panic!("ty var should have been resolved: {t:?}"),
-                            ))
-                        }
-                    }
+                    let sub_root = self.get_or_insert_sub_root(vid);
+                    let ui = match self.canonicalize_mode {
+                        CanonicalizeMode::Input { .. } => ty::UniverseIndex::ROOT,
+                        CanonicalizeMode::Response { .. } => self
+                            .delegate
+                            .universe_of_ty(vid)
+                            .unwrap_or_else(|| panic!("ty var should have been resolved: {t:?}")),
+                    };
+                    CanonicalVarKind::Ty { ui, sub_root }
                 }
                 ty::IntVar(vid) => {
                     debug_assert_eq!(
diff --git a/compiler/rustc_next_trait_solver/src/delegate.rs b/compiler/rustc_next_trait_solver/src/delegate.rs
index 7b932010d49..4460e9ad2f1 100644
--- a/compiler/rustc_next_trait_solver/src/delegate.rs
+++ b/compiler/rustc_next_trait_solver/src/delegate.rs
@@ -57,12 +57,14 @@ pub trait SolverDelegate: Deref<Target = Self::Infcx> + Sized {
     where
         V: TypeFoldable<Self::Interner>;
 
-    fn instantiate_canonical_var_with_infer(
+    fn instantiate_canonical_var(
         &self,
         kind: ty::CanonicalVarKind<Self::Interner>,
         span: <Self::Interner as Interner>::Span,
+        var_values: &[<Self::Interner as Interner>::GenericArg],
         universe_map: impl Fn(ty::UniverseIndex) -> ty::UniverseIndex,
     ) -> <Self::Interner as Interner>::GenericArg;
+
     fn add_item_bounds_for_hidden_type(
         &self,
         def_id: <Self::Interner as Interner>::DefId,
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 6f9f4067384..8d7a55c55be 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
@@ -16,7 +16,8 @@ use rustc_type_ir::data_structures::HashSet;
 use rustc_type_ir::inherent::*;
 use rustc_type_ir::relate::solver_relating::RelateExt;
 use rustc_type_ir::{
-    self as ty, Canonical, CanonicalVarValues, InferCtxtLike, Interner, TypeFoldable,
+    self as ty, Canonical, CanonicalVarKind, CanonicalVarValues, InferCtxtLike, Interner,
+    TypeFoldable,
 };
 use tracing::{debug, instrument, trace};
 
@@ -336,7 +337,16 @@ where
         {
             match result_value.kind() {
                 ty::GenericArgKind::Type(t) => {
-                    if let ty::Bound(debruijn, b) = t.kind() {
+                    // We disable the instantiation guess for inference variables
+                    // and only use it for placeholders. We need to handle the
+                    // `sub_root` of type inference variables which would make this
+                    // more involved. They are also a lot rarer than region variables.
+                    if let ty::Bound(debruijn, b) = t.kind()
+                        && !matches!(
+                            response.variables.get(b.var().as_usize()).unwrap(),
+                            CanonicalVarKind::Ty { .. }
+                        )
+                    {
                         assert_eq!(debruijn, ty::INNERMOST);
                         opt_values[b.var()] = Some(*original_value);
                     }
@@ -356,38 +366,37 @@ where
             }
         }
 
-        let var_values = delegate.cx().mk_args_from_iter(
-            response.variables.iter().enumerate().map(|(index, var_kind)| {
-                if var_kind.universe() != ty::UniverseIndex::ROOT {
-                    // A variable from inside a binder of the query. While ideally these shouldn't
-                    // exist at all (see the FIXME at the start of this method), we have to deal with
-                    // them for now.
-                    delegate.instantiate_canonical_var_with_infer(var_kind, span, |idx| {
-                        prev_universe + idx.index()
-                    })
-                } else if var_kind.is_existential() {
-                    // As an optimization we sometimes avoid creating a new inference variable here.
-                    //
-                    // All new inference variables we create start out in the current universe of the caller.
-                    // This is conceptually wrong as these inference variables would be able to name
-                    // more placeholders then they should be able to. However the inference variables have
-                    // to "come from somewhere", so by equating them with the original values of the caller
-                    // later on, we pull them down into their correct universe again.
-                    if let Some(v) = opt_values[ty::BoundVar::from_usize(index)] {
-                        v
-                    } else {
-                        delegate
-                            .instantiate_canonical_var_with_infer(var_kind, span, |_| prev_universe)
-                    }
+        let mut var_values = Vec::with_capacity(response.variables.len());
+        for (index, kind) in response.variables.iter().enumerate() {
+            let value = if kind.universe() != ty::UniverseIndex::ROOT {
+                // A variable from inside a binder of the query. While ideally these shouldn't
+                // exist at all (see the FIXME at the start of this method), we have to deal with
+                // them for now.
+                delegate.instantiate_canonical_var(kind, span, &var_values, |idx| {
+                    prev_universe + idx.index()
+                })
+            } else if kind.is_existential() {
+                // As an optimization we sometimes avoid creating a new inference variable here.
+                //
+                // All new inference variables we create start out in the current universe of the caller.
+                // This is conceptually wrong as these inference variables would be able to name
+                // more placeholders then they should be able to. However the inference variables have
+                // to "come from somewhere", so by equating them with the original values of the caller
+                // later on, we pull them down into their correct universe again.
+                if let Some(v) = opt_values[ty::BoundVar::from_usize(index)] {
+                    v
                 } else {
-                    // For placeholders which were already part of the input, we simply map this
-                    // universal bound variable back the placeholder of the input.
-                    original_values[var_kind.expect_placeholder_index()]
+                    delegate.instantiate_canonical_var(kind, span, &var_values, |_| prev_universe)
                 }
-            }),
-        );
+            } else {
+                // For placeholders which were already part of the input, we simply map this
+                // universal bound variable back the placeholder of the input.
+                original_values[kind.expect_placeholder_index()]
+            };
+            var_values.push(value)
+        }
 
-        CanonicalVarValues { var_values }
+        CanonicalVarValues { var_values: delegate.cx().mk_args(&var_values) }
     }
 
     /// Unify the `original_values` with the `var_values` returned by the canonical query..
diff --git a/compiler/rustc_next_trait_solver/src/solve/mod.rs b/compiler/rustc_next_trait_solver/src/solve/mod.rs
index a2db21796a2..91b83e6cbbe 100644
--- a/compiler/rustc_next_trait_solver/src/solve/mod.rs
+++ b/compiler/rustc_next_trait_solver/src/solve/mod.rs
@@ -418,6 +418,11 @@ pub struct GoalEvaluation<I: Interner> {
     pub has_changed: HasChanged,
     /// If the [`Certainty`] was `Maybe`, then keep track of whether the goal has changed
     /// before rerunning it.
+    ///
+    /// We knowingly ignore the `sub_root` of our inference variables here. This means we
+    /// may not reevaluate a goal even though a change to the `sub_root` could cause a goal
+    /// to make progress. Tracking them adds additional complexity for an incredibly minor
+    /// type inference improvement. We could look into properly handling this in the future.
     pub stalled_on: Option<GoalStalledOn<I>>,
 }