Split `CrateImplDefs` in inherent and trait impls

This makes the intention of inherent vs. trait impls somewhat more
clear and also fixes (?) an issue where trait impls with an unresolved
trait were added as inherent impls instead (hence the test changes).

7 files changed, 130 insertions, 118 deletions

diff --git a/crates/ra_hir/src/code_model.rs b/crates/ra_hir/src/code_model.rs
index e09eb77c2..cc72964ff 100644
--- a/crates/ra_hir/src/code_model.rs
+++ b/crates/ra_hir/src/code_model.rs
@@ -1053,12 +1053,14 @@ pub struct ImplDef {
 
 impl ImplDef {
     pub fn all_in_crate(db: &dyn HirDatabase, krate: Crate) -> Vec<ImplDef> {
-        let impls = db.impls_in_crate(krate.id);
-        impls.all_impls().map(Self::from).collect()
+        let inherent = db.inherent_impls_in_crate(krate.id);
+        let trait_ = db.trait_impls_in_crate(krate.id);
+
+        inherent.all_impls().chain(trait_.all_impls()).map(Self::from).collect()
     }
     pub fn for_trait(db: &dyn HirDatabase, krate: Crate, trait_: Trait) -> Vec<ImplDef> {
-        let impls = db.impls_in_crate(krate.id);
-        impls.lookup_impl_defs_for_trait(trait_.id).map(Self::from).collect()
+        let impls = db.trait_impls_in_crate(krate.id);
+        impls.for_trait(trait_.id).map(Self::from).collect()
     }
 
     pub fn target_trait(self, db: &dyn HirDatabase) -> Option<TypeRef> {
@@ -1303,10 +1305,10 @@ impl Type {
         mut callback: impl FnMut(AssocItem) -> Option<T>,
     ) -> Option<T> {
         for krate in self.ty.value.def_crates(db, krate.id)? {
-            let impls = db.impls_in_crate(krate);
+            let impls = db.inherent_impls_in_crate(krate);
 
-            for impl_def in impls.lookup_impl_defs(&self.ty.value) {
-                for &item in db.impl_data(impl_def).items.iter() {
+            for impl_def in impls.for_self_ty(&self.ty.value) {
+                for &item in db.impl_data(*impl_def).items.iter() {
                     if let Some(result) = callback(item.into()) {
                         return Some(result);
                     }
diff --git a/crates/ra_hir/src/db.rs b/crates/ra_hir/src/db.rs
index bb67952de..cb48ca065 100644
--- a/crates/ra_hir/src/db.rs
+++ b/crates/ra_hir/src/db.rs
@@ -16,10 +16,10 @@ pub use hir_expand::db::{
 pub use hir_ty::db::{
     AssociatedTyDataQuery, AssociatedTyValueQuery, CallableItemSignatureQuery, FieldTypesQuery,
     GenericDefaultsQuery, GenericPredicatesForParamQuery, GenericPredicatesQuery, HirDatabase,
-    HirDatabaseStorage, ImplDatumQuery, ImplSelfTyQuery, ImplTraitQuery, ImplsFromDepsQuery,
-    ImplsInCrateQuery, InferQueryQuery, InternAssocTyValueQuery, InternChalkImplQuery,
-    InternTypeCtorQuery, InternTypeParamIdQuery, ReturnTypeImplTraitsQuery, StructDatumQuery,
-    TraitDatumQuery, TraitSolveQuery, TyQuery, ValueTyQuery,
+    HirDatabaseStorage, ImplDatumQuery, ImplSelfTyQuery, ImplTraitQuery, InferQueryQuery,
+    InherentImplsInCrateQuery, InternAssocTyValueQuery, InternChalkImplQuery, InternTypeCtorQuery,
+    InternTypeParamIdQuery, ReturnTypeImplTraitsQuery, StructDatumQuery, TraitDatumQuery,
+    TraitImplsInCrateQuery, TraitImplsInDepsQuery, TraitSolveQuery, TyQuery, ValueTyQuery,
 };
 
 #[test]
diff --git a/crates/ra_hir_ty/src/db.rs b/crates/ra_hir_ty/src/db.rs
index cad553273..dc06c0ee7 100644
--- a/crates/ra_hir_ty/src/db.rs
+++ b/crates/ra_hir_ty/src/db.rs
@@ -11,7 +11,7 @@ use ra_db::{impl_intern_key, salsa, CrateId, Upcast};
 use ra_prof::profile;
 
 use crate::{
-    method_resolution::CrateImplDefs,
+    method_resolution::{InherentImpls, TraitImpls},
     traits::{chalk, AssocTyValue, Impl},
     Binders, CallableDef, GenericPredicate, InferenceResult, OpaqueTyId, PolyFnSig,
     ReturnTypeImplTraits, TraitRef, Ty, TyDefId, TypeCtor, ValueTyDefId,
@@ -67,11 +67,14 @@ pub trait HirDatabase: DefDatabase + Upcast<dyn DefDatabase> {
     #[salsa::invoke(crate::lower::generic_defaults_query)]
     fn generic_defaults(&self, def: GenericDefId) -> Arc<[Binders<Ty>]>;
 
-    #[salsa::invoke(crate::method_resolution::CrateImplDefs::impls_in_crate_query)]
-    fn impls_in_crate(&self, krate: CrateId) -> Arc<CrateImplDefs>;
+    #[salsa::invoke(InherentImpls::inherent_impls_in_crate_query)]
+    fn inherent_impls_in_crate(&self, krate: CrateId) -> Arc<InherentImpls>;
 
-    #[salsa::invoke(crate::method_resolution::CrateImplDefs::impls_from_deps_query)]
-    fn impls_from_deps(&self, krate: CrateId) -> Arc<CrateImplDefs>;
+    #[salsa::invoke(TraitImpls::trait_impls_in_crate_query)]
+    fn trait_impls_in_crate(&self, krate: CrateId) -> Arc<TraitImpls>;
+
+    #[salsa::invoke(TraitImpls::trait_impls_in_deps_query)]
+    fn trait_impls_in_deps(&self, krate: CrateId) -> Arc<TraitImpls>;
 
     // Interned IDs for Chalk integration
     #[salsa::interned]
diff --git a/crates/ra_hir_ty/src/method_resolution.rs b/crates/ra_hir_ty/src/method_resolution.rs
index 201604e1d..5dbabd12b 100644
--- a/crates/ra_hir_ty/src/method_resolution.rs
+++ b/crates/ra_hir_ty/src/method_resolution.rs
@@ -38,81 +38,55 @@ impl TyFingerprint {
     }
 }
 
-/// A queryable and mergeable collection of impls.
-#[derive(Debug, PartialEq, Eq)]
-pub struct CrateImplDefs {
-    inherent_impls: FxHashMap<TyFingerprint, Vec<ImplId>>,
-    impls_by_trait: FxHashMap<TraitId, FxHashMap<Option<TyFingerprint>, Vec<ImplId>>>,
+/// Trait impls defined or available in some crate.
+#[derive(Debug, Eq, PartialEq)]
+pub struct TraitImpls {
+    // If the `Option<TyFingerprint>` is `None`, the impl may apply to any self type.
+    map: 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 = CrateImplDefs {
-            inherent_impls: FxHashMap::default(),
-            impls_by_trait: FxHashMap::default(),
-        };
-        res.fill(db, krate);
+impl TraitImpls {
+    pub(crate) fn trait_impls_in_crate_query(db: &dyn HirDatabase, krate: CrateId) -> Arc<Self> {
+        let _p = profile("trait_impls_in_crate_query");
+        let mut impls = Self { map: FxHashMap::default() };
 
-        Arc::new(res)
+        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() {
+                let target_trait = match db.impl_trait(impl_id) {
+                    Some(tr) => tr.value.trait_,
+                    None => continue,
+                };
+                let self_ty = db.impl_self_ty(impl_id);
+                let self_ty_fp = TyFingerprint::for_impl(&self_ty.value);
+                impls
+                    .map
+                    .entry(target_trait)
+                    .or_default()
+                    .entry(self_ty_fp)
+                    .or_default()
+                    .push(impl_id);
+            }
+        }
+
+        Arc::new(impls)
     }
 
-    /// 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");
+    pub(crate) fn trait_impls_in_deps_query(db: &dyn HirDatabase, krate: CrateId) -> Arc<Self> {
+        let _p = profile("trait_impls_in_deps_query");
         let crate_graph = db.crate_graph();
-        let mut res = CrateImplDefs {
-            inherent_impls: FxHashMap::default(),
-            impls_by_trait: FxHashMap::default(),
-        };
+        let mut res = Self { map: FxHashMap::default() };
 
         for krate in crate_graph.transitive_deps(krate) {
-            res.merge(&db.impls_in_crate(krate));
+            res.merge(&db.trait_impls_in_crate(krate));
         }
 
         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() {
-                match db.impl_trait(impl_id) {
-                    Some(tr) => {
-                        let self_ty = db.impl_self_ty(impl_id);
-                        let self_ty_fp = TyFingerprint::for_impl(&self_ty.value);
-                        self.impls_by_trait
-                            .entry(tr.value.trait_)
-                            .or_default()
-                            .entry(self_ty_fp)
-                            .or_default()
-                            .push(impl_id);
-                    }
-                    None => {
-                        let self_ty = db.impl_self_ty(impl_id);
-                        if let Some(self_ty_fp) = TyFingerprint::for_impl(&self_ty.value) {
-                            self.inherent_impls.entry(self_ty_fp).or_default().push(impl_id);
-                        }
-                    }
-                }
-            }
-        }
-    }
-
     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);
-        }
-
-        for (trait_, other_map) in &other.impls_by_trait {
-            let map = self.impls_by_trait.entry(*trait_).or_default();
+        for (trait_, other_map) in &other.map {
+            let map = self.map.entry(*trait_).or_default();
             for (fp, impls) in other_map {
                 let vec = map.entry(*fp).or_default();
                 vec.extend(impls);
@@ -120,45 +94,75 @@ impl CrateImplDefs {
         }
     }
 
-    pub fn lookup_impl_defs(&self, ty: &Ty) -> impl Iterator<Item = ImplId> + '_ {
-        let fingerprint = TyFingerprint::for_impl(ty);
-        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> + '_ {
-        self.impls_by_trait
-            .get(&tr)
+    /// Queries all impls of the given trait.
+    pub fn for_trait(&self, trait_: TraitId) -> impl Iterator<Item = ImplId> + '_ {
+        self.map
+            .get(&trait_)
             .into_iter()
-            .flat_map(|m| m.values().flat_map(|v| v.iter().copied()))
+            .flat_map(|map| map.values().flat_map(|v| v.iter().copied()))
     }
 
-    pub fn lookup_impl_defs_for_trait_and_ty(
+    /// Queries all impls of `trait_` that may apply to `self_ty`.
+    pub fn for_trait_and_self_ty(
         &self,
-        tr: TraitId,
-        fp: TyFingerprint,
+        trait_: TraitId,
+        self_ty: TyFingerprint,
     ) -> impl Iterator<Item = ImplId> + '_ {
-        self.impls_by_trait
-            .get(&tr)
-            .and_then(|m| m.get(&Some(fp)))
+        self.map
+            .get(&trait_)
             .into_iter()
-            .flatten()
-            .copied()
-            .chain(
-                self.impls_by_trait
-                    .get(&tr)
-                    .and_then(|m| m.get(&None))
-                    .into_iter()
-                    .flatten()
-                    .copied(),
-            )
+            .flat_map(move |map| map.get(&None).into_iter().chain(map.get(&Some(self_ty))))
+            .flat_map(|v| v.iter().copied())
+    }
+
+    pub fn all_impls(&self) -> impl Iterator<Item = ImplId> + '_ {
+        self.map.values().flat_map(|map| map.values().flat_map(|v| v.iter().copied()))
+    }
+}
+
+/// Inherent impls defined in some crate.
+///
+/// Inherent impls can only be defined in the crate that also defines the self type of the impl
+/// (note that some primitives are considered to be defined by both libcore and liballoc).
+///
+/// This makes inherent impl lookup easier than trait impl lookup since we only have to consider a
+/// single crate.
+#[derive(Debug, Eq, PartialEq)]
+pub struct InherentImpls {
+    map: FxHashMap<TyFingerprint, Vec<ImplId>>,
+}
+
+impl InherentImpls {
+    pub(crate) fn inherent_impls_in_crate_query(db: &dyn HirDatabase, krate: CrateId) -> Arc<Self> {
+        let mut map: FxHashMap<_, Vec<_>> = FxHashMap::default();
+
+        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() {
+                let data = db.impl_data(impl_id);
+                if data.target_trait.is_some() {
+                    continue;
+                }
+
+                let self_ty = db.impl_self_ty(impl_id);
+                if let Some(fp) = TyFingerprint::for_impl(&self_ty.value) {
+                    map.entry(fp).or_default().push(impl_id);
+                }
+            }
+        }
+
+        Arc::new(Self { map })
+    }
+
+    pub fn for_self_ty(&self, self_ty: &Ty) -> &[ImplId] {
+        match TyFingerprint::for_impl(self_ty) {
+            Some(fp) => self.map.get(&fp).map(|vec| vec.as_ref()).unwrap_or(&[]),
+            None => &[],
+        }
     }
 
-    pub fn all_impls<'a>(&'a self) -> impl Iterator<Item = ImplId> + 'a {
-        self.inherent_impls
-            .values()
-            .chain(self.impls_by_trait.values().flat_map(|m| m.values()))
-            .flatten()
-            .copied()
+    pub fn all_impls(&self) -> impl Iterator<Item = ImplId> + '_ {
+        self.map.values().flat_map(|v| v.iter().copied())
     }
 }
 
@@ -515,9 +519,9 @@ fn iterate_inherent_methods(
         None => return false,
     };
     for krate in def_crates {
-        let impls = db.impls_in_crate(krate);
+        let impls = db.inherent_impls_in_crate(krate);
 
-        for impl_def in impls.lookup_impl_defs(&self_ty.value) {
+        for &impl_def in impls.for_self_ty(&self_ty.value) {
             for &item in db.impl_data(impl_def).items.iter() {
                 if !is_valid_candidate(db, name, receiver_ty, item, self_ty) {
                     continue;
diff --git a/crates/ra_hir_ty/src/traits/chalk.rs b/crates/ra_hir_ty/src/traits/chalk.rs
index 8ef4941c0..c97b81d57 100644
--- a/crates/ra_hir_ty/src/traits/chalk.rs
+++ b/crates/ra_hir_ty/src/traits/chalk.rs
@@ -77,8 +77,8 @@ impl<'a> chalk_solve::RustIrDatabase<Interner> for ChalkContext<'a> {
         // Note: Since we're using impls_for_trait, only impls where the trait
         // can be resolved should ever reach Chalk. `impl_datum` relies on that
         // and will panic if the trait can't be resolved.
-        let in_deps = self.db.impls_from_deps(self.krate);
-        let in_self = self.db.impls_in_crate(self.krate);
+        let in_deps = self.db.trait_impls_in_deps(self.krate);
+        let in_self = self.db.trait_impls_in_crate(self.krate);
         let impl_maps = [in_deps, in_self];
 
         let id_to_chalk = |id: hir_def::ImplId| Impl::ImplDef(id).to_chalk(self.db);
@@ -87,14 +87,12 @@ impl<'a> chalk_solve::RustIrDatabase<Interner> for ChalkContext<'a> {
             Some(fp) => impl_maps
                 .iter()
                 .flat_map(|crate_impl_defs| {
-                    crate_impl_defs.lookup_impl_defs_for_trait_and_ty(trait_, fp).map(id_to_chalk)
+                    crate_impl_defs.for_trait_and_self_ty(trait_, fp).map(id_to_chalk)
                 })
                 .collect(),
             None => impl_maps
                 .iter()
-                .flat_map(|crate_impl_defs| {
-                    crate_impl_defs.lookup_impl_defs_for_trait(trait_).map(id_to_chalk)
-                })
+                .flat_map(|crate_impl_defs| crate_impl_defs.for_trait(trait_).map(id_to_chalk))
                 .collect(),
         };
 
diff --git a/crates/ra_ide/src/goto_implementation.rs b/crates/ra_ide/src/goto_implementation.rs
index 99a7022a4..9acc960fc 100644
--- a/crates/ra_ide/src/goto_implementation.rs
+++ b/crates/ra_ide/src/goto_implementation.rs
@@ -219,6 +219,10 @@ impl T for &Foo {}
   #[derive(Copy)]
 //^^^^^^^^^^^^^^^
 struct Foo<|>;
+
+mod marker {
+    trait Copy {}
+}
 "#,
         );
     }
diff --git a/crates/ra_ide_db/src/change.rs b/crates/ra_ide_db/src/change.rs
index b507000f2..dbe6eacc5 100644
--- a/crates/ra_ide_db/src/change.rs
+++ b/crates/ra_ide_db/src/change.rs
@@ -243,8 +243,9 @@ impl RootDatabase {
             hir::db::GenericPredicatesForParamQuery
             hir::db::GenericPredicatesQuery
             hir::db::GenericDefaultsQuery
-            hir::db::ImplsInCrateQuery
-            hir::db::ImplsFromDepsQuery
+            hir::db::InherentImplsInCrateQuery
+            hir::db::TraitImplsInCrateQuery
+            hir::db::TraitImplsInDepsQuery
             hir::db::InternTypeCtorQuery
             hir::db::InternTypeParamIdQuery
             hir::db::InternChalkImplQuery