re PR libstdc++/49559 ([C++0x] stable_sort calls self-move-assignment operator)

2011-07-11  Paolo Carlini  <paolo.carlini@oracle.com>

	PR libstdc++/49559
	* include/bits/stl_algo.h (__move_merge_backward): Remove.
	(__move_merge_adaptive, __move_merge_adaptive_backward): New.
	(__merge_adaptive): Use the latter two.
	(__rotate_adaptive): Avoid self move-assignment.
	* include/bits/stl_algobase.h (move_backward): Fix comment.
	* testsuite/25_algorithms/stable_sort/49559.cc: New.
	* testsuite/25_algorithms/inplace_merge/49559.cc: Likewise.
	* testsuite/25_algorithms/inplace_merge/moveable.cc: Extend.
	* testsuite/25_algorithms/inplace_merge/moveable2.cc: Likewise.
	* testsuite/util/testsuite_rvalref.h (rvalstruct::operator=
	(rvalstruct&&)): Check for self move-assignment.

From-SVN: r176174

2 files changed, 171 insertions, 94 deletions

diff --git a/libstdc++-v3/include/bits/stl_algo.h b/libstdc++-v3/include/bits/stl_algo.h
index 5fc561e..8391d3e 100644
--- a/libstdc++-v3/include/bits/stl_algo.h
+++ b/libstdc++-v3/include/bits/stl_algo.h
@@ -2716,20 +2716,76 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
   // merge
 
-  /// This is a helper function for the merge routines.
+  /// This is a helper function for the __merge_adaptive routines.
+  template<typename _InputIterator1, typename _InputIterator2,
+	   typename _OutputIterator>
+    void
+    __move_merge_adaptive(_InputIterator1 __first1, _InputIterator1 __last1,
+			  _InputIterator2 __first2, _InputIterator2 __last2,
+			  _OutputIterator __result)
+    {
+      while (__first1 != __last1 && __first2 != __last2)
+	{
+	  if (*__first2 < *__first1)
+	    {
+	      *__result = _GLIBCXX_MOVE(*__first2);
+	      ++__first2;
+	    }
+	  else
+	    {
+	      *__result = _GLIBCXX_MOVE(*__first1);
+	      ++__first1;
+	    }
+	  ++__result;
+	}
+      if (__first1 != __last1)
+	_GLIBCXX_MOVE3(__first1, __last1, __result);
+    }
+
+  /// This is a helper function for the __merge_adaptive routines.
+  template<typename _InputIterator1, typename _InputIterator2,
+	   typename _OutputIterator, typename _Compare>
+    void
+    __move_merge_adaptive(_InputIterator1 __first1, _InputIterator1 __last1,
+			  _InputIterator2 __first2, _InputIterator2 __last2,
+			  _OutputIterator __result, _Compare __comp)
+    {
+      while (__first1 != __last1 && __first2 != __last2)
+	{
+	  if (__comp(*__first2, *__first1))
+	    {
+	      *__result = _GLIBCXX_MOVE(*__first2);
+	      ++__first2;
+	    }
+	  else
+	    {
+	      *__result = _GLIBCXX_MOVE(*__first1);
+	      ++__first1;
+	    }
+	  ++__result;
+	}
+      if (__first1 != __last1)
+	_GLIBCXX_MOVE3(__first1, __last1, __result);
+    }
+
+  /// This is a helper function for the __merge_adaptive routines.
   template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
 	   typename _BidirectionalIterator3>
-    _BidirectionalIterator3
-    __move_merge_backward(_BidirectionalIterator1 __first1,
-			  _BidirectionalIterator1 __last1,
-			  _BidirectionalIterator2 __first2,
-			  _BidirectionalIterator2 __last2,
-			  _BidirectionalIterator3 __result)
+    void
+    __move_merge_adaptive_backward(_BidirectionalIterator1 __first1,
+				   _BidirectionalIterator1 __last1,
+				   _BidirectionalIterator2 __first2,
+				   _BidirectionalIterator2 __last2,
+				   _BidirectionalIterator3 __result)
     {
       if (__first1 == __last1)
-	return _GLIBCXX_MOVE_BACKWARD3(__first2, __last2, __result);
-      if (__first2 == __last2)
-	return _GLIBCXX_MOVE_BACKWARD3(__first1, __last1, __result);
+	{
+	  _GLIBCXX_MOVE_BACKWARD3(__first2, __last2, __result);
+	  return;
+	}
+      else if (__first2 == __last2)
+	return;
+
       --__last1;
       --__last2;
       while (true)
@@ -2738,34 +2794,41 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	    {
 	      *--__result = _GLIBCXX_MOVE(*__last1);
 	      if (__first1 == __last1)
-		return _GLIBCXX_MOVE_BACKWARD3(__first2, ++__last2, __result);
+		{
+		  _GLIBCXX_MOVE_BACKWARD3(__first2, ++__last2, __result);
+		  return;
+		}
 	      --__last1;
 	    }
 	  else
 	    {
 	      *--__result = _GLIBCXX_MOVE(*__last2);
 	      if (__first2 == __last2)
-		return _GLIBCXX_MOVE_BACKWARD3(__first1, ++__last1, __result);
+		return;
 	      --__last2;
 	    }
 	}
     }
 
-  /// This is a helper function for the merge routines.
+  /// This is a helper function for the __merge_adaptive routines.
   template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
 	   typename _BidirectionalIterator3, typename _Compare>
-    _BidirectionalIterator3
-    __move_merge_backward(_BidirectionalIterator1 __first1,
-			  _BidirectionalIterator1 __last1,
-			  _BidirectionalIterator2 __first2,
-			  _BidirectionalIterator2 __last2,
-			  _BidirectionalIterator3 __result,
-			  _Compare __comp)
+    void
+    __move_merge_adaptive_backward(_BidirectionalIterator1 __first1,
+				   _BidirectionalIterator1 __last1,
+				   _BidirectionalIterator2 __first2,
+				   _BidirectionalIterator2 __last2,
+				   _BidirectionalIterator3 __result,
+				   _Compare __comp)
     {
       if (__first1 == __last1)
-	return _GLIBCXX_MOVE_BACKWARD3(__first2, __last2, __result);
-      if (__first2 == __last2)
-	return _GLIBCXX_MOVE_BACKWARD3(__first1, __last1, __result);
+	{
+	  _GLIBCXX_MOVE_BACKWARD3(__first2, __last2, __result);
+	  return;
+	}
+      else if (__first2 == __last2)
+	return;
+
       --__last1;
       --__last2;
       while (true)
@@ -2774,75 +2837,23 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	    {
 	      *--__result = _GLIBCXX_MOVE(*__last1);
 	      if (__first1 == __last1)
-		return _GLIBCXX_MOVE_BACKWARD3(__first2, ++__last2, __result);
+		{
+		  _GLIBCXX_MOVE_BACKWARD3(__first2, ++__last2, __result);
+		  return;
+		}
 	      --__last1;
 	    }
 	  else
 	    {
 	      *--__result = _GLIBCXX_MOVE(*__last2);
 	      if (__first2 == __last2)
-		return _GLIBCXX_MOVE_BACKWARD3(__first1, ++__last1, __result);
+		return;
 	      --__last2;
 	    }
 	}
     }
 
   /// This is a helper function for the merge routines.
-  template<typename _InputIterator1, typename _InputIterator2,
-	   typename _OutputIterator>
-    _OutputIterator
-    __move_merge(_InputIterator1 __first1, _InputIterator1 __last1,
-		 _InputIterator2 __first2, _InputIterator2 __last2,
-		 _OutputIterator __result)
-    {
-      while (__first1 != __last1 && __first2 != __last2)
-	{
-	  if (*__first2 < *__first1)
-	    {
-	      *__result = _GLIBCXX_MOVE(*__first2);
-	      ++__first2;
-	    }
-	  else
-	    {
-	      *__result = _GLIBCXX_MOVE(*__first1);
-	      ++__first1;
-	    }
-	  ++__result;
-	}
-      return _GLIBCXX_MOVE3(__first2, __last2,
-			    _GLIBCXX_MOVE3(__first1, __last1,
-					   __result));
-    }
-
-  /// This is a helper function for the merge routines.
-  template<typename _InputIterator1, typename _InputIterator2,
-	   typename _OutputIterator, typename _Compare>
-    _OutputIterator
-    __move_merge(_InputIterator1 __first1, _InputIterator1 __last1,
-		 _InputIterator2 __first2, _InputIterator2 __last2,
-		 _OutputIterator __result, _Compare __comp)
-    {
-      while (__first1 != __last1 && __first2 != __last2)
-	{
-	  if (__comp(*__first2, *__first1))
-	    {
-	      *__result = _GLIBCXX_MOVE(*__first2);
-	      ++__first2;
-	    }
-	  else
-	    {
-	      *__result = _GLIBCXX_MOVE(*__first1);
-	      ++__first1;
-	    }
-	  ++__result;
-	}
-      return _GLIBCXX_MOVE3(__first2, __last2,
-			    _GLIBCXX_MOVE3(__first1, __last1,
-					   __result));
-    }
-
-
-  /// This is a helper function for the merge routines.
   template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
 	   typename _Distance>
     _BidirectionalIterator1
@@ -2856,15 +2867,25 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       _BidirectionalIterator2 __buffer_end;
       if (__len1 > __len2 && __len2 <= __buffer_size)
 	{
-	  __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
-	  _GLIBCXX_MOVE_BACKWARD3(__first, __middle, __last);
-	  return _GLIBCXX_MOVE3(__buffer, __buffer_end, __first);
+	  if (__len2)
+	    {
+	      __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
+	      _GLIBCXX_MOVE_BACKWARD3(__first, __middle, __last);
+	      return _GLIBCXX_MOVE3(__buffer, __buffer_end, __first);
+	    }
+	  else
+	    return __first;
 	}
       else if (__len1 <= __buffer_size)
 	{
-	  __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
-	  _GLIBCXX_MOVE3(__middle, __last, __first);
-	  return _GLIBCXX_MOVE_BACKWARD3(__buffer, __buffer_end, __last);
+	  if (__len1)
+	    {
+	      __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
+	      _GLIBCXX_MOVE3(__middle, __last, __first);
+	      return _GLIBCXX_MOVE_BACKWARD3(__buffer, __buffer_end, __last);
+	    }
+	  else
+	    return __last;
 	}
       else
 	{
@@ -2887,13 +2908,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       if (__len1 <= __len2 && __len1 <= __buffer_size)
 	{
 	  _Pointer __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
-	  std::__move_merge(__buffer, __buffer_end, __middle, __last, __first);
+	  std::__move_merge_adaptive(__buffer, __buffer_end, __middle, __last,
+				     __first);
 	}
       else if (__len2 <= __buffer_size)
 	{
 	  _Pointer __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
-	  std::__move_merge_backward(__first, __middle, __buffer,
-				    __buffer_end, __last);
+	  std::__move_merge_adaptive_backward(__first, __middle, __buffer,
+					      __buffer_end, __last);
 	}
       else
 	{
@@ -2943,14 +2965,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       if (__len1 <= __len2 && __len1 <= __buffer_size)
 	{
 	  _Pointer __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
-	  std::__move_merge(__buffer, __buffer_end, __middle, __last,
-			    __first, __comp);
+	  std::__move_merge_adaptive(__buffer, __buffer_end, __middle, __last,
+				     __first, __comp);
 	}
       else if (__len2 <= __buffer_size)
 	{
 	  _Pointer __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
-	  std::__move_merge_backward(__first, __middle, __buffer, __buffer_end,
-				     __last, __comp);
+	  std::__move_merge_adaptive_backward(__first, __middle, __buffer,
+					      __buffer_end, __last, __comp);
 	}
       else
 	{
@@ -3187,6 +3209,61 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 			      __comp);
     }
 
+
+  /// This is a helper function for the __merge_sort_loop routines.
+  template<typename _InputIterator1, typename _InputIterator2,
+	   typename _OutputIterator>
+    _OutputIterator
+    __move_merge(_InputIterator1 __first1, _InputIterator1 __last1,
+		 _InputIterator2 __first2, _InputIterator2 __last2,
+		 _OutputIterator __result)
+    {
+      while (__first1 != __last1 && __first2 != __last2)
+	{
+	  if (*__first2 < *__first1)
+	    {
+	      *__result = _GLIBCXX_MOVE(*__first2);
+	      ++__first2;
+	    }
+	  else
+	    {
+	      *__result = _GLIBCXX_MOVE(*__first1);
+	      ++__first1;
+	    }
+	  ++__result;
+	}
+      return _GLIBCXX_MOVE3(__first2, __last2,
+			    _GLIBCXX_MOVE3(__first1, __last1,
+					   __result));
+    }
+
+  /// This is a helper function for the __merge_sort_loop routines.
+  template<typename _InputIterator1, typename _InputIterator2,
+	   typename _OutputIterator, typename _Compare>
+    _OutputIterator
+    __move_merge(_InputIterator1 __first1, _InputIterator1 __last1,
+		 _InputIterator2 __first2, _InputIterator2 __last2,
+		 _OutputIterator __result, _Compare __comp)
+    {
+      while (__first1 != __last1 && __first2 != __last2)
+	{
+	  if (__comp(*__first2, *__first1))
+	    {
+	      *__result = _GLIBCXX_MOVE(*__first2);
+	      ++__first2;
+	    }
+	  else
+	    {
+	      *__result = _GLIBCXX_MOVE(*__first1);
+	      ++__first1;
+	    }
+	  ++__result;
+	}
+      return _GLIBCXX_MOVE3(__first2, __last2,
+			    _GLIBCXX_MOVE3(__first1, __last1,
+					   __result));
+    }
+
   template<typename _RandomAccessIterator1, typename _RandomAccessIterator2,
 	   typename _Distance>
     void
diff --git a/libstdc++-v3/include/bits/stl_algobase.h b/libstdc++-v3/include/bits/stl_algobase.h
index 626d5bf..aecdcb9 100644
--- a/libstdc++-v3/include/bits/stl_algobase.h
+++ b/libstdc++-v3/include/bits/stl_algobase.h
@@ -641,7 +641,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
    *  loop count will be known (and therefore a candidate for compiler
    *  optimizations such as unrolling).
    *
-   *  Result may not be in the range [first,last).  Use move instead.  Note
+   *  Result may not be in the range (first,last].  Use move instead.  Note
    *  that the start of the output range may overlap [first,last).
   */
   template<typename _BI1, typename _BI2>