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, c++20
12
13 // MSVC warning C4244: 'argument': conversion from 'double' to 'const int', possible loss of data
14 // ADDITIONAL_COMPILE_FLAGS(cl-style-warnings): /wd4244
15
16 // template<input_iterator I, sentinel_for<I> S, class T,
17 // indirectly-binary-left-foldable<T, I> F>
18 // constexpr see below ranges::fold_left_with_iter(I first, S last, T init, F f);
19 //
20 // template<input_range R, class T, indirectly-binary-left-foldable<T, iterator_t<R>> F>
21 // constexpr see below ranges::fold_left_with_iter(R&& r, T init, F f);
22
23 // template<input_iterator I, sentinel_for<I> S, class T,
24 // indirectly-binary-left-foldable<T, I> F>
25 // constexpr see below ranges::fold_left(I first, S last, T init, F f);
26 //
27 // template<input_range R, class T, indirectly-binary-left-foldable<T, iterator_t<R>> F>
28 // constexpr see below ranges::fold_left(R&& r, T init, F f);
29
30 #include <algorithm>
31 #include <cassert>
32 #include <concepts>
33 #include <deque>
34 #include <forward_list>
35 #include <functional>
36 #include <iterator>
37 #include <list>
38 #include <ranges>
39 #include <string_view>
40 #include <string>
41 #include <vector>
42
43 #include "test_macros.h"
44 #include "test_range.h"
45 #include "invocable_with_telemetry.h"
46 #include "maths.h"
47
48 #if !defined(TEST_HAS_NO_LOCALIZATION)
49 # include <sstream>
50 #endif
51
52 using std::ranges::fold_left;
53 using std::ranges::fold_left_with_iter;
54
55 template <class Result, class Range, class T>
56 concept is_in_value_result =
57 std::same_as<Result, std::ranges::fold_left_with_iter_result<std::ranges::iterator_t<Range>, T>>;
58
59 template <class Result, class T>
60 concept is_dangling_with = std::same_as<Result, std::ranges::fold_left_with_iter_result<std::ranges::dangling, T>>;
61
62 struct Long {
63 int value;
64
LongLong65 constexpr Long(int const x) : value(x) {}
66
plusLong67 constexpr Long plus(int const x) const { return Long{value + x}; }
68
69 friend constexpr bool operator==(Long const& x, Long const& y) = default;
70 };
71
72 template <std::ranges::input_range R, class T, class F, std::equality_comparable Expected>
73 requires std::copyable<R>
check_iterator(R & r,T const & init,F f,Expected const & expected)74 constexpr void check_iterator(R& r, T const& init, F f, Expected const& expected) {
75 {
76 is_in_value_result<R, Expected> decltype(auto) result = fold_left_with_iter(r.begin(), r.end(), init, f);
77 assert(result.in == r.end());
78 assert(result.value == expected);
79 }
80 {
81 auto telemetry = invocable_telemetry();
82 auto f2 = invocable_with_telemetry(f, telemetry);
83 is_in_value_result<R, Expected> decltype(auto) result = fold_left_with_iter(r.begin(), r.end(), init, f2);
84 assert(result.in == r.end());
85 assert(result.value == expected);
86 assert(telemetry.invocations == std::ranges::distance(r));
87 assert(telemetry.moves == 0);
88 assert(telemetry.copies == 1);
89 }
90
91 {
92 std::same_as<Expected> decltype(auto) result = fold_left(r.begin(), r.end(), init, f);
93 assert(result == expected);
94 }
95 {
96 auto telemetry = invocable_telemetry();
97 auto f2 = invocable_with_telemetry(f, telemetry);
98 std::same_as<Expected> decltype(auto) result = fold_left(r.begin(), r.end(), init, f2);
99 assert(result == expected);
100 assert(telemetry.invocations == std::ranges::distance(r));
101 assert(telemetry.moves == 0);
102 assert(telemetry.copies == 1);
103 }
104 }
105
106 template <std::ranges::input_range R, class T, class F, std::equality_comparable Expected>
107 requires std::copyable<R>
check_lvalue_range(R & r,T const & init,F f,Expected const & expected)108 constexpr void check_lvalue_range(R& r, T const& init, F f, Expected const& expected) {
109 {
110 is_in_value_result<R, Expected> decltype(auto) result = fold_left_with_iter(r, init, f);
111 assert(result.in == r.end());
112 assert(result.value == expected);
113 }
114 {
115 auto telemetry = invocable_telemetry();
116 auto f2 = invocable_with_telemetry(f, telemetry);
117 std::same_as<Expected> decltype(auto) result = fold_left(r, init, f2);
118 assert(result == expected);
119 assert(telemetry.invocations == std::ranges::distance(r));
120 assert(telemetry.moves == 0);
121 assert(telemetry.copies == 1);
122 }
123
124 {
125 std::same_as<Expected> decltype(auto) result = fold_left(r, init, f);
126 assert(result == expected);
127 }
128 {
129 auto telemetry = invocable_telemetry();
130 auto f2 = invocable_with_telemetry(f, telemetry);
131 std::same_as<Expected> decltype(auto) result = fold_left(r, init, f2);
132 assert(result == expected);
133 assert(telemetry.invocations == std::ranges::distance(r));
134 assert(telemetry.moves == 0);
135 assert(telemetry.copies == 1);
136 }
137 }
138
139 template <std::ranges::input_range R, class T, class F, std::equality_comparable Expected>
140 requires std::copyable<R>
check_rvalue_range(R & r,T const & init,F f,Expected const & expected)141 constexpr void check_rvalue_range(R& r, T const& init, F f, Expected const& expected) {
142 {
143 auto r2 = r;
144 is_dangling_with<Expected> decltype(auto) result = fold_left_with_iter(std::move(r2), init, f);
145 assert(result.value == expected);
146 }
147 {
148 auto telemetry = invocable_telemetry();
149 auto f2 = invocable_with_telemetry(f, telemetry);
150 auto r2 = r;
151 is_dangling_with<Expected> decltype(auto) result = fold_left_with_iter(std::move(r2), init, f2);
152 assert(result.value == expected);
153 assert(telemetry.invocations == std::ranges::distance(r));
154 assert(telemetry.moves == 0);
155 assert(telemetry.copies == 1);
156 }
157
158 {
159 auto r2 = r;
160 std::same_as<Expected> decltype(auto) result = fold_left(std::move(r2), init, f);
161 assert(result == expected);
162 }
163 {
164 auto telemetry = invocable_telemetry();
165 auto f2 = invocable_with_telemetry(f, telemetry);
166 auto r2 = r;
167 std::same_as<Expected> decltype(auto) result = fold_left(std::move(r2), init, f2);
168 assert(result == expected);
169 assert(telemetry.invocations == std::ranges::distance(r));
170 assert(telemetry.moves == 0);
171 assert(telemetry.copies == 1);
172 }
173 }
174
175 template <std::ranges::input_range R, class T, class F, std::equality_comparable Expected>
176 requires std::copyable<R>
check(R r,T const & init,F f,Expected const & expected)177 constexpr void check(R r, T const& init, F f, Expected const& expected) {
178 check_iterator(r, init, f, expected);
179 check_lvalue_range(r, init, f, expected);
180 check_rvalue_range(r, init, f, expected);
181 }
182
empty_range_test_case()183 constexpr void empty_range_test_case() {
184 auto const data = std::vector<int>{};
185 check(data, 100, std::plus(), 100);
186 check(data, -100, std::multiplies(), -100);
187
188 check(data | std::views::take_while([](auto) { return false; }), 1.23, std::plus(), 1.23);
189 check(data, Long(52), &Long::plus, Long(52));
190 }
191
common_range_test_case()192 constexpr void common_range_test_case() {
193 auto const data = std::vector<int>{1, 2, 3, 4};
194 check(data, 0, std::plus(), triangular_sum(data));
195 check(data, 1, std::multiplies(), factorial(data.back()));
196
197 auto multiply_with_prev = [n = 1](auto const x, auto const y) mutable {
198 auto const result = x * y * n;
199 n = y;
200 return static_cast<std::size_t>(result);
201 };
202 check(data, 1, multiply_with_prev, factorial(data.size()) * factorial(data.size() - 1));
203
204 auto fib = [n = 1](auto x, auto) mutable {
205 auto old_x = x;
206 x += n;
207 n = old_x;
208 return x;
209 };
210 check(data, 0, fib, fibonacci(data.back()));
211
212 check(data, Long(0), &Long::plus, Long(triangular_sum(data)));
213 }
214
non_common_range_test_case()215 constexpr void non_common_range_test_case() {
216 auto parse = [](std::string_view const s) {
217 return s == "zero" ? 0.0
218 : s == "one" ? 1.0
219 : s == "two" ? 2.0
220 : s == "three" ? 3.0
221 : s == "four" ? 4.0
222 : s == "five" ? 5.0
223 : s == "six" ? 6.0
224 : s == "seven" ? 7.0
225 : s == "eight" ? 8.0
226 : s == "nine" ? 9.0
227 : (assert(false), 10.0); // the number here is arbitrary
228 };
229
230 {
231 auto data = std::vector<std::string>{"five", "three", "two", "six", "one", "four"};
232 auto range = data | std::views::transform(parse);
233 check(range, 0, std::plus(), triangular_sum(range));
234 }
235
236 {
237 auto data = std::string("five three two six one four");
238 auto to_string_view = [](auto&& r) {
239 auto const n = std::ranges::distance(r);
240 return std::string_view(&*r.begin(), n);
241 };
242 auto range =
243 std::views::lazy_split(data, ' ') | std::views::transform(to_string_view) | std::views::transform(parse);
244 check(range, 0, std::plus(), triangular_sum(range));
245 }
246 }
247
test_case()248 constexpr bool test_case() {
249 empty_range_test_case();
250 common_range_test_case();
251 non_common_range_test_case();
252 return true;
253 }
254
255 // Most containers aren't constexpr
runtime_only_test_case()256 void runtime_only_test_case() {
257 #if !defined(TEST_HAS_NO_LOCALIZATION)
258 { // istream_view is a genuine input range and needs specific handling.
259 constexpr auto raw_data = "Shells Orange Syrup Baratie Cocoyashi Loguetown";
260 constexpr auto expected = "WindmillShellsOrangeSyrupBaratieCocoyashiLoguetown";
261 auto const init = std::string("Windmill");
262
263 {
264 auto input = std::istringstream(raw_data);
265 auto data = std::views::istream<std::string>(input);
266 is_in_value_result<std::ranges::basic_istream_view<std::string, char>, std::string> decltype(auto) result =
267 fold_left_with_iter(data.begin(), data.end(), init, std::plus());
268
269 assert(result.in == data.end());
270 assert(result.value == expected);
271 }
272 {
273 auto input = std::istringstream(raw_data);
274 auto data = std::views::istream<std::string>(input);
275 is_in_value_result<std::ranges::basic_istream_view<std::string, char>, std::string> decltype(auto) result =
276 fold_left_with_iter(data, init, std::plus());
277 assert(result.in == data.end());
278 assert(result.value == expected);
279 }
280 {
281 auto input = std::istringstream(raw_data);
282 auto data = std::views::istream<std::string>(input);
283 assert(fold_left(data.begin(), data.end(), init, std::plus()) == expected);
284 }
285 {
286 auto input = std::istringstream(raw_data);
287 auto data = std::views::istream<std::string>(input);
288 assert(fold_left(data, init, std::plus()) == expected);
289 }
290 }
291 #endif
292 {
293 auto const data = std::forward_list<int>{1, 3, 5, 7, 9};
294 auto const n = std::ranges::distance(data);
295 auto const expected = static_cast<float>(n * n); // sum of n consecutive odd numbers = n^2
296 check(data, 0.0f, std::plus(), expected);
297 }
298
299 {
300 auto const data = std::list<int>{2, 4, 6, 8, 10, 12};
301 auto const expected = triangular_sum(data);
302 check(data, 0, std::plus<long>(), static_cast<long>(expected));
303 }
304
305 {
306 auto const data = std::deque<double>{-1.1, -2.2, -3.3, -4.4, -5.5, -6.6};
307 auto plus = [](int const x, double const y) { return x + y; };
308 auto const expected = -21.6; // int( 0.0) + -1.1 = 0 + -1.1 = -1.1
309 // int(- 1.1) + -2.2 = - 1 + -2.2 = -3.2
310 // int(- 3.2) + -3.3 = - 3 + -3.3 = -6.3
311 // int(- 6.3) + -4.4 = - 6 + -4.4 = -10.4
312 // int(-10.4) + -5.5 = -10 + -5.5 = -15.5
313 // int(-15.5) + -6.6 = -15 + -6.6 = -21.6.
314 check(data, 0.0, plus, expected);
315 }
316 }
317
main(int,char **)318 int main(int, char**) {
319 test_case();
320 static_assert(test_case());
321 runtime_only_test_case();
322 return 0;
323 }
324