[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

130

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.

135

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

31–33

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

130

This makes a lot of sense.

[sammccall]

just nits, all this stuff up to you

clangd/index/Index.h

131

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

38

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

clangd/index/SymbolCollector.cpp

63

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

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

 
 // The class presents a C++ symbol, e.g. class, function.
 //
 // FIXME: instead of having own copy fields for each symbol, we can share
 // storage from SymbolSlab.
 struct Symbol {
   // The ID of the symbol.
   SymbolID ID;
-  // The qualified name of the symbol, e.g. Foo::bar.
-  std::string QualifiedName;
+  // The unqualified name of the symbol, e.g. "bar" (for "n1::n2::bar").
+  std::string Name;
+  // The scope (e.g. namespace) of the symbol, e.g. "n1::n2" (for
+  // "n1::n2::bar").
+  std::string Scope;
   // The symbol information, like symbol kind.
   index::SymbolInfo SymInfo;
   // The location of the canonical declaration of the symbol.
   //
   // A C++ symbol could have multiple declarations and one definition (e.g.
   // a function is declared in ".h" file, and is defined in ".cc" file).
   //   * For classes, the canonical declaration is usually definition.
   //   * For non-inline functions, the canonical declaration is a declaration

 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.
+  /// un-qualified identifiers and should not contain qualifiers like "::".
   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".
+  ///
+  /// A scope must be fully qualified without leading or trailing "::" e.g.
+  /// "n1::n2". "" is interpreted as the global namespace, and "::" is invalid.
+  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

 //===--- MemIndex.cpp - Dynamic in-memory symbol index. ----------*- C++-*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===-------------------------------------------------------------------===//
 
 #include "MemIndex.h"
+#include "Logger.h"
 
 namespace clang {
 namespace clangd {
 
 void MemIndex::build(std::shared_ptr<std::vector<const Symbol *>> Syms) {
   llvm::DenseMap<SymbolID, const Symbol *> TempIndex;
   for (const Symbol *Sym : *Syms)
     TempIndex[Sym->ID] = Sym;
 
   // 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,
+bool MemIndex::fuzzyFind(Context &Ctx, const FuzzyFindRequest &Req,
                          std::function<void(const Symbol &)> Callback) const {
-  std::string LoweredQuery = llvm::StringRef(Req.Query).lower();
+  assert(!StringRef(Req.Query).contains("::") &&
+         "There must be no :: in query.");
+
   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)) {
+
+      // Exact match against all possible scopes.
+      bool ScopeMatched = Req.Scopes.empty();
+      for (StringRef Scope : Req.Scopes) {
+        if (Scope == Sym->Scope) {
+          ScopeMatched = true;
+          break;
+        }
+      }
+      if (!ScopeMatched)
+        continue;
+
+      // FIXME(ioeric): use fuzzy matcher.
+      if (StringRef(StringRef(Sym->Name).lower()).contains(Req.Query)) {
         if (++Matched > Req.MaxCandidateCount)
           return false;
         Callback(*Sym);
       }
     }
   }
   return true;
 }
 
 } // namespace clangd
 } // namespace clang

clangd/index/SymbolCollector.cpp

if (Dir) {
     SmallVector<char, 128> AbsoluteFilename;
     llvm::sys::path::append(AbsoluteFilename, DirName,
                             llvm::sys::path::filename(AbsolutePath.str()));
     return llvm::StringRef(AbsoluteFilename.data(), AbsoluteFilename.size())
         .str();
   }
   return AbsolutePath.str();
 }
+
+// Split a qualified symbol name into scope and unqualified name, e.g. given
+// "a::b::c", return {"a::b", "c"}. Scope is empty if it doesn't exist.
+std::pair<llvm::StringRef, llvm::StringRef>
+splitQualifiedName(llvm::StringRef QName) {
+  assert(!QName.startswith("::") && "Qualified names should not start with ::");
+  size_t Pos = QName.rfind("::");
+  if (Pos == llvm::StringRef::npos)
+    return {StringRef(), QName};
+  return {QName.substr(0, Pos), QName.substr(Pos + 2)};
+}
+
 } // namespace
 
 // Always return true to continue indexing.
 bool SymbolCollector::handleDeclOccurence(
     const Decl *D, index::SymbolRoleSet Roles,
     ArrayRef<index::SymbolRelation> Relations, FileID FID, unsigned Offset,
     index::IndexDataConsumer::ASTNodeInfo ASTNode) {
   // FIXME: collect all symbol references.
if (const NamedDecl *ND = llvm::dyn_cast<NamedDecl>(D)) {
     auto ID = SymbolID(USR);
     if (Symbols.find(ID) != Symbols.end())
       return true;
 
     auto &SM = ND->getASTContext().getSourceManager();
     SymbolLocation Location = {
         makeAbsolutePath(SM, SM.getFilename(D->getLocation())),
         SM.getFileOffset(D->getLocStart()), SM.getFileOffset(D->getLocEnd())};
-    Symbols.insert({std::move(ID), ND->getQualifiedNameAsString(),
+    std::string QName = ND->getQualifiedNameAsString();
+    auto ScopeAndName = splitQualifiedName(QName);
+    Symbols.insert({std::move(ID), ScopeAndName.second, ScopeAndName.first,
                     index::getSymbolInfo(D), std::move(Location)});
   }
 
   return true;
 }
 
 void SymbolCollector::finish() { Symbols.freeze(); }
 
 } // namespace clangd
 } // namespace clang

clangd/index/SymbolYAML.cpp

template <> struct MappingTraits<SymbolInfo> {
   }
 };
 
 template<> struct MappingTraits<Symbol> {
   static void mapping(IO &IO, Symbol &Sym) {
     MappingNormalization<NormalizedSymbolID, SymbolID> NSymbolID(
         IO, Sym.ID);
     IO.mapRequired("ID", NSymbolID->HexString);
-    IO.mapRequired("QualifiedName", Sym.QualifiedName);
+    IO.mapRequired("Name", Sym.Name);
+    IO.mapRequired("Scope", Sym.Scope);
     IO.mapRequired("SymInfo", Sym.SymInfo);
     IO.mapRequired("CanonicalDeclaration", Sym.CanonicalDeclaration);
   }
 };
 
 template <> struct ScalarEnumerationTraits<SymbolLanguage> {
   static void enumeration(IO &IO, SymbolLanguage &Value) {
     IO.enumCase(Value, "C", SymbolLanguage::C);

unittests/clangd/FileIndexTests.cpp

 namespace clang {
 namespace clangd {
 
 namespace {
 
 Symbol symbol(llvm::StringRef ID) {
   Symbol Sym;
   Sym.ID = SymbolID(ID);
-  Sym.QualifiedName = ID;
+  Sym.Name = ID;
   return Sym;
 }
 
 void addNumSymbolsToSlab(int Begin, int End, SymbolSlab *Slab) {
   for (int i = Begin; i <= End; i++)
     Slab->insert(symbol(std::to_string(i)));
 }
 
 std::vector<std::string>
 getSymbolNames(const std::vector<const Symbol *> &Symbols) {
   std::vector<std::string> Names;
   for (const Symbol *Sym : Symbols)
-    Names.push_back(Sym->QualifiedName);
+    Names.push_back(Sym->Name);
   return Names;
 }
 
 TEST(FileSymbolsTest, UpdateAndGet) {
   FileSymbols FS;
   EXPECT_THAT(getSymbolNames(*FS.allSymbols()), UnorderedElementsAre());
 
   auto Slab = llvm::make_unique<SymbolSlab>();
TEST(FileSymbolsTest, SnapshotAliveAfterRemove) {
 
   EXPECT_THAT(getSymbolNames(*Symbols), UnorderedElementsAre("1", "2", "3"));
 }
 
 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); });
+  I.fuzzyFind(Ctx, Req, [&](const Symbol &Sym) {
+    Matches.push_back(Sym.Scope + (Sym.Scope.empty() ? "" : "::") + Sym.Name);
+  });
   return Matches;
 }
 
 /// Create an ParsedAST for \p Code. Returns None if \p Code is empty.
 llvm::Optional<ParsedAST> build(std::string Path, llvm::StringRef Code) {
   Context Ctx = Context::empty();
   if (Code.empty())
     return llvm::None;

 TEST(FileIndexTest, IndexAST) {
   FileIndex M;
   auto Ctx = Context::empty();
   M.update(
       Ctx, "f1",
       build("f1", "namespace ns { void f() {} class X {}; }").getPointer());
 
   FuzzyFindRequest Req;
-  Req.Query = "ns::";
+  Req.Query = "";
+  Req.Scopes = {"ns"};
   EXPECT_THAT(match(M, Req), UnorderedElementsAre("ns::f", "ns::X"));
 }
 
 TEST(FileIndexTest, NoLocal) {
   FileIndex M;
   auto Ctx = Context::empty();
   M.update(
       Ctx, "f1",
TEST(FileIndexTest, IndexMultiASTAndDeduplicate) {
   M.update(
       Ctx, "f1",
       build("f1", "namespace ns { void f() {} class X {}; }").getPointer());
   M.update(
       Ctx, "f2",
       build("f2", "namespace ns { void ff() {} class X {}; }").getPointer());
 
   FuzzyFindRequest Req;
-  Req.Query = "ns::";
-  EXPECT_THAT(match(M, Req),
-              UnorderedElementsAre("ns::f", "ns::X", "ns::ff"));
+  Req.Query = "";
+  Req.Scopes = {"ns"};
+  EXPECT_THAT(match(M, Req), UnorderedElementsAre("ns::f", "ns::X", "ns::ff"));
 }
 
 TEST(FileIndexTest, RemoveAST) {
   FileIndex M;
   auto Ctx = Context::empty();
   M.update(
       Ctx, "f1",
       build("f1", "namespace ns { void f() {} class X {}; }").getPointer());
 
   FuzzyFindRequest Req;
-  Req.Query = "ns::";
+  Req.Query = "";
+  Req.Scopes = {"ns"};
   EXPECT_THAT(match(M, Req), UnorderedElementsAre("ns::f", "ns::X"));
 
   M.update(Ctx, "f1", nullptr);
   EXPECT_THAT(match(M, Req), UnorderedElementsAre());
 }
 
 TEST(FileIndexTest, RemoveNonExisting) {
   FileIndex M;

unittests/clangd/IndexTests.cpp

 
 using testing::UnorderedElementsAre;
 
 namespace clang {
 namespace clangd {
 
 namespace {
 
-Symbol symbol(llvm::StringRef ID) {
+Symbol symbol(llvm::StringRef QName) {
   Symbol Sym;
-  Sym.ID = SymbolID(ID);
-  Sym.QualifiedName = ID;
+  Sym.ID = SymbolID(QName.str());
+  size_t Pos = QName.rfind("::");
+  if (Pos == llvm::StringRef::npos) {
+    Sym.Name = QName;
+    Sym.Scope = "";
+  } else {
+    Sym.Name = QName.substr(Pos + 2);
+    Sym.Scope = QName.substr(0, Pos);
+  }
   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); });
+  I.fuzzyFind(Ctx, Req, [&](const Symbol &Sym) {
+    Matches.push_back(Sym.Scope + (Sym.Scope.empty() ? "" : "::") + Sym.Name);
+  });
   return Matches;
 }
 
 TEST(MemIndexTest, MemIndexSymbolsRecycled) {
   MemIndex I;
   std::weak_ptr<SlabAndPointers> Symbols;
   I.build(generateNumSymbols(0, 10, &Symbols));
   FuzzyFindRequest Req;
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

unittests/clangd/SymbolCollectorTests.cpp

 #include <memory>
 #include <string>
 
 using testing::Eq;
 using testing::Field;
 using testing::UnorderedElementsAre;
 
 // GMock helpers for matching Symbol.
-MATCHER_P(QName, Name, "") { return arg.second.QualifiedName == Name; }
+MATCHER_P(QName, Name, "") {
+  return (arg.second.Scope + (arg.second.Scope.empty() ? "" : "::") +
+          arg.second.Name) == Name;
+}
 
 namespace clang {
 namespace clangd {
 
 namespace {
 class SymbolIndexActionFactory : public tooling::FrontendActionFactory {
 public:
   SymbolIndexActionFactory() = default;
TEST_F(SymbolCollectorTest, CollectSymbol) {
   EXPECT_THAT(Symbols, UnorderedElementsAre(QName("Foo"), QName("Foo::f"),
                                             QName("f1"), QName("f2")));
 }
 
 TEST_F(SymbolCollectorTest, YAMLConversions) {
   const std::string YAML1 = R"(
 ---
 ID: 057557CEBF6E6B2DD437FBF60CC58F352D1DF856
-QualifiedName:   'clang::Foo1'
+Name:   'Foo1'
+Scope:   'clang'
 SymInfo:
   Kind:            Function
   Lang:            Cpp
 CanonicalDeclaration:
   StartOffset:     0
   EndOffset:       1
   FilePath:        /path/foo.h
 ...
 )";
   const std::string YAML2 = R"(
 ---
 ID: 057557CEBF6E6B2DD437FBF60CC58F352D1DF858
-QualifiedName:   'clang::Foo2'
+Name:   'Foo2'
+Scope:   'clang'
 SymInfo:
   Kind:            Function
   Lang:            Cpp
 CanonicalDeclaration:
   StartOffset:     10
   EndOffset:       12
   FilePath:        /path/foo.h
 ...