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,60 @@ 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(); } + + // 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 @@ -128,5 +128,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/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/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;