[PATCH 1/3] libstdc++: Fold some ranges algo subroutines into their only caller

[Jonathan Wakely]

On 14/02/20 10:35 -0500, Patrick Palka wrote:
>These subroutines have only a single call site, so it might be best and simplest
>to eliminate them before we convert the algos into function objects.
>
>libstdc++-v3/ChangeLog:
>
>	* include/bits/ranges_algo.h (ranges::__find_end): Fold into ...
>	(ranges::find_end): ... here.
>	(ranges::__lexicographical_compare): Fold into ...
>	(ranges::lexicographical_compare): ... here.
>	* include/bits/ranges_algobase.h (ranges::__equal): Fold into ...
>	(ranges::equal): ... here.

OK for master, but please note the two comments below.


> libstdc++-v3/include/bits/ranges_algo.h     | 104 ++++++++------------
> libstdc++-v3/include/bits/ranges_algobase.h |  33 +++----
> 2 files changed, 55 insertions(+), 82 deletions(-)
>
>diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h
>index 84a02cabb80..6b6f4defdf5 100644
>--- a/libstdc++-v3/include/bits/ranges_algo.h
>+++ b/libstdc++-v3/include/bits/ranges_algo.h
>@@ -513,40 +513,7 @@ namespace ranges
> 			      std::move(__pred), std::move(__proj));
>     }
>
>-  template<forward_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
>-	   forward_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>
>-    constexpr subrange<_Iter1>
>-    __find_end(_Iter1 __first1, _Sent1 __last1,
>-	       _Iter2 __first2, _Sent2 __last2,
>-	       _Pred __pred, _Proj1 __proj1, _Proj2 __proj2)
>-    {
>-      auto __i = ranges::next(__first1, __last1);
>-      if (__first2 == __last2)
>-	return {__i, __i};
>
>-      auto __result_begin = __i;
>-      auto __result_end = __i;
>-      for (;;)
>-	{
>-	  auto __new_range = ranges::search(__first1, __last1,
>-					    __first2, __last2,
>-					    __pred, __proj1, __proj2);
>-	  auto __new_result_begin = ranges::begin(__new_range);
>-	  auto __new_result_end = ranges::end(__new_range);
>-	  if (__new_result_begin == __last1)
>-	    return {__result_begin, __result_end};
>-	  else
>-	    {
>-	      __result_begin = __new_result_begin;
>-	      __result_end = __new_result_end;
>-	      __first1 = __result_begin;
>-	      ++__first1;
>-	    }
>-	}
>-    }
>
>   template<forward_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
> 	   forward_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
>@@ -578,9 +545,31 @@ namespace ranges
> 	    return {__result_first, __result_last};
> 	}
>       else
>-	return ranges::__find_end(__first1, __last1, __first2, __last2,
>-				  std::move(__pred),
>-				  std::move(__proj1), std::move(__proj2));
>+	{
>+	  auto __i = ranges::next(__first1, __last1);
>+	  if (__first2 == __last2)
>+	    return {__i, __i};
>+
>+	  auto __result_begin = __i;
>+	  auto __result_end = __i;
>+	  for (;;)
>+	    {
>+	      auto __new_range = ranges::search(__first1, __last1,
>+						__first2, __last2,
>+						__pred, __proj1, __proj2);
>+	      auto __new_result_begin = ranges::begin(__new_range);
>+	      auto __new_result_end = ranges::end(__new_range);
>+	      if (__new_result_begin == __last1)
>+		return {__result_begin, __result_end};
>+	      else
>+		{
>+		  __result_begin = __new_result_begin;
>+		  __result_end = __new_result_end;
>+		  __first1 = __result_begin;
>+		  ++__first1;
>+		}
>+	    }
>+	}
>     }
>
>   template<forward_range _Range1, forward_range _Range2,
>@@ -2908,14 +2897,26 @@ namespace ranges
>
>   template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
> 	   input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
>-	   typename _Proj1, typename _Proj2,
>+	   typename _Proj1 = identity, typename _Proj2 = identity,
> 	   indirect_strict_weak_order<projected<_Iter1, _Proj1>,
>-				      projected<_Iter2, _Proj2>> _Comp>
>+				      projected<_Iter2, _Proj2>>
>+	     _Comp = ranges::less>
>     constexpr bool
>-    __lexicographical_compare(_Iter1 __first1, _Sent1 __last1,
>-			      _Iter2 __first2, _Sent2 __last2,
>-			      _Comp __comp, _Proj1 __proj1, _Proj2 __proj2)
>+    lexicographical_compare(_Iter1 __first1, _Sent1 __last1,
>+			    _Iter2 __first2, _Sent2 __last2,
>+			    _Comp __comp = {},
>+			    _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
>     {
>+      if constexpr (__detail::__is_normal_iterator<_Iter1>
>+		    || __detail::__is_normal_iterator<_Iter2>)
>+	return ranges::lexicographical_compare
>+		 (std::__niter_base(std::move(__first1)),
>+		  std::__niter_base(std::move(__last1)),
>+		  std::__niter_base(std::move(__first2)),
>+		  std::__niter_base(std::move(__last2)),
>+		  std::move(__comp),
>+		  std::move(__proj1), std::move(__proj2));
>+

I think we want "else {" here, so the lines following are not
instantiated when we unpack normal iterators.

That can be done in a separate patch later though.

>       constexpr bool __sized_iters
> 	= (sized_sentinel_for<_Sent1, _Iter1>
> 	   && sized_sentinel_for<_Sent2, _Iter2>);
>@@ -2976,27 +2977,6 @@ namespace ranges
>       return __first1 == __last1 && __first2 != __last2;
>     }
>
>-  template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
>-	   input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
>-	   typename _Proj1 = identity, typename _Proj2 = identity,
>-	   indirect_strict_weak_order<projected<_Iter1, _Proj1>,
>-				      projected<_Iter2, _Proj2>>
>-	     _Comp = ranges::less>
>-    constexpr bool
>-    lexicographical_compare(_Iter1 __first1, _Sent1 __last1,
>-			    _Iter2 __first2, _Sent2 __last2,
>-			    _Comp __comp = {},
>-			    _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
>-    {
>-      return (ranges::__lexicographical_compare
>-	      (std::__niter_base(std::move(__first1)),
>-	       std::__niter_base(std::move(__last1)),
>-	       std::__niter_base(std::move(__first2)),
>-	       std::__niter_base(std::move(__last2)),
>-	       std::move(__comp),
>-	       std::move(__proj1), std::move(__proj2)));
>-    }
>-
>   template<input_range _Range1, input_range _Range2, typename _Proj1 = identity,
> 	   typename _Proj2 = identity,
> 	   indirect_strict_weak_order<projected<iterator_t<_Range1>, _Proj1>,
>diff --git a/libstdc++-v3/include/bits/ranges_algobase.h b/libstdc++-v3/include/bits/ranges_algobase.h
>index f63c032cf0b..813a5096ae0 100644
>--- a/libstdc++-v3/include/bits/ranges_algobase.h
>+++ b/libstdc++-v3/include/bits/ranges_algobase.h
>@@ -73,14 +73,24 @@ namespace ranges
>
>   template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
> 	   input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
>-	   typename _Pred, typename _Proj1, typename _Proj2>
>+	   typename _Pred = ranges::equal_to,
>+	   typename _Proj1 = identity, typename _Proj2 = identity>
>     requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2>
>     constexpr bool
>-    __equal(_Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Sent2 __last2,
>-	    _Pred __pred, _Proj1 __proj1, _Proj2 __proj2)
>+    equal(_Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Sent2 __last2,
>+	  _Pred __pred = {}, _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
>     {
>       // TODO: implement more specializations to at least have parity with
>       // std::equal.
>+      if constexpr (__detail::__is_normal_iterator<_Iter1>
>+		    || __detail::__is_normal_iterator<_Iter2>)
>+	return ranges::equal(std::__niter_base(std::move(__first1)),
>+			     std::__niter_base(std::move(__last1)),
>+			     std::__niter_base(std::move(__first2)),
>+			     std::__niter_base(std::move(__last2)),
>+			     std::move(__pred),
>+			     std::move(__proj1), std::move(__proj2));
>+

Same thing here.

>       constexpr bool __sized_iters
> 	= (sized_sentinel_for<_Sent1, _Iter1>
> 	   && sized_sentinel_for<_Sent2, _Iter2>);
>@@ -129,23 +139,6 @@ namespace ranges
> 	}
>     }
>
>-  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>
>-    constexpr bool
>-    equal(_Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Sent2 __last2,
>-	  _Pred __pred = {}, _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
>-    {
>-      return ranges::__equal(std::__niter_base(std::move(__first1)),
>-			     std::__niter_base(std::move(__last1)),
>-			     std::__niter_base(std::move(__first2)),
>-			     std::__niter_base(std::move(__last2)),
>-			     std::move(__pred),
>-			     std::move(__proj1), std::move(__proj2));
>-    }
>-
>   template<input_range _Range1, input_range _Range2,
> 	   typename _Pred = ranges::equal_to,
> 	   typename _Proj1 = identity, typename _Proj2 = identity>
>-- 
>2.25.0.232.gd8437c57fa
>