[clangd] Enable partial namespace matches for workspace symbols

[kadircet]

Summary

This will enable queries like "clangd::" to find symbols under clangd
namespace, without requiring full "clang::clangd::" qualification.

Since Fuzzyfind performs the search under all scopes and only boosts the symbols
from relevant namespaces, we might get symbols from non-matching namespaces.
This patch chooses to drop those as they clearly do not match the query.

Fixes https://github.com/clangd/clangd/issues/550.

[sammccall]

clang-tools-extra/clangd/FindSymbols.cpp

104

Add a comment here (or elsewhere, I guess) about how qualified names are handled.

• exact namespace: boosted on the index side
• approximate namespace (e.g. substring): included using "all scopes" logic
• non-matching namespace (no subtring match): filtered out from index-provided results

113

This expression doesn't make sense (except in context of the above code). Variables are cheap!

LeadingColons = consume_front("::");
Req.AnyScope = !LeadingColons
if (LeadingColons || !Names.first.empty())
  ...

117–122

Given the dynamic filter, we should request a greater multiple here (this time if anyscope && Names.first.empty is the right logic!)

This gives us a second class of regression :-) but we can tune the multiple to control it. I'd suggest 5 or so

129

nit: fuzzyfind

131

Pull out a approximateScopeMatch(scope, query) or so function?

Substring isn't quite right - fine for now with a fixme, but might as well pull out the function now so we don't make a mess when the code grows.

143

Would be nice to incorporate exact vs approximate scope match here: people complain a lot when an exact string match ranks below an approximate one.

I don't think ScopeDistance works as-is, because it assumes the reference point (query) is absolute.
You could consider NeedsFixIts or applying a multiplier to NameMatch (0.3?) or InBaseClass (all of these are a stretch I guess)

[kadircet]

• Perform sub-scope matching rather than substring match for partial namespaces.
• Apply a penalty for partially matching namespaces.

[sammccall]

clang-tools-extra/clangd/FindSymbols.cpp

45

I had a little trouble following this...
It seems a little simpler (fewer vars to track) if we avoid the up-front split on scopes.

assert(Scope.empty() || Scope.endswith("::")); // or handle in some way
// Walk through Scope, consuming matching tokens from Query.
StringRef First;
while (!Scope.empty() && !Query.empty()) {
  tie(First, Scope) = Scope.split("::");
  if (Query.front() == First)
    Query = Query.drop_front();
}
return Query.empty(); // all components of query matched

in fact we can avoid preprocessing query too:

// Query is just a StringRef
assert(Scope.empty() || Scope.endswith("::")); // or handle in some way
assert(Query.empty() || Query.endswith("::"));

// Walk through Scope, consuming matching tokens from Query.
StringRef First;
while (!Scope.empty() && !Query.empty()) {
  tie(First, Scope) = Scope.split("::");
  Query.consume_front(StringRef(First.data(), First.size() + 2) /*Including ::*/);
}
return Query.empty(); // all components of query matched

clang-tools-extra/clangd/unittests/FindSymbolsTests.cpp

274

Partil -> Partial

[kadircet]

clang-tools-extra/clangd/FindSymbols.cpp

45

Yes but they would do different things. I believe the confusion is caused by usage of sub-scope without a clear definition. The codes you've suggested are performing sub-sequence matches rather than sub-string(i.e. we are looking for a contigious segment in Scope that matches Query).

I believe a query of the form a::c:: shouldn't be matched by a::b::c::. I can try simplifying the logic, but it would be nice to agree on the behaviour :D.

Sorry if I miscommunicated this so far.

[sammccall]

clang-tools-extra/clangd/FindSymbols.cpp

45

Ah right, I was indeed misreading the code. Let's have some definitions...

given query a::b::Foo with scope a::b::

	a::b::	W::a::b::	a::X::b::	a::b::Y
exact	*
prefix	*			*
suffix	*	*
substring	*	*		*
subsequence	*	*	*	*

These support correcting different types of "errors":

• exact: none
• prefix: may omit namespaces immediately before Foo
• suffix: query may be rooted anywhere (other than global ns)
• substring: query rooted anywhere, omit namespaces before Foo
• subsequence: may omit any component

We know "exact" is too strict.

I think "prefix" and by extension "substring" aren't particularly compelling rules as the "immediately before Foo" requirement is arbitrary.
Why does a::b::Foo match a::b::c::Foo and not a::c::b::Foo? In each case we've omitted a namespace inside the query, the only difference is what it's sandwiched between.

Suffix makes intuitive sense, it accepts strings that make sense *somewhere* in the codebase.
Subsequence makes intuitive sense too: you're allowed to forget uninteresting components, similar to how fuzzy-match lets you omit uninteresting words.

I'd prefer one of those and don't really mind which - I'd assumed subsequence was intended. Suffix is way easier to implement though :-)

[kadircet]

• Switch from substring to subscope matching.

clang-tools-extra/clangd/FindSymbols.cpp

45

Thanks for the nice table :D

I was mainly shying away from subsequence as I thought it would be too loose, but I suppose it is okay thinking about the fuzzyfind logic. So I've changed the implementation to be that way, while adding some tests.

[sammccall]

Yeah, we can fairly easily make this tighter if it's noisy. My suspicion is people will rather complain about ranking than these results being totally irrelevant.
Nice that we now have workspace/symbols users that can send this feedback!

clang-tools-extra/clangd/FindSymbols.cpp

47

there's no need for these to be special cases, the loop handles them correctly

It simplifies the asserts slightly, but seems like false economy

[kadircet]

• Move if checks into asserts.

clang-tools-extra/clangd/FindSymbols.cpp

 #include "Quality.h"
 #include "SourceCode.h"
 #include "index/Index.h"
 #include "support/Logger.h"
 #include "clang/AST/DeclTemplate.h"
 #include "clang/Index/IndexDataConsumer.h"
 #include "clang/Index/IndexSymbol.h"
 #include "clang/Index/IndexingAction.h"
+#include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/FormatVariadic.h"
 #include "llvm/Support/Path.h"
 #include "llvm/Support/ScopedPrinter.h"
+#include <tuple>
 
 #define DEBUG_TYPE "FindSymbols"
 
 namespace clang {
 namespace clangd {
 
 namespace {
 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.
   }
 };
 
+// Returns true if \p Query can be found as a sub-sequence inside \p Scope.
+bool approximateScopeMatch(llvm::StringRef Scope, llvm::StringRef Query) {
+  // An empty query always matches the scope.
+  if (Query.empty())
+    return true;
+  // Query is non-empty, so cannot be matched.
+  if (Scope.empty())
+    return false;
+
+  assert(Scope.endswith("::"));
+  assert(Query.endswith("::"));
+  while (!Scope.empty() && !Query.empty()) {
+    auto Colons = Scope.find("::");
+    assert(Colons != llvm::StringRef::npos);
+
+    llvm::StringRef LeadingSpecifier = Scope.slice(0, Colons + 2);
+    Scope = Scope.slice(Colons + 2, llvm::StringRef::npos);
+    Query.consume_front(LeadingSpecifier);
+  }
+  return Query.empty();
+}
+
 } // namespace
 
 llvm::Expected<Location> indexToLSPLocation(const SymbolLocation &Loc,
                                             llvm::StringRef TUPath) {
   auto Path = URI::resolve(Loc.FileURI, TUPath);
   if (!Path)
     return error("Could not resolve path for file '{0}': {1}", Loc.FileURI,
                  Path.takeError());

 
 llvm::Expected<std::vector<SymbolInformation>>
 getWorkspaceSymbols(llvm::StringRef Query, int Limit,
                     const SymbolIndex *const Index, llvm::StringRef HintPath) {
   std::vector<SymbolInformation> Result;
   if (Query.empty() || !Index)
     return Result;
 
+  // Lookup for qualified names are performed as:
+  // - Exact namespaces are boosted by the index.
+  // - Approximate matches are (sub-scope match) included via AnyScope logic.
+  // - Non-matching namespaces (no sub-scope match) are post-filtered.
   auto Names = splitQualifiedName(Query);
 
   FuzzyFindRequest Req;
   Req.Query = std::string(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())
+  // FuzzyFind doesn't want leading :: qualifier.
+  auto HasLeadingColons = Names.first.consume_front("::");
+  // Limit the query to specific namespace if it is fully-qualified.
+  Req.AnyScope = !HasLeadingColons;
+  // Boost symbols from desired namespace.
+  if (HasLeadingColons || !Names.first.empty())
     Req.Scopes = {std::string(Names.first)};
-  else
-    Req.AnyScope = true;
-  if (Limit)
+  if (Limit) {
     Req.Limit = Limit;
+    // If we are boosting a specific scope allow more results to be retrieved,
+    // since some symbols from preferred namespaces might not make the cut.
+    if (Req.AnyScope && !Req.Scopes.empty())
+      *Req.Limit *= 5;
+  }
   TopN<ScoredSymbolInfo, ScoredSymbolGreater> Top(
       Req.Limit ? *Req.Limit : std::numeric_limits<size_t>::max());
   FuzzyMatcher Filter(Req.Query);
-  Index->fuzzyFind(Req, [HintPath, &Top, &Filter](const Symbol &Sym) {
+
+  Index->fuzzyFind(Req, [HintPath, &Top, &Filter, AnyScope = Req.AnyScope,
+                         ReqScope = Names.first](const Symbol &Sym) {
+    llvm::StringRef Scope = Sym.Scope;
+    // Fuzzyfind might return symbols from irrelevant namespaces if query was
+    // not fully-qualified, drop those.
+    if (AnyScope && !approximateScopeMatch(Scope, ReqScope))
+      return;
+
     auto Loc = symbolToLocation(Sym, HintPath);
     if (!Loc) {
       log("Workspace symbols: {0}", Loc.takeError());
       return;
     }
 
-    llvm::StringRef Scope = Sym.Scope;
-    Scope.consume_back("::");
-    SymbolInformation Info;
-    Info.name = (Sym.Name + Sym.TemplateSpecializationArgs).str();
-    Info.kind = indexSymbolKindToSymbolKind(Sym.SymInfo.Kind);
-    Info.location = *Loc;
-    Info.containerName = Scope.str();
-
     SymbolQualitySignals Quality;
     Quality.merge(Sym);
     SymbolRelevanceSignals Relevance;
     Relevance.Name = Sym.Name;
     Relevance.Query = SymbolRelevanceSignals::Generic;
+    // If symbol and request scopes do not match exactly, apply a penalty.
+    Relevance.InBaseClass = AnyScope && Scope != ReqScope;
     if (auto NameMatch = Filter.match(Sym.Name))
       Relevance.NameMatch = *NameMatch;
     else {
       log("Workspace symbol: {0} didn't match query {1}", Sym.Name,
           Filter.pattern());
       return;
     }
     Relevance.merge(Sym);
     auto Score = evaluateSymbolAndRelevance(Quality.evaluateHeuristics(),
                                             Relevance.evaluateHeuristics());
     dlog("FindSymbols: {0}{1} = {2}\n{3}{4}\n", Sym.Scope, Sym.Name, Score,
          Quality, Relevance);
 
+    SymbolInformation Info;
+    Info.name = (Sym.Name + Sym.TemplateSpecializationArgs).str();
+    Info.kind = indexSymbolKindToSymbolKind(Sym.SymInfo.Kind);
+    Info.location = *Loc;
+    Scope.consume_back("::");
+    Info.containerName = Scope.str();
+
     // Exposed score excludes fuzzy-match component, for client-side re-ranking.
     Info.score = Score / Relevance.NameMatch;
     Top.push({Score, std::move(Info)});
   });
   for (auto &R : std::move(Top).items())
     Result.push_back(std::move(R.second));
   return Result;
 }

clang-tools-extra/clangd/unittests/FindSymbolsTests.cpp

EXPECT_THAT(getSymbols(TU, "test"),
               ElementsAre(QName("test"), QName("test2")));
 }
 
 TEST(WorkspaceSymbols, Namespaces) {
   TestTU TU;
   TU.AdditionalFiles["foo.h"] = R"cpp(
       namespace ans1 {
         int ai1;
         namespace ans2 {
           int ai2;
+          namespace ans3 {
+            int ai3;
+          }
         }
       }
       )cpp";
   TU.Code = R"cpp(
       #include "foo.h"
       )cpp";
   EXPECT_THAT(getSymbols(TU, "a"),
-              UnorderedElementsAre(QName("ans1"), QName("ans1::ai1"),
-                                   QName("ans1::ans2"),
-                                   QName("ans1::ans2::ai2")));
+              UnorderedElementsAre(
+                  QName("ans1"), QName("ans1::ai1"), QName("ans1::ans2"),
+                  QName("ans1::ans2::ai2"), QName("ans1::ans2::ans3"),
+                  QName("ans1::ans2::ans3::ai3")));
   EXPECT_THAT(getSymbols(TU, "::"), ElementsAre(QName("ans1")));
   EXPECT_THAT(getSymbols(TU, "::a"), ElementsAre(QName("ans1")));
   EXPECT_THAT(getSymbols(TU, "ans1::"),
-              UnorderedElementsAre(QName("ans1::ai1"), QName("ans1::ans2")));
+              UnorderedElementsAre(QName("ans1::ai1"), QName("ans1::ans2"),
+                                   QName("ans1::ans2::ai2"),
+                                   QName("ans1::ans2::ans3"),
+                                   QName("ans1::ans2::ans3::ai3")));
+  EXPECT_THAT(getSymbols(TU, "ans2::"),
+              UnorderedElementsAre(QName("ans1::ans2::ai2"),
+                                   QName("ans1::ans2::ans3"),
+                                   QName("ans1::ans2::ans3::ai3")));
   EXPECT_THAT(getSymbols(TU, "::ans1"), ElementsAre(QName("ans1")));
   EXPECT_THAT(getSymbols(TU, "::ans1::"),
               UnorderedElementsAre(QName("ans1::ai1"), QName("ans1::ans2")));
   EXPECT_THAT(getSymbols(TU, "::ans1::ans2"), ElementsAre(QName("ans1::ans2")));
   EXPECT_THAT(getSymbols(TU, "::ans1::ans2::"),
-              ElementsAre(QName("ans1::ans2::ai2")));
+              ElementsAre(QName("ans1::ans2::ai2"), QName("ans1::ans2::ans3")));
+
+  // Ensure sub-sequence matching works.
+  EXPECT_THAT(getSymbols(TU, "ans1::ans3::ai"),
+              UnorderedElementsAre(QName("ans1::ans2::ans3::ai3")));
 }
 
 TEST(WorkspaceSymbols, AnonymousNamespace) {
   TestTU TU;
   TU.Code = R"cpp(
       namespace {
       void test() {}
       }
TU.AdditionalFiles["foo.h"] = R"cpp(
       void func();
       )cpp";
   TU.Code = R"cpp(
       #include "foo.h"
       )cpp";
   EXPECT_THAT(getSymbols(TU, "::"), ElementsAre(QName("func"), QName("ns")));
 }
 
+TEST(WorkspaceSymbols, RankingPartialNamespace) {
+  TestTU TU;
+  TU.Code = R"cpp(
+    namespace ns1 {
+      namespace ns2 { struct Foo {}; }
+    }
+    namespace ns2 { struct FooB {}; })cpp";
+  EXPECT_THAT(getSymbols(TU, "ns2::f"),
+              ElementsAre(QName("ns2::FooB"), QName("ns1::ns2::Foo")));
+}
+
 TEST(WorkspaceSymbols, WithLimit) {
   TestTU TU;
   TU.AdditionalFiles["foo.h"] = R"cpp(
       int foo;
       int foo2;
       )cpp";
   TU.Code = R"cpp(
       #include "foo.h"