[libc++] [P0879] constexpr std::sort, and add new tests for it

[• Quuxplusone]

Summary

This completes libc++'s implementation of P0879 "Constexpr for swap and swap related functions."
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0879r0.html

For the feature-macro adjustment, see
https://cplusplus.github.io/LWG/issue3256

[• Quuxplusone]

libcxx/include/algorithm

3953

This comment was never correct. _Compare may be Pred&, or it may be __debug_less<Pred> without the &.

4147

I'm preserving the old code's strategy here. As I say in D92190, I'd like to change this to call _VSTD::sort(first, last, __less<void*>()) and explicitly instantiate __sort<,__less<void*>&, void*> in "libc++.a"; but I'd like to do that in a separate PR because it has ABI implications.

I also note in passing that it would be awesome if we had a way to detect contiguous iterators in C++17-and-earlier, so that we could use that, instead of special-casing T** and __wrap_iter<T*>. This is related to the use of __unwrap_iter in std::copy; whatever we do should be applied consistently in both sort and copy.

5364

In the nth_element review (D93557) I decided to constexpr-ify the algorithm itself. In this one, I decided that the simplest course of action would be to switch on is_constant_evaluated and if we're doing it at compile-time let's just do a plain old heapsort because that's already constexpr-friendly, and then we don't have to worry about making __sort itself constexpr.

So the name here might be misleading, and I'd take suggestions for better names. Here __sort_constexpr means "This algorithm is guaranteed constexpr-friendly," but it's above the switch-dispatch-thingie, whereas in e.g. __copy_constexpr it's below the switch-dispatch-thingie.

I don't want to change the name of __sort itself in this specific patch, because that would have ABI implications (some explicit template instantiations are placed in "libc++.a"). I'm excited for the prospect of ABI breakage ;) but I'd like to confine any ABI breakage to a separate PR.

[• Quuxplusone]

Add feature-macro stuff and update the CSV files.

[ldionne]

What's the status of this? Can you please rebase so CI runs (there were some CI issues during the holidays, I remember patch application failing). Ping me when this is ready for review, until then I'm marking as "changes requested".

[• Quuxplusone]

Rebase on D93557, and indicate that we're now targeting release 13.0 not 12.0.

[ldionne]

libcxx/include/algorithm

5245

I don't think we need this declaration. Isn't it the same as the definition on line 5165?

5364

If we get rid of the __unwrap_iter overload for sort(), we can simply remove __sort_constexpr and that solves the question. WDYT?

5502

In a second step, couldn't we remove this overload to replace it by calls to __unwrap_iter?

[• Quuxplusone]

libcxx/include/algorithm

5502

As of current main, no, because __unwrap_iter isn't optimized for non-trivially-copyable element types (it unwraps __wrap_iter<int*> but not __wrap_iter<string*>). If we land D94807 first, then yes.

I suppose this implies that I should make D94807 a parent of this one and prioritize it. I think I agree that that would be a much nicer overall solution than the current soup of overload sets.

[• Quuxplusone]

Temporarily upload the combined diff for D94807 (contiguous iterators) and D93661 (std::sort) together, to see what buildkite thinks of this whole idea.

[• Quuxplusone]

Rebase on main (after landing D94807)

At least on OSX, this patch has no effect on the output of nm libc++.dylib or ls -l libc++.dylib. The effect on libc++.a is that it shrinks from 7968'560 to 7968'408 bytes; the diff in nm libc++.a | sort is this, which I don't see why this should happen at all, but anyway it's not a bad thing:

 000000000001bfc0 T __ZNSt3__16locale5__impC2ERKS1_RKNS_12basic_stringIcNS_11char_traitsIcEENS_9allocatorIcEEEEi
 000000000001c6c0 T __ZNSt3__16locale5__impC1ERKS1_RKNS_12basic_stringIcNS_11char_traitsIcEENS_9allocatorIcEEEEi
 000000000001c6d0 T __ZNSt3__16locale5__impC2ERKS1_S3_i
-000000000001d188 b __ZZNSt3__117iostream_categoryEvE1s
-000000000001d190 b __ZGVZNSt3__117iostream_categoryEvE1s
-000000000001d198 b __ZZNSt3__18ios_base5iwordEiE5error
-000000000001d1a0 b __ZZNSt3__18ios_base5pwordEiE5error
-000000000001d1a8 S __ZNSt3__18ios_base9__xindex_E
+000000000001d180 b __ZZNSt3__117iostream_categoryEvE1s
+000000000001d188 b __ZGVZNSt3__117iostream_categoryEvE1s
+000000000001d190 b __ZZNSt3__18ios_base5iwordEiE5error
+000000000001d198 b __ZZNSt3__18ios_base5pwordEiE5error
+000000000001d1a0 S __ZNSt3__18ios_base9__xindex_E
 000000000001d4e8 b __ZZNSt3__115future_categoryEvE3__f
 000000000001d4f0 b __ZGVZNSt3__115future_categoryEvE3__f
 000000000001e430 T __ZNSt3__16locale5__impC1ERKS1_S3_i
 000000000001e440 T __ZNSt3__16locale5__impC2ERKS1_PNS0_5facetEl

[ldionne]

LGTM pending CI!

[danlark]

libcxx/include/algorithm

5364

One thing to think about:

Yet, std::sort does not guarantee the order of equal elements. With the current patch it may happen that constexpr std::sort and usual std::sort return different ranges because of different stability guarantees and that might be not user friendly, i.e. the property of determinism is lost.

I don't have a strong opinion on that question, however, I'd prefer constexprify this function instead of calling partial_sort

[• Quuxplusone]

libcxx/include/algorithm

5364

With the current patch it may happen that constexpr std::sort and usual std::sort return different ranges [...] i.e. the property of determinism is lost.

That's a good point I hadn't thought of: Maybe constexpr sort produces (1, 2a, 2c, 2b, 3) while runtime sort produces (1, 2b, 2a, 2c, 3). However, arguably, libc++ doesn't want to be in the business of making guarantees about sort's behavior/stability — the user should just avoid writing code that relies on those outcomes.

Vice versa, if we make the existing sort algorithm constexpr-friendly in order to make users happy, I think users would even more so want us to do it without altering any of its existing outcomes. They might object if libc++ v12.0 sort produces (1, 2b, 2a, 2c, 3) [at runtime only] while libc++ v13.0 sort produces (1, 2b, 2c, 2a, 3) [at runtime and compile-time].

[danlark]

libcxx/include/algorithm

5364

Depending on the exact values is definitely the user's problem. I don't know if sorting algorithms must be deterministic from the input data but I definitely see cases where some users might expose constant array and check for sorting equality during the runtime

Many questions and unfortunately standard does not answer them fully AFAIK. The algorithm should definitely be deterministic but does changing the evaluation context counts as input?

libcxx/include/algorithm

     constexpr ForwardIterator    // constexpr in C++20
     is_sorted_until(ForwardIterator first, ForwardIterator last);
 
 template <class ForwardIterator, class Compare>
     constexpr ForwardIterator    // constexpr in C++20
     is_sorted_until(ForwardIterator first, ForwardIterator last, Compare comp);
 
 template <class RandomAccessIterator>
-    void
+    constexpr void               // constexpr in C++20
     sort(RandomAccessIterator first, RandomAccessIterator last);
 
 template <class RandomAccessIterator, class Compare>
-    void
+    constexpr void               // constexpr in C++20
     sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
 
 template <class RandomAccessIterator>
     void
     stable_sort(RandomAccessIterator first, RandomAccessIterator last);
 
 template <class RandomAccessIterator, class Compare>
     void

         __h.release();
     }
 }
 
 template <class _Compare, class _RandomAccessIterator>
 void
 __sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
 {
-    // _Compare is known to be a reference type
     typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
     typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
     const difference_type __limit = is_trivially_copy_constructible<value_type>::value &&
                                     is_trivially_copy_assignable<value_type>::value ? 30 : 6;
     while (true)
     {
     __restart:
         difference_type __len = __last - __first;

         {
             _VSTD::__sort<_Compare>(__i+1, __last, __comp);
             // _VSTD::__sort<_Compare>(__first, __i, __comp);
             __last = __i;
         }
     }
 }
 
-// This forwarder keeps the top call and the recursive calls using the same instantiation, forcing a reference _Compare
-template <class _RandomAccessIterator, class _Compare>
+template <class _Compare, class _Tp>
 inline _LIBCPP_INLINE_VISIBILITY
 void
-sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
+__sort(_Tp** __first, _Tp** __last, __less<_Tp*>&)
 {
-    typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
-    _VSTD::__sort<_Comp_ref>(__first, __last, _Comp_ref(__comp));
-}
-
-template <class _RandomAccessIterator>
-inline _LIBCPP_INLINE_VISIBILITY
-void
-sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
-{
-    _VSTD::sort(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
-}
-
-template <class _Tp>
-inline _LIBCPP_INLINE_VISIBILITY
-void
-sort(_Tp** __first, _Tp** __last)
-{
-    _VSTD::sort((uintptr_t*)__first, (uintptr_t*)__last, __less<uintptr_t>());
-}
-
-template <class _Tp>
-inline _LIBCPP_INLINE_VISIBILITY
-void
-sort(__wrap_iter<_Tp*> __first, __wrap_iter<_Tp*> __last)
-{
-    _VSTD::sort(__first.base(), __last.base());
-}
-
-template <class _Tp, class _Compare>
-inline _LIBCPP_INLINE_VISIBILITY
-void
-sort(__wrap_iter<_Tp*> __first, __wrap_iter<_Tp*> __last, _Compare __comp)
-{
-    typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
-    _VSTD::sort<_Tp*, _Comp_ref>(__first.base(), __last.base(), __comp);
+    __less<uintptr_t> __comp;
+    _VSTD::__sort<__less<uintptr_t>&, uintptr_t*>((uintptr_t*)__first, (uintptr_t*)__last, __comp);
 }
 
 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<char>&, char*>(char*, char*, __less<char>&))
 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, __less<wchar_t>&))
 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<signed char>&, signed char*>(signed char*, signed char*, __less<signed char>&))
 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned char>&, unsigned char*>(unsigned char*, unsigned char*, __less<unsigned char>&))
 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<short>&, short*>(short*, short*, __less<short>&))
 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned short>&, unsigned short*>(unsigned short*, unsigned short*, __less<unsigned short>&))

 _RandomAccessIterator
 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>());
 }
 
+template <class _Compare, class _RandomAccessIterator>
+_LIBCPP_CONSTEXPR_AFTER_CXX17 void
+__partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last,
+             _Compare __comp);
+
 // 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

         {
             // *__first == *__m, *__first doesn't go in first part
             if (_VSTD::__nth_element_find_guard<_Compare>(__i, __j, __m, __comp)) {
                 swap(*__i, *__j);
                 ++__n_swaps;
                 // found guard for downward moving __j, now use unguarded partition
             } else if (_VSTD::__nth_element_partloop<_Compare>(__first, __last, __i, __j, __n_swaps, __comp)) {
                 return;
             } else if (__nth < __i) {
                 return;
             } else {
                 // __nth_element the second part
                 // _VSTD::__nth_element<_Compare>(__i, __nth, __last, __comp);
                 __first = __i;
                 continue;  // i.e., goto __restart
             }
         }

 template <class _RandomAccessIterator>
 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
+
+template <class _Compare, class _RandomAccessIterator>
+_LIBCPP_CONSTEXPR_AFTER_CXX17 void
+__sort_constexpr(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
+{
+    if (__libcpp_is_constant_evaluated()) {
+        _VSTD::__partial_sort<_Compare>(__first, __last, __last, __comp);
+    } else {
+        _VSTD::__sort<_Compare>(__first, __last, __comp);
+    }
+}
+
+template <class _RandomAccessIterator, class _Compare>
+inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
+void
+sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
+{
+    typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
+    _VSTD::__sort_constexpr<_Comp_ref>(__first, __last, _Comp_ref(__comp));
+}
+
+template <class _Tp, class _Compare>
+inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
+void
+sort(__wrap_iter<_Tp*> __first, __wrap_iter<_Tp*> __last, _Compare __comp)
+{
+    typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
+    _VSTD::__sort_constexpr<_Comp_ref>(__first.base(), __last.base(), _Comp_ref(__comp));
+}
+
+template <class _RandomAccessIterator>
+inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
+void
+sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
+{
+    _VSTD::sort(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
+}
+
 // includes
 
 template <class _Compare, class _InputIterator1, class _InputIterator2>
 _LIBCPP_CONSTEXPR_AFTER_CXX17 bool
 __includes(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2,
            _Compare __comp)
 {
     for (; __first2 != __last2; ++__first1)

                 *__result = *__first1;
                 ++__result;
                 ++__first1;
             }
             ++__first2;
         }
     }
     return __result;
 }
 
 template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 _OutputIterator
 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
                  _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
 {
     typedef typename __comp_ref_type<_Compare>::type _Comp_ref;

libcxx/test/std/algorithms/alg.sorting/alg.sort/sort/sort_constexpr.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
+//   sort(Iter first, Iter last);
+
+#include <algorithm>
+#include <cassert>
+
+#include "test_macros.h"
+#include "test_iterators.h"
+#include "MoveOnly.h"
+
+template<int N, class T, class Iter>
+TEST_CONSTEXPR_CXX20 bool test()
+{
+    int orig[N] = {};
+    unsigned x = 1;
+    for (int i=0; i < N; ++i) {
+        x = (x * 1664525) + 1013904223;
+        orig[i] = x % 1000;
+    }
+    T work[N] = {};
+    std::copy(orig, orig+N, work);
+    std::sort(Iter(work), Iter(work+N));
+    assert(std::is_sorted(work, work+N));
+    assert(std::is_permutation(work, work+N, orig));
+
+    return true;
+}
+
+template<int N, class T, class Iter>
+TEST_CONSTEXPR_CXX20 bool test_pointers()
+{
+    T data[N] = {};
+    T *orig[N] = {};
+    unsigned x = 1;
+    for (int i=0; i < N; ++i) {
+        orig[i] = &data[x % 258];
+    }
+    T *work[N] = {};
+    std::copy(orig, orig+N, work);
+    std::sort(Iter(work), Iter(work+N));
+    assert(std::is_sorted(work, work+N));
+    assert(std::is_permutation(work, work+N, orig));
+
+    return true;
+}
+
+int main(int, char**)
+{
+    test<7, int, int*>();
+    test<7, int, random_access_iterator<int*> >();
+    test<257, int, int*>();
+    test<257, int, random_access_iterator<int*> >();
+
+#if TEST_STD_VER >= 11
+    test<7, MoveOnly, MoveOnly*>();
+    test<7, MoveOnly, random_access_iterator<MoveOnly*> >();
+    test<257, MoveOnly, MoveOnly*>();
+    test<257, MoveOnly, random_access_iterator<MoveOnly*> >();
+#endif
+
+    test_pointers<17, char, char**>();
+    test_pointers<17, char, random_access_iterator<char**> >();
+    test_pointers<17, const char, const char**>();
+    test_pointers<17, const char, random_access_iterator<const char**> >();
+    test_pointers<17, int, int**>();
+    test_pointers<17, int, random_access_iterator<int**> >();
+
+#if TEST_STD_VER >= 20
+    static_assert(test<7, int, int*>());
+    static_assert(test<7, int, random_access_iterator<int*>>());
+    static_assert(test<257, int, int*>());
+    static_assert(test<257, int, random_access_iterator<int*>>());
+
+    static_assert(test<7, MoveOnly, MoveOnly*>());
+    static_assert(test<7, MoveOnly, random_access_iterator<MoveOnly*>>());
+    static_assert(test<257, MoveOnly, MoveOnly*>());
+    static_assert(test<257, MoveOnly, random_access_iterator<MoveOnly*>>());
+
+    static_assert(test_pointers<17, char, char**>());
+    static_assert(test_pointers<17, char, random_access_iterator<char**>>());
+    static_assert(test_pointers<17, const char, const char**>());
+    static_assert(test_pointers<17, const char, random_access_iterator<const char**>>());
+    static_assert(test_pointers<17, int, int**>());
+    static_assert(test_pointers<17, int, random_access_iterator<int**>>());
+#endif
+
+    return 0;
+}

libcxx/test/std/algorithms/alg.sorting/alg.sort/sort/sort_constexpr_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
+//   sort(Iter first, Iter last, Compare comp);
+
+#include <algorithm>
+#include <cassert>
+#include <functional>
+
+#include "test_macros.h"
+#include "test_iterators.h"
+#include "MoveOnly.h"
+
+template<int N, class T, class Iter>
+TEST_CONSTEXPR_CXX20 bool test()
+{
+    int orig[N] = {};
+    unsigned x = 1;
+    for (int i=0; i < N; ++i) {
+        x = (x * 1664525) + 1013904223;
+        orig[i] = x % 1000;
+    }
+    T work[N] = {};
+    std::copy(orig, orig+N, work);
+    std::sort(Iter(work), Iter(work+N), std::greater<T>());
+    assert(std::is_sorted(work, work+N, std::greater<T>()));
+    assert(std::is_permutation(work, work+N, orig));
+
+    return true;
+}
+
+template<int N, class T, class Iter>
+TEST_CONSTEXPR_CXX20 bool test_pointers()
+{
+    T data[N] = {};
+    T *orig[N] = {};
+    unsigned x = 1;
+    for (int i=0; i < N; ++i) {
+        orig[i] = &data[x % 258];
+    }
+    T *work[N] = {};
+    std::copy(orig, orig+N, work);
+    std::sort(Iter(work), Iter(work+N), std::greater<T*>());
+    assert(std::is_sorted(work, work+N, std::greater<T*>()));
+    assert(std::is_permutation(work, work+N, orig));
+
+    return true;
+}
+
+int main(int, char**)
+{
+    test<7, int, int*>();
+    test<7, int, random_access_iterator<int*> >();
+    test<257, int, int*>();
+    test<257, int, random_access_iterator<int*> >();
+
+#if TEST_STD_VER >= 11
+    test<7, MoveOnly, MoveOnly*>();
+    test<7, MoveOnly, random_access_iterator<MoveOnly*> >();
+    test<257, MoveOnly, MoveOnly*>();
+    test<257, MoveOnly, random_access_iterator<MoveOnly*> >();
+#endif
+
+    test_pointers<17, char, char**>();
+    test_pointers<17, char, random_access_iterator<char**> >();
+    test_pointers<17, const char, const char**>();
+    test_pointers<17, const char, random_access_iterator<const char**> >();
+    test_pointers<17, int, int**>();
+    test_pointers<17, int, random_access_iterator<int**> >();
+
+#if TEST_STD_VER >= 20
+    static_assert(test<7, int, int*>());
+    static_assert(test<7, int, random_access_iterator<int*>>());
+    static_assert(test<257, int, int*>());
+    static_assert(test<257, int, random_access_iterator<int*>>());
+
+    static_assert(test<7, MoveOnly, MoveOnly*>());
+    static_assert(test<7, MoveOnly, random_access_iterator<MoveOnly*>>());
+    static_assert(test<257, MoveOnly, MoveOnly*>());
+    static_assert(test<257, MoveOnly, random_access_iterator<MoveOnly*>>());
+
+    static_assert(test_pointers<17, char, char**>());
+    static_assert(test_pointers<17, char, random_access_iterator<char**>>());
+    static_assert(test_pointers<17, const char, const char**>());
+    static_assert(test_pointers<17, const char, random_access_iterator<const char**>>());
+    static_assert(test_pointers<17, int, int**>());
+    static_assert(test_pointers<17, int, random_access_iterator<int**>>());
+#endif
+
+    return 0;
+}