399 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 13// template<input_iterator I, sentinel_for<I> S, weakly_incrementable O>14// requires indirectly_copyable<I, O>15// constexpr ranges::copy_result<I, O> ranges::copy(I first, S last, O result);16// template<input_range R, weakly_incrementable O>17// requires indirectly_copyable<iterator_t<R>, O>18// constexpr ranges::copy_result<borrowed_iterator_t<R>, O> ranges::copy(R&& r, O result);19 20#include <algorithm>21#include <array>22#include <cassert>23#include <deque>24#include <ranges>25#include <vector>26 27#include "almost_satisfies_types.h"28#include "sized_allocator.h"29#include "test_iterators.h"30#include "test_macros.h"31#include "type_algorithms.h"32 33template <class In, class Out = In, class Sent = sentinel_wrapper<In>>34concept HasCopyIt = requires(In in, Sent sent, Out out) { std::ranges::copy(in, sent, out); };35 36static_assert(HasCopyIt<int*>);37static_assert(!HasCopyIt<InputIteratorNotDerivedFrom>);38static_assert(!HasCopyIt<InputIteratorNotIndirectlyReadable>);39static_assert(!HasCopyIt<InputIteratorNotInputOrOutputIterator>);40static_assert(!HasCopyIt<int*, WeaklyIncrementableNotMovable>);41struct NotIndirectlyCopyable {};42static_assert(!HasCopyIt<int*, NotIndirectlyCopyable*>);43static_assert(!HasCopyIt<int*, int*, SentinelForNotSemiregular>);44static_assert(!HasCopyIt<int*, int*, SentinelForNotWeaklyEqualityComparableWith>);45 46template <class Range, class Out>47concept HasCopyR = requires(Range range, Out out) { std::ranges::copy(range, out); };48 49static_assert(HasCopyR<std::array<int, 10>, int*>);50static_assert(!HasCopyR<InputRangeNotDerivedFrom, int*>);51static_assert(!HasCopyR<InputRangeNotIndirectlyReadable, int*>);52static_assert(!HasCopyR<InputRangeNotInputOrOutputIterator, int*>);53static_assert(!HasCopyR<WeaklyIncrementableNotMovable, int*>);54static_assert(!HasCopyR<UncheckedRange<NotIndirectlyCopyable*>, int*>);55static_assert(!HasCopyR<InputRangeNotSentinelSemiregular, int*>);56static_assert(!HasCopyR<InputRangeNotSentinelEqualityComparableWith, int*>);57 58static_assert(std::is_same_v<std::ranges::copy_result<int, long>, std::ranges::in_out_result<int, long>>);59 60// clang-format off61template <class In, class Out, class Sent = In>62constexpr void test_iterators() {63 { // simple test64 {65 std::array in{1, 2, 3, 4};66 std::array<int, 4> out;67 std::same_as<std::ranges::in_out_result<In, Out>> auto ret =68 std::ranges::copy(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 in{1, 2, 3, 4};75 std::array<int, 4> out;76 auto range = std::ranges::subrange(In(in.data()), Sent(In(in.data() + in.size())));77 std::same_as<std::ranges::in_out_result<In, Out>> auto ret = std::ranges::copy(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 { // check that an empty range works85 {86 std::array<int, 0> in;87 std::array<int, 0> out;88 auto ret = std::ranges::copy(In(in.data()), Sent(In(in.data() + in.size())), Out(out.data()));89 assert(base(ret.in) == in.data());90 assert(base(ret.out) == out.data());91 }92 {93 std::array<int, 0> in;94 std::array<int, 0> out;95 auto range = std::ranges::subrange(In(in.data()), Sent(In(in.data() + in.size())));96 auto ret = std::ranges::copy(range, Out(out.data()));97 assert(base(ret.in) == in.data());98 assert(base(ret.out) == out.data());99 }100 }101}102// clang-format on103 104#if TEST_STD_VER >= 23105constexpr bool test_vector_bool(std::size_t N) {106 std::vector<bool> in(N, false);107 for (std::size_t i = 0; i < N; i += 2)108 in[i] = true;109 110 { // Test copy with aligned bytes111 std::vector<bool> out(N);112 std::ranges::copy(in, out.begin());113 assert(in == out);114 }115 { // Test copy with unaligned bytes116 std::vector<bool> out(N + 8);117 std::ranges::copy(in, out.begin() + 4);118 for (std::size_t i = 0; i < N; ++i)119 assert(out[i + 4] == in[i]);120 }121 122 return true;123}124#endif125 126constexpr bool test() {127 types::for_each(types::forward_iterator_list<int*>{}, []<class Out>() {128 test_iterators<cpp20_input_iterator<int*>, Out, sentinel_wrapper<cpp20_input_iterator<int*>>>();129 test_iterators<ProxyIterator<cpp20_input_iterator<int*>>,130 ProxyIterator<Out>,131 sentinel_wrapper<ProxyIterator<cpp20_input_iterator<int*>>>>();132 133 types::for_each(types::forward_iterator_list<int*>{}, []<class In>() {134 test_iterators<In, Out>();135 test_iterators<In, Out, sized_sentinel<In>>();136 test_iterators<In, Out, sentinel_wrapper<In>>();137 138 test_iterators<ProxyIterator<In>, ProxyIterator<Out>>();139 test_iterators<ProxyIterator<In>, ProxyIterator<Out>, sized_sentinel<ProxyIterator<In>>>();140 test_iterators<ProxyIterator<In>, ProxyIterator<Out>, sentinel_wrapper<ProxyIterator<In>>>();141 });142 });143 144 { // check that ranges::dangling is returned145 std::array<int, 4> out;146 std::same_as<std::ranges::in_out_result<std::ranges::dangling, int*>> auto ret =147 std::ranges::copy(std::array{1, 2, 3, 4}, out.data());148 assert(ret.out == out.data() + 4);149 assert((out == std::array{1, 2, 3, 4}));150 }151 152 { // check that an iterator is returned with a borrowing range153 std::array in{1, 2, 3, 4};154 std::array<int, 4> out;155 std::same_as<std::ranges::in_out_result<std::array<int, 4>::iterator, int*>> auto ret =156 std::ranges::copy(std::views::all(in), out.data());157 assert(ret.in == in.end());158 assert(ret.out == out.data() + 4);159 assert(in == out);160 }161 162 { // check that every element is copied exactly once163 struct CopyOnce {164 bool copied = false;165 constexpr CopyOnce() = default;166 constexpr CopyOnce(const CopyOnce& other) = delete;167 constexpr CopyOnce& operator=(const CopyOnce& other) {168 assert(!other.copied);169 copied = true;170 return *this;171 }172 };173 {174 std::array<CopyOnce, 4> in{};175 std::array<CopyOnce, 4> out{};176 auto ret = std::ranges::copy(in.begin(), in.end(), out.begin());177 assert(ret.in == in.end());178 assert(ret.out == out.end());179 assert(std::all_of(out.begin(), out.end(), [](const auto& e) { return e.copied; }));180 }181 {182 std::array<CopyOnce, 4> in{};183 std::array<CopyOnce, 4> out{};184 auto ret = std::ranges::copy(in, out.begin());185 assert(ret.in == in.end());186 assert(ret.out == out.end());187 assert(std::all_of(out.begin(), out.end(), [](const auto& e) { return e.copied; }));188 }189 }190 191 { // check that the range is copied forwards192 struct OnlyForwardsCopyable {193 OnlyForwardsCopyable* next = nullptr;194 bool canCopy = false;195 OnlyForwardsCopyable() = default;196 constexpr OnlyForwardsCopyable& operator=(const OnlyForwardsCopyable&) {197 assert(canCopy);198 if (next != nullptr)199 next->canCopy = true;200 return *this;201 }202 };203 {204 std::array<OnlyForwardsCopyable, 3> in{};205 std::array<OnlyForwardsCopyable, 3> out{};206 out[0].next = &out[1];207 out[1].next = &out[2];208 out[0].canCopy = true;209 auto ret = std::ranges::copy(in.begin(), in.end(), out.begin());210 assert(ret.in == in.end());211 assert(ret.out == out.end());212 assert(out[0].canCopy);213 assert(out[1].canCopy);214 assert(out[2].canCopy);215 }216 {217 std::array<OnlyForwardsCopyable, 3> in{};218 std::array<OnlyForwardsCopyable, 3> out{};219 out[0].next = &out[1];220 out[1].next = &out[2];221 out[0].canCopy = true;222 auto ret = std::ranges::copy(in, out.begin());223 assert(ret.in == in.end());224 assert(ret.out == out.end());225 assert(out[0].canCopy);226 assert(out[1].canCopy);227 assert(out[2].canCopy);228 }229 }230 231#if TEST_STD_VER >= 23232 { // Test vector<bool>::iterator optimization233 assert(test_vector_bool(8));234 assert(test_vector_bool(19));235 assert(test_vector_bool(32));236 assert(test_vector_bool(49));237 assert(test_vector_bool(64));238 assert(test_vector_bool(199));239 assert(test_vector_bool(256));240 }241 242 // Validate std::ranges::copy with std::vector<bool> iterators and custom storage types.243 // Ensure that assigned bits hold the intended values, while unassigned bits stay unchanged.244 // Related issue: https://llvm.org/PR131692.245 {246 //// Tests for std::ranges::copy with aligned bits247 248 { // Test the first (partial) word for uint8_t249 using Alloc = sized_allocator<bool, std::uint8_t, std::int8_t>;250 std::vector<bool, Alloc> in(8, false, Alloc(1));251 std::vector<bool, Alloc> out(8, true, Alloc(1));252 std::ranges::copy(std::ranges::subrange(in.begin() + 1, in.begin() + 2), out.begin() + 1); // out[1] = false253 assert(out[1] == false);254 for (std::size_t i = 0; i < out.size(); ++i) // Ensure that unassigned bits remain unchanged255 if (i != 1)256 assert(out[i] == true);257 }258 { // Test the last (partial) word for uint8_t259 using Alloc = sized_allocator<bool, std::uint8_t, std::int8_t>;260 std::vector<bool, Alloc> in(8, false, Alloc(1));261 std::vector<bool, Alloc> out(8, true, Alloc(1));262 std::ranges::copy(std::ranges::subrange(in.begin(), in.begin() + 1), out.begin()); // out[0] = false263 assert(out[0] == false);264 for (std::size_t i = 1; i < out.size(); ++i) // Ensure that unassigned bits remain unchanged265 assert(out[i] == true);266 }267 { // Test middle (whole) words for uint8_t268 using Alloc = sized_allocator<bool, std::uint8_t, std::int8_t>;269 std::vector<bool, Alloc> in(32, true, Alloc(1));270 for (std::size_t i = 0; i < in.size(); i += 2)271 in[i] = false;272 std::vector<bool, Alloc> out(32, false, Alloc(1));273 std::ranges::copy(std::ranges::subrange(in.begin() + 4, in.end() - 4), out.begin() + 4);274 for (std::size_t i = 4; i < static_cast<std::size_t>(in.size() - 4); ++i)275 assert(in[i] == out[i]);276 for (std::size_t i = 0; i < 4; ++i)277 assert(out[i] == false);278 for (std::size_t i = 28; i < out.size(); ++i)279 assert(out[i] == false);280 }281 282 { // Test the first (partial) word for uint16_t283 using Alloc = sized_allocator<bool, std::uint16_t, std::int16_t>;284 std::vector<bool, Alloc> in(16, false, Alloc(1));285 std::vector<bool, Alloc> out(16, true, Alloc(1));286 std::ranges::copy(std::ranges::subrange(in.begin() + 1, in.begin() + 3), out.begin() + 1); // out[1..2] = false287 assert(out[1] == false);288 assert(out[2] == false);289 for (std::size_t i = 0; i < out.size(); ++i) // Ensure that unassigned bits remain unchanged290 if (i != 1 && i != 2)291 assert(out[i] == true);292 }293 { // Test the last (partial) word for uint16_t294 using Alloc = sized_allocator<bool, std::uint16_t, std::int16_t>;295 std::vector<bool, Alloc> in(16, false, Alloc(1));296 std::vector<bool, Alloc> out(16, true, Alloc(1));297 std::ranges::copy(std::ranges::subrange(in.begin(), in.begin() + 2), out.begin()); // out[0..1] = false298 assert(out[0] == false);299 assert(out[1] == false);300 for (std::size_t i = 2; i < out.size(); ++i) // Ensure that unassigned bits remain unchanged301 assert(out[i] == true);302 }303 { // Test middle (whole) words for uint16_t304 using Alloc = sized_allocator<bool, std::uint16_t, std::int16_t>;305 std::vector<bool, Alloc> in(64, true, Alloc(1));306 for (std::size_t i = 0; i < in.size(); i += 2)307 in[i] = false;308 std::vector<bool, Alloc> out(64, false, Alloc(1));309 std::ranges::copy(std::ranges::subrange(in.begin() + 8, in.end() - 8), out.begin() + 8);310 for (std::size_t i = 8; i < static_cast<std::size_t>(in.size() - 8); ++i)311 assert(in[i] == out[i]);312 for (std::size_t i = 0; i < 8; ++i)313 assert(out[i] == false);314 for (std::size_t i = static_cast<std::size_t>(out.size() - 8); i < out.size(); ++i)315 assert(out[i] == false);316 }317 318 //// Tests for std::ranges::copy with unaligned bits319 320 { // Test the first (partial) word for uint8_t321 using Alloc = sized_allocator<bool, std::uint8_t, std::int8_t>;322 std::vector<bool, Alloc> in(8, false, Alloc(1));323 std::vector<bool, Alloc> out(8, true, Alloc(1));324 std::ranges::copy(std::ranges::subrange(in.begin() + 7, in.end()), out.begin()); // out[0] = false325 assert(out[0] == false);326 for (std::size_t i = 1; i < out.size(); ++i) // Ensure that unassigned bits remain unchanged327 assert(out[i] == true);328 }329 { // Test the last (partial) word for uint8_t330 using Alloc = sized_allocator<bool, std::uint8_t, std::int8_t>;331 std::vector<bool, Alloc> in(8, false, Alloc(1));332 std::vector<bool, Alloc> out(8, true, Alloc(1));333 std::ranges::copy(std::ranges::subrange(in.begin(), in.begin() + 1), out.begin() + 2); // out[2] = false334 assert(out[2] == false);335 for (std::size_t i = 1; i < out.size(); ++i) // Ensure that unassigned bits remain unchanged336 if (i != 2)337 assert(out[i] == true);338 }339 { // Test middle (whole) words for uint8_t340 using Alloc = sized_allocator<bool, std::uint8_t, std::int8_t>;341 std::vector<bool, Alloc> in(36, true, Alloc(1));342 for (std::size_t i = 0; i < in.size(); i += 2)343 in[i] = false;344 std::vector<bool, Alloc> out(40, false, Alloc(1));345 std::ranges::copy(std::ranges::subrange(in.begin(), in.end()), out.begin() + 4);346 for (std::size_t i = 0; i < in.size(); ++i)347 assert(in[i] == out[i + 4]);348 for (std::size_t i = 0; i < 4; ++i)349 assert(out[i] == false);350 }351 352 { // Test the first (partial) word for uint16_t353 using Alloc = sized_allocator<bool, std::uint16_t, std::int16_t>;354 std::vector<bool, Alloc> in(16, false, Alloc(1));355 std::vector<bool, Alloc> out(16, true, Alloc(1));356 std::ranges::copy(std::ranges::subrange(in.begin() + 14, in.end()), out.begin()); // out[0..1] = false357 assert(out[0] == false);358 assert(out[1] == false);359 for (std::size_t i = 2; i < out.size(); ++i) // Ensure that unassigned bits remain unchanged360 assert(out[i] == true);361 }362 { // Test the last (partial) word for uint16_t363 using Alloc = sized_allocator<bool, std::uint16_t, std::int16_t>;364 std::vector<bool, Alloc> in(16, false, Alloc(1));365 std::vector<bool, Alloc> out(16, true, Alloc(1));366 std::ranges::copy(std::ranges::subrange(in.begin(), in.begin() + 2), out.begin() + 1); // out[1..2] = false367 assert(out[1] == false);368 assert(out[2] == false);369 for (std::size_t i = 0; i < out.size(); ++i) // Ensure that unassigned bits remain unchanged370 if (i != 1 && i != 2)371 assert(out[i] == true);372 }373 { // Test middle (whole) words for uint16_t374 using Alloc = sized_allocator<bool, std::uint16_t, std::int16_t>;375 std::vector<bool, Alloc> in(72, true, Alloc(1));376 for (std::size_t i = 0; i < in.size(); i += 2)377 in[i] = false;378 std::vector<bool, Alloc> out(80, false, Alloc(1));379 std::ranges::copy(std::ranges::subrange(in.begin(), in.end()), out.begin() + 4);380 for (std::size_t i = 0; i < in.size(); ++i)381 assert(in[i] == out[i + 4]);382 for (std::size_t i = 0; i < 4; ++i)383 assert(out[i] == false);384 for (std::size_t i = in.size() + 4; i < out.size(); ++i)385 assert(out[i] == false);386 }387 }388#endif389 390 return true;391}392 393int main(int, char**) {394 test();395 static_assert(test());396 397 return 0;398}399