3 files changed, 71 insertions, 37 deletions

diff --git a/crates/completion/src/completions/unqualified_path.rs b/crates/completion/src/completions/unqualified_path.rs
index d09849752..3d72a08b4 100644
--- a/crates/completion/src/completions/unqualified_path.rs
+++ b/crates/completion/src/completions/unqualified_path.rs
@@ -135,7 +135,7 @@ fn fuzzy_completion(acc: &mut Completions, ctx: &CompletionContext) -> Option<()
         ctx.krate?,
         Some(100),
         &potential_import_name,
-        true,
+        false,
     )
     .filter_map(|import_candidate| {
         Some(match import_candidate {
diff --git a/crates/hir_def/src/import_map.rs b/crates/hir_def/src/import_map.rs
index c0f108848..64d0ec471 100644
--- a/crates/hir_def/src/import_map.rs
+++ b/crates/hir_def/src/import_map.rs
@@ -156,8 +156,7 @@ impl ImportMap {
             let start = last_batch_start;
             last_batch_start = idx + 1;
 
-            let key = fst_path(&importables[start].1.path);
-
+            let key = fst_string(&importables[start].1.path);
             builder.insert(key, start as u64).unwrap();
         }
 
@@ -213,15 +212,15 @@ impl fmt::Debug for ImportMap {
     }
 }
 
-fn fst_path(path: &ImportPath) -> String {
-    let mut s = path.to_string();
+fn fst_string<T: ToString>(t: &T) -> String {
+    let mut s = t.to_string();
     s.make_ascii_lowercase();
     s
 }
 
 fn cmp((_, lhs): &(&ItemInNs, &ImportInfo), (_, rhs): &(&ItemInNs, &ImportInfo)) -> Ordering {
-    let lhs_str = fst_path(&lhs.path);
-    let rhs_str = fst_path(&rhs.path);
+    let lhs_str = fst_string(&lhs.path);
+    let rhs_str = fst_string(&rhs.path);
     lhs_str.cmp(&rhs_str)
 }
 
@@ -242,7 +241,10 @@ pub enum ImportKind {
 pub struct Query {
     query: String,
     lowercased: String,
-    anchor_end: bool,
+    // TODO kb use enums instead?
+    name_only: bool,
+    name_end: bool,
+    strict_include: bool,
     case_sensitive: bool,
     limit: usize,
     exclude_import_kinds: FxHashSet<ImportKind>,
@@ -253,17 +255,27 @@ impl Query {
         Self {
             lowercased: query.to_lowercase(),
             query: query.to_string(),
-            anchor_end: false,
+            name_only: false,
+            name_end: false,
+            strict_include: false,
             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 }
+    pub fn name_end(self) -> Self {
+        Self { name_end: true, ..self }
+    }
+
+    /// todo kb
+    pub fn name_only(self) -> Self {
+        Self { name_only: true, ..self }
+    }
+
+    /// todo kb
+    pub fn strict_include(self) -> Self {
+        Self { strict_include: true, ..self }
     }
 
     /// Limits the returned number of items to `limit`.
@@ -283,6 +295,35 @@ impl Query {
     }
 }
 
+// TODO kb: ugly with a special `return true` case and the `enforce_lowercase` one.
+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 };
+
+    if query.strict_include {
+        if query.name_end {
+            &input == query_string
+        } else {
+            input.contains(query_string)
+        }
+    } else if query.name_end {
+        input.ends_with(query_string)
+    } else {
+        let input_chars = input.chars().collect::<FxHashSet<_>>();
+        // TODO kb actually check for the order and the quantity
+        query_string.chars().all(|query_char| input_chars.contains(&query_char))
+    }
+}
+
 /// 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 +353,26 @@ 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_string(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_string(&import_map.map[item].path)
                 })
                 .filter(|&item| match item_import_kind(item) {
                     Some(import_kind) => !query.exclude_import_kinds.contains(&import_kind),
                     None => true,
-                });
-
-            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);
-            }
+                })
+                .filter(|item| contains_query(&query, &import_map.map[item].path, false));
+            res.extend(iter);
 
             if res.len() >= query.limit {
                 res.truncate(query.limit);
@@ -728,7 +756,7 @@ mod tests {
         check_search(
             ra_fixture,
             "main",
-            Query::new("fmt").anchor_end(),
+            Query::new("fmt").name_only().strict_include(),
             expect![[r#"
                 dep::fmt (t)
                 dep::Fmt (t)
diff --git a/crates/ide_db/src/imports_locator.rs b/crates/ide_db/src/imports_locator.rs
index b2980a5d6..0de949b9a 100644
--- a/crates/ide_db/src/imports_locator.rs
+++ b/crates/ide_db/src/imports_locator.rs
@@ -27,7 +27,12 @@ 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()
+            .name_end()
+            .strict_include()
+            .case_sensitive(),
     )
 }
 
@@ -36,11 +41,12 @@ pub fn find_similar_imports<'a>(
     krate: Crate,
     limit: Option<usize>,
     name_to_import: &str,
+    // TODO kb change it to search across the whole path or not?
     ignore_modules: 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);
+    let mut external_query = import_map::Query::new(name_to_import).name_only();
     if ignore_modules {
         external_query = external_query.exclude_import_kind(import_map::ImportKind::Module);
     }