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

[Sam McCall via Phabricator via cfe-commits]

sammccall created this revision.
sammccall added a reviewer: hokein.
Herald added subscribers: cfe-commits, ilya-biryukov, klimek.

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 :-)


Repository:
  rCTE Clang Tools Extra

https://reviews.llvm.org/D42060

Files:
  clangd/index/MemIndex.cpp
  unittests/clangd/IndexTests.cpp


Index: unittests/clangd/IndexTests.cpp
===================================================================
--- unittests/clangd/IndexTests.cpp
+++ unittests/clangd/IndexTests.cpp
@@ -148,12 +148,22 @@
   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"));
 }
 
@@ -163,7 +173,6 @@
   FuzzyFindRequest Req;
   Req.Query = "y";
   Req.Scopes = {""};
-  auto Matches = match(I, Req);
   EXPECT_THAT(match(I, Req), UnorderedElementsAre("yz"));
 }
 
@@ -173,7 +182,6 @@
   FuzzyFindRequest Req;
   Req.Query = "y";
   Req.Scopes = {"a"};
-  auto Matches = match(I, Req);
   EXPECT_THAT(match(I, Req), UnorderedElementsAre("a::xyz", "a::yy"));
 }
 
@@ -183,7 +191,6 @@
   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"));
 }
 
@@ -193,7 +200,6 @@
   FuzzyFindRequest Req;
   Req.Query = "y";
   Req.Scopes = {"a"};
-  auto Matches = match(I, Req);
   EXPECT_THAT(match(I, Req), UnorderedElementsAre("a::xyz"));
 }
 
@@ -203,7 +209,6 @@
   FuzzyFindRequest Req;
   Req.Query = "AB";
   Req.Scopes = {"ns"};
-  auto Matches = match(I, Req);
   EXPECT_THAT(match(I, Req), UnorderedElementsAre("ns::ABC", "ns::abc"));
 }
 
Index: clangd/index/MemIndex.cpp
===================================================================
--- clangd/index/MemIndex.cpp
+++ clangd/index/MemIndex.cpp
@@ -8,7 +8,9 @@
 //===-------------------------------------------------------------------===//
 
 #include "MemIndex.h"
+#include "../FuzzyMatch.h"
 #include "../Logger.h"
+#include <queue>
 
 namespace clang {
 namespace clangd {
@@ -32,7 +34,9 @@
   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) {
@@ -42,15 +46,18 @@
       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) {

_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits