diff options
19 files changed, 328 insertions, 388 deletions
diff --git a/clang-tools-extra/clangd/ClangdServer.cpp b/clang-tools-extra/clangd/ClangdServer.cpp index 30bef3ca75f..5bd2a910dff 100644 --- a/clang-tools-extra/clangd/ClangdServer.cpp +++ b/clang-tools-extra/clangd/ClangdServer.cpp @@ -106,7 +106,7 @@ private: // Contains information from each file's preamble only. // These are large, but update fairly infrequently (preambles are stable). // Missing information: - // - symbol occurrences (these are always "from the main file") + // - symbol refs (these are always "from the main file") // - definition locations in the main file // // FIXME: Because the preambles for different TUs have large overlap and @@ -118,7 +118,7 @@ private: // Contains information from each file's main AST. // These are updated frequently (on file change), but are relatively small. // Mostly contains: - // - occurrences of symbols declared in the preamble and referenced from main + // - refs to symbols declared in the preamble and referenced from main // - symbols declared both in the main file and the preamble // (Note that symbols *only* in the main file are not indexed). FileIndex MainFileIdx; diff --git a/clang-tools-extra/clangd/index/FileIndex.cpp b/clang-tools-extra/clangd/index/FileIndex.cpp index 105c7fdbe16..1b430e66ab6 100644 --- a/clang-tools-extra/clangd/index/FileIndex.cpp +++ b/clang-tools-extra/clangd/index/FileIndex.cpp @@ -16,7 +16,7 @@ namespace clang { namespace clangd { -std::pair<SymbolSlab, SymbolOccurrenceSlab> +std::pair<SymbolSlab, RefSlab> indexAST(ASTContext &AST, std::shared_ptr<Preprocessor> PP, llvm::Optional<llvm::ArrayRef<Decl *>> TopLevelDecls, llvm::ArrayRef<std::string> URISchemes) { @@ -45,12 +45,12 @@ indexAST(ASTContext &AST, std::shared_ptr<Preprocessor> PP, DeclsToIndex.assign(AST.getTranslationUnitDecl()->decls().begin(), AST.getTranslationUnitDecl()->decls().end()); - // We only collect occurrences when indexing main AST. + // We only collect refs when indexing main AST. // FIXME: this is a hacky way to detect whether we are indexing preamble AST // or main AST, we should make it explicitly. bool IsIndexMainAST = TopLevelDecls.hasValue(); if (IsIndexMainAST) - CollectorOpts.OccurrenceFilter = AllOccurrenceKinds; + CollectorOpts.RefFilter = RefKind::All; SymbolCollector Collector(std::move(CollectorOpts)); Collector.setPreprocessor(PP); @@ -61,13 +61,13 @@ indexAST(ASTContext &AST, std::shared_ptr<Preprocessor> PP, std::string FileName = MainFileEntry ? MainFileEntry->getName() : ""; auto Syms = Collector.takeSymbols(); - auto Occurrences = Collector.takeOccurrences(); + auto Refs = Collector.takeRefs(); vlog("index {0}AST for {1}: \n" " symbol slab: {2} symbols, {3} bytes\n" - " occurrence slab: {4} symbols, {5} bytes", + " ref slab: {4} symbols, {5} bytes", IsIndexMainAST ? "Main" : "Preamble", FileName, Syms.size(), - Syms.bytes(), Occurrences.size(), Occurrences.bytes()); - return {std::move(Syms), std::move(Occurrences)}; + Syms.bytes(), Refs.size(), Refs.bytes()); + return {std::move(Syms), std::move(Refs)}; } FileIndex::FileIndex(std::vector<std::string> URISchemes) @@ -75,45 +75,63 @@ FileIndex::FileIndex(std::vector<std::string> URISchemes) reset(FSymbols.buildMemIndex()); } -void FileSymbols::update(PathRef Path, std::unique_ptr<SymbolSlab> Slab, - std::unique_ptr<SymbolOccurrenceSlab> Occurrences) { +void FileSymbols::update(PathRef Path, std::unique_ptr<SymbolSlab> Symbols, + std::unique_ptr<RefSlab> Refs) { std::lock_guard<std::mutex> Lock(Mutex); - if (!Slab) - FileToSlabs.erase(Path); + if (!Symbols) + FileToSymbols.erase(Path); else - FileToSlabs[Path] = std::move(Slab); - if (!Occurrences) - FileToOccurrenceSlabs.erase(Path); + FileToSymbols[Path] = std::move(Symbols); + if (!Refs) + FileToRefs.erase(Path); else - FileToOccurrenceSlabs[Path] = std::move(Occurrences); + FileToRefs[Path] = std::move(Refs); } std::unique_ptr<SymbolIndex> FileSymbols::buildMemIndex() { - std::vector<std::shared_ptr<SymbolSlab>> Slabs; - std::vector<std::shared_ptr<SymbolOccurrenceSlab>> OccurrenceSlabs; + std::vector<std::shared_ptr<SymbolSlab>> SymbolSlabs; + std::vector<std::shared_ptr<RefSlab>> RefSlabs; { std::lock_guard<std::mutex> Lock(Mutex); - for (const auto &FileAndSlab : FileToSlabs) - Slabs.push_back(FileAndSlab.second); - for (const auto &FileAndOccurrenceSlab : FileToOccurrenceSlabs) - OccurrenceSlabs.push_back(FileAndOccurrenceSlab.second); + for (const auto &FileAndSymbols : FileToSymbols) + SymbolSlabs.push_back(FileAndSymbols.second); + for (const auto &FileAndRefs : FileToRefs) + RefSlabs.push_back(FileAndRefs.second); } std::vector<const Symbol *> AllSymbols; - for (const auto &Slab : Slabs) + for (const auto &Slab : SymbolSlabs) 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); + + std::vector<Ref> RefsStorage; // Contiguous ranges for each SymbolID. + llvm::DenseMap<SymbolID, ArrayRef<Ref>> AllRefs; + { + llvm::DenseMap<SymbolID, SmallVector<Ref, 4>> MergedRefs; + size_t Count = 0; + for (const auto &RefSlab : RefSlabs) + for (const auto &Sym : *RefSlab) { + MergedRefs[Sym.first].append(Sym.second.begin(), Sym.second.end()); + Count += Sym.second.size(); + } + RefsStorage.reserve(Count); + AllRefs.reserve(MergedRefs.size()); + for (auto &Sym : MergedRefs) { + auto &SymRefs = Sym.second; + // Sorting isn't required, but yields more stable results over rebuilds. + std::sort(SymRefs.begin(), SymRefs.end()); + std::copy(SymRefs.begin(), SymRefs.end(), back_inserter(RefsStorage)); + AllRefs.try_emplace( + Sym.first, + ArrayRef<Ref>(&RefsStorage[RefsStorage.size() - SymRefs.size()], + SymRefs.size())); } + } - // Index must keep the slabs alive. + // Index must keep the slabs and contiguous ranges alive. return llvm::make_unique<MemIndex>( - llvm::make_pointee_range(AllSymbols), std::move(AllOccurrences), - std::make_pair(std::move(Slabs), std::move(OccurrenceSlabs))); + llvm::make_pointee_range(AllSymbols), std::move(AllRefs), + std::make_tuple(std::move(SymbolSlabs), std::move(RefSlabs), + std::move(RefsStorage))); } void FileIndex::update(PathRef Path, ASTContext *AST, @@ -123,11 +141,10 @@ void FileIndex::update(PathRef Path, ASTContext *AST, FSymbols.update(Path, nullptr, nullptr); } else { assert(PP); - auto Slab = llvm::make_unique<SymbolSlab>(); - auto OccurrenceSlab = llvm::make_unique<SymbolOccurrenceSlab>(); - std::tie(*Slab, *OccurrenceSlab) = - indexAST(*AST, PP, TopLevelDecls, URISchemes); - FSymbols.update(Path, std::move(Slab), std::move(OccurrenceSlab)); + auto Contents = indexAST(*AST, PP, TopLevelDecls, URISchemes); + FSymbols.update(Path, + llvm::make_unique<SymbolSlab>(std::move(Contents.first)), + llvm::make_unique<RefSlab>(std::move(Contents.second))); } reset(FSymbols.buildMemIndex()); } diff --git a/clang-tools-extra/clangd/index/FileIndex.h b/clang-tools-extra/clangd/index/FileIndex.h index 471fa4c9ee2..9c616231ee0 100644 --- a/clang-tools-extra/clangd/index/FileIndex.h +++ b/clang-tools-extra/clangd/index/FileIndex.h @@ -39,10 +39,10 @@ namespace clangd { /// locking when we swap or obtain references to snapshots. class FileSymbols { public: - /// Updates all symbols and occurrences in a file. + /// Updates all symbols and refs in a file. /// If either is nullptr, corresponding data for \p Path will be removed. void update(PathRef Path, std::unique_ptr<SymbolSlab> Slab, - std::unique_ptr<SymbolOccurrenceSlab> Occurrences); + std::unique_ptr<RefSlab> Refs); // The index keeps the symbols alive. std::unique_ptr<SymbolIndex> buildMemIndex(); @@ -50,10 +50,10 @@ public: private: mutable std::mutex Mutex; - /// Stores the latest snapshots for all active files. - llvm::StringMap<std::shared_ptr<SymbolSlab>> FileToSlabs; - /// Stores the latest occurrence slabs for all active files. - llvm::StringMap<std::shared_ptr<SymbolOccurrenceSlab>> FileToOccurrenceSlabs; + /// Stores the latest symbol snapshots for all active files. + llvm::StringMap<std::shared_ptr<SymbolSlab>> FileToSymbols; + /// Stores the latest ref snapshots for all active files. + llvm::StringMap<std::shared_ptr<RefSlab>> FileToRefs; }; /// This manages symbols from files and an in-memory index on all symbols. @@ -81,12 +81,12 @@ private: std::vector<std::string> URISchemes; }; -/// Retrieves symbols and symbol occurrences in \p AST. +/// Retrieves symbols and refs in \p AST. /// Exposed to assist in unit tests. /// If URISchemes is empty, the default schemes in SymbolCollector will be used. /// If \p TopLevelDecls is set, only these decls are indexed. Otherwise, all top /// level decls obtained from \p AST are indexed. -std::pair<SymbolSlab, SymbolOccurrenceSlab> +std::pair<SymbolSlab, RefSlab> indexAST(ASTContext &AST, std::shared_ptr<Preprocessor> PP, llvm::Optional<llvm::ArrayRef<Decl *>> TopLevelDecls = llvm::None, llvm::ArrayRef<std::string> URISchemes = {}); diff --git a/clang-tools-extra/clangd/index/Index.cpp b/clang-tools-extra/clangd/index/Index.cpp index eaa287ef068..52eb42799af 100644 --- a/clang-tools-extra/clangd/index/Index.cpp +++ b/clang-tools-extra/clangd/index/Index.cpp @@ -122,8 +122,8 @@ SymbolSlab SymbolSlab::Builder::build() && { return SymbolSlab(std::move(NewArena), std::move(Symbols)); } -raw_ostream &operator<<(raw_ostream &OS, SymbolOccurrenceKind K) { - if (K == SymbolOccurrenceKind::Unknown) +raw_ostream &operator<<(raw_ostream &OS, RefKind K) { + if (K == RefKind::Unknown) return OS << "Unknown"; static const std::vector<const char *> Messages = {"Decl", "Def", "Ref"}; bool VisitedOnce = false; @@ -138,31 +138,32 @@ raw_ostream &operator<<(raw_ostream &OS, SymbolOccurrenceKind K) { return OS; } -llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, - const SymbolOccurrence &Occurrence) { - OS << Occurrence.Location << ":" << Occurrence.Kind; - return OS; +llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, const Ref &R) { + return OS << R.Location << ":" << R.Kind; } -void SymbolOccurrenceSlab::insert(const SymbolID &SymID, - const SymbolOccurrence &Occurrence) { - assert(!Frozen && - "Can't insert a symbol occurrence after the slab has been frozen!"); - auto &SymOccurrences = Occurrences[SymID]; - SymOccurrences.push_back(Occurrence); - SymOccurrences.back().Location.FileURI = - UniqueStrings.save(Occurrence.Location.FileURI); +void RefSlab::Builder::insert(const SymbolID &ID, const Ref &S) { + auto &M = Refs[ID]; + M.push_back(S); + M.back().Location.FileURI = UniqueStrings.save(M.back().Location.FileURI); } -void SymbolOccurrenceSlab::freeze() { - // Deduplicate symbol occurrences. - for (auto &IDAndOccurrence : Occurrences) { - auto &Occurrence = IDAndOccurrence.getSecond(); - std::sort(Occurrence.begin(), Occurrence.end()); - Occurrence.erase(std::unique(Occurrence.begin(), Occurrence.end()), - Occurrence.end()); +RefSlab RefSlab::Builder::build() && { + // We can reuse the arena, as it only has unique strings and we need them all. + // Reallocate refs on the arena to reduce waste and indirections when reading. + std::vector<std::pair<SymbolID, ArrayRef<Ref>>> Result; + Result.reserve(Refs.size()); + for (auto &Sym : Refs) { + auto &SymRefs = Sym.second; + std::sort(SymRefs.begin(), SymRefs.end()); + // TODO: do we really need to dedup? + SymRefs.erase(std::unique(SymRefs.begin(), SymRefs.end()), SymRefs.end()); + + auto *Array = Arena.Allocate<Ref>(SymRefs.size()); + std::uninitialized_copy(SymRefs.begin(), SymRefs.end(), Array); + Result.emplace_back(Sym.first, ArrayRef<Ref>(Array, SymRefs.size())); } - Frozen = true; + return RefSlab(std::move(Result), std::move(Arena)); } void SwapIndex::reset(std::unique_ptr<SymbolIndex> Index) { @@ -187,10 +188,9 @@ void SwapIndex::lookup(const LookupRequest &R, llvm::function_ref<void(const Symbol &)> CB) const { return snapshot()->lookup(R, CB); } -void SwapIndex::findOccurrences( - const OccurrencesRequest &R, - llvm::function_ref<void(const SymbolOccurrence &)> CB) const { - return snapshot()->findOccurrences(R, CB); +void SwapIndex::refs(const RefsRequest &R, + llvm::function_ref<void(const Ref &)> CB) const { + return snapshot()->refs(R, CB); } size_t SwapIndex::estimateMemoryUsage() const { return snapshot()->estimateMemoryUsage(); diff --git a/clang-tools-extra/clangd/index/Index.h b/clang-tools-extra/clangd/index/Index.h index 771261a8ac6..c1778e18932 100644 --- a/clang-tools-extra/clangd/index/Index.h +++ b/clang-tools-extra/clangd/index/Index.h @@ -242,7 +242,6 @@ struct Symbol { /// any definition. llvm::SmallVector<IncludeHeaderWithReferences, 1> IncludeHeaders; - // FIXME: add all occurrences support. // FIXME: add extra fields for index scoring signals. }; llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, const Symbol &S); @@ -309,109 +308,86 @@ private: std::vector<Symbol> Symbols; // Sorted by SymbolID to allow lookup. }; -// Describes the kind of a symbol occurrence. +// Describes the kind of a cross-reference. // // This is a bitfield which can be combined from different kinds. -enum class SymbolOccurrenceKind : uint8_t { +enum class RefKind : uint8_t { Unknown = 0, Declaration = static_cast<uint8_t>(index::SymbolRole::Declaration), Definition = static_cast<uint8_t>(index::SymbolRole::Definition), Reference = static_cast<uint8_t>(index::SymbolRole::Reference), + All = Declaration | Definition | Reference, }; -inline SymbolOccurrenceKind operator|(SymbolOccurrenceKind L, - SymbolOccurrenceKind R) { - return static_cast<SymbolOccurrenceKind>(static_cast<uint8_t>(L) | - static_cast<uint8_t>(R)); +inline RefKind operator|(RefKind L, RefKind R) { + return static_cast<RefKind>(static_cast<uint8_t>(L) | + static_cast<uint8_t>(R)); } -inline SymbolOccurrenceKind &operator|=(SymbolOccurrenceKind &L, - SymbolOccurrenceKind R) { - return L = L | R; +inline RefKind &operator|=(RefKind &L, RefKind R) { return L = L | R; } +inline RefKind operator&(RefKind A, RefKind B) { + return static_cast<RefKind>(static_cast<uint8_t>(A) & + static_cast<uint8_t>(B)); } -inline SymbolOccurrenceKind operator&(SymbolOccurrenceKind A, - SymbolOccurrenceKind B) { - return static_cast<SymbolOccurrenceKind>(static_cast<uint8_t>(A) & - static_cast<uint8_t>(B)); -} -llvm::raw_ostream &operator<<(llvm::raw_ostream &, SymbolOccurrenceKind); -static const SymbolOccurrenceKind AllOccurrenceKinds = - SymbolOccurrenceKind::Declaration | SymbolOccurrenceKind::Definition | - SymbolOccurrenceKind::Reference; +llvm::raw_ostream &operator<<(llvm::raw_ostream &, RefKind); -// Represents a symbol occurrence in the source file. It could be a -// declaration/definition/reference occurrence. +// Represents a symbol occurrence in the source file. +// Despite the name, it could be a declaration/definition/reference. // // WARNING: Location does not own the underlying data - Copies are shallow. -struct SymbolOccurrence { - // The location of the occurrence. +struct Ref { + // The source location where the symbol is named. SymbolLocation Location; - SymbolOccurrenceKind Kind = SymbolOccurrenceKind::Unknown; + RefKind Kind = RefKind::Unknown; }; -inline bool operator<(const SymbolOccurrence &L, const SymbolOccurrence &R) { +inline bool operator<(const Ref &L, const Ref &R) { return std::tie(L.Location, L.Kind) < std::tie(R.Location, R.Kind); } -inline bool operator==(const SymbolOccurrence &L, const SymbolOccurrence &R) { +inline bool operator==(const Ref &L, const Ref &R) { return std::tie(L.Location, L.Kind) == std::tie(R.Location, R.Kind); } -llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, - const SymbolOccurrence &Occurrence); +llvm::raw_ostream &operator<<(llvm::raw_ostream &, const Ref &); -// An efficient structure of storing large set of symbol occurrences in memory. +// An efficient structure of storing large set of symbol references in memory. // Filenames are deduplicated. -class SymbolOccurrenceSlab { +class RefSlab { public: - using const_iterator = - llvm::DenseMap<SymbolID, std::vector<SymbolOccurrence>>::const_iterator; + using value_type = std::pair<SymbolID, llvm::ArrayRef<Ref>>; + using const_iterator = std::vector<value_type>::const_iterator; using iterator = const_iterator; - SymbolOccurrenceSlab() : UniqueStrings(Arena) {} - - static SymbolOccurrenceSlab createEmpty() { - SymbolOccurrenceSlab Empty; - Empty.freeze(); - return Empty; - } - - // Define move semantics for the slab, allowing assignment from an rvalue. - // Implicit move assignment is deleted by the compiler because - // StringSaver has a reference type member. - SymbolOccurrenceSlab(SymbolOccurrenceSlab &&Slab) = default; - SymbolOccurrenceSlab &operator=(SymbolOccurrenceSlab &&RHS) { - assert(RHS.Frozen && - "SymbolOcucrrenceSlab must be frozen when move assigned!"); - Arena = std::move(RHS.Arena); - Frozen = true; - Occurrences = std::move(RHS.Occurrences); - return *this; - } + RefSlab() = default; + RefSlab(RefSlab &&Slab) = default; + RefSlab &operator=(RefSlab &&RHS) = default; - const_iterator begin() const { return Occurrences.begin(); } - const_iterator end() const { return Occurrences.end(); } + const_iterator begin() const { return Refs.begin(); } + const_iterator end() const { return Refs.end(); } + size_t size() const { return Refs.size(); } size_t bytes() const { - return sizeof(*this) + Arena.getTotalMemory() + Occurrences.getMemorySize(); + return sizeof(*this) + Arena.getTotalMemory() + + sizeof(value_type) * Refs.size(); } - size_t size() const { return Occurrences.size(); } - - // Adds a symbol occurrence. - // This is a deep copy: underlying FileURI will be owned by the slab. - void insert(const SymbolID &SymID, const SymbolOccurrence &Occurrence); - - llvm::ArrayRef<SymbolOccurrence> find(const SymbolID &ID) const { - assert(Frozen && "SymbolOccurrenceSlab must be frozen before looking up!"); - auto It = Occurrences.find(ID); - if (It == Occurrences.end()) - return {}; - return It->second; - } + // RefSlab::Builder is a mutable container that can 'freeze' to RefSlab. + class Builder { + public: + Builder() : UniqueStrings(Arena) {} + // Adds a ref to the slab. Deep copy: Strings will be owned by the slab. + void insert(const SymbolID &ID, const Ref &S); + // Consumes the builder to finalize the slab. + RefSlab build() &&; - void freeze(); + private: + llvm::BumpPtrAllocator Arena; + llvm::UniqueStringSaver UniqueStrings; // Contents on the arena. + llvm::DenseMap<SymbolID, std::vector<Ref>> Refs; + }; private: - bool Frozen = false; + RefSlab(std::vector<value_type> Refs, llvm::BumpPtrAllocator Arena) + : Arena(std::move(Arena)), Refs(std::move(Refs)) {} + llvm::BumpPtrAllocator Arena; - llvm::UniqueStringSaver UniqueStrings; - llvm::DenseMap<SymbolID, std::vector<SymbolOccurrence>> Occurrences; + std::vector<value_type> Refs; }; struct FuzzyFindRequest { @@ -447,9 +423,9 @@ struct LookupRequest { llvm::DenseSet<SymbolID> IDs; }; -struct OccurrencesRequest { +struct RefsRequest { llvm::DenseSet<SymbolID> IDs; - SymbolOccurrenceKind Filter = AllOccurrenceKinds; + RefKind Filter = RefKind::All; }; /// Interface for symbol indexes that can be used for searching or @@ -474,15 +450,13 @@ public: lookup(const LookupRequest &Req, llvm::function_ref<void(const Symbol &)> Callback) const = 0; - /// CrossReference finds all symbol occurrences (e.g. references, - /// declarations, definitions) and applies \p Callback on each result. - /// - /// Results are returned in arbitrary order. + /// Finds all occurrences (e.g. references, declarations, definitions) of a + /// symbol and applies \p Callback on each result. /// + /// Results should be returned in arbitrary order. /// The returned result must be deep-copied if it's used outside Callback. - virtual void findOccurrences( - const OccurrencesRequest &Req, - llvm::function_ref<void(const SymbolOccurrence &)> Callback) const = 0; + virtual void refs(const RefsRequest &Req, + llvm::function_ref<void(const Ref &)> Callback) const = 0; /// Returns estimated size of index (in bytes). // FIXME(kbobyrev): Currently, this only returns the size of index itself @@ -505,9 +479,8 @@ public: llvm::function_ref<void(const Symbol &)>) const override; void lookup(const LookupRequest &, llvm::function_ref<void(const Symbol &)>) const override; - void findOccurrences( - const OccurrencesRequest &, - llvm::function_ref<void(const SymbolOccurrence &)>) const override; + void refs(const RefsRequest &, + llvm::function_ref<void(const Ref &)>) const override; size_t estimateMemoryUsage() const override; private: diff --git a/clang-tools-extra/clangd/index/MemIndex.cpp b/clang-tools-extra/clangd/index/MemIndex.cpp index 43629f4861d..2a7cd601bdb 100644 --- a/clang-tools-extra/clangd/index/MemIndex.cpp +++ b/clang-tools-extra/clangd/index/MemIndex.cpp @@ -15,16 +15,9 @@ namespace clang { namespace clangd { -std::unique_ptr<SymbolIndex> MemIndex::build(SymbolSlab Slab, - SymbolOccurrenceSlab Occurrences) { - 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<MemIndex>(Data.first, std::move(M), std::move(Data)); +std::unique_ptr<SymbolIndex> MemIndex::build(SymbolSlab Slab, RefSlab Refs) { + auto Data = std::make_pair(std::move(Slab), std::move(Refs)); + return llvm::make_unique<MemIndex>(Data.first, Data.second, std::move(Data)); } bool MemIndex::fuzzyFind( @@ -67,17 +60,15 @@ void MemIndex::lookup(const LookupRequest &Req, } } -void MemIndex::findOccurrences( - const OccurrencesRequest &Req, - llvm::function_ref<void(const SymbolOccurrence &)> Callback) const { +void MemIndex::refs(const RefsRequest &Req, + llvm::function_ref<void(const Ref &)> Callback) const { for (const auto &ReqID : Req.IDs) { - auto FoundOccurrences = Occurrences.find(ReqID); - if (FoundOccurrences == Occurrences.end()) + auto SymRefs = Refs.find(ReqID); + if (SymRefs == Refs.end()) continue; - for (const auto *O : FoundOccurrences->second) { - if (static_cast<int>(Req.Filter & O->Kind)) - Callback(*O); - } + for (const auto &O : SymRefs->second) + if (static_cast<int>(Req.Filter & O.Kind)) + Callback(O); } } diff --git a/clang-tools-extra/clangd/index/MemIndex.h b/clang-tools-extra/clangd/index/MemIndex.h index 3f1dcdfed2f..add45896249 100644 --- a/clang-tools-extra/clangd/index/MemIndex.h +++ b/clang-tools-extra/clangd/index/MemIndex.h @@ -19,31 +19,26 @@ namespace clangd { /// 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. - /// The map doesn't own occurrence objects. - using OccurrenceMap = - llvm::DenseMap<SymbolID, std::vector<const SymbolOccurrence *>>; - MemIndex() = default; - // All symbols and occurrences must outlive this index. - // TODO: find a better type for Occurrences here. - template <typename SymbolRange> - MemIndex(SymbolRange &&Symbols, OccurrenceMap Occurrences) - : Occurrences(std::move(Occurrences)) { + // All symbols and refs must outlive this index. + template <typename SymbolRange, typename RefRange> + MemIndex(SymbolRange &&Symbols, RefRange &&Refs) { for (const Symbol &S : Symbols) Index[S.ID] = &S; + for (const std::pair<SymbolID, llvm::ArrayRef<Ref>> &R : Refs) + this->Refs.try_emplace(R.first, R.second.begin(), R.second.end()); } // Symbols are owned by BackingData, Index takes ownership. - template <typename Range, typename Payload> - MemIndex(Range &&Symbols, OccurrenceMap Occurrences, Payload &&BackingData) - : MemIndex(std::forward<Range>(Symbols), std::move(Occurrences)) { + template <typename SymbolRange, typename RefRange, typename Payload> + MemIndex(SymbolRange &&Symbols, RefRange &&Refs, Payload &&BackingData) + : MemIndex(std::forward<SymbolRange>(Symbols), + std::forward<RefRange>(Refs)) { KeepAlive = std::shared_ptr<void>( std::make_shared<Payload>(std::move(BackingData)), nullptr); } - /// Builds an index from a slab. The index takes ownership of the data. - static std::unique_ptr<SymbolIndex> build(SymbolSlab Slab, - SymbolOccurrenceSlab Occurrences); + /// Builds an index from slabs. The index takes ownership of the data. + static std::unique_ptr<SymbolIndex> build(SymbolSlab Symbols, RefSlab Refs); bool fuzzyFind(const FuzzyFindRequest &Req, @@ -52,17 +47,16 @@ public: void lookup(const LookupRequest &Req, llvm::function_ref<void(const Symbol &)> Callback) const override; - void findOccurrences(const OccurrencesRequest &Req, - llvm::function_ref<void(const SymbolOccurrence &)> - Callback) const override; + void refs(const RefsRequest &Req, + llvm::function_ref<void(const Ref &)> Callback) const override; size_t estimateMemoryUsage() const override; private: // Index is a set of symbols that are deduplicated by symbol IDs. llvm::DenseMap<SymbolID, const Symbol *> Index; - // A map from symbol ID to symbol occurrences, support query by IDs. - OccurrenceMap Occurrences; + // A map from symbol ID to symbol refs, support query by IDs. + llvm::DenseMap<SymbolID, llvm::ArrayRef<Ref>> Refs; std::shared_ptr<void> KeepAlive; // poor man's move-only std::any }; diff --git a/clang-tools-extra/clangd/index/Merge.cpp b/clang-tools-extra/clangd/index/Merge.cpp index 6c384bfd6a4..5f79cffa57d 100644 --- a/clang-tools-extra/clangd/index/Merge.cpp +++ b/clang-tools-extra/clangd/index/Merge.cpp @@ -7,12 +7,12 @@ // //===----------------------------------------------------------------------===// -#include <set> - #include "Merge.h" #include "../Logger.h" #include "llvm/ADT/STLExtras.h" +#include "llvm/ADT/StringSet.h" #include "llvm/Support/raw_ostream.h" +#include <set> namespace clang { namespace clangd { @@ -78,28 +78,24 @@ class MergedIndex : public SymbolIndex { Callback(*Sym); } - void findOccurrences(const OccurrencesRequest &Req, - llvm::function_ref<void(const SymbolOccurrence &)> - Callback) const override { - // We don't want duplicated occurrences from the static/dynamic indexes, - // and we can't reliably duplicate them because occurrence offsets may - // differ slightly. - // We consider the dynamic index authoritative and report all its - // occurrences, and only report static index occurrences from other files. + void refs(const RefsRequest &Req, + llvm::function_ref<void(const Ref &)> Callback) const override { + // We don't want duplicated refs from the static/dynamic indexes, + // and we can't reliably duplicate them because offsets may differ slightly. + // We consider the dynamic index authoritative and report all its refs, + // and only report static index refs from other files. // // FIXME: The heuristic fails if the dynamic index contains a file, but all - // occurrences were removed (we will report stale ones from the static - // index). Ultimately we should explicit check which index has the file - // instead. - std::set<std::string> DynamicIndexFileURIs; - Dynamic->findOccurrences(Req, [&](const SymbolOccurrence &O) { + // refs were removed (we will report stale ones from the static index). + // Ultimately we should explicit check which index has the file instead. + llvm::StringSet<> DynamicIndexFileURIs; + Dynamic->refs(Req, [&](const Ref &O) { DynamicIndexFileURIs.insert(O.Location.FileURI); Callback(O); }); - Static->findOccurrences(Req, [&](const SymbolOccurrence &O) { - if (DynamicIndexFileURIs.count(O.Location.FileURI)) - return; - Callback(O); + Static->refs(Req, [&](const Ref &O) { + if (!DynamicIndexFileURIs.count(O.Location.FileURI)) + Callback(O); }); } diff --git a/clang-tools-extra/clangd/index/Merge.h b/clang-tools-extra/clangd/index/Merge.h index acf9ce1d221..ca496c2bf22 100644 --- a/clang-tools-extra/clangd/index/Merge.h +++ b/clang-tools-extra/clangd/index/Merge.h @@ -26,8 +26,8 @@ Symbol mergeSymbol(const Symbol &L, const Symbol &R); // The returned index attempts to combine results, and avoid duplicates. // // FIXME: We don't have a mechanism in Index to track deleted symbols and -// occurrences in dirty files, so the merged index may return stale symbols -// and occurrences from Static index. +// refs in dirty files, so the merged index may return stale symbols +// and refs from Static index. std::unique_ptr<SymbolIndex> mergeIndex(const SymbolIndex *Dynamic, const SymbolIndex *Static); diff --git a/clang-tools-extra/clangd/index/SymbolCollector.cpp b/clang-tools-extra/clangd/index/SymbolCollector.cpp index 912c6508597..7a83243f8f0 100644 --- a/clang-tools-extra/clangd/index/SymbolCollector.cpp +++ b/clang-tools-extra/clangd/index/SymbolCollector.cpp @@ -231,9 +231,8 @@ bool isPreferredDeclaration(const NamedDecl &ND, index::SymbolRoleSet Roles) { match(decl(isExpansionInMainFile()), ND, ND.getASTContext()).empty(); } -SymbolOccurrenceKind toOccurrenceKind(index::SymbolRoleSet Roles) { - return static_cast<SymbolOccurrenceKind>( - static_cast<unsigned>(AllOccurrenceKinds) & Roles); +RefKind toRefKind(index::SymbolRoleSet Roles) { + return static_cast<RefKind>(static_cast<unsigned>(RefKind::All) & Roles); } } // namespace @@ -326,9 +325,9 @@ bool SymbolCollector::handleDeclOccurence( SM.getFileID(SpellingLoc) == SM.getMainFileID()) ReferencedDecls.insert(ND); - if ((static_cast<unsigned>(Opts.OccurrenceFilter) & Roles) && + if ((static_cast<unsigned>(Opts.RefFilter) & Roles) && SM.getFileID(SpellingLoc) == SM.getMainFileID()) - DeclOccurrences[ND].emplace_back(SpellingLoc, Roles); + DeclRefs[ND].emplace_back(SpellingLoc, Roles); // Don't continue indexing if this is a mere reference. if (!(Roles & static_cast<unsigned>(index::SymbolRole::Declaration) || @@ -459,18 +458,18 @@ void SymbolCollector::finish() { if (auto MainFileURI = toURI(SM, MainFileEntry->getName(), Opts)) { std::string MainURI = *MainFileURI; - for (const auto &It : DeclOccurrences) { + for (const auto &It : DeclRefs) { if (auto ID = getSymbolID(It.first)) { if (Symbols.find(*ID)) { for (const auto &LocAndRole : It.second) { - SymbolOccurrence Occurrence; + Ref R; auto Range = getTokenRange(LocAndRole.first, SM, ASTCtx->getLangOpts()); - Occurrence.Location.Start = Range.first; - Occurrence.Location.End = Range.second; - Occurrence.Location.FileURI = MainURI; - Occurrence.Kind = toOccurrenceKind(LocAndRole.second); - SymbolOccurrences.insert(*ID, Occurrence); + R.Location.Start = Range.first; + R.Location.End = Range.second; + R.Location.FileURI = MainURI; + R.Kind = toRefKind(LocAndRole.second); + Refs.insert(*ID, R); } } } @@ -481,7 +480,7 @@ void SymbolCollector::finish() { ReferencedDecls.clear(); ReferencedMacros.clear(); - DeclOccurrences.clear(); + DeclRefs.clear(); } const Symbol *SymbolCollector::addDeclaration(const NamedDecl &ND, diff --git a/clang-tools-extra/clangd/index/SymbolCollector.h b/clang-tools-extra/clangd/index/SymbolCollector.h index ab88c066dfa..db0e3074ecf 100644 --- a/clang-tools-extra/clangd/index/SymbolCollector.h +++ b/clang-tools-extra/clangd/index/SymbolCollector.h @@ -52,10 +52,9 @@ public: const CanonicalIncludes *Includes = nullptr; // Populate the Symbol.References field. bool CountReferences = false; - /// The symbol occurrence kind that will be collected. - /// If not set (Unknown), SymbolCollector will not collect any symbol - /// occurrences. - SymbolOccurrenceKind OccurrenceFilter = SymbolOccurrenceKind::Unknown; + /// The symbol ref kinds that will be collected. + /// If not set, SymbolCollector will not collect refs. + RefKind RefFilter = RefKind::Unknown; // Every symbol collected will be stamped with this origin. SymbolOrigin Origin = SymbolOrigin::Unknown; /// Collect macros. @@ -89,11 +88,7 @@ public: SourceLocation Loc) override; SymbolSlab takeSymbols() { return std::move(Symbols).build(); } - - SymbolOccurrenceSlab takeOccurrences() { - SymbolOccurrences.freeze(); - return std::move(SymbolOccurrences); - } + RefSlab takeRefs() { return std::move(Refs).build(); } void finish() override; @@ -103,21 +98,20 @@ private: // All Symbols collected from the AST. SymbolSlab::Builder Symbols; - // All symbol occurrences collected from the AST. - // Only symbols declared in preamble (from #include) and references from the + // All refs collected from the AST. + // Only symbols declared in preamble (from #include) and referenced from the // main file will be included. - SymbolOccurrenceSlab SymbolOccurrences; + RefSlab::Builder Refs; ASTContext *ASTCtx; std::shared_ptr<Preprocessor> PP; std::shared_ptr<GlobalCodeCompletionAllocator> CompletionAllocator; std::unique_ptr<CodeCompletionTUInfo> CompletionTUInfo; Options Opts; - using DeclOccurrence = std::pair<SourceLocation, index::SymbolRoleSet>; + using DeclRef = std::pair<SourceLocation, index::SymbolRoleSet>; // Symbols referenced from the current TU, flushed on finish(). llvm::DenseSet<const NamedDecl *> ReferencedDecls; llvm::DenseSet<const IdentifierInfo *> ReferencedMacros; - llvm::DenseMap<const NamedDecl *, std::vector<DeclOccurrence>> - DeclOccurrences; + llvm::DenseMap<const NamedDecl *, std::vector<DeclRef>> DeclRefs; // Maps canonical declaration provided by clang to canonical declaration for // an index symbol, if clangd prefers a different declaration than that // provided by clang. For example, friend declaration might be considered diff --git a/clang-tools-extra/clangd/index/dex/DexIndex.cpp b/clang-tools-extra/clangd/index/dex/DexIndex.cpp index 3275cb7bbc9..ed1f60b9b4a 100644 --- a/clang-tools-extra/clangd/index/dex/DexIndex.cpp +++ b/clang-tools-extra/clangd/index/dex/DexIndex.cpp @@ -144,10 +144,9 @@ void DexIndex::lookup(const LookupRequest &Req, } } -void DexIndex::findOccurrences( - const OccurrencesRequest &Req, - llvm::function_ref<void(const SymbolOccurrence &)> Callback) const { - log("findOccurrences is not implemented."); +void DexIndex::refs(const RefsRequest &Req, + llvm::function_ref<void(const Ref &)> Callback) const { + log("refs is not implemented."); } size_t DexIndex::estimateMemoryUsage() const { diff --git a/clang-tools-extra/clangd/index/dex/DexIndex.h b/clang-tools-extra/clangd/index/dex/DexIndex.h index ad379136b8b..3244e62ec26 100644 --- a/clang-tools-extra/clangd/index/dex/DexIndex.h +++ b/clang-tools-extra/clangd/index/dex/DexIndex.h @@ -64,9 +64,8 @@ public: void lookup(const LookupRequest &Req, llvm::function_ref<void(const Symbol &)> Callback) const override; - void findOccurrences(const OccurrencesRequest &Req, - llvm::function_ref<void(const SymbolOccurrence &)> - Callback) const override; + void refs(const RefsRequest &Req, + llvm::function_ref<void(const Ref &)> Callback) const override; size_t estimateMemoryUsage() const override; diff --git a/clang-tools-extra/clangd/tool/ClangdMain.cpp b/clang-tools-extra/clangd/tool/ClangdMain.cpp index cf5c7fac015..c9ceb9aa859 100644 --- a/clang-tools-extra/clangd/tool/ClangdMain.cpp +++ b/clang-tools-extra/clangd/tool/ClangdMain.cpp @@ -54,8 +54,7 @@ std::unique_ptr<SymbolIndex> buildStaticIndex(llvm::StringRef YamlSymbolFile) { SymsBuilder.insert(Sym); return UseDex ? dex::DexIndex::build(std::move(SymsBuilder).build()) - : MemIndex::build(std::move(SymsBuilder).build(), - SymbolOccurrenceSlab::createEmpty()); + : MemIndex::build(std::move(SymsBuilder).build(), RefSlab()); } } // namespace diff --git a/clang-tools-extra/unittests/clangd/CodeCompleteTests.cpp b/clang-tools-extra/unittests/clangd/CodeCompleteTests.cpp index ca2f449bfb0..3a6fe9ba3af 100644 --- a/clang-tools-extra/unittests/clangd/CodeCompleteTests.cpp +++ b/clang-tools-extra/unittests/clangd/CodeCompleteTests.cpp @@ -82,8 +82,7 @@ std::unique_ptr<SymbolIndex> memIndex(std::vector<Symbol> Symbols) { SymbolSlab::Builder Slab; for (const auto &Sym : Symbols) Slab.insert(Sym); - return MemIndex::build(std::move(Slab).build(), - SymbolOccurrenceSlab::createEmpty()); + return MemIndex::build(std::move(Slab).build(), RefSlab()); } CodeCompleteResult completions(ClangdServer &Server, StringRef TestCode, @@ -974,9 +973,8 @@ public: void lookup(const LookupRequest &, llvm::function_ref<void(const Symbol &)>) const override {} - void findOccurrences(const OccurrencesRequest &Req, - llvm::function_ref<void(const SymbolOccurrence &)> - Callback) const override {} + void refs(const RefsRequest &, + llvm::function_ref<void(const Ref &)>) const override {} // This is incorrect, but IndexRequestCollector is not an actual index and it // isn't used in production code. diff --git a/clang-tools-extra/unittests/clangd/FileIndexTests.cpp b/clang-tools-extra/unittests/clangd/FileIndexTests.cpp index debca6ac6df..096ccd9e647 100644 --- a/clang-tools-extra/unittests/clangd/FileIndexTests.cpp +++ b/clang-tools-extra/unittests/clangd/FileIndexTests.cpp @@ -19,10 +19,13 @@ #include "clang/Tooling/CompilationDatabase.h" #include "gtest/gtest.h" -using testing::UnorderedElementsAre; +using testing::_; using testing::AllOf; +using testing::ElementsAre; +using testing::Pair; +using testing::UnorderedElementsAre; -MATCHER_P(OccurrenceRange, Range, "") { +MATCHER_P(RefRange, Range, "") { return std::tie(arg.Location.Start.Line, arg.Location.Start.Column, arg.Location.End.Line, arg.Location.End.Column) == std::tie(Range.start.line, Range.start.character, Range.end.line, @@ -32,8 +35,11 @@ MATCHER_P(FileURI, F, "") { return arg.Location.FileURI == F; } namespace clang { namespace clangd { - namespace { +testing::Matcher<const RefSlab &> +RefsAre(std::vector<testing::Matcher<Ref>> Matchers) { + return ElementsAre(testing::Pair(_, UnorderedElementsAreArray(Matchers))); +} Symbol symbol(llvm::StringRef ID) { Symbol Sym; @@ -49,14 +55,13 @@ std::unique_ptr<SymbolSlab> numSlab(int Begin, int End) { return llvm::make_unique<SymbolSlab>(std::move(Slab).build()); } -std::unique_ptr<SymbolOccurrenceSlab> occurrenceSlab(const SymbolID &ID, - llvm::StringRef Path) { - auto Slab = llvm::make_unique<SymbolOccurrenceSlab>(); - SymbolOccurrence Occurrence; - Occurrence.Location.FileURI = Path; - Occurrence.Kind = SymbolOccurrenceKind::Reference; - Slab->insert(ID, Occurrence); - return Slab; +std::unique_ptr<RefSlab> refSlab(const SymbolID &ID, llvm::StringRef Path) { + RefSlab::Builder Slab; + Ref R; + R.Location.FileURI = Path; + R.Kind = RefKind::Reference; + Slab.insert(ID, R); + return llvm::make_unique<RefSlab>(std::move(Slab).build()); } std::vector<std::string> getSymbolNames(const SymbolIndex &I, @@ -68,37 +73,29 @@ std::vector<std::string> getSymbolNames(const SymbolIndex &I, return Names; } -std::vector<std::string> getOccurrencePaths(const SymbolIndex &I, SymbolID ID) { - OccurrencesRequest Req; +RefSlab getRefs(const SymbolIndex &I, SymbolID ID) { + RefsRequest Req; Req.IDs = {ID}; - std::vector<std::string> Paths; - I.findOccurrences(Req, [&](const SymbolOccurrence &S) { - Paths.push_back(S.Location.FileURI); - }); - return Paths; -} - -std::unique_ptr<SymbolOccurrenceSlab> emptyOccurrence() { - auto EmptySlab = llvm::make_unique<SymbolOccurrenceSlab>(); - EmptySlab->freeze(); - return EmptySlab; + RefSlab::Builder Slab; + I.refs(Req, [&](const Ref &S) { Slab.insert(ID, S); }); + return std::move(Slab).build(); } TEST(FileSymbolsTest, UpdateAndGet) { FileSymbols FS; EXPECT_THAT(getSymbolNames(*FS.buildMemIndex()), UnorderedElementsAre()); - FS.update("f1", numSlab(1, 3), occurrenceSlab(SymbolID("1"), "f1.cc")); + FS.update("f1", numSlab(1, 3), refSlab(SymbolID("1"), "f1.cc")); EXPECT_THAT(getSymbolNames(*FS.buildMemIndex()), UnorderedElementsAre("1", "2", "3")); - EXPECT_THAT(getOccurrencePaths(*FS.buildMemIndex(), SymbolID("1")), - UnorderedElementsAre("f1.cc")); + EXPECT_THAT(getRefs(*FS.buildMemIndex(), SymbolID("1")), + RefsAre({FileURI("f1.cc")})); } TEST(FileSymbolsTest, Overlap) { FileSymbols FS; - FS.update("f1", numSlab(1, 3), emptyOccurrence()); - FS.update("f2", numSlab(3, 5), emptyOccurrence()); + FS.update("f1", numSlab(1, 3), nullptr); + FS.update("f2", numSlab(3, 5), nullptr); EXPECT_THAT(getSymbolNames(*FS.buildMemIndex()), UnorderedElementsAre("1", "2", "3", "4", "5")); } @@ -107,19 +104,19 @@ TEST(FileSymbolsTest, SnapshotAliveAfterRemove) { FileSymbols FS; SymbolID ID("1"); - FS.update("f1", numSlab(1, 3), occurrenceSlab(ID, "f1.cc")); + FS.update("f1", numSlab(1, 3), refSlab(ID, "f1.cc")); auto Symbols = FS.buildMemIndex(); EXPECT_THAT(getSymbolNames(*Symbols), UnorderedElementsAre("1", "2", "3")); - EXPECT_THAT(getOccurrencePaths(*Symbols, ID), UnorderedElementsAre("f1.cc")); + EXPECT_THAT(getRefs(*Symbols, ID), RefsAre({FileURI("f1.cc")})); FS.update("f1", nullptr, nullptr); auto Empty = FS.buildMemIndex(); EXPECT_THAT(getSymbolNames(*Empty), UnorderedElementsAre()); - EXPECT_THAT(getOccurrencePaths(*Empty, ID), UnorderedElementsAre()); + EXPECT_THAT(getRefs(*Empty, ID), ElementsAre()); EXPECT_THAT(getSymbolNames(*Symbols), UnorderedElementsAre("1", "2", "3")); - EXPECT_THAT(getOccurrencePaths(*Symbols, ID), UnorderedElementsAre("f1.cc")); + EXPECT_THAT(getRefs(*Symbols, ID), RefsAre({FileURI("f1.cc")})); } std::vector<std::string> match(const SymbolIndex &I, @@ -314,7 +311,7 @@ TEST(FileIndexTest, RebuildWithPreamble) { UnorderedElementsAre("ns_in_header", "ns_in_header::func_in_header")); } -TEST(FileIndexTest, Occurrences) { +TEST(FileIndexTest, Refs) { const char *HeaderCode = "class Foo {};"; Annotations MainCode(R"cpp( void f() { @@ -325,11 +322,8 @@ TEST(FileIndexTest, Occurrences) { auto Foo = findSymbol(TestTU::withHeaderCode(HeaderCode).headerSymbols(), "Foo"); - OccurrencesRequest Request; + RefsRequest Request; Request.IDs = {Foo.ID}; - Request.Filter = SymbolOccurrenceKind::Declaration | - SymbolOccurrenceKind::Definition | - SymbolOccurrenceKind::Reference; FileIndex Index(/*URISchemes*/ {"unittest"}); // Add test.cc @@ -349,15 +343,11 @@ TEST(FileIndexTest, Occurrences) { Index.update(Test2.Filename, &AST.getASTContext(), AST.getPreprocessorPtr(), AST.getLocalTopLevelDecls()); - std::vector<SymbolOccurrence> Results; - Index.findOccurrences( - Request, [&Results](const SymbolOccurrence &O) { Results.push_back(O); }); - - EXPECT_THAT(Results, - UnorderedElementsAre(AllOf(OccurrenceRange(MainCode.range("foo")), - FileURI("unittest:///test.cc")), - AllOf(OccurrenceRange(MainCode.range("foo")), - FileURI("unittest:///test2.cc")))); + EXPECT_THAT(getRefs(Index, Foo.ID), + RefsAre({AllOf(RefRange(MainCode.range("foo")), + FileURI("unittest:///test.cc")), + AllOf(RefRange(MainCode.range("foo")), + FileURI("unittest:///test2.cc"))})); } } // namespace diff --git a/clang-tools-extra/unittests/clangd/IndexTests.cpp b/clang-tools-extra/unittests/clangd/IndexTests.cpp index 181475f2d94..7742e520197 100644 --- a/clang-tools-extra/unittests/clangd/IndexTests.cpp +++ b/clang-tools-extra/unittests/clangd/IndexTests.cpp @@ -17,8 +17,10 @@ #include "index/Merge.h" #include "gtest/gtest.h" +using testing::_; using testing::AllOf; using testing::ElementsAre; +using testing::Pair; using testing::Pointee; using testing::UnorderedElementsAre; using namespace llvm; @@ -28,7 +30,7 @@ namespace clangd { namespace { MATCHER_P(Named, N, "") { return arg.Name == N; } -MATCHER_P(OccurrenceRange, Range, "") { +MATCHER_P(RefRange, Range, "") { return std::tie(arg.Location.Start.Line, arg.Location.Start.Column, arg.Location.End.Line, arg.Location.End.Column) == std::tie(Range.start.line, Range.start.character, Range.end.line, @@ -56,8 +58,8 @@ TEST(SwapIndexTest, OldIndexRecycled) { auto Token = std::make_shared<int>(); std::weak_ptr<int> WeakToken = Token; - SwapIndex S(llvm::make_unique<MemIndex>( - SymbolSlab(), MemIndex::OccurrenceMap(), std::move(Token))); + SwapIndex S( + llvm::make_unique<MemIndex>(SymbolSlab(), RefSlab(), std::move(Token))); EXPECT_FALSE(WeakToken.expired()); // Current MemIndex keeps it alive. S.reset(llvm::make_unique<MemIndex>()); // Now the MemIndex is destroyed. EXPECT_TRUE(WeakToken.expired()); // So the token is too. @@ -68,12 +70,12 @@ TEST(MemIndexTest, MemIndexDeduplicate) { symbol("2") /* duplicate */}; FuzzyFindRequest Req; Req.Query = "2"; - MemIndex I(Symbols, MemIndex::OccurrenceMap()); + MemIndex I(Symbols, RefSlab()); EXPECT_THAT(match(I, Req), ElementsAre("2")); } TEST(MemIndexTest, MemIndexLimitedNumMatches) { - auto I = MemIndex::build(generateNumSymbols(0, 100), SymbolOccurrenceSlab()); + auto I = MemIndex::build(generateNumSymbols(0, 100), RefSlab()); FuzzyFindRequest Req; Req.Query = "5"; Req.MaxCandidateCount = 3; @@ -86,7 +88,7 @@ TEST(MemIndexTest, MemIndexLimitedNumMatches) { TEST(MemIndexTest, FuzzyMatch) { auto I = MemIndex::build( generateSymbols({"LaughingOutLoud", "LionPopulation", "LittleOldLady"}), - SymbolOccurrenceSlab()); + RefSlab()); FuzzyFindRequest Req; Req.Query = "lol"; Req.MaxCandidateCount = 2; @@ -95,16 +97,16 @@ TEST(MemIndexTest, FuzzyMatch) { } TEST(MemIndexTest, MatchQualifiedNamesWithoutSpecificScope) { - auto I = MemIndex::build(generateSymbols({"a::y1", "b::y2", "y3"}), - SymbolOccurrenceSlab()); + auto I = + MemIndex::build(generateSymbols({"a::y1", "b::y2", "y3"}), RefSlab()); FuzzyFindRequest Req; Req.Query = "y"; EXPECT_THAT(match(*I, Req), UnorderedElementsAre("a::y1", "b::y2", "y3")); } TEST(MemIndexTest, MatchQualifiedNamesWithGlobalScope) { - auto I = MemIndex::build(generateSymbols({"a::y1", "b::y2", "y3"}), - SymbolOccurrenceSlab()); + auto I = + MemIndex::build(generateSymbols({"a::y1", "b::y2", "y3"}), RefSlab()); FuzzyFindRequest Req; Req.Query = "y"; Req.Scopes = {""}; @@ -113,8 +115,7 @@ TEST(MemIndexTest, MatchQualifiedNamesWithGlobalScope) { TEST(MemIndexTest, MatchQualifiedNamesWithOneScope) { auto I = MemIndex::build( - generateSymbols({"a::y1", "a::y2", "a::x", "b::y2", "y3"}), - SymbolOccurrenceSlab()); + generateSymbols({"a::y1", "a::y2", "a::x", "b::y2", "y3"}), RefSlab()); FuzzyFindRequest Req; Req.Query = "y"; Req.Scopes = {"a::"}; @@ -123,8 +124,7 @@ TEST(MemIndexTest, MatchQualifiedNamesWithOneScope) { TEST(MemIndexTest, MatchQualifiedNamesWithMultipleScopes) { auto I = MemIndex::build( - generateSymbols({"a::y1", "a::y2", "a::x", "b::y3", "y3"}), - SymbolOccurrenceSlab()); + generateSymbols({"a::y1", "a::y2", "a::x", "b::y3", "y3"}), RefSlab()); FuzzyFindRequest Req; Req.Query = "y"; Req.Scopes = {"a::", "b::"}; @@ -132,8 +132,7 @@ TEST(MemIndexTest, MatchQualifiedNamesWithMultipleScopes) { } TEST(MemIndexTest, NoMatchNestedScopes) { - auto I = MemIndex::build(generateSymbols({"a::y1", "a::b::y2"}), - SymbolOccurrenceSlab()); + auto I = MemIndex::build(generateSymbols({"a::y1", "a::b::y2"}), RefSlab()); FuzzyFindRequest Req; Req.Query = "y"; Req.Scopes = {"a::"}; @@ -141,8 +140,7 @@ TEST(MemIndexTest, NoMatchNestedScopes) { } TEST(MemIndexTest, IgnoreCases) { - auto I = MemIndex::build(generateSymbols({"ns::ABC", "ns::abc"}), - SymbolOccurrenceSlab()); + auto I = MemIndex::build(generateSymbols({"ns::ABC", "ns::abc"}), RefSlab()); FuzzyFindRequest Req; Req.Query = "AB"; Req.Scopes = {"ns::"}; @@ -150,8 +148,7 @@ TEST(MemIndexTest, IgnoreCases) { } TEST(MemIndexTest, Lookup) { - auto I = MemIndex::build(generateSymbols({"ns::abc", "ns::xyz"}), - SymbolOccurrenceSlab()); + auto I = MemIndex::build(generateSymbols({"ns::abc", "ns::xyz"}), RefSlab()); 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")); @@ -161,10 +158,8 @@ TEST(MemIndexTest, Lookup) { } TEST(MergeIndexTest, Lookup) { - auto I = MemIndex::build(generateSymbols({"ns::A", "ns::B"}), - SymbolOccurrenceSlab()), - J = MemIndex::build(generateSymbols({"ns::B", "ns::C"}), - SymbolOccurrenceSlab()); + auto I = MemIndex::build(generateSymbols({"ns::A", "ns::B"}), RefSlab()), + J = MemIndex::build(generateSymbols({"ns::B", "ns::C"}), RefSlab()); 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")); @@ -178,10 +173,8 @@ TEST(MergeIndexTest, Lookup) { } TEST(MergeIndexTest, FuzzyFind) { - auto I = MemIndex::build(generateSymbols({"ns::A", "ns::B"}), - SymbolOccurrenceSlab()), - J = MemIndex::build(generateSymbols({"ns::B", "ns::C"}), - SymbolOccurrenceSlab()); + auto I = MemIndex::build(generateSymbols({"ns::A", "ns::B"}), RefSlab()), + J = MemIndex::build(generateSymbols({"ns::B", "ns::C"}), RefSlab()); FuzzyFindRequest Req; Req.Scopes = {"ns::"}; EXPECT_THAT(match(*mergeIndex(I.get(), J.get()), Req), @@ -234,7 +227,7 @@ TEST(MergeTest, PreferSymbolWithDefn) { EXPECT_EQ(M.Name, "right"); } -TEST(MergeIndexTest, FindOccurrences) { +TEST(MergeIndexTest, Refs) { FileIndex Dyn({"unittest"}); FileIndex StaticIndex({"unittest"}); auto MergedIndex = mergeIndex(&Dyn, &StaticIndex); @@ -258,12 +251,12 @@ TEST(MergeIndexTest, FindOccurrences) { Test.Code = "// static\nclass Foo {};"; Test.Filename = "test.cc"; auto StaticAST = Test.build(); - // Add stale occurrences for test.cc. + // Add stale refs for test.cc. StaticIndex.update(Test.Filename, &StaticAST.getASTContext(), StaticAST.getPreprocessorPtr(), StaticAST.getLocalTopLevelDecls()); - // Add occcurrences for test2.cc + // Add refs for test2.cc Annotations Test2Code(R"(class $Foo[[Foo]] {};)"); TestTU Test2; Test2.HeaderCode = HeaderCode; @@ -274,18 +267,18 @@ TEST(MergeIndexTest, FindOccurrences) { StaticAST.getPreprocessorPtr(), StaticAST.getLocalTopLevelDecls()); - OccurrencesRequest Request; + RefsRequest Request; Request.IDs = {Foo.ID}; - Request.Filter = AllOccurrenceKinds; - std::vector<SymbolOccurrence> Results; - MergedIndex->findOccurrences( - Request, [&](const SymbolOccurrence &O) { Results.push_back(O); }); - - EXPECT_THAT(Results, UnorderedElementsAre( - AllOf(OccurrenceRange(Test1Code.range("Foo")), - FileURI("unittest:///test.cc")), - AllOf(OccurrenceRange(Test2Code.range("Foo")), - FileURI("unittest:///test2.cc")))); + RefSlab::Builder Results; + MergedIndex->refs(Request, [&](const Ref &O) { Results.insert(Foo.ID, O); }); + + EXPECT_THAT( + std::move(Results).build(), + ElementsAre(Pair( + _, UnorderedElementsAre(AllOf(RefRange(Test1Code.range("Foo")), + FileURI("unittest:///test.cc")), + AllOf(RefRange(Test2Code.range("Foo")), + FileURI("unittest:///test2.cc")))))); } MATCHER_P2(IncludeHeaderWithRef, IncludeHeader, References, "") { diff --git a/clang-tools-extra/unittests/clangd/SymbolCollectorTests.cpp b/clang-tools-extra/unittests/clangd/SymbolCollectorTests.cpp index b9efa5ba407..cc3c7d18622 100644 --- a/clang-tools-extra/unittests/clangd/SymbolCollectorTests.cpp +++ b/clang-tools-extra/unittests/clangd/SymbolCollectorTests.cpp @@ -33,11 +33,14 @@ namespace clangd { namespace { +using testing::_; using testing::AllOf; +using testing::Contains; using testing::Eq; using testing::Field; using testing::IsEmpty; using testing::Not; +using testing::Pair; using testing::UnorderedElementsAre; using testing::UnorderedElementsAreArray; @@ -76,21 +79,21 @@ MATCHER_P(DefRange, Pos, "") { std::tie(Pos.start.line, Pos.start.character, Pos.end.line, Pos.end.character); } -MATCHER_P(Refs, R, "") { return int(arg.References) == R; } +MATCHER_P(RefCount, R, "") { return int(arg.References) == R; } MATCHER_P(ForCodeCompletion, IsIndexedForCodeCompletion, "") { return arg.IsIndexedForCodeCompletion == IsIndexedForCodeCompletion; } -MATCHER(OccurrenceRange, "") { - const SymbolOccurrence &Pos = testing::get<0>(arg); +MATCHER(RefRange, "") { + const Ref &Pos = testing::get<0>(arg); const Range &Range = testing::get<1>(arg); return std::tie(Pos.Location.Start.Line, Pos.Location.Start.Column, Pos.Location.End.Line, Pos.Location.End.Column) == std::tie(Range.start.line, Range.start.character, Range.end.line, Range.end.character); } -testing::Matcher<const std::vector<SymbolOccurrence> &> +testing::Matcher<const std::vector<Ref> &> HaveRanges(const std::vector<Range> Ranges) { - return testing::UnorderedPointwise(OccurrenceRange(), Ranges); + return testing::UnorderedPointwise(RefRange(), Ranges); } class ShouldCollectSymbolTest : public ::testing::Test { @@ -250,7 +253,7 @@ public: llvm::MemoryBuffer::getMemBuffer(MainCode)); Invocation.run(); Symbols = Factory->Collector->takeSymbols(); - SymbolOccurrences = Factory->Collector->takeOccurrences(); + Refs = Factory->Collector->takeRefs(); return true; } @@ -261,7 +264,7 @@ protected: std::string TestFileName; std::string TestFileURI; SymbolSlab Symbols; - SymbolOccurrenceSlab SymbolOccurrences; + RefSlab Refs; SymbolCollector::Options CollectorOpts; std::unique_ptr<CommentHandler> PragmaHandler; }; @@ -428,7 +431,7 @@ o]](); )); } -TEST_F(SymbolCollectorTest, Occurrences) { +TEST_F(SymbolCollectorTest, Refs) { Annotations Header(R"( class $foo[[Foo]] { public: @@ -457,28 +460,23 @@ TEST_F(SymbolCollectorTest, Occurrences) { static const int c = 0; class d {}; )"); - CollectorOpts.OccurrenceFilter = AllOccurrenceKinds; + CollectorOpts.RefFilter = RefKind::All; runSymbolCollector(Header.code(), (Main.code() + SymbolsOnlyInMainCode.code()).str()); auto HeaderSymbols = TestTU::withHeaderCode(Header.code()).headerSymbols(); - EXPECT_THAT(SymbolOccurrences.find(findSymbol(Symbols, "Foo").ID), - HaveRanges(Main.ranges("foo"))); - EXPECT_THAT(SymbolOccurrences.find(findSymbol(Symbols, "Bar").ID), - HaveRanges(Main.ranges("bar"))); - EXPECT_THAT(SymbolOccurrences.find(findSymbol(Symbols, "func").ID), - HaveRanges(Main.ranges("func"))); - - // Retrieve IDs for symbols *only* in the main file, and verify these symbols - // are not collected. + EXPECT_THAT(Refs, Contains(Pair(findSymbol(Symbols, "Foo").ID, + HaveRanges(Main.ranges("foo"))))); + EXPECT_THAT(Refs, Contains(Pair(findSymbol(Symbols, "Bar").ID, + HaveRanges(Main.ranges("bar"))))); + EXPECT_THAT(Refs, Contains(Pair(findSymbol(Symbols, "func").ID, + HaveRanges(Main.ranges("func"))))); + // Symbols *only* in the main file (a, b, c) had no refs collected. auto MainSymbols = TestTU::withHeaderCode(SymbolsOnlyInMainCode.code()).headerSymbols(); - EXPECT_THAT(SymbolOccurrences.find(findSymbol(MainSymbols, "a").ID), - IsEmpty()); - EXPECT_THAT(SymbolOccurrences.find(findSymbol(MainSymbols, "b").ID), - IsEmpty()); - EXPECT_THAT(SymbolOccurrences.find(findSymbol(MainSymbols, "c").ID), - IsEmpty()); + EXPECT_THAT(Refs, Not(Contains(Pair(findSymbol(MainSymbols, "a").ID, _)))); + EXPECT_THAT(Refs, Not(Contains(Pair(findSymbol(MainSymbols, "b").ID, _)))); + EXPECT_THAT(Refs, Not(Contains(Pair(findSymbol(MainSymbols, "c").ID, _)))); } TEST_F(SymbolCollectorTest, References) { @@ -502,10 +500,10 @@ TEST_F(SymbolCollectorTest, References) { CollectorOpts.CountReferences = true; runSymbolCollector(Header, Main); EXPECT_THAT(Symbols, - UnorderedElementsAre(AllOf(QName("W"), Refs(1)), - AllOf(QName("X"), Refs(1)), - AllOf(QName("Y"), Refs(0)), - AllOf(QName("Z"), Refs(0)), QName("y"))); + UnorderedElementsAre(AllOf(QName("W"), RefCount(1)), + AllOf(QName("X"), RefCount(1)), + AllOf(QName("Y"), RefCount(0)), + AllOf(QName("Z"), RefCount(0)), QName("y"))); } TEST_F(SymbolCollectorTest, SymbolRelativeNoFallback) { @@ -1058,8 +1056,8 @@ TEST_F(SymbolCollectorTest, ReferencesInFriendDecl) { )"; CollectorOpts.CountReferences = true; runSymbolCollector(Header, Main); - EXPECT_THAT(Symbols, UnorderedElementsAre(AllOf(QName("X"), Refs(1)), - AllOf(QName("Y"), Refs(1)))); + EXPECT_THAT(Symbols, UnorderedElementsAre(AllOf(QName("X"), RefCount(1)), + AllOf(QName("Y"), RefCount(1)))); } TEST_F(SymbolCollectorTest, Origin) { @@ -1085,14 +1083,14 @@ TEST_F(SymbolCollectorTest, CollectMacros) { CollectorOpts.CountReferences = true; CollectorOpts.CollectMacro = true; runSymbolCollector(Header.code(), Main); - EXPECT_THAT( - Symbols, - UnorderedElementsAre( - QName("p"), - AllOf(QName("X"), DeclURI(TestHeaderURI), - IncludeHeader(TestHeaderURI)), - AllOf(Labeled("MAC(x)"), Refs(0), DeclRange(Header.range("mac"))), - AllOf(Labeled("USED(y)"), Refs(1), DeclRange(Header.range("used"))))); + EXPECT_THAT(Symbols, + UnorderedElementsAre(QName("p"), + AllOf(QName("X"), DeclURI(TestHeaderURI), + IncludeHeader(TestHeaderURI)), + AllOf(Labeled("MAC(x)"), RefCount(0), + DeclRange(Header.range("mac"))), + AllOf(Labeled("USED(y)"), RefCount(1), + DeclRange(Header.range("used"))))); } } // namespace diff --git a/clang-tools-extra/unittests/clangd/TestTU.cpp b/clang-tools-extra/unittests/clangd/TestTU.cpp index 9fd38a81667..d4b442cb505 100644 --- a/clang-tools-extra/unittests/clangd/TestTU.cpp +++ b/clang-tools-extra/unittests/clangd/TestTU.cpp @@ -49,8 +49,8 @@ SymbolSlab TestTU::headerSymbols() const { } std::unique_ptr<SymbolIndex> TestTU::index() const { - // FIXME: we should generate proper occurrences for TestTU. - return MemIndex::build(headerSymbols(), SymbolOccurrenceSlab::createEmpty()); + // FIXME: we should generate proper refs for TestTU. + return MemIndex::build(headerSymbols(), RefSlab()); } const Symbol &findSymbol(const SymbolSlab &Slab, llvm::StringRef QName) { |
