1 files changed, 71 insertions, 19 deletions

diff --git a/crates/hir_ty/src/lib.rs b/crates/hir_ty/src/lib.rs
index ad908f957..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)]
@@ -132,6 +134,12 @@ impl TypeWalk for ProjectionTy {
     }
 }
 
+#[derive(Clone, PartialEq, Eq, Debug, Hash)]
+pub struct DynTy {
+    /// The unknown self type.
+    pub bounds: Binders<QuantifiedWhereClauses>,
+}
+
 pub type FnSig = chalk_ir::FnSig<Interner>;
 
 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
@@ -283,7 +291,7 @@ pub enum TyKind {
     /// represents the `Self` type inside the bounds. This is currently
     /// implicit; Chalk has the `Binders` struct to make it explicit, but it
     /// didn't seem worth the overhead yet.
-    Dyn(Arc<[WhereClause]>),
+    Dyn(DynTy),
 
     /// A placeholder for a type which could not be computed; this is propagated
     /// to avoid useless error messages. Doubles as a placeholder where type
@@ -490,6 +498,13 @@ impl<T> Binders<T> {
         Self { num_binders, value }
     }
 
+    pub fn wrap_empty(value: T) -> Self
+    where
+        T: TypeWalk,
+    {
+        Self { num_binders: 0, value: value.shift_bound_vars(DebruijnIndex::ONE) }
+    }
+
     pub fn as_ref(&self) -> Binders<&T> {
         Binders { num_binders: self.num_binders, value: &self.value }
     }
@@ -501,6 +516,14 @@ impl<T> Binders<T> {
     pub fn filter_map<U>(self, f: impl FnOnce(T) -> Option<U>) -> Option<Binders<U>> {
         Some(Binders { num_binders: self.num_binders, value: f(self.value)? })
     }
+
+    pub fn skip_binders(&self) -> &T {
+        &self.value
+    }
+
+    pub fn into_value_and_skipped_binders(self) -> (T, usize) {
+        (self.value, self.num_binders)
+    }
 }
 
 impl<T: Clone> Binders<&T> {
@@ -614,6 +637,24 @@ impl TypeWalk for WhereClause {
     }
 }
 
+pub type QuantifiedWhereClause = Binders<WhereClause>;
+
+#[derive(Debug, Clone, PartialEq, Eq, Hash)]
+pub struct QuantifiedWhereClauses(Arc<[QuantifiedWhereClause]>);
+
+impl QuantifiedWhereClauses {
+    pub fn from_iter(
+        _interner: &Interner,
+        elements: impl IntoIterator<Item = QuantifiedWhereClause>,
+    ) -> Self {
+        QuantifiedWhereClauses(elements.into_iter().collect())
+    }
+
+    pub fn interned(&self) -> &Arc<[QuantifiedWhereClause]> {
+        &self.0
+    }
+}
+
 /// Basically a claim (currently not validated / checked) that the contained
 /// type / trait ref contains no inference variables; any inference variables it
 /// contained have been replaced by bound variables, and `kinds` tells us how
@@ -623,12 +664,18 @@ impl TypeWalk for WhereClause {
 #[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) }
     }
 }
 
@@ -810,12 +857,14 @@ impl Ty {
     }
 
     /// If this is a `dyn Trait` type, this returns the `Trait` part.
-    pub fn dyn_trait_ref(&self) -> Option<&TraitRef> {
+    fn dyn_trait_ref(&self) -> Option<&TraitRef> {
         match self.interned(&Interner) {
-            TyKind::Dyn(bounds) => bounds.get(0).and_then(|b| match b {
-                WhereClause::Implemented(trait_ref) => Some(trait_ref),
-                _ => None,
-            }),
+            TyKind::Dyn(dyn_ty) => {
+                dyn_ty.bounds.value.interned().get(0).and_then(|b| match b.skip_binders() {
+                    WhereClause::Implemented(trait_ref) => Some(trait_ref),
+                    _ => None,
+                })
+            }
             _ => None,
         }
     }
@@ -892,7 +941,7 @@ impl Ty {
         }
     }
 
-    pub fn impl_trait_bounds(&self, db: &dyn HirDatabase) -> Option<Vec<WhereClause>> {
+    pub fn impl_trait_bounds(&self, db: &dyn HirDatabase) -> Option<Vec<QuantifiedWhereClause>> {
         match self.interned(&Interner) {
             TyKind::OpaqueType(opaque_ty_id, ..) => {
                 match db.lookup_intern_impl_trait_id((*opaque_ty_id).into()) {
@@ -905,10 +954,13 @@ impl Ty {
                             // This is only used by type walking.
                             // Parameters will be walked outside, and projection predicate is not used.
                             // So just provide the Future trait.
-                            let impl_bound = WhereClause::Implemented(TraitRef {
-                                trait_id: to_chalk_trait_id(future_trait),
-                                substitution: Substitution::empty(),
-                            });
+                            let impl_bound = Binders::new(
+                                0,
+                                WhereClause::Implemented(TraitRef {
+                                    trait_id: to_chalk_trait_id(future_trait),
+                                    substitution: Substitution::empty(),
+                                }),
+                            );
                             Some(vec![impl_bound])
                         } else {
                             None
@@ -945,7 +997,7 @@ impl Ty {
                             .generic_predicates(id.parent)
                             .into_iter()
                             .map(|pred| pred.clone().subst(&substs))
-                            .filter(|wc| match &wc {
+                            .filter(|wc| match &wc.skip_binders() {
                                 WhereClause::Implemented(tr) => tr.self_type_parameter() == self,
                                 WhereClause::AliasEq(AliasEq {
                                     alias: AliasTy::Projection(proj),
@@ -1094,8 +1146,8 @@ impl TypeWalk for Ty {
                     t.walk(f);
                 }
             }
-            TyKind::Dyn(predicates) => {
-                for p in predicates.iter() {
+            TyKind::Dyn(dyn_ty) => {
+                for p in dyn_ty.bounds.value.interned().iter() {
                     p.walk(f);
                 }
             }
@@ -1122,8 +1174,8 @@ impl TypeWalk for Ty {
             TyKind::Alias(AliasTy::Projection(p_ty)) => {
                 p_ty.substitution.walk_mut_binders(f, binders);
             }
-            TyKind::Dyn(predicates) => {
-                for p in make_mut_slice(predicates) {
+            TyKind::Dyn(dyn_ty) => {
+                for p in make_mut_slice(&mut dyn_ty.bounds.value.0) {
                     p.walk_mut_binders(f, binders.shifted_in());
                 }
             }
@@ -1173,7 +1225,7 @@ pub struct ReturnTypeImplTraits {
 
 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
 pub(crate) struct ReturnTypeImplTrait {
-    pub(crate) bounds: Binders<Vec<WhereClause>>,
+    pub(crate) bounds: Binders<Vec<QuantifiedWhereClause>>,
 }
 
 pub fn to_foreign_def_id(id: TypeAliasId) -> ForeignDefId {