10 files changed, 326 insertions, 32 deletions

diff --git a/crates/ra_hir/src/code_model_api.rs b/crates/ra_hir/src/code_model_api.rs
index cafc5279d..19f103855 100644
--- a/crates/ra_hir/src/code_model_api.rs
+++ b/crates/ra_hir/src/code_model_api.rs
@@ -1,7 +1,7 @@
 use std::sync::Arc;
 
 use relative_path::RelativePathBuf;
-use ra_db::{CrateId, FileId};
+use ra_db::{CrateId, FileId, SourceRootId};
 use ra_syntax::{ast::self, TreeArc, SyntaxNode};
 
 use crate::{
@@ -16,7 +16,7 @@ use crate::{
     docs::{Documentation, Docs, docs_from_ast},
     module_tree::ModuleId,
     ids::{FunctionId, StructId, EnumId, AstItemDef, ConstId, StaticId, TraitId, TypeId},
-    impl_block::ImplId,
+    impl_block::{ImplId, ImplBlock},
     resolve::Resolver,
 };
 
@@ -44,6 +44,15 @@ impl Crate {
     pub fn root_module(&self, db: &impl PersistentHirDatabase) -> Option<Module> {
         self.root_module_impl(db)
     }
+
+    // TODO: should this be in source_binder?
+    pub fn source_root_crates(
+        db: &impl PersistentHirDatabase,
+        source_root: SourceRootId,
+    ) -> Vec<Crate> {
+        let crate_ids = db.source_root_crates(source_root);
+        crate_ids.iter().map(|&crate_id| Crate { crate_id }).collect()
+    }
 }
 
 #[derive(Debug)]
@@ -168,6 +177,27 @@ impl Module {
         let item_map = db.item_map(self.krate);
         Resolver::default().push_module_scope(item_map, *self)
     }
+
+    pub fn declarations(self, db: &impl HirDatabase) -> Vec<ModuleDef> {
+        let (lowered_module, _) = db.lower_module(self);
+        lowered_module
+            .declarations
+            .values()
+            .cloned()
+            .flat_map(|per_ns| {
+                per_ns.take_types().into_iter().chain(per_ns.take_values().into_iter())
+            })
+            .collect()
+    }
+
+    pub fn impl_blocks(self, db: &impl HirDatabase) -> Vec<ImplBlock> {
+        let module_impl_blocks = db.impls_in_module(self);
+        module_impl_blocks
+            .impls
+            .iter()
+            .map(|(impl_id, _)| ImplBlock::from_id(module_impl_blocks.clone(), impl_id))
+            .collect()
+    }
 }
 
 impl Docs for Module {
diff --git a/crates/ra_hir/src/expr.rs b/crates/ra_hir/src/expr.rs
index 4e61d87ff..4e73590d0 100644
--- a/crates/ra_hir/src/expr.rs
+++ b/crates/ra_hir/src/expr.rs
@@ -70,6 +70,14 @@ impl Body {
         self.owner
     }
 
+    pub fn exprs(&self) -> impl Iterator<Item = (ExprId, &Expr)> {
+        self.exprs.iter()
+    }
+
+    pub fn pats(&self) -> impl Iterator<Item = (PatId, &Pat)> {
+        self.pats.iter()
+    }
+
     pub fn syntax_mapping(&self, db: &impl HirDatabase) -> Arc<BodySyntaxMapping> {
         db.body_syntax_mapping(self.owner)
     }
@@ -831,18 +839,18 @@ impl ExprCollector {
                     p.field_pat_list().expect("every struct should have a field list");
                 let mut fields: Vec<_> = field_pat_list
                     .bind_pats()
-                    .map(|bind_pat| {
+                    .filter_map(|bind_pat| {
                         let ast_pat = ast::Pat::cast(bind_pat.syntax()).expect("bind pat is a pat");
                         let pat = self.collect_pat(ast_pat);
-                        let name = bind_pat.name().expect("bind pat has a name").as_name();
-                        FieldPat { name, pat }
+                        let name = bind_pat.name()?.as_name();
+                        Some(FieldPat { name, pat })
                     })
                     .collect();
-                let iter = field_pat_list.field_pats().map(|f| {
-                    let ast_pat = f.pat().expect("field pat always contains a pattern");
+                let iter = field_pat_list.field_pats().filter_map(|f| {
+                    let ast_pat = f.pat()?;
                     let pat = self.collect_pat(ast_pat);
-                    let name = f.name().expect("field pats always have a name").as_name();
-                    FieldPat { name, pat }
+                    let name = f.name()?.as_name();
+                    Some(FieldPat { name, pat })
                 });
                 fields.extend(iter);
 
@@ -850,6 +858,7 @@ impl ExprCollector {
             }
 
             // TODO: implement
+            ast::PatKind::LiteralPat(_) => Pat::Missing,
             ast::PatKind::SlicePat(_) | ast::PatKind::RangePat(_) => Pat::Missing,
         };
         let syntax_ptr = SyntaxNodePtr::new(pat.syntax());
diff --git a/crates/ra_hir/src/marks.rs b/crates/ra_hir/src/marks.rs
index d704c3adb..aba0c9968 100644
--- a/crates/ra_hir/src/marks.rs
+++ b/crates/ra_hir/src/marks.rs
@@ -3,4 +3,5 @@ test_utils::marks!(
     item_map_enum_importing
     type_var_cycles_resolve_completely
     type_var_cycles_resolve_as_possible
+    type_var_resolves_to_int_var
 );
diff --git a/crates/ra_hir/src/ty.rs b/crates/ra_hir/src/ty.rs
index 453520bbe..2dc1de41a 100644
--- a/crates/ra_hir/src/ty.rs
+++ b/crates/ra_hir/src/ty.rs
@@ -449,6 +449,49 @@ impl Ty {
         Ty::Tuple(Arc::new([]))
     }
 
+    pub fn walk(&self, f: &mut impl FnMut(&Ty)) {
+        f(self);
+        match self {
+            Ty::Slice(t) | Ty::Array(t) => t.walk(f),
+            Ty::RawPtr(t, _) => t.walk(f),
+            Ty::Ref(t, _) => t.walk(f),
+            Ty::Tuple(ts) => {
+                for t in ts.iter() {
+                    t.walk(f);
+                }
+            }
+            Ty::FnPtr(sig) => {
+                for input in &sig.input {
+                    input.walk(f);
+                }
+                sig.output.walk(f);
+            }
+            Ty::FnDef { substs, sig, .. } => {
+                for input in &sig.input {
+                    input.walk(f);
+                }
+                sig.output.walk(f);
+                for t in substs.0.iter() {
+                    t.walk(f);
+                }
+            }
+            Ty::Adt { substs, .. } => {
+                for t in substs.0.iter() {
+                    t.walk(f);
+                }
+            }
+            Ty::Bool
+            | Ty::Char
+            | Ty::Int(_)
+            | Ty::Float(_)
+            | Ty::Str
+            | Ty::Never
+            | Ty::Param { .. }
+            | Ty::Infer(_)
+            | Ty::Unknown => {}
+        }
+    }
+
     fn walk_mut(&mut self, f: &mut impl FnMut(&mut Ty)) {
         f(self);
         match self {
@@ -491,7 +534,15 @@ impl Ty {
                 }
                 substs.0 = v.into();
             }
-            _ => {}
+            Ty::Bool
+            | Ty::Char
+            | Ty::Int(_)
+            | Ty::Float(_)
+            | Ty::Str
+            | Ty::Never
+            | Ty::Param { .. }
+            | Ty::Infer(_)
+            | Ty::Unknown => {}
         }
     }
 
@@ -879,11 +930,22 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
         ty
     }
 
-    fn unify_substs(&mut self, substs1: &Substs, substs2: &Substs) -> bool {
-        substs1.0.iter().zip(substs2.0.iter()).all(|(t1, t2)| self.unify(t1, t2))
+    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);
@@ -904,13 +966,15 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
             (
                 Ty::Adt { def_id: def_id1, substs: substs1, .. },
                 Ty::Adt { def_id: def_id2, substs: substs2, .. },
-            ) if def_id1 == def_id2 => self.unify_substs(substs1, substs2),
-            (Ty::Slice(t1), Ty::Slice(t2)) => self.unify(t1, t2),
-            (Ty::RawPtr(t1, m1), Ty::RawPtr(t2, m2)) if m1 == m2 => self.unify(t1, t2),
-            (Ty::Ref(t1, m1), Ty::Ref(t2, m2)) if m1 == m2 => self.unify(t1, t2),
+            ) if def_id1 == def_id2 => self.unify_substs(substs1, substs2, depth + 1),
+            (Ty::Slice(t1), Ty::Slice(t2)) => self.unify_inner(t1, t2, depth + 1),
+            (Ty::RawPtr(t1, m1), Ty::RawPtr(t2, m2)) if m1 == m2 => {
+                self.unify_inner(t1, t2, depth + 1)
+            }
+            (Ty::Ref(t1, m1), Ty::Ref(t2, m2)) if m1 == m2 => self.unify_inner(t1, t2, depth + 1),
             (Ty::FnPtr(sig1), Ty::FnPtr(sig2)) if sig1 == sig2 => true,
             (Ty::Tuple(ts1), Ty::Tuple(ts2)) if ts1.len() == ts2.len() => {
-                ts1.iter().zip(ts2.iter()).all(|(t1, t2)| self.unify(t1, t2))
+                ts1.iter().zip(ts2.iter()).all(|(t1, t2)| self.unify_inner(t1, t2, depth + 1))
             }
             (Ty::Infer(InferTy::TypeVar(tv1)), Ty::Infer(InferTy::TypeVar(tv2)))
             | (Ty::Infer(InferTy::IntVar(tv1)), Ty::Infer(InferTy::IntVar(tv2)))
@@ -989,19 +1053,30 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
     /// 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> {
-        match ty {
-            Ty::Infer(tv) => {
-                let inner = tv.to_inner();
-                match self.var_unification_table.probe_value(inner).known() {
-                    Some(known_ty) => {
-                        // The known_ty can't be a type var itself
-                        Cow::Owned(known_ty.clone())
+        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.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,
                     }
-                    _ => Cow::Borrowed(ty),
                 }
+                _ => return ty,
             }
-            _ => Cow::Borrowed(ty),
         }
+        log::error!("Inference variable still not resolved: {:?}", ty);
+        ty
     }
 
     /// Resolves the type completely; type variables without known type are
@@ -1185,17 +1260,21 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
                 self.infer_path_expr(&resolver, &path).unwrap_or(Ty::Unknown)
             }
             Pat::Bind { mode, name: _name, subpat } => {
-                let subty = if let Some(subpat) = subpat {
+                let inner_ty = if let Some(subpat) = subpat {
                     self.infer_pat(*subpat, expected)
                 } else {
                     expected.clone()
                 };
+                let inner_ty = self.insert_type_vars_shallow(inner_ty);
 
-                match mode {
-                    BindingAnnotation::Ref => Ty::Ref(subty.into(), Mutability::Shared),
-                    BindingAnnotation::RefMut => Ty::Ref(subty.into(), Mutability::Mut),
-                    BindingAnnotation::Mutable | BindingAnnotation::Unannotated => subty,
-                }
+                let bound_ty = match mode {
+                    BindingAnnotation::Ref => Ty::Ref(inner_ty.clone().into(), Mutability::Shared),
+                    BindingAnnotation::RefMut => Ty::Ref(inner_ty.clone().into(), Mutability::Mut),
+                    BindingAnnotation::Mutable | BindingAnnotation::Unannotated => inner_ty.clone(),
+                };
+                let bound_ty = self.resolve_ty_as_possible(&mut vec![], bound_ty);
+                self.write_pat_ty(pat, bound_ty);
+                return inner_ty;
             }
             _ => Ty::Unknown,
         };
diff --git a/crates/ra_hir/src/ty/snapshots/tests__infer_std_crash_1.snap b/crates/ra_hir/src/ty/snapshots/tests__infer_std_crash_1.snap
new file mode 100644
index 000000000..4b99788e4
--- /dev/null
+++ b/crates/ra_hir/src/ty/snapshots/tests__infer_std_crash_1.snap
@@ -0,0 +1,13 @@
+---
+created: "2019-02-09T16:56:24.803326529Z"
+creator: [email protected]
+source: crates/ra_hir/src/ty/tests.rs
+expression: "&result"
+---
+[54; 139) '{     ...   } }': ()
+[60; 137) 'match ...     }': ()
+[66; 83) 'someth...nknown': Maybe<[unknown]>
+[94; 124) 'Maybe:...thing)': Maybe<[unknown]>
+[106; 123) 'ref mu...ething': &mut [unknown]
+[128; 130) '()': ()
+
diff --git a/crates/ra_hir/src/ty/snapshots/tests__infer_std_crash_2.snap b/crates/ra_hir/src/ty/snapshots/tests__infer_std_crash_2.snap
new file mode 100644
index 000000000..fd0b39b7d
--- /dev/null
+++ b/crates/ra_hir/src/ty/snapshots/tests__infer_std_crash_2.snap
@@ -0,0 +1,14 @@
+---
+created: "2019-02-09T17:03:11.974225590Z"
+creator: [email protected]
+source: crates/ra_hir/src/ty/tests.rs
+expression: "&result"
+---
+[23; 53) '{     ...n']; }': ()
+[29; 50) '&[0, b...b'\n']': &[u8]
+[30; 50) '[0, b'...b'\n']': [u8]
+[31; 32) '0': u8
+[34; 39) 'b'\n'': u8
+[41; 42) '1': u8
+[44; 49) 'b'\n'': u8
+
diff --git a/crates/ra_hir/src/ty/snapshots/tests__infer_std_crash_3.snap b/crates/ra_hir/src/ty/snapshots/tests__infer_std_crash_3.snap
new file mode 100644
index 000000000..d15b77e17
--- /dev/null
+++ b/crates/ra_hir/src/ty/snapshots/tests__infer_std_crash_3.snap
@@ -0,0 +1,13 @@
+---
+created: "2019-02-09T18:02:37.377591660Z"
+creator: [email protected]
+source: crates/ra_hir/src/ty/tests.rs
+expression: "&result"
+---
+[18; 102) '{     ...   } }': ()
+[24; 100) 'match ...     }': ()
+[42; 88) 'SizeSk...tail }': [unknown]
+[76; 80) 'true': [unknown]
+[82; 86) 'tail': [unknown]
+[92; 94) '{}': ()
+
diff --git a/crates/ra_hir/src/ty/snapshots/tests__infer_std_crash_4.snap b/crates/ra_hir/src/ty/snapshots/tests__infer_std_crash_4.snap
new file mode 100644
index 000000000..fb31883ce
--- /dev/null
+++ b/crates/ra_hir/src/ty/snapshots/tests__infer_std_crash_4.snap
@@ -0,0 +1,16 @@
+---
+created: "2019-02-09T19:55:39.712470520Z"
+creator: [email protected]
+source: crates/ra_hir/src/ty/tests.rs
+expression: "&result"
+---
+[25; 110) '{     ...   } }': ()
+[31; 108) 'match ...     }': ()
+[37; 42) '*self': [unknown]
+[38; 42) 'self': [unknown]
+[53; 95) 'Borrow...), ..}': [unknown]
+[74; 77) 'box': [unknown]
+[78; 87) 'Primitive': [unknown]
+[88; 89) 'p': [unknown]
+[99; 101) '{}': ()
+
diff --git a/crates/ra_hir/src/ty/snapshots/tests__infer_std_crash_5.snap b/crates/ra_hir/src/ty/snapshots/tests__infer_std_crash_5.snap
new file mode 100644
index 000000000..6bbf59fb6
--- /dev/null
+++ b/crates/ra_hir/src/ty/snapshots/tests__infer_std_crash_5.snap
@@ -0,0 +1,30 @@
+---
+created: "2019-02-09T20:28:37.294693728Z"
+creator: [email protected]
+source: crates/ra_hir/src/ty/tests.rs
+expression: "&result"
+---
+[27; 323) '{     ...   } }': ()
+[33; 321) 'for co...     }': ()
+[37; 44) 'content': &[unknown]
+[48; 61) 'doesnt_matter': [unknown]
+[62; 321) '{     ...     }': ()
+[76; 80) 'name': &&[unknown]
+[83; 167) 'if doe...     }': &&[unknown]
+[86; 99) 'doesnt_matter': bool
+[100; 129) '{     ...     }': &&[unknown]
+[114; 119) 'first': &&[unknown]
+[135; 167) '{     ...     }': &&[unknown]
+[149; 157) '&content': &&[unknown]
+[150; 157) 'content': &[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]
+[243; 247) 'name': &&[unknown]
+[249; 277) '{     ...     }': &&[unknown]
+[263; 267) 'name': &&[unknown]
+[283; 314) '{     ...     }': &[unknown]
+[297; 304) 'content': &[unknown]
+
diff --git a/crates/ra_hir/src/ty/tests.rs b/crates/ra_hir/src/ty/tests.rs
index 2621d1b55..e64fd2749 100644
--- a/crates/ra_hir/src/ty/tests.rs
+++ b/crates/ra_hir/src/ty/tests.rs
@@ -630,6 +630,95 @@ fn test() {
     );
 }
 
+#[test]
+fn infer_std_crash_1() {
+    // caused stack overflow, taken from std
+    check_inference(
+        "infer_std_crash_1",
+        r#"
+enum Maybe<T> {
+    Real(T),
+    Fake,
+}
+
+fn write() {
+    match something_unknown {
+        Maybe::Real(ref mut something) => (),
+    }
+}
+"#,
+    );
+}
+
+#[test]
+fn infer_std_crash_2() {
+    covers!(type_var_resolves_to_int_var);
+    // caused "equating two type variables, ...", taken from std
+    check_inference(
+        "infer_std_crash_2",
+        r#"
+fn test_line_buffer() {
+    &[0, b'\n', 1, b'\n'];
+}
+"#,
+    );
+}
+
+#[test]
+fn infer_std_crash_3() {
+    // taken from rustc
+    check_inference(
+        "infer_std_crash_3",
+        r#"
+pub fn compute() {
+    match _ {
+        SizeSkeleton::Pointer { non_zero: true, tail } => {}
+    }
+}
+"#,
+    );
+}
+
+#[test]
+fn infer_std_crash_4() {
+    // taken from rustc
+    check_inference(
+        "infer_std_crash_4",
+        r#"
+pub fn primitive_type() {
+    match *self {
+        BorrowedRef { type_: box Primitive(p), ..} => {},
+    }
+}
+"#,
+    );
+}
+
+#[test]
+fn infer_std_crash_5() {
+    // taken from rustc
+    check_inference(
+        "infer_std_crash_5",
+        r#"
+fn extra_compiler_flags() {
+    for content in doesnt_matter {
+        let name = if doesnt_matter {
+            first
+        } else {
+            &content
+        };
+
+        let content = if ICE_REPORT_COMPILER_FLAGS_STRIP_VALUE.contains(&name) {
+            name
+        } else {
+            content
+        };
+    }
+}
+"#,
+    );
+}
+
 fn infer(content: &str) -> String {
     let (db, _, file_id) = MockDatabase::with_single_file(content);
     let source_file = db.parse(file_id);