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_PUSH_RANGE_CONTAINER_ADAPTORS_H
10#define SUPPORT_PUSH_RANGE_CONTAINER_ADAPTORS_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#include "unwrap_container_adaptor.h"
33
34template <class Container, class Range>
35concept HasPushRange = requires (Container& c, Range&& range) {
36 c.push_range(range);
37};
38
39template <template <class...> class Container, class T, class U>
40constexpr bool test_constraints_push_range() {
41 // Input range with the same value type.
42 static_assert(HasPushRange<Container<T>, InputRange<T>>);
43 // Input range with a convertible value type.
44 static_assert(HasPushRange<Container<T>, InputRange<U>>);
45 // Input range with a non-convertible value type.
46 static_assert(!HasPushRange<Container<T>, InputRange<Empty>>);
47 // Not an input range.
48 static_assert(!HasPushRange<Container<T>, InputRangeNotDerivedFrom>);
49 static_assert(!HasPushRange<Container<T>, InputRangeNotIndirectlyReadable>);
50 static_assert(!HasPushRange<Container<T>, InputRangeNotInputOrOutputIterator>);
51
52 return true;
53}
54
55// Empty container.
56
57template <class T>
58TestCase<T> constexpr EmptyContainer_EmptyRange {
59 .initial = {}, .input = {}, .expected = {}
60};
61
62template <class T> constexpr TestCase<T> EmptyContainer_OneElementRange {
63 .initial = {}, .input = {5}, .expected = {5}
64};
65
66template <class T> constexpr TestCase<T> EmptyContainer_MidRange {
67 .initial = {}, .input = {5, 3, 1, 7, 9}, .expected = {5, 3, 1, 7, 9}
68};
69
70// One-element container.
71
72template <class T> constexpr TestCase<T> OneElementContainer_EmptyRange {
73 .initial = {3}, .input = {}, .expected = {3}
74};
75
76template <class T> constexpr TestCase<T> OneElementContainer_OneElementRange {
77 .initial = {3}, .input = {-5}, .expected = {3, -5}
78};
79
80template <class T> constexpr TestCase<T> OneElementContainer_MidRange {
81 .initial = {3}, .input = {-5, -3, -1, -7, -9}, .expected = {3, -5, -3, -1, -7, -9}
82};
83
84// Full container.
85
86template <class T> constexpr TestCase<T> FullContainer_EmptyRange {
87 .initial = {11, 29, 35, 14, 84}, .input = {}, .expected = {11, 29, 35, 14, 84}
88};
89
90template <class T> constexpr TestCase<T> FullContainer_OneElementRange {
91 .initial = {11, 29, 35, 14, 84}, .input = {-5}, .expected = {11, 29, 35, 14, 84, -5}
92};
93
94template <class T> constexpr TestCase<T> FullContainer_MidRange {
95 .initial = {11, 29, 35, 14, 84},
96 .input = {-5, -3, -1, -7, -9},
97 .expected = {11, 29, 35, 14, 84, -5, -3, -1, -7, -9}
98};
99
100template <class T> constexpr TestCase<T> FullContainer_LongRange {
101 .initial = {11, 29, 35, 14, 84},
102 .input = {-5, -3, -1, -7, -9, -19, -48, -56, -13, -14, -29, -88, -17, -1, -5, -11, -89, -21, -33, -48},
103 .expected = {
104 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
105 }
106};
107
108// Container adaptors tests.
109
110template <class Adaptor, class Iter, class Sent>
111constexpr void test_push_range(bool is_result_heapified = false) {
112 using T = typename Adaptor::value_type;
113
114 auto test = [&](auto& test_case) {
115 Adaptor adaptor(test_case.initial.begin(), test_case.initial.end());
116 auto in = wrap_input<Iter, Sent>(test_case.input);
117
118 adaptor.push_range(in);
119 UnwrapAdaptor<Adaptor> unwrap_adaptor(std::move(adaptor));
120 auto& c = unwrap_adaptor.get_container();
121
122 if (is_result_heapified) {
123 assert(std::ranges::is_heap(c));
124 return std::ranges::is_permutation(c, test_case.expected);
125 } else {
126 return std::ranges::equal(c, test_case.expected);
127 }
128 };
129
130 { // Empty container.
131 // empty_c.push_range(empty_range)
132 assert(test(EmptyContainer_EmptyRange<T>));
133 // empty_c.push_range(one_element_range)
134 assert(test(EmptyContainer_OneElementRange<T>));
135 // empty_c.push_range(mid_range)
136 assert(test(EmptyContainer_MidRange<T>));
137 }
138
139 { // One-element container.
140 // one_element_c.push_range(empty_range)
141 assert(test(OneElementContainer_EmptyRange<T>));
142 // one_element_c.push_range(one_element_range)
143 assert(test(OneElementContainer_OneElementRange<T>));
144 // one_element_c.push_range(mid_range)
145 assert(test(OneElementContainer_MidRange<T>));
146 }
147
148 { // Full container.
149 // full_container.push_range(empty_range)
150 assert(test(FullContainer_EmptyRange<T>));
151 // full_container.push_range(one_element_range)
152 assert(test(FullContainer_OneElementRange<T>));
153 // full_container.push_range(mid_range)
154 assert(test(FullContainer_MidRange<T>));
155 // full_container.push_range(long_range)
156 assert(test(FullContainer_LongRange<T>));
157 }
158}
159
160// Move-only types.
161
162template <template <class ...> class Container>
163constexpr void test_push_range_move_only() {
164 MoveOnly input[5];
165 std::ranges::subrange in(std::move_iterator{input}, std::move_iterator{input + 5});
166
167 Container<MoveOnly> c;
168 c.push_range(in);
169}
170
171// Check that `append_range` is preferred if available and `push_back` is used as a fallback.
172
173enum class InserterChoice {
174 Invalid,
175 PushBack,
176 AppendRange
177};
178
179template <class T, InserterChoice Inserter>
180struct Container {
181 InserterChoice inserter_choice = InserterChoice::Invalid;
182
183 using value_type = T;
184 using iterator = T*;
185 using reference = T&;
186 using const_reference = const T&;
187 using size_type = std::size_t;
188
189 static constexpr int Capacity = 8;
190 int size_ = 0;
191 value_type buffer_[Capacity] = {};
192
193 iterator begin() { return buffer_; }
194 iterator end() { return buffer_ + size_; }
195 size_type size() const { return size_; }
196
197 template <class U>
198 void push_back(U val)
199 requires (Inserter >= InserterChoice::PushBack) {
200 inserter_choice = InserterChoice::PushBack;
201 buffer_[size_] = val;
202 ++size_;
203 }
204
205 template <std::ranges::input_range Range>
206 void append_range(Range&& range)
207 requires (Inserter >= InserterChoice::AppendRange) {
208 assert(size() + std::ranges::distance(range) <= Capacity);
209
210 inserter_choice = InserterChoice::AppendRange;
211
212 for (auto&& e : range) {
213 buffer_[size_] = e;
214 ++size_;
215 }
216 }
217
218 friend bool operator==(const Container&, const Container&) = default;
219};
220
221template <template <class ...> class AdaptorT, class T>
222void test_push_range_inserter_choice(bool is_result_heapified = false) {
223 { // `append_range` is preferred if available.
224 using BaseContainer = Container<T, InserterChoice::AppendRange>;
225 using Adaptor = AdaptorT<T, BaseContainer>;
226 T in[] = {1, 2, 3, 4, 5};
227
228 Adaptor adaptor;
229 adaptor.push_range(in);
230
231 UnwrapAdaptor<Adaptor> unwrap_adaptor(std::move(adaptor));
232 auto& c = unwrap_adaptor.get_container();
233 assert(c.inserter_choice == InserterChoice::AppendRange);
234 if (is_result_heapified) {
235 assert(std::ranges::is_heap(c));
236 assert(std::ranges::is_permutation(c, in));
237 } else {
238 assert(std::ranges::equal(c, in));
239 }
240 }
241
242 { // `push_back` is used as a fallback (via `back_inserter`).
243 using BaseContainer = Container<T, InserterChoice::PushBack>;
244 using Adaptor = AdaptorT<T, BaseContainer>;
245 T in[] = {1, 2, 3, 4, 5};
246
247 Adaptor adaptor;
248 adaptor.push_range(in);
249
250 UnwrapAdaptor<Adaptor> unwrap_adaptor(std::move(adaptor));
251 auto& c = unwrap_adaptor.get_container();
252 assert(c.inserter_choice == InserterChoice::PushBack);
253 if (is_result_heapified) {
254 assert(std::ranges::is_heap(c));
255 assert(std::ranges::is_permutation(c, in));
256 } else {
257 assert(std::ranges::equal(c, in));
258 }
259 }
260}
261
262// Exception safety.
263
264template <template <class ...> class Container>
265void test_push_range_exception_safety_throwing_copy() {
266#if !defined(TEST_HAS_NO_EXCEPTIONS)
267 constexpr int ThrowOn = 3;
268 using T = ThrowingCopy<ThrowOn>;
269 test_exception_safety_throwing_copy<ThrowOn, /*Size=*/5>([](auto* from, auto* to) {
270 Container<T> c;
271 c.push_range(std::ranges::subrange(from, to));
272 });
273#endif
274}
275
276template <template <class ...> class Adaptor, template <class ...> class BaseContainer, class T>
277void test_push_range_exception_safety_throwing_allocator() {
278#if !defined(TEST_HAS_NO_EXCEPTIONS)
279 T in[] = {0, 1};
280
281 try {
282 globalMemCounter.reset();
283 Adaptor<T, BaseContainer<T, ThrowingAllocator<T>>> c;
284 c.push_range(in);
285 assert(false); // The function call above should throw.
286
287 } catch (int) {
288 assert(globalMemCounter.new_called == globalMemCounter.delete_called);
289 }
290#endif
291}
292
293#endif // SUPPORT_PUSH_RANGE_CONTAINER_ADAPTORS_H
294

source code of libcxx/test/std/containers/container.adaptors/push_range_container_adaptors.h