Move Ty

23 files changed, 12282 insertions, 2 deletions

diff --git a/crates/ra_hir_ty/src/autoderef.rs b/crates/ra_hir_ty/src/autoderef.rs
new file mode 100644
index 000000000..9d1d4e48c
--- /dev/null
+++ b/crates/ra_hir_ty/src/autoderef.rs
@@ -0,0 +1,108 @@
+//! In certain situations, rust automatically inserts derefs as necessary: for
+//! example, field accesses `foo.bar` still work when `foo` is actually a
+//! reference to a type with the field `bar`. This is an approximation of the
+//! logic in rustc (which lives in librustc_typeck/check/autoderef.rs).
+
+use std::iter::successors;
+
+use hir_def::lang_item::LangItemTarget;
+use hir_expand::name;
+use log::{info, warn};
+use ra_db::CrateId;
+
+use crate::db::HirDatabase;
+
+use super::{
+    traits::{InEnvironment, Solution},
+    Canonical, Substs, Ty, TypeWalk,
+};
+
+const AUTODEREF_RECURSION_LIMIT: usize = 10;
+
+pub fn autoderef<'a>(
+    db: &'a impl HirDatabase,
+    krate: Option<CrateId>,
+    ty: InEnvironment<Canonical<Ty>>,
+) -> impl Iterator<Item = Canonical<Ty>> + 'a {
+    let InEnvironment { value: ty, environment } = ty;
+    successors(Some(ty), move |ty| {
+        deref(db, krate?, InEnvironment { value: ty, environment: environment.clone() })
+    })
+    .take(AUTODEREF_RECURSION_LIMIT)
+}
+
+pub(crate) fn deref(
+    db: &impl HirDatabase,
+    krate: CrateId,
+    ty: InEnvironment<&Canonical<Ty>>,
+) -> Option<Canonical<Ty>> {
+    if let Some(derefed) = ty.value.value.builtin_deref() {
+        Some(Canonical { value: derefed, num_vars: ty.value.num_vars })
+    } else {
+        deref_by_trait(db, krate, ty)
+    }
+}
+
+fn deref_by_trait(
+    db: &impl HirDatabase,
+    krate: CrateId,
+    ty: InEnvironment<&Canonical<Ty>>,
+) -> Option<Canonical<Ty>> {
+    let deref_trait = match db.lang_item(krate.into(), "deref".into())? {
+        LangItemTarget::TraitId(it) => it,
+        _ => return None,
+    };
+    let target = db.trait_data(deref_trait).associated_type_by_name(&name::TARGET_TYPE)?;
+
+    let generic_params = db.generic_params(target.into());
+    if generic_params.count_params_including_parent() != 1 {
+        // the Target type + Deref trait should only have one generic parameter,
+        // namely Deref's Self type
+        return None;
+    }
+
+    // FIXME make the Canonical handling nicer
+
+    let parameters = Substs::build_for_generics(&generic_params)
+        .push(ty.value.value.clone().shift_bound_vars(1))
+        .build();
+
+    let projection = super::traits::ProjectionPredicate {
+        ty: Ty::Bound(0),
+        projection_ty: super::ProjectionTy { associated_ty: target, parameters },
+    };
+
+    let obligation = super::Obligation::Projection(projection);
+
+    let in_env = InEnvironment { value: obligation, environment: ty.environment };
+
+    let canonical = super::Canonical { num_vars: 1 + ty.value.num_vars, value: in_env };
+
+    let solution = db.trait_solve(krate.into(), canonical)?;
+
+    match &solution {
+        Solution::Unique(vars) => {
+            // FIXME: vars may contain solutions for any inference variables
+            // that happened to be inside ty. To correctly handle these, we
+            // would have to pass the solution up to the inference context, but
+            // that requires a larger refactoring (especially if the deref
+            // happens during method resolution). So for the moment, we just
+            // check that we're not in the situation we're we would actually
+            // need to handle the values of the additional variables, i.e.
+            // they're just being 'passed through'. In the 'standard' case where
+            // we have `impl<T> Deref for Foo<T> { Target = T }`, that should be
+            // the case.
+            for i in 1..vars.0.num_vars {
+                if vars.0.value[i] != Ty::Bound((i - 1) as u32) {
+                    warn!("complex solution for derefing {:?}: {:?}, ignoring", ty.value, solution);
+                    return None;
+                }
+            }
+            Some(Canonical { value: vars.0.value[0].clone(), num_vars: vars.0.num_vars })
+        }
+        Solution::Ambig(_) => {
+            info!("Ambiguous solution for derefing {:?}: {:?}", ty.value, solution);
+            None
+        }
+    }
+}
diff --git a/crates/ra_hir_ty/src/db.rs b/crates/ra_hir_ty/src/db.rs
new file mode 100644
index 000000000..aa2659c4b
--- /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 000000000..4a13fac23
--- /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_ty/src/display.rs b/crates/ra_hir_ty/src/display.rs
new file mode 100644
index 000000000..9bb3ece6c
--- /dev/null
+++ b/crates/ra_hir_ty/src/display.rs
@@ -0,0 +1,93 @@
+//! FIXME: write short doc here
+
+use std::fmt;
+
+use crate::db::HirDatabase;
+
+pub struct HirFormatter<'a, 'b, DB> {
+    pub db: &'a DB,
+    fmt: &'a mut fmt::Formatter<'b>,
+    buf: String,
+    curr_size: usize,
+    max_size: Option<usize>,
+}
+
+pub trait HirDisplay {
+    fn hir_fmt(&self, f: &mut HirFormatter<impl HirDatabase>) -> fmt::Result;
+
+    fn display<'a, DB>(&'a self, db: &'a DB) -> HirDisplayWrapper<'a, DB, Self>
+    where
+        Self: Sized,
+    {
+        HirDisplayWrapper(db, self, None)
+    }
+
+    fn display_truncated<'a, DB>(
+        &'a self,
+        db: &'a DB,
+        max_size: Option<usize>,
+    ) -> HirDisplayWrapper<'a, DB, Self>
+    where
+        Self: Sized,
+    {
+        HirDisplayWrapper(db, self, max_size)
+    }
+}
+
+impl<'a, 'b, DB> HirFormatter<'a, 'b, DB>
+where
+    DB: HirDatabase,
+{
+    pub fn write_joined<T: HirDisplay>(
+        &mut self,
+        iter: impl IntoIterator<Item = T>,
+        sep: &str,
+    ) -> fmt::Result {
+        let mut first = true;
+        for e in iter {
+            if !first {
+                write!(self, "{}", sep)?;
+            }
+            first = false;
+            e.hir_fmt(self)?;
+        }
+        Ok(())
+    }
+
+    /// This allows using the `write!` macro directly with a `HirFormatter`.
+    pub fn write_fmt(&mut self, args: fmt::Arguments) -> fmt::Result {
+        // We write to a buffer first to track output size
+        self.buf.clear();
+        fmt::write(&mut self.buf, args)?;
+        self.curr_size += self.buf.len();
+
+        // Then we write to the internal formatter from the buffer
+        self.fmt.write_str(&self.buf)
+    }
+
+    pub fn should_truncate(&self) -> bool {
+        if let Some(max_size) = self.max_size {
+            self.curr_size >= max_size
+        } else {
+            false
+        }
+    }
+}
+
+pub struct HirDisplayWrapper<'a, DB, T>(&'a DB, &'a T, Option<usize>);
+
+impl<'a, DB, T> fmt::Display for HirDisplayWrapper<'a, DB, T>
+where
+    DB: HirDatabase,
+    T: HirDisplay,
+{
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        self.1.hir_fmt(&mut HirFormatter {
+            db: self.0,
+            fmt: f,
+            buf: String::with_capacity(20),
+            curr_size: 0,
+            max_size: self.2,
+        })
+    }
+}
diff --git a/crates/ra_hir_ty/src/expr.rs b/crates/ra_hir_ty/src/expr.rs
new file mode 100644
index 000000000..5c65f9370
--- /dev/null
+++ b/crates/ra_hir_ty/src/expr.rs
@@ -0,0 +1,151 @@
+//! FIXME: write short doc here
+
+use std::sync::Arc;
+
+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;
+
+use crate::{
+    db::HirDatabase,
+    diagnostics::{MissingFields, MissingOkInTailExpr},
+    ApplicationTy, InferenceResult, Ty, TypeCtor,
+};
+
+pub use hir_def::{
+    body::{
+        scope::{ExprScopes, ScopeEntry, ScopeId},
+        Body, BodySourceMap, ExprPtr, ExprSource, PatPtr, PatSource,
+    },
+    expr::{
+        ArithOp, Array, BinaryOp, BindingAnnotation, CmpOp, Expr, ExprId, Literal, LogicOp,
+        MatchArm, Ordering, Pat, PatId, RecordFieldPat, RecordLitField, Statement, UnaryOp,
+    },
+};
+
+pub struct ExprValidator<'a, 'b: 'a> {
+    func: FunctionId,
+    infer: Arc<InferenceResult>,
+    sink: &'a mut DiagnosticSink<'b>,
+}
+
+impl<'a, 'b> ExprValidator<'a, 'b> {
+    pub fn new(
+        func: FunctionId,
+        infer: Arc<InferenceResult>,
+        sink: &'a mut DiagnosticSink<'b>,
+    ) -> ExprValidator<'a, 'b> {
+        ExprValidator { func, infer, sink }
+    }
+
+    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 {
+                self.validate_record_literal(id, path, fields, *spread, db);
+            }
+        }
+
+        let body_expr = &body[body.body_expr];
+        if let Expr::Block { statements: _, tail: Some(t) } = body_expr {
+            self.validate_results_in_tail_expr(body.body_expr, *t, db);
+        }
+    }
+
+    fn validate_record_literal(
+        &mut self,
+        id: ExprId,
+        _path: &Option<Path>,
+        fields: &[RecordLitField],
+        spread: Option<ExprId>,
+        db: &impl HirDatabase,
+    ) {
+        if spread.is_some() {
+            return;
+        }
+
+        let struct_def = match self.infer[id].as_adt() {
+            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_data
+            .variant_data
+            .fields()
+            .iter()
+            .filter_map(|(_f, d)| {
+                let name = d.name.clone();
+                if lit_fields.contains(&name) {
+                    None
+                } else {
+                    Some(name)
+                }
+            })
+            .collect();
+        if missed_fields.is_empty() {
+            return;
+        }
+        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() {
+                let root = source_ptr.file_syntax(db);
+                if let ast::Expr::RecordLit(record_lit) = expr.to_node(&root) {
+                    if let Some(field_list) = record_lit.record_field_list() {
+                        self.sink.push(MissingFields {
+                            file: source_ptr.file_id,
+                            field_list: AstPtr::new(&field_list),
+                            missed_fields,
+                        })
+                    }
+                }
+            }
+        }
+    }
+
+    fn validate_results_in_tail_expr(
+        &mut self,
+        body_id: ExprId,
+        id: ExprId,
+        db: &impl HirDatabase,
+    ) {
+        // the mismatch will be on the whole block currently
+        let mismatch = match self.infer.type_mismatch_for_expr(body_id) {
+            Some(m) => m,
+            None => return,
+        };
+
+        let std_result_path = known::std_result_result();
+
+        let resolver = self.func.resolver(db);
+        let std_result_enum = match resolver.resolve_known_enum(db, &std_result_path) {
+            Some(it) => it,
+            _ => return,
+        };
+
+        let std_result_ctor = TypeCtor::Adt(AdtId::EnumId(std_result_enum));
+        let params = match &mismatch.expected {
+            Ty::Apply(ApplicationTy { ctor, parameters }) if ctor == &std_result_ctor => parameters,
+            _ => return,
+        };
+
+        if params.len() == 2 && &params[0] == &mismatch.actual {
+            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() {
+                    self.sink.push(MissingOkInTailExpr { file: source_ptr.file_id, expr });
+                }
+            }
+        }
+    }
+}
diff --git a/crates/ra_hir_ty/src/infer.rs b/crates/ra_hir_ty/src/infer.rs
new file mode 100644
index 000000000..1e9f4b208
--- /dev/null
+++ b/crates/ra_hir_ty/src/infer.rs
@@ -0,0 +1,723 @@
+//! Type inference, i.e. the process of walking through the code and determining
+//! the type of each expression and pattern.
+//!
+//! For type inference, compare the implementations in rustc (the various
+//! check_* methods in librustc_typeck/check/mod.rs are a good entry point) and
+//! IntelliJ-Rust (org.rust.lang.core.types.infer). Our entry point for
+//! inference here is the `infer` function, which infers the types of all
+//! expressions in a given function.
+//!
+//! During inference, types (i.e. the `Ty` struct) can contain type 'variables'
+//! which represent currently unknown types; as we walk through the expressions,
+//! we might determine that certain variables need to be equal to each other, or
+//! to certain types. To record this, we use the union-find implementation from
+//! the `ena` crate, which is extracted from rustc.
+
+use std::borrow::Cow;
+use std::mem;
+use std::ops::Index;
+use std::sync::Arc;
+
+use ena::unify::{InPlaceUnificationTable, NoError, UnifyKey, UnifyValue};
+use rustc_hash::FxHashMap;
+
+use hir_def::{
+    body::Body,
+    data::{ConstData, FunctionData},
+    expr::{BindingAnnotation, ExprId, PatId},
+    path::{known, Path},
+    resolver::{HasResolver, Resolver, TypeNs},
+    type_ref::{Mutability, TypeRef},
+    AdtId, AssocItemId, DefWithBodyId, FunctionId, StructFieldId, TypeAliasId, VariantId,
+};
+use hir_expand::{diagnostics::DiagnosticSink, name};
+use ra_arena::map::ArenaMap;
+use ra_prof::profile;
+use test_utils::tested_by;
+
+use super::{
+    primitive::{FloatTy, IntTy},
+    traits::{Guidance, Obligation, ProjectionPredicate, Solution},
+    ApplicationTy, InEnvironment, ProjectionTy, Substs, TraitEnvironment, TraitRef, Ty, TypeCtor,
+    TypeWalk, Uncertain,
+};
+use crate::{db::HirDatabase, infer::diagnostics::InferenceDiagnostic};
+
+macro_rules! ty_app {
+    ($ctor:pat, $param:pat) => {
+        crate::Ty::Apply(crate::ApplicationTy { ctor: $ctor, parameters: $param })
+    };
+    ($ctor:pat) => {
+        ty_app!($ctor, _)
+    };
+}
+
+mod unify;
+mod path;
+mod expr;
+mod pat;
+mod coerce;
+
+/// The entry point of type inference.
+pub fn infer_query(db: &impl HirDatabase, def: DefWithBodyId) -> Arc<InferenceResult> {
+    let _p = profile("infer_query");
+    let resolver = def.resolver(db);
+    let mut ctx = InferenceContext::new(db, def, resolver);
+
+    match def {
+        DefWithBodyId::ConstId(c) => ctx.collect_const(&db.const_data(c)),
+        DefWithBodyId::FunctionId(f) => ctx.collect_fn(&db.function_data(f)),
+        DefWithBodyId::StaticId(s) => ctx.collect_const(&db.static_data(s)),
+    }
+
+    ctx.infer_body();
+
+    Arc::new(ctx.resolve_all())
+}
+
+#[derive(Debug, Copy, Clone, Hash, PartialEq, Eq)]
+enum ExprOrPatId {
+    ExprId(ExprId),
+    PatId(PatId),
+}
+
+impl_froms!(ExprOrPatId: ExprId, PatId);
+
+/// Binding modes inferred for patterns.
+/// https://doc.rust-lang.org/reference/patterns.html#binding-modes
+#[derive(Copy, Clone, Debug, Eq, PartialEq)]
+enum BindingMode {
+    Move,
+    Ref(Mutability),
+}
+
+impl BindingMode {
+    pub fn convert(annotation: BindingAnnotation) -> BindingMode {
+        match annotation {
+            BindingAnnotation::Unannotated | BindingAnnotation::Mutable => BindingMode::Move,
+            BindingAnnotation::Ref => BindingMode::Ref(Mutability::Shared),
+            BindingAnnotation::RefMut => BindingMode::Ref(Mutability::Mut),
+        }
+    }
+}
+
+impl Default for BindingMode {
+    fn default() -> Self {
+        BindingMode::Move
+    }
+}
+
+/// A mismatch between an expected and an inferred type.
+#[derive(Clone, PartialEq, Eq, Debug, Hash)]
+pub struct TypeMismatch {
+    pub expected: Ty,
+    pub actual: Ty,
+}
+
+/// The result of type inference: A mapping from expressions and patterns to types.
+#[derive(Clone, PartialEq, Eq, Debug, Default)]
+pub struct InferenceResult {
+    /// For each method call expr, records the function it resolves to.
+    method_resolutions: FxHashMap<ExprId, FunctionId>,
+    /// For each field access expr, records the field it resolves to.
+    field_resolutions: FxHashMap<ExprId, StructFieldId>,
+    /// For each field in record literal, records the field it resolves to.
+    record_field_resolutions: FxHashMap<ExprId, StructFieldId>,
+    /// For each struct literal, records the variant it resolves to.
+    variant_resolutions: FxHashMap<ExprOrPatId, VariantId>,
+    /// For each associated item record what it resolves to
+    assoc_resolutions: FxHashMap<ExprOrPatId, AssocItemId>,
+    diagnostics: Vec<InferenceDiagnostic>,
+    pub type_of_expr: ArenaMap<ExprId, Ty>,
+    pub type_of_pat: ArenaMap<PatId, Ty>,
+    pub(super) type_mismatches: ArenaMap<ExprId, TypeMismatch>,
+}
+
+impl InferenceResult {
+    pub fn method_resolution(&self, expr: ExprId) -> Option<FunctionId> {
+        self.method_resolutions.get(&expr).copied()
+    }
+    pub fn field_resolution(&self, expr: ExprId) -> Option<StructFieldId> {
+        self.field_resolutions.get(&expr).copied()
+    }
+    pub fn record_field_resolution(&self, expr: ExprId) -> Option<StructFieldId> {
+        self.record_field_resolutions.get(&expr).copied()
+    }
+    pub fn variant_resolution_for_expr(&self, id: ExprId) -> Option<VariantId> {
+        self.variant_resolutions.get(&id.into()).copied()
+    }
+    pub fn variant_resolution_for_pat(&self, id: PatId) -> Option<VariantId> {
+        self.variant_resolutions.get(&id.into()).copied()
+    }
+    pub fn assoc_resolutions_for_expr(&self, id: ExprId) -> Option<AssocItemId> {
+        self.assoc_resolutions.get(&id.into()).copied()
+    }
+    pub fn assoc_resolutions_for_pat(&self, id: PatId) -> Option<AssocItemId> {
+        self.assoc_resolutions.get(&id.into()).copied()
+    }
+    pub fn type_mismatch_for_expr(&self, expr: ExprId) -> Option<&TypeMismatch> {
+        self.type_mismatches.get(expr)
+    }
+    pub fn add_diagnostics(
+        &self,
+        db: &impl HirDatabase,
+        owner: FunctionId,
+        sink: &mut DiagnosticSink,
+    ) {
+        self.diagnostics.iter().for_each(|it| it.add_to(db, owner, sink))
+    }
+}
+
+impl Index<ExprId> for InferenceResult {
+    type Output = Ty;
+
+    fn index(&self, expr: ExprId) -> &Ty {
+        self.type_of_expr.get(expr).unwrap_or(&Ty::Unknown)
+    }
+}
+
+impl Index<PatId> for InferenceResult {
+    type Output = Ty;
+
+    fn index(&self, pat: PatId) -> &Ty {
+        self.type_of_pat.get(pat).unwrap_or(&Ty::Unknown)
+    }
+}
+
+/// The inference context contains all information needed during type inference.
+#[derive(Clone, Debug)]
+struct InferenceContext<'a, D: HirDatabase> {
+    db: &'a D,
+    owner: DefWithBodyId,
+    body: Arc<Body>,
+    resolver: Resolver,
+    var_unification_table: InPlaceUnificationTable<TypeVarId>,
+    trait_env: Arc<TraitEnvironment>,
+    obligations: Vec<Obligation>,
+    result: InferenceResult,
+    /// The return type of the function being inferred.
+    return_ty: Ty,
+
+    /// Impls of `CoerceUnsized` used in coercion.
+    /// (from_ty_ctor, to_ty_ctor) => coerce_generic_index
+    // FIXME: Use trait solver for this.
+    // Chalk seems unable to work well with builtin impl of `Unsize` now.
+    coerce_unsized_map: FxHashMap<(TypeCtor, TypeCtor), usize>,
+}
+
+impl<'a, D: HirDatabase> InferenceContext<'a, D> {
+    fn new(db: &'a D, owner: DefWithBodyId, resolver: Resolver) -> Self {
+        InferenceContext {
+            result: InferenceResult::default(),
+            var_unification_table: InPlaceUnificationTable::new(),
+            obligations: Vec::default(),
+            return_ty: Ty::Unknown, // set in collect_fn_signature
+            trait_env: TraitEnvironment::lower(db, &resolver),
+            coerce_unsized_map: Self::init_coerce_unsized_map(db, &resolver),
+            db,
+            owner,
+            body: db.body(owner.into()),
+            resolver,
+        }
+    }
+
+    fn resolve_all(mut self) -> InferenceResult {
+        // FIXME resolve obligations as well (use Guidance if necessary)
+        let mut result = mem::replace(&mut self.result, InferenceResult::default());
+        let mut tv_stack = Vec::new();
+        for ty in result.type_of_expr.values_mut() {
+            let resolved = self.resolve_ty_completely(&mut tv_stack, mem::replace(ty, Ty::Unknown));
+            *ty = resolved;
+        }
+        for ty in result.type_of_pat.values_mut() {
+            let resolved = self.resolve_ty_completely(&mut tv_stack, mem::replace(ty, Ty::Unknown));
+            *ty = resolved;
+        }
+        result
+    }
+
+    fn write_expr_ty(&mut self, expr: ExprId, ty: Ty) {
+        self.result.type_of_expr.insert(expr, ty);
+    }
+
+    fn write_method_resolution(&mut self, expr: ExprId, func: FunctionId) {
+        self.result.method_resolutions.insert(expr, func);
+    }
+
+    fn write_field_resolution(&mut self, expr: ExprId, field: StructFieldId) {
+        self.result.field_resolutions.insert(expr, field);
+    }
+
+    fn write_variant_resolution(&mut self, id: ExprOrPatId, variant: VariantId) {
+        self.result.variant_resolutions.insert(id, variant);
+    }
+
+    fn write_assoc_resolution(&mut self, id: ExprOrPatId, item: AssocItemId) {
+        self.result.assoc_resolutions.insert(id, item.into());
+    }
+
+    fn write_pat_ty(&mut self, pat: PatId, ty: Ty) {
+        self.result.type_of_pat.insert(pat, ty);
+    }
+
+    fn push_diagnostic(&mut self, diagnostic: InferenceDiagnostic) {
+        self.result.diagnostics.push(diagnostic);
+    }
+
+    fn make_ty(&mut self, type_ref: &TypeRef) -> Ty {
+        let ty = Ty::from_hir(
+            self.db,
+            // FIXME use right resolver for block
+            &self.resolver,
+            type_ref,
+        );
+        let ty = self.insert_type_vars(ty);
+        self.normalize_associated_types_in(ty)
+    }
+
+    fn unify_substs(&mut self, substs1: &Substs, substs2: &Substs, depth: usize) -> bool {
+        substs1.0.iter().zip(substs2.0.iter()).all(|(t1, t2)| self.unify_inner(t1, t2, depth))
+    }
+
+    fn unify(&mut self, ty1: &Ty, ty2: &Ty) -> bool {
+        self.unify_inner(ty1, ty2, 0)
+    }
+
+    fn unify_inner(&mut self, ty1: &Ty, ty2: &Ty, depth: usize) -> bool {
+        if depth > 1000 {
+            // prevent stackoverflows
+            panic!("infinite recursion in unification");
+        }
+        if ty1 == ty2 {
+            return true;
+        }
+        // try to resolve type vars first
+        let ty1 = self.resolve_ty_shallow(ty1);
+        let ty2 = self.resolve_ty_shallow(ty2);
+        match (&*ty1, &*ty2) {
+            (Ty::Apply(a_ty1), Ty::Apply(a_ty2)) if a_ty1.ctor == a_ty2.ctor => {
+                self.unify_substs(&a_ty1.parameters, &a_ty2.parameters, depth + 1)
+            }
+            _ => self.unify_inner_trivial(&ty1, &ty2),
+        }
+    }
+
+    fn unify_inner_trivial(&mut self, ty1: &Ty, ty2: &Ty) -> bool {
+        match (ty1, ty2) {
+            (Ty::Unknown, _) | (_, Ty::Unknown) => true,
+
+            (Ty::Infer(InferTy::TypeVar(tv1)), Ty::Infer(InferTy::TypeVar(tv2)))
+            | (Ty::Infer(InferTy::IntVar(tv1)), Ty::Infer(InferTy::IntVar(tv2)))
+            | (Ty::Infer(InferTy::FloatVar(tv1)), Ty::Infer(InferTy::FloatVar(tv2)))
+            | (
+                Ty::Infer(InferTy::MaybeNeverTypeVar(tv1)),
+                Ty::Infer(InferTy::MaybeNeverTypeVar(tv2)),
+            ) => {
+                // both type vars are unknown since we tried to resolve them
+                self.var_unification_table.union(*tv1, *tv2);
+                true
+            }
+
+            // The order of MaybeNeverTypeVar matters here.
+            // Unifying MaybeNeverTypeVar and TypeVar will let the latter become MaybeNeverTypeVar.
+            // Unifying MaybeNeverTypeVar and other concrete type will let the former become it.
+            (Ty::Infer(InferTy::TypeVar(tv)), other)
+            | (other, Ty::Infer(InferTy::TypeVar(tv)))
+            | (Ty::Infer(InferTy::MaybeNeverTypeVar(tv)), other)
+            | (other, Ty::Infer(InferTy::MaybeNeverTypeVar(tv)))
+            | (Ty::Infer(InferTy::IntVar(tv)), other @ ty_app!(TypeCtor::Int(_)))
+            | (other @ ty_app!(TypeCtor::Int(_)), Ty::Infer(InferTy::IntVar(tv)))
+            | (Ty::Infer(InferTy::FloatVar(tv)), other @ ty_app!(TypeCtor::Float(_)))
+            | (other @ ty_app!(TypeCtor::Float(_)), Ty::Infer(InferTy::FloatVar(tv))) => {
+                // the type var is unknown since we tried to resolve it
+                self.var_unification_table.union_value(*tv, TypeVarValue::Known(other.clone()));
+                true
+            }
+
+            _ => false,
+        }
+    }
+
+    fn new_type_var(&mut self) -> Ty {
+        Ty::Infer(InferTy::TypeVar(self.var_unification_table.new_key(TypeVarValue::Unknown)))
+    }
+
+    fn new_integer_var(&mut self) -> Ty {
+        Ty::Infer(InferTy::IntVar(self.var_unification_table.new_key(TypeVarValue::Unknown)))
+    }
+
+    fn new_float_var(&mut self) -> Ty {
+        Ty::Infer(InferTy::FloatVar(self.var_unification_table.new_key(TypeVarValue::Unknown)))
+    }
+
+    fn new_maybe_never_type_var(&mut self) -> Ty {
+        Ty::Infer(InferTy::MaybeNeverTypeVar(
+            self.var_unification_table.new_key(TypeVarValue::Unknown),
+        ))
+    }
+
+    /// Replaces Ty::Unknown by a new type var, so we can maybe still infer it.
+    fn insert_type_vars_shallow(&mut self, ty: Ty) -> Ty {
+        match ty {
+            Ty::Unknown => self.new_type_var(),
+            Ty::Apply(ApplicationTy { ctor: TypeCtor::Int(Uncertain::Unknown), .. }) => {
+                self.new_integer_var()
+            }
+            Ty::Apply(ApplicationTy { ctor: TypeCtor::Float(Uncertain::Unknown), .. }) => {
+                self.new_float_var()
+            }
+            _ => ty,
+        }
+    }
+
+    fn insert_type_vars(&mut self, ty: Ty) -> Ty {
+        ty.fold(&mut |ty| self.insert_type_vars_shallow(ty))
+    }
+
+    fn resolve_obligations_as_possible(&mut self) {
+        let obligations = mem::replace(&mut self.obligations, Vec::new());
+        for obligation in obligations {
+            let in_env = InEnvironment::new(self.trait_env.clone(), obligation.clone());
+            let canonicalized = self.canonicalizer().canonicalize_obligation(in_env);
+            let solution = self
+                .db
+                .trait_solve(self.resolver.krate().unwrap().into(), canonicalized.value.clone());
+
+            match solution {
+                Some(Solution::Unique(substs)) => {
+                    canonicalized.apply_solution(self, substs.0);
+                }
+                Some(Solution::Ambig(Guidance::Definite(substs))) => {
+                    canonicalized.apply_solution(self, substs.0);
+                    self.obligations.push(obligation);
+                }
+                Some(_) => {
+                    // FIXME use this when trying to resolve everything at the end
+                    self.obligations.push(obligation);
+                }
+                None => {
+                    // FIXME obligation cannot be fulfilled => diagnostic
+                }
+            };
+        }
+    }
+
+    /// Resolves the type as far as currently possible, replacing type variables
+    /// by their known types. All types returned by the infer_* functions should
+    /// be resolved as far as possible, i.e. contain no type variables with
+    /// known type.
+    fn resolve_ty_as_possible(&mut self, tv_stack: &mut Vec<TypeVarId>, ty: Ty) -> Ty {
+        self.resolve_obligations_as_possible();
+
+        ty.fold(&mut |ty| match ty {
+            Ty::Infer(tv) => {
+                let inner = tv.to_inner();
+                if tv_stack.contains(&inner) {
+                    tested_by!(type_var_cycles_resolve_as_possible);
+                    // recursive type
+                    return tv.fallback_value();
+                }
+                if let Some(known_ty) =
+                    self.var_unification_table.inlined_probe_value(inner).known()
+                {
+                    // known_ty may contain other variables that are known by now
+                    tv_stack.push(inner);
+                    let result = self.resolve_ty_as_possible(tv_stack, known_ty.clone());
+                    tv_stack.pop();
+                    result
+                } else {
+                    ty
+                }
+            }
+            _ => ty,
+        })
+    }
+
+    /// If `ty` is a type variable with known type, returns that type;
+    /// otherwise, return ty.
+    fn resolve_ty_shallow<'b>(&mut self, ty: &'b Ty) -> Cow<'b, Ty> {
+        let mut ty = Cow::Borrowed(ty);
+        // The type variable could resolve to a int/float variable. Hence try
+        // resolving up to three times; each type of variable shouldn't occur
+        // more than once
+        for i in 0..3 {
+            if i > 0 {
+                tested_by!(type_var_resolves_to_int_var);
+            }
+            match &*ty {
+                Ty::Infer(tv) => {
+                    let inner = tv.to_inner();
+                    match self.var_unification_table.inlined_probe_value(inner).known() {
+                        Some(known_ty) => {
+                            // The known_ty can't be a type var itself
+                            ty = Cow::Owned(known_ty.clone());
+                        }
+                        _ => return ty,
+                    }
+                }
+                _ => return ty,
+            }
+        }
+        log::error!("Inference variable still not resolved: {:?}", ty);
+        ty
+    }
+
+    /// Recurses through the given type, normalizing associated types mentioned
+    /// in it by replacing them by type variables and registering obligations to
+    /// resolve later. This should be done once for every type we get from some
+    /// type annotation (e.g. from a let type annotation, field type or function
+    /// call). `make_ty` handles this already, but e.g. for field types we need
+    /// to do it as well.
+    fn normalize_associated_types_in(&mut self, ty: Ty) -> Ty {
+        let ty = self.resolve_ty_as_possible(&mut vec![], ty);
+        ty.fold(&mut |ty| match ty {
+            Ty::Projection(proj_ty) => self.normalize_projection_ty(proj_ty),
+            _ => ty,
+        })
+    }
+
+    fn normalize_projection_ty(&mut self, proj_ty: ProjectionTy) -> Ty {
+        let var = self.new_type_var();
+        let predicate = ProjectionPredicate { projection_ty: proj_ty, ty: var.clone() };
+        let obligation = Obligation::Projection(predicate);
+        self.obligations.push(obligation);
+        var
+    }
+
+    /// Resolves the type completely; type variables without known type are
+    /// replaced by Ty::Unknown.
+    fn resolve_ty_completely(&mut self, tv_stack: &mut Vec<TypeVarId>, ty: Ty) -> Ty {
+        ty.fold(&mut |ty| match ty {
+            Ty::Infer(tv) => {
+                let inner = tv.to_inner();
+                if tv_stack.contains(&inner) {
+                    tested_by!(type_var_cycles_resolve_completely);
+                    // recursive type
+                    return tv.fallback_value();
+                }
+                if let Some(known_ty) =
+                    self.var_unification_table.inlined_probe_value(inner).known()
+                {
+                    // known_ty may contain other variables that are known by now
+                    tv_stack.push(inner);
+                    let result = self.resolve_ty_completely(tv_stack, known_ty.clone());
+                    tv_stack.pop();
+                    result
+                } else {
+                    tv.fallback_value()
+                }
+            }
+            _ => ty,
+        })
+    }
+
+    fn resolve_variant(&mut self, path: Option<&Path>) -> (Ty, Option<VariantId>) {
+        let path = match path {
+            Some(path) => path,
+            None => return (Ty::Unknown, None),
+        };
+        let resolver = &self.resolver;
+        // FIXME: this should resolve assoc items as well, see this example:
+        // https://play.rust-lang.org/?gist=087992e9e22495446c01c0d4e2d69521
+        match resolver.resolve_path_in_type_ns_fully(self.db, &path) {
+            Some(TypeNs::AdtId(AdtId::StructId(strukt))) => {
+                let substs = Ty::substs_from_path(self.db, resolver, path, strukt.into());
+                let ty = self.db.ty(strukt.into());
+                let ty = self.insert_type_vars(ty.apply_substs(substs));
+                (ty, Some(strukt.into()))
+            }
+            Some(TypeNs::EnumVariantId(var)) => {
+                let substs = Ty::substs_from_path(self.db, resolver, path, var.into());
+                let ty = self.db.ty(var.parent.into());
+                let ty = self.insert_type_vars(ty.apply_substs(substs));
+                (ty, Some(var.into()))
+            }
+            Some(_) | None => (Ty::Unknown, None),
+        }
+    }
+
+    fn collect_const(&mut self, data: &ConstData) {
+        self.return_ty = self.make_ty(&data.type_ref);
+    }
+
+    fn collect_fn(&mut self, data: &FunctionData) {
+        let body = Arc::clone(&self.body); // avoid borrow checker problem
+        for (type_ref, pat) in data.params.iter().zip(body.params.iter()) {
+            let ty = self.make_ty(type_ref);
+
+            self.infer_pat(*pat, &ty, BindingMode::default());
+        }
+        self.return_ty = self.make_ty(&data.ret_type);
+    }
+
+    fn infer_body(&mut self) {
+        self.infer_expr(self.body.body_expr, &Expectation::has_type(self.return_ty.clone()));
+    }
+
+    fn resolve_into_iter_item(&self) -> Option<TypeAliasId> {
+        let path = known::std_iter_into_iterator();
+        let trait_ = self.resolver.resolve_known_trait(self.db, &path)?;
+        self.db.trait_data(trait_).associated_type_by_name(&name::ITEM_TYPE)
+    }
+
+    fn resolve_ops_try_ok(&self) -> Option<TypeAliasId> {
+        let path = known::std_ops_try();
+        let trait_ = self.resolver.resolve_known_trait(self.db, &path)?;
+        self.db.trait_data(trait_).associated_type_by_name(&name::OK_TYPE)
+    }
+
+    fn resolve_future_future_output(&self) -> Option<TypeAliasId> {
+        let path = known::std_future_future();
+        let trait_ = self.resolver.resolve_known_trait(self.db, &path)?;
+        self.db.trait_data(trait_).associated_type_by_name(&name::OUTPUT_TYPE)
+    }
+
+    fn resolve_boxed_box(&self) -> Option<AdtId> {
+        let path = known::std_boxed_box();
+        let struct_ = self.resolver.resolve_known_struct(self.db, &path)?;
+        Some(struct_.into())
+    }
+}
+
+/// The ID of a type variable.
+#[derive(Copy, Clone, PartialEq, Eq, Hash, Debug)]
+pub struct TypeVarId(pub(super) u32);
+
+impl UnifyKey for TypeVarId {
+    type Value = TypeVarValue;
+
+    fn index(&self) -> u32 {
+        self.0
+    }
+
+    fn from_index(i: u32) -> Self {
+        TypeVarId(i)
+    }
+
+    fn tag() -> &'static str {
+        "TypeVarId"
+    }
+}
+
+/// The value of a type variable: either we already know the type, or we don't
+/// know it yet.
+#[derive(Clone, PartialEq, Eq, Debug)]
+pub enum TypeVarValue {
+    Known(Ty),
+    Unknown,
+}
+
+impl TypeVarValue {
+    fn known(&self) -> Option<&Ty> {
+        match self {
+            TypeVarValue::Known(ty) => Some(ty),
+            TypeVarValue::Unknown => None,
+        }
+    }
+}
+
+impl UnifyValue for TypeVarValue {
+    type Error = NoError;
+
+    fn unify_values(value1: &Self, value2: &Self) -> Result<Self, NoError> {
+        match (value1, value2) {
+            // We should never equate two type variables, both of which have
+            // known types. Instead, we recursively equate those types.
+            (TypeVarValue::Known(t1), TypeVarValue::Known(t2)) => panic!(
+                "equating two type variables, both of which have known types: {:?} and {:?}",
+                t1, t2
+            ),
+
+            // If one side is known, prefer that one.
+            (TypeVarValue::Known(..), TypeVarValue::Unknown) => Ok(value1.clone()),
+            (TypeVarValue::Unknown, TypeVarValue::Known(..)) => Ok(value2.clone()),
+
+            (TypeVarValue::Unknown, TypeVarValue::Unknown) => Ok(TypeVarValue::Unknown),
+        }
+    }
+}
+
+/// The kinds of placeholders we need during type inference. There's separate
+/// values for general types, and for integer and float variables. The latter
+/// two are used for inference of literal values (e.g. `100` could be one of
+/// several integer types).
+#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
+pub enum InferTy {
+    TypeVar(TypeVarId),
+    IntVar(TypeVarId),
+    FloatVar(TypeVarId),
+    MaybeNeverTypeVar(TypeVarId),
+}
+
+impl InferTy {
+    fn to_inner(self) -> TypeVarId {
+        match self {
+            InferTy::TypeVar(ty)
+            | InferTy::IntVar(ty)
+            | InferTy::FloatVar(ty)
+            | InferTy::MaybeNeverTypeVar(ty) => ty,
+        }
+    }
+
+    fn fallback_value(self) -> Ty {
+        match self {
+            InferTy::TypeVar(..) => Ty::Unknown,
+            InferTy::IntVar(..) => Ty::simple(TypeCtor::Int(Uncertain::Known(IntTy::i32()))),
+            InferTy::FloatVar(..) => Ty::simple(TypeCtor::Float(Uncertain::Known(FloatTy::f64()))),
+            InferTy::MaybeNeverTypeVar(..) => Ty::simple(TypeCtor::Never),
+        }
+    }
+}
+
+/// When inferring an expression, we propagate downward whatever type hint we
+/// are able in the form of an `Expectation`.
+#[derive(Clone, PartialEq, Eq, Debug)]
+struct Expectation {
+    ty: Ty,
+    // FIXME: In some cases, we need to be aware whether the expectation is that
+    // the type match exactly what we passed, or whether it just needs to be
+    // coercible to the expected type. See Expectation::rvalue_hint in rustc.
+}
+
+impl Expectation {
+    /// The expectation that the type of the expression needs to equal the given
+    /// type.
+    fn has_type(ty: Ty) -> Self {
+        Expectation { ty }
+    }
+
+    /// This expresses no expectation on the type.
+    fn none() -> Self {
+        Expectation { ty: Ty::Unknown }
+    }
+}
+
+mod diagnostics {
+    use hir_def::{expr::ExprId, FunctionId, HasSource, Lookup};
+    use hir_expand::diagnostics::DiagnosticSink;
+
+    use crate::{db::HirDatabase, diagnostics::NoSuchField};
+
+    #[derive(Debug, PartialEq, Eq, Clone)]
+    pub(super) enum InferenceDiagnostic {
+        NoSuchField { expr: ExprId, field: usize },
+    }
+
+    impl InferenceDiagnostic {
+        pub(super) fn add_to(
+            &self,
+            db: &impl HirDatabase,
+            owner: FunctionId,
+            sink: &mut DiagnosticSink,
+        ) {
+            match self {
+                InferenceDiagnostic::NoSuchField { expr, field } => {
+                    let file = owner.lookup(db).source(db).file_id;
+                    let (_, source_map) = db.body_with_source_map(owner.into());
+                    let field = source_map.field_syntax(*expr, *field);
+                    sink.push(NoSuchField { file, field })
+                }
+            }
+        }
+    }
+}
diff --git a/crates/ra_hir_ty/src/infer/coerce.rs b/crates/ra_hir_ty/src/infer/coerce.rs
new file mode 100644
index 000000000..d66a21932
--- /dev/null
+++ b/crates/ra_hir_ty/src/infer/coerce.rs
@@ -0,0 +1,354 @@
+//! Coercion logic. Coercions are certain type conversions that can implicitly
+//! happen in certain places, e.g. weakening `&mut` to `&` or deref coercions
+//! like going from `&Vec<T>` to `&[T]`.
+//!
+//! See: https://doc.rust-lang.org/nomicon/coercions.html
+
+use hir_def::{
+    lang_item::LangItemTarget,
+    resolver::{HasResolver, Resolver},
+    type_ref::Mutability,
+    AdtId,
+};
+use rustc_hash::FxHashMap;
+use test_utils::tested_by;
+
+use crate::{autoderef, db::HirDatabase, Substs, TraitRef, Ty, TypeCtor, TypeWalk};
+
+use super::{InEnvironment, InferTy, InferenceContext, TypeVarValue};
+
+impl<'a, D: HirDatabase> InferenceContext<'a, D> {
+    /// Unify two types, but may coerce the first one to the second one
+    /// using "implicit coercion rules" if needed.
+    pub(super) fn coerce(&mut self, from_ty: &Ty, to_ty: &Ty) -> bool {
+        let from_ty = self.resolve_ty_shallow(from_ty).into_owned();
+        let to_ty = self.resolve_ty_shallow(to_ty);
+        self.coerce_inner(from_ty, &to_ty)
+    }
+
+    /// Merge two types from different branches, with possible implicit coerce.
+    ///
+    /// Note that it is only possible that one type are coerced to another.
+    /// Coercing both types to another least upper bound type is not possible in rustc,
+    /// which will simply result in "incompatible types" error.
+    pub(super) fn coerce_merge_branch<'t>(&mut self, ty1: &Ty, ty2: &Ty) -> Ty {
+        if self.coerce(ty1, ty2) {
+            ty2.clone()
+        } else if self.coerce(ty2, ty1) {
+            ty1.clone()
+        } else {
+            tested_by!(coerce_merge_fail_fallback);
+            // For incompatible types, we use the latter one as result
+            // to be better recovery for `if` without `else`.
+            ty2.clone()
+        }
+    }
+
+    pub(super) fn init_coerce_unsized_map(
+        db: &'a D,
+        resolver: &Resolver,
+    ) -> FxHashMap<(TypeCtor, TypeCtor), usize> {
+        let krate = resolver.krate().unwrap();
+        let impls = match db.lang_item(krate.into(), "coerce_unsized".into()) {
+            Some(LangItemTarget::TraitId(trait_)) => {
+                db.impls_for_trait(krate.into(), trait_.into())
+            }
+            _ => return FxHashMap::default(),
+        };
+
+        impls
+            .iter()
+            .filter_map(|&impl_id| {
+                let impl_data = db.impl_data(impl_id);
+                let resolver = impl_id.resolver(db);
+                let target_ty = Ty::from_hir(db, &resolver, &impl_data.target_type);
+
+                // `CoerseUnsized` has one generic parameter for the target type.
+                let trait_ref = TraitRef::from_hir(
+                    db,
+                    &resolver,
+                    impl_data.target_trait.as_ref()?,
+                    Some(target_ty),
+                )?;
+                let cur_from_ty = trait_ref.substs.0.get(0)?;
+                let cur_to_ty = trait_ref.substs.0.get(1)?;
+
+                match (&cur_from_ty, cur_to_ty) {
+                    (ty_app!(ctor1, st1), ty_app!(ctor2, st2)) => {
+                        // FIXME: We return the first non-equal bound as the type parameter to coerce to unsized type.
+                        // This works for smart-pointer-like coercion, which covers all impls from std.
+                        st1.iter().zip(st2.iter()).enumerate().find_map(|(i, (ty1, ty2))| {
+                            match (ty1, ty2) {
+                                (Ty::Param { idx: p1, .. }, Ty::Param { idx: p2, .. })
+                                    if p1 != p2 =>
+                                {
+                                    Some(((*ctor1, *ctor2), i))
+                                }
+                                _ => None,
+                            }
+                        })
+                    }
+                    _ => None,
+                }
+            })
+            .collect()
+    }
+
+    fn coerce_inner(&mut self, mut from_ty: Ty, to_ty: &Ty) -> bool {
+        match (&from_ty, to_ty) {
+            // Never type will make type variable to fallback to Never Type instead of Unknown.
+            (ty_app!(TypeCtor::Never), Ty::Infer(InferTy::TypeVar(tv))) => {
+                let var = self.new_maybe_never_type_var();
+                self.var_unification_table.union_value(*tv, TypeVarValue::Known(var));
+                return true;
+            }
+            (ty_app!(TypeCtor::Never), _) => return true,
+
+            // Trivial cases, this should go after `never` check to
+            // avoid infer result type to be never
+            _ => {
+                if self.unify_inner_trivial(&from_ty, &to_ty) {
+                    return true;
+                }
+            }
+        }
+
+        // Pointer weakening and function to pointer
+        match (&mut from_ty, to_ty) {
+            // `*mut T`, `&mut T, `&T`` -> `*const T`
+            // `&mut T` -> `&T`
+            // `&mut T` -> `*mut T`
+            (ty_app!(c1@TypeCtor::RawPtr(_)), ty_app!(c2@TypeCtor::RawPtr(Mutability::Shared)))
+            | (ty_app!(c1@TypeCtor::Ref(_)), ty_app!(c2@TypeCtor::RawPtr(Mutability::Shared)))
+            | (ty_app!(c1@TypeCtor::Ref(_)), ty_app!(c2@TypeCtor::Ref(Mutability::Shared)))
+            | (ty_app!(c1@TypeCtor::Ref(Mutability::Mut)), ty_app!(c2@TypeCtor::RawPtr(_))) => {
+                *c1 = *c2;
+            }
+
+            // Illegal mutablity conversion
+            (
+                ty_app!(TypeCtor::RawPtr(Mutability::Shared)),
+                ty_app!(TypeCtor::RawPtr(Mutability::Mut)),
+            )
+            | (
+                ty_app!(TypeCtor::Ref(Mutability::Shared)),
+                ty_app!(TypeCtor::Ref(Mutability::Mut)),
+            ) => return false,
+
+            // `{function_type}` -> `fn()`
+            (ty_app!(TypeCtor::FnDef(_)), ty_app!(TypeCtor::FnPtr { .. })) => {
+                match from_ty.callable_sig(self.db) {
+                    None => return false,
+                    Some(sig) => {
+                        let num_args = sig.params_and_return.len() as u16 - 1;
+                        from_ty =
+                            Ty::apply(TypeCtor::FnPtr { num_args }, Substs(sig.params_and_return));
+                    }
+                }
+            }
+
+            _ => {}
+        }
+
+        if let Some(ret) = self.try_coerce_unsized(&from_ty, &to_ty) {
+            return ret;
+        }
+
+        // Auto Deref if cannot coerce
+        match (&from_ty, to_ty) {
+            // FIXME: DerefMut
+            (ty_app!(TypeCtor::Ref(_), st1), ty_app!(TypeCtor::Ref(_), st2)) => {
+                self.unify_autoderef_behind_ref(&st1[0], &st2[0])
+            }
+
+            // Otherwise, normal unify
+            _ => self.unify(&from_ty, to_ty),
+        }
+    }
+
+    /// Coerce a type using `from_ty: CoerceUnsized<ty_ty>`
+    ///
+    /// See: https://doc.rust-lang.org/nightly/std/marker/trait.CoerceUnsized.html
+    fn try_coerce_unsized(&mut self, from_ty: &Ty, to_ty: &Ty) -> Option<bool> {
+        let (ctor1, st1, ctor2, st2) = match (from_ty, to_ty) {
+            (ty_app!(ctor1, st1), ty_app!(ctor2, st2)) => (ctor1, st1, ctor2, st2),
+            _ => return None,
+        };
+
+        let coerce_generic_index = *self.coerce_unsized_map.get(&(*ctor1, *ctor2))?;
+
+        // Check `Unsize` first
+        match self.check_unsize_and_coerce(
+            st1.0.get(coerce_generic_index)?,
+            st2.0.get(coerce_generic_index)?,
+            0,
+        ) {
+            Some(true) => {}
+            ret => return ret,
+        }
+
+        let ret = st1
+            .iter()
+            .zip(st2.iter())
+            .enumerate()
+            .filter(|&(idx, _)| idx != coerce_generic_index)
+            .all(|(_, (ty1, ty2))| self.unify(ty1, ty2));
+
+        Some(ret)
+    }
+
+    /// Check if `from_ty: Unsize<to_ty>`, and coerce to `to_ty` if it holds.
+    ///
+    /// It should not be directly called. It is only used by `try_coerce_unsized`.
+    ///
+    /// See: https://doc.rust-lang.org/nightly/std/marker/trait.Unsize.html
+    fn check_unsize_and_coerce(&mut self, from_ty: &Ty, to_ty: &Ty, depth: usize) -> Option<bool> {
+        if depth > 1000 {
+            panic!("Infinite recursion in coercion");
+        }
+
+        match (&from_ty, &to_ty) {
+            // `[T; N]` -> `[T]`
+            (ty_app!(TypeCtor::Array, st1), ty_app!(TypeCtor::Slice, st2)) => {
+                Some(self.unify(&st1[0], &st2[0]))
+            }
+
+            // `T` -> `dyn Trait` when `T: Trait`
+            (_, Ty::Dyn(_)) => {
+                // FIXME: Check predicates
+                Some(true)
+            }
+
+            // `(..., T)` -> `(..., U)` when `T: Unsize<U>`
+            (
+                ty_app!(TypeCtor::Tuple { cardinality: len1 }, st1),
+                ty_app!(TypeCtor::Tuple { cardinality: len2 }, st2),
+            ) => {
+                if len1 != len2 || *len1 == 0 {
+                    return None;
+                }
+
+                match self.check_unsize_and_coerce(
+                    st1.last().unwrap(),
+                    st2.last().unwrap(),
+                    depth + 1,
+                ) {
+                    Some(true) => {}
+                    ret => return ret,
+                }
+
+                let ret = st1[..st1.len() - 1]
+                    .iter()
+                    .zip(&st2[..st2.len() - 1])
+                    .all(|(ty1, ty2)| self.unify(ty1, ty2));
+
+                Some(ret)
+            }
+
+            // Foo<..., T, ...> is Unsize<Foo<..., U, ...>> if:
+            // - T: Unsize<U>
+            // - Foo is a struct
+            // - Only the last field of Foo has a type involving T
+            // - T is not part of the type of any other fields
+            // - Bar<T>: Unsize<Bar<U>>, if the last field of Foo has type Bar<T>
+            (
+                ty_app!(TypeCtor::Adt(AdtId::StructId(struct1)), st1),
+                ty_app!(TypeCtor::Adt(AdtId::StructId(struct2)), st2),
+            ) if struct1 == struct2 => {
+                let field_tys = self.db.field_types((*struct1).into());
+                let struct_data = self.db.struct_data(*struct1);
+
+                let mut fields = struct_data.variant_data.fields().iter();
+                let (last_field_id, _data) = fields.next_back()?;
+
+                // Get the generic parameter involved in the last field.
+                let unsize_generic_index = {
+                    let mut index = None;
+                    let mut multiple_param = false;
+                    field_tys[last_field_id].walk(&mut |ty| match ty {
+                        &Ty::Param { idx, .. } => {
+                            if index.is_none() {
+                                index = Some(idx);
+                            } else if Some(idx) != index {
+                                multiple_param = true;
+                            }
+                        }
+                        _ => {}
+                    });
+
+                    if multiple_param {
+                        return None;
+                    }
+                    index?
+                };
+
+                // Check other fields do not involve it.
+                let mut multiple_used = false;
+                fields.for_each(|(field_id, _data)| {
+                    field_tys[field_id].walk(&mut |ty| match ty {
+                        &Ty::Param { idx, .. } if idx == unsize_generic_index => {
+                            multiple_used = true
+                        }
+                        _ => {}
+                    })
+                });
+                if multiple_used {
+                    return None;
+                }
+
+                let unsize_generic_index = unsize_generic_index as usize;
+
+                // Check `Unsize` first
+                match self.check_unsize_and_coerce(
+                    st1.get(unsize_generic_index)?,
+                    st2.get(unsize_generic_index)?,
+                    depth + 1,
+                ) {
+                    Some(true) => {}
+                    ret => return ret,
+                }
+
+                // Then unify other parameters
+                let ret = st1
+                    .iter()
+                    .zip(st2.iter())
+                    .enumerate()
+                    .filter(|&(idx, _)| idx != unsize_generic_index)
+                    .all(|(_, (ty1, ty2))| self.unify(ty1, ty2));
+
+                Some(ret)
+            }
+
+            _ => None,
+        }
+    }
+
+    /// Unify `from_ty` to `to_ty` with optional auto Deref
+    ///
+    /// Note that the parameters are already stripped the outer reference.
+    fn unify_autoderef_behind_ref(&mut self, from_ty: &Ty, to_ty: &Ty) -> bool {
+        let canonicalized = self.canonicalizer().canonicalize_ty(from_ty.clone());
+        let to_ty = self.resolve_ty_shallow(&to_ty);
+        // FIXME: Auto DerefMut
+        for derefed_ty in autoderef::autoderef(
+            self.db,
+            self.resolver.krate(),
+            InEnvironment {
+                value: canonicalized.value.clone(),
+                environment: self.trait_env.clone(),
+            },
+        ) {
+            let derefed_ty = canonicalized.decanonicalize_ty(derefed_ty.value);
+            match (&*self.resolve_ty_shallow(&derefed_ty), &*to_ty) {
+                // Stop when constructor matches.
+                (ty_app!(from_ctor, st1), ty_app!(to_ctor, st2)) if from_ctor == to_ctor => {
+                    // It will not recurse to `coerce`.
+                    return self.unify_substs(st1, st2, 0);
+                }
+                _ => {}
+            }
+        }
+
+        false
+    }
+}
diff --git a/crates/ra_hir_ty/src/infer/expr.rs b/crates/ra_hir_ty/src/infer/expr.rs
new file mode 100644
index 000000000..2f9ca4bbb
--- /dev/null
+++ b/crates/ra_hir_ty/src/infer/expr.rs
@@ -0,0 +1,686 @@
+//! Type inference for expressions.
+
+use std::iter::{repeat, repeat_with};
+use std::sync::Arc;
+
+use hir_def::{
+    builtin_type::Signedness,
+    expr::{Array, BinaryOp, Expr, ExprId, Literal, Statement, UnaryOp},
+    generics::GenericParams,
+    path::{GenericArg, GenericArgs},
+    resolver::resolver_for_expr,
+    AdtId, ContainerId, Lookup, StructFieldId,
+};
+use hir_expand::name::{self, Name};
+
+use crate::{
+    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};
+
+impl<'a, D: HirDatabase> InferenceContext<'a, D> {
+    pub(super) fn infer_expr(&mut self, tgt_expr: ExprId, expected: &Expectation) -> Ty {
+        let ty = self.infer_expr_inner(tgt_expr, expected);
+        let could_unify = self.unify(&ty, &expected.ty);
+        if !could_unify {
+            self.result.type_mismatches.insert(
+                tgt_expr,
+                TypeMismatch { expected: expected.ty.clone(), actual: ty.clone() },
+            );
+        }
+        let ty = self.resolve_ty_as_possible(&mut vec![], ty);
+        ty
+    }
+
+    /// Infer type of expression with possibly implicit coerce to the expected type.
+    /// Return the type after possible coercion.
+    fn infer_expr_coerce(&mut self, expr: ExprId, expected: &Expectation) -> Ty {
+        let ty = self.infer_expr_inner(expr, &expected);
+        let ty = if !self.coerce(&ty, &expected.ty) {
+            self.result
+                .type_mismatches
+                .insert(expr, TypeMismatch { expected: expected.ty.clone(), actual: ty.clone() });
+            // Return actual type when type mismatch.
+            // This is needed for diagnostic when return type mismatch.
+            ty
+        } else if expected.ty == Ty::Unknown {
+            ty
+        } else {
+            expected.ty.clone()
+        };
+
+        self.resolve_ty_as_possible(&mut vec![], ty)
+    }
+
+    fn infer_expr_inner(&mut self, tgt_expr: ExprId, expected: &Expectation) -> Ty {
+        let body = Arc::clone(&self.body); // avoid borrow checker problem
+        let ty = match &body[tgt_expr] {
+            Expr::Missing => Ty::Unknown,
+            Expr::If { condition, then_branch, else_branch } => {
+                // if let is desugared to match, so this is always simple if
+                self.infer_expr(*condition, &Expectation::has_type(Ty::simple(TypeCtor::Bool)));
+
+                let then_ty = self.infer_expr_inner(*then_branch, &expected);
+                let else_ty = match else_branch {
+                    Some(else_branch) => self.infer_expr_inner(*else_branch, &expected),
+                    None => Ty::unit(),
+                };
+
+                self.coerce_merge_branch(&then_ty, &else_ty)
+            }
+            Expr::Block { statements, tail } => self.infer_block(statements, *tail, expected),
+            Expr::TryBlock { body } => {
+                let _inner = self.infer_expr(*body, expected);
+                // FIXME should be std::result::Result<{inner}, _>
+                Ty::Unknown
+            }
+            Expr::Loop { body } => {
+                self.infer_expr(*body, &Expectation::has_type(Ty::unit()));
+                // FIXME handle break with value
+                Ty::simple(TypeCtor::Never)
+            }
+            Expr::While { condition, body } => {
+                // while let is desugared to a match loop, so this is always simple while
+                self.infer_expr(*condition, &Expectation::has_type(Ty::simple(TypeCtor::Bool)));
+                self.infer_expr(*body, &Expectation::has_type(Ty::unit()));
+                Ty::unit()
+            }
+            Expr::For { iterable, body, pat } => {
+                let iterable_ty = self.infer_expr(*iterable, &Expectation::none());
+
+                let pat_ty = match self.resolve_into_iter_item() {
+                    Some(into_iter_item_alias) => {
+                        let pat_ty = self.new_type_var();
+                        let projection = ProjectionPredicate {
+                            ty: pat_ty.clone(),
+                            projection_ty: ProjectionTy {
+                                associated_ty: into_iter_item_alias,
+                                parameters: Substs::single(iterable_ty),
+                            },
+                        };
+                        self.obligations.push(Obligation::Projection(projection));
+                        self.resolve_ty_as_possible(&mut vec![], pat_ty)
+                    }
+                    None => Ty::Unknown,
+                };
+
+                self.infer_pat(*pat, &pat_ty, BindingMode::default());
+                self.infer_expr(*body, &Expectation::has_type(Ty::unit()));
+                Ty::unit()
+            }
+            Expr::Lambda { body, args, arg_types } => {
+                assert_eq!(args.len(), arg_types.len());
+
+                let mut sig_tys = Vec::new();
+
+                for (arg_pat, arg_type) in args.iter().zip(arg_types.iter()) {
+                    let expected = if let Some(type_ref) = arg_type {
+                        self.make_ty(type_ref)
+                    } else {
+                        Ty::Unknown
+                    };
+                    let arg_ty = self.infer_pat(*arg_pat, &expected, BindingMode::default());
+                    sig_tys.push(arg_ty);
+                }
+
+                // add return type
+                let ret_ty = self.new_type_var();
+                sig_tys.push(ret_ty.clone());
+                let sig_ty = Ty::apply(
+                    TypeCtor::FnPtr { num_args: sig_tys.len() as u16 - 1 },
+                    Substs(sig_tys.into()),
+                );
+                let closure_ty = Ty::apply_one(
+                    TypeCtor::Closure { def: self.owner.into(), expr: tgt_expr },
+                    sig_ty,
+                );
+
+                // Eagerly try to relate the closure type with the expected
+                // type, otherwise we often won't have enough information to
+                // infer the body.
+                self.coerce(&closure_ty, &expected.ty);
+
+                self.infer_expr(*body, &Expectation::has_type(ret_ty));
+                closure_ty
+            }
+            Expr::Call { callee, args } => {
+                let callee_ty = self.infer_expr(*callee, &Expectation::none());
+                let (param_tys, ret_ty) = match callee_ty.callable_sig(self.db) {
+                    Some(sig) => (sig.params().to_vec(), sig.ret().clone()),
+                    None => {
+                        // Not callable
+                        // FIXME: report an error
+                        (Vec::new(), Ty::Unknown)
+                    }
+                };
+                self.register_obligations_for_call(&callee_ty);
+                self.check_call_arguments(args, &param_tys);
+                let ret_ty = self.normalize_associated_types_in(ret_ty);
+                ret_ty
+            }
+            Expr::MethodCall { receiver, args, method_name, generic_args } => self
+                .infer_method_call(tgt_expr, *receiver, &args, &method_name, generic_args.as_ref()),
+            Expr::Match { expr, arms } => {
+                let input_ty = self.infer_expr(*expr, &Expectation::none());
+
+                let mut result_ty = self.new_maybe_never_type_var();
+
+                for arm in arms {
+                    for &pat in &arm.pats {
+                        let _pat_ty = self.infer_pat(pat, &input_ty, BindingMode::default());
+                    }
+                    if let Some(guard_expr) = arm.guard {
+                        self.infer_expr(
+                            guard_expr,
+                            &Expectation::has_type(Ty::simple(TypeCtor::Bool)),
+                        );
+                    }
+
+                    let arm_ty = self.infer_expr_inner(arm.expr, &expected);
+                    result_ty = self.coerce_merge_branch(&result_ty, &arm_ty);
+                }
+
+                result_ty
+            }
+            Expr::Path(p) => {
+                // FIXME this could be more efficient...
+                let resolver = resolver_for_expr(self.db, self.owner.into(), tgt_expr);
+                self.infer_path(&resolver, p, tgt_expr.into()).unwrap_or(Ty::Unknown)
+            }
+            Expr::Continue => Ty::simple(TypeCtor::Never),
+            Expr::Break { expr } => {
+                if let Some(expr) = expr {
+                    // FIXME handle break with value
+                    self.infer_expr(*expr, &Expectation::none());
+                }
+                Ty::simple(TypeCtor::Never)
+            }
+            Expr::Return { expr } => {
+                if let Some(expr) = expr {
+                    self.infer_expr(*expr, &Expectation::has_type(self.return_ty.clone()));
+                }
+                Ty::simple(TypeCtor::Never)
+            }
+            Expr::RecordLit { path, fields, spread } => {
+                let (ty, def_id) = self.resolve_variant(path.as_ref());
+                if let Some(variant) = def_id {
+                    self.write_variant_resolution(tgt_expr.into(), variant);
+                }
+
+                self.unify(&ty, &expected.ty);
+
+                let substs = ty.substs().unwrap_or_else(Substs::empty);
+                let field_types =
+                    def_id.map(|it| self.db.field_types(it.into())).unwrap_or_default();
+                let variant_data = def_id.map(|it| variant_data(self.db, it));
+                for (field_idx, field) in fields.iter().enumerate() {
+                    let field_def =
+                        variant_data.as_ref().and_then(|it| match it.field(&field.name) {
+                            Some(local_id) => {
+                                Some(StructFieldId { parent: def_id.unwrap(), local_id })
+                            }
+                            None => {
+                                self.push_diagnostic(InferenceDiagnostic::NoSuchField {
+                                    expr: tgt_expr,
+                                    field: field_idx,
+                                });
+                                None
+                            }
+                        });
+                    if let Some(field_def) = field_def {
+                        self.result.record_field_resolutions.insert(field.expr, field_def);
+                    }
+                    let field_ty = field_def
+                        .map_or(Ty::Unknown, |it| field_types[it.local_id].clone())
+                        .subst(&substs);
+                    self.infer_expr_coerce(field.expr, &Expectation::has_type(field_ty));
+                }
+                if let Some(expr) = spread {
+                    self.infer_expr(*expr, &Expectation::has_type(ty.clone()));
+                }
+                ty
+            }
+            Expr::Field { expr, name } => {
+                let receiver_ty = self.infer_expr(*expr, &Expectation::none());
+                let canonicalized = self.canonicalizer().canonicalize_ty(receiver_ty);
+                let ty = autoderef::autoderef(
+                    self.db,
+                    self.resolver.krate(),
+                    InEnvironment {
+                        value: canonicalized.value.clone(),
+                        environment: self.trait_env.clone(),
+                    },
+                )
+                .find_map(|derefed_ty| match canonicalized.decanonicalize_ty(derefed_ty.value) {
+                    Ty::Apply(a_ty) => match a_ty.ctor {
+                        TypeCtor::Tuple { .. } => name
+                            .as_tuple_index()
+                            .and_then(|idx| a_ty.parameters.0.get(idx).cloned()),
+                        TypeCtor::Adt(AdtId::StructId(s)) => {
+                            self.db.struct_data(s).variant_data.field(name).map(|local_id| {
+                                let field = StructFieldId { parent: s.into(), local_id }.into();
+                                self.write_field_resolution(tgt_expr, field);
+                                self.db.field_types(s.into())[field.local_id]
+                                    .clone()
+                                    .subst(&a_ty.parameters)
+                            })
+                        }
+                        // FIXME:
+                        TypeCtor::Adt(AdtId::UnionId(_)) => None,
+                        _ => None,
+                    },
+                    _ => None,
+                })
+                .unwrap_or(Ty::Unknown);
+                let ty = self.insert_type_vars(ty);
+                self.normalize_associated_types_in(ty)
+            }
+            Expr::Await { expr } => {
+                let inner_ty = self.infer_expr(*expr, &Expectation::none());
+                let ty = match self.resolve_future_future_output() {
+                    Some(future_future_output_alias) => {
+                        let ty = self.new_type_var();
+                        let projection = ProjectionPredicate {
+                            ty: ty.clone(),
+                            projection_ty: ProjectionTy {
+                                associated_ty: future_future_output_alias,
+                                parameters: Substs::single(inner_ty),
+                            },
+                        };
+                        self.obligations.push(Obligation::Projection(projection));
+                        self.resolve_ty_as_possible(&mut vec![], ty)
+                    }
+                    None => Ty::Unknown,
+                };
+                ty
+            }
+            Expr::Try { expr } => {
+                let inner_ty = self.infer_expr(*expr, &Expectation::none());
+                let ty = match self.resolve_ops_try_ok() {
+                    Some(ops_try_ok_alias) => {
+                        let ty = self.new_type_var();
+                        let projection = ProjectionPredicate {
+                            ty: ty.clone(),
+                            projection_ty: ProjectionTy {
+                                associated_ty: ops_try_ok_alias,
+                                parameters: Substs::single(inner_ty),
+                            },
+                        };
+                        self.obligations.push(Obligation::Projection(projection));
+                        self.resolve_ty_as_possible(&mut vec![], ty)
+                    }
+                    None => Ty::Unknown,
+                };
+                ty
+            }
+            Expr::Cast { expr, type_ref } => {
+                let _inner_ty = self.infer_expr(*expr, &Expectation::none());
+                let cast_ty = self.make_ty(type_ref);
+                // FIXME check the cast...
+                cast_ty
+            }
+            Expr::Ref { expr, mutability } => {
+                let expectation =
+                    if let Some((exp_inner, exp_mutability)) = &expected.ty.as_reference() {
+                        if *exp_mutability == Mutability::Mut && *mutability == Mutability::Shared {
+                            // FIXME: throw type error - expected mut reference but found shared ref,
+                            // which cannot be coerced
+                        }
+                        Expectation::has_type(Ty::clone(exp_inner))
+                    } else {
+                        Expectation::none()
+                    };
+                // FIXME reference coercions etc.
+                let inner_ty = self.infer_expr(*expr, &expectation);
+                Ty::apply_one(TypeCtor::Ref(*mutability), inner_ty)
+            }
+            Expr::Box { expr } => {
+                let inner_ty = self.infer_expr(*expr, &Expectation::none());
+                if let Some(box_) = self.resolve_boxed_box() {
+                    Ty::apply_one(TypeCtor::Adt(box_), inner_ty)
+                } else {
+                    Ty::Unknown
+                }
+            }
+            Expr::UnaryOp { expr, op } => {
+                let inner_ty = self.infer_expr(*expr, &Expectation::none());
+                match op {
+                    UnaryOp::Deref => match self.resolver.krate() {
+                        Some(krate) => {
+                            let canonicalized = self.canonicalizer().canonicalize_ty(inner_ty);
+                            match autoderef::deref(
+                                self.db,
+                                krate,
+                                InEnvironment {
+                                    value: &canonicalized.value,
+                                    environment: self.trait_env.clone(),
+                                },
+                            ) {
+                                Some(derefed_ty) => {
+                                    canonicalized.decanonicalize_ty(derefed_ty.value)
+                                }
+                                None => Ty::Unknown,
+                            }
+                        }
+                        None => Ty::Unknown,
+                    },
+                    UnaryOp::Neg => {
+                        match &inner_ty {
+                            Ty::Apply(a_ty) => match a_ty.ctor {
+                                TypeCtor::Int(Uncertain::Unknown)
+                                | TypeCtor::Int(Uncertain::Known(IntTy {
+                                    signedness: Signedness::Signed,
+                                    ..
+                                }))
+                                | TypeCtor::Float(..) => inner_ty,
+                                _ => Ty::Unknown,
+                            },
+                            Ty::Infer(InferTy::IntVar(..)) | Ty::Infer(InferTy::FloatVar(..)) => {
+                                inner_ty
+                            }
+                            // FIXME: resolve ops::Neg trait
+                            _ => Ty::Unknown,
+                        }
+                    }
+                    UnaryOp::Not => {
+                        match &inner_ty {
+                            Ty::Apply(a_ty) => match a_ty.ctor {
+                                TypeCtor::Bool | TypeCtor::Int(_) => inner_ty,
+                                _ => Ty::Unknown,
+                            },
+                            Ty::Infer(InferTy::IntVar(..)) => inner_ty,
+                            // FIXME: resolve ops::Not trait for inner_ty
+                            _ => Ty::Unknown,
+                        }
+                    }
+                }
+            }
+            Expr::BinaryOp { lhs, rhs, op } => match op {
+                Some(op) => {
+                    let lhs_expectation = match op {
+                        BinaryOp::LogicOp(..) => Expectation::has_type(Ty::simple(TypeCtor::Bool)),
+                        _ => Expectation::none(),
+                    };
+                    let lhs_ty = self.infer_expr(*lhs, &lhs_expectation);
+                    // FIXME: find implementation of trait corresponding to operation
+                    // symbol and resolve associated `Output` type
+                    let rhs_expectation = op::binary_op_rhs_expectation(*op, lhs_ty);
+                    let rhs_ty = self.infer_expr(*rhs, &Expectation::has_type(rhs_expectation));
+
+                    // FIXME: similar as above, return ty is often associated trait type
+                    op::binary_op_return_ty(*op, rhs_ty)
+                }
+                _ => Ty::Unknown,
+            },
+            Expr::Index { base, index } => {
+                let _base_ty = self.infer_expr(*base, &Expectation::none());
+                let _index_ty = self.infer_expr(*index, &Expectation::none());
+                // FIXME: use `std::ops::Index::Output` to figure out the real return type
+                Ty::Unknown
+            }
+            Expr::Tuple { exprs } => {
+                let mut tys = match &expected.ty {
+                    ty_app!(TypeCtor::Tuple { .. }, st) => st
+                        .iter()
+                        .cloned()
+                        .chain(repeat_with(|| self.new_type_var()))
+                        .take(exprs.len())
+                        .collect::<Vec<_>>(),
+                    _ => (0..exprs.len()).map(|_| self.new_type_var()).collect(),
+                };
+
+                for (expr, ty) in exprs.iter().zip(tys.iter_mut()) {
+                    self.infer_expr_coerce(*expr, &Expectation::has_type(ty.clone()));
+                }
+
+                Ty::apply(TypeCtor::Tuple { cardinality: tys.len() as u16 }, Substs(tys.into()))
+            }
+            Expr::Array(array) => {
+                let elem_ty = match &expected.ty {
+                    ty_app!(TypeCtor::Array, st) | ty_app!(TypeCtor::Slice, st) => {
+                        st.as_single().clone()
+                    }
+                    _ => self.new_type_var(),
+                };
+
+                match array {
+                    Array::ElementList(items) => {
+                        for expr in items.iter() {
+                            self.infer_expr_coerce(*expr, &Expectation::has_type(elem_ty.clone()));
+                        }
+                    }
+                    Array::Repeat { initializer, repeat } => {
+                        self.infer_expr_coerce(
+                            *initializer,
+                            &Expectation::has_type(elem_ty.clone()),
+                        );
+                        self.infer_expr(
+                            *repeat,
+                            &Expectation::has_type(Ty::simple(TypeCtor::Int(Uncertain::Known(
+                                IntTy::usize(),
+                            )))),
+                        );
+                    }
+                }
+
+                Ty::apply_one(TypeCtor::Array, elem_ty)
+            }
+            Expr::Literal(lit) => match lit {
+                Literal::Bool(..) => Ty::simple(TypeCtor::Bool),
+                Literal::String(..) => {
+                    Ty::apply_one(TypeCtor::Ref(Mutability::Shared), Ty::simple(TypeCtor::Str))
+                }
+                Literal::ByteString(..) => {
+                    let byte_type = Ty::simple(TypeCtor::Int(Uncertain::Known(IntTy::u8())));
+                    let slice_type = Ty::apply_one(TypeCtor::Slice, byte_type);
+                    Ty::apply_one(TypeCtor::Ref(Mutability::Shared), slice_type)
+                }
+                Literal::Char(..) => Ty::simple(TypeCtor::Char),
+                Literal::Int(_v, ty) => Ty::simple(TypeCtor::Int((*ty).into())),
+                Literal::Float(_v, ty) => Ty::simple(TypeCtor::Float((*ty).into())),
+            },
+        };
+        // use a new type variable if we got Ty::Unknown here
+        let ty = self.insert_type_vars_shallow(ty);
+        let ty = self.resolve_ty_as_possible(&mut vec![], ty);
+        self.write_expr_ty(tgt_expr, ty.clone());
+        ty
+    }
+
+    fn infer_block(
+        &mut self,
+        statements: &[Statement],
+        tail: Option<ExprId>,
+        expected: &Expectation,
+    ) -> Ty {
+        let mut diverges = false;
+        for stmt in statements {
+            match stmt {
+                Statement::Let { pat, type_ref, initializer } => {
+                    let decl_ty =
+                        type_ref.as_ref().map(|tr| self.make_ty(tr)).unwrap_or(Ty::Unknown);
+
+                    // Always use the declared type when specified
+                    let mut ty = decl_ty.clone();
+
+                    if let Some(expr) = initializer {
+                        let actual_ty =
+                            self.infer_expr_coerce(*expr, &Expectation::has_type(decl_ty.clone()));
+                        if decl_ty == Ty::Unknown {
+                            ty = actual_ty;
+                        }
+                    }
+
+                    let ty = self.resolve_ty_as_possible(&mut vec![], ty);
+                    self.infer_pat(*pat, &ty, BindingMode::default());
+                }
+                Statement::Expr(expr) => {
+                    if let ty_app!(TypeCtor::Never) = self.infer_expr(*expr, &Expectation::none()) {
+                        diverges = true;
+                    }
+                }
+            }
+        }
+
+        let ty = if let Some(expr) = tail {
+            self.infer_expr_coerce(expr, expected)
+        } else {
+            self.coerce(&Ty::unit(), &expected.ty);
+            Ty::unit()
+        };
+        if diverges {
+            Ty::simple(TypeCtor::Never)
+        } else {
+            ty
+        }
+    }
+
+    fn infer_method_call(
+        &mut self,
+        tgt_expr: ExprId,
+        receiver: ExprId,
+        args: &[ExprId],
+        method_name: &Name,
+        generic_args: Option<&GenericArgs>,
+    ) -> Ty {
+        let receiver_ty = self.infer_expr(receiver, &Expectation::none());
+        let canonicalized_receiver = self.canonicalizer().canonicalize_ty(receiver_ty.clone());
+        let resolved = method_resolution::lookup_method(
+            &canonicalized_receiver.value,
+            self.db,
+            method_name,
+            &self.resolver,
+        );
+        let (derefed_receiver_ty, method_ty, def_generics) = match resolved {
+            Some((ty, func)) => {
+                let ty = canonicalized_receiver.decanonicalize_ty(ty);
+                self.write_method_resolution(tgt_expr, func);
+                (ty, self.db.value_ty(func.into()), Some(self.db.generic_params(func.into())))
+            }
+            None => (receiver_ty, Ty::Unknown, None),
+        };
+        let substs = self.substs_for_method_call(def_generics, generic_args, &derefed_receiver_ty);
+        let method_ty = method_ty.apply_substs(substs);
+        let method_ty = self.insert_type_vars(method_ty);
+        self.register_obligations_for_call(&method_ty);
+        let (expected_receiver_ty, param_tys, ret_ty) = match method_ty.callable_sig(self.db) {
+            Some(sig) => {
+                if !sig.params().is_empty() {
+                    (sig.params()[0].clone(), sig.params()[1..].to_vec(), sig.ret().clone())
+                } else {
+                    (Ty::Unknown, Vec::new(), sig.ret().clone())
+                }
+            }
+            None => (Ty::Unknown, Vec::new(), Ty::Unknown),
+        };
+        // Apply autoref so the below unification works correctly
+        // FIXME: return correct autorefs from lookup_method
+        let actual_receiver_ty = match expected_receiver_ty.as_reference() {
+            Some((_, mutability)) => Ty::apply_one(TypeCtor::Ref(mutability), derefed_receiver_ty),
+            _ => derefed_receiver_ty,
+        };
+        self.unify(&expected_receiver_ty, &actual_receiver_ty);
+
+        self.check_call_arguments(args, &param_tys);
+        let ret_ty = self.normalize_associated_types_in(ret_ty);
+        ret_ty
+    }
+
+    fn check_call_arguments(&mut self, args: &[ExprId], param_tys: &[Ty]) {
+        // Quoting https://github.com/rust-lang/rust/blob/6ef275e6c3cb1384ec78128eceeb4963ff788dca/src/librustc_typeck/check/mod.rs#L3325 --
+        // We do this in a pretty awful way: first we type-check any arguments
+        // that are not closures, then we type-check the closures. This is so
+        // that we have more information about the types of arguments when we
+        // type-check the functions. This isn't really the right way to do this.
+        for &check_closures in &[false, true] {
+            let param_iter = param_tys.iter().cloned().chain(repeat(Ty::Unknown));
+            for (&arg, param_ty) in args.iter().zip(param_iter) {
+                let is_closure = match &self.body[arg] {
+                    Expr::Lambda { .. } => true,
+                    _ => false,
+                };
+
+                if is_closure != check_closures {
+                    continue;
+                }
+
+                let param_ty = self.normalize_associated_types_in(param_ty);
+                self.infer_expr_coerce(arg, &Expectation::has_type(param_ty.clone()));
+            }
+        }
+    }
+
+    fn substs_for_method_call(
+        &mut self,
+        def_generics: Option<Arc<GenericParams>>,
+        generic_args: Option<&GenericArgs>,
+        receiver_ty: &Ty,
+    ) -> Substs {
+        let (parent_param_count, param_count) =
+            def_generics.as_ref().map_or((0, 0), |g| (g.count_parent_params(), g.params.len()));
+        let mut substs = Vec::with_capacity(parent_param_count + param_count);
+        // Parent arguments are unknown, except for the receiver type
+        if let Some(parent_generics) = def_generics.and_then(|p| p.parent_params.clone()) {
+            for param in &parent_generics.params {
+                if param.name == name::SELF_TYPE {
+                    substs.push(receiver_ty.clone());
+                } else {
+                    substs.push(Ty::Unknown);
+                }
+            }
+        }
+        // handle provided type arguments
+        if let Some(generic_args) = generic_args {
+            // if args are provided, it should be all of them, but we can't rely on that
+            for arg in generic_args.args.iter().take(param_count) {
+                match arg {
+                    GenericArg::Type(type_ref) => {
+                        let ty = self.make_ty(type_ref);
+                        substs.push(ty);
+                    }
+                }
+            }
+        };
+        let supplied_params = substs.len();
+        for _ in supplied_params..parent_param_count + param_count {
+            substs.push(Ty::Unknown);
+        }
+        assert_eq!(substs.len(), parent_param_count + param_count);
+        Substs(substs.into())
+    }
+
+    fn register_obligations_for_call(&mut self, callable_ty: &Ty) {
+        if let Ty::Apply(a_ty) = callable_ty {
+            if let TypeCtor::FnDef(def) = a_ty.ctor {
+                let generic_predicates = self.db.generic_predicates(def.into());
+                for predicate in generic_predicates.iter() {
+                    let predicate = predicate.clone().subst(&a_ty.parameters);
+                    if let Some(obligation) = Obligation::from_predicate(predicate) {
+                        self.obligations.push(obligation);
+                    }
+                }
+                // add obligation for trait implementation, if this is a trait method
+                match def {
+                    CallableDef::FunctionId(f) => {
+                        if let ContainerId::TraitId(trait_) = f.lookup(self.db).container {
+                            // construct a TraitDef
+                            let substs = a_ty.parameters.prefix(
+                                self.db
+                                    .generic_params(trait_.into())
+                                    .count_params_including_parent(),
+                            );
+                            self.obligations.push(Obligation::Trait(TraitRef {
+                                trait_: trait_.into(),
+                                substs,
+                            }));
+                        }
+                    }
+                    CallableDef::StructId(_) | CallableDef::EnumVariantId(_) => {}
+                }
+            }
+        }
+    }
+}
diff --git a/crates/ra_hir_ty/src/infer/pat.rs b/crates/ra_hir_ty/src/infer/pat.rs
new file mode 100644
index 000000000..1ebb36239
--- /dev/null
+++ b/crates/ra_hir_ty/src/infer/pat.rs
@@ -0,0 +1,186 @@
+//! Type inference for patterns.
+
+use std::iter::repeat;
+use std::sync::Arc;
+
+use hir_def::{
+    expr::{BindingAnnotation, Pat, PatId, RecordFieldPat},
+    path::Path,
+    type_ref::Mutability,
+};
+use hir_expand::name::Name;
+use test_utils::tested_by;
+
+use super::{BindingMode, InferenceContext};
+use crate::{db::HirDatabase, utils::variant_data, Substs, Ty, TypeCtor, TypeWalk};
+
+impl<'a, D: HirDatabase> InferenceContext<'a, D> {
+    fn infer_tuple_struct_pat(
+        &mut self,
+        path: Option<&Path>,
+        subpats: &[PatId],
+        expected: &Ty,
+        default_bm: BindingMode,
+    ) -> Ty {
+        let (ty, def) = self.resolve_variant(path);
+        let var_data = def.map(|it| variant_data(self.db, it));
+        self.unify(&ty, expected);
+
+        let substs = ty.substs().unwrap_or_else(Substs::empty);
+
+        let field_tys = def.map(|it| self.db.field_types(it.into())).unwrap_or_default();
+
+        for (i, &subpat) in subpats.iter().enumerate() {
+            let expected_ty = var_data
+                .as_ref()
+                .and_then(|d| d.field(&Name::new_tuple_field(i)))
+                .map_or(Ty::Unknown, |field| field_tys[field].clone())
+                .subst(&substs);
+            let expected_ty = self.normalize_associated_types_in(expected_ty);
+            self.infer_pat(subpat, &expected_ty, default_bm);
+        }
+
+        ty
+    }
+
+    fn infer_record_pat(
+        &mut self,
+        path: Option<&Path>,
+        subpats: &[RecordFieldPat],
+        expected: &Ty,
+        default_bm: BindingMode,
+        id: PatId,
+    ) -> Ty {
+        let (ty, def) = self.resolve_variant(path);
+        let var_data = def.map(|it| variant_data(self.db, it));
+        if let Some(variant) = def {
+            self.write_variant_resolution(id.into(), variant);
+        }
+
+        self.unify(&ty, expected);
+
+        let substs = ty.substs().unwrap_or_else(Substs::empty);
+
+        let field_tys = def.map(|it| self.db.field_types(it.into())).unwrap_or_default();
+        for subpat in subpats {
+            let matching_field = var_data.as_ref().and_then(|it| it.field(&subpat.name));
+            let expected_ty =
+                matching_field.map_or(Ty::Unknown, |field| field_tys[field].clone()).subst(&substs);
+            let expected_ty = self.normalize_associated_types_in(expected_ty);
+            self.infer_pat(subpat.pat, &expected_ty, default_bm);
+        }
+
+        ty
+    }
+
+    pub(super) fn infer_pat(
+        &mut self,
+        pat: PatId,
+        mut expected: &Ty,
+        mut default_bm: BindingMode,
+    ) -> Ty {
+        let body = Arc::clone(&self.body); // avoid borrow checker problem
+
+        let is_non_ref_pat = match &body[pat] {
+            Pat::Tuple(..)
+            | Pat::TupleStruct { .. }
+            | Pat::Record { .. }
+            | Pat::Range { .. }
+            | Pat::Slice { .. } => true,
+            // FIXME: Path/Lit might actually evaluate to ref, but inference is unimplemented.
+            Pat::Path(..) | Pat::Lit(..) => true,
+            Pat::Wild | Pat::Bind { .. } | Pat::Ref { .. } | Pat::Missing => false,
+        };
+        if is_non_ref_pat {
+            while let Some((inner, mutability)) = expected.as_reference() {
+                expected = inner;
+                default_bm = match default_bm {
+                    BindingMode::Move => BindingMode::Ref(mutability),
+                    BindingMode::Ref(Mutability::Shared) => BindingMode::Ref(Mutability::Shared),
+                    BindingMode::Ref(Mutability::Mut) => BindingMode::Ref(mutability),
+                }
+            }
+        } else if let Pat::Ref { .. } = &body[pat] {
+            tested_by!(match_ergonomics_ref);
+            // When you encounter a `&pat` pattern, reset to Move.
+            // This is so that `w` is by value: `let (_, &w) = &(1, &2);`
+            default_bm = BindingMode::Move;
+        }
+
+        // Lose mutability.
+        let default_bm = default_bm;
+        let expected = expected;
+
+        let ty = match &body[pat] {
+            Pat::Tuple(ref args) => {
+                let expectations = match expected.as_tuple() {
+                    Some(parameters) => &*parameters.0,
+                    _ => &[],
+                };
+                let expectations_iter = expectations.iter().chain(repeat(&Ty::Unknown));
+
+                let inner_tys = args
+                    .iter()
+                    .zip(expectations_iter)
+                    .map(|(&pat, ty)| self.infer_pat(pat, ty, default_bm))
+                    .collect();
+
+                Ty::apply(TypeCtor::Tuple { cardinality: args.len() as u16 }, Substs(inner_tys))
+            }
+            Pat::Ref { pat, mutability } => {
+                let expectation = match expected.as_reference() {
+                    Some((inner_ty, exp_mut)) => {
+                        if *mutability != exp_mut {
+                            // FIXME: emit type error?
+                        }
+                        inner_ty
+                    }
+                    _ => &Ty::Unknown,
+                };
+                let subty = self.infer_pat(*pat, expectation, default_bm);
+                Ty::apply_one(TypeCtor::Ref(*mutability), subty)
+            }
+            Pat::TupleStruct { path: p, args: subpats } => {
+                self.infer_tuple_struct_pat(p.as_ref(), subpats, expected, default_bm)
+            }
+            Pat::Record { path: p, args: fields } => {
+                self.infer_record_pat(p.as_ref(), fields, expected, default_bm, pat)
+            }
+            Pat::Path(path) => {
+                // FIXME use correct resolver for the surrounding expression
+                let resolver = self.resolver.clone();
+                self.infer_path(&resolver, &path, pat.into()).unwrap_or(Ty::Unknown)
+            }
+            Pat::Bind { mode, name: _, subpat } => {
+                let mode = if mode == &BindingAnnotation::Unannotated {
+                    default_bm
+                } else {
+                    BindingMode::convert(*mode)
+                };
+                let inner_ty = if let Some(subpat) = subpat {
+                    self.infer_pat(*subpat, expected, default_bm)
+                } else {
+                    expected.clone()
+                };
+                let inner_ty = self.insert_type_vars_shallow(inner_ty);
+
+                let bound_ty = match mode {
+                    BindingMode::Ref(mutability) => {
+                        Ty::apply_one(TypeCtor::Ref(mutability), inner_ty.clone())
+                    }
+                    BindingMode::Move => inner_ty.clone(),
+                };
+                let bound_ty = self.resolve_ty_as_possible(&mut vec![], bound_ty);
+                self.write_pat_ty(pat, bound_ty);
+                return inner_ty;
+            }
+            _ => Ty::Unknown,
+        };
+        // use a new type variable if we got Ty::Unknown here
+        let ty = self.insert_type_vars_shallow(ty);
+        self.unify(&ty, expected);
+        let ty = self.resolve_ty_as_possible(&mut vec![], ty);
+        self.write_pat_ty(pat, ty.clone());
+        ty
+    }
+}
diff --git a/crates/ra_hir_ty/src/infer/path.rs b/crates/ra_hir_ty/src/infer/path.rs
new file mode 100644
index 000000000..e6676e1aa
--- /dev/null
+++ b/crates/ra_hir_ty/src/infer/path.rs
@@ -0,0 +1,270 @@
+//! Path expression resolution.
+
+use hir_def::{
+    path::{Path, PathKind, PathSegment},
+    resolver::{HasResolver, ResolveValueResult, Resolver, TypeNs, ValueNs},
+    AssocItemId, ContainerId, Lookup,
+};
+use hir_expand::name::Name;
+
+use crate::{db::HirDatabase, method_resolution, Substs, Ty, TypeWalk, ValueTyDefId};
+
+use super::{ExprOrPatId, InferenceContext, TraitRef};
+
+impl<'a, D: HirDatabase> InferenceContext<'a, D> {
+    pub(super) fn infer_path(
+        &mut self,
+        resolver: &Resolver,
+        path: &Path,
+        id: ExprOrPatId,
+    ) -> Option<Ty> {
+        let ty = self.resolve_value_path(resolver, path, id)?;
+        let ty = self.insert_type_vars(ty);
+        let ty = self.normalize_associated_types_in(ty);
+        Some(ty)
+    }
+
+    fn resolve_value_path(
+        &mut self,
+        resolver: &Resolver,
+        path: &Path,
+        id: ExprOrPatId,
+    ) -> Option<Ty> {
+        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;
+            }
+            let ty = self.make_ty(type_ref);
+            let remaining_segments_for_ty = &path.segments[..path.segments.len() - 1];
+            let ty = Ty::from_type_relative_path(self.db, resolver, ty, remaining_segments_for_ty);
+            self.resolve_ty_assoc_item(
+                ty,
+                &path.segments.last().expect("path had at least one segment").name,
+                id,
+            )?
+        } else {
+            let value_or_partial = resolver.resolve_path_in_value_ns(self.db, &path)?;
+
+            match value_or_partial {
+                ResolveValueResult::ValueNs(it) => (it, None),
+                ResolveValueResult::Partial(def, remaining_index) => {
+                    self.resolve_assoc_item(def, path, remaining_index, id)?
+                }
+            }
+        };
+
+        let typable: ValueTyDefId = match value {
+            ValueNs::LocalBinding(pat) => {
+                let ty = self.result.type_of_pat.get(pat)?.clone();
+                let ty = self.resolve_ty_as_possible(&mut vec![], ty);
+                return Some(ty);
+            }
+            ValueNs::FunctionId(it) => it.into(),
+            ValueNs::ConstId(it) => it.into(),
+            ValueNs::StaticId(it) => it.into(),
+            ValueNs::StructId(it) => it.into(),
+            ValueNs::EnumVariantId(it) => it.into(),
+        };
+
+        let mut ty = self.db.value_ty(typable);
+        if let Some(self_subst) = self_subst {
+            ty = ty.subst(&self_subst);
+        }
+        let substs = Ty::substs_from_path(self.db, &self.resolver, path, typable);
+        let ty = ty.subst(&substs);
+        Some(ty)
+    }
+
+    fn resolve_assoc_item(
+        &mut self,
+        def: TypeNs,
+        path: &Path,
+        remaining_index: usize,
+        id: ExprOrPatId,
+    ) -> Option<(ValueNs, Option<Substs>)> {
+        assert!(remaining_index < path.segments.len());
+        // there may be more intermediate segments between the resolved one and
+        // the end. Only the last segment needs to be resolved to a value; from
+        // the segments before that, we need to get either a type or a trait ref.
+
+        let resolved_segment = &path.segments[remaining_index - 1];
+        let remaining_segments = &path.segments[remaining_index..];
+        let is_before_last = remaining_segments.len() == 1;
+
+        match (def, is_before_last) {
+            (TypeNs::TraitId(trait_), true) => {
+                let segment =
+                    remaining_segments.last().expect("there should be at least one segment here");
+                let trait_ref = TraitRef::from_resolved_path(
+                    self.db,
+                    &self.resolver,
+                    trait_.into(),
+                    resolved_segment,
+                    None,
+                );
+                self.resolve_trait_assoc_item(trait_ref, segment, id)
+            }
+            (def, _) => {
+                // Either we already have a type (e.g. `Vec::new`), or we have a
+                // trait but it's not the last segment, so the next segment
+                // should resolve to an associated type of that trait (e.g. `<T
+                // as Iterator>::Item::default`)
+                let remaining_segments_for_ty = &remaining_segments[..remaining_segments.len() - 1];
+                let ty = Ty::from_partly_resolved_hir_path(
+                    self.db,
+                    &self.resolver,
+                    def,
+                    resolved_segment,
+                    remaining_segments_for_ty,
+                );
+                if let Ty::Unknown = ty {
+                    return None;
+                }
+
+                let ty = self.insert_type_vars(ty);
+                let ty = self.normalize_associated_types_in(ty);
+
+                let segment =
+                    remaining_segments.last().expect("there should be at least one segment here");
+
+                self.resolve_ty_assoc_item(ty, &segment.name, id)
+            }
+        }
+    }
+
+    fn resolve_trait_assoc_item(
+        &mut self,
+        trait_ref: TraitRef,
+        segment: &PathSegment,
+        id: ExprOrPatId,
+    ) -> Option<(ValueNs, Option<Substs>)> {
+        let trait_ = trait_ref.trait_;
+        let item = self
+            .db
+            .trait_data(trait_)
+            .items
+            .iter()
+            .map(|(_name, id)| (*id).into())
+            .find_map(|item| match item {
+                AssocItemId::FunctionId(func) => {
+                    if segment.name == self.db.function_data(func).name {
+                        Some(AssocItemId::FunctionId(func))
+                    } else {
+                        None
+                    }
+                }
+
+                AssocItemId::ConstId(konst) => {
+                    if self.db.const_data(konst).name.as_ref().map_or(false, |n| n == &segment.name)
+                    {
+                        Some(AssocItemId::ConstId(konst))
+                    } else {
+                        None
+                    }
+                }
+                AssocItemId::TypeAliasId(_) => None,
+            })?;
+        let def = match item {
+            AssocItemId::FunctionId(f) => ValueNs::FunctionId(f),
+            AssocItemId::ConstId(c) => ValueNs::ConstId(c),
+            AssocItemId::TypeAliasId(_) => unreachable!(),
+        };
+        let substs = Substs::build_for_def(self.db, item)
+            .use_parent_substs(&trait_ref.substs)
+            .fill_with_params()
+            .build();
+
+        self.write_assoc_resolution(id, item);
+        Some((def, Some(substs)))
+    }
+
+    fn resolve_ty_assoc_item(
+        &mut self,
+        ty: Ty,
+        name: &Name,
+        id: ExprOrPatId,
+    ) -> Option<(ValueNs, Option<Substs>)> {
+        if let Ty::Unknown = ty {
+            return None;
+        }
+
+        let canonical_ty = self.canonicalizer().canonicalize_ty(ty.clone());
+
+        method_resolution::iterate_method_candidates(
+            &canonical_ty.value,
+            self.db,
+            &self.resolver.clone(),
+            Some(name),
+            method_resolution::LookupMode::Path,
+            move |_ty, item| {
+                let (def, container) = match item {
+                    AssocItemId::FunctionId(f) => {
+                        (ValueNs::FunctionId(f), f.lookup(self.db).container)
+                    }
+                    AssocItemId::ConstId(c) => (ValueNs::ConstId(c), c.lookup(self.db).container),
+                    AssocItemId::TypeAliasId(_) => unreachable!(),
+                };
+                let substs = match container {
+                    ContainerId::ImplId(_) => self.find_self_types(&def, ty.clone()),
+                    ContainerId::TraitId(trait_) => {
+                        // we're picking this method
+                        let trait_substs = Substs::build_for_def(self.db, trait_)
+                            .push(ty.clone())
+                            .fill(std::iter::repeat_with(|| self.new_type_var()))
+                            .build();
+                        let substs = Substs::build_for_def(self.db, item)
+                            .use_parent_substs(&trait_substs)
+                            .fill_with_params()
+                            .build();
+                        self.obligations.push(super::Obligation::Trait(TraitRef {
+                            trait_,
+                            substs: trait_substs,
+                        }));
+                        Some(substs)
+                    }
+                    ContainerId::ModuleId(_) => None,
+                };
+
+                self.write_assoc_resolution(id, item.into());
+                Some((def, substs))
+            },
+        )
+    }
+
+    fn find_self_types(&self, def: &ValueNs, actual_def_ty: Ty) -> Option<Substs> {
+        if let ValueNs::FunctionId(func) = *def {
+            // We only do the infer if parent has generic params
+            let gen = self.db.generic_params(func.into());
+            if gen.count_parent_params() == 0 {
+                return None;
+            }
+
+            let impl_id = match func.lookup(self.db).container {
+                ContainerId::ImplId(it) => it,
+                _ => return None,
+            };
+            let resolver = impl_id.resolver(self.db);
+            let impl_data = self.db.impl_data(impl_id);
+            let impl_block = Ty::from_hir(self.db, &resolver, &impl_data.target_type);
+            let impl_block_substs = impl_block.substs()?;
+            let actual_substs = actual_def_ty.substs()?;
+
+            let mut new_substs = vec![Ty::Unknown; gen.count_parent_params()];
+
+            // The following code *link up* the function actual parma type
+            // and impl_block type param index
+            impl_block_substs.iter().zip(actual_substs.iter()).for_each(|(param, pty)| {
+                if let Ty::Param { idx, .. } = param {
+                    if let Some(s) = new_substs.get_mut(*idx as usize) {
+                        *s = pty.clone();
+                    }
+                }
+            });
+
+            Some(Substs(new_substs.into()))
+        } else {
+            None
+        }
+    }
+}
diff --git a/crates/ra_hir_ty/src/infer/unify.rs b/crates/ra_hir_ty/src/infer/unify.rs
new file mode 100644
index 000000000..f3a875678
--- /dev/null
+++ b/crates/ra_hir_ty/src/infer/unify.rs
@@ -0,0 +1,162 @@
+//! Unification and canonicalization logic.
+
+use super::{InferenceContext, Obligation};
+use crate::{
+    db::HirDatabase, utils::make_mut_slice, Canonical, InEnvironment, InferTy, ProjectionPredicate,
+    ProjectionTy, Substs, TraitRef, Ty, TypeWalk,
+};
+
+impl<'a, D: HirDatabase> InferenceContext<'a, D> {
+    pub(super) fn canonicalizer<'b>(&'b mut self) -> Canonicalizer<'a, 'b, D>
+    where
+        'a: 'b,
+    {
+        Canonicalizer { ctx: self, free_vars: Vec::new(), var_stack: Vec::new() }
+    }
+}
+
+pub(super) struct Canonicalizer<'a, 'b, D: HirDatabase>
+where
+    'a: 'b,
+{
+    ctx: &'b mut InferenceContext<'a, D>,
+    free_vars: Vec<InferTy>,
+    /// A stack of type variables that is used to detect recursive types (which
+    /// are an error, but we need to protect against them to avoid stack
+    /// overflows).
+    var_stack: Vec<super::TypeVarId>,
+}
+
+pub(super) struct Canonicalized<T> {
+    pub value: Canonical<T>,
+    free_vars: Vec<InferTy>,
+}
+
+impl<'a, 'b, D: HirDatabase> Canonicalizer<'a, 'b, D>
+where
+    'a: 'b,
+{
+    fn add(&mut self, free_var: InferTy) -> usize {
+        self.free_vars.iter().position(|&v| v == free_var).unwrap_or_else(|| {
+            let next_index = self.free_vars.len();
+            self.free_vars.push(free_var);
+            next_index
+        })
+    }
+
+    fn do_canonicalize_ty(&mut self, ty: Ty) -> Ty {
+        ty.fold(&mut |ty| match ty {
+            Ty::Infer(tv) => {
+                let inner = tv.to_inner();
+                if self.var_stack.contains(&inner) {
+                    // recursive type
+                    return tv.fallback_value();
+                }
+                if let Some(known_ty) =
+                    self.ctx.var_unification_table.inlined_probe_value(inner).known()
+                {
+                    self.var_stack.push(inner);
+                    let result = self.do_canonicalize_ty(known_ty.clone());
+                    self.var_stack.pop();
+                    result
+                } else {
+                    let root = self.ctx.var_unification_table.find(inner);
+                    let free_var = match tv {
+                        InferTy::TypeVar(_) => InferTy::TypeVar(root),
+                        InferTy::IntVar(_) => InferTy::IntVar(root),
+                        InferTy::FloatVar(_) => InferTy::FloatVar(root),
+                        InferTy::MaybeNeverTypeVar(_) => InferTy::MaybeNeverTypeVar(root),
+                    };
+                    let position = self.add(free_var);
+                    Ty::Bound(position as u32)
+                }
+            }
+            _ => ty,
+        })
+    }
+
+    fn do_canonicalize_trait_ref(&mut self, mut trait_ref: TraitRef) -> TraitRef {
+        for ty in make_mut_slice(&mut trait_ref.substs.0) {
+            *ty = self.do_canonicalize_ty(ty.clone());
+        }
+        trait_ref
+    }
+
+    fn into_canonicalized<T>(self, result: T) -> Canonicalized<T> {
+        Canonicalized {
+            value: Canonical { value: result, num_vars: self.free_vars.len() },
+            free_vars: self.free_vars,
+        }
+    }
+
+    fn do_canonicalize_projection_ty(&mut self, mut projection_ty: ProjectionTy) -> ProjectionTy {
+        for ty in make_mut_slice(&mut projection_ty.parameters.0) {
+            *ty = self.do_canonicalize_ty(ty.clone());
+        }
+        projection_ty
+    }
+
+    fn do_canonicalize_projection_predicate(
+        &mut self,
+        projection: ProjectionPredicate,
+    ) -> ProjectionPredicate {
+        let ty = self.do_canonicalize_ty(projection.ty);
+        let projection_ty = self.do_canonicalize_projection_ty(projection.projection_ty);
+
+        ProjectionPredicate { ty, projection_ty }
+    }
+
+    // FIXME: add some point, we need to introduce a `Fold` trait that abstracts
+    // over all the things that can be canonicalized (like Chalk and rustc have)
+
+    pub(crate) fn canonicalize_ty(mut self, ty: Ty) -> Canonicalized<Ty> {
+        let result = self.do_canonicalize_ty(ty);
+        self.into_canonicalized(result)
+    }
+
+    pub(crate) fn canonicalize_obligation(
+        mut self,
+        obligation: InEnvironment<Obligation>,
+    ) -> Canonicalized<InEnvironment<Obligation>> {
+        let result = match obligation.value {
+            Obligation::Trait(tr) => Obligation::Trait(self.do_canonicalize_trait_ref(tr)),
+            Obligation::Projection(pr) => {
+                Obligation::Projection(self.do_canonicalize_projection_predicate(pr))
+            }
+        };
+        self.into_canonicalized(InEnvironment {
+            value: result,
+            environment: obligation.environment,
+        })
+    }
+}
+
+impl<T> Canonicalized<T> {
+    pub fn decanonicalize_ty(&self, mut ty: Ty) -> Ty {
+        ty.walk_mut_binders(
+            &mut |ty, binders| match ty {
+                &mut Ty::Bound(idx) => {
+                    if idx as usize >= binders && (idx as usize - binders) < self.free_vars.len() {
+                        *ty = Ty::Infer(self.free_vars[idx as usize - binders]);
+                    }
+                }
+                _ => {}
+            },
+            0,
+        );
+        ty
+    }
+
+    pub fn apply_solution(
+        &self,
+        ctx: &mut InferenceContext<'_, impl HirDatabase>,
+        solution: Canonical<Vec<Ty>>,
+    ) {
+        // the solution may contain new variables, which we need to convert to new inference vars
+        let new_vars = Substs((0..solution.num_vars).map(|_| ctx.new_type_var()).collect());
+        for (i, ty) in solution.value.into_iter().enumerate() {
+            let var = self.free_vars[i];
+            ctx.unify(&Ty::Infer(var), &ty.subst_bound_vars(&new_vars));
+        }
+    }
+}
diff --git a/crates/ra_hir_ty/src/lib.rs b/crates/ra_hir_ty/src/lib.rs
index 28859ba63..f25846326 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_ty/src/lower.rs b/crates/ra_hir_ty/src/lower.rs
new file mode 100644
index 000000000..53d955a12
--- /dev/null
+++ b/crates/ra_hir_ty/src/lower.rs
@@ -0,0 +1,753 @@
+//! Methods for lowering the HIR to types. There are two main cases here:
+//!
+//!  - Lowering a type reference like `&usize` or `Option<foo::bar::Baz>` to a
+//!    type: The entry point for this is `Ty::from_hir`.
+//!  - Building the type for an item: This happens through the `type_for_def` query.
+//!
+//! This usually involves resolving names, collecting generic arguments etc.
+use std::iter;
+use std::sync::Arc;
+
+use hir_def::{
+    builtin_type::BuiltinType,
+    generics::WherePredicate,
+    path::{GenericArg, Path, PathKind, PathSegment},
+    resolver::{HasResolver, Resolver, TypeNs},
+    type_ref::{TypeBound, TypeRef},
+    AdtId, AstItemDef, ConstId, EnumId, EnumVariantId, FunctionId, GenericDefId, HasModule,
+    LocalStructFieldId, Lookup, StaticId, StructId, TraitId, TypeAliasId, UnionId, VariantId,
+};
+use ra_arena::map::ArenaMap;
+use ra_db::CrateId;
+
+use super::{
+    FnSig, GenericPredicate, ProjectionPredicate, ProjectionTy, Substs, TraitEnvironment, TraitRef,
+    Ty, TypeCtor, TypeWalk,
+};
+use crate::{
+    db::HirDatabase,
+    primitive::{FloatTy, IntTy},
+    utils::make_mut_slice,
+    utils::{all_super_traits, associated_type_by_name_including_super_traits, variant_data},
+};
+
+impl Ty {
+    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) => {
+                let inner_tys: Arc<[Ty]> =
+                    inner.iter().map(|tr| Ty::from_hir(db, resolver, tr)).collect();
+                Ty::apply(
+                    TypeCtor::Tuple { cardinality: inner_tys.len() as u16 },
+                    Substs(inner_tys),
+                )
+            }
+            TypeRef::Path(path) => Ty::from_hir_path(db, resolver, path),
+            TypeRef::RawPtr(inner, mutability) => {
+                let inner_ty = Ty::from_hir(db, resolver, inner);
+                Ty::apply_one(TypeCtor::RawPtr(*mutability), inner_ty)
+            }
+            TypeRef::Array(inner) => {
+                let inner_ty = Ty::from_hir(db, resolver, inner);
+                Ty::apply_one(TypeCtor::Array, inner_ty)
+            }
+            TypeRef::Slice(inner) => {
+                let inner_ty = Ty::from_hir(db, resolver, inner);
+                Ty::apply_one(TypeCtor::Slice, inner_ty)
+            }
+            TypeRef::Reference(inner, mutability) => {
+                let inner_ty = Ty::from_hir(db, resolver, inner);
+                Ty::apply_one(TypeCtor::Ref(*mutability), inner_ty)
+            }
+            TypeRef::Placeholder => Ty::Unknown,
+            TypeRef::Fn(params) => {
+                let sig = Substs(params.iter().map(|tr| Ty::from_hir(db, resolver, tr)).collect());
+                Ty::apply(TypeCtor::FnPtr { num_args: sig.len() as u16 - 1 }, sig)
+            }
+            TypeRef::DynTrait(bounds) => {
+                let self_ty = Ty::Bound(0);
+                let predicates = bounds
+                    .iter()
+                    .flat_map(|b| {
+                        GenericPredicate::from_type_bound(db, resolver, b, self_ty.clone())
+                    })
+                    .collect();
+                Ty::Dyn(predicates)
+            }
+            TypeRef::ImplTrait(bounds) => {
+                let self_ty = Ty::Bound(0);
+                let predicates = bounds
+                    .iter()
+                    .flat_map(|b| {
+                        GenericPredicate::from_type_bound(db, resolver, b, self_ty.clone())
+                    })
+                    .collect();
+                Ty::Opaque(predicates)
+            }
+            TypeRef::Error => Ty::Unknown,
+        }
+    }
+
+    /// This is only for `generic_predicates_for_param`, where we can't just
+    /// lower the self types of the predicates since that could lead to cycles.
+    /// So we just check here if the `type_ref` resolves to a generic param, and which.
+    fn from_hir_only_param(
+        db: &impl HirDatabase,
+        resolver: &Resolver,
+        type_ref: &TypeRef,
+    ) -> Option<u32> {
+        let path = match type_ref {
+            TypeRef::Path(path) => path,
+            _ => return None,
+        };
+        if let PathKind::Type(_) = &path.kind {
+            return None;
+        }
+        if path.segments.len() > 1 {
+            return None;
+        }
+        let resolution = match resolver.resolve_path_in_type_ns(db, path) {
+            Some((it, None)) => it,
+            _ => return None,
+        };
+        if let TypeNs::GenericParam(idx) = resolution {
+            Some(idx)
+        } else {
+            None
+        }
+    }
+
+    pub(crate) fn from_type_relative_path(
+        db: &impl HirDatabase,
+        resolver: &Resolver,
+        ty: Ty,
+        remaining_segments: &[PathSegment],
+    ) -> Ty {
+        if remaining_segments.len() == 1 {
+            // resolve unselected assoc types
+            let segment = &remaining_segments[0];
+            Ty::select_associated_type(db, resolver, ty, segment)
+        } else if remaining_segments.len() > 1 {
+            // FIXME report error (ambiguous associated type)
+            Ty::Unknown
+        } else {
+            ty
+        }
+    }
+
+    pub(crate) fn from_partly_resolved_hir_path(
+        db: &impl HirDatabase,
+        resolver: &Resolver,
+        resolution: TypeNs,
+        resolved_segment: &PathSegment,
+        remaining_segments: &[PathSegment],
+    ) -> Ty {
+        let ty = match resolution {
+            TypeNs::TraitId(trait_) => {
+                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(
+                        db,
+                        trait_ref.trait_,
+                        &segment.name,
+                    );
+                    match associated_ty {
+                        Some(associated_ty) => {
+                            // FIXME handle type parameters on the segment
+                            Ty::Projection(ProjectionTy {
+                                associated_ty,
+                                parameters: trait_ref.substs,
+                            })
+                        }
+                        None => {
+                            // FIXME: report error (associated type not found)
+                            Ty::Unknown
+                        }
+                    }
+                } else if remaining_segments.len() > 1 {
+                    // FIXME report error (ambiguous associated type)
+                    Ty::Unknown
+                } else {
+                    Ty::Dyn(Arc::new([GenericPredicate::Implemented(trait_ref)]))
+                };
+            }
+            TypeNs::GenericParam(idx) => {
+                // FIXME: maybe return name in resolution?
+                let name = resolved_segment.name.clone();
+                Ty::Param { idx, name }
+            }
+            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()),
+            TypeNs::BuiltinType(it) => {
+                Ty::from_hir_path_inner(db, resolver, resolved_segment, it.into())
+            }
+            TypeNs::TypeAliasId(it) => {
+                Ty::from_hir_path_inner(db, resolver, resolved_segment, it.into())
+            }
+            // FIXME: report error
+            TypeNs::EnumVariantId(_) => return Ty::Unknown,
+        };
+
+        Ty::from_type_relative_path(db, resolver, ty, remaining_segments)
+    }
+
+    pub(crate) fn from_hir_path(db: &impl HirDatabase, resolver: &Resolver, path: &Path) -> Ty {
+        // Resolve the path (in type namespace)
+        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);
+        }
+        let (resolution, remaining_index) = match resolver.resolve_path_in_type_ns(db, path) {
+            Some(it) => it,
+            None => return Ty::Unknown,
+        };
+        let (resolved_segment, remaining_segments) = match remaining_index {
+            None => (
+                path.segments.last().expect("resolved path has at least one element"),
+                &[] as &[PathSegment],
+            ),
+            Some(i) => (&path.segments[i - 1], &path.segments[i..]),
+        };
+        Ty::from_partly_resolved_hir_path(
+            db,
+            resolver,
+            resolution,
+            resolved_segment,
+            remaining_segments,
+        )
+    }
+
+    fn select_associated_type(
+        db: &impl HirDatabase,
+        resolver: &Resolver,
+        self_ty: Ty,
+        segment: &PathSegment,
+    ) -> Ty {
+        let param_idx = match self_ty {
+            Ty::Param { idx, .. } => idx,
+            _ => return Ty::Unknown, // Error: Ambiguous associated type
+        };
+        let def = match resolver.generic_def() {
+            Some(def) => def,
+            None => return Ty::Unknown, // this can't actually happen
+        };
+        let predicates = db.generic_predicates_for_param(def.into(), param_idx);
+        let traits_from_env = predicates.iter().filter_map(|pred| match pred {
+            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));
+        for t in traits {
+            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 });
+            }
+        }
+        Ty::Unknown
+    }
+
+    fn from_hir_path_inner(
+        db: &impl HirDatabase,
+        resolver: &Resolver,
+        segment: &PathSegment,
+        typable: TyDefId,
+    ) -> Ty {
+        let generic_def = match typable {
+            TyDefId::BuiltinType(_) => None,
+            TyDefId::AdtId(it) => Some(it.into()),
+            TyDefId::TypeAliasId(it) => Some(it.into()),
+        };
+        let substs = substs_from_path_segment(db, resolver, segment, generic_def, false);
+        db.ty(typable).subst(&substs)
+    }
+
+    /// Collect generic arguments from a path into a `Substs`. See also
+    /// `create_substs_for_ast_path` and `def_to_ty` in rustc.
+    pub(super) fn substs_from_path(
+        db: &impl HirDatabase,
+        resolver: &Resolver,
+        path: &Path,
+        // Note that we don't call `db.value_type(resolved)` here,
+        // `ValueTyDefId` is just a convenient way to pass generics and
+        // special-case enum variants
+        resolved: ValueTyDefId,
+    ) -> Substs {
+        let last = path.segments.last().expect("path should have at least one segment");
+        let (segment, generic_def) = match resolved {
+            ValueTyDefId::FunctionId(it) => (last, Some(it.into())),
+            ValueTyDefId::StructId(it) => (last, Some(it.into())),
+            ValueTyDefId::ConstId(it) => (last, Some(it.into())),
+            ValueTyDefId::StaticId(_) => (last, None),
+            ValueTyDefId::EnumVariantId(var) => {
+                // the generic args for an enum variant may be either specified
+                // on the segment referring to the enum, or on the segment
+                // referring to the variant. So `Option::<T>::None` and
+                // `Option::None::<T>` are both allowed (though the former is
+                // preferred). See also `def_ids_for_path_segments` in rustc.
+                let len = path.segments.len();
+                let segment = if len >= 2 && path.segments[len - 2].args_and_bindings.is_some() {
+                    // Option::<T>::None
+                    &path.segments[len - 2]
+                } else {
+                    // Option::None::<T>
+                    last
+                };
+                (segment, Some(var.parent.into()))
+            }
+        };
+        substs_from_path_segment(db, resolver, segment, generic_def, false)
+    }
+}
+
+pub(super) fn substs_from_path_segment(
+    db: &impl HirDatabase,
+    resolver: &Resolver,
+    segment: &PathSegment,
+    def_generic: Option<GenericDefId>,
+    add_self_param: bool,
+) -> Substs {
+    let mut substs = Vec::new();
+    let def_generics = def_generic.map(|def| db.generic_params(def.into()));
+
+    let (parent_param_count, param_count) =
+        def_generics.map_or((0, 0), |g| (g.count_parent_params(), g.params.len()));
+    substs.extend(iter::repeat(Ty::Unknown).take(parent_param_count));
+    if add_self_param {
+        // FIXME this add_self_param argument is kind of a hack: Traits have the
+        // Self type as an implicit first type parameter, but it can't be
+        // actually provided in the type arguments
+        // (well, actually sometimes it can, in the form of type-relative paths: `<Foo as Default>::default()`)
+        substs.push(Ty::Unknown);
+    }
+    if let Some(generic_args) = &segment.args_and_bindings {
+        // if args are provided, it should be all of them, but we can't rely on that
+        let self_param_correction = if add_self_param { 1 } else { 0 };
+        let param_count = param_count - self_param_correction;
+        for arg in generic_args.args.iter().take(param_count) {
+            match arg {
+                GenericArg::Type(type_ref) => {
+                    let ty = Ty::from_hir(db, resolver, type_ref);
+                    substs.push(ty);
+                }
+            }
+        }
+    }
+    // add placeholders for args that were not provided
+    let supplied_params = substs.len();
+    for _ in supplied_params..parent_param_count + param_count {
+        substs.push(Ty::Unknown);
+    }
+    assert_eq!(substs.len(), parent_param_count + param_count);
+
+    // handle defaults
+    if let Some(def_generic) = def_generic {
+        let default_substs = db.generic_defaults(def_generic.into());
+        assert_eq!(substs.len(), default_substs.len());
+
+        for (i, default_ty) in default_substs.iter().enumerate() {
+            if substs[i] == Ty::Unknown {
+                substs[i] = default_ty.clone();
+            }
+        }
+    }
+
+    Substs(substs.into())
+}
+
+impl TraitRef {
+    pub(crate) fn from_path(
+        db: &impl HirDatabase,
+        resolver: &Resolver,
+        path: &Path,
+        explicit_self_ty: Option<Ty>,
+    ) -> Option<Self> {
+        let resolved = match resolver.resolve_path_in_type_ns_fully(db, &path)? {
+            TypeNs::TraitId(tr) => tr,
+            _ => return None,
+        };
+        let segment = path.segments.last().expect("path should have at least one segment");
+        Some(TraitRef::from_resolved_path(db, resolver, resolved.into(), segment, explicit_self_ty))
+    }
+
+    pub(super) fn from_resolved_path(
+        db: &impl HirDatabase,
+        resolver: &Resolver,
+        resolved: TraitId,
+        segment: &PathSegment,
+        explicit_self_ty: Option<Ty>,
+    ) -> Self {
+        let mut substs = TraitRef::substs_from_path(db, resolver, segment, resolved);
+        if let Some(self_ty) = explicit_self_ty {
+            make_mut_slice(&mut substs.0)[0] = self_ty;
+        }
+        TraitRef { trait_: resolved, substs }
+    }
+
+    pub(crate) fn from_hir(
+        db: &impl HirDatabase,
+        resolver: &Resolver,
+        type_ref: &TypeRef,
+        explicit_self_ty: Option<Ty>,
+    ) -> Option<Self> {
+        let path = match type_ref {
+            TypeRef::Path(path) => path,
+            _ => return None,
+        };
+        TraitRef::from_path(db, resolver, path, explicit_self_ty)
+    }
+
+    fn substs_from_path(
+        db: &impl HirDatabase,
+        resolver: &Resolver,
+        segment: &PathSegment,
+        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.into()), !has_self_param)
+    }
+
+    pub fn for_trait(db: &impl HirDatabase, trait_: TraitId) -> TraitRef {
+        let substs = Substs::identity(&db.generic_params(trait_.into()));
+        TraitRef { trait_, substs }
+    }
+
+    pub(crate) fn from_type_bound(
+        db: &impl HirDatabase,
+        resolver: &Resolver,
+        bound: &TypeBound,
+        self_ty: Ty,
+    ) -> Option<TraitRef> {
+        match bound {
+            TypeBound::Path(path) => TraitRef::from_path(db, resolver, path, Some(self_ty)),
+            TypeBound::Error => None,
+        }
+    }
+}
+
+impl GenericPredicate {
+    pub(crate) fn from_where_predicate<'a>(
+        db: &'a impl HirDatabase,
+        resolver: &'a Resolver,
+        where_predicate: &'a WherePredicate,
+    ) -> impl Iterator<Item = GenericPredicate> + 'a {
+        let self_ty = Ty::from_hir(db, resolver, &where_predicate.type_ref);
+        GenericPredicate::from_type_bound(db, resolver, &where_predicate.bound, self_ty)
+    }
+
+    pub(crate) fn from_type_bound<'a>(
+        db: &'a impl HirDatabase,
+        resolver: &'a Resolver,
+        bound: &'a TypeBound,
+        self_ty: Ty,
+    ) -> impl Iterator<Item = GenericPredicate> + 'a {
+        let trait_ref = TraitRef::from_type_bound(db, &resolver, bound, self_ty);
+        iter::once(trait_ref.clone().map_or(GenericPredicate::Error, GenericPredicate::Implemented))
+            .chain(
+                trait_ref.into_iter().flat_map(move |tr| {
+                    assoc_type_bindings_from_type_bound(db, resolver, bound, tr)
+                }),
+            )
+    }
+}
+
+fn assoc_type_bindings_from_type_bound<'a>(
+    db: &'a impl HirDatabase,
+    resolver: &'a Resolver,
+    bound: &'a TypeBound,
+    trait_ref: TraitRef,
+) -> impl Iterator<Item = GenericPredicate> + 'a {
+    let last_segment = match bound {
+        TypeBound::Path(path) => path.segments.last(),
+        TypeBound::Error => None,
+    };
+    last_segment
+        .into_iter()
+        .flat_map(|segment| segment.args_and_bindings.iter())
+        .flat_map(|args_and_bindings| args_and_bindings.bindings.iter())
+        .map(move |(name, type_ref)| {
+            let associated_ty =
+                associated_type_by_name_including_super_traits(db, trait_ref.trait_, &name);
+            let associated_ty = match associated_ty {
+                None => return GenericPredicate::Error,
+                Some(t) => t,
+            };
+            let projection_ty =
+                ProjectionTy { associated_ty, parameters: trait_ref.substs.clone() };
+            let ty = Ty::from_hir(db, resolver, type_ref);
+            let projection_predicate = ProjectionPredicate { projection_ty, ty };
+            GenericPredicate::Projection(projection_predicate)
+        })
+}
+
+/// Build the signature of a callable item (function, struct or enum variant).
+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),
+        CallableDef::EnumVariantId(e) => fn_sig_for_enum_variant_constructor(db, e),
+    }
+}
+
+/// Build the type of all specific fields of a struct or enum variant.
+pub(crate) fn field_types_query(
+    db: &impl HirDatabase,
+    variant_id: VariantId,
+) -> Arc<ArenaMap<LocalStructFieldId, Ty>> {
+    let var_data = variant_data(db, variant_id);
+    let resolver = match variant_id {
+        VariantId::StructId(it) => it.resolver(db),
+        VariantId::UnionId(it) => it.resolver(db),
+        VariantId::EnumVariantId(it) => it.parent.resolver(db),
+    };
+    let mut res = ArenaMap::default();
+    for (field_id, field_data) in var_data.fields().iter() {
+        res.insert(field_id, Ty::from_hir(db, &resolver, &field_data.type_ref))
+    }
+    Arc::new(res)
+}
+
+/// This query exists only to be used when resolving short-hand associated types
+/// like `T::Item`.
+///
+/// See the analogous query in rustc and its comment:
+/// https://github.com/rust-lang/rust/blob/9150f844e2624eb013ec78ca08c1d416e6644026/src/librustc_typeck/astconv.rs#L46
+/// This is a query mostly to handle cycles somewhat gracefully; e.g. the
+/// following bounds are disallowed: `T: Foo<U::Item>, U: Foo<T::Item>`, but
+/// these are fine: `T: Foo<U::Item>, U: Foo<()>`.
+pub(crate) fn generic_predicates_for_param_query(
+    db: &impl HirDatabase,
+    def: GenericDefId,
+    param_idx: u32,
+) -> Arc<[GenericPredicate]> {
+    let resolver = def.resolver(db);
+    resolver
+        .where_predicates_in_scope()
+        // we have to filter out all other predicates *first*, before attempting to lower them
+        .filter(|pred| Ty::from_hir_only_param(db, &resolver, &pred.type_ref) == Some(param_idx))
+        .flat_map(|pred| GenericPredicate::from_where_predicate(db, &resolver, pred))
+        .collect()
+}
+
+impl 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))
+            .collect::<Vec<_>>();
+
+        Arc::new(TraitEnvironment { predicates })
+    }
+}
+
+/// Resolve the where clause(s) of an item with generics.
+pub(crate) fn generic_predicates_query(
+    db: &impl HirDatabase,
+    def: GenericDefId,
+) -> Arc<[GenericPredicate]> {
+    let resolver = def.resolver(db);
+    resolver
+        .where_predicates_in_scope()
+        .flat_map(|pred| GenericPredicate::from_where_predicate(db, &resolver, pred))
+        .collect()
+}
+
+/// Resolve the default type params from generics
+pub(crate) fn generic_defaults_query(db: &impl HirDatabase, def: GenericDefId) -> Substs {
+    let resolver = def.resolver(db);
+    let generic_params = db.generic_params(def.into());
+
+    let defaults = generic_params
+        .params_including_parent()
+        .into_iter()
+        .map(|p| p.default.as_ref().map_or(Ty::Unknown, |t| Ty::from_hir(db, &resolver, t)))
+        .collect();
+
+    Substs(defaults)
+}
+
+fn fn_sig_for_fn(db: &impl HirDatabase, def: FunctionId) -> FnSig {
+    let data = db.function_data(def);
+    let resolver = def.resolver(db);
+    let params = data.params.iter().map(|tr| Ty::from_hir(db, &resolver, tr)).collect::<Vec<_>>();
+    let ret = Ty::from_hir(db, &resolver, &data.ret_type);
+    FnSig::from_params_and_return(params, ret)
+}
+
+/// Build the declared type of a function. This should not need to look at the
+/// function body.
+fn type_for_fn(db: &impl HirDatabase, def: FunctionId) -> Ty {
+    let generics = db.generic_params(def.into());
+    let substs = Substs::identity(&generics);
+    Ty::apply(TypeCtor::FnDef(def.into()), substs)
+}
+
+/// Build the declared type of a const.
+fn type_for_const(db: &impl HirDatabase, def: ConstId) -> Ty {
+    let data = db.const_data(def);
+    let resolver = def.resolver(db);
+
+    Ty::from_hir(db, &resolver, &data.type_ref)
+}
+
+/// Build the declared type of a static.
+fn type_for_static(db: &impl HirDatabase, def: StaticId) -> Ty {
+    let data = db.static_data(def);
+    let resolver = def.resolver(db);
+
+    Ty::from_hir(db, &resolver, &data.type_ref)
+}
+
+/// Build the declared type of a static.
+fn type_for_builtin(def: BuiltinType) -> Ty {
+    Ty::simple(match def {
+        BuiltinType::Char => TypeCtor::Char,
+        BuiltinType::Bool => TypeCtor::Bool,
+        BuiltinType::Str => TypeCtor::Str,
+        BuiltinType::Int(t) => TypeCtor::Int(IntTy::from(t).into()),
+        BuiltinType::Float(t) => TypeCtor::Float(FloatTy::from(t).into()),
+    })
+}
+
+fn fn_sig_for_struct_constructor(db: &impl HirDatabase, def: StructId) -> FnSig {
+    let struct_data = db.struct_data(def.into());
+    let fields = struct_data.variant_data.fields();
+    let resolver = def.resolver(db);
+    let params = fields
+        .iter()
+        .map(|(_, field)| Ty::from_hir(db, &resolver, &field.type_ref))
+        .collect::<Vec<_>>();
+    let ret = type_for_adt(db, def.into());
+    FnSig::from_params_and_return(params, ret)
+}
+
+/// Build the type of a tuple struct constructor.
+fn type_for_struct_constructor(db: &impl HirDatabase, def: StructId) -> Ty {
+    let struct_data = db.struct_data(def.into());
+    if struct_data.variant_data.is_unit() {
+        return type_for_adt(db, def.into()); // Unit struct
+    }
+    let generics = db.generic_params(def.into());
+    let substs = Substs::identity(&generics);
+    Ty::apply(TypeCtor::FnDef(def.into()), substs)
+}
+
+fn fn_sig_for_enum_variant_constructor(db: &impl HirDatabase, def: EnumVariantId) -> FnSig {
+    let enum_data = db.enum_data(def.parent);
+    let var_data = &enum_data.variants[def.local_id];
+    let fields = var_data.variant_data.fields();
+    let resolver = def.parent.resolver(db);
+    let params = fields
+        .iter()
+        .map(|(_, field)| Ty::from_hir(db, &resolver, &field.type_ref))
+        .collect::<Vec<_>>();
+    let generics = db.generic_params(def.parent.into());
+    let substs = Substs::identity(&generics);
+    let ret = type_for_adt(db, def.parent.into()).subst(&substs);
+    FnSig::from_params_and_return(params, ret)
+}
+
+/// Build the type of a tuple enum variant constructor.
+fn type_for_enum_variant_constructor(db: &impl HirDatabase, def: EnumVariantId) -> Ty {
+    let enum_data = db.enum_data(def.parent);
+    let var_data = &enum_data.variants[def.local_id].variant_data;
+    if var_data.is_unit() {
+        return type_for_adt(db, def.parent.into()); // Unit variant
+    }
+    let generics = db.generic_params(def.parent.into());
+    let substs = Substs::identity(&generics);
+    Ty::apply(TypeCtor::FnDef(EnumVariantId::from(def).into()), substs)
+}
+
+fn type_for_adt(db: &impl HirDatabase, adt: AdtId) -> Ty {
+    let generics = db.generic_params(adt.into());
+    Ty::apply(TypeCtor::Adt(adt), Substs::identity(&generics))
+}
+
+fn type_for_type_alias(db: &impl HirDatabase, t: TypeAliasId) -> Ty {
+    let generics = db.generic_params(t.into());
+    let resolver = t.resolver(db);
+    let type_ref = &db.type_alias_data(t).type_ref;
+    let substs = Substs::identity(&generics);
+    let inner = Ty::from_hir(db, &resolver, type_ref.as_ref().unwrap_or(&TypeRef::Error));
+    inner.subst(&substs)
+}
+
+#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
+pub enum CallableDef {
+    FunctionId(FunctionId),
+    StructId(StructId),
+    EnumVariantId(EnumVariantId),
+}
+impl_froms!(CallableDef: FunctionId, StructId, EnumVariantId);
+
+impl CallableDef {
+    pub fn krate(self, db: &impl HirDatabase) -> CrateId {
+        match self {
+            CallableDef::FunctionId(f) => f.lookup(db).module(db).krate,
+            CallableDef::StructId(s) => s.module(db).krate,
+            CallableDef::EnumVariantId(e) => e.parent.module(db).krate,
+        }
+    }
+}
+
+impl From<CallableDef> for GenericDefId {
+    fn from(def: CallableDef) -> GenericDefId {
+        match def {
+            CallableDef::FunctionId(f) => f.into(),
+            CallableDef::StructId(s) => s.into(),
+            CallableDef::EnumVariantId(e) => e.into(),
+        }
+    }
+}
+
+#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
+pub enum TyDefId {
+    BuiltinType(BuiltinType),
+    AdtId(AdtId),
+    TypeAliasId(TypeAliasId),
+}
+impl_froms!(TyDefId: BuiltinType, AdtId(StructId, EnumId, UnionId), TypeAliasId);
+
+#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
+pub enum ValueTyDefId {
+    FunctionId(FunctionId),
+    StructId(StructId),
+    EnumVariantId(EnumVariantId),
+    ConstId(ConstId),
+    StaticId(StaticId),
+}
+impl_froms!(ValueTyDefId: FunctionId, StructId, EnumVariantId, ConstId, StaticId);
+
+/// Build the declared type of an item. This depends on the namespace; e.g. for
+/// `struct Foo(usize)`, we have two types: The type of the struct itself, and
+/// the constructor function `(usize) -> Foo` which lives in the values
+/// namespace.
+pub(crate) fn ty_query(db: &impl HirDatabase, def: TyDefId) -> Ty {
+    match def {
+        TyDefId::BuiltinType(it) => type_for_builtin(it),
+        TyDefId::AdtId(it) => type_for_adt(db, it),
+        TyDefId::TypeAliasId(it) => type_for_type_alias(db, it),
+    }
+}
+pub(crate) fn value_ty_query(db: &impl HirDatabase, def: ValueTyDefId) -> Ty {
+    match def {
+        ValueTyDefId::FunctionId(it) => type_for_fn(db, it),
+        ValueTyDefId::StructId(it) => type_for_struct_constructor(db, it),
+        ValueTyDefId::EnumVariantId(it) => type_for_enum_variant_constructor(db, it),
+        ValueTyDefId::ConstId(it) => type_for_const(db, it),
+        ValueTyDefId::StaticId(it) => type_for_static(db, it),
+    }
+}
diff --git a/crates/ra_hir_ty/src/marks.rs b/crates/ra_hir_ty/src/marks.rs
new file mode 100644
index 000000000..0f754eb9c
--- /dev/null
+++ b/crates/ra_hir_ty/src/marks.rs
@@ -0,0 +1,9 @@
+//! See test_utils/src/marks.rs
+
+test_utils::marks!(
+    type_var_cycles_resolve_completely
+    type_var_cycles_resolve_as_possible
+    type_var_resolves_to_int_var
+    match_ergonomics_ref
+    coerce_merge_fail_fallback
+);
diff --git a/crates/ra_hir_ty/src/method_resolution.rs b/crates/ra_hir_ty/src/method_resolution.rs
new file mode 100644
index 000000000..53c541eb8
--- /dev/null
+++ b/crates/ra_hir_ty/src/method_resolution.rs
@@ -0,0 +1,363 @@
+//! This module is concerned with finding methods that a given type provides.
+//! For details about how this works in rustc, see the method lookup page in the
+//! [rustc guide](https://rust-lang.github.io/rustc-guide/method-lookup.html)
+//! and the corresponding code mostly in librustc_typeck/check/method/probe.rs.
+use std::sync::Arc;
+
+use arrayvec::ArrayVec;
+use hir_def::{
+    lang_item::LangItemTarget, resolver::HasResolver, resolver::Resolver, type_ref::Mutability,
+    AssocItemId, AstItemDef, FunctionId, HasModule, ImplId, TraitId,
+};
+use hir_expand::name::Name;
+use ra_db::CrateId;
+use ra_prof::profile;
+use rustc_hash::FxHashMap;
+
+use crate::{
+    db::HirDatabase,
+    primitive::{FloatBitness, Uncertain},
+    utils::all_super_traits,
+    Ty, TypeCtor,
+};
+
+use super::{autoderef, Canonical, InEnvironment, TraitEnvironment, TraitRef};
+
+/// This is used as a key for indexing impls.
+#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
+pub enum TyFingerprint {
+    Apply(TypeCtor),
+}
+
+impl TyFingerprint {
+    /// Creates a TyFingerprint for looking up an impl. Only certain types can
+    /// have impls: if we have some `struct S`, we can have an `impl S`, but not
+    /// `impl &S`. Hence, this will return `None` for reference types and such.
+    fn for_impl(ty: &Ty) -> Option<TyFingerprint> {
+        match ty {
+            Ty::Apply(a_ty) => Some(TyFingerprint::Apply(a_ty.ctor)),
+            _ => None,
+        }
+    }
+}
+
+#[derive(Debug, PartialEq, Eq)]
+pub struct CrateImplBlocks {
+    impls: FxHashMap<TyFingerprint, Vec<ImplId>>,
+    impls_by_trait: FxHashMap<TraitId, Vec<ImplId>>,
+}
+
+impl CrateImplBlocks {
+    pub(crate) fn impls_in_crate_query(
+        db: &impl HirDatabase,
+        krate: CrateId,
+    ) -> Arc<CrateImplBlocks> {
+        let _p = profile("impls_in_crate_query");
+        let mut res =
+            CrateImplBlocks { impls: FxHashMap::default(), impls_by_trait: FxHashMap::default() };
+
+        let crate_def_map = db.crate_def_map(krate);
+        for (_module_id, module_data) in crate_def_map.modules.iter() {
+            for &impl_id in module_data.impls.iter() {
+                let impl_data = db.impl_data(impl_id);
+                let resolver = impl_id.resolver(db);
+
+                let target_ty = Ty::from_hir(db, &resolver, &impl_data.target_type);
+
+                match &impl_data.target_trait {
+                    Some(trait_ref) => {
+                        if let Some(tr) =
+                            TraitRef::from_hir(db, &resolver, &trait_ref, Some(target_ty))
+                        {
+                            res.impls_by_trait.entry(tr.trait_).or_default().push(impl_id);
+                        }
+                    }
+                    None => {
+                        if let Some(target_ty_fp) = TyFingerprint::for_impl(&target_ty) {
+                            res.impls.entry(target_ty_fp).or_default().push(impl_id);
+                        }
+                    }
+                }
+            }
+        }
+
+        Arc::new(res)
+    }
+    pub fn lookup_impl_blocks(&self, ty: &Ty) -> impl Iterator<Item = ImplId> + '_ {
+        let fingerprint = TyFingerprint::for_impl(ty);
+        fingerprint.and_then(|f| self.impls.get(&f)).into_iter().flatten().copied()
+    }