Index: clangd/index/FileIndex.h =================================================================== --- clangd/index/FileIndex.h +++ clangd/index/FileIndex.h @@ -39,18 +39,25 @@ /// locking when we swap or obtain refereces to snapshots. class FileSymbols { public: - /// \brief Updates all symbols in a file. If \p Slab is nullptr, symbols for - /// \p Path will be removed. - void update(PathRef Path, std::unique_ptr Slab); + /// \brief Updates all symbols and occurrences in a file. + /// If \p Slab (Occurrence) is nullptr, symbols (occurrences) 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; + private: mutable std::mutex Mutex; /// \brief 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 symbls from files and an in-memory index on all symbols. @@ -87,12 +94,12 @@ std::vector URISchemes; }; -/// Retrieves namespace and class level symbols in \p AST. +/// Retrieves symbols and symbol occurrences 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. -SymbolSlab +std::pair indexAST(ASTContext &AST, std::shared_ptr PP, llvm::Optional> TopLevelDecls = llvm::None, llvm::ArrayRef URISchemes = {}); Index: clangd/index/FileIndex.cpp =================================================================== --- clangd/index/FileIndex.cpp +++ clangd/index/FileIndex.cpp @@ -16,9 +16,10 @@ namespace clang { namespace clangd { -SymbolSlab indexAST(ASTContext &AST, std::shared_ptr PP, - llvm::Optional> TopLevelDecls, - llvm::ArrayRef URISchemes) { +std::pair +indexAST(ASTContext &AST, std::shared_ptr PP, + llvm::Optional> TopLevelDecls, + llvm::ArrayRef URISchemes) { SymbolCollector::Options CollectorOpts; // FIXME(ioeric): we might also want to collect include headers. We would need // to make sure all includes are canonicalized (with CanonicalIncludes), which @@ -31,8 +32,6 @@ CollectorOpts.URISchemes = URISchemes; CollectorOpts.Origin = SymbolOrigin::Dynamic; - SymbolCollector Collector(std::move(CollectorOpts)); - Collector.setPreprocessor(PP); index::IndexingOptions IndexOpts; // We only need declarations, because we don't count references. IndexOpts.SystemSymbolFilter = @@ -46,20 +45,42 @@ DeclsToIndex.assign(AST.getTranslationUnitDecl()->decls().begin(), AST.getTranslationUnitDecl()->decls().end()); + // We only collect occurrences 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. + if (TopLevelDecls) { + CollectorOpts.OccurrenceFilter = SymbolOccurrenceKind::Declaration | + SymbolOccurrenceKind::Definition | + SymbolOccurrenceKind::Reference; + } + + SymbolCollector Collector(std::move(CollectorOpts)); + Collector.setPreprocessor(PP); index::indexTopLevelDecls(AST, DeclsToIndex, Collector, IndexOpts); - return Collector.takeSymbols(); + auto Syms = Collector.takeSymbols(); + auto Occurrences = Collector.takeOccurrences(); + vlog("index for AST: \n" + " symbol slab: {0} symbols, {1} bytes\n" + " occurrence slab: {2} symbols, {3} bytes", + Syms.size(), Syms.bytes(), Occurrences.size(), Occurrences.bytes()); + return {std::move(Syms), std::move(Occurrences)}; } FileIndex::FileIndex(std::vector URISchemes) : URISchemes(std::move(URISchemes)) {} -void FileSymbols::update(PathRef Path, std::unique_ptr Slab) { +void FileSymbols::update(PathRef Path, std::unique_ptr Slab, + std::unique_ptr Occurrences) { std::lock_guard Lock(Mutex); if (!Slab) FileToSlabs.erase(Path); else FileToSlabs[Path] = std::move(Slab); + if (!Occurrences) + FileToOccurrenceSlabs.erase(Path); + else + FileToOccurrenceSlabs[Path] = std::move(Occurrences); } std::shared_ptr> FileSymbols::allSymbols() { @@ -85,19 +106,47 @@ 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 occurence 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); + } + } + } + + return {std::move(Snap), &Snap->Occurrences}; +} + void FileIndex::update(PathRef Path, ASTContext *AST, std::shared_ptr PP, llvm::Optional> TopLevelDecls) { if (!AST) { - FSymbols.update(Path, nullptr); + FSymbols.update(Path, nullptr, nullptr); } else { assert(PP); auto Slab = llvm::make_unique(); - *Slab = indexAST(*AST, PP, TopLevelDecls, URISchemes); - FSymbols.update(Path, std::move(Slab)); + auto OccurrenceSlab = llvm::make_unique(); + auto IndexResults = indexAST(*AST, PP, TopLevelDecls, URISchemes); + std::tie(*Slab, *OccurrenceSlab) = + indexAST(*AST, PP, TopLevelDecls, URISchemes); + FSymbols.update(Path, std::move(Slab), std::move(OccurrenceSlab)); } auto Symbols = FSymbols.allSymbols(); - Index.build(std::move(Symbols)); + Index.build(std::move(Symbols), FSymbols.allOccurrences()); } bool FileIndex::fuzzyFind( @@ -115,7 +164,7 @@ void FileIndex::findOccurrences( const OccurrencesRequest &Req, llvm::function_ref Callback) const { - log("findOccurrences is not implemented."); + Index.findOccurrences(Req, Callback); } } // namespace clangd Index: clangd/index/Index.h =================================================================== --- clangd/index/Index.h +++ clangd/index/Index.h @@ -31,9 +31,6 @@ uint32_t Line = 0; // 0-based // Using UTF-16 code units. uint32_t Column = 0; // 0-based - bool operator==(const Position& P) const { - return Line == P.Line && Column == P.Column; - } }; // The URI of the source file where a symbol occurs. @@ -44,11 +41,25 @@ Position End; explicit operator bool() const { return !FileURI.empty(); } - bool operator==(const SymbolLocation& Loc) const { - return std::tie(FileURI, Start, End) == - std::tie(Loc.FileURI, Loc.Start, Loc.End); - } }; +inline bool operator==(const SymbolLocation::Position& L, + const SymbolLocation::Position& R) { + return std::tie(L.Line, L.Column) == std::tie(R.Line, R.Column); +} +inline bool operator<(const SymbolLocation::Position &L, + const SymbolLocation::Position &R){ + return std::tie(L.Line, L.Column) < std::tie(R.Line, R.Column); +} +inline bool operator==(const SymbolLocation&L, + const SymbolLocation&R){ + return std::tie(L.FileURI, L.Start, L.End) == + std::tie(R.FileURI, R.Start, R.End); +} +inline bool operator<(const SymbolLocation&L, + const SymbolLocation&R){ + return std::tie(L.FileURI, L.Start, L.End) < + std::tie(R.FileURI, R.Start, R.End); +} llvm::raw_ostream &operator<<(llvm::raw_ostream &, const SymbolLocation &); // The class identifies a particular C++ symbol (class, function, method, etc). @@ -323,6 +334,67 @@ SymbolLocation Location; SymbolOccurrenceKind Kind = SymbolOccurrenceKind::Unknown; }; +inline bool operator<(const SymbolOccurrence &L, const SymbolOccurrence &R) { + return std::tie(L.Location, L.Kind) < std::tie(R.Location, R.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 &Occurrence); + +// An efficient structure of storing large set of symbol occurrences in memory. +// Filenames are deduplicated. +class SymbolOccurrenceSlab { + public: + using const_iterator = + llvm::DenseMap>::const_iterator; + using iterator = const_iterator; + + SymbolOccurrenceSlab() : UniqueStrings(Arena) {} + + // 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; + } + + const_iterator begin() const { return Occurrences.begin(); } + const_iterator end() const { return Occurrences.end(); } + + size_t bytes() const { + return sizeof(*this) + Arena.getTotalMemory() + + Occurrences.getMemorySize(); + } + + 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 find(const SymbolID &ID) const { + auto It = Occurrences.find(ID); + if (It == Occurrences.end()) + return {}; + return It->second; + } + + void freeze(); + +private: + bool Frozen = false; + llvm::BumpPtrAllocator Arena; + llvm::UniqueStringSaver UniqueStrings; + llvm::DenseMap> Occurrences; +}; struct FuzzyFindRequest { /// \brief A query string for the fuzzy find. This is matched against symbols' Index: clangd/index/Index.cpp =================================================================== --- clangd/index/Index.cpp +++ clangd/index/Index.cpp @@ -8,6 +8,7 @@ //===----------------------------------------------------------------------===// #include "Index.h" + #include "llvm/ADT/StringExtras.h" #include "llvm/Support/SHA1.h" #include "llvm/Support/raw_ostream.h" @@ -128,5 +129,48 @@ return SymbolSlab(std::move(NewArena), std::move(Symbols)); } +raw_ostream &operator<<(raw_ostream &OS, SymbolOccurrenceKind K) { + if (K == SymbolOccurrenceKind::Unknown) + return OS << "Unknown"; + static const std::vector Messages = {"Decl", "Def", "Ref"}; + bool VisitedOnce = false; + for (unsigned I = 0; I < Messages.size(); ++I) { + if (static_cast(K) & 1u << I) { + if (VisitedOnce) + OS << ", "; + OS << Messages[I]; + VisitedOnce = true; + } + } + return OS; +} + +llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, + const SymbolOccurrence &Occurrence) { + OS << Occurrence.Location << ":" << Occurrence.Kind; + return OS; +} + +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 SymbolOccurrenceSlab::freeze() { + // Deduplicate symbol occurrenes. + for (auto &IDAndOccurrence : Occurrences) { + auto &Occurrence = IDAndOccurrence.getSecond(); + std::sort(Occurrence.begin(), Occurrence.end()); + Occurrence.erase(std::unique(Occurrence.begin(), Occurrence.end()), + Occurrence.end()); + } + Frozen = true; +} + } // namespace clangd } // namespace clang Index: clangd/index/MemIndex.h =================================================================== --- clangd/index/MemIndex.h +++ clangd/index/MemIndex.h @@ -16,15 +16,21 @@ namespace clang { namespace clangd { -/// \brief This implements an index for a (relatively small) set of symbols that -/// can be easily managed in memory. +/// \brief This implements an index for a (relatively small) set of symbols (or +/// symbol occurrences) that can be easily managed in memory. class MemIndex : 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> Symbols); + using OccurrenceMap = + llvm::DenseMap>; - /// \brief Build index from a symbol slab. + /// \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); + + /// \brief Build index from a symbol slab. The returned Index doesn't have + /// symbol occurrences support. static std::unique_ptr build(SymbolSlab Slab); bool @@ -44,6 +50,8 @@ // 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; }; Index: clangd/index/MemIndex.cpp =================================================================== --- clangd/index/MemIndex.cpp +++ clangd/index/MemIndex.cpp @@ -15,7 +15,10 @@ namespace clang { namespace clangd { -void MemIndex::build(std::shared_ptr> Syms) { +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; @@ -25,12 +28,14 @@ std::lock_guard Lock(Mutex); Index = std::move(TempIndex); Symbols = std::move(Syms); // Relase old symbols. + Occurrences = std::move(AllOccurrences); } } std::unique_ptr MemIndex::build(SymbolSlab Slab) { auto Idx = llvm::make_unique(); - Idx->build(getSymbolsFromSlab(std::move(Slab))); + auto EmptyOccurrences = llvm::make_unique(); + Idx->build(getSymbolsFromSlab(std::move(Slab)), std::move(EmptyOccurrences)); return std::move(Idx); } @@ -81,7 +86,16 @@ void MemIndex::findOccurrences( const OccurrencesRequest &Req, llvm::function_ref Callback) const { - log("findOccurrences is not implemented."); + std::lock_guard Lock(Mutex); + for (const auto& ReqID : Req.IDs) { + auto FoundOccurrences = Occurrences->find(ReqID); + if (FoundOccurrences == Occurrences->end()) + continue; + for (const auto *O : FoundOccurrences->second) { + if (static_cast(Req.Filter & O->Kind)) + Callback(*O); + } + } } std::shared_ptr> Index: clangd/index/Merge.h =================================================================== --- clangd/index/Merge.h +++ clangd/index/Merge.h @@ -24,6 +24,10 @@ // - the Dynamic index covers few files, but is relatively up-to-date. // - the Static index covers a bigger set of files, but is relatively stale. // 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. std::unique_ptr mergeIndex(const SymbolIndex *Dynamic, const SymbolIndex *Static); Index: clangd/index/Merge.cpp =================================================================== --- clangd/index/Merge.cpp +++ clangd/index/Merge.cpp @@ -81,7 +81,27 @@ void findOccurrences(const OccurrencesRequest &Req, llvm::function_ref Callback) const override { - log("findOccurrences is not implemented."); + // 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. + // + // FIXME: The heuristic fails if the dynamic index containts 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. + llvm::DenseSet DynamicIndexFileURIs; + Dynamic->findOccurrences(Req, [&](const SymbolOccurrence &O) { + DynamicIndexFileURIs.insert(O.Location.FileURI); + Callback(O); + }); + Static->findOccurrences(Req, [&](const SymbolOccurrence &O) { + if (DynamicIndexFileURIs.find(O.Location.FileURI) != + DynamicIndexFileURIs.end()) + return; + Callback(O); + }); } private: Index: clangd/index/SymbolCollector.h =================================================================== --- clangd/index/SymbolCollector.h +++ clangd/index/SymbolCollector.h @@ -59,6 +59,10 @@ /// collect macros. For example, `indexTopLevelDecls` will not index any /// macro even if this is true. bool CollectMacro = false; + /// The symbol occurrence kind that will be collected. + /// If not set (Unknown), SymbolCollector will not collect any symbol + /// occurrences. + SymbolOccurrenceKind OccurrenceFilter = SymbolOccurrenceKind::Unknown; }; SymbolCollector(Options Opts); @@ -86,6 +90,10 @@ SymbolSlab takeSymbols() { return std::move(Symbols).build(); } + SymbolOccurrenceSlab takeOccurrences() { + return std::move(SymbolOccurrences); + } + void finish() override; private: @@ -108,6 +116,13 @@ // canonical by clang but should not be considered canonical in the index // unless it's a definition. llvm::DenseMap CanonicalDecls; + + using DeclOccurrence = std::pair; + llvm::DenseMap> DeclOccurrences; + // All symbol occurrences collected from the AST, assembled on finish(). + // Only symbols declared in preamble (from #inclues) and references from the + // main file will be included. + SymbolOccurrenceSlab SymbolOccurrences; }; } // namespace clangd Index: clangd/index/SymbolCollector.cpp =================================================================== --- clangd/index/SymbolCollector.cpp +++ clangd/index/SymbolCollector.cpp @@ -224,6 +224,17 @@ match(decl(isExpansionInMainFile()), ND, ND.getASTContext()).empty(); } +SymbolOccurrenceKind ToOccurrenceKind(index::SymbolRoleSet Roles) { + SymbolOccurrenceKind Kind; + for (auto Mask : + {SymbolOccurrenceKind::Declaration, SymbolOccurrenceKind::Definition, + SymbolOccurrenceKind::Reference}) { + if (Roles & static_cast(Mask)) + Kind |= Mask; + } + return Kind; +} + } // namespace SymbolCollector::SymbolCollector(Options Opts) : Opts(std::move(Opts)) {} @@ -313,6 +324,10 @@ SM.getFileID(SM.getSpellingLoc(Loc)) == SM.getMainFileID()) ReferencedDecls.insert(ND); + if ((static_cast(Opts.OccurrenceFilter) & Roles) && + SM.getFileID(SM.getSpellingLoc(Loc)) == SM.getMainFileID()) + DeclOccurrences[ND].emplace_back(Loc, Roles); + // Don't continue indexing if this is a mere reference. if (!(Roles & static_cast(index::SymbolRole::Declaration) || Roles & static_cast(index::SymbolRole::Definition))) @@ -436,8 +451,28 @@ IncRef(SymbolID(USR)); } } + + for (auto& It : DeclOccurrences) { + if (auto ID = getSymbolID(It.first)) { + if (Symbols.find(*ID)) { + for (const auto& LocAndRole: It.second) { + std::string FileURI; + if (auto DeclLoc = getTokenLocation(LocAndRole.first, + ASTCtx->getSourceManager(), Opts, + ASTCtx->getLangOpts(), FileURI)) { + SymbolOccurrence Occurrence; + Occurrence.Location = *DeclLoc; + Occurrence.Kind = ToOccurrenceKind(LocAndRole.second); + SymbolOccurrences.insert(*ID, Occurrence); + } + } + } + } + } + SymbolOccurrences.freeze(); ReferencedDecls.clear(); ReferencedMacros.clear(); + DeclOccurrences.clear(); } const Symbol *SymbolCollector::addDeclaration(const NamedDecl &ND, Index: unittests/clangd/FileIndexTests.cpp =================================================================== --- unittests/clangd/FileIndexTests.cpp +++ unittests/clangd/FileIndexTests.cpp @@ -7,18 +7,28 @@ // //===----------------------------------------------------------------------===// +#include "Annotations.h" #include "ClangdUnit.h" #include "TestFS.h" #include "TestTU.h" +#include "gmock/gmock.h" #include "index/FileIndex.h" #include "clang/Frontend/CompilerInvocation.h" #include "clang/Frontend/PCHContainerOperations.h" #include "clang/Lex/Preprocessor.h" #include "clang/Tooling/CompilationDatabase.h" -#include "gmock/gmock.h" #include "gtest/gtest.h" using testing::UnorderedElementsAre; +using testing::AllOf; + +MATCHER_P(OccurrenceRange, 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, + Range.end.character); +} +MATCHER_P(FileURI, F, "") { return arg.Location.FileURI == F; } namespace clang { namespace clangd { @@ -39,6 +49,15 @@ return llvm::make_unique(std::move(Slab).build()); } +std::unique_ptr occurrenceSlab(const SymbolID &ID, + llvm::StringRef Path) { + auto Slab = llvm::make_unique(); + SymbolOccurrence Occurrence; + Occurrence.Location.FileURI = Path; + Slab->insert(ID, Occurrence); + return Slab; +} + std::vector getSymbolNames(const std::vector &Symbols) { std::vector Names; @@ -47,19 +66,38 @@ return Names; } +std::vector +getOccurrencePath(const std::vector &Occurrences) { + std::vector Paths; + for (const auto *O : Occurrences) + Paths.push_back(O->Location.FileURI); + return Paths; +} + +std::unique_ptr emptyOccurrence() { + auto EmptySlab = llvm::make_unique(); + EmptySlab->freeze(); + return EmptySlab; +} + TEST(FileSymbolsTest, UpdateAndGet) { FileSymbols FS; EXPECT_THAT(getSymbolNames(*FS.allSymbols()), UnorderedElementsAre()); + EXPECT_TRUE(FS.allOccurrences()->empty()); - FS.update("f1", numSlab(1, 3)); + SymbolID ID("1"); + FS.update("f1", numSlab(1, 3), occurrenceSlab(ID, "f1.cc")); EXPECT_THAT(getSymbolNames(*FS.allSymbols()), UnorderedElementsAre("1", "2", "3")); + auto Occurrences = FS.allOccurrences(); + EXPECT_THAT(getOccurrencePath((*Occurrences)[ID]), + UnorderedElementsAre("f1.cc")); } TEST(FileSymbolsTest, Overlap) { FileSymbols FS; - FS.update("f1", numSlab(1, 3)); - FS.update("f2", numSlab(3, 5)); + 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")); } @@ -67,14 +105,22 @@ TEST(FileSymbolsTest, SnapshotAliveAfterRemove) { FileSymbols FS; - FS.update("f1", numSlab(1, 3)); + SymbolID ID("1"); + FS.update("f1", numSlab(1, 3), occurrenceSlab(ID, "f1.cc")); auto Symbols = FS.allSymbols(); EXPECT_THAT(getSymbolNames(*Symbols), UnorderedElementsAre("1", "2", "3")); + auto Occurrences = FS.allOccurrences(); + EXPECT_THAT(getOccurrencePath((*Occurrences)[ID]), + UnorderedElementsAre("f1.cc")); - FS.update("f1", nullptr); + FS.update("f1", nullptr, nullptr); EXPECT_THAT(getSymbolNames(*FS.allSymbols()), UnorderedElementsAre()); EXPECT_THAT(getSymbolNames(*Symbols), UnorderedElementsAre("1", "2", "3")); + + EXPECT_TRUE(FS.allOccurrences()->empty()); + EXPECT_THAT(getOccurrencePath((*Occurrences)[ID]), + UnorderedElementsAre("f1.cc")); } std::vector match(const SymbolIndex &I, @@ -270,6 +316,45 @@ UnorderedElementsAre("ns_in_header", "ns_in_header::func_in_header")); } +TEST(FileIndexTest, Occurrences) { + const char *HeaderCode = "class Foo {};"; + Annotations MainCode(R"cpp( + void f() { + $foo[[Foo]] foo; + } + )cpp"); + + auto Foo = + findSymbol(TestTU::withHeaderCode(HeaderCode).headerSymbols(), "Foo"); + + OccurrencesRequest Request; + Request.IDs = {Foo.ID}; + Request.Filter = SymbolOccurrenceKind::Declaration | + SymbolOccurrenceKind::Definition | + SymbolOccurrenceKind::Reference; + + FileIndex Index(/*URISchemes*/ {"unittest"}); + // Add test.cc + auto AST = + TestTU::withAllCode(HeaderCode, MainCode.code(), "test.cc").build(); + Index.update("test.cc", &AST.getASTContext(), AST.getPreprocessorPtr(), + AST.getLocalTopLevelDecls()); + // Add test2.cc + AST = TestTU::withAllCode(HeaderCode, MainCode.code(), "test2.cc").build(); + Index.update("test2.cc", &AST.getASTContext(), AST.getPreprocessorPtr(), + AST.getLocalTopLevelDecls()); + + std::vector 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")))); +} + } // namespace } // namespace clangd } // namespace clang Index: unittests/clangd/IndexTests.cpp =================================================================== --- unittests/clangd/IndexTests.cpp +++ unittests/clangd/IndexTests.cpp @@ -7,21 +7,36 @@ // //===----------------------------------------------------------------------===// +#include "Annotations.h" #include "TestIndex.h" +#include "TestTU.h" +#include "gmock/gmock.h" +#include "index/FileIndex.h" #include "index/Index.h" #include "index/MemIndex.h" #include "index/Merge.h" -#include "gmock/gmock.h" #include "gtest/gtest.h" using testing::Pointee; using testing::UnorderedElementsAre; +using testing::AllOf; 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, + arg.Location.End.Line, arg.Location.End.Column) == + std::tie(Range.start.line, Range.start.character, Range.end.line, + Range.end.character); +} +MATCHER_P(FileURI, F, "") { return arg.Location.FileURI == F; } TEST(SymbolSlab, FindAndIterate) { SymbolSlab::Builder B; @@ -42,14 +57,14 @@ TEST(MemIndexTest, MemIndexSymbolsRecycled) { MemIndex I; std::weak_ptr Symbols; - I.build(generateNumSymbols(0, 10, &Symbols)); + I.build(generateNumSymbols(0, 10, &Symbols), emptyOccurrences()); FuzzyFindRequest Req; Req.Query = "7"; EXPECT_THAT(match(I, Req), UnorderedElementsAre("7")); EXPECT_FALSE(Symbols.expired()); // Release old symbols. - I.build(generateNumSymbols(0, 0)); + I.build(generateNumSymbols(0, 0), emptyOccurrences()); EXPECT_TRUE(Symbols.expired()); } @@ -65,14 +80,14 @@ FuzzyFindRequest Req; Req.Query = "7"; MemIndex I; - I.build(std::move(Symbols)); + I.build(std::move(Symbols), emptyOccurrences()); auto Matches = match(I, Req); EXPECT_EQ(Matches.size(), 1u); } TEST(MemIndexTest, MemIndexLimitedNumMatches) { MemIndex I; - I.build(generateNumSymbols(0, 100)); + I.build(generateNumSymbols(0, 100), emptyOccurrences()); FuzzyFindRequest Req; Req.Query = "5"; Req.MaxCandidateCount = 3; @@ -85,7 +100,8 @@ TEST(MemIndexTest, FuzzyMatch) { MemIndex I; I.build( - generateSymbols({"LaughingOutLoud", "LionPopulation", "LittleOldLady"})); + generateSymbols({"LaughingOutLoud", "LionPopulation", "LittleOldLady"}), + emptyOccurrences()); FuzzyFindRequest Req; Req.Query = "lol"; Req.MaxCandidateCount = 2; @@ -95,7 +111,7 @@ TEST(MemIndexTest, MatchQualifiedNamesWithoutSpecificScope) { MemIndex I; - I.build(generateSymbols({"a::y1", "b::y2", "y3"})); + I.build(generateSymbols({"a::y1", "b::y2", "y3"}), emptyOccurrences()); FuzzyFindRequest Req; Req.Query = "y"; EXPECT_THAT(match(I, Req), UnorderedElementsAre("a::y1", "b::y2", "y3")); @@ -103,7 +119,7 @@ TEST(MemIndexTest, MatchQualifiedNamesWithGlobalScope) { MemIndex I; - I.build(generateSymbols({"a::y1", "b::y2", "y3"})); + I.build(generateSymbols({"a::y1", "b::y2", "y3"}), emptyOccurrences()); FuzzyFindRequest Req; Req.Query = "y"; Req.Scopes = {""}; @@ -112,7 +128,8 @@ TEST(MemIndexTest, MatchQualifiedNamesWithOneScope) { MemIndex I; - I.build(generateSymbols({"a::y1", "a::y2", "a::x", "b::y2", "y3"})); + I.build(generateSymbols({"a::y1", "a::y2", "a::x", "b::y2", "y3"}), + emptyOccurrences()); FuzzyFindRequest Req; Req.Query = "y"; Req.Scopes = {"a::"}; @@ -121,7 +138,8 @@ TEST(MemIndexTest, MatchQualifiedNamesWithMultipleScopes) { MemIndex I; - I.build(generateSymbols({"a::y1", "a::y2", "a::x", "b::y3", "y3"})); + I.build(generateSymbols({"a::y1", "a::y2", "a::x", "b::y3", "y3"}), + emptyOccurrences()); FuzzyFindRequest Req; Req.Query = "y"; Req.Scopes = {"a::", "b::"}; @@ -130,7 +148,7 @@ TEST(MemIndexTest, NoMatchNestedScopes) { MemIndex I; - I.build(generateSymbols({"a::y1", "a::b::y2"})); + I.build(generateSymbols({"a::y1", "a::b::y2"}), emptyOccurrences()); FuzzyFindRequest Req; Req.Query = "y"; Req.Scopes = {"a::"}; @@ -139,7 +157,7 @@ TEST(MemIndexTest, IgnoreCases) { MemIndex I; - I.build(generateSymbols({"ns::ABC", "ns::abc"})); + I.build(generateSymbols({"ns::ABC", "ns::abc"}), emptyOccurrences()); FuzzyFindRequest Req; Req.Query = "AB"; Req.Scopes = {"ns::"}; @@ -148,7 +166,7 @@ TEST(MemIndexTest, Lookup) { MemIndex I; - I.build(generateSymbols({"ns::abc", "ns::xyz"})); + 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")}), UnorderedElementsAre("ns::abc", "ns::xyz")); @@ -159,8 +177,8 @@ TEST(MergeIndexTest, Lookup) { MemIndex I, J; - I.build(generateSymbols({"ns::A", "ns::B"})); - J.build(generateSymbols({"ns::B", "ns::C"})); + 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")), @@ -180,8 +198,8 @@ TEST(MergeIndexTest, FuzzyFind) { MemIndex I, J; - I.build(generateSymbols({"ns::A", "ns::B"})); - J.build(generateSymbols({"ns::B", "ns::C"})); + I.build(generateSymbols({"ns::A", "ns::B"}), emptyOccurrences()); + J.build(generateSymbols({"ns::B", "ns::C"}), emptyOccurrences()); FuzzyFindRequest Req; Req.Scopes = {"ns::"}; EXPECT_THAT(match(*mergeIndex(&I, &J), Req), @@ -243,6 +261,55 @@ EXPECT_EQ(M.Name, "right"); } +TEST(MergeIndexTest, FindOccurrences) { + FileIndex Dyn({"unittest"}); + FileIndex StaticIndex({"unittest"}); + auto MergedIndex = mergeIndex(&Dyn, &StaticIndex); + + const char *HeaderCode = "class Foo;"; + auto HeaderSymbols = TestTU::withHeaderCode("class Foo;").headerSymbols(); + auto Foo = findSymbol(HeaderSymbols, "Foo"); + + // Build dynamic index. + Annotations Test1Code(R"(class $Foo[[Foo]];)"); + auto AST = + TestTU::withAllCode(HeaderCode, Test1Code.code(), "test.cc").build(); + Dyn.update("test.cc", &AST.getASTContext(), AST.getPreprocessorPtr(), + AST.getLocalTopLevelDecls()); + + // Build static index. + auto StaticAST = + TestTU::withAllCode(HeaderCode, "// static\nclass Foo {};", "test.cc") + .build(); + // Add stale occurrences for test.cc. + StaticIndex.update("test.cc", &StaticAST.getASTContext(), + StaticAST.getPreprocessorPtr(), + StaticAST.getLocalTopLevelDecls()); + + // Add occcurrences for test2.cc + Annotations Test2Code(R"(class $Foo[[Foo]] {};)"); + StaticAST = + TestTU::withAllCode(HeaderCode, Test2Code.code(), "test2.cc").build(); + StaticIndex.update("test2.cc", &StaticAST.getASTContext(), + StaticAST.getPreprocessorPtr(), + StaticAST.getLocalTopLevelDecls()); + + OccurrencesRequest Request; + Request.IDs = {Foo.ID}; + Request.Filter = SymbolOccurrenceKind::Declaration | + SymbolOccurrenceKind::Definition | + SymbolOccurrenceKind::Reference; + std::vector 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")))); +} + } // namespace } // namespace clangd } // namespace clang Index: unittests/clangd/SymbolCollectorTests.cpp =================================================================== --- unittests/clangd/SymbolCollectorTests.cpp +++ unittests/clangd/SymbolCollectorTests.cpp @@ -74,6 +74,16 @@ MATCHER_P(ForCodeCompletion, IsIndexedForCodeCompletion, "") { return arg.IsIndexedForCodeCompletion == IsIndexedForCodeCompletion; } +MATCHER(OccurrenceRange, "") { + const clang::clangd::SymbolOccurrence& Pos = testing::get<0>(arg); + const clang::clangd::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); +} namespace clang { namespace clangd { @@ -237,6 +247,7 @@ llvm::MemoryBuffer::getMemBuffer(MainCode)); Invocation.run(); Symbols = Factory->Collector->takeSymbols(); + SymbolOccurrences = Factory->Collector->takeOccurrences(); return true; } @@ -247,6 +258,7 @@ std::string TestFileName; std::string TestFileURI; SymbolSlab Symbols; + SymbolOccurrenceSlab SymbolOccurrences; SymbolCollector::Options CollectorOpts; std::unique_ptr PragmaHandler; }; @@ -413,6 +425,67 @@ )); } +TEST_F(SymbolCollectorTest, Occurrences) { + Annotations Header(R"( + class $foo[[Foo]] { + public: + $foo[[Foo]]() {} + $foo[[Foo]](int); + }; + class $bar[[Bar]]; + void $func[[func]](); + )"); + Annotations Main(R"( + class $bar[[Bar]] {}; + + void $func[[func]](); + + void fff() { + $foo[[Foo]] foo; + $bar[[Bar]] bar; + $func[[func]](); + int abc = 0; + $foo[[Foo]] foo2 = abc; + } + )"); + Annotations SymbolsOnlyInMainCode(R"( + int a; + void b() {} + static const int c = 0; + class d {}; + )"); + CollectorOpts.OccurrenceFilter = SymbolOccurrenceKind::Declaration | + SymbolOccurrenceKind::Definition | + SymbolOccurrenceKind::Reference; + runSymbolCollector(Header.code(), + (Main.code() + SymbolsOnlyInMainCode.code()).str()); + auto HeaderSymbols = TestTU::withHeaderCode(Header.code()).headerSymbols(); + + EXPECT_THAT( + SymbolOccurrences.find(findSymbol(Symbols, "Foo").ID), + testing::UnorderedPointwise(OccurrenceRange(), Main.ranges("foo"))); + EXPECT_THAT( + SymbolOccurrences.find(findSymbol(Symbols, "Bar").ID), + testing::UnorderedPointwise(OccurrenceRange(), Main.ranges("bar"))); + EXPECT_THAT( + SymbolOccurrences.find(findSymbol(Symbols, "func").ID), + testing::UnorderedPointwise(OccurrenceRange(), Main.ranges("func"))); + + // Retrieve IDs for symbols *only* in the main file, and verify these symbols + // are not collected. + auto MainSymbols = + TestTU::withHeaderCode(SymbolsOnlyInMainCode.code()).headerSymbols(); + EXPECT_THAT( + SymbolOccurrences.find(findSymbol(MainSymbols, "a").ID), + testing::IsEmpty()); + EXPECT_THAT( + SymbolOccurrences.find(findSymbol(MainSymbols, "b").ID), + testing::IsEmpty()); + EXPECT_THAT( + SymbolOccurrences.find(findSymbol(MainSymbols, "c").ID), + testing::IsEmpty()); +} + TEST_F(SymbolCollectorTest, References) { const std::string Header = R"( class W; Index: unittests/clangd/TestTU.h =================================================================== --- unittests/clangd/TestTU.h +++ unittests/clangd/TestTU.h @@ -38,6 +38,16 @@ return TU; } + static TestTU withAllCode(llvm::StringRef HeaderCode, llvm::StringRef Code, + llvm::StringRef Filename = "") { + TestTU TU; + TU.HeaderCode = HeaderCode; + TU.Code = Code; + if (!Filename.empty()) + TU.Filename = Filename; + return TU; + } + // The code to be compiled. std::string Code; std::string Filename = "TestTU.cpp"; Index: unittests/clangd/TestTU.cpp =================================================================== --- unittests/clangd/TestTU.cpp +++ unittests/clangd/TestTU.cpp @@ -45,7 +45,7 @@ SymbolSlab TestTU::headerSymbols() const { auto AST = build(); - return indexAST(AST.getASTContext(), AST.getPreprocessorPtr()); + return indexAST(AST.getASTContext(), AST.getPreprocessorPtr()).first; } std::unique_ptr TestTU::index() const {