[clangd] Support filtering by fixing scopes in fuzzyFind.

Summary: When scopes are specified, only match symbols from scopes.

Reviewers: sammccall

Reviewed By: sammccall

Subscribers: klimek, ilya-biryukov, cfe-commits

Differential Revision: https://reviews.llvm.org/D41367

git-svn-id: https://llvm.org/svn/llvm-project/clang-tools-extra/trunk@321067 91177308-0d34-0410-b5e6-96231b3b80d8

4 files changed, 50 insertions, 13 deletions

diff --git a/clangd/index/Index.h b/clangd/index/Index.h
index 886e880b..1cb8943a 100644
--- a/clangd/index/Index.h
+++ b/clangd/index/Index.h
@@ -76,8 +76,11 @@ void operator>>(llvm::StringRef HexStr, SymbolID &ID);
 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.
@@ -124,8 +127,16 @@ private:
 
 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;
 };
diff --git a/clangd/index/MemIndex.cpp b/clangd/index/MemIndex.cpp
index 98896757..cc4c0ed8 100644
--- a/clangd/index/MemIndex.cpp
+++ b/clangd/index/MemIndex.cpp
@@ -8,6 +8,7 @@
 //===-------------------------------------------------------------------===//
 
 #include "MemIndex.h"
+#include "Logger.h"
 
 namespace clang {
 namespace clangd {
@@ -25,20 +26,30 @@ void MemIndex::build(std::shared_ptr<std::vector<const Symbol *>> Syms) {
   }
 }
 
-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);
diff --git a/clangd/index/SymbolCollector.cpp b/clangd/index/SymbolCollector.cpp
index 5b364291..6b575ab6 100644
--- a/clangd/index/SymbolCollector.cpp
+++ b/clangd/index/SymbolCollector.cpp
@@ -56,6 +56,18 @@ std::string makeAbsolutePath(const SourceManager &SM, StringRef Path) {
   }
   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.
@@ -86,7 +98,9 @@ bool SymbolCollector::handleDeclOccurence(
     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)});
   }
 
diff --git a/clangd/index/SymbolYAML.cpp b/clangd/index/SymbolYAML.cpp
index 9d89cc9a..beb0ab55 100644
--- a/clangd/index/SymbolYAML.cpp
+++ b/clangd/index/SymbolYAML.cpp
@@ -64,7 +64,8 @@ template<> struct MappingTraits<Symbol> {
     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);
   }