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

[Sam McCall via Phabricator via cfe-commits]

This revision was automatically updated to reflect the committed changes.
sammccall marked an inline comment as done.
Closed by commit rL322821: [clangd] Use fuzzy match to select top N index 
results. (authored by sammccall, committed by ).
Herald added a reviewer: jkorous-apple.
Herald added a subscriber: llvm-commits.

Changed prior to commit:
  https://reviews.llvm.org/D42060?vs=129833&id=130363#toc

Repository:
  rL LLVM

https://reviews.llvm.org/D42060

Files:
  clang-tools-extra/trunk/clangd/index/MemIndex.cpp
  clang-tools-extra/trunk/unittests/clangd/IndexTests.cpp


Index: clang-tools-extra/trunk/clangd/index/MemIndex.cpp
===================================================================
--- clang-tools-extra/trunk/clangd/index/MemIndex.cpp
+++ clang-tools-extra/trunk/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 More;
 }
 
 std::unique_ptr<SymbolIndex> MemIndex::build(SymbolSlab Slab) {
Index: clang-tools-extra/trunk/unittests/clangd/IndexTests.cpp
===================================================================
--- clang-tools-extra/trunk/unittests/clangd/IndexTests.cpp
+++ clang-tools-extra/trunk/unittests/clangd/IndexTests.cpp
@@ -149,12 +149,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"));
 }
 
@@ -164,7 +174,6 @@
   FuzzyFindRequest Req;
   Req.Query = "y";
   Req.Scopes = {""};
-  auto Matches = match(I, Req);
   EXPECT_THAT(match(I, Req), UnorderedElementsAre("yz"));
 }
 
@@ -174,7 +183,6 @@
   FuzzyFindRequest Req;
   Req.Query = "y";
   Req.Scopes = {"a"};
-  auto Matches = match(I, Req);
   EXPECT_THAT(match(I, Req), UnorderedElementsAre("a::xyz", "a::yy"));
 }
 
@@ -184,7 +192,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"));
 }
 
@@ -194,7 +201,6 @@
   FuzzyFindRequest Req;
   Req.Query = "y";
   Req.Scopes = {"a"};
-  auto Matches = match(I, Req);
   EXPECT_THAT(match(I, Req), UnorderedElementsAre("a::xyz"));
 }
 
@@ -204,7 +210,6 @@
   FuzzyFindRequest Req;
   Req.Query = "AB";
   Req.Scopes = {"ns"};
-  auto Matches = match(I, Req);
   EXPECT_THAT(match(I, Req), UnorderedElementsAre("ns::ABC", "ns::abc"));
 }
 

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