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 | |
36 | template <typename V=VECTOR_T<unsigned>> |
37 | auto 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 | |
45 | template <typename V=FLEX_VECTOR_T<unsigned>> |
46 | auto 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 | |
54 | TEST_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 | |
65 | TEST_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 | |
76 | TEST_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 | |
105 | TEST_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 | |