* [PATCH] libstdc++: Fix iterator caching inside range adaptors [PR100479]
@ 2021-05-17 15:43 Patrick Palka
2021-05-17 16:51 ` Jonathan Wakely
2021-05-17 18:39 ` Tim Song
0 siblings, 2 replies; 7+ messages in thread
From: Patrick Palka @ 2021-05-17 15:43 UTC (permalink / raw)
To: gcc-patches; +Cc: libstdc++, Patrick Palka
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? Shall we
also backport this?
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.
* testsuite/std/ranges/adaptors/100479.cc: New test.
---
libstdc++-v3/include/std/ranges | 133 +++++++++---------
.../testsuite/std/ranges/adaptors/100479.cc | 82 +++++++++++
2 files changed, 148 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..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());
+}
--
2.31.1.621.g97eea85a0a
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [PATCH] libstdc++: Fix iterator caching inside range adaptors [PR100479]
2021-05-17 15:43 [PATCH] libstdc++: Fix iterator caching inside range adaptors [PR100479] Patrick Palka
@ 2021-05-17 16:51 ` Jonathan Wakely
2021-05-17 18:39 ` Tim Song
1 sibling, 0 replies; 7+ messages in thread
From: Jonathan Wakely @ 2021-05-17 16:51 UTC (permalink / raw)
To: Patrick Palka; +Cc: gcc-patches, libstdc++
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.
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [PATCH] libstdc++: Fix iterator caching inside range adaptors [PR100479]
2021-05-17 15:43 [PATCH] libstdc++: Fix iterator caching inside range adaptors [PR100479] Patrick Palka
2021-05-17 16:51 ` Jonathan Wakely
@ 2021-05-17 18:39 ` Tim Song
2021-05-17 19:59 ` Patrick Palka
1 sibling, 1 reply; 7+ messages in thread
From: Tim Song @ 2021-05-17 18:39 UTC (permalink / raw)
To: Patrick Palka; +Cc: gcc-patches, libstdc++
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.
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [PATCH] libstdc++: Fix iterator caching inside range adaptors [PR100479]
2021-05-17 18:39 ` Tim Song
@ 2021-05-17 19:59 ` Patrick Palka
2021-05-17 22:28 ` Tim Song
0 siblings, 1 reply; 7+ messages in thread
From: Patrick Palka @ 2021-05-17 19:59 UTC (permalink / raw)
To: Tim Song; +Cc: Patrick Palka, gcc-patches, libstdc++
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());
+}
--
2.31.1.621.g97eea85a0a
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [PATCH] libstdc++: Fix iterator caching inside range adaptors [PR100479]
2021-05-17 19:59 ` Patrick Palka
@ 2021-05-17 22:28 ` Tim Song
2021-05-18 4:53 ` Patrick Palka
0 siblings, 1 reply; 7+ messages in thread
From: Tim Song @ 2021-05-17 22:28 UTC (permalink / raw)
To: Patrick Palka; +Cc: gcc-patches, libstdc++
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;
> + }
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [PATCH] libstdc++: Fix iterator caching inside range adaptors [PR100479]
2021-05-17 22:28 ` Tim Song
@ 2021-05-18 4:53 ` Patrick Palka
2021-05-24 18:59 ` Jonathan Wakely
0 siblings, 1 reply; 7+ messages in thread
From: Patrick Palka @ 2021-05-18 4:53 UTC (permalink / raw)
To: Tim Song; +Cc: Patrick Palka, gcc-patches, libstdc++
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());
+}
--
2.31.1.621.g97eea85a0a
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [PATCH] libstdc++: Fix iterator caching inside range adaptors [PR100479]
2021-05-18 4:53 ` Patrick Palka
@ 2021-05-24 18:59 ` Jonathan Wakely
0 siblings, 0 replies; 7+ messages in thread
From: Jonathan Wakely @ 2021-05-24 18:59 UTC (permalink / raw)
To: Patrick Palka; +Cc: Tim Song, libstdc++, gcc-patches
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.
^ permalink raw reply [flat|nested] 7+ messages in thread
end of thread, other threads:[~2021-05-24 18:59 UTC | newest]
Thread overview: 7+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2021-05-17 15:43 [PATCH] libstdc++: Fix iterator caching inside range adaptors [PR100479] Patrick Palka
2021-05-17 16:51 ` Jonathan Wakely
2021-05-17 18:39 ` Tim Song
2021-05-17 19:59 ` Patrick Palka
2021-05-17 22:28 ` Tim Song
2021-05-18 4:53 ` Patrick Palka
2021-05-24 18:59 ` Jonathan Wakely
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).