From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.133.124]) by sourceware.org (Postfix) with ESMTPS id 53D9D3858D32 for ; Fri, 14 Apr 2023 09:49:45 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 53D9D3858D32 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=redhat.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=redhat.com DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1681465785; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version:content-type:content-type: in-reply-to:in-reply-to:references:references; bh=g4z67C/4pFki3ZWx6r3BfCD3E69g1LYmzpbtAHp6Wew=; b=jVxCLIs92DRqmT53IJOKcfuSn7uLoqlbrC1qELu5QUEFiJtLvzfrtphIAipEcIdL/nsdUT d7YWcl+GZLcMkH3BS2YcL5LLuzU4zQTlbLWv+iBPY4Frc/FNYbdQH5aTbuZOhsbX98XwYB GR859BJsq98sJCqc85u5RiWlD6dKKvQ= Received: from mail-lf1-f69.google.com (mail-lf1-f69.google.com [209.85.167.69]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_256_GCM_SHA384) id us-mta-436-PS2Cn99qOe-oMtZ0z-Tpbg-1; Fri, 14 Apr 2023 05:49:43 -0400 X-MC-Unique: PS2Cn99qOe-oMtZ0z-Tpbg-1 Received: by mail-lf1-f69.google.com with SMTP id g28-20020a19e05c000000b004edaf554a64so1402055lfj.20 for ; Fri, 14 Apr 2023 02:49:43 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1681465782; x=1684057782; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=g4z67C/4pFki3ZWx6r3BfCD3E69g1LYmzpbtAHp6Wew=; b=iqhdOkpHUwSZmWeXFcbE/IcLfpbQFqatWywwHA6RymEQ0YQcNwD+bVI/Vv+c/dtcqi 3wu+Az5vtcc1v5BLUy0V3FQB6bdMlMMHopAK0dlUCelanPKNe/XU364qjThOHgg2HqjQ zKhrz2LT2StvdHDmW5OoafIXFwmElA7RZ3k3obI7pa+IZ51PztPtxwZUWnp1Hq/X46Yh BFMl+ylh+Wqcoi6HIuJS1ipGL31QJg6OeLXsM+rH9jTHfd6kBXu2rWAIgp8sJcpVbpof XeIP4hqaQ+nGBOjSGCaELlH89oq/I9FRe9lfKZOdcJQUucoKNtr6wo1EFj4px2a1VECw T85g== X-Gm-Message-State: AAQBX9f48OBM0espXxOiqs44/lkgkwpir7UxpTABMlnvnMV+oOaTPeIw BQH9wxh4WydLfZaum4I8UfSiWLqqDdckLClj36R77kwoVZeSORtqY2B23fWfmUSvIcyAZUd+v87 L192rnJcuIvb9tzukBMHreQ3T4NSTIMA= X-Received: by 2002:ac2:4893:0:b0:4ec:8f8d:88f8 with SMTP id x19-20020ac24893000000b004ec8f8d88f8mr1668750lfc.8.1681465781822; Fri, 14 Apr 2023 02:49:41 -0700 (PDT) X-Google-Smtp-Source: AKy350a9w5GqZNwPOZlQEAtnYz+v1NDpIeKLAjz6RKZyorqUlw152/EEXjvVSmO+cTNYIy4lBsPt4zu63oULxFzpk0E= X-Received: by 2002:ac2:4893:0:b0:4ec:8f8d:88f8 with SMTP id x19-20020ac24893000000b004ec8f8d88f8mr1668743lfc.8.1681465781455; Fri, 14 Apr 2023 02:49:41 -0700 (PDT) MIME-Version: 1.0 References: <20230414040038.1498807-1-ppalka@redhat.com> In-Reply-To: <20230414040038.1498807-1-ppalka@redhat.com> From: Jonathan Wakely Date: Fri, 14 Apr 2023 10:49:30 +0100 Message-ID: Subject: Re: [PATCH] libstdc++: Implement ranges::fold_* from P2322R6 To: Patrick Palka Cc: gcc-patches@gcc.gnu.org, libstdc++@gcc.gnu.org X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Type: text/plain; charset="UTF-8" X-Spam-Status: No, score=-13.1 required=5.0 tests=BAYES_00,DKIMWL_WL_HIGH,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,GIT_PATCH_0,KAM_NUMSUBJECT,RCVD_IN_DNSWL_NONE,RCVD_IN_MSPIKE_H2,SPF_HELO_NONE,SPF_NONE,TXREP,T_SCC_BODY_TEXT_LINE autolearn=unavailable autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org List-Id: On Fri, 14 Apr 2023 at 05:01, Patrick Palka via Libstdc++ 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 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 > +#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 + 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>>; > + 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 + __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 _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 + __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 > + 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 + __detail::__indirectly_binary_left_foldable, 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 + __detail::__indirectly_binary_left_foldable, 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 + __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 _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 + __detail::__indirectly_binary_right_foldable, 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 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 > +#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 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 > +#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.40.0.335.g9857273be0 >