From: Patrick Palka <ppalka@redhat.com>
To: gcc-patches@gcc.gnu.org
Cc: libstdc++@gcc.gnu.org
Subject: Re: [PATCH] libstdc++: Implement P2770R0 changes to join_view / join_with_view
Date: Wed, 16 Aug 2023 12:04:27 -0400 [thread overview]
Message-ID: <CAMOnLZbNSZD8kyw28_LqCZ0Chw6rpFah1EbBBFCnTuDyGEUhbA@mail.gmail.com> (raw)
In-Reply-To: <20230417133916.3110637-1-ppalka@redhat.com>
On Mon, Apr 17, 2023 at 9:39 AM Patrick Palka <ppalka@redhat.com> wrote:
>
> This C++23 paper fixes a bug in these views when adapting a certain kind
> of non-forward range, and we treat it as a DR against C++20.
>
> Tested on x86_64-pc-linux-gnu, does this look OK for GCC 13? This
> is an ABI change for join_view so it'd be unsuitable for backporting
> later I think :(
Ping, does this look OK for trunk?
>
> libstdc++-v3/ChangeLog:
>
> * include/bits/regex.h (regex_iterator::iterator_concept):
> Define for C++20 as per P2770R0.
> (regex_token_iterator::iterator_concept): Likewise.
> * include/std/ranges (__detail::__as_lvalue): Define.
> (join_view::_Iterator): Befriend join_view.
> (join_view::_Iterator::_M_satisfy): Use _M_get_outer
> instead of _M_outer.
> (join_view::_Iterator::_M_get_outer): Define.
> (join_view::_Iterator::_Iterator): Split constructor taking
> _Parent argument into two as per P2770R0. Remove constraint on
> default constructor.
> (join_view::_Iterator::_M_outer): Make this data member present
> only when the underlying range is forward.
> (join_view::_Iterator::operator++): Use _M_get_outer instead of
> _M_outer.
> (join_view::_Iterator::operator--): Use __as_lvalue helper.
> (join_view::_Iterator::operator==): Adjust constraints as per
> P2770R0.
> (join_view::_Sentinel::__equal): Use _M_get_outer instead of
> _M_outer.
> (join_view::_M_outer): New data member when the underlying range
> is non-forward.
> (join_view::begin): Adjust definition as per P2770R0.
> (join_view::end): Likewise.
> (join_with_view::_M_outer_it): New data member when the
> underlying range is non-forward.
> (join_with_view::begin): Adjust definition as per P2770R0.
> (join_with_view::end): Likewise.
> (join_with_view::_Iterator::_M_outer_it): Make this data member
> present only when the underlying range is forward.
> (join_with_view::_Iterator::_M_get_outer): Define.
> (join_with_view::_Iterator::_Iterator): Split constructor
> taking _Parent argument into two as per P2770R0. Remove
> constraint on default constructor.
> (join_with_view::_Iterator::_M_update_inner): Adjust definition
> as per P2770R0.
> (join_with_view::_Iterator::_M_get_inner): Likewise.
> (join_with_view::_Iterator::_M_satisfy): Adjust calls to
> _M_get_inner. Use _M_get_outer instead of _M_outer_it.
> (join_with_view::_Iterator::operator==): Adjust constraints
> as per P2770R0.
> (join_with_view::_Sentinel::operator==): Use _M_get_outer
> instead of _M_outer_it.
> * testsuite/std/ranges/adaptors/p2770r0.cc: New test.
> ---
> libstdc++-v3/include/bits/regex.h | 6 +
> libstdc++-v3/include/std/ranges | 190 +++++++++++++-----
> .../testsuite/std/ranges/adaptors/p2770r0.cc | 110 ++++++++++
> 3 files changed, 257 insertions(+), 49 deletions(-)
> create mode 100644 libstdc++-v3/testsuite/std/ranges/adaptors/p2770r0.cc
>
> diff --git a/libstdc++-v3/include/bits/regex.h b/libstdc++-v3/include/bits/regex.h
> index 26ac6a21c31..2d306868721 100644
> --- a/libstdc++-v3/include/bits/regex.h
> +++ b/libstdc++-v3/include/bits/regex.h
> @@ -2740,6 +2740,9 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11
> typedef const value_type* pointer;
> typedef const value_type& reference;
> typedef std::forward_iterator_tag iterator_category;
> +#if __cplusplus > 201703L
> + typedef std::input_iterator_tag iterator_concept;
> +#endif
>
> /**
> * @brief Provides a singular iterator, useful for indicating
> @@ -2869,6 +2872,9 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11
> typedef const value_type* pointer;
> typedef const value_type& reference;
> typedef std::forward_iterator_tag iterator_category;
> +#if __cplusplus > 201703L
> + typedef std::input_iterator_tag iterator_concept;
> +#endif
>
> public:
> /**
> diff --git a/libstdc++-v3/include/std/ranges b/libstdc++-v3/include/std/ranges
> index 283d757faa4..ddcf50cc93e 100644
> --- a/libstdc++-v3/include/std/ranges
> +++ b/libstdc++-v3/include/std/ranges
> @@ -2705,6 +2705,14 @@ namespace views::__adaptor
> inline constexpr _DropWhile drop_while;
> } // namespace views
>
> + namespace __detail
> + {
> + template<typename _Tp>
> + constexpr _Tp&
> + __as_lvalue(_Tp&& __t)
> + { return static_cast<_Tp&>(__t); }
> + } // namespace __detail
> +
> template<input_range _Vp>
> requires view<_Vp> && input_range<range_reference_t<_Vp>>
> class join_view : public view_interface<join_view<_Vp>>
> @@ -2767,6 +2775,8 @@ namespace views::__adaptor
> using _Parent = __detail::__maybe_const_t<_Const, join_view>;
> using _Base = join_view::_Base<_Const>;
>
> + friend join_view;
> +
> static constexpr bool _S_ref_is_glvalue
> = join_view::_S_ref_is_glvalue<_Const>;
>
> @@ -2780,9 +2790,10 @@ namespace views::__adaptor
> return _M_parent->_M_inner._M_emplace_deref(__x);
> };
>
> - for (; _M_outer != ranges::end(_M_parent->_M_base); ++_M_outer)
> + _Outer_iter& __outer = _M_get_outer();
> + for (; __outer != ranges::end(_M_parent->_M_base); ++__outer)
> {
> - auto&& __inner = __update_inner(_M_outer);
> + auto&& __inner = __update_inner(__outer);
> _M_inner = ranges::begin(__inner);
> if (_M_inner != ranges::end(__inner))
> return;
> @@ -2811,7 +2822,36 @@ namespace views::__adaptor
> using _Outer_iter = join_view::_Outer_iter<_Const>;
> using _Inner_iter = join_view::_Inner_iter<_Const>;
>
> - _Outer_iter _M_outer = _Outer_iter();
> + constexpr _Outer_iter&
> + _M_get_outer()
> + {
> + if constexpr (forward_range<_Base>)
> + return _M_outer;
> + else
> + return *_M_parent->_M_outer;
> + }
> +
> + constexpr const _Outer_iter&
> + _M_get_outer() const
> + {
> + if constexpr (forward_range<_Base>)
> + return _M_outer;
> + else
> + return *_M_parent->_M_outer;
> + }
> +
> + constexpr
> + _Iterator(_Parent* __parent, _Outer_iter __outer) requires forward_range<_Base>
> + : _M_outer(std::move(__outer)), _M_parent(__parent)
> + { _M_satisfy(); }
> +
> + constexpr explicit
> + _Iterator(_Parent* __parent) requires (!forward_range<_Base>)
> + : _M_parent(__parent)
> + { _M_satisfy(); }
> +
> + [[no_unique_address]]
> + __detail::__maybe_present_t<forward_range<_Base>, _Outer_iter> _M_outer;
> optional<_Inner_iter> _M_inner;
> _Parent* _M_parent = nullptr;
>
> @@ -2823,13 +2863,7 @@ namespace views::__adaptor
> = common_type_t<range_difference_t<_Base>,
> range_difference_t<range_reference_t<_Base>>>;
>
> - _Iterator() requires default_initializable<_Outer_iter> = default;
> -
> - constexpr
> - _Iterator(_Parent* __parent, _Outer_iter __outer)
> - : _M_outer(std::move(__outer)),
> - _M_parent(__parent)
> - { _M_satisfy(); }
> + _Iterator() = default;
>
> constexpr
> _Iterator(_Iterator<!_Const> __i)
> @@ -2857,13 +2891,13 @@ namespace views::__adaptor
> {
> auto&& __inner_range = [this] () -> auto&& {
> if constexpr (_S_ref_is_glvalue)
> - return *_M_outer;
> + return *_M_get_outer();
> else
> return *_M_parent->_M_inner;
> }();
> if (++*_M_inner == ranges::end(__inner_range))
> {
> - ++_M_outer;
> + ++_M_get_outer();
> _M_satisfy();
> }
> return *this;
> @@ -2890,9 +2924,9 @@ namespace views::__adaptor
> && common_range<range_reference_t<_Base>>
> {
> if (_M_outer == ranges::end(_M_parent->_M_base))
> - _M_inner = ranges::end(*--_M_outer);
> - while (*_M_inner == ranges::begin(*_M_outer))
> - *_M_inner = ranges::end(*--_M_outer);
> + _M_inner = ranges::end(__detail::__as_lvalue(*--_M_outer));
> + while (*_M_inner == ranges::begin(__detail::__as_lvalue(*_M_outer)))
> + *_M_inner = ranges::end(__detail::__as_lvalue(*--_M_outer));
> --*_M_inner;
> return *this;
> }
> @@ -2911,7 +2945,7 @@ namespace views::__adaptor
> friend constexpr bool
> operator==(const _Iterator& __x, const _Iterator& __y)
> requires _S_ref_is_glvalue
> - && equality_comparable<_Outer_iter>
> + && forward_range<_Base>
> && equality_comparable<_Inner_iter>
> {
> return (__x._M_outer == __y._M_outer
> @@ -2943,7 +2977,7 @@ namespace views::__adaptor
> template<bool _Const2>
> constexpr bool
> __equal(const _Iterator<_Const2>& __i) const
> - { return __i._M_outer == _M_end; }
> + { return __i._M_get_outer() == _M_end; }
>
> sentinel_t<_Base> _M_end = sentinel_t<_Base>();
>
> @@ -2972,6 +3006,9 @@ namespace views::__adaptor
> };
>
> _Vp _M_base = _Vp();
> + [[no_unique_address]]
> + __detail::__maybe_present_t<!forward_range<_Vp>,
> + __detail::__non_propagating_cache<iterator_t<_Vp>>> _M_outer;
> [[no_unique_address]]
> __detail::__non_propagating_cache<remove_cv_t<_InnerRange>> _M_inner;
>
> @@ -2994,16 +3031,25 @@ namespace views::__adaptor
> constexpr auto
> begin()
> {
> - constexpr bool __use_const
> - = (__detail::__simple_view<_Vp>
> - && is_reference_v<range_reference_t<_Vp>>);
> - return _Iterator<__use_const>{this, ranges::begin(_M_base)};
> + if constexpr (forward_range<_Vp>)
> + {
> + constexpr bool __use_const
> + = (__detail::__simple_view<_Vp>
> + && is_reference_v<range_reference_t<_Vp>>);
> + return _Iterator<__use_const>{this, ranges::begin(_M_base)};
> + }
> + else
> + {
> + _M_outer = ranges::begin(_M_base);
> + return _Iterator<false>{this};
> + }
> }
>
> constexpr auto
> begin() const
> - requires input_range<const _Vp>
> + requires forward_range<const _Vp>
> && is_reference_v<range_reference_t<const _Vp>>
> + && input_range<range_reference_t<const _Vp>>
> {
> return _Iterator<true>{this, ranges::begin(_M_base)};
> }
> @@ -3022,11 +3068,11 @@ namespace views::__adaptor
>
> constexpr auto
> end() const
> - requires input_range<const _Vp>
> + requires forward_range<const _Vp>
> && is_reference_v<range_reference_t<const _Vp>>
> + && input_range<range_reference_t<const _Vp>>
> {
> - if constexpr (forward_range<const _Vp>
> - && is_reference_v<range_reference_t<const _Vp>>
> + if constexpr (is_reference_v<range_reference_t<const _Vp>>
> && forward_range<range_reference_t<const _Vp>>
> && common_range<const _Vp>
> && common_range<range_reference_t<const _Vp>>)
> @@ -6948,6 +6994,9 @@ namespace views::__adaptor
> using _InnerRange = range_reference_t<_Vp>;
>
> _Vp _M_base = _Vp();
> + [[no_unique_address]]
> + __detail::__maybe_present_t<!forward_range<_Vp>,
> + __detail::__non_propagating_cache<iterator_t<_Vp>>> _M_outer_it;
> __detail::__non_propagating_cache<remove_cv_t<_InnerRange>> _M_inner;
> _Pattern _M_pattern = _Pattern();
>
> @@ -7035,16 +7084,25 @@ namespace views::__adaptor
> 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)};
> + if constexpr (forward_range<_Vp>)
> + {
> + 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)};
> + }
> + else
> + {
> + _M_outer_it = ranges::begin(_M_base);
> + return _Iterator<false>{*this};
> + }
> }
>
> constexpr auto
> begin() const
> - requires input_range<const _Vp>
> + requires forward_range<const _Vp>
> && forward_range<const _Pattern>
> && is_reference_v<range_reference_t<const _Vp>>
> + && input_range<range_reference_t<const _Vp>>
> { return _Iterator<true>{*this, ranges::begin(_M_base)}; }
>
> constexpr auto
> @@ -7062,13 +7120,13 @@ namespace views::__adaptor
>
> constexpr auto
> end() const
> - requires input_range<const _Vp>
> + requires forward_range<const _Vp>
> && forward_range<const _Pattern>
> && is_reference_v<range_reference_t<const _Vp>>
> + && input_range<range_reference_t<const _Vp>>
> {
> using _InnerConstRange = range_reference_t<const _Vp>;
> - if constexpr (forward_range<const _Vp>
> - && forward_range<_InnerConstRange>
> + if constexpr (forward_range<_InnerConstRange>
> && common_range<const _Vp>
> && common_range<_InnerConstRange>)
> return _Iterator<true>{*this, ranges::end(_M_base)};
> @@ -7105,35 +7163,69 @@ namespace views::__adaptor
> static constexpr bool _S_ref_is_glvalue = join_with_view::_S_ref_is_glvalue<_Const>;
>
> _Parent* _M_parent = nullptr;
> - _OuterIter _M_outer_it = _OuterIter();
> + [[no_unique_address]]
> + __detail::__maybe_present_t<forward_range<_Base>, _OuterIter> _M_outer_it;
> variant<_PatternIter, _InnerIter> _M_inner_it;
>
> + constexpr _OuterIter&
> + _M_get_outer()
> + {
> + if constexpr (forward_range<_Base>)
> + return _M_outer_it;
> + else
> + return *_M_parent->_M_outer_it;
> + }
> +
> + constexpr const _OuterIter&
> + _M_get_outer() const
> + {
> + if constexpr (forward_range<_Base>)
> + return _M_outer_it;
> + else
> + return *_M_parent->_M_outer_it;
> + }
> +
> constexpr
> - _Iterator(_Parent& __parent, iterator_t<_Base> __outer)
> + _Iterator(_Parent& __parent, _OuterIter __outer)
> + requires forward_range<_Base>
> : _M_parent(std::__addressof(__parent)), _M_outer_it(std::move(__outer))
> {
> - if (_M_outer_it != ranges::end(_M_parent->_M_base))
> + if (_M_get_outer() != ranges::end(_M_parent->_M_base))
> + {
> + auto&& __inner = _M_update_inner();
> + _M_inner_it.template emplace<1>(ranges::begin(__inner));
> + _M_satisfy();
> + }
> + }
> +
> + constexpr
> + _Iterator(_Parent& __parent)
> + requires (!forward_range<_Base>)
> + : _M_parent(std::__addressof(__parent))
> + {
> + if (_M_get_outer() != ranges::end(_M_parent->_M_base))
> {
> - auto&& __inner = _M_update_inner(_M_outer_it);
> + auto&& __inner = _M_update_inner();
> _M_inner_it.template emplace<1>(ranges::begin(__inner));
> _M_satisfy();
> }
> }
>
> - constexpr auto&&
> - _M_update_inner(const _OuterIter& __x)
> + constexpr auto&
> + _M_update_inner()
> {
> + _OuterIter& __outer = _M_get_outer();
> if constexpr (_S_ref_is_glvalue)
> - return *__x;
> + return __detail::__as_lvalue(*__outer);
> else
> - return _M_parent->_M_inner._M_emplace_deref(__x);
> + return _M_parent->_M_inner._M_emplace_deref(__outer);
> }
>
> - constexpr auto&&
> - _M_get_inner(const _OuterIter& __x)
> + constexpr auto&
> + _M_get_inner()
> {
> if constexpr (_S_ref_is_glvalue)
> - return *__x;
> + return __detail::__as_lvalue(*_M_get_outer());
> else
> return *_M_parent->_M_inner;
> }
> @@ -7148,16 +7240,16 @@ namespace views::__adaptor
> if (std::get<0>(_M_inner_it) != ranges::end(_M_parent->_M_pattern))
> break;
>
> - auto&& __inner = _M_update_inner(_M_outer_it);
> + auto&& __inner = _M_update_inner();
> _M_inner_it.template emplace<1>(ranges::begin(__inner));
> }
> else
> {
> - auto&& __inner = _M_get_inner(_M_outer_it);
> + auto&& __inner = _M_get_inner();
> if (std::get<1>(_M_inner_it) != ranges::end(__inner))
> break;
>
> - if (++_M_outer_it == ranges::end(_M_parent->_M_base))
> + if (++_M_get_outer() == ranges::end(_M_parent->_M_base))
> {
> if constexpr (_S_ref_is_glvalue)
> _M_inner_it.template emplace<0>();
> @@ -7196,7 +7288,7 @@ namespace views::__adaptor
> iter_difference_t<_InnerIter>,
> iter_difference_t<_PatternIter>>;
>
> - _Iterator() requires default_initializable<_OuterIter> = default;
> + _Iterator() = default;
>
> constexpr
> _Iterator(_Iterator<!_Const> __i)
> @@ -7306,7 +7398,7 @@ namespace views::__adaptor
> friend constexpr bool
> operator==(const _Iterator& __x, const _Iterator& __y)
> requires _S_ref_is_glvalue
> - && equality_comparable<_OuterIter> && equality_comparable<_InnerIter>
> + && forward_range<_Base> && equality_comparable<_InnerIter>
> { return __x._M_outer_it == __y._M_outer_it && __x._M_inner_it ==__y._M_inner_it; }
>
> friend constexpr common_reference_t<iter_rvalue_reference_t<_InnerIter>,
> @@ -7373,7 +7465,7 @@ namespace views::__adaptor
> 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; }
> + { return __x._M_get_outer() == __y._M_end; }
> };
>
> namespace views
> diff --git a/libstdc++-v3/testsuite/std/ranges/adaptors/p2770r0.cc b/libstdc++-v3/testsuite/std/ranges/adaptors/p2770r0.cc
> new file mode 100644
> index 00000000000..15d71b2faa9
> --- /dev/null
> +++ b/libstdc++-v3/testsuite/std/ranges/adaptors/p2770r0.cc
> @@ -0,0 +1,110 @@
> +// { dg-options "-std=gnu++20" }
> +// { dg-do run { target c++20 } }
> +
> +#include <ranges>
> +#include <algorithm>
> +#include <regex>
> +#include <string_view>
> +#include <testsuite_hooks.h>
> +
> +namespace ranges = std::ranges;
> +namespace views = std::views;
> +
> +void
> +test01()
> +{
> + // Test case from LWG 3698
> + char const text[] = "Hello";
> + std::regex regex{"[a-z]"};
> +
> + auto lower
> + = ranges::subrange(std::cregex_iterator(ranges::begin(text),
> + ranges::end(text),
> + regex),
> + std::cregex_iterator{})
> + | views::join
> + | views::transform([](auto const& sm) {
> + return std::string_view(sm.first, sm.second);
> + });
> +
> + VERIFY( ranges::equal(lower, (std::string_view[]){"e", "l", "l", "o"}));
> +}
> +
> +void
> +test02()
> +{
> +#if __cpp_lib_ranges_join_with
> + // Analogous test case from LWG 3698 for join_with_view
> + char const text[] = "Hello";
> + std::regex regex{"[a-z]"};
> +
> + auto lower
> + = ranges::subrange(std::cregex_iterator(ranges::begin(text),
> + ranges::end(text),
> + regex),
> + std::cregex_iterator{})
> + | views::join_with(views::empty<std::sub_match<const char*>>)
> + | views::transform([](auto const& sm) {
> + return std::string_view(sm.first, sm.second);
> + });
> +
> + VERIFY( ranges::equal(lower, (std::string_view[]){"e", "l", "l", "o"}));
> +#endif
> +}
> +
> +void
> +test03()
> +{
> + // Test case from LWG 3700
> + auto r = views::iota(0, 5) | views::split(1);
> + auto s = views::single(r);
> + auto j = s | views::join;
> + auto f = j.front();
> +}
> +
> +void
> +test04()
> +{
> +#if __cpp_lib_ranges_join_with
> + // Analogous test case from LWG 3700 for join_with_view
> + auto r = views::iota(0, 5) | views::split(1);
> + auto s = views::single(r);
> + auto j = s | views::join_with(views::empty<ranges::range_value_t<decltype(r)>>);
> + auto f = j.front();
> +#endif
> +}
> +
> +void
> +test05()
> +{
> + // Test case from LWG 3791
> + std::vector<std::vector<int>> v = {{1}};
> + auto r = v
> + | views::transform([](auto& x) -> auto&& { return std::move(x); })
> + | views::join;
> + auto e = --r.end();
> +}
> +
> +void
> +test06()
> +{
> +#if __cpp_lib_ranges_join_with
> + // Analogous test case from LWG 3791 for join_with_view
> + std::vector<std::vector<int>> v = {{1}};
> + auto r = v
> + | views::transform([](auto& x) -> auto&& { return std::move(x); })
> + | views::join_with(views::empty<int>);
> + auto e = --r.end();
> +#endif
> +}
> +
> +int
> +main()
> +{
> + test01();
> + test02();
> + test03();
> + test04();
> + test05();
> + test06();
> +}
> --
> 2.40.0.335.g9857273be0
>
next prev parent reply other threads:[~2023-08-16 16:04 UTC|newest]
Thread overview: 3+ messages / expand[flat|nested] mbox.gz Atom feed top
2023-04-17 13:39 Patrick Palka
2023-08-16 16:04 ` Patrick Palka [this message]
2023-08-16 17:28 ` Jonathan Wakely
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=CAMOnLZbNSZD8kyw28_LqCZ0Chw6rpFah1EbBBFCnTuDyGEUhbA@mail.gmail.com \
--to=ppalka@redhat.com \
--cc=gcc-patches@gcc.gnu.org \
--cc=libstdc++@gcc.gnu.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).