1 files changed, 69 insertions, 82 deletions

diff --git a/crates/hir_ty/src/lower.rs b/crates/hir_ty/src/lower.rs
index c87789d45..214655807 100644
--- a/crates/hir_ty/src/lower.rs
+++ b/crates/hir_ty/src/lower.rs
@@ -15,7 +15,7 @@ use hir_def::{
     generics::{TypeParamProvenance, WherePredicate, WherePredicateTypeTarget},
     path::{GenericArg, Path, PathSegment, PathSegments},
     resolver::{HasResolver, Resolver, TypeNs},
-    type_ref::{TypeBound, TypeRef},
+    type_ref::{TraitRef as HirTraitRef, TypeBound, TypeRef},
     AdtId, AssocContainerId, AssocItemId, ConstId, ConstParamId, EnumId, EnumVariantId, FunctionId,
     GenericDefId, HasModule, ImplId, LocalFieldId, Lookup, StaticId, StructId, TraitId,
     TypeAliasId, TypeParamId, UnionId, VariantId,
@@ -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)]
@@ -146,7 +146,7 @@ impl<'a> TyLoweringContext<'a> {
         self.lower_ty_ext(type_ref).0
     }
 
-    fn lower_ty_ext(&self, type_ref: &TypeRef) -> (Ty, Option<TypeNs>) {
+    pub fn lower_ty_ext(&self, type_ref: &TypeRef) -> (Ty, Option<TypeNs>) {
         let mut res = None;
         let ty = match type_ref {
             TypeRef::Never => TyKind::Never.intern(&Interner),
@@ -178,9 +178,10 @@ impl<'a> TyLoweringContext<'a> {
             }
             TypeRef::Placeholder => TyKind::Unknown.intern(&Interner),
             TypeRef::Fn(params, is_varargs) => {
-                let substs = Substitution(params.iter().map(|tr| self.lower_ty(tr)).collect());
+                let substs =
+                    Substitution::from_iter(&Interner, params.iter().map(|tr| self.lower_ty(tr)));
                 TyKind::Function(FnPointer {
-                    num_args: substs.len() - 1,
+                    num_args: substs.len(&Interner) - 1,
                     sig: FnSig { abi: (), safety: Safety::Safe, variadic: *is_varargs },
                     substs,
                 })
@@ -233,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,
@@ -410,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)
             }
@@ -477,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(),
@@ -625,7 +619,7 @@ impl<'a> TyLoweringContext<'a> {
 
                 for default_ty in defaults.iter().skip(substs.len()) {
                     // each default can depend on the previous parameters
-                    let substs_so_far = Substitution(substs.clone().into());
+                    let substs_so_far = Substitution::from_iter(&Interner, substs.clone());
                     substs.push(default_ty.clone().subst(&substs_so_far));
                 }
             }
@@ -638,7 +632,7 @@ impl<'a> TyLoweringContext<'a> {
         }
         assert_eq!(substs.len(), total_len);
 
-        Substitution(substs.into())
+        Substitution::from_iter(&Interner, substs)
     }
 
     fn lower_trait_ref_from_path(
@@ -667,14 +661,10 @@ impl<'a> TyLoweringContext<'a> {
 
     fn lower_trait_ref(
         &self,
-        type_ref: &TypeRef,
+        trait_ref: &HirTraitRef,
         explicit_self_ty: Option<Ty>,
     ) -> Option<TraitRef> {
-        let path = match type_ref {
-            TypeRef::Path(path) => path,
-            _ => return None,
-        };
-        self.lower_trait_ref_from_path(path, explicit_self_ty)
+        self.lower_trait_ref_from_path(&trait_ref.path, explicit_self_ty)
     }
 
     fn trait_ref_substs_from_path(
@@ -825,58 +815,54 @@ pub fn associated_type_shorthand_candidates<R>(
     res: TypeNs,
     mut cb: impl FnMut(&Name, &TraitRef, TypeAliasId) -> Option<R>,
 ) -> Option<R> {
-    let traits_from_env: Vec<_> = match res {
-        TypeNs::SelfType(impl_id) => match db.impl_trait(impl_id) {
-            None => vec![],
-            // FIXME: how to correctly handle higher-ranked bounds here?
-            Some(trait_ref) => vec![trait_ref.value.shift_bound_vars_out(DebruijnIndex::ONE)],
-        },
+    let mut search = |t| {
+        for t in all_super_trait_refs(db, t) {
+            let data = db.trait_data(t.hir_trait_id());
+
+            for (name, assoc_id) in &data.items {
+                if let AssocItemId::TypeAliasId(alias) = assoc_id {
+                    if let Some(result) = cb(name, &t, *alias) {
+                        return Some(result);
+                    }
+                }
+            }
+        }
+        None
+    };
+
+    match res {
+        // FIXME: how to correctly handle higher-ranked bounds here?
+        TypeNs::SelfType(impl_id) => {
+            search(db.impl_trait(impl_id)?.value.shift_bound_vars_out(DebruijnIndex::ONE))
+        }
         TypeNs::GenericParam(param_id) => {
             let predicates = db.generic_predicates_for_param(param_id);
-            let mut traits_: Vec<_> = predicates
-                .iter()
-                .filter_map(|pred| match &pred.value.value {
-                    // FIXME: how to correctly handle higher-ranked bounds here?
-                    WhereClause::Implemented(tr) => {
-                        Some(tr.clone().shift_bound_vars_out(DebruijnIndex::ONE))
-                    }
-                    _ => None,
-                })
-                .collect();
+            let res = predicates.iter().find_map(|pred| match &pred.value.value {
+                // FIXME: how to correctly handle higher-ranked bounds here?
+                WhereClause::Implemented(tr) => {
+                    search(tr.clone().shift_bound_vars_out(DebruijnIndex::ONE))
+                }
+                _ => None,
+            });
+            if let res @ Some(_) = res {
+                return res;
+            }
             // Handle `Self::Type` referring to own associated type in trait definitions
             if let GenericDefId::TraitId(trait_id) = param_id.parent {
                 let generics = generics(db.upcast(), trait_id.into());
                 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),
-                    };
-                    traits_.push(trait_ref);
-                }
-            }
-            traits_
-        }
-        _ => vec![],
-    };
-
-    for t in traits_from_env.into_iter().flat_map(move |t| all_super_trait_refs(db, t)) {
-        let data = db.trait_data(t.hir_trait_id());
-
-        for (name, assoc_id) in &data.items {
-            match assoc_id {
-                AssocItemId::TypeAliasId(alias) => {
-                    if let Some(result) = cb(name, &t, *alias) {
-                        return Some(result);
-                    }
+                    let trait_ref = TyBuilder::trait_ref(db, trait_id)
+                        .fill_with_bound_vars(DebruijnIndex::INNERMOST, 0)
+                        .build();
+                    return search(trait_ref);
                 }
-                AssocItemId::FunctionId(_) | AssocItemId::ConstId(_) => {}
             }
+            None
         }
+        _ => None,
     }
-
-    None
 }
 
 /// Build the type of all specific fields of a struct or enum variant.
@@ -978,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);
@@ -1060,16 +1046,16 @@ fn fn_sig_for_fn(db: &dyn HirDatabase, def: FunctionId) -> PolyFnSig {
     let ret = (&ctx_ret).lower_ty(&data.ret_type);
     let generics = generics(db.upcast(), def.into());
     let num_binders = generics.len();
-    Binders::new(num_binders, CallableSig::from_params_and_return(params, ret, data.is_varargs))
+    Binders::new(num_binders, CallableSig::from_params_and_return(params, ret, data.is_varargs()))
 }
 
 /// Build the declared type of a function. This should not need to look at the
 /// 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(),
+        substs.len(&Interner),
         TyKind::FnDef(CallableDefId::FunctionId(def).to_chalk(db), substs).intern(&Interner),
     )
 }
@@ -1112,9 +1098,9 @@ 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(),
+        substs.len(&Interner),
         TyKind::FnDef(CallableDefId::StructId(def).to_chalk(db), substs).intern(&Interner),
     )
 }
@@ -1139,17 +1125,18 @@ 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(),
+        substs.len(&Interner),
         TyKind::FnDef(CallableDefId::EnumVariantId(def).to_chalk(db), substs).intern(&Interner),
     )
 }
 
 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(), 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> {
@@ -1161,7 +1148,7 @@ fn type_for_type_alias(db: &dyn HirDatabase, t: TypeAliasId) -> Binders<Ty> {
         Binders::new(0, TyKind::ForeignType(crate::to_foreign_def_id(t)).intern(&Interner))
     } else {
         let type_ref = &db.type_alias_data(t).type_ref;
-        let inner = ctx.lower_ty(type_ref.as_ref().unwrap_or(&TypeRef::Error));
+        let inner = ctx.lower_ty(type_ref.as_deref().unwrap_or(&TypeRef::Error));
         Binders::new(generics.len(), inner)
     }
 }
@@ -1221,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),
     }
@@ -1253,7 +1240,7 @@ pub(crate) fn impl_self_ty_query(db: &dyn HirDatabase, impl_id: ImplId) -> Binde
     let generics = generics(db.upcast(), impl_id.into());
     let ctx =
         TyLoweringContext::new(db, &resolver).with_type_param_mode(TypeParamLoweringMode::Variable);
-    Binders::new(generics.len(), ctx.lower_ty(&impl_data.target_type))
+    Binders::new(generics.len(), ctx.lower_ty(&impl_data.self_ty))
 }
 
 pub(crate) fn const_param_ty_query(db: &dyn HirDatabase, def: ConstParamId) -> Ty {