14 files changed, 337 insertions, 215 deletions

diff --git a/crates/hir_ty/src/autoderef.rs b/crates/hir_ty/src/autoderef.rs
index 23ab042c1..dc5fc759a 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;
@@ -27,9 +27,9 @@ pub fn autoderef<'a>(
     krate: Option<CrateId>,
     ty: InEnvironment<Canonical<Ty>>,
 ) -> impl Iterator<Item = Canonical<Ty>> + 'a {
-    let InEnvironment { value: ty, environment } = ty;
+    let InEnvironment { goal: ty, environment } = ty;
     successors(Some(ty), move |ty| {
-        deref(db, krate?, InEnvironment { value: ty, environment: environment.clone() })
+        deref(db, krate?, InEnvironment { goal: ty, environment: environment.clone() })
     })
     .take(AUTODEREF_RECURSION_LIMIT)
 }
@@ -39,8 +39,8 @@ pub(crate) fn deref(
     krate: CrateId,
     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() })
+    if let Some(derefed) = ty.goal.value.builtin_deref() {
+        Some(Canonical { value: derefed, binders: ty.goal.binders.clone() })
     } else {
         deref_by_trait(db, krate, ty)
     }
@@ -67,15 +67,15 @@ fn deref_by_trait(
     // FIXME make the Canonical / bound var handling nicer
 
     let parameters =
-        Substitution::build_for_generics(&generic_params).push(ty.value.value.clone()).build();
+        Substitution::build_for_generics(&generic_params).push(ty.goal.value.clone()).build();
 
     // Check that the type implements Deref at all
     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.goal.binders.clone(),
         value: InEnvironment {
-            value: trait_ref.cast(&Interner),
+            goal: 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.goal.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 in_env = InEnvironment { goal: obligation, environment: ty.environment };
+
+    let canonical = Canonical {
+        value: in_env,
+        binders: CanonicalVarKinds::from_iter(
+            &Interner,
+            ty.goal.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,21 +130,21 @@ 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))
                 {
-                    warn!("complex solution for derefing {:?}: {:?}, ignoring", ty.value, solution);
+                    warn!("complex solution for derefing {:?}: {:?}, ignoring", ty.goal, solution);
                     return None;
                 }
             }
             Some(Canonical {
                 value: vars.0.value[vars.0.value.len() - 1].clone(),
-                kinds: vars.0.kinds.clone(),
+                binders: vars.0.binders.clone(),
             })
         }
         Solution::Ambig(_) => {
-            info!("Ambiguous solution for derefing {:?}: {:?}", ty.value, solution);
+            info!("Ambiguous solution for derefing {:?}: {:?}", ty.goal, solution);
             None
         }
     }
diff --git a/crates/hir_ty/src/db.rs b/crates/hir_ty/src/db.rs
index 91a2e0b5b..58e4247c6 100644
--- a/crates/hir_ty/src/db.rs
+++ b/crates/hir_ty/src/db.rs
@@ -12,8 +12,8 @@ use la_arena::ArenaMap;
 use crate::{
     method_resolution::{InherentImpls, TraitImpls},
     traits::chalk,
-    Binders, CallableDefId, FnDefId, ImplTraitId, InferenceResult, PolyFnSig, ReturnTypeImplTraits,
-    TraitRef, Ty, TyDefId, ValueTyDefId, WhereClause,
+    Binders, CallableDefId, FnDefId, ImplTraitId, InferenceResult, PolyFnSig,
+    QuantifiedWhereClause, ReturnTypeImplTraits, TraitRef, Ty, TyDefId, ValueTyDefId,
 };
 use hir_expand::name::Name;
 
@@ -57,10 +57,13 @@ pub trait HirDatabase: DefDatabase + Upcast<dyn DefDatabase> {
 
     #[salsa::invoke(crate::lower::generic_predicates_for_param_query)]
     #[salsa::cycle(crate::lower::generic_predicates_for_param_recover)]
-    fn generic_predicates_for_param(&self, param_id: TypeParamId) -> Arc<[Binders<WhereClause>]>;
+    fn generic_predicates_for_param(
+        &self,
+        param_id: TypeParamId,
+    ) -> Arc<[Binders<QuantifiedWhereClause>]>;
 
     #[salsa::invoke(crate::lower::generic_predicates_query)]
-    fn generic_predicates(&self, def: GenericDefId) -> Arc<[Binders<WhereClause>]>;
+    fn generic_predicates(&self, def: GenericDefId) -> Arc<[Binders<QuantifiedWhereClause>]>;
 
     #[salsa::invoke(crate::lower::trait_environment_query)]
     fn trait_environment(&self, def: GenericDefId) -> Arc<crate::TraitEnvironment>;
diff --git a/crates/hir_ty/src/display.rs b/crates/hir_ty/src/display.rs
index 9d3b79be3..6149067c7 100644
--- a/crates/hir_ty/src/display.rs
+++ b/crates/hir_ty/src/display.rs
@@ -1,6 +1,6 @@
 //! FIXME: write short doc here
 
-use std::{borrow::Cow, fmt};
+use std::fmt;
 
 use arrayvec::ArrayVec;
 use chalk_ir::Mutability;
@@ -20,7 +20,7 @@ use crate::{
     db::HirDatabase, from_assoc_type_id, from_foreign_def_id, from_placeholder_idx, primitive,
     to_assoc_type_id, traits::chalk::from_chalk, utils::generics, AdtId, AliasEq, AliasTy,
     CallableDefId, CallableSig, DomainGoal, ImplTraitId, Interner, Lifetime, OpaqueTy,
-    ProjectionTy, Scalar, Substitution, TraitRef, Ty, TyKind, WhereClause,
+    ProjectionTy, QuantifiedWhereClause, Scalar, Substitution, TraitRef, Ty, TyKind, WhereClause,
 };
 
 pub struct HirFormatter<'a> {
@@ -190,6 +190,7 @@ impl DisplayTarget {
 pub enum DisplaySourceCodeError {
     PathNotFound,
     UnknownType,
+    Closure,
 }
 
 pub enum HirDisplayError {
@@ -328,9 +329,9 @@ impl HirDisplay for Ty {
 
                 // FIXME: all this just to decide whether to use parentheses...
                 let datas;
-                let predicates = match t.interned(&Interner) {
-                    TyKind::Dyn(predicates) if predicates.len() > 1 => {
-                        Cow::Borrowed(predicates.as_ref())
+                let predicates: Vec<_> = match t.interned(&Interner) {
+                    TyKind::Dyn(dyn_ty) if dyn_ty.bounds.skip_binders().interned().len() > 1 => {
+                        dyn_ty.bounds.skip_binders().interned().iter().cloned().collect()
                     }
                     &TyKind::Alias(AliasTy::Opaque(OpaqueTy {
                         opaque_ty_id,
@@ -345,17 +346,21 @@ impl HirDisplay for Ty {
                                 .as_ref()
                                 .map(|rpit| rpit.impl_traits[idx as usize].bounds.clone());
                             let bounds = data.subst(parameters);
-                            Cow::Owned(bounds.value)
+                            bounds.value
                         } else {
-                            Cow::Borrowed(&[][..])
+                            Vec::new()
                         }
                     }
-                    _ => Cow::Borrowed(&[][..]),
+                    _ => Vec::new(),
                 };
 
-                if let [WhereClause::Implemented(trait_ref), _] = predicates.as_ref() {
+                if let Some(WhereClause::Implemented(trait_ref)) =
+                    predicates.get(0).map(|b| b.skip_binders())
+                {
                     let trait_ = trait_ref.hir_trait_id();
-                    if fn_traits(f.db.upcast(), trait_).any(|it| it == trait_) {
+                    if fn_traits(f.db.upcast(), trait_).any(|it| it == trait_)
+                        && predicates.len() <= 2
+                    {
                         return write!(f, "{}", ty_display);
                     }
                 }
@@ -539,6 +544,11 @@ impl HirDisplay for Ty {
                 }
             }
             TyKind::Closure(.., substs) => {
+                if f.display_target.is_source_code() {
+                    return Err(HirDisplayError::DisplaySourceCodeError(
+                        DisplaySourceCodeError::Closure,
+                    ));
+                }
                 let sig = substs[0].callable_sig(f.db);
                 if let Some(sig) = sig {
                     if sig.params().is_empty() {
@@ -577,7 +587,7 @@ impl HirDisplay for 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),
@@ -591,8 +601,12 @@ impl HirDisplay for Ty {
                 }
             }
             TyKind::BoundVar(idx) => write!(f, "?{}.{}", idx.debruijn.depth(), idx.index)?,
-            TyKind::Dyn(predicates) => {
-                write_bounds_like_dyn_trait_with_prefix("dyn", predicates, f)?;
+            TyKind::Dyn(dyn_ty) => {
+                write_bounds_like_dyn_trait_with_prefix(
+                    "dyn",
+                    dyn_ty.bounds.skip_binders().interned(),
+                    f,
+                )?;
             }
             TyKind::Alias(AliasTy::Projection(p_ty)) => p_ty.hir_fmt(f)?,
             TyKind::Alias(AliasTy::Opaque(opaque_ty)) => {
@@ -661,7 +675,7 @@ fn fn_traits(db: &dyn DefDatabase, trait_: TraitId) -> impl Iterator<Item = Trai
 
 pub fn write_bounds_like_dyn_trait_with_prefix(
     prefix: &str,
-    predicates: &[WhereClause],
+    predicates: &[QuantifiedWhereClause],
     f: &mut HirFormatter,
 ) -> Result<(), HirDisplayError> {
     write!(f, "{}", prefix)?;
@@ -674,7 +688,7 @@ pub fn write_bounds_like_dyn_trait_with_prefix(
 }
 
 fn write_bounds_like_dyn_trait(
-    predicates: &[WhereClause],
+    predicates: &[QuantifiedWhereClause],
     f: &mut HirFormatter,
 ) -> Result<(), HirDisplayError> {
     // Note: This code is written to produce nice results (i.e.
@@ -687,7 +701,7 @@ fn write_bounds_like_dyn_trait(
     let mut angle_open = false;
     let mut is_fn_trait = false;
     for p in predicates.iter() {
-        match p {
+        match p.skip_binders() {
             WhereClause::Implemented(trait_ref) => {
                 let trait_ = trait_ref.hir_trait_id();
                 if !is_fn_trait {
diff --git a/crates/hir_ty/src/infer.rs b/crates/hir_ty/src/infer.rs
index b9e434c78..8f9cf7480 100644
--- a/crates/hir_ty/src/infer.rs
+++ b/crates/hir_ty/src/infer.rs
@@ -331,7 +331,7 @@ impl<'a> InferenceContext<'a> {
     fn resolve_obligations_as_possible(&mut self) {
         let obligations = mem::replace(&mut self.obligations, Vec::new());
         for obligation in obligations {
-            let in_env = InEnvironment::new(self.trait_env.clone(), obligation.clone());
+            let in_env = InEnvironment::new(self.trait_env.env.clone(), obligation.clone());
             let canonicalized = self.canonicalizer().canonicalize_obligation(in_env);
             let solution =
                 self.db.trait_solve(self.resolver.krate().unwrap(), canonicalized.value.clone());
diff --git a/crates/hir_ty/src/infer/coerce.rs b/crates/hir_ty/src/infer/coerce.rs
index 07eb96573..9c62932b1 100644
--- a/crates/hir_ty/src/infer/coerce.rs
+++ b/crates/hir_ty/src/infer/coerce.rs
@@ -142,7 +142,7 @@ impl<'a> InferenceContext<'a> {
             .build();
         let trait_ref =
             TraitRef { trait_id: to_chalk_trait_id(coerce_unsized_trait), substitution: substs };
-        let goal = InEnvironment::new(self.trait_env.clone(), trait_ref.cast(&Interner));
+        let goal = InEnvironment::new(self.trait_env.env.clone(), trait_ref.cast(&Interner));
 
         let canonicalizer = self.canonicalizer();
         let canonicalized = canonicalizer.canonicalize_obligation(goal);
@@ -170,8 +170,8 @@ impl<'a> InferenceContext<'a> {
             self.db,
             self.resolver.krate(),
             InEnvironment {
-                value: canonicalized.value.clone(),
-                environment: self.trait_env.clone(),
+                goal: canonicalized.value.clone(),
+                environment: self.trait_env.env.clone(),
             },
         ) {
             let derefed_ty = canonicalized.decanonicalize_ty(derefed_ty.value);
diff --git a/crates/hir_ty/src/infer/expr.rs b/crates/hir_ty/src/infer/expr.rs
index 24deff707..19249973c 100644
--- a/crates/hir_ty/src/infer/expr.rs
+++ b/crates/hir_ty/src/infer/expr.rs
@@ -11,6 +11,7 @@ use hir_def::{
     AssocContainerId, FieldId, Lookup,
 };
 use hir_expand::name::{name, Name};
+use stdx::always;
 use syntax::ast::RangeOp;
 
 use crate::{
@@ -89,12 +90,12 @@ impl<'a> InferenceContext<'a> {
         let substs =
             Substitution::build_for_generics(&generic_params).push(ty.clone()).push(arg_ty).build();
 
-        let trait_env = Arc::clone(&self.trait_env);
+        let trait_env = self.trait_env.env.clone();
         let implements_fn_trait: DomainGoal =
             TraitRef { trait_id: to_chalk_trait_id(fn_once_trait), substitution: substs.clone() }
                 .cast(&Interner);
         let goal = self.canonicalizer().canonicalize_obligation(InEnvironment {
-            value: implements_fn_trait.clone(),
+            goal: implements_fn_trait.clone(),
             environment: trait_env,
         });
         if self.db.trait_solve(krate, goal.value).is_some() {
@@ -298,8 +299,8 @@ impl<'a> InferenceContext<'a> {
                     self.db,
                     self.resolver.krate(),
                     InEnvironment {
-                        value: canonicalized.value.clone(),
-                        environment: self.trait_env.clone(),
+                        goal: canonicalized.value.clone(),
+                        environment: self.trait_env.env.clone(),
                     },
                 );
                 let (param_tys, ret_ty): (Vec<Ty>, Ty) = derefs
@@ -437,8 +438,8 @@ impl<'a> InferenceContext<'a> {
                     self.db,
                     self.resolver.krate(),
                     InEnvironment {
-                        value: canonicalized.value.clone(),
-                        environment: self.trait_env.clone(),
+                        goal: canonicalized.value.clone(),
+                        environment: self.trait_env.env.clone(),
                     },
                 )
                 .find_map(|derefed_ty| {
@@ -537,8 +538,8 @@ impl<'a> InferenceContext<'a> {
                                 self.db,
                                 krate,
                                 InEnvironment {
-                                    value: &canonicalized.value,
-                                    environment: self.trait_env.clone(),
+                                    goal: &canonicalized.value,
+                                    environment: self.trait_env.env.clone(),
                                 },
                             ) {
                                 Some(derefed_ty) => {
@@ -936,7 +937,9 @@ impl<'a> InferenceContext<'a> {
             let def: CallableDefId = from_chalk(self.db, *fn_def);
             let generic_predicates = self.db.generic_predicates(def.into());
             for predicate in generic_predicates.iter() {
-                let predicate = predicate.clone().subst(parameters);
+                let (predicate, binders) =
+                    predicate.clone().subst(parameters).into_value_and_skipped_binders();
+                always!(binders == 0); // quantified where clauses not yet handled
                 self.obligations.push(predicate.cast(&Interner));
             }
             // add obligation for trait implementation, if this is a trait method
diff --git a/crates/hir_ty/src/infer/unify.rs b/crates/hir_ty/src/infer/unify.rs
index 1fc03c8f4..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::{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> {
@@ -89,15 +98,12 @@ impl<'a, 'b> Canonicalizer<'a, 'b> {
         mut self,
         obligation: InEnvironment<DomainGoal>,
     ) -> Canonicalized<InEnvironment<DomainGoal>> {
-        let result = match obligation.value {
+        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 })
     }
 }
 
@@ -125,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(),
         );
@@ -147,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())
@@ -170,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(),
     )
@@ -310,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;
                     }
                 }
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 {
diff --git a/crates/hir_ty/src/lower.rs b/crates/hir_ty/src/lower.rs
index fd451a823..f60cec649 100644
--- a/crates/hir_ty/src/lower.rs
+++ b/crates/hir_ty/src/lower.rs
@@ -33,9 +33,10 @@ use crate::{
         all_super_trait_refs, associated_type_by_name_including_super_traits, generics,
         variant_data,
     },
-    AliasEq, AliasTy, Binders, BoundVar, CallableSig, DebruijnIndex, FnPointer, FnSig, ImplTraitId,
-    OpaqueTy, PolyFnSig, ProjectionTy, ReturnTypeImplTrait, ReturnTypeImplTraits, Substitution,
-    TraitEnvironment, TraitRef, Ty, TyKind, TypeWalk, WhereClause,
+    AliasEq, AliasTy, Binders, BoundVar, CallableSig, DebruijnIndex, DynTy, FnPointer, FnSig,
+    ImplTraitId, OpaqueTy, PolyFnSig, ProjectionTy, QuantifiedWhereClause, QuantifiedWhereClauses,
+    ReturnTypeImplTrait, ReturnTypeImplTraits, Substitution, TraitEnvironment, TraitRef, Ty,
+    TyKind, TypeWalk, WhereClause,
 };
 
 #[derive(Debug)]
@@ -188,13 +189,14 @@ impl<'a> TyLoweringContext<'a> {
             TypeRef::DynTrait(bounds) => {
                 let self_ty =
                     TyKind::BoundVar(BoundVar::new(DebruijnIndex::INNERMOST, 0)).intern(&Interner);
-                let predicates = self.with_shifted_in(DebruijnIndex::ONE, |ctx| {
-                    bounds
-                        .iter()
-                        .flat_map(|b| ctx.lower_type_bound(b, self_ty.clone(), false))
-                        .collect()
+                let bounds = self.with_shifted_in(DebruijnIndex::ONE, |ctx| {
+                    QuantifiedWhereClauses::from_iter(
+                        &Interner,
+                        bounds.iter().flat_map(|b| ctx.lower_type_bound(b, self_ty.clone(), false)),
+                    )
                 });
-                TyKind::Dyn(predicates).intern(&Interner)
+                let bounds = Binders::new(1, bounds);
+                TyKind::Dyn(DynTy { bounds }).intern(&Interner)
             }
             TypeRef::ImplTrait(bounds) => {
                 match self.impl_trait_mode {
@@ -376,7 +378,16 @@ impl<'a> TyLoweringContext<'a> {
                     // FIXME report error (ambiguous associated type)
                     TyKind::Unknown.intern(&Interner)
                 } else {
-                    TyKind::Dyn(Arc::new([WhereClause::Implemented(trait_ref)])).intern(&Interner)
+                    let dyn_ty = DynTy {
+                        bounds: Binders::new(
+                            1,
+                            QuantifiedWhereClauses::from_iter(
+                                &Interner,
+                                Some(Binders::wrap_empty(WhereClause::Implemented(trait_ref))),
+                            ),
+                        ),
+                    };
+                    TyKind::Dyn(dyn_ty).intern(&Interner)
                 };
                 return (ty, None);
             }
@@ -670,7 +681,7 @@ impl<'a> TyLoweringContext<'a> {
         &'a self,
         where_predicate: &'a WherePredicate,
         ignore_bindings: bool,
-    ) -> impl Iterator<Item = WhereClause> + 'a {
+    ) -> impl Iterator<Item = QuantifiedWhereClause> + 'a {
         match where_predicate {
             WherePredicate::ForLifetime { target, bound, .. }
             | WherePredicate::TypeBound { target, bound } => {
@@ -705,12 +716,12 @@ impl<'a> TyLoweringContext<'a> {
         bound: &'a TypeBound,
         self_ty: Ty,
         ignore_bindings: bool,
-    ) -> impl Iterator<Item = WhereClause> + 'a {
+    ) -> impl Iterator<Item = QuantifiedWhereClause> + 'a {
         let mut bindings = None;
         let trait_ref = match bound {
             TypeBound::Path(path) => {
                 bindings = self.lower_trait_ref_from_path(path, Some(self_ty));
-                bindings.clone().map(WhereClause::Implemented)
+                bindings.clone().map(WhereClause::Implemented).map(|b| Binders::wrap_empty(b))
             }
             TypeBound::Lifetime(_) => None,
             TypeBound::Error => None,
@@ -727,7 +738,7 @@ impl<'a> TyLoweringContext<'a> {
         &'a self,
         bound: &'a TypeBound,
         trait_ref: TraitRef,
-    ) -> impl Iterator<Item = WhereClause> + 'a {
+    ) -> impl Iterator<Item = QuantifiedWhereClause> + 'a {
         let last_segment = match bound {
             TypeBound::Path(path) => path.segments().last(),
             TypeBound::Error | TypeBound::Lifetime(_) => None,
@@ -743,7 +754,7 @@ impl<'a> TyLoweringContext<'a> {
                     &binding.name,
                 );
                 let (super_trait_ref, associated_ty) = match found {
-                    None => return SmallVec::<[WhereClause; 1]>::new(),
+                    None => return SmallVec::<[QuantifiedWhereClause; 1]>::new(),
                     Some(t) => t,
                 };
                 let projection_ty = ProjectionTy {
@@ -757,7 +768,7 @@ impl<'a> TyLoweringContext<'a> {
                     let ty = self.lower_ty(type_ref);
                     let alias_eq =
                         AliasEq { alias: AliasTy::Projection(projection_ty.clone()), ty };
-                    preds.push(WhereClause::AliasEq(alias_eq));
+                    preds.push(Binders::wrap_empty(WhereClause::AliasEq(alias_eq)));
                 }
                 for bound in &binding.bounds {
                     preds.extend(self.lower_type_bound(
@@ -814,7 +825,7 @@ pub fn associated_type_shorthand_candidates<R>(
             let predicates = db.generic_predicates_for_param(param_id);
             let mut traits_: Vec<_> = predicates
                 .iter()
-                .filter_map(|pred| match &pred.value {
+                .filter_map(|pred| match &pred.value.value {
                     WhereClause::Implemented(tr) => Some(tr.clone()),
                     _ => None,
                 })
@@ -887,7 +898,7 @@ pub(crate) fn field_types_query(
 pub(crate) fn generic_predicates_for_param_query(
     db: &dyn HirDatabase,
     param_id: TypeParamId,
-) -> Arc<[Binders<WhereClause>]> {
+) -> Arc<[Binders<QuantifiedWhereClause>]> {
     let resolver = param_id.parent.resolver(db.upcast());
     let ctx =
         TyLoweringContext::new(db, &resolver).with_type_param_mode(TypeParamLoweringMode::Variable);
@@ -915,7 +926,7 @@ pub(crate) fn generic_predicates_for_param_recover(
     _db: &dyn HirDatabase,
     _cycle: &[String],
     _param_id: &TypeParamId,
-) -> Arc<[Binders<WhereClause>]> {
+) -> Arc<[Binders<QuantifiedWhereClause>]> {
     Arc::new([])
 }
 
@@ -930,7 +941,7 @@ pub(crate) fn trait_environment_query(
     let mut clauses = Vec::new();
     for pred in resolver.where_predicates_in_scope() {
         for pred in ctx.lower_where_predicate(pred, false) {
-            if let WhereClause::Implemented(tr) = &pred {
+            if let WhereClause::Implemented(tr) = &pred.skip_binders() {
                 traits_in_scope.push((tr.self_type_parameter().clone(), tr.hir_trait_id()));
             }
             let program_clause: chalk_ir::ProgramClause<Interner> =
@@ -970,7 +981,7 @@ pub(crate) fn trait_environment_query(
 pub(crate) fn generic_predicates_query(
     db: &dyn HirDatabase,
     def: GenericDefId,
-) -> Arc<[Binders<WhereClause>]> {
+) -> Arc<[Binders<QuantifiedWhereClause>]> {
     let resolver = def.resolver(db.upcast());
     let ctx =
         TyLoweringContext::new(db, &resolver).with_type_param_mode(TypeParamLoweringMode::Variable);
diff --git a/crates/hir_ty/src/method_resolution.rs b/crates/hir_ty/src/method_resolution.rs
index da6bc2a4a..8e986ddde 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.
@@ -375,7 +376,7 @@ fn iterate_method_candidates_impl(
             // Also note that when we've got a receiver like &S, even if the method we
             // find in the end takes &self, we still do the autoderef step (just as
             // rustc does an autoderef and then autoref again).
-            let ty = InEnvironment { value: ty.clone(), environment: env.clone() };
+            let ty = InEnvironment { goal: ty.clone(), environment: env.env.clone() };
 
             // We have to be careful about the order we're looking at candidates
             // in here. Consider the case where we're resolving `x.clone()`
@@ -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(
@@ -621,7 +622,7 @@ pub fn resolve_indexing_op(
     krate: CrateId,
     index_trait: TraitId,
 ) -> Option<Canonical<Ty>> {
-    let ty = InEnvironment { value: ty.clone(), environment: env.clone() };
+    let ty = InEnvironment { goal: ty.clone(), environment: env.env.clone() };
     let deref_chain = autoderef_method_receiver(db, krate, ty);
     for ty in deref_chain {
         let goal = generic_implements_goal(db, env.clone(), index_trait, ty.clone());
@@ -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.env.clone(), 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.rs b/crates/hir_ty/src/traits.rs
index 7dadd1ffb..ccee0e5ad 100644
--- a/crates/hir_ty/src/traits.rs
+++ b/crates/hir_ty/src/traits.rs
@@ -1,6 +1,5 @@
 //! Trait solving using Chalk.
 use std::env::var;
-use std::sync::Arc;
 
 use base_db::CrateId;
 use chalk_ir::cast::Cast;
@@ -44,7 +43,7 @@ pub struct TraitEnvironment {
     // When we're using Chalk's Ty we can make this a BTreeMap since it's Ord,
     // but for now it's too annoying...
     pub(crate) traits_from_clauses: Vec<(Ty, TraitId)>,
-    pub(crate) env: chalk_ir::Environment<Interner>,
+    pub env: chalk_ir::Environment<Interner>,
 }
 
 impl TraitEnvironment {
@@ -74,13 +73,13 @@ impl Default for TraitEnvironment {
 /// Something (usually a goal), along with an environment.
 #[derive(Clone, Debug, PartialEq, Eq, Hash)]
 pub struct InEnvironment<T> {
-    pub environment: Arc<TraitEnvironment>,
-    pub value: T,
+    pub environment: chalk_ir::Environment<Interner>,
+    pub goal: T,
 }
 
 impl<T> InEnvironment<T> {
-    pub fn new(environment: Arc<TraitEnvironment>, value: T) -> InEnvironment<T> {
-        InEnvironment { environment, value }
+    pub fn new(environment: chalk_ir::Environment<Interner>, value: T) -> InEnvironment<T> {
+        InEnvironment { environment, goal: value }
     }
 }
 
@@ -126,18 +125,18 @@ pub(crate) fn trait_solve_query(
     krate: CrateId,
     goal: Canonical<InEnvironment<DomainGoal>>,
 ) -> Option<Solution> {
-    let _p = profile::span("trait_solve_query").detail(|| match &goal.value.value {
+    let _p = profile::span("trait_solve_query").detail(|| match &goal.value.goal {
         DomainGoal::Holds(WhereClause::Implemented(it)) => {
             db.trait_data(it.hir_trait_id()).name.to_string()
         }
         DomainGoal::Holds(WhereClause::AliasEq(_)) => "alias_eq".to_string(),
     });
-    log::info!("trait_solve_query({})", goal.value.value.display(db));
+    log::info!("trait_solve_query({})", goal.value.goal.display(db));
 
     if let DomainGoal::Holds(WhereClause::AliasEq(AliasEq {
         alias: AliasTy::Projection(projection_ty),
         ..
-    })) = &goal.value.value
+    })) = &goal.value.goal
     {
         if let TyKind::BoundVar(_) = &projection_ty.substitution[0].interned(&Interner) {
             // Hack: don't ask Chalk to normalize with an unknown self type, it'll say that's impossible
diff --git a/crates/hir_ty/src/traits/chalk.rs b/crates/hir_ty/src/traits/chalk.rs
index 944145603..4019fdf17 100644
--- a/crates/hir_ty/src/traits/chalk.rs
+++ b/crates/hir_ty/src/traits/chalk.rs
@@ -238,7 +238,10 @@ impl<'a> chalk_solve::RustIrDatabase<Interner> for ChalkContext<'a> {
                     });
                     let bound = OpaqueTyDatumBound {
                         bounds: make_binders(
-                            vec![impl_bound.to_chalk(self.db), proj_bound.to_chalk(self.db)],
+                            vec![
+                                wrap_in_empty_binders(impl_bound).to_chalk(self.db),
+                                wrap_in_empty_binders(proj_bound).to_chalk(self.db),
+                            ],
                             1,
                         ),
                         where_clauses: make_binders(vec![], 0),
@@ -397,7 +400,6 @@ pub(crate) fn associated_ty_data_query(
         .iter()
         .flat_map(|bound| ctx.lower_type_bound(bound, self_ty.clone(), false))
         .filter_map(|pred| generic_predicate_to_inline_bound(db, &pred, &self_ty))
-        .map(|bound| make_binders(bound.shifted_in(&Interner), 0))
         .collect();
 
     let where_clauses = convert_where_clauses(db, type_alias.into(), &bound_vars);
@@ -720,3 +722,7 @@ impl From<crate::db::InternedClosureId> for chalk_ir::ClosureId<Interner> {
         chalk_ir::ClosureId(id.as_intern_id())
     }
 }
+
+fn wrap_in_empty_binders<T: crate::TypeWalk>(value: T) -> crate::Binders<T> {
+    crate::Binders::wrap_empty(value)
+}
diff --git a/crates/hir_ty/src/traits/chalk/mapping.rs b/crates/hir_ty/src/traits/chalk/mapping.rs
index 65feb82e5..aef6b8a15 100644
--- a/crates/hir_ty/src/traits/chalk/mapping.rs
+++ b/crates/hir_ty/src/traits/chalk/mapping.rs
@@ -7,15 +7,14 @@ use chalk_ir::{cast::Cast, fold::shift::Shift, interner::HasInterner, LifetimeDa
 use chalk_solve::rust_ir;
 
 use base_db::salsa::InternKey;
-use hir_def::{AssocContainerId, GenericDefId, Lookup, TypeAliasId};
+use hir_def::{GenericDefId, TypeAliasId};
 
 use crate::{
     db::HirDatabase,
-    from_assoc_type_id,
     primitive::UintTy,
     traits::{Canonical, DomainGoal},
-    AliasTy, CallableDefId, FnPointer, InEnvironment, OpaqueTy, ProjectionTy, Scalar, Substitution,
-    TraitRef, Ty, WhereClause,
+    AliasTy, CallableDefId, FnPointer, InEnvironment, OpaqueTy, ProjectionTy,
+    QuantifiedWhereClause, Scalar, Substitution, TraitRef, Ty, TypeWalk, WhereClause,
 };
 
 use super::interner::*;
@@ -95,10 +94,10 @@ impl ToChalk for Ty {
             TyKind::Placeholder(idx) => idx.to_ty::<Interner>(&Interner),
             TyKind::BoundVar(idx) => chalk_ir::TyKind::BoundVar(idx).intern(&Interner),
             TyKind::InferenceVar(..) => panic!("uncanonicalized infer ty"),
-            TyKind::Dyn(predicates) => {
+            TyKind::Dyn(dyn_ty) => {
                 let where_clauses = chalk_ir::QuantifiedWhereClauses::from_iter(
                     &Interner,
-                    predicates.iter().cloned().map(|p| p.to_chalk(db)),
+                    dyn_ty.bounds.value.interned().iter().cloned().map(|p| p.to_chalk(db)),
                 );
                 let bounded_ty = chalk_ir::DynTy {
                     bounds: make_binders(where_clauses, 1),
@@ -144,13 +143,17 @@ impl ToChalk for Ty {
             chalk_ir::TyKind::InferenceVar(_iv, _kind) => TyKind::Unknown,
             chalk_ir::TyKind::Dyn(where_clauses) => {
                 assert_eq!(where_clauses.bounds.binders.len(&Interner), 1);
-                let predicates = where_clauses
+                let bounds = where_clauses
                     .bounds
                     .skip_binders()
                     .iter(&Interner)
-                    .map(|c| from_chalk(db, c.clone()))
-                    .collect();
-                TyKind::Dyn(predicates)
+                    .map(|c| from_chalk(db, c.clone()));
+                TyKind::Dyn(crate::DynTy {
+                    bounds: crate::Binders::new(
+                        1,
+                        crate::QuantifiedWhereClauses::from_iter(&Interner, bounds),
+                    ),
+                })
             }
 
             chalk_ir::TyKind::Adt(adt_id, subst) => TyKind::Adt(adt_id, from_chalk(db, subst)),
@@ -305,33 +308,22 @@ impl ToChalk for TypeAliasAsValue {
 }
 
 impl ToChalk for WhereClause {
-    type Chalk = chalk_ir::QuantifiedWhereClause<Interner>;
+    type Chalk = chalk_ir::WhereClause<Interner>;
 
-    fn to_chalk(self, db: &dyn HirDatabase) -> chalk_ir::QuantifiedWhereClause<Interner> {
+    fn to_chalk(self, db: &dyn HirDatabase) -> chalk_ir::WhereClause<Interner> {
         match self {
             WhereClause::Implemented(trait_ref) => {
-                let chalk_trait_ref = trait_ref.to_chalk(db);
-                let chalk_trait_ref = chalk_trait_ref.shifted_in(&Interner);
-                make_binders(chalk_ir::WhereClause::Implemented(chalk_trait_ref), 0)
+                chalk_ir::WhereClause::Implemented(trait_ref.to_chalk(db))
             }
-            WhereClause::AliasEq(alias_eq) => make_binders(
-                chalk_ir::WhereClause::AliasEq(alias_eq.to_chalk(db).shifted_in(&Interner)),
-                0,
-            ),
+            WhereClause::AliasEq(alias_eq) => chalk_ir::WhereClause::AliasEq(alias_eq.to_chalk(db)),
         }
     }
 
     fn from_chalk(
         db: &dyn HirDatabase,
-        where_clause: chalk_ir::QuantifiedWhereClause<Interner>,
+        where_clause: chalk_ir::WhereClause<Interner>,
     ) -> WhereClause {
-        // we don't produce any where clauses with binders and can't currently deal with them
-        match where_clause
-            .skip_binders()
-            .clone()
-            .shifted_out(&Interner)
-            .expect("unexpected bound vars in where clause")
-        {
+        match where_clause {
             chalk_ir::WhereClause::Implemented(tr) => WhereClause::Implemented(from_chalk(db, tr)),
             chalk_ir::WhereClause::AliasEq(alias_eq) => {
                 WhereClause::AliasEq(from_chalk(db, alias_eq))
@@ -447,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) }
     }
 }
 
@@ -486,10 +455,7 @@ where
     type Chalk = chalk_ir::InEnvironment<T::Chalk>;
 
     fn to_chalk(self, db: &dyn HirDatabase) -> chalk_ir::InEnvironment<T::Chalk> {
-        chalk_ir::InEnvironment {
-            environment: self.environment.env.clone(),
-            goal: self.value.to_chalk(db),
-        }
+        chalk_ir::InEnvironment { environment: self.environment, goal: self.goal.to_chalk(db) }
     }
 
     fn from_chalk(
@@ -500,6 +466,29 @@ where
     }
 }
 
+impl<T: ToChalk> ToChalk for crate::Binders<T>
+where
+    T::Chalk: chalk_ir::interner::HasInterner<Interner = Interner>,
+{
+    type Chalk = chalk_ir::Binders<T::Chalk>;
+
+    fn to_chalk(self, db: &dyn HirDatabase) -> chalk_ir::Binders<T::Chalk> {
+        chalk_ir::Binders::new(
+            chalk_ir::VariableKinds::from_iter(
+                &Interner,
+                std::iter::repeat(chalk_ir::VariableKind::Ty(chalk_ir::TyVariableKind::General))
+                    .take(self.num_binders),
+            ),
+            self.value.to_chalk(db),
+        )
+    }
+
+    fn from_chalk(db: &dyn HirDatabase, binders: chalk_ir::Binders<T::Chalk>) -> crate::Binders<T> {
+        let (v, b) = binders.into_value_and_skipped_binders();
+        crate::Binders::new(b.len(&Interner), from_chalk(db, v))
+    }
+}
+
 pub(super) fn make_binders<T>(value: T, num_vars: usize) -> chalk_ir::Binders<T>
 where
     T: HasInterner<Interner = Interner>,
@@ -529,14 +518,15 @@ pub(super) fn convert_where_clauses(
 
 pub(super) fn generic_predicate_to_inline_bound(
     db: &dyn HirDatabase,
-    pred: &WhereClause,
+    pred: &QuantifiedWhereClause,
     self_ty: &Ty,
-) -> Option<rust_ir::InlineBound<Interner>> {
+) -> Option<chalk_ir::Binders<rust_ir::InlineBound<Interner>>> {
     // An InlineBound is like a GenericPredicate, except the self type is left out.
     // We don't have a special type for this, but Chalk does.
-    match pred {
+    let self_ty_shifted_in = self_ty.clone().shift_bound_vars(DebruijnIndex::ONE);
+    match &pred.value {
         WhereClause::Implemented(trait_ref) => {
-            if &trait_ref.substitution[0] != self_ty {
+            if trait_ref.self_type_parameter() != &self_ty_shifted_in {
                 // we can only convert predicates back to type bounds if they
                 // have the expected self type
                 return None;
@@ -546,19 +536,13 @@ pub(super) fn generic_predicate_to_inline_bound(
                 .map(|ty| ty.clone().to_chalk(db).cast(&Interner))
                 .collect();
             let trait_bound = rust_ir::TraitBound { trait_id: trait_ref.trait_id, args_no_self };
-            Some(rust_ir::InlineBound::TraitBound(trait_bound))
+            Some(make_binders(rust_ir::InlineBound::TraitBound(trait_bound), pred.num_binders))
         }
         WhereClause::AliasEq(AliasEq { alias: AliasTy::Projection(projection_ty), ty }) => {
-            if &projection_ty.substitution[0] != self_ty {
+            if projection_ty.self_type_parameter() != &self_ty_shifted_in {
                 return None;
             }
-            let trait_ = match from_assoc_type_id(projection_ty.associated_ty_id)
-                .lookup(db.upcast())
-                .container
-            {
-                AssocContainerId::TraitId(t) => t,
-                _ => panic!("associated type not in trait"),
-            };
+            let trait_ = projection_ty.trait_(db);
             let args_no_self = projection_ty.substitution[1..]
                 .iter()
                 .map(|ty| ty.clone().to_chalk(db).cast(&Interner))
@@ -569,7 +553,7 @@ pub(super) fn generic_predicate_to_inline_bound(
                 associated_ty_id: projection_ty.associated_ty_id,
                 parameters: Vec::new(), // FIXME we don't support generic associated types yet
             };
-            Some(rust_ir::InlineBound::AliasEqBound(alias_eq_bound))
+            Some(make_binders(rust_ir::InlineBound::AliasEqBound(alias_eq_bound), pred.num_binders))
         }
         _ => None,
     }
diff --git a/crates/hir_ty/src/utils.rs b/crates/hir_ty/src/utils.rs
index 1ec1ecd43..19874e42b 100644
--- a/crates/hir_ty/src/utils.rs
+++ b/crates/hir_ty/src/utils.rs
@@ -63,7 +63,7 @@ fn direct_super_trait_refs(db: &dyn HirDatabase, trait_ref: &TraitRef) -> Vec<Tr
     db.generic_predicates_for_param(trait_self)
         .iter()
         .filter_map(|pred| {
-            pred.as_ref().filter_map(|pred| match pred {
+            pred.as_ref().filter_map(|pred| match pred.skip_binders() {
                 WhereClause::Implemented(tr) => Some(tr.clone()),
                 _ => None,
             })