Merge #8020

8020: Power up goto_implementation r=matklad a=Veykril

by allowing it to be invoked on references of names, now showing all (trait)
implementations of the given type in all crates instead of just the defining
crate as well as including support for builtin types

![image](https://user-images.githubusercontent.com/3757771/111144403-52bb0700-8587-11eb-9205-7a2a5b8b75a3.png)
Example screenshot of `impl`s of Box in `log`, `alloc`, `std` and the current crate. Before you had to invoke it on the definition where it would only show the `impls` in `alloc`.

Co-authored-by: Lukas Wirth <[email protected]>

4 files changed, 136 insertions, 64 deletions

diff --git a/crates/hir/src/lib.rs b/crates/hir/src/lib.rs
index 25e5bfb01..c5161dadd 100644
--- a/crates/hir/src/lib.rs
+++ b/crates/hir/src/lib.rs
@@ -51,7 +51,8 @@ use hir_expand::{diagnostics::DiagnosticSink, name::name, MacroDefKind};
 use hir_ty::{
     autoderef,
     display::{write_bounds_like_dyn_trait_with_prefix, HirDisplayError, HirFormatter},
-    method_resolution, to_assoc_type_id,
+    method_resolution::{self, TyFingerprint},
+    to_assoc_type_id,
     traits::{FnTrait, Solution, SolutionVariables},
     AliasTy, BoundVar, CallableDefId, CallableSig, Canonical, DebruijnIndex, GenericPredicate,
     InEnvironment, Interner, Obligation, ProjectionPredicate, ProjectionTy, Scalar, Substs, Ty,
@@ -695,8 +696,8 @@ impl Adt {
         }
     }
 
-    pub fn krate(self, db: &dyn HirDatabase) -> Option<Crate> {
-        Some(self.module(db).krate())
+    pub fn krate(self, db: &dyn HirDatabase) -> Crate {
+        self.module(db).krate()
     }
 
     pub fn name(self, db: &dyn HirDatabase) -> Name {
@@ -1018,8 +1019,8 @@ impl TypeAlias {
         Module { id: self.id.lookup(db.upcast()).module(db.upcast()) }
     }
 
-    pub fn krate(self, db: &dyn HirDatabase) -> Option<Crate> {
-        Some(self.module(db).krate())
+    pub fn krate(self, db: &dyn HirDatabase) -> Crate {
+        self.module(db).krate()
     }
 
     pub fn type_ref(self, db: &dyn HirDatabase) -> Option<TypeRef> {
@@ -1482,9 +1483,44 @@ impl Impl {
 
         inherent.all_impls().chain(trait_.all_impls()).map(Self::from).collect()
     }
-    pub fn for_trait(db: &dyn HirDatabase, krate: Crate, trait_: Trait) -> Vec<Impl> {
-        let impls = db.trait_impls_in_crate(krate.id);
-        impls.for_trait(trait_.id).map(Self::from).collect()
+
+    pub fn all_for_type(db: &dyn HirDatabase, Type { krate, ty }: Type) -> Vec<Impl> {
+        let def_crates = match ty.value.def_crates(db, krate) {
+            Some(def_crates) => def_crates,
+            None => return Vec::new(),
+        };
+
+        let filter = |impl_def: &Impl| {
+            let target_ty = impl_def.target_ty(db);
+            let rref = target_ty.remove_ref();
+            ty.value.equals_ctor(rref.as_ref().map_or(&target_ty.ty.value, |it| &it.ty.value))
+        };
+
+        let mut all = Vec::new();
+        def_crates.into_iter().for_each(|id| {
+            all.extend(db.inherent_impls_in_crate(id).all_impls().map(Self::from).filter(filter))
+        });
+        let fp = TyFingerprint::for_impl(&ty.value);
+        for id in db.crate_graph().iter() {
+            match fp {
+                Some(fp) => all.extend(
+                    db.trait_impls_in_crate(id).for_self_ty(fp).map(Self::from).filter(filter),
+                ),
+                None => all
+                    .extend(db.trait_impls_in_crate(id).all_impls().map(Self::from).filter(filter)),
+            }
+        }
+        all
+    }
+
+    pub fn all_for_trait(db: &dyn HirDatabase, trait_: Trait) -> Vec<Impl> {
+        let krate = trait_.module(db).krate();
+        let mut all = Vec::new();
+        for Crate { id } in krate.reverse_dependencies(db).into_iter().chain(Some(krate)) {
+            let impls = db.trait_impls_in_crate(id);
+            all.extend(impls.for_trait(trait_.id).map(Self::from))
+        }
+        all
     }
 
     // FIXME: the return type is wrong. This should be a hir version of
@@ -1932,12 +1968,6 @@ impl Type {
         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 {
-        let rref = other.remove_ref();
-        self.ty.value.equals_ctor(rref.as_ref().map_or(&other.ty.value, |it| &it.ty.value))
-    }
-
     fn derived(&self, ty: Ty) -> Type {
         Type {
             krate: self.krate,
diff --git a/crates/hir_ty/src/method_resolution.rs b/crates/hir_ty/src/method_resolution.rs
index 741440006..be72c4a1c 100644
--- a/crates/hir_ty/src/method_resolution.rs
+++ b/crates/hir_ty/src/method_resolution.rs
@@ -44,7 +44,7 @@ impl TyFingerprint {
     /// Creates a TyFingerprint for looking up an impl. Only certain types can
     /// have impls: if we have some `struct S`, we can have an `impl S`, but not
     /// `impl &S`. Hence, this will return `None` for reference types and such.
-    pub(crate) fn for_impl(ty: &Ty) -> Option<TyFingerprint> {
+    pub fn for_impl(ty: &Ty) -> Option<TyFingerprint> {
         let fp = match *ty.interned(&Interner) {
             TyKind::Str => TyFingerprint::Str,
             TyKind::Never => TyFingerprint::Never,
@@ -141,6 +141,14 @@ impl TraitImpls {
         }
     }
 
+    /// Queries all trait impls for the given type.
+    pub fn for_self_ty(&self, fp: TyFingerprint) -> impl Iterator<Item = ImplId> + '_ {
+        self.map
+            .values()
+            .flat_map(move |impls| impls.get(&None).into_iter().chain(impls.get(&Some(fp))))
+            .flat_map(|it| it.iter().copied())
+    }
+
     /// Queries all impls of the given trait.
     pub fn for_trait(&self, trait_: TraitId) -> impl Iterator<Item = ImplId> + '_ {
         self.map
diff --git a/crates/ide/src/goto_implementation.rs b/crates/ide/src/goto_implementation.rs
index 3990305fc..f4d7c14a6 100644
--- a/crates/ide/src/goto_implementation.rs
+++ b/crates/ide/src/goto_implementation.rs
@@ -1,6 +1,9 @@
-use hir::{Crate, Impl, Semantics};
-use ide_db::RootDatabase;
-use syntax::{algo::find_node_at_offset, ast, AstNode};
+use hir::{Impl, Semantics};
+use ide_db::{
+    defs::{Definition, NameClass, NameRefClass},
+    RootDatabase,
+};
+use syntax::{ast, AstNode};
 
 use crate::{display::TryToNav, FilePosition, NavigationTarget, RangeInfo};
 
@@ -21,55 +24,42 @@ pub(crate) fn goto_implementation(
     let source_file = sema.parse(position.file_id);
     let syntax = source_file.syntax().clone();
 
-    let krate = sema.to_module_def(position.file_id)?.krate();
-
-    if let Some(nominal_def) = find_node_at_offset::<ast::Adt>(&syntax, position.offset) {
-        return Some(RangeInfo::new(
-            nominal_def.syntax().text_range(),
-            impls_for_def(&sema, &nominal_def, krate)?,
-        ));
-    } else if let Some(trait_def) = find_node_at_offset::<ast::Trait>(&syntax, position.offset) {
-        return Some(RangeInfo::new(
-            trait_def.syntax().text_range(),
-            impls_for_trait(&sema, &trait_def, krate)?,
-        ));
-    }
-
-    None
-}
-
-fn impls_for_def(
-    sema: &Semantics<RootDatabase>,
-    node: &ast::Adt,
-    krate: Crate,
-) -> Option<Vec<NavigationTarget>> {
-    let ty = match node {
-        ast::Adt::Struct(def) => sema.to_def(def)?.ty(sema.db),
-        ast::Adt::Enum(def) => sema.to_def(def)?.ty(sema.db),
-        ast::Adt::Union(def) => sema.to_def(def)?.ty(sema.db),
+    let node = sema.find_node_at_offset_with_descend(&syntax, position.offset)?;
+    let def = match &node {
+        ast::NameLike::Name(name) => {
+            NameClass::classify(&sema, name).map(|class| class.referenced_or_defined(sema.db))
+        }
+        ast::NameLike::NameRef(name_ref) => {
+            NameRefClass::classify(&sema, name_ref).map(|class| class.referenced(sema.db))
+        }
+        ast::NameLike::Lifetime(_) => None,
+    }?;
+    let def = match def {
+        Definition::ModuleDef(def) => def,
+        _ => return None,
     };
-
-    let impls = Impl::all_in_crate(sema.db, krate);
-
-    Some(
-        impls
-            .into_iter()
-            .filter(|impl_def| ty.is_equal_for_find_impls(&impl_def.target_ty(sema.db)))
-            .filter_map(|imp| imp.try_to_nav(sema.db))
-            .collect(),
-    )
+    let navs = match def {
+        hir::ModuleDef::Trait(trait_) => impls_for_trait(&sema, trait_),
+        hir::ModuleDef::Adt(adt) => impls_for_ty(&sema, adt.ty(sema.db)),
+        hir::ModuleDef::TypeAlias(alias) => impls_for_ty(&sema, alias.ty(sema.db)),
+        hir::ModuleDef::BuiltinType(builtin) => {
+            let module = sema.to_module_def(position.file_id)?;
+            impls_for_ty(&sema, builtin.ty(sema.db, module))
+        }
+        _ => return None,
+    };
+    Some(RangeInfo { range: node.syntax().text_range(), info: navs })
 }
 
-fn impls_for_trait(
-    sema: &Semantics<RootDatabase>,
-    node: &ast::Trait,
-    krate: Crate,
-) -> Option<Vec<NavigationTarget>> {
-    let tr = sema.to_def(node)?;
-
-    let impls = Impl::for_trait(sema.db, krate, tr);
+fn impls_for_ty(sema: &Semantics<RootDatabase>, ty: hir::Type) -> Vec<NavigationTarget> {
+    Impl::all_for_type(sema.db, ty).into_iter().filter_map(|imp| imp.try_to_nav(sema.db)).collect()
+}
 
-    Some(impls.into_iter().filter_map(|imp| imp.try_to_nav(sema.db)).collect())
+fn impls_for_trait(sema: &Semantics<RootDatabase>, trait_: hir::Trait) -> Vec<NavigationTarget> {
+    Impl::all_for_trait(sema.db, trait_)
+        .into_iter()
+        .filter_map(|imp| imp.try_to_nav(sema.db))
+        .collect()
 }
 
 #[cfg(test)]
@@ -226,4 +216,48 @@ macro Copy {}
 "#,
         );
     }
+
+    #[test]
+    fn goto_implementation_type_alias() {
+        check(
+            r#"
+struct Foo;
+
+type Bar$0 = Foo;
+
+impl Foo {}
+   //^^^
+impl Bar {}
+   //^^^
+"#,
+        );
+    }
+
+    #[test]
+    fn goto_implementation_adt_generic() {
+        check(
+            r#"
+struct Foo$0<T>;
+
+impl<T> Foo<T> {}
+      //^^^^^^
+impl Foo<str> {}
+   //^^^^^^^^
+"#,
+        );
+    }
+
+    #[test]
+    fn goto_implementation_builtin() {
+        check(
+            r#"
+//- /lib.rs crate:main deps:core
+fn foo(_: bool$0) {{}}
+//- /libcore.rs crate:core
+#[lang = "bool"]
+impl bool {}
+   //^^^^
+"#,
+        );
+    }
 }
diff --git a/crates/ide/src/inlay_hints.rs b/crates/ide/src/inlay_hints.rs
index 4ceb20742..16c04eeee 100644
--- a/crates/ide/src/inlay_hints.rs
+++ b/crates/ide/src/inlay_hints.rs
@@ -219,7 +219,7 @@ fn hint_iterator(
     let strukt = std::iter::successors(Some(ty.clone()), |ty| ty.remove_ref())
         .last()
         .and_then(|strukt| strukt.as_adt())?;
-    let krate = strukt.krate(db)?;
+    let krate = strukt.krate(db);
     if krate != famous_defs.core()? {
         return None;
     }