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 E7545385114E for ; Thu, 25 Aug 2022 15:40:10 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org E7545385114E 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=1661442010; 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=XFSBArmRVuSKfpxCOpwn2JghhHg5RdweiFL52SVx6fM=; b=FSew7FMd1Ghlv7VBXE2bMw4fuUtmA068mXugtoxlESmScx0I04tRcFAwDqWqOKwJ9nRZ0C wExydK2oO5GyA3DQpKCYGh63UbTKoysPj5vQKDVho0h9ZoO5Mpd5FSFny7T3/AGQKKaHtW M3x6VpPAsNSYEH+J+hI6qxfVGfHeVsM= Received: from mail-qt1-f197.google.com (mail-qt1-f197.google.com [209.85.160.197]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_128_GCM_SHA256) id us-mta-344-3W32m4bhMEeo_HBGOPMt8Q-1; Thu, 25 Aug 2022 11:40:04 -0400 X-MC-Unique: 3W32m4bhMEeo_HBGOPMt8Q-1 Received: by mail-qt1-f197.google.com with SMTP id z6-20020ac875c6000000b0034454b14c91so15479801qtq.15 for ; Thu, 25 Aug 2022 08:40:04 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=content-transfer-encoding:mime-version:message-id:date:subject:cc :to:from:x-gm-message-state:from:to:cc; bh=XFSBArmRVuSKfpxCOpwn2JghhHg5RdweiFL52SVx6fM=; b=NRUa5QExWS/tKlPKJx/+e2TkS1w/BqchGVKE0yUAQTnpieL++Nm8yuwGqRuREL6/go hi3NY6sHx0fAcGAvXMoQmJBm/iDkac7jrv1jFRpb09ChZ788ZjmD5rR7HI3dTJXWE3h0 QTnw48YJ/MDBp/Ew9EhJCWy1A3fZnMs9Gy/LoomuIfbXRGilngmQjyYLpQ8aL5tlSnOB ZbVI6SjJ1lusSnilfG63/g4v7dfqi9Pl1EBdAndD8Uh/m9oKf7eV1qWBrSFMADYDymeH fO6C0zRlu/1gsCIpl8A8SsdU7wKaEqrmpHOZGXL29+kr8u7jQV8rbhKSiCfr3Nkr6vj7 j64A== X-Gm-Message-State: ACgBeo2XMiGOHoO4wikb34ilFkNABOcgDFhnzPFp7gZ/1TPM3AK9pzgT tRJZZZZ9zjDtP+MgjWEQHD+FCbPVQc/Nkk1Z60cyLb2spNtqq3ME3mV/j7w+EDqByS+E9qvHUCm oPVm49+oGUm5QO9A= X-Received: by 2002:ac8:5dd3:0:b0:344:94e6:d667 with SMTP id e19-20020ac85dd3000000b0034494e6d667mr4140023qtx.409.1661442003451; Thu, 25 Aug 2022 08:40:03 -0700 (PDT) X-Google-Smtp-Source: AA6agR4L0OGtDhxa78M8/uMBaGqeUAmfQqJ/0yw6a481w68dxjmuW39Ftjnft2Den0B00qFtt7KSSg== X-Received: by 2002:ac8:5dd3:0:b0:344:94e6:d667 with SMTP id e19-20020ac85dd3000000b0034494e6d667mr4139998qtx.409.1661442003137; Thu, 25 Aug 2022 08:40:03 -0700 (PDT) Received: from localhost.localdomain (ool-457670bb.dyn.optonline.net. [69.118.112.187]) by smtp.gmail.com with ESMTPSA id j27-20020a05620a147b00b006ba9b2167a2sm16033677qkl.16.2022.08.25.08.40.02 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 25 Aug 2022 08:40:02 -0700 (PDT) From: Patrick Palka To: gcc-patches@gcc.gnu.org Cc: libstdc++@gcc.gnu.org, Patrick Palka Subject: [PATCH 1/2] libstdc++: Implement ranges::zip_transform_view from P2321R2 Date: Thu, 25 Aug 2022 11:39:37 -0400 Message-Id: <20220825153938.2249619-1-ppalka@redhat.com> X-Mailer: git-send-email 2.37.2.382.g795ea8776b 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.7 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,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: Tested on x86_64-pc-linux-gnu, does this look OK for trunk? libstdc++-v3/ChangeLog: * include/std/ranges (zip_view::_Iterator): Befriend zip_transform_view. (__detail::__range_iter_cat): Define. (zip_transform_view): Define. (zip_transform_view::_Iterator): Define. (zip_transform_view::_Sentinel): Define. (views::__detail::__can_zip_transform_view): Define. (views::_ZipTransform): Define. (views::zip_transform): Define. * testsuite/std/ranges/zip_transform/1.cc: New test. --- libstdc++-v3/include/std/ranges | 343 ++++++++++++++++++ .../testsuite/std/ranges/zip_transform/1.cc | 108 ++++++ 2 files changed, 451 insertions(+) create mode 100644 libstdc++-v3/testsuite/std/ranges/zip_transform/1.cc diff --git a/libstdc++-v3/include/std/ranges b/libstdc++-v3/include/std/ranges index fb815c48f99..d748cb73346 100644 --- a/libstdc++-v3/include/std/ranges +++ b/libstdc++-v3/include/std/ranges @@ -4502,6 +4502,12 @@ namespace views::__adaptor return input_iterator_tag{}; } + template + requires (view<_Ws> && ...) && (sizeof...(_Ws) > 0) && is_object_v<_Fp> + && regular_invocable<_Fp&, range_reference_t<_Ws>...> + && std::__detail::__can_reference...>> + friend class zip_transform_view; + public: // iterator_category defined in __zip_view_iter_cat using iterator_concept = decltype(_S_iter_concept()); @@ -4781,6 +4787,343 @@ namespace views::__adaptor inline constexpr _Zip zip; } + + namespace __detail + { + template + using __range_iter_cat + = typename iterator_traits>>::iterator_category; + } + + template + requires (view<_Vs> && ...) && (sizeof...(_Vs) > 0) && is_object_v<_Fp> + && regular_invocable<_Fp&, range_reference_t<_Vs>...> + && std::__detail::__can_reference...>> + class zip_transform_view : public view_interface> + { + [[no_unique_address]] __detail::__box<_Fp> _M_fun; + zip_view<_Vs...> _M_zip; + + using _InnerView = zip_view<_Vs...>; + + template + using __ziperator = iterator_t<__detail::__maybe_const_t<_Const, _InnerView>>; + + template + using __zentinel = sentinel_t<__detail::__maybe_const_t<_Const, _InnerView>>; + + template + using _Base = __detail::__maybe_const_t<_Const, _InnerView>; + + template + struct __iter_cat + { }; + + template + requires forward_range<_Base<_Const>> + struct __iter_cat<_Const> + { + private: + static auto + _S_iter_cat() + { + using __detail::__maybe_const_t; + using __detail::__range_iter_cat; + using _Res = invoke_result_t<__maybe_const_t<_Const, _Fp>&, + range_reference_t<__maybe_const_t<_Const, _Vs>>...>; + if constexpr (!is_lvalue_reference_v<_Res>) + return input_iterator_tag{}; + else if constexpr ((derived_from<__range_iter_cat<_Vs, _Const>, + random_access_iterator_tag> && ...)) + return random_access_iterator_tag{}; + else if constexpr ((derived_from<__range_iter_cat<_Vs, _Const>, + bidirectional_iterator_tag> && ...)) + return bidirectional_iterator_tag{}; + else if constexpr ((derived_from<__range_iter_cat<_Vs, _Const>, + forward_iterator_tag> && ...)) + return forward_iterator_tag{}; + else + return input_iterator_tag{}; + } + public: + using iterator_category = decltype(_S_iter_cat()); + }; + + template class _Iterator; + template class _Sentinel; + + public: + zip_transform_view() = default; + + constexpr explicit + zip_transform_view(_Fp __fun, _Vs... __views) + : _M_fun(std::move(__fun)), _M_zip(std::move(__views)...) + { } + + constexpr auto + begin() + { return _Iterator(*this, _M_zip.begin()); } + + constexpr auto + begin() const + requires range + && regular_invocable...> + { return _Iterator(*this, _M_zip.begin()); } + + constexpr auto + end() + { + if constexpr (common_range<_InnerView>) + return _Iterator(*this, _M_zip.end()); + else + return _Sentinel(_M_zip.end()); + } + + constexpr auto + end() const + requires range + && regular_invocable...> + { + if constexpr (common_range) + return _Iterator(*this, _M_zip.end()); + else + return _Sentinel(_M_zip.end()); + } + + constexpr auto + size() requires sized_range<_InnerView> + { return _M_zip.size(); } + + constexpr auto + size() const requires sized_range + { return _M_zip.size(); } + }; + + template + zip_transform_view(_Fp, Rs&&...) -> zip_transform_view<_Fp, views::all_t...>; + + template + requires (view<_Vs> && ...) && (sizeof...(_Vs) > 0) && is_object_v<_Fp> + && regular_invocable<_Fp&, range_reference_t<_Vs>...> + && std::__detail::__can_reference...>> + template + class zip_transform_view<_Fp, _Vs...>::_Iterator : public __iter_cat<_Const> + { + using _Parent = __detail::__maybe_const_t<_Const, zip_transform_view>; + + _Parent* _M_parent = nullptr; + __ziperator<_Const> _M_inner; + + constexpr + _Iterator(_Parent& __parent, __ziperator<_Const> __inner) + : _M_parent(std::__addressof(__parent)), _M_inner(std::move(__inner)) + { } + + friend class zip_transform_view; + + public: + // iterator_category defined in zip_transform_view::__iter_cat + using iterator_concept = typename __ziperator<_Const>::iterator_concept; + using value_type + = remove_cvref_t&, + range_reference_t<__detail::__maybe_const_t<_Const, _Vs>>...>>; + using difference_type = range_difference_t<_Base<_Const>>; + + _Iterator() = default; + + constexpr + _Iterator(_Iterator __i) + requires _Const && convertible_to<__ziperator, __ziperator<_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 void + operator++(int) + { + ++*this; + } + + constexpr _Iterator + operator++(int) requires forward_range<_Base<_Const>> + { + auto __tmp = *this; + ++*this; + return __tmp; + } + + constexpr _Iterator& + operator--() requires bidirectional_range<_Base<_Const>> + { + --_M_inner; + return *this; + } + + constexpr _Iterator + operator--(int) requires bidirectional_range<_Base<_Const>> + { + auto __tmp = *this; + --*this; + return __tmp; + } + + constexpr _Iterator& + operator+=(difference_type __x) requires random_access_range<_Base<_Const>> + { + _M_inner += __x; + return *this; + } + + constexpr _Iterator& + operator-=(difference_type __x) requires random_access_range<_Base<_Const>> + { + _M_inner -= __x; + return *this; + } + + constexpr decltype(auto) + operator[](difference_type __n) const requires random_access_range<_Base<_Const>> + { + return std::apply([&](const _Is&... __iters) -> decltype(auto) { + return std::__invoke(*_M_parent->_M_fun, __iters[iter_difference_t<_Is>(__n)]...); + }, _M_inner._M_current); + } + + friend constexpr bool + operator==(const _Iterator& __x, const _Iterator& __y) + requires equality_comparable<__ziperator<_Const>> + { return __x._M_inner == __y._M_inner; } + + friend constexpr bool + operator<(const _Iterator& __x, const _Iterator& __y) + requires random_access_range<_Base<_Const>> + { return __x._M_inner < __y._M_inner; } + + friend constexpr bool + operator>(const _Iterator& __x, const _Iterator& __y) + requires random_access_range<_Base<_Const>> + { return __x._M_inner > __y._M_inner; } + + friend constexpr bool + operator<=(const _Iterator& __x, const _Iterator& __y) + requires random_access_range<_Base<_Const>> + { return __x._M_inner <= __y._M_inner; } + + friend constexpr bool + operator>=(const _Iterator& __x, const _Iterator& __y) + requires random_access_range<_Base<_Const>> + { return __x._M_inner >= __y._M_inner; } + + friend constexpr auto + operator<=>(const _Iterator& __x, const _Iterator& __y) + requires random_access_range<_Base<_Const>> && three_way_comparable<__ziperator<_Const>> + { return __x._M_inner <=> __y._M_inner; } + + friend constexpr _Iterator + operator+(const _Iterator& __i, difference_type __n) + requires random_access_range<_Base<_Const>> + { return _Iterator(*__i._M_parent, __i._M_inner + __n); } + + friend constexpr _Iterator + operator+(difference_type __n, const _Iterator& __i) + requires random_access_range<_Base<_Const>> + { return _Iterator(*__i._M_parent, __i._M_inner + __n); } + + friend constexpr _Iterator + operator-(const _Iterator& __i, difference_type __n) + requires random_access_range<_Base<_Const>> + { return _Iterator(*__i._M_parent, __i._M_inner - __n); } + + friend constexpr difference_type + operator-(const _Iterator& __x, const _Iterator& __y) + requires sized_sentinel_for<__ziperator<_Const>, __ziperator<_Const>> + { return __x._M_inner - __y._M_inner; } + }; + + template + requires (view<_Vs> && ...) && (sizeof...(_Vs) > 0) && is_object_v<_Fp> + && regular_invocable<_Fp&, range_reference_t<_Vs>...> + && std::__detail::__can_reference...>> + template + class zip_transform_view<_Fp, _Vs...>::_Sentinel + { + __zentinel<_Const> _M_inner; + + constexpr explicit + _Sentinel(__zentinel<_Const> __inner) + : _M_inner(__inner) + { } + + friend class zip_transform_view; + + public: + _Sentinel() = default; + + constexpr + _Sentinel(_Sentinel __i) + requires _Const && convertible_to<__zentinel, __zentinel<_Const>> + : _M_inner(std::move(__i._M_inner)) + { } + + template + requires sentinel_for<__zentinel<_Const>, __ziperator> + friend constexpr bool + operator==(const _Iterator& __x, const _Sentinel& __y) + { return __x._M_inner == __y._M_inner; } + + template + requires sized_sentinel_for<__zentinel<_Const>, __ziperator> + friend constexpr range_difference_t<__detail::__maybe_const_t> + operator-(const _Iterator& __x, const _Sentinel& __y) + { return __x._M_inner - __y._M_inner; } + + template + requires sized_sentinel_for<__zentinel<_Const>, __ziperator> + friend constexpr range_difference_t<__detail::__maybe_const_t> + operator-(const _Sentinel& __x, const _Iterator& __y) + { return __x._M_inner - __y._M_inner; } + }; + + namespace views + { + namespace __detail + { + template + concept __can_zip_transform_view + = requires { zip_transform_view(std::declval<_Fp>(), std::declval<_Ts>()...); }; + } + + struct _ZipTransform + { + template + requires (sizeof...(_Ts) == 0) || __detail::__can_zip_transform_view<_Fp, _Ts...> + [[nodiscard]] + constexpr auto + operator()(_Fp&& __f, _Ts&&... __ts) const + { + if constexpr (sizeof...(_Ts) == 0) + return views::empty>>; + else + return zip_transform_view(std::forward<_Fp>(__f), std::forward<_Ts>(__ts)...); + } + }; + + inline constexpr _ZipTransform zip_transform; + } #endif // C++23 } // namespace ranges diff --git a/libstdc++-v3/testsuite/std/ranges/zip_transform/1.cc b/libstdc++-v3/testsuite/std/ranges/zip_transform/1.cc new file mode 100644 index 00000000000..5ea24c578a8 --- /dev/null +++ b/libstdc++-v3/testsuite/std/ranges/zip_transform/1.cc @@ -0,0 +1,108 @@ +// { 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() +{ + static_assert(ranges::empty(views::zip_transform([] { return 0; }))); + + auto z1 = views::zip_transform(std::identity{}, + std::array{1, 2, 3}); + VERIFY( ranges::equal(z1, (int[]){1, 2, 3}) ); + const auto i0 = z1.begin(), i1 = z1.begin() + 1; + VERIFY( i0 + 1 - 1 == i0 ); + VERIFY( i0 < i1 ); + VERIFY( i1 < z1.end() ); + VERIFY( i1 - i0 == 1 ); + VERIFY( i0 - i1 == -1 ); + VERIFY( z1.end() - i1 == 2 ); + VERIFY( i1 - z1.end() == -2 ); + ranges::iter_swap(i0, i1); + VERIFY( ranges::equal(std::move(z1), (int[]){2, 1, 3}) ); + + auto z2 = views::zip_transform(std::multiplies{}, + std::array{-1, 2}, + std::array{3, 4, 5}); + auto i2 = z2.begin(); + i2 += 1; + i2 -= -1; + VERIFY( i2 == z2.end() ); + VERIFY( ranges::size(z2) == 2 ); + VERIFY( ranges::size(std::as_const(z2)) == 2 ); + VERIFY( ranges::equal(z2, (int[]){-3, 8}) ); + + auto z3 = views::zip_transform([] (auto... xs) { return ranges::max({xs...}); }, + std::array{1, 6, 7, 0, 0}, + std::array{2, 5, 9}, + std::array{3, 4, 8, 0}); + VERIFY( ranges::size(z3) == 3 ); + VERIFY( ranges::equal(z3, (int[]){3, 6, 9}) ); + + 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::zip_transform_view, + views::all_t>, + views::all_t>>; + static_assert(ranges::forward_range); + static_assert(!ranges::random_access_range); + static_assert(!ranges::sized_range); + + using ty2 = ranges::zip_transform_view>, + views::all_t>, + views::all_t>>; + static_assert(ranges::input_range); + static_assert(!ranges::forward_range); + static_assert(!ranges::sized_range); + + return true; +} + +constexpr bool +test03() +{ + int u[] = {1, 2, 3, 4}, v[] = {4, 5, 6}; + auto z = views::zip_transform(std::plus{}, + u | views::filter([](auto) { return true; }), + v); + using ty = decltype(z); + static_assert(ranges::forward_range); + static_assert(!ranges::common_range); + static_assert(!ranges::sized_range); + VERIFY( z.begin() == z.begin() ); + VERIFY( z.begin() != z.end() ); + VERIFY( ranges::next(z.begin(), 3) == z.end() ); + auto it = z.begin(); + ++it; + it++; + it--; + --it; + VERIFY( it == z.begin() ); + + return true; +} + +int +main() +{ + static_assert(test01()); + static_assert(test02()); + static_assert(test03()); +} -- 2.37.2.382.g795ea8776b