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

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