1 //! A map of all publicly exported items in a crate.
3 use std::{fmt, hash::BuildHasherDefault, sync::Arc};
6 use fst::{self, Streamer};
7 use hir_expand::name::Name;
8 use indexmap::{map::Entry, IndexMap};
9 use itertools::Itertools;
10 use rustc_hash::{FxHashSet, FxHasher};
13 db::DefDatabase, item_scope::ItemInNs, visibility::Visibility, AssocItemId, ModuleDefId,
17 type FxIndexMap<K, V> = IndexMap<K, V, BuildHasherDefault<FxHasher>>;
19 /// Item import details stored in the `ImportMap`.
20 #[derive(Debug, Clone, Eq, PartialEq)]
21 pub struct ImportInfo {
22 /// A path that can be used to import the item, relative to the crate's root.
24 /// The module containing this item.
25 pub container: ModuleId,
26 /// Whether the import is a trait associated item or not.
27 pub is_trait_assoc_item: bool,
30 #[derive(Debug, Clone, Eq, PartialEq)]
31 pub struct ImportPath {
32 pub segments: Vec<Name>,
35 impl fmt::Display for ImportPath {
36 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
37 fmt::Display::fmt(&self.segments.iter().format("::"), f)
42 fn len(&self) -> usize {
47 /// A map from publicly exported items to the path needed to import/name them from a downstream
50 /// Reexports of items are taken into account, ie. if something is exported under multiple
51 /// names, the one with the shortest import path will be used.
53 /// Note that all paths are relative to the containing crate's root, so the crate name still needs
54 /// to be prepended to the `ModPath` before the path is valid.
56 pub struct ImportMap {
57 map: FxIndexMap<ItemInNs, ImportInfo>,
59 /// List of keys stored in `map`, sorted lexicographically by their `ModPath`. Indexed by the
60 /// values returned by running `fst`.
62 /// Since a path can refer to multiple items due to namespacing, we store all items with the
63 /// same path right after each other. This allows us to find all items after the FST gives us
64 /// the index of the first one.
65 importables: Vec<ItemInNs>,
66 fst: fst::Map<Vec<u8>>,
70 pub fn import_map_query(db: &dyn DefDatabase, krate: CrateId) -> Arc<Self> {
71 let _p = profile::span("import_map_query");
73 let mut import_map = collect_import_map(db, krate);
75 let mut importables = import_map
78 .map(|(item, info)| (item, fst_path(&info.path)))
80 importables.sort_by(|(_, fst_path), (_, fst_path2)| fst_path.cmp(fst_path2));
82 // Build the FST, taking care not to insert duplicate values.
84 let mut builder = fst::MapBuilder::memory();
85 let mut last_batch_start = 0;
87 for idx in 0..importables.len() {
88 let key = &importables[last_batch_start].1;
89 if let Some((_, fst_path)) = importables.get(idx + 1) {
95 let _ = builder.insert(key, last_batch_start as u64);
97 last_batch_start = idx + 1;
100 import_map.fst = builder.into_map();
101 import_map.importables = importables.iter().map(|&(&item, _)| item).collect();
106 /// Returns the `ModPath` needed to import/mention `item`, relative to this crate's root.
107 pub fn path_of(&self, item: ItemInNs) -> Option<&ImportPath> {
108 self.import_info_for(item).map(|it| &it.path)
111 pub fn import_info_for(&self, item: ItemInNs) -> Option<&ImportInfo> {
115 fn collect_trait_assoc_items(
117 db: &dyn DefDatabase,
120 original_import_info: &ImportInfo,
122 let _p = profile::span("collect_trait_assoc_items");
123 for (assoc_item_name, item) in &db.trait_data(tr).items {
124 let module_def_id = match item {
125 AssocItemId::FunctionId(f) => ModuleDefId::from(*f),
126 AssocItemId::ConstId(c) => ModuleDefId::from(*c),
127 // cannot use associated type aliases directly: need a `<Struct as Trait>::TypeAlias`
128 // qualifier, ergo no need to store it for imports in import_map
129 AssocItemId::TypeAliasId(_) => {
130 cov_mark::hit!(type_aliases_ignored);
134 let assoc_item = if is_type_in_ns {
135 ItemInNs::Types(module_def_id)
137 ItemInNs::Values(module_def_id)
140 let mut assoc_item_info = original_import_info.clone();
141 assoc_item_info.path.segments.push(assoc_item_name.to_owned());
142 assoc_item_info.is_trait_assoc_item = true;
143 self.map.insert(assoc_item, assoc_item_info);
148 fn collect_import_map(db: &dyn DefDatabase, krate: CrateId) -> ImportMap {
149 let _p = profile::span("collect_import_map");
151 let def_map = db.crate_def_map(krate);
152 let mut import_map = ImportMap::default();
154 // We look only into modules that are public(ly reexported), starting with the crate root.
155 let empty = ImportPath { segments: vec![] };
156 let root = def_map.module_id(def_map.root());
157 let mut worklist = vec![(root, empty)];
158 while let Some((module, mod_path)) = worklist.pop() {
160 let mod_data = if module.krate == krate {
161 &def_map[module.local_id]
163 // The crate might reexport a module defined in another crate.
164 ext_def_map = module.def_map(db);
165 &ext_def_map[module.local_id]
168 let visible_items = mod_data.scope.entries().filter_map(|(name, per_ns)| {
169 let per_ns = per_ns.filter_visibility(|vis| vis == Visibility::Public);
170 if per_ns.is_none() { None } else { Some((name, per_ns)) }
173 for (name, per_ns) in visible_items {
175 let mut path = mod_path.clone();
176 path.segments.push(name.clone());
180 for item in per_ns.iter_items() {
181 let path = mk_path();
182 let path_len = path.len();
184 ImportInfo { path, container: module, is_trait_assoc_item: false };
186 if let Some(ModuleDefId::TraitId(tr)) = item.as_module_def_id() {
187 import_map.collect_trait_assoc_items(
190 matches!(item, ItemInNs::Types(_)),
195 match import_map.map.entry(item) {
196 Entry::Vacant(entry) => {
197 entry.insert(import_info);
199 Entry::Occupied(mut entry) => {
200 // If the new path is shorter, prefer that one.
201 if path_len < entry.get().path.len() {
202 *entry.get_mut() = import_info;
209 // If we've just added a path to a module, descend into it. We might traverse
210 // modules multiple times, but only if the new path to it is shorter than the
211 // first (else we `continue` above).
212 if let Some(ModuleDefId::ModuleId(mod_id)) = item.as_module_def_id() {
213 worklist.push((mod_id, mk_path()));
222 impl PartialEq for ImportMap {
223 fn eq(&self, other: &Self) -> bool {
224 // `fst` and `importables` are built from `map`, so we don't need to compare them.
225 self.map == other.map
229 impl Eq for ImportMap {}
231 impl fmt::Debug for ImportMap {
232 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
233 let mut importable_paths: Vec<_> = self
236 .map(|(item, info)| {
237 let ns = match item {
238 ItemInNs::Types(_) => "t",
239 ItemInNs::Values(_) => "v",
240 ItemInNs::Macros(_) => "m",
242 format!("- {} ({})", info.path, ns)
246 importable_paths.sort();
247 f.write_str(&importable_paths.join("\n"))
251 fn fst_path(path: &ImportPath) -> String {
252 let _p = profile::span("fst_path");
253 let mut s = path.to_string();
254 s.make_ascii_lowercase();
258 #[derive(Debug, Eq, PartialEq, Hash)]
259 pub enum ImportKind {
273 /// A way to match import map contents against the search query.
275 pub enum SearchMode {
276 /// Import map entry should strictly match the query string.
278 /// Import map entry should contain the query string.
280 /// Import map entry should contain all letters from the query string,
281 /// in the same order, but not necessary adjacent.
290 assoc_items_only: bool,
291 search_mode: SearchMode,
292 case_sensitive: bool,
294 exclude_import_kinds: FxHashSet<ImportKind>,
298 pub fn new(query: String) -> Self {
299 let lowercased = query.to_lowercase();
304 assoc_items_only: false,
305 search_mode: SearchMode::Contains,
306 case_sensitive: false,
307 limit: usize::max_value(),
308 exclude_import_kinds: FxHashSet::default(),
312 /// Matches entries' names only, ignoring the rest of
314 /// Example: for `std::marker::PhantomData`, the name is `PhantomData`.
315 pub fn name_only(self) -> Self {
316 Self { name_only: true, ..self }
319 /// Matches only the entries that are associated items, ignoring the rest.
320 pub fn assoc_items_only(self) -> Self {
321 Self { assoc_items_only: true, ..self }
324 /// Specifies the way to search for the entries using the query.
325 pub fn search_mode(self, search_mode: SearchMode) -> Self {
326 Self { search_mode, ..self }
329 /// Limits the returned number of items to `limit`.
330 pub fn limit(self, limit: usize) -> Self {
331 Self { limit, ..self }
334 /// Respect casing of the query string when matching.
335 pub fn case_sensitive(self) -> Self {
336 Self { case_sensitive: true, ..self }
339 /// Do not include imports of the specified kind in the search results.
340 pub fn exclude_import_kind(mut self, import_kind: ImportKind) -> Self {
341 self.exclude_import_kinds.insert(import_kind);
345 fn import_matches(&self, import: &ImportInfo, enforce_lowercase: bool) -> bool {
346 let _p = profile::span("import_map::Query::import_matches");
347 if import.is_trait_assoc_item {
348 if self.exclude_import_kinds.contains(&ImportKind::AssociatedItem) {
351 } else if self.assoc_items_only {
355 let mut input = if import.is_trait_assoc_item || self.name_only {
356 import.path.segments.last().unwrap().to_string()
358 import.path.to_string()
360 if enforce_lowercase || !self.case_sensitive {
361 input.make_ascii_lowercase();
365 if !enforce_lowercase && self.case_sensitive { &self.query } else { &self.lowercased };
367 match self.search_mode {
368 SearchMode::Equals => &input == query_string,
369 SearchMode::Contains => input.contains(query_string),
370 SearchMode::Fuzzy => {
371 let mut unchecked_query_chars = query_string.chars();
372 let mut mismatching_query_char = unchecked_query_chars.next();
374 for input_char in input.chars() {
375 match mismatching_query_char {
377 Some(matching_query_char) if matching_query_char == input_char => {
378 mismatching_query_char = unchecked_query_chars.next();
383 mismatching_query_char.is_none()
389 /// Searches dependencies of `krate` for an importable path matching `query`.
391 /// This returns a list of items that could be imported from dependencies of `krate`.
392 pub fn search_dependencies<'a>(
393 db: &'a dyn DefDatabase,
396 ) -> FxHashSet<ItemInNs> {
397 let _p = profile::span("search_dependencies").detail(|| format!("{:?}", query));
399 let graph = db.crate_graph();
400 let import_maps: Vec<_> =
401 graph[krate].dependencies.iter().map(|dep| db.import_map(dep.crate_id)).collect();
403 let automaton = fst::automaton::Subsequence::new(&query.lowercased);
405 let mut op = fst::map::OpBuilder::new();
406 for map in &import_maps {
407 op = op.add(map.fst.search(&automaton));
410 let mut stream = op.union();
412 let mut all_indexed_values = FxHashSet::default();
413 while let Some((_, indexed_values)) = stream.next() {
414 all_indexed_values.extend(indexed_values.iter().copied());
417 let mut res = FxHashSet::default();
418 for indexed_value in all_indexed_values {
419 let import_map = &import_maps[indexed_value.index];
420 let importables = &import_map.importables[indexed_value.value as usize..];
422 let common_importable_data = &import_map.map[&importables[0]];
423 if !query.import_matches(common_importable_data, true) {
427 // Path shared by the importable items in this group.
428 let common_importables_path_fst = fst_path(&common_importable_data.path);
429 // Add the items from this `ModPath` group. Those are all subsequent items in
430 // `importables` whose paths match `path`.
431 let iter = importables
434 .take_while(|item| common_importables_path_fst == fst_path(&import_map.map[item].path))
435 .filter(|&item| match item_import_kind(item) {
436 Some(import_kind) => !query.exclude_import_kinds.contains(&import_kind),
440 !query.case_sensitive // we've already checked the common importables path case-insensitively
441 || query.import_matches(&import_map.map[item], false)
445 if res.len() >= query.limit {
453 fn item_import_kind(item: ItemInNs) -> Option<ImportKind> {
454 Some(match item.as_module_def_id()? {
455 ModuleDefId::ModuleId(_) => ImportKind::Module,
456 ModuleDefId::FunctionId(_) => ImportKind::Function,
457 ModuleDefId::AdtId(_) => ImportKind::Adt,
458 ModuleDefId::EnumVariantId(_) => ImportKind::EnumVariant,
459 ModuleDefId::ConstId(_) => ImportKind::Const,
460 ModuleDefId::StaticId(_) => ImportKind::Static,
461 ModuleDefId::TraitId(_) => ImportKind::Trait,
462 ModuleDefId::TypeAliasId(_) => ImportKind::TypeAlias,
463 ModuleDefId::BuiltinType(_) => ImportKind::BuiltinType,
464 ModuleDefId::MacroId(_) => ImportKind::Macro,
470 use base_db::{fixture::WithFixture, SourceDatabase, Upcast};
471 use expect_test::{expect, Expect};
473 use crate::{test_db::TestDB, ItemContainerId, Lookup};
477 fn check_search(ra_fixture: &str, crate_name: &str, query: Query, expect: Expect) {
478 let db = TestDB::with_files(ra_fixture);
479 let crate_graph = db.crate_graph();
480 let krate = crate_graph
483 crate_graph[*krate].display_name.as_ref().map(|n| n.to_string())
484 == Some(crate_name.to_string())
488 let actual = search_dependencies(db.upcast(), krate, query)
490 .filter_map(|dependency| {
491 let dependency_krate = dependency.krate(db.upcast())?;
492 let dependency_imports = db.import_map(dependency_krate);
494 let (path, mark) = match assoc_item_path(&db, &dependency_imports, dependency) {
495 Some(assoc_item_path) => (assoc_item_path, "a"),
497 dependency_imports.path_of(dependency)?.to_string(),
499 ItemInNs::Types(ModuleDefId::FunctionId(_))
500 | ItemInNs::Values(ModuleDefId::FunctionId(_)) => "f",
501 ItemInNs::Types(_) => "t",
502 ItemInNs::Values(_) => "v",
503 ItemInNs::Macros(_) => "m",
510 crate_graph[dependency_krate].display_name.as_ref()?,
515 // HashSet iteration order isn't defined - it's different on
516 // x86_64 and i686 at the very least
518 .collect::<String>();
519 expect.assert_eq(&actual)
523 db: &dyn DefDatabase,
524 dependency_imports: &ImportMap,
525 dependency: ItemInNs,
526 ) -> Option<String> {
527 let dependency_assoc_item_id = match dependency {
528 ItemInNs::Types(ModuleDefId::FunctionId(id))
529 | ItemInNs::Values(ModuleDefId::FunctionId(id)) => AssocItemId::from(id),
530 ItemInNs::Types(ModuleDefId::ConstId(id))
531 | ItemInNs::Values(ModuleDefId::ConstId(id)) => AssocItemId::from(id),
532 ItemInNs::Types(ModuleDefId::TypeAliasId(id))
533 | ItemInNs::Values(ModuleDefId::TypeAliasId(id)) => AssocItemId::from(id),
537 let trait_ = assoc_to_trait(db, dependency)?;
538 if let ModuleDefId::TraitId(tr) = trait_.as_module_def_id()? {
539 let trait_data = db.trait_data(tr);
540 let assoc_item_name =
541 trait_data.items.iter().find_map(|(assoc_item_name, assoc_item_id)| {
542 if &dependency_assoc_item_id == assoc_item_id {
543 Some(assoc_item_name)
548 return Some(format!("{}::{}", dependency_imports.path_of(trait_)?, assoc_item_name));
553 fn assoc_to_trait(db: &dyn DefDatabase, item: ItemInNs) -> Option<ItemInNs> {
554 let assoc: AssocItemId = match item {
555 ItemInNs::Types(it) | ItemInNs::Values(it) => match it {
556 ModuleDefId::TypeAliasId(it) => it.into(),
557 ModuleDefId::FunctionId(it) => it.into(),
558 ModuleDefId::ConstId(it) => it.into(),
564 let container = match assoc {
565 AssocItemId::FunctionId(it) => it.lookup(db).container,
566 AssocItemId::ConstId(it) => it.lookup(db).container,
567 AssocItemId::TypeAliasId(it) => it.lookup(db).container,
571 ItemContainerId::TraitId(it) => Some(ItemInNs::Types(it.into())),
576 fn check(ra_fixture: &str, expect: Expect) {
577 let db = TestDB::with_files(ra_fixture);
578 let crate_graph = db.crate_graph();
580 let actual = crate_graph
582 .filter_map(|krate| {
583 let cdata = &crate_graph[krate];
584 let name = cdata.display_name.as_ref()?;
586 let map = db.import_map(krate);
588 Some(format!("{}:\n{:?}\n", name, map))
591 .collect::<String>();
593 expect.assert_eq(&actual)
600 //- /main.rs crate:main deps:lib
604 pub struct InPrivateModule;
614 pub mod real_pu2 { // same path length as above
618 //- /lib.rs crate:lib
620 pub struct Pub2; // t + v
638 fn prefers_shortest_path() {
641 //- /main.rs crate:main
648 pub use super::sub::subsub::Def;
661 fn type_reexport_cross_crate() {
662 // Reexports need to be visible from a crate, even if the original crate exports the item
663 // at a shorter path.
666 //- /main.rs crate:main deps:lib
670 //- /lib.rs crate:lib
686 fn macro_reexport() {
689 //- /main.rs crate:main deps:lib
691 pub use lib::pub_macro;
693 //- /lib.rs crate:lib
695 macro_rules! pub_macro {
710 fn module_reexport() {
711 // Reexporting modules from a dependency adds all contents to the import map.
714 //- /main.rs crate:main deps:lib
715 pub use lib::module as reexported_module;
716 //- /lib.rs crate:lib
727 - reexported_module (t)
728 - reexported_module::S (t)
729 - reexported_module::S (v)
735 fn cyclic_module_reexport() {
736 // A cyclic reexport does not hang.
739 //- /lib.rs crate:lib
742 pub use super::sub::*;
746 pub use super::module;
763 //- /lib.rs crate:lib
764 macro_rules! private_macro {
779 //- /lib.rs crate:lib
780 pub struct Thing; // t + v
782 macro_rules! Thing { // m
796 //- /lib.rs crate:lib
797 pub mod Thing {} // t
799 macro_rules! Thing { // m
812 fn fuzzy_import_trait_and_assoc_items() {
813 cov_mark::check!(type_aliases_ignored);
815 //- /main.rs crate:main deps:dep
816 //- /dep.rs crate:dep
820 const FMT_CONST: bool;
822 fn format_function();
823 fn format_method(&self);
831 Query::new("fmt".to_string()).search_mode(SearchMode::Fuzzy),
834 dep::fmt::Display (t)
835 dep::fmt::Display::FMT_CONST (a)
836 dep::fmt::Display::format_function (a)
837 dep::fmt::Display::format_method (a)
843 fn assoc_items_filtering() {
845 //- /main.rs crate:main deps:dep
846 //- /dep.rs crate:dep
850 const FMT_CONST: bool;
852 fn format_function();
853 fn format_method(&self);
861 Query::new("fmt".to_string()).search_mode(SearchMode::Fuzzy).assoc_items_only(),
863 dep::fmt::Display::FMT_CONST (a)
864 dep::fmt::Display::format_function (a)
865 dep::fmt::Display::format_method (a)
872 Query::new("fmt".to_string())
873 .search_mode(SearchMode::Fuzzy)
874 .exclude_import_kind(ImportKind::AssociatedItem),
877 dep::fmt::Display (t)
884 Query::new("fmt".to_string())
885 .search_mode(SearchMode::Fuzzy)
887 .exclude_import_kind(ImportKind::AssociatedItem),
895 //- /main.rs crate:main deps:dep
896 //- /dep.rs crate:dep deps:tdep
897 use tdep::fmt as fmt_dep;
912 //- /tdep.rs crate:tdep
914 pub struct NotImportableFromMain;
921 Query::new("fmt".to_string()).search_mode(SearchMode::Fuzzy),
927 dep::fmt::Display (t)
928 dep::fmt::Display::fmt (a)
936 Query::new("fmt".to_string()).search_mode(SearchMode::Equals),
942 dep::fmt::Display::fmt (a)
949 Query::new("fmt".to_string()).search_mode(SearchMode::Contains),
955 dep::fmt::Display (t)
956 dep::fmt::Display::fmt (a)
964 //- /main.rs crate:main deps:dep
965 //- /dep.rs crate:dep deps:tdep
966 use tdep::fmt as fmt_dep;
981 //- /tdep.rs crate:tdep
983 pub struct NotImportableFromMain;
990 Query::new("fmt".to_string()),
996 dep::fmt::Display (t)
997 dep::fmt::Display::fmt (a)
1004 Query::new("fmt".to_string()).name_only(),
1010 dep::fmt::Display::fmt (a)
1016 fn search_casing() {
1017 let ra_fixture = r#"
1018 //- /main.rs crate:main deps:dep
1019 //- /dep.rs crate:dep
1028 Query::new("FMT".to_string()),
1040 Query::new("FMT".to_string()).case_sensitive(),
1052 //- /main.rs crate:main deps:dep
1053 //- /dep.rs crate:dep
1069 Query::new("".to_string()).limit(2),
1080 fn search_exclusions() {
1081 let ra_fixture = r#"
1082 //- /main.rs crate:main deps:dep
1083 //- /dep.rs crate:dep
1092 Query::new("FMT".to_string()),
1104 Query::new("FMT".to_string()).exclude_import_kind(ImportKind::Adt),