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