3 files changed, 188 insertions, 49 deletions

diff --git a/crates/completion/src/completions/unqualified_path.rs b/crates/completion/src/completions/unqualified_path.rs
index d09849752..59f950189 100644
--- a/crates/completion/src/completions/unqualified_path.rs
+++ b/crates/completion/src/completions/unqualified_path.rs
@@ -101,8 +101,9 @@ fn complete_enum_variants(acc: &mut Completions, ctx: &CompletionContext, ty: &T
 //
 // .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.
+// To avoid an excessive amount of the results returned, completion input is checked for inclusion in the names only
+// (i.e. in `HashMap` in the `std::collections::HashMap` path).
+// For the same reasons, avoids searching for any imports for inputs with their length less that 2 symbols.
 //
 // .Merge Behavior
 //
@@ -126,6 +127,10 @@ fn fuzzy_completion(acc: &mut Completions, ctx: &CompletionContext) -> Option<()
     let _p = profile::span("fuzzy_completion");
     let potential_import_name = ctx.token.to_string();
 
+    if potential_import_name.len() < 2 {
+        return None;
+    }
+
     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)?;
@@ -133,7 +138,7 @@ fn fuzzy_completion(acc: &mut Completions, ctx: &CompletionContext) -> Option<()
     let mut all_mod_paths = imports_locator::find_similar_imports(
         &ctx.sema,
         ctx.krate?,
-        Some(100),
+        Some(40),
         &potential_import_name,
         true,
     )
diff --git a/crates/hir_def/src/import_map.rs b/crates/hir_def/src/import_map.rs
index c0f108848..fdc681d6c 100644
--- a/crates/hir_def/src/import_map.rs
+++ b/crates/hir_def/src/import_map.rs
@@ -238,11 +238,24 @@ pub enum ImportKind {
     BuiltinType,
 }
 
+/// A way to match import map contents against the search query.
+#[derive(Debug)]
+pub enum SearchMode {
+    /// Import map entry should strictly match the query string.
+    Equals,
+    /// Import map entry should contain the query string.
+    Contains,
+    /// Import map entry should contain all letters from the query string,
+    /// in the same order, but not necessary adjacent.
+    Fuzzy,
+}
+
 #[derive(Debug)]
 pub struct Query {
     query: String,
     lowercased: String,
-    anchor_end: bool,
+    name_only: bool,
+    search_mode: SearchMode,
     case_sensitive: bool,
     limit: usize,
     exclude_import_kinds: FxHashSet<ImportKind>,
@@ -251,19 +264,26 @@ pub struct Query {
 impl Query {
     pub fn new(query: &str) -> Self {
         Self {
-            lowercased: query.to_lowercase(),
             query: query.to_string(),
-            anchor_end: false,
+            lowercased: query.to_lowercase(),
+            name_only: false,
+            search_mode: SearchMode::Contains,
             case_sensitive: false,
             limit: usize::max_value(),
             exclude_import_kinds: FxHashSet::default(),
         }
     }
 
-    /// Only returns items whose paths end with the (case-insensitive) query string as their last
-    /// segment.
-    pub fn anchor_end(self) -> Self {
-        Self { anchor_end: true, ..self }
+    /// Matches entries' names only, ignoring the rest of
+    /// the qualifier.
+    /// Example: for `std::marker::PhantomData`, the name is `PhantomData`.
+    pub fn name_only(self) -> Self {
+        Self { name_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 }
     }
 
     /// Limits the returned number of items to `limit`.
@@ -283,6 +303,40 @@ impl Query {
     }
 }
 
+fn contains_query(query: &Query, input_path: &ImportPath, enforce_lowercase: bool) -> bool {
+    let mut input = if query.name_only {
+        input_path.segments.last().unwrap().to_string()
+    } else {
+        input_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();
+                    }
+                    _ => (),
+                }
+            }
+            mismatching_query_char.is_none()
+        }
+    }
+}
+
 /// Searches dependencies of `krate` for an importable path matching `query`.
 ///
 /// This returns a list of items that could be imported from dependencies of `krate`.
@@ -312,39 +366,29 @@ pub fn search_dependencies<'a>(
             let importables = &import_map.importables[indexed_value.value as usize..];
 
             // Path shared by the importable items in this group.
-            let path = &import_map.map[&importables[0]].path;
-
-            if query.anchor_end {
-                // Last segment must match query.
-                let last = path.segments.last().unwrap().to_string();
-                if last.to_lowercase() != query.lowercased {
-                    continue;
-                }
+            let common_importables_path = &import_map.map[&importables[0]].path;
+            if !contains_query(&query, common_importables_path, true) {
+                continue;
             }
 
+            let common_importables_path_fst = fst_path(common_importables_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| {
-                    let item_path = &import_map.map[item].path;
-                    fst_path(item_path) == fst_path(path)
+                    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
+                        || contains_query(&query, &import_map.map[item].path, false)
                 });
-
-            if query.case_sensitive {
-                // FIXME: This does not do a subsequence match.
-                res.extend(iter.filter(|item| {
-                    let item_path = &import_map.map[item].path;
-                    item_path.to_string().contains(&query.query)
-                }));
-            } else {
-                res.extend(iter);
-            }
+            res.extend(iter);
 
             if res.len() >= query.limit {
                 res.truncate(query.limit);
@@ -388,7 +432,7 @@ mod tests {
     use base_db::{fixture::WithFixture, SourceDatabase, Upcast};
     use expect_test::{expect, Expect};
 
-    use crate::{test_db::TestDB, AssocContainerId, Lookup};
+    use crate::{data::FunctionData, test_db::TestDB, AssocContainerId, Lookup};
 
     use super::*;
 
@@ -407,14 +451,31 @@ mod tests {
             .into_iter()
             .filter_map(|item| {
                 let mark = match item {
+                    ItemInNs::Types(ModuleDefId::FunctionId(_))
+                    | ItemInNs::Values(ModuleDefId::FunctionId(_)) => "f",
                     ItemInNs::Types(_) => "t",
                     ItemInNs::Values(_) => "v",
                     ItemInNs::Macros(_) => "m",
                 };
-                let item = assoc_to_trait(&db, item);
                 item.krate(db.upcast()).map(|krate| {
                     let map = db.import_map(krate);
-                    let path = map.path_of(item).unwrap();
+
+                    let path = match assoc_to_trait(&db, item) {
+                        Some(trait_) => {
+                            let mut full_path = map.path_of(trait_).unwrap().to_string();
+                            if let ItemInNs::Types(ModuleDefId::FunctionId(function_id))
+                            | ItemInNs::Values(ModuleDefId::FunctionId(function_id)) = item
+                            {
+                                full_path += &format!(
+                                    "::{}",
+                                    FunctionData::fn_data_query(&db, function_id).name
+                                );
+                            }
+                            full_path
+                        }
+                        None => map.path_of(item).unwrap().to_string(),
+                    };
+
                     format!(
                         "{}::{} ({})\n",
                         crate_graph[krate].display_name.as_ref().unwrap(),
@@ -427,15 +488,15 @@ mod tests {
         expect.assert_eq(&actual)
     }
 
-    fn assoc_to_trait(db: &dyn DefDatabase, item: ItemInNs) -> ItemInNs {
+    fn assoc_to_trait(db: &dyn DefDatabase, item: ItemInNs) -> Option<ItemInNs> {
         let assoc: AssocItemId = match item {
             ItemInNs::Types(it) | ItemInNs::Values(it) => match it {
                 ModuleDefId::TypeAliasId(it) => it.into(),
                 ModuleDefId::FunctionId(it) => it.into(),
                 ModuleDefId::ConstId(it) => it.into(),
-                _ => return item,
+                _ => return None,
             },
-            _ => return item,
+            _ => return None,
         };
 
         let container = match assoc {
@@ -445,8 +506,8 @@ mod tests {
         };
 
         match container {
-            AssocContainerId::TraitId(it) => ItemInNs::Types(it.into()),
-            _ => item,
+            AssocContainerId::TraitId(it) => Some(ItemInNs::Types(it.into())),
+            _ => None,
         }
     }
 
@@ -685,7 +746,7 @@ mod tests {
     }
 
     #[test]
-    fn search() {
+    fn search_mode() {
         let ra_fixture = r#"
             //- /main.rs crate:main deps:dep
             //- /dep.rs crate:dep deps:tdep
@@ -713,28 +774,96 @@ mod tests {
         check_search(
             ra_fixture,
             "main",
-            Query::new("fmt"),
+            Query::new("fmt").search_mode(SearchMode::Fuzzy),
             expect![[r#"
                 dep::fmt (t)
                 dep::Fmt (t)
                 dep::Fmt (v)
                 dep::Fmt (m)
                 dep::fmt::Display (t)
-                dep::format (v)
+                dep::format (f)
+                dep::fmt::Display::fmt (f)
+            "#]],
+        );
+
+        check_search(
+            ra_fixture,
+            "main",
+            Query::new("fmt").search_mode(SearchMode::Equals),
+            expect![[r#"
+                dep::fmt (t)
+                dep::Fmt (t)
+                dep::Fmt (v)
+                dep::Fmt (m)
+                dep::fmt::Display::fmt (f)
+            "#]],
+        );
+
+        check_search(
+            ra_fixture,
+            "main",
+            Query::new("fmt").search_mode(SearchMode::Contains),
+            expect![[r#"
+                dep::fmt (t)
+                dep::Fmt (t)
+                dep::Fmt (v)
+                dep::Fmt (m)
                 dep::fmt::Display (t)
+                dep::fmt::Display::fmt (f)
             "#]],
         );
+    }
+
+    #[test]
+    fn name_only() {
+        let ra_fixture = r#"
+            //- /main.rs crate:main deps:dep
+            //- /dep.rs crate:dep deps:tdep
+            use tdep::fmt as fmt_dep;
+            pub mod fmt {
+                pub trait Display {
+                    fn fmt();
+                }
+            }
+            #[macro_export]
+            macro_rules! Fmt {
+                () => {};
+            }
+            pub struct Fmt;
+
+            pub fn format() {}
+            pub fn no() {}
+
+            //- /tdep.rs crate:tdep
+            pub mod fmt {
+                pub struct NotImportableFromMain;
+            }
+        "#;
 
         check_search(
             ra_fixture,
             "main",
-            Query::new("fmt").anchor_end(),
+            Query::new("fmt"),
             expect![[r#"
                 dep::fmt (t)
                 dep::Fmt (t)
                 dep::Fmt (v)
                 dep::Fmt (m)
                 dep::fmt::Display (t)
+                dep::fmt::Display::fmt (f)
+            "#]],
+        );
+
+        check_search(
+            ra_fixture,
+            "main",
+            Query::new("fmt").name_only(),
+            expect![[r#"
+                dep::fmt (t)
+                dep::Fmt (t)
+                dep::Fmt (v)
+                dep::Fmt (m)
+                dep::fmt::Display::fmt (f)
             "#]],
         );
     }
diff --git a/crates/ide_db/src/imports_locator.rs b/crates/ide_db/src/imports_locator.rs
index b2980a5d6..b6355af4b 100644
--- a/crates/ide_db/src/imports_locator.rs
+++ b/crates/ide_db/src/imports_locator.rs
@@ -27,7 +27,11 @@ pub fn find_exact_imports<'a>(
             local_query.limit(40);
             local_query
         },
-        import_map::Query::new(name_to_import).anchor_end().case_sensitive().limit(40),
+        import_map::Query::new(name_to_import)
+            .limit(40)
+            .name_only()
+            .search_mode(import_map::SearchMode::Equals)
+            .case_sensitive(),
     )
 }
 
@@ -35,17 +39,18 @@ pub fn find_similar_imports<'a>(
     sema: &Semantics<'a, RootDatabase>,
     krate: Crate,
     limit: Option<usize>,
-    name_to_import: &str,
-    ignore_modules: bool,
+    fuzzy_search_string: &str,
+    name_only: bool,
 ) -> impl Iterator<Item = Either<ModuleDef, MacroDef>> {
     let _p = profile::span("find_similar_imports");
 
-    let mut external_query = import_map::Query::new(name_to_import);
-    if ignore_modules {
-        external_query = external_query.exclude_import_kind(import_map::ImportKind::Module);
+    let mut external_query =
+        import_map::Query::new(fuzzy_search_string).search_mode(import_map::SearchMode::Fuzzy);
+    if name_only {
+        external_query = external_query.name_only();
     }
 
-    let mut local_query = symbol_index::Query::new(name_to_import.to_string());
+    let mut local_query = symbol_index::Query::new(fuzzy_search_string.to_string());
 
     if let Some(limit) = limit {
         local_query.limit(limit);