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

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