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 // UNSUPPORTED: c++03, c++11, c++14, c++17
10 // In the modules build, adding another overload of `memmove` doesn't work.
11 // UNSUPPORTED: clang-modules-build
12 // GCC complains about "ambiguating" `__builtin_memmove`.
13 // UNSUPPORTED: gcc
14
15 // <algorithm>
16
17 // These tests check that `std::copy` and `std::move` (including their variations like `copy_n`) forward to
18 // `memmove` when possible.
19
20 #include <cstddef>
21
22 struct Foo {
23 int i = 0;
24
25 Foo() = default;
FooFoo26 Foo(int set_i) : i(set_i) {}
27
28 friend bool operator==(const Foo&, const Foo&) = default;
29 };
30
31 static bool memmove_called = false;
32
33 // This template is a better match than the actual `builtin_memmove` (it can match the pointer type exactly, without an
34 // implicit conversion to `void*`), so it should hijack the call inside `std::copy` and similar algorithms if it's made.
35 template <class Dst, class Src>
__builtin_memmove(Dst * dst,Src * src,std::size_t count)36 constexpr void* __builtin_memmove(Dst* dst, Src* src, std::size_t count) {
37 memmove_called = true;
38 return __builtin_memmove(static_cast<void*>(dst), static_cast<const void*>(src), count);
39 }
40
41 #include <algorithm>
42 #include <cassert>
43 #include <cstdint>
44 #include <iterator>
45 #include <limits>
46 #include <ranges>
47 #include <type_traits>
48
49 #include "test_iterators.h"
50
51 static_assert(std::is_trivially_copyable_v<Foo>);
52
53 // To test pointers to functions.
Func()54 void Func() {}
55 using FuncPtr = decltype(&Func);
56
57 // To test pointers to members.
58 struct S {
59 int mem_obj = 0;
MemFuncS60 void MemFunc() {}
61 };
62 using MemObjPtr = decltype(&S::mem_obj);
63 using MemFuncPtr = decltype(&S::MemFunc);
64
65 // To test bitfields.
66 struct BitfieldS {
67 unsigned char b1 : 3;
68 unsigned char : 2;
69 unsigned char b2 : 5;
70 friend bool operator==(const BitfieldS&, const BitfieldS&) = default;
71 };
72
73 // To test non-default alignment.
74 struct AlignedS {
75 alignas(64) int x;
76 alignas(8) int y;
77 friend bool operator==(const AlignedS&, const AlignedS&) = default;
78 };
79
80 template <class T>
make(int from)81 T make(int from) {
82 return T(from);
83 }
84
85 template <class T>
86 requires (std::is_pointer_v<T> && !std::is_function_v<std::remove_pointer_t<T>>)
make(int i)87 T make(int i) {
88 static std::remove_pointer_t<T> arr[8];
89 return arr + i;
90 }
91
92 template <class T>
93 requires std::same_as<T, FuncPtr>
make(int)94 FuncPtr make(int) {
95 return &Func;
96 }
97
98 template <class T>
99 requires std::same_as<T, MemObjPtr>
make(int)100 MemObjPtr make(int) {
101 return &S::mem_obj;
102 }
103
104 template <class T>
105 requires std::same_as<T, MemFuncPtr>
make(int)106 MemFuncPtr make(int) {
107 return &S::MemFunc;
108 }
109
110 template <class T>
111 requires std::same_as<T, BitfieldS>
make(int x)112 BitfieldS make(int x) {
113 BitfieldS result = {};
114 result.b1 = x;
115 result.b2 = x;
116 return result;
117 }
118
119 template <class T>
120 requires std::same_as<T, AlignedS>
make(int x)121 AlignedS make(int x) {
122 AlignedS result;
123 result.x = x;
124 result.y = x;
125 return result;
126 }
127
128 template <class InIter, template <class> class SentWrapper, class OutIter, class Func>
test_one(Func func)129 void test_one(Func func) {
130 using From = std::iter_value_t<InIter>;
131 using To = std::iter_value_t<OutIter>;
132
133 // Normal case.
134 {
135 const std::size_t N = 4;
136
137 From input[N] = {make<From>(1), make<From>(2), make<From>(3), make<From>(4)};
138 To output[N];
139
140 auto in = InIter(input);
141 auto in_end = InIter(input + N);
142 auto sent = SentWrapper<decltype(in_end)>(in_end);
143 auto out = OutIter(output);
144
145 assert(!memmove_called);
146 func(in, sent, out, N);
147 assert(memmove_called);
148 memmove_called = false;
149
150 assert(std::equal(input, input + N, output, [](const From& lhs, const To& rhs) {
151 // Prevents warnings/errors due to mismatched signed-ness.
152 if constexpr (std::convertible_to<From, To>) {
153 return static_cast<To>(lhs) == rhs;
154 } else if constexpr (std::convertible_to<To, From>) {
155 return lhs == static_cast<From>(rhs);
156 }
157 }));
158 }
159 }
160
161 template <class InIter, template <class> class SentWrapper, class OutIter>
test_copy_and_move()162 void test_copy_and_move() {
163 // Classic.
164 if constexpr (std::same_as<InIter, SentWrapper<InIter>>) {
165 test_one<InIter, SentWrapper, OutIter>([](auto first, auto last, auto out, std::size_t) {
166 std::copy(first, last, out);
167 });
168 test_one<InIter, SentWrapper, OutIter>([](auto first, auto last, auto out, std::size_t n) {
169 std::copy_backward(first, last, out + n);
170 });
171 test_one<InIter, SentWrapper, OutIter>([](auto first, auto, auto out, std::size_t n) {
172 std::copy_n(first, n, out);
173 });
174 test_one<InIter, SentWrapper, OutIter>([](auto first, auto last, auto out, std::size_t) {
175 std::move(first, last, out);
176 });
177 test_one<InIter, SentWrapper, OutIter>([](auto first, auto last, auto out, std::size_t n) {
178 std::move_backward(first, last, out + n);
179 });
180 }
181
182 // Ranges.
183 test_one<InIter, SentWrapper, OutIter>([](auto first, auto last, auto out, std::size_t) {
184 std::ranges::copy(first, last, out);
185 });
186 test_one<InIter, SentWrapper, OutIter>([](auto first, auto last, auto out, std::size_t n) {
187 std::ranges::copy_backward(first, last, out + n);
188 });
189 test_one<InIter, SentWrapper, OutIter>([](auto first, auto, auto out, std::size_t n) {
190 std::ranges::copy_n(first, n, out);
191 });
192 test_one<InIter, SentWrapper, OutIter>([](auto first, auto last, auto out, std::size_t) {
193 std::ranges::move(first, last, out);
194 });
195 test_one<InIter, SentWrapper, OutIter>([](auto first, auto last, auto out, std::size_t n) {
196 std::ranges::move_backward(first, last, out + n);
197 });
198 }
199
200 template <class From, class To, template <class> class SentWrapper, bool BothDirections = !std::same_as<From, To>>
test_all_permutations_from_to_sent()201 void test_all_permutations_from_to_sent() {
202 test_copy_and_move<From*, SentWrapper, To*>();
203 test_copy_and_move<contiguous_iterator<From*>, SentWrapper, To*>();
204 test_copy_and_move<From*, SentWrapper, contiguous_iterator<To*>>();
205 test_copy_and_move<contiguous_iterator<From*>, SentWrapper, contiguous_iterator<To*>>();
206
207 if (BothDirections) {
208 test_copy_and_move<To*, SentWrapper, From*>();
209 test_copy_and_move<contiguous_iterator<To*>, SentWrapper, From*>();
210 test_copy_and_move<To*, SentWrapper, contiguous_iterator<From*>>();
211 test_copy_and_move<contiguous_iterator<To*>, SentWrapper, contiguous_iterator<From*>>();
212 }
213 }
214
test_different_signedness()215 void test_different_signedness() {
216 auto check = [](auto alg) {
217 // Signed -> unsigned.
218 {
219 constexpr int N = 3;
220 constexpr auto min_value = std::numeric_limits<int>::min();
221
222 int in[N] = {-1, min_value / 2, min_value};
223 unsigned int out[N];
224 unsigned int expected[N] = {
225 static_cast<unsigned int>(in[0]),
226 static_cast<unsigned int>(in[1]),
227 static_cast<unsigned int>(in[2]),
228 };
229
230 assert(!memmove_called);
231 alg(in, in + N, out, N);
232 assert(memmove_called);
233 memmove_called = false;
234
235 assert(std::equal(out, out + N, expected));
236 }
237
238 // Unsigned -> signed.
239 {
240 constexpr int N = 3;
241 constexpr auto max_signed = std::numeric_limits<int>::max();
242 constexpr auto max_unsigned = std::numeric_limits<unsigned int>::max();
243
244 unsigned int in[N] = {static_cast<unsigned int>(max_signed) + 1, max_unsigned / 2, max_unsigned};
245 int out[N];
246 int expected[N] = {
247 static_cast<int>(in[0]),
248 static_cast<int>(in[1]),
249 static_cast<int>(in[2]),
250 };
251
252 assert(!memmove_called);
253 alg(in, in + N, out, N);
254 assert(memmove_called);
255 memmove_called = false;
256
257 assert(std::equal(out, out + N, expected));
258 }
259 };
260
261 check([](auto first, auto last, auto out, std::size_t) {
262 std::copy(first, last, out);
263 });
264 check([](auto first, auto last, auto out, std::size_t n) {
265 std::copy_backward(first, last, out + n);
266 });
267 check([](auto first, auto, auto out, std::size_t n) {
268 std::copy_n(first, n, out);
269 });
270 check([](auto first, auto last, auto out, std::size_t) {
271 std::move(first, last, out);
272 });
273 check([](auto first, auto last, auto out, std::size_t n) {
274 std::move_backward(first, last, out + n);
275 });
276
277 // Ranges.
278 check([](auto first, auto last, auto out, std::size_t) {
279 std::ranges::copy(first, last, out);
280 });
281 check([](auto first, auto last, auto out, std::size_t n) {
282 std::ranges::copy_backward(first, last, out + n);
283 });
284 check([](auto first, auto, auto out, std::size_t n) {
285 std::ranges::copy_n(first, n, out);
286 });
287 check([](auto first, auto last, auto out, std::size_t) {
288 std::ranges::move(first, last, out);
289 });
290 check([](auto first, auto last, auto out, std::size_t n) {
291 std::ranges::move_backward(first, last, out + n);
292 });
293 }
294
test()295 void test() {
296 // Built-in.
297 test_all_permutations_from_to_sent<int, int, std::type_identity_t>();
298 // User-defined.
299 test_all_permutations_from_to_sent<Foo, Foo, std::type_identity_t>();
300
301 // Conversions.
302 test_all_permutations_from_to_sent<char32_t, std::int32_t, sized_sentinel>();
303 test_all_permutations_from_to_sent<std::int32_t, std::uint32_t, sized_sentinel>();
304 // Conversion from `bool` to `char` invokes the optimization (the set of values for `char` is a superset of the set of
305 // values for `bool`), but the other way round cannot.
306 test_all_permutations_from_to_sent<bool, char, sized_sentinel, /*BothDirections=*/false>();
307
308 // Copying between regular pointers.
309 test_copy_and_move<int**, std::type_identity_t, int**>();
310
311 // Copying between pointers to functions.
312 test_copy_and_move<FuncPtr*, std::type_identity_t, FuncPtr*>();
313
314 // Copying between pointers to members.
315 test_copy_and_move<MemObjPtr*, std::type_identity_t, MemObjPtr*>();
316 test_copy_and_move<MemFuncPtr*, std::type_identity_t, MemFuncPtr*>();
317
318 // Copying structs with bitfields.
319 test_copy_and_move<BitfieldS*, std::type_identity_t, BitfieldS*>();
320
321 // Copying objects with non-default alignment.
322 test_copy_and_move<AlignedS*, std::type_identity_t, AlignedS*>();
323
324 // Copying integers with different signedness produces the same results as built-in assignment.
325 test_different_signedness();
326 }
327
main(int,char **)328 int main(int, char**) {
329 test();
330 // The test relies on a global variable, so it cannot be made `constexpr`; the `memmove` optimization is not used in
331 // `constexpr` mode anyway.
332
333 return 0;
334 }
335