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
34 template <class Container, class Range>
requires(Container & c,Range && range)35 concept HasPushRange = requires (Container& c, Range&& range) {
36 c.push_range(range);
37 };
38
39 template <template <class...> class Container, class T, class U>
test_constraints_push_range()40 constexpr 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
57 template <class T>
58 TestCase<T> constexpr EmptyContainer_EmptyRange {
59 .initial = {}, .input = {}, .expected = {}
60 };
61
62 template <class T> constexpr TestCase<T> EmptyContainer_OneElementRange {
63 .initial = {}, .input = {5}, .expected = {5}
64 };
65
66 template <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
72 template <class T> constexpr TestCase<T> OneElementContainer_EmptyRange {
73 .initial = {3}, .input = {}, .expected = {3}
74 };
75
76 template <class T> constexpr TestCase<T> OneElementContainer_OneElementRange {
77 .initial = {3}, .input = {-5}, .expected = {3, -5}
78 };
79
80 template <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
86 template <class T> constexpr TestCase<T> FullContainer_EmptyRange {
87 .initial = {11, 29, 35, 14, 84}, .input = {}, .expected = {11, 29, 35, 14, 84}
88 };
89
90 template <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
94 template <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
100 template <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
110 template <class Adaptor, class Iter, class Sent>
111 constexpr 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
162 template <template <class ...> class Container>
test_push_range_move_only()163 constexpr 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
173 enum class InserterChoice {
174 Invalid,
175 PushBack,
176 AppendRange
177 };
178
179 template <class T, InserterChoice Inserter>
180 struct 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
beginContainer193 iterator begin() { return buffer_; }
endContainer194 iterator end() { return buffer_ + size_; }
sizeContainer195 size_type size() const { return size_; }
196
197 template <class U>
push_backContainer198 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>
append_rangeContainer206 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
221 template <template <class ...> class AdaptorT, class T>
222 void 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
264 template <template <class ...> class Container>
test_push_range_exception_safety_throwing_copy()265 void 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
276 template <template <class ...> class Adaptor, template <class ...> class BaseContainer, class T>
test_push_range_exception_safety_throwing_allocator()277 void 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