From d08c63cb9e3574fa97374a8529136814530bf416 Mon Sep 17 00:00:00 2001
From: Jonas Schievink <jonasschievink@gmail.com>
Date: Wed, 20 May 2020 23:51:20 +0200
Subject: Add an ImportMap

---
 crates/ra_hir_def/src/db.rs         |   4 +
 crates/ra_hir_def/src/find_path.rs  |  19 +--
 crates/ra_hir_def/src/import_map.rs | 323 ++++++++++++++++++++++++++++++++++++
 crates/ra_hir_def/src/lib.rs        |   1 +
 crates/ra_hir_def/src/path.rs       |  13 ++
 crates/ra_hir_def/src/per_ns.rs     |  10 +-
 6 files changed, 358 insertions(+), 12 deletions(-)
 create mode 100644 crates/ra_hir_def/src/import_map.rs

(limited to 'crates/ra_hir_def/src')

diff --git a/crates/ra_hir_def/src/db.rs b/crates/ra_hir_def/src/db.rs
index 945a0025e..a23d65371 100644
--- a/crates/ra_hir_def/src/db.rs
+++ b/crates/ra_hir_def/src/db.rs
@@ -14,6 +14,7 @@ use crate::{
     docs::Documentation,
     find_path,
     generics::GenericParams,
+    import_map::ImportMap,
     item_scope::ItemInNs,
     lang_item::{LangItemTarget, LangItems},
     nameres::{raw::RawItems, CrateDefMap},
@@ -122,6 +123,9 @@ pub trait DefDatabase: InternDatabase + AstDatabase + Upcast<dyn AstDatabase> {
 
     #[salsa::invoke(find_path::find_path_inner_query)]
     fn find_path_inner(&self, item: ItemInNs, from: ModuleId, max_len: usize) -> Option<ModPath>;
+
+    #[salsa::invoke(ImportMap::import_map_query)]
+    fn import_map(&self, krate: CrateId) -> Arc<ImportMap>;
 }
 
 fn crate_def_map_wait(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 4db798473..088e8dd32 100644
--- a/crates/ra_hir_def/src/find_path.rs
+++ b/crates/ra_hir_def/src/find_path.rs
@@ -36,17 +36,6 @@ impl ModPath {
         let first_segment = self.segments.first();
         first_segment == Some(&known::alloc) || first_segment == Some(&known::core)
     }
-
-    fn len(&self) -> usize {
-        self.segments.len()
-            + match self.kind {
-                PathKind::Plain => 0,
-                PathKind::Super(i) => i as usize,
-                PathKind::Crate => 1,
-                PathKind::Abs => 0,
-                PathKind::DollarCrate(_) => 1,
-            }
-    }
 }
 
 pub(crate) fn find_path_inner_query(
@@ -192,9 +181,17 @@ fn find_importable_locations(
 ) -> Vec<(ModuleId, Name)> {
     let crate_graph = db.crate_graph();
     let mut result = Vec::new();
+
     // We only look in the crate from which we are importing, and the direct
     // dependencies. We cannot refer to names from transitive dependencies
     // directly (only through reexports in direct dependencies).
+
+    // For the crate from which we're importing, we have to check whether any
+    // module visible to `from` exports the item we're looking for.
+    // For dependencies of the crate only `pub` items reachable through `pub`
+    // modules from the crate root are relevant. For that we precompute an
+    // import map that tells us the shortest path to any importable item with a
+    // single lookup.
     for krate in Some(from.krate)
         .into_iter()
         .chain(crate_graph[from.krate].dependencies.iter().map(|dep| dep.crate_id))
diff --git a/crates/ra_hir_def/src/import_map.rs b/crates/ra_hir_def/src/import_map.rs
new file mode 100644
index 000000000..7dae64efa
--- /dev/null
+++ b/crates/ra_hir_def/src/import_map.rs
@@ -0,0 +1,323 @@
+//! A map of all publicly exported items in a crate.
+
+use crate::{
+    db::DefDatabase,
+    item_scope::ItemInNs,
+    path::{ModPath, PathKind},
+    visibility::Visibility,
+    ModuleDefId, ModuleId,
+};
+use ra_db::CrateId;
+use rustc_hash::FxHashMap;
+use std::{collections::hash_map::Entry, sync::Arc};
+
+/// A map from publicly exported items to the path needed to import/name them from a downstream
+/// crate.
+///
+/// Reexports of items are taken into account, ie. if something is exported under multiple
+/// names, the one with the shortest import path will be used.
+///
+/// Note that all paths are relative to the containing crate's root, so the crate name still needs
+/// to be prepended to the `ModPath` before the path is valid.
+#[derive(Debug, Eq, PartialEq)]
+pub struct ImportMap {
+    map: FxHashMap<ItemInNs, ModPath>,
+}
+
+impl ImportMap {
+    pub fn import_map_query(db: &dyn DefDatabase, krate: CrateId) -> Arc<Self> {
+        let _p = ra_prof::profile("import_map_query");
+        let def_map = db.crate_def_map(krate);
+        let mut import_map = FxHashMap::with_capacity_and_hasher(64, Default::default());
+
+        // We look only into modules that are public(ly reexported), starting with the crate root.
+        let empty = ModPath { kind: PathKind::Plain, segments: vec![] };
+        let root = ModuleId { krate, local_id: def_map.root };
+        let mut worklist = vec![(root, empty)];
+        while let Some((module, mod_path)) = worklist.pop() {
+            let ext_def_map;
+            let mod_data = if module.krate == krate {
+                &def_map[module.local_id]
+            } else {
+                // The crate might reexport a module defined in another crate.
+                ext_def_map = db.crate_def_map(module.krate);
+                &ext_def_map[module.local_id]
+            };
+
+            let visible_items = mod_data.scope.entries().filter_map(|(name, per_ns)| {
+                let per_ns = per_ns.filter_visibility(|vis| vis == Visibility::Public);
+                if per_ns.is_none() {
+                    None
+                } else {
+                    Some((name, per_ns))
+                }
+            });
+
+            for (name, per_ns) in visible_items {
+                let mk_path = || {
+                    let mut path = mod_path.clone();
+                    path.segments.push(name.clone());
+                    path
+                };
+
+                for item in per_ns.iter_items() {
+                    let path = mk_path();
+                    match import_map.entry(item) {
+                        Entry::Vacant(entry) => {
+                            entry.insert(path);
+                        }
+                        Entry::Occupied(mut entry) => {
+                            // If the new path is shorter, prefer that one.
+                            if path.len() < entry.get().len() {
+                                *entry.get_mut() = path;
+                            } else {
+                                continue;
+                            }
+                        }
+                    }
+
+                    // If we've just added a path to a module, descend into it.
+                    if let Some(ModuleDefId::ModuleId(mod_id)) = item.as_module_def_id() {
+                        worklist.push((mod_id, mk_path()));
+                    }
+                }
+            }
+        }
+
+        Arc::new(Self { map: import_map })
+    }
+
+    /// Returns the `ModPath` needed to import/mention `item`, relative to this crate's root.
+    pub fn path_of(&self, item: ItemInNs) -> Option<&ModPath> {
+        self.map.get(&item)
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+    use crate::test_db::TestDB;
+    use insta::assert_snapshot;
+    use ra_db::fixture::WithFixture;
+    use ra_db::SourceDatabase;
+
+    fn import_map(ra_fixture: &str) -> String {
+        let db = TestDB::with_files(ra_fixture);
+        let crate_graph = db.crate_graph();
+
+        let import_maps: Vec<_> = crate_graph
+            .iter()
+            .filter_map(|krate| {
+                let cdata = &crate_graph[krate];
+                let name = cdata.display_name.as_ref()?;
+
+                let map = db.import_map(krate);
+
+                let mut importable_paths: Vec<_> = map
+                    .map
+                    .iter()
+                    .map(|(item, modpath)| {
+                        let ns = match item {
+                            ItemInNs::Types(_) => "t",
+                            ItemInNs::Values(_) => "v",
+                            ItemInNs::Macros(_) => "m",
+                        };
+                        format!("- {} ({})", modpath, ns)
+                    })
+                    .collect();
+
+                importable_paths.sort();
+                let importable_paths = importable_paths.join("\n");
+
+                Some(format!("{}:\n{}", name, importable_paths))
+            })
+            .collect();
+
+        import_maps.join("\n")
+    }
+
+    #[test]
+    fn smoke() {
+        let map = import_map(
+            r"
+            //- /main.rs crate:main deps:lib
+
+            mod private {
+                pub use lib::Pub;
+                pub struct InPrivateModule;
+            }
+
+            pub mod publ1 {
+                use lib::Pub;
+            }
+
+            pub mod real_pub {
+                pub use lib::Pub;
+            }
+            pub mod real_pu2 { // same path length as above
+                pub use lib::Pub;
+            }
+
+            //- /lib.rs crate:lib
+            pub struct Pub {}
+            pub struct Pub2; // t + v
+            struct Priv;
+        ",
+        );
+
+        assert_snapshot!(map, @r###"
+        main:
+        - publ1 (t)
+        - real_pu2 (t)
+        - real_pub (t)
+        - real_pub::Pub (t)
+        lib:
+        - Pub (t)
+        - Pub2 (t)
+        - Pub2 (v)
+        "###);
+    }
+
+    #[test]
+    fn prefers_shortest_path() {
+        let map = import_map(
+            r"
+            //- /main.rs crate:main
+
+            pub mod sub {
+                pub mod subsub {
+                    pub struct Def {}
+                }
+
+                pub use super::sub::subsub::Def;
+            }
+        ",
+        );
+
+        assert_snapshot!(map, @r###"
+        main:
+        - sub (t)
+        - sub::Def (t)
+        - sub::subsub (t)
+        "###);
+    }
+
+    #[test]
+    fn type_reexport_cross_crate() {
+        // Reexports need to be visible from a crate, even if the original crate exports the item
+        // at a shorter path.
+        let map = import_map(
+            r"
+            //- /main.rs crate:main deps:lib
+            pub mod m {
+                pub use lib::S;
+            }
+            //- /lib.rs crate:lib
+            pub struct S;
+        ",
+        );
+
+        assert_snapshot!(map, @r###"
+        main:
+        - m (t)
+        - m::S (t)
+        - m::S (v)
+        lib:
+        - S (t)
+        - S (v)
+        "###);
+    }
+
+    #[test]
+    fn macro_reexport() {
+        let map = import_map(
+            r"
+            //- /main.rs crate:main deps:lib
+            pub mod m {
+                pub use lib::pub_macro;
+            }
+            //- /lib.rs crate:lib
+            #[macro_export]
+            macro_rules! pub_macro {
+                () => {};
+            }
+        ",
+        );
+
+        assert_snapshot!(map, @r###"
+        main:
+        - m (t)
+        - m::pub_macro (m)
+        lib:
+        - pub_macro (m)
+        "###);
+    }
+
+    #[test]
+    fn module_reexport() {
+        // Reexporting modules from a dependency adds all contents to the import map.
+        let map = import_map(
+            r"
+            //- /main.rs crate:main deps:lib
+            pub use lib::module as reexported_module;
+            //- /lib.rs crate:lib
+            pub mod module {
+                pub struct S;
+            }
+        ",
+        );
+
+        assert_snapshot!(map, @r###"
+        main:
+        - reexported_module (t)
+        - reexported_module::S (t)
+        - reexported_module::S (v)
+        lib:
+        - module (t)
+        - module::S (t)
+        - module::S (v)
+        "###);
+    }
+
+    #[test]
+    fn cyclic_module_reexport() {
+        // Reexporting modules from a dependency adds all contents to the import map.
+        let map = import_map(
+            r"
+            //- /lib.rs crate:lib
+            pub mod module {
+                pub struct S;
+                pub use super::sub::*;
+            }
+
+            pub mod sub {
+                pub use super::module;
+            }
+        ",
+        );
+
+        assert_snapshot!(map, @r###"
+        lib:
+        - module (t)
+        - module::S (t)
+        - module::S (v)
+        - sub (t)
+        "###);
+    }
+
+    #[test]
+    fn private_macro() {
+        let map = import_map(
+            r"
+            //- /lib.rs crate:lib
+            macro_rules! private_macro {
+                () => {};
+            }
+        ",
+        );
+
+        assert_snapshot!(map, @r###"
+        lib:
+        "###);
+    }
+}
diff --git a/crates/ra_hir_def/src/lib.rs b/crates/ra_hir_def/src/lib.rs
index 5325a2760..de490fcc5 100644
--- a/crates/ra_hir_def/src/lib.rs
+++ b/crates/ra_hir_def/src/lib.rs
@@ -43,6 +43,7 @@ pub mod child_by_source;
 
 pub mod visibility;
 pub mod find_path;
+pub mod import_map;
 
 #[cfg(test)]
 mod test_db;
diff --git a/crates/ra_hir_def/src/path.rs b/crates/ra_hir_def/src/path.rs
index 4512448e0..bfa921de2 100644
--- a/crates/ra_hir_def/src/path.rs
+++ b/crates/ra_hir_def/src/path.rs
@@ -76,6 +76,19 @@ impl ModPath {
         }
     }
 
+    /// Returns the number of segments in the path (counting special segments like `$crate` and
+    /// `super`).
+    pub fn len(&self) -> usize {
+        self.segments.len()
+            + match self.kind {
+                PathKind::Plain => 0,
+                PathKind::Super(i) => i as usize,
+                PathKind::Crate => 1,
+                PathKind::Abs => 0,
+                PathKind::DollarCrate(_) => 1,
+            }
+    }
+
     pub fn is_ident(&self) -> bool {
         self.kind == PathKind::Plain && self.segments.len() == 1
     }
diff --git a/crates/ra_hir_def/src/per_ns.rs b/crates/ra_hir_def/src/per_ns.rs
index 6e435c8c1..74665c588 100644
--- a/crates/ra_hir_def/src/per_ns.rs
+++ b/crates/ra_hir_def/src/per_ns.rs
@@ -5,7 +5,7 @@
 
 use hir_expand::MacroDefId;
 
-use crate::{visibility::Visibility, ModuleDefId};
+use crate::{item_scope::ItemInNs, visibility::Visibility, ModuleDefId};
 
 #[derive(Debug, Copy, Clone, PartialEq, Eq)]
 pub struct PerNs {
@@ -84,4 +84,12 @@ impl PerNs {
             macros: self.macros.or(other.macros),
         }
     }
+
+    pub fn iter_items(self) -> impl Iterator<Item = ItemInNs> {
+        self.types
+            .map(|it| ItemInNs::Types(it.0))
+            .into_iter()
+            .chain(self.values.map(|it| ItemInNs::Values(it.0)).into_iter())
+            .chain(self.macros.map(|it| ItemInNs::Macros(it.0)).into_iter())
+    }
 }
-- 
cgit v1.2.3


From 3c496f7fa7afe78102ea2c7ee5f7e006a66629d4 Mon Sep 17 00:00:00 2001
From: Jonas Schievink <jonasschievink@gmail.com>
Date: Thu, 4 Jun 2020 19:30:29 +0200
Subject: Use `ImportMap` in `find_path`, remove old queries

---
 crates/ra_hir_def/src/db.rs         |  16 +--
 crates/ra_hir_def/src/find_path.rs  | 199 +++++++++++++++++++++---------------
 crates/ra_hir_def/src/item_scope.rs |  22 +++-
 3 files changed, 140 insertions(+), 97 deletions(-)

(limited to 'crates/ra_hir_def/src')

diff --git a/crates/ra_hir_def/src/db.rs b/crates/ra_hir_def/src/db.rs
index a23d65371..10cc26480 100644
--- a/crates/ra_hir_def/src/db.rs
+++ b/crates/ra_hir_def/src/db.rs
@@ -1,7 +1,7 @@
 //! Defines database & queries for name resolution.
 use std::sync::Arc;
 
-use hir_expand::{db::AstDatabase, name::Name, HirFileId};
+use hir_expand::{db::AstDatabase, HirFileId};
 use ra_db::{salsa, CrateId, SourceDatabase, Upcast};
 use ra_prof::profile;
 use ra_syntax::SmolStr;
@@ -12,14 +12,10 @@ use crate::{
     body::{scope::ExprScopes, Body, BodySourceMap},
     data::{ConstData, FunctionData, ImplData, StaticData, TraitData, TypeAliasData},
     docs::Documentation,
-    find_path,
     generics::GenericParams,
     import_map::ImportMap,
-    item_scope::ItemInNs,
     lang_item::{LangItemTarget, LangItems},
     nameres::{raw::RawItems, CrateDefMap},
-    path::ModPath,
-    visibility::Visibility,
     AttrDefId, ConstId, ConstLoc, DefWithBodyId, EnumId, EnumLoc, FunctionId, FunctionLoc,
     GenericDefId, ImplId, ImplLoc, ModuleId, StaticId, StaticLoc, StructId, StructLoc, TraitId,
     TraitLoc, TypeAliasId, TypeAliasLoc, UnionId, UnionLoc,
@@ -114,16 +110,6 @@ pub trait DefDatabase: InternDatabase + AstDatabase + Upcast<dyn AstDatabase> {
     #[salsa::invoke(Documentation::documentation_query)]
     fn documentation(&self, def: AttrDefId) -> Option<Documentation>;
 
-    #[salsa::invoke(find_path::importable_locations_of_query)]
-    fn importable_locations_of(
-        &self,
-        item: ItemInNs,
-        krate: CrateId,
-    ) -> Arc<[(ModuleId, Name, Visibility)]>;
-
-    #[salsa::invoke(find_path::find_path_inner_query)]
-    fn find_path_inner(&self, item: ItemInNs, from: ModuleId, max_len: usize) -> Option<ModPath>;
-
     #[salsa::invoke(ImportMap::import_map_query)]
     fn import_map(&self, krate: CrateId) -> Arc<ImportMap>;
 }
diff --git a/crates/ra_hir_def/src/find_path.rs b/crates/ra_hir_def/src/find_path.rs
index 088e8dd32..79f4afab6 100644
--- a/crates/ra_hir_def/src/find_path.rs
+++ b/crates/ra_hir_def/src/find_path.rs
@@ -1,7 +1,5 @@
 //! An algorithm to find a path to refer to a certain item.
 
-use std::sync::Arc;
-
 use hir_expand::name::{known, AsName, Name};
 use ra_prof::profile;
 use test_utils::mark;
@@ -11,8 +9,9 @@ use crate::{
     item_scope::ItemInNs,
     path::{ModPath, PathKind},
     visibility::Visibility,
-    CrateId, ModuleDefId, ModuleId,
+    ModuleDefId, ModuleId,
 };
+use rustc_hash::FxHashSet;
 
 // FIXME: handle local items
 
@@ -20,7 +19,7 @@ use crate::{
 /// *from where* you're referring to the item, hence the `from` parameter.
 pub fn find_path(db: &dyn DefDatabase, item: ItemInNs, from: ModuleId) -> Option<ModPath> {
     let _p = profile("find_path");
-    db.find_path_inner(item, from, MAX_PATH_LEN)
+    find_path_inner(db, item, from, MAX_PATH_LEN)
 }
 
 const MAX_PATH_LEN: usize = 15;
@@ -38,7 +37,7 @@ impl ModPath {
     }
 }
 
-pub(crate) fn find_path_inner_query(
+pub(crate) fn find_path_inner(
     db: &dyn DefDatabase,
     item: ItemInNs,
     from: ModuleId,
@@ -122,31 +121,61 @@ pub(crate) fn find_path_inner_query(
     }
 
     // - otherwise, look for modules containing (reexporting) it and import it from one of those
+
     let crate_root = ModuleId { local_id: def_map.root, krate: from.krate };
     let crate_attrs = db.attrs(crate_root.into());
     let prefer_no_std = crate_attrs.by_key("no_std").exists();
-    let importable_locations = find_importable_locations(db, item, from);
     let mut best_path = None;
     let mut best_path_len = max_len;
-    for (module_id, name) in importable_locations {
-        let mut path = match db.find_path_inner(
-            ItemInNs::Types(ModuleDefId::ModuleId(module_id)),
-            from,
-            best_path_len - 1,
-        ) {
-            None => continue,
-            Some(path) => path,
-        };
-        path.segments.push(name);
 
-        let new_path = if let Some(best_path) = best_path {
-            select_best_path(best_path, path, prefer_no_std)
-        } else {
-            path
-        };
-        best_path_len = new_path.len();
-        best_path = Some(new_path);
+    if item.defining_crate(db) == Some(from.krate) {
+        // Item was defined in the same crate that wants to import it. It cannot be found in any
+        // dependency in this case.
+
+        let local_imports = find_local_import_locations(db, item, from);
+        for (module_id, name) in local_imports {
+            if let Some(mut path) = find_path_inner(
+                db,
+                ItemInNs::Types(ModuleDefId::ModuleId(module_id)),
+                from,
+                best_path_len - 1,
+            ) {
+                path.segments.push(name);
+
+                let new_path = if let Some(best_path) = best_path {
+                    select_best_path(best_path, path, prefer_no_std)
+                } else {
+                    path
+                };
+                best_path_len = new_path.len();
+                best_path = Some(new_path);
+            }
+        }
+    } else {
+        // Item was defined in some upstream crate. This means that it must be exported from one,
+        // too (unless we can't name it at all). It could *also* be (re)exported by the same crate
+        // that wants to import it here, but we always prefer to use the external path here.
+
+        let crate_graph = db.crate_graph();
+        let extern_paths = crate_graph[from.krate].dependencies.iter().filter_map(|dep| {
+            let import_map = db.import_map(dep.crate_id);
+            import_map.path_of(item).map(|modpath| {
+                let mut modpath = modpath.clone();
+                modpath.segments.insert(0, dep.as_name());
+                modpath
+            })
+        });
+
+        for path in extern_paths {
+            let new_path = if let Some(best_path) = best_path {
+                select_best_path(best_path, path, prefer_no_std)
+            } else {
+                path
+            };
+            best_path = Some(new_path);
+        }
     }
+
     best_path
 }
 
@@ -174,77 +203,86 @@ fn select_best_path(old_path: ModPath, new_path: ModPath, prefer_no_std: bool) -
     }
 }
 
-fn find_importable_locations(
+/// Finds locations in `from.krate` from which `item` can be imported by `from`.
+fn find_local_import_locations(
     db: &dyn DefDatabase,
     item: ItemInNs,
     from: ModuleId,
 ) -> Vec<(ModuleId, Name)> {
-    let crate_graph = db.crate_graph();
-    let mut result = Vec::new();
-
-    // We only look in the crate from which we are importing, and the direct
-    // dependencies. We cannot refer to names from transitive dependencies
-    // directly (only through reexports in direct dependencies).
-
-    // For the crate from which we're importing, we have to check whether any
-    // module visible to `from` exports the item we're looking for.
-    // For dependencies of the crate only `pub` items reachable through `pub`
-    // modules from the crate root are relevant. For that we precompute an
-    // import map that tells us the shortest path to any importable item with a
-    // single lookup.
-    for krate in Some(from.krate)
-        .into_iter()
-        .chain(crate_graph[from.krate].dependencies.iter().map(|dep| dep.crate_id))
-    {
-        result.extend(
-            db.importable_locations_of(item, krate)
-                .iter()
-                .filter(|(_, _, vis)| vis.is_visible_from(db, from))
-                .map(|(m, n, _)| (*m, n.clone())),
-        );
-    }
-    result
-}
+    let _p = profile("find_local_import_locations");
+
+    // `from` can import anything below `from` with visibility of at least `from`, and anything
+    // above `from` with any visibility. That means we do not need to descend into private siblings
+    // of `from` (and similar).
+
+    let def_map = db.crate_def_map(from.krate);
+
+    // Compute the initial worklist. We start with all direct child modules of `from` as well as all
+    // of its (recursive) parent modules.
+    let data = &def_map.modules[from.local_id];
+    let mut worklist = data
+        .children
+        .values()
+        .map(|child| ModuleId { krate: from.krate, local_id: *child })
+        .collect::<Vec<_>>();
+    let mut parent = data.parent;
+    while let Some(p) = parent {
+        worklist.push(ModuleId { krate: from.krate, local_id: p });
+        parent = def_map.modules[p].parent;
+    }
+
+    let mut seen: FxHashSet<_> = FxHashSet::default();
+
+    let mut locations = Vec::new();
+    while let Some(module) = worklist.pop() {
+        if !seen.insert(module) {
+            continue; // already processed this module
+        }
+
+        let ext_def_map;
+        let data = if module.krate == from.krate {
+            &def_map[module.local_id]
+        } else {
+            // The crate might reexport a module defined in another crate.
+            ext_def_map = db.crate_def_map(module.krate);
+            &ext_def_map[module.local_id]
+        };
 
-/// Collects all locations from which we might import the item in a particular
-/// crate. These include the original definition of the item, and any
-/// non-private `use`s.
-///
-/// Note that the crate doesn't need to be the one in which the item is defined;
-/// it might be re-exported in other crates.
-pub(crate) fn importable_locations_of_query(
-    db: &dyn DefDatabase,
-    item: ItemInNs,
-    krate: CrateId,
-) -> Arc<[(ModuleId, Name, Visibility)]> {
-    let _p = profile("importable_locations_of_query");
-    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.name_of(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 {
+            if vis.is_visible_from(db, from) {
+                let is_private = if let Visibility::Module(private_to) = vis {
+                    private_to.local_id == module.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
+                };
+
                 // 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;
+                if !is_private || is_original_def {
+                    locations.push((module, name.clone()));
+                }
+            }
+        }
+
+        // Descend into all modules visible from `from`.
+        for (_, per_ns) in data.scope.entries() {
+            if let Some((ModuleDefId::ModuleId(module), vis)) = per_ns.take_types_vis() {
+                if vis.is_visible_from(db, from) {
+                    worklist.push(module);
+                }
             }
-            result.push((ModuleId { krate, local_id }, name.clone(), vis));
         }
     }
 
-    Arc::from(result)
+    locations
 }
 
 #[cfg(test)]
@@ -382,6 +420,7 @@ mod tests {
 
     #[test]
     fn different_crate_renamed() {
+        // Even if a local path exists, if the item is defined externally, prefer an external path.
         let code = r#"
             //- /main.rs crate:main deps:std
             extern crate std as std_renamed;
@@ -389,7 +428,7 @@ mod tests {
             //- /std.rs crate:std
             pub struct S;
         "#;
-        check_found_path(code, "std_renamed::S");
+        check_found_path(code, "std::S");
     }
 
     #[test]
diff --git a/crates/ra_hir_def/src/item_scope.rs b/crates/ra_hir_def/src/item_scope.rs
index fc15948ad..ede1aa045 100644
--- a/crates/ra_hir_def/src/item_scope.rs
+++ b/crates/ra_hir_def/src/item_scope.rs
@@ -6,9 +6,10 @@ use once_cell::sync::Lazy;
 use rustc_hash::FxHashMap;
 
 use crate::{
-    per_ns::PerNs, visibility::Visibility, AdtId, BuiltinType, ImplId, MacroDefId, ModuleDefId,
-    TraitId,
+    db::DefDatabase, per_ns::PerNs, visibility::Visibility, AdtId, BuiltinType, HasModule, ImplId,
+    Lookup, MacroDefId, ModuleDefId, TraitId,
 };
+use ra_db::CrateId;
 
 #[derive(Debug, Default, PartialEq, Eq)]
 pub struct ItemScope {
@@ -203,4 +204,21 @@ impl ItemInNs {
             ItemInNs::Macros(_) => None,
         }
     }
+
+    pub fn defining_crate(&self, db: &dyn DefDatabase) -> Option<CrateId> {
+        Some(match self {
+            ItemInNs::Types(did) | ItemInNs::Values(did) => match did {
+                ModuleDefId::ModuleId(id) => id.krate,
+                ModuleDefId::FunctionId(id) => id.lookup(db).module(db).krate,
+                ModuleDefId::AdtId(id) => id.module(db).krate,
+                ModuleDefId::EnumVariantId(id) => id.parent.lookup(db).container.module(db).krate,
+                ModuleDefId::ConstId(id) => id.lookup(db).container.module(db).krate,
+                ModuleDefId::StaticId(id) => id.lookup(db).container.module(db).krate,
+                ModuleDefId::TraitId(id) => id.lookup(db).container.module(db).krate,
+                ModuleDefId::TypeAliasId(id) => id.lookup(db).module(db).krate,
+                ModuleDefId::BuiltinType(_) => return None,
+            },
+            ItemInNs::Macros(id) => return id.krate,
+        })
+    }
 }
-- 
cgit v1.2.3


From e0e9c6d1a4cfdd4410b802ad8db1e29c9f1b4291 Mon Sep 17 00:00:00 2001
From: Jonas Schievink <jonas.schievink@ferrous-systems.com>
Date: Fri, 5 Jun 2020 13:04:35 +0200
Subject: Fix wrong comment

---
 crates/ra_hir_def/src/import_map.rs | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

(limited to 'crates/ra_hir_def/src')

diff --git a/crates/ra_hir_def/src/import_map.rs b/crates/ra_hir_def/src/import_map.rs
index 7dae64efa..7c8c4b6cb 100644
--- a/crates/ra_hir_def/src/import_map.rs
+++ b/crates/ra_hir_def/src/import_map.rs
@@ -281,7 +281,7 @@ mod tests {
 
     #[test]
     fn cyclic_module_reexport() {
-        // Reexporting modules from a dependency adds all contents to the import map.
+        // A cyclic reexport does not hang.
         let map = import_map(
             r"
             //- /lib.rs crate:lib
-- 
cgit v1.2.3


From 86fbd8cc2b71f473b9e6d41f4fe3e1a114f1f992 Mon Sep 17 00:00:00 2001
From: Jonas Schievink <jonas.schievink@ferrous-systems.com>
Date: Fri, 5 Jun 2020 13:05:19 +0200
Subject: defining_crate -> krate

---
 crates/ra_hir_def/src/find_path.rs  | 2 +-
 crates/ra_hir_def/src/item_scope.rs | 3 ++-
 2 files changed, 3 insertions(+), 2 deletions(-)

(limited to 'crates/ra_hir_def/src')

diff --git a/crates/ra_hir_def/src/find_path.rs b/crates/ra_hir_def/src/find_path.rs
index 79f4afab6..e6cd89478 100644
--- a/crates/ra_hir_def/src/find_path.rs
+++ b/crates/ra_hir_def/src/find_path.rs
@@ -128,7 +128,7 @@ pub(crate) fn find_path_inner(
     let mut best_path = None;
     let mut best_path_len = max_len;
 
-    if item.defining_crate(db) == Some(from.krate) {
+    if item.krate(db) == Some(from.krate) {
         // Item was defined in the same crate that wants to import it. It cannot be found in any
         // dependency in this case.
 
diff --git a/crates/ra_hir_def/src/item_scope.rs b/crates/ra_hir_def/src/item_scope.rs
index ede1aa045..d340e1f13 100644
--- a/crates/ra_hir_def/src/item_scope.rs
+++ b/crates/ra_hir_def/src/item_scope.rs
@@ -205,7 +205,8 @@ impl ItemInNs {
         }
     }
 
-    pub fn defining_crate(&self, db: &dyn DefDatabase) -> Option<CrateId> {
+    /// Returns the crate defining this item (or `None` if `self` is built-in).
+    pub fn krate(&self, db: &dyn DefDatabase) -> Option<CrateId> {
         Some(match self {
             ItemInNs::Types(did) | ItemInNs::Values(did) => match did {
                 ModuleDefId::ModuleId(id) => id.krate,
-- 
cgit v1.2.3


From 5f23f8ca449e456087d0657f925837bfb1a3f5ec Mon Sep 17 00:00:00 2001
From: Jonas Schievink <jonas.schievink@ferrous-systems.com>
Date: Fri, 5 Jun 2020 13:11:53 +0200
Subject: Make `find_path_inner` private again

---
 crates/ra_hir_def/src/find_path.rs | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

(limited to 'crates/ra_hir_def/src')

diff --git a/crates/ra_hir_def/src/find_path.rs b/crates/ra_hir_def/src/find_path.rs
index e6cd89478..d6ae970dc 100644
--- a/crates/ra_hir_def/src/find_path.rs
+++ b/crates/ra_hir_def/src/find_path.rs
@@ -37,7 +37,7 @@ impl ModPath {
     }
 }
 
-pub(crate) fn find_path_inner(
+fn find_path_inner(
     db: &dyn DefDatabase,
     item: ItemInNs,
     from: ModuleId,
-- 
cgit v1.2.3


From 8395396782e343c6fe6bd318c74e8c9884b22323 Mon Sep 17 00:00:00 2001
From: Jonas Schievink <jonas.schievink@ferrous-systems.com>
Date: Fri, 5 Jun 2020 13:15:16 +0200
Subject: Reorder imports

---
 crates/ra_hir_def/src/find_path.rs  | 2 +-
 crates/ra_hir_def/src/import_map.rs | 8 +++++---
 crates/ra_hir_def/src/item_scope.rs | 2 +-
 3 files changed, 7 insertions(+), 5 deletions(-)

(limited to 'crates/ra_hir_def/src')

diff --git a/crates/ra_hir_def/src/find_path.rs b/crates/ra_hir_def/src/find_path.rs
index d6ae970dc..a7f59e028 100644
--- a/crates/ra_hir_def/src/find_path.rs
+++ b/crates/ra_hir_def/src/find_path.rs
@@ -2,6 +2,7 @@
 
 use hir_expand::name::{known, AsName, Name};
 use ra_prof::profile;
+use rustc_hash::FxHashSet;
 use test_utils::mark;
 
 use crate::{
@@ -11,7 +12,6 @@ use crate::{
     visibility::Visibility,
     ModuleDefId, ModuleId,
 };
-use rustc_hash::FxHashSet;
 
 // FIXME: handle local items
 
diff --git a/crates/ra_hir_def/src/import_map.rs b/crates/ra_hir_def/src/import_map.rs
index 7c8c4b6cb..1c812a19a 100644
--- a/crates/ra_hir_def/src/import_map.rs
+++ b/crates/ra_hir_def/src/import_map.rs
@@ -1,5 +1,10 @@
 //! A map of all publicly exported items in a crate.
 
+use std::{collections::hash_map::Entry, sync::Arc};
+
+use ra_db::CrateId;
+use rustc_hash::FxHashMap;
+
 use crate::{
     db::DefDatabase,
     item_scope::ItemInNs,
@@ -7,9 +12,6 @@ use crate::{
     visibility::Visibility,
     ModuleDefId, ModuleId,
 };
-use ra_db::CrateId;
-use rustc_hash::FxHashMap;
-use std::{collections::hash_map::Entry, sync::Arc};
 
 /// A map from publicly exported items to the path needed to import/name them from a downstream
 /// crate.
diff --git a/crates/ra_hir_def/src/item_scope.rs b/crates/ra_hir_def/src/item_scope.rs
index d340e1f13..b03ba939a 100644
--- a/crates/ra_hir_def/src/item_scope.rs
+++ b/crates/ra_hir_def/src/item_scope.rs
@@ -3,13 +3,13 @@
 
 use hir_expand::name::Name;
 use once_cell::sync::Lazy;
+use ra_db::CrateId;
 use rustc_hash::FxHashMap;
 
 use crate::{
     db::DefDatabase, per_ns::PerNs, visibility::Visibility, AdtId, BuiltinType, HasModule, ImplId,
     Lookup, MacroDefId, ModuleDefId, TraitId,
 };
-use ra_db::CrateId;
 
 #[derive(Debug, Default, PartialEq, Eq)]
 pub struct ItemScope {
-- 
cgit v1.2.3


From 2fb3d87bf77826f213d2876c921308e9f168ca63 Mon Sep 17 00:00:00 2001
From: Jonas Schievink <jonas.schievink@ferrous-systems.com>
Date: Fri, 5 Jun 2020 13:36:19 +0200
Subject: impl Debug for ImportMap

---
 crates/ra_hir_def/src/import_map.rs | 42 ++++++++++++++++++++-----------------
 1 file changed, 23 insertions(+), 19 deletions(-)

(limited to 'crates/ra_hir_def/src')

diff --git a/crates/ra_hir_def/src/import_map.rs b/crates/ra_hir_def/src/import_map.rs
index 1c812a19a..70749f380 100644
--- a/crates/ra_hir_def/src/import_map.rs
+++ b/crates/ra_hir_def/src/import_map.rs
@@ -1,6 +1,6 @@
 //! A map of all publicly exported items in a crate.
 
-use std::{collections::hash_map::Entry, sync::Arc};
+use std::{collections::hash_map::Entry, fmt, sync::Arc};
 
 use ra_db::CrateId;
 use rustc_hash::FxHashMap;
@@ -21,7 +21,7 @@ use crate::{
 ///
 /// Note that all paths are relative to the containing crate's root, so the crate name still needs
 /// to be prepended to the `ModPath` before the path is valid.
-#[derive(Debug, Eq, PartialEq)]
+#[derive(Eq, PartialEq)]
 pub struct ImportMap {
     map: FxHashMap<ItemInNs, ModPath>,
 }
@@ -95,6 +95,26 @@ impl ImportMap {
     }
 }
 
+impl fmt::Debug for ImportMap {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        let mut importable_paths: Vec<_> = self
+            .map
+            .iter()
+            .map(|(item, modpath)| {
+                let ns = match item {
+                    ItemInNs::Types(_) => "t",
+                    ItemInNs::Values(_) => "v",
+                    ItemInNs::Macros(_) => "m",
+                };
+                format!("- {} ({})", modpath, ns)
+            })
+            .collect();
+
+        importable_paths.sort();
+        f.write_str(&importable_paths.join("\n"))
+    }
+}
+
 #[cfg(test)]
 mod tests {
     use super::*;
@@ -115,23 +135,7 @@ mod tests {
 
                 let map = db.import_map(krate);
 
-                let mut importable_paths: Vec<_> = map
-                    .map
-                    .iter()
-                    .map(|(item, modpath)| {
-                        let ns = match item {
-                            ItemInNs::Types(_) => "t",
-                            ItemInNs::Values(_) => "v",
-                            ItemInNs::Macros(_) => "m",
-                        };
-                        format!("- {} ({})", modpath, ns)
-                    })
-                    .collect();
-
-                importable_paths.sort();
-                let importable_paths = importable_paths.join("\n");
-
-                Some(format!("{}:\n{}", name, importable_paths))
+                Some(format!("{}:\n{:?}", name, map))
             })
             .collect();
 
-- 
cgit v1.2.3


From bc2d1729957a25bf5ee8e2213d07460e22c76def Mon Sep 17 00:00:00 2001
From: Jonas Schievink <jonas.schievink@ferrous-systems.com>
Date: Fri, 5 Jun 2020 14:24:51 +0200
Subject: Clarify when we visit modules multiple times

---
 crates/ra_hir_def/src/import_map.rs | 4 +++-
 1 file changed, 3 insertions(+), 1 deletion(-)

(limited to 'crates/ra_hir_def/src')

diff --git a/crates/ra_hir_def/src/import_map.rs b/crates/ra_hir_def/src/import_map.rs
index 70749f380..4284a0a91 100644
--- a/crates/ra_hir_def/src/import_map.rs
+++ b/crates/ra_hir_def/src/import_map.rs
@@ -78,7 +78,9 @@ impl ImportMap {
                         }
                     }
 
-                    // If we've just added a path to a module, descend into it.
+                    // If we've just added a path to a module, descend into it. We might traverse
+                    // modules multiple times, but only if the new path to it is shorter than the
+                    // first (else we `continue` above).
                     if let Some(ModuleDefId::ModuleId(mod_id)) = item.as_module_def_id() {
                         worklist.push((mod_id, mk_path()));
                     }
-- 
cgit v1.2.3