Revert "Revert "[libc++] [P0879] constexpr std::nth_element, and rewrite its tests.""

[• Quuxplusone]

Summary

The bug is now fixed (it was a stupid cut-and-paste kind of error), and the regression test added.
The new patch is also simpler than the old one!

This is an updated version of D93557.

Subsumes D96074.

[ldionne]

Simple "manual" tests can also pay off :-) Thanks for fixing quickly.

[• Quuxplusone]

Simple "manual" tests can also pay off :-)

Well, actually, before landing this I thought I'd better run some more randomized tests... and I found that this patch also has a bug somewhere! Reduced from the randomized tests:

std::vector<int> v2 = { 18, -7, 1, -9, 3, 13, -10, -10, -9, 4, -10, 5, 8, 6, 11, -10, 19 };
std::nth_element(v2.begin(), v2.begin() + 10, v2.end());
assert(std::all_of(v2.begin(), v2.begin() + 10, [&](int x){ return x <= v2[10]; }));
assert(std::all_of(v2.begin() + 10, v2.end(), [&](int x){ return x >= v2[10]; }));  // fails!

So I'm still working on this.

...EDIT: wait, no, maybe I messed up and this fails using the old version but not the new version. Blech. Anyway, if I land this today it'll be after convincing myself that it passes randomized tests too.

[rupprecht]

FWIW, I applied this patch and was able to make it pass this pretty exhaustive test:

  {
  constexpr int kMaxLen = 64;
  for (int len = 1; len < kMaxLen; ++len) {
    int v[kMaxLen];
    for (int i = 0; i < len; ++i)
      v[i] = i;
    T v2[kMaxLen];
    std::copy(v, v + len, v2);
    do {
      for (int n = 0; n < len; ++n) {
        for (int m = 0; m < n; ++m) {
          std::nth_element(Iter(v2), Iter(v2 + m), Iter(v2 + n),
                           std::greater<T>());
          assert(std::is_permutation(v2, v2 + len, v));
          // No element to m's left is less than m.
          for (int i = 0; i < m; ++i) {
            assert(!(v2[i] < v2[m]));
          }
          // No element to m's right is greater than m.
          for (int i = m; i < n; ++i) {
            assert(!(v2[i] > v2[m]));
          }
        }
      }
    } while (std::next_permutation(Iter(v2), Iter(v2 + len)));
  }
}

[• Quuxplusone]

In D96084#2545452, @rupprecht wrote:

FWIW, I applied this patch and was able to make it pass this pretty exhaustive test: [...]

@rupprecht: I'm looking at adding a similar test to the libc++ test suite, but, I don't really understand what this test is doing. You're running nth_element repeatedly on the same array with increasing m and n, which is kind of a selection sort on the first len-1 elements? And then next_permutation takes it from 4 3 2 1 0 5 to 4 3 2 1 5 0 and we selection-sort the first n-1 elements again to get 5 4 3 2 1 0, and then the second next_permutation kicks us out to increment len?
I thought maybe you were going for the "try all permutations of 64 elements" exhaustive test, but that would take 64! iterations which is heat-death-of-the-universe territory.
Is there a subtle logic to the particular sequence your test is actually doing?

libcxx/include/algorithm

                       RandomAccessIterator result_first, RandomAccessIterator result_last);
 
 template <class InputIterator, class RandomAccessIterator, class Compare>
     constexpr RandomAccessIterator    // constexpr in C++20
     partial_sort_copy(InputIterator first, InputIterator last,
                       RandomAccessIterator result_first, RandomAccessIterator result_last, Compare comp);
 
 template <class RandomAccessIterator>
-    void
+    constexpr void                    // constexpr in C++20
     nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last);
 
 template <class RandomAccessIterator, class Compare>
-    void
+    constexpr void                    // constexpr in C++20
     nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, Compare comp);
 
 template <class ForwardIterator, class T>
     constexpr ForwardIterator                         // constexpr in C++20
     lower_bound(ForwardIterator first, ForwardIterator last, const T& value);
 
 template <class ForwardIterator, class T, class Compare>
     constexpr ForwardIterator                         // constexpr in C++20

     return _VSTD::is_sorted(__first, __last, __less<typename iterator_traits<_ForwardIterator>::value_type>());
 }
 
 // sort
 
 // stable, 2-3 compares, 0-2 swaps
 
 template <class _Compare, class _ForwardIterator>
-unsigned
+_LIBCPP_CONSTEXPR_AFTER_CXX11 unsigned
 __sort3(_ForwardIterator __x, _ForwardIterator __y, _ForwardIterator __z, _Compare __c)
 {
     unsigned __r = 0;
     if (!__c(*__y, *__x))          // if x <= y
     {
         if (!__c(*__z, *__y))      // if y <= z
             return __r;            // x <= y && y <= z
                                    // x <= y && y > z

             }
         }
     }
     return __r;
 }
 
 // Assumes size > 0
 template <class _Compare, class _BidirectionalIterator>
-void
+_LIBCPP_CONSTEXPR_AFTER_CXX11 void
 __selection_sort(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
 {
     _BidirectionalIterator __lm1 = __last;
     for (--__lm1; __first != __lm1; ++__first)
     {
         _BidirectionalIterator __i = _VSTD::min_element<_BidirectionalIterator,
                                                         typename add_lvalue_reference<_Compare>::type>
                                                        (__first, __last, __comp);

                   _RandomAccessIterator __result_first, _RandomAccessIterator __result_last)
 {
     return _VSTD::partial_sort_copy(__first, __last, __result_first, __result_last,
                                    __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
 }
 
 // nth_element
 
+template<class _Compare, class _RandomAccessIterator>
+_LIBCPP_CONSTEXPR_AFTER_CXX11 bool
+__nth_element_find_guard(_RandomAccessIterator& __i, _RandomAccessIterator& __j,
+                         _RandomAccessIterator __m, _Compare __comp)
+{
+    // manually guard downward moving __j against __i
+    while (true) {
+        if (__i == --__j) {
+            return false;
+        }
+        if (__comp(*__j, *__m)) {
+            return true;  // found guard for downward moving __j, now use unguarded partition
+        }
+    }
+}
+
 template <class _Compare, class _RandomAccessIterator>
-void
+_LIBCPP_CONSTEXPR_AFTER_CXX11 void
 __nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last, _Compare __comp)
 {
     // _Compare is known to be a reference type
     typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
     const difference_type __limit = 7;
     while (true)
     {
-    __restart:
         if (__nth == __last)
             return;
         difference_type __len = __last - __first;
         switch (__len)
         {
         case 0:
         case 1:
             return;

         _RandomAccessIterator __i = __first;
         _RandomAccessIterator __j = __lm1;
         // j points beyond range to be tested, *__lm1 is known to be <= *__m
         // The search going up is known to be guarded but the search coming down isn't.
         // Prime the downward search with a guard.
         if (!__comp(*__i, *__m))  // if *__first == *__m
         {
             // *__first == *__m, *__first doesn't go in first part
-            // manually guard downward moving __j against __i
-            while (true)
-            {
-                if (__i == --__j)
-                {
-                    // *__first == *__m, *__m <= all other elements
-                    // Partition instead into [__first, __i) == *__first and *__first < [__i, __last)
-                    ++__i;  // __first + 1
-                    __j = __last;
-                    if (!__comp(*__first, *--__j))  // we need a guard if *__first == *(__last-1)
-                    {
-                        while (true)
-                        {
-                            if (__i == __j)
-                                return;  // [__first, __last) all equivalent elements
-                            if (__comp(*__first, *__i))
-                            {
-                                swap(*__i, *__j);
-                                ++__n_swaps;
-                                ++__i;
-                                break;
-                            }
-                            ++__i;
-                        }
-                    }
-                    // [__first, __i) == *__first and *__first < [__j, __last) and __j == __last - 1
-                    if (__i == __j)
-                        return;
-                    while (true)
-                    {
-                        while (!__comp(*__first, *__i))
+            if (_VSTD::__nth_element_find_guard<_Compare>(__i, __j, __m, __comp)) {
+                swap(*__i, *__j);
+                ++__n_swaps;
+            } else {
+                // *__first == *__m, *__m <= all other elements
+                // Partition instead into [__first, __i) == *__first and *__first < [__i, __last)
+                ++__i;  // __first + 1
+                __j = __last;
+                if (!__comp(*__first, *--__j)) {  // we need a guard if *__first == *(__last-1)
+                    while (true) {
+                        if (__i == __j) {
+                            return;  // [__first, __last) all equivalent elements
+                        } else if (__comp(*__first, *__i)) {
+                            swap(*__i, *__j);
+                            ++__n_swaps;
                             ++__i;
-                        while (__comp(*__first, *--__j))
-                            ;
-                        if (__i >= __j)
                             break;
-                        swap(*__i, *__j);
-                        ++__n_swaps;
+                        }
                         ++__i;
                     }
-                    // [__first, __i) == *__first and *__first < [__i, __last)
-                    // The first part is sorted,
-                    if (__nth < __i)
-                        return;
-                    // __nth_element the second part
-                    // _VSTD::__nth_element<_Compare>(__i, __nth, __last, __comp);
-                    __first = __i;
-                    goto __restart;
                 }
-                if (__comp(*__j, *__m))
-                {
+                // [__first, __i) == *__first and *__first < [__j, __last) and __j == __last - 1
+                if (__i == __j) {
+                    return;
+                }
+                while (true) {
+                    while (!__comp(*__first, *__i))
+                        ++__i;
+                    while (__comp(*__first, *--__j))
+                        ;
+                    if (__i >= __j)
+                        break;
                     swap(*__i, *__j);
                     ++__n_swaps;
-                    break;  // found guard for downward moving __j, now use unguarded partition
+                    ++__i;
                 }
+                // [__first, __i) == *__first and *__first < [__i, __last)
+                // The first part is sorted,
+                if (__nth < __i) {
+                    return;
+                }
+                // __nth_element the second part
+                // _VSTD::__nth_element<_Compare>(__i, __nth, __last, __comp);
+                __first = __i;
+                continue;
             }
         }
         ++__i;
         // j points beyond range to be tested, *__lm1 is known to be <= *__m
         // if not yet partitioned...
         if (__i < __j)
         {
             // known that *(__i - 1) < *__m

             return;
         if (__n_swaps == 0)
         {
             // We were given a perfectly partitioned sequence.  Coincidence?
             if (__nth < __i)
             {
                 // Check for [__first, __i) already sorted
                 __j = __m = __first;
-                while (++__j != __i)
-                {
-                    if (__comp(*__j, *__m))
+                while (true) {
+                    if (++__j == __i) {
+                        // [__first, __i) sorted
+                        return;
+                    }
+                    if (__comp(*__j, *__m)) {
                         // not yet sorted, so sort
-                        goto not_sorted;
+                        break;
+                    }
                     __m = __j;
                 }
-                // [__first, __i) sorted
-                return;
             }
             else
             {
                 // Check for [__i, __last) already sorted
                 __j = __m = __i;
-                while (++__j != __last)
-                {
-                    if (__comp(*__j, *__m))
+                while (true) {
+                    if (++__j == __last) {
+                        // [__i, __last) sorted
+                        return;
+                    }
+                    if (__comp(*__j, *__m)) {
                         // not yet sorted, so sort
-                        goto not_sorted;
+                        break;
+                    }
                     __m = __j;
                 }
-                // [__i, __last) sorted
-                return;
             }
         }
-not_sorted:
         // __nth_element on range containing __nth
         if (__nth < __i)
         {
             // _VSTD::__nth_element<_Compare>(__first, __nth, __i, __comp);
             __last = __i;
         }
         else
         {
             // _VSTD::__nth_element<_Compare>(__i+1, __nth, __last, __comp);
             __first = ++__i;
         }
     }
 }
 
 template <class _RandomAccessIterator, class _Compare>
-inline _LIBCPP_INLINE_VISIBILITY
+inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 void
 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last, _Compare __comp)
 {
     typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
     _VSTD::__nth_element<_Comp_ref>(__first, __nth, __last, __comp);
 }
 
 template <class _RandomAccessIterator>
-inline _LIBCPP_INLINE_VISIBILITY
+inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 void
 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last)
 {
     _VSTD::nth_element(__first, __nth, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
 }
 
 // sort
 

libcxx/test/std/algorithms/alg.sorting/alg.nth.element/nth_element.pass.cpp

 //===----------------------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 // <algorithm>
 
 // template<RandomAccessIterator Iter>
-//   requires ShuffleIterator<Iter>
-//         && LessThanComparable<Iter::value_type>
-//   void
+//   requires ShuffleIterator<Iter> && LessThanComparable<Iter::value_type>
+//   constexpr void  // constexpr in C++20
 //   nth_element(Iter first, Iter nth, Iter last);
 
 #include <algorithm>
-#include <random>
 #include <cassert>
 
 #include "test_macros.h"
+#include "test_iterators.h"
+#include "MoveOnly.h"
 
-std::mt19937 randomness;
+template<class T, class Iter>
+TEST_CONSTEXPR_CXX20 bool test()
+{
+    int orig[15] = {3,1,4,1,5, 9,2,6,5,3, 5,8,9,7,9};
+    T work[15] = {3,1,4,1,5, 9,2,6,5,3, 5,8,9,7,9};
+    for (int n = 0; n < 15; ++n) {
+        for (int m = 0; m < n; ++m) {
+            std::nth_element(Iter(work), Iter(work+m), Iter(work+n));
+            assert(std::is_permutation(work, work+n, orig));
+            // No element to m's left is greater than m.
+            for (int i = 0; i < m; ++i) {
+                assert(!(work[i] > work[m]));
+            }
+            // No element to m's right is less than m.
+            for (int i = m; i < n; ++i) {
+                assert(!(work[i] < work[m]));
+            }
+            std::copy(orig, orig+15, work);
+        }
+    }
 
-void
-test_one(int N, int M)
     {
-    assert(N != 0);
-    assert(M < N);
-    int* array = new int[N];
-    for (int i = 0; i < N; ++i)
-        array[i] = i;
-    std::shuffle(array, array+N, randomness);
-    std::nth_element(array, array+M, array+N);
-    assert(array[M] == M);
-    std::nth_element(array, array+N, array+N); // begin, end, end
-    delete [] array;
+        T input[] = {3,1,4,1,5,9,2};
+        std::nth_element(Iter(input), Iter(input+4), Iter(input+7));
+        assert(input[4] == 4);
+        assert(input[5] + input[6] == 5 + 9);
     }
 
-void
-test(int N)
     {
-    test_one(N, 0);
-    test_one(N, 1);
-    test_one(N, 2);
-    test_one(N, 3);
-    test_one(N, N/2-1);
-    test_one(N, N/2);
-    test_one(N, N/2+1);
-    test_one(N, N-3);
-    test_one(N, N-2);
-    test_one(N, N-1);
+        T input[] = {0, 1, 2, 3, 4, 5, 7, 6};
+        std::nth_element(Iter(input), Iter(input + 6), Iter(input + 8));
+        assert(input[6] == 6);
+        assert(input[7] == 7);
+    }
+
+    {
+        T input[] = {1, 0, 2, 3, 4, 5, 6, 7};
+        std::nth_element(Iter(input), Iter(input + 1), Iter(input + 8));
+        assert(input[0] == 0);
+        assert(input[1] == 1);
+    }
+
+    return true;
 }
 
 int main(int, char**)
 {
-    int d = 0;
-    std::nth_element(&d, &d, &d);
-    assert(d == 0);
-    test(256);
-    test(257);
-    test(499);
-    test(500);
-    test(997);
-    test(1000);
-    test(1009);
+    test<int, random_access_iterator<int*> >();
+    test<int, int*>();
+
+#if TEST_STD_VER >= 11
+    test<MoveOnly, random_access_iterator<MoveOnly*>>();
+    test<MoveOnly, MoveOnly*>();
+#endif
+
+#if TEST_STD_VER >= 20
+    static_assert(test<int, random_access_iterator<int*>>());
+    static_assert(test<int, int*>());
+    static_assert(test<MoveOnly, random_access_iterator<MoveOnly*>>());
+    static_assert(test<MoveOnly, MoveOnly*>());
+#endif
 
     return 0;
 }

libcxx/test/std/algorithms/alg.sorting/alg.nth.element/nth_element_comp.pass.cpp

 //===----------------------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 // <algorithm>
 
 // template<RandomAccessIterator Iter, StrictWeakOrder<auto, Iter::value_type> Compare>
-//   requires ShuffleIterator<Iter>
-//         && CopyConstructible<Compare>
-//   void
+//   requires ShuffleIterator<Iter> && CopyConstructible<Compare>
+//   constexpr void  // constexpr in C++20
 //   nth_element(Iter first, Iter nth, Iter last, Compare comp);
 
 #include <algorithm>
-#include <functional>
-#include <vector>
-#include <random>
 #include <cassert>
-#include <cstddef>
-#include <memory>
+#include <functional>
 
 #include "test_macros.h"
+#include "test_iterators.h"
+#include "MoveOnly.h"
 
-struct indirect_less
+template<class T, class Iter>
+TEST_CONSTEXPR_CXX20 bool test()
 {
-    template <class P>
-    bool operator()(const P& x, const P& y)
-        {return *x < *y;}
-};
+    int orig[15] = {3,1,4,1,5, 9,2,6,5,3, 5,8,9,7,9};
+    T work[15] = {3,1,4,1,5, 9,2,6,5,3, 5,8,9,7,9};
+    for (int n = 0; n < 15; ++n) {
+        for (int m = 0; m < n; ++m) {
+            std::nth_element(Iter(work), Iter(work+m), Iter(work+n), std::greater<T>());
+            assert(std::is_permutation(work, work+n, orig));
+            // No element to m's left is less than m.
+            for (int i = 0; i < m; ++i) {
+                assert(!(work[i] < work[m]));
+            }
+            // No element to m's right is greater than m.
+            for (int i = m; i < n; ++i) {
+                assert(!(work[i] > work[m]));
+            }
+            std::copy(orig, orig+15, work);
+        }
+    }
 
-std::mt19937 randomness;
+    {
+        T input[] = {3,1,4,1,5,9,2};
+        std::nth_element(Iter(input), Iter(input+4), Iter(input+7), std::greater<T>());
+        assert(input[4] == 2);
+        assert(input[5] + input[6] == 1 + 1);
+    }
 
-void
-test_one(int N, int M)
     {
-    assert(N != 0);
-    assert(M < N);
-    int* array = new int[N];
-    for (int i = 0; i < N; ++i)
-        array[i] = i;
-    std::shuffle(array, array+N, randomness);
-    std::nth_element(array, array+M, array+N, std::greater<int>());
-    assert(array[M] == N-M-1);
-    std::nth_element(array, array+N, array+N, std::greater<int>()); // begin, end, end
-    delete [] array;
+        T input[] = {0, 1, 2, 3, 4, 5, 7, 6};
+        std::nth_element(Iter(input), Iter(input + 6), Iter(input + 8), std::greater<T>());
+        assert(input[6] == 1);
+        assert(input[7] == 0);
     }
 
-void
-test(int N)
     {
-    test_one(N, 0);
-    test_one(N, 1);
-    test_one(N, 2);
-    test_one(N, 3);
-    test_one(N, N/2-1);
-    test_one(N, N/2);
-    test_one(N, N/2+1);
-    test_one(N, N-3);
-    test_one(N, N-2);
-    test_one(N, N-1);
+        T input[] = {1, 0, 2, 3, 4, 5, 6, 7};
+        std::nth_element(Iter(input), Iter(input + 1), Iter(input + 8), std::greater<T>());
+        assert(input[0] == 7);
+        assert(input[1] == 6);
+    }
+
+    return true;
 }
 
 int main(int, char**)
 {
-    int d = 0;
-    std::nth_element(&d, &d, &d);
-    assert(d == 0);
-    test(256);
-    test(257);
-    test(499);
-    test(500);
-    test(997);
-    test(1000);
-    test(1009);
+    test<int, random_access_iterator<int*> >();
+    test<int, int*>();
 
 #if TEST_STD_VER >= 11
-    {
-    std::vector<std::unique_ptr<int> > v(1000);
-    for (int i = 0; static_cast<std::size_t>(i) < v.size(); ++i)
-        v[i].reset(new int(i));
-    std::nth_element(v.begin(), v.begin() + v.size()/2, v.end(), indirect_less());
-    assert(static_cast<std::size_t>(*v[v.size()/2]) == v.size()/2);
-    }
+    test<MoveOnly, random_access_iterator<MoveOnly*>>();
+    test<MoveOnly, MoveOnly*>();
+#endif
+
+#if TEST_STD_VER >= 20
+    static_assert(test<int, random_access_iterator<int*>>());
+    static_assert(test<int, int*>());
+    static_assert(test<MoveOnly, random_access_iterator<MoveOnly*>>());
+    static_assert(test<MoveOnly, MoveOnly*>());
 #endif
 
     return 0;
 }