11 files changed, 108 insertions, 112 deletions

diff --git a/crates/hir/src/lib.rs b/crates/hir/src/lib.rs
index 003821981..db4ebada4 100644
--- a/crates/hir/src/lib.rs
+++ b/crates/hir/src/lib.rs
@@ -55,6 +55,7 @@ use hir_ty::{
     autoderef, could_unify,
     method_resolution::{self, TyFingerprint},
     primitive::UintTy,
+    subst_prefix,
     traits::FnTrait,
     AliasEq, AliasTy, BoundVar, CallableDefId, CallableSig, Canonical, CanonicalVarKinds, Cast,
     DebruijnIndex, InEnvironment, Interner, QuantifiedWhereClause, Scalar, Solution,
@@ -1503,7 +1504,7 @@ impl TypeParam {
         let krate = self.id.parent.module(db.upcast()).krate();
         let ty = params.get(local_idx)?.clone();
         let subst = TyBuilder::type_params_subst(db, self.id.parent);
-        let ty = ty.substitute(&Interner, &subst.prefix(local_idx));
+        let ty = ty.substitute(&Interner, &subst_prefix(&subst, local_idx));
         Some(Type::new_with_resolver_inner(db, krate, &resolver, ty))
     }
 }
diff --git a/crates/hir_ty/src/autoderef.rs b/crates/hir_ty/src/autoderef.rs
index 7ca4af80e..c5890e24d 100644
--- a/crates/hir_ty/src/autoderef.rs
+++ b/crates/hir_ty/src/autoderef.rs
@@ -13,7 +13,7 @@ use log::{info, warn};
 
 use crate::{
     db::HirDatabase, AliasEq, AliasTy, BoundVar, Canonical, CanonicalVarKinds, DebruijnIndex,
-    InEnvironment, Interner, Solution, Ty, TyBuilder, TyKind,
+    InEnvironment, Interner, ProjectionTyExt, Solution, Ty, TyBuilder, TyKind,
 };
 
 const AUTODEREF_RECURSION_LIMIT: usize = 10;
diff --git a/crates/hir_ty/src/chalk_ext.rs b/crates/hir_ty/src/chalk_ext.rs
index b7463366b..0f4cb43e9 100644
--- a/crates/hir_ty/src/chalk_ext.rs
+++ b/crates/hir_ty/src/chalk_ext.rs
@@ -1,6 +1,11 @@
 //! Various extensions traits for Chalk types.
 
-use crate::{Interner, Ty, TyKind};
+use hir_def::{AssocContainerId, Lookup, TraitId};
+
+use crate::{
+    db::HirDatabase, from_assoc_type_id, to_chalk_trait_id, Interner, ProjectionTy, TraitRef, Ty,
+    TyKind,
+};
 
 pub trait TyExt {
     fn is_unit(&self) -> bool;
@@ -11,3 +16,24 @@ impl TyExt for Ty {
         matches!(self.kind(&Interner), TyKind::Tuple(0, _))
     }
 }
+
+pub trait ProjectionTyExt {
+    fn trait_ref(&self, db: &dyn HirDatabase) -> TraitRef;
+    fn trait_(&self, db: &dyn HirDatabase) -> TraitId;
+}
+
+impl ProjectionTyExt for ProjectionTy {
+    fn trait_ref(&self, db: &dyn HirDatabase) -> TraitRef {
+        TraitRef {
+            trait_id: to_chalk_trait_id(self.trait_(db)),
+            substitution: self.substitution.clone(),
+        }
+    }
+
+    fn trait_(&self, db: &dyn HirDatabase) -> TraitId {
+        match from_assoc_type_id(self.associated_ty_id).lookup(db.upcast()).container {
+            AssocContainerId::TraitId(it) => it,
+            _ => panic!("projection ty without parent trait"),
+        }
+    }
+}
diff --git a/crates/hir_ty/src/display.rs b/crates/hir_ty/src/display.rs
index 01c7ef91f..4ef8024d0 100644
--- a/crates/hir_ty/src/display.rs
+++ b/crates/hir_ty/src/display.rs
@@ -19,10 +19,11 @@ use hir_expand::name::Name;
 
 use crate::{
     db::HirDatabase, from_assoc_type_id, from_foreign_def_id, from_placeholder_idx,
-    lt_from_placeholder_idx, primitive, to_assoc_type_id, traits::chalk::from_chalk,
+    lt_from_placeholder_idx, primitive, subst_prefix, to_assoc_type_id, traits::chalk::from_chalk,
     utils::generics, AdtId, AliasEq, AliasTy, CallableDefId, CallableSig, DomainGoal, GenericArg,
     ImplTraitId, Interner, Lifetime, LifetimeData, LifetimeOutlives, Mutability, OpaqueTy,
-    ProjectionTy, QuantifiedWhereClause, Scalar, TraitRef, Ty, TyExt, TyKind, WhereClause,
+    ProjectionTy, ProjectionTyExt, QuantifiedWhereClause, Scalar, TraitRef, Ty, TyExt, TyKind,
+    WhereClause,
 };
 
 pub struct HirFormatter<'a> {
@@ -483,9 +484,11 @@ impl HirDisplay for Ty {
                                             default_from = i + 1;
                                         }
                                         (_, Some(default_parameter)) => {
-                                            let actual_default = default_parameter
-                                                .clone()
-                                                .substitute(&Interner, &parameters.prefix(i));
+                                            let actual_default =
+                                                default_parameter.clone().substitute(
+                                                    &Interner,
+                                                    &subst_prefix(parameters, i),
+                                                );
                                             if parameter.assert_ty_ref(&Interner) != &actual_default
                                             {
                                                 default_from = i + 1;
diff --git a/crates/hir_ty/src/infer/expr.rs b/crates/hir_ty/src/infer/expr.rs
index 6966d26e7..185a2dfc3 100644
--- a/crates/hir_ty/src/infer/expr.rs
+++ b/crates/hir_ty/src/infer/expr.rs
@@ -22,8 +22,8 @@ use crate::{
     to_chalk_trait_id,
     traits::{chalk::from_chalk, FnTrait},
     utils::{generics, variant_data, Generics},
-    AdtId, Binders, CallableDefId, FnPointer, FnSig, InEnvironment, Interner, Rawness, Scalar,
-    Substitution, TraitRef, Ty, TyBuilder, TyKind,
+    AdtId, Binders, CallableDefId, FnPointer, FnSig, InEnvironment, Interner, ProjectionTyExt,
+    Rawness, Scalar, Substitution, TraitRef, Ty, TyBuilder, TyKind,
 };
 
 use super::{
@@ -180,7 +180,8 @@ impl<'a> InferenceContext<'a> {
                 let inner_ty = self.infer_expr(*body, &Expectation::none());
                 let impl_trait_id = crate::ImplTraitId::AsyncBlockTypeImplTrait(self.owner, *body);
                 let opaque_ty_id = self.db.intern_impl_trait_id(impl_trait_id).into();
-                TyKind::OpaqueType(opaque_ty_id, Substitution::single(inner_ty)).intern(&Interner)
+                TyKind::OpaqueType(opaque_ty_id, Substitution::from1(&Interner, inner_ty))
+                    .intern(&Interner)
             }
             Expr::Loop { body, label } => {
                 self.breakables.push(BreakableContext {
@@ -266,7 +267,8 @@ impl<'a> InferenceContext<'a> {
                 .intern(&Interner);
                 let closure_id = self.db.intern_closure((self.owner, tgt_expr)).into();
                 let closure_ty =
-                    TyKind::Closure(closure_id, Substitution::single(sig_ty)).intern(&Interner);
+                    TyKind::Closure(closure_id, Substitution::from1(&Interner, sig_ty))
+                        .intern(&Interner);
 
                 // Eagerly try to relate the closure type with the expected
                 // type, otherwise we often won't have enough information to
@@ -962,8 +964,10 @@ impl<'a> InferenceContext<'a> {
                     if let AssocContainerId::TraitId(trait_) = f.lookup(self.db.upcast()).container
                     {
                         // construct a TraitRef
-                        let substs =
-                            parameters.prefix(generics(self.db.upcast(), trait_.into()).len());
+                        let substs = crate::subst_prefix(
+                            &*parameters,
+                            generics(self.db.upcast(), trait_.into()).len(),
+                        );
                         self.push_obligation(
                             TraitRef { trait_id: to_chalk_trait_id(trait_), substitution: substs }
                                 .cast(&Interner),
diff --git a/crates/hir_ty/src/lib.rs b/crates/hir_ty/src/lib.rs
index a3addc8e9..f74b22b58 100644
--- a/crates/hir_ty/src/lib.rs
+++ b/crates/hir_ty/src/lib.rs
@@ -31,7 +31,6 @@ mod test_db;
 use std::sync::Arc;
 
 use itertools::Itertools;
-use smallvec::SmallVec;
 
 use base_db::salsa;
 use hir_def::{
@@ -43,13 +42,13 @@ use crate::{db::HirDatabase, display::HirDisplay, utils::generics};
 
 pub use autoderef::autoderef;
 pub use builder::TyBuilder;
-pub use chalk_ext::TyExt;
+pub use chalk_ext::{ProjectionTyExt, TyExt};
 pub use infer::{could_unify, InferenceResult, InferenceVar};
 pub use lower::{
     associated_type_shorthand_candidates, callable_item_sig, CallableDefId, ImplTraitLoweringMode,
     TyDefId, TyLoweringContext, ValueTyDefId,
 };
-pub use traits::TraitEnvironment;
+pub use traits::{chalk::Interner, TraitEnvironment};
 pub use types::*;
 pub use walk::TypeWalk;
 
@@ -57,8 +56,6 @@ pub use chalk_ir::{
     cast::Cast, AdtId, BoundVar, DebruijnIndex, Mutability, Safety, Scalar, TyVariableKind,
 };
 
-pub use crate::traits::chalk::Interner;
-
 pub type ForeignDefId = chalk_ir::ForeignDefId<Interner>;
 pub type AssocTypeId = chalk_ir::AssocTypeId<Interner>;
 pub type FnDefId = chalk_ir::FnDefId<Interner>;
@@ -76,46 +73,11 @@ pub type LifetimeOutlives = chalk_ir::LifetimeOutlives<Interner>;
 
 pub type ChalkTraitId = chalk_ir::TraitId<Interner>;
 
-impl ProjectionTy {
-    pub fn trait_ref(&self, db: &dyn HirDatabase) -> TraitRef {
-        TraitRef {
-            trait_id: to_chalk_trait_id(self.trait_(db)),
-            substitution: self.substitution.clone(),
-        }
-    }
-
-    pub fn self_type_parameter(&self, interner: &Interner) -> &Ty {
-        &self.substitution.interned()[0].assert_ty_ref(interner)
-    }
-
-    fn trait_(&self, db: &dyn HirDatabase) -> TraitId {
-        match from_assoc_type_id(self.associated_ty_id).lookup(db.upcast()).container {
-            AssocContainerId::TraitId(it) => it,
-            _ => panic!("projection ty without parent trait"),
-        }
-    }
-}
-
 pub type FnSig = chalk_ir::FnSig<Interner>;
 
-impl Substitution {
-    pub fn single(ty: Ty) -> Substitution {
-        Substitution::intern({
-            let mut v = SmallVec::new();
-            v.push(ty.cast(&Interner));
-            v
-        })
-    }
-
-    pub fn prefix(&self, n: usize) -> Substitution {
-        Substitution::intern(self.interned()[..std::cmp::min(self.len(&Interner), n)].into())
-    }
-
-    pub fn suffix(&self, n: usize) -> Substitution {
-        Substitution::intern(
-            self.interned()[self.len(&Interner) - std::cmp::min(self.len(&Interner), n)..].into(),
-        )
-    }
+// FIXME: get rid of this
+pub fn subst_prefix(s: &Substitution, n: usize) -> Substitution {
+    Substitution::intern(s.interned()[..std::cmp::min(s.len(&Interner), n)].into())
 }
 
 /// Return an index of a parameter in the generic type parameter list by it's id.
@@ -123,22 +85,11 @@ pub fn param_idx(db: &dyn HirDatabase, id: TypeParamId) -> Option<usize> {
     generics(db.upcast(), id.parent).param_idx(id)
 }
 
-impl<T> Binders<T> {
-    pub fn wrap_empty(value: T) -> Self
-    where
-        T: TypeWalk,
-    {
-        Binders::empty(&Interner, value.shifted_in_from(DebruijnIndex::ONE))
-    }
-}
-
-impl<T: TypeWalk> Binders<T> {
-    /// Substitutes all variables.
-    pub fn substitute(self, interner: &Interner, subst: &Substitution) -> T {
-        let (value, binders) = self.into_value_and_skipped_binders();
-        assert_eq!(subst.len(interner), binders.len(interner));
-        value.subst_bound_vars(subst)
-    }
+pub fn wrap_empty_binders<T>(value: T) -> Binders<T>
+where
+    T: TypeWalk,
+{
+    Binders::empty(&Interner, value.shifted_in_from(DebruijnIndex::ONE))
 }
 
 pub fn make_only_type_binders<T>(num_vars: usize, value: T) -> Binders<T> {
@@ -153,31 +104,11 @@ pub fn make_only_type_binders<T>(num_vars: usize, value: T) -> Binders<T> {
 }
 
 impl TraitRef {
-    pub fn self_type_parameter(&self, interner: &Interner) -> &Ty {
-        &self.substitution.at(interner, 0).assert_ty_ref(interner)
-    }
-
     pub fn hir_trait_id(&self) -> TraitId {
         from_chalk_trait_id(self.trait_id)
     }
 }
 
-impl WhereClause {
-    pub fn is_implemented(&self) -> bool {
-        matches!(self, WhereClause::Implemented(_))
-    }
-
-    pub fn trait_ref(&self, db: &dyn HirDatabase) -> Option<TraitRef> {
-        match self {
-            WhereClause::Implemented(tr) => Some(tr.clone()),
-            WhereClause::AliasEq(AliasEq { alias: AliasTy::Projection(proj), .. }) => {
-                Some(proj.trait_ref(db))
-            }
-            WhereClause::AliasEq(_) => None,
-        }
-    }
-}
-
 impl<T> Canonical<T> {
     pub fn new(value: T, kinds: impl IntoIterator<Item = TyVariableKind>) -> Self {
         let kinds = kinds.into_iter().map(|tk| {
diff --git a/crates/hir_ty/src/lower.rs b/crates/hir_ty/src/lower.rs
index 48c26f471..6cef8095f 100644
--- a/crates/hir_ty/src/lower.rs
+++ b/crates/hir_ty/src/lower.rs
@@ -384,7 +384,9 @@ impl<'a> TyLoweringContext<'a> {
                             1,
                             QuantifiedWhereClauses::from_iter(
                                 &Interner,
-                                Some(Binders::wrap_empty(WhereClause::Implemented(trait_ref))),
+                                Some(crate::wrap_empty_binders(WhereClause::Implemented(
+                                    trait_ref,
+                                ))),
                             ),
                         ),
                     };
@@ -720,7 +722,7 @@ impl<'a> TyLoweringContext<'a> {
         let trait_ref = match bound {
             TypeBound::Path(path) => {
                 bindings = self.lower_trait_ref_from_path(path, Some(self_ty));
-                bindings.clone().map(WhereClause::Implemented).map(|b| Binders::wrap_empty(b))
+                bindings.clone().map(WhereClause::Implemented).map(|b| crate::wrap_empty_binders(b))
             }
             TypeBound::Lifetime(_) => None,
             TypeBound::Error => None,
@@ -767,7 +769,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(Binders::wrap_empty(WhereClause::AliasEq(alias_eq)));
+                    preds.push(crate::wrap_empty_binders(WhereClause::AliasEq(alias_eq)));
                 }
                 for bound in &binding.bounds {
                     preds.extend(self.lower_type_bound(
diff --git a/crates/hir_ty/src/method_resolution.rs b/crates/hir_ty/src/method_resolution.rs
index 19a1fa793..d6de844a8 100644
--- a/crates/hir_ty/src/method_resolution.rs
+++ b/crates/hir_ty/src/method_resolution.rs
@@ -709,8 +709,9 @@ pub(crate) fn inherent_impl_substs(
 ) -> Option<Substitution> {
     // 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 self_ty_vars = self_ty.binders.len(&Interner);
     let vars = TyBuilder::subst_for_def(db, impl_id)
-        .fill_with_bound_vars(DebruijnIndex::INNERMOST, self_ty.binders.len(&Interner))
+        .fill_with_bound_vars(DebruijnIndex::INNERMOST, self_ty_vars)
         .build();
     let self_ty_with_vars = db.impl_self_ty(impl_id).substitute(&Interner, &vars);
     let mut kinds = self_ty.binders.interned().to_vec();
@@ -725,14 +726,15 @@ pub(crate) fn inherent_impl_substs(
         binders: CanonicalVarKinds::from_iter(&Interner, kinds),
         value: (self_ty_with_vars, self_ty.value.clone()),
     };
-    let substs = super::infer::unify(&tys);
+    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(&Interner)), self_ty.binders.len(&Interner)))
+    let suffix =
+        Substitution::from_iter(&Interner, substs.iter(&Interner).cloned().skip(self_ty_vars));
+    Some(fallback_bound_vars(suffix, self_ty_vars))
 }
 
 /// This replaces any 'free' Bound vars in `s` (i.e. those with indices past
diff --git a/crates/hir_ty/src/traits/chalk.rs b/crates/hir_ty/src/traits/chalk.rs
index dff87ef70..5a8b5cd86 100644
--- a/crates/hir_ty/src/traits/chalk.rs
+++ b/crates/hir_ty/src/traits/chalk.rs
@@ -220,7 +220,8 @@ impl<'a> chalk_solve::RustIrDatabase<Interner> for ChalkContext<'a> {
                     let impl_bound = WhereClause::Implemented(TraitRef {
                         trait_id: to_chalk_trait_id(future_trait),
                         // Self type as the first parameter.
-                        substitution: Substitution::single(
+                        substitution: Substitution::from1(
+                            &Interner,
                             TyKind::BoundVar(BoundVar {
                                 debruijn: DebruijnIndex::INNERMOST,
                                 index: 0,
@@ -232,7 +233,8 @@ impl<'a> chalk_solve::RustIrDatabase<Interner> for ChalkContext<'a> {
                         alias: AliasTy::Projection(ProjectionTy {
                             associated_ty_id: to_assoc_type_id(future_output),
                             // Self type as the first parameter.
-                            substitution: Substitution::single(
+                            substitution: Substitution::from1(
+                                &Interner,
                                 TyKind::BoundVar(BoundVar::new(DebruijnIndex::INNERMOST, 0))
                                     .intern(&Interner),
                             ),
@@ -244,8 +246,8 @@ impl<'a> chalk_solve::RustIrDatabase<Interner> for ChalkContext<'a> {
                     let bound = OpaqueTyDatumBound {
                         bounds: make_binders(
                             vec![
-                                wrap_in_empty_binders(impl_bound).to_chalk(self.db),
-                                wrap_in_empty_binders(proj_bound).to_chalk(self.db),
+                                crate::wrap_empty_binders(impl_bound).to_chalk(self.db),
+                                crate::wrap_empty_binders(proj_bound).to_chalk(self.db),
                             ],
                             1,
                         ),
@@ -721,7 +723,3 @@ 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 c3b148cab..9f10b889f 100644
--- a/crates/hir_ty/src/traits/chalk/mapping.rs
+++ b/crates/hir_ty/src/traits/chalk/mapping.rs
@@ -10,9 +10,9 @@ use base_db::salsa::InternKey;
 use hir_def::{GenericDefId, TypeAliasId};
 
 use crate::{
-    db::HirDatabase, primitive::UintTy, AliasTy, CallableDefId, Canonical, DomainGoal, FnPointer,
-    GenericArg, InEnvironment, OpaqueTy, ProjectionTy, QuantifiedWhereClause, Scalar, Substitution,
-    TraitRef, Ty, TypeWalk, WhereClause,
+    chalk_ext::ProjectionTyExt, db::HirDatabase, primitive::UintTy, AliasTy, CallableDefId,
+    Canonical, DomainGoal, FnPointer, GenericArg, InEnvironment, OpaqueTy, ProjectionTy,
+    QuantifiedWhereClause, Scalar, Substitution, TraitRef, Ty, TypeWalk, WhereClause,
 };
 
 use super::interner::*;
diff --git a/crates/hir_ty/src/types.rs b/crates/hir_ty/src/types.rs
index dc64e6e2b..4a626d5e7 100644
--- a/crates/hir_ty/src/types.rs
+++ b/crates/hir_ty/src/types.rs
@@ -4,7 +4,7 @@
 use std::sync::Arc;
 
 use chalk_ir::{
-    cast::{CastTo, Caster},
+    cast::{Cast, CastTo, Caster},
     BoundVar, Mutability, Scalar, TyVariableKind,
 };
 use smallvec::SmallVec;
@@ -29,6 +29,12 @@ pub struct ProjectionTy {
     pub substitution: Substitution,
 }
 
+impl ProjectionTy {
+    pub fn self_type_parameter(&self, interner: &Interner) -> &Ty {
+        &self.substitution.interned()[0].assert_ty_ref(interner)
+    }
+}
+
 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
 pub struct DynTy {
     /// The unknown self type.
@@ -272,6 +278,14 @@ impl Substitution {
         self.0.iter()
     }
 
+    pub fn from1(_interner: &Interner, ty: Ty) -> Substitution {
+        Substitution::intern({
+            let mut v = SmallVec::new();
+            v.push(ty.cast(&Interner));
+            v
+        })
+    }
+
     pub fn from_iter(
         interner: &Interner,
         elements: impl IntoIterator<Item = impl CastTo<GenericArg>>,
@@ -346,6 +360,15 @@ impl<T: Clone> Binders<&T> {
     }
 }
 
+impl<T: TypeWalk> Binders<T> {
+    /// Substitutes all variables.
+    pub fn substitute(self, interner: &Interner, subst: &Substitution) -> T {
+        let (value, binders) = self.into_value_and_skipped_binders();
+        assert_eq!(subst.len(interner), binders.len(interner));
+        value.subst_bound_vars(subst)
+    }
+}
+
 impl<T: std::fmt::Debug> std::fmt::Debug for Binders<T> {
     fn fmt(&self, fmt: &mut std::fmt::Formatter<'_>) -> Result<(), std::fmt::Error> {
         let Binders { ref binders, ref value } = *self;
@@ -361,6 +384,12 @@ pub struct TraitRef {
     pub substitution: Substitution,
 }
 
+impl TraitRef {
+    pub fn self_type_parameter(&self, interner: &Interner) -> &Ty {
+        &self.substitution.at(interner, 0).assert_ty_ref(interner)
+    }
+}
+
 /// Like `generics::WherePredicate`, but with resolved types: A condition on the
 /// parameters of a generic item.
 #[derive(Debug, Clone, PartialEq, Eq, Hash)]