On Fri, 14 Apr 2023 at 05:01, Patrick Palka via Libstdc++
<libstd...@gcc.gnu.org> wrote:
>
> Tested on x86_64-pc-linux-gnu, does this look OK for trunk?
OK, looks good, thanks.
>
> libstdc++-v3/ChangeLog:
>
> * include/bits/ranges_algo.h: Include <optional> 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.
> * libstdc++-v3/testsuite/25_algorithms/fold_left/1.cc: New test.
> * libstdc++-v3/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 5d039bd1cd4..f041ff16b0e 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 <optional>
> +#endif
> #include <bits/ranges_algobase.h>
> #include <bits/ranges_util.h>
> #include <bits/uniform_int_dist.h> // 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<typename _Iter, typename _Tp>
> + struct in_value_result
> + {
> + [[no_unique_address]] _Iter in;
> + [[no_unique_address]] _Tp value;
> +
> + template<typename _Iter2, typename _Tp2>
> + requires convertible_to<const _Iter&, _Iter2>
> + && convertible_to<const _Tp&, _Tp2>
> + constexpr
> + operator in_value_result<_Iter2, _Tp2>() const &
> + { return {in, value}; }
> +
> + template<typename _Iter2, typename _Tp2>
> + 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<typename _Fp>
> + class __flipped
> + {
> + _Fp _M_f;
> +
> + public:
> + template<typename _Tp, typename _Up>
> + requires invocable<_Fp&, _Up, _Tp>
> + invoke_result_t<_Fp&, _Up, _Tp>
> + operator()(_Tp&&, _Up&&); // not defined
> + };
> +
> + template<typename _Fp, typename _Tp, typename _Iter, typename _Up>
> + 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<typename _Fp, typename _Tp, typename _Iter>
> + concept __indirectly_binary_left_foldable = copy_constructible<_Fp>
> + && indirectly_readable<_Iter>
> + && invocable<_Fp&, _Tp, iter_reference_t<_Iter>>
> + && convertible_to<invoke_result_t<_Fp&, _Tp, iter_reference_t<_Iter>>,
> + decay_t<invoke_result_t<_Fp&, _Tp,
> iter_reference_t<_Iter>>>>
> + && __indirectly_binary_left_foldable_impl
> + <_Fp, _Tp, _Iter, decay_t<invoke_result_t<_Fp&, _Tp,
> iter_reference_t<_Iter>>>>;
> +
> + template <typename _Fp, typename _Tp, typename _Iter>
> + concept __indirectly_binary_right_foldable
> + = __indirectly_binary_left_foldable<__flipped<_Fp>, _Tp, _Iter>;
> + } // namespace __detail
> +
> + template<typename _Iter, typename _Tp>
> + using fold_left_with_iter_result = in_value_result<_Iter, _Tp>;
> +
> + struct __fold_left_with_iter_fn
> + {
> + template<typename _Ret_iter,
> + typename _Iter, typename _Sent, typename _Tp, typename _Fp>
> + static constexpr auto
> + _S_impl(_Iter __first, _Sent __last, _Tp __init, _Fp __f)
> + {
> + using _Up = decay_t<invoke_result_t<_Fp&, _Tp,
> iter_reference_t<_Iter>>>;
> + 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<input_iterator _Iter, sentinel_for<_Iter> _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<input_range _Range, typename _Tp,
> + __detail::__indirectly_binary_left_foldable<_Tp,
> iterator_t<_Range>> _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<input_iterator _Iter, sentinel_for<_Iter> _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<input_range _Range, typename _Tp,
> + __detail::__indirectly_binary_left_foldable<_Tp,
> iterator_t<_Range>> _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<typename _Iter, typename _Tp>
> + using fold_left_first_with_iter_result = in_value_result<_Iter, _Tp>;
> +
> + struct __fold_left_first_with_iter_fn
> + {
> + template<typename _Ret_iter, typename _Iter, typename _Sent, typename
> _Fp>
> + 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<input_iterator _Iter, sentinel_for<_Iter> _Sent,
> + __detail::__indirectly_binary_left_foldable<iter_value_t<_Iter>,
> _Iter> _Fp>
> + requires constructible_from<iter_value_t<_Iter>,
> 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<input_range _Range,
> +
> __detail::__indirectly_binary_left_foldable<range_value_t<_Range>,
> iterator_t<_Range>> _Fp>
> + requires constructible_from<range_value_t<_Range>,
> 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<input_iterator _Iter, sentinel_for<_Iter> _Sent,
> + __detail::__indirectly_binary_left_foldable<iter_value_t<_Iter>,
> _Iter> _Fp>
> + requires constructible_from<iter_value_t<_Iter>,
> 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<input_range _Range,
> +
> __detail::__indirectly_binary_left_foldable<range_value_t<_Range>,
> iterator_t<_Range>> _Fp>
> + requires constructible_from<range_value_t<_Range>,
> 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<bidirectional_iterator _Iter, sentinel_for<_Iter> _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<invoke_result_t<_Fp&, iter_reference_t<_Iter>,
> _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<bidirectional_range _Range, typename _Tp,
> + __detail::__indirectly_binary_right_foldable<_Tp,
> iterator_t<_Range>> _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<bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
> +
> __detail::__indirectly_binary_right_foldable<iter_value_t<_Iter>, _Iter> _Fp>
> + requires constructible_from<iter_value_t<_Iter>,
> 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<bidirectional_range _Range,
> +
> __detail::__indirectly_binary_right_foldable<range_value_t<_Range>,
> iterator_t<_Range>> _Fp>
> + requires constructible_from<range_value_t<_Range>,
> 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 b35435c2669..d233b037d1a 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 00000000000..5cc91b67d27
> --- /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 <algorithm>
> +#include <ranges>
> +#include <testsuite_iterators.h>
> +
> +#if __cpp_lib_fold != 202207L
> +# error "Feature-test macro __cpp_lib_fold has wrong value in <algorithm>"
> +#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<int> 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 00000000000..b08b57c6364
> --- /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 <algorithm>
> +#include <ranges>
> +#include <testsuite_iterators.h>
> +
> +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<decltype(v)>
> + && !ranges::random_access_range<decltype(v)> );
> + 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.40.0.335.g9857273be0
>
