1 //! Look up accessible paths for items.
3 AsAssocItem, AssocItem, AssocItemContainer, Crate, ItemInNs, ModPath, Module, ModuleDef,
4 PathResolution, PrefixKind, ScopeDef, Semantics, SemanticsScope, Type,
6 use itertools::Itertools;
7 use rustc_hash::FxHashSet;
10 utils::path_to_string_stripping_turbo_fish,
16 items_locator::{self, AssocItemSearch, DEFAULT_QUERY_SEARCH_LIMIT},
20 /// A candidate for import, derived during various IDE activities:
21 /// * completion with imports on the fly proposals
22 /// * completion edit resolve requests
26 pub enum ImportCandidate {
27 /// A path, qualified (`std::collections::HashMap`) or not (`HashMap`).
28 Path(PathImportCandidate),
29 /// A trait associated function (with no self parameter) or an associated constant.
30 /// For 'test_mod::TestEnum::test_function', `ty` is the `test_mod::TestEnum` expression type
31 /// and `name` is the `test_function`
32 TraitAssocItem(TraitImportCandidate),
33 /// A trait method with self parameter.
34 /// For 'test_enum.test_method()', `ty` is the `test_enum` expression type
35 /// and `name` is the `test_method`
36 TraitMethod(TraitImportCandidate),
39 /// A trait import needed for a given associated item access.
40 /// For `some::path::SomeStruct::ASSOC_`, contains the
41 /// type of `some::path::SomeStruct` and `ASSOC_` as the item name.
43 pub struct TraitImportCandidate {
44 /// A type of the item that has the associated item accessed at.
45 pub receiver_ty: Type,
46 /// The associated item name that the trait to import should contain.
47 pub assoc_item_name: NameToImport,
50 /// Path import for a given name, qualified or not.
52 pub struct PathImportCandidate {
53 /// Optional qualifier before name.
54 pub qualifier: Option<FirstSegmentUnresolved>,
55 /// The name the item (struct, trait, enum, etc.) should have.
56 pub name: NameToImport,
59 /// A qualifier that has a first segment and it's unresolved.
61 pub struct FirstSegmentUnresolved {
62 fist_segment: ast::NameRef,
63 full_qualifier: ast::Path,
66 /// A name that will be used during item lookups.
67 #[derive(Debug, Clone)]
68 pub enum NameToImport {
69 /// Requires items with names that exactly match the given string, bool indicates case-sensitivity.
71 /// Requires items with names that case-insensitively contain all letters from the string,
72 /// in the same order, but not necessary adjacent.
77 pub fn exact_case_sensitive(s: String) -> NameToImport {
78 NameToImport::Exact(s, true)
83 pub fn text(&self) -> &str {
85 NameToImport::Exact(text, _) => text.as_str(),
86 NameToImport::Fuzzy(text) => text.as_str(),
91 /// A struct to find imports in the project, given a certain name (or its part) and the context.
93 pub struct ImportAssets {
94 import_candidate: ImportCandidate,
95 candidate_node: SyntaxNode,
96 module_with_candidate: Module,
100 pub fn for_method_call(
101 method_call: &ast::MethodCallExpr,
102 sema: &Semantics<'_, RootDatabase>,
104 let candidate_node = method_call.syntax().clone();
106 import_candidate: ImportCandidate::for_method_call(sema, method_call)?,
107 module_with_candidate: sema.scope(&candidate_node)?.module(),
112 pub fn for_exact_path(
113 fully_qualified_path: &ast::Path,
114 sema: &Semantics<'_, RootDatabase>,
116 let candidate_node = fully_qualified_path.syntax().clone();
117 if let Some(use_tree) = candidate_node.ancestors().find_map(ast::UseTree::cast) {
118 // Path is inside a use tree, then only continue if it is the first segment of a use statement.
119 if use_tree.syntax().parent().and_then(ast::Use::cast).is_none()
120 || fully_qualified_path.qualifier().is_some()
126 import_candidate: ImportCandidate::for_regular_path(sema, fully_qualified_path)?,
127 module_with_candidate: sema.scope(&candidate_node)?.module(),
132 pub fn for_ident_pat(sema: &Semantics<'_, RootDatabase>, pat: &ast::IdentPat) -> Option<Self> {
133 if !pat.is_simple_ident() {
136 let name = pat.name()?;
137 let candidate_node = pat.syntax().clone();
139 import_candidate: ImportCandidate::for_name(sema, &name)?,
140 module_with_candidate: sema.scope(&candidate_node)?.module(),
145 pub fn for_fuzzy_path(
146 module_with_candidate: Module,
147 qualifier: Option<ast::Path>,
149 sema: &Semantics<'_, RootDatabase>,
150 candidate_node: SyntaxNode,
153 import_candidate: ImportCandidate::for_fuzzy_path(qualifier, fuzzy_name, sema)?,
154 module_with_candidate,
159 pub fn for_fuzzy_method_call(
160 module_with_method_call: Module,
162 fuzzy_method_name: String,
163 candidate_node: SyntaxNode,
166 import_candidate: ImportCandidate::TraitMethod(TraitImportCandidate {
168 assoc_item_name: NameToImport::Fuzzy(fuzzy_method_name),
170 module_with_candidate: module_with_method_call,
176 /// An import (not necessary the only one) that corresponds a certain given [`PathImportCandidate`].
177 /// (the structure is not entirely correct, since there can be situations requiring two imports, see FIXME below for the details)
178 #[derive(Debug, Clone, PartialEq, Eq, Hash)]
179 pub struct LocatedImport {
180 /// The path to use in the `use` statement for a given candidate to be imported.
181 pub import_path: ModPath,
182 /// An item that will be imported with the import path given.
183 pub item_to_import: ItemInNs,
184 /// The path import candidate, resolved.
186 /// Not necessary matches the import:
187 /// For any associated constant from the trait, we try to access as `some::path::SomeStruct::ASSOC_`
188 /// the original item is the associated constant, but the import has to be a trait that
189 /// defines this constant.
190 pub original_item: ItemInNs,
191 /// A path of the original item.
192 pub original_path: Option<ModPath>,
197 import_path: ModPath,
198 item_to_import: ItemInNs,
199 original_item: ItemInNs,
200 original_path: Option<ModPath>,
202 Self { import_path, item_to_import, original_item, original_path }
207 pub fn import_candidate(&self) -> &ImportCandidate {
208 &self.import_candidate
211 pub fn search_for_imports(
213 sema: &Semantics<'_, RootDatabase>,
214 prefix_kind: PrefixKind,
216 ) -> Vec<LocatedImport> {
217 let _p = profile::span("import_assets::search_for_imports");
218 self.search_for(sema, Some(prefix_kind), prefer_no_std)
221 /// This may return non-absolute paths if a part of the returned path is already imported into scope.
222 pub fn search_for_relative_paths(
224 sema: &Semantics<'_, RootDatabase>,
226 ) -> Vec<LocatedImport> {
227 let _p = profile::span("import_assets::search_for_relative_paths");
228 self.search_for(sema, None, prefer_no_std)
231 pub fn path_fuzzy_name_to_exact(&mut self, case_sensitive: bool) {
232 if let ImportCandidate::Path(PathImportCandidate { name: to_import, .. }) =
233 &mut self.import_candidate
235 let name = match to_import {
236 NameToImport::Fuzzy(name) => std::mem::take(name),
239 *to_import = NameToImport::Exact(name, case_sensitive);
245 sema: &Semantics<'_, RootDatabase>,
246 prefixed: Option<PrefixKind>,
248 ) -> Vec<LocatedImport> {
249 let _p = profile::span("import_assets::search_for");
251 let scope_definitions = self.scope_definitions(sema);
252 let mod_path = |item| {
255 item_for_path_search(sema.db, item)?,
256 &self.module_with_candidate,
262 let krate = self.module_with_candidate.krate();
263 let scope = match sema.scope(&self.candidate_node) {
265 None => return Vec::new(),
268 match &self.import_candidate {
269 ImportCandidate::Path(path_candidate) => {
270 path_applicable_imports(sema, krate, path_candidate, mod_path)
272 ImportCandidate::TraitAssocItem(trait_candidate) => {
273 trait_applicable_items(sema, krate, &scope, trait_candidate, true, mod_path)
275 ImportCandidate::TraitMethod(trait_candidate) => {
276 trait_applicable_items(sema, krate, &scope, trait_candidate, false, mod_path)
280 .filter(|import| import.import_path.len() > 1)
281 .filter(|import| !scope_definitions.contains(&ScopeDef::from(import.item_to_import)))
282 .sorted_by(|a, b| a.import_path.cmp(&b.import_path))
286 fn scope_definitions(&self, sema: &Semantics<'_, RootDatabase>) -> FxHashSet<ScopeDef> {
287 let _p = profile::span("import_assets::scope_definitions");
288 let mut scope_definitions = FxHashSet::default();
289 if let Some(scope) = sema.scope(&self.candidate_node) {
290 scope.process_all_names(&mut |_, scope_def| {
291 scope_definitions.insert(scope_def);
298 fn path_applicable_imports(
299 sema: &Semantics<'_, RootDatabase>,
300 current_crate: Crate,
301 path_candidate: &PathImportCandidate,
302 mod_path: impl Fn(ItemInNs) -> Option<ModPath> + Copy,
303 ) -> FxHashSet<LocatedImport> {
304 let _p = profile::span("import_assets::path_applicable_imports");
306 match &path_candidate.qualifier {
308 items_locator::items_with_name(
311 path_candidate.name.clone(),
312 // FIXME: we could look up assoc items by the input and propose those in completion,
313 // but that requires more preparation first:
314 // * store non-trait assoc items in import_map to fully enable this lookup
315 // * ensure that does not degrade the performance (benchmark it)
316 // * write more logic to check for corresponding trait presence requirement (we're unable to flyimport multiple item right now)
317 // * improve the associated completion item matching and/or scoring to ensure no noisy completions appear
319 // see also an ignored test under FIXME comment in the qualify_path.rs module
320 AssocItemSearch::Exclude,
321 Some(DEFAULT_QUERY_SEARCH_LIMIT.inner()),
324 let mod_path = mod_path(item)?;
325 Some(LocatedImport::new(mod_path.clone(), item, item, Some(mod_path)))
329 Some(first_segment_unresolved) => {
330 let unresolved_qualifier =
331 path_to_string_stripping_turbo_fish(&first_segment_unresolved.full_qualifier);
332 let unresolved_first_segment = first_segment_unresolved.fist_segment.text();
333 items_locator::items_with_name(
336 path_candidate.name.clone(),
337 AssocItemSearch::Include,
338 Some(DEFAULT_QUERY_SEARCH_LIMIT.inner()),
344 &unresolved_first_segment,
345 &unresolved_qualifier,
356 mod_path: impl Fn(ItemInNs) -> Option<ModPath>,
357 unresolved_first_segment: &str,
358 unresolved_qualifier: &str,
359 original_item: ItemInNs,
360 ) -> Option<LocatedImport> {
361 let _p = profile::span("import_assets::import_for_item");
363 let original_item_candidate = item_for_path_search(db, original_item)?;
364 let import_path_candidate = mod_path(original_item_candidate)?;
365 let import_path_string = import_path_candidate.to_string();
367 let expected_import_end = if item_as_assoc(db, original_item).is_some() {
368 unresolved_qualifier.to_string()
370 format!("{}::{}", unresolved_qualifier, item_name(db, original_item)?)
372 if !import_path_string.contains(unresolved_first_segment)
373 || !import_path_string.ends_with(&expected_import_end)
379 find_import_for_segment(db, original_item_candidate, unresolved_first_segment)?;
380 let trait_item_to_import = item_as_assoc(db, original_item)
381 .and_then(|assoc| assoc.containing_trait(db))
382 .map(|trait_| ItemInNs::from(ModuleDef::from(trait_)));
383 Some(match (segment_import == original_item_candidate, trait_item_to_import) {
385 // FIXME we should be able to import both the trait and the segment,
386 // but it's unclear what to do with overlapping edits (merge imports?)
387 // especially in case of lazy completion edit resolutions.
390 (false, Some(trait_to_import)) => LocatedImport::new(
391 mod_path(trait_to_import)?,
394 mod_path(original_item),
396 (true, None) => LocatedImport::new(
397 import_path_candidate,
398 original_item_candidate,
400 mod_path(original_item),
402 (false, None) => LocatedImport::new(
403 mod_path(segment_import)?,
406 mod_path(original_item),
411 pub fn item_for_path_search(db: &RootDatabase, item: ItemInNs) -> Option<ItemInNs> {
413 ItemInNs::Types(_) | ItemInNs::Values(_) => match item_as_assoc(db, item) {
414 Some(assoc_item) => match assoc_item.container(db) {
415 AssocItemContainer::Trait(trait_) => ItemInNs::from(ModuleDef::from(trait_)),
416 AssocItemContainer::Impl(impl_) => {
417 ItemInNs::from(ModuleDef::from(impl_.self_ty(db).as_adt()?))
422 ItemInNs::Macros(_) => item,
426 fn find_import_for_segment(
428 original_item: ItemInNs,
429 unresolved_first_segment: &str,
430 ) -> Option<ItemInNs> {
431 let segment_is_name = item_name(db, original_item)
432 .map(|name| name.to_smol_str() == unresolved_first_segment)
435 Some(if segment_is_name {
438 let matching_module =
439 module_with_segment_name(db, unresolved_first_segment, original_item)?;
440 ItemInNs::from(ModuleDef::from(matching_module))
444 fn module_with_segment_name(
448 ) -> Option<Module> {
449 let mut current_module = match candidate {
450 ItemInNs::Types(module_def_id) => module_def_id.module(db),
451 ItemInNs::Values(module_def_id) => module_def_id.module(db),
452 ItemInNs::Macros(macro_def_id) => ModuleDef::from(macro_def_id).module(db),
454 while let Some(module) = current_module {
455 if let Some(module_name) = module.name(db) {
456 if module_name.to_smol_str() == segment_name {
460 current_module = module.parent(db);
465 fn trait_applicable_items(
466 sema: &Semantics<'_, RootDatabase>,
467 current_crate: Crate,
468 scope: &SemanticsScope<'_>,
469 trait_candidate: &TraitImportCandidate,
470 trait_assoc_item: bool,
471 mod_path: impl Fn(ItemInNs) -> Option<ModPath>,
472 ) -> FxHashSet<LocatedImport> {
473 let _p = profile::span("import_assets::trait_applicable_items");
477 let inherent_traits = trait_candidate.receiver_ty.applicable_inherent_traits(db);
478 let env_traits = trait_candidate.receiver_ty.env_traits(db);
479 let related_traits = inherent_traits.chain(env_traits).collect::<FxHashSet<_>>();
481 let mut required_assoc_items = FxHashSet::default();
482 let trait_candidates = items_locator::items_with_name(
485 trait_candidate.assoc_item_name.clone(),
486 AssocItemSearch::AssocItemsOnly,
487 Some(DEFAULT_QUERY_SEARCH_LIMIT.inner()),
489 .filter_map(|input| item_as_assoc(db, input))
490 .filter_map(|assoc| {
491 let assoc_item_trait = assoc.containing_trait(db)?;
492 if related_traits.contains(&assoc_item_trait) {
495 required_assoc_items.insert(assoc);
496 Some(assoc_item_trait.into())
501 let mut located_imports = FxHashSet::default();
503 if trait_assoc_item {
504 trait_candidate.receiver_ty.iterate_path_candidates(
511 if required_assoc_items.contains(&assoc) {
512 if let AssocItem::Function(f) = assoc {
513 if f.self_param(db).is_some() {
517 let located_trait = assoc.containing_trait(db)?;
518 let trait_item = ItemInNs::from(ModuleDef::from(located_trait));
519 let original_item = assoc_to_item(assoc);
520 located_imports.insert(LocatedImport::new(
521 mod_path(trait_item)?,
524 mod_path(original_item),
531 trait_candidate.receiver_ty.iterate_method_candidates(
538 let assoc = function.as_assoc_item(db)?;
539 if required_assoc_items.contains(&assoc) {
540 let located_trait = assoc.containing_trait(db)?;
541 let trait_item = ItemInNs::from(ModuleDef::from(located_trait));
542 let original_item = assoc_to_item(assoc);
543 located_imports.insert(LocatedImport::new(
544 mod_path(trait_item)?,
547 mod_path(original_item),
558 fn assoc_to_item(assoc: AssocItem) -> ItemInNs {
560 AssocItem::Function(f) => ItemInNs::from(ModuleDef::from(f)),
561 AssocItem::Const(c) => ItemInNs::from(ModuleDef::from(c)),
562 AssocItem::TypeAlias(t) => ItemInNs::from(ModuleDef::from(t)),
568 item_to_search: ItemInNs,
569 module_with_candidate: &Module,
570 prefixed: Option<PrefixKind>,
572 ) -> Option<ModPath> {
573 if let Some(prefix_kind) = prefixed {
574 module_with_candidate.find_use_path_prefixed(db, item_to_search, prefix_kind, prefer_no_std)
576 module_with_candidate.find_use_path(db, item_to_search, prefer_no_std)
580 impl ImportCandidate {
582 sema: &Semantics<'_, RootDatabase>,
583 method_call: &ast::MethodCallExpr,
585 match sema.resolve_method_call(method_call) {
587 None => Some(Self::TraitMethod(TraitImportCandidate {
588 receiver_ty: sema.type_of_expr(&method_call.receiver()?)?.adjusted(),
589 assoc_item_name: NameToImport::exact_case_sensitive(
590 method_call.name_ref()?.to_string(),
596 fn for_regular_path(sema: &Semantics<'_, RootDatabase>, path: &ast::Path) -> Option<Self> {
597 if sema.resolve_path(path).is_some() {
600 path_import_candidate(
603 NameToImport::exact_case_sensitive(path.segment()?.name_ref()?.to_string()),
607 fn for_name(sema: &Semantics<'_, RootDatabase>, name: &ast::Name) -> Option<Self> {
609 .scope(name.syntax())?
610 .speculative_resolve(&ast::make::ext::ident_path(&name.text()))
615 Some(ImportCandidate::Path(PathImportCandidate {
617 name: NameToImport::exact_case_sensitive(name.to_string()),
622 qualifier: Option<ast::Path>,
624 sema: &Semantics<'_, RootDatabase>,
626 path_import_candidate(sema, qualifier, NameToImport::Fuzzy(fuzzy_name))
630 fn path_import_candidate(
631 sema: &Semantics<'_, RootDatabase>,
632 qualifier: Option<ast::Path>,
634 ) -> Option<ImportCandidate> {
635 Some(match qualifier {
636 Some(qualifier) => match sema.resolve_path(&qualifier) {
638 let qualifier_start =
639 qualifier.syntax().descendants().find_map(ast::NameRef::cast)?;
640 let qualifier_start_path =
641 qualifier_start.syntax().ancestors().find_map(ast::Path::cast)?;
642 if sema.resolve_path(&qualifier_start_path).is_none() {
643 ImportCandidate::Path(PathImportCandidate {
644 qualifier: Some(FirstSegmentUnresolved {
645 fist_segment: qualifier_start,
646 full_qualifier: qualifier,
654 Some(PathResolution::Def(ModuleDef::Adt(assoc_item_path))) => {
655 ImportCandidate::TraitAssocItem(TraitImportCandidate {
656 receiver_ty: assoc_item_path.ty(sema.db),
657 assoc_item_name: name,
660 Some(PathResolution::Def(ModuleDef::TypeAlias(alias))) => {
661 let ty = alias.ty(sema.db);
662 if ty.as_adt().is_some() {
663 ImportCandidate::TraitAssocItem(TraitImportCandidate {
665 assoc_item_name: name,
671 Some(_) => return None,
673 None => ImportCandidate::Path(PathImportCandidate { qualifier: None, name }),
677 fn item_as_assoc(db: &RootDatabase, item: ItemInNs) -> Option<AssocItem> {
678 item.as_module_def().and_then(|module_def| module_def.as_assoc_item(db))