[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

112

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

121

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())
  ...

125–130

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

137

nit: fuzzyfind

139

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.

162

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

44

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

262

Partil -> Partial

[kadircet]

clang-tools-extra/clangd/FindSymbols.cpp

44

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

44

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

44

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

46

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"
 
 #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-scope inside \p Scope.
+bool approximateScopeMatch(llvm::StringRef Scope,
+                           llvm::ArrayRef<llvm::StringRef> Query) {
+  if (Query.empty())
+    return true;
+
+  llvm::SmallVector<llvm::StringRef, 2> Scopes;
+  Scope.split(Scopes, "::");
+
+  llvm::ArrayRef<llvm::StringRef> ScopesRef(Scopes);
+  // We perform a naive string search below, assuming scopes as our characters.
+  while (ScopesRef.size() >= Query.size()) {
+    // Trim Scopes from left until we find the first scope of Query. E.g:
+    // Scopes: a::b::c::
+    // Query:     b::c::
+    // This will trim `a::` from Scopes.
+    ScopesRef = ScopesRef.drop_while(
+        [FirstQueryScope = Query.front()](llvm::StringRef Scope) {
+          return Scope != FirstQueryScope;
+        });
+    if (ScopesRef.size() < Query.size())
+      break;
+    // Check if ScopesRef prefix matches Query.
+    if (ScopesRef.take_front(Query.size()).equals(Query))
+      return true;
+    // If not try with the rest.
+    ScopesRef = ScopesRef.drop_front();
+  }
+  return false;
+}
+
 } // 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) {
+
+  llvm::SmallVector<llvm::StringRef, 2> ReqScopes;
+  Names.first.consume_back("::");
+  if (!Names.first.empty())
+    Names.first.split(ReqScopes, "::");
+  Index->fuzzyFind(Req, [HintPath, &Top, &Filter, &ReqScopes,
+                         AnyScope = Req.AnyScope,
+                         ReqScope = Names.first](const Symbol &Sym) {
+    std::string Scope = std::string(Sym.Scope);
+    llvm::StringRef ScopeRef = Scope;
+    ScopeRef.consume_back("::");
+    // Fuzzyfind might return symbols from irrelevant namespaces if query was
+    // not fully-qualified, drop those.
+    if (AnyScope && !approximateScopeMatch(ScopeRef, ReqScopes))
+      return;
+
     auto Loc = symbolToLocation(Sym, HintPath);
     if (!Loc) {
       log("Workspace symbols: {0}", Loc.takeError());
       return;
     }
 
     SymbolKind SK = indexSymbolKindToSymbolKind(Sym.SymInfo.Kind);
-    std::string Scope = std::string(Sym.Scope);
-    llvm::StringRef ScopeRef = Scope;
-    ScopeRef.consume_back("::");
     SymbolInformation Info = {(Sym.Name + Sym.TemplateSpecializationArgs).str(),
                               SK, *Loc, std::string(ScopeRef)};
 
     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 && ScopeRef != 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);

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

TU.Code = R"cpp(
       )cpp";
   EXPECT_THAT(getSymbols(TU, "a"),
               UnorderedElementsAre(QName("ans1"), QName("ans1::ai1"),
                                    QName("ans1::ans2"),
                                    QName("ans1::ans2::ai2")));
   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")));
+  EXPECT_THAT(getSymbols(TU, "ans2::"),
+              UnorderedElementsAre(QName("ans1::ans2::ai2")));
   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")));
 }
 
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, RankingPartilNamespace) {
+  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"