9 files changed, 264 insertions, 29 deletions

diff --git a/crates/completion/Cargo.toml b/crates/completion/Cargo.toml
index 3015ec9e0..e7df9d955 100644
--- a/crates/completion/Cargo.toml
+++ b/crates/completion/Cargo.toml
@@ -13,6 +13,7 @@ doctest = false
 itertools = "0.9.0"
 log = "0.4.8"
 rustc-hash = "1.1.0"
+either = "1.6.1"
 
 assists = { path = "../assists", version = "0.0.0" }
 stdx = { path = "../stdx", version = "0.0.0" }
diff --git a/crates/completion/src/completions.rs b/crates/completion/src/completions.rs
index 75dbb1a23..9b7d6c580 100644
--- a/crates/completion/src/completions.rs
+++ b/crates/completion/src/completions.rs
@@ -90,7 +90,7 @@ impl Completions {
             Some(it) => it,
             None => return,
         };
-        if let Some(item) = render_macro(RenderContext::new(ctx), name, macro_) {
+        if let Some(item) = render_macro(RenderContext::new(ctx), None, name, macro_) {
             self.add(item);
         }
     }
@@ -101,7 +101,7 @@ impl Completions {
         func: hir::Function,
         local_name: Option<String>,
     ) {
-        let item = render_fn(RenderContext::new(ctx), local_name, func);
+        let item = render_fn(RenderContext::new(ctx), None, local_name, func);
         self.add(item)
     }
 
@@ -123,7 +123,7 @@ impl Completions {
         variant: hir::EnumVariant,
         path: ModPath,
     ) {
-        let item = render_enum_variant(RenderContext::new(ctx), None, variant, Some(path));
+        let item = render_enum_variant(RenderContext::new(ctx), None, None, variant, Some(path));
         self.add(item);
     }
 
@@ -133,7 +133,7 @@ impl Completions {
         variant: hir::EnumVariant,
         local_name: Option<String>,
     ) {
-        let item = render_enum_variant(RenderContext::new(ctx), local_name, variant, None);
+        let item = render_enum_variant(RenderContext::new(ctx), None, local_name, variant, None);
         self.add(item);
     }
 }
diff --git a/crates/completion/src/completions/unqualified_path.rs b/crates/completion/src/completions/unqualified_path.rs
index 7df58e1da..86c143b63 100644
--- a/crates/completion/src/completions/unqualified_path.rs
+++ b/crates/completion/src/completions/unqualified_path.rs
@@ -1,10 +1,16 @@
 //! Completion of names from the current scope, e.g. locals and imported items.
 
+use assists::utils::ImportScope;
+use either::Either;
 use hir::{Adt, ModuleDef, ScopeDef, Type};
+use ide_db::imports_locator;
 use syntax::AstNode;
 use test_utils::mark;
 
-use crate::{CompletionContext, Completions};
+use crate::{
+    render::{render_resolution_with_import, RenderContext},
+    CompletionContext, Completions,
+};
 
 pub(crate) fn complete_unqualified_path(acc: &mut Completions, ctx: &CompletionContext) {
     if !(ctx.is_trivial_path || ctx.is_pat_binding_or_const) {
@@ -37,6 +43,8 @@ pub(crate) fn complete_unqualified_path(acc: &mut Completions, ctx: &CompletionC
         }
         acc.add_resolution(ctx, name.to_string(), &res)
     });
+
+    fuzzy_completion(acc, ctx).unwrap_or_default()
 }
 
 fn complete_enum_variants(acc: &mut Completions, ctx: &CompletionContext, ty: &Type) {
@@ -63,6 +71,45 @@ fn complete_enum_variants(acc: &mut Completions, ctx: &CompletionContext, ty: &T
     }
 }
 
+fn fuzzy_completion(acc: &mut Completions, ctx: &CompletionContext) -> Option<()> {
+    let _p = profile::span("fuzzy_completion");
+    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?, &potential_import_name, 400)
+            .filter_map(|import_candidate| match import_candidate {
+                // when completing outside the use declaration, modules are pretty useless
+                // and tend to bloat the completion suggestions a lot
+                Either::Left(ModuleDef::Module(_)) => None,
+                Either::Left(module_def) => Some((
+                    current_module.find_use_path(ctx.db, module_def)?,
+                    ScopeDef::ModuleDef(module_def),
+                )),
+                Either::Right(macro_def) => Some((
+                    current_module.find_use_path(ctx.db, macro_def)?,
+                    ScopeDef::MacroDef(macro_def),
+                )),
+            })
+            .filter(|(mod_path, _)| mod_path.len() > 1)
+            .filter_map(|(import_path, definition)| {
+                render_resolution_with_import(
+                    RenderContext::new(ctx),
+                    import_path.clone(),
+                    import_scope.clone(),
+                    ctx.config.merge,
+                    &definition,
+                )
+            })
+            .take(20);
+
+    acc.add_all(possible_imports);
+    Some(())
+}
+
 #[cfg(test)]
 mod tests {
     use expect_test::{expect, Expect};
@@ -676,4 +723,85 @@ impl My<|>
             "#]],
         )
     }
+
+    #[test]
+    fn function_fuzzy_completion() {
+        check_edit(
+            "stdin",
+            r#"
+//- /lib.rs crate:dep
+pub mod io {
+    pub fn stdin() {}
+};
+
+//- /main.rs crate:main deps:dep
+fn main() {
+    stdi<|>
+}
+"#,
+            r#"
+use dep::io::stdin;
+
+fn main() {
+    stdin()$0
+}
+"#,
+        );
+    }
+
+    #[test]
+    fn macro_fuzzy_completion() {
+        check_edit(
+            "macro_with_curlies!",
+            r#"
+//- /lib.rs crate:dep
+/// Please call me as macro_with_curlies! {}
+#[macro_export]
+macro_rules! macro_with_curlies {
+    () => {}
+}
+
+//- /main.rs crate:main deps:dep
+fn main() {
+    curli<|>
+}
+"#,
+            r#"
+use dep::macro_with_curlies;
+
+fn main() {
+    macro_with_curlies! {$0}
+}
+"#,
+        );
+    }
+
+    #[test]
+    fn struct_fuzzy_completion() {
+        check_edit(
+            "ThirdStruct",
+            r#"
+//- /lib.rs crate:dep
+pub struct FirstStruct;
+pub mod some_module {
+    pub struct SecondStruct;
+    pub struct ThirdStruct;
+}
+
+//- /main.rs crate:main deps:dep
+use dep::{FirstStruct, some_module::SecondStruct};
+
+fn main() {
+    this<|>
+}
+"#,
+            r#"
+use dep::{FirstStruct, some_module::{SecondStruct, ThirdStruct}};
+
+fn main() {
+    ThirdStruct
+}
+"#,
+        );
+    }
 }
diff --git a/crates/completion/src/config.rs b/crates/completion/src/config.rs
index 71b49ace8..82874ff25 100644
--- a/crates/completion/src/config.rs
+++ b/crates/completion/src/config.rs
@@ -4,12 +4,15 @@
 //! module, and we use to statically check that we only produce snippet
 //! completions if we are allowed to.
 
+use assists::utils::MergeBehaviour;
+
 #[derive(Clone, Debug, PartialEq, Eq)]
 pub struct CompletionConfig {
     pub enable_postfix_completions: bool,
     pub add_call_parenthesis: bool,
     pub add_call_argument_snippets: bool,
     pub snippet_cap: Option<SnippetCap>,
+    pub merge: Option<MergeBehaviour>,
 }
 
 impl CompletionConfig {
@@ -30,6 +33,7 @@ impl Default for CompletionConfig {
             add_call_parenthesis: true,
             add_call_argument_snippets: true,
             snippet_cap: Some(SnippetCap { _private: () }),
+            merge: Some(MergeBehaviour::Full),
         }
     }
 }
diff --git a/crates/completion/src/item.rs b/crates/completion/src/item.rs
index 6d1d085f4..b13c3f376 100644
--- a/crates/completion/src/item.rs
+++ b/crates/completion/src/item.rs
@@ -2,8 +2,9 @@
 
 use std::fmt;
 
-use hir::{Documentation, Mutability};
-use syntax::TextRange;
+use assists::utils::{insert_use, mod_path_to_ast, ImportScope, MergeBehaviour};
+use hir::{Documentation, ModPath, Mutability};
+use syntax::{algo, TextRange};
 use text_edit::TextEdit;
 
 use crate::config::SnippetCap;
@@ -31,6 +32,7 @@ pub struct CompletionItem {
     ///
     /// Typically, replaces `source_range` with new identifier.
     text_edit: TextEdit,
+
     insert_text_format: InsertTextFormat,
 
     /// What item (struct, function, etc) are we completing.
@@ -199,8 +201,10 @@ impl CompletionItem {
             trigger_call_info: None,
             score: None,
             ref_match: None,
+            import_data: None,
         }
     }
+
     /// What user sees in pop-up in the UI.
     pub fn label(&self) -> &str {
         &self.label
@@ -257,6 +261,7 @@ impl CompletionItem {
 pub(crate) struct Builder {
     source_range: TextRange,
     completion_kind: CompletionKind,
+    import_data: Option<(ModPath, ImportScope, Option<MergeBehaviour>)>,
     label: String,
     insert_text: Option<String>,
     insert_text_format: InsertTextFormat,
@@ -273,23 +278,50 @@ pub(crate) struct Builder {
 
 impl Builder {
     pub(crate) fn build(self) -> CompletionItem {
-        let label = self.label;
-        let text_edit = match self.text_edit {
+        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_path, import_scope, merge_behaviour)) = self.import_data {
+            let import = mod_path_to_ast(&import_path);
+            let mut import_path_without_last_segment = import_path;
+            let _ = import_path_without_last_segment.segments.pop();
+
+            if !import_path_without_last_segment.segments.is_empty() {
+                if lookup.is_none() {
+                    lookup = Some(label.clone());
+                }
+                if insert_text.is_none() {
+                    insert_text = Some(label.clone());
+                }
+                label = format!("{}::{}", import_path_without_last_segment, label);
+            }
+
+            let rewriter = insert_use(&import_scope, import, 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 {
             Some(it) => it,
-            None => TextEdit::replace(
-                self.source_range,
-                self.insert_text.unwrap_or_else(|| label.clone()),
-            ),
+            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,
+            text_edit: resulting_edit,
             detail: self.detail,
             documentation: self.documentation,
-            lookup: self.lookup,
+            lookup,
             kind: self.kind,
             completion_kind: self.completion_kind,
             deprecated: self.deprecated.unwrap_or(false),
@@ -358,6 +390,13 @@ impl Builder {
         self.trigger_call_info = Some(true);
         self
     }
+    pub(crate) fn import_data(
+        mut self,
+        import_data: Option<(ModPath, ImportScope, Option<MergeBehaviour>)>,
+    ) -> Builder {
+        self.import_data = import_data;
+        self
+    }
     pub(crate) fn set_ref_match(
         mut self,
         ref_match: Option<(Mutability, CompletionScore)>,
diff --git a/crates/completion/src/render.rs b/crates/completion/src/render.rs
index 1fa02c375..e892d4de8 100644
--- a/crates/completion/src/render.rs
+++ b/crates/completion/src/render.rs
@@ -9,7 +9,8 @@ pub(crate) mod type_alias;
 
 mod builder_ext;
 
-use hir::{Documentation, HasAttrs, HirDisplay, Mutability, ScopeDef, Type};
+use assists::utils::{ImportScope, MergeBehaviour};
+use hir::{Documentation, HasAttrs, HirDisplay, ModPath, Mutability, ScopeDef, Type};
 use ide_db::RootDatabase;
 use syntax::TextRange;
 use test_utils::mark;
@@ -42,7 +43,22 @@ pub(crate) fn render_resolution<'a>(
     local_name: String,
     resolution: &ScopeDef,
 ) -> Option<CompletionItem> {
-    Render::new(ctx).render_resolution(local_name, resolution)
+    Render::new(ctx).render_resolution(local_name, None, resolution)
+}
+
+pub(crate) fn render_resolution_with_import<'a>(
+    ctx: RenderContext<'a>,
+    import: ModPath,
+    import_scope: ImportScope,
+    merge_behaviour: Option<MergeBehaviour>,
+    resolution: &ScopeDef,
+) -> Option<CompletionItem> {
+    let local_name = import.segments.last()?.to_string();
+    Render::new(ctx).render_resolution(
+        local_name,
+        Some((import, import_scope, merge_behaviour)),
+        resolution,
+    )
 }
 
 /// Interface for data and methods required for items rendering.
@@ -131,6 +147,7 @@ impl<'a> Render<'a> {
     fn render_resolution(
         self,
         local_name: String,
+        import_data: Option<(ModPath, ImportScope, Option<MergeBehaviour>)>,
         resolution: &ScopeDef,
     ) -> Option<CompletionItem> {
         use hir::ModuleDef::*;
@@ -142,15 +159,15 @@ impl<'a> Render<'a> {
 
         let kind = match resolution {
             ScopeDef::ModuleDef(Function(func)) => {
-                let item = render_fn(self.ctx, Some(local_name), *func);
+                let item = render_fn(self.ctx, import_data, Some(local_name), *func);
                 return Some(item);
             }
             ScopeDef::ModuleDef(EnumVariant(var)) => {
-                let item = render_enum_variant(self.ctx, Some(local_name), *var, None);
+                let item = render_enum_variant(self.ctx, import_data, Some(local_name), *var, None);
                 return Some(item);
             }
             ScopeDef::MacroDef(mac) => {
-                let item = render_macro(self.ctx, local_name, *mac);
+                let item = render_macro(self.ctx, import_data, local_name, *mac);
                 return item;
             }
 
@@ -175,6 +192,7 @@ impl<'a> Render<'a> {
                     local_name,
                 )
                 .kind(CompletionItemKind::UnresolvedReference)
+                .import_data(import_data)
                 .build();
                 return Some(item);
             }
@@ -227,7 +245,12 @@ impl<'a> Render<'a> {
             }
         }
 
-        let item = item.kind(kind).set_documentation(docs).set_ref_match(ref_match).build();
+        let item = item
+            .kind(kind)
+            .import_data(import_data)
+            .set_documentation(docs)
+            .set_ref_match(ref_match)
+            .build();
         Some(item)
     }
 
@@ -426,6 +449,28 @@ 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 fd412ed0e..6070e9b1d 100644
--- a/crates/completion/src/render/enum_variant.rs
+++ b/crates/completion/src/render/enum_variant.rs
@@ -1,5 +1,6 @@
 //! Renderer for `enum` variants.
 
+use assists::utils::{ImportScope, MergeBehaviour};
 use hir::{HasAttrs, HirDisplay, ModPath, StructKind};
 use itertools::Itertools;
 use test_utils::mark;
@@ -11,11 +12,12 @@ use crate::{
 
 pub(crate) fn render_enum_variant<'a>(
     ctx: RenderContext<'a>,
+    import_data: Option<(ModPath, ImportScope, Option<MergeBehaviour>)>,
     local_name: Option<String>,
     variant: hir::EnumVariant,
     path: Option<ModPath>,
 ) -> CompletionItem {
-    EnumVariantRender::new(ctx, local_name, variant, path).render()
+    EnumVariantRender::new(ctx, local_name, variant, path).render(import_data)
 }
 
 #[derive(Debug)]
@@ -60,7 +62,10 @@ impl<'a> EnumVariantRender<'a> {
         }
     }
 
-    fn render(self) -> CompletionItem {
+    fn render(
+        self,
+        import_data: Option<(ModPath, ImportScope, Option<MergeBehaviour>)>,
+    ) -> CompletionItem {
         let mut builder = CompletionItem::new(
             CompletionKind::Reference,
             self.ctx.source_range(),
@@ -69,6 +74,7 @@ impl<'a> EnumVariantRender<'a> {
         .kind(CompletionItemKind::EnumVariant)
         .set_documentation(self.variant.docs(self.ctx.db()))
         .set_deprecated(self.ctx.is_deprecated(self.variant))
+        .import_data(import_data)
         .detail(self.detail());
 
         if self.variant_kind == StructKind::Tuple {
diff --git a/crates/completion/src/render/function.rs b/crates/completion/src/render/function.rs
index 4fa6eafd7..9dd5cd18c 100644
--- a/crates/completion/src/render/function.rs
+++ b/crates/completion/src/render/function.rs
@@ -1,6 +1,7 @@
 //! Renderer for function calls.
 
-use hir::{HasSource, Type};
+use assists::utils::{ImportScope, MergeBehaviour};
+use hir::{HasSource, ModPath, Type};
 use syntax::{ast::Fn, display::function_declaration};
 
 use crate::{
@@ -10,10 +11,11 @@ use crate::{
 
 pub(crate) fn render_fn<'a>(
     ctx: RenderContext<'a>,
+    import_data: Option<(ModPath, ImportScope, Option<MergeBehaviour>)>,
     local_name: Option<String>,
     fn_: hir::Function,
 ) -> CompletionItem {
-    FunctionRender::new(ctx, local_name, fn_).render()
+    FunctionRender::new(ctx, local_name, fn_).render(import_data)
 }
 
 #[derive(Debug)]
@@ -36,7 +38,10 @@ impl<'a> FunctionRender<'a> {
         FunctionRender { ctx, name, fn_, ast_node }
     }
 
-    fn render(self) -> CompletionItem {
+    fn render(
+        self,
+        import_data: Option<(ModPath, ImportScope, Option<MergeBehaviour>)>,
+    ) -> CompletionItem {
         let params = self.params();
         CompletionItem::new(CompletionKind::Reference, self.ctx.source_range(), self.name.clone())
             .kind(self.kind())
@@ -44,6 +49,7 @@ impl<'a> FunctionRender<'a> {
             .set_deprecated(self.ctx.is_deprecated(self.fn_))
             .detail(self.detail())
             .add_call_parens(self.ctx.completion, self.name, params)
+            .import_data(import_data)
             .build()
     }
 
diff --git a/crates/completion/src/render/macro_.rs b/crates/completion/src/render/macro_.rs
index 96be59cc3..fead59e41 100644
--- a/crates/completion/src/render/macro_.rs
+++ b/crates/completion/src/render/macro_.rs
@@ -1,6 +1,7 @@
 //! Renderer for macro invocations.
 
-use hir::{Documentation, HasSource};
+use assists::utils::{ImportScope, MergeBehaviour};
+use hir::{Documentation, HasSource, ModPath};
 use syntax::display::macro_label;
 use test_utils::mark;
 
@@ -11,10 +12,11 @@ use crate::{
 
 pub(crate) fn render_macro<'a>(
     ctx: RenderContext<'a>,
+    import_data: Option<(ModPath, ImportScope, Option<MergeBehaviour>)>,
     name: String,
     macro_: hir::MacroDef,
 ) -> Option<CompletionItem> {
-    MacroRender::new(ctx, name, macro_).render()
+    MacroRender::new(ctx, name, macro_).render(import_data)
 }
 
 #[derive(Debug)]
@@ -36,7 +38,10 @@ impl<'a> MacroRender<'a> {
         MacroRender { ctx, name, macro_, docs, bra, ket }
     }
 
-    fn render(&self) -> Option<CompletionItem> {
+    fn render(
+        &self,
+        import_data: Option<(ModPath, ImportScope, Option<MergeBehaviour>)>,
+    ) -> Option<CompletionItem> {
         // FIXME: Currently proc-macro do not have ast-node,
         // such that it does not have source
         if self.macro_.is_proc_macro() {
@@ -48,6 +53,7 @@ impl<'a> MacroRender<'a> {
                 .kind(CompletionItemKind::Macro)
                 .set_documentation(self.docs.clone())
                 .set_deprecated(self.ctx.is_deprecated(self.macro_))
+                .import_data(import_data)
                 .detail(self.detail());
 
         let needs_bang = self.needs_bang();