[PATCH 1/3] libstdc++: Fix elements_view::operator* and operator[] [LWG 3502]

[PATCH 1/3] libstdc++: Fix elements_view::operator* and operator[] [LWG 3502]

[Patrick Palka]

While we're modifying elements_view, this also implements the one-line
resolution of LWG 3492.

libstdc++-v3/ChangeLog:

	* include/std/ranges (__detail::__returnable_element): New
	concept.
	(elements_view): Use this concept in its constraints.  Add
	missing private access specifier.
	(elements_view::_S_get_element): Define as per LWG 3502.
	(elements_view::operator*, elements_view::operator[]): Use
	_S_get_element.
	(elements_view::operator++): Remove unnecessary constraint
	as per LWG 3492.
	* testsuite/std/ranges/adaptors/elements.cc (test05): New test.
---
 libstdc++-v3/include/std/ranges               | 26 ++++++++++++++++---
 .../testsuite/std/ranges/adaptors/elements.cc | 16 ++++++++++++
 2 files changed, 38 insertions(+), 4 deletions(-)

diff --git a/libstdc++-v3/include/std/ranges b/libstdc++-v3/include/std/ranges
index 978578197dc..cfcbcaba065 100644
--- a/libstdc++-v3/include/std/ranges
+++ b/libstdc++-v3/include/std/ranges
@@ -3234,6 +3234,10 @@ namespace views::__adaptor
 	{ std::get<_Nm>(__t) }
 	  -> convertible_to<const tuple_element_t<_Nm, _Tp>&>;
       };
+
+    template<typename _Tp, size_t _Nm>
+      concept __returnable_element
+	= is_reference_v<_Tp> || move_constructible<tuple_element_t<_Nm, _Tp>>;
   }
 
   template<input_range _Vp, size_t _Nm>
@@ -3241,6 +3245,7 @@ namespace views::__adaptor
       && __detail::__has_tuple_element<range_value_t<_Vp>, _Nm>
       && __detail::__has_tuple_element<remove_reference_t<range_reference_t<_Vp>>,
 				       _Nm>
+      && __detail::__returnable_element<range_reference_t<_Vp>, _Nm>
     class elements_view : public view_interface<elements_view<_Vp, _Nm>>
     {
     public:
@@ -3298,10 +3303,23 @@ namespace views::__adaptor
       template<bool _Const>
 	struct _Iterator
 	{
+	private:
 	  using _Base = __detail::__maybe_const_t<_Const, _Vp>;
 
 	  iterator_t<_Base> _M_current = iterator_t<_Base>();
 
+	  static constexpr decltype(auto)
+	  _S_get_element(const iterator_t<_Base>& __i)
+	  {
+	    if constexpr (is_reference_v<range_reference_t<_Base>>)
+	      return std::get<_Nm>(*__i);
+	    else
+	      {
+		using _Et = remove_cv_t<tuple_element_t<_Nm, range_reference_t<_Base>>>;
+		return static_cast<_Et>(std::get<_Nm>(*__i));
+	      }
+	  }
+
 	  friend _Iterator<!_Const>;
 
 	public:
@@ -3334,8 +3352,8 @@ namespace views::__adaptor
 	  { return std::move(_M_current); }
 
 	  constexpr decltype(auto)
-	    operator*() const
-	  { return std::get<_Nm>(*_M_current); }
+	  operator*() const
+	  { return _S_get_element(_M_current); }
 
 	  constexpr _Iterator&
 	  operator++()
@@ -3345,7 +3363,7 @@ namespace views::__adaptor
 	  }
 
 	  constexpr void
-	  operator++(int) requires (!forward_range<_Base>)
+	  operator++(int)
 	  { ++_M_current; }
 
 	  constexpr _Iterator
@@ -3390,7 +3408,7 @@ namespace views::__adaptor
 	  constexpr decltype(auto)
 	  operator[](difference_type __n) const
 	    requires random_access_range<_Base>
-	  { return std::get<_Nm>(*(_M_current + __n)); }
+	  { return _S_get_element(_M_current + __n); }
 
 	  friend constexpr bool
 	  operator==(const _Iterator& __x, const _Iterator& __y)
diff --git a/libstdc++-v3/testsuite/std/ranges/adaptors/elements.cc b/libstdc++-v3/testsuite/std/ranges/adaptors/elements.cc
index b0d122f8db5..134afd6a873 100644
--- a/libstdc++-v3/testsuite/std/ranges/adaptors/elements.cc
+++ b/libstdc++-v3/testsuite/std/ranges/adaptors/elements.cc
@@ -100,6 +100,21 @@ test04()
   static_assert(!requires { 0 | elements; });
 }
 
+void
+test05()
+{
+  // LWG 3502
+  std::vector<int> vec = {42};
+  auto r1 = vec
+    | views::transform([](auto c) { return std::make_tuple(c, c); })
+    | views::keys;
+  VERIFY( ranges::equal(r1, (int[]){42}) );
+
+  std::tuple<int, int> a[] = {{1,2},{3,4}};
+  auto r2 = a | views::keys;
+  VERIFY( r2[0] == 1 && r2[1] == 3 );
+}
+
 int
 main()
 {
@@ -107,4 +122,5 @@ main()
   test02();
   test03();
   test04();
+  test05();
 }
-- 
2.31.1.133.g84d06cdc06

[PATCH 2/3] libstdc++: Simplify copy-pasted algorithms in <ranges>

[Patrick Palka]

The <ranges> header currently copies some simple algorithms from
<bits/ranges_algo.h>, which was originally done in order to avoid a
circular dependency with the header.  This is no longer an issue since
the latter header now includes <bits/ranges_util.h> instead of all of
<ranges>.

This means we could now just include <bits/ranges_algo.h> and remove the
copied algorithms, but that would double the size of <ranges>.  And we
can't use the corresponding STL-style algorithms here because they
assume input iterators are copyable.  So this patch instead simplifies
these copied algorithms, removing their constraints and unused
parameters, and keeps them around.  In a subsequent patch we're going to
copy ranges::find into <ranges> as well.

libstdc++-v3/ChangeLog:

	* include/std/ranges (__detail::find_if): Simplify.
	(__detail::find_if_not): Likewise.
	(__detail::min): Remove.
	(__detail::mismatch): Simplify.
	(take_view::size): Use std::min instead of __detail::min.
---
 libstdc++-v3/include/std/ranges | 59 ++++++++++-----------------------
 1 file changed, 17 insertions(+), 42 deletions(-)

diff --git a/libstdc++-v3/include/std/ranges b/libstdc++-v3/include/std/ranges
index cfcbcaba065..9077271e4e6 100644
--- a/libstdc++-v3/include/std/ranges
+++ b/libstdc++-v3/include/std/ranges
@@ -978,65 +978,40 @@ namespace views::__adaptor
       using all_t = decltype(all(std::declval<_Range>()));
   } // namespace views
 
-  // XXX: the following algos are copied from ranges_algo.h to avoid a circular
-  // dependency with that header.
+  // The following simple algos are transcribed from ranges_algo.h to avoid
+  // having to include that entire header.
   namespace __detail
   {
-    template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
-	     typename _Proj = identity,
-	     indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
+    template<typename _Iter, typename _Sent, typename _Pred>
       constexpr _Iter
-      find_if(_Iter __first, _Sent __last, _Pred __pred, _Proj __proj = {})
+      find_if(_Iter __first, _Sent __last, _Pred __pred)
       {
 	while (__first != __last
-	    && !(bool)std::__invoke(__pred, std::__invoke(__proj, *__first)))
+	       && !(bool)std::__invoke(__pred, *__first))
 	  ++__first;
 	return __first;
       }
 
-    template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
-	     typename _Proj = identity,
-	     indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
+    template<typename _Iter, typename _Sent, typename _Pred>
       constexpr _Iter
-      find_if_not(_Iter __first, _Sent __last, _Pred __pred, _Proj __proj = {})
+      find_if_not(_Iter __first, _Sent __last, _Pred __pred)
       {
 	while (__first != __last
-	    && (bool)std::__invoke(__pred, std::__invoke(__proj, *__first)))
+	       && (bool)std::__invoke(__pred, *__first))
 	  ++__first;
 	return __first;
       }
 
-    template<typename _Tp, typename _Proj = identity,
-	     indirect_strict_weak_order<projected<const _Tp*, _Proj>>
-	       _Comp = ranges::less>
-      constexpr const _Tp&
-      min(const _Tp& __a, const _Tp& __b, _Comp __comp = {}, _Proj __proj = {})
-      {
-	if (std::__invoke(std::move(__comp),
-			  std::__invoke(__proj, __b),
-			  std::__invoke(__proj, __a)))
-	  return __b;
-	else
-	  return __a;
-      }
-
-    template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
-	     input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
-	     typename _Pred = ranges::equal_to,
-	     typename _Proj1 = identity, typename _Proj2 = identity>
-      requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2>
+    template<typename _Iter1, typename _Sent1, typename _Iter2, typename _Sent2>
       constexpr pair<_Iter1, _Iter2>
-      mismatch(_Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Sent2 __last2,
-	       _Pred __pred = {}, _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
+      mismatch(_Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Sent2 __last2)
       {
 	while (__first1 != __last1 && __first2 != __last2
-	       && (bool)std::__invoke(__pred,
-				      std::__invoke(__proj1, *__first1),
-				      std::__invoke(__proj2, *__first2)))
-	{
-	  ++__first1;
-	  ++__first2;
-	}
+	       && (bool)ranges::equal_to{}(*__first1, *__first2))
+	  {
+	    ++__first1;
+	    ++__first2;
+	  }
 	return { std::move(__first1), std::move(__first2) };
       }
   } // namespace __detail
@@ -1847,14 +1822,14 @@ namespace views::__adaptor
       size() requires sized_range<_Vp>
       {
 	auto __n = ranges::size(_M_base);
-	return __detail::min(__n, static_cast<decltype(__n)>(_M_count));
+	return std::min(__n, static_cast<decltype(__n)>(_M_count));
       }
 
       constexpr auto
       size() const requires sized_range<const _Vp>
       {
 	auto __n = ranges::size(_M_base);
-	return __detail::min(__n, static_cast<decltype(__n)>(_M_count));
+	return std::min(__n, static_cast<decltype(__n)>(_M_count));
       }
     };
 
-- 
2.31.1.133.g84d06cdc06

[PATCH 3/3] libstdc++: Fix split_view::_OuterIter::operator++ [LWG 3505]

[Patrick Palka]

libstdc++-v3/ChangeLog:

	* include/std/ranges (__detail::find): Define.
	(split_view::_OuterIter::operator++): Apply proposed resolution
	of LWG 3505.
	* testsuite/std/ranges/adaptors/split.cc (test10): New test.
---
 libstdc++-v3/include/std/ranges               | 28 ++++++++++++++++---
 .../testsuite/std/ranges/adaptors/split.cc    | 12 ++++++++
 2 files changed, 36 insertions(+), 4 deletions(-)

diff --git a/libstdc++-v3/include/std/ranges b/libstdc++-v3/include/std/ranges
index 9077271e4e6..baec8c0efef 100644
--- a/libstdc++-v3/include/std/ranges
+++ b/libstdc++-v3/include/std/ranges
@@ -982,6 +982,16 @@ namespace views::__adaptor
   // having to include that entire header.
   namespace __detail
   {
+    template<typename _Iter, typename _Sent, typename _Tp>
+      constexpr _Iter
+      find(_Iter __first, _Sent __last, const _Tp& __value)
+      {
+	while (__first != __last
+	       && !(bool)(*__first == __value))
+	  ++__first;
+	return __first;
+      }
+
     template<typename _Iter, typename _Sent, typename _Pred>
       constexpr _Iter
       find_if(_Iter __first, _Sent __last, _Pred __pred)
@@ -2656,21 +2666,31 @@ namespace views::__adaptor
 	  constexpr _OuterIter&
 	  operator++()
 	  {
+	    // _GLIBCXX_RESOLVE_LIB_DEFECTS
+	    // 3505. split_view::outer-iterator::operator++ misspecified
 	    const auto __end = ranges::end(_M_parent->_M_base);
 	    if (__current() == __end)
 	      return *this;
 	    const auto [__pbegin, __pend] = subrange{_M_parent->_M_pattern};
 	    if (__pbegin == __pend)
 	      ++__current();
+	    else if constexpr (__detail::__tiny_range<_Pattern>)
+	      {
+		__current() = __detail::find(std::move(__current()), __end,
+					     *__pbegin);
+		if (__current() != __end)
+		  ++__current();
+	      }
 	    else
 	      do
 		{
 		  auto [__b, __p]
-		    = __detail::mismatch(std::move(__current()), __end,
-					 __pbegin, __pend);
-		  __current() = std::move(__b);
+		    = __detail::mismatch(__current(), __end, __pbegin, __pend);
 		  if (__p == __pend)
-		    break;
+		    {
+		      __current() = __b;
+		      break;
+		    }
 		} while (++__current() != __end);
 	    return *this;
 	  }
diff --git a/libstdc++-v3/testsuite/std/ranges/adaptors/split.cc b/libstdc++-v3/testsuite/std/ranges/adaptors/split.cc
index b9fb3728708..9d2cfa8632a 100644
--- a/libstdc++-v3/testsuite/std/ranges/adaptors/split.cc
+++ b/libstdc++-v3/testsuite/std/ranges/adaptors/split.cc
@@ -182,6 +182,17 @@ test09()
   static_assert(requires { adapt2(s); });
 }
 
+void
+test10()
+{
+  // LWG 3505
+  auto to_string = [] (auto r) {
+    return std::string(r.begin(), ranges::next(r.begin(), r.end()));
+  };
+  auto v = "xxyx"sv | views::split("xy"sv) | views::transform(to_string);
+  VERIFY( ranges::equal(v, (std::string_view[]){"x", "x"}) );
+}
+
 int
 main()
 {
@@ -194,4 +205,5 @@ main()
   test07();
   test08();
   test09();
+  test10();
 }
-- 
2.31.1.133.g84d06cdc06

Re: [PATCH 2/3] libstdc++: Simplify copy-pasted algorithms in <ranges>

[Patrick Palka]

On Mon, 29 Mar 2021, Patrick Palka wrote:

> The <ranges> header currently copies some simple algorithms from
> <bits/ranges_algo.h>, which was originally done in order to avoid a
> circular dependency with the header.  This is no longer an issue since
> the latter header now includes <bits/ranges_util.h> instead of all of
> <ranges>.
> 
> This means we could now just include <bits/ranges_algo.h> and remove the
> copied algorithms, but that would double the size of <ranges>.

Whoops, more like increase the size of <ranges> by ~10% (33k SLOC -> 37k).

> And we
> can't use the corresponding STL-style algorithms here because they
> assume input iterators are copyable.  So this patch instead simplifies
> these copied algorithms, removing their constraints and unused
> parameters, and keeps them around.  In a subsequent patch we're going to
> copy ranges::find into <ranges> as well.
> 
> libstdc++-v3/ChangeLog:
> 
> 	* include/std/ranges (__detail::find_if): Simplify.
> 	(__detail::find_if_not): Likewise.
> 	(__detail::min): Remove.
> 	(__detail::mismatch): Simplify.
> 	(take_view::size): Use std::min instead of __detail::min.
> ---
>  libstdc++-v3/include/std/ranges | 59 ++++++++++-----------------------
>  1 file changed, 17 insertions(+), 42 deletions(-)
> 
> diff --git a/libstdc++-v3/include/std/ranges b/libstdc++-v3/include/std/ranges
> index cfcbcaba065..9077271e4e6 100644
> --- a/libstdc++-v3/include/std/ranges
> +++ b/libstdc++-v3/include/std/ranges
> @@ -978,65 +978,40 @@ namespace views::__adaptor
>        using all_t = decltype(all(std::declval<_Range>()));
>    } // namespace views
>  
> -  // XXX: the following algos are copied from ranges_algo.h to avoid a circular
> -  // dependency with that header.
> +  // The following simple algos are transcribed from ranges_algo.h to avoid
> +  // having to include that entire header.
>    namespace __detail
>    {
> -    template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
> -	     typename _Proj = identity,
> -	     indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
> +    template<typename _Iter, typename _Sent, typename _Pred>
>        constexpr _Iter
> -      find_if(_Iter __first, _Sent __last, _Pred __pred, _Proj __proj = {})
> +      find_if(_Iter __first, _Sent __last, _Pred __pred)
>        {
>  	while (__first != __last
> -	    && !(bool)std::__invoke(__pred, std::__invoke(__proj, *__first)))
> +	       && !(bool)std::__invoke(__pred, *__first))
>  	  ++__first;
>  	return __first;
>        }
>  
> -    template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
> -	     typename _Proj = identity,
> -	     indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
> +    template<typename _Iter, typename _Sent, typename _Pred>
>        constexpr _Iter
> -      find_if_not(_Iter __first, _Sent __last, _Pred __pred, _Proj __proj = {})
> +      find_if_not(_Iter __first, _Sent __last, _Pred __pred)
>        {
>  	while (__first != __last
> -	    && (bool)std::__invoke(__pred, std::__invoke(__proj, *__first)))
> +	       && (bool)std::__invoke(__pred, *__first))
>  	  ++__first;
>  	return __first;
>        }
>  
> -    template<typename _Tp, typename _Proj = identity,
> -	     indirect_strict_weak_order<projected<const _Tp*, _Proj>>
> -	       _Comp = ranges::less>
> -      constexpr const _Tp&
> -      min(const _Tp& __a, const _Tp& __b, _Comp __comp = {}, _Proj __proj = {})
> -      {
> -	if (std::__invoke(std::move(__comp),
> -			  std::__invoke(__proj, __b),
> -			  std::__invoke(__proj, __a)))
> -	  return __b;
> -	else
> -	  return __a;
> -      }
> -
> -    template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
> -	     input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
> -	     typename _Pred = ranges::equal_to,
> -	     typename _Proj1 = identity, typename _Proj2 = identity>
> -      requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2>
> +    template<typename _Iter1, typename _Sent1, typename _Iter2, typename _Sent2>
>        constexpr pair<_Iter1, _Iter2>
> -      mismatch(_Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Sent2 __last2,
> -	       _Pred __pred = {}, _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
> +      mismatch(_Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Sent2 __last2)
>        {
>  	while (__first1 != __last1 && __first2 != __last2
> -	       && (bool)std::__invoke(__pred,
> -				      std::__invoke(__proj1, *__first1),
> -				      std::__invoke(__proj2, *__first2)))
> -	{
> -	  ++__first1;
> -	  ++__first2;
> -	}
> +	       && (bool)ranges::equal_to{}(*__first1, *__first2))
> +	  {
> +	    ++__first1;
> +	    ++__first2;
> +	  }
>  	return { std::move(__first1), std::move(__first2) };
>        }
>    } // namespace __detail
> @@ -1847,14 +1822,14 @@ namespace views::__adaptor
>        size() requires sized_range<_Vp>
>        {
>  	auto __n = ranges::size(_M_base);
> -	return __detail::min(__n, static_cast<decltype(__n)>(_M_count));
> +	return std::min(__n, static_cast<decltype(__n)>(_M_count));
>        }
>  
>        constexpr auto
>        size() const requires sized_range<const _Vp>
>        {
>  	auto __n = ranges::size(_M_base);
> -	return __detail::min(__n, static_cast<decltype(__n)>(_M_count));
> +	return std::min(__n, static_cast<decltype(__n)>(_M_count));
>        }
>      };
>  
> -- 
> 2.31.1.133.g84d06cdc06
> 
> 

Re: [PATCH 1/3] libstdc++: Fix elements_view::operator* and operator[] [LWG 3502]

[Jonathan Wakely]

On 29/03/21 14:49 -0400, Patrick Palka via Libstdc++ wrote:
>While we're modifying elements_view, this also implements the one-line
>resolution of LWG 3492.
>
>libstdc++-v3/ChangeLog:
>
>	* include/std/ranges (__detail::__returnable_element): New
>	concept.
>	(elements_view): Use this concept in its constraints.  Add
>	missing private access specifier.
>	(elements_view::_S_get_element): Define as per LWG 3502.
>	(elements_view::operator*, elements_view::operator[]): Use
>	_S_get_element.
>	(elements_view::operator++): Remove unnecessary constraint
>	as per LWG 3492.
>	* testsuite/std/ranges/adaptors/elements.cc (test05): New test.

OK, thanks.

Re: [PATCH 3/3] libstdc++: Fix split_view::_OuterIter::operator++ [LWG 3505]

[Jonathan Wakely]

On 29/03/21 14:49 -0400, Patrick Palka via Libstdc++ wrote:
>libstdc++-v3/ChangeLog:
>
>	* include/std/ranges (__detail::find): Define.
>	(split_view::_OuterIter::operator++): Apply proposed resolution
>	of LWG 3505.
>	* testsuite/std/ranges/adaptors/split.cc (test10): New test.

OK, thanks.

Re: [PATCH 2/3] libstdc++: Simplify copy-pasted algorithms in <ranges>

[Jonathan Wakely]

On 29/03/21 14:49 -0400, Patrick Palka via Libstdc++ wrote:
>The <ranges> header currently copies some simple algorithms from
><bits/ranges_algo.h>, which was originally done in order to avoid a
>circular dependency with the header.  This is no longer an issue since
>the latter header now includes <bits/ranges_util.h> instead of all of
><ranges>.
>
>This means we could now just include <bits/ranges_algo.h> and remove the
>copied algorithms, but that would double the size of <ranges>.  And we
>can't use the corresponding STL-style algorithms here because they
>assume input iterators are copyable.  So this patch instead simplifies
>these copied algorithms, removing their constraints and unused
>parameters, and keeps them around.  In a subsequent patch we're going to
>copy ranges::find into <ranges> as well.
>
>libstdc++-v3/ChangeLog:
>
>	* include/std/ranges (__detail::find_if): Simplify.
>	(__detail::find_if_not): Likewise.
>	(__detail::min): Remove.
>	(__detail::mismatch): Simplify.
>	(take_view::size): Use std::min instead of __detail::min.

I wonder if we want a <bits/ranges_algobase.h> which has this subset
of algos. That could be used from <ranges> and also from the real
algos in <bits/ranges_algo.h>. The ones in ranges_algobase.h wouldn't
need to have the constraints (because we know the caller is
constrained, or uses them correctly), but for that to work the unused
params would need to be re-added. We can consider that for GCC 12
though.

So OK for GCC 11.