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

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