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_MAPS_SETS_H
10#define SUPPORT_INSERT_RANGE_MAPS_SETS_H
11
12#include <algorithm>
13#include <array>
14#include <cassert>
15#include <concepts>
16#include <ranges>
17#include <type_traits>
18#include <vector>
19
20#include "MoveOnly.h"
21#include "almost_satisfies_types.h"
22#include "count_new.h"
23#include "exception_safety_helpers.h"
24#include "insert_range_helpers.h"
25#include "min_allocator.h"
26#include "test_allocator.h"
27#include "test_compare.h"
28#include "test_hash.h"
29#include "test_iterators.h"
30#include "test_macros.h"
31#include "type_algorithms.h"
32
33template <class Container, class Range>
34concept HasInsertRange = requires (Container& c, Range&& range) {
35 c.insert_range(range);
36};
37
38template <template <class...> class Container, class T, class U>
39constexpr bool test_set_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
54template <template <class...> class Container, class K, class V, class K2, class V2>
55constexpr bool test_map_constraints_insert_range() {
56 using ValueType = std::pair<const K, V>;
57
58 // Input range with the same value type.
59 static_assert(HasInsertRange<Container<K, V>, InputRange<ValueType>>);
60 // Input range with a convertible value type.
61 static_assert(HasInsertRange<Container<K, V>, InputRange<std::pair<const K2, V2>>>);
62 // Input range with a non-convertible value type.
63 static_assert(!HasInsertRange<Container<K, V>, InputRange<std::pair<const K, Empty>>>);
64 static_assert(!HasInsertRange<Container<K, V>, InputRange<std::pair<const Empty, V>>>);
65 // Not an input range.
66 static_assert(!HasInsertRange<Container<K, V>, InputRangeNotDerivedFromGeneric<ValueType>>);
67
68 return true;
69}
70
71template <class T>
72struct TestCaseMapSet {
73 Buffer<T> initial;
74 Buffer<T> input;
75 Buffer<T> expected;
76 Buffer<T> expected_multi;
77};
78
79// Empty container.
80
81template <class T>
82TestCaseMapSet<T> constexpr EmptyContainer_EmptyRange {
83 .initial = {}, .input = {}, .expected = {}
84};
85
86template <class T>
87TestCaseMapSet<T> constexpr EmptyContainer_OneElementRange {
88 .initial = {}, .input = {1}, .expected = {1}
89};
90template <class K, class V> TestCaseMapSet<std::pair<K, V>>
91constexpr EmptyContainer_OneElementRange<std::pair<K, V>> {
92 .initial = {}, .input = {{1, 'a'}}, .expected = {{1, 'a'}}
93};
94
95template <class T>
96TestCaseMapSet<T> constexpr EmptyContainer_RangeNoDuplicates {
97 .initial = {}, .input = {5, 1, 3, 8, 6}, .expected = {5, 1, 3, 8, 6}
98};
99template <class K, class V> TestCaseMapSet<std::pair<K, V>>
100constexpr EmptyContainer_RangeNoDuplicates<std::pair<K, V>> {
101 .initial = {}, .input = {{5, 'a'}, {1, 'e'}, {3, 'i'}, {8, 'o'}, {6, 'u'}},
102 .expected = {{5, 'a'}, {1, 'e'}, {3, 'i'}, {8, 'o'}, {6, 'u'}}
103};
104
105template <class T>
106TestCaseMapSet<T> constexpr EmptyContainer_RangeWithDuplicates {
107 .initial = {},
108 .input = {5, 1, 1, 3, 5, 8, 5, 6, 10},
109 .expected = {5, 1, 3, 8, 6, 10},
110 .expected_multi = {5, 1, 1, 3, 5, 8, 5, 6, 10}
111};
112template <class K, class V> TestCaseMapSet<std::pair<K, V>>
113constexpr EmptyContainer_RangeWithDuplicates<std::pair<K, V>> {
114 .initial = {},
115 .input = {{5, 'a'}, {1, 'a'}, {1, 'b'}, {3, 'a'}, {5, 'b'}, {8, 'a'}, {5, 'c'}, {6, 'a'}, {10, 'b'}},
116 .expected = {{5, 'a'}, {1, 'a'}, {3, 'a'}, {8, 'a'}, {6, 'a'}, {10, 'b'}},
117 .expected_multi = {{5, 'a'}, {1, 'a'}, {1, 'b'}, {3, 'a'}, {5, 'b'}, {8, 'a'}, {5, 'c'}, {6, 'a'}, {10, 'b'}}
118};
119
120// One-element container.
121
122template <class T>
123TestCaseMapSet<T> constexpr OneElementContainer_EmptyRange {
124 .initial = {10}, .input = {}, .expected = {10}
125};
126template <class K, class V> TestCaseMapSet<std::pair<K, V>>
127constexpr OneElementContainer_EmptyRange<std::pair<K, V>> {
128 .initial = {{10, 'A'}}, .input = {}, .expected = {{10, 'A'}}
129};
130
131template <class T>
132TestCaseMapSet<T> constexpr OneElementContainer_OneElementRange {
133 .initial = {10}, .input = {1}, .expected = {1, 10}
134};
135template <class K, class V> TestCaseMapSet<std::pair<K, V>>
136constexpr OneElementContainer_OneElementRange<std::pair<K, V>> {
137 .initial = {{10, 'A'}}, .input = {{1, 'a'}}, .expected = {{1, 'a'}, {10, 'A'}}
138};
139
140template <class T>
141TestCaseMapSet<T> constexpr OneElementContainer_RangeNoDuplicates {
142 .initial = {10}, .input = {5, 1, 3, 8, 6}, .expected = {5, 1, 3, 8, 6, 10}
143};
144template <class K, class V> TestCaseMapSet<std::pair<K, V>>
145constexpr OneElementContainer_RangeNoDuplicates<std::pair<K, V>> {
146 .initial = {{10, 'A'}}, .input = {{5, 'a'}, {1, 'e'}, {3, 'i'}, {8, 'o'}, {6, 'u'}},
147 .expected = {{5, 'a'}, {1, 'e'}, {3, 'i'}, {8, 'o'}, {6, 'u'}, {10, 'A'}}
148};
149
150template <class T>
151TestCaseMapSet<T> constexpr OneElementContainer_RangeWithDuplicates {
152 .initial = {10},
153 .input = {5, 1, 1, 3, 5, 8, 5, 6, 10},
154 .expected = {5, 1, 3, 8, 6, 10},
155 .expected_multi = {5, 1, 1, 3, 5, 8, 5, 6, 10, 10}
156};
157template <class K, class V> TestCaseMapSet<std::pair<K, V>>
158constexpr OneElementContainer_RangeWithDuplicates<std::pair<K, V>> {
159 .initial = {{10, 'A'}},
160 .input = {{5, 'a'}, {1, 'a'}, {1, 'b'}, {3, 'a'}, {5, 'b'}, {8, 'a'}, {5, 'c'}, {6, 'a'}, {10, 'b'}},
161 .expected = {{5, 'a'}, {1, 'a'}, {3, 'a'}, {8, 'a'}, {6, 'a'}, {10, 'A'}},
162 .expected_multi = {
163 {5, 'a'}, {1, 'a'}, {1, 'b'}, {3, 'a'}, {5, 'b'}, {8, 'a'}, {5, 'c'}, {6, 'a'}, {10, 'A'}, {10, 'b'}
164 }
165};
166
167// N-elements container.
168
169template <class T>
170TestCaseMapSet<T> constexpr NElementsContainer_EmptyRange {
171 .initial = {10, 15, 19, 16}, .input = {}, .expected = {10, 15, 19, 16}
172};
173template <class K, class V> TestCaseMapSet<std::pair<K, V>>
174constexpr NElementsContainer_EmptyRange<std::pair<K, V>> {
175 .initial = {{10, 'A'}, {15, 'B'}, {19, 'C'}, {16, 'D'}}, .input = {},
176 .expected = {{10, 'A'}, {15, 'B'}, {19, 'C'}, {16, 'D'}}
177};
178
179template <class T>
180TestCaseMapSet<T> constexpr NElementsContainer_OneElementRange {
181 .initial = {10, 15, 19, 16}, .input = {1}, .expected = {1, 10, 15, 19, 16}
182};
183template <class K, class V> TestCaseMapSet<std::pair<K, V>>
184constexpr NElementsContainer_OneElementRange<std::pair<K, V>> {
185 .initial = {{10, 'A'}, {15, 'B'}, {19, 'C'}, {16, 'D'}}, .input = {{1, 'a'}},
186 .expected = {{1, 'a'}, {10, 'A'}, {15, 'B'}, {19, 'C'}, {16, 'D'}}
187};
188
189template <class T>
190TestCaseMapSet<T> constexpr NElementsContainer_RangeNoDuplicates {
191 .initial = {10, 15, 19, 16}, .input = {5, 1, 3, 8, 6}, .expected = {5, 1, 3, 8, 6, 10, 15, 19, 16}
192};
193template <class K, class V> TestCaseMapSet<std::pair<K, V>>
194constexpr NElementsContainer_RangeNoDuplicates<std::pair<K, V>> {
195 .initial = {{10, 'A'}, {15, 'B'}, {19, 'C'}, {16, 'D'}},
196 .input = {{5, 'a'}, {1, 'e'}, {3, 'i'}, {8, 'o'}, {6, 'u'}},
197 .expected = {{5, 'a'}, {1, 'e'}, {3, 'i'}, {8, 'o'}, {6, 'u'}, {10, 'A'}, {15, 'B'}, {19, 'C'}, {16, 'D'}}
198};
199
200template <class T>
201TestCaseMapSet<T> constexpr NElementsContainer_RangeWithDuplicates {
202 .initial = {10, 15, 19, 16},
203 .input = {5, 1, 1, 3, 5, 8, 5, 6, 10},
204 .expected = {5, 1, 3, 8, 6, 10, 15, 19, 16},
205 .expected_multi = {5, 1, 1, 3, 5, 8, 5, 6, 10, 10, 15, 19, 16}
206};
207template <class K, class V> TestCaseMapSet<std::pair<K, V>>
208constexpr NElementsContainer_RangeWithDuplicates<std::pair<K, V>> {
209 .initial = {{10, 'A'}, {15, 'B'}, {19, 'C'}, {16, 'D'}},
210 .input = {{5, 'a'}, {1, 'a'}, {1, 'b'}, {3, 'a'}, {5, 'b'}, {8, 'a'}, {5, 'c'}, {6, 'a'}, {10, 'b'}},
211 .expected = {{5, 'a'}, {1, 'a'}, {3, 'a'}, {8, 'a'}, {6, 'a'}, {10, 'A'}, {15, 'B'}, {19, 'C'}, {16, 'D'}},
212 .expected_multi = {
213 {5, 'a'}, {1, 'a'}, {1, 'b'}, {3, 'a'}, {5, 'b'}, {8, 'a'}, {5, 'c'}, {6, 'a'}, {10, 'b'},
214 {10, 'A'}, {15, 'B'}, {19, 'C'}, {16, 'D'}
215 }
216};
217
218template <class Container, class T, class Iter, class Sent>
219void test_map_set_insert_range(bool allow_duplicates = false) {
220 auto test = [&](const TestCaseMapSet<T>& test_case, bool check_multi = false) {
221 Container c(test_case.initial.begin(), test_case.initial.end());
222 auto in = wrap_input<Iter, Sent>(test_case.input);
223
224 c.insert_range(in);
225 if (check_multi) {
226 return std::ranges::is_permutation(c, test_case.expected_multi);
227 } else {
228 return std::ranges::is_permutation(c, test_case.expected);
229 }
230 };
231
232 { // Empty container.
233 // empty_c.insert_range(empty_range)
234 assert(test(EmptyContainer_EmptyRange<T>));
235 // empty_c.insert_range(one_element_range)
236 assert(test(EmptyContainer_OneElementRange<T>));
237 // empty_c.insert_range(range_no_duplicates)
238 assert(test(EmptyContainer_RangeNoDuplicates<T>));
239 // empty_c.insert_range(range_with_duplicates)
240 assert(test(EmptyContainer_RangeWithDuplicates<T>, allow_duplicates));
241 }
242
243 { // One-element container.
244 // one_element_c.insert_range(empty_range)
245 assert(test(OneElementContainer_EmptyRange<T>));
246 // one_element_c.insert_range(one_element_range)
247 assert(test(OneElementContainer_OneElementRange<T>));
248 // one_element_c.insert_range(range_no_duplicates)
249 assert(test(OneElementContainer_RangeNoDuplicates<T>));
250 // one_element_c.insert_range(range_with_duplicates)
251 assert(test(OneElementContainer_RangeWithDuplicates<T>, allow_duplicates));
252 }
253
254 { // N-elements container.
255 // n_elements_c.insert_range(empty_range)
256 assert(test(NElementsContainer_EmptyRange<T>));
257 // n_elements_c.insert_range(one_element_range)
258 assert(test(NElementsContainer_OneElementRange<T>));
259 // n_elements_c.insert_range(range_no_duplicates)
260 assert(test(NElementsContainer_RangeNoDuplicates<T>));
261 // n_elements_c.insert_range(range_with_duplicates)
262 assert(test(NElementsContainer_RangeWithDuplicates<T>, allow_duplicates));
263 }
264}
265
266// Move-only types.
267
268template <template <class ...> class Container>
269void test_set_insert_range_move_only() {
270 MoveOnly input[5];
271 std::ranges::subrange in(std::move_iterator{input}, std::move_iterator{input + 5});
272
273 Container<MoveOnly> c;
274 c.insert_range(in);
275}
276
277template <template <class ...> class Container>
278void test_map_insert_range_move_only() {
279 using Value = std::pair<const int, MoveOnly>;
280 Value input[5];
281 std::ranges::subrange in(std::move_iterator{input}, std::move_iterator{input + 5});
282
283 Container<int, MoveOnly> c;
284 c.insert_range(in);
285}
286
287// Exception safety.
288
289template <template <class ...> class Container>
290void test_set_insert_range_exception_safety_throwing_copy() {
291#if !defined(TEST_HAS_NO_EXCEPTIONS)
292 using T = ThrowingCopy<3>;
293 T::reset();
294 T in[5] = {{1}, {2}, {3}, {4}, {5}};
295
296 try {
297 Container<T> c;
298 c.insert_range(in);
299 assert(false); // The constructor call above should throw.
300
301 } catch (int) {
302 assert(T::created_by_copying == 3);
303 assert(T::destroyed == 2); // No destructor call for the partially-constructed element.
304 }
305#endif
306}
307
308template <template <class ...> class Container>
309void test_map_insert_range_exception_safety_throwing_copy() {
310#if !defined(TEST_HAS_NO_EXCEPTIONS)
311 using K = int;
312 using V = ThrowingCopy<3>;
313
314 V::throwing_enabled = false;
315 std::pair<const K, V> in[5] = {
316 {1, {}}, {2, {}}, {3, {}}, {4, {}}, {5, {}}
317 };
318 V::throwing_enabled = true;
319 V::reset();
320
321 try {
322 Container<K, V> c;
323 c.insert_range(in);
324 assert(false); // The function call above should throw.
325
326 } catch (int) {
327 assert(V::created_by_copying == 3);
328 assert(V::destroyed == 2); // No destructor call for the partially-constructed element.
329 }
330#endif
331}
332
333template <template <class ...> class Container, class T>
334void test_assoc_set_insert_range_exception_safety_throwing_allocator() {
335#if !defined(TEST_HAS_NO_EXCEPTIONS)
336 T in[] = {1, 2};
337
338 try {
339 ThrowingAllocator<T> alloc;
340
341 globalMemCounter.reset();
342 Container<T, test_less<T>, ThrowingAllocator<T>> c(alloc);
343 c.insert_range(in);
344 assert(false); // The function call above should throw.
345
346 } catch (int) {
347 assert(globalMemCounter.new_called == globalMemCounter.delete_called);
348 }
349#endif
350}
351
352template <template <class ...> class Container, class T>
353void test_unord_set_insert_range_exception_safety_throwing_allocator() {
354#if !defined(TEST_HAS_NO_EXCEPTIONS)
355 T in[] = {1, 2};
356
357 try {
358 ThrowingAllocator<T> alloc;
359
360 globalMemCounter.reset();
361 Container<T, test_hash<T>, test_equal_to<T>, ThrowingAllocator<T>> c(alloc);
362 c.insert_range(in);
363 assert(false); // The function call above should throw.
364
365 } catch (int) {
366 assert(globalMemCounter.new_called == globalMemCounter.delete_called);
367 }
368#endif
369}
370
371template <template <class ...> class Container, class K, class V>
372void test_assoc_map_insert_range_exception_safety_throwing_allocator() {
373#if !defined(TEST_HAS_NO_EXCEPTIONS)
374 using ValueType = std::pair<const K, V>;
375 ValueType in[] = {
376 ValueType{K{1}, V{1}}
377 };
378
379 try {
380 ThrowingAllocator<ValueType> alloc;
381
382 globalMemCounter.reset();
383 Container<K, V, test_less<K>, ThrowingAllocator<ValueType>> c(alloc);
384 c.insert_range(in);
385 assert(false); // The function call above should throw.
386
387 } catch (int) {
388 assert(globalMemCounter.new_called == globalMemCounter.delete_called);
389 }
390#endif
391}
392
393template <template <class ...> class Container, class K, class V>
394void test_unord_map_insert_range_exception_safety_throwing_allocator() {
395#if !defined(TEST_HAS_NO_EXCEPTIONS)
396 using ValueType = std::pair<const K, V>;
397 ValueType in[] = {
398 ValueType{K{1}, V{1}}
399 };
400
401 try {
402 ThrowingAllocator<ValueType> alloc;
403
404 globalMemCounter.reset();
405 Container<K, V, test_hash<K>, test_equal_to<K>, ThrowingAllocator<ValueType>> c(alloc);
406 c.insert_range(in);
407 assert(false); // The function call above should throw.
408
409 } catch (int) {
410 assert(globalMemCounter.new_called == globalMemCounter.delete_called);
411 }
412#endif
413}
414
415#endif // SUPPORT_INSERT_RANGE_MAPS_SETS_H
416

source code of libcxx/test/std/containers/insert_range_maps_sets.h