[PATCH 1/3] libstdc++: Implement P1994R1 changes to ranges::elements_view

[PATCH 1/3] libstdc++: Implement P1994R1 changes to ranges::elements_view

[Patrick Palka]

The example from the paper doesn't compile without the proposed
resolution for LWG 3406, so we'll add a testcase for this once the
proposed resolution is in.

libstdc++-v3/ChangeLog:

	P1994R1: elements_view needs its own sentinel.
	* include/std/ranges (elements_view::end): Replace these two
	overloads with four new overloads.
	(elements_view::_Iterator::operator==): Remove.
	(elements_view::_Iterator::operator-): Likewise.
	(elements_view::_Sentinel): Define.
---
 libstdc++-v3/include/std/ranges | 74 ++++++++++++++++++++++++++-------
 1 file changed, 60 insertions(+), 14 deletions(-)

diff --git a/libstdc++-v3/include/std/ranges b/libstdc++-v3/include/std/ranges
index 9d22b138082..efa8d2cf9f4 100644
--- a/libstdc++-v3/include/std/ranges
+++ b/libstdc++-v3/include/std/ranges
@@ -3366,12 +3366,20 @@ namespace views
       { return _Iterator<true>(ranges::begin(_M_base)); }
 
       constexpr auto
-      end() requires (!__detail::__simple_view<_Vp>)
-      { return ranges::end(_M_base); }
+      end()
+      { return _Sentinel<false>{ranges::end(_M_base)}; }
 
       constexpr auto
-      end() const requires __detail::__simple_view<_Vp>
-      { return ranges::end(_M_base); }
+      end() requires common_range<_Vp>
+      { return _Iterator<false>{ranges::end(_M_base)}; }
+
+      constexpr auto
+      end() const requires range<const _Vp>
+      { return _Sentinel<true>{ranges::end(_M_base)}; }
+
+      constexpr auto
+      end() const requires common_range<const _Vp>
+      { return _Iterator<true>{ranges::end(_M_base)}; }
 
       constexpr auto
       size() requires sized_range<_Vp>
@@ -3382,6 +3390,9 @@ namespace views
       { return ranges::size(_M_base); }
 
     private:
+      template<bool _Const>
+	struct _Sentinel;
+
       template<bool _Const>
 	struct _Iterator
 	{
@@ -3484,10 +3495,6 @@ namespace views
 	    requires equality_comparable<iterator_t<_Base>>
 	  { return __x._M_current == __y._M_current; }
 
-	  friend constexpr bool
-	  operator==(const _Iterator& __x, const sentinel_t<_Base>& __y)
-	  { return __x._M_current == __y; }
-
 	  friend constexpr bool
 	  operator<(const _Iterator& __x, const _Iterator& __y)
 	    requires random_access_range<_Base>
@@ -3536,15 +3543,54 @@ namespace views
 	    requires random_access_range<_Base>
 	  { return __x._M_current - __y._M_current; }
 
-	  friend constexpr difference_type
-	  operator-(const _Iterator<_Const>& __x, const sentinel_t<_Base>& __y)
+	  friend _Sentinel<_Const>;
+	};
+
+      template<bool _Const>
+	struct _Sentinel
+	{
+	private:
+	  constexpr bool
+	  _M_equal(const _Iterator<_Const>& __x) const
+	  { return __x._M_current == _M_end; }
+
+	  using _Base = __detail::__maybe_const_t<_Const, _Vp>;
+	  sentinel_t<_Base> _M_end = sentinel_t<_Base>();
+
+	public:
+	  _Sentinel() = default;
+
+	  constexpr explicit
+	  _Sentinel(sentinel_t<_Base> __end)
+	    : _M_end(std::move(__end))
+	  { }
+
+	  constexpr
+	  _Sentinel(_Sentinel<!_Const> __other)
+	    requires _Const
+	      && convertible_to<sentinel_t<_Vp>, sentinel_t<_Base>>
+	    : _M_end(std::move(__other._M_end))
+	  { }
+
+	  constexpr sentinel_t<_Base>
+	  base() const
+	  { return _M_end; }
+
+	  friend constexpr bool
+	  operator==(const _Iterator<_Const>& __x, const _Sentinel& __y)
+	  { return __y._M_equal(__x); }
+
+	  friend constexpr range_difference_t<_Base>
+	  operator-(const _Iterator<_Const>& __x, const _Sentinel& __y)
 	    requires sized_sentinel_for<sentinel_t<_Base>, iterator_t<_Base>>
-	  { return __x._M_current - __y; }
+	  { return __x._M_current - __y._M_end; }
 
-	  friend constexpr difference_type
-	  operator-(const sentinel_t<_Base>& __x, const _Iterator<_Const>& __y)
+	  friend constexpr range_difference_t<_Base>
+	  operator-(const _Sentinel& __x, const _Iterator<_Const>& __y)
 	    requires sized_sentinel_for<sentinel_t<_Base>, iterator_t<_Base>>
-	  { return -(__y - __x); }
+	  { return __x._M_end - __y._M_current; }
+
+	  friend _Sentinel<!_Const>;
 	};
 
       _Vp _M_base = _Vp();
-- 
2.28.0.337.ge9b77c84a0

[PATCH 2/3] libstdc++: elements_view's sentinel and iterator not comparable [LWG 3406]

[Patrick Palka]

This implements the proposed resolution for LWG 3406 and adds a testcase
for the example from P1994R1.

libstdc++-v3/ChangeLog:

	LWG 3406
	* include/std/ranges (elements_view::begin): Adjust constraints.
	(elements_view::end): Likewise.
	(elements_view::_Sentinel::operator==): Templatize to take both
	_Iterator<true> and _Iterator<false>.
	(elements_view::_Sentinel::operator-): Likewise.
	* testsuite/std/ranges/adaptors/elements.cc: Add testcase for
	the example from P1994R1.
	* testsuite/std/range/adaptors/lwg3406.cc: New test.
---
 libstdc++-v3/include/std/ranges               | 39 ++++++++-------
 .../testsuite/std/ranges/adaptors/elements.cc | 22 +++++++++
 .../testsuite/std/ranges/adaptors/lwg3406.cc  | 48 +++++++++++++++++++
 3 files changed, 93 insertions(+), 16 deletions(-)
 create mode 100644 libstdc++-v3/testsuite/std/ranges/adaptors/lwg3406.cc

diff --git a/libstdc++-v3/include/std/ranges b/libstdc++-v3/include/std/ranges
index efa8d2cf9f4..42028354b81 100644
--- a/libstdc++-v3/include/std/ranges
+++ b/libstdc++-v3/include/std/ranges
@@ -3362,15 +3362,15 @@ namespace views
       { return _Iterator<false>(ranges::begin(_M_base)); }
 
       constexpr auto
-      begin() const requires __detail::__simple_view<_Vp>
+      begin() const requires range<const _Vp>
       { return _Iterator<true>(ranges::begin(_M_base)); }
 
       constexpr auto
-      end()
+      end() requires (!__detail::__simple_view<_Vp> && !common_range<_Vp>)
       { return _Sentinel<false>{ranges::end(_M_base)}; }
 
       constexpr auto
-      end() requires common_range<_Vp>
+      end() requires (!__detail::__simple_view<_Vp> && common_range<_Vp>)
       { return _Iterator<false>{ranges::end(_M_base)}; }
 
       constexpr auto
@@ -3576,19 +3576,26 @@ namespace views
 	  base() const
 	  { return _M_end; }
 
-	  friend constexpr bool
-	  operator==(const _Iterator<_Const>& __x, const _Sentinel& __y)
-	  { return __y._M_equal(__x); }
-
-	  friend constexpr range_difference_t<_Base>
-	  operator-(const _Iterator<_Const>& __x, const _Sentinel& __y)
-	    requires sized_sentinel_for<sentinel_t<_Base>, iterator_t<_Base>>
-	  { return __x._M_current - __y._M_end; }
-
-	  friend constexpr range_difference_t<_Base>
-	  operator-(const _Sentinel& __x, const _Iterator<_Const>& __y)
-	    requires sized_sentinel_for<sentinel_t<_Base>, iterator_t<_Base>>
-	  { return __x._M_end - __y._M_current; }
+	  template<bool _Const2>
+	    requires sentinel_for<sentinel_t<_Base>,
+		       iterator_t<__detail::__maybe_const_t<_Const2, _Vp>>>
+	    friend constexpr bool
+	    operator==(const _Iterator<_Const2>& __x, const _Sentinel& __y)
+	    { return __y._M_equal(__x); }
+
+	  template<bool _Const2,
+		   typename _Base2 = __detail::__maybe_const_t<_Const2, _Vp>>
+	    requires sized_sentinel_for<sentinel_t<_Base>, iterator_t<_Base2>>
+	    friend constexpr range_difference_t<_Base2>
+	    operator-(const _Iterator<_Const2>& __x, const _Sentinel& __y)
+	    { return __x._M_current - __y._M_end; }
+
+	  template<bool _Const2,
+		   typename _Base2 = __detail::__maybe_const_t<_Const2, _Vp>>
+	    requires sized_sentinel_for<sentinel_t<_Base>, iterator_t<_Base2>>
+	    friend constexpr range_difference_t<_Base>
+	    operator-(const _Sentinel& __x, const _Iterator<_Const2>& __y)
+	    { return __x._M_end - __y._M_current; }
 
 	  friend _Sentinel<!_Const>;
 	};
diff --git a/libstdc++-v3/testsuite/std/ranges/adaptors/elements.cc b/libstdc++-v3/testsuite/std/ranges/adaptors/elements.cc
index d846c4cf33e..af5c2d43bb6 100644
--- a/libstdc++-v3/testsuite/std/ranges/adaptors/elements.cc
+++ b/libstdc++-v3/testsuite/std/ranges/adaptors/elements.cc
@@ -45,8 +45,30 @@ test01()
   VERIFY( ranges::equal(v1, x | views::values) );
 }
 
+struct S
+{
+  friend bool
+  operator==(std::input_iterator auto const& i, S)
+  { return std::get<1>(*i) == 0; }
+};
+
+void
+test02()
+{
+  // This verifies that P1994R1 (and LWG3406) is implemented.
+  std::pair<std::pair<char, int>, long> x[]
+    = {{{1,2},3l}, {{1,0},2l}, {{1,2},0l}};
+  ranges::subrange r{ranges::begin(x), S{}};
+
+  auto v = r | views::keys;
+  VERIFY( ranges::equal(v, (std::pair<char, int>[]){{1,2},{1,0}}) );
+  ranges::subrange v2 = {ranges::begin(v), S{}};
+  VERIFY( ranges::equal(v2, (std::pair<char, int>[]){{1,2}}) );
+}
+
 int
 main()
 {
   test01();
+  test02();
 }
diff --git a/libstdc++-v3/testsuite/std/ranges/adaptors/lwg3406.cc b/libstdc++-v3/testsuite/std/ranges/adaptors/lwg3406.cc
new file mode 100644
index 00000000000..d36db22aad5
--- /dev/null
+++ b/libstdc++-v3/testsuite/std/ranges/adaptors/lwg3406.cc
@@ -0,0 +1,48 @@
+// Copyright (C) 2020 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 compile { target c++2a } }
+
+#include <ranges>
+#include <testsuite_hooks.h>
+
+namespace ranges = std::ranges;
+namespace views = std::views;
+
+void
+test01()
+{
+  std::tuple<int, int> x[] = {{0,0}};
+  auto v = x | views::elements<0>;
+  bool b = ranges::cbegin(v) == ranges::end(v);
+}
+
+void
+test02()
+{
+  std::tuple x = {0, 1};
+  auto v = views::single(x) | views::elements<0>;
+  auto i = ranges::cbegin(v);
+}
+
+int
+main()
+{
+  test01();
+  test02();
+}
-- 
2.28.0.337.ge9b77c84a0

[PATCH 3/3] libstdc++: Implement remaining piece of LWG 3448

[Patrick Palka]

Almost all of the proposed resolution for LWG 3448 is already
implemented; the only part left is to adjust the return type of
transform_view::sentinel::operator-.

libstdc++-v3/ChangeLog:

	LWG 3448
	PR libstdc++/95322
	* include/std/ranges (transform_view::__distance_from): Give
	this a deduced return type.
	(transform_view::sentinel::operator-): Adjust the return type so
	that it's based on the constness of the iterator rather than
	that of the sentinel.
	* testsuite/std/ranges/adaptors/95322.cc: Refer to LWG 3488.
---
 libstdc++-v3/include/std/ranges                | 18 +++++++++---------
 .../testsuite/std/ranges/adaptors/95322.cc     |  2 +-
 2 files changed, 10 insertions(+), 10 deletions(-)

diff --git a/libstdc++-v3/include/std/ranges b/libstdc++-v3/include/std/ranges
index 42028354b81..2d0017f1750 100644
--- a/libstdc++-v3/include/std/ranges
+++ b/libstdc++-v3/include/std/ranges
@@ -1865,7 +1865,7 @@ namespace views
 	  using _Base = __detail::__maybe_const_t<_Const, _Vp>;
 
 	  template<bool _Const2>
-	    constexpr range_difference_t<_Base>
+	    constexpr auto
 	    __distance_from(const _Iterator<_Const2>& __i) const
 	    { return _M_end - __i._M_current; }
 
@@ -1902,17 +1902,17 @@ namespace views
 	    operator==(const _Iterator<_Const2>& __x, const _Sentinel& __y)
 	    { return __y.__equal(__x); }
 
-	  template<bool _Const2>
-	    requires sized_sentinel_for<sentinel_t<_Base>,
-		       iterator_t<__detail::__maybe_const_t<_Const2, _Vp>>>
-	    friend constexpr range_difference_t<_Base>
+	  template<bool _Const2,
+		   typename _Base2 = __detail::__maybe_const_t<_Const2, _Vp>>
+	    requires sized_sentinel_for<sentinel_t<_Base>, iterator_t<_Base2>>
+	    friend constexpr range_difference_t<_Base2>
 	    operator-(const _Iterator<_Const2>& __x, const _Sentinel& __y)
 	    { return -__y.__distance_from(__x); }
 
-	  template<bool _Const2>
-	    requires sized_sentinel_for<sentinel_t<_Base>,
-		       iterator_t<__detail::__maybe_const_t<_Const2, _Vp>>>
-	    friend constexpr range_difference_t<_Base>
+	  template<bool _Const2,
+		   typename _Base2 = __detail::__maybe_const_t<_Const2, _Vp>>
+	    requires sized_sentinel_for<sentinel_t<_Base>, iterator_t<_Base2>>
+	    friend constexpr range_difference_t<_Base2>
 	    operator-(const _Sentinel& __y, const _Iterator<_Const2>& __x)
 	    { return __y.__distance_from(__x); }
 
diff --git a/libstdc++-v3/testsuite/std/ranges/adaptors/95322.cc b/libstdc++-v3/testsuite/std/ranges/adaptors/95322.cc
index 9279d5520a8..67bc7d33917 100644
--- a/libstdc++-v3/testsuite/std/ranges/adaptors/95322.cc
+++ b/libstdc++-v3/testsuite/std/ranges/adaptors/95322.cc
@@ -26,7 +26,7 @@ using __gnu_test::test_forward_range;
 void
 test01()
 {
-  // PR libstdc++/95322
+  // PR libstdc++/95322 and LWG 3488
   int a[2]{1, 2};
   test_forward_range<int> v{a};
   auto view1 = v | std::views::take(2);
-- 
2.28.0.337.ge9b77c84a0

Re: [PATCH 1/3] libstdc++: Implement P1994R1 changes to ranges::elements_view

[Jonathan Wakely]

On 26/08/20 16:44 -0400, Patrick Palka via Libstdc++ wrote:
>The example from the paper doesn't compile without the proposed
>resolution for LWG 3406, so we'll add a testcase for this once the
>proposed resolution is in.
>
>libstdc++-v3/ChangeLog:
>
>	P1994R1: elements_view needs its own sentinel.
>	* include/std/ranges (elements_view::end): Replace these two
>	overloads with four new overloads.
>	(elements_view::_Iterator::operator==): Remove.
>	(elements_view::_Iterator::operator-): Likewise.
>	(elements_view::_Sentinel): Define.

OK, thanks.

Re: [PATCH 2/3] libstdc++: elements_view's sentinel and iterator not comparable [LWG 3406]

[Jonathan Wakely]

On 26/08/20 16:44 -0400, Patrick Palka via Libstdc++ wrote:
>This implements the proposed resolution for LWG 3406 and adds a testcase
>for the example from P1994R1.
>
>libstdc++-v3/ChangeLog:
>
>	LWG 3406
>	* include/std/ranges (elements_view::begin): Adjust constraints.
>	(elements_view::end): Likewise.
>	(elements_view::_Sentinel::operator==): Templatize to take both
>	_Iterator<true> and _Iterator<false>.
>	(elements_view::_Sentinel::operator-): Likewise.
>	* testsuite/std/ranges/adaptors/elements.cc: Add testcase for
>	the example from P1994R1.
>	* testsuite/std/range/adaptors/lwg3406.cc: New test.

OK, thanks.

Re: [PATCH 3/3] libstdc++: Implement remaining piece of LWG 3448

[Jonathan Wakely]

On 26/08/20 16:44 -0400, Patrick Palka via Libstdc++ wrote:
>Almost all of the proposed resolution for LWG 3448 is already
>implemented; the only part left is to adjust the return type of
>transform_view::sentinel::operator-.
>
>libstdc++-v3/ChangeLog:
>
>	LWG 3448
>	PR libstdc++/95322
>	* include/std/ranges (transform_view::__distance_from): Give
>	this a deduced return type.
>	(transform_view::sentinel::operator-): Adjust the return type so
>	that it's based on the constness of the iterator rather than
>	that of the sentinel.
>	* testsuite/std/ranges/adaptors/95322.cc: Refer to LWG 3488.

Also OK, thanks for fixing these.