Better handle never type and branch merging

Split out tests for never type to another file

5 files changed, 392 insertions, 181 deletions

diff --git a/crates/ra_hir/src/marks.rs b/crates/ra_hir/src/marks.rs
index fe119b97c..b2111be05 100644
--- a/crates/ra_hir/src/marks.rs
+++ b/crates/ra_hir/src/marks.rs
@@ -13,4 +13,5 @@ test_utils::marks!(
     infer_while_let
     macro_rules_from_other_crates_are_visible_with_macro_use
     prelude_is_macro_use
+    coerce_merge_fail_fallback
 );
diff --git a/crates/ra_hir/src/ty/infer.rs b/crates/ra_hir/src/ty/infer.rs
index def787fb1..cbbba8b23 100644
--- a/crates/ra_hir/src/ty/infer.rs
+++ b/crates/ra_hir/src/ty/infer.rs
@@ -297,23 +297,35 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
     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::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::IntVar(tv)), other)
-            | (other, Ty::Infer(InferTy::IntVar(tv)))
-            | (Ty::Infer(InferTy::FloatVar(tv)), other)
-            | (other, Ty::Infer(InferTy::FloatVar(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,
         }
     }
@@ -330,6 +342,12 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
         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 {
@@ -817,6 +835,24 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
         ty
     }
 
+    /// Merge two types from different branches, with possible implicit coerce.
+    ///
+    /// Note that it is only possible that one type are coerced to another.
+    /// Coercing both types to another least upper bound type is not possible in rustc,
+    /// which will simply result in "incompatible types" error.
+    fn coerce_merge_branch<'t>(&mut self, ty1: &Ty, ty2: &Ty) -> Ty {
+        if self.coerce(ty1, ty2) {
+            ty2.clone()
+        } else if self.coerce(ty2, ty1) {
+            ty1.clone()
+        } else {
+            tested_by!(coerce_merge_fail_fallback);
+            // For incompatible types, we use the latter one as result
+            // to be better recovery for `if` without `else`.
+            ty2.clone()
+        }
+    }
+
     /// Unify two types, but may coerce the first one to the second one
     /// using "implicit coercion rules" if needed.
     ///
@@ -828,12 +864,26 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
     }
 
     fn coerce_inner(&mut self, mut from_ty: Ty, to_ty: &Ty) -> bool {
-        match (&mut from_ty, &*to_ty) {
-            // Top and bottom type
+        match (&from_ty, to_ty) {
+            // Never type will make type variable to fallback to Never Type instead of Unknown.
+            (ty_app!(TypeCtor::Never), Ty::Infer(InferTy::TypeVar(tv))) => {
+                let var = self.new_maybe_never_type_var();
+                self.var_unification_table.union_value(*tv, TypeVarValue::Known(var));
+                return true;
+            }
             (ty_app!(TypeCtor::Never), _) => return true,
 
-            // FIXME: Solve `FromTy: CoerceUnsized<ToTy>` instead of listing common impls here.
+            // Trivial cases, this should go after `never` check to
+            // avoid infer result type to be never
+            _ => {
+                if self.unify_inner_trivial(&from_ty, &to_ty) {
+                    return true;
+                }
+            }
+        }
 
+        // Pointer weakening and function to pointer
+        match (&mut from_ty, to_ty) {
             // `*mut T`, `&mut T, `&T`` -> `*const T`
             // `&mut T` -> `&T`
             // `&mut T` -> `*mut T`
@@ -866,71 +916,67 @@ 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) {
-                    return true;
-                }
-            }
+            _ => {}
         }
 
-        // Try coerce or unify
+        // FIXME: Solve `FromTy: CoerceUnsized<ToTy>` instead of listing common impls here.
         match (&from_ty, &to_ty) {
-            // FIXME: Solve `FromTy: CoerceUnsized<ToTy>` instead of listing common impls here.
+            // Mutilibity is checked above
             (ty_app!(TypeCtor::Ref(_), st1), ty_app!(TypeCtor::Ref(_), st2))
             | (ty_app!(TypeCtor::RawPtr(_), st1), ty_app!(TypeCtor::RawPtr(_), st2)) => {
-                match self.try_coerce_unsized(&st1[0], &st2[0], 0) {
-                    Some(ret) => return ret,
-                    None => {}
+                if self.try_coerce_unsized(&st1[0], &st2[0], 0) {
+                    return true;
                 }
             }
             _ => {}
         }
 
         // Auto Deref if cannot coerce
-        match (&from_ty, &to_ty) {
+        match (&from_ty, to_ty) {
+            // FIXME: DerefMut
             (ty_app!(TypeCtor::Ref(_), st1), ty_app!(TypeCtor::Ref(_), st2)) => {
                 self.unify_autoderef_behind_ref(&st1[0], &st2[0])
             }
 
-            // Normal unify
-            _ => self.unify(&from_ty, &to_ty),
+            // Otherwise, normal unify
+            _ => self.unify(&from_ty, to_ty),
         }
     }
 
     /// Coerce a type to a DST if `FromTy: Unsize<ToTy>`
     ///
     /// See: `https://doc.rust-lang.org/nightly/std/marker/trait.Unsize.html`
-    fn try_coerce_unsized(&mut self, from_ty: &Ty, to_ty: &Ty, depth: usize) -> Option<bool> {
+    fn try_coerce_unsized(&mut self, from_ty: &Ty, to_ty: &Ty, depth: usize) -> bool {
         if depth > 1000 {
             panic!("Infinite recursion in coercion");
         }
 
-        // FIXME: Correctly handle
         match (&from_ty, &to_ty) {
             // `[T; N]` -> `[T]`
             (ty_app!(TypeCtor::Array, st1), ty_app!(TypeCtor::Slice, st2)) => {
-                Some(self.unify(&st1[0], &st2[0]))
+                self.unify(&st1[0], &st2[0])
             }
 
             // `T` -> `dyn Trait` when `T: Trait`
             (_, Ty::Dyn(_)) => {
                 // FIXME: Check predicates
-                Some(true)
+                true
             }
 
-            (ty_app!(ctor1, st1), ty_app!(ctor2, st2)) if ctor1 == ctor2 => {
+            (
+                ty_app!(TypeCtor::Adt(Adt::Struct(struct1)), st1),
+                ty_app!(TypeCtor::Adt(Adt::Struct(struct2)), st2),
+            ) if struct1 == struct2 => {
+                // FIXME: Check preconditions here
                 for (ty1, ty2) in st1.iter().zip(st2.iter()) {
-                    match self.try_coerce_unsized(ty1, ty2, depth + 1) {
-                        Some(true) => {}
-                        ret => return ret,
+                    if !self.try_coerce_unsized(ty1, ty2, depth + 1) {
+                        return false;
                     }
                 }
-                Some(true)
+                true
             }
 
-            _ => None,
+            _ => false,
         }
     }
 
@@ -980,18 +1026,12 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
                 self.infer_expr(*condition, &Expectation::has_type(Ty::simple(TypeCtor::Bool)));
 
                 let then_ty = self.infer_expr_inner(*then_branch, &expected);
-                self.coerce(&then_ty, &expected.ty);
-
                 let else_ty = match else_branch {
                     Some(else_branch) => self.infer_expr_inner(*else_branch, &expected),
                     None => Ty::unit(),
                 };
-                if !self.coerce(&else_ty, &expected.ty) {
-                    self.coerce(&expected.ty, &else_ty);
-                    else_ty.clone()
-                } else {
-                    expected.ty.clone()
-                }
+
+                self.coerce_merge_branch(&then_ty, &else_ty)
             }
             Expr::Block { statements, tail } => self.infer_block(statements, *tail, expected),
             Expr::TryBlock { body } => {
@@ -1087,11 +1127,8 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
                 .infer_method_call(tgt_expr, *receiver, &args, &method_name, generic_args.as_ref()),
             Expr::Match { expr, arms } => {
                 let input_ty = self.infer_expr(*expr, &Expectation::none());
-                let mut expected = match expected.ty {
-                    Ty::Unknown => Expectation::has_type(Ty::simple(TypeCtor::Never)),
-                    _ => expected.clone(),
-                };
-                let mut all_never = true;
+
+                let mut result_ty = self.new_maybe_never_type_var();
 
                 for arm in arms {
                     for &pat in &arm.pats {
@@ -1103,22 +1140,12 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
                             &Expectation::has_type(Ty::simple(TypeCtor::Bool)),
                         );
                     }
+
                     let arm_ty = self.infer_expr_inner(arm.expr, &expected);
-                    match &arm_ty {
-                        ty_app!(TypeCtor::Never) => (),
-                        _ => all_never = false,
-                    }
-                    if !self.coerce(&arm_ty, &expected.ty) {
-                        self.coerce(&expected.ty, &arm_ty);
-                        expected = Expectation::has_type(arm_ty);
-                    }
+                    result_ty = self.coerce_merge_branch(&result_ty, &arm_ty);
                 }
 
-                if all_never {
-                    Ty::simple(TypeCtor::Never)
-                } else {
-                    expected.ty
-                }
+                result_ty
             }
             Expr::Path(p) => {
                 // FIXME this could be more efficient...
@@ -1558,12 +1585,16 @@ pub enum InferTy {
     TypeVar(TypeVarId),
     IntVar(TypeVarId),
     FloatVar(TypeVarId),
+    MaybeNeverTypeVar(TypeVarId),
 }
 
 impl InferTy {
     fn to_inner(self) -> TypeVarId {
         match self {
-            InferTy::TypeVar(ty) | InferTy::IntVar(ty) | InferTy::FloatVar(ty) => ty,
+            InferTy::TypeVar(ty)
+            | InferTy::IntVar(ty)
+            | InferTy::FloatVar(ty)
+            | InferTy::MaybeNeverTypeVar(ty) => ty,
         }
     }
 
@@ -1576,6 +1607,7 @@ impl InferTy {
             InferTy::FloatVar(..) => Ty::simple(TypeCtor::Float(
                 primitive::UncertainFloatTy::Known(primitive::FloatTy::f64()),
             )),
+            InferTy::MaybeNeverTypeVar(..) => Ty::simple(TypeCtor::Never),
         }
     }
 }
diff --git a/crates/ra_hir/src/ty/infer/unify.rs b/crates/ra_hir/src/ty/infer/unify.rs
index 9a0d2d8f9..b6ebee3b1 100644
--- a/crates/ra_hir/src/ty/infer/unify.rs
+++ b/crates/ra_hir/src/ty/infer/unify.rs
@@ -63,6 +63,7 @@ where
                         InferTy::TypeVar(_) => InferTy::TypeVar(root),
                         InferTy::IntVar(_) => InferTy::IntVar(root),
                         InferTy::FloatVar(_) => InferTy::FloatVar(root),
+                        InferTy::MaybeNeverTypeVar(_) => InferTy::MaybeNeverTypeVar(root),
                     };
                     let position = self.add(free_var);
                     Ty::Bound(position as u32)
diff --git a/crates/ra_hir/src/ty/tests.rs b/crates/ra_hir/src/ty/tests.rs
index 2ce0039b1..081bfe37c 100644
--- a/crates/ra_hir/src/ty/tests.rs
+++ b/crates/ra_hir/src/ty/tests.rs
@@ -20,6 +20,8 @@ use crate::{
 // against snapshots of the expected results using insta. Use cargo-insta to
 // update the snapshots.
 
+mod never_type;
+
 #[test]
 fn infer_await() {
     let (mut db, pos) = MockDatabase::with_position(
@@ -1078,6 +1080,42 @@ fn test(i: i32) {
 }
 
 #[test]
+fn coerce_merge_one_by_one1() {
+    covers!(coerce_merge_fail_fallback);
+
+    assert_snapshot!(
+        infer(r#"
+fn test() {
+    let t = &mut 1;
+    let x = match 1 {
+        1 => t as *mut i32,
+        2 => t as &i32,
+        _ => t as *const i32,
+    };
+}
+"#),
+        @r###"
+    [11; 145) '{     ...  }; }': ()
+    [21; 22) 't': &mut i32
+    [25; 31) '&mut 1': &mut i32
+    [30; 31) '1': i32
+    [41; 42) 'x': *const i32
+    [45; 142) 'match ...     }': *const i32
+    [51; 52) '1': i32
+    [63; 64) '1': i32
+    [68; 69) 't': &mut i32
+    [68; 81) 't as *mut i32': *mut i32
+    [91; 92) '2': i32
+    [96; 97) 't': &mut i32
+    [96; 105) 't as &i32': &i32
+    [115; 116) '_': i32
+    [120; 121) 't': &mut i32
+    [120; 135) 't as *const i32': *const i32
+    "###
+    );
+}
+
+#[test]
 fn bug_484() {
     assert_snapshot!(
         infer(r#"
@@ -2458,7 +2496,6 @@ fn extra_compiler_flags() {
 }
 "#),
         @r###"
-
     [27; 323) '{     ...   } }': ()
     [33; 321) 'for co...     }': ()
     [37; 44) 'content': &{unknown}
@@ -2472,8 +2509,8 @@ fn extra_compiler_flags() {
     [135; 167) '{     ...     }': &&{unknown}
     [149; 157) '&content': &&{unknown}
     [150; 157) 'content': &{unknown}
-    [182; 189) 'content': &&{unknown}
-    [192; 314) 'if ICE...     }': &&{unknown}
+    [182; 189) 'content': &{unknown}
+    [192; 314) 'if ICE...     }': &{unknown}
     [195; 232) 'ICE_RE..._VALUE': {unknown}
     [195; 248) 'ICE_RE...&name)': bool
     [242; 247) '&name': &&&{unknown}
@@ -4683,121 +4720,3 @@ fn no_such_field_diagnostics() {
     "###
     );
 }
-
-mod branching_with_never_tests {
-    use super::type_at;
-
-    #[test]
-    fn if_never() {
-        let t = type_at(
-            r#"
-//- /main.rs
-fn test() {
-    let i = if true {
-        loop {}
-    } else {
-        3.0
-    };
-    i<|>
-    ()
-}
-"#,
-        );
-        assert_eq!(t, "f64");
-    }
-
-    #[test]
-    fn if_else_never() {
-        let t = type_at(
-            r#"
-//- /main.rs
-fn test(input: bool) {
-    let i = if input {
-        2.0
-    } else {
-        return
-    };
-    i<|>
-    ()
-}
-"#,
-        );
-        assert_eq!(t, "f64");
-    }
-
-    #[test]
-    fn match_first_arm_never() {
-        let t = type_at(
-            r#"
-//- /main.rs
-fn test(a: i32) {
-    let i = match a {
-        1 => return,
-        2 => 2.0,
-        3 => loop {},
-        _ => 3.0,
-    };
-    i<|>
-    ()
-}
-"#,
-        );
-        assert_eq!(t, "f64");
-    }
-
-    #[test]
-    fn match_second_arm_never() {
-        let t = type_at(
-            r#"
-//- /main.rs
-fn test(a: i32) {
-    let i = match a {
-        1 => 3.0,
-        2 => loop {},
-        3 => 3.0,
-        _ => return,
-    };
-    i<|>
-    ()
-}
-"#,
-        );
-        assert_eq!(t, "f64");
-    }
-
-    #[test]
-    fn match_all_arms_never() {
-        let t = type_at(
-            r#"
-//- /main.rs
-fn test(a: i32) {
-    let i = match a {
-        2 => return,
-        _ => loop {},
-    };
-    i<|>
-    ()
-}
-"#,
-        );
-        assert_eq!(t, "!");
-    }
-
-    #[test]
-    fn match_no_never_arms() {
-        let t = type_at(
-            r#"
-//- /main.rs
-fn test(a: i32) {
-    let i = match a {
-        2 => 2.0,
-        _ => 3.0,
-    };
-    i<|>
-    ()
-}
-"#,
-        );
-        assert_eq!(t, "f64");
-    }
-}
diff --git a/crates/ra_hir/src/ty/tests/never_type.rs b/crates/ra_hir/src/ty/tests/never_type.rs
new file mode 100644
index 000000000..b9af918e9
--- /dev/null
+++ b/crates/ra_hir/src/ty/tests/never_type.rs
@@ -0,0 +1,258 @@
+use super::type_at;
+
+#[test]
+fn infer_never1() {
+    let t = type_at(
+        r#"
+//- /main.rs
+fn test() {
+    let t = return;
+    t<|>;
+}
+"#,
+    );
+    assert_eq!(t, "!");
+}
+
+#[test]
+fn infer_never2() {
+    let t = type_at(
+        r#"
+//- /main.rs
+trait Foo { fn gen() -> Self; }
+impl Foo for ! { fn gen() -> Self { loop {} } }
+impl Foo for () { fn gen() -> Self { loop {} } }
+
+fn test() {
+    let a = Foo::gen();
+    if false { a } else { loop {} };
+    a<|>;
+}
+"#,
+    );
+    assert_eq!(t, "!");
+}
+
+#[test]
+fn infer_never3() {
+    let t = type_at(
+        r#"
+//- /main.rs
+trait Foo { fn gen() -> Self; }
+impl Foo for ! { fn gen() -> Self { loop {} } }
+impl Foo for () { fn gen() -> Self { loop {} } }
+
+fn test() {
+    let a = Foo::gen();
+    if false { loop {} } else { a };
+    a<|>;
+}
+"#,
+    );
+    assert_eq!(t, "!");
+}
+
+#[test]
+fn never_type_in_generic_args() {
+    let t = type_at(
+        r#"
+//- /main.rs
+enum Option<T> { None, Some(T) }
+
+fn test() {
+    let a = if true { Option::None } else { Option::Some(return) };
+    a<|>;
+}
+"#,
+    );
+    assert_eq!(t, "Option<!>");
+}
+
+#[test]
+fn never_type_can_be_reinferred1() {
+    let t = type_at(
+        r#"
+//- /main.rs
+trait Foo { fn gen() -> Self; }
+impl Foo for ! { fn gen() -> Self { loop {} } }
+impl Foo for () { fn gen() -> Self { loop {} } }
+
+fn test() {
+    let a = Foo::gen();
+    if false { loop {} } else { a };
+    a<|>;
+    if false { a };
+}
+"#,
+    );
+    assert_eq!(t, "()");
+}
+
+#[test]
+fn never_type_can_be_reinferred2() {
+    let t = type_at(
+        r#"
+//- /main.rs
+enum Option<T> { None, Some(T) }
+
+fn test() {
+    let a = if true { Option::None } else { Option::Some(return) };
+    a<|>;
+    match 42 {
+        42 => a,
+        _ => Option::Some(42),
+    };
+}
+"#,
+    );
+    assert_eq!(t, "Option<i32>");
+}
+#[test]
+fn never_type_can_be_reinferred3() {
+    let t = type_at(
+        r#"
+//- /main.rs
+enum Option<T> { None, Some(T) }
+
+fn test() {
+    let a = if true { Option::None } else { Option::Some(return) };
+    a<|>;
+    match 42 {
+        42 => a,
+        _ => Option::Some("str"),
+    };
+}
+"#,
+    );
+    assert_eq!(t, "Option<&str>");
+}
+
+#[test]
+fn match_no_arm() {
+    let t = type_at(
+        r#"
+//- /main.rs
+enum Void {}
+
+fn test(a: Void) {
+    let t = match a {};
+    t<|>;
+}
+"#,
+    );
+    assert_eq!(t, "!");
+}
+
+#[test]
+fn if_never() {
+    let t = type_at(
+        r#"
+//- /main.rs
+fn test() {
+    let i = if true {
+        loop {}
+    } else {
+        3.0
+    };
+    i<|>
+    ()
+}
+"#,
+    );
+    assert_eq!(t, "f64");
+}
+
+#[test]
+fn if_else_never() {
+    let t = type_at(
+        r#"
+//- /main.rs
+fn test(input: bool) {
+    let i = if input {
+        2.0
+    } else {
+        return
+    };
+    i<|>
+    ()
+}
+"#,
+    );
+    assert_eq!(t, "f64");
+}
+
+#[test]
+fn match_first_arm_never() {
+    let t = type_at(
+        r#"
+//- /main.rs
+fn test(a: i32) {
+    let i = match a {
+        1 => return,
+        2 => 2.0,
+        3 => loop {},
+        _ => 3.0,
+    };
+    i<|>
+    ()
+}
+"#,
+    );
+    assert_eq!(t, "f64");
+}
+
+#[test]
+fn match_second_arm_never() {
+    let t = type_at(
+        r#"
+//- /main.rs
+fn test(a: i32) {
+    let i = match a {
+        1 => 3.0,
+        2 => loop {},
+        3 => 3.0,
+        _ => return,
+    };
+    i<|>
+    ()
+}
+"#,
+    );
+    assert_eq!(t, "f64");
+}
+
+#[test]
+fn match_all_arms_never() {
+    let t = type_at(
+        r#"
+//- /main.rs
+fn test(a: i32) {
+    let i = match a {
+        2 => return,
+        _ => loop {},
+    };
+    i<|>
+    ()
+}
+"#,
+    );
+    assert_eq!(t, "!");
+}
+
+#[test]
+fn match_no_never_arms() {
+    let t = type_at(
+        r#"
+//- /main.rs
+fn test(a: i32) {
+    let i = match a {
+        2 => 2.0,
+        _ => 3.0,
+    };
+    i<|>
+    ()
+}
+"#,
+    );
+    assert_eq!(t, "f64");
+}