Re: [PATCH] libstdc++: Fix iterator caching inside range adaptors [PR100479]

[Patrick Palka <ppalka@redhat.com>]

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