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 DABF9385696D for ; Tue, 4 Oct 2022 01:11:29 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org DABF9385696D 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=1664845889; 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=2a5xsAnHUXDQl1kNdmBA7uC0LBy076R37jz0aP808ek=; b=BQePpi2uIEbPfaj7TBcnuMxEFJFtqABUygVxNL/IiQ06J2IEB2MG1Msjgo6YuUTZT2qZ65 +0kht9JVggP3pro3xLWbrQPP2gGVDXXUJtWtul7OPjcZ6tP3A9sZ0lsAaOrJ9bNr5u36iS oIk+GaY6LXHVAK3YmclR6GR6bnC0lYk= Received: from mail-qk1-f200.google.com (mail-qk1-f200.google.com [209.85.222.200]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_128_GCM_SHA256) id us-mta-587-UbhOUiCQOcmImFPBPhwPvg-1; Mon, 03 Oct 2022 21:11:20 -0400 X-MC-Unique: UbhOUiCQOcmImFPBPhwPvg-1 Received: by mail-qk1-f200.google.com with SMTP id bl17-20020a05620a1a9100b006cdf19243acso10369011qkb.4 for ; Mon, 03 Oct 2022 18:11:20 -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:subject:date:message-id :reply-to; bh=2a5xsAnHUXDQl1kNdmBA7uC0LBy076R37jz0aP808ek=; b=hFhRqkL4C7zq2msqNzgL6Qx/4YX6A/LX51KMsT/lWTa8ddvVxxOQrw9YFBkwJdfJss sxN3Hq3cN1SzXkdzr8BRZ5AzEzHo6wkydHgGTpjRNbzWUFhjA1ohANCS4rkc4eYiE4qt NfYYoWHYsPb/krcGKbxhNTYUIGURxX2ClTZ+R6rcBQDcW/Ev4+TSM1Q7naVKocVizcLC ilTLiX4bHDt1WBbeflWLba7tz5OAvjc3iiuB9BMTNjRfi2/4T4wG8yW1iOOaYdNAsLU7 GCzsXtMjmIUvA+zhPErjmzQDRYWb8yiOVnwxzDtExr2ivmrU1FnIWSoll1GXOYbsvzAS xjcQ== X-Gm-Message-State: ACrzQf2GaEvgJ+ZvgSXd8g779+E1JkLbHtCALZYYK16LRKIdnK1fZkRU LNherJRZHo1jh2p6aZm1+HPPpeCFZD2F/lxOYC+/9U+ReKVskjihH2b6re8RhdArgPZguiLqllQ SAOuvI6hKh8tM5lw= X-Received: by 2002:a05:620a:2901:b0:6ce:179c:d875 with SMTP id m1-20020a05620a290100b006ce179cd875mr15726250qkp.484.1664845879559; Mon, 03 Oct 2022 18:11:19 -0700 (PDT) X-Google-Smtp-Source: AMsMyM73pgnN+xmKgeE2F8Ugc0Xp/T1RlEGUfBY4ldDiu5xnKmyri7DjyHYxrsiDBw47jP4VnqOFlQ== X-Received: by 2002:a05:620a:2901:b0:6ce:179c:d875 with SMTP id m1-20020a05620a290100b006ce179cd875mr15726240qkp.484.1664845879248; Mon, 03 Oct 2022 18:11:19 -0700 (PDT) Received: from localhost.localdomain (ool-457670bb.dyn.optonline.net. [69.118.112.187]) by smtp.gmail.com with ESMTPSA id o13-20020a05620a2a0d00b006ce51b541dfsm13178649qkp.36.2022.10.03.18.11.18 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 03 Oct 2022 18:11:18 -0700 (PDT) From: Patrick Palka To: gcc-patches@gcc.gnu.org Cc: libstdc++@gcc.gnu.org, Patrick Palka Subject: [PATCH] libstdc++: Implement ranges::join_with_view from P2441R2 Date: Mon, 3 Oct 2022 21:11:15 -0400 Message-Id: <20221004011115.2009591-1-ppalka@redhat.com> X-Mailer: git-send-email 2.38.0.rc2 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=-14.1 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 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? FWIW using variant<_PatternIter, _InnerIter> in the implementation means we need to include from , which increases the preprocessed size of by 3% (51.5k vs 53k). I suppose that's an acceptable cost? libstdc++-v3/ChangeLog: * include/std/ranges: Include . (__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. --- libstdc++-v3/include/std/ranges | 458 ++++++++++++++++++ .../std/ranges/adaptors/join_with/1.cc | 80 +++ 2 files changed, 538 insertions(+) create mode 100644 libstdc++-v3/testsuite/std/ranges/adaptors/join_with/1.cc diff --git a/libstdc++-v3/include/std/ranges b/libstdc++-v3/include/std/ranges index c2eacdebe28..50198865b18 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..e39b46da0a3 --- /dev/null +++ b/libstdc++-v3/testsuite/std/ranges/adaptors/join_with/1.cc @@ -0,0 +1,80 @@ +// { 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() +{ + 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(); + ++i; + i++; + VERIFY( *i == 'l' ); + --i; + i--; + VERIFY( *i == 'h' ); + return true; +} + +constexpr bool +test02() +{ + using namespace std::literals; + 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; +} + +int +main() +{ + static_assert(test01()); + static_assert(test02()); + static_assert(test03()); +} -- 2.38.0.rc2