1 files changed, 72 insertions, 47 deletions

diff --git a/crates/hir_ty/src/infer/unify.rs b/crates/hir_ty/src/infer/unify.rs
index b2d4f67b3..75250a369 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::{InferenceContext, Obligation};
+use super::{DomainGoal, InferenceContext};
 use crate::{
-    BoundVar, Canonical, DebruijnIndex, FnPointer, GenericPredicate, InEnvironment, InferenceVar,
-    Interner, Scalar, Substitution, Ty, TyKind, TypeWalk,
+    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> {
@@ -87,20 +96,14 @@ impl<'a, 'b> Canonicalizer<'a, 'b> {
 
     pub(crate) fn canonicalize_obligation(
         mut self,
-        obligation: InEnvironment<Obligation>,
-    ) -> Canonicalized<InEnvironment<Obligation>> {
-        let result = match obligation.value {
-            Obligation::Trait(tr) => {
-                Obligation::Trait(self.do_canonicalize(tr, DebruijnIndex::INNERMOST))
-            }
-            Obligation::Projection(pr) => {
-                Obligation::Projection(self.do_canonicalize(pr, DebruijnIndex::INNERMOST))
+        obligation: InEnvironment<DomainGoal>,
+    ) -> Canonicalized<InEnvironment<DomainGoal>> {
+        let result = match obligation.goal {
+            DomainGoal::Holds(wc) => {
+                DomainGoal::Holds(self.do_canonicalize(wc, DebruijnIndex::INNERMOST))
             }
         };
-        self.into_canonicalized(InEnvironment {
-            value: result,
-            environment: obligation.environment,
-        })
+        self.into_canonicalized(InEnvironment { goal: result, environment: obligation.environment })
     }
 }
 
@@ -128,12 +131,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(),
         );
@@ -150,8 +160,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())
@@ -173,7 +183,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(),
     )
@@ -313,9 +323,18 @@ impl InferenceTable {
 
             (TyKind::Placeholder(p1), TyKind::Placeholder(p2)) if *p1 == *p2 => true,
 
-            (TyKind::Dyn(dyn1), TyKind::Dyn(dyn2)) if dyn1.len() == dyn2.len() => {
-                for (pred1, pred2) in dyn1.iter().zip(dyn2.iter()) {
-                    if !self.unify_preds(pred1, pred2, depth + 1) {
+            (TyKind::Dyn(dyn1), TyKind::Dyn(dyn2))
+                if dyn1.bounds.skip_binders().interned().len()
+                    == dyn2.bounds.skip_binders().interned().len() =>
+            {
+                for (pred1, pred2) in dyn1
+                    .bounds
+                    .skip_binders()
+                    .interned()
+                    .iter()
+                    .zip(dyn2.bounds.skip_binders().interned().iter())
+                {
+                    if !self.unify_preds(pred1.skip_binders(), pred2.skip_binders(), depth + 1) {
                         return false;
                     }
                 }
@@ -382,26 +401,32 @@ impl InferenceTable {
         }
     }
 
-    fn unify_preds(
-        &mut self,
-        pred1: &GenericPredicate,
-        pred2: &GenericPredicate,
-        depth: usize,
-    ) -> bool {
+    fn unify_preds(&mut self, pred1: &WhereClause, pred2: &WhereClause, depth: usize) -> bool {
         match (pred1, pred2) {
-            (GenericPredicate::Implemented(tr1), GenericPredicate::Implemented(tr2))
-                if tr1.trait_ == tr2.trait_ =>
+            (WhereClause::Implemented(tr1), WhereClause::Implemented(tr2))
+                if tr1.trait_id == tr2.trait_id =>
             {
-                self.unify_substs(&tr1.substs, &tr2.substs, depth + 1)
+                self.unify_substs(&tr1.substitution, &tr2.substitution, depth + 1)
             }
-            (GenericPredicate::Projection(proj1), GenericPredicate::Projection(proj2))
-                if proj1.projection_ty.associated_ty_id == proj2.projection_ty.associated_ty_id =>
-            {
-                self.unify_substs(
-                    &proj1.projection_ty.substitution,
-                    &proj2.projection_ty.substitution,
-                    depth + 1,
-                ) && self.unify_inner(&proj1.ty, &proj2.ty, depth + 1)
+            (
+                WhereClause::AliasEq(AliasEq { alias: alias1, ty: ty1 }),
+                WhereClause::AliasEq(AliasEq { alias: alias2, ty: ty2 }),
+            ) => {
+                let (substitution1, substitution2) = match (alias1, alias2) {
+                    (AliasTy::Projection(projection_ty1), AliasTy::Projection(projection_ty2))
+                        if projection_ty1.associated_ty_id == projection_ty2.associated_ty_id =>
+                    {
+                        (&projection_ty1.substitution, &projection_ty2.substitution)
+                    }
+                    (AliasTy::Opaque(opaque1), AliasTy::Opaque(opaque2))
+                        if opaque1.opaque_ty_id == opaque2.opaque_ty_id =>
+                    {
+                        (&opaque1.substitution, &opaque2.substitution)
+                    }
+                    _ => return false,
+                };
+                self.unify_substs(&substitution1, &substitution2, depth + 1)
+                    && self.unify_inner(&ty1, &ty2, depth + 1)
             }
             _ => false,
         }