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 "test/dada.hpp"
10#include "test/util.hpp"
11#include "test/transient_tester.hpp"
12
13#include <immer/algorithm.hpp>
14
15#include <catch.hpp>
16#include <boost/range/adaptors.hpp>
17#include <boost/range/irange.hpp>
18
19#include <algorithm>
20#include <numeric>
21#include <vector>
22#include <array>
23
24#ifndef FLEX_VECTOR_T
25#error "define the vector template to use in FLEX_VECTOR_T"
26#endif
27
28#ifndef FLEX_VECTOR_TRANSIENT_T
29#error "define the vector template to use in FLEX_VECTOR_TRANSIENT_T"
30#endif
31
32#ifndef VECTOR_T
33#error "define the vector template to use in VECTOR_T"
34#endif
35
36template <typename V=VECTOR_T<unsigned>>
37auto make_test_flex_vector(unsigned min, unsigned max)
38{
39 auto v = V{};
40 for (auto i = min; i < max; ++i)
41 v = v.push_back({i});
42 return v;
43}
44
45template <typename V=FLEX_VECTOR_T<unsigned>>
46auto make_test_flex_vector_front(unsigned min, unsigned max)
47{
48 auto v = V{};
49 for (auto i = max; i > min;)
50 v = v.push_front({--i});
51 return v;
52}
53
54TEST_CASE("from flex_vector and to flex_vector")
55{
56 constexpr auto n = 100u;
57
58 auto v = make_test_flex_vector(0, n).transient();
59 CHECK_VECTOR_EQUALS(v, boost::irange(0u, n));
60
61 auto p = v.persistent();
62 CHECK_VECTOR_EQUALS(p, boost::irange(0u, n));
63}
64
65TEST_CASE("adopt regular vector contents")
66{
67 const auto n = 666u;
68 auto v = VECTOR_T<unsigned>{};
69 for (auto i = 0u; i < n; ++i) {
70 v = v.push_back(i);
71 auto fv = FLEX_VECTOR_TRANSIENT_T<unsigned>{v.transient()};
72 CHECK_VECTOR_EQUALS_AUX(v, fv, [] (auto&& v) { return &v; });
73 }
74}
75
76TEST_CASE("drop move")
77{
78 using vector_t = FLEX_VECTOR_T<unsigned>;
79
80 auto v = vector_t{};
81
82 auto check_move = [&] (vector_t&& x) -> vector_t&& {
83 if (vector_t::memory_policy::use_transient_rvalues)
84 CHECK(&x == &v);
85 else
86 CHECK(&x != &v);
87 return std::move(x);
88 };
89
90 v = v.push_back(0).push_back(1);
91
92 auto addr_before = &v[0];
93 v = check_move(std::move(v).drop(1));
94 auto addr_after = &v[0];
95
96 if (vector_t::bits_leaf > 0 &&
97 vector_t::memory_policy::use_transient_rvalues)
98 CHECK(addr_before == addr_after);
99 else
100 CHECK(addr_before != addr_after);
101
102 CHECK_VECTOR_EQUALS(v, boost::irange(1u, 2u));
103}
104
105TEST_CASE("exception safety relaxed")
106{
107 using dadaist_vector_t = typename dadaist_wrapper<FLEX_VECTOR_T<unsigned>>::type;
108 constexpr auto n = 667u;
109
110 SECTION("push back")
111 {
112 auto half = n / 2;
113 auto t = as_transient_tester(
114 make_test_flex_vector_front<dadaist_vector_t>(0, half));
115 auto d = dadaism{};
116 for (auto li = half, i = half; i < n;) {
117 auto s = d.next();
118 try {
119 if (t.transient)
120 t.vt.push_back({i});
121 else
122 t.vp = t.vp.push_back({i});
123 ++i;
124 } catch (dada_error) {}
125 if (t.step())
126 li = i;
127 if (t.transient) {
128 CHECK_VECTOR_EQUALS(t.vt, boost::irange(0u, i));
129 CHECK_VECTOR_EQUALS(t.vp, boost::irange(0u, li));
130 } else {
131 CHECK_VECTOR_EQUALS(t.vp, boost::irange(0u, i));
132 CHECK_VECTOR_EQUALS(t.vt, boost::irange(0u, li));
133 }
134 }
135 CHECK(d.happenings > 0);
136 CHECK(t.d.happenings > 0);
137 IMMER_TRACE_E(d.happenings);
138 IMMER_TRACE_E(t.d.happenings);
139 }
140
141 SECTION("update")
142 {
143 using boost::join;
144 using boost::irange;
145
146 auto t = as_transient_tester(
147 make_test_flex_vector_front<dadaist_vector_t>(0, n));
148 auto d = dadaism{};
149 for (auto li = 0u, i = 0u; i < n;) {
150 auto s = d.next();
151 try {
152 if (t.transient) {
153 t.vt.update(i, [] (auto x) { return dada(), x + 1; });
154 } else {
155 t.vp = t.vp.update(i, [] (auto x) { return dada(), x + 1; });
156 }
157 ++i;
158 } catch (dada_error) {}
159 if (t.step())
160 li = i;
161 if (t.transient) {
162 CHECK_VECTOR_EQUALS(t.vt, join(irange(1u, 1u + i), irange(i, n)));
163 CHECK_VECTOR_EQUALS(t.vp, join(irange(1u, 1u + li), irange(li, n)));
164 } else {
165 CHECK_VECTOR_EQUALS(t.vp, join(irange(1u, 1u + i), irange(i, n)));
166 CHECK_VECTOR_EQUALS(t.vt, join(irange(1u, 1u + li), irange(li, n)));
167 }
168 }
169 CHECK(d.happenings > 0);
170 CHECK(t.d.happenings > 0);
171 }
172
173 SECTION("take")
174 {
175 auto t = as_transient_tester(
176 make_test_flex_vector_front<dadaist_vector_t>(0, n));
177 auto d = dadaism{};
178 auto deltas = magic_rotator();
179 auto delta = deltas.next();
180 for (auto i = n, li = i;;) {
181 auto s = d.next();
182 auto r = dadaist_vector_t{};
183 try {
184 if (t.transient)
185 t.vt.take(i);
186 else
187 t.vp = t.vp.take(i);
188 if (t.step())
189 li = i;
190 delta = deltas.next();
191 if (i < delta)
192 break;
193 i -= delta;
194 } catch (dada_error) {}
195 if (t.transient) {
196 CHECK_VECTOR_EQUALS(t.vt, boost::irange(0u, i + delta));
197 CHECK_VECTOR_EQUALS(t.vp, boost::irange(0u, li));
198 } else {
199 CHECK_VECTOR_EQUALS(t.vp, boost::irange(0u, i + delta));
200 CHECK_VECTOR_EQUALS(t.vt, boost::irange(0u, li));
201 }
202 }
203 CHECK(d.happenings > 0);
204 CHECK(t.d.happenings > 0);
205 }
206
207 SECTION("drop")
208 {
209 auto t = as_transient_tester(
210 make_test_flex_vector<dadaist_vector_t>(0, n));
211 auto d = dadaism{};
212 auto deltas = magic_rotator();
213 auto delta = deltas.next();
214 for (auto i = delta, li = 0u; i < n;) {
215 auto s = d.next();
216 auto r = dadaist_vector_t{};
217 try {
218 if (t.transient)
219 t.vt.drop(delta);
220 else
221 t.vp = t.vp.drop(delta);
222 if (t.step()) {
223 li = i;
224 }
225 delta = deltas.next();
226 i += delta;
227 } catch (dada_error) {}
228 if (t.transient) {
229 CHECK_VECTOR_EQUALS(t.vt, boost::irange(i - delta, n));
230 CHECK_VECTOR_EQUALS(t.vp, boost::irange(li, n));
231 } else {
232 CHECK_VECTOR_EQUALS(t.vp, boost::irange(i - delta, n));
233 CHECK_VECTOR_EQUALS(t.vt, boost::irange(li, n));
234 }
235 }
236 CHECK(d.happenings > 0);
237 CHECK(t.d.happenings > 0);
238 }
239
240 SECTION("append")
241 {
242 auto make_ = [](auto i, auto delta) {
243 auto d = dadaism::disable();
244 return make_test_flex_vector<dadaist_vector_t>(i, i + delta);
245 };
246 auto t = as_transient_tester(dadaist_vector_t{});
247 auto d = dadaism();
248 auto deltas = magic_rotator();
249 auto delta = deltas.next();
250 for (auto i = 0u, li = 0u; i < n;) {
251 try {
252 if (t.transient) {
253 auto data = make_(i, delta);
254 auto datat = data.transient();
255 t.vt.append(datat);
256 } else {
257 auto data = make_(i, delta);
258 t.vp = t.vp + data;
259 }
260 i += delta;
261 if (t.step()) {
262 li = i;
263 }
264 delta = deltas.next() * 3;
265 } catch (dada_error) {}
266 if (t.transient) {
267 CHECK_VECTOR_EQUALS(t.vt, boost::irange(0u, i));
268 CHECK_VECTOR_EQUALS(t.vp, boost::irange(0u, li));
269 } else {
270 CHECK_VECTOR_EQUALS(t.vp, boost::irange(0u, i));
271 CHECK_VECTOR_EQUALS(t.vt, boost::irange(0u, li));
272 }
273 }
274 CHECK(d.happenings == 0);
275 CHECK(t.d.happenings > 0);
276 }
277
278 SECTION("append mut")
279 {
280 auto make_ = [](auto i, auto delta) {
281 auto d = dadaism::disable();
282 return make_test_flex_vector<dadaist_vector_t>(i, i + delta);
283 };
284 auto t = as_transient_tester(dadaist_vector_t{});
285 auto d = dadaism();
286 auto deltas = magic_rotator();
287 auto delta = deltas.next();
288 for (auto i = 0u, li = 0u; i < n;) {
289 try {
290 if (t.transient) {
291 auto data = make_(i, delta);
292 auto datat = data.transient();
293 t.vt.append(std::move(datat));
294 } else {
295 auto data = make_(i, delta);
296 t.vp = t.vp + data;
297 }
298 i += delta;
299 if (t.step()) {
300 li = i;
301 }
302 delta = deltas.next() * 3;
303 } catch (dada_error) {}
304 if (t.transient) {
305 CHECK_VECTOR_EQUALS(t.vt, boost::irange(0u, i));
306 CHECK_VECTOR_EQUALS(t.vp, boost::irange(0u, li));
307 } else {
308 CHECK_VECTOR_EQUALS(t.vp, boost::irange(0u, i));
309 CHECK_VECTOR_EQUALS(t.vt, boost::irange(0u, li));
310 }
311 }
312 CHECK(d.happenings == 0);
313 CHECK(t.d.happenings > 0);
314 }
315
316 SECTION("prepend")
317 {
318 auto make_ = [](auto i, auto delta) {
319 auto d = dadaism::disable();
320 return make_test_flex_vector<dadaist_vector_t>(i, i + delta);
321 };
322 auto t = as_transient_tester(dadaist_vector_t{});
323 auto d = dadaism();
324 auto deltas = magic_rotator();
325 auto delta = deltas.next();
326 for (auto i = n, li = n; i > 0;) {
327 delta = std::min(i, delta);
328 try {
329 if (t.transient) {
330 auto data = make_(i - delta, delta);
331 auto datat = data.transient();
332 t.vt.prepend(datat);
333 } else {
334 auto data = make_(i - delta, delta);
335 t.vp = data + t.vp;
336 }
337 i -= delta;
338 if (t.step()) {
339 li = i;
340 }
341 delta = deltas.next() * 3;
342 } catch (dada_error) {}
343 if (t.transient) {
344 CHECK_VECTOR_EQUALS(t.vt, boost::irange(i, n));
345 CHECK_VECTOR_EQUALS(t.vp, boost::irange(li, n));
346 } else {
347 CHECK_VECTOR_EQUALS(t.vp, boost::irange(i, n));
348 CHECK_VECTOR_EQUALS(t.vt, boost::irange(li, n));
349 }
350 }
351 CHECK(d.happenings == 0);
352 CHECK(t.d.happenings > 0);
353 }
354
355 SECTION("prepend mut")
356 {
357 auto make_ = [](auto i, auto delta) {
358 auto d = dadaism::disable();
359 return make_test_flex_vector<dadaist_vector_t>(i, i + delta);
360 };
361 auto t = as_transient_tester(dadaist_vector_t{});
362 auto d = dadaism();
363 auto deltas = magic_rotator();
364 auto delta = deltas.next();
365 for (auto i = n, li = n; i > 0;) {
366 delta = std::min(i, delta);
367 try {
368 if (t.transient) {
369 auto data = make_(i - delta, delta);
370 auto datat = data.transient();
371 t.vt.prepend(std::move(datat));
372 } else {
373 auto data = make_(i - delta, delta);
374 t.vp = data + t.vp;
375 }
376 i -= delta;
377 if (t.step()) {
378 li = i;
379 }
380 delta = deltas.next() * 3;
381 } catch (dada_error) {}
382 if (t.transient) {
383 CHECK_VECTOR_EQUALS(t.vt, boost::irange(i, n));
384 CHECK_VECTOR_EQUALS(t.vp, boost::irange(li, n));
385 } else {
386 CHECK_VECTOR_EQUALS(t.vp, boost::irange(i, n));
387 CHECK_VECTOR_EQUALS(t.vt, boost::irange(li, n));
388 }
389 }
390 CHECK(d.happenings == 0);
391 CHECK(t.d.happenings > 0);
392 }
393}
394