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