[clangd] Make completion scores use 0-1 floats internally.

[sammccall]

Summary

This scale is much easier to mix with other signals, such as fuzzy match strength.
Mostly NFC, but it does reorder some low-priority items that get folded together at a score of 0 (see completion-qualifiers.test).
Removed the exact sortText from the testcases, because it's the ranking that we want to test.

[hokein]

A few comments based on our discussion.

clangd/ClangdUnit.cpp

390–391

example

419

nit: mention that if a < b, encodeFloat(a) < encodeFloat(b)

420

I think we'd better have unittest for this function.

426

Would be nice to explain more what we do here: we are trying to remap from the signed range [INT_MIN, INT_MAX] to the unsigned range [0, UINT_MAX], so that we can compare them via string literal comparison.

428

U ^ SignBit

test/clangd/completion-items-kinds.test

1

an off-topic comment: why not using -pretty in this test?

[sammccall]

Thanks for the quick review, took me a while to get back to this but I do care about it!

clangd/ClangdUnit.cpp

390–391

Done, also spelled out more what's going on here.

420

I'd discussed this briefly with Ilya and we weren't sure it was worthwhile.
This is a pretty deep implementation detail - would you expose the function from ClangdUnit? Protocol?

426

Turns out the explanation was slightly wrong (but the implementation right, because I lifted it from a trusted source :-)

Spelled this out some more. (Also sign-magnitude is a bit easier to understand that 2s complement)

428

This matches my old explanation but isn't correct for sign-magnitude.

test/clangd/completion-items-kinds.test

1

Because of the old check-dag when we didn't want to assert the order.

It's still clumsy to express incomplete multiline assertions due to FileCheck limitations though. Given the amount of test merge conflicts i'm looking at, I'd rather not change this in this patch...

[sammccall]

address review comments

[hokein]

LGTM

clangd/ClangdUnit.cpp

428

Well, I see! You are right. The implement is correct here.

clangd/ClangdUnit.cpp

 
 /// A scored code completion result.
 /// It may be promoted to a CompletionItem if it's among the top-ranked results.
 struct CompletionCandidate {
   CompletionCandidate(CodeCompletionResult &Result)
       : Result(&Result), Score(score(Result)) {}
 
   CodeCompletionResult *Result;
-  // Higher score is worse. FIXME: use a more natural scale!
-  int Score;
+  float Score; // 0 to 1, higher is better.
 
   // Comparison reflects rank: better candidates are smaller.
   bool operator<(const CompletionCandidate &C) const {
     if (Score != C.Score)
-      return Score < C.Score;
+      return Score > C.Score;
     return *Result < *C.Result;
   }
 
+  // Returns a string that sorts in the same order as operator<, for LSP.
+  // Conceptually, this is [-Score, Name]. We convert -Score to an integer, and
+  // hex-encode it for readability. Example: [0.5, "foo"] -> "41000000foo"
   std::string sortText() const {
-    // Fill in the sortText of the CompletionItem.
-    assert(Score <= 999999 && "Expecting score to have at most 6-digits");
     std::string S, NameStorage;
-    StringRef Name = Result->getOrderedName(NameStorage);
-    llvm::raw_string_ostream(S)
-        << llvm::format("%06d%.*s", Score, Name.size(), Name.data());
-    return S;
+    llvm::raw_string_ostream OS(S);
+    write_hex(OS, encodeFloat(-Score), llvm::HexPrintStyle::Lower,
+              /*Width=*/2 * sizeof(Score));
+    OS << Result->getOrderedName(NameStorage);
+    return OS.str();
   }
 
 private:
-  static int score(const CodeCompletionResult &Result) {
-    int Score = Result.Priority;
-    // Fill in the sortText of the CompletionItem.
-    assert(Score <= 99999 && "Expecting code completion result "
-                             "priority to have at most 5-digits");
+  static float score(const CodeCompletionResult &Result) {
+    // Priority 80 is a really bad score.
+    float Score = 1 - std::min<float>(80, Result.Priority) / 80;
 
-    const int Penalty = 100000;
     switch (static_cast<CXAvailabilityKind>(Result.Availability)) {
     case CXAvailability_Available:
       // No penalty.
       break;
     case CXAvailability_Deprecated:
-      Score += Penalty;
+      Score *= 0.1;
       break;
     case CXAvailability_NotAccessible:
-      Score += 2 * Penalty;
-      break;
     case CXAvailability_NotAvailable:
-      Score += 3 * Penalty;
+      Score = 0;
       break;
     }
     return Score;
   }
+
+  // Produces an integer that sorts in the same order as F.
+  // That is: a < b <==> encodeFloat(a) < encodeFloat(b).
+  static uint32_t encodeFloat(float F) {
+    static_assert(std::numeric_limits<float>::is_iec559, "");
+    static_assert(sizeof(float) == sizeof(uint32_t), "");
+    constexpr uint32_t TopBit = ~(~uint32_t{0} >> 1);
+
+    // Get the bits of the float. Endianness is the same as for integers.
+    uint32_t U;
+    memcpy(&U, &F, sizeof(float));
+    // IEEE 754 floats compare like sign-magnitude integers.
+    if (U & TopBit)  // Negative float.
+      return 0 - U;  // Map onto the low half of integers, order reversed.
+    return U + SignBit; // Positive floats map onto the high half of integers.
+  }
 };
 
 class CompletionItemsCollector : public CodeCompleteConsumer {
 public:
   CompletionItemsCollector(const clangd::CodeCompleteOptions &CodeCompleteOpts,
                            CompletionList &Items)
       : CodeCompleteConsumer(CodeCompleteOpts.getClangCompleteOpts(),
                              /*OutputIsBinary=*/false),

test/clangd/authority-less-uri.test

 # CHECK-NEXT:  "result": {
 # CHECK-NEXT:    "isIncomplete": false,
 # CHECK-NEXT:    "items": [
 #      CHECK:        "filterText": "fake",
 # CHECK-NEXT:        "insertText": "fake",
 # CHECK-NEXT:        "insertTextFormat": 1,
 # CHECK-NEXT:        "kind": 7,
 # CHECK-NEXT:        "label": "fake::",
-# CHECK-NEXT:        "sortText": "000075fake"
+# CHECK-NEXT:        "sortText": "{{.*}}fake"
 #      CHECK:    ]
 # CHECK-NEXT:  }
 Content-Length: 172
 
 {"jsonrpc":"2.0","id":2,"method":"textDocument/completion","params":{"textDocument":{"uri":"file:///main.cpp"},"uri":"file:///main.cpp","position":{"line":3,"character":5}}}
 # Test params parsing in the presence of a 1.x-compatible client (inlined "uri")
 #
 #      CHECK:  "id": 2,
 # CHECK-NEXT:  "jsonrpc": "2.0",
 # CHECK-NEXT:  "result": {
 # CHECK-NEXT:    "isIncomplete": false,
 # CHECK-NEXT:    "items": [
 #      CHECK:        "filterText": "fake",
 # CHECK-NEXT:        "insertText": "fake",
 # CHECK-NEXT:        "insertTextFormat": 1,
 # CHECK-NEXT:        "kind": 7,
 # CHECK-NEXT:        "label": "fake::",
-# CHECK-NEXT:        "sortText": "000075fake"
+# CHECK-NEXT:        "sortText": "{{.*}}fake"
 #      CHECK:    ]
 # CHECK-NEXT:  }
 Content-Length: 44
 
 {"jsonrpc":"2.0","id":3,"method":"shutdown"}
 Content-Length: 33
 
 {"jsonrpc":"2.0":"method":"exit"}

test/clangd/completion-items-kinds.test

 # RUN: clangd -enable-snippets -run-synchronously < %s | FileCheck %s
 # It is absolutely vital that this file has CRLF line endings.
 #
 Content-Length: 125
 
 {"jsonrpc":"2.0","id":0,"method":"initialize","params":{"processId":123,"rootPath":"clangd","capabilities":{},"trace":"off"}}
 Content-Length: 220
 
 {"jsonrpc":"2.0","method":"textDocument/didOpen","params":{"textDocument":{"uri":"file:///main.cpp","languageId":"cpp","version":1,"text":"#define MACRO X\nint variable;\nstruct Struct {};\n int function();\nint X = "}}}
 Content-Length: 148
 
 {"jsonrpc":"2.0","id":1,"method":"textDocument/completion","params":{"textDocument":{"uri":"file:///main.cpp"},"position":{"line":4,"character":7}}}
 Content-Length: 58
 # CHECK: {"id":1,"jsonrpc":"2.0","result":{"isIncomplete":false,"items":
 #
-# Keyword
-# CHECK-DAG: {"filterText":"int","insertText":"int","insertTextFormat":1,"kind":14,"label":"int","sortText":"000050int"}
+# Function
+# CHECK: {"detail":"int","filterText":"function","insertText":"function()","insertTextFormat":1,"kind":3,"label":"function()","sortText":"{{.*}}function"}
+#
+# Variable
+# CHECK: {"detail":"int","filterText":"variable","insertText":"variable","insertTextFormat":1,"kind":6,"label":"variable","sortText":"{{.*}}variable"}
 #
 # Code pattern
-# CHECK-DAG: {"filterText":"static_cast","insertText":"static_cast<${1:type}>(${2:expression})","insertTextFormat":2,"kind":15,"label":"static_cast<type>(expression)","sortText":"000040static_cast"}
+# CHECK: {"filterText":"static_cast","insertText":"static_cast<${1:type}>(${2:expression})","insertTextFormat":2,"kind":15,"label":"static_cast<type>(expression)","sortText":"{{.*}}static_cast"}
+#
+# Keyword
+# CHECK: {"filterText":"int","insertText":"int","insertTextFormat":1,"kind":14,"label":"int","sortText":"{{.*}}int"}
 #
 # Struct
-# CHECK-DAG: {"filterText":"Struct","insertText":"Struct","insertTextFormat":1,"kind":7,"label":"Struct","sortText":"000050Struct"}
+# CHECK: {"filterText":"Struct","insertText":"Struct","insertTextFormat":1,"kind":7,"label":"Struct","sortText":"{{.*}}Struct"}
 #
 # Macro
-# CHECK-DAG: {"filterText":"MACRO","insertText":"MACRO","insertTextFormat":1,"kind":1,"label":"MACRO","sortText":"000070MACRO"}
-#
-# Variable
-# CHECK-DAG: {"detail":"int","filterText":"variable","insertText":"variable","insertTextFormat":1,"kind":6,"label":"variable","sortText":"000012variable"}
-#
-# Function
-# CHECK-DAG: {"detail":"int","filterText":"function","insertText":"function()","insertTextFormat":1,"kind":3,"label":"function()","sortText":"000012function"}
+# CHECK: {"filterText":"MACRO","insertText":"MACRO","insertTextFormat":1,"kind":1,"label":"MACRO","sortText":"{{.*}}MACRO"}
 #
 # CHECK-SAME: ]}}
 
 {"jsonrpc":"2.0","id":3,"method":"shutdown","params":null}

test/clangd/completion-priorities.test

 # CHECK-NEXT:    "items": [
 # CHECK-NEXT:      {
 # CHECK-NEXT:        "detail": "void",
 # CHECK-NEXT:        "filterText": "priv",
 # CHECK-NEXT:        "insertText": "priv",
 # CHECK-NEXT:        "insertTextFormat": 1,
 # CHECK-NEXT:        "kind": 2,
 # CHECK-NEXT:        "label": "priv()",
-# CHECK-NEXT:        "sortText": "000034priv"
+# CHECK-NEXT:        "sortText": "{{.*}}priv"
 # CHECK-NEXT:      },
 # CHECK-NEXT:      {
 # CHECK-NEXT:        "detail": "void",
 # CHECK-NEXT:        "filterText": "prot",
 # CHECK-NEXT:        "insertText": "prot",
 # CHECK-NEXT:        "insertTextFormat": 1,
 # CHECK-NEXT:        "kind": 2,
 # CHECK-NEXT:        "label": "prot()",
-# CHECK-NEXT:        "sortText": "000034prot"
+# CHECK-NEXT:        "sortText": "{{.*}}prot"
 # CHECK-NEXT:      },
 # CHECK-NEXT:      {
 # CHECK-NEXT:        "detail": "void",
 # CHECK-NEXT:        "filterText": "pub",
 # CHECK-NEXT:        "insertText": "pub",
 # CHECK-NEXT:        "insertTextFormat": 1,
 # CHECK-NEXT:        "kind": 2,
 # CHECK-NEXT:        "label": "pub()",
-# CHECK-NEXT:        "sortText": "000034pub"
+# CHECK-NEXT:        "sortText": "{{.*}}pub"
 # CHECK-NEXT:      },
 Content-Length: 151
 
 {"jsonrpc":"2.0","id":3,"method":"textDocument/completion","params":{"textDocument":{"uri":"file:///main.cpp"},"position":{"line":17,"character":4}}}
 #      CHECK:  "id": 3,
 # CHECK-NEXT:  "jsonrpc": "2.0",
 # CHECK-NEXT:  "result": {
 # CHECK-NEXT:    "isIncomplete": false,
 # CHECK-NEXT:    "items": [
 # CHECK-NEXT:      {
 # CHECK-NEXT:        "detail": "void",
 # CHECK-NEXT:        "filterText": "pub",
 # CHECK-NEXT:        "insertText": "pub",
 # CHECK-NEXT:        "insertTextFormat": 1,
 # CHECK-NEXT:        "kind": 2,
 # CHECK-NEXT:        "label": "pub()",
-# CHECK-NEXT:        "sortText": "000034pub"
+# CHECK-NEXT:        "sortText": "{{.*}}pub"
 # CHECK-NEXT:      },
 # priv() and prot() are at the end of the list
 # CHECK-NEXT:      {
 #      CHECK:        "detail": "void",
 #      CHECK:        "filterText": "priv",
 # CHECK-NEXT:        "insertText": "priv",
 # CHECK-NEXT:        "insertTextFormat": 1,
 # CHECK-NEXT:        "kind": 2,
 # CHECK-NEXT:        "label": "priv()",
-# CHECK-NEXT:        "sortText": "200034priv"
+# CHECK-NEXT:        "sortText": "{{.*}}priv"
 # CHECK-NEXT:      },
 # CHECK-NEXT:      {
 # CHECK-NEXT:        "detail": "void",
 # CHECK-NEXT:        "filterText": "prot",
 # CHECK-NEXT:        "insertText": "prot",
 # CHECK-NEXT:        "insertTextFormat": 1,
 # CHECK-NEXT:        "kind": 2,
 # CHECK-NEXT:        "label": "prot()",
-# CHECK-NEXT:        "sortText": "200034prot"
+# CHECK-NEXT:        "sortText": "{{.*}}prot"
 # CHECK-NEXT:      }
 # CHECK-NEXT:    ]
 # CHECK-NEXT:  }
 Content-Length: 58
 
 {"jsonrpc":"2.0","id":4,"method":"shutdown","params":null}
 Content-Length: 33
 
 {"jsonrpc":"2.0":"method":"exit"}

test/clangd/completion-qualifiers.test

 # Eligible const functions are at the top of the list.
 # CHECK-NEXT:      {
 # CHECK-NEXT:        "detail": "int",
 # CHECK-NEXT:        "filterText": "bar",
 # CHECK-NEXT:        "insertText": "bar",
 # CHECK-NEXT:        "insertTextFormat": 1,
 # CHECK-NEXT:        "kind": 2,
 # CHECK-NEXT:        "label": "bar() const",
-# CHECK-NEXT:        "sortText": "000037bar"
+# CHECK-NEXT:        "sortText": "{{.*}}bar"
 # CHECK-NEXT:      },
 # CHECK-NEXT:      {
 # CHECK-NEXT:        "detail": "int",
 # CHECK-NEXT:        "filterText": "foo",
 # CHECK-NEXT:        "insertText": "foo",
 # CHECK-NEXT:        "insertTextFormat": 1,
 # CHECK-NEXT:        "kind": 2,
 # CHECK-NEXT:        "label": "Foo::foo() const",
-# CHECK-NEXT:        "sortText": "000037foo"
+# CHECK-NEXT:        "sortText": "{{.*}}foo"
 # CHECK-NEXT:      },
-# Ineligible non-const function is at the bottom of the list.
+# Ineligible non-const function is near the bottom of the list.
 # CHECK-NEXT:      {
 #      CHECK:        "detail": "int",
 #      CHECK:        "filterText": "foo",
 # CHECK-NEXT:        "insertText": "foo",
 # CHECK-NEXT:        "insertTextFormat": 1,
 # CHECK-NEXT:        "kind": 2,
 # CHECK-NEXT:        "label": "foo() const",
-# CHECK-NEXT:        "sortText": "200035foo"
-# CHECK-NEXT:      }
-# CHECK-NEXT:    ]
-# CHECK-NEXT:  }
+# CHECK-NEXT:        "sortText": "{{.*}}foo"
+# CHECK-NEXT:      }
 Content-Length: 44
 
 {"jsonrpc":"2.0","id":4,"method":"shutdown"}
 Content-Length: 33
 
 {"jsonrpc":"2.0":"method":"exit"}

test/clangd/completion-snippet.test

 # CHECK-NEXT:    "items": [
 # CHECK-NEXT:      {
 # CHECK-NEXT:        "detail": "int",
 # CHECK-NEXT:        "filterText": "a",
 # CHECK-NEXT:        "insertText": "a",
 # CHECK-NEXT:        "insertTextFormat": 1,
 # CHECK-NEXT:        "kind": 5,
 # CHECK-NEXT:        "label": "a",
-# CHECK-NEXT:        "sortText": "000035a"
+# CHECK-NEXT:        "sortText": "{{.*}}a"
 # CHECK-NEXT:      },
 # CHECK-NEXT:      {
 # CHECK-NEXT:        "detail": "int",
 # CHECK-NEXT:        "filterText": "bb",
 # CHECK-NEXT:        "insertText": "bb",
 # CHECK-NEXT:        "insertTextFormat": 1,
 # CHECK-NEXT:        "kind": 5,
 # CHECK-NEXT:        "label": "bb",
-# CHECK-NEXT:        "sortText": "000035bb"
+# CHECK-NEXT:        "sortText": "{{.*}}bb"
 # CHECK-NEXT:      },
 # CHECK-NEXT:      {
 # CHECK-NEXT:        "detail": "int",
 # CHECK-NEXT:        "filterText": "ccc",
 # CHECK-NEXT:        "insertText": "ccc",
 # CHECK-NEXT:        "insertTextFormat": 1,
 # CHECK-NEXT:        "kind": 5,
 # CHECK-NEXT:        "label": "ccc",
-# CHECK-NEXT:        "sortText": "000035ccc"
+# CHECK-NEXT:        "sortText": "{{.*}}ccc"
 # CHECK-NEXT:      },
 # CHECK-NEXT:      {
 # CHECK-NEXT:        "detail": "int",
 # CHECK-NEXT:        "filterText": "f",
 # CHECK-NEXT:        "insertText": "f(${1:int i}, ${2:const float f})",
 # CHECK-NEXT:        "insertTextFormat": 2,
 # CHECK-NEXT:        "kind": 2,
 # CHECK-NEXT:        "label": "f(int i, const float f) const",
-# CHECK-NEXT:        "sortText": "000035f"
+# CHECK-NEXT:        "sortText": "{{.*}}f"
 # CHECK-NEXT:      },
 # CHECK-NEXT:      {
 # CHECK-NEXT:        "filterText": "fake",
 # CHECK-NEXT:        "insertText": "fake::",
 # CHECK-NEXT:        "insertTextFormat": 1,
 # CHECK-NEXT:        "kind": 7,
 # CHECK-NEXT:        "label": "fake::",
-# CHECK-NEXT:        "sortText": "000075fake"
+# CHECK-NEXT:        "sortText": "{{.*}}fake"
 # CHECK-NEXT:      },
 # CHECK-NEXT:      {
 # CHECK-NEXT:        "detail": "fake &",
 # CHECK-NEXT:        "filterText": "operator=",
 # CHECK-NEXT:        "insertText": "operator=(${1:const fake &})",
 # CHECK-NEXT:        "insertTextFormat": 2,
 # CHECK-NEXT:        "kind": 2,
 # CHECK-NEXT:        "label": "operator=(const fake &)",
-# CHECK-NEXT:        "sortText": "000079operator="
+# CHECK-NEXT:        "sortText": "{{.*}}operator="
 # CHECK-NEXT:      },
 # FIXME: Why do some buildbots show an extra operator==(fake&&) here?
 #      CHECK:      {
 #      CHECK:        "detail": "void",
 # CHECK-NEXT:        "filterText": "~fake",
 # CHECK-NEXT:        "insertText": "~fake()",
 # CHECK-NEXT:        "insertTextFormat": 1,
 # CHECK-NEXT:        "kind": 4,
 # CHECK-NEXT:        "label": "~fake()",
-# CHECK-NEXT:        "sortText": "000079~fake"
+# CHECK-NEXT:        "sortText": "{{.*}}~fake"
 # CHECK-NEXT:      }
 # CHECK-NEXT:    ]
 # CHECK-NEXT:  }
 # Update the source file and check for completions again.
 Content-Length: 226
 
 {"jsonrpc":"2.0","method":"textDocument/didChange","params":{"textDocument":{"uri":"file:///main.cpp","version":2},"contentChanges":[{"text":"struct fancy { int (*func())(int, int); };\nint main() {\n  fancy f;\n  f.\n}\n"}]}}
 
 Content-Length: 148
 
 {"jsonrpc":"2.0","id":3,"method":"textDocument/completion","params":{"textDocument":{"uri":"file:///main.cpp"},"position":{"line":3,"character":5}}}
 #      CHECK:  "id": 3,
 # CHECK-NEXT:  "jsonrpc": "2.0",
 # CHECK-NEXT:  "result": {
 # CHECK-NEXT:    "isIncomplete": false,
 # CHECK-NEXT:    "items": [
 # CHECK-NEXT:      {
 # CHECK-NEXT:        "detail": "int (*)(int, int)",
 # CHECK-NEXT:        "filterText": "func",
 # CHECK-NEXT:        "insertText": "func()",
 # CHECK-NEXT:        "insertTextFormat": 1,
 # CHECK-NEXT:        "kind": 2,
 # CHECK-NEXT:        "label": "func()",
-# CHECK-NEXT:        "sortText": "000034func"
+# CHECK-NEXT:        "sortText": "{{.*}}func"
 # CHECK-NEXT:      },
 Content-Length: 44
 
 {"jsonrpc":"2.0","id":4,"method":"shutdown"}
 Content-Length: 33
 
 {"jsonrpc":"2.0":"method":"exit"}

test/clangd/completion.test

 # CHECK-NEXT:    "items": [
 # CHECK-NEXT:    {
 # CHECK-NEXT:      "detail": "int",
 # CHECK-NEXT:      "filterText": "a",
 # CHECK-NEXT:      "insertText": "a",
 # CHECK-NEXT:      "insertTextFormat": 1,
 # CHECK-NEXT:      "kind": 5,
 # CHECK-NEXT:      "label": "a",
-# CHECK-NEXT:      "sortText": "000035a"
+# CHECK-NEXT:      "sortText": "{{.*}}a"
 # CHECK-NEXT:    },
 # CHECK-NEXT:    {
 # CHECK-NEXT:      "detail": "int",
 # CHECK-NEXT:      "filterText": "bb",
 # CHECK-NEXT:      "insertText": "bb",
 # CHECK-NEXT:      "insertTextFormat": 1,
 # CHECK-NEXT:      "kind": 5,
 # CHECK-NEXT:      "label": "bb",
-# CHECK-NEXT:      "sortText": "000035bb"
+# CHECK-NEXT:      "sortText": "{{.*}}bb"
 # CHECK-NEXT:    },
 # CHECK-NEXT:    {
 # CHECK-NEXT:      "detail": "int",
 # CHECK-NEXT:      "filterText": "ccc",
 # CHECK-NEXT:      "insertText": "ccc",
 # CHECK-NEXT:      "insertTextFormat": 1,
 # CHECK-NEXT:      "kind": 5,
 # CHECK-NEXT:      "label": "ccc",
-# CHECK-NEXT:      "sortText": "000035ccc"
+# CHECK-NEXT:      "sortText": "{{.*}}ccc"
 # CHECK-NEXT:    },
 # CHECK-NEXT:    {
 # CHECK-NEXT:      "detail": "int",
 # CHECK-NEXT:      "filterText": "f",
 # CHECK-NEXT:      "insertText": "f",
 # CHECK-NEXT:      "insertTextFormat": 1,
 # CHECK-NEXT:      "kind": 2,
 # CHECK-NEXT:      "label": "f(int i, const float f) const",
-# CHECK-NEXT:      "sortText": "000035f"
+# CHECK-NEXT:      "sortText": "{{.*}}f"
 # CHECK-NEXT:    },
 # CHECK-NEXT:    {
 # CHECK-NEXT:      "filterText": "fake",
 # CHECK-NEXT:      "insertText": "fake",
 # CHECK-NEXT:      "insertTextFormat": 1,
 # CHECK-NEXT:      "kind": 7,
 # CHECK-NEXT:      "label": "fake::",
-# CHECK-NEXT:      "sortText": "000075fake"
+# CHECK-NEXT:      "sortText": "{{.*}}fake"
 # CHECK-NEXT:    },
 # CHECK-NEXT:    {
 # CHECK-NEXT:      "detail": "fake &",
 # CHECK-NEXT:      "filterText": "operator=",
 # CHECK-NEXT:      "insertText": "operator=",
 # CHECK-NEXT:      "insertTextFormat": 1,
 # CHECK-NEXT:      "kind": 2,
 # CHECK-NEXT:      "label": "operator=(const fake &)",
-# CHECK-NEXT:      "sortText": "000079operator="
+# CHECK-NEXT:      "sortText": "{{.*}}operator="
 # CHECK-NEXT:    },
 # FIXME: Why do some buildbots show an extra operator==(fake&&) here?
 #      CHECK:    {
 #      CHECK:      "detail": "void",
 # CHECK-NEXT:      "filterText": "~fake",
 # CHECK-NEXT:      "insertText": "~fake",
 # CHECK-NEXT:      "insertTextFormat": 1,
 # CHECK-NEXT:      "kind": 4,
 # CHECK-NEXT:      "label": "~fake()",
-# CHECK-NEXT:      "sortText": "000079~fake"
+# CHECK-NEXT:      "sortText": "{{.*}}~fake"
 # CHECK-NEXT:    }
 # CHECK-NEXT:  ]
 Content-Length: 148
 
 {"jsonrpc":"2.0","id":2,"method":"textDocument/completion","params":{"textDocument":{"uri":"file:///main.cpp"},"position":{"line":3,"character":5}}}
 #      CHECK:  "id": 2
 # CHECK-NEXT:  "jsonrpc": "2.0",
 # CHECK-NEXT:  "result": {
 # CHECK-NEXT:    "isIncomplete": false,
 # CHECK-NEXT:    "items": [
 # CHECK-NEXT:    {
 # CHECK-NEXT:      "detail": "int",
 # CHECK-NEXT:      "filterText": "a",
 # CHECK-NEXT:      "insertText": "a",
 # CHECK-NEXT:      "insertTextFormat": 1,
 # CHECK-NEXT:      "kind": 5,
 # CHECK-NEXT:      "label": "a",
-# CHECK-NEXT:      "sortText": "000035a"
+# CHECK-NEXT:      "sortText": "{{.*}}"
 # CHECK-NEXT:    },
 # CHECK-NEXT:    {
 # CHECK-NEXT:      "detail": "int",
 # CHECK-NEXT:      "filterText": "bb",
 # CHECK-NEXT:      "insertText": "bb",
 # CHECK-NEXT:      "insertTextFormat": 1,
 # CHECK-NEXT:      "kind": 5,
 # CHECK-NEXT:      "label": "bb",
-# CHECK-NEXT:      "sortText": "000035bb"
+# CHECK-NEXT:      "sortText": "{{.*}}"
 # CHECK-NEXT:    },
 # CHECK-NEXT:    {
 # CHECK-NEXT:      "detail": "int",
 # CHECK-NEXT:      "filterText": "ccc",
 # CHECK-NEXT:      "insertText": "ccc",
 # CHECK-NEXT:      "insertTextFormat": 1,
 # CHECK-NEXT:      "kind": 5,
 # CHECK-NEXT:      "label": "ccc",
-# CHECK-NEXT:      "sortText": "000035ccc"
+# CHECK-NEXT:      "sortText": "{{.*}}"
 # CHECK-NEXT:    },
 # CHECK-NEXT:    {
 # CHECK-NEXT:      "detail": "int",
 # CHECK-NEXT:      "filterText": "f",
 # CHECK-NEXT:      "insertText": "f",
 # CHECK-NEXT:      "insertTextFormat": 1,
 # CHECK-NEXT:      "kind": 2,
 # CHECK-NEXT:      "label": "f(int i, const float f) const",
-# CHECK-NEXT:      "sortText": "000035f"
+# CHECK-NEXT:      "sortText": "{{.*}}"
 # CHECK-NEXT:    },
 # CHECK-NEXT:    {
 # CHECK-NEXT:      "filterText": "fake",
 # CHECK-NEXT:      "insertText": "fake",
 # CHECK-NEXT:      "insertTextFormat": 1,
 # CHECK-NEXT:      "kind": 7,
 # CHECK-NEXT:      "label": "fake::",
-# CHECK-NEXT:      "sortText": "000075fake"
+# CHECK-NEXT:      "sortText": "{{.*}}"
 # CHECK-NEXT:    },
 # CHECK-NEXT:    {
 # CHECK-NEXT:      "detail": "fake &",
 # CHECK-NEXT:      "filterText": "operator=",
 # CHECK-NEXT:      "insertText": "operator=",
 # CHECK-NEXT:      "insertTextFormat": 1,
 # CHECK-NEXT:      "kind": 2,
 # CHECK-NEXT:      "label": "operator=(const fake &)",
-# CHECK-NEXT:      "sortText": "000079operator="
+# CHECK-NEXT:      "sortText": "{{.*}}"
 # CHECK-NEXT:    },
 #      CHECK:    {
 #      CHECK:      "detail": "void",
 # CHECK-NEXT:      "filterText": "~fake",
 # CHECK-NEXT:      "insertText": "~fake",
 # CHECK-NEXT:      "insertTextFormat": 1,
 # CHECK-NEXT:      "kind": 4,
 # CHECK-NEXT:      "label": "~fake()",
-# CHECK-NEXT:      "sortText": "000079~fake"
+# CHECK-NEXT:      "sortText": "{{.*}}"
 # CHECK-NEXT:    }
 # CHECK-NEXT:  ]
 # Update the source file and check for completions again.
 Content-Length: 226
 
 {"jsonrpc":"2.0","method":"textDocument/didChange","params":{"textDocument":{"uri":"file:///main.cpp","version":2},"contentChanges":[{"text":"struct fancy { int (*func())(int, int); };\nint main() {\n  fancy f;\n  f.\n}\n"}]}}
 
 Content-Length: 148
 
 {"jsonrpc":"2.0","id":3,"method":"textDocument/completion","params":{"textDocument":{"uri":"file:///main.cpp"},"position":{"line":3,"character":5}}}
 #      CHECK:    "id": 3,
 # CHECK-NEXT:  "jsonrpc": "2.0",
 # CHECK-NEXT:  "result": {
 # CHECK-NEXT:    "isIncomplete": false,
 # CHECK-NEXT:    "items": [
 # CHECK-NEXT:    {
 # CHECK-NEXT:      "detail": "int (*)(int, int)",
 # CHECK-NEXT:      "filterText": "func",
 # CHECK-NEXT:      "insertText": "func",
 # CHECK-NEXT:      "insertTextFormat": 1,
 # CHECK-NEXT:      "kind": 2,
 # CHECK-NEXT:      "label": "func()",
-# CHECK-NEXT:      "sortText": "000034func"
+# CHECK-NEXT:      "sortText": "{{.*}}"
 # CHECK-NEXT:    },
 # CHECK-NEXT:    {
 # CHECK-NEXT:      "filterText": "fancy",
 # CHECK-NEXT:      "insertText": "fancy",
 # CHECK-NEXT:      "insertTextFormat": 1,
 # CHECK-NEXT:      "kind": 7,
 # CHECK-NEXT:      "label": "fancy::",
-# CHECK-NEXT:      "sortText": "000075fancy"
+# CHECK-NEXT:      "sortText": "{{.*}}"
 # CHECK-NEXT:    },
 # CHECK-NEXT:    {
 # CHECK-NEXT:      "detail": "fancy &",
 # CHECK-NEXT:      "filterText": "operator=",
 # CHECK-NEXT:      "insertText": "operator=",
 # CHECK-NEXT:      "insertTextFormat": 1,
 # CHECK-NEXT:      "kind": 2,
 # CHECK-NEXT:      "label": "operator=(const fancy &)",
-# CHECK-NEXT:      "sortText": "000079operator="
+# CHECK-NEXT:      "sortText": "{{.*}}"
 # CHECK-NEXT:    },
 #      CHECK:    {
 #      CHECK:      "detail": "void",
 # CHECK-NEXT:      "filterText": "~fancy",
 # CHECK-NEXT:      "insertText": "~fancy",
 # CHECK-NEXT:      "insertTextFormat": 1,
 # CHECK-NEXT:      "kind": 4,
 # CHECK-NEXT:      "label": "~fancy()",
-# CHECK-NEXT:      "sortText": "000079~fancy"
+# CHECK-NEXT:      "sortText": "{{.*}}"
 # CHECK-NEXT:    }
 # CHECK-NEXT:  ]
 Content-Length: 44
 
 {"jsonrpc":"2.0","id":4,"method":"shutdown"}
 Content-Length: 33
 
 {"jsonrpc":"2.0":"method":"exit"}

test/clangd/protocol.test

 # CHECK-NEXT:  "result": {
 # CHECK-NEXT:    "isIncomplete": false,
 # CHECK-NEXT:    "items": [
 #      CHECK:        "filterText": "fake",
 # CHECK-NEXT:        "insertText": "fake",
 # CHECK-NEXT:        "insertTextFormat": 1,
 # CHECK-NEXT:        "kind": 7,
 # CHECK-NEXT:        "label": "fake::",
-# CHECK-NEXT:        "sortText": "000075fake"
+# CHECK-NEXT:        "sortText": "{{.*}}"
 #      CHECK:    ]
 # CHECK-NEXT:  }
 
 X-Test: Testing
 Content-Type: application/vscode-jsonrpc; charset-utf-8
 Content-Length: 146
 Content-Type: application/vscode-jsonrpc; charset-utf-8
 X-Testing: Test

 # CHECK-NEXT:  "result": {
 # CHECK-NEXT:    "isIncomplete": false,
 # CHECK-NEXT:    "items": [
 #      CHECK:        "filterText": "fake",
 # CHECK-NEXT:        "insertText": "fake",
 # CHECK-NEXT:        "insertTextFormat": 1,
 # CHECK-NEXT:        "kind": 7,
 # CHECK-NEXT:        "label": "fake::",
-# CHECK-NEXT:        "sortText": "000075fake"
+# CHECK-NEXT:        "sortText": "{{.*}}"
 #      CHECK:    ]
 # CHECK-NEXT:  }
 # STDERR: Warning: Duplicate Content-Length header received. The previous value for this message (10) was ignored.
 
 Content-Type: application/vscode-jsonrpc; charset-utf-8
 Content-Length: 10
 
 {"jsonrpc":"2.0","id":4,"method":"textDocument/completion","params":{"textDocument":{"uri":"file:/main.cpp"},"position":{"line":3,"character":5}}}

 # CHECK-NEXT:  "result": {
 # CHECK-NEXT:    "isIncomplete": false,
 # CHECK-NEXT:    "items": [
 #      CHECK:        "filterText": "fake",
 # CHECK-NEXT:        "insertText": "fake",
 # CHECK-NEXT:        "insertTextFormat": 1,
 # CHECK-NEXT:        "kind": 7,
 # CHECK-NEXT:        "label": "fake::",
-# CHECK-NEXT:        "sortText": "000075fake"
+# CHECK-NEXT:        "sortText": "{{.*}}"
 #      CHECK:    ]
 # CHECK-NEXT:  }
 Content-Length: 1024
 
 {"jsonrpc":"2.0","id":5,"method":"textDocument/completion","params":{"textDocument":{"uri":"file:/main.cpp"},"position":{"line":3,"character":5}}}
 # Test message which reads beyond the end of the stream.
 #
 # Ensure this is the last test in the file!
 # STDERR: Input was aborted. Read only {{[0-9]+}} bytes of expected {{[0-9]+}}.