//! 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};
/// The module containing this item.
pub container: ModuleId,
/// Whether the import is a trait associated item or not.
- pub is_assoc_item: bool,
+ pub is_trait_assoc_item: bool,
}
#[derive(Debug, Clone, Eq, PartialEq)]
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
- };
-
- for item in per_ns.iter_items() {
- let path = mk_path();
- let path_len = path.len();
- let import_info = ImportInfo { path, container: module, is_assoc_item: false };
-
- // If we've added a path to a trait, add the trait's associated items to the assoc map.
- if let Some(ModuleDefId::TraitId(tr)) = item.as_module_def_id() {
- import_map.collect_trait_assoc_items(db, tr, &import_info);
- }
+ let mut import_map = collect_import_map(db, krate);
- 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)
}
&mut self,
db: &dyn DefDatabase,
tr: TraitId,
- import_info: &ImportInfo,
+ is_type_in_ns: bool,
+ original_import_info: &ImportInfo,
) {
- for (assoc_item_name, item) in db.trait_data(tr).items.iter() {
- let assoc_item = ItemInNs::Types(match item.clone() {
- AssocItemId::FunctionId(f) => f.into(),
- AssocItemId::ConstId(c) => c.into(),
- AssocItemId::TypeAliasId(t) => t.into(),
- });
- let mut assoc_item_info = import_info.to_owned();
+ 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),
+ AssocItemId::ConstId(c) => ModuleDefId::from(*c),
+ // 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(_) => {
+ cov_mark::hit!(type_aliases_ignored);
+ continue;
+ }
+ };
+ let assoc_item = if is_type_in_ns {
+ ItemInNs::Types(module_def_id)
+ } else {
+ ItemInNs::Values(module_def_id)
+ };
+
+ let mut assoc_item_info = original_import_info.clone();
assoc_item_info.path.segments.push(assoc_item_name.to_owned());
- assoc_item_info.is_assoc_item = true;
+ assoc_item_info.is_trait_assoc_item = true;
self.map.insert(assoc_item, assoc_item_info);
}
}
}
+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,
Trait,
TypeAlias,
BuiltinType,
+ AssociatedItem,
}
/// A way to match import map contents against the search query.
query: String,
lowercased: String,
name_only: bool,
+ assoc_items_only: bool,
search_mode: SearchMode,
case_sensitive: bool,
limit: usize,
query,
lowercased,
name_only: false,
+ assoc_items_only: false,
search_mode: SearchMode::Contains,
case_sensitive: false,
limit: usize::max_value(),
Self { name_only: true, ..self }
}
+ /// Matches only the entries that are associated items, ignoring the rest.
+ pub fn assoc_items_only(self) -> Self {
+ Self { assoc_items_only: true, ..self }
+ }
+
/// Specifies the way to search for the entries using the query.
pub fn search_mode(self, search_mode: SearchMode) -> Self {
Self { search_mode, ..self }
self.exclude_import_kinds.insert(import_kind);
self
}
-}
-fn import_matches_query(import: &ImportInfo, query: &Query, enforce_lowercase: bool) -> bool {
- let mut input = if import.is_assoc_item || query.name_only {
- import.path.segments.last().unwrap().to_string()
- } else {
- import.path.to_string()
- };
- if enforce_lowercase || !query.case_sensitive {
- input.make_ascii_lowercase();
- }
-
- let query_string =
- if !enforce_lowercase && query.case_sensitive { &query.query } else { &query.lowercased };
-
- match query.search_mode {
- SearchMode::Equals => &input == query_string,
- SearchMode::Contains => input.contains(query_string),
- SearchMode::Fuzzy => {
- let mut unchecked_query_chars = query_string.chars();
- let mut mismatching_query_char = unchecked_query_chars.next();
-
- for input_char in input.chars() {
- match mismatching_query_char {
- None => return true,
- Some(matching_query_char) if matching_query_char == input_char => {
- mismatching_query_char = unchecked_query_chars.next();
+ 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;
+ }
+ } else if self.assoc_items_only {
+ return false;
+ }
+
+ let mut input = if import.is_trait_assoc_item || self.name_only {
+ import.path.segments.last().unwrap().to_string()
+ } else {
+ import.path.to_string()
+ };
+ if enforce_lowercase || !self.case_sensitive {
+ input.make_ascii_lowercase();
+ }
+
+ let query_string =
+ if !enforce_lowercase && self.case_sensitive { &self.query } else { &self.lowercased };
+
+ match self.search_mode {
+ SearchMode::Equals => &input == query_string,
+ SearchMode::Contains => input.contains(query_string),
+ SearchMode::Fuzzy => {
+ let mut unchecked_query_chars = query_string.chars();
+ let mut mismatching_query_char = unchecked_query_chars.next();
+
+ for input_char in input.chars() {
+ match mismatching_query_char {
+ None => return true,
+ Some(matching_query_char) if matching_query_char == input_char => {
+ mismatching_query_char = unchecked_query_chars.next();
+ }
+ _ => (),
}
- _ => (),
}
+ mismatching_query_char.is_none()
}
- mismatching_query_char.is_none()
}
}
}
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 !import_matches_query(common_importable_data, &query, 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..];
- // 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
- || import_matches_query(&import_map.map[item], &query, false)
- });
- res.extend(iter);
-
- if res.len() >= query.limit {
- res.truncate(query.limit);
- return res;
- }
+ 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
+ || query.import_matches(&import_map.map[item], false)
+ });
+ res.extend(iter);
+
+ if res.len() >= query.limit {
+ return res;
}
}
use base_db::{fixture::WithFixture, SourceDatabase, Upcast};
use expect_test::{expect, Expect};
- use crate::{test_db::TestDB, AssocContainerId, Lookup};
+ use crate::{test_db::TestDB, ItemContainerId, Lookup};
use super::*;
None => (
dependency_imports.path_of(dependency)?.to_string(),
match dependency {
+ ItemInNs::Types(ModuleDefId::FunctionId(_))
+ | ItemInNs::Values(ModuleDefId::FunctionId(_)) => "f",
ItemInNs::Types(_) => "t",
ItemInNs::Values(_) => "v",
ItemInNs::Macros(_) => "m",
dependency_imports: &ImportMap,
dependency: ItemInNs,
) -> Option<String> {
- let dependency_assoc_item_id = dependency.as_assoc_item_id()?;
+ let dependency_assoc_item_id = match dependency {
+ ItemInNs::Types(ModuleDefId::FunctionId(id))
+ | ItemInNs::Values(ModuleDefId::FunctionId(id)) => AssocItemId::from(id),
+ ItemInNs::Types(ModuleDefId::ConstId(id))
+ | ItemInNs::Values(ModuleDefId::ConstId(id)) => AssocItemId::from(id),
+ ItemInNs::Types(ModuleDefId::TypeAliasId(id))
+ | ItemInNs::Values(ModuleDefId::TypeAliasId(id)) => AssocItemId::from(id),
+ _ => return None,
+ };
+
let trait_ = assoc_to_trait(db, dependency)?;
if let ModuleDefId::TraitId(tr) = trait_.as_module_def_id()? {
let trait_data = db.trait_data(tr);
};
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() {
+ 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::FmtTypeAlias (a)
dep::fmt::Display::format_function (a)
- dep::fmt::Display::format_method (a)
"#]],
);
}
+ #[test]
+ fn assoc_items_filtering() {
+ let ra_fixture = r#"
+ //- /main.rs crate:main deps:dep
+ //- /dep.rs crate:dep
+ pub mod fmt {
+ pub trait Display {
+ type FmtTypeAlias;
+ const FMT_CONST: bool;
+
+ fn format_function();
+ fn format_method(&self);
+ }
+ }
+ "#;
+
+ check_search(
+ ra_fixture,
+ "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)
+ "#]],
+ );
+
+ check_search(
+ ra_fixture,
+ "main",
+ Query::new("fmt".to_string())
+ .search_mode(SearchMode::Fuzzy)
+ .exclude_import_kind(ImportKind::AssociatedItem),
+ expect![[r#"
+ dep::fmt (t)
+ dep::fmt::Display (t)
+ "#]],
+ );
+
+ check_search(
+ ra_fixture,
+ "main",
+ Query::new("fmt".to_string())
+ .search_mode(SearchMode::Fuzzy)
+ .assoc_items_only()
+ .exclude_import_kind(ImportKind::AssociatedItem),
+ expect![[r#""#]],
+ );
+ }
+
#[test]
fn search_mode() {
let ra_fixture = r#"
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 (v)
+ 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)
"#]],
);