Index: clangd/index/FileIndex.h =================================================================== --- clangd/index/FileIndex.h +++ clangd/index/FileIndex.h @@ -24,7 +24,7 @@ namespace clang { namespace clangd { -/// \brief A container of Symbols from several source files. It can be updated +/// A container of Symbols from several source files. It can be updated /// at source-file granularity, replacing all symbols from one file with a new /// set. /// @@ -39,35 +39,31 @@ /// locking when we swap or obtain references to snapshots. class FileSymbols { public: - /// \brief Updates all symbols and occurrences in a file. - /// If \p Slab (Occurrence) is nullptr, symbols (occurrences) for \p Path - /// will be removed. + /// Updates all symbols and occurrences in a file. + /// If either is nullptr, corresponding data for \p Path will be removed. void update(PathRef Path, std::unique_ptr Slab, std::unique_ptr Occurrences); - // The shared_ptr keeps the symbols alive - std::shared_ptr> allSymbols(); - - /// Returns all symbol occurrences for all active files. - std::shared_ptr allOccurrences() const; + // The index keeps the symbols alive. + std::unique_ptr buildMemIndex(); private: mutable std::mutex Mutex; - /// \brief Stores the latest snapshots for all active files. + /// Stores the latest snapshots for all active files. llvm::StringMap> FileToSlabs; /// Stores the latest occurrence slabs for all active files. llvm::StringMap> FileToOccurrenceSlabs; }; -/// \brief This manages symbols from files and an in-memory index on all symbols. -class FileIndex : public SymbolIndex { +/// This manages symbols from files and an in-memory index on all symbols. +class FileIndex : public SwapIndex { public: /// If URISchemes is empty, the default schemes in SymbolCollector will be /// used. FileIndex(std::vector URISchemes = {}); - /// \brief Update symbols in \p Path with symbols in \p AST. If \p AST is + /// Update symbols in \p Path with symbols in \p AST. If \p AST is /// nullptr, this removes all symbols in the file. /// If \p AST is not null, \p PP cannot be null and it should be the /// preprocessor that was used to build \p AST. @@ -77,23 +73,11 @@ update(PathRef Path, ASTContext *AST, std::shared_ptr PP, llvm::Optional> TopLevelDecls = llvm::None); - bool - fuzzyFind(const FuzzyFindRequest &Req, - llvm::function_ref Callback) const override; - - void lookup(const LookupRequest &Req, - llvm::function_ref Callback) const override; - - - void findOccurrences(const OccurrencesRequest &Req, - llvm::function_ref - Callback) const override; - - size_t estimateMemoryUsage() const override; - private: + // Only update() should swap the index. + using SwapIndex::reset; + FileSymbols FSymbols; - MemIndex Index; std::vector URISchemes; }; Index: clangd/index/FileIndex.cpp =================================================================== --- clangd/index/FileIndex.cpp +++ clangd/index/FileIndex.cpp @@ -71,7 +71,9 @@ } FileIndex::FileIndex(std::vector URISchemes) - : URISchemes(std::move(URISchemes)) {} + : URISchemes(std::move(URISchemes)) { + reset(FSymbols.buildMemIndex()); +} void FileSymbols::update(PathRef Path, std::unique_ptr Slab, std::unique_ptr Occurrences) { @@ -86,52 +88,32 @@ FileToOccurrenceSlabs[Path] = std::move(Occurrences); } -std::shared_ptr> FileSymbols::allSymbols() { - // The snapshot manages life time of symbol slabs and provides pointers of all - // symbols in all slabs. - struct Snapshot { - std::vector Pointers; - std::vector> KeepAlive; - }; - auto Snap = std::make_shared(); +std::unique_ptr FileSymbols::buildMemIndex() { + std::vector> Slabs; + std::vector> OccurrenceSlabs; { std::lock_guard Lock(Mutex); - - for (const auto &FileAndSlab : FileToSlabs) { - Snap->KeepAlive.push_back(FileAndSlab.second); - for (const auto &Iter : *FileAndSlab.second) - Snap->Pointers.push_back(&Iter); - } + for (const auto &FileAndSlab : FileToSlabs) + Slabs.push_back(FileAndSlab.second); + for (const auto &FileAndOccurrenceSlab : FileToOccurrenceSlabs) + OccurrenceSlabs.push_back(FileAndOccurrenceSlab.second); } - auto *Pointers = &Snap->Pointers; - // Use aliasing constructor to keep the snapshot alive along with the - // pointers. - return {std::move(Snap), Pointers}; -} - -std::shared_ptr FileSymbols::allOccurrences() const { - // The snapshot manages life time of symbol occurrence slabs and provides - // pointers to all occurrences in all occurrence slabs. - struct Snapshot { - MemIndex::OccurrenceMap Occurrences; // ID => {Occurrence} - std::vector> KeepAlive; - }; - - auto Snap = std::make_shared(); - { - std::lock_guard Lock(Mutex); - - for (const auto &FileAndSlab : FileToOccurrenceSlabs) { - Snap->KeepAlive.push_back(FileAndSlab.second); - for (const auto &IDAndOccurrences : *FileAndSlab.second) { - auto &Occurrences = Snap->Occurrences[IDAndOccurrences.first]; - for (const auto &Occurrence : IDAndOccurrences.second) - Occurrences.push_back(&Occurrence); - } + std::vector AllSymbols; + for (const auto &Slab : Slabs) + for (const auto &Sym : *Slab) + AllSymbols.push_back(&Sym); + MemIndex::OccurrenceMap AllOccurrences; + for (const auto &OccurrenceSlab : OccurrenceSlabs) + for (const auto &Sym : *OccurrenceSlab) { + auto &Entry = AllOccurrences[Sym.first]; + for (const auto &Occ : Sym.second) + Entry.push_back(&Occ); } - } - return {std::move(Snap), &Snap->Occurrences}; + // Index must keep the slabs alive. + return llvm::make_unique( + llvm::make_pointee_range(AllSymbols), std::move(AllOccurrences), + std::make_pair(std::move(Slabs), std::move(OccurrenceSlabs))); } void FileIndex::update(PathRef Path, ASTContext *AST, @@ -148,30 +130,7 @@ indexAST(*AST, PP, TopLevelDecls, URISchemes); FSymbols.update(Path, std::move(Slab), std::move(OccurrenceSlab)); } - auto Symbols = FSymbols.allSymbols(); - Index.build(std::move(Symbols), FSymbols.allOccurrences()); -} - -bool FileIndex::fuzzyFind( - const FuzzyFindRequest &Req, - llvm::function_ref Callback) const { - return Index.fuzzyFind(Req, Callback); -} - -void FileIndex::lookup( - const LookupRequest &Req, - llvm::function_ref Callback) const { - Index.lookup(Req, Callback); -} - -void FileIndex::findOccurrences( - const OccurrencesRequest &Req, - llvm::function_ref Callback) const { - Index.findOccurrences(Req, Callback); -} - -size_t FileIndex::estimateMemoryUsage() const { - return Index.estimateMemoryUsage(); + reset(FSymbols.buildMemIndex()); } } // namespace clangd Index: clangd/index/Index.h =================================================================== --- clangd/index/Index.h +++ clangd/index/Index.h @@ -12,6 +12,7 @@ #include "clang/Index/IndexSymbol.h" #include "clang/Lex/Lexer.h" +#include "llvm/ADT/Any.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/DenseSet.h" #include "llvm/ADT/Hashing.h" @@ -21,6 +22,7 @@ #include "llvm/ADT/StringRef.h" #include "llvm/Support/StringSaver.h" #include +#include #include #include @@ -331,6 +333,7 @@ return static_cast(static_cast(A) & static_cast(B)); } +llvm::raw_ostream &operator<<(llvm::raw_ostream &, SymbolOccurrenceKind); static const SymbolOccurrenceKind AllOccurrenceKinds = SymbolOccurrenceKind::Declaration | SymbolOccurrenceKind::Definition | SymbolOccurrenceKind::Reference; @@ -447,10 +450,10 @@ struct OccurrencesRequest { llvm::DenseSet IDs; - SymbolOccurrenceKind Filter; + SymbolOccurrenceKind Filter = AllOccurrenceKinds; }; -/// \brief Interface for symbol indexes that can be used for searching or +/// 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: @@ -489,6 +492,31 @@ virtual size_t estimateMemoryUsage() const = 0; }; +// Delegating implementation of SymbolIndex whose delegate can be swapped out. +class SwapIndex : public SymbolIndex { +public: + // If an index is not provided, reset() must be called. + SwapIndex(std::unique_ptr Index = nullptr) + : Index(std::move(Index)) {} + void reset(std::unique_ptr); + + // SymbolIndex methods delegate to the current index, which is kept alive + // until the call returns (even if reset() is called). + bool fuzzyFind(const FuzzyFindRequest &, + llvm::function_ref) const override; + void lookup(const LookupRequest &, + llvm::function_ref) const override; + void findOccurrences( + const OccurrencesRequest &, + llvm::function_ref) const override; + size_t estimateMemoryUsage() const override; + +private: + std::shared_ptr snapshot() const; + mutable std::mutex Mutex; + std::shared_ptr Index; +}; + } // namespace clangd } // namespace clang Index: clangd/index/Index.cpp =================================================================== --- clangd/index/Index.cpp +++ clangd/index/Index.cpp @@ -165,5 +165,36 @@ Frozen = true; } +void SwapIndex::reset(std::unique_ptr Index) { + // Keep the old index alive, so we don't destroy it under lock (may be slow). + std::shared_ptr Pin; + { + std::lock_guard Lock(Mutex); + Pin = std::move(this->Index); + this->Index = std::move(Index); + } +} +std::shared_ptr SwapIndex::snapshot() const { + std::lock_guard Lock(Mutex); + return Index; +} + +bool SwapIndex::fuzzyFind(const FuzzyFindRequest &R, + llvm::function_ref CB) const { + return snapshot()->fuzzyFind(R, CB); +} +void SwapIndex::lookup(const LookupRequest &R, + llvm::function_ref CB) const { + return snapshot()->lookup(R, CB); +} +void SwapIndex::findOccurrences( + const OccurrencesRequest &R, + llvm::function_ref CB) const { + return snapshot()->findOccurrences(R, CB); +} +size_t SwapIndex::estimateMemoryUsage() const { + return snapshot()->estimateMemoryUsage(); +} + } // namespace clangd } // namespace clang Index: clangd/index/MemIndex.h =================================================================== --- clangd/index/MemIndex.h +++ clangd/index/MemIndex.h @@ -16,8 +16,7 @@ namespace clang { namespace clangd { -/// \brief This implements an index for a (relatively small) set of symbols (or -/// symbol occurrences) that can be easily managed in memory. +/// MemIndex is a naive in-memory index suitable for a small set of symbols. class MemIndex : public SymbolIndex { public: /// Maps from a symbol ID to all corresponding symbol occurrences. @@ -25,23 +24,33 @@ using OccurrenceMap = llvm::DenseMap>; - /// \brief (Re-)Build index for `Symbols` and update `Occurrences`. - /// All symbol pointers and symbol occurrence pointers must remain accessible - /// as long as `Symbols` and `Occurrences` are kept alive. - void build(std::shared_ptr> Symbols, - std::shared_ptr Occurrences); + MemIndex() = default; + // All symbols and occurrences must outlive this index. + // TODO: find a better type for Occurrences here. + template + MemIndex(SymbolRange &&Symbols, OccurrenceMap Occurrences) + : Occurrences(std::move(Occurrences)) { + for (const Symbol &S : Symbols) + Index[S.ID] = &S; + } + // Symbols are owned by BackingData, Index takes ownership. + template + MemIndex(Range &&Symbols, OccurrenceMap Occurrences, Payload &&BackingData) + : MemIndex(std::forward(Symbols), std::move(Occurrences)) { + KeepAlive = std::shared_ptr( + std::make_shared(std::move(BackingData)), nullptr); + } - /// \brief Build index from a symbol slab and a symbol occurrence slab. - static std::unique_ptr build(SymbolSlab Symbols, + /// Builds an index from a slab. The index takes ownership of the data. + static std::unique_ptr build(SymbolSlab Slab, SymbolOccurrenceSlab Occurrences); bool fuzzyFind(const FuzzyFindRequest &Req, llvm::function_ref Callback) const override; - void - lookup(const LookupRequest &Req, - llvm::function_ref Callback) const override; + void lookup(const LookupRequest &Req, + llvm::function_ref Callback) const override; void findOccurrences(const OccurrencesRequest &Req, llvm::function_ref @@ -50,21 +59,13 @@ size_t estimateMemoryUsage() const override; 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; // A map from symbol ID to symbol occurrences, support query by IDs. - std::shared_ptr Occurrences; - mutable std::mutex Mutex; + OccurrenceMap Occurrences; + std::shared_ptr KeepAlive; // poor man's move-only std::any }; -// Returns pointers to the symbols in given slab and bundles slab lifetime with -// returned symbol pointers so that the pointers are never invalid. -std::shared_ptr> -getSymbolsFromSlab(SymbolSlab Slab); - } // namespace clangd } // namespace clang Index: clangd/index/MemIndex.cpp =================================================================== --- clangd/index/MemIndex.cpp +++ clangd/index/MemIndex.cpp @@ -15,49 +15,16 @@ namespace clang { namespace clangd { -static std::shared_ptr -getOccurrencesFromSlab(SymbolOccurrenceSlab OccurrencesSlab) { - struct Snapshot { - SymbolOccurrenceSlab Slab; - MemIndex::OccurrenceMap Occurrences; - }; - - auto Snap = std::make_shared(); - Snap->Slab = std::move(OccurrencesSlab); - for (const auto &IDAndOccurrences : Snap->Slab) { - auto &Occurrences = Snap->Occurrences[IDAndOccurrences.first]; - for (const auto &Occurrence : IDAndOccurrences.second) - Occurrences.push_back(&Occurrence); - } - return {std::move(Snap), &Snap->Occurrences}; -} - -void MemIndex::build(std::shared_ptr> Syms, - std::shared_ptr AllOccurrences) { - assert(Syms && "Syms must be set when build MemIndex"); - assert(AllOccurrences && "Occurrences must be set when build MemIndex"); - llvm::DenseMap TempIndex; - for (const Symbol *Sym : *Syms) - TempIndex[Sym->ID] = Sym; - - // Swap out the old symbols and index. - { - std::lock_guard Lock(Mutex); - Index = std::move(TempIndex); - Symbols = std::move(Syms); // Release old symbols. - Occurrences = std::move(AllOccurrences); - } - - vlog("Built MemIndex with estimated memory usage {0} bytes.", - estimateMemoryUsage()); -} - -std::unique_ptr MemIndex::build(SymbolSlab Symbols, +std::unique_ptr MemIndex::build(SymbolSlab Slab, SymbolOccurrenceSlab Occurrences) { - auto Idx = llvm::make_unique(); - Idx->build(getSymbolsFromSlab(std::move(Symbols)), - getOccurrencesFromSlab(std::move(Occurrences))); - return std::move(Idx); + OccurrenceMap M; + for (const auto &SymbolAndOccurrences : Occurrences) { + auto &Entry = M[SymbolAndOccurrences.first]; + for (const auto &Occurrence : SymbolAndOccurrences.second) + Entry.push_back(&Occurrence); + } + auto Data = std::make_pair(std::move(Slab), std::move(Occurrences)); + return llvm::make_unique(Data.first, std::move(M), std::move(Data)); } bool MemIndex::fuzzyFind( @@ -69,34 +36,30 @@ std::priority_queue> Top; FuzzyMatcher Filter(Req.Query); bool More = false; - { - std::lock_guard Lock(Mutex); - for (const auto Pair : Index) { - const Symbol *Sym = Pair.second; + for (const auto Pair : Index) { + const Symbol *Sym = Pair.second; - // Exact match against all possible scopes. - if (!Req.Scopes.empty() && !llvm::is_contained(Req.Scopes, Sym->Scope)) - continue; - if (Req.RestrictForCodeCompletion && !Sym->IsIndexedForCodeCompletion) - continue; + // 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 (auto Score = Filter.match(Sym->Name)) { - Top.emplace(-*Score * quality(*Sym), Sym); - if (Top.size() > Req.MaxCandidateCount) { - More = true; - Top.pop(); - } + if (auto Score = Filter.match(Sym->Name)) { + Top.emplace(-*Score * quality(*Sym), Sym); + if (Top.size() > Req.MaxCandidateCount) { + More = true; + Top.pop(); } } - for (; !Top.empty(); Top.pop()) - Callback(*Top.top().second); } + for (; !Top.empty(); Top.pop()) + Callback(*Top.top().second); return More; } void MemIndex::lookup(const LookupRequest &Req, llvm::function_ref Callback) const { - std::lock_guard Lock(Mutex); for (const auto &ID : Req.IDs) { auto I = Index.find(ID); if (I != Index.end()) @@ -107,10 +70,9 @@ void MemIndex::findOccurrences( const OccurrencesRequest &Req, llvm::function_ref Callback) const { - std::lock_guard Lock(Mutex); for (const auto &ReqID : Req.IDs) { - auto FoundOccurrences = Occurrences->find(ReqID); - if (FoundOccurrences == Occurrences->end()) + auto FoundOccurrences = Occurrences.find(ReqID); + if (FoundOccurrences == Occurrences.end()) continue; for (const auto *O : FoundOccurrences->second) { if (static_cast(Req.Filter & O->Kind)) @@ -119,22 +81,7 @@ } } -std::shared_ptr> -getSymbolsFromSlab(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); - return std::shared_ptr>(std::move(Snap), - &Snap->Pointers); -} - size_t MemIndex::estimateMemoryUsage() const { - std::lock_guard Lock(Mutex); return Index.getMemorySize(); } Index: clangd/index/dex/DexIndex.h =================================================================== --- clangd/index/dex/DexIndex.h +++ clangd/index/dex/DexIndex.h @@ -25,7 +25,6 @@ #include "Iterator.h" #include "Token.h" #include "Trigram.h" -#include namespace clang { namespace clangd { @@ -39,12 +38,24 @@ // index on disk and then load it if available. class DexIndex : public SymbolIndex { public: - /// \brief (Re-)Build index for `Symbols`. All symbol pointers must remain - /// accessible as long as `Symbols` is kept alive. - void build(std::shared_ptr> Syms); + // All symbols must outlive this index. + template DexIndex(Range &&Symbols) { + for (auto &&Sym : Symbols) + this->Symbols.push_back(&Sym); + buildIndex(); + } + // Symbols are owned by BackingData, Index takes ownership. + template + DexIndex(Range &&Symbols, Payload &&BackingData) + : DexIndex(std::forward(Symbols)) { + KeepAlive = std::shared_ptr( + std::make_shared(std::move(BackingData)), nullptr); + } - /// \brief Build index from a symbol slab. - static std::unique_ptr build(SymbolSlab Slab); + /// Builds an index from a slab. The index takes ownership of the slab. + static std::unique_ptr build(SymbolSlab Slab) { + return llvm::make_unique(Slab, std::move(Slab)); + } bool fuzzyFind(const FuzzyFindRequest &Req, @@ -60,19 +71,19 @@ size_t estimateMemoryUsage() const override; private: + void buildIndex(); - mutable std::mutex Mutex; - - std::shared_ptr> Symbols /*GUARDED_BY(Mutex)*/; - llvm::DenseMap LookupTable /*GUARDED_BY(Mutex)*/; - llvm::DenseMap SymbolQuality /*GUARDED_BY(Mutex)*/; + std::vector Symbols; + llvm::DenseMap LookupTable; + llvm::DenseMap SymbolQuality; // Inverted index is a mapping from the search token to the posting list, // which contains all items which can be characterized by such search token. // For example, if the search token is scope "std::", the corresponding // posting list would contain all indices of symbols defined in namespace std. // Inverted index is used to retrieve posting lists which are processed during // the fuzzyFind process. - llvm::DenseMap InvertedIndex /*GUARDED_BY(Mutex)*/; + llvm::DenseMap InvertedIndex; + std::shared_ptr KeepAlive; // poor man's move-only std::any }; } // namespace dex Index: clangd/index/dex/DexIndex.cpp =================================================================== --- clangd/index/dex/DexIndex.cpp +++ clangd/index/dex/DexIndex.cpp @@ -36,48 +36,30 @@ } // namespace -void DexIndex::build(std::shared_ptr> Syms) { - llvm::DenseMap TempLookupTable; - llvm::DenseMap TempSymbolQuality; - for (const Symbol *Sym : *Syms) { - TempLookupTable[Sym->ID] = Sym; - TempSymbolQuality[Sym] = quality(*Sym); +void DexIndex::buildIndex() { + for (const Symbol *Sym : Symbols) { + LookupTable[Sym->ID] = Sym; + SymbolQuality[Sym] = quality(*Sym); } // 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(*Syms), end(*Syms), + std::sort(begin(Symbols), end(Symbols), [&](const Symbol *LHS, const Symbol *RHS) { - return TempSymbolQuality[LHS] > TempSymbolQuality[RHS]; + return SymbolQuality[LHS] > SymbolQuality[RHS]; }); - llvm::DenseMap TempInvertedIndex; + // Populate TempInvertedIndex with posting lists for index symbols. - for (DocID SymbolRank = 0; SymbolRank < Syms->size(); ++SymbolRank) { - const auto *Sym = (*Syms)[SymbolRank]; + for (DocID SymbolRank = 0; SymbolRank < Symbols.size(); ++SymbolRank) { + const auto *Sym = Symbols[SymbolRank]; for (const auto &Token : generateSearchTokens(*Sym)) - TempInvertedIndex[Token].push_back(SymbolRank); - } - - { - std::lock_guard Lock(Mutex); - - // Replace outdated index with the new one. - LookupTable = std::move(TempLookupTable); - Symbols = std::move(Syms); - InvertedIndex = std::move(TempInvertedIndex); - SymbolQuality = std::move(TempSymbolQuality); + InvertedIndex[Token].push_back(SymbolRank); } vlog("Built DexIndex with estimated memory usage {0} bytes.", estimateMemoryUsage()); } -std::unique_ptr DexIndex::build(SymbolSlab Slab) { - auto Idx = llvm::make_unique(); - Idx->build(getSymbolsFromSlab(std::move(Slab))); - return std::move(Idx); -} - /// Constructs iterators over tokens extracted from the query and exhausts it /// while applying Callback to each symbol in the order of decreasing quality /// of the matched symbols. @@ -92,75 +74,69 @@ std::vector> TopLevelChildren; const auto TrigramTokens = generateIdentifierTrigrams(Req.Query); - { - std::lock_guard Lock(Mutex); - - // Generate query trigrams and construct AND iterator over all query - // trigrams. - std::vector> TrigramIterators; - for (const auto &Trigram : TrigramTokens) { - const auto It = InvertedIndex.find(Trigram); - if (It != InvertedIndex.end()) - TrigramIterators.push_back(create(It->second)); - } - if (!TrigramIterators.empty()) - 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)); - } - // Add OR iterator for scopes if there are any Scope Iterators. - if (!ScopeIterators.empty()) - TopLevelChildren.push_back(createOr(move(ScopeIterators))); - - // Use TRUE iterator if both trigrams and scopes from the query are not - // present in the symbol index. - auto QueryIterator = TopLevelChildren.empty() - ? createTrue(Symbols->size()) - : createAnd(move(TopLevelChildren)); - // Retrieve more items than it was requested: some of the items with high - // final score might not be retrieved otherwise. - // FIXME(kbobyrev): Pre-scoring retrieval threshold should be adjusted as - // using 100x of the requested number might not be good in practice, e.g. - // when the requested number of items is small. - const unsigned ItemsToRetrieve = 100 * Req.MaxCandidateCount; - auto Root = createLimit(move(QueryIterator), ItemsToRetrieve); - // FIXME(kbobyrev): Add boosting to the query and utilize retrieved - // boosting scores. - std::vector> SymbolDocIDs = consume(*Root); - - // Retrieve top Req.MaxCandidateCount items. - std::priority_queue> Top; - for (const auto &P : SymbolDocIDs) { - const DocID SymbolDocID = P.first; - const auto *Sym = (*Symbols)[SymbolDocID]; - const llvm::Optional Score = Filter.match(Sym->Name); - if (!Score) - continue; - // Multiply score by a negative factor so that Top stores items with the - // highest actual score. - Top.emplace(-(*Score) * SymbolQuality.find(Sym)->second, Sym); - if (Top.size() > Req.MaxCandidateCount) { - More = true; - Top.pop(); - } + // Generate query trigrams and construct AND iterator over all query + // trigrams. + std::vector> TrigramIterators; + for (const auto &Trigram : TrigramTokens) { + const auto It = InvertedIndex.find(Trigram); + if (It != InvertedIndex.end()) + TrigramIterators.push_back(create(It->second)); + } + if (!TrigramIterators.empty()) + 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)); + } + // Add OR iterator for scopes if there are any Scope Iterators. + if (!ScopeIterators.empty()) + TopLevelChildren.push_back(createOr(move(ScopeIterators))); + + // Use TRUE iterator if both trigrams and scopes from the query are not + // present in the symbol index. + auto QueryIterator = TopLevelChildren.empty() + ? createTrue(Symbols.size()) + : createAnd(move(TopLevelChildren)); + // Retrieve more items than it was requested: some of the items with high + // final score might not be retrieved otherwise. + // FIXME(kbobyrev): Pre-scoring retrieval threshold should be adjusted as + // using 100x of the requested number might not be good in practice, e.g. + // when the requested number of items is small. + const unsigned ItemsToRetrieve = 100 * Req.MaxCandidateCount; + auto Root = createLimit(move(QueryIterator), ItemsToRetrieve); + // FIXME(kbobyrev): Add boosting to the query and utilize retrieved + // boosting scores. + std::vector> SymbolDocIDs = consume(*Root); + + // Retrieve top Req.MaxCandidateCount items. + std::priority_queue> Top; + for (const auto &P : SymbolDocIDs) { + const DocID SymbolDocID = P.first; + const auto *Sym = Symbols[SymbolDocID]; + const llvm::Optional Score = Filter.match(Sym->Name); + if (!Score) + continue; + // Multiply score by a negative factor so that Top stores items with the + // highest actual score. + Top.emplace(-(*Score) * SymbolQuality.find(Sym)->second, Sym); + if (Top.size() > Req.MaxCandidateCount) { + More = true; + Top.pop(); } - - // Apply callback to the top Req.MaxCandidateCount items. - for (; !Top.empty(); Top.pop()) - Callback(*Top.top().second); } + // Apply callback to the top Req.MaxCandidateCount items. + for (; !Top.empty(); Top.pop()) + Callback(*Top.top().second); return More; } void DexIndex::lookup(const LookupRequest &Req, llvm::function_ref Callback) const { - std::lock_guard Lock(Mutex); for (const auto &ID : Req.IDs) { auto I = LookupTable.find(ID); if (I != LookupTable.end()) @@ -175,8 +151,6 @@ } size_t DexIndex::estimateMemoryUsage() const { - std::lock_guard Lock(Mutex); - size_t Bytes = LookupTable.size() * sizeof(std::pair); Bytes += SymbolQuality.size() * sizeof(std::pair); Index: unittests/clangd/DexIndexTests.cpp =================================================================== --- unittests/clangd/DexIndexTests.cpp +++ unittests/clangd/DexIndexTests.cpp @@ -23,6 +23,7 @@ using ::testing::ElementsAre; using ::testing::UnorderedElementsAre; +using namespace llvm; namespace clang { namespace clangd { @@ -408,171 +409,140 @@ } 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")}), + auto I = DexIndex::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")}), + EXPECT_THAT(lookup(*I, {SymbolID("ns::nonono"), SymbolID("ns::xyz")}), UnorderedElementsAre("ns::xyz")); - EXPECT_THAT(lookup(I, SymbolID("ns::nonono")), UnorderedElementsAre()); + EXPECT_THAT(lookup(*I, SymbolID("ns::nonono")), UnorderedElementsAre()); } TEST(DexIndex, FuzzyFind) { - DexIndex Index; - Index.build(generateSymbols({"ns::ABC", "ns::BCD", "::ABC", "ns::nested::ABC", - "other::ABC", "other::A"})); + auto Index = DexIndex::build( + generateSymbols({"ns::ABC", "ns::BCD", "::ABC", "ns::nested::ABC", + "other::ABC", "other::A"})); FuzzyFindRequest Req; Req.Query = "ABC"; Req.Scopes = {"ns::"}; - EXPECT_THAT(match(Index, Req), UnorderedElementsAre("ns::ABC")); + EXPECT_THAT(match(*Index, Req), UnorderedElementsAre("ns::ABC")); Req.Scopes = {"ns::", "ns::nested::"}; - EXPECT_THAT(match(Index, Req), + EXPECT_THAT(match(*Index, Req), UnorderedElementsAre("ns::ABC", "ns::nested::ABC")); Req.Query = "A"; Req.Scopes = {"other::"}; - EXPECT_THAT(match(Index, Req), + EXPECT_THAT(match(*Index, Req), UnorderedElementsAre("other::A", "other::ABC")); Req.Query = ""; Req.Scopes = {}; - EXPECT_THAT(match(Index, Req), + EXPECT_THAT(match(*Index, Req), UnorderedElementsAre("ns::ABC", "ns::BCD", "::ABC", "ns::nested::ABC", "other::ABC", "other::A")); } TEST(DexIndexTest, FuzzyMatchQ) { - DexIndex I; - I.build( + auto I = DexIndex::build( generateSymbols({"LaughingOutLoud", "LionPopulation", "LittleOldLady"})); FuzzyFindRequest Req; Req.Query = "lol"; Req.MaxCandidateCount = 2; - EXPECT_THAT(match(I, Req), + 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()); -} - // FIXME(kbobyrev): This test is different for DexIndex and MemIndex: while // MemIndex manages response deduplication, DexIndex simply returns all matched // symbols which means there might be equivalent symbols in the response. // Before drop-in replacement of MemIndex with DexIndex happens, FileIndex // should handle deduplication instead. TEST(DexIndexTest, DexIndexDeduplicate) { - auto Symbols = generateNumSymbols(0, 10); - - // Inject duplicates. - auto Sym = symbol("7"); - Symbols->push_back(&Sym); - Symbols->push_back(&Sym); - Symbols->push_back(&Sym); - + std::vector Symbols = {symbol("1"), symbol("2"), symbol("3"), + symbol("2") /* duplicate */}; FuzzyFindRequest Req; - Req.Query = "7"; - DexIndex I; - I.build(std::move(Symbols)); - auto Matches = match(I, Req); - EXPECT_EQ(Matches.size(), 4u); + Req.Query = "2"; + DexIndex I(Symbols); + EXPECT_THAT(match(I, Req), ElementsAre("2", "2")); } TEST(DexIndexTest, DexIndexLimitedNumMatches) { - DexIndex I; - I.build(generateNumSymbols(0, 100)); + auto I = DexIndex::build(generateNumSymbols(0, 100)); FuzzyFindRequest Req; Req.Query = "5"; Req.MaxCandidateCount = 3; bool Incomplete; - auto Matches = match(I, Req, &Incomplete); + auto Matches = match(*I, Req, &Incomplete); EXPECT_EQ(Matches.size(), Req.MaxCandidateCount); EXPECT_TRUE(Incomplete); } TEST(DexIndexTest, FuzzyMatch) { - DexIndex I; - I.build( + auto I = DexIndex::build( generateSymbols({"LaughingOutLoud", "LionPopulation", "LittleOldLady"})); FuzzyFindRequest Req; Req.Query = "lol"; Req.MaxCandidateCount = 2; - EXPECT_THAT(match(I, Req), + EXPECT_THAT(match(*I, Req), UnorderedElementsAre("LaughingOutLoud", "LittleOldLady")); } TEST(DexIndexTest, MatchQualifiedNamesWithoutSpecificScope) { - DexIndex I; - I.build(generateSymbols({"a::y1", "b::y2", "y3"})); + auto I = DexIndex::build(generateSymbols({"a::y1", "b::y2", "y3"})); FuzzyFindRequest Req; Req.Query = "y"; - EXPECT_THAT(match(I, Req), UnorderedElementsAre("a::y1", "b::y2", "y3")); + EXPECT_THAT(match(*I, Req), UnorderedElementsAre("a::y1", "b::y2", "y3")); } TEST(DexIndexTest, MatchQualifiedNamesWithGlobalScope) { - DexIndex I; - I.build(generateSymbols({"a::y1", "b::y2", "y3"})); + auto I = DexIndex::build(generateSymbols({"a::y1", "b::y2", "y3"})); FuzzyFindRequest Req; Req.Query = "y"; Req.Scopes = {""}; - EXPECT_THAT(match(I, Req), UnorderedElementsAre("y3")); + EXPECT_THAT(match(*I, Req), UnorderedElementsAre("y3")); } TEST(DexIndexTest, MatchQualifiedNamesWithOneScope) { - DexIndex I; - I.build(generateSymbols({"a::y1", "a::y2", "a::x", "b::y2", "y3"})); + auto I = DexIndex::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")); + 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"})); + auto I = DexIndex::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")); + 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"})); + auto I = DexIndex::build(generateSymbols({"a::y1", "a::b::y2"})); FuzzyFindRequest Req; Req.Query = "y"; Req.Scopes = {"a::"}; - EXPECT_THAT(match(I, Req), UnorderedElementsAre("a::y1")); + EXPECT_THAT(match(*I, Req), UnorderedElementsAre("a::y1")); } TEST(DexIndexTest, IgnoreCases) { - DexIndex I; - I.build(generateSymbols({"ns::ABC", "ns::abc"})); + auto I = DexIndex::build(generateSymbols({"ns::ABC", "ns::abc"})); FuzzyFindRequest Req; Req.Query = "AB"; Req.Scopes = {"ns::"}; - EXPECT_THAT(match(I, Req), UnorderedElementsAre("ns::ABC", "ns::abc")); + 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")}), + auto I = DexIndex::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")}), + EXPECT_THAT(lookup(*I, {SymbolID("ns::nonono"), SymbolID("ns::xyz")}), UnorderedElementsAre("ns::xyz")); - EXPECT_THAT(lookup(I, SymbolID("ns::nonono")), UnorderedElementsAre()); + EXPECT_THAT(lookup(*I, SymbolID("ns::nonono")), UnorderedElementsAre()); } } // namespace Index: unittests/clangd/FileIndexTests.cpp =================================================================== --- unittests/clangd/FileIndexTests.cpp +++ unittests/clangd/FileIndexTests.cpp @@ -54,23 +54,27 @@ auto Slab = llvm::make_unique(); SymbolOccurrence Occurrence; Occurrence.Location.FileURI = Path; + Occurrence.Kind = SymbolOccurrenceKind::Reference; Slab->insert(ID, Occurrence); return Slab; } -std::vector -getSymbolNames(const std::vector &Symbols) { +std::vector getSymbolNames(const SymbolIndex &I, + std::string Query = "") { + FuzzyFindRequest Req; + Req.Query = Query; std::vector Names; - for (const Symbol *Sym : Symbols) - Names.push_back(Sym->Name); + I.fuzzyFind(Req, [&](const Symbol &S) { Names.push_back(S.Name); }); return Names; } -std::vector -getOccurrencePath(const std::vector &Occurrences) { +std::vector getOccurrencePaths(const SymbolIndex &I, SymbolID ID) { + OccurrencesRequest Req; + Req.IDs = {ID}; std::vector Paths; - for (const auto *O : Occurrences) - Paths.push_back(O->Location.FileURI); + I.findOccurrences(Req, [&](const SymbolOccurrence &S) { + Paths.push_back(S.Location.FileURI); + }); return Paths; } @@ -82,15 +86,12 @@ TEST(FileSymbolsTest, UpdateAndGet) { FileSymbols FS; - EXPECT_THAT(getSymbolNames(*FS.allSymbols()), UnorderedElementsAre()); - EXPECT_TRUE(FS.allOccurrences()->empty()); + EXPECT_THAT(getSymbolNames(*FS.buildMemIndex()), UnorderedElementsAre()); - SymbolID ID("1"); - FS.update("f1", numSlab(1, 3), occurrenceSlab(ID, "f1.cc")); - EXPECT_THAT(getSymbolNames(*FS.allSymbols()), + FS.update("f1", numSlab(1, 3), occurrenceSlab(SymbolID("1"), "f1.cc")); + EXPECT_THAT(getSymbolNames(*FS.buildMemIndex()), UnorderedElementsAre("1", "2", "3")); - auto Occurrences = FS.allOccurrences(); - EXPECT_THAT(getOccurrencePath((*Occurrences)[ID]), + EXPECT_THAT(getOccurrencePaths(*FS.buildMemIndex(), SymbolID("1")), UnorderedElementsAre("f1.cc")); } @@ -98,8 +99,8 @@ FileSymbols FS; FS.update("f1", numSlab(1, 3), emptyOccurrence()); FS.update("f2", numSlab(3, 5), emptyOccurrence()); - EXPECT_THAT(getSymbolNames(*FS.allSymbols()), - UnorderedElementsAre("1", "2", "3", "3", "4", "5")); + EXPECT_THAT(getSymbolNames(*FS.buildMemIndex()), + UnorderedElementsAre("1", "2", "3", "4", "5")); } TEST(FileSymbolsTest, SnapshotAliveAfterRemove) { @@ -108,19 +109,17 @@ SymbolID ID("1"); FS.update("f1", numSlab(1, 3), occurrenceSlab(ID, "f1.cc")); - auto Symbols = FS.allSymbols(); + auto Symbols = FS.buildMemIndex(); EXPECT_THAT(getSymbolNames(*Symbols), UnorderedElementsAre("1", "2", "3")); - auto Occurrences = FS.allOccurrences(); - EXPECT_THAT(getOccurrencePath((*Occurrences)[ID]), - UnorderedElementsAre("f1.cc")); + EXPECT_THAT(getOccurrencePaths(*Symbols, ID), UnorderedElementsAre("f1.cc")); FS.update("f1", nullptr, nullptr); - EXPECT_THAT(getSymbolNames(*FS.allSymbols()), UnorderedElementsAre()); - EXPECT_THAT(getSymbolNames(*Symbols), UnorderedElementsAre("1", "2", "3")); + auto Empty = FS.buildMemIndex(); + EXPECT_THAT(getSymbolNames(*Empty), UnorderedElementsAre()); + EXPECT_THAT(getOccurrencePaths(*Empty, ID), UnorderedElementsAre()); - EXPECT_TRUE(FS.allOccurrences()->empty()); - EXPECT_THAT(getOccurrencePath((*Occurrences)[ID]), - UnorderedElementsAre("f1.cc")); + EXPECT_THAT(getSymbolNames(*Symbols), UnorderedElementsAre("1", "2", "3")); + EXPECT_THAT(getOccurrencePaths(*Symbols, ID), UnorderedElementsAre("f1.cc")); } std::vector match(const SymbolIndex &I, Index: unittests/clangd/IndexTests.cpp =================================================================== --- unittests/clangd/IndexTests.cpp +++ unittests/clangd/IndexTests.cpp @@ -17,18 +17,16 @@ #include "index/Merge.h" #include "gtest/gtest.h" +using testing::AllOf; +using testing::ElementsAre; using testing::Pointee; using testing::UnorderedElementsAre; -using testing::AllOf; +using namespace llvm; namespace clang { namespace clangd { namespace { -std::shared_ptr emptyOccurrences() { - return llvm::make_unique(); -} - MATCHER_P(Named, N, "") { return arg.Name == N; } MATCHER_P(OccurrenceRange, Range, "") { return std::tie(arg.Location.Start.Line, arg.Location.Start.Column, @@ -54,155 +52,139 @@ EXPECT_THAT(*S.find(SymbolID(Sym)), Named(Sym)); } -TEST(MemIndexTest, MemIndexSymbolsRecycled) { - MemIndex I; - std::weak_ptr Symbols; - I.build(generateNumSymbols(0, 10, &Symbols), emptyOccurrences()); - FuzzyFindRequest Req; - Req.Query = "7"; - EXPECT_THAT(match(I, Req), UnorderedElementsAre("7")); +TEST(SwapIndexTest, OldIndexRecycled) { + auto Token = std::make_shared(); + std::weak_ptr WeakToken = Token; - EXPECT_FALSE(Symbols.expired()); - // Release old symbols. - I.build(generateNumSymbols(0, 0), emptyOccurrences()); - EXPECT_TRUE(Symbols.expired()); + SwapIndex S(make_unique(SymbolSlab(), MemIndex::OccurrenceMap(), + std::move(Token))); + EXPECT_FALSE(WeakToken.expired()); // Current MemIndex keeps it alive. + S.reset(make_unique()); // Now the MemIndex is destroyed. + EXPECT_TRUE(WeakToken.expired()); // So the token is too. } TEST(MemIndexTest, MemIndexDeduplicate) { - 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); - + std::vector Symbols = {symbol("1"), symbol("2"), symbol("3"), + symbol("2") /* duplicate */}; FuzzyFindRequest Req; - Req.Query = "7"; - MemIndex I; - I.build(std::move(Symbols), emptyOccurrences()); - auto Matches = match(I, Req); - EXPECT_EQ(Matches.size(), 1u); + Req.Query = "2"; + MemIndex I(Symbols, MemIndex::OccurrenceMap()); + EXPECT_THAT(match(I, Req), ElementsAre("2")); } TEST(MemIndexTest, MemIndexLimitedNumMatches) { - MemIndex I; - I.build(generateNumSymbols(0, 100), emptyOccurrences()); + auto I = MemIndex::build(generateNumSymbols(0, 100), SymbolOccurrenceSlab()); FuzzyFindRequest Req; Req.Query = "5"; Req.MaxCandidateCount = 3; bool Incomplete; - auto Matches = match(I, Req, &Incomplete); + auto Matches = match(*I, Req, &Incomplete); EXPECT_EQ(Matches.size(), Req.MaxCandidateCount); EXPECT_TRUE(Incomplete); } TEST(MemIndexTest, FuzzyMatch) { - MemIndex I; - I.build( + auto I = MemIndex::build( generateSymbols({"LaughingOutLoud", "LionPopulation", "LittleOldLady"}), - emptyOccurrences()); + SymbolOccurrenceSlab()); FuzzyFindRequest Req; Req.Query = "lol"; Req.MaxCandidateCount = 2; - EXPECT_THAT(match(I, Req), + EXPECT_THAT(match(*I, Req), UnorderedElementsAre("LaughingOutLoud", "LittleOldLady")); } TEST(MemIndexTest, MatchQualifiedNamesWithoutSpecificScope) { - MemIndex I; - I.build(generateSymbols({"a::y1", "b::y2", "y3"}), emptyOccurrences()); + auto I = MemIndex::build(generateSymbols({"a::y1", "b::y2", "y3"}), + SymbolOccurrenceSlab()); FuzzyFindRequest Req; Req.Query = "y"; - EXPECT_THAT(match(I, Req), UnorderedElementsAre("a::y1", "b::y2", "y3")); + EXPECT_THAT(match(*I, Req), UnorderedElementsAre("a::y1", "b::y2", "y3")); } TEST(MemIndexTest, MatchQualifiedNamesWithGlobalScope) { - MemIndex I; - I.build(generateSymbols({"a::y1", "b::y2", "y3"}), emptyOccurrences()); + auto I = MemIndex::build(generateSymbols({"a::y1", "b::y2", "y3"}), + SymbolOccurrenceSlab()); FuzzyFindRequest Req; Req.Query = "y"; Req.Scopes = {""}; - EXPECT_THAT(match(I, Req), UnorderedElementsAre("y3")); + EXPECT_THAT(match(*I, Req), UnorderedElementsAre("y3")); } TEST(MemIndexTest, MatchQualifiedNamesWithOneScope) { - MemIndex I; - I.build(generateSymbols({"a::y1", "a::y2", "a::x", "b::y2", "y3"}), - emptyOccurrences()); + auto I = MemIndex::build( + generateSymbols({"a::y1", "a::y2", "a::x", "b::y2", "y3"}), + SymbolOccurrenceSlab()); FuzzyFindRequest Req; Req.Query = "y"; Req.Scopes = {"a::"}; - EXPECT_THAT(match(I, Req), UnorderedElementsAre("a::y1", "a::y2")); + EXPECT_THAT(match(*I, Req), UnorderedElementsAre("a::y1", "a::y2")); } TEST(MemIndexTest, MatchQualifiedNamesWithMultipleScopes) { - MemIndex I; - I.build(generateSymbols({"a::y1", "a::y2", "a::x", "b::y3", "y3"}), - emptyOccurrences()); + auto I = MemIndex::build( + generateSymbols({"a::y1", "a::y2", "a::x", "b::y3", "y3"}), + SymbolOccurrenceSlab()); FuzzyFindRequest Req; Req.Query = "y"; Req.Scopes = {"a::", "b::"}; - EXPECT_THAT(match(I, Req), UnorderedElementsAre("a::y1", "a::y2", "b::y3")); + EXPECT_THAT(match(*I, Req), UnorderedElementsAre("a::y1", "a::y2", "b::y3")); } TEST(MemIndexTest, NoMatchNestedScopes) { - MemIndex I; - I.build(generateSymbols({"a::y1", "a::b::y2"}), emptyOccurrences()); + auto I = MemIndex::build(generateSymbols({"a::y1", "a::b::y2"}), + SymbolOccurrenceSlab()); FuzzyFindRequest Req; Req.Query = "y"; Req.Scopes = {"a::"}; - EXPECT_THAT(match(I, Req), UnorderedElementsAre("a::y1")); + EXPECT_THAT(match(*I, Req), UnorderedElementsAre("a::y1")); } TEST(MemIndexTest, IgnoreCases) { - MemIndex I; - I.build(generateSymbols({"ns::ABC", "ns::abc"}), emptyOccurrences()); + auto I = MemIndex::build(generateSymbols({"ns::ABC", "ns::abc"}), + SymbolOccurrenceSlab()); FuzzyFindRequest Req; Req.Query = "AB"; Req.Scopes = {"ns::"}; - EXPECT_THAT(match(I, Req), UnorderedElementsAre("ns::ABC", "ns::abc")); + EXPECT_THAT(match(*I, Req), UnorderedElementsAre("ns::ABC", "ns::abc")); } TEST(MemIndexTest, Lookup) { - MemIndex I; - I.build(generateSymbols({"ns::abc", "ns::xyz"}), emptyOccurrences()); - EXPECT_THAT(lookup(I, SymbolID("ns::abc")), UnorderedElementsAre("ns::abc")); - EXPECT_THAT(lookup(I, {SymbolID("ns::abc"), SymbolID("ns::xyz")}), + auto I = MemIndex::build(generateSymbols({"ns::abc", "ns::xyz"}), + SymbolOccurrenceSlab()); + 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")}), + EXPECT_THAT(lookup(*I, {SymbolID("ns::nonono"), SymbolID("ns::xyz")}), UnorderedElementsAre("ns::xyz")); - EXPECT_THAT(lookup(I, SymbolID("ns::nonono")), UnorderedElementsAre()); + EXPECT_THAT(lookup(*I, SymbolID("ns::nonono")), UnorderedElementsAre()); } TEST(MergeIndexTest, Lookup) { - MemIndex I, J; - I.build(generateSymbols({"ns::A", "ns::B"}), emptyOccurrences()); - J.build(generateSymbols({"ns::B", "ns::C"}), emptyOccurrences()); - 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()); + auto I = MemIndex::build(generateSymbols({"ns::A", "ns::B"}), + SymbolOccurrenceSlab()), + J = MemIndex::build(generateSymbols({"ns::B", "ns::C"}), + SymbolOccurrenceSlab()); + auto M = mergeIndex(I.get(), J.get()); + EXPECT_THAT(lookup(*M, SymbolID("ns::A")), UnorderedElementsAre("ns::A")); + EXPECT_THAT(lookup(*M, SymbolID("ns::B")), UnorderedElementsAre("ns::B")); + EXPECT_THAT(lookup(*M, SymbolID("ns::C")), UnorderedElementsAre("ns::C")); + EXPECT_THAT(lookup(*M, {SymbolID("ns::A"), SymbolID("ns::B")}), + UnorderedElementsAre("ns::A", "ns::B")); + EXPECT_THAT(lookup(*M, {SymbolID("ns::A"), SymbolID("ns::C")}), + UnorderedElementsAre("ns::A", "ns::C")); + EXPECT_THAT(lookup(*M, SymbolID("ns::D")), UnorderedElementsAre()); + EXPECT_THAT(lookup(*M, {}), UnorderedElementsAre()); } TEST(MergeIndexTest, FuzzyFind) { - MemIndex I, J; - I.build(generateSymbols({"ns::A", "ns::B"}), emptyOccurrences()); - J.build(generateSymbols({"ns::B", "ns::C"}), emptyOccurrences()); + auto I = MemIndex::build(generateSymbols({"ns::A", "ns::B"}), + SymbolOccurrenceSlab()), + J = MemIndex::build(generateSymbols({"ns::B", "ns::C"}), + SymbolOccurrenceSlab()); FuzzyFindRequest Req; Req.Scopes = {"ns::"}; - EXPECT_THAT(match(*mergeIndex(&I, &J), Req), + EXPECT_THAT(match(*mergeIndex(I.get(), J.get()), Req), UnorderedElementsAre("ns::A", "ns::B", "ns::C")); } Index: unittests/clangd/TestIndex.h =================================================================== --- unittests/clangd/TestIndex.h +++ unittests/clangd/TestIndex.h @@ -23,26 +23,11 @@ // Creates Symbol instance and sets SymbolID to given QualifiedName. Symbol symbol(llvm::StringRef QName); -// Bundles symbol pointers with the actual symbol slab the pointers refer to in -// order to ensure that the slab isn't destroyed while it's used by and index. -struct SlabAndPointers { - SymbolSlab Slab; - std::vector Pointers; -}; +// Create a slab of symbols with the given qualified names as IDs and names. +SymbolSlab generateSymbols(std::vector QualifiedNames); -// 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); +// Create a slab of symbols with IDs and names [Begin, End]. +SymbolSlab generateNumSymbols(int Begin, int End); // Returns fully-qualified name out of given symbol. std::string getQualifiedName(const Symbol &Sym); Index: unittests/clangd/TestIndex.cpp =================================================================== --- unittests/clangd/TestIndex.cpp +++ unittests/clangd/TestIndex.cpp @@ -26,30 +26,18 @@ return Sym; } -std::shared_ptr> -generateSymbols(std::vector QualifiedNames, - std::weak_ptr *WeakSymbols) { +SymbolSlab generateSymbols(std::vector QualifiedNames) { 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}; + return std::move(Slab).build(); } -std::shared_ptr> -generateNumSymbols(int Begin, int End, - std::weak_ptr *WeakSymbols) { +SymbolSlab generateNumSymbols(int Begin, int End) { std::vector Names; for (int i = Begin; i <= End; i++) Names.push_back(std::to_string(i)); - return generateSymbols(Names, WeakSymbols); + return generateSymbols(Names); } std::string getQualifiedName(const Symbol &Sym) {