bitdeque.cpp
1 // Copyright (c) 2022-present The Bitcoin Core developers 2 // Distributed under the MIT software license, see the accompanying 3 // file COPYING or http://www.opensource.org/licenses/mit-license.php. 4 5 #include <random.h> 6 #include <test/fuzz/FuzzedDataProvider.h> 7 #include <test/fuzz/util.h> 8 #include <util/bitdeque.h> 9 10 #include <deque> 11 #include <vector> 12 13 namespace { 14 15 constexpr int LEN_BITS = 16; 16 constexpr int RANDDATA_BITS = 20; 17 18 using bitdeque_type = bitdeque<128>; 19 20 //! Deterministic random vector of bools, for begin/end insertions to draw from. 21 std::vector<bool> RANDDATA; 22 23 void InitRandData() 24 { 25 FastRandomContext ctx(true); 26 RANDDATA.clear(); 27 for (size_t i = 0; i < (1U << RANDDATA_BITS) + (1U << LEN_BITS); ++i) { 28 RANDDATA.push_back(ctx.randbool()); 29 } 30 } 31 32 } // namespace 33 34 FUZZ_TARGET(bitdeque, .init = InitRandData) 35 { 36 FuzzedDataProvider provider(buffer.data(), buffer.size()); 37 FastRandomContext ctx(true); 38 39 size_t maxlen = (1U << provider.ConsumeIntegralInRange<size_t>(0, LEN_BITS)) - 1; 40 size_t limitlen = 4 * maxlen; 41 42 std::deque<bool> deq; 43 bitdeque_type bitdeq; 44 45 const auto& cdeq = deq; 46 const auto& cbitdeq = bitdeq; 47 48 size_t initlen = provider.ConsumeIntegralInRange<size_t>(0, maxlen); 49 while (initlen) { 50 bool val = ctx.randbool(); 51 deq.push_back(val); 52 bitdeq.push_back(val); 53 --initlen; 54 } 55 56 const auto iter_limit{maxlen > 6000 ? 90U : 900U}; 57 LIMITED_WHILE(provider.remaining_bytes() > 0, iter_limit) 58 { 59 CallOneOf( 60 provider, 61 [&] { 62 // constructor() 63 deq = std::deque<bool>{}; 64 bitdeq = bitdeque_type{}; 65 }, 66 [&] { 67 // clear() 68 deq.clear(); 69 bitdeq.clear(); 70 }, 71 [&] { 72 // resize() 73 auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen); 74 deq.resize(count); 75 bitdeq.resize(count); 76 }, 77 [&] { 78 // assign(count, val) 79 auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen); 80 bool val = ctx.randbool(); 81 deq.assign(count, val); 82 bitdeq.assign(count, val); 83 }, 84 [&] { 85 // constructor(count, val) 86 auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen); 87 bool val = ctx.randbool(); 88 deq = std::deque<bool>(count, val); 89 bitdeq = bitdeque_type(count, val); 90 }, 91 [&] { 92 // constructor(count) 93 auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen); 94 deq = std::deque<bool>(count); 95 bitdeq = bitdeque_type(count); 96 }, 97 [&] { 98 // construct(begin, end) 99 auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen); 100 auto rand_begin = RANDDATA.begin() + ctx.randbits(RANDDATA_BITS); 101 auto rand_end = rand_begin + count; 102 deq = std::deque<bool>(rand_begin, rand_end); 103 bitdeq = bitdeque_type(rand_begin, rand_end); 104 }, 105 [&] { 106 // assign(begin, end) 107 auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen); 108 auto rand_begin = RANDDATA.begin() + ctx.randbits(RANDDATA_BITS); 109 auto rand_end = rand_begin + count; 110 deq.assign(rand_begin, rand_end); 111 bitdeq.assign(rand_begin, rand_end); 112 }, 113 [&] { 114 // construct(initializer_list) 115 std::initializer_list<bool> ilist{ctx.randbool(), ctx.randbool(), ctx.randbool(), ctx.randbool(), ctx.randbool()}; 116 deq = std::deque<bool>(ilist); 117 bitdeq = bitdeque_type(ilist); 118 }, 119 [&] { 120 // assign(initializer_list) 121 std::initializer_list<bool> ilist{ctx.randbool(), ctx.randbool(), ctx.randbool()}; 122 deq.assign(ilist); 123 bitdeq.assign(ilist); 124 }, 125 [&] { 126 // operator=(const&) 127 auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen); 128 bool val = ctx.randbool(); 129 const std::deque<bool> deq2(count, val); 130 deq = deq2; 131 const bitdeque_type bitdeq2(count, val); 132 bitdeq = bitdeq2; 133 }, 134 [&] { 135 // operator=(&&) 136 auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen); 137 bool val = ctx.randbool(); 138 std::deque<bool> deq2(count, val); 139 deq = std::move(deq2); 140 bitdeque_type bitdeq2(count, val); 141 bitdeq = std::move(bitdeq2); 142 }, 143 [&] { 144 // deque swap 145 auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen); 146 auto rand_begin = RANDDATA.begin() + ctx.randbits(RANDDATA_BITS); 147 auto rand_end = rand_begin + count; 148 std::deque<bool> deq2(rand_begin, rand_end); 149 bitdeque_type bitdeq2(rand_begin, rand_end); 150 using std::swap; 151 assert(deq.size() == bitdeq.size()); 152 assert(deq2.size() == bitdeq2.size()); 153 swap(deq, deq2); 154 swap(bitdeq, bitdeq2); 155 assert(deq.size() == bitdeq.size()); 156 assert(deq2.size() == bitdeq2.size()); 157 }, 158 [&] { 159 // deque.swap 160 auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen); 161 auto rand_begin = RANDDATA.begin() + ctx.randbits(RANDDATA_BITS); 162 auto rand_end = rand_begin + count; 163 std::deque<bool> deq2(rand_begin, rand_end); 164 bitdeque_type bitdeq2(rand_begin, rand_end); 165 assert(deq.size() == bitdeq.size()); 166 assert(deq2.size() == bitdeq2.size()); 167 deq.swap(deq2); 168 bitdeq.swap(bitdeq2); 169 assert(deq.size() == bitdeq.size()); 170 assert(deq2.size() == bitdeq2.size()); 171 }, 172 [&] { 173 // operator=(initializer_list) 174 std::initializer_list<bool> ilist{ctx.randbool(), ctx.randbool(), ctx.randbool()}; 175 deq = ilist; 176 bitdeq = ilist; 177 }, 178 [&] { 179 // iterator arithmetic 180 auto pos1 = provider.ConsumeIntegralInRange<long>(0, cdeq.size()); 181 auto pos2 = provider.ConsumeIntegralInRange<long>(0, cdeq.size()); 182 auto it = deq.begin() + pos1; 183 auto bitit = bitdeq.begin() + pos1; 184 if ((size_t)pos1 != cdeq.size()) assert(*it == *bitit); 185 assert(it - deq.begin() == pos1); 186 assert(bitit - bitdeq.begin() == pos1); 187 if (provider.ConsumeBool()) { 188 it += pos2 - pos1; 189 bitit += pos2 - pos1; 190 } else { 191 it -= pos1 - pos2; 192 bitit -= pos1 - pos2; 193 } 194 if ((size_t)pos2 != cdeq.size()) assert(*it == *bitit); 195 assert(deq.end() - it == bitdeq.end() - bitit); 196 if (provider.ConsumeBool()) { 197 if ((size_t)pos2 != cdeq.size()) { 198 ++it; 199 ++bitit; 200 } 201 } else { 202 if (pos2 != 0) { 203 --it; 204 --bitit; 205 } 206 } 207 assert(deq.end() - it == bitdeq.end() - bitit); 208 }, 209 [&] { 210 // begin() and end() 211 assert(deq.end() - deq.begin() == bitdeq.end() - bitdeq.begin()); 212 }, 213 [&] { 214 // begin() and end() (const) 215 assert(cdeq.end() - cdeq.begin() == cbitdeq.end() - cbitdeq.begin()); 216 }, 217 [&] { 218 // rbegin() and rend() 219 assert(deq.rend() - deq.rbegin() == bitdeq.rend() - bitdeq.rbegin()); 220 }, 221 [&] { 222 // rbegin() and rend() (const) 223 assert(cdeq.rend() - cdeq.rbegin() == cbitdeq.rend() - cbitdeq.rbegin()); 224 }, 225 [&] { 226 // cbegin() and cend() 227 assert(cdeq.cend() - cdeq.cbegin() == cbitdeq.cend() - cbitdeq.cbegin()); 228 }, 229 [&] { 230 // crbegin() and crend() 231 assert(cdeq.crend() - cdeq.crbegin() == cbitdeq.crend() - cbitdeq.crbegin()); 232 }, 233 [&] { 234 // size() and maxsize() 235 assert(cdeq.size() == cbitdeq.size()); 236 assert(cbitdeq.size() <= cbitdeq.max_size()); 237 }, 238 [&] { 239 // empty 240 assert(cdeq.empty() == cbitdeq.empty()); 241 }, 242 [&] { 243 // at (in range) and flip 244 if (!cdeq.empty()) { 245 size_t pos = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() - 1); 246 auto& ref = deq.at(pos); 247 auto bitref = bitdeq.at(pos); 248 assert(ref == bitref); 249 if (ctx.randbool()) { 250 ref = !ref; 251 bitref.flip(); 252 } 253 } 254 }, 255 [&] { 256 // at (maybe out of range) and bit assign 257 size_t pos = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() + maxlen); 258 bool newval = ctx.randbool(); 259 bool throw_deq{false}, throw_bitdeq{false}; 260 bool val_deq{false}, val_bitdeq{false}; 261 try { 262 auto& ref = deq.at(pos); 263 val_deq = ref; 264 ref = newval; 265 } catch (const std::out_of_range&) { 266 throw_deq = true; 267 } 268 try { 269 auto ref = bitdeq.at(pos); 270 val_bitdeq = ref; 271 ref = newval; 272 } catch (const std::out_of_range&) { 273 throw_bitdeq = true; 274 } 275 assert(throw_deq == throw_bitdeq); 276 assert(throw_bitdeq == (pos >= cdeq.size())); 277 if (!throw_deq) assert(val_deq == val_bitdeq); 278 }, 279 [&] { 280 // at (maybe out of range) (const) 281 size_t pos = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() + maxlen); 282 bool throw_deq{false}, throw_bitdeq{false}; 283 bool val_deq{false}, val_bitdeq{false}; 284 try { 285 auto& ref = cdeq.at(pos); 286 val_deq = ref; 287 } catch (const std::out_of_range&) { 288 throw_deq = true; 289 } 290 try { 291 auto ref = cbitdeq.at(pos); 292 val_bitdeq = ref; 293 } catch (const std::out_of_range&) { 294 throw_bitdeq = true; 295 } 296 assert(throw_deq == throw_bitdeq); 297 assert(throw_bitdeq == (pos >= cdeq.size())); 298 if (!throw_deq) assert(val_deq == val_bitdeq); 299 }, 300 [&] { 301 // operator[] 302 if (!cdeq.empty()) { 303 size_t pos = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() - 1); 304 assert(deq[pos] == bitdeq[pos]); 305 if (ctx.randbool()) { 306 deq[pos] = !deq[pos]; 307 bitdeq[pos].flip(); 308 } 309 } 310 }, 311 [&] { 312 // operator[] const 313 if (!cdeq.empty()) { 314 size_t pos = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() - 1); 315 assert(deq[pos] == bitdeq[pos]); 316 } 317 }, 318 [&] { 319 // front() 320 if (!cdeq.empty()) { 321 auto& ref = deq.front(); 322 auto bitref = bitdeq.front(); 323 assert(ref == bitref); 324 if (ctx.randbool()) { 325 ref = !ref; 326 bitref = !bitref; 327 } 328 } 329 }, 330 [&] { 331 // front() const 332 if (!cdeq.empty()) { 333 auto& ref = cdeq.front(); 334 auto bitref = cbitdeq.front(); 335 assert(ref == bitref); 336 } 337 }, 338 [&] { 339 // back() and swap(bool, ref) 340 if (!cdeq.empty()) { 341 auto& ref = deq.back(); 342 auto bitref = bitdeq.back(); 343 assert(ref == bitref); 344 if (ctx.randbool()) { 345 ref = !ref; 346 bitref.flip(); 347 } 348 } 349 }, 350 [&] { 351 // back() const 352 if (!cdeq.empty()) { 353 const auto& cdeq = deq; 354 const auto& cbitdeq = bitdeq; 355 auto& ref = cdeq.back(); 356 auto bitref = cbitdeq.back(); 357 assert(ref == bitref); 358 } 359 }, 360 [&] { 361 // push_back() 362 if (cdeq.size() < limitlen) { 363 bool val = ctx.randbool(); 364 if (cdeq.empty()) { 365 deq.push_back(val); 366 bitdeq.push_back(val); 367 } else { 368 size_t pos = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() - 1); 369 auto& ref = deq[pos]; 370 auto bitref = bitdeq[pos]; 371 assert(ref == bitref); 372 deq.push_back(val); 373 bitdeq.push_back(val); 374 assert(ref == bitref); // references are not invalidated 375 } 376 } 377 }, 378 [&] { 379 // push_front() 380 if (cdeq.size() < limitlen) { 381 bool val = ctx.randbool(); 382 if (cdeq.empty()) { 383 deq.push_front(val); 384 bitdeq.push_front(val); 385 } else { 386 size_t pos = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() - 1); 387 auto& ref = deq[pos]; 388 auto bitref = bitdeq[pos]; 389 assert(ref == bitref); 390 deq.push_front(val); 391 bitdeq.push_front(val); 392 assert(ref == bitref); // references are not invalidated 393 } 394 } 395 }, 396 [&] { 397 // pop_back() 398 if (!cdeq.empty()) { 399 if (cdeq.size() == 1) { 400 deq.pop_back(); 401 bitdeq.pop_back(); 402 } else { 403 size_t pos = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() - 2); 404 auto& ref = deq[pos]; 405 auto bitref = bitdeq[pos]; 406 assert(ref == bitref); 407 deq.pop_back(); 408 bitdeq.pop_back(); 409 assert(ref == bitref); // references to other elements are not invalidated 410 } 411 } 412 }, 413 [&] { 414 // pop_front() 415 if (!cdeq.empty()) { 416 if (cdeq.size() == 1) { 417 deq.pop_front(); 418 bitdeq.pop_front(); 419 } else { 420 size_t pos = provider.ConsumeIntegralInRange<size_t>(1, cdeq.size() - 1); 421 auto& ref = deq[pos]; 422 auto bitref = bitdeq[pos]; 423 assert(ref == bitref); 424 deq.pop_front(); 425 bitdeq.pop_front(); 426 assert(ref == bitref); // references to other elements are not invalidated 427 } 428 } 429 }, 430 [&] { 431 // erase (in middle, single) 432 if (!cdeq.empty()) { 433 size_t before = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() - 1); 434 size_t after = cdeq.size() - 1 - before; 435 auto it = deq.erase(cdeq.begin() + before); 436 auto bitit = bitdeq.erase(cbitdeq.begin() + before); 437 assert(it == cdeq.begin() + before && it == cdeq.end() - after); 438 assert(bitit == cbitdeq.begin() + before && bitit == cbitdeq.end() - after); 439 } 440 }, 441 [&] { 442 // erase (at front, range) 443 size_t count = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size()); 444 auto it = deq.erase(cdeq.begin(), cdeq.begin() + count); 445 auto bitit = bitdeq.erase(cbitdeq.begin(), cbitdeq.begin() + count); 446 assert(it == deq.begin()); 447 assert(bitit == bitdeq.begin()); 448 }, 449 [&] { 450 // erase (at back, range) 451 size_t count = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size()); 452 auto it = deq.erase(cdeq.end() - count, cdeq.end()); 453 auto bitit = bitdeq.erase(cbitdeq.end() - count, cbitdeq.end()); 454 assert(it == deq.end()); 455 assert(bitit == bitdeq.end()); 456 }, 457 [&] { 458 // erase (in middle, range) 459 size_t count = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size()); 460 size_t before = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() - count); 461 size_t after = cdeq.size() - count - before; 462 auto it = deq.erase(cdeq.begin() + before, cdeq.end() - after); 463 auto bitit = bitdeq.erase(cbitdeq.begin() + before, cbitdeq.end() - after); 464 assert(it == cdeq.begin() + before && it == cdeq.end() - after); 465 assert(bitit == cbitdeq.begin() + before && bitit == cbitdeq.end() - after); 466 }, 467 [&] { 468 // insert/emplace (in middle, single) 469 if (cdeq.size() < limitlen) { 470 size_t before = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size()); 471 bool val = ctx.randbool(); 472 bool do_emplace = provider.ConsumeBool(); 473 auto it = deq.insert(cdeq.begin() + before, val); 474 auto bitit = do_emplace ? bitdeq.emplace(cbitdeq.begin() + before, val) 475 : bitdeq.insert(cbitdeq.begin() + before, val); 476 assert(it == deq.begin() + before); 477 assert(bitit == bitdeq.begin() + before); 478 } 479 }, 480 [&] { 481 // insert (at front, begin/end) 482 if (cdeq.size() < limitlen) { 483 size_t count = provider.ConsumeIntegralInRange<size_t>(0, maxlen); 484 auto rand_begin = RANDDATA.begin() + ctx.randbits(RANDDATA_BITS); 485 auto rand_end = rand_begin + count; 486 auto it = deq.insert(cdeq.begin(), rand_begin, rand_end); 487 auto bitit = bitdeq.insert(cbitdeq.begin(), rand_begin, rand_end); 488 assert(it == cdeq.begin()); 489 assert(bitit == cbitdeq.begin()); 490 } 491 }, 492 [&] { 493 // insert (at back, begin/end) 494 if (cdeq.size() < limitlen) { 495 size_t count = provider.ConsumeIntegralInRange<size_t>(0, maxlen); 496 auto rand_begin = RANDDATA.begin() + ctx.randbits(RANDDATA_BITS); 497 auto rand_end = rand_begin + count; 498 auto it = deq.insert(cdeq.end(), rand_begin, rand_end); 499 auto bitit = bitdeq.insert(cbitdeq.end(), rand_begin, rand_end); 500 assert(it == cdeq.end() - count); 501 assert(bitit == cbitdeq.end() - count); 502 } 503 }, 504 [&] { 505 // insert (in middle, range) 506 if (cdeq.size() < limitlen) { 507 size_t count = provider.ConsumeIntegralInRange<size_t>(0, maxlen); 508 size_t before = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size()); 509 bool val = ctx.randbool(); 510 auto it = deq.insert(cdeq.begin() + before, count, val); 511 auto bitit = bitdeq.insert(cbitdeq.begin() + before, count, val); 512 assert(it == deq.begin() + before); 513 assert(bitit == bitdeq.begin() + before); 514 } 515 }, 516 [&] { 517 // insert (in middle, begin/end) 518 if (cdeq.size() < limitlen) { 519 size_t count = provider.ConsumeIntegralInRange<size_t>(0, maxlen); 520 size_t before = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size()); 521 auto rand_begin = RANDDATA.begin() + ctx.randbits(RANDDATA_BITS); 522 auto rand_end = rand_begin + count; 523 auto it = deq.insert(cdeq.begin() + before, rand_begin, rand_end); 524 auto bitit = bitdeq.insert(cbitdeq.begin() + before, rand_begin, rand_end); 525 assert(it == deq.begin() + before); 526 assert(bitit == bitdeq.begin() + before); 527 } 528 }); 529 } 530 { 531 assert(deq.size() == bitdeq.size()); 532 auto it = deq.begin(); 533 auto bitit = bitdeq.begin(); 534 auto itend = deq.end(); 535 while (it != itend) { 536 assert(*it == *bitit); 537 ++it; 538 ++bitit; 539 } 540 } 541 }