From 7639bf34fa1942b0a56a0ba441637c1ce75e1127 Mon Sep 17 00:00:00 2001 From: Patrick Palka Date: Fri, 14 Apr 2023 10:31:44 -0400 Subject: [PATCH] libstdc++: Implement ranges::fold_* from P2322R6 libstdc++-v3/ChangeLog: * include/bits/ranges_algo.h: Include for C++23. (__cpp_lib_fold): Define for C++23. (in_value_result): Likewise. (__detail::__flipped): Likewise. (__detail::__indirectly_binary_left_foldable_impl): Likewise. (__detail::__indirectly_binary_left_foldable): Likewise. (___detail:__indirectly_binary_right_foldable): Likewise. (fold_left_with_iter_result): Likewise. (__fold_left_with_iter_fn, fold_left_with_iter): Likewise. (__fold_left_fn, fold_left): Likewise. (__fold_left_first_with_iter_fn, fold_left_first_with_iter): Likewise. (__fold_left_first_fn, fold_left_first): Likewise. (__fold_right_fn, fold_right): Likewise. (__fold_right_last_fn, fold_right_last): Likewise. * include/std/version (__cpp_lib_fold): Likewise. * testsuite/25_algorithms/fold_left/1.cc: New test. * testsuite/25_algorithms/fold_right/1.cc: New test. --- libstdc++-v3/include/bits/ranges_algo.h | 251 +++++++++++++++++++++ libstdc++-v3/include/std/version | 1 + .../testsuite/25_algorithms/fold_left/1.cc | 73 ++++++ .../testsuite/25_algorithms/fold_right/1.cc | 45 ++++ 4 files changed, 370 insertions(+) create mode 100644 libstdc++-v3/testsuite/25_algorithms/fold_left/1.cc create mode 100644 libstdc++-v3/testsuite/25_algorithms/fold_right/1.cc diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h index 5d039bd..f041ff1 100644 --- a/libstdc++-v3/include/bits/ranges_algo.h +++ b/libstdc++-v3/include/bits/ranges_algo.h @@ -32,6 +32,9 @@ #if __cplusplus > 201703L +#if __cplusplus > 202002L +#include +#endif #include #include #include // concept uniform_random_bit_generator @@ -3691,6 +3694,254 @@ namespace ranges }; inline constexpr __find_last_if_not_fn find_last_if_not{}; + +#define __cpp_lib_fold 202207L + + template + struct in_value_result + { + [[no_unique_address]] _Iter in; + [[no_unique_address]] _Tp value; + + template + requires convertible_to + && convertible_to + constexpr + operator in_value_result<_Iter2, _Tp2>() const & + { return {in, value}; } + + template + requires convertible_to<_Iter, _Iter2> + && convertible_to<_Tp, _Tp2> + constexpr + operator in_value_result<_Iter2, _Tp2>() && + { return {std::move(in), std::move(value)}; } + }; + + namespace __detail + { + template + class __flipped + { + _Fp _M_f; + + public: + template + requires invocable<_Fp&, _Up, _Tp> + invoke_result_t<_Fp&, _Up, _Tp> + operator()(_Tp&&, _Up&&); // not defined + }; + + template + concept __indirectly_binary_left_foldable_impl = movable<_Tp> && movable<_Up> + && convertible_to<_Tp, _Up> + && invocable<_Fp&, _Up, iter_reference_t<_Iter>> + && assignable_from<_Up&, invoke_result_t<_Fp&, _Up, iter_reference_t<_Iter>>>; + + template + concept __indirectly_binary_left_foldable = copy_constructible<_Fp> + && indirectly_readable<_Iter> + && invocable<_Fp&, _Tp, iter_reference_t<_Iter>> + && convertible_to>, + decay_t>>> + && __indirectly_binary_left_foldable_impl + <_Fp, _Tp, _Iter, decay_t>>>; + + template + concept __indirectly_binary_right_foldable + = __indirectly_binary_left_foldable<__flipped<_Fp>, _Tp, _Iter>; + } // namespace __detail + + template + using fold_left_with_iter_result = in_value_result<_Iter, _Tp>; + + struct __fold_left_with_iter_fn + { + template + static constexpr auto + _S_impl(_Iter __first, _Sent __last, _Tp __init, _Fp __f) + { + using _Up = decay_t>>; + using _Ret = fold_left_with_iter_result<_Ret_iter, _Up>; + + if (__first == __last) + return _Ret{std::move(__first), _Up(std::move(__init))}; + + _Up __accum = std::__invoke(__f, std::move(__init), *__first); + for (++__first; __first != __last; ++__first) + __accum = std::__invoke(__f, std::move(__accum), *__first); + return _Ret{std::move(__first), std::move(__accum)}; + } + + template _Sent, typename _Tp, + __detail::__indirectly_binary_left_foldable<_Tp, _Iter> _Fp> + constexpr auto + operator()(_Iter __first, _Sent __last, _Tp __init, _Fp __f) const + { + using _Ret_iter = _Iter; + return _S_impl<_Ret_iter>(std::move(__first), __last, + std::move(__init), std::move(__f)); + } + + template> _Fp> + constexpr auto + operator()(_Range&& __r, _Tp __init, _Fp __f) const + { + using _Ret_iter = borrowed_iterator_t<_Range>; + return _S_impl<_Ret_iter>(ranges::begin(__r), ranges::end(__r), + std::move(__init), std::move(__f)); + } + }; + + inline constexpr __fold_left_with_iter_fn fold_left_with_iter{}; + + struct __fold_left_fn + { + template _Sent, typename _Tp, + __detail::__indirectly_binary_left_foldable<_Tp, _Iter> _Fp> + constexpr auto + operator()(_Iter __first, _Sent __last, _Tp __init, _Fp __f) const + { + return ranges::fold_left_with_iter(std::move(__first), __last, + std::move(__init), std::move(__f)).value; + } + + template> _Fp> + constexpr auto + operator()(_Range&& __r, _Tp __init, _Fp __f) const + { return (*this)(ranges::begin(__r), ranges::end(__r), std::move(__init), std::move(__f)); } + }; + + inline constexpr __fold_left_fn fold_left{}; + + template + using fold_left_first_with_iter_result = in_value_result<_Iter, _Tp>; + + struct __fold_left_first_with_iter_fn + { + template + static constexpr auto + _S_impl(_Iter __first, _Sent __last, _Fp __f) + { + using _Up = decltype(ranges::fold_left(std::move(__first), __last, + iter_value_t<_Iter>(*__first), __f)); + using _Ret = fold_left_first_with_iter_result<_Ret_iter, optional<_Up>>; + + if (__first == __last) + return _Ret{std::move(__first), optional<_Up>()}; + + optional<_Up> __init(in_place, *__first); + for (++__first; __first != __last; ++__first) + *__init = std::__invoke(__f, std::move(*__init), *__first); + return _Ret{std::move(__first), std::move(__init)}; + } + + template _Sent, + __detail::__indirectly_binary_left_foldable, _Iter> _Fp> + requires constructible_from, iter_reference_t<_Iter>> + constexpr auto + operator()(_Iter __first, _Sent __last, _Fp __f) const + { + using _Ret_iter = _Iter; + return _S_impl<_Ret_iter>(std::move(__first), __last, std::move(__f)); + } + + template, iterator_t<_Range>> _Fp> + requires constructible_from, range_reference_t<_Range>> + constexpr auto + operator()(_Range&& __r, _Fp __f) const + { + using _Ret_iter = borrowed_iterator_t<_Range>; + return _S_impl<_Ret_iter>(ranges::begin(__r), ranges::end(__r), std::move(__f)); + } + }; + + inline constexpr __fold_left_first_with_iter_fn fold_left_first_with_iter{}; + + struct __fold_left_first_fn + { + template _Sent, + __detail::__indirectly_binary_left_foldable, _Iter> _Fp> + requires constructible_from, iter_reference_t<_Iter>> + constexpr auto + operator()(_Iter __first, _Sent __last, _Fp __f) const + { + return ranges::fold_left_first_with_iter(std::move(__first), __last, + std::move(__f)).value; + } + + template, iterator_t<_Range>> _Fp> + requires constructible_from, range_reference_t<_Range>> + constexpr auto + operator()(_Range&& __r, _Fp __f) const + { return (*this)(ranges::begin(__r), ranges::end(__r), std::move(__f)); } + }; + + inline constexpr __fold_left_first_fn fold_left_first{}; + + struct __fold_right_fn + { + template _Sent, typename _Tp, + __detail::__indirectly_binary_right_foldable<_Tp, _Iter> _Fp> + constexpr auto + operator()(_Iter __first, _Sent __last, _Tp __init, _Fp __f) const + { + using _Up = decay_t, _Tp>>; + + if (__first == __last) + return _Up(std::move(__init)); + + _Iter __tail = ranges::next(__first, __last); + _Up __accum = std::__invoke(__f, *--__tail, std::move(__init)); + while (__first != __tail) + __accum = std::__invoke(__f, *--__tail, std::move(__accum)); + return __accum; + } + + template> _Fp> + constexpr auto + operator()(_Range&& __r, _Tp __init, _Fp __f) const + { return (*this)(ranges::begin(__r), ranges::end(__r), std::move(__init), std::move(__f)); } + }; + + inline constexpr __fold_right_fn fold_right{}; + + struct __fold_right_last_fn + { + template _Sent, + __detail::__indirectly_binary_right_foldable, _Iter> _Fp> + requires constructible_from, iter_reference_t<_Iter>> + constexpr auto + operator()(_Iter __first, _Sent __last, _Fp __f) const + { + using _Up = decltype(ranges::fold_right(__first, __last, + iter_value_t<_Iter>(*__first), __f)); + + if (__first == __last) + return optional<_Up>(); + + _Iter __tail = ranges::prev(ranges::next(__first, std::move(__last))); + return optional<_Up>(in_place, + ranges::fold_right(std::move(__first), __tail, + iter_value_t<_Iter>(*__tail), + std::move(__f))); + } + + template, iterator_t<_Range>> _Fp> + requires constructible_from, range_reference_t<_Range>> + constexpr auto + operator()(_Range&& __r, _Fp __f) const + { return (*this)(ranges::begin(__r), ranges::end(__r), std::move(__f)); } + }; + + inline constexpr __fold_right_last_fn fold_right_last{}; #endif // C++23 } // namespace ranges diff --git a/libstdc++-v3/include/std/version b/libstdc++-v3/include/std/version index b35435c..d233b03 100644 --- a/libstdc++-v3/include/std/version +++ b/libstdc++-v3/include/std/version @@ -340,6 +340,7 @@ #define __cpp_lib_ranges_cartesian_product 202207L #define __cpp_lib_ranges_as_rvalue 202207L #define __cpp_lib_ranges_enumerate 202302L +#define __cpp_lib_fold 202207L #if __cpp_constexpr_dynamic_alloc # if _GLIBCXX_HOSTED # define __cpp_lib_constexpr_bitset 202202L diff --git a/libstdc++-v3/testsuite/25_algorithms/fold_left/1.cc b/libstdc++-v3/testsuite/25_algorithms/fold_left/1.cc new file mode 100644 index 0000000..5cc91b6 --- /dev/null +++ b/libstdc++-v3/testsuite/25_algorithms/fold_left/1.cc @@ -0,0 +1,73 @@ +// { dg-options "-std=gnu++23" } +// { dg-do run { target c++23 } } + +#include +#include +#include + +#if __cpp_lib_fold != 202207L +# error "Feature-test macro __cpp_lib_fold has wrong value in " +#endif + +namespace ranges = std::ranges; +namespace views = std::views; + +constexpr bool +test01() +{ + int x[] = {1, 2, 3, 4, 5}; + auto f = [](int&& acc, int& x) { + return 2 * acc + x; + }; + VERIFY( ranges::fold_left(x, 0, f) == 57 ); + VERIFY( ranges::fold_left(x, 1, f) == 89 ); + VERIFY( ranges::fold_left(x+0, x+0, 1, f) == 1 ); + + VERIFY( ranges::fold_left_first(x, f).value() == 57 ); + VERIFY( !ranges::fold_left_first(x+0, x+0, f).has_value() ); + + return true; +} + +void +test02() +{ + int x[] = {1, 2, 3, 4, 5}; + auto f = [](int&& acc, int& x) { + return 2 * acc + x; + }; + + __gnu_test::test_input_range rx(x); + ranges::in_value_result ivr = ranges::fold_left_with_iter(rx, 0, f); + VERIFY( ivr.in == rx.end() ); + VERIFY( ivr.value == 57 ); + + rx.bounds.first = x; + ranges::in_value_result ivr2 = ranges::fold_left_first_with_iter(rx, f); + VERIFY( ivr2.in == rx.end() ); + VERIFY( ivr2.value.value() == 57 ); + + rx.bounds.first = x; + auto v = rx | views::take(0); + ranges::in_value_result ivr3 = ranges::fold_left_first_with_iter(v, f); + VERIFY( ivr3.in == v.end() ); + VERIFY( !ivr3.value.has_value() ); +} + +constexpr bool +test03() +{ + double x[] = {0.5, 0.25, 0.125, 0.125}; + VERIFY( ranges::fold_left(x, 0, std::plus{}) == 1.0 ); + VERIFY( ranges::fold_left_with_iter(x, 0, std::plus{}).value == 1.0 ); + + return true; +} + +int +main() +{ + static_assert(test01()); + test02(); + static_assert(test03()); +} diff --git a/libstdc++-v3/testsuite/25_algorithms/fold_right/1.cc b/libstdc++-v3/testsuite/25_algorithms/fold_right/1.cc new file mode 100644 index 0000000..b08b57c --- /dev/null +++ b/libstdc++-v3/testsuite/25_algorithms/fold_right/1.cc @@ -0,0 +1,45 @@ +// { dg-options "-std=gnu++23" } +// { dg-do run { target c++23 } } + +#include +#include +#include + +namespace ranges = std::ranges; +namespace views = std::views; + +constexpr bool +test01() +{ + int x[] = {1, 2, 3, 4, 5}; + auto v = x | views::filter([](int) { return true; }); + static_assert( ranges::bidirectional_range + && !ranges::random_access_range ); + auto f = [](int& x, int&& acc) { + return 2 * acc + x; + }; + VERIFY( ranges::fold_right(v, 0, f) == 129 ); + VERIFY( ranges::fold_right(v, 1, f) == 161 ); + VERIFY( ranges::fold_right(v.begin(), v.begin(), 1, f) == 1 ); + + VERIFY( ranges::fold_right_last(v, f).value() == 129 ); + VERIFY( !ranges::fold_right_last(v.begin(), v.begin(), f).has_value() ); + + return true; +} + +constexpr bool +test02() +{ + double x[] = {0.5, 0.25, 0.125, 0.125}; + VERIFY( ranges::fold_right(x, 0, std::plus{}) == 1.0 ); + + return true; +} + +int +main() +{ + static_assert(test01()); + static_assert(test02()); +} -- 2.7.4