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// UNSUPPORTED: c++03, c++11, c++14, c++17
10// UNSUPPORTED: GCC-ALWAYS_INLINE-FIXME
11
12// <algorithm>
13
14// template<bidirectional_iterator I1, sentinel_for<I1> S1, bidirectional_iterator I2>
15// requires indirectly_movable<I1, I2>
16// constexpr ranges::move_backward_result<I1, I2>
17// ranges::move_backward(I1 first, S1 last, I2 result);
18// template<bidirectional_range R, bidirectional_iterator I>
19// requires indirectly_movable<iterator_t<R>, I>
20// constexpr ranges::move_backward_result<borrowed_iterator_t<R>, I>
21// ranges::move_backward(R&& r, I result);
22
23#include <algorithm>
24#include <array>
25#include <cassert>
26#include <deque>
27#include <iterator>
28#include <ranges>
29#include <vector>
30
31#include "almost_satisfies_types.h"
32#include "MoveOnly.h"
33#include "test_iterators.h"
34#include "test_macros.h"
35
36template <class In, class Out = In, class Sent = sentinel_wrapper<In>>
37concept HasMoveBackwardIt = requires(In in, Sent sent, Out out) { std::ranges::move_backward(in, sent, out); };
38
39static_assert(HasMoveBackwardIt<int*>);
40static_assert(!HasMoveBackwardIt<InputIteratorNotDerivedFrom>);
41static_assert(!HasMoveBackwardIt<InputIteratorNotIndirectlyReadable>);
42static_assert(!HasMoveBackwardIt<InputIteratorNotInputOrOutputIterator>);
43static_assert(!HasMoveBackwardIt<int*, WeaklyIncrementableNotMovable>);
44struct NotIndirectlyCopyable {};
45static_assert(!HasMoveBackwardIt<int*, NotIndirectlyCopyable*>);
46static_assert(!HasMoveBackwardIt<int*, int*, SentinelForNotSemiregular>);
47static_assert(!HasMoveBackwardIt<int*, int*, SentinelForNotWeaklyEqualityComparableWith>);
48
49template <class Range, class Out>
50concept HasMoveBackwardR = requires(Range range, Out out) { std::ranges::move_backward(range, out); };
51
52static_assert(HasMoveBackwardR<std::array<int, 10>, int*>);
53static_assert(!HasMoveBackwardR<InputRangeNotDerivedFrom, int*>);
54static_assert(!HasMoveBackwardR<InputRangeNotIndirectlyReadable, int*>);
55static_assert(!HasMoveBackwardR<InputRangeNotInputOrOutputIterator, int*>);
56static_assert(!HasMoveBackwardR<WeaklyIncrementableNotMovable, int*>);
57static_assert(!HasMoveBackwardR<UncheckedRange<NotIndirectlyCopyable*>, int*>);
58static_assert(!HasMoveBackwardR<InputRangeNotSentinelSemiregular, int*>);
59static_assert(!HasMoveBackwardR<InputRangeNotSentinelEqualityComparableWith, int*>);
60static_assert(!HasMoveBackwardR<UncheckedRange<int*>, WeaklyIncrementableNotMovable>);
61
62static_assert(std::is_same_v<std::ranges::copy_result<int, long>, std::ranges::in_out_result<int, long>>);
63
64template <class In, class Out, class Sent, int N>
65constexpr void test(std::array<int, N> in) {
66 {
67 std::array<int, N> out;
68 std::same_as<std::ranges::in_out_result<In, Out>> decltype(auto) ret =
69 std::ranges::move_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<int, N> out;
76 auto range = std::ranges::subrange(In(in.data()), Sent(In(in.data() + in.size())));
77 std::same_as<std::ranges::in_out_result<In, Out>> decltype(auto) ret =
78 std::ranges::move_backward(range, Out(out.data() + out.size()));
79 assert(in == out);
80 assert(base(ret.in) == in.data() + in.size());
81 assert(base(ret.out) == out.data());
82 }
83}
84
85template <class In, class Out, class Sent = In>
86constexpr void test_iterators() {
87 // simple test
88 test<In, Out, Sent, 4>({1, 2, 3, 4});
89 // check that an empty range works
90 test<In, Out, Sent, 0>({});
91}
92
93template <class InContainer, class OutContainer, class In, class Out, class Sent = In>
94constexpr void test_containers() {
95 {
96 InContainer in{1, 2, 3, 4};
97 OutContainer out(4);
98 std::same_as<std::ranges::in_out_result<In, Out>> auto ret =
99 std::ranges::move_backward(In(in.begin()), Sent(In(in.end())), Out(out.end()));
100 assert(std::ranges::equal(in, out));
101 assert(base(ret.in) == in.end());
102 assert(base(ret.out) == out.begin());
103 }
104 {
105 InContainer in{1, 2, 3, 4};
106 OutContainer out(4);
107 auto range = std::ranges::subrange(In(in.begin()), Sent(In(in.end())));
108 std::same_as<std::ranges::in_out_result<In, Out>> auto ret = std::ranges::move_backward(range, Out(out.end()));
109 assert(std::ranges::equal(in, out));
110 assert(base(ret.in) == in.end());
111 assert(base(ret.out) == out.begin());
112 }
113}
114
115template <template <class> class InIter, template <class> class OutIter>
116constexpr void test_sentinels() {
117 test_iterators<InIter<int*>, OutIter<int*>, InIter<int*>>();
118 test_iterators<InIter<int*>, OutIter<int*>, sentinel_wrapper<InIter<int*>>>();
119 test_iterators<InIter<int*>, OutIter<int*>, sized_sentinel<InIter<int*>>>();
120
121 if (!std::is_constant_evaluated()) {
122 if constexpr (!std::is_same_v<InIter<int*>, contiguous_iterator<int*>> &&
123 !std::is_same_v<OutIter<int*>, contiguous_iterator<int*>> &&
124 !std::is_same_v<InIter<int*>, ContiguousProxyIterator<int*>> &&
125 !std::is_same_v<OutIter<int*>, ContiguousProxyIterator<int*>>) {
126 test_containers<std::deque<int>,
127 std::deque<int>,
128 InIter<std::deque<int>::iterator>,
129 OutIter<std::deque<int>::iterator>>();
130 test_containers<std::deque<int>,
131 std::vector<int>,
132 InIter<std::deque<int>::iterator>,
133 OutIter<std::vector<int>::iterator>>();
134 test_containers<std::vector<int>,
135 std::deque<int>,
136 InIter<std::vector<int>::iterator>,
137 OutIter<std::deque<int>::iterator>>();
138 test_containers<std::vector<int>,
139 std::vector<int>,
140 InIter<std::vector<int>::iterator>,
141 OutIter<std::vector<int>::iterator>>();
142 }
143 }
144}
145
146template <template <class> class Out>
147constexpr void test_in_iterators() {
148 test_sentinels<bidirectional_iterator, Out>();
149 test_sentinels<random_access_iterator, Out>();
150 test_sentinels<contiguous_iterator, Out>();
151 test_sentinels<std::type_identity_t, Out>();
152}
153
154template <template <class> class Out>
155constexpr void test_proxy_in_iterators() {
156 test_sentinels<BidirectionalProxyIterator, Out>();
157 test_sentinels<RandomAccessProxyIterator, Out>();
158 test_sentinels<ContiguousProxyIterator, Out>();
159 test_sentinels<ProxyIterator, Out>();
160}
161
162struct IteratorWithMoveIter {
163 using value_type = int;
164 using difference_type = int;
165 explicit IteratorWithMoveIter() = default;
166 int* ptr;
167 constexpr IteratorWithMoveIter(int* ptr_) : ptr(ptr_) {}
168
169 constexpr int& operator*() const; // iterator with iter_move should not be dereferenced
170
171 constexpr IteratorWithMoveIter& operator++() {
172 ++ptr;
173 return *this;
174 }
175 constexpr IteratorWithMoveIter operator++(int) {
176 auto ret = *this;
177 ++*this;
178 return ret;
179 }
180
181 constexpr IteratorWithMoveIter& operator--() {
182 --ptr;
183 return *this;
184 }
185 constexpr IteratorWithMoveIter operator--(int) {
186 auto ret = *this;
187 --*this;
188 return ret;
189 }
190
191 friend constexpr int iter_move(const IteratorWithMoveIter&) { return 42; }
192
193 constexpr bool operator==(const IteratorWithMoveIter& other) const = default;
194};
195
196#if TEST_STD_VER >= 23
197constexpr bool test_vector_bool(std::size_t N) {
198 std::vector<bool> v(N, false);
199 for (std::size_t i = 0; i < N; i += 2)
200 v[i] = true;
201
202 { // Test move_backward with aligned bytes
203 std::vector<bool> in{v};
204 std::vector<bool> out(N);
205 std::ranges::move_backward(in, out.end());
206 assert(out == v);
207 }
208 { // Test move_backward with unaligned bytes
209 std::vector<bool> in{v};
210 std::vector<bool> out(N);
211 std::ranges::move_backward(std::views::counted(in.begin(), N - 4), out.end());
212 assert(std::ranges::equal(v | std::views::take(N - 4), out | std::views::drop(4)));
213 }
214
215 return true;
216}
217#endif
218
219constexpr bool test() {
220 test_in_iterators<bidirectional_iterator>();
221 test_in_iterators<random_access_iterator>();
222 test_in_iterators<contiguous_iterator>();
223 test_in_iterators<std::type_identity_t>();
224
225 test_proxy_in_iterators<BidirectionalProxyIterator>();
226 test_proxy_in_iterators<RandomAccessProxyIterator>();
227 test_proxy_in_iterators<ContiguousProxyIterator>();
228 test_proxy_in_iterators<ProxyIterator>();
229
230 { // check that a move-only type works
231 // When non-trivial
232 {
233 MoveOnly a[] = {1, 2, 3};
234 MoveOnly b[3];
235 std::ranges::move_backward(a, std::end(b));
236 assert(b[0].get() == 1);
237 assert(b[1].get() == 2);
238 assert(b[2].get() == 3);
239 }
240 {
241 MoveOnly a[] = {1, 2, 3};
242 MoveOnly b[3];
243 std::ranges::move_backward(std::begin(a), std::end(a), std::end(b));
244 assert(b[0].get() == 1);
245 assert(b[1].get() == 2);
246 assert(b[2].get() == 3);
247 }
248
249 // When trivial
250 {
251 TrivialMoveOnly a[] = {1, 2, 3};
252 TrivialMoveOnly b[3];
253 std::ranges::move_backward(a, std::end(b));
254 assert(b[0].get() == 1);
255 assert(b[1].get() == 2);
256 assert(b[2].get() == 3);
257 }
258 {
259 TrivialMoveOnly a[] = {1, 2, 3};
260 TrivialMoveOnly b[3];
261 std::ranges::move_backward(std::begin(a), std::end(a), std::end(b));
262 assert(b[0].get() == 1);
263 assert(b[1].get() == 2);
264 assert(b[2].get() == 3);
265 }
266 }
267
268 { // check that a move-only type works for ProxyIterator
269 {
270 MoveOnly a[] = {1, 2, 3};
271 MoveOnly b[3];
272 ProxyRange proxyA{a};
273 ProxyRange proxyB{b};
274 std::ranges::move_backward(proxyA, std::ranges::next(proxyB.begin(), std::end(proxyB)));
275 assert(b[0].get() == 1);
276 assert(b[1].get() == 2);
277 assert(b[2].get() == 3);
278 }
279 {
280 MoveOnly a[] = {1, 2, 3};
281 MoveOnly b[3];
282 ProxyRange proxyA{a};
283 ProxyRange proxyB{b};
284 std::ranges::move_backward(
285 std::begin(proxyA), std::end(proxyA), std::ranges::next(proxyB.begin(), std::end(proxyB)));
286 assert(b[0].get() == 1);
287 assert(b[1].get() == 2);
288 assert(b[2].get() == 3);
289 }
290 }
291
292 { // check that ranges::dangling is returned
293 std::array<int, 4> out;
294 std::same_as<std::ranges::in_out_result<std::ranges::dangling, int*>> auto ret =
295 std::ranges::move_backward(std::array{1, 2, 3, 4}, out.data() + out.size());
296 assert(ret.out == out.data());
297 assert((out == std::array{1, 2, 3, 4}));
298 }
299
300 { // check that an iterator is returned with a borrowing range
301 std::array in{1, 2, 3, 4};
302 std::array<int, 4> out;
303 std::same_as<std::ranges::in_out_result<std::array<int, 4>::iterator, int*>> auto ret =
304 std::ranges::move_backward(std::views::all(in), out.data() + out.size());
305 assert(ret.in == in.end());
306 assert(ret.out == out.data());
307 assert(in == out);
308 }
309
310 { // check that every element is moved exactly once
311 struct MoveOnce {
312 bool moved = false;
313 constexpr MoveOnce() = default;
314 constexpr MoveOnce(const MoveOnce& other) = delete;
315 constexpr MoveOnce& operator=(const MoveOnce& other) {
316 assert(!other.moved);
317 moved = true;
318 return *this;
319 }
320 };
321 {
322 std::array<MoveOnce, 4> in{};
323 std::array<MoveOnce, 4> out{};
324 auto ret = std::ranges::move_backward(in.begin(), in.end(), out.end());
325 assert(ret.in == in.end());
326 assert(ret.out == out.begin());
327 assert(std::all_of(out.begin(), out.end(), [](const auto& e) { return e.moved; }));
328 }
329 {
330 std::array<MoveOnce, 4> in{};
331 std::array<MoveOnce, 4> out{};
332 auto ret = std::ranges::move_backward(in, out.end());
333 assert(ret.in == in.end());
334 assert(ret.out == out.begin());
335 assert(std::all_of(out.begin(), out.end(), [](const auto& e) { return e.moved; }));
336 }
337 }
338
339 { // check that the range is moved backwards
340 struct OnlyBackwardsMovable {
341 OnlyBackwardsMovable* next = nullptr;
342 bool canMove = false;
343 OnlyBackwardsMovable() = default;
344 constexpr OnlyBackwardsMovable& operator=(const OnlyBackwardsMovable&) {
345 assert(canMove);
346 if (next != nullptr)
347 next->canMove = true;
348 return *this;
349 }
350 };
351 {
352 std::array<OnlyBackwardsMovable, 3> in{};
353 std::array<OnlyBackwardsMovable, 3> out{};
354 out[1].next = &out[0];
355 out[2].next = &out[1];
356 out[2].canMove = true;
357 auto ret = std::ranges::move_backward(in, out.end());
358 assert(ret.in == in.end());
359 assert(ret.out == out.begin());
360 assert(out[0].canMove);
361 assert(out[1].canMove);
362 assert(out[2].canMove);
363 }
364 {
365 std::array<OnlyBackwardsMovable, 3> in{};
366 std::array<OnlyBackwardsMovable, 3> out{};
367 out[1].next = &out[0];
368 out[2].next = &out[1];
369 out[2].canMove = true;
370 auto ret = std::ranges::move_backward(in.begin(), in.end(), out.end());
371 assert(ret.in == in.end());
372 assert(ret.out == out.begin());
373 assert(out[0].canMove);
374 assert(out[1].canMove);
375 assert(out[2].canMove);
376 }
377 }
378
379 { // check that iter_move is used properly
380 {
381 int a[] = {1, 2, 3, 4};
382 std::array<int, 4> b;
383 auto ret = std::ranges::move_backward(IteratorWithMoveIter(a), IteratorWithMoveIter(a + 4), b.data() + b.size());
384 assert(ret.in == a + 4);
385 assert(ret.out == b.data());
386 assert((b == std::array{42, 42, 42, 42}));
387 }
388 {
389 int a[] = {1, 2, 3, 4};
390 std::array<int, 4> b;
391 auto range = std::ranges::subrange(IteratorWithMoveIter(a), IteratorWithMoveIter(a + 4));
392 auto ret = std::ranges::move_backward(range, b.data() + b.size());
393 assert(ret.in == a + 4);
394 assert(ret.out == b.data());
395 assert((b == std::array{42, 42, 42, 42}));
396 }
397 }
398
399#if TEST_STD_VER >= 23
400 { // Test vector<bool>::iterator optimization
401 assert(test_vector_bool(8));
402 assert(test_vector_bool(19));
403 assert(test_vector_bool(32));
404 assert(test_vector_bool(49));
405 assert(test_vector_bool(64));
406 assert(test_vector_bool(199));
407 assert(test_vector_bool(256));
408 }
409#endif
410
411 return true;
412}
413
414int main(int, char**) {
415 test();
416 static_assert(test());
417
418 return 0;
419}
420

source code of libcxx/test/std/algorithms/alg.modifying.operations/alg.move/ranges.move_backward.pass.cpp