libcxx/test/std/algorithms/alg.modifying.operations/alg.move/ranges.move_backward.pass.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-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
  35 template <class In, class Out = In, class Sent = sentinel_wrapper<In>>
  36 concept HasMoveBackwardIt = requires(In in, Sent sent, Out out) { std::ranges::move_backward(in, sent, out); };
  37
  38 static_assert(HasMoveBackwardIt<int*>);
  39 static_assert(!HasMoveBackwardIt<InputIteratorNotDerivedFrom>);
  40 static_assert(!HasMoveBackwardIt<InputIteratorNotIndirectlyReadable>);
  41 static_assert(!HasMoveBackwardIt<InputIteratorNotInputOrOutputIterator>);
  42 static_assert(!HasMoveBackwardIt<int*, WeaklyIncrementableNotMovable>);
  43 struct NotIndirectlyCopyable {};
  44 static_assert(!HasMoveBackwardIt<int*, NotIndirectlyCopyable*>);
  45 static_assert(!HasMoveBackwardIt<int*, int*, SentinelForNotSemiregular>);
  46 static_assert(!HasMoveBackwardIt<int*, int*, SentinelForNotWeaklyEqualityComparableWith>);
  47
  48 template <class Range, class Out>
  49 concept HasMoveBackwardR = requires(Range range, Out out) { std::ranges::move_backward(range, out); };
  50
  51 static_assert(HasMoveBackwardR<std::array<int, 10>, int*>);
  52 static_assert(!HasMoveBackwardR<InputRangeNotDerivedFrom, int*>);
  53 static_assert(!HasMoveBackwardR<InputRangeNotIndirectlyReadable, int*>);
  54 static_assert(!HasMoveBackwardR<InputRangeNotInputOrOutputIterator, int*>);
  55 static_assert(!HasMoveBackwardR<WeaklyIncrementableNotMovable, int*>);
  56 static_assert(!HasMoveBackwardR<UncheckedRange<NotIndirectlyCopyable*>, int*>);
  57 static_assert(!HasMoveBackwardR<InputRangeNotSentinelSemiregular, int*>);
  58 static_assert(!HasMoveBackwardR<InputRangeNotSentinelEqualityComparableWith, int*>);
  59 static_assert(!HasMoveBackwardR<UncheckedRange<int*>, WeaklyIncrementableNotMovable>);
  60
  61 static_assert(std::is_same_v<std::ranges::copy_result<int, long>, std::ranges::in_out_result<int, long>>);
  62
  63 template <class In, class Out, class Sent, int N>
  64 constexpr 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
  84 template <class In, class Out, class Sent = In>
  85 constexpr 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
  92 template <class InContainer, class OutContainer, class In, class Out, class Sent = In>
  93 constexpr 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
 114 template <template <class> class InIter, template <class> class OutIter>
 115 constexpr 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
 145 template <template <class> class Out>
 146 constexpr 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
 153 template <template <class> class Out>
 154 constexpr 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
 161 struct 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
 181 constexpr 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
 363 int main(int, char**) {
 364   test();
 365   static_assert(test());
 366
 367   return 0;
 368 }