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<int*, int*>> decltype(auto) ret = 279 std::ranges::move(std::views::all(in), out.data()); 280 assert(ret.in == in.data() + 4); 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 } 383