38 files changed, 3677 insertions, 3852 deletions
diff --git a/crates/hir_ty/Cargo.toml b/crates/hir_ty/Cargo.toml
index 030b7eebe..abc0e7532 100644
--- a/crates/hir_ty/Cargo.toml
+++ b/crates/hir_ty/Cargo.toml
@@ -12,7 +12,7 @@ doctest = false
 [dependencies]
 cov-mark = { version = "1.1", features = ["thread-local"] }
 itertools = "0.10.0"
-arrayvec = "0.6"
+arrayvec = "0.7"
 smallvec = "1.2.0"
 ena = "0.14.0"
 log = "0.4.8"
diff --git a/crates/hir_ty/src/autoderef.rs b/crates/hir_ty/src/autoderef.rs
index dc5fc759a..2c07494a9 100644
--- a/crates/hir_ty/src/autoderef.rs
+++ b/crates/hir_ty/src/autoderef.rs
@@ -6,18 +6,15 @@
 use std::iter::successors;
 use base_db::CrateId;
-use chalk_ir::cast::Cast;
+use chalk_ir::{cast::Cast, fold::Fold, interner::HasInterner, VariableKind};
 use hir_def::lang_item::LangItemTarget;
 use hir_expand::name::name;
 use log::{info, warn};
 use crate::{
-    db::HirDatabase,
+    db::HirDatabase, static_lifetime, AliasEq, AliasTy, BoundVar, Canonical, CanonicalVarKinds,
-    to_assoc_type_id, to_chalk_trait_id,
+    DebruijnIndex, InEnvironment, Interner, ProjectionTyExt, Solution, Substitution, Ty, TyBuilder,
-    traits::{InEnvironment, Solution},
+    TyKind,
-    utils::generics,
-    AliasEq, AliasTy, BoundVar, Canonical, CanonicalVarKinds, DebruijnIndex, Interner,
-    ProjectionTy, Substitution, TraitRef, Ty, TyKind,
 };
 const AUTODEREF_RECURSION_LIMIT: usize = 10;
@@ -39,39 +36,48 @@ pub(crate) fn deref(
    krate: CrateId,
    ty: InEnvironment<&Canonical<Ty>>,
 ) -> Option<Canonical<Ty>> {
-    if let Some(derefed) = ty.goal.value.builtin_deref() {
+    let _p = profile::span("deref");
+    if let Some(derefed) = builtin_deref(&ty.goal.value) {
        Some(Canonical { value: derefed, binders: ty.goal.binders.clone() })
    } else {
        deref_by_trait(db, krate, ty)
    }
 }
+fn builtin_deref(ty: &Ty) -> Option<Ty> {
+    match ty.kind(&Interner) {
+        TyKind::Ref(.., ty) => Some(ty.clone()),
+        TyKind::Raw(.., ty) => Some(ty.clone()),
+        _ => None,
+    }
+}
 fn deref_by_trait(
    db: &dyn HirDatabase,
    krate: CrateId,
    ty: InEnvironment<&Canonical<Ty>>,
 ) -> Option<Canonical<Ty>> {
+    let _p = profile::span("deref_by_trait");
    let deref_trait = match db.lang_item(krate, "deref".into())? {
        LangItemTarget::TraitId(it) => it,
        _ => return None,
    };
    let target = db.trait_data(deref_trait).associated_type_by_name(&name![Target])?;
-    let generic_params = generics(db.upcast(), target.into());
+    let projection = {
-    if generic_params.len() != 1 {
+        let b = TyBuilder::assoc_type_projection(db, target);
-        // the Target type + Deref trait should only have one generic parameter,
+        if b.remaining() != 1 {
-        // namely Deref's Self type
+            // the Target type + Deref trait should only have one generic parameter,
-        return None;
+            // 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 =
+    let trait_ref = projection.trait_ref(db);
-        TraitRef { trait_id: to_chalk_trait_id(deref_trait), substitution: parameters.clone() };
    let implements_goal = Canonical {
        binders: ty.goal.binders.clone(),
        value: InEnvironment {
@@ -84,11 +90,8 @@ fn deref_by_trait(
    }
    // Now do the assoc type projection
-    let projection = AliasEq {
+    let alias_eq = AliasEq {
-        alias: AliasTy::Projection(ProjectionTy {
+        alias: AliasTy::Projection(projection),
-            associated_ty_id: to_assoc_type_id(target),
-            substitution: parameters,
-        }),
        ty: TyKind::BoundVar(BoundVar::new(
            DebruijnIndex::INNERMOST,
            ty.goal.binders.len(&Interner),
@@ -96,16 +99,14 @@ fn deref_by_trait(
        .intern(&Interner),
    };
-    let obligation = projection.cast(&Interner);
+    let in_env = InEnvironment { goal: alias_eq.cast(&Interner), environment: ty.environment };
-    let in_env = InEnvironment { goal: obligation, environment: ty.environment };
    let canonical = Canonical {
        value: in_env,
        binders: CanonicalVarKinds::from_iter(
            &Interner,
            ty.goal.binders.iter(&Interner).cloned().chain(Some(chalk_ir::WithKind::new(
-                chalk_ir::VariableKind::Ty(chalk_ir::TyVariableKind::General),
+                VariableKind::Ty(chalk_ir::TyVariableKind::General),
                chalk_ir::UniverseIndex::ROOT,
            ))),
        ),
@@ -130,18 +131,25 @@ fn deref_by_trait(
            // assumptions will be broken. We would need to properly introduce
            // new variables in that case
-            for i in 1..vars.0.binders.len(&Interner) {
+            for i in 1..vars.binders.len(&Interner) {
-                if vars.0.value[i - 1].interned(&Interner)
+                if vars.value.subst.at(&Interner, i - 1).assert_ty_ref(&Interner).kind(&Interner)
                    != &TyKind::BoundVar(BoundVar::new(DebruijnIndex::INNERMOST, i - 1))
                {
                    warn!("complex solution for derefing {:?}: {:?}, ignoring", ty.goal, solution);
                    return None;
                }
            }
-            Some(Canonical {
+            // FIXME: we remove lifetime variables here since they can confuse
-                value: vars.0.value[vars.0.value.len() - 1].clone(),
+            // the method resolution code later
-                binders: vars.0.binders.clone(),
+            Some(fixup_lifetime_variables(Canonical {
-            })
+                value: vars
+                    .value
+                    .subst
+                    .at(&Interner, vars.value.subst.len(&Interner) - 1)
+                    .assert_ty_ref(&Interner)
+                    .clone(),
+                binders: vars.binders.clone(),
+            }))
        }
        Solution::Ambig(_) => {
            info!("Ambiguous solution for derefing {:?}: {:?}", ty.goal, solution);
@@ -149,3 +157,32 @@ fn deref_by_trait(
        }
    }
 }
+fn fixup_lifetime_variables<T: Fold<Interner, Result = T> + HasInterner<Interner = Interner>>(
+    c: Canonical<T>,
+) -> Canonical<T> {
+    // Removes lifetime variables from the Canonical, replacing them by static lifetimes.
+    let mut i = 0;
+    let subst = Substitution::from_iter(
+        &Interner,
+        c.binders.iter(&Interner).map(|vk| match vk.kind {
+            VariableKind::Ty(_) => {
+                let index = i;
+                i += 1;
+                BoundVar::new(DebruijnIndex::INNERMOST, index).to_ty(&Interner).cast(&Interner)
+            }
+            VariableKind::Lifetime => static_lifetime().cast(&Interner),
+            VariableKind::Const(_) => unimplemented!(),
+        }),
+    );
+    let binders = CanonicalVarKinds::from_iter(
+        &Interner,
+        c.binders.iter(&Interner).filter(|vk| match vk.kind {
+            VariableKind::Ty(_) => true,
+            VariableKind::Lifetime => false,
+            VariableKind::Const(_) => true,
+        }),
+    );
+    let value = subst.apply(c.value, &Interner);
+    Canonical { binders, value }
+}
diff --git a/crates/hir_ty/src/builder.rs b/crates/hir_ty/src/builder.rs
new file mode 100644
index 000000000..e25ef866d
--- /dev/null
+++ b/crates/hir_ty/src/builder.rs
@@ -0,0 +1,223 @@
+//! `TyBuilder`, a helper for building instances of `Ty` and related types.
+use std::iter;
+use chalk_ir::{
+    cast::{Cast, CastTo, Caster},
+    fold::Fold,
+    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, FnSubst, GenericArg, Interner, ProjectionTy, Substitution,
+    TraitRef, Ty, TyDefId, TyExt, TyKind, 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);
+        let subst = Substitution::from_iter(&Interner, 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::Error.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_binders: 0,
+            sig: FnSig { abi: (), safety: Safety::Safe, variadic: sig.is_varargs },
+            substitution: FnSubst(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::from_iter(&Interner, self.vec.clone());
+                self.vec
+                    .push(default_ty.clone().substitute(&Interner, &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: HasInterner<Interner = Interner> + Fold<Interner>> TyBuilder<Binders<T>> {
+    fn subst_binders(b: Binders<T>) -> Self {
+        let param_count = b.binders.len(&Interner);
+        TyBuilder::new(b, param_count)
+    }
+    pub fn build(self) -> <T as Fold<Interner>>::Result {
+        let (b, subst) = self.build_internal();
+        b.substitute(&Interner, &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_cast.rs b/crates/hir_ty/src/chalk_cast.rs
deleted file mode 100644
index bf884ae15..000000000
--- a/crates/hir_ty/src/chalk_cast.rs
+++ /dev/null
@@ -1,53 +0,0 @@
-//! Implementations of the Chalk `Cast` trait for our types.
-use chalk_ir::{
-    cast::{Cast, CastTo},
-    interner::HasInterner,
-};
-use crate::{AliasEq, DomainGoal, Interner, TraitRef, WhereClause};
-macro_rules! has_interner {
-    ($t:ty) => {
-        impl HasInterner for $t {
-            type Interner = crate::Interner;
-        }
-    };
-}
-has_interner!(WhereClause);
-has_interner!(DomainGoal);
-impl CastTo<WhereClause> for TraitRef {
-    fn cast_to(self, _interner: &Interner) -> WhereClause {
-        WhereClause::Implemented(self)
-    }
-}
-impl CastTo<WhereClause> for AliasEq {
-    fn cast_to(self, _interner: &Interner) -> WhereClause {
-        WhereClause::AliasEq(self)
-    }
-}
-impl CastTo<DomainGoal> for WhereClause {
-    fn cast_to(self, _interner: &Interner) -> DomainGoal {
-        DomainGoal::Holds(self)
-    }
-}
-macro_rules! transitive_impl {
-    ($a:ty, $b:ty, $c:ty) => {
-        impl CastTo<$c> for $a {
-            fn cast_to(self, interner: &Interner) -> $c {
-                self.cast::<$b>(interner).cast(interner)
-            }
-        }
-    };
-}
-// In Chalk, these can be done as blanket impls, but that doesn't work here
-// because of coherence
-transitive_impl!(TraitRef, WhereClause, DomainGoal);
-transitive_impl!(AliasEq, WhereClause, DomainGoal);
diff --git a/crates/hir_ty/src/traits/chalk.rs b/crates/hir_ty/src/chalk_db.rs
index 011bef6f6..8f054d06b 100644
--- a/crates/hir_ty/src/traits/chalk.rs
+++ b/crates/hir_ty/src/chalk_db.rs
@@ -1,52 +1,47 @@
-//! Conversion code from/to Chalk.
+//! The implementation of `RustIrDatabase` for Chalk, which provides information
+//! about the code that Chalk needs.
 use std::sync::Arc;
 use log::debug;
-use chalk_ir::{fold::shift::Shift, CanonicalVarKinds, GenericArg};
+use chalk_ir::{cast::Cast, fold::shift::Shift, CanonicalVarKinds};
 use chalk_solve::rust_ir::{self, OpaqueTyDatumBound, WellKnownTrait};
-use base_db::{salsa::InternKey, CrateId};
+use base_db::CrateId;
 use hir_def::{
    lang_item::{lang_attr, LangItemTarget},
-    AssocContainerId, AssocItemId, HasModule, Lookup, TypeAliasId,
+    AssocContainerId, AssocItemId, GenericDefId, HasModule, Lookup, TypeAliasId,
 };
 use hir_expand::name::name;
-use super::ChalkContext;
 use crate::{
    db::HirDatabase,
    display::HirDisplay,
-    from_assoc_type_id,
+    from_assoc_type_id, from_chalk_trait_id, make_only_type_binders,
+    mapping::{from_chalk, ToChalk, TypeAliasAsValue},
    method_resolution::{TyFingerprint, ALL_FLOAT_FPS, ALL_INT_FPS},
    to_assoc_type_id, to_chalk_trait_id,
+    traits::ChalkContext,
    utils::generics,
-    AliasEq, AliasTy, BoundVar, CallableDefId, DebruijnIndex, FnDefId, ProjectionTy, Substitution,
+    AliasEq, AliasTy, BoundVar, CallableDefId, DebruijnIndex, FnDefId, Interner, ProjectionTy,
-    TraitRef, Ty, TyKind, WhereClause,
+    ProjectionTyExt, QuantifiedWhereClause, Substitution, TraitRef, TraitRefExt, Ty, TyBuilder,
+    TyExt, TyKind, WhereClause,
 };
-use mapping::{
-    convert_where_clauses, generic_predicate_to_inline_bound, make_binders, TypeAliasAsValue,
-};
-pub use self::interner::Interner;
-pub(crate) use self::interner::*;
-pub(super) mod tls;
+pub(crate) type AssociatedTyDatum = chalk_solve::rust_ir::AssociatedTyDatum<Interner>;
-mod interner;
+pub(crate) type TraitDatum = chalk_solve::rust_ir::TraitDatum<Interner>;
-mod mapping;
+pub(crate) type StructDatum = chalk_solve::rust_ir::AdtDatum<Interner>;
+pub(crate) type ImplDatum = chalk_solve::rust_ir::ImplDatum<Interner>;
-pub(crate) trait ToChalk {
+pub(crate) type OpaqueTyDatum = chalk_solve::rust_ir::OpaqueTyDatum<Interner>;
-    type Chalk;
-    fn to_chalk(self, db: &dyn HirDatabase) -> Self::Chalk;
+pub(crate) type AssocTypeId = chalk_ir::AssocTypeId<Interner>;
-    fn from_chalk(db: &dyn HirDatabase, chalk: Self::Chalk) -> Self;
+pub(crate) type TraitId = chalk_ir::TraitId<Interner>;
-}
+pub(crate) type AdtId = chalk_ir::AdtId<Interner>;
+pub(crate) type ImplId = chalk_ir::ImplId<Interner>;
-pub(crate) fn from_chalk<T, ChalkT>(db: &dyn HirDatabase, chalk: ChalkT) -> T
+pub(crate) type AssociatedTyValueId = chalk_solve::rust_ir::AssociatedTyValueId<Interner>;
-where
+pub(crate) type AssociatedTyValue = chalk_solve::rust_ir::AssociatedTyValue<Interner>;
-    T: ToChalk<Chalk = ChalkT>,
+pub(crate) type FnDefDatum = chalk_solve::rust_ir::FnDefDatum<Interner>;
-{
+pub(crate) type Variances = chalk_ir::Variances<Interner>;
-    T::from_chalk(db, chalk)
-}
 impl<'a> chalk_solve::RustIrDatabase<Interner> for ChalkContext<'a> {
    fn associated_ty_data(&self, id: AssocTypeId) -> Arc<AssociatedTyDatum> {
@@ -80,19 +75,19 @@ impl<'a> chalk_solve::RustIrDatabase<Interner> for ChalkContext<'a> {
    fn impls_for_trait(
        &self,
        trait_id: TraitId,
-        parameters: &[GenericArg<Interner>],
+        parameters: &[chalk_ir::GenericArg<Interner>],
        binders: &CanonicalVarKinds<Interner>,
    ) -> Vec<ImplId> {
        debug!("impls_for_trait {:?}", trait_id);
-        let trait_: hir_def::TraitId = from_chalk(self.db, trait_id);
+        let trait_: hir_def::TraitId = from_chalk_trait_id(trait_id);
-        let ty: Ty = from_chalk(self.db, parameters[0].assert_ty_ref(&Interner).clone());
+        let ty: Ty = parameters[0].assert_ty_ref(&Interner).clone();
        fn binder_kind(
            ty: &Ty,
            binders: &CanonicalVarKinds<Interner>,
        ) -> Option<chalk_ir::TyVariableKind> {
-            if let TyKind::BoundVar(bv) = ty.interned(&Interner) {
+            if let TyKind::BoundVar(bv) = ty.kind(&Interner) {
                let binders = binders.as_slice(&Interner);
                if bv.debruijn == DebruijnIndex::INNERMOST {
                    if let chalk_ir::VariableKind::Ty(tk) = binders[bv.index].kind {
@@ -103,7 +98,7 @@ impl<'a> chalk_solve::RustIrDatabase<Interner> for ChalkContext<'a> {
            None
        }
-        let self_ty_fp = TyFingerprint::for_impl(&ty);
+        let self_ty_fp = TyFingerprint::for_trait_impl(&ty);
        let fps: &[TyFingerprint] = match binder_kind(&ty, binders) {
            Some(chalk_ir::TyVariableKind::Integer) => &ALL_INT_FPS,
            Some(chalk_ir::TyVariableKind::Float) => &ALL_FLOAT_FPS,
@@ -166,7 +161,7 @@ impl<'a> chalk_solve::RustIrDatabase<Interner> for ChalkContext<'a> {
            Some(LangItemTarget::TraitId(trait_)) => trait_,
            _ => return None,
        };
-        Some(trait_.to_chalk(self.db))
+        Some(to_chalk_trait_id(trait_))
    }
    fn program_clauses_for_env(
@@ -184,16 +179,16 @@ impl<'a> chalk_solve::RustIrDatabase<Interner> for ChalkContext<'a> {
                    .db
                    .return_type_impl_traits(func)
                    .expect("impl trait id without impl traits");
-                let data = &datas.value.impl_traits[idx as usize];
+                let (datas, binders) = (*datas).as_ref().into_value_and_skipped_binders();
+                let data = &datas.impl_traits[idx as usize];
                let bound = OpaqueTyDatumBound {
-                    bounds: make_binders(
+                    bounds: make_only_type_binders(
-                        data.bounds.value.iter().cloned().map(|b| b.to_chalk(self.db)).collect(),
                        1,
+                        data.bounds.skip_binders().iter().cloned().collect(),
                    ),
-                    where_clauses: make_binders(vec![], 0),
+                    where_clauses: make_only_type_binders(0, vec![]),
                };
-                let num_vars = datas.num_binders;
+                chalk_ir::Binders::new(binders, bound)
-                make_binders(bound, num_vars)
            }
            crate::ImplTraitId::AsyncBlockTypeImplTrait(..) => {
                if let Some((future_trait, future_output)) = self
@@ -215,7 +210,8 @@ impl<'a> chalk_solve::RustIrDatabase<Interner> for ChalkContext<'a> {
                    let impl_bound = WhereClause::Implemented(TraitRef {
                        trait_id: to_chalk_trait_id(future_trait),
                        // Self type as the first parameter.
-                        substitution: Substitution::single(
+                        substitution: Substitution::from1(
+                            &Interner,
                            TyKind::BoundVar(BoundVar {
                                debruijn: DebruijnIndex::INNERMOST,
                                index: 0,
@@ -227,7 +223,8 @@ impl<'a> chalk_solve::RustIrDatabase<Interner> for ChalkContext<'a> {
                        alias: AliasTy::Projection(ProjectionTy {
                            associated_ty_id: to_assoc_type_id(future_output),
                            // Self type as the first parameter.
-                            substitution: Substitution::single(
+                            substitution: Substitution::from1(
+                                &Interner,
                                TyKind::BoundVar(BoundVar::new(DebruijnIndex::INNERMOST, 0))
                                    .intern(&Interner),
                            ),
@@ -237,25 +234,25 @@ impl<'a> chalk_solve::RustIrDatabase<Interner> for ChalkContext<'a> {
                            .intern(&Interner),
                    });
                    let bound = OpaqueTyDatumBound {
-                        bounds: make_binders(
+                        bounds: make_only_type_binders(
+                            1,
                            vec![
-                                wrap_in_empty_binders(impl_bound).to_chalk(self.db),
+                                crate::wrap_empty_binders(impl_bound),
-                                wrap_in_empty_binders(proj_bound).to_chalk(self.db),
+                                crate::wrap_empty_binders(proj_bound),
                            ],
-                            1,
                        ),
-                        where_clauses: make_binders(vec![], 0),
+                        where_clauses: make_only_type_binders(0, vec![]),
                    };
                    // The opaque type has 1 parameter.
-                    make_binders(bound, 1)
+                    make_only_type_binders(1, bound)
                } else {
                    // If failed to find Symbol’s value as variable is void: Future::Output, return empty bounds as fallback.
                    let bound = OpaqueTyDatumBound {
-                        bounds: make_binders(vec![], 0),
+                        bounds: make_only_type_binders(0, vec![]),
-                        where_clauses: make_binders(vec![], 0),
+                        where_clauses: make_only_type_binders(0, vec![]),
                    };
                    // The opaque type has 1 parameter.
-                    make_binders(bound, 1)
+                    make_only_type_binders(1, bound)
                }
            }
        };
@@ -265,7 +262,7 @@ impl<'a> chalk_solve::RustIrDatabase<Interner> for ChalkContext<'a> {
    fn hidden_opaque_type(&self, _id: chalk_ir::OpaqueTyId<Interner>) -> chalk_ir::Ty<Interner> {
        // FIXME: actually provide the hidden type; it is relevant for auto traits
-        TyKind::Unknown.intern(&Interner).to_chalk(self.db)
+        TyKind::Error.intern(&Interner)
    }
    fn is_object_safe(&self, _trait_id: chalk_ir::TraitId<Interner>) -> bool {
@@ -286,33 +283,32 @@ impl<'a> chalk_solve::RustIrDatabase<Interner> for ChalkContext<'a> {
        _closure_id: chalk_ir::ClosureId<Interner>,
        substs: &chalk_ir::Substitution<Interner>,
    ) -> chalk_ir::Binders<rust_ir::FnDefInputsAndOutputDatum<Interner>> {
-        let sig_ty: Ty =
+        let sig_ty = substs.at(&Interner, 0).assert_ty_ref(&Interner).clone();
-            from_chalk(self.db, substs.at(&Interner, 0).assert_ty_ref(&Interner).clone());
        let sig = &sig_ty.callable_sig(self.db).expect("first closure param should be fn ptr");
        let io = rust_ir::FnDefInputsAndOutputDatum {
-            argument_types: sig.params().iter().map(|ty| ty.clone().to_chalk(self.db)).collect(),
+            argument_types: sig.params().iter().cloned().collect(),
-            return_type: sig.ret().clone().to_chalk(self.db),
+            return_type: sig.ret().clone(),
        };
-        make_binders(io.shifted_in(&Interner), 0)
+        make_only_type_binders(0, io.shifted_in(&Interner))
    }
    fn closure_upvars(
        &self,
        _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();
-        make_binders(ty, 0)
+        make_only_type_binders(0, ty)
    }
    fn closure_fn_substitution(
        &self,
        _closure_id: chalk_ir::ClosureId<Interner>,
        _substs: &chalk_ir::Substitution<Interner>,
    ) -> chalk_ir::Substitution<Interner> {
-        Substitution::empty().to_chalk(self.db)
+        Substitution::empty(&Interner)
    }
    fn trait_name(&self, trait_id: chalk_ir::TraitId<Interner>) -> String {
-        let id = from_chalk(self.db, trait_id);
+        let id = from_chalk_trait_id(trait_id);
        self.db.trait_data(id).name.to_string()
    }
    fn adt_name(&self, chalk_ir::AdtId(adt_id): AdtId) -> String {
@@ -387,7 +383,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);
@@ -403,10 +399,10 @@ pub(crate) fn associated_ty_data_query(
    let where_clauses = convert_where_clauses(db, type_alias.into(), &bound_vars);
    let bound_data = rust_ir::AssociatedTyDatumBound { bounds, where_clauses };
    let datum = AssociatedTyDatum {
-        trait_id: trait_.to_chalk(db),
+        trait_id: to_chalk_trait_id(trait_),
        id,
        name: type_alias,
-        binders: make_binders(bound_data, generic_params.len()),
+        binders: make_only_type_binders(generic_params.len(), bound_data),
    };
    Arc::new(datum)
 }
@@ -417,11 +413,11 @@ pub(crate) fn trait_datum_query(
    trait_id: TraitId,
 ) -> Arc<TraitDatum> {
    debug!("trait_datum {:?}", trait_id);
-    let trait_: hir_def::TraitId = from_chalk(db, trait_id);
+    let trait_ = from_chalk_trait_id(trait_id);
    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,
@@ -439,7 +435,7 @@ pub(crate) fn trait_datum_query(
        lang_attr(db.upcast(), trait_).and_then(|name| well_known_trait_from_lang_attr(&name));
    let trait_datum = TraitDatum {
        id: trait_id,
-        binders: make_binders(trait_datum_bound, bound_vars.len()),
+        binders: make_only_type_binders(bound_vars.len(&Interner), trait_datum_bound),
        flags,
        associated_ty_ids,
        well_known,
@@ -490,7 +486,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 {
@@ -508,7 +504,7 @@ pub(crate) fn struct_datum_query(
        // FIXME set ADT kind
        kind: rust_ir::AdtKind::Struct,
        id: struct_id,
-        binders: make_binders(struct_datum_bound, num_params),
+        binders: make_only_type_binders(num_params, struct_datum_bound),
        flags,
    };
    Arc::new(struct_datum)
@@ -535,11 +531,12 @@ fn impl_def_datum(
        .impl_trait(impl_id)
        // ImplIds for impls where the trait ref can't be resolved should never reach Chalk
        .expect("invalid impl passed to Chalk")
-        .value;
+        .into_value_and_skipped_binders()
+        .0;
    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
@@ -555,7 +552,6 @@ fn impl_def_datum(
        trait_ref.display(db),
        where_clauses
    );
-    let trait_ref = trait_ref.to_chalk(db);
    let polarity = if negative { rust_ir::Polarity::Negative } else { rust_ir::Polarity::Positive };
@@ -577,7 +573,7 @@ fn impl_def_datum(
        .collect();
    debug!("impl_datum: {:?}", impl_datum_bound);
    let impl_datum = ImplDatum {
-        binders: make_binders(impl_datum_bound, bound_vars.len()),
+        binders: make_only_type_binders(bound_vars.len(&Interner), impl_datum_bound),
        impl_type,
        polarity,
        associated_ty_value_ids,
@@ -605,18 +601,22 @@ fn type_alias_associated_ty_value(
        _ => panic!("assoc ty value should be in impl"),
    };
-    let trait_ref = db.impl_trait(impl_id).expect("assoc ty value should not exist").value; // we don't return any assoc ty values if the impl'd trait can't be resolved
+    let trait_ref = db
+        .impl_trait(impl_id)
+        .expect("assoc ty value should not exist")
+        .into_value_and_skipped_binders()
+        .0; // we don't return any assoc ty values if the impl'd trait can't be resolved
    let assoc_ty = db
        .trait_data(trait_ref.hir_trait_id())
        .associated_type_by_name(&type_alias_data.name)
        .expect("assoc ty value should not exist"); // validated when building the impl data as well
-    let ty = db.ty(type_alias.into());
+    let (ty, binders) = db.ty(type_alias.into()).into_value_and_skipped_binders();
-    let value_bound = rust_ir::AssociatedTyValueBound { ty: ty.value.to_chalk(db) };
+    let value_bound = rust_ir::AssociatedTyValueBound { ty };
    let value = rust_ir::AssociatedTyValue {
        impl_id: impl_id.to_chalk(db),
        associated_ty_id: to_assoc_type_id(assoc_ty),
-        value: make_binders(value_bound, ty.num_binders),
+        value: chalk_ir::Binders::new(binders, value_bound),
    };
    Arc::new(value)
 }
@@ -628,34 +628,25 @@ pub(crate) fn fn_def_datum_query(
 ) -> Arc<FnDefDatum> {
    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 (sig, binders) = db.callable_item_signature(callable_def).into_value_and_skipped_binders();
-    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
-        inputs_and_output: make_binders(
+        inputs_and_output: make_only_type_binders(
+            0,
            rust_ir::FnDefInputsAndOutputDatum {
-                argument_types: sig
+                argument_types: sig.params().iter().cloned().collect(),
-                    .value
+                return_type: sig.ret().clone(),
-                    .params()
-                    .iter()
-                    .map(|ty| ty.clone().to_chalk(db))
-                    .collect(),
-                return_type: sig.value.ret().clone().to_chalk(db),
            }
            .shifted_in(&Interner),
-            0,
        ),
        where_clauses,
    };
    let datum = FnDefDatum {
        id: fn_def_id,
-        sig: chalk_ir::FnSig {
+        sig: chalk_ir::FnSig { abi: (), safety: chalk_ir::Safety::Safe, variadic: sig.is_varargs },
-            abi: (),
+        binders: chalk_ir::Binders::new(binders, bound),
-            safety: chalk_ir::Safety::Safe,
-            variadic: sig.value.is_varargs,
-        },
-        binders: make_binders(bound, sig.num_binders),
    };
    Arc::new(datum)
 }
@@ -685,42 +676,65 @@ pub(crate) fn adt_variance_query(
    )
 }
-impl From<FnDefId> for crate::db::InternedCallableDefId {
+pub(super) fn convert_where_clauses(
-    fn from(fn_def_id: FnDefId) -> Self {
+    db: &dyn HirDatabase,
-        InternKey::from_intern_id(fn_def_id.0)
+    def: GenericDefId,
-    }
+    substs: &Substitution,
-}
+) -> Vec<chalk_ir::QuantifiedWhereClause<Interner>> {
+    let generic_predicates = db.generic_predicates(def);
-impl From<crate::db::InternedCallableDefId> for FnDefId {
+    let mut result = Vec::with_capacity(generic_predicates.len());
-    fn from(callable_def_id: crate::db::InternedCallableDefId) -> Self {
+    for pred in generic_predicates.iter() {
-        chalk_ir::FnDefId(callable_def_id.as_intern_id())
+        result.push(pred.clone().substitute(&Interner, substs));
-    }
+    }
-}
+    result
-impl From<OpaqueTyId> for crate::db::InternedOpaqueTyId {
-    fn from(id: OpaqueTyId) -> Self {
-        InternKey::from_intern_id(id.0)
-    }
-}
-impl From<crate::db::InternedOpaqueTyId> for OpaqueTyId {
-    fn from(id: crate::db::InternedOpaqueTyId) -> Self {
-        chalk_ir::OpaqueTyId(id.as_intern_id())
-    }
-}
-impl From<chalk_ir::ClosureId<Interner>> for crate::db::InternedClosureId {
-    fn from(id: chalk_ir::ClosureId<Interner>) -> Self {
-        Self::from_intern_id(id.0)
-    }
 }
-impl From<crate::db::InternedClosureId> for chalk_ir::ClosureId<Interner> {
+pub(super) fn generic_predicate_to_inline_bound(
-    fn from(id: crate::db::InternedClosureId) -> Self {
+    db: &dyn HirDatabase,
-        chalk_ir::ClosureId(id.as_intern_id())
+    pred: &QuantifiedWhereClause,
+    self_ty: &Ty,
+) -> Option<chalk_ir::Binders<rust_ir::InlineBound<Interner>>> {
+    // An InlineBound is like a GenericPredicate, except the self type is left out.
+    // We don't have a special type for this, but Chalk does.
+    let self_ty_shifted_in = self_ty.clone().shifted_in_from(&Interner, DebruijnIndex::ONE);
+    let (pred, binders) = pred.as_ref().into_value_and_skipped_binders();
+    match pred {
+        WhereClause::Implemented(trait_ref) => {
+            if trait_ref.self_type_parameter(&Interner) != self_ty_shifted_in {
+                // we can only convert predicates back to type bounds if they
+                // have the expected self type
+                return None;
+            }
+            let args_no_self = trait_ref.substitution.as_slice(&Interner)[1..]
+                .iter()
+                .map(|ty| ty.clone().cast(&Interner))
+                .collect();
+            let trait_bound = rust_ir::TraitBound { trait_id: trait_ref.trait_id, args_no_self };
+            Some(chalk_ir::Binders::new(binders, rust_ir::InlineBound::TraitBound(trait_bound)))
+        }
+        WhereClause::AliasEq(AliasEq { alias: AliasTy::Projection(projection_ty), ty }) => {
+            if projection_ty.self_type_parameter(&Interner) != self_ty_shifted_in {
+                return None;
+            }
+            let trait_ = projection_ty.trait_(db);
+            let args_no_self = projection_ty.substitution.as_slice(&Interner)[1..]
+                .iter()
+                .map(|ty| ty.clone().cast(&Interner))
+                .collect();
+            let alias_eq_bound = rust_ir::AliasEqBound {
+                value: ty.clone(),
+                trait_bound: rust_ir::TraitBound {
+                    trait_id: to_chalk_trait_id(trait_),
+                    args_no_self,
+                },
+                associated_ty_id: projection_ty.associated_ty_id,
+                parameters: Vec::new(), // FIXME we don't support generic associated types yet
+            };
+            Some(chalk_ir::Binders::new(
+                binders,
+                rust_ir::InlineBound::AliasEqBound(alias_eq_bound),
+            ))
+        }
+        _ => None,
    }
 }
-fn wrap_in_empty_binders<T: crate::TypeWalk>(value: T) -> crate::Binders<T> {
-    crate::Binders::wrap_empty(value)
-}
diff --git a/crates/hir_ty/src/chalk_ext.rs b/crates/hir_ty/src/chalk_ext.rs
new file mode 100644
index 000000000..8c4542956
--- /dev/null
+++ b/crates/hir_ty/src/chalk_ext.rs
@@ -0,0 +1,305 @@
+//! Various extensions traits for Chalk types.
+use chalk_ir::Mutability;
+use hir_def::{
+    type_ref::Rawness, AssocContainerId, FunctionId, GenericDefId, HasModule, Lookup, TraitId,
+};
+use crate::{
+    db::HirDatabase, from_assoc_type_id, from_chalk_trait_id, from_foreign_def_id,
+    from_placeholder_idx, to_chalk_trait_id, AdtId, AliasEq, AliasTy, Binders, CallableDefId,
+    CallableSig, FnPointer, ImplTraitId, Interner, Lifetime, ProjectionTy, QuantifiedWhereClause,
+    Substitution, TraitRef, Ty, TyBuilder, TyKind, WhereClause,
+};
+pub trait TyExt {
+    fn is_unit(&self) -> bool;
+    fn is_never(&self) -> bool;
+    fn is_unknown(&self) -> bool;
+    fn as_adt(&self) -> Option<(hir_def::AdtId, &Substitution)>;
+    fn as_tuple(&self) -> Option<&Substitution>;
+    fn as_fn_def(&self, db: &dyn HirDatabase) -> Option<FunctionId>;
+    fn as_reference(&self) -> Option<(&Ty, Lifetime, Mutability)>;
+    fn as_reference_or_ptr(&self) -> Option<(&Ty, Rawness, Mutability)>;
+    fn as_generic_def(&self, db: &dyn HirDatabase) -> Option<GenericDefId>;
+    fn callable_def(&self, db: &dyn HirDatabase) -> Option<CallableDefId>;
+    fn callable_sig(&self, db: &dyn HirDatabase) -> Option<CallableSig>;
+    fn strip_references(&self) -> &Ty;
+    /// If this is a `dyn Trait`, returns that trait.
+    fn dyn_trait(&self) -> Option<TraitId>;
+    fn impl_trait_bounds(&self, db: &dyn HirDatabase) -> Option<Vec<QuantifiedWhereClause>>;
+    fn associated_type_parent_trait(&self, db: &dyn HirDatabase) -> Option<TraitId>;
+    /// FIXME: Get rid of this, it's not a good abstraction
+    fn equals_ctor(&self, other: &Ty) -> bool;
+}
+impl TyExt for Ty {
+    fn is_unit(&self) -> bool {
+        matches!(self.kind(&Interner), TyKind::Tuple(0, _))
+    }
+    fn is_never(&self) -> bool {
+        matches!(self.kind(&Interner), TyKind::Never)
+    }
+    fn is_unknown(&self) -> bool {
+        matches!(self.kind(&Interner), TyKind::Error)
+    }
+    fn as_adt(&self) -> Option<(hir_def::AdtId, &Substitution)> {
+        match self.kind(&Interner) {
+            TyKind::Adt(AdtId(adt), parameters) => Some((*adt, parameters)),
+            _ => None,
+        }
+    }
+    fn as_tuple(&self) -> Option<&Substitution> {
+        match self.kind(&Interner) {
+            TyKind::Tuple(_, substs) => Some(substs),
+            _ => None,
+        }
+    }
+    fn as_fn_def(&self, db: &dyn HirDatabase) -> Option<FunctionId> {
+        if let Some(CallableDefId::FunctionId(func)) = self.callable_def(db) {
+            Some(func)
+        } else {
+            None
+        }
+    }
+    fn as_reference(&self) -> Option<(&Ty, Lifetime, Mutability)> {
+        match self.kind(&Interner) {
+            TyKind::Ref(mutability, lifetime, ty) => Some((ty, lifetime.clone(), *mutability)),
+            _ => None,
+        }
+    }
+    fn as_reference_or_ptr(&self) -> Option<(&Ty, Rawness, Mutability)> {
+        match self.kind(&Interner) {
+            TyKind::Ref(mutability, _, ty) => Some((ty, Rawness::Ref, *mutability)),
+            TyKind::Raw(mutability, ty) => Some((ty, Rawness::RawPtr, *mutability)),
+            _ => None,
+        }
+    }
+    fn as_generic_def(&self, db: &dyn HirDatabase) -> Option<GenericDefId> {
+        match *self.kind(&Interner) {
+            TyKind::Adt(AdtId(adt), ..) => Some(adt.into()),
+            TyKind::FnDef(callable, ..) => {
+                Some(db.lookup_intern_callable_def(callable.into()).into())
+            }
+            TyKind::AssociatedType(type_alias, ..) => Some(from_assoc_type_id(type_alias).into()),
+            TyKind::Foreign(type_alias, ..) => Some(from_foreign_def_id(type_alias).into()),
+            _ => None,
+        }
+    }
+    fn callable_def(&self, db: &dyn HirDatabase) -> Option<CallableDefId> {
+        match self.kind(&Interner) {
+            &TyKind::FnDef(def, ..) => Some(db.lookup_intern_callable_def(def.into())),
+            _ => None,
+        }
+    }
+    fn callable_sig(&self, db: &dyn HirDatabase) -> Option<CallableSig> {
+        match self.kind(&Interner) {
+            TyKind::Function(fn_ptr) => Some(CallableSig::from_fn_ptr(fn_ptr)),
+            TyKind::FnDef(def, parameters) => {
+                let callable_def = db.lookup_intern_callable_def((*def).into());
+                let sig = db.callable_item_signature(callable_def);
+                Some(sig.substitute(&Interner, &parameters))
+            }
+            TyKind::Closure(.., substs) => {
+                let sig_param = substs.at(&Interner, 0).assert_ty_ref(&Interner);
+                sig_param.callable_sig(db)
+            }
+            _ => None,
+        }
+    }
+    fn dyn_trait(&self) -> Option<TraitId> {
+        let trait_ref = match self.kind(&Interner) {
+            TyKind::Dyn(dyn_ty) => dyn_ty.bounds.skip_binders().interned().get(0).and_then(|b| {
+                match b.skip_binders() {
+                    WhereClause::Implemented(trait_ref) => Some(trait_ref),
+                    _ => None,
+                }
+            }),
+            _ => None,
+        }?;
+        Some(from_chalk_trait_id(trait_ref.trait_id))
+    }
+    fn strip_references(&self) -> &Ty {
+        let mut t: &Ty = self;
+        while let TyKind::Ref(_mutability, _lifetime, ty) = t.kind(&Interner) {
+            t = ty;
+        }
+        t
+    }
+    fn impl_trait_bounds(&self, db: &dyn HirDatabase) -> Option<Vec<QuantifiedWhereClause>> {
+        match self.kind(&Interner) {
+            TyKind::OpaqueType(opaque_ty_id, ..) => {
+                match db.lookup_intern_impl_trait_id((*opaque_ty_id).into()) {
+                    ImplTraitId::AsyncBlockTypeImplTrait(def, _expr) => {
+                        let krate = def.module(db.upcast()).krate();
+                        if let Some(future_trait) = db
+                            .lang_item(krate, "future_trait".into())
+                            .and_then(|item| item.as_trait())
+                        {
+                            // This is only used by type walking.
+                            // Parameters will be walked outside, and projection predicate is not used.
+                            // So just provide the Future trait.
+                            let impl_bound = Binders::empty(
+                                &Interner,
+                                WhereClause::Implemented(TraitRef {
+                                    trait_id: to_chalk_trait_id(future_trait),
+                                    substitution: Substitution::empty(&Interner),
+                                }),
+                            );
+                            Some(vec![impl_bound])
+                        } else {
+                            None
+                        }
+                    }
+                    ImplTraitId::ReturnTypeImplTrait(..) => None,
+                }
+            }
+            TyKind::Alias(AliasTy::Opaque(opaque_ty)) => {
+                let predicates = match db.lookup_intern_impl_trait_id(opaque_ty.opaque_ty_id.into())
+                {
+                    ImplTraitId::ReturnTypeImplTrait(func, idx) => {
+                        db.return_type_impl_traits(func).map(|it| {
+                            let data = (*it)
+                                .as_ref()
+                                .map(|rpit| rpit.impl_traits[idx as usize].bounds.clone());
+                            data.substitute(&Interner, &opaque_ty.substitution)
+                        })
+                    }
+                    // It always has an parameter for Future::Output type.
+                    ImplTraitId::AsyncBlockTypeImplTrait(..) => unreachable!(),
+                };
+                predicates.map(|it| it.into_value_and_skipped_binders().0)
+            }
+            TyKind::Placeholder(idx) => {
+                let id = from_placeholder_idx(db, *idx);
+                let generic_params = db.generic_params(id.parent);
+                let param_data = &generic_params.types[id.local_id];
+                match param_data.provenance {
+                    hir_def::generics::TypeParamProvenance::ArgumentImplTrait => {
+                        let substs = TyBuilder::type_params_subst(db, id.parent);
+                        let predicates = db
+                            .generic_predicates(id.parent)
+                            .into_iter()
+                            .map(|pred| pred.clone().substitute(&Interner, &substs))
+                            .filter(|wc| match &wc.skip_binders() {
+                                WhereClause::Implemented(tr) => {
+                                    &tr.self_type_parameter(&Interner) == self
+                                }
+                                WhereClause::AliasEq(AliasEq {
+                                    alias: AliasTy::Projection(proj),
+                                    ty: _,
+                                }) => &proj.self_type_parameter(&Interner) == self,
+                                _ => false,
+                            })
+                            .collect::<Vec<_>>();
+                        Some(predicates)
+                    }
+                    _ => None,
+                }
+            }
+            _ => None,
+        }
+    }
+    fn associated_type_parent_trait(&self, db: &dyn HirDatabase) -> Option<TraitId> {
+        match self.kind(&Interner) {
+            TyKind::AssociatedType(id, ..) => {
+                match from_assoc_type_id(*id).lookup(db.upcast()).container {
+                    AssocContainerId::TraitId(trait_id) => Some(trait_id),
+                    _ => None,
+                }
+            }
+            TyKind::Alias(AliasTy::Projection(projection_ty)) => {
+                match from_assoc_type_id(projection_ty.associated_ty_id)
+                    .lookup(db.upcast())
+                    .container
+                {
+                    AssocContainerId::TraitId(trait_id) => Some(trait_id),
+                    _ => None,
+                }
+            }
+            _ => None,
+        }
+    }
+    fn equals_ctor(&self, other: &Ty) -> bool {
+        match (self.kind(&Interner), other.kind(&Interner)) {
+            (TyKind::Adt(adt, ..), TyKind::Adt(adt2, ..)) => adt == adt2,
+            (TyKind::Slice(_), TyKind::Slice(_)) | (TyKind::Array(_, _), TyKind::Array(_, _)) => {
+                true
+            }
+            (TyKind::FnDef(def_id, ..), TyKind::FnDef(def_id2, ..)) => def_id == def_id2,
+            (TyKind::OpaqueType(ty_id, ..), TyKind::OpaqueType(ty_id2, ..)) => ty_id == ty_id2,
+            (TyKind::AssociatedType(ty_id, ..), TyKind::AssociatedType(ty_id2, ..)) => {
+                ty_id == ty_id2
+            }
+            (TyKind::Foreign(ty_id, ..), TyKind::Foreign(ty_id2, ..)) => ty_id == ty_id2,
+            (TyKind::Closure(id1, _), TyKind::Closure(id2, _)) => id1 == id2,
+            (TyKind::Ref(mutability, ..), TyKind::Ref(mutability2, ..))
+            | (TyKind::Raw(mutability, ..), TyKind::Raw(mutability2, ..)) => {
+                mutability == mutability2
+            }
+            (
+                TyKind::Function(FnPointer { num_binders, sig, .. }),
+                TyKind::Function(FnPointer { num_binders: num_binders2, sig: sig2, .. }),
+            ) => num_binders == num_binders2 && sig == sig2,
+            (TyKind::Tuple(cardinality, _), TyKind::Tuple(cardinality2, _)) => {
+                cardinality == cardinality2
+            }
+            (TyKind::Str, TyKind::Str) | (TyKind::Never, TyKind::Never) => true,
+            (TyKind::Scalar(scalar), TyKind::Scalar(scalar2)) => scalar == scalar2,
+            _ => false,
+        }
+    }
+}
+pub trait ProjectionTyExt {
+    fn trait_ref(&self, db: &dyn HirDatabase) -> TraitRef;
+    fn trait_(&self, db: &dyn HirDatabase) -> TraitId;
+}
+impl ProjectionTyExt for ProjectionTy {
+    fn trait_ref(&self, db: &dyn HirDatabase) -> TraitRef {
+        TraitRef {
+            trait_id: to_chalk_trait_id(self.trait_(db)),
+            substitution: self.substitution.clone(),
+        }
+    }
+    fn trait_(&self, db: &dyn HirDatabase) -> TraitId {
+        match from_assoc_type_id(self.associated_ty_id).lookup(db.upcast()).container {
+            AssocContainerId::TraitId(it) => it,
+            _ => panic!("projection ty without parent trait"),
+        }
+    }
+}
+pub trait TraitRefExt {
+    fn hir_trait_id(&self) -> TraitId;
+}
+impl TraitRefExt for TraitRef {
+    fn hir_trait_id(&self) -> TraitId {
+        from_chalk_trait_id(self.trait_id)
+    }
+}
diff --git a/crates/hir_ty/src/db.rs b/crates/hir_ty/src/db.rs
index 58e4247c6..cf67d4266 100644
--- a/crates/hir_ty/src/db.rs
+++ b/crates/hir_ty/src/db.rs
@@ -1,18 +1,19 @@
-//! FIXME: write short doc here
+//! The home of `HirDatabase`, which is the Salsa database containing all the
+//! type inference-related queries.
 use std::sync::Arc;
 use base_db::{impl_intern_key, salsa, CrateId, Upcast};
 use hir_def::{
    db::DefDatabase, expr::ExprId, ConstParamId, DefWithBodyId, FunctionId, GenericDefId, ImplId,
-    LocalFieldId, TypeParamId, VariantId,
+    LifetimeParamId, LocalFieldId, TypeParamId, VariantId,
 };
 use la_arena::ArenaMap;
 use crate::{
+    chalk_db,
    method_resolution::{InherentImpls, TraitImpls},
-    traits::chalk,
+    Binders, CallableDefId, FnDefId, ImplTraitId, InferenceResult, Interner, PolyFnSig,
-    Binders, CallableDefId, FnDefId, ImplTraitId, InferenceResult, PolyFnSig,
    QuantifiedWhereClause, ReturnTypeImplTraits, TraitRef, Ty, TyDefId, ValueTyDefId,
 };
 use hir_expand::name::Name;
@@ -86,51 +87,68 @@ pub trait HirDatabase: DefDatabase + Upcast<dyn DefDatabase> {
    #[salsa::interned]
    fn intern_type_param_id(&self, param_id: TypeParamId) -> InternedTypeParamId;
    #[salsa::interned]
+    fn intern_lifetime_param_id(&self, param_id: LifetimeParamId) -> InternedLifetimeParamId;
+    #[salsa::interned]
+    fn intern_const_param_id(&self, param_id: ConstParamId) -> InternedConstParamId;
+    #[salsa::interned]
    fn intern_impl_trait_id(&self, id: ImplTraitId) -> InternedOpaqueTyId;
    #[salsa::interned]
    fn intern_closure(&self, id: (DefWithBodyId, ExprId)) -> InternedClosureId;
-    #[salsa::invoke(chalk::associated_ty_data_query)]
+    #[salsa::invoke(chalk_db::associated_ty_data_query)]
-    fn associated_ty_data(&self, id: chalk::AssocTypeId) -> Arc<chalk::AssociatedTyDatum>;
+    fn associated_ty_data(&self, id: chalk_db::AssocTypeId) -> Arc<chalk_db::AssociatedTyDatum>;
-    #[salsa::invoke(chalk::trait_datum_query)]
+    #[salsa::invoke(chalk_db::trait_datum_query)]
-    fn trait_datum(&self, krate: CrateId, trait_id: chalk::TraitId) -> Arc<chalk::TraitDatum>;
+    fn trait_datum(&self, krate: CrateId, trait_id: chalk_db::TraitId)
+        -> Arc<chalk_db::TraitDatum>;
-    #[salsa::invoke(chalk::struct_datum_query)]
+    #[salsa::invoke(chalk_db::struct_datum_query)]
-    fn struct_datum(&self, krate: CrateId, struct_id: chalk::AdtId) -> Arc<chalk::StructDatum>;
+    fn struct_datum(
+        &self,
+        krate: CrateId,
+        struct_id: chalk_db::AdtId,
+    ) -> Arc<chalk_db::StructDatum>;
-    #[salsa::invoke(crate::traits::chalk::impl_datum_query)]
+    #[salsa::invoke(chalk_db::impl_datum_query)]
-    fn impl_datum(&self, krate: CrateId, impl_id: chalk::ImplId) -> Arc<chalk::ImplDatum>;
+    fn impl_datum(&self, krate: CrateId, impl_id: chalk_db::ImplId) -> Arc<chalk_db::ImplDatum>;
-    #[salsa::invoke(crate::traits::chalk::fn_def_datum_query)]
+    #[salsa::invoke(chalk_db::fn_def_datum_query)]
-    fn fn_def_datum(&self, krate: CrateId, fn_def_id: FnDefId) -> Arc<chalk::FnDefDatum>;
+    fn fn_def_datum(&self, krate: CrateId, fn_def_id: FnDefId) -> Arc<chalk_db::FnDefDatum>;
-    #[salsa::invoke(crate::traits::chalk::fn_def_variance_query)]
+    #[salsa::invoke(chalk_db::fn_def_variance_query)]
-    fn fn_def_variance(&self, krate: CrateId, fn_def_id: FnDefId) -> chalk::Variances;
+    fn fn_def_variance(&self, krate: CrateId, fn_def_id: FnDefId) -> chalk_db::Variances;
-    #[salsa::invoke(crate::traits::chalk::adt_variance_query)]
+    #[salsa::invoke(chalk_db::adt_variance_query)]
-    fn adt_variance(&self, krate: CrateId, adt_id: chalk::AdtId) -> chalk::Variances;
+    fn adt_variance(&self, krate: CrateId, adt_id: chalk_db::AdtId) -> chalk_db::Variances;
-    #[salsa::invoke(crate::traits::chalk::associated_ty_value_query)]
+    #[salsa::invoke(chalk_db::associated_ty_value_query)]
    fn associated_ty_value(
        &self,
        krate: CrateId,
-        id: chalk::AssociatedTyValueId,
+        id: chalk_db::AssociatedTyValueId,
-    ) -> Arc<chalk::AssociatedTyValue>;
+    ) -> Arc<chalk_db::AssociatedTyValue>;
-    #[salsa::invoke(crate::traits::trait_solve_query)]
+    #[salsa::invoke(trait_solve_wait)]
+    #[salsa::transparent]
    fn trait_solve(
        &self,
        krate: CrateId,
        goal: crate::Canonical<crate::InEnvironment<crate::DomainGoal>>,
-    ) -> Option<crate::traits::Solution>;
+    ) -> Option<crate::Solution>;
-    #[salsa::invoke(crate::traits::chalk::program_clauses_for_chalk_env_query)]
+    #[salsa::invoke(crate::traits::trait_solve_query)]
+    fn trait_solve_query(
+        &self,
+        krate: CrateId,
+        goal: crate::Canonical<crate::InEnvironment<crate::DomainGoal>>,
+    ) -> Option<crate::Solution>;
+    #[salsa::invoke(chalk_db::program_clauses_for_chalk_env_query)]
    fn program_clauses_for_chalk_env(
        &self,
        krate: CrateId,
-        env: chalk_ir::Environment<chalk::Interner>,
+        env: chalk_ir::Environment<Interner>,
-    ) -> chalk_ir::ProgramClauses<chalk::Interner>;
+    ) -> chalk_ir::ProgramClauses<Interner>;
 }
 fn infer_wait(db: &dyn HirDatabase, def: DefWithBodyId) -> Arc<InferenceResult> {
@@ -146,6 +164,15 @@ fn infer_wait(db: &dyn HirDatabase, def: DefWithBodyId) -> Arc<InferenceResult>
    db.infer_query(def)
 }
+fn trait_solve_wait(
+    db: &dyn HirDatabase,
+    krate: CrateId,
+    goal: crate::Canonical<crate::InEnvironment<crate::DomainGoal>>,
+) -> Option<crate::Solution> {
+    let _p = profile::span("trait_solve::wait");
+    db.trait_solve_query(krate, goal)
+}
 #[test]
 fn hir_database_is_object_safe() {
    fn _assert_object_safe(_: &dyn HirDatabase) {}
@@ -156,6 +183,14 @@ pub struct InternedTypeParamId(salsa::InternId);
 impl_intern_key!(InternedTypeParamId);
 #[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
+pub struct InternedLifetimeParamId(salsa::InternId);
+impl_intern_key!(InternedLifetimeParamId);
+#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
+pub struct InternedConstParamId(salsa::InternId);
+impl_intern_key!(InternedConstParamId);
+#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
 pub struct InternedOpaqueTyId(salsa::InternId);
 impl_intern_key!(InternedOpaqueTyId);
diff --git a/crates/hir_ty/src/diagnostics.rs b/crates/hir_ty/src/diagnostics.rs
index 86f937e1d..84fc8ce14 100644
--- a/crates/hir_ty/src/diagnostics.rs
+++ b/crates/hir_ty/src/diagnostics.rs
@@ -1,4 +1,4 @@
-//! FIXME: write short doc here
+//! Type inference-based diagnostics.
 mod expr;
 mod match_check;
 mod unsafe_check;
diff --git a/crates/hir_ty/src/diagnostics/decl_check.rs b/crates/hir_ty/src/diagnostics/decl_check.rs
index 33a0f4d7d..075dc4131 100644
--- a/crates/hir_ty/src/diagnostics/decl_check.rs
+++ b/crates/hir_ty/src/diagnostics/decl_check.rs
@@ -35,6 +35,8 @@ use crate::{
 };
 mod allow {
+    pub(super) const BAD_STYLE: &str = "bad_style";
+    pub(super) const NONSTANDARD_STYLE: &str = "nonstandard_style";
    pub(super) const NON_SNAKE_CASE: &str = "non_snake_case";
    pub(super) const NON_UPPER_CASE_GLOBAL: &str = "non_upper_case_globals";
    pub(super) const NON_CAMEL_CASE_TYPES: &str = "non_camel_case_types";
@@ -83,15 +85,44 @@ impl<'a, 'b> DeclValidator<'a, 'b> {
    }
    /// Checks whether not following the convention is allowed for this item.
-    ///
+    fn allowed(&self, id: AttrDefId, allow_name: &str, recursing: bool) -> bool {
-    /// Currently this method doesn't check parent attributes.
+        let is_allowed = |def_id| {
-    fn allowed(&self, id: AttrDefId, allow_name: &str) -> bool {
+            let attrs = self.db.attrs(def_id);
-        self.db.attrs(id).by_key("allow").tt_values().any(|tt| tt.to_string().contains(allow_name))
+            // don't bug the user about directly no_mangle annotated stuff, they can't do anything about it
+            (!recursing && attrs.by_key("no_mangle").exists())
+                || attrs.by_key("allow").tt_values().any(|tt| {
+                    let allows = tt.to_string();
+                    allows.contains(allow_name)
+                        || allows.contains(allow::BAD_STYLE)
+                        || allows.contains(allow::NONSTANDARD_STYLE)
+                })
+        };
+        is_allowed(id)
+            // go upwards one step or give up
+            || match id {
+                AttrDefId::ModuleId(m) => m.containing_module(self.db.upcast()).map(|v| v.into()),
+                AttrDefId::FunctionId(f) => Some(f.lookup(self.db.upcast()).container.into()),
+                AttrDefId::StaticId(sid) => Some(sid.lookup(self.db.upcast()).container.into()),
+                AttrDefId::ConstId(cid) => Some(cid.lookup(self.db.upcast()).container.into()),
+                AttrDefId::TraitId(tid) => Some(tid.lookup(self.db.upcast()).container.into()),
+                AttrDefId::ImplId(iid) => Some(iid.lookup(self.db.upcast()).container.into()),
+                // These warnings should not explore macro definitions at all
+                AttrDefId::MacroDefId(_) => None,
+                // Will never occur under an enum/struct/union/type alias
+                AttrDefId::AdtId(_) => None,
+                AttrDefId::FieldId(_) => None,
+                AttrDefId::EnumVariantId(_) => None,
+                AttrDefId::TypeAliasId(_) => None,
+                AttrDefId::GenericParamId(_) => None,
+            }
+            .map(|mid| self.allowed(mid, allow_name, true))
+            .unwrap_or(false)
    }
    fn validate_func(&mut self, func: FunctionId) {
        let data = self.db.function_data(func);
-        if data.is_in_extern_block {
+        if data.is_in_extern_block() {
            cov_mark::hit!(extern_func_incorrect_case_ignored);
            return;
        }
@@ -99,8 +130,7 @@ impl<'a, 'b> DeclValidator<'a, 'b> {
        let body = self.db.body(func.into());
        // Recursively validate inner scope items, such as static variables and constants.
-        let db = self.db;
+        for (_, block_def_map) in body.blocks(self.db.upcast()) {
-        for block_def_map in body.block_scopes.iter().filter_map(|block| db.block_def_map(*block)) {
            for (_, module) in block_def_map.modules() {
                for def_id in module.scope.declarations() {
                    let mut validator = DeclValidator::new(self.db, self.krate, self.sink);
@@ -110,7 +140,7 @@ impl<'a, 'b> DeclValidator<'a, 'b> {
        }
        // Check whether non-snake case identifiers are allowed for this function.
-        if self.allowed(func.into(), allow::NON_SNAKE_CASE) {
+        if self.allowed(func.into(), allow::NON_SNAKE_CASE, false) {
            return;
        }
@@ -329,8 +359,9 @@ impl<'a, 'b> DeclValidator<'a, 'b> {
    fn validate_struct(&mut self, struct_id: StructId) {
        let data = self.db.struct_data(struct_id);
-        let non_camel_case_allowed = self.allowed(struct_id.into(), allow::NON_CAMEL_CASE_TYPES);
+        let non_camel_case_allowed =
-        let non_snake_case_allowed = self.allowed(struct_id.into(), allow::NON_SNAKE_CASE);
+            self.allowed(struct_id.into(), allow::NON_CAMEL_CASE_TYPES, false);
+        let non_snake_case_allowed = self.allowed(struct_id.into(), allow::NON_SNAKE_CASE, false);
        // Check the structure name.
        let struct_name = data.name.to_string();
@@ -462,7 +493,7 @@ impl<'a, 'b> DeclValidator<'a, 'b> {
        let data = self.db.enum_data(enum_id);
        // Check whether non-camel case names are allowed for this enum.
-        if self.allowed(enum_id.into(), allow::NON_CAMEL_CASE_TYPES) {
+        if self.allowed(enum_id.into(), allow::NON_CAMEL_CASE_TYPES, false) {
            return;
        }
@@ -585,7 +616,7 @@ impl<'a, 'b> DeclValidator<'a, 'b> {
    fn validate_const(&mut self, const_id: ConstId) {
        let data = self.db.const_data(const_id);
-        if self.allowed(const_id.into(), allow::NON_UPPER_CASE_GLOBAL) {
+        if self.allowed(const_id.into(), allow::NON_UPPER_CASE_GLOBAL, false) {
            return;
        }
@@ -633,7 +664,7 @@ impl<'a, 'b> DeclValidator<'a, 'b> {
            return;
        }
-        if self.allowed(static_id.into(), allow::NON_UPPER_CASE_GLOBAL) {
+        if self.allowed(static_id.into(), allow::NON_UPPER_CASE_GLOBAL, false) {
            return;
        }
@@ -868,23 +899,116 @@ fn main() {
    fn allow_attributes() {
        check_diagnostics(
            r#"
-            #[allow(non_snake_case)]
+#[allow(non_snake_case)]
-    fn NonSnakeCaseName(SOME_VAR: u8) -> u8{
+fn NonSnakeCaseName(SOME_VAR: u8) -> u8{
-        let OtherVar = SOME_VAR + 1;
+    // cov_flags generated output from elsewhere in this file
-        OtherVar
+    extern "C" {
+        #[no_mangle]
+        static lower_case: u8;
    }
-    #[allow(non_snake_case, non_camel_case_types)]
+    let OtherVar = SOME_VAR + 1;
-    pub struct some_type {
+    OtherVar
-        SOME_FIELD: u8,
+}
-        SomeField: u16,
+#[allow(nonstandard_style)]
+mod CheckNonstandardStyle {
+    fn HiImABadFnName() {}
+}
+#[allow(bad_style)]
+mod CheckBadStyle {
+    fn HiImABadFnName() {}
+}
+mod F {
+    #![allow(non_snake_case)]
+    fn CheckItWorksWithModAttr(BAD_NAME_HI: u8) {}
+}
+#[allow(non_snake_case, non_camel_case_types)]
+pub struct some_type {
+    SOME_FIELD: u8,
+    SomeField: u16,
+}
+#[allow(non_upper_case_globals)]
+pub const some_const: u8 = 10;
+#[allow(non_upper_case_globals)]
+pub static SomeStatic: u8 = 10;
+    "#,
+        );
    }
-    #[allow(non_upper_case_globals)]
+    #[test]
-    pub const some_const: u8 = 10;
+    fn allow_attributes_crate_attr() {
+        check_diagnostics(
+            r#"
+#![allow(non_snake_case)]
-    #[allow(non_upper_case_globals)]
+mod F {
-    pub static SomeStatic: u8 = 10;
+    fn CheckItWorksWithCrateAttr(BAD_NAME_HI: u8) {}
+}
+    "#,
+        );
+    }
+    #[test]
+    #[ignore]
+    fn bug_trait_inside_fn() {
+        // FIXME:
+        // This is broken, and in fact, should not even be looked at by this
+        // lint in the first place. There's weird stuff going on in the
+        // collection phase.
+        // It's currently being brought in by:
+        // * validate_func on `a` recursing into modules
+        // * then it finds the trait and then the function while iterating
+        //   through modules
+        // * then validate_func is called on Dirty
+        // * ... which then proceeds to look at some unknown module taking no
+        //   attrs from either the impl or the fn a, and then finally to the root
+        //   module
+        //
+        // It should find the attribute on the trait, but it *doesn't even see
+        // the trait* as far as I can tell.
+        check_diagnostics(
+            r#"
+trait T { fn a(); }
+struct U {}
+impl T for U {
+    fn a() {
+        // this comes out of bitflags, mostly
+        #[allow(non_snake_case)]
+        trait __BitFlags {
+            const HiImAlsoBad: u8 = 2;
+            #[inline]
+            fn Dirty(&self) -> bool {
+                false
+            }
+        }
+    }
+}
+    "#,
+        );
+    }
+    #[test]
+    #[ignore]
+    fn bug_traits_arent_checked() {
+        // FIXME: Traits and functions in traits aren't currently checked by
+        // r-a, even though rustc will complain about them.
+        check_diagnostics(
+            r#"
+trait BAD_TRAIT {
+    // ^^^^^^^^^ Trait `BAD_TRAIT` should have CamelCase name, e.g. `BadTrait`
+    fn BAD_FUNCTION();
+    // ^^^^^^^^^^^^ Function `BAD_FUNCTION` should have snake_case name, e.g. `bad_function`
+    fn BadFunction();
+    // ^^^^^^^^^^^^ Function `BadFunction` should have snake_case name, e.g. `bad_function`
+}
    "#,
        );
    }
diff --git a/crates/hir_ty/src/diagnostics/expr.rs b/crates/hir_ty/src/diagnostics/expr.rs
index 3909ad354..79602c3dd 100644
--- a/crates/hir_ty/src/diagnostics/expr.rs
+++ b/crates/hir_ty/src/diagnostics/expr.rs
@@ -14,8 +14,7 @@ use crate::{
        MismatchedArgCount, MissingFields, MissingMatchArms, MissingOkOrSomeInTailExpr,
        MissingPatFields, RemoveThisSemicolon,
    },
-    utils::variant_data,
+    AdtId, InferenceResult, Interner, TyExt, TyKind,
-    AdtId, InferenceResult, Interner, Ty, TyKind,
 };
 pub(crate) use hir_def::{
@@ -104,7 +103,7 @@ impl<'a, 'b> ExprValidator<'a, 'b> {
            let root = source_ptr.file_syntax(db.upcast());
            if let ast::Expr::RecordExpr(record_expr) = &source_ptr.value.to_node(&root) {
                if let Some(_) = record_expr.record_expr_field_list() {
-                    let variant_data = variant_data(db.upcast(), variant_def);
+                    let variant_data = variant_def.variant_data(db.upcast());
                    let missed_fields = missed_fields
                        .into_iter()
                        .map(|idx| variant_data.fields()[idx].name.clone())
@@ -135,7 +134,7 @@ impl<'a, 'b> ExprValidator<'a, 'b> {
                let root = source_ptr.file_syntax(db.upcast());
                if let ast::Pat::RecordPat(record_pat) = expr.to_node(&root) {
                    if let Some(_) = record_pat.record_pat_field_list() {
-                        let variant_data = variant_data(db.upcast(), variant_def);
+                        let variant_data = variant_def.variant_data(db.upcast());
                        let missed_fields = missed_fields
                            .into_iter()
                            .map(|idx| variant_data.fields()[idx].name.clone())
@@ -245,7 +244,8 @@ impl<'a, 'b> ExprValidator<'a, 'b> {
                    Some(callee) => callee,
                    None => return,
                };
-                let sig = db.callable_item_signature(callee.into()).value;
+                let sig =
+                    db.callable_item_signature(callee.into()).into_value_and_skipped_binders().0;
                (sig, args)
            }
@@ -314,7 +314,7 @@ impl<'a, 'b> ExprValidator<'a, 'b> {
                if pat_ty == match_expr_ty
                    || match_expr_ty
                        .as_reference()
-                        .map(|(match_expr_ty, _)| match_expr_ty == pat_ty)
+                        .map(|(match_expr_ty, ..)| match_expr_ty == pat_ty)
                        .unwrap_or(false)
                {
                    // If we had a NotUsefulMatchArm diagnostic, we could
@@ -378,7 +378,7 @@ impl<'a, 'b> ExprValidator<'a, 'b> {
            _ => return,
        };
-        let (params, required) = match mismatch.expected.interned(&Interner) {
+        let (params, required) = match mismatch.expected.kind(&Interner) {
            TyKind::Adt(AdtId(hir_def::AdtId::EnumId(enum_id)), ref parameters)
                if *enum_id == core_result_enum =>
            {
@@ -392,7 +392,9 @@ impl<'a, 'b> ExprValidator<'a, 'b> {
            _ => return,
        };
-        if params.len() > 0 && params[0] == mismatch.actual {
+        if params.len(&Interner) > 0
+            && params.at(&Interner, 0).ty(&Interner) == Some(&mismatch.actual)
+        {
            let (_, source_map) = db.body_with_source_map(self.owner);
            if let Ok(source_ptr) = source_map.expr_syntax(id) {
@@ -421,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;
        }
@@ -450,7 +452,7 @@ pub fn record_literal_missing_fields(
        return None;
    }
-    let variant_data = variant_data(db.upcast(), variant_def);
+    let variant_data = variant_def.variant_data(db.upcast());
    let specified_fields: FxHashSet<_> = fields.iter().map(|f| &f.name).collect();
    let missed_fields: Vec<LocalFieldId> = variant_data
@@ -480,7 +482,7 @@ pub fn record_pattern_missing_fields(
        return None;
    }
-    let variant_data = variant_data(db.upcast(), variant_def);
+    let variant_data = variant_def.variant_data(db.upcast());
    let specified_fields: FxHashSet<_> = fields.iter().map(|f| &f.name).collect();
    let missed_fields: Vec<LocalFieldId> = variant_data
diff --git a/crates/hir_ty/src/diagnostics/match_check.rs b/crates/hir_ty/src/diagnostics/match_check.rs
index 5a5cdcbf3..e9762622f 100644
--- a/crates/hir_ty/src/diagnostics/match_check.rs
+++ b/crates/hir_ty/src/diagnostics/match_check.rs
@@ -227,7 +227,7 @@ use hir_def::{
 use la_arena::Idx;
 use smallvec::{smallvec, SmallVec};
-use crate::{db::HirDatabase, AdtId, InferenceResult, Interner, TyKind};
+use crate::{db::HirDatabase, AdtId, InferenceResult, Interner, TyExt, TyKind};
 #[derive(Debug, Clone, Copy)]
 /// Either a pattern from the source code being analyzed, represented as
@@ -539,7 +539,7 @@ impl Matrix {
        if let Some(Pat::Or(pat_ids)) = row.get_head().map(|pat_id| pat_id.as_pat(cx)) {
            // Or patterns are expanded here
            for pat_id in pat_ids {
-                self.0.push(PatStack::from_pattern(pat_id));
+                self.0.push(row.replace_head_with([pat_id].iter()));
            }
        } else {
            self.0.push(row);
@@ -626,7 +626,7 @@ pub(super) fn is_useful(
    // - enum with no variants
    // - `!` type
    // In those cases, no match arm is useful.
-    match cx.infer[cx.match_expr].strip_references().interned(&Interner) {
+    match cx.infer[cx.match_expr].strip_references().kind(&Interner) {
        TyKind::Adt(AdtId(hir_def::AdtId::EnumId(enum_id)), ..) => {
            if cx.db.enum_data(*enum_id).variants.is_empty() {
                return Ok(Usefulness::NotUseful);
@@ -792,7 +792,10 @@ fn pat_constructor(cx: &MatchCheckCtx, pat: PatIdOrWild) -> MatchCheckResult<Opt
        Pat::Tuple { .. } => {
            let pat_id = pat.as_id().expect("we already know this pattern is not a wild");
            Some(Constructor::Tuple {
-                arity: cx.infer.type_of_pat[pat_id].as_tuple().ok_or(MatchCheckErr::Unknown)?.len(),
+                arity: cx.infer.type_of_pat[pat_id]
+                    .as_tuple()
+                    .ok_or(MatchCheckErr::Unknown)?
+                    .len(&Interner),
            })
        }
        Pat::Lit(lit_expr) => match cx.body.exprs[lit_expr] {
@@ -1085,6 +1088,20 @@ fn main() {
    }
    #[test]
+    fn or_pattern_no_diagnostic() {
+        check_diagnostics(
+            r#"
+enum Either {A, B}
+fn main() {
+    match (Either::A, Either::B) {
+        (Either::A | Either::B, _) => (),
+    }
+}"#,
+        )
+    }
+    #[test]
    fn mismatched_types() {
        // Match statements with arms that don't match the
        // expression pattern do not fire this diagnostic.
@@ -1336,30 +1353,6 @@ fn bang(never: !) {
    }
    #[test]
-    fn or_pattern_panic() {
-        check_diagnostics(
-            r#"
-pub enum Category { Infinity, Zero }
-fn panic(a: Category, b: Category) {
-    match (a, b) {
-        (Category::Zero | Category::Infinity, _) => (),
-        (_, Category::Zero | Category::Infinity) => (),
-    }
-    // FIXME: This is a false positive, but the code used to cause a panic in the match checker,
-    // so this acts as a regression test for that.
-    match (a, b) {
-        //^^^^^^ Missing match arm
-        (Category::Infinity, Category::Infinity) | (Category::Zero, Category::Zero) => (),
-        (Category::Infinity | Category::Zero, _) => (),
-    }
-}
-"#,
-        );
-    }
-    #[test]
    fn unknown_type() {
        check_diagnostics(
            r#"
diff --git a/crates/hir_ty/src/diagnostics/unsafe_check.rs b/crates/hir_ty/src/diagnostics/unsafe_check.rs
index 1f49a4909..ed97dc0e3 100644
--- a/crates/hir_ty/src/diagnostics/unsafe_check.rs
+++ b/crates/hir_ty/src/diagnostics/unsafe_check.rs
@@ -11,7 +11,9 @@ use hir_def::{
 };
 use hir_expand::diagnostics::DiagnosticSink;
-use crate::{db::HirDatabase, diagnostics::MissingUnsafe, InferenceResult, Interner, TyKind};
+use crate::{
+    db::HirDatabase, diagnostics::MissingUnsafe, InferenceResult, Interner, TyExt, TyKind,
+};
 pub(super) struct UnsafeValidator<'a, 'b: 'a> {
    owner: DefWithBodyId,
@@ -32,7 +34,7 @@ impl<'a, 'b> UnsafeValidator<'a, 'b> {
        let def = self.owner;
        let unsafe_expressions = unsafe_expressions(db, self.infer.as_ref(), def);
        let is_unsafe = match self.owner {
-            DefWithBodyId::FunctionId(it) => db.function_data(it).qualifier.is_unsafe,
+            DefWithBodyId::FunctionId(it) => db.function_data(it).is_unsafe(),
            DefWithBodyId::StaticId(_) | DefWithBodyId::ConstId(_) => false,
        };
        if is_unsafe
@@ -86,7 +88,7 @@ fn walk_unsafe(
    match expr {
        &Expr::Call { callee, .. } => {
            if let Some(func) = infer[callee].as_fn_def(db) {
-                if db.function_data(func).qualifier.is_unsafe {
+                if db.function_data(func).is_unsafe() {
                    unsafe_exprs.push(UnsafeExpr { expr: current, inside_unsafe_block });
                }
            }
@@ -103,14 +105,14 @@ fn walk_unsafe(
        Expr::MethodCall { .. } => {
            if infer
                .method_resolution(current)
-                .map(|func| db.function_data(func).qualifier.is_unsafe)
+                .map(|func| db.function_data(func).is_unsafe())
                .unwrap_or(false)
            {
                unsafe_exprs.push(UnsafeExpr { expr: current, inside_unsafe_block });
            }
        }
        Expr::UnaryOp { expr, op: UnaryOp::Deref } => {
-            if let TyKind::Raw(..) = &infer[*expr].interned(&Interner) {
+            if let TyKind::Raw(..) = &infer[*expr].kind(&Interner) {
                unsafe_exprs.push(UnsafeExpr { expr: current, inside_unsafe_block });
            }
        }
diff --git a/crates/hir_ty/src/display.rs b/crates/hir_ty/src/display.rs
index 51480304b..e7c9dabc2 100644
--- a/crates/hir_ty/src/display.rs
+++ b/crates/hir_ty/src/display.rs
@@ -1,14 +1,19 @@
-//! FIXME: write short doc here
+//! The `HirDisplay` trait, which serves two purposes: Turning various bits from
+//! HIR back into source code, and just displaying them for debugging/testing
+//! purposes.
-use std::{array, fmt};
+use std::{
+    array,
+    fmt::{self, Debug},
+};
-use chalk_ir::Mutability;
+use chalk_ir::BoundVar;
 use hir_def::{
    db::DefDatabase,
    find_path,
    generics::TypeParamProvenance,
    item_scope::ItemInNs,
-    path::{GenericArg, Path, PathKind},
+    path::{Path, PathKind},
    type_ref::{TypeBound, TypeRef},
    visibility::Visibility,
    AssocContainerId, Lookup, ModuleId, TraitId,
@@ -16,10 +21,12 @@ use hir_def::{
 use hir_expand::name::Name;
 use crate::{
-    db::HirDatabase, from_assoc_type_id, from_foreign_def_id, from_placeholder_idx, primitive,
+    const_from_placeholder_idx, db::HirDatabase, from_assoc_type_id, from_foreign_def_id,
-    to_assoc_type_id, traits::chalk::from_chalk, utils::generics, AdtId, AliasEq, AliasTy,
+    from_placeholder_idx, lt_from_placeholder_idx, mapping::from_chalk, primitive, subst_prefix,
-    CallableDefId, CallableSig, DomainGoal, ImplTraitId, Interner, Lifetime, OpaqueTy,
+    to_assoc_type_id, utils::generics, AdtId, AliasEq, AliasTy, CallableDefId, CallableSig, Const,
-    ProjectionTy, QuantifiedWhereClause, Scalar, Substitution, TraitRef, Ty, TyKind, WhereClause,
+    ConstValue, DomainGoal, GenericArg, ImplTraitId, Interner, Lifetime, LifetimeData,
+    LifetimeOutlives, Mutability, OpaqueTy, ProjectionTy, ProjectionTyExt, QuantifiedWhereClause,
+    Scalar, TraitRef, TraitRefExt, Ty, TyExt, TyKind, WhereClause,
 };
 pub struct HirFormatter<'a> {
@@ -46,6 +53,10 @@ pub trait HirDisplay {
    where
        Self: Sized,
    {
+        assert!(
+            !matches!(display_target, DisplayTarget::SourceCode { .. }),
+            "HirDisplayWrapper cannot fail with DisplaySourceCodeError, use HirDisplay::hir_fmt directly instead"
+        );
        HirDisplayWrapper { db, t: self, max_size, omit_verbose_types, display_target }
    }
@@ -230,7 +241,7 @@ where
            Err(HirDisplayError::FmtError) => Err(fmt::Error),
            Err(HirDisplayError::DisplaySourceCodeError(_)) => {
                // This should never happen
-                panic!("HirDisplay failed when calling Display::fmt!")
+                panic!("HirDisplay::hir_fmt failed with DisplaySourceCodeError when calling Display::fmt!")
            }
        }
    }
@@ -251,16 +262,12 @@ impl HirDisplay for ProjectionTy {
        }
        let trait_ = f.db.trait_data(self.trait_(f.db));
-        let first_parameter = self.substitution[0].into_displayable(
+        write!(f, "<")?;
-            f.db,
+        self.self_type_parameter(&Interner).hir_fmt(f)?;
-            f.max_size,
+        write!(f, " as {}", trait_.name)?;
-            f.omit_verbose_types,
+        if self.substitution.len(&Interner) > 1 {
-            f.display_target,
-        );
-        write!(f, "<{} as {}", first_parameter, trait_.name)?;
-        if self.substitution.len() > 1 {
            write!(f, "<")?;
-            f.write_joined(&self.substitution[1..], ", ")?;
+            f.write_joined(&self.substitution.as_slice(&Interner)[1..], ", ")?;
            write!(f, ">")?;
        }
        write!(f, ">::{}", f.db.type_alias_data(from_assoc_type_id(self.associated_ty_id)).name)?;
@@ -274,7 +281,40 @@ impl HirDisplay for OpaqueTy {
            return write!(f, "{}", TYPE_HINT_TRUNCATION);
        }
-        self.substitution[0].hir_fmt(f)
+        self.substitution.at(&Interner, 0).hir_fmt(f)
+    }
+}
+impl HirDisplay for GenericArg {
+    fn hir_fmt(&self, f: &mut HirFormatter) -> Result<(), HirDisplayError> {
+        match self.interned() {
+            crate::GenericArgData::Ty(ty) => ty.hir_fmt(f),
+            crate::GenericArgData::Lifetime(lt) => lt.hir_fmt(f),
+            crate::GenericArgData::Const(c) => c.hir_fmt(f),
+        }
+    }
+}
+impl HirDisplay for Const {
+    fn hir_fmt(&self, f: &mut HirFormatter) -> Result<(), HirDisplayError> {
+        let data = self.interned();
+        match data.value {
+            ConstValue::BoundVar(idx) => idx.hir_fmt(f),
+            ConstValue::InferenceVar(..) => write!(f, "_"),
+            ConstValue::Placeholder(idx) => {
+                let id = const_from_placeholder_idx(f.db, idx);
+                let generics = generics(f.db.upcast(), id.parent);
+                let param_data = &generics.params.consts[id.local_id];
+                write!(f, "{}", param_data.name)
+            }
+            ConstValue::Concrete(_) => write!(f, "_"),
+        }
+    }
+}
+impl HirDisplay for BoundVar {
+    fn hir_fmt(&self, f: &mut HirFormatter) -> Result<(), HirDisplayError> {
+        write!(f, "?{}.{}", self.debruijn.depth(), self.index)
    }
 }
@@ -284,7 +324,7 @@ impl HirDisplay for Ty {
            return write!(f, "{}", TYPE_HINT_TRUNCATION);
        }
-        match self.interned(&Interner) {
+        match self.kind(&Interner) {
            TyKind::Never => write!(f, "!")?,
            TyKind::Str => write!(f, "str")?,
            TyKind::Scalar(Scalar::Bool) => write!(f, "bool")?,
@@ -297,16 +337,15 @@ impl HirDisplay for Ty {
                t.hir_fmt(f)?;
                write!(f, "]")?;
            }
-            TyKind::Array(t) => {
+            TyKind::Array(t, c) => {
                write!(f, "[")?;
                t.hir_fmt(f)?;
-                write!(f, "; _]")?;
+                write!(f, "; ")?;
+                c.hir_fmt(f)?;
+                write!(f, "]")?;
            }
-            TyKind::Raw(m, t) | TyKind::Ref(m, t) => {
+            TyKind::Raw(m, t) | TyKind::Ref(m, _, t) => {
-                let ty_display =
+                if matches!(self.kind(&Interner), TyKind::Raw(..)) {
-                    t.into_displayable(f.db, f.max_size, f.omit_verbose_types, f.display_target);
-                if matches!(self.interned(&Interner), TyKind::Raw(..)) {
                    write!(
                        f,
                        "*{}",
@@ -328,7 +367,7 @@ impl HirDisplay for Ty {
                // FIXME: all this just to decide whether to use parentheses...
                let datas;
-                let predicates: Vec<_> = match t.interned(&Interner) {
+                let predicates: Vec<_> = match t.kind(&Interner) {
                    TyKind::Dyn(dyn_ty) if dyn_ty.bounds.skip_binders().interned().len() > 1 => {
                        dyn_ty.bounds.skip_binders().interned().iter().cloned().collect()
                    }
@@ -344,8 +383,8 @@ impl HirDisplay for Ty {
                            let data = (*datas)
                                .as_ref()
                                .map(|rpit| rpit.impl_traits[idx as usize].bounds.clone());
-                            let bounds = data.subst(parameters);
+                            let bounds = data.substitute(&Interner, parameters);
-                            bounds.value
+                            bounds.into_value_and_skipped_binders().0
                        } else {
                            Vec::new()
                        }
@@ -360,26 +399,26 @@ impl HirDisplay for Ty {
                    if fn_traits(f.db.upcast(), trait_).any(|it| it == trait_)
                        && predicates.len() <= 2
                    {
-                        return write!(f, "{}", ty_display);
+                        return t.hir_fmt(f);
                    }
                }
                if predicates.len() > 1 {
                    write!(f, "(")?;
-                    write!(f, "{}", ty_display)?;
+                    t.hir_fmt(f)?;
                    write!(f, ")")?;
                } else {
-                    write!(f, "{}", ty_display)?;
+                    t.hir_fmt(f)?;
                }
            }
            TyKind::Tuple(_, substs) => {
-                if substs.len() == 1 {
+                if substs.len(&Interner) == 1 {
                    write!(f, "(")?;
-                    substs[0].hir_fmt(f)?;
+                    substs.at(&Interner, 0).hir_fmt(f)?;
                    write!(f, ",)")?;
                } else {
                    write!(f, "(")?;
-                    f.write_joined(&*substs.0, ", ")?;
+                    f.write_joined(&*substs.as_slice(&Interner), ", ")?;
                    write!(f, ")")?;
                }
            }
@@ -389,7 +428,7 @@ impl HirDisplay for Ty {
            }
            TyKind::FnDef(def, parameters) => {
                let def = from_chalk(f.db, *def);
-                let sig = f.db.callable_item_signature(def).subst(parameters);
+                let sig = f.db.callable_item_signature(def).substitute(&Interner, parameters);
                match def {
                    CallableDefId::FunctionId(ff) => {
                        write!(f, "fn {}", f.db.function_data(ff).name)?
@@ -399,7 +438,7 @@ impl HirDisplay for Ty {
                        write!(f, "{}", f.db.enum_data(e.parent).variants[e.local_id].name)?
                    }
                };
-                if parameters.len() > 0 {
+                if parameters.len(&Interner) > 0 {
                    let generics = generics(f.db.upcast(), def.into());
                    let (parent_params, self_param, type_params, _impl_trait_params) =
                        generics.provenance_split();
@@ -407,7 +446,7 @@ impl HirDisplay for Ty {
                    // We print all params except implicit impl Trait params. Still a bit weird; should we leave out parent and self?
                    if total_len > 0 {
                        write!(f, "<")?;
-                        f.write_joined(&parameters.0[..total_len], ", ")?;
+                        f.write_joined(&parameters.as_slice(&Interner)[..total_len], ", ")?;
                        write!(f, ">")?;
                    }
                }
@@ -415,15 +454,9 @@ 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(
+                    write!(f, " -> ")?;
-                        f.db,
+                    ret.hir_fmt(f)?;
-                        f.max_size,
-                        f.omit_verbose_types,
-                        f.display_target,
-                    );
-                    write!(f, " -> {}", ret_display)?;
                }
            }
            TyKind::Adt(AdtId(def_id), parameters) => {
@@ -451,7 +484,7 @@ impl HirDisplay for Ty {
                    }
                }
-                if parameters.len() > 0 {
+                if parameters.len(&Interner) > 0 {
                    let parameters_to_write = if f.display_target.is_source_code()
                        || f.omit_verbose_types()
                    {
@@ -460,30 +493,35 @@ impl HirDisplay for Ty {
                            .map(|generic_def_id| f.db.generic_defaults(generic_def_id))
                            .filter(|defaults| !defaults.is_empty())
                        {
-                            None => parameters.0.as_ref(),
+                            None => parameters.as_slice(&Interner),
                            Some(default_parameters) => {
                                let mut default_from = 0;
-                                for (i, parameter) in parameters.iter().enumerate() {
+                                for (i, parameter) in parameters.iter(&Interner).enumerate() {
-                                    match (parameter.interned(&Interner), default_parameters.get(i))
+                                    match (
-                                    {
+                                        parameter.assert_ty_ref(&Interner).kind(&Interner),
-                                        (&TyKind::Unknown, _) | (_, None) => {
+                                        default_parameters.get(i),
+                                    ) {
+                                        (&TyKind::Error, _) | (_, None) => {
                                            default_from = i + 1;
                                        }
                                        (_, Some(default_parameter)) => {
-                                            let actual_default = default_parameter
+                                            let actual_default =
-                                                .clone()
+                                                default_parameter.clone().substitute(
-                                                .subst(&parameters.prefix(i));
+                                                    &Interner,
-                                            if parameter != &actual_default {
+                                                    &subst_prefix(parameters, i),
+                                                );
+                                            if parameter.assert_ty_ref(&Interner) != &actual_default
+                                            {
                                                default_from = i + 1;
                                            }
                                        }
                                    }
                                }
-                                &parameters.0[0..default_from]
+                                &parameters.as_slice(&Interner)[0..default_from]
                            }
                        }
                    } else {
-                        parameters.0.as_ref()
+                        parameters.as_slice(&Interner)
                    };
                    if !parameters_to_write.is_empty() {
                        write!(f, "<")?;
@@ -504,9 +542,9 @@ impl HirDisplay for Ty {
                // Use placeholder associated types when the target is test (https://rust-lang.github.io/chalk/book/clauses/type_equality.html#placeholder-associated-types)
                if f.display_target.is_test() {
                    write!(f, "{}::{}", trait_.name, type_alias_data.name)?;
-                    if parameters.len() > 0 {
+                    if parameters.len(&Interner) > 0 {
                        write!(f, "<")?;
-                        f.write_joined(&*parameters.0, ", ")?;
+                        f.write_joined(&*parameters.as_slice(&Interner), ", ")?;
                        write!(f, ">")?;
                    }
                } else {
@@ -518,7 +556,7 @@ impl HirDisplay for Ty {
                    projection_ty.hir_fmt(f)?;
                }
            }
-            TyKind::ForeignType(type_alias) => {
+            TyKind::Foreign(type_alias) => {
                let type_alias = f.db.type_alias_data(from_foreign_def_id(*type_alias));
                write!(f, "{}", type_alias.name)?;
            }
@@ -531,13 +569,13 @@ impl HirDisplay for Ty {
                        let data = (*datas)
                            .as_ref()
                            .map(|rpit| rpit.impl_traits[idx as usize].bounds.clone());
-                        let bounds = data.subst(&parameters);
+                        let bounds = data.substitute(&Interner, &parameters);
-                        write_bounds_like_dyn_trait_with_prefix("impl", &bounds.value, f)?;
+                        write_bounds_like_dyn_trait_with_prefix("impl", bounds.skip_binders(), f)?;
                        // FIXME: it would maybe be good to distinguish this from the alias type (when debug printing), and to show the substitution
                    }
                    ImplTraitId::AsyncBlockTypeImplTrait(..) => {
                        write!(f, "impl Future<Output = ")?;
-                        parameters[0].hir_fmt(f)?;
+                        parameters.at(&Interner, 0).hir_fmt(f)?;
                        write!(f, ">")?;
                    }
                }
@@ -548,7 +586,7 @@ impl HirDisplay for Ty {
                        DisplaySourceCodeError::Closure,
                    ));
                }
-                let sig = substs[0].callable_sig(f.db);
+                let sig = substs.at(&Interner, 0).assert_ty_ref(&Interner).callable_sig(f.db);
                if let Some(sig) = sig {
                    if sig.params().is_empty() {
                        write!(f, "||")?;
@@ -560,13 +598,8 @@ impl HirDisplay for Ty {
                        write!(f, "|")?;
                    };
-                    let ret_display = sig.ret().into_displayable(
+                    write!(f, " -> ")?;
-                        f.db,
+                    sig.ret().hir_fmt(f)?;
-                        f.max_size,
-                        f.omit_verbose_types,
-                        f.display_target,
-                    );
-                    write!(f, " -> {}", ret_display)?;
                } else {
                    write!(f, "{{closure}}")?;
                }
@@ -580,26 +613,27 @@ 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
+                        let bounds =
-                            .db
+                            f.db.generic_predicates(id.parent)
-                            .generic_predicates(id.parent)
+                                .into_iter()
-                            .into_iter()
+                                .map(|pred| pred.clone().substitute(&Interner, &substs))
-                            .map(|pred| pred.clone().subst(&substs))
+                                .filter(|wc| match &wc.skip_binders() {
-                            .filter(|wc| match &wc.skip_binders() {
+                                    WhereClause::Implemented(tr) => {
-                                WhereClause::Implemented(tr) => tr.self_type_parameter() == self,
+                                        &tr.self_type_parameter(&Interner) == self
-                                WhereClause::AliasEq(AliasEq {
+                                    }
-                                    alias: AliasTy::Projection(proj),
+                                    WhereClause::AliasEq(AliasEq {
-                                    ty: _,
+                                        alias: AliasTy::Projection(proj),
-                                }) => proj.self_type_parameter() == self,
+                                        ty: _,
-                                _ => false,
+                                    }) => &proj.self_type_parameter(&Interner) == self,
-                            })
+                                    _ => false,
-                            .collect::<Vec<_>>();
+                                })
+                                .collect::<Vec<_>>();
                        write_bounds_like_dyn_trait_with_prefix("impl", &bounds, f)?;
                    }
                }
            }
-            TyKind::BoundVar(idx) => write!(f, "?{}.{}", idx.debruijn.depth(), idx.index)?,
+            TyKind::BoundVar(idx) => idx.hir_fmt(f)?,
            TyKind::Dyn(dyn_ty) => {
                write_bounds_like_dyn_trait_with_prefix(
                    "dyn",
@@ -617,15 +651,15 @@ impl HirDisplay for Ty {
                        let data = (*datas)
                            .as_ref()
                            .map(|rpit| rpit.impl_traits[idx as usize].bounds.clone());
-                        let bounds = data.subst(&opaque_ty.substitution);
+                        let bounds = data.substitute(&Interner, &opaque_ty.substitution);
-                        write_bounds_like_dyn_trait_with_prefix("impl", &bounds.value, f)?;
+                        write_bounds_like_dyn_trait_with_prefix("impl", bounds.skip_binders(), f)?;
                    }
                    ImplTraitId::AsyncBlockTypeImplTrait(..) => {
                        write!(f, "{{async block}}")?;
                    }
                };
            }
-            TyKind::Unknown => {
+            TyKind::Error => {
                if f.display_target.is_source_code() {
                    return Err(HirDisplayError::DisplaySourceCodeError(
                        DisplaySourceCodeError::UnknownType,
@@ -634,6 +668,8 @@ impl HirDisplay for Ty {
                write!(f, "{{unknown}}")?;
            }
            TyKind::InferenceVar(..) => write!(f, "_")?,
+            TyKind::Generator(..) => write!(f, "{{generator}}")?,
+            TyKind::GeneratorWitness(..) => write!(f, "{{generator witness}}")?,
        }
        Ok(())
    }
@@ -652,10 +688,9 @@ impl HirDisplay for CallableSig {
        }
        write!(f, ")")?;
        let ret = self.ret();
-        if *ret != Ty::unit() {
+        if !ret.is_unit() {
-            let ret_display =
+            write!(f, " -> ")?;
-                ret.into_displayable(f.db, f.max_size, f.omit_verbose_types, f.display_target);
+            ret.hir_fmt(f)?;
-            write!(f, " -> {}", ret_display)?;
        }
        Ok(())
    }
@@ -712,15 +747,17 @@ fn write_bounds_like_dyn_trait(
                if !first {
                    write!(f, " + ")?;
                }
-                // We assume that the self type is $0 (i.e. the
+                // We assume that the self type is ^0.0 (i.e. the
                // existential) here, which is the only thing that's
                // possible in actual Rust, and hence don't print it
                write!(f, "{}", f.db.trait_data(trait_).name)?;
-                if let [_, params @ ..] = &*trait_ref.substitution.0 {
+                if let [_, params @ ..] = &*trait_ref.substitution.as_slice(&Interner) {
                    if is_fn_trait {
-                        if let Some(args) = params.first().and_then(|it| it.as_tuple()) {
+                        if let Some(args) =
+                            params.first().and_then(|it| it.assert_ty_ref(&Interner).as_tuple())
+                        {
                            write!(f, "(")?;
-                            f.write_joined(&*args.0, ", ")?;
+                            f.write_joined(args.as_slice(&Interner), ", ")?;
                            write!(f, ")")?;
                        }
                    } else if !params.is_empty() {
@@ -752,6 +789,10 @@ fn write_bounds_like_dyn_trait(
                }
                ty.hir_fmt(f)?;
            }
+            // FIXME implement these
+            WhereClause::LifetimeOutlives(_) => {}
+            WhereClause::TypeOutlives(_) => {}
        }
        first = false;
    }
@@ -761,31 +802,29 @@ fn write_bounds_like_dyn_trait(
    Ok(())
 }
-impl TraitRef {
+fn fmt_trait_ref(tr: &TraitRef, f: &mut HirFormatter, use_as: bool) -> Result<(), HirDisplayError> {
-    fn hir_fmt_ext(&self, f: &mut HirFormatter, use_as: bool) -> Result<(), HirDisplayError> {
+    if f.should_truncate() {
-        if f.should_truncate() {
+        return write!(f, "{}", TYPE_HINT_TRUNCATION);
-            return write!(f, "{}", TYPE_HINT_TRUNCATION);
+    }
-        }
-        self.substitution[0].hir_fmt(f)?;
+    tr.self_type_parameter(&Interner).hir_fmt(f)?;
-        if use_as {
+    if use_as {
-            write!(f, " as ")?;
+        write!(f, " as ")?;
-        } else {
+    } else {
-            write!(f, ": ")?;
+        write!(f, ": ")?;
-        }
+    }
-        write!(f, "{}", f.db.trait_data(self.hir_trait_id()).name)?;
+    write!(f, "{}", f.db.trait_data(tr.hir_trait_id()).name)?;
-        if self.substitution.len() > 1 {
+    if tr.substitution.len(&Interner) > 1 {
-            write!(f, "<")?;
+        write!(f, "<")?;
-            f.write_joined(&self.substitution[1..], ", ")?;
+        f.write_joined(&tr.substitution.as_slice(&Interner)[1..], ", ")?;
-            write!(f, ">")?;
+        write!(f, ">")?;
-        }
-        Ok(())
    }
+    Ok(())
 }
 impl HirDisplay for TraitRef {
    fn hir_fmt(&self, f: &mut HirFormatter) -> Result<(), HirDisplayError> {
-        self.hir_fmt_ext(f, false)
+        fmt_trait_ref(self, f, false)
    }
 }
@@ -799,7 +838,7 @@ impl HirDisplay for WhereClause {
            WhereClause::Implemented(trait_ref) => trait_ref.hir_fmt(f)?,
            WhereClause::AliasEq(AliasEq { alias: AliasTy::Projection(projection_ty), ty }) => {
                write!(f, "<")?;
-                projection_ty.trait_ref(f.db).hir_fmt_ext(f, true)?;
+                fmt_trait_ref(&projection_ty.trait_ref(f.db), f, true)?;
                write!(
                    f,
                    ">::{} = ",
@@ -808,20 +847,44 @@ impl HirDisplay for WhereClause {
                ty.hir_fmt(f)?;
            }
            WhereClause::AliasEq(_) => write!(f, "{{error}}")?,
+            // FIXME implement these
+            WhereClause::TypeOutlives(..) => {}
+            WhereClause::LifetimeOutlives(..) => {}
        }
        Ok(())
    }
 }
+impl HirDisplay for LifetimeOutlives {
+    fn hir_fmt(&self, f: &mut HirFormatter) -> Result<(), HirDisplayError> {
+        self.a.hir_fmt(f)?;
+        write!(f, ": ")?;
+        self.b.hir_fmt(f)
+    }
+}
 impl HirDisplay for Lifetime {
    fn hir_fmt(&self, f: &mut HirFormatter) -> Result<(), HirDisplayError> {
+        self.interned().hir_fmt(f)
+    }
+}
+impl HirDisplay for LifetimeData {
+    fn hir_fmt(&self, f: &mut HirFormatter) -> Result<(), HirDisplayError> {
        match self {
-            Lifetime::Parameter(id) => {
+            LifetimeData::BoundVar(idx) => idx.hir_fmt(f),
+            LifetimeData::InferenceVar(_) => write!(f, "_"),
+            LifetimeData::Placeholder(idx) => {
+                let id = lt_from_placeholder_idx(f.db, *idx);
                let generics = generics(f.db.upcast(), id.parent);
                let param_data = &generics.params.lifetimes[id.local_id];
-                write!(f, "{}", &param_data.name)
+                write!(f, "{}", param_data.name)
            }
-            Lifetime::Static => write!(f, "'static"),
+            LifetimeData::Static => write!(f, "'static"),
+            LifetimeData::Empty(_) => Ok(()),
+            LifetimeData::Erased => Ok(()),
+            LifetimeData::Phantom(_, _) => Ok(()),
        }
    }
 }
@@ -832,9 +895,11 @@ impl HirDisplay for DomainGoal {
            DomainGoal::Holds(wc) => {
                write!(f, "Holds(")?;
                wc.hir_fmt(f)?;
-                write!(f, ")")
+                write!(f, ")")?;
            }
+            _ => write!(f, "?")?,
        }
+        Ok(())
    }
 }
@@ -1016,11 +1081,11 @@ impl HirDisplay for Path {
    }
 }
-impl HirDisplay for GenericArg {
+impl HirDisplay for hir_def::path::GenericArg {
    fn hir_fmt(&self, f: &mut HirFormatter) -> Result<(), HirDisplayError> {
        match self {
-            GenericArg::Type(ty) => ty.hir_fmt(f),
+            hir_def::path::GenericArg::Type(ty) => ty.hir_fmt(f),
-            GenericArg::Lifetime(lifetime) => write!(f, "{}", lifetime.name),
+            hir_def::path::GenericArg::Lifetime(lifetime) => write!(f, "{}", lifetime.name),
        }
    }
 }
diff --git a/crates/hir_ty/src/infer.rs b/crates/hir_ty/src/infer.rs
index e4407ff50..bf2da2d4a 100644
--- a/crates/hir_ty/src/infer.rs
+++ b/crates/hir_ty/src/infer.rs
@@ -18,7 +18,7 @@ use std::mem;
 use std::ops::Index;
 use std::sync::Arc;
-use chalk_ir::{cast::Cast, Mutability};
+use chalk_ir::{cast::Cast, DebruijnIndex, Mutability};
 use hir_def::{
    body::Body,
    data::{ConstData, FunctionData, StaticData},
@@ -37,12 +37,12 @@ use stdx::impl_from;
 use syntax::SmolStr;
 use super::{
-    traits::{DomainGoal, Guidance, Solution},
+    DomainGoal, Guidance, InEnvironment, ProjectionTy, Solution, TraitEnvironment, TraitRef, Ty,
-    InEnvironment, ProjectionTy, Substitution, TraitEnvironment, TraitRef, Ty, TypeWalk,
 };
 use crate::{
-    db::HirDatabase, infer::diagnostics::InferenceDiagnostic, lower::ImplTraitLoweringMode,
+    db::HirDatabase, fold_tys, infer::diagnostics::InferenceDiagnostic,
-    to_assoc_type_id, to_chalk_trait_id, AliasEq, AliasTy, Interner, TyKind,
+    lower::ImplTraitLoweringMode, to_assoc_type_id, AliasEq, AliasTy, Canonical, Interner,
+    TyBuilder, TyExt, TyKind,
 };
 // This lint has a false positive here. See the link below for details.
@@ -120,7 +120,7 @@ struct InternedStandardTypes {
 impl Default for InternedStandardTypes {
    fn default() -> Self {
-        InternedStandardTypes { unknown: TyKind::Unknown.intern(&Interner) }
+        InternedStandardTypes { unknown: TyKind::Error.intern(&Interner) }
    }
 }
@@ -131,10 +131,7 @@ pub struct InferenceResult {
    method_resolutions: FxHashMap<ExprId, FunctionId>,
    /// For each field access expr, records the field it resolves to.
    field_resolutions: FxHashMap<ExprId, FieldId>,
-    /// For each field in record literal, records the field it resolves to.
+    /// For each struct literal or pattern, records the variant it resolves to.
-    record_field_resolutions: FxHashMap<ExprId, FieldId>,
-    record_pat_field_resolutions: FxHashMap<PatId, FieldId>,
-    /// For each struct literal, records the variant it resolves to.
    variant_resolutions: FxHashMap<ExprOrPatId, VariantId>,
    /// For each associated item record what it resolves to
    assoc_resolutions: FxHashMap<ExprOrPatId, AssocItemId>,
@@ -153,12 +150,6 @@ impl InferenceResult {
    pub fn field_resolution(&self, expr: ExprId) -> Option<FieldId> {
        self.field_resolutions.get(&expr).copied()
    }
-    pub fn record_field_resolution(&self, expr: ExprId) -> Option<FieldId> {
-        self.record_field_resolutions.get(&expr).copied()
-    }
-    pub fn record_pat_field_resolution(&self, pat: PatId) -> Option<FieldId> {
-        self.record_pat_field_resolutions.get(&pat).copied()
-    }
    pub fn variant_resolution_for_expr(&self, id: ExprId) -> Option<VariantId> {
        self.variant_resolutions.get(&id.into()).copied()
    }
@@ -210,6 +201,7 @@ struct InferenceContext<'a> {
    table: unify::InferenceTable,
    trait_env: Arc<TraitEnvironment>,
    obligations: Vec<DomainGoal>,
+    last_obligations_check: Option<u32>,
    result: InferenceResult,
    /// The return type of the function being inferred, or the closure if we're
    /// currently within one.
@@ -245,7 +237,8 @@ impl<'a> InferenceContext<'a> {
            result: InferenceResult::default(),
            table: unify::InferenceTable::new(),
            obligations: Vec::default(),
-            return_ty: TyKind::Unknown.intern(&Interner), // set in collect_fn_signature
+            last_obligations_check: None,
+            return_ty: TyKind::Error.intern(&Interner), // set in collect_fn_signature
            trait_env: owner
                .as_generic_def_id()
                .map_or_else(Default::default, |d| db.trait_environment(d)),
@@ -259,7 +252,7 @@ impl<'a> InferenceContext<'a> {
    }
    fn err_ty(&self) -> Ty {
-        TyKind::Unknown.intern(&Interner)
+        TyKind::Error.intern(&Interner)
    }
    fn resolve_all(mut self) -> InferenceResult {
@@ -323,30 +316,44 @@ impl<'a> InferenceContext<'a> {
    /// Replaces Ty::Unknown by a new type var, so we can maybe still infer it.
    fn insert_type_vars_shallow(&mut self, ty: Ty) -> Ty {
-        match ty.interned(&Interner) {
+        match ty.kind(&Interner) {
-            TyKind::Unknown => self.table.new_type_var(),
+            TyKind::Error => self.table.new_type_var(),
            _ => ty,
        }
    }
    fn insert_type_vars(&mut self, ty: Ty) -> Ty {
-        ty.fold(&mut |ty| self.insert_type_vars_shallow(ty))
+        fold_tys(ty, |ty, _| self.insert_type_vars_shallow(ty), DebruijnIndex::INNERMOST)
    }
    fn resolve_obligations_as_possible(&mut self) {
+        if self.last_obligations_check == Some(self.table.revision) {
+            // no change
+            return;
+        }
+        let _span = profile::span("resolve_obligations_as_possible");
+        self.last_obligations_check = Some(self.table.revision);
        let obligations = mem::replace(&mut self.obligations, Vec::new());
        for obligation in obligations {
-            let in_env = InEnvironment::new(self.trait_env.env.clone(), obligation.clone());
+            let in_env = InEnvironment::new(&self.trait_env.env, obligation.clone());
            let canonicalized = self.canonicalizer().canonicalize_obligation(in_env);
            let solution =
                self.db.trait_solve(self.resolver.krate().unwrap(), canonicalized.value.clone());
            match solution {
-                Some(Solution::Unique(substs)) => {
+                Some(Solution::Unique(canonical_subst)) => {
-                    canonicalized.apply_solution(self, substs.0);
+                    canonicalized.apply_solution(
+                        self,
+                        Canonical {
+                            binders: canonical_subst.binders,
+                            // FIXME: handle constraints
+                            value: canonical_subst.value.subst,
+                        },
+                    );
                }
                Some(Solution::Ambig(Guidance::Definite(substs))) => {
-                    canonicalized.apply_solution(self, substs.0);
+                    canonicalized.apply_solution(self, substs);
                    self.obligations.push(obligation);
                }
                Some(_) => {
@@ -360,6 +367,11 @@ impl<'a> InferenceContext<'a> {
        }
    }
+    fn push_obligation(&mut self, o: DomainGoal) {
+        self.obligations.push(o);
+        self.last_obligations_check = None;
+    }
    fn unify(&mut self, ty1: &Ty, ty2: &Ty) -> bool {
        self.table.unify(ty1, ty2)
    }
@@ -395,21 +407,19 @@ 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(),
                };
-                self.obligations.push(trait_ref.cast(&Interner));
+                self.push_obligation(trait_ref.cast(&Interner));
-                self.obligations.push(alias_eq.cast(&Interner));
+                self.push_obligation(alias_eq.cast(&Interner));
                self.resolve_ty_as_possible(ty)
            }
            None => self.err_ty(),
@@ -424,19 +434,23 @@ impl<'a> InferenceContext<'a> {
    /// to do it as well.
    fn normalize_associated_types_in(&mut self, ty: Ty) -> Ty {
        let ty = self.resolve_ty_as_possible(ty);
-        ty.fold(&mut |ty| match ty.interned(&Interner) {
+        fold_tys(
-            TyKind::Alias(AliasTy::Projection(proj_ty)) => {
+            ty,
-                self.normalize_projection_ty(proj_ty.clone())
+            |ty, _| match ty.kind(&Interner) {
-            }
+                TyKind::Alias(AliasTy::Projection(proj_ty)) => {
-            _ => ty,
+                    self.normalize_projection_ty(proj_ty.clone())
-        })
+                }
+                _ => ty,
+            },
+            DebruijnIndex::INNERMOST,
+        )