bitdeque.cpp raw
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 }
542