510 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// <algorithm>10 11// UNSUPPORTED: c++03, c++11, c++14, c++1712// UNSUPPORTED: GCC-ALWAYS_INLINE-FIXME13 14// template<bidirectional_iterator I1, sentinel_for<I1> S1, bidirectional_iterator I2>15// requires indirectly_copyable<I1, I2>16// constexpr ranges::copy_backward_result<I1, I2>17// ranges::copy_backward(I1 first, S1 last, I2 result);18// template<bidirectional_range R, bidirectional_iterator I>19// requires indirectly_copyable<iterator_t<R>, I>20// constexpr ranges::copy_backward_result<borrowed_iterator_t<R>, I>21// ranges::copy_backward(R&& r, I result);22 23#include <algorithm>24#include <array>25#include <cassert>26#include <deque>27#include <ranges>28#include <vector>29 30#include "almost_satisfies_types.h"31#include "sized_allocator.h"32#include "test_iterators.h"33#include "test_macros.h"34 35template <class In, class Out = In, class Sent = sentinel_wrapper<In>>36concept HasCopyBackwardIt = requires(In in, Sent sent, Out out) { std::ranges::copy_backward(in, sent, out); };37 38static_assert(HasCopyBackwardIt<int*>);39static_assert(!HasCopyBackwardIt<InputIteratorNotDerivedFrom>);40static_assert(!HasCopyBackwardIt<InputIteratorNotIndirectlyReadable>);41static_assert(!HasCopyBackwardIt<InputIteratorNotInputOrOutputIterator>);42static_assert(!HasCopyBackwardIt<int*, WeaklyIncrementableNotMovable>);43struct NotIndirectlyCopyable {};44static_assert(!HasCopyBackwardIt<int*, NotIndirectlyCopyable*>);45static_assert(!HasCopyBackwardIt<int*, int*, SentinelForNotSemiregular>);46static_assert(!HasCopyBackwardIt<int*, int*, SentinelForNotWeaklyEqualityComparableWith>);47 48template <class Range, class Out>49concept HasCopyBackwardR = requires(Range range, Out out) { std::ranges::copy_backward(range, out); };50 51static_assert(HasCopyBackwardR<std::array<int, 10>, int*>);52static_assert(!HasCopyBackwardR<InputRangeNotDerivedFrom, int*>);53static_assert(!HasCopyBackwardR<InputRangeNotIndirectlyReadable, int*>);54static_assert(!HasCopyBackwardR<InputRangeNotInputOrOutputIterator, int*>);55static_assert(!HasCopyBackwardR<WeaklyIncrementableNotMovable, int*>);56static_assert(!HasCopyBackwardR<UncheckedRange<NotIndirectlyCopyable*>, int*>);57static_assert(!HasCopyBackwardR<InputRangeNotSentinelSemiregular, int*>);58static_assert(!HasCopyBackwardR<InputRangeNotSentinelEqualityComparableWith, int*>);59 60static_assert(std::is_same_v<std::ranges::copy_result<int, long>, std::ranges::in_out_result<int, long>>);61 62template <class In, class Out, class Sent>63constexpr void test_iterators() {64 { // simple test65 {66 std::array in{1, 2, 3, 4};67 std::array<int, 4> out;68 std::same_as<std::ranges::in_out_result<In, Out>> auto ret =69 std::ranges::copy_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 in{1, 2, 3, 4};76 std::array<int, 4> out;77 auto range = std::ranges::subrange(In(in.data()), Sent(In(in.data() + in.size())));78 std::same_as<std::ranges::in_out_result<In, Out>> auto ret =79 std::ranges::copy_backward(range, Out(out.data() + out.size()));80 assert(in == out);81 assert(base(ret.in) == in.data() + in.size());82 assert(base(ret.out) == out.data());83 }84 }85 86 { // check that an empty range works87 {88 std::array<int, 0> in;89 std::array<int, 0> out;90 auto ret =91 std::ranges::copy_backward(In(in.data()), Sent(In(in.data() + in.size())), Out(out.data() + out.size()));92 assert(base(ret.in) == in.data() + in.size());93 assert(base(ret.out) == out.data());94 }95 {96 std::array<int, 0> in;97 std::array<int, 0> out;98 auto range = std::ranges::subrange(In(in.data()), Sent(In(in.data() + in.size())));99 auto ret = std::ranges::copy_backward(range, Out(out.data()));100 assert(base(ret.in) == in.data() + in.size());101 assert(base(ret.out) == out.data());102 }103 }104}105 106template <class InContainer, class OutContainer, class In, class Out, class Sent = In>107constexpr void test_containers() {108 {109 InContainer in{1, 2, 3, 4};110 OutContainer out(4);111 std::same_as<std::ranges::in_out_result<In, Out>> auto ret =112 std::ranges::copy_backward(In(in.begin()), Sent(In(in.end())), Out(out.end()));113 assert(std::ranges::equal(in, out));114 assert(base(ret.in) == in.end());115 assert(base(ret.out) == out.begin());116 }117 {118 InContainer in{1, 2, 3, 4};119 OutContainer out(4);120 auto range = std::ranges::subrange(In(in.begin()), Sent(In(in.end())));121 std::same_as<std::ranges::in_out_result<In, Out>> auto ret = std::ranges::copy_backward(range, Out(out.end()));122 assert(std::ranges::equal(in, out));123 assert(base(ret.in) == in.end());124 assert(base(ret.out) == out.begin());125 }126}127 128template <class Iter, class Sent>129constexpr void test_join_view() {130 auto to_subranges =131 std::views::transform([](auto& vec) { return std::ranges::subrange(Iter(vec.begin()), Sent(Iter(vec.end()))); });132 133 { // segmented -> contiguous134 std::vector<std::vector<int>> vectors = {};135 auto range = vectors | to_subranges;136 std::vector<std::ranges::subrange<Iter, Sent>> subrange_vector(range.begin(), range.end());137 std::array<int, 0> arr;138 139 std::ranges::copy_backward(subrange_vector | std::views::join, arr.end());140 assert(std::ranges::equal(arr, std::array<int, 0>{}));141 }142 { // segmented -> contiguous143 std::vector<std::vector<int>> vectors = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10}, {}};144 auto range = vectors | to_subranges;145 std::vector<std::ranges::subrange<Iter, Sent>> subrange_vector(range.begin(), range.end());146 std::array<int, 10> arr;147 148 std::ranges::copy_backward(subrange_vector | std::views::join, arr.end());149 assert(std::ranges::equal(arr, std::array{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}));150 }151 { // contiguous -> segmented152 std::vector<std::vector<int>> vectors = {{0, 0, 0, 0}, {0, 0}, {0, 0, 0, 0}, {}};153 auto range = vectors | to_subranges;154 std::vector<std::ranges::subrange<Iter, Sent>> subrange_vector(range.begin(), range.end());155 std::array arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};156 157 std::ranges::copy_backward(arr, (subrange_vector | std::views::join).end());158 assert(std::ranges::equal(subrange_vector | std::views::join, std::array{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}));159 }160 { // segmented -> segmented161 std::vector<std::vector<int>> vectors = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10}, {}};162 auto range1 = vectors | to_subranges;163 std::vector<std::ranges::subrange<Iter, Sent>> subrange_vector(range1.begin(), range1.end());164 std::vector<std::vector<int>> to_vectors = {{0, 0, 0, 0}, {0, 0, 0, 0}, {}, {0, 0}};165 auto range2 = to_vectors | to_subranges;166 std::vector<std::ranges::subrange<Iter, Sent>> to_subrange_vector(range2.begin(), range2.end());167 168 std::ranges::copy_backward(subrange_vector | std::views::join, (to_subrange_vector | std::views::join).end());169 assert(std::ranges::equal(to_subrange_vector | std::views::join, std::array{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}));170 }171}172 173template <class>174constexpr bool is_proxy_iterator = false;175 176template <class Iter>177constexpr bool is_proxy_iterator<ProxyIterator<Iter>> = true;178 179template <template <class> class InIter, template <class> class OutIter>180constexpr void test_sentinels() {181 test_iterators<InIter<int*>, OutIter<int*>, InIter<int*>>();182 test_iterators<InIter<int*>, OutIter<int*>, sentinel_wrapper<InIter<int*>>>();183 test_iterators<InIter<int*>, OutIter<int*>, sized_sentinel<InIter<int*>>>();184 185 if constexpr (!std::is_same_v<InIter<int*>, contiguous_iterator<int*>> &&186 !std::is_same_v<OutIter<int*>, contiguous_iterator<int*>> &&187 !std::is_same_v<InIter<int*>, ContiguousProxyIterator<int*>> &&188 !std::is_same_v<OutIter<int*>, ContiguousProxyIterator<int*>>) {189 if (!std::is_constant_evaluated()) {190 test_containers<std::deque<int>,191 std::deque<int>,192 InIter<std::deque<int>::iterator>,193 OutIter<std::deque<int>::iterator>>();194 test_containers<std::deque<int>,195 std::vector<int>,196 InIter<std::deque<int>::iterator>,197 OutIter<std::vector<int>::iterator>>();198 test_containers<std::vector<int>,199 std::deque<int>,200 InIter<std::vector<int>::iterator>,201 OutIter<std::deque<int>::iterator>>();202 test_containers<std::vector<int>,203 std::vector<int>,204 InIter<std::vector<int>::iterator>,205 OutIter<std::vector<int>::iterator>>();206 }207 if constexpr (!is_proxy_iterator<InIter<int*>>)208 test_join_view<InIter<std::vector<int>::iterator>, InIter<std::vector<int>::iterator>>();209 }210}211 212template <template <class> class Out>213constexpr void test_in_iterators() {214 test_sentinels<bidirectional_iterator, Out>();215 test_sentinels<random_access_iterator, Out>();216 test_sentinels<contiguous_iterator, Out>();217 test_sentinels<std::type_identity_t, Out>();218}219 220template <template <class> class Out>221constexpr void test_proxy_in_iterators() {222 test_sentinels<BidirectionalProxyIterator, Out>();223 test_sentinels<RandomAccessProxyIterator, Out>();224 test_sentinels<ContiguousProxyIterator, Out>();225 test_sentinels<ProxyIterator, Out>();226}227 228#if TEST_STD_VER >= 23229 230constexpr bool test_vector_bool(std::size_t N) {231 std::vector<bool> in(N, false);232 for (std::size_t i = 0; i < N; i += 2)233 in[i] = true;234 235 { // Test copy_backward with aligned bytes236 std::vector<bool> out(N);237 std::ranges::copy_backward(in, out.end());238 assert(in == out);239 }240 { // Test copy_backward with unaligned bytes241 std::vector<bool> out(N + 8);242 std::ranges::copy_backward(in, out.end() - 4);243 for (std::size_t i = 0; i < N; ++i)244 assert(out[i + 4] == in[i]);245 }246 247 return true;248};249 250#endif251 252constexpr bool test() {253 test_in_iterators<bidirectional_iterator>();254 test_in_iterators<random_access_iterator>();255 test_in_iterators<contiguous_iterator>();256 test_in_iterators<std::type_identity_t>();257 258 test_proxy_in_iterators<BidirectionalProxyIterator>();259 test_proxy_in_iterators<RandomAccessProxyIterator>();260 test_proxy_in_iterators<ContiguousProxyIterator>();261 262 { // check that ranges::dangling is returned263 std::array<int, 4> out;264 std::same_as<std::ranges::in_out_result<std::ranges::dangling, int*>> auto ret =265 std::ranges::copy_backward(std::array{1, 2, 3, 4}, out.data() + out.size());266 assert(ret.out == out.data());267 assert((out == std::array{1, 2, 3, 4}));268 }269 270 { // check that an iterator is returned with a borrowing range271 std::array in{1, 2, 3, 4};272 std::array<int, 4> out;273 std::same_as<std::ranges::in_out_result<std::array<int, 4>::iterator, int*>> auto ret =274 std::ranges::copy_backward(std::views::all(in), out.data() + out.size());275 assert(ret.in == in.end());276 assert(ret.out == out.data());277 assert(in == out);278 }279 280 { // check that every element is copied exactly once281 struct CopyOnce {282 bool copied = false;283 constexpr CopyOnce() = default;284 constexpr CopyOnce(const CopyOnce& other) = delete;285 constexpr CopyOnce& operator=(const CopyOnce& other) {286 assert(!other.copied);287 copied = true;288 return *this;289 }290 };291 {292 std::array<CopyOnce, 4> in{};293 std::array<CopyOnce, 4> out{};294 auto ret = std::ranges::copy_backward(in.begin(), in.end(), out.end());295 assert(ret.in == in.end());296 assert(ret.out == out.begin());297 assert(std::all_of(out.begin(), out.end(), [](const auto& e) { return e.copied; }));298 }299 {300 std::array<CopyOnce, 4> in{};301 std::array<CopyOnce, 4> out{};302 auto ret = std::ranges::copy_backward(in, out.end());303 assert(ret.in == in.end());304 assert(ret.out == out.begin());305 assert(std::all_of(out.begin(), out.end(), [](const auto& e) { return e.copied; }));306 }307 }308 309 { // check that the range is copied backwards310 struct OnlyBackwardsCopyable {311 OnlyBackwardsCopyable* next = nullptr;312 bool canCopy = false;313 OnlyBackwardsCopyable() = default;314 constexpr OnlyBackwardsCopyable& operator=(const OnlyBackwardsCopyable&) {315 assert(canCopy);316 if (next != nullptr)317 next->canCopy = true;318 return *this;319 }320 };321 {322 std::array<OnlyBackwardsCopyable, 3> in{};323 std::array<OnlyBackwardsCopyable, 3> out{};324 out[1].next = &out[0];325 out[2].next = &out[1];326 out[2].canCopy = true;327 auto ret = std::ranges::copy_backward(in, out.end());328 assert(ret.in == in.end());329 assert(ret.out == out.begin());330 assert(out[0].canCopy);331 assert(out[1].canCopy);332 assert(out[2].canCopy);333 }334 {335 std::array<OnlyBackwardsCopyable, 3> in{};336 std::array<OnlyBackwardsCopyable, 3> out{};337 out[1].next = &out[0];338 out[2].next = &out[1];339 out[2].canCopy = true;340 auto ret = std::ranges::copy_backward(in.begin(), in.end(), out.end());341 assert(ret.in == in.end());342 assert(ret.out == out.begin());343 assert(out[0].canCopy);344 assert(out[1].canCopy);345 assert(out[2].canCopy);346 }347 }348 349#if TEST_STD_VER >= 23350 { // Test vector<bool>::iterator optimization351 assert(test_vector_bool(8));352 assert(test_vector_bool(19));353 assert(test_vector_bool(32));354 assert(test_vector_bool(49));355 assert(test_vector_bool(64));356 assert(test_vector_bool(199));357 assert(test_vector_bool(256));358 }359 360 // Validate std::ranges::copy_backward with std::vector<bool> iterators and custom storage types.361 // Ensure that assigned bits hold the intended values, while unassigned bits stay unchanged.362 // Related issue: https://llvm.org/PR131718.363 {364 //// Tests for std::ranges::copy_backward with aligned bits365 366 { // Test the first (partial) word for uint8_t367 using Alloc = sized_allocator<bool, std::uint8_t, std::int8_t>;368 std::vector<bool, Alloc> in(7, false, Alloc(1));369 std::vector<bool, Alloc> out(8, true, Alloc(1));370 std::ranges::copy_backward(std::ranges::subrange(in.begin(), in.begin() + 1), out.begin() + 1);371 assert(out[0] == false);372 for (std::size_t i = 1; i < out.size(); ++i)373 assert(out[i] == true);374 }375 { // Test the last (partial) word for uint8_t376 using Alloc = sized_allocator<bool, std::uint8_t, std::int8_t>;377 std::vector<bool, Alloc> in(8, false, Alloc(1));378 for (std::size_t i = 0; i < in.size(); i += 2)379 in[i] = true;380 std::vector<bool, Alloc> out(8, true, Alloc(1));381 std::ranges::copy_backward(std::ranges::subrange(in.end() - 4, in.end()), out.end());382 for (std::size_t i = 0; i < static_cast<std::size_t>(in.size() - 4); ++i)383 assert(out[i] == true);384 for (std::size_t i = in.size() + 4; i < out.size(); ++i)385 assert(in[i] == out[i]);386 }387 { // Test the middle (whole) words for uint8_t388 using Alloc = sized_allocator<bool, std::uint8_t, std::int8_t>;389 std::vector<bool, Alloc> in(17, false, Alloc(1));390 for (std::size_t i = 0; i < in.size(); i += 2)391 in[i] = true;392 std::vector<bool, Alloc> out(24, true, Alloc(1));393 std::ranges::copy_backward(std::ranges::subrange(in.begin(), in.end()), out.begin() + in.size());394 for (std::size_t i = 0; i < in.size(); ++i)395 assert(in[i] == out[i]);396 for (std::size_t i = in.size(); i < out.size(); ++i)397 assert(out[i] == true);398 }399 400 { // Test the first (partial) word for uint16_t401 using Alloc = sized_allocator<bool, std::uint16_t, std::int16_t>;402 std::vector<bool, Alloc> in(14, false, Alloc(1));403 std::vector<bool, Alloc> out(16, true, Alloc(1));404 std::ranges::copy_backward(std::ranges::subrange(in.begin(), in.begin() + 2), out.begin() + 2);405 assert(out[0] == false);406 assert(out[1] == false);407 for (std::size_t i = 2; i < out.size(); ++i)408 assert(out[i] == true);409 }410 { // Test the last (partial) word for uint16_t411 using Alloc = sized_allocator<bool, std::uint16_t, std::int16_t>;412 std::vector<bool, Alloc> in(16, false, Alloc(1));413 for (std::size_t i = 0; i < in.size(); i += 2)414 in[i] = true;415 std::vector<bool, Alloc> out(16, true, Alloc(1));416 std::ranges::copy_backward(std::ranges::subrange(in.end() - 8, in.end()), out.end());417 for (std::size_t i = 0; i < static_cast<std::size_t>(in.size() - 8); ++i)418 assert(out[i] == true);419 for (std::size_t i = in.size() + 8; i < out.size(); ++i)420 assert(in[i] == out[i]);421 }422 { // Test the middle (whole) words for uint16_t423 using Alloc = sized_allocator<bool, std::uint16_t, std::int16_t>;424 std::vector<bool, Alloc> in(34, false, Alloc(1));425 for (std::size_t i = 0; i < in.size(); i += 2)426 in[i] = true;427 std::vector<bool, Alloc> out(48, true, Alloc(1));428 std::ranges::copy_backward(std::ranges::subrange(in.begin(), in.end()), out.begin() + in.size());429 for (std::size_t i = 0; i < in.size(); ++i)430 assert(in[i] == out[i]);431 for (std::size_t i = in.size(); i < out.size(); ++i)432 assert(out[i] == true);433 }434 435 //// Tests for std::ranges::copy_backward with unaligned bits436 437 { // Test the first (partial) word for uint8_t438 using Alloc = sized_allocator<bool, std::uint8_t, std::int8_t>;439 std::vector<bool, Alloc> in(8, false, Alloc(1));440 std::vector<bool, Alloc> out(8, true, Alloc(1));441 std::ranges::copy_backward(std::ranges::subrange(in.begin(), in.begin() + 1), out.begin() + 1);442 assert(out[0] == false);443 for (std::size_t i = 1; i < out.size(); ++i)444 assert(out[i] == true);445 }446 { // Test the last (partial) word for uint8_t447 using Alloc = sized_allocator<bool, std::uint8_t, std::int8_t>;448 std::vector<bool, Alloc> in(8, false, Alloc(1));449 std::vector<bool, Alloc> out(8, true, Alloc(1));450 std::ranges::copy_backward(std::ranges::subrange(in.end() - 1, in.end()), out.begin() + 1);451 assert(out[0] == false);452 for (std::size_t i = 1; i < out.size(); ++i)453 assert(out[i] == true);454 }455 { // Test the middle (whole) words for uint8_t456 using Alloc = sized_allocator<bool, std::uint8_t, std::int8_t>;457 std::vector<bool, Alloc> in(16, false, Alloc(1));458 for (std::size_t i = 0; i < in.size(); i += 2)459 in[i] = true;460 std::vector<bool, Alloc> out(17, true, Alloc(1));461 std::ranges::copy_backward(std::ranges::subrange(in.begin(), in.end()), out.end());462 assert(out[0] == true);463 for (std::size_t i = 0; i < in.size(); ++i)464 assert(in[i] == out[i + 1]);465 }466 467 { // Test the first (partial) word for uint16_t468 using Alloc = sized_allocator<bool, std::uint16_t, std::int16_t>;469 std::vector<bool, Alloc> in(16, false, Alloc(1));470 std::vector<bool, Alloc> out(16, true, Alloc(1));471 std::ranges::copy_backward(std::ranges::subrange(in.begin(), in.begin() + 2), out.begin() + 2);472 assert(out[0] == false);473 assert(out[1] == false);474 for (std::size_t i = 2; i < out.size(); ++i)475 assert(out[i] == true);476 }477 { // Test the last (partial) word for uint16_t478 using Alloc = sized_allocator<bool, std::uint16_t, std::int16_t>;479 std::vector<bool, Alloc> in(16, false, Alloc(1));480 std::vector<bool, Alloc> out(16, true, Alloc(1));481 std::ranges::copy_backward(std::ranges::subrange(in.end() - 2, in.end()), out.begin() + 2);482 assert(out[0] == false);483 assert(out[1] == false);484 for (std::size_t i = 2; i < out.size(); ++i)485 assert(out[i] == true);486 }487 { // Test the middle (whole) words for uint16_t488 using Alloc = sized_allocator<bool, std::uint16_t, std::int16_t>;489 std::vector<bool, Alloc> in(32, false, Alloc(1));490 for (std::size_t i = 0; i < in.size(); i += 2)491 in[i] = true;492 std::vector<bool, Alloc> out(33, true, Alloc(1));493 std::ranges::copy_backward(std::ranges::subrange(in.begin(), in.end()), out.end());494 assert(out[0] == true);495 for (std::size_t i = 0; i < in.size(); ++i)496 assert(in[i] == out[i + 1]);497 }498 }499#endif500 501 return true;502}503 504int main(int, char**) {505 test();506 static_assert(test());507 508 return 0;509}510