From d08c63cb9e3574fa97374a8529136814530bf416 Mon Sep 17 00:00:00 2001 From: Jonas Schievink Date: Wed, 20 May 2020 23:51:20 +0200 Subject: Add an ImportMap --- crates/ra_hir_def/src/import_map.rs | 323 ++++++++++++++++++++++++++++++++++++ 1 file changed, 323 insertions(+) create mode 100644 crates/ra_hir_def/src/import_map.rs (limited to 'crates/ra_hir_def/src/import_map.rs') 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, +} + +impl ImportMap { + pub fn import_map_query(db: &dyn DefDatabase, krate: CrateId) -> Arc { + 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: + "###); + } +} -- cgit v1.2.3 From e0e9c6d1a4cfdd4410b802ad8db1e29c9f1b4291 Mon Sep 17 00:00:00 2001 From: Jonas Schievink 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/import_map.rs') 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 8395396782e343c6fe6bd318c74e8c9884b22323 Mon Sep 17 00:00:00 2001 From: Jonas Schievink Date: Fri, 5 Jun 2020 13:15:16 +0200 Subject: Reorder imports --- crates/ra_hir_def/src/import_map.rs | 8 +++++--- 1 file changed, 5 insertions(+), 3 deletions(-) (limited to 'crates/ra_hir_def/src/import_map.rs') 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. -- cgit v1.2.3 From 2fb3d87bf77826f213d2876c921308e9f168ca63 Mon Sep 17 00:00:00 2001 From: Jonas Schievink 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/import_map.rs') 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, } @@ -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 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/import_map.rs') 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