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
33 template <class Container, class Range>
requires(Container & c,Range && range)34 concept HasInsertRange = requires (Container& c, Range&& range) {
35 c.insert_range(range);
36 };
37
38 template <template <class...> class Container, class T, class U>
test_set_constraints_insert_range()39 constexpr 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
54 template <template <class...> class Container, class K, class V, class K2, class V2>
test_map_constraints_insert_range()55 constexpr 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
71 template <class T>
72 struct TestCaseMapSet {
73 Buffer<T> initial;
74 Buffer<T> input;
75 Buffer<T> expected;
76 Buffer<T> expected_multi;
77 };
78
79 // Empty container.
80
81 template <class T>
82 TestCaseMapSet<T> constexpr EmptyContainer_EmptyRange {
83 .initial = {}, .input = {}, .expected = {}
84 };
85
86 template <class T>
87 TestCaseMapSet<T> constexpr EmptyContainer_OneElementRange {
88 .initial = {}, .input = {1}, .expected = {1}
89 };
90 template <class K, class V> TestCaseMapSet<std::pair<K, V>>
91 constexpr EmptyContainer_OneElementRange<std::pair<K, V>> {
92 .initial = {}, .input = {{1, 'a'}}, .expected = {{1, 'a'}}
93 };
94
95 template <class T>
96 TestCaseMapSet<T> constexpr EmptyContainer_RangeNoDuplicates {
97 .initial = {}, .input = {5, 1, 3, 8, 6}, .expected = {5, 1, 3, 8, 6}
98 };
99 template <class K, class V> TestCaseMapSet<std::pair<K, V>>
100 constexpr 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
105 template <class T>
106 TestCaseMapSet<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 };
112 template <class K, class V> TestCaseMapSet<std::pair<K, V>>
113 constexpr 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
122 template <class T>
123 TestCaseMapSet<T> constexpr OneElementContainer_EmptyRange {
124 .initial = {10}, .input = {}, .expected = {10}
125 };
126 template <class K, class V> TestCaseMapSet<std::pair<K, V>>
127 constexpr OneElementContainer_EmptyRange<std::pair<K, V>> {
128 .initial = {{10, 'A'}}, .input = {}, .expected = {{10, 'A'}}
129 };
130
131 template <class T>
132 TestCaseMapSet<T> constexpr OneElementContainer_OneElementRange {
133 .initial = {10}, .input = {1}, .expected = {1, 10}
134 };
135 template <class K, class V> TestCaseMapSet<std::pair<K, V>>
136 constexpr OneElementContainer_OneElementRange<std::pair<K, V>> {
137 .initial = {{10, 'A'}}, .input = {{1, 'a'}}, .expected = {{1, 'a'}, {10, 'A'}}
138 };
139
140 template <class T>
141 TestCaseMapSet<T> constexpr OneElementContainer_RangeNoDuplicates {
142 .initial = {10}, .input = {5, 1, 3, 8, 6}, .expected = {5, 1, 3, 8, 6, 10}
143 };
144 template <class K, class V> TestCaseMapSet<std::pair<K, V>>
145 constexpr 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
150 template <class T>
151 TestCaseMapSet<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 };
157 template <class K, class V> TestCaseMapSet<std::pair<K, V>>
158 constexpr 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
169 template <class T>
170 TestCaseMapSet<T> constexpr NElementsContainer_EmptyRange {
171 .initial = {10, 15, 19, 16}, .input = {}, .expected = {10, 15, 19, 16}
172 };
173 template <class K, class V> TestCaseMapSet<std::pair<K, V>>
174 constexpr 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
179 template <class T>
180 TestCaseMapSet<T> constexpr NElementsContainer_OneElementRange {
181 .initial = {10, 15, 19, 16}, .input = {1}, .expected = {1, 10, 15, 19, 16}
182 };
183 template <class K, class V> TestCaseMapSet<std::pair<K, V>>
184 constexpr 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
189 template <class T>
190 TestCaseMapSet<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 };
193 template <class K, class V> TestCaseMapSet<std::pair<K, V>>
194 constexpr 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
200 template <class T>
201 TestCaseMapSet<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 };
207 template <class K, class V> TestCaseMapSet<std::pair<K, V>>
208 constexpr 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
218 template <class Container, class T, class Iter, class Sent>
219 void 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
268 template <template <class ...> class Container>
test_set_insert_range_move_only()269 void 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
277 template <template <class ...> class Container>
test_map_insert_range_move_only()278 void 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
289 template <template <class ...> class Container>
test_set_insert_range_exception_safety_throwing_copy()290 void 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
308 template <template <class ...> class Container>
test_map_insert_range_exception_safety_throwing_copy()309 void 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
333 template <template <class ...> class Container, class T>
test_assoc_set_insert_range_exception_safety_throwing_allocator()334 void 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
352 template <template <class ...> class Container, class T>
test_unord_set_insert_range_exception_safety_throwing_allocator()353 void 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
371 template <template <class ...> class Container, class K, class V>
test_assoc_map_insert_range_exception_safety_throwing_allocator()372 void 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
393 template <template <class ...> class Container, class K, class V>
test_unord_map_insert_range_exception_safety_throwing_allocator()394 void 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