//! A map of all publicly exported items in a crate.
-use std::{cmp::Ordering, fmt, hash::BuildHasherDefault, sync::Arc};
+use std::{fmt, hash::BuildHasherDefault, sync::Arc};
use base_db::CrateId;
use fst::{self, Streamer};
use indexmap::{map::Entry, IndexMap};
use itertools::Itertools;
use rustc_hash::{FxHashSet, FxHasher};
-use test_utils::mark;
use crate::{
db::DefDatabase, item_scope::ItemInNs, visibility::Visibility, AssocItemId, ModuleDefId,
impl ImportMap {
pub fn import_map_query(db: &dyn DefDatabase, krate: CrateId) -> Arc<Self> {
let _p = profile::span("import_map_query");
- let def_map = db.crate_def_map(krate);
- let mut import_map = Self::default();
-
- // We look only into modules that are public(ly reexported), starting with the crate root.
- let empty = ImportPath { 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
- };
+ let mut import_map = collect_import_map(db, krate);
- for item in per_ns.iter_items() {
- let path = mk_path();
- let path_len = path.len();
- let import_info =
- ImportInfo { path, container: module, is_trait_assoc_item: false };
-
- if let Some(ModuleDefId::TraitId(tr)) = item.as_module_def_id() {
- import_map.collect_trait_assoc_items(
- db,
- tr,
- matches!(item, ItemInNs::Types(_)),
- &import_info,
- );
- }
-
- match import_map.map.entry(item) {
- Entry::Vacant(entry) => {
- entry.insert(import_info);
- }
- Entry::Occupied(mut entry) => {
- // If the new path is shorter, prefer that one.
- if path_len < entry.get().path.len() {
- *entry.get_mut() = import_info;
- } else {
- continue;
- }
- }
- }
-
- // 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()));
- }
- }
- }
- }
-
- let mut importables = import_map.map.iter().collect::<Vec<_>>();
-
- importables.sort_by(cmp);
+ let mut importables = import_map
+ .map
+ .iter()
+ .map(|(item, info)| (item, fst_path(&info.path)))
+ .collect::<Vec<_>>();
+ importables.sort_by(|(_, fst_path), (_, fst_path2)| fst_path.cmp(fst_path2));
// Build the FST, taking care not to insert duplicate values.
let mut last_batch_start = 0;
for idx in 0..importables.len() {
- if let Some(next_item) = importables.get(idx + 1) {
- if cmp(&importables[last_batch_start], next_item) == Ordering::Equal {
+ let key = &importables[last_batch_start].1;
+ if let Some((_, fst_path)) = importables.get(idx + 1) {
+ if key == fst_path {
continue;
}
}
- let key = fst_path(&importables[last_batch_start].1.path);
- builder.insert(key, last_batch_start as u64).unwrap();
+ let _ = builder.insert(key, last_batch_start as u64);
last_batch_start = idx + 1;
}
- import_map.fst = fst::Map::new(builder.into_inner().unwrap()).unwrap();
- import_map.importables = importables.iter().map(|(item, _)| **item).collect();
+ import_map.fst = builder.into_map();
+ import_map.importables = importables.iter().map(|&(&item, _)| item).collect();
Arc::new(import_map)
}
is_type_in_ns: bool,
original_import_info: &ImportInfo,
) {
+ let _p = profile::span("collect_trait_assoc_items");
for (assoc_item_name, item) in &db.trait_data(tr).items {
let module_def_id = match item {
AssocItemId::FunctionId(f) => ModuleDefId::from(*f),
// cannot use associated type aliases directly: need a `<Struct as Trait>::TypeAlias`
// qualifier, ergo no need to store it for imports in import_map
AssocItemId::TypeAliasId(_) => {
- mark::hit!(type_aliases_ignored);
+ cov_mark::hit!(type_aliases_ignored);
continue;
}
};
}
}
+fn collect_import_map(db: &dyn DefDatabase, krate: CrateId) -> ImportMap {
+ let _p = profile::span("collect_import_map");
+
+ let def_map = db.crate_def_map(krate);
+ let mut import_map = ImportMap::default();
+
+ // We look only into modules that are public(ly reexported), starting with the crate root.
+ let empty = ImportPath { segments: vec![] };
+ let root = def_map.module_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 = module.def_map(db);
+ &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();
+ let path_len = path.len();
+ let import_info =
+ ImportInfo { path, container: module, is_trait_assoc_item: false };
+
+ if let Some(ModuleDefId::TraitId(tr)) = item.as_module_def_id() {
+ import_map.collect_trait_assoc_items(
+ db,
+ tr,
+ matches!(item, ItemInNs::Types(_)),
+ &import_info,
+ );
+ }
+
+ match import_map.map.entry(item) {
+ Entry::Vacant(entry) => {
+ entry.insert(import_info);
+ }
+ Entry::Occupied(mut entry) => {
+ // If the new path is shorter, prefer that one.
+ if path_len < entry.get().path.len() {
+ *entry.get_mut() = import_info;
+ } else {
+ continue;
+ }
+ }
+ }
+
+ // 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()));
+ }
+ }
+ }
+ }
+
+ import_map
+}
+
impl PartialEq for ImportMap {
fn eq(&self, other: &Self) -> bool {
// `fst` and `importables` are built from `map`, so we don't need to compare them.
}
fn fst_path(path: &ImportPath) -> String {
+ let _p = profile::span("fst_path");
let mut s = path.to_string();
s.make_ascii_lowercase();
s
}
-fn cmp((_, lhs): &(&ItemInNs, &ImportInfo), (_, rhs): &(&ItemInNs, &ImportInfo)) -> Ordering {
- let lhs_str = fst_path(&lhs.path);
- let rhs_str = fst_path(&rhs.path);
- lhs_str.cmp(&rhs_str)
-}
-
#[derive(Debug, Eq, PartialEq, Hash)]
pub enum ImportKind {
Module,
}
fn import_matches(&self, import: &ImportInfo, enforce_lowercase: bool) -> bool {
+ let _p = profile::span("import_map::Query::import_matches");
if import.is_trait_assoc_item {
if self.exclude_import_kinds.contains(&ImportKind::AssociatedItem) {
return false;
db: &'a dyn DefDatabase,
krate: CrateId,
query: Query,
-) -> Vec<ItemInNs> {
+) -> FxHashSet<ItemInNs> {
let _p = profile::span("search_dependencies").detail(|| format!("{:?}", query));
let graph = db.crate_graph();
}
let mut stream = op.union();
- let mut res = Vec::new();
+
+ let mut all_indexed_values = FxHashSet::default();
while let Some((_, indexed_values)) = stream.next() {
- for indexed_value in indexed_values {
- let import_map = &import_maps[indexed_value.index];
- let importables = &import_map.importables[indexed_value.value as usize..];
+ all_indexed_values.extend(indexed_values.iter().copied());
+ }
- let common_importable_data = &import_map.map[&importables[0]];
- if !query.import_matches(common_importable_data, true) {
- continue;
- }
+ let mut res = FxHashSet::default();
+ for indexed_value in all_indexed_values {
+ let import_map = &import_maps[indexed_value.index];
+ let importables = &import_map.importables[indexed_value.value as usize..];
+
+ let common_importable_data = &import_map.map[&importables[0]];
+ if !query.import_matches(common_importable_data, true) {
+ continue;
+ }
- // Path shared by the importable items in this group.
- let common_importables_path_fst = fst_path(&common_importable_data.path);
- // Add the items from this `ModPath` group. Those are all subsequent items in
- // `importables` whose paths match `path`.
- let iter = importables
- .iter()
- .copied()
- .take_while(|item| {
- common_importables_path_fst == fst_path(&import_map.map[item].path)
- })
- .filter(|&item| match item_import_kind(item) {
- Some(import_kind) => !query.exclude_import_kinds.contains(&import_kind),
- None => true,
- })
- .filter(|item| {
- !query.case_sensitive // we've already checked the common importables path case-insensitively
+ // Path shared by the importable items in this group.
+ let common_importables_path_fst = fst_path(&common_importable_data.path);
+ // Add the items from this `ModPath` group. Those are all subsequent items in
+ // `importables` whose paths match `path`.
+ let iter = importables
+ .iter()
+ .copied()
+ .take_while(|item| common_importables_path_fst == fst_path(&import_map.map[item].path))
+ .filter(|&item| match item_import_kind(item) {
+ Some(import_kind) => !query.exclude_import_kinds.contains(&import_kind),
+ None => true,
+ })
+ .filter(|item| {
+ !query.case_sensitive // we've already checked the common importables path case-insensitively
|| query.import_matches(&import_map.map[item], false)
- });
- res.extend(iter);
+ });
+ res.extend(iter);
- if res.len() >= query.limit {
- res.truncate(query.limit);
- return res;
- }
+ if res.len() >= query.limit {
+ return res;
}
}
mod tests {
use base_db::{fixture::WithFixture, SourceDatabase, Upcast};
use expect_test::{expect, Expect};
- use test_utils::mark;
- use crate::{test_db::TestDB, AssocContainerId, Lookup};
+ use crate::{test_db::TestDB, ItemContainerId, Lookup};
use super::*;
};
match container {
- AssocContainerId::TraitId(it) => Some(ItemInNs::Types(it.into())),
+ ItemContainerId::TraitId(it) => Some(ItemInNs::Types(it.into())),
_ => None,
}
}
#[test]
fn fuzzy_import_trait_and_assoc_items() {
- mark::check!(type_aliases_ignored);
+ cov_mark::check!(type_aliases_ignored);
let ra_fixture = r#"
//- /main.rs crate:main deps:dep
//- /dep.rs crate:dep
Query::new("fmt".to_string()).search_mode(SearchMode::Fuzzy),
expect![[r#"
dep::fmt (t)
+ dep::fmt::Display::format_method (a)
dep::fmt::Display (t)
dep::fmt::Display::FMT_CONST (a)
dep::fmt::Display::format_function (a)
- dep::fmt::Display::format_method (a)
"#]],
);
}
"main",
Query::new("fmt".to_string()).search_mode(SearchMode::Fuzzy).assoc_items_only(),
expect![[r#"
+ dep::fmt::Display::format_method (a)
dep::fmt::Display::FMT_CONST (a)
dep::fmt::Display::format_function (a)
- dep::fmt::Display::format_method (a)
"#]],
);
Query::new("fmt".to_string()).search_mode(SearchMode::Fuzzy),
expect![[r#"
dep::fmt (t)
- dep::Fmt (t)
+ dep::format (f)
dep::Fmt (v)
dep::Fmt (m)
- dep::fmt::Display (t)
+ dep::Fmt (t)
dep::fmt::Display::fmt (a)
- dep::format (f)
+ dep::fmt::Display (t)
"#]],
);
Query::new("fmt".to_string()).search_mode(SearchMode::Equals),
expect![[r#"
dep::fmt (t)
- dep::Fmt (t)
dep::Fmt (v)
dep::Fmt (m)
+ dep::Fmt (t)
dep::fmt::Display::fmt (a)
"#]],
);
Query::new("fmt".to_string()).search_mode(SearchMode::Contains),
expect![[r#"
dep::fmt (t)
- dep::Fmt (t)
dep::Fmt (v)
dep::Fmt (m)
- dep::fmt::Display (t)
+ dep::Fmt (t)
dep::fmt::Display::fmt (a)
+ dep::fmt::Display (t)
"#]],
);
}
Query::new("fmt".to_string()),
expect![[r#"
dep::fmt (t)
- dep::Fmt (t)
dep::Fmt (v)
dep::Fmt (m)
- dep::fmt::Display (t)
+ dep::Fmt (t)
dep::fmt::Display::fmt (a)
+ dep::fmt::Display (t)
"#]],
);
Query::new("fmt".to_string()).name_only(),
expect![[r#"
dep::fmt (t)
- dep::Fmt (t)
dep::Fmt (v)
dep::Fmt (m)
+ dep::Fmt (t)
dep::fmt::Display::fmt (a)
"#]],
);
Query::new("FMT".to_string()),
expect![[r#"
dep::fmt (t)
+ dep::FMT (v)
dep::fmt (v)
dep::FMT (t)
- dep::FMT (v)
"#]],
);
Query::new("".to_string()).limit(2),
expect![[r#"
dep::fmt (t)
+ dep::Fmt (m)
dep::Fmt (t)
+ dep::Fmt (v)
"#]],
);
}
Query::new("FMT".to_string()),
expect![[r#"
dep::fmt (t)
+ dep::FMT (v)
dep::fmt (v)
dep::FMT (t)
- dep::FMT (v)
"#]],
);
projects / rust.git / blobdiff