13 files changed, 583 insertions, 221 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()))
+}
diff --git a/crates/ra_ide_api/src/goto_definition.rs b/crates/ra_ide_api/src/goto_definition.rs
index 517dffbca..40a2bd148 100644
--- a/crates/ra_ide_api/src/goto_definition.rs
+++ b/crates/ra_ide_api/src/goto_definition.rs
@@ -104,7 +104,7 @@ pub(crate) fn reference_definition(
                     }
                 }
                 hir::PathResolution::AssocItem(assoc) => {
-                    return Exact(NavigationTarget::from_impl_item(db, assoc))
+                    return Exact(NavigationTarget::from_impl_item(db, assoc));
                 }
             }
         }