[clangd] Use fuzzy match to select top N index results.

[sammccall]

Summary

This makes performance slower but more predictable (it always processes
every symbol). We need to find ways to make this fast, possibly by precomputing
short queries or capping the number of scored results. But our current approach
is too naive.

It also no longer returns results in a "good" order. In fact it's pathological:
the top N results are ranked from worst to best. Indexes aren't responsible for
ranking and MergedIndex can't do a good job, so I'm pleased that this will make
any hidden assumptions we have more noticeable :-)

[hokein]

LGTM.

clangd/index/MemIndex.cpp

60

this should be more?

clangd/index/MemIndex.cpp

 //===--- MemIndex.cpp - Dynamic in-memory symbol index. ----------*- C++-*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===-------------------------------------------------------------------===//
 
 #include "MemIndex.h"
+#include "../FuzzyMatch.h"
 #include "../Logger.h"
+#include <queue>
 
 namespace clang {
 namespace clangd {
 
 void MemIndex::build(std::shared_ptr<std::vector<const Symbol *>> Syms) {
   llvm::DenseMap<SymbolID, const Symbol *> TempIndex;
   for (const Symbol *Sym : *Syms)
     TempIndex[Sym->ID] = Sym;
 
   // Swap out the old symbols and index.
   {
     std::lock_guard<std::mutex> Lock(Mutex);
     Index = std::move(TempIndex);
     Symbols = std::move(Syms); // Relase old symbols.
   }
 }
 
 bool MemIndex::fuzzyFind(
     const Context &Ctx, const FuzzyFindRequest &Req,
     llvm::function_ref<void(const Symbol &)> Callback) const {
   assert(!StringRef(Req.Query).contains("::") &&
          "There must be no :: in query.");
 
-  unsigned Matched = 0;
+  std::priority_queue<std::pair<float, const Symbol *>> Top;
+  FuzzyMatcher Filter(Req.Query);
+  bool More = false;
   {
     std::lock_guard<std::mutex> Lock(Mutex);
     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;
 
-      // FIXME(ioeric): use fuzzy matcher.
-      if (StringRef(Sym->Name).find_lower(Req.Query) != StringRef::npos) {
-        if (++Matched > Req.MaxCandidateCount)
-          return false;
-        Callback(*Sym);
+      if (auto Score = Filter.match(Sym->Name)) {
+        Top.emplace(-*Score, Sym);
+        if (Top.size() > Req.MaxCandidateCount) {
+          More = true;
+          Top.pop();
+        }
       }
     }
+    for (; !Top.empty(); Top.pop())
+      Callback(*Top.top().second);
   }
-  return true;
+  return false;
 }
 
 std::unique_ptr<SymbolIndex> MemIndex::build(SymbolSlab Slab) {
   struct Snapshot {
     SymbolSlab Slab;
     std::vector<const Symbol *> Pointers;
   };
   auto Snap = std::make_shared<Snapshot>();

unittests/clangd/IndexTests.cpp

TEST(MemIndexTest, MemIndexLimitedNumMatches) {
   I.build(generateNumSymbols(0, 100));
   FuzzyFindRequest Req;
   Req.Query = "5";
   Req.MaxCandidateCount = 3;
   auto Matches = match(I, Req);
   EXPECT_EQ(Matches.size(), Req.MaxCandidateCount);
 }
 
+TEST(MemIndexTest, FuzzyMatch) {
+  MemIndex I;
+  I.build(
+      generateSymbols({"LaughingOutLoud", "LionPopulation", "LittleOldLady"}));
+  FuzzyFindRequest Req;
+  Req.Query = "lol";
+  Req.MaxCandidateCount = 2;
+  EXPECT_THAT(match(I, Req),
+              UnorderedElementsAre("LaughingOutLoud", "LittleOldLady"));
+}
+
 TEST(MemIndexTest, MatchQualifiedNamesWithoutSpecificScope) {
   MemIndex I;
   I.build(generateSymbols({"a::xyz", "b::yz", "yz"}));
   FuzzyFindRequest Req;
   Req.Query = "y";
-  auto Matches = match(I, Req);
   EXPECT_THAT(match(I, Req), UnorderedElementsAre("a::xyz", "b::yz", "yz"));
 }
 
 TEST(MemIndexTest, MatchQualifiedNamesWithGlobalScope) {
   MemIndex I;
   I.build(generateSymbols({"a::xyz", "b::yz", "yz"}));
   FuzzyFindRequest Req;
   Req.Query = "y";
   Req.Scopes = {""};
-  auto Matches = match(I, Req);
   EXPECT_THAT(match(I, Req), UnorderedElementsAre("yz"));
 }
 
 TEST(MemIndexTest, MatchQualifiedNamesWithOneScope) {
   MemIndex I;
   I.build(generateSymbols({"a::xyz", "a::yy", "a::xz", "b::yz", "yz"}));
   FuzzyFindRequest Req;
   Req.Query = "y";
   Req.Scopes = {"a"};
-  auto Matches = match(I, Req);
   EXPECT_THAT(match(I, Req), UnorderedElementsAre("a::xyz", "a::yy"));
 }
 
 TEST(MemIndexTest, MatchQualifiedNamesWithMultipleScopes) {
   MemIndex I;
   I.build(generateSymbols({"a::xyz", "a::yy", "a::xz", "b::yz", "yz"}));
   FuzzyFindRequest Req;
   Req.Query = "y";
   Req.Scopes = {"a", "b"};
-  auto Matches = match(I, Req);
   EXPECT_THAT(match(I, Req), UnorderedElementsAre("a::xyz", "a::yy", "b::yz"));
 }
 
 TEST(MemIndexTest, NoMatchNestedScopes) {
   MemIndex I;
   I.build(generateSymbols({"a::xyz", "a::b::yy"}));
   FuzzyFindRequest Req;
   Req.Query = "y";
   Req.Scopes = {"a"};
-  auto Matches = match(I, Req);
   EXPECT_THAT(match(I, Req), UnorderedElementsAre("a::xyz"));
 }
 
 TEST(MemIndexTest, IgnoreCases) {
   MemIndex I;
   I.build(generateSymbols({"ns::ABC", "ns::abc"}));
   FuzzyFindRequest Req;
   Req.Query = "AB";
   Req.Scopes = {"ns"};
-  auto Matches = match(I, Req);
   EXPECT_THAT(match(I, Req), UnorderedElementsAre("ns::ABC", "ns::abc"));
 }
 
 } // namespace
 } // namespace clangd
 } // namespace clang