diff --git a/clang-tools-extra/clangd/index/Background.h b/clang-tools-extra/clangd/index/Background.h --- a/clang-tools-extra/clangd/index/Background.h +++ b/clang-tools-extra/clangd/index/Background.h @@ -110,6 +110,9 @@ std::mutex IndexMu; std::condition_variable IndexCV; + // Note that FileSymbols counts References by incrementing it per each file + // mentioning the symbol, including headers. This contradicts with the + // behavior inside clangd-indexer, which only counts translation units. FileSymbols IndexedSymbols; llvm::StringMap IndexedFileDigests; // Key is absolute file path. std::mutex DigestsMu; diff --git a/clang-tools-extra/clangd/index/FileIndex.h b/clang-tools-extra/clangd/index/FileIndex.h --- a/clang-tools-extra/clangd/index/FileIndex.h +++ b/clang-tools-extra/clangd/index/FileIndex.h @@ -56,6 +56,10 @@ /// /// The snapshot semantics keeps critical sections minimal since we only need /// locking when we swap or obtain references to snapshots. +/// +/// Will calculate Symbol::References based on number of RefSlabs referencing it +/// when building the index with DuplicateHandling::Merge option if any +/// References exists. class FileSymbols { public: /// Updates all symbols and refs in a file. diff --git a/clang-tools-extra/clangd/index/FileIndex.cpp b/clang-tools-extra/clangd/index/FileIndex.cpp --- a/clang-tools-extra/clangd/index/FileIndex.cpp +++ b/clang-tools-extra/clangd/index/FileIndex.cpp @@ -27,6 +27,52 @@ namespace clang { namespace clangd { +namespace { +// Puts all refs for the same symbol into RefsStorage in a contigious way. +// If MergedSyms is provided, increments a symbols Reference count once for +// every slab it was mentioned in. +void mergeRefs(llvm::ArrayRef> RefSlabs, + std::vector &RefsStorage, + llvm::DenseMap> &AllRefs, + llvm::DenseMap *MergedSyms = nullptr) { + llvm::DenseMap> MergedRefs; + size_t Count = 0; + for (const auto &RefSlab : RefSlabs) { + for (const auto &Sym : *RefSlab) { + auto MergedRefEntry = MergedRefs.try_emplace(Sym.first); + MergedRefEntry.first->getSecond().append(Sym.second.begin(), + Sym.second.end()); + Count += Sym.second.size(); + if (MergedSyms) { + auto It = MergedSyms->find(Sym.first); + // This can happen when indexing is still going on, hopefully in the end + // all referenced symbols should exist inside MergedSyms. + if (It == MergedSyms->end()) + continue; + // If this is the first time we see references to a symbol, reset its + // Reference count, since filesymbols re-count number of references + // based on number of refslabs referring to it. + if (MergedRefEntry.second) + It->getSecond().References = 0; + It->getSecond().References++; + } + } + } + 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. + llvm::sort(SymRefs); + llvm::copy(SymRefs, back_inserter(RefsStorage)); + AllRefs.try_emplace( + Sym.first, + llvm::ArrayRef(&RefsStorage[RefsStorage.size() - SymRefs.size()], + SymRefs.size())); + } +} + +} // namespace static std::pair indexSymbols(ASTContext &AST, std::shared_ptr PP, @@ -115,6 +161,9 @@ } std::vector AllSymbols; std::vector SymsStorage; + std::vector RefsStorage; // Contiguous ranges for each SymbolID. + llvm::DenseMap> AllRefs; + switch (DuplicateHandle) { case DuplicateHandling::Merge: { llvm::DenseMap Merged; @@ -125,12 +174,12 @@ I.first->second = mergeSymbol(I.first->second, Sym); } } + mergeRefs(RefSlabs, RefsStorage, AllRefs, &Merged); SymsStorage.reserve(Merged.size()); for (auto &Sym : Merged) { SymsStorage.push_back(std::move(Sym.second)); AllSymbols.push_back(&SymsStorage.back()); } - // FIXME: aggregate symbol reference count based on references. break; } case DuplicateHandling::PickOne: { @@ -139,34 +188,11 @@ for (const auto &Sym : *Slab) if (AddedSymbols.insert(Sym.ID).second) AllSymbols.push_back(&Sym); + mergeRefs(RefSlabs, RefsStorage, AllRefs); break; } } - std::vector RefsStorage; // Contiguous ranges for each SymbolID. - llvm::DenseMap> AllRefs; - { - llvm::DenseMap> 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. - llvm::sort(SymRefs); - llvm::copy(SymRefs, back_inserter(RefsStorage)); - AllRefs.try_emplace( - Sym.first, - llvm::ArrayRef(&RefsStorage[RefsStorage.size() - SymRefs.size()], - SymRefs.size())); - } - } - size_t StorageSize = RefsStorage.size() * sizeof(Ref) + SymsStorage.size() * sizeof(Symbol); for (const auto &Slab : SymbolSlabs) diff --git a/clang-tools-extra/unittests/clangd/BackgroundIndexTests.cpp b/clang-tools-extra/unittests/clangd/BackgroundIndexTests.cpp --- a/clang-tools-extra/unittests/clangd/BackgroundIndexTests.cpp +++ b/clang-tools-extra/unittests/clangd/BackgroundIndexTests.cpp @@ -32,6 +32,7 @@ return !arg.IsTU && !arg.URI.empty() && arg.Digest == FileDigest{{0}} && arg.DirectIncludes.empty(); } +MATCHER_P(NumReferences, N, "") { return arg.References == N; } class MemoryShardStorage : public BackgroundIndexStorage { mutable std::mutex StorageMu; @@ -127,20 +128,25 @@ CDB.setCompileCommand(testPath("root/A.cc"), Cmd); ASSERT_TRUE(Idx.blockUntilIdleForTest()); - EXPECT_THAT( - runFuzzyFind(Idx, ""), - UnorderedElementsAre(Named("common"), Named("A_CC"), Named("g"), - AllOf(Named("f_b"), Declared(), Not(Defined())))); + EXPECT_THAT(runFuzzyFind(Idx, ""), + UnorderedElementsAre(AllOf(Named("common"), NumReferences(2U)), + AllOf(Named("A_CC"), NumReferences(1U)), + AllOf(Named("g"), NumReferences(0U)), + AllOf(Named("f_b"), Declared(), + Not(Defined()), NumReferences(1U)))); Cmd.Filename = testPath("root/B.cc"); Cmd.CommandLine = {"clang++", Cmd.Filename}; - CDB.setCompileCommand(testPath("root/A.cc"), Cmd); + CDB.setCompileCommand(testPath("root/B.cc"), Cmd); ASSERT_TRUE(Idx.blockUntilIdleForTest()); // B_CC is dropped as we don't collect symbols from A.h in this compilation. EXPECT_THAT(runFuzzyFind(Idx, ""), - UnorderedElementsAre(Named("common"), Named("A_CC"), Named("g"), - AllOf(Named("f_b"), Declared(), Defined()))); + UnorderedElementsAre(AllOf(Named("common"), NumReferences(3U)), + AllOf(Named("A_CC"), NumReferences(1U)), + AllOf(Named("g"), NumReferences(0U)), + AllOf(Named("f_b"), Declared(), Defined(), + NumReferences(2U)))); auto Syms = runFuzzyFind(Idx, "common"); EXPECT_THAT(Syms, UnorderedElementsAre(Named("common"))); diff --git a/clang-tools-extra/unittests/clangd/FileIndexTests.cpp b/clang-tools-extra/unittests/clangd/FileIndexTests.cpp --- a/clang-tools-extra/unittests/clangd/FileIndexTests.cpp +++ b/clang-tools-extra/unittests/clangd/FileIndexTests.cpp @@ -46,6 +46,9 @@ return llvm::StringRef(arg.Definition.FileURI) == U; } MATCHER_P(QName, N, "") { return (arg.Scope + arg.Name).str() == N; } +MATCHER_P(NumReferences, N, "") { + return arg.References == static_cast(N); +} namespace clang { namespace clangd { @@ -59,6 +62,7 @@ Symbol Sym; Sym.ID = SymbolID(ID); Sym.Name = ID; + Sym.References = 1; return Sym; } @@ -417,6 +421,31 @@ EXPECT_THAT(getRefs(Index, Foo.ID), RefsAre({RefRange(Main.range())})); } +TEST(FileSymbolsTest, CountReferencesNoRefs) { + FileSymbols FS; + FS.update("f1", numSlab(1, 3), nullptr); + FS.update("f2", numSlab(1, 3), nullptr); + FS.update("f3", numSlab(1, 3), nullptr); + EXPECT_THAT( + runFuzzyFind(*FS.buildIndex(IndexType::Light, DuplicateHandling::Merge), + ""), + UnorderedElementsAre(AllOf(QName("1"), NumReferences(3)), + AllOf(QName("2"), NumReferences(3)), + AllOf(QName("3"), NumReferences(3)))); +} + +TEST(FileSymbolsTest, CountReferencesWithRefs) { + FileSymbols FS; + FS.update("f1", numSlab(1, 3), refSlab(SymbolID("1"), "f1.cpp")); + FS.update("f2", numSlab(1, 3), refSlab(SymbolID("2"), "f2.cpp")); + FS.update("f3", numSlab(1, 3), refSlab(SymbolID("3"), "f3.cpp")); + EXPECT_THAT( + runFuzzyFind(*FS.buildIndex(IndexType::Light, DuplicateHandling::Merge), + ""), + UnorderedElementsAre(AllOf(QName("1"), NumReferences(1)), + AllOf(QName("2"), NumReferences(1)), + AllOf(QName("3"), NumReferences(1)))); +} } // namespace } // namespace clangd } // namespace clang