pass `sub_relations` into canonical queries

4 files changed, 73 insertions, 46 deletions

diff --git a/compiler/rustc_infer/src/infer/canonical/canonicalizer.rs b/compiler/rustc_infer/src/infer/canonical/canonicalizer.rs
index 40d3e8acaa4..be68609502a 100644
--- a/compiler/rustc_infer/src/infer/canonical/canonicalizer.rs
+++ b/compiler/rustc_infer/src/infer/canonical/canonicalizer.rs
@@ -6,6 +6,7 @@
 //! [c]: https://rust-lang.github.io/chalk/book/canonical_queries/canonicalization.html
 
 use rustc_data_structures::fx::FxHashMap;
+use rustc_data_structures::sso::SsoHashMap;
 use rustc_index::Idx;
 use rustc_middle::bug;
 use rustc_middle::ty::{
@@ -293,6 +294,7 @@ struct Canonicalizer<'cx, 'tcx> {
     // Note that indices is only used once `var_values` is big enough to be
     // heap-allocated.
     indices: FxHashMap<GenericArg<'tcx>, BoundVar>,
+    sub_root_lookup_table: SsoHashMap<ty::TyVid, usize>,
     canonicalize_mode: &'cx dyn CanonicalizeMode,
     needs_canonical_flags: TypeFlags,
 
@@ -361,7 +363,8 @@ impl<'cx, 'tcx> TypeFolder<TyCtxt<'tcx>> for Canonicalizer<'cx, 'tcx> {
                             // FIXME: perf problem described in #55921.
                             ui = ty::UniverseIndex::ROOT;
                         }
-                        self.canonicalize_ty_var(CanonicalVarKind::Ty(ui), t)
+                        let sub_root = self.get_or_insert_sub_root(vid);
+                        self.canonicalize_ty_var(CanonicalVarKind::Ty { ui, sub_root }, t)
                     }
                 }
             }
@@ -559,6 +562,7 @@ impl<'cx, 'tcx> Canonicalizer<'cx, 'tcx> {
             variables: SmallVec::from_slice(base.variables),
             query_state,
             indices: FxHashMap::default(),
+            sub_root_lookup_table: Default::default(),
             binder_index: ty::INNERMOST,
         };
         if canonicalizer.query_state.var_values.spilled() {
@@ -657,6 +661,13 @@ impl<'cx, 'tcx> Canonicalizer<'cx, 'tcx> {
         }
     }
 
+    fn get_or_insert_sub_root(&mut self, vid: ty::TyVid) -> ty::BoundVar {
+        let root_vid = self.infcx.unwrap().sub_root_var(vid);
+        let idx =
+            *self.sub_root_lookup_table.entry(root_vid).or_insert_with(|| self.variables.len());
+        ty::BoundVar::from(idx)
+    }
+
     /// Replaces the universe indexes used in `var_values` with their index in
     /// `query_state.universe_map`. This minimizes the maximum universe used in
     /// the canonicalized value.
@@ -679,7 +690,9 @@ impl<'cx, 'tcx> Canonicalizer<'cx, 'tcx> {
                 CanonicalVarKind::Int | CanonicalVarKind::Float => {
                     return kind;
                 }
-                CanonicalVarKind::Ty(u) => CanonicalVarKind::Ty(reverse_universe_map[&u]),
+                CanonicalVarKind::Ty { ui, sub_root } => {
+                    CanonicalVarKind::Ty { ui: reverse_universe_map[&ui], sub_root }
+                }
                 CanonicalVarKind::Region(u) => CanonicalVarKind::Region(reverse_universe_map[&u]),
                 CanonicalVarKind::Const(u) => CanonicalVarKind::Const(reverse_universe_map[&u]),
                 CanonicalVarKind::PlaceholderTy(placeholder) => {
diff --git a/compiler/rustc_infer/src/infer/canonical/mod.rs b/compiler/rustc_infer/src/infer/canonical/mod.rs
index 223fb8419ec..4e1ea52af4c 100644
--- a/compiler/rustc_infer/src/infer/canonical/mod.rs
+++ b/compiler/rustc_infer/src/infer/canonical/mod.rs
@@ -84,13 +84,12 @@ impl<'tcx> InferCtxt<'tcx> {
         variables: &List<CanonicalVarKind<'tcx>>,
         universe_map: impl Fn(ty::UniverseIndex) -> ty::UniverseIndex,
     ) -> CanonicalVarValues<'tcx> {
-        CanonicalVarValues {
-            var_values: self.tcx.mk_args_from_iter(
-                variables
-                    .iter()
-                    .map(|kind| self.instantiate_canonical_var(span, kind, &universe_map)),
-            ),
+        let mut var_values = Vec::with_capacity(variables.len());
+        for info in variables.iter() {
+            let value = self.instantiate_canonical_var(span, info, &var_values, &universe_map);
+            var_values.push(value);
         }
+        CanonicalVarValues { var_values: self.tcx.mk_args(&var_values) }
     }
 
     /// Given the "info" about a canonical variable, creates a fresh
@@ -105,10 +104,22 @@ impl<'tcx> InferCtxt<'tcx> {
         &self,
         span: Span,
         kind: CanonicalVarKind<'tcx>,
+        previous_var_values: &[GenericArg<'tcx>],
         universe_map: impl Fn(ty::UniverseIndex) -> ty::UniverseIndex,
     ) -> GenericArg<'tcx> {
         match kind {
-            CanonicalVarKind::Ty(ui) => self.next_ty_var_in_universe(span, universe_map(ui)).into(),
+            CanonicalVarKind::Ty { ui, sub_root } => {
+                let vid = self.next_ty_vid_in_universe(span, universe_map(ui));
+                // Fetch the `sub_root` in case it exists.
+                if let Some(prev) = previous_var_values.get(sub_root.as_usize()) {
+                    if let &ty::Infer(ty::TyVar(sub_root)) = prev.expect_ty().kind() {
+                        self.inner.borrow_mut().type_variables().sub(vid, sub_root);
+                    } else {
+                        unreachable!()
+                    }
+                }
+                Ty::new_var(self.tcx, vid).into()
+            }
 
             CanonicalVarKind::Int => self.next_int_var().into(),
 
diff --git a/compiler/rustc_infer/src/infer/canonical/query_response.rs b/compiler/rustc_infer/src/infer/canonical/query_response.rs
index 09578598114..22c9c4edccc 100644
--- a/compiler/rustc_infer/src/infer/canonical/query_response.rs
+++ b/compiler/rustc_infer/src/infer/canonical/query_response.rs
@@ -13,6 +13,7 @@ use std::iter;
 use rustc_index::{Idx, IndexVec};
 use rustc_middle::arena::ArenaAllocatable;
 use rustc_middle::bug;
+use rustc_middle::infer::canonical::CanonicalVarKind;
 use rustc_middle::ty::{self, BoundVar, GenericArg, GenericArgKind, Ty, TyCtxt, TypeFoldable};
 use tracing::{debug, instrument};
 
@@ -413,26 +414,27 @@ impl<'tcx> InferCtxt<'tcx> {
         let mut opt_values: IndexVec<BoundVar, Option<GenericArg<'tcx>>> =
             IndexVec::from_elem_n(None, query_response.variables.len());
 
-        // In terms of our example above, we are iterating over pairs like:
-        // [(?A, Vec<?0>), ('static, '?1), (?B, ?0)]
         for (original_value, result_value) in iter::zip(&original_values.var_values, result_values)
         {
             match result_value.kind() {
                 GenericArgKind::Type(result_value) => {
-                    // e.g., here `result_value` might be `?0` in the example above...
-                    if let ty::Bound(debruijn, b) = *result_value.kind() {
-                        // ...in which case we would set `canonical_vars[0]` to `Some(?U)`.
-
+                    // 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) = *result_value.kind()
+                        && !matches!(
+                            query_response.variables[b.var.as_usize()],
+                            CanonicalVarKind::Ty { .. }
+                        )
+                    {
                         // We only allow a `ty::INNERMOST` index in generic parameters.
                         assert_eq!(debruijn, ty::INNERMOST);
                         opt_values[b.var] = Some(*original_value);
                     }
                 }
                 GenericArgKind::Lifetime(result_value) => {
-                    // e.g., here `result_value` might be `'?1` in the example above...
                     if let ty::ReBound(debruijn, b) = result_value.kind() {
-                        // ... in which case we would set `canonical_vars[0]` to `Some('static)`.
-
                         // We only allow a `ty::INNERMOST` index in generic parameters.
                         assert_eq!(debruijn, ty::INNERMOST);
                         opt_values[b.var] = Some(*original_value);
@@ -440,8 +442,6 @@ impl<'tcx> InferCtxt<'tcx> {
                 }
                 GenericArgKind::Const(result_value) => {
                     if let ty::ConstKind::Bound(debruijn, b) = result_value.kind() {
-                        // ...in which case we would set `canonical_vars[0]` to `Some(const X)`.
-
                         // We only allow a `ty::INNERMOST` index in generic parameters.
                         assert_eq!(debruijn, ty::INNERMOST);
                         opt_values[b.var] = Some(*original_value);
@@ -453,32 +453,31 @@ impl<'tcx> InferCtxt<'tcx> {
         // Create result arguments: if we found a value for a
         // given variable in the loop above, use that. Otherwise, use
         // a fresh inference variable.
-        let result_args = CanonicalVarValues {
-            var_values: self.tcx.mk_args_from_iter(
-                query_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, we have to deal with them for now.
-                        self.instantiate_canonical_var(cause.span, var_kind, |u| {
-                            universe_map[u.as_usize()]
-                        })
-                    } else if var_kind.is_existential() {
-                        match opt_values[BoundVar::new(index)] {
-                            Some(k) => k,
-                            None => self.instantiate_canonical_var(cause.span, var_kind, |u| {
-                                universe_map[u.as_usize()]
-                            }),
-                        }
-                    } else {
-                        // For placeholders which were already part of the input, we simply map this
-                        // universal bound variable back the placeholder of the input.
-                        opt_values[BoundVar::new(index)].expect(
-                            "expected placeholder to be unified with itself during response",
-                        )
-                    }
-                }),
-            ),
-        };
+        let mut var_values = Vec::with_capacity(query_response.variables.len());
+        for (index, kind) in query_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, we have to deal with them for now.
+                self.instantiate_canonical_var(cause.span, kind, &var_values, |u| {
+                    universe_map[u.as_usize()]
+                })
+            } else if kind.is_existential() {
+                match opt_values[BoundVar::new(index)] {
+                    Some(k) => k,
+                    None => self.instantiate_canonical_var(cause.span, kind, &var_values, |u| {
+                        universe_map[u.as_usize()]
+                    }),
+                }
+            } else {
+                // For placeholders which were already part of the input, we simply map this
+                // universal bound variable back the placeholder of the input.
+                opt_values[BoundVar::new(index)]
+                    .expect("expected placeholder to be unified with itself during response")
+            };
+            var_values.push(value);
+        }
+
+        let result_args = CanonicalVarValues { var_values: self.tcx.mk_args(&var_values) };
 
         let mut obligations = PredicateObligations::new();
 
diff --git a/compiler/rustc_infer/src/infer/context.rs b/compiler/rustc_infer/src/infer/context.rs
index efd623fac78..b76931caaa5 100644
--- a/compiler/rustc_infer/src/infer/context.rs
+++ b/compiler/rustc_infer/src/infer/context.rs
@@ -59,6 +59,10 @@ impl<'tcx> rustc_type_ir::InferCtxtLike for InferCtxt<'tcx> {
         self.root_var(var)
     }
 
+    fn sub_root_ty_var(&self, var: ty::TyVid) -> ty::TyVid {
+        self.sub_root_var(var)
+    }
+
     fn root_const_var(&self, var: ty::ConstVid) -> ty::ConstVid {
         self.root_const_var(var)
     }