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
23namespace {
24
25template <std::size_t VarCount = 2, unsigned Bits = 2>
26int 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
196TEST_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