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 8FD4E385840F for ; Thu, 1 Sep 2022 11:14:53 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 8FD4E385840F 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=1662030893; 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=3/FB1oRIW7laSJRoSNRt2XMx0rGdRrrYwR5m41uKITg=; b=blTnA7rmJ4s5BsSwKzxygiB38w9f0/KKUt1UzIVrtOkuoxNPJarM4E1gtGCRf1vqmvcYt5 517vbh1aNEtO9yc2FTeywpoK5NKfWH7WLkE+WBg/qfx24z8G9EXLKtJIl00TC3YSBcQ8OR hJ1yAiHUeC1YDgM7ti8VQfI2NVWzCQg= 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_128_GCM_SHA256) id us-mta-441-ufBsfiU6Msa4b13kx4ABNQ-1; Thu, 01 Sep 2022 07:14:52 -0400 X-MC-Unique: ufBsfiU6Msa4b13kx4ABNQ-1 Received: by mail-qt1-f200.google.com with SMTP id o22-20020ac85a56000000b0034481129ce6so13366751qta.19 for ; Thu, 01 Sep 2022 04:14:52 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:x-gm-message-state:from:to:cc:subject:date; bh=3/FB1oRIW7laSJRoSNRt2XMx0rGdRrrYwR5m41uKITg=; b=MRaO1Nidb857WSwwI4g3sbHH94M+k7QNIKBZQDPQr68/moHT4FjkDgyJQMV7YrVxiF eIVdHLMDY1SEn0LsNTIiWWlaJzT6lloG+T+JQLOjJusv5nUtldA6HwBWvD36bpLvUPZv 9aAPd7kbnIuxavNtvqOZxthpMXxianxfz6j8QAl3R9vzqH60E3hymsiayN2WaE8BE1qC UZzF957mgJmga7q3Q307XZ5ns2yOdmQ6M1UK/AOKqG8Q8ijirw9fv8etQB7zrB4bkleA 5DvQQJOE5tDUWKR4htjoMzTuSwMJoaP7pWgyJYmNIGxUt3GSHFpWAJ9M/OFhmuiWn1PX qOXg== X-Gm-Message-State: ACgBeo0pfdA9PylzOAnJOyOR6tzy4fVRnHS+bB/9fx6HN6wsG/OGh7Xb VGuZWErF7j/MiEDbYttcFxQVrSbjCDVbn4/qjIR41/phXmRCBUKXiKu8jZct554Z7ahUn04V9h2 AUHazY9lKGYtE+dPWh8P8AE/kO3mxkcw= X-Received: by 2002:ac8:5b15:0:b0:343:6789:193a with SMTP id m21-20020ac85b15000000b003436789193amr22439974qtw.647.1662030891578; Thu, 01 Sep 2022 04:14:51 -0700 (PDT) X-Google-Smtp-Source: AA6agR7EsAbW3sSS6wOmcMDvUs8swSR/QSSta9uMQH2mxq8ycPjvveSP1fLS3vkq8SxPVCThPzFKC9pFW0/YjubKnmo= X-Received: by 2002:ac8:5b15:0:b0:343:6789:193a with SMTP id m21-20020ac85b15000000b003436789193amr22439944qtw.647.1662030891247; Thu, 01 Sep 2022 04:14:51 -0700 (PDT) MIME-Version: 1.0 References: <20220830171335.54110-1-ppalka@redhat.com> <20220830171335.54110-2-ppalka@redhat.com> In-Reply-To: <20220830171335.54110-2-ppalka@redhat.com> From: Jonathan Wakely Date: Thu, 1 Sep 2022 12:14:40 +0100 Message-ID: Subject: Re: [PATCH 2/2] libstdc++: Implement ranges::adjacent_transform_view from P2321R2 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=-12.3 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_LOW,SPF_HELO_NONE,SPF_NONE,TXREP,T_SCC_BODY_TEXT_LINE 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: On Tue, 30 Aug 2022 at 18:14, Patrick Palka via Libstdc++ wrote: > > Tested on x86_64-pc-linux-gnu, does this look OK for trunk? OK > > libstdc++-v3/ChangeLog: > > * include/std/ranges (__detail::__unarize): Define. > (adjacent_view::_Iterator): Befriend adjacent_transform_view. > (adjacent_transform_view): Define. > (adjacent_transform_view::_Iterator): Define. > (adjacent_transform_view::_Sentinel): Define. > (views::__detail::__can_adjacent_transform_view): Define. > (views::_AdjacentTransform): Define. > (views::adjacent_transform): Define. > (views::pairwise): Define. > * testsuite/std/ranges/adaptors/adjacent_transform/1.cc: New test. > --- > libstdc++-v3/include/std/ranges | 342 ++++++++++++++++++ > .../ranges/adaptors/adjacent_transform/1.cc | 106 ++++++ > 2 files changed, 448 insertions(+) > create mode 100644 libstdc++-v3/testsuite/std/ranges/adaptors/adjacent_transform/1.cc > > diff --git a/libstdc++-v3/include/std/ranges b/libstdc++-v3/include/std/ranges > index 4fb879a088c..3a7f0545030 100644 > --- a/libstdc++-v3/include/std/ranges > +++ b/libstdc++-v3/include/std/ranges > @@ -5158,6 +5158,20 @@ namespace views::__adaptor > // Yields tuple<_Tp, ..., _Tp> with _Nm elements. > template > using __repeated_tuple = decltype(std::tuple_cat(std::declval>())); > + > + // For a functor F that takes N arguments, the expression declval<__unarize>(x) > + // is equivalent to declval(x, ..., x). > + template > + struct __unarize > + { > + template > + static invoke_result_t<_Fp, _Ts...> > + __tuple_apply(const tuple<_Ts...>&); // not defined > + > + template > + decltype(__tuple_apply(std::declval<__repeated_tuple<_Tp, _Nm>>())) > + operator()(_Tp&&); // not defined > + }; > } > > template > @@ -5205,6 +5219,13 @@ namespace views::__adaptor > > friend class adjacent_view; > > + template > + requires view<_Wp> && (_Mm > 0) && is_object_v<_Fp> > + && regular_invocable<__detail::__unarize<_Fp&, _Mm>, range_reference_t<_Wp>> > + && std::__detail::__can_reference, > + range_reference_t<_Wp>>> > + friend class adjacent_transform_view; > + > public: > using iterator_category = input_iterator_tag; > using iterator_concept = decltype(_S_iter_concept()); > @@ -5440,6 +5461,327 @@ namespace views::__adaptor > > inline constexpr auto pairwise = adjacent<2>; > } > + > + template > + requires view<_Vp> && (_Nm > 0) && is_object_v<_Fp> > + && regular_invocable<__detail::__unarize<_Fp&, _Nm>, range_reference_t<_Vp>> > + && std::__detail::__can_reference, > + range_reference_t<_Vp>>> > + class adjacent_transform_view : public view_interface> > + { > + [[no_unique_address]] __detail::__box<_Fp> _M_fun; > + adjacent_view<_Vp, _Nm> _M_inner; > + > + using _InnerView = adjacent_view<_Vp, _Nm>; > + > + template > + using _InnerIter = iterator_t<__detail::__maybe_const_t<_Const, _InnerView>>; > + > + template > + using _InnerSent = sentinel_t<__detail::__maybe_const_t<_Const, _InnerView>>; > + > + template class _Iterator; > + template class _Sentinel; > + > + public: > + adjacent_transform_view() = default; > + > + constexpr explicit > + adjacent_transform_view(_Vp __base, _Fp __fun) > + : _M_fun(std::move(__fun)), _M_inner(std::move(__base)) > + { } > + > + constexpr auto > + begin() > + { return _Iterator(*this, _M_inner.begin()); } > + > + constexpr auto > + begin() const > + requires range > + && regular_invocable<__detail::__unarize, > + range_reference_t> > + { return _Iterator(*this, _M_inner.begin()); } > + > + constexpr auto > + end() > + { > + if constexpr (common_range<_InnerView>) > + return _Iterator(*this, _M_inner.end()); > + else > + return _Sentinel(_M_inner.end()); > + } > + > + constexpr auto > + end() const > + requires range > + && regular_invocable<__detail::__unarize, > + range_reference_t> > + { > + if constexpr (common_range) > + return _Iterator(*this, _M_inner.end()); > + else > + return _Sentinel(_M_inner.end()); > + } > + > + constexpr auto > + size() requires sized_range<_InnerView> > + { return _M_inner.size(); } > + > + constexpr auto > + size() const requires sized_range > + { return _M_inner.size(); } > + }; > + > + template > + requires view<_Vp> && (_Nm > 0) && is_object_v<_Fp> > + && regular_invocable<__detail::__unarize<_Fp&, _Nm>, range_reference_t<_Vp>> > + && std::__detail::__can_reference, > + range_reference_t<_Vp>>> > + template > + class adjacent_transform_view<_Vp, _Fp, _Nm>::_Iterator > + { > + using _Parent = __detail::__maybe_const_t<_Const, adjacent_transform_view>; > + using _Base = __detail::__maybe_const_t<_Const, _Vp>; > + > + _Parent* _M_parent = nullptr; > + _InnerIter<_Const> _M_inner; > + > + constexpr > + _Iterator(_Parent& __parent, _InnerIter<_Const> __inner) > + : _M_parent(std::__addressof(__parent)), _M_inner(std::move(__inner)) > + { } > + > + static auto > + _S_iter_cat() > + { > + using __detail::__maybe_const_t; > + using __detail::__unarize; > + using _Res = invoke_result_t<__unarize<__maybe_const_t<_Const, _Fp>&, _Nm>, > + range_reference_t<_Base>>; > + using _Cat = iterator_traits>::iterator_category; > + if constexpr (!is_lvalue_reference_v<_Res>) > + return input_iterator_tag{}; > + else if constexpr (derived_from<_Cat, random_access_iterator_tag>) > + return random_access_iterator_tag{}; > + else if constexpr (derived_from<_Cat, bidirectional_iterator_tag>) > + return bidirectional_iterator_tag{}; > + else if constexpr (derived_from<_Cat, forward_iterator_tag>) > + return forward_iterator_tag{}; > + else > + return input_iterator_tag{}; > + } > + > + friend class adjacent_transform_view; > + > + public: > + using iterator_category = decltype(_S_iter_cat()); > + using iterator_concept = typename _InnerIter<_Const>::iterator_concept; > + using value_type > + = remove_cvref_t + <__detail::__unarize<__detail::__maybe_const_t<_Const, _Fp>&, _Nm>, > + range_reference_t<_Base>>>; > + using difference_type = range_difference_t<_Base>; > + > + _Iterator() = default; > + > + constexpr > + _Iterator(_Iterator __i) > + requires _Const && convertible_to<_InnerIter, _InnerIter<_Const>> > + : _M_parent(__i._M_parent), _M_inner(std::move(__i._M_inner)) > + { } > + > + constexpr decltype(auto) > + operator*() const > + { > + return std::apply([&](const auto&... __iters) -> decltype(auto) { > + return std::__invoke(*_M_parent->_M_fun, *__iters...); > + }, _M_inner._M_current); > + } > + > + constexpr _Iterator& > + operator++() > + { > + ++_M_inner; > + return *this; > + } > + > + constexpr _Iterator > + operator++(int) > + { > + auto __tmp = *this; > + ++*this; > + return __tmp; > + } > + > + constexpr _Iterator& > + operator--() requires bidirectional_range<_Base> > + { > + --_M_inner; > + return *this; > + } > + > + constexpr _Iterator > + operator--(int) requires bidirectional_range<_Base> > + { > + auto __tmp = *this; > + --*this; > + return __tmp; > + } > + > + constexpr _Iterator& > + operator+=(difference_type __x) requires random_access_range<_Base> > + { > + _M_inner += __x; > + return *this; > + } > + > + constexpr _Iterator& > + operator-=(difference_type __x) requires random_access_range<_Base> > + { > + _M_inner -= __x; > + return *this; > + } > + > + constexpr decltype(auto) > + operator[](difference_type __n) const requires random_access_range<_Base> > + { > + return std::apply([&](const auto&... __iters) -> decltype(auto) { > + return std::__invoke(*_M_parent->_M_fun, __iters[__n]...); > + }, _M_inner._M_current); > + } > + > + friend constexpr bool > + operator==(const _Iterator& __x, const _Iterator& __y) > + { return __x._M_inner == __y._M_inner; } > + > + friend constexpr bool > + operator<(const _Iterator& __x, const _Iterator& __y) > + requires random_access_range<_Base> > + { return __x._M_inner < __y._M_inner; } > + > + friend constexpr bool > + operator>(const _Iterator& __x, const _Iterator& __y) > + requires random_access_range<_Base> > + { return __x._M_inner > __y._M_inner; } > + > + friend constexpr bool > + operator<=(const _Iterator& __x, const _Iterator& __y) > + requires random_access_range<_Base> > + { return __x._M_inner <= __y._M_inner; } > + > + friend constexpr bool > + operator>=(const _Iterator& __x, const _Iterator& __y) > + requires random_access_range<_Base> > + { return __x._M_inner >= __y._M_inner; } > + > + friend constexpr auto > + operator<=>(const _Iterator& __x, const _Iterator& __y) > + requires random_access_range<_Base> && > + three_way_comparable<_InnerIter<_Const>> > + { return __x._M_inner <=> __y._M_inner; } > + > + friend constexpr _Iterator > + operator+(const _Iterator& __i, difference_type __n) > + requires random_access_range<_Base> > + { return _Iterator(*__i._M_parent, __i._M_inner + __n); } > + > + friend constexpr _Iterator > + operator+(difference_type __n, const _Iterator& __i) > + requires random_access_range<_Base> > + { return _Iterator(*__i._M_parent, __i._M_inner + __n); } > + > + friend constexpr _Iterator > + operator-(const _Iterator& __i, difference_type __n) > + requires random_access_range<_Base> > + { return _Iterator(*__i._M_parent, __i._M_inner - __n); } > + > + friend constexpr difference_type > + operator-(const _Iterator& __x, const _Iterator& __y) > + requires sized_sentinel_for<_InnerIter<_Const>, _InnerIter<_Const>> > + { return __x._M_inner - __y._M_inner; } > + }; > + > + template > + requires view<_Vp> && (_Nm > 0) && is_object_v<_Fp> > + && regular_invocable<__detail::__unarize<_Fp&, _Nm>, range_reference_t<_Vp>> > + && std::__detail::__can_reference, > + range_reference_t<_Vp>>> > + template > + class adjacent_transform_view<_Vp, _Fp, _Nm>::_Sentinel > + { > + _InnerSent<_Const> _M_inner; > + > + constexpr explicit > + _Sentinel(_InnerSent<_Const> __inner) > + : _M_inner(__inner) > + { } > + > + friend class adjacent_transform_view; > + > + public: > + _Sentinel() = default; > + > + constexpr > + _Sentinel(_Sentinel __i) > + requires _Const && convertible_to<_InnerSent, _InnerSent<_Const>> > + : _M_inner(std::move(__i._M_inner)) > + { } > + > + template > + requires sentinel_for<_InnerSent<_Const>, _InnerIter<_OtherConst>> > + friend constexpr bool > + operator==(const _Iterator<_OtherConst>& __x, const _Sentinel& __y) > + { return __x._M_inner == __y._M_inner; } > + > + template > + requires sized_sentinel_for<_InnerSent<_Const>, _InnerIter<_OtherConst>> > + friend constexpr range_difference_t<__detail::__maybe_const_t<_OtherConst, _InnerView>> > + operator-(const _Iterator<_OtherConst>& __x, const _Sentinel& __y) > + { return __x._M_inner - __y._M_inner; } > + > + template > + requires sized_sentinel_for<_InnerSent<_Const>, _InnerIter<_OtherConst>> > + friend constexpr range_difference_t<__detail::__maybe_const_t<_OtherConst, _InnerView>> > + operator-(const _Sentinel& __x, const _Iterator<_OtherConst>& __y) > + { return __x._M_inner - __y._M_inner; } > + }; > + > + namespace views > + { > + namespace __detail > + { > + template > + concept __can_adjacent_transform_view > + = requires { adjacent_transform_view, decay_t<_Fp>, _Nm> > + (std::declval<_Range>(), std::declval<_Fp>()); }; > + } > + > + template > + struct _AdjacentTransform : __adaptor::_RangeAdaptor<_AdjacentTransform<_Nm>> > + { > + template > + requires (_Nm == 0) || __detail::__can_adjacent_transform_view<_Nm, _Range, _Fp> > + [[nodiscard]] > + constexpr auto > + operator()(_Range&& __r, _Fp&& __f) const > + { > + if constexpr (_Nm == 0) > + return views::empty>; > + else > + return adjacent_transform_view, decay_t<_Fp>, _Nm> > + (std::forward<_Range>(__r), std::forward<_Fp>(__f)); > + } > + > + using __adaptor::_RangeAdaptor<_AdjacentTransform>::operator(); > + static constexpr int _S_arity = 2; > + static constexpr bool _S_has_simple_extra_args = true; > + }; > + > + template > + inline constexpr _AdjacentTransform<_Nm> adjacent_transform; > + > + inline constexpr auto pairwise_transform = adjacent_transform<2>; > + } > #endif // C++23 > } // namespace ranges > > diff --git a/libstdc++-v3/testsuite/std/ranges/adaptors/adjacent_transform/1.cc b/libstdc++-v3/testsuite/std/ranges/adaptors/adjacent_transform/1.cc > new file mode 100644 > index 00000000000..07f20b702dd > --- /dev/null > +++ b/libstdc++-v3/testsuite/std/ranges/adaptors/adjacent_transform/1.cc > @@ -0,0 +1,106 @@ > +// { dg-options "-std=gnu++23" } > +// { dg-do run { target c++23 } } > + > +#include > +#include > +#include > +#include > +#include > + > +namespace ranges = std::ranges; > +namespace views = std::views; > + > +constexpr bool > +test01() > +{ > + auto v1 = std::array{1, 2, 3} | views::adjacent_transform<1>(std::identity{}); > + VERIFY( ranges::equal(v1, (int[]){1, 2, 3}) ); > + const auto i0 = v1.begin(), i1 = v1.begin() + 1; > + VERIFY( i0 + 1 - 1 == i0 ); > + VERIFY( i0 < i1 ); > + VERIFY( i1 < v1.end() ); > + VERIFY( i1 - i0 == 1 ); > + VERIFY( i0 - i1 == -1 ); > + VERIFY( v1.end() - i1 == 2 ); > + VERIFY( i1 - v1.end() == -2 ); > + ranges::iter_swap(i0, i1); > + VERIFY( ranges::equal(std::move(v1), (int[]){2, 1, 3}) ); > + > + auto v2 = std::array{1, -1, 2, -2} | views::pairwise_transform(std::multiplies{}); > + auto i2 = v2.begin(); > + i2 += 1; > + i2 -= -2; > + VERIFY( i2 == v2.end() ); > + VERIFY( ranges::size(v2) == 3 ); > + VERIFY( ranges::size(std::as_const(v2)) == 3 ); > + VERIFY( ranges::equal(v2, (int[]){-1, -2, -4}) ); > + > + int y[] = {1, 2, 3, 4, 5, 6}; > + auto v3 = y | views::adjacent_transform<3>([](auto... xs) { return ranges::max({xs...}); }); > + VERIFY( ranges::size(v3) == 4 ); > + VERIFY( ranges::equal(v3, (int[]){3, 4, 5, 6}) ); > + > + const auto v6 = y | views::adjacent_transform<6>([](auto...) { return 0; }); > + VERIFY( ranges::equal(v6, (int[]){0}) ); > + > + const auto v7 = y | views::adjacent_transform<7>([](auto...) { return 0; }); > + VERIFY( ranges::empty(v7) ); > + > + const auto v0 = y | views::adjacent_transform<0>([] { return 0; }); > + VERIFY( ranges::empty(v0) ); > + > + return true; > +} > + > +constexpr bool > +test02() > +{ > + using __gnu_test::test_input_range; > + using __gnu_test::test_forward_range; > + using __gnu_test::test_random_access_range; > + > + using ty1 = ranges::adjacent_transform_view>, > + std::plus<>, 2>; > + static_assert(ranges::forward_range); > + static_assert(!ranges::bidirectional_range); > + static_assert(!ranges::sized_range); > + > + using ty2 = ranges::adjacent_transform_view>, > + decltype([](int, int, int) { return 0;}), 3>; > + static_assert(ranges::random_access_range); > + static_assert(ranges::sized_range); > + > + return true; > +} > + > +constexpr bool > +test03() > +{ > + auto v = views::iota(0, 4) > + | views::filter([](auto) { return true; }) > + | views::pairwise_transform(std::plus{}); > + using ty = decltype(v); > + static_assert(ranges::forward_range); > + static_assert(ranges::common_range); > + static_assert(!ranges::sized_range); > + VERIFY( v.begin() == v.begin() ); > + VERIFY( v.begin() != v.end() ); > + VERIFY( ranges::next(v.begin(), 3) == v.end() ); > + auto it = v.begin(); > + ++it; > + it++; > + VERIFY( ranges::next(it) == v.end() ); > + it--; > + --it; > + VERIFY( it == v.begin() ); > + > + return true; > +} > + > +int > +main() > +{ > + static_assert(test01()); > + static_assert(test02()); > + static_assert(test03()); > +} > -- > 2.37.2.490.g6c8e4ee870 >