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 
11 // <algorithm>
12 
13 // template<input_range R1, input_range R2, weakly_incrementable O,
14 //          copy_constructible F, class Proj1 = identity, class Proj2 = identity>
15 //   requires indirectly_writable<O, indirect_result_t<F&, projected<iterator_t<R1>, Proj1>,
16 //                                          projected<iterator_t<R2>, Proj2>>>
17 //   constexpr ranges::binary_transform_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>, O>
18 //     ranges::transform(R1&& r1, R2&& r2, O result,
19 //                       F binary_op, Proj1 proj1 = {}, Proj2 proj2 = {});
20 
21 // The iterator overloads are tested in ranges.tranform.binary.iterator.pass.cpp.
22 
23 #include <algorithm>
24 #include <array>
25 #include <cassert>
26 #include <functional>
27 #include <ranges>
28 
29 #include "test_iterators.h"
30 #include "almost_satisfies_types.h"
31 
32 struct BinaryFunc {
33   int operator()(int, int);
34 };
35 
36 template <class Range>
37 concept HasTranformR = requires(Range r, int* out) { std::ranges::transform(r, r, out, BinaryFunc{}); };
38 
39 static_assert(HasTranformR<std::array<int, 1>>);
40 static_assert(!HasTranformR<int>);
41 static_assert(!HasTranformR<InputRangeNotDerivedFrom>);
42 static_assert(!HasTranformR<InputRangeNotIndirectlyReadable>);
43 static_assert(!HasTranformR<InputRangeNotInputOrOutputIterator>);
44 static_assert(!HasTranformR<InputRangeNotSentinelSemiregular>);
45 static_assert(!HasTranformR<InputRangeNotSentinelEqualityComparableWith>);
46 
47 template <class It>
48 concept HasTransformOut = requires(int* it, int* sent, It out, std::array<int, 2> range) {
49   std::ranges::transform(range, range, out, BinaryFunc{});
50 };
51 static_assert(HasTransformOut<int*>);
52 static_assert(!HasTransformOut<WeaklyIncrementableNotMovable>);
53 
54 // check indirectly_readable
55 static_assert(HasTransformOut<char*>);
56 static_assert(!HasTransformOut<int**>);
57 
58 struct MoveOnlyFunctor {
59   MoveOnlyFunctor(const MoveOnlyFunctor&) = delete;
60   MoveOnlyFunctor(MoveOnlyFunctor&&)      = default;
61   int operator()(int, int);
62 };
63 
64 template <class Func>
65 concept HasTransformFuncBinary = requires(int* it, int* sent, int* out, std::array<int, 2> range, Func func) {
66   std::ranges::transform(range, range, out, func);
67 };
68 static_assert(HasTransformFuncBinary<BinaryFunc>);
69 static_assert(!HasTransformFuncBinary<MoveOnlyFunctor>);
70 
71 static_assert(std::is_same_v<std::ranges::binary_transform_result<int, long, char>,
72                              std::ranges::in_in_out_result<int, long, char>>);
73 
74 // clang-format off
75 template <class In1, class In2, class Out, class Sent1, class Sent2>
76 constexpr bool test_iterators() {
77   { // simple
78     int a[] = {1, 2, 3, 4, 5};
79     int b[] = {5, 4, 3, 2, 1};
80     int c[5];
81 
82     auto range1 = std::ranges::subrange(In1(a), Sent1(In1(a + 5)));
83     auto range2 = std::ranges::subrange(In2(b), Sent2(In2(b + 5)));
84 
85     std::same_as<std::ranges::in_in_out_result<In1, In2, Out>> decltype(auto) ret = std::ranges::transform(
86         range1, range2, Out(c), [](int i, int j) { return i + j; });
87 
88     assert((std::to_array(c) == std::array{6, 6, 6, 6, 6}));
89     assert(base(ret.in1) == a + 5);
90     assert(base(ret.in2) == b + 5);
91     assert(base(ret.out) == c + 5);
92   }
93 
94   { // first range empty
95     int a[] = {};
96     int b[] = {5, 4, 3, 2, 1};
97     int c[5];
98 
99     auto range1 = std::ranges::subrange(In1(a), Sent1(In1(a)));
100     auto range2 = std::ranges::subrange(In2(b), Sent2(In2(b + 5)));
101 
102     auto ret = std::ranges::transform(range1, range2, Out(c), [](int i, int j) { return i + j; });
103 
104     assert(base(ret.in1) == a);
105     assert(base(ret.in2) == b);
106     assert(base(ret.out) == c);
107   }
108 
109   { // second range empty
110     int a[] = {5, 4, 3, 2, 1};
111     int b[] = {};
112     int c[5];
113 
114     auto range1 = std::ranges::subrange(In1(a), Sent1(In1(a + 5)));
115     auto range2 = std::ranges::subrange(In2(b), Sent2(In2(b)));
116 
117     auto ret = std::ranges::transform(range1, range2, Out(c), [](int i, int j) { return i + j; });
118 
119     assert(base(ret.in1) == a);
120     assert(base(ret.in2) == b);
121     assert(base(ret.out) == c);
122   }
123 
124   { // both ranges empty
125     int a[] = {};
126     int b[] = {};
127     int c[5];
128 
129     auto range1 = std::ranges::subrange(In1(a), Sent1(In1(a)));
130     auto range2 = std::ranges::subrange(In2(b), Sent2(In2(b)));
131 
132     auto ret = std::ranges::transform(range1, range2, Out(c), [](int i, int j) { return i + j; });
133 
134     assert(base(ret.in1) == a);
135     assert(base(ret.in2) == b);
136     assert(base(ret.out) == c);
137   }
138 
139   { // first range one element
140     int a[] = {2};
141     int b[] = {5, 4, 3, 2, 1};
142     int c[5];
143 
144     auto range1 = std::ranges::subrange(In1(a), Sent1(In1(a + 1)));
145     auto range2 = std::ranges::subrange(In2(b), Sent2(In2(b + 5)));
146 
147     auto ret = std::ranges::transform(range1, range2, Out(c), [](int i, int j) { return i + j; });
148 
149     assert(c[0] == 7);
150     assert(base(ret.in1) == a + 1);
151     assert(base(ret.in2) == b + 1);
152     assert(base(ret.out) == c + 1);
153   }
154 
155   { // second range contains one element
156     int a[] = {5, 4, 3, 2, 1};
157     int b[] = {4};
158     int c[5];
159 
160     auto range1 = std::ranges::subrange(In1(a), Sent1(In1(a + 5)));
161     auto range2 = std::ranges::subrange(In2(b), Sent2(In2(b + 1)));
162 
163     auto ret = std::ranges::transform(range1, range2, Out(c), [](int i, int j) { return i + j; });
164 
165     assert(c[0] == 9);
166     assert(base(ret.in1) == a + 1);
167     assert(base(ret.in2) == b + 1);
168     assert(base(ret.out) == c + 1);
169   }
170 
171   { // check that the transform function and projection call counts are correct
172     int predCount = 0;
173     int proj1Count = 0;
174     int proj2Count = 0;
175     auto pred = [&](int, int) { ++predCount; return 1; };
176     auto proj1 = [&](int) { ++proj1Count; return 0; };
177     auto proj2 = [&](int) { ++proj2Count; return 0; };
178     int a[] = {1, 2, 3, 4};
179     int b[] = {1, 2, 3, 4};
180     std::array<int, 4> c;
181     auto range1 = std::ranges::subrange(In1(a), Sent1(In1(a + 4)));
182     auto range2 = std::ranges::subrange(In2(b), Sent2(In2(b + 4)));
183     std::ranges::transform(range1, range2, Out(c.data()), pred, proj1, proj2);
184     assert(predCount == 4);
185     assert(proj1Count == 4);
186     assert(proj2Count == 4);
187     assert((c == std::array{1, 1, 1, 1}));
188   }
189 
190   return true;
191 }
192 // clang-format on
193 
194 template <class In2, class Out, class Sent2 = In2>
195 constexpr void test_iterator_in1() {
196   test_iterators<cpp17_input_iterator<int*>, In2, Out, sentinel_wrapper<cpp17_input_iterator<int*>>, Sent2>();
197   test_iterators<cpp20_input_iterator<int*>, In2, Out, sentinel_wrapper<cpp20_input_iterator<int*>>, Sent2>();
198   test_iterators<forward_iterator<int*>, In2, Out, forward_iterator<int*>, Sent2>();
199   test_iterators<bidirectional_iterator<int*>, In2, Out, bidirectional_iterator<int*>, Sent2>();
200   test_iterators<random_access_iterator<int*>, In2, Out, random_access_iterator<int*>, Sent2>();
201   test_iterators<contiguous_iterator<int*>, In2, Out, contiguous_iterator<int*>, Sent2>();
202   test_iterators<int*, In2, Out, int*, Sent2>();
203   // static_asserting here to avoid hitting the constant evaluation step limit
204   static_assert(test_iterators<cpp17_input_iterator<int*>, In2, Out, sentinel_wrapper<cpp17_input_iterator<int*>>, Sent2>());
205   static_assert(test_iterators<cpp20_input_iterator<int*>, In2, Out, sentinel_wrapper<cpp20_input_iterator<int*>>, Sent2>());
206   static_assert(test_iterators<forward_iterator<int*>, In2, Out, forward_iterator<int*>, Sent2>());
207   static_assert(test_iterators<bidirectional_iterator<int*>, In2, Out, bidirectional_iterator<int*>, Sent2>());
208   static_assert(test_iterators<random_access_iterator<int*>, In2, Out, random_access_iterator<int*>, Sent2>());
209   static_assert(test_iterators<contiguous_iterator<int*>, In2, Out, contiguous_iterator<int*>, Sent2>());
210   static_assert(test_iterators<int*, In2, Out, int*, Sent2>());
211 }
212 
213 template <class Out>
214 constexpr void test_iterators_in1_in2() {
215   test_iterator_in1<cpp17_input_iterator<int*>, Out, sentinel_wrapper<cpp17_input_iterator<int*>>>();
216   test_iterator_in1<cpp20_input_iterator<int*>, Out, sentinel_wrapper<cpp20_input_iterator<int*>>>();
217   test_iterator_in1<forward_iterator<int*>, Out>();
218   test_iterator_in1<bidirectional_iterator<int*>, Out>();
219   test_iterator_in1<random_access_iterator<int*>, Out>();
220   test_iterator_in1<contiguous_iterator<int*>, Out>();
221   test_iterator_in1<int*, Out>();
222 }
223 
224 constexpr bool test() {
225   test_iterators_in1_in2<cpp17_output_iterator<int*>>();
226   test_iterators_in1_in2<cpp20_output_iterator<int*>>();
227   test_iterators_in1_in2<forward_iterator<int*>>();
228   test_iterators_in1_in2<bidirectional_iterator<int*>>();
229   test_iterators_in1_in2<random_access_iterator<int*>>();
230   test_iterators_in1_in2<contiguous_iterator<int*>>();
231   test_iterators_in1_in2<int*>();
232 
233   { // check that std::ranges::dangling is returned properly
234     {
235       int b[] = {2, 5, 4, 3, 1};
236       std::array<int, 5> c;
237       std::same_as<std::ranges::in_in_out_result<std::ranges::dangling, int*, int*>> auto ret =
238           std::ranges::transform(std::array{1, 2, 3, 5, 4}, b, c.data(), [](int i, int j) { return i * j; });
239       assert((c == std::array{2, 10, 12, 15, 4}));
240       assert(ret.in2 == b + 5);
241       assert(ret.out == c.data() + c.size());
242     }
243     {
244       int a[] = {2, 5, 4, 3, 1, 4, 5, 6};
245       std::array<int, 8> c;
246       std::same_as<std::ranges::in_in_out_result<int*, std::ranges::dangling, int*>> auto ret =
247           std::ranges::transform(a, std::array{1, 2, 3, 5, 4, 5, 6, 7}, c.data(), [](int i, int j) { return i * j; });
248       assert((c == std::array{2, 10, 12, 15, 4, 20, 30, 42}));
249       assert(ret.in1 == a + 8);
250       assert(ret.out == c.data() + c.size());
251     }
252     {
253       std::array<int, 3> c;
254       std::same_as<std::ranges::in_in_out_result<std::ranges::dangling, std::ranges::dangling, int*>> auto ret =
255           std::ranges::transform(std::array{4, 4, 4}, std::array{4, 4, 4}, c.data(), [](int i, int j) { return i * j; });
256       assert((c == std::array{16, 16, 16}));
257       assert(ret.out == c.data() + c.size());
258     }
259   }
260 
261   { // check that returning another type from the projection works
262     struct S { int i; int other; };
263     S a[] = { S{0, 0}, S{1, 0}, S{3, 0}, S{10, 0} };
264     S b[] = { S{0, 10}, S{1, 20}, S{3, 30}, S{10, 40} };
265     std::array<int, 4> c;
266     std::ranges::transform(a, b, c.begin(), [](S s1, S s2) { return s1.i + s2.other; });
267     assert((c == std::array{10, 21, 33, 50}));
268   }
269 
270   { // check that std::invoke is used
271     struct S { int i; };
272     S a[] = { S{1}, S{3}, S{2} };
273     S b[] = { S{2}, S{5}, S{3} };
274     std::array<int, 3> c;
275     auto ret = std::ranges::transform(a, b, c.data(), [](int i, int j) { return i + j + 2; }, &S::i, &S::i);
276     assert((c == std::array{5, 10, 7}));
277     assert(ret.out == c.data() + 3);
278   }
279 
280   return true;
281 }
282 
283 int main(int, char**) {
284   test();
285   static_assert(test());
286 
287   return 0;
288 }
289