https://github.com/nickitat updated https://github.com/llvm/llvm-project/pull/237760
>From 07d52699e1b110c4eb1a5cdd2ca059dcc1ea823f Mon Sep 17 00:00:00 2001 From: Nikita Taranov <[email protected]> Date: Sun, 1 Nov 2026 18:34:41 +0000 Subject: [PATCH 1/6] [clangd] Speed up loading the background index from disk Two hot spots showed up when profiling how clangd loads a large background index (17k TUs, 41k shards, 447 MB) at startup: - `Dex` re-inserted every entry of the refs map built by `FileSymbols::buildIndex` into its own `DenseMap` of the same type. It now takes the map over when it is passed by rvalue. This was 18.6% of the load. - Refs read from an index file went through `RefSlab::Builder`, which interns the file URI and inserts into a `DenseSet` for every ref, then sorts everything again. Refs on disk are already grouped by symbol, so add `RefSlab::BundleBuilder`, which takes whole per-symbol bundles, interns each URI once per distinct string, and keeps the existing order. If a symbol appears in several bundles it falls back to `RefSlab::Builder`, so the result is the same. This was about 12% of the load. Time from enqueueing the project to serving the loaded index, on a warm page cache: 5.4-5.6 s before, 4.0-4.1 s after (-26%). Results of `workspace/symbol` and `textDocument/references` queries are identical. Co-Authored-By: Claude Opus 5.5 <[email protected]> --- clang-tools-extra/clangd/index/Ref.cpp | 39 +++++++++++++++ clang-tools-extra/clangd/index/Ref.h | 21 ++++++++ .../clangd/index/Serialization.cpp | 5 +- clang-tools-extra/clangd/index/dex/Dex.h | 11 ++++- .../clangd/unittests/IndexTests.cpp | 49 +++++++++++++++++++ 5 files changed, 120 insertions(+), 5 deletions(-) diff --git a/clang-tools-extra/clangd/index/Ref.cpp b/clang-tools-extra/clangd/index/Ref.cpp index edbfb95b528400..41bb3de7fb78a1 100644 --- a/clang-tools-extra/clangd/index/Ref.cpp +++ b/clang-tools-extra/clangd/index/Ref.cpp @@ -39,6 +39,45 @@ void RefSlab::Builder::insert(const SymbolID &ID, const Ref &S) { Entries.insert(std::move(E)); } +void RefSlab::BundleBuilder::insert(const SymbolID &ID, + llvm::ArrayRef<Ref> SymbolRefs) { + if (SymbolRefs.empty()) + return; + Ref *Copy = Arena.Allocate<Ref>(SymbolRefs.size()); + for (size_t I = 0; I < SymbolRefs.size(); ++I) { + Ref R = SymbolRefs[I]; + const char *&Interned = InternedURIs[R.Location.FileURI]; + if (!Interned) + Interned = UniqueStrings.save(R.Location.FileURI).data(); + R.Location.FileURI = Interned; + new (&Copy[I]) Ref(R); + } + llvm::MutableArrayRef<Ref> Stored(Copy, SymbolRefs.size()); + if (!llvm::is_sorted(Stored)) + llvm::sort(Stored); // By file, affects xrefs display order. + Refs.emplace_back(ID, Stored); + NumRefs += SymbolRefs.size(); +} + +RefSlab RefSlab::BundleBuilder::build() && { + // Keep the invariant of Builder: sorted by SymbolID, one entry per symbol. + if (!llvm::is_sorted(Refs, llvm::less_first())) + llvm::stable_sort(Refs, llvm::less_first()); + std::vector<value_type> Merged; + bool HasDuplicates = false; + for (size_t I = 1; I < Refs.size() && !HasDuplicates; ++I) + HasDuplicates = Refs[I - 1].first == Refs[I].first; + if (!HasDuplicates) + return RefSlab(std::move(Refs), std::move(Arena), NumRefs); + // Rare: the same symbol appeared in several bundles. Fall back to Builder, + // which also removes duplicate refs. + Builder B; + for (const auto &[ID, SymbolRefs] : Refs) + for (const Ref &R : SymbolRefs) + B.insert(ID, R); + return std::move(B).build(); +} + RefSlab RefSlab::Builder::build() && { std::vector<std::pair<SymbolID, llvm::ArrayRef<Ref>>> Result; // We'll reuse the arena, as it only has unique strings and we need them all. diff --git a/clang-tools-extra/clangd/index/Ref.h b/clang-tools-extra/clangd/index/Ref.h index b71f09611fed1f..d71d9c7ef916c0 100644 --- a/clang-tools-extra/clangd/index/Ref.h +++ b/clang-tools-extra/clangd/index/Ref.h @@ -11,6 +11,7 @@ #include "index/SymbolID.h" #include "index/SymbolLocation.h" +#include "llvm/ADT/DenseMap.h" #include "llvm/ADT/Hashing.h" #include "llvm/Support/Allocator.h" #include "llvm/Support/StringSaver.h" @@ -131,6 +132,26 @@ class RefSlab { sizeof(value_type) * Refs.capacity(); } + /// Builds a RefSlab from refs that are already grouped by symbol, such as + /// the ones read from an index file. Unlike Builder, does not deduplicate + /// individual refs, which makes it much cheaper. + class BundleBuilder { + public: + BundleBuilder() : UniqueStrings(Arena) {} + /// Adds all refs of \p ID. Deep copy: strings will be owned by the slab. + void insert(const SymbolID &ID, llvm::ArrayRef<Ref> SymbolRefs); + RefSlab build() &&; + + private: + llvm::BumpPtrAllocator Arena; + llvm::UniqueStringSaver UniqueStrings; // Contents on the arena. + /// Input FileURI pointer -> interned copy. The input usually points into + /// a string table, so most lookups hit without hashing the string. + llvm::DenseMap<const char *, const char *> InternedURIs; + std::vector<value_type> Refs; + size_t NumRefs = 0; + }; + /// RefSlab::Builder is a mutable container that can 'freeze' to RefSlab. class Builder { public: diff --git a/clang-tools-extra/clangd/index/Serialization.cpp b/clang-tools-extra/clangd/index/Serialization.cpp index 764ec7903aecb9..508c9783e74e0f 100644 --- a/clang-tools-extra/clangd/index/Serialization.cpp +++ b/clang-tools-extra/clangd/index/Serialization.cpp @@ -518,11 +518,10 @@ llvm::Expected<IndexFileIn> readRIFF(llvm::StringRef Data, } if (Chunks.count("refs")) { Reader RefsReader(Chunks.lookup("refs")); - RefSlab::Builder Refs; + RefSlab::BundleBuilder Refs; while (!RefsReader.eof()) { auto RefsBundle = readRefs(RefsReader, Strings->Strings); - for (const auto &Ref : RefsBundle.second) // FIXME: bulk insert? - Refs.insert(RefsBundle.first, Ref); + Refs.insert(RefsBundle.first, RefsBundle.second); } if (RefsReader.err()) return error("malformed or truncated refs"); diff --git a/clang-tools-extra/clangd/index/dex/Dex.h b/clang-tools-extra/clangd/index/dex/Dex.h index 1ea7d8c06c67c5..70551cbb140c04 100644 --- a/clang-tools-extra/clangd/index/dex/Dex.h +++ b/clang-tools-extra/clangd/index/dex/Dex.h @@ -41,8 +41,15 @@ class Dex : public SymbolIndex { : Corpus(0) { for (auto &&Sym : Symbols) this->Symbols.push_back(&Sym); - for (auto &&Ref : Refs) - this->Refs.try_emplace(Ref.first, Ref.second); + if constexpr (std::is_same_v<std::decay_t<RefsRange>, + decltype(this->Refs)> && + !std::is_lvalue_reference_v<RefsRange>) { + // Take over a map of the right type instead of rehashing every entry. + this->Refs = std::move(Refs); + } else { + for (auto &&Ref : Refs) + this->Refs.try_emplace(Ref.first, Ref.second); + } for (auto &&Rel : Relations) { this->Relations[std::make_pair(Rel.Subject, static_cast<uint8_t>(Rel.Predicate))] diff --git a/clang-tools-extra/clangd/unittests/IndexTests.cpp b/clang-tools-extra/clangd/unittests/IndexTests.cpp index a66680d39c87d2..3e790c0b4d8f19 100644 --- a/clang-tools-extra/clangd/unittests/IndexTests.cpp +++ b/clang-tools-extra/clangd/unittests/IndexTests.cpp @@ -514,6 +514,55 @@ TEST(MergeIndexTest, Refs) { fileURI("unittest:///test2.cc")))))); } +TEST(RefSlabTest, BundleBuilderMatchesBuilder) { + SymbolID A("a"), B("b"), C("c"); + std::string FileX = "file:///x.cc", FileY = "file:///y.cc"; + auto MakeRef = [](const std::string &File, uint32_t Line) { + Ref R; + R.Location.FileURI = File.c_str(); + R.Location.Start.setLine(Line); + R.Location.End.setLine(Line); + R.Kind = RefKind::Reference; + return R; + }; + // Bundles out of SymbolID order, refs out of order within a bundle, and + // symbol C split over two bundles that share a ref. + std::vector<std::pair<SymbolID, std::vector<Ref>>> Bundles = { + {B, {MakeRef(FileY, 2), MakeRef(FileX, 1)}}, + {C, {MakeRef(FileX, 5)}}, + {A, {MakeRef(FileX, 3)}}, + {C, {MakeRef(FileY, 4), MakeRef(FileX, 5)}}, + }; + auto Build = [&](bool WithDuplicateSymbol) { + RefSlab::Builder Expected; + RefSlab::BundleBuilder Actual; + for (const auto &[ID, Refs] : Bundles) { + if (!WithDuplicateSymbol && &Bundles.back().second == &Refs) + continue; + for (const Ref &R : Refs) + Expected.insert(ID, R); + Actual.insert(ID, Refs); + } + return std::make_pair(std::move(Expected).build(), + std::move(Actual).build()); + }; + for (bool WithDuplicateSymbol : {false, true}) { + auto [Expected, Actual] = Build(WithDuplicateSymbol); + // Strings must be owned by the slabs. + std::fill(FileX.begin(), FileX.end(), '?'); + std::fill(FileY.begin(), FileY.end(), '?'); + EXPECT_EQ(Expected.numRefs(), Actual.numRefs()); + ASSERT_EQ(Expected.size(), Actual.size()); + for (size_t I = 0; I < Expected.size(); ++I) { + auto ExpectedIt = Expected.begin() + I, ActualIt = Actual.begin() + I; + EXPECT_EQ(ExpectedIt->first, ActualIt->first); + EXPECT_EQ(ExpectedIt->second, ActualIt->second); + } + FileX = "file:///x.cc"; + FileY = "file:///y.cc"; + } +} + TEST(MergeIndexTest, IndexedFiles) { SymbolSlab DynSymbols; RefSlab DynRefs; >From 6212c7944b46adaedd8f4b752f3af2c236983ec6 Mon Sep 17 00:00:00 2001 From: Nikita Taranov <[email protected]> Date: Sun, 1 Nov 2026 19:10:57 +0000 Subject: [PATCH 2/6] [clangd] Intern ref file URIs by content in RefSlab::BundleBuilder `BundleBuilder` cached interned file URIs by the caller's pointer for its whole lifetime. A caller that reuses a buffer for a different URI got the first URI back, which breaks the deep-copy contract of `insert`. Intern by content, like `RefSlab::Builder` does. This costs about 0.1 s of the 4.4 s it takes to load a 950 MB index. Co-Authored-By: Claude Opus 5.5 <[email protected]> --- clang-tools-extra/clangd/index/Ref.cpp | 5 +---- clang-tools-extra/clangd/index/Ref.h | 4 ---- .../clangd/unittests/IndexTests.cpp | 20 +++++++++++++++++++ 3 files changed, 21 insertions(+), 8 deletions(-) diff --git a/clang-tools-extra/clangd/index/Ref.cpp b/clang-tools-extra/clangd/index/Ref.cpp index 41bb3de7fb78a1..9a2de4c834ebe5 100644 --- a/clang-tools-extra/clangd/index/Ref.cpp +++ b/clang-tools-extra/clangd/index/Ref.cpp @@ -46,10 +46,7 @@ void RefSlab::BundleBuilder::insert(const SymbolID &ID, Ref *Copy = Arena.Allocate<Ref>(SymbolRefs.size()); for (size_t I = 0; I < SymbolRefs.size(); ++I) { Ref R = SymbolRefs[I]; - const char *&Interned = InternedURIs[R.Location.FileURI]; - if (!Interned) - Interned = UniqueStrings.save(R.Location.FileURI).data(); - R.Location.FileURI = Interned; + R.Location.FileURI = UniqueStrings.save(R.Location.FileURI).data(); new (&Copy[I]) Ref(R); } llvm::MutableArrayRef<Ref> Stored(Copy, SymbolRefs.size()); diff --git a/clang-tools-extra/clangd/index/Ref.h b/clang-tools-extra/clangd/index/Ref.h index d71d9c7ef916c0..fcd0b6849dfc1d 100644 --- a/clang-tools-extra/clangd/index/Ref.h +++ b/clang-tools-extra/clangd/index/Ref.h @@ -11,7 +11,6 @@ #include "index/SymbolID.h" #include "index/SymbolLocation.h" -#include "llvm/ADT/DenseMap.h" #include "llvm/ADT/Hashing.h" #include "llvm/Support/Allocator.h" #include "llvm/Support/StringSaver.h" @@ -145,9 +144,6 @@ class RefSlab { private: llvm::BumpPtrAllocator Arena; llvm::UniqueStringSaver UniqueStrings; // Contents on the arena. - /// Input FileURI pointer -> interned copy. The input usually points into - /// a string table, so most lookups hit without hashing the string. - llvm::DenseMap<const char *, const char *> InternedURIs; std::vector<value_type> Refs; size_t NumRefs = 0; }; diff --git a/clang-tools-extra/clangd/unittests/IndexTests.cpp b/clang-tools-extra/clangd/unittests/IndexTests.cpp index 3e790c0b4d8f19..7f8df6d5cdabf5 100644 --- a/clang-tools-extra/clangd/unittests/IndexTests.cpp +++ b/clang-tools-extra/clangd/unittests/IndexTests.cpp @@ -563,6 +563,26 @@ TEST(RefSlabTest, BundleBuilderMatchesBuilder) { } } +TEST(RefSlabTest, BundleBuilderCopiesReusedBuffers) { + // The same buffer holds a different file URI for each insert. + char Buffer[] = "file:///x.cc"; + Ref R; + R.Location.FileURI = Buffer; + RefSlab::BundleBuilder Builder; + Builder.insert(SymbolID("a"), {R}); + Buffer[8] = 'y'; + Builder.insert(SymbolID("b"), {R}); + Buffer[8] = '?'; + RefSlab Slab = std::move(Builder).build(); + llvm::StringMap<SymbolID> FileToSymbol; + for (const auto &[ID, Refs] : Slab) + for (const Ref &Ref : Refs) + FileToSymbol.try_emplace(Ref.Location.FileURI, ID); + EXPECT_EQ(FileToSymbol.size(), 2u); + EXPECT_EQ(FileToSymbol.lookup("file:///x.cc"), SymbolID("a")); + EXPECT_EQ(FileToSymbol.lookup("file:///y.cc"), SymbolID("b")); +} + TEST(MergeIndexTest, IndexedFiles) { SymbolSlab DynSymbols; RefSlab DynRefs; >From 18f244b70b60b266377af482d10c9baac8a5556e Mon Sep 17 00:00:00 2001 From: Nikita Taranov <[email protected]> Date: Sun, 1 Nov 2026 19:26:29 +0000 Subject: [PATCH 3/6] [clangd] Forward the refs map into Dex instead of special-casing rvalues `std::forward` covers both cases: an rvalue map is moved, and an lvalue map of the same type is copied, which is still cheaper than re-inserting every entry. Co-Authored-By: Claude Opus 5.5 <[email protected]> --- clang-tools-extra/clangd/index/dex/Dex.h | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-) diff --git a/clang-tools-extra/clangd/index/dex/Dex.h b/clang-tools-extra/clangd/index/dex/Dex.h index 70551cbb140c04..1b9cbbb62b2050 100644 --- a/clang-tools-extra/clangd/index/dex/Dex.h +++ b/clang-tools-extra/clangd/index/dex/Dex.h @@ -42,10 +42,10 @@ class Dex : public SymbolIndex { for (auto &&Sym : Symbols) this->Symbols.push_back(&Sym); if constexpr (std::is_same_v<std::decay_t<RefsRange>, - decltype(this->Refs)> && - !std::is_lvalue_reference_v<RefsRange>) { - // Take over a map of the right type instead of rehashing every entry. - this->Refs = std::move(Refs); + decltype(this->Refs)>) { + // A map of the right type can be taken as is instead of rehashing every + // entry. + this->Refs = std::forward<RefsRange>(Refs); } else { for (auto &&Ref : Refs) this->Refs.try_emplace(Ref.first, Ref.second); >From a1ed6e4e85c74ca045514be643390a90a65d29f2 Mon Sep 17 00:00:00 2001 From: Nikita Taranov <[email protected]> Date: Sun, 1 Nov 2026 19:29:49 +0000 Subject: [PATCH 4/6] [clangd] Take the Dex refs fast path whenever the map is assignable Check that the refs argument can be assigned to the map instead of requiring the exact map type. `Dex::build` still passes a `RefSlab`, which is not assignable and keeps using the loop. Co-Authored-By: Claude Opus 5.5 <[email protected]> --- clang-tools-extra/clangd/index/dex/Dex.h | 6 ++---- 1 file changed, 2 insertions(+), 4 deletions(-) diff --git a/clang-tools-extra/clangd/index/dex/Dex.h b/clang-tools-extra/clangd/index/dex/Dex.h index 1b9cbbb62b2050..c106a16aba5c84 100644 --- a/clang-tools-extra/clangd/index/dex/Dex.h +++ b/clang-tools-extra/clangd/index/dex/Dex.h @@ -41,10 +41,8 @@ class Dex : public SymbolIndex { : Corpus(0) { for (auto &&Sym : Symbols) this->Symbols.push_back(&Sym); - if constexpr (std::is_same_v<std::decay_t<RefsRange>, - decltype(this->Refs)>) { - // A map of the right type can be taken as is instead of rehashing every - // entry. + if constexpr (std::is_assignable_v<decltype(this->Refs) &, RefsRange>) { + // Take a map that can be assigned as is instead of rehashing every entry. this->Refs = std::forward<RefsRange>(Refs); } else { for (auto &&Ref : Refs) >From 36239554a921bf5055e00f17d29c54763b62bbb4 Mon Sep 17 00:00:00 2001 From: Nikita Taranov <[email protected]> Date: Sun, 1 Nov 2026 19:51:01 +0000 Subject: [PATCH 5/6] [clangd] Require refs in RefSlab order instead of repairing them Refs in an index file are always written from a `RefSlab`: sorted by symbol, one bundle per symbol, each bundle sorted. `RefSlab::BundleBuilder` used to re-check and repair the order, and fall back to `RefSlab::Builder` for a repeated symbol, which never happens for files clangd writes. Make that order a precondition of `BundleBuilder`, and reject index files that violate it in `readRIFF` as malformed, like other inconsistencies there. Co-Authored-By: Claude Opus 5.5 <[email protected]> --- clang-tools-extra/clangd/index/Ref.cpp | 25 ++----- clang-tools-extra/clangd/index/Ref.h | 8 ++- .../clangd/index/Serialization.cpp | 8 +++ .../clangd/unittests/IndexTests.cpp | 72 +++++++++---------- .../clangd/unittests/SerializationTests.cpp | 25 +++++++ 5 files changed, 77 insertions(+), 61 deletions(-) diff --git a/clang-tools-extra/clangd/index/Ref.cpp b/clang-tools-extra/clangd/index/Ref.cpp index 9a2de4c834ebe5..5c431060494024 100644 --- a/clang-tools-extra/clangd/index/Ref.cpp +++ b/clang-tools-extra/clangd/index/Ref.cpp @@ -41,6 +41,9 @@ void RefSlab::Builder::insert(const SymbolID &ID, const Ref &S) { void RefSlab::BundleBuilder::insert(const SymbolID &ID, llvm::ArrayRef<Ref> SymbolRefs) { + assert((Refs.empty() || Refs.back().first < ID) && + "Symbols must be added in increasing order"); + assert(llvm::is_sorted(SymbolRefs) && "Refs of a symbol must be sorted"); if (SymbolRefs.empty()) return; Ref *Copy = Arena.Allocate<Ref>(SymbolRefs.size()); @@ -49,30 +52,12 @@ void RefSlab::BundleBuilder::insert(const SymbolID &ID, R.Location.FileURI = UniqueStrings.save(R.Location.FileURI).data(); new (&Copy[I]) Ref(R); } - llvm::MutableArrayRef<Ref> Stored(Copy, SymbolRefs.size()); - if (!llvm::is_sorted(Stored)) - llvm::sort(Stored); // By file, affects xrefs display order. - Refs.emplace_back(ID, Stored); + Refs.emplace_back(ID, llvm::ArrayRef<Ref>(Copy, SymbolRefs.size())); NumRefs += SymbolRefs.size(); } RefSlab RefSlab::BundleBuilder::build() && { - // Keep the invariant of Builder: sorted by SymbolID, one entry per symbol. - if (!llvm::is_sorted(Refs, llvm::less_first())) - llvm::stable_sort(Refs, llvm::less_first()); - std::vector<value_type> Merged; - bool HasDuplicates = false; - for (size_t I = 1; I < Refs.size() && !HasDuplicates; ++I) - HasDuplicates = Refs[I - 1].first == Refs[I].first; - if (!HasDuplicates) - return RefSlab(std::move(Refs), std::move(Arena), NumRefs); - // Rare: the same symbol appeared in several bundles. Fall back to Builder, - // which also removes duplicate refs. - Builder B; - for (const auto &[ID, SymbolRefs] : Refs) - for (const Ref &R : SymbolRefs) - B.insert(ID, R); - return std::move(B).build(); + return RefSlab(std::move(Refs), std::move(Arena), NumRefs); } RefSlab RefSlab::Builder::build() && { diff --git a/clang-tools-extra/clangd/index/Ref.h b/clang-tools-extra/clangd/index/Ref.h index fcd0b6849dfc1d..9d621de1c5cd7c 100644 --- a/clang-tools-extra/clangd/index/Ref.h +++ b/clang-tools-extra/clangd/index/Ref.h @@ -131,13 +131,15 @@ class RefSlab { sizeof(value_type) * Refs.capacity(); } - /// Builds a RefSlab from refs that are already grouped by symbol, such as - /// the ones read from an index file. Unlike Builder, does not deduplicate - /// individual refs, which makes it much cheaper. + /// Builds a RefSlab from refs that are already in RefSlab order, such as the + /// ones read from an index file. Much cheaper than Builder, which has to + /// group, deduplicate and sort refs one by one. class BundleBuilder { public: BundleBuilder() : UniqueStrings(Arena) {} /// Adds all refs of \p ID. Deep copy: strings will be owned by the slab. + /// Symbols must be added in strictly increasing order of their IDs, and + /// \p SymbolRefs must be sorted. void insert(const SymbolID &ID, llvm::ArrayRef<Ref> SymbolRefs); RefSlab build() &&; diff --git a/clang-tools-extra/clangd/index/Serialization.cpp b/clang-tools-extra/clangd/index/Serialization.cpp index 508c9783e74e0f..17f6354653f012 100644 --- a/clang-tools-extra/clangd/index/Serialization.cpp +++ b/clang-tools-extra/clangd/index/Serialization.cpp @@ -23,6 +23,7 @@ #include "llvm/Support/Error.h" #include "llvm/Support/raw_ostream.h" #include <cstdint> +#include <optional> #include <vector> namespace clang { @@ -519,8 +520,15 @@ llvm::Expected<IndexFileIn> readRIFF(llvm::StringRef Data, if (Chunks.count("refs")) { Reader RefsReader(Chunks.lookup("refs")); RefSlab::BundleBuilder Refs; + std::optional<SymbolID> PrevID; while (!RefsReader.eof()) { auto RefsBundle = readRefs(RefsReader, Strings->Strings); + // Refs are written from a RefSlab: sorted by symbol, one bundle per + // symbol, and each bundle sorted. + if ((PrevID && !(*PrevID < RefsBundle.first)) || + !llvm::is_sorted(RefsBundle.second)) + return error("malformed refs: not sorted or repeated symbol"); + PrevID = RefsBundle.first; Refs.insert(RefsBundle.first, RefsBundle.second); } if (RefsReader.err()) diff --git a/clang-tools-extra/clangd/unittests/IndexTests.cpp b/clang-tools-extra/clangd/unittests/IndexTests.cpp index 7f8df6d5cdabf5..4e66743b3cb03c 100644 --- a/clang-tools-extra/clangd/unittests/IndexTests.cpp +++ b/clang-tools-extra/clangd/unittests/IndexTests.cpp @@ -515,7 +515,6 @@ TEST(MergeIndexTest, Refs) { } TEST(RefSlabTest, BundleBuilderMatchesBuilder) { - SymbolID A("a"), B("b"), C("c"); std::string FileX = "file:///x.cc", FileY = "file:///y.cc"; auto MakeRef = [](const std::string &File, uint32_t Line) { Ref R; @@ -525,53 +524,50 @@ TEST(RefSlabTest, BundleBuilderMatchesBuilder) { R.Kind = RefKind::Reference; return R; }; - // Bundles out of SymbolID order, refs out of order within a bundle, and - // symbol C split over two bundles that share a ref. std::vector<std::pair<SymbolID, std::vector<Ref>>> Bundles = { - {B, {MakeRef(FileY, 2), MakeRef(FileX, 1)}}, - {C, {MakeRef(FileX, 5)}}, - {A, {MakeRef(FileX, 3)}}, - {C, {MakeRef(FileY, 4), MakeRef(FileX, 5)}}, + {SymbolID("a"), {MakeRef(FileX, 3)}}, + {SymbolID("b"), {MakeRef(FileY, 2), MakeRef(FileX, 1)}}, + {SymbolID("c"), {MakeRef(FileY, 4), MakeRef(FileX, 5)}}, }; - auto Build = [&](bool WithDuplicateSymbol) { - RefSlab::Builder Expected; - RefSlab::BundleBuilder Actual; - for (const auto &[ID, Refs] : Bundles) { - if (!WithDuplicateSymbol && &Bundles.back().second == &Refs) - continue; - for (const Ref &R : Refs) - Expected.insert(ID, R); - Actual.insert(ID, Refs); - } - return std::make_pair(std::move(Expected).build(), - std::move(Actual).build()); - }; - for (bool WithDuplicateSymbol : {false, true}) { - auto [Expected, Actual] = Build(WithDuplicateSymbol); - // Strings must be owned by the slabs. - std::fill(FileX.begin(), FileX.end(), '?'); - std::fill(FileY.begin(), FileY.end(), '?'); - EXPECT_EQ(Expected.numRefs(), Actual.numRefs()); - ASSERT_EQ(Expected.size(), Actual.size()); - for (size_t I = 0; I < Expected.size(); ++I) { - auto ExpectedIt = Expected.begin() + I, ActualIt = Actual.begin() + I; - EXPECT_EQ(ExpectedIt->first, ActualIt->first); - EXPECT_EQ(ExpectedIt->second, ActualIt->second); - } - FileX = "file:///x.cc"; - FileY = "file:///y.cc"; + // BundleBuilder takes refs in RefSlab order. + llvm::sort(Bundles, llvm::less_first()); + for (auto &[ID, Refs] : Bundles) + llvm::sort(Refs); + + RefSlab::Builder ExpectedBuilder; + RefSlab::BundleBuilder ActualBuilder; + for (const auto &[ID, Refs] : Bundles) { + for (const Ref &R : Refs) + ExpectedBuilder.insert(ID, R); + ActualBuilder.insert(ID, Refs); + } + RefSlab Expected = std::move(ExpectedBuilder).build(); + RefSlab Actual = std::move(ActualBuilder).build(); + // Strings must be owned by the slabs. + std::fill(FileX.begin(), FileX.end(), '?'); + std::fill(FileY.begin(), FileY.end(), '?'); + + EXPECT_EQ(Expected.numRefs(), Actual.numRefs()); + ASSERT_EQ(Expected.size(), Actual.size()); + for (size_t I = 0; I < Expected.size(); ++I) { + auto ExpectedIt = Expected.begin() + I, ActualIt = Actual.begin() + I; + EXPECT_EQ(ExpectedIt->first, ActualIt->first); + EXPECT_EQ(ExpectedIt->second, ActualIt->second); } } TEST(RefSlabTest, BundleBuilderCopiesReusedBuffers) { + SymbolID First("a"), Second("b"); + if (Second < First) + std::swap(First, Second); // The same buffer holds a different file URI for each insert. char Buffer[] = "file:///x.cc"; Ref R; R.Location.FileURI = Buffer; RefSlab::BundleBuilder Builder; - Builder.insert(SymbolID("a"), {R}); + Builder.insert(First, {R}); Buffer[8] = 'y'; - Builder.insert(SymbolID("b"), {R}); + Builder.insert(Second, {R}); Buffer[8] = '?'; RefSlab Slab = std::move(Builder).build(); llvm::StringMap<SymbolID> FileToSymbol; @@ -579,8 +575,8 @@ TEST(RefSlabTest, BundleBuilderCopiesReusedBuffers) { for (const Ref &Ref : Refs) FileToSymbol.try_emplace(Ref.Location.FileURI, ID); EXPECT_EQ(FileToSymbol.size(), 2u); - EXPECT_EQ(FileToSymbol.lookup("file:///x.cc"), SymbolID("a")); - EXPECT_EQ(FileToSymbol.lookup("file:///y.cc"), SymbolID("b")); + EXPECT_EQ(FileToSymbol.lookup("file:///x.cc"), First); + EXPECT_EQ(FileToSymbol.lookup("file:///y.cc"), Second); } TEST(MergeIndexTest, IndexedFiles) { diff --git a/clang-tools-extra/clangd/unittests/SerializationTests.cpp b/clang-tools-extra/clangd/unittests/SerializationTests.cpp index cbe2a9726f8656..358fddba1a33ad 100644 --- a/clang-tools-extra/clangd/unittests/SerializationTests.cpp +++ b/clang-tools-extra/clangd/unittests/SerializationTests.cpp @@ -543,6 +543,31 @@ TEST(SerializationTest, NoCrashOnBadArraySize) { "malformed or truncated include uri"); } +// Refs are written in RefSlab order: one bundle per symbol, sorted by symbol. +TEST(SerializationTest, RejectsRepeatedRefsBundle) { + auto In = readIndexFile(YAML); + ASSERT_FALSE(!In) << In.takeError(); + IndexFileOut Out(*In); + Out.Format = IndexFileFormat::RIFF; + std::string Serialized = llvm::to_string(Out); + ASSERT_FALSE(!readIndexFile(Serialized)); + + auto Parsed = riff::readFile(Serialized); + ASSERT_FALSE(!Parsed) << Parsed.takeError(); + auto Refs = llvm::find_if(Parsed->Chunks, [](riff::Chunk C) { + return C.ID == riff::fourCC("refs"); + }); + ASSERT_NE(Refs, Parsed->Chunks.end()); + // The fixture has refs for a single symbol; repeat its bundle. + std::string RepeatedRefs = (Refs->Data + Refs->Data).str(); + Refs->Data = RepeatedRefs; + + auto CorruptParsed = readIndexFile(llvm::to_string(*Parsed)); + ASSERT_TRUE(!CorruptParsed); + EXPECT_EQ(llvm::toString(CorruptParsed.takeError()), + "malformed refs: not sorted or repeated symbol"); +} + // Check we detect invalid string table size size without allocating it first. // If this detection fails, the test should allocate a huge array and crash. TEST(SerializationTest, NoCrashOnBadStringTableSize) { >From 4a730414f304d95c2accbf796632845db3fa4dfe Mon Sep 17 00:00:00 2001 From: Nikita Taranov <[email protected]> Date: Sun, 1 Nov 2026 21:02:54 +0000 Subject: [PATCH 6/6] [clangd] Check ref decoding errors first and accept refs in any order Two problems with the order check added to `readRIFF`: - It compared refs before checking `RefsReader.err()`. An out-of-range string index leaves a null file URI, and comparing two refs then calls `strcmp` on it. Check for decoding errors right after reading each bundle. - `SymbolID::operator<` compares the hash as a native integer, so `RefSlab` order depends on the host's endianness. A valid index written on a host of the other endianness has its refs in a different order and was rejected. `RefSlab::BundleBuilder` now puts bundles and refs in order when they are not, which costs one `is_sorted` pass for files written on the same host. A symbol with refs in more than one bundle is still rejected as malformed, since no host writes that. Co-Authored-By: Claude Opus 5.5 <[email protected]> --- clang-tools-extra/clangd/index/Ref.cpp | 10 ++- clang-tools-extra/clangd/index/Ref.h | 11 +-- .../clangd/index/Serialization.cpp | 18 ++--- .../clangd/unittests/IndexTests.cpp | 10 +-- .../clangd/unittests/SerializationTests.cpp | 78 +++++++++++++++---- 5 files changed, 89 insertions(+), 38 deletions(-) diff --git a/clang-tools-extra/clangd/index/Ref.cpp b/clang-tools-extra/clangd/index/Ref.cpp index 5c431060494024..a28450423a20cd 100644 --- a/clang-tools-extra/clangd/index/Ref.cpp +++ b/clang-tools-extra/clangd/index/Ref.cpp @@ -41,9 +41,6 @@ void RefSlab::Builder::insert(const SymbolID &ID, const Ref &S) { void RefSlab::BundleBuilder::insert(const SymbolID &ID, llvm::ArrayRef<Ref> SymbolRefs) { - assert((Refs.empty() || Refs.back().first < ID) && - "Symbols must be added in increasing order"); - assert(llvm::is_sorted(SymbolRefs) && "Refs of a symbol must be sorted"); if (SymbolRefs.empty()) return; Ref *Copy = Arena.Allocate<Ref>(SymbolRefs.size()); @@ -52,11 +49,16 @@ void RefSlab::BundleBuilder::insert(const SymbolID &ID, R.Location.FileURI = UniqueStrings.save(R.Location.FileURI).data(); new (&Copy[I]) Ref(R); } - Refs.emplace_back(ID, llvm::ArrayRef<Ref>(Copy, SymbolRefs.size())); + llvm::MutableArrayRef<Ref> Stored(Copy, SymbolRefs.size()); + if (!llvm::is_sorted(Stored)) + llvm::sort(Stored); // By file, affects xrefs display order. + Refs.emplace_back(ID, Stored); NumRefs += SymbolRefs.size(); } RefSlab RefSlab::BundleBuilder::build() && { + if (!llvm::is_sorted(Refs, llvm::less_first())) + llvm::sort(Refs, llvm::less_first()); return RefSlab(std::move(Refs), std::move(Arena), NumRefs); } diff --git a/clang-tools-extra/clangd/index/Ref.h b/clang-tools-extra/clangd/index/Ref.h index 9d621de1c5cd7c..8422e63629640c 100644 --- a/clang-tools-extra/clangd/index/Ref.h +++ b/clang-tools-extra/clangd/index/Ref.h @@ -131,15 +131,16 @@ class RefSlab { sizeof(value_type) * Refs.capacity(); } - /// Builds a RefSlab from refs that are already in RefSlab order, such as the - /// ones read from an index file. Much cheaper than Builder, which has to - /// group, deduplicate and sort refs one by one. + /// Builds a RefSlab from refs that are already grouped by symbol, such as + /// the ones read from an index file. Much cheaper than Builder, which has to + /// group and deduplicate refs one by one. Bundles are put in RefSlab order + /// if needed: that order depends on the host (SymbolID's operator< does), + /// so a file written elsewhere may differ. class BundleBuilder { public: BundleBuilder() : UniqueStrings(Arena) {} /// Adds all refs of \p ID. Deep copy: strings will be owned by the slab. - /// Symbols must be added in strictly increasing order of their IDs, and - /// \p SymbolRefs must be sorted. + /// Each symbol may be added only once. void insert(const SymbolID &ID, llvm::ArrayRef<Ref> SymbolRefs); RefSlab build() &&; diff --git a/clang-tools-extra/clangd/index/Serialization.cpp b/clang-tools-extra/clangd/index/Serialization.cpp index 17f6354653f012..5ee804693a5ecb 100644 --- a/clang-tools-extra/clangd/index/Serialization.cpp +++ b/clang-tools-extra/clangd/index/Serialization.cpp @@ -23,7 +23,6 @@ #include "llvm/Support/Error.h" #include "llvm/Support/raw_ostream.h" #include <cstdint> -#include <optional> #include <vector> namespace clang { @@ -520,20 +519,19 @@ llvm::Expected<IndexFileIn> readRIFF(llvm::StringRef Data, if (Chunks.count("refs")) { Reader RefsReader(Chunks.lookup("refs")); RefSlab::BundleBuilder Refs; - std::optional<SymbolID> PrevID; while (!RefsReader.eof()) { auto RefsBundle = readRefs(RefsReader, Strings->Strings); - // Refs are written from a RefSlab: sorted by symbol, one bundle per - // symbol, and each bundle sorted. - if ((PrevID && !(*PrevID < RefsBundle.first)) || - !llvm::is_sorted(RefsBundle.second)) - return error("malformed refs: not sorted or repeated symbol"); - PrevID = RefsBundle.first; + // Check before using the refs: a bad string index leaves a null URI. + if (RefsReader.err()) + return error("malformed or truncated refs"); Refs.insert(RefsBundle.first, RefsBundle.second); } - if (RefsReader.err()) - return error("malformed or truncated refs"); Result.Refs = std::move(Refs).build(); + // Refs are written from a RefSlab, which has one bundle per symbol. + if (llvm::adjacent_find(*Result.Refs, [](const auto &L, const auto &R) { + return L.first == R.first; + }) != Result.Refs->end()) + return error("malformed refs: repeated symbol"); } if (Chunks.count("rela")) { Reader RelationsReader(Chunks.lookup("rela")); diff --git a/clang-tools-extra/clangd/unittests/IndexTests.cpp b/clang-tools-extra/clangd/unittests/IndexTests.cpp index 4e66743b3cb03c..096e58c32540f7 100644 --- a/clang-tools-extra/clangd/unittests/IndexTests.cpp +++ b/clang-tools-extra/clangd/unittests/IndexTests.cpp @@ -529,10 +529,12 @@ TEST(RefSlabTest, BundleBuilderMatchesBuilder) { {SymbolID("b"), {MakeRef(FileY, 2), MakeRef(FileX, 1)}}, {SymbolID("c"), {MakeRef(FileY, 4), MakeRef(FileX, 5)}}, }; - // BundleBuilder takes refs in RefSlab order. - llvm::sort(Bundles, llvm::less_first()); + // The order of a file written on another host may differ from ours: give + // BundleBuilder bundles in decreasing order and refs out of order. + llvm::sort(Bundles, + [](const auto &L, const auto &R) { return R.first < L.first; }); for (auto &[ID, Refs] : Bundles) - llvm::sort(Refs); + llvm::sort(Refs, [](const Ref &L, const Ref &R) { return R < L; }); RefSlab::Builder ExpectedBuilder; RefSlab::BundleBuilder ActualBuilder; @@ -558,8 +560,6 @@ TEST(RefSlabTest, BundleBuilderMatchesBuilder) { TEST(RefSlabTest, BundleBuilderCopiesReusedBuffers) { SymbolID First("a"), Second("b"); - if (Second < First) - std::swap(First, Second); // The same buffer holds a different file URI for each insert. char Buffer[] = "file:///x.cc"; Ref R; diff --git a/clang-tools-extra/clangd/unittests/SerializationTests.cpp b/clang-tools-extra/clangd/unittests/SerializationTests.cpp index 358fddba1a33ad..4789d14432677d 100644 --- a/clang-tools-extra/clangd/unittests/SerializationTests.cpp +++ b/clang-tools-extra/clangd/unittests/SerializationTests.cpp @@ -543,29 +543,79 @@ TEST(SerializationTest, NoCrashOnBadArraySize) { "malformed or truncated include uri"); } -// Refs are written in RefSlab order: one bundle per symbol, sorted by symbol. -TEST(SerializationTest, RejectsRepeatedRefsBundle) { +// Serializes the YAML fixture as RIFF, replaces its refs chunk with the result +// of Edit, and reads the edited file back. +llvm::Expected<IndexFileIn> +readWithEditedRefs(llvm::function_ref<std::string(llvm::StringRef)> Edit) { auto In = readIndexFile(YAML); - ASSERT_FALSE(!In) << In.takeError(); + if (!In) + return In.takeError(); IndexFileOut Out(*In); Out.Format = IndexFileFormat::RIFF; std::string Serialized = llvm::to_string(Out); - ASSERT_FALSE(!readIndexFile(Serialized)); - auto Parsed = riff::readFile(Serialized); - ASSERT_FALSE(!Parsed) << Parsed.takeError(); + if (!Parsed) + return Parsed.takeError(); auto Refs = llvm::find_if(Parsed->Chunks, [](riff::Chunk C) { return C.ID == riff::fourCC("refs"); }); - ASSERT_NE(Refs, Parsed->Chunks.end()); - // The fixture has refs for a single symbol; repeat its bundle. - std::string RepeatedRefs = (Refs->Data + Refs->Data).str(); - Refs->Data = RepeatedRefs; + if (Refs == Parsed->Chunks.end()) + return llvm::createStringError("no refs chunk"); + std::string Edited = Edit(Refs->Data); + Refs->Data = Edited; + return readIndexFile(llvm::to_string(*Parsed)); +} - auto CorruptParsed = readIndexFile(llvm::to_string(*Parsed)); - ASSERT_TRUE(!CorruptParsed); - EXPECT_EQ(llvm::toString(CorruptParsed.takeError()), - "malformed refs: not sorted or repeated symbol"); +// The fixture's refs chunk is a single bundle: an 8-byte SymbolID, the number +// of refs (1, as a one-byte varint), then the ref. +constexpr size_t RefsBundleHeaderSize = SymbolID::RawSize + 1; + +TEST(SerializationTest, RejectsRepeatedRefsBundle) { + auto Read = readWithEditedRefs( + [](llvm::StringRef Refs) { return (Refs + Refs).str(); }); + ASSERT_TRUE(!Read); + EXPECT_EQ(llvm::toString(Read.takeError()), + "malformed refs: repeated symbol"); +} + +TEST(SerializationTest, NoCrashOnBadRefsFileURI) { + // Give the bundle a second ref whose file URI is not in the string table. + auto Read = readWithEditedRefs([](llvm::StringRef Refs) { + llvm::StringRef ID = Refs.take_front(SymbolID::RawSize); + llvm::StringRef Ref = Refs.drop_front(RefsBundleHeaderSize); + EXPECT_EQ(Refs[SymbolID::RawSize], 1); + // A ref is: 1 byte kind, varint(stringID) file URI, ... We need the URI to + // be encoded in one byte to replace it. + EXPECT_LT(static_cast<uint8_t>(Ref[1]), 0x80); + std::string BadRef = + (Ref.take_front(1) + llvm::fromHex("ffffffff0f") + Ref.drop_front(2)) + .str(); + return (ID + "\x02" + Ref + BadRef).str(); + }); + ASSERT_TRUE(!Read); + EXPECT_EQ(llvm::toString(Read.takeError()), "malformed or truncated refs"); +} + +// SymbolID order depends on the host's endianness, so a valid index written on +// another host can have its refs in a different order. +TEST(SerializationTest, AcceptsRefsBundlesInAnyOrder) { + SymbolID First, Second; + auto Read = readWithEditedRefs([&](llvm::StringRef Refs) { + std::string OtherID = Refs.take_front(SymbolID::RawSize).str(); + OtherID.back() ^= 1; + SymbolID A = SymbolID::fromRaw(Refs.take_front(SymbolID::RawSize)); + SymbolID B = SymbolID::fromRaw(OtherID); + std::tie(First, Second) = A < B ? std::tie(A, B) : std::tie(B, A); + // Write the bundles in decreasing order for this host. + llvm::StringRef Rest = Refs.drop_front(SymbolID::RawSize); + return (llvm::StringRef(Second.raw()) + Rest + First.raw() + Rest).str(); + }); + ASSERT_FALSE(!Read) << Read.takeError(); + ASSERT_TRUE(Read->Refs); + std::vector<SymbolID> IDs; + for (const auto &[ID, Refs] : *Read->Refs) + IDs.push_back(ID); + EXPECT_THAT(IDs, ElementsAre(First, Second)); } // Check we detect invalid string table size size without allocating it first. _______________________________________________ cfe-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
