Merge #6946

6946: Better fuzzy heuristics r=matklad a=SomeoneToIgnore

Continuation of the https://github.com/rust-analyzer/rust-analyzer/pull/6922, mainly created for a test.

Turns out our current completions tests were sorting the completions by label, I had to remove that to test the order properly and update this order in a bunch of tests (ergo the changes)

Co-authored-by: Kirill Bulatov <mail4score@gmail.com>

12 files changed, 263 insertions, 216 deletions

diff --git a/crates/completion/src/completions/attribute.rs b/crates/completion/src/completions/attribute.rs
index acce2e7e7a5..19ce2482fd4 100644
--- a/crates/completion/src/completions/attribute.rs
+++ b/crates/completion/src/completions/attribute.rs
@@ -428,8 +428,8 @@ struct Test {}
                 at Hash
                 at PartialEq
                 at PartialEq, Eq
-                at PartialEq, Eq, PartialOrd, Ord
                 at PartialEq, PartialOrd
+                at PartialEq, Eq, PartialOrd, Ord
             "#]],
         );
     }
@@ -457,10 +457,10 @@ struct Test {}
                 at Clone, Copy
                 at Debug
                 at Default
-                at Eq
-                at Eq, PartialOrd, Ord
                 at Hash
+                at Eq
                 at PartialOrd
+                at Eq, PartialOrd, Ord
             "#]],
         )
     }
@@ -472,14 +472,14 @@ struct Test {}
             expect![[r#"
                 at allow(…)
                 at automatically_derived
-                at cfg(…)
                 at cfg_attr(…)
+                at cfg(…)
                 at cold
                 at deny(…)
                 at deprecated = "…"
                 at derive(…)
-                at doc = "…"
                 at export_name = "…"
+                at doc = "…"
                 at forbid(…)
                 at ignore = "…"
                 at inline(…)
@@ -518,15 +518,15 @@ struct Test {}
             expect![[r#"
                 at allow(…)
                 at automatically_derived
-                at cfg(…)
                 at cfg_attr(…)
+                at cfg(…)
                 at cold
                 at crate_name = ""
                 at deny(…)
                 at deprecated = "…"
                 at derive(…)
-                at doc = "…"
                 at export_name = "…"
+                at doc = "…"
                 at feature(…)
                 at forbid(…)
                 at global_allocator
@@ -538,8 +538,8 @@ struct Test {}
                 at macro_export
                 at macro_use
                 at must_use = "…"
-                at no_implicit_prelude
                 at no_link
+                at no_implicit_prelude
                 at no_main
                 at no_mangle
                 at no_std
diff --git a/crates/completion/src/completions/dot.rs b/crates/completion/src/completions/dot.rs
index c9875045ad4..551ef17716d 100644
--- a/crates/completion/src/completions/dot.rs
+++ b/crates/completion/src/completions/dot.rs
@@ -82,8 +82,8 @@ impl S {
 fn foo(s: S) { s.<|> }
 "#,
             expect![[r#"
-                me bar() fn bar(&self)
                 fd foo   u32
+                me bar() fn bar(&self)
             "#]],
         );
     }
@@ -98,8 +98,8 @@ impl S {
 }
 "#,
             expect![[r#"
-                me foo()     fn foo(self)
                 fd the_field (u32,)
+                me foo()     fn foo(self)
             "#]],
         )
     }
@@ -114,8 +114,8 @@ impl A {
 }
 "#,
             expect![[r#"
-                me foo()     fn foo(&self)
                 fd the_field (u32, i32)
+                me foo()     fn foo(&self)
             "#]],
         )
     }
@@ -147,8 +147,8 @@ mod inner {
 fn foo(a: inner::A) { a.<|> }
 "#,
             expect![[r#"
-                fd crate_field u32
                 fd pub_field   u32
+                fd crate_field u32
                 fd super_field u32
             "#]],
         );
diff --git a/crates/completion/src/completions/keyword.rs b/crates/completion/src/completions/keyword.rs
index 720349b9ded..1859dec7086 100644
--- a/crates/completion/src/completions/keyword.rs
+++ b/crates/completion/src/completions/keyword.rs
@@ -223,21 +223,21 @@ mod tests {
         check(
             r"m<|>",
             expect![[r#"
-                kw const
-                kw enum
-                kw extern
                 kw fn
+                kw use
                 kw impl
-                kw mod
-                kw pub
-                kw pub(crate)
-                kw static
-                kw struct
                 kw trait
-                kw type
+                kw enum
+                kw struct
                 kw union
+                kw mod
+                kw const
+                kw type
+                kw static
+                kw extern
                 kw unsafe
-                kw use
+                kw pub(crate)
+                kw pub
             "#]],
         );
     }
@@ -247,23 +247,23 @@ mod tests {
         check(
             r"fn quux() { <|> }",
             expect![[r#"
-                kw const
-                kw extern
                 kw fn
+                kw use
+                kw impl
+                kw trait
+                kw match
+                kw while
+                kw loop
                 kw if
                 kw if let
-                kw impl
                 kw let
-                kw loop
-                kw match
                 kw mod
-                kw return
-                kw static
-                kw trait
+                kw const
                 kw type
+                kw static
+                kw extern
                 kw unsafe
-                kw use
-                kw while
+                kw return
             "#]],
         );
     }
@@ -273,23 +273,23 @@ mod tests {
         check(
             r"fn quux() { if true { <|> } }",
             expect![[r#"
-                kw const
-                kw extern
                 kw fn
+                kw use
+                kw impl
+                kw trait
+                kw match
+                kw while
+                kw loop
                 kw if
                 kw if let
-                kw impl
                 kw let
-                kw loop
-                kw match
                 kw mod
-                kw return
-                kw static
-                kw trait
+                kw const
                 kw type
+                kw static
+                kw extern
                 kw unsafe
-                kw use
-                kw while
+                kw return
             "#]],
         );
     }
@@ -299,25 +299,25 @@ mod tests {
         check(
             r#"fn quux() { if true { () } <|> }"#,
             expect![[r#"
-                kw const
-                kw else
-                kw else if
-                kw extern
                 kw fn
+                kw use
+                kw impl
+                kw trait
+                kw match
+                kw while
+                kw loop
                 kw if
                 kw if let
-                kw impl
                 kw let
-                kw loop
-                kw match
+                kw else
+                kw else if
                 kw mod
-                kw return
-                kw static
-                kw trait
+                kw const
                 kw type
+                kw static
+                kw extern
                 kw unsafe
-                kw use
-                kw while
+                kw return
             "#]],
         );
         check_edit(
@@ -336,13 +336,13 @@ fn quux() -> i32 {
 }
 "#,
             expect![[r#"
+                kw match
+                kw while
+                kw loop
                 kw if
                 kw if let
-                kw loop
-                kw match
-                kw return
                 kw unsafe
-                kw while
+                kw return
             "#]],
         );
     }
@@ -352,8 +352,8 @@ fn quux() -> i32 {
         check(
             r"trait My { <|> }",
             expect![[r#"
-                kw const
                 kw fn
+                kw const
                 kw type
                 kw unsafe
             "#]],
@@ -365,12 +365,12 @@ fn quux() -> i32 {
         check(
             r"impl My { <|> }",
             expect![[r#"
-                kw const
                 kw fn
-                kw pub
-                kw pub(crate)
+                kw const
                 kw type
                 kw unsafe
+                kw pub(crate)
+                kw pub
             "#]],
         );
     }
@@ -380,25 +380,25 @@ fn quux() -> i32 {
         check(
             r"fn my() { loop { <|> } }",
             expect![[r#"
-                kw break
-                kw const
-                kw continue
-                kw extern
                 kw fn
+                kw use
+                kw impl
+                kw trait
+                kw match
+                kw while
+                kw loop
                 kw if
                 kw if let
-                kw impl
                 kw let
-                kw loop
-                kw match
                 kw mod
-                kw return
-                kw static
-                kw trait
+                kw const
                 kw type
+                kw static
+                kw extern
                 kw unsafe
-                kw use
-                kw while
+                kw continue
+                kw break
+                kw return
             "#]],
         );
     }
@@ -409,8 +409,8 @@ fn quux() -> i32 {
             r"unsafe <|>",
             expect![[r#"
                 kw fn
-                kw impl
                 kw trait
+                kw impl
             "#]],
         );
     }
@@ -421,8 +421,8 @@ fn quux() -> i32 {
             r"fn my_fn() { unsafe <|> }",
             expect![[r#"
                 kw fn
-                kw impl
                 kw trait
+                kw impl
             "#]],
         );
     }
@@ -542,12 +542,12 @@ pub mod future {
         check(
             r#"fn main() { let _ = <|> }"#,
             expect![[r#"
+                kw match
+                kw while
+                kw loop
                 kw if
                 kw if let
-                kw loop
-                kw match
                 kw return
-                kw while
             "#]],
         )
     }
@@ -562,8 +562,8 @@ struct Foo {
 }
 "#,
             expect![[r#"
-                kw pub
                 kw pub(crate)
+                kw pub
             "#]],
         )
     }
@@ -600,12 +600,12 @@ fn foo() {
 }
 "#,
             expect![[r#"
+                kw match
+                kw while
+                kw loop
                 kw if
                 kw if let
-                kw loop
-                kw match
                 kw return
-                kw while
             "#]],
         );
     }
diff --git a/crates/completion/src/completions/mod_.rs b/crates/completion/src/completions/mod_.rs
index c96f84171bc..f77864b7752 100644
--- a/crates/completion/src/completions/mod_.rs
+++ b/crates/completion/src/completions/mod_.rs
@@ -170,8 +170,8 @@ mod tests {
             fn ignored_bar() {}
         "#,
             expect![[r#"
-                md bar;
                 md foo;
+                md bar;
             "#]],
         );
     }
@@ -207,8 +207,8 @@ mod tests {
             fn ignored_bar() {}
         "#,
             expect![[r#"
-                md bar;
                 md foo;
+                md bar;
             "#]],
         );
     }
diff --git a/crates/completion/src/completions/pattern.rs b/crates/completion/src/completions/pattern.rs
index 4f63ff0ef67..0c98e4412e7 100644
--- a/crates/completion/src/completions/pattern.rs
+++ b/crates/completion/src/completions/pattern.rs
@@ -66,10 +66,10 @@ fn foo() {
 }
 "#,
             expect![[r#"
-                st Bar
                 en E
-                ev X   ()
                 ct Z
+                st Bar
+                ev X   ()
                 md m
             "#]],
         );
diff --git a/crates/completion/src/completions/postfix.rs b/crates/completion/src/completions/postfix.rs
index c8ba63cd3be..d6db82a93bb 100644
--- a/crates/completion/src/completions/postfix.rs
+++ b/crates/completion/src/completions/postfix.rs
@@ -315,20 +315,20 @@ fn main() {
 }
 "#,
             expect![[r#"
-                sn box   Box::new(expr)
-                sn call  function(expr)
-                sn dbg   dbg!(expr)
-                sn dbgr  dbg!(&expr)
                 sn if    if expr {}
-                sn let   let
-                sn letm  let mut
-                sn match match expr {}
+                sn while while expr {}
                 sn not   !expr
-                sn ok    Ok(expr)
                 sn ref   &expr
                 sn refm  &mut expr
+                sn match match expr {}
+                sn box   Box::new(expr)
+                sn ok    Ok(expr)
                 sn some  Some(expr)
-                sn while while expr {}
+                sn dbg   dbg!(expr)
+                sn dbgr  dbg!(&expr)
+                sn call  function(expr)
+                sn let   let
+                sn letm  let mut
             "#]],
         );
     }
@@ -347,18 +347,18 @@ fn main() {
 }
 "#,
             expect![[r#"
-                sn box   Box::new(expr)
-                sn call  function(expr)
-                sn dbg   dbg!(expr)
-                sn dbgr  dbg!(&expr)
                 sn if    if expr {}
-                sn match match expr {}
+                sn while while expr {}
                 sn not   !expr
-                sn ok    Ok(expr)
                 sn ref   &expr
                 sn refm  &mut expr
+                sn match match expr {}
+                sn box   Box::new(expr)
+                sn ok    Ok(expr)
                 sn some  Some(expr)
-                sn while while expr {}
+                sn dbg   dbg!(expr)
+                sn dbgr  dbg!(&expr)
+                sn call  function(expr)
             "#]],
         );
     }
@@ -373,17 +373,17 @@ fn main() {
 }
 "#,
             expect![[r#"
+                sn ref   &expr
+                sn refm  &mut expr
+                sn match match expr {}
                 sn box   Box::new(expr)
-                sn call  function(expr)
+                sn ok    Ok(expr)
+                sn some  Some(expr)
                 sn dbg   dbg!(expr)
                 sn dbgr  dbg!(&expr)
+                sn call  function(expr)
                 sn let   let
                 sn letm  let mut
-                sn match match expr {}
-                sn ok    Ok(expr)
-                sn ref   &expr
-                sn refm  &mut expr
-                sn some  Some(expr)
             "#]],
         )
     }
@@ -398,20 +398,20 @@ fn main() {
 }
 "#,
             expect![[r#"
-                sn box   Box::new(expr)
-                sn call  function(expr)
-                sn dbg   dbg!(expr)
-                sn dbgr  dbg!(&expr)
                 sn if    if expr {}
-                sn let   let
-                sn letm  let mut
-                sn match match expr {}
+                sn while while expr {}
                 sn not   !expr
-                sn ok    Ok(expr)
                 sn ref   &expr
                 sn refm  &mut expr
+                sn match match expr {}
+                sn box   Box::new(expr)
+                sn ok    Ok(expr)
                 sn some  Some(expr)
-                sn while while expr {}
+                sn dbg   dbg!(expr)
+                sn dbgr  dbg!(&expr)
+                sn call  function(expr)
+                sn let   let
+                sn letm  let mut
             "#]],
         );
     }
diff --git a/crates/completion/src/completions/qualified_path.rs b/crates/completion/src/completions/qualified_path.rs
index bc23bea3faf..1300f00b2f2 100644
--- a/crates/completion/src/completions/qualified_path.rs
+++ b/crates/completion/src/completions/qualified_path.rs
@@ -199,22 +199,22 @@ use self::{foo::*, bar<|>};
         check_builtin(
             r#"fn main() { let _: <|> = 92; }"#,
             expect![[r#"
+                bt u32
                 bt bool
-                bt char
+                bt u8
+                bt isize
+                bt u16
+                bt u64
+                bt u128
                 bt f32
-                bt f64
                 bt i128
                 bt i16
-                bt i32
+                bt str
                 bt i64
+                bt char
+                bt f64
+                bt i32
                 bt i8
-                bt isize
-                bt str
-                bt u128
-                bt u16
-                bt u32
-                bt u64
-                bt u8
                 bt usize
             "#]],
         );
@@ -279,8 +279,8 @@ struct Spam;
 use crate::Sp<|>
 "#,
             expect![[r#"
-                st Spam
                 md foo
+                st Spam
             "#]],
         );
     }
@@ -296,8 +296,8 @@ struct Spam;
 use crate::{Sp<|>};
 "#,
             expect![[r#"
-                st Spam
                 md foo
+                st Spam
             "#]],
         );
     }
@@ -330,8 +330,8 @@ enum E { Foo, Bar(i32) }
 fn foo() { let _ = E::<|> }
 "#,
             expect![[r#"
-                ev Bar(…) (i32)
                 ev Foo    ()
+                ev Bar(…) (i32)
             "#]],
         );
     }
@@ -353,10 +353,10 @@ impl S {
 fn foo() { let _ = S::<|> }
 "#,
             expect![[r#"
-                ct C    const C: i32 = 42;
-                ta T    type T = i32;
                 fn a()  fn a()
                 me b(…) fn b(&self)
+                ct C    const C: i32 = 42;
+                ta T    type T = i32;
             "#]],
         );
     }
@@ -381,9 +381,9 @@ mod m {
 fn foo() { let _ = S::<|> }
 "#,
             expect![[r#"
+                fn public_method() pub(crate) fn public_method()
                 ct PUBLIC_CONST    pub(crate) const PUBLIC_CONST: u32 = 1;
                 ta PublicType      pub(crate) type PublicType = u32;
-                fn public_method() pub(crate) fn public_method()
             "#]],
         );
     }
@@ -503,14 +503,14 @@ trait Sub: Super {
 fn foo<T: Sub>() { T::<|> }
 "#,
             expect![[r#"
-                ct C2           const C2: ();
-                ct CONST        const CONST: u8;
                 ta SubTy        type SubTy;
                 ta Ty           type Ty;
-                fn func()       fn func()
-                me method(…)    fn method(&self)
+                ct C2           const C2: ();
                 fn subfunc()    fn subfunc()
                 me submethod(…) fn submethod(&self)
+                ct CONST        const CONST: u8;
+                fn func()       fn func()
+                me method(…)    fn method(&self)
             "#]],
         );
     }
@@ -543,12 +543,12 @@ impl<T> Sub for Wrap<T> {
 }
 "#,
             expect![[r#"
-                ct C2           const C2: () = ();
-                ct CONST        const CONST: u8 = 0;
                 ta SubTy        type SubTy;
                 ta Ty           type Ty;
+                ct CONST        const CONST: u8 = 0;
                 fn func()       fn func()
                 me method(…)    fn method(&self)
+                ct C2           const C2: () = ();
                 fn subfunc()    fn subfunc()
                 me submethod(…) fn submethod(&self)
             "#]],
@@ -567,8 +567,8 @@ impl T { fn bar() {} }
 fn main() { T::<|>; }
 "#,
             expect![[r#"
-                fn bar() fn bar()
                 fn foo() fn foo()
+                fn bar() fn bar()
             "#]],
         );
     }
@@ -583,9 +583,9 @@ macro_rules! foo { () => {} }
 fn main() { let _ = crate::<|> }
         "#,
             expect![[r##"
+                fn main()  fn main()
                 ma foo!(…) #[macro_export]
                 macro_rules! foo
-                fn main()  fn main()
             "##]],
         );
     }
@@ -603,8 +603,8 @@ mod a {
 }
 "#,
             expect![[r#"
-                ct A
                 md b
+                ct A
             "#]],
         );
     }
@@ -628,8 +628,8 @@ mod p {
 "#,
             expect![[r#"
                 ct RIGHT_CONST
-                st RightType
                 fn right_fn()  fn wrong_fn()
+                st RightType
             "#]],
         );
 
@@ -675,8 +675,8 @@ fn main() { m!(self::f<|>); }
 fn foo() {}
 "#,
             expect![[r#"
-                fn foo()  fn foo()
                 fn main() fn main()
+                fn foo()  fn foo()
             "#]],
         );
     }
@@ -747,8 +747,8 @@ fn main() {
 }
 "#,
             expect![[r#"
-                fn foo(…) fn foo(a: i32, b: i32)
                 fn main() fn main()
+                fn foo(…) fn foo(a: i32, b: i32)
             "#]],
         );
     }
diff --git a/crates/completion/src/completions/record.rs b/crates/completion/src/completions/record.rs
index eaa44c97d1f..91bf4a8ad95 100644
--- a/crates/completion/src/completions/record.rs
+++ b/crates/completion/src/completions/record.rs
@@ -94,9 +94,9 @@ fn process(f: S) {
         check_snippet(
             test_code,
             expect![[r#"
-                fd ..Default::default()
                 sn pd
                 sn ppd
+                fd ..Default::default()
             "#]],
         );
     }
@@ -160,8 +160,8 @@ fn process(e: E) {
 }
 "#,
             expect![[r#"
-                fd bar ()
                 fd foo u32
+                fd bar ()
             "#]],
         );
     }
diff --git a/crates/completion/src/completions/snippet.rs b/crates/completion/src/completions/snippet.rs
index 6f0c000781c..84259013002 100644
--- a/crates/completion/src/completions/snippet.rs
+++ b/crates/completion/src/completions/snippet.rs
@@ -105,9 +105,9 @@ mod tests {
 }
 "#,
             expect![[r#"
-                sn macro_rules
-                sn tfn (Test function)
                 sn tmod (Test module)
+                sn tfn (Test function)
+                sn macro_rules
             "#]],
         )
     }
diff --git a/crates/completion/src/completions/trait_impl.rs b/crates/completion/src/completions/trait_impl.rs
index e2fe44aff9f..c4e0d06698f 100644
--- a/crates/completion/src/completions/trait_impl.rs
+++ b/crates/completion/src/completions/trait_impl.rs
@@ -266,10 +266,10 @@ impl Test for T {
 }
 "#,
             expect![["
+ta type TestType = \n\
 ct const TEST_CONST: u16 = \n\
 fn fn test()
-ta type TestType = \n\
-            "]],
+"]],
         );
     }
 
diff --git a/crates/completion/src/completions/unqualified_path.rs b/crates/completion/src/completions/unqualified_path.rs
index 93869f92ef9..099ffb4d48b 100644
--- a/crates/completion/src/completions/unqualified_path.rs
+++ b/crates/completion/src/completions/unqualified_path.rs
@@ -1,7 +1,7 @@
 //! Completion of names from the current scope, e.g. locals and imported items.
 
 use either::Either;
-use hir::{Adt, ModuleDef, ScopeDef, Type};
+use hir::{Adt, ModPath, ModuleDef, ScopeDef, Type};
 use ide_db::helpers::insert_use::ImportScope;
 use ide_db::imports_locator;
 use syntax::AstNode;
@@ -146,13 +146,9 @@ fn fuzzy_completion(acc: &mut Completions, ctx: &CompletionContext) -> Option<()
     .filter(|(mod_path, _)| mod_path.len() > 1)
     .collect::<Vec<_>>();
 
+    let user_input_lowercased = potential_import_name.to_lowercase();
     all_mod_paths.sort_by_cached_key(|(mod_path, _)| {
-        if let Some(name) = mod_path.segments.last().map(|name| name.to_string().to_lowercase()) {
-            if name.contains(&potential_import_name.to_lowercase()) {
-                return 0;
-            }
-        }
-        1
+        compute_fuzzy_completion_order_key(mod_path, &user_input_lowercased)
     });
 
     acc.add_all(all_mod_paths.into_iter().filter_map(|(import_path, definition)| {
@@ -165,21 +161,48 @@ fn fuzzy_completion(acc: &mut Completions, ctx: &CompletionContext) -> Option<()
     Some(())
 }
 
+fn compute_fuzzy_completion_order_key(
+    proposed_mod_path: &ModPath,
+    user_input_lowercased: &str,
+) -> usize {
+    mark::hit!(certain_fuzzy_order_test);
+    let proposed_import_name = match proposed_mod_path.segments.last() {
+        Some(name) => name.to_string().to_lowercase(),
+        None => return usize::MAX,
+    };
+    match proposed_import_name.match_indices(user_input_lowercased).next() {
+        Some((first_matching_index, _)) => first_matching_index,
+        None => usize::MAX,
+    }
+}
+
 #[cfg(test)]
 mod tests {
     use expect_test::{expect, Expect};
     use test_utils::mark;
 
     use crate::{
-        test_utils::{check_edit, check_edit_with_config, completion_list},
+        test_utils::{check_edit, check_edit_with_config, completion_list_with_config},
         CompletionConfig, CompletionKind,
     };
 
     fn check(ra_fixture: &str, expect: Expect) {
-        let actual = completion_list(ra_fixture, CompletionKind::Reference);
+        check_with_config(CompletionConfig::default(), ra_fixture, expect);
+    }
+
+    fn check_with_config(config: CompletionConfig, ra_fixture: &str, expect: Expect) {
+        let actual = completion_list_with_config(config, ra_fixture, CompletionKind::Reference);
         expect.assert_eq(&actual)
     }
 
+    fn fuzzy_completion_config() -> CompletionConfig {
+        let mut completion_config = CompletionConfig::default();
+        completion_config
+            .active_resolve_capabilities
+            .insert(crate::CompletionResolveCapability::AdditionalTextEdits);
+        completion_config
+    }
+
     #[test]
     fn self_fulfilling_completion() {
         mark::check!(self_fulfilling_completion);
@@ -255,9 +278,9 @@ fn quux(x: i32) {
 }
 "#,
             expect![[r#"
-                fn quux(…) fn quux(x: i32)
-                bn x       i32
                 bn y       i32
+                bn x       i32
+                fn quux(…) fn quux(x: i32)
             "#]],
         );
     }
@@ -277,8 +300,8 @@ fn quux() {
 }
 "#,
             expect![[r#"
-                bn a
                 bn b      i32
+                bn a
                 fn quux() fn quux()
             "#]],
         );
@@ -293,8 +316,8 @@ fn quux() {
 }
 "#,
             expect![[r#"
-                fn quux() fn quux()
                 bn x
+                fn quux() fn quux()
             "#]],
         );
     }
@@ -335,9 +358,9 @@ fn main() {
         check(
             r#"struct S<T> { x: <|>}"#,
             expect![[r#"
-                st S<…>
                 tp Self
                 tp T
+                st S<…>
             "#]],
         );
     }
@@ -362,9 +385,9 @@ enum E {}
 fn quux() { <|> }
 "#,
             expect![[r#"
-                en E
                 st S
                 fn quux() fn quux()
+                en E
             "#]],
         );
     }
@@ -416,8 +439,8 @@ mod m {
 }
 "#,
             expect![[r#"
-                st Bar
                 fn quux() fn quux()
+                st Bar
             "#]],
         );
     }
@@ -462,8 +485,8 @@ fn foo() {
         check(
             r#"impl S { fn foo(&self) { <|> } }"#,
             expect![[r#"
-                tp Self
                 bn self &{unknown}
+                tp Self
             "#]],
         );
     }
@@ -482,9 +505,9 @@ use prelude::*;
 mod prelude { struct Option; }
 "#,
             expect![[r#"
-                st Option
                 fn foo()  fn foo()
                 md std
+                st Option
             "#]],
         );
     }
@@ -509,10 +532,10 @@ use prelude::*;
 mod prelude { struct String; }
 "#,
             expect![[r#"
-                st String
-                md core
                 fn foo()  fn foo()
                 md std
+                md core
+                st String
             "#]],
         );
     }
@@ -538,13 +561,13 @@ mod m2 {
 fn main() { let v = <|> }
 "#,
             expect![[r##"
-                ma bar!(…) macro_rules! bar
+                md m1
                 ma baz!(…) #[macro_export]
                 macro_rules! baz
-                ma foo!(…) macro_rules! foo
-                md m1
-                md m2
                 fn main()  fn main()
+                md m2
+                ma bar!(…) macro_rules! bar
+                ma foo!(…) macro_rules! foo
             "##]],
         );
     }
@@ -557,8 +580,8 @@ macro_rules! foo { () => {} }
 fn foo() { <|> }
 "#,
             expect![[r#"
-                ma foo!(…) macro_rules! foo
                 fn foo()   fn foo()
+                ma foo!(…) macro_rules! foo
             "#]],
         );
     }
@@ -571,8 +594,8 @@ macro_rules! foo { () => {} }
 fn main() { let x: <|> }
 "#,
             expect![[r#"
-                ma foo!(…) macro_rules! foo
                 fn main()  fn main()
+                ma foo!(…) macro_rules! foo
             "#]],
         );
     }
@@ -585,8 +608,8 @@ macro_rules! foo { () => {} }
 fn main() { <|> }
 "#,
             expect![[r#"
-                ma foo!(…) macro_rules! foo
                 fn main()  fn main()
+                ma foo!(…) macro_rules! foo
             "#]],
         );
     }
@@ -618,10 +641,10 @@ fn quux(x: i32) {
 }
 "#,
             expect![[r#"
-                ma m!(…)   macro_rules! m
-                fn quux(…) fn quux(x: i32)
-                bn x       i32
                 bn y       i32
+                bn x       i32
+                fn quux(…) fn quux(x: i32)
+                ma m!(…)   macro_rules! m
             "#]],
         );
     }
@@ -637,10 +660,10 @@ fn quux(x: i32) {
 }
 ",
             expect![[r#"
-                ma m!(…)   macro_rules! m
-                fn quux(…) fn quux(x: i32)
-                bn x       i32
                 bn y       i32
+                bn x       i32
+                fn quux(…) fn quux(x: i32)
+                ma m!(…)   macro_rules! m
             "#]],
         );
     }
@@ -656,10 +679,10 @@ fn quux(x: i32) {
 }
 "#,
             expect![[r#"
-                ma m!(…)   macro_rules! m
-                fn quux(…) fn quux(x: i32)
-                bn x       i32
                 bn y       i32
+                bn x       i32
+                fn quux(…) fn quux(x: i32)
+                ma m!(…)   macro_rules! m
             "#]],
         );
     }
@@ -673,8 +696,8 @@ use spam::Quux;
 fn main() { <|> }
 "#,
             expect![[r#"
-                ?? Quux
                 fn main() fn main()
+                ?? Quux
             "#]],
         );
     }
@@ -690,10 +713,10 @@ fn main() {
 }
 "#,
             expect![[r#"
-                en Foo
                 ev Foo::Bar  ()
                 ev Foo::Baz  ()
                 ev Foo::Quux ()
+                en Foo
             "#]],
         )
     }
@@ -710,10 +733,10 @@ fn main() {
 }
 "#,
             expect![[r#"
-                en Foo
                 ev Foo::Bar  ()
                 ev Foo::Baz  ()
                 ev Foo::Quux ()
+                en Foo
             "#]],
         )
     }
@@ -726,10 +749,10 @@ enum Foo { Bar, Baz, Quux }
 fn main() { let foo: Foo = Q<|> }
 "#,
             expect![[r#"
-                en Foo
                 ev Foo::Bar  ()
                 ev Foo::Baz  ()
                 ev Foo::Quux ()
+                en Foo
                 fn main()    fn main()
             "#]],
         )
@@ -743,9 +766,9 @@ mod m { pub enum E { V } }
 fn f() -> m::E { V<|> }
 "#,
             expect![[r#"
-                fn f()     fn f() -> m::E
-                md m
                 ev m::E::V ()
+                md m
+                fn f()     fn f() -> m::E
             "#]],
         )
     }
@@ -772,22 +795,17 @@ struct MyStruct {}
 impl My<|>
 "#,
             expect![[r#"
-                st MyStruct
-                tt MyTrait
                 tp Self
+                tt MyTrait
+                st MyStruct
             "#]],
         )
     }
 
     #[test]
     fn function_fuzzy_completion() {
-        let mut completion_config = CompletionConfig::default();
-        completion_config
-            .active_resolve_capabilities
-            .insert(crate::CompletionResolveCapability::AdditionalTextEdits);
-
         check_edit_with_config(
-            completion_config,
+            fuzzy_completion_config(),
             "stdin",
             r#"
 //- /lib.rs crate:dep
@@ -812,13 +830,8 @@ fn main() {
 
     #[test]
     fn macro_fuzzy_completion() {
-        let mut completion_config = CompletionConfig::default();
-        completion_config
-            .active_resolve_capabilities
-            .insert(crate::CompletionResolveCapability::AdditionalTextEdits);
-
         check_edit_with_config(
-            completion_config,
+            fuzzy_completion_config(),
             "macro_with_curlies!",
             r#"
 //- /lib.rs crate:dep
@@ -845,13 +858,8 @@ fn main() {
 
     #[test]
     fn struct_fuzzy_completion() {
-        let mut completion_config = CompletionConfig::default();
-        completion_config
-            .active_resolve_capabilities
-            .insert(crate::CompletionResolveCapability::AdditionalTextEdits);
-
         check_edit_with_config(
-            completion_config,
+            fuzzy_completion_config(),
             "ThirdStruct",
             r#"
 //- /lib.rs crate:dep
@@ -877,4 +885,44 @@ fn main() {
 "#,
         );
     }
+
+    #[test]
+    fn fuzzy_completions_come_in_specific_order() {
+        mark::check!(certain_fuzzy_order_test);
+        check_with_config(
+            fuzzy_completion_config(),
+            r#"
+//- /lib.rs crate:dep
+pub struct FirstStruct;
+pub mod some_module {
+    // already imported, omitted
+    pub struct SecondStruct;
+    // does not contain all letters from the query, omitted
+    pub struct UnrelatedOne;
+    // contains all letters from the query, but not in sequence, displayed last
+    pub struct ThiiiiiirdStruct;
+    // contains all letters from the query, but not in the beginning, displayed second
+    pub struct AfterThirdStruct;
+    // contains all letters from the query in the begginning, displayed first
+    pub struct ThirdStruct;
+}
+
+//- /main.rs crate:main deps:dep
+use dep::{FirstStruct, some_module::SecondStruct};
+
+fn main() {
+    hir<|>
+}
+"#,
+            expect![[r#"
+                fn main()           fn main()
+                st SecondStruct
+                st FirstStruct
+                md dep
+                st dep::some_module::ThirdStruct
+                st dep::some_module::AfterThirdStruct
+                st dep::some_module::ThiiiiiirdStruct
+            "#]],
+        );
+    }
 }
diff --git a/crates/completion/src/test_utils.rs b/crates/completion/src/test_utils.rs
index db896b2df23..eb0c16f52bd 100644
--- a/crates/completion/src/test_utils.rs
+++ b/crates/completion/src/test_utils.rs
@@ -47,9 +47,8 @@ pub(crate) fn completion_list_with_config(
     code: &str,
     kind: CompletionKind,
 ) -> String {
-    let mut kind_completions: Vec<CompletionItem> =
+    let kind_completions: Vec<CompletionItem> =
         get_all_items(config, code).into_iter().filter(|c| c.completion_kind == kind).collect();
-    kind_completions.sort_by_key(|c| c.label().to_owned());
     let label_width = kind_completions
         .iter()
         .map(|it| monospace_width(it.label()))