[clangd] Incorporate #occurrences in scoring code complete results.

[sammccall]

Summary

needs tests

[ilya-biryukov]

the patch LG and fixes the problem of llvm namespace not showing up in completions from the static index.
Let's add some tests and ship it!

[sammccall]

Add completion test.

[sammccall]

Added a test - it's kind of perfunctory, I really want to organize symbol scoring more thoroughly which will provide a better place to test well.

[sammccall]

Fix tests.

[ilya-biryukov]

LGTM

clangd/CodeComplete.cpp

 struct CompletionCandidate {
   llvm::StringRef Name; // Used for filtering and sorting.
   // We may have a result from Sema, from the index, or both.
   const CodeCompletionResult *SemaResult = nullptr;
   const Symbol *IndexResult = nullptr;
 
   // Computes the "symbol quality" score for this completion. Higher is better.
   float score() const {
-    // For now we just use the Sema priority, mapping it onto a 0-1 interval.
-    if (!SemaResult) // FIXME(sammccall): better scoring for index results.
-      return 0.3f;   // fixed mediocre score for index-only results.
-
+    float Score = 1;
+    if (IndexResult)
+      Score *= quality(*IndexResult);
+    if (SemaResult) {
+      // For now we just use the Sema priority, mapping it onto a 0-2 interval.
+      // That makes 1 neutral-ish, so we don't reward/penalize non-Sema results.
       // Priority 80 is a really bad score.
-    float Score = 1 - std::min<float>(80, SemaResult->Priority) / 80;
+      Score *= 2 - std::min<float>(80, SemaResult->Priority) / 40;
 
       switch (static_cast<CXAvailabilityKind>(SemaResult->Availability)) {
       case CXAvailability_Available:
         // No penalty.
         break;
       case CXAvailability_Deprecated:
         Score *= 0.1f;
         break;
       case CXAvailability_NotAccessible:
       case CXAvailability_NotAvailable:
         Score = 0;
         break;
       }
+    }
     return Score;
   }
 
   // Builds an LSP completion item.
   CompletionItem build(llvm::StringRef FileName,
                        const CompletionItemScores &Scores,
                        const CodeCompleteOptions &Opts,
                        CodeCompletionString *SemaCCS) const {

clangd/index/Index.h

struct Symbol {
   // Optional details of the symbol.
   const Details *Detail = nullptr;
 
   // FIXME: add all occurrences support.
   // FIXME: add extra fields for index scoring signals.
 };
 llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, const Symbol &S);
 
+// Computes query-independent quality score for a Symbol.
+// This currently falls in the range [1, ln(#indexed documents)].
+// FIXME: this should probably be split into symbol -> signals
+//        and signals -> score, so it can be reused for Sema completions.
+double quality(const Symbol &S);
+
 // An immutable symbol container that stores a set of symbols.
 // The container will maintain the lifetime of the symbols.
 class SymbolSlab {
 public:
   using const_iterator = std::vector<Symbol>::const_iterator;
   using iterator = const_iterator;
 
   SymbolSlab() = default;

clangd/index/Index.cpp

void operator>>(StringRef Str, SymbolID &ID) {
   assert(HexString.size() == ID.HashValue.size());
   std::copy(HexString.begin(), HexString.end(), ID.HashValue.begin());
 }
 
 raw_ostream &operator<<(raw_ostream &OS, const Symbol &S) {
   return OS << S.Scope << S.Name;
 }
 
+double quality(const Symbol &S) {
+  // This avoids a sharp gradient for tail symbols, and also neatly avoids the
+  // question of whether 0 references means a bad symbol or missing data.
+  if (S.References < 3)
+    return 1;
+  return std::log(S.References);
+}
+
 SymbolSlab::const_iterator SymbolSlab::find(const SymbolID &ID) const {
   auto It = std::lower_bound(Symbols.begin(), Symbols.end(), ID,
                              [](const Symbol &S, const SymbolID &I) {
                                return S.ID < I;
                              });
   if (It != Symbols.end() && It->ID == ID)
     return It;
   return Symbols.end();

clangd/index/MemIndex.cpp

bool More = false;
     for (const auto Pair : Index) {
       const Symbol *Sym = Pair.second;
 
       // Exact match against all possible scopes.
       if (!Req.Scopes.empty() && !llvm::is_contained(Req.Scopes, Sym->Scope))
         continue;
 
       if (auto Score = Filter.match(Sym->Name)) {
-        Top.emplace(-*Score, Sym);
+        Top.emplace(-*Score * quality(*Sym), Sym);
         if (Top.size() > Req.MaxCandidateCount) {
           More = true;
           Top.pop();
         }
       }
     }
     for (; !Top.empty(); Top.pop())
       Callback(*Top.top().second);

unittests/clangd/CodeCompleteTests.cpp

Symbol func(StringRef Name) { // Assumes the function has no args.
   return sym(Name, index::SymbolKind::Function, "@F@\\0#"); // no args
 }
 Symbol cls(StringRef Name) {
   return sym(Name, index::SymbolKind::Class, "@S@\\0@S@\\0");
 }
 Symbol var(StringRef Name) {
   return sym(Name, index::SymbolKind::Variable, "@\\0");
 }
+Symbol ns(StringRef Name) {
+  return sym(Name, index::SymbolKind::Namespace, "@N@\\0");
+}
+Symbol withReferences(int N, Symbol S) {
+  S.References = N;
+  return S;
+}
 
 TEST(CompletionTest, Limit) {
   clangd::CodeCompleteOptions Opts;
   Opts.Limit = 2;
   auto Results = completions(R"cpp(
 struct ClassWithMembers {
   int AAA();
   int BBB();
auto Results = completions(
       R"cpp(
           void f() { ns::x^ }
       )cpp",
       {cls("ns::XYZ"), func("ns::foo")});
   EXPECT_THAT(Results.items,
               UnorderedElementsAre(AllOf(Named("XYZ"), Filter("XYZ"))));
 }
 
+TEST(CompletionTest, ReferencesAffectRanking) {
+  auto Results = completions("int main() { abs^ }", {ns("absl"), func("abs")});
+  EXPECT_THAT(Results.items, HasSubsequence(Named("abs"), Named("absl")));
+  Results = completions("int main() { abs^ }",
+                        {withReferences(10000, ns("absl")), func("abs")});
+  EXPECT_THAT(Results.items, HasSubsequence(Named("absl"), Named("abs")));
+}
+
 TEST(CompletionTest, GlobalQualified) {
   auto Results = completions(
       R"cpp(
           void f() { ::^ }
       )cpp",
       {cls("XYZ")});
   EXPECT_THAT(Results.items, AllOf(Has("XYZ", CompletionItemKind::Class),
                                    Has("f", CompletionItemKind::Function)));