70 files changed, 2086 insertions, 1453 deletions
diff --git a/Cargo.lock b/Cargo.lock
index 4344f8df5..05383d8b7 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -37,9 +37,9 @@ dependencies = [
 [[package]]
 name = "anyhow"
-version = "1.0.39"
+version = "1.0.40"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "81cddc5f91628367664cc7c69714ff08deee8a3efc54623011c772544d7b2767"
+checksum = "28b2cd92db5cbd74e8e5028f7e27dd7aa3090e89e4f2a197cc7c8dfb69c7063b"
 [[package]]
 name = "anymap"
@@ -49,9 +49,9 @@ checksum = "33954243bd79057c2de7338850b85983a44588021f8a5fee574a8888c6de4344"
 [[package]]
 name = "arrayvec"
-version = "0.6.0"
+version = "0.6.1"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "682f88bd1270f264991da8922b89ee1fb520b0da73f97c9f73cda54980123017"
+checksum = "269d0f5e68353a7cab87f81e7c736adc008d279a36ebc6a05dfe01193a89f0c9"
 [[package]]
 name = "atty"
@@ -797,9 +797,9 @@ checksum = "e2abad23fbc42b3700f2f279844dc832adb2b2eb069b2df918f455c4e18cc646"
 [[package]]
 name = "libc"
-version = "0.2.91"
+version = "0.2.92"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "8916b1f6ca17130ec6568feccee27c156ad12037880833a3b842a823236502e7"
+checksum = "56d855069fafbb9b344c0f962150cd2c1187975cb1c22c1522c240d8c4986714"
 [[package]]
 name = "libloading"
@@ -822,9 +822,9 @@ dependencies = [
 [[package]]
 name = "lock_api"
-version = "0.4.2"
+version = "0.4.3"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "dd96ffd135b2fd7b973ac026d28085defbe8983df057ced3eb4f2130b0831312"
+checksum = "5a3c91c24eae6777794bb1997ad98bbb87daf92890acab859f7eaa4320333176"
 dependencies = [
 "scopeguard",
 ]
@@ -921,9 +921,9 @@ dependencies = [
 [[package]]
 name = "memoffset"
-version = "0.6.1"
+version = "0.6.3"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "157b4208e3059a8f9e78d559edc658e13df41410cb3ae03979c83130067fdd87"
+checksum = "f83fb6581e8ed1f85fd45c116db8405483899489e38406156c25eb743554361d"
 dependencies = [
 "autocfg",
 ]
@@ -1157,9 +1157,9 @@ checksum = "dbf0c48bc1d91375ae5c3cd81e3722dff1abcf81a30960240640d223f59fe0e5"
 [[package]]
 name = "proc-macro2"
-version = "1.0.24"
+version = "1.0.26"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "1e0704ee1a7e00d7bb417d0770ea303c1bccbabf0ef1667dae92b5967f5f8a71"
+checksum = "a152013215dca273577e18d2bf00fa862b89b24169fb78c4c95aeb07992c9cec"
 dependencies = [
 "unicode-xid",
 ]
@@ -1577,9 +1577,9 @@ dependencies = [
 [[package]]
 name = "syn"
-version = "1.0.64"
+version = "1.0.68"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "3fd9d1e9976102a03c542daa2eff1b43f9d72306342f3f8b3ed5fb8908195d6f"
+checksum = "3ce15dd3ed8aa2f8eeac4716d6ef5ab58b6b9256db41d7e1a0224c2788e8fd87"
 dependencies = [
 "proc-macro2",
 "quote",
diff --git a/crates/cfg/src/tests.rs b/crates/cfg/src/tests.rs
index bd0f9ec48..d8736c893 100644
--- a/crates/cfg/src/tests.rs
+++ b/crates/cfg/src/tests.rs
@@ -8,7 +8,7 @@ fn assert_parse_result(input: &str, expected: CfgExpr) {
    let (tt, _) = {
        let source_file = ast::SourceFile::parse(input).ok().unwrap();
        let tt = source_file.syntax().descendants().find_map(ast::TokenTree::cast).unwrap();
-        ast_to_token_tree(&tt).unwrap()
+        ast_to_token_tree(&tt)
    };
    let cfg = CfgExpr::parse(&tt);
    assert_eq!(cfg, expected);
@@ -18,7 +18,7 @@ fn check_dnf(input: &str, expect: Expect) {
    let (tt, _) = {
        let source_file = ast::SourceFile::parse(input).ok().unwrap();
        let tt = source_file.syntax().descendants().find_map(ast::TokenTree::cast).unwrap();
-        ast_to_token_tree(&tt).unwrap()
+        ast_to_token_tree(&tt)
    };
    let cfg = CfgExpr::parse(&tt);
    let actual = format!("#![cfg({})]", DnfExpr::new(cfg));
@@ -29,7 +29,7 @@ fn check_why_inactive(input: &str, opts: &CfgOptions, expect: Expect) {
    let (tt, _) = {
        let source_file = ast::SourceFile::parse(input).ok().unwrap();
        let tt = source_file.syntax().descendants().find_map(ast::TokenTree::cast).unwrap();
-        ast_to_token_tree(&tt).unwrap()
+        ast_to_token_tree(&tt)
    };
    let cfg = CfgExpr::parse(&tt);
    let dnf = DnfExpr::new(cfg);
@@ -42,7 +42,7 @@ fn check_enable_hints(input: &str, opts: &CfgOptions, expected_hints: &[&str]) {
    let (tt, _) = {
        let source_file = ast::SourceFile::parse(input).ok().unwrap();
        let tt = source_file.syntax().descendants().find_map(ast::TokenTree::cast).unwrap();
-        ast_to_token_tree(&tt).unwrap()
+        ast_to_token_tree(&tt)
    };
    let cfg = CfgExpr::parse(&tt);
    let dnf = DnfExpr::new(cfg);
diff --git a/crates/hir/src/db.rs b/crates/hir/src/db.rs
index 1902a8d16..df5758342 100644
--- a/crates/hir/src/db.rs
+++ b/crates/hir/src/db.rs
@@ -1,14 +1,6 @@
 //! FIXME: write short doc here
-pub use hir_def::db::{
+pub use hir_def::db::*;
-    AttrsQuery, BlockDefMapQuery, BodyQuery, BodyWithSourceMapQuery, ConstDataQuery,
-    CrateDefMapQueryQuery, CrateLangItemsQuery, DefDatabase, DefDatabaseStorage, EnumDataQuery,
-    ExprScopesQuery, FileItemTreeQuery, FunctionDataQuery, GenericParamsQuery, ImplDataQuery,
-    ImportMapQuery, InternConstQuery, InternDatabase, InternDatabaseStorage, InternEnumQuery,
-    InternFunctionQuery, InternImplQuery, InternStaticQuery, InternStructQuery, InternTraitQuery,
-    InternTypeAliasQuery, InternUnionQuery, LangItemQuery, StaticDataQuery, StructDataQuery,
-    TraitDataQuery, TypeAliasDataQuery, UnionDataQuery,
-};
 pub use hir_expand::db::{
    AstDatabase, AstDatabaseStorage, AstIdMapQuery, HygieneFrameQuery, InternEagerExpansionQuery,
    InternMacroQuery, MacroArgTextQuery, MacroDefQuery, MacroExpandQuery, ParseMacroExpansionQuery,
diff --git a/crates/hir/src/display.rs b/crates/hir/src/display.rs
index ab04c55bc..993772aac 100644
--- a/crates/hir/src/display.rs
+++ b/crates/hir/src/display.rs
@@ -13,29 +13,28 @@ use syntax::ast::{self, NameOwner};
 use crate::{
    Adt, Const, ConstParam, Enum, Field, Function, GenericParam, HasVisibility, LifetimeParam,
-    Module, Static, Struct, Substitution, Trait, Type, TypeAlias, TypeParam, Union, Variant,
+    Module, Static, Struct, Trait, TyBuilder, Type, TypeAlias, TypeParam, Union, Variant,
 };
 impl HirDisplay for Function {
    fn hir_fmt(&self, f: &mut HirFormatter) -> Result<(), HirDisplayError> {
        let data = f.db.function_data(self.id);
        write_visibility(self.module(f.db).id, self.visibility(f.db), f)?;
-        let qual = &data.qualifier;
+        if data.is_default() {
-        if qual.is_default {
            write!(f, "default ")?;
        }
-        if qual.is_const {
+        if data.is_const() {
            write!(f, "const ")?;
        }
-        if qual.is_async {
+        if data.is_async() {
            write!(f, "async ")?;
        }
-        if qual.is_unsafe {
+        if data.is_unsafe() {
            write!(f, "unsafe ")?;
        }
-        if let Some(abi) = &qual.abi {
+        if let Some(abi) = &data.abi {
            // FIXME: String escape?
-            write!(f, "extern \"{}\" ", abi)?;
+            write!(f, "extern \"{}\" ", &**abi)?;
        }
        write!(f, "fn {}", data.name)?;
@@ -68,7 +67,7 @@ impl HirDisplay for Function {
                write!(f, ", ")?;
            } else {
                first = false;
-                if data.has_self_param {
+                if data.has_self_param() {
                    write_self_param(type_ref, f)?;
                    continue;
                }
@@ -88,7 +87,7 @@ impl HirDisplay for Function {
        // `FunctionData::ret_type` will be `::core::future::Future<Output = ...>` for async fns.
        // Use ugly pattern match to strip the Future trait.
        // Better way?
-        let ret_type = if !qual.is_async {
+        let ret_type = if !data.is_async() {
            &data.ret_type
        } else {
            match &*data.ret_type {
@@ -235,7 +234,7 @@ impl HirDisplay for TypeParam {
    fn hir_fmt(&self, f: &mut HirFormatter) -> Result<(), HirDisplayError> {
        write!(f, "{}", self.name(f.db))?;
        let bounds = f.db.generic_predicates_for_param(self.id);
-        let substs = Substitution::type_params(f.db, self.id.parent);
+        let substs = TyBuilder::type_params_subst(f.db, self.id.parent);
        let predicates = bounds.iter().cloned().map(|b| b.subst(&substs)).collect::<Vec<_>>();
        if !(predicates.is_empty() || f.omit_verbose_types()) {
            write_bounds_like_dyn_trait_with_prefix(":", &predicates, f)?;
diff --git a/crates/hir/src/lib.rs b/crates/hir/src/lib.rs
index 29010191b..e41efb385 100644
--- a/crates/hir/src/lib.rs
+++ b/crates/hir/src/lib.rs
@@ -55,11 +55,11 @@ use hir_ty::{
    autoderef, could_unify,
    method_resolution::{self, TyFingerprint},
    primitive::UintTy,
-    to_assoc_type_id,
+    traits::FnTrait,
-    traits::{FnTrait, Solution, SolutionVariables},
    AliasEq, AliasTy, BoundVar, CallableDefId, CallableSig, Canonical, CanonicalVarKinds, Cast,
-    DebruijnIndex, InEnvironment, Interner, ProjectionTy, QuantifiedWhereClause, Scalar,
+    DebruijnIndex, InEnvironment, Interner, QuantifiedWhereClause, Scalar, Solution,
-    Substitution, TraitEnvironment, Ty, TyDefId, TyKind, TyVariableKind, WhereClause,
+    SolutionVariables, Substitution, TraitEnvironment, Ty, TyBuilder, TyDefId, TyKind,
+    TyVariableKind, WhereClause,
 };
 use itertools::Itertools;
 use rustc_hash::FxHashSet;
@@ -515,7 +515,7 @@ impl Field {
            VariantDef::Union(it) => it.id.into(),
            VariantDef::Variant(it) => it.parent.id.into(),
        };
-        let substs = Substitution::type_params(db, generic_def_id);
+        let substs = TyBuilder::type_params_subst(db, generic_def_id);
        let ty = db.field_types(var_id)[self.id].clone().subst(&substs);
        Type::new(db, self.parent.module(db).id.krate(), var_id, ty)
    }
@@ -832,7 +832,7 @@ impl Function {
    }
    pub fn self_param(self, db: &dyn HirDatabase) -> Option<SelfParam> {
-        if !db.function_data(self.id).has_self_param {
+        if !db.function_data(self.id).has_self_param() {
            return None;
        }
        Some(SelfParam { func: self.id })
@@ -864,7 +864,7 @@ impl Function {
    }
    pub fn is_unsafe(self, db: &dyn HirDatabase) -> bool {
-        db.function_data(self.id).qualifier.is_unsafe
+        db.function_data(self.id).is_unsafe()
    }
    pub fn diagnostics(self, db: &dyn HirDatabase, sink: &mut DiagnosticSink) {
@@ -878,7 +878,7 @@ impl Function {
    ///
    /// This is false in the case of required (not provided) trait methods.
    pub fn has_body(self, db: &dyn HirDatabase) -> bool {
-        db.function_data(self.id).has_body
+        db.function_data(self.id).has_body()
    }
    /// A textual representation of the HIR of this function for debugging purposes.
@@ -1129,7 +1129,7 @@ pub struct BuiltinType {
 impl BuiltinType {
    pub fn ty(self, db: &dyn HirDatabase, module: Module) -> Type {
        let resolver = module.id.resolver(db.upcast());
-        Type::new_with_resolver(db, &resolver, Ty::builtin(self.inner))
+        Type::new_with_resolver(db, &resolver, TyBuilder::builtin(self.inner))
            .expect("crate not present in resolver")
    }
@@ -1502,7 +1502,7 @@ impl TypeParam {
        let resolver = self.id.parent.resolver(db.upcast());
        let krate = self.id.parent.module(db.upcast()).krate();
        let ty = params.get(local_idx)?.clone();
-        let subst = Substitution::type_params(db, self.id.parent);
+        let subst = TyBuilder::type_params_subst(db, self.id.parent);
        let ty = ty.subst(&subst.prefix(local_idx));
        Some(Type::new_with_resolver_inner(db, krate, &resolver, ty))
    }
@@ -1703,10 +1703,9 @@ impl Type {
    fn from_def(
        db: &dyn HirDatabase,
        krate: CrateId,
-        def: impl HasResolver + Into<TyDefId> + Into<GenericDefId>,
+        def: impl HasResolver + Into<TyDefId>,
    ) -> Type {
-        let substs = Substitution::build_for_def(db, def).fill_with_unknown().build();
+        let ty = TyBuilder::def_ty(db, def.into()).fill_with_unknown().build();
-        let ty = db.ty(def.into()).subst(&substs);
        Type::new(db, krate, def, ty)
    }
@@ -1785,13 +1784,10 @@ impl Type {
    }
    pub fn impls_trait(&self, db: &dyn HirDatabase, trait_: Trait, args: &[Type]) -> bool {
-        let trait_ref = hir_ty::TraitRef {
+        let trait_ref = TyBuilder::trait_ref(db, trait_.id)
-            trait_id: hir_ty::to_chalk_trait_id(trait_.id),
+            .push(self.ty.clone())
-            substitution: Substitution::build_for_def(db, trait_.id)
+            .fill(args.iter().map(|t| t.ty.clone()))
-                .push(self.ty.clone())
+            .build();
-                .fill(args.iter().map(|t| t.ty.clone()))
-                .build(),
-        };
        let goal = Canonical {
            value: hir_ty::InEnvironment::new(self.env.env.clone(), trait_ref.cast(&Interner)),
@@ -1804,11 +1800,10 @@ impl Type {
    pub fn normalize_trait_assoc_type(
        &self,
        db: &dyn HirDatabase,
-        trait_: Trait,
        args: &[Type],
        alias: TypeAlias,
    ) -> Option<Type> {
-        let subst = Substitution::build_for_def(db, trait_.id)
+        let projection = TyBuilder::assoc_type_projection(db, alias.id)
            .push(self.ty.clone())
            .fill(args.iter().map(|t| t.ty.clone()))
            .build();
@@ -1816,10 +1811,7 @@ impl Type {
            InEnvironment::new(
                self.env.env.clone(),
                AliasEq {
-                    alias: AliasTy::Projection(ProjectionTy {
+                    alias: AliasTy::Projection(projection),
-                        associated_ty_id: to_assoc_type_id(alias.id),
-                        substitution: subst,
-                    }),
                    ty: TyKind::BoundVar(BoundVar::new(DebruijnIndex::INNERMOST, 0))
                        .intern(&Interner),
                }
@@ -1831,7 +1823,7 @@ impl Type {
        match db.trait_solve(self.krate, goal)? {
            Solution::Unique(SolutionVariables(subst)) => subst
                .value
-                .interned(&Interner)
+                .interned()
                .first()
                .map(|ty| self.derived(ty.assert_ty_ref(&Interner).clone())),
            Solution::Ambig(_) => None,
diff --git a/crates/hir_def/src/attr.rs b/crates/hir_def/src/attr.rs
index 2bab121d9..442c5fb5b 100644
--- a/crates/hir_def/src/attr.rs
+++ b/crates/hir_def/src/attr.rs
@@ -533,7 +533,7 @@ impl Attr {
            };
            Some(AttrInput::Literal(value))
        } else if let Some(tt) = ast.token_tree() {
-            Some(AttrInput::TokenTree(ast_to_token_tree(&tt)?.0))
+            Some(AttrInput::TokenTree(ast_to_token_tree(&tt).0))
        } else {
            None
        };
diff --git a/crates/hir_def/src/body.rs b/crates/hir_def/src/body.rs
index 1080d9c2c..96b959967 100644
--- a/crates/hir_def/src/body.rs
+++ b/crates/hir_def/src/body.rs
@@ -226,7 +226,7 @@ pub struct Body {
    /// The `ExprId` of the actual body expression.
    pub body_expr: ExprId,
    /// Block expressions in this body that may contain inner items.
-    pub block_scopes: Vec<BlockId>,
+    block_scopes: Vec<BlockId>,
    _c: Count<Self>,
 }
@@ -302,7 +302,8 @@ impl Body {
            }
        };
        let expander = Expander::new(db, file_id, module);
-        let (body, source_map) = Body::new(db, expander, params, body);
+        let (mut body, source_map) = Body::new(db, expander, params, body);
+        body.shrink_to_fit();
        (Arc::new(body), Arc::new(source_map))
    }
@@ -310,6 +311,16 @@ impl Body {
        db.body_with_source_map(def).0
    }
+    /// Returns an iterator over all block expressions in this body that define inner items.
+    pub fn blocks<'a>(
+        &'a self,
+        db: &'a dyn DefDatabase,
+    ) -> impl Iterator<Item = (BlockId, Arc<DefMap>)> + '_ {
+        self.block_scopes
+            .iter()
+            .map(move |block| (*block, db.block_def_map(*block).expect("block ID without DefMap")))
+    }
    fn new(
        db: &dyn DefDatabase,
        expander: Expander,
@@ -318,6 +329,15 @@ impl Body {
    ) -> (Body, BodySourceMap) {
        lower::lower(db, expander, params, body)
    }
+    fn shrink_to_fit(&mut self) {
+        let Self { _c: _, body_expr: _, block_scopes, exprs, labels, params, pats } = self;
+        block_scopes.shrink_to_fit();
+        exprs.shrink_to_fit();
+        labels.shrink_to_fit();
+        params.shrink_to_fit();
+        pats.shrink_to_fit();
+    }
 }
 impl Index<ExprId> for Body {
diff --git a/crates/hir_def/src/body/lower.rs b/crates/hir_def/src/body/lower.rs
index 229e81dd4..63e89a1f4 100644
--- a/crates/hir_def/src/body/lower.rs
+++ b/crates/hir_def/src/body/lower.rs
@@ -673,12 +673,14 @@ impl ExprCollector<'_> {
        let block_loc =
            BlockLoc { ast_id, module: self.expander.def_map.module_id(self.expander.module) };
        let block_id = self.db.intern_block(block_loc);
-        self.body.block_scopes.push(block_id);
-        let opt_def_map = self.db.block_def_map(block_id);
+        let (module, def_map) = match self.db.block_def_map(block_id) {
-        let has_def_map = opt_def_map.is_some();
+            Some(def_map) => {
-        let def_map = opt_def_map.unwrap_or_else(|| self.expander.def_map.clone());
+                self.body.block_scopes.push(block_id);
-        let module = if has_def_map { def_map.root() } else { self.expander.module };
+                (def_map.root(), def_map)
+            }
+            None => (self.expander.module, self.expander.def_map.clone()),
+        };
        let prev_def_map = mem::replace(&mut self.expander.def_map, def_map);
        let prev_local_module = mem::replace(&mut self.expander.module, module);
        let prev_statements = std::mem::take(&mut self.statements_in_scope);
diff --git a/crates/hir_def/src/child_by_source.rs b/crates/hir_def/src/child_by_source.rs
index 2a331dcaf..f40a7f80d 100644
--- a/crates/hir_def/src/child_by_source.rs
+++ b/crates/hir_def/src/child_by_source.rs
@@ -160,7 +160,7 @@ impl ChildBySource for EnumId {
 impl ChildBySource for DefWithBodyId {
    fn child_by_source_to(&self, db: &dyn DefDatabase, res: &mut DynMap) {
        let body = db.body(*self);
-        for def_map in body.block_scopes.iter().filter_map(|block| db.block_def_map(*block)) {
+        for (_, def_map) in body.blocks(db) {
            // All block expressions are merged into the same map, because they logically all add
            // inner items to the containing `DefWithBodyId`.
            def_map[def_map.root()].scope.child_by_source_to(db, res);
diff --git a/crates/hir_def/src/data.rs b/crates/hir_def/src/data.rs
index 31f994681..135a6698e 100644
--- a/crates/hir_def/src/data.rs
+++ b/crates/hir_def/src/data.rs
@@ -10,7 +10,7 @@ use crate::{
    body::Expander,
    db::DefDatabase,
    intern::Interned,
-    item_tree::{AssocItem, FunctionQualifier, ItemTreeId, ModItem, Param},
+    item_tree::{AssocItem, FnFlags, ItemTreeId, ModItem, Param},
    type_ref::{TraitRef, TypeBound, TypeRef},
    visibility::RawVisibility,
    AssocContainerId, AssocItemId, ConstId, ConstLoc, FunctionId, FunctionLoc, HasModule, ImplId,
@@ -23,14 +23,9 @@ pub struct FunctionData {
    pub params: Vec<Interned<TypeRef>>,
    pub ret_type: Interned<TypeRef>,
    pub attrs: Attrs,
-    /// True if the first param is `self`. This is relevant to decide whether this
-    /// can be called as a method.
-    pub has_self_param: bool,
-    pub has_body: bool,
-    pub qualifier: FunctionQualifier,
-    pub is_in_extern_block: bool,
-    pub is_varargs: bool,
    pub visibility: RawVisibility,
+    pub abi: Option<Interned<str>>,
+    flags: FnFlags,
 }
 impl FunctionData {
@@ -53,6 +48,11 @@ impl FunctionData {
            .next_back()
            .map_or(false, |param| matches!(item_tree[param], Param::Varargs));
+        let mut flags = func.flags;
+        if is_varargs {
+            flags.bits |= FnFlags::IS_VARARGS;
+        }
        Arc::new(FunctionData {
            name: func.name.clone(),
            params: enabled_params
@@ -64,14 +64,45 @@ impl FunctionData {
                .collect(),
            ret_type: func.ret_type.clone(),
            attrs: item_tree.attrs(db, krate, ModItem::from(loc.id.value).into()),
-            has_self_param: func.has_self_param,
-            has_body: func.has_body,
-            qualifier: func.qualifier.clone(),
-            is_in_extern_block: func.is_in_extern_block,
-            is_varargs,
            visibility: item_tree[func.visibility].clone(),
+            abi: func.abi.clone(),
+            flags,
        })
    }
+    pub fn has_body(&self) -> bool {
+        self.flags.bits & FnFlags::HAS_BODY != 0
+    }
+    /// True if the first param is `self`. This is relevant to decide whether this
+    /// can be called as a method.
+    pub fn has_self_param(&self) -> bool {
+        self.flags.bits & FnFlags::HAS_SELF_PARAM != 0
+    }
+    pub fn is_default(&self) -> bool {
+        self.flags.bits & FnFlags::IS_DEFAULT != 0
+    }
+    pub fn is_const(&self) -> bool {
+        self.flags.bits & FnFlags::IS_CONST != 0
+    }
+    pub fn is_async(&self) -> bool {
+        self.flags.bits & FnFlags::IS_ASYNC != 0
+    }
+    pub fn is_unsafe(&self) -> bool {
+        self.flags.bits & FnFlags::IS_UNSAFE != 0
+    }
+    pub fn is_in_extern_block(&self) -> bool {
+        self.flags.bits & FnFlags::IS_IN_EXTERN_BLOCK != 0
+    }
+    pub fn is_varargs(&self) -> bool {
+        self.flags.bits & FnFlags::IS_VARARGS != 0
+    }
 }
 #[derive(Debug, Clone, PartialEq, Eq)]
diff --git a/crates/hir_def/src/db.rs b/crates/hir_def/src/db.rs
index 068b2ee38..9b7a213a1 100644
--- a/crates/hir_def/src/db.rs
+++ b/crates/hir_def/src/db.rs
@@ -13,6 +13,7 @@ use crate::{
    data::{ConstData, FunctionData, ImplData, StaticData, TraitData, TypeAliasData},
    generics::GenericParams,
    import_map::ImportMap,
+    intern::Interned,
    item_tree::ItemTree,
    lang_item::{LangItemTarget, LangItems},
    nameres::DefMap,
@@ -113,7 +114,7 @@ pub trait DefDatabase: InternDatabase + AstDatabase + Upcast<dyn AstDatabase> {
    fn expr_scopes(&self, def: DefWithBodyId) -> Arc<ExprScopes>;
    #[salsa::invoke(GenericParams::generic_params_query)]
-    fn generic_params(&self, def: GenericDefId) -> Arc<GenericParams>;
+    fn generic_params(&self, def: GenericDefId) -> Interned<GenericParams>;
    #[salsa::invoke(Attrs::variants_attrs_query)]
    fn variants_attrs(&self, def: EnumId) -> Arc<ArenaMap<LocalEnumVariantId, Attrs>>;
diff --git a/crates/hir_def/src/generics.rs b/crates/hir_def/src/generics.rs
index 7c6cbff11..de5acced8 100644
--- a/crates/hir_def/src/generics.rs
+++ b/crates/hir_def/src/generics.rs
@@ -2,7 +2,6 @@
 //! structs, impls, traits, etc. This module provides a common HIR for these
 //! generic parameters. See also the `Generics` type and the `generics_of` query
 //! in rustc.
-use std::sync::Arc;
 use base_db::FileId;
 use either::Either;
@@ -18,6 +17,7 @@ use crate::{
    child_by_source::ChildBySource,
    db::DefDatabase,
    dyn_map::DynMap,
+    intern::Interned,
    keys,
    src::{HasChildSource, HasSource},
    type_ref::{LifetimeRef, TypeBound, TypeRef},
@@ -26,27 +26,27 @@ use crate::{
 };
 /// Data about a generic type parameter (to a function, struct, impl, ...).
-#[derive(Clone, PartialEq, Eq, Debug)]
+#[derive(Clone, PartialEq, Eq, Debug, Hash)]
 pub struct TypeParamData {
    pub name: Option<Name>,
-    pub default: Option<TypeRef>,
+    pub default: Option<Interned<TypeRef>>,
    pub provenance: TypeParamProvenance,
 }
 /// Data about a generic lifetime parameter (to a function, struct, impl, ...).
-#[derive(Clone, PartialEq, Eq, Debug)]
+#[derive(Clone, PartialEq, Eq, Debug, Hash)]
 pub struct LifetimeParamData {
    pub name: Name,
 }
 /// Data about a generic const parameter (to a function, struct, impl, ...).
-#[derive(Clone, PartialEq, Eq, Debug)]
+#[derive(Clone, PartialEq, Eq, Debug, Hash)]
 pub struct ConstParamData {
    pub name: Name,
-    pub ty: TypeRef,
+    pub ty: Interned<TypeRef>,
 }
-#[derive(Copy, Clone, PartialEq, Eq, Debug)]
+#[derive(Copy, Clone, PartialEq, Eq, Debug, Hash)]
 pub enum TypeParamProvenance {
    TypeParamList,
    TraitSelf,
@@ -54,7 +54,7 @@ pub enum TypeParamProvenance {
 }
 /// Data about the generic parameters of a function, struct, impl, etc.
-#[derive(Clone, PartialEq, Eq, Debug, Default)]
+#[derive(Clone, PartialEq, Eq, Debug, Default, Hash)]
 pub struct GenericParams {
    pub types: Arena<TypeParamData>,
    pub lifetimes: Arena<LifetimeParamData>,
@@ -66,16 +66,16 @@ pub struct GenericParams {
 /// where clauses like `where T: Foo + Bar` are turned into multiple of these.
 /// It might still result in multiple actual predicates though, because of
 /// associated type bindings like `Iterator<Item = u32>`.
-#[derive(Clone, PartialEq, Eq, Debug)]
+#[derive(Clone, PartialEq, Eq, Debug, Hash)]
 pub enum WherePredicate {
    TypeBound { target: WherePredicateTypeTarget, bound: TypeBound },
    Lifetime { target: LifetimeRef, bound: LifetimeRef },
    ForLifetime { lifetimes: Box<[Name]>, target: WherePredicateTypeTarget, bound: TypeBound },
 }
-#[derive(Clone, PartialEq, Eq, Debug)]
+#[derive(Clone, PartialEq, Eq, Debug, Hash)]
 pub enum WherePredicateTypeTarget {
-    TypeRef(TypeRef),
+    TypeRef(Interned<TypeRef>),
    /// For desugared where predicates that can directly refer to a type param.
    TypeParam(LocalTypeParamId),
 }
@@ -91,7 +91,7 @@ impl GenericParams {
    pub(crate) fn generic_params_query(
        db: &dyn DefDatabase,
        def: GenericDefId,
-    ) -> Arc<GenericParams> {
+    ) -> Interned<GenericParams> {
        let _p = profile::span("generic_params_query");
        let generics = match def {
@@ -99,47 +99,49 @@ impl GenericParams {
                let id = id.lookup(db).id;
                let tree = id.item_tree(db);
                let item = &tree[id.value];
-                tree[item.generic_params].clone()
+                item.generic_params.clone()
            }
            GenericDefId::AdtId(AdtId::StructId(id)) => {
                let id = id.lookup(db).id;
                let tree = id.item_tree(db);
                let item = &tree[id.value];
-                tree[item.generic_params].clone()
+                item.generic_params.clone()
            }
            GenericDefId::AdtId(AdtId::EnumId(id)) => {
                let id = id.lookup(db).id;
                let tree = id.item_tree(db);
                let item = &tree[id.value];
-                tree[item.generic_params].clone()
+                item.generic_params.clone()
            }
            GenericDefId::AdtId(AdtId::UnionId(id)) => {
                let id = id.lookup(db).id;
                let tree = id.item_tree(db);
                let item = &tree[id.value];
-                tree[item.generic_params].clone()
+                item.generic_params.clone()
            }
            GenericDefId::TraitId(id) => {
                let id = id.lookup(db).id;
                let tree = id.item_tree(db);
                let item = &tree[id.value];
-                tree[item.generic_params].clone()
+                item.generic_params.clone()
            }
            GenericDefId::TypeAliasId(id) => {
                let id = id.lookup(db).id;
                let tree = id.item_tree(db);
                let item = &tree[id.value];
-                tree[item.generic_params].clone()
+                item.generic_params.clone()
            }
            GenericDefId::ImplId(id) => {
                let id = id.lookup(db).id;
                let tree = id.item_tree(db);
                let item = &tree[id.value];
-                tree[item.generic_params].clone()
+                item.generic_params.clone()
+            }
+            GenericDefId::EnumVariantId(_) | GenericDefId::ConstId(_) => {
+                Interned::new(GenericParams::default())
            }
-            GenericDefId::EnumVariantId(_) | GenericDefId::ConstId(_) => GenericParams::default(),
        };
-        Arc::new(generics)
+        generics
    }
    fn new(db: &dyn DefDatabase, def: GenericDefId) -> (GenericParams, InFile<SourceMap>) {
@@ -217,6 +219,7 @@ impl GenericParams {
            GenericDefId::EnumVariantId(_) | GenericDefId::ConstId(_) => FileId(!0).into(),
        };
+        generics.shrink_to_fit();
        (generics, InFile::new(file_id, sm))
    }
@@ -256,7 +259,8 @@ impl GenericParams {
        for type_param in params.type_params() {
            let name = type_param.name().map_or_else(Name::missing, |it| it.as_name());
            // FIXME: Use `Path::from_src`
-            let default = type_param.default_type().map(|it| TypeRef::from_ast(lower_ctx, it));
+            let default =
+                type_param.default_type().map(|it| Interned::new(TypeRef::from_ast(lower_ctx, it)));
            let param = TypeParamData {
                name: Some(name.clone()),
                default,
@@ -280,7 +284,7 @@ impl GenericParams {
        for const_param in params.const_params() {
            let name = const_param.name().map_or_else(Name::missing, |it| it.as_name());
            let ty = const_param.ty().map_or(TypeRef::Error, |it| TypeRef::from_ast(lower_ctx, it));
-            let param = ConstParamData { name, ty };
+            let param = ConstParamData { name, ty: Interned::new(ty) };
            let param_id = self.consts.alloc(param);
            sm.const_params.insert(param_id, const_param.clone());
        }
@@ -334,11 +338,11 @@ impl GenericParams {
            (Either::Left(type_ref), bound) => match hrtb_lifetimes {
                Some(hrtb_lifetimes) => WherePredicate::ForLifetime {
                    lifetimes: hrtb_lifetimes.clone(),
-                    target: WherePredicateTypeTarget::TypeRef(type_ref),
+                    target: WherePredicateTypeTarget::TypeRef(Interned::new(type_ref)),
                    bound,
                },
                None => WherePredicate::TypeBound {
-                    target: WherePredicateTypeTarget::TypeRef(type_ref),
+                    target: WherePredicateTypeTarget::TypeRef(Interned::new(type_ref)),
                    bound,
                },
            },
@@ -369,6 +373,14 @@ impl GenericParams {
        });
    }
+    pub(crate) fn shrink_to_fit(&mut self) {
+        let Self { consts, lifetimes, types, where_predicates } = self;
+        consts.shrink_to_fit();
+        lifetimes.shrink_to_fit();
+        types.shrink_to_fit();
+        where_predicates.shrink_to_fit();
+    }
    pub fn find_type_by_name(&self, name: &Name) -> Option<LocalTypeParamId> {
        self.types
            .iter()
diff --git a/crates/hir_def/src/intern.rs b/crates/hir_def/src/intern.rs
index d163f633f..2467e9299 100644
--- a/crates/hir_def/src/intern.rs
+++ b/crates/hir_def/src/intern.rs
@@ -14,6 +14,8 @@ use dashmap::{lock::RwLockWriteGuard, DashMap, SharedValue};
 use once_cell::sync::OnceCell;
 use rustc_hash::FxHasher;
+use crate::generics::GenericParams;
 type InternMap<T> = DashMap<Arc<T>, (), BuildHasherDefault<FxHasher>>;
 type Guard<T> =
    RwLockWriteGuard<'static, HashMap<Arc<T>, SharedValue<()>, BuildHasherDefault<FxHasher>>>;
@@ -194,4 +196,10 @@ macro_rules! impl_internable {
    )+ };
 }
-impl_internable!(crate::type_ref::TypeRef, crate::type_ref::TraitRef, crate::path::ModPath, str);
+impl_internable!(
+    crate::type_ref::TypeRef,
+    crate::type_ref::TraitRef,
+    crate::path::ModPath,
+    GenericParams,
+    str
+);
diff --git a/crates/hir_def/src/item_scope.rs b/crates/hir_def/src/item_scope.rs
index f3ebe7c72..a8ee5eeac 100644
--- a/crates/hir_def/src/item_scope.rs
+++ b/crates/hir_def/src/item_scope.rs
@@ -285,6 +285,28 @@ impl ItemScope {
            buf.push('\n');
        }
    }
+    pub(crate) fn shrink_to_fit(&mut self) {
+        // Exhaustive match to require handling new fields.
+        let Self {
+            types,
+            values,
+            macros,
+            unresolved,
+            defs,
+            impls,
+            unnamed_trait_imports,
+            legacy_macros,
+        } = self;
+        types.shrink_to_fit();
+        values.shrink_to_fit();
+        macros.shrink_to_fit();
+        unresolved.shrink_to_fit();
+        defs.shrink_to_fit();
+        impls.shrink_to_fit();
+        unnamed_trait_imports.shrink_to_fit();
+        legacy_macros.shrink_to_fit();
+    }
 }
 impl PerNs {
diff --git a/crates/hir_def/src/item_tree.rs b/crates/hir_def/src/item_tree.rs
index 69a313c7e..240662486 100644
--- a/crates/hir_def/src/item_tree.rs
+++ b/crates/hir_def/src/item_tree.rs
@@ -24,7 +24,7 @@ use la_arena::{Arena, Idx, RawIdx};
 use profile::Count;
 use rustc_hash::FxHashMap;
 use smallvec::SmallVec;
-use syntax::{ast, match_ast, SmolStr, SyntaxKind};
+use syntax::{ast, match_ast, SyntaxKind};
 use crate::{
    attr::{Attrs, RawAttrs},
@@ -58,13 +58,6 @@ impl fmt::Debug for RawVisibilityId {
    }
 }
-#[derive(Debug, Copy, Clone, Eq, PartialEq)]
-pub struct GenericParamsId(u32);
-impl GenericParamsId {
-    pub const EMPTY: Self = GenericParamsId(u32::max_value());
-}
 /// The item tree of a source file.
 #[derive(Debug, Default, Eq, PartialEq)]
 pub struct ItemTree {
@@ -146,7 +139,6 @@ impl ItemTree {
                macro_rules,
                macro_defs,
                vis,
-                generics,
                inner_items,
            } = &mut **data;
@@ -170,7 +162,6 @@ impl ItemTree {
            macro_defs.shrink_to_fit();
            vis.arena.shrink_to_fit();
-            generics.arena.shrink_to_fit();
            inner_items.shrink_to_fit();
        }
@@ -242,32 +233,6 @@ static VIS_PRIV: RawVisibility = RawVisibility::Module(ModPath::from_kind(PathKi
 static VIS_PUB_CRATE: RawVisibility = RawVisibility::Module(ModPath::from_kind(PathKind::Crate));
 #[derive(Default, Debug, Eq, PartialEq)]
-struct GenericParamsStorage {
-    arena: Arena<GenericParams>,
-}
-impl GenericParamsStorage {
-    fn alloc(&mut self, params: GenericParams) -> GenericParamsId {
-        if params.types.is_empty()
-            && params.lifetimes.is_empty()
-            && params.consts.is_empty()
-            && params.where_predicates.is_empty()
-        {
-            return GenericParamsId::EMPTY;
-        }
-        GenericParamsId(self.arena.alloc(params).into_raw().into())
-    }
-}
-static EMPTY_GENERICS: GenericParams = GenericParams {
-    types: Arena::new(),
-    lifetimes: Arena::new(),
-    consts: Arena::new(),
-    where_predicates: Vec::new(),
-};
-#[derive(Default, Debug, Eq, PartialEq)]
 struct ItemTreeData {
    imports: Arena<Import>,
    extern_crates: Arena<ExternCrate>,
@@ -289,7 +254,6 @@ struct ItemTreeData {
    macro_defs: Arena<MacroDef>,
    vis: ItemVisibilities,
-    generics: GenericParamsStorage,
    inner_items: FxHashMap<FileAstId<ast::BlockExpr>, SmallVec<[ModItem; 1]>>,
 }
@@ -508,17 +472,6 @@ impl Index<RawVisibilityId> for ItemTree {
    }
 }
-impl Index<GenericParamsId> for ItemTree {
-    type Output = GenericParams;
-    fn index(&self, index: GenericParamsId) -> &Self::Output {
-        match index {
-            GenericParamsId::EMPTY => &EMPTY_GENERICS,
-            _ => &self.data().generics.arena[Idx::from_raw(index.0.into())],
-        }
-    }
-}
 impl<N: ItemTreeNode> Index<FileItemTreeId<N>> for ItemTree {
    type Output = N;
    fn index(&self, id: FileItemTreeId<N>) -> &N {
@@ -529,7 +482,7 @@ impl<N: ItemTreeNode> Index<FileItemTreeId<N>> for ItemTree {
 /// A desugared `use` import.
 #[derive(Debug, Clone, Eq, PartialEq)]
 pub struct Import {
-    pub path: ModPath,
+    pub path: Interned<ModPath>,
    pub alias: Option<ImportAlias>,
    pub visibility: RawVisibilityId,
    pub is_glob: bool,
@@ -555,16 +508,12 @@ pub struct ExternCrate {
 pub struct Function {
    pub name: Name,
    pub visibility: RawVisibilityId,
-    pub generic_params: GenericParamsId,
+    pub generic_params: Interned<GenericParams>,
-    pub has_self_param: bool,
+    pub abi: Option<Interned<str>>,
-    pub has_body: bool,
-    pub qualifier: FunctionQualifier,
-    /// Whether the function is located in an `extern` block (*not* whether it is an
-    /// `extern "abi" fn`).
-    pub is_in_extern_block: bool,
    pub params: IdRange<Param>,
    pub ret_type: Interned<TypeRef>,
    pub ast_id: FileAstId<ast::Fn>,
+    pub(crate) flags: FnFlags,
 }
 #[derive(Debug, Clone, Eq, PartialEq)]
@@ -573,20 +522,28 @@ pub enum Param {
    Varargs,
 }
-#[derive(Debug, Clone, PartialEq, Eq)]
+#[derive(Debug, Clone, Copy, Eq, PartialEq, Default)]
-pub struct FunctionQualifier {
+pub(crate) struct FnFlags {
-    pub is_default: bool,
+    pub(crate) bits: u8,
-    pub is_const: bool,
+}
-    pub is_async: bool,
+impl FnFlags {
-    pub is_unsafe: bool,
+    pub(crate) const HAS_SELF_PARAM: u8 = 1 << 0;
-    pub abi: Option<SmolStr>,
+    pub(crate) const HAS_BODY: u8 = 1 << 1;
+    pub(crate) const IS_DEFAULT: u8 = 1 << 2;
+    pub(crate) const IS_CONST: u8 = 1 << 3;
+    pub(crate) const IS_ASYNC: u8 = 1 << 4;
+    pub(crate) const IS_UNSAFE: u8 = 1 << 5;
+    /// Whether the function is located in an `extern` block (*not* whether it is an
+    /// `extern "abi" fn`).
+    pub(crate) const IS_IN_EXTERN_BLOCK: u8 = 1 << 6;
+    pub(crate) const IS_VARARGS: u8 = 1 << 7;
 }
 #[derive(Debug, Clone, Eq, PartialEq)]
 pub struct Struct {
    pub name: Name,
    pub visibility: RawVisibilityId,
-    pub generic_params: GenericParamsId,
+    pub generic_params: Interned<GenericParams>,
    pub fields: Fields,
    pub ast_id: FileAstId<ast::Struct>,
    pub kind: StructDefKind,
@@ -606,7 +563,7 @@ pub enum StructDefKind {
 pub struct Union {
    pub name: Name,
    pub visibility: RawVisibilityId,
-    pub generic_params: GenericParamsId,
+    pub generic_params: Interned<GenericParams>,
    pub fields: Fields,
    pub ast_id: FileAstId<ast::Union>,
 }
@@ -615,7 +572,7 @@ pub struct Union {
 pub struct Enum {
    pub name: Name,
    pub visibility: RawVisibilityId,
-    pub generic_params: GenericParamsId,
+    pub generic_params: Interned<GenericParams>,
    pub variants: IdRange<Variant>,
    pub ast_id: FileAstId<ast::Enum>,
 }
@@ -644,7 +601,7 @@ pub struct Static {
 pub struct Trait {
    pub name: Name,
    pub visibility: RawVisibilityId,
-    pub generic_params: GenericParamsId,
+    pub generic_params: Interned<GenericParams>,
    pub is_auto: bool,
    pub is_unsafe: bool,
    pub bounds: Box<[TypeBound]>,
@@ -654,7 +611,7 @@ pub struct Trait {
 #[derive(Debug, Clone, Eq, PartialEq)]
 pub struct Impl {
-    pub generic_params: GenericParamsId,
+    pub generic_params: Interned<GenericParams>,
    pub target_trait: Option<Interned<TraitRef>>,
    pub self_ty: Interned<TypeRef>,
    pub is_negative: bool,
@@ -668,7 +625,7 @@ pub struct TypeAlias {
    pub visibility: RawVisibilityId,
    /// Bounds on the type alias itself. Only valid in trait declarations, eg. `type Assoc: Copy;`.
    pub bounds: Box<[TypeBound]>,
-    pub generic_params: GenericParamsId,
+    pub generic_params: Interned<GenericParams>,
    pub type_ref: Option<Interned<TypeRef>>,
    pub is_extern: bool,
    pub ast_id: FileAstId<ast::TypeAlias>,
diff --git a/crates/hir_def/src/item_tree/lower.rs b/crates/hir_def/src/item_tree/lower.rs
index 5247379c5..c5629af24 100644
--- a/crates/hir_def/src/item_tree/lower.rs
+++ b/crates/hir_def/src/item_tree/lower.rs
@@ -395,39 +395,51 @@ impl Ctx {
            ret_type
        };
-        let has_body = func.body().is_some();
+        let abi = func.abi().map(|abi| {
+            // FIXME: Abi::abi() -> Option<SyntaxToken>?
+            match abi.syntax().last_token() {
+                Some(tok) if tok.kind() == SyntaxKind::STRING => {
+                    // FIXME: Better way to unescape?
+                    Interned::new_str(tok.text().trim_matches('"'))
+                }
+                _ => {
+                    // `extern` default to be `extern "C"`.
+                    Interned::new_str("C")
+                }
+            }
+        });
        let ast_id = self.source_ast_id_map.ast_id(func);
-        let qualifier = FunctionQualifier {
-            is_default: func.default_token().is_some(),
+        let mut flags = FnFlags::default();
-            is_const: func.const_token().is_some(),
+        if func.body().is_some() {
-            is_async: func.async_token().is_some(),
+            flags.bits |= FnFlags::HAS_BODY;
-            is_unsafe: func.unsafe_token().is_some(),
+        }
-            abi: func.abi().map(|abi| {
+        if has_self_param {
-                // FIXME: Abi::abi() -> Option<SyntaxToken>?
+            flags.bits |= FnFlags::HAS_SELF_PARAM;
-                match abi.syntax().last_token() {
+        }
-                    Some(tok) if tok.kind() == SyntaxKind::STRING => {
+        if func.default_token().is_some() {
-                        // FIXME: Better way to unescape?
+            flags.bits |= FnFlags::IS_DEFAULT;
-                        tok.text().trim_matches('"').into()
+        }
-                    }
+        if func.const_token().is_some() {
-                    _ => {
+            flags.bits |= FnFlags::IS_CONST;
-                        // `extern` default to be `extern "C"`.
+        }
-                        "C".into()
+        if func.async_token().is_some() {
-                    }
+            flags.bits |= FnFlags::IS_ASYNC;
-                }
+        }
-            }),
+        if func.unsafe_token().is_some() {
-        };
+            flags.bits |= FnFlags::IS_UNSAFE;
+        }
        let mut res = Function {
            name,
            visibility,
-            generic_params: GenericParamsId::EMPTY,
+            generic_params: Interned::new(GenericParams::default()),
-            has_self_param,
+            abi,
-            has_body,
-            qualifier,
-            is_in_extern_block: false,
            params,
            ret_type: Interned::new(ret_type),
            ast_id,
+            flags,
        };
        res.generic_params = self.lower_generic_params(GenericsOwner::Function(&res), func);
@@ -577,7 +589,7 @@ impl Ctx {
            &self.hygiene,
            |path, _use_tree, is_glob, alias| {
                imports.push(id(tree.imports.alloc(Import {
-                    path,
+                    path: Interned::new(path),
                    alias,
                    visibility,
                    is_glob,
@@ -640,8 +652,10 @@ impl Ctx {
                        ast::ExternItem::Fn(ast) => {
                            let func_id = self.lower_function(&ast)?;
                            let func = &mut self.data().functions[func_id.index];
-                            func.qualifier.is_unsafe = is_intrinsic_fn_unsafe(&func.name);
+                            if is_intrinsic_fn_unsafe(&func.name) {
-                            func.is_in_extern_block = true;
+                                func.flags.bits |= FnFlags::IS_UNSAFE;
+                            }
+                            func.flags.bits |= FnFlags::IS_IN_EXTERN_BLOCK;
                            func_id.into()
                        }
                        ast::ExternItem::Static(ast) => {
@@ -668,7 +682,7 @@ impl Ctx {
        &mut self,
        owner: GenericsOwner<'_>,
        node: &impl ast::GenericParamsOwner,
-    ) -> GenericParamsId {
+    ) -> Interned<GenericParams> {
        // Generics are part of item headers and may contain inner items we need to collect.
        if let Some(params) = node.generic_param_list() {
            self.collect_inner_items(params.syntax());
@@ -684,7 +698,7 @@ impl Ctx {
        &mut self,
        owner: GenericsOwner<'_>,
        node: &impl ast::GenericParamsOwner,
-    ) -> GenericParamsId {
+    ) -> Interned<GenericParams> {
        let mut sm = &mut Default::default();
        let mut generics = GenericParams::default();
        match owner {
@@ -725,7 +739,8 @@ impl Ctx {
            }
        }
-        self.data().generics.alloc(generics)
+        generics.shrink_to_fit();
+        Interned::new(generics)
    }
    fn lower_type_bounds(&mut self, node: &impl ast::TypeBoundsOwner) -> Vec<TypeBound> {
diff --git a/crates/hir_def/src/lib.rs b/crates/hir_def/src/lib.rs
index f408e510a..be9a5e1a0 100644
--- a/crates/hir_def/src/lib.rs
+++ b/crates/hir_def/src/lib.rs
@@ -27,6 +27,7 @@ pub mod dyn_map;
 pub mod keys;
 pub mod item_tree;
+pub mod intern;
 pub mod adt;
 pub mod data;
@@ -49,7 +50,6 @@ pub mod import_map;
 #[cfg(test)]
 mod test_db;
-mod intern;
 use std::{
    hash::{Hash, Hasher},
diff --git a/crates/hir_def/src/nameres.rs b/crates/hir_def/src/nameres.rs
index 9e8e4e9ec..7dd68219f 100644
--- a/crates/hir_def/src/nameres.rs
+++ b/crates/hir_def/src/nameres.rs
@@ -409,6 +409,31 @@ impl DefMap {
            }
        }
    }
+    fn shrink_to_fit(&mut self) {
+        // Exhaustive match to require handling new fields.
+        let Self {
+            _c: _,
+            exported_proc_macros,
+            extern_prelude,
+            diagnostics,
+            modules,
+            block: _,
+            edition: _,
+            krate: _,
+            prelude: _,
+            root: _,
+        } = self;
+        extern_prelude.shrink_to_fit();
+        exported_proc_macros.shrink_to_fit();
+        diagnostics.shrink_to_fit();
+        modules.shrink_to_fit();
+        for (_, module) in modules.iter_mut() {
+            module.children.shrink_to_fit();
+            module.scope.shrink_to_fit();
+        }
+    }
 }
 impl ModuleData {
diff --git a/crates/hir_def/src/nameres/collector.rs b/crates/hir_def/src/nameres/collector.rs
index c8f494707..4ddc791ce 100644
--- a/crates/hir_def/src/nameres/collector.rs
+++ b/crates/hir_def/src/nameres/collector.rs
@@ -23,6 +23,7 @@ use crate::{
    attr::Attrs,
    db::DefDatabase,
    derive_macro_as_call_id,
+    intern::Interned,
    item_scope::{ImportType, PerNsGlobImports},
    item_tree::{
        self, FileItemTreeId, ItemTree, ItemTreeId, MacroCall, MacroDef, MacroRules, Mod, ModItem,
@@ -108,7 +109,9 @@ pub(super) fn collect_defs(
        }
    }
    collector.collect();
-    collector.finish()
+    let mut def_map = collector.finish();
+    def_map.shrink_to_fit();
+    def_map
 }
 #[derive(Copy, Clone, Debug, Eq, PartialEq)]
@@ -139,7 +142,7 @@ enum ImportSource {
 #[derive(Clone, Debug, Eq, PartialEq)]
 struct Import {
-    path: ModPath,
+    path: Interned<ModPath>,
    alias: Option<ImportAlias>,
    visibility: RawVisibility,
    is_glob: bool,
@@ -181,7 +184,10 @@ impl Import {
        let attrs = &tree.attrs(db, krate, ModItem::from(id.value).into());
        let visibility = &tree[it.visibility];
        Self {
-            path: ModPath::from_segments(PathKind::Plain, iter::once(it.name.clone())),
+            path: Interned::new(ModPath::from_segments(
+                PathKind::Plain,
+                iter::once(it.name.clone()),
+            )),
            alias: it.alias.clone(),
            visibility: visibility.clone(),
            is_glob: false,
diff --git a/crates/hir_def/src/path.rs b/crates/hir_def/src/path.rs
index a3e83e2cf..f9c8328f0 100644
--- a/crates/hir_def/src/path.rs
+++ b/crates/hir_def/src/path.rs
@@ -122,7 +122,7 @@ impl ModPath {
 pub struct Path {
    /// Type based path like `<T>::foo`.
    /// Note that paths like `<Type as Trait>::foo` are desugard to `Trait::<Self=Type>::foo`.
-    type_anchor: Option<Box<TypeRef>>,
+    type_anchor: Option<Interned<TypeRef>>,
    mod_path: Interned<ModPath>,
    /// Invariant: the same len as `self.mod_path.segments`
    generic_args: Vec<Option<Arc<GenericArgs>>>,
diff --git a/crates/hir_def/src/path/lower.rs b/crates/hir_def/src/path/lower.rs
index 28f6244da..7b29d9d4f 100644
--- a/crates/hir_def/src/path/lower.rs
+++ b/crates/hir_def/src/path/lower.rs
@@ -69,7 +69,7 @@ pub(super) fn lower_path(mut path: ast::Path, hygiene: &Hygiene) -> Option<Path>
                match trait_ref {
                    // <T>::foo
                    None => {
-                        type_anchor = Some(Box::new(self_type));
+                        type_anchor = Some(Interned::new(self_type));
                        kind = PathKind::Plain;
                    }
                    // <T as Trait<A>>::Foo desugars to Trait<Self=T, A>::Foo
diff --git a/crates/hir_def/src/resolver.rs b/crates/hir_def/src/resolver.rs
index a73585ee7..0391cc49b 100644
--- a/crates/hir_def/src/resolver.rs
+++ b/crates/hir_def/src/resolver.rs
@@ -14,6 +14,7 @@ use crate::{
    db::DefDatabase,
    expr::{ExprId, LabelId, PatId},
    generics::GenericParams,
+    intern::Interned,
    item_scope::{BuiltinShadowMode, BUILTIN_SCOPE},
    nameres::DefMap,
    path::{ModPath, PathKind},
@@ -50,7 +51,7 @@ enum Scope {
    /// All the items and imported names of a module
    ModuleScope(ModuleItemMap),
    /// Brings the generic parameters of an item into scope
-    GenericParams { def: GenericDefId, params: Arc<GenericParams> },
+    GenericParams { def: GenericDefId, params: Interned<GenericParams> },
    /// Brings `Self` in `impl` block into scope
    ImplDefScope(ImplId),
    /// Brings `Self` in enum, struct and union definitions into scope
diff --git a/crates/hir_def/src/visibility.rs b/crates/hir_def/src/visibility.rs
index 7d00a37c4..9908cd926 100644
--- a/crates/hir_def/src/visibility.rs
+++ b/crates/hir_def/src/visibility.rs
@@ -11,7 +11,7 @@ use crate::{
    nameres::DefMap,
    path::{ModPath, PathKind},
    resolver::HasResolver,
-    FunctionId, HasModule, LocalFieldId, ModuleDefId, ModuleId, VariantId,
+    FunctionId, HasModule, LocalFieldId, ModuleId, VariantId,
 };
 /// Visibility of an item, not yet resolved.
@@ -25,7 +25,7 @@ pub enum RawVisibility {
 }
 impl RawVisibility {
-    pub(crate) const fn private() -> RawVisibility {
+    pub(crate) fn private() -> RawVisibility {
        RawVisibility::Module(ModPath::from_kind(PathKind::Super(0)))
    }
@@ -217,6 +217,6 @@ pub(crate) fn field_visibilities_query(
 /// Resolve visibility of a function.
 pub(crate) fn function_visibility_query(db: &dyn DefDatabase, def: FunctionId) -> Visibility {
-    let resolver = ModuleDefId::from(def).module(db).unwrap().resolver(db);
+    let resolver = def.resolver(db);
    db.function_data(def).visibility.resolve(db, &resolver)
 }
diff --git a/crates/hir_expand/src/builtin_macro.rs b/crates/hir_expand/src/builtin_macro.rs
index 3aa3d8997..75ec4196b 100644
--- a/crates/hir_expand/src/builtin_macro.rs
+++ b/crates/hir_expand/src/builtin_macro.rs
@@ -584,7 +584,7 @@ mod tests {
                };
                let args = macro_call.token_tree().unwrap();
-                let parsed_args = mbe::ast_to_token_tree(&args).unwrap().0;
+                let parsed_args = mbe::ast_to_token_tree(&args).0;
                let call_id = AstId::new(file_id.into(), ast_id_map.ast_id(&macro_call));
                let arg_id = db.intern_eager_expansion({
diff --git a/crates/hir_expand/src/db.rs b/crates/hir_expand/src/db.rs
index c0ab70b60..10fe60821 100644
--- a/crates/hir_expand/src/db.rs
+++ b/crates/hir_expand/src/db.rs
@@ -119,7 +119,7 @@ pub fn expand_hypothetical(
    token_to_map: syntax::SyntaxToken,
 ) -> Option<(SyntaxNode, syntax::SyntaxToken)> {
    let macro_file = MacroFile { macro_call_id: actual_macro_call };
-    let (tt, tmap_1) = mbe::syntax_node_to_token_tree(hypothetical_args.syntax()).unwrap();
+    let (tt, tmap_1) = mbe::syntax_node_to_token_tree(hypothetical_args.syntax());
    let range =
        token_to_map.text_range().checked_sub(hypothetical_args.syntax().text_range().start())?;
    let token_id = tmap_1.token_by_range(range)?;
@@ -143,10 +143,7 @@ fn macro_def(db: &dyn AstDatabase, id: MacroDefId) -> Option<Arc<(TokenExpander,
        MacroDefKind::Declarative(ast_id) => match ast_id.to_node(db) {
            syntax::ast::Macro::MacroRules(macro_rules) => {
                let arg = macro_rules.token_tree()?;
-                let (tt, tmap) = mbe::ast_to_token_tree(&arg).or_else(|| {
+                let (tt, tmap) = mbe::ast_to_token_tree(&arg);
-                    log::warn!("fail on macro_rules to token tree: {:#?}", arg);
-                    None
-                })?;
                let rules = match MacroRules::parse(&tt) {
                    Ok(it) => it,
                    Err(err) => {
@@ -159,10 +156,7 @@ fn macro_def(db: &dyn AstDatabase, id: MacroDefId) -> Option<Arc<(TokenExpander,
            }
            syntax::ast::Macro::MacroDef(macro_def) => {
                let arg = macro_def.body()?;
-                let (tt, tmap) = mbe::ast_to_token_tree(&arg).or_else(|| {
+                let (tt, tmap) = mbe::ast_to_token_tree(&arg);
-                    log::warn!("fail on macro_def to token tree: {:#?}", arg);
-                    None
-                })?;
                let rules = match MacroDef::parse(&tt) {
                    Ok(it) => it,
                    Err(err) => {
@@ -202,7 +196,7 @@ fn macro_arg_text(db: &dyn AstDatabase, id: MacroCallId) -> Option<GreenNode> {
 fn macro_arg(db: &dyn AstDatabase, id: MacroCallId) -> Option<Arc<(tt::Subtree, mbe::TokenMap)>> {
    let arg = db.macro_arg_text(id)?;
-    let (tt, tmap) = mbe::syntax_node_to_token_tree(&SyntaxNode::new_root(arg))?;
+    let (tt, tmap) = mbe::syntax_node_to_token_tree(&SyntaxNode::new_root(arg));
    Some(Arc::new((tt, tmap)))
 }
diff --git a/crates/hir_expand/src/eager.rs b/crates/hir_expand/src/eager.rs
index 9eedc8461..9705526fa 100644
--- a/crates/hir_expand/src/eager.rs
+++ b/crates/hir_expand/src/eager.rs
@@ -106,7 +106,7 @@ pub fn expand_eager_macro(
    mut diagnostic_sink: &mut dyn FnMut(mbe::ExpandError),
 ) -> Result<EagerMacroId, ErrorEmitted> {
    let parsed_args = diagnostic_sink.option_with(
-        || Some(mbe::ast_to_token_tree(&macro_call.value.token_tree()?)?.0),
+        || Some(mbe::ast_to_token_tree(&macro_call.value.token_tree()?).0),
        || err("malformed macro invocation"),
    )?;
@@ -161,7 +161,7 @@ pub fn expand_eager_macro(
 }
 fn to_subtree(node: &SyntaxNode) -> Option<tt::Subtree> {
-    let mut subtree = mbe::syntax_node_to_token_tree(node)?.0;
+    let mut subtree = mbe::syntax_node_to_token_tree(node).0;
    subtree.delimiter = None;
    Some(subtree)
 }
diff --git a/crates/hir_ty/src/autoderef.rs b/crates/hir_ty/src/autoderef.rs
index c859f9491..7ca4af80e 100644
--- a/crates/hir_ty/src/autoderef.rs
+++ b/crates/hir_ty/src/autoderef.rs
@@ -12,12 +12,8 @@ use hir_expand::name::name;
 use log::{info, warn};
 use crate::{
-    db::HirDatabase,
+    db::HirDatabase, AliasEq, AliasTy, BoundVar, Canonical, CanonicalVarKinds, DebruijnIndex,
-    to_assoc_type_id, to_chalk_trait_id,
+    InEnvironment, Interner, Solution, Ty, TyBuilder, TyKind,
-    traits::{InEnvironment, Solution},
-    utils::generics,
-    AliasEq, AliasTy, BoundVar, Canonical, CanonicalVarKinds, DebruijnIndex, Interner,
-    ProjectionTy, Substitution, TraitRef, Ty, TyKind,
 };
 const AUTODEREF_RECURSION_LIMIT: usize = 10;
@@ -57,21 +53,20 @@ fn deref_by_trait(
    };
    let target = db.trait_data(deref_trait).associated_type_by_name(&name![Target])?;
-    let generic_params = generics(db.upcast(), target.into());
+    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 +79,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,9 +88,7 @@ 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,
diff --git a/crates/hir_ty/src/builder.rs b/crates/hir_ty/src/builder.rs
new file mode 100644
index 000000000..0bac31e4c
--- /dev/null
+++ b/crates/hir_ty/src/builder.rs
@@ -0,0 +1,219 @@
+//! `TyBuilder`, a helper for building instances of `Ty` and related types.
+use std::iter;
+use chalk_ir::{
+    cast::{Cast, CastTo, Caster},
+    interner::HasInterner,
+    AdtId, BoundVar, DebruijnIndex, Safety, Scalar,
+};
+use hir_def::{builtin_type::BuiltinType, GenericDefId, TraitId, TypeAliasId};
+use smallvec::SmallVec;
+use crate::{
+    db::HirDatabase, primitive, to_assoc_type_id, to_chalk_trait_id, utils::generics, Binders,
+    CallableSig, FnPointer, FnSig, GenericArg, Interner, ProjectionTy, Substitution, TraitRef, Ty,
+    TyDefId, TyKind, TypeWalk, ValueTyDefId,
+};
+/// This is a builder for `Ty` or anything that needs a `Substitution`.
+pub struct TyBuilder<D> {
+    /// The `data` field is used to keep track of what we're building (e.g. an
+    /// ADT, a `TraitRef`, ...).
+    data: D,
+    vec: SmallVec<[GenericArg; 2]>,
+    param_count: usize,
+}
+impl<D> TyBuilder<D> {
+    fn new(data: D, param_count: usize) -> TyBuilder<D> {
+        TyBuilder { data, param_count, vec: SmallVec::with_capacity(param_count) }
+    }
+    fn build_internal(self) -> (D, Substitution) {
+        assert_eq!(self.vec.len(), self.param_count);
+        // FIXME: would be good to have a way to construct a chalk_ir::Substitution from the interned form
+        let subst = Substitution::intern(self.vec);
+        (self.data, subst)
+    }
+    pub fn push(mut self, arg: impl CastTo<GenericArg>) -> Self {
+        self.vec.push(arg.cast(&Interner));
+        self
+    }
+    pub fn remaining(&self) -> usize {
+        self.param_count - self.vec.len()
+    }
+    pub fn fill_with_bound_vars(self, debruijn: DebruijnIndex, starting_from: usize) -> Self {
+        self.fill(
+            (starting_from..)
+                .map(|idx| TyKind::BoundVar(BoundVar::new(debruijn, idx)).intern(&Interner)),
+        )
+    }
+    pub fn fill_with_unknown(self) -> Self {
+        self.fill(iter::repeat(TyKind::Unknown.intern(&Interner)))
+    }
+    pub fn fill(mut self, filler: impl Iterator<Item = impl CastTo<GenericArg>>) -> Self {
+        self.vec.extend(filler.take(self.remaining()).casted(&Interner));
+        assert_eq!(self.remaining(), 0);
+        self
+    }
+    pub fn use_parent_substs(mut self, parent_substs: &Substitution) -> Self {
+        assert!(self.vec.is_empty());
+        assert!(parent_substs.len(&Interner) <= self.param_count);
+        self.vec.extend(parent_substs.iter(&Interner).cloned());
+        self
+    }
+}
+impl TyBuilder<()> {
+    pub fn unit() -> Ty {
+        TyKind::Tuple(0, Substitution::empty(&Interner)).intern(&Interner)
+    }
+    pub fn fn_ptr(sig: CallableSig) -> Ty {
+        TyKind::Function(FnPointer {
+            num_args: sig.params().len(),
+            sig: FnSig { abi: (), safety: Safety::Safe, variadic: sig.is_varargs },
+            substs: Substitution::from_iter(&Interner, sig.params_and_return.iter().cloned()),
+        })
+        .intern(&Interner)
+    }
+    pub fn builtin(builtin: BuiltinType) -> Ty {
+        match builtin {
+            BuiltinType::Char => TyKind::Scalar(Scalar::Char).intern(&Interner),
+            BuiltinType::Bool => TyKind::Scalar(Scalar::Bool).intern(&Interner),
+            BuiltinType::Str => TyKind::Str.intern(&Interner),
+            BuiltinType::Int(t) => {
+                TyKind::Scalar(Scalar::Int(primitive::int_ty_from_builtin(t))).intern(&Interner)
+            }
+            BuiltinType::Uint(t) => {
+                TyKind::Scalar(Scalar::Uint(primitive::uint_ty_from_builtin(t))).intern(&Interner)
+            }
+            BuiltinType::Float(t) => {
+                TyKind::Scalar(Scalar::Float(primitive::float_ty_from_builtin(t))).intern(&Interner)
+            }
+        }
+    }
+    pub fn type_params_subst(db: &dyn HirDatabase, def: impl Into<GenericDefId>) -> Substitution {
+        let params = generics(db.upcast(), def.into());
+        params.type_params_subst(db)
+    }
+    pub fn subst_for_def(db: &dyn HirDatabase, def: impl Into<GenericDefId>) -> TyBuilder<()> {
+        let def = def.into();
+        let params = generics(db.upcast(), def);
+        let param_count = params.len();
+        TyBuilder::new((), param_count)
+    }
+    pub fn build(self) -> Substitution {
+        let ((), subst) = self.build_internal();
+        subst
+    }
+}
+impl TyBuilder<hir_def::AdtId> {
+    pub fn adt(db: &dyn HirDatabase, adt: hir_def::AdtId) -> TyBuilder<hir_def::AdtId> {
+        let generics = generics(db.upcast(), adt.into());
+        let param_count = generics.len();
+        TyBuilder::new(adt, param_count)
+    }
+    pub fn fill_with_defaults(
+        mut self,
+        db: &dyn HirDatabase,
+        mut fallback: impl FnMut() -> Ty,
+    ) -> Self {
+        let defaults = db.generic_defaults(self.data.into());
+        for default_ty in defaults.iter().skip(self.vec.len()) {
+            if default_ty.skip_binders().is_unknown() {
+                self.vec.push(fallback().cast(&Interner));
+            } else {
+                // each default can depend on the previous parameters
+                let subst_so_far = Substitution::intern(self.vec.clone());
+                self.vec.push(default_ty.clone().subst(&subst_so_far).cast(&Interner));
+            }
+        }
+        self
+    }
+    pub fn build(self) -> Ty {
+        let (adt, subst) = self.build_internal();
+        TyKind::Adt(AdtId(adt), subst).intern(&Interner)
+    }
+}
+pub struct Tuple(usize);
+impl TyBuilder<Tuple> {
+    pub fn tuple(size: usize) -> TyBuilder<Tuple> {
+        TyBuilder::new(Tuple(size), size)
+    }
+    pub fn build(self) -> Ty {
+        let (Tuple(size), subst) = self.build_internal();
+        TyKind::Tuple(size, subst).intern(&Interner)
+    }
+}
+impl TyBuilder<TraitId> {
+    pub fn trait_ref(db: &dyn HirDatabase, trait_id: TraitId) -> TyBuilder<TraitId> {
+        let generics = generics(db.upcast(), trait_id.into());
+        let param_count = generics.len();
+        TyBuilder::new(trait_id, param_count)
+    }
+    pub fn build(self) -> TraitRef {
+        let (trait_id, substitution) = self.build_internal();
+        TraitRef { trait_id: to_chalk_trait_id(trait_id), substitution }
+    }
+}
+impl TyBuilder<TypeAliasId> {
+    pub fn assoc_type_projection(
+        db: &dyn HirDatabase,
+        type_alias: TypeAliasId,
+    ) -> TyBuilder<TypeAliasId> {
+        let generics = generics(db.upcast(), type_alias.into());
+        let param_count = generics.len();
+        TyBuilder::new(type_alias, param_count)
+    }
+    pub fn build(self) -> ProjectionTy {
+        let (type_alias, substitution) = self.build_internal();
+        ProjectionTy { associated_ty_id: to_assoc_type_id(type_alias), substitution }
+    }
+}
+impl<T: TypeWalk + HasInterner<Interner = Interner>> TyBuilder<Binders<T>> {
+    fn subst_binders(b: Binders<T>) -> Self {
+        let param_count = b.num_binders;
+        TyBuilder::new(b, param_count)
+    }
+    pub fn build(self) -> T {
+        let (b, subst) = self.build_internal();
+        b.subst(&subst)
+    }
+}
+impl TyBuilder<Binders<Ty>> {
+    pub fn def_ty(db: &dyn HirDatabase, def: TyDefId) -> TyBuilder<Binders<Ty>> {
+        TyBuilder::subst_binders(db.ty(def.into()))
+    }
+    pub fn impl_self_ty(db: &dyn HirDatabase, def: hir_def::ImplId) -> TyBuilder<Binders<Ty>> {
+        TyBuilder::subst_binders(db.impl_self_ty(def))
+    }
+    pub fn value_ty(db: &dyn HirDatabase, def: ValueTyDefId) -> TyBuilder<Binders<Ty>> {
+        TyBuilder::subst_binders(db.value_ty(def))
+    }
+}
diff --git a/crates/hir_ty/src/chalk_ext.rs b/crates/hir_ty/src/chalk_ext.rs
new file mode 100644
index 000000000..b7463366b
--- /dev/null
+++ b/crates/hir_ty/src/chalk_ext.rs
@@ -0,0 +1,13 @@
+//! Various extensions traits for Chalk types.
+use crate::{Interner, Ty, TyKind};
+pub trait TyExt {
+    fn is_unit(&self) -> bool;
+}
+impl TyExt for Ty {
+    fn is_unit(&self) -> bool {
+        matches!(self.kind(&Interner), TyKind::Tuple(0, _))
+    }
+}
diff --git a/crates/hir_ty/src/db.rs b/crates/hir_ty/src/db.rs
index 58e4247c6..4300680d9 100644
--- a/crates/hir_ty/src/db.rs
+++ b/crates/hir_ty/src/db.rs
@@ -123,7 +123,7 @@ pub trait HirDatabase: DefDatabase + Upcast<dyn DefDatabase> {
        &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)]
    fn program_clauses_for_chalk_env(
diff --git a/crates/hir_ty/src/diagnostics/decl_check.rs b/crates/hir_ty/src/diagnostics/decl_check.rs
index 33a0f4d7d..1c9f9ede7 100644
--- a/crates/hir_ty/src/diagnostics/decl_check.rs
+++ b/crates/hir_ty/src/diagnostics/decl_check.rs
@@ -91,7 +91,7 @@ impl<'a, 'b> DeclValidator<'a, 'b> {
    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 +99,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);
diff --git a/crates/hir_ty/src/diagnostics/expr.rs b/crates/hir_ty/src/diagnostics/expr.rs
index ad1259b34..8169b759f 100644
--- a/crates/hir_ty/src/diagnostics/expr.rs
+++ b/crates/hir_ty/src/diagnostics/expr.rs
@@ -15,7 +15,7 @@ use crate::{
        MissingPatFields, RemoveThisSemicolon,
    },
    utils::variant_data,
-    AdtId, InferenceResult, Interner, Ty, TyKind,
+    AdtId, InferenceResult, Interner, TyExt, TyKind,
 };
 pub(crate) use hir_def::{
@@ -423,7 +423,7 @@ impl<'a, 'b> ExprValidator<'a, 'b> {
            None => return,
        };
-        if mismatch.actual != Ty::unit() || mismatch.expected != *possible_tail_ty {
+        if !mismatch.actual.is_unit() || mismatch.expected != *possible_tail_ty {
            return;
        }
diff --git a/crates/hir_ty/src/diagnostics/unsafe_check.rs b/crates/hir_ty/src/diagnostics/unsafe_check.rs
index a71eebc6f..b5efe9df5 100644
--- a/crates/hir_ty/src/diagnostics/unsafe_check.rs
+++ b/crates/hir_ty/src/diagnostics/unsafe_check.rs
@@ -32,7 +32,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 +86,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,7 +103,7 @@ 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 });
diff --git a/crates/hir_ty/src/display.rs b/crates/hir_ty/src/display.rs
index 97f1092c6..148eb7506 100644
--- a/crates/hir_ty/src/display.rs
+++ b/crates/hir_ty/src/display.rs
@@ -19,7 +19,7 @@ use crate::{
    db::HirDatabase, from_assoc_type_id, from_foreign_def_id, from_placeholder_idx, primitive,
    to_assoc_type_id, traits::chalk::from_chalk, utils::generics, AdtId, AliasEq, AliasTy,
    CallableDefId, CallableSig, DomainGoal, GenericArg, ImplTraitId, Interner, Lifetime, OpaqueTy,
-    ProjectionTy, QuantifiedWhereClause, Scalar, Substitution, TraitRef, Ty, TyKind, WhereClause,
+    ProjectionTy, QuantifiedWhereClause, Scalar, TraitRef, Ty, TyExt, TyKind, WhereClause,
 };
 pub struct HirFormatter<'a> {
@@ -260,7 +260,7 @@ impl HirDisplay for ProjectionTy {
        write!(f, "<{} as {}", first_parameter, trait_.name)?;
        if self.substitution.len(&Interner) > 1 {
            write!(f, "<")?;
-            f.write_joined(&self.substitution.interned(&Interner)[1..], ", ")?;
+            f.write_joined(&self.substitution.interned()[1..], ", ")?;
            write!(f, ">")?;
        }
        write!(f, ">::{}", f.db.type_alias_data(from_assoc_type_id(self.associated_ty_id)).name)?;
@@ -387,7 +387,7 @@ impl HirDisplay for Ty {
                    write!(f, ",)")?;
                } else {
                    write!(f, "(")?;
-                    f.write_joined(&*substs.0, ", ")?;
+                    f.write_joined(&*substs.interned(), ", ")?;
                    write!(f, ")")?;
                }
            }
@@ -415,7 +415,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.interned()[..total_len], ", ")?;
                        write!(f, ">")?;
                    }
                }
@@ -423,7 +423,7 @@ impl HirDisplay for Ty {
                f.write_joined(sig.params(), ", ")?;
                write!(f, ")")?;
                let ret = sig.ret();
-                if *ret != Ty::unit() {
+                if !ret.is_unit() {
                    let ret_display = ret.into_displayable(
                        f.db,
                        f.max_size,
@@ -468,7 +468,7 @@ 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.interned().as_ref(),
                            Some(default_parameters) => {
                                let mut default_from = 0;
                                for (i, parameter) in parameters.iter(&Interner).enumerate() {
@@ -490,11 +490,11 @@ impl HirDisplay for Ty {
                                        }
                                    }
                                }
-                                &parameters.0[0..default_from]
+                                &parameters.interned()[0..default_from]
                            }
                        }
                    } else {
-                        parameters.0.as_ref()
+                        parameters.interned().as_ref()
                    };
                    if !parameters_to_write.is_empty() {
                        write!(f, "<")?;
@@ -517,7 +517,7 @@ impl HirDisplay for Ty {
                    write!(f, "{}::{}", trait_.name, type_alias_data.name)?;
                    if parameters.len(&Interner) > 0 {
                        write!(f, "<")?;
-                        f.write_joined(&*parameters.0, ", ")?;
+                        f.write_joined(&*parameters.interned(), ", ")?;
                        write!(f, ">")?;
                    }
                } else {
@@ -591,7 +591,7 @@ impl HirDisplay for Ty {
                        write!(f, "{}", param_data.name.clone().unwrap_or_else(Name::missing))?
                    }
                    TypeParamProvenance::ArgumentImplTrait => {
-                        let substs = Substitution::type_params_for_generics(f.db, &generics);
+                        let substs = generics.type_params_subst(f.db);
                        let bounds = f
                            .db
                            .generic_predicates(id.parent)
@@ -663,7 +663,7 @@ impl HirDisplay for CallableSig {
        }
        write!(f, ")")?;
        let ret = self.ret();
-        if *ret != Ty::unit() {
+        if !ret.is_unit() {
            let ret_display =
                ret.into_displayable(f.db, f.max_size, f.omit_verbose_types, f.display_target);
            write!(f, " -> {}", ret_display)?;
@@ -727,13 +727,13 @@ fn write_bounds_like_dyn_trait(
                // 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.interned() {
                    if is_fn_trait {
                        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.interned(), ", ")?;
                            write!(f, ")")?;
                        }
                    } else if !params.is_empty() {
@@ -789,7 +789,7 @@ impl TraitRef {
        write!(f, "{}", f.db.trait_data(self.hir_trait_id()).name)?;
        if self.substitution.len(&Interner) > 1 {
            write!(f, "<")?;
-            f.write_joined(&self.substitution.interned(&Interner)[1..], ", ")?;
+            f.write_joined(&self.substitution.interned()[1..], ", ")?;
            write!(f, ">")?;
        }
        Ok(())
diff --git a/crates/hir_ty/src/infer.rs b/crates/hir_ty/src/infer.rs
index b871594bd..bb885db35 100644
--- a/crates/hir_ty/src/infer.rs
+++ b/crates/hir_ty/src/infer.rs
@@ -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,
+    TypeWalk,
 };
 use crate::{
    db::HirDatabase, infer::diagnostics::InferenceDiagnostic, lower::ImplTraitLoweringMode,
-    to_assoc_type_id, to_chalk_trait_id, AliasEq, AliasTy, Interner, TyKind,
+    to_assoc_type_id, AliasEq, AliasTy, Interner, TyBuilder, TyKind,
 };
 // This lint has a false positive here. See the link below for details.
@@ -409,16 +409,14 @@ impl<'a> InferenceContext<'a> {
                    _ => panic!("resolve_associated_type called with non-associated type"),
                };
                let ty = self.table.new_type_var();
-                let substs = Substitution::build_for_def(self.db, res_assoc_ty)
+                let trait_ref = TyBuilder::trait_ref(self.db, trait_)
                    .push(inner_ty)
                    .fill(params.iter().cloned())
                    .build();
-                let trait_ref =
-                    TraitRef { trait_id: to_chalk_trait_id(trait_), substitution: substs.clone() };
                let alias_eq = AliasEq {
                    alias: AliasTy::Projection(ProjectionTy {
                        associated_ty_id: to_assoc_type_id(res_assoc_ty),
-                        substitution: substs,
+                        substitution: trait_ref.substitution.clone(),
                    }),
                    ty: ty.clone(),
                };
@@ -489,7 +487,7 @@ impl<'a> InferenceContext<'a> {
            }
            TypeNs::SelfType(impl_id) => {
                let generics = crate::utils::generics(self.db.upcast(), impl_id.into());
-                let substs = Substitution::type_params_for_generics(self.db, &generics);
+                let substs = generics.type_params_subst(self.db);
                let ty = self.db.impl_self_ty(impl_id).subst(&substs);
                match unresolved {
                    None => {
@@ -516,10 +514,9 @@ impl<'a> InferenceContext<'a> {
                }
            }
            TypeNs::TypeAliasId(it) => {
-                let substs = Substitution::build_for_def(self.db, it)
+                let ty = TyBuilder::def_ty(self.db, it.into())
                    .fill(std::iter::repeat_with(|| self.table.new_type_var()))
                    .build();
-                let ty = self.db.ty(it.into()).subst(&substs);
                let variant = ty_variant(&ty);
                forbid_unresolved_segments((ty, variant), unresolved)
            }
diff --git a/crates/hir_ty/src/infer/coerce.rs b/crates/hir_ty/src/infer/coerce.rs
index d887e21a2..32c273afc 100644
--- a/crates/hir_ty/src/infer/coerce.rs
+++ b/crates/hir_ty/src/infer/coerce.rs
@@ -7,9 +7,7 @@
 use chalk_ir::{cast::Cast, Mutability, TyVariableKind};
 use hir_def::lang_item::LangItemTarget;
-use crate::{
+use crate::{autoderef, Interner, Solution, Ty, TyBuilder, TyKind};
-    autoderef, to_chalk_trait_id, traits::Solution, Interner, Substitution, TraitRef, Ty, TyKind,
-};
 use super::{InEnvironment, InferenceContext};
@@ -44,8 +42,8 @@ impl<'a> InferenceContext<'a> {
                // https://github.com/rust-lang/rust/blob/7b805396bf46dce972692a6846ce2ad8481c5f85/src/librustc_typeck/check/coercion.rs#L877-L916
                let sig1 = ty1.callable_sig(self.db).expect("FnDef without callable sig");
                let sig2 = ty2.callable_sig(self.db).expect("FnDef without callable sig");
-                let ptr_ty1 = Ty::fn_ptr(sig1);
+                let ptr_ty1 = TyBuilder::fn_ptr(sig1);
-                let ptr_ty2 = Ty::fn_ptr(sig2);
+                let ptr_ty2 = TyBuilder::fn_ptr(sig2);
                self.coerce_merge_branch(&ptr_ty1, &ptr_ty2)
            } else {
                cov_mark::hit!(coerce_merge_fail_fallback);
@@ -95,7 +93,7 @@ impl<'a> InferenceContext<'a> {
            (TyKind::FnDef(..), TyKind::Function { .. }) => match from_ty.callable_sig(self.db) {
                None => return false,
                Some(sig) => {
-                    from_ty = Ty::fn_ptr(sig);
+                    from_ty = TyBuilder::fn_ptr(sig);
                }
            },
@@ -130,18 +128,15 @@ impl<'a> InferenceContext<'a> {
            _ => return None,
        };
-        let generic_params = crate::utils::generics(self.db.upcast(), coerce_unsized_trait.into());
+        let trait_ref = {
-        if generic_params.len() != 2 {
+            let b = TyBuilder::trait_ref(self.db, coerce_unsized_trait);
-            // The CoerceUnsized trait should have two generic params: Self and T.
+            if b.remaining() != 2 {
-            return None;
+                // The CoerceUnsized trait should have two generic params: Self and T.
-        }
+                return None;
+            }
+            b.push(from_ty.clone()).push(to_ty.clone()).build()
+        };
-        let substs = Substitution::build_for_generics(&generic_params)
-            .push(from_ty.clone())
-            .push(to_ty.clone())
-            .build();
-        let trait_ref =
-            TraitRef { trait_id: to_chalk_trait_id(coerce_unsized_trait), substitution: substs };
        let goal = InEnvironment::new(self.trait_env.env.clone(), trait_ref.cast(&Interner));
        let canonicalizer = self.canonicalizer();
diff --git a/crates/hir_ty/src/infer/expr.rs b/crates/hir_ty/src/infer/expr.rs
index dd3914ec3..ccaae53e9 100644
--- a/crates/hir_ty/src/infer/expr.rs
+++ b/crates/hir_ty/src/infer/expr.rs
@@ -19,11 +19,11 @@ use crate::{
    lower::lower_to_chalk_mutability,
    method_resolution, op,
    primitive::{self, UintTy},
-    to_assoc_type_id, to_chalk_trait_id,
+    to_chalk_trait_id,
-    traits::{chalk::from_chalk, FnTrait, InEnvironment},
+    traits::{chalk::from_chalk, FnTrait},
    utils::{generics, variant_data, Generics},
-    AdtId, Binders, CallableDefId, DomainGoal, FnPointer, FnSig, Interner, Rawness, Scalar,
+    AdtId, Binders, CallableDefId, FnPointer, FnSig, InEnvironment, Interner, Rawness, Scalar,
-    Substitution, TraitRef, Ty, TyKind,
+    Substitution, TraitRef, Ty, TyBuilder, TyKind,
 };
 use super::{
@@ -73,38 +73,33 @@ impl<'a> InferenceContext<'a> {
        let fn_once_trait = FnTrait::FnOnce.get_id(self.db, krate)?;
        let output_assoc_type =
            self.db.trait_data(fn_once_trait).associated_type_by_name(&name![Output])?;
-        let generic_params = generics(self.db.upcast(), fn_once_trait.into());
-        if generic_params.len() != 2 {
-            return None;
-        }
-        let mut param_builder = Substitution::builder(num_args);
        let mut arg_tys = vec![];
-        for _ in 0..num_args {
+        let arg_ty = TyBuilder::tuple(num_args)
-            let arg = self.table.new_type_var();
+            .fill(repeat_with(|| {
-            param_builder = param_builder.push(arg.clone());
+                let arg = self.table.new_type_var();
-            arg_tys.push(arg);
+                arg_tys.push(arg.clone());
-        }
+                arg
-        let parameters = param_builder.build();
+            }))
-        let arg_ty = TyKind::Tuple(num_args, parameters).intern(&Interner);
+            .build();
-        let substs =
-            Substitution::build_for_generics(&generic_params).push(ty.clone()).push(arg_ty).build();
+        let projection = {
+            let b = TyBuilder::assoc_type_projection(self.db, output_assoc_type);
+            if b.remaining() != 2 {
+                return None;
+            }
+            b.push(ty.clone()).push(arg_ty).build()
+        };
        let trait_env = self.trait_env.env.clone();
-        let implements_fn_trait: DomainGoal =
+        let obligation = InEnvironment {
-            TraitRef { trait_id: to_chalk_trait_id(fn_once_trait), substitution: substs.clone() }
+            goal: projection.trait_ref(self.db).cast(&Interner),
-                .cast(&Interner);
-        let goal = self.canonicalizer().canonicalize_obligation(InEnvironment {
-            goal: implements_fn_trait.clone(),
            environment: trait_env,
-        });
+        };
-        if self.db.trait_solve(krate, goal.value).is_some() {
+        let canonical = self.canonicalizer().canonicalize_obligation(obligation.clone());
-            self.push_obligation(implements_fn_trait);
+        if self.db.trait_solve(krate, canonical.value).is_some() {
-            let output_proj_ty = crate::ProjectionTy {
+            self.push_obligation(obligation.goal);
-                associated_ty_id: to_assoc_type_id(output_assoc_type),
+            let return_ty = self.normalize_projection_ty(projection);
-                substitution: substs,
-            };
-            let return_ty = self.normalize_projection_ty(output_proj_ty);
            Some((arg_tys, return_ty))
        } else {
            None
@@ -138,7 +133,7 @@ impl<'a> InferenceContext<'a> {
                both_arms_diverge &= mem::replace(&mut self.diverges, Diverges::Maybe);
                let else_ty = match else_branch {
                    Some(else_branch) => self.infer_expr_inner(*else_branch, &expected),
-                    None => Ty::unit(),
+                    None => TyBuilder::unit(),
                };
                both_arms_diverge &= self.diverges;
@@ -193,7 +188,7 @@ impl<'a> InferenceContext<'a> {
                    break_ty: self.table.new_type_var(),
                    label: label.map(|label| self.body[label].name.clone()),
                });
-                self.infer_expr(*body, &Expectation::has_type(Ty::unit()));
+                self.infer_expr(*body, &Expectation::has_type(TyBuilder::unit()));
                let ctxt = self.breakables.pop().expect("breakable stack broken");
                if ctxt.may_break {
@@ -217,11 +212,11 @@ impl<'a> InferenceContext<'a> {
                    *condition,
                    &Expectation::has_type(TyKind::Scalar(Scalar::Bool).intern(&Interner)),
                );
-                self.infer_expr(*body, &Expectation::has_type(Ty::unit()));
+                self.infer_expr(*body, &Expectation::has_type(TyBuilder::unit()));
                let _ctxt = self.breakables.pop().expect("breakable stack broken");
                // the body may not run, so it diverging doesn't mean we diverge
                self.diverges = Diverges::Maybe;
-                Ty::unit()
+                TyBuilder::unit()
            }
            Expr::For { iterable, body, pat, label } => {
                let iterable_ty = self.infer_expr(*iterable, &Expectation::none());
@@ -236,11 +231,11 @@ impl<'a> InferenceContext<'a> {
                self.infer_pat(*pat, &pat_ty, BindingMode::default());
-                self.infer_expr(*body, &Expectation::has_type(Ty::unit()));
+                self.infer_expr(*body, &Expectation::has_type(TyBuilder::unit()));
                let _ctxt = self.breakables.pop().expect("breakable stack broken");
                // the body may not run, so it diverging doesn't mean we diverge
                self.diverges = Diverges::Maybe;
-                Ty::unit()
+                TyBuilder::unit()
            }
            Expr::Lambda { body, args, ret_type, arg_types } => {
                assert_eq!(args.len(), arg_types.len());
@@ -360,7 +355,7 @@ impl<'a> InferenceContext<'a> {
                let val_ty = if let Some(expr) = expr {
                    self.infer_expr(*expr, &Expectation::none())
                } else {
-                    Ty::unit()
+                    TyBuilder::unit()
                };
                let last_ty =
@@ -386,7 +381,7 @@ impl<'a> InferenceContext<'a> {
                if let Some(expr) = expr {
                    self.infer_expr_coerce(*expr, &Expectation::has_type(self.return_ty.clone()));
                } else {
-                    let unit = Ty::unit();
+                    let unit = TyBuilder::unit();
                    self.coerce(&unit, &self.return_ty.clone());
                }
                TyKind::Never.intern(&Interner)
@@ -457,11 +452,7 @@ impl<'a> InferenceContext<'a> {
                    };
                    match canonicalized.decanonicalize_ty(derefed_ty.value).kind(&Interner) {
                        TyKind::Tuple(_, substs) => name.as_tuple_index().and_then(|idx| {
-                            substs
+                            substs.interned().get(idx).map(|a| a.assert_ty_ref(&Interner)).cloned()
-                                .interned(&Interner)
-                                .get(idx)
-                                .map(|a| a.assert_ty_ref(&Interner))
-                                .cloned()
                        }),
                        TyKind::Adt(AdtId(hir_def::AdtId::StructId(s)), parameters) => {
                            let local_id = self.db.struct_data(*s).variant_data.field(name)?;
@@ -539,17 +530,10 @@ impl<'a> InferenceContext<'a> {
            Expr::Box { expr } => {
                let inner_ty = self.infer_expr_inner(*expr, &Expectation::none());
                if let Some(box_) = self.resolve_boxed_box() {
-                    let mut sb =
+                    TyBuilder::adt(self.db, box_)
-                        Substitution::build_for_generics(&generics(self.db.upcast(), box_.into()));
+                        .push(inner_ty)
-                    sb = sb.push(inner_ty);
+                        .fill_with_defaults(self.db, || self.table.new_type_var())
-                    match self.db.generic_defaults(box_.into()).get(1) {
+                        .build()
-                        Some(alloc_ty) if !alloc_ty.value.is_unknown() && sb.remaining() > 0 => {
-                            sb = sb.push(alloc_ty.value.clone());
-                        }
-                        _ => (),
-                    }
-                    sb = sb.fill(repeat_with(|| self.table.new_type_var()));
-                    Ty::adt_ty(box_, sb.build())
                } else {
                    self.err_ty()
                }
@@ -639,31 +623,31 @@ impl<'a> InferenceContext<'a> {
                let rhs_ty = rhs.map(|e| self.infer_expr(e, &rhs_expect));
                match (range_type, lhs_ty, rhs_ty) {
                    (RangeOp::Exclusive, None, None) => match self.resolve_range_full() {
-                        Some(adt) => Ty::adt_ty(adt, Substitution::empty(&Interner)),
+                        Some(adt) => TyBuilder::adt(self.db, adt).build(),
                        None => self.err_ty(),
                    },
                    (RangeOp::Exclusive, None, Some(ty)) => match self.resolve_range_to() {
-                        Some(adt) => Ty::adt_ty(adt, Substitution::single(ty)),
+                        Some(adt) => TyBuilder::adt(self.db, adt).push(ty).build(),
                        None => self.err_ty(),
                    },
                    (RangeOp::Inclusive, None, Some(ty)) => {
                        match self.resolve_range_to_inclusive() {
-                            Some(adt) => Ty::adt_ty(adt, Substitution::single(ty)),
+                            Some(adt) => TyBuilder::adt(self.db, adt).push(ty).build(),
                            None => self.err_ty(),
                        }
                    }
                    (RangeOp::Exclusive, Some(_), Some(ty)) => match self.resolve_range() {
-                        Some(adt) => Ty::adt_ty(adt, Substitution::single(ty)),
+                        Some(adt) => TyBuilder::adt(self.db, adt).push(ty).build(),
                        None => self.err_ty(),
                    },
                    (RangeOp::Inclusive, Some(_), Some(ty)) => {
                        match self.resolve_range_inclusive() {
-                            Some(adt) => Ty::adt_ty(adt, Substitution::single(ty)),
+                            Some(adt) => TyBuilder::adt(self.db, adt).push(ty).build(),
                            None => self.err_ty(),
                        }
                    }
                    (RangeOp::Exclusive, Some(ty), None) => match self.resolve_range_from() {
-                        Some(adt) => Ty::adt_ty(adt, Substitution::single(ty)),
+                        Some(adt) => TyBuilder::adt(self.db, adt).push(ty).build(),
                        None => self.err_ty(),
                    },
                    (RangeOp::Inclusive, _, None) => self.err_ty(),
@@ -828,8 +812,8 @@ impl<'a> InferenceContext<'a> {
                // we don't even make an attempt at coercion
                self.table.new_maybe_never_var()
            } else {
-                self.coerce(&Ty::unit(), &expected.coercion_target());
+                self.coerce(&TyBuilder::unit(), &expected.coercion_target());
-                Ty::unit()
+                TyBuilder::unit()
            }
        };
        ty
diff --git a/crates/hir_ty/src/infer/pat.rs b/crates/hir_ty/src/infer/pat.rs
index 10df8d8cb..469f37dd9 100644
--- a/crates/hir_ty/src/infer/pat.rs
+++ b/crates/hir_ty/src/infer/pat.rs
@@ -13,9 +13,8 @@ use hir_expand::name::Name;
 use super::{BindingMode, Expectation, InferenceContext};
 use crate::{
-    lower::lower_to_chalk_mutability,
+    lower::lower_to_chalk_mutability, utils::variant_data, Interner, Substitution, Ty, TyBuilder,
-    utils::{generics, variant_data},
+    TyKind,
-    Interner, Substitution, Ty, TyKind,
 };
 impl<'a> InferenceContext<'a> {
@@ -124,7 +123,7 @@ impl<'a> InferenceContext<'a> {
        let ty = match &body[pat] {
            &Pat::Tuple { ref args, ellipsis } => {
                let expectations = match expected.as_tuple() {
-                    Some(parameters) => &*parameters.0,
+                    Some(parameters) => &*parameters.interned(),
                    _ => &[],
                };
@@ -240,29 +239,18 @@ impl<'a> InferenceContext<'a> {
                    let (inner_ty, alloc_ty) = match expected.as_adt() {
                        Some((adt, subst)) if adt == box_adt => (
                            subst.at(&Interner, 0).assert_ty_ref(&Interner).clone(),
-                            subst.interned(&Interner).get(1).and_then(|a| a.ty(&Interner).cloned()),
+                            subst.interned().get(1).and_then(|a| a.ty(&Interner).cloned()),
                        ),
                        _ => (self.result.standard_types.unknown.clone(), None),
                    };
                    let inner_ty = self.infer_pat(*inner, &inner_ty, default_bm);
-                    let mut sb = Substitution::build_for_generics(&generics(
+                    let mut b = TyBuilder::adt(self.db, box_adt).push(inner_ty);
-                        self.db.upcast(),
-                        box_adt.into(),
+                    if let Some(alloc_ty) = alloc_ty {
-                    ));
+                        b = b.push(alloc_ty);
-                    sb = sb.push(inner_ty);
-                    if sb.remaining() == 1 {
-                        sb = sb.push(match alloc_ty {
-                            Some(alloc_ty) if !alloc_ty.is_unknown() => alloc_ty,
-                            _ => match self.db.generic_defaults(box_adt.into()).get(1) {
-                                Some(alloc_ty) if !alloc_ty.value.is_unknown() => {
-                                    alloc_ty.value.clone()
-                                }
-                                _ => self.table.new_type_var(),
-                            },
-                        });
                    }
-                    Ty::adt_ty(box_adt, sb.build())
+                    b.fill_with_defaults(self.db, || self.table.new_type_var()).build()
                }
                None => self.err_ty(),
            },
diff --git a/crates/hir_ty/src/infer/path.rs b/crates/hir_ty/src/infer/path.rs
index 1ba15f737..637341b53 100644
--- a/crates/hir_ty/src/infer/path.rs
+++ b/crates/hir_ty/src/infer/path.rs
@@ -10,9 +10,7 @@ use hir_def::{
 };
 use hir_expand::name::Name;
-use crate::{
+use crate::{method_resolution, Interner, Substitution, Ty, TyBuilder, TyKind, ValueTyDefId};
-    method_resolution, to_chalk_trait_id, Interner, Substitution, Ty, TyKind, ValueTyDefId,
-};
 use super::{ExprOrPatId, InferenceContext, TraitRef};
@@ -82,7 +80,7 @@ impl<'a> InferenceContext<'a> {
            }
            ValueNs::ImplSelf(impl_id) => {
                let generics = crate::utils::generics(self.db.upcast(), impl_id.into());
-                let substs = Substitution::type_params_for_generics(self.db, &generics);
+                let substs = generics.type_params_subst(self.db);
                let ty = self.db.impl_self_ty(impl_id).subst(&substs);
                if let Some((AdtId::StructId(struct_id), substs)) = ty.as_adt() {
                    let ty = self.db.value_ty(struct_id.into()).subst(&substs);
@@ -95,16 +93,13 @@ impl<'a> InferenceContext<'a> {
            ValueNs::GenericParam(it) => return Some(self.db.const_param_ty(it)),
        };
-        let ty = self.db.value_ty(typable);
-        // self_subst is just for the parent
        let parent_substs = self_subst.unwrap_or_else(|| Substitution::empty(&Interner));
        let ctx = crate::lower::TyLoweringContext::new(self.db, &self.resolver);
        let substs = ctx.substs_from_path(path, typable, true);
-        let full_substs = Substitution::builder(substs.len(&Interner))
+        let ty = TyBuilder::value_ty(self.db, typable)
            .use_parent_substs(&parent_substs)
-            .fill(substs.interned(&Interner)[parent_substs.len(&Interner)..].iter().cloned())
+            .fill(substs.interned()[parent_substs.len(&Interner)..].iter().cloned())
            .build();
-        let ty = ty.subst(&full_substs);
        Some(ty)
    }
@@ -245,7 +240,7 @@ impl<'a> InferenceContext<'a> {
                };
                let substs = match container {
                    AssocContainerId::ImplId(impl_id) => {
-                        let impl_substs = Substitution::build_for_def(self.db, impl_id)
+                        let impl_substs = TyBuilder::subst_for_def(self.db, impl_id)
                            .fill(iter::repeat_with(|| self.table.new_type_var()))
                            .build();
                        let impl_self_ty = self.db.impl_self_ty(impl_id).subst(&impl_substs);
@@ -254,18 +249,12 @@ impl<'a> InferenceContext<'a> {
                    }
                    AssocContainerId::TraitId(trait_) => {
                        // we're picking this method
-                        let trait_substs = Substitution::build_for_def(self.db, trait_)
+                        let trait_ref = TyBuilder::trait_ref(self.db, trait_)
                            .push(ty.clone())
                            .fill(std::iter::repeat_with(|| self.table.new_type_var()))
                            .build();
-                        self.push_obligation(
+                        self.push_obligation(trait_ref.clone().cast(&Interner));
-                            TraitRef {
+                        Some(trait_ref.substitution)
-                                trait_id: to_chalk_trait_id(trait_),
-                                substitution: trait_substs.clone(),
-                            }
-                            .cast(&Interner),
-                        );
-                        Some(trait_substs)
                    }
                    AssocContainerId::ModuleId(_) => None,
                };
diff --git a/crates/hir_ty/src/infer/unify.rs b/crates/hir_ty/src/infer/unify.rs
index d2496db3b..b7bc48569 100644
--- a/crates/hir_ty/src/infer/unify.rs
+++ b/crates/hir_ty/src/infer/unify.rs
@@ -186,14 +186,11 @@ pub(crate) fn unify(tys: &Canonical<(Ty, Ty)>) -> Option<Substitution> {
            );
        }
    }
-    Some(
+    Some(Substitution::from_iter(
-        Substitution::builder(tys.binders.len(&Interner))
+        &Interner,
-            .fill(
+        vars.iter(&Interner)
-                vars.iter(&Interner)
+            .map(|v| table.resolve_ty_completely(v.assert_ty_ref(&Interner).clone())),
-                    .map(|v| table.resolve_ty_completely(v.assert_ty_ref(&Interner).clone())),
+    ))
-            )
-            .build(),
-    )
 }
 #[derive(Clone, Debug)]
@@ -287,7 +284,7 @@ impl InferenceTable {
        substs2: &Substitution,
        depth: usize,
    ) -> bool {
-        substs1.0.iter().zip(substs2.0.iter()).all(|(t1, t2)| {
+        substs1.iter(&Interner).zip(substs2.iter(&Interner)).all(|(t1, t2)| {
            self.unify_inner(t1.assert_ty_ref(&Interner), t2.assert_ty_ref(&Interner), depth)
        })
    }
diff --git a/crates/hir_ty/src/lib.rs b/crates/hir_ty/src/lib.rs
index 4c3d904bf..76609e2df 100644
--- a/crates/hir_ty/src/lib.rs
+++ b/crates/hir_ty/src/lib.rs
@@ -14,6 +14,10 @@ mod lower;
 pub(crate) mod infer;
 pub(crate) mod utils;
 mod chalk_cast;
+mod chalk_ext;
+mod builder;
+mod walk;
+mod types;
 pub mod display;
 pub mod db;
@@ -24,30 +28,30 @@ mod tests;
 #[cfg(test)]
 mod test_db;
-use std::{iter, mem, sync::Arc};
+use std::sync::Arc;
-use base_db::salsa;
-use chalk_ir::cast::{CastTo, Caster};
-use hir_def::{
-    builtin_type::BuiltinType, expr::ExprId, type_ref::Rawness, AssocContainerId, FunctionId,
-    GenericDefId, HasModule, LifetimeParamId, Lookup, TraitId, TypeAliasId, TypeParamId,
-};
 use itertools::Itertools;
 use smallvec::SmallVec;
-use crate::{
+use base_db::salsa;
-    db::HirDatabase,
+use hir_def::{
-    display::HirDisplay,
+    expr::ExprId, type_ref::Rawness, AssocContainerId, FunctionId, GenericDefId, HasModule, Lookup,
-    utils::{generics, make_mut_slice, Generics},
+    TraitId, TypeAliasId, TypeParamId,
 };
+use crate::{db::HirDatabase, display::HirDisplay, utils::generics};
 pub use autoderef::autoderef;
+pub use builder::TyBuilder;
+pub use chalk_ext::TyExt;
 pub use infer::{could_unify, InferenceResult, InferenceVar};
 pub use lower::{
    associated_type_shorthand_candidates, callable_item_sig, CallableDefId, ImplTraitLoweringMode,
    TyDefId, TyLoweringContext, ValueTyDefId,
 };
-pub use traits::{AliasEq, DomainGoal, InEnvironment, TraitEnvironment};
+pub use traits::TraitEnvironment;
+pub use types::*;
+pub use walk::TypeWalk;
 pub use chalk_ir::{
    cast::Cast, AdtId, BoundVar, DebruijnIndex, Mutability, Safety, Scalar, TyVariableKind,
@@ -66,41 +70,6 @@ pub type CanonicalVarKinds = chalk_ir::CanonicalVarKinds<Interner>;
 pub type ChalkTraitId = chalk_ir::TraitId<Interner>;
-#[derive(Clone, PartialEq, Eq, Debug, Hash)]
-pub enum Lifetime {
-    Parameter(LifetimeParamId),
-    Static,
-}
-#[derive(Clone, PartialEq, Eq, Debug, Hash)]
-pub struct OpaqueTy {
-    pub opaque_ty_id: OpaqueTyId,
-    pub substitution: Substitution,
-}
-impl TypeWalk for OpaqueTy {
-    fn walk(&self, f: &mut impl FnMut(&Ty)) {
-        self.substitution.walk(f);
-    }
-    fn walk_mut_binders(
-        &mut self,
-        f: &mut impl FnMut(&mut Ty, DebruijnIndex),
-        binders: DebruijnIndex,
-    ) {
-        self.substitution.walk_mut_binders(f, binders);
-    }
-}
-/// A "projection" type corresponds to an (unnormalized)
-/// projection like `<P0 as Trait<P1..Pn>>::Foo`. Note that the
-/// trait and all its parameters are fully known.
-#[derive(Clone, PartialEq, Eq, Debug, Hash)]
-pub struct ProjectionTy {
-    pub associated_ty_id: AssocTypeId,
-    pub substitution: Substitution,
-}
 impl ProjectionTy {
    pub fn trait_ref(&self, db: &dyn HirDatabase) -> TraitRef {
        TraitRef {
@@ -110,7 +79,7 @@ impl ProjectionTy {
    }
    pub fn self_type_parameter(&self) -> &Ty {
-        &self.substitution.interned(&Interner)[0].assert_ty_ref(&Interner)
+        &self.substitution.interned()[0].assert_ty_ref(&Interner)
    }
    fn trait_(&self, db: &dyn HirDatabase) -> TraitId {
@@ -121,322 +90,11 @@ impl ProjectionTy {
    }
 }
-impl TypeWalk for ProjectionTy {
-    fn walk(&self, f: &mut impl FnMut(&Ty)) {
-        self.substitution.walk(f);
-    }
-    fn walk_mut_binders(
-        &mut self,
-        f: &mut impl FnMut(&mut Ty, DebruijnIndex),
-        binders: DebruijnIndex,
-    ) {
-        self.substitution.walk_mut_binders(f, binders);
-    }
-}
-#[derive(Clone, PartialEq, Eq, Debug, Hash)]
-pub struct DynTy {
-    /// The unknown self type.
-    pub bounds: Binders<QuantifiedWhereClauses>,
-}
 pub type FnSig = chalk_ir::FnSig<Interner>;
-#[derive(Clone, PartialEq, Eq, Debug, Hash)]
-pub struct FnPointer {
-    pub num_args: usize,
-    pub sig: FnSig,
-    pub substs: Substitution,
-}
-#[derive(Clone, PartialEq, Eq, Debug, Hash)]
-pub enum AliasTy {
-    /// A "projection" type corresponds to an (unnormalized)
-    /// projection like `<P0 as Trait<P1..Pn>>::Foo`. Note that the
-    /// trait and all its parameters are fully known.
-    Projection(ProjectionTy),
-    /// An opaque type (`impl Trait`).
-    ///
-    /// This is currently only used for return type impl trait; each instance of
-    /// `impl Trait` in a return type gets its own ID.
-    Opaque(OpaqueTy),
-}
-impl TypeWalk for AliasTy {
-    fn walk(&self, f: &mut impl FnMut(&Ty)) {
-        match self {
-            AliasTy::Projection(it) => it.walk(f),
-            AliasTy::Opaque(it) => it.walk(f),
-        }
-    }
-    fn walk_mut_binders(
-        &mut self,
-        f: &mut impl FnMut(&mut Ty, DebruijnIndex),
-        binders: DebruijnIndex,
-    ) {
-        match self {
-            AliasTy::Projection(it) => it.walk_mut_binders(f, binders),
-            AliasTy::Opaque(it) => it.walk_mut_binders(f, binders),
-        }
-    }
-}
-/// A type.
-///
-/// See also the `TyKind` enum in rustc (librustc/ty/sty.rs), which represents
-/// the same thing (but in a different way).
-///
-/// This should be cheap to clone.
-#[derive(Clone, PartialEq, Eq, Debug, Hash)]
-pub enum TyKind {
-    /// Structures, enumerations and unions.
-    Adt(AdtId<Interner>, Substitution),
-    /// Represents an associated item like `Iterator::Item`.  This is used
-    /// when we have tried to normalize a projection like `T::Item` but
-    /// couldn't find a better representation.  In that case, we generate
-    /// an **application type** like `(Iterator::Item)<T>`.
-    AssociatedType(AssocTypeId, Substitution),
-    /// a scalar type like `bool` or `u32`
-    Scalar(Scalar),
-    /// A tuple type.  For example, `(i32, bool)`.
-    Tuple(usize, Substitution),
-    /// An array with the given length. Written as `[T; n]`.
-    Array(Ty),
-    /// The pointee of an array slice.  Written as `[T]`.
-    Slice(Ty),
-    /// A raw pointer. Written as `*mut T` or `*const T`
-    Raw(Mutability, Ty),
-    /// A reference; a pointer with an associated lifetime. Written as
-    /// `&'a mut T` or `&'a T`.
-    Ref(Mutability, Ty),
-    /// This represents a placeholder for an opaque type in situations where we
-    /// don't know the hidden type (i.e. currently almost always). This is
-    /// analogous to the `AssociatedType` type constructor.
-    /// It is also used as the type of async block, with one type parameter
-    /// representing the Future::Output type.
-    OpaqueType(OpaqueTyId, Substitution),
-    /// The anonymous type of a function declaration/definition. Each
-    /// function has a unique type, which is output (for a function
-    /// named `foo` returning an `i32`) as `fn() -> i32 {foo}`.
-    ///
-    /// This includes tuple struct / enum variant constructors as well.
-    ///
-    /// For example the type of `bar` here:
-    ///
-    /// ```
-    /// fn foo() -> i32 { 1 }
-    /// let bar = foo; // bar: fn() -> i32 {foo}
-    /// ```
-    FnDef(FnDefId, Substitution),
-    /// The pointee of a string slice. Written as `str`.
-    Str,
-    /// The never type `!`.
-    Never,
-    /// The type of a specific closure.
-    ///
-    /// The closure signature is stored in a `FnPtr` type in the first type
-    /// parameter.
-    Closure(ClosureId, Substitution),
-    /// Represents a foreign type declared in external blocks.
-    ForeignType(ForeignDefId),
-    /// A pointer to a function.  Written as `fn() -> i32`.
-    ///
-    /// For example the type of `bar` here:
-    ///
-    /// ```
-    /// fn foo() -> i32 { 1 }
-    /// let bar: fn() -> i32 = foo;
-    /// ```
-    Function(FnPointer),
-    /// An "alias" type represents some form of type alias, such as:
-    /// - An associated type projection like `<T as Iterator>::Item`
-    /// - `impl Trait` types
-    /// - Named type aliases like `type Foo<X> = Vec<X>`
-    Alias(AliasTy),
-    /// A placeholder for a type parameter; for example, `T` in `fn f<T>(x: T)
-    /// {}` when we're type-checking the body of that function. In this
-    /// situation, we know this stands for *some* type, but don't know the exact
-    /// type.
-    Placeholder(PlaceholderIndex),
-    /// A bound type variable. This is used in various places: when representing
-    /// some polymorphic type like the type of function `fn f<T>`, the type
-    /// parameters get turned into variables; during trait resolution, inference
-    /// variables get turned into bound variables and back; and in `Dyn` the
-    /// `Self` type is represented with a bound variable as well.
-    BoundVar(BoundVar),
-    /// A type variable used during type checking.
-    InferenceVar(InferenceVar, TyVariableKind),
-    /// A trait object (`dyn Trait` or bare `Trait` in pre-2018 Rust).
-    ///
-    /// The predicates are quantified over the `Self` type, i.e. `Ty::Bound(0)`
-    /// represents the `Self` type inside the bounds. This is currently
-    /// implicit; Chalk has the `Binders` struct to make it explicit, but it
-    /// didn't seem worth the overhead yet.
-    Dyn(DynTy),
-    /// A placeholder for a type which could not be computed; this is propagated
-    /// to avoid useless error messages. Doubles as a placeholder where type
-    /// variables are inserted before type checking, since we want to try to
-    /// infer a better type here anyway -- for the IDE use case, we want to try
-    /// to infer as much as possible even in the presence of type errors.
-    Unknown,
-}
-#[derive(Clone, PartialEq, Eq, Debug, Hash)]
-pub struct Ty(Arc<TyKind>);
-impl TyKind {
-    pub fn intern(self, _interner: &Interner) -> Ty {
-        Ty(Arc::new(self))
-    }
-}
-impl Ty {
-    pub fn kind(&self, _interner: &Interner) -> &TyKind {
-        &self.0
-    }
-    pub fn interned_mut(&mut self) -> &mut TyKind {
-        Arc::make_mut(&mut self.0)
-    }
-    pub fn into_inner(self) -> TyKind {
-        Arc::try_unwrap(self.0).unwrap_or_else(|a| (*a).clone())
-    }
-}
-#[derive(Clone, PartialEq, Eq, Debug, Hash)]
-pub struct GenericArg {
-    interned: GenericArgData,
-}
-#[derive(Clone, PartialEq, Eq, Debug, Hash)]
-pub enum GenericArgData {
-    Ty(Ty),
-}
-impl GenericArg {
-    /// Constructs a generic argument using `GenericArgData`.
-    pub fn new(_interner: &Interner, data: GenericArgData) -> Self {
-        GenericArg { interned: data }
-    }
-    /// Gets the interned value.
-    pub fn interned(&self) -> &GenericArgData {
-        &self.interned
-    }
-    /// Asserts that this is a type argument.
-    pub fn assert_ty_ref(&self, interner: &Interner) -> &Ty {
-        self.ty(interner).unwrap()
-    }
-    /// Checks whether the generic argument is a type.
-    pub fn is_ty(&self, _interner: &Interner) -> bool {
-        match self.interned() {
-            GenericArgData::Ty(_) => true,
-        }
-    }
-    /// Returns the type if it is one, `None` otherwise.
-    pub fn ty(&self, _interner: &Interner) -> Option<&Ty> {
-        match self.interned() {
-            GenericArgData::Ty(t) => Some(t),
-        }
-    }
-}
-impl TypeWalk for GenericArg {
-    fn walk(&self, f: &mut impl FnMut(&Ty)) {
-        match &self.interned {
-            GenericArgData::Ty(ty) => {
-                ty.walk(f);
-            }
-        }
-    }
-    fn walk_mut_binders(
-        &mut self,
-        f: &mut impl FnMut(&mut Ty, DebruijnIndex),
-        binders: DebruijnIndex,
-    ) {
-        match &mut self.interned {
-            GenericArgData::Ty(ty) => {
-                ty.walk_mut_binders(f, binders);
-            }
-        }
-    }
-}
-/// A list of substitutions for generic parameters.
-#[derive(Clone, PartialEq, Eq, Debug, Hash)]
-pub struct Substitution(SmallVec<[GenericArg; 2]>);
-impl TypeWalk for Substitution {
-    fn walk(&self, f: &mut impl FnMut(&Ty)) {
-        for t in self.0.iter() {
-            t.walk(f);
-        }
-    }
-    fn walk_mut_binders(
-        &mut self,
-        f: &mut impl FnMut(&mut Ty, DebruijnIndex),
-        binders: DebruijnIndex,
-    ) {
-        for t in &mut self.0 {
-            t.walk_mut_binders(f, binders);
-        }
-    }
-}
 impl Substitution {
-    pub fn interned(&self, _: &Interner) -> &[GenericArg] {
-        &self.0
-    }
-    pub fn len(&self, _: &Interner) -> usize {
-        self.0.len()
-    }
-    pub fn is_empty(&self, _: &Interner) -> bool {
-        self.0.is_empty()
-    }
-    pub fn at(&self, _: &Interner, i: usize) -> &GenericArg {
-        &self.0[i]
-    }
-    pub fn empty(_: &Interner) -> Substitution {
-        Substitution(SmallVec::new())
-    }
-    pub fn iter(&self, _: &Interner) -> std::slice::Iter<'_, GenericArg> {
-        self.0.iter()
-    }
    pub fn single(ty: Ty) -> Substitution {
-        Substitution({
+        Substitution::intern({
            let mut v = SmallVec::new();
            v.push(ty.cast(&Interner));
            v
@@ -444,64 +102,14 @@ impl Substitution {
    }
    pub fn prefix(&self, n: usize) -> Substitution {
-        Substitution(self.0[..std::cmp::min(self.0.len(), n)].into())
+        Substitution::intern(self.interned()[..std::cmp::min(self.len(&Interner), n)].into())
    }
    pub fn suffix(&self, n: usize) -> Substitution {
-        Substitution(self.0[self.0.len() - std::cmp::min(self.0.len(), n)..].into())
+        Substitution::intern(
-    }
+            self.interned()[self.len(&Interner) - std::cmp::min(self.len(&Interner), n)..].into(),
-    pub fn from_iter(
-        interner: &Interner,
-        elements: impl IntoIterator<Item = impl CastTo<GenericArg>>,
-    ) -> Self {
-        Substitution(elements.into_iter().casted(interner).collect())
-    }
-    /// Return Substs that replace each parameter by itself (i.e. `Ty::Param`).
-    pub(crate) fn type_params_for_generics(
-        db: &dyn HirDatabase,
-        generic_params: &Generics,
-    ) -> Substitution {
-        Substitution::from_iter(
-            &Interner,
-            generic_params
-                .iter()
-                .map(|(id, _)| TyKind::Placeholder(to_placeholder_idx(db, id)).intern(&Interner)),
-        )
-    }
-    /// Return Substs that replace each parameter by itself (i.e. `Ty::Param`).
-    pub fn type_params(db: &dyn HirDatabase, def: impl Into<GenericDefId>) -> Substitution {
-        let params = generics(db.upcast(), def.into());
-        Substitution::type_params_for_generics(db, &params)
-    }
-    /// Return Substs that replace each parameter by a bound variable.
-    pub(crate) fn bound_vars(generic_params: &Generics, debruijn: DebruijnIndex) -> Substitution {
-        Substitution::from_iter(
-            &Interner,
-            generic_params
-                .iter()
-                .enumerate()
-                .map(|(idx, _)| TyKind::BoundVar(BoundVar::new(debruijn, idx)).intern(&Interner)),
        )
    }
-    pub fn build_for_def(db: &dyn HirDatabase, def: impl Into<GenericDefId>) -> SubstsBuilder {
-        let def = def.into();
-        let params = generics(db.upcast(), def);
-        let param_count = params.len();
-        Substitution::builder(param_count)
-    }
-    pub(crate) fn build_for_generics(generic_params: &Generics) -> SubstsBuilder {
-        Substitution::builder(generic_params.len())
-    }
-    fn builder(param_count: usize) -> SubstsBuilder {
-        SubstsBuilder { vec: Vec::with_capacity(param_count), param_count }
-    }
 }
 /// Return an index of a parameter in the generic type parameter list by it's id.
@@ -509,58 +117,6 @@ pub fn param_idx(db: &dyn HirDatabase, id: TypeParamId) -> Option<usize> {
    generics(db.upcast(), id.parent).param_idx(id)
 }
-#[derive(Debug, Clone)]
-pub struct SubstsBuilder {
-    vec: Vec<GenericArg>,
-    param_count: usize,
-}
-impl SubstsBuilder {
-    pub fn build(self) -> Substitution {
-        assert_eq!(self.vec.len(), self.param_count);
-        Substitution::from_iter(&Interner, self.vec)
-    }
-    pub fn push(mut self, ty: impl CastTo<GenericArg>) -> Self {
-        self.vec.push(ty.cast(&Interner));
-        self
-    }
-    fn remaining(&self) -> usize {
-        self.param_count - self.vec.len()
-    }
-    pub fn fill_with_bound_vars(self, debruijn: DebruijnIndex, starting_from: usize) -> Self {
-        self.fill(
-            (starting_from..)
-                .map(|idx| TyKind::BoundVar(BoundVar::new(debruijn, idx)).intern(&Interner)),
-        )
-    }
-    pub fn fill_with_unknown(self) -> Self {
-        self.fill(iter::repeat(TyKind::Unknown.intern(&Interner)))
-    }
-    pub fn fill(mut self, filler: impl Iterator<Item = impl CastTo<GenericArg>>) -> Self {
-        self.vec.extend(filler.take(self.remaining()).casted(&Interner));
-        assert_eq!(self.remaining(), 0);
-        self
-    }
-    pub fn use_parent_substs(mut self, parent_substs: &Substitution) -> Self {
-        assert!(self.vec.is_empty());
-        assert!(parent_substs.len(&Interner) <= self.param_count);
-        self.vec.extend(parent_substs.iter(&Interner).cloned());
-        self
-    }
-}
-#[derive(Copy, Clone, PartialEq, Eq, Debug, Hash)]
-pub struct Binders<T> {
-    pub num_binders: usize,
-    pub value: T,
-}
 impl<T> Binders<T> {
    pub fn new(num_binders: usize, value: T) -> Self {
        Self { num_binders, value }
@@ -608,27 +164,6 @@ impl<T: TypeWalk> Binders<T> {
    }
 }
-impl<T: TypeWalk> TypeWalk for Binders<T> {
-    fn walk(&self, f: &mut impl FnMut(&Ty)) {
-        self.value.walk(f);
-    }
-    fn walk_mut_binders(
-        &mut self,
-        f: &mut impl FnMut(&mut Ty, DebruijnIndex),
-        binders: DebruijnIndex,
-    ) {
-        self.value.walk_mut_binders(f, binders.shifted_in())
-    }
-}
-/// A trait with type parameters. This includes the `Self`, so this represents a concrete type implementing the trait.
-#[derive(Clone, PartialEq, Eq, Debug, Hash)]
-pub struct TraitRef {
-    pub trait_id: ChalkTraitId,
-    pub substitution: Substitution,
-}
 impl TraitRef {
    pub fn self_type_parameter(&self) -> &Ty {
        &self.substitution.at(&Interner, 0).assert_ty_ref(&Interner)
@@ -639,30 +174,6 @@ impl TraitRef {
    }
 }
-impl TypeWalk for TraitRef {
-    fn walk(&self, f: &mut impl FnMut(&Ty)) {
-        self.substitution.walk(f);
-    }
-    fn walk_mut_binders(
-        &mut self,
-        f: &mut impl FnMut(&mut Ty, DebruijnIndex),
-        binders: DebruijnIndex,
-    ) {
-        self.substitution.walk_mut_binders(f, binders);
-    }
-}
-/// Like `generics::WherePredicate`, but with resolved types: A condition on the
-/// parameters of a generic item.
-#[derive(Debug, Clone, PartialEq, Eq, Hash)]
-pub enum WhereClause {
-    /// The given trait needs to be implemented for its type parameters.
-    Implemented(TraitRef),
-    /// An associated type bindings like in `Iterator<Item = T>`.
-    AliasEq(AliasEq),
-}
 impl WhereClause {
    pub fn is_implemented(&self) -> bool {
        matches!(self, WhereClause::Implemented(_))
@@ -679,56 +190,6 @@ impl WhereClause {
    }
 }
-impl TypeWalk for WhereClause {
-    fn walk(&self, f: &mut impl FnMut(&Ty)) {
-        match self {
-            WhereClause::Implemented(trait_ref) => trait_ref.walk(f),
-            WhereClause::AliasEq(alias_eq) => alias_eq.walk(f),
-        }
-    }
-    fn walk_mut_binders(
-        &mut self,
-        f: &mut impl FnMut(&mut Ty, DebruijnIndex),
-        binders: DebruijnIndex,
-    ) {
-        match self {
-            WhereClause::Implemented(trait_ref) => trait_ref.walk_mut_binders(f, binders),
-            WhereClause::AliasEq(alias_eq) => alias_eq.walk_mut_binders(f, binders),
-        }
-    }
-}
-pub type QuantifiedWhereClause = Binders<WhereClause>;
-#[derive(Debug, Clone, PartialEq, Eq, Hash)]
-pub struct QuantifiedWhereClauses(Arc<[QuantifiedWhereClause]>);
-impl QuantifiedWhereClauses {
-    pub fn from_iter(
-        _interner: &Interner,
-        elements: impl IntoIterator<Item = QuantifiedWhereClause>,
-    ) -> Self {
-        QuantifiedWhereClauses(elements.into_iter().collect())
-    }
-    pub fn interned(&self) -> &Arc<[QuantifiedWhereClause]> {
-        &self.0
-    }
-}
-/// Basically a claim (currently not validated / checked) that the contained
-/// type / trait ref contains no inference variables; any inference variables it
-/// contained have been replaced by bound variables, and `kinds` tells us how
-/// many there are and whether they were normal or float/int variables. This is
-/// used to erase irrelevant differences between types before using them in
-/// queries.
-#[derive(Debug, Clone, PartialEq, Eq, Hash)]
-pub struct Canonical<T> {
-    pub value: T,
-    pub binders: CanonicalVarKinds,
-}
 impl<T> Canonical<T> {
    pub fn new(value: T, kinds: impl IntoIterator<Item = TyVariableKind>) -> Self {
        let kinds = kinds.into_iter().map(|tk| {
@@ -760,12 +221,12 @@ impl CallableSig {
    pub fn from_fn_ptr(fn_ptr: &FnPointer) -> CallableSig {
        CallableSig {
-            // FIXME: what to do about lifetime params?
+            // FIXME: what to do about lifetime params? -> return PolyFnSig
            params_and_return: fn_ptr
                .substs
                .clone()
                .shift_bound_vars_out(DebruijnIndex::ONE)
-                .interned(&Interner)
+                .interned()
                .iter()
                .map(|arg| arg.assert_ty_ref(&Interner).clone())
                .collect(),
@@ -773,16 +234,6 @@ impl CallableSig {
        }
    }
-    pub fn from_substs(substs: &Substitution) -> CallableSig {
-        CallableSig {
-            params_and_return: substs
-                .iter(&Interner)
-                .map(|arg| arg.assert_ty_ref(&Interner).clone())
-                .collect(),
-            is_varargs: false,
-        }
-    }
    pub fn params(&self) -> &[Ty] {
        &self.params_and_return[0..self.params_and_return.len() - 1]
    }
@@ -792,59 +243,7 @@ impl CallableSig {
    }
 }
-impl TypeWalk for CallableSig {
-    fn walk(&self, f: &mut impl FnMut(&Ty)) {
-        for t in self.params_and_return.iter() {
-            t.walk(f);
-        }
-    }
-    fn walk_mut_binders(
-        &mut self,
-        f: &mut impl FnMut(&mut Ty, DebruijnIndex),
-        binders: DebruijnIndex,
-    ) {
-        for t in make_mut_slice(&mut self.params_and_return) {
-            t.walk_mut_binders(f, binders);
-        }
-    }
-}
 impl Ty {
-    pub fn unit() -> Self {
-        TyKind::Tuple(0, Substitution::empty(&Interner)).intern(&Interner)
-    }
-    pub fn adt_ty(adt: hir_def::AdtId, substs: Substitution) -> Ty {
-        TyKind::Adt(AdtId(adt), substs).intern(&Interner)
-    }
-    pub fn fn_ptr(sig: CallableSig) -> Self {
-        TyKind::Function(FnPointer {
-            num_args: sig.params().len(),
-            sig: FnSig { abi: (), safety: Safety::Safe, variadic: sig.is_varargs },
-            substs: Substitution::from_iter(&Interner, sig.params_and_return.iter().cloned()),
-        })
-        .intern(&Interner)
-    }
-    pub fn builtin(builtin: BuiltinType) -> Self {
-        match builtin {
-            BuiltinType::Char => TyKind::Scalar(Scalar::Char).intern(&Interner),
-            BuiltinType::Bool => TyKind::Scalar(Scalar::Bool).intern(&Interner),
-            BuiltinType::Str => TyKind::Str.intern(&Interner),
-            BuiltinType::Int(t) => {
-                TyKind::Scalar(Scalar::Int(primitive::int_ty_from_builtin(t))).intern(&Interner)
-            }
-            BuiltinType::Uint(t) => {
-                TyKind::Scalar(Scalar::Uint(primitive::uint_ty_from_builtin(t))).intern(&Interner)
-            }
-            BuiltinType::Float(t) => {
-                TyKind::Scalar(Scalar::Float(primitive::float_ty_from_builtin(t))).intern(&Interner)
-            }
-        }
-    }
    pub fn as_reference(&self) -> Option<(&Ty, Mutability)> {
        match self.kind(&Interner) {
            TyKind::Ref(mutability, ty) => Some((ty, *mutability)),
@@ -1068,7 +467,7 @@ impl Ty {
                let param_data = &generic_params.types[id.local_id];
                match param_data.provenance {
                    hir_def::generics::TypeParamProvenance::ArgumentImplTrait => {
-                        let substs = Substitution::type_params(db, id.parent);
+                        let substs = TyBuilder::type_params_subst(db, id.parent);
                        let predicates = db
                            .generic_predicates(id.parent)
                            .into_iter()
@@ -1114,200 +513,6 @@ impl Ty {
    }
 }
-/// This allows walking structures that contain types to do something with those
-/// types, similar to Chalk's `Fold` trait.
-pub trait TypeWalk {
-    fn walk(&self, f: &mut impl FnMut(&Ty));
-    fn walk_mut(&mut self, f: &mut impl FnMut(&mut Ty)) {
-        self.walk_mut_binders(&mut |ty, _binders| f(ty), DebruijnIndex::INNERMOST);
-    }
-    /// Walk the type, counting entered binders.
-    ///
-    /// `TyKind::Bound` variables use DeBruijn indexing, which means that 0 refers
-    /// to the innermost binder, 1 to the next, etc.. So when we want to
-    /// substitute a certain bound variable, we can't just walk the whole type
-    /// and blindly replace each instance of a certain index; when we 'enter'
-    /// things that introduce new bound variables, we have to keep track of
-    /// that. Currently, the only thing that introduces bound variables on our
-    /// side are `TyKind::Dyn` and `TyKind::Opaque`, which each introduce a bound
-    /// variable for the self type.
-    fn walk_mut_binders(
-        &mut self,
-        f: &mut impl FnMut(&mut Ty, DebruijnIndex),
-        binders: DebruijnIndex,
-    );
-    fn fold_binders(
-        mut self,
-        f: &mut impl FnMut(Ty, DebruijnIndex) -> Ty,
-        binders: DebruijnIndex,
-    ) -> Self
-    where
-        Self: Sized,
-    {
-        self.walk_mut_binders(
-            &mut |ty_mut, binders| {
-                let ty = mem::replace(ty_mut, TyKind::Unknown.intern(&Interner));
-                *ty_mut = f(ty, binders);
-            },
-            binders,
-        );
-        self
-    }
-    fn fold(mut self, f: &mut impl FnMut(Ty) -> Ty) -> Self
-    where
-        Self: Sized,
-    {
-        self.walk_mut(&mut |ty_mut| {
-            let ty = mem::replace(ty_mut, TyKind::Unknown.intern(&Interner));
-            *ty_mut = f(ty);
-        });
-        self
-    }
-    /// Substitutes `TyKind::Bound` vars with the given substitution.
-    fn subst_bound_vars(self, substs: &Substitution) -> Self
-    where
-        Self: Sized,
-    {
-        self.subst_bound_vars_at_depth(substs, DebruijnIndex::INNERMOST)
-    }
-    /// Substitutes `TyKind::Bound` vars with the given substitution.
-    fn subst_bound_vars_at_depth(mut self, substs: &Substitution, depth: DebruijnIndex) -> Self
-    where
-        Self: Sized,
-    {
-        self.walk_mut_binders(
-            &mut |ty, binders| {
-                if let &mut TyKind::BoundVar(bound) = ty.interned_mut() {
-                    if bound.debruijn >= binders {
-                        *ty = substs.0[bound.index]
-                            .assert_ty_ref(&Interner)
-                            .clone()
-                            .shift_bound_vars(binders);
-                    }
-                }
-            },
-            depth,
-        );
-        self
-    }
-    /// Shifts up debruijn indices of `TyKind::Bound` vars by `n`.
-    fn shift_bound_vars(self, n: DebruijnIndex) -> Self
-    where
-        Self: Sized,
-    {
-        self.fold_binders(
-            &mut |ty, binders| match ty.kind(&Interner) {
-                TyKind::BoundVar(bound) if bound.debruijn >= binders => {
-                    TyKind::BoundVar(bound.shifted_in_from(n)).intern(&Interner)
-                }
-                _ => ty,
-            },
-            DebruijnIndex::INNERMOST,
-        )
-    }
-    /// Shifts debruijn indices of `TyKind::Bound` vars out (down) by `n`.
-    fn shift_bound_vars_out(self, n: DebruijnIndex) -> Self
-    where
-        Self: Sized + std::fmt::Debug,
-    {
-        self.fold_binders(
-            &mut |ty, binders| match ty.kind(&Interner) {
-                TyKind::BoundVar(bound) if bound.debruijn >= binders => {
-                    TyKind::BoundVar(bound.shifted_out_to(n).unwrap_or(bound.clone()))
-                        .intern(&Interner)
-                }
-                _ => ty,
-            },
-            DebruijnIndex::INNERMOST,
-        )
-    }
-}
-impl TypeWalk for Ty {
-    fn walk(&self, f: &mut impl FnMut(&Ty)) {
-        match self.kind(&Interner) {
-            TyKind::Alias(AliasTy::Projection(p_ty)) => {
-                for t in p_ty.substitution.iter(&Interner) {
-                    t.walk(f);
-                }
-            }
-            TyKind::Alias(AliasTy::Opaque(o_ty)) => {
-                for t in o_ty.substitution.iter(&Interner) {
-                    t.walk(f);
-                }
-            }
-            TyKind::Dyn(dyn_ty) => {
-                for p in dyn_ty.bounds.value.interned().iter() {
-                    p.walk(f);
-                }
-            }
-            TyKind::Slice(ty) | TyKind::Array(ty) | TyKind::Ref(_, ty) | TyKind::Raw(_, ty) => {
-                ty.walk(f);
-            }
-            _ => {
-                if let Some(substs) = self.substs() {
-                    for t in substs.iter(&Interner) {
-                        t.walk(f);
-                    }
-                }
-            }
-        }
-        f(self);
-    }
-    fn walk_mut_binders(
-        &mut self,
-        f: &mut impl FnMut(&mut Ty, DebruijnIndex),
-        binders: DebruijnIndex,
-    ) {
-        match self.interned_mut() {
-            TyKind::Alias(AliasTy::Projection(p_ty)) => {
-                p_ty.substitution.walk_mut_binders(f, binders);
-            }
-            TyKind::Dyn(dyn_ty) => {
-                for p in make_mut_slice(&mut dyn_ty.bounds.value.0) {
-                    p.walk_mut_binders(f, binders.shifted_in());
-                }
-            }
-            TyKind::Alias(AliasTy::Opaque(o_ty)) => {
-                o_ty.substitution.walk_mut_binders(f, binders);
-            }
-            TyKind::Slice(ty) | TyKind::Array(ty) | TyKind::Ref(_, ty) | TyKind::Raw(_, ty) => {
-                ty.walk_mut_binders(f, binders);
-            }
-            _ => {
-                if let Some(substs) = self.substs_mut() {
-                    substs.walk_mut_binders(f, binders);
-                }
-            }
-        }
-        f(self, binders);
-    }
-}
-impl<T: TypeWalk> TypeWalk for Vec<T> {
-    fn walk(&self, f: &mut impl FnMut(&Ty)) {
-        for t in self {
-            t.walk(f);
-        }
-    }
-    fn walk_mut_binders(
-        &mut self,
-        f: &mut impl FnMut(&mut Ty, DebruijnIndex),
-        binders: DebruijnIndex,
-    ) {
-        for t in self {
-            t.walk_mut_binders(f, binders);
-        }
-    }
-}
 #[derive(Copy, Clone, PartialEq, Eq, Debug, Hash)]
 pub enum ImplTraitId {
    ReturnTypeImplTrait(hir_def::FunctionId, u16),
diff --git a/crates/hir_ty/src/lower.rs b/crates/hir_ty/src/lower.rs
index f595683e5..214655807 100644
--- a/crates/hir_ty/src/lower.rs
+++ b/crates/hir_ty/src/lower.rs
@@ -36,7 +36,7 @@ use crate::{
    AliasEq, AliasTy, Binders, BoundVar, CallableSig, DebruijnIndex, DynTy, FnPointer, FnSig,
    ImplTraitId, OpaqueTy, PolyFnSig, ProjectionTy, QuantifiedWhereClause, QuantifiedWhereClauses,
    ReturnTypeImplTrait, ReturnTypeImplTraits, Substitution, TraitEnvironment, TraitRef, Ty,
-    TyKind, TypeWalk, WhereClause,
+    TyBuilder, TyKind, TypeWalk, WhereClause,
 };
 #[derive(Debug)]
@@ -234,7 +234,7 @@ impl<'a> TyLoweringContext<'a> {
                        let impl_trait_id = ImplTraitId::ReturnTypeImplTrait(func, idx);
                        let opaque_ty_id = self.db.intern_impl_trait_id(impl_trait_id).into();
                        let generics = generics(self.db.upcast(), func.into());
-                        let parameters = Substitution::bound_vars(&generics, self.in_binders);
+                        let parameters = generics.bound_vars_subst(self.in_binders);
                        TyKind::Alias(AliasTy::Opaque(OpaqueTy {
                            opaque_ty_id,
                            substitution: parameters,
@@ -411,24 +411,16 @@ impl<'a> TyLoweringContext<'a> {
            TypeNs::SelfType(impl_id) => {
                let generics = generics(self.db.upcast(), impl_id.into());
                let substs = match self.type_param_mode {
-                    TypeParamLoweringMode::Placeholder => {
+                    TypeParamLoweringMode::Placeholder => generics.type_params_subst(self.db),
-                        Substitution::type_params_for_generics(self.db, &generics)
+                    TypeParamLoweringMode::Variable => generics.bound_vars_subst(self.in_binders),
-                    }
-                    TypeParamLoweringMode::Variable => {
-                        Substitution::bound_vars(&generics, self.in_binders)
-                    }
                };
                self.db.impl_self_ty(impl_id).subst(&substs)
            }
            TypeNs::AdtSelfType(adt) => {
                let generics = generics(self.db.upcast(), adt.into());
                let substs = match self.type_param_mode {
-                    TypeParamLoweringMode::Placeholder => {
+                    TypeParamLoweringMode::Placeholder => generics.type_params_subst(self.db),
-                        Substitution::type_params_for_generics(self.db, &generics)
+                    TypeParamLoweringMode::Variable => generics.bound_vars_subst(self.in_binders),
-                    }
-                    TypeParamLoweringMode::Variable => {
-                        Substitution::bound_vars(&generics, self.in_binders)
-                    }
                };
                self.db.ty(adt.into()).subst(&substs)
            }
@@ -478,12 +470,13 @@ impl<'a> TyLoweringContext<'a> {
                            TypeParamLoweringMode::Placeholder => {
                                // if we're lowering to placeholders, we have to put
                                // them in now
-                                let s = Substitution::type_params(
+                                let generics = generics(
-                                    self.db,
+                                    self.db.upcast(),
                                    self.resolver.generic_def().expect(
                                        "there should be generics if there's a generic param",
                                    ),
                                );
+                                let s = generics.type_params_subst(self.db);
                                t.substitution.clone().subst_bound_vars(&s)
                            }
                            TypeParamLoweringMode::Variable => t.substitution.clone(),
@@ -860,10 +853,9 @@ pub fn associated_type_shorthand_candidates<R>(
                if generics.params.types[param_id.local_id].provenance
                    == TypeParamProvenance::TraitSelf
                {
-                    let trait_ref = TraitRef {
+                    let trait_ref = TyBuilder::trait_ref(db, trait_id)
-                        trait_id: to_chalk_trait_id(trait_id),
+                        .fill_with_bound_vars(DebruijnIndex::INNERMOST, 0)
-                        substitution: Substitution::bound_vars(&generics, DebruijnIndex::INNERMOST),
+                        .build();
-                    };
                    return search(trait_ref);
                }
            }
@@ -972,7 +964,7 @@ pub(crate) fn trait_environment_query(
        // function default implementations (and hypothetical code
        // inside consts or type aliases)
        cov_mark::hit!(trait_self_implements_self);
-        let substs = Substitution::type_params(db, trait_id);
+        let substs = TyBuilder::type_params_subst(db, trait_id);
        let trait_ref = TraitRef { trait_id: to_chalk_trait_id(trait_id), substitution: substs };
        let pred = WhereClause::Implemented(trait_ref);
        let program_clause: chalk_ir::ProgramClause<Interner> = pred.to_chalk(db).cast(&Interner);
@@ -1054,14 +1046,14 @@ fn fn_sig_for_fn(db: &dyn HirDatabase, def: FunctionId) -> PolyFnSig {
    let ret = (&ctx_ret).lower_ty(&data.ret_type);
    let generics = generics(db.upcast(), def.into());
    let num_binders = generics.len();
-    Binders::new(num_binders, CallableSig::from_params_and_return(params, ret, data.is_varargs))
+    Binders::new(num_binders, CallableSig::from_params_and_return(params, ret, data.is_varargs()))
 }
 /// Build the declared type of a function. This should not need to look at the
 /// function body.
 fn type_for_fn(db: &dyn HirDatabase, def: FunctionId) -> Binders<Ty> {
    let generics = generics(db.upcast(), def.into());
-    let substs = Substitution::bound_vars(&generics, DebruijnIndex::INNERMOST);
+    let substs = generics.bound_vars_subst(DebruijnIndex::INNERMOST);
    Binders::new(
        substs.len(&Interner),
        TyKind::FnDef(CallableDefId::FunctionId(def).to_chalk(db), substs).intern(&Interner),
@@ -1106,7 +1098,7 @@ fn type_for_struct_constructor(db: &dyn HirDatabase, def: StructId) -> Binders<T
        return type_for_adt(db, def.into());
    }
    let generics = generics(db.upcast(), def.into());
-    let substs = Substitution::bound_vars(&generics, DebruijnIndex::INNERMOST);
+    let substs = generics.bound_vars_subst(DebruijnIndex::INNERMOST);
    Binders::new(
        substs.len(&Interner),
        TyKind::FnDef(CallableDefId::StructId(def).to_chalk(db), substs).intern(&Interner),
@@ -1133,7 +1125,7 @@ fn type_for_enum_variant_constructor(db: &dyn HirDatabase, def: EnumVariantId) -
        return type_for_adt(db, def.parent.into());
    }
    let generics = generics(db.upcast(), def.parent.into());
-    let substs = Substitution::bound_vars(&generics, DebruijnIndex::INNERMOST);
+    let substs = generics.bound_vars_subst(DebruijnIndex::INNERMOST);
    Binders::new(
        substs.len(&Interner),
        TyKind::FnDef(CallableDefId::EnumVariantId(def).to_chalk(db), substs).intern(&Interner),
@@ -1141,9 +1133,10 @@ fn type_for_enum_variant_constructor(db: &dyn HirDatabase, def: EnumVariantId) -
 }
 fn type_for_adt(db: &dyn HirDatabase, adt: AdtId) -> Binders<Ty> {
-    let generics = generics(db.upcast(), adt.into());
+    let b = TyBuilder::adt(db, adt);
-    let substs = Substitution::bound_vars(&generics, DebruijnIndex::INNERMOST);
+    let num_binders = b.remaining();
-    Binders::new(substs.len(&Interner), Ty::adt_ty(adt, substs))
+    let ty = b.fill_with_bound_vars(DebruijnIndex::INNERMOST, 0).build();
+    Binders::new(num_binders, ty)
 }
 fn type_for_type_alias(db: &dyn HirDatabase, t: TypeAliasId) -> Binders<Ty> {
@@ -1215,7 +1208,7 @@ impl_from!(FunctionId, StructId, UnionId, EnumVariantId, ConstId, StaticId for V
 /// namespace.
 pub(crate) fn ty_query(db: &dyn HirDatabase, def: TyDefId) -> Binders<Ty> {
    match def {
-        TyDefId::BuiltinType(it) => Binders::new(0, Ty::builtin(it)),
+        TyDefId::BuiltinType(it) => Binders::new(0, TyBuilder::builtin(it)),
        TyDefId::AdtId(it) => type_for_adt(db, it),
        TyDefId::TypeAliasId(it) => type_for_type_alias(db, it),
    }
diff --git a/crates/hir_ty/src/method_resolution.rs b/crates/hir_ty/src/method_resolution.rs
index 338851fa8..0e4a620b6 100644
--- a/crates/hir_ty/src/method_resolution.rs
+++ b/crates/hir_ty/src/method_resolution.rs
@@ -19,10 +19,9 @@ use crate::{
    db::HirDatabase,
    from_foreign_def_id,
    primitive::{self, FloatTy, IntTy, UintTy},
-    to_chalk_trait_id,
    utils::all_super_traits,
    AdtId, Canonical, CanonicalVarKinds, DebruijnIndex, FnPointer, FnSig, ForeignDefId,
-    InEnvironment, Interner, Scalar, Substitution, TraitEnvironment, TraitRef, Ty, TyKind,
+    InEnvironment, Interner, Scalar, Substitution, TraitEnvironment, Ty, TyBuilder, TyKind,
    TypeWalk,
 };
@@ -675,7 +674,7 @@ fn is_valid_candidate(
                }
            }
            if let Some(receiver_ty) = receiver_ty {
-                if !data.has_self_param {
+                if !data.has_self_param() {
                    return false;
                }
                let transformed_receiver_ty = match transform_receiver_ty(db, m, self_ty) {
@@ -710,7 +709,7 @@ pub(crate) fn inherent_impl_substs(
 ) -> Option<Substitution> {
    // we create a var for each type parameter of the impl; we need to keep in
    // mind here that `self_ty` might have vars of its own
-    let vars = Substitution::build_for_def(db, impl_id)
+    let vars = TyBuilder::subst_for_def(db, impl_id)
        .fill_with_bound_vars(DebruijnIndex::INNERMOST, self_ty.binders.len(&Interner))
        .build();
    let self_ty_with_vars = db.impl_self_ty(impl_id).subst(&vars);
@@ -761,13 +760,13 @@ fn transform_receiver_ty(
    self_ty: &Canonical<Ty>,
 ) -> Option<Ty> {
    let substs = match function_id.lookup(db.upcast()).container {
-        AssocContainerId::TraitId(_) => Substitution::build_for_def(db, function_id)
+        AssocContainerId::TraitId(_) => TyBuilder::subst_for_def(db, function_id)
            .push(self_ty.value.clone())
            .fill_with_unknown()
            .build(),
        AssocContainerId::ImplId(impl_id) => {
            let impl_substs = inherent_impl_substs(db, impl_id, &self_ty)?;
-            Substitution::build_for_def(db, function_id)
+            TyBuilder::subst_for_def(db, function_id)
                .use_parent_substs(&impl_substs)
                .fill_with_unknown()
                .build()
@@ -801,7 +800,7 @@ pub fn implements_trait_unique(
    let goal = generic_implements_goal(db, env, trait_, ty.clone());
    let solution = db.trait_solve(krate, goal);
-    matches!(solution, Some(crate::traits::Solution::Unique(_)))
+    matches!(solution, Some(crate::Solution::Unique(_)))
 }
 /// This creates Substs for a trait with the given Self type and type variables
@@ -813,7 +812,7 @@ fn generic_implements_goal(
    self_ty: Canonical<Ty>,
 ) -> Canonical<InEnvironment<super::DomainGoal>> {
    let mut kinds = self_ty.binders.interned().to_vec();
-    let substs = super::Substitution::build_for_def(db, trait_)
+    let trait_ref = TyBuilder::trait_ref(db, trait_)
        .push(self_ty.value)
        .fill_with_bound_vars(DebruijnIndex::INNERMOST, kinds.len())
        .build();
@@ -822,9 +821,8 @@ fn generic_implements_goal(
            chalk_ir::VariableKind::Ty(chalk_ir::TyVariableKind::General),
            UniverseIndex::ROOT,
        ))
-        .take(substs.len(&Interner) - 1),
+        .take(trait_ref.substitution.len(&Interner) - 1),
    );
-    let trait_ref = TraitRef { trait_id: to_chalk_trait_id(trait_), substitution: substs };
    let obligation = trait_ref.cast(&Interner);
    Canonical {
        binders: CanonicalVarKinds::from_iter(&Interner, kinds),
diff --git a/crates/hir_ty/src/op.rs b/crates/hir_ty/src/op.rs
index 8533e1ed8..90dd31a35 100644
--- a/crates/hir_ty/src/op.rs
+++ b/crates/hir_ty/src/op.rs
@@ -2,12 +2,12 @@
 use chalk_ir::TyVariableKind;
 use hir_def::expr::{ArithOp, BinaryOp, CmpOp};
-use crate::{Interner, Scalar, Ty, TyKind};
+use crate::{Interner, Scalar, Ty, TyBuilder, TyKind};
 pub(super) fn binary_op_return_ty(op: BinaryOp, lhs_ty: Ty, rhs_ty: Ty) -> Ty {
    match op {
        BinaryOp::LogicOp(_) | BinaryOp::CmpOp(_) => TyKind::Scalar(Scalar::Bool).intern(&Interner),
-        BinaryOp::Assignment { .. } => Ty::unit(),
+        BinaryOp::Assignment { .. } => TyBuilder::unit(),
        BinaryOp::ArithOp(ArithOp::Shl) | BinaryOp::ArithOp(ArithOp::Shr) => {
            match lhs_ty.kind(&Interner) {
                TyKind::Scalar(Scalar::Int(_))
diff --git a/crates/hir_ty/src/tests.rs b/crates/hir_ty/src/tests.rs
index ad283c1e0..ccfb88c52 100644
--- a/crates/hir_ty/src/tests.rs
+++ b/crates/hir_ty/src/tests.rs
@@ -288,7 +288,7 @@ fn visit_module(
    }
    fn visit_body(db: &TestDB, body: &Body, cb: &mut dyn FnMut(DefWithBodyId)) {
-        for def_map in body.block_scopes.iter().filter_map(|block| db.block_def_map(*block)) {
+        for (_, def_map) in body.blocks(db) {
            for (mod_id, _) in def_map.modules() {
                visit_module(db, &def_map, mod_id, cb);
            }
diff --git a/crates/hir_ty/src/traits.rs b/crates/hir_ty/src/traits.rs
index e5e8cff33..66d600bfc 100644
--- a/crates/hir_ty/src/traits.rs
+++ b/crates/hir_ty/src/traits.rs
@@ -8,8 +8,8 @@ use hir_def::{lang_item::LangItemTarget, TraitId};
 use stdx::panic_context;
 use crate::{
-    db::HirDatabase, AliasTy, Canonical, DebruijnIndex, HirDisplay, Substitution, Ty, TyKind,
+    db::HirDatabase, AliasEq, AliasTy, Canonical, DomainGoal, Guidance, HirDisplay, InEnvironment,
-    TypeWalk, WhereClause,
+    Solution, SolutionVariables, Ty, TyKind, WhereClause,
 };
 use self::chalk::{from_chalk, Interner, ToChalk};
@@ -70,55 +70,6 @@ impl Default for TraitEnvironment {
    }
 }
-/// Something (usually a goal), along with an environment.
-#[derive(Clone, Debug, PartialEq, Eq, Hash)]
-pub struct InEnvironment<T> {
-    pub environment: chalk_ir::Environment<Interner>,
-    pub goal: T,
-}
-impl<T> InEnvironment<T> {
-    pub fn new(environment: chalk_ir::Environment<Interner>, value: T) -> InEnvironment<T> {
-        InEnvironment { environment, goal: value }
-    }
-}
-/// Something that needs to be proven (by Chalk) during type checking, e.g. that
-/// a certain type implements a certain trait. Proving the Obligation might
-/// result in additional information about inference variables.
-#[derive(Clone, Debug, PartialEq, Eq, Hash)]
-pub enum DomainGoal {
-    Holds(WhereClause),
-}
-#[derive(Clone, Debug, PartialEq, Eq, Hash)]
-pub struct AliasEq {
-    pub alias: AliasTy,
-    pub ty: Ty,
-}
-impl TypeWalk for AliasEq {
-    fn walk(&self, f: &mut impl FnMut(&Ty)) {
-        self.ty.walk(f);
-        match &self.alias {
-            AliasTy::Projection(projection_ty) => projection_ty.walk(f),
-            AliasTy::Opaque(opaque) => opaque.walk(f),
-        }
-    }
-    fn walk_mut_binders(
-        &mut self,
-        f: &mut impl FnMut(&mut Ty, DebruijnIndex),
-        binders: DebruijnIndex,
-    ) {
-        self.ty.walk_mut_binders(f, binders);
-        match &mut self.alias {
-            AliasTy::Projection(projection_ty) => projection_ty.walk_mut_binders(f, binders),
-            AliasTy::Opaque(opaque) => opaque.walk_mut_binders(f, binders),
-        }
-    }
-}
 /// Solve a trait goal using Chalk.
 pub(crate) fn trait_solve_query(
    db: &dyn HirDatabase,
@@ -246,41 +197,6 @@ fn solution_from_chalk(
    }
 }
-#[derive(Clone, Debug, PartialEq, Eq)]
-pub struct SolutionVariables(pub Canonical<Substitution>);
-#[derive(Clone, Debug, PartialEq, Eq)]
-/// A (possible) solution for a proposed goal.
-pub enum Solution {
-    /// The goal indeed holds, and there is a unique value for all existential
-    /// variables.
-    Unique(SolutionVariables),
-    /// The goal may be provable in multiple ways, but regardless we may have some guidance
-    /// for type inference. In this case, we don't return any lifetime
-    /// constraints, since we have not "committed" to any particular solution
-    /// yet.
-    Ambig(Guidance),
-}
-#[derive(Clone, Debug, PartialEq, Eq)]
-/// When a goal holds ambiguously (e.g., because there are multiple possible
-/// solutions), we issue a set of *guidance* back to type inference.
-pub enum Guidance {
-    /// The existential variables *must* have the given values if the goal is
-    /// ever to hold, but that alone isn't enough to guarantee the goal will
-    /// actually hold.
-    Definite(SolutionVariables),
-    /// There are multiple plausible values for the existentials, but the ones
-    /// here are suggested as the preferred choice heuristically. These should
-    /// be used for inference fallback only.
-    Suggested(SolutionVariables),
-    /// There's no useful information to feed back to type inference
-    Unknown,
-}
 #[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
 pub enum FnTrait {
    FnOnce,
diff --git a/crates/hir_ty/src/traits/chalk.rs b/crates/hir_ty/src/traits/chalk.rs
index fbac51b05..541e6082f 100644
--- a/crates/hir_ty/src/traits/chalk.rs
+++ b/crates/hir_ty/src/traits/chalk.rs
@@ -22,7 +22,7 @@ use crate::{
    to_assoc_type_id, to_chalk_trait_id,
    utils::generics,
    AliasEq, AliasTy, BoundVar, CallableDefId, DebruijnIndex, FnDefId, ProjectionTy, Substitution,
-    TraitRef, Ty, TyKind, WhereClause,
+    TraitRef, Ty, TyBuilder, TyKind, WhereClause,
 };
 use mapping::{
    convert_where_clauses, generic_predicate_to_inline_bound, make_binders, TypeAliasAsValue,
@@ -300,7 +300,7 @@ impl<'a> chalk_solve::RustIrDatabase<Interner> for ChalkContext<'a> {
        _closure_id: chalk_ir::ClosureId<Interner>,
        _substs: &chalk_ir::Substitution<Interner>,
    ) -> chalk_ir::Binders<chalk_ir::Ty<Interner>> {
-        let ty = Ty::unit().to_chalk(self.db);
+        let ty = TyBuilder::unit().to_chalk(self.db);
        make_binders(ty, 0)
    }
    fn closure_fn_substitution(
@@ -387,7 +387,7 @@ pub(crate) fn associated_ty_data_query(
    // Lower bounds -- we could/should maybe move this to a separate query in `lower`
    let type_alias_data = db.type_alias_data(type_alias);
    let generic_params = generics(db.upcast(), type_alias.into());
-    let bound_vars = Substitution::bound_vars(&generic_params, DebruijnIndex::INNERMOST);
+    let bound_vars = generic_params.bound_vars_subst(DebruijnIndex::INNERMOST);
    let resolver = hir_def::resolver::HasResolver::resolver(type_alias, db.upcast());
    let ctx = crate::TyLoweringContext::new(db, &resolver)
        .with_type_param_mode(crate::lower::TypeParamLoweringMode::Variable);
@@ -421,7 +421,7 @@ pub(crate) fn trait_datum_query(
    let trait_data = db.trait_data(trait_);
    debug!("trait {:?} = {:?}", trait_id, trait_data.name);
    let generic_params = generics(db.upcast(), trait_.into());
-    let bound_vars = Substitution::bound_vars(&generic_params, DebruijnIndex::INNERMOST);
+    let bound_vars = generic_params.bound_vars_subst(DebruijnIndex::INNERMOST);
    let flags = rust_ir::TraitFlags {
        auto: trait_data.is_auto,
        upstream: trait_.lookup(db.upcast()).container.krate() != krate,
@@ -490,7 +490,7 @@ pub(crate) fn struct_datum_query(
    let upstream = adt_id.module(db.upcast()).krate() != krate;
    let where_clauses = {
        let generic_params = generics(db.upcast(), adt_id.into());
-        let bound_vars = Substitution::bound_vars(&generic_params, DebruijnIndex::INNERMOST);
+        let bound_vars = generic_params.bound_vars_subst(DebruijnIndex::INNERMOST);
        convert_where_clauses(db, adt_id.into(), &bound_vars)
    };
    let flags = rust_ir::AdtFlags {
@@ -539,7 +539,7 @@ fn impl_def_datum(
    let impl_data = db.impl_data(impl_id);
    let generic_params = generics(db.upcast(), impl_id.into());
-    let bound_vars = Substitution::bound_vars(&generic_params, DebruijnIndex::INNERMOST);
+    let bound_vars = generic_params.bound_vars_subst(DebruijnIndex::INNERMOST);
    let trait_ = trait_ref.hir_trait_id();
    let impl_type = if impl_id.lookup(db.upcast()).container.krate() == krate {
        rust_ir::ImplType::Local
@@ -629,7 +629,7 @@ pub(crate) fn fn_def_datum_query(
    let callable_def: CallableDefId = from_chalk(db, fn_def_id);
    let generic_params = generics(db.upcast(), callable_def.into());
    let sig = db.callable_item_signature(callable_def);
-    let bound_vars = Substitution::bound_vars(&generic_params, DebruijnIndex::INNERMOST);
+    let bound_vars = generic_params.bound_vars_subst(DebruijnIndex::INNERMOST);
    let where_clauses = convert_where_clauses(db, callable_def.into(), &bound_vars);
    let bound = rust_ir::FnDefDatumBound {
        // Note: Chalk doesn't actually use this information yet as far as I am aware, but we provide it anyway
diff --git a/crates/hir_ty/src/traits/chalk/mapping.rs b/crates/hir_ty/src/traits/chalk/mapping.rs
index 452b357e8..5e4f97a46 100644
--- a/crates/hir_ty/src/traits/chalk/mapping.rs
+++ b/crates/hir_ty/src/traits/chalk/mapping.rs
@@ -10,11 +10,9 @@ use base_db::salsa::InternKey;
 use hir_def::{GenericDefId, TypeAliasId};
 use crate::{
-    db::HirDatabase,
+    db::HirDatabase, primitive::UintTy, AliasTy, CallableDefId, Canonical, DomainGoal, FnPointer,
-    primitive::UintTy,
+    GenericArg, InEnvironment, OpaqueTy, ProjectionTy, QuantifiedWhereClause, Scalar, Substitution,
-    traits::{Canonical, DomainGoal},
+    TraitRef, Ty, TypeWalk, WhereClause,
-    AliasTy, CallableDefId, FnPointer, GenericArg, InEnvironment, OpaqueTy, ProjectionTy,
-    QuantifiedWhereClause, Scalar, Substitution, TraitRef, Ty, TypeWalk, WhereClause,
 };
 use super::interner::*;
@@ -220,8 +218,8 @@ impl ToChalk for GenericArg {
    type Chalk = chalk_ir::GenericArg<Interner>;
    fn to_chalk(self, db: &dyn HirDatabase) -> Self::Chalk {
-        match self.interned {
+        match self.interned() {
-            crate::GenericArgData::Ty(ty) => ty.to_chalk(db).cast(&Interner),
+            crate::GenericArgData::Ty(ty) => ty.clone().to_chalk(db).cast(&Interner),
        }
    }
@@ -249,7 +247,7 @@ impl ToChalk for Substitution {
        parameters: chalk_ir::Substitution<Interner>,
    ) -> Substitution {
        let tys = parameters.iter(&Interner).map(|p| from_chalk(db, p.clone())).collect();
-        Substitution(tys)
+        Substitution::intern(tys)
    }
 }
@@ -546,7 +544,7 @@ pub(super) fn generic_predicate_to_inline_bound(
                // have the expected self type
                return None;
            }
-            let args_no_self = trait_ref.substitution.interned(&Interner)[1..]
+            let args_no_self = trait_ref.substitution.interned()[1..]
                .iter()
                .map(|ty| ty.clone().to_chalk(db).cast(&Interner))
                .collect();
@@ -558,7 +556,7 @@ pub(super) fn generic_predicate_to_inline_bound(
                return None;
            }
            let trait_ = projection_ty.trait_(db);
-            let args_no_self = projection_ty.substitution.interned(&Interner)[1..]
+            let args_no_self = projection_ty.substitution.interned()[1..]
                .iter()
                .map(|ty| ty.clone().to_chalk(db).cast(&Interner))
                .collect();
diff --git a/crates/hir_ty/src/types.rs b/crates/hir_ty/src/types.rs
new file mode 100644
index 000000000..53662fcdc
--- /dev/null
+++ b/crates/hir_ty/src/types.rs
@@ -0,0 +1,416 @@
+//! This is the home of `Ty` etc. until they get replaced by their chalk_ir
+//! equivalents.
+use std::sync::Arc;
+use chalk_ir::{
+    cast::{CastTo, Caster},
+    BoundVar, Mutability, Scalar, TyVariableKind,
+};
+use hir_def::LifetimeParamId;
+use smallvec::SmallVec;
+use crate::{
+    AssocTypeId, CanonicalVarKinds, ChalkTraitId, ClosureId, FnDefId, FnSig, ForeignDefId,
+    InferenceVar, Interner, OpaqueTyId, PlaceholderIndex,
+};
+#[derive(Clone, PartialEq, Eq, Debug, Hash)]
+pub enum Lifetime {
+    Parameter(LifetimeParamId),
+    Static,
+}
+#[derive(Clone, PartialEq, Eq, Debug, Hash)]
+pub struct OpaqueTy {
+    pub opaque_ty_id: OpaqueTyId,
+    pub substitution: Substitution,
+}
+/// A "projection" type corresponds to an (unnormalized)
+/// projection like `<P0 as Trait<P1..Pn>>::Foo`. Note that the
+/// trait and all its parameters are fully known.
+#[derive(Clone, PartialEq, Eq, Debug, Hash)]
+pub struct ProjectionTy {
+    pub associated_ty_id: AssocTypeId,
+    pub substitution: Substitution,
+}
+#[derive(Clone, PartialEq, Eq, Debug, Hash)]
+pub struct DynTy {
+    /// The unknown self type.
+    pub bounds: Binders<QuantifiedWhereClauses>,
+}
+#[derive(Clone, PartialEq, Eq, Debug, Hash)]
+pub struct FnPointer {
+    pub num_args: usize,
+    pub sig: FnSig,
+    pub substs: Substitution,
+}
+#[derive(Clone, PartialEq, Eq, Debug, Hash)]
+pub enum AliasTy {
+    /// A "projection" type corresponds to an (unnormalized)
+    /// projection like `<P0 as Trait<P1..Pn>>::Foo`. Note that the
+    /// trait and all its parameters are fully known.
+    Projection(ProjectionTy),
+    /// An opaque type (`impl Trait`).
+    ///
+    /// This is currently only used for return type impl trait; each instance of
+    /// `impl Trait` in a return type gets its own ID.
+    Opaque(OpaqueTy),
+}
+/// A type.
+///
+/// See also the `TyKind` enum in rustc (librustc/ty/sty.rs), which represents
+/// the same thing (but in a different way).
+///
+/// This should be cheap to clone.
+#[derive(Clone, PartialEq, Eq, Debug, Hash)]
+pub enum TyKind {
+    /// Structures, enumerations and unions.
+    Adt(chalk_ir::AdtId<Interner>, Substitution),
+    /// Represents an associated item like `Iterator::Item`.  This is used
+    /// when we have tried to normalize a projection like `T::Item` but
+    /// couldn't find a better representation.  In that case, we generate
+    /// an **application type** like `(Iterator::Item)<T>`.
+    AssociatedType(AssocTypeId, Substitution),
+    /// a scalar type like `bool` or `u32`
+    Scalar(Scalar),
+    /// A tuple type.  For example, `(i32, bool)`.
+    Tuple(usize, Substitution),
+    /// An array with the given length. Written as `[T; n]`.
+    Array(Ty),
+    /// The pointee of an array slice.  Written as `[T]`.
+    Slice(Ty),
+    /// A raw pointer. Written as `*mut T` or `*const T`
+    Raw(Mutability, Ty),
+    /// A reference; a pointer with an associated lifetime. Written as
+    /// `&'a mut T` or `&'a T`.
+    Ref(Mutability, Ty),
+    /// This represents a placeholder for an opaque type in situations where we
+    /// don't know the hidden type (i.e. currently almost always). This is
+    /// analogous to the `AssociatedType` type constructor.
+    /// It is also used as the type of async block, with one type parameter
+    /// representing the Future::Output type.
+    OpaqueType(OpaqueTyId, Substitution),
+    /// The anonymous type of a function declaration/definition. Each
+    /// function has a unique type, which is output (for a function
+    /// named `foo` returning an `i32`) as `fn() -> i32 {foo}`.
+    ///
+    /// This includes tuple struct / enum variant constructors as well.
+    ///
+    /// For example the type of `bar` here:
+    ///
+    /// ```
+    /// fn foo() -> i32 { 1 }
+    /// let bar = foo; // bar: fn() -> i32 {foo}
+    /// ```
+    FnDef(FnDefId, Substitution),
+    /// The pointee of a string slice. Written as `str`.
+    Str,
+    /// The never type `!`.
+    Never,
+    /// The type of a specific closure.
+    ///
+    /// The closure signature is stored in a `FnPtr` type in the first type
+    /// parameter.
+    Closure(ClosureId, Substitution),
+    /// Represents a foreign type declared in external blocks.
+    ForeignType(ForeignDefId),
+    /// A pointer to a function.  Written as `fn() -> i32`.
+    ///
+    /// For example the type of `bar` here:
+    ///
+    /// ```
+    /// fn foo() -> i32 { 1 }
+    /// let bar: fn() -> i32 = foo;
+    /// ```
+    Function(FnPointer),
+    /// An "alias" type represents some form of type alias, such as:
+    /// - An associated type projection like `<T as Iterator>::Item`
+    /// - `impl Trait` types
+    /// - Named type aliases like `type Foo<X> = Vec<X>`
+    Alias(AliasTy),
+    /// A placeholder for a type parameter; for example, `T` in `fn f<T>(x: T)
+    /// {}` when we're type-checking the body of that function. In this
+    /// situation, we know this stands for *some* type, but don't know the exact
+    /// type.
+    Placeholder(PlaceholderIndex),
+    /// A bound type variable. This is used in various places: when representing
+    /// some polymorphic type like the type of function `fn f<T>`, the type
+    /// parameters get turned into variables; during trait resolution, inference
+    /// variables get turned into bound variables and back; and in `Dyn` the
+    /// `Self` type is represented with a bound variable as well.
+    BoundVar(BoundVar),
+    /// A type variable used during type checking.
+    InferenceVar(InferenceVar, TyVariableKind),
+    /// A trait object (`dyn Trait` or bare `Trait` in pre-2018 Rust).
+    ///
+    /// The predicates are quantified over the `Self` type, i.e. `Ty::Bound(0)`
+    /// represents the `Self` type inside the bounds. This is currently
+    /// implicit; Chalk has the `Binders` struct to make it explicit, but it
+    /// didn't seem worth the overhead yet.
+    Dyn(DynTy),
+    /// A placeholder for a type which could not be computed; this is propagated
+    /// to avoid useless error messages. Doubles as a placeholder where type
+    /// variables are inserted before type checking, since we want to try to
+    /// infer a better type here anyway -- for the IDE use case, we want to try
+    /// to infer as much as possible even in the presence of type errors.
+    Unknown,
+}
+#[derive(Clone, PartialEq, Eq, Debug, Hash)]
+pub struct Ty(Arc<TyKind>);
+impl TyKind {
+    pub fn intern(self, _interner: &Interner) -> Ty {
+        Ty(Arc::new(self))
+    }
+}
+impl Ty {
+    pub fn kind(&self, _interner: &Interner) -> &TyKind {
+        &self.0
+    }
+    pub fn interned_mut(&mut self) -> &mut TyKind {
+        Arc::make_mut(&mut self.0)
+    }
+    pub fn into_inner(self) -> TyKind {
+        Arc::try_unwrap(self.0).unwrap_or_else(|a| (*a).clone())
+    }
+}
+#[derive(Clone, PartialEq, Eq, Debug, Hash)]
+pub struct GenericArg {
+    interned: GenericArgData,
+}
+#[derive(Clone, PartialEq, Eq, Debug, Hash)]
+pub enum GenericArgData {
+    Ty(Ty),
+}
+impl GenericArg {
+    /// Constructs a generic argument using `GenericArgData`.
+    pub fn new(_interner: &Interner, data: GenericArgData) -> Self {
+        GenericArg { interned: data }
+    }
+    /// Gets the interned value.
+    pub fn interned(&self) -> &GenericArgData {
+        &self.interned
+    }
+    /// Asserts that this is a type argument.
+    pub fn assert_ty_ref(&self, interner: &Interner) -> &Ty {
+        self.ty(interner).unwrap()
+    }
+    /// Checks whether the generic argument is a type.
+    pub fn is_ty(&self, _interner: &Interner) -> bool {
+        match self.interned() {
+            GenericArgData::Ty(_) => true,
+        }
+    }
+    /// Returns the type if it is one, `None` otherwise.
+    pub fn ty(&self, _interner: &Interner) -> Option<&Ty> {
+        match self.interned() {
+            GenericArgData::Ty(t) => Some(t),
+        }
+    }
+    pub fn interned_mut(&mut self) -> &mut GenericArgData {
+        &mut self.interned
+    }
+}
+/// A list of substitutions for generic parameters.
+#[derive(Clone, PartialEq, Eq, Debug, Hash)]
+pub struct Substitution(SmallVec<[GenericArg; 2]>);
+impl Substitution {
+    pub fn interned(&self) -> &[GenericArg] {
+        &self.0
+    }
+    pub fn len(&self, _: &Interner) -> usize {
+        self.0.len()
+    }
+    pub fn is_empty(&self, _: &Interner) -> bool {
+        self.0.is_empty()
+    }
+    pub fn at(&self, _: &Interner, i: usize) -> &GenericArg {
+        &self.0[i]
+    }
+    pub fn empty(_: &Interner) -> Substitution {
+        Substitution(SmallVec::new())
+    }
+    pub fn iter(&self, _: &Interner) -> std::slice::Iter<'_, GenericArg> {
+        self.0.iter()
+    }
+    pub fn from_iter(
+        interner: &Interner,
+        elements: impl IntoIterator<Item = impl CastTo<GenericArg>>,
+    ) -> Self {
+        Substitution(elements.into_iter().casted(interner).collect())
+    }
+    // We can hopefully add this to Chalk
+    pub fn intern(interned: SmallVec<[GenericArg; 2]>) -> Substitution {
+        Substitution(interned)
+    }
+    pub fn interned_mut(&mut self) -> &mut SmallVec<[GenericArg; 2]> {
+        &mut self.0
+    }
+}
+#[derive(Copy, Clone, PartialEq, Eq, Debug, Hash)]
+pub struct Binders<T> {
+    pub num_binders: usize,
+    pub value: T,
+}
+/// A trait with type parameters. This includes the `Self`, so this represents a concrete type implementing the trait.
+#[derive(Clone, PartialEq, Eq, Debug, Hash)]
+pub struct TraitRef {
+    pub trait_id: ChalkTraitId,
+    pub substitution: Substitution,
+}
+/// Like `generics::WherePredicate`, but with resolved types: A condition on the
+/// parameters of a generic item.
+#[derive(Debug, Clone, PartialEq, Eq, Hash)]
+pub enum WhereClause {
+    /// The given trait needs to be implemented for its type parameters.
+    Implemented(TraitRef),
+    /// An associated type bindings like in `Iterator<Item = T>`.
+    AliasEq(AliasEq),
+}
+pub type QuantifiedWhereClause = Binders<WhereClause>;
+#[derive(Debug, Clone, PartialEq, Eq, Hash)]
+pub struct QuantifiedWhereClauses(Arc<[QuantifiedWhereClause]>);
+impl QuantifiedWhereClauses {
+    pub fn from_iter(
+        _interner: &Interner,
+        elements: impl IntoIterator<Item = QuantifiedWhereClause>,
+    ) -> Self {
+        QuantifiedWhereClauses(elements.into_iter().collect())
+    }
+    pub fn interned(&self) -> &Arc<[QuantifiedWhereClause]> {
+        &self.0
+    }
+    pub fn interned_mut(&mut self) -> &mut Arc<[QuantifiedWhereClause]> {
+        &mut self.0
+    }
+}
+/// Basically a claim (currently not validated / checked) that the contained
+/// type / trait ref contains no inference variables; any inference variables it
+/// contained have been replaced by bound variables, and `kinds` tells us how
+/// many there are and whether they were normal or float/int variables. This is
+/// used to erase irrelevant differences between types before using them in
+/// queries.
+#[derive(Debug, Clone, PartialEq, Eq, Hash)]
+pub struct Canonical<T> {
+    pub value: T,
+    pub binders: CanonicalVarKinds,
+}
+/// Something (usually a goal), along with an environment.
+#[derive(Clone, Debug, PartialEq, Eq, Hash)]
+pub struct InEnvironment<T> {
+    pub environment: chalk_ir::Environment<Interner>,
+    pub goal: T,
+}
+impl<T> InEnvironment<T> {
+    pub fn new(environment: chalk_ir::Environment<Interner>, value: T) -> InEnvironment<T> {
+        InEnvironment { environment, goal: value }
+    }
+}
+/// Something that needs to be proven (by Chalk) during type checking, e.g. that
+/// a certain type implements a certain trait. Proving the Obligation might
+/// result in additional information about inference variables.
+#[derive(Clone, Debug, PartialEq, Eq, Hash)]
+pub enum DomainGoal {
+    Holds(WhereClause),
+}
+#[derive(Clone, Debug, PartialEq, Eq, Hash)]
+pub struct AliasEq {
+    pub alias: AliasTy,
+    pub ty: Ty,
+}
+#[derive(Clone, Debug, PartialEq, Eq)]
+pub struct SolutionVariables(pub Canonical<Substitution>);
+#[derive(Clone, Debug, PartialEq, Eq)]
+/// A (possible) solution for a proposed goal.
+pub enum Solution {
+    /// The goal indeed holds, and there is a unique value for all existential
+    /// variables.
+    Unique(SolutionVariables),
+    /// The goal may be provable in multiple ways, but regardless we may have some guidance
+    /// for type inference. In this case, we don't return any lifetime
+    /// constraints, since we have not "committed" to any particular solution
+    /// yet.
+    Ambig(Guidance),
+}
+#[derive(Clone, Debug, PartialEq, Eq)]
+/// When a goal holds ambiguously (e.g., because there are multiple possible
+/// solutions), we issue a set of *guidance* back to type inference.
+pub enum Guidance {
+    /// The existential variables *must* have the given values if the goal is
+    /// ever to hold, but that alone isn't enough to guarantee the goal will
+    /// actually hold.
+    Definite(SolutionVariables),
+    /// There are multiple plausible values for the existentials, but the ones
+    /// here are suggested as the preferred choice heuristically. These should
+    /// be used for inference fallback only.
+    Suggested(SolutionVariables),
+    /// There's no useful information to feed back to type inference
+    Unknown,
+}
diff --git a/crates/hir_ty/src/utils.rs b/crates/hir_ty/src/utils.rs
index 42d7af146..df0ea4368 100644
--- a/crates/hir_ty/src/utils.rs
+++ b/crates/hir_ty/src/utils.rs
@@ -2,13 +2,14 @@
 //! query, but can't be computed directly from `*Data` (ie, which need a `db`).
 use std::sync::Arc;
-use chalk_ir::DebruijnIndex;
+use chalk_ir::{BoundVar, DebruijnIndex};
 use hir_def::{
    adt::VariantData,
    db::DefDatabase,
    generics::{
        GenericParams, TypeParamData, TypeParamProvenance, WherePredicate, WherePredicateTypeTarget,
    },
+    intern::Interned,
    path::Path,
    resolver::{HasResolver, TypeNs},
    type_ref::TypeRef,
@@ -16,7 +17,7 @@ use hir_def::{
 };
 use hir_expand::name::{name, Name};
-use crate::{db::HirDatabase, TraitRef, TypeWalk, WhereClause};
+use crate::{db::HirDatabase, Interner, Substitution, TraitRef, TyKind, TypeWalk, WhereClause};
 fn direct_super_traits(db: &dyn DefDatabase, trait_: TraitId) -> Vec<TraitId> {
    let resolver = trait_.resolver(db);
@@ -32,11 +33,10 @@ fn direct_super_traits(db: &dyn DefDatabase, trait_: TraitId) -> Vec<TraitId> {
        .filter_map(|pred| match pred {
            WherePredicate::ForLifetime { target, bound, .. }
            | WherePredicate::TypeBound { target, bound } => match target {
-                WherePredicateTypeTarget::TypeRef(TypeRef::Path(p))
+                WherePredicateTypeTarget::TypeRef(type_ref) => match &**type_ref {
-                    if p == &Path::from(name![Self]) =>
+                    TypeRef::Path(p) if p == &Path::from(name![Self]) => bound.as_path(),
-                {
+                    _ => None,
-                    bound.as_path()
+                },
-                }
                WherePredicateTypeTarget::TypeParam(local_id) if Some(*local_id) == trait_self => {
                    bound.as_path()
                }
@@ -159,7 +159,7 @@ pub(crate) fn generics(db: &dyn DefDatabase, def: GenericDefId) -> Generics {
 #[derive(Debug)]
 pub(crate) struct Generics {
    def: GenericDefId,
-    pub(crate) params: Arc<GenericParams>,
+    pub(crate) params: Interned<GenericParams>,
    parent_generics: Option<Box<Generics>>,
 }
@@ -249,6 +249,26 @@ impl Generics {
            self.parent_generics.as_ref().and_then(|g| g.find_param(param))
        }
    }
+    /// Returns a Substitution that replaces each parameter by a bound variable.
+    pub(crate) fn bound_vars_subst(&self, debruijn: DebruijnIndex) -> Substitution {
+        Substitution::from_iter(
+            &Interner,
+            self.iter()
+                .enumerate()
+                .map(|(idx, _)| TyKind::BoundVar(BoundVar::new(debruijn, idx)).intern(&Interner)),
+        )
+    }
+    /// Returns a Substitution that replaces each parameter by itself (i.e. `Ty::Param`).
+    pub(crate) fn type_params_subst(&self, db: &dyn HirDatabase) -> Substitution {
+        Substitution::from_iter(
+            &Interner,
+            self.iter().map(|(id, _)| {
+                TyKind::Placeholder(crate::to_placeholder_idx(db, id)).intern(&Interner)
+            }),
+        )
+    }
 }
 fn parent_generic_def(db: &dyn DefDatabase, def: GenericDefId) -> Option<GenericDefId> {
diff --git a/crates/hir_ty/src/walk.rs b/crates/hir_ty/src/walk.rs
new file mode 100644
index 000000000..bfb3f1041
--- /dev/null
+++ b/crates/hir_ty/src/walk.rs
@@ -0,0 +1,381 @@
+//! The `TypeWalk` trait (probably to be replaced by Chalk's `Fold` and
+//! `Visit`).
+use std::mem;
+use chalk_ir::DebruijnIndex;
+use crate::{
+    utils::make_mut_slice, AliasEq, AliasTy, Binders, CallableSig, GenericArg, GenericArgData,
+    Interner, OpaqueTy, ProjectionTy, Substitution, TraitRef, Ty, TyKind, WhereClause,
+};
+/// This allows walking structures that contain types to do something with those
+/// types, similar to Chalk's `Fold` trait.
+pub trait TypeWalk {
+    fn walk(&self, f: &mut impl FnMut(&Ty));
+    fn walk_mut(&mut self, f: &mut impl FnMut(&mut Ty)) {
+        self.walk_mut_binders(&mut |ty, _binders| f(ty), DebruijnIndex::INNERMOST);
+    }
+    /// Walk the type, counting entered binders.
+    ///
+    /// `TyKind::Bound` variables use DeBruijn indexing, which means that 0 refers
+    /// to the innermost binder, 1 to the next, etc.. So when we want to
+    /// substitute a certain bound variable, we can't just walk the whole type
+    /// and blindly replace each instance of a certain index; when we 'enter'
+    /// things that introduce new bound variables, we have to keep track of
+    /// that. Currently, the only thing that introduces bound variables on our
+    /// side are `TyKind::Dyn` and `TyKind::Opaque`, which each introduce a bound
+    /// variable for the self type.
+    fn walk_mut_binders(
+        &mut self,
+        f: &mut impl FnMut(&mut Ty, DebruijnIndex),
+        binders: DebruijnIndex,
+    );
+    fn fold_binders(
+        mut self,
+        f: &mut impl FnMut(Ty, DebruijnIndex) -> Ty,
+        binders: DebruijnIndex,
+    ) -> Self
+    where
+        Self: Sized,
+    {
+        self.walk_mut_binders(
+            &mut |ty_mut, binders| {
+                let ty = mem::replace(ty_mut, TyKind::Unknown.intern(&Interner));
+                *ty_mut = f(ty, binders);
+            },
+            binders,
+        );
+        self
+    }
+    fn fold(mut self, f: &mut impl FnMut(Ty) -> Ty) -> Self
+    where
+        Self: Sized,
+    {
+        self.walk_mut(&mut |ty_mut| {
+            let ty = mem::replace(ty_mut, TyKind::Unknown.intern(&Interner));
+            *ty_mut = f(ty);
+        });
+        self
+    }
+    /// Substitutes `TyKind::Bound` vars with the given substitution.
+    fn subst_bound_vars(self, substs: &Substitution) -> Self
+    where
+        Self: Sized,
+    {
+        self.subst_bound_vars_at_depth(substs, DebruijnIndex::INNERMOST)
+    }
+    /// Substitutes `TyKind::Bound` vars with the given substitution.
+    fn subst_bound_vars_at_depth(mut self, substs: &Substitution, depth: DebruijnIndex) -> Self
+    where
+        Self: Sized,
+    {
+        self.walk_mut_binders(
+            &mut |ty, binders| {
+                if let &mut TyKind::BoundVar(bound) = ty.interned_mut() {
+                    if bound.debruijn >= binders {
+                        *ty = substs.interned()[bound.index]
+                            .assert_ty_ref(&Interner)
+                            .clone()
+                            .shift_bound_vars(binders);
+                    }
+                }
+            },
+            depth,
+        );
+        self
+    }
+    /// Shifts up debruijn indices of `TyKind::Bound` vars by `n`.
+    fn shift_bound_vars(self, n: DebruijnIndex) -> Self
+    where
+        Self: Sized,
+    {
+        self.fold_binders(
+            &mut |ty, binders| match ty.kind(&Interner) {
+                TyKind::BoundVar(bound) if bound.debruijn >= binders => {
+                    TyKind::BoundVar(bound.shifted_in_from(n)).intern(&Interner)
+                }
+                _ => ty,
+            },
+            DebruijnIndex::INNERMOST,
+        )
+    }
+    /// Shifts debruijn indices of `TyKind::Bound` vars out (down) by `n`.
+    fn shift_bound_vars_out(self, n: DebruijnIndex) -> Self
+    where
+        Self: Sized + std::fmt::Debug,
+    {
+        self.fold_binders(
+            &mut |ty, binders| match ty.kind(&Interner) {
+                TyKind::BoundVar(bound) if bound.debruijn >= binders => {
+                    TyKind::BoundVar(bound.shifted_out_to(n).unwrap_or(bound.clone()))
+                        .intern(&Interner)
+                }
+                _ => ty,
+            },
+            DebruijnIndex::INNERMOST,
+        )
+    }
+}
+impl TypeWalk for Ty {
+    fn walk(&self, f: &mut impl FnMut(&Ty)) {
+        match self.kind(&Interner) {
+            TyKind::Alias(AliasTy::Projection(p_ty)) => {
+                for t in p_ty.substitution.iter(&Interner) {
+                    t.walk(f);
+                }
+            }
+            TyKind::Alias(AliasTy::Opaque(o_ty)) => {
+                for t in o_ty.substitution.iter(&Interner) {
+                    t.walk(f);
+                }
+            }
+            TyKind::Dyn(dyn_ty) => {
+                for p in dyn_ty.bounds.value.interned().iter() {
+                    p.walk(f);
+                }
+            }
+            TyKind::Slice(ty) | TyKind::Array(ty) | TyKind::Ref(_, ty) | TyKind::Raw(_, ty) => {
+                ty.walk(f);
+            }
+            _ => {
+                if let Some(substs) = self.substs() {
+                    for t in substs.iter(&Interner) {
+                        t.walk(f);
+                    }
+                }
+            }
+        }
+        f(self);
+    }
+    fn walk_mut_binders(
+        &mut self,
+        f: &mut impl FnMut(&mut Ty, DebruijnIndex),
+        binders: DebruijnIndex,
+    ) {
+        match self.interned_mut() {
+            TyKind::Alias(AliasTy::Projection(p_ty)) => {
+                p_ty.substitution.walk_mut_binders(f, binders);
+            }
+            TyKind::Dyn(dyn_ty) => {
+                for p in make_mut_slice(dyn_ty.bounds.value.interned_mut()) {
+                    p.walk_mut_binders(f, binders.shifted_in());
+                }
+            }
+            TyKind::Alias(AliasTy::Opaque(o_ty)) => {
+                o_ty.substitution.walk_mut_binders(f, binders);
+            }
+            TyKind::Slice(ty) | TyKind::Array(ty) | TyKind::Ref(_, ty) | TyKind::Raw(_, ty) => {
+                ty.walk_mut_binders(f, binders);
+            }
+            _ => {
+                if let Some(substs) = self.substs_mut() {
+                    substs.walk_mut_binders(f, binders);
+                }
+            }
+        }
+        f(self, binders);
+    }
+}
+impl<T: TypeWalk> TypeWalk for Vec<T> {
+    fn walk(&self, f: &mut impl FnMut(&Ty)) {
+        for t in self {
+            t.walk(f);
+        }
+    }
+    fn walk_mut_binders(
+        &mut self,
+        f: &mut impl FnMut(&mut Ty, DebruijnIndex),
+        binders: DebruijnIndex,
+    ) {
+        for t in self {
+            t.walk_mut_binders(f, binders);
+        }
+    }
+}
+impl TypeWalk for OpaqueTy {
+    fn walk(&self, f: &mut impl FnMut(&Ty)) {
+        self.substitution.walk(f);
+    }
+    fn walk_mut_binders(
+        &mut self,
+        f: &mut impl FnMut(&mut Ty, DebruijnIndex),
+        binders: DebruijnIndex,
+    ) {
+        self.substitution.walk_mut_binders(f, binders);
+    }
+}
+impl TypeWalk for ProjectionTy {
+    fn walk(&self, f: &mut impl FnMut(&Ty)) {
+        self.substitution.walk(f);
+    }
+    fn walk_mut_binders(
+        &mut self,
+        f: &mut impl FnMut(&mut Ty, DebruijnIndex),
+        binders: DebruijnIndex,
+    ) {
+        self.substitution.walk_mut_binders(f, binders);
+    }
+}
+impl TypeWalk for AliasTy {
+    fn walk(&self, f: &mut impl FnMut(&Ty)) {
+        match self {
+            AliasTy::Projection(it) => it.walk(f),
+            AliasTy::Opaque(it) => it.walk(f),
+        }
+    }
+    fn walk_mut_binders(
+        &mut self,
+        f: &mut impl FnMut(&mut Ty, DebruijnIndex),
+        binders: DebruijnIndex,
+    ) {
+        match self {
+            AliasTy::Projection(it) => it.walk_mut_binders(f, binders),
+            AliasTy::Opaque(it) => it.walk_mut_binders(f, binders),
+        }
+    }
+}
+impl TypeWalk for GenericArg {
+    fn walk(&self, f: &mut impl FnMut(&Ty)) {
+        match &self.interned() {
+            GenericArgData::Ty(ty) => {
+                ty.walk(f);
+            }
+        }
+    }
+    fn walk_mut_binders(
+        &mut self,
+        f: &mut impl FnMut(&mut Ty, DebruijnIndex),
+        binders: DebruijnIndex,
+    ) {
+        match self.interned_mut() {
+            GenericArgData::Ty(ty) => {
+                ty.walk_mut_binders(f, binders);
+            }
+        }
+    }
+}
+impl TypeWalk for Substitution {
+    fn walk(&self, f: &mut impl FnMut(&Ty)) {
+        for t in self.iter(&Interner) {
+            t.walk(f);
+        }
+    }
+    fn walk_mut_binders(
+        &mut self,
+        f: &mut impl FnMut(&mut Ty, DebruijnIndex),
+        binders: DebruijnIndex,
+    ) {
+        for t in self.interned_mut() {
+            t.walk_mut_binders(f, binders);
+        }
+    }
+}
+impl<T: TypeWalk> TypeWalk for Binders<T> {
+    fn walk(&self, f: &mut impl FnMut(&Ty)) {
+        self.value.walk(f);
+    }
+    fn walk_mut_binders(
+        &mut self,
+        f: &mut impl FnMut(&mut Ty, DebruijnIndex),
+        binders: DebruijnIndex,
+    ) {
+        self.value.walk_mut_binders(f, binders.shifted_in())
+    }
+}
+impl TypeWalk for TraitRef {
+    fn walk(&self, f: &mut impl FnMut(&Ty)) {
+        self.substitution.walk(f);
+    }
+    fn walk_mut_binders(
+        &mut self,
+        f: &mut impl FnMut(&mut Ty, DebruijnIndex),
+        binders: DebruijnIndex,
+    ) {
+        self.substitution.walk_mut_binders(f, binders);
+    }
+}
+impl TypeWalk for WhereClause {
+    fn walk(&self, f: &mut impl FnMut(&Ty)) {
+        match self {
+            WhereClause::Implemented(trait_ref) => trait_ref.walk(f),
+            WhereClause::AliasEq(alias_eq) => alias_eq.walk(f),
+        }
+    }
+    fn walk_mut_binders(
+        &mut self,
+        f: &mut impl FnMut(&mut Ty, DebruijnIndex),
+        binders: DebruijnIndex,
+    ) {
+        match self {
+            WhereClause::Implemented(trait_ref) => trait_ref.walk_mut_binders(f, binders),
+            WhereClause::AliasEq(alias_eq) => alias_eq.walk_mut_binders(f, binders),
+        }
+    }
+}
+impl TypeWalk for CallableSig {
+    fn walk(&self, f: &mut impl FnMut(&Ty)) {
+        for t in self.params_and_return.iter() {
+            t.walk(f);
+        }
+    }
+    fn walk_mut_binders(
+        &mut self,
+        f: &mut impl FnMut(&mut Ty, DebruijnIndex),
+        binders: DebruijnIndex,
+    ) {
+        for t in make_mut_slice(&mut self.params_and_return) {
+            t.walk_mut_binders(f, binders);
+        }
+    }
+}
+impl TypeWalk for AliasEq {
+    fn walk(&self, f: &mut impl FnMut(&Ty)) {
+        self.ty.walk(f);
+        match &self.alias {
+            AliasTy::Projection(projection_ty) => projection_ty.walk(f),
+            AliasTy::Opaque(opaque) => opaque.walk(f),
+        }
+    }
+    fn walk_mut_binders(
+        &mut self,
+        f: &mut impl FnMut(&mut Ty, DebruijnIndex),
+        binders: DebruijnIndex,
+    ) {
+        self.ty.walk_mut_binders(f, binders);
+        match &mut self.alias {
+            AliasTy::Projection(projection_ty) => projection_ty.walk_mut_binders(f, binders),
+            AliasTy::Opaque(opaque) => opaque.walk_mut_binders(f, binders),
+        }
+    }
+}
diff --git a/crates/ide/src/inlay_hints.rs b/crates/ide/src/inlay_hints.rs
index f73edf8b6..d5ef054d8 100644
--- a/crates/ide/src/inlay_hints.rs
+++ b/crates/ide/src/inlay_hints.rs
@@ -234,7 +234,7 @@ fn hint_iterator(
            hir::AssocItem::TypeAlias(alias) if alias.name(db) == known::Item => Some(alias),
            _ => None,
        })?;
-        if let Some(ty) = ty.normalize_trait_assoc_type(db, iter_trait, &[], assoc_type_item) {
+        if let Some(ty) = ty.normalize_trait_assoc_type(db, &[], assoc_type_item) {
            const LABEL_START: &str = "impl Iterator<Item = ";
            const LABEL_END: &str = ">";
diff --git a/crates/ide_assists/src/handlers/convert_into_to_from.rs b/crates/ide_assists/src/handlers/convert_into_to_from.rs
new file mode 100644
index 000000000..199e1ad5c
--- /dev/null
+++ b/crates/ide_assists/src/handlers/convert_into_to_from.rs
@@ -0,0 +1,355 @@
+use ide_db::{
+    helpers::{mod_path_to_ast, FamousDefs},
+    traits::resolve_target_trait,
+};
+use syntax::ast::{self, AstNode, NameOwner};
+use crate::{AssistContext, AssistId, AssistKind, Assists};
+// Assist: convert_into_to_from
+//
+// Converts an Into impl to an equivalent From impl.
+//
+// ```
+// # //- /lib.rs crate:core
+// # pub mod convert { pub trait Into<T> { pub fn into(self) -> T; } }
+// # //- /lib.rs crate:main deps:core
+// # use core::convert::Into;
+// impl $0Into<Thing> for usize {
+//     fn into(self) -> Thing {
+//         Thing {
+//             b: self.to_string(),
+//             a: self
+//         }
+//     }
+// }
+// ```
+// ->
+// ```
+// # use core::convert::Into;
+// impl From<usize> for Thing {
+//     fn from(val: usize) -> Self {
+//         Thing {
+//             b: val.to_string(),
+//             a: val
+//         }
+//     }
+// }
+// ```
+pub(crate) fn convert_into_to_from(acc: &mut Assists, ctx: &AssistContext) -> Option<()> {
+    let impl_ = ctx.find_node_at_offset::<ast::Impl>()?;
+    let src_type = impl_.self_ty()?;
+    let ast_trait = impl_.trait_()?;
+    let module = ctx.sema.scope(impl_.syntax()).module()?;
+    let trait_ = resolve_target_trait(&ctx.sema, &impl_)?;
+    if trait_ != FamousDefs(&ctx.sema, Some(module.krate())).core_convert_Into()? {
+        return None;
+    }
+    let src_type_path = {
+        let src_type_path = src_type.syntax().descendants().find_map(ast::Path::cast)?;
+        let src_type_def = match ctx.sema.resolve_path(&src_type_path) {
+            Some(hir::PathResolution::Def(module_def)) => module_def,
+            _ => return None,
+        };
+        mod_path_to_ast(&module.find_use_path(ctx.db(), src_type_def)?)
+    };
+    let dest_type = match &ast_trait {
+        ast::Type::PathType(path) => {
+            path.path()?.segment()?.generic_arg_list()?.generic_args().next()?
+        }
+        _ => return None,
+    };
+    let into_fn = impl_.assoc_item_list()?.assoc_items().find_map(|item| {
+        if let ast::AssocItem::Fn(f) = item {
+            if f.name()?.text() == "into" {
+                return Some(f);
+            }
+        };
+        None
+    })?;
+    let into_fn_name = into_fn.name()?;
+    let into_fn_params = into_fn.param_list()?;
+    let into_fn_return = into_fn.ret_type()?;
+    let selfs = into_fn
+        .body()?
+        .syntax()
+        .descendants()
+        .filter_map(ast::NameRef::cast)
+        .filter(|name| name.text() == "self" || name.text() == "Self");
+    acc.add(
+        AssistId("convert_into_to_from", AssistKind::RefactorRewrite),
+        "Convert Into to From",
+        impl_.syntax().text_range(),
+        |builder| {
+            builder.replace(src_type.syntax().text_range(), dest_type.to_string());
+            builder.replace(ast_trait.syntax().text_range(), format!("From<{}>", src_type));
+            builder.replace(into_fn_return.syntax().text_range(), "-> Self");
+            builder.replace(
+                into_fn_params.syntax().text_range(),
+                format!("(val: {})", src_type.to_string()),
+            );
+            builder.replace(into_fn_name.syntax().text_range(), "from");
+            for s in selfs {
+                match s.text().as_ref() {
+                    "self" => builder.replace(s.syntax().text_range(), "val"),
+                    "Self" => builder.replace(s.syntax().text_range(), src_type_path.to_string()),
+                    _ => {}
+                }
+            }
+        },
+    )
+}
+#[cfg(test)]
+mod tests {
+    use super::*;
+    use crate::tests::check_assist;
+    #[test]
+    fn convert_into_to_from_converts_a_struct() {
+        check_convert_into_to_from(
+            r#"
+struct Thing {
+    a: String,
+    b: usize
+}
+impl $0core::convert::Into<Thing> for usize {
+    fn into(self) -> Thing {
+        Thing {
+            b: self.to_string(),
+            a: self
+        }
+    }
+}
+"#,
+            r#"
+struct Thing {
+    a: String,
+    b: usize
+}
+impl From<usize> for Thing {
+    fn from(val: usize) -> Self {
+        Thing {
+            b: val.to_string(),
+            a: val
+        }
+    }
+}
+"#,
+        )
+    }
+    #[test]
+    fn convert_into_to_from_converts_enums() {
+        check_convert_into_to_from(
+            r#"
+enum Thing {
+    Foo(String),
+    Bar(String)
+}
+impl $0core::convert::Into<String> for Thing {
+    fn into(self) -> String {
+        match self {
+            Self::Foo(s) => s,
+            Self::Bar(s) => s
+        }
+    }
+}
+"#,
+            r#"
+enum Thing {
+    Foo(String),
+    Bar(String)
+}
+impl From<Thing> for String {
+    fn from(val: Thing) -> Self {
+        match val {
+            Thing::Foo(s) => s,
+            Thing::Bar(s) => s
+        }
+    }
+}
+"#,
+        )
+    }
+    #[test]
+    fn convert_into_to_from_on_enum_with_lifetimes() {
+        check_convert_into_to_from(
+            r#"
+enum Thing<'a> {
+    Foo(&'a str),
+    Bar(&'a str)
+}
+impl<'a> $0core::convert::Into<&'a str> for Thing<'a> {
+    fn into(self) -> &'a str {
+        match self {
+            Self::Foo(s) => s,
+            Self::Bar(s) => s
+        }
+    }
+}
+"#,
+            r#"
+enum Thing<'a> {
+    Foo(&'a str),
+    Bar(&'a str)
+}
+impl<'a> From<Thing<'a>> for &'a str {
+    fn from(val: Thing<'a>) -> Self {
+        match val {
+            Thing::Foo(s) => s,
+            Thing::Bar(s) => s
+        }
+    }
+}
+"#,
+        )
+    }
+    #[test]
+    fn convert_into_to_from_works_on_references() {
+        check_convert_into_to_from(
+            r#"
+struct Thing(String);
+impl $0core::convert::Into<String> for &Thing {
+    fn into(self) -> Thing {
+        self.0.clone()
+    }
+}
+"#,
+            r#"
+struct Thing(String);
+impl From<&Thing> for String {
+    fn from(val: &Thing) -> Self {
+        val.0.clone()
+    }
+}
+"#,
+        )
+    }
+    #[test]
+    fn convert_into_to_from_works_on_qualified_structs() {
+        check_convert_into_to_from(
+            r#"
+mod things {
+    pub struct Thing(String);
+    pub struct BetterThing(String);
+}
+impl $0core::convert::Into<things::BetterThing> for &things::Thing {
+    fn into(self) -> Thing {
+        things::BetterThing(self.0.clone())
+    }
+}
+"#,
+            r#"
+mod things {
+    pub struct Thing(String);
+    pub struct BetterThing(String);
+}
+impl From<&things::Thing> for things::BetterThing {
+    fn from(val: &things::Thing) -> Self {
+        things::BetterThing(val.0.clone())
+    }
+}
+"#,
+        )
+    }
+    #[test]
+    fn convert_into_to_from_works_on_qualified_enums() {
+        check_convert_into_to_from(
+            r#"
+mod things {
+    pub enum Thing {
+        A(String)
+    }
+    pub struct BetterThing {
+        B(String)
+    }
+}
+impl $0core::convert::Into<things::BetterThing> for &things::Thing {
+    fn into(self) -> Thing {
+        match self {
+            Self::A(s) => things::BetterThing::B(s)
+        }
+    }
+}
+"#,
+            r#"
+mod things {
+    pub enum Thing {
+        A(String)
+    }
+    pub struct BetterThing {
+        B(String)
+    }
+}
+impl From<&things::Thing> for things::BetterThing {
+    fn from(val: &things::Thing) -> Self {
+        match val {
+            things::Thing::A(s) => things::BetterThing::B(s)
+        }
+    }
+}
+"#,
+        )
+    }
+    #[test]
+    fn convert_into_to_from_not_applicable_on_any_trait_named_into() {
+        check_assist_not_applicable(
+            r#"
+pub trait Into<T> {{
+    pub fn into(self) -> T;
+}}
+struct Thing {
+    a: String,
+}
+impl $0Into<Thing> for String {
+    fn into(self) -> Thing {
+        Thing {
+            a: self
+        }
+    }
+}
+"#,
+        );
+    }
+    fn check_convert_into_to_from(before: &str, after: &str) {
+        let before = &format!("//- /main.rs crate:main deps:core{}{}", before, FamousDefs::FIXTURE);
+        check_assist(convert_into_to_from, before, after);
+    }
+    fn check_assist_not_applicable(before: &str) {
+        let before = &format!("//- /main.rs crate:main deps:core{}{}", before, FamousDefs::FIXTURE);
+        crate::tests::check_assist_not_applicable(convert_into_to_from, before);
+    }
+}
diff --git a/crates/ide_assists/src/lib.rs b/crates/ide_assists/src/lib.rs
index 3d1dcef4c..3e2c82dac 100644
--- a/crates/ide_assists/src/lib.rs
+++ b/crates/ide_assists/src/lib.rs
@@ -117,6 +117,7 @@ mod handlers {
    mod convert_integer_literal;
    mod convert_comment_block;
    mod convert_iter_for_each_to_for;
+    mod convert_into_to_from;
    mod early_return;
    mod expand_glob_import;
    mod extract_function;
@@ -185,6 +186,7 @@ mod handlers {
            convert_integer_literal::convert_integer_literal,
            convert_comment_block::convert_comment_block,
            convert_iter_for_each_to_for::convert_iter_for_each_to_for,
+            convert_into_to_from::convert_into_to_from,
            early_return::convert_to_guarded_return,
            expand_glob_import::expand_glob_import,
            extract_struct_from_enum_variant::extract_struct_from_enum_variant,
diff --git a/crates/ide_assists/src/tests/generated.rs b/crates/ide_assists/src/tests/generated.rs
index 03b7fb366..27a22ca10 100644
--- a/crates/ide_assists/src/tests/generated.rs
+++ b/crates/ide_assists/src/tests/generated.rs
@@ -206,6 +206,38 @@ const _: i32 = 0b1010;
 }
 #[test]
+fn doctest_convert_into_to_from() {
+    check_doc_test(
+        "convert_into_to_from",
+        r#####"
+//- /lib.rs crate:core
+pub mod convert { pub trait Into<T> { pub fn into(self) -> T; } }
+//- /lib.rs crate:main deps:core
+use core::convert::Into;
+impl $0Into<Thing> for usize {
+    fn into(self) -> Thing {
+        Thing {
+            b: self.to_string(),
+            a: self
+        }
+    }
+}
+"#####,
+        r#####"
+use core::convert::Into;
+impl From<usize> for Thing {
+    fn from(val: usize) -> Self {
+        Thing {
+            b: val.to_string(),
+            a: val
+        }
+    }
+}
+"#####,
+    )
+}
+#[test]
 fn doctest_convert_iter_for_each_to_for() {
    check_doc_test(
        "convert_iter_for_each_to_for",
diff --git a/crates/ide_db/src/helpers.rs b/crates/ide_db/src/helpers.rs
index 9992a92bd..66798ea3a 100644
--- a/crates/ide_db/src/helpers.rs
+++ b/crates/ide_db/src/helpers.rs
@@ -93,6 +93,10 @@ impl FamousDefs<'_, '_> {
        self.find_trait("core:convert:From")
    }
+    pub fn core_convert_Into(&self) -> Option<Trait> {
+        self.find_trait("core:convert:Into")
+    }
    pub fn core_option_Option(&self) -> Option<Enum> {
        self.find_enum("core:option:Option")
    }
diff --git a/crates/ide_db/src/helpers/famous_defs_fixture.rs b/crates/ide_db/src/helpers/famous_defs_fixture.rs
index d3464ae17..4d79e064e 100644
--- a/crates/ide_db/src/helpers/famous_defs_fixture.rs
+++ b/crates/ide_db/src/helpers/famous_defs_fixture.rs
@@ -14,6 +14,10 @@ pub mod convert {
    pub trait From<T> {
        fn from(t: T) -> Self;
    }
+    pub trait Into<T> {
+        pub fn into(self) -> T;
+    }
 }
 pub mod default {
@@ -120,7 +124,7 @@ pub mod option {
 pub mod prelude {
    pub use crate::{
        cmp::Ord,
-        convert::From,
+        convert::{From, Into},
        default::Default,
        iter::{IntoIterator, Iterator},
        ops::{Fn, FnMut, FnOnce},
diff --git a/crates/mbe/src/benchmark.rs b/crates/mbe/src/benchmark.rs
index ba814a2e1..38707ffa5 100644
--- a/crates/mbe/src/benchmark.rs
+++ b/crates/mbe/src/benchmark.rs
@@ -65,7 +65,7 @@ fn macro_rules_fixtures_tt() -> FxHashMap<String, tt::Subtree> {
        .filter_map(ast::MacroRules::cast)
        .map(|rule| {
            let id = rule.name().unwrap().to_string();
-            let (def_tt, _) = ast_to_token_tree(&rule.token_tree().unwrap()).unwrap();
+            let (def_tt, _) = ast_to_token_tree(&rule.token_tree().unwrap());
            (id, def_tt)
        })
        .collect()
diff --git a/crates/mbe/src/expander.rs b/crates/mbe/src/expander.rs
index 3197c834c..bfef7f73d 100644
--- a/crates/mbe/src/expander.rs
+++ b/crates/mbe/src/expander.rs
@@ -159,8 +159,7 @@ mod tests {
        let macro_definition =
            source_file.syntax().descendants().find_map(ast::MacroRules::cast).unwrap();
-        let (definition_tt, _) =
+        let (definition_tt, _) = ast_to_token_tree(&macro_definition.token_tree().unwrap());
-            ast_to_token_tree(&macro_definition.token_tree().unwrap()).unwrap();
        crate::MacroRules::parse(&definition_tt).unwrap()
    }
@@ -169,8 +168,7 @@ mod tests {
        let macro_invocation =
            source_file.syntax().descendants().find_map(ast::MacroCall::cast).unwrap();
-        let (invocation_tt, _) =
+        let (invocation_tt, _) = ast_to_token_tree(&macro_invocation.token_tree().unwrap());
-            ast_to_token_tree(&macro_invocation.token_tree().unwrap()).unwrap();
        expand_rules(&rules.rules, &invocation_tt)
    }
diff --git a/crates/mbe/src/syntax_bridge.rs b/crates/mbe/src/syntax_bridge.rs
index ae0780072..9ba98f7fb 100644
--- a/crates/mbe/src/syntax_bridge.rs
+++ b/crates/mbe/src/syntax_bridge.rs
@@ -43,18 +43,18 @@ pub struct TokenMap {
 /// Convert the syntax tree (what user has written) to a `TokenTree` (what macro
 /// will consume).
-pub fn ast_to_token_tree(ast: &impl ast::AstNode) -> Option<(tt::Subtree, TokenMap)> {
+pub fn ast_to_token_tree(ast: &impl ast::AstNode) -> (tt::Subtree, TokenMap) {
    syntax_node_to_token_tree(ast.syntax())
 }
 /// Convert the syntax node to a `TokenTree` (what macro
 /// will consume).
-pub fn syntax_node_to_token_tree(node: &SyntaxNode) -> Option<(tt::Subtree, TokenMap)> {
+pub fn syntax_node_to_token_tree(node: &SyntaxNode) -> (tt::Subtree, TokenMap) {
    let global_offset = node.text_range().start();
    let mut c = Convertor::new(node, global_offset);
-    let subtree = c.go()?;
+    let subtree = c.go();
    c.id_alloc.map.entries.shrink_to_fit();
-    Some((subtree, c.id_alloc.map))
+    (subtree, c.id_alloc.map)
 }
 // The following items are what `rustc` macro can be parsed into :
@@ -108,7 +108,7 @@ pub fn parse_to_token_tree(text: &str) -> Option<(tt::Subtree, TokenMap)> {
        },
    };
-    let subtree = conv.go()?;
+    let subtree = conv.go();
    Some((subtree, conv.id_alloc.map))
 }
@@ -319,7 +319,7 @@ trait SrcToken: std::fmt::Debug {
 trait TokenConvertor {
    type Token: SrcToken;
-    fn go(&mut self) -> Option<tt::Subtree> {
+    fn go(&mut self) -> tt::Subtree {
        let mut subtree = tt::Subtree::default();
        subtree.delimiter = None;
        while self.peek().is_some() {
@@ -327,10 +327,10 @@ trait TokenConvertor {
        }
        if subtree.token_trees.len() == 1 {
            if let tt::TokenTree::Subtree(first) = &subtree.token_trees[0] {
-                return Some(first.clone());
+                return first.clone();
            }
        }
-        Some(subtree)
+        subtree
    }
    fn collect_leaf(&mut self, result: &mut Vec<tt::TokenTree>) {
@@ -858,7 +858,7 @@ mod tests {
        // - T!['}']
        // - WHITE_SPACE
        let token_tree = ast::TokenTree::cast(token_tree).unwrap();
-        let tt = ast_to_token_tree(&token_tree).unwrap().0;
+        let tt = ast_to_token_tree(&token_tree).0;
        assert_eq!(tt.delimiter_kind(), Some(tt::DelimiterKind::Brace));
    }
@@ -867,7 +867,7 @@ mod tests {
    fn test_token_tree_multi_char_punct() {
        let source_file = ast::SourceFile::parse("struct Foo { a: x::Y }").ok().unwrap();
        let struct_def = source_file.syntax().descendants().find_map(ast::Struct::cast).unwrap();
-        let tt = ast_to_token_tree(&struct_def).unwrap().0;
+        let tt = ast_to_token_tree(&struct_def).0;
        token_tree_to_syntax_node(&tt, FragmentKind::Item).unwrap();
    }
 }
diff --git a/crates/mbe/src/tests.rs b/crates/mbe/src/tests.rs
index 6da18ecf4..3698ff3f0 100644
--- a/crates/mbe/src/tests.rs
+++ b/crates/mbe/src/tests.rs
@@ -29,8 +29,7 @@ macro_rules! impl_fixture {
                let macro_invocation =
                    source_file.syntax().descendants().find_map(ast::MacroCall::cast).unwrap();
-                let (invocation_tt, _) = ast_to_token_tree(&macro_invocation.token_tree().unwrap())
+                let (invocation_tt, _) = ast_to_token_tree(&macro_invocation.token_tree().unwrap());
-                    .ok_or_else(|| ExpandError::ConversionError)?;
                self.rules.expand(&invocation_tt).result()
            }
@@ -101,7 +100,7 @@ macro_rules! impl_fixture {
                        .descendants()
                        .find_map(ast::TokenTree::cast)
                        .unwrap();
-                    let mut wrapped = ast_to_token_tree(&wrapped).unwrap().0;
+                    let mut wrapped = ast_to_token_tree(&wrapped).0;
                    wrapped.delimiter = None;
                    wrapped
                };
@@ -151,7 +150,7 @@ pub(crate) fn parse_macro_error(ra_fixture: &str) -> ParseError {
 pub(crate) fn parse_to_token_tree_by_syntax(ra_fixture: &str) -> tt::Subtree {
    let source_file = ast::SourceFile::parse(ra_fixture).ok().unwrap();
-    let tt = syntax_node_to_token_tree(source_file.syntax()).unwrap().0;
+    let tt = syntax_node_to_token_tree(source_file.syntax()).0;
    let parsed = parse_to_token_tree(ra_fixture).unwrap().0;
    assert_eq!(tt, parsed);
@@ -164,7 +163,7 @@ fn parse_macro_rules_to_tt(ra_fixture: &str) -> tt::Subtree {
    let macro_definition =
        source_file.syntax().descendants().find_map(ast::MacroRules::cast).unwrap();
-    let (definition_tt, _) = ast_to_token_tree(&macro_definition.token_tree().unwrap()).unwrap();
+    let (definition_tt, _) = ast_to_token_tree(&macro_definition.token_tree().unwrap());
    let parsed = parse_to_token_tree(
        &ra_fixture[macro_definition.token_tree().unwrap().syntax().text_range()],
@@ -181,7 +180,7 @@ fn parse_macro_def_to_tt(ra_fixture: &str) -> tt::Subtree {
    let macro_definition =
        source_file.syntax().descendants().find_map(ast::MacroDef::cast).unwrap();
-    let (definition_tt, _) = ast_to_token_tree(&macro_definition.body().unwrap()).unwrap();
+    let (definition_tt, _) = ast_to_token_tree(&macro_definition.body().unwrap());
    let parsed =
        parse_to_token_tree(&ra_fixture[macro_definition.body().unwrap().syntax().text_range()])
diff --git a/crates/mbe/src/tests/rule.rs b/crates/mbe/src/tests/rule.rs
index bf48112b3..5c61a98fd 100644
--- a/crates/mbe/src/tests/rule.rs
+++ b/crates/mbe/src/tests/rule.rs
@@ -44,6 +44,6 @@ fn parse_macro_arm(arm_definition: &str) -> Result<crate::MacroRules, ParseError
    let macro_definition =
        source_file.syntax().descendants().find_map(ast::MacroRules::cast).unwrap();
-    let (definition_tt, _) = ast_to_token_tree(&macro_definition.token_tree().unwrap()).unwrap();
+    let (definition_tt, _) = ast_to_token_tree(&macro_definition.token_tree().unwrap());
    crate::MacroRules::parse(&definition_tt)
 }
diff --git a/crates/rust-analyzer/src/bin/flags.rs b/crates/rust-analyzer/src/bin/flags.rs
index b05fc00b9..63953098a 100644
--- a/crates/rust-analyzer/src/bin/flags.rs
+++ b/crates/rust-analyzer/src/bin/flags.rs
@@ -71,6 +71,8 @@ xflags::xflags! {
            optional --load-output-dirs
            /// Use proc-macro-srv for proc-macro expanding.
            optional --with-proc-macro
+            /// Only resolve names, don't run type inference.
+            optional --skip-inference
        }
        cmd diagnostics
@@ -158,6 +160,7 @@ pub struct AnalysisStats {
    pub no_sysroot: bool,
    pub load_output_dirs: bool,
    pub with_proc_macro: bool,
+    pub skip_inference: bool,
 }
 #[derive(Debug)]
diff --git a/crates/rust-analyzer/src/bin/main.rs b/crates/rust-analyzer/src/bin/main.rs
index 3b9b9e8b4..873e82c7b 100644
--- a/crates/rust-analyzer/src/bin/main.rs
+++ b/crates/rust-analyzer/src/bin/main.rs
@@ -78,6 +78,7 @@ fn try_main() -> Result<()> {
            path: cmd.path,
            load_output_dirs: cmd.load_output_dirs,
            with_proc_macro: cmd.with_proc_macro,
+            skip_inference: cmd.skip_inference,
        }
        .run(verbosity)?,
diff --git a/crates/rust-analyzer/src/cargo_target_spec.rs b/crates/rust-analyzer/src/cargo_target_spec.rs
index 5af0802a2..909c21532 100644
--- a/crates/rust-analyzer/src/cargo_target_spec.rs
+++ b/crates/rust-analyzer/src/cargo_target_spec.rs
@@ -201,7 +201,7 @@ mod tests {
        let cfg_expr = {
            let source_file = ast::SourceFile::parse(cfg).ok().unwrap();
            let tt = source_file.syntax().descendants().find_map(ast::TokenTree::cast).unwrap();
-            let (tt, _) = ast_to_token_tree(&tt).unwrap();
+            let (tt, _) = ast_to_token_tree(&tt);
            CfgExpr::parse(&tt)
        };
diff --git a/crates/rust-analyzer/src/cli/analysis_stats.rs b/crates/rust-analyzer/src/cli/analysis_stats.rs
index 9c59e7ee4..18fd7ea74 100644
--- a/crates/rust-analyzer/src/cli/analysis_stats.rs
+++ b/crates/rust-analyzer/src/cli/analysis_stats.rs
@@ -9,10 +9,11 @@ use std::{
 use hir::{
    db::{AstDatabase, DefDatabase, HirDatabase},
-    AssocItem, Crate, HasSource, HirDisplay, ModuleDef,
+    AssocItem, Crate, Function, HasSource, HirDisplay, ModuleDef,
 };
 use hir_def::FunctionId;
 use hir_ty::TypeWalk;
+use ide::{AnalysisHost, RootDatabase};
 use ide_db::base_db::{
    salsa::{self, ParallelDatabase},
    SourceDatabaseExt,
@@ -24,6 +25,7 @@ use rayon::prelude::*;
 use rustc_hash::FxHashSet;
 use stdx::format_to;
 use syntax::AstNode;
+use vfs::Vfs;
 use crate::cli::{
    load_cargo::{load_workspace_at, LoadCargoConfig},
@@ -51,6 +53,7 @@ pub struct AnalysisStatsCmd {
    pub path: PathBuf,
    pub load_output_dirs: bool,
    pub with_proc_macro: bool,
+    pub skip_inference: bool,
 }
 impl AnalysisStatsCmd {
@@ -128,6 +131,39 @@ impl AnalysisStatsCmd {
            shuffle(&mut rng, &mut funcs);
        }
+        if !self.skip_inference {
+            self.run_inference(&host, db, &vfs, &funcs, verbosity);
+        }
+        let total_span = analysis_sw.elapsed();
+        eprintln!("{:<20} {}", "Total:", total_span);
+        report_metric("total time", total_span.time.as_millis() as u64, "ms");
+        if let Some(instructions) = total_span.instructions {
+            report_metric("total instructions", instructions, "#instr");
+        }
+        if let Some(memory) = total_span.memory {
+            report_metric("total memory", memory.allocated.megabytes() as u64, "MB");
+        }
+        if env::var("RA_COUNT").is_ok() {
+            eprintln!("{}", profile::countme::get_all());
+        }
+        if self.memory_usage && verbosity.is_verbose() {
+            print_memory_usage(host, vfs);
+        }
+        Ok(())
+    }
+    fn run_inference(
+        &self,
+        host: &AnalysisHost,
+        db: &RootDatabase,
+        vfs: &Vfs,
+        funcs: &[Function],
+        verbosity: Verbosity,
+    ) {
        let mut bar = match verbosity {
            Verbosity::Quiet | Verbosity::Spammy => ProgressReport::hidden(),
            _ if self.parallel => ProgressReport::hidden(),
@@ -154,7 +190,7 @@ impl AnalysisStatsCmd {
        let mut num_exprs_unknown = 0;
        let mut num_exprs_partially_unknown = 0;
        let mut num_type_mismatches = 0;
-        for f in funcs {
+        for f in funcs.iter().copied() {
            let name = f.name(db);
            let full_name = f
                .module(db)
@@ -296,26 +332,6 @@ impl AnalysisStatsCmd {
        report_metric("type mismatches", num_type_mismatches, "#");
        eprintln!("{:<20} {}", "Inference:", inference_sw.elapsed());
-        let total_span = analysis_sw.elapsed();
-        eprintln!("{:<20} {}", "Total:", total_span);
-        report_metric("total time", total_span.time.as_millis() as u64, "ms");
-        if let Some(instructions) = total_span.instructions {
-            report_metric("total instructions", instructions, "#instr");
-        }
-        if let Some(memory) = total_span.memory {
-            report_metric("total memory", memory.allocated.megabytes() as u64, "MB");
-        }
-        if env::var("RA_COUNT").is_ok() {
-            eprintln!("{}", profile::countme::get_all());
-        }
-        if self.memory_usage && verbosity.is_verbose() {
-            print_memory_usage(host, vfs);
-        }
-        Ok(())
    }
    fn stop_watch(&self) -> StopWatch {
diff --git a/crates/rust-analyzer/src/handlers.rs b/crates/rust-analyzer/src/handlers.rs
index 53d29ddfc..4d10a2ead 100644
--- a/crates/rust-analyzer/src/handlers.rs
+++ b/crates/rust-analyzer/src/handlers.rs
@@ -927,19 +927,22 @@ pub(crate) fn handle_formatting(
    let captured_stderr = String::from_utf8(output.stderr).unwrap_or_default();
    if !output.status.success() {
-        match output.status.code() {
+        let rustfmt_not_installed =
-            Some(1) if !captured_stderr.contains("not installed") => {
+            captured_stderr.contains("not installed") || captured_stderr.contains("not available");
+        return match output.status.code() {
+            Some(1) if !rustfmt_not_installed => {
                // While `rustfmt` doesn't have a specific exit code for parse errors this is the
                // likely cause exiting with 1. Most Language Servers swallow parse errors on
                // formatting because otherwise an error is surfaced to the user on top of the
                // syntax error diagnostics they're already receiving. This is especially jarring
                // if they have format on save enabled.
                log::info!("rustfmt exited with status 1, assuming parse error and ignoring");
-                return Ok(None);
+                Ok(None)
            }
            _ => {
                // Something else happened - e.g. `rustfmt` is missing or caught a signal
-                return Err(LspError::new(
+                Err(LspError::new(
                    -32900,
                    format!(
                        r#"rustfmt exited with:
@@ -949,9 +952,9 @@ pub(crate) fn handle_formatting(
                        output.status, captured_stdout, captured_stderr,
                    ),
                )
-                .into());
+                .into())
            }
-        }
+        };
    }
    let (new_text, new_line_endings) = LineEndings::normalize(captured_stdout);
diff --git a/docs/dev/lsp-extensions.md b/docs/dev/lsp-extensions.md
index 8a6f9f06e..73be59a82 100644
--- a/docs/dev/lsp-extensions.md
+++ b/docs/dev/lsp-extensions.md
@@ -602,8 +602,7 @@ interface TestInfo {
 This request is sent from client to server to move item under cursor or selection in some direction.
-**Method:** `experimental/moveItemUp`
+**Method:** `experimental/moveItem`
-**Method:** `experimental/moveItemDown`
 **Request:** `MoveItemParams`
diff --git a/docs/dev/style.md b/docs/dev/style.md
index c594946be..48ce4b92a 100644
--- a/docs/dev/style.md
+++ b/docs/dev/style.md
@@ -842,7 +842,26 @@ Re-using originally single-purpose function often leads to bad coupling.
 ## Helper Variables
-Introduce helper variables freely, especially for multiline conditions.
+Introduce helper variables freely, especially for multiline conditions:
+```rust
+// GOOD
+let rustfmt_not_installed =
+    captured_stderr.contains("not installed") || captured_stderr.contains("not available");
+match output.status.code() {
+    Some(1) if !rustfmt_not_installed => Ok(None),
+    _ => Err(format_err!("rustfmt failed:\n{}", captured_stderr)),
+};
+// BAD
+match output.status.code() {
+    Some(1)
+        if !captured_stderr.contains("not installed")
+           && !captured_stderr.contains("not available") => Ok(None),
+    _ => Err(format_err!("rustfmt failed:\n{}", captured_stderr)),
+};
+```
 **Rationale:** like blocks, single-use variables are a cognitively cheap abstraction, as they have access to all the context.
 Extra variables help during debugging, they make it easy to print/view important intermediate results.
diff --git a/lib/arena/src/lib.rs b/lib/arena/src/lib.rs
index 230a50291..1720537cb 100644
--- a/lib/arena/src/lib.rs
+++ b/lib/arena/src/lib.rs
@@ -90,7 +90,7 @@ impl<T> Idx<T> {
 }
 /// Yet another index-based arena.
-#[derive(Clone, PartialEq, Eq)]
+#[derive(Clone, PartialEq, Eq, Hash)]
 pub struct Arena<T> {
    data: Vec<T>,
 }
@@ -194,6 +194,29 @@ impl<T> Arena<T> {
        self.data.iter().enumerate().map(|(idx, value)| (Idx::from_raw(RawIdx(idx as u32)), value))
    }
+    /// Returns an iterator over the arena’s mutable elements.
+    ///
+    /// ```
+    /// let mut arena = la_arena::Arena::new();
+    /// let idx1 = arena.alloc(20);
+    ///
+    /// assert_eq!(arena[idx1], 20);
+    ///
+    /// let mut iterator = arena.iter_mut();
+    /// *iterator.next().unwrap().1 = 10;
+    /// drop(iterator);
+    ///
+    /// assert_eq!(arena[idx1], 10);
+    /// ```
+    pub fn iter_mut(
+        &mut self,
+    ) -> impl Iterator<Item = (Idx<T>, &mut T)> + ExactSizeIterator + DoubleEndedIterator {
+        self.data
+            .iter_mut()
+            .enumerate()
+            .map(|(idx, value)| (Idx::from_raw(RawIdx(idx as u32)), value))
+    }
    /// Reallocates the arena to make it take up as little space as possible.
    pub fn shrink_to_fit(&mut self) {
        self.data.shrink_to_fit();