Index: clangd/FindSymbols.h =================================================================== --- clangd/FindSymbols.h +++ clangd/FindSymbols.h @@ -17,9 +17,9 @@ #include "llvm/ADT/StringRef.h" namespace clang { -class ParsedAST; namespace clangd { class SymbolIndex; +class ParsedAST; /// Searches for the symbols matching \p Query. The syntax of \p Query can be /// the non-qualified name or fully qualified of a symbol. For example, "vector" Index: clangd/index/FileIndex.h =================================================================== --- clangd/index/FileIndex.h +++ clangd/index/FileIndex.h @@ -73,6 +73,10 @@ void lookup(const LookupRequest &Req, llvm::function_ref Callback) const override; + + void findOccurrences(const OccurrencesRequest &Req, + llvm::function_ref + Callback) const override; private: FileSymbols FSymbols; MemIndex Index; Index: clangd/index/FileIndex.cpp =================================================================== --- clangd/index/FileIndex.cpp +++ clangd/index/FileIndex.cpp @@ -105,5 +105,11 @@ Index.lookup(Req, Callback); } +void FileIndex::findOccurrences( + const OccurrencesRequest &Req, + llvm::function_ref Callback) const { + // FIXME(hokein): implement it. +} + } // namespace clangd } // namespace clang Index: clangd/index/Index.h =================================================================== --- clangd/index/Index.h +++ clangd/index/Index.h @@ -17,6 +17,8 @@ #include "llvm/ADT/Hashing.h" #include "llvm/ADT/Optional.h" #include "llvm/ADT/StringExtras.h" +#include "llvm/Support/Allocator.h" +#include "llvm/Support/StringSaver.h" #include #include @@ -215,7 +217,6 @@ // Optional details of the symbol. const Details *Detail = nullptr; - // FIXME: add all occurrences support. // FIXME: add extra fields for index scoring signals. }; llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, const Symbol &S); @@ -280,6 +281,96 @@ std::vector Symbols; // Sorted by SymbolID to allow lookup. }; +// Describes the kind of a symbol occurrence. +// +// This is a bitfield which can be combined from different kinds. +enum class SymbolOccurrenceKind : uint8_t { + Unknown = 0, + Declaration = static_cast(index::SymbolRole::Declaration), + Definition = static_cast(index::SymbolRole::Definition), + Reference = static_cast(index::SymbolRole::Reference), +}; +inline SymbolOccurrenceKind operator|(SymbolOccurrenceKind L, + SymbolOccurrenceKind R) { + return static_cast(static_cast(L) | + static_cast(R)); +} +inline SymbolOccurrenceKind &operator|=(SymbolOccurrenceKind &L, + SymbolOccurrenceKind R) { + return L = L | R; +} +inline SymbolOccurrenceKind operator&(SymbolOccurrenceKind A, + SymbolOccurrenceKind B) { + return static_cast(static_cast(A) & + static_cast(B)); +} +raw_ostream &operator<<(raw_ostream &, SymbolOccurrenceKind); + +// Represents a symbol occurrence in the source file. It could be a +// declaration/definition/reference occurrence. +struct SymbolOccurrence { + // The location of the occurrence. + // WARNING: Location does not own the underlying data - FileURI are owned by a + // SymbolOccurrenceSlab. Copies are shallow. + SymbolLocation Location; + SymbolOccurrenceKind Kind; +}; +inline bool operator==(const SymbolOccurrence &L, const SymbolOccurrence &R){ + return std::tie(L.Location, L.Kind) == std::tie(R.Location, R.Kind); +} + +llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, const SymbolOccurrence &S); + +// An efficient structure of storing large set of symbol occurrences in memory. +// Filenames are deduplicated. +class SymbolOccurrenceSlab { + public: + SymbolOccurrenceSlab() = default; + + SymbolOccurrenceSlab(SymbolOccurrenceSlab &&Old) + : Arena(std::move(Old.Arena)), Occurrences(std::move(Old.Occurrences)) {} + SymbolOccurrenceSlab &operator=(SymbolOccurrenceSlab &&Old) { + Arena = std::move(Old.Arena); + Occurrences = std::move(Old.Occurrences); + return *this; + } + + llvm::ArrayRef find(const SymbolID& ID) const { + auto It = Occurrences.find(ID); + if (It == Occurrences.end()) + return {}; + return It->second; + } + + // A mutable container that can 'freeze' to SymbolOccurrenceSlab. + // The frozen OccurrenceSlab will use less memory. + class Builder { + public: + Builder() : UniqueStrings(Arena) {} + // 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); + + // Consumes the builder to finalize the slab. + SymbolOccurrenceSlab build() &&; + + private: + llvm::BumpPtrAllocator Arena; + UniqueStringSaver UniqueStrings; + + llvm::DenseMap> Occurrences; + }; + +private: + SymbolOccurrenceSlab( + llvm::BumpPtrAllocator Arena, + llvm::DenseMap> Occurrences) + : Arena(std::move(Arena)), Occurrences(std::move(Occurrences)) {} + + llvm::BumpPtrAllocator Arena; + llvm::DenseMap> Occurrences; +}; + struct FuzzyFindRequest { /// \brief A query string for the fuzzy find. This is matched against symbols' /// un-qualified identifiers and should not contain qualifiers like "::". @@ -305,6 +396,11 @@ llvm::DenseSet IDs; }; +struct OccurrencesRequest { + llvm::DenseSet IDs; + SymbolOccurrenceKind Filter; +}; + /// \brief 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 { @@ -327,8 +423,14 @@ lookup(const LookupRequest &Req, llvm::function_ref Callback) const = 0; - // FIXME: add interfaces for more index use cases: - // - getAllOccurrences(SymbolID); + /// CrossReference finds all symbol occurrences (e.g. references, + /// declarations, definitions) and applies \p Callback on each result. + /// + /// The API is not responsible to rank results. + /// The returned result must be deep-copied if it's used outside Callback. + virtual void findOccurrences( + const OccurrencesRequest &Req, + llvm::function_ref Callback) const = 0; }; } // namespace clangd Index: clangd/index/Index.cpp =================================================================== --- clangd/index/Index.cpp +++ clangd/index/Index.cpp @@ -134,5 +134,34 @@ return SymbolSlab(std::move(NewArena), std::move(Symbols)); } +raw_ostream &operator<<(raw_ostream &OS, SymbolOccurrenceKind K) { + if (K == SymbolOccurrenceKind::Unknown) + return OS << "unknown"; + if (K == SymbolOccurrenceKind::Declaration) + return OS << "declaration"; + if (K == SymbolOccurrenceKind::Definition) + return OS << "definition"; + if (K == SymbolOccurrenceKind::Reference) + return OS << "reference"; + return OS; +} +llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, const SymbolOccurrence &S) { + OS << S.Location << S.Kind; + return OS; +} + +void SymbolOccurrenceSlab::Builder::insert(const SymbolID &SymID, + const SymbolOccurrence &Occurrence) { + auto& SymOccurrences = Occurrences[SymID]; + SymOccurrences.push_back(Occurrence); + SymOccurrences.back().Location.FileURI = + UniqueStrings.save(Occurrence.Location.FileURI); +} + +// Consumes the builder to finalize the slab. +SymbolOccurrenceSlab SymbolOccurrenceSlab::Builder::build() && { + return SymbolOccurrenceSlab(std::move(Arena), std::move(Occurrences)); +} + } // namespace clangd } // namespace clang Index: clangd/index/MemIndex.h =================================================================== --- clangd/index/MemIndex.h +++ clangd/index/MemIndex.h @@ -22,7 +22,8 @@ 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> Symbols); + void build(std::shared_ptr> Symbols, + SymbolOccurrenceSlab OccurrenceSlab = {}); /// \brief Build index from a symbol slab. static std::unique_ptr build(SymbolSlab Slab); @@ -31,15 +32,21 @@ fuzzyFind(const FuzzyFindRequest &Req, llvm::function_ref Callback) const override; - virtual void + void lookup(const LookupRequest &Req, llvm::function_ref Callback) const override; + void findOccurrences(const OccurrencesRequest &Req, + llvm::function_ref + Callback) const override; + private: std::shared_ptr> Symbols; // Index is a set of symbols that are deduplicated by symbol IDs. // FIXME: build smarter index structure. llvm::DenseMap Index; + + SymbolOccurrenceSlab Occurrences; mutable std::mutex Mutex; }; Index: clangd/index/MemIndex.cpp =================================================================== --- clangd/index/MemIndex.cpp +++ clangd/index/MemIndex.cpp @@ -15,7 +15,8 @@ namespace clang { namespace clangd { -void MemIndex::build(std::shared_ptr> Syms) { +void MemIndex::build(std::shared_ptr> Syms, + SymbolOccurrenceSlab OccurrenceSlab) { llvm::DenseMap TempIndex; for (const Symbol *Sym : *Syms) TempIndex[Sym->ID] = Sym; @@ -25,6 +26,7 @@ std::lock_guard Lock(Mutex); Index = std::move(TempIndex); Symbols = std::move(Syms); // Relase old symbols. + Occurrences = std::move(OccurrenceSlab); } } @@ -87,5 +89,17 @@ return std::move(MemIdx); } +void MemIndex::findOccurrences( + const OccurrencesRequest &Req, + llvm::function_ref Callback) const { + for (const auto &ID : Req.IDs) { + for (const auto& Occurrence : Occurrences.find(ID)) { + if (static_cast(Req.Filter & Occurrence.Kind)) { + Callback(Occurrence); + } + } + } +} + } // namespace clangd } // namespace clang Index: clangd/index/Merge.cpp =================================================================== --- clangd/index/Merge.cpp +++ clangd/index/Merge.cpp @@ -74,6 +74,12 @@ Callback(*Sym); } + void findOccurrences(const OccurrencesRequest &Req, + llvm::function_ref + Callback) const override { + // FIXME(hokein): implement it. + } + private: const SymbolIndex *Dynamic, *Static; }; Index: unittests/clangd/CodeCompleteTests.cpp =================================================================== --- unittests/clangd/CodeCompleteTests.cpp +++ unittests/clangd/CodeCompleteTests.cpp @@ -891,6 +891,10 @@ void lookup(const LookupRequest &, llvm::function_ref) const override {} + void findOccurrences(const OccurrencesRequest &Req, + llvm::function_ref + Callback) const override {} + const std::vector allRequests() const { return Requests; } private: Index: unittests/clangd/IndexTests.cpp =================================================================== --- unittests/clangd/IndexTests.cpp +++ unittests/clangd/IndexTests.cpp @@ -34,7 +34,22 @@ return Sym; } +SymbolOccurrence symbolOccurrence(SymbolOccurrenceKind Kind, + llvm::StringRef FileURI, + uint32_t Line, uint32_t Column) { + SymbolOccurrence Occurrence; + Occurrence.Kind = Kind; + Occurrence.Location.FileURI = FileURI; + Occurrence.Location.Start.Line = Occurrence.Location.End.Line; + Occurrence.Location.Start.Column = Column; + Occurrence.Location.End.Column = Column; + return Occurrence; +} + MATCHER_P(Named, N, "") { return arg.Name == N; } +MATCHER_P(Occurrence, L, "") { + return arg == L; +} TEST(SymbolSlab, FindAndIterate) { SymbolSlab::Builder B; @@ -235,6 +250,53 @@ EXPECT_THAT(lookup(I, SymbolID("ns::nonono")), UnorderedElementsAre()); } +std::vector findOccurrences(const SymbolIndex &I, + OccurrencesRequest Req) { + std::vector Results; + I.findOccurrences(Req, [&](const SymbolOccurrence &Occurrence) { + Results.push_back(Occurrence); + }); + return Results; +} + +TEST(MemIndexTest, findOccurrences) { + auto FooDecl = symbolOccurrence(SymbolOccurrenceKind::Declaration, + "file:///foo.h", 1, 2); + auto FooDef = symbolOccurrence(SymbolOccurrenceKind::Definition, + "file:///foo.cc", 1, 2); + auto FooRef = symbolOccurrence(SymbolOccurrenceKind::Reference, + "file:///call_foo.cc", 1, 2); + auto BarDecl = symbolOccurrence(SymbolOccurrenceKind::Declaration, + "file:///bar.h", 1, 2); + SymbolOccurrenceSlab::Builder Occurrences; + Occurrences.insert(SymbolID("foo"), FooDecl); + Occurrences.insert(SymbolID("foo"), FooDef); + Occurrences.insert(SymbolID("foo"), FooRef); + Occurrences.insert(SymbolID("bar"), BarDecl); + auto Empty = std::make_shared>(); + MemIndex I; + I.build(Empty, std::move(Occurrences).build()); + + OccurrencesRequest Req; + Req.IDs.insert(SymbolID("foo")); + Req.Filter = SymbolOccurrenceKind::Declaration; + EXPECT_THAT(findOccurrences(I, Req), + UnorderedElementsAre(Occurrence(FooDecl))); + + Req.Filter = SymbolOccurrenceKind::Definition; + EXPECT_THAT(findOccurrences(I, Req), + UnorderedElementsAre(Occurrence(FooDef))); + + Req.Filter = SymbolOccurrenceKind::Declaration | + SymbolOccurrenceKind::Definition | + SymbolOccurrenceKind::Reference; + + EXPECT_THAT(findOccurrences(I, Req), + UnorderedElementsAre(Occurrence(FooDecl), + Occurrence(FooDef), + Occurrence(FooRef))); +} + TEST(MergeIndexTest, Lookup) { MemIndex I, J; I.build(generateSymbols({"ns::A", "ns::B"}));