| Message ID | 20210430143835.893089-1-ppalka@redhat.com |
|---|---|
| State | New |
| Headers | show |
| Series | libstdc++: Implement P2328 changes to join_view | expand |
On 30/04/21 10:38 -0400, Patrick Palka via Libstdc++ wrote: >This implements the wording changes of "join_view should join all views >of ranges". > >Tested on x86_64-pc-linux-gnu, does this look OK for trunk? OK, thanks. >libstdc++-v3/ChangeLog: > > * include/std/ranges (__detail::__non_propating_cache): Define > as per P2328. > (join_view): Remove constraints on the value and reference types > of the wrapped iterator type as per P2328. > (join_view::_Iterator::_M_satisfy): Adjust as per P2328. > (join_view::_Iterator::operator++): Likewise. > (join_view::_M_inner): Use __non_propating_cache as per P2328. > Remove now-redundant use of __maybe_present_t. > * testsuite/std/ranges/adaptors/join.cc (test10): New test. >--- > libstdc++-v3/include/std/ranges | 70 ++++++++++++++++--- > .../testsuite/std/ranges/adaptors/join.cc | 12 ++++ > 2 files changed, 71 insertions(+), 11 deletions(-) > >diff --git a/libstdc++-v3/include/std/ranges b/libstdc++-v3/include/std/ranges >index 4be643baeaa..b43f9b337a4 100644 >--- a/libstdc++-v3/include/std/ranges >+++ b/libstdc++-v3/include/std/ranges >@@ -2258,10 +2258,61 @@ namespace views::__adaptor > inline constexpr _DropWhile drop_while; > } // namespace views > >+ namespace __detail >+ { >+ template<typename _Tp> >+ struct __non_propagating_cache >+ { >+ // When _Tp is not an object type (e.g. is a reference type), we make >+ // __non_propagating_cache<_Tp> empty rather than an invalid type so >+ // that users can easily conditionally declare data members with this >+ // type (such as join_view::_M_inner). >+ }; >+ >+ template<typename _Tp> >+ requires is_object_v<_Tp> >+ struct __non_propagating_cache<_Tp> : private optional<_Tp> >+ { >+ __non_propagating_cache() = default; >+ >+ constexpr >+ __non_propagating_cache(const __non_propagating_cache&) noexcept >+ { } >+ >+ constexpr >+ __non_propagating_cache(__non_propagating_cache&& __other) noexcept >+ { __other.reset(); } >+ >+ constexpr __non_propagating_cache& >+ operator=(const __non_propagating_cache& __other) noexcept >+ { >+ if (std::__addressof(__other) != this) >+ this->reset(); >+ return *this; >+ } >+ >+ constexpr __non_propagating_cache& >+ operator=(__non_propagating_cache&& __other) noexcept >+ { >+ this->reset(); >+ __other.reset(); >+ return *this; >+ } >+ >+ using optional<_Tp>::operator*; >+ >+ template<typename _Iter> >+ _Tp& >+ _M_emplace_deref(const _Iter& __i) >+ { >+ this->reset(); >+ return this->emplace(*__i); >+ } >+ }; >+ } >+ > template<input_range _Vp> > requires view<_Vp> && input_range<range_reference_t<_Vp>> >- && (is_reference_v<range_reference_t<_Vp>> >- || view<range_value_t<_Vp>>) > class join_view : public view_interface<join_view<_Vp>> > { > private: >@@ -2327,17 +2378,16 @@ namespace views::__adaptor > constexpr void > _M_satisfy() > { >- auto __update_inner = [this] (range_reference_t<_Base> __x) -> auto& >- { >+ auto __update_inner = [this] (const iterator_t<_Base>& __x) -> auto&& { > if constexpr (_S_ref_is_glvalue) >- return __x; >+ return *__x; > else >- return (_M_parent->_M_inner = views::all(std::move(__x))); >+ return _M_parent->_M_inner._M_emplace_deref(__x); > }; > > for (; _M_outer != ranges::end(_M_parent->_M_base); ++_M_outer) > { >- auto& __inner = __update_inner(*_M_outer); >+ auto&& __inner = __update_inner(_M_outer); > _M_inner = ranges::begin(__inner); > if (_M_inner != ranges::end(__inner)) > return; >@@ -2413,7 +2463,7 @@ namespace views::__adaptor > if constexpr (_S_ref_is_glvalue) > return *_M_outer; > else >- return _M_parent->_M_inner; >+ return *_M_parent->_M_inner; > }(); > if (++_M_inner == ranges::end(__inner_range)) > { >@@ -2524,10 +2574,8 @@ namespace views::__adaptor > friend _Sentinel<!_Const>; > }; > >- // XXX: _M_inner is "present only when !is_reference_v<_InnerRange>" > [[no_unique_address]] >- __detail::__maybe_present_t<!is_reference_v<_InnerRange>, >- views::all_t<_InnerRange>> _M_inner; >+ __detail::__non_propagating_cache<remove_cv_t<_InnerRange>> _M_inner; > _Vp _M_base = _Vp(); > > public: >diff --git a/libstdc++-v3/testsuite/std/ranges/adaptors/join.cc b/libstdc++-v3/testsuite/std/ranges/adaptors/join.cc >index fb06a7698af..6890b105eab 100644 >--- a/libstdc++-v3/testsuite/std/ranges/adaptors/join.cc >+++ b/libstdc++-v3/testsuite/std/ranges/adaptors/join.cc >@@ -160,6 +160,17 @@ test09() > static_assert(!requires { 0 | join; }); > } > >+void >+test10() >+{ >+// Verify P2328 changes. >+ int r[] = {1, 2, 3}; >+ auto v = r >+ | views::transform([] (int n) { return std::vector{{n, -n}}; }) >+ | views::join; >+ VERIFY( ranges::equal(v, (int[]){1, -1, 2, -2, 3, -3}) ); >+} >+ > int > main() > { >@@ -172,4 +183,5 @@ main() > test07(); > test08(); > test09(); >+ test10(); > } >-- >2.31.1.362.g311531c9de >
On Fri, Apr 30, 2021 at 12:11 PM Patrick Palka via Libstdc++ <libstdc++@gcc.gnu.org> wrote: > > + template<typename _Iter> > + _Tp& > + _M_emplace_deref(const _Iter& __i) > + { > + this->reset(); > + return this->emplace(*__i); > + } This incurs a move, avoiding of which is the sole reason for emplace-deref's existence. > + }; > + } > +
On Fri, 30 Apr 2021, Tim Song wrote: > On Fri, Apr 30, 2021 at 12:11 PM Patrick Palka via Libstdc++ > <libstdc++@gcc.gnu.org> wrote: > > > > + template<typename _Iter> > > + _Tp& > > + _M_emplace_deref(const _Iter& __i) > > + { > > + this->reset(); > > + return this->emplace(*__i); > > + } > > This incurs a move, avoiding of which is the sole reason for > emplace-deref's existence. Ah thanks, I had missed that... IIUC, if we instead derive from optional's internal base class _Optional_base, we can easily get at the underlying storage for the object and directly initialize it with '*__i' and avoid the move. How does the the following adjustment to the patch look? -- >8 -- diff --git a/libstdc++-v3/include/std/ranges b/libstdc++-v3/include/std/ranges index 971898f5492..f1db4a238ef 100644 --- a/libstdc++-v3/include/std/ranges +++ b/libstdc++-v3/include/std/ranges @@ -2254,7 +2254,7 @@ namespace views::__adaptor template<typename _Tp> requires is_object_v<_Tp> - struct __non_propagating_cache<_Tp> : private optional<_Tp> + struct __non_propagating_cache<_Tp> : private _Optional_base<_Tp> { __non_propagating_cache() = default; @@ -2264,32 +2264,36 @@ namespace views::__adaptor constexpr __non_propagating_cache(__non_propagating_cache&& __other) noexcept - { __other.reset(); } + { __other._M_reset(); } constexpr __non_propagating_cache& operator=(const __non_propagating_cache& __other) noexcept { if (std::__addressof(__other) != this) - this->reset(); + this->_M_reset(); return *this; } constexpr __non_propagating_cache& operator=(__non_propagating_cache&& __other) noexcept { - this->reset(); - __other.reset(); + this->_M_reset(); + __other._M_reset(); return *this; } - using optional<_Tp>::operator*; + constexpr _Tp& + operator*() noexcept + { return this->_M_get(); } template<typename _Iter> _Tp& _M_emplace_deref(const _Iter& __i) { - this->reset(); - return this->emplace(*__i); + this->_M_reset(); + ::new ((void *) std::__addressof(this->_M_payload._M_payload)) _Tp(*__i); + this->_M_payload._M_engaged = true; + return this->_M_get(); } }; }
On 30/04/21 17:34 -0400, Patrick Palka via Libstdc++ wrote: >On Fri, 30 Apr 2021, Tim Song wrote: > >> On Fri, Apr 30, 2021 at 12:11 PM Patrick Palka via Libstdc++ >> <libstdc++@gcc.gnu.org> wrote: >> > >> > + template<typename _Iter> >> > + _Tp& >> > + _M_emplace_deref(const _Iter& __i) >> > + { >> > + this->reset(); >> > + return this->emplace(*__i); >> > + } >> >> This incurs a move, avoiding of which is the sole reason for >> emplace-deref's existence. > >Ah thanks, I had missed that... IIUC, if we instead derive from >optional's internal base class _Optional_base, we can easily get at the >underlying storage for the object and directly initialize it with '*__i' >and avoid the move. How does the the following adjustment to the patch >look? Looks good to me, thanks. >-- >8 -- > >diff --git a/libstdc++-v3/include/std/ranges b/libstdc++-v3/include/std/ranges > >index 971898f5492..f1db4a238ef 100644 >--- a/libstdc++-v3/include/std/ranges >+++ b/libstdc++-v3/include/std/ranges >@@ -2254,7 +2254,7 @@ namespace views::__adaptor > > template<typename _Tp> > requires is_object_v<_Tp> >- struct __non_propagating_cache<_Tp> : private optional<_Tp> >+ struct __non_propagating_cache<_Tp> : private _Optional_base<_Tp> > { > __non_propagating_cache() = default; > >@@ -2264,32 +2264,36 @@ namespace views::__adaptor > > constexpr > __non_propagating_cache(__non_propagating_cache&& __other) noexcept >- { __other.reset(); } >+ { __other._M_reset(); } > > constexpr __non_propagating_cache& > operator=(const __non_propagating_cache& __other) noexcept > { > if (std::__addressof(__other) != this) >- this->reset(); >+ this->_M_reset(); > return *this; > } > > constexpr __non_propagating_cache& > operator=(__non_propagating_cache&& __other) noexcept > { >- this->reset(); >- __other.reset(); >+ this->_M_reset(); >+ __other._M_reset(); > return *this; > } > >- using optional<_Tp>::operator*; >+ constexpr _Tp& >+ operator*() noexcept >+ { return this->_M_get(); } > > template<typename _Iter> > _Tp& > _M_emplace_deref(const _Iter& __i) > { >- this->reset(); >- return this->emplace(*__i); >+ this->_M_reset(); >+ ::new ((void *) std::__addressof(this->_M_payload._M_payload)) _Tp(*__i); >+ this->_M_payload._M_engaged = true; >+ return this->_M_get(); > } > }; > } >
On 30/04/21 12:43 -0500, Tim Song via Libstdc++ wrote: >On Fri, Apr 30, 2021 at 12:11 PM Patrick Palka via Libstdc++ ><libstdc++@gcc.gnu.org> wrote: >> >> + template<typename _Iter> >> + _Tp& >> + _M_emplace_deref(const _Iter& __i) >> + { >> + this->reset(); >> + return this->emplace(*__i); >> + } > >This incurs a move, avoiding of which is the sole reason for >emplace-deref's existence. I completely forgot about that, even though we only discussed it last week. Thanks, Tim.
On Fri, 30 Apr 2021, Jonathan Wakely wrote: > On 30/04/21 17:34 -0400, Patrick Palka via Libstdc++ wrote: > > On Fri, 30 Apr 2021, Tim Song wrote: > > > > > On Fri, Apr 30, 2021 at 12:11 PM Patrick Palka via Libstdc++ > > > <libstdc++@gcc.gnu.org> wrote: > > > > > > > > + template<typename _Iter> > > > > + _Tp& > > > > + _M_emplace_deref(const _Iter& __i) > > > > + { > > > > + this->reset(); > > > > + return this->emplace(*__i); > > > > + } > > > > > > This incurs a move, avoiding of which is the sole reason for > > > emplace-deref's existence. > > > > Ah thanks, I had missed that... IIUC, if we instead derive from > > optional's internal base class _Optional_base, we can easily get at the > > underlying storage for the object and directly initialize it with '*__i' > > and avoid the move. How does the the following adjustment to the patch > > look? > > Looks good to me, thanks. Here's what I ended up committing, complete with a comment to __non_propagating_cache::_M_emplace_deref and a test to verify we're avoiding the extra move: -- >8 -- Subject: [PATCH] libstdc++: Implement P2328 changes to join_view This implements the wording changes of P2328R0 "join_view should join all views of ranges". libstdc++-v3/ChangeLog: * include/std/ranges (__detail::__non_propating_cache): Define as per P2328. (join_view): Remove constraints on the value and reference types of the wrapped iterator type as per P2328. (join_view::_Iterator::_M_satisfy): Adjust as per P2328. (join_view::_Iterator::operator++): Likewise. (join_view::_M_inner): Use __non_propating_cache as per P2328. Remove now-redundant use of __maybe_present_t. * testsuite/std/ranges/adaptors/join.cc: Include <array>. (test10): New test. --- libstdc++-v3/include/std/ranges | 77 ++++++++++++++++--- .../testsuite/std/ranges/adaptors/join.cc | 24 ++++++ 2 files changed, 90 insertions(+), 11 deletions(-) diff --git a/libstdc++-v3/include/std/ranges b/libstdc++-v3/include/std/ranges index 4975d5c630b..4a7ca49b45d 100644 --- a/libstdc++-v3/include/std/ranges +++ b/libstdc++-v3/include/std/ranges @@ -2241,10 +2241,68 @@ namespace views::__adaptor inline constexpr _DropWhile drop_while; } // namespace views + namespace __detail + { + template<typename _Tp> + struct __non_propagating_cache + { + // When _Tp is not an object type (e.g. is a reference type), we make + // __non_propagating_cache<_Tp> empty rather than ill-formed so that + // users can easily conditionally declare data members with this type + // (such as join_view::_M_inner). + }; + + template<typename _Tp> + requires is_object_v<_Tp> + struct __non_propagating_cache<_Tp> : private _Optional_base<_Tp> + { + __non_propagating_cache() = default; + + constexpr + __non_propagating_cache(const __non_propagating_cache&) noexcept + { } + + constexpr + __non_propagating_cache(__non_propagating_cache&& __other) noexcept + { __other._M_reset(); } + + constexpr __non_propagating_cache& + operator=(const __non_propagating_cache& __other) noexcept + { + if (std::__addressof(__other) != this) + this->_M_reset(); + return *this; + } + + constexpr __non_propagating_cache& + operator=(__non_propagating_cache&& __other) noexcept + { + this->_M_reset(); + __other._M_reset(); + return *this; + } + + constexpr _Tp& + operator*() noexcept + { return this->_M_get(); } + + template<typename _Iter> + _Tp& + _M_emplace_deref(const _Iter& __i) + { + this->_M_reset(); + // Using _Optional_base::_M_construct to initialize from '*__i' + // would incur an extra move due to the indirection, so we instead + // use placement new directly. + ::new ((void *) std::__addressof(this->_M_payload._M_payload)) _Tp(*__i); + this->_M_payload._M_engaged = true; + return this->_M_get(); + } + }; + } + template<input_range _Vp> requires view<_Vp> && input_range<range_reference_t<_Vp>> - && (is_reference_v<range_reference_t<_Vp>> - || view<range_value_t<_Vp>>) class join_view : public view_interface<join_view<_Vp>> { private: @@ -2310,17 +2368,16 @@ namespace views::__adaptor constexpr void _M_satisfy() { - auto __update_inner = [this] (range_reference_t<_Base> __x) -> auto& - { + auto __update_inner = [this] (const iterator_t<_Base>& __x) -> auto&& { if constexpr (_S_ref_is_glvalue) - return __x; + return *__x; else - return (_M_parent->_M_inner = views::all(std::move(__x))); + return _M_parent->_M_inner._M_emplace_deref(__x); }; for (; _M_outer != ranges::end(_M_parent->_M_base); ++_M_outer) { - auto& __inner = __update_inner(*_M_outer); + auto&& __inner = __update_inner(_M_outer); _M_inner = ranges::begin(__inner); if (_M_inner != ranges::end(__inner)) return; @@ -2396,7 +2453,7 @@ namespace views::__adaptor if constexpr (_S_ref_is_glvalue) return *_M_outer; else - return _M_parent->_M_inner; + return *_M_parent->_M_inner; }(); if (++_M_inner == ranges::end(__inner_range)) { @@ -2507,10 +2564,8 @@ namespace views::__adaptor friend _Sentinel<!_Const>; }; - // XXX: _M_inner is "present only when !is_reference_v<_InnerRange>" [[no_unique_address]] - __detail::__maybe_present_t<!is_reference_v<_InnerRange>, - views::all_t<_InnerRange>> _M_inner; + __detail::__non_propagating_cache<remove_cv_t<_InnerRange>> _M_inner; _Vp _M_base = _Vp(); public: diff --git a/libstdc++-v3/testsuite/std/ranges/adaptors/join.cc b/libstdc++-v3/testsuite/std/ranges/adaptors/join.cc index e6c71d771de..d774e8d9385 100644 --- a/libstdc++-v3/testsuite/std/ranges/adaptors/join.cc +++ b/libstdc++-v3/testsuite/std/ranges/adaptors/join.cc @@ -19,6 +19,7 @@ // { dg-do run { target c++2a } } #include <algorithm> +#include <array> #include <ranges> #include <string> #include <string_view> @@ -170,6 +171,28 @@ test10() VERIFY( ranges::next(v.begin()) == v.end() ); } +void +test11() +{ + // Verify P2328 changes. + int r[] = {1, 2, 3}; + auto v = r + | views::transform([] (int n) { return std::vector{{n, -n}}; }) + | views::join; + VERIFY( ranges::equal(v, (int[]){1, -1, 2, -2, 3, -3}) ); + + struct S { + S() = default; + S(const S&) = delete; + S(S&&) = delete; + }; + auto w = r + | views::transform([] (int) { return std::array<S, 2>{}; }) + | views::join; + for (auto& i : w) + ; +} + int main() { @@ -183,4 +206,5 @@ main() test08(); test09(); test10(); + test11(); }
diff --git a/libstdc++-v3/include/std/ranges b/libstdc++-v3/include/std/ranges index 4be643baeaa..b43f9b337a4 100644 --- a/libstdc++-v3/include/std/ranges +++ b/libstdc++-v3/include/std/ranges @@ -2258,10 +2258,61 @@ namespace views::__adaptor inline constexpr _DropWhile drop_while; } // namespace views + namespace __detail + { + template<typename _Tp> + struct __non_propagating_cache + { + // When _Tp is not an object type (e.g. is a reference type), we make + // __non_propagating_cache<_Tp> empty rather than an invalid type so + // that users can easily conditionally declare data members with this + // type (such as join_view::_M_inner). + }; + + template<typename _Tp> + requires is_object_v<_Tp> + struct __non_propagating_cache<_Tp> : private optional<_Tp> + { + __non_propagating_cache() = default; + + constexpr + __non_propagating_cache(const __non_propagating_cache&) noexcept + { } + + constexpr + __non_propagating_cache(__non_propagating_cache&& __other) noexcept + { __other.reset(); } + + constexpr __non_propagating_cache& + operator=(const __non_propagating_cache& __other) noexcept + { + if (std::__addressof(__other) != this) + this->reset(); + return *this; + } + + constexpr __non_propagating_cache& + operator=(__non_propagating_cache&& __other) noexcept + { + this->reset(); + __other.reset(); + return *this; + } + + using optional<_Tp>::operator*; + + template<typename _Iter> + _Tp& + _M_emplace_deref(const _Iter& __i) + { + this->reset(); + return this->emplace(*__i); + } + }; + } + template<input_range _Vp> requires view<_Vp> && input_range<range_reference_t<_Vp>> - && (is_reference_v<range_reference_t<_Vp>> - || view<range_value_t<_Vp>>) class join_view : public view_interface<join_view<_Vp>> { private: @@ -2327,17 +2378,16 @@ namespace views::__adaptor constexpr void _M_satisfy() { - auto __update_inner = [this] (range_reference_t<_Base> __x) -> auto& - { + auto __update_inner = [this] (const iterator_t<_Base>& __x) -> auto&& { if constexpr (_S_ref_is_glvalue) - return __x; + return *__x; else - return (_M_parent->_M_inner = views::all(std::move(__x))); + return _M_parent->_M_inner._M_emplace_deref(__x); }; for (; _M_outer != ranges::end(_M_parent->_M_base); ++_M_outer) { - auto& __inner = __update_inner(*_M_outer); + auto&& __inner = __update_inner(_M_outer); _M_inner = ranges::begin(__inner); if (_M_inner != ranges::end(__inner)) return; @@ -2413,7 +2463,7 @@ namespace views::__adaptor if constexpr (_S_ref_is_glvalue) return *_M_outer; else - return _M_parent->_M_inner; + return *_M_parent->_M_inner; }(); if (++_M_inner == ranges::end(__inner_range)) { @@ -2524,10 +2574,8 @@ namespace views::__adaptor friend _Sentinel<!_Const>; }; - // XXX: _M_inner is "present only when !is_reference_v<_InnerRange>" [[no_unique_address]] - __detail::__maybe_present_t<!is_reference_v<_InnerRange>, - views::all_t<_InnerRange>> _M_inner; + __detail::__non_propagating_cache<remove_cv_t<_InnerRange>> _M_inner; _Vp _M_base = _Vp(); public: diff --git a/libstdc++-v3/testsuite/std/ranges/adaptors/join.cc b/libstdc++-v3/testsuite/std/ranges/adaptors/join.cc index fb06a7698af..6890b105eab 100644 --- a/libstdc++-v3/testsuite/std/ranges/adaptors/join.cc +++ b/libstdc++-v3/testsuite/std/ranges/adaptors/join.cc @@ -160,6 +160,17 @@ test09() static_assert(!requires { 0 | join; }); } +void +test10() +{ +// Verify P2328 changes. + int r[] = {1, 2, 3}; + auto v = r + | views::transform([] (int n) { return std::vector{{n, -n}}; }) + | views::join; + VERIFY( ranges::equal(v, (int[]){1, -1, 2, -2, 3, -3}) ); +} + int main() { @@ -172,4 +183,5 @@ main() test07(); test08(); test09(); + test10(); }