From: Jonathan Wakely <jwakely@redhat.com>
To: Patrick Palka <ppalka@redhat.com>
Cc: gcc-patches@gcc.gnu.org, libstdc++@gcc.gnu.org
Subject: Re: [PATCH] libstdc++: Implement ranges::fold_* from P2322R6
Date: Fri, 14 Apr 2023 10:49:30 +0100 [thread overview]
Message-ID: <CACb0b4=EDiivSp62+HkNfP3+x=3X-Bo4sQvjs_=UzHzz0ORwFQ@mail.gmail.com> (raw)
In-Reply-To: <20230414040038.1498807-1-ppalka@redhat.com>
On Fri, 14 Apr 2023 at 05:01, Patrick Palka via Libstdc++
<libstdc++@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
>
prev parent reply other threads:[~2023-04-14 9:49 UTC|newest]
Thread overview: 2+ messages / expand[flat|nested] mbox.gz Atom feed top
2023-04-14 4:00 Patrick Palka
2023-04-14 9:49 ` Jonathan Wakely [this message]
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to='CACb0b4=EDiivSp62+HkNfP3+x=3X-Bo4sQvjs_=UzHzz0ORwFQ@mail.gmail.com' \
--to=jwakely@redhat.com \
--cc=gcc-patches@gcc.gnu.org \
--cc=libstdc++@gcc.gnu.org \
--cc=ppalka@redhat.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).