1 | // |
2 | // immer: immutable data structures for C++ |
3 | // Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente |
4 | // |
5 | // This software is distributed under the Boost Software License, Version 1.0. |
6 | // See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt |
7 | // |
8 | |
9 | #include "extra/fuzzer/fuzzer_input.hpp" |
10 | #include <immer/flex_vector.hpp> |
11 | #include <immer/flex_vector_transient.hpp> |
12 | #include <immer/heap/gc_heap.hpp> |
13 | #include <immer/refcount/no_refcount_policy.hpp> |
14 | #include <array> |
15 | #include <iostream> |
16 | #include <catch.hpp> |
17 | |
18 | #define IMMER_FUZZED_TRACE_ENABLE 0 |
19 | |
20 | #if IMMER_FUZZED_TRACE_ENABLE |
21 | #define IMMER_FUZZED_TRACE(...) std::cout << __VA_ARGS__ << std::endl; |
22 | #else |
23 | #define IMMER_FUZZED_TRACE(...) |
24 | #endif |
25 | |
26 | using gc_memory = immer::memory_policy< |
27 | immer::heap_policy<immer::gc_heap>, |
28 | immer::no_refcount_policy, |
29 | immer::gc_transience_policy, |
30 | false>; |
31 | |
32 | namespace { |
33 | |
34 | template <std::size_t VarCount = 4, unsigned Bits = 2> |
35 | int run_input(const std::uint8_t* data, std::size_t size) |
36 | { |
37 | using vector_t = immer::flex_vector<int, gc_memory, Bits, Bits>; |
38 | using transient_t = typename vector_t::transient_type; |
39 | using size_t = std::uint8_t; |
40 | |
41 | auto vs = std::array<vector_t, VarCount>{}; |
42 | auto ts = std::array<transient_t, VarCount>{}; |
43 | |
44 | #if IMMER_FUZZED_TRACE_ENABLE |
45 | std::cout << "/// new test run" << std::endl; |
46 | for (auto i = 0; i < VarCount; ++i) |
47 | std::cout << "auto v" << i << " = vector_t{};" << std::endl; |
48 | for (auto i = 0; i < VarCount; ++i) |
49 | std::cout << "auto t" << i << " = transient_t{};" << std::endl; |
50 | #endif |
51 | |
52 | auto is_valid_var = [&] (auto idx) { |
53 | return idx >= 0 && idx < VarCount; |
54 | }; |
55 | auto is_valid_var_neq = [](auto other) { |
56 | return [=] (auto idx) { |
57 | return idx >= 0 && idx < VarCount && idx != other; |
58 | }; |
59 | }; |
60 | auto is_valid_index = [] (auto& v) { |
61 | return [&] (auto idx) { return idx >= 0 && idx < v.size(); }; |
62 | }; |
63 | auto is_valid_size = [] (auto& v) { |
64 | return [&] (auto idx) { return idx >= 0 && idx <= v.size(); }; |
65 | }; |
66 | auto can_concat = [] (auto&& v1, auto&& v2) { |
67 | using size_type = decltype(v1.size()); |
68 | auto max = std::numeric_limits<size_type>::max() >> (Bits * 4); |
69 | return v1.size() < max && v2.size() < max; |
70 | }; |
71 | |
72 | return fuzzer_input{data, size}.run([&] (auto& in) |
73 | { |
74 | enum ops { |
75 | op_transient, |
76 | op_persistent, |
77 | op_push_back, |
78 | op_update, |
79 | op_take, |
80 | op_drop, |
81 | op_concat, |
82 | op_push_back_mut, |
83 | op_update_mut, |
84 | op_take_mut, |
85 | op_drop_mut, |
86 | op_prepend_mut, |
87 | op_prepend_mut_move, |
88 | op_append_mut, |
89 | op_append_mut_move, |
90 | }; |
91 | auto dst = read<std::uint8_t>(in, is_valid_var); |
92 | switch (read<char>(in)) |
93 | { |
94 | case op_transient: { |
95 | auto src = read<std::uint8_t>(in, is_valid_var); |
96 | IMMER_FUZZED_TRACE( |
97 | "t" << +dst << " = v" << +src << ".transient();" ); |
98 | ts[dst] = vs[src].transient(); |
99 | break; |
100 | } |
101 | case op_persistent: { |
102 | auto src = read<std::uint8_t>(in, is_valid_var); |
103 | IMMER_FUZZED_TRACE( |
104 | "v" << +dst << " = t" << +src << ".persistent();" ); |
105 | vs[dst] = ts[src].persistent(); |
106 | break; |
107 | } |
108 | case op_push_back: { |
109 | auto src = read<std::uint8_t>(in, is_valid_var); |
110 | IMMER_FUZZED_TRACE( |
111 | "v" << +dst << " = v" << +src << |
112 | ".push_back(42);" ); |
113 | vs[dst] = vs[src].push_back(42); |
114 | break; |
115 | } |
116 | case op_update: { |
117 | auto src = read<std::uint8_t>(in, is_valid_var); |
118 | auto idx = read<size_t>(in, is_valid_index(vs[src])); |
119 | IMMER_FUZZED_TRACE( |
120 | "v" << +dst << " = v" << +src << |
121 | ".update(" << +idx << ", [] (auto x) { return x + 1; });" ); |
122 | vs[dst] = vs[src].update(idx, [] (auto x) { return x + 1; }); |
123 | break; |
124 | } |
125 | case op_take: { |
126 | auto src = read<std::uint8_t>(in, is_valid_var); |
127 | auto idx = read<size_t>(in, is_valid_size(vs[src])); |
128 | IMMER_FUZZED_TRACE( |
129 | "v" << +dst << " = v" << +src << |
130 | ".take(" << +idx << ");" ); |
131 | vs[dst] = vs[src].take(idx); |
132 | break; |
133 | } |
134 | case op_drop: { |
135 | auto src = read<std::uint8_t>(in, is_valid_var); |
136 | auto idx = read<size_t>(in, is_valid_size(vs[src])); |
137 | IMMER_FUZZED_TRACE( |
138 | "v" << +dst << " = v" << +src << |
139 | ".take(" << +idx << ");" ); |
140 | vs[dst] = vs[src].drop(idx); |
141 | break; |
142 | } |
143 | case op_concat: { |
144 | auto src = read<std::uint8_t>(in, is_valid_var); |
145 | auto src2 = read<std::uint8_t>(in, is_valid_var); |
146 | if (can_concat(vs[src], vs[src2])) { |
147 | IMMER_FUZZED_TRACE( |
148 | "v" << +dst << " = v" << +src << " + v" << +src2 << ";" ); |
149 | vs[dst] = vs[src] + vs[src2]; |
150 | } |
151 | break; |
152 | } |
153 | case op_push_back_mut: { |
154 | IMMER_FUZZED_TRACE("t" << +dst << ".push_back(13);" ); |
155 | ts[dst].push_back(13); |
156 | break; |
157 | } |
158 | case op_update_mut: { |
159 | auto idx = read<size_t>(in, is_valid_index(ts[dst])); |
160 | IMMER_FUZZED_TRACE( |
161 | "t" << +dst << ".update(" |
162 | << +idx << ", [] (auto x) { return x + 1; });" ); |
163 | ts[dst].update(idx, [] (auto x) { return x + 1; }); |
164 | break; |
165 | } |
166 | case op_take_mut: { |
167 | auto idx = read<size_t>(in, is_valid_size(ts[dst])); |
168 | IMMER_FUZZED_TRACE("t" << +dst << ").take(" << +idx << ");" ); |
169 | ts[dst].take(idx); |
170 | break; |
171 | } |
172 | case op_prepend_mut: { |
173 | auto src = read<std::uint8_t>(in, is_valid_var_neq(dst)); |
174 | if (can_concat(ts[dst], ts[src])) { |
175 | IMMER_FUZZED_TRACE( |
176 | "t" << +dst << ".prepend(t" << +src << ");" ); |
177 | ts[dst].prepend(ts[src]); |
178 | } |
179 | break; |
180 | } |
181 | case op_prepend_mut_move: { |
182 | auto src = read<std::uint8_t>(in, is_valid_var_neq(dst)); |
183 | if (can_concat(ts[dst], ts[src])) { |
184 | IMMER_FUZZED_TRACE( |
185 | "t" << +dst << ".prepend(std::move(t" << +src << "));" |
186 | << " t" << +src << " = {};" ); |
187 | ts[dst].prepend(std::move(ts[src])); |
188 | ts[src] = {}; |
189 | } |
190 | break; |
191 | } |
192 | case op_append_mut: { |
193 | auto src = read<std::uint8_t>(in, is_valid_var_neq(dst)); |
194 | if (can_concat(ts[dst], ts[src])) { |
195 | IMMER_FUZZED_TRACE( |
196 | "t" << +dst << ".append(t" << +src << ");" ); |
197 | ts[dst].append(ts[src]); |
198 | } |
199 | break; |
200 | } |
201 | case op_append_mut_move: { |
202 | auto src = read<std::uint8_t>(in, is_valid_var_neq(dst)); |
203 | if (can_concat(ts[dst], ts[src])) { |
204 | IMMER_FUZZED_TRACE( |
205 | "t" << +dst << ".append(std::move(t" << +src << "));" |
206 | << " t" << +src << " = {};" ); |
207 | ts[dst].append(std::move(ts[src])); |
208 | ts[src] = {}; |
209 | } |
210 | break; |
211 | } |
212 | default: |
213 | break; |
214 | }; |
215 | return true; |
216 | }); |
217 | } |
218 | |
219 | } // anonymous |
220 | |
221 | TEST_CASE("bug: concatenating transients" ) |
222 | { |
223 | // When concatenating two transients vectors the nodes from the |
224 | // argument become aliased in the result. As such, we need to |
225 | // reset the identitiy of the argument. |
226 | SECTION("simplified" ) |
227 | { |
228 | using vector_t = immer::flex_vector<int, gc_memory, 2, 2>; |
229 | auto t0 = vector_t{}.transient(); |
230 | t0.push_back(42); |
231 | t0.push_back(42); |
232 | t0.push_back(42); |
233 | t0.push_back(42); |
234 | t0.push_back(42); |
235 | t0.push_back(42); |
236 | auto t1 = t0; |
237 | t1.append(t0); |
238 | t1.append(t0); |
239 | t0.append(t1); |
240 | t1.append(t0); |
241 | } |
242 | |
243 | #if __GNUC__ != 9 |
244 | SECTION("" ) |
245 | { |
246 | constexpr std::uint8_t input[] = { |
247 | 0x2,0x2,0x2,0x2,0x29,0x32,0x0,0x0,0x2,0x2,0x2,0x2,0x2,0x2,0x2,0x2,0x2,0x2,0x2,0x2,0x6,0x2,0x2,0x2,0x2,0x2,0x6,0x2,0x2,0x2,0x0,0x38,0x2,0x0,0x0,0x2,0x2,0xd,0x0,0x0,0x3b,0xff,0x3a,0x2,0xd,0xd,0x2,0x0,0x0,0x10,0xe,0x0,0xd,0x0,0x0,0x2,0x2,0xd,0x0,0x1,0x5, |
248 | }; |
249 | CHECK(run_input(input, sizeof(input)) == 0); |
250 | } |
251 | #endif |
252 | } |
253 | |
254 | TEST_CASE("bug: concatenating moved transients" ) |
255 | { |
256 | // A moved from concatenated transient is totally smashed, we can |
257 | // not do anything with it but reasign... |
258 | SECTION("simplified" ) |
259 | { |
260 | using vector_t = immer::flex_vector<int, gc_memory, 2, 2>; |
261 | using transient_t = typename vector_t::transient_type; |
262 | auto v0 = vector_t{}; |
263 | auto t0 = transient_t{}; |
264 | auto t2 = transient_t{}; |
265 | v0 = v0.push_back(42); |
266 | t2 = v0.transient(); |
267 | v0 = v0 + v0; |
268 | v0 = v0 + v0; |
269 | v0 = v0 + v0; |
270 | v0 = v0 + v0; |
271 | t0 = v0.transient(); |
272 | t0 = v0.transient(); |
273 | t0.append(std::move(t2)); t2 = {}; |
274 | t2.append(std::move(t0)); |
275 | } |
276 | |
277 | #if __GNUC__ != 9 |
278 | SECTION("" ) |
279 | { |
280 | constexpr std::uint8_t input[] = { |
281 | 0x0,0x2,0x0,0x2,0x0,0x0,0x0,0x6,0x0,0x0,0x0,0x6,0x0,0x0,0x0,0x9d,0x0,0x6,0x0,0x0,0x0,0x6,0x0,0x0,0x0,0x9d,0x28,0x0,0x0,0x0,0x0,0x0,0xf7,0xc5,0x0,0xa,0xa,0x0,0xfa,0xe7,0xff,0xe7,0xff,0x0,0xe,0x2,0x9,0x0,0x28,0x2,0xe,0x0,0x0,0x2,0xd,0x0,0x0,0x28,0x0,0xd,0x2,0x5,0x0,0x2, |
282 | }; |
283 | CHECK(run_input(input, sizeof(input)) == 0); |
284 | } |
285 | #endif |
286 | |
287 | SECTION("simplified" ) |
288 | { |
289 | using vector_t = immer::flex_vector<int, gc_memory, 2, 2>; |
290 | using transient_t = typename vector_t::transient_type; |
291 | auto v0 = vector_t{}; |
292 | auto t0 = transient_t{}; |
293 | auto t2 = transient_t{}; |
294 | v0 = v0.push_back(42); |
295 | v0 = v0.push_back(42); |
296 | v0 = v0 + v0; |
297 | t0 = v0.transient(); |
298 | t2.prepend(std::move(t0)); t0 = {}; |
299 | t0 = v0.transient(); |
300 | t0.push_back(13); |
301 | t2.append(std::move(t0)); t0 = {}; |
302 | t0 = v0.transient(); |
303 | t0.push_back(13); |
304 | t2.prepend(std::move(t0)); t0 = {}; |
305 | } |
306 | |
307 | #if __GNUC__ != 9 |
308 | SECTION("" ) |
309 | { |
310 | return; |
311 | constexpr std::uint8_t input[] = { |
312 | 0x0,0x2,0x0,0x0,0x2,0xb7,0x1,0x36,0x40,0x0,0x0,0x0,0x0,0xb6,0x0,0x2,0x0,0x0,0x6,0xe,0x0,0x0,0xfe,0x0,0x0,0xff,0x0,0x2,0xc,0xff,0xfc,0x29,0x0,0x0,0x0,0x0,0x0,0x7,0x2,0xe,0xff,0xfc,0x29,0x0,0x0,0x0,0x0,0x0,0x7,0x3,0x0,0x0,0x2,0xc,0x2,0xc,0x0,0xd,0x0,0x0,0x0,0x0,0x25,0x6, |
313 | }; |
314 | CHECK(run_input(input, sizeof(input)) == 0); |
315 | } |
316 | #endif |
317 | } |
318 | |
319 | TEST_CASE("bug: aegsdas" ) |
320 | { |
321 | SECTION("simplified" ) |
322 | { |
323 | using vector_t = immer::flex_vector<int, gc_memory, 2, 2>; |
324 | using transient_t = typename vector_t::transient_type; |
325 | auto v2 = vector_t{}; |
326 | auto t0 = transient_t{}; |
327 | auto t1 = transient_t{}; |
328 | v2 = v2.push_back(42); |
329 | v2 = v2.push_back(42); |
330 | v2 = v2.push_back(42); |
331 | v2 = v2.push_back(42); |
332 | v2 = v2.push_back(42); |
333 | t0 = v2.transient(); |
334 | t1.prepend(t0); |
335 | t1.prepend(t0); |
336 | t1.prepend(t0); |
337 | t0.prepend(std::move(t1)); t1 = {}; |
338 | } |
339 | |
340 | #if __GNUC__ != 9 |
341 | SECTION("" ) |
342 | { |
343 | constexpr std::uint8_t input[] = { |
344 | 0xff,0xff,0x2,0x2,0x2,0x2,0x2,0x2,0x2,0x2,0x2,0x82,0x2,0x2,0x2,0x2,0x2,0x2,0x0,0x0,0x3d,0x0,0x0,0x0,0x2,0x84,0x0,0x3b,0x1,0xb,0x0,0xa,0x1,0xb,0x0,0x0,0x3,0x2,0x0,0x3b,0x1,0xb,0x1,0x0,0x0,0xc,0xb,0x1,0x8,0xff,0xff,0xfc,0xfd,0x0,0x3b,0x3,0x2,0x0,0x3b,0x1,0x9,0x1,0x3b, |
345 | }; |
346 | CHECK(run_input(input, sizeof(input)) == 0); |
347 | } |
348 | #endif |
349 | } |
350 | |