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

[sammccall]

Summary

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

[hokein]

LGTM.

clangd/FindSymbols.cpp

159

Should we add a log statement here? IMO, this rarely happens? If it happens, it means that the fuzzy matcher algorithms used by index and clangd side have disagreement.

[malaperle]

This works much better! Just a nit.

clangd/FindSymbols.cpp

20

nit: I don't think this is used. Remove?

[sammccall]

clangd/FindSymbols.cpp

20

This is consumed by the LLVM_DEBUG macro. You can enable program-wide debug output with -debug, but much more useful is -debug-only=somestring which will only enable LLVM_DEBUG sections in files with the matching DEBUG_TYPE.

So here if you get mysterious ranking of workspace/symbol results, you can run clangd with -debug-only=FindSymbols and get the signals and component scores dumped to stderr.

clangd/FindSymbols.cpp

 //===--- FindSymbols.cpp ------------------------------------*- C++-*------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 #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 {
 
 namespace {
 
 // Convert a index::SymbolKind to clangd::SymbolKind (LSP)
 // Note, some are not perfect matches and should be improved when this LSP
 // issue is addressed:
SymbolKind indexSymbolKindToSymbolKind(index::SymbolKind Kind) {
   case index::SymbolKind::Parameter:
     return SymbolKind::Variable;
   case index::SymbolKind::Using:
     return SymbolKind::Namespace;
   }
   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>>
 getWorkspaceSymbols(StringRef Query, int Limit,
                     const SymbolIndex *const Index) {
   std::vector<SymbolInformation> Result;
   if (Query.empty() || !Index)
     return Result;
 
   auto Names = splitQualifiedName(Query);
 
   FuzzyFindRequest Req;
   Req.Query = Names.second;
 
   // FuzzyFind doesn't want leading :: qualifier
   bool IsGlobalQuery = Names.first.consume_front("::");
   // Restrict results to the scope in the query string if present (global or
   // not).
   if (IsGlobalQuery || !Names.first.empty())
     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);
     if (!Uri) {
       log(llvm::formatv(
           "Workspace symbol: Could not parse URI '{0}' for symbol '{1}'.",
           CD.FileURI, Sym.Name));
       return;
Index->fuzzyFind(Req, [&Top, &Filter](const Symbol &Sym) {
     Start.character = CD.Start.Column;
     End.line = CD.End.Line;
     End.character = CD.End.Column;
     L.range = {Start, End};
     SymbolKind SK = indexSymbolKindToSymbolKind(Sym.SymInfo.Kind);
     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
+      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;
 }
 
 } // namespace clangd
 } // namespace clang

unittests/clangd/FindSymbolsTests.cpp

TEST_F(WorkspaceSymbolsTest, Enums) {
   EXPECT_THAT(getSymbols("Color2::Yellow"), ElementsAre(Named("Yellow")));
   EXPECT_THAT(getSymbols("Yellow"), ElementsAre(Named("Yellow")));
 
   EXPECT_THAT(getSymbols("ns::Black"), ElementsAre(Named("Black")));
   EXPECT_THAT(getSymbols("ns::Blue"), ElementsAre(Named("Blue")));
   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;
       int foo2;
       )cpp");
   addFile("foo.cpp", R"cpp(
       #include "foo.h"
       )cpp");
+  // Foo is higher ranked because of exact name match.
   EXPECT_THAT(getSymbols("foo"),
               ElementsAre(AllOf(Named("foo"), InContainer(""),
                                 WithKind(SymbolKind::Variable)),
                           AllOf(Named("foo2"), InContainer(""),
                                 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
 } // namespace clang