Merge #1120

1120: More trait infrastructure r=matklad a=flodiebold

This adds enough trait infrastructure to be able to make some deductions about type variables when resolving trait methods, while at the same time doing as little as possible that will be later replaced by Chalk :smile: 

E.g. (as the tests show) if we have
```rust
trait Trait<T> { fn method(self) -> T }
impl Trait<u32> for S {}
...
S.method()
```
we can infer that the return type is `u32`. On the other hand the unification logic is so primitive that we can't handle e.g. `impl<T> Trait<T> for S<T>`.

It's all quite hacky, I plan to refactor the parts that will stay, while hopefully the other parts will be replaced soon :slightly_smiling_face: In particular, we need to handle 'containers' (impls and trait defs) more cleanly, and I need to reorganize the method resolution / type inference code...

Co-authored-by: Florian Diebold <[email protected]>

12 files changed, 582 insertions, 220 deletions

diff --git a/crates/ra_hir/src/code_model_api.rs b/crates/ra_hir/src/code_model_api.rs
index 5d8cf57b6..8f1ed1086 100644
--- a/crates/ra_hir/src/code_model_api.rs
+++ b/crates/ra_hir/src/code_model_api.rs
@@ -11,7 +11,7 @@ use crate::{
     expr::{Body, BodySourceMap},
     ty::InferenceResult,
     adt::{EnumVariantId, StructFieldId, VariantDef},
-    generics::GenericParams,
+    generics::HasGenericParams,
     docs::{Documentation, Docs, docs_from_ast},
     ids::{FunctionId, StructId, EnumId, AstItemDef, ConstId, StaticId, TraitId, TypeAliasId},
     impl_block::ImplBlock,
@@ -189,12 +189,12 @@ impl Module {
         }
     }
 
-    pub(crate) fn resolver(&self, db: &impl HirDatabase) -> Resolver {
+    pub(crate) fn resolver(&self, db: &impl DefDatabase) -> Resolver {
         let def_map = db.crate_def_map(self.krate);
         Resolver::default().push_module_scope(def_map, self.module_id)
     }
 
-    pub fn declarations(self, db: &impl HirDatabase) -> Vec<ModuleDef> {
+    pub fn declarations(self, db: &impl DefDatabase) -> Vec<ModuleDef> {
         let def_map = db.crate_def_map(self.krate);
         def_map[self.module_id]
             .scope
@@ -299,10 +299,6 @@ impl Struct {
             .map(|(id, _)| StructField { parent: (*self).into(), id })
     }
 
-    pub fn generic_params(&self, db: &impl DefDatabase) -> Arc<GenericParams> {
-        db.generic_params((*self).into())
-    }
-
     pub fn ty(&self, db: &impl HirDatabase) -> Ty {
         db.type_for_def((*self).into(), Namespace::Types)
     }
@@ -363,10 +359,6 @@ impl Enum {
             .map(|(id, _)| EnumVariant { parent: *self, id })
     }
 
-    pub fn generic_params(&self, db: &impl DefDatabase) -> Arc<GenericParams> {
-        db.generic_params((*self).into())
-    }
-
     pub fn ty(&self, db: &impl HirDatabase) -> Ty {
         db.type_for_def((*self).into(), Namespace::Types)
     }
@@ -537,24 +529,32 @@ impl Function {
         db.infer((*self).into())
     }
 
-    pub fn generic_params(&self, db: &impl DefDatabase) -> Arc<GenericParams> {
-        db.generic_params((*self).into())
-    }
-
     /// The containing impl block, if this is a method.
     pub fn impl_block(&self, db: &impl DefDatabase) -> Option<ImplBlock> {
         let module_impls = db.impls_in_module(self.module(db));
         ImplBlock::containing(module_impls, (*self).into())
     }
 
+    /// The containing trait, if this is a trait method definition.
+    pub fn parent_trait(&self, db: &impl DefDatabase) -> Option<Trait> {
+        db.trait_items_index(self.module(db)).get_parent_trait((*self).into())
+    }
+
+    pub fn container(&self, db: &impl DefDatabase) -> Option<Container> {
+        if let Some(impl_block) = self.impl_block(db) {
+            Some(impl_block.into())
+        } else if let Some(trait_) = self.parent_trait(db) {
+            Some(trait_.into())
+        } else {
+            None
+        }
+    }
+
     // FIXME: move to a more general type for 'body-having' items
     /// Builds a resolver for code inside this item.
     pub(crate) fn resolver(&self, db: &impl HirDatabase) -> Resolver {
         // take the outer scope...
-        let r = self
-            .impl_block(db)
-            .map(|ib| ib.resolver(db))
-            .unwrap_or_else(|| self.module(db).resolver(db));
+        let r = self.container(db).map_or_else(|| self.module(db).resolver(db), |c| c.resolver(db));
         // ...and add generic params, if present
         let p = self.generic_params(db);
         let r = if !p.params.is_empty() { r.push_generic_params_scope(p) } else { r };
@@ -684,10 +684,6 @@ impl Trait {
         self.id.module(db)
     }
 
-    pub fn generic_params(&self, db: &impl DefDatabase) -> Arc<GenericParams> {
-        db.generic_params((*self).into())
-    }
-
     pub fn name(self, db: &impl DefDatabase) -> Option<Name> {
         self.trait_data(db).name().clone()
     }
@@ -699,6 +695,14 @@ impl Trait {
     pub(crate) fn trait_data(self, db: &impl DefDatabase) -> Arc<TraitData> {
         db.trait_data(self)
     }
+
+    pub(crate) fn resolver(&self, db: &impl DefDatabase) -> Resolver {
+        let r = self.module(db).resolver(db);
+        // add generic params, if present
+        let p = self.generic_params(db);
+        let r = if !p.params.is_empty() { r.push_generic_params_scope(p) } else { r };
+        r
+    }
 }
 
 impl Docs for Trait {
@@ -717,10 +721,6 @@ impl TypeAlias {
         self.id.source(db)
     }
 
-    pub fn generic_params(&self, db: &impl DefDatabase) -> Arc<GenericParams> {
-        db.generic_params((*self).into())
-    }
-
     pub fn module(&self, db: &impl DefDatabase) -> Module {
         self.id.module(db)
     }
@@ -731,6 +731,21 @@ impl TypeAlias {
         ImplBlock::containing(module_impls, (*self).into())
     }
 
+    /// The containing trait, if this is a trait method definition.
+    pub fn parent_trait(&self, db: &impl DefDatabase) -> Option<Trait> {
+        db.trait_items_index(self.module(db)).get_parent_trait((*self).into())
+    }
+
+    pub fn container(&self, db: &impl DefDatabase) -> Option<Container> {
+        if let Some(impl_block) = self.impl_block(db) {
+            Some(impl_block.into())
+        } else if let Some(trait_) = self.parent_trait(db) {
+            Some(trait_.into())
+        } else {
+            None
+        }
+    }
+
     pub fn type_ref(self, db: &impl DefDatabase) -> Arc<TypeRef> {
         db.type_alias_ref(self)
     }
@@ -754,3 +769,18 @@ impl Docs for TypeAlias {
         docs_from_ast(&*self.source(db).1)
     }
 }
+
+pub enum Container {
+    Trait(Trait),
+    ImplBlock(ImplBlock),
+}
+impl_froms!(Container: Trait, ImplBlock);
+
+impl Container {
+    pub(crate) fn resolver(&self, db: &impl DefDatabase) -> Resolver {
+        match self {
+            Container::Trait(trait_) => trait_.resolver(db),
+            Container::ImplBlock(impl_block) => impl_block.resolver(db),
+        }
+    }
+}
diff --git a/crates/ra_hir/src/db.rs b/crates/ra_hir/src/db.rs
index e23e2bb2b..18627bbc2 100644
--- a/crates/ra_hir/src/db.rs
+++ b/crates/ra_hir/src/db.rs
@@ -53,6 +53,9 @@ pub trait DefDatabase: SourceDatabase {
     #[salsa::invoke(crate::traits::TraitData::trait_data_query)]
     fn trait_data(&self, t: Trait) -> Arc<TraitData>;
 
+    #[salsa::invoke(crate::traits::TraitItemsIndex::trait_items_index)]
+    fn trait_items_index(&self, module: Module) -> crate::traits::TraitItemsIndex;
+
     #[salsa::invoke(crate::source_id::AstIdMap::ast_id_map_query)]
     fn ast_id_map(&self, file_id: HirFileId) -> Arc<AstIdMap>;
 
@@ -128,8 +131,8 @@ pub trait HirDatabase: DefDatabase {
     #[salsa::invoke(crate::ty::method_resolution::CrateImplBlocks::impls_in_crate_query)]
     fn impls_in_crate(&self, krate: Crate) -> Arc<CrateImplBlocks>;
 
-    #[salsa::invoke(crate::ty::method_resolution::implements)]
-    fn implements(&self, trait_ref: TraitRef) -> bool;
+    #[salsa::invoke(crate::ty::traits::implements)]
+    fn implements(&self, trait_ref: TraitRef) -> Option<crate::ty::traits::Solution>;
 }
 
 #[test]
diff --git a/crates/ra_hir/src/generics.rs b/crates/ra_hir/src/generics.rs
index 84fe94289..5625c2459 100644
--- a/crates/ra_hir/src/generics.rs
+++ b/crates/ra_hir/src/generics.rs
@@ -9,7 +9,7 @@ use ra_syntax::ast::{self, NameOwner, TypeParamsOwner};
 
 use crate::{
     db::DefDatabase,
-    Name, AsName, Function, Struct, Enum, Trait, TypeAlias, ImplBlock
+    Name, AsName, Function, Struct, Enum, Trait, TypeAlias, ImplBlock, Container
 };
 
 /// Data about a generic parameter (to a function, struct, impl, ...).
@@ -27,6 +27,7 @@ pub struct GenericParams {
     pub(crate) params: Vec<GenericParam>,
 }
 
+// FIXME: consts can have type parameters from their parents (i.e. associated consts of traits)
 #[derive(Clone, Copy, PartialEq, Eq, Debug, Hash)]
 pub enum GenericDef {
     Function(Function),
@@ -45,18 +46,22 @@ impl GenericParams {
     ) -> Arc<GenericParams> {
         let mut generics = GenericParams::default();
         let parent = match def {
-            GenericDef::Function(it) => it.impl_block(db),
-            GenericDef::TypeAlias(it) => it.impl_block(db),
+            GenericDef::Function(it) => it.container(db).map(GenericDef::from),
+            GenericDef::TypeAlias(it) => it.container(db).map(GenericDef::from),
             GenericDef::Struct(_) | GenericDef::Enum(_) | GenericDef::Trait(_) => None,
             GenericDef::ImplBlock(_) => None,
         };
-        generics.parent_params = parent.map(|p| p.generic_params(db));
+        generics.parent_params = parent.map(|p| db.generic_params(p));
         let start = generics.parent_params.as_ref().map(|p| p.params.len()).unwrap_or(0) as u32;
         match def {
             GenericDef::Function(it) => generics.fill(&*it.source(db).1, start),
             GenericDef::Struct(it) => generics.fill(&*it.source(db).1, start),
             GenericDef::Enum(it) => generics.fill(&*it.source(db).1, start),
-            GenericDef::Trait(it) => generics.fill(&*it.source(db).1, start),
+            GenericDef::Trait(it) => {
+                // traits get the Self type as an implicit first type parameter
+                generics.params.push(GenericParam { idx: start, name: Name::self_type() });
+                generics.fill(&*it.source(db).1, start + 1);
+            }
             GenericDef::TypeAlias(it) => generics.fill(&*it.source(db).1, start),
             GenericDef::ImplBlock(it) => generics.fill(&*it.source(db).1, start),
         }
@@ -104,3 +109,25 @@ impl GenericParams {
         vec
     }
 }
+
+impl From<Container> for GenericDef {
+    fn from(c: Container) -> Self {
+        match c {
+            Container::Trait(trait_) => trait_.into(),
+            Container::ImplBlock(impl_block) => impl_block.into(),
+        }
+    }
+}
+
+pub trait HasGenericParams {
+    fn generic_params(self, db: &impl DefDatabase) -> Arc<GenericParams>;
+}
+
+impl<T> HasGenericParams for T
+where
+    T: Into<GenericDef>,
+{
+    fn generic_params(self, db: &impl DefDatabase) -> Arc<GenericParams> {
+        db.generic_params(self.into())
+    }
+}
diff --git a/crates/ra_hir/src/impl_block.rs b/crates/ra_hir/src/impl_block.rs
index b306874cc..a8a466e43 100644
--- a/crates/ra_hir/src/impl_block.rs
+++ b/crates/ra_hir/src/impl_block.rs
@@ -9,16 +9,15 @@ use ra_syntax::{
 
 use crate::{
     Const, TypeAlias, Function, HirFileId,
-    HirDatabase, DefDatabase,
-    ModuleDef, Trait, Resolution,
+    HirDatabase, DefDatabase, TraitRef,
     type_ref::TypeRef,
     ids::LocationCtx,
     resolve::Resolver,
-    ty::Ty, generics::GenericParams,
+    ty::Ty,
+    generics::HasGenericParams,
+    code_model_api::{Module, ModuleSource}
 };
 
-use crate::code_model_api::{Module, ModuleSource};
-
 #[derive(Debug, Default, PartialEq, Eq)]
 pub struct ImplSourceMap {
     map: ArenaMap<ImplId, AstPtr<ast::ImplBlock>>,
@@ -73,7 +72,7 @@ impl ImplBlock {
         self.module
     }
 
-    pub fn target_trait_ref(&self, db: &impl DefDatabase) -> Option<TypeRef> {
+    pub fn target_trait(&self, db: &impl DefDatabase) -> Option<TypeRef> {
         db.impls_in_module(self.module).impls[self.impl_id].target_trait().cloned()
     }
 
@@ -85,27 +84,16 @@ impl ImplBlock {
         Ty::from_hir(db, &self.resolver(db), &self.target_type(db))
     }
 
-    pub fn target_trait(&self, db: &impl HirDatabase) -> Option<Trait> {
-        if let Some(TypeRef::Path(path)) = self.target_trait_ref(db) {
-            let resolver = self.resolver(db);
-            if let Some(Resolution::Def(ModuleDef::Trait(tr))) =
-                resolver.resolve_path(db, &path).take_types()
-            {
-                return Some(tr);
-            }
-        }
-        None
+    pub fn target_trait_ref(&self, db: &impl HirDatabase) -> Option<TraitRef> {
+        let target_ty = self.target_ty(db);
+        TraitRef::from_hir(db, &self.resolver(db), &self.target_trait(db)?, Some(target_ty))
     }
 
     pub fn items(&self, db: &impl DefDatabase) -> Vec<ImplItem> {
         db.impls_in_module(self.module).impls[self.impl_id].items().to_vec()
     }
 
-    pub fn generic_params(&self, db: &impl DefDatabase) -> Arc<GenericParams> {
-        db.generic_params((*self).into())
-    }
-
-    pub(crate) fn resolver(&self, db: &impl HirDatabase) -> Resolver {
+    pub(crate) fn resolver(&self, db: &impl DefDatabase) -> Resolver {
         let r = self.module().resolver(db);
         // add generic params, if present
         let p = self.generic_params(db);
diff --git a/crates/ra_hir/src/lib.rs b/crates/ra_hir/src/lib.rs
index a9db23060..9292de1b5 100644
--- a/crates/ra_hir/src/lib.rs
+++ b/crates/ra_hir/src/lib.rs
@@ -61,12 +61,13 @@ pub use self::{
     source_id::{AstIdMap, ErasedFileAstId},
     ids::{HirFileId, MacroDefId, MacroCallId, MacroCallLoc},
     nameres::{PerNs, Namespace, ImportId},
-    ty::{Ty, ApplicationTy, TypeCtor, Substs, display::HirDisplay, CallableDef},
+    ty::{Ty, ApplicationTy, TypeCtor, TraitRef, Substs, display::HirDisplay, CallableDef},
     impl_block::{ImplBlock, ImplItem},
     docs::{Docs, Documentation},
     adt::AdtDef,
     expr::ExprScopes,
     resolve::Resolution,
+    generics::{GenericParams, GenericParam, HasGenericParams},
     source_binder::{SourceAnalyzer, PathResolution, ScopeEntryWithSyntax},
 };
 
@@ -78,5 +79,5 @@ pub use self::code_model_api::{
     Function, FnSignature,
     StructField, FieldSource,
     Static, Const, ConstSignature,
-    Trait, TypeAlias,
+    Trait, TypeAlias, Container,
 };
diff --git a/crates/ra_hir/src/traits.rs b/crates/ra_hir/src/traits.rs
index 725bdd5cb..15f0977b7 100644
--- a/crates/ra_hir/src/traits.rs
+++ b/crates/ra_hir/src/traits.rs
@@ -1,10 +1,11 @@
 //! HIR for trait definitions.
 
 use std::sync::Arc;
+use rustc_hash::FxHashMap;
 
 use ra_syntax::ast::{self, NameOwner};
 
-use crate::{Function, Const, TypeAlias, Name, DefDatabase, Trait, ids::LocationCtx, name::AsName};
+use crate::{Function, Const, TypeAlias, Name, DefDatabase, Trait, ids::LocationCtx, name::AsName, Module};
 
 #[derive(Debug, Clone, PartialEq, Eq)]
 pub struct TraitData {
@@ -49,4 +50,34 @@ pub enum TraitItem {
     TypeAlias(TypeAlias),
     // Existential
 }
+// FIXME: not every function, ... is actually a trait item. maybe we should make
+// sure that you can only turn actual trait items into TraitItems. This would
+// require not implementing From, and instead having some checked way of
+// casting them.
 impl_froms!(TraitItem: Function, Const, TypeAlias);
+
+#[derive(Debug, Clone, PartialEq, Eq)]
+pub struct TraitItemsIndex {
+    traits_by_def: FxHashMap<TraitItem, Trait>,
+}
+
+impl TraitItemsIndex {
+    pub(crate) fn trait_items_index(db: &impl DefDatabase, module: Module) -> TraitItemsIndex {
+        let mut index = TraitItemsIndex { traits_by_def: FxHashMap::default() };
+        for decl in module.declarations(db) {
+            match decl {
+                crate::ModuleDef::Trait(tr) => {
+                    for item in tr.trait_data(db).items() {
+                        index.traits_by_def.insert(*item, tr);
+                    }
+                }
+                _ => {}
+            }
+        }
+        index
+    }
+
+    pub(crate) fn get_parent_trait(&self, item: TraitItem) -> Option<Trait> {
+        self.traits_by_def.get(&item).cloned()
+    }
+}
diff --git a/crates/ra_hir/src/ty.rs b/crates/ra_hir/src/ty.rs
index ecf13fbc3..12e10c751 100644
--- a/crates/ra_hir/src/ty.rs
+++ b/crates/ra_hir/src/ty.rs
@@ -5,6 +5,7 @@ mod autoderef;
 pub(crate) mod primitive;
 #[cfg(test)]
 mod tests;
+pub(crate) mod traits;
 pub(crate) mod method_resolution;
 mod op;
 mod lower;
@@ -145,6 +146,10 @@ impl Substs {
         Substs(Arc::new([ty]))
     }
 
+    pub fn prefix(&self, n: usize) -> Substs {
+        Substs(self.0.iter().cloned().take(n).collect::<Vec<_>>().into())
+    }
+
     pub fn iter(&self) -> impl Iterator<Item = &Ty> {
         self.0.iter()
     }
@@ -170,6 +175,12 @@ impl Substs {
     }
 }
 
+impl From<Vec<Ty>> for Substs {
+    fn from(v: Vec<Ty>) -> Self {
+        Substs(v.into())
+    }
+}
+
 /// 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)]
@@ -210,6 +221,14 @@ impl FnSig {
         &self.params_and_return[self.params_and_return.len() - 1]
     }
 
+    /// Applies the given substitutions to all types in this signature and
+    /// returns the result.
+    pub fn subst(&self, substs: &Substs) -> FnSig {
+        let result: Vec<_> =
+            self.params_and_return.iter().map(|ty| ty.clone().subst(substs)).collect();
+        FnSig { params_and_return: result.into() }
+    }
+
     pub fn walk_mut(&mut self, f: &mut impl FnMut(&mut Ty)) {
         // Without an Arc::make_mut_slice, we can't avoid the clone here:
         let mut v: Vec<_> = self.params_and_return.iter().cloned().collect();
@@ -309,6 +328,20 @@ impl Ty {
         }
     }
 
+    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))
+                }
+                _ => 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
diff --git a/crates/ra_hir/src/ty/infer.rs b/crates/ra_hir/src/ty/infer.rs
index 28947be51..651a78fe5 100644
--- a/crates/ra_hir/src/ty/infer.rs
+++ b/crates/ra_hir/src/ty/infer.rs
@@ -20,9 +20,9 @@ use std::sync::Arc;
 use std::mem;
 
 use ena::unify::{InPlaceUnificationTable, UnifyKey, UnifyValue, NoError};
-use ra_arena::map::ArenaMap;
 use rustc_hash::FxHashMap;
 
+use ra_arena::map::ArenaMap;
 use test_utils::tested_by;
 
 use crate::{
@@ -33,15 +33,18 @@ use crate::{
     ImplItem,
     type_ref::{TypeRef, Mutability},
     expr::{Body, Expr, BindingAnnotation, Literal, ExprId, Pat, PatId, UnaryOp, BinaryOp, Statement, FieldPat,Array, self},
-    generics::GenericParams,
+    generics::{GenericParams, HasGenericParams},
     path::{GenericArgs, GenericArg},
     adt::VariantDef,
     resolve::{Resolver, Resolution},
     nameres::Namespace,
-    ty::infer::diagnostics::InferenceDiagnostic,
     diagnostics::DiagnosticSink,
 };
-use super::{Ty, TypableDef, Substs, primitive, op, FnSig, ApplicationTy, TypeCtor};
+use super::{
+    Ty, TypableDef, Substs, primitive, op, ApplicationTy, TypeCtor, CallableDef, TraitRef,
+    traits::{ Solution, Obligation, Guidance},
+};
+use self::diagnostics::InferenceDiagnostic;
 
 /// The entry point of type inference.
 pub fn infer(db: &impl HirDatabase, def: DefWithBody) -> Arc<InferenceResult> {
@@ -153,6 +156,7 @@ struct InferenceContext<'a, D: HirDatabase> {
     body: Arc<Body>,
     resolver: Resolver,
     var_unification_table: InPlaceUnificationTable<TypeVarId>,
+    obligations: Vec<Obligation>,
     method_resolutions: FxHashMap<ExprId, Function>,
     field_resolutions: FxHashMap<ExprId, StructField>,
     assoc_resolutions: FxHashMap<ExprOrPatId, ImplItem>,
@@ -173,6 +177,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
             type_of_pat: ArenaMap::default(),
             diagnostics: Vec::default(),
             var_unification_table: InPlaceUnificationTable::new(),
+            obligations: Vec::default(),
             return_ty: Ty::Unknown, // set in collect_fn_signature
             db,
             body,
@@ -181,6 +186,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
     }
 
     fn resolve_all(mut self) -> InferenceResult {
+        // FIXME resolve obligations as well (use Guidance if necessary)
         let mut tv_stack = Vec::new();
         let mut expr_types = mem::replace(&mut self.type_of_expr, ArenaMap::default());
         for ty in expr_types.values_mut() {
@@ -311,11 +317,49 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
         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 {
+            // FIXME resolve types in the obligation first
+            let (solution, var_mapping) = match &obligation {
+                Obligation::Trait(tr) => {
+                    let (tr, var_mapping) = super::traits::canonicalize(tr.clone());
+                    (self.db.implements(tr), var_mapping)
+                }
+            };
+            match solution {
+                Some(Solution::Unique(substs)) => {
+                    for (i, subst) in substs.0.iter().enumerate() {
+                        let uncanonical = var_mapping[i];
+                        // FIXME the subst may contain type variables, which would need to be mapped back as well
+                        self.unify(&Ty::Infer(InferTy::TypeVar(uncanonical)), subst);
+                    }
+                }
+                Some(Solution::Ambig(Guidance::Definite(substs))) => {
+                    for (i, subst) in substs.0.iter().enumerate() {
+                        let uncanonical = var_mapping[i];
+                        // FIXME the subst may contain type variables, which would need to be mapped back as well
+                        self.unify(&Ty::Infer(InferTy::TypeVar(uncanonical)), subst);
+                    }
+                    self.obligations.push(obligation);
+                }
+                Some(_) => {
+                    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();
@@ -420,6 +464,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
         for segment in &path.segments[remaining_index..] {
             let ty = match resolved {
                 Resolution::Def(def) => {
+                    // FIXME resolve associated items from traits as well
                     let typable: Option<TypableDef> = def.into();
                     let typable = typable?;
 
@@ -709,13 +754,21 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
     fn substs_for_method_call(
         &mut self,
         def_generics: Option<Arc<GenericParams>>,
-        generic_args: &Option<GenericArgs>,
+        generic_args: Option<&GenericArgs>,
+        receiver_ty: &Ty,
     ) -> Substs {
         let (parent_param_count, param_count) =
-            def_generics.map_or((0, 0), |g| (g.count_parent_params(), g.params.len()));
+            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);
-        for _ in 0..parent_param_count {
-            substs.push(Ty::Unknown);
+        // 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.as_known_name() == Some(crate::KnownName::SelfType) {
+                    substs.push(receiver_ty.clone());
+                } else {
+                    substs.push(Ty::Unknown);
+                }
+            }
         }
         // handle provided type arguments
         if let Some(generic_args) = generic_args {
@@ -737,6 +790,83 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
         Substs(substs.into())
     }
 
+    fn register_obligations_for_call(&mut self, callable_ty: &Ty) {
+        match callable_ty {
+            Ty::Apply(a_ty) => match a_ty.ctor {
+                TypeCtor::FnDef(def) => {
+                    // add obligation for trait implementation, if this is a trait method
+                    // FIXME also register obligations from where clauses from the trait or impl and method
+                    match def {
+                        CallableDef::Function(f) => {
+                            if let Some(trait_) = f.parent_trait(self.db) {
+                                // construct a TraitDef
+                                let substs = a_ty.parameters.prefix(
+                                    trait_.generic_params(self.db).count_params_including_parent(),
+                                );
+                                self.obligations
+                                    .push(Obligation::Trait(TraitRef { trait_, substs }));
+                            }
+                        }
+                        CallableDef::Struct(_) | CallableDef::EnumVariant(_) => {}
+                    }
+                }
+                _ => {}
+            },
+            _ => {}
+        }
+    }
+
+    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 resolved = receiver_ty.clone().lookup_method(self.db, method_name, &self.resolver);
+        let (derefed_receiver_ty, method_ty, def_generics) = match resolved {
+            Some((ty, func)) => {
+                self.write_method_resolution(tgt_expr, func);
+                (
+                    ty,
+                    self.db.type_for_def(func.into(), Namespace::Values),
+                    Some(func.generic_params(self.db)),
+                )
+            }
+            None => (receiver_ty, Ty::Unknown, None),
+        };
+        let substs =
+            self.substs_for_method_call(def_generics.clone(), 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);
+
+        let param_iter = param_tys.into_iter().chain(repeat(Ty::Unknown));
+        for (arg, param) in args.iter().zip(param_iter) {
+            self.infer_expr(*arg, &Expectation::has_type(param));
+        }
+        ret_ty
+    }
+
     fn infer_expr(&mut self, tgt_expr: ExprId, expected: &Expectation) -> Ty {
         let body = Arc::clone(&self.body); // avoid borrow checker problem
         let ty = match &body[tgt_expr] {
@@ -793,102 +923,23 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
             }
             Expr::Call { callee, args } => {
                 let callee_ty = self.infer_expr(*callee, &Expectation::none());
-                let (param_tys, ret_ty) = match &callee_ty {
-                    Ty::Apply(a_ty) => match a_ty.ctor {
-                        TypeCtor::FnPtr => {
-                            let sig = FnSig::from_fn_ptr_substs(&a_ty.parameters);
-                            (sig.params().to_vec(), sig.ret().clone())
-                        }
-                        TypeCtor::FnDef(def) => {
-                            let sig = self.db.callable_item_signature(def);
-                            let ret_ty = sig.ret().clone().subst(&a_ty.parameters);
-                            let param_tys = sig
-                                .params()
-                                .iter()
-                                .map(|ty| ty.clone().subst(&a_ty.parameters))
-                                .collect();
-                            (param_tys, ret_ty)
-                        }
-                        _ => (Vec::new(), Ty::Unknown),
-                    },
-                    _ => {
-                        // not callable
-                        // FIXME report an error?
+                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)
                     }
                 };
+                // FIXME register obligations from where clauses from the function
                 let param_iter = param_tys.into_iter().chain(repeat(Ty::Unknown));
                 for (arg, param) in args.iter().zip(param_iter) {
                     self.infer_expr(*arg, &Expectation::has_type(param));
                 }
                 ret_ty
             }
-            Expr::MethodCall { receiver, args, method_name, generic_args } => {
-                let receiver_ty = self.infer_expr(*receiver, &Expectation::none());
-                let resolved =
-                    receiver_ty.clone().lookup_method(self.db, method_name, &self.resolver);
-                let (derefed_receiver_ty, method_ty, def_generics) = match resolved {
-                    Some((ty, func)) => {
-                        self.write_method_resolution(tgt_expr, func);
-                        (
-                            ty,
-                            self.db.type_for_def(func.into(), Namespace::Values),
-                            Some(func.generic_params(self.db)),
-                        )
-                    }
-                    None => (receiver_ty, Ty::Unknown, None),
-                };
-                let substs = self.substs_for_method_call(def_generics, generic_args);
-                let method_ty = method_ty.apply_substs(substs);
-                let method_ty = self.insert_type_vars(method_ty);
-                let (expected_receiver_ty, param_tys, ret_ty) = match &method_ty {
-                    Ty::Apply(a_ty) => match a_ty.ctor {
-                        TypeCtor::FnPtr => {
-                            let sig = FnSig::from_fn_ptr_substs(&a_ty.parameters);
-                            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())
-                            }
-                        }
-                        TypeCtor::FnDef(def) => {
-                            let sig = self.db.callable_item_signature(def);
-                            let ret_ty = sig.ret().clone().subst(&a_ty.parameters);
-
-                            if !sig.params().is_empty() {
-                                let mut params_iter = sig
-                                    .params()
-                                    .iter()
-                                    .map(|ty| ty.clone().subst(&a_ty.parameters));
-                                let receiver_ty = params_iter.next().unwrap();
-                                (receiver_ty, params_iter.collect(), ret_ty)
-                            } else {
-                                (Ty::Unknown, Vec::new(), ret_ty)
-                            }
-                        }
-                        _ => (Ty::Unknown, Vec::new(), Ty::Unknown),
-                    },
-                    _ => (Ty::Unknown, Vec::new(), Ty::Unknown),
-                };
-                // Apply autoref so the below unification works correctly
-                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);
-
-                let param_iter = param_tys.into_iter().chain(repeat(Ty::Unknown));
-                for (arg, param) in args.iter().zip(param_iter) {
-                    self.infer_expr(*arg, &Expectation::has_type(param));
-                }
-                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 expected = if expected.ty == Ty::Unknown {
                     Expectation::has_type(self.new_type_var())
@@ -1180,7 +1231,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
 
 /// The ID of a type variable.
 #[derive(Copy, Clone, PartialEq, Eq, Hash, Debug)]
-pub struct TypeVarId(u32);
+pub struct TypeVarId(pub(super) u32);
 
 impl UnifyKey for TypeVarId {
     type Value = TypeVarValue;
diff --git a/crates/ra_hir/src/ty/lower.rs b/crates/ra_hir/src/ty/lower.rs
index 003a89f0d..7fac084ce 100644
--- a/crates/ra_hir/src/ty/lower.rs
+++ b/crates/ra_hir/src/ty/lower.rs
@@ -5,6 +5,7 @@
 //!  - 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 crate::{
     Function, Struct, StructField, Enum, EnumVariant, Path,
@@ -15,11 +16,11 @@ use crate::{
     name::KnownName,
     nameres::Namespace,
     resolve::{Resolver, Resolution},
-    path::{ PathSegment, GenericArg},
-    generics::GenericParams,
-    adt::VariantDef,
+    path::{PathSegment, GenericArg},
+    generics::{GenericParams, HasGenericParams},
+    adt::VariantDef, Trait
 };
-use super::{Ty, primitive, FnSig, Substs, TypeCtor};
+use super::{Ty, primitive, FnSig, Substs, TypeCtor, TraitRef};
 
 impl Ty {
     pub(crate) fn from_hir(db: &impl HirDatabase, resolver: &Resolver, type_ref: &TypeRef) -> Self {
@@ -115,7 +116,6 @@ impl Ty {
         segment: &PathSegment,
         resolved: TypableDef,
     ) -> Substs {
-        let mut substs = Vec::new();
         let def_generics = match resolved {
             TypableDef::Function(func) => func.generic_params(db),
             TypableDef::Struct(s) => s.generic_params(db),
@@ -124,28 +124,7 @@ impl Ty {
             TypableDef::TypeAlias(t) => t.generic_params(db),
             TypableDef::Const(_) | TypableDef::Static(_) => GenericParams::default().into(),
         };
-        let parent_param_count = def_generics.count_parent_params();
-        substs.extend((0..parent_param_count).map(|_| 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 param_count = def_generics.params.len();
-            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
-        // FIXME: handle defaults
-        let supplied_params = substs.len();
-        for _ in supplied_params..def_generics.count_params_including_parent() {
-            substs.push(Ty::Unknown);
-        }
-        assert_eq!(substs.len(), def_generics.count_params_including_parent());
-        Substs(substs.into())
+        substs_from_path_segment(db, resolver, segment, &def_generics, false)
     }
 
     /// Collect generic arguments from a path into a `Substs`. See also
@@ -185,6 +164,82 @@ impl Ty {
     }
 }
 
+pub(super) fn substs_from_path_segment(
+    db: &impl HirDatabase,
+    resolver: &Resolver,
+    segment: &PathSegment,
+    def_generics: &GenericParams,
+    add_self_param: bool,
+) -> Substs {
+    let mut substs = Vec::new();
+    let parent_param_count = def_generics.count_parent_params();
+    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 = def_generics.params.len() - 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
+    // FIXME: handle defaults
+    let supplied_params = substs.len();
+    for _ in supplied_params..def_generics.count_params_including_parent() {
+        substs.push(Ty::Unknown);
+    }
+    assert_eq!(substs.len(), def_generics.count_params_including_parent());
+    Substs(substs.into())
+}
+
+impl TraitRef {
+    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,
+        };
+        let resolved = match resolver.resolve_path(db, &path).take_types()? {
+            Resolution::Def(ModuleDef::Trait(tr)) => tr,
+            _ => return None,
+        };
+        let mut substs = Self::substs_from_path(db, resolver, path, resolved);
+        if let Some(self_ty) = explicit_self_ty {
+            // FIXME this could be nicer
+            let mut substs_vec = substs.0.to_vec();
+            substs_vec[0] = self_ty;
+            substs.0 = substs_vec.into();
+        }
+        Some(TraitRef { trait_: resolved, substs })
+    }
+
+    fn substs_from_path(
+        db: &impl HirDatabase,
+        resolver: &Resolver,
+        path: &Path,
+        resolved: Trait,
+    ) -> Substs {
+        let segment = path.segments.last().expect("path should have at least one segment");
+        substs_from_path_segment(db, resolver, segment, &resolved.generic_params(db), true)
+    }
+}
+
 /// 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
diff --git a/crates/ra_hir/src/ty/method_resolution.rs b/crates/ra_hir/src/ty/method_resolution.rs
index bb23246a6..6b7918187 100644
--- a/crates/ra_hir/src/ty/method_resolution.rs
+++ b/crates/ra_hir/src/ty/method_resolution.rs
@@ -10,10 +10,12 @@ use crate::{
     HirDatabase, Module, Crate, Name, Function, Trait,
     impl_block::{ImplId, ImplBlock, ImplItem},
     ty::{Ty, TypeCtor},
-    nameres::CrateModuleId, resolve::Resolver, traits::TraitItem
-
+    nameres::CrateModuleId,
+    resolve::Resolver,
+    traits::TraitItem,
+    generics::HasGenericParams,
 };
-use super::{ TraitRef, Substs};
+use super::{TraitRef, Substs};
 
 /// This is used as a key for indexing impls.
 #[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
@@ -72,9 +74,9 @@ impl CrateImplBlocks {
 
             let target_ty = impl_block.target_ty(db);
 
-            if let Some(tr) = impl_block.target_trait(db) {
+            if let Some(tr) = impl_block.target_trait_ref(db) {
                 self.impls_by_trait
-                    .entry(tr)
+                    .entry(tr.trait_)
                     .or_insert_with(Vec::new)
                     .push((module.module_id, impl_id));
             } else {
@@ -108,20 +110,6 @@ impl CrateImplBlocks {
     }
 }
 
-/// Rudimentary check whether an impl exists for a given type and trait; this
-/// will actually be done by chalk.
-pub(crate) fn implements(db: &impl HirDatabase, trait_ref: TraitRef) -> bool {
-    // FIXME use all trait impls in the whole crate graph
-    let krate = trait_ref.trait_.module(db).krate(db);
-    let krate = match krate {
-        Some(krate) => krate,
-        None => return false,
-    };
-    let crate_impl_blocks = db.impls_in_crate(krate);
-    let mut impl_blocks = crate_impl_blocks.lookup_impl_blocks_for_trait(&trait_ref.trait_);
-    impl_blocks.any(|impl_block| &impl_block.target_ty(db) == trait_ref.self_ty())
-}
-
 fn def_crate(db: &impl HirDatabase, ty: &Ty) -> Option<Crate> {
     match ty {
         Ty::Apply(a_ty) => match a_ty.ctor {
@@ -142,6 +130,7 @@ impl Ty {
         resolver: &Resolver,
     ) -> Option<(Ty, Function)> {
         // FIXME: trait methods should be used before autoderefs
+        // (and we need to do autoderefs for trait method calls as well)
         let inherent_method = self.clone().iterate_methods(db, |ty, f| {
             let sig = f.signature(db);
             if sig.name() == name && sig.has_self_param() {
@@ -174,22 +163,15 @@ impl Ty {
                 }
             }
         }
-        // FIXME:
-        //  - we might not actually be able to determine fully that the type
-        //    implements the trait here; it's enough if we (well, Chalk) determine
-        //    that it's possible.
-        //  - when the trait method is picked, we need to register an
-        //    'obligation' somewhere so that we later check that it's really
-        //    implemented
-        //  - both points go for additional requirements from where clauses as
-        //    well (in fact, the 'implements' condition could just be considered a
-        //    'where Self: Trait' clause)
         candidates.retain(|(t, _m)| {
-            let trait_ref = TraitRef { trait_: *t, substs: Substs::single(self.clone()) };
-            db.implements(trait_ref)
+            let trait_ref =
+                TraitRef { trait_: *t, substs: fresh_substs_for_trait(db, *t, self.clone()) };
+            let (trait_ref, _) = super::traits::canonicalize(trait_ref);
+            db.implements(trait_ref).is_some()
         });
         // FIXME if there's multiple candidates here, that's an ambiguity error
         let (_chosen_trait, chosen_method) = candidates.first()?;
+        // FIXME return correct receiver type
         Some((self.clone(), *chosen_method))
     }
 
@@ -252,3 +234,17 @@ impl Ty {
         None
     }
 }
+
+/// This creates Substs for a trait with the given Self type and type variables
+/// for all other parameters. This is kind of a hack since these aren't 'real'
+/// type variables; the resulting trait reference is just used for the
+/// preliminary method candidate check.
+fn fresh_substs_for_trait(db: &impl HirDatabase, tr: Trait, self_ty: Ty) -> Substs {
+    let mut substs = Vec::new();
+    let generics = tr.generic_params(db);
+    substs.push(self_ty);
+    substs.extend(generics.params_including_parent().into_iter().skip(1).enumerate().map(
+        |(i, _p)| Ty::Infer(super::infer::InferTy::TypeVar(super::infer::TypeVarId(i as u32))),
+    ));
+    substs.into()
+}
diff --git a/crates/ra_hir/src/ty/tests.rs b/crates/ra_hir/src/ty/tests.rs
index d7c2ca132..291bc9ae5 100644
--- a/crates/ra_hir/src/ty/tests.rs
+++ b/crates/ra_hir/src/ty/tests.rs
@@ -1926,8 +1926,8 @@ fn test() {
 }
 "#),
         @r###"
-[31; 35) 'self': &{unknown}
-[110; 114) 'self': &{unknown}
+[31; 35) 'self': &Self
+[110; 114) 'self': &Self
 [170; 228) '{     ...i128 }': ()
 [176; 178) 'S1': S1
 [176; 187) 'S1.method()': u32
@@ -1972,8 +1972,8 @@ mod bar_test {
 }
 "#),
         @r###"
-[63; 67) 'self': &{unknown}
-[169; 173) 'self': &{unknown}
+[63; 67) 'self': &Self
+[169; 173) 'self': &Self
 [300; 337) '{     ...     }': ()
 [310; 311) 'S': S
 [310; 320) 'S.method()': u32
@@ -1998,10 +1998,45 @@ fn test() {
 }
 "#),
         @r###"
-[33; 37) 'self': &{unknown}
+[33; 37) 'self': &Self
 [92; 111) '{     ...d(); }': ()
 [98; 99) 'S': S
-[98; 108) 'S.method()': {unknown}"###
+[98; 108) 'S.method()': u32"###
+    );
+}
+
+#[test]
+fn infer_trait_method_generic_more_params() {
+    // the trait implementation is intentionally incomplete -- it shouldn't matter
+    assert_snapshot_matches!(
+        infer(r#"
+trait Trait<T1, T2, T3> {
+    fn method1(&self) -> (T1, T2, T3);
+    fn method2(&self) -> (T3, T2, T1);
+}
+struct S1;
+impl Trait<u8, u16, u32> for S1 {}
+struct S2;
+impl<T> Trait<i8, i16, T> for S2 {}
+fn test() {
+    S1.method1(); // u8, u16, u32
+    S1.method2(); // u32, u16, u8
+    S2.method1(); // i8, i16, {unknown}
+    S2.method2(); // {unknown}, i16, i8
+}
+"#),
+        @r###"
+[43; 47) 'self': &Self
+[82; 86) 'self': &Self
+[210; 361) '{     ..., i8 }': ()
+[216; 218) 'S1': S1
+[216; 228) 'S1.method1()': (u8, u16, u32)
+[250; 252) 'S1': S1
+[250; 262) 'S1.method2()': (u32, u16, u8)
+[284; 286) 'S2': S2
+[284; 296) 'S2.method1()': (i8, i16, {unknown})
+[324; 326) 'S2': S2
+[324; 336) 'S2.method2()': ({unknown}, i16, i8)"###
     );
 }
 
@@ -2020,7 +2055,7 @@ fn test() {
 }
 "#),
         @r###"
-[33; 37) 'self': &{unknown}
+[33; 37) 'self': &Self
 [102; 127) '{     ...d(); }': ()
 [108; 109) 'S': S<u32>(T) -> S<T>
 [108; 115) 'S(1u32)': S<u32>
@@ -2168,7 +2203,7 @@ fn test() {
 }
 "#),
         @r###"
-[29; 33) 'self': {unknown}
+[29; 33) 'self': Self
 [107; 198) '{     ...(S); }': ()
 [117; 118) 'x': u32
 [126; 127) 'S': S
diff --git a/crates/ra_hir/src/ty/traits.rs b/crates/ra_hir/src/ty/traits.rs
new file mode 100644
index 000000000..f8c3958bd
--- /dev/null
+++ b/crates/ra_hir/src/ty/traits.rs
@@ -0,0 +1,112 @@
+//! Stuff that will probably mostly replaced by Chalk.
+use std::collections::HashMap;
+
+use crate::db::HirDatabase;
+use super::{ TraitRef, Substs, infer::{ TypeVarId, InferTy}, Ty};
+
+// Copied (and simplified) from Chalk
+
+#[derive(Clone, Debug, PartialEq, Eq)]
+/// A (possible) solution for a proposed goal. Usually packaged in a `Result`,
+/// where `Err` represents definite *failure* to prove a goal.
+pub enum Solution {
+    /// The goal indeed holds, and there is a unique value for all existential
+    /// variables.
+    Unique(Substs),
+
+    /// The goal may be provable in multiple ways, but regardless we may have some guidance
+    /// for type inference.
+    Ambig(Guidance),
+}
+
+#[derive(Clone, Debug, PartialEq, Eq)]
+/// When a goal holds ambiguously (e.g., because there are multiple possible
+/// solutions), we issue a set of *guidance* back to type inference.
+pub enum Guidance {
+    /// The existential variables *must* have the given values if the goal is
+    /// ever to hold, but that alone isn't enough to guarantee the goal will
+    /// actually hold.
+    Definite(Substs),
+
+    /// There are multiple plausible values for the existentials, but the ones
+    /// here are suggested as the preferred choice heuristically. These should
+    /// be used for inference fallback only.
+    Suggested(Substs),
+
+    /// There's no useful information to feed back to type inference
+    Unknown,
+}
+
+/// Something that needs to be proven (by Chalk) during type checking, e.g. that
+/// a certain type implements a certain trait. Proving the Obligation might
+/// result in additional information about inference variables.
+///
+/// This might be handled by Chalk when we integrate it?
+#[derive(Clone, Debug, PartialEq, Eq)]
+pub enum Obligation {
+    /// Prove that a certain type implements a trait (the type is the `Self` type
+    /// parameter to the `TraitRef`).
+    Trait(TraitRef),
+}
+
+/// Rudimentary check whether an impl exists for a given type and trait; this
+/// will actually be done by chalk.
+pub(crate) fn implements(db: &impl HirDatabase, trait_ref: TraitRef) -> Option<Solution> {
+    // FIXME use all trait impls in the whole crate graph
+    let krate = trait_ref.trait_.module(db).krate(db);
+    let krate = match krate {
+        Some(krate) => krate,
+        None => return None,
+    };
+    let crate_impl_blocks = db.impls_in_crate(krate);
+    let mut impl_blocks = crate_impl_blocks.lookup_impl_blocks_for_trait(&trait_ref.trait_);
+    impl_blocks
+        .find_map(|impl_block| unify_trait_refs(&trait_ref, &impl_block.target_trait_ref(db)?))
+}
+
+pub(super) fn canonicalize(trait_ref: TraitRef) -> (TraitRef, Vec<TypeVarId>) {
+    let mut canonical = HashMap::new(); // mapping uncanonical -> canonical
+    let mut uncanonical = Vec::new(); // mapping canonical -> uncanonical (which is dense)
+    let mut substs = trait_ref.substs.0.to_vec();
+    for ty in &mut substs {
+        ty.walk_mut(&mut |ty| match ty {
+            Ty::Infer(InferTy::TypeVar(tv)) => {
+                let tv: &mut TypeVarId = tv;
+                *tv = *canonical.entry(*tv).or_insert_with(|| {
+                    let i = uncanonical.len();
+                    uncanonical.push(*tv);
+                    TypeVarId(i as u32)
+                });
+            }
+            _ => {}
+        });
+    }
+    (TraitRef { substs: substs.into(), ..trait_ref }, uncanonical)
+}
+
+fn unify_trait_refs(tr1: &TraitRef, tr2: &TraitRef) -> Option<Solution> {
+    if tr1.trait_ != tr2.trait_ {
+        return None;
+    }
+    let mut solution_substs = Vec::new();
+    for (t1, t2) in tr1.substs.0.iter().zip(tr2.substs.0.iter()) {
+        // this is very bad / hacky 'unification' logic, just enough to make the simple tests pass
+        match (t1, t2) {
+            (_, Ty::Infer(InferTy::TypeVar(_))) | (_, Ty::Unknown) | (_, Ty::Param { .. }) => {
+                // type variable (or similar) in the impl, we just assume it works
+            }
+            (Ty::Infer(InferTy::TypeVar(v1)), _) => {
+                // type variable in the query and fixed type in the impl, record its value
+                solution_substs.resize_with(v1.0 as usize + 1, || Ty::Unknown);
+                solution_substs[v1.0 as usize] = t2.clone();
+            }
+            _ => {
+                // check that they're equal (actually we'd have to recurse etc.)
+                if t1 != t2 {
+                    return None;
+                }
+            }
+        }
+    }
+    Some(Solution::Unique(solution_substs.into()))
+}