5 files changed, 454 insertions, 186 deletions

diff --git a/crates/ra_hir_ty/src/infer/coerce.rs b/crates/ra_hir_ty/src/infer/coerce.rs
index 719a0f395..83c0c2c3f 100644
--- a/crates/ra_hir_ty/src/infer/coerce.rs
+++ b/crates/ra_hir_ty/src/infer/coerce.rs
@@ -8,9 +8,9 @@ use hir_def::{lang_item::LangItemTarget, resolver::Resolver, type_ref::Mutabilit
 use rustc_hash::FxHashMap;
 use test_utils::tested_by;
 
-use crate::{autoderef, db::HirDatabase, ImplTy, Substs, Ty, TypeCtor, TypeWalk};
+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
@@ -54,10 +54,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
         impls
             .iter()
             .filter_map(|&impl_id| {
-                let trait_ref = match db.impl_ty(impl_id) {
-                    ImplTy::TraitRef(it) => it,
-                    ImplTy::Inherent(_) => return None,
-                };
+                let trait_ref = db.impl_trait(impl_id)?;
 
                 // `CoerseUnsized` has one generic parameter for the target type.
                 let cur_from_ty = trait_ref.substs.0.get(0)?;
@@ -88,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();
-                self.var_unification_table.union_value(*tv, TypeVarValue::Known(var));
+                let var = self.table.new_maybe_never_type_var();
+                self.table.var_unification_table.union_value(*tv, TypeVarValue::Known(var));
                 return true;
             }
             (ty_app!(TypeCtor::Never), _) => return true,
@@ -97,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;
                 }
             }
@@ -137,6 +134,10 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
                 }
             }
 
+            (ty_app!(TypeCtor::Closure { .. }, params), ty_app!(TypeCtor::FnPtr { .. })) => {
+                from_ty = params[0].clone();
+            }
+
             _ => {}
         }
 
@@ -333,9 +334,13 @@ 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);
+                }
+                _ => {
+                    if self.table.unify_inner_trivial(&derefed_ty, &to_ty) {
+                        return true;
+                    }
                 }
-                _ => {}
             }
         }
 
diff --git a/crates/ra_hir_ty/src/infer/expr.rs b/crates/ra_hir_ty/src/infer/expr.rs
index 2f9ca4bbb..3af05394c 100644
--- a/crates/ra_hir_ty/src/infer/expr.rs
+++ b/crates/ra_hir_ty/src/infer/expr.rs
@@ -6,17 +6,21 @@ use std::sync::Arc;
 use hir_def::{
     builtin_type::Signedness,
     expr::{Array, BinaryOp, Expr, ExprId, Literal, Statement, UnaryOp},
-    generics::GenericParams,
     path::{GenericArg, GenericArgs},
     resolver::resolver_for_expr,
-    AdtId, ContainerId, Lookup, StructFieldId,
+    AdtId, AssocContainerId, Lookup, StructFieldId,
 };
-use hir_expand::name::{self, Name};
+use hir_expand::name::{name, Name};
+use ra_syntax::ast::RangeOp;
 
 use crate::{
-    autoderef, db::HirDatabase, method_resolution, op, traits::InEnvironment, utils::variant_data,
-    CallableDef, InferTy, IntTy, Mutability, Obligation, ProjectionPredicate, ProjectionTy, Substs,
-    TraitRef, Ty, TypeCtor, TypeWalk, Uncertain,
+    autoderef,
+    db::HirDatabase,
+    method_resolution, op,
+    traits::InEnvironment,
+    utils::{generics, variant_data, Generics},
+    ApplicationTy, CallableDef, InferTy, IntTy, Mutability, Obligation, Substs, TraitRef, Ty,
+    TypeCtor, TypeWalk, Uncertain,
 };
 
 use super::{BindingMode, Expectation, InferenceContext, InferenceDiagnostic, TypeMismatch};
@@ -31,13 +35,13 @@ 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
     }
 
     /// Infer type of expression with possibly implicit coerce to the expected type.
     /// Return the type after possible coercion.
-    fn infer_expr_coerce(&mut self, expr: ExprId, expected: &Expectation) -> Ty {
+    pub(super) fn infer_expr_coerce(&mut self, expr: ExprId, expected: &Expectation) -> Ty {
         let ty = self.infer_expr_inner(expr, &expected);
         let ty = if !self.coerce(&ty, &expected.ty) {
             self.result
@@ -52,7 +56,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 {
@@ -91,27 +95,14 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
             Expr::For { iterable, body, pat } => {
                 let iterable_ty = self.infer_expr(*iterable, &Expectation::none());
 
-                let pat_ty = match self.resolve_into_iter_item() {
-                    Some(into_iter_item_alias) => {
-                        let pat_ty = self.new_type_var();
-                        let projection = ProjectionPredicate {
-                            ty: pat_ty.clone(),
-                            projection_ty: ProjectionTy {
-                                associated_ty: into_iter_item_alias,
-                                parameters: Substs::single(iterable_ty),
-                            },
-                        };
-                        self.obligations.push(Obligation::Projection(projection));
-                        self.resolve_ty_as_possible(&mut vec![], pat_ty)
-                    }
-                    None => Ty::Unknown,
-                };
+                let pat_ty =
+                    self.resolve_associated_type(iterable_ty, self.resolve_into_iter_item());
 
                 self.infer_pat(*pat, &pat_ty, BindingMode::default());
                 self.infer_expr(*body, &Expectation::has_type(Ty::unit()));
                 Ty::unit()
             }
-            Expr::Lambda { body, args, arg_types } => {
+            Expr::Lambda { body, args, ret_type, arg_types } => {
                 assert_eq!(args.len(), arg_types.len());
 
                 let mut sig_tys = Vec::new();
@@ -127,7 +118,10 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
                 }
 
                 // add return type
-                let ret_ty = self.new_type_var();
+                let ret_ty = match ret_type {
+                    Some(type_ref) => self.make_ty(type_ref),
+                    None => 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 },
@@ -143,7 +137,12 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
                 // infer the body.
                 self.coerce(&closure_ty, &expected.ty);
 
-                self.infer_expr(*body, &Expectation::has_type(ret_ty));
+                let prev_ret_ty = std::mem::replace(&mut self.return_ty, ret_ty.clone());
+
+                self.infer_expr_coerce(*body, &Expectation::has_type(ret_ty));
+
+                self.return_ty = prev_ret_ty;
+
                 closure_ty
             }
             Expr::Call { callee, args } => {
@@ -166,7 +165,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 {
@@ -200,7 +199,10 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
             }
             Expr::Return { expr } => {
                 if let Some(expr) = expr {
-                    self.infer_expr(*expr, &Expectation::has_type(self.return_ty.clone()));
+                    self.infer_expr_coerce(*expr, &Expectation::has_type(self.return_ty.clone()));
+                } else {
+                    let unit = Ty::unit();
+                    self.coerce(&unit, &self.return_ty.clone());
                 }
                 Ty::simple(TypeCtor::Never)
             }
@@ -244,7 +246,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
                 ty
             }
             Expr::Field { expr, name } => {
-                let receiver_ty = self.infer_expr(*expr, &Expectation::none());
+                let receiver_ty = self.infer_expr_inner(*expr, &Expectation::none());
                 let canonicalized = self.canonicalizer().canonicalize_ty(receiver_ty);
                 let ty = autoderef::autoderef(
                     self.db,
@@ -279,45 +281,18 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
                 self.normalize_associated_types_in(ty)
             }
             Expr::Await { expr } => {
-                let inner_ty = self.infer_expr(*expr, &Expectation::none());
-                let ty = match self.resolve_future_future_output() {
-                    Some(future_future_output_alias) => {
-                        let ty = self.new_type_var();
-                        let projection = ProjectionPredicate {
-                            ty: ty.clone(),
-                            projection_ty: ProjectionTy {
-                                associated_ty: future_future_output_alias,
-                                parameters: Substs::single(inner_ty),
-                            },
-                        };
-                        self.obligations.push(Obligation::Projection(projection));
-                        self.resolve_ty_as_possible(&mut vec![], ty)
-                    }
-                    None => Ty::Unknown,
-                };
+                let inner_ty = self.infer_expr_inner(*expr, &Expectation::none());
+                let ty =
+                    self.resolve_associated_type(inner_ty, self.resolve_future_future_output());
                 ty
             }
             Expr::Try { expr } => {
-                let inner_ty = self.infer_expr(*expr, &Expectation::none());
-                let ty = match self.resolve_ops_try_ok() {
-                    Some(ops_try_ok_alias) => {
-                        let ty = self.new_type_var();
-                        let projection = ProjectionPredicate {
-                            ty: ty.clone(),
-                            projection_ty: ProjectionTy {
-                                associated_ty: ops_try_ok_alias,
-                                parameters: Substs::single(inner_ty),
-                            },
-                        };
-                        self.obligations.push(Obligation::Projection(projection));
-                        self.resolve_ty_as_possible(&mut vec![], ty)
-                    }
-                    None => Ty::Unknown,
-                };
+                let inner_ty = self.infer_expr_inner(*expr, &Expectation::none());
+                let ty = self.resolve_associated_type(inner_ty, self.resolve_ops_try_ok());
                 ty
             }
             Expr::Cast { expr, type_ref } => {
-                let _inner_ty = self.infer_expr(*expr, &Expectation::none());
+                let _inner_ty = self.infer_expr_inner(*expr, &Expectation::none());
                 let cast_ty = self.make_ty(type_ref);
                 // FIXME check the cast...
                 cast_ty
@@ -333,12 +308,11 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
                     } else {
                         Expectation::none()
                     };
-                // FIXME reference coercions etc.
-                let inner_ty = self.infer_expr(*expr, &expectation);
+                let inner_ty = self.infer_expr_inner(*expr, &expectation);
                 Ty::apply_one(TypeCtor::Ref(*mutability), inner_ty)
             }
             Expr::Box { expr } => {
-                let inner_ty = self.infer_expr(*expr, &Expectation::none());
+                let inner_ty = self.infer_expr_inner(*expr, &Expectation::none());
                 if let Some(box_) = self.resolve_boxed_box() {
                     Ty::apply_one(TypeCtor::Adt(box_), inner_ty)
                 } else {
@@ -346,7 +320,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
                 }
             }
             Expr::UnaryOp { expr, op } => {
-                let inner_ty = self.infer_expr(*expr, &Expectation::none());
+                let inner_ty = self.infer_expr_inner(*expr, &Expectation::none());
                 match op {
                     UnaryOp::Deref => match self.resolver.krate() {
                         Some(krate) => {
@@ -369,31 +343,36 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
                     },
                     UnaryOp::Neg => {
                         match &inner_ty {
-                            Ty::Apply(a_ty) => match a_ty.ctor {
-                                TypeCtor::Int(Uncertain::Unknown)
-                                | TypeCtor::Int(Uncertain::Known(IntTy {
-                                    signedness: Signedness::Signed,
-                                    ..
-                                }))
-                                | TypeCtor::Float(..) => inner_ty,
-                                _ => Ty::Unknown,
-                            },
-                            Ty::Infer(InferTy::IntVar(..)) | Ty::Infer(InferTy::FloatVar(..)) => {
-                                inner_ty
-                            }
-                            // FIXME: resolve ops::Neg trait
-                            _ => Ty::Unknown,
+                            // Fast path for builtins
+                            Ty::Apply(ApplicationTy {
+                                ctor:
+                                    TypeCtor::Int(Uncertain::Known(IntTy {
+                                        signedness: Signedness::Signed,
+                                        ..
+                                    })),
+                                ..
+                            })
+                            | Ty::Apply(ApplicationTy {
+                                ctor: TypeCtor::Int(Uncertain::Unknown),
+                                ..
+                            })
+                            | Ty::Apply(ApplicationTy { ctor: TypeCtor::Float(_), .. })
+                            | Ty::Infer(InferTy::IntVar(..))
+                            | Ty::Infer(InferTy::FloatVar(..)) => inner_ty,
+                            // Otherwise we resolve via the std::ops::Neg trait
+                            _ => self
+                                .resolve_associated_type(inner_ty, self.resolve_ops_neg_output()),
                         }
                     }
                     UnaryOp::Not => {
                         match &inner_ty {
-                            Ty::Apply(a_ty) => match a_ty.ctor {
-                                TypeCtor::Bool | TypeCtor::Int(_) => inner_ty,
-                                _ => Ty::Unknown,
-                            },
-                            Ty::Infer(InferTy::IntVar(..)) => inner_ty,
-                            // FIXME: resolve ops::Not trait for inner_ty
-                            _ => Ty::Unknown,
+                            // Fast path for builtins
+                            Ty::Apply(ApplicationTy { ctor: TypeCtor::Bool, .. })
+                            | Ty::Apply(ApplicationTy { ctor: TypeCtor::Int(_), .. })
+                            | Ty::Infer(InferTy::IntVar(..)) => inner_ty,
+                            // Otherwise we resolve via the std::ops::Not trait
+                            _ => self
+                                .resolve_associated_type(inner_ty, self.resolve_ops_not_output()),
                         }
                     }
                 }
@@ -415,21 +394,63 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
                 }
                 _ => Ty::Unknown,
             },
+            Expr::Range { lhs, rhs, range_type } => {
+                let lhs_ty = lhs.map(|e| self.infer_expr_inner(e, &Expectation::none()));
+                let rhs_expect = lhs_ty
+                    .as_ref()
+                    .map_or_else(Expectation::none, |ty| Expectation::has_type(ty.clone()));
+                let rhs_ty = rhs.map(|e| self.infer_expr(e, &rhs_expect));
+                match (range_type, lhs_ty, rhs_ty) {
+                    (RangeOp::Exclusive, None, None) => match self.resolve_range_full() {
+                        Some(adt) => Ty::simple(TypeCtor::Adt(adt)),
+                        None => Ty::Unknown,
+                    },
+                    (RangeOp::Exclusive, None, Some(ty)) => match self.resolve_range_to() {
+                        Some(adt) => Ty::apply_one(TypeCtor::Adt(adt), ty),
+                        None => Ty::Unknown,
+                    },
+                    (RangeOp::Inclusive, None, Some(ty)) => {
+                        match self.resolve_range_to_inclusive() {
+                            Some(adt) => Ty::apply_one(TypeCtor::Adt(adt), ty),
+                            None => Ty::Unknown,
+                        }
+                    }
+                    (RangeOp::Exclusive, Some(_), Some(ty)) => match self.resolve_range() {
+                        Some(adt) => Ty::apply_one(TypeCtor::Adt(adt), ty),
+                        None => Ty::Unknown,
+                    },
+                    (RangeOp::Inclusive, Some(_), Some(ty)) => {
+                        match self.resolve_range_inclusive() {
+                            Some(adt) => Ty::apply_one(TypeCtor::Adt(adt), ty),
+                            None => Ty::Unknown,
+                        }
+                    }
+                    (RangeOp::Exclusive, Some(ty), None) => match self.resolve_range_from() {
+                        Some(adt) => Ty::apply_one(TypeCtor::Adt(adt), ty),
+                        None => Ty::Unknown,
+                    },
+                    (RangeOp::Inclusive, _, None) => Ty::Unknown,
+                }
+            }
             Expr::Index { base, index } => {
-                let _base_ty = self.infer_expr(*base, &Expectation::none());
-                let _index_ty = self.infer_expr(*index, &Expectation::none());
-                // FIXME: use `std::ops::Index::Output` to figure out the real return type
-                Ty::Unknown
+                let base_ty = self.infer_expr_inner(*base, &Expectation::none());
+                let index_ty = self.infer_expr(*index, &Expectation::none());
+
+                self.resolve_associated_type_with_params(
+                    base_ty,
+                    self.resolve_ops_index_output(),
+                    &[index_ty],
+                )
             }
             Expr::Tuple { exprs } => {
                 let mut tys = match &expected.ty {
                     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()) {
@@ -443,7 +464,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 {
@@ -485,7 +506,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
     }
@@ -514,7 +535,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) => {
@@ -558,7 +579,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
             Some((ty, func)) => {
                 let ty = canonicalized_receiver.decanonicalize_ty(ty);
                 self.write_method_resolution(tgt_expr, func);
-                (ty, self.db.value_ty(func.into()), Some(self.db.generic_params(func.into())))
+                (ty, self.db.value_ty(func.into()), Some(generics(self.db, func.into())))
             }
             None => (receiver_ty, Ty::Unknown, None),
         };
@@ -607,6 +628,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
                     continue;
                 }
 
+                let param_ty = self.insert_vars_for_impl_trait(param_ty);
                 let param_ty = self.normalize_associated_types_in(param_ty);
                 self.infer_expr_coerce(arg, &Expectation::has_type(param_ty.clone()));
             }
@@ -615,17 +637,17 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
 
     fn substs_for_method_call(
         &mut self,
-        def_generics: Option<Arc<GenericParams>>,
+        def_generics: Option<Generics>,
         generic_args: Option<&GenericArgs>,
         receiver_ty: &Ty,
     ) -> Substs {
-        let (parent_param_count, param_count) =
-            def_generics.as_ref().map_or((0, 0), |g| (g.count_parent_params(), g.params.len()));
-        let mut substs = Vec::with_capacity(parent_param_count + param_count);
+        let (total_len, _parent_len, child_len) =
+            def_generics.as_ref().map_or((0, 0, 0), |g| g.len_split());
+        let mut substs = Vec::with_capacity(total_len);
         // Parent arguments are unknown, except for the receiver type
-        if let Some(parent_generics) = def_generics.and_then(|p| p.parent_params.clone()) {
-            for param in &parent_generics.params {
-                if param.name == name::SELF_TYPE {
+        if let Some(parent_generics) = def_generics.as_ref().map(|p| p.iter_parent()) {
+            for (_id, param) in parent_generics {
+                if param.name == name![Self] {
                     substs.push(receiver_ty.clone());
                 } else {
                     substs.push(Ty::Unknown);
@@ -635,7 +657,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
         // handle provided type arguments
         if let Some(generic_args) = generic_args {
             // if args are provided, it should be all of them, but we can't rely on that
-            for arg in generic_args.args.iter().take(param_count) {
+            for arg in generic_args.args.iter().take(child_len) {
                 match arg {
                     GenericArg::Type(type_ref) => {
                         let ty = self.make_ty(type_ref);
@@ -645,10 +667,10 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
             }
         };
         let supplied_params = substs.len();
-        for _ in supplied_params..parent_param_count + param_count {
+        for _ in supplied_params..total_len {
             substs.push(Ty::Unknown);
         }
-        assert_eq!(substs.len(), parent_param_count + param_count);
+        assert_eq!(substs.len(), total_len);
         Substs(substs.into())
     }
 
@@ -665,13 +687,10 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
                 // add obligation for trait implementation, if this is a trait method
                 match def {
                     CallableDef::FunctionId(f) => {
-                        if let ContainerId::TraitId(trait_) = f.lookup(self.db).container {
+                        if let AssocContainerId::TraitId(trait_) = f.lookup(self.db).container {
                             // construct a TraitDef
-                            let substs = a_ty.parameters.prefix(
-                                self.db
-                                    .generic_params(trait_.into())
-                                    .count_params_including_parent(),
-                            );
+                            let substs =
+                                a_ty.parameters.prefix(generics(self.db, trait_.into()).len());
                             self.obligations.push(Obligation::Trait(TraitRef {
                                 trait_: trait_.into(),
                                 substs,
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 14be66836..ffd358367 100644
--- a/crates/ra_hir_ty/src/infer/path.rs
+++ b/crates/ra_hir_ty/src/infer/path.rs
@@ -1,9 +1,11 @@
 //! Path expression resolution.
 
+use std::iter;
+
 use hir_def::{
-    path::{Path, PathKind, PathSegment},
+    path::{Path, PathSegment},
     resolver::{ResolveValueResult, Resolver, TypeNs, ValueNs},
-    AssocItemId, ContainerId, Lookup,
+    AssocContainerId, AssocItemId, Lookup,
 };
 use hir_expand::name::Name;
 
@@ -30,21 +32,21 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
         path: &Path,
         id: ExprOrPatId,
     ) -> Option<Ty> {
-        let (value, self_subst) = if let PathKind::Type(type_ref) = &path.kind {
-            if path.segments.is_empty() {
+        let (value, self_subst) = if let Some(type_ref) = path.type_anchor() {
+            if path.segments().is_empty() {
                 // This can't actually happen syntax-wise
                 return None;
             }
             let ty = self.make_ty(type_ref);
-            let remaining_segments_for_ty = &path.segments[..path.segments.len() - 1];
+            let remaining_segments_for_ty = path.segments().take(path.segments().len() - 1);
             let ty = Ty::from_type_relative_path(self.db, resolver, ty, remaining_segments_for_ty);
             self.resolve_ty_assoc_item(
                 ty,
-                &path.segments.last().expect("path had at least one segment").name,
+                &path.segments().last().expect("path had at least one segment").name,
                 id,
             )?
         } else {
-            let value_or_partial = resolver.resolve_path_in_value_ns(self.db, &path)?;
+            let value_or_partial = resolver.resolve_path_in_value_ns(self.db, path.mod_path())?;
 
             match value_or_partial {
                 ResolveValueResult::ValueNs(it) => (it, None),
@@ -57,7 +59,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(),
@@ -83,13 +85,13 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
         remaining_index: usize,
         id: ExprOrPatId,
     ) -> Option<(ValueNs, Option<Substs>)> {
-        assert!(remaining_index < path.segments.len());
+        assert!(remaining_index < path.segments().len());
         // there may be more intermediate segments between the resolved one and
         // the end. Only the last segment needs to be resolved to a value; from
         // the segments before that, we need to get either a type or a trait ref.
 
-        let resolved_segment = &path.segments[remaining_index - 1];
-        let remaining_segments = &path.segments[remaining_index..];
+        let resolved_segment = path.segments().get(remaining_index - 1).unwrap();
+        let remaining_segments = path.segments().skip(remaining_index);
         let is_before_last = remaining_segments.len() == 1;
 
         match (def, is_before_last) {
@@ -110,7 +112,8 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
                 // trait but it's not the last segment, so the next segment
                 // should resolve to an associated type of that trait (e.g. `<T
                 // as Iterator>::Item::default`)
-                let remaining_segments_for_ty = &remaining_segments[..remaining_segments.len() - 1];
+                let remaining_segments_for_ty =
+                    remaining_segments.take(remaining_segments.len() - 1);
                 let ty = Ty::from_partly_resolved_hir_path(
                     self.db,
                     &self.resolver,
@@ -136,7 +139,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
     fn resolve_trait_assoc_item(
         &mut self,
         trait_ref: TraitRef,
-        segment: &PathSegment,
+        segment: PathSegment<'_>,
         id: ExprOrPatId,
     ) -> Option<(ValueNs, Option<Substs>)> {
         let trait_ = trait_ref.trait_;
@@ -148,7 +151,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
             .map(|(_name, id)| (*id).into())
             .find_map(|item| match item {
                 AssocItemId::FunctionId(func) => {
-                    if segment.name == self.db.function_data(func).name {
+                    if segment.name == &self.db.function_data(func).name {
                         Some(AssocItemId::FunctionId(func))
                     } else {
                         None
@@ -156,7 +159,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
                 }
 
                 AssocItemId::ConstId(konst) => {
-                    if self.db.const_data(konst).name.as_ref().map_or(false, |n| n == &segment.name)
+                    if self.db.const_data(konst).name.as_ref().map_or(false, |n| n == segment.name)
                     {
                         Some(AssocItemId::ConstId(konst))
                     } else {
@@ -206,12 +209,23 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
                     AssocItemId::TypeAliasId(_) => unreachable!(),
                 };
                 let substs = match container {
-                    ContainerId::ImplId(_) => self.find_self_types(&def, ty.clone()),
-                    ContainerId::TraitId(trait_) => {
+                    AssocContainerId::ImplId(impl_id) => {
+                        let impl_substs = Substs::build_for_def(self.db, impl_id)
+                            .fill(iter::repeat_with(|| self.table.new_type_var()))
+                            .build();
+                        let impl_self_ty = self.db.impl_self_ty(impl_id).subst(&impl_substs);
+                        let substs = Substs::build_for_def(self.db, item)
+                            .use_parent_substs(&impl_substs)
+                            .fill_with_params()
+                            .build();
+                        self.unify(&impl_self_ty, &ty);
+                        Some(substs)
+                    }
+                    AssocContainerId::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)
@@ -223,7 +237,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
                         }));
                         Some(substs)
                     }
-                    ContainerId::ModuleId(_) => None,
+                    AssocContainerId::ContainerId(_) => None,
                 };
 
                 self.write_assoc_resolution(id, item.into());
@@ -231,38 +245,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_ty(impl_id).self_type().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..fe05642ae 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: &Canonical<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.value) {
+        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),
         }
     }
 }