4 files changed, 89 insertions, 44 deletions

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 79bbc5dab..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| {
@@ -513,10 +514,10 @@ impl<'a> InferenceContext<'a> {
                 let inner_ty = self.infer_expr_inner(*expr, &Expectation::none());
                 if let Some(box_) = self.resolve_boxed_box() {
                     let mut sb =
-                        Substitution::builder(generics(self.db.upcast(), box_.into()).len());
+                        Substitution::build_for_generics(&generics(self.db.upcast(), box_.into()));
                     sb = sb.push(inner_ty);
-                    match self.db.generic_defaults(box_.into()).as_ref() {
-                        [_, alloc_ty, ..] if !alloc_ty.value.is_unknown() => {
+                    match self.db.generic_defaults(box_.into()).get(1) {
+                        Some(alloc_ty) if !alloc_ty.value.is_unknown() && sb.remaining() > 0 => {
                             sb = sb.push(alloc_ty.value.clone());
                         }
                         _ => (),
@@ -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/pat.rs b/crates/hir_ty/src/infer/pat.rs
index befa0d69b..474363709 100644
--- a/crates/hir_ty/src/infer/pat.rs
+++ b/crates/hir_ty/src/infer/pat.rs
@@ -13,7 +13,9 @@ use hir_expand::name::Name;
 
 use super::{BindingMode, Expectation, InferenceContext};
 use crate::{
-    lower::lower_to_chalk_mutability, utils::variant_data, Interner, Substitution, Ty, TyKind,
+    lower::lower_to_chalk_mutability,
+    utils::{generics, variant_data},
+    Interner, Substitution, Ty, TyKind,
 };
 
 impl<'a> InferenceContext<'a> {
@@ -38,7 +40,7 @@ impl<'a> InferenceContext<'a> {
         let field_tys = def.map(|it| self.db.field_types(it)).unwrap_or_default();
         let (pre, post) = match ellipsis {
             Some(idx) => subpats.split_at(idx),
-            None => (&subpats[..], &[][..]),
+            None => (subpats, &[][..]),
         };
         let post_idx_offset = field_tys.iter().count() - post.len();
 
@@ -233,13 +235,31 @@ impl<'a> InferenceContext<'a> {
             Pat::Lit(expr) => self.infer_expr(*expr, &Expectation::has_type(expected.clone())),
             Pat::Box { inner } => match self.resolve_boxed_box() {
                 Some(box_adt) => {
-                    let inner_expected = match expected.as_adt() {
-                        Some((adt, substs)) if adt == box_adt => substs.as_single().clone(),
-                        _ => self.result.standard_types.unknown.clone(),
+                    let (inner_ty, alloc_ty) = match expected.as_adt() {
+                        Some((adt, subst)) if adt == box_adt => {
+                            (subst[0].clone(), subst.get(1).cloned())
+                        }
+                        _ => (self.result.standard_types.unknown.clone(), None),
                     };
 
-                    let inner_ty = self.infer_pat(*inner, &inner_expected, default_bm);
-                    Ty::adt_ty(box_adt, Substitution::single(inner_ty))
+                    let inner_ty = self.infer_pat(*inner, &inner_ty, default_bm);
+                    let mut sb = Substitution::build_for_generics(&generics(
+                        self.db.upcast(),
+                        box_adt.into(),
+                    ));
+                    sb = sb.push(inner_ty);
+                    if sb.remaining() == 1 {
+                        sb = sb.push(match alloc_ty {
+                            Some(alloc_ty) if !alloc_ty.is_unknown() => alloc_ty,
+                            _ => match self.db.generic_defaults(box_adt.into()).get(1) {
+                                Some(alloc_ty) if !alloc_ty.value.is_unknown() => {
+                                    alloc_ty.value.clone()
+                                }
+                                _ => self.table.new_type_var(),
+                            },
+                        });
+                    }
+                    Ty::adt_ty(box_adt, sb.build())
                 }
                 None => self.err_ty(),
             },
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;
                     }
                 }