[clangd] Make workspace/symbols actually rank its results.

Summary: The index doesn't actually return results in ranked order.

Reviewers: hokein

Subscribers: ilya-biryukov, ioeric, MaskRay, jkorous, cfe-commits

Differential Revision: https://reviews.llvm.org/D47821

2 files changed, 52 insertions, 5 deletions

diff --git a/clang-tools-extra/clangd/FindSymbols.cpp b/clang-tools-extra/clangd/FindSymbols.cpp
index f2e7dd254cf..3ecbd709085 100644
--- a/clang-tools-extra/clangd/FindSymbols.cpp
+++ b/clang-tools-extra/clangd/FindSymbols.cpp
@@ -9,12 +9,16 @@
 #include "FindSymbols.h"
 
 #include "Logger.h"
+#include "FuzzyMatch.h"
 #include "SourceCode.h"
+#include "Quality.h"
 #include "index/Index.h"
 #include "clang/Index/IndexSymbol.h"
 #include "llvm/Support/FormatVariadic.h"
 #include "llvm/Support/Path.h"
 
+#define DEBUG_TYPE "FindSymbols"
+
 namespace clang {
 namespace clangd {
 
@@ -79,6 +83,15 @@ SymbolKind indexSymbolKindToSymbolKind(index::SymbolKind Kind) {
   llvm_unreachable("invalid symbol kind");
 }
 
+using ScoredSymbolInfo = std::pair<float, SymbolInformation>;
+struct ScoredSymbolGreater {
+  bool operator()(const ScoredSymbolInfo &L, const ScoredSymbolInfo &R) {
+    if (L.first != R.first)
+      return L.first > R.first;
+    return L.second.name < R.second.name; // Earlier name is better.
+  }
+};
+
 } // namespace
 
 llvm::Expected<std::vector<SymbolInformation>>
@@ -101,7 +114,9 @@ getWorkspaceSymbols(StringRef Query, int Limit,
     Req.Scopes = {Names.first};
   if (Limit)
     Req.MaxCandidateCount = Limit;
-  Index->fuzzyFind(Req, [&Result](const Symbol &Sym) {
+  TopN<ScoredSymbolInfo, ScoredSymbolGreater> Top(Req.MaxCandidateCount);
+  FuzzyMatcher Filter(Req.Query);
+  Index->fuzzyFind(Req, [&Top, &Filter](const Symbol &Sym) {
     // Prefer the definition over e.g. a function declaration in a header
     auto &CD = Sym.Definition ? Sym.Definition : Sym.CanonicalDeclaration;
     auto Uri = URI::parse(CD.FileURI);
@@ -132,8 +147,30 @@ getWorkspaceSymbols(StringRef Query, int Limit,
     std::string Scope = Sym.Scope;
     StringRef ScopeRef = Scope;
     ScopeRef.consume_back("::");
-    Result.push_back({Sym.Name, SK, L, ScopeRef});
+    SymbolInformation Info = {Sym.Name, SK, L, ScopeRef};
+
+    SymbolQualitySignals Quality;
+    Quality.merge(Sym);
+    SymbolRelevanceSignals Relevance;
+    Relevance.Query = SymbolRelevanceSignals::Generic;
+    if (auto NameMatch = Filter.match(Sym.Name))
+      Relevance.NameMatch = *NameMatch;
+    else {
+      log(llvm::formatv("Workspace symbol: {0} didn't match query {1}",
+                        Sym.Name, Filter.pattern()));
+      return;
+    }
+    Relevance.merge(Sym);
+    auto Score =
+        evaluateSymbolAndRelevance(Quality.evaluate(), Relevance.evaluate());
+    LLVM_DEBUG(llvm::dbgs() << "FindSymbols: " << Sym.Scope << Sym.Name << " = "
+                            << Score << "\n"
+                            << Quality << Relevance << "\n");
+
+    Top.push({Score, std::move(Info)});
   });
+  for (auto &R : std::move(Top).items())
+    Result.push_back(std::move(R.second));
   return Result;
 }
 
diff --git a/clang-tools-extra/unittests/clangd/FindSymbolsTests.cpp b/clang-tools-extra/unittests/clangd/FindSymbolsTests.cpp
index e4eea0bebe1..d8483e98df1 100644
--- a/clang-tools-extra/unittests/clangd/FindSymbolsTests.cpp
+++ b/clang-tools-extra/unittests/clangd/FindSymbolsTests.cpp
@@ -264,6 +264,17 @@ TEST_F(WorkspaceSymbolsTest, Enums) {
   EXPECT_THAT(getSymbols("ns::Color4::White"), ElementsAre(Named("White")));
 }
 
+TEST_F(WorkspaceSymbolsTest, Ranking) {
+  addFile("foo.h", R"cpp(
+      namespace ns{}
+      function func();
+      )cpp");
+  addFile("foo.cpp", R"cpp(
+      #include "foo.h"
+      )cpp");
+  EXPECT_THAT(getSymbols("::"), ElementsAre(Named("func"), Named("ns")));
+}
+
 TEST_F(WorkspaceSymbolsTest, WithLimit) {
   addFile("foo.h", R"cpp(
       int foo;
@@ -272,6 +283,7 @@ TEST_F(WorkspaceSymbolsTest, WithLimit) {
   addFile("foo.cpp", R"cpp(
       #include "foo.h"
       )cpp");
+  // Foo is higher ranked because of exact name match.
   EXPECT_THAT(getSymbols("foo"),
               UnorderedElementsAre(AllOf(Named("foo"), InContainer(""),
                                          WithKind(SymbolKind::Variable)),
@@ -279,9 +291,7 @@ TEST_F(WorkspaceSymbolsTest, WithLimit) {
                                          WithKind(SymbolKind::Variable))));
 
   Limit = 1;
-  EXPECT_THAT(getSymbols("foo"),
-              ElementsAre(AnyOf((Named("foo"), InContainer("")),
-                                AllOf(Named("foo2"), InContainer("")))));
+  EXPECT_THAT(getSymbols("foo"), ElementsAre(Named("foo")));
 }
 
 } // namespace clangd