| Message ID | 20210517154302.840608-1-ppalka@redhat.com |
|---|---|
| State | New |
| Headers | show |
| Series | libstdc++: Fix iterator caching inside range adaptors [PR100479] | expand |
On 17/05/21 11:43 -0400, Patrick Palka via Libstdc++ wrote: >This fixes two issues with our iterator caching as described in detail >in the PR. Since r12-336 added the __non_propagating_cache class >template as part of P2328, this patch just rewrites the _CachedPosition >partial specialization in terms of this class template. > >Tested on x86_64-pc-linux-gnu, does this look OK for trunk? OK, thanks. >Shall we >also backport this? I think so, but give it a couple of weeks (or more) on trunk first.
On Mon, May 17, 2021 at 11:46 AM Patrick Palka via Libstdc++ <libstdc++@gcc.gnu.org> wrote: > constexpr void > _M_set(const _Range&, const iterator_t<_Range>& __it) > { > __glibcxx_assert(!_M_has_value()); > - _M_iter = __it; > + this->_M_payload._M_payload._M_value = __it; > + this->_M_payload._M_engaged = true; > } > }; This part looks questionable - if we don't have a value then we can't assign to a nonexistent object. Also, I believe the offset partial specialization of _CachedPosition needs a change to invalidate the source on move.
On Mon, 17 May 2021, Tim Song wrote: > On Mon, May 17, 2021 at 11:46 AM Patrick Palka via Libstdc++ > <libstdc++@gcc.gnu.org> wrote: > > constexpr void > > _M_set(const _Range&, const iterator_t<_Range>& __it) > > { > > __glibcxx_assert(!_M_has_value()); > > - _M_iter = __it; > > + this->_M_payload._M_payload._M_value = __it; > > + this->_M_payload._M_engaged = true; > > } > > }; > > This part looks questionable - if we don't have a value then we can't > assign to a nonexistent object. Whoops, that was my lazy attempt at making the function constexpr-friendly without thinking enough about it. I now changed this to use std::construct_at appropriately. > > Also, I believe the offset partial specialization of _CachedPosition > needs a change to invalidate the source on move. Ah, true. I reckoned that because it's safe to propagate an offset on copy, we can leave alone its behavior on move. I changed this to propagate the cached offset on copy/move, but additionally invalidate the source object on move. How does this look? -- >8 -- Subject: [PATCH] libstdc++: Fix iterator caching inside range adaptors [PR100479] This fixes two issues with our iterator caching as described in detail in the PR. Since we recently added the __non_propagating_cache class template as part of r12-336 for P2328, this patch just rewrites the problematic _CachedPosition partial specialization in terms of this class template. For the offset partial specialization, it's safe to propagate the cached value on copy/move, but we should still invalidate the cached value in the source object on move. libstdc++-v3/ChangeLog: PR libstdc++/100479 * include/std/ranges (__detail::__non_propagating_cache): Move definition up to before that of _CachedPosition. Make base class _Optional_base protected instead of private. Add const overload for operator*. (__detail::_CachedPosition): Rewrite the partial specialization for forward ranges as a derived class of __non_propagating_cache. Remove the size constraint on the partial specialization for random access ranges. Add copy/move/copy-assignment/move-assignment members to the offset partial specialization for random access ranges that propagate the cached value but additionally invalidates it in the source object on move. * testsuite/std/ranges/adaptors/100479.cc: New test. --- libstdc++-v3/include/std/ranges | 158 ++++++++++-------- .../testsuite/std/ranges/adaptors/100479.cc | 113 +++++++++++++ 2 files changed, 204 insertions(+), 67 deletions(-) create mode 100644 libstdc++-v3/testsuite/std/ranges/adaptors/100479.cc diff --git a/libstdc++-v3/include/std/ranges b/libstdc++-v3/include/std/ranges index 1707aeaebcd..b48fbca3cf6 100644 --- a/libstdc++-v3/include/std/ranges +++ b/libstdc++-v3/include/std/ranges @@ -1139,6 +1139,67 @@ namespace views::__adaptor 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> : protected _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(); } + + constexpr const _Tp& + operator*() const 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<range _Range> struct _CachedPosition { @@ -1160,27 +1221,26 @@ namespace views::__adaptor template<forward_range _Range> struct _CachedPosition<_Range> + : protected __non_propagating_cache<iterator_t<_Range>> { - private: - iterator_t<_Range> _M_iter{}; - - public: constexpr bool _M_has_value() const - { return _M_iter != iterator_t<_Range>{}; } + { return this->_M_is_engaged(); } constexpr iterator_t<_Range> _M_get(const _Range&) const { __glibcxx_assert(_M_has_value()); - return _M_iter; + return **this; } constexpr void _M_set(const _Range&, const iterator_t<_Range>& __it) { __glibcxx_assert(!_M_has_value()); - _M_iter = __it; + std::construct_at(std::__addressof(this->_M_payload._M_payload), + in_place, __it); + this->_M_payload._M_engaged = true; } }; @@ -1193,6 +1253,30 @@ namespace views::__adaptor range_difference_t<_Range> _M_offset = -1; public: + _CachedPosition() = default; + + constexpr + _CachedPosition(const _CachedPosition&) = default; + + constexpr + _CachedPosition(_CachedPosition&& __other) noexcept + { *this = std::move(__other); } + + constexpr _CachedPosition& + operator=(const _CachedPosition&) = default; + + constexpr _CachedPosition& + operator=(_CachedPosition&& __other) noexcept + { + if (std::__addressof(__other) != this) + { + // Propagate the cached offset, but invalidate the source. + this->_M_offset = __other._M_offset; + __other._M_offset = -1; + } + return *this; + } + constexpr bool _M_has_value() const { return _M_offset >= 0; } @@ -2339,66 +2423,6 @@ 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>> class join_view : public view_interface<join_view<_Vp>> diff --git a/libstdc++-v3/testsuite/std/ranges/adaptors/100479.cc b/libstdc++-v3/testsuite/std/ranges/adaptors/100479.cc new file mode 100644 index 00000000000..bcf1b3596cc --- /dev/null +++ b/libstdc++-v3/testsuite/std/ranges/adaptors/100479.cc @@ -0,0 +1,113 @@ +// Copyright (C) 2021 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// <http://www.gnu.org/licenses/>. + +// { dg-options "-std=gnu++2a" } +// { dg-do run { target c++2a } } + +// PR libstdc++/100479 + +#include <ranges> +#include <testsuite_hooks.h> +#include <testsuite_iterators.h> + +using __gnu_test::test_forward_range; +using __gnu_test::test_random_access_range; + +namespace ranges = std::ranges; +namespace views = std::views; + +void +test01() +{ + // Verify we don't propagate cached iterators when copying/moving a forward + // range that memoizes its begin(). + static int pred_counter; + int x[] = {1,2,3,4,5}; + test_forward_range rx(x); + auto is_odd = [](auto n) { ++pred_counter; return n%2 != 0; }; + + auto v = rx | views::filter(is_odd); + v.begin(); v.begin(); + VERIFY( pred_counter == 1 ); // filter_view caches iterator for begin() + + auto w = v; + v.begin(); v.begin(); + VERIFY( pred_counter == 1 ); // cached iterator not invalidated on copy + w.begin(); w.begin(); + VERIFY( pred_counter == 2 ); // cached iterator not propagated on copy + + auto z = std::move(w); + w.begin(); w.begin(); + VERIFY( pred_counter == 3 ); // cached iterator invalidated on move + z.begin(); z.begin(); + VERIFY( pred_counter == 4 ); // cached iterator not propagated on move +} + +void +test02() +{ + // Verify we invalidate the cached offset when moving a random access range + // that memoizes its begin(). + static int pred_counter; + int x[] = {1,2,3,4,5}; + test_random_access_range rx(x); + auto is_odd = [](auto n) { ++pred_counter; return n%2 != 0; }; + + auto v = rx | views::filter(is_odd); + v.begin(); v.begin(); + VERIFY( pred_counter == 1 ); // filter_view caches iterator for begin() + + auto w = v; + v.begin(); v.begin(); + VERIFY( pred_counter == 1 ); // cached offset not invalidated on copy + w.begin(); w.begin(); + VERIFY( pred_counter == 1 ); // cached offset propagated on copy + + auto z = std::move(w); + w.begin(); w.begin(); + VERIFY( pred_counter == 2 ); // cached offset invalidated on move + z.begin(); z.begin(); + VERIFY( pred_counter == 2 ); // cached offset propagated on move +} + +constexpr bool +test03() +{ + // Propagating cached iterators during copy/move would cause these asserts + // to fail here. + auto v = views::single(1) + | views::split(1) + | views::drop(0) + | views::drop_while([](auto) { return false; }) + | views::filter([](auto) { return true; }); + static_assert(ranges::forward_range<decltype(v)>); + VERIFY( ranges::next(v.begin()) == v.end() ); + auto w = v; + VERIFY( ranges::next(w.begin()) == w.end() ); + auto z = std::move(w); + VERIFY( ranges::next(z.begin()) == z.end() ); + return true; +} + +int +main() +{ + test01(); + test02(); + test03(); + static_assert(test03()); +}
On Mon, May 17, 2021 at 2:59 PM Patrick Palka <ppalka@redhat.com> wrote: > > + constexpr _CachedPosition& > + operator=(_CachedPosition&& __other) noexcept > + { > + if (std::__addressof(__other) != this) I don't think we need this check - self-move-assigning the underlying view isn't required to be a no-op, so we should still invalidate. > + { > + // Propagate the cached offset, but invalidate the source. > + this->_M_offset = __other._M_offset; > + __other._M_offset = -1; > + } > + return *this; > + }
On Mon, 17 May 2021, Tim Song wrote: > On Mon, May 17, 2021 at 2:59 PM Patrick Palka <ppalka@redhat.com> wrote: > > > > + constexpr _CachedPosition& > > + operator=(_CachedPosition&& __other) noexcept > > + { > > + if (std::__addressof(__other) != this) > > I don't think we need this check - self-move-assigning the underlying > view isn't required to be a no-op, so we should still invalidate. Sounds good, so like so: -- >8 -- Subject: [PATCH] libstdc++: Fix iterator caching inside range adaptors [PR100479] This fixes two issues with our iterator caching as described in detail in the PR. Since we recently added the __non_propagating_cache class template as part of r12-336 for P2328, this patch just rewrites the problematic _CachedPosition partial specialization in terms of this class template. For the offset partial specialization, it's safe to propagate the cached offset on copy/move, but we should still invalidate the cached offset in the source object on move. libstdc++-v3/ChangeLog: PR libstdc++/100479 * include/std/ranges (__detail::__non_propagating_cache): Move definition up to before that of _CachedPosition. Make base class _Optional_base protected instead of private. Add const overload for operator*. (__detail::_CachedPosition): Rewrite the partial specialization for forward ranges as a derived class of __non_propagating_cache. Remove the size constraint on the partial specialization for random access ranges. Add copy/move/copy-assignment/move-assignment members to the offset partial specialization for random access ranges that propagate the cached value but additionally invalidate it in the source object on move. * testsuite/std/ranges/adaptors/100479.cc: New test. --- libstdc++-v3/include/std/ranges | 155 ++++++++++-------- .../testsuite/std/ranges/adaptors/100479.cc | 113 +++++++++++++ 2 files changed, 201 insertions(+), 67 deletions(-) create mode 100644 libstdc++-v3/testsuite/std/ranges/adaptors/100479.cc diff --git a/libstdc++-v3/include/std/ranges b/libstdc++-v3/include/std/ranges index ca62f73ae5d..f7ffee56f56 100644 --- a/libstdc++-v3/include/std/ranges +++ b/libstdc++-v3/include/std/ranges @@ -1039,6 +1039,67 @@ namespace views::__adaptor 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> : protected _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(); } + + constexpr const _Tp& + operator*() const 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<range _Range> struct _CachedPosition { @@ -1060,27 +1121,26 @@ namespace views::__adaptor template<forward_range _Range> struct _CachedPosition<_Range> + : protected __non_propagating_cache<iterator_t<_Range>> { - private: - iterator_t<_Range> _M_iter{}; - - public: constexpr bool _M_has_value() const - { return _M_iter != iterator_t<_Range>{}; } + { return this->_M_is_engaged(); } constexpr iterator_t<_Range> _M_get(const _Range&) const { __glibcxx_assert(_M_has_value()); - return _M_iter; + return **this; } constexpr void _M_set(const _Range&, const iterator_t<_Range>& __it) { __glibcxx_assert(!_M_has_value()); - _M_iter = __it; + std::construct_at(std::__addressof(this->_M_payload._M_payload), + in_place, __it); + this->_M_payload._M_engaged = true; } }; @@ -1093,6 +1153,27 @@ namespace views::__adaptor range_difference_t<_Range> _M_offset = -1; public: + _CachedPosition() = default; + + constexpr + _CachedPosition(const _CachedPosition&) = default; + + constexpr + _CachedPosition(_CachedPosition&& __other) noexcept + { *this = std::move(__other); } + + constexpr _CachedPosition& + operator=(const _CachedPosition&) = default; + + constexpr _CachedPosition& + operator=(_CachedPosition&& __other) noexcept + { + // Propagate the cached offset, but invalidate the source. + _M_offset = __other._M_offset; + __other._M_offset = -1; + return *this; + } + constexpr bool _M_has_value() const { return _M_offset >= 0; } @@ -2233,66 +2314,6 @@ 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>> class join_view : public view_interface<join_view<_Vp>> diff --git a/libstdc++-v3/testsuite/std/ranges/adaptors/100479.cc b/libstdc++-v3/testsuite/std/ranges/adaptors/100479.cc new file mode 100644 index 00000000000..37fe15a9f05 --- /dev/null +++ b/libstdc++-v3/testsuite/std/ranges/adaptors/100479.cc @@ -0,0 +1,113 @@ +// Copyright (C) 2021 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// <http://www.gnu.org/licenses/>. + +// { dg-options "-std=gnu++2a" } +// { dg-do run { target c++2a } } + +// PR libstdc++/100479 + +#include <ranges> +#include <testsuite_hooks.h> +#include <testsuite_iterators.h> + +using __gnu_test::test_forward_range; +using __gnu_test::test_random_access_range; + +namespace ranges = std::ranges; +namespace views = std::views; + +void +test01() +{ + // Verify we don't propagate cached iterators when copying/moving an adapted + // forward range that memoizes its begin(). + static int pred_counter; + int x[] = {1,2,3,4,5}; + test_forward_range rx(x); + auto is_odd = [](auto n) { ++pred_counter; return n%2 != 0; }; + + auto v = rx | views::filter(is_odd); + v.begin(); v.begin(); + VERIFY( pred_counter == 1 ); // filter_view caches iterator for begin() + + auto w = v; + v.begin(); v.begin(); + VERIFY( pred_counter == 1 ); // cached iterator not invalidated on copy + w.begin(); w.begin(); + VERIFY( pred_counter == 2 ); // cached iterator not propagated on copy + + auto z = std::move(w); + w.begin(); w.begin(); + VERIFY( pred_counter == 3 ); // cached iterator invalidated on move + z.begin(); z.begin(); + VERIFY( pred_counter == 4 ); // cached iterator not propagated on move +} + +void +test02() +{ + // Verify we invalidate the cached offset when moving an adapted + // random access range that memoizes its begin(). + static int pred_counter; + int x[] = {1,2,3,4,5}; + test_random_access_range rx(x); + auto is_odd = [](auto n) { ++pred_counter; return n%2 != 0; }; + + auto v = rx | views::filter(is_odd); + v.begin(); v.begin(); + VERIFY( pred_counter == 1 ); // filter_view caches iterator for begin() + + auto w = v; + v.begin(); v.begin(); + VERIFY( pred_counter == 1 ); // cached offset not invalidated on copy + w.begin(); w.begin(); + VERIFY( pred_counter == 1 ); // cached offset propagated on copy + + auto z = std::move(w); + w.begin(); w.begin(); + VERIFY( pred_counter == 2 ); // cached offset invalidated on move + z.begin(); z.begin(); + VERIFY( pred_counter == 2 ); // cached offset propagated on move +} + +constexpr bool +test03() +{ + // Propagating cached iterators during copy/move would cause these asserts + // to fail here. + auto v = views::single(1) + | views::split(1) + | views::drop(0) + | views::drop_while([](auto) { return false; }) + | views::filter([](auto) { return true; }); + static_assert(ranges::forward_range<decltype(v)>); + VERIFY( ranges::next(v.begin()) == v.end() ); + auto w = v; + VERIFY( ranges::next(w.begin()) == w.end() ); + auto z = std::move(w); + VERIFY( ranges::next(z.begin()) == z.end() ); + return true; +} + +int +main() +{ + test01(); + test02(); + test03(); + static_assert(test03()); +}
On 18/05/21 00:53 -0400, Patrick Palka via Libstdc++ wrote: >On Mon, 17 May 2021, Tim Song wrote: > >> On Mon, May 17, 2021 at 2:59 PM Patrick Palka <ppalka@redhat.com> wrote: >> > >> > + constexpr _CachedPosition& >> > + operator=(_CachedPosition&& __other) noexcept >> > + { >> > + if (std::__addressof(__other) != this) >> >> I don't think we need this check - self-move-assigning the underlying >> view isn't required to be a no-op, so we should still invalidate. > >Sounds good, so like so: Looks good to me (but then so did the previous one ;-) Please push, as this is an improvement on what's on trunk now. If Tim spots any more problems they can be fixed later. Thanks both of you.
diff --git a/libstdc++-v3/include/std/ranges b/libstdc++-v3/include/std/ranges index 1707aeaebcd..fe6379fb858 100644 --- a/libstdc++-v3/include/std/ranges +++ b/libstdc++-v3/include/std/ranges @@ -1139,6 +1139,67 @@ namespace views::__adaptor 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> : protected _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(); } + + constexpr const _Tp& + operator*() const 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<range _Range> struct _CachedPosition { @@ -1160,27 +1221,25 @@ namespace views::__adaptor template<forward_range _Range> struct _CachedPosition<_Range> + : protected __non_propagating_cache<iterator_t<_Range>> { - private: - iterator_t<_Range> _M_iter{}; - - public: constexpr bool _M_has_value() const - { return _M_iter != iterator_t<_Range>{}; } + { return this->_M_is_engaged(); } constexpr iterator_t<_Range> _M_get(const _Range&) const { __glibcxx_assert(_M_has_value()); - return _M_iter; + return **this; } constexpr void _M_set(const _Range&, const iterator_t<_Range>& __it) { __glibcxx_assert(!_M_has_value()); - _M_iter = __it; + this->_M_payload._M_payload._M_value = __it; + this->_M_payload._M_engaged = true; } }; @@ -2339,66 +2398,6 @@ 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>> class join_view : public view_interface<join_view<_Vp>> diff --git a/libstdc++-v3/testsuite/std/ranges/adaptors/100479.cc b/libstdc++-v3/testsuite/std/ranges/adaptors/100479.cc new file mode 100644 index 00000000000..744d4607512 --- /dev/null +++ b/libstdc++-v3/testsuite/std/ranges/adaptors/100479.cc @@ -0,0 +1,82 @@ +// Copyright (C) 2021 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// <http://www.gnu.org/licenses/>. + +// { dg-options "-std=gnu++2a" } +// { dg-do run { target c++2a } } + +#include <ranges> +#include <testsuite_hooks.h> +#include <testsuite_iterators.h> + +using __gnu_test::test_forward_range; + +namespace ranges = std::ranges; +namespace views = std::views; + +void +test01() +{ + // Verify we don't propagate cached iterators when copying/moving a forward + // range that memoizes its begin(). + static int pred_counter; + int x[] = {1,2,3,4,5}; + test_forward_range rx(x); + auto is_odd = [](auto n) { ++pred_counter; return n%2 != 0; }; + + auto v = rx | views::filter(is_odd); + v.begin(); v.begin(); + VERIFY( pred_counter == 1 ); // filter_view caches iterator for begin() + + auto w = v; + v.begin(); v.begin(); + VERIFY( pred_counter == 1 ); // cached iterator not invalidated during copy + w.begin(); w.begin(); + VERIFY( pred_counter == 2 ); // cached iterator not propagated during copy + + auto z = std::move(w); + w.begin(); w.begin(); + VERIFY( pred_counter == 3 ); // cached iterator invalidated during move + z.begin(); z.begin(); + VERIFY( pred_counter == 4 ); // cached iterator not propagated during move +} + +constexpr bool +test02() +{ + // Propagating cached iterators during copy/move would cause the assertions + // to fail here. + auto v = views::single(1) + | views::split(1) + | views::drop(0) + | views::drop_while([](auto) { return false; }) + | views::filter([](auto) { return true; }); + static_assert(ranges::forward_range<decltype(v)>); + VERIFY( ranges::next(v.begin()) == v.end() ); + auto w = v; + VERIFY( ranges::next(w.begin()) == w.end() ); + auto z = std::move(w); + VERIFY( ranges::next(z.begin()) == z.end() ); + return true; +} + +int +main() +{ + test01(); + test02(); + static_assert(test02()); +}