333 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++17, c++2012 13// MSVC warning C4244: 'argument': conversion from 'double' to 'const int', possible loss of data14// ADDITIONAL_COMPILE_FLAGS(cl-style-warnings): /wd424415 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#endif51 52using std::ranges::fold_left;53using std::ranges::fold_left_with_iter;54 55template <class Result, class Range, class T>56concept is_in_value_result =57 std::same_as<Result, std::ranges::fold_left_with_iter_result<std::ranges::iterator_t<Range>, T>>;58 59template <class Result, class T>60concept is_dangling_with = std::same_as<Result, std::ranges::fold_left_with_iter_result<std::ranges::dangling, T>>;61 62struct Integer {63 int value;64 65 constexpr Integer(int const x) : value(x) {}66 67 constexpr Integer plus(int const x) const { return Integer{value + x}; }68 69 friend constexpr bool operator==(Integer const& x, Integer const& y) = default;70};71 72template <std::ranges::input_range R, class T, class F, std::equality_comparable Expected>73 requires std::copyable<R>74constexpr 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 {82 auto telemetry = invocable_telemetry();83 auto f2 = invocable_with_telemetry(f, telemetry);84 is_in_value_result<R, Expected> decltype(auto) result = fold_left_with_iter(r.begin(), r.end(), init, f2);85 assert(result.in == r.end());86 assert(result.value == expected);87 assert(telemetry.invocations == std::ranges::distance(r));88 assert(telemetry.moves == 0);89 assert(telemetry.copies == 1);90 }91 92 {93 std::same_as<Expected> decltype(auto) result = fold_left(r.begin(), r.end(), init, f);94 assert(result == expected);95 }96 97 {98 auto telemetry = invocable_telemetry();99 auto f2 = invocable_with_telemetry(f, telemetry);100 std::same_as<Expected> decltype(auto) result = fold_left(r.begin(), r.end(), init, f2);101 assert(result == expected);102 assert(telemetry.invocations == std::ranges::distance(r));103 assert(telemetry.moves == 0);104 assert(telemetry.copies == 1);105 }106}107 108template <std::ranges::input_range R, class T, class F, std::equality_comparable Expected>109 requires std::copyable<R>110constexpr void check_lvalue_range(R& r, T const& init, F f, Expected const& expected) {111 {112 is_in_value_result<R, Expected> decltype(auto) result = fold_left_with_iter(r, init, f);113 assert(result.in == r.end());114 assert(result.value == expected);115 }116 117 {118 auto telemetry = invocable_telemetry();119 auto f2 = invocable_with_telemetry(f, telemetry);120 std::same_as<Expected> decltype(auto) result = fold_left(r, init, f2);121 assert(result == expected);122 assert(telemetry.invocations == std::ranges::distance(r));123 assert(telemetry.moves == 0);124 assert(telemetry.copies == 1);125 }126 127 {128 std::same_as<Expected> decltype(auto) result = fold_left(r, init, f);129 assert(result == expected);130 }131 132 {133 auto telemetry = invocable_telemetry();134 auto f2 = invocable_with_telemetry(f, telemetry);135 std::same_as<Expected> decltype(auto) result = fold_left(r, init, f2);136 assert(result == expected);137 assert(telemetry.invocations == std::ranges::distance(r));138 assert(telemetry.moves == 0);139 assert(telemetry.copies == 1);140 }141}142 143template <std::ranges::input_range R, class T, class F, std::equality_comparable Expected>144 requires std::copyable<R>145constexpr void check_rvalue_range(R& r, T const& init, F f, Expected const& expected) {146 {147 auto r2 = r;148 is_dangling_with<Expected> decltype(auto) result = fold_left_with_iter(std::move(r2), init, f);149 assert(result.value == expected);150 }151 152 {153 auto telemetry = invocable_telemetry();154 auto f2 = invocable_with_telemetry(f, telemetry);155 auto r2 = r;156 is_dangling_with<Expected> decltype(auto) result = fold_left_with_iter(std::move(r2), init, f2);157 assert(result.value == expected);158 assert(telemetry.invocations == std::ranges::distance(r));159 assert(telemetry.moves == 0);160 assert(telemetry.copies == 1);161 }162 163 {164 auto r2 = r;165 std::same_as<Expected> decltype(auto) result = fold_left(std::move(r2), init, f);166 assert(result == expected);167 }168 169 {170 auto telemetry = invocable_telemetry();171 auto f2 = invocable_with_telemetry(f, telemetry);172 auto r2 = r;173 std::same_as<Expected> decltype(auto) result = fold_left(std::move(r2), init, f2);174 assert(result == expected);175 assert(telemetry.invocations == std::ranges::distance(r));176 assert(telemetry.moves == 0);177 assert(telemetry.copies == 1);178 }179}180 181template <std::ranges::input_range R, class T, class F, std::equality_comparable Expected>182 requires std::copyable<R>183constexpr void check(R r, T const& init, F f, Expected const& expected) {184 check_iterator(r, init, f, expected);185 check_lvalue_range(r, init, f, expected);186 check_rvalue_range(r, init, f, expected);187}188 189constexpr void empty_range_test_case() {190 auto const data = std::vector<int>{};191 check(data, 100, std::plus(), 100);192 check(data, -100, std::multiplies(), -100);193 194 check(data | std::views::take_while([](auto) { return false; }), 1.23, std::plus(), 1.23);195 check(data, Integer(52), &Integer::plus, Integer(52));196}197 198constexpr void common_range_test_case() {199 auto const data = std::vector<int>{1, 2, 3, 4};200 check(data, 0, std::plus(), triangular_sum(data));201 check(data, 1, std::multiplies(), factorial(data.back()));202 203 auto multiply_with_prev = [n = 1](auto const x, auto const y) mutable {204 auto const result = x * y * n;205 n = y;206 return static_cast<std::size_t>(result);207 };208 check(data, 1, multiply_with_prev, factorial(data.size()) * factorial(data.size() - 1));209 210 auto fib = [n = 1](auto x, auto) mutable {211 auto old_x = x;212 x += n;213 n = old_x;214 return x;215 };216 check(data, 0, fib, fibonacci(data.back()));217 218 check(data, Integer(0), &Integer::plus, Integer(triangular_sum(data)));219}220 221constexpr void non_common_range_test_case() {222 auto parse = [](std::string_view const s) {223 return s == "zero" ? 0.0224 : s == "one" ? 1.0225 : s == "two" ? 2.0226 : s == "three" ? 3.0227 : s == "four" ? 4.0228 : s == "five" ? 5.0229 : s == "six" ? 6.0230 : s == "seven" ? 7.0231 : s == "eight" ? 8.0232 : s == "nine" ? 9.0233 : (assert(false), 10.0); // the number here is arbitrary234 };235 236 {237 auto data = std::vector<std::string>{"five", "three", "two", "six", "one", "four"};238 auto range = data | std::views::transform(parse);239 check(range, 0, std::plus(), triangular_sum(range));240 }241 242 {243 auto data = std::string("five three two six one four");244 auto to_string_view = [](auto&& r) {245 auto const n = std::ranges::distance(r);246 return std::string_view(&*r.begin(), n);247 };248 auto range =249 std::views::lazy_split(data, ' ') | std::views::transform(to_string_view) | std::views::transform(parse);250 check(range, 0, std::plus(), triangular_sum(range));251 }252}253 254constexpr bool test_case() {255 empty_range_test_case();256 common_range_test_case();257 non_common_range_test_case();258 return true;259}260 261// Most containers aren't constexpr262void runtime_only_test_case() {263#if !defined(TEST_HAS_NO_LOCALIZATION)264 { // istream_view is a genuine input range and needs specific handling.265 constexpr auto raw_data = "Shells Orange Syrup Baratie Cocoyashi Loguetown";266 constexpr auto expected = "WindmillShellsOrangeSyrupBaratieCocoyashiLoguetown";267 auto const init = std::string("Windmill");268 269 {270 auto input = std::istringstream(raw_data);271 auto data = std::views::istream<std::string>(input);272 is_in_value_result<std::ranges::basic_istream_view<std::string, char>, std::string> decltype(auto) result =273 fold_left_with_iter(data.begin(), data.end(), init, std::plus());274 275 assert(result.in == data.end());276 assert(result.value == expected);277 }278 279 {280 auto input = std::istringstream(raw_data);281 auto data = std::views::istream<std::string>(input);282 is_in_value_result<std::ranges::basic_istream_view<std::string, char>, std::string> decltype(auto) result =283 fold_left_with_iter(data, init, std::plus());284 assert(result.in == data.end());285 assert(result.value == expected);286 }287 288 {289 auto input = std::istringstream(raw_data);290 auto data = std::views::istream<std::string>(input);291 assert(fold_left(data.begin(), data.end(), init, std::plus()) == expected);292 }293 294 {295 auto input = std::istringstream(raw_data);296 auto data = std::views::istream<std::string>(input);297 assert(fold_left(data, init, std::plus()) == expected);298 }299 }300#endif301 {302 auto const data = std::forward_list<int>{1, 3, 5, 7, 9};303 auto const n = std::ranges::distance(data);304 auto const expected = static_cast<float>(n * n); // sum of n consecutive odd numbers = n^2305 check(data, 0.0f, std::plus(), expected);306 }307 308 {309 auto const data = std::list<int>{2, 4, 6, 8, 10, 12};310 auto const expected = triangular_sum(data);311 check(data, 0, std::plus<long>(), static_cast<long>(expected));312 }313 314 {315 auto const data = std::deque<double>{-1.1, -2.2, -3.3, -4.4, -5.5, -6.6};316 auto plus = [](int const x, double const y) { return x + y; };317 auto const expected = -21.6; // int( 0.0) + -1.1 = 0 + -1.1 = -1.1318 // int(- 1.1) + -2.2 = - 1 + -2.2 = -3.2319 // int(- 3.2) + -3.3 = - 3 + -3.3 = -6.3320 // int(- 6.3) + -4.4 = - 6 + -4.4 = -10.4321 // int(-10.4) + -5.5 = -10 + -5.5 = -15.5322 // int(-15.5) + -6.6 = -15 + -6.6 = -21.6.323 check(data, 0.0, plus, expected);324 }325}326 327int main(int, char**) {328 test_case();329 static_assert(test_case());330 runtime_only_test_case();331 return 0;332}333