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 <array> |
12 | #include <iostream> |
13 | #include <catch.hpp> |
14 | |
15 | #define IMMER_FUZZED_TRACE_ENABLE 0 |
16 | |
17 | #if IMMER_FUZZED_TRACE_ENABLE |
18 | #define IMMER_FUZZED_TRACE(...) std::cout << __VA_ARGS__ << std::endl; |
19 | #else |
20 | #define IMMER_FUZZED_TRACE(...) |
21 | #endif |
22 | |
23 | namespace { |
24 | |
25 | template <std::size_t VarCount = 2, unsigned Bits = 2> |
26 | int run_input(const std::uint8_t* data, std::size_t size) |
27 | { |
28 | using vector_t = immer::flex_vector<int, immer::default_memory_policy, Bits, Bits>; |
29 | using size_t = std::uint8_t; |
30 | |
31 | auto vars = std::array<vector_t, VarCount>{}; |
32 | |
33 | #if IMMER_FUZZED_TRACE_ENABLE |
34 | std::cout << "/// new test run" << std::endl; |
35 | for (auto i = 0u; i < VarCount; ++i) |
36 | std::cout << "auto var" << i << " = vector_t{};" << std::endl; |
37 | #endif |
38 | |
39 | auto is_valid_var = [&] (auto idx) { |
40 | return idx >= 0 && idx < VarCount; |
41 | }; |
42 | auto is_valid_var_neq = [](auto other) { |
43 | return [=] (auto idx) { |
44 | return idx >= 0 && idx < VarCount && idx != other; |
45 | }; |
46 | }; |
47 | auto is_valid_index = [] (auto& v) { |
48 | return [&] (auto idx) { return idx >= 0 && idx < v.size(); }; |
49 | }; |
50 | auto is_valid_size = [] (auto& v) { |
51 | return [&] (auto idx) { return idx >= 0 && idx <= v.size(); }; |
52 | }; |
53 | auto can_concat = [] (auto&& v1, auto&& v2) { |
54 | using size_type = decltype(v1.size()); |
55 | return v2.size() < (std::numeric_limits<size_type>::max() - v1.size()); |
56 | }; |
57 | auto can_insert = [] (auto&& v1) { |
58 | using size_type = decltype(v1.size()); |
59 | return v1.size() < std::numeric_limits<size_type>::max(); |
60 | }; |
61 | |
62 | return fuzzer_input{data, size}.run([&] (auto& in) |
63 | { |
64 | enum ops { |
65 | op_push_back, |
66 | op_update, |
67 | op_take, |
68 | op_drop, |
69 | op_concat, |
70 | op_push_back_move, |
71 | op_update_move, |
72 | op_take_move, |
73 | op_drop_move, |
74 | op_concat_move_l, |
75 | op_concat_move_r, |
76 | op_concat_move_lr, |
77 | }; |
78 | auto src = read<std::uint8_t>(in, is_valid_var); |
79 | auto dst = read<std::uint8_t>(in, is_valid_var); |
80 | switch (read<char>(in)) |
81 | { |
82 | case op_push_back: |
83 | if (can_insert(vars[src])) { |
84 | IMMER_FUZZED_TRACE( |
85 | "var" << +dst << " = var" << +src << |
86 | ".push_back(42);" ); |
87 | vars[dst] = vars[src].push_back(42); |
88 | } |
89 | break; |
90 | case op_update: { |
91 | auto idx = read<size_t>(in, is_valid_index(vars[src])); |
92 | IMMER_FUZZED_TRACE( |
93 | "var" << +dst << " = var" << +src << |
94 | ".update(" << +idx << ", [] (auto x) { return x + 1; });" ); |
95 | vars[dst] = vars[src].update(idx, [] (auto x) { return x + 1; }); |
96 | break; |
97 | } |
98 | case op_take: { |
99 | auto idx = read<size_t>(in, is_valid_size(vars[src])); |
100 | IMMER_FUZZED_TRACE( |
101 | "var" << +dst << " = var" << +src << |
102 | ".take(" << +idx << ");" ); |
103 | vars[dst] = vars[src].take(idx); |
104 | break; |
105 | } |
106 | case op_drop: { |
107 | auto idx = read<size_t>(in, is_valid_size(vars[src])); |
108 | IMMER_FUZZED_TRACE( |
109 | "var" << +dst << " = var" << +src << |
110 | ".take(" << +idx << ");" ); |
111 | vars[dst] = vars[src].drop(idx); |
112 | break; |
113 | } |
114 | case op_concat: { |
115 | auto src2 = read<std::uint8_t>(in, is_valid_var); |
116 | if (can_concat(vars[src], vars[src2])) { |
117 | IMMER_FUZZED_TRACE( |
118 | "var" << +dst << " = var" << +src << " + var" << +src2 << ";" ); |
119 | vars[dst] = vars[src] + vars[src2]; |
120 | } |
121 | break; |
122 | } |
123 | case op_push_back_move: { |
124 | if (can_insert(vars[src])) { |
125 | IMMER_FUZZED_TRACE( |
126 | "var" << +dst << " = std::move(var" << +src << |
127 | ").push_back(21);" ); |
128 | vars[dst] = std::move(vars[src]).push_back(21); |
129 | } |
130 | break; |
131 | } |
132 | case op_update_move: { |
133 | auto idx = read<size_t>(in, is_valid_index(vars[src])); |
134 | IMMER_FUZZED_TRACE( |
135 | "var" << +dst << " = std::move(var" << +src << |
136 | ").update(" << +idx << ", [] (auto x) { return x + 1; });" ); |
137 | vars[dst] = std::move(vars[src]) |
138 | .update(idx, [] (auto x) { return x + 1; }); |
139 | break; |
140 | } |
141 | case op_take_move: { |
142 | auto idx = read<size_t>(in, is_valid_size(vars[src])); |
143 | IMMER_FUZZED_TRACE( |
144 | "var" << +dst << " = std::move(var" << +src << |
145 | ").take(" << +idx << ");" ); |
146 | vars[dst] = std::move(vars[src]).take(idx); |
147 | break; |
148 | } |
149 | case op_drop_move: { |
150 | auto idx = read<size_t>(in, is_valid_size(vars[src])); |
151 | IMMER_FUZZED_TRACE( |
152 | "var" << +dst << " = std::move(var" << +src << |
153 | ").drop(" << +idx << ");" ); |
154 | vars[dst] = std::move(vars[src]).drop(idx); |
155 | break; |
156 | } |
157 | case op_concat_move_l: { |
158 | auto src2 = read<std::uint8_t>(in, is_valid_var_neq(src)); |
159 | if (can_concat(vars[src], vars[src2])) { |
160 | IMMER_FUZZED_TRACE( |
161 | "var" << +dst << " = std::move(var" << +src |
162 | << ") + var" << +src2 << ";" ); |
163 | vars[dst] = std::move(vars[src]) + vars[src2]; |
164 | } |
165 | break; |
166 | } |
167 | case op_concat_move_r: { |
168 | auto src2 = read<std::uint8_t>(in, is_valid_var_neq(src)); |
169 | if (can_concat(vars[src], vars[src2])) { |
170 | IMMER_FUZZED_TRACE( |
171 | "var" << +dst << " = var" << +src |
172 | << " + std::move(var" << +src2 << ");" ); |
173 | vars[dst] = vars[src] + std::move(vars[src2]); |
174 | } |
175 | break; |
176 | } |
177 | case op_concat_move_lr: { |
178 | auto src2 = read<std::uint8_t>(in, is_valid_var_neq(src)); |
179 | if (can_concat(vars[src], vars[src2])) { |
180 | IMMER_FUZZED_TRACE( |
181 | "var" << +dst << " = std::move(var" << +src |
182 | << ") + std::move(var" << +src2 << ");" ); |
183 | vars[dst] = std::move(vars[src]) + std::move(vars[src2]); |
184 | } |
185 | break; |
186 | } |
187 | default: |
188 | break; |
189 | }; |
190 | return true; |
191 | }); |
192 | } |
193 | |
194 | } // anonymous |
195 | |
196 | TEST_CASE("bug: concat with moving the right side" ) |
197 | { |
198 | // This was a stupid bug on the concatenation of small vectors |
199 | // when moving one of the sides. |
200 | SECTION("simplified" ) |
201 | { |
202 | using vector_t = immer::flex_vector<int, immer::default_memory_policy, 2, 2>; |
203 | auto var0 = vector_t{}; |
204 | auto var1 = vector_t{}; |
205 | var0 = var0.push_back(42); |
206 | var0 = var0.push_back(42); |
207 | var0 = var0.push_back(42); |
208 | var1 = var0.push_back(42); |
209 | var0 = var0 + var0; |
210 | var0 = var0.push_back(42); |
211 | var0 = var0 + var1; |
212 | var0 = var0 + var0; |
213 | var0 = var0 + std::move(var1); |
214 | } |
215 | |
216 | #if __GNUC__ != 9 |
217 | SECTION("vm" ) |
218 | { |
219 | constexpr std::uint8_t input[] = { |
220 | 0x0,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0x0,0x0,0x0,0x0,0x1,0x0,0x40,0x28,0x0,0x4,0x3f,0x20,0x0,0x0,0x4,0x3f,0x8,0x0,0x0,0x0,0x0,0x1,0x0,0x0,0x0,0x4,0x3f,0x0,0x0,0x40,0x0,0x0,0x0,0x0,0x4,0x3f,0x1,0x0,0x0,0x4,0x3f,0x0,0x0,0xff,0x0,0xa,0x1,0x0,0xff,0x0,0x0, |
221 | }; |
222 | CHECK(run_input(input, sizeof(input)) == 0); |
223 | } |
224 | #endif |
225 | } |
226 | |