Lower impl trait to variables, move away from using placeholders where they don't belong

9 files changed, 220 insertions, 188 deletions

diff --git a/crates/ra_hir_ty/src/db.rs b/crates/ra_hir_ty/src/db.rs
index eb521c7a0..fea122a8b 100644
--- a/crates/ra_hir_ty/src/db.rs
+++ b/crates/ra_hir_ty/src/db.rs
@@ -12,8 +12,8 @@ use ra_prof::profile;
 use crate::{
     method_resolution::CrateImplBlocks,
     traits::{chalk, AssocTyValue, Impl},
-    CallableDef, FnSig, GenericPredicate, InferenceResult, Substs, TraitRef, Ty, TyDefId, TypeCtor,
-    ValueTyDefId,
+    CallableDef, PolyFnSig, GenericPredicate, InferenceResult, Substs, TraitRef, Ty, TyDefId, TypeCtor,
+    ValueTyDefId, Binders,
 };
 
 #[salsa::query_group(HirDatabaseStorage)]
@@ -27,14 +27,14 @@ pub trait HirDatabase: DefDatabase {
 
     #[salsa::invoke(crate::lower::ty_query)]
     #[salsa::cycle(crate::lower::ty_recover)]
-    fn ty(&self, def: TyDefId) -> Ty;
+    fn ty(&self, def: TyDefId) -> Binders<Ty>;
 
     #[salsa::invoke(crate::lower::value_ty_query)]
-    fn value_ty(&self, def: ValueTyDefId) -> Ty;
+    fn value_ty(&self, def: ValueTyDefId) -> Binders<Ty>;
 
     #[salsa::invoke(crate::lower::impl_self_ty_query)]
     #[salsa::cycle(crate::lower::impl_self_ty_recover)]
-    fn impl_self_ty(&self, def: ImplId) -> Ty;
+    fn impl_self_ty(&self, def: ImplId) -> Binders<Ty>;
 
     #[salsa::invoke(crate::lower::impl_trait_query)]
     fn impl_trait(&self, def: ImplId) -> Option<TraitRef>;
@@ -43,7 +43,7 @@ pub trait HirDatabase: DefDatabase {
     fn field_types(&self, var: VariantId) -> Arc<ArenaMap<LocalStructFieldId, Ty>>;
 
     #[salsa::invoke(crate::callable_item_sig)]
-    fn callable_item_signature(&self, def: CallableDef) -> FnSig;
+    fn callable_item_signature(&self, def: CallableDef) -> PolyFnSig;
 
     #[salsa::invoke(crate::lower::generic_predicates_for_param_query)]
     #[salsa::cycle(crate::lower::generic_predicates_for_param_recover)]
diff --git a/crates/ra_hir_ty/src/infer.rs b/crates/ra_hir_ty/src/infer.rs
index b4a3e1675..f7ef09f0e 100644
--- a/crates/ra_hir_ty/src/infer.rs
+++ b/crates/ra_hir_ty/src/infer.rs
@@ -279,11 +279,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
         impl_trait_mode: ImplTraitLoweringMode,
     ) -> Ty {
         // FIXME use right resolver for block
-        let ctx = crate::lower::TyLoweringContext {
-            db: self.db,
-            resolver: &self.resolver,
-            impl_trait_mode,
-        };
+        let ctx = crate::lower::TyLoweringContext::new(self.db, &self.resolver).with_impl_trait_mode(impl_trait_mode);
         let ty = Ty::from_hir(&ctx, type_ref);
         let ty = self.insert_type_vars(ty);
         self.normalize_associated_types_in(ty)
@@ -457,24 +453,20 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
             None => return (Ty::Unknown, None),
         };
         let resolver = &self.resolver;
-        let ctx = crate::lower::TyLoweringContext {
-            db: self.db,
-            resolver: &self.resolver,
-            impl_trait_mode: ImplTraitLoweringMode::Disallowed,
-        };
+        let ctx = crate::lower::TyLoweringContext::new(self.db, &self.resolver);
         // FIXME: this should resolve assoc items as well, see this example:
         // https://play.rust-lang.org/?gist=087992e9e22495446c01c0d4e2d69521
         match resolver.resolve_path_in_type_ns_fully(self.db, path.mod_path()) {
             Some(TypeNs::AdtId(AdtId::StructId(strukt))) => {
                 let substs = Ty::substs_from_path(&ctx, path, strukt.into());
                 let ty = self.db.ty(strukt.into());
-                let ty = self.insert_type_vars(ty.apply_substs(substs));
+                let ty = self.insert_type_vars(ty.subst(&substs));
                 (ty, Some(strukt.into()))
             }
             Some(TypeNs::EnumVariantId(var)) => {
                 let substs = Ty::substs_from_path(&ctx, path, var.into());
                 let ty = self.db.ty(var.parent.into());
-                let ty = self.insert_type_vars(ty.apply_substs(substs));
+                let ty = self.insert_type_vars(ty.subst(&substs));
                 (ty, Some(var.into()))
             }
             Some(_) | None => (Ty::Unknown, None),
@@ -492,7 +484,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
 
             self.infer_pat(*pat, &ty, BindingMode::default());
         }
-        let return_ty = self.make_ty_with_mode(&data.ret_type, ImplTraitLoweringMode::Placeholder);
+        let return_ty = self.make_ty_with_mode(&data.ret_type, ImplTraitLoweringMode::Variable);
         self.return_ty = self.insert_vars_for_impl_trait(return_ty);
     }
 
diff --git a/crates/ra_hir_ty/src/infer/expr.rs b/crates/ra_hir_ty/src/infer/expr.rs
index 97cb20cea..e1fdb356d 100644
--- a/crates/ra_hir_ty/src/infer/expr.rs
+++ b/crates/ra_hir_ty/src/infer/expr.rs
@@ -20,7 +20,7 @@ use crate::{
     traits::InEnvironment,
     utils::{generics, variant_data, Generics},
     ApplicationTy, CallableDef, InferTy, IntTy, Mutability, Obligation, Substs, TraitRef, Ty,
-    TypeCtor, TypeWalk, Uncertain,
+    TypeCtor, TypeWalk, Uncertain, Binders,
 };
 
 use super::{BindingMode, Expectation, InferenceContext, InferenceDiagnostic, TypeMismatch};
@@ -588,10 +588,10 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
                 self.write_method_resolution(tgt_expr, func);
                 (ty, self.db.value_ty(func.into()), Some(generics(self.db, func.into())))
             }
-            None => (receiver_ty, Ty::Unknown, None),
+            None => (receiver_ty, Binders::new(0, Ty::Unknown), None),
         };
         let substs = self.substs_for_method_call(def_generics, generic_args, &derefed_receiver_ty);
-        let method_ty = method_ty.apply_substs(substs);
+        let method_ty = method_ty.subst(&substs);
         let method_ty = self.insert_type_vars(method_ty);
         self.register_obligations_for_call(&method_ty);
         let (expected_receiver_ty, param_tys, ret_ty) = match method_ty.callable_sig(self.db) {
diff --git a/crates/ra_hir_ty/src/infer/path.rs b/crates/ra_hir_ty/src/infer/path.rs
index 02fc99288..39aa346eb 100644
--- a/crates/ra_hir_ty/src/infer/path.rs
+++ b/crates/ra_hir_ty/src/infer/path.rs
@@ -10,8 +10,8 @@ use hir_def::{
 use hir_expand::name::Name;
 
 use crate::{
-    db::HirDatabase, lower::ImplTraitLoweringMode, method_resolution, Substs, Ty, TypeWalk,
-    ValueTyDefId,
+    db::HirDatabase, method_resolution, Substs, Ty,
+    ValueTyDefId
 };
 
 use super::{ExprOrPatId, InferenceContext, TraitRef};
@@ -42,11 +42,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
             }
             let ty = self.make_ty(type_ref);
             let remaining_segments_for_ty = path.segments().take(path.segments().len() - 1);
-            let ctx = crate::lower::TyLoweringContext {
-                db: self.db,
-                resolver: &resolver,
-                impl_trait_mode: ImplTraitLoweringMode::Disallowed,
-            };
+            let ctx = crate::lower::TyLoweringContext::new(self.db, &resolver);
             let ty = Ty::from_type_relative_path(&ctx, ty, remaining_segments_for_ty);
             self.resolve_ty_assoc_item(
                 ty,
@@ -77,17 +73,16 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
             ValueNs::EnumVariantId(it) => it.into(),
         };
 
-        let mut ty = self.db.value_ty(typable);
-        if let Some(self_subst) = self_subst {
-            ty = ty.subst(&self_subst);
-        }
-        let ctx = crate::lower::TyLoweringContext {
-            db: self.db,
-            resolver: &self.resolver,
-            impl_trait_mode: ImplTraitLoweringMode::Disallowed,
-        };
+        let ty = self.db.value_ty(typable);
+        // self_subst is just for the parent
+        let parent_substs = self_subst.unwrap_or_else(Substs::empty);
+        let ctx = crate::lower::TyLoweringContext::new(self.db, &self.resolver);
         let substs = Ty::substs_from_path(&ctx, path, typable);
-        let ty = ty.subst(&substs);
+        let full_substs = Substs::builder(substs.len())
+            .use_parent_substs(&parent_substs)
+            .fill(substs.0[parent_substs.len()..].iter().cloned())
+            .build();
+        let ty = ty.subst(&full_substs);
         Some(ty)
     }
 
@@ -111,11 +106,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
             (TypeNs::TraitId(trait_), true) => {
                 let segment =
                     remaining_segments.last().expect("there should be at least one segment here");
-                let ctx = crate::lower::TyLoweringContext {
-                    db: self.db,
-                    resolver: &self.resolver,
-                    impl_trait_mode: ImplTraitLoweringMode::Disallowed,
-                };
+                let ctx = crate::lower::TyLoweringContext::new(self.db, &self.resolver);
                 let trait_ref =
                     TraitRef::from_resolved_path(&ctx, trait_.into(), resolved_segment, None);
                 self.resolve_trait_assoc_item(trait_ref, segment, id)
@@ -127,11 +118,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
                 // as Iterator>::Item::default`)
                 let remaining_segments_for_ty =
                     remaining_segments.take(remaining_segments.len() - 1);
-                let ctx = crate::lower::TyLoweringContext {
-                    db: self.db,
-                    resolver: &self.resolver,
-                    impl_trait_mode: ImplTraitLoweringMode::Disallowed,
-                };
+                let ctx = crate::lower::TyLoweringContext::new(self.db, &self.resolver);
                 let ty = Ty::from_partly_resolved_hir_path(
                     &ctx,
                     def,
@@ -235,12 +222,8 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
                             .fill(iter::repeat_with(|| self.table.new_type_var()))
                             .build();
                         let impl_self_ty = self.db.impl_self_ty(impl_id).subst(&impl_substs);
-                        let substs = Substs::build_for_def(self.db, item)
-                            .use_parent_substs(&impl_substs)
-                            .fill_with_params()
-                            .build();
                         self.unify(&impl_self_ty, &ty);
-                        Some(substs)
+                        Some(impl_substs)
                     }
                     AssocContainerId::TraitId(trait_) => {
                         // we're picking this method
@@ -248,15 +231,11 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
                             .push(ty.clone())
                             .fill(std::iter::repeat_with(|| self.table.new_type_var()))
                             .build();
-                        let substs = Substs::build_for_def(self.db, item)
-                            .use_parent_substs(&trait_substs)
-                            .fill_with_params()
-                            .build();
                         self.obligations.push(super::Obligation::Trait(TraitRef {
                             trait_,
-                            substs: trait_substs,
+                            substs: trait_substs.clone(),
                         }));
-                        Some(substs)
+                        Some(trait_substs)
                     }
                     AssocContainerId::ContainerId(_) => None,
                 };
diff --git a/crates/ra_hir_ty/src/lib.rs b/crates/ra_hir_ty/src/lib.rs
index cb7a60352..79084bb3e 100644
--- a/crates/ra_hir_ty/src/lib.rs
+++ b/crates/ra_hir_ty/src/lib.rs
@@ -453,6 +453,30 @@ impl Deref for Substs {
     }
 }
 
+#[derive(Copy, Clone, PartialEq, Eq, Debug)]
+pub struct Binders<T> {
+    pub num_binders: usize,
+    pub value: T,
+}
+
+impl<T> Binders<T> {
+    pub fn new(num_binders: usize, value: T) -> Self { Self { num_binders, value } }
+}
+
+impl<T: TypeWalk> Binders<T> {
+    /// Substitutes all variables.
+    pub fn subst(self, subst: &Substs) -> T {
+        assert_eq!(subst.len(), self.num_binders);
+        self.value.subst_bound_vars(subst)
+    }
+
+    /// Substitutes just a prefix of the variables (shifting the rest).
+    pub fn subst_prefix(self, subst: &Substs) -> Binders<T> {
+        assert!(subst.len() < self.num_binders);
+        Binders::new(self.num_binders - subst.len(), self.value.subst_bound_vars(subst))
+    }
+}
+
 /// A trait with type parameters. This includes the `Self`, so this represents a concrete type implementing the trait.
 /// Name to be bikeshedded: TraitBound? TraitImplements?
 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
@@ -553,6 +577,9 @@ pub struct FnSig {
     params_and_return: Arc<[Ty]>,
 }
 
+/// A polymorphic function signature.
+pub type PolyFnSig = Binders<FnSig>;
+
 impl FnSig {
     pub fn from_params_and_return(mut params: Vec<Ty>, ret: Ty) -> FnSig {
         params.push(ret);
@@ -757,6 +784,9 @@ pub trait TypeWalk {
                 &mut Ty::Bound(idx) => {
                     if idx as usize >= binders && (idx as usize - binders) < substs.len() {
                         *ty = substs.0[idx as usize - binders].clone();
+                    } else if idx as usize >= binders + substs.len() {
+                        // shift free binders
+                        *ty = Ty::Bound(idx - substs.len() as u32);
                     }
                 }
                 _ => {}
@@ -903,8 +933,8 @@ impl HirDisplay for ApplicationTy {
                     write!(f, ">")?;
                 }
                 write!(f, "(")?;
-                f.write_joined(sig.params(), ", ")?;
-                write!(f, ") -> {}", sig.ret().display(f.db))?;
+                f.write_joined(sig.value.params(), ", ")?;
+                write!(f, ") -> {}", sig.value.ret().display(f.db))?;
             }
             TypeCtor::Adt(def_id) => {
                 let name = match def_id {
diff --git a/crates/ra_hir_ty/src/lower.rs b/crates/ra_hir_ty/src/lower.rs
index 6f7681475..006101f2f 100644
--- a/crates/ra_hir_ty/src/lower.rs
+++ b/crates/ra_hir_ty/src/lower.rs
@@ -28,32 +28,62 @@ use crate::{
         variant_data,
     },
     FnSig, GenericPredicate, ProjectionPredicate, ProjectionTy, Substs, TraitEnvironment, TraitRef,
-    Ty, TypeCtor, TypeWalk,
+    Ty, TypeCtor, PolyFnSig, Binders,
 };
 
-#[derive(Clone, Debug)]
+#[derive(Debug)]
 pub struct TyLoweringContext<'a, DB: HirDatabase> {
     pub db: &'a DB,
     pub resolver: &'a Resolver,
+    /// Note: Conceptually, it's thinkable that we could be in a location where
+    /// some type params are quantified universally (and should be represented
+    /// as placeholders), and others are quantified existentially (and should be
+    /// converted to variables). I think in practice, this isn't possible
+    /// currently, so this should be fine for now.
+    pub type_param_mode: TypeParamLoweringMode,
     pub impl_trait_mode: ImplTraitLoweringMode,
+    pub impl_trait_counter: std::cell::Cell<u16>,
 }
 
-#[derive(Clone, Debug)]
+impl<'a, DB: HirDatabase> TyLoweringContext<'a, DB> {
+    pub fn new(db: &'a DB, resolver: &'a Resolver) -> Self {
+        let impl_trait_counter = std::cell::Cell::new(0);
+        let impl_trait_mode = ImplTraitLoweringMode::Disallowed;
+        let type_param_mode = TypeParamLoweringMode::Placeholder;
+        Self { db, resolver, impl_trait_mode, impl_trait_counter, type_param_mode }
+    }
+
+    pub fn with_impl_trait_mode(self, impl_trait_mode: ImplTraitLoweringMode) -> Self {
+        Self { impl_trait_mode, ..self }
+    }
+
+    pub fn with_type_param_mode(self, type_param_mode: TypeParamLoweringMode) -> Self {
+        Self { type_param_mode, ..self }
+    }
+}
+
+#[derive(Copy, Clone, Debug)]
 pub enum ImplTraitLoweringMode {
     /// `impl Trait` gets lowered into an opaque type that doesn't unify with
     /// anything except itself. This is used in places where values flow 'out',
     /// i.e. for arguments of the function we're currently checking, and return
     /// types of functions we're calling.
     Opaque,
-    /// `impl Trait` gets lowered into a placeholder that can unify with some
+    /// `impl Trait` gets lowered into a variable that can unify with some
     /// type. This is used in places where values flow 'in', i.e. for arguments
     /// of functions we're calling, and the return type of the function we're
     /// currently checking.
-    Placeholder,
+    Variable,
     /// `impl Trait` is disallowed and will be an error.
     Disallowed,
 }
 
+#[derive(Copy, Clone, Debug)]
+pub enum TypeParamLoweringMode {
+    Placeholder,
+    Variable,
+}
+
 impl Ty {
     pub fn from_hir(ctx: &TyLoweringContext<'_, impl HirDatabase>, type_ref: &TypeRef) -> Self {
         match type_ref {
@@ -101,17 +131,25 @@ impl Ty {
                         let self_ty = Ty::Bound(0);
                         let predicates = bounds
                             .iter()
-                            .flat_map(|b| GenericPredicate::from_type_bound(ctx, b, self_ty.clone()))
+                            .flat_map(|b| {
+                                GenericPredicate::from_type_bound(ctx, b, self_ty.clone())
+                            })
                             .collect();
                         Ty::Opaque(predicates)
-                    },
-                    ImplTraitLoweringMode::Placeholder => {
-                        todo!()
-                    },
+                    }
+                    ImplTraitLoweringMode::Variable => {
+                        let idx = ctx.impl_trait_counter.get();
+                        ctx.impl_trait_counter.set(idx + 1);
+                        let generics =
+                            generics(ctx.db, ctx.resolver.generic_def().expect("generics in scope"));
+                        let (self_params, list_params, impl_trait_params) = generics.provenance_split();
+                        assert!((idx as usize) < impl_trait_params);
+                        Ty::Bound(idx as u32 + self_params as u32 + list_params as u32)
+                    }
                     ImplTraitLoweringMode::Disallowed => {
                         // FIXME: report error
                         Ty::Unknown
-                    },
+                    }
                 }
             }
             TypeRef::Error => Ty::Unknown,
@@ -205,12 +243,31 @@ impl Ty {
                 let generics =
                     generics(ctx.db, ctx.resolver.generic_def().expect("generics in scope"));
                 let idx = generics.param_idx(param_id);
-                // FIXME: maybe return name in resolution?
-                let name = generics.param_name(param_id);
-                Ty::Param { idx, name }
+                match ctx.type_param_mode {
+                    TypeParamLoweringMode::Placeholder => {
+                        // FIXME: maybe return name in resolution?
+                        let name = generics.param_name(param_id);
+                        Ty::Param { idx, name }
+                    },
+                    TypeParamLoweringMode::Variable => Ty::Bound(idx),
+                }
             }
-            TypeNs::SelfType(impl_id) => ctx.db.impl_self_ty(impl_id).clone(),
-            TypeNs::AdtSelfType(adt) => ctx.db.ty(adt.into()),
+            TypeNs::SelfType(impl_id) => {
+                let generics = generics(ctx.db, impl_id.into());
+                let substs = match ctx.type_param_mode {
+                    TypeParamLoweringMode::Placeholder => Substs::identity(&generics),
+                    TypeParamLoweringMode::Variable => Substs::bound_vars(&generics),
+                };
+                ctx.db.impl_self_ty(impl_id).subst(&substs)
+            },
+            TypeNs::AdtSelfType(adt) => {
+                let generics = generics(ctx.db, adt.into());
+                let substs = match ctx.type_param_mode {
+                    TypeParamLoweringMode::Placeholder => Substs::identity(&generics),
+                    TypeParamLoweringMode::Variable => Substs::bound_vars(&generics),
+                };
+                ctx.db.ty(adt.into()).subst(&substs)
+            },
 
             TypeNs::AdtId(it) => Ty::from_hir_path_inner(ctx, resolved_segment, it.into()),
             TypeNs::BuiltinType(it) => Ty::from_hir_path_inner(ctx, resolved_segment, it.into()),
@@ -341,7 +398,7 @@ pub(super) fn substs_from_path_segment(
         // Self type as an implicit first type parameter, but it can't be
         // actually provided in the type arguments
         // (well, actually sometimes it can, in the form of type-relative paths: `<Foo as Default>::default()`)
-        // TODO handle this using type param provenance
+        // TODO handle this using type param provenance (if there's a self param, and not one provided, add unknown)
         substs.push(Ty::Unknown);
     }
     if let Some(generic_args) = &segment.args_and_bindings {
@@ -493,7 +550,7 @@ fn assoc_type_bindings_from_type_bound<'a>(
 }
 
 /// Build the signature of a callable item (function, struct or enum variant).
-pub fn callable_item_sig(db: &impl HirDatabase, def: CallableDef) -> FnSig {
+pub fn callable_item_sig(db: &impl HirDatabase, def: CallableDef) -> PolyFnSig {
     match def {
         CallableDef::FunctionId(f) => fn_sig_for_fn(db, f),
         CallableDef::StructId(s) => fn_sig_for_struct_constructor(db, s),
@@ -513,11 +570,7 @@ pub(crate) fn field_types_query(
         VariantId::EnumVariantId(it) => it.parent.resolver(db),
     };
     let mut res = ArenaMap::default();
-    let ctx = TyLoweringContext {
-        db,
-        resolver: &resolver,
-        impl_trait_mode: ImplTraitLoweringMode::Disallowed,
-    };
+    let ctx = TyLoweringContext::new(db, &resolver);
     for (field_id, field_data) in var_data.fields().iter() {
         res.insert(field_id, Ty::from_hir(&ctx, &field_data.type_ref))
     }
@@ -538,11 +591,7 @@ pub(crate) fn generic_predicates_for_param_query(
     param_idx: u32,
 ) -> Arc<[GenericPredicate]> {
     let resolver = def.resolver(db);
-    let ctx = TyLoweringContext {
-        db,
-        resolver: &resolver,
-        impl_trait_mode: ImplTraitLoweringMode::Disallowed,
-    };
+    let ctx = TyLoweringContext::new(db, &resolver);
     resolver
         .where_predicates_in_scope()
         // we have to filter out all other predicates *first*, before attempting to lower them
@@ -562,8 +611,7 @@ pub(crate) fn generic_predicates_for_param_recover(
 
 impl TraitEnvironment {
     pub fn lower(db: &impl HirDatabase, resolver: &Resolver) -> Arc<TraitEnvironment> {
-        let ctx =
-            TyLoweringContext { db, resolver, impl_trait_mode: ImplTraitLoweringMode::Disallowed };
+        let ctx = TyLoweringContext::new(db, &resolver);
         let predicates = resolver
             .where_predicates_in_scope()
             .flat_map(|pred| GenericPredicate::from_where_predicate(&ctx, pred))
@@ -579,11 +627,7 @@ pub(crate) fn generic_predicates_query(
     def: GenericDefId,
 ) -> Arc<[GenericPredicate]> {
     let resolver = def.resolver(db);
-    let ctx = TyLoweringContext {
-        db,
-        resolver: &resolver,
-        impl_trait_mode: ImplTraitLoweringMode::Disallowed,
-    };
+    let ctx = TyLoweringContext::new(db, &resolver);
     resolver
         .where_predicates_in_scope()
         .flat_map(|pred| GenericPredicate::from_where_predicate(&ctx, pred))
@@ -593,11 +637,7 @@ pub(crate) fn generic_predicates_query(
 /// Resolve the default type params from generics
 pub(crate) fn generic_defaults_query(db: &impl HirDatabase, def: GenericDefId) -> Substs {
     let resolver = def.resolver(db);
-    let ctx = TyLoweringContext {
-        db,
-        resolver: &resolver,
-        impl_trait_mode: ImplTraitLoweringMode::Disallowed,
-    };
+    let ctx = TyLoweringContext::new(db, &resolver);
     let generic_params = generics(db, def.into());
 
     let defaults = generic_params
@@ -608,56 +648,46 @@ pub(crate) fn generic_defaults_query(db: &impl HirDatabase, def: GenericDefId) -
     Substs(defaults)
 }
 
-fn fn_sig_for_fn(db: &impl HirDatabase, def: FunctionId) -> FnSig {
+fn fn_sig_for_fn(db: &impl HirDatabase, def: FunctionId) -> PolyFnSig {
     let data = db.function_data(def);
     let resolver = def.resolver(db);
-    let ctx_params = TyLoweringContext {
-        db,
-        resolver: &resolver,
-        impl_trait_mode: ImplTraitLoweringMode::Placeholder,
-    };
+    let ctx_params = TyLoweringContext::new(db, &resolver)
+        .with_impl_trait_mode(ImplTraitLoweringMode::Variable)
+        .with_type_param_mode(TypeParamLoweringMode::Variable);
     let params = data.params.iter().map(|tr| Ty::from_hir(&ctx_params, tr)).collect::<Vec<_>>();
-    let ctx_ret = TyLoweringContext {
-        db,
-        resolver: &resolver,
-        impl_trait_mode: ImplTraitLoweringMode::Opaque,
-    };
+    let ctx_ret = ctx_params.with_impl_trait_mode(ImplTraitLoweringMode::Opaque);
     let ret = Ty::from_hir(&ctx_ret, &data.ret_type);
-    FnSig::from_params_and_return(params, ret)
+    let generics = generics(db, def.into());
+    let num_binders = generics.len();
+    Binders::new(num_binders, FnSig::from_params_and_return(params, ret))
 }
 
 /// Build the declared type of a function. This should not need to look at the
 /// function body.
-fn type_for_fn(db: &impl HirDatabase, def: FunctionId) -> Ty {
+fn type_for_fn(db: &impl HirDatabase, def: FunctionId) -> Binders<Ty> {
     let generics = generics(db, def.into());
-    let substs = Substs::identity(&generics);
-    Ty::apply(TypeCtor::FnDef(def.into()), substs)
+    let substs = Substs::bound_vars(&generics);
+    Binders::new(substs.len(), Ty::apply(TypeCtor::FnDef(def.into()), substs))
 }
 
 /// Build the declared type of a const.
-fn type_for_const(db: &impl HirDatabase, def: ConstId) -> Ty {
+fn type_for_const(db: &impl HirDatabase, def: ConstId) -> Binders<Ty> {
     let data = db.const_data(def);
+    let generics = generics(db, def.into());
     let resolver = def.resolver(db);
-    let ctx = TyLoweringContext {
-        db,
-        resolver: &resolver,
-        impl_trait_mode: ImplTraitLoweringMode::Disallowed,
-    };
+    let ctx = TyLoweringContext::new(db, &resolver)
+        .with_type_param_mode(TypeParamLoweringMode::Variable);
 
-    Ty::from_hir(&ctx, &data.type_ref)
+    Binders::new(generics.len(), Ty::from_hir(&ctx, &data.type_ref))
 }
 
 /// Build the declared type of a static.
-fn type_for_static(db: &impl HirDatabase, def: StaticId) -> Ty {
+fn type_for_static(db: &impl HirDatabase, def: StaticId) -> Binders<Ty> {
     let data = db.static_data(def);
     let resolver = def.resolver(db);
-    let ctx = TyLoweringContext {
-        db,
-        resolver: &resolver,
-        impl_trait_mode: ImplTraitLoweringMode::Disallowed,
-    };
+    let ctx = TyLoweringContext::new(db, &resolver);
 
-    Ty::from_hir(&ctx, &data.type_ref)
+    Binders::new(0, Ty::from_hir(&ctx, &data.type_ref))
 }
 
 /// Build the declared type of a static.
@@ -671,79 +701,71 @@ fn type_for_builtin(def: BuiltinType) -> Ty {
     })
 }
 
-fn fn_sig_for_struct_constructor(db: &impl HirDatabase, def: StructId) -> FnSig {
+fn fn_sig_for_struct_constructor(db: &impl HirDatabase, def: StructId) -> PolyFnSig {
     let struct_data = db.struct_data(def.into());
     let fields = struct_data.variant_data.fields();
     let resolver = def.resolver(db);
-    let ctx = TyLoweringContext {
-        db,
-        resolver: &resolver,
-        impl_trait_mode: ImplTraitLoweringMode::Disallowed,
-    };
+    let ctx = TyLoweringContext::new(db, &resolver)
+        .with_type_param_mode(TypeParamLoweringMode::Variable);
     let params =
         fields.iter().map(|(_, field)| Ty::from_hir(&ctx, &field.type_ref)).collect::<Vec<_>>();
     let ret = type_for_adt(db, def.into());
-    FnSig::from_params_and_return(params, ret)
+    Binders::new(ret.num_binders, FnSig::from_params_and_return(params, ret.value))
 }
 
 /// Build the type of a tuple struct constructor.
-fn type_for_struct_constructor(db: &impl HirDatabase, def: StructId) -> Ty {
+fn type_for_struct_constructor(db: &impl HirDatabase, def: StructId) -> Binders<Ty> {
     let struct_data = db.struct_data(def.into());
     if struct_data.variant_data.is_unit() {
         return type_for_adt(db, def.into()); // Unit struct
     }
     let generics = generics(db, def.into());
-    let substs = Substs::identity(&generics);
-    Ty::apply(TypeCtor::FnDef(def.into()), substs)
+    let substs = Substs::bound_vars(&generics);
+    Binders::new(substs.len(), Ty::apply(TypeCtor::FnDef(def.into()), substs))
 }
 
-fn fn_sig_for_enum_variant_constructor(db: &impl HirDatabase, def: EnumVariantId) -> FnSig {
+fn fn_sig_for_enum_variant_constructor(db: &impl HirDatabase, def: EnumVariantId) -> PolyFnSig {
     let enum_data = db.enum_data(def.parent);
     let var_data = &enum_data.variants[def.local_id];
     let fields = var_data.variant_data.fields();
     let resolver = def.parent.resolver(db);
-    let ctx = TyLoweringContext {
-        db,
-        resolver: &resolver,
-        impl_trait_mode: ImplTraitLoweringMode::Disallowed,
-    };
+    let ctx = TyLoweringContext::new(db, &resolver);
     let params =
         fields.iter().map(|(_, field)| Ty::from_hir(&ctx, &field.type_ref)).collect::<Vec<_>>();
     let generics = generics(db, def.parent.into());
-    let substs = Substs::identity(&generics);
+    let substs = Substs::bound_vars(&generics);
     let ret = type_for_adt(db, def.parent.into()).subst(&substs);
-    FnSig::from_params_and_return(params, ret)
+    let num_binders = generics.len();
+    Binders::new(num_binders, FnSig::from_params_and_return(params, ret))
 }
 
 /// Build the type of a tuple enum variant constructor.
-fn type_for_enum_variant_constructor(db: &impl HirDatabase, def: EnumVariantId) -> Ty {
+fn type_for_enum_variant_constructor(db: &impl HirDatabase, def: EnumVariantId) -> Binders<Ty> {
     let enum_data = db.enum_data(def.parent);
     let var_data = &enum_data.variants[def.local_id].variant_data;
     if var_data.is_unit() {
         return type_for_adt(db, def.parent.into()); // Unit variant
     }
     let generics = generics(db, def.parent.into());
-    let substs = Substs::identity(&generics);
-    Ty::apply(TypeCtor::FnDef(EnumVariantId::from(def).into()), substs)
+    let substs = Substs::bound_vars(&generics);
+    Binders::new(substs.len(), Ty::apply(TypeCtor::FnDef(EnumVariantId::from(def).into()), substs))
 }
 
-fn type_for_adt(db: &impl HirDatabase, adt: AdtId) -> Ty {
+fn type_for_adt(db: &impl HirDatabase, adt: AdtId) -> Binders<Ty> {
     let generics = generics(db, adt.into());
-    Ty::apply(TypeCtor::Adt(adt), Substs::identity(&generics))
+    let substs = Substs::bound_vars(&generics);
+    Binders::new(substs.len(), Ty::apply(TypeCtor::Adt(adt), substs))
 }
 
-fn type_for_type_alias(db: &impl HirDatabase, t: TypeAliasId) -> Ty {
+fn type_for_type_alias(db: &impl HirDatabase, t: TypeAliasId) -> Binders<Ty> {
     let generics = generics(db, t.into());
     let resolver = t.resolver(db);
-    let ctx = TyLoweringContext {
-        db,
-        resolver: &resolver,
-        impl_trait_mode: ImplTraitLoweringMode::Disallowed,
-    };
+    let ctx = TyLoweringContext::new(db, &resolver)
+        .with_type_param_mode(TypeParamLoweringMode::Variable);
     let type_ref = &db.type_alias_data(t).type_ref;
-    let substs = Substs::identity(&generics);
+    let substs = Substs::bound_vars(&generics);
     let inner = Ty::from_hir(&ctx, type_ref.as_ref().unwrap_or(&TypeRef::Error));
-    inner.subst(&substs)
+    Binders::new(substs.len(), inner)
 }
 
 #[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
@@ -797,19 +819,20 @@ impl_froms!(ValueTyDefId: FunctionId, StructId, EnumVariantId, ConstId, StaticId
 /// `struct Foo(usize)`, we have two types: The type of the struct itself, and
 /// the constructor function `(usize) -> Foo` which lives in the values
 /// namespace.
-pub(crate) fn ty_query(db: &impl HirDatabase, def: TyDefId) -> Ty {
+pub(crate) fn ty_query(db: &impl HirDatabase, def: TyDefId) -> Binders<Ty> {
     match def {
-        TyDefId::BuiltinType(it) => type_for_builtin(it),
+        TyDefId::BuiltinType(it) => Binders::new(0, type_for_builtin(it)),
         TyDefId::AdtId(it) => type_for_adt(db, it),
         TyDefId::TypeAliasId(it) => type_for_type_alias(db, it),
     }
 }
 
-pub(crate) fn ty_recover(_db: &impl HirDatabase, _cycle: &[String], _def: &TyDefId) -> Ty {
-    Ty::Unknown
+pub(crate) fn ty_recover(_db: &impl HirDatabase, _cycle: &[String], _def: &TyDefId) -> Binders<Ty> {
+    // TODO still need correct number of binders here
+    Binders::new(0, Ty::Unknown)
 }
 
-pub(crate) fn value_ty_query(db: &impl HirDatabase, def: ValueTyDefId) -> Ty {
+pub(crate) fn value_ty_query(db: &impl HirDatabase, def: ValueTyDefId) -> Binders<Ty> {
     match def {
         ValueTyDefId::FunctionId(it) => type_for_fn(db, it),
         ValueTyDefId::StructId(it) => type_for_struct_constructor(db, it),
@@ -819,34 +842,30 @@ pub(crate) fn value_ty_query(db: &impl HirDatabase, def: ValueTyDefId) -> Ty {
     }
 }
 
-pub(crate) fn impl_self_ty_query(db: &impl HirDatabase, impl_id: ImplId) -> Ty {
+pub(crate) fn impl_self_ty_query(db: &impl HirDatabase, impl_id: ImplId) -> Binders<Ty> {
     let impl_data = db.impl_data(impl_id);
     let resolver = impl_id.resolver(db);
-    let ctx = TyLoweringContext {
-        db,
-        resolver: &resolver,
-        impl_trait_mode: ImplTraitLoweringMode::Disallowed,
-    };
-    Ty::from_hir(&ctx, &impl_data.target_type)
+    let generics = generics(db, impl_id.into());
+    let ctx = TyLoweringContext::new(db, &resolver)
+        .with_type_param_mode(TypeParamLoweringMode::Variable);
+    Binders::new(generics.len(), Ty::from_hir(&ctx, &impl_data.target_type))
 }
 
 pub(crate) fn impl_self_ty_recover(
-    _db: &impl HirDatabase,
+    db: &impl HirDatabase,
     _cycle: &[String],
-    _impl_id: &ImplId,
-) -> Ty {
-    Ty::Unknown
+    impl_id: &ImplId,
+) -> Binders<Ty> {
+    let generics = generics(db, (*impl_id).into());
+    Binders::new(generics.len(), Ty::Unknown)
 }
 
 pub(crate) fn impl_trait_query(db: &impl HirDatabase, impl_id: ImplId) -> Option<TraitRef> {
     let impl_data = db.impl_data(impl_id);
     let resolver = impl_id.resolver(db);
-    let ctx = TyLoweringContext {
-        db,
-        resolver: &resolver,
-        impl_trait_mode: ImplTraitLoweringMode::Disallowed,
-    };
-    let self_ty = db.impl_self_ty(impl_id);
+    let generics = generics(db, impl_id.into());
+    let ctx = TyLoweringContext::new(db, &resolver);
+    let self_ty = db.impl_self_ty(impl_id).subst(&Substs::identity(&generics));
     let target_trait = impl_data.target_trait.as_ref()?;
     TraitRef::from_hir(&ctx, target_trait, Some(self_ty.clone()))
 }
diff --git a/crates/ra_hir_ty/src/method_resolution.rs b/crates/ra_hir_ty/src/method_resolution.rs
index 5bacbbd7c..eab2149dc 100644
--- a/crates/ra_hir_ty/src/method_resolution.rs
+++ b/crates/ra_hir_ty/src/method_resolution.rs
@@ -65,7 +65,7 @@ impl CrateImplBlocks {
                     }
                     None => {
                         let self_ty = db.impl_self_ty(impl_id);
-                        if let Some(self_ty_fp) = TyFingerprint::for_impl(&self_ty) {
+                        if let Some(self_ty_fp) = TyFingerprint::for_impl(&self_ty.value) {
                             res.impls.entry(self_ty_fp).or_default().push(impl_id);
                         }
                     }
@@ -496,7 +496,7 @@ fn transform_receiver_ty(
         AssocContainerId::ContainerId(_) => unreachable!(),
     };
     let sig = db.callable_item_signature(function_id.into());
-    Some(sig.params()[0].clone().subst(&substs))
+    Some(sig.value.params()[0].clone().subst_bound_vars(&substs))
 }
 
 pub fn implements_trait(
diff --git a/crates/ra_hir_ty/src/tests/simple.rs b/crates/ra_hir_ty/src/tests/simple.rs
index fdab9c187..f1238506b 100644
--- a/crates/ra_hir_ty/src/tests/simple.rs
+++ b/crates/ra_hir_ty/src/tests/simple.rs
@@ -1220,7 +1220,7 @@ fn test() {
 }
 
 #[test]
-fn infer_impl_generics() {
+fn infer_impl_generics_basic() {
     assert_snapshot!(
         infer(r#"
 struct A<T1, T2> {
diff --git a/crates/ra_hir_ty/src/utils.rs b/crates/ra_hir_ty/src/utils.rs
index 314a3241f..f116b95e7 100644
--- a/crates/ra_hir_ty/src/utils.rs
+++ b/crates/ra_hir_ty/src/utils.rs
@@ -5,7 +5,7 @@ use std::sync::Arc;
 use hir_def::{
     adt::VariantData,
     db::DefDatabase,
-    generics::{GenericParams, TypeParamData},
+    generics::{GenericParams, TypeParamData, TypeParamProvenance},
     path::Path,
     resolver::{HasResolver, TypeNs},
     type_ref::TypeRef,
@@ -117,19 +117,31 @@ impl Generics {
     pub(crate) fn len(&self) -> usize {
         self.len_split().0
     }
+
     /// (total, parents, child)
     pub(crate) fn len_split(&self) -> (usize, usize, usize) {
         let parent = self.parent_generics.as_ref().map_or(0, |p| p.len());
         let child = self.params.types.len();
         (parent + child, parent, child)
     }
+
+    /// (self, type param list, impl trait)
+    pub(crate) fn provenance_split(&self) -> (usize, usize, usize) {
+        let self_params = self.params.types.iter().filter(|(_, p)| p.provenance == TypeParamProvenance::TraitSelf).count();
+        let list_params = self.params.types.iter().filter(|(_, p)| p.provenance == TypeParamProvenance::TypeParamList).count();
+        let impl_trait_params = self.params.types.iter().filter(|(_, p)| p.provenance == TypeParamProvenance::ArgumentImplTrait).count();
+        (self_params, list_params, impl_trait_params)
+    }
+
     pub(crate) fn param_idx(&self, param: TypeParamId) -> u32 {
         self.find_param(param).0
     }
+
     pub(crate) fn param_name(&self, param: TypeParamId) -> Name {
         // FIXME make this return Option
         self.find_param(param).1.name.clone().unwrap_or_else(Name::missing)
     }
+
     fn find_param(&self, param: TypeParamId) -> (u32, &TypeParamData) {
         if param.parent == self.def {
             let (idx, (_local_id, data)) = self