Fix a self-move bug in inplace_merge. Thanks to Ted and Dexon for the report and the suggested fix.

llvm-svn: 243530

3 files changed, 101 insertions, 18 deletions

diff --git a/libcxx/include/algorithm b/libcxx/include/algorithm
index 459071f0984..7b0c53e05a5 100644
--- a/libcxx/include/algorithm
+++ b/libcxx/include/algorithm
@@ -4361,6 +4361,34 @@ merge(_InputIterator1 __first1, _InputIterator1 __last1,
 
 // inplace_merge
 
+template <class _Compare, class _InputIterator1, class _InputIterator2,
+          class _OutputIterator>
+void __half_inplace_merge(_InputIterator1 __first1, _InputIterator1 __last1,
+                          _InputIterator2 __first2, _InputIterator2 __last2,
+                          _OutputIterator __result, _Compare __comp)
+{
+    for (; __first1 != __last1; ++__result)
+    {
+        if (__first2 == __last2)
+        {
+            _VSTD::move(__first1, __last1, __result);
+            return;
+        }
+
+        if (__comp(*__first2, *__first1))
+        {
+            *__result = _VSTD::move(*__first2);
+            ++__first2;
+        }
+        else
+        {
+            *__result = _VSTD::move(*__first1);
+            ++__first1;
+        }
+    }
+    // __first2 through __last2 are already in the right spot.
+}
+
 template <class _Compare, class _BidirectionalIterator>
 void
 __buffered_inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last,
@@ -4376,11 +4404,7 @@ __buffered_inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator
         value_type* __p = __buff;
         for (_BidirectionalIterator __i = __first; __i != __middle; __d.__incr((value_type*)0), (void) ++__i, ++__p)
             ::new(__p) value_type(_VSTD::move(*__i));
-        __merge<_Compare>(move_iterator<value_type*>(__buff),
-                          move_iterator<value_type*>(__p),
-                          move_iterator<_BidirectionalIterator>(__middle),
-                          move_iterator<_BidirectionalIterator>(__last),
-                          __first, __comp);
+        __half_inplace_merge(__buff, __p, __middle, __last, __first, __comp);
     }
     else
     {
@@ -4389,9 +4413,9 @@ __buffered_inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator
             ::new(__p) value_type(_VSTD::move(*__i));
         typedef reverse_iterator<_BidirectionalIterator> _RBi;
         typedef reverse_iterator<value_type*> _Rv;
-        __merge(move_iterator<_RBi>(_RBi(__middle)), move_iterator<_RBi>(_RBi(__first)),
-                move_iterator<_Rv>(_Rv(__p)), move_iterator<_Rv>(_Rv(__buff)),
-                _RBi(__last), __negate<_Compare>(__comp));
+        __half_inplace_merge(_Rv(__p), _Rv(__buff), 
+                             _RBi(__middle), _RBi(__first),
+                             _RBi(__last), __negate<_Compare>(__comp));
     }
 }
 
diff --git a/libcxx/test/std/algorithms/alg.sorting/alg.merge/inplace_merge.pass.cpp b/libcxx/test/std/algorithms/alg.sorting/alg.merge/inplace_merge.pass.cpp
index 01db088aa43..9065b991d53 100644
--- a/libcxx/test/std/algorithms/alg.sorting/alg.merge/inplace_merge.pass.cpp
+++ b/libcxx/test/std/algorithms/alg.sorting/alg.merge/inplace_merge.pass.cpp
@@ -20,12 +20,35 @@
 
 #include "test_iterators.h"
 
+#ifndef TEST_STD_VER >= 11
+struct S {
+	S() : i_(0) {}
+	S(int i) : i_(i) {}
+	
+	S(const S&  rhs) : i_(rhs.i_) {}
+	S(      S&& rhs) : i_(rhs.i_) { rhs.i_ = -1; }
+	
+	S& operator =(const S&  rhs) { i_ = rhs.i_;              return *this; }
+	S& operator =(      S&& rhs) { i_ = rhs.i_; rhs.i_ = -2; assert(this != &rhs); return *this; }
+	S& operator =(int i)         { i_ = i;                   return *this; }
+	
+	bool operator  <(const S&  rhs) const { return i_ < rhs.i_; }
+	bool operator ==(const S&  rhs) const { return i_ == rhs.i_; }
+	bool operator ==(int i)         const { return i_ == i; }
+
+	void set(int i) { i_ = i; }
+	
+	int i_;
+	};
+#endif
+
 template <class Iter>
 void
 test_one(unsigned N, unsigned M)
 {
+    typedef typename std::iterator_traits<Iter>::value_type value_type;
     assert(M <= N);
-    int* ia = new int[N];
+    value_type* ia = new value_type[N];
     for (unsigned i = 0; i < N; ++i)
         ia[i] = i;
     std::random_shuffle(ia, ia+N);
@@ -76,4 +99,10 @@ int main()
     test<bidirectional_iterator<int*> >();
     test<random_access_iterator<int*> >();
     test<int*>();
+
+#ifndef TEST_STD_VER >= 11
+    test<bidirectional_iterator<S*> >();
+    test<random_access_iterator<S*> >();
+    test<S*>();
+#endif  // TEST_STD_VER >= 11
 }
diff --git a/libcxx/test/std/algorithms/alg.sorting/alg.merge/inplace_merge_comp.pass.cpp b/libcxx/test/std/algorithms/alg.sorting/alg.merge/inplace_merge_comp.pass.cpp
index b54efb688de..a9b14fca2fb 100644
--- a/libcxx/test/std/algorithms/alg.sorting/alg.merge/inplace_merge_comp.pass.cpp
+++ b/libcxx/test/std/algorithms/alg.sorting/alg.merge/inplace_merge_comp.pass.cpp
@@ -18,7 +18,10 @@
 #include <algorithm>
 #include <functional>
 #include <cassert>
-#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
+
+#include "test_macros.h"
+
+#ifndef TEST_STD_VER >= 11
 #include <memory>
 
 struct indirect_less
@@ -28,7 +31,29 @@ struct indirect_less
         {return *x < *y;}
 };
 
-#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
+struct S {
+	S() : i_(0) {}
+	S(int i) : i_(i) {}
+	
+	S(const S&  rhs) : i_(rhs.i_) {}
+	S(      S&& rhs) : i_(rhs.i_) { rhs.i_ = -1; }
+	
+	S& operator =(const S&  rhs) { i_ = rhs.i_;              return *this; }
+	S& operator =(      S&& rhs) { i_ = rhs.i_; rhs.i_ = -2; assert(this != &rhs); return *this; }
+	S& operator =(int i)         { i_ = i;                   return *this; }
+	
+	bool operator  <(const S&  rhs) const { return i_ < rhs.i_; }
+	bool operator  >(const S&  rhs) const { return i_ > rhs.i_; }
+	bool operator ==(const S&  rhs) const { return i_ == rhs.i_; }
+	bool operator ==(int i)         const { return i_ == i; }
+
+	void set(int i) { i_ = i; }
+	
+	int i_;
+	};
+
+
+#endif  // TEST_STD_VER >= 11
 
 #include "test_iterators.h"
 #include "counting_predicates.hpp"
@@ -38,19 +63,20 @@ void
 test_one(unsigned N, unsigned M)
 {
     assert(M <= N);
-    int* ia = new int[N];
+    typedef typename std::iterator_traits<Iter>::value_type value_type;
+    value_type* ia = new value_type[N];
     for (unsigned i = 0; i < N; ++i)
         ia[i] = i;
     std::random_shuffle(ia, ia+N);
-    std::sort(ia, ia+M, std::greater<int>());
-    std::sort(ia+M, ia+N, std::greater<int>());
-    binary_counting_predicate<std::greater<int>, int, int> pred((std::greater<int>()));
+    std::sort(ia, ia+M, std::greater<value_type>());
+    std::sort(ia+M, ia+N, std::greater<value_type>());
+    binary_counting_predicate<std::greater<value_type>, value_type, value_type> pred((std::greater<value_type>()));
     std::inplace_merge(Iter(ia), Iter(ia+M), Iter(ia+N), std::ref(pred));
     if(N > 0)
     {
         assert(ia[0] == N-1);
         assert(ia[N-1] == 0);
-        assert(std::is_sorted(ia, ia+N, std::greater<int>()));
+        assert(std::is_sorted(ia, ia+N, std::greater<value_type>()));
         assert(pred.count() <= (N-1));
     }
     delete [] ia;
@@ -93,7 +119,11 @@ int main()
     test<random_access_iterator<int*> >();
     test<int*>();
 
-#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
+#ifndef TEST_STD_VER >= 11
+    test<bidirectional_iterator<S*> >();
+    test<random_access_iterator<S*> >();
+    test<S*>();
+
     {
     unsigned N = 100;
     unsigned M = 50;
@@ -112,5 +142,5 @@ int main()
     }
     delete [] ia;
     }
-#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
+#endif  // TEST_STD_VER >= 11
 }