From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 1888) id 73AF03858D37; Tue, 4 Oct 2022 13:45:47 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 73AF03858D37 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1664891147; bh=NqsbjbVMR/JBP0acHbd0QFuF5j+dVsn4TPZVlEY302E=; h=From:To:Subject:Date:From; b=jHAaqqmRTC5jAh3VHrAFPrDsHDALwmG9I75iNZfoDNUbrNwkPJojKTiVn6+FT6fhV Y1S1ECgKogOJi3QVh31Ckk14AQs8UzRX6WIBguuNBluHN7gdbMT/QcGIoSB31LY8oE bu3saAIRLgG+BMC4kiSXJaacOtDiweFr2Zl89g2A= 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-3057] libstdc++: Implement ranges::join_with_view from P2441R2 X-Act-Checkin: gcc X-Git-Author: Patrick Palka X-Git-Refname: refs/heads/master X-Git-Oldrev: e886ebd17965d78f609b62479f4f48085108389c X-Git-Newrev: 147f6ed39f66a3812a27d0ecd154c8efc1918688 Message-Id: <20221004134547.73AF03858D37@sourceware.org> Date: Tue, 4 Oct 2022 13:45:47 +0000 (GMT) List-Id: https://gcc.gnu.org/g:147f6ed39f66a3812a27d0ecd154c8efc1918688 commit r13-3057-g147f6ed39f66a3812a27d0ecd154c8efc1918688 Author: Patrick Palka Date: Tue Oct 4 09:45:15 2022 -0400 libstdc++: Implement ranges::join_with_view from P2441R2 libstdc++-v3/ChangeLog: * include/std/ranges: Include for C++23. (__detail::__compatible_joinable_ranges): Define. (__detail::__bidirectional_common): Define. (join_with_view): Define. (join_with_view::_Iterator): Define. (join_with_view::_Sentinel): Define. (views::__detail::__can_join_with_view): Define. (views::_JoinWith, views::join_with): Define. * testsuite/std/ranges/adaptors/join_with/1.cc: New test. Diff: --- libstdc++-v3/include/std/ranges | 458 +++++++++++++++++++++ .../testsuite/std/ranges/adaptors/join_with/1.cc | 97 +++++ 2 files changed, 555 insertions(+) diff --git a/libstdc++-v3/include/std/ranges b/libstdc++-v3/include/std/ranges index c2eacdebe28..d0d6ce61a87 100644 --- a/libstdc++-v3/include/std/ranges +++ b/libstdc++-v3/include/std/ranges @@ -44,6 +44,9 @@ #include #include #include +#if __cplusplus > 202002L +#include +#endif #include #include @@ -6873,6 +6876,461 @@ namespace views::__adaptor inline constexpr _ChunkBy chunk_by; } + + namespace __detail + { + template + concept __compatible_joinable_ranges + = common_with, range_value_t<_Pattern>> + && common_reference_with, + range_reference_t<_Pattern>> + && common_reference_with, + range_rvalue_reference_t<_Pattern>>; + + template + concept __bidirectional_common = bidirectional_range<_Range> && common_range<_Range>; + } + + template + requires view<_Vp> && view<_Pattern> + && input_range> + && __detail::__compatible_joinable_ranges, _Pattern> + class join_with_view : public view_interface> + { + using _InnerRange = range_reference_t<_Vp>; + + _Vp _M_base = _Vp(); + __detail::__non_propagating_cache> _M_inner; + _Pattern _M_pattern = _Pattern(); + + template using _Base = __detail::__maybe_const_t<_Const, _Vp>; + template using _InnerBase = range_reference_t<_Base<_Const>>; + template using _PatternBase = __detail::__maybe_const_t<_Const, _Pattern>; + + template using _OuterIter = iterator_t<_Base<_Const>>; + template using _InnerIter = iterator_t<_InnerBase<_Const>>; + template using _PatternIter = iterator_t<_PatternBase<_Const>>; + + template + static constexpr bool _S_ref_is_glvalue = is_reference_v<_InnerBase<_Const>>; + + template + struct __iter_cat + { }; + + template + requires _S_ref_is_glvalue<_Const> + && forward_range<_Base<_Const>> + && forward_range<_InnerBase<_Const>> + struct __iter_cat<_Const> + { + private: + static auto + _S_iter_cat() + { + using _OuterIter = join_with_view::_OuterIter<_Const>; + using _InnerIter = join_with_view::_InnerIter<_Const>; + using _PatternIter = join_with_view::_PatternIter<_Const>; + using _OuterCat = typename iterator_traits<_OuterIter>::iterator_category; + using _InnerCat = typename iterator_traits<_InnerIter>::iterator_category; + using _PatternCat = typename iterator_traits<_PatternIter>::iterator_category; + if constexpr (!is_lvalue_reference_v, + iter_reference_t<_PatternIter>>>) + return input_iterator_tag{}; + else if constexpr (derived_from<_OuterCat, bidirectional_iterator_tag> + && derived_from<_InnerCat, bidirectional_iterator_tag> + && derived_from<_PatternCat, bidirectional_iterator_tag> + && common_range<_InnerBase<_Const>> + && common_range<_PatternBase<_Const>>) + return bidirectional_iterator_tag{}; + else if constexpr (derived_from<_OuterCat, forward_iterator_tag> + && derived_from<_InnerCat, forward_iterator_tag> + && derived_from<_PatternCat, forward_iterator_tag>) + return forward_iterator_tag{}; + else + return input_iterator_tag{}; + } + public: + using iterator_category = decltype(_S_iter_cat()); + }; + + template struct _Iterator; + template struct _Sentinel; + + public: + join_with_view() requires (default_initializable<_Vp> + && default_initializable<_Pattern>) + = default; + + constexpr + join_with_view(_Vp __base, _Pattern __pattern) + : _M_base(std::move(__base)), _M_pattern(std::move(__pattern)) + { } + + template + requires constructible_from<_Vp, views::all_t<_Range>> + && constructible_from<_Pattern, single_view>> + constexpr + join_with_view(_Range&& __r, range_value_t<_InnerRange> __e) + : _M_base(views::all(std::forward<_Range>(__r))), + _M_pattern(views::single(std::move(__e))) + { } + + constexpr _Vp + base() const& requires copy_constructible<_Vp> + { return _M_base; } + + constexpr _Vp + base() && + { return std::move(_M_base); } + + constexpr auto + begin() + { + constexpr bool __use_const = is_reference_v<_InnerRange> + && __detail::__simple_view<_Vp> && __detail::__simple_view<_Pattern>; + return _Iterator<__use_const>{*this, ranges::begin(_M_base)}; + } + + constexpr auto + begin() const + requires input_range + && forward_range + && is_reference_v> + { return _Iterator{*this, ranges::begin(_M_base)}; } + + constexpr auto + end() + { + constexpr bool __use_const + = __detail::__simple_view<_Vp> && __detail::__simple_view<_Pattern>; + if constexpr (is_reference_v<_InnerRange> + && forward_range<_Vp> && common_range<_Vp> + && forward_range<_InnerRange> && common_range<_InnerRange>) + return _Iterator<__use_const>{*this, ranges::end(_M_base)}; + else + return _Sentinel<__use_const>{*this}; + } + + constexpr auto + end() const + requires input_range + && forward_range + && is_reference_v> + { + using _InnerConstRange = range_reference_t; + if constexpr (forward_range + && forward_range<_InnerConstRange> + && common_range + && common_range<_InnerConstRange>) + return _Iterator{*this, ranges::end(_M_base)}; + else + return _Sentinel{*this}; + } + }; + + template + join_with_view(_Range&&, _Pattern&&) + -> join_with_view, views::all_t<_Pattern>>; + + template + join_with_view(_Range&&, range_value_t>) + -> join_with_view, + single_view>>>; + + template + requires view<_Vp> && view<_Pattern> + && input_range> + && __detail::__compatible_joinable_ranges, _Pattern> + template + class join_with_view<_Vp, _Pattern>::_Iterator : public __iter_cat<_Const> + { + using _Parent = __detail::__maybe_const_t<_Const, join_with_view>; + using _Base = join_with_view::_Base<_Const>; + using _InnerBase = join_with_view::_InnerBase<_Const>; + using _PatternBase = join_with_view::_PatternBase<_Const>; + + using _OuterIter = join_with_view::_OuterIter<_Const>; + using _InnerIter = join_with_view::_InnerIter<_Const>; + using _PatternIter = join_with_view::_PatternIter<_Const>; + + static constexpr bool _S_ref_is_glvalue = join_with_view::_S_ref_is_glvalue<_Const>; + + _Parent* _M_parent = nullptr; + _OuterIter _M_outer_it = _OuterIter(); + variant<_PatternIter, _InnerIter> _M_inner_it; + + constexpr + _Iterator(_Parent& __parent, iterator_t<_Base> __outer) + : _M_parent(std::__addressof(__parent)), _M_outer_it(std::move(__outer)) + { + if (_M_outer_it != ranges::end(_M_parent->_M_base)) + { + auto&& __inner = _M_update_inner(_M_outer_it); + _M_inner_it.template emplace<1>(ranges::begin(__inner)); + _M_satisfy(); + } + } + + constexpr auto&& + _M_update_inner(const _OuterIter& __x) + { + if constexpr (_S_ref_is_glvalue) + return *__x; + else + return _M_parent->_M_inner._M_emplace_deref(__x); + } + + constexpr auto&& + _M_get_inner(const _OuterIter& __x) + { + if constexpr (_S_ref_is_glvalue) + return *__x; + else + return *_M_parent->_M_inner; + } + + constexpr void + _M_satisfy() + { + while (true) + { + if (_M_inner_it.index() == 0) + { + if (std::get<0>(_M_inner_it) != ranges::end(_M_parent->_M_pattern)) + break; + + auto&& __inner = _M_update_inner(_M_outer_it); + _M_inner_it.template emplace<1>(ranges::begin(__inner)); + } + else + { + auto&& __inner = _M_get_inner(_M_outer_it); + if (std::get<1>(_M_inner_it) != ranges::end(__inner)) + break; + + if (++_M_outer_it == ranges::end(_M_parent->_M_base)) + { + if constexpr (_S_ref_is_glvalue) + _M_inner_it.template emplace<0>(); + break; + } + + _M_inner_it.template emplace<0>(ranges::begin(_M_parent->_M_pattern)); + } + } + } + + static auto + _S_iter_concept() + { + if constexpr (_S_ref_is_glvalue + && bidirectional_range<_Base> + && __detail::__bidirectional_common<_InnerBase> + && __detail::__bidirectional_common<_PatternBase>) + return bidirectional_iterator_tag{}; + else if constexpr (_S_ref_is_glvalue + && forward_range<_Base> + && forward_range<_InnerBase>) + return forward_iterator_tag{}; + else + return input_iterator_tag{}; + } + + friend join_with_view; + + public: + using iterator_concept = decltype(_S_iter_concept()); + // iterator_category defined in join_with_view::__iter_cat + using value_type = common_type_t, + iter_value_t<_PatternIter>>; + using difference_type = common_type_t, + iter_difference_t<_InnerIter>, + iter_difference_t<_PatternIter>>; + + _Iterator() requires default_initializable<_OuterIter> = default; + + constexpr + _Iterator(_Iterator __i) + requires _Const + && convertible_to, _OuterIter> + && convertible_to, _InnerIter> + && convertible_to, _PatternIter> + : _M_parent(__i._M_parent), + _M_outer_it(std::move(__i._M_outer_it)) + { + if (__i._M_inner_it.index() == 0) + _M_inner_it.template emplace<0>(std::get<0>(std::move(__i._M_inner_it))); + else + _M_inner_it.template emplace<1>(std::get<1>(std::move(__i._M_inner_it))); + } + + constexpr decltype(auto) + operator*() const + { + using reference = common_reference_t, + iter_reference_t<_PatternIter>>; + return std::visit([](auto& __it) -> reference { return *__it; }, _M_inner_it); + } + + constexpr _Iterator& + operator++() + { + std::visit([](auto& __it){ ++__it; }, _M_inner_it); + _M_satisfy(); + return *this; + } + + constexpr void + operator++(int) + { ++*this; } + + constexpr _Iterator + operator++(int) + requires _S_ref_is_glvalue + && forward_iterator<_OuterIter> && forward_iterator<_InnerIter> + { + _Iterator __tmp = *this; + ++*this; + return __tmp; + } + + constexpr _Iterator& + operator--() + requires _S_ref_is_glvalue + && bidirectional_range<_Base> + && __detail::__bidirectional_common<_InnerBase> + && __detail::__bidirectional_common<_PatternBase> + { + if (_M_outer_it == ranges::end(_M_parent->_M_base)) + { + auto&& __inner = *--_M_outer_it; + _M_inner_it.template emplace<1>(ranges::end(__inner)); + } + + while (true) + { + if (_M_inner_it.index() == 0) + { + auto& __it = std::get<0>(_M_inner_it); + if (__it == ranges::begin(_M_parent->_M_pattern)) + { + auto&& __inner = *--_M_outer_it; + _M_inner_it.template emplace<1>(ranges::end(__inner)); + } + else + break; + } + else + { + auto& __it = std::get<1>(_M_inner_it); + auto&& __inner = *_M_outer_it; + if (__it == ranges::begin(__inner)) + _M_inner_it.template emplace<0>(ranges::end(_M_parent->_M_pattern)); + else + break; + } + } + + std::visit([](auto& __it){ --__it; }, _M_inner_it); + return *this; + } + + constexpr _Iterator + operator--(int) + requires _S_ref_is_glvalue && bidirectional_range<_Base> + && __detail::__bidirectional_common<_InnerBase> + && __detail::__bidirectional_common<_PatternBase> + { + _Iterator __tmp = *this; + --*this; + return __tmp; + } + + friend constexpr bool + operator==(const _Iterator& __x, const _Iterator& __y) + requires _S_ref_is_glvalue + && equality_comparable<_OuterIter> && equality_comparable<_InnerIter> + { return __x._M_outer_it == __y._M_outer_it && __x._M_inner_it ==__y._M_inner_it; } + + friend constexpr decltype(auto) + iter_move(const _Iterator& __x) + { + using __rval_ref = common_reference_t, + iter_rvalue_reference_t<_PatternIter>>; + return std::visit<__rval_ref>(ranges::iter_move, __x._M_inner_it); + } + + friend constexpr void + iter_swap(const _Iterator& __x, const _Iterator& __y) + requires indirectly_swappable<_InnerIter, _PatternIter> + { std::visit(ranges::iter_swap, __x._M_inner_it, __y._M_inner_it); } + }; + + template + requires view<_Vp> && view<_Pattern> + && input_range> + && __detail::__compatible_joinable_ranges, _Pattern> + template + class join_with_view<_Vp, _Pattern>::_Sentinel + { + using _Parent = __detail::__maybe_const_t<_Const, join_with_view>; + using _Base = join_with_view::_Base<_Const>; + + sentinel_t<_Base> _M_end = sentinel_t<_Base>(); + + constexpr explicit + _Sentinel(_Parent& __parent) + : _M_end(ranges::end(__parent._M_base)) + { } + + friend join_with_view; + + public: + _Sentinel() = default; + + constexpr + _Sentinel(_Sentinel __s) + requires _Const && convertible_to, sentinel_t<_Base>> + : _M_end(std::move(__s._M_end)) + { } + + template + requires sentinel_for, + iterator_t<__detail::__maybe_const_t<_OtherConst, _Vp>>> + friend constexpr bool + operator==(const _Iterator<_OtherConst>& __x, const _Sentinel& __y) + { return __x._M_outer_it == __y._M_end; } + }; + + namespace views + { + namespace __detail + { + template + concept __can_join_with_view + = requires { join_with_view(std::declval<_Range>(), std::declval<_Pattern>()); }; + } // namespace __detail + + struct _JoinWith : __adaptor::_RangeAdaptor<_JoinWith> + { + template + requires __detail::__can_join_with_view<_Range, _Pattern> + constexpr auto + operator() [[nodiscard]] (_Range&& __r, _Pattern&& __f) const + { + return join_with_view(std::forward<_Range>(__r), std::forward<_Pattern>(__f)); + } + + using _RangeAdaptor<_JoinWith>::operator(); + static constexpr int _S_arity = 2; + template + static constexpr bool _S_has_simple_extra_args + = _LazySplit::_S_has_simple_extra_args<_Pattern>; + }; + + inline constexpr _JoinWith join_with; + } // namespace views #endif // C++23 } // namespace ranges diff --git a/libstdc++-v3/testsuite/std/ranges/adaptors/join_with/1.cc b/libstdc++-v3/testsuite/std/ranges/adaptors/join_with/1.cc new file mode 100644 index 00000000000..efa350feb11 --- /dev/null +++ b/libstdc++-v3/testsuite/std/ranges/adaptors/join_with/1.cc @@ -0,0 +1,97 @@ +// { 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; +using namespace std::literals; + +constexpr bool +test01() +{ + std::string_view rs[] = {"hello", "world"}; + auto v = rs | views::join_with(' '); + VERIFY( ranges::equal(v | views::split(' '), rs, ranges::equal) ); + auto i = v.begin(), j = v.begin(); + VERIFY( i == j ); + ++i; + i++; + VERIFY( i != j ); + VERIFY( *i == 'l' ); + --i; + i--; + VERIFY( *i == 'h' ); + return true; +} + +constexpr bool +test02() +{ + std::string_view rs[] = {"the", "quick", "brown", "fox"}; + auto v = rs + | views::transform([](auto x) { return x; }) + | views::filter([](auto) { return true; }); + VERIFY( ranges::equal(v | views::join_with(views::empty), "thequickbrownfox"sv) ); + VERIFY( ranges::equal(v | views::join_with('-'), "the-quick-brown-fox"sv) ); + VERIFY( ranges::equal(v | views::join_with("--"sv), "the--quick--brown--fox"sv) ); + VERIFY( ranges::empty(views::empty | views::join_with(0))); + VERIFY( ranges::equal(views::single(std::array{42}) | views::join_with(0), (int[]){42})); + return true; +} + +constexpr bool +test03() +{ + using __gnu_test::test_input_range; + using __gnu_test::test_forward_range; + using __gnu_test::test_bidirectional_range; + + using ty1 = ranges::join_with_view>>, + views::all_t>>; + static_assert(ranges::input_range); + static_assert(!ranges::forward_range); + static_assert(!ranges::common_range); + + using ty2 = ranges::join_with_view>>, + views::all_t>>; + static_assert(ranges::forward_range); + static_assert(!ranges::bidirectional_range); + static_assert(!ranges::common_range); + + using ty3 = ranges::join_with_view>, + std::string_view>; + static_assert(ranges::bidirectional_range); + static_assert(!ranges::random_access_range); + static_assert(ranges::common_range); + + return true; +} + +constexpr bool +test04() +{ + std::string rs[] = {"a", "", "b", "", "c"}; + auto v = rs | views::join_with(' '); + VERIFY( ranges::equal(v, "a b c"sv) ); + auto i = v.begin(); + auto j = ranges::next(i, 3); + ranges::iter_swap(i, j); + *j = ranges::iter_move(i); + VERIFY( ranges::equal(v, "b b c"sv) ); + return true; +} + +int +main() +{ + static_assert(test01()); + static_assert(test02()); + static_assert(test03()); + static_assert(test04()); +}