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