[clangd] Support filtering by fixing scopes in fuzzyFind.

[ioeric]

Summary

When scopes are specified, only match symbols from scopes.

[ioeric]

• minor cleanup.

[sammccall]

Nice, thanks!
Some suggestions for further tightening the semantics, I'm happy to do these as a followup if you think it's too invasive here.

clangd/index/Index.h

127

If i'm reading this right, you still support fuzzy-matching the scopes (scope information can be in Query, or Scopes, or both). Why? Semantics would be simpler if query matched the identifier only.

133

nit: can we choose one?
i.e. we should mandate one of

• {"", "foo", "foo::bar"}
• {"", "::foo", "::foo::bar"}
• {"", "foo::", "foo::bar::"}
• {"::", "::foo::", "::foo::bar::"}

Allowing multiple options is somewhat confusing to callers and puts a bigger burden on implementers of this interface.

clangd/index/MemIndex.cpp

30

Rather than doing tricky matches against QName, it may be simpler to split Symbol::QName into Symbol::Scope + Symbol::Name. In addition to this becoming exact string matching without parsing, the Symbol::Scopes will have lots of duplicates that can share storage, reducing the size of each Symbol.

WDYT?

[ioeric]

• Address review comments.

[ioeric]

Thanks for the review!

clangd/index/Index.h

127

This makes a lot of sense.

[sammccall]

just nits, all this stuff up to you

clangd/index/Index.h

128

I think the rest of the comment isn't needed now - the first two sentences are enough (plus the comment on Scopes)

clangd/index/MemIndex.cpp

39

This is too early - we may not actually have an N+1th match :-(

clangd/index/SymbolCollector.cpp

63 ↗

(On Diff #127478)

If you'll never have leading ::, assert that.
Otherwise strip it (I think an assert is better unless you actually expect it)

unittests/clangd/FileIndexTests.cpp

127 ↗

(On Diff #127478)

nit: i usually find Req.Scopes = {"ns"} more clear, up to you

[ioeric]

• Address a few more comments.

[ioeric]

• Minor cleanup

clangd/index/Index.h

 private:
   bool Frozen = false;
 
   llvm::DenseMap<SymbolID, Symbol> Symbols;
 };
 
 struct FuzzyFindRequest {
   /// \brief A query string for the fuzzy find. This is matched against symbols'
-  /// qualfified names.
+  /// qualified names. If any scope below is provided, \p Query is only matched
+  /// against symbols in the scope (excl. symbols in nested scopes).
   std::string Query;
+  /// \brief If this is non-empty, symbols must be in at least one of the scopes
+  /// (e.g. namespaces) excluding nested scopes. For example, if a scope "xyz"
+  /// is provided, the matched symbols must be defined in scope "xyz" but not
+  /// "xyz::abc". "" and "::" are interpreted as the global namespace.
+  std::vector<std::string> Scopes;
   /// \brief The maxinum number of candidates to return.
   size_t MaxCandidateCount = UINT_MAX;
 };
 
 /// \brief Interface for symbol indexes that can be used for searching or
 /// matching symbols among a set of symbols based on names or unique IDs.
 class SymbolIndex {
 public:

clangd/index/MemIndex.cpp

// Swap out the old symbols and index.
     std::lock_guard<std::mutex> Lock(Mutex);
     Index = std::move(TempIndex);
     Symbols = std::move(Syms); // Relase old symbols.
   }
 }
 
 bool MemIndex::fuzzyFind(Context & /*Ctx*/, const FuzzyFindRequest &Req,
                          std::function<void(const Symbol &)> Callback) const {
-  std::string LoweredQuery = llvm::StringRef(Req.Query).lower();
+  std::vector<std::string> FixedPrefixes;
+  for (StringRef Scope : Req.Scopes)
+    FixedPrefixes.push_back(
+        (Scope == "::" || Scope.empty()) ? "" : (Scope + "::").str());
+
   unsigned Matched = 0;
   {
     std::lock_guard<std::mutex> Lock(Mutex);
     for (const auto Pair : Index) {
-      const Symbol *Sym = Pair.second;
-      // Find all symbols that contain the query, igoring cases.
-      // FIXME: consider matching chunks in qualified names instead the whole
-      // string.
-      // FIXME: use better matching algorithm, e.g. fuzzy matcher.
-      if (StringRef(StringRef(Sym->QualifiedName).lower())
-              .contains(LoweredQuery)) {
-        if (++Matched > Req.MaxCandidateCount)
-          return false;
+      if (Matched >= Req.MaxCandidateCount)
+      const Symbol *Sym = Pair.second;
+
+      auto Match = [&](llvm::StringRef Name) {
+        // FIXME(ioeric): use fuzzy matcher.
+        if (!StringRef(Name.lower()).contains(Req.Query))
+          return;
+        Matched++;
         Callback(*Sym);
+      };
+
+      StringRef QName = Sym->QualifiedName;
+      if (FixedPrefixes.empty()) {
+        // No prefix is specified. Simply match the entire qualified name.
+        Match(QName);
+      } else {
+        // Try (exact-)matching against possible scopes/prefixes.
+        for (StringRef Prefix : FixedPrefixes) {
+          // Only match symbols that are directly defined in the scope.
+          if (QName.consume_front(Prefix) && !QName.contains("::")) {
+            Match(QName);
+            // Skip the rest scopes since a symbols have only one scope.
+            break;
+          }
+        }
       }
     }
   }
   return true;
 }
 
 } // namespace clangd
 } // namespace clang

unittests/clangd/IndexTests.cpp

Symbol symbol(llvm::StringRef ID) {
   return Sym;
 }
 
 struct SlabAndPointers {
   SymbolSlab Slab;
   std::vector<const Symbol *> Pointers;
 };
 
-// Create a slab of symbols with IDs and names [Begin, End]. The life time of
-// the slab is managed by the returned shared pointer. If \p WeakSymbols is
-// provided, it will be pointed to the managed object in the returned shared
-// pointer.
+// Create a slab of symbols with the given qualified names as both IDs and
+// names. The life time of the slab is managed by the returned shared pointer.
+// If \p WeakSymbols is provided, it will be pointed to the managed object in
+// the returned shared pointer.
 std::shared_ptr<std::vector<const Symbol *>>
-generateNumSymbols(int Begin, int End,
-                   std::weak_ptr<SlabAndPointers> *WeakSymbols = nullptr) {
+generateSymbols(std::vector<std::string> QualifiedNames,
   auto Slab = std::make_shared<SlabAndPointers>();
   if (WeakSymbols)
     *WeakSymbols = Slab;
 
-  for (int i = Begin; i <= End; i++)
-    Slab->Slab.insert(symbol(std::to_string(i)));
+  for (llvm::StringRef QName : QualifiedNames)
+    Slab->Slab.insert(symbol(QName));
 
   for (const auto &Sym : Slab->Slab)
     Slab->Pointers.push_back(&Sym.second);
 
   auto *Pointers = &Slab->Pointers;
   return {std::move(Slab), Pointers};
 }
 
+// Create a slab of symbols with IDs and names [Begin, End], otherwise identical
+// to the `generateSymbols` above.
+std::shared_ptr<std::vector<const Symbol *>>
+generateNumSymbols(int Begin, int End,
+                   std::weak_ptr<SlabAndPointers> *WeakSymbols = nullptr) {
+  std::vector<std::string> Names;
+  for (int i = Begin; i <= End; i++)
+    Names.push_back(std::to_string(i));
+  return generateSymbols(Names, WeakSymbols);
+}
+
 std::vector<std::string> match(const SymbolIndex &I,
                                const FuzzyFindRequest &Req) {
   std::vector<std::string> Matches;
   auto Ctx = Context::empty();
   I.fuzzyFind(Ctx, Req,
               [&](const Symbol &Sym) { Matches.push_back(Sym.QualifiedName); });
   return Matches;
 }
TEST(MemIndexTest, MemIndexLimitedNumMatches) {
   I.build(generateNumSymbols(0, 100));
   FuzzyFindRequest Req;
   Req.Query = "5";
   Req.MaxCandidateCount = 3;
   auto Matches = match(I, Req);
   EXPECT_EQ(Matches.size(), Req.MaxCandidateCount);
 }
 
+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"));
+}
+
+TEST(MemIndexTest, MatchQualifiedNamesWithGlobalScope) {
+  MemIndex I;
+  I.build(generateSymbols({"a::xyz", "b::yz", "yz"}));
+  FuzzyFindRequest Req;
+  Req.Query = "y";
+  Req.Scopes.push_back("::");
+  auto Matches = match(I, Req);
+  EXPECT_THAT(match(I, Req), UnorderedElementsAre("yz"));
+}
+
+TEST(MemIndexTest, MatchQualifiedNamesWithOneScope) {
+  MemIndex I;
+  I.build(generateSymbols({"a::xyz", "a::yy", "a::xz", "b::yz", "yz"}));
+  FuzzyFindRequest Req;
+  Req.Query = "y";
+  Req.Scopes.push_back("a");
+  auto Matches = match(I, Req);
+  EXPECT_THAT(match(I, Req), UnorderedElementsAre("a::xyz", "a::yy"));
+}
+
+TEST(MemIndexTest, MatchQualifiedNamesWithMultipleScopes) {
+  MemIndex I;
+  I.build(generateSymbols({"a::xyz", "a::yy", "a::xz", "b::yz", "yz"}));
+  FuzzyFindRequest Req;
+  Req.Query = "y";
+  Req.Scopes.push_back("a");
+  Req.Scopes.push_back("b");
+  auto Matches = match(I, Req);
+  EXPECT_THAT(match(I, Req), UnorderedElementsAre("a::xyz", "a::yy", "b::yz"));
+}
+
+TEST(MemIndexTest, NoMatchNestedScopes) {
+  MemIndex I;
+  I.build(generateSymbols({"a::xyz", "a::b::yy"}));
+  FuzzyFindRequest Req;
+  Req.Query = "y";
+  Req.Scopes.push_back("a");
+  auto Matches = match(I, Req);
+  EXPECT_THAT(match(I, Req), UnorderedElementsAre("a::xyz"));
+}
+
 } // namespace
 } // namespace clangd
 } // namespace clang