9 files changed, 203 insertions, 93 deletions

diff --git a/crates/completion/src/completions/unqualified_path.rs b/crates/completion/src/completions/unqualified_path.rs
index 81691cd7f..4e4e2b36f 100644
--- a/crates/completion/src/completions/unqualified_path.rs
+++ b/crates/completion/src/completions/unqualified_path.rs
@@ -9,7 +9,7 @@ use test_utils::mark;
 
 use crate::{
     render::{render_resolution_with_import, RenderContext},
-    CompletionContext, Completions,
+    CompletionContext, Completions, ImportEdit,
 };
 
 pub(crate) fn complete_unqualified_path(acc: &mut Completions, ctx: &CompletionContext) {
@@ -44,7 +44,7 @@ pub(crate) fn complete_unqualified_path(acc: &mut Completions, ctx: &CompletionC
         acc.add_resolution(ctx, name.to_string(), &res)
     });
 
-    if ctx.config.enable_experimental_completions {
+    if ctx.config.enable_autoimport_completions && ctx.config.resolve_additional_edits_lazily() {
         fuzzy_completion(acc, ctx).unwrap_or_default()
     }
 }
@@ -73,19 +73,64 @@ fn complete_enum_variants(acc: &mut Completions, ctx: &CompletionContext, ty: &T
     }
 }
 
+// Feature: Fuzzy Completion and Autoimports
+//
+// When completing names in the current scope, proposes additional imports from other modules or crates,
+// if they can be qualified in the scope and their name contains all symbols from the completion input
+// (case-insensitive, in any order or places).
+//
+// ```
+// fn main() {
+//     pda<|>
+// }
+// # pub mod std { pub mod marker { pub struct PhantomData { } } }
+// ```
+// ->
+// ```
+// use std::marker::PhantomData;
+//
+// fn main() {
+//     PhantomData
+// }
+// # pub mod std { pub mod marker { pub struct PhantomData { } } }
+// ```
+//
+// .Fuzzy search details
+//
+// To avoid an excessive amount of the results returned, completion input is checked for inclusion in the identifiers only
+// (i.e. in `HashMap` in the `std::collections::HashMap` path), also not in the module indentifiers.
+//
+// .Merge Behaviour
+//
+// It is possible to configure how use-trees are merged with the `importMergeBehaviour` setting.
+// Mimics the corresponding behaviour of the `Auto Import` feature.
+//
+// .LSP and performance implications
+//
+// The feature is enabled only if the LSP client supports LSP protocol version 3.16+ and reports the `additionalTextEdits`
+// (case sensitive) resolve client capability in its client capabilities.
+// This way the server is able to defer the costly computations, doing them for a selected completion item only.
+// For clients with no such support, all edits have to be calculated on the completion request, including the fuzzy search completion ones,
+// which might be slow ergo the feature is automatically disabled.
+//
+// .Feature toggle
+//
+// The feature can be forcefully turned off in the settings with the `rust-analyzer.completion.enableAutoimportCompletions` flag.
+// Note that having this flag set to `true` does not guarantee that the feature is enabled: your client needs to have the corredponding
+// capability enabled.
 fn fuzzy_completion(acc: &mut Completions, ctx: &CompletionContext) -> Option<()> {
     let _p = profile::span("fuzzy_completion");
+    let potential_import_name = ctx.token.to_string();
+
     let current_module = ctx.scope.module()?;
     let anchor = ctx.name_ref_syntax.as_ref()?;
     let import_scope = ImportScope::find_insert_use_container(anchor.syntax(), &ctx.sema)?;
 
-    let potential_import_name = ctx.token.to_string();
-
     let possible_imports = imports_locator::find_similar_imports(
         &ctx.sema,
         ctx.krate?,
+        Some(100),
         &potential_import_name,
-        50,
         true,
     )
     .filter_map(|import_candidate| {
@@ -99,13 +144,14 @@ fn fuzzy_completion(acc: &mut Completions, ctx: &CompletionContext) -> Option<()
         })
     })
     .filter(|(mod_path, _)| mod_path.len() > 1)
-    .take(20)
     .filter_map(|(import_path, definition)| {
         render_resolution_with_import(
             RenderContext::new(ctx),
-            import_path.clone(),
-            import_scope.clone(),
-            ctx.config.merge,
+            ImportEdit {
+                import_path: import_path.clone(),
+                import_scope: import_scope.clone(),
+                merge_behaviour: ctx.config.merge,
+            },
             &definition,
         )
     });
@@ -120,8 +166,8 @@ mod tests {
     use test_utils::mark;
 
     use crate::{
-        test_utils::{check_edit, completion_list},
-        CompletionKind,
+        test_utils::{check_edit, check_edit_with_config, completion_list},
+        CompletionConfig, CompletionKind,
     };
 
     fn check(ra_fixture: &str, expect: Expect) {
@@ -730,7 +776,13 @@ impl My<|>
 
     #[test]
     fn function_fuzzy_completion() {
-        check_edit(
+        let mut completion_config = CompletionConfig::default();
+        completion_config
+            .active_resolve_capabilities
+            .insert(crate::CompletionResolveCapability::AdditionalTextEdits);
+
+        check_edit_with_config(
+            completion_config,
             "stdin",
             r#"
 //- /lib.rs crate:dep
@@ -755,7 +807,13 @@ fn main() {
 
     #[test]
     fn macro_fuzzy_completion() {
-        check_edit(
+        let mut completion_config = CompletionConfig::default();
+        completion_config
+            .active_resolve_capabilities
+            .insert(crate::CompletionResolveCapability::AdditionalTextEdits);
+
+        check_edit_with_config(
+            completion_config,
             "macro_with_curlies!",
             r#"
 //- /lib.rs crate:dep
@@ -782,7 +840,13 @@ fn main() {
 
     #[test]
     fn struct_fuzzy_completion() {
-        check_edit(
+        let mut completion_config = CompletionConfig::default();
+        completion_config
+            .active_resolve_capabilities
+            .insert(crate::CompletionResolveCapability::AdditionalTextEdits);
+
+        check_edit_with_config(
+            completion_config,
             "ThirdStruct",
             r#"
 //- /lib.rs crate:dep
diff --git a/crates/completion/src/config.rs b/crates/completion/src/config.rs
index 654a76f7b..5175b9d69 100644
--- a/crates/completion/src/config.rs
+++ b/crates/completion/src/config.rs
@@ -5,21 +5,42 @@
 //! completions if we are allowed to.
 
 use ide_db::helpers::insert_use::MergeBehaviour;
+use rustc_hash::FxHashSet;
 
 #[derive(Clone, Debug, PartialEq, Eq)]
 pub struct CompletionConfig {
     pub enable_postfix_completions: bool,
-    pub enable_experimental_completions: bool,
+    pub enable_autoimport_completions: bool,
     pub add_call_parenthesis: bool,
     pub add_call_argument_snippets: bool,
     pub snippet_cap: Option<SnippetCap>,
     pub merge: Option<MergeBehaviour>,
+    /// A set of capabilities, enabled on the client and supported on the server.
+    pub active_resolve_capabilities: FxHashSet<CompletionResolveCapability>,
+}
+
+/// A resolve capability, supported on the server.
+/// If the client registers any completion resolve capabilities,
+/// the server is able to render completion items' corresponding fields later,
+/// not during an initial completion item request.
+/// See https://github.com/rust-analyzer/rust-analyzer/issues/6366 for more details.
+#[derive(Debug, Copy, Clone, Hash, Eq, PartialEq)]
+pub enum CompletionResolveCapability {
+    Documentation,
+    Detail,
+    AdditionalTextEdits,
 }
 
 impl CompletionConfig {
     pub fn allow_snippets(&mut self, yes: bool) {
         self.snippet_cap = if yes { Some(SnippetCap { _private: () }) } else { None }
     }
+
+    /// Whether the completions' additional edits are calculated when sending an initional completions list
+    /// or later, in a separate resolve request.
+    pub fn resolve_additional_edits_lazily(&self) -> bool {
+        self.active_resolve_capabilities.contains(&CompletionResolveCapability::AdditionalTextEdits)
+    }
 }
 
 #[derive(Clone, Copy, Debug, PartialEq, Eq)]
@@ -31,11 +52,12 @@ impl Default for CompletionConfig {
     fn default() -> Self {
         CompletionConfig {
             enable_postfix_completions: true,
-            enable_experimental_completions: true,
+            enable_autoimport_completions: true,
             add_call_parenthesis: true,
             add_call_argument_snippets: true,
             snippet_cap: Some(SnippetCap { _private: () }),
             merge: Some(MergeBehaviour::Full),
+            active_resolve_capabilities: FxHashSet::default(),
         }
     }
 }
diff --git a/crates/completion/src/item.rs b/crates/completion/src/item.rs
index e85549fef..bd94402d7 100644
--- a/crates/completion/src/item.rs
+++ b/crates/completion/src/item.rs
@@ -15,6 +15,7 @@ use crate::config::SnippetCap;
 /// `CompletionItem` describes a single completion variant in the editor pop-up.
 /// It is basically a POD with various properties. To construct a
 /// `CompletionItem`, use `new` method and the `Builder` struct.
+#[derive(Clone)]
 pub struct CompletionItem {
     /// Used only internally in tests, to check only specific kind of
     /// completion (postfix, keyword, reference, etc).
@@ -65,6 +66,9 @@ pub struct CompletionItem {
     /// Indicates that a reference or mutable reference to this variable is a
     /// possible match.
     ref_match: Option<(Mutability, CompletionScore)>,
+
+    /// The import data to add to completion's edits.
+    import_to_add: Option<ImportEdit>,
 }
 
 // We use custom debug for CompletionItem to make snapshot tests more readable.
@@ -256,14 +260,37 @@ impl CompletionItem {
     pub fn ref_match(&self) -> Option<(Mutability, CompletionScore)> {
         self.ref_match
     }
+
+    pub fn import_to_add(&self) -> Option<&ImportEdit> {
+        self.import_to_add.as_ref()
+    }
 }
 
 /// An extra import to add after the completion is applied.
-#[derive(Clone)]
-pub(crate) struct ImportToAdd {
-    pub(crate) import_path: ModPath,
-    pub(crate) import_scope: ImportScope,
-    pub(crate) merge_behaviour: Option<MergeBehaviour>,
+#[derive(Debug, Clone)]
+pub struct ImportEdit {
+    pub import_path: ModPath,
+    pub import_scope: ImportScope,
+    pub merge_behaviour: Option<MergeBehaviour>,
+}
+
+impl ImportEdit {
+    /// Attempts to insert the import to the given scope, producing a text edit.
+    /// May return no edit in edge cases, such as scope already containing the import.
+    pub fn to_text_edit(&self) -> Option<TextEdit> {
+        let _p = profile::span("ImportEdit::to_text_edit");
+
+        let rewriter = insert_use::insert_use(
+            &self.import_scope,
+            mod_path_to_ast(&self.import_path),
+            self.merge_behaviour,
+        );
+        let old_ast = rewriter.rewrite_root()?;
+        let mut import_insert = TextEdit::builder();
+        algo::diff(&old_ast, &rewriter.rewrite(&old_ast)).into_text_edit(&mut import_insert);
+
+        Some(import_insert.finish())
+    }
 }
 
 /// A helper to make `CompletionItem`s.
@@ -272,7 +299,7 @@ pub(crate) struct ImportToAdd {
 pub(crate) struct Builder {
     source_range: TextRange,
     completion_kind: CompletionKind,
-    import_to_add: Option<ImportToAdd>,
+    import_to_add: Option<ImportEdit>,
     label: String,
     insert_text: Option<String>,
     insert_text_format: InsertTextFormat,
@@ -294,11 +321,9 @@ impl Builder {
         let mut label = self.label;
         let mut lookup = self.lookup;
         let mut insert_text = self.insert_text;
-        let mut text_edits = TextEdit::builder();
 
-        if let Some(import_data) = self.import_to_add {
-            let import = mod_path_to_ast(&import_data.import_path);
-            let mut import_path_without_last_segment = import_data.import_path;
+        if let Some(import_to_add) = self.import_to_add.as_ref() {
+            let mut import_path_without_last_segment = import_to_add.import_path.to_owned();
             let _ = import_path_without_last_segment.segments.pop();
 
             if !import_path_without_last_segment.segments.is_empty() {
@@ -310,32 +335,20 @@ impl Builder {
                 }
                 label = format!("{}::{}", import_path_without_last_segment, label);
             }
-
-            let rewriter = insert_use::insert_use(
-                &import_data.import_scope,
-                import,
-                import_data.merge_behaviour,
-            );
-            if let Some(old_ast) = rewriter.rewrite_root() {
-                algo::diff(&old_ast, &rewriter.rewrite(&old_ast)).into_text_edit(&mut text_edits);
-            }
         }
 
-        let original_edit = match self.text_edit {
+        let text_edit = match self.text_edit {
             Some(it) => it,
             None => {
                 TextEdit::replace(self.source_range, insert_text.unwrap_or_else(|| label.clone()))
             }
         };
 
-        let mut resulting_edit = text_edits.finish();
-        resulting_edit.union(original_edit).expect("Failed to unite text edits");
-
         CompletionItem {
             source_range: self.source_range,
             label,
             insert_text_format: self.insert_text_format,
-            text_edit: resulting_edit,
+            text_edit,
             detail: self.detail,
             documentation: self.documentation,
             lookup,
@@ -345,6 +358,7 @@ impl Builder {
             trigger_call_info: self.trigger_call_info.unwrap_or(false),
             score: self.score,
             ref_match: self.ref_match,
+            import_to_add: self.import_to_add,
         }
     }
     pub(crate) fn lookup_by(mut self, lookup: impl Into<String>) -> Builder {
@@ -407,7 +421,7 @@ impl Builder {
         self.trigger_call_info = Some(true);
         self
     }
-    pub(crate) fn add_import(mut self, import_to_add: Option<ImportToAdd>) -> Builder {
+    pub(crate) fn add_import(mut self, import_to_add: Option<ImportEdit>) -> Builder {
         self.import_to_add = import_to_add;
         self
     }
diff --git a/crates/completion/src/lib.rs b/crates/completion/src/lib.rs
index 1ec2e9be7..f60f87243 100644
--- a/crates/completion/src/lib.rs
+++ b/crates/completion/src/lib.rs
@@ -11,14 +11,17 @@ mod render;
 
 mod completions;
 
-use ide_db::base_db::FilePosition;
-use ide_db::RootDatabase;
+use ide_db::{
+    base_db::FilePosition, helpers::insert_use::ImportScope, imports_locator, RootDatabase,
+};
+use syntax::AstNode;
+use text_edit::TextEdit;
 
 use crate::{completions::Completions, context::CompletionContext, item::CompletionKind};
 
 pub use crate::{
-    config::CompletionConfig,
-    item::{CompletionItem, CompletionItemKind, CompletionScore, InsertTextFormat},
+    config::{CompletionConfig, CompletionResolveCapability},
+    item::{CompletionItem, CompletionItemKind, CompletionScore, ImportEdit, InsertTextFormat},
 };
 
 //FIXME: split the following feature into fine-grained features.
@@ -70,12 +73,9 @@ pub use crate::{
 // }
 // ```
 //
-// And experimental completions, enabled with the `rust-analyzer.completion.enableExperimental` setting.
-// This flag enables or disables:
-//
-// - Auto import: additional completion options with automatic `use` import and options from all project importable items, matched for the input
-//
-// Experimental completions might cause issues with performance and completion list look.
+// And the auto import completions, enabled with the `rust-analyzer.completion.autoimport.enable` setting and the corresponding LSP client capabilities.
+// Those are the additional completion options with automatic `use` import and options from all project importable items,
+// fuzzy matched agains the completion imput.
 
 /// Main entry point for completion. We run completion as a two-phase process.
 ///
@@ -131,6 +131,33 @@ pub fn completions(
     Some(acc)
 }
 
+/// Resolves additional completion data at the position given.
+pub fn resolve_completion_edits(
+    db: &RootDatabase,
+    config: &CompletionConfig,
+    position: FilePosition,
+    full_import_path: &str,
+    imported_name: &str,
+) -> Option<Vec<TextEdit>> {
+    let ctx = CompletionContext::new(db, position, config)?;
+    let anchor = ctx.name_ref_syntax.as_ref()?;
+    let import_scope = ImportScope::find_insert_use_container(anchor.syntax(), &ctx.sema)?;
+
+    let current_module = ctx.sema.scope(anchor.syntax()).module()?;
+    let current_crate = current_module.krate();
+
+    let import_path = imports_locator::find_exact_imports(&ctx.sema, current_crate, imported_name)
+        .filter_map(|candidate| {
+            let item: hir::ItemInNs = candidate.either(Into::into, Into::into);
+            current_module.find_use_path(db, item)
+        })
+        .find(|mod_path| mod_path.to_string() == full_import_path)?;
+
+    ImportEdit { import_path, import_scope, merge_behaviour: config.merge }
+        .to_text_edit()
+        .map(|edit| vec![edit])
+}
+
 #[cfg(test)]
 mod tests {
     use crate::config::CompletionConfig;
diff --git a/crates/completion/src/render.rs b/crates/completion/src/render.rs
index 504757a6a..b940388df 100644
--- a/crates/completion/src/render.rs
+++ b/crates/completion/src/render.rs
@@ -9,14 +9,13 @@ pub(crate) mod type_alias;
 
 mod builder_ext;
 
-use hir::{Documentation, HasAttrs, HirDisplay, ModPath, Mutability, ScopeDef, Type};
-use ide_db::helpers::insert_use::{ImportScope, MergeBehaviour};
+use hir::{Documentation, HasAttrs, HirDisplay, Mutability, ScopeDef, Type};
 use ide_db::RootDatabase;
 use syntax::TextRange;
 use test_utils::mark;
 
 use crate::{
-    config::SnippetCap, item::ImportToAdd, CompletionContext, CompletionItem, CompletionItemKind,
+    config::SnippetCap, item::ImportEdit, CompletionContext, CompletionItem, CompletionItemKind,
     CompletionKind, CompletionScore,
 };
 
@@ -48,15 +47,12 @@ pub(crate) fn render_resolution<'a>(
 
 pub(crate) fn render_resolution_with_import<'a>(
     ctx: RenderContext<'a>,
-    import_path: ModPath,
-    import_scope: ImportScope,
-    merge_behaviour: Option<MergeBehaviour>,
+    import_edit: ImportEdit,
     resolution: &ScopeDef,
 ) -> Option<CompletionItem> {
-    let local_name = import_path.segments.last()?.to_string();
     Render::new(ctx).render_resolution(
-        local_name,
-        Some(ImportToAdd { import_path, import_scope, merge_behaviour }),
+        import_edit.import_path.segments.last()?.to_string(),
+        Some(import_edit),
         resolution,
     )
 }
@@ -147,7 +143,7 @@ impl<'a> Render<'a> {
     fn render_resolution(
         self,
         local_name: String,
-        import_to_add: Option<ImportToAdd>,
+        import_to_add: Option<ImportEdit>,
         resolution: &ScopeDef,
     ) -> Option<CompletionItem> {
         let _p = profile::span("render_resolution");
@@ -451,28 +447,6 @@ fn main() { let _: m::Spam = S<|> }
                         kind: Module,
                     },
                     CompletionItem {
-                        label: "m::Spam",
-                        source_range: 75..76,
-                        text_edit: TextEdit {
-                            indels: [
-                                Indel {
-                                    insert: "use m::Spam;",
-                                    delete: 0..0,
-                                },
-                                Indel {
-                                    insert: "\n\n",
-                                    delete: 0..0,
-                                },
-                                Indel {
-                                    insert: "Spam",
-                                    delete: 75..76,
-                                },
-                            ],
-                        },
-                        kind: Enum,
-                        lookup: "Spam",
-                    },
-                    CompletionItem {
                         label: "m::Spam::Foo",
                         source_range: 75..76,
                         delete: 75..76,
diff --git a/crates/completion/src/render/enum_variant.rs b/crates/completion/src/render/enum_variant.rs
index f4bd02f25..8e0fea6c0 100644
--- a/crates/completion/src/render/enum_variant.rs
+++ b/crates/completion/src/render/enum_variant.rs
@@ -5,13 +5,13 @@ use itertools::Itertools;
 use test_utils::mark;
 
 use crate::{
-    item::{CompletionItem, CompletionItemKind, CompletionKind, ImportToAdd},
+    item::{CompletionItem, CompletionItemKind, CompletionKind, ImportEdit},
     render::{builder_ext::Params, RenderContext},
 };
 
 pub(crate) fn render_enum_variant<'a>(
     ctx: RenderContext<'a>,
-    import_to_add: Option<ImportToAdd>,
+    import_to_add: Option<ImportEdit>,
     local_name: Option<String>,
     variant: hir::EnumVariant,
     path: Option<ModPath>,
@@ -62,7 +62,7 @@ impl<'a> EnumVariantRender<'a> {
         }
     }
 
-    fn render(self, import_to_add: Option<ImportToAdd>) -> CompletionItem {
+    fn render(self, import_to_add: Option<ImportEdit>) -> CompletionItem {
         let mut builder = CompletionItem::new(
             CompletionKind::Reference,
             self.ctx.source_range(),
diff --git a/crates/completion/src/render/function.rs b/crates/completion/src/render/function.rs
index 00e3eb203..d16005249 100644
--- a/crates/completion/src/render/function.rs
+++ b/crates/completion/src/render/function.rs
@@ -5,13 +5,13 @@ use syntax::{ast::Fn, display::function_declaration};
 use test_utils::mark;
 
 use crate::{
-    item::{CompletionItem, CompletionItemKind, CompletionKind, ImportToAdd},
+    item::{CompletionItem, CompletionItemKind, CompletionKind, ImportEdit},
     render::{builder_ext::Params, RenderContext},
 };
 
 pub(crate) fn render_fn<'a>(
     ctx: RenderContext<'a>,
-    import_to_add: Option<ImportToAdd>,
+    import_to_add: Option<ImportEdit>,
     local_name: Option<String>,
     fn_: hir::Function,
 ) -> CompletionItem {
@@ -39,7 +39,7 @@ impl<'a> FunctionRender<'a> {
         FunctionRender { ctx, name, func: fn_, ast_node }
     }
 
-    fn render(self, import_to_add: Option<ImportToAdd>) -> CompletionItem {
+    fn render(self, import_to_add: Option<ImportEdit>) -> CompletionItem {
         let params = self.params();
         CompletionItem::new(CompletionKind::Reference, self.ctx.source_range(), self.name.clone())
             .kind(self.kind())
diff --git a/crates/completion/src/render/macro_.rs b/crates/completion/src/render/macro_.rs
index b4ab32c6e..eb3209bee 100644
--- a/crates/completion/src/render/macro_.rs
+++ b/crates/completion/src/render/macro_.rs
@@ -5,13 +5,13 @@ use syntax::display::macro_label;
 use test_utils::mark;
 
 use crate::{
-    item::{CompletionItem, CompletionItemKind, CompletionKind, ImportToAdd},
+    item::{CompletionItem, CompletionItemKind, CompletionKind, ImportEdit},
     render::RenderContext,
 };
 
 pub(crate) fn render_macro<'a>(
     ctx: RenderContext<'a>,
-    import_to_add: Option<ImportToAdd>,
+    import_to_add: Option<ImportEdit>,
     name: String,
     macro_: hir::MacroDef,
 ) -> Option<CompletionItem> {
@@ -38,7 +38,7 @@ impl<'a> MacroRender<'a> {
         MacroRender { ctx, name, macro_, docs, bra, ket }
     }
 
-    fn render(&self, import_to_add: Option<ImportToAdd>) -> Option<CompletionItem> {
+    fn render(&self, import_to_add: Option<ImportEdit>) -> Option<CompletionItem> {
         // FIXME: Currently proc-macro do not have ast-node,
         // such that it does not have source
         if self.macro_.is_proc_macro() {
diff --git a/crates/completion/src/test_utils.rs b/crates/completion/src/test_utils.rs
index 4c1b1a839..25f5f4924 100644
--- a/crates/completion/src/test_utils.rs
+++ b/crates/completion/src/test_utils.rs
@@ -96,7 +96,16 @@ pub(crate) fn check_edit_with_config(
         .collect_tuple()
         .unwrap_or_else(|| panic!("can't find {:?} completion in {:#?}", what, completions));
     let mut actual = db.file_text(position.file_id).to_string();
-    completion.text_edit().apply(&mut actual);
+
+    let mut combined_edit = completion.text_edit().to_owned();
+    if let Some(import_text_edit) = completion.import_to_add().and_then(|edit| edit.to_text_edit())
+    {
+        combined_edit.union(import_text_edit).expect(
+            "Failed to apply completion resolve changes: change ranges overlap, but should not",
+        )
+    }
+
+    combined_edit.apply(&mut actual);
     assert_eq_text!(&ra_fixture_after, &actual)
 }