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
26using 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
32namespace {
33
34template <std::size_t VarCount = 4, unsigned Bits = 2>
35int 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
221TEST_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
254TEST_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
319TEST_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