From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 1888) id 06E9C385382D; Wed, 24 Aug 2022 23:17:38 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 06E9C385382D DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1661383058; bh=sY/VdFB3u/V9YYqDjmAimim69/+QepYaswfD+VMtHZg=; h=From:To:Subject:Date:From; b=wbLo1yGnjEZgABH1qA5v2eD+Ur9vgWI02fps2iqFkUBFNYmGIWfvGsUO3io+XXsyX EE+BMhWoI2aAa3/uInkUxi5p4Cnti0LNTnIkkq38hWhJQtHqZ5ehFOHpKi40pRRi7u ChlwEPpw9LlUcv+elD7BpIKS/xui3dNzRVvV6K7I= MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Content-Type: text/plain; charset="utf-8" From: Patrick Palka To: gcc-cvs@gcc.gnu.org, libstdc++-cvs@gcc.gnu.org Subject: [gcc r13-2193] libstdc++: Implement ranges::zip_view from P2321R2 X-Act-Checkin: gcc X-Git-Author: Patrick Palka X-Git-Refname: refs/heads/master X-Git-Oldrev: e5428086c2c8daf69e5916dd5016d1e7b85d3f0d X-Git-Newrev: 49e25d3e29aa1b56e6e82654de1a452a6cedc265 Message-Id: <20220824231738.06E9C385382D@sourceware.org> Date: Wed, 24 Aug 2022 23:17:38 +0000 (GMT) List-Id: https://gcc.gnu.org/g:49e25d3e29aa1b56e6e82654de1a452a6cedc265 commit r13-2193-g49e25d3e29aa1b56e6e82654de1a452a6cedc265 Author: Patrick Palka Date: Wed Aug 24 19:17:27 2022 -0400 libstdc++: Implement ranges::zip_view from P2321R2 libstdc++-v3/ChangeLog: * include/bits/ranges_algo.h (__min_fn, min): Move to ... * include/bits/ranges_util.h: ... here, in order to avoid including all of ranges_algo.h from . * include/std/ranges (__detail::__zip_is_common): Define for C++23 as per P2321R2. (__detail::__tuple_or_pair): Likewise. (__detail::__tuple_or_pair_t): Likewise. (__detail::__tuple_transform): Likewise. (__detail::__tuple_for_each): Likewise. (zip_view): Likewise. (enable_borrowed_range): Likewise. (__detail::__all_random_access): Likewise. (__detail::__all_bidirectional): Likewise. (__detail::__all_forward): Likewise. (__detail::__zip_view_iter_cat): Likewise. (zip_view::_Iterator): Likewise. (zip_view::_Sentinel): Likewise. * testsuite/std/ranges/zip/1.cc: New test. Diff: --- libstdc++-v3/include/bits/ranges_algo.h | 54 +--- libstdc++-v3/include/bits/ranges_util.h | 55 ++++ libstdc++-v3/include/std/ranges | 442 +++++++++++++++++++++++++++++ libstdc++-v3/testsuite/std/ranges/zip/1.cc | 111 ++++++++ 4 files changed, 609 insertions(+), 53 deletions(-) diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h index 3d30fb1428c..2a116361a67 100644 --- a/libstdc++-v3/include/bits/ranges_algo.h +++ b/libstdc++-v3/include/bits/ranges_algo.h @@ -2902,59 +2902,7 @@ namespace ranges inline constexpr __set_symmetric_difference_fn set_symmetric_difference{}; - struct __min_fn - { - template> - _Comp = ranges::less> - constexpr const _Tp& - operator()(const _Tp& __a, const _Tp& __b, - _Comp __comp = {}, _Proj __proj = {}) const - { - if (std::__invoke(__comp, - std::__invoke(__proj, __b), - std::__invoke(__proj, __a))) - return __b; - else - return __a; - } - - template, _Proj>> - _Comp = ranges::less> - requires indirectly_copyable_storable, - range_value_t<_Range>*> - constexpr range_value_t<_Range> - operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const - { - auto __first = ranges::begin(__r); - auto __last = ranges::end(__r); - __glibcxx_assert(__first != __last); - auto __result = *__first; - while (++__first != __last) - { - auto __tmp = *__first; - if (std::__invoke(__comp, - std::__invoke(__proj, __tmp), - std::__invoke(__proj, __result))) - __result = std::move(__tmp); - } - return __result; - } - - template> - _Comp = ranges::less> - constexpr _Tp - operator()(initializer_list<_Tp> __r, - _Comp __comp = {}, _Proj __proj = {}) const - { - return (*this)(ranges::subrange(__r), - std::move(__comp), std::move(__proj)); - } - }; - - inline constexpr __min_fn min{}; + // min is defined in . struct __max_fn { diff --git a/libstdc++-v3/include/bits/ranges_util.h b/libstdc++-v3/include/bits/ranges_util.h index 37d7bc862f9..bb56deee01b 100644 --- a/libstdc++-v3/include/bits/ranges_util.h +++ b/libstdc++-v3/include/bits/ranges_util.h @@ -649,6 +649,61 @@ namespace ranges }; inline constexpr __search_fn search{}; + + struct __min_fn + { + template> + _Comp = ranges::less> + constexpr const _Tp& + operator()(const _Tp& __a, const _Tp& __b, + _Comp __comp = {}, _Proj __proj = {}) const + { + if (std::__invoke(__comp, + std::__invoke(__proj, __b), + std::__invoke(__proj, __a))) + return __b; + else + return __a; + } + + template, _Proj>> + _Comp = ranges::less> + requires indirectly_copyable_storable, + range_value_t<_Range>*> + constexpr range_value_t<_Range> + operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const + { + auto __first = ranges::begin(__r); + auto __last = ranges::end(__r); + __glibcxx_assert(__first != __last); + auto __result = *__first; + while (++__first != __last) + { + auto __tmp = *__first; + if (std::__invoke(__comp, + std::__invoke(__proj, __tmp), + std::__invoke(__proj, __result))) + __result = std::move(__tmp); + } + return __result; + } + + template> + _Comp = ranges::less> + constexpr _Tp + operator()(initializer_list<_Tp> __r, + _Comp __comp = {}, _Proj __proj = {}) const + { + return (*this)(ranges::subrange(__r), + std::move(__comp), std::move(__proj)); + } + }; + + inline constexpr __min_fn min{}; + } // namespace ranges using ranges::get; diff --git a/libstdc++-v3/include/std/ranges b/libstdc++-v3/include/std/ranges index 3e71ecb32b7..c600bad6283 100644 --- a/libstdc++-v3/include/std/ranges +++ b/libstdc++-v3/include/std/ranges @@ -4352,6 +4352,448 @@ namespace views::__adaptor inline constexpr auto values = elements<1>; } // namespace views +#if __cplusplus > 202002L + namespace __detail + { + template + concept __zip_is_common = (sizeof...(_Rs) == 1 && (common_range<_Rs> && ...)) + || (!(bidirectional_range<_Rs> && ...) && (common_range<_Rs> && ...)) + || ((random_access_range<_Rs> && ...) && (sized_range<_Rs> && ...)); + + template + struct __tuple_or_pair + { using type = std::tuple<_Ts...>; }; + + template + struct __tuple_or_pair<_Tp, _Up> + { using type = pair<_Tp, _Up>; }; + + template + using __tuple_or_pair_t = typename __tuple_or_pair<_Ts...>::type; + + template + constexpr auto + __tuple_transform(_Fp&& __f, _Tuple&& __tuple) + { + return std::apply([&](_Ts&&... __elts) { + return __tuple_or_pair_t...> + (std::__invoke(__f, std::forward<_Ts>(__elts))...); + }, std::forward<_Tuple>(__tuple)); + } + + template + constexpr void + __tuple_for_each(_Fp&& __f, _Tuple&& __tuple) + { + std::apply([&](_Ts&&... __elts) { + (std::__invoke(__f, std::forward<_Ts>(__elts)), ...); + }, std::forward<_Tuple>(__tuple)); + } + } // namespace __detail + + template + requires (view<_Vs> && ...) && (sizeof...(_Vs) > 0) + class zip_view : public view_interface> + { + tuple<_Vs...> _M_views; + + template class _Iterator; + template class _Sentinel; + + public: + zip_view() = default; + + constexpr explicit + zip_view(_Vs... __views) + : _M_views(std::move(__views)...) + { } + + constexpr auto + begin() requires (!(__detail::__simple_view<_Vs> && ...)) + { return _Iterator(__detail::__tuple_transform(ranges::begin, _M_views)); } + + constexpr auto + begin() const requires (range && ...) + { return _Iterator(__detail::__tuple_transform(ranges::begin, _M_views)); } + + constexpr auto + end() requires (!(__detail::__simple_view<_Vs> && ...)) + { + if constexpr (!__detail::__zip_is_common<_Vs...>) + return _Sentinel(__detail::__tuple_transform(ranges::end, _M_views)); + else if constexpr ((random_access_range<_Vs> && ...)) + return begin() + iter_difference_t<_Iterator>(size()); + else + return _Iterator(__detail::__tuple_transform(ranges::end, _M_views)); + } + + constexpr auto + end() const requires (range && ...) + { + if constexpr (!__detail::__zip_is_common) + return _Sentinel(__detail::__tuple_transform(ranges::end, _M_views)); + else if constexpr ((random_access_range && ...)) + return begin() + iter_difference_t<_Iterator>(size()); + else + return _Iterator(__detail::__tuple_transform(ranges::end, _M_views)); + } + + constexpr auto + size() requires (sized_range<_Vs> && ...) + { + return std::apply([](auto... sizes) { + using _CT = __detail::__make_unsigned_like_t>; + return ranges::min({_CT(sizes)...}); + }, __detail::__tuple_transform(ranges::size, _M_views)); + } + + constexpr auto + size() const requires (sized_range && ...) + { + return std::apply([](auto... sizes) { + using _CT = __detail::__make_unsigned_like_t>; + return ranges::min({_CT(sizes)...}); + }, __detail::__tuple_transform(ranges::size, _M_views)); + } + }; + + template + zip_view(_Rs&&...) -> zip_view...>; + + template + inline constexpr bool enable_borrowed_range> + = (enable_borrowed_range<_Views> && ...); + + namespace __detail + { + template + concept __all_random_access + = (random_access_range<__maybe_const_t<_Const, _Vs>> && ...); + + template + concept __all_bidirectional + = (bidirectional_range<__maybe_const_t<_Const, _Vs>> && ...); + + template + concept __all_forward + = (forward_range<__maybe_const_t<_Const, _Vs>> && ...); + + template + struct __zip_view_iter_cat + { }; + + template + requires __all_forward<_Const, _Views...> + struct __zip_view_iter_cat<_Const, _Views...> + { using iterator_category = input_iterator_tag; }; + } // namespace __detail + + template + requires (view<_Vs> && ...) && (sizeof...(_Vs) > 0) + template + class zip_view<_Vs...>::_Iterator + : public __detail::__zip_view_iter_cat<_Const, _Vs...> + { + __detail::__tuple_or_pair_t>...> _M_current; + + constexpr explicit + _Iterator(decltype(_M_current) __current) + : _M_current(std::move(__current)) + { } + + static auto + _S_iter_concept() + { + if constexpr (__detail::__all_random_access<_Const, _Vs...>) + return random_access_iterator_tag{}; + else if constexpr (__detail::__all_bidirectional<_Const, _Vs...>) + return bidirectional_iterator_tag{}; + else if constexpr (__detail::__all_forward<_Const, _Vs...>) + return forward_iterator_tag{}; + else + return input_iterator_tag{}; + } + + public: + // iterator_category defined in __zip_view_iter_cat + using iterator_concept = decltype(_S_iter_concept()); + using value_type + = __detail::__tuple_or_pair_t>...>; + using difference_type + = common_type_t>...>; + + _Iterator() = default; + + constexpr + _Iterator(_Iterator __i) + requires _Const + && (convertible_to, + iterator_t<__detail::__maybe_const_t<_Const, _Vs>>> && ...) + : _M_current(std::move(__i._M_current)) + { } + + constexpr auto + operator*() const + { + auto __f = [](auto& __i) -> decltype(auto) { + return *__i; + }; + return __detail::__tuple_transform(__f, _M_current); + } + + constexpr _Iterator& + operator++() + { + __detail::__tuple_for_each([](auto& __i) { ++__i; }, _M_current); + return *this; + } + + constexpr void + operator++(int) + { ++*this; } + + constexpr _Iterator + operator++(int) + requires __detail::__all_forward<_Const, _Vs...> + { + auto __tmp = *this; + ++*this; + return __tmp; + } + + constexpr _Iterator& + operator--() + requires __detail::__all_bidirectional<_Const, _Vs...> + { + __detail::__tuple_for_each([](auto& __i) { --__i; }, _M_current); + return *this; + } + + constexpr _Iterator + operator--(int) + requires __detail::__all_bidirectional<_Const, _Vs...> + { + auto __tmp = *this; + --*this; + return __tmp; + } + + constexpr _Iterator& + operator+=(difference_type __x) + requires __detail::__all_random_access<_Const, _Vs...> + { + auto __f = [&](_It& __i) { + __i += iter_difference_t<_It>(__x); + }; + __detail::__tuple_for_each(__f, _M_current); + return *this; + } + + constexpr _Iterator& + operator-=(difference_type __x) + requires __detail::__all_random_access<_Const, _Vs...> + { + auto __f = [&](_It& __i) { + __i -= iter_difference_t<_It>(__x); + }; + __detail::__tuple_for_each(__f, _M_current); + return *this; + } + + constexpr auto + operator[](difference_type __n) const + requires __detail::__all_random_access<_Const, _Vs...> + { + auto __f = [&](_It& __i) -> decltype(auto) { + return __i[iter_difference_t<_It>(__n)]; + }; + return __detail::__tuple_transform(__f, _M_current); + } + + friend constexpr bool + operator==(const _Iterator& __x, const _Iterator& __y) + requires (equality_comparable>> && ...) + { + if constexpr (__detail::__all_bidirectional<_Const, _Vs...>) + return __x._M_current == __y._M_current; + else + return [&](index_sequence<_Is...>) { + return ((std::get<_Is>(__x._M_current) == std::get<_Is>(__y._M_current)) || ...); + }(make_index_sequence{}); + } + + friend constexpr bool + operator<(const _Iterator& __x, const _Iterator& __y) + requires __detail::__all_random_access<_Const, _Vs...> + { return __x._M_current < __y._M_current; } + + friend constexpr bool + operator>(const _Iterator& __x, const _Iterator& __y) + requires __detail::__all_random_access<_Const, _Vs...> + { return __y < __x; } + + friend constexpr bool + operator<=(const _Iterator& __x, const _Iterator& __y) + requires __detail::__all_random_access<_Const, _Vs...> + { return !(__y < __x); } + + friend constexpr bool + operator>=(const _Iterator& __x, const _Iterator& __y) + requires __detail::__all_random_access<_Const, _Vs...> + { return !(__x < __y); } + + friend constexpr auto + operator<=>(const _Iterator& __x, const _Iterator& __y) + requires __detail::__all_random_access<_Const, _Vs...> + && (three_way_comparable>> && ...) + { return __x._M_current <=> __y._M_current; } + + friend constexpr _Iterator + operator+(const _Iterator& __i, difference_type __n) + requires __detail::__all_random_access<_Const, _Vs...> + { + auto __r = __i; + __r += __n; + return __r; + } + + friend constexpr _Iterator + operator+(difference_type __n, const _Iterator& __i) + requires __detail::__all_random_access<_Const, _Vs...> + { + auto __r = __i; + __r += __n; + return __r; + } + + friend constexpr _Iterator + operator-(const _Iterator& __i, difference_type __n) + requires __detail::__all_random_access<_Const, _Vs...> + { + auto __r = __i; + __r -= __n; + return __r; + } + + friend constexpr difference_type + operator-(const _Iterator& __x, const _Iterator& __y) + requires (sized_sentinel_for>, + iterator_t<__detail::__maybe_const_t<_Const, _Vs>>> && ...) + { + return [&](index_sequence<_Is...>) { + return ranges::min({difference_type(std::get<_Is>(__x._M_current) + - std::get<_Is>(__y._M_current))...}, + ranges::less{}, + [](difference_type __i) -> make_unsigned_t { + return __i < 0 ? -__i : __i; + }); + }(make_index_sequence{}); + } + + friend constexpr auto + iter_move(const _Iterator& __i) + { return __detail::__tuple_transform(ranges::iter_move, __i._M_current); } + + friend constexpr void + iter_swap(const _Iterator& __l, const _Iterator& __r) + requires (indirectly_swappable>> && ...) + { + [&](index_sequence<_Is...>) { + (ranges::iter_swap(std::get<_Is>(__l._M_current), std::get<_Is>(__r._M_current)), ...); + }(make_index_sequence{}); + } + + friend class zip_view; + }; + + template + requires (view<_Vs> && ...) && (sizeof...(_Vs) > 0) + template + class zip_view<_Vs...>::_Sentinel + { + __detail::__tuple_or_pair_t>...> _M_end; + + constexpr explicit + _Sentinel(decltype(_M_end) __end) + : _M_end(__end) + { } + + friend class zip_view; + + public: + _Sentinel() = default; + + constexpr + _Sentinel(_Sentinel __i) + requires _Const + && (convertible_to, + sentinel_t<__detail::__maybe_const_t<_Const, _Vs>>> && ...) + : _M_end(std::move(__i._M_end)) + { } + + template + requires (sentinel_for>, + iterator_t<__detail::__maybe_const_t<_OtherConst, _Vs>>> && ...) + friend constexpr bool + operator==(const _Iterator<_OtherConst>& __x, const _Sentinel& __y) + { + return [&](index_sequence<_Is...>) { + return ((std::get<_Is>(__x._M_current) == std::get<_Is>(__y._M_end)) || ...); + }(make_index_sequence{}); + } + + template + requires (sized_sentinel_for>, + iterator_t<__detail::__maybe_const_t<_OtherConst, _Vs>>> && ...) + friend constexpr auto + operator-(const _Iterator<_OtherConst>& __x, const _Sentinel& __y) + { + using _Ret + = common_type_t>...>; + return [&](index_sequence<_Is...>) { + return ranges::min({_Ret(std::get<_Is>(__x._M_current) - std::get<_Is>(__y._M_end))...}, + ranges::less{}, + [](_Ret __i) -> make_unsigned_t<_Ret> { + return __i < 0 ? -__i : __i; + }); + }(make_index_sequence{}); + } + + template + requires (sized_sentinel_for>, + iterator_t<__detail::__maybe_const_t<_OtherConst, _Vs>>> && ...) + friend constexpr auto + operator-(const _Sentinel& __y, const _Iterator<_OtherConst>& __x) + { return -(__x - __y); } + }; + + namespace views + { + namespace __detail + { + template + concept __can_zip_view + = requires { zip_view...>(std::declval<_Ts>()...); }; + } + + struct _Zip + { + template + requires (sizeof...(_Ts) == 0 || __detail::__can_zip_view<_Ts...>) + [[nodiscard]] + constexpr auto + operator()(_Ts&&... __ts) const + { + if constexpr (sizeof...(_Ts) == 0) + return views::empty>; + else + return zip_view...>(std::forward<_Ts>(__ts)...); + } + }; + + inline constexpr _Zip zip; + } +#endif // C++23 } // namespace ranges namespace views = ranges::views; diff --git a/libstdc++-v3/testsuite/std/ranges/zip/1.cc b/libstdc++-v3/testsuite/std/ranges/zip/1.cc new file mode 100644 index 00000000000..0113efdb537 --- /dev/null +++ b/libstdc++-v3/testsuite/std/ranges/zip/1.cc @@ -0,0 +1,111 @@ +// { dg-options "-std=gnu++23" } +// { dg-do run { target c++23 } } + +#include +#include +#include +#include +#include +#include + +namespace ranges = std::ranges; +namespace views = std::views; + +constexpr bool +test01() +{ + static_assert(ranges::empty(views::zip())); + static_assert(ranges::empty(views::empty)); + + auto z1 = views::zip(std::array{1, 2}); + 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 == 1 ); + VERIFY( i1 - z1.end() == -1 ); + ranges::iter_swap(i0, i1); + VERIFY( ranges::equal(std::move(z1) | views::keys, (int[]){2, 1}) ); + + auto z2 = views::zip(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( z2[0].first == 1 && z2[0].second == 3 ); + VERIFY( z2[1].first == 2 && z2[1].second == 4 ); + for (const auto [x, y] : z2) + { + VERIFY( y - x == 2 ); + std::swap(x, y); + } + + int x[2] = {1, 2}, y[2] = {3, 4}, z[2] = {5, 6}; + const auto z3 = views::zip(x, y, z); + VERIFY( ranges::size(z3) == 2 ); + for (int i = 0; i < ranges::size(x); i++) + { + VERIFY( &std::get<0>(z3[i]) == &x[i] ); + VERIFY( &std::get<1>(z3[i]) == &y[i] ); + VERIFY( &std::get<2>(z3[i]) == &z[i] ); + } + + 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_view>, + views::all_t>>; + static_assert(ranges::forward_range); + static_assert(!ranges::random_access_range); + static_assert(!ranges::sized_range); + + using ty2 = ranges::zip_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}, w[] = {7, 8, 9, 10}; + auto z = views::zip(u | views::filter([](auto) { return true; }), v, w); + 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()); +}