]> git.lizzy.rs Git - rust.git/blobdiff - crates/hir_ty/src/lower.rs
Rename TyKind::ForeignType to Foreign
[rust.git] / crates / hir_ty / src / lower.rs
index b4c650fa1ecc2c4957b54163fc8f1c9b5504d161..ba48be4ad0f1daa924e448898a3b8b9d6b3127ba 100644 (file)
@@ -15,7 +15,7 @@
     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,
 
 use crate::{
     db::HirDatabase,
-    to_assoc_type_id, to_placeholder_idx,
+    to_assoc_type_id, to_chalk_trait_id, to_placeholder_idx,
     traits::chalk::{Interner, ToChalk},
     utils::{
         all_super_trait_refs, associated_type_by_name_including_super_traits, generics,
-        make_mut_slice, variant_data,
+        variant_data,
     },
-    AliasTy, Binders, BoundVar, CallableSig, DebruijnIndex, FnPointer, FnSig, GenericPredicate,
-    ImplTraitId, OpaqueTy, PolyFnSig, ProjectionPredicate, ProjectionTy, ReturnTypeImplTrait,
-    ReturnTypeImplTraits, Substs, TraitEnvironment, TraitRef, Ty, TyKind, TypeWalk,
+    AliasEq, AliasTy, Binders, BoundVar, CallableSig, DebruijnIndex, DynTy, FnPointer, FnSig,
+    ImplTraitId, OpaqueTy, PolyFnSig, ProjectionTy, QuantifiedWhereClause, QuantifiedWhereClauses,
+    ReturnTypeImplTrait, ReturnTypeImplTraits, Substitution, TraitEnvironment, TraitRef, Ty,
+    TyBuilder, TyKind, TypeWalk, WhereClause,
 };
 
 #[derive(Debug)]
@@ -145,13 +146,14 @@ pub fn lower_ty(&self, type_ref: &TypeRef) -> Ty {
         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),
             TypeRef::Tuple(inner) => {
-                let inner_tys: Arc<[Ty]> = inner.iter().map(|tr| self.lower_ty(tr)).collect();
-                TyKind::Tuple(inner_tys.len(), Substs(inner_tys)).intern(&Interner)
+                let inner_tys = inner.iter().map(|tr| self.lower_ty(tr));
+                TyKind::Tuple(inner_tys.len(), Substitution::from_iter(&Interner, inner_tys))
+                    .intern(&Interner)
             }
             TypeRef::Path(path) => {
                 let (ty, res_) = self.lower_path(path);
@@ -174,11 +176,12 @@ fn lower_ty_ext(&self, type_ref: &TypeRef) -> (Ty, Option<TypeNs>) {
                 let inner_ty = self.lower_ty(inner);
                 TyKind::Ref(lower_to_chalk_mutability(*mutability), inner_ty).intern(&Interner)
             }
-            TypeRef::Placeholder => TyKind::Unknown.intern(&Interner),
+            TypeRef::Placeholder => TyKind::Error.intern(&Interner),
             TypeRef::Fn(params, is_varargs) => {
-                let substs = Substs(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,
                 })
@@ -187,10 +190,14 @@ fn lower_ty_ext(&self, type_ref: &TypeRef) -> (Ty, Option<TypeNs>) {
             TypeRef::DynTrait(bounds) => {
                 let self_ty =
                     TyKind::BoundVar(BoundVar::new(DebruijnIndex::INNERMOST, 0)).intern(&Interner);
-                let predicates = self.with_shifted_in(DebruijnIndex::ONE, |ctx| {
-                    bounds.iter().flat_map(|b| ctx.lower_type_bound(b, self_ty.clone())).collect()
+                let bounds = self.with_shifted_in(DebruijnIndex::ONE, |ctx| {
+                    QuantifiedWhereClauses::from_iter(
+                        &Interner,
+                        bounds.iter().flat_map(|b| ctx.lower_type_bound(b, self_ty.clone(), false)),
+                    )
                 });
-                TyKind::Dyn(predicates).intern(&Interner)
+                let bounds = Binders::new(1, bounds);
+                TyKind::Dyn(DynTy { bounds }).intern(&Interner)
             }
             TypeRef::ImplTrait(bounds) => {
                 match self.impl_trait_mode {
@@ -227,7 +234,7 @@ fn lower_ty_ext(&self, type_ref: &TypeRef) -> (Ty, Option<TypeNs>) {
                         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 = Substs::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,
@@ -246,12 +253,12 @@ fn lower_ty_ext(&self, type_ref: &TypeRef) -> (Ty, Option<TypeNs>) {
                                     data.provenance == TypeParamProvenance::ArgumentImplTrait
                                 })
                                 .nth(idx as usize)
-                                .map_or(TyKind::Unknown, |(id, _)| {
+                                .map_or(TyKind::Error, |(id, _)| {
                                     TyKind::Placeholder(to_placeholder_idx(self.db, id))
                                 });
                             param.intern(&Interner)
                         } else {
-                            TyKind::Unknown.intern(&Interner)
+                            TyKind::Error.intern(&Interner)
                         }
                     }
                     ImplTraitLoweringMode::Variable => {
@@ -273,11 +280,11 @@ fn lower_ty_ext(&self, type_ref: &TypeRef) -> (Ty, Option<TypeNs>) {
                     }
                     ImplTraitLoweringMode::Disallowed => {
                         // FIXME: report error
-                        TyKind::Unknown.intern(&Interner)
+                        TyKind::Error.intern(&Interner)
                     }
                 }
             }
-            TypeRef::Error => TyKind::Unknown.intern(&Interner),
+            TypeRef::Error => TyKind::Error.intern(&Interner),
         };
         (ty, res)
     }
@@ -321,7 +328,7 @@ pub(crate) fn lower_ty_relative_path(
             (self.select_associated_type(res, segment), None)
         } else if remaining_segments.len() > 1 {
             // FIXME report error (ambiguous associated type)
-            (TyKind::Unknown.intern(&Interner), None)
+            (TyKind::Error.intern(&Interner), None)
         } else {
             (ty, res)
         }
@@ -359,21 +366,29 @@ pub(crate) fn lower_partly_resolved_path(
                             // FIXME handle type parameters on the segment
                             TyKind::Alias(AliasTy::Projection(ProjectionTy {
                                 associated_ty_id: to_assoc_type_id(associated_ty),
-                                substitution: super_trait_ref.substs,
+                                substitution: super_trait_ref.substitution,
                             }))
                             .intern(&Interner)
                         }
                         None => {
                             // FIXME: report error (associated type not found)
-                            TyKind::Unknown.intern(&Interner)
+                            TyKind::Error.intern(&Interner)
                         }
                     }
                 } else if remaining_segments.len() > 1 {
                     // FIXME report error (ambiguous associated type)
-                    TyKind::Unknown.intern(&Interner)
+                    TyKind::Error.intern(&Interner)
                 } else {
-                    TyKind::Dyn(Arc::new([GenericPredicate::Implemented(trait_ref)]))
-                        .intern(&Interner)
+                    let dyn_ty = DynTy {
+                        bounds: Binders::new(
+                            1,
+                            QuantifiedWhereClauses::from_iter(
+                                &Interner,
+                                Some(Binders::wrap_empty(WhereClause::Implemented(trait_ref))),
+                            ),
+                        ),
+                    };
+                    TyKind::Dyn(dyn_ty).intern(&Interner)
                 };
                 return (ty, None);
             }
@@ -396,24 +411,16 @@ pub(crate) fn lower_partly_resolved_path(
             TypeNs::SelfType(impl_id) => {
                 let generics = generics(self.db.upcast(), impl_id.into());
                 let substs = match self.type_param_mode {
-                    TypeParamLoweringMode::Placeholder => {
-                        Substs::type_params_for_generics(self.db, &generics)
-                    }
-                    TypeParamLoweringMode::Variable => {
-                        Substs::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 => {
-                        Substs::type_params_for_generics(self.db, &generics)
-                    }
-                    TypeParamLoweringMode::Variable => {
-                        Substs::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)
             }
@@ -426,7 +433,7 @@ pub(crate) fn lower_partly_resolved_path(
                 self.lower_path_inner(resolved_segment, it.into(), infer_args)
             }
             // FIXME: report error
-            TypeNs::EnumVariantId(_) => return (TyKind::Unknown.intern(&Interner), None),
+            TypeNs::EnumVariantId(_) => return (TyKind::Error.intern(&Interner), None),
         };
         self.lower_ty_relative_path(ty, Some(resolution), remaining_segments)
     }
@@ -440,7 +447,7 @@ pub(crate) fn lower_path(&self, path: &Path) -> (Ty, Option<TypeNs>) {
         let (resolution, remaining_index) =
             match self.resolver.resolve_path_in_type_ns(self.db.upcast(), path.mod_path()) {
                 Some(it) => it,
-                None => return (TyKind::Unknown.intern(&Interner), None),
+                None => return (TyKind::Error.intern(&Interner), None),
             };
         let (resolved_segment, remaining_segments) = match remaining_index {
             None => (
@@ -463,15 +470,16 @@ fn select_associated_type(&self, res: Option<TypeNs>, segment: PathSegment<'_>)
                             TypeParamLoweringMode::Placeholder => {
                                 // if we're lowering to placeholders, we have to put
                                 // them in now
-                                let s = Substs::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",
                                     ),
                                 );
-                                t.substs.clone().subst_bound_vars(&s)
+                                let s = generics.type_params_subst(self.db);
+                                t.substitution.clone().subst_bound_vars(&s)
                             }
-                            TypeParamLoweringMode::Variable => t.substs.clone(),
+                            TypeParamLoweringMode::Variable => t.substitution.clone(),
                         };
                         // We need to shift in the bound vars, since
                         // associated_type_shorthand_candidates does not do that
@@ -490,9 +498,9 @@ fn select_associated_type(&self, res: Option<TypeNs>, segment: PathSegment<'_>)
                 },
             );
 
-            ty.unwrap_or(TyKind::Unknown.intern(&Interner))
+            ty.unwrap_or(TyKind::Error.intern(&Interner))
         } else {
-            TyKind::Unknown.intern(&Interner)
+            TyKind::Error.intern(&Interner)
         }
     }
 
@@ -507,7 +515,7 @@ fn lower_path_inner(
             TyDefId::AdtId(it) => Some(it.into()),
             TyDefId::TypeAliasId(it) => Some(it.into()),
         };
-        let substs = self.substs_from_path_segment(segment, generic_def, infer_args);
+        let substs = self.substs_from_path_segment(segment, generic_def, infer_args, None);
         self.db.ty(typeable).subst(&substs)
     }
 
@@ -521,7 +529,7 @@ pub(super) fn substs_from_path(
         // special-case enum variants
         resolved: ValueTyDefId,
         infer_args: bool,
-    ) -> Substs {
+    ) -> Substitution {
         let last = path.segments().last().expect("path should have at least one segment");
         let (segment, generic_def) = match resolved {
             ValueTyDefId::FunctionId(it) => (last, Some(it.into())),
@@ -544,7 +552,7 @@ pub(super) fn substs_from_path(
                 (segment, Some(var.parent.into()))
             }
         };
-        self.substs_from_path_segment(segment, generic_def, infer_args)
+        self.substs_from_path_segment(segment, generic_def, infer_args, None)
     }
 
     fn substs_from_path_segment(
@@ -552,7 +560,8 @@ fn substs_from_path_segment(
         segment: PathSegment<'_>,
         def_generic: Option<GenericDefId>,
         infer_args: bool,
-    ) -> Substs {
+        explicit_self_ty: Option<Ty>,
+    ) -> Substitution {
         let mut substs = Vec::new();
         let def_generics = def_generic.map(|def| generics(self.db.upcast(), def));
 
@@ -560,13 +569,21 @@ fn substs_from_path_segment(
             def_generics.map_or((0, 0, 0, 0), |g| g.provenance_split());
         let total_len = parent_params + self_params + type_params + impl_trait_params;
 
-        substs.extend(iter::repeat(TyKind::Unknown.intern(&Interner)).take(parent_params));
+        substs.extend(iter::repeat(TyKind::Error.intern(&Interner)).take(parent_params));
 
+        let fill_self_params = || {
+            substs.extend(
+                explicit_self_ty
+                    .into_iter()
+                    .chain(iter::repeat(TyKind::Error.intern(&Interner)))
+                    .take(self_params),
+            )
+        };
         let mut had_explicit_type_args = false;
 
         if let Some(generic_args) = &segment.args_and_bindings {
             if !generic_args.has_self_type {
-                substs.extend(iter::repeat(TyKind::Unknown.intern(&Interner)).take(self_params));
+                fill_self_params();
             }
             let expected_num =
                 if generic_args.has_self_type { self_params + type_params } else { type_params };
@@ -588,6 +605,8 @@ fn substs_from_path_segment(
                     GenericArg::Lifetime(_) => {}
                 }
             }
+        } else {
+            fill_self_params();
         }
 
         // handle defaults. In expression or pattern path segments without
@@ -600,7 +619,7 @@ fn substs_from_path_segment(
 
                 for default_ty in defaults.iter().skip(substs.len()) {
                     // each default can depend on the previous parameters
-                    let substs_so_far = Substs(substs.clone().into());
+                    let substs_so_far = Substitution::from_iter(&Interner, substs.clone());
                     substs.push(default_ty.clone().subst(&substs_so_far));
                 }
             }
@@ -609,11 +628,11 @@ fn substs_from_path_segment(
         // add placeholders for args that were not provided
         // FIXME: emit diagnostics in contexts where this is not allowed
         for _ in substs.len()..total_len {
-            substs.push(TyKind::Unknown.intern(&Interner));
+            substs.push(TyKind::Error.intern(&Interner));
         }
         assert_eq!(substs.len(), total_len);
 
-        Substs(substs.into())
+        Substitution::from_iter(&Interner, substs)
     }
 
     fn lower_trait_ref_from_path(
@@ -636,33 +655,32 @@ pub(crate) fn lower_trait_ref_from_resolved_path(
         segment: PathSegment<'_>,
         explicit_self_ty: Option<Ty>,
     ) -> TraitRef {
-        let mut substs = self.trait_ref_substs_from_path(segment, resolved);
-        if let Some(self_ty) = explicit_self_ty {
-            make_mut_slice(&mut substs.0)[0] = self_ty;
-        }
-        TraitRef { trait_: resolved, substs }
+        let substs = self.trait_ref_substs_from_path(segment, resolved, explicit_self_ty);
+        TraitRef { trait_id: to_chalk_trait_id(resolved), substitution: substs }
     }
 
     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(&self, segment: PathSegment<'_>, resolved: TraitId) -> Substs {
-        self.substs_from_path_segment(segment, Some(resolved.into()), false)
+    fn trait_ref_substs_from_path(
+        &self,
+        segment: PathSegment<'_>,
+        resolved: TraitId,
+        explicit_self_ty: Option<Ty>,
+    ) -> Substitution {
+        self.substs_from_path_segment(segment, Some(resolved.into()), false, explicit_self_ty)
     }
 
     pub(crate) fn lower_where_predicate(
         &'a self,
         where_predicate: &'a WherePredicate,
-    ) -> impl Iterator<Item = GenericPredicate> + 'a {
+        ignore_bindings: bool,
+    ) -> impl Iterator<Item = QuantifiedWhereClause> + 'a {
         match where_predicate {
             WherePredicate::ForLifetime { target, bound, .. }
             | WherePredicate::TypeBound { target, bound } => {
@@ -684,7 +702,9 @@ pub(crate) fn lower_where_predicate(
                         .intern(&Interner)
                     }
                 };
-                self.lower_type_bound(bound, self_ty).collect::<Vec<_>>().into_iter()
+                self.lower_type_bound(bound, self_ty, ignore_bindings)
+                    .collect::<Vec<_>>()
+                    .into_iter()
             }
             WherePredicate::Lifetime { .. } => vec![].into_iter(),
         }
@@ -694,21 +714,21 @@ pub(crate) fn lower_type_bound(
         &'a self,
         bound: &'a TypeBound,
         self_ty: Ty,
-    ) -> impl Iterator<Item = GenericPredicate> + 'a {
+        ignore_bindings: bool,
+    ) -> impl Iterator<Item = QuantifiedWhereClause> + 'a {
         let mut bindings = None;
         let trait_ref = match bound {
             TypeBound::Path(path) => {
                 bindings = self.lower_trait_ref_from_path(path, Some(self_ty));
-                Some(
-                    bindings.clone().map_or(GenericPredicate::Error, GenericPredicate::Implemented),
-                )
+                bindings.clone().map(WhereClause::Implemented).map(|b| Binders::wrap_empty(b))
             }
             TypeBound::Lifetime(_) => None,
-            TypeBound::Error => Some(GenericPredicate::Error),
+            TypeBound::Error => None,
         };
         trait_ref.into_iter().chain(
             bindings
                 .into_iter()
+                .filter(move |_| !ignore_bindings)
                 .flat_map(move |tr| self.assoc_type_bindings_from_type_bound(bound, tr)),
         )
     }
@@ -717,7 +737,7 @@ fn assoc_type_bindings_from_type_bound(
         &'a self,
         bound: &'a TypeBound,
         trait_ref: TraitRef,
-    ) -> impl Iterator<Item = GenericPredicate> + 'a {
+    ) -> impl Iterator<Item = QuantifiedWhereClause> + 'a {
         let last_segment = match bound {
             TypeBound::Path(path) => path.segments().last(),
             TypeBound::Error | TypeBound::Lifetime(_) => None,
@@ -733,26 +753,27 @@ fn assoc_type_bindings_from_type_bound(
                     &binding.name,
                 );
                 let (super_trait_ref, associated_ty) = match found {
-                    None => return SmallVec::<[GenericPredicate; 1]>::new(),
+                    None => return SmallVec::<[QuantifiedWhereClause; 1]>::new(),
                     Some(t) => t,
                 };
                 let projection_ty = ProjectionTy {
                     associated_ty_id: to_assoc_type_id(associated_ty),
-                    substitution: super_trait_ref.substs,
+                    substitution: super_trait_ref.substitution,
                 };
                 let mut preds = SmallVec::with_capacity(
                     binding.type_ref.as_ref().map_or(0, |_| 1) + binding.bounds.len(),
                 );
                 if let Some(type_ref) = &binding.type_ref {
                     let ty = self.lower_ty(type_ref);
-                    let projection_predicate =
-                        ProjectionPredicate { projection_ty: projection_ty.clone(), ty };
-                    preds.push(GenericPredicate::Projection(projection_predicate));
+                    let alias_eq =
+                        AliasEq { alias: AliasTy::Projection(projection_ty.clone()), ty };
+                    preds.push(Binders::wrap_empty(WhereClause::AliasEq(alias_eq)));
                 }
                 for bound in &binding.bounds {
                     preds.extend(self.lower_type_bound(
                         bound,
                         TyKind::Alias(AliasTy::Projection(projection_ty.clone())).intern(&Interner),
+                        false,
                     ));
                 }
                 preds
@@ -764,7 +785,7 @@ fn lower_impl_trait(&self, bounds: &[TypeBound]) -> ReturnTypeImplTrait {
         let self_ty =
             TyKind::BoundVar(BoundVar::new(DebruijnIndex::INNERMOST, 0)).intern(&Interner);
         let predicates = self.with_shifted_in(DebruijnIndex::ONE, |ctx| {
-            bounds.iter().flat_map(|b| ctx.lower_type_bound(b, self_ty.clone())).collect()
+            bounds.iter().flat_map(|b| ctx.lower_type_bound(b, self_ty.clone(), false)).collect()
         });
         ReturnTypeImplTrait { bounds: Binders::new(1, predicates) }
     }
@@ -794,54 +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![],
-            Some(trait_ref) => vec![trait_ref.value],
-        },
+    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 {
-                    GenericPredicate::Implemented(tr) => Some(tr.clone()),
-                    _ => 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_: trait_id,
-                        substs: Substs::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.trait_);
-
-        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.
@@ -876,7 +897,7 @@ pub(crate) fn field_types_query(
 pub(crate) fn generic_predicates_for_param_query(
     db: &dyn HirDatabase,
     param_id: TypeParamId,
-) -> Arc<[Binders<GenericPredicate>]> {
+) -> Arc<[Binders<QuantifiedWhereClause>]> {
     let resolver = param_id.parent.resolver(db.upcast());
     let ctx =
         TyLoweringContext::new(db, &resolver).with_type_param_mode(TypeParamLoweringMode::Variable);
@@ -894,7 +915,9 @@ pub(crate) fn generic_predicates_for_param_query(
             },
             WherePredicate::Lifetime { .. } => false,
         })
-        .flat_map(|pred| ctx.lower_where_predicate(pred).map(|p| Binders::new(generics.len(), p)))
+        .flat_map(|pred| {
+            ctx.lower_where_predicate(pred, true).map(|p| Binders::new(generics.len(), p))
+        })
         .collect()
 }
 
@@ -902,7 +925,7 @@ pub(crate) fn generic_predicates_for_param_recover(
     _db: &dyn HirDatabase,
     _cycle: &[String],
     _param_id: &TypeParamId,
-) -> Arc<[Binders<GenericPredicate>]> {
+) -> Arc<[Binders<QuantifiedWhereClause>]> {
     Arc::new([])
 }
 
@@ -916,12 +939,9 @@ pub(crate) fn trait_environment_query(
     let mut traits_in_scope = Vec::new();
     let mut clauses = Vec::new();
     for pred in resolver.where_predicates_in_scope() {
-        for pred in ctx.lower_where_predicate(pred) {
-            if pred.is_error() {
-                continue;
-            }
-            if let GenericPredicate::Implemented(tr) = &pred {
-                traits_in_scope.push((tr.self_ty().clone(), tr.trait_));
+        for pred in ctx.lower_where_predicate(pred, false) {
+            if let WhereClause::Implemented(tr) = &pred.skip_binders() {
+                traits_in_scope.push((tr.self_type_parameter().clone(), tr.hir_trait_id()));
             }
             let program_clause: chalk_ir::ProgramClause<Interner> =
                 pred.clone().to_chalk(db).cast(&Interner);
@@ -944,11 +964,10 @@ 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 = Substs::type_params(db, trait_id);
-        let trait_ref = TraitRef { trait_: trait_id, substs };
-        let pred = GenericPredicate::Implemented(trait_ref);
-        let program_clause: chalk_ir::ProgramClause<Interner> =
-            pred.clone().to_chalk(db).cast(&Interner);
+        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);
         clauses.push(program_clause.into_from_env_clause(&Interner));
     }
 
@@ -961,14 +980,16 @@ pub(crate) fn trait_environment_query(
 pub(crate) fn generic_predicates_query(
     db: &dyn HirDatabase,
     def: GenericDefId,
-) -> Arc<[Binders<GenericPredicate>]> {
+) -> Arc<[Binders<QuantifiedWhereClause>]> {
     let resolver = def.resolver(db.upcast());
     let ctx =
         TyLoweringContext::new(db, &resolver).with_type_param_mode(TypeParamLoweringMode::Variable);
     let generics = generics(db.upcast(), def);
     resolver
         .where_predicates_in_scope()
-        .flat_map(|pred| ctx.lower_where_predicate(pred).map(|p| Binders::new(generics.len(), p)))
+        .flat_map(|pred| {
+            ctx.lower_where_predicate(pred, false).map(|p| Binders::new(generics.len(), p))
+        })
         .collect()
 }
 
@@ -987,7 +1008,7 @@ pub(crate) fn generic_defaults_query(
         .enumerate()
         .map(|(idx, (_, p))| {
             let mut ty =
-                p.default.as_ref().map_or(TyKind::Unknown.intern(&Interner), |t| ctx.lower_ty(t));
+                p.default.as_ref().map_or(TyKind::Error.intern(&Interner), |t| ctx.lower_ty(t));
 
             // Each default can only refer to previous parameters.
             ty.walk_mut_binders(
@@ -997,7 +1018,7 @@ pub(crate) fn generic_defaults_query(
                             // type variable default referring to parameter coming
                             // after it. This is forbidden (FIXME: report
                             // diagnostic)
-                            *ty = TyKind::Unknown.intern(&Interner);
+                            *ty = TyKind::Error.intern(&Interner);
                         }
                     }
                     _ => {}
@@ -1025,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 = Substs::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),
     )
 }
@@ -1077,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 = Substs::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),
     )
 }
@@ -1104,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 = Substs::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 = Substs::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> {
@@ -1123,12 +1145,11 @@ fn type_for_type_alias(db: &dyn HirDatabase, t: TypeAliasId) -> Binders<Ty> {
     let ctx =
         TyLoweringContext::new(db, &resolver).with_type_param_mode(TypeParamLoweringMode::Variable);
     if db.type_alias_data(t).is_extern {
-        Binders::new(0, TyKind::ForeignType(crate::to_foreign_def_id(t)).intern(&Interner))
+        Binders::new(0, TyKind::Foreign(crate::to_foreign_def_id(t)).intern(&Interner))
     } else {
-        let substs = Substs::bound_vars(&generics, DebruijnIndex::INNERMOST);
         let type_ref = &db.type_alias_data(t).type_ref;
-        let inner = ctx.lower_ty(type_ref.as_ref().unwrap_or(&TypeRef::Error));
-        Binders::new(substs.len(), inner)
+        let inner = ctx.lower_ty(type_ref.as_deref().unwrap_or(&TypeRef::Error));
+        Binders::new(generics.len(), inner)
     }
 }
 
@@ -1187,7 +1208,7 @@ pub enum ValueTyDefId {
 /// 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),
     }
@@ -1199,7 +1220,7 @@ pub(crate) fn ty_recover(db: &dyn HirDatabase, _cycle: &[String], def: &TyDefId)
         TyDefId::AdtId(it) => generics(db.upcast(), it.into()).len(),
         TyDefId::TypeAliasId(it) => generics(db.upcast(), it.into()).len(),
     };
-    Binders::new(num_binders, TyKind::Unknown.intern(&Interner))
+    Binders::new(num_binders, TyKind::Error.intern(&Interner))
 }
 
 pub(crate) fn value_ty_query(db: &dyn HirDatabase, def: ValueTyDefId) -> Binders<Ty> {
@@ -1219,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 {
@@ -1237,7 +1258,7 @@ pub(crate) fn impl_self_ty_recover(
     impl_id: &ImplId,
 ) -> Binders<Ty> {
     let generics = generics(db.upcast(), (*impl_id).into());
-    Binders::new(generics.len(), TyKind::Unknown.intern(&Interner))
+    Binders::new(generics.len(), TyKind::Error.intern(&Interner))
 }
 
 pub(crate) fn impl_trait_query(db: &dyn HirDatabase, impl_id: ImplId) -> Option<Binders<TraitRef>> {