diff options
Diffstat (limited to 'src/test')
-rw-r--r-- | src/test/fuzz/bitdeque.cpp | 542 | ||||
-rw-r--r-- | src/test/util_tests.cpp | 1 |
2 files changed, 543 insertions, 0 deletions
diff --git a/src/test/fuzz/bitdeque.cpp b/src/test/fuzz/bitdeque.cpp new file mode 100644 index 0000000000..01af8320b5 --- /dev/null +++ b/src/test/fuzz/bitdeque.cpp @@ -0,0 +1,542 @@ +// Copyright (c) 2022 The Bitcoin Core developers +// Distributed under the MIT software license, see the accompanying +// file COPYING or http://www.opensource.org/licenses/mit-license.php. + +#include <util/bitdeque.h> + +#include <random.h> +#include <test/fuzz/FuzzedDataProvider.h> +#include <test/fuzz/util.h> + +#include <deque> +#include <vector> + +namespace { + +constexpr int LEN_BITS = 16; +constexpr int RANDDATA_BITS = 20; + +using bitdeque_type = bitdeque<128>; + +//! Deterministic random vector of bools, for begin/end insertions to draw from. +std::vector<bool> RANDDATA; + +void InitRandData() +{ + FastRandomContext ctx(true); + RANDDATA.clear(); + for (size_t i = 0; i < (1U << RANDDATA_BITS) + (1U << LEN_BITS); ++i) { + RANDDATA.push_back(ctx.randbool()); + } +} + +} // namespace + +FUZZ_TARGET_INIT(bitdeque, InitRandData) +{ + FuzzedDataProvider provider(buffer.data(), buffer.size()); + FastRandomContext ctx(true); + + size_t maxlen = (1U << provider.ConsumeIntegralInRange<size_t>(0, LEN_BITS)) - 1; + size_t limitlen = 4 * maxlen; + + std::deque<bool> deq; + bitdeque_type bitdeq; + + const auto& cdeq = deq; + const auto& cbitdeq = bitdeq; + + size_t initlen = provider.ConsumeIntegralInRange<size_t>(0, maxlen); + while (initlen) { + bool val = ctx.randbool(); + deq.push_back(val); + bitdeq.push_back(val); + --initlen; + } + + while (provider.remaining_bytes()) { + { + assert(deq.size() == bitdeq.size()); + auto it = deq.begin(); + auto bitit = bitdeq.begin(); + auto itend = deq.end(); + while (it != itend) { + assert(*it == *bitit); + ++it; + ++bitit; + } + } + + CallOneOf(provider, + [&] { + // constructor() + deq = std::deque<bool>{}; + bitdeq = bitdeque_type{}; + }, + [&] { + // clear() + deq.clear(); + bitdeq.clear(); + }, + [&] { + // resize() + auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen); + deq.resize(count); + bitdeq.resize(count); + }, + [&] { + // assign(count, val) + auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen); + bool val = ctx.randbool(); + deq.assign(count, val); + bitdeq.assign(count, val); + }, + [&] { + // constructor(count, val) + auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen); + bool val = ctx.randbool(); + deq = std::deque<bool>(count, val); + bitdeq = bitdeque_type(count, val); + }, + [&] { + // constructor(count) + auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen); + deq = std::deque<bool>(count); + bitdeq = bitdeque_type(count); + }, + [&] { + // construct(begin, end) + auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen); + auto rand_begin = RANDDATA.begin() + ctx.randbits(RANDDATA_BITS); + auto rand_end = rand_begin + count; + deq = std::deque<bool>(rand_begin, rand_end); + bitdeq = bitdeque_type(rand_begin, rand_end); + }, + [&] { + // assign(begin, end) + auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen); + auto rand_begin = RANDDATA.begin() + ctx.randbits(RANDDATA_BITS); + auto rand_end = rand_begin + count; + deq.assign(rand_begin, rand_end); + bitdeq.assign(rand_begin, rand_end); + }, + [&] { + // construct(initializer_list) + std::initializer_list<bool> ilist{ctx.randbool(), ctx.randbool(), ctx.randbool(), ctx.randbool(), ctx.randbool()}; + deq = std::deque<bool>(ilist); + bitdeq = bitdeque_type(ilist); + }, + [&] { + // assign(initializer_list) + std::initializer_list<bool> ilist{ctx.randbool(), ctx.randbool(), ctx.randbool()}; + deq.assign(ilist); + bitdeq.assign(ilist); + }, + [&] { + // operator=(const&) + auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen); + bool val = ctx.randbool(); + const std::deque<bool> deq2(count, val); + deq = deq2; + const bitdeque_type bitdeq2(count, val); + bitdeq = bitdeq2; + }, + [&] { + // operator=(&&) + auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen); + bool val = ctx.randbool(); + std::deque<bool> deq2(count, val); + deq = std::move(deq2); + bitdeque_type bitdeq2(count, val); + bitdeq = std::move(bitdeq2); + }, + [&] { + // deque swap + auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen); + auto rand_begin = RANDDATA.begin() + ctx.randbits(RANDDATA_BITS); + auto rand_end = rand_begin + count; + std::deque<bool> deq2(rand_begin, rand_end); + bitdeque_type bitdeq2(rand_begin, rand_end); + using std::swap; + assert(deq.size() == bitdeq.size()); + assert(deq2.size() == bitdeq2.size()); + swap(deq, deq2); + swap(bitdeq, bitdeq2); + assert(deq.size() == bitdeq.size()); + assert(deq2.size() == bitdeq2.size()); + }, + [&] { + // deque.swap + auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen); + auto rand_begin = RANDDATA.begin() + ctx.randbits(RANDDATA_BITS); + auto rand_end = rand_begin + count; + std::deque<bool> deq2(rand_begin, rand_end); + bitdeque_type bitdeq2(rand_begin, rand_end); + assert(deq.size() == bitdeq.size()); + assert(deq2.size() == bitdeq2.size()); + deq.swap(deq2); + bitdeq.swap(bitdeq2); + assert(deq.size() == bitdeq.size()); + assert(deq2.size() == bitdeq2.size()); + }, + [&] { + // operator=(initializer_list) + std::initializer_list<bool> ilist{ctx.randbool(), ctx.randbool(), ctx.randbool()}; + deq = ilist; + bitdeq = ilist; + }, + [&] { + // iterator arithmetic + auto pos1 = provider.ConsumeIntegralInRange<long>(0, cdeq.size()); + auto pos2 = provider.ConsumeIntegralInRange<long>(0, cdeq.size()); + auto it = deq.begin() + pos1; + auto bitit = bitdeq.begin() + pos1; + if ((size_t)pos1 != cdeq.size()) assert(*it == *bitit); + assert(it - deq.begin() == pos1); + assert(bitit - bitdeq.begin() == pos1); + if (provider.ConsumeBool()) { + it += pos2 - pos1; + bitit += pos2 - pos1; + } else { + it -= pos1 - pos2; + bitit -= pos1 - pos2; + } + if ((size_t)pos2 != cdeq.size()) assert(*it == *bitit); + assert(deq.end() - it == bitdeq.end() - bitit); + if (provider.ConsumeBool()) { + if ((size_t)pos2 != cdeq.size()) { + ++it; + ++bitit; + } + } else { + if (pos2 != 0) { + --it; + --bitit; + } + } + assert(deq.end() - it == bitdeq.end() - bitit); + }, + [&] { + // begin() and end() + assert(deq.end() - deq.begin() == bitdeq.end() - bitdeq.begin()); + }, + [&] { + // begin() and end() (const) + assert(cdeq.end() - cdeq.begin() == cbitdeq.end() - cbitdeq.begin()); + }, + [&] { + // rbegin() and rend() + assert(deq.rend() - deq.rbegin() == bitdeq.rend() - bitdeq.rbegin()); + }, + [&] { + // rbegin() and rend() (const) + assert(cdeq.rend() - cdeq.rbegin() == cbitdeq.rend() - cbitdeq.rbegin()); + }, + [&] { + // cbegin() and cend() + assert(cdeq.cend() - cdeq.cbegin() == cbitdeq.cend() - cbitdeq.cbegin()); + }, + [&] { + // crbegin() and crend() + assert(cdeq.crend() - cdeq.crbegin() == cbitdeq.crend() - cbitdeq.crbegin()); + }, + [&] { + // size() and maxsize() + assert(cdeq.size() == cbitdeq.size()); + assert(cbitdeq.size() <= cbitdeq.max_size()); + }, + [&] { + // empty + assert(cdeq.empty() == cbitdeq.empty()); + }, + [&] { + // at (in range) and flip + if (!cdeq.empty()) { + size_t pos = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() - 1); + auto& ref = deq.at(pos); + auto bitref = bitdeq.at(pos); + assert(ref == bitref); + if (ctx.randbool()) { + ref = !ref; + bitref.flip(); + } + } + }, + [&] { + // at (maybe out of range) and bit assign + size_t pos = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() + maxlen); + bool newval = ctx.randbool(); + bool throw_deq{false}, throw_bitdeq{false}; + bool val_deq{false}, val_bitdeq{false}; + try { + auto& ref = deq.at(pos); + val_deq = ref; + ref = newval; + } catch (const std::out_of_range&) { + throw_deq = true; + } + try { + auto ref = bitdeq.at(pos); + val_bitdeq = ref; + ref = newval; + } catch (const std::out_of_range&) { + throw_bitdeq = true; + } + assert(throw_deq == throw_bitdeq); + assert(throw_bitdeq == (pos >= cdeq.size())); + if (!throw_deq) assert(val_deq == val_bitdeq); + }, + [&] { + // at (maybe out of range) (const) + size_t pos = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() + maxlen); + bool throw_deq{false}, throw_bitdeq{false}; + bool val_deq{false}, val_bitdeq{false}; + try { + auto& ref = cdeq.at(pos); + val_deq = ref; + } catch (const std::out_of_range&) { + throw_deq = true; + } + try { + auto ref = cbitdeq.at(pos); + val_bitdeq = ref; + } catch (const std::out_of_range&) { + throw_bitdeq = true; + } + assert(throw_deq == throw_bitdeq); + assert(throw_bitdeq == (pos >= cdeq.size())); + if (!throw_deq) assert(val_deq == val_bitdeq); + }, + [&] { + // operator[] + if (!cdeq.empty()) { + size_t pos = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() - 1); + assert(deq[pos] == bitdeq[pos]); + if (ctx.randbool()) { + deq[pos] = !deq[pos]; + bitdeq[pos].flip(); + } + } + }, + [&] { + // operator[] const + if (!cdeq.empty()) { + size_t pos = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() - 1); + assert(deq[pos] == bitdeq[pos]); + } + }, + [&] { + // front() + if (!cdeq.empty()) { + auto& ref = deq.front(); + auto bitref = bitdeq.front(); + assert(ref == bitref); + if (ctx.randbool()) { + ref = !ref; + bitref = !bitref; + } + } + }, + [&] { + // front() const + if (!cdeq.empty()) { + auto& ref = cdeq.front(); + auto bitref = cbitdeq.front(); + assert(ref == bitref); + } + }, + [&] { + // back() and swap(bool, ref) + if (!cdeq.empty()) { + auto& ref = deq.back(); + auto bitref = bitdeq.back(); + assert(ref == bitref); + if (ctx.randbool()) { + ref = !ref; + bitref.flip(); + } + } + }, + [&] { + // back() const + if (!cdeq.empty()) { + const auto& cdeq = deq; + const auto& cbitdeq = bitdeq; + auto& ref = cdeq.back(); + auto bitref = cbitdeq.back(); + assert(ref == bitref); + } + }, + [&] { + // push_back() + if (cdeq.size() < limitlen) { + bool val = ctx.randbool(); + if (cdeq.empty()) { + deq.push_back(val); + bitdeq.push_back(val); + } else { + size_t pos = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() - 1); + auto& ref = deq[pos]; + auto bitref = bitdeq[pos]; + assert(ref == bitref); + deq.push_back(val); + bitdeq.push_back(val); + assert(ref == bitref); // references are not invalidated + } + } + }, + [&] { + // push_front() + if (cdeq.size() < limitlen) { + bool val = ctx.randbool(); + if (cdeq.empty()) { + deq.push_front(val); + bitdeq.push_front(val); + } else { + size_t pos = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() - 1); + auto& ref = deq[pos]; + auto bitref = bitdeq[pos]; + assert(ref == bitref); + deq.push_front(val); + bitdeq.push_front(val); + assert(ref == bitref); // references are not invalidated + } + } + }, + [&] { + // pop_back() + if (!cdeq.empty()) { + if (cdeq.size() == 1) { + deq.pop_back(); + bitdeq.pop_back(); + } else { + size_t pos = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() - 2); + auto& ref = deq[pos]; + auto bitref = bitdeq[pos]; + assert(ref == bitref); + deq.pop_back(); + bitdeq.pop_back(); + assert(ref == bitref); // references to other elements are not invalidated + } + } + }, + [&] { + // pop_front() + if (!cdeq.empty()) { + if (cdeq.size() == 1) { + deq.pop_front(); + bitdeq.pop_front(); + } else { + size_t pos = provider.ConsumeIntegralInRange<size_t>(1, cdeq.size() - 1); + auto& ref = deq[pos]; + auto bitref = bitdeq[pos]; + assert(ref == bitref); + deq.pop_front(); + bitdeq.pop_front(); + assert(ref == bitref); // references to other elements are not invalidated + } + } + }, + [&] { + // erase (in middle, single) + if (!cdeq.empty()) { + size_t before = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() - 1); + size_t after = cdeq.size() - 1 - before; + auto it = deq.erase(cdeq.begin() + before); + auto bitit = bitdeq.erase(cbitdeq.begin() + before); + assert(it == cdeq.begin() + before && it == cdeq.end() - after); + assert(bitit == cbitdeq.begin() + before && bitit == cbitdeq.end() - after); + } + }, + [&] { + // erase (at front, range) + size_t count = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size()); + auto it = deq.erase(cdeq.begin(), cdeq.begin() + count); + auto bitit = bitdeq.erase(cbitdeq.begin(), cbitdeq.begin() + count); + assert(it == deq.begin()); + assert(bitit == bitdeq.begin()); + }, + [&] { + // erase (at back, range) + size_t count = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size()); + auto it = deq.erase(cdeq.end() - count, cdeq.end()); + auto bitit = bitdeq.erase(cbitdeq.end() - count, cbitdeq.end()); + assert(it == deq.end()); + assert(bitit == bitdeq.end()); + }, + [&] { + // erase (in middle, range) + size_t count = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size()); + size_t before = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() - count); + size_t after = cdeq.size() - count - before; + auto it = deq.erase(cdeq.begin() + before, cdeq.end() - after); + auto bitit = bitdeq.erase(cbitdeq.begin() + before, cbitdeq.end() - after); + assert(it == cdeq.begin() + before && it == cdeq.end() - after); + assert(bitit == cbitdeq.begin() + before && bitit == cbitdeq.end() - after); + }, + [&] { + // insert/emplace (in middle, single) + if (cdeq.size() < limitlen) { + size_t before = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size()); + bool val = ctx.randbool(); + bool do_emplace = provider.ConsumeBool(); + auto it = deq.insert(cdeq.begin() + before, val); + auto bitit = do_emplace ? bitdeq.emplace(cbitdeq.begin() + before, val) + : bitdeq.insert(cbitdeq.begin() + before, val); + assert(it == deq.begin() + before); + assert(bitit == bitdeq.begin() + before); + } + }, + [&] { + // insert (at front, begin/end) + if (cdeq.size() < limitlen) { + size_t count = provider.ConsumeIntegralInRange<size_t>(0, maxlen); + auto rand_begin = RANDDATA.begin() + ctx.randbits(RANDDATA_BITS); + auto rand_end = rand_begin + count; + auto it = deq.insert(cdeq.begin(), rand_begin, rand_end); + auto bitit = bitdeq.insert(cbitdeq.begin(), rand_begin, rand_end); + assert(it == cdeq.begin()); + assert(bitit == cbitdeq.begin()); + } + }, + [&] { + // insert (at back, begin/end) + if (cdeq.size() < limitlen) { + size_t count = provider.ConsumeIntegralInRange<size_t>(0, maxlen); + auto rand_begin = RANDDATA.begin() + ctx.randbits(RANDDATA_BITS); + auto rand_end = rand_begin + count; + auto it = deq.insert(cdeq.end(), rand_begin, rand_end); + auto bitit = bitdeq.insert(cbitdeq.end(), rand_begin, rand_end); + assert(it == cdeq.end() - count); + assert(bitit == cbitdeq.end() - count); + } + }, + [&] { + // insert (in middle, range) + if (cdeq.size() < limitlen) { + size_t count = provider.ConsumeIntegralInRange<size_t>(0, maxlen); + size_t before = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size()); + bool val = ctx.randbool(); + auto it = deq.insert(cdeq.begin() + before, count, val); + auto bitit = bitdeq.insert(cbitdeq.begin() + before, count, val); + assert(it == deq.begin() + before); + assert(bitit == bitdeq.begin() + before); + } + }, + [&] { + // insert (in middle, begin/end) + if (cdeq.size() < limitlen) { + size_t count = provider.ConsumeIntegralInRange<size_t>(0, maxlen); + size_t before = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size()); + auto rand_begin = RANDDATA.begin() + ctx.randbits(RANDDATA_BITS); + auto rand_end = rand_begin + count; + auto it = deq.insert(cdeq.begin() + before, rand_begin, rand_end); + auto bitit = bitdeq.insert(cbitdeq.begin() + before, rand_begin, rand_end); + assert(it == deq.begin() + before); + assert(bitit == bitdeq.begin() + before); + } + } + ); + } + +} diff --git a/src/test/util_tests.cpp b/src/test/util_tests.cpp index 70e2f89e0b..015237f43d 100644 --- a/src/test/util_tests.cpp +++ b/src/test/util_tests.cpp @@ -23,6 +23,7 @@ #include <util/string.h> #include <util/time.h> #include <util/vector.h> +#include <util/bitdeque.h> #include <array> #include <fstream> |