4 files changed, 77 insertions, 34 deletions

diff --git a/crates/ra_hir_def/src/db.rs b/crates/ra_hir_def/src/db.rs
index da273eb11..0c00627b5 100644
--- a/crates/ra_hir_def/src/db.rs
+++ b/crates/ra_hir_def/src/db.rs
@@ -107,6 +107,13 @@ pub trait DefDatabase: InternDatabase + AstDatabase {
     // Remove this query completely, in favor of `Attrs::docs` method
     #[salsa::invoke(Documentation::documentation_query)]
     fn documentation(&self, def: AttrDefId) -> Option<Documentation>;
+
+    #[salsa::invoke(crate::find_path::importable_locations_in_crate_query)]
+    fn importable_locations_in_crate(
+        &self,
+        item: crate::item_scope::ItemInNs,
+        krate: CrateId,
+    ) -> Arc<[(ModuleId, hir_expand::name::Name, crate::visibility::Visibility)]>;
 }
 
 fn crate_def_map(db: &impl DefDatabase, krate: CrateId) -> Arc<CrateDefMap> {
diff --git a/crates/ra_hir_def/src/find_path.rs b/crates/ra_hir_def/src/find_path.rs
index be34ee662..09f3bf87d 100644
--- a/crates/ra_hir_def/src/find_path.rs
+++ b/crates/ra_hir_def/src/find_path.rs
@@ -4,12 +4,11 @@ use crate::{
     db::DefDatabase,
     item_scope::ItemInNs,
     path::{ModPath, PathKind},
-    ModuleId, ModuleDefId,
+    visibility::Visibility,
+    CrateId, ModuleDefId, ModuleId,
 };
 use hir_expand::name::Name;
 
-// TODO performance / memoize
-
 pub fn find_path(db: &impl DefDatabase, item: ItemInNs, from: ModuleId) -> Option<ModPath> {
     // Base cases:
 
@@ -21,13 +20,23 @@ pub fn find_path(db: &impl DefDatabase, item: ItemInNs, from: ModuleId) -> Optio
     }
 
     // - if the item is the crate root, return `crate`
-    if item == ItemInNs::Types(ModuleDefId::ModuleId(ModuleId { krate: from.krate, local_id: def_map.root })) {
+    if item
+        == ItemInNs::Types(ModuleDefId::ModuleId(ModuleId {
+            krate: from.krate,
+            local_id: def_map.root,
+        }))
+    {
         return Some(ModPath::from_simple_segments(PathKind::Crate, Vec::new()));
     }
 
     // - if the item is the parent module, use `super` (this is not used recursively, since `super::super` is ugly)
     if let Some(parent_id) = def_map.modules[from.local_id].parent {
-        if item == ItemInNs::Types(ModuleDefId::ModuleId(ModuleId { krate: from.krate, local_id: parent_id })) {
+        if item
+            == ItemInNs::Types(ModuleDefId::ModuleId(ModuleId {
+                krate: from.krate,
+                local_id: parent_id,
+            }))
+        {
             return Some(ModPath::from_simple_segments(PathKind::Super(1), Vec::new()));
         }
     }
@@ -42,7 +51,8 @@ pub fn find_path(db: &impl DefDatabase, item: ItemInNs, from: ModuleId) -> Optio
     // - if the item is in the prelude, return the name from there
     if let Some(prelude_module) = def_map.prelude {
         let prelude_def_map = db.crate_def_map(prelude_module.krate);
-        let prelude_scope: &crate::item_scope::ItemScope = &prelude_def_map.modules[prelude_module.local_id].scope;
+        let prelude_scope: &crate::item_scope::ItemScope =
+            &prelude_def_map.modules[prelude_module.local_id].scope;
         if let Some((name, vis)) = prelude_scope.reverse_get(item) {
             if vis.is_visible_from(db, from) {
                 return Some(ModPath::from_simple_segments(PathKind::Plain, vec![name.clone()]));
@@ -68,7 +78,8 @@ pub fn find_path(db: &impl DefDatabase, item: ItemInNs, from: ModuleId) -> Optio
     let mut candidate_paths = Vec::new();
     for (module_id, name) in importable_locations {
         // TODO prevent infinite loops
-        let mut path = match find_path(db, ItemInNs::Types(ModuleDefId::ModuleId(module_id)), from) {
+        let mut path = match find_path(db, ItemInNs::Types(ModuleDefId::ModuleId(module_id)), from)
+        {
             None => continue,
             Some(path) => path,
         };
@@ -78,33 +89,58 @@ pub fn find_path(db: &impl DefDatabase, item: ItemInNs, from: ModuleId) -> Optio
     candidate_paths.into_iter().min_by_key(|path| path.segments.len())
 }
 
-fn find_importable_locations(db: &impl DefDatabase, item: ItemInNs, from: ModuleId) -> Vec<(ModuleId, Name)> {
+fn find_importable_locations(
+    db: &impl DefDatabase,
+    item: ItemInNs,
+    from: ModuleId,
+) -> Vec<(ModuleId, Name)> {
     let crate_graph = db.crate_graph();
     let mut result = Vec::new();
-    for krate in Some(from.krate).into_iter().chain(crate_graph.dependencies(from.krate).map(|dep| dep.crate_id)) {
-        let def_map = db.crate_def_map(krate);
-        for (local_id, data) in def_map.modules.iter() {
-            if let Some((name, vis)) = data.scope.reverse_get(item) {
-                let is_private = if let crate::visibility::Visibility::Module(private_to) = vis {
-                    private_to.local_id == local_id
-                } else { false };
-                let is_original_def = if let Some(module_def_id) = item.as_module_def_id() {
-                    data.scope.declarations().any(|it| it == module_def_id)
-                } else { false };
-                if is_private && !is_original_def {
-                    // Ignore private imports. these could be used if we are
-                    // in a submodule of this module, but that's usually not
-                    // what the user wants; and if this module can import
-                    // the item and we're a submodule of it, so can we.
-                    continue;
-                }
-                if vis.is_visible_from(db, from) {
-                    result.push((ModuleId { krate, local_id }, name.clone()));
-                }
+    for krate in Some(from.krate)
+        .into_iter()
+        .chain(crate_graph.dependencies(from.krate).map(|dep| dep.crate_id))
+    {
+        result.extend(
+            db.importable_locations_in_crate(item, krate)
+                .iter()
+                .filter(|(_, _, vis)| vis.is_visible_from(db, from))
+                .map(|(m, n, _)| (*m, n.clone())),
+        );
+    }
+    result
+}
+
+pub(crate) fn importable_locations_in_crate_query(
+    db: &impl DefDatabase,
+    item: ItemInNs,
+    krate: CrateId,
+) -> std::sync::Arc<[(ModuleId, Name, Visibility)]> {
+    let def_map = db.crate_def_map(krate);
+    let mut result = Vec::new();
+    for (local_id, data) in def_map.modules.iter() {
+        if let Some((name, vis)) = data.scope.reverse_get(item) {
+            let is_private = if let Visibility::Module(private_to) = vis {
+                private_to.local_id == local_id
+            } else {
+                false
+            };
+            let is_original_def = if let Some(module_def_id) = item.as_module_def_id() {
+                data.scope.declarations().any(|it| it == module_def_id)
+            } else {
+                false
+            };
+            if is_private && !is_original_def {
+                // Ignore private imports. these could be used if we are
+                // in a submodule of this module, but that's usually not
+                // what the user wants; and if this module can import
+                // the item and we're a submodule of it, so can we.
+                // Also this keeps the cached data smaller.
+                continue;
             }
+            result.push((ModuleId { krate, local_id }, name.clone(), vis));
         }
     }
-    result
+    result.into()
 }
 
 #[cfg(test)]
diff --git a/crates/ra_hir_def/src/item_scope.rs b/crates/ra_hir_def/src/item_scope.rs
index 71afdb235..87c50b34f 100644
--- a/crates/ra_hir_def/src/item_scope.rs
+++ b/crates/ra_hir_def/src/item_scope.rs
@@ -183,7 +183,7 @@ impl PerNs {
     }
 }
 
-#[derive(Clone, Copy, PartialEq, Eq)]
+#[derive(Clone, Copy, PartialEq, Eq, Debug, Hash)]
 pub enum ItemInNs {
     Types(ModuleDefId),
     Values(ModuleDefId),
@@ -195,13 +195,13 @@ impl ItemInNs {
         match self {
             ItemInNs::Types(def) => {
                 per_ns.types.filter(|(other_def, _)| *other_def == def).map(|(_, vis)| vis)
-            },
+            }
             ItemInNs::Values(def) => {
                 per_ns.values.filter(|(other_def, _)| *other_def == def).map(|(_, vis)| vis)
-            },
+            }
             ItemInNs::Macros(def) => {
                 per_ns.macros.filter(|(other_def, _)| *other_def == def).map(|(_, vis)| vis)
-            },
+            }
         }
     }
 
diff --git a/crates/ra_hir_def/src/test_db.rs b/crates/ra_hir_def/src/test_db.rs
index a403f183f..1568820e9 100644
--- a/crates/ra_hir_def/src/test_db.rs
+++ b/crates/ra_hir_def/src/test_db.rs
@@ -5,8 +5,8 @@ use std::{
     sync::{Arc, Mutex},
 };
 
-use ra_db::{salsa, CrateId, FileId, FileLoader, FileLoaderDelegate, RelativePath};
 use crate::db::DefDatabase;
+use ra_db::{salsa, CrateId, FileId, FileLoader, FileLoaderDelegate, RelativePath};
 
 #[salsa::database(
     ra_db::SourceDatabaseExtStorage,