117 files changed, 6137 insertions, 1919 deletions
diff --git a/crates/paths/src/lib.rs b/crates/paths/src/lib.rs
index c7ce0c42f..190c50913 100644
--- a/crates/paths/src/lib.rs
+++ b/crates/paths/src/lib.rs
@@ -2,7 +2,7 @@
 //! relative paths.
 use std::{
    convert::{TryFrom, TryInto},
-    ops,
+    io, ops,
    path::{Component, Path, PathBuf},
 };
@@ -46,6 +46,9 @@ impl TryFrom<&str> for AbsPathBuf {
 }
 impl AbsPathBuf {
+    pub fn canonicalized(path: &Path) -> io::Result<AbsPathBuf> {
+        path.canonicalize().map(|it| AbsPathBuf::try_from(it).unwrap())
+    }
    pub fn as_path(&self) -> &AbsPath {
        AbsPath::new_unchecked(self.0.as_path())
    }
diff --git a/crates/ra_assists/src/assist_context.rs b/crates/ra_assists/src/assist_context.rs
index edd8255f4..ee614de72 100644
--- a/crates/ra_assists/src/assist_context.rs
+++ b/crates/ra_assists/src/assist_context.rs
@@ -252,7 +252,7 @@ impl AssistBuilder {
    pub(crate) fn rewrite(&mut self, rewriter: SyntaxRewriter) {
        let node = rewriter.rewrite_root().unwrap();
        let new = rewriter.rewrite(&node);
-        algo::diff(&node, &new).into_text_edit(&mut self.edit)
+        algo::diff(&node, &new).into_text_edit(&mut self.edit);
    }
    // FIXME: kill this API
diff --git a/crates/ra_assists/src/handlers/replace_qualified_name_with_use.rs b/crates/ra_assists/src/handlers/replace_qualified_name_with_use.rs
index 0197a8cf0..b4784c333 100644
--- a/crates/ra_assists/src/handlers/replace_qualified_name_with_use.rs
+++ b/crates/ra_assists/src/handlers/replace_qualified_name_with_use.rs
@@ -1,7 +1,10 @@
 use hir;
-use ra_syntax::{ast, AstNode, SmolStr, TextRange};
+use ra_syntax::{algo::SyntaxRewriter, ast, match_ast, AstNode, SmolStr, SyntaxNode};
-use crate::{utils::insert_use_statement, AssistContext, AssistId, Assists};
+use crate::{
+    utils::{find_insert_use_container, insert_use_statement},
+    AssistContext, AssistId, Assists,
+};
 // Assist: replace_qualified_name_with_use
 //
@@ -39,16 +42,18 @@ pub(crate) fn replace_qualified_name_with_use(
        target,
        |builder| {
            let path_to_import = hir_path.mod_path().clone();
+            let container = match find_insert_use_container(path.syntax(), ctx) {
+                Some(c) => c,
+                None => return,
+            };
            insert_use_statement(path.syntax(), &path_to_import, ctx, builder.text_edit_builder());
-            if let Some(last) = path.segment() {
+            // Now that we've brought the name into scope, re-qualify all paths that could be
-                // Here we are assuming the assist will provide a correct use statement
+            // affected (that is, all paths inside the node we added the `use` to).
-                // so we can delete the path qualifier
+            let mut rewriter = SyntaxRewriter::default();
-                builder.delete(TextRange::new(
+            let syntax = container.either(|l| l.syntax().clone(), |r| r.syntax().clone());
-                    path.syntax().text_range().start(),
+            shorten_paths(&mut rewriter, syntax, path);
-                    last.syntax().text_range().start(),
+            builder.rewrite(rewriter);
-                ));
-            }
        },
    )
 }
@@ -73,6 +78,69 @@ fn collect_hir_path_segments(path: &hir::Path) -> Option<Vec<SmolStr>> {
    Some(ps)
 }
+/// Adds replacements to `re` that shorten `path` in all descendants of `node`.
+fn shorten_paths(rewriter: &mut SyntaxRewriter<'static>, node: SyntaxNode, path: ast::Path) {
+    for child in node.children() {
+        match_ast! {
+            match child {
+                // Don't modify `use` items, as this can break the `use` item when injecting a new
+                // import into the use tree.
+                ast::UseItem(_it) => continue,
+                // Don't descend into submodules, they don't have the same `use` items in scope.
+                ast::Module(_it) => continue,
+                ast::Path(p) => {
+                    match maybe_replace_path(rewriter, p.clone(), path.clone()) {
+                        Some(()) => {},
+                        None => shorten_paths(rewriter, p.syntax().clone(), path.clone()),
+                    }
+                },
+                _ => shorten_paths(rewriter, child, path.clone()),
+            }
+        }
+    }
+}
+fn maybe_replace_path(
+    rewriter: &mut SyntaxRewriter<'static>,
+    path: ast::Path,
+    target: ast::Path,
+) -> Option<()> {
+    if !path_eq(path.clone(), target.clone()) {
+        return None;
+    }
+    // Shorten `path`, leaving only its last segment.
+    if let Some(parent) = path.qualifier() {
+        rewriter.delete(parent.syntax());
+    }
+    if let Some(double_colon) = path.coloncolon_token() {
+        rewriter.delete(&double_colon);
+    }
+    Some(())
+}
+fn path_eq(lhs: ast::Path, rhs: ast::Path) -> bool {
+    let mut lhs_curr = lhs;
+    let mut rhs_curr = rhs;
+    loop {
+        match (lhs_curr.segment(), rhs_curr.segment()) {
+            (Some(lhs), Some(rhs)) if lhs.syntax().text() == rhs.syntax().text() => (),
+            _ => return false,
+        }
+        match (lhs_curr.qualifier(), rhs_curr.qualifier()) {
+            (Some(lhs), Some(rhs)) => {
+                lhs_curr = lhs;
+                rhs_curr = rhs;
+            }
+            (None, None) => return true,
+            _ => return false,
+        }
+    }
+}
 #[cfg(test)]
 mod tests {
    use crate::tests::{check_assist, check_assist_not_applicable};
@@ -83,10 +151,10 @@ mod tests {
    fn test_replace_add_use_no_anchor() {
        check_assist(
            replace_qualified_name_with_use,
-            "
+            r"
 std::fmt::Debug<|>
    ",
-            "
+            r"
 use std::fmt::Debug;
 Debug
@@ -97,13 +165,13 @@ Debug
    fn test_replace_add_use_no_anchor_with_item_below() {
        check_assist(
            replace_qualified_name_with_use,
-            "
+            r"
 std::fmt::Debug<|>
 fn main() {
 }
    ",
-            "
+            r"
 use std::fmt::Debug;
 Debug
@@ -118,13 +186,13 @@ fn main() {
    fn test_replace_add_use_no_anchor_with_item_above() {
        check_assist(
            replace_qualified_name_with_use,
-            "
+            r"
 fn main() {
 }
 std::fmt::Debug<|>
    ",
-            "
+            r"
 use std::fmt::Debug;
 fn main() {
@@ -139,10 +207,10 @@ Debug
    fn test_replace_add_use_no_anchor_2seg() {
        check_assist(
            replace_qualified_name_with_use,
-            "
+            r"
 std::fmt<|>::Debug
    ",
-            "
+            r"
 use std::fmt;
 fmt::Debug
@@ -154,13 +222,13 @@ fmt::Debug
    fn test_replace_add_use() {
        check_assist(
            replace_qualified_name_with_use,
-            "
+            r"
 use stdx;
 impl std::fmt::Debug<|> for Foo {
 }
    ",
-            "
+            r"
 use stdx;
 use std::fmt::Debug;
@@ -174,11 +242,11 @@ impl Debug for Foo {
    fn test_replace_file_use_other_anchor() {
        check_assist(
            replace_qualified_name_with_use,
-            "
+            r"
 impl std::fmt::Debug<|> for Foo {
 }
    ",
-            "
+            r"
 use std::fmt::Debug;
 impl Debug for Foo {
@@ -191,11 +259,11 @@ impl Debug for Foo {
    fn test_replace_add_use_other_anchor_indent() {
        check_assist(
            replace_qualified_name_with_use,
-            "
+            r"
    impl std::fmt::Debug<|> for Foo {
    }
    ",
-            "
+            r"
    use std::fmt::Debug;
    impl Debug for Foo {
@@ -208,13 +276,13 @@ impl Debug for Foo {
    fn test_replace_split_different() {
        check_assist(
            replace_qualified_name_with_use,
-            "
+            r"
 use std::fmt;
 impl std::io<|> for Foo {
 }
    ",
-            "
+            r"
 use std::{io, fmt};
 impl io for Foo {
@@ -227,13 +295,13 @@ impl io for Foo {
    fn test_replace_split_self_for_use() {
        check_assist(
            replace_qualified_name_with_use,
-            "
+            r"
 use std::fmt;
 impl std::fmt::Debug<|> for Foo {
 }
    ",
-            "
+            r"
 use std::fmt::{self, Debug, };
 impl Debug for Foo {
@@ -246,13 +314,13 @@ impl Debug for Foo {
    fn test_replace_split_self_for_target() {
        check_assist(
            replace_qualified_name_with_use,
-            "
+            r"
 use std::fmt::Debug;
 impl std::fmt<|> for Foo {
 }
    ",
-            "
+            r"
 use std::fmt::{self, Debug};
 impl fmt for Foo {
@@ -265,13 +333,13 @@ impl fmt for Foo {
    fn test_replace_add_to_nested_self_nested() {
        check_assist(
            replace_qualified_name_with_use,
-            "
+            r"
 use std::fmt::{Debug, nested::{Display}};
 impl std::fmt::nested<|> for Foo {
 }
 ",
-            "
+            r"
 use std::fmt::{Debug, nested::{Display, self}};
 impl nested for Foo {
@@ -284,13 +352,13 @@ impl nested for Foo {
    fn test_replace_add_to_nested_self_already_included() {
        check_assist(
            replace_qualified_name_with_use,
-            "
+            r"
 use std::fmt::{Debug, nested::{self, Display}};
 impl std::fmt::nested<|> for Foo {
 }
 ",
-            "
+            r"
 use std::fmt::{Debug, nested::{self, Display}};
 impl nested for Foo {
@@ -303,13 +371,13 @@ impl nested for Foo {
    fn test_replace_add_to_nested_nested() {
        check_assist(
            replace_qualified_name_with_use,
-            "
+            r"
 use std::fmt::{Debug, nested::{Display}};
 impl std::fmt::nested::Debug<|> for Foo {
 }
 ",
-            "
+            r"
 use std::fmt::{Debug, nested::{Display, Debug}};
 impl Debug for Foo {
@@ -322,13 +390,13 @@ impl Debug for Foo {
    fn test_replace_split_common_target_longer() {
        check_assist(
            replace_qualified_name_with_use,
-            "
+            r"
 use std::fmt::Debug;
 impl std::fmt::nested::Display<|> for Foo {
 }
 ",
-            "
+            r"
 use std::fmt::{nested::Display, Debug};
 impl Display for Foo {
@@ -341,13 +409,13 @@ impl Display for Foo {
    fn test_replace_split_common_use_longer() {
        check_assist(
            replace_qualified_name_with_use,
-            "
+            r"
 use std::fmt::nested::Debug;
 impl std::fmt::Display<|> for Foo {
 }
 ",
-            "
+            r"
 use std::fmt::{Display, nested::Debug};
 impl Display for Foo {
@@ -360,7 +428,7 @@ impl Display for Foo {
    fn test_replace_use_nested_import() {
        check_assist(
            replace_qualified_name_with_use,
-            "
+            r"
 use crate::{
    ty::{Substs, Ty},
    AssocItem,
@@ -368,7 +436,7 @@ use crate::{
 fn foo() { crate::ty::lower<|>::trait_env() }
 ",
-            "
+            r"
 use crate::{
    ty::{Substs, Ty, lower},
    AssocItem,
@@ -383,13 +451,13 @@ fn foo() { lower::trait_env() }
    fn test_replace_alias() {
        check_assist(
            replace_qualified_name_with_use,
-            "
+            r"
 use std::fmt as foo;
 impl foo::Debug<|> for Foo {
 }
 ",
-            "
+            r"
 use std::fmt as foo;
 impl Debug for Foo {
@@ -402,7 +470,7 @@ impl Debug for Foo {
    fn test_replace_not_applicable_one_segment() {
        check_assist_not_applicable(
            replace_qualified_name_with_use,
-            "
+            r"
 impl foo<|> for Foo {
 }
 ",
@@ -413,7 +481,7 @@ impl foo<|> for Foo {
    fn test_replace_not_applicable_in_use() {
        check_assist_not_applicable(
            replace_qualified_name_with_use,
-            "
+            r"
 use std::fmt<|>;
 ",
        );
@@ -423,14 +491,14 @@ use std::fmt<|>;
    fn test_replace_add_use_no_anchor_in_mod_mod() {
        check_assist(
            replace_qualified_name_with_use,
-            "
+            r"
 mod foo {
    mod bar {
        std::fmt::Debug<|>
    }
 }
    ",
-            "
+            r"
 mod foo {
    mod bar {
        use std::fmt::Debug;
@@ -446,14 +514,14 @@ mod foo {
    fn inserts_imports_after_inner_attributes() {
        check_assist(
            replace_qualified_name_with_use,
-            "
+            r"
 #![allow(dead_code)]
 fn main() {
    std::fmt::Debug<|>
 }
    ",
-            "
+            r"
 #![allow(dead_code)]
 use std::fmt::Debug;
@@ -463,4 +531,116 @@ fn main() {
    ",
        );
    }
+    #[test]
+    fn replaces_all_affected_paths() {
+        check_assist(
+            replace_qualified_name_with_use,
+            r"
+fn main() {
+    std::fmt::Debug<|>;
+    let x: std::fmt::Debug = std::fmt::Debug;
+}
+    ",
+            r"
+use std::fmt::Debug;
+fn main() {
+    Debug;
+    let x: Debug = Debug;
+}
+    ",
+        );
+    }
+    #[test]
+    fn replaces_all_affected_paths_mod() {
+        check_assist(
+            replace_qualified_name_with_use,
+            r"
+mod m {
+    fn f() {
+        std::fmt::Debug<|>;
+        let x: std::fmt::Debug = std::fmt::Debug;
+    }
+    fn g() {
+        std::fmt::Debug;
+    }
+}
+fn f() {
+    std::fmt::Debug;
+}
+    ",
+            r"
+mod m {
+    use std::fmt::Debug;
+    fn f() {
+        Debug;
+        let x: Debug = Debug;
+    }
+    fn g() {
+        Debug;
+    }
+}
+fn f() {
+    std::fmt::Debug;
+}
+    ",
+        );
+    }
+    #[test]
+    fn does_not_replace_in_submodules() {
+        check_assist(
+            replace_qualified_name_with_use,
+            r"
+fn main() {
+    std::fmt::Debug<|>;
+}
+mod sub {
+    fn f() {
+        std::fmt::Debug;
+    }
+}
+    ",
+            r"
+use std::fmt::Debug;
+fn main() {
+    Debug;
+}
+mod sub {
+    fn f() {
+        std::fmt::Debug;
+    }
+}
+    ",
+        );
+    }
+    #[test]
+    fn does_not_replace_in_use() {
+        check_assist(
+            replace_qualified_name_with_use,
+            r"
+use std::fmt::Display;
+fn main() {
+    std::fmt<|>;
+}
+    ",
+            r"
+use std::fmt::{self, Display};
+fn main() {
+    fmt;
+}
+    ",
+        );
+    }
 }
diff --git a/crates/ra_assists/src/utils.rs b/crates/ra_assists/src/utils.rs
index 0038a9764..c1ff0de7b 100644
--- a/crates/ra_assists/src/utils.rs
+++ b/crates/ra_assists/src/utils.rs
@@ -13,7 +13,7 @@ use rustc_hash::FxHashSet;
 use crate::assist_config::SnippetCap;
-pub(crate) use insert_use::insert_use_statement;
+pub(crate) use insert_use::{find_insert_use_container, insert_use_statement};
 #[derive(Clone, Copy, Debug)]
 pub(crate) enum Cursor<'a> {
diff --git a/crates/ra_assists/src/utils/insert_use.rs b/crates/ra_assists/src/utils/insert_use.rs
index 0ee43482f..8c4f33e59 100644
--- a/crates/ra_assists/src/utils/insert_use.rs
+++ b/crates/ra_assists/src/utils/insert_use.rs
@@ -12,6 +12,20 @@ use ra_syntax::{
 use ra_text_edit::TextEditBuilder;
 use crate::assist_context::AssistContext;
+use either::Either;
+/// Determines the containing syntax node in which to insert a `use` statement affecting `position`.
+pub(crate) fn find_insert_use_container(
+    position: &SyntaxNode,
+    ctx: &AssistContext,
+) -> Option<Either<ast::ItemList, ast::SourceFile>> {
+    ctx.sema.ancestors_with_macros(position.clone()).find_map(|n| {
+        if let Some(module) = ast::Module::cast(n.clone()) {
+            return module.item_list().map(|it| Either::Left(it));
+        }
+        Some(Either::Right(ast::SourceFile::cast(n)?))
+    })
+}
 /// Creates and inserts a use statement for the given path to import.
 /// The use statement is inserted in the scope most appropriate to the
@@ -24,15 +38,11 @@ pub(crate) fn insert_use_statement(
    builder: &mut TextEditBuilder,
 ) {
    let target = path_to_import.to_string().split("::").map(SmolStr::new).collect::<Vec<_>>();
-    let container = ctx.sema.ancestors_with_macros(position.clone()).find_map(|n| {
+    let container = find_insert_use_container(position, ctx);
-        if let Some(module) = ast::Module::cast(n.clone()) {
-            return module.item_list().map(|it| it.syntax().clone());
-        }
-        ast::SourceFile::cast(n).map(|it| it.syntax().clone())
-    });
    if let Some(container) = container {
-        let action = best_action_for_target(container, position.clone(), &target);
+        let syntax = container.either(|l| l.syntax().clone(), |r| r.syntax().clone());
+        let action = best_action_for_target(syntax, position.clone(), &target);
        make_assist(&action, &target, builder);
    }
 }
diff --git a/crates/ra_db/src/input.rs b/crates/ra_db/src/input.rs
index bf26048f2..e6af99035 100644
--- a/crates/ra_db/src/input.rs
+++ b/crates/ra_db/src/input.rs
@@ -254,12 +254,12 @@ impl CrateGraph {
            return false;
        }
+        if target == from {
+            return true;
+        }
        for dep in &self[from].dependencies {
            let crate_id = dep.crate_id;
-            if crate_id == target {
-                return true;
-            }
            if self.dfs_find(target, crate_id, visited) {
                return true;
            }
@@ -369,7 +369,7 @@ mod tests {
    use super::{CfgOptions, CrateGraph, CrateName, Dependency, Edition::Edition2018, Env, FileId};
    #[test]
-    fn it_should_panic_because_of_cycle_dependencies() {
+    fn detect_cyclic_dependency_indirect() {
        let mut graph = CrateGraph::default();
        let crate1 = graph.add_crate_root(
            FileId(1u32),
@@ -404,6 +404,31 @@ mod tests {
    }
    #[test]
+    fn detect_cyclic_dependency_direct() {
+        let mut graph = CrateGraph::default();
+        let crate1 = graph.add_crate_root(
+            FileId(1u32),
+            Edition2018,
+            None,
+            CfgOptions::default(),
+            Env::default(),
+            Default::default(),
+            Default::default(),
+        );
+        let crate2 = graph.add_crate_root(
+            FileId(2u32),
+            Edition2018,
+            None,
+            CfgOptions::default(),
+            Env::default(),
+            Default::default(),
+            Default::default(),
+        );
+        assert!(graph.add_dep(crate1, CrateName::new("crate2").unwrap(), crate2).is_ok());
+        assert!(graph.add_dep(crate2, CrateName::new("crate2").unwrap(), crate2).is_err());
+    }
+    #[test]
    fn it_works() {
        let mut graph = CrateGraph::default();
        let crate1 = graph.add_crate_root(
diff --git a/crates/ra_hir/src/code_model.rs b/crates/ra_hir/src/code_model.rs
index 1a9f6cc76..ffd5278ec 100644
--- a/crates/ra_hir/src/code_model.rs
+++ b/crates/ra_hir/src/code_model.rs
@@ -26,8 +26,8 @@ use hir_ty::{
    autoderef,
    display::{HirDisplayError, HirFormatter},
    expr::ExprValidator,
-    method_resolution, ApplicationTy, Canonical, InEnvironment, Substs, TraitEnvironment, Ty,
+    method_resolution, ApplicationTy, Canonical, GenericPredicate, InEnvironment, Substs,
-    TyDefId, TypeCtor,
+    TraitEnvironment, Ty, TyDefId, TypeCtor,
 };
 use ra_db::{CrateId, CrateName, Edition, FileId};
 use ra_prof::profile;
@@ -186,6 +186,22 @@ impl ModuleDef {
        module.visibility_of(db, self)
    }
+    pub fn name(self, db: &dyn HirDatabase) -> Option<Name> {
+        match self {
+            ModuleDef::Adt(it) => Some(it.name(db)),
+            ModuleDef::Trait(it) => Some(it.name(db)),
+            ModuleDef::Function(it) => Some(it.name(db)),
+            ModuleDef::EnumVariant(it) => Some(it.name(db)),
+            ModuleDef::TypeAlias(it) => Some(it.name(db)),
+            ModuleDef::Module(it) => it.name(db),
+            ModuleDef::Const(it) => it.name(db),
+            ModuleDef::Static(it) => it.name(db),
+            ModuleDef::BuiltinType(it) => Some(it.as_name()),
+        }
+    }
 }
 pub use hir_def::{
@@ -1359,6 +1375,27 @@ impl Type {
        Some(adt.into())
    }
+    pub fn as_dyn_trait(&self) -> Option<Trait> {
+        self.ty.value.dyn_trait().map(Into::into)
+    }
+    pub fn as_impl_traits(&self, db: &dyn HirDatabase) -> Option<Vec<Trait>> {
+        self.ty.value.impl_trait_bounds(db).map(|it| {
+            it.into_iter()
+                .filter_map(|pred| match pred {
+                    hir_ty::GenericPredicate::Implemented(trait_ref) => {
+                        Some(Trait::from(trait_ref.trait_))
+                    }
+                    _ => None,
+                })
+                .collect()
+        })
+    }
+    pub fn as_associated_type_parent_trait(&self, db: &dyn HirDatabase) -> Option<Trait> {
+        self.ty.value.associated_type_parent_trait(db).map(Into::into)
+    }
    // FIXME: provide required accessors such that it becomes implementable from outside.
    pub fn is_equal_for_find_impls(&self, other: &Type) -> bool {
        match (&self.ty.value, &other.ty.value) {
@@ -1380,6 +1417,80 @@ impl Type {
            ty: InEnvironment { value: ty, environment: self.ty.environment.clone() },
        }
    }
+    pub fn walk(&self, db: &dyn HirDatabase, mut cb: impl FnMut(Type)) {
+        // TypeWalk::walk for a Ty at first visits parameters and only after that the Ty itself.
+        // We need a different order here.
+        fn walk_substs(
+            db: &dyn HirDatabase,
+            type_: &Type,
+            substs: &Substs,
+            cb: &mut impl FnMut(Type),
+        ) {
+            for ty in substs.iter() {
+                walk_type(db, &type_.derived(ty.clone()), cb);
+            }
+        }
+        fn walk_bounds(
+            db: &dyn HirDatabase,
+            type_: &Type,
+            bounds: &[GenericPredicate],
+            cb: &mut impl FnMut(Type),
+        ) {
+            for pred in bounds {
+                match pred {
+                    GenericPredicate::Implemented(trait_ref) => {
+                        cb(type_.clone());
+                        walk_substs(db, type_, &trait_ref.substs, cb);
+                    }
+                    _ => (),
+                }
+            }
+        }
+        fn walk_type(db: &dyn HirDatabase, type_: &Type, cb: &mut impl FnMut(Type)) {
+            let ty = type_.ty.value.strip_references();
+            match ty {
+                Ty::Apply(ApplicationTy { ctor, parameters }) => {
+                    match ctor {
+                        TypeCtor::Adt(_) => {
+                            cb(type_.derived(ty.clone()));
+                        }
+                        TypeCtor::AssociatedType(_) => {
+                            if let Some(_) = ty.associated_type_parent_trait(db) {
+                                cb(type_.derived(ty.clone()));
+                            }
+                        }
+                        _ => (),
+                    }
+                    // adt params, tuples, etc...
+                    walk_substs(db, type_, parameters, cb);
+                }
+                Ty::Opaque(opaque_ty) => {
+                    if let Some(bounds) = ty.impl_trait_bounds(db) {
+                        walk_bounds(db, &type_.derived(ty.clone()), &bounds, cb);
+                    }
+                    walk_substs(db, type_, &opaque_ty.parameters, cb);
+                }
+                Ty::Placeholder(_) => {
+                    if let Some(bounds) = ty.impl_trait_bounds(db) {
+                        walk_bounds(db, &type_.derived(ty.clone()), &bounds, cb);
+                    }
+                }
+                Ty::Dyn(bounds) => {
+                    walk_bounds(db, &type_.derived(ty.clone()), bounds.as_ref(), cb);
+                }
+                _ => (),
+            }
+        }
+        walk_type(db, self, &mut cb);
+    }
 }
 impl HirDisplay for Type {
diff --git a/crates/ra_hir/src/db.rs b/crates/ra_hir/src/db.rs
index b6b665de1..b25dac28e 100644
--- a/crates/ra_hir/src/db.rs
+++ b/crates/ra_hir/src/db.rs
@@ -16,7 +16,7 @@ pub use hir_expand::db::{
 pub use hir_ty::db::{
    AssociatedTyDataQuery, AssociatedTyValueQuery, CallableItemSignatureQuery, FieldTypesQuery,
    GenericDefaultsQuery, GenericPredicatesForParamQuery, GenericPredicatesQuery, HirDatabase,
-    HirDatabaseStorage, ImplDatumQuery, ImplSelfTyQuery, ImplTraitQuery, ImplsForTraitQuery,
+    HirDatabaseStorage, ImplDatumQuery, ImplSelfTyQuery, ImplTraitQuery, ImplsFromDepsQuery,
    ImplsInCrateQuery, InferQueryQuery, InternAssocTyValueQuery, InternChalkImplQuery,
    InternTypeCtorQuery, InternTypeParamIdQuery, ReturnTypeImplTraitsQuery, StructDatumQuery,
    TraitDatumQuery, TraitSolveQuery, TyQuery, ValueTyQuery,
diff --git a/crates/ra_hir/src/semantics.rs b/crates/ra_hir/src/semantics.rs
index a232a5856..6a49c424a 100644
--- a/crates/ra_hir/src/semantics.rs
+++ b/crates/ra_hir/src/semantics.rs
@@ -6,9 +6,9 @@ use std::{cell::RefCell, fmt, iter::successors};
 use hir_def::{
    resolver::{self, HasResolver, Resolver},
-    AsMacroCall, TraitId,
+    AsMacroCall, TraitId, VariantId,
 };
-use hir_expand::{hygiene::Hygiene, ExpansionInfo};
+use hir_expand::{diagnostics::AstDiagnostic, hygiene::Hygiene, ExpansionInfo};
 use hir_ty::associated_type_shorthand_candidates;
 use itertools::Itertools;
 use ra_db::{FileId, FileRange};
@@ -104,6 +104,13 @@ impl<'db, DB: HirDatabase> Semantics<'db, DB> {
        tree
    }
+    pub fn ast<T: AstDiagnostic + Diagnostic>(&self, d: &T) -> <T as AstDiagnostic>::AST {
+        let file_id = d.source().file_id;
+        let root = self.db.parse_or_expand(file_id).unwrap();
+        self.cache(root, file_id);
+        d.ast(self.db)
+    }
    pub fn expand(&self, macro_call: &ast::MacroCall) -> Option<SyntaxNode> {
        let macro_call = self.find_file(macro_call.syntax().clone()).with_value(macro_call);
        let sa = self.analyze2(macro_call.map(|it| it.syntax()), None);
@@ -247,6 +254,10 @@ impl<'db, DB: HirDatabase> Semantics<'db, DB> {
        self.analyze(path.syntax()).resolve_path(self.db, path)
    }
+    pub fn resolve_variant(&self, record_lit: ast::RecordLit) -> Option<VariantId> {
+        self.analyze(record_lit.syntax()).resolve_variant(self.db, record_lit)
+    }
    pub fn lower_path(&self, path: &ast::Path) -> Option<Path> {
        let src = self.find_file(path.syntax().clone());
        Path::from_src(path.clone(), &Hygiene::new(self.db.upcast(), src.file_id.into()))
diff --git a/crates/ra_hir/src/source_analyzer.rs b/crates/ra_hir/src/source_analyzer.rs
index 7c6bbea13..757d1e397 100644
--- a/crates/ra_hir/src/source_analyzer.rs
+++ b/crates/ra_hir/src/source_analyzer.rs
@@ -313,6 +313,16 @@ impl SourceAnalyzer {
        })?;
        Some(macro_call_id.as_file())
    }
+    pub(crate) fn resolve_variant(
+        &self,
+        db: &dyn HirDatabase,
+        record_lit: ast::RecordLit,
+    ) -> Option<VariantId> {
+        let infer = self.infer.as_ref()?;
+        let expr_id = self.expr_id(db, &record_lit.into())?;
+        infer.variant_resolution_for_expr(expr_id)
+    }
 }
 fn scope_for(
diff --git a/crates/ra_hir_def/src/body/scope.rs b/crates/ra_hir_def/src/body/scope.rs
index e48ff38f9..661f00407 100644
--- a/crates/ra_hir_def/src/body/scope.rs
+++ b/crates/ra_hir_def/src/body/scope.rs
@@ -87,15 +87,13 @@ impl ExprScopes {
    }
    fn add_bindings(&mut self, body: &Body, scope: ScopeId, pat: PatId) {
-        match &body[pat] {
+        let pattern = &body[pat];
-            Pat::Bind { name, .. } => {
+        if let Pat::Bind { name, .. } = pattern {
-                // bind can have a sub pattern, but it's actually not allowed
+            let entry = ScopeEntry { name: name.clone(), pat };
-                // to bind to things in there
+            self.scopes[scope].entries.push(entry);
-                let entry = ScopeEntry { name: name.clone(), pat };
-                self.scopes[scope].entries.push(entry)
-            }
-            p => p.walk_child_pats(|pat| self.add_bindings(body, scope, pat)),
        }
+        pattern.walk_child_pats(|pat| self.add_bindings(body, scope, pat));
    }
    fn add_params_bindings(&mut self, body: &Body, scope: ScopeId, params: &[PatId]) {
@@ -190,8 +188,8 @@ mod tests {
        }
    }
-    fn do_check(code: &str, expected: &[&str]) {
+    fn do_check(ra_fixture: &str, expected: &[&str]) {
-        let (off, code) = extract_offset(code);
+        let (off, code) = extract_offset(ra_fixture);
        let code = {
            let mut buf = String::new();
            let off: usize = off.into();
@@ -300,6 +298,22 @@ mod tests {
        );
    }
+    #[test]
+    fn test_bindings_after_at() {
+        do_check(
+            r"
+            fn foo() {
+                match Some(()) {
+                    opt @ Some(unit) => {
+                        <|>
+                    }
+                    _ => {}
+                }
+            }",
+            &["opt", "unit"],
+        );
+    }
    fn do_check_local_name(code: &str, expected_offset: u32) {
        let (off, code) = extract_offset(code);
diff --git a/crates/ra_hir_def/src/diagnostics.rs b/crates/ra_hir_def/src/diagnostics.rs
index 510c5e064..30db48f86 100644
--- a/crates/ra_hir_def/src/diagnostics.rs
+++ b/crates/ra_hir_def/src/diagnostics.rs
@@ -3,7 +3,6 @@
 use std::any::Any;
 use hir_expand::diagnostics::Diagnostic;
-use ra_db::RelativePathBuf;
 use ra_syntax::{ast, AstPtr, SyntaxNodePtr};
 use hir_expand::{HirFileId, InFile};
@@ -12,7 +11,7 @@ use hir_expand::{HirFileId, InFile};
 pub struct UnresolvedModule {
    pub file: HirFileId,
    pub decl: AstPtr<ast::Module>,
-    pub candidate: RelativePathBuf,
+    pub candidate: String,
 }
 impl Diagnostic for UnresolvedModule {
diff --git a/crates/ra_hir_def/src/lib.rs b/crates/ra_hir_def/src/lib.rs
index edc59e5a8..af2a717c9 100644
--- a/crates/ra_hir_def/src/lib.rs
+++ b/crates/ra_hir_def/src/lib.rs
@@ -159,7 +159,7 @@ pub struct TypeAliasId(salsa::InternId);
 type TypeAliasLoc = AssocItemLoc<ast::TypeAliasDef>;
 impl_intern!(TypeAliasId, TypeAliasLoc, intern_type_alias, lookup_intern_type_alias);
-#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
+#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Ord, PartialOrd)]
 pub struct ImplId(salsa::InternId);
 type ImplLoc = ItemLoc<ast::ImplDef>;
 impl_intern!(ImplId, ImplLoc, intern_impl, lookup_intern_impl);
diff --git a/crates/ra_hir_def/src/nameres.rs b/crates/ra_hir_def/src/nameres.rs
index f279c2ad4..b8560fdc9 100644
--- a/crates/ra_hir_def/src/nameres.rs
+++ b/crates/ra_hir_def/src/nameres.rs
@@ -119,13 +119,6 @@ impl Default for ModuleOrigin {
 }
 impl ModuleOrigin {
-    pub(crate) fn not_sure_file(file: Option<FileId>, declaration: AstId<ast::Module>) -> Self {
-        match file {
-            None => ModuleOrigin::Inline { definition: declaration },
-            Some(definition) => ModuleOrigin::File { declaration, definition },
-        }
-    }
    fn declaration(&self) -> Option<AstId<ast::Module>> {
        match self {
            ModuleOrigin::File { declaration: module, .. }
@@ -296,7 +289,6 @@ pub enum ModuleSource {
 mod diagnostics {
    use hir_expand::diagnostics::DiagnosticSink;
-    use ra_db::RelativePathBuf;
    use ra_syntax::{ast, AstPtr};
    use crate::{db::DefDatabase, diagnostics::UnresolvedModule, nameres::LocalModuleId, AstId};
@@ -306,7 +298,7 @@ mod diagnostics {
        UnresolvedModule {
            module: LocalModuleId,
            declaration: AstId<ast::Module>,
-            candidate: RelativePathBuf,
+            candidate: String,
        },
    }
diff --git a/crates/ra_hir_def/src/nameres/collector.rs b/crates/ra_hir_def/src/nameres/collector.rs
index 976e5e585..b8f6aac8f 100644
--- a/crates/ra_hir_def/src/nameres/collector.rs
+++ b/crates/ra_hir_def/src/nameres/collector.rs
@@ -36,8 +36,8 @@ pub(super) fn collect_defs(db: &dyn DefDatabase, mut def_map: CrateDefMap) -> Cr
    // populate external prelude
    for dep in &crate_graph[def_map.krate].dependencies {
-        let dep_def_map = db.crate_def_map(dep.crate_id);
        log::debug!("crate dep {:?} -> {:?}", dep.name, dep.crate_id);
+        let dep_def_map = db.crate_def_map(dep.crate_id);
        def_map.extern_prelude.insert(
            dep.as_name(),
            ModuleId { krate: dep.crate_id, local_id: dep_def_map.root }.into(),
@@ -825,7 +825,10 @@ impl ModCollector<'_, '_> {
        let modules = &mut self.def_collector.def_map.modules;
        let res = modules.alloc(ModuleData::default());
        modules[res].parent = Some(self.module_id);
-        modules[res].origin = ModuleOrigin::not_sure_file(definition, declaration);
+        modules[res].origin = match definition {
+            None => ModuleOrigin::Inline { definition: declaration },
+            Some(definition) => ModuleOrigin::File { declaration, definition },
+        };
        for (name, mac) in modules[self.module_id].scope.collect_legacy_macros() {
            modules[res].scope.define_legacy_macro(name, mac)
        }
diff --git a/crates/ra_hir_def/src/nameres/mod_resolution.rs b/crates/ra_hir_def/src/nameres/mod_resolution.rs
index cede4a6fc..19fe0615a 100644
--- a/crates/ra_hir_def/src/nameres/mod_resolution.rs
+++ b/crates/ra_hir_def/src/nameres/mod_resolution.rs
@@ -44,7 +44,7 @@ impl ModDir {
        file_id: HirFileId,
        name: &Name,
        attr_path: Option<&SmolStr>,
-    ) -> Result<(FileId, ModDir), RelativePathBuf> {
+    ) -> Result<(FileId, ModDir), String> {
        let file_id = file_id.original_file(db.upcast());
        let mut candidate_files = Vec::new();
@@ -52,11 +52,11 @@ impl ModDir {
            Some(attr_path) => {
                let base =
                    if self.root_non_dir_owner { self.path.parent().unwrap() } else { &self.path };
-                candidate_files.push(base.join(attr_path))
+                candidate_files.push(base.join(attr_path).to_string())
            }
            None => {
-                candidate_files.push(self.path.join(&format!("{}.rs", name)));
+                candidate_files.push(self.path.join(&format!("{}.rs", name)).to_string());
-                candidate_files.push(self.path.join(&format!("{}/mod.rs", name)));
+                candidate_files.push(self.path.join(&format!("{}/mod.rs", name)).to_string());
            }
        };
diff --git a/crates/ra_hir_ty/src/_match.rs b/crates/ra_hir_ty/src/_match.rs
index fff257193..5495ce284 100644
--- a/crates/ra_hir_ty/src/_match.rs
+++ b/crates/ra_hir_ty/src/_match.rs
@@ -312,20 +312,16 @@ impl PatStack {
        Self(v)
    }
-    fn is_empty(&self) -> bool {
-        self.0.is_empty()
-    }
-    fn head(&self) -> PatIdOrWild {
-        self.0[0]
-    }
    fn get_head(&self) -> Option<PatIdOrWild> {
        self.0.first().copied()
    }
+    fn tail(&self) -> &[PatIdOrWild] {
+        self.0.get(1..).unwrap_or(&[])
+    }
    fn to_tail(&self) -> PatStack {
-        Self::from_slice(&self.0[1..])
+        Self::from_slice(self.tail())
    }
    fn replace_head_with<I, T>(&self, pats: I) -> PatStack
@@ -347,7 +343,7 @@ impl PatStack {
    ///
    /// See the module docs and the associated documentation in rustc for details.
    fn specialize_wildcard(&self, cx: &MatchCheckCtx) -> Option<PatStack> {
-        if matches!(self.head().as_pat(cx), Pat::Wild) {
+        if matches!(self.get_head()?.as_pat(cx), Pat::Wild) {
            Some(self.to_tail())
        } else {
            None
@@ -362,7 +358,13 @@ impl PatStack {
        cx: &MatchCheckCtx,
        constructor: &Constructor,
    ) -> MatchCheckResult<Option<PatStack>> {
-        let result = match (self.head().as_pat(cx), constructor) {
+        let head = match self.get_head() {
+            Some(head) => head,
+            None => return Ok(None),
+        };
+        let head_pat = head.as_pat(cx);
+        let result = match (head_pat, constructor) {
            (Pat::Tuple { args: ref pat_ids, ellipsis }, Constructor::Tuple { arity: _ }) => {
                if ellipsis.is_some() {
                    // If there are ellipsis here, we should add the correct number of
@@ -389,7 +391,7 @@ impl PatStack {
            (Pat::Wild, constructor) => Some(self.expand_wildcard(cx, constructor)?),
            (Pat::Path(_), Constructor::Enum(constructor)) => {
                // unit enum variants become `Pat::Path`
-                let pat_id = self.head().as_id().expect("we know this isn't a wild");
+                let pat_id = head.as_id().expect("we know this isn't a wild");
                if !enum_variant_matches(cx, pat_id, *constructor) {
                    None
                } else {
@@ -400,7 +402,7 @@ impl PatStack {
                Pat::TupleStruct { args: ref pat_ids, ellipsis, .. },
                Constructor::Enum(enum_constructor),
            ) => {
-                let pat_id = self.head().as_id().expect("we know this isn't a wild");
+                let pat_id = head.as_id().expect("we know this isn't a wild");
                if !enum_variant_matches(cx, pat_id, *enum_constructor) {
                    None
                } else {
@@ -440,7 +442,7 @@ impl PatStack {
                }
            }
            (Pat::Record { args: ref arg_patterns, .. }, Constructor::Enum(e)) => {
-                let pat_id = self.head().as_id().expect("we know this isn't a wild");
+                let pat_id = head.as_id().expect("we know this isn't a wild");
                if !enum_variant_matches(cx, pat_id, *e) {
                    None
                } else {
@@ -486,7 +488,7 @@ impl PatStack {
    ) -> MatchCheckResult<PatStack> {
        assert_eq!(
            Pat::Wild,
-            self.head().as_pat(cx),
+            self.get_head().expect("expand_wildcard called on empty PatStack").as_pat(cx),
            "expand_wildcard must only be called on PatStack with wild at head",
        );
@@ -504,7 +506,6 @@ impl PatStack {
    }
 }
-#[derive(Debug)]
 /// A collection of PatStack.
 ///
 /// This type is modeled from the struct of the same name in `rustc`.
@@ -531,7 +532,7 @@ impl Matrix {
    }
    fn heads(&self) -> Vec<PatIdOrWild> {
-        self.0.iter().map(|p| p.head()).collect()
+        self.0.iter().flat_map(|p| p.get_head()).collect()
    }
    /// Computes `D(self)` for each contained PatStack.
@@ -618,13 +619,16 @@ pub(crate) fn is_useful(
        _ => (),
    }
-    if v.is_empty() {
+    let head = match v.get_head() {
-        let result = if matrix.is_empty() { Usefulness::Useful } else { Usefulness::NotUseful };
+        Some(head) => head,
+        None => {
+            let result = if matrix.is_empty() { Usefulness::Useful } else { Usefulness::NotUseful };
-        return Ok(result);
+            return Ok(result);
-    }
+        }
+    };
-    if let Pat::Or(pat_ids) = v.head().as_pat(cx) {
+    if let Pat::Or(pat_ids) = head.as_pat(cx) {
        let mut found_unimplemented = false;
        let any_useful = pat_ids.iter().any(|&pat_id| {
            let v = PatStack::from_pattern(pat_id);
@@ -648,7 +652,7 @@ pub(crate) fn is_useful(
        };
    }
-    if let Some(constructor) = pat_constructor(cx, v.head())? {
+    if let Some(constructor) = pat_constructor(cx, head)? {
        let matrix = matrix.specialize_constructor(&cx, &constructor)?;
        let v = v
            .specialize_constructor(&cx, &constructor)?
@@ -837,194 +841,193 @@ mod tests {
    pub(super) use crate::{diagnostics::MissingMatchArms, test_db::TestDB};
-    pub(super) fn check_diagnostic_message(content: &str) -> String {
+    pub(super) fn check_diagnostic_message(ra_fixture: &str) -> String {
-        TestDB::with_single_file(content).0.diagnostic::<MissingMatchArms>().0
+        TestDB::with_single_file(ra_fixture).0.diagnostic::<MissingMatchArms>().0
    }
-    pub(super) fn check_diagnostic(content: &str) {
+    pub(super) fn check_diagnostic(ra_fixture: &str) {
        let diagnostic_count =
-            TestDB::with_single_file(content).0.diagnostic::<MissingMatchArms>().1;
+            TestDB::with_single_file(ra_fixture).0.diagnostic::<MissingMatchArms>().1;
        assert_eq!(1, diagnostic_count, "no diagnostic reported");
    }
-    pub(super) fn check_no_diagnostic(content: &str) {
+    pub(super) fn check_no_diagnostic(ra_fixture: &str) {
-        let diagnostic_count =
+        let (s, diagnostic_count) =
-            TestDB::with_single_file(content).0.diagnostic::<MissingMatchArms>().1;
+            TestDB::with_single_file(ra_fixture).0.diagnostic::<MissingMatchArms>();
-        assert_eq!(0, diagnostic_count, "expected no diagnostic, found one");
+        assert_eq!(0, diagnostic_count, "expected no diagnostic, found one: {}", s);
    }
    #[test]
    fn empty_tuple_no_arms_diagnostic_message() {
-        let content = r"
-            fn test_fn() {
-                match () {
-                }
-            }
-        ";
        assert_snapshot!(
-            check_diagnostic_message(content),
+            check_diagnostic_message(r"
+                fn test_fn() {
+                    match () {
+                    }
+                }
+            "),
            @"\"()\": Missing match arm\n"
        );
    }
    #[test]
    fn empty_tuple_no_arms() {
-        let content = r"
+        check_diagnostic(
+            r"
            fn test_fn() {
                match () {
                }
            }
-        ";
+        ",
+        );
-        check_diagnostic(content);
    }
    #[test]
    fn empty_tuple_wild() {
-        let content = r"
+        check_no_diagnostic(
+            r"
            fn test_fn() {
                match () {
                    _ => {}
                }
            }
-        ";
+        ",
+        );
-        check_no_diagnostic(content);
    }
    #[test]
    fn empty_tuple_no_diagnostic() {
-        let content = r"
+        check_no_diagnostic(
+            r"
            fn test_fn() {
                match () {
                    () => {}
                }
            }
-        ";
+        ",
+        );
-        check_no_diagnostic(content);
    }
    #[test]
    fn tuple_of_empty_tuple_no_arms() {
-        let content = r"
+        check_diagnostic(
+            r"
            fn test_fn() {
                match (()) {
                }
            }
-        ";
+        ",
+        );
-        check_diagnostic(content);
    }
    #[test]
    fn tuple_of_empty_tuple_no_diagnostic() {
-        let content = r"
+        check_no_diagnostic(
+            r"
            fn test_fn() {
                match (()) {
                    (()) => {}
                }
            }
-        ";
+        ",
+        );
-        check_no_diagnostic(content);
    }
    #[test]
    fn tuple_of_two_empty_tuple_no_arms() {
-        let content = r"
+        check_diagnostic(
+            r"
            fn test_fn() {
                match ((), ()) {
                }
            }
-        ";
+        ",
+        );
-        check_diagnostic(content);
    }
    #[test]
    fn tuple_of_two_empty_tuple_no_diagnostic() {
-        let content = r"
+        check_no_diagnostic(
+            r"
            fn test_fn() {
                match ((), ()) {
                    ((), ()) => {}
                }
            }
-        ";
+        ",
+        );
-        check_no_diagnostic(content);
    }
    #[test]
    fn bool_no_arms() {
-        let content = r"
+        check_diagnostic(
+            r"
            fn test_fn() {
                match false {
                }
            }
-        ";
+        ",
+        );
-        check_diagnostic(content);
    }
    #[test]
    fn bool_missing_arm() {
-        let content = r"
+        check_diagnostic(
+            r"
            fn test_fn() {
                match false {
                    true => {}
                }
            }
-        ";
+        ",
+        );
-        check_diagnostic(content);
    }
    #[test]
    fn bool_no_diagnostic() {
-        let content = r"
+        check_no_diagnostic(
+            r"
            fn test_fn() {
                match false {
                    true => {}
                    false => {}
                }
            }
-        ";
+        ",
+        );
-        check_no_diagnostic(content);
    }
    #[test]
    fn tuple_of_bools_no_arms() {
-        let content = r"
+        check_diagnostic(
+            r"
            fn test_fn() {
                match (false, true) {
                }
            }
-        ";
+        ",
+        );
-        check_diagnostic(content);
    }
    #[test]
    fn tuple_of_bools_missing_arms() {
-        let content = r"
+        check_diagnostic(
+            r"
            fn test_fn() {
                match (false, true) {
                    (true, true) => {},
                }
            }
-        ";
+        ",
+        );
-        check_diagnostic(content);
    }
    #[test]
    fn tuple_of_bools_missing_arm() {
-        let content = r"
+        check_diagnostic(
+            r"
            fn test_fn() {
                match (false, true) {
                    (false, true) => {},
@@ -1032,14 +1035,14 @@ mod tests {
                    (true, false) => {},
                }
            }
-        ";
+        ",
+        );
-        check_diagnostic(content);
    }
    #[test]
    fn tuple_of_bools_with_wilds() {
-        let content = r"
+        check_no_diagnostic(
+            r"
            fn test_fn() {
                match (false, true) {
                    (false, _) => {},
@@ -1047,14 +1050,14 @@ mod tests {
                    (_, true) => {},
                }
            }
-        ";
+        ",
+        );
-        check_no_diagnostic(content);
    }
    #[test]
    fn tuple_of_bools_no_diagnostic() {
-        let content = r"
+        check_no_diagnostic(
+            r"
            fn test_fn() {
                match (false, true) {
                    (true, true) => {},
@@ -1063,27 +1066,27 @@ mod tests {
                    (false, false) => {},
                }
            }
-        ";
+        ",
+        );
-        check_no_diagnostic(content);
    }
    #[test]
    fn tuple_of_bools_binding_missing_arms() {
-        let content = r"
+        check_diagnostic(
+            r"
            fn test_fn() {
                match (false, true) {
                    (true, _x) => {},
                }
            }
-        ";
+        ",
+        );
-        check_diagnostic(content);
    }
    #[test]
    fn tuple_of_bools_binding_no_diagnostic() {
-        let content = r"
+        check_no_diagnostic(
+            r"
            fn test_fn() {
                match (false, true) {
                    (true, _x) => {},
@@ -1091,80 +1094,80 @@ mod tests {
                    (false, false) => {},
                }
            }
-        ";
+        ",
+        );
-        check_no_diagnostic(content);
    }
    #[test]
    fn tuple_of_bools_with_ellipsis_at_end_no_diagnostic() {
-        let content = r"
+        check_no_diagnostic(
+            r"
            fn test_fn() {
                match (false, true, false) {
                    (false, ..) => {},
                    (true, ..) => {},
                }
            }
-        ";
+        ",
+        );
-        check_no_diagnostic(content);
    }
    #[test]
    fn tuple_of_bools_with_ellipsis_at_beginning_no_diagnostic() {
-        let content = r"
+        check_no_diagnostic(
+            r"
            fn test_fn() {
                match (false, true, false) {
                    (.., false) => {},
                    (.., true) => {},
                }
            }
-        ";
+        ",
+        );
-        check_no_diagnostic(content);
    }
    #[test]
    fn tuple_of_bools_with_ellipsis_no_diagnostic() {
-        let content = r"
+        check_no_diagnostic(
+            r"
            fn test_fn() {
                match (false, true, false) {
                    (..) => {},
                }
            }
-        ";
+        ",
+        );
-        check_no_diagnostic(content);
    }
    #[test]
    fn tuple_of_tuple_and_bools_no_arms() {
-        let content = r"
+        check_diagnostic(
+            r"
            fn test_fn() {
                match (false, ((), false)) {
                }
            }
-        ";
+        ",
+        );
-        check_diagnostic(content);
    }
    #[test]
    fn tuple_of_tuple_and_bools_missing_arms() {
-        let content = r"
+        check_diagnostic(
+            r"
            fn test_fn() {
                match (false, ((), false)) {
                    (true, ((), true)) => {},
                }
            }
-        ";
+        ",
+        );
-        check_diagnostic(content);
    }
    #[test]
    fn tuple_of_tuple_and_bools_no_diagnostic() {
-        let content = r"
+        check_no_diagnostic(
+            r"
            fn test_fn() {
                match (false, ((), false)) {
                    (true, ((), true)) => {},
@@ -1173,27 +1176,27 @@ mod tests {
                    (false, ((), false)) => {},
                }
            }
-        ";
+        ",
+        );
-        check_no_diagnostic(content);
    }
    #[test]
    fn tuple_of_tuple_and_bools_wildcard_missing_arms() {
-        let content = r"
+        check_diagnostic(
+            r"
            fn test_fn() {
                match (false, ((), false)) {
                    (true, _) => {},
                }
            }
-        ";
+        ",
+        );
-        check_diagnostic(content);
    }
    #[test]
    fn tuple_of_tuple_and_bools_wildcard_no_diagnostic() {
-        let content = r"
+        check_no_diagnostic(
+            r"
            fn test_fn() {
                match (false, ((), false)) {
                    (true, ((), true)) => {},
@@ -1201,14 +1204,14 @@ mod tests {
                    (false, _) => {},
                }
            }
-        ";
+        ",
+        );
-        check_no_diagnostic(content);
    }
    #[test]
    fn enum_no_arms() {
-        let content = r"
+        check_diagnostic(
+            r"
            enum Either {
                A,
                B,
@@ -1217,14 +1220,14 @@ mod tests {
                match Either::A {
                }
            }
-        ";
+        ",
+        );
-        check_diagnostic(content);
    }
    #[test]
    fn enum_missing_arms() {
-        let content = r"
+        check_diagnostic(
+            r"
            enum Either {
                A,
                B,
@@ -1234,14 +1237,14 @@ mod tests {
                    Either::A => {},
                }
            }
-        ";
+        ",
+        );
-        check_diagnostic(content);
    }
    #[test]
    fn enum_no_diagnostic() {
-        let content = r"
+        check_no_diagnostic(
+            r"
            enum Either {
                A,
                B,
@@ -1252,14 +1255,14 @@ mod tests {
                    Either::B => {},
                }
            }
-        ";
+        ",
+        );
-        check_no_diagnostic(content);
    }
    #[test]
    fn enum_ref_missing_arms() {
-        let content = r"
+        check_diagnostic(
+            r"
            enum Either {
                A,
                B,
@@ -1269,14 +1272,14 @@ mod tests {
                    Either::A => {},
                }
            }
-        ";
+        ",
+        );
-        check_diagnostic(content);
    }
    #[test]
    fn enum_ref_no_diagnostic() {
-        let content = r"
+        check_no_diagnostic(
+            r"
            enum Either {
                A,
                B,
@@ -1287,14 +1290,14 @@ mod tests {
                    Either::B => {},
                }
            }
-        ";
+        ",
+        );
-        check_no_diagnostic(content);
    }
    #[test]
    fn enum_containing_bool_no_arms() {
-        let content = r"
+        check_diagnostic(
+            r"
            enum Either {
                A(bool),
                B,
@@ -1303,14 +1306,14 @@ mod tests {
                match Either::B {
                }
            }
-        ";
+        ",
+        );
-        check_diagnostic(content);
    }
    #[test]
    fn enum_containing_bool_missing_arms() {
-        let content = r"
+        check_diagnostic(
+            r"
            enum Either {
                A(bool),
                B,
@@ -1321,14 +1324,14 @@ mod tests {
                    Either::B => (),
                }
            }
-        ";
+        ",
+        );
-        check_diagnostic(content);
    }
    #[test]
    fn enum_containing_bool_no_diagnostic() {
-        let content = r"
+        check_no_diagnostic(
+            r"
            enum Either {
                A(bool),
                B,
@@ -1340,14 +1343,14 @@ mod tests {
                    Either::B => (),
                }
            }
-        ";
+        ",
+        );
-        check_no_diagnostic(content);
    }
    #[test]
    fn enum_containing_bool_with_wild_no_diagnostic() {
-        let content = r"
+        check_no_diagnostic(
+            r"
            enum Either {
                A(bool),
                B,
@@ -1358,14 +1361,14 @@ mod tests {
                    _ => (),
                }
            }
-        ";
+        ",
+        );
-        check_no_diagnostic(content);
    }
    #[test]
    fn enum_containing_bool_with_wild_2_no_diagnostic() {
-        let content = r"
+        check_no_diagnostic(
+            r"
            enum Either {
                A(bool),
                B,
@@ -1376,14 +1379,14 @@ mod tests {
                    Either::B => (),
                }
            }
-        ";
+        ",
+        );
-        check_no_diagnostic(content);
    }
    #[test]
    fn enum_different_sizes_missing_arms() {
-        let content = r"
+        check_diagnostic(
+            r"
            enum Either {
                A(bool),
                B(bool, bool),
@@ -1394,14 +1397,14 @@ mod tests {
                    Either::B(false, _) => (),
                }
            }
-        ";
+        ",
+        );
-        check_diagnostic(content);
    }
    #[test]
    fn enum_different_sizes_no_diagnostic() {
-        let content = r"
+        check_no_diagnostic(
+            r"
            enum Either {
                A(bool),
                B(bool, bool),
@@ -1413,14 +1416,14 @@ mod tests {
                    Either::B(false, _) => (),
                }
            }
-        ";
+        ",
+        );
-        check_no_diagnostic(content);
    }
    #[test]
    fn or_no_diagnostic() {
-        let content = r"
+        check_no_diagnostic(
+            r"
            enum Either {
                A(bool),
                B(bool, bool),
@@ -1432,14 +1435,14 @@ mod tests {
                    Either::B(false, _) => (),
                }
            }
-        ";
+        ",
+        );
-        check_no_diagnostic(content);
    }
    #[test]
    fn tuple_of_enum_no_diagnostic() {
-        let content = r"
+        check_no_diagnostic(
+            r"
            enum Either {
                A(bool),
                B(bool, bool),
@@ -1456,14 +1459,16 @@ mod tests {
                    (Either::B(_, _), Either2::D) => (),
                }
            }
-        ";
+        ",
+        );
-        check_no_diagnostic(content);
    }
    #[test]
    fn mismatched_types() {
-        let content = r"
+        // Match statements with arms that don't match the
+        // expression pattern do not fire this diagnostic.
+        check_no_diagnostic(
+            r"
            enum Either {
                A,
                B,
@@ -1478,47 +1483,47 @@ mod tests {
                    Either2::D => (),
                }
            }
-        ";
+        ",
+        );
-        // Match statements with arms that don't match the
-        // expression pattern do not fire this diagnostic.
-        check_no_diagnostic(content);
    }
    #[test]
    fn mismatched_types_with_different_arity() {
-        let content = r"
+        // Match statements with arms that don't match the
+        // expression pattern do not fire this diagnostic.
+        check_no_diagnostic(
+            r"
            fn test_fn() {
                match (true, false) {
                    (true, false, true) => (),
                    (true) => (),
                }
            }
-        ";
+        ",
+        );
-        // Match statements with arms that don't match the
-        // expression pattern do not fire this diagnostic.
-        check_no_diagnostic(content);
    }
    #[test]
    fn malformed_match_arm_tuple_missing_pattern() {
-        let content = r"
+        // Match statements with arms that don't match the
+        // expression pattern do not fire this diagnostic.
+        check_no_diagnostic(
+            r"
            fn test_fn() {
                match (0) {
                    () => (),
                }
            }
-        ";
+        ",
+        );
-        // Match statements with arms that don't match the
-        // expression pattern do not fire this diagnostic.
-        check_no_diagnostic(content);
    }
    #[test]
    fn malformed_match_arm_tuple_enum_missing_pattern() {
-        let content = r"
+        // We are testing to be sure we don't panic here when the match
+        // arm `Either::B` is missing its pattern.
+        check_no_diagnostic(
+            r"
            enum Either {
                A,
                B(u32),
@@ -1529,32 +1534,30 @@ mod tests {
                    Either::B() => (),
                }
            }
-        ";
+        ",
+        );
-        // We are testing to be sure we don't panic here when the match
-        // arm `Either::B` is missing its pattern.
-        check_no_diagnostic(content);
    }
    #[test]
    fn enum_not_in_scope() {
-        let content = r"
+        // The enum is not in scope so we don't perform exhaustiveness
+        // checking, but we want to be sure we don't panic here (and
+        // we don't create a diagnostic).
+        check_no_diagnostic(
+            r"
            fn test_fn() {
                match Foo::Bar {
                    Foo::Baz => (),
                }
            }
-        ";
+        ",
+        );
-        // The enum is not in scope so we don't perform exhaustiveness
-        // checking, but we want to be sure we don't panic here (and
-        // we don't create a diagnostic).
-        check_no_diagnostic(content);
    }
    #[test]
    fn expr_diverges() {
-        let content = r"
+        check_no_diagnostic(
+            r"
            enum Either {
                A,
                B,
@@ -1565,14 +1568,14 @@ mod tests {
                    Either::B => (),
                }
            }
-        ";
+        ",
+        );
-        check_no_diagnostic(content);
    }
    #[test]
    fn expr_loop_with_break() {
-        let content = r"
+        check_no_diagnostic(
+            r"
            enum Either {
                A,
                B,
@@ -1583,14 +1586,14 @@ mod tests {
                    Either::B => (),
                }
            }
-        ";
+        ",
+        );
-        check_no_diagnostic(content);
    }
    #[test]
    fn expr_partially_diverges() {
-        let content = r"
+        check_no_diagnostic(
+            r"
            enum Either<T> {
                A(T),
                B,
@@ -1604,14 +1607,14 @@ mod tests {
                    Either::B => 0,
                }
            }
-        ";
+        ",
+        );
-        check_no_diagnostic(content);
    }
    #[test]
    fn enum_record_no_arms() {
-        let content = r"
+        check_diagnostic(
+            r"
            enum Either {
                A { foo: bool },
                B,
@@ -1621,14 +1624,14 @@ mod tests {
                match a {
                }
            }
-        ";
+        ",
+        );
-        check_diagnostic(content);
    }
    #[test]
    fn enum_record_missing_arms() {
-        let content = r"
+        check_diagnostic(
+            r"
            enum Either {
                A { foo: bool },
                B,
@@ -1639,14 +1642,14 @@ mod tests {
                    Either::A { foo: true } => (),
                }
            }
-        ";
+        ",
+        );
-        check_diagnostic(content);
    }
    #[test]
    fn enum_record_no_diagnostic() {
-        let content = r"
+        check_no_diagnostic(
+            r"
            enum Either {
                A { foo: bool },
                B,
@@ -1659,14 +1662,17 @@ mod tests {
                    Either::B => (),
                }
            }
-        ";
+        ",
+        );
-        check_no_diagnostic(content);
    }
    #[test]
    fn enum_record_missing_field_no_diagnostic() {
-        let content = r"
+        // When `Either::A` is missing a struct member, we don't want
+        // to fire the missing match arm diagnostic. This should fire
+        // some other diagnostic.
+        check_no_diagnostic(
+            r"
            enum Either {
                A { foo: bool },
                B,
@@ -1678,17 +1684,16 @@ mod tests {
                    Either::B => (),
                }
            }
-        ";
+        ",
+        );
-        // When `Either::A` is missing a struct member, we don't want
-        // to fire the missing match arm diagnostic. This should fire
-        // some other diagnostic.
-        check_no_diagnostic(content);
    }
    #[test]
    fn enum_record_missing_field_missing_match_arm() {
-        let content = r"
+        // Even though `Either::A` is missing fields, we still want to fire
+        // the missing arm diagnostic here, since we know `Either::B` is missing.
+        check_diagnostic(
+            r"
            enum Either {
                A { foo: bool },
                B,
@@ -1699,16 +1704,14 @@ mod tests {
                    Either::A { } => (),
                }
            }
-        ";
+        ",
+        );
-        // Even though `Either::A` is missing fields, we still want to fire
-        // the missing arm diagnostic here, since we know `Either::B` is missing.
-        check_diagnostic(content);
    }
    #[test]
    fn enum_record_no_diagnostic_wild() {
-        let content = r"
+        check_no_diagnostic(
+            r"
            enum Either {
                A { foo: bool },
                B,
@@ -1720,14 +1723,14 @@ mod tests {
                    Either::B => (),
                }
            }
-        ";
+        ",
+        );
-        check_no_diagnostic(content);
    }
    #[test]
    fn enum_record_fields_out_of_order_missing_arm() {
-        let content = r"
+        check_diagnostic(
+            r"
            enum Either {
                A { foo: bool, bar: () },
                B,
@@ -1739,14 +1742,14 @@ mod tests {
                    Either::A { foo: true, bar: () } => (),
                }
            }
-        ";
+        ",
+        );
-        check_diagnostic(content);
    }
    #[test]
    fn enum_record_fields_out_of_order_no_diagnostic() {
-        let content = r"
+        check_no_diagnostic(
+            r"
            enum Either {
                A { foo: bool, bar: () },
                B,
@@ -1759,89 +1762,89 @@ mod tests {
                    Either::B => (),
                }
            }
-        ";
+        ",
+        );
-        check_no_diagnostic(content);
    }
    #[test]
    fn enum_record_ellipsis_missing_arm() {
-        let content = r"
+        check_diagnostic(
-             enum Either {
+            r"
-                 A { foo: bool, bar: bool },
+            enum Either {
-                 B,
+                A { foo: bool, bar: bool },
-             }
+                B,
-             fn test_fn() {
+            }
-                 match Either::B {
+            fn test_fn() {
-                     Either::A { foo: true, .. } => (),
+                match Either::B {
-                     Either::B => (),
+                    Either::A { foo: true, .. } => (),
-                 }
+                    Either::B => (),
-             }
+                }
-         ";
+            }
+        ",
-        check_diagnostic(content);
+        );
    }
    #[test]
    fn enum_record_ellipsis_no_diagnostic() {
-        let content = r"
+        check_no_diagnostic(
-             enum Either {
+            r"
-                 A { foo: bool, bar: bool },
+            enum Either {
-                 B,
+                A { foo: bool, bar: bool },
-             }
+                B,
-             fn test_fn() {
+            }
-                 let a = Either::A { foo: true };
+            fn test_fn() {
-                 match a {
+                let a = Either::A { foo: true };
-                     Either::A { foo: true, .. } => (),
+                match a {
-                     Either::A { foo: false, .. } => (),
+                    Either::A { foo: true, .. } => (),
-                     Either::B => (),
+                    Either::A { foo: false, .. } => (),
-                 }
+                    Either::B => (),
-             }
+                }
-         ";
+            }
+        ",
-        check_no_diagnostic(content);
+        );
    }
    #[test]
    fn enum_record_ellipsis_all_fields_missing_arm() {
-        let content = r"
+        check_diagnostic(
-             enum Either {
+            r"
-                 A { foo: bool, bar: bool },
+            enum Either {
-                 B,
+                A { foo: bool, bar: bool },
-             }
+                B,
-             fn test_fn() {
+            }
-                 let a = Either::B;
+            fn test_fn() {
-                 match a {
+                let a = Either::B;
-                     Either::A { .. } => (),
+                match a {
-                 }
+                    Either::A { .. } => (),
-             }
+                }
-         ";
+            }
+        ",
-        check_diagnostic(content);
+        );
    }
    #[test]
    fn enum_record_ellipsis_all_fields_no_diagnostic() {
-        let content = r"
+        check_no_diagnostic(
-             enum Either {
+            r"
-                 A { foo: bool, bar: bool },
+            enum Either {
-                 B,
+                A { foo: bool, bar: bool },
-             }
+                B,
-             fn test_fn() {
+            }
-                 let a = Either::B;
+            fn test_fn() {
-                 match a {
+                let a = Either::B;
-                     Either::A { .. } => (),
+                match a {
-                     Either::B => (),
+                    Either::A { .. } => (),
-                 }
+                    Either::B => (),
-             }
+                }
-         ";
+            }
+        ",
-        check_no_diagnostic(content);
+        );
    }
    #[test]
    fn enum_tuple_partial_ellipsis_no_diagnostic() {
-        let content = r"
+        check_no_diagnostic(
+            r"
            enum Either {
                A(bool, bool, bool, bool),
                B,
@@ -1855,14 +1858,14 @@ mod tests {
                    Either::B => {},
                }
            }
-        ";
+        ",
+        );
-        check_no_diagnostic(content);
    }
    #[test]
    fn enum_tuple_partial_ellipsis_2_no_diagnostic() {
-        let content = r"
+        check_no_diagnostic(
+            r"
            enum Either {
                A(bool, bool, bool, bool),
                B,
@@ -1876,14 +1879,14 @@ mod tests {
                    Either::B => {},
                }
            }
-        ";
+        ",
+        );
-        check_no_diagnostic(content);
    }
    #[test]
    fn enum_tuple_partial_ellipsis_missing_arm() {
-        let content = r"
+        check_diagnostic(
+            r"
            enum Either {
                A(bool, bool, bool, bool),
                B,
@@ -1896,14 +1899,14 @@ mod tests {
                    Either::B => {},
                }
            }
-        ";
+        ",
+        );
-        check_diagnostic(content);
    }
    #[test]
    fn enum_tuple_partial_ellipsis_2_missing_arm() {
-        let content = r"
+        check_diagnostic(
+            r"
            enum Either {
                A(bool, bool, bool, bool),
                B,
@@ -1916,14 +1919,14 @@ mod tests {
                    Either::B => {},
                }
            }
-        ";
+        ",
+        );
-        check_diagnostic(content);
    }
    #[test]
    fn enum_tuple_ellipsis_no_diagnostic() {
-        let content = r"
+        check_no_diagnostic(
+            r"
            enum Either {
                A(bool, bool, bool, bool),
                B,
@@ -1934,51 +1937,51 @@ mod tests {
                    Either::B => {},
                }
            }
-        ";
+        ",
+        );
-        check_no_diagnostic(content);
    }
    #[test]
    fn enum_never() {
-        let content = r"
+        check_no_diagnostic(
+            r"
            enum Never {}
            fn test_fn(never: Never) {
                match never {}
            }
-        ";
+        ",
+        );
-        check_no_diagnostic(content);
    }
    #[test]
    fn type_never() {
-        let content = r"
+        check_no_diagnostic(
+            r"
            fn test_fn(never: !) {
                match never {}
            }
-        ";
+        ",
+        );
-        check_no_diagnostic(content);
    }
    #[test]
    fn enum_never_ref() {
-        let content = r"
+        check_no_diagnostic(
+            r"
            enum Never {}
            fn test_fn(never: &Never) {
                match never {}
            }
-        ";
+        ",
+        );
-        check_no_diagnostic(content);
    }
    #[test]
    fn expr_diverges_missing_arm() {
-        let content = r"
+        check_no_diagnostic(
+            r"
            enum Either {
                A,
                B,
@@ -1988,9 +1991,49 @@ mod tests {
                    Either::A => (),
                }
            }
-        ";
+        ",
+        );
+    }
-        check_no_diagnostic(content);
+    #[test]
+    fn or_pattern_panic() {
+        check_no_diagnostic(
+            r"
+            pub enum Category {
+                Infinity,
+                Zero,
+            }
+            fn panic(a: Category, b: Category) {
+                match (a, b) {
+                    (Category::Zero | Category::Infinity, _) => {}
+                    (_, Category::Zero | Category::Infinity) => {}
+                }
+            }
+        ",
+        );
+    }
+    #[test]
+    fn or_pattern_panic_2() {
+        // FIXME: This is a false positive, but the code used to cause a panic in the match checker,
+        // so this acts as a regression test for that.
+        check_diagnostic(
+            r"
+            pub enum Category {
+                Infinity,
+                Zero,
+            }
+            fn panic(a: Category, b: Category) {
+                match (a, b) {
+                    (Category::Infinity, Category::Infinity) | (Category::Zero, Category::Zero) => {}
+                    (Category::Infinity | Category::Zero, _) => {}
+                }
+            }
+        ",
+        );
    }
 }
@@ -2010,23 +2053,26 @@ mod false_negatives {
    #[test]
    fn integers() {
-        let content = r"
+        // This is a false negative.
+        // We don't currently check integer exhaustiveness.
+        check_no_diagnostic(
+            r"
            fn test_fn() {
                match 5 {
                    10 => (),
                    11..20 => (),
                }
            }
-        ";
+        ",
+        );
-        // This is a false negative.
-        // We don't currently check integer exhaustiveness.
-        check_no_diagnostic(content);
    }
    #[test]
    fn internal_or() {
-        let content = r"
+        // This is a false negative.
+        // We do not currently handle patterns with internal `or`s.
+        check_no_diagnostic(
+            r"
            fn test_fn() {
                enum Either {
                    A(bool),
@@ -2036,16 +2082,18 @@ mod false_negatives {
                    Either::A(true | false) => (),
                }
            }
-        ";
+        ",
+        );
-        // This is a false negative.
-        // We do not currently handle patterns with internal `or`s.
-        check_no_diagnostic(content);
    }
    #[test]
    fn expr_loop_missing_arm() {
-        let content = r"
+        // This is a false negative.
+        // We currently infer the type of `loop { break Foo::A }` to `!`, which
+        // causes us to skip the diagnostic since `Either::A` doesn't type check
+        // with `!`.
+        check_diagnostic(
+            r"
            enum Either {
                A,
                B,
@@ -2055,48 +2103,46 @@ mod false_negatives {
                    Either::A => (),
                }
            }
-        ";
+        ",
+        );
-        // This is a false negative.
-        // We currently infer the type of `loop { break Foo::A }` to `!`, which
-        // causes us to skip the diagnostic since `Either::A` doesn't type check
-        // with `!`.
-        check_diagnostic(content);
    }
    #[test]
    fn tuple_of_bools_with_ellipsis_at_end_missing_arm() {
-        let content = r"
+        // This is a false negative.
+        // We don't currently handle tuple patterns with ellipsis.
+        check_no_diagnostic(
+            r"
            fn test_fn() {
                match (false, true, false) {
                    (false, ..) => {},
                }
            }
-        ";
+        ",
+        );
-        // This is a false negative.
-        // We don't currently handle tuple patterns with ellipsis.
-        check_no_diagnostic(content);
    }
    #[test]
    fn tuple_of_bools_with_ellipsis_at_beginning_missing_arm() {
-        let content = r"
+        // This is a false negative.
+        // We don't currently handle tuple patterns with ellipsis.
+        check_no_diagnostic(
+            r"
            fn test_fn() {
                match (false, true, false) {
                    (.., false) => {},
                }
            }
-        ";
+        ",
+        );
-        // This is a false negative.
-        // We don't currently handle tuple patterns with ellipsis.
-        check_no_diagnostic(content);
    }
    #[test]
    fn struct_missing_arm() {
-        let content = r"
+        // This is a false negative.
+        // We don't currently handle structs.
+        check_no_diagnostic(
+            r"
            struct Foo {
                a: bool,
            }
@@ -2105,10 +2151,7 @@ mod false_negatives {
                    Foo { a: true } => {},
                }
            }
-        ";
+        ",
+        );
-        // This is a false negative.
-        // We don't currently handle structs.
-        check_no_diagnostic(content);
    }
 }
diff --git a/crates/ra_hir_ty/src/db.rs b/crates/ra_hir_ty/src/db.rs
index bf71d38d6..7889b8d2c 100644
--- a/crates/ra_hir_ty/src/db.rs
+++ b/crates/ra_hir_ty/src/db.rs
@@ -3,15 +3,15 @@
 use std::sync::Arc;
 use hir_def::{
-    db::DefDatabase, DefWithBodyId, FunctionId, GenericDefId, ImplId, LocalFieldId, TraitId,
+    db::DefDatabase, DefWithBodyId, FunctionId, GenericDefId, ImplId, LocalFieldId, TypeParamId,
-    TypeParamId, VariantId,
+    VariantId,
 };
 use ra_arena::map::ArenaMap;
 use ra_db::{impl_intern_key, salsa, CrateId, Upcast};
 use ra_prof::profile;
 use crate::{
-    method_resolution::{CrateImplDefs, TyFingerprint},
+    method_resolution::CrateImplDefs,
    traits::{chalk, AssocTyValue, Impl},
    Binders, CallableDef, GenericPredicate, InferenceResult, OpaqueTyId, PolyFnSig,
    ReturnTypeImplTraits, Substs, TraitRef, Ty, TyDefId, TypeCtor, ValueTyDefId,
@@ -70,13 +70,8 @@ pub trait HirDatabase: DefDatabase + Upcast<dyn DefDatabase> {
    #[salsa::invoke(crate::method_resolution::CrateImplDefs::impls_in_crate_query)]
    fn impls_in_crate(&self, krate: CrateId) -> Arc<CrateImplDefs>;
-    #[salsa::invoke(crate::traits::impls_for_trait_query)]
+    #[salsa::invoke(crate::method_resolution::CrateImplDefs::impls_from_deps_query)]
-    fn impls_for_trait(
+    fn impls_from_deps(&self, krate: CrateId) -> Arc<CrateImplDefs>;
-        &self,
-        krate: CrateId,
-        trait_: TraitId,
-        self_ty_fp: Option<TyFingerprint>,
-    ) -> Arc<[ImplId]>;
    // Interned IDs for Chalk integration
    #[salsa::interned]
diff --git a/crates/ra_hir_ty/src/diagnostics.rs b/crates/ra_hir_ty/src/diagnostics.rs
index 2c7298714..ebd9cb08f 100644
--- a/crates/ra_hir_ty/src/diagnostics.rs
+++ b/crates/ra_hir_ty/src/diagnostics.rs
@@ -6,7 +6,7 @@ use hir_expand::{db::AstDatabase, name::Name, HirFileId, InFile};
 use ra_syntax::{ast, AstNode, AstPtr, SyntaxNodePtr};
 use stdx::format_to;
-pub use hir_def::{diagnostics::UnresolvedModule, expr::MatchArm};
+pub use hir_def::{diagnostics::UnresolvedModule, expr::MatchArm, path::Path};
 pub use hir_expand::diagnostics::{AstDiagnostic, Diagnostic, DiagnosticSink};
 #[derive(Debug)]
@@ -29,6 +29,16 @@ impl Diagnostic for NoSuchField {
    }
 }
+impl AstDiagnostic for NoSuchField {
+    type AST = ast::RecordField;
+    fn ast(&self, db: &impl AstDatabase) -> Self::AST {
+        let root = db.parse_or_expand(self.source().file_id).unwrap();
+        let node = self.source().value.to_node(&root);
+        ast::RecordField::cast(node).unwrap()
+    }
+}
 #[derive(Debug)]
 pub struct MissingFields {
    pub file: HirFileId,
diff --git a/crates/ra_hir_ty/src/infer/expr.rs b/crates/ra_hir_ty/src/infer/expr.rs
index 9fd310f69..a9565a58d 100644
--- a/crates/ra_hir_ty/src/infer/expr.rs
+++ b/crates/ra_hir_ty/src/infer/expr.rs
@@ -10,12 +10,12 @@ use hir_def::{
    resolver::resolver_for_expr,
    AdtId, AssocContainerId, FieldId, Lookup,
 };
-use hir_expand::name::Name;
+use hir_expand::name::{name, Name};
 use ra_syntax::ast::RangeOp;
 use crate::{
    autoderef, method_resolution, op,
-    traits::InEnvironment,
+    traits::{FnTrait, InEnvironment},
    utils::{generics, variant_data, Generics},
    ApplicationTy, Binders, CallableDef, InferTy, IntTy, Mutability, Obligation, Rawness, Substs,
    TraitRef, Ty, TypeCtor,
@@ -63,6 +63,58 @@ impl<'a> InferenceContext<'a> {
        self.resolve_ty_as_possible(ty)
    }
+    fn callable_sig_from_fn_trait(&mut self, ty: &Ty, num_args: usize) -> Option<(Vec<Ty>, Ty)> {
+        let krate = self.resolver.krate()?;
+        let fn_once_trait = FnTrait::FnOnce.get_id(self.db, krate)?;
+        let output_assoc_type =
+            self.db.trait_data(fn_once_trait).associated_type_by_name(&name![Output])?;
+        let generic_params = generics(self.db.upcast(), fn_once_trait.into());
+        if generic_params.len() != 2 {
+            return None;
+        }
+        let mut param_builder = Substs::builder(num_args);
+        let mut arg_tys = vec![];
+        for _ in 0..num_args {
+            let arg = self.table.new_type_var();
+            param_builder = param_builder.push(arg.clone());
+            arg_tys.push(arg);
+        }
+        let parameters = param_builder.build();
+        let arg_ty = Ty::Apply(ApplicationTy {
+            ctor: TypeCtor::Tuple { cardinality: num_args as u16 },
+            parameters,
+        });
+        let substs = Substs::build_for_generics(&generic_params)
+            .push(ty.clone())
+            .push(arg_ty.clone())
+            .build();
+        let trait_env = Arc::clone(&self.trait_env);
+        let implements_fn_trait =
+            Obligation::Trait(TraitRef { trait_: fn_once_trait, substs: substs.clone() });
+        let goal = self.canonicalizer().canonicalize_obligation(InEnvironment {
+            value: implements_fn_trait.clone(),
+            environment: trait_env,
+        });
+        if self.db.trait_solve(krate, goal.value).is_some() {
+            self.obligations.push(implements_fn_trait);
+            let output_proj_ty =
+                crate::ProjectionTy { associated_ty: output_assoc_type, parameters: substs };
+            let return_ty = self.normalize_projection_ty(output_proj_ty);
+            Some((arg_tys, return_ty))
+        } else {
+            None
+        }
+    }
+    pub fn callable_sig(&mut self, ty: &Ty, num_args: usize) -> Option<(Vec<Ty>, Ty)> {
+        match ty.callable_sig(self.db) {
+            Some(sig) => Some((sig.params().to_vec(), sig.ret().clone())),
+            None => self.callable_sig_from_fn_trait(ty, num_args),
+        }
+    }
    fn infer_expr_inner(&mut self, tgt_expr: ExprId, expected: &Expectation) -> Ty {
        let body = Arc::clone(&self.body); // avoid borrow checker problem
        let ty = match &body[tgt_expr] {
@@ -198,14 +250,23 @@ impl<'a> InferenceContext<'a> {
            }
            Expr::Call { callee, args } => {
                let callee_ty = self.infer_expr(*callee, &Expectation::none());
-                let (param_tys, ret_ty) = match callee_ty.callable_sig(self.db) {
+                let canonicalized = self.canonicalizer().canonicalize_ty(callee_ty.clone());
-                    Some(sig) => (sig.params().to_vec(), sig.ret().clone()),
+                let mut derefs = autoderef(
-                    None => {
+                    self.db,
-                        // Not callable
+                    self.resolver.krate(),
-                        // FIXME: report an error
+                    InEnvironment {
-                        (Vec::new(), Ty::Unknown)
+                        value: canonicalized.value.clone(),
-                    }
+                        environment: self.trait_env.clone(),
-                };
+                    },
+                );
+                let (param_tys, ret_ty): (Vec<Ty>, Ty) = derefs
+                    .find_map(|callee_deref_ty| {
+                        self.callable_sig(
+                            &canonicalized.decanonicalize_ty(callee_deref_ty.value),
+                            args.len(),
+                        )
+                    })
+                    .unwrap_or((Vec::new(), Ty::Unknown));
                self.register_obligations_for_call(&callee_ty);
                self.check_call_arguments(args, &param_tys);
                self.normalize_associated_types_in(ret_ty)
diff --git a/crates/ra_hir_ty/src/infer/path.rs b/crates/ra_hir_ty/src/infer/path.rs
index 1ad0d8397..80d7ed10e 100644
--- a/crates/ra_hir_ty/src/infer/path.rs
+++ b/crates/ra_hir_ty/src/infer/path.rs
@@ -81,7 +81,7 @@ impl<'a> InferenceContext<'a> {
                let generics = crate::utils::generics(self.db.upcast(), impl_id.into());
                let substs = Substs::type_params_for_generics(&generics);
                let ty = self.db.impl_self_ty(impl_id).subst(&substs);
-                if let Some((AdtId::StructId(struct_id), _)) = ty.as_adt() {
+                if let Some((AdtId::StructId(struct_id), substs)) = ty.as_adt() {
                    let ty = self.db.value_ty(struct_id.into()).subst(&substs);
                    return Some(ty);
                } else {
diff --git a/crates/ra_hir_ty/src/lib.rs b/crates/ra_hir_ty/src/lib.rs
index 2b9372b4b..f22232324 100644
--- a/crates/ra_hir_ty/src/lib.rs
+++ b/crates/ra_hir_ty/src/lib.rs
@@ -73,6 +73,7 @@ pub use lower::{
 pub use traits::{InEnvironment, Obligation, ProjectionPredicate, TraitEnvironment};
 pub use chalk_ir::{BoundVar, DebruijnIndex};
+use itertools::Itertools;
 /// A type constructor or type name: this might be something like the primitive
 /// type `bool`, a struct like `Vec`, or things like function pointers or
@@ -815,6 +816,11 @@ impl Ty {
        }
    }
+    /// If this is a `dyn Trait`, returns that trait.
+    pub fn dyn_trait(&self) -> Option<TraitId> {
+        self.dyn_trait_ref().map(|it| it.trait_)
+    }
    fn builtin_deref(&self) -> Option<Ty> {
        match self {
            Ty::Apply(a_ty) => match a_ty.ctor {
@@ -867,13 +873,56 @@ impl Ty {
        }
    }
-    /// If this is a `dyn Trait`, returns that trait.
+    pub fn impl_trait_bounds(&self, db: &dyn HirDatabase) -> Option<Vec<GenericPredicate>> {
-    pub fn dyn_trait(&self) -> Option<TraitId> {
        match self {
-            Ty::Dyn(predicates) => predicates.iter().find_map(|pred| match pred {
+            Ty::Opaque(opaque_ty) => {
-                GenericPredicate::Implemented(tr) => Some(tr.trait_),
+                let predicates = match opaque_ty.opaque_ty_id {
-                _ => None,
+                    OpaqueTyId::ReturnTypeImplTrait(func, idx) => {
-            }),
+                        db.return_type_impl_traits(func).map(|it| {
+                            let data = (*it)
+                                .as_ref()
+                                .map(|rpit| rpit.impl_traits[idx as usize].bounds.clone());
+                            data.clone().subst(&opaque_ty.parameters)
+                        })
+                    }
+                };
+                predicates.map(|it| it.value)
+            }
+            Ty::Placeholder(id) => {
+                let generic_params = db.generic_params(id.parent);
+                let param_data = &generic_params.types[id.local_id];
+                match param_data.provenance {
+                    hir_def::generics::TypeParamProvenance::ArgumentImplTrait => {
+                        let predicates = db
+                            .generic_predicates_for_param(*id)
+                            .into_iter()
+                            .map(|pred| pred.value.clone())
+                            .collect_vec();
+                        Some(predicates)
+                    }
+                    _ => None,
+                }
+            }
+            _ => None,
+        }
+    }
+    pub fn associated_type_parent_trait(&self, db: &dyn HirDatabase) -> Option<TraitId> {
+        match self {
+            Ty::Apply(ApplicationTy { ctor: TypeCtor::AssociatedType(type_alias_id), .. }) => {
+                match type_alias_id.lookup(db.upcast()).container {
+                    AssocContainerId::TraitId(trait_id) => Some(trait_id),
+                    _ => None,
+                }
+            }
+            Ty::Projection(projection_ty) => {
+                match projection_ty.associated_ty.lookup(db.upcast()).container {
+                    AssocContainerId::TraitId(trait_id) => Some(trait_id),
+                    _ => None,
+                }
+            }
            _ => None,
        }
    }
@@ -1057,5 +1106,5 @@ pub struct ReturnTypeImplTraits {
 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
 pub(crate) struct ReturnTypeImplTrait {
-    pub(crate) bounds: Binders<Vec<GenericPredicate>>,
+    pub bounds: Binders<Vec<GenericPredicate>>,
 }
diff --git a/crates/ra_hir_ty/src/lower.rs b/crates/ra_hir_ty/src/lower.rs
index 42713928f..d5154f436 100644
--- a/crates/ra_hir_ty/src/lower.rs
+++ b/crates/ra_hir_ty/src/lower.rs
@@ -337,17 +337,17 @@ impl Ty {
                    TraitRef::from_resolved_path(ctx, trait_, resolved_segment, self_ty);
                let ty = if remaining_segments.len() == 1 {
                    let segment = remaining_segments.first().unwrap();
-                    let associated_ty = associated_type_by_name_including_super_traits(
+                    let found = associated_type_by_name_including_super_traits(
-                        ctx.db.upcast(),
+                        ctx.db,
-                        trait_ref.trait_,
+                        trait_ref.clone(),
                        &segment.name,
                    );
-                    match associated_ty {
+                    match found {
-                        Some(associated_ty) => {
+                        Some((super_trait_ref, associated_ty)) => {
                            // FIXME handle type parameters on the segment
                            Ty::Projection(ProjectionTy {
                                associated_ty,
-                                parameters: trait_ref.substs,
+                                parameters: super_trait_ref.substs,
                            })
                        }
                        None => {
@@ -467,6 +467,9 @@ impl Ty {
                            }
                            TypeParamLoweringMode::Variable => t.substs.clone(),
                        };
+                        // We need to shift in the bound vars, since
+                        // associated_type_shorthand_candidates does not do that
+                        let substs = substs.shift_bound_vars(ctx.in_binders);
                        // FIXME handle type parameters on the segment
                        return Some(Ty::Projection(ProjectionTy {
                            associated_ty,
@@ -706,17 +709,17 @@ fn assoc_type_bindings_from_type_bound<'a>(
        .flat_map(|segment| segment.args_and_bindings.into_iter())
        .flat_map(|args_and_bindings| args_and_bindings.bindings.iter())
        .flat_map(move |binding| {
-            let associated_ty = associated_type_by_name_including_super_traits(
+            let found = associated_type_by_name_including_super_traits(
-                ctx.db.upcast(),
+                ctx.db,
-                trait_ref.trait_,
+                trait_ref.clone(),
                &binding.name,
            );
-            let associated_ty = match associated_ty {
+            let (super_trait_ref, associated_ty) = match found {
                None => return SmallVec::<[GenericPredicate; 1]>::new(),
                Some(t) => t,
            };
            let projection_ty =
-                ProjectionTy { associated_ty, parameters: trait_ref.substs.clone() };
+                ProjectionTy { associated_ty, parameters: super_trait_ref.substs.clone() };
            let mut preds = SmallVec::with_capacity(
                binding.type_ref.as_ref().map_or(0, |_| 1) + binding.bounds.len(),
            );
diff --git a/crates/ra_hir_ty/src/method_resolution.rs b/crates/ra_hir_ty/src/method_resolution.rs
index e83b39456..ed638c195 100644
--- a/crates/ra_hir_ty/src/method_resolution.rs
+++ b/crates/ra_hir_ty/src/method_resolution.rs
@@ -38,18 +38,53 @@ impl TyFingerprint {
    }
 }
+/// A queryable and mergeable collection of impls.
 #[derive(Debug, PartialEq, Eq)]
 pub struct CrateImplDefs {
-    impls: FxHashMap<TyFingerprint, Vec<ImplId>>,
+    inherent_impls: FxHashMap<TyFingerprint, Vec<ImplId>>,
    impls_by_trait: FxHashMap<TraitId, FxHashMap<Option<TyFingerprint>, Vec<ImplId>>>,
 }
 impl CrateImplDefs {
    pub(crate) fn impls_in_crate_query(db: &dyn HirDatabase, krate: CrateId) -> Arc<CrateImplDefs> {
        let _p = profile("impls_in_crate_query");
-        let mut res =
+        let mut res = CrateImplDefs {
-            CrateImplDefs { impls: FxHashMap::default(), impls_by_trait: FxHashMap::default() };
+            inherent_impls: FxHashMap::default(),
+            impls_by_trait: FxHashMap::default(),
+        };
+        res.fill(db, krate);
+        Arc::new(res)
+    }
+    /// Collects all impls from transitive dependencies of `krate` that may be used by `krate`.
+    ///
+    /// The full set of impls that can be used by `krate` is the returned map plus all the impls
+    /// from `krate` itself.
+    pub(crate) fn impls_from_deps_query(
+        db: &dyn HirDatabase,
+        krate: CrateId,
+    ) -> Arc<CrateImplDefs> {
+        let _p = profile("impls_from_deps_query");
+        let crate_graph = db.crate_graph();
+        let mut res = CrateImplDefs {
+            inherent_impls: FxHashMap::default(),
+            impls_by_trait: FxHashMap::default(),
+        };
+        // For each dependency, calculate `impls_from_deps` recursively, then add its own
+        // `impls_in_crate`.
+        // As we might visit crates multiple times, `merge` has to deduplicate impls to avoid
+        // wasting memory.
+        for dep in &crate_graph[krate].dependencies {
+            res.merge(&db.impls_from_deps(dep.crate_id));
+            res.merge(&db.impls_in_crate(dep.crate_id));
+        }
+        Arc::new(res)
+    }
+    fn fill(&mut self, db: &dyn HirDatabase, krate: CrateId) {
        let crate_def_map = db.crate_def_map(krate);
        for (_module_id, module_data) in crate_def_map.modules.iter() {
            for impl_id in module_data.scope.impls() {
@@ -57,7 +92,7 @@ impl CrateImplDefs {
                    Some(tr) => {
                        let self_ty = db.impl_self_ty(impl_id);
                        let self_ty_fp = TyFingerprint::for_impl(&self_ty.value);
-                        res.impls_by_trait
+                        self.impls_by_trait
                            .entry(tr.value.trait_)
                            .or_default()
                            .entry(self_ty_fp)
@@ -67,18 +102,36 @@ impl CrateImplDefs {
                    None => {
                        let self_ty = db.impl_self_ty(impl_id);
                        if let Some(self_ty_fp) = TyFingerprint::for_impl(&self_ty.value) {
-                            res.impls.entry(self_ty_fp).or_default().push(impl_id);
+                            self.inherent_impls.entry(self_ty_fp).or_default().push(impl_id);
                        }
                    }
                }
            }
        }
+    }
-        Arc::new(res)
+    fn merge(&mut self, other: &Self) {
+        for (fp, impls) in &other.inherent_impls {
+            let vec = self.inherent_impls.entry(*fp).or_default();
+            vec.extend(impls);
+            vec.sort();
+            vec.dedup();
+        }
+        for (trait_, other_map) in &other.impls_by_trait {
+            let map = self.impls_by_trait.entry(*trait_).or_default();
+            for (fp, impls) in other_map {
+                let vec = map.entry(*fp).or_default();
+                vec.extend(impls);
+                vec.sort();
+                vec.dedup();
+            }
+        }
    }
    pub fn lookup_impl_defs(&self, ty: &Ty) -> impl Iterator<Item = ImplId> + '_ {
        let fingerprint = TyFingerprint::for_impl(ty);
-        fingerprint.and_then(|f| self.impls.get(&f)).into_iter().flatten().copied()
+        fingerprint.and_then(|f| self.inherent_impls.get(&f)).into_iter().flatten().copied()
    }
    pub fn lookup_impl_defs_for_trait(&self, tr: TraitId) -> impl Iterator<Item = ImplId> + '_ {
@@ -110,7 +163,7 @@ impl CrateImplDefs {
    }
    pub fn all_impls<'a>(&'a self) -> impl Iterator<Item = ImplId> + 'a {
-        self.impls
+        self.inherent_impls
            .values()
            .chain(self.impls_by_trait.values().flat_map(|m| m.values()))