6 files changed, 638 insertions, 95 deletions

diff --git a/crates/hir/Cargo.toml b/crates/hir/Cargo.toml
index d4ea7327e..55e9c3f0c 100644
--- a/crates/hir/Cargo.toml
+++ b/crates/hir/Cargo.toml
@@ -15,6 +15,7 @@ rustc-hash = "1.1.0"
 either = "1.5.3"
 arrayvec = "0.5.1"
 itertools = "0.10.0"
+smallvec = "1.4.0"
 
 stdx = { path = "../stdx", version = "0.0.0" }
 syntax = { path = "../syntax", version = "0.0.0" }
diff --git a/crates/hir/src/display.rs b/crates/hir/src/display.rs
new file mode 100644
index 000000000..44cdcc296
--- /dev/null
+++ b/crates/hir/src/display.rs
@@ -0,0 +1,441 @@
+//! HirDisplay implementations for various hir types.
+use hir_def::{
+    adt::VariantData,
+    generics::{TypeParamProvenance, WherePredicate, WherePredicateTypeTarget},
+    type_ref::{TypeBound, TypeRef},
+    AdtId, GenericDefId,
+};
+use hir_ty::display::{
+    write_bounds_like_dyn_trait_with_prefix, write_visibility, HirDisplay, HirDisplayError,
+    HirFormatter,
+};
+use syntax::ast::{self, NameOwner};
+
+use crate::{
+    Const, ConstParam, Enum, Field, Function, HasVisibility, Module, Static, Struct, Substs, Trait,
+    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 qual.is_default {
+            write!(f, "default ")?;
+        }
+        if qual.is_const {
+            write!(f, "const ")?;
+        }
+        if qual.is_async {
+            write!(f, "async ")?;
+        }
+        if qual.is_unsafe {
+            write!(f, "unsafe ")?;
+        }
+        if let Some(abi) = &qual.abi {
+            // FIXME: String escape?
+            write!(f, "extern \"{}\" ", abi)?;
+        }
+        write!(f, "fn {}", data.name)?;
+
+        write_generic_params(GenericDefId::FunctionId(self.id), f)?;
+
+        write!(f, "(")?;
+
+        let write_self_param = |ty: &TypeRef, f: &mut HirFormatter| match ty {
+            TypeRef::Path(p) if p.is_self_type() => write!(f, "self"),
+            TypeRef::Reference(inner, lifetime, mut_) if matches!(&**inner,TypeRef::Path(p) if p.is_self_type()) =>
+            {
+                write!(f, "&")?;
+                if let Some(lifetime) = lifetime {
+                    write!(f, "{} ", lifetime.name)?;
+                }
+                if let hir_def::type_ref::Mutability::Mut = mut_ {
+                    write!(f, "mut ")?;
+                }
+                write!(f, "self")
+            }
+            _ => {
+                write!(f, "self: ")?;
+                ty.hir_fmt(f)
+            }
+        };
+
+        let mut first = true;
+        for (param, type_ref) in self.assoc_fn_params(f.db).into_iter().zip(&data.params) {
+            if !first {
+                write!(f, ", ")?;
+            } else {
+                first = false;
+                if data.has_self_param {
+                    write_self_param(type_ref, f)?;
+                    continue;
+                }
+            }
+            match param.pattern_source(f.db) {
+                Some(ast::Pat::IdentPat(p)) if p.name().is_some() => {
+                    write!(f, "{}: ", p.name().unwrap())?
+                }
+                _ => write!(f, "_: ")?,
+            }
+            // FIXME: Use resolved `param.ty` or raw `type_ref`?
+            // The former will ignore lifetime arguments currently.
+            type_ref.hir_fmt(f)?;
+        }
+        write!(f, ")")?;
+
+        // `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 {
+            &data.ret_type
+        } else {
+            match &data.ret_type {
+                TypeRef::ImplTrait(bounds) => match &bounds[0] {
+                    TypeBound::Path(path) => {
+                        path.segments().iter().last().unwrap().args_and_bindings.unwrap().bindings
+                            [0]
+                        .type_ref
+                        .as_ref()
+                        .unwrap()
+                    }
+                    _ => panic!("Async fn ret_type should be impl Future"),
+                },
+                _ => panic!("Async fn ret_type should be impl Future"),
+            }
+        };
+
+        match ret_type {
+            TypeRef::Tuple(tup) if tup.is_empty() => {}
+            ty => {
+                write!(f, " -> ")?;
+                ty.hir_fmt(f)?;
+            }
+        }
+
+        write_where_clause(GenericDefId::FunctionId(self.id), f)?;
+
+        Ok(())
+    }
+}
+
+impl HirDisplay for Struct {
+    fn hir_fmt(&self, f: &mut HirFormatter) -> Result<(), HirDisplayError> {
+        write_visibility(self.module(f.db).id, self.visibility(f.db), f)?;
+        write!(f, "struct ")?;
+        write!(f, "{}", self.name(f.db))?;
+        let def_id = GenericDefId::AdtId(AdtId::StructId(self.id));
+        write_generic_params(def_id, f)?;
+        write_where_clause(def_id, f)?;
+        Ok(())
+    }
+}
+
+impl HirDisplay for Enum {
+    fn hir_fmt(&self, f: &mut HirFormatter) -> Result<(), HirDisplayError> {
+        write_visibility(self.module(f.db).id, self.visibility(f.db), f)?;
+        write!(f, "enum ")?;
+        write!(f, "{}", self.name(f.db))?;
+        let def_id = GenericDefId::AdtId(AdtId::EnumId(self.id));
+        write_generic_params(def_id, f)?;
+        write_where_clause(def_id, f)?;
+        Ok(())
+    }
+}
+
+impl HirDisplay for Union {
+    fn hir_fmt(&self, f: &mut HirFormatter) -> Result<(), HirDisplayError> {
+        write_visibility(self.module(f.db).id, self.visibility(f.db), f)?;
+        write!(f, "union ")?;
+        write!(f, "{}", self.name(f.db))?;
+        let def_id = GenericDefId::AdtId(AdtId::UnionId(self.id));
+        write_generic_params(def_id, f)?;
+        write_where_clause(def_id, f)?;
+        Ok(())
+    }
+}
+
+impl HirDisplay for Field {
+    fn hir_fmt(&self, f: &mut HirFormatter) -> Result<(), HirDisplayError> {
+        write_visibility(self.parent.module(f.db).id, self.visibility(f.db), f)?;
+        write!(f, "{}: ", self.name(f.db))?;
+        self.signature_ty(f.db).hir_fmt(f)
+    }
+}
+
+impl HirDisplay for Variant {
+    fn hir_fmt(&self, f: &mut HirFormatter) -> Result<(), HirDisplayError> {
+        write!(f, "{}", self.name(f.db))?;
+        let data = self.variant_data(f.db);
+        match &*data {
+            VariantData::Unit => {}
+            VariantData::Tuple(fields) => {
+                write!(f, "(")?;
+                let mut first = true;
+                for (_, field) in fields.iter() {
+                    if first {
+                        first = false;
+                    } else {
+                        write!(f, ", ")?;
+                    }
+                    // Enum variant fields must be pub.
+                    field.type_ref.hir_fmt(f)?;
+                }
+                write!(f, ")")?;
+            }
+            VariantData::Record(fields) => {
+                write!(f, " {{")?;
+                let mut first = true;
+                for (_, field) in fields.iter() {
+                    if first {
+                        first = false;
+                        write!(f, " ")?;
+                    } else {
+                        write!(f, ", ")?;
+                    }
+                    // Enum variant fields must be pub.
+                    write!(f, "{}: ", field.name)?;
+                    field.type_ref.hir_fmt(f)?;
+                }
+                write!(f, " }}")?;
+            }
+        }
+        Ok(())
+    }
+}
+
+impl HirDisplay for Type {
+    fn hir_fmt(&self, f: &mut HirFormatter) -> Result<(), HirDisplayError> {
+        self.ty.value.hir_fmt(f)
+    }
+}
+
+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 = Substs::type_params(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)?;
+        }
+        Ok(())
+    }
+}
+
+impl HirDisplay for ConstParam {
+    fn hir_fmt(&self, f: &mut HirFormatter) -> Result<(), HirDisplayError> {
+        write!(f, "const {}: ", self.name(f.db))?;
+        self.ty(f.db).hir_fmt(f)
+    }
+}
+
+fn write_generic_params(def: GenericDefId, f: &mut HirFormatter) -> Result<(), HirDisplayError> {
+    let params = f.db.generic_params(def);
+    if params.lifetimes.is_empty()
+        && params.consts.is_empty()
+        && params
+            .types
+            .iter()
+            .all(|(_, param)| !matches!(param.provenance, TypeParamProvenance::TypeParamList))
+    {
+        return Ok(());
+    }
+    write!(f, "<")?;
+
+    let mut first = true;
+    let mut delim = |f: &mut HirFormatter| {
+        if first {
+            first = false;
+            Ok(())
+        } else {
+            write!(f, ", ")
+        }
+    };
+    for (_, lifetime) in params.lifetimes.iter() {
+        delim(f)?;
+        write!(f, "{}", lifetime.name)?;
+    }
+    for (_, ty) in params.types.iter() {
+        if ty.provenance != TypeParamProvenance::TypeParamList {
+            continue;
+        }
+        if let Some(name) = &ty.name {
+            delim(f)?;
+            write!(f, "{}", name)?;
+            if let Some(default) = &ty.default {
+                write!(f, " = ")?;
+                default.hir_fmt(f)?;
+            }
+        }
+    }
+    for (_, konst) in params.consts.iter() {
+        delim(f)?;
+        write!(f, "const {}: ", konst.name)?;
+        konst.ty.hir_fmt(f)?;
+    }
+
+    write!(f, ">")?;
+    Ok(())
+}
+
+fn write_where_clause(def: GenericDefId, f: &mut HirFormatter) -> Result<(), HirDisplayError> {
+    let params = f.db.generic_params(def);
+    if params.where_predicates.is_empty() {
+        return Ok(());
+    }
+
+    let write_target = |target: &WherePredicateTypeTarget, f: &mut HirFormatter| match target {
+        WherePredicateTypeTarget::TypeRef(ty) => ty.hir_fmt(f),
+        WherePredicateTypeTarget::TypeParam(id) => match &params.types[*id].name {
+            Some(name) => write!(f, "{}", name),
+            None => write!(f, "{{unnamed}}"),
+        },
+    };
+
+    write!(f, "\nwhere")?;
+
+    for (pred_idx, pred) in params.where_predicates.iter().enumerate() {
+        let prev_pred =
+            if pred_idx == 0 { None } else { Some(&params.where_predicates[pred_idx - 1]) };
+
+        let new_predicate = |f: &mut HirFormatter| {
+            write!(f, "{}", if pred_idx == 0 { "\n    " } else { ",\n    " })
+        };
+
+        match pred {
+            WherePredicate::TypeBound { target, bound } => {
+                if matches!(prev_pred, Some(WherePredicate::TypeBound { target: target_, .. }) if target_ == target)
+                {
+                    write!(f, " + ")?;
+                } else {
+                    new_predicate(f)?;
+                    write_target(target, f)?;
+                    write!(f, ": ")?;
+                }
+                bound.hir_fmt(f)?;
+            }
+            WherePredicate::Lifetime { target, bound } => {
+                if matches!(prev_pred, Some(WherePredicate::Lifetime { target: target_, .. }) if target_ == target)
+                {
+                    write!(f, " + {}", bound.name)?;
+                } else {
+                    new_predicate(f)?;
+                    write!(f, "{}: {}", target.name, bound.name)?;
+                }
+            }
+            WherePredicate::ForLifetime { lifetimes, target, bound } => {
+                if matches!(
+                    prev_pred,
+                    Some(WherePredicate::ForLifetime { lifetimes: lifetimes_, target: target_, .. })
+                    if lifetimes_ == lifetimes && target_ == target,
+                ) {
+                    write!(f, " + ")?;
+                } else {
+                    new_predicate(f)?;
+                    write!(f, "for<")?;
+                    for (idx, lifetime) in lifetimes.iter().enumerate() {
+                        if idx != 0 {
+                            write!(f, ", ")?;
+                        }
+                        write!(f, "{}", lifetime)?;
+                    }
+                    write!(f, "> ")?;
+                    write_target(target, f)?;
+                    write!(f, ": ")?;
+                }
+                bound.hir_fmt(f)?;
+            }
+        }
+    }
+
+    // End of final predicate. There must be at least one predicate here.
+    write!(f, ",")?;
+
+    Ok(())
+}
+
+impl HirDisplay for Const {
+    fn hir_fmt(&self, f: &mut HirFormatter) -> Result<(), HirDisplayError> {
+        write_visibility(self.module(f.db).id, self.visibility(f.db), f)?;
+        let data = f.db.const_data(self.id);
+        write!(f, "const ")?;
+        match &data.name {
+            Some(name) => write!(f, "{}: ", name)?,
+            None => write!(f, "_: ")?,
+        }
+        data.type_ref.hir_fmt(f)?;
+        Ok(())
+    }
+}
+
+impl HirDisplay for Static {
+    fn hir_fmt(&self, f: &mut HirFormatter) -> Result<(), HirDisplayError> {
+        write_visibility(self.module(f.db).id, self.visibility(f.db), f)?;
+        let data = f.db.static_data(self.id);
+        write!(f, "static ")?;
+        if data.mutable {
+            write!(f, "mut ")?;
+        }
+        match &data.name {
+            Some(name) => write!(f, "{}: ", name)?,
+            None => write!(f, "_: ")?,
+        }
+        data.type_ref.hir_fmt(f)?;
+        Ok(())
+    }
+}
+
+impl HirDisplay for Trait {
+    fn hir_fmt(&self, f: &mut HirFormatter) -> Result<(), HirDisplayError> {
+        write_visibility(self.module(f.db).id, self.visibility(f.db), f)?;
+        let data = f.db.trait_data(self.id);
+        if data.is_unsafe {
+            write!(f, "unsafe ")?;
+        }
+        if data.is_auto {
+            write!(f, "auto ")?;
+        }
+        write!(f, "trait {}", data.name)?;
+        let def_id = GenericDefId::TraitId(self.id);
+        write_generic_params(def_id, f)?;
+        if !data.bounds.is_empty() {
+            write!(f, ": ")?;
+            f.write_joined(&*data.bounds, " + ")?;
+        }
+        write_where_clause(def_id, f)?;
+        Ok(())
+    }
+}
+
+impl HirDisplay for TypeAlias {
+    fn hir_fmt(&self, f: &mut HirFormatter) -> Result<(), HirDisplayError> {
+        write_visibility(self.module(f.db).id, self.visibility(f.db), f)?;
+        let data = f.db.type_alias_data(self.id);
+        write!(f, "type {}", data.name)?;
+        if !data.bounds.is_empty() {
+            write!(f, ": ")?;
+            f.write_joined(&data.bounds, " + ")?;
+        }
+        if let Some(ty) = &data.type_ref {
+            write!(f, " = ")?;
+            ty.hir_fmt(f)?;
+        }
+        Ok(())
+    }
+}
+
+impl HirDisplay for Module {
+    fn hir_fmt(&self, f: &mut HirFormatter) -> Result<(), HirDisplayError> {
+        // FIXME: Module doesn't have visibility saved in data.
+        match self.name(f.db) {
+            Some(name) => write!(f, "mod {}", name),
+            None if self.crate_root(f.db) == *self => match self.krate().display_name(f.db) {
+                Some(name) => write!(f, "extern crate {}", name),
+                None => write!(f, "extern crate {{unknown}}"),
+            },
+            None => write!(f, "mod {{unnamed}}"),
+        }
+    }
+}
diff --git a/crates/hir/src/lib.rs b/crates/hir/src/lib.rs
index 8d082994a..f0bc2c7b9 100644
--- a/crates/hir/src/lib.rs
+++ b/crates/hir/src/lib.rs
@@ -29,6 +29,8 @@ mod has_source;
 pub mod diagnostics;
 pub mod db;
 
+mod display;
+
 use std::{iter, sync::Arc};
 
 use arrayvec::ArrayVec;
@@ -50,12 +52,13 @@ use hir_def::{
 use hir_expand::{diagnostics::DiagnosticSink, name::name, MacroDefKind};
 use hir_ty::{
     autoderef,
-    display::{write_bounds_like_dyn_trait_with_prefix, HirDisplayError, HirFormatter},
-    method_resolution,
+    method_resolution::{self, TyFingerprint},
+    primitive::UintTy,
+    to_assoc_type_id,
     traits::{FnTrait, Solution, SolutionVariables},
     AliasTy, BoundVar, CallableDefId, CallableSig, Canonical, DebruijnIndex, GenericPredicate,
-    InEnvironment, Obligation, ProjectionPredicate, ProjectionTy, Scalar, Substs, TraitEnvironment,
-    Ty, TyDefId, TyVariableKind,
+    InEnvironment, Interner, Obligation, ProjectionPredicate, ProjectionTy, Scalar, Substs, Ty,
+    TyDefId, TyKind, TyVariableKind,
 };
 use rustc_hash::FxHashSet;
 use stdx::{format_to, impl_from};
@@ -266,8 +269,7 @@ impl ModuleDef {
     }
 
     pub fn canonical_path(&self, db: &dyn HirDatabase) -> Option<String> {
-        let mut segments = Vec::new();
-        segments.push(self.name(db)?.to_string());
+        let mut segments = vec![self.name(db)?.to_string()];
         for m in self.module(db)?.path_to_root(db) {
             segments.extend(m.name(db).map(|it| it.to_string()))
         }
@@ -571,6 +573,12 @@ impl Struct {
     }
 }
 
+impl HasVisibility for Struct {
+    fn visibility(&self, db: &dyn HirDatabase) -> Visibility {
+        db.struct_data(self.id).visibility.resolve(db.upcast(), &self.id.resolver(db.upcast()))
+    }
+}
+
 #[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
 pub struct Union {
     pub(crate) id: UnionId,
@@ -603,6 +611,12 @@ impl Union {
     }
 }
 
+impl HasVisibility for Union {
+    fn visibility(&self, db: &dyn HirDatabase) -> Visibility {
+        db.union_data(self.id).visibility.resolve(db.upcast(), &self.id.resolver(db.upcast()))
+    }
+}
+
 #[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
 pub struct Enum {
     pub(crate) id: EnumId,
@@ -630,6 +644,12 @@ impl Enum {
     }
 }
 
+impl HasVisibility for Enum {
+    fn visibility(&self, db: &dyn HirDatabase) -> Visibility {
+        db.enum_data(self.id).visibility.resolve(db.upcast(), &self.id.resolver(db.upcast()))
+    }
+}
+
 #[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
 pub struct Variant {
     pub(crate) parent: Enum,
@@ -677,7 +697,7 @@ impl_from!(Struct, Union, Enum for Adt);
 impl Adt {
     pub fn has_non_default_type_params(self, db: &dyn HirDatabase) -> bool {
         let subst = db.generic_defaults(self.into());
-        subst.iter().any(|ty| &ty.value == &Ty::Unknown)
+        subst.iter().any(|ty| ty.value.is_unknown())
     }
 
     /// Turns this ADT into a type. Any type parameters of the ADT will be
@@ -696,8 +716,8 @@ impl Adt {
         }
     }
 
-    pub fn krate(self, db: &dyn HirDatabase) -> Option<Crate> {
-        Some(self.module(db).krate())
+    pub fn krate(self, db: &dyn HirDatabase) -> Crate {
+        self.module(db).krate()
     }
 
     pub fn name(self, db: &dyn HirDatabase) -> Name {
@@ -802,7 +822,7 @@ impl Function {
         let krate = self.id.lookup(db.upcast()).container.module(db.upcast()).krate();
         let ret_type = &db.function_data(self.id).ret_type;
         let ctx = hir_ty::TyLoweringContext::new(db, &resolver);
-        let ty = Ty::from_hir_ext(&ctx, ret_type).0;
+        let ty = ctx.lower_ty(ret_type);
         Type::new_with_resolver_inner(db, krate, &resolver, ty)
     }
 
@@ -817,19 +837,20 @@ impl Function {
         let resolver = self.id.resolver(db.upcast());
         let krate = self.id.lookup(db.upcast()).container.module(db.upcast()).krate();
         let ctx = hir_ty::TyLoweringContext::new(db, &resolver);
-        let environment = TraitEnvironment::lower(db, &resolver);
+        let environment = db.trait_environment(self.id.into());
         db.function_data(self.id)
             .params
             .iter()
-            .map(|type_ref| {
+            .enumerate()
+            .map(|(idx, type_ref)| {
                 let ty = Type {
                     krate,
                     ty: InEnvironment {
-                        value: Ty::from_hir_ext(&ctx, type_ref).0,
+                        value: ctx.lower_ty(type_ref),
                         environment: environment.clone(),
                     },
                 };
-                Param { ty }
+                Param { func: self, ty, idx }
             })
             .collect()
     }
@@ -843,7 +864,7 @@ impl Function {
     }
 
     pub fn is_unsafe(self, db: &dyn HirDatabase) -> bool {
-        db.function_data(self.id).is_unsafe
+        db.function_data(self.id).qualifier.is_unsafe
     }
 
     pub fn diagnostics(self, db: &dyn HirDatabase, sink: &mut DiagnosticSink) {
@@ -892,6 +913,9 @@ impl From<hir_ty::Mutability> for Access {
 
 #[derive(Debug)]
 pub struct Param {
+    func: Function,
+    /// The index in parameter list, including self parameter.
+    idx: usize,
     ty: Type,
 }
 
@@ -899,6 +923,15 @@ impl Param {
     pub fn ty(&self) -> &Type {
         &self.ty
     }
+
+    pub fn pattern_source(&self, db: &dyn HirDatabase) -> Option<ast::Pat> {
+        let params = self.func.source(db)?.value.param_list()?;
+        if params.self_param().is_some() {
+            params.params().nth(self.idx.checked_sub(1)?)?.pat()
+        } else {
+            params.params().nth(self.idx)?.pat()
+        }
+    }
 }
 
 #[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
@@ -956,6 +989,10 @@ impl Const {
     pub fn name(self, db: &dyn HirDatabase) -> Option<Name> {
         db.const_data(self.id).name.clone()
     }
+
+    pub fn type_ref(self, db: &dyn HirDatabase) -> TypeRef {
+        db.const_data(self.id).type_ref.clone()
+    }
 }
 
 impl HasVisibility for Const {
@@ -989,6 +1026,12 @@ impl Static {
     }
 }
 
+impl HasVisibility for Static {
+    fn visibility(&self, db: &dyn HirDatabase) -> Visibility {
+        db.static_data(self.id).visibility.resolve(db.upcast(), &self.id.resolver(db.upcast()))
+    }
+}
+
 #[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
 pub struct Trait {
     pub(crate) id: TraitId,
@@ -1008,7 +1051,13 @@ impl Trait {
     }
 
     pub fn is_auto(self, db: &dyn HirDatabase) -> bool {
-        db.trait_data(self.id).auto
+        db.trait_data(self.id).is_auto
+    }
+}
+
+impl HasVisibility for Trait {
+    fn visibility(&self, db: &dyn HirDatabase) -> Visibility {
+        db.trait_data(self.id).visibility.resolve(db.upcast(), &self.id.resolver(db.upcast()))
     }
 }
 
@@ -1020,15 +1069,15 @@ pub struct TypeAlias {
 impl TypeAlias {
     pub fn has_non_default_type_params(self, db: &dyn HirDatabase) -> bool {
         let subst = db.generic_defaults(self.id.into());
-        subst.iter().any(|ty| &ty.value == &Ty::Unknown)
+        subst.iter().any(|ty| ty.value.is_unknown())
     }
 
     pub fn module(self, db: &dyn HirDatabase) -> Module {
         Module { id: self.id.lookup(db.upcast()).module(db.upcast()) }
     }
 
-    pub fn krate(self, db: &dyn HirDatabase) -> Option<Crate> {
-        Some(self.module(db).krate())
+    pub fn krate(self, db: &dyn HirDatabase) -> Crate {
+        self.module(db).krate()
     }
 
     pub fn type_ref(self, db: &dyn HirDatabase) -> Option<TypeRef> {
@@ -1392,7 +1441,7 @@ impl TypeParam {
     pub fn ty(self, db: &dyn HirDatabase) -> Type {
         let resolver = self.id.parent.resolver(db.upcast());
         let krate = self.id.parent.module(db.upcast()).krate();
-        let ty = Ty::Placeholder(self.id);
+        let ty = TyKind::Placeholder(hir_ty::to_placeholder_idx(db, self.id)).intern(&Interner);
         Type::new_with_resolver_inner(db, krate, &resolver, ty)
     }
 
@@ -1420,19 +1469,6 @@ impl TypeParam {
     }
 }
 
-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 = Substs::type_params(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)?;
-        }
-        Ok(())
-    }
-}
-
 #[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
 pub struct LifetimeParam {
     pub(crate) id: LifetimeParamId,
@@ -1491,9 +1527,44 @@ impl Impl {
 
         inherent.all_impls().chain(trait_.all_impls()).map(Self::from).collect()
     }
-    pub fn for_trait(db: &dyn HirDatabase, krate: Crate, trait_: Trait) -> Vec<Impl> {
-        let impls = db.trait_impls_in_crate(krate.id);
-        impls.for_trait(trait_.id).map(Self::from).collect()
+
+    pub fn all_for_type(db: &dyn HirDatabase, Type { krate, ty }: Type) -> Vec<Impl> {
+        let def_crates = match ty.value.def_crates(db, krate) {
+            Some(def_crates) => def_crates,
+            None => return Vec::new(),
+        };
+
+        let filter = |impl_def: &Impl| {
+            let target_ty = impl_def.target_ty(db);
+            let rref = target_ty.remove_ref();
+            ty.value.equals_ctor(rref.as_ref().map_or(&target_ty.ty.value, |it| &it.ty.value))
+        };
+
+        let mut all = Vec::new();
+        def_crates.into_iter().for_each(|id| {
+            all.extend(db.inherent_impls_in_crate(id).all_impls().map(Self::from).filter(filter))
+        });
+        let fp = TyFingerprint::for_impl(&ty.value);
+        for id in db.crate_graph().iter() {
+            match fp {
+                Some(fp) => all.extend(
+                    db.trait_impls_in_crate(id).for_self_ty(fp).map(Self::from).filter(filter),
+                ),
+                None => all
+                    .extend(db.trait_impls_in_crate(id).all_impls().map(Self::from).filter(filter)),
+            }
+        }
+        all
+    }
+
+    pub fn all_for_trait(db: &dyn HirDatabase, trait_: Trait) -> Vec<Impl> {
+        let krate = trait_.module(db).krate();
+        let mut all = Vec::new();
+        for Crate { id } in krate.reverse_dependencies(db).into_iter().chain(Some(krate)) {
+            let impls = db.trait_impls_in_crate(id);
+            all.extend(impls.for_trait(trait_.id).map(Self::from))
+        }
+        all
     }
 
     // FIXME: the return type is wrong. This should be a hir version of
@@ -1507,7 +1578,7 @@ impl Impl {
         let resolver = self.id.resolver(db.upcast());
         let krate = self.id.lookup(db.upcast()).container.krate();
         let ctx = hir_ty::TyLoweringContext::new(db, &resolver);
-        let ty = Ty::from_hir(&ctx, &impl_data.target_type);
+        let ty = ctx.lower_ty(&impl_data.target_type);
         Type::new_with_resolver_inner(db, krate, &resolver, ty)
     }
 
@@ -1571,13 +1642,15 @@ impl Type {
         resolver: &Resolver,
         ty: Ty,
     ) -> Type {
-        let environment = TraitEnvironment::lower(db, &resolver);
+        let environment =
+            resolver.generic_def().map_or_else(Default::default, |d| db.trait_environment(d));
         Type { krate, ty: InEnvironment { value: ty, environment } }
     }
 
     fn new(db: &dyn HirDatabase, krate: CrateId, lexical_env: impl HasResolver, ty: Ty) -> Type {
         let resolver = lexical_env.resolver(db.upcast());
-        let environment = TraitEnvironment::lower(db, &resolver);
+        let environment =
+            resolver.generic_def().map_or_else(Default::default, |d| db.trait_environment(d));
         Type { krate, ty: InEnvironment { value: ty, environment } }
     }
 
@@ -1592,25 +1665,29 @@ impl Type {
     }
 
     pub fn is_unit(&self) -> bool {
-        matches!(self.ty.value, Ty::Tuple(0, ..))
+        matches!(self.ty.value.interned(&Interner), TyKind::Tuple(0, ..))
     }
     pub fn is_bool(&self) -> bool {
-        matches!(self.ty.value, Ty::Scalar(Scalar::Bool))
+        matches!(self.ty.value.interned(&Interner), TyKind::Scalar(Scalar::Bool))
     }
 
     pub fn is_mutable_reference(&self) -> bool {
-        matches!(self.ty.value, Ty::Ref(hir_ty::Mutability::Mut, ..))
+        matches!(self.ty.value.interned(&Interner), TyKind::Ref(hir_ty::Mutability::Mut, ..))
+    }
+
+    pub fn is_usize(&self) -> bool {
+        matches!(self.ty.value.interned(&Interner), TyKind::Scalar(Scalar::Uint(UintTy::Usize)))
     }
 
     pub fn remove_ref(&self) -> Option<Type> {
-        match &self.ty.value {
-            Ty::Ref(.., substs) => Some(self.derived(substs[0].clone())),
+        match &self.ty.value.interned(&Interner) {
+            TyKind::Ref(.., ty) => Some(self.derived(ty.clone())),
             _ => None,
         }
     }
 
     pub fn is_unknown(&self) -> bool {
-        matches!(self.ty.value, Ty::Unknown)
+        self.ty.value.is_unknown()
     }
 
     /// Checks that particular type `ty` implements `std::future::Future`.
@@ -1691,8 +1768,11 @@ impl Type {
             .fill(args.iter().map(|t| t.ty.value.clone()))
             .build();
         let predicate = ProjectionPredicate {
-            projection_ty: ProjectionTy { associated_ty: alias.id, parameters: subst },
-            ty: Ty::BoundVar(BoundVar::new(DebruijnIndex::INNERMOST, 0)),
+            projection_ty: ProjectionTy {
+                associated_ty_id: to_assoc_type_id(alias.id),
+                substitution: subst,
+            },
+            ty: TyKind::BoundVar(BoundVar::new(DebruijnIndex::INNERMOST, 0)).intern(&Interner),
         };
         let goal = Canonical {
             value: InEnvironment::new(
@@ -1720,26 +1800,23 @@ impl Type {
     }
 
     pub fn as_callable(&self, db: &dyn HirDatabase) -> Option<Callable> {
-        let def = match self.ty.value {
-            Ty::FnDef(def, _) => Some(def),
-            _ => None,
-        };
+        let def = self.ty.value.callable_def(db);
 
         let sig = self.ty.value.callable_sig(db)?;
         Some(Callable { ty: self.clone(), sig, def, is_bound_method: false })
     }
 
     pub fn is_closure(&self) -> bool {
-        matches!(&self.ty.value, Ty::Closure { .. })
+        matches!(&self.ty.value.interned(&Interner), TyKind::Closure { .. })
     }
 
     pub fn is_fn(&self) -> bool {
-        matches!(&self.ty.value, Ty::FnDef(..) | Ty::Function { .. })
+        matches!(&self.ty.value.interned(&Interner), TyKind::FnDef(..) | TyKind::Function { .. })
     }
 
     pub fn is_packed(&self, db: &dyn HirDatabase) -> bool {
-        let adt_id = match self.ty.value {
-            Ty::Adt(hir_ty::AdtId(adt_id), ..) => adt_id,
+        let adt_id = match self.ty.value.interned(&Interner) {
+            &TyKind::Adt(hir_ty::AdtId(adt_id), ..) => adt_id,
             _ => return false,
         };
 
@@ -1751,24 +1828,45 @@ impl Type {
     }
 
     pub fn is_raw_ptr(&self) -> bool {
-        matches!(&self.ty.value, Ty::Raw(..))
+        matches!(&self.ty.value.interned(&Interner), TyKind::Raw(..))
     }
 
     pub fn contains_unknown(&self) -> bool {
         return go(&self.ty.value);
 
         fn go(ty: &Ty) -> bool {
-            match ty {
-                Ty::Unknown => true,
-                _ => ty.substs().map_or(false, |substs| substs.iter().any(go)),
+            match ty.interned(&Interner) {
+                TyKind::Unknown => true,
+
+                TyKind::Adt(_, substs)
+                | TyKind::AssociatedType(_, substs)
+                | TyKind::Tuple(_, substs)
+                | TyKind::OpaqueType(_, substs)
+                | TyKind::FnDef(_, substs)
+                | TyKind::Closure(_, substs) => substs.iter().any(go),
+
+                TyKind::Array(ty) | TyKind::Slice(ty) | TyKind::Raw(_, ty) | TyKind::Ref(_, ty) => {
+                    go(ty)
+                }
+
+                TyKind::Scalar(_)
+                | TyKind::Str
+                | TyKind::Never
+                | TyKind::Placeholder(_)
+                | TyKind::BoundVar(_)
+                | TyKind::InferenceVar(_, _)
+                | TyKind::Dyn(_)
+                | TyKind::Function(_)
+                | TyKind::Alias(_)
+                | TyKind::ForeignType(_) => false,
             }
         }
     }
 
     pub fn fields(&self, db: &dyn HirDatabase) -> Vec<(Field, Type)> {
-        let (variant_id, substs) = match self.ty.value {
-            Ty::Adt(hir_ty::AdtId(AdtId::StructId(s)), ref substs) => (s.into(), substs),
-            Ty::Adt(hir_ty::AdtId(AdtId::UnionId(u)), ref substs) => (u.into(), substs),
+        let (variant_id, substs) = match self.ty.value.interned(&Interner) {
+            &TyKind::Adt(hir_ty::AdtId(AdtId::StructId(s)), ref substs) => (s.into(), substs),
+            &TyKind::Adt(hir_ty::AdtId(AdtId::UnionId(u)), ref substs) => (u.into(), substs),
             _ => return Vec::new(),
         };
 
@@ -1783,7 +1881,7 @@ impl Type {
     }
 
     pub fn tuple_fields(&self, _db: &dyn HirDatabase) -> Vec<Type> {
-        if let Ty::Tuple(_, substs) = &self.ty.value {
+        if let TyKind::Tuple(_, substs) = &self.ty.value.interned(&Interner) {
             substs.iter().map(|ty| self.derived(ty.clone())).collect()
         } else {
             Vec::new()
@@ -1918,12 +2016,6 @@ impl Type {
         self.ty.value.associated_type_parent_trait(db).map(Into::into)
     }
 
-    // FIXME: provide required accessors such that it becomes implementable from outside.
-    pub fn is_equal_for_find_impls(&self, other: &Type) -> bool {
-        let rref = other.remove_ref();
-        self.ty.value.equals_ctor(rref.as_ref().map_or(&other.ty.value, |it| &it.ty.value))
-    }
-
     fn derived(&self, ty: Ty) -> Type {
         Type {
             krate: self.krate,
@@ -1965,36 +2057,40 @@ impl Type {
 
         fn walk_type(db: &dyn HirDatabase, type_: &Type, cb: &mut impl FnMut(Type)) {
             let ty = type_.ty.value.strip_references();
-            match ty {
-                Ty::Adt(..) => {
+            match ty.interned(&Interner) {
+                TyKind::Adt(..) => {
                     cb(type_.derived(ty.clone()));
                 }
-                Ty::AssociatedType(..) => {
+                TyKind::AssociatedType(..) => {
                     if let Some(_) = ty.associated_type_parent_trait(db) {
                         cb(type_.derived(ty.clone()));
                     }
                 }
-                Ty::OpaqueType(..) => {
+                TyKind::OpaqueType(..) => {
                     if let Some(bounds) = ty.impl_trait_bounds(db) {
                         walk_bounds(db, &type_.derived(ty.clone()), &bounds, cb);
                     }
                 }
-                Ty::Alias(AliasTy::Opaque(opaque_ty)) => {
+                TyKind::Alias(AliasTy::Opaque(opaque_ty)) => {
                     if let Some(bounds) = ty.impl_trait_bounds(db) {
                         walk_bounds(db, &type_.derived(ty.clone()), &bounds, cb);
                     }
 
-                    walk_substs(db, type_, &opaque_ty.parameters, cb);
+                    walk_substs(db, type_, &opaque_ty.substitution, cb);
                 }
-                Ty::Placeholder(_) => {
+                TyKind::Placeholder(_) => {
                     if let Some(bounds) = ty.impl_trait_bounds(db) {
                         walk_bounds(db, &type_.derived(ty.clone()), &bounds, cb);
                     }
                 }
-                Ty::Dyn(bounds) => {
+                TyKind::Dyn(bounds) => {
                     walk_bounds(db, &type_.derived(ty.clone()), bounds.as_ref(), cb);
                 }
 
+                TyKind::Ref(_, ty) | TyKind::Raw(_, ty) | TyKind::Array(ty) | TyKind::Slice(ty) => {
+                    walk_type(db, &type_.derived(ty.clone()), cb);
+                }
+
                 _ => {}
             }
             if let Some(substs) = ty.substs() {
@@ -2006,12 +2102,6 @@ impl Type {
     }
 }
 
-impl HirDisplay for Type {
-    fn hir_fmt(&self, f: &mut HirFormatter) -> Result<(), HirDisplayError> {
-        self.ty.value.hir_fmt(f)
-    }
-}
-
 // FIXME: closures
 #[derive(Debug)]
 pub struct Callable {
diff --git a/crates/hir/src/semantics.rs b/crates/hir/src/semantics.rs
index 945638cc5..519339c0c 100644
--- a/crates/hir/src/semantics.rs
+++ b/crates/hir/src/semantics.rs
@@ -259,6 +259,10 @@ impl<'db, DB: HirDatabase> Semantics<'db, DB> {
     }
 
     pub fn to_module_def(&self, file: FileId) -> Option<Module> {
+        self.imp.to_module_def(file).next()
+    }
+
+    pub fn to_module_defs(&self, file: FileId) -> impl Iterator<Item = Module> {
         self.imp.to_module_def(file)
     }
 
@@ -537,8 +541,8 @@ impl<'db> SemanticsImpl<'db> {
         f(&mut ctx)
     }
 
-    fn to_module_def(&self, file: FileId) -> Option<Module> {
-        self.with_ctx(|ctx| ctx.file_to_def(file)).map(Module::from)
+    fn to_module_def(&self, file: FileId) -> impl Iterator<Item = Module> {
+        self.with_ctx(|ctx| ctx.file_to_def(file)).into_iter().map(Module::from)
     }
 
     fn scope(&self, node: &SyntaxNode) -> SemanticsScope<'db> {
diff --git a/crates/hir/src/semantics/source_to_def.rs b/crates/hir/src/semantics/source_to_def.rs
index 6c612ee86..e9d820140 100644
--- a/crates/hir/src/semantics/source_to_def.rs
+++ b/crates/hir/src/semantics/source_to_def.rs
@@ -12,6 +12,7 @@ use hir_def::{
 };
 use hir_expand::{name::AsName, AstId, MacroDefKind};
 use rustc_hash::FxHashMap;
+use smallvec::SmallVec;
 use stdx::impl_from;
 use syntax::{
     ast::{self, NameOwner},
@@ -28,14 +29,19 @@ pub(super) struct SourceToDefCtx<'a, 'b> {
 }
 
 impl SourceToDefCtx<'_, '_> {
-    pub(super) fn file_to_def(&mut self, file: FileId) -> Option<ModuleId> {
+    pub(super) fn file_to_def(&mut self, file: FileId) -> SmallVec<[ModuleId; 1]> {
         let _p = profile::span("SourceBinder::to_module_def");
-        self.db.relevant_crates(file).iter().find_map(|&crate_id| {
+        let mut mods = SmallVec::new();
+        for &crate_id in self.db.relevant_crates(file).iter() {
             // FIXME: inner items
             let crate_def_map = self.db.crate_def_map(crate_id);
-            let local_id = crate_def_map.modules_for_file(file).next()?;
-            Some(crate_def_map.module_id(local_id))
-        })
+            mods.extend(
+                crate_def_map
+                    .modules_for_file(file)
+                    .map(|local_id| crate_def_map.module_id(local_id)),
+            )
+        }
+        mods
     }
 
     pub(super) fn module_to_def(&mut self, src: InFile<ast::Module>) -> Option<ModuleId> {
@@ -55,7 +61,7 @@ impl SourceToDefCtx<'_, '_> {
             Some(parent_declaration) => self.module_to_def(parent_declaration),
             None => {
                 let file_id = src.file_id.original_file(self.db.upcast());
-                self.file_to_def(file_id)
+                self.file_to_def(file_id).get(0).copied()
             }
         }?;
 
@@ -185,7 +191,7 @@ impl SourceToDefCtx<'_, '_> {
     ) -> Option<MacroDefId> {
         let kind = MacroDefKind::Declarative;
         let file_id = src.file_id.original_file(self.db.upcast());
-        let krate = self.file_to_def(file_id)?.krate();
+        let krate = self.file_to_def(file_id).get(0).copied()?.krate();
         let file_ast_id = self.db.ast_id_map(src.file_id).ast_id(&src.value);
         let ast_id = Some(AstId::new(src.file_id, file_ast_id.upcast()));
         Some(MacroDefId { krate, ast_id, kind, local_inner: false })
@@ -245,7 +251,7 @@ impl SourceToDefCtx<'_, '_> {
             return Some(res);
         }
 
-        let def = self.file_to_def(src.file_id.original_file(self.db.upcast()))?;
+        let def = self.file_to_def(src.file_id.original_file(self.db.upcast())).get(0).copied()?;
         Some(def.into())
     }
 
diff --git a/crates/hir/src/source_analyzer.rs b/crates/hir/src/source_analyzer.rs
index d546512cb..4d59293e9 100644
--- a/crates/hir/src/source_analyzer.rs
+++ b/crates/hir/src/source_analyzer.rs
@@ -161,8 +161,9 @@ impl SourceAnalyzer {
         db: &dyn HirDatabase,
         field: &ast::RecordExprField,
     ) -> Option<(Field, Option<Local>)> {
-        let expr = field.expr()?;
-        let expr_id = self.expr_id(db, &expr)?;
+        let expr_id =
+            self.body_source_map.as_ref()?.node_field(InFile::new(self.file_id, field))?;
+
         let local = if field.name_ref().is_some() {
             None
         } else {