Branch data Line data Source code
1 : : // Copyright (c) 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 <span.h>
7 : : #include <test/fuzz/util.h>
8 : : #include <util/vecdeque.h>
9 : :
10 : : #include <deque>
11 : : #include <stdint.h>
12 : :
13 : : namespace {
14 : :
15 : : /** The maximum number of simultaneous buffers kept by the test. */
16 : : static constexpr size_t MAX_BUFFERS{3};
17 : : /** How many elements are kept in a buffer at most. */
18 : : static constexpr size_t MAX_BUFFER_SIZE{48};
19 : : /** How many operations are performed at most on the buffers in one test. */
20 : : static constexpr size_t MAX_OPERATIONS{1024};
21 : :
22 : : /** Perform a simulation fuzz test on VecDeque type T.
23 : : *
24 : : * T must be constructible from a uint64_t seed, comparable to other T, copyable, and movable.
25 : : */
26 : : template<typename T, bool CheckNoneLeft>
27 : 4347 : void TestType(Span<const uint8_t> buffer, uint64_t rng_tweak)
28 : : {
29 : 4347 : FuzzedDataProvider provider(buffer.data(), buffer.size());
30 : : // Local RNG, only used for the seeds to initialize T objects with.
31 : 4347 : InsecureRandomContext rng(provider.ConsumeIntegral<uint64_t>() ^ rng_tweak);
32 : :
33 : : // Real circular buffers.
34 : 4347 : std::vector<VecDeque<T>> real;
35 [ + - + - : 4347 : real.reserve(MAX_BUFFERS);
+ - + - +
- + - +
- ]
36 : : // Simulated circular buffers.
37 : 4347 : std::vector<std::deque<T>> sim;
38 [ + - + - : 4347 : sim.reserve(MAX_BUFFERS);
+ - + - +
- + - +
- ]
39 : : // Temporary object of type T.
40 : 4347 : std::optional<T> tmp;
41 : :
42 : : // Compare a real and a simulated buffer.
43 : 980770 : auto compare_fn = [](const VecDeque<T>& r, const std::deque<T>& s) {
44 [ + - + - : 976423 : assert(r.size() == s.size());
+ - + - +
- + - +
- ]
45 [ + - + - : 976423 : assert(r.empty() == s.empty());
+ - + - +
- + - +
- ]
46 [ + - + - : 976423 : assert(r.capacity() >= r.size());
+ - + - +
- + - +
- ]
47 [ + + + + : 976423 : if (s.size() == 0) return;
+ + + + +
+ + + +
+ ]
48 [ + - + - : 566069 : assert(r.front() == s.front());
+ - + - +
- + - +
- ]
49 [ + - + - : 566069 : assert(r.back() == s.back());
+ - + - +
- + - +
- ]
50 [ + + + + : 10983077 : for (size_t i = 0; i < s.size(); ++i) {
+ + + + +
+ + + +
+ ]
51 [ + - + - : 10417008 : assert(r[i] == s[i]);
+ - + - +
- + - +
- ]
52 : 10417008 : }
53 : 976423 : };
54 : :
55 [ - + + + : 2588523 : LIMITED_WHILE(provider.remaining_bytes(), MAX_OPERATIONS) {
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ ]
56 [ - + - + : 2584176 : int command = provider.ConsumeIntegral<uint8_t>() % 64;
- + - + +
- + - +
- ]
57 [ + + - + : 2584176 : unsigned idx = real.empty() ? 0 : provider.ConsumeIntegralInRange<unsigned>(0, real.size() - 1);
+ + + + +
+ + + + +
+ + ]
58 : 2584176 : const size_t num_buffers = sim.size();
59 : : // Pick one operation based on value of command. Not all operations are always applicable.
60 : : // Loop through the applicable ones until command reaches 0 (which avoids the need to
61 : : // compute the number of applicable commands ahead of time).
62 : 2584176 : const bool non_empty{num_buffers != 0};
63 : 2584176 : const bool non_full{num_buffers < MAX_BUFFERS};
64 [ + + + + : 2584176 : const bool partially_full{non_empty && non_full};
+ + + + +
+ + + +
+ ]
65 : 2584176 : const bool multiple_exist{num_buffers > 1};
66 [ + + + + : 2584176 : const bool existing_buffer_non_full{non_empty && sim[idx].size() < MAX_BUFFER_SIZE};
+ + + + +
+ + + +
+ ]
67 [ + + + + : 2584176 : const bool existing_buffer_non_empty{non_empty && !sim[idx].empty()};
+ + + + +
+ + + +
+ ]
68 [ + + - + : 2584176 : assert(non_full || non_empty);
+ + - + +
+ - + + +
- + + + -
+ + + - +
+ + - + ]
69 : 6013105 : while (true) {
70 [ + + + + : 6013105 : if (non_full && command-- == 0) {
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + ]
71 : : /* Default construct. */
72 [ + - + - : 74879 : real.emplace_back();
+ - + - +
- + - +
- ]
73 [ + - + - : 74879 : sim.emplace_back();
+ - + - +
- + - +
- ]
74 : 74879 : break;
75 : : }
76 [ + + + + : 5938226 : if (non_empty && command-- == 0) {
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + ]
77 : : /* resize() */
78 [ + - + - : 322644 : compare_fn(real[idx], sim[idx]);
+ - + - +
- + - +
- ]
79 [ + - ]: 322644 : size_t new_size = provider.ConsumeIntegralInRange<size_t>(0, MAX_BUFFER_SIZE);
80 [ + - + - : 322644 : real[idx].resize(new_size);
+ - + - +
- + - +
- ]
81 [ + - + - : 322644 : sim[idx].resize(new_size);
+ - + - +
- + - +
- ]
82 [ + - + - : 322644 : assert(real[idx].size() == new_size);
+ - + - +
- + - +
- ]
83 : : break;
84 : 322644 : }
85 [ + + + + : 5615582 : if (non_empty && command-- == 0) {
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + ]
86 : : /* clear() */
87 [ + - + - : 138530 : compare_fn(real[idx], sim[idx]);
+ - + - +
- + - +
- ]
88 : 138530 : real[idx].clear();
89 : 138530 : sim[idx].clear();
90 [ + - + - : 138530 : assert(real[idx].empty());
+ - + - +
- + - +
- ]
91 : 138530 : break;
92 : : }
93 [ + + + + : 5477052 : if (non_empty && command-- == 0) {
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + ]
94 : : /* Copy construct default. */
95 [ + - + - : 127792 : compare_fn(real[idx], sim[idx]);
+ - + - +
- + - +
- ]
96 : 127792 : real[idx] = VecDeque<T>();
97 : 127792 : sim[idx].clear();
98 [ + - + - : 127792 : assert(real[idx].size() == 0);
+ - + - +
- + - +
- ]
99 : 127792 : break;
100 : : }
101 [ + + + + : 5349260 : if (non_empty && command-- == 0) {
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + ]
102 : : /* Destruct. */
103 [ + - + - : 109802 : compare_fn(real.back(), sim.back());
+ - + - +
- + - +
- ]
104 : 109802 : real.pop_back();
105 : 109802 : sim.pop_back();
106 : 109802 : break;
107 : : }
108 [ + + + + : 5239458 : if (partially_full && command-- == 0) {
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + ]
109 : : /* Copy construct. */
110 [ + - + - : 21616 : real.emplace_back(real[idx]);
+ - + - +
- + - +
- ]
111 [ + - + - : 21616 : sim.emplace_back(sim[idx]);
+ - + - +
- + - +
- ]
112 : 21616 : break;
113 : : }
114 [ + + + + : 5217842 : if (partially_full && command-- == 0) {
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + ]
115 : : /* Move construct. */
116 [ + - + - : 23548 : VecDeque<T> copy(real[idx]);
+ - + - +
- + - +
- ]
117 [ + - + - : 23548 : real.emplace_back(std::move(copy));
+ - + - +
- + - +
- ]
118 [ + - + - : 23548 : sim.emplace_back(sim[idx]);
+ - + - +
- + - +
- ]
119 : : break;
120 : 23548 : }
121 [ + + + + : 5194294 : if (multiple_exist && command-- == 0) {
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + ]
122 : : /* swap() */
123 : 57673 : swap(real[idx], real[(idx + 1) % num_buffers]);
124 : 57673 : swap(sim[idx], sim[(idx + 1) % num_buffers]);
125 : 57673 : break;
126 : : }
127 [ + + + + : 5136621 : if (multiple_exist && command-- == 0) {
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + ]
128 : : /* Copy assign. */
129 [ + - + - : 135464 : compare_fn(real[idx], sim[idx]);
+ - + - +
- + - +
- ]
130 [ + - + - : 135464 : real[idx] = real[(idx + 1) % num_buffers];
+ - + - +
- + - +
- ]
131 [ + - + - : 135464 : sim[idx] = sim[(idx + 1) % num_buffers];
+ - + - +
- + - +
- ]
132 : 135464 : break;
133 : : }
134 [ + + + + : 5001157 : if (multiple_exist && command-- == 0) {
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + ]
135 : : /* Move assign. */
136 [ + - + - : 131950 : VecDeque<T> copy(real[(idx + 1) % num_buffers]);
+ - + - +
- + - +
- ]
137 [ + - + - : 131950 : compare_fn(real[idx], sim[idx]);
+ - + - +
- + - +
- ]
138 : 131950 : real[idx] = std::move(copy);
139 [ + - + - : 131950 : sim[idx] = sim[(idx + 1) % num_buffers];
+ - + - +
- + - +
- ]
140 : : break;
141 : 131950 : }
142 [ + + + + : 4869207 : if (non_empty && command-- == 0) {
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + ]
143 : : /* Self swap() */
144 : 49784 : swap(real[idx], real[idx]);
145 : 49784 : break;
146 : : }
147 [ + + + + : 4819423 : if (non_empty && command-- == 0) {
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + ]
148 : : /* Self-copy assign. */
149 [ + - + - : 71582 : real[idx] = real[idx];
+ - + - +
- + - +
- ]
150 : 71582 : break;
151 : : }
152 [ + + + + : 4747841 : if (non_empty && command-- == 0) {
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + ]
153 : : /* Self-move assign. */
154 : : // Do not use std::move(real[idx]) here: -Wself-move correctly warns about that.
155 : 87192 : real[idx] = static_cast<VecDeque<T>&&>(real[idx]);
156 : 87192 : break;
157 : : }
158 [ + + + + : 4660649 : if (non_empty && command-- == 0) {
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + ]
159 : : /* reserve() */
160 [ - + ]: 60886 : size_t res_size = provider.ConsumeIntegralInRange<size_t>(0, MAX_BUFFER_SIZE);
161 : 60886 : size_t old_cap = real[idx].capacity();
162 : 60886 : size_t old_size = real[idx].size();
163 [ + - - + : 60886 : real[idx].reserve(res_size);
- + - + -
+ - + -
+ ]
164 [ + - - + : 60886 : assert(real[idx].size() == old_size);
- + - + -
+ - + -
+ ]
165 [ + - - + : 60886 : assert(real[idx].capacity() == std::max(old_cap, res_size));
- + - + -
+ - + - +
- + ]
166 : : break;
167 : 60886 : }
168 [ + + + + : 4599763 : if (non_empty && command-- == 0) {
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + ]
169 : : /* shrink_to_fit() */
170 : 77483 : size_t old_size = real[idx].size();
171 [ + - + - : 77483 : real[idx].shrink_to_fit();
+ - + - +
- + - +
- ]
172 [ + - + - : 77483 : assert(real[idx].size() == old_size);
+ - + - +
- + - +
- ]
173 [ + - + - : 77483 : assert(real[idx].capacity() == old_size);
+ - + - +
- + - +
- ]
174 : : break;
175 : 77483 : }
176 [ + + + + : 4522280 : if (existing_buffer_non_full && command-- == 0) {
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + ]
177 : : /* push_back() (copying) */
178 [ - + - + : 126917 : tmp = T(rng.rand64());
- + - + -
+ - + ]
179 : 126917 : size_t old_size = real[idx].size();
180 : 126917 : size_t old_cap = real[idx].capacity();
181 [ + - + - : 126917 : real[idx].push_back(*tmp);
+ - + - +
- + - +
- ]
182 [ + - + - : 126917 : sim[idx].push_back(*tmp);
+ - + - +
- + - +
- ]
183 [ - + - + : 126917 : assert(real[idx].size() == old_size + 1);
- + - + -
+ - + -
+ ]
184 [ + + + + : 126917 : if (old_cap > old_size) {
+ + + + +
+ + + +
+ ]
185 [ - + - + : 95956 : assert(real[idx].capacity() == old_cap);
- + - + +
- + - +
- ]
186 : 95956 : } else {
187 [ - + - + : 30961 : assert(real[idx].capacity() > old_cap);
- + - + -
+ - + -
+ ]
188 [ + - + - : 30961 : assert(real[idx].capacity() <= 2 * (old_cap + 1));
+ - + - -
+ - + -
+ ]
189 : : }
190 : : break;
191 : 126917 : }
192 [ + + + + : 4395363 : if (existing_buffer_non_full && command-- == 0) {
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + ]
193 : : /* push_back() (moving) */
194 [ + - + - : 71309 : tmp = T(rng.rand64());
+ - + - +
- + - ]
195 : 71309 : size_t old_size = real[idx].size();
196 : 71309 : size_t old_cap = real[idx].capacity();
197 [ + - + - : 71309 : sim[idx].push_back(*tmp);
+ - + - +
- + - +
- ]
198 [ + - + - : 71309 : real[idx].push_back(std::move(*tmp));
+ - + - +
- + - +
- ]
199 [ + - + - : 71309 : assert(real[idx].size() == old_size + 1);
+ - + - +
- + - +
- ]
200 [ + + + + : 71309 : if (old_cap > old_size) {
+ + + + +
+ + + +
+ ]
201 [ + - + - : 49882 : assert(real[idx].capacity() == old_cap);
+ - + - -
+ - + -
+ ]
202 : 49882 : } else {
203 [ - + - + : 21427 : assert(real[idx].capacity() > old_cap);
- + - + -
+ - + -
+ ]
204 [ - + - + : 21427 : assert(real[idx].capacity() <= 2 * (old_cap + 1));
- + - + +
- + - +
- ]
205 : : }
206 : : break;
207 : 71309 : }
208 [ + + + + : 4324054 : if (existing_buffer_non_full && command-- == 0) {
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + ]
209 : : /* emplace_back() */
210 : 102032 : uint64_t seed{rng.rand64()};
211 : 102032 : size_t old_size = real[idx].size();
212 : 102032 : size_t old_cap = real[idx].capacity();
213 [ + - + - : 102032 : sim[idx].emplace_back(seed);
+ - + - +
- + - +
- ]
214 [ + - + - : 102032 : real[idx].emplace_back(seed);
+ - + - +
- + - +
- ]
215 [ + - + - : 102032 : assert(real[idx].size() == old_size + 1);
+ - + - +
- + - +
- ]
216 [ + + + + : 102032 : if (old_cap > old_size) {
+ + + + +
+ + + +
+ ]
217 [ - + + - : 72429 : assert(real[idx].capacity() == old_cap);
+ - + - -
+ - + -
+ ]
218 : 72429 : } else {
219 [ - + - + : 29603 : assert(real[idx].capacity() > old_cap);
- + - + -
+ - + -
+ ]
220 [ + - - + : 29603 : assert(real[idx].capacity() <= 2 * (old_cap + 1));
- + - + +
- + - +
- ]
221 : : }
222 : : break;
223 : 102032 : }
224 [ + + + + : 4222022 : if (existing_buffer_non_full && command-- == 0) {
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + ]
225 : : /* push_front() (copying) */
226 [ - + - + : 85092 : tmp = T(rng.rand64());
- + - + -
+ - + ]
227 : 85092 : size_t old_size = real[idx].size();
228 : 85092 : size_t old_cap = real[idx].capacity();
229 [ + - + - : 85092 : real[idx].push_front(*tmp);
+ - + - +
- + - +
- ]
230 [ + - + - : 85092 : sim[idx].push_front(*tmp);
+ - + - +
- + - +
- ]
231 [ - + - + : 85092 : assert(real[idx].size() == old_size + 1);
- + - + -
+ - + -
+ ]
232 [ + + + + : 85092 : if (old_cap > old_size) {
+ + + + +
+ + + +
+ ]
233 [ + - - + : 55321 : assert(real[idx].capacity() == old_cap);
- + - + -
+ - + -
+ ]
234 : 55321 : } else {
235 [ - + - + : 29771 : assert(real[idx].capacity() > old_cap);
- + - + -
+ - + -
+ ]
236 [ + - - + : 29771 : assert(real[idx].capacity() <= 2 * (old_cap + 1));
- + - + +
- + - +
- ]
237 : : }
238 : : break;
239 : 85092 : }
240 [ + + + + : 4136930 : if (existing_buffer_non_full && command-- == 0) {
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + ]
241 : : /* push_front() (moving) */
242 [ + - + - : 104300 : tmp = T(rng.rand64());
+ - + - +
- + - ]
243 : 104300 : size_t old_size = real[idx].size();
244 : 104300 : size_t old_cap = real[idx].capacity();
245 [ + - + - : 104300 : sim[idx].push_front(*tmp);
+ - + - +
- + - +
- ]
246 [ + - + - : 104300 : real[idx].push_front(std::move(*tmp));
+ - + - +
- + - +
- ]
247 [ + - + - : 104300 : assert(real[idx].size() == old_size + 1);
+ - + - +
- + - +
- ]
248 [ + + + + : 104300 : if (old_cap > old_size) {
+ + + + +
+ + + +
+ ]
249 [ + - + - : 78127 : assert(real[idx].capacity() == old_cap);
+ - + - +
- + - +
- ]
250 : 78127 : } else {
251 [ + - + - : 26173 : assert(real[idx].capacity() > old_cap);
+ - + - +
- + - +
- ]
252 [ + - + - : 26173 : assert(real[idx].capacity() <= 2 * (old_cap + 1));
+ - + - +
- + - +
- ]
253 : : }
254 : : break;
255 : 104300 : }
256 [ + + + + : 4032630 : if (existing_buffer_non_full && command-- == 0) {
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + ]
257 : : /* emplace_front() */
258 : 171654 : uint64_t seed{rng.rand64()};
259 : 171654 : size_t old_size = real[idx].size();
260 : 171654 : size_t old_cap = real[idx].capacity();
261 [ + - + - : 171654 : sim[idx].emplace_front(seed);
+ - + - +
- + - +
- ]
262 [ + - + - : 171654 : real[idx].emplace_front(seed);
+ - + - +
- + - +
- ]
263 [ + - + - : 171654 : assert(real[idx].size() == old_size + 1);
+ - + - +
- + - +
- ]
264 [ + + + + : 171654 : if (old_cap > old_size) {
+ + + + +
+ + + +
+ ]
265 [ - + + - : 134687 : assert(real[idx].capacity() == old_cap);
+ - + - +
- + - +
- ]
266 : 134687 : } else {
267 [ - + - + : 36967 : assert(real[idx].capacity() > old_cap);
- + - + -
+ - + -
+ ]
268 [ + - - + : 36967 : assert(real[idx].capacity() <= 2 * (old_cap + 1));
- + - + -
+ - + -
+ ]
269 : : }
270 : : break;
271 : 171654 : }
272 [ + + + + : 3860976 : if (existing_buffer_non_empty && command-- == 0) {
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + ]
273 : : /* front() [modifying] */
274 [ - + - + : 49700 : tmp = T(rng.rand64());
- + - + -
+ - + ]
275 : 49700 : size_t old_size = real[idx].size();
276 [ - + - + : 49700 : assert(sim[idx].front() == real[idx].front());
- + - + +
- + - + -
+ - + - +
- ]
277 [ + - + - : 49700 : sim[idx].front() = *tmp;
+ - ]
278 [ + - + - : 49700 : real[idx].front() = std::move(*tmp);
+ - ]
279 [ - + + - : 49700 : assert(real[idx].size() == old_size);
+ - + - +
- + - +
- ]
280 : : break;
281 : 49700 : }
282 [ + + + + : 3811276 : if (existing_buffer_non_empty && command-- == 0) {
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + ]
283 : : /* back() [modifying] */
284 [ - + - + : 42259 : tmp = T(rng.rand64());
- + - + -
+ - + ]
285 : 42259 : size_t old_size = real[idx].size();
286 [ - + - + : 42259 : assert(sim[idx].back() == real[idx].back());
- + - + +
- + - + -
+ - + - +
- ]
287 [ + - + - : 42259 : sim[idx].back() = *tmp;
+ - ]
288 [ + - + - : 42259 : real[idx].back() = *tmp;
+ - ]
289 [ - + - + : 42259 : assert(real[idx].size() == old_size);
- + - + +
- + - +
- ]
290 : : break;
291 : 42259 : }
292 [ + + + + : 3769017 : if (existing_buffer_non_empty && command-- == 0) {
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + ]
293 : : /* operator[] [modifying] */
294 [ - + - + : 63315 : tmp = T(rng.rand64());
- + - + -
+ - + ]
295 [ - + ]: 63315 : size_t pos = provider.ConsumeIntegralInRange<size_t>(0, sim[idx].size() - 1);
296 : 63315 : size_t old_size = real[idx].size();
297 [ - + - + : 63315 : assert(sim[idx][pos] == real[idx][pos]);
- + - + +
- + - + -
+ - + - +
- ]
298 [ + - + - : 63315 : sim[idx][pos] = *tmp;
+ - ]
299 [ + - + - : 63315 : real[idx][pos] = std::move(*tmp);
+ - ]
300 [ - + - + : 63315 : assert(real[idx].size() == old_size);
- + - + +
- + - +
- ]
301 : : break;
302 : 63315 : }
303 [ + + + + : 3705702 : if (existing_buffer_non_empty && command-- == 0) {
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + ]
304 : : /* pop_front() */
305 [ - + - + : 224714 : assert(sim[idx].front() == real[idx].front());
- + - + +
- - + + -
- + + - -
+ ]
306 : 224714 : size_t old_size = real[idx].size();
307 : 224714 : sim[idx].pop_front();
308 [ - + - + : 224714 : real[idx].pop_front();
- + - + -
+ - + -
+ ]
309 [ - + + - : 224714 : assert(real[idx].size() == old_size - 1);
+ - + - +
- + - +
- ]
310 : : break;
311 : 224714 : }
312 [ + + + + : 3480988 : if (existing_buffer_non_empty && command-- == 0) {
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + ]
313 : : /* pop_back() */
314 [ - + - + : 52059 : assert(sim[idx].back() == real[idx].back());
- + - + +
- - + + -
- + + - -
+ ]
315 : 52059 : size_t old_size = real[idx].size();
316 : 52059 : sim[idx].pop_back();
317 [ - + - + : 52059 : real[idx].pop_back();
- + - + -
+ - + -
+ ]
318 [ + - + - : 52059 : assert(real[idx].size() == old_size - 1);
+ - + - -
+ - + -
+ ]
319 : : break;
320 : 52059 : }
321 : : }
322 : 2584176 : }
323 : :
324 : : /* Fully compare the final state. */
325 [ + + + + : 14588 : for (unsigned i = 0; i < sim.size(); ++i) {
+ + + + +
+ + + +
+ ]
326 : : // Make sure const getters work.
327 : 10241 : const VecDeque<T>& realbuf = real[i];
328 : 10241 : const std::deque<T>& simbuf = sim[i];
329 [ + - + - : 10241 : compare_fn(realbuf, simbuf);
+ - + - +
- + - +
- ]
330 [ + + + + : 37954 : for (unsigned j = 0; j < sim.size(); ++j) {
+ + + + +
+ + + +
+ ]
331 [ + - + - : 27713 : assert((realbuf == real[j]) == (simbuf == sim[j]));
- + + - +
- - + + -
+ - - + +
- + - - +
+ - + - -
+ + - + -
- + + - +
- - + ]
332 [ + - + - : 27713 : assert(((realbuf <=> real[j]) >= 0) == (simbuf >= sim[j]));
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - ]
333 [ + - + - : 27713 : assert(((realbuf <=> real[j]) <= 0) == (simbuf <= sim[j]));
- + + - +
- - + + -
+ - - + +
- + - - +
+ - + - -
+ + - + -
- + + - +
- - + ]
334 : 27713 : }
335 : : // Clear out the buffers so we can check below that no objects exist anymore.
336 : 10241 : sim[i].clear();
337 : 10241 : real[i].clear();
338 : 10241 : }
339 : :
340 : : if constexpr (CheckNoneLeft) {
341 : 1863 : tmp = std::nullopt;
342 [ + - + - : 1863 : T::CheckNoneExist();
+ - ]
343 : : }
344 : 4347 : }
345 : :
346 : : /** Data structure with built-in tracking of all existing objects. */
347 : : template<size_t Size>
348 : : class TrackedObj
349 : : {
350 : : static_assert(Size > 0);
351 : :
352 : : /* Data type for map that actually stores the object data.
353 : : *
354 : : * The key is a pointer to the TrackedObj, the value is the uint64_t it was initialized with.
355 : : * Default-constructed and moved-from objects hold an std::nullopt.
356 : : */
357 : : using track_map_type = std::map<const TrackedObj<Size>*, std::optional<uint64_t>>;
358 : :
359 : : private:
360 : :
361 : : /** Actual map. */
362 : 3 : static inline track_map_type g_tracker;
363 : :
364 : : /** Iterators into the tracker map for this object.
365 : : *
366 : : * This is an array of size Size, all holding the same value, to give the object configurable
367 : : * size. The value is g_tracker.end() if this object is not fully initialized. */
368 : : typename track_map_type::iterator m_track_entry[Size];
369 : :
370 : 32905020 : void Check() const
371 : : {
372 : 32905020 : auto it = g_tracker.find(this);
373 [ + + + + : 263240160 : for (size_t i = 0; i < Size; ++i) {
+ + ]
374 [ + - + - : 230335140 : assert(m_track_entry[i] == it);
+ - ]
375 : 230335140 : }
376 : 32905020 : }
377 : :
378 : : /** Create entry for this object in g_tracker and populate m_track_entry. */
379 : 7637748 : void Register()
380 : : {
381 : 61101984 : auto [it, inserted] = g_tracker.emplace(this, std::nullopt);
382 [ + - + - : 7637748 : assert(inserted);
+ - ]
383 [ + + + + : 61101984 : for (size_t i = 0; i < Size; ++i) {
+ + ]
384 : 53464236 : m_track_entry[i] = it;
385 : 53464236 : }
386 : 7637748 : }
387 : :
388 : 7637748 : void Deregister()
389 : : {
390 : 7637748 : Check();
391 [ + - + - : 7637748 : assert(m_track_entry[0] != g_tracker.end());
+ - ]
392 : 7637748 : g_tracker.erase(m_track_entry[0]);
393 [ + + + + : 61101984 : for (size_t i = 0; i < Size; ++i) {
+ + ]
394 : 53464236 : m_track_entry[i] = g_tracker.end();
395 : 53464236 : }
396 : 7637748 : }
397 : :
398 : : /** Get value corresponding to this object in g_tracker. */
399 : 9149112 : std::optional<uint64_t>& Deref()
400 : : {
401 : 9149112 : Check();
402 [ + - + - : 9149112 : assert(m_track_entry[0] != g_tracker.end());
+ - ]
403 : 9149112 : return m_track_entry[0]->second;
404 : : }
405 : :
406 : : /** Get value corresponding to this object in g_tracker. */
407 : 16118160 : const std::optional<uint64_t>& Deref() const
408 : : {
409 : 16118160 : Check();
410 [ + - + - : 16118160 : assert(m_track_entry[0] != g_tracker.end());
+ - ]
411 : 16118160 : return m_track_entry[0]->second;
412 : : }
413 : :
414 : : public:
415 [ + - + - : 7637748 : ~TrackedObj() { Deregister(); }
+ - ]
416 : 2435100 : TrackedObj() { Register(); }
417 : :
418 : 467256 : TrackedObj(uint64_t value)
419 : : {
420 : 467256 : Register();
421 : 467256 : Deref() = value;
422 : 467256 : }
423 : :
424 : 3707244 : TrackedObj(const TrackedObj& other)
425 : : {
426 : 3707244 : Register();
427 : 3707244 : Deref() = other.Deref();
428 : 3707244 : }
429 : :
430 : 1028148 : TrackedObj(TrackedObj&& other)
431 : : {
432 : 1028148 : Register();
433 : 1028148 : Deref() = other.Deref();
434 : 1028148 : other.Deref() = std::nullopt;
435 : 1028148 : }
436 : :
437 : 1051890 : TrackedObj& operator=(const TrackedObj& other)
438 : : {
439 [ + - + - : 1051890 : if (this == &other) return *this;
+ - ]
440 : 1051890 : Deref() = other.Deref();
441 : 1051890 : return *this;
442 : 1051890 : }
443 : :
444 : 279426 : TrackedObj& operator=(TrackedObj&& other)
445 : : {
446 [ + - + - : 279426 : if (this == &other) return *this;
+ - ]
447 : 279426 : Deref() = other.Deref();
448 : 279426 : other.Deref() = std::nullopt;
449 : 279426 : return *this;
450 : 279426 : }
451 : :
452 : 5256201 : friend bool operator==(const TrackedObj& a, const TrackedObj& b)
453 : : {
454 : 5256201 : return a.Deref() == b.Deref();
455 : : }
456 : :
457 : 254832 : friend std::strong_ordering operator<=>(const TrackedObj& a, const TrackedObj& b)
458 : : {
459 : : // Libc++ 15 & 16 do not support std::optional<T>::operator<=> yet. See
460 : : // https://reviews.llvm.org/D146392.
461 [ + + + + : 254832 : if (!a.Deref().has_value() || !b.Deref().has_value()) {
+ + + + +
+ + + ]
462 : 173376 : return a.Deref().has_value() <=> b.Deref().has_value();
463 : : }
464 : 81456 : return *a.Deref() <=> *b.Deref();
465 : 254832 : }
466 : :
467 : 1863 : static void CheckNoneExist()
468 : : {
469 [ + - + - : 1863 : assert(g_tracker.empty());
+ - ]
470 : 1863 : }
471 : : };
472 : :
473 : : } // namespace
474 : :
475 [ + - + - ]: 624 : FUZZ_TARGET(vecdeque)
476 : : {
477 : : // Run the test with simple uints (which satisfy all the trivial properties).
478 : : static_assert(std::is_trivially_copyable_v<uint32_t>);
479 : : static_assert(std::is_trivially_destructible_v<uint64_t>);
480 : 621 : TestType<uint8_t, false>(buffer, 1);
481 : 621 : TestType<uint16_t, false>(buffer, 2);
482 : 621 : TestType<uint32_t, false>(buffer, 3);
483 : 621 : TestType<uint64_t, false>(buffer, 4);
484 : :
485 : : // Run the test with TrackedObjs (which do not).
486 : : static_assert(!std::is_trivially_copyable_v<TrackedObj<3>>);
487 : : static_assert(!std::is_trivially_destructible_v<TrackedObj<17>>);
488 : 621 : TestType<TrackedObj<1>, true>(buffer, 5);
489 : 621 : TestType<TrackedObj<3>, true>(buffer, 6);
490 : 621 : TestType<TrackedObj<17>, true>(buffer, 7);
491 : 621 : }
|
