1 //===----------------------------------------------------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8
9 #ifndef SUPPORT_INSERT_RANGE_SEQUENCE_CONTAINERS_H
10 #define SUPPORT_INSERT_RANGE_SEQUENCE_CONTAINERS_H
11
12 #include <algorithm>
13 #include <cassert>
14 #include <concepts>
15 #include <cstddef>
16 #include <initializer_list>
17 #include <ranges>
18 #include <type_traits>
19 #include <vector>
20
21 #include "../exception_safety_helpers.h"
22 #include "../from_range_helpers.h"
23 #include "../insert_range_helpers.h"
24 #include "MoveOnly.h"
25 #include "almost_satisfies_types.h"
26 #include "count_new.h"
27 #include "min_allocator.h"
28 #include "test_allocator.h"
29 #include "test_iterators.h"
30 #include "test_macros.h"
31 #include "type_algorithms.h"
32
33 template <class Container, class Range>
requires(Container & c,Range && range)34 concept HasInsertRange = requires (Container& c, Range&& range) {
35 c.insert_range(c.end(), range);
36 };
37
38 template <template <class...> class Container, class T, class U>
test_constraints_insert_range()39 constexpr bool test_constraints_insert_range() {
40 // Input range with the same value type.
41 static_assert(HasInsertRange<Container<T>, InputRange<T>>);
42 // Input range with a convertible value type.
43 static_assert(HasInsertRange<Container<T>, InputRange<U>>);
44 // Input range with a non-convertible value type.
45 static_assert(!HasInsertRange<Container<T>, InputRange<Empty>>);
46 // Not an input range.
47 static_assert(!HasInsertRange<Container<T>, InputRangeNotDerivedFrom>);
48 static_assert(!HasInsertRange<Container<T>, InputRangeNotIndirectlyReadable>);
49 static_assert(!HasInsertRange<Container<T>, InputRangeNotInputOrOutputIterator>);
50
51 return true;
52 }
53
54 template <class Container, class Range>
requires(Container & c,Range && range)55 concept HasAppendRange = requires (Container& c, Range&& range) {
56 c.append_range(range);
57 };
58
59 template <template <class...> class Container, class T, class U>
test_constraints_append_range()60 constexpr bool test_constraints_append_range() {
61 // Input range with the same value type.
62 static_assert(HasAppendRange<Container<T>, InputRange<T>>);
63 // Input range with a convertible value type.
64 static_assert(HasAppendRange<Container<T>, InputRange<U>>);
65 // Input range with a non-convertible value type.
66 static_assert(!HasAppendRange<Container<T>, InputRange<Empty>>);
67 // Not an input range.
68 static_assert(!HasAppendRange<Container<T>, InputRangeNotDerivedFrom>);
69 static_assert(!HasAppendRange<Container<T>, InputRangeNotIndirectlyReadable>);
70 static_assert(!HasAppendRange<Container<T>, InputRangeNotInputOrOutputIterator>);
71
72 return true;
73 }
74
75 template <class Container, class Range>
requires(Container & c,Range && range)76 concept HasPrependRange = requires (Container& c, Range&& range) {
77 c.prepend_range(range);
78 };
79
80 template <template <class...> class Container, class T, class U>
test_constraints_prepend_range()81 constexpr bool test_constraints_prepend_range() {
82 // Input range with the same value type.
83 static_assert(HasPrependRange<Container<T>, InputRange<T>>);
84 // Input range with a convertible value type.
85 static_assert(HasPrependRange<Container<T>, InputRange<U>>);
86 // Input range with a non-convertible value type.
87 static_assert(!HasPrependRange<Container<T>, InputRange<Empty>>);
88 // Not an input range.
89 static_assert(!HasPrependRange<Container<T>, InputRangeNotDerivedFrom>);
90 static_assert(!HasPrependRange<Container<T>, InputRangeNotIndirectlyReadable>);
91 static_assert(!HasPrependRange<Container<T>, InputRangeNotInputOrOutputIterator>);
92
93 return true;
94 }
95
96 template <class Container, class Range>
requires(Container & c,Range && range)97 concept HasAssignRange = requires (Container& c, Range&& range) {
98 c.assign_range(range);
99 };
100
101 template <template <class...> class Container, class T, class U>
test_constraints_assign_range()102 constexpr bool test_constraints_assign_range() {
103 // Input range with the same value type.
104 static_assert(HasAssignRange<Container<T>, InputRange<T>>);
105 // Input range with a convertible value type.
106 static_assert(HasAssignRange<Container<T>, InputRange<U>>);
107 // Input range with a non-convertible value type.
108 static_assert(!HasAssignRange<Container<T>, InputRange<Empty>>);
109 // Not an input range.
110 static_assert(!HasAssignRange<Container<T>, InputRangeNotDerivedFrom>);
111 static_assert(!HasAssignRange<Container<T>, InputRangeNotIndirectlyReadable>);
112 static_assert(!HasAssignRange<Container<T>, InputRangeNotInputOrOutputIterator>);
113
114 return true;
115 }
116
117 // Empty container.
118
119 template <class T>
120 TestCase<T> constexpr EmptyContainer_EmptyRange {
121 .initial = {}, .index = 0, .input = {}, .expected = {}
122 };
123 // Note: specializations for `bool` still use `vector<int>` for inputs. This is to avoid dealing with `vector<bool>` and
124 // its iterators over proxy types.
125 template <> constexpr TestCase<int> EmptyContainer_EmptyRange<bool> {
126 .initial = {}, .index = 0, .input = {}, .expected = {}
127 };
128
129 template <class T> constexpr TestCase<T> EmptyContainer_OneElementRange;
130 template <> constexpr TestCase<int> EmptyContainer_OneElementRange<int> {
131 .initial = {}, .index = 0, .input = {5}, .expected = {5}
132 };
133 template <> constexpr TestCase<char> EmptyContainer_OneElementRange<char> {
134 .initial = {}, .index = 0, .input = "a", .expected = "a"
135 };
136 template <> constexpr TestCase<int> EmptyContainer_OneElementRange<bool> {
137 .initial = {}, .index = 0, .input = {true}, .expected = {true}
138 };
139
140 template <class T> constexpr TestCase<T> EmptyContainer_MidRange;
141 template <> constexpr TestCase<int> EmptyContainer_MidRange<int> {
142 .initial = {}, .index = 0, .input = {5, 3, 1, 7, 9}, .expected = {5, 3, 1, 7, 9}
143 };
144 template <> constexpr TestCase<char> EmptyContainer_MidRange<char> {
145 .initial = {}, .index = 0, .input = "aeiou", .expected = "aeiou"
146 };
147 template <> constexpr TestCase<int> EmptyContainer_MidRange<bool> {
148 .initial = {}, .index = 0, .input = {1, 1, 0, 1, 1}, .expected = {1, 1, 0, 1, 1}
149 };
150
151 // One-element container.
152
153 template <class T> constexpr TestCase<T> OneElementContainer_Begin_EmptyRange;
154 template <> constexpr TestCase<int> OneElementContainer_Begin_EmptyRange<int> {
155 .initial = {3}, .index = 0, .input = {}, .expected = {3}
156 };
157 template <> constexpr TestCase<char> OneElementContainer_Begin_EmptyRange<char> {
158 .initial = "B", .index = 0, .input = {}, .expected = "B"
159 };
160 template <> constexpr TestCase<int> OneElementContainer_Begin_EmptyRange<bool> {
161 .initial = {0}, .index = 0, .input = {}, .expected = {0}
162 };
163
164 template <class T> constexpr TestCase<T> OneElementContainer_End_EmptyRange;
165 template <> constexpr TestCase<int> OneElementContainer_End_EmptyRange<int> {
166 .initial = {3}, .index = 1, .input = {}, .expected = {3}
167 };
168 template <> constexpr TestCase<char> OneElementContainer_End_EmptyRange<char> {
169 .initial = "B", .index = 1, .input = {}, .expected = "B"
170 };
171 template <> constexpr TestCase<int> OneElementContainer_End_EmptyRange<bool> {
172 .initial = {0}, .index = 1, .input = {}, .expected = {0}
173 };
174
175 template <class T> constexpr TestCase<T> OneElementContainer_Begin_OneElementRange;
176 template <> constexpr TestCase<int> OneElementContainer_Begin_OneElementRange<int> {
177 .initial = {3}, .index = 0, .input = {-5}, .expected = {-5, 3}
178 };
179 template <> constexpr TestCase<char> OneElementContainer_Begin_OneElementRange<char> {
180 .initial = "B", .index = 0, .input = "a", .expected = "aB"
181 };
182 template <> constexpr TestCase<int> OneElementContainer_Begin_OneElementRange<bool> {
183 .initial = {0}, .index = 0, .input = {1}, .expected = {1, 0}
184 };
185
186 template <class T> constexpr TestCase<T> OneElementContainer_End_OneElementRange;
187 template <> constexpr TestCase<int> OneElementContainer_End_OneElementRange<int> {
188 .initial = {3}, .index = 1, .input = {-5}, .expected = {3, -5}
189 };
190 template <> constexpr TestCase<char> OneElementContainer_End_OneElementRange<char> {
191 .initial = "B", .index = 1, .input = "a", .expected = "Ba"
192 };
193 template <> constexpr TestCase<int> OneElementContainer_End_OneElementRange<bool> {
194 .initial = {0}, .index = 1, .input = {1}, .expected = {0, 1}
195 };
196
197 template <class T> constexpr TestCase<T> OneElementContainer_Begin_MidRange;
198 template <> constexpr TestCase<int> OneElementContainer_Begin_MidRange<int> {
199 .initial = {3}, .index = 0, .input = {-5, -3, -1, -7, -9}, .expected = {-5, -3, -1, -7, -9, 3}
200 };
201 template <> constexpr TestCase<char> OneElementContainer_Begin_MidRange<char> {
202 .initial = "B", .index = 0, .input = "aeiou", .expected = "aeiouB"
203 };
204 template <> constexpr TestCase<int> OneElementContainer_Begin_MidRange<bool> {
205 .initial = {0}, .index = 0, .input = {1, 1, 0, 1, 1}, .expected = {1, 1, 0, 1, 1, 0}
206 };
207
208 template <class T> constexpr TestCase<T> OneElementContainer_End_MidRange;
209 template <> constexpr TestCase<int> OneElementContainer_End_MidRange<int> {
210 .initial = {3}, .index = 1, .input = {-5, -3, -1, -7, -9}, .expected = {3, -5, -3, -1, -7, -9}
211 };
212 template <> constexpr TestCase<char> OneElementContainer_End_MidRange<char> {
213 .initial = "B", .index = 1, .input = "aeiou", .expected = "Baeiou"
214 };
215 template <> constexpr TestCase<int> OneElementContainer_End_MidRange<bool> {
216 .initial = {0}, .index = 1, .input = {1, 1, 0, 1, 1}, .expected = {0, 1, 1, 0, 1, 1}
217 };
218
219 // Full container / empty range.
220
221 template <class T> constexpr TestCase<T> FullContainer_Begin_EmptyRange;
222 template <> constexpr TestCase<int> FullContainer_Begin_EmptyRange<int> {
223 .initial = {11, 29, 35, 14, 84}, .index = 0, .input = {}, .expected = {11, 29, 35, 14, 84}
224 };
225 template <> constexpr TestCase<char> FullContainer_Begin_EmptyRange<char> {
226 .initial = "_BCD_", .index = 0, .input = {}, .expected = "_BCD_"
227 };
228 template <> constexpr TestCase<int> FullContainer_Begin_EmptyRange<bool> {
229 .initial = {0, 0, 1, 0, 0}, .index = 0, .input = {}, .expected = {0, 0, 1, 0, 0}
230 };
231
232 template <class T> constexpr TestCase<T> FullContainer_Mid_EmptyRange;
233 template <> constexpr TestCase<int> FullContainer_Mid_EmptyRange<int> {
234 .initial = {11, 29, 35, 14, 84}, .index = 2, .input = {}, .expected = {11, 29, 35, 14, 84}
235 };
236 template <> constexpr TestCase<char> FullContainer_Mid_EmptyRange<char> {
237 .initial = "_BCD_", .index = 2, .input = {}, .expected = "_BCD_"
238 };
239 template <> constexpr TestCase<int> FullContainer_Mid_EmptyRange<bool> {
240 .initial = {0, 0, 1, 0, 0}, .index = 2, .input = {}, .expected = {0, 0, 1, 0, 0}
241 };
242
243 template <class T> constexpr TestCase<T> FullContainer_End_EmptyRange;
244 template <> constexpr TestCase<int> FullContainer_End_EmptyRange<int> {
245 .initial = {11, 29, 35, 14, 84}, .index = 5, .input = {}, .expected = {11, 29, 35, 14, 84}
246 };
247 template <> constexpr TestCase<char> FullContainer_End_EmptyRange<char> {
248 .initial = "_BCD_", .index = 5, .input = {}, .expected = "_BCD_"
249 };
250 template <> constexpr TestCase<int> FullContainer_End_EmptyRange<bool> {
251 .initial = {0, 0, 1, 0, 0}, .index = 5, .input = {}, .expected = {0, 0, 1, 0, 0}
252 };
253
254 // Full container / one-element range.
255
256 template <class T> constexpr TestCase<T> FullContainer_Begin_OneElementRange;
257 template <> constexpr TestCase<int> FullContainer_Begin_OneElementRange<int> {
258 .initial = {11, 29, 35, 14, 84}, .index = 0, .input = {-5}, .expected = {-5, 11, 29, 35, 14, 84}
259 };
260 template <> constexpr TestCase<char> FullContainer_Begin_OneElementRange<char> {
261 .initial = "_BCD_", .index = 0, .input = "a", .expected = "a_BCD_"
262 };
263 template <> constexpr TestCase<int> FullContainer_Begin_OneElementRange<bool> {
264 .initial = {0, 0, 1, 0, 0}, .index = 0, .input = {1}, .expected = {1, 0, 0, 1, 0, 0}
265 };
266
267 template <class T> constexpr TestCase<T> FullContainer_Mid_OneElementRange;
268 template <> constexpr TestCase<int> FullContainer_Mid_OneElementRange<int> {
269 .initial = {11, 29, 35, 14, 84}, .index = 2, .input = {-5}, .expected = {11, 29, -5, 35, 14, 84}
270 };
271 template <> constexpr TestCase<char> FullContainer_Mid_OneElementRange<char> {
272 .initial = "_BCD_", .index = 2, .input = "a", .expected = "_BaCD_"
273 };
274 template <> constexpr TestCase<int> FullContainer_Mid_OneElementRange<bool> {
275 .initial = {0, 0, 1, 0, 0}, .index = 2, .input = {1}, .expected = {0, 0, 1, 1, 0, 0}
276 };
277
278 template <class T> constexpr TestCase<T> FullContainer_End_OneElementRange;
279 template <> constexpr TestCase<int> FullContainer_End_OneElementRange<int> {
280 .initial = {11, 29, 35, 14, 84}, .index = 5, .input = {-5}, .expected = {11, 29, 35, 14, 84, -5}
281 };
282 template <> constexpr TestCase<char> FullContainer_End_OneElementRange<char> {
283 .initial = "_BCD_", .index = 5, .input = "a", .expected = "_BCD_a"
284 };
285 template <> constexpr TestCase<int> FullContainer_End_OneElementRange<bool> {
286 .initial = {0, 0, 1, 0, 0}, .index = 5, .input = {1}, .expected = {0, 0, 1, 0, 0, 1}
287 };
288
289 // Full container / mid-sized range.
290
291 template <class T> constexpr TestCase<T> FullContainer_Begin_MidRange;
292 template <> constexpr TestCase<int> FullContainer_Begin_MidRange<int> {
293 .initial = {11, 29, 35, 14, 84},
294 .index = 0,
295 .input = {-5, -3, -1, -7, -9},
296 .expected = {-5, -3, -1, -7, -9, 11, 29, 35, 14, 84}
297 };
298 template <> constexpr TestCase<char> FullContainer_Begin_MidRange<char> {
299 .initial = "_BCD_",
300 .index = 0,
301 .input = "aeiou",
302 .expected = "aeiou_BCD_"
303 };
304 template <> constexpr TestCase<int> FullContainer_Begin_MidRange<bool> {
305 .initial = {0, 0, 1, 0, 1},
306 .index = 0,
307 .input = {1, 1, 0, 1, 1},
308 .expected = {1, 1, 0, 1, 1, 0, 0, 1, 0, 1}
309 };
310
311 template <class T> constexpr TestCase<T> FullContainer_Mid_MidRange;
312 template <> constexpr TestCase<int> FullContainer_Mid_MidRange<int> {
313 .initial = {11, 29, 35, 14, 84},
314 .index = 2,
315 .input = {-5, -3, -1, -7, -9},
316 .expected = {11, 29, -5, -3, -1, -7, -9, 35, 14, 84}
317 };
318 template <> constexpr TestCase<char> FullContainer_Mid_MidRange<char> {
319 .initial = "_BCD_",
320 .index = 2,
321 .input = "aeiou",
322 .expected = "_BaeiouCD_"
323 };
324 template <> constexpr TestCase<int> FullContainer_Mid_MidRange<bool> {
325 .initial = {0, 0, 1, 0, 1},
326 .index = 2,
327 .input = {1, 1, 0, 1, 1},
328 .expected = {0, 0, 1, 1, 0, 1, 1, 1, 0, 1}
329 };
330
331 template <class T> constexpr TestCase<T> FullContainer_End_MidRange;
332 template <> constexpr TestCase<int> FullContainer_End_MidRange<int> {
333 .initial = {11, 29, 35, 14, 84},
334 .index = 5,
335 .input = {-5, -3, -1, -7, -9},
336 .expected = {11, 29, 35, 14, 84, -5, -3, -1, -7, -9}
337 };
338 template <> constexpr TestCase<char> FullContainer_End_MidRange<char> {
339 .initial = "_BCD_",
340 .index = 5,
341 .input = "aeiou",
342 .expected = "_BCD_aeiou"
343 };
344 template <> constexpr TestCase<int> FullContainer_End_MidRange<bool> {
345 .initial = {0, 0, 1, 0, 1},
346 .index = 5,
347 .input = {1, 1, 0, 1, 1},
348 .expected = {0, 0, 1, 0, 1, 1, 1, 0, 1, 1}
349 };
350
351 // Full container / long range.
352
353 template <class T> constexpr TestCase<T> FullContainer_Begin_LongRange;
354 template <> constexpr TestCase<int> FullContainer_Begin_LongRange<int> {
355 .initial = {11, 29, 35, 14, 84},
356 .index = 0,
357 .input = {-5, -3, -1, -7, -9, -19, -48, -56, -13, -14, -29, -88, -17, -1, -5, -11, -89, -21, -33, -48},
358 .expected = {
359 -5, -3, -1, -7, -9, -19, -48, -56, -13, -14, -29, -88, -17, -1, -5, -11, -89, -21, -33, -48, 11, 29, 35, 14, 84
360 }
361 };
362 template <> constexpr TestCase<char> FullContainer_Begin_LongRange<char> {
363 .initial = "_BCD_",
364 .index = 0,
365 .input = "aeiouqwxyz5781964203",
366 .expected = "aeiouqwxyz5781964203_BCD_"
367 };
368 template <> constexpr TestCase<int> FullContainer_Begin_LongRange<bool> {
369 .initial = {0, 0, 1, 0, 0},
370 .index = 0,
371 .input = {1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0},
372 .expected = {
373 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0
374 }
375 };
376
377 template <class T> constexpr TestCase<T> FullContainer_Mid_LongRange;
378 template <> constexpr TestCase<int> FullContainer_Mid_LongRange<int> {
379 .initial = {11, 29, 35, 14, 84},
380 .index = 2,
381 .input = {-5, -3, -1, -7, -9, -19, -48, -56, -13, -14, -29, -88, -17, -1, -5, -11, -89, -21, -33, -48},
382 .expected = {
383 11, 29, -5, -3, -1, -7, -9, -19, -48, -56, -13, -14, -29, -88, -17, -1, -5, -11, -89, -21, -33, -48, 35, 14, 84
384 }
385 };
386 template <> constexpr TestCase<char> FullContainer_Mid_LongRange<char> {
387 .initial = "_BCD_",
388 .index = 2,
389 .input = "aeiouqwxyz5781964203",
390 .expected = "_Baeiouqwxyz5781964203CD_"
391 };
392 template <> constexpr TestCase<int> FullContainer_Mid_LongRange<bool> {
393 .initial = {0, 0, 1, 0, 0},
394 .index = 2,
395 .input = {1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0},
396 .expected = {
397 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0
398 }
399 };
400
401 template <class T> constexpr TestCase<T> FullContainer_End_LongRange;
402 template <> constexpr TestCase<int> FullContainer_End_LongRange<int> {
403 .initial = {11, 29, 35, 14, 84},
404 .index = 5,
405 .input = {-5, -3, -1, -7, -9, -19, -48, -56, -13, -14, -29, -88, -17, -1, -5, -11, -89, -21, -33, -48},
406 .expected = {
407 11, 29, 35, 14, 84, -5, -3, -1, -7, -9, -19, -48, -56, -13, -14, -29, -88, -17, -1, -5, -11, -89, -21, -33, -48
408 }
409 };
410 template <> constexpr TestCase<char> FullContainer_End_LongRange<char> {
411 .initial = "_BCD_",
412 .index = 5,
413 .input = "aeiouqwxyz5781964203",
414 .expected = "_BCD_aeiouqwxyz5781964203"
415 };
416 template <> constexpr TestCase<int> FullContainer_End_LongRange<bool> {
417 .initial = {0, 0, 1, 0, 1},
418 .index = 5,
419 .input = {1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0},
420 .expected = {
421 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0
422 }
423 };
424
425 // Sequence containers tests.
426
427 template <class Container, class Iter, class Sent, class Validate>
test_sequence_insert_range(Validate validate)428 constexpr void test_sequence_insert_range(Validate validate) {
429 using T = typename Container::value_type;
430 using D = typename Container::difference_type;
431 auto get_pos = [](auto& c, auto& test_case) { return std::ranges::next(c.begin(), static_cast<D>(test_case.index)); };
432
433 auto test = [&](auto& test_case) {
434 Container c(test_case.initial.begin(), test_case.initial.end());
435 auto in = wrap_input<Iter, Sent>(test_case.input);
436 auto pos = get_pos(c, test_case);
437
438 auto result = c.insert_range(pos, in);
439 assert(result == get_pos(c, test_case));
440 validate(c);
441 return std::ranges::equal(c, test_case.expected);
442 };
443
444 { // Empty container.
445 // empty_c.insert_range(end, empty_range)
446 assert(test(EmptyContainer_EmptyRange<T>));
447 // empty_c.insert_range(end, one_element_range)
448 assert(test(EmptyContainer_OneElementRange<T>));
449 // empty_c.insert_range(end, mid_range)
450 assert(test(EmptyContainer_MidRange<T>));
451 }
452
453 { // One-element container.
454 // one_element_c.insert_range(begin, empty_range)
455 assert(test(OneElementContainer_Begin_EmptyRange<T>));
456 // one_element_c.insert_range(end, empty_range)
457 assert(test(OneElementContainer_End_EmptyRange<T>));
458 // one_element_c.insert_range(begin, one_element_range)
459 assert(test(OneElementContainer_Begin_OneElementRange<T>));
460 // one_element_c.insert_range(end, one_element_range)
461 assert(test(OneElementContainer_End_OneElementRange<T>));
462 // one_element_c.insert_range(begin, mid_range)
463 assert(test(OneElementContainer_Begin_MidRange<T>));
464 // one_element_c.insert_range(end, mid_range)
465 assert(test(OneElementContainer_End_MidRange<T>));
466 }
467
468 { // Full container.
469 // full_container.insert_range(begin, empty_range)
470 assert(test(FullContainer_Begin_EmptyRange<T>));
471 // full_container.insert_range(mid, empty_range)
472 assert(test(FullContainer_Mid_EmptyRange<T>));
473 // full_container.insert_range(end, empty_range)
474 assert(test(FullContainer_End_EmptyRange<T>));
475 // full_container.insert_range(begin, one_element_range)
476 assert(test(FullContainer_Begin_OneElementRange<T>));
477 // full_container.insert_range(end, one_element_range)
478 assert(test(FullContainer_Mid_OneElementRange<T>));
479 // full_container.insert_range(end, one_element_range)
480 assert(test(FullContainer_End_OneElementRange<T>));
481 // full_container.insert_range(begin, mid_range)
482 assert(test(FullContainer_Begin_MidRange<T>));
483 // full_container.insert_range(mid, mid_range)
484 assert(test(FullContainer_Mid_MidRange<T>));
485 // full_container.insert_range(end, mid_range)
486 assert(test(FullContainer_End_MidRange<T>));
487 // full_container.insert_range(begin, long_range)
488 assert(test(FullContainer_Begin_LongRange<T>));
489 // full_container.insert_range(mid, long_range)
490 assert(test(FullContainer_Mid_LongRange<T>));
491 // full_container.insert_range(end, long_range)
492 assert(test(FullContainer_End_LongRange<T>));
493 }
494 }
495
496 template <class Container, class Iter, class Sent, class Validate>
test_sequence_prepend_range(Validate validate)497 constexpr void test_sequence_prepend_range(Validate validate) {
498 using T = typename Container::value_type;
499
500 auto test = [&](auto& test_case) {
501 Container c(test_case.initial.begin(), test_case.initial.end());
502 auto in = wrap_input<Iter, Sent>(test_case.input);
503
504 c.prepend_range(in);
505 validate(c);
506 return std::ranges::equal(c, test_case.expected);
507 };
508
509 { // Empty container.
510 // empty_c.prepend_range(empty_range)
511 assert(test(EmptyContainer_EmptyRange<T>));
512 // empty_c.prepend_range(one_element_range)
513 assert(test(EmptyContainer_OneElementRange<T>));
514 // empty_c.prepend_range(mid_range)
515 assert(test(EmptyContainer_MidRange<T>));
516 }
517
518 { // One-element container.
519 // one_element_c.prepend_range(empty_range)
520 assert(test(OneElementContainer_Begin_EmptyRange<T>));
521 // one_element_c.prepend_range(one_element_range)
522 assert(test(OneElementContainer_Begin_OneElementRange<T>));
523 // one_element_c.prepend_range(mid_range)
524 assert(test(OneElementContainer_Begin_MidRange<T>));
525 }
526
527 { // Full container.
528 // full_container.prepend_range(empty_range)
529 assert(test(FullContainer_Begin_EmptyRange<T>));
530 // full_container.prepend_range(one_element_range)
531 assert(test(FullContainer_Begin_OneElementRange<T>));
532 // full_container.prepend_range(mid_range)
533 assert(test(FullContainer_Begin_MidRange<T>));
534 // full_container.prepend_range(long_range)
535 assert(test(FullContainer_Begin_LongRange<T>));
536 }
537 }
538
539 template <class Container, class Iter, class Sent, class Validate>
test_sequence_append_range(Validate validate)540 constexpr void test_sequence_append_range(Validate validate) {
541 using T = typename Container::value_type;
542
543 auto test = [&](auto& test_case) {
544 Container c(test_case.initial.begin(), test_case.initial.end());
545 auto in = wrap_input<Iter, Sent>(test_case.input);
546
547 c.append_range(in);
548 validate(c);
549 return std::ranges::equal(c, test_case.expected);
550 };
551
552 { // Empty container.
553 // empty_c.append_range(empty_range)
554 assert(test(EmptyContainer_EmptyRange<T>));
555 // empty_c.append_range(one_element_range)
556 assert(test(EmptyContainer_OneElementRange<T>));
557 // empty_c.append_range(mid_range)
558 assert(test(EmptyContainer_MidRange<T>));
559 }
560
561 { // One-element container.
562 // one_element_c.append_range(empty_range)
563 assert(test(OneElementContainer_End_EmptyRange<T>));
564 // one_element_c.append_range(one_element_range)
565 assert(test(OneElementContainer_End_OneElementRange<T>));
566 // one_element_c.append_range(mid_range)
567 assert(test(OneElementContainer_End_MidRange<T>));
568 }
569
570 { // Full container.
571 // full_container.append_range(empty_range)
572 assert(test(FullContainer_End_EmptyRange<T>));
573 // full_container.append_range(one_element_range)
574 assert(test(FullContainer_End_OneElementRange<T>));
575 // full_container.append_range(mid_range)
576 assert(test(FullContainer_End_MidRange<T>));
577 // full_container.append_range(long_range)
578 assert(test(FullContainer_End_LongRange<T>));
579 }
580 }
581
582 template <class Container, class Iter, class Sent, class Validate>
test_sequence_assign_range(Validate validate)583 constexpr void test_sequence_assign_range(Validate validate) {
584 using T = typename Container::value_type;
585
586 auto& initial_empty = EmptyContainer_EmptyRange<T>.initial;
587 auto& initial_one_element = OneElementContainer_Begin_EmptyRange<T>.initial;
588 auto& initial_full = FullContainer_Begin_EmptyRange<T>.initial;
589 auto& input_empty = FullContainer_Begin_EmptyRange<T>.input;
590 auto& input_one_element = FullContainer_Begin_OneElementRange<T>.input;
591 auto& input_mid_range = FullContainer_Begin_MidRange<T>.input;
592 auto& input_long_range = FullContainer_Begin_LongRange<T>.input;
593
594 auto test = [&](auto& initial, auto& input) {
595 Container c(initial.begin(), initial.end());
596 auto in = wrap_input<Iter, Sent>(input);
597
598 c.assign_range(in);
599 validate(c);
600 return std::ranges::equal(c, input);
601 };
602
603 { // Empty container.
604 // empty_container.assign_range(empty_range)
605 assert(test(initial_empty, input_empty));
606 // empty_container.assign_range(one_element_range)
607 assert(test(initial_empty, input_one_element));
608 // empty_container.assign_range(mid_range)
609 assert(test(initial_empty, input_mid_range));
610 // empty_container.assign_range(long_range)
611 assert(test(initial_empty, input_long_range));
612 }
613
614 { // One-element container.
615 // one_element_container.assign_range(empty_range)
616 assert(test(initial_one_element, input_empty));
617 // one_element_container.assign_range(one_element_range)
618 assert(test(initial_one_element, input_one_element));
619 // one_element_container.assign_range(mid_range)
620 assert(test(initial_one_element, input_mid_range));
621 // one_element_container.assign_range(long_range)
622 assert(test(initial_one_element, input_long_range));
623 }
624
625 { // Full container.
626 // full_container.assign_range(empty_range)
627 assert(test(initial_full, input_empty));
628 // full_container.assign_range(one_element_range)
629 assert(test(initial_full, input_one_element));
630 // full_container.assign_range(mid_range)
631 assert(test(initial_full, input_mid_range));
632 // full_container.assign_range(long_range)
633 assert(test(initial_full, input_long_range));
634 }
635 }
636
637 // Move-only types.
638
639 template <template <class ...> class Container>
test_sequence_insert_range_move_only()640 constexpr void test_sequence_insert_range_move_only() {
641 MoveOnly input[5];
642 std::ranges::subrange in(std::move_iterator{input}, std::move_iterator{input + 5});
643
644 Container<MoveOnly> c;
645 c.insert_range(c.end(), in);
646 }
647
648 template <template <class ...> class Container>
test_sequence_prepend_range_move_only()649 constexpr void test_sequence_prepend_range_move_only() {
650 MoveOnly input[5];
651 std::ranges::subrange in(std::move_iterator{input}, std::move_iterator{input + 5});
652
653 Container<MoveOnly> c;
654 c.prepend_range(in);
655 }
656
657 template <template <class ...> class Container>
test_sequence_append_range_move_only()658 constexpr void test_sequence_append_range_move_only() {
659 MoveOnly input[5];
660 std::ranges::subrange in(std::move_iterator{input}, std::move_iterator{input + 5});
661
662 Container<MoveOnly> c;
663 c.append_range(in);
664 }
665
666 template <template <class ...> class Container>
test_sequence_assign_range_move_only()667 constexpr void test_sequence_assign_range_move_only() {
668 MoveOnly input[5];
669 std::ranges::subrange in(std::move_iterator{input}, std::move_iterator{input + 5});
670
671 Container<MoveOnly> c;
672 c.assign_range(in);
673 }
674
675 // Exception safety.
676
677 template <template <class ...> class Container>
test_insert_range_exception_safety_throwing_copy()678 void test_insert_range_exception_safety_throwing_copy() {
679 #if !defined(TEST_HAS_NO_EXCEPTIONS)
680 constexpr int ThrowOn = 3;
681 using T = ThrowingCopy<ThrowOn>;
682 test_exception_safety_throwing_copy<ThrowOn, /*Size=*/5>([](T* from, T* to) {
683 Container<T> c;
684 c.insert_range(c.end(), std::ranges::subrange(from, to));
685 });
686 #endif
687 }
688
689 template <template <class ...> class Container, class T>
test_insert_range_exception_safety_throwing_allocator()690 void test_insert_range_exception_safety_throwing_allocator() {
691 #if !defined(TEST_HAS_NO_EXCEPTIONS)
692 T in[] = {0, 1};
693
694 try {
695 ThrowingAllocator<T> alloc;
696
697 globalMemCounter.reset();
698 Container<T, ThrowingAllocator<T>> c(alloc);
699 c.insert_range(c.end(), in);
700 assert(false); // The function call above should throw.
701
702 } catch (int) {
703 assert(globalMemCounter.new_called == globalMemCounter.delete_called);
704 }
705 #endif
706 }
707
708 template <template <class ...> class Container>
test_prepend_range_exception_safety_throwing_copy()709 void test_prepend_range_exception_safety_throwing_copy() {
710 #if !defined(TEST_HAS_NO_EXCEPTIONS)
711 constexpr int ThrowOn = 3;
712 using T = ThrowingCopy<ThrowOn>;
713 test_exception_safety_throwing_copy<ThrowOn, /*Size=*/5>([](T* from, T* to) {
714 Container<T> c;
715 c.prepend_range(std::ranges::subrange(from, to));
716 });
717 #endif
718 }
719
720 template <template <class ...> class Container, class T>
test_prepend_range_exception_safety_throwing_allocator()721 void test_prepend_range_exception_safety_throwing_allocator() {
722 #if !defined(TEST_HAS_NO_EXCEPTIONS)
723 T in[] = {0, 1};
724
725 try {
726 ThrowingAllocator<T> alloc;
727
728 globalMemCounter.reset();
729 Container<T, ThrowingAllocator<T>> c(alloc);
730 c.prepend_range(in);
731 assert(false); // The function call above should throw.
732
733 } catch (int) {
734 assert(globalMemCounter.new_called == globalMemCounter.delete_called);
735 }
736 #endif
737 }
738
739 template <template <class ...> class Container>
test_append_range_exception_safety_throwing_copy()740 void test_append_range_exception_safety_throwing_copy() {
741 #if !defined(TEST_HAS_NO_EXCEPTIONS)
742 constexpr int ThrowOn = 3;
743 using T = ThrowingCopy<ThrowOn>;
744 test_exception_safety_throwing_copy<ThrowOn, /*Size=*/5>([](T* from, T* to) {
745 Container<T> c;
746 c.append_range(std::ranges::subrange(from, to));
747 });
748 #endif
749 }
750
751 template <template <class ...> class Container, class T>
test_append_range_exception_safety_throwing_allocator()752 void test_append_range_exception_safety_throwing_allocator() {
753 #if !defined(TEST_HAS_NO_EXCEPTIONS)
754 T in[] = {0, 1};
755
756 try {
757 ThrowingAllocator<T> alloc;
758
759 globalMemCounter.reset();
760 Container<T, ThrowingAllocator<T>> c(alloc);
761 c.append_range(in);
762 assert(false); // The function call above should throw.
763
764 } catch (int) {
765 assert(globalMemCounter.new_called == globalMemCounter.delete_called);
766 }
767 #endif
768 }
769
770 template <template <class ...> class Container>
test_assign_range_exception_safety_throwing_copy()771 void test_assign_range_exception_safety_throwing_copy() {
772 #if !defined(TEST_HAS_NO_EXCEPTIONS)
773 constexpr int ThrowOn = 3;
774 using T = ThrowingCopy<ThrowOn>;
775 test_exception_safety_throwing_copy<ThrowOn, /*Size=*/5>([](T* from, T* to) {
776 Container<T> c;
777 c.assign_range(std::ranges::subrange(from, to));
778 });
779 #endif
780 }
781
782 template <template <class ...> class Container, class T>
test_assign_range_exception_safety_throwing_allocator()783 void test_assign_range_exception_safety_throwing_allocator() {
784 #if !defined(TEST_HAS_NO_EXCEPTIONS)
785 T in[] = {0, 1};
786
787 try {
788 ThrowingAllocator<T> alloc;
789
790 globalMemCounter.reset();
791 Container<T, ThrowingAllocator<T>> c(alloc);
792 c.assign_range(in);
793 assert(false); // The function call above should throw.
794
795 } catch (int) {
796 assert(globalMemCounter.new_called == globalMemCounter.delete_called);
797 }
798 #endif
799 }
800
801 #endif // SUPPORT_INSERT_RANGE_SEQUENCE_CONTAINERS_H
802