9 files changed, 570 insertions, 340 deletions
diff --git a/crates/ra_hir_ty/src/infer.rs b/crates/ra_hir_ty/src/infer.rs
index fe259371f..d16f1eb46 100644
--- a/crates/ra_hir_ty/src/infer.rs
+++ b/crates/ra_hir_ty/src/infer.rs
@@ -18,7 +18,6 @@ use std::mem;
 use std::ops::Index;
 use std::sync::Arc;
-use ena::unify::{InPlaceUnificationTable, NoError, UnifyKey, UnifyValue};
 use rustc_hash::FxHashMap;
 use hir_def::{
@@ -33,16 +32,17 @@ use hir_def::{
 use hir_expand::{diagnostics::DiagnosticSink, name};
 use ra_arena::map::ArenaMap;
 use ra_prof::profile;
-use test_utils::tested_by;
 use super::{
    primitive::{FloatTy, IntTy},
    traits::{Guidance, Obligation, ProjectionPredicate, Solution},
-    ApplicationTy, InEnvironment, ProjectionTy, Substs, TraitEnvironment, TraitRef, Ty, TypeCtor,
+    ApplicationTy, InEnvironment, ProjectionTy, TraitEnvironment, TraitRef, Ty, TypeCtor, TypeWalk,
-    TypeWalk, Uncertain,
+    Uncertain,
 };
 use crate::{db::HirDatabase, infer::diagnostics::InferenceDiagnostic};
+pub(crate) use unify::unify;
 macro_rules! ty_app {
    ($ctor:pat, $param:pat) => {
        crate::Ty::Apply(crate::ApplicationTy { ctor: $ctor, parameters: $param })
@@ -191,7 +191,7 @@ struct InferenceContext<'a, D: HirDatabase> {
    owner: DefWithBodyId,
    body: Arc<Body>,
    resolver: Resolver,
-    var_unification_table: InPlaceUnificationTable<TypeVarId>,
+    table: unify::InferenceTable,
    trait_env: Arc<TraitEnvironment>,
    obligations: Vec<Obligation>,
    result: InferenceResult,
@@ -209,7 +209,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
    fn new(db: &'a D, owner: DefWithBodyId, resolver: Resolver) -> Self {
        InferenceContext {
            result: InferenceResult::default(),
-            var_unification_table: InPlaceUnificationTable::new(),
+            table: unify::InferenceTable::new(),
            obligations: Vec::default(),
            return_ty: Ty::Unknown, // set in collect_fn_signature
            trait_env: TraitEnvironment::lower(db, &resolver),
@@ -224,13 +224,12 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
    fn resolve_all(mut self) -> InferenceResult {
        // FIXME resolve obligations as well (use Guidance if necessary)
        let mut result = mem::replace(&mut self.result, InferenceResult::default());
-        let mut tv_stack = Vec::new();
        for ty in result.type_of_expr.values_mut() {
-            let resolved = self.resolve_ty_completely(&mut tv_stack, mem::replace(ty, Ty::Unknown));
+            let resolved = self.table.resolve_ty_completely(mem::replace(ty, Ty::Unknown));
            *ty = resolved;
        }
        for ty in result.type_of_pat.values_mut() {
-            let resolved = self.resolve_ty_completely(&mut tv_stack, mem::replace(ty, Ty::Unknown));
+            let resolved = self.table.resolve_ty_completely(mem::replace(ty, Ty::Unknown));
            *ty = resolved;
        }
        result
@@ -275,96 +274,15 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
        self.normalize_associated_types_in(ty)
    }
-    fn unify_substs(&mut self, substs1: &Substs, substs2: &Substs, depth: usize) -> bool {
-        substs1.0.iter().zip(substs2.0.iter()).all(|(t1, t2)| self.unify_inner(t1, t2, depth))
-    }
-    fn unify(&mut self, ty1: &Ty, ty2: &Ty) -> bool {
-        self.unify_inner(ty1, ty2, 0)
-    }
-    fn unify_inner(&mut self, ty1: &Ty, ty2: &Ty, depth: usize) -> bool {
-        if depth > 1000 {
-            // prevent stackoverflows
-            panic!("infinite recursion in unification");
-        }
-        if ty1 == ty2 {
-            return true;
-        }
-        // try to resolve type vars first
-        let ty1 = self.resolve_ty_shallow(ty1);
-        let ty2 = self.resolve_ty_shallow(ty2);
-        match (&*ty1, &*ty2) {
-            (Ty::Apply(a_ty1), Ty::Apply(a_ty2)) if a_ty1.ctor == a_ty2.ctor => {
-                self.unify_substs(&a_ty1.parameters, &a_ty2.parameters, depth + 1)
-            }
-            _ => self.unify_inner_trivial(&ty1, &ty2),
-        }
-    }
-    fn unify_inner_trivial(&mut self, ty1: &Ty, ty2: &Ty) -> bool {
-        match (ty1, ty2) {
-            (Ty::Unknown, _) | (_, Ty::Unknown) => true,
-            (Ty::Infer(InferTy::TypeVar(tv1)), Ty::Infer(InferTy::TypeVar(tv2)))
-            | (Ty::Infer(InferTy::IntVar(tv1)), Ty::Infer(InferTy::IntVar(tv2)))
-            | (Ty::Infer(InferTy::FloatVar(tv1)), Ty::Infer(InferTy::FloatVar(tv2)))
-            | (
-                Ty::Infer(InferTy::MaybeNeverTypeVar(tv1)),
-                Ty::Infer(InferTy::MaybeNeverTypeVar(tv2)),
-            ) => {
-                // both type vars are unknown since we tried to resolve them
-                self.var_unification_table.union(*tv1, *tv2);
-                true
-            }
-            // The order of MaybeNeverTypeVar matters here.
-            // Unifying MaybeNeverTypeVar and TypeVar will let the latter become MaybeNeverTypeVar.
-            // Unifying MaybeNeverTypeVar and other concrete type will let the former become it.
-            (Ty::Infer(InferTy::TypeVar(tv)), other)
-            | (other, Ty::Infer(InferTy::TypeVar(tv)))
-            | (Ty::Infer(InferTy::MaybeNeverTypeVar(tv)), other)
-            | (other, Ty::Infer(InferTy::MaybeNeverTypeVar(tv)))
-            | (Ty::Infer(InferTy::IntVar(tv)), other @ ty_app!(TypeCtor::Int(_)))
-            | (other @ ty_app!(TypeCtor::Int(_)), Ty::Infer(InferTy::IntVar(tv)))
-            | (Ty::Infer(InferTy::FloatVar(tv)), other @ ty_app!(TypeCtor::Float(_)))
-            | (other @ ty_app!(TypeCtor::Float(_)), Ty::Infer(InferTy::FloatVar(tv))) => {
-                // the type var is unknown since we tried to resolve it
-                self.var_unification_table.union_value(*tv, TypeVarValue::Known(other.clone()));
-                true
-            }
-            _ => false,
-        }
-    }
-    fn new_type_var(&mut self) -> Ty {
-        Ty::Infer(InferTy::TypeVar(self.var_unification_table.new_key(TypeVarValue::Unknown)))
-    }
-    fn new_integer_var(&mut self) -> Ty {
-        Ty::Infer(InferTy::IntVar(self.var_unification_table.new_key(TypeVarValue::Unknown)))
-    }
-    fn new_float_var(&mut self) -> Ty {
-        Ty::Infer(InferTy::FloatVar(self.var_unification_table.new_key(TypeVarValue::Unknown)))
-    }
-    fn new_maybe_never_type_var(&mut self) -> Ty {
-        Ty::Infer(InferTy::MaybeNeverTypeVar(
-            self.var_unification_table.new_key(TypeVarValue::Unknown),
-        ))
-    }
    /// Replaces Ty::Unknown by a new type var, so we can maybe still infer it.
    fn insert_type_vars_shallow(&mut self, ty: Ty) -> Ty {
        match ty {
-            Ty::Unknown => self.new_type_var(),
+            Ty::Unknown => self.table.new_type_var(),
            Ty::Apply(ApplicationTy { ctor: TypeCtor::Int(Uncertain::Unknown), .. }) => {
-                self.new_integer_var()
+                self.table.new_integer_var()
            }
            Ty::Apply(ApplicationTy { ctor: TypeCtor::Float(Uncertain::Unknown), .. }) => {
-                self.new_float_var()
+                self.table.new_float_var()
            }
            _ => ty,
        }
@@ -402,64 +320,22 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
        }
    }
+    fn unify(&mut self, ty1: &Ty, ty2: &Ty) -> bool {
+        self.table.unify(ty1, ty2)
+    }
    /// 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 {
+    fn resolve_ty_as_possible(&mut self, ty: Ty) -> Ty {
        self.resolve_obligations_as_possible();
-        ty.fold(&mut |ty| match ty {
+        self.table.resolve_ty_as_possible(ty)
-            Ty::Infer(tv) => {
-                let inner = tv.to_inner();
-                if tv_stack.contains(&inner) {
-                    tested_by!(type_var_cycles_resolve_as_possible);
-                    // recursive type
-                    return tv.fallback_value();
-                }
-                if let Some(known_ty) =
-                    self.var_unification_table.inlined_probe_value(inner).known()
-                {
-                    // known_ty may contain other variables that are known by now
-                    tv_stack.push(inner);
-                    let result = self.resolve_ty_as_possible(tv_stack, known_ty.clone());
-                    tv_stack.pop();
-                    result
-                } else {
-                    ty
-                }
-            }
-            _ => ty,
-        })
    }
-    /// If `ty` is a type variable with known type, returns that type;
-    /// otherwise, return ty.
    fn resolve_ty_shallow<'b>(&mut self, ty: &'b Ty) -> Cow<'b, Ty> {
-        let mut ty = Cow::Borrowed(ty);
+        self.table.resolve_ty_shallow(ty)
-        // The type variable could resolve to a int/float variable. Hence try
-        // resolving up to three times; each type of variable shouldn't occur
-        // more than once
-        for i in 0..3 {
-            if i > 0 {
-                tested_by!(type_var_resolves_to_int_var);
-            }
-            match &*ty {
-                Ty::Infer(tv) => {
-                    let inner = tv.to_inner();
-                    match self.var_unification_table.inlined_probe_value(inner).known() {
-                        Some(known_ty) => {
-                            // The known_ty can't be a type var itself
-                            ty = Cow::Owned(known_ty.clone());
-                        }
-                        _ => return ty,
-                    }
-                }
-                _ => return ty,
-            }
-        }
-        log::error!("Inference variable still not resolved: {:?}", ty);
-        ty
    }
    /// Recurses through the given type, normalizing associated types mentioned
@@ -469,7 +345,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
    /// call). `make_ty` handles this already, but e.g. for field types we need
    /// to do it as well.
    fn normalize_associated_types_in(&mut self, ty: Ty) -> Ty {
-        let ty = self.resolve_ty_as_possible(&mut vec![], ty);
+        let ty = self.resolve_ty_as_possible(ty);
        ty.fold(&mut |ty| match ty {
            Ty::Projection(proj_ty) => self.normalize_projection_ty(proj_ty),
            _ => ty,
@@ -477,40 +353,13 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
    }
    fn normalize_projection_ty(&mut self, proj_ty: ProjectionTy) -> Ty {
-        let var = self.new_type_var();
+        let var = self.table.new_type_var();
        let predicate = ProjectionPredicate { projection_ty: proj_ty, ty: var.clone() };
        let obligation = Obligation::Projection(predicate);
        self.obligations.push(obligation);
        var
    }
-    /// Resolves the type completely; type variables without known type are
-    /// replaced by Ty::Unknown.
-    fn resolve_ty_completely(&mut self, tv_stack: &mut Vec<TypeVarId>, ty: Ty) -> Ty {
-        ty.fold(&mut |ty| match ty {
-            Ty::Infer(tv) => {
-                let inner = tv.to_inner();
-                if tv_stack.contains(&inner) {
-                    tested_by!(type_var_cycles_resolve_completely);
-                    // recursive type
-                    return tv.fallback_value();
-                }
-                if let Some(known_ty) =
-                    self.var_unification_table.inlined_probe_value(inner).known()
-                {
-                    // known_ty may contain other variables that are known by now
-                    tv_stack.push(inner);
-                    let result = self.resolve_ty_completely(tv_stack, known_ty.clone());
-                    tv_stack.pop();
-                    result
-                } else {
-                    tv.fallback_value()
-                }
-            }
-            _ => ty,
-        })
-    }
    fn resolve_variant(&mut self, path: Option<&Path>) -> (Ty, Option<VariantId>) {
        let path = match path {
            Some(path) => path,
@@ -615,78 +464,20 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
    }
 }
-/// The ID of a type variable.
-#[derive(Copy, Clone, PartialEq, Eq, Hash, Debug)]
-pub struct TypeVarId(pub(super) u32);
-impl UnifyKey for TypeVarId {
-    type Value = TypeVarValue;
-    fn index(&self) -> u32 {
-        self.0
-    }
-    fn from_index(i: u32) -> Self {
-        TypeVarId(i)
-    }
-    fn tag() -> &'static str {
-        "TypeVarId"
-    }
-}
-/// The value of a type variable: either we already know the type, or we don't
-/// know it yet.
-#[derive(Clone, PartialEq, Eq, Debug)]
-pub enum TypeVarValue {
-    Known(Ty),
-    Unknown,
-}
-impl TypeVarValue {
-    fn known(&self) -> Option<&Ty> {
-        match self {
-            TypeVarValue::Known(ty) => Some(ty),
-            TypeVarValue::Unknown => None,
-        }
-    }
-}
-impl UnifyValue for TypeVarValue {
-    type Error = NoError;
-    fn unify_values(value1: &Self, value2: &Self) -> Result<Self, NoError> {
-        match (value1, value2) {
-            // We should never equate two type variables, both of which have
-            // known types. Instead, we recursively equate those types.
-            (TypeVarValue::Known(t1), TypeVarValue::Known(t2)) => panic!(
-                "equating two type variables, both of which have known types: {:?} and {:?}",
-                t1, t2
-            ),
-            // If one side is known, prefer that one.
-            (TypeVarValue::Known(..), TypeVarValue::Unknown) => Ok(value1.clone()),
-            (TypeVarValue::Unknown, TypeVarValue::Known(..)) => Ok(value2.clone()),
-            (TypeVarValue::Unknown, TypeVarValue::Unknown) => Ok(TypeVarValue::Unknown),
-        }
-    }
-}
 /// The kinds of placeholders we need during type inference. There's separate
 /// values for general types, and for integer and float variables. The latter
 /// two are used for inference of literal values (e.g. `100` could be one of
 /// several integer types).
 #[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
 pub enum InferTy {
-    TypeVar(TypeVarId),
+    TypeVar(unify::TypeVarId),
-    IntVar(TypeVarId),
+    IntVar(unify::TypeVarId),
-    FloatVar(TypeVarId),
+    FloatVar(unify::TypeVarId),
-    MaybeNeverTypeVar(TypeVarId),
+    MaybeNeverTypeVar(unify::TypeVarId),
 }
 impl InferTy {
-    fn to_inner(self) -> TypeVarId {
+    fn to_inner(self) -> unify::TypeVarId {
        match self {
            InferTy::TypeVar(ty)
            | InferTy::IntVar(ty)
diff --git a/crates/ra_hir_ty/src/infer/coerce.rs b/crates/ra_hir_ty/src/infer/coerce.rs
index 064993d34..9daa77cfa 100644
--- a/crates/ra_hir_ty/src/infer/coerce.rs
+++ b/crates/ra_hir_ty/src/infer/coerce.rs
@@ -10,7 +10,7 @@ use test_utils::tested_by;
 use crate::{autoderef, db::HirDatabase, Substs, Ty, TypeCtor, TypeWalk};
-use super::{InEnvironment, InferTy, InferenceContext, TypeVarValue};
+use super::{unify::TypeVarValue, InEnvironment, InferTy, InferenceContext};
 impl<'a, D: HirDatabase> InferenceContext<'a, D> {
    /// Unify two types, but may coerce the first one to the second one
@@ -85,8 +85,8 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
        match (&from_ty, to_ty) {
            // Never type will make type variable to fallback to Never Type instead of Unknown.
            (ty_app!(TypeCtor::Never), Ty::Infer(InferTy::TypeVar(tv))) => {
-                let var = self.new_maybe_never_type_var();
+                let var = self.table.new_maybe_never_type_var();
-                self.var_unification_table.union_value(*tv, TypeVarValue::Known(var));
+                self.table.var_unification_table.union_value(*tv, TypeVarValue::Known(var));
                return true;
            }
            (ty_app!(TypeCtor::Never), _) => return true,
@@ -94,7 +94,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
            // Trivial cases, this should go after `never` check to
            // avoid infer result type to be never
            _ => {
-                if self.unify_inner_trivial(&from_ty, &to_ty) {
+                if self.table.unify_inner_trivial(&from_ty, &to_ty) {
                    return true;
                }
            }
@@ -330,7 +330,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
                // Stop when constructor matches.
                (ty_app!(from_ctor, st1), ty_app!(to_ctor, st2)) if from_ctor == to_ctor => {
                    // It will not recurse to `coerce`.
-                    return self.unify_substs(st1, st2, 0);
+                    return self.table.unify_substs(st1, st2, 0);
                }
                _ => {}
            }
diff --git a/crates/ra_hir_ty/src/infer/expr.rs b/crates/ra_hir_ty/src/infer/expr.rs
index 4014f4732..1e78f6efd 100644
--- a/crates/ra_hir_ty/src/infer/expr.rs
+++ b/crates/ra_hir_ty/src/infer/expr.rs
@@ -32,7 +32,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
                TypeMismatch { expected: expected.ty.clone(), actual: ty.clone() },
            );
        }
-        let ty = self.resolve_ty_as_possible(&mut vec![], ty);
+        let ty = self.resolve_ty_as_possible(ty);
        ty
    }
@@ -53,7 +53,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
            expected.ty.clone()
        };
-        self.resolve_ty_as_possible(&mut vec![], ty)
+        self.resolve_ty_as_possible(ty)
    }
    fn infer_expr_inner(&mut self, tgt_expr: ExprId, expected: &Expectation) -> Ty {
@@ -94,7 +94,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
                let pat_ty = match self.resolve_into_iter_item() {
                    Some(into_iter_item_alias) => {
-                        let pat_ty = self.new_type_var();
+                        let pat_ty = self.table.new_type_var();
                        let projection = ProjectionPredicate {
                            ty: pat_ty.clone(),
                            projection_ty: ProjectionTy {
@@ -103,7 +103,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
                            },
                        };
                        self.obligations.push(Obligation::Projection(projection));
-                        self.resolve_ty_as_possible(&mut vec![], pat_ty)
+                        self.resolve_ty_as_possible(pat_ty)
                    }
                    None => Ty::Unknown,
                };
@@ -128,7 +128,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
                }
                // add return type
-                let ret_ty = self.new_type_var();
+                let ret_ty = self.table.new_type_var();
                sig_tys.push(ret_ty.clone());
                let sig_ty = Ty::apply(
                    TypeCtor::FnPtr { num_args: sig_tys.len() as u16 - 1 },
@@ -167,7 +167,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
            Expr::Match { expr, arms } => {
                let input_ty = self.infer_expr(*expr, &Expectation::none());
-                let mut result_ty = self.new_maybe_never_type_var();
+                let mut result_ty = self.table.new_maybe_never_type_var();
                for arm in arms {
                    for &pat in &arm.pats {
@@ -283,7 +283,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
                let inner_ty = self.infer_expr(*expr, &Expectation::none());
                let ty = match self.resolve_future_future_output() {
                    Some(future_future_output_alias) => {
-                        let ty = self.new_type_var();
+                        let ty = self.table.new_type_var();
                        let projection = ProjectionPredicate {
                            ty: ty.clone(),
                            projection_ty: ProjectionTy {
@@ -292,7 +292,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
                            },
                        };
                        self.obligations.push(Obligation::Projection(projection));
-                        self.resolve_ty_as_possible(&mut vec![], ty)
+                        self.resolve_ty_as_possible(ty)
                    }
                    None => Ty::Unknown,
                };
@@ -302,7 +302,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
                let inner_ty = self.infer_expr(*expr, &Expectation::none());
                let ty = match self.resolve_ops_try_ok() {
                    Some(ops_try_ok_alias) => {
-                        let ty = self.new_type_var();
+                        let ty = self.table.new_type_var();
                        let projection = ProjectionPredicate {
                            ty: ty.clone(),
                            projection_ty: ProjectionTy {
@@ -311,7 +311,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
                            },
                        };
                        self.obligations.push(Obligation::Projection(projection));
-                        self.resolve_ty_as_possible(&mut vec![], ty)
+                        self.resolve_ty_as_possible(ty)
                    }
                    None => Ty::Unknown,
                };
@@ -465,10 +465,10 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
                    ty_app!(TypeCtor::Tuple { .. }, st) => st
                        .iter()
                        .cloned()
-                        .chain(repeat_with(|| self.new_type_var()))
+                        .chain(repeat_with(|| self.table.new_type_var()))
                        .take(exprs.len())
                        .collect::<Vec<_>>(),
-                    _ => (0..exprs.len()).map(|_| self.new_type_var()).collect(),
+                    _ => (0..exprs.len()).map(|_| self.table.new_type_var()).collect(),
                };
                for (expr, ty) in exprs.iter().zip(tys.iter_mut()) {
@@ -482,7 +482,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
                    ty_app!(TypeCtor::Array, st) | ty_app!(TypeCtor::Slice, st) => {
                        st.as_single().clone()
                    }
-                    _ => self.new_type_var(),
+                    _ => self.table.new_type_var(),
                };
                match array {
@@ -524,7 +524,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
        };
        // use a new type variable if we got Ty::Unknown here
        let ty = self.insert_type_vars_shallow(ty);
-        let ty = self.resolve_ty_as_possible(&mut vec![], ty);
+        let ty = self.resolve_ty_as_possible(ty);
        self.write_expr_ty(tgt_expr, ty.clone());
        ty
    }
@@ -553,7 +553,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
                        }
                    }
-                    let ty = self.resolve_ty_as_possible(&mut vec![], ty);
+                    let ty = self.resolve_ty_as_possible(ty);
                    self.infer_pat(*pat, &ty, BindingMode::default());
                }
                Statement::Expr(expr) => {
diff --git a/crates/ra_hir_ty/src/infer/pat.rs b/crates/ra_hir_ty/src/infer/pat.rs
index 1ebb36239..a14662884 100644
--- a/crates/ra_hir_ty/src/infer/pat.rs
+++ b/crates/ra_hir_ty/src/infer/pat.rs
@@ -170,7 +170,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
                    }
                    BindingMode::Move => inner_ty.clone(),
                };
-                let bound_ty = self.resolve_ty_as_possible(&mut vec![], bound_ty);
+                let bound_ty = self.resolve_ty_as_possible(bound_ty);
                self.write_pat_ty(pat, bound_ty);
                return inner_ty;
            }
@@ -179,7 +179,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
        // use a new type variable if we got Ty::Unknown here
        let ty = self.insert_type_vars_shallow(ty);
        self.unify(&ty, expected);
-        let ty = self.resolve_ty_as_possible(&mut vec![], ty);
+        let ty = self.resolve_ty_as_possible(ty);
        self.write_pat_ty(pat, ty.clone());
        ty
    }
diff --git a/crates/ra_hir_ty/src/infer/path.rs b/crates/ra_hir_ty/src/infer/path.rs
index bbf146418..b0024c6e1 100644
--- a/crates/ra_hir_ty/src/infer/path.rs
+++ b/crates/ra_hir_ty/src/infer/path.rs
@@ -57,7 +57,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
        let typable: ValueTyDefId = match value {
            ValueNs::LocalBinding(pat) => {
                let ty = self.result.type_of_pat.get(pat)?.clone();
-                let ty = self.resolve_ty_as_possible(&mut vec![], ty);
+                let ty = self.resolve_ty_as_possible(ty);
                return Some(ty);
            }
            ValueNs::FunctionId(it) => it.into(),
@@ -206,12 +206,14 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
                    AssocItemId::TypeAliasId(_) => unreachable!(),
                };
                let substs = match container {
-                    ContainerId::ImplId(_) => self.find_self_types(&def, ty.clone()),
+                    ContainerId::ImplId(impl_id) => {
+                        method_resolution::inherent_impl_substs(self.db, impl_id, &ty)
+                    }
                    ContainerId::TraitId(trait_) => {
                        // we're picking this method
                        let trait_substs = Substs::build_for_def(self.db, trait_)
                            .push(ty.clone())
-                            .fill(std::iter::repeat_with(|| self.new_type_var()))
+                            .fill(std::iter::repeat_with(|| self.table.new_type_var()))
                            .build();
                        let substs = Substs::build_for_def(self.db, item)
                            .use_parent_substs(&trait_substs)
@@ -231,38 +233,4 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
            },
        )
    }
-    fn find_self_types(&self, def: &ValueNs, actual_def_ty: Ty) -> Option<Substs> {
-        if let ValueNs::FunctionId(func) = *def {
-            // We only do the infer if parent has generic params
-            let gen = self.db.generic_params(func.into());
-            if gen.count_parent_params() == 0 {
-                return None;
-            }
-            let impl_id = match func.lookup(self.db).container {
-                ContainerId::ImplId(it) => it,
-                _ => return None,
-            };
-            let self_ty = self.db.impl_self_ty(impl_id).clone();
-            let self_ty_substs = self_ty.substs()?;
-            let actual_substs = actual_def_ty.substs()?;
-            let mut new_substs = vec![Ty::Unknown; gen.count_parent_params()];
-            // The following code *link up* the function actual parma type
-            // and impl_block type param index
-            self_ty_substs.iter().zip(actual_substs.iter()).for_each(|(param, pty)| {
-                if let Ty::Param { idx, .. } = param {
-                    if let Some(s) = new_substs.get_mut(*idx as usize) {
-                        *s = pty.clone();
-                    }
-                }
-            });
-            Some(Substs(new_substs.into()))
-        } else {
-            None
-        }
-    }
 }
diff --git a/crates/ra_hir_ty/src/infer/unify.rs b/crates/ra_hir_ty/src/infer/unify.rs
index f3a875678..8ed2a6090 100644
--- a/crates/ra_hir_ty/src/infer/unify.rs
+++ b/crates/ra_hir_ty/src/infer/unify.rs
@@ -1,9 +1,15 @@
 //! Unification and canonicalization logic.
+use std::borrow::Cow;
+use ena::unify::{InPlaceUnificationTable, NoError, UnifyKey, UnifyValue};
+use test_utils::tested_by;
 use super::{InferenceContext, Obligation};
 use crate::{
    db::HirDatabase, utils::make_mut_slice, Canonical, InEnvironment, InferTy, ProjectionPredicate,
-    ProjectionTy, Substs, TraitRef, Ty, TypeWalk,
+    ProjectionTy, Substs, TraitRef, Ty, TypeCtor, TypeWalk,
 };
 impl<'a, D: HirDatabase> InferenceContext<'a, D> {
@@ -24,7 +30,7 @@ where
    /// A stack of type variables that is used to detect recursive types (which
    /// are an error, but we need to protect against them to avoid stack
    /// overflows).
-    var_stack: Vec<super::TypeVarId>,
+    var_stack: Vec<TypeVarId>,
 }
 pub(super) struct Canonicalized<T> {
@@ -53,14 +59,14 @@ where
                    return tv.fallback_value();
                }
                if let Some(known_ty) =
-                    self.ctx.var_unification_table.inlined_probe_value(inner).known()
+                    self.ctx.table.var_unification_table.inlined_probe_value(inner).known()
                {
                    self.var_stack.push(inner);
                    let result = self.do_canonicalize_ty(known_ty.clone());
                    self.var_stack.pop();
                    result
                } else {
-                    let root = self.ctx.var_unification_table.find(inner);
+                    let root = self.ctx.table.var_unification_table.find(inner);
                    let free_var = match tv {
                        InferTy::TypeVar(_) => InferTy::TypeVar(root),
                        InferTy::IntVar(_) => InferTy::IntVar(root),
@@ -153,10 +159,268 @@ impl<T> Canonicalized<T> {
        solution: Canonical<Vec<Ty>>,
    ) {
        // the solution may contain new variables, which we need to convert to new inference vars
-        let new_vars = Substs((0..solution.num_vars).map(|_| ctx.new_type_var()).collect());
+        let new_vars = Substs((0..solution.num_vars).map(|_| ctx.table.new_type_var()).collect());
        for (i, ty) in solution.value.into_iter().enumerate() {
            let var = self.free_vars[i];
-            ctx.unify(&Ty::Infer(var), &ty.subst_bound_vars(&new_vars));
+            ctx.table.unify(&Ty::Infer(var), &ty.subst_bound_vars(&new_vars));
+        }
+    }
+}
+pub fn unify(ty1: Canonical<&Ty>, ty2: &Ty) -> Option<Substs> {
+    let mut table = InferenceTable::new();
+    let vars =
+        Substs::builder(ty1.num_vars).fill(std::iter::repeat_with(|| table.new_type_var())).build();
+    let ty_with_vars = ty1.value.clone().subst_bound_vars(&vars);
+    if !table.unify(&ty_with_vars, ty2) {
+        return None;
+    }
+    Some(
+        Substs::builder(ty1.num_vars)
+            .fill(vars.iter().map(|v| table.resolve_ty_completely(v.clone())))
+            .build(),
+    )
+}
+#[derive(Clone, Debug)]
+pub(crate) struct InferenceTable {
+    pub(super) var_unification_table: InPlaceUnificationTable<TypeVarId>,
+}
+impl InferenceTable {
+    pub fn new() -> Self {
+        InferenceTable { var_unification_table: InPlaceUnificationTable::new() }
+    }
+    pub fn new_type_var(&mut self) -> Ty {
+        Ty::Infer(InferTy::TypeVar(self.var_unification_table.new_key(TypeVarValue::Unknown)))
+    }
+    pub fn new_integer_var(&mut self) -> Ty {
+        Ty::Infer(InferTy::IntVar(self.var_unification_table.new_key(TypeVarValue::Unknown)))
+    }
+    pub fn new_float_var(&mut self) -> Ty {
+        Ty::Infer(InferTy::FloatVar(self.var_unification_table.new_key(TypeVarValue::Unknown)))
+    }
+    pub fn new_maybe_never_type_var(&mut self) -> Ty {
+        Ty::Infer(InferTy::MaybeNeverTypeVar(
+            self.var_unification_table.new_key(TypeVarValue::Unknown),
+        ))
+    }
+    pub fn resolve_ty_completely(&mut self, ty: Ty) -> Ty {
+        self.resolve_ty_completely_inner(&mut Vec::new(), ty)
+    }
+    pub fn resolve_ty_as_possible(&mut self, ty: Ty) -> Ty {
+        self.resolve_ty_as_possible_inner(&mut Vec::new(), ty)
+    }
+    pub fn unify(&mut self, ty1: &Ty, ty2: &Ty) -> bool {
+        self.unify_inner(ty1, ty2, 0)
+    }
+    pub fn unify_substs(&mut self, substs1: &Substs, substs2: &Substs, depth: usize) -> bool {
+        substs1.0.iter().zip(substs2.0.iter()).all(|(t1, t2)| self.unify_inner(t1, t2, depth))
+    }
+    fn unify_inner(&mut self, ty1: &Ty, ty2: &Ty, depth: usize) -> bool {
+        if depth > 1000 {
+            // prevent stackoverflows
+            panic!("infinite recursion in unification");
+        }
+        if ty1 == ty2 {
+            return true;
+        }
+        // try to resolve type vars first
+        let ty1 = self.resolve_ty_shallow(ty1);
+        let ty2 = self.resolve_ty_shallow(ty2);
+        match (&*ty1, &*ty2) {
+            (Ty::Apply(a_ty1), Ty::Apply(a_ty2)) if a_ty1.ctor == a_ty2.ctor => {
+                self.unify_substs(&a_ty1.parameters, &a_ty2.parameters, depth + 1)
+            }
+            _ => self.unify_inner_trivial(&ty1, &ty2),
+        }
+    }
+    pub(super) fn unify_inner_trivial(&mut self, ty1: &Ty, ty2: &Ty) -> bool {
+        match (ty1, ty2) {
+            (Ty::Unknown, _) | (_, Ty::Unknown) => true,
+            (Ty::Infer(InferTy::TypeVar(tv1)), Ty::Infer(InferTy::TypeVar(tv2)))
+            | (Ty::Infer(InferTy::IntVar(tv1)), Ty::Infer(InferTy::IntVar(tv2)))
+            | (Ty::Infer(InferTy::FloatVar(tv1)), Ty::Infer(InferTy::FloatVar(tv2)))
+            | (
+                Ty::Infer(InferTy::MaybeNeverTypeVar(tv1)),
+                Ty::Infer(InferTy::MaybeNeverTypeVar(tv2)),
+            ) => {
+                // both type vars are unknown since we tried to resolve them
+                self.var_unification_table.union(*tv1, *tv2);
+                true
+            }
+            // The order of MaybeNeverTypeVar matters here.
+            // Unifying MaybeNeverTypeVar and TypeVar will let the latter become MaybeNeverTypeVar.
+            // Unifying MaybeNeverTypeVar and other concrete type will let the former become it.
+            (Ty::Infer(InferTy::TypeVar(tv)), other)
+            | (other, Ty::Infer(InferTy::TypeVar(tv)))
+            | (Ty::Infer(InferTy::MaybeNeverTypeVar(tv)), other)
+            | (other, Ty::Infer(InferTy::MaybeNeverTypeVar(tv)))
+            | (Ty::Infer(InferTy::IntVar(tv)), other @ ty_app!(TypeCtor::Int(_)))
+            | (other @ ty_app!(TypeCtor::Int(_)), Ty::Infer(InferTy::IntVar(tv)))
+            | (Ty::Infer(InferTy::FloatVar(tv)), other @ ty_app!(TypeCtor::Float(_)))
+            | (other @ ty_app!(TypeCtor::Float(_)), Ty::Infer(InferTy::FloatVar(tv))) => {
+                // the type var is unknown since we tried to resolve it
+                self.var_unification_table.union_value(*tv, TypeVarValue::Known(other.clone()));
+                true
+            }
+            _ => false,
+        }
+    }
+    /// If `ty` is a type variable with known type, returns that type;
+    /// otherwise, return ty.
+    pub fn resolve_ty_shallow<'b>(&mut self, ty: &'b Ty) -> Cow<'b, Ty> {
+        let mut ty = Cow::Borrowed(ty);
+        // The type variable could resolve to a int/float variable. Hence try
+        // resolving up to three times; each type of variable shouldn't occur
+        // more than once
+        for i in 0..3 {
+            if i > 0 {
+                tested_by!(type_var_resolves_to_int_var);
+            }
+            match &*ty {
+                Ty::Infer(tv) => {
+                    let inner = tv.to_inner();
+                    match self.var_unification_table.inlined_probe_value(inner).known() {
+                        Some(known_ty) => {
+                            // The known_ty can't be a type var itself
+                            ty = Cow::Owned(known_ty.clone());
+                        }
+                        _ => return ty,
+                    }
+                }
+                _ => return ty,
+            }
+        }
+        log::error!("Inference variable still not resolved: {:?}", ty);
+        ty
+    }
+    /// 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_inner(&mut self, tv_stack: &mut Vec<TypeVarId>, ty: Ty) -> Ty {
+        ty.fold(&mut |ty| match ty {
+            Ty::Infer(tv) => {
+                let inner = tv.to_inner();
+                if tv_stack.contains(&inner) {
+                    tested_by!(type_var_cycles_resolve_as_possible);
+                    // recursive type
+                    return tv.fallback_value();
+                }
+                if let Some(known_ty) =
+                    self.var_unification_table.inlined_probe_value(inner).known()
+                {
+                    // known_ty may contain other variables that are known by now
+                    tv_stack.push(inner);
+                    let result = self.resolve_ty_as_possible_inner(tv_stack, known_ty.clone());
+                    tv_stack.pop();
+                    result
+                } else {
+                    ty
+                }
+            }
+            _ => ty,
+        })
+    }
+    /// Resolves the type completely; type variables without known type are
+    /// replaced by Ty::Unknown.
+    fn resolve_ty_completely_inner(&mut self, tv_stack: &mut Vec<TypeVarId>, ty: Ty) -> Ty {
+        ty.fold(&mut |ty| match ty {
+            Ty::Infer(tv) => {
+                let inner = tv.to_inner();
+                if tv_stack.contains(&inner) {
+                    tested_by!(type_var_cycles_resolve_completely);
+                    // recursive type
+                    return tv.fallback_value();
+                }
+                if let Some(known_ty) =
+                    self.var_unification_table.inlined_probe_value(inner).known()
+                {
+                    // known_ty may contain other variables that are known by now
+                    tv_stack.push(inner);
+                    let result = self.resolve_ty_completely_inner(tv_stack, known_ty.clone());
+                    tv_stack.pop();
+                    result
+                } else {
+                    tv.fallback_value()
+                }
+            }
+            _ => ty,
+        })
+    }
+}
+/// The ID of a type variable.
+#[derive(Copy, Clone, PartialEq, Eq, Hash, Debug)]
+pub struct TypeVarId(pub(super) u32);
+impl UnifyKey for TypeVarId {
+    type Value = TypeVarValue;
+    fn index(&self) -> u32 {
+        self.0
+    }
+    fn from_index(i: u32) -> Self {
+        TypeVarId(i)
+    }
+    fn tag() -> &'static str {
+        "TypeVarId"
+    }
+}
+/// The value of a type variable: either we already know the type, or we don't
+/// know it yet.
+#[derive(Clone, PartialEq, Eq, Debug)]
+pub enum TypeVarValue {
+    Known(Ty),
+    Unknown,
+}
+impl TypeVarValue {
+    fn known(&self) -> Option<&Ty> {
+        match self {
+            TypeVarValue::Known(ty) => Some(ty),
+            TypeVarValue::Unknown => None,
+        }
+    }
+}
+impl UnifyValue for TypeVarValue {
+    type Error = NoError;
+    fn unify_values(value1: &Self, value2: &Self) -> Result<Self, NoError> {
+        match (value1, value2) {
+            // We should never equate two type variables, both of which have
+            // known types. Instead, we recursively equate those types.
+            (TypeVarValue::Known(t1), TypeVarValue::Known(t2)) => panic!(
+                "equating two type variables, both of which have known types: {:?} and {:?}",
+                t1, t2
+            ),
+            // If one side is known, prefer that one.
+            (TypeVarValue::Known(..), TypeVarValue::Unknown) => Ok(value1.clone()),
+            (TypeVarValue::Unknown, TypeVarValue::Known(..)) => Ok(value2.clone()),
+            (TypeVarValue::Unknown, TypeVarValue::Unknown) => Ok(TypeVarValue::Unknown),
        }
    }
 }
diff --git a/crates/ra_hir_ty/src/method_resolution.rs b/crates/ra_hir_ty/src/method_resolution.rs
index 2bded3dbd..21efb196a 100644
--- a/crates/ra_hir_ty/src/method_resolution.rs
+++ b/crates/ra_hir_ty/src/method_resolution.rs
@@ -7,19 +7,20 @@ use std::sync::Arc;
 use arrayvec::ArrayVec;
 use hir_def::{
    lang_item::LangItemTarget, resolver::Resolver, type_ref::Mutability, AssocItemId, AstItemDef,
-    FunctionId, HasModule, ImplId, TraitId,
+    FunctionId, HasModule, ImplId, Lookup, TraitId,
 };
 use hir_expand::name::Name;
 use ra_db::CrateId;
 use ra_prof::profile;
 use rustc_hash::FxHashMap;
+use super::Substs;
 use crate::{
    autoderef,
    db::HirDatabase,
    primitive::{FloatBitness, Uncertain},
    utils::all_super_traits,
-    Canonical, InEnvironment, TraitEnvironment, TraitRef, Ty, TypeCtor,
+    Canonical, InEnvironment, TraitEnvironment, TraitRef, Ty, TypeCtor, TypeWalk,
 };
 /// This is used as a key for indexing impls.
@@ -176,7 +177,6 @@ pub fn iterate_method_candidates<T>(
    mode: LookupMode,
    mut callback: impl FnMut(&Ty, AssocItemId) -> Option<T>,
 ) -> Option<T> {
-    let krate = resolver.krate()?;
    match mode {
        LookupMode::MethodCall => {
            // For method calls, rust first does any number of autoderef, and then one
@@ -189,57 +189,159 @@ pub fn iterate_method_candidates<T>(
            // rustc does an autoderef and then autoref again).
            let environment = TraitEnvironment::lower(db, resolver);
            let ty = InEnvironment { value: ty.clone(), environment };
-            for derefed_ty in autoderef::autoderef(db, resolver.krate(), ty) {
+            let krate = resolver.krate()?;
-                if let Some(result) =
-                    iterate_inherent_methods(&derefed_ty, db, name, mode, krate, &mut callback)
+            // We have to be careful about the order we're looking at candidates
-                {
+            // in here. Consider the case where we're resolving `x.clone()`
-                    return Some(result);
+            // where `x: &Vec<_>`. This resolves to the clone method with self
-                }
+            // type `Vec<_>`, *not* `&_`. I.e. we need to consider methods where
-                if let Some(result) = iterate_trait_method_candidates(
+            // the receiver type exactly matches before cases where we have to
-                    &derefed_ty,
+            // do autoref. But in the autoderef steps, the `&_` self type comes
+            // up *before* the `Vec<_>` self type.
+            //
+            // On the other hand, we don't want to just pick any by-value method
+            // before any by-autoref method; it's just that we need to consider
+            // the methods by autoderef order of *receiver types*, not *self
+            // types*.
+            let deref_chain: Vec<_> = autoderef::autoderef(db, Some(krate), ty.clone()).collect();
+            for i in 0..deref_chain.len() {
+                if let Some(result) = iterate_method_candidates_with_autoref(
+                    &deref_chain[i..],
                    db,
                    resolver,
                    name,
-                    mode,
                    &mut callback,
                ) {
                    return Some(result);
                }
            }
+            None
        }
        LookupMode::Path => {
            // No autoderef for path lookups
-            if let Some(result) =
+            iterate_method_candidates_for_self_ty(&ty, db, resolver, name, &mut callback)
-                iterate_inherent_methods(&ty, db, name, mode, krate.into(), &mut callback)
+        }
-            {
+    }
-                return Some(result);
+}
-            }
-            if let Some(result) =
+fn iterate_method_candidates_with_autoref<T>(
-                iterate_trait_method_candidates(&ty, db, resolver, name, mode, &mut callback)
+    deref_chain: &[Canonical<Ty>],
-            {
+    db: &impl HirDatabase,
-                return Some(result);
+    resolver: &Resolver,
-            }
+    name: Option<&Name>,
+    mut callback: impl FnMut(&Ty, AssocItemId) -> Option<T>,
+) -> Option<T> {
+    if let Some(result) = iterate_method_candidates_by_receiver(
+        &deref_chain[0],
+        &deref_chain[1..],
+        db,
+        resolver,
+        name,
+        &mut callback,
+    ) {
+        return Some(result);
+    }
+    let refed = Canonical {
+        num_vars: deref_chain[0].num_vars,
+        value: Ty::apply_one(TypeCtor::Ref(Mutability::Shared), deref_chain[0].value.clone()),
+    };
+    if let Some(result) = iterate_method_candidates_by_receiver(
+        &refed,
+        deref_chain,
+        db,
+        resolver,
+        name,
+        &mut callback,
+    ) {
+        return Some(result);
+    }
+    let ref_muted = Canonical {
+        num_vars: deref_chain[0].num_vars,
+        value: Ty::apply_one(TypeCtor::Ref(Mutability::Mut), deref_chain[0].value.clone()),
+    };
+    if let Some(result) = iterate_method_candidates_by_receiver(
+        &ref_muted,
+        deref_chain,
+        db,
+        resolver,
+        name,
+        &mut callback,
+    ) {
+        return Some(result);
+    }
+    None
+}
+fn iterate_method_candidates_by_receiver<T>(
+    receiver_ty: &Canonical<Ty>,
+    rest_of_deref_chain: &[Canonical<Ty>],
+    db: &impl HirDatabase,
+    resolver: &Resolver,
+    name: Option<&Name>,
+    mut callback: impl FnMut(&Ty, AssocItemId) -> Option<T>,
+) -> Option<T> {
+    // We're looking for methods with *receiver* type receiver_ty. These could
+    // be found in any of the derefs of receiver_ty, so we have to go through
+    // that.
+    let krate = resolver.krate()?;
+    for self_ty in std::iter::once(receiver_ty).chain(rest_of_deref_chain) {
+        if let Some(result) =
+            iterate_inherent_methods(self_ty, db, name, Some(receiver_ty), krate, &mut callback)
+        {
+            return Some(result);
+        }
+    }
+    for self_ty in std::iter::once(receiver_ty).chain(rest_of_deref_chain) {
+        if let Some(result) = iterate_trait_method_candidates(
+            self_ty,
+            db,
+            resolver,
+            name,
+            Some(receiver_ty),
+            &mut callback,
+        ) {
+            return Some(result);
        }
    }
    None
 }
+fn iterate_method_candidates_for_self_ty<T>(
+    self_ty: &Canonical<Ty>,
+    db: &impl HirDatabase,
+    resolver: &Resolver,
+    name: Option<&Name>,
+    mut callback: impl FnMut(&Ty, AssocItemId) -> Option<T>,
+) -> Option<T> {
+    let krate = resolver.krate()?;
+    if let Some(result) = iterate_inherent_methods(self_ty, db, name, None, krate, &mut callback) {
+        return Some(result);
+    }
+    if let Some(result) =
+        iterate_trait_method_candidates(self_ty, db, resolver, name, None, &mut callback)
+    {
+        return Some(result);
+    }
+    None
+}
 fn iterate_trait_method_candidates<T>(
-    ty: &Canonical<Ty>,
+    self_ty: &Canonical<Ty>,
    db: &impl HirDatabase,
    resolver: &Resolver,
    name: Option<&Name>,
-    mode: LookupMode,
+    receiver_ty: Option<&Canonical<Ty>>,
    mut callback: impl FnMut(&Ty, AssocItemId) -> Option<T>,
 ) -> Option<T> {
    let krate = resolver.krate()?;
    // FIXME: maybe put the trait_env behind a query (need to figure out good input parameters for that)
    let env = TraitEnvironment::lower(db, resolver);
    // if ty is `impl Trait` or `dyn Trait`, the trait doesn't need to be in scope
-    let inherent_trait = ty.value.inherent_trait().into_iter();
+    let inherent_trait = self_ty.value.inherent_trait().into_iter();
    // if we have `T: Trait` in the param env, the trait doesn't need to be in scope
    let traits_from_env = env
-        .trait_predicates_for_self_ty(&ty.value)
+        .trait_predicates_for_self_ty(&self_ty.value)
        .map(|tr| tr.trait_)
        .flat_map(|t| all_super_traits(db, t));
    let traits =
@@ -252,17 +354,17 @@ fn iterate_trait_method_candidates<T>(
        // iteration
        let mut known_implemented = false;
        for (_name, item) in data.items.iter() {
-            if !is_valid_candidate(db, name, mode, (*item).into()) {
+            if !is_valid_candidate(db, name, receiver_ty, (*item).into(), self_ty) {
                continue;
            }
            if !known_implemented {
-                let goal = generic_implements_goal(db, env.clone(), t, ty.clone());
+                let goal = generic_implements_goal(db, env.clone(), t, self_ty.clone());
                if db.trait_solve(krate.into(), goal).is_none() {
                    continue 'traits;
                }
            }
            known_implemented = true;
-            if let Some(result) = callback(&ty.value, (*item).into()) {
+            if let Some(result) = callback(&self_ty.value, (*item).into()) {
                return Some(result);
            }
        }
@@ -271,22 +373,22 @@ fn iterate_trait_method_candidates<T>(
 }
 fn iterate_inherent_methods<T>(
-    ty: &Canonical<Ty>,
+    self_ty: &Canonical<Ty>,
    db: &impl HirDatabase,
    name: Option<&Name>,
-    mode: LookupMode,
+    receiver_ty: Option<&Canonical<Ty>>,
    krate: CrateId,
    mut callback: impl FnMut(&Ty, AssocItemId) -> Option<T>,
 ) -> Option<T> {
-    for krate in ty.value.def_crates(db, krate)? {
+    for krate in self_ty.value.def_crates(db, krate)? {
        let impls = db.impls_in_crate(krate);
-        for impl_block in impls.lookup_impl_blocks(&ty.value) {
+        for impl_block in impls.lookup_impl_blocks(&self_ty.value) {
            for &item in db.impl_data(impl_block).items.iter() {
-                if !is_valid_candidate(db, name, mode, item) {
+                if !is_valid_candidate(db, name, receiver_ty, item, self_ty) {
                    continue;
                }
-                if let Some(result) = callback(&ty.value, item.into()) {
+                if let Some(result) = callback(&self_ty.value, item) {
                    return Some(result);
                }
            }
@@ -298,23 +400,68 @@ fn iterate_inherent_methods<T>(
 fn is_valid_candidate(
    db: &impl HirDatabase,
    name: Option<&Name>,
-    mode: LookupMode,
+    receiver_ty: Option<&Canonical<Ty>>,
    item: AssocItemId,
+    self_ty: &Canonical<Ty>,
 ) -> bool {
    match item {
        AssocItemId::FunctionId(m) => {
            let data = db.function_data(m);
-            name.map_or(true, |name| &data.name == name)
+            if let Some(name) = name {
-                && (data.has_self_param || mode == LookupMode::Path)
+                if &data.name != name {
+                    return false;
+                }
+            }
+            if let Some(receiver_ty) = receiver_ty {
+                if !data.has_self_param {
+                    return false;
+                }
+                let transformed_receiver_ty = match transform_receiver_ty(db, m, self_ty) {
+                    Some(ty) => ty,
+                    None => return false,
+                };
+                if transformed_receiver_ty != receiver_ty.value {
+                    return false;
+                }
+            }
+            true
        }
        AssocItemId::ConstId(c) => {
            let data = db.const_data(c);
-            name.map_or(true, |name| data.name.as_ref() == Some(name)) && (mode == LookupMode::Path)
+            name.map_or(true, |name| data.name.as_ref() == Some(name)) && receiver_ty.is_none()
        }
        _ => false,
    }
 }
+pub(crate) fn inherent_impl_substs(
+    db: &impl HirDatabase,
+    impl_id: ImplId,
+    self_ty: &Ty,
+) -> Option<Substs> {
+    let vars = Substs::build_for_def(db, impl_id).fill_with_bound_vars(0).build();
+    let self_ty_with_vars = db.impl_self_ty(impl_id).subst(&vars);
+    let self_ty_with_vars = Canonical { num_vars: vars.len(), value: &self_ty_with_vars };
+    super::infer::unify(self_ty_with_vars, self_ty)
+}
+fn transform_receiver_ty(
+    db: &impl HirDatabase,
+    function_id: FunctionId,
+    self_ty: &Canonical<Ty>,
+) -> Option<Ty> {
+    let substs = match function_id.lookup(db).container {
+        hir_def::ContainerId::TraitId(_) => Substs::build_for_def(db, function_id)
+            .push(self_ty.value.clone())
+            .fill_with_unknown()
+            .build(),
+        hir_def::ContainerId::ImplId(impl_id) => inherent_impl_substs(db, impl_id, &self_ty.value)?,
+        hir_def::ContainerId::ModuleId(_) => unreachable!(),
+    };
+    let sig = db.callable_item_signature(function_id.into());
+    Some(sig.params()[0].clone().subst(&substs))
+}
 pub fn implements_trait(
    ty: &Canonical<Ty>,
    db: &impl HirDatabase,
diff --git a/crates/ra_hir_ty/src/tests.rs b/crates/ra_hir_ty/src/tests.rs
index a3cc5cf95..d5b8d10e2 100644
--- a/crates/ra_hir_ty/src/tests.rs
+++ b/crates/ra_hir_ty/src/tests.rs
@@ -3433,7 +3433,20 @@ pub fn baz() -> usize { 31usize }
    assert_eq!("(i32, usize)", type_at_pos(&db, pos));
 }
-#[ignore]
+#[test]
+fn method_resolution_unify_impl_self_type() {
+    let t = type_at(
+        r#"
+//- /main.rs
+struct S<T>;
+impl S<u32> { fn foo(&self) -> u8 {} }
+impl S<i32> { fn foo(&self) -> i8 {} }
+fn test() { (S::<u32>.foo(), S::<i32>.foo())<|>; }
+"#,
+    );
+    assert_eq!(t, "(u8, i8)");
+}
 #[test]
 fn method_resolution_trait_before_autoref() {
    let t = type_at(
@@ -3449,7 +3462,6 @@ fn test() { S.foo()<|>; }
    assert_eq!(t, "u128");
 }
-#[ignore]
 #[test]
 fn method_resolution_by_value_before_autoref() {
    let t = type_at(
@@ -3496,6 +3508,21 @@ fn test() { S.foo()<|>; }
 }
 #[test]
+fn method_resolution_impl_ref_before_trait() {
+    let t = type_at(
+        r#"
+//- /main.rs
+trait Trait { fn foo(self) -> u128; }
+struct S;
+impl S { fn foo(&self) -> i8 { 0 } }
+impl Trait for &S { fn foo(self) -> u128 { 0 } }
+fn test() { S.foo()<|>; }
+"#,
+    );
+    assert_eq!(t, "i8");
+}
+#[test]
 fn method_resolution_trait_autoderef() {
    let t = type_at(
        r#"
diff --git a/crates/ra_ide/src/completion/complete_dot.rs b/crates/ra_ide/src/completion/complete_dot.rs
index b6fe48627..a52eb0ee4 100644
--- a/crates/ra_ide/src/completion/complete_dot.rs
+++ b/crates/ra_ide/src/completion/complete_dot.rs
@@ -217,6 +217,39 @@ mod tests {
    }
    #[test]
+    fn test_method_completion_only_fitting_impls() {
+        assert_debug_snapshot!(
+            do_ref_completion(
+                r"
+            struct A<T> {}
+            impl A<u32> {
+                fn the_method(&self) {}
+            }
+            impl A<i32> {
+                fn the_other_method(&self) {}
+            }
+            fn foo(a: A<u32>) {
+               a.<|>
+            }
+            ",
+            ),
+            @r###"
+        [
+            CompletionItem {
+                label: "the_method()",
+                source_range: [243; 243),
+                delete: [243; 243),
+                insert: "the_method()$0",
+                kind: Method,
+                lookup: "the_method",
+                detail: "fn the_method(&self)",
+            },
+        ]
+        "###
+        );
+    }
+    #[test]
    fn test_trait_method_completion() {
        assert_debug_snapshot!(
            do_ref_completion(