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_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 off
61template <class In, class Out, class Sent = In>
62constexpr void test_iterators() {
63 { // simple test
64 {
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 works
85 {
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 on
103
104#if TEST_STD_VER >= 23
105constexpr 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 bytes
111 std::vector<bool> out(N);
112 std::ranges::copy(in, out.begin());
113 assert(in == out);
114 }
115 { // Test copy with unaligned bytes
116 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#endif
125
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 returned
145 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 range
153 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 once
163 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 forwards
192 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 >= 23
232 { // Test vector<bool>::iterator optimization
233 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://github.com/llvm/llvm-project/issues/131692.
245 {
246 //// Tests for std::ranges::copy with aligned bits
247
248 { // Test the first (partial) word for uint8_t
249 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] = false
253 assert(out[1] == false);
254 for (std::size_t i = 0; i < out.size(); ++i) // Ensure that unassigned bits remain unchanged
255 if (i != 1)
256 assert(out[i] == true);
257 }
258 { // Test the last (partial) word for uint8_t
259 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] = false
263 assert(out[0] == false);
264 for (std::size_t i = 1; i < out.size(); ++i) // Ensure that unassigned bits remain unchanged
265 assert(out[i] == true);
266 }
267 { // Test middle (whole) words for uint8_t
268 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_t
283 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] = false
287 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 unchanged
290 if (i != 1 && i != 2)
291 assert(out[i] == true);
292 }
293 { // Test the last (partial) word for uint16_t
294 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] = false
298 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 unchanged
301 assert(out[i] == true);
302 }
303 { // Test middle (whole) words for uint16_t
304 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 bits
319
320 { // Test the first (partial) word for uint8_t
321 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] = false
325 assert(out[0] == false);
326 for (std::size_t i = 1; i < out.size(); ++i) // Ensure that unassigned bits remain unchanged
327 assert(out[i] == true);
328 }
329 { // Test the last (partial) word for uint8_t
330 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] = false
334 assert(out[2] == false);
335 for (std::size_t i = 1; i < out.size(); ++i) // Ensure that unassigned bits remain unchanged
336 if (i != 2)
337 assert(out[i] == true);
338 }
339 { // Test middle (whole) words for uint8_t
340 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_t
353 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] = false
357 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 unchanged
360 assert(out[i] == true);
361 }
362 { // Test the last (partial) word for uint16_t
363 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] = false
367 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 unchanged
370 if (i != 1 && i != 2)
371 assert(out[i] == true);
372 }
373 { // Test middle (whole) words for uint16_t
374 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#endif
389
390 return true;
391}
392
393int main(int, char**) {
394 test();
395 static_assert(test());
396
397 return 0;
398}
399

source code of libcxx/test/std/algorithms/alg.modifying.operations/alg.copy/ranges.copy.pass.cpp