Index: clangd/index/Index.h =================================================================== --- clangd/index/Index.h +++ clangd/index/Index.h @@ -76,8 +76,11 @@ 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 @@ 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 Scopes; /// \brief The maxinum number of candidates to return. size_t MaxCandidateCount = UINT_MAX; }; Index: clangd/index/MemIndex.cpp =================================================================== --- clangd/index/MemIndex.cpp +++ clangd/index/MemIndex.cpp @@ -8,6 +8,7 @@ //===-------------------------------------------------------------------===// #include "MemIndex.h" +#include "Logger.h" namespace clang { namespace clangd { @@ -25,20 +26,30 @@ } } -bool MemIndex::fuzzyFind(Context & /*Ctx*/, const FuzzyFindRequest &Req, +bool MemIndex::fuzzyFind(Context &Ctx, const FuzzyFindRequest &Req, std::function 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 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); Index: clangd/index/SymbolCollector.cpp =================================================================== --- clangd/index/SymbolCollector.cpp +++ clangd/index/SymbolCollector.cpp @@ -56,6 +56,18 @@ } 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 +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 @@ 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)}); } Index: clangd/index/SymbolYAML.cpp =================================================================== --- clangd/index/SymbolYAML.cpp +++ clangd/index/SymbolYAML.cpp @@ -64,7 +64,8 @@ MappingNormalization 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); } Index: unittests/clangd/FileIndexTests.cpp =================================================================== --- unittests/clangd/FileIndexTests.cpp +++ unittests/clangd/FileIndexTests.cpp @@ -24,7 +24,7 @@ Symbol symbol(llvm::StringRef ID) { Symbol Sym; Sym.ID = SymbolID(ID); - Sym.QualifiedName = ID; + Sym.Name = ID; return Sym; } @@ -37,7 +37,7 @@ getSymbolNames(const std::vector &Symbols) { std::vector Names; for (const Symbol *Sym : Symbols) - Names.push_back(Sym->QualifiedName); + Names.push_back(Sym->Name); return Names; } @@ -92,8 +92,9 @@ const FuzzyFindRequest &Req) { std::vector 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; } @@ -122,7 +123,8 @@ 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")); } @@ -150,9 +152,9 @@ 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) { @@ -163,7 +165,8 @@ 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); Index: unittests/clangd/IndexTests.cpp =================================================================== --- unittests/clangd/IndexTests.cpp +++ unittests/clangd/IndexTests.cpp @@ -19,10 +19,17 @@ 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; } @@ -31,19 +38,19 @@ std::vector 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> -generateNumSymbols(int Begin, int End, - std::weak_ptr *WeakSymbols = nullptr) { +generateSymbols(std::vector QualifiedNames, + std::weak_ptr *WeakSymbols = nullptr) { auto Slab = std::make_shared(); 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); @@ -52,12 +59,24 @@ 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> +generateNumSymbols(int Begin, int End, + std::weak_ptr *WeakSymbols = nullptr) { + std::vector Names; + for (int i = Begin; i <= End; i++) + Names.push_back(std::to_string(i)); + return generateSymbols(Names, WeakSymbols); +} + std::vector match(const SymbolIndex &I, const FuzzyFindRequest &Req) { std::vector 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; } @@ -110,6 +129,56 @@ 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 Index: unittests/clangd/SymbolCollectorTests.cpp =================================================================== --- unittests/clangd/SymbolCollectorTests.cpp +++ unittests/clangd/SymbolCollectorTests.cpp @@ -31,7 +31,10 @@ 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 { @@ -111,7 +114,8 @@ const std::string YAML1 = R"( --- ID: 057557CEBF6E6B2DD437FBF60CC58F352D1DF856 -QualifiedName: 'clang::Foo1' +Name: 'Foo1' +Scope: 'clang' SymInfo: Kind: Function Lang: Cpp @@ -124,7 +128,8 @@ const std::string YAML2 = R"( --- ID: 057557CEBF6E6B2DD437FBF60CC58F352D1DF858 -QualifiedName: 'clang::Foo2' +Name: 'Foo2' +Scope: 'clang' SymInfo: Kind: Function Lang: Cpp