Index: clang-tools-extra/clangd/CMakeLists.txt =================================================================== --- clang-tools-extra/clangd/CMakeLists.txt +++ clang-tools-extra/clangd/CMakeLists.txt @@ -43,8 +43,10 @@ index/SymbolCollector.cpp index/SymbolYAML.cpp + index/dex/DexIndex.cpp index/dex/Iterator.cpp index/dex/Trigram.cpp + index/dex/Token.cpp LINK_LIBS clangAST Index: clang-tools-extra/clangd/index/MemIndex.h =================================================================== --- clang-tools-extra/clangd/index/MemIndex.h +++ clang-tools-extra/clangd/index/MemIndex.h @@ -42,7 +42,6 @@ private: std::shared_ptr> Symbols; // Index is a set of symbols that are deduplicated by symbol IDs. - // FIXME: build smarter index structure. llvm::DenseMap Index; mutable std::mutex Mutex; }; Index: clang-tools-extra/clangd/index/dex/DexIndex.h =================================================================== --- /dev/null +++ clang-tools-extra/clangd/index/dex/DexIndex.h @@ -0,0 +1,56 @@ +//===--- DexIndex.h - Dex Symbol Index Implementation -----------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_DEX_DEXINDEX_H +#define LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_DEX_DEXINDEX_H + +#include "../Index.h" +#include "../MemIndex.h" +#include "Iterator.h" +#include "Token.h" +#include "Trigram.h" +#include + +namespace clang { +namespace clangd { +namespace dex { + +/// In-memory Dex trigram-based index implementation. +class DexIndex : public SymbolIndex { +public: + void build(std::shared_ptr> Symbols); + + // FIXME(kbobyrev): This is the same as in MemIndex. Should this be abstracted + // out to Index.h? + static std::unique_ptr build(SymbolSlab Slab); + + bool + fuzzyFind(const FuzzyFindRequest &Req, + llvm::function_ref Callback) const override; + + virtual void + lookup(const LookupRequest &Req, + llvm::function_ref Callback) const override; + + void findOccurrences(const OccurrencesRequest &Req, + llvm::function_ref + Callback) const override; + +private: + std::shared_ptr> Symbols; + llvm::DenseMap Index; + mutable std::mutex Mutex; + llvm::DenseMap InvertedIndex; +}; + +} // namespace dex +} // namespace clangd +} // namespace clang + +#endif Index: clang-tools-extra/clangd/index/dex/DexIndex.cpp =================================================================== --- /dev/null +++ clang-tools-extra/clangd/index/dex/DexIndex.cpp @@ -0,0 +1,181 @@ +//===--- DexIndex.cpp - Dex Symbol Index Implementation ---------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#include "DexIndex.h" +#include "../../FuzzyMatch.h" +#include "../../Logger.h" +#include + +namespace clang { +namespace clangd { +namespace dex { + +void DexIndex::build(std::shared_ptr> Syms) { + llvm::DenseMap TempIndex; + for (const Symbol *Sym : *Syms) + TempIndex[Sym->ID] = Sym; + + { + std::lock_guard Lock(Mutex); + + // Replace outdated index with the new one. + Index = std::move(TempIndex); + Symbols = std::move(Syms); + + // Symbols are sorted by symbol qualities so that items in the posting lists + // are stored in the descending order of symbol quality. + std::sort(begin(*Symbols), end(*Symbols), + [](const Symbol *LHS, const Symbol *RHS) { + return quality(*LHS) > quality(*RHS); + }); + InvertedIndex.clear(); + // Populate InvertedIndex with posting lists for index symbols. + for (DocID SymbolRank = 0; SymbolRank < Symbols->size(); ++SymbolRank) { + const auto Sym = (*Symbols)[SymbolRank]; + for (const auto &Token : generateSearchTokens(*Sym)) { + if (!InvertedIndex.count(Token)) + InvertedIndex[Token] = {SymbolRank}; + else + InvertedIndex[Token].push_back(SymbolRank); + } + } + } +} + +bool DexIndex::fuzzyFind( + const FuzzyFindRequest &Req, + llvm::function_ref Callback) const { + assert(!StringRef(Req.Query).contains("::") && + "There must be no :: in query."); + FuzzyMatcher Filter(Req.Query); + bool More; + { + std::lock_guard Lock(Mutex); + + std::vector SymbolDocIDs; + + // FIXME(kbobyrev): Implement short queries (<3 length) using posting + // lists and incomplete trigrams. Unigram and bigram posting lists are + // likely to be very dense, which is why posting list compression should be + // also implemented in that approach. + // FIXME(kbobyrev): Code sharing is not very pleasant here, is it better to + // dispatch long and short queries to internal helper functions? + if (Req.Query.size() >= 3) { + // Generate query trigrams and construct AND iterator over all query + // trigrams. + const auto TrigramTokens = generateIdentifierTrigrams(Req.Query); + std::vector> TrigramIterators; + for (const auto &Trigram : TrigramTokens) { + const auto It = InvertedIndex.find(Trigram); + if (It != InvertedIndex.end()) + TrigramIterators.push_back(create(It->second)); + } + + std::vector> TopLevelChildren; + TopLevelChildren.push_back(createAnd(move(TrigramIterators))); + + // Generate scope tokens for search query. + std::vector> ScopeIterators; + for (const auto &Scope : Req.Scopes) { + const auto It = InvertedIndex.find(Token(Token::Kind::Scope, Scope)); + if (It != InvertedIndex.end()) + ScopeIterators.push_back(create(It->second)); + } + // Only add OR iterator for scopes if the request contains scopes, + // otherwise the iterator won't have any children and will be invalid. + if (ScopeIterators.size()) + TopLevelChildren.push_back(createOr(move(ScopeIterators))); + + auto QueryIterator = createAnd(move(TopLevelChildren)); + // FIXME(kbobyrev): Limit the total number of consumed symbols using + // Req.MaxCandidateCount. That would require implementing Limit iterator. + SymbolDocIDs = consume(*QueryIterator); + More = SymbolDocIDs.size() > Req.MaxCandidateCount; + } else { + // FIXME(kbobyrev): Don't score items twice. + for (const auto &Pair : Index) { + const auto Sym = Pair.second; + const auto Score = Filter.match(Sym->Name); + // Exact match against all possible scopes. + if (!Req.Scopes.empty() && !llvm::is_contained(Req.Scopes, Sym->Scope)) + continue; + if (Req.RestrictForCodeCompletion && !Sym->IsIndexedForCodeCompletion) + continue; + if (Score.hasValue()) { + // If the requested number of results is already retrieved but there + // are other symbols which match the criteria, just stop processing + // items and let callee know there are more results. + if (SymbolDocIDs.size() == Req.MaxCandidateCount) { + More = true; + break; + } + const auto SymDocID = + std::find(Symbols->begin(), Symbols->end(), Sym) - + Symbols->begin(); + SymbolDocIDs.push_back(SymDocID); + } + } + } + + // FIXME(kbobyrev): Scoring all matched symbols and then processing + // MaxCandidateCount items is rather expensive, this should be replaced by + // two-stage filtering at some point as proposed in Dex design document. + std::vector> Scores(SymbolDocIDs.size()); + for (size_t SymbolIdx = 0; SymbolIdx < SymbolDocIDs.size(); ++SymbolIdx) { + const auto Sym = (*Symbols)[SymbolDocIDs[SymbolIdx]]; + const auto Score = Filter.match(Sym->Name); + assert(Score.hasValue() && "Matched symbol has all Fuzzy Matching " + "trigrams, it should match the query"); + Scores[SymbolIdx] = std::make_pair(-*Score * quality(*Sym), Sym); + } + // Sort retrieved symbol by Fuzzy Matching score. + std::sort(begin(Scores), end(Scores)); + + for (size_t CandidateRank = 0; + CandidateRank < std::min(Req.MaxCandidateCount, Scores.size()); + ++CandidateRank) + Callback(*Scores[CandidateRank].second); + } + return More; +} + +void DexIndex::lookup(const LookupRequest &Req, + llvm::function_ref Callback) const { + for (const auto &ID : Req.IDs) { + auto I = Index.find(ID); + if (I != Index.end()) + Callback(*I->second); + } +} + +std::unique_ptr DexIndex::build(SymbolSlab Slab) { + struct Snapshot { + SymbolSlab Slab; + std::vector Pointers; + }; + auto Snap = std::make_shared(); + Snap->Slab = std::move(Slab); + for (auto &Sym : Snap->Slab) + Snap->Pointers.push_back(&Sym); + auto S = std::shared_ptr>(std::move(Snap), + &Snap->Pointers); + auto DexIdx = llvm::make_unique(); + DexIdx->build(std::move(S)); + return std::move(DexIdx); +} + +void DexIndex::findOccurrences( + const OccurrencesRequest &Req, + llvm::function_ref Callback) const { + log("findOccurrences is not implemented."); +} + +} // namespace dex +} // namespace clangd +} // namespace clang Index: clang-tools-extra/clangd/index/dex/Token.h =================================================================== --- clang-tools-extra/clangd/index/dex/Token.h +++ clang-tools-extra/clangd/index/dex/Token.h @@ -22,9 +22,9 @@ #ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_DEX_TOKEN_H #define LLVM_CLANG_TOOLS_EXTRA_CLANGD_DEX_TOKEN_H +#include "../Index.h" #include "llvm/ADT/DenseMap.h" #include "llvm/Support/raw_ostream.h" - #include #include @@ -81,6 +81,8 @@ } }; +std::vector generateSearchTokens(const Symbol &Sym); + } // namespace dex } // namespace clangd } // namespace clang Index: clang-tools-extra/clangd/index/dex/Token.cpp =================================================================== --- /dev/null +++ clang-tools-extra/clangd/index/dex/Token.cpp @@ -0,0 +1,25 @@ +//===--- Token.cpp - Symbol Search primitive --------------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#include "Token.h" +#include "Trigram.h" + +namespace clang { +namespace clangd { +namespace dex { + +std::vector generateSearchTokens(const Symbol &Sym) { + std::vector Result = generateIdentifierTrigrams(Sym.Name); + Result.push_back(Token(Token::Kind::Scope, Sym.Scope)); + return Result; +} + +} // namespace dex +} // namespace clangd +} // namespace clang Index: clang-tools-extra/unittests/clangd/CMakeLists.txt =================================================================== --- clang-tools-extra/unittests/clangd/CMakeLists.txt +++ clang-tools-extra/unittests/clangd/CMakeLists.txt @@ -30,6 +30,7 @@ SyncAPI.cpp TUSchedulerTests.cpp TestFS.cpp + TestIndexOperations.cpp TestTU.cpp ThreadingTests.cpp TraceTests.cpp Index: clang-tools-extra/unittests/clangd/DexIndexTests.cpp =================================================================== --- clang-tools-extra/unittests/clangd/DexIndexTests.cpp +++ clang-tools-extra/unittests/clangd/DexIndexTests.cpp @@ -7,6 +7,10 @@ // //===----------------------------------------------------------------------===// +#include "IndexHelpers.h" +#include "index/Index.h" +#include "index/Merge.h" +#include "index/dex/DexIndex.h" #include "index/dex/Iterator.h" #include "index/dex/Token.h" #include "index/dex/Trigram.h" @@ -17,11 +21,13 @@ #include #include +using ::testing::ElementsAre; +using ::testing::UnorderedElementsAre; + namespace clang { namespace clangd { namespace dex { - -using ::testing::ElementsAre; +namespace { TEST(DexIndexIterators, DocumentIterator) { const PostingList L = {4, 7, 8, 20, 42, 100}; @@ -312,6 +318,218 @@ "hij", "ijk", "jkl", "klm"})); } +TEST(DexIndex, Lookup) { + DexIndex I; + I.build(generateSymbols({"ns::abc", "ns::xyz"})); + EXPECT_THAT(lookup(I, SymbolID("ns::abc")), UnorderedElementsAre("ns::abc")); + EXPECT_THAT(lookup(I, {SymbolID("ns::abc"), SymbolID("ns::xyz")}), + UnorderedElementsAre("ns::abc", "ns::xyz")); + EXPECT_THAT(lookup(I, {SymbolID("ns::nonono"), SymbolID("ns::xyz")}), + UnorderedElementsAre("ns::xyz")); + EXPECT_THAT(lookup(I, SymbolID("ns::nonono")), UnorderedElementsAre()); +} + +// FIXME(kbobyrev): Use 3+ symbols long names so that trigram index is used. +TEST(MergeDexIndex, Lookup) { + DexIndex I, J; + I.build(generateSymbols({"ns::A", "ns::B"})); + J.build(generateSymbols({"ns::B", "ns::C"})); + EXPECT_THAT(lookup(*mergeIndex(&I, &J), SymbolID("ns::A")), + UnorderedElementsAre("ns::A")); + EXPECT_THAT(lookup(*mergeIndex(&I, &J), SymbolID("ns::B")), + UnorderedElementsAre("ns::B")); + EXPECT_THAT(lookup(*mergeIndex(&I, &J), SymbolID("ns::C")), + UnorderedElementsAre("ns::C")); + EXPECT_THAT( + lookup(*mergeIndex(&I, &J), {SymbolID("ns::A"), SymbolID("ns::B")}), + UnorderedElementsAre("ns::A", "ns::B")); + EXPECT_THAT( + lookup(*mergeIndex(&I, &J), {SymbolID("ns::A"), SymbolID("ns::C")}), + UnorderedElementsAre("ns::A", "ns::C")); + EXPECT_THAT(lookup(*mergeIndex(&I, &J), SymbolID("ns::D")), + UnorderedElementsAre()); + EXPECT_THAT(lookup(*mergeIndex(&I, &J), {}), UnorderedElementsAre()); +} + +// FIXME(kbobyrev): Add more tests on DexIndex? Right now, it's mostly a wrapper +// around DexIndex, adopting tests from IndexTests.cpp sounds reasonable. +// However, most of these tests use short names (<3 symbols) for symbol lookups, +// which currently are dispatched to DexIndex and hence just duplicating these +// tests while substituting DexIndex with DexIndex is not a viable solution. +TEST(DexIndex, FuzzyFindQ) { + DexIndex Index; + Index.build(generateSymbols( + {"ns::ABC", "ns::BCD", "::ABC", "ns::nested::ABC", "other::ABC"})); + FuzzyFindRequest Req; + Req.Query = "ABC"; + Req.Scopes = {"ns::"}; + EXPECT_THAT(match(Index, Req), UnorderedElementsAre("ns::ABC")); + Req.Scopes = {"ns::", "ns::nested::"}; + EXPECT_THAT(match(Index, Req), + UnorderedElementsAre("ns::ABC", "ns::nested::ABC")); +} + +TEST(DexIndexTest, FuzzyMatchQ) { + DexIndex I; + I.build( + generateSymbols({"LaughingOutLoud", "LionPopulation", "LittleOldLady"})); + FuzzyFindRequest Req; + Req.Query = "lol"; + Req.MaxCandidateCount = 2; + EXPECT_THAT(match(I, Req), + UnorderedElementsAre("LaughingOutLoud", "LittleOldLady")); +} + +TEST(DexIndexTest, DexIndexSymbolsRecycled) { + DexIndex I; + std::weak_ptr Symbols; + I.build(generateNumSymbols(0, 10, &Symbols)); + FuzzyFindRequest Req; + Req.Query = "7"; + EXPECT_THAT(match(I, Req), UnorderedElementsAre("7")); + + EXPECT_FALSE(Symbols.expired()); + // Release old symbols. + I.build(generateNumSymbols(0, 0)); + EXPECT_TRUE(Symbols.expired()); +} + +TEST(DexIndexTest, DexIndexDeduplicate) { + auto Symbols = generateNumSymbols(0, 10); + + // Inject some duplicates and make sure we only match the same symbol once. + auto Sym = symbol("7"); + Symbols->push_back(&Sym); + Symbols->push_back(&Sym); + Symbols->push_back(&Sym); + + FuzzyFindRequest Req; + Req.Query = "7"; + DexIndex I; + I.build(std::move(Symbols)); + auto Matches = match(I, Req); + EXPECT_EQ(Matches.size(), 1u); +} + +TEST(DexIndexTest, DexIndexLimitedNumMatches) { + DexIndex I; + I.build(generateNumSymbols(0, 100)); + FuzzyFindRequest Req; + Req.Query = "5"; + Req.MaxCandidateCount = 3; + bool Incomplete; + auto Matches = match(I, Req, &Incomplete); + EXPECT_EQ(Matches.size(), Req.MaxCandidateCount); + EXPECT_TRUE(Incomplete); +} + +TEST(DexIndexTest, FuzzyMatch) { + DexIndex I; + I.build( + generateSymbols({"LaughingOutLoud", "LionPopulation", "LittleOldLady"})); + FuzzyFindRequest Req; + Req.Query = "lol"; + Req.MaxCandidateCount = 2; + EXPECT_THAT(match(I, Req), + UnorderedElementsAre("LaughingOutLoud", "LittleOldLady")); +} + +TEST(DexIndexTest, MatchQualifiedNamesWithoutSpecificScope) { + DexIndex I; + I.build(generateSymbols({"a::y1", "b::y2", "y3"})); + FuzzyFindRequest Req; + Req.Query = "y"; + EXPECT_THAT(match(I, Req), UnorderedElementsAre("a::y1", "b::y2", "y3")); +} + +TEST(DexIndexTest, MatchQualifiedNamesWithGlobalScope) { + DexIndex I; + I.build(generateSymbols({"a::y1", "b::y2", "y3"})); + FuzzyFindRequest Req; + Req.Query = "y"; + Req.Scopes = {""}; + EXPECT_THAT(match(I, Req), UnorderedElementsAre("y3")); +} + +TEST(DexIndexTest, MatchQualifiedNamesWithOneScope) { + DexIndex I; + I.build(generateSymbols({"a::y1", "a::y2", "a::x", "b::y2", "y3"})); + FuzzyFindRequest Req; + Req.Query = "y"; + Req.Scopes = {"a::"}; + EXPECT_THAT(match(I, Req), UnorderedElementsAre("a::y1", "a::y2")); +} + +TEST(DexIndexTest, MatchQualifiedNamesWithMultipleScopes) { + DexIndex I; + I.build(generateSymbols({"a::y1", "a::y2", "a::x", "b::y3", "y3"})); + FuzzyFindRequest Req; + Req.Query = "y"; + Req.Scopes = {"a::", "b::"}; + EXPECT_THAT(match(I, Req), UnorderedElementsAre("a::y1", "a::y2", "b::y3")); +} + +TEST(DexIndexTest, NoMatchNestedScopes) { + DexIndex I; + I.build(generateSymbols({"a::y1", "a::b::y2"})); + FuzzyFindRequest Req; + Req.Query = "y"; + Req.Scopes = {"a::"}; + EXPECT_THAT(match(I, Req), UnorderedElementsAre("a::y1")); +} + +TEST(DexIndexTest, IgnoreCases) { + DexIndex I; + I.build(generateSymbols({"ns::ABC", "ns::abc"})); + FuzzyFindRequest Req; + Req.Query = "AB"; + Req.Scopes = {"ns::"}; + EXPECT_THAT(match(I, Req), UnorderedElementsAre("ns::ABC", "ns::abc")); +} + +TEST(DexIndexTest, Lookup) { + DexIndex I; + I.build(generateSymbols({"ns::abc", "ns::xyz"})); + EXPECT_THAT(lookup(I, SymbolID("ns::abc")), UnorderedElementsAre("ns::abc")); + EXPECT_THAT(lookup(I, {SymbolID("ns::abc"), SymbolID("ns::xyz")}), + UnorderedElementsAre("ns::abc", "ns::xyz")); + EXPECT_THAT(lookup(I, {SymbolID("ns::nonono"), SymbolID("ns::xyz")}), + UnorderedElementsAre("ns::xyz")); + EXPECT_THAT(lookup(I, SymbolID("ns::nonono")), UnorderedElementsAre()); +} + +TEST(DexMergeIndexTest, Lookup) { + DexIndex I, J; + I.build(generateSymbols({"ns::A", "ns::B"})); + J.build(generateSymbols({"ns::B", "ns::C"})); + EXPECT_THAT(lookup(*mergeIndex(&I, &J), SymbolID("ns::A")), + UnorderedElementsAre("ns::A")); + EXPECT_THAT(lookup(*mergeIndex(&I, &J), SymbolID("ns::B")), + UnorderedElementsAre("ns::B")); + EXPECT_THAT(lookup(*mergeIndex(&I, &J), SymbolID("ns::C")), + UnorderedElementsAre("ns::C")); + EXPECT_THAT( + lookup(*mergeIndex(&I, &J), {SymbolID("ns::A"), SymbolID("ns::B")}), + UnorderedElementsAre("ns::A", "ns::B")); + EXPECT_THAT( + lookup(*mergeIndex(&I, &J), {SymbolID("ns::A"), SymbolID("ns::C")}), + UnorderedElementsAre("ns::A", "ns::C")); + EXPECT_THAT(lookup(*mergeIndex(&I, &J), SymbolID("ns::D")), + UnorderedElementsAre()); + EXPECT_THAT(lookup(*mergeIndex(&I, &J), {}), UnorderedElementsAre()); +} + +TEST(DexMergeIndexTest, FuzzyFind) { + DexIndex I, J; + I.build(generateSymbols({"ns::A", "ns::B"})); + J.build(generateSymbols({"ns::B", "ns::C"})); + FuzzyFindRequest Req; + Req.Scopes = {"ns::"}; + EXPECT_THAT(match(*mergeIndex(&I, &J), Req), + UnorderedElementsAre("ns::A", "ns::B", "ns::C")); +} + +} // namespace } // namespace dex } // namespace clangd } // namespace clang Index: clang-tools-extra/unittests/clangd/IndexTests.cpp =================================================================== --- clang-tools-extra/unittests/clangd/IndexTests.cpp +++ clang-tools-extra/unittests/clangd/IndexTests.cpp @@ -7,33 +7,20 @@ // //===----------------------------------------------------------------------===// +#include "IndexHelpers.h" #include "index/Index.h" #include "index/MemIndex.h" #include "index/Merge.h" #include "gmock/gmock.h" #include "gtest/gtest.h" -using testing::UnorderedElementsAre; using testing::Pointee; +using testing::UnorderedElementsAre; namespace clang { namespace clangd { namespace { -Symbol symbol(llvm::StringRef QName) { - Symbol Sym; - 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 + 2); - } - return Sym; -} - MATCHER_P(Named, N, "") { return arg.Name == N; } TEST(SymbolSlab, FindAndIterate) { @@ -52,59 +39,6 @@ EXPECT_THAT(*S.find(SymbolID(Sym)), Named(Sym)); } -struct SlabAndPointers { - SymbolSlab Slab; - std::vector Pointers; -}; - -// 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> -generateSymbols(std::vector QualifiedNames, - std::weak_ptr *WeakSymbols = nullptr) { - SymbolSlab::Builder Slab; - for (llvm::StringRef QName : QualifiedNames) - Slab.insert(symbol(QName)); - - auto Storage = std::make_shared(); - Storage->Slab = std::move(Slab).build(); - for (const auto &Sym : Storage->Slab) - Storage->Pointers.push_back(&Sym); - if (WeakSymbols) - *WeakSymbols = Storage; - auto *Pointers = &Storage->Pointers; - return {std::move(Storage), 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::string getQualifiedName(const Symbol &Sym) { - return (Sym.Scope + Sym.Name).str(); -} - -std::vector match(const SymbolIndex &I, - const FuzzyFindRequest &Req, - bool *Incomplete = nullptr) { - std::vector Matches; - bool IsIncomplete = I.fuzzyFind(Req, [&](const Symbol &Sym) { - Matches.push_back(getQualifiedName(Sym)); - }); - if (Incomplete) - *Incomplete = IsIncomplete; - return Matches; -} - TEST(MemIndexTest, MemIndexSymbolsRecycled) { MemIndex I; std::weak_ptr Symbols; @@ -212,18 +146,6 @@ EXPECT_THAT(match(I, Req), UnorderedElementsAre("ns::ABC", "ns::abc")); } -// Returns qualified names of symbols with any of IDs in the index. -std::vector lookup(const SymbolIndex &I, - llvm::ArrayRef IDs) { - LookupRequest Req; - Req.IDs.insert(IDs.begin(), IDs.end()); - std::vector Results; - I.lookup(Req, [&](const Symbol &Sym) { - Results.push_back(getQualifiedName(Sym)); - }); - return Results; -} - TEST(MemIndexTest, Lookup) { MemIndex I; I.build(generateSymbols({"ns::abc", "ns::xyz"})); @@ -269,7 +191,7 @@ TEST(MergeTest, Merge) { Symbol L, R; L.ID = R.ID = SymbolID("hello"); - L.Name = R.Name = "Foo"; // same in both + L.Name = R.Name = "Foo"; // same in both L.CanonicalDeclaration.FileURI = "file:///left.h"; // differs R.CanonicalDeclaration.FileURI = "file:///right.h"; L.References = 1; Index: clang-tools-extra/unittests/clangd/TestIndexOperations.h =================================================================== --- /dev/null +++ clang-tools-extra/unittests/clangd/TestIndexOperations.h @@ -0,0 +1,57 @@ +//===-- IndexHelpers.h ------------------------------------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_TOOLS_EXTRA_UNITTESTS_CLANGD_INDEXTESTCOMMON_H +#define LLVM_CLANG_TOOLS_EXTRA_UNITTESTS_CLANGD_INDEXTESTCOMMON_H + +#include "index/Index.h" +#include "index/Merge.h" +#include "index/dex/DexIndex.h" +#include "index/dex/Iterator.h" +#include "index/dex/Token.h" +#include "index/dex/Trigram.h" + +namespace clang { +namespace clangd { + +Symbol symbol(llvm::StringRef QName); + +struct SlabAndPointers { + SymbolSlab Slab; + std::vector Pointers; +}; + +// 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> +generateSymbols(std::vector QualifiedNames, + std::weak_ptr *WeakSymbols = nullptr); + +// 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::string getQualifiedName(const Symbol &Sym); + +std::vector match(const SymbolIndex &I, + const FuzzyFindRequest &Req, + bool *Incomplete = nullptr); + +// Returns qualified names of symbols with any of IDs in the index. +std::vector lookup(const SymbolIndex &I, + llvm::ArrayRef IDs); + +} // namespace clangd +} // namespace clang + +#endif Index: clang-tools-extra/unittests/clangd/TestIndexOperations.cpp =================================================================== --- /dev/null +++ clang-tools-extra/unittests/clangd/TestIndexOperations.cpp @@ -0,0 +1,89 @@ +//===-- IndexHelpers.cpp ----------------------------------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#include "IndexHelpers.h" + +namespace clang { +namespace clangd { + +Symbol symbol(llvm::StringRef QName) { + Symbol Sym; + 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 + 2); + } + return Sym; +} + +// 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> +generateSymbols(std::vector QualifiedNames, + std::weak_ptr *WeakSymbols) { + SymbolSlab::Builder Slab; + for (llvm::StringRef QName : QualifiedNames) + Slab.insert(symbol(QName)); + + auto Storage = std::make_shared(); + Storage->Slab = std::move(Slab).build(); + for (const auto &Sym : Storage->Slab) + Storage->Pointers.push_back(&Sym); + if (WeakSymbols) + *WeakSymbols = Storage; + auto *Pointers = &Storage->Pointers; + return {std::move(Storage), 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) { + std::vector Names; + for (int i = Begin; i <= End; i++) + Names.push_back(std::to_string(i)); + return generateSymbols(Names, WeakSymbols); +} + +std::string getQualifiedName(const Symbol &Sym) { + return (Sym.Scope + Sym.Name).str(); +} + +std::vector match(const SymbolIndex &I, + const FuzzyFindRequest &Req, bool *Incomplete) { + std::vector Matches; + bool IsIncomplete = I.fuzzyFind(Req, [&](const Symbol &Sym) { + Matches.push_back(clang::clangd::getQualifiedName(Sym)); + }); + if (Incomplete) + *Incomplete = IsIncomplete; + return Matches; +} + +// Returns qualified names of symbols with any of IDs in the index. +std::vector lookup(const SymbolIndex &I, + llvm::ArrayRef IDs) { + LookupRequest Req; + Req.IDs.insert(IDs.begin(), IDs.end()); + std::vector Results; + I.lookup(Req, [&](const Symbol &Sym) { + Results.push_back(getQualifiedName(Sym)); + }); + return Results; +} + +} // namespace clangd +} // namespace clang