Merge #7904

7904: Improved completion sorting r=JoshMcguigan a=JoshMcguigan

I was working on extending #3954 to apply completion scores in more places (I'll have another PR open for that soon) when I discovered that actually completion sorting was not working for me at all in `coc.nvim`. This led me down a bit of a rabbit hole of how coc and vs code each sort completion items.

Before this PR, rust-analyzer was setting the `sortText` field on completion items to `None` if we hadn't applied any completion score for that item, or to the label of the item with a leading whitespace character if we had applied any completion score. Completion score is defined in rust-analyzer as an enum with two variants, `TypeMatch` and `TypeAndNameMatch`. 

In vs code the above strategy works, because if `sortText` isn't set [they default it to the label](https://github.com/microsoft/vscode/commit/b4ead4ed665e1ce2e58d8329c682f78da2d4e89d). However, coc [does not do this](https://github.com/neoclide/coc.nvim/blob/e211e361475a38b146a903b9b02343551c6cd372/src/completion/complete.ts#L245).

I was going to file a bug report against coc, but I read the [LSP spec for the `sortText` field](https://microsoft.github.io/language-server-protocol/specifications/specification-current/#textDocument_completion) and I feel like it is ambiguous and coc could claim what they do is a valid interpretation of the spec.

Further, the existing rust-analyzer behavior of prepending a leading whitespace character for completion items with any completion score does not handle sorting `TypeAndNameMatch` completions above `TypeMatch` completions. They were both being treated the same.

The first change this PR makes is to set the `sortText` field to either "1" for `TypeAndNameMatch` completions, "2" for `TypeMatch` completions, or "3" for completions which are neither of those. This change works around the potential ambiguity in the LSP spec and fixes completion sorting for users of coc. It also allows `TypeAndNameMatch` items to be sorted above just `TypeMatch` items (of course both of these will be sorted above completion items without a score). 

The second change this PR makes is to use the actual completion scores for ref matches. The existing code ignored the actual score and always assumed these would be a high priority completion item.

#### Before

Here coc just sorts based on how close the items are in the file.

![image](https://user-images.githubusercontent.com/22216761/110249880-46063580-7f2d-11eb-9233-91a2bbd48238.png)

#### After

Here we correctly get `zzz` first, since that is both a type and name match. Then we get `ccc` which is just a type match.

![image](https://user-images.githubusercontent.com/22216761/110249883-4e5e7080-7f2d-11eb-9269-a3bc133fdee7.png)


Co-authored-by: Josh Mcguigan <[email protected]>

3 files changed, 117 insertions, 33 deletions

diff --git a/crates/ide_completion/src/item.rs b/crates/ide_completion/src/item.rs
index cf1aaa131..3febab32b 100644
--- a/crates/ide_completion/src/item.rs
+++ b/crates/ide_completion/src/item.rs
@@ -70,7 +70,7 @@ pub struct CompletionItem {
     /// Note that Relevance ignores fuzzy match score. We compute Relevance for
     /// all possible items, and then separately build an ordered completion list
     /// based on relevance and fuzzy matching with the already typed identifier.
-    relevance: Relevance,
+    relevance: CompletionRelevance,
 
     /// Indicates that a reference or mutable reference to this variable is a
     /// possible match.
@@ -107,9 +107,11 @@ impl fmt::Debug for CompletionItem {
         if self.deprecated {
             s.field("deprecated", &true);
         }
-        if self.relevance.is_relevant() {
+
+        if self.relevance != CompletionRelevance::default() {
             s.field("relevance", &self.relevance);
         }
+
         if let Some(mutability) = &self.ref_match {
             s.field("ref_match", &format!("&{}", mutability.as_keyword_for_ref()));
         }
@@ -120,16 +122,8 @@ impl fmt::Debug for CompletionItem {
     }
 }
 
-#[derive(Debug, Clone, Copy, Ord, PartialOrd, Eq, PartialEq)]
-pub enum CompletionScore {
-    /// If only type match
-    TypeMatch,
-    /// If type and name match
-    TypeAndNameMatch,
-}
-
 #[derive(Debug, Clone, Copy, Ord, PartialOrd, Eq, PartialEq, Default)]
-pub struct Relevance {
+pub struct CompletionRelevance {
     /// This is set in cases like these:
     ///
     /// ```
@@ -152,9 +146,34 @@ pub struct Relevance {
     pub exact_type_match: bool,
 }
 
-impl Relevance {
+impl CompletionRelevance {
+    /// Provides a relevance score. Higher values are more relevant.
+    ///
+    /// The absolute value of the relevance score is not meaningful, for
+    /// example a value of 0 doesn't mean "not relevant", rather
+    /// it means "least relevant". The score value should only be used
+    /// for relative ordering.
+    ///
+    /// See is_relevant if you need to make some judgement about score
+    /// in an absolute sense.
+    pub fn score(&self) -> u32 {
+        let mut score = 0;
+
+        if self.exact_name_match {
+            score += 1;
+        }
+        if self.exact_type_match {
+            score += 1;
+        }
+
+        score
+    }
+
+    /// Returns true when the score for this threshold is above
+    /// some threshold such that we think it is especially likely
+    /// to be relevant.
     pub fn is_relevant(&self) -> bool {
-        self != &Relevance::default()
+        self.score() > 0
     }
 }
 
@@ -249,7 +268,7 @@ impl CompletionItem {
             text_edit: None,
             deprecated: false,
             trigger_call_info: None,
-            relevance: Relevance::default(),
+            relevance: CompletionRelevance::default(),
             ref_match: None,
             import_to_add: None,
         }
@@ -292,7 +311,7 @@ impl CompletionItem {
         self.deprecated
     }
 
-    pub fn relevance(&self) -> Relevance {
+    pub fn relevance(&self) -> CompletionRelevance {
         self.relevance
     }
 
@@ -300,8 +319,14 @@ impl CompletionItem {
         self.trigger_call_info
     }
 
-    pub fn ref_match(&self) -> Option<Mutability> {
-        self.ref_match
+    pub fn ref_match(&self) -> Option<(Mutability, CompletionRelevance)> {
+        // Relevance of the ref match should be the same as the original
+        // match, but with exact type match set because self.ref_match
+        // is only set if there is an exact type match.
+        let mut relevance = self.relevance;
+        relevance.exact_type_match = true;
+
+        self.ref_match.map(|mutability| (mutability, relevance))
     }
 
     pub fn import_to_add(&self) -> Option<&ImportEdit> {
@@ -349,7 +374,7 @@ pub(crate) struct Builder {
     text_edit: Option<TextEdit>,
     deprecated: bool,
     trigger_call_info: Option<bool>,
-    relevance: Relevance,
+    relevance: CompletionRelevance,
     ref_match: Option<Mutability>,
 }
 
@@ -457,7 +482,7 @@ impl Builder {
         self.deprecated = deprecated;
         self
     }
-    pub(crate) fn set_relevance(&mut self, relevance: Relevance) -> &mut Builder {
+    pub(crate) fn set_relevance(&mut self, relevance: CompletionRelevance) -> &mut Builder {
         self.relevance = relevance;
         self
     }
@@ -474,3 +499,63 @@ impl Builder {
         self
     }
 }
+
+#[cfg(test)]
+mod tests {
+    use itertools::Itertools;
+    use test_utils::assert_eq_text;
+
+    use super::CompletionRelevance;
+
+    /// Check that these are CompletionRelevance are sorted in ascending order
+    /// by their relevance score.
+    ///
+    /// We want to avoid making assertions about the absolute score of any
+    /// item, but we do want to assert whether each is >, <, or == to the
+    /// others.
+    ///
+    /// If provided vec![vec![a], vec![b, c], vec![d]], then this will assert:
+    ///     a.score < b.score == c.score < d.score
+    fn check_relevance_score_ordered(expected_relevance_order: Vec<Vec<CompletionRelevance>>) {
+        let expected = format!("{:#?}", &expected_relevance_order);
+
+        let actual_relevance_order = expected_relevance_order
+            .into_iter()
+            .flatten()
+            .map(|r| (r.score(), r))
+            .sorted_by_key(|(score, _r)| *score)
+            .fold(
+                (u32::MIN, vec![vec![]]),
+                |(mut currently_collecting_score, mut out), (score, r)| {
+                    if currently_collecting_score == score {
+                        out.last_mut().unwrap().push(r);
+                    } else {
+                        currently_collecting_score = score;
+                        out.push(vec![r]);
+                    }
+                    (currently_collecting_score, out)
+                },
+            )
+            .1;
+
+        let actual = format!("{:#?}", &actual_relevance_order);
+
+        assert_eq_text!(&expected, &actual);
+    }
+
+    #[test]
+    fn relevance_score() {
+        // This test asserts that the relevance score for these items is ascending, and
+        // that any items in the same vec have the same score.
+        let expected_relevance_order = vec![
+            vec![CompletionRelevance::default()],
+            vec![
+                CompletionRelevance { exact_name_match: true, ..CompletionRelevance::default() },
+                CompletionRelevance { exact_type_match: true, ..CompletionRelevance::default() },
+            ],
+            vec![CompletionRelevance { exact_name_match: true, exact_type_match: true }],
+        ];
+
+        check_relevance_score_ordered(expected_relevance_order);
+    }
+}
diff --git a/crates/ide_completion/src/lib.rs b/crates/ide_completion/src/lib.rs
index d46f521a0..263554ecf 100644
--- a/crates/ide_completion/src/lib.rs
+++ b/crates/ide_completion/src/lib.rs
@@ -23,10 +23,7 @@ use crate::{completions::Completions, context::CompletionContext, item::Completi
 
 pub use crate::{
     config::CompletionConfig,
-    item::{
-        CompletionItem, CompletionItemKind, CompletionScore, ImportEdit, InsertTextFormat,
-        Relevance,
-    },
+    item::{CompletionItem, CompletionItemKind, CompletionRelevance, ImportEdit, InsertTextFormat},
 };
 
 //FIXME: split the following feature into fine-grained features.
diff --git a/crates/ide_completion/src/render.rs b/crates/ide_completion/src/render.rs
index f7f9084d9..db31896e5 100644
--- a/crates/ide_completion/src/render.rs
+++ b/crates/ide_completion/src/render.rs
@@ -20,7 +20,7 @@ use ide_db::{
 use syntax::TextRange;
 
 use crate::{
-    item::{ImportEdit, Relevance},
+    item::{CompletionRelevance, ImportEdit},
     CompletionContext, CompletionItem, CompletionItemKind, CompletionKind,
 };
 
@@ -322,9 +322,9 @@ impl<'a> Render<'a> {
     }
 }
 
-fn compute_relevance(ctx: &RenderContext, ty: &Type, name: &str) -> Option<Relevance> {
+fn compute_relevance(ctx: &RenderContext, ty: &Type, name: &str) -> Option<CompletionRelevance> {
     let (expected_name, expected_type) = ctx.expected_name_and_type()?;
-    let mut res = Relevance::default();
+    let mut res = CompletionRelevance::default();
     res.exact_type_match = ty == &expected_type;
     res.exact_name_match = name == &expected_name;
     Some(res)
@@ -338,7 +338,7 @@ mod tests {
 
     use crate::{
         test_utils::{check_edit, do_completion, get_all_items, TEST_CONFIG},
-        CompletionKind, Relevance,
+        CompletionKind, CompletionRelevance,
     };
 
     fn check(ra_fixture: &str, expect: Expect) {
@@ -347,12 +347,14 @@ mod tests {
     }
 
     fn check_relevance(ra_fixture: &str, expect: Expect) {
-        fn display_relevance(relevance: Relevance) -> &'static str {
+        fn display_relevance(relevance: CompletionRelevance) -> &'static str {
             match relevance {
-                Relevance { exact_type_match: true, exact_name_match: true } => "[type+name]",
-                Relevance { exact_type_match: true, exact_name_match: false } => "[type]",
-                Relevance { exact_type_match: false, exact_name_match: true } => "[name]",
-                Relevance { exact_type_match: false, exact_name_match: false } => "[]",
+                CompletionRelevance { exact_type_match: true, exact_name_match: true } => {
+                    "[type+name]"
+                }
+                CompletionRelevance { exact_type_match: true, exact_name_match: false } => "[type]",
+                CompletionRelevance { exact_type_match: false, exact_name_match: true } => "[name]",
+                CompletionRelevance { exact_type_match: false, exact_name_match: false } => "[]",
             }
         }
 
@@ -975,7 +977,7 @@ fn main() {
                             Local,
                         ),
                         detail: "S",
-                        relevance: Relevance {
+                        relevance: CompletionRelevance {
                             exact_name_match: true,
                             exact_type_match: false,
                         },