Add a fuzztest for StableBlockList. The test verifies that StableBlockList is a drop in replacement of std::list, for the operations supported by the former. See the file comment of stable_block_list_fuzz_test.cc for details. PiperOrigin-RevId: 964912944
diff --git a/build/source_list.bzl b/build/source_list.bzl index d810ecd..f60d6dc 100644 --- a/build/source_list.bzl +++ b/build/source_list.bzl
@@ -1169,6 +1169,7 @@ "common/quiche_text_utils_test.cc", "common/quiche_weak_ptr_test.cc", "common/simple_buffer_allocator_test.cc", + "common/stable_block_list_fuzz_test.cc", "common/stable_block_list_test.cc", "common/structured_headers_generated_test.cc", "common/structured_headers_test.cc",
diff --git a/build/source_list.gni b/build/source_list.gni index b4ac905..610ae26 100644 --- a/build/source_list.gni +++ b/build/source_list.gni
@@ -1171,6 +1171,7 @@ "src/quiche/common/quiche_text_utils_test.cc", "src/quiche/common/quiche_weak_ptr_test.cc", "src/quiche/common/simple_buffer_allocator_test.cc", + "src/quiche/common/stable_block_list_fuzz_test.cc", "src/quiche/common/stable_block_list_test.cc", "src/quiche/common/structured_headers_generated_test.cc", "src/quiche/common/structured_headers_test.cc",
diff --git a/build/source_list.json b/build/source_list.json index f27cc10..80c06ac 100644 --- a/build/source_list.json +++ b/build/source_list.json
@@ -1170,6 +1170,7 @@ "quiche/common/quiche_text_utils_test.cc", "quiche/common/quiche_weak_ptr_test.cc", "quiche/common/simple_buffer_allocator_test.cc", + "quiche/common/stable_block_list_fuzz_test.cc", "quiche/common/stable_block_list_test.cc", "quiche/common/structured_headers_generated_test.cc", "quiche/common/structured_headers_test.cc",
diff --git a/quiche/common/stable_block_list_fuzz_test.cc b/quiche/common/stable_block_list_fuzz_test.cc new file mode 100644 index 0000000..d639b69 --- /dev/null +++ b/quiche/common/stable_block_list_fuzz_test.cc
@@ -0,0 +1,447 @@ +// Copyright (c) 2026 The Chromium Authors. All rights reserved. +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. + +// Differential property-based fuzz test comparing quiche::StableBlockList +// against std::list. +// +// The test executes randomized sequences of container operations (push_back, +// emplace_back, insert at end, single-element erase, range erase including +// empty ranges, pop_front, pop_back, clear, shrink_to_fit, move, and swap) +// across various block capacities (1, 2, 4, 16, 32, 64). +// +// After every operation, it rigorously verifies container invariants: +// - Element order, empty(), and size() parity with std::list. +// - Forward and reverse iterator traversal parity. +// - Bidirectional iterator step navigation across erased holes and block +// boundaries. +// - Pointer and reference stability: surviving element addresses remain +// stable across arbitrary insertions, deletions, block deallocations, and +// memory shrink operations. +// - Iterator stability: saved iterators to surviving elements remain valid, +// dereference to the correct values, and step correctly to surviving +// neighbors. + +#include <cstddef> +#include <iterator> +#include <list> +#include <utility> +#include <variant> +#include <vector> + +#include "absl/functional/overload.h" +#include "quiche/common/platform/api/quiche_fuzztest.h" +#include "quiche/common/platform/api/quiche_test.h" +#include "quiche/common/stable_block_list.h" + +namespace quiche { +namespace { + +using ::fuzztest::Arbitrary; +using ::fuzztest::Domain; +using ::fuzztest::VariantOf; +using ::fuzztest::VectorOf; + +struct PushBackOp { + int value; +}; +struct EmplaceBackOp { + int value; +}; +struct InsertEndOp { + int value; +}; +struct EraseIndexOp { + size_t index; +}; +struct EraseRangeOp { + size_t start_index; + size_t count; +}; +struct PopFrontOp {}; +struct PopBackOp {}; +struct ClearOp {}; +struct ShrinkToFitOp {}; +struct MoveOp {}; +struct SwapOp {}; + +using Op = std::variant<PushBackOp, EmplaceBackOp, InsertEndOp, EraseIndexOp, + EraseRangeOp, PopFrontOp, PopBackOp, ClearOp, + ShrinkToFitOp, MoveOp, SwapOp>; + +Domain<Op> AnyOpDomain() { + return VariantOf(Arbitrary<PushBackOp>(), Arbitrary<EmplaceBackOp>(), + Arbitrary<InsertEndOp>(), Arbitrary<EraseIndexOp>(), + Arbitrary<EraseRangeOp>(), Arbitrary<PopFrontOp>(), + Arbitrary<PopBackOp>(), Arbitrary<ClearOp>(), + Arbitrary<ShrinkToFitOp>(), Arbitrary<MoveOp>(), + Arbitrary<SwapOp>()); +} + +template <size_t BlockCapacity> +struct ElementTracker { + int value; + const int* sbl_ptr; + typename StableBlockList<int, BlockCapacity>::iterator sbl_it; + const int* std_ptr; + std::list<int>::iterator std_it; +}; + +template <size_t BlockCapacity> +void VerifyInvariants( + const StableBlockList<int, BlockCapacity>& sbl, + const std::list<int>& std_list, + const std::vector<ElementTracker<BlockCapacity>>& active_trackers) { + // 1. Size & Empty parity + ASSERT_EQ(sbl.size(), std_list.size()); + ASSERT_EQ(sbl.size(), active_trackers.size()); + ASSERT_EQ(sbl.empty(), std_list.empty()); + ASSERT_EQ(sbl.empty(), active_trackers.empty()); + + if (sbl.empty()) { + EXPECT_TRUE(sbl.begin() == sbl.end()); + EXPECT_TRUE(sbl.cbegin() == sbl.cend()); + EXPECT_TRUE(sbl.rbegin() == sbl.rend()); + EXPECT_TRUE(sbl.crbegin() == sbl.crend()); + return; + } + + // 2. Front & Back parity + EXPECT_EQ(sbl.front(), std_list.front()); + EXPECT_EQ(sbl.front(), active_trackers.front().value); + EXPECT_EQ(sbl.back(), std_list.back()); + EXPECT_EQ(sbl.back(), active_trackers.back().value); + + // 3. Forward iterator traversal and element order + auto sbl_it = sbl.begin(); + auto std_it = std_list.begin(); + size_t idx = 0; + while (sbl_it != sbl.end() && std_it != std_list.end()) { + EXPECT_EQ(*sbl_it, *std_it); + EXPECT_EQ(*sbl_it, active_trackers[idx].value); + EXPECT_EQ(&*sbl_it, active_trackers[idx].sbl_ptr); + EXPECT_EQ(&*std_it, active_trackers[idx].std_ptr); + EXPECT_TRUE(sbl_it == active_trackers[idx].sbl_it); + EXPECT_TRUE(std_it == active_trackers[idx].std_it); + ++sbl_it; + ++std_it; + ++idx; + } + EXPECT_TRUE(sbl_it == sbl.end()); + EXPECT_TRUE(std_it == std_list.end()); + EXPECT_EQ(idx, active_trackers.size()); + + // 4. Const forward iterator traversal + auto sbl_cit = sbl.cbegin(); + auto std_cit = std_list.cbegin(); + size_t cidx = 0; + while (sbl_cit != sbl.cend() && std_cit != std_list.cend()) { + EXPECT_EQ(*sbl_cit, *std_cit); + EXPECT_EQ(*sbl_cit, active_trackers[cidx].value); + EXPECT_EQ(&*sbl_cit, active_trackers[cidx].sbl_ptr); + EXPECT_EQ(&*std_cit, active_trackers[cidx].std_ptr); + ++sbl_cit; + ++std_cit; + ++cidx; + } + EXPECT_TRUE(sbl_cit == sbl.cend()); + EXPECT_TRUE(std_cit == std_list.cend()); + EXPECT_EQ(cidx, active_trackers.size()); + + // 5. Reverse iterator traversal + auto sbl_rit = sbl.rbegin(); + auto std_rit = std_list.rbegin(); + size_t ridx = active_trackers.size(); + while (sbl_rit != sbl.rend() && std_rit != std_list.rend()) { + --ridx; + EXPECT_EQ(*sbl_rit, *std_rit); + EXPECT_EQ(*sbl_rit, active_trackers[ridx].value); + EXPECT_EQ(&*sbl_rit, active_trackers[ridx].sbl_ptr); + EXPECT_EQ(&*std_rit, active_trackers[ridx].std_ptr); + ++sbl_rit; + ++std_rit; + } + EXPECT_TRUE(sbl_rit == sbl.rend()); + EXPECT_TRUE(std_rit == std_list.rend()); + EXPECT_EQ(ridx, 0); + + // 6. Const reverse iterator traversal + auto sbl_crit = sbl.crbegin(); + auto std_crit = std_list.crbegin(); + size_t cridx = active_trackers.size(); + while (sbl_crit != sbl.crend() && std_crit != std_list.crend()) { + --cridx; + EXPECT_EQ(*sbl_crit, *std_crit); + EXPECT_EQ(*sbl_crit, active_trackers[cridx].value); + EXPECT_EQ(&*sbl_crit, active_trackers[cridx].sbl_ptr); + EXPECT_EQ(&*std_crit, active_trackers[cridx].std_ptr); + ++sbl_crit; + ++std_crit; + } + EXPECT_TRUE(sbl_crit == sbl.crend()); + EXPECT_TRUE(std_crit == std_list.crend()); + EXPECT_EQ(cridx, 0); + + // 7. Bidirectional stepping (decrementing from end()) + { + auto b_sbl_it = sbl.end(); + auto b_std_it = std_list.end(); + size_t b_idx = active_trackers.size(); + do { + --b_sbl_it; + --b_std_it; + --b_idx; + EXPECT_EQ(*b_sbl_it, *b_std_it); + EXPECT_EQ(*b_sbl_it, active_trackers[b_idx].value); + EXPECT_EQ(&*b_sbl_it, active_trackers[b_idx].sbl_ptr); + EXPECT_EQ(&*b_std_it, active_trackers[b_idx].std_ptr); + } while (b_sbl_it != sbl.begin() && b_std_it != std_list.begin()); + EXPECT_TRUE(b_sbl_it == sbl.begin()); + EXPECT_TRUE(b_std_it == std_list.begin()); + EXPECT_EQ(b_idx, 0); + } + + // 8. Individual pointer & iterator stability and neighbor connectivity + for (size_t i = 0; i < active_trackers.size(); ++i) { + const auto& tracker = active_trackers[i]; + EXPECT_EQ(*tracker.sbl_ptr, tracker.value); + EXPECT_EQ(*tracker.std_ptr, tracker.value); + EXPECT_EQ(*tracker.sbl_it, tracker.value); + EXPECT_EQ(*tracker.std_it, tracker.value); + EXPECT_EQ(&*tracker.sbl_it, tracker.sbl_ptr); + EXPECT_EQ(&*tracker.std_it, tracker.std_ptr); + + if (i + 1 < active_trackers.size()) { + EXPECT_TRUE(std::next(tracker.sbl_it) == active_trackers[i + 1].sbl_it); + EXPECT_TRUE(std::next(tracker.std_it) == active_trackers[i + 1].std_it); + } else { + EXPECT_TRUE(std::next(tracker.sbl_it) == sbl.end()); + EXPECT_TRUE(std::next(tracker.std_it) == std_list.end()); + } + + if (i > 0) { + EXPECT_TRUE(std::prev(tracker.sbl_it) == active_trackers[i - 1].sbl_it); + EXPECT_TRUE(std::prev(tracker.std_it) == active_trackers[i - 1].std_it); + } else { + EXPECT_TRUE(tracker.sbl_it == sbl.begin()); + EXPECT_TRUE(tracker.std_it == std_list.begin()); + } + } +} + +template <size_t BlockCapacity> +void StableBlockListMatchesStdList(const std::vector<Op>& ops) { + StableBlockList<int, BlockCapacity> sbl; + std::list<int> std_list; + std::vector<ElementTracker<BlockCapacity>> active_trackers; + + StableBlockList<int, BlockCapacity> secondary_sbl; + std::list<int> secondary_std; + std::vector<ElementTracker<BlockCapacity>> secondary_trackers; + + VerifyInvariants(sbl, std_list, active_trackers); + + for (const Op& op : ops) { + std::visit( + absl::Overload{ + [&](const PushBackOp& op) { + sbl.push_back(op.value); + std_list.push_back(op.value); + auto sbl_it = std::prev(sbl.end()); + auto std_it = std::prev(std_list.end()); + active_trackers.push_back( + {op.value, &*sbl_it, sbl_it, &*std_it, std_it}); + }, + [&](const EmplaceBackOp& op) { + auto sbl_it = sbl.emplace(sbl.end(), op.value); + auto std_it = std_list.emplace(std_list.end(), op.value); + active_trackers.push_back( + {op.value, &*sbl_it, sbl_it, &*std_it, std_it}); + }, + [&](const InsertEndOp& op) { + auto sbl_it = sbl.insert(sbl.end(), op.value); + auto std_it = std_list.insert(std_list.end(), op.value); + active_trackers.push_back( + {op.value, &*sbl_it, sbl_it, &*std_it, std_it}); + }, + [&](const EraseIndexOp& op) { + if (active_trackers.empty()) { + return; + } + size_t target_idx = op.index % active_trackers.size(); + auto sbl_ret = sbl.erase(active_trackers[target_idx].sbl_it); + auto std_ret = std_list.erase(active_trackers[target_idx].std_it); + if (target_idx + 1 < active_trackers.size()) { + EXPECT_EQ(*sbl_ret, *std_ret); + EXPECT_EQ(*sbl_ret, active_trackers[target_idx + 1].value); + } else { + EXPECT_TRUE(sbl_ret == sbl.end()); + EXPECT_TRUE(std_ret == std_list.end()); + } + active_trackers.erase(active_trackers.begin() + target_idx); + }, + [&](const EraseRangeOp& op) { + if (active_trackers.empty()) { + auto sbl_ret = sbl.erase(sbl.begin(), sbl.end()); + auto std_ret = std_list.erase(std_list.begin(), std_list.end()); + EXPECT_TRUE(sbl_ret == sbl.end()); + EXPECT_TRUE(std_ret == std_list.end()); + return; + } + size_t start = op.start_index % (active_trackers.size() + 1); + size_t max_count = active_trackers.size() - start; + size_t num_to_erase = op.count % (max_count + 1); + + auto sbl_first = (start == active_trackers.size()) + ? sbl.end() + : active_trackers[start].sbl_it; + auto std_first = (start == active_trackers.size()) + ? std_list.end() + : active_trackers[start].std_it; + auto sbl_last = + (start + num_to_erase == active_trackers.size()) + ? sbl.end() + : active_trackers[start + num_to_erase].sbl_it; + auto std_last = + (start + num_to_erase == active_trackers.size()) + ? std_list.end() + : active_trackers[start + num_to_erase].std_it; + auto sbl_ret = sbl.erase(sbl_first, sbl_last); + auto std_ret = std_list.erase(std_first, std_last); + if (start + num_to_erase < active_trackers.size()) { + EXPECT_EQ(*sbl_ret, *std_ret); + EXPECT_EQ(*sbl_ret, + active_trackers[start + num_to_erase].value); + } else { + EXPECT_TRUE(sbl_ret == sbl.end()); + EXPECT_TRUE(std_ret == std_list.end()); + } + active_trackers.erase( + active_trackers.begin() + start, + active_trackers.begin() + start + num_to_erase); + }, + [&](const PopFrontOp&) { + if (active_trackers.empty()) { + return; + } + sbl.erase(sbl.begin()); + std_list.pop_front(); + active_trackers.erase(active_trackers.begin()); + }, + [&](const PopBackOp&) { + if (active_trackers.empty()) { + return; + } + sbl.erase(std::prev(sbl.end())); + std_list.pop_back(); + active_trackers.pop_back(); + }, + [&](const ClearOp&) { + sbl.clear(); + std_list.clear(); + active_trackers.clear(); + }, + [&](const ShrinkToFitOp&) { sbl.shrink_to_fit(); }, + [&](const MoveOp&) { + StableBlockList<int, BlockCapacity> temp_sbl = std::move(sbl); + std::list<int> temp_std = std::move(std_list); + sbl = std::move(temp_sbl); + std_list = std::move(temp_std); + }, + [&](const SwapOp&) { + sbl.swap(secondary_sbl); + std_list.swap(secondary_std); + active_trackers.swap(secondary_trackers); + }, + }, + op); + + VerifyInvariants(sbl, std_list, active_trackers); + VerifyInvariants(secondary_sbl, secondary_std, secondary_trackers); + } +} + +void StableBlockListMatchesStdListCap1( + const std::vector<Op>& ops) { // NOLINT(readability-redundant-declaration) + StableBlockListMatchesStdList<1>(ops); +} + +void StableBlockListMatchesStdListCap2( + const std::vector<Op>& ops) { // NOLINT(readability-redundant-declaration) + StableBlockListMatchesStdList<2>(ops); +} + +void StableBlockListMatchesStdListCap4( + const std::vector<Op>& ops) { // NOLINT(readability-redundant-declaration) + StableBlockListMatchesStdList<4>(ops); +} + +void StableBlockListMatchesStdListCap16( + const std::vector<Op>& ops) { // NOLINT(readability-redundant-declaration) + StableBlockListMatchesStdList<16>(ops); +} + +void StableBlockListMatchesStdListCap32( + const std::vector<Op>& ops) { // NOLINT(readability-redundant-declaration) + StableBlockListMatchesStdList<32>(ops); +} + +void StableBlockListMatchesStdListCap64( + const std::vector<Op>& ops) { // NOLINT(readability-redundant-declaration) + StableBlockListMatchesStdList<64>(ops); +} + +FUZZ_TEST(StableBlockListFuzzTest, // NOLINT(readability-redundant-declaration) + StableBlockListMatchesStdListCap1) + .WithDomains(VectorOf(AnyOpDomain()).WithMinSize(100)); + +FUZZ_TEST(StableBlockListFuzzTest, // NOLINT(readability-redundant-declaration) + StableBlockListMatchesStdListCap2) + .WithDomains(VectorOf(AnyOpDomain()).WithMinSize(100)); + +FUZZ_TEST(StableBlockListFuzzTest, // NOLINT(readability-redundant-declaration) + StableBlockListMatchesStdListCap4) + .WithDomains(VectorOf(AnyOpDomain()).WithMinSize(100)); + +FUZZ_TEST(StableBlockListFuzzTest, // NOLINT(readability-redundant-declaration) + StableBlockListMatchesStdListCap16) + .WithDomains(VectorOf(AnyOpDomain()).WithMinSize(100)); + +FUZZ_TEST(StableBlockListFuzzTest, // NOLINT(readability-redundant-declaration) + StableBlockListMatchesStdListCap32) + .WithDomains(VectorOf(AnyOpDomain()).WithMinSize(100)); + +FUZZ_TEST(StableBlockListFuzzTest, // NOLINT(readability-redundant-declaration) + StableBlockListMatchesStdListCap64) + .WithDomains(VectorOf(AnyOpDomain()).WithMinSize(100)); + +TEST(StableBlockListFuzzTest, DeterministicBasicParity) { + std::vector<Op> ops = { + PushBackOp{10}, PushBackOp{20}, PushBackOp{30}, PopFrontOp{}, + PushBackOp{40}, EraseIndexOp{0}, InsertEndOp{50}, EmplaceBackOp{60}, + EraseRangeOp{0, 2}, ShrinkToFitOp{}, ClearOp{}, PushBackOp{70}, + }; + StableBlockListMatchesStdList<4>(ops); + StableBlockListMatchesStdList<16>(ops); +} + +TEST(StableBlockListFuzzTest, EmptyRangeErasureParity) { + std::vector<Op> ops = { + EraseRangeOp{0, 0}, // On empty container + PushBackOp{10}, PushBackOp{20}, + PushBackOp{30}, EraseRangeOp{0, 0}, // Empty range at begin + EraseRangeOp{1, 0}, // Empty range in middle + EraseRangeOp{2, 0}, // Empty range before end + EraseRangeOp{3, 0}, // Empty range at end + PushBackOp{40}, + }; + StableBlockListMatchesStdList<1>(ops); + StableBlockListMatchesStdList<2>(ops); + StableBlockListMatchesStdList<4>(ops); + StableBlockListMatchesStdList<16>(ops); + StableBlockListMatchesStdList<32>(ops); + StableBlockListMatchesStdList<64>(ops); +} + +} // namespace +} // namespace quiche