libstdc++: Fix some ranges algos optimizations [PR95578]

diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h
index c038a505afa..94ca7b6488d 100644
--- a/libstdc++-v3/include/bits/ranges_algo.h
+++ b/libstdc++-v3/include/bits/ranges_algo.h
@@ -3452,11 +3452,15 @@  namespace ranges
 		 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
       {
 	if constexpr (__detail::__is_normal_iterator<_Iter1>
-		      || __detail::__is_normal_iterator<_Iter2>)
-	  return (*this)(std::__niter_base(std::move(__first1)),
-			 std::__niter_base(std::move(__last1)),
-			 std::__niter_base(std::move(__first2)),
-			 std::__niter_base(std::move(__last2)),
+		      && same_as<_Iter1, _Sent1>)
+	  return (*this)(__first1.base(), __last1.base(),
+			 std::move(__first2), std::move(__last2),
+			 std::move(__comp),
+			 std::move(__proj1), std::move(__proj2));
+	else if constexpr (__detail::__is_normal_iterator<_Iter2>
+			   && same_as<_Iter2, _Sent2>)
+	  return (*this)(std::move(__first1), std::move(__last1),
+			 __first2.base(), __last2.base(),
 			 std::move(__comp),
 			 std::move(__proj1), std::move(__proj2));
 	else
diff --git a/libstdc++-v3/include/bits/ranges_algobase.h b/libstdc++-v3/include/bits/ranges_algobase.h
index 49ca5ed4155..3bdc7cc471b 100644
--- a/libstdc++-v3/include/bits/ranges_algobase.h
+++ b/libstdc++-v3/include/bits/ranges_algobase.h
@@ -85,11 +85,15 @@  namespace ranges
 	// 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 (*this)(std::__niter_base(std::move(__first1)),
-			 std::__niter_base(std::move(__last1)),
-			 std::__niter_base(std::move(__first2)),
-			 std::__niter_base(std::move(__last2)),
+		      && same_as<_Iter1, _Sent1>)
+	  return (*this)(__first1.base(), __last1.base(),
+			 std::move(__first2), std::move(__last2),
+			 std::move(__pred),
+			 std::move(__proj1), std::move(__proj2));
+	else if constexpr (__detail::__is_normal_iterator<_Iter2>
+			   && same_as<_Iter2, _Sent2>)
+	  return (*this)(std::move(__first1), std::move(__last1),
+			 __first2.base(), __last2.base(),
 			 std::move(__pred),
 			 std::move(__proj1), std::move(__proj2));
 	else if constexpr (sized_sentinel_for<_Sent1, _Iter1>
@@ -211,14 +215,10 @@  namespace ranges
     {
       // TODO: implement more specializations to be at least on par with
       // std::copy/std::move.
-      constexpr bool __normal_iterator_p
-	= (__detail::__is_normal_iterator<_Iter>
-	   || __detail::__is_normal_iterator<_Out>);
-      constexpr bool __reverse_p
-	= (__detail::__is_reverse_iterator<_Iter>
-	   && __detail::__is_reverse_iterator<_Out>);
-      constexpr bool __move_iterator_p = __detail::__is_move_iterator<_Iter>;
-      if constexpr (__move_iterator_p)
+      using __detail::__is_move_iterator;
+      using __detail::__is_reverse_iterator;
+      using __detail::__is_normal_iterator;
+      if constexpr (__is_move_iterator<_Iter> && same_as<_Iter, _Sent>)
 	{
 	  auto [__in, __out]
 	    = ranges::__copy_or_move<true>(std::move(__first).base(),
@@ -226,23 +226,28 @@  namespace ranges
 					   std::move(__result));
 	  return {move_iterator{std::move(__in)}, std::move(__out)};
 	}
-      else if constexpr (__reverse_p)
+      else if constexpr (__is_reverse_iterator<_Iter> && same_as<_Iter, _Sent>
+			 && __is_reverse_iterator<_Out>)
 	{
 	  auto [__in,__out]
-	    = ranges::__copy_or_move_backward<_IsMove>(__last.base(),
-						       __first.base(),
-						       __result.base());
+	    = ranges::__copy_or_move_backward<_IsMove>(std::move(__last).base(),
+						       std::move(__first).base(),
+						       std::move(__result).base());
 	  return {reverse_iterator{std::move(__in)},
 		  reverse_iterator{std::move(__out)}};
 	}
-      else if constexpr (__normal_iterator_p)
+      else if constexpr (__is_normal_iterator<_Iter> && same_as<_Iter, _Sent>)
+	{
+	  auto [__in,__out]
+	    = ranges::__copy_or_move<_IsMove>(__first.base(), __last.base(),
+					      __result);
+	  return {decltype(__first){__in}, std::move(__out)};
+	}
+      else if constexpr (__is_normal_iterator<_Out>)
 	{
 	  auto [__in,__out]
-	    = ranges::__copy_or_move<_IsMove>(std::__niter_base(__first),
-					      std::__niter_base(__last),
-					      std::__niter_base(__result));
-	  return {std::__niter_wrap(__first, std::move(__in)),
-		  std::__niter_wrap(__result, std::move(__out))};
+	    = ranges::__copy_or_move<_IsMove>(__first, __last, __result.base());
+	  return {std::move(__in), decltype(__result){__out}};
 	}
       else if constexpr (sized_sentinel_for<_Sent, _Iter>)
 	{
@@ -353,30 +358,33 @@  namespace ranges
     {
       // TODO: implement more specializations to be at least on par with
       // std::copy_backward/std::move_backward.
-      constexpr bool __normal_iterator_p
-	= (__detail::__is_normal_iterator<_Iter>
-	   || __detail::__is_normal_iterator<_Out>);
-      constexpr bool __reverse_p
-	= (__detail::__is_reverse_iterator<_Iter>
-	   && __detail::__is_reverse_iterator<_Out>);
-      if constexpr (__reverse_p)
+      using __detail::__is_reverse_iterator;
+      using __detail::__is_normal_iterator;
+      if constexpr (__is_reverse_iterator<_Iter> && same_as<_Iter, _Sent>
+		    && __is_reverse_iterator<_Out>)
 	{
 	  auto [__in,__out]
-	    = ranges::__copy_or_move<_IsMove>(__last.base(),
-					      __first.base(),
-					      __result.base());
+	    = ranges::__copy_or_move<_IsMove>(std::move(__last).base(),
+					      std::move(__first).base(),
+					      std::move(__result).base());
 	  return {reverse_iterator{std::move(__in)},
 		  reverse_iterator{std::move(__out)}};
 	}
-      else if constexpr (__normal_iterator_p)
+      else if constexpr (__is_normal_iterator<_Iter> && same_as<_Iter, _Sent>)
 	{
 	  auto [__in,__out]
-	    = ranges::__copy_or_move_backward<_IsMove>
-	      (std::__niter_base(__first),
-	       std::__niter_base(__last),
-	       std::__niter_base(__result));
-	  return {std::__niter_wrap(__first, std::move(__in)),
-		  std::__niter_wrap(__result, std::move(__out))};
+	    = ranges::__copy_or_move_backward<_IsMove>(__first.base(),
+						       __last.base(),
+						       std::move(__result));
+	  return {decltype(__first){__in}, std::move(__out)};
+	}
+      else if constexpr (__is_normal_iterator<_Out>)
+	{
+	  auto [__in,__out]
+	    = ranges::__copy_or_move_backward<_IsMove>(std::move(__first),
+						       std::move(__last),
+						       __result.base());
+	  return {std::move(__in), decltype(__result){__out}};
 	}
       else if constexpr (sized_sentinel_for<_Sent, _Iter>)
 	{
diff --git a/libstdc++-v3/testsuite/25_algorithms/copy/95578.cc b/libstdc++-v3/testsuite/25_algorithms/copy/95578.cc
new file mode 100644
index 00000000000..7aaefba454c
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/copy/95578.cc
@@ -0,0 +1,74 @@ 
+// 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 run { target c++2a } }
+
+#include <algorithm>
+#include <vector>
+#include <testsuite_hooks.h>
+
+namespace ranges = std::ranges;
+
+template<typename It>
+struct sentinel
+{
+  It it;
+
+  friend bool
+  operator==(It x, sentinel y)
+  { return x == y.it; }
+};
+
+void
+test01()
+{
+  std::vector<int> v = {1,2,3,4,5}, w = {0,0,0,0,0};
+  ranges::subrange sr = {v.begin(), sentinel{v.end()}};
+  ranges::copy(sr, w.begin());
+  VERIFY( ranges::equal(w, (int[]){1,2,3,4,5}) );
+}
+
+void
+test02()
+{
+  using std::reverse_iterator;
+  std::vector<int> v = {1,2,3,4,5}, w = {0,0,0,0,0};
+  ranges::subrange sr
+    = {reverse_iterator{v.end()}, sentinel{reverse_iterator{v.begin()}}};
+  ranges::copy(sr, reverse_iterator{w.end()});
+  VERIFY( ranges::equal(w, (int[]){1,2,3,4,5}) );
+}
+
+void
+test03()
+{
+  using std::move_iterator;
+  std::vector<int> v = {1,2,3,4,5}, w = {0,0,0,0,0};
+  ranges::subrange sr
+    = {move_iterator{v.begin()}, sentinel{move_iterator{v.end()}}};
+  ranges::copy(sr, w.begin());
+  VERIFY( ranges::equal(w, (int[]){1,2,3,4,5}) );
+}
+
+int
+main()
+{
+  test01();
+  test02();
+  test03();
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/copy_backward/95578.cc b/libstdc++-v3/testsuite/25_algorithms/copy_backward/95578.cc
new file mode 100644
index 00000000000..6e3d1b62401
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/copy_backward/95578.cc
@@ -0,0 +1,62 @@ 
+// 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 run { target c++2a } }
+
+#include <algorithm>
+#include <vector>
+#include <testsuite_hooks.h>
+
+namespace ranges = std::ranges;
+
+template<typename It>
+struct sentinel
+{
+  It it;
+
+  friend bool
+  operator==(It x, sentinel y)
+  { return x == y.it; }
+};
+
+void
+test01()
+{
+  std::vector<int> v = {1,2,3,4,5}, w = {0,0,0,0,0};
+  ranges::subrange sr = {v.begin(), sentinel{v.end()}};
+  ranges::copy_backward(sr, w.end());
+  VERIFY( ranges::equal(w, (int[]){1,2,3,4,5}) );
+}
+
+void
+test02()
+{
+  using std::reverse_iterator;
+  std::vector<int> v = {1,2,3,4,5}, w = {0,0,0,0,0};
+  ranges::subrange sr
+    = {reverse_iterator{v.end()}, sentinel{reverse_iterator{v.begin()}}};
+  ranges::copy_backward(sr, reverse_iterator{w.begin()});
+  VERIFY( ranges::equal(w, (int[]){1,2,3,4,5}) );
+}
+
+int
+main()
+{
+  test01();
+  test02();
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/equal/95578.cc b/libstdc++-v3/testsuite/25_algorithms/equal/95578.cc
new file mode 100644
index 00000000000..b69d877e4e3
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/equal/95578.cc
@@ -0,0 +1,74 @@ 
+// 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 run { target c++2a } }
+
+#include <algorithm>
+#include <vector>
+#include <testsuite_hooks.h>
+
+namespace ranges = std::ranges;
+
+template<typename It>
+struct sentinel
+{
+  It it;
+
+  friend bool
+  operator==(It x, sentinel y)
+  { return x == y.it; }
+};
+
+void
+test01()
+{
+  std::vector<int> v = {1,2,3,4,5};
+  ranges::subrange sr = {v.begin(), sentinel{v.end()}};
+  VERIFY( ranges::equal(sr, v) );
+  VERIFY( ranges::equal(v, sr) );
+}
+
+void
+test02()
+{
+  using std::reverse_iterator;
+  std::vector<int> v = {1,2,3,4,5};
+  ranges::subrange sr
+    = {reverse_iterator{v.end()}, sentinel{reverse_iterator{v.begin()}}};
+  VERIFY( ranges::equal(sr, (int[]){5,4,3,2,1}) );
+  VERIFY( ranges::equal((int[]){5,4,3,2,1}, sr) );
+}
+
+void
+test03()
+{
+  using std::move_iterator;
+  std::vector<int> v = {1,2,3,4,5};
+  ranges::subrange sr
+    = {move_iterator{v.begin()}, sentinel{move_iterator{v.end()}}};
+  VERIFY( ranges::equal(sr, v) );
+  VERIFY( ranges::equal(v, sr) );
+}
+
+int
+main()
+{
+  test01();
+  test02();
+  test03();
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/95578.cc b/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/95578.cc
new file mode 100644
index 00000000000..693506826bc
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/95578.cc
@@ -0,0 +1,74 @@ 
+// 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 run { target c++2a } }
+
+#include <algorithm>
+#include <vector>
+#include <testsuite_hooks.h>
+
+namespace ranges = std::ranges;
+
+template<typename It>
+struct sentinel
+{
+  It it;
+
+  friend bool
+  operator==(It x, sentinel y)
+  { return x == y.it; }
+};
+
+void
+test01()
+{
+  std::vector<int> v = {1,2,3,4,5};
+  ranges::subrange sr = {v.begin(), sentinel{v.end()}};
+  VERIFY( ranges::lexicographical_compare(sr, (int[]){1,2,3,5,5}) );
+  VERIFY( !ranges::lexicographical_compare((int[]){1,2,3,5,5}, sr) );
+}
+
+void
+test02()
+{
+  using std::reverse_iterator;
+  std::vector<int> v = {1,2,3,4,5};
+  ranges::subrange sr
+    = {reverse_iterator{v.end()}, sentinel{reverse_iterator{v.begin()}}};
+  VERIFY( ranges::lexicographical_compare(sr, (int[]){5,4,3,2,2}) );
+  VERIFY( !ranges::lexicographical_compare((int[]){5,4,3,2,2}, sr) );
+}
+
+void
+test03()
+{
+  using std::move_iterator;
+  std::vector<int> v = {1,2,3,4,5};
+  ranges::subrange sr
+    = {move_iterator{v.begin()}, sentinel{move_iterator{v.end()}}};
+  VERIFY( ranges::lexicographical_compare(sr, (int[]){1,2,3,5,5}) );
+  VERIFY( !ranges::lexicographical_compare((int[]){1,2,3,5,5}, sr) );
+}
+
+int
+main()
+{
+  test01();
+  test02();
+  test03();
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/move/95578.cc b/libstdc++-v3/testsuite/25_algorithms/move/95578.cc
new file mode 100644
index 00000000000..e5c494d55d2
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/move/95578.cc
@@ -0,0 +1,62 @@ 
+// 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 run { target c++2a } }
+
+#include <algorithm>
+#include <vector>
+#include <testsuite_hooks.h>
+
+namespace ranges = std::ranges;
+
+template<typename It>
+struct sentinel
+{
+  It it;
+
+  friend bool
+  operator==(It x, sentinel y)
+  { return x == y.it; }
+};
+
+void
+test01()
+{
+  std::vector<int> v = {1,2,3,4,5}, w = {0,0,0,0,0};
+  ranges::subrange sr = {v.begin(), sentinel{v.end()}};
+  ranges::move(sr, w.begin());
+  VERIFY( ranges::equal(w, (int[]){1,2,3,4,5}) );
+}
+
+void
+test02()
+{
+  using std::reverse_iterator;
+  std::vector<int> v = {1,2,3,4,5}, w = {0,0,0,0,0};
+  ranges::subrange sr
+    = {reverse_iterator{v.end()}, sentinel{reverse_iterator{v.begin()}}};
+  ranges::move(sr, reverse_iterator{w.end()});
+  VERIFY( ranges::equal(w, (int[]){1,2,3,4,5}) );
+}
+
+int
+main()
+{
+  test01();
+  test02();
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/move_backward/95578.cc b/libstdc++-v3/testsuite/25_algorithms/move_backward/95578.cc
new file mode 100644
index 00000000000..694e4a75c83
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/move_backward/95578.cc
@@ -0,0 +1,62 @@ 
+// 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 run { target c++2a } }
+
+#include <algorithm>
+#include <vector>
+#include <testsuite_hooks.h>
+
+namespace ranges = std::ranges;
+
+template<typename It>
+struct sentinel
+{
+  It it;
+
+  friend bool
+  operator==(It x, sentinel y)
+  { return x == y.it; }
+};
+
+void
+test01()
+{
+  std::vector<int> v = {1,2,3,4,5}, w = {0,0,0,0,0};
+  ranges::subrange sr = {v.begin(), sentinel{v.end()}};
+  ranges::move_backward(sr, w.end());
+  VERIFY( ranges::equal(w, (int[]){1,2,3,4,5}) );
+}
+
+void
+test02()
+{
+  using std::reverse_iterator;
+  std::vector<int> v = {1,2,3,4,5}, w = {0,0,0,0,0};
+  ranges::subrange sr
+    = {reverse_iterator{v.end()}, sentinel{reverse_iterator{v.begin()}}};
+  ranges::move_backward(sr, reverse_iterator{w.begin()});
+  VERIFY( ranges::equal(w, (int[]){1,2,3,4,5}) );
+}
+
+int
+main()
+{
+  test01();
+  test02();
+}