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.129.124]) by sourceware.org (Postfix) with ESMTPS id 357293858D37 for ; Fri, 14 Apr 2023 04:00:46 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 357293858D37 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=1681444845; 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: content-transfer-encoding:content-transfer-encoding; bh=fDUcR7lqpw/K/zDdxsp8i0uc3zLsz0bZcaSyd7DEIiQ=; b=CBQAHtoPKOpW2lybWIPgU5jf+MNWBsi0kTbsiUOLS1gT04A0zduONMnXcipp+52uKGdu+d K33pTV/Hwz+HAaiO0iXZxAHGhtZWh3bGv3WI/yh/Xeofx31m/7RzlDITkl6oRkx518VW7c N41BMqQawKJ5leZr9ExEgMJ3B6Eiv7U= Received: from mail-qt1-f200.google.com (mail-qt1-f200.google.com [209.85.160.200]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_256_GCM_SHA384) id us-mta-213-vS_kk8joMraGKvxd1o4ETw-1; Fri, 14 Apr 2023 00:00:44 -0400 X-MC-Unique: vS_kk8joMraGKvxd1o4ETw-1 Received: by mail-qt1-f200.google.com with SMTP id 13-20020ac8590d000000b003eaf7aca024so686288qty.22 for ; Thu, 13 Apr 2023 21:00:43 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1681444843; x=1684036843; h=content-transfer-encoding:mime-version:message-id:date:subject:cc :to:from:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=fDUcR7lqpw/K/zDdxsp8i0uc3zLsz0bZcaSyd7DEIiQ=; b=ULXA3LovkgV+EKP1+hrjC/QOGPthQfgGKJ+uC4p+Si71kRgD2o2KRbqtcV2ewOE4Qr g2lAHGlbWfrUmhbVDwJel84s8dqMR1cNwYx7Uo5YACtyK3xAXv2+Ure1+vDyuZR8BTZC rTbLKZAyigdw7oMV3GLhdetzLUJC9IfVhCOik3frXiDvnAcQZHj70HVjMApw3t1nUdnh TtCLnad4ZrJ978D59UD3mOxPRsLF3mO7EPPyDzNEpFBBwp+TT219ClwQz2VAcO9zYkrD mAXQC3AMmFfwojBOoGKMiYEOKtMNNvfPMV1hHKnaSqzXDPTivglP9ZY7IBHB6+pidjZD REHg== X-Gm-Message-State: AAQBX9cSt52Vb6TPPsbI9Xtbq8ayTwfUMqPn1GM+91lrqIZFv6Mn1RYB FgYqaYsBiewzpKIBSfVgB3GID9FF9gFfZ58c95IUucD+OXgUA4J/cpXKPukyvym3x//0oRV8g+h L/rxmEfjjH+/Ss+Y= X-Received: by 2002:a05:6214:3011:b0:5ef:43d6:f910 with SMTP id ke17-20020a056214301100b005ef43d6f910mr1072209qvb.21.1681444843007; Thu, 13 Apr 2023 21:00:43 -0700 (PDT) X-Google-Smtp-Source: AKy350aehb3eWCXvqn8YJ8pg19XQQzy9u33EYJahnU8QL/SPVOd6dcjX7HZvwzYsIkqLirVE/pj5qQ== X-Received: by 2002:a05:6214:3011:b0:5ef:43d6:f910 with SMTP id ke17-20020a056214301100b005ef43d6f910mr1072169qvb.21.1681444842520; Thu, 13 Apr 2023 21:00:42 -0700 (PDT) Received: from localhost.localdomain (ool-457670bb.dyn.optonline.net. [69.118.112.187]) by smtp.gmail.com with ESMTPSA id m3-20020a0cfba3000000b005dd8b93457asm886721qvp.18.2023.04.13.21.00.41 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 13 Apr 2023 21:00:42 -0700 (PDT) From: Patrick Palka To: gcc-patches@gcc.gnu.org Cc: libstdc++@gcc.gnu.org, Patrick Palka Subject: [PATCH] libstdc++: Implement ranges::fold_* from P2322R6 Date: Fri, 14 Apr 2023 00:00:38 -0400 Message-ID: <20230414040038.1498807-1-ppalka@redhat.com> X-Mailer: git-send-email 2.40.0.335.g9857273be0 MIME-Version: 1.0 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Transfer-Encoding: 8bit Content-Type: text/plain; charset="US-ASCII"; x-default=true X-Spam-Status: No, score=-13.4 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 autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org List-Id: Tested on x86_64-pc-linux-gnu, does this look OK for trunk? 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 + 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 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