20 files changed, 423 insertions, 373 deletions

diff --git a/crates/hir/src/display.rs b/crates/hir/src/display.rs
index 559ea31a0..993772aac 100644
--- a/crates/hir/src/display.rs
+++ b/crates/hir/src/display.rs
@@ -13,7 +13,7 @@ use syntax::ast::{self, NameOwner};
 
 use crate::{
     Adt, Const, ConstParam, Enum, Field, Function, GenericParam, HasVisibility, LifetimeParam,
-    Module, Static, Struct, Substitution, Trait, Type, TypeAlias, TypeParam, Union, Variant,
+    Module, Static, Struct, Trait, TyBuilder, Type, TypeAlias, TypeParam, Union, Variant,
 };
 
 impl HirDisplay for Function {
@@ -234,7 +234,7 @@ impl HirDisplay for TypeParam {
     fn hir_fmt(&self, f: &mut HirFormatter) -> Result<(), HirDisplayError> {
         write!(f, "{}", self.name(f.db))?;
         let bounds = f.db.generic_predicates_for_param(self.id);
-        let substs = Substitution::type_params(f.db, self.id.parent);
+        let substs = TyBuilder::type_params_subst(f.db, self.id.parent);
         let predicates = bounds.iter().cloned().map(|b| b.subst(&substs)).collect::<Vec<_>>();
         if !(predicates.is_empty() || f.omit_verbose_types()) {
             write_bounds_like_dyn_trait_with_prefix(":", &predicates, f)?;
diff --git a/crates/hir/src/lib.rs b/crates/hir/src/lib.rs
index eb19e4b51..19901ed33 100644
--- a/crates/hir/src/lib.rs
+++ b/crates/hir/src/lib.rs
@@ -55,11 +55,10 @@ use hir_ty::{
     autoderef, could_unify,
     method_resolution::{self, TyFingerprint},
     primitive::UintTy,
-    to_assoc_type_id,
     traits::{FnTrait, Solution, SolutionVariables},
     AliasEq, AliasTy, BoundVar, CallableDefId, CallableSig, Canonical, CanonicalVarKinds, Cast,
-    DebruijnIndex, InEnvironment, Interner, ProjectionTy, QuantifiedWhereClause, Scalar,
-    Substitution, TraitEnvironment, Ty, TyDefId, TyKind, TyVariableKind, WhereClause,
+    DebruijnIndex, InEnvironment, Interner, QuantifiedWhereClause, Scalar, Substitution,
+    TraitEnvironment, Ty, TyBuilder, TyDefId, TyKind, TyVariableKind, WhereClause,
 };
 use itertools::Itertools;
 use rustc_hash::FxHashSet;
@@ -515,7 +514,7 @@ impl Field {
             VariantDef::Union(it) => it.id.into(),
             VariantDef::Variant(it) => it.parent.id.into(),
         };
-        let substs = Substitution::type_params(db, generic_def_id);
+        let substs = TyBuilder::type_params_subst(db, generic_def_id);
         let ty = db.field_types(var_id)[self.id].clone().subst(&substs);
         Type::new(db, self.parent.module(db).id.krate(), var_id, ty)
     }
@@ -1129,7 +1128,7 @@ pub struct BuiltinType {
 impl BuiltinType {
     pub fn ty(self, db: &dyn HirDatabase, module: Module) -> Type {
         let resolver = module.id.resolver(db.upcast());
-        Type::new_with_resolver(db, &resolver, Ty::builtin(self.inner))
+        Type::new_with_resolver(db, &resolver, TyBuilder::builtin(self.inner))
             .expect("crate not present in resolver")
     }
 
@@ -1502,7 +1501,7 @@ impl TypeParam {
         let resolver = self.id.parent.resolver(db.upcast());
         let krate = self.id.parent.module(db.upcast()).krate();
         let ty = params.get(local_idx)?.clone();
-        let subst = Substitution::type_params(db, self.id.parent);
+        let subst = TyBuilder::type_params_subst(db, self.id.parent);
         let ty = ty.subst(&subst.prefix(local_idx));
         Some(Type::new_with_resolver_inner(db, krate, &resolver, ty))
     }
@@ -1703,10 +1702,9 @@ impl Type {
     fn from_def(
         db: &dyn HirDatabase,
         krate: CrateId,
-        def: impl HasResolver + Into<TyDefId> + Into<GenericDefId>,
+        def: impl HasResolver + Into<TyDefId>,
     ) -> Type {
-        let substs = Substitution::build_for_def(db, def).fill_with_unknown().build();
-        let ty = db.ty(def.into()).subst(&substs);
+        let ty = TyBuilder::def_ty(db, def.into()).fill_with_unknown().build();
         Type::new(db, krate, def, ty)
     }
 
@@ -1785,13 +1783,10 @@ impl Type {
     }
 
     pub fn impls_trait(&self, db: &dyn HirDatabase, trait_: Trait, args: &[Type]) -> bool {
-        let trait_ref = hir_ty::TraitRef {
-            trait_id: hir_ty::to_chalk_trait_id(trait_.id),
-            substitution: Substitution::build_for_def(db, trait_.id)
-                .push(self.ty.clone())
-                .fill(args.iter().map(|t| t.ty.clone()))
-                .build(),
-        };
+        let trait_ref = TyBuilder::trait_ref(db, trait_.id)
+            .push(self.ty.clone())
+            .fill(args.iter().map(|t| t.ty.clone()))
+            .build();
 
         let goal = Canonical {
             value: hir_ty::InEnvironment::new(self.env.env.clone(), trait_ref.cast(&Interner)),
@@ -1804,11 +1799,10 @@ impl Type {
     pub fn normalize_trait_assoc_type(
         &self,
         db: &dyn HirDatabase,
-        trait_: Trait,
         args: &[Type],
         alias: TypeAlias,
     ) -> Option<Type> {
-        let subst = Substitution::build_for_def(db, trait_.id)
+        let projection = TyBuilder::assoc_type_projection(db, alias.id)
             .push(self.ty.clone())
             .fill(args.iter().map(|t| t.ty.clone()))
             .build();
@@ -1816,10 +1810,7 @@ impl Type {
             InEnvironment::new(
                 self.env.env.clone(),
                 AliasEq {
-                    alias: AliasTy::Projection(ProjectionTy {
-                        associated_ty_id: to_assoc_type_id(alias.id),
-                        substitution: subst,
-                    }),
+                    alias: AliasTy::Projection(projection),
                     ty: TyKind::BoundVar(BoundVar::new(DebruijnIndex::INNERMOST, 0))
                         .intern(&Interner),
                 }
diff --git a/crates/hir_ty/src/autoderef.rs b/crates/hir_ty/src/autoderef.rs
index c859f9491..70c56cc45 100644
--- a/crates/hir_ty/src/autoderef.rs
+++ b/crates/hir_ty/src/autoderef.rs
@@ -13,11 +13,9 @@ use log::{info, warn};
 
 use crate::{
     db::HirDatabase,
-    to_assoc_type_id, to_chalk_trait_id,
     traits::{InEnvironment, Solution},
-    utils::generics,
-    AliasEq, AliasTy, BoundVar, Canonical, CanonicalVarKinds, DebruijnIndex, Interner,
-    ProjectionTy, Substitution, TraitRef, Ty, TyKind,
+    AliasEq, AliasTy, BoundVar, Canonical, CanonicalVarKinds, DebruijnIndex, Interner, Ty,
+    TyBuilder, TyKind,
 };
 
 const AUTODEREF_RECURSION_LIMIT: usize = 10;
@@ -57,21 +55,20 @@ fn deref_by_trait(
     };
     let target = db.trait_data(deref_trait).associated_type_by_name(&name![Target])?;
 
-    let generic_params = generics(db.upcast(), target.into());
-    if generic_params.len() != 1 {
-        // the Target type + Deref trait should only have one generic parameter,
-        // namely Deref's Self type
-        return None;
-    }
+    let projection = {
+        let b = TyBuilder::assoc_type_projection(db, target);
+        if b.remaining() != 1 {
+            // the Target type + Deref trait should only have one generic parameter,
+            // namely Deref's Self type
+            return None;
+        }
+        b.push(ty.goal.value.clone()).build()
+    };
 
     // FIXME make the Canonical / bound var handling nicer
 
-    let parameters =
-        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 trait_ref = projection.trait_ref(db);
     let implements_goal = Canonical {
         binders: ty.goal.binders.clone(),
         value: InEnvironment {
@@ -84,11 +81,8 @@ fn deref_by_trait(
     }
 
     // Now do the assoc type projection
-    let projection = AliasEq {
-        alias: AliasTy::Projection(ProjectionTy {
-            associated_ty_id: to_assoc_type_id(target),
-            substitution: parameters,
-        }),
+    let alias_eq = AliasEq {
+        alias: AliasTy::Projection(projection),
         ty: TyKind::BoundVar(BoundVar::new(
             DebruijnIndex::INNERMOST,
             ty.goal.binders.len(&Interner),
@@ -96,9 +90,7 @@ fn deref_by_trait(
         .intern(&Interner),
     };
 
-    let obligation = projection.cast(&Interner);
-
-    let in_env = InEnvironment { goal: obligation, environment: ty.environment };
+    let in_env = InEnvironment { goal: alias_eq.cast(&Interner), environment: ty.environment };
 
     let canonical = Canonical {
         value: in_env,
diff --git a/crates/hir_ty/src/builder.rs b/crates/hir_ty/src/builder.rs
new file mode 100644
index 000000000..4a9a8058f
--- /dev/null
+++ b/crates/hir_ty/src/builder.rs
@@ -0,0 +1,219 @@
+//! `TyBuilder`, a helper for building instances of `Ty` and related types.
+
+use std::iter;
+
+use chalk_ir::{
+    cast::{Cast, CastTo, Caster},
+    interner::HasInterner,
+    AdtId, BoundVar, DebruijnIndex, Safety, Scalar,
+};
+use hir_def::{builtin_type::BuiltinType, GenericDefId, TraitId, TypeAliasId};
+use smallvec::SmallVec;
+
+use crate::{
+    db::HirDatabase, primitive, to_assoc_type_id, to_chalk_trait_id, utils::generics, Binders,
+    CallableSig, FnPointer, FnSig, GenericArg, Interner, ProjectionTy, Substitution, TraitRef, Ty,
+    TyDefId, TyKind, TypeWalk, ValueTyDefId,
+};
+
+/// This is a builder for `Ty` or anything that needs a `Substitution`.
+pub struct TyBuilder<D> {
+    /// The `data` field is used to keep track of what we're building (e.g. an
+    /// ADT, a `TraitRef`, ...).
+    data: D,
+    vec: SmallVec<[GenericArg; 2]>,
+    param_count: usize,
+}
+
+impl<D> TyBuilder<D> {
+    fn new(data: D, param_count: usize) -> TyBuilder<D> {
+        TyBuilder { data, param_count, vec: SmallVec::with_capacity(param_count) }
+    }
+
+    fn build_internal(self) -> (D, Substitution) {
+        assert_eq!(self.vec.len(), self.param_count);
+        // FIXME: would be good to have a way to construct a chalk_ir::Substitution from the interned form
+        let subst = Substitution(self.vec);
+        (self.data, subst)
+    }
+
+    pub fn push(mut self, arg: impl CastTo<GenericArg>) -> Self {
+        self.vec.push(arg.cast(&Interner));
+        self
+    }
+
+    pub fn remaining(&self) -> usize {
+        self.param_count - self.vec.len()
+    }
+
+    pub fn fill_with_bound_vars(self, debruijn: DebruijnIndex, starting_from: usize) -> Self {
+        self.fill(
+            (starting_from..)
+                .map(|idx| TyKind::BoundVar(BoundVar::new(debruijn, idx)).intern(&Interner)),
+        )
+    }
+
+    pub fn fill_with_unknown(self) -> Self {
+        self.fill(iter::repeat(TyKind::Unknown.intern(&Interner)))
+    }
+
+    pub fn fill(mut self, filler: impl Iterator<Item = impl CastTo<GenericArg>>) -> Self {
+        self.vec.extend(filler.take(self.remaining()).casted(&Interner));
+        assert_eq!(self.remaining(), 0);
+        self
+    }
+
+    pub fn use_parent_substs(mut self, parent_substs: &Substitution) -> Self {
+        assert!(self.vec.is_empty());
+        assert!(parent_substs.len(&Interner) <= self.param_count);
+        self.vec.extend(parent_substs.iter(&Interner).cloned());
+        self
+    }
+}
+
+impl TyBuilder<()> {
+    pub fn unit() -> Ty {
+        TyKind::Tuple(0, Substitution::empty(&Interner)).intern(&Interner)
+    }
+
+    pub fn fn_ptr(sig: CallableSig) -> Ty {
+        TyKind::Function(FnPointer {
+            num_args: sig.params().len(),
+            sig: FnSig { abi: (), safety: Safety::Safe, variadic: sig.is_varargs },
+            substs: Substitution::from_iter(&Interner, sig.params_and_return.iter().cloned()),
+        })
+        .intern(&Interner)
+    }
+
+    pub fn builtin(builtin: BuiltinType) -> Ty {
+        match builtin {
+            BuiltinType::Char => TyKind::Scalar(Scalar::Char).intern(&Interner),
+            BuiltinType::Bool => TyKind::Scalar(Scalar::Bool).intern(&Interner),
+            BuiltinType::Str => TyKind::Str.intern(&Interner),
+            BuiltinType::Int(t) => {
+                TyKind::Scalar(Scalar::Int(primitive::int_ty_from_builtin(t))).intern(&Interner)
+            }
+            BuiltinType::Uint(t) => {
+                TyKind::Scalar(Scalar::Uint(primitive::uint_ty_from_builtin(t))).intern(&Interner)
+            }
+            BuiltinType::Float(t) => {
+                TyKind::Scalar(Scalar::Float(primitive::float_ty_from_builtin(t))).intern(&Interner)
+            }
+        }
+    }
+
+    pub fn type_params_subst(db: &dyn HirDatabase, def: impl Into<GenericDefId>) -> Substitution {
+        let params = generics(db.upcast(), def.into());
+        params.type_params_subst(db)
+    }
+
+    pub fn subst_for_def(db: &dyn HirDatabase, def: impl Into<GenericDefId>) -> TyBuilder<()> {
+        let def = def.into();
+        let params = generics(db.upcast(), def);
+        let param_count = params.len();
+        TyBuilder::new((), param_count)
+    }
+
+    pub fn build(self) -> Substitution {
+        let ((), subst) = self.build_internal();
+        subst
+    }
+}
+
+impl TyBuilder<hir_def::AdtId> {
+    pub fn adt(db: &dyn HirDatabase, adt: hir_def::AdtId) -> TyBuilder<hir_def::AdtId> {
+        let generics = generics(db.upcast(), adt.into());
+        let param_count = generics.len();
+        TyBuilder::new(adt, param_count)
+    }
+
+    pub fn fill_with_defaults(
+        mut self,
+        db: &dyn HirDatabase,
+        mut fallback: impl FnMut() -> Ty,
+    ) -> Self {
+        let defaults = db.generic_defaults(self.data.into());
+        for default_ty in defaults.iter().skip(self.vec.len()) {
+            if default_ty.skip_binders().is_unknown() {
+                self.vec.push(fallback().cast(&Interner));
+            } else {
+                // each default can depend on the previous parameters
+                let subst_so_far = Substitution(self.vec.clone());
+                self.vec.push(default_ty.clone().subst(&subst_so_far).cast(&Interner));
+            }
+        }
+        self
+    }
+
+    pub fn build(self) -> Ty {
+        let (adt, subst) = self.build_internal();
+        TyKind::Adt(AdtId(adt), subst).intern(&Interner)
+    }
+}
+
+pub struct Tuple(usize);
+impl TyBuilder<Tuple> {
+    pub fn tuple(size: usize) -> TyBuilder<Tuple> {
+        TyBuilder::new(Tuple(size), size)
+    }
+
+    pub fn build(self) -> Ty {
+        let (Tuple(size), subst) = self.build_internal();
+        TyKind::Tuple(size, subst).intern(&Interner)
+    }
+}
+
+impl TyBuilder<TraitId> {
+    pub fn trait_ref(db: &dyn HirDatabase, trait_id: TraitId) -> TyBuilder<TraitId> {
+        let generics = generics(db.upcast(), trait_id.into());
+        let param_count = generics.len();
+        TyBuilder::new(trait_id, param_count)
+    }
+
+    pub fn build(self) -> TraitRef {
+        let (trait_id, substitution) = self.build_internal();
+        TraitRef { trait_id: to_chalk_trait_id(trait_id), substitution }
+    }
+}
+
+impl TyBuilder<TypeAliasId> {
+    pub fn assoc_type_projection(
+        db: &dyn HirDatabase,
+        type_alias: TypeAliasId,
+    ) -> TyBuilder<TypeAliasId> {
+        let generics = generics(db.upcast(), type_alias.into());
+        let param_count = generics.len();
+        TyBuilder::new(type_alias, param_count)
+    }
+
+    pub fn build(self) -> ProjectionTy {
+        let (type_alias, substitution) = self.build_internal();
+        ProjectionTy { associated_ty_id: to_assoc_type_id(type_alias), substitution }
+    }
+}
+
+impl<T: TypeWalk + HasInterner<Interner = Interner>> TyBuilder<Binders<T>> {
+    fn subst_binders(b: Binders<T>) -> Self {
+        let param_count = b.num_binders;
+        TyBuilder::new(b, param_count)
+    }
+
+    pub fn build(self) -> T {
+        let (b, subst) = self.build_internal();
+        b.subst(&subst)
+    }
+}
+
+impl TyBuilder<Binders<Ty>> {
+    pub fn def_ty(db: &dyn HirDatabase, def: TyDefId) -> TyBuilder<Binders<Ty>> {
+        TyBuilder::subst_binders(db.ty(def.into()))
+    }
+
+    pub fn impl_self_ty(db: &dyn HirDatabase, def: hir_def::ImplId) -> TyBuilder<Binders<Ty>> {
+        TyBuilder::subst_binders(db.impl_self_ty(def))
+    }
+
+    pub fn value_ty(db: &dyn HirDatabase, def: ValueTyDefId) -> TyBuilder<Binders<Ty>> {
+        TyBuilder::subst_binders(db.value_ty(def))
+    }
+}
diff --git a/crates/hir_ty/src/chalk_ext.rs b/crates/hir_ty/src/chalk_ext.rs
new file mode 100644
index 000000000..b7463366b
--- /dev/null
+++ b/crates/hir_ty/src/chalk_ext.rs
@@ -0,0 +1,13 @@
+//! Various extensions traits for Chalk types.
+
+use crate::{Interner, Ty, TyKind};
+
+pub trait TyExt {
+    fn is_unit(&self) -> bool;
+}
+
+impl TyExt for Ty {
+    fn is_unit(&self) -> bool {
+        matches!(self.kind(&Interner), TyKind::Tuple(0, _))
+    }
+}
diff --git a/crates/hir_ty/src/diagnostics/expr.rs b/crates/hir_ty/src/diagnostics/expr.rs
index ad1259b34..8169b759f 100644
--- a/crates/hir_ty/src/diagnostics/expr.rs
+++ b/crates/hir_ty/src/diagnostics/expr.rs
@@ -15,7 +15,7 @@ use crate::{
         MissingPatFields, RemoveThisSemicolon,
     },
     utils::variant_data,
-    AdtId, InferenceResult, Interner, Ty, TyKind,
+    AdtId, InferenceResult, Interner, TyExt, TyKind,
 };
 
 pub(crate) use hir_def::{
@@ -423,7 +423,7 @@ impl<'a, 'b> ExprValidator<'a, 'b> {
             None => return,
         };
 
-        if mismatch.actual != Ty::unit() || mismatch.expected != *possible_tail_ty {
+        if !mismatch.actual.is_unit() || mismatch.expected != *possible_tail_ty {
             return;
         }
 
diff --git a/crates/hir_ty/src/display.rs b/crates/hir_ty/src/display.rs
index 97f1092c6..385bd9405 100644
--- a/crates/hir_ty/src/display.rs
+++ b/crates/hir_ty/src/display.rs
@@ -19,7 +19,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, GenericArg, ImplTraitId, Interner, Lifetime, OpaqueTy,
-    ProjectionTy, QuantifiedWhereClause, Scalar, Substitution, TraitRef, Ty, TyKind, WhereClause,
+    ProjectionTy, QuantifiedWhereClause, Scalar, TraitRef, Ty, TyExt, TyKind, WhereClause,
 };
 
 pub struct HirFormatter<'a> {
@@ -423,7 +423,7 @@ impl HirDisplay for Ty {
                 f.write_joined(sig.params(), ", ")?;
                 write!(f, ")")?;
                 let ret = sig.ret();
-                if *ret != Ty::unit() {
+                if !ret.is_unit() {
                     let ret_display = ret.into_displayable(
                         f.db,
                         f.max_size,
@@ -591,7 +591,7 @@ impl HirDisplay for Ty {
                         write!(f, "{}", param_data.name.clone().unwrap_or_else(Name::missing))?
                     }
                     TypeParamProvenance::ArgumentImplTrait => {
-                        let substs = Substitution::type_params_for_generics(f.db, &generics);
+                        let substs = generics.type_params_subst(f.db);
                         let bounds = f
                             .db
                             .generic_predicates(id.parent)
@@ -663,7 +663,7 @@ impl HirDisplay for CallableSig {
         }
         write!(f, ")")?;
         let ret = self.ret();
-        if *ret != Ty::unit() {
+        if !ret.is_unit() {
             let ret_display =
                 ret.into_displayable(f.db, f.max_size, f.omit_verbose_types, f.display_target);
             write!(f, " -> {}", ret_display)?;
diff --git a/crates/hir_ty/src/infer.rs b/crates/hir_ty/src/infer.rs
index b871594bd..1b1d4458c 100644
--- a/crates/hir_ty/src/infer.rs
+++ b/crates/hir_ty/src/infer.rs
@@ -38,11 +38,11 @@ use syntax::SmolStr;
 
 use super::{
     traits::{DomainGoal, Guidance, Solution},
-    InEnvironment, ProjectionTy, Substitution, TraitEnvironment, TraitRef, Ty, TypeWalk,
+    InEnvironment, ProjectionTy, TraitEnvironment, TraitRef, Ty, TypeWalk,
 };
 use crate::{
     db::HirDatabase, infer::diagnostics::InferenceDiagnostic, lower::ImplTraitLoweringMode,
-    to_assoc_type_id, to_chalk_trait_id, AliasEq, AliasTy, Interner, TyKind,
+    to_assoc_type_id, AliasEq, AliasTy, Interner, TyBuilder, TyKind,
 };
 
 // This lint has a false positive here. See the link below for details.
@@ -409,16 +409,14 @@ impl<'a> InferenceContext<'a> {
                     _ => panic!("resolve_associated_type called with non-associated type"),
                 };
                 let ty = self.table.new_type_var();
-                let substs = Substitution::build_for_def(self.db, res_assoc_ty)
+                let trait_ref = TyBuilder::trait_ref(self.db, trait_)
                     .push(inner_ty)
                     .fill(params.iter().cloned())
                     .build();
-                let trait_ref =
-                    TraitRef { trait_id: to_chalk_trait_id(trait_), substitution: substs.clone() };
                 let alias_eq = AliasEq {
                     alias: AliasTy::Projection(ProjectionTy {
                         associated_ty_id: to_assoc_type_id(res_assoc_ty),
-                        substitution: substs,
+                        substitution: trait_ref.substitution.clone(),
                     }),
                     ty: ty.clone(),
                 };
@@ -489,7 +487,7 @@ impl<'a> InferenceContext<'a> {
             }
             TypeNs::SelfType(impl_id) => {
                 let generics = crate::utils::generics(self.db.upcast(), impl_id.into());
-                let substs = Substitution::type_params_for_generics(self.db, &generics);
+                let substs = generics.type_params_subst(self.db);
                 let ty = self.db.impl_self_ty(impl_id).subst(&substs);
                 match unresolved {
                     None => {
@@ -516,10 +514,9 @@ impl<'a> InferenceContext<'a> {
                 }
             }
             TypeNs::TypeAliasId(it) => {
-                let substs = Substitution::build_for_def(self.db, it)
+                let ty = TyBuilder::def_ty(self.db, it.into())
                     .fill(std::iter::repeat_with(|| self.table.new_type_var()))
                     .build();
-                let ty = self.db.ty(it.into()).subst(&substs);
                 let variant = ty_variant(&ty);
                 forbid_unresolved_segments((ty, variant), unresolved)
             }
diff --git a/crates/hir_ty/src/infer/coerce.rs b/crates/hir_ty/src/infer/coerce.rs
index d887e21a2..028a4d568 100644
--- a/crates/hir_ty/src/infer/coerce.rs
+++ b/crates/hir_ty/src/infer/coerce.rs
@@ -7,9 +7,7 @@
 use chalk_ir::{cast::Cast, Mutability, TyVariableKind};
 use hir_def::lang_item::LangItemTarget;
 
-use crate::{
-    autoderef, to_chalk_trait_id, traits::Solution, Interner, Substitution, TraitRef, Ty, TyKind,
-};
+use crate::{autoderef, traits::Solution, Interner, Ty, TyBuilder, TyKind};
 
 use super::{InEnvironment, InferenceContext};
 
@@ -44,8 +42,8 @@ impl<'a> InferenceContext<'a> {
                 // https://github.com/rust-lang/rust/blob/7b805396bf46dce972692a6846ce2ad8481c5f85/src/librustc_typeck/check/coercion.rs#L877-L916
                 let sig1 = ty1.callable_sig(self.db).expect("FnDef without callable sig");
                 let sig2 = ty2.callable_sig(self.db).expect("FnDef without callable sig");
-                let ptr_ty1 = Ty::fn_ptr(sig1);
-                let ptr_ty2 = Ty::fn_ptr(sig2);
+                let ptr_ty1 = TyBuilder::fn_ptr(sig1);
+                let ptr_ty2 = TyBuilder::fn_ptr(sig2);
                 self.coerce_merge_branch(&ptr_ty1, &ptr_ty2)
             } else {
                 cov_mark::hit!(coerce_merge_fail_fallback);
@@ -95,7 +93,7 @@ impl<'a> InferenceContext<'a> {
             (TyKind::FnDef(..), TyKind::Function { .. }) => match from_ty.callable_sig(self.db) {
                 None => return false,
                 Some(sig) => {
-                    from_ty = Ty::fn_ptr(sig);
+                    from_ty = TyBuilder::fn_ptr(sig);
                 }
             },
 
@@ -130,18 +128,15 @@ impl<'a> InferenceContext<'a> {
             _ => return None,
         };
 
-        let generic_params = crate::utils::generics(self.db.upcast(), coerce_unsized_trait.into());
-        if generic_params.len() != 2 {
-            // The CoerceUnsized trait should have two generic params: Self and T.
-            return None;
-        }
+        let trait_ref = {
+            let b = TyBuilder::trait_ref(self.db, coerce_unsized_trait);
+            if b.remaining() != 2 {
+                // The CoerceUnsized trait should have two generic params: Self and T.
+                return None;
+            }
+            b.push(from_ty.clone()).push(to_ty.clone()).build()
+        };
 
-        let substs = Substitution::build_for_generics(&generic_params)
-            .push(from_ty.clone())
-            .push(to_ty.clone())
-            .build();
-        let trait_ref =
-            TraitRef { trait_id: to_chalk_trait_id(coerce_unsized_trait), substitution: substs };
         let goal = InEnvironment::new(self.trait_env.env.clone(), trait_ref.cast(&Interner));
 
         let canonicalizer = self.canonicalizer();
diff --git a/crates/hir_ty/src/infer/expr.rs b/crates/hir_ty/src/infer/expr.rs
index dd3914ec3..c584a2c08 100644
--- a/crates/hir_ty/src/infer/expr.rs
+++ b/crates/hir_ty/src/infer/expr.rs
@@ -19,11 +19,11 @@ use crate::{
     lower::lower_to_chalk_mutability,
     method_resolution, op,
     primitive::{self, UintTy},
-    to_assoc_type_id, to_chalk_trait_id,
+    to_chalk_trait_id,
     traits::{chalk::from_chalk, FnTrait, InEnvironment},
     utils::{generics, variant_data, Generics},
-    AdtId, Binders, CallableDefId, DomainGoal, FnPointer, FnSig, Interner, Rawness, Scalar,
-    Substitution, TraitRef, Ty, TyKind,
+    AdtId, Binders, CallableDefId, FnPointer, FnSig, Interner, Rawness, Scalar, Substitution,
+    TraitRef, Ty, TyBuilder, TyKind,
 };
 
 use super::{
@@ -73,38 +73,33 @@ impl<'a> InferenceContext<'a> {
         let fn_once_trait = FnTrait::FnOnce.get_id(self.db, krate)?;
         let output_assoc_type =
             self.db.trait_data(fn_once_trait).associated_type_by_name(&name![Output])?;
-        let generic_params = generics(self.db.upcast(), fn_once_trait.into());
-        if generic_params.len() != 2 {
-            return None;
-        }
 
-        let mut param_builder = Substitution::builder(num_args);
         let mut arg_tys = vec![];
-        for _ in 0..num_args {
-            let arg = self.table.new_type_var();
-            param_builder = param_builder.push(arg.clone());
-            arg_tys.push(arg);
-        }
-        let parameters = param_builder.build();
-        let arg_ty = TyKind::Tuple(num_args, parameters).intern(&Interner);
-        let substs =
-            Substitution::build_for_generics(&generic_params).push(ty.clone()).push(arg_ty).build();
+        let arg_ty = TyBuilder::tuple(num_args)
+            .fill(repeat_with(|| {
+                let arg = self.table.new_type_var();
+                arg_tys.push(arg.clone());
+                arg
+            }))
+            .build();
+
+        let projection = {
+            let b = TyBuilder::assoc_type_projection(self.db, output_assoc_type);
+            if b.remaining() != 2 {
+                return None;
+            }
+            b.push(ty.clone()).push(arg_ty).build()
+        };
 
         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 {
-            goal: implements_fn_trait.clone(),
+        let obligation = InEnvironment {
+            goal: projection.trait_ref(self.db).cast(&Interner),
             environment: trait_env,
-        });
-        if self.db.trait_solve(krate, goal.value).is_some() {
-            self.push_obligation(implements_fn_trait);
-            let output_proj_ty = crate::ProjectionTy {
-                associated_ty_id: to_assoc_type_id(output_assoc_type),
-                substitution: substs,
-            };
-            let return_ty = self.normalize_projection_ty(output_proj_ty);
+        };
+        let canonical = self.canonicalizer().canonicalize_obligation(obligation.clone());
+        if self.db.trait_solve(krate, canonical.value).is_some() {
+            self.push_obligation(obligation.goal);
+            let return_ty = self.normalize_projection_ty(projection);
             Some((arg_tys, return_ty))
         } else {
             None
@@ -138,7 +133,7 @@ impl<'a> InferenceContext<'a> {
                 both_arms_diverge &= mem::replace(&mut self.diverges, Diverges::Maybe);
                 let else_ty = match else_branch {
                     Some(else_branch) => self.infer_expr_inner(*else_branch, &expected),
-                    None => Ty::unit(),
+                    None => TyBuilder::unit(),
                 };
                 both_arms_diverge &= self.diverges;
 
@@ -193,7 +188,7 @@ impl<'a> InferenceContext<'a> {
                     break_ty: self.table.new_type_var(),
                     label: label.map(|label| self.body[label].name.clone()),
                 });
-                self.infer_expr(*body, &Expectation::has_type(Ty::unit()));
+                self.infer_expr(*body, &Expectation::has_type(TyBuilder::unit()));
 
                 let ctxt = self.breakables.pop().expect("breakable stack broken");
                 if ctxt.may_break {
@@ -217,11 +212,11 @@ impl<'a> InferenceContext<'a> {
                     *condition,
                     &Expectation::has_type(TyKind::Scalar(Scalar::Bool).intern(&Interner)),
                 );
-                self.infer_expr(*body, &Expectation::has_type(Ty::unit()));
+                self.infer_expr(*body, &Expectation::has_type(TyBuilder::unit()));
                 let _ctxt = self.breakables.pop().expect("breakable stack broken");
                 // the body may not run, so it diverging doesn't mean we diverge
                 self.diverges = Diverges::Maybe;
-                Ty::unit()
+                TyBuilder::unit()
             }
             Expr::For { iterable, body, pat, label } => {
                 let iterable_ty = self.infer_expr(*iterable, &Expectation::none());
@@ -236,11 +231,11 @@ impl<'a> InferenceContext<'a> {
 
                 self.infer_pat(*pat, &pat_ty, BindingMode::default());
 
-                self.infer_expr(*body, &Expectation::has_type(Ty::unit()));
+                self.infer_expr(*body, &Expectation::has_type(TyBuilder::unit()));
                 let _ctxt = self.breakables.pop().expect("breakable stack broken");
                 // the body may not run, so it diverging doesn't mean we diverge
                 self.diverges = Diverges::Maybe;
-                Ty::unit()
+                TyBuilder::unit()
             }
             Expr::Lambda { body, args, ret_type, arg_types } => {
                 assert_eq!(args.len(), arg_types.len());
@@ -360,7 +355,7 @@ impl<'a> InferenceContext<'a> {
                 let val_ty = if let Some(expr) = expr {
                     self.infer_expr(*expr, &Expectation::none())
                 } else {
-                    Ty::unit()
+                    TyBuilder::unit()
                 };
 
                 let last_ty =
@@ -386,7 +381,7 @@ impl<'a> InferenceContext<'a> {
                 if let Some(expr) = expr {
                     self.infer_expr_coerce(*expr, &Expectation::has_type(self.return_ty.clone()));
                 } else {
-                    let unit = Ty::unit();
+                    let unit = TyBuilder::unit();
                     self.coerce(&unit, &self.return_ty.clone());
                 }
                 TyKind::Never.intern(&Interner)
@@ -539,17 +534,10 @@ impl<'a> InferenceContext<'a> {
             Expr::Box { expr } => {
                 let inner_ty = self.infer_expr_inner(*expr, &Expectation::none());
                 if let Some(box_) = self.resolve_boxed_box() {
-                    let mut sb =
-                        Substitution::build_for_generics(&generics(self.db.upcast(), box_.into()));
-                    sb = sb.push(inner_ty);
-                    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());
-                        }
-                        _ => (),
-                    }
-                    sb = sb.fill(repeat_with(|| self.table.new_type_var()));
-                    Ty::adt_ty(box_, sb.build())
+                    TyBuilder::adt(self.db, box_)
+                        .push(inner_ty)
+                        .fill_with_defaults(self.db, || self.table.new_type_var())
+                        .build()
                 } else {
                     self.err_ty()
                 }
@@ -639,31 +627,31 @@ impl<'a> InferenceContext<'a> {
                 let rhs_ty = rhs.map(|e| self.infer_expr(e, &rhs_expect));
                 match (range_type, lhs_ty, rhs_ty) {
                     (RangeOp::Exclusive, None, None) => match self.resolve_range_full() {
-                        Some(adt) => Ty::adt_ty(adt, Substitution::empty(&Interner)),
+                        Some(adt) => TyBuilder::adt(self.db, adt).build(),
                         None => self.err_ty(),
                     },
                     (RangeOp::Exclusive, None, Some(ty)) => match self.resolve_range_to() {
-                        Some(adt) => Ty::adt_ty(adt, Substitution::single(ty)),
+                        Some(adt) => TyBuilder::adt(self.db, adt).push(ty).build(),
                         None => self.err_ty(),
                     },
                     (RangeOp::Inclusive, None, Some(ty)) => {
                         match self.resolve_range_to_inclusive() {
-                            Some(adt) => Ty::adt_ty(adt, Substitution::single(ty)),
+                            Some(adt) => TyBuilder::adt(self.db, adt).push(ty).build(),
                             None => self.err_ty(),
                         }
                     }
                     (RangeOp::Exclusive, Some(_), Some(ty)) => match self.resolve_range() {
-                        Some(adt) => Ty::adt_ty(adt, Substitution::single(ty)),
+                        Some(adt) => TyBuilder::adt(self.db, adt).push(ty).build(),
                         None => self.err_ty(),
                     },
                     (RangeOp::Inclusive, Some(_), Some(ty)) => {
                         match self.resolve_range_inclusive() {
-                            Some(adt) => Ty::adt_ty(adt, Substitution::single(ty)),
+                            Some(adt) => TyBuilder::adt(self.db, adt).push(ty).build(),
                             None => self.err_ty(),
                         }
                     }
                     (RangeOp::Exclusive, Some(ty), None) => match self.resolve_range_from() {
-                        Some(adt) => Ty::adt_ty(adt, Substitution::single(ty)),
+                        Some(adt) => TyBuilder::adt(self.db, adt).push(ty).build(),
                         None => self.err_ty(),
                     },
                     (RangeOp::Inclusive, _, None) => self.err_ty(),
@@ -828,8 +816,8 @@ impl<'a> InferenceContext<'a> {
                 // we don't even make an attempt at coercion
                 self.table.new_maybe_never_var()
             } else {
-                self.coerce(&Ty::unit(), &expected.coercion_target());
-                Ty::unit()
+                self.coerce(&TyBuilder::unit(), &expected.coercion_target());
+                TyBuilder::unit()
             }
         };
         ty
diff --git a/crates/hir_ty/src/infer/pat.rs b/crates/hir_ty/src/infer/pat.rs
index 10df8d8cb..5b70d5e5a 100644
--- a/crates/hir_ty/src/infer/pat.rs
+++ b/crates/hir_ty/src/infer/pat.rs
@@ -13,9 +13,8 @@ use hir_expand::name::Name;
 
 use super::{BindingMode, Expectation, InferenceContext};
 use crate::{
-    lower::lower_to_chalk_mutability,
-    utils::{generics, variant_data},
-    Interner, Substitution, Ty, TyKind,
+    lower::lower_to_chalk_mutability, utils::variant_data, Interner, Substitution, Ty, TyBuilder,
+    TyKind,
 };
 
 impl<'a> InferenceContext<'a> {
@@ -246,23 +245,12 @@ impl<'a> InferenceContext<'a> {
                     };
 
                     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(),
-                            },
-                        });
+                    let mut b = TyBuilder::adt(self.db, box_adt).push(inner_ty);
+
+                    if let Some(alloc_ty) = alloc_ty {
+                        b = b.push(alloc_ty);
                     }
-                    Ty::adt_ty(box_adt, sb.build())
+                    b.fill_with_defaults(self.db, || self.table.new_type_var()).build()
                 }
                 None => self.err_ty(),
             },
diff --git a/crates/hir_ty/src/infer/path.rs b/crates/hir_ty/src/infer/path.rs
index 1ba15f737..671ea355f 100644
--- a/crates/hir_ty/src/infer/path.rs
+++ b/crates/hir_ty/src/infer/path.rs
@@ -10,9 +10,7 @@ use hir_def::{
 };
 use hir_expand::name::Name;
 
-use crate::{
-    method_resolution, to_chalk_trait_id, Interner, Substitution, Ty, TyKind, ValueTyDefId,
-};
+use crate::{method_resolution, Interner, Substitution, Ty, TyBuilder, TyKind, ValueTyDefId};
 
 use super::{ExprOrPatId, InferenceContext, TraitRef};
 
@@ -82,7 +80,7 @@ impl<'a> InferenceContext<'a> {
             }
             ValueNs::ImplSelf(impl_id) => {
                 let generics = crate::utils::generics(self.db.upcast(), impl_id.into());
-                let substs = Substitution::type_params_for_generics(self.db, &generics);
+                let substs = generics.type_params_subst(self.db);
                 let ty = self.db.impl_self_ty(impl_id).subst(&substs);
                 if let Some((AdtId::StructId(struct_id), substs)) = ty.as_adt() {
                     let ty = self.db.value_ty(struct_id.into()).subst(&substs);
@@ -95,16 +93,13 @@ impl<'a> InferenceContext<'a> {
             ValueNs::GenericParam(it) => return Some(self.db.const_param_ty(it)),
         };
 
-        let ty = self.db.value_ty(typable);
-        // self_subst is just for the parent
         let parent_substs = self_subst.unwrap_or_else(|| Substitution::empty(&Interner));
         let ctx = crate::lower::TyLoweringContext::new(self.db, &self.resolver);
         let substs = ctx.substs_from_path(path, typable, true);
-        let full_substs = Substitution::builder(substs.len(&Interner))
+        let ty = TyBuilder::value_ty(self.db, typable)
             .use_parent_substs(&parent_substs)
             .fill(substs.interned(&Interner)[parent_substs.len(&Interner)..].iter().cloned())
             .build();
-        let ty = ty.subst(&full_substs);
         Some(ty)
     }
 
@@ -245,7 +240,7 @@ impl<'a> InferenceContext<'a> {
                 };
                 let substs = match container {
                     AssocContainerId::ImplId(impl_id) => {
-                        let impl_substs = Substitution::build_for_def(self.db, impl_id)
+                        let impl_substs = TyBuilder::subst_for_def(self.db, impl_id)
                             .fill(iter::repeat_with(|| self.table.new_type_var()))
                             .build();
                         let impl_self_ty = self.db.impl_self_ty(impl_id).subst(&impl_substs);
@@ -254,18 +249,12 @@ impl<'a> InferenceContext<'a> {
                     }
                     AssocContainerId::TraitId(trait_) => {
                         // we're picking this method
-                        let trait_substs = Substitution::build_for_def(self.db, trait_)
+                        let trait_ref = TyBuilder::trait_ref(self.db, trait_)
                             .push(ty.clone())
                             .fill(std::iter::repeat_with(|| self.table.new_type_var()))
                             .build();
-                        self.push_obligation(
-                            TraitRef {
-                                trait_id: to_chalk_trait_id(trait_),
-                                substitution: trait_substs.clone(),
-                            }
-                            .cast(&Interner),
-                        );
-                        Some(trait_substs)
+                        self.push_obligation(trait_ref.clone().cast(&Interner));
+                        Some(trait_ref.substitution)
                     }
                     AssocContainerId::ModuleId(_) => None,
                 };
diff --git a/crates/hir_ty/src/infer/unify.rs b/crates/hir_ty/src/infer/unify.rs
index d2496db3b..a04b935ef 100644
--- a/crates/hir_ty/src/infer/unify.rs
+++ b/crates/hir_ty/src/infer/unify.rs
@@ -186,14 +186,11 @@ pub(crate) fn unify(tys: &Canonical<(Ty, Ty)>) -> Option<Substitution> {
             );
         }
     }
-    Some(
-        Substitution::builder(tys.binders.len(&Interner))
-            .fill(
-                vars.iter(&Interner)
-                    .map(|v| table.resolve_ty_completely(v.assert_ty_ref(&Interner).clone())),
-            )
-            .build(),
-    )
+    Some(Substitution::from_iter(
+        &Interner,
+        vars.iter(&Interner)
+            .map(|v| table.resolve_ty_completely(v.assert_ty_ref(&Interner).clone())),
+    ))
 }
 
 #[derive(Clone, Debug)]
diff --git a/crates/hir_ty/src/lib.rs b/crates/hir_ty/src/lib.rs
index 4c3d904bf..a8c87eadf 100644
--- a/crates/hir_ty/src/lib.rs
+++ b/crates/hir_ty/src/lib.rs
@@ -14,6 +14,8 @@ mod lower;
 pub(crate) mod infer;
 pub(crate) mod utils;
 mod chalk_cast;
+mod chalk_ext;
+mod builder;
 
 pub mod display;
 pub mod db;
@@ -24,24 +26,27 @@ mod tests;
 #[cfg(test)]
 mod test_db;
 
-use std::{iter, mem, sync::Arc};
+use std::{mem, sync::Arc};
 
-use base_db::salsa;
 use chalk_ir::cast::{CastTo, Caster};
-use hir_def::{
-    builtin_type::BuiltinType, expr::ExprId, type_ref::Rawness, AssocContainerId, FunctionId,
-    GenericDefId, HasModule, LifetimeParamId, Lookup, TraitId, TypeAliasId, TypeParamId,
-};
 use itertools::Itertools;
 use smallvec::SmallVec;
 
+use base_db::salsa;
+use hir_def::{
+    expr::ExprId, type_ref::Rawness, AssocContainerId, FunctionId, GenericDefId, HasModule,
+    LifetimeParamId, Lookup, TraitId, TypeAliasId, TypeParamId,
+};
+
 use crate::{
     db::HirDatabase,
     display::HirDisplay,
-    utils::{generics, make_mut_slice, Generics},
+    utils::{generics, make_mut_slice},
 };
 
 pub use autoderef::autoderef;
+pub use builder::TyBuilder;
+pub use chalk_ext::TyExt;
 pub use infer::{could_unify, InferenceResult, InferenceVar};
 pub use lower::{
     associated_type_shorthand_candidates, callable_item_sig, CallableDefId, ImplTraitLoweringMode,
@@ -457,51 +462,6 @@ impl Substitution {
     ) -> Self {
         Substitution(elements.into_iter().casted(interner).collect())
     }
-
-    /// Return Substs that replace each parameter by itself (i.e. `Ty::Param`).
-    pub(crate) fn type_params_for_generics(
-        db: &dyn HirDatabase,
-        generic_params: &Generics,
-    ) -> Substitution {
-        Substitution::from_iter(
-            &Interner,
-            generic_params
-                .iter()
-                .map(|(id, _)| TyKind::Placeholder(to_placeholder_idx(db, id)).intern(&Interner)),
-        )
-    }
-
-    /// Return Substs that replace each parameter by itself (i.e. `Ty::Param`).
-    pub fn type_params(db: &dyn HirDatabase, def: impl Into<GenericDefId>) -> Substitution {
-        let params = generics(db.upcast(), def.into());
-        Substitution::type_params_for_generics(db, &params)
-    }
-
-    /// Return Substs that replace each parameter by a bound variable.
-    pub(crate) fn bound_vars(generic_params: &Generics, debruijn: DebruijnIndex) -> Substitution {
-        Substitution::from_iter(
-            &Interner,
-            generic_params
-                .iter()
-                .enumerate()
-                .map(|(idx, _)| TyKind::BoundVar(BoundVar::new(debruijn, idx)).intern(&Interner)),
-        )
-    }
-
-    pub fn build_for_def(db: &dyn HirDatabase, def: impl Into<GenericDefId>) -> SubstsBuilder {
-        let def = def.into();
-        let params = generics(db.upcast(), def);
-        let param_count = params.len();
-        Substitution::builder(param_count)
-    }
-
-    pub(crate) fn build_for_generics(generic_params: &Generics) -> SubstsBuilder {
-        Substitution::builder(generic_params.len())
-    }
-
-    fn builder(param_count: usize) -> SubstsBuilder {
-        SubstsBuilder { vec: Vec::with_capacity(param_count), param_count }
-    }
 }
 
 /// Return an index of a parameter in the generic type parameter list by it's id.
@@ -509,52 +469,6 @@ pub fn param_idx(db: &dyn HirDatabase, id: TypeParamId) -> Option<usize> {
     generics(db.upcast(), id.parent).param_idx(id)
 }
 
-#[derive(Debug, Clone)]
-pub struct SubstsBuilder {
-    vec: Vec<GenericArg>,
-    param_count: usize,
-}
-
-impl SubstsBuilder {
-    pub fn build(self) -> Substitution {
-        assert_eq!(self.vec.len(), self.param_count);
-        Substitution::from_iter(&Interner, self.vec)
-    }
-
-    pub fn push(mut self, ty: impl CastTo<GenericArg>) -> Self {
-        self.vec.push(ty.cast(&Interner));
-        self
-    }
-
-    fn remaining(&self) -> usize {
-        self.param_count - self.vec.len()
-    }
-
-    pub fn fill_with_bound_vars(self, debruijn: DebruijnIndex, starting_from: usize) -> Self {
-        self.fill(
-            (starting_from..)
-                .map(|idx| TyKind::BoundVar(BoundVar::new(debruijn, idx)).intern(&Interner)),
-        )
-    }
-
-    pub fn fill_with_unknown(self) -> Self {
-        self.fill(iter::repeat(TyKind::Unknown.intern(&Interner)))
-    }
-
-    pub fn fill(mut self, filler: impl Iterator<Item = impl CastTo<GenericArg>>) -> Self {
-        self.vec.extend(filler.take(self.remaining()).casted(&Interner));
-        assert_eq!(self.remaining(), 0);
-        self
-    }
-
-    pub fn use_parent_substs(mut self, parent_substs: &Substitution) -> Self {
-        assert!(self.vec.is_empty());
-        assert!(parent_substs.len(&Interner) <= self.param_count);
-        self.vec.extend(parent_substs.iter(&Interner).cloned());
-        self
-    }
-}
-
 #[derive(Copy, Clone, PartialEq, Eq, Debug, Hash)]
 pub struct Binders<T> {
     pub num_binders: usize,
@@ -760,7 +674,7 @@ impl CallableSig {
 
     pub fn from_fn_ptr(fn_ptr: &FnPointer) -> CallableSig {
         CallableSig {
-            // FIXME: what to do about lifetime params?
+            // FIXME: what to do about lifetime params? -> return PolyFnSig
             params_and_return: fn_ptr
                 .substs
                 .clone()
@@ -773,16 +687,6 @@ impl CallableSig {
         }
     }
 
-    pub fn from_substs(substs: &Substitution) -> CallableSig {
-        CallableSig {
-            params_and_return: substs
-                .iter(&Interner)
-                .map(|arg| arg.assert_ty_ref(&Interner).clone())
-                .collect(),
-            is_varargs: false,
-        }
-    }
-
     pub fn params(&self) -> &[Ty] {
         &self.params_and_return[0..self.params_and_return.len() - 1]
     }
@@ -811,40 +715,6 @@ impl TypeWalk for CallableSig {
 }
 
 impl Ty {
-    pub fn unit() -> Self {
-        TyKind::Tuple(0, Substitution::empty(&Interner)).intern(&Interner)
-    }
-
-    pub fn adt_ty(adt: hir_def::AdtId, substs: Substitution) -> Ty {
-        TyKind::Adt(AdtId(adt), substs).intern(&Interner)
-    }
-
-    pub fn fn_ptr(sig: CallableSig) -> Self {
-        TyKind::Function(FnPointer {
-            num_args: sig.params().len(),
-            sig: FnSig { abi: (), safety: Safety::Safe, variadic: sig.is_varargs },
-            substs: Substitution::from_iter(&Interner, sig.params_and_return.iter().cloned()),
-        })
-        .intern(&Interner)
-    }
-
-    pub fn builtin(builtin: BuiltinType) -> Self {
-        match builtin {
-            BuiltinType::Char => TyKind::Scalar(Scalar::Char).intern(&Interner),
-            BuiltinType::Bool => TyKind::Scalar(Scalar::Bool).intern(&Interner),
-            BuiltinType::Str => TyKind::Str.intern(&Interner),
-            BuiltinType::Int(t) => {
-                TyKind::Scalar(Scalar::Int(primitive::int_ty_from_builtin(t))).intern(&Interner)
-            }
-            BuiltinType::Uint(t) => {
-                TyKind::Scalar(Scalar::Uint(primitive::uint_ty_from_builtin(t))).intern(&Interner)
-            }
-            BuiltinType::Float(t) => {
-                TyKind::Scalar(Scalar::Float(primitive::float_ty_from_builtin(t))).intern(&Interner)
-            }
-        }
-    }
-
     pub fn as_reference(&self) -> Option<(&Ty, Mutability)> {
         match self.kind(&Interner) {
             TyKind::Ref(mutability, ty) => Some((ty, *mutability)),
@@ -1068,7 +938,7 @@ impl Ty {
                 let param_data = &generic_params.types[id.local_id];
                 match param_data.provenance {
                     hir_def::generics::TypeParamProvenance::ArgumentImplTrait => {
-                        let substs = Substitution::type_params(db, id.parent);
+                        let substs = TyBuilder::type_params_subst(db, id.parent);
                         let predicates = db
                             .generic_predicates(id.parent)
                             .into_iter()
diff --git a/crates/hir_ty/src/lower.rs b/crates/hir_ty/src/lower.rs
index e60d7c730..214655807 100644
--- a/crates/hir_ty/src/lower.rs
+++ b/crates/hir_ty/src/lower.rs
@@ -36,7 +36,7 @@ use crate::{
     AliasEq, AliasTy, Binders, BoundVar, CallableSig, DebruijnIndex, DynTy, FnPointer, FnSig,
     ImplTraitId, OpaqueTy, PolyFnSig, ProjectionTy, QuantifiedWhereClause, QuantifiedWhereClauses,
     ReturnTypeImplTrait, ReturnTypeImplTraits, Substitution, TraitEnvironment, TraitRef, Ty,
-    TyKind, TypeWalk, WhereClause,
+    TyBuilder, TyKind, TypeWalk, WhereClause,
 };
 
 #[derive(Debug)]
@@ -234,7 +234,7 @@ impl<'a> TyLoweringContext<'a> {
                         let impl_trait_id = ImplTraitId::ReturnTypeImplTrait(func, idx);
                         let opaque_ty_id = self.db.intern_impl_trait_id(impl_trait_id).into();
                         let generics = generics(self.db.upcast(), func.into());
-                        let parameters = Substitution::bound_vars(&generics, self.in_binders);
+                        let parameters = generics.bound_vars_subst(self.in_binders);
                         TyKind::Alias(AliasTy::Opaque(OpaqueTy {
                             opaque_ty_id,
                             substitution: parameters,
@@ -411,24 +411,16 @@ impl<'a> TyLoweringContext<'a> {
             TypeNs::SelfType(impl_id) => {
                 let generics = generics(self.db.upcast(), impl_id.into());
                 let substs = match self.type_param_mode {
-                    TypeParamLoweringMode::Placeholder => {
-                        Substitution::type_params_for_generics(self.db, &generics)
-                    }
-                    TypeParamLoweringMode::Variable => {
-                        Substitution::bound_vars(&generics, self.in_binders)
-                    }
+                    TypeParamLoweringMode::Placeholder => generics.type_params_subst(self.db),
+                    TypeParamLoweringMode::Variable => generics.bound_vars_subst(self.in_binders),
                 };
                 self.db.impl_self_ty(impl_id).subst(&substs)
             }
             TypeNs::AdtSelfType(adt) => {
                 let generics = generics(self.db.upcast(), adt.into());
                 let substs = match self.type_param_mode {
-                    TypeParamLoweringMode::Placeholder => {
-                        Substitution::type_params_for_generics(self.db, &generics)
-                    }
-                    TypeParamLoweringMode::Variable => {
-                        Substitution::bound_vars(&generics, self.in_binders)
-                    }
+                    TypeParamLoweringMode::Placeholder => generics.type_params_subst(self.db),
+                    TypeParamLoweringMode::Variable => generics.bound_vars_subst(self.in_binders),
                 };
                 self.db.ty(adt.into()).subst(&substs)
             }
@@ -478,12 +470,13 @@ impl<'a> TyLoweringContext<'a> {
                             TypeParamLoweringMode::Placeholder => {
                                 // if we're lowering to placeholders, we have to put
                                 // them in now
-                                let s = Substitution::type_params(
-                                    self.db,
+                                let generics = generics(
+                                    self.db.upcast(),
                                     self.resolver.generic_def().expect(
                                         "there should be generics if there's a generic param",
                                     ),
                                 );
+                                let s = generics.type_params_subst(self.db);
                                 t.substitution.clone().subst_bound_vars(&s)
                             }
                             TypeParamLoweringMode::Variable => t.substitution.clone(),
@@ -860,10 +853,9 @@ pub fn associated_type_shorthand_candidates<R>(
                 if generics.params.types[param_id.local_id].provenance
                     == TypeParamProvenance::TraitSelf
                 {
-                    let trait_ref = TraitRef {
-                        trait_id: to_chalk_trait_id(trait_id),
-                        substitution: Substitution::bound_vars(&generics, DebruijnIndex::INNERMOST),
-                    };
+                    let trait_ref = TyBuilder::trait_ref(db, trait_id)
+                        .fill_with_bound_vars(DebruijnIndex::INNERMOST, 0)
+                        .build();
                     return search(trait_ref);
                 }
             }
@@ -972,7 +964,7 @@ pub(crate) fn trait_environment_query(
         // function default implementations (and hypothetical code
         // inside consts or type aliases)
         cov_mark::hit!(trait_self_implements_self);
-        let substs = Substitution::type_params(db, trait_id);
+        let substs = TyBuilder::type_params_subst(db, trait_id);
         let trait_ref = TraitRef { trait_id: to_chalk_trait_id(trait_id), substitution: substs };
         let pred = WhereClause::Implemented(trait_ref);
         let program_clause: chalk_ir::ProgramClause<Interner> = pred.to_chalk(db).cast(&Interner);
@@ -1061,7 +1053,7 @@ fn fn_sig_for_fn(db: &dyn HirDatabase, def: FunctionId) -> PolyFnSig {
 /// function body.
 fn type_for_fn(db: &dyn HirDatabase, def: FunctionId) -> Binders<Ty> {
     let generics = generics(db.upcast(), def.into());
-    let substs = Substitution::bound_vars(&generics, DebruijnIndex::INNERMOST);
+    let substs = generics.bound_vars_subst(DebruijnIndex::INNERMOST);
     Binders::new(
         substs.len(&Interner),
         TyKind::FnDef(CallableDefId::FunctionId(def).to_chalk(db), substs).intern(&Interner),
@@ -1106,7 +1098,7 @@ fn type_for_struct_constructor(db: &dyn HirDatabase, def: StructId) -> Binders<T
         return type_for_adt(db, def.into());
     }
     let generics = generics(db.upcast(), def.into());
-    let substs = Substitution::bound_vars(&generics, DebruijnIndex::INNERMOST);
+    let substs = generics.bound_vars_subst(DebruijnIndex::INNERMOST);
     Binders::new(
         substs.len(&Interner),
         TyKind::FnDef(CallableDefId::StructId(def).to_chalk(db), substs).intern(&Interner),
@@ -1133,7 +1125,7 @@ fn type_for_enum_variant_constructor(db: &dyn HirDatabase, def: EnumVariantId) -
         return type_for_adt(db, def.parent.into());
     }
     let generics = generics(db.upcast(), def.parent.into());
-    let substs = Substitution::bound_vars(&generics, DebruijnIndex::INNERMOST);
+    let substs = generics.bound_vars_subst(DebruijnIndex::INNERMOST);
     Binders::new(
         substs.len(&Interner),
         TyKind::FnDef(CallableDefId::EnumVariantId(def).to_chalk(db), substs).intern(&Interner),
@@ -1141,9 +1133,10 @@ fn type_for_enum_variant_constructor(db: &dyn HirDatabase, def: EnumVariantId) -
 }
 
 fn type_for_adt(db: &dyn HirDatabase, adt: AdtId) -> Binders<Ty> {
-    let generics = generics(db.upcast(), adt.into());
-    let substs = Substitution::bound_vars(&generics, DebruijnIndex::INNERMOST);
-    Binders::new(substs.len(&Interner), Ty::adt_ty(adt, substs))
+    let b = TyBuilder::adt(db, adt);
+    let num_binders = b.remaining();
+    let ty = b.fill_with_bound_vars(DebruijnIndex::INNERMOST, 0).build();
+    Binders::new(num_binders, ty)
 }
 
 fn type_for_type_alias(db: &dyn HirDatabase, t: TypeAliasId) -> Binders<Ty> {
@@ -1215,7 +1208,7 @@ impl_from!(FunctionId, StructId, UnionId, EnumVariantId, ConstId, StaticId for V
 /// namespace.
 pub(crate) fn ty_query(db: &dyn HirDatabase, def: TyDefId) -> Binders<Ty> {
     match def {
-        TyDefId::BuiltinType(it) => Binders::new(0, Ty::builtin(it)),
+        TyDefId::BuiltinType(it) => Binders::new(0, TyBuilder::builtin(it)),
         TyDefId::AdtId(it) => type_for_adt(db, it),
         TyDefId::TypeAliasId(it) => type_for_type_alias(db, it),
     }
diff --git a/crates/hir_ty/src/method_resolution.rs b/crates/hir_ty/src/method_resolution.rs
index c093fce20..a76586f0c 100644
--- a/crates/hir_ty/src/method_resolution.rs
+++ b/crates/hir_ty/src/method_resolution.rs
@@ -19,10 +19,9 @@ use crate::{
     db::HirDatabase,
     from_foreign_def_id,
     primitive::{self, FloatTy, IntTy, UintTy},
-    to_chalk_trait_id,
     utils::all_super_traits,
     AdtId, Canonical, CanonicalVarKinds, DebruijnIndex, FnPointer, FnSig, ForeignDefId,
-    InEnvironment, Interner, Scalar, Substitution, TraitEnvironment, TraitRef, Ty, TyKind,
+    InEnvironment, Interner, Scalar, Substitution, TraitEnvironment, Ty, TyBuilder, TyKind,
     TypeWalk,
 };
 
@@ -710,7 +709,7 @@ 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 vars = Substitution::build_for_def(db, impl_id)
+    let vars = TyBuilder::subst_for_def(db, impl_id)
         .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);
@@ -761,13 +760,13 @@ fn transform_receiver_ty(
     self_ty: &Canonical<Ty>,
 ) -> Option<Ty> {
     let substs = match function_id.lookup(db.upcast()).container {
-        AssocContainerId::TraitId(_) => Substitution::build_for_def(db, function_id)
+        AssocContainerId::TraitId(_) => TyBuilder::subst_for_def(db, function_id)
             .push(self_ty.value.clone())
             .fill_with_unknown()
             .build(),
         AssocContainerId::ImplId(impl_id) => {
             let impl_substs = inherent_impl_substs(db, impl_id, &self_ty)?;
-            Substitution::build_for_def(db, function_id)
+            TyBuilder::subst_for_def(db, function_id)
                 .use_parent_substs(&impl_substs)
                 .fill_with_unknown()
                 .build()
@@ -813,7 +812,7 @@ fn generic_implements_goal(
     self_ty: Canonical<Ty>,
 ) -> Canonical<InEnvironment<super::DomainGoal>> {
     let mut kinds = self_ty.binders.interned().to_vec();
-    let substs = super::Substitution::build_for_def(db, trait_)
+    let trait_ref = TyBuilder::trait_ref(db, trait_)
         .push(self_ty.value)
         .fill_with_bound_vars(DebruijnIndex::INNERMOST, kinds.len())
         .build();
@@ -822,9 +821,8 @@ fn generic_implements_goal(
             chalk_ir::VariableKind::Ty(chalk_ir::TyVariableKind::General),
             UniverseIndex::ROOT,
         ))
-        .take(substs.len(&Interner) - 1),
+        .take(trait_ref.substitution.len(&Interner) - 1),
     );
-    let trait_ref = TraitRef { trait_id: to_chalk_trait_id(trait_), substitution: substs };
     let obligation = trait_ref.cast(&Interner);
     Canonical {
         binders: CanonicalVarKinds::from_iter(&Interner, kinds),
diff --git a/crates/hir_ty/src/op.rs b/crates/hir_ty/src/op.rs
index 8533e1ed8..90dd31a35 100644
--- a/crates/hir_ty/src/op.rs
+++ b/crates/hir_ty/src/op.rs
@@ -2,12 +2,12 @@
 use chalk_ir::TyVariableKind;
 use hir_def::expr::{ArithOp, BinaryOp, CmpOp};
 
-use crate::{Interner, Scalar, Ty, TyKind};
+use crate::{Interner, Scalar, Ty, TyBuilder, TyKind};
 
 pub(super) fn binary_op_return_ty(op: BinaryOp, lhs_ty: Ty, rhs_ty: Ty) -> Ty {
     match op {
         BinaryOp::LogicOp(_) | BinaryOp::CmpOp(_) => TyKind::Scalar(Scalar::Bool).intern(&Interner),
-        BinaryOp::Assignment { .. } => Ty::unit(),
+        BinaryOp::Assignment { .. } => TyBuilder::unit(),
         BinaryOp::ArithOp(ArithOp::Shl) | BinaryOp::ArithOp(ArithOp::Shr) => {
             match lhs_ty.kind(&Interner) {
                 TyKind::Scalar(Scalar::Int(_))
diff --git a/crates/hir_ty/src/traits/chalk.rs b/crates/hir_ty/src/traits/chalk.rs
index fbac51b05..541e6082f 100644
--- a/crates/hir_ty/src/traits/chalk.rs
+++ b/crates/hir_ty/src/traits/chalk.rs
@@ -22,7 +22,7 @@ use crate::{
     to_assoc_type_id, to_chalk_trait_id,
     utils::generics,
     AliasEq, AliasTy, BoundVar, CallableDefId, DebruijnIndex, FnDefId, ProjectionTy, Substitution,
-    TraitRef, Ty, TyKind, WhereClause,
+    TraitRef, Ty, TyBuilder, TyKind, WhereClause,
 };
 use mapping::{
     convert_where_clauses, generic_predicate_to_inline_bound, make_binders, TypeAliasAsValue,
@@ -300,7 +300,7 @@ impl<'a> chalk_solve::RustIrDatabase<Interner> for ChalkContext<'a> {
         _closure_id: chalk_ir::ClosureId<Interner>,
         _substs: &chalk_ir::Substitution<Interner>,
     ) -> chalk_ir::Binders<chalk_ir::Ty<Interner>> {
-        let ty = Ty::unit().to_chalk(self.db);
+        let ty = TyBuilder::unit().to_chalk(self.db);
         make_binders(ty, 0)
     }
     fn closure_fn_substitution(
@@ -387,7 +387,7 @@ pub(crate) fn associated_ty_data_query(
     // Lower bounds -- we could/should maybe move this to a separate query in `lower`
     let type_alias_data = db.type_alias_data(type_alias);
     let generic_params = generics(db.upcast(), type_alias.into());
-    let bound_vars = Substitution::bound_vars(&generic_params, DebruijnIndex::INNERMOST);
+    let bound_vars = generic_params.bound_vars_subst(DebruijnIndex::INNERMOST);
     let resolver = hir_def::resolver::HasResolver::resolver(type_alias, db.upcast());
     let ctx = crate::TyLoweringContext::new(db, &resolver)
         .with_type_param_mode(crate::lower::TypeParamLoweringMode::Variable);
@@ -421,7 +421,7 @@ pub(crate) fn trait_datum_query(
     let trait_data = db.trait_data(trait_);
     debug!("trait {:?} = {:?}", trait_id, trait_data.name);
     let generic_params = generics(db.upcast(), trait_.into());
-    let bound_vars = Substitution::bound_vars(&generic_params, DebruijnIndex::INNERMOST);
+    let bound_vars = generic_params.bound_vars_subst(DebruijnIndex::INNERMOST);
     let flags = rust_ir::TraitFlags {
         auto: trait_data.is_auto,
         upstream: trait_.lookup(db.upcast()).container.krate() != krate,
@@ -490,7 +490,7 @@ pub(crate) fn struct_datum_query(
     let upstream = adt_id.module(db.upcast()).krate() != krate;
     let where_clauses = {
         let generic_params = generics(db.upcast(), adt_id.into());
-        let bound_vars = Substitution::bound_vars(&generic_params, DebruijnIndex::INNERMOST);
+        let bound_vars = generic_params.bound_vars_subst(DebruijnIndex::INNERMOST);
         convert_where_clauses(db, adt_id.into(), &bound_vars)
     };
     let flags = rust_ir::AdtFlags {
@@ -539,7 +539,7 @@ fn impl_def_datum(
     let impl_data = db.impl_data(impl_id);
 
     let generic_params = generics(db.upcast(), impl_id.into());
-    let bound_vars = Substitution::bound_vars(&generic_params, DebruijnIndex::INNERMOST);
+    let bound_vars = generic_params.bound_vars_subst(DebruijnIndex::INNERMOST);
     let trait_ = trait_ref.hir_trait_id();
     let impl_type = if impl_id.lookup(db.upcast()).container.krate() == krate {
         rust_ir::ImplType::Local
@@ -629,7 +629,7 @@ pub(crate) fn fn_def_datum_query(
     let callable_def: CallableDefId = from_chalk(db, fn_def_id);
     let generic_params = generics(db.upcast(), callable_def.into());
     let sig = db.callable_item_signature(callable_def);
-    let bound_vars = Substitution::bound_vars(&generic_params, DebruijnIndex::INNERMOST);
+    let bound_vars = generic_params.bound_vars_subst(DebruijnIndex::INNERMOST);
     let where_clauses = convert_where_clauses(db, callable_def.into(), &bound_vars);
     let bound = rust_ir::FnDefDatumBound {
         // Note: Chalk doesn't actually use this information yet as far as I am aware, but we provide it anyway
diff --git a/crates/hir_ty/src/utils.rs b/crates/hir_ty/src/utils.rs
index 42d7af146..b23e91b1b 100644
--- a/crates/hir_ty/src/utils.rs
+++ b/crates/hir_ty/src/utils.rs
@@ -2,7 +2,7 @@
 //! query, but can't be computed directly from `*Data` (ie, which need a `db`).
 use std::sync::Arc;
 
-use chalk_ir::DebruijnIndex;
+use chalk_ir::{BoundVar, DebruijnIndex};
 use hir_def::{
     adt::VariantData,
     db::DefDatabase,
@@ -16,7 +16,7 @@ use hir_def::{
 };
 use hir_expand::name::{name, Name};
 
-use crate::{db::HirDatabase, TraitRef, TypeWalk, WhereClause};
+use crate::{db::HirDatabase, Interner, Substitution, TraitRef, TyKind, TypeWalk, WhereClause};
 
 fn direct_super_traits(db: &dyn DefDatabase, trait_: TraitId) -> Vec<TraitId> {
     let resolver = trait_.resolver(db);
@@ -249,6 +249,26 @@ impl Generics {
             self.parent_generics.as_ref().and_then(|g| g.find_param(param))
         }
     }
+
+    /// Returns a Substitution that replaces each parameter by a bound variable.
+    pub(crate) fn bound_vars_subst(&self, debruijn: DebruijnIndex) -> Substitution {
+        Substitution::from_iter(
+            &Interner,
+            self.iter()
+                .enumerate()
+                .map(|(idx, _)| TyKind::BoundVar(BoundVar::new(debruijn, idx)).intern(&Interner)),
+        )
+    }
+
+    /// Returns a Substitution that replaces each parameter by itself (i.e. `Ty::Param`).
+    pub(crate) fn type_params_subst(&self, db: &dyn HirDatabase) -> Substitution {
+        Substitution::from_iter(
+            &Interner,
+            self.iter().map(|(id, _)| {
+                TyKind::Placeholder(crate::to_placeholder_idx(db, id)).intern(&Interner)
+            }),
+        )
+    }
 }
 
 fn parent_generic_def(db: &dyn DefDatabase, def: GenericDefId) -> Option<GenericDefId> {
diff --git a/crates/ide/src/inlay_hints.rs b/crates/ide/src/inlay_hints.rs
index f73edf8b6..d5ef054d8 100644
--- a/crates/ide/src/inlay_hints.rs
+++ b/crates/ide/src/inlay_hints.rs
@@ -234,7 +234,7 @@ fn hint_iterator(
             hir::AssocItem::TypeAlias(alias) if alias.name(db) == known::Item => Some(alias),
             _ => None,
         })?;
-        if let Some(ty) = ty.normalize_trait_assoc_type(db, iter_trait, &[], assoc_type_item) {
+        if let Some(ty) = ty.normalize_trait_assoc_type(db, &[], assoc_type_item) {
             const LABEL_START: &str = "impl Iterator<Item = ";
             const LABEL_END: &str = ">";