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

[• Quuxplusone]

Summary

This patch is more than just adding the constexpr keyword, because the old code relied on goto, and goto is not constexpr-friendly. Refactor to eliminate goto, and then mark it as constexpr in C++20.

I freely admit that the name __nth_element_partloop is bad; I couldn't find any better name because I don't really know what this loop is doing, conceptually. Vice versa, I think __nth_element_find_guard has a decent name.

Now the only one we're still missing from P0879 is sort.

[ldionne]

Can you please ping me once CI passes?

libcxx/include/algorithm

5281

This comment is anchored to something that doesn't exist anymore, so I would remove it.

[• Quuxplusone]

libcxx/include/algorithm

5281

You mean you'd remove // i.e., goto __restart? I prefer to leave it, for the same reason we leave the existing comments like // _VSTD::__nth_element<_Compare>(__i, __nth, __last, __comp) — they show what we would put on that line if it weren't troublesome for mechanical reasons (don't want recursion, can't use goto). I left a comment above: // __restart: -- this is the target of a "continue" below

I'm very much not a fan of using continue for non-trivial control flow, anyway. But I'll take another look at this code and see if I can maybe figure out a way to eliminate the continue. For example, we could definitely just indent lines 5284–5362 one more level and stuff them into an else block.

[• Quuxplusone]

Add "simple" tests per @ldionne's preferences. :)
I looked at ways to remove that continue; and realized that the thing I was thinking of wouldn't work. (The section I was saying I could put in an else block, would actually have to go in a separate helper function so that it could be reached along two different codepaths.) So I'd say let's ship this as-is, and let someone else refactor it if they want to.

[• Quuxplusone]

Rebase and poke buildkite.

[ldionne]

LGTM. CI is passing due to the extern-templates.sh.cpp test, which I broke. Go ahead.

libcxx/include/algorithm

5284

Would it make sense to replace this by a variant of std::find_if? I'd do any other refactoring in a separate patch, though, to keep this one purely mechanical.

[rupprecht]

It looks like this is generating incorrect results. I uploaded D96074 which shows the failing test case.

Mind if I revert first, and the fix forward (with the added test case, plus probably some more) can land later?

[• Quuxplusone]

@rupprecht: Uh-oh. :( Your suggestion to revert D93557 SGTM. It looks like it should revert cleanly.

[rupprecht]

Reverted, thanks!

When I was reducing a test case, one thing I noticed was the problem only happens for certain pivot values, e.g.:

int main() {
  std::vector<int> v = {
      0, 1, 2, 3, 4, 5, 7, 6,
  };

  for (int i = 0; i < v.size(); ++i) {
    std::vector<int> v2 = v;

    auto pivot = v2.begin() + i;
    std::nth_element(v2.begin(), pivot, v2.end());

    for (auto it = v2.begin(); it != pivot; ++it)
      if (*it > *pivot)
        std::cerr << "Bad result with pivot " << i << "\n";
    for (auto it = std::next(pivot); it != v2.end(); ++it)
      if (*pivot > *it)
        std::cerr << "Bad result with pivot " << i << "\n";
  }
}

$ clang++ /tmp/nth.cpp -stdlib=libc++ && ./a.out
Bad result with pivot 6
Bad result with pivot 7

The existing test case operates on {3,1,4,1,5, 9,2,6,5,3, 5,8,9,7,9}, which has multiple 1s and multiple 9s, so if the bug is something about incorrectly handling a pivot point at the end or right next to the end (or vice versa for the beginning), then the bug would be masked because the value would be the same in those instances. (e.g. std::nth_element of the last element is 9, but so is std::nth_element of the last - 1 element). So maybe it would be good to also include a test case that has only unique values to avoid that case. (Including a case with equal values is good too, so don't remove that test case).

[• Quuxplusone]

libcxx/include/algorithm

5466

This was the bug. while (++__j != __last) should have changed to while (true), if I was going to repeat the condition here.
However, I've got a better patch now anyway, which I'm posting as D96084.

libcxx/include/algorithm

partial_sort_copy(InputIterator first, InputIterator last,
                       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
is_sorted(_ForwardIterator __first, _ForwardIterator __last)
     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
if (__c(*__x5, *__x4))
             }
         }
     }
     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);

 partial_sort_copy(_InputIterator __first, _InputIterator __last,
                   _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>
-void
+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 (--__j != __i)
+    {
+        if (__comp(*__j, *__m))
+        {
+            return true;
+        }
+    }
+    return false;
+}
+
+template<class _Compare, class _RandomAccessIterator>
+_LIBCPP_CONSTEXPR_AFTER_CXX11 bool
+__nth_element_partloop(_RandomAccessIterator __first, _RandomAccessIterator __last,
+                       _RandomAccessIterator& __i, _RandomAccessIterator& __j,
+                       unsigned& __n_swaps, _Compare __comp)
+{
+    // *__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 true;  // [__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 true;
+    while (true)
+    {
+        while (!__comp(*__first, *__i))
+            ++__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.
+    return false;
+}
+
+template <class _Compare, class _RandomAccessIterator>
+_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:
+        // __restart: -- this is the target of a "continue" below
         if (__nth == __last)
             return;
         difference_type __len = __last - __first;
         switch (__len)
         {
         case 0:
         case 1:
             return;
while (true)
         _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))
-                            ++__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))
-                {
-                    swap(*__i, *__j);
-                    ++__n_swaps;
-                    break;  // found guard for downward moving __j, now use unguarded partition
-                }
+            if (_VSTD::__nth_element_find_guard<_Compare>(__i, __j, __m, __comp)) {
+                // found guard for downward moving __j, now use unguarded partition
+            } else if (_VSTD::__nth_element_partloop<_Compare>(__first, __last, __i, __j, __n_swaps, __comp)) {
+            } else if (__nth < __i) {
+            } else {
+                continue;  // i.e., goto __restart
             }
         }
         ++__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
while (true)
             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)
+                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 (++__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>());
 }
 
 // includes
 

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;
-
-void
-test_one(int N, int M)
+template<class T, class Iter>
+TEST_CONSTEXPR_CXX20 bool test()
 {
-    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;
+    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(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[] = {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);
+    }
+    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;}
-};
-
-std::mt19937 randomness;
-
-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;
+    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);
+        }
     }
 
-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[] = {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);
+    }
+    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;
 }