Fix std::inplace_merge to be stable for all inputs

[jdoerrie]

Summary

This change fixes std::inplace_merge to be stable for all inputs and adds corresponding tests.

Fixes Bug 31166: https://bugs.llvm.org//show_bug.cgi?id=31166

[jdoerrie]

include/algorithm

4471

As marshall pointed out in https://bugs.llvm.org//show_bug.cgi?id=31166 this is where the problem lies. While reversing the input ranges is a very nifty trick to be able to use the moved out space at the end of [first, last), simply negating the comparison functor is not enough to preserve stability.

Assuming a default __comp of std::less, in line 4431 a negated __comp will evaluate to true for equivalent elements, resulting in a move from *__first2 and thus breaking stability. The fix for this to to still have __comp evaluate to false for equivalent elements, what the change in 748 accomplishes.

Given that now __negate technically does not negate anymore, maybe it should be renamed to a more suiting __reverse or __swap or similar. Doing a quick grep over the code base line 4471 seems to be the only place where this is used, so a rename should not have further consequences. Furthermore, the unary bool operator() could be deleted.

[jdoerrie]

Ping, please take a look at this.

[mclow.lists]

I applied the test change, but not the algorithm change, and the tests passed.

[mclow.lists]

Note: I suspect that the proposed change to <algorithm> fixes the problem, but the new tests don't check that.

[mclow.lists]

I committed as r311952 which fixes this - based on Jan's suggestion, but not quite the same as this patch.

[jdoerrie]

Thanks for applying a fix based on my patch! I could have sworn the added tests failed locally before applying the algorithm patch, though... oh well.

include/algorithm

public:
     explicit __negate(_Predicate __p) : __p_(__p) {}
 
     template <class _T1>
     _LIBCPP_INLINE_VISIBILITY
     bool operator()(const _T1& __x) {return !__p_(__x);}
 
     template <class _T1, class _T2>
     _LIBCPP_INLINE_VISIBILITY
-    bool operator()(const _T1& __x, const _T2& __y) {return !__p_(__x, __y);}
+    bool operator()(const _T1& __x, const _T2& __y) {return __p_(__y, __x);}
 };
 
 #ifdef _LIBCPP_DEBUG
 
 template <class _Compare>
 struct __debug_less
 {
     _Compare __comp_;
__buffered_inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last,
     {
         value_type* __p = __buff;
         for (_BidirectionalIterator __i = __middle; __i != __last; __d.__incr((value_type*)0), (void) ++__i, ++__p)
             ::new(__p) value_type(_VSTD::move(*__i));
         typedef reverse_iterator<_BidirectionalIterator> _RBi;
         typedef reverse_iterator<value_type*> _Rv;
         __half_inplace_merge(_Rv(__p), _Rv(__buff),
                              _RBi(__middle), _RBi(__first),
                              _RBi(__last), __negate<_Compare>(__comp));
     }
 }
 
 template <class _Compare, class _BidirectionalIterator>
 void
 __inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last,
                 _Compare __comp, typename iterator_traits<_BidirectionalIterator>::difference_type __len1,
                                  typename iterator_traits<_BidirectionalIterator>::difference_type __len2,

test/std/algorithms/alg.sorting/alg.merge/inplace_merge_comp.pass.cpp

 
 struct indirect_less
 {
     template <class P>
     bool operator()(const P& x, const P& y)
         {return *x < *y;}
 };
 
+struct first_only
+{
+    bool operator()(const std::pair<int, int>& x, const std::pair<int, int>& y)
+    {
+        return x.first < y.first;
+    }
+};
+
 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; }
if(N > 0)
         assert(ia[0] == static_cast<int>(N)-1);
         assert(ia[N-1] == 0);
         assert(std::is_sorted(ia, ia+N, std::greater<value_type>()));
         assert(pred.count() <= (N-1));
     }
     delete [] ia;
 }
 
+void
+test_two(unsigned N, unsigned M)
+{
+    typedef std::pair<int, int> P;
+    std::vector<P> v(N);
+    unsigned mod = std::max(M, N - M);
+    for (unsigned i = 0; i < N; ++i)
+    {
+        v[i] = P(i % mod, i >= M);
+    }
+
+    std::stable_sort(v.begin(), v.begin() + M, first_only());
+    std::stable_sort(v.begin() + M, v.end(), first_only());
+    std::inplace_merge(v.begin(), v.begin() + M, v.end(), first_only());
+    assert(std::is_sorted(v.begin(), v.end()));
+}
+
 template <class Iter>
 void
 test(unsigned N)
 {
     test_one<Iter>(N, 0);
     test_one<Iter>(N, N/4);
     test_one<Iter>(N, N/2);
     test_one<Iter>(N, 3*N/4);
     test_one<Iter>(N, N);
+
+    test_two(N, 0);
+    test_two(N, N/4);
+    test_two(N, N/2);
+    test_two(N, 3*N/4);
+    test_two(N, N);
 }
 
 template <class Iter>
 void
 test()
 {
     test_one<Iter>(0, 0);
     test_one<Iter>(1, 0);
     test_one<Iter>(1, 1);
     test_one<Iter>(2, 0);
     test_one<Iter>(2, 1);
     test_one<Iter>(2, 2);
     test_one<Iter>(3, 0);
     test_one<Iter>(3, 1);
     test_one<Iter>(3, 2);
     test_one<Iter>(3, 3);
+
+    test_two(0, 0);
+    test_two(1, 0);
+    test_two(1, 1);
+    test_two(2, 0);
+    test_two(2, 1);
+    test_two(2, 2);
+    test_two(3, 0);
+    test_two(3, 1);
+    test_two(3, 2);
+    test_two(3, 3);
+
     test<Iter>(4);
     test<Iter>(20);
     test<Iter>(100);
     test<Iter>(1000);
 }
 
 int main()
 {