Repository: rust-analyzer/rust-analyzer
Pull request #2429 (2019-11-27 18:24:30)

Move type inference to a separate crate


Patch:
diff --git a/Cargo.lock b/Cargo.lock
index f751be2e38..0f7a45d6cb 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -962,28 +962,13 @@ dependencies = [
 name = "ra_hir"
 version = "0.1.0"
 dependencies = [
- "arrayvec 0.5.1 (registry+https://github.com/rust-lang/crates.io-index)",
- "chalk-ir 0.1.0 (git+https://github.com/jackh726/chalk.git?rev=095cd38a4f16337913bba487f2055b9ca0179f30)",
- "chalk-rust-ir 0.1.0 (git+https://github.com/jackh726/chalk.git?rev=095cd38a4f16337913bba487f2055b9ca0179f30)",
- "chalk-solve 0.1.0 (git+https://github.com/jackh726/chalk.git?rev=095cd38a4f16337913bba487f2055b9ca0179f30)",
- "ena 0.13.1 (registry+https://github.com/rust-lang/crates.io-index)",
- "insta 0.12.0 (registry+https://github.com/rust-lang/crates.io-index)",
- "lalrpop-intern 0.15.1 (registry+https://github.com/rust-lang/crates.io-index)",
  "log 0.4.8 (registry+https://github.com/rust-lang/crates.io-index)",
- "once_cell 1.2.0 (registry+https://github.com/rust-lang/crates.io-index)",
- "parking_lot 0.10.0 (registry+https://github.com/rust-lang/crates.io-index)",
- "ra_arena 0.1.0",
- "ra_cfg 0.1.0",
  "ra_db 0.1.0",
  "ra_hir_def 0.1.0",
  "ra_hir_expand 0.1.0",
  "ra_hir_ty 0.1.0",
- "ra_mbe 0.1.0",
- "ra_prof 0.1.0",
  "ra_syntax 0.1.0",
- "ra_tt 0.1.0",
  "rustc-hash 1.0.1 (registry+https://github.com/rust-lang/crates.io-index)",
- "test_utils 0.1.0",
 ]
 
 [[package]]
@@ -1023,6 +1008,7 @@ dependencies = [
 name = "ra_hir_ty"
 version = "0.1.0"
 dependencies = [
+ "arrayvec 0.5.1 (registry+https://github.com/rust-lang/crates.io-index)",
  "chalk-ir 0.1.0 (git+https://github.com/jackh726/chalk.git?rev=095cd38a4f16337913bba487f2055b9ca0179f30)",
  "chalk-rust-ir 0.1.0 (git+https://github.com/jackh726/chalk.git?rev=095cd38a4f16337913bba487f2055b9ca0179f30)",
  "chalk-solve 0.1.0 (git+https://github.com/jackh726/chalk.git?rev=095cd38a4f16337913bba487f2055b9ca0179f30)",
@@ -1030,7 +1016,6 @@ dependencies = [
  "insta 0.12.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "lalrpop-intern 0.15.1 (registry+https://github.com/rust-lang/crates.io-index)",
  "log 0.4.8 (registry+https://github.com/rust-lang/crates.io-index)",
- "parking_lot 0.10.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "ra_arena 0.1.0",
  "ra_db 0.1.0",
  "ra_hir_def 0.1.0",
diff --git a/crates/ra_hir/Cargo.toml b/crates/ra_hir/Cargo.toml
index caba85a4f0..e79361e7cc 100644
--- a/crates/ra_hir/Cargo.toml
+++ b/crates/ra_hir/Cargo.toml
@@ -8,31 +8,11 @@ authors = ["rust-analyzer developers"]
 doctest = false
 
 [dependencies]
-arrayvec = "0.5.1"
 log = "0.4.5"
 rustc-hash = "1.0"
-parking_lot = "0.10.0"
-ena = "0.13"
-once_cell = "1.0.1"
 
 ra_syntax = { path = "../ra_syntax" }
-ra_arena = { path = "../ra_arena" }
-ra_cfg = { path = "../ra_cfg" }
 ra_db = { path = "../ra_db" }
-mbe = { path = "../ra_mbe", package = "ra_mbe" }
-tt = { path = "../ra_tt", package = "ra_tt" }
 hir_expand = { path = "../ra_hir_expand", package = "ra_hir_expand" }
 hir_def = { path = "../ra_hir_def", package = "ra_hir_def" }
 hir_ty = { path = "../ra_hir_ty", package = "ra_hir_ty" }
-test_utils = { path = "../test_utils" }
-ra_prof = { path = "../ra_prof" }
-
-# https://github.com/rust-lang/chalk/pull/294
-chalk-solve =   { git = "https://github.com/jackh726/chalk.git", rev = "095cd38a4f16337913bba487f2055b9ca0179f30" }
-chalk-rust-ir = { git = "https://github.com/jackh726/chalk.git", rev = "095cd38a4f16337913bba487f2055b9ca0179f30" }
-chalk-ir =      { git = "https://github.com/jackh726/chalk.git", rev = "095cd38a4f16337913bba487f2055b9ca0179f30" }
-
-lalrpop-intern = "0.15.1"
-
-[dev-dependencies]
-insta = "0.12.0"
diff --git a/crates/ra_hir/src/code_model.rs b/crates/ra_hir/src/code_model.rs
index 52ad4e5d16..87c78d98e1 100644
--- a/crates/ra_hir/src/code_model.rs
+++ b/crates/ra_hir/src/code_model.rs
@@ -6,8 +6,10 @@ use std::sync::Arc;
 
 use hir_def::{
     adt::VariantData,
+    body::{Body, BodySourceMap},
     builtin_type::BuiltinType,
     docs::Documentation,
+    expr::{BindingAnnotation, Pat, PatId},
     per_ns::PerNs,
     resolver::HasResolver,
     type_ref::{Mutability, TypeRef},
@@ -20,12 +22,12 @@ use hir_expand::{
     name::{self, AsName},
     AstId, MacroDefId,
 };
+use hir_ty::expr::ExprValidator;
 use ra_db::{CrateId, Edition, FileId, FilePosition};
 use ra_syntax::{ast, AstNode, SyntaxNode};
 
 use crate::{
     db::{DefDatabase, HirDatabase},
-    expr::{BindingAnnotation, Body, BodySourceMap, ExprValidator, Pat, PatId},
     ty::display::HirFormatter,
     ty::{
         self, InEnvironment, InferenceResult, TraitEnvironment, TraitRef, Ty, TyDefId, TypeCtor,
@@ -353,8 +355,8 @@ impl Struct {
             .map(|(id, _)| StructField { parent: self.into(), id })
     }
 
-    pub fn ty(self, db: &impl HirDatabase) -> Ty {
-        db.ty(self.id.into())
+    pub fn ty(self, db: &impl HirDatabase) -> Type {
+        Type::from_def(db, self.id.module(db).krate, self.id)
     }
 
     pub fn constructor_ty(self, db: &impl HirDatabase) -> Ty {
@@ -380,8 +382,8 @@ impl Union {
         Module { id: self.id.module(db) }
     }
 
-    pub fn ty(self, db: &impl HirDatabase) -> Ty {
-        db.ty(self.id.into())
+    pub fn ty(self, db: &impl HirDatabase) -> Type {
+        Type::from_def(db, self.id.module(db).krate, self.id)
     }
 
     pub fn fields(self, db: &impl HirDatabase) -> Vec<StructField> {
@@ -441,8 +443,8 @@ impl Enum {
             .map(|(id, _)| EnumVariant { parent: self, id })
     }
 
-    pub fn ty(self, db: &impl HirDatabase) -> Ty {
-        db.ty(self.id.into())
+    pub fn ty(self, db: &impl HirDatabase) -> Type {
+        Type::from_def(db, self.id.module(db).krate, self.id)
     }
 }
 
@@ -640,7 +642,7 @@ impl Function {
     pub fn diagnostics(self, db: &impl HirDatabase, sink: &mut DiagnosticSink) {
         let infer = self.infer(db);
         infer.add_diagnostics(db, self.id, sink);
-        let mut validator = ExprValidator::new(self, infer, sink);
+        let mut validator = ExprValidator::new(self.id, infer, sink);
         validator.validate_body(db);
     }
 }
@@ -946,13 +948,12 @@ impl ImplBlock {
         db.impl_data(self.id).target_type.clone()
     }
 
-    pub fn target_ty(&self, db: &impl HirDatabase) -> Ty {
-        Ty::from_hir(db, &self.id.resolver(db), &self.target_type(db))
-    }
-
-    pub fn target_trait_ref(&self, db: &impl HirDatabase) -> Option<TraitRef> {
-        let target_ty = self.target_ty(db);
-        TraitRef::from_hir(db, &self.id.resolver(db), &self.target_trait(db)?, Some(target_ty))
+    pub fn target_ty(&self, db: &impl HirDatabase) -> Type {
+        let impl_data = db.impl_data(self.id);
+        let resolver = self.id.resolver(db);
+        let environment = TraitEnvironment::lower(db, &resolver);
+        let ty = Ty::from_hir(db, &resolver, &impl_data.target_type);
+        Type { krate: self.id.module(db).krate, ty: InEnvironment { value: ty, environment } }
     }
 
     pub fn items(&self, db: &impl DefDatabase) -> Vec<AssocItem> {
@@ -1130,6 +1131,22 @@ impl Type {
         Some(adt.into())
     }
 
+    // FIXME: provide required accessors such that it becomes implementable from outside.
+    pub fn is_equal_for_find_impls(&self, other: &Type) -> bool {
+        match (&self.ty.value, &other.ty.value) {
+            (Ty::Apply(a_original_ty), Ty::Apply(ty::ApplicationTy { ctor, parameters })) => {
+                match ctor {
+                    TypeCtor::Ref(..) => match parameters.as_single() {
+                        Ty::Apply(a_ty) => a_original_ty.ctor == a_ty.ctor,
+                        _ => false,
+                    },
+                    _ => a_original_ty.ctor == *ctor,
+                }
+            }
+            _ => false,
+        }
+    }
+
     fn derived(&self, ty: Ty) -> Type {
         Type {
             krate: self.krate,
diff --git a/crates/ra_hir/src/db.rs b/crates/ra_hir/src/db.rs
index e192c8f470..bfae3660b4 100644
--- a/crates/ra_hir/src/db.rs
+++ b/crates/ra_hir/src/db.rs
@@ -1,18 +1,5 @@
 //! FIXME: write short doc here
 
-use std::sync::Arc;
-
-use hir_def::{DefWithBodyId, GenericDefId, ImplId, LocalStructFieldId, TraitId, VariantId};
-use ra_arena::map::ArenaMap;
-use ra_db::{salsa, CrateId};
-
-use crate::ty::{
-    method_resolution::CrateImplBlocks,
-    traits::{AssocTyValue, Impl},
-    CallableDef, FnSig, GenericPredicate, InferenceResult, Substs, Ty, TyDefId, TypeCtor,
-    ValueTyDefId,
-};
-
 pub use hir_def::db::{
     BodyQuery, BodyWithSourceMapQuery, ConstDataQuery, CrateDefMapQuery, CrateLangItemsQuery,
     DefDatabase, DefDatabaseStorage, DocumentationQuery, EnumDataQuery, ExprScopesQuery,
@@ -24,104 +11,12 @@ pub use hir_expand::db::{
     AstDatabase, AstDatabaseStorage, AstIdMapQuery, MacroArgQuery, MacroDefQuery, MacroExpandQuery,
     ParseMacroQuery,
 };
-
-#[salsa::query_group(HirDatabaseStorage)]
-#[salsa::requires(salsa::Database)]
-pub trait HirDatabase: DefDatabase {
-    #[salsa::invoke(crate::ty::infer_query)]
-    fn infer(&self, def: DefWithBodyId) -> Arc<InferenceResult>;
-
-    #[salsa::invoke(crate::ty::ty_query)]
-    fn ty(&self, def: TyDefId) -> Ty;
-
-    #[salsa::invoke(crate::ty::value_ty_query)]
-    fn value_ty(&self, def: ValueTyDefId) -> Ty;
-
-    #[salsa::invoke(crate::ty::field_types_query)]
-    fn field_types(&self, var: VariantId) -> Arc<ArenaMap<LocalStructFieldId, Ty>>;
-
-    #[salsa::invoke(crate::ty::callable_item_sig)]
-    fn callable_item_signature(&self, def: CallableDef) -> FnSig;
-
-    #[salsa::invoke(crate::ty::generic_predicates_for_param_query)]
-    fn generic_predicates_for_param(
-        &self,
-        def: GenericDefId,
-        param_idx: u32,
-    ) -> Arc<[GenericPredicate]>;
-
-    #[salsa::invoke(crate::ty::generic_predicates_query)]
-    fn generic_predicates(&self, def: GenericDefId) -> Arc<[GenericPredicate]>;
-
-    #[salsa::invoke(crate::ty::generic_defaults_query)]
-    fn generic_defaults(&self, def: GenericDefId) -> Substs;
-
-    #[salsa::invoke(crate::ty::method_resolution::CrateImplBlocks::impls_in_crate_query)]
-    fn impls_in_crate(&self, krate: CrateId) -> Arc<CrateImplBlocks>;
-
-    #[salsa::invoke(crate::ty::traits::impls_for_trait_query)]
-    fn impls_for_trait(&self, krate: CrateId, trait_: TraitId) -> Arc<[ImplId]>;
-
-    /// This provides the Chalk trait solver instance. Because Chalk always
-    /// works from a specific crate, this query is keyed on the crate; and
-    /// because Chalk does its own internal caching, the solver is wrapped in a
-    /// Mutex and the query does an untracked read internally, to make sure the
-    /// cached state is thrown away when input facts change.
-    #[salsa::invoke(crate::ty::traits::trait_solver_query)]
-    fn trait_solver(&self, krate: CrateId) -> crate::ty::traits::TraitSolver;
-
-    // Interned IDs for Chalk integration
-    #[salsa::interned]
-    fn intern_type_ctor(&self, type_ctor: TypeCtor) -> crate::ty::TypeCtorId;
-    #[salsa::interned]
-    fn intern_chalk_impl(&self, impl_: Impl) -> crate::ty::traits::GlobalImplId;
-    #[salsa::interned]
-    fn intern_assoc_ty_value(
-        &self,
-        assoc_ty_value: AssocTyValue,
-    ) -> crate::ty::traits::AssocTyValueId;
-
-    #[salsa::invoke(crate::ty::traits::chalk::associated_ty_data_query)]
-    fn associated_ty_data(
-        &self,
-        id: chalk_ir::TypeId,
-    ) -> Arc<chalk_rust_ir::AssociatedTyDatum<chalk_ir::family::ChalkIr>>;
-
-    #[salsa::invoke(crate::ty::traits::chalk::trait_datum_query)]
-    fn trait_datum(
-        &self,
-        krate: CrateId,
-        trait_id: chalk_ir::TraitId,
-    ) -> Arc<chalk_rust_ir::TraitDatum<chalk_ir::family::ChalkIr>>;
-
-    #[salsa::invoke(crate::ty::traits::chalk::struct_datum_query)]
-    fn struct_datum(
-        &self,
-        krate: CrateId,
-        struct_id: chalk_ir::StructId,
-    ) -> Arc<chalk_rust_ir::StructDatum<chalk_ir::family::ChalkIr>>;
-
-    #[salsa::invoke(crate::ty::traits::chalk::impl_datum_query)]
-    fn impl_datum(
-        &self,
-        krate: CrateId,
-        impl_id: chalk_ir::ImplId,
-    ) -> Arc<chalk_rust_ir::ImplDatum<chalk_ir::family::ChalkIr>>;
-
-    #[salsa::invoke(crate::ty::traits::chalk::associated_ty_value_query)]
-    fn associated_ty_value(
-        &self,
-        krate: CrateId,
-        id: chalk_rust_ir::AssociatedTyValueId,
-    ) -> Arc<chalk_rust_ir::AssociatedTyValue<chalk_ir::family::ChalkIr>>;
-
-    #[salsa::invoke(crate::ty::traits::trait_solve_query)]
-    fn trait_solve(
-        &self,
-        krate: CrateId,
-        goal: crate::ty::Canonical<crate::ty::InEnvironment<crate::ty::Obligation>>,
-    ) -> Option<crate::ty::traits::Solution>;
-}
+pub use hir_ty::db::{
+    AssociatedTyDataQuery, CallableItemSignatureQuery, FieldTypesQuery, GenericDefaultsQuery,
+    GenericPredicatesQuery, HirDatabase, HirDatabaseStorage, ImplDatumQuery, ImplsForTraitQuery,
+    ImplsInCrateQuery, InferQuery, StructDatumQuery, TraitDatumQuery, TraitSolveQuery, TyQuery,
+    ValueTyQuery,
+};
 
 #[test]
 fn hir_database_is_object_safe() {
diff --git a/crates/ra_hir/src/diagnostics.rs b/crates/ra_hir/src/diagnostics.rs
index 6db499e060..a9040ea3d5 100644
--- a/crates/ra_hir/src/diagnostics.rs
+++ b/crates/ra_hir/src/diagnostics.rs
@@ -1,93 +1,4 @@
 //! FIXME: write short doc here
-
-use std::any::Any;
-
-use hir_expand::HirFileId;
-use ra_syntax::{ast, AstNode, AstPtr, SyntaxNodePtr};
-
-use crate::{db::AstDatabase, Name, Source};
-
 pub use hir_def::diagnostics::UnresolvedModule;
 pub use hir_expand::diagnostics::{AstDiagnostic, Diagnostic, DiagnosticSink};
-
-#[derive(Debug)]
-pub struct NoSuchField {
-    pub file: HirFileId,
-    pub field: AstPtr<ast::RecordField>,
-}
-
-impl Diagnostic for NoSuchField {
-    fn message(&self) -> String {
-        "no such field".to_string()
-    }
-
-    fn source(&self) -> Source<SyntaxNodePtr> {
-        Source { file_id: self.file, value: self.field.into() }
-    }
-
-    fn as_any(&self) -> &(dyn Any + Send + 'static) {
-        self
-    }
-}
-
-#[derive(Debug)]
-pub struct MissingFields {
-    pub file: HirFileId,
-    pub field_list: AstPtr<ast::RecordFieldList>,
-    pub missed_fields: Vec<Name>,
-}
-
-impl Diagnostic for MissingFields {
-    fn message(&self) -> String {
-        use std::fmt::Write;
-        let mut message = String::from("Missing structure fields:\n");
-        for field in &self.missed_fields {
-            write!(message, "- {}\n", field).unwrap();
-        }
-        message
-    }
-    fn source(&self) -> Source<SyntaxNodePtr> {
-        Source { file_id: self.file, value: self.field_list.into() }
-    }
-    fn as_any(&self) -> &(dyn Any + Send + 'static) {
-        self
-    }
-}
-
-impl AstDiagnostic for MissingFields {
-    type AST = ast::RecordFieldList;
-
-    fn ast(&self, db: &impl AstDatabase) -> Self::AST {
-        let root = db.parse_or_expand(self.source().file_id).unwrap();
-        let node = self.source().value.to_node(&root);
-        ast::RecordFieldList::cast(node).unwrap()
-    }
-}
-
-#[derive(Debug)]
-pub struct MissingOkInTailExpr {
-    pub file: HirFileId,
-    pub expr: AstPtr<ast::Expr>,
-}
-
-impl Diagnostic for MissingOkInTailExpr {
-    fn message(&self) -> String {
-        "wrap return expression in Ok".to_string()
-    }
-    fn source(&self) -> Source<SyntaxNodePtr> {
-        Source { file_id: self.file, value: self.expr.into() }
-    }
-    fn as_any(&self) -> &(dyn Any + Send + 'static) {
-        self
-    }
-}
-
-impl AstDiagnostic for MissingOkInTailExpr {
-    type AST = ast::Expr;
-
-    fn ast(&self, db: &impl AstDatabase) -> Self::AST {
-        let root = db.parse_or_expand(self.file).unwrap();
-        let node = self.source().value.to_node(&root);
-        ast::Expr::cast(node).unwrap()
-    }
-}
+pub use hir_ty::diagnostics::{MissingFields, MissingOkInTailExpr, NoSuchField};
diff --git a/crates/ra_hir/src/lib.rs b/crates/ra_hir/src/lib.rs
index b88e4c745a..3c12c61f03 100644
--- a/crates/ra_hir/src/lib.rs
+++ b/crates/ra_hir/src/lib.rs
@@ -32,20 +32,13 @@ pub mod db;
 pub mod source_binder;
 
 mod ty;
-mod expr;
 pub mod diagnostics;
-mod util;
 
 mod from_id;
 mod code_model;
 
 pub mod from_source;
 
-#[cfg(test)]
-mod test_db;
-#[cfg(test)]
-mod marks;
-
 pub use crate::{
     code_model::{
         src::HasSource, Adt, AssocItem, AttrDef, Const, Container, Crate, CrateDependency,
@@ -53,7 +46,6 @@ pub use crate::{
         HasAttrs, ImplBlock, Import, Local, MacroDef, Module, ModuleDef, ModuleSource, ScopeDef,
         Static, Struct, StructField, Trait, Type, TypeAlias, Union, VariantDef,
     },
-    expr::ExprScopes,
     from_source::FromSource,
     source_binder::{PathResolution, ScopeEntryWithSyntax, SourceAnalyzer},
     ty::{
@@ -64,6 +56,7 @@ pub use crate::{
 };
 
 pub use hir_def::{
+    body::scope::ExprScopes,
     builtin_type::BuiltinType,
     docs::Documentation,
     path::{Path, PathKind},
diff --git a/crates/ra_hir/src/source_binder.rs b/crates/ra_hir/src/source_binder.rs
index 05f5bca575..76c493f1a8 100644
--- a/crates/ra_hir/src/source_binder.rs
+++ b/crates/ra_hir/src/source_binder.rs
@@ -8,6 +8,10 @@
 use std::sync::Arc;
 
 use hir_def::{
+    body::{
+        scope::{ExprScopes, ScopeId},
+        BodySourceMap,
+    },
     expr::{ExprId, PatId},
     path::known,
     resolver::{self, resolver_for_scope, HasResolver, Resolver, TypeNs, ValueNs},
@@ -25,7 +29,6 @@ use ra_syntax::{
 
 use crate::{
     db::HirDatabase,
-    expr::{BodySourceMap, ExprScopes, ScopeId},
     ty::{
         method_resolution::{self, implements_trait},
         InEnvironment, TraitEnvironment, Ty,
@@ -91,7 +94,7 @@ pub struct SourceAnalyzer {
     body_owner: Option<DefWithBody>,
     body_source_map: Option<Arc<BodySourceMap>>,
     infer: Option<Arc<crate::ty::InferenceResult>>,
-    scopes: Option<Arc<crate::expr::ExprScopes>>,
+    scopes: Option<Arc<ExprScopes>>,
 }
 
 #[derive(Debug, Clone, PartialEq, Eq)]
@@ -455,21 +458,6 @@ impl SourceAnalyzer {
             macro_file_kind: to_macro_file_kind(macro_call.value),
         })
     }
-
-    #[cfg(test)]
-    pub(crate) fn body_source_map(&self) -> Arc<BodySourceMap> {
-        self.body_source_map.clone().unwrap()
-    }
-
-    #[cfg(test)]
-    pub(crate) fn inference_result(&self) -> Arc<crate::ty::InferenceResult> {
-        self.infer.clone().unwrap()
-    }
-
-    #[cfg(test)]
-    pub(crate) fn analyzed_declaration(&self) -> Option<DefWithBody> {
-        self.body_owner
-    }
 }
 
 fn scope_for(
diff --git a/crates/ra_hir/src/ty.rs b/crates/ra_hir/src/ty.rs
index e4ba8afa61..4ed69c00dc 100644
--- a/crates/ra_hir/src/ty.rs
+++ b/crates/ra_hir/src/ty.rs
@@ -1,1113 +1,4 @@
 //! The type system. We currently use this to infer types for completion, hover
 //! information and various assists.
 
-mod autoderef;
-pub(crate) mod primitive;
-pub(crate) mod traits;
-pub(crate) mod method_resolution;
-mod op;
-mod lower;
-mod infer;
-pub(crate) mod display;
-pub(crate) mod utils;
-
-#[cfg(test)]
-mod tests;
-
-use std::ops::Deref;
-use std::sync::Arc;
-use std::{fmt, iter, mem};
-
-use hir_def::{
-    expr::ExprId, generics::GenericParams, type_ref::Mutability, AdtId, ContainerId, DefWithBodyId,
-    GenericDefId, HasModule, Lookup, TraitId, TypeAliasId,
-};
-use hir_expand::name::Name;
-use ra_db::{impl_intern_key, salsa, CrateId};
-
-use crate::{
-    db::HirDatabase,
-    ty::primitive::{FloatTy, IntTy, Uncertain},
-    util::make_mut_slice,
-};
-use display::{HirDisplay, HirFormatter};
-
-pub(crate) use autoderef::autoderef;
-pub(crate) use infer::{infer_query, InferTy, InferenceResult};
-pub use lower::CallableDef;
-pub(crate) use lower::{
-    callable_item_sig, field_types_query, generic_defaults_query,
-    generic_predicates_for_param_query, generic_predicates_query, ty_query, value_ty_query,
-    TyDefId, ValueTyDefId,
-};
-pub(crate) use traits::{InEnvironment, Obligation, ProjectionPredicate, TraitEnvironment};
-
-/// A type constructor or type name: this might be something like the primitive
-/// type `bool`, a struct like `Vec`, or things like function pointers or
-/// tuples.
-#[derive(Copy, Clone, PartialEq, Eq, Debug, Hash)]
-pub enum TypeCtor {
-    /// The primitive boolean type. Written as `bool`.
-    Bool,
-
-    /// The primitive character type; holds a Unicode scalar value
-    /// (a non-surrogate code point). Written as `char`.
-    Char,
-
-    /// A primitive integer type. For example, `i32`.
-    Int(Uncertain<IntTy>),
-
-    /// A primitive floating-point type. For example, `f64`.
-    Float(Uncertain<FloatTy>),
-
-    /// Structures, enumerations and unions.
-    Adt(AdtId),
-
-    /// The pointee of a string slice. Written as `str`.
-    Str,
-
-    /// The pointee of an array slice.  Written as `[T]`.
-    Slice,
-
-    /// An array with the given length. Written as `[T; n]`.
-    Array,
-
-    /// A raw pointer. Written as `*mut T` or `*const T`
-    RawPtr(Mutability),
-
-    /// A reference; a pointer with an associated lifetime. Written as
-    /// `&'a mut T` or `&'a T`.
-    Ref(Mutability),
-
-    /// 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(CallableDef),
-
-    /// 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;
-    /// ```
-    FnPtr { num_args: u16 },
-
-    /// The never type `!`.
-    Never,
-
-    /// A tuple type.  For example, `(i32, bool)`.
-    Tuple { cardinality: u16 },
-
-    /// 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(TypeAliasId),
-
-    /// The type of a specific closure.
-    ///
-    /// The closure signature is stored in a `FnPtr` type in the first type
-    /// parameter.
-    Closure { def: DefWithBodyId, expr: ExprId },
-}
-
-/// This exists just for Chalk, because Chalk just has a single `StructId` where
-/// we have different kinds of ADTs, primitive types and special type
-/// constructors like tuples and function pointers.
-#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
-pub struct TypeCtorId(salsa::InternId);
-impl_intern_key!(TypeCtorId);
-
-impl TypeCtor {
-    pub fn num_ty_params(self, db: &impl HirDatabase) -> usize {
-        match self {
-            TypeCtor::Bool
-            | TypeCtor::Char
-            | TypeCtor::Int(_)
-            | TypeCtor::Float(_)
-            | TypeCtor::Str
-            | TypeCtor::Never => 0,
-            TypeCtor::Slice
-            | TypeCtor::Array
-            | TypeCtor::RawPtr(_)
-            | TypeCtor::Ref(_)
-            | TypeCtor::Closure { .. } // 1 param representing the signature of the closure
-            => 1,
-            TypeCtor::Adt(adt) => {
-                let generic_params = db.generic_params(AdtId::from(adt).into());
-                generic_params.count_params_including_parent()
-            }
-            TypeCtor::FnDef(callable) => {
-                let generic_params = db.generic_params(callable.into());
-                generic_params.count_params_including_parent()
-            }
-            TypeCtor::AssociatedType(type_alias) => {
-                let generic_params = db.generic_params(type_alias.into());
-                generic_params.count_params_including_parent()
-            }
-            TypeCtor::FnPtr { num_args } => num_args as usize + 1,
-            TypeCtor::Tuple { cardinality } => cardinality as usize,
-        }
-    }
-
-    pub fn krate(self, db: &impl HirDatabase) -> Option<CrateId> {
-        match self {
-            TypeCtor::Bool
-            | TypeCtor::Char
-            | TypeCtor::Int(_)
-            | TypeCtor::Float(_)
-            | TypeCtor::Str
-            | TypeCtor::Never
-            | TypeCtor::Slice
-            | TypeCtor::Array
-            | TypeCtor::RawPtr(_)
-            | TypeCtor::Ref(_)
-            | TypeCtor::FnPtr { .. }
-            | TypeCtor::Tuple { .. } => None,
-            // Closure's krate is irrelevant for coherence I would think?
-            TypeCtor::Closure { .. } => None,
-            TypeCtor::Adt(adt) => Some(adt.module(db).krate),
-            TypeCtor::FnDef(callable) => Some(callable.krate(db)),
-            TypeCtor::AssociatedType(type_alias) => Some(type_alias.lookup(db).module(db).krate),
-        }
-    }
-
-    pub fn as_generic_def(self) -> Option<GenericDefId> {
-        match self {
-            TypeCtor::Bool
-            | TypeCtor::Char
-            | TypeCtor::Int(_)
-            | TypeCtor::Float(_)
-            | TypeCtor::Str
-            | TypeCtor::Never
-            | TypeCtor::Slice
-            | TypeCtor::Array
-            | TypeCtor::RawPtr(_)
-            | TypeCtor::Ref(_)
-            | TypeCtor::FnPtr { .. }
-            | TypeCtor::Tuple { .. }
-            | TypeCtor::Closure { .. } => None,
-            TypeCtor::Adt(adt) => Some(adt.into()),
-            TypeCtor::FnDef(callable) => Some(callable.into()),
-            TypeCtor::AssociatedType(type_alias) => Some(type_alias.into()),
-        }
-    }
-}
-
-/// A nominal type with (maybe 0) type parameters. This might be a primitive
-/// type like `bool`, a struct, tuple, function pointer, reference or
-/// several other things.
-#[derive(Clone, PartialEq, Eq, Debug, Hash)]
-pub struct ApplicationTy {
-    pub ctor: TypeCtor,
-    pub parameters: Substs,
-}
-
-/// 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: TypeAliasId,
-    pub parameters: Substs,
-}
-
-impl ProjectionTy {
-    pub fn trait_ref(&self, db: &impl HirDatabase) -> TraitRef {
-        TraitRef { trait_: self.trait_(db).into(), substs: self.parameters.clone() }
-    }
-
-    fn trait_(&self, db: &impl HirDatabase) -> TraitId {
-        match self.associated_ty.lookup(db).container {
-            ContainerId::TraitId(it) => it,
-            _ => panic!("projection ty without parent trait"),
-        }
-    }
-}
-
-impl TypeWalk for ProjectionTy {
-    fn walk(&self, f: &mut impl FnMut(&Ty)) {
-        self.parameters.walk(f);
-    }
-
-    fn walk_mut_binders(&mut self, f: &mut impl FnMut(&mut Ty, usize), binders: usize) {
-        self.parameters.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 Ty {
-    /// A nominal type with (maybe 0) type parameters. This might be a primitive
-    /// type like `bool`, a struct, tuple, function pointer, reference or
-    /// several other things.
-    Apply(ApplicationTy),
-
-    /// 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),
-
-    /// A type parameter; for example, `T` in `fn f<T>(x: T) {}
-    Param {
-        /// The index of the parameter (starting with parameters from the
-        /// surrounding impl, then the current function).
-        idx: u32,
-        /// The name of the parameter, for displaying.
-        // FIXME get rid of this
-        name: Name,
-    },
-
-    /// A bound type variable. Used during trait resolution to represent Chalk
-    /// variables, and in `Dyn` and `Opaque` bounds to represent the `Self` type.
-    Bound(u32),
-
-    /// A type variable used during type checking. Not to be confused with a
-    /// type parameter.
-    Infer(InferTy),
-
-    /// 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(Arc<[GenericPredicate]>),
-
-    /// An opaque type (`impl Trait`).
-    ///
-    /// The predicates are quantified over the `Self` type; see `Ty::Dyn` for
-    /// more.
-    Opaque(Arc<[GenericPredicate]>),
-
-    /// 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,
-}
-
-/// A list of substitutions for generic parameters.
-#[derive(Clone, PartialEq, Eq, Debug, Hash)]
-pub struct Substs(Arc<[Ty]>);
-
-impl TypeWalk for Substs {
-    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, usize), binders: usize) {
-        for t in make_mut_slice(&mut self.0) {
-            t.walk_mut_binders(f, binders);
-        }
-    }
-}
-
-impl Substs {
-    pub fn empty() -> Substs {
-        Substs(Arc::new([]))
-    }
-
-    pub fn single(ty: Ty) -> Substs {
-        Substs(Arc::new([ty]))
-    }
-
-    pub fn prefix(&self, n: usize) -> Substs {
-        Substs(self.0[..std::cmp::min(self.0.len(), n)].into())
-    }
-
-    pub fn as_single(&self) -> &Ty {
-        if self.0.len() != 1 {
-            panic!("expected substs of len 1, got {:?}", self);
-        }
-        &self.0[0]
-    }
-
-    /// Return Substs that replace each parameter by itself (i.e. `Ty::Param`).
-    pub fn identity(generic_params: &GenericParams) -> Substs {
-        Substs(
-            generic_params
-                .params_including_parent()
-                .into_iter()
-                .map(|p| Ty::Param { idx: p.idx, name: p.name.clone() })
-                .collect(),
-        )
-    }
-
-    /// Return Substs that replace each parameter by a bound variable.
-    pub fn bound_vars(generic_params: &GenericParams) -> Substs {
-        Substs(
-            generic_params
-                .params_including_parent()
-                .into_iter()
-                .map(|p| Ty::Bound(p.idx))
-                .collect(),
-        )
-    }
-
-    pub fn build_for_def(db: &impl HirDatabase, def: impl Into<GenericDefId>) -> SubstsBuilder {
-        let def = def.into();
-        let params = db.generic_params(def);
-        let param_count = params.count_params_including_parent();
-        Substs::builder(param_count)
-    }
-
-    pub fn build_for_generics(generic_params: &GenericParams) -> SubstsBuilder {
-        Substs::builder(generic_params.count_params_including_parent())
-    }
-
-    pub fn build_for_type_ctor(db: &impl HirDatabase, type_ctor: TypeCtor) -> SubstsBuilder {
-        Substs::builder(type_ctor.num_ty_params(db))
-    }
-
-    fn builder(param_count: usize) -> SubstsBuilder {
-        SubstsBuilder { vec: Vec::with_capacity(param_count), param_count }
-    }
-}
-
-#[derive(Debug, Clone)]
-pub struct SubstsBuilder {
-    vec: Vec<Ty>,
-    param_count: usize,
-}
-
-impl SubstsBuilder {
-    pub fn build(self) -> Substs {
-        assert_eq!(self.vec.len(), self.param_count);
-        Substs(self.vec.into())
-    }
-
-    pub fn push(mut self, ty: Ty) -> Self {
-        self.vec.push(ty);
-        self
-    }
-
-    fn remaining(&self) -> usize {
-        self.param_count - self.vec.len()
-    }
-
-    pub fn fill_with_bound_vars(self, starting_from: u32) -> Self {
-        self.fill((starting_from..).map(Ty::Bound))
-    }
-
-    pub fn fill_with_params(self) -> Self {
-        let start = self.vec.len() as u32;
-        self.fill((start..).map(|idx| Ty::Param { idx, name: Name::missing() }))
-    }
-
-    pub fn fill_with_unknown(self) -> Self {
-        self.fill(iter::repeat(Ty::Unknown))
-    }
-
-    pub fn fill(mut self, filler: impl Iterator<Item = Ty>) -> Self {
-        self.vec.extend(filler.take(self.remaining()));
-        assert_eq!(self.remaining(), 0);
-        self
-    }
-
-    pub fn use_parent_substs(mut self, parent_substs: &Substs) -> Self {
-        assert!(self.vec.is_empty());
-        assert!(parent_substs.len() <= self.param_count);
-        self.vec.extend(parent_substs.iter().cloned());
-        self
-    }
-}
-
-impl Deref for Substs {
-    type Target = [Ty];
-
-    fn deref(&self) -> &[Ty] {
-        &self.0
-    }
-}
-
-/// A trait with type parameters. This includes the `Self`, so this represents a concrete type implementing the trait.
-/// Name to be bikeshedded: TraitBound? TraitImplements?
-#[derive(Clone, PartialEq, Eq, Debug, Hash)]
-pub struct TraitRef {
-    /// FIXME name?
-    pub trait_: TraitId,
-    pub substs: Substs,
-}
-
-impl TraitRef {
-    pub fn self_ty(&self) -> &Ty {
-        &self.substs[0]
-    }
-}
-
-impl TypeWalk for TraitRef {
-    fn walk(&self, f: &mut impl FnMut(&Ty)) {
-        self.substs.walk(f);
-    }
-
-    fn walk_mut_binders(&mut self, f: &mut impl FnMut(&mut Ty, usize), binders: usize) {
-        self.substs.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 GenericPredicate {
-    /// The given trait needs to be implemented for its type parameters.
-    Implemented(TraitRef),
-    /// An associated type bindings like in `Iterator<Item = T>`.
-    Projection(ProjectionPredicate),
-    /// We couldn't resolve the trait reference. (If some type parameters can't
-    /// be resolved, they will just be Unknown).
-    Error,
-}
-
-impl GenericPredicate {
-    pub fn is_error(&self) -> bool {
-        match self {
-            GenericPredicate::Error => true,
-            _ => false,
-        }
-    }
-
-    pub fn is_implemented(&self) -> bool {
-        match self {
-            GenericPredicate::Implemented(_) => true,
-            _ => false,
-        }
-    }
-
-    pub fn trait_ref(&self, db: &impl HirDatabase) -> Option<TraitRef> {
-        match self {
-            GenericPredicate::Implemented(tr) => Some(tr.clone()),
-            GenericPredicate::Projection(proj) => Some(proj.projection_ty.trait_ref(db)),
-            GenericPredicate::Error => None,
-        }
-    }
-}
-
-impl TypeWalk for GenericPredicate {
-    fn walk(&self, f: &mut impl FnMut(&Ty)) {
-        match self {
-            GenericPredicate::Implemented(trait_ref) => trait_ref.walk(f),
-            GenericPredicate::Projection(projection_pred) => projection_pred.walk(f),
-            GenericPredicate::Error => {}
-        }
-    }
-
-    fn walk_mut_binders(&mut self, f: &mut impl FnMut(&mut Ty, usize), binders: usize) {
-        match self {
-            GenericPredicate::Implemented(trait_ref) => trait_ref.walk_mut_binders(f, binders),
-            GenericPredicate::Projection(projection_pred) => {
-                projection_pred.walk_mut_binders(f, binders)
-            }
-            GenericPredicate::Error => {}
-        }
-    }
-}
-
-/// 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 `num_vars` tells us how
-/// many there are. 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 num_vars: usize,
-}
-
-/// A function signature as seen by type inference: Several parameter types and
-/// one return type.
-#[derive(Clone, PartialEq, Eq, Debug)]
-pub struct FnSig {
-    params_and_return: Arc<[Ty]>,
-}
-
-impl FnSig {
-    pub fn from_params_and_return(mut params: Vec<Ty>, ret: Ty) -> FnSig {
-        params.push(ret);
-        FnSig { params_and_return: params.into() }
-    }
-
-    pub fn from_fn_ptr_substs(substs: &Substs) -> FnSig {
-        FnSig { params_and_return: Arc::clone(&substs.0) }
-    }
-
-    pub fn params(&self) -> &[Ty] {
-        &self.params_and_return[0..self.params_and_return.len() - 1]
-    }
-
-    pub fn ret(&self) -> &Ty {
-        &self.params_and_return[self.params_and_return.len() - 1]
-    }
-}
-
-impl TypeWalk for FnSig {
-    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, usize), binders: usize) {
-        for t in make_mut_slice(&mut self.params_and_return) {
-            t.walk_mut_binders(f, binders);
-        }
-    }
-}
-
-impl Ty {
-    pub fn simple(ctor: TypeCtor) -> Ty {
-        Ty::Apply(ApplicationTy { ctor, parameters: Substs::empty() })
-    }
-    pub fn apply_one(ctor: TypeCtor, param: Ty) -> Ty {
-        Ty::Apply(ApplicationTy { ctor, parameters: Substs::single(param) })
-    }
-    pub fn apply(ctor: TypeCtor, parameters: Substs) -> Ty {
-        Ty::Apply(ApplicationTy { ctor, parameters })
-    }
-    pub fn unit() -> Self {
-        Ty::apply(TypeCtor::Tuple { cardinality: 0 }, Substs::empty())
-    }
-
-    pub fn as_reference(&self) -> Option<(&Ty, Mutability)> {
-        match self {
-            Ty::Apply(ApplicationTy { ctor: TypeCtor::Ref(mutability), parameters }) => {
-                Some((parameters.as_single(), *mutability))
-            }
-            _ => None,
-        }
-    }
-
-    pub fn as_adt(&self) -> Option<(AdtId, &Substs)> {
-        match self {
-            Ty::Apply(ApplicationTy { ctor: TypeCtor::Adt(adt_def), parameters }) => {
-                Some((*adt_def, parameters))
-            }
-            _ => None,
-        }
-    }
-
-    pub fn as_tuple(&self) -> Option<&Substs> {
-        match self {
-            Ty::Apply(ApplicationTy { ctor: TypeCtor::Tuple { .. }, parameters }) => {
-                Some(parameters)
-            }
-            _ => None,
-        }
-    }
-
-    pub fn as_callable(&self) -> Option<(CallableDef, &Substs)> {
-        match self {
-            Ty::Apply(ApplicationTy { ctor: TypeCtor::FnDef(callable_def), parameters }) => {
-                Some((*callable_def, parameters))
-            }
-            _ => None,
-        }
-    }
-
-    fn builtin_deref(&self) -> Option<Ty> {
-        match self {
-            Ty::Apply(a_ty) => match a_ty.ctor {
-                TypeCtor::Ref(..) => Some(Ty::clone(a_ty.parameters.as_single())),
-                TypeCtor::RawPtr(..) => Some(Ty::clone(a_ty.parameters.as_single())),
-                _ => None,
-            },
-            _ => None,
-        }
-    }
-
-    fn callable_sig(&self, db: &impl HirDatabase) -> Option<FnSig> {
-        match self {
-            Ty::Apply(a_ty) => match a_ty.ctor {
-                TypeCtor::FnPtr { .. } => Some(FnSig::from_fn_ptr_substs(&a_ty.parameters)),
-                TypeCtor::FnDef(def) => {
-                    let sig = db.callable_item_signature(def);
-                    Some(sig.subst(&a_ty.parameters))
-                }
-                TypeCtor::Closure { .. } => {
-                    let sig_param = &a_ty.parameters[0];
-                    sig_param.callable_sig(db)
-                }
-                _ => None,
-            },
-            _ => None,
-        }
-    }
-
-    /// If this is a type with type parameters (an ADT or function), replaces
-    /// the `Substs` for these type parameters with the given ones. (So e.g. if
-    /// `self` is `Option<_>` and the substs contain `u32`, we'll have
-    /// `Option<u32>` afterwards.)
-    pub fn apply_substs(self, substs: Substs) -> Ty {
-        match self {
-            Ty::Apply(ApplicationTy { ctor, parameters: previous_substs }) => {
-                assert_eq!(previous_substs.len(), substs.len());
-                Ty::Apply(ApplicationTy { ctor, parameters: substs })
-            }
-            _ => self,
-        }
-    }
-
-    /// Returns the type parameters of this type if it has some (i.e. is an ADT
-    /// or function); so if `self` is `Option<u32>`, this returns the `u32`.
-    pub fn substs(&self) -> Option<Substs> {
-        match self {
-            Ty::Apply(ApplicationTy { parameters, .. }) => Some(parameters.clone()),
-            _ => None,
-        }
-    }
-
-    /// If this is an `impl Trait` or `dyn Trait`, returns that trait.
-    pub fn inherent_trait(&self) -> Option<TraitId> {
-        match self {
-            Ty::Dyn(predicates) | Ty::Opaque(predicates) => {
-                predicates.iter().find_map(|pred| match pred {
-                    GenericPredicate::Implemented(tr) => Some(tr.trait_),
-                    _ => None,
-                })
-            }
-            _ => None,
-        }
-    }
-}
-
-/// 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), 0);
-    }
-    /// Walk the type, counting entered binders.
-    ///
-    /// `Ty::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 `Ty::Dyn` and `Ty::Opaque`, which each introduce a bound
-    /// variable for the self type.
-    fn walk_mut_binders(&mut self, f: &mut impl FnMut(&mut Ty, usize), binders: usize);
-
-    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, Ty::Unknown);
-            *ty_mut = f(ty);
-        });
-        self
-    }
-
-    /// Replaces type parameters in this type using the given `Substs`. (So e.g.
-    /// if `self` is `&[T]`, where type parameter T has index 0, and the
-    /// `Substs` contain `u32` at index 0, we'll have `&[u32]` afterwards.)
-    fn subst(self, substs: &Substs) -> Self
-    where
-        Self: Sized,
-    {
-        self.fold(&mut |ty| match ty {
-            Ty::Param { idx, name } => {
-                substs.get(idx as usize).cloned().unwrap_or(Ty::Param { idx, name })
-            }
-            ty => ty,
-        })
-    }
-
-    /// Substitutes `Ty::Bound` vars (as opposed to type parameters).
-    fn subst_bound_vars(mut self, substs: &Substs) -> Self
-    where
-        Self: Sized,
-    {
-        self.walk_mut_binders(
-            &mut |ty, binders| match ty {
-                &mut Ty::Bound(idx) => {
-                    if idx as usize >= binders && (idx as usize - binders) < substs.len() {
-                        *ty = substs.0[idx as usize - binders].clone();
-                    }
-                }
-                _ => {}
-            },
-            0,
-        );
-        self
-    }
-
-    /// Shifts up `Ty::Bound` vars by `n`.
-    fn shift_bound_vars(self, n: i32) -> Self
-    where
-        Self: Sized,
-    {
-        self.fold(&mut |ty| match ty {
-            Ty::Bound(idx) => {
-                assert!(idx as i32 >= -n);
-                Ty::Bound((idx as i32 + n) as u32)
-            }
-            ty => ty,
-        })
-    }
-}
-
-impl TypeWalk for Ty {
-    fn walk(&self, f: &mut impl FnMut(&Ty)) {
-        match self {
-            Ty::Apply(a_ty) => {
-                for t in a_ty.parameters.iter() {
-                    t.walk(f);
-                }
-            }
-            Ty::Projection(p_ty) => {
-                for t in p_ty.parameters.iter() {
-                    t.walk(f);
-                }
-            }
-            Ty::Dyn(predicates) | Ty::Opaque(predicates) => {
-                for p in predicates.iter() {
-                    p.walk(f);
-                }
-            }
-            Ty::Param { .. } | Ty::Bound(_) | Ty::Infer(_) | Ty::Unknown => {}
-        }
-        f(self);
-    }
-
-    fn walk_mut_binders(&mut self, f: &mut impl FnMut(&mut Ty, usize), binders: usize) {
-        match self {
-            Ty::Apply(a_ty) => {
-                a_ty.parameters.walk_mut_binders(f, binders);
-            }
-            Ty::Projection(p_ty) => {
-                p_ty.parameters.walk_mut_binders(f, binders);
-            }
-            Ty::Dyn(predicates) | Ty::Opaque(predicates) => {
-                for p in make_mut_slice(predicates) {
-                    p.walk_mut_binders(f, binders + 1);
-                }
-            }
-            Ty::Param { .. } | Ty::Bound(_) | Ty::Infer(_) | Ty::Unknown => {}
-        }
-        f(self, binders);
-    }
-}
-
-impl HirDisplay for &Ty {
-    fn hir_fmt(&self, f: &mut HirFormatter<impl HirDatabase>) -> fmt::Result {
-        HirDisplay::hir_fmt(*self, f)
-    }
-}
-
-impl HirDisplay for ApplicationTy {
-    fn hir_fmt(&self, f: &mut HirFormatter<impl HirDatabase>) -> fmt::Result {
-        if f.should_truncate() {
-            return write!(f, "…");
-        }
-
-        match self.ctor {
-            TypeCtor::Bool => write!(f, "bool")?,
-            TypeCtor::Char => write!(f, "char")?,
-            TypeCtor::Int(t) => write!(f, "{}", t)?,
-            TypeCtor::Float(t) => write!(f, "{}", t)?,
-            TypeCtor::Str => write!(f, "str")?,
-            TypeCtor::Slice => {
-                let t = self.parameters.as_single();
-                write!(f, "[{}]", t.display(f.db))?;
-            }
-            TypeCtor::Array => {
-                let t = self.parameters.as_single();
-                write!(f, "[{};_]", t.display(f.db))?;
-            }
-            TypeCtor::RawPtr(m) => {
-                let t = self.parameters.as_single();
-                write!(f, "*{}{}", m.as_keyword_for_ptr(), t.display(f.db))?;
-            }
-            TypeCtor::Ref(m) => {
-                let t = self.parameters.as_single();
-                write!(f, "&{}{}", m.as_keyword_for_ref(), t.display(f.db))?;
-            }
-            TypeCtor::Never => write!(f, "!")?,
-            TypeCtor::Tuple { .. } => {
-                let ts = &self.parameters;
-                if ts.len() == 1 {
-                    write!(f, "({},)", ts[0].display(f.db))?;
-                } else {
-                    write!(f, "(")?;
-                    f.write_joined(&*ts.0, ", ")?;
-                    write!(f, ")")?;
-                }
-            }
-            TypeCtor::FnPtr { .. } => {
-                let sig = FnSig::from_fn_ptr_substs(&self.parameters);
-                write!(f, "fn(")?;
-                f.write_joined(sig.params(), ", ")?;
-                write!(f, ") -> {}", sig.ret().display(f.db))?;
-            }
-            TypeCtor::FnDef(def) => {
-                let sig = f.db.callable_item_signature(def);
-                let name = match def {
-                    CallableDef::FunctionId(ff) => f.db.function_data(ff).name.clone(),
-                    CallableDef::StructId(s) => {
-                        f.db.struct_data(s).name.clone().unwrap_or_else(Name::missing)
-                    }
-                    CallableDef::EnumVariantId(e) => {
-                        let enum_data = f.db.enum_data(e.parent);
-                        enum_data.variants[e.local_id].name.clone().unwrap_or_else(Name::missing)
-                    }
-                };
-                match def {
-                    CallableDef::FunctionId(_) => write!(f, "fn {}", name)?,
-                    CallableDef::StructId(_) | CallableDef::EnumVariantId(_) => {
-                        write!(f, "{}", name)?
-                    }
-                }
-                if self.parameters.len() > 0 {
-                    write!(f, "<")?;
-                    f.write_joined(&*self.parameters.0, ", ")?;
-                    write!(f, ">")?;
-                }
-                write!(f, "(")?;
-                f.write_joined(sig.params(), ", ")?;
-                write!(f, ") -> {}", sig.ret().display(f.db))?;
-            }
-            TypeCtor::Adt(def_id) => {
-                let name = match def_id {
-                    AdtId::StructId(it) => f.db.struct_data(it).name.clone(),
-                    AdtId::UnionId(it) => f.db.union_data(it).name.clone(),
-                    AdtId::EnumId(it) => f.db.enum_data(it).name.clone(),
-                }
-                .unwrap_or_else(Name::missing);
-                write!(f, "{}", name)?;
-                if self.parameters.len() > 0 {
-                    write!(f, "<")?;
-                    f.write_joined(&*self.parameters.0, ", ")?;
-                    write!(f, ">")?;
-                }
-            }
-            TypeCtor::AssociatedType(type_alias) => {
-                let trait_ = match type_alias.lookup(f.db).container {
-                    ContainerId::TraitId(it) => it,
-                    _ => panic!("not an associated type"),
-                };
-                let trait_name = f.db.trait_data(trait_).name.clone().unwrap_or_else(Name::missing);
-                let name = f.db.type_alias_data(type_alias).name.clone();
-                write!(f, "{}::{}", trait_name, name)?;
-                if self.parameters.len() > 0 {
-                    write!(f, "<")?;
-                    f.write_joined(&*self.parameters.0, ", ")?;
-                    write!(f, ">")?;
-                }
-            }
-            TypeCtor::Closure { .. } => {
-                let sig = self.parameters[0]
-                    .callable_sig(f.db)
-                    .expect("first closure parameter should contain signature");
-                write!(f, "|")?;
-                f.write_joined(sig.params(), ", ")?;
-                write!(f, "| -> {}", sig.ret().display(f.db))?;
-            }
-        }
-        Ok(())
-    }
-}
-
-impl HirDisplay for ProjectionTy {
-    fn hir_fmt(&self, f: &mut HirFormatter<impl HirDatabase>) -> fmt::Result {
-        if f.should_truncate() {
-            return write!(f, "…");
-        }
-
-        let trait_name =
-            f.db.trait_data(self.trait_(f.db)).name.clone().unwrap_or_else(Name::missing);
-        write!(f, "<{} as {}", self.parameters[0].display(f.db), trait_name,)?;
-        if self.parameters.len() > 1 {
-            write!(f, "<")?;
-            f.write_joined(&self.parameters[1..], ", ")?;
-            write!(f, ">")?;
-        }
-        write!(f, ">::{}", f.db.type_alias_data(self.associated_ty).name)?;
-        Ok(())
-    }
-}
-
-impl HirDisplay for Ty {
-    fn hir_fmt(&self, f: &mut HirFormatter<impl HirDatabase>) -> fmt::Result {
-        if f.should_truncate() {
-            return write!(f, "…");
-        }
-
-        match self {
-            Ty::Apply(a_ty) => a_ty.hir_fmt(f)?,
-            Ty::Projection(p_ty) => p_ty.hir_fmt(f)?,
-            Ty::Param { name, .. } => write!(f, "{}", name)?,
-            Ty::Bound(idx) => write!(f, "?{}", idx)?,
-            Ty::Dyn(predicates) | Ty::Opaque(predicates) => {
-                match self {
-                    Ty::Dyn(_) => write!(f, "dyn ")?,
-                    Ty::Opaque(_) => write!(f, "impl ")?,
-                    _ => unreachable!(),
-                };
-                // Note: This code is written to produce nice results (i.e.
-                // corresponding to surface Rust) for types that can occur in
-                // actual Rust. It will have weird results if the predicates
-                // aren't as expected (i.e. self types = $0, projection
-                // predicates for a certain trait come after the Implemented
-                // predicate for that trait).
-                let mut first = true;
-                let mut angle_open = false;
-                for p in predicates.iter() {
-                    match p {
-                        GenericPredicate::Implemented(trait_ref) => {
-                            if angle_open {
-                                write!(f, ">")?;
-                            }
-                            if !first {
-                                write!(f, " + ")?;
-                            }
-                            // We assume that the self type is $0 (i.e. the
-                            // existential) here, which is the only thing that's
-                            // possible in actual Rust, and hence don't print it
-                            write!(
-                                f,
-                                "{}",
-                                f.db.trait_data(trait_ref.trait_)
-                                    .name
-                                    .clone()
-                                    .unwrap_or_else(Name::missing)
-                            )?;
-                            if trait_ref.substs.len() > 1 {
-                                write!(f, "<")?;
-                                f.write_joined(&trait_ref.substs[1..], ", ")?;
-                                // there might be assoc type bindings, so we leave the angle brackets open
-                                angle_open = true;
-                            }
-                        }
-                        GenericPredicate::Projection(projection_pred) => {
-                            // in types in actual Rust, these will always come
-                            // after the corresponding Implemented predicate
-                            if angle_open {
-                                write!(f, ", ")?;
-                            } else {
-                                write!(f, "<")?;
-                                angle_open = true;
-                            }
-                            let name =
-                                f.db.type_alias_data(projection_pred.projection_ty.associated_ty)
-                                    .name
-                                    .clone();
-                            write!(f, "{} = ", name)?;
-                            projection_pred.ty.hir_fmt(f)?;
-                        }
-                        GenericPredicate::Error => {
-                            if angle_open {
-                                // impl Trait<X, {error}>
-                                write!(f, ", ")?;
-                            } else if !first {
-                                // impl Trait + {error}
-                                write!(f, " + ")?;
-                            }
-                            p.hir_fmt(f)?;
-                        }
-                    }
-                    first = false;
-                }
-                if angle_open {
-                    write!(f, ">")?;
-                }
-            }
-            Ty::Unknown => write!(f, "{{unknown}}")?,
-            Ty::Infer(..) => write!(f, "_")?,
-        }
-        Ok(())
-    }
-}
-
-impl TraitRef {
-    fn hir_fmt_ext(&self, f: &mut HirFormatter<impl HirDatabase>, use_as: bool) -> fmt::Result {
-        if f.should_truncate() {
-            return write!(f, "…");
-        }
-
-        self.substs[0].hir_fmt(f)?;
-        if use_as {
-            write!(f, " as ")?;
-        } else {
-            write!(f, ": ")?;
-        }
-        write!(f, "{}", f.db.trait_data(self.trait_).name.clone().unwrap_or_else(Name::missing))?;
-        if self.substs.len() > 1 {
-            write!(f, "<")?;
-            f.write_joined(&self.substs[1..], ", ")?;
-            write!(f, ">")?;
-        }
-        Ok(())
-    }
-}
-
-impl HirDisplay for TraitRef {
-    fn hir_fmt(&self, f: &mut HirFormatter<impl HirDatabase>) -> fmt::Result {
-        self.hir_fmt_ext(f, false)
-    }
-}
-
-impl HirDisplay for &GenericPredicate {
-    fn hir_fmt(&self, f: &mut HirFormatter<impl HirDatabase>) -> fmt::Result {
-        HirDisplay::hir_fmt(*self, f)
-    }
-}
-
-impl HirDisplay for GenericPredicate {
-    fn hir_fmt(&self, f: &mut HirFormatter<impl HirDatabase>) -> fmt::Result {
-        if f.should_truncate() {
-            return write!(f, "…");
-        }
-
-        match self {
-            GenericPredicate::Implemented(trait_ref) => trait_ref.hir_fmt(f)?,
-            GenericPredicate::Projection(projection_pred) => {
-                write!(f, "<")?;
-                projection_pred.projection_ty.trait_ref(f.db).hir_fmt_ext(f, true)?;
-                write!(
-                    f,
-                    ">::{} = {}",
-                    f.db.type_alias_data(projection_pred.projection_ty.associated_ty).name,
-                    projection_pred.ty.display(f.db)
-                )?;
-            }
-            GenericPredicate::Error => write!(f, "{{error}}")?,
-        }
-        Ok(())
-    }
-}
-
-impl HirDisplay for Obligation {
-    fn hir_fmt(&self, f: &mut HirFormatter<impl HirDatabase>) -> fmt::Result {
-        match self {
-            Obligation::Trait(tr) => write!(f, "Implements({})", tr.display(f.db)),
-            Obligation::Projection(proj) => write!(
-                f,
-                "Normalize({} => {})",
-                proj.projection_ty.display(f.db),
-                proj.ty.display(f.db)
-            ),
-        }
-    }
-}
+pub use hir_ty::*;
diff --git a/crates/ra_hir/src/ty/primitive.rs b/crates/ra_hir/src/ty/primitive.rs
deleted file mode 100644
index 12dc965725..0000000000
--- a/crates/ra_hir/src/ty/primitive.rs
+++ /dev/null
@@ -1,3 +0,0 @@
-//! FIXME: write short doc here
-
-pub use hir_ty::primitive::{FloatBitness, FloatTy, IntBitness, IntTy, Signedness, Uncertain};
diff --git a/crates/ra_hir/src/util.rs b/crates/ra_hir/src/util.rs
deleted file mode 100644
index 0095ee45d3..0000000000
--- a/crates/ra_hir/src/util.rs
+++ /dev/null
@@ -1,12 +0,0 @@
-//! Internal utility functions.
-
-use std::sync::Arc;
-
-/// Helper for mutating `Arc<[T]>` (i.e. `Arc::make_mut` for Arc slices).
-/// The underlying values are cloned if there are other strong references.
-pub(crate) fn make_mut_slice<T: Clone>(a: &mut Arc<[T]>) -> &mut [T] {
-    if Arc::get_mut(a).is_none() {
-        *a = a.iter().cloned().collect();
-    }
-    Arc::get_mut(a).unwrap()
-}
diff --git a/crates/ra_hir_def/src/lib.rs b/crates/ra_hir_def/src/lib.rs
index ea3f00bb33..ddf464c605 100644
--- a/crates/ra_hir_def/src/lib.rs
+++ b/crates/ra_hir_def/src/lib.rs
@@ -27,7 +27,7 @@ pub mod body;
 pub mod resolver;
 
 mod trace;
-mod nameres;
+pub mod nameres;
 
 #[cfg(test)]
 mod test_db;
diff --git a/crates/ra_hir_ty/Cargo.toml b/crates/ra_hir_ty/Cargo.toml
index 027b508657..429242870f 100644
--- a/crates/ra_hir_ty/Cargo.toml
+++ b/crates/ra_hir_ty/Cargo.toml
@@ -8,18 +8,18 @@ authors = ["rust-analyzer developers"]
 doctest = false
 
 [dependencies]
+arrayvec = "0.5.1"
+ena = "0.13"
 log = "0.4.5"
 rustc-hash = "1.0"
-parking_lot = "0.10.0"
-ena = "0.13"
 
-ra_syntax = { path = "../ra_syntax" }
+hir_def = { path = "../ra_hir_def", package = "ra_hir_def" }
+hir_expand = { path = "../ra_hir_expand", package = "ra_hir_expand" }
 ra_arena = { path = "../ra_arena" }
 ra_db = { path = "../ra_db" }
-hir_expand = { path = "../ra_hir_expand", package = "ra_hir_expand" }
-hir_def = { path = "../ra_hir_def", package = "ra_hir_def" }
-test_utils = { path = "../test_utils" }
 ra_prof = { path = "../ra_prof" }
+ra_syntax = { path = "../ra_syntax" }
+test_utils = { path = "../test_utils" }
 
 # https://github.com/rust-lang/chalk/pull/294
 chalk-solve =   { git = "https://github.com/jackh726/chalk.git", rev = "095cd38a4f16337913bba487f2055b9ca0179f30" }
diff --git a/crates/ra_hir/src/ty/autoderef.rs b/crates/ra_hir_ty/src/autoderef.rs
similarity index 99%
rename from crates/ra_hir/src/ty/autoderef.rs
rename to crates/ra_hir_ty/src/autoderef.rs
index ae68234aca..9d1d4e48c6 100644
--- a/crates/ra_hir/src/ty/autoderef.rs
+++ b/crates/ra_hir_ty/src/autoderef.rs
@@ -19,7 +19,7 @@ use super::{
 
 const AUTODEREF_RECURSION_LIMIT: usize = 10;
 
-pub(crate) fn autoderef<'a>(
+pub fn autoderef<'a>(
     db: &'a impl HirDatabase,
     krate: Option<CrateId>,
     ty: InEnvironment<Canonical<Ty>>,
diff --git a/crates/ra_hir_ty/src/db.rs b/crates/ra_hir_ty/src/db.rs
new file mode 100644
index 0000000000..aa2659c4bf
--- /dev/null
+++ b/crates/ra_hir_ty/src/db.rs
@@ -0,0 +1,116 @@
+//! FIXME: write short doc here
+
+use std::sync::Arc;
+
+use hir_def::{
+    db::DefDatabase, DefWithBodyId, GenericDefId, ImplId, LocalStructFieldId, TraitId, VariantId,
+};
+use ra_arena::map::ArenaMap;
+use ra_db::{salsa, CrateId};
+
+use crate::{
+    method_resolution::CrateImplBlocks,
+    traits::{AssocTyValue, Impl},
+    CallableDef, FnSig, GenericPredicate, InferenceResult, Substs, Ty, TyDefId, TypeCtor,
+    ValueTyDefId,
+};
+
+#[salsa::query_group(HirDatabaseStorage)]
+#[salsa::requires(salsa::Database)]
+pub trait HirDatabase: DefDatabase {
+    #[salsa::invoke(crate::infer_query)]
+    fn infer(&self, def: DefWithBodyId) -> Arc<InferenceResult>;
+
+    #[salsa::invoke(crate::lower::ty_query)]
+    fn ty(&self, def: TyDefId) -> Ty;
+
+    #[salsa::invoke(crate::lower::value_ty_query)]
+    fn value_ty(&self, def: ValueTyDefId) -> Ty;
+
+    #[salsa::invoke(crate::lower::field_types_query)]
+    fn field_types(&self, var: VariantId) -> Arc<ArenaMap<LocalStructFieldId, Ty>>;
+
+    #[salsa::invoke(crate::callable_item_sig)]
+    fn callable_item_signature(&self, def: CallableDef) -> FnSig;
+
+    #[salsa::invoke(crate::lower::generic_predicates_for_param_query)]
+    fn generic_predicates_for_param(
+        &self,
+        def: GenericDefId,
+        param_idx: u32,
+    ) -> Arc<[GenericPredicate]>;
+
+    #[salsa::invoke(crate::lower::generic_predicates_query)]
+    fn generic_predicates(&self, def: GenericDefId) -> Arc<[GenericPredicate]>;
+
+    #[salsa::invoke(crate::lower::generic_defaults_query)]
+    fn generic_defaults(&self, def: GenericDefId) -> Substs;
+
+    #[salsa::invoke(crate::method_resolution::CrateImplBlocks::impls_in_crate_query)]
+    fn impls_in_crate(&self, krate: CrateId) -> Arc<CrateImplBlocks>;
+
+    #[salsa::invoke(crate::traits::impls_for_trait_query)]
+    fn impls_for_trait(&self, krate: CrateId, trait_: TraitId) -> Arc<[ImplId]>;
+
+    /// This provides the Chalk trait solver instance. Because Chalk always
+    /// works from a specific crate, this query is keyed on the crate; and
+    /// because Chalk does its own internal caching, the solver is wrapped in a
+    /// Mutex and the query does an untracked read internally, to make sure the
+    /// cached state is thrown away when input facts change.
+    #[salsa::invoke(crate::traits::trait_solver_query)]
+    fn trait_solver(&self, krate: CrateId) -> crate::traits::TraitSolver;
+
+    // Interned IDs for Chalk integration
+    #[salsa::interned]
+    fn intern_type_ctor(&self, type_ctor: TypeCtor) -> crate::TypeCtorId;
+    #[salsa::interned]
+    fn intern_chalk_impl(&self, impl_: Impl) -> crate::traits::GlobalImplId;
+    #[salsa::interned]
+    fn intern_assoc_ty_value(&self, assoc_ty_value: AssocTyValue) -> crate::traits::AssocTyValueId;
+
+    #[salsa::invoke(crate::traits::chalk::associated_ty_data_query)]
+    fn associated_ty_data(
+        &self,
+        id: chalk_ir::TypeId,
+    ) -> Arc<chalk_rust_ir::AssociatedTyDatum<chalk_ir::family::ChalkIr>>;
+
+    #[salsa::invoke(crate::traits::chalk::trait_datum_query)]
+    fn trait_datum(
+        &self,
+        krate: CrateId,
+        trait_id: chalk_ir::TraitId,
+    ) -> Arc<chalk_rust_ir::TraitDatum<chalk_ir::family::ChalkIr>>;
+
+    #[salsa::invoke(crate::traits::chalk::struct_datum_query)]
+    fn struct_datum(
+        &self,
+        krate: CrateId,
+        struct_id: chalk_ir::StructId,
+    ) -> Arc<chalk_rust_ir::StructDatum<chalk_ir::family::ChalkIr>>;
+
+    #[salsa::invoke(crate::traits::chalk::impl_datum_query)]
+    fn impl_datum(
+        &self,
+        krate: CrateId,
+        impl_id: chalk_ir::ImplId,
+    ) -> Arc<chalk_rust_ir::ImplDatum<chalk_ir::family::ChalkIr>>;
+
+    #[salsa::invoke(crate::traits::chalk::associated_ty_value_query)]
+    fn associated_ty_value(
+        &self,
+        krate: CrateId,
+        id: chalk_rust_ir::AssociatedTyValueId,
+    ) -> Arc<chalk_rust_ir::AssociatedTyValue<chalk_ir::family::ChalkIr>>;
+
+    #[salsa::invoke(crate::traits::trait_solve_query)]
+    fn trait_solve(
+        &self,
+        krate: CrateId,
+        goal: crate::Canonical<crate::InEnvironment<crate::Obligation>>,
+    ) -> Option<crate::traits::Solution>;
+}
+
+#[test]
+fn hir_database_is_object_safe() {
+    fn _assert_object_safe(_: &dyn HirDatabase) {}
+}
diff --git a/crates/ra_hir_ty/src/diagnostics.rs b/crates/ra_hir_ty/src/diagnostics.rs
new file mode 100644
index 0000000000..4a13fac239
--- /dev/null
+++ b/crates/ra_hir_ty/src/diagnostics.rs
@@ -0,0 +1,91 @@
+//! FIXME: write short doc here
+
+use std::any::Any;
+
+use hir_expand::{db::AstDatabase, name::Name, HirFileId, Source};
+use ra_syntax::{ast, AstNode, AstPtr, SyntaxNodePtr};
+
+pub use hir_def::diagnostics::UnresolvedModule;
+pub use hir_expand::diagnostics::{AstDiagnostic, Diagnostic, DiagnosticSink};
+
+#[derive(Debug)]
+pub struct NoSuchField {
+    pub file: HirFileId,
+    pub field: AstPtr<ast::RecordField>,
+}
+
+impl Diagnostic for NoSuchField {
+    fn message(&self) -> String {
+        "no such field".to_string()
+    }
+
+    fn source(&self) -> Source<SyntaxNodePtr> {
+        Source { file_id: self.file, value: self.field.into() }
+    }
+
+    fn as_any(&self) -> &(dyn Any + Send + 'static) {
+        self
+    }
+}
+
+#[derive(Debug)]
+pub struct MissingFields {
+    pub file: HirFileId,
+    pub field_list: AstPtr<ast::RecordFieldList>,
+    pub missed_fields: Vec<Name>,
+}
+
+impl Diagnostic for MissingFields {
+    fn message(&self) -> String {
+        use std::fmt::Write;
+        let mut message = String::from("Missing structure fields:\n");
+        for field in &self.missed_fields {
+            write!(message, "- {}\n", field).unwrap();
+        }
+        message
+    }
+    fn source(&self) -> Source<SyntaxNodePtr> {
+        Source { file_id: self.file, value: self.field_list.into() }
+    }
+    fn as_any(&self) -> &(dyn Any + Send + 'static) {
+        self
+    }
+}
+
+impl AstDiagnostic for MissingFields {
+    type AST = ast::RecordFieldList;
+
+    fn ast(&self, db: &impl AstDatabase) -> Self::AST {
+        let root = db.parse_or_expand(self.source().file_id).unwrap();
+        let node = self.source().value.to_node(&root);
+        ast::RecordFieldList::cast(node).unwrap()
+    }
+}
+
+#[derive(Debug)]
+pub struct MissingOkInTailExpr {
+    pub file: HirFileId,
+    pub expr: AstPtr<ast::Expr>,
+}
+
+impl Diagnostic for MissingOkInTailExpr {
+    fn message(&self) -> String {
+        "wrap return expression in Ok".to_string()
+    }
+    fn source(&self) -> Source<SyntaxNodePtr> {
+        Source { file_id: self.file, value: self.expr.into() }
+    }
+    fn as_any(&self) -> &(dyn Any + Send + 'static) {
+        self
+    }
+}
+
+impl AstDiagnostic for MissingOkInTailExpr {
+    type AST = ast::Expr;
+
+    fn ast(&self, db: &impl AstDatabase) -> Self::AST {
+        let root = db.parse_or_expand(self.file).unwrap();
+        let node = self.source().value.to_node(&root);
+        ast::Expr::cast(node).unwrap()
+    }
+}
diff --git a/crates/ra_hir/src/ty/display.rs b/crates/ra_hir_ty/src/display.rs
similarity index 100%
rename from crates/ra_hir/src/ty/display.rs
rename to crates/ra_hir_ty/src/display.rs
diff --git a/crates/ra_hir/src/expr.rs b/crates/ra_hir_ty/src/expr.rs
similarity index 81%
rename from crates/ra_hir/src/expr.rs
rename to crates/ra_hir_ty/src/expr.rs
index 5c82c23d6c..5c65f93707 100644
--- a/crates/ra_hir/src/expr.rs
+++ b/crates/ra_hir_ty/src/expr.rs
@@ -2,8 +2,12 @@
 
 use std::sync::Arc;
 
-use hir_def::{path::known, resolver::HasResolver, AdtId};
-use hir_expand::diagnostics::DiagnosticSink;
+use hir_def::{
+    path::{known, Path},
+    resolver::HasResolver,
+    AdtId, FunctionId,
+};
+use hir_expand::{diagnostics::DiagnosticSink, name::Name};
 use ra_syntax::ast;
 use ra_syntax::AstPtr;
 use rustc_hash::FxHashSet;
@@ -11,8 +15,7 @@ use rustc_hash::FxHashSet;
 use crate::{
     db::HirDatabase,
     diagnostics::{MissingFields, MissingOkInTailExpr},
-    ty::{ApplicationTy, InferenceResult, Ty, TypeCtor},
-    Function, Name, Path, Struct,
+    ApplicationTy, InferenceResult, Ty, TypeCtor,
 };
 
 pub use hir_def::{
@@ -26,23 +29,23 @@ pub use hir_def::{
     },
 };
 
-pub(crate) struct ExprValidator<'a, 'b: 'a> {
-    func: Function,
+pub struct ExprValidator<'a, 'b: 'a> {
+    func: FunctionId,
     infer: Arc<InferenceResult>,
     sink: &'a mut DiagnosticSink<'b>,
 }
 
 impl<'a, 'b> ExprValidator<'a, 'b> {
-    pub(crate) fn new(
-        func: Function,
+    pub fn new(
+        func: FunctionId,
         infer: Arc<InferenceResult>,
         sink: &'a mut DiagnosticSink<'b>,
     ) -> ExprValidator<'a, 'b> {
         ExprValidator { func, infer, sink }
     }
 
-    pub(crate) fn validate_body(&mut self, db: &impl HirDatabase) {
-        let body = self.func.body(db);
+    pub fn validate_body(&mut self, db: &impl HirDatabase) {
+        let body = db.body(self.func.into());
 
         for e in body.exprs.iter() {
             if let (id, Expr::RecordLit { path, fields, spread }) = e {
@@ -69,16 +72,18 @@ impl<'a, 'b> ExprValidator<'a, 'b> {
         }
 
         let struct_def = match self.infer[id].as_adt() {
-            Some((AdtId::StructId(s), _)) => Struct::from(s),
+            Some((AdtId::StructId(s), _)) => s,
             _ => return,
         };
+        let struct_data = db.struct_data(struct_def);
 
         let lit_fields: FxHashSet<_> = fields.iter().map(|f| &f.name).collect();
-        let missed_fields: Vec<Name> = struct_def
-            .fields(db)
+        let missed_fields: Vec<Name> = struct_data
+            .variant_data
+            .fields()
             .iter()
-            .filter_map(|f| {
-                let name = f.name(db);
+            .filter_map(|(_f, d)| {
+                let name = d.name.clone();
                 if lit_fields.contains(&name) {
                     None
                 } else {
@@ -89,7 +94,7 @@ impl<'a, 'b> ExprValidator<'a, 'b> {
         if missed_fields.is_empty() {
             return;
         }
-        let source_map = self.func.body_source_map(db);
+        let (_, source_map) = db.body_with_source_map(self.func.into());
 
         if let Some(source_ptr) = source_map.expr_syntax(id) {
             if let Some(expr) = source_ptr.value.a() {
@@ -121,7 +126,7 @@ impl<'a, 'b> ExprValidator<'a, 'b> {
 
         let std_result_path = known::std_result_result();
 
-        let resolver = self.func.id.resolver(db);
+        let resolver = self.func.resolver(db);
         let std_result_enum = match resolver.resolve_known_enum(db, &std_result_path) {
             Some(it) => it,
             _ => return,
@@ -134,7 +139,7 @@ impl<'a, 'b> ExprValidator<'a, 'b> {
         };
 
         if params.len() == 2 && &params[0] == &mismatch.actual {
-            let source_map = self.func.body_source_map(db);
+            let (_, source_map) = db.body_with_source_map(self.func.into());
 
             if let Some(source_ptr) = source_map.expr_syntax(id) {
                 if let Some(expr) = source_ptr.value.a() {
diff --git a/crates/ra_hir/src/ty/infer.rs b/crates/ra_hir_ty/src/infer.rs
similarity index 98%
rename from crates/ra_hir/src/ty/infer.rs
rename to crates/ra_hir_ty/src/infer.rs
index 59e4e5f36b..1e9f4b208d 100644
--- a/crates/ra_hir/src/ty/infer.rs
+++ b/crates/ra_hir_ty/src/infer.rs
@@ -41,11 +41,11 @@ use super::{
     ApplicationTy, InEnvironment, ProjectionTy, Substs, TraitEnvironment, TraitRef, Ty, TypeCtor,
     TypeWalk, Uncertain,
 };
-use crate::{db::HirDatabase, ty::infer::diagnostics::InferenceDiagnostic};
+use crate::{db::HirDatabase, infer::diagnostics::InferenceDiagnostic};
 
 macro_rules! ty_app {
     ($ctor:pat, $param:pat) => {
-        crate::ty::Ty::Apply(crate::ty::ApplicationTy { ctor: $ctor, parameters: $param })
+        crate::Ty::Apply(crate::ApplicationTy { ctor: $ctor, parameters: $param })
     };
     ($ctor:pat) => {
         ty_app!($ctor, _)
@@ -128,8 +128,8 @@ pub struct InferenceResult {
     /// For each associated item record what it resolves to
     assoc_resolutions: FxHashMap<ExprOrPatId, AssocItemId>,
     diagnostics: Vec<InferenceDiagnostic>,
-    pub(super) type_of_expr: ArenaMap<ExprId, Ty>,
-    pub(super) type_of_pat: ArenaMap<PatId, Ty>,
+    pub type_of_expr: ArenaMap<ExprId, Ty>,
+    pub type_of_pat: ArenaMap<PatId, Ty>,
     pub(super) type_mismatches: ArenaMap<ExprId, TypeMismatch>,
 }
 
@@ -158,7 +158,7 @@ impl InferenceResult {
     pub fn type_mismatch_for_expr(&self, expr: ExprId) -> Option<&TypeMismatch> {
         self.type_mismatches.get(expr)
     }
-    pub(crate) fn add_diagnostics(
+    pub fn add_diagnostics(
         &self,
         db: &impl HirDatabase,
         owner: FunctionId,
diff --git a/crates/ra_hir/src/ty/infer/coerce.rs b/crates/ra_hir_ty/src/infer/coerce.rs
similarity index 99%
rename from crates/ra_hir/src/ty/infer/coerce.rs
rename to crates/ra_hir_ty/src/infer/coerce.rs
index 3fb5d8a83b..d66a21932f 100644
--- a/crates/ra_hir/src/ty/infer/coerce.rs
+++ b/crates/ra_hir_ty/src/infer/coerce.rs
@@ -13,10 +13,7 @@ use hir_def::{
 use rustc_hash::FxHashMap;
 use test_utils::tested_by;
 
-use crate::{
-    db::HirDatabase,
-    ty::{autoderef, Substs, TraitRef, Ty, TypeCtor, TypeWalk},
-};
+use crate::{autoderef, db::HirDatabase, Substs, TraitRef, Ty, TypeCtor, TypeWalk};
 
 use super::{InEnvironment, InferTy, InferenceContext, TypeVarValue};
 
diff --git a/crates/ra_hir/src/ty/infer/expr.rs b/crates/ra_hir_ty/src/infer/expr.rs
similarity index 99%
rename from crates/ra_hir/src/ty/infer/expr.rs
rename to crates/ra_hir_ty/src/infer/expr.rs
index f9ededa235..2f9ca4bbbf 100644
--- a/crates/ra_hir/src/ty/infer/expr.rs
+++ b/crates/ra_hir_ty/src/infer/expr.rs
@@ -14,12 +14,9 @@ use hir_def::{
 use hir_expand::name::{self, Name};
 
 use crate::{
-    db::HirDatabase,
-    ty::{
-        autoderef, method_resolution, op, traits::InEnvironment, utils::variant_data, CallableDef,
-        InferTy, IntTy, Mutability, Obligation, ProjectionPredicate, ProjectionTy, Substs,
-        TraitRef, Ty, TypeCtor, TypeWalk, Uncertain,
-    },
+    autoderef, db::HirDatabase, method_resolution, op, traits::InEnvironment, utils::variant_data,
+    CallableDef, InferTy, IntTy, Mutability, Obligation, ProjectionPredicate, ProjectionTy, Substs,
+    TraitRef, Ty, TypeCtor, TypeWalk, Uncertain,
 };
 
 use super::{BindingMode, Expectation, InferenceContext, InferenceDiagnostic, TypeMismatch};
diff --git a/crates/ra_hir/src/ty/infer/pat.rs b/crates/ra_hir_ty/src/infer/pat.rs
similarity index 98%
rename from crates/ra_hir/src/ty/infer/pat.rs
rename to crates/ra_hir_ty/src/infer/pat.rs
index a147746077..1ebb362399 100644
--- a/crates/ra_hir/src/ty/infer/pat.rs
+++ b/crates/ra_hir_ty/src/infer/pat.rs
@@ -12,10 +12,7 @@ use hir_expand::name::Name;
 use test_utils::tested_by;
 
 use super::{BindingMode, InferenceContext};
-use crate::{
-    db::HirDatabase,
-    ty::{utils::variant_data, Substs, Ty, TypeCtor, TypeWalk},
-};
+use crate::{db::HirDatabase, utils::variant_data, Substs, Ty, TypeCtor, TypeWalk};
 
 impl<'a, D: HirDatabase> InferenceContext<'a, D> {
     fn infer_tuple_struct_pat(
diff --git a/crates/ra_hir/src/ty/infer/path.rs b/crates/ra_hir_ty/src/infer/path.rs
similarity index 97%
rename from crates/ra_hir/src/ty/infer/path.rs
rename to crates/ra_hir_ty/src/infer/path.rs
index 09ff797288..e6676e1aa8 100644
--- a/crates/ra_hir/src/ty/infer/path.rs
+++ b/crates/ra_hir_ty/src/infer/path.rs
@@ -1,16 +1,13 @@
 //! Path expression resolution.
 
 use hir_def::{
-    path::{Path, PathSegment},
+    path::{Path, PathKind, PathSegment},
     resolver::{HasResolver, ResolveValueResult, Resolver, TypeNs, ValueNs},
     AssocItemId, ContainerId, Lookup,
 };
 use hir_expand::name::Name;
 
-use crate::{
-    db::HirDatabase,
-    ty::{method_resolution, Substs, Ty, TypeWalk, ValueTyDefId},
-};
+use crate::{db::HirDatabase, method_resolution, Substs, Ty, TypeWalk, ValueTyDefId};
 
 use super::{ExprOrPatId, InferenceContext, TraitRef};
 
@@ -33,7 +30,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
         path: &Path,
         id: ExprOrPatId,
     ) -> Option<Ty> {
-        let (value, self_subst) = if let crate::PathKind::Type(type_ref) = &path.kind {
+        let (value, self_subst) = if let PathKind::Type(type_ref) = &path.kind {
             if path.segments.is_empty() {
                 // This can't actually happen syntax-wise
                 return None;
diff --git a/crates/ra_hir/src/ty/infer/unify.rs b/crates/ra_hir_ty/src/infer/unify.rs
similarity index 96%
rename from crates/ra_hir/src/ty/infer/unify.rs
rename to crates/ra_hir_ty/src/infer/unify.rs
index e27bb2f825..f3a8756785 100644
--- a/crates/ra_hir/src/ty/infer/unify.rs
+++ b/crates/ra_hir_ty/src/infer/unify.rs
@@ -2,12 +2,8 @@
 
 use super::{InferenceContext, Obligation};
 use crate::{
-    db::HirDatabase,
-    ty::{
-        Canonical, InEnvironment, InferTy, ProjectionPredicate, ProjectionTy, Substs, TraitRef, Ty,
-        TypeWalk,
-    },
-    util::make_mut_slice,
+    db::HirDatabase, utils::make_mut_slice, Canonical, InEnvironment, InferTy, ProjectionPredicate,
+    ProjectionTy, Substs, TraitRef, Ty, TypeWalk,
 };
 
 impl<'a, D: HirDatabase> InferenceContext<'a, D> {
diff --git a/crates/ra_hir_ty/src/lib.rs b/crates/ra_hir_ty/src/lib.rs
index 28859ba636..f258463268 100644
--- a/crates/ra_hir_ty/src/lib.rs
+++ b/crates/ra_hir_ty/src/lib.rs
@@ -1,4 +1,1134 @@
-//! Work in Progress: everything related to types, type inference and trait
-//! solving.
+//! The type system. We currently use this to infer types for completion, hover
+//! information and various assists.
 
+macro_rules! impl_froms {
+    ($e:ident: $($v:ident $(($($sv:ident),*))?),*) => {
+        $(
+            impl From<$v> for $e {
+                fn from(it: $v) -> $e {
+                    $e::$v(it)
+                }
+            }
+            $($(
+                impl From<$sv> for $e {
+                    fn from(it: $sv) -> $e {
+                        $e::$v($v::$sv(it))
+                    }
+                }
+            )*)?
+        )*
+    }
+}
+
+mod autoderef;
 pub mod primitive;
+pub mod traits;
+pub mod method_resolution;
+mod op;
+mod lower;
+mod infer;
+pub mod display;
+pub(crate) mod utils;
+pub mod db;
+pub mod diagnostics;
+pub mod expr;
+
+#[cfg(test)]
+mod tests;
+#[cfg(test)]
+mod test_db;
+mod marks;
+
+use std::ops::Deref;
+use std::sync::Arc;
+use std::{fmt, iter, mem};
+
+use hir_def::{
+    expr::ExprId, generics::GenericParams, type_ref::Mutability, AdtId, ContainerId, DefWithBodyId,
+    GenericDefId, HasModule, Lookup, TraitId, TypeAliasId,
+};
+use hir_expand::name::Name;
+use ra_db::{impl_intern_key, salsa, CrateId};
+
+use crate::{
+    db::HirDatabase,
+    primitive::{FloatTy, IntTy, Uncertain},
+    utils::make_mut_slice,
+};
+use display::{HirDisplay, HirFormatter};
+
+pub use autoderef::autoderef;
+pub use infer::{infer_query, InferTy, InferenceResult};
+pub use lower::CallableDef;
+pub use lower::{callable_item_sig, TyDefId, ValueTyDefId};
+pub use traits::{InEnvironment, Obligation, ProjectionPredicate, TraitEnvironment};
+
+/// A type constructor or type name: this might be something like the primitive
+/// type `bool`, a struct like `Vec`, or things like function pointers or
+/// tuples.
+#[derive(Copy, Clone, PartialEq, Eq, Debug, Hash)]
+pub enum TypeCtor {
+    /// The primitive boolean type. Written as `bool`.
+    Bool,
+
+    /// The primitive character type; holds a Unicode scalar value
+    /// (a non-surrogate code point). Written as `char`.
+    Char,
+
+    /// A primitive integer type. For example, `i32`.
+    Int(Uncertain<IntTy>),
+
+    /// A primitive floating-point type. For example, `f64`.
+    Float(Uncertain<FloatTy>),
+
+    /// Structures, enumerations and unions.
+    Adt(AdtId),
+
+    /// The pointee of a string slice. Written as `str`.
+    Str,
+
+    /// The pointee of an array slice.  Written as `[T]`.
+    Slice,
+
+    /// An array with the given length. Written as `[T; n]`.
+    Array,
+
+    /// A raw pointer. Written as `*mut T` or `*const T`
+    RawPtr(Mutability),
+
+    /// A reference; a pointer with an associated lifetime. Written as
+    /// `&'a mut T` or `&'a T`.
+    Ref(Mutability),
+
+    /// 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(CallableDef),
+
+    /// 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;
+    /// ```
+    FnPtr { num_args: u16 },
+
+    /// The never type `!`.
+    Never,
+
+    /// A tuple type.  For example, `(i32, bool)`.
+    Tuple { cardinality: u16 },
+
+    /// 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(TypeAliasId),
+
+    /// The type of a specific closure.
+    ///
+    /// The closure signature is stored in a `FnPtr` type in the first type
+    /// parameter.
+    Closure { def: DefWithBodyId, expr: ExprId },
+}
+
+/// This exists just for Chalk, because Chalk just has a single `StructId` where
+/// we have different kinds of ADTs, primitive types and special type
+/// constructors like tuples and function pointers.
+#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
+pub struct TypeCtorId(salsa::InternId);
+impl_intern_key!(TypeCtorId);
+
+impl TypeCtor {
+    pub fn num_ty_params(self, db: &impl HirDatabase) -> usize {
+        match self {
+            TypeCtor::Bool
+            | TypeCtor::Char
+            | TypeCtor::Int(_)
+            | TypeCtor::Float(_)
+            | TypeCtor::Str
+            | TypeCtor::Never => 0,
+            TypeCtor::Slice
+            | TypeCtor::Array
+            | TypeCtor::RawPtr(_)
+            | TypeCtor::Ref(_)
+            | TypeCtor::Closure { .. } // 1 param representing the signature of the closure
+            => 1,
+            TypeCtor::Adt(adt) => {
+                let generic_params = db.generic_params(AdtId::from(adt).into());
+                generic_params.count_params_including_parent()
+            }
+            TypeCtor::FnDef(callable) => {
+                let generic_params = db.generic_params(callable.into());
+                generic_params.count_params_including_parent()
+            }
+            TypeCtor::AssociatedType(type_alias) => {
+                let generic_params = db.generic_params(type_alias.into());
+                generic_params.count_params_including_parent()
+            }
+            TypeCtor::FnPtr { num_args } => num_args as usize + 1,
+            TypeCtor::Tuple { cardinality } => cardinality as usize,
+        }
+    }
+
+    pub fn krate(self, db: &impl HirDatabase) -> Option<CrateId> {
+        match self {
+            TypeCtor::Bool
+            | TypeCtor::Char
+            | TypeCtor::Int(_)
+            | TypeCtor::Float(_)
+            | TypeCtor::Str
+            | TypeCtor::Never
+            | TypeCtor::Slice
+            | TypeCtor::Array
+            | TypeCtor::RawPtr(_)
+            | TypeCtor::Ref(_)
+            | TypeCtor::FnPtr { .. }
+            | TypeCtor::Tuple { .. } => None,
+            // Closure's krate is irrelevant for coherence I would think?
+            TypeCtor::Closure { .. } => None,
+            TypeCtor::Adt(adt) => Some(adt.module(db).krate),
+            TypeCtor::FnDef(callable) => Some(callable.krate(db)),
+            TypeCtor::AssociatedType(type_alias) => Some(type_alias.lookup(db).module(db).krate),
+        }
+    }
+
+    pub fn as_generic_def(self) -> Option<GenericDefId> {
+        match self {
+            TypeCtor::Bool
+            | TypeCtor::Char
+            | TypeCtor::Int(_)
+            | TypeCtor::Float(_)
+            | TypeCtor::Str
+            | TypeCtor::Never
+            | TypeCtor::Slice
+            | TypeCtor::Array
+            | TypeCtor::RawPtr(_)
+            | TypeCtor::Ref(_)
+            | TypeCtor::FnPtr { .. }
+            | TypeCtor::Tuple { .. }
+            | TypeCtor::Closure { .. } => None,
+            TypeCtor::Adt(adt) => Some(adt.into()),
+            TypeCtor::FnDef(callable) => Some(callable.into()),
+            TypeCtor::AssociatedType(type_alias) => Some(type_alias.into()),
+        }
+    }
+}
+
+/// A nominal type with (maybe 0) type parameters. This might be a primitive
+/// type like `bool`, a struct, tuple, function pointer, reference or
+/// several other things.
+#[derive(Clone, PartialEq, Eq, Debug, Hash)]
+pub struct ApplicationTy {
+    pub ctor: TypeCtor,
+    pub parameters: Substs,
+}
+
+/// 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: TypeAliasId,
+    pub parameters: Substs,
+}
+
+impl ProjectionTy {
+    pub fn trait_ref(&self, db: &impl HirDatabase) -> TraitRef {
+        TraitRef { trait_: self.trait_(db).into(), substs: self.parameters.clone() }
+    }
+
+    fn trait_(&self, db: &impl HirDatabase) -> TraitId {
+        match self.associated_ty.lookup(db).container {
+            ContainerId::TraitId(it) => it,
+            _ => panic!("projection ty without parent trait"),
+        }
+    }
+}
+
+impl TypeWalk for ProjectionTy {
+    fn walk(&self, f: &mut impl FnMut(&Ty)) {
+        self.parameters.walk(f);
+    }
+
+    fn walk_mut_binders(&mut self, f: &mut impl FnMut(&mut Ty, usize), binders: usize) {
+        self.parameters.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 Ty {
+    /// A nominal type with (maybe 0) type parameters. This might be a primitive
+    /// type like `bool`, a struct, tuple, function pointer, reference or
+    /// several other things.
+    Apply(ApplicationTy),
+
+    /// 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),
+
+    /// A type parameter; for example, `T` in `fn f<T>(x: T) {}
+    Param {
+        /// The index of the parameter (starting with parameters from the
+        /// surrounding impl, then the current function).
+        idx: u32,
+        /// The name of the parameter, for displaying.
+        // FIXME get rid of this
+        name: Name,
+    },
+
+    /// A bound type variable. Used during trait resolution to represent Chalk
+    /// variables, and in `Dyn` and `Opaque` bounds to represent the `Self` type.
+    Bound(u32),
+
+    /// A type variable used during type checking. Not to be confused with a
+    /// type parameter.
+    Infer(InferTy),
+
+    /// 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(Arc<[GenericPredicate]>),
+
+    /// An opaque type (`impl Trait`).
+    ///
+    /// The predicates are quantified over the `Self` type; see `Ty::Dyn` for
+    /// more.
+    Opaque(Arc<[GenericPredicate]>),
+
+    /// 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,
+}
+
+/// A list of substitutions for generic parameters.
+#[derive(Clone, PartialEq, Eq, Debug, Hash)]
+pub struct Substs(Arc<[Ty]>);
+
+impl TypeWalk for Substs {
+    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, usize), binders: usize) {
+        for t in make_mut_slice(&mut self.0) {
+            t.walk_mut_binders(f, binders);
+        }
+    }
+}
+
+impl Substs {
+    pub fn empty() -> Substs {
+        Substs(Arc::new([]))
+    }
+
+    pub fn single(ty: Ty) -> Substs {
+        Substs(Arc::new([ty]))
+    }
+
+    pub fn prefix(&self, n: usize) -> Substs {
+        Substs(self.0[..std::cmp::min(self.0.len(), n)].into())
+    }
+
+    pub fn as_single(&self) -> &Ty {
+        if self.0.len() != 1 {
+            panic!("expected substs of len 1, got {:?}", self);
+        }
+        &self.0[0]
+    }
+
+    /// Return Substs that replace each parameter by itself (i.e. `Ty::Param`).
+    pub fn identity(generic_params: &GenericParams) -> Substs {
+        Substs(
+            generic_params
+                .params_including_parent()
+                .into_iter()
+                .map(|p| Ty::Param { idx: p.idx, name: p.name.clone() })
+                .collect(),
+        )
+    }
+
+    /// Return Substs that replace each parameter by a bound variable.
+    pub fn bound_vars(generic_params: &GenericParams) -> Substs {
+        Substs(
+            generic_params
+                .params_including_parent()
+                .into_iter()
+                .map(|p| Ty::Bound(p.idx))
+                .collect(),
+        )
+    }
+
+    pub fn build_for_def(db: &impl HirDatabase, def: impl Into<GenericDefId>) -> SubstsBuilder {
+        let def = def.into();
+        let params = db.generic_params(def);
+        let param_count = params.count_params_including_parent();
+        Substs::builder(param_count)
+    }
+
+    pub fn build_for_generics(generic_params: &GenericParams) -> SubstsBuilder {
+        Substs::builder(generic_params.count_params_including_parent())
+    }
+
+    pub fn build_for_type_ctor(db: &impl HirDatabase, type_ctor: TypeCtor) -> SubstsBuilder {
+        Substs::builder(type_ctor.num_ty_params(db))
+    }
+
+    fn builder(param_count: usize) -> SubstsBuilder {
+        SubstsBuilder { vec: Vec::with_capacity(param_count), param_count }
+    }
+}
+
+#[derive(Debug, Clone)]
+pub struct SubstsBuilder {
+    vec: Vec<Ty>,
+    param_count: usize,
+}
+
+impl SubstsBuilder {
+    pub fn build(self) -> Substs {
+        assert_eq!(self.vec.len(), self.param_count);
+        Substs(self.vec.into())
+    }
+
+    pub fn push(mut self, ty: Ty) -> Self {
+        self.vec.push(ty);
+        self
+    }
+
+    fn remaining(&self) -> usize {
+        self.param_count - self.vec.len()
+    }
+
+    pub fn fill_with_bound_vars(self, starting_from: u32) -> Self {
+        self.fill((starting_from..).map(Ty::Bound))
+    }
+
+    pub fn fill_with_params(self) -> Self {
+        let start = self.vec.len() as u32;
+        self.fill((start..).map(|idx| Ty::Param { idx, name: Name::missing() }))
+    }
+
+    pub fn fill_with_unknown(self) -> Self {
+        self.fill(iter::repeat(Ty::Unknown))
+    }
+
+    pub fn fill(mut self, filler: impl Iterator<Item = Ty>) -> Self {
+        self.vec.extend(filler.take(self.remaining()));
+        assert_eq!(self.remaining(), 0);
+        self
+    }
+
+    pub fn use_parent_substs(mut self, parent_substs: &Substs) -> Self {
+        assert!(self.vec.is_empty());
+        assert!(parent_substs.len() <= self.param_count);
+        self.vec.extend(parent_substs.iter().cloned());
+        self
+    }
+}
+
+impl Deref for Substs {
+    type Target = [Ty];
+
+    fn deref(&self) -> &[Ty] {
+        &self.0
+    }
+}
+
+/// A trait with type parameters. This includes the `Self`, so this represents a concrete type implementing the trait.
+/// Name to be bikeshedded: TraitBound? TraitImplements?
+#[derive(Clone, PartialEq, Eq, Debug, Hash)]
+pub struct TraitRef {
+    /// FIXME name?
+    pub trait_: TraitId,
+    pub substs: Substs,
+}
+
+impl TraitRef {
+    pub fn self_ty(&self) -> &Ty {
+        &self.substs[0]
+    }
+}
+
+impl TypeWalk for TraitRef {
+    fn walk(&self, f: &mut impl FnMut(&Ty)) {
+        self.substs.walk(f);
+    }
+
+    fn walk_mut_binders(&mut self, f: &mut impl FnMut(&mut Ty, usize), binders: usize) {
+        self.substs.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 GenericPredicate {
+    /// The given trait needs to be implemented for its type parameters.
+    Implemented(TraitRef),
+    /// An associated type bindings like in `Iterator<Item = T>`.
+    Projection(ProjectionPredicate),
+    /// We couldn't resolve the trait reference. (If some type parameters can't
+    /// be resolved, they will just be Unknown).
+    Error,
+}
+
+impl GenericPredicate {
+    pub fn is_error(&self) -> bool {
+        match self {
+            GenericPredicate::Error => true,
+            _ => false,
+        }
+    }
+
+    pub fn is_implemented(&self) -> bool {
+        match self {
+            GenericPredicate::Implemented(_) => true,
+            _ => false,
+        }
+    }
+
+    pub fn trait_ref(&self, db: &impl HirDatabase) -> Option<TraitRef> {
+        match self {
+            GenericPredicate::Implemented(tr) => Some(tr.clone()),
+            GenericPredicate::Projection(proj) => Some(proj.projection_ty.trait_ref(db)),
+            GenericPredicate::Error => None,
+        }
+    }
+}
+
+impl TypeWalk for GenericPredicate {
+    fn walk(&self, f: &mut impl FnMut(&Ty)) {
+        match self {
+            GenericPredicate::Implemented(trait_ref) => trait_ref.walk(f),
+            GenericPredicate::Projection(projection_pred) => projection_pred.walk(f),
+            GenericPredicate::Error => {}
+        }
+    }
+
+    fn walk_mut_binders(&mut self, f: &mut impl FnMut(&mut Ty, usize), binders: usize) {
+        match self {
+            GenericPredicate::Implemented(trait_ref) => trait_ref.walk_mut_binders(f, binders),
+            GenericPredicate::Projection(projection_pred) => {
+                projection_pred.walk_mut_binders(f, binders)
+            }
+            GenericPredicate::Error => {}
+        }
+    }
+}
+
+/// 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 `num_vars` tells us how
+/// many there are. 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 num_vars: usize,
+}
+
+/// A function signature as seen by type inference: Several parameter types and
+/// one return type.
+#[derive(Clone, PartialEq, Eq, Debug)]
+pub struct FnSig {
+    params_and_return: Arc<[Ty]>,
+}
+
+impl FnSig {
+    pub fn from_params_and_return(mut params: Vec<Ty>, ret: Ty) -> FnSig {
+        params.push(ret);
+        FnSig { params_and_return: params.into() }
+    }
+
+    pub fn from_fn_ptr_substs(substs: &Substs) -> FnSig {
+        FnSig { params_and_return: Arc::clone(&substs.0) }
+    }
+
+    pub fn params(&self) -> &[Ty] {
+        &self.params_and_return[0..self.params_and_return.len() - 1]
+    }
+
+    pub fn ret(&self) -> &Ty {
+        &self.params_and_return[self.params_and_return.len() - 1]
+    }
+}
+
+impl TypeWalk for FnSig {
+    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, usize), binders: usize) {
+        for t in make_mut_slice(&mut self.params_and_return) {
+            t.walk_mut_binders(f, binders);
+        }
+    }
+}
+
+impl Ty {
+    pub fn simple(ctor: TypeCtor) -> Ty {
+        Ty::Apply(ApplicationTy { ctor, parameters: Substs::empty() })
+    }
+    pub fn apply_one(ctor: TypeCtor, param: Ty) -> Ty {
+        Ty::Apply(ApplicationTy { ctor, parameters: Substs::single(param) })
+    }
+    pub fn apply(ctor: TypeCtor, parameters: Substs) -> Ty {
+        Ty::Apply(ApplicationTy { ctor, parameters })
+    }
+    pub fn unit() -> Self {
+        Ty::apply(TypeCtor::Tuple { cardinality: 0 }, Substs::empty())
+    }
+
+    pub fn as_reference(&self) -> Option<(&Ty, Mutability)> {
+        match self {
+            Ty::Apply(ApplicationTy { ctor: TypeCtor::Ref(mutability), parameters }) => {
+                Some((parameters.as_single(), *mutability))
+            }
+            _ => None,
+        }
+    }
+
+    pub fn as_adt(&self) -> Option<(AdtId, &Substs)> {
+        match self {
+            Ty::Apply(ApplicationTy { ctor: TypeCtor::Adt(adt_def), parameters }) => {
+                Some((*adt_def, parameters))
+            }
+            _ => None,
+        }
+    }
+
+    pub fn as_tuple(&self) -> Option<&Substs> {
+        match self {
+            Ty::Apply(ApplicationTy { ctor: TypeCtor::Tuple { .. }, parameters }) => {
+                Some(parameters)
+            }
+            _ => None,
+        }
+    }
+
+    pub fn as_callable(&self) -> Option<(CallableDef, &Substs)> {
+        match self {
+            Ty::Apply(ApplicationTy { ctor: TypeCtor::FnDef(callable_def), parameters }) => {
+                Some((*callable_def, parameters))
+            }
+            _ => None,
+        }
+    }
+
+    fn builtin_deref(&self) -> Option<Ty> {
+        match self {
+            Ty::Apply(a_ty) => match a_ty.ctor {
+                TypeCtor::Ref(..) => Some(Ty::clone(a_ty.parameters.as_single())),
+                TypeCtor::RawPtr(..) => Some(Ty::clone(a_ty.parameters.as_single())),
+                _ => None,
+            },
+            _ => None,
+        }
+    }
+
+    fn callable_sig(&self, db: &impl HirDatabase) -> Option<FnSig> {
+        match self {
+            Ty::Apply(a_ty) => match a_ty.ctor {
+                TypeCtor::FnPtr { .. } => Some(FnSig::from_fn_ptr_substs(&a_ty.parameters)),
+                TypeCtor::FnDef(def) => {
+                    let sig = db.callable_item_signature(def);
+                    Some(sig.subst(&a_ty.parameters))
+                }
+                TypeCtor::Closure { .. } => {
+                    let sig_param = &a_ty.parameters[0];
+                    sig_param.callable_sig(db)
+                }
+                _ => None,
+            },
+            _ => None,
+        }
+    }
+
+    /// If this is a type with type parameters (an ADT or function), replaces
+    /// the `Substs` for these type parameters with the given ones. (So e.g. if
+    /// `self` is `Option<_>` and the substs contain `u32`, we'll have
+    /// `Option<u32>` afterwards.)
+    pub fn apply_substs(self, substs: Substs) -> Ty {
+        match self {
+            Ty::Apply(ApplicationTy { ctor, parameters: previous_substs }) => {
+                assert_eq!(previous_substs.len(), substs.len());
+                Ty::Apply(ApplicationTy { ctor, parameters: substs })
+            }
+            _ => self,
+        }
+    }
+
+    /// Returns the type parameters of this type if it has some (i.e. is an ADT
+    /// or function); so if `self` is `Option<u32>`, this returns the `u32`.
+    pub fn substs(&self) -> Option<Substs> {
+        match self {
+            Ty::Apply(ApplicationTy { parameters, .. }) => Some(parameters.clone()),
+            _ => None,
+        }
+    }
+
+    /// If this is an `impl Trait` or `dyn Trait`, returns that trait.
+    pub fn inherent_trait(&self) -> Option<TraitId> {
+        match self {
+            Ty::Dyn(predicates) | Ty::Opaque(predicates) => {
+                predicates.iter().find_map(|pred| match pred {
+                    GenericPredicate::Implemented(tr) => Some(tr.trait_),
+                    _ => None,
+                })
+            }
+            _ => None,
+        }
+    }
+}
+
+/// 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), 0);
+    }
+    /// Walk the type, counting entered binders.
+    ///
+    /// `Ty::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 `Ty::Dyn` and `Ty::Opaque`, which each introduce a bound
+    /// variable for the self type.
+    fn walk_mut_binders(&mut self, f: &mut impl FnMut(&mut Ty, usize), binders: usize);
+
+    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, Ty::Unknown);
+            *ty_mut = f(ty);
+        });
+        self
+    }
+
+    /// Replaces type parameters in this type using the given `Substs`. (So e.g.
+    /// if `self` is `&[T]`, where type parameter T has index 0, and the
+    /// `Substs` contain `u32` at index 0, we'll have `&[u32]` afterwards.)
+    fn subst(self, substs: &Substs) -> Self
+    where
+        Self: Sized,
+    {
+        self.fold(&mut |ty| match ty {
+            Ty::Param { idx, name } => {
+                substs.get(idx as usize).cloned().unwrap_or(Ty::Param { idx, name })
+            }
+            ty => ty,
+        })
+    }
+
+    /// Substitutes `Ty::Bound` vars (as opposed to type parameters).
+    fn subst_bound_vars(mut self, substs: &Substs) -> Self
+    where
+        Self: Sized,
+    {
+        self.walk_mut_binders(
+            &mut |ty, binders| match ty {
+                &mut Ty::Bound(idx) => {
+                    if idx as usize >= binders && (idx as usize - binders) < substs.len() {
+                        *ty = substs.0[idx as usize - binders].clone();
+                    }
+                }
+                _ => {}
+            },
+            0,
+        );
+        self
+    }
+
+    /// Shifts up `Ty::Bound` vars by `n`.
+    fn shift_bound_vars(self, n: i32) -> Self
+    where
+        Self: Sized,
+    {
+        self.fold(&mut |ty| match ty {
+            Ty::Bound(idx) => {
+                assert!(idx as i32 >= -n);
+                Ty::Bound((idx as i32 + n) as u32)
+            }
+            ty => ty,
+        })
+    }
+}
+
+impl TypeWalk for Ty {
+    fn walk(&self, f: &mut impl FnMut(&Ty)) {
+        match self {
+            Ty::Apply(a_ty) => {
+                for t in a_ty.parameters.iter() {
+                    t.walk(f);
+                }
+            }
+            Ty::Projection(p_ty) => {
+                for t in p_ty.parameters.iter() {
+                    t.walk(f);
+                }
+            }
+            Ty::Dyn(predicates) | Ty::Opaque(predicates) => {
+                for p in predicates.iter() {
+                    p.walk(f);
+                }
+            }
+            Ty::Param { .. } | Ty::Bound(_) | Ty::Infer(_) | Ty::Unknown => {}
+        }
+        f(self);
+    }
+
+    fn walk_mut_binders(&mut self, f: &mut impl FnMut(&mut Ty, usize), binders: usize) {
+        match self {
+            Ty::Apply(a_ty) => {
+                a_ty.parameters.walk_mut_binders(f, binders);
+            }
+            Ty::Projection(p_ty) => {
+                p_ty.parameters.walk_mut_binders(f, binders);
+            }
+            Ty::Dyn(predicates) | Ty::Opaque(predicates) => {
+                for p in make_mut_slice(predicates) {
+                    p.walk_mut_binders(f, binders + 1);
+                }
+            }
+            Ty::Param { .. } | Ty::Bound(_) | Ty::Infer(_) | Ty::Unknown => {}
+        }
+        f(self, binders);
+    }
+}
+
+impl HirDisplay for &Ty {
+    fn hir_fmt(&self, f: &mut HirFormatter<impl HirDatabase>) -> fmt::Result {
+        HirDisplay::hir_fmt(*self, f)
+    }
+}
+
+impl HirDisplay for ApplicationTy {
+    fn hir_fmt(&self, f: &mut HirFormatter<impl HirDatabase>) -> fmt::Result {
+        if f.should_truncate() {
+            return write!(f, "…");
+        }
+
+        match self.ctor {
+            TypeCtor::Bool => write!(f, "bool")?,
+            TypeCtor::Char => write!(f, "char")?,
+            TypeCtor::Int(t) => write!(f, "{}", t)?,
+            TypeCtor::Float(t) => write!(f, "{}", t)?,
+            TypeCtor::Str => write!(f, "str")?,
+            TypeCtor::Slice => {
+                let t = self.parameters.as_single();
+                write!(f, "[{}]", t.display(f.db))?;
+            }
+            TypeCtor::Array => {
+                let t = self.parameters.as_single();
+                write!(f, "[{};_]", t.display(f.db))?;
+            }
+            TypeCtor::RawPtr(m) => {
+                let t = self.parameters.as_single();
+                write!(f, "*{}{}", m.as_keyword_for_ptr(), t.display(f.db))?;
+            }
+            TypeCtor::Ref(m) => {
+                let t = self.parameters.as_single();
+                write!(f, "&{}{}", m.as_keyword_for_ref(), t.display(f.db))?;
+            }
+            TypeCtor::Never => write!(f, "!")?,
+            TypeCtor::Tuple { .. } => {
+                let ts = &self.parameters;
+                if ts.len() == 1 {
+                    write!(f, "({},)", ts[0].display(f.db))?;
+                } else {
+                    write!(f, "(")?;
+                    f.write_joined(&*ts.0, ", ")?;
+                    write!(f, ")")?;
+                }
+            }
+            TypeCtor::FnPtr { .. } => {
+                let sig = FnSig::from_fn_ptr_substs(&self.parameters);
+                write!(f, "fn(")?;
+                f.write_joined(sig.params(), ", ")?;
+                write!(f, ") -> {}", sig.ret().display(f.db))?;
+            }
+            TypeCtor::FnDef(def) => {
+                let sig = f.db.callable_item_signature(def);
+                let name = match def {
+                    CallableDef::FunctionId(ff) => f.db.function_data(ff).name.clone(),
+                    CallableDef::StructId(s) => {
+                        f.db.struct_data(s).name.clone().unwrap_or_else(Name::missing)
+                    }
+                    CallableDef::EnumVariantId(e) => {
+                        let enum_data = f.db.enum_data(e.parent);
+                        enum_data.variants[e.local_id].name.clone().unwrap_or_else(Name::missing)
+                    }
+                };
+                match def {
+                    CallableDef::FunctionId(_) => write!(f, "fn {}", name)?,
+                    CallableDef::StructId(_) | CallableDef::EnumVariantId(_) => {
+                        write!(f, "{}", name)?
+                    }
+                }
+                if self.parameters.len() > 0 {
+                    write!(f, "<")?;
+                    f.write_joined(&*self.parameters.0, ", ")?;
+                    write!(f, ">")?;
+                }
+                write!(f, "(")?;
+                f.write_joined(sig.params(), ", ")?;
+                write!(f, ") -> {}", sig.ret().display(f.db))?;
+            }
+            TypeCtor::Adt(def_id) => {
+                let name = match def_id {
+                    AdtId::StructId(it) => f.db.struct_data(it).name.clone(),
+                    AdtId::UnionId(it) => f.db.union_data(it).name.clone(),
+                    AdtId::EnumId(it) => f.db.enum_data(it).name.clone(),
+                }
+                .unwrap_or_else(Name::missing);
+                write!(f, "{}", name)?;
+                if self.parameters.len() > 0 {
+                    write!(f, "<")?;
+                    f.write_joined(&*self.parameters.0, ", ")?;
+                    write!(f, ">")?;
+                }
+            }
+            TypeCtor::AssociatedType(type_alias) => {
+                let trait_ = match type_alias.lookup(f.db).container {
+                    ContainerId::TraitId(it) => it,
+                    _ => panic!("not an associated type"),
+                };
+                let trait_name = f.db.trait_data(trait_).name.clone().unwrap_or_else(Name::missing);
+                let name = f.db.type_alias_data(type_alias).name.clone();
+                write!(f, "{}::{}", trait_name, name)?;
+                if self.parameters.len() > 0 {
+                    write!(f, "<")?;
+                    f.write_joined(&*self.parameters.0, ", ")?;
+                    write!(f, ">")?;
+                }
+            }
+            TypeCtor::Closure { .. } => {
+                let sig = self.parameters[0]
+                    .callable_sig(f.db)
+                    .expect("first closure parameter should contain signature");
+                write!(f, "|")?;
+                f.write_joined(sig.params(), ", ")?;
+                write!(f, "| -> {}", sig.ret().display(f.db))?;
+            }
+        }
+        Ok(())
+    }
+}
+
+impl HirDisplay for ProjectionTy {
+    fn hir_fmt(&self, f: &mut HirFormatter<impl HirDatabase>) -> fmt::Result {
+        if f.should_truncate() {
+            return write!(f, "…");
+        }
+
+        let trait_name =
+            f.db.trait_data(self.trait_(f.db)).name.clone().unwrap_or_else(Name::missing);
+        write!(f, "<{} as {}", self.parameters[0].display(f.db), trait_name,)?;
+        if self.parameters.len() > 1 {
+            write!(f, "<")?;
+            f.write_joined(&self.parameters[1..], ", ")?;
+            write!(f, ">")?;
+        }
+        write!(f, ">::{}", f.db.type_alias_data(self.associated_ty).name)?;
+        Ok(())
+    }
+}
+
+impl HirDisplay for Ty {
+    fn hir_fmt(&self, f: &mut HirFormatter<impl HirDatabase>) -> fmt::Result {
+        if f.should_truncate() {
+            return write!(f, "…");
+        }
+
+        match self {
+            Ty::Apply(a_ty) => a_ty.hir_fmt(f)?,
+            Ty::Projection(p_ty) => p_ty.hir_fmt(f)?,
+            Ty::Param { name, .. } => write!(f, "{}", name)?,
+            Ty::Bound(idx) => write!(f, "?{}", idx)?,
+            Ty::Dyn(predicates) | Ty::Opaque(predicates) => {
+                match self {
+                    Ty::Dyn(_) => write!(f, "dyn ")?,
+                    Ty::Opaque(_) => write!(f, "impl ")?,
+                    _ => unreachable!(),
+                };
+                // Note: This code is written to produce nice results (i.e.
+                // corresponding to surface Rust) for types that can occur in
+                // actual Rust. It will have weird results if the predicates
+                // aren't as expected (i.e. self types = $0, projection
+                // predicates for a certain trait come after the Implemented
+                // predicate for that trait).
+                let mut first = true;
+                let mut angle_open = false;
+                for p in predicates.iter() {
+                    match p {
+                        GenericPredicate::Implemented(trait_ref) => {
+                            if angle_open {
+                                write!(f, ">")?;
+                            }
+                            if !first {
+                                write!(f, " + ")?;
+                            }
+                            // We assume that the self type is $0 (i.e. the
+                            // existential) here, which is the only thing that's
+                            // possible in actual Rust, and hence don't print it
+                            write!(
+                                f,
+                                "{}",
+                                f.db.trait_data(trait_ref.trait_)
+                                    .name
+                                    .clone()
+                                    .unwrap_or_else(Name::missing)
+                            )?;
+                            if trait_ref.substs.len() > 1 {
+                                write!(f, "<")?;
+                                f.write_joined(&trait_ref.substs[1..], ", ")?;
+                                // there might be assoc type bindings, so we leave the angle brackets open
+                                angle_open = true;
+                            }
+                        }
+                        GenericPredicate::Projection(projection_pred) => {
+                            // in types in actual Rust, these will always come
+                            // after the corresponding Implemented predicate
+                            if angle_open {
+                                write!(f, ", ")?;
+                            } else {
+                                write!(f, "<")?;
+                                angle_open = true;
+                            }
+                            let name =
+                                f.db.type_alias_data(projection_pred.projection_ty.associated_ty)
+                                    .name
+                                    .clone();
+                            write!(f, "{} = ", name)?;
+                            projection_pred.ty.hir_fmt(f)?;
+                        }
+                        GenericPredicate::Error => {
+                            if angle_open {
+                                // impl Trait<X, {error}>
+                                write!(f, ", ")?;
+                            } else if !first {
+                                // impl Trait + {error}
+                                write!(f, " + ")?;
+                            }
+                            p.hir_fmt(f)?;
+                        }
+                    }
+                    first = false;
+                }
+                if angle_open {
+                    write!(f, ">")?;
+                }
+            }
+            Ty::Unknown => write!(f, "{{unknown}}")?,
+            Ty::Infer(..) => write!(f, "_")?,
+        }
+        Ok(())
+    }
+}
+
+impl TraitRef {
+    fn hir_fmt_ext(&self, f: &mut HirFormatter<impl HirDatabase>, use_as: bool) -> fmt::Result {
+        if f.should_truncate() {
+            return write!(f, "…");
+        }
+
+        self.substs[0].hir_fmt(f)?;
+        if use_as {
+            write!(f, " as ")?;
+        } else {
+            write!(f, ": ")?;
+        }
+        write!(f, "{}", f.db.trait_data(self.trait_).name.clone().unwrap_or_else(Name::missing))?;
+        if self.substs.len() > 1 {
+            write!(f, "<")?;
+            f.write_joined(&self.substs[1..], ", ")?;
+            write!(f, ">")?;
+        }
+        Ok(())
+    }
+}
+
+impl HirDisplay for TraitRef {
+    fn hir_fmt(&self, f: &mut HirFormatter<impl HirDatabase>) -> fmt::Result {
+        self.hir_fmt_ext(f, false)
+    }
+}
+
+impl HirDisplay for &GenericPredicate {
+    fn hir_fmt(&self, f: &mut HirFormatter<impl HirDatabase>) -> fmt::Result {
+        HirDisplay::hir_fmt(*self, f)
+    }
+}
+
+impl HirDisplay for GenericPredicate {
+    fn hir_fmt(&self, f: &mut HirFormatter<impl HirDatabase>) -> fmt::Result {
+        if f.should_truncate() {
+            return write!(f, "…");
+        }
+
+        match self {
+            GenericPredicate::Implemented(trait_ref) => trait_ref.hir_fmt(f)?,
+            GenericPredicate::Projection(projection_pred) => {
+                write!(f, "<")?;
+                projection_pred.projection_ty.trait_ref(f.db).hir_fmt_ext(f, true)?;
+                write!(
+                    f,
+                    ">::{} = {}",
+                    f.db.type_alias_data(projection_pred.projection_ty.associated_ty).name,
+                    projection_pred.ty.display(f.db)
+                )?;
+            }
+            GenericPredicate::Error => write!(f, "{{error}}")?,
+        }
+        Ok(())
+    }
+}
+
+impl HirDisplay for Obligation {
+    fn hir_fmt(&self, f: &mut HirFormatter<impl HirDatabase>) -> fmt::Result {
+        match self {
+            Obligation::Trait(tr) => write!(f, "Implements({})", tr.display(f.db)),
+            Obligation::Projection(proj) => write!(
+                f,
+                "Normalize({} => {})",
+                proj.projection_ty.display(f.db),
+                proj.ty.display(f.db)
+            ),
+        }
+    }
+}
diff --git a/crates/ra_hir/src/ty/lower.rs b/crates/ra_hir_ty/src/lower.rs
similarity index 94%
rename from crates/ra_hir/src/ty/lower.rs
rename to crates/ra_hir_ty/src/lower.rs
index 5dce2f3423..53d955a124 100644
--- a/crates/ra_hir/src/ty/lower.rs
+++ b/crates/ra_hir_ty/src/lower.rs
@@ -11,7 +11,7 @@ use std::sync::Arc;
 use hir_def::{
     builtin_type::BuiltinType,
     generics::WherePredicate,
-    path::{GenericArg, Path, PathSegment},
+    path::{GenericArg, Path, PathKind, PathSegment},
     resolver::{HasResolver, Resolver, TypeNs},
     type_ref::{TypeBound, TypeRef},
     AdtId, AstItemDef, ConstId, EnumId, EnumVariantId, FunctionId, GenericDefId, HasModule,
@@ -26,16 +26,13 @@ use super::{
 };
 use crate::{
     db::HirDatabase,
-    ty::{
-        primitive::{FloatTy, IntTy},
-        utils::{all_super_traits, associated_type_by_name_including_super_traits, variant_data},
-    },
-    util::make_mut_slice,
-    ImplBlock, Trait,
+    primitive::{FloatTy, IntTy},
+    utils::make_mut_slice,
+    utils::{all_super_traits, associated_type_by_name_including_super_traits, variant_data},
 };
 
 impl Ty {
-    pub(crate) fn from_hir(db: &impl HirDatabase, resolver: &Resolver, type_ref: &TypeRef) -> Self {
+    pub fn from_hir(db: &impl HirDatabase, resolver: &Resolver, type_ref: &TypeRef) -> Self {
         match type_ref {
             TypeRef::Never => Ty::simple(TypeCtor::Never),
             TypeRef::Tuple(inner) => {
@@ -104,7 +101,7 @@ impl Ty {
             TypeRef::Path(path) => path,
             _ => return None,
         };
-        if let crate::PathKind::Type(_) = &path.kind {
+        if let PathKind::Type(_) = &path.kind {
             return None;
         }
         if path.segments.len() > 1 {
@@ -148,13 +145,8 @@ impl Ty {
     ) -> Ty {
         let ty = match resolution {
             TypeNs::TraitId(trait_) => {
-                let trait_ref = TraitRef::from_resolved_path(
-                    db,
-                    resolver,
-                    trait_.into(),
-                    resolved_segment,
-                    None,
-                );
+                let trait_ref =
+                    TraitRef::from_resolved_path(db, resolver, trait_, resolved_segment, None);
                 return if remaining_segments.len() == 1 {
                     let segment = &remaining_segments[0];
                     let associated_ty = associated_type_by_name_including_super_traits(
@@ -187,7 +179,11 @@ impl Ty {
                 let name = resolved_segment.name.clone();
                 Ty::Param { idx, name }
             }
-            TypeNs::SelfType(impl_block) => ImplBlock::from(impl_block).target_ty(db),
+            TypeNs::SelfType(impl_id) => {
+                let impl_data = db.impl_data(impl_id);
+                let resolver = impl_id.resolver(db);
+                Ty::from_hir(db, &resolver, &impl_data.target_type)
+            }
             TypeNs::AdtSelfType(adt) => db.ty(adt.into()),
 
             TypeNs::AdtId(it) => Ty::from_hir_path_inner(db, resolver, resolved_segment, it.into()),
@@ -206,7 +202,7 @@ impl Ty {
 
     pub(crate) fn from_hir_path(db: &impl HirDatabase, resolver: &Resolver, path: &Path) -> Ty {
         // Resolve the path (in type namespace)
-        if let crate::PathKind::Type(type_ref) = &path.kind {
+        if let PathKind::Type(type_ref) = &path.kind {
             let ty = Ty::from_hir(db, resolver, &type_ref);
             let remaining_segments = &path.segments[..];
             return Ty::from_type_relative_path(db, resolver, ty, remaining_segments);
@@ -250,14 +246,11 @@ impl Ty {
             GenericPredicate::Implemented(tr) if tr.self_ty() == &self_ty => Some(tr.trait_),
             _ => None,
         });
-        let traits = traits_from_env.flat_map(|t| all_super_traits(db, t)).map(Trait::from);
+        let traits = traits_from_env.flat_map(|t| all_super_traits(db, t));
         for t in traits {
-            if let Some(associated_ty) = db.trait_data(t.id).associated_type_by_name(&segment.name)
-            {
-                let substs = Substs::build_for_def(db, t.id)
-                    .push(self_ty.clone())
-                    .fill_with_unknown()
-                    .build();
+            if let Some(associated_ty) = db.trait_data(t).associated_type_by_name(&segment.name) {
+                let substs =
+                    Substs::build_for_def(db, t).push(self_ty.clone()).fill_with_unknown().build();
                 // FIXME handle type parameters on the segment
                 return Ty::Projection(ProjectionTy { associated_ty, parameters: substs });
             }
@@ -391,7 +384,7 @@ impl TraitRef {
     pub(super) fn from_resolved_path(
         db: &impl HirDatabase,
         resolver: &Resolver,
-        resolved: Trait,
+        resolved: TraitId,
         segment: &PathSegment,
         explicit_self_ty: Option<Ty>,
     ) -> Self {
@@ -399,7 +392,7 @@ impl TraitRef {
         if let Some(self_ty) = explicit_self_ty {
             make_mut_slice(&mut substs.0)[0] = self_ty;
         }
-        TraitRef { trait_: resolved.id, substs }
+        TraitRef { trait_: resolved, substs }
     }
 
     pub(crate) fn from_hir(
@@ -419,14 +412,14 @@ impl TraitRef {
         db: &impl HirDatabase,
         resolver: &Resolver,
         segment: &PathSegment,
-        resolved: Trait,
+        resolved: TraitId,
     ) -> Substs {
         let has_self_param =
             segment.args_and_bindings.as_ref().map(|a| a.has_self_type).unwrap_or(false);
-        substs_from_path_segment(db, resolver, segment, Some(resolved.id.into()), !has_self_param)
+        substs_from_path_segment(db, resolver, segment, Some(resolved.into()), !has_self_param)
     }
 
-    pub(crate) fn for_trait(db: &impl HirDatabase, trait_: TraitId) -> TraitRef {
+    pub fn for_trait(db: &impl HirDatabase, trait_: TraitId) -> TraitRef {
         let substs = Substs::identity(&db.generic_params(trait_.into()));
         TraitRef { trait_, substs }
     }
@@ -500,7 +493,7 @@ fn assoc_type_bindings_from_type_bound<'a>(
 }
 
 /// Build the signature of a callable item (function, struct or enum variant).
-pub(crate) fn callable_item_sig(db: &impl HirDatabase, def: CallableDef) -> FnSig {
+pub fn callable_item_sig(db: &impl HirDatabase, def: CallableDef) -> FnSig {
     match def {
         CallableDef::FunctionId(f) => fn_sig_for_fn(db, f),
         CallableDef::StructId(s) => fn_sig_for_struct_constructor(db, s),
@@ -549,7 +542,7 @@ pub(crate) fn generic_predicates_for_param_query(
 }
 
 impl TraitEnvironment {
-    pub(crate) fn lower(db: &impl HirDatabase, resolver: &Resolver) -> Arc<TraitEnvironment> {
+    pub fn lower(db: &impl HirDatabase, resolver: &Resolver) -> Arc<TraitEnvironment> {
         let predicates = resolver
             .where_predicates_in_scope()
             .flat_map(|pred| GenericPredicate::from_where_predicate(db, &resolver, pred))
diff --git a/crates/ra_hir/src/marks.rs b/crates/ra_hir_ty/src/marks.rs
similarity index 100%
rename from crates/ra_hir/src/marks.rs
rename to crates/ra_hir_ty/src/marks.rs
diff --git a/crates/ra_hir/src/ty/method_resolution.rs b/crates/ra_hir_ty/src/method_resolution.rs
similarity index 98%
rename from crates/ra_hir/src/ty/method_resolution.rs
rename to crates/ra_hir_ty/src/method_resolution.rs
index 5cc2498552..53c541eb8e 100644
--- a/crates/ra_hir/src/ty/method_resolution.rs
+++ b/crates/ra_hir_ty/src/method_resolution.rs
@@ -16,8 +16,9 @@ use rustc_hash::FxHashMap;
 
 use crate::{
     db::HirDatabase,
-    ty::primitive::{FloatBitness, Uncertain},
-    ty::{utils::all_super_traits, Ty, TypeCtor},
+    primitive::{FloatBitness, Uncertain},
+    utils::all_super_traits,
+    Ty, TypeCtor,
 };
 
 use super::{autoderef, Canonical, InEnvironment, TraitEnvironment, TraitRef};
@@ -97,7 +98,7 @@ impl CrateImplBlocks {
 }
 
 impl Ty {
-    pub(crate) fn def_crates(
+    pub fn def_crates(
         &self,
         db: &impl HirDatabase,
         cur_crate: CrateId,
@@ -176,7 +177,7 @@ pub enum LookupMode {
 // This would be nicer if it just returned an iterator, but that runs into
 // lifetime problems, because we need to borrow temp `CrateImplBlocks`.
 // FIXME add a context type here?
-pub(crate) fn iterate_method_candidates<T>(
+pub fn iterate_method_candidates<T>(
     ty: &Canonical<Ty>,
     db: &impl HirDatabase,
     resolver: &Resolver,
@@ -323,7 +324,7 @@ fn is_valid_candidate(
     }
 }
 
-pub(crate) fn implements_trait(
+pub fn implements_trait(
     ty: &Canonical<Ty>,
     db: &impl HirDatabase,
     resolver: &Resolver,
diff --git a/crates/ra_hir/src/ty/op.rs b/crates/ra_hir_ty/src/op.rs
similarity index 98%
rename from crates/ra_hir/src/ty/op.rs
rename to crates/ra_hir_ty/src/op.rs
index cc6e244f44..09c47a76d0 100644
--- a/crates/ra_hir/src/ty/op.rs
+++ b/crates/ra_hir_ty/src/op.rs
@@ -2,7 +2,7 @@
 use hir_def::expr::{BinaryOp, CmpOp};
 
 use super::{InferTy, Ty, TypeCtor};
-use crate::ty::ApplicationTy;
+use crate::ApplicationTy;
 
 pub(super) fn binary_op_return_ty(op: BinaryOp, rhs_ty: Ty) -> Ty {
     match op {
diff --git a/crates/ra_hir/src/ty/tests/coercion.rs b/crates/ra_hir_ty/src/tests/coercion.rs
similarity index 100%
rename from crates/ra_hir/src/ty/tests/coercion.rs
rename to crates/ra_hir_ty/src/tests/coercion.rs
diff --git a/crates/ra_hir/src/ty/tests/never_type.rs b/crates/ra_hir_ty/src/tests/never_type.rs
similarity index 100%
rename from crates/ra_hir/src/ty/tests/never_type.rs
rename to crates/ra_hir_ty/src/tests/never_type.rs
diff --git a/crates/ra_hir/src/ty/traits.rs b/crates/ra_hir_ty/src/traits.rs
similarity index 100%
rename from crates/ra_hir/src/ty/traits.rs
rename to crates/ra_hir_ty/src/traits.rs
diff --git a/crates/ra_hir/src/ty/traits/chalk.rs b/crates/ra_hir_ty/src/traits/chalk.rs
similarity index 96%
rename from crates/ra_hir/src/ty/traits/chalk.rs
rename to crates/ra_hir_ty/src/traits/chalk.rs
index 67ac5422cf..810e8c21a6 100644
--- a/crates/ra_hir/src/ty/traits/chalk.rs
+++ b/crates/ra_hir_ty/src/traits/chalk.rs
@@ -11,8 +11,8 @@ use chalk_rust_ir::{AssociatedTyDatum, AssociatedTyValue, ImplDatum, StructDatum
 use ra_db::CrateId;
 
 use hir_def::{
-    lang_item::LangItemTarget, resolver::HasResolver, AssocItemId, AstItemDef, ContainerId,
-    GenericDefId, ImplId, Lookup, TraitId, TypeAliasId,
+    expr::Expr, lang_item::LangItemTarget, resolver::HasResolver, AssocItemId, AstItemDef,
+    ContainerId, GenericDefId, ImplId, Lookup, TraitId, TypeAliasId,
 };
 use hir_expand::name;
 
@@ -21,8 +21,8 @@ use ra_db::salsa::{InternId, InternKey};
 use super::{AssocTyValue, Canonical, ChalkContext, Impl, Obligation};
 use crate::{
     db::HirDatabase,
-    ty::display::HirDisplay,
-    ty::{ApplicationTy, GenericPredicate, ProjectionTy, Substs, TraitRef, Ty, TypeCtor, TypeWalk},
+    display::HirDisplay,
+    {ApplicationTy, GenericPredicate, ProjectionTy, Substs, TraitRef, Ty, TypeCtor, TypeWalk},
 };
 
 /// This represents a trait whose name we could not resolve.
@@ -723,7 +723,7 @@ fn closure_fn_trait_impl_datum(
     let _output = db.trait_data(fn_once_trait).associated_type_by_name(&name::OUTPUT_TYPE)?;
 
     let num_args: u16 = match &db.body(data.def.into())[data.expr] {
-        crate::expr::Expr::Lambda { args, .. } => args.len() as u16,
+        Expr::Lambda { args, .. } => args.len() as u16,
         _ => {
             log::warn!("closure for closure type {:?} not found", data);
             0
@@ -823,7 +823,7 @@ fn closure_fn_trait_output_assoc_ty_value(
     let impl_id = Impl::ClosureFnTraitImpl(data.clone()).to_chalk(db);
 
     let num_args: u16 = match &db.body(data.def.into())[data.expr] {
-        crate::expr::Expr::Lambda { args, .. } => args.len() as u16,
+        Expr::Lambda { args, .. } => args.len() as u16,
         _ => {
             log::warn!("closure for closure type {:?} not found", data);
             0
@@ -869,38 +869,38 @@ fn id_to_chalk<T: InternKey>(salsa_id: T) -> chalk_ir::RawId {
     chalk_ir::RawId { index: salsa_id.as_intern_id().as_u32() }
 }
 
-impl From<chalk_ir::StructId> for crate::ty::TypeCtorId {
+impl From<chalk_ir::StructId> for crate::TypeCtorId {
     fn from(struct_id: chalk_ir::StructId) -> Self {
         id_from_chalk(struct_id.0)
     }
 }
 
-impl From<crate::ty::TypeCtorId> for chalk_ir::StructId {
-    fn from(type_ctor_id: crate::ty::TypeCtorId) -> Self {
+impl From<crate::TypeCtorId> for chalk_ir::StructId {
+    fn from(type_ctor_id: crate::TypeCtorId) -> Self {
         chalk_ir::StructId(id_to_chalk(type_ctor_id))
     }
 }
 
-impl From<chalk_ir::ImplId> for crate::ty::traits::GlobalImplId {
+impl From<chalk_ir::ImplId> for crate::traits::GlobalImplId {
     fn from(impl_id: chalk_ir::ImplId) -> Self {
         id_from_chalk(impl_id.0)
     }
 }
 
-impl From<crate::ty::traits::GlobalImplId> for chalk_ir::ImplId {
-    fn from(impl_id: crate::ty::traits::GlobalImplId) -> Self {
+impl From<crate::traits::GlobalImplId> for chalk_ir::ImplId {
+    fn from(impl_id: crate::traits::GlobalImplId) -> Self {
         chalk_ir::ImplId(id_to_chalk(impl_id))
     }
 }
 
-impl From<chalk_rust_ir::AssociatedTyValueId> for crate::ty::traits::AssocTyValueId {
+impl From<chalk_rust_ir::AssociatedTyValueId> for crate::traits::AssocTyValueId {
     fn from(id: chalk_rust_ir::AssociatedTyValueId) -> Self {
         id_from_chalk(id.0)
     }
 }
 
-impl From<crate::ty::traits::AssocTyValueId> for chalk_rust_ir::AssociatedTyValueId {
-    fn from(assoc_ty_value_id: crate::ty::traits::AssocTyValueId) -> Self {
+impl From<crate::traits::AssocTyValueId> for chalk_rust_ir::AssociatedTyValueId {
+    fn from(assoc_ty_value_id: crate::traits::AssocTyValueId) -> Self {
         chalk_rust_ir::AssociatedTyValueId(id_to_chalk(assoc_ty_value_id))
     }
 }
diff --git a/crates/ra_hir/src/ty/utils.rs b/crates/ra_hir_ty/src/utils.rs
similarity index 89%
rename from crates/ra_hir/src/ty/utils.rs
rename to crates/ra_hir_ty/src/utils.rs
index f82e6ac9b1..e4ba890efa 100644
--- a/crates/ra_hir/src/ty/utils.rs
+++ b/crates/ra_hir_ty/src/utils.rs
@@ -73,3 +73,12 @@ pub(super) fn variant_data(db: &impl DefDatabase, var: VariantId) -> Arc<Variant
         }
     }
 }
+
+/// Helper for mutating `Arc<[T]>` (i.e. `Arc::make_mut` for Arc slices).
+/// The underlying values are cloned if there are other strong references.
+pub(crate) fn make_mut_slice<T: Clone>(a: &mut Arc<[T]>) -> &mut [T] {
+    if Arc::get_mut(a).is_none() {
+        *a = a.iter().cloned().collect();
+    }
+    Arc::get_mut(a).unwrap()
+}
diff --git a/crates/ra_ide_api/src/impls.rs b/crates/ra_ide_api/src/impls.rs
index b3ebd91454..aa480e399b 100644
--- a/crates/ra_ide_api/src/impls.rs
+++ b/crates/ra_ide_api/src/impls.rs
@@ -1,6 +1,6 @@
 //! FIXME: write short doc here
 
-use hir::{ApplicationTy, FromSource, ImplBlock, Ty, TypeCtor};
+use hir::{FromSource, ImplBlock};
 use ra_db::SourceDatabase;
 use ra_syntax::{algo::find_node_at_offset, ast, AstNode};
 
@@ -61,7 +61,7 @@ fn impls_for_def(
     Some(
         impls
             .into_iter()
-            .filter(|impl_block| is_equal_for_find_impls(&ty, &impl_block.target_ty(db)))
+            .filter(|impl_block| ty.is_equal_for_find_impls(&impl_block.target_ty(db)))
             .map(|imp| imp.to_nav(db))
             .collect(),
     )
@@ -82,19 +82,6 @@ fn impls_for_trait(
     Some(impls.into_iter().map(|imp| imp.to_nav(db)).collect())
 }
 
-fn is_equal_for_find_impls(original_ty: &Ty, impl_ty: &Ty) -> bool {
-    match (original_ty, impl_ty) {
-        (Ty::Apply(a_original_ty), Ty::Apply(ApplicationTy { ctor, parameters })) => match ctor {
-            TypeCtor::Ref(..) => match parameters.as_single() {
-                Ty::Apply(a_ty) => a_original_ty.ctor == a_ty.ctor,
-                _ => false,
-            },
-            _ => a_original_ty.ctor == *ctor,
-        },
-        _ => false,
-    }
-}
-
 #[cfg(test)]
 mod tests {
     use crate::mock_analysis::analysis_and_position;


Test patch:
diff --git a/crates/ra_hir/src/test_db.rs b/crates/ra_hir_ty/src/test_db.rs
similarity index 55%
rename from crates/ra_hir/src/test_db.rs
rename to crates/ra_hir_ty/src/test_db.rs
index a2071f71cf..8743570085 100644
--- a/crates/ra_hir/src/test_db.rs
+++ b/crates/ra_hir_ty/src/test_db.rs
@@ -1,21 +1,23 @@
 //! Database used for testing `hir`.
 
-use std::{panic, sync::Arc};
+use std::{
+    panic,
+    sync::{Arc, Mutex},
+};
 
-use hir_def::{db::DefDatabase, ModuleId};
+use hir_def::{db::DefDatabase, AssocItemId, ModuleDefId, ModuleId};
 use hir_expand::diagnostics::DiagnosticSink;
-use parking_lot::Mutex;
 use ra_db::{salsa, CrateId, FileId, FileLoader, FileLoaderDelegate, RelativePath, SourceDatabase};
 
-use crate::{db, debug::HirDebugHelper};
+use crate::{db::HirDatabase, expr::ExprValidator};
 
 #[salsa::database(
     ra_db::SourceDatabaseExtStorage,
     ra_db::SourceDatabaseStorage,
-    db::InternDatabaseStorage,
-    db::AstDatabaseStorage,
-    db::DefDatabaseStorage,
-    db::HirDatabaseStorage
+    hir_expand::db::AstDatabaseStorage,
+    hir_def::db::InternDatabaseStorage,
+    hir_def::db::DefDatabaseStorage,
+    crate::db::HirDatabaseStorage
 )]
 #[derive(Debug, Default)]
 pub struct TestDB {
@@ -33,7 +35,7 @@ impl salsa::Database for TestDB {
     }
 
     fn salsa_event(&self, event: impl Fn() -> salsa::Event<TestDB>) {
-        let mut events = self.events.lock();
+        let mut events = self.events.lock().unwrap();
         if let Some(events) = &mut *events {
             events.push(event());
         }
@@ -67,32 +69,53 @@ impl FileLoader for TestDB {
     }
 }
 
-// FIXME: improve `WithFixture` to bring useful hir debugging back
-impl HirDebugHelper for TestDB {
-    fn crate_name(&self, _krate: CrateId) -> Option<String> {
-        None
-    }
-
-    fn file_path(&self, _file_id: FileId) -> Option<String> {
-        None
+impl TestDB {
+    pub fn module_for_file(&self, file_id: FileId) -> ModuleId {
+        for &krate in self.relevant_crates(file_id).iter() {
+            let crate_def_map = self.crate_def_map(krate);
+            for (module_id, data) in crate_def_map.modules.iter() {
+                if data.definition == Some(file_id) {
+                    return ModuleId { krate, module_id };
+                }
+            }
+        }
+        panic!("Can't find module for file")
     }
-}
 
-impl TestDB {
+    // FIXME: don't duplicate this
     pub fn diagnostics(&self) -> String {
         let mut buf = String::new();
         let crate_graph = self.crate_graph();
         for krate in crate_graph.iter().next() {
             let crate_def_map = self.crate_def_map(krate);
+
+            let mut fns = Vec::new();
             for (module_id, _) in crate_def_map.modules.iter() {
-                let module_id = ModuleId { krate, module_id };
-                let module = crate::Module::from(module_id);
-                module.diagnostics(
-                    self,
-                    &mut DiagnosticSink::new(|d| {
-                        buf += &format!("{:?}: {}\n", d.syntax_node(self).text(), d.message());
-                    }),
-                )
+                for decl in crate_def_map[module_id].scope.declarations() {
+                    match decl {
+                        ModuleDefId::FunctionId(f) => fns.push(f),
+                        _ => (),
+                    }
+                }
+
+                for &impl_id in crate_def_map[module_id].impls.iter() {
+                    let impl_data = self.impl_data(impl_id);
+                    for item in impl_data.items.iter() {
+                        if let AssocItemId::FunctionId(f) = item {
+                            fns.push(*f)
+                        }
+                    }
+                }
+            }
+
+            for f in fns {
+                let infer = self.infer(f.into());
+                let mut sink = DiagnosticSink::new(|d| {
+                    buf += &format!("{:?}: {}\n", d.syntax_node(self).text(), d.message());
+                });
+                infer.add_diagnostics(self, f, &mut sink);
+                let mut validator = ExprValidator::new(f, infer, &mut sink);
+                validator.validate_body(self);
             }
         }
         buf
@@ -101,9 +124,9 @@ impl TestDB {
 
 impl TestDB {
     pub fn log(&self, f: impl FnOnce()) -> Vec<salsa::Event<TestDB>> {
-        *self.events.lock() = Some(Vec::new());
+        *self.events.lock().unwrap() = Some(Vec::new());
         f();
-        self.events.lock().take().unwrap()
+        self.events.lock().unwrap().take().unwrap()
     }
 
     pub fn log_executed(&self, f: impl FnOnce()) -> Vec<String> {
diff --git a/crates/ra_hir/src/ty/tests.rs b/crates/ra_hir_ty/src/tests.rs
similarity index 96%
rename from crates/ra_hir/src/ty/tests.rs
rename to crates/ra_hir_ty/src/tests.rs
index 98eb863cb9..c1744663a6 100644
--- a/crates/ra_hir/src/ty/tests.rs
+++ b/crates/ra_hir_ty/src/tests.rs
@@ -4,20 +4,20 @@ mod coercion;
 use std::fmt::Write;
 use std::sync::Arc;
 
+use hir_def::{
+    body::BodySourceMap, db::DefDatabase, nameres::CrateDefMap, AssocItemId, DefWithBodyId,
+    LocalModuleId, Lookup, ModuleDefId,
+};
+use hir_expand::Source;
 use insta::assert_snapshot;
 use ra_db::{fixture::WithFixture, salsa::Database, FilePosition, SourceDatabase};
 use ra_syntax::{
     algo,
     ast::{self, AstNode},
-    SyntaxKind::*,
 };
-use rustc_hash::FxHashSet;
 use test_utils::covers;
 
-use crate::{
-    expr::BodySourceMap, test_db::TestDB, ty::display::HirDisplay, ty::InferenceResult, Source,
-    SourceAnalyzer,
-};
+use crate::{db::HirDatabase, display::HirDisplay, test_db::TestDB, InferenceResult};
 
 // These tests compare the inference results for all expressions in a file
 // against snapshots of the expected results using insta. Use cargo-insta to
@@ -4674,10 +4674,20 @@ fn test<T, U>() where T: Trait<U::Item>, U: Trait<T::Item> {
 fn type_at_pos(db: &TestDB, pos: FilePosition) -> String {
     let file = db.parse(pos.file_id).ok().unwrap();
     let expr = algo::find_node_at_offset::<ast::Expr>(file.syntax(), pos.offset).unwrap();
-    let analyzer =
-        SourceAnalyzer::new(db, Source::new(pos.file_id.into(), expr.syntax()), Some(pos.offset));
-    let ty = analyzer.type_of(db, &expr).unwrap();
-    ty.display(db).to_string()
+
+    let module = db.module_for_file(pos.file_id);
+    let crate_def_map = db.crate_def_map(module.krate);
+    for decl in crate_def_map[module.module_id].scope.declarations() {
+        if let ModuleDefId::FunctionId(func) = decl {
+            let (_body, source_map) = db.body_with_source_map(func.into());
+            if let Some(expr_id) = source_map.node_expr(Source::new(pos.file_id.into(), &expr)) {
+                let infer = db.infer(func.into());
+                let ty = &infer[expr_id];
+                return ty.display(db).to_string();
+            }
+        }
+    }
+    panic!("Can't find expression")
 }
 
 fn type_at(content: &str) -> String {
@@ -4687,7 +4697,6 @@ fn type_at(content: &str) -> String {
 
 fn infer(content: &str) -> String {
     let (db, file_id) = TestDB::with_single_file(content);
-    let source_file = db.parse(file_id).ok().unwrap();
 
     let mut acc = String::new();
 
@@ -4740,20 +4749,69 @@ fn infer(content: &str) -> String {
         }
     };
 
-    let mut analyzed = FxHashSet::default();
-    for node in source_file.syntax().descendants() {
-        if node.kind() == FN_DEF || node.kind() == CONST_DEF || node.kind() == STATIC_DEF {
-            let analyzer = SourceAnalyzer::new(&db, Source::new(file_id.into(), &node), None);
-            if analyzed.insert(analyzer.analyzed_declaration()) {
-                infer_def(analyzer.inference_result(), analyzer.body_source_map());
-            }
+    let module = db.module_for_file(file_id);
+    let crate_def_map = db.crate_def_map(module.krate);
+
+    let mut defs: Vec<DefWithBodyId> = Vec::new();
+    visit_module(&db, &crate_def_map, module.module_id, &mut |it| defs.push(it));
+    defs.sort_by_key(|def| match def {
+        DefWithBodyId::FunctionId(it) => {
+            it.lookup(&db).ast_id.to_node(&db).syntax().text_range().start()
+        }
+        DefWithBodyId::ConstId(it) => {
+            it.lookup(&db).ast_id.to_node(&db).syntax().text_range().start()
+        }
+        DefWithBodyId::StaticId(it) => {
+            it.lookup(&db).ast_id.to_node(&db).syntax().text_range().start()
         }
+    });
+    for def in defs {
+        let (_body, source_map) = db.body_with_source_map(def);
+        let infer = db.infer(def);
+        infer_def(infer, source_map);
     }
 
     acc.truncate(acc.trim_end().len());
     acc
 }
 
+fn visit_module(
+    db: &TestDB,
+    crate_def_map: &CrateDefMap,
+    module_id: LocalModuleId,
+    cb: &mut dyn FnMut(DefWithBodyId),
+) {
+    for decl in crate_def_map[module_id].scope.declarations() {
+        match decl {
+            ModuleDefId::FunctionId(it) => cb(it.into()),
+            ModuleDefId::ConstId(it) => cb(it.into()),
+            ModuleDefId::StaticId(it) => cb(it.into()),
+            ModuleDefId::TraitId(it) => {
+                let trait_data = db.trait_data(it);
+                for &(_, item) in trait_data.items.iter() {
+                    match item {
+                        AssocItemId::FunctionId(it) => cb(it.into()),
+                        AssocItemId::ConstId(it) => cb(it.into()),
+                        AssocItemId::TypeAliasId(_) => (),
+                    }
+                }
+            }
+            ModuleDefId::ModuleId(it) => visit_module(db, crate_def_map, it.module_id, cb),
+            _ => (),
+        }
+    }
+    for &impl_id in crate_def_map[module_id].impls.iter() {
+        let impl_data = db.impl_data(impl_id);
+        for &item in impl_data.items.iter() {
+            match item {
+                AssocItemId::FunctionId(it) => cb(it.into()),
+                AssocItemId::ConstId(it) => cb(it.into()),
+                AssocItemId::TypeAliasId(_) => (),
+            }
+        }
+    }
+}
+
 fn ellipsize(mut text: String, max_len: usize) -> String {
     if text.len() <= max_len {
         return text;
@@ -4783,10 +4841,12 @@ fn typing_whitespace_inside_a_function_should_not_invalidate_types() {
     ",
     );
     {
-        let file = db.parse(pos.file_id).ok().unwrap();
-        let node = file.syntax().token_at_offset(pos.offset).right_biased().unwrap().parent();
         let events = db.log_executed(|| {
-            SourceAnalyzer::new(&db, Source::new(pos.file_id.into(), &node), None);
+            let module = db.module_for_file(pos.file_id);
+            let crate_def_map = db.crate_def_map(module.krate);
+            visit_module(&db, &crate_def_map, module.module_id, &mut |def| {
+                db.infer(def);
+            });
         });
         assert!(format!("{:?}", events).contains("infer"))
     }
@@ -4803,10 +4863,12 @@ fn typing_whitespace_inside_a_function_should_not_invalidate_types() {
     db.query_mut(ra_db::FileTextQuery).set(pos.file_id, Arc::new(new_text));
 
     {
-        let file = db.parse(pos.file_id).ok().unwrap();
-        let node = file.syntax().token_at_offset(pos.offset).right_biased().unwrap().parent();
         let events = db.log_executed(|| {
-            SourceAnalyzer::new(&db, Source::new(pos.file_id.into(), &node), None);
+            let module = db.module_for_file(pos.file_id);
+            let crate_def_map = db.crate_def_map(module.krate);
+            visit_module(&db, &crate_def_map, module.module_id, &mut |def| {
+                db.infer(def);
+            });
         });
         assert!(!format!("{:?}", events).contains("infer"), "{:#?}", events)
     }
diff --git a/xtask/tests/tidy-tests/docs.rs b/xtask/tests/tidy-tests/docs.rs
index fae871285a..e0653b460f 100644
--- a/xtask/tests/tidy-tests/docs.rs
+++ b/xtask/tests/tidy-tests/docs.rs
@@ -83,6 +83,7 @@ fn no_docs_comments() {
         "ra_syntax",
         "ra_text_edit",
         "ra_tt",
+        "ra_hir_ty",
     ];
 
     let mut has_fixmes = whitelist.iter().map(|it| (*it, false)).collect::<HashMap<&str, bool>>();