1 files changed, 135 insertions, 64 deletions

diff --git a/crates/ra_hir_ty/src/method_resolution.rs b/crates/ra_hir_ty/src/method_resolution.rs
index e83b39456..c19519cf1 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 =
-            CrateImplDefs { impls: FxHashMap::default(), impls_by_trait: FxHashMap::default() };
+        let mut res = CrateImplDefs {
+            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);
                         }
                     }
                 }
             }
         }
+    }
+
+    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();
+        }
 
-        Arc::new(res)
+        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()))
             .flatten()
@@ -218,6 +271,34 @@ pub fn iterate_method_candidates<T>(
     mode: LookupMode,
     mut callback: impl FnMut(&Ty, AssocItemId) -> Option<T>,
 ) -> Option<T> {
+    let mut slot = None;
+    iterate_method_candidates_impl(
+        ty,
+        db,
+        env,
+        krate,
+        traits_in_scope,
+        name,
+        mode,
+        &mut |ty, item| {
+            assert!(slot.is_none());
+            slot = callback(ty, item);
+            slot.is_some()
+        },
+    );
+    slot
+}
+
+fn iterate_method_candidates_impl(
+    ty: &Canonical<Ty>,
+    db: &dyn HirDatabase,
+    env: Arc<TraitEnvironment>,
+    krate: CrateId,
+    traits_in_scope: &FxHashSet<TraitId>,
+    name: Option<&Name>,
+    mode: LookupMode,
+    callback: &mut dyn FnMut(&Ty, AssocItemId) -> bool,
+) -> bool {
     match mode {
         LookupMode::MethodCall => {
             // For method calls, rust first does any number of autoderef, and then one
@@ -245,19 +326,19 @@ pub fn iterate_method_candidates<T>(
 
             let deref_chain = autoderef_method_receiver(db, krate, ty);
             for i in 0..deref_chain.len() {
-                if let Some(result) = iterate_method_candidates_with_autoref(
+                if iterate_method_candidates_with_autoref(
                     &deref_chain[i..],
                     db,
                     env.clone(),
                     krate,
                     traits_in_scope,
                     name,
-                    &mut callback,
+                    callback,
                 ) {
-                    return Some(result);
+                    return true;
                 }
             }
-            None
+            false
         }
         LookupMode::Path => {
             // No autoderef for path lookups
@@ -268,22 +349,22 @@ pub fn iterate_method_candidates<T>(
                 krate,
                 traits_in_scope,
                 name,
-                &mut callback,
+                callback,
             )
         }
     }
 }
 
-fn iterate_method_candidates_with_autoref<T>(
+fn iterate_method_candidates_with_autoref(
     deref_chain: &[Canonical<Ty>],
     db: &dyn HirDatabase,
     env: Arc<TraitEnvironment>,
     krate: CrateId,
     traits_in_scope: &FxHashSet<TraitId>,
     name: Option<&Name>,
-    mut callback: impl FnMut(&Ty, AssocItemId) -> Option<T>,
-) -> Option<T> {
-    if let Some(result) = iterate_method_candidates_by_receiver(
+    mut callback: &mut dyn FnMut(&Ty, AssocItemId) -> bool,
+) -> bool {
+    if iterate_method_candidates_by_receiver(
         &deref_chain[0],
         &deref_chain[1..],
         db,
@@ -293,13 +374,13 @@ fn iterate_method_candidates_with_autoref<T>(
         name,
         &mut callback,
     ) {
-        return Some(result);
+        return true;
     }
     let refed = Canonical {
         num_vars: deref_chain[0].num_vars,
         value: Ty::apply_one(TypeCtor::Ref(Mutability::Shared), deref_chain[0].value.clone()),
     };
-    if let Some(result) = iterate_method_candidates_by_receiver(
+    if iterate_method_candidates_by_receiver(
         &refed,
         deref_chain,
         db,
@@ -309,13 +390,13 @@ fn iterate_method_candidates_with_autoref<T>(
         name,
         &mut callback,
     ) {
-        return Some(result);
+        return true;
     }
     let ref_muted = Canonical {
         num_vars: deref_chain[0].num_vars,
         value: Ty::apply_one(TypeCtor::Ref(Mutability::Mut), deref_chain[0].value.clone()),
     };
-    if let Some(result) = iterate_method_candidates_by_receiver(
+    if iterate_method_candidates_by_receiver(
         &ref_muted,
         deref_chain,
         db,
@@ -325,12 +406,12 @@ fn iterate_method_candidates_with_autoref<T>(
         name,
         &mut callback,
     ) {
-        return Some(result);
+        return true;
     }
-    None
+    false
 }
 
-fn iterate_method_candidates_by_receiver<T>(
+fn iterate_method_candidates_by_receiver(
     receiver_ty: &Canonical<Ty>,
     rest_of_deref_chain: &[Canonical<Ty>],
     db: &dyn HirDatabase,
@@ -338,20 +419,18 @@ fn iterate_method_candidates_by_receiver<T>(
     krate: CrateId,
     traits_in_scope: &FxHashSet<TraitId>,
     name: Option<&Name>,
-    mut callback: impl FnMut(&Ty, AssocItemId) -> Option<T>,
-) -> Option<T> {
+    mut callback: &mut dyn FnMut(&Ty, AssocItemId) -> bool,
+) -> bool {
     // We're looking for methods with *receiver* type receiver_ty. These could
     // be found in any of the derefs of receiver_ty, so we have to go through
     // that.
     for self_ty in std::iter::once(receiver_ty).chain(rest_of_deref_chain) {
-        if let Some(result) =
-            iterate_inherent_methods(self_ty, db, name, Some(receiver_ty), krate, &mut callback)
-        {
-            return Some(result);
+        if iterate_inherent_methods(self_ty, db, name, Some(receiver_ty), krate, &mut callback) {
+            return true;
         }
     }
     for self_ty in std::iter::once(receiver_ty).chain(rest_of_deref_chain) {
-        if let Some(result) = iterate_trait_method_candidates(
+        if iterate_trait_method_candidates(
             self_ty,
             db,
             env.clone(),
@@ -361,40 +440,28 @@ fn iterate_method_candidates_by_receiver<T>(
             Some(receiver_ty),
             &mut callback,
         ) {
-            return Some(result);
+            return true;
         }
     }
-    None
+    false
 }
 
-fn iterate_method_candidates_for_self_ty<T>(
+fn iterate_method_candidates_for_self_ty(
     self_ty: &Canonical<Ty>,
     db: &dyn HirDatabase,
     env: Arc<TraitEnvironment>,
     krate: CrateId,
     traits_in_scope: &FxHashSet<TraitId>,
     name: Option<&Name>,
-    mut callback: impl FnMut(&Ty, AssocItemId) -> Option<T>,
-) -> Option<T> {
-    if let Some(result) = iterate_inherent_methods(self_ty, db, name, None, krate, &mut callback) {
-        return Some(result);
-    }
-    if let Some(result) = iterate_trait_method_candidates(
-        self_ty,
-        db,
-        env,
-        krate,
-        traits_in_scope,
-        name,
-        None,
-        &mut callback,
-    ) {
-        return Some(result);
+    mut callback: &mut dyn FnMut(&Ty, AssocItemId) -> bool,
+) -> bool {
+    if iterate_inherent_methods(self_ty, db, name, None, krate, &mut callback) {
+        return true;
     }
-    None
+    iterate_trait_method_candidates(self_ty, db, env, krate, traits_in_scope, name, None, callback)
 }
 
-fn iterate_trait_method_candidates<T>(
+fn iterate_trait_method_candidates(
     self_ty: &Canonical<Ty>,
     db: &dyn HirDatabase,
     env: Arc<TraitEnvironment>,
@@ -402,8 +469,8 @@ fn iterate_trait_method_candidates<T>(
     traits_in_scope: &FxHashSet<TraitId>,
     name: Option<&Name>,
     receiver_ty: Option<&Canonical<Ty>>,
-    mut callback: impl FnMut(&Ty, AssocItemId) -> Option<T>,
-) -> Option<T> {
+    callback: &mut dyn FnMut(&Ty, AssocItemId) -> bool,
+) -> bool {
     // if ty is `dyn Trait`, the trait doesn't need to be in scope
     let inherent_trait =
         self_ty.value.dyn_trait().into_iter().flat_map(|t| all_super_traits(db.upcast(), t));
@@ -436,23 +503,27 @@ fn iterate_trait_method_candidates<T>(
                 }
             }
             known_implemented = true;
-            if let Some(result) = callback(&self_ty.value, *item) {
-                return Some(result);
+            if callback(&self_ty.value, *item) {
+                return true;
             }
         }
     }
-    None
+    false
 }
 
-fn iterate_inherent_methods<T>(
+fn iterate_inherent_methods(
     self_ty: &Canonical<Ty>,
     db: &dyn HirDatabase,
     name: Option<&Name>,
     receiver_ty: Option<&Canonical<Ty>>,
     krate: CrateId,
-    mut callback: impl FnMut(&Ty, AssocItemId) -> Option<T>,
-) -> Option<T> {
-    for krate in self_ty.value.def_crates(db, krate)? {
+    callback: &mut dyn FnMut(&Ty, AssocItemId) -> bool,
+) -> bool {
+    let def_crates = match self_ty.value.def_crates(db, krate) {
+        Some(k) => k,
+        None => return false,
+    };
+    for krate in def_crates {
         let impls = db.impls_in_crate(krate);
 
         for impl_def in impls.lookup_impl_defs(&self_ty.value) {
@@ -468,13 +539,13 @@ fn iterate_inherent_methods<T>(
                     test_utils::mark::hit!(impl_self_type_match_without_receiver);
                     continue;
                 }
-                if let Some(result) = callback(&self_ty.value, item) {
-                    return Some(result);
+                if callback(&self_ty.value, item) {
+                    return true;
                 }
             }
         }
     }
-    None
+    false
 }
 
 /// Returns the self type for the index trait call.