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// <algorithm>
10
11// UNSUPPORTED: c++03, c++11, c++14, c++17
12// UNSUPPORTED: GCC-ALWAYS_INLINE-FIXME
13
14// template<bidirectional_iterator I1, sentinel_for<I1> S1, bidirectional_iterator I2>
15// requires indirectly_copyable<I1, I2>
16// constexpr ranges::copy_backward_result<I1, I2>
17// ranges::copy_backward(I1 first, S1 last, I2 result);
18// template<bidirectional_range R, bidirectional_iterator I>
19// requires indirectly_copyable<iterator_t<R>, I>
20// constexpr ranges::copy_backward_result<borrowed_iterator_t<R>, I>
21// ranges::copy_backward(R&& r, I result);
22
23#include <algorithm>
24#include <array>
25#include <cassert>
26#include <deque>
27#include <ranges>
28#include <vector>
29
30#include "almost_satisfies_types.h"
31#include "sized_allocator.h"
32#include "test_iterators.h"
33#include "test_macros.h"
34
35template <class In, class Out = In, class Sent = sentinel_wrapper<In>>
36concept HasCopyBackwardIt = requires(In in, Sent sent, Out out) { std::ranges::copy_backward(in, sent, out); };
37
38static_assert(HasCopyBackwardIt<int*>);
39static_assert(!HasCopyBackwardIt<InputIteratorNotDerivedFrom>);
40static_assert(!HasCopyBackwardIt<InputIteratorNotIndirectlyReadable>);
41static_assert(!HasCopyBackwardIt<InputIteratorNotInputOrOutputIterator>);
42static_assert(!HasCopyBackwardIt<int*, WeaklyIncrementableNotMovable>);
43struct NotIndirectlyCopyable {};
44static_assert(!HasCopyBackwardIt<int*, NotIndirectlyCopyable*>);
45static_assert(!HasCopyBackwardIt<int*, int*, SentinelForNotSemiregular>);
46static_assert(!HasCopyBackwardIt<int*, int*, SentinelForNotWeaklyEqualityComparableWith>);
47
48template <class Range, class Out>
49concept HasCopyBackwardR = requires(Range range, Out out) { std::ranges::copy_backward(range, out); };
50
51static_assert(HasCopyBackwardR<std::array<int, 10>, int*>);
52static_assert(!HasCopyBackwardR<InputRangeNotDerivedFrom, int*>);
53static_assert(!HasCopyBackwardR<InputRangeNotIndirectlyReadable, int*>);
54static_assert(!HasCopyBackwardR<InputRangeNotInputOrOutputIterator, int*>);
55static_assert(!HasCopyBackwardR<WeaklyIncrementableNotMovable, int*>);
56static_assert(!HasCopyBackwardR<UncheckedRange<NotIndirectlyCopyable*>, int*>);
57static_assert(!HasCopyBackwardR<InputRangeNotSentinelSemiregular, int*>);
58static_assert(!HasCopyBackwardR<InputRangeNotSentinelEqualityComparableWith, int*>);
59
60static_assert(std::is_same_v<std::ranges::copy_result<int, long>, std::ranges::in_out_result<int, long>>);
61
62template <class In, class Out, class Sent>
63constexpr void test_iterators() {
64 { // simple test
65 {
66 std::array in{1, 2, 3, 4};
67 std::array<int, 4> out;
68 std::same_as<std::ranges::in_out_result<In, Out>> auto ret =
69 std::ranges::copy_backward(In(in.data()), Sent(In(in.data() + in.size())), Out(out.data() + out.size()));
70 assert(in == out);
71 assert(base(ret.in) == in.data() + in.size());
72 assert(base(ret.out) == out.data());
73 }
74 {
75 std::array in{1, 2, 3, 4};
76 std::array<int, 4> out;
77 auto range = std::ranges::subrange(In(in.data()), Sent(In(in.data() + in.size())));
78 std::same_as<std::ranges::in_out_result<In, Out>> auto ret =
79 std::ranges::copy_backward(range, Out(out.data() + out.size()));
80 assert(in == out);
81 assert(base(ret.in) == in.data() + in.size());
82 assert(base(ret.out) == out.data());
83 }
84 }
85
86 { // check that an empty range works
87 {
88 std::array<int, 0> in;
89 std::array<int, 0> out;
90 auto ret =
91 std::ranges::copy_backward(In(in.data()), Sent(In(in.data() + in.size())), Out(out.data() + out.size()));
92 assert(base(ret.in) == in.data() + in.size());
93 assert(base(ret.out) == out.data());
94 }
95 {
96 std::array<int, 0> in;
97 std::array<int, 0> out;
98 auto range = std::ranges::subrange(In(in.data()), Sent(In(in.data() + in.size())));
99 auto ret = std::ranges::copy_backward(range, Out(out.data()));
100 assert(base(ret.in) == in.data() + in.size());
101 assert(base(ret.out) == out.data());
102 }
103 }
104}
105
106template <class InContainer, class OutContainer, class In, class Out, class Sent = In>
107constexpr void test_containers() {
108 {
109 InContainer in{1, 2, 3, 4};
110 OutContainer out(4);
111 std::same_as<std::ranges::in_out_result<In, Out>> auto ret =
112 std::ranges::copy_backward(In(in.begin()), Sent(In(in.end())), Out(out.end()));
113 assert(std::ranges::equal(in, out));
114 assert(base(ret.in) == in.end());
115 assert(base(ret.out) == out.begin());
116 }
117 {
118 InContainer in{1, 2, 3, 4};
119 OutContainer out(4);
120 auto range = std::ranges::subrange(In(in.begin()), Sent(In(in.end())));
121 std::same_as<std::ranges::in_out_result<In, Out>> auto ret = std::ranges::copy_backward(range, Out(out.end()));
122 assert(std::ranges::equal(in, out));
123 assert(base(ret.in) == in.end());
124 assert(base(ret.out) == out.begin());
125 }
126}
127
128template <class Iter, class Sent>
129constexpr void test_join_view() {
130 auto to_subranges =
131 std::views::transform([](auto& vec) { return std::ranges::subrange(Iter(vec.begin()), Sent(Iter(vec.end()))); });
132
133 { // segmented -> contiguous
134 std::vector<std::vector<int>> vectors = {};
135 auto range = vectors | to_subranges;
136 std::vector<std::ranges::subrange<Iter, Sent>> subrange_vector(range.begin(), range.end());
137 std::array<int, 0> arr;
138
139 std::ranges::copy_backward(subrange_vector | std::views::join, arr.end());
140 assert(std::ranges::equal(arr, std::array<int, 0>{}));
141 }
142 { // segmented -> contiguous
143 std::vector<std::vector<int>> vectors = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10}, {}};
144 auto range = vectors | to_subranges;
145 std::vector<std::ranges::subrange<Iter, Sent>> subrange_vector(range.begin(), range.end());
146 std::array<int, 10> arr;
147
148 std::ranges::copy_backward(subrange_vector | std::views::join, arr.end());
149 assert(std::ranges::equal(arr, std::array{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}));
150 }
151 { // contiguous -> segmented
152 std::vector<std::vector<int>> vectors = {{0, 0, 0, 0}, {0, 0}, {0, 0, 0, 0}, {}};
153 auto range = vectors | to_subranges;
154 std::vector<std::ranges::subrange<Iter, Sent>> subrange_vector(range.begin(), range.end());
155 std::array arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
156
157 std::ranges::copy_backward(arr, (subrange_vector | std::views::join).end());
158 assert(std::ranges::equal(subrange_vector | std::views::join, std::array{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}));
159 }
160 { // segmented -> segmented
161 std::vector<std::vector<int>> vectors = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10}, {}};
162 auto range1 = vectors | to_subranges;
163 std::vector<std::ranges::subrange<Iter, Sent>> subrange_vector(range1.begin(), range1.end());
164 std::vector<std::vector<int>> to_vectors = {{0, 0, 0, 0}, {0, 0, 0, 0}, {}, {0, 0}};
165 auto range2 = to_vectors | to_subranges;
166 std::vector<std::ranges::subrange<Iter, Sent>> to_subrange_vector(range2.begin(), range2.end());
167
168 std::ranges::copy_backward(subrange_vector | std::views::join, (to_subrange_vector | std::views::join).end());
169 assert(std::ranges::equal(to_subrange_vector | std::views::join, std::array{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}));
170 }
171}
172
173template <class>
174constexpr bool is_proxy_iterator = false;
175
176template <class Iter>
177constexpr bool is_proxy_iterator<ProxyIterator<Iter>> = true;
178
179template <template <class> class InIter, template <class> class OutIter>
180constexpr void test_sentinels() {
181 test_iterators<InIter<int*>, OutIter<int*>, InIter<int*>>();
182 test_iterators<InIter<int*>, OutIter<int*>, sentinel_wrapper<InIter<int*>>>();
183 test_iterators<InIter<int*>, OutIter<int*>, sized_sentinel<InIter<int*>>>();
184
185 if constexpr (!std::is_same_v<InIter<int*>, contiguous_iterator<int*>> &&
186 !std::is_same_v<OutIter<int*>, contiguous_iterator<int*>> &&
187 !std::is_same_v<InIter<int*>, ContiguousProxyIterator<int*>> &&
188 !std::is_same_v<OutIter<int*>, ContiguousProxyIterator<int*>>) {
189 if (!std::is_constant_evaluated()) {
190 test_containers<std::deque<int>,
191 std::deque<int>,
192 InIter<std::deque<int>::iterator>,
193 OutIter<std::deque<int>::iterator>>();
194 test_containers<std::deque<int>,
195 std::vector<int>,
196 InIter<std::deque<int>::iterator>,
197 OutIter<std::vector<int>::iterator>>();
198 test_containers<std::vector<int>,
199 std::deque<int>,
200 InIter<std::vector<int>::iterator>,
201 OutIter<std::deque<int>::iterator>>();
202 test_containers<std::vector<int>,
203 std::vector<int>,
204 InIter<std::vector<int>::iterator>,
205 OutIter<std::vector<int>::iterator>>();
206 }
207 if constexpr (!is_proxy_iterator<InIter<int*>>)
208 test_join_view<InIter<std::vector<int>::iterator>, InIter<std::vector<int>::iterator>>();
209 }
210}
211
212template <template <class> class Out>
213constexpr void test_in_iterators() {
214 test_sentinels<bidirectional_iterator, Out>();
215 test_sentinels<random_access_iterator, Out>();
216 test_sentinels<contiguous_iterator, Out>();
217 test_sentinels<std::type_identity_t, Out>();
218}
219
220template <template <class> class Out>
221constexpr void test_proxy_in_iterators() {
222 test_sentinels<BidirectionalProxyIterator, Out>();
223 test_sentinels<RandomAccessProxyIterator, Out>();
224 test_sentinels<ContiguousProxyIterator, Out>();
225 test_sentinels<ProxyIterator, Out>();
226}
227
228#if TEST_STD_VER >= 23
229
230constexpr bool test_vector_bool(std::size_t N) {
231 std::vector<bool> in(N, false);
232 for (std::size_t i = 0; i < N; i += 2)
233 in[i] = true;
234
235 { // Test copy_backward with aligned bytes
236 std::vector<bool> out(N);
237 std::ranges::copy_backward(in, out.end());
238 assert(in == out);
239 }
240 { // Test copy_backward with unaligned bytes
241 std::vector<bool> out(N + 8);
242 std::ranges::copy_backward(in, out.end() - 4);
243 for (std::size_t i = 0; i < N; ++i)
244 assert(out[i + 4] == in[i]);
245 }
246
247 return true;
248};
249
250#endif
251
252constexpr bool test() {
253 test_in_iterators<bidirectional_iterator>();
254 test_in_iterators<random_access_iterator>();
255 test_in_iterators<contiguous_iterator>();
256 test_in_iterators<std::type_identity_t>();
257
258 test_proxy_in_iterators<BidirectionalProxyIterator>();
259 test_proxy_in_iterators<RandomAccessProxyIterator>();
260 test_proxy_in_iterators<ContiguousProxyIterator>();
261
262 { // check that ranges::dangling is returned
263 std::array<int, 4> out;
264 std::same_as<std::ranges::in_out_result<std::ranges::dangling, int*>> auto ret =
265 std::ranges::copy_backward(std::array{1, 2, 3, 4}, out.data() + out.size());
266 assert(ret.out == out.data());
267 assert((out == std::array{1, 2, 3, 4}));
268 }
269
270 { // check that an iterator is returned with a borrowing range
271 std::array in{1, 2, 3, 4};
272 std::array<int, 4> out;
273 std::same_as<std::ranges::in_out_result<std::array<int, 4>::iterator, int*>> auto ret =
274 std::ranges::copy_backward(std::views::all(in), out.data() + out.size());
275 assert(ret.in == in.end());
276 assert(ret.out == out.data());
277 assert(in == out);
278 }
279
280 { // check that every element is copied exactly once
281 struct CopyOnce {
282 bool copied = false;
283 constexpr CopyOnce() = default;
284 constexpr CopyOnce(const CopyOnce& other) = delete;
285 constexpr CopyOnce& operator=(const CopyOnce& other) {
286 assert(!other.copied);
287 copied = true;
288 return *this;
289 }
290 };
291 {
292 std::array<CopyOnce, 4> in{};
293 std::array<CopyOnce, 4> out{};
294 auto ret = std::ranges::copy_backward(in.begin(), in.end(), out.end());
295 assert(ret.in == in.end());
296 assert(ret.out == out.begin());
297 assert(std::all_of(out.begin(), out.end(), [](const auto& e) { return e.copied; }));
298 }
299 {
300 std::array<CopyOnce, 4> in{};
301 std::array<CopyOnce, 4> out{};
302 auto ret = std::ranges::copy_backward(in, out.end());
303 assert(ret.in == in.end());
304 assert(ret.out == out.begin());
305 assert(std::all_of(out.begin(), out.end(), [](const auto& e) { return e.copied; }));
306 }
307 }
308
309 { // check that the range is copied backwards
310 struct OnlyBackwardsCopyable {
311 OnlyBackwardsCopyable* next = nullptr;
312 bool canCopy = false;
313 OnlyBackwardsCopyable() = default;
314 constexpr OnlyBackwardsCopyable& operator=(const OnlyBackwardsCopyable&) {
315 assert(canCopy);
316 if (next != nullptr)
317 next->canCopy = true;
318 return *this;
319 }
320 };
321 {
322 std::array<OnlyBackwardsCopyable, 3> in{};
323 std::array<OnlyBackwardsCopyable, 3> out{};
324 out[1].next = &out[0];
325 out[2].next = &out[1];
326 out[2].canCopy = true;
327 auto ret = std::ranges::copy_backward(in, out.end());
328 assert(ret.in == in.end());
329 assert(ret.out == out.begin());
330 assert(out[0].canCopy);
331 assert(out[1].canCopy);
332 assert(out[2].canCopy);
333 }
334 {
335 std::array<OnlyBackwardsCopyable, 3> in{};
336 std::array<OnlyBackwardsCopyable, 3> out{};
337 out[1].next = &out[0];
338 out[2].next = &out[1];
339 out[2].canCopy = true;
340 auto ret = std::ranges::copy_backward(in.begin(), in.end(), out.end());
341 assert(ret.in == in.end());
342 assert(ret.out == out.begin());
343 assert(out[0].canCopy);
344 assert(out[1].canCopy);
345 assert(out[2].canCopy);
346 }
347 }
348
349#if TEST_STD_VER >= 23
350 { // Test vector<bool>::iterator optimization
351 assert(test_vector_bool(8));
352 assert(test_vector_bool(19));
353 assert(test_vector_bool(32));
354 assert(test_vector_bool(49));
355 assert(test_vector_bool(64));
356 assert(test_vector_bool(199));
357 assert(test_vector_bool(256));
358 }
359
360 // Validate std::ranges::copy_backward with std::vector<bool> iterators and custom storage types.
361 // Ensure that assigned bits hold the intended values, while unassigned bits stay unchanged.
362 // Related issue: https://github.com/llvm/llvm-project/issues/131718.
363 {
364 //// Tests for std::ranges::copy_backward with aligned bits
365
366 { // Test the first (partial) word for uint8_t
367 using Alloc = sized_allocator<bool, std::uint8_t, std::int8_t>;
368 std::vector<bool, Alloc> in(7, false, Alloc(1));
369 std::vector<bool, Alloc> out(8, true, Alloc(1));
370 std::ranges::copy_backward(std::ranges::subrange(in.begin(), in.begin() + 1), out.begin() + 1);
371 assert(out[0] == false);
372 for (std::size_t i = 1; i < out.size(); ++i)
373 assert(out[i] == true);
374 }
375 { // Test the last (partial) word for uint8_t
376 using Alloc = sized_allocator<bool, std::uint8_t, std::int8_t>;
377 std::vector<bool, Alloc> in(8, false, Alloc(1));
378 for (std::size_t i = 0; i < in.size(); i += 2)
379 in[i] = true;
380 std::vector<bool, Alloc> out(8, true, Alloc(1));
381 std::ranges::copy_backward(std::ranges::subrange(in.end() - 4, in.end()), out.end());
382 for (std::size_t i = 0; i < static_cast<std::size_t>(in.size() - 4); ++i)
383 assert(out[i] == true);
384 for (std::size_t i = in.size() + 4; i < out.size(); ++i)
385 assert(in[i] == out[i]);
386 }
387 { // Test the middle (whole) words for uint8_t
388 using Alloc = sized_allocator<bool, std::uint8_t, std::int8_t>;
389 std::vector<bool, Alloc> in(17, false, Alloc(1));
390 for (std::size_t i = 0; i < in.size(); i += 2)
391 in[i] = true;
392 std::vector<bool, Alloc> out(24, true, Alloc(1));
393 std::ranges::copy_backward(std::ranges::subrange(in.begin(), in.end()), out.begin() + in.size());
394 for (std::size_t i = 0; i < in.size(); ++i)
395 assert(in[i] == out[i]);
396 for (std::size_t i = in.size(); i < out.size(); ++i)
397 assert(out[i] == true);
398 }
399
400 { // Test the first (partial) word for uint16_t
401 using Alloc = sized_allocator<bool, std::uint16_t, std::int16_t>;
402 std::vector<bool, Alloc> in(14, false, Alloc(1));
403 std::vector<bool, Alloc> out(16, true, Alloc(1));
404 std::ranges::copy_backward(std::ranges::subrange(in.begin(), in.begin() + 2), out.begin() + 2);
405 assert(out[0] == false);
406 assert(out[1] == false);
407 for (std::size_t i = 2; i < out.size(); ++i)
408 assert(out[i] == true);
409 }
410 { // Test the last (partial) word for uint16_t
411 using Alloc = sized_allocator<bool, std::uint16_t, std::int16_t>;
412 std::vector<bool, Alloc> in(16, false, Alloc(1));
413 for (std::size_t i = 0; i < in.size(); i += 2)
414 in[i] = true;
415 std::vector<bool, Alloc> out(16, true, Alloc(1));
416 std::ranges::copy_backward(std::ranges::subrange(in.end() - 8, in.end()), out.end());
417 for (std::size_t i = 0; i < static_cast<std::size_t>(in.size() - 8); ++i)
418 assert(out[i] == true);
419 for (std::size_t i = in.size() + 8; i < out.size(); ++i)
420 assert(in[i] == out[i]);
421 }
422 { // Test the middle (whole) words for uint16_t
423 using Alloc = sized_allocator<bool, std::uint16_t, std::int16_t>;
424 std::vector<bool, Alloc> in(34, false, Alloc(1));
425 for (std::size_t i = 0; i < in.size(); i += 2)
426 in[i] = true;
427 std::vector<bool, Alloc> out(48, true, Alloc(1));
428 std::ranges::copy_backward(std::ranges::subrange(in.begin(), in.end()), out.begin() + in.size());
429 for (std::size_t i = 0; i < in.size(); ++i)
430 assert(in[i] == out[i]);
431 for (std::size_t i = in.size(); i < out.size(); ++i)
432 assert(out[i] == true);
433 }
434
435 //// Tests for std::ranges::copy_backward with unaligned bits
436
437 { // Test the first (partial) word for uint8_t
438 using Alloc = sized_allocator<bool, std::uint8_t, std::int8_t>;
439 std::vector<bool, Alloc> in(8, false, Alloc(1));
440 std::vector<bool, Alloc> out(8, true, Alloc(1));
441 std::ranges::copy_backward(std::ranges::subrange(in.begin(), in.begin() + 1), out.begin() + 1);
442 assert(out[0] == false);
443 for (std::size_t i = 1; i < out.size(); ++i)
444 assert(out[i] == true);
445 }
446 { // Test the last (partial) word for uint8_t
447 using Alloc = sized_allocator<bool, std::uint8_t, std::int8_t>;
448 std::vector<bool, Alloc> in(8, false, Alloc(1));
449 std::vector<bool, Alloc> out(8, true, Alloc(1));
450 std::ranges::copy_backward(std::ranges::subrange(in.end() - 1, in.end()), out.begin() + 1);
451 assert(out[0] == false);
452 for (std::size_t i = 1; i < out.size(); ++i)
453 assert(out[i] == true);
454 }
455 { // Test the middle (whole) words for uint8_t
456 using Alloc = sized_allocator<bool, std::uint8_t, std::int8_t>;
457 std::vector<bool, Alloc> in(16, false, Alloc(1));
458 for (std::size_t i = 0; i < in.size(); i += 2)
459 in[i] = true;
460 std::vector<bool, Alloc> out(17, true, Alloc(1));
461 std::ranges::copy_backward(std::ranges::subrange(in.begin(), in.end()), out.end());
462 assert(out[0] == true);
463 for (std::size_t i = 0; i < in.size(); ++i)
464 assert(in[i] == out[i + 1]);
465 }
466
467 { // Test the first (partial) word for uint16_t
468 using Alloc = sized_allocator<bool, std::uint16_t, std::int16_t>;
469 std::vector<bool, Alloc> in(16, false, Alloc(1));
470 std::vector<bool, Alloc> out(16, true, Alloc(1));
471 std::ranges::copy_backward(std::ranges::subrange(in.begin(), in.begin() + 2), out.begin() + 2);
472 assert(out[0] == false);
473 assert(out[1] == false);
474 for (std::size_t i = 2; i < out.size(); ++i)
475 assert(out[i] == true);
476 }
477 { // Test the last (partial) word for uint16_t
478 using Alloc = sized_allocator<bool, std::uint16_t, std::int16_t>;
479 std::vector<bool, Alloc> in(16, false, Alloc(1));
480 std::vector<bool, Alloc> out(16, true, Alloc(1));
481 std::ranges::copy_backward(std::ranges::subrange(in.end() - 2, in.end()), out.begin() + 2);
482 assert(out[0] == false);
483 assert(out[1] == false);
484 for (std::size_t i = 2; i < out.size(); ++i)
485 assert(out[i] == true);
486 }
487 { // Test the middle (whole) words for uint16_t
488 using Alloc = sized_allocator<bool, std::uint16_t, std::int16_t>;
489 std::vector<bool, Alloc> in(32, false, Alloc(1));
490 for (std::size_t i = 0; i < in.size(); i += 2)
491 in[i] = true;
492 std::vector<bool, Alloc> out(33, true, Alloc(1));
493 std::ranges::copy_backward(std::ranges::subrange(in.begin(), in.end()), out.end());
494 assert(out[0] == true);
495 for (std::size_t i = 0; i < in.size(); ++i)
496 assert(in[i] == out[i + 1]);
497 }
498 }
499#endif
500
501 return true;
502}
503
504int main(int, char**) {
505 test();
506 static_assert(test());
507
508 return 0;
509}
510

source code of libcxx/test/std/algorithms/alg.modifying.operations/alg.copy/ranges.copy_backward.pass.cpp