1 //! A map of all publicly exported items in a crate.
3 use std::{cmp::Ordering, 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::{FxHashMap, FxHashSet, FxHasher};
11 use smallvec::SmallVec;
15 db::DefDatabase, item_scope::ItemInNs, visibility::Visibility, AssocItemId, ModuleDefId,
19 type FxIndexMap<K, V> = IndexMap<K, V, BuildHasherDefault<FxHasher>>;
21 /// Item import details stored in the `ImportMap`.
22 #[derive(Debug, Clone, Eq, PartialEq)]
23 pub struct ImportInfo {
24 /// A path that can be used to import the item, relative to the crate's root.
26 /// The module containing this item.
27 pub container: ModuleId,
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>>,
68 /// Maps names of associated items to the item's ID. Only includes items whose defining trait is
70 assoc_map: FxHashMap<SmolStr, SmallVec<[AssocItemId; 1]>>,
74 pub fn import_map_query(db: &dyn DefDatabase, krate: CrateId) -> Arc<Self> {
75 let _p = profile::span("import_map_query");
76 let def_map = db.crate_def_map(krate);
77 let mut import_map = Self::default();
79 // We look only into modules that are public(ly reexported), starting with the crate root.
80 let empty = ImportPath { segments: vec![] };
81 let root = ModuleId { krate, local_id: def_map.root };
82 let mut worklist = vec![(root, empty)];
83 while let Some((module, mod_path)) = worklist.pop() {
85 let mod_data = if module.krate == krate {
86 &def_map[module.local_id]
88 // The crate might reexport a module defined in another crate.
89 ext_def_map = db.crate_def_map(module.krate);
90 &ext_def_map[module.local_id]
93 let visible_items = mod_data.scope.entries().filter_map(|(name, per_ns)| {
94 let per_ns = per_ns.filter_visibility(|vis| vis == Visibility::Public);
102 for (name, per_ns) in visible_items {
104 let mut path = mod_path.clone();
105 path.segments.push(name.clone());
109 for item in per_ns.iter_items() {
110 let path = mk_path();
111 match import_map.map.entry(item) {
112 Entry::Vacant(entry) => {
113 entry.insert(ImportInfo { path, container: module });
115 Entry::Occupied(mut entry) => {
116 // If the new path is shorter, prefer that one.
117 if path.len() < entry.get().path.len() {
118 *entry.get_mut() = ImportInfo { path, container: module };
125 // If we've just added a path to a module, descend into it. We might traverse
126 // modules multiple times, but only if the new path to it is shorter than the
127 // first (else we `continue` above).
128 if let Some(ModuleDefId::ModuleId(mod_id)) = item.as_module_def_id() {
129 worklist.push((mod_id, mk_path()));
132 // If we've added a path to a trait, add the trait's methods to the method map.
133 if let Some(ModuleDefId::TraitId(tr)) = item.as_module_def_id() {
134 import_map.collect_trait_methods(db, tr);
140 let mut importables = import_map.map.iter().collect::<Vec<_>>();
142 importables.sort_by(cmp);
144 // Build the FST, taking care not to insert duplicate values.
146 let mut builder = fst::MapBuilder::memory();
147 let mut last_batch_start = 0;
149 for idx in 0..importables.len() {
150 if let Some(next_item) = importables.get(idx + 1) {
151 if cmp(&importables[last_batch_start], next_item) == Ordering::Equal {
156 let start = last_batch_start;
157 last_batch_start = idx + 1;
159 let key = fst_path(&importables[start].1.path);
161 builder.insert(key, start as u64).unwrap();
164 import_map.fst = fst::Map::new(builder.into_inner().unwrap()).unwrap();
165 import_map.importables = importables.iter().map(|(item, _)| **item).collect();
170 /// Returns the `ModPath` needed to import/mention `item`, relative to this crate's root.
171 pub fn path_of(&self, item: ItemInNs) -> Option<&ImportPath> {
172 self.import_info_for(item).map(|it| &it.path)
175 pub fn import_info_for(&self, item: ItemInNs) -> Option<&ImportInfo> {
179 fn collect_trait_methods(&mut self, db: &dyn DefDatabase, tr: TraitId) {
180 let data = db.trait_data(tr);
181 for (name, item) in data.items.iter() {
182 self.assoc_map.entry(name.to_string().into()).or_default().push(*item);
187 impl PartialEq for ImportMap {
188 fn eq(&self, other: &Self) -> bool {
189 // `fst` and `importables` are built from `map`, so we don't need to compare them.
190 self.map == other.map
194 impl Eq for ImportMap {}
196 impl fmt::Debug for ImportMap {
197 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
198 let mut importable_paths: Vec<_> = self
201 .map(|(item, info)| {
202 let ns = match item {
203 ItemInNs::Types(_) => "t",
204 ItemInNs::Values(_) => "v",
205 ItemInNs::Macros(_) => "m",
207 format!("- {} ({})", info.path, ns)
211 importable_paths.sort();
212 f.write_str(&importable_paths.join("\n"))
216 fn fst_path(path: &ImportPath) -> String {
217 let mut s = path.to_string();
218 s.make_ascii_lowercase();
222 fn cmp((_, lhs): &(&ItemInNs, &ImportInfo), (_, rhs): &(&ItemInNs, &ImportInfo)) -> Ordering {
223 let lhs_str = fst_path(&lhs.path);
224 let rhs_str = fst_path(&rhs.path);
225 lhs_str.cmp(&rhs_str)
228 #[derive(Debug, Eq, PartialEq, Hash)]
229 pub enum ImportKind {
241 /// A way to match import map contents against the search query.
243 pub enum SearchMode {
244 /// Import map entry should strictly match the query string.
246 /// Import map entry should contain the query string.
248 /// Import map entry should contain all letters from the query string,
249 /// in the same order, but not necessary adjacent.
258 search_mode: SearchMode,
259 case_sensitive: bool,
261 exclude_import_kinds: FxHashSet<ImportKind>,
265 pub fn new(query: String) -> Self {
266 let lowercased = query.to_lowercase();
271 search_mode: SearchMode::Contains,
272 case_sensitive: false,
273 limit: usize::max_value(),
274 exclude_import_kinds: FxHashSet::default(),
278 /// Matches entries' names only, ignoring the rest of
280 /// Example: for `std::marker::PhantomData`, the name is `PhantomData`.
281 pub fn name_only(self) -> Self {
282 Self { name_only: true, ..self }
285 /// Specifies the way to search for the entries using the query.
286 pub fn search_mode(self, search_mode: SearchMode) -> Self {
287 Self { search_mode, ..self }
290 /// Limits the returned number of items to `limit`.
291 pub fn limit(self, limit: usize) -> Self {
292 Self { limit, ..self }
295 /// Respect casing of the query string when matching.
296 pub fn case_sensitive(self) -> Self {
297 Self { case_sensitive: true, ..self }
300 /// Do not include imports of the specified kind in the search results.
301 pub fn exclude_import_kind(mut self, import_kind: ImportKind) -> Self {
302 self.exclude_import_kinds.insert(import_kind);
307 fn contains_query(query: &Query, input_path: &ImportPath, enforce_lowercase: bool) -> bool {
308 let mut input = if query.name_only {
309 input_path.segments.last().unwrap().to_string()
311 input_path.to_string()
313 if enforce_lowercase || !query.case_sensitive {
314 input.make_ascii_lowercase();
318 if !enforce_lowercase && query.case_sensitive { &query.query } else { &query.lowercased };
320 match query.search_mode {
321 SearchMode::Equals => &input == query_string,
322 SearchMode::Contains => input.contains(query_string),
323 SearchMode::Fuzzy => {
324 let mut unchecked_query_chars = query_string.chars();
325 let mut mismatching_query_char = unchecked_query_chars.next();
327 for input_char in input.chars() {
328 match mismatching_query_char {
330 Some(matching_query_char) if matching_query_char == input_char => {
331 mismatching_query_char = unchecked_query_chars.next();
336 mismatching_query_char.is_none()
341 /// Searches dependencies of `krate` for an importable path matching `query`.
343 /// This returns a list of items that could be imported from dependencies of `krate`.
344 pub fn search_dependencies<'a>(
345 db: &'a dyn DefDatabase,
349 let _p = profile::span("search_dependencies").detail(|| format!("{:?}", query));
351 let graph = db.crate_graph();
352 let import_maps: Vec<_> =
353 graph[krate].dependencies.iter().map(|dep| db.import_map(dep.crate_id)).collect();
355 let automaton = fst::automaton::Subsequence::new(&query.lowercased);
357 let mut op = fst::map::OpBuilder::new();
358 for map in &import_maps {
359 op = op.add(map.fst.search(&automaton));
362 let mut stream = op.union();
363 let mut res = Vec::new();
364 while let Some((_, indexed_values)) = stream.next() {
365 for indexed_value in indexed_values {
366 let import_map = &import_maps[indexed_value.index];
367 let importables = &import_map.importables[indexed_value.value as usize..];
369 // Path shared by the importable items in this group.
370 let common_importables_path = &import_map.map[&importables[0]].path;
371 if !contains_query(&query, common_importables_path, true) {
375 let common_importables_path_fst = fst_path(common_importables_path);
376 // Add the items from this `ModPath` group. Those are all subsequent items in
377 // `importables` whose paths match `path`.
378 let iter = importables
382 common_importables_path_fst == fst_path(&import_map.map[item].path)
384 .filter(|&item| match item_import_kind(item) {
385 Some(import_kind) => !query.exclude_import_kinds.contains(&import_kind),
389 !query.case_sensitive // we've already checked the common importables path case-insensitively
390 || contains_query(&query, &import_map.map[item].path, false)
394 if res.len() >= query.limit {
395 res.truncate(query.limit);
401 // Add all exported associated items whose names match the query (exactly).
402 for map in &import_maps {
403 if let Some(v) = map.assoc_map.get(&*query.query) {
404 res.extend(v.iter().map(|&assoc| {
405 ItemInNs::Types(match assoc {
406 AssocItemId::FunctionId(it) => it.into(),
407 AssocItemId::ConstId(it) => it.into(),
408 AssocItemId::TypeAliasId(it) => it.into(),
417 fn item_import_kind(item: ItemInNs) -> Option<ImportKind> {
418 Some(match item.as_module_def_id()? {
419 ModuleDefId::ModuleId(_) => ImportKind::Module,
420 ModuleDefId::FunctionId(_) => ImportKind::Function,
421 ModuleDefId::AdtId(_) => ImportKind::Adt,
422 ModuleDefId::EnumVariantId(_) => ImportKind::EnumVariant,
423 ModuleDefId::ConstId(_) => ImportKind::Const,
424 ModuleDefId::StaticId(_) => ImportKind::Static,
425 ModuleDefId::TraitId(_) => ImportKind::Trait,
426 ModuleDefId::TypeAliasId(_) => ImportKind::TypeAlias,
427 ModuleDefId::BuiltinType(_) => ImportKind::BuiltinType,
433 use base_db::{fixture::WithFixture, SourceDatabase, Upcast};
434 use expect_test::{expect, Expect};
436 use crate::{data::FunctionData, test_db::TestDB, AssocContainerId, Lookup};
440 fn check_search(ra_fixture: &str, crate_name: &str, query: Query, expect: Expect) {
441 let db = TestDB::with_files(ra_fixture);
442 let crate_graph = db.crate_graph();
443 let krate = crate_graph
446 crate_graph[*krate].display_name.as_ref().map(|n| n.to_string())
447 == Some(crate_name.to_string())
451 let actual = search_dependencies(db.upcast(), krate, query)
454 let mark = match item {
455 ItemInNs::Types(ModuleDefId::FunctionId(_))
456 | ItemInNs::Values(ModuleDefId::FunctionId(_)) => "f",
457 ItemInNs::Types(_) => "t",
458 ItemInNs::Values(_) => "v",
459 ItemInNs::Macros(_) => "m",
461 item.krate(db.upcast()).map(|krate| {
462 let map = db.import_map(krate);
464 let path = match assoc_to_trait(&db, item) {
466 let mut full_path = map.path_of(trait_).unwrap().to_string();
467 if let ItemInNs::Types(ModuleDefId::FunctionId(function_id))
468 | ItemInNs::Values(ModuleDefId::FunctionId(function_id)) = item
470 full_path += &format!(
472 FunctionData::fn_data_query(&db, function_id).name
477 None => map.path_of(item).unwrap().to_string(),
482 crate_graph[krate].display_name.as_ref().unwrap(),
488 .collect::<String>();
489 expect.assert_eq(&actual)
492 fn assoc_to_trait(db: &dyn DefDatabase, item: ItemInNs) -> Option<ItemInNs> {
493 let assoc: AssocItemId = match item {
494 ItemInNs::Types(it) | ItemInNs::Values(it) => match it {
495 ModuleDefId::TypeAliasId(it) => it.into(),
496 ModuleDefId::FunctionId(it) => it.into(),
497 ModuleDefId::ConstId(it) => it.into(),
503 let container = match assoc {
504 AssocItemId::FunctionId(it) => it.lookup(db).container,
505 AssocItemId::ConstId(it) => it.lookup(db).container,
506 AssocItemId::TypeAliasId(it) => it.lookup(db).container,
510 AssocContainerId::TraitId(it) => Some(ItemInNs::Types(it.into())),
515 fn check(ra_fixture: &str, expect: Expect) {
516 let db = TestDB::with_files(ra_fixture);
517 let crate_graph = db.crate_graph();
519 let actual = crate_graph
521 .filter_map(|krate| {
522 let cdata = &crate_graph[krate];
523 let name = cdata.display_name.as_ref()?;
525 let map = db.import_map(krate);
527 Some(format!("{}:\n{:?}\n", name, map))
529 .collect::<String>();
531 expect.assert_eq(&actual)
538 //- /main.rs crate:main deps:lib
542 pub struct InPrivateModule;
552 pub mod real_pu2 { // same path length as above
556 //- /lib.rs crate:lib
558 pub struct Pub2; // t + v
576 fn prefers_shortest_path() {
579 //- /main.rs crate:main
586 pub use super::sub::subsub::Def;
599 fn type_reexport_cross_crate() {
600 // Reexports need to be visible from a crate, even if the original crate exports the item
601 // at a shorter path.
604 //- /main.rs crate:main deps:lib
608 //- /lib.rs crate:lib
624 fn macro_reexport() {
627 //- /main.rs crate:main deps:lib
629 pub use lib::pub_macro;
631 //- /lib.rs crate:lib
633 macro_rules! pub_macro {
648 fn module_reexport() {
649 // Reexporting modules from a dependency adds all contents to the import map.
652 //- /main.rs crate:main deps:lib
653 pub use lib::module as reexported_module;
654 //- /lib.rs crate:lib
661 - reexported_module (t)
662 - reexported_module::S (t)
663 - reexported_module::S (v)
673 fn cyclic_module_reexport() {
674 // A cyclic reexport does not hang.
677 //- /lib.rs crate:lib
680 pub use super::sub::*;
684 pub use super::module;
701 //- /lib.rs crate:lib
702 macro_rules! private_macro {
717 //- /lib.rs crate:lib
718 pub struct Thing; // t + v
720 macro_rules! Thing { // m
734 //- /lib.rs crate:lib
735 pub mod Thing {} // t
737 macro_rules! Thing { // m
752 //- /main.rs crate:main deps:dep
753 //- /dep.rs crate:dep deps:tdep
754 use tdep::fmt as fmt_dep;
769 //- /tdep.rs crate:tdep
771 pub struct NotImportableFromMain;
778 Query::new("fmt".to_string()).search_mode(SearchMode::Fuzzy),
784 dep::fmt::Display (t)
786 dep::fmt::Display::fmt (f)
793 Query::new("fmt".to_string()).search_mode(SearchMode::Equals),
799 dep::fmt::Display::fmt (f)
806 Query::new("fmt".to_string()).search_mode(SearchMode::Contains),
812 dep::fmt::Display (t)
813 dep::fmt::Display::fmt (f)
821 //- /main.rs crate:main deps:dep
822 //- /dep.rs crate:dep deps:tdep
823 use tdep::fmt as fmt_dep;
838 //- /tdep.rs crate:tdep
840 pub struct NotImportableFromMain;
847 Query::new("fmt".to_string()),
853 dep::fmt::Display (t)
854 dep::fmt::Display::fmt (f)
861 Query::new("fmt".to_string()).name_only(),
867 dep::fmt::Display::fmt (f)
875 //- /main.rs crate:main deps:dep
876 //- /dep.rs crate:dep
885 Query::new("FMT".to_string()),
897 Query::new("FMT".to_string()).case_sensitive(),
909 //- /main.rs crate:main deps:dep
910 //- /dep.rs crate:dep
926 Query::new("".to_string()).limit(2),
935 fn search_exclusions() {
937 //- /main.rs crate:main deps:dep
938 //- /dep.rs crate:dep
947 Query::new("FMT".to_string()),
959 Query::new("FMT".to_string()).exclude_import_kind(ImportKind::Adt),