6 files changed, 125 insertions, 81 deletions

diff --git a/crates/hir/src/lib.rs b/crates/hir/src/lib.rs
index a325b6691..b7ab03edf 100644
--- a/crates/hir/src/lib.rs
+++ b/crates/hir/src/lib.rs
@@ -56,9 +56,9 @@ use hir_ty::{
     primitive::UintTy,
     to_assoc_type_id,
     traits::{FnTrait, Solution, SolutionVariables},
-    AliasEq, AliasTy, BoundVar, CallableDefId, CallableSig, Canonical, Cast, DebruijnIndex,
-    InEnvironment, Interner, ProjectionTy, QuantifiedWhereClause, Scalar, Substitution, Ty,
-    TyDefId, TyKind, TyVariableKind, WhereClause,
+    AliasEq, AliasTy, BoundVar, CallableDefId, CallableSig, Canonical, CanonicalVarKinds, Cast,
+    DebruijnIndex, InEnvironment, Interner, ProjectionTy, QuantifiedWhereClause, Scalar,
+    Substitution, Ty, TyDefId, TyKind, TyVariableKind, WhereClause,
 };
 use itertools::Itertools;
 use rustc_hash::FxHashSet;
@@ -1723,7 +1723,10 @@ impl Type {
             None => return false,
         };
 
-        let canonical_ty = Canonical { value: self.ty.value.clone(), kinds: Arc::new([]) };
+        let canonical_ty = Canonical {
+            value: self.ty.value.clone(),
+            binders: CanonicalVarKinds::empty(&Interner),
+        };
         method_resolution::implements_trait(
             &canonical_ty,
             db,
@@ -1745,7 +1748,10 @@ impl Type {
             None => return false,
         };
 
-        let canonical_ty = Canonical { value: self.ty.value.clone(), kinds: Arc::new([]) };
+        let canonical_ty = Canonical {
+            value: self.ty.value.clone(),
+            binders: CanonicalVarKinds::empty(&Interner),
+        };
         method_resolution::implements_trait_unique(
             &canonical_ty,
             db,
@@ -1769,7 +1775,7 @@ impl Type {
                 self.ty.environment.clone(),
                 trait_ref.cast(&Interner),
             ),
-            kinds: Arc::new([]),
+            binders: CanonicalVarKinds::empty(&Interner),
         };
 
         db.trait_solve(self.krate, goal).is_some()
@@ -1786,8 +1792,8 @@ impl Type {
             .push(self.ty.value.clone())
             .fill(args.iter().map(|t| t.ty.value.clone()))
             .build();
-        let goal = Canonical {
-            value: InEnvironment::new(
+        let goal = Canonical::new(
+            InEnvironment::new(
                 self.ty.environment.clone(),
                 AliasEq {
                     alias: AliasTy::Projection(ProjectionTy {
@@ -1799,8 +1805,8 @@ impl Type {
                 }
                 .cast(&Interner),
             ),
-            kinds: Arc::new([TyVariableKind::General]),
-        };
+            [TyVariableKind::General].iter().copied(),
+        );
 
         match db.trait_solve(self.krate, goal)? {
             Solution::Unique(SolutionVariables(subst)) => {
@@ -1911,7 +1917,10 @@ impl Type {
     pub fn autoderef<'a>(&'a self, db: &'a dyn HirDatabase) -> impl Iterator<Item = Type> + 'a {
         // There should be no inference vars in types passed here
         // FIXME check that?
-        let canonical = Canonical { value: self.ty.value.clone(), kinds: Arc::new([]) };
+        let canonical = Canonical {
+            value: self.ty.value.clone(),
+            binders: CanonicalVarKinds::empty(&Interner),
+        };
         let environment = self.ty.environment.clone();
         let ty = InEnvironment { value: canonical, environment };
         autoderef(db, Some(self.krate), ty)
@@ -1962,7 +1971,10 @@ impl Type {
         // There should be no inference vars in types passed here
         // FIXME check that?
         // FIXME replace Unknown by bound vars here
-        let canonical = Canonical { value: self.ty.value.clone(), kinds: Arc::new([]) };
+        let canonical = Canonical {
+            value: self.ty.value.clone(),
+            binders: CanonicalVarKinds::empty(&Interner),
+        };
 
         let env = self.ty.environment.clone();
         let krate = krate.id;
@@ -1993,7 +2005,10 @@ impl Type {
         // There should be no inference vars in types passed here
         // FIXME check that?
         // FIXME replace Unknown by bound vars here
-        let canonical = Canonical { value: self.ty.value.clone(), kinds: Arc::new([]) };
+        let canonical = Canonical {
+            value: self.ty.value.clone(),
+            binders: CanonicalVarKinds::empty(&Interner),
+        };
 
         let env = self.ty.environment.clone();
         let krate = krate.id;
diff --git a/crates/hir_ty/src/autoderef.rs b/crates/hir_ty/src/autoderef.rs
index 23ab042c1..d6f0553b1 100644
--- a/crates/hir_ty/src/autoderef.rs
+++ b/crates/hir_ty/src/autoderef.rs
@@ -16,8 +16,8 @@ use crate::{
     to_assoc_type_id, to_chalk_trait_id,
     traits::{InEnvironment, Solution},
     utils::generics,
-    AliasEq, AliasTy, BoundVar, Canonical, DebruijnIndex, Interner, ProjectionTy, Substitution,
-    TraitRef, Ty, TyKind,
+    AliasEq, AliasTy, BoundVar, Canonical, CanonicalVarKinds, DebruijnIndex, Interner,
+    ProjectionTy, Substitution, TraitRef, Ty, TyKind,
 };
 
 const AUTODEREF_RECURSION_LIMIT: usize = 10;
@@ -40,7 +40,7 @@ pub(crate) fn deref(
     ty: InEnvironment<&Canonical<Ty>>,
 ) -> Option<Canonical<Ty>> {
     if let Some(derefed) = ty.value.value.builtin_deref() {
-        Some(Canonical { value: derefed, kinds: ty.value.kinds.clone() })
+        Some(Canonical { value: derefed, binders: ty.value.binders.clone() })
     } else {
         deref_by_trait(db, krate, ty)
     }
@@ -73,7 +73,7 @@ fn deref_by_trait(
     let trait_ref =
         TraitRef { trait_id: to_chalk_trait_id(deref_trait), substitution: parameters.clone() };
     let implements_goal = Canonical {
-        kinds: ty.value.kinds.clone(),
+        binders: ty.value.binders.clone(),
         value: InEnvironment {
             value: trait_ref.cast(&Interner),
             environment: ty.environment.clone(),
@@ -89,18 +89,27 @@ fn deref_by_trait(
             associated_ty_id: to_assoc_type_id(target),
             substitution: parameters,
         }),
-        ty: TyKind::BoundVar(BoundVar::new(DebruijnIndex::INNERMOST, ty.value.kinds.len()))
-            .intern(&Interner),
+        ty: TyKind::BoundVar(BoundVar::new(
+            DebruijnIndex::INNERMOST,
+            ty.value.binders.len(&Interner),
+        ))
+        .intern(&Interner),
     };
 
     let obligation = projection.cast(&Interner);
 
     let in_env = InEnvironment { value: obligation, environment: ty.environment };
 
-    let canonical = Canonical::new(
-        in_env,
-        ty.value.kinds.iter().copied().chain(Some(chalk_ir::TyVariableKind::General)),
-    );
+    let canonical = Canonical {
+        value: in_env,
+        binders: CanonicalVarKinds::from_iter(
+            &Interner,
+            ty.value.binders.iter(&Interner).cloned().chain(Some(chalk_ir::WithKind::new(
+                chalk_ir::VariableKind::Ty(chalk_ir::TyVariableKind::General),
+                chalk_ir::UniverseIndex::ROOT,
+            ))),
+        ),
+    };
 
     let solution = db.trait_solve(krate, canonical)?;
 
@@ -121,7 +130,7 @@ fn deref_by_trait(
             // assumptions will be broken. We would need to properly introduce
             // new variables in that case
 
-            for i in 1..vars.0.kinds.len() {
+            for i in 1..vars.0.binders.len(&Interner) {
                 if vars.0.value[i - 1].interned(&Interner)
                     != &TyKind::BoundVar(BoundVar::new(DebruijnIndex::INNERMOST, i - 1))
                 {
@@ -131,7 +140,7 @@ fn deref_by_trait(
             }
             Some(Canonical {
                 value: vars.0.value[vars.0.value.len() - 1].clone(),
-                kinds: vars.0.kinds.clone(),
+                binders: vars.0.binders.clone(),
             })
         }
         Solution::Ambig(_) => {
diff --git a/crates/hir_ty/src/infer/unify.rs b/crates/hir_ty/src/infer/unify.rs
index 35b0a2059..7595b46cf 100644
--- a/crates/hir_ty/src/infer/unify.rs
+++ b/crates/hir_ty/src/infer/unify.rs
@@ -2,13 +2,13 @@
 
 use std::borrow::Cow;
 
-use chalk_ir::{FloatTy, IntTy, TyVariableKind};
+use chalk_ir::{FloatTy, IntTy, TyVariableKind, UniverseIndex, VariableKind};
 use ena::unify::{InPlaceUnificationTable, NoError, UnifyKey, UnifyValue};
 
 use super::{DomainGoal, InferenceContext};
 use crate::{
-    AliasEq, AliasTy, BoundVar, Canonical, DebruijnIndex, FnPointer, InEnvironment, InferenceVar,
-    Interner, Scalar, Substitution, Ty, TyKind, TypeWalk, WhereClause,
+    AliasEq, AliasTy, BoundVar, Canonical, CanonicalVarKinds, DebruijnIndex, FnPointer,
+    InEnvironment, InferenceVar, Interner, Scalar, Substitution, Ty, TyKind, TypeWalk, WhereClause,
 };
 
 impl<'a> InferenceContext<'a> {
@@ -76,8 +76,17 @@ impl<'a, 'b> Canonicalizer<'a, 'b> {
     }
 
     fn into_canonicalized<T>(self, result: T) -> Canonicalized<T> {
-        let kinds = self.free_vars.iter().map(|&(_, k)| k).collect();
-        Canonicalized { value: Canonical { value: result, kinds }, free_vars: self.free_vars }
+        let kinds = self
+            .free_vars
+            .iter()
+            .map(|&(_, k)| chalk_ir::WithKind::new(VariableKind::Ty(k), UniverseIndex::ROOT));
+        Canonicalized {
+            value: Canonical {
+                value: result,
+                binders: CanonicalVarKinds::from_iter(&Interner, kinds),
+            },
+            free_vars: self.free_vars,
+        }
     }
 
     pub(crate) fn canonicalize_ty(mut self, ty: Ty) -> Canonicalized<Ty> {
@@ -125,12 +134,19 @@ impl<T> Canonicalized<T> {
         // the solution may contain new variables, which we need to convert to new inference vars
         let new_vars = Substitution(
             solution
-                .kinds
-                .iter()
-                .map(|k| match k {
-                    TyVariableKind::General => ctx.table.new_type_var(),
-                    TyVariableKind::Integer => ctx.table.new_integer_var(),
-                    TyVariableKind::Float => ctx.table.new_float_var(),
+                .binders
+                .iter(&Interner)
+                .map(|k| match k.kind {
+                    VariableKind::Ty(TyVariableKind::General) => ctx.table.new_type_var(),
+                    VariableKind::Ty(TyVariableKind::Integer) => ctx.table.new_integer_var(),
+                    VariableKind::Ty(TyVariableKind::Float) => ctx.table.new_float_var(),
+                    // HACK: Chalk can sometimes return new lifetime variables. We
+                    // want to just skip them, but to not mess up the indices of
+                    // other variables, we'll just create a new type variable in
+                    // their place instead. This should not matter (we never see the
+                    // actual *uses* of the lifetime variable).
+                    VariableKind::Lifetime => ctx.table.new_type_var(),
+                    _ => panic!("const variable in solution"),
                 })
                 .collect(),
         );
@@ -147,8 +163,8 @@ impl<T> Canonicalized<T> {
 pub(crate) fn unify(tys: &Canonical<(Ty, Ty)>) -> Option<Substitution> {
     let mut table = InferenceTable::new();
     let vars = Substitution(
-        tys.kinds
-            .iter()
+        tys.binders
+            .iter(&Interner)
             // we always use type vars here because we want everything to
             // fallback to Unknown in the end (kind of hacky, as below)
             .map(|_| table.new_type_var())
@@ -170,7 +186,7 @@ pub(crate) fn unify(tys: &Canonical<(Ty, Ty)>) -> Option<Substitution> {
         }
     }
     Some(
-        Substitution::builder(tys.kinds.len())
+        Substitution::builder(tys.binders.len(&Interner))
             .fill(vars.iter().map(|v| table.resolve_ty_completely(v.clone())))
             .build(),
     )
diff --git a/crates/hir_ty/src/lib.rs b/crates/hir_ty/src/lib.rs
index 90b5b17e2..0f49dd39b 100644
--- a/crates/hir_ty/src/lib.rs
+++ b/crates/hir_ty/src/lib.rs
@@ -61,6 +61,8 @@ pub type ClosureId = chalk_ir::ClosureId<Interner>;
 pub type OpaqueTyId = chalk_ir::OpaqueTyId<Interner>;
 pub type PlaceholderIndex = chalk_ir::PlaceholderIndex;
 
+pub type CanonicalVarKinds = chalk_ir::CanonicalVarKinds<Interner>;
+
 pub type ChalkTraitId = chalk_ir::TraitId<Interner>;
 
 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
@@ -662,12 +664,18 @@ impl QuantifiedWhereClauses {
 #[derive(Debug, Clone, PartialEq, Eq, Hash)]
 pub struct Canonical<T> {
     pub value: T,
-    pub kinds: Arc<[TyVariableKind]>,
+    pub binders: CanonicalVarKinds,
 }
 
 impl<T> Canonical<T> {
     pub fn new(value: T, kinds: impl IntoIterator<Item = TyVariableKind>) -> Self {
-        Self { value, kinds: kinds.into_iter().collect() }
+        let kinds = kinds.into_iter().map(|tk| {
+            chalk_ir::CanonicalVarKind::new(
+                chalk_ir::VariableKind::Ty(tk),
+                chalk_ir::UniverseIndex::ROOT,
+            )
+        });
+        Self { value, binders: chalk_ir::CanonicalVarKinds::from_iter(&Interner, kinds) }
     }
 }
 
diff --git a/crates/hir_ty/src/method_resolution.rs b/crates/hir_ty/src/method_resolution.rs
index da6bc2a4a..0abe8f0a3 100644
--- a/crates/hir_ty/src/method_resolution.rs
+++ b/crates/hir_ty/src/method_resolution.rs
@@ -6,7 +6,7 @@ use std::{iter, sync::Arc};
 
 use arrayvec::ArrayVec;
 use base_db::CrateId;
-use chalk_ir::{cast::Cast, Mutability};
+use chalk_ir::{cast::Cast, Mutability, UniverseIndex};
 use hir_def::{
     lang_item::LangItemTarget, AssocContainerId, AssocItemId, FunctionId, GenericDefId, HasModule,
     ImplId, Lookup, ModuleId, TraitId,
@@ -21,8 +21,9 @@ use crate::{
     primitive::{self, FloatTy, IntTy, UintTy},
     to_chalk_trait_id,
     utils::all_super_traits,
-    AdtId, Canonical, DebruijnIndex, FnPointer, FnSig, ForeignDefId, InEnvironment, Interner,
-    Scalar, Substitution, TraitEnvironment, TraitRef, Ty, TyKind, TypeWalk,
+    AdtId, Canonical, CanonicalVarKinds, DebruijnIndex, FnPointer, FnSig, ForeignDefId,
+    InEnvironment, Interner, Scalar, Substitution, TraitEnvironment, TraitRef, Ty, TyKind,
+    TypeWalk,
 };
 
 /// This is used as a key for indexing impls.
@@ -443,7 +444,7 @@ fn iterate_method_candidates_with_autoref(
         return true;
     }
     let refed = Canonical {
-        kinds: deref_chain[0].kinds.clone(),
+        binders: deref_chain[0].binders.clone(),
         value: TyKind::Ref(Mutability::Not, deref_chain[0].value.clone()).intern(&Interner),
     };
     if iterate_method_candidates_by_receiver(
@@ -459,7 +460,7 @@ fn iterate_method_candidates_with_autoref(
         return true;
     }
     let ref_muted = Canonical {
-        kinds: deref_chain[0].kinds.clone(),
+        binders: deref_chain[0].binders.clone(),
         value: TyKind::Ref(Mutability::Mut, deref_chain[0].value.clone()).intern(&Interner),
     };
     if iterate_method_candidates_by_receiver(
@@ -677,19 +678,28 @@ pub(crate) fn inherent_impl_substs(
     // we create a var for each type parameter of the impl; we need to keep in
     // mind here that `self_ty` might have vars of its own
     let vars = Substitution::build_for_def(db, impl_id)
-        .fill_with_bound_vars(DebruijnIndex::INNERMOST, self_ty.kinds.len())
+        .fill_with_bound_vars(DebruijnIndex::INNERMOST, self_ty.binders.len(&Interner))
         .build();
     let self_ty_with_vars = db.impl_self_ty(impl_id).subst(&vars);
-    let mut kinds = self_ty.kinds.to_vec();
-    kinds.extend(iter::repeat(chalk_ir::TyVariableKind::General).take(vars.len()));
-    let tys = Canonical { kinds: kinds.into(), value: (self_ty_with_vars, self_ty.value.clone()) };
+    let mut kinds = self_ty.binders.interned().to_vec();
+    kinds.extend(
+        iter::repeat(chalk_ir::WithKind::new(
+            chalk_ir::VariableKind::Ty(chalk_ir::TyVariableKind::General),
+            UniverseIndex::ROOT,
+        ))
+        .take(vars.len()),
+    );
+    let tys = Canonical {
+        binders: CanonicalVarKinds::from_iter(&Interner, kinds),
+        value: (self_ty_with_vars, self_ty.value.clone()),
+    };
     let substs = super::infer::unify(&tys);
     // We only want the substs for the vars we added, not the ones from self_ty.
     // Also, if any of the vars we added are still in there, we replace them by
     // Unknown. I think this can only really happen if self_ty contained
     // Unknown, and in that case we want the result to contain Unknown in those
     // places again.
-    substs.map(|s| fallback_bound_vars(s.suffix(vars.len()), self_ty.kinds.len()))
+    substs.map(|s| fallback_bound_vars(s.suffix(vars.len()), self_ty.binders.len(&Interner)))
 }
 
 /// This replaces any 'free' Bound vars in `s` (i.e. those with indices past
@@ -768,15 +778,24 @@ fn generic_implements_goal(
     trait_: TraitId,
     self_ty: Canonical<Ty>,
 ) -> Canonical<InEnvironment<super::DomainGoal>> {
-    let mut kinds = self_ty.kinds.to_vec();
+    let mut kinds = self_ty.binders.interned().to_vec();
     let substs = super::Substitution::build_for_def(db, trait_)
         .push(self_ty.value)
         .fill_with_bound_vars(DebruijnIndex::INNERMOST, kinds.len())
         .build();
-    kinds.extend(iter::repeat(chalk_ir::TyVariableKind::General).take(substs.len() - 1));
+    kinds.extend(
+        iter::repeat(chalk_ir::WithKind::new(
+            chalk_ir::VariableKind::Ty(chalk_ir::TyVariableKind::General),
+            UniverseIndex::ROOT,
+        ))
+        .take(substs.len() - 1),
+    );
     let trait_ref = TraitRef { trait_id: to_chalk_trait_id(trait_), substitution: substs };
     let obligation = trait_ref.cast(&Interner);
-    Canonical { kinds: kinds.into(), value: InEnvironment::new(env, obligation) }
+    Canonical {
+        binders: CanonicalVarKinds::from_iter(&Interner, kinds),
+        value: InEnvironment::new(env, obligation),
+    }
 }
 
 fn autoderef_method_receiver(
@@ -789,9 +808,9 @@ fn autoderef_method_receiver(
     if let Some(TyKind::Array(parameters)) =
         deref_chain.last().map(|ty| ty.value.interned(&Interner))
     {
-        let kinds = deref_chain.last().unwrap().kinds.clone();
+        let kinds = deref_chain.last().unwrap().binders.clone();
         let unsized_ty = TyKind::Slice(parameters.clone()).intern(&Interner);
-        deref_chain.push(Canonical { value: unsized_ty, kinds })
+        deref_chain.push(Canonical { value: unsized_ty, binders: kinds })
     }
     deref_chain
 }
diff --git a/crates/hir_ty/src/traits/chalk/mapping.rs b/crates/hir_ty/src/traits/chalk/mapping.rs
index 7209dd14e..58d8f2894 100644
--- a/crates/hir_ty/src/traits/chalk/mapping.rs
+++ b/crates/hir_ty/src/traits/chalk/mapping.rs
@@ -439,35 +439,12 @@ where
     type Chalk = chalk_ir::Canonical<T::Chalk>;
 
     fn to_chalk(self, db: &dyn HirDatabase) -> chalk_ir::Canonical<T::Chalk> {
-        let kinds = self.kinds.iter().map(|&tk| {
-            chalk_ir::CanonicalVarKind::new(
-                chalk_ir::VariableKind::Ty(tk),
-                chalk_ir::UniverseIndex::ROOT,
-            )
-        });
         let value = self.value.to_chalk(db);
-        chalk_ir::Canonical {
-            value,
-            binders: chalk_ir::CanonicalVarKinds::from_iter(&Interner, kinds),
-        }
+        chalk_ir::Canonical { value, binders: self.binders }
     }
 
     fn from_chalk(db: &dyn HirDatabase, canonical: chalk_ir::Canonical<T::Chalk>) -> Canonical<T> {
-        let kinds = canonical
-            .binders
-            .iter(&Interner)
-            .map(|k| match k.kind {
-                chalk_ir::VariableKind::Ty(tk) => tk,
-                // HACK: Chalk can sometimes return new lifetime variables. We
-                // want to just skip them, but to not mess up the indices of
-                // other variables, we'll just create a new type variable in
-                // their place instead. This should not matter (we never see the
-                // actual *uses* of the lifetime variable).
-                chalk_ir::VariableKind::Lifetime => chalk_ir::TyVariableKind::General,
-                chalk_ir::VariableKind::Const(_) => panic!("unexpected const from Chalk"),
-            })
-            .collect();
-        Canonical { kinds, value: from_chalk(db, canonical.value) }
+        Canonical { binders: canonical.binders, value: from_chalk(db, canonical.value) }
     }
 }