420 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8 9// UNSUPPORTED: c++03, c++11, c++14, c++1710// UNSUPPORTED: GCC-ALWAYS_INLINE-FIXME11 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 test88 test<In, Out, Sent, 4>({1, 2, 3, 4});89 // check that an empty range works90 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 dereferenced170 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 >= 23197constexpr 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 bytes203 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 bytes209 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#endif218 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 works231 // When non-trivial232 {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 trivial250 {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 ProxyIterator269 {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 returned293 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 range301 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 once311 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 backwards340 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 properly380 {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 >= 23400 { // Test vector<bool>::iterator optimization401 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#endif410 411 return true;412}413 414int main(int, char**) {415 test();416 static_assert(test());417 418 return 0;419}420