aboutsummaryrefslogtreecommitdiff
path: root/crates/ide_db
diff options
context:
space:
mode:
authorKirill Bulatov <[email protected]>2021-03-20 13:02:52 +0000
committerKirill Bulatov <[email protected]>2021-03-20 20:33:54 +0000
commita631108d2dd0596b079b59efa37b1af00d7555db (patch)
tree14492ac7c646f7ce786a4b62896a18dc6d718342 /crates/ide_db
parent81961dc035106dcfd29b894aae339261a0ba037b (diff)
Do not query item search by name eagerly
Diffstat (limited to 'crates/ide_db')
-rw-r--r--crates/ide_db/src/helpers/import_assets.rs210
-rw-r--r--crates/ide_db/src/items_locator.rs149
2 files changed, 162 insertions, 197 deletions
diff --git a/crates/ide_db/src/helpers/import_assets.rs b/crates/ide_db/src/helpers/import_assets.rs
index dbc980ba9..ae234eddc 100644
--- a/crates/ide_db/src/helpers/import_assets.rs
+++ b/crates/ide_db/src/helpers/import_assets.rs
@@ -61,7 +61,7 @@ pub struct FirstSegmentUnresolved {
61} 61}
62 62
63/// A name that will be used during item lookups. 63/// A name that will be used during item lookups.
64#[derive(Debug)] 64#[derive(Debug, Clone)]
65pub enum NameToImport { 65pub enum NameToImport {
66 /// Requires items with names that exactly match the given string, case-sensitive. 66 /// Requires items with names that exactly match the given string, case-sensitive.
67 Exact(String), 67 Exact(String),
@@ -201,131 +201,96 @@ impl ImportAssets {
201 sema: &Semantics<RootDatabase>, 201 sema: &Semantics<RootDatabase>,
202 prefixed: Option<PrefixKind>, 202 prefixed: Option<PrefixKind>,
203 ) -> Vec<LocatedImport> { 203 ) -> Vec<LocatedImport> {
204 let items_with_candidate_name = match self.name_to_import() { 204 let _p = profile::span("import_assets::search_for");
205 NameToImport::Exact(exact_name) => items_locator::with_exact_name(
206 sema,
207 self.module_with_candidate.krate(),
208 exact_name.clone(),
209 ),
210 // FIXME: ideally, we should avoid using `fst` for seacrhing trait imports for assoc items:
211 // instead, we need to look up all trait impls for a certain struct and search through them only
212 // see https://github.com/rust-analyzer/rust-analyzer/pull/7293#issuecomment-761585032
213 // and https://rust-lang.zulipchat.com/#narrow/stream/185405-t-compiler.2Fwg-rls-2.2E0/topic/Blanket.20trait.20impls.20lookup
214 // for the details
215 NameToImport::Fuzzy(fuzzy_name) => {
216 let (assoc_item_search, limit) = if self.import_candidate.is_trait_candidate() {
217 (AssocItemSearch::AssocItemsOnly, None)
218 } else {
219 (AssocItemSearch::Include, Some(DEFAULT_QUERY_SEARCH_LIMIT))
220 };
221
222 items_locator::with_similar_name(
223 sema,
224 self.module_with_candidate.krate(),
225 fuzzy_name.clone(),
226 assoc_item_search,
227 limit,
228 )
229 }
230 };
231 205
232 let scope_definitions = self.scope_definitions(sema); 206 let scope_definitions = self.scope_definitions(sema);
233 self.applicable_defs(sema.db, prefixed, items_with_candidate_name)
234 .into_iter()
235 .filter(|import| import.import_path.len() > 1)
236 .filter(|import| !scope_definitions.contains(&ScopeDef::from(import.item_to_import)))
237 .sorted_by_key(|import| import.import_path.clone())
238 .collect()
239 }
240
241 fn scope_definitions(&self, sema: &Semantics<RootDatabase>) -> FxHashSet<ScopeDef> {
242 let mut scope_definitions = FxHashSet::default();
243 sema.scope(&self.candidate_node).process_all_names(&mut |_, scope_def| {
244 scope_definitions.insert(scope_def);
245 });
246 scope_definitions
247 }
248
249 fn name_to_import(&self) -> &NameToImport {
250 match &self.import_candidate {
251 ImportCandidate::Path(candidate) => &candidate.name,
252 ImportCandidate::TraitAssocItem(candidate)
253 | ImportCandidate::TraitMethod(candidate) => &candidate.assoc_item_name,
254 }
255 }
256
257 fn applicable_defs(
258 &self,
259 db: &RootDatabase,
260 prefixed: Option<PrefixKind>,
261 items_with_candidate_name: FxHashSet<ItemInNs>,
262 ) -> FxHashSet<LocatedImport> {
263 let _p = profile::span("import_assets::applicable_defs");
264 let current_crate = self.module_with_candidate.krate(); 207 let current_crate = self.module_with_candidate.krate();
265
266 let mod_path = |item| { 208 let mod_path = |item| {
267 get_mod_path(db, item_for_path_search(db, item)?, &self.module_with_candidate, prefixed) 209 get_mod_path(
210 sema.db,
211 item_for_path_search(sema.db, item)?,
212 &self.module_with_candidate,
213 prefixed,
214 )
268 }; 215 };
269 216
270 match &self.import_candidate { 217 match &self.import_candidate {
271 ImportCandidate::Path(path_candidate) => { 218 ImportCandidate::Path(path_candidate) => {
272 path_applicable_imports(db, path_candidate, mod_path, items_with_candidate_name) 219 path_applicable_imports(sema, current_crate, path_candidate, mod_path)
220 }
221 ImportCandidate::TraitAssocItem(trait_candidate) => {
222 trait_applicable_items(sema, current_crate, trait_candidate, true, mod_path)
223 }
224 ImportCandidate::TraitMethod(trait_candidate) => {
225 trait_applicable_items(sema, current_crate, trait_candidate, false, mod_path)
273 } 226 }
274 ImportCandidate::TraitAssocItem(trait_candidate) => trait_applicable_items(
275 db,
276 current_crate,
277 trait_candidate,
278 true,
279 mod_path,
280 items_with_candidate_name,
281 ),
282 ImportCandidate::TraitMethod(trait_candidate) => trait_applicable_items(
283 db,
284 current_crate,
285 trait_candidate,
286 false,
287 mod_path,
288 items_with_candidate_name,
289 ),
290 } 227 }
228 .into_iter()
229 .filter(|import| import.import_path.len() > 1)
230 .filter(|import| !scope_definitions.contains(&ScopeDef::from(import.item_to_import)))
231 .sorted_by_key(|import| import.import_path.clone())
232 .collect()
233 }
234
235 fn scope_definitions(&self, sema: &Semantics<RootDatabase>) -> FxHashSet<ScopeDef> {
236 let _p = profile::span("import_assets::scope_definitions");
237 let mut scope_definitions = FxHashSet::default();
238 sema.scope(&self.candidate_node).process_all_names(&mut |_, scope_def| {
239 scope_definitions.insert(scope_def);
240 });
241 scope_definitions
291 } 242 }
292} 243}
293 244
294fn path_applicable_imports( 245fn path_applicable_imports(
295 db: &RootDatabase, 246 sema: &Semantics<RootDatabase>,
247 current_crate: Crate,
296 path_candidate: &PathImportCandidate, 248 path_candidate: &PathImportCandidate,
297 mod_path: impl Fn(ItemInNs) -> Option<ModPath> + Copy, 249 mod_path: impl Fn(ItemInNs) -> Option<ModPath> + Copy,
298 items_with_candidate_name: FxHashSet<ItemInNs>,
299) -> FxHashSet<LocatedImport> { 250) -> FxHashSet<LocatedImport> {
300 let _p = profile::span("import_assets::path_applicable_imports"); 251 let _p = profile::span("import_assets::path_applicable_imports");
301 252
302 let (unresolved_first_segment, unresolved_qualifier) = match &path_candidate.qualifier { 253 match &path_candidate.qualifier {
303 None => { 254 None => {
304 return items_with_candidate_name 255 items_locator::locate_for_name(
305 .into_iter() 256 sema,
306 .filter_map(|item| { 257 current_crate,
307 if item_as_assoc(db, item).is_some() { 258 path_candidate.name.clone(),
308 // unqualified assoc items are not valid syntax 259 // unqualified assoc items are not valid syntax
309 return None; 260 AssocItemSearch::Exclude,
310 } 261 Some(DEFAULT_QUERY_SEARCH_LIMIT),
311 262 )
312 let mod_path = mod_path(item)?; 263 .into_iter()
313 Some(LocatedImport::new(mod_path.clone(), item, item, Some(mod_path))) 264 .filter_map(|item| {
314 }) 265 let mod_path = mod_path(item)?;
315 .collect(); 266 Some(LocatedImport::new(mod_path.clone(), item, item, Some(mod_path)))
267 })
268 .collect()
316 } 269 }
317 Some(first_segment_unresolved) => ( 270 Some(first_segment_unresolved) => {
318 first_segment_unresolved.fist_segment.to_string(), 271 let unresolved_qualifier =
319 path_to_string_stripping_turbo_fish(&first_segment_unresolved.full_qualifier), 272 path_to_string_stripping_turbo_fish(&first_segment_unresolved.full_qualifier);
320 ), 273 let unresolved_first_segment = first_segment_unresolved.fist_segment.text();
321 }; 274 items_locator::locate_for_name(
322 275 sema,
323 items_with_candidate_name 276 current_crate,
324 .into_iter() 277 path_candidate.name.clone(),
325 .filter_map(|item| { 278 AssocItemSearch::Include,
326 import_for_item(db, mod_path, &unresolved_first_segment, &unresolved_qualifier, item) 279 Some(DEFAULT_QUERY_SEARCH_LIMIT),
327 }) 280 )
328 .collect() 281 .into_iter()
282 .filter_map(|item| {
283 import_for_item(
284 sema.db,
285 mod_path,
286 unresolved_first_segment,
287 &unresolved_qualifier,
288 item,
289 )
290 })
291 .collect()
292 }
293 }
329} 294}
330 295
331fn import_for_item( 296fn import_for_item(
@@ -440,25 +405,32 @@ fn module_with_segment_name(
440} 405}
441 406
442fn trait_applicable_items( 407fn trait_applicable_items(
443 db: &RootDatabase, 408 sema: &Semantics<RootDatabase>,
444 current_crate: Crate, 409 current_crate: Crate,
445 trait_candidate: &TraitImportCandidate, 410 trait_candidate: &TraitImportCandidate,
446 trait_assoc_item: bool, 411 trait_assoc_item: bool,
447 mod_path: impl Fn(ItemInNs) -> Option<ModPath>, 412 mod_path: impl Fn(ItemInNs) -> Option<ModPath>,
448 items_with_candidate_name: FxHashSet<ItemInNs>,
449) -> FxHashSet<LocatedImport> { 413) -> FxHashSet<LocatedImport> {
450 let _p = profile::span("import_assets::trait_applicable_items"); 414 let _p = profile::span("import_assets::trait_applicable_items");
451 let mut required_assoc_items = FxHashSet::default();
452 415
453 let trait_candidates = items_with_candidate_name 416 let db = sema.db;
454 .into_iter() 417
455 .filter_map(|input| item_as_assoc(db, input)) 418 let mut required_assoc_items = FxHashSet::default();
456 .filter_map(|assoc| { 419 let trait_candidates = items_locator::locate_for_name(
457 let assoc_item_trait = assoc.containing_trait(db)?; 420 sema,
458 required_assoc_items.insert(assoc); 421 current_crate,
459 Some(assoc_item_trait.into()) 422 trait_candidate.assoc_item_name.clone(),
460 }) 423 AssocItemSearch::AssocItemsOnly,
461 .collect(); 424 Some(DEFAULT_QUERY_SEARCH_LIMIT),
425 )
426 .into_iter()
427 .filter_map(|input| item_as_assoc(db, input))
428 .filter_map(|assoc| {
429 let assoc_item_trait = assoc.containing_trait(db)?;
430 required_assoc_items.insert(assoc);
431 Some(assoc_item_trait.into())
432 })
433 .collect();
462 434
463 let mut located_imports = FxHashSet::default(); 435 let mut located_imports = FxHashSet::default();
464 436
@@ -567,10 +539,6 @@ impl ImportCandidate {
567 ) -> Option<Self> { 539 ) -> Option<Self> {
568 path_import_candidate(sema, qualifier, NameToImport::Fuzzy(fuzzy_name)) 540 path_import_candidate(sema, qualifier, NameToImport::Fuzzy(fuzzy_name))
569 } 541 }
570
571 fn is_trait_candidate(&self) -> bool {
572 matches!(self, ImportCandidate::TraitAssocItem(_) | ImportCandidate::TraitMethod(_))
573 }
574} 542}
575 543
576fn path_import_candidate( 544fn path_import_candidate(
diff --git a/crates/ide_db/src/items_locator.rs b/crates/ide_db/src/items_locator.rs
index 8a7f02935..088be72c4 100644
--- a/crates/ide_db/src/items_locator.rs
+++ b/crates/ide_db/src/items_locator.rs
@@ -10,6 +10,7 @@ use syntax::{ast, AstNode, SyntaxKind::NAME};
10 10
11use crate::{ 11use crate::{
12 defs::{Definition, NameClass}, 12 defs::{Definition, NameClass},
13 helpers::import_assets::NameToImport,
13 symbol_index::{self, FileSymbol}, 14 symbol_index::{self, FileSymbol},
14 RootDatabase, 15 RootDatabase,
15}; 16};
@@ -17,115 +18,105 @@ use rustc_hash::FxHashSet;
17 18
18pub(crate) const DEFAULT_QUERY_SEARCH_LIMIT: usize = 40; 19pub(crate) const DEFAULT_QUERY_SEARCH_LIMIT: usize = 40;
19 20
20pub fn with_exact_name( 21/// TODO kb docs here and around + update the module doc
21 sema: &Semantics<'_, RootDatabase>, 22#[derive(Debug, Clone, Copy)]
22 krate: Crate,
23 exact_name: String,
24) -> FxHashSet<ItemInNs> {
25 let _p = profile::span("find_exact_imports");
26 find_items(
27 sema,
28 krate,
29 {
30 let mut local_query = symbol_index::Query::new(exact_name.clone());
31 local_query.exact();
32 local_query.limit(DEFAULT_QUERY_SEARCH_LIMIT);
33 local_query
34 },
35 import_map::Query::new(exact_name)
36 .limit(DEFAULT_QUERY_SEARCH_LIMIT)
37 .name_only()
38 .search_mode(import_map::SearchMode::Equals)
39 .case_sensitive(),
40 )
41}
42
43#[derive(Debug)]
44pub enum AssocItemSearch { 23pub enum AssocItemSearch {
45 Include, 24 Include,
46 Exclude, 25 Exclude,
47 AssocItemsOnly, 26 AssocItemsOnly,
48} 27}
49 28
50pub fn with_similar_name( 29pub fn locate_for_name(
51 sema: &Semantics<'_, RootDatabase>, 30 sema: &Semantics<'_, RootDatabase>,
52 krate: Crate, 31 krate: Crate,
53 fuzzy_search_string: String, 32 name: NameToImport,
54 assoc_item_search: AssocItemSearch, 33 assoc_item_search: AssocItemSearch,
55 limit: Option<usize>, 34 limit: Option<usize>,
56) -> FxHashSet<ItemInNs> { 35) -> FxHashSet<ItemInNs> {
57 let _p = profile::span("find_similar_imports"); 36 let _p = profile::span("locate_for_name").detail(|| {
37 format!(
38 "Name: {} ({:?}), crate: {:?}, limit: {:?}",
39 name.text(),
40 assoc_item_search,
41 krate.display_name(sema.db).map(|name| name.to_string()),
42 limit,
43 )
44 });
45
46 let (mut local_query, mut external_query) = match name {
47 NameToImport::Exact(exact_name) => {
48 let mut local_query = symbol_index::Query::new(exact_name.clone());
49 local_query.exact();
58 50
59 let mut external_query = import_map::Query::new(fuzzy_search_string.clone()) 51 let external_query = import_map::Query::new(exact_name)
60 .search_mode(import_map::SearchMode::Fuzzy) 52 .name_only()
61 .name_only(); 53 .search_mode(import_map::SearchMode::Equals)
54 .case_sensitive();
62 55
63 match assoc_item_search { 56 (local_query, external_query)
64 AssocItemSearch::Include => {}
65 AssocItemSearch::Exclude => {
66 external_query = external_query.exclude_import_kind(ImportKind::AssociatedItem);
67 } 57 }
68 AssocItemSearch::AssocItemsOnly => { 58 NameToImport::Fuzzy(fuzzy_search_string) => {
69 external_query = external_query.assoc_items_only(); 59 let mut external_query = import_map::Query::new(fuzzy_search_string.clone())
60 .search_mode(import_map::SearchMode::Fuzzy)
61 .name_only();
62 match assoc_item_search {
63 AssocItemSearch::Include => {}
64 AssocItemSearch::Exclude => {
65 external_query = external_query.exclude_import_kind(ImportKind::AssociatedItem);
66 }
67 AssocItemSearch::AssocItemsOnly => {
68 external_query = external_query.assoc_items_only();
69 }
70 }
71
72 (symbol_index::Query::new(fuzzy_search_string), external_query)
70 } 73 }
71 } 74 };
72
73 let mut local_query = symbol_index::Query::new(fuzzy_search_string);
74 75
75 if let Some(limit) = limit { 76 if let Some(limit) = limit {
76 external_query = external_query.limit(limit); 77 external_query = external_query.limit(limit);
77 local_query.limit(limit); 78 local_query.limit(limit);
78 } 79 }
79 80
80 find_items(sema, krate, local_query, external_query) 81 find_items(sema, krate, assoc_item_search, local_query, external_query)
81 .into_iter()
82 .filter(move |&item| match assoc_item_search {
83 AssocItemSearch::Include => true,
84 AssocItemSearch::Exclude => !is_assoc_item(item, sema.db),
85 AssocItemSearch::AssocItemsOnly => is_assoc_item(item, sema.db),
86 })
87 .collect()
88}
89
90fn is_assoc_item(item: ItemInNs, db: &RootDatabase) -> bool {
91 item.as_module_def_id()
92 .and_then(|module_def_id| ModuleDef::from(module_def_id).as_assoc_item(db))
93 .is_some()
94} 82}
95 83
96fn find_items( 84fn find_items(
97 sema: &Semantics<'_, RootDatabase>, 85 sema: &Semantics<'_, RootDatabase>,
98 krate: Crate, 86 krate: Crate,
87 assoc_item_search: AssocItemSearch,
99 local_query: symbol_index::Query, 88 local_query: symbol_index::Query,
100 external_query: import_map::Query, 89 external_query: import_map::Query,
101) -> FxHashSet<ItemInNs> { 90) -> FxHashSet<ItemInNs> {
102 let _p = profile::span("find_similar_imports"); 91 let _p = profile::span("find_items");
103 let db = sema.db; 92 let db = sema.db;
104 93
105 // Query dependencies first. 94 let external_importables =
106 let mut candidates = krate 95 krate.query_external_importables(db, external_query).map(|external_importable| {
107 .query_external_importables(db, external_query) 96 match external_importable {
108 .map(|external_importable| match external_importable { 97 Either::Left(module_def) => ItemInNs::from(module_def),
109 Either::Left(module_def) => ItemInNs::from(module_def), 98 Either::Right(macro_def) => ItemInNs::from(macro_def),
110 Either::Right(macro_def) => ItemInNs::from(macro_def), 99 }
111 }) 100 });
112 .collect::<FxHashSet<_>>();
113 101
114 // Query the local crate using the symbol index. 102 // Query the local crate using the symbol index.
115 let local_results = symbol_index::crate_symbols(db, krate.into(), local_query); 103 let local_results = symbol_index::crate_symbols(db, krate.into(), local_query)
116 104 .into_iter()
117 candidates.extend( 105 .filter_map(|local_candidate| get_name_definition(sema, &local_candidate))
118 local_results 106 .filter_map(|name_definition_to_import| match name_definition_to_import {
119 .into_iter() 107 Definition::ModuleDef(module_def) => Some(ItemInNs::from(module_def)),
120 .filter_map(|local_candidate| get_name_definition(sema, &local_candidate)) 108 Definition::Macro(macro_def) => Some(ItemInNs::from(macro_def)),
121 .filter_map(|name_definition_to_import| match name_definition_to_import { 109 _ => None,
122 Definition::ModuleDef(module_def) => Some(ItemInNs::from(module_def)), 110 });
123 Definition::Macro(macro_def) => Some(ItemInNs::from(macro_def)), 111
124 _ => None, 112 external_importables
125 }), 113 .chain(local_results)
126 ); 114 .filter(move |&item| match assoc_item_search {
127 115 AssocItemSearch::Include => true,
128 candidates 116 AssocItemSearch::Exclude => !is_assoc_item(item, sema.db),
117 AssocItemSearch::AssocItemsOnly => is_assoc_item(item, sema.db),
118 })
119 .collect()
129} 120}
130 121
131fn get_name_definition( 122fn get_name_definition(
@@ -144,3 +135,9 @@ fn get_name_definition(
144 let name = ast::Name::cast(candidate_name_node)?; 135 let name = ast::Name::cast(candidate_name_node)?;
145 NameClass::classify(sema, &name)?.defined(sema.db) 136 NameClass::classify(sema, &name)?.defined(sema.db)
146} 137}
138
139fn is_assoc_item(item: ItemInNs, db: &RootDatabase) -> bool {
140 item.as_module_def_id()
141 .and_then(|module_def_id| ModuleDef::from(module_def_id).as_assoc_item(db))
142 .is_some()
143}