[libc++] [P0879] constexpr reverse, partition, *_permutation

[• Quuxplusone]

Summary

After this patch, the only parts of P0879 that remain missing will be std::nth_element, std::sort, and the heap/partial_sort algorithms.
std::sort may be interesting, I'm not sure yet. The others are all trivial except that their existing tests use std::shuffle which is not constexpr-friendly, so I will rewrite those tests in a separate PR.

[• Quuxplusone]

The buildbot was indeed happy. Remove the *_heap algorithms (in preparation for their separate PR). This is now ready for landing AFAIC.

[• Quuxplusone]

Rebased on main. @ldionne ping!

libcxx/include/algorithm

template <class InputIterator, class OutputIterator>
     constexpr OutputIterator     // constexpr in C++20
     unique_copy(InputIterator first, InputIterator last, OutputIterator result);
 
 template <class InputIterator, class OutputIterator, class BinaryPredicate>
     constexpr OutputIterator     // constexpr in C++20
     unique_copy(InputIterator first, InputIterator last, OutputIterator result, BinaryPredicate pred);
 
 template <class BidirectionalIterator>
-    void
+    constexpr void               // constexpr in C++20
     reverse(BidirectionalIterator first, BidirectionalIterator last);
 
 template <class BidirectionalIterator, class OutputIterator>
     constexpr OutputIterator       // constexpr in C++20
     reverse_copy(BidirectionalIterator first, BidirectionalIterator last, OutputIterator result);
 
 template <class ForwardIterator>
     constexpr ForwardIterator      // constexpr in C++20
constexpr ForwardIterator
     shift_right(ForwardIterator first, ForwardIterator last,
                 typename iterator_traits<ForwardIterator>::difference_type n); // C++20
 
 template <class InputIterator, class Predicate>
     constexpr bool  // constexpr in C++20
     is_partitioned(InputIterator first, InputIterator last, Predicate pred);
 
 template <class ForwardIterator, class Predicate>
-    ForwardIterator
+    constexpr ForwardIterator  // constexpr in C++20
     partition(ForwardIterator first, ForwardIterator last, Predicate pred);
 
 template <class InputIterator, class OutputIterator1,
           class OutputIterator2, class Predicate>
     constexpr pair<OutputIterator1, OutputIterator2>   // constexpr in C++20
     partition_copy(InputIterator first, InputIterator last,
                    OutputIterator1 out_true, OutputIterator2 out_false,
                    Predicate pred);
template <class InputIterator1, class InputIterator2>
     lexicographical_compare(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2);
 
 template <class InputIterator1, class InputIterator2, class Compare>
     constexpr bool     // constexpr in C++20
     lexicographical_compare(InputIterator1 first1, InputIterator1 last1,
                             InputIterator2 first2, InputIterator2 last2, Compare comp);
 
 template <class BidirectionalIterator>
-    bool
+    constexpr bool     // constexpr in C++20
     next_permutation(BidirectionalIterator first, BidirectionalIterator last);
 
 template <class BidirectionalIterator, class Compare>
-    bool
+    constexpr bool     // constexpr in C++20
     next_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp);
 
 template <class BidirectionalIterator>
-    bool
+    constexpr bool     // constexpr in C++20
     prev_permutation(BidirectionalIterator first, BidirectionalIterator last);
 
 template <class BidirectionalIterator, class Compare>
-    bool
+    constexpr bool     // constexpr in C++20
     prev_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp);
 
 }  // std
 
 */
 
 #include <__config>
 #include <initializer_list>

 {
     typedef typename iterator_traits<_InputIterator>::value_type __v;
     return _VSTD::unique_copy(__first, __last, __result, __equal_to<__v>());
 }
 
 // reverse
 
 template <class _BidirectionalIterator>
-inline _LIBCPP_INLINE_VISIBILITY
+inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 void
 __reverse(_BidirectionalIterator __first, _BidirectionalIterator __last, bidirectional_iterator_tag)
 {
     while (__first != __last)
     {
         if (__first == --__last)
             break;
         _VSTD::iter_swap(__first, __last);
         ++__first;
     }
 }
 
 template <class _RandomAccessIterator>
-inline _LIBCPP_INLINE_VISIBILITY
+inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 void
 __reverse(_RandomAccessIterator __first, _RandomAccessIterator __last, random_access_iterator_tag)
 {
     if (__first != __last)
         for (; __first < --__last; ++__first)
             _VSTD::iter_swap(__first, __last);
 }
 
 template <class _BidirectionalIterator>
-inline _LIBCPP_INLINE_VISIBILITY
+inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 void
 reverse(_BidirectionalIterator __first, _BidirectionalIterator __last)
 {
     _VSTD::__reverse(__first, __last, typename iterator_traits<_BidirectionalIterator>::iterator_category());
 }
 
 // reverse_copy
 
for (; __first != __last; ++__first)
         if (__pred(*__first))
             return false;
     return true;
 }
 
 // partition
 
 template <class _Predicate, class _ForwardIterator>
-_ForwardIterator
+_LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator
 __partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, forward_iterator_tag)
 {
     while (true)
     {
         if (__first == __last)
             return __first;
         if (!__pred(*__first))
             break;
         ++__first;
     }
     for (_ForwardIterator __p = __first; ++__p != __last;)
     {
         if (__pred(*__p))
         {
             swap(*__first, *__p);
             ++__first;
         }
     }
     return __first;
 }
 
 template <class _Predicate, class _BidirectionalIterator>
-_BidirectionalIterator
+_LIBCPP_CONSTEXPR_AFTER_CXX17 _BidirectionalIterator
 __partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred,
             bidirectional_iterator_tag)
 {
     while (true)
     {
         while (true)
         {
             if (__first == __last)
                 return __first;
             if (!__pred(*__first))
                 break;
             ++__first;
         }
         do
         {
             if (__first == --__last)
                 return __first;
         } while (!__pred(*__last));
         swap(*__first, *__last);
         ++__first;
     }
 }
 
 template <class _ForwardIterator, class _Predicate>
-inline _LIBCPP_INLINE_VISIBILITY
+inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 _ForwardIterator
 partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
 {
     return _VSTD::__partition<typename add_lvalue_reference<_Predicate>::type>
                             (__first, __last, __pred, typename iterator_traits<_ForwardIterator>::iterator_category());
 }
 
 // partition_copy
lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1,
     return _VSTD::lexicographical_compare(__first1, __last1, __first2, __last2,
                                          __less<typename iterator_traits<_InputIterator1>::value_type,
                                                 typename iterator_traits<_InputIterator2>::value_type>());
 }
 
 // next_permutation
 
 template <class _Compare, class _BidirectionalIterator>
-bool
+_LIBCPP_CONSTEXPR_AFTER_CXX17 bool
 __next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
 {
     _BidirectionalIterator __i = __last;
     if (__first == __last || __first == --__i)
         return false;
     while (true)
     {
         _BidirectionalIterator __ip1 = __i;
while (true)
         {
             _VSTD::reverse(__first, __last);
             return false;
         }
     }
 }
 
 template <class _BidirectionalIterator, class _Compare>
-inline _LIBCPP_INLINE_VISIBILITY
+inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 bool
 next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
 {
     typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
     return _VSTD::__next_permutation<_Comp_ref>(__first, __last, __comp);
 }
 
 template <class _BidirectionalIterator>
-inline _LIBCPP_INLINE_VISIBILITY
+inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 bool
 next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last)
 {
     return _VSTD::next_permutation(__first, __last,
                                   __less<typename iterator_traits<_BidirectionalIterator>::value_type>());
 }
 
 // prev_permutation
 
 template <class _Compare, class _BidirectionalIterator>
-bool
+_LIBCPP_CONSTEXPR_AFTER_CXX17 bool
 __prev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
 {
     _BidirectionalIterator __i = __last;
     if (__first == __last || __first == --__i)
         return false;
     while (true)
     {
         _BidirectionalIterator __ip1 = __i;
while (true)
         {
             _VSTD::reverse(__first, __last);
             return false;
         }
     }
 }
 
 template <class _BidirectionalIterator, class _Compare>
-inline _LIBCPP_INLINE_VISIBILITY
+inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 bool
 prev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
 {
     typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
     return _VSTD::__prev_permutation<_Comp_ref>(__first, __last, __comp);
 }
 
 template <class _BidirectionalIterator>
-inline _LIBCPP_INLINE_VISIBILITY
+inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 bool
 prev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last)
 {
     return _VSTD::prev_permutation(__first, __last,
                                   __less<typename iterator_traits<_BidirectionalIterator>::value_type>());
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 _LIBCPP_POP_MACROS
 
 #if defined(_LIBCPP_HAS_PARALLEL_ALGORITHMS) && _LIBCPP_STD_VER >= 17
 #   include <__pstl_algorithm>
 #endif
 
 #endif  // _LIBCPP_ALGORITHM

libcxx/test/std/algorithms/alg.modifying.operations/alg.partitions/partition.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<BidirectionalIterator Iter, Predicate<auto, Iter::value_type> Pred>
 //   requires ShuffleIterator<Iter>
 //         && CopyConstructible<Pred>
-//   Iter
+//   constexpr Iter  // constexpr in C++20
 //   partition(Iter first, Iter last, Pred pred);
 
 #include <algorithm>
 #include <cassert>
 
 
 #include "test_macros.h"
 #include "test_iterators.h"
 
 struct is_odd
 {
-    bool operator()(const int& i) const {return i & 1;}
+    TEST_CONSTEXPR bool operator()(const int& i) const {return i & 1;}
 };
 
 template <class Iter>
-void
+TEST_CONSTEXPR_CXX20 bool
 test()
 {
     // check mixed
     int ia[] = {1, 2, 3, 4, 5, 6, 7, 8 ,9};
     const unsigned sa = sizeof(ia)/sizeof(ia[0]);
     Iter r = std::partition(Iter(ia), Iter(ia + sa), is_odd());
     assert(base(r) == ia + 5);
     for (int* i = ia; i < base(r); ++i)
for (unsigned i = 0; i < sa; ++i)
         ia[i] = 2*i;
     ia[0] = 11;
     r = std::partition(Iter(ia), Iter(ia+sa), is_odd());
     assert(base(r) == ia+1);
     for (int* i = ia; i < base(r); ++i)
         assert(is_odd()(*i));
     for (int* i = base(r); i < ia+sa; ++i)
         assert(!is_odd()(*i));
+
+    return true;
 }
 
 int main(int, char**)
 {
     test<bidirectional_iterator<int*> >();
     test<random_access_iterator<int*> >();
     test<int*>();
 
+#if TEST_STD_VER >= 20
+    static_assert(test<bidirectional_iterator<int*>>());
+    static_assert(test<random_access_iterator<int*>>());
+    static_assert(test<int*>());
+#endif
+
     return 0;
 }

libcxx/test/std/algorithms/alg.modifying.operations/alg.reverse/reverse.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<BidirectionalIterator Iter>
 //   requires HasSwap<Iter::reference, Iter::reference>
-//   void
+//   constexpr void  // constexpr in C++20
 //   reverse(Iter first, Iter last);
 
 #include <algorithm>
 #include <cassert>
 
 #include "test_macros.h"
 #include "test_iterators.h"
 
 template <class Iter>
-void
+TEST_CONSTEXPR_CXX20 bool
 test()
 {
     int ia[] = {0};
     const unsigned sa = sizeof(ia)/sizeof(ia[0]);
     std::reverse(Iter(ia), Iter(ia));
     assert(ia[0] == 0);
     std::reverse(Iter(ia), Iter(ia+sa));
     assert(ia[0] == 0);
test()
 
     int id[] = {0, 1, 2, 3};
     const unsigned sd = sizeof(id)/sizeof(id[0]);
     std::reverse(Iter(id), Iter(id+sd));
     assert(id[0] == 3);
     assert(id[1] == 2);
     assert(id[2] == 1);
     assert(id[3] == 0);
+
+    return true;
 }
 
 int main(int, char**)
 {
     test<bidirectional_iterator<int*> >();
     test<random_access_iterator<int*> >();
     test<int*>();
 
+#if TEST_STD_VER >= 20
+    static_assert(test<bidirectional_iterator<int*>>());
+    static_assert(test<random_access_iterator<int*>>());
+    static_assert(test<int*>());
+#endif
+
     return 0;
 }

libcxx/test/std/algorithms/alg.sorting/alg.permutation.generators/next_permutation.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<BidirectionalIterator Iter>
 //   requires ShuffleIterator<Iter>
 //         && LessThanComparable<Iter::value_type>
-//   bool
+//   constexpr bool  // constexpr in C++20
 //   next_permutation(Iter first, Iter last);
 
 #include <algorithm>
 #include <cassert>
 
 #include "test_macros.h"
 #include "test_iterators.h"
 
 #include <cstdio>
 
-int factorial(int x)
+TEST_CONSTEXPR_CXX14 int factorial(int x)
 {
     int r = 1;
     for (; x; --x)
         r *= x;
     return r;
 }
 
 template <class Iter>
-void
+TEST_CONSTEXPR_CXX20 bool
 test()
 {
     int ia[] = {1, 2, 3, 4, 5, 6};
     const int sa = sizeof(ia)/sizeof(ia[0]);
     int prev[sa];
     for (int e = 0; e <= sa; ++e)
     {
         int count = 0;
         bool x;
         do
         {
             std::copy(ia, ia+e, prev);
             x = std::next_permutation(Iter(ia), Iter(ia+e));
             if (e > 1)
             {
                 if (x)
                     assert(std::lexicographical_compare(prev, prev+e, ia, ia+e));
                 else
                     assert(std::lexicographical_compare(ia, ia+e, prev, prev+e));
             }
             ++count;
         } while (x);
         assert(count == factorial(e));
     }
+    return true;
 }
 
 int main(int, char**)
 {
     test<bidirectional_iterator<int*> >();
     test<random_access_iterator<int*> >();
     test<int*>();
 
+#if TEST_STD_VER >= 20
+    static_assert(test<bidirectional_iterator<int*>>());
+    static_assert(test<random_access_iterator<int*>>());
+    static_assert(test<int*>());
+#endif
+
     return 0;
 }

libcxx/test/std/algorithms/alg.sorting/alg.permutation.generators/next_permutation_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<BidirectionalIterator Iter, StrictWeakOrder<auto, Iter::value_type> Compare>
 //   requires ShuffleIterator<Iter>
 //         && CopyConstructible<Compare>
-//   bool
+//   constexpr bool  // constexpr in C++20
 //   next_permutation(Iter first, Iter last, Compare comp);
 
 #include <algorithm>
 #include <functional>
 #include <cassert>
 
 #include "test_macros.h"
 #include "test_iterators.h"
 
 #include <cstdio>
 
-int factorial(int x)
+TEST_CONSTEXPR_CXX14 int factorial(int x)
 {
     int r = 1;
     for (; x; --x)
         r *= x;
     return r;
 }
 
 template <class Iter>
-void
+TEST_CONSTEXPR_CXX20 bool
 test()
 {
     typedef std::greater<int> C;
     int ia[] = {6, 5, 4, 3, 2, 1};
     const int sa = sizeof(ia)/sizeof(ia[0]);
     int prev[sa];
     for (int e = 0; e <= sa; ++e)
     {
for (int e = 0; e <= sa; ++e)
                     assert(std::lexicographical_compare(prev, prev+e, ia, ia+e, C()));
                 else
                     assert(std::lexicographical_compare(ia, ia+e, prev, prev+e, C()));
             }
             ++count;
         } while (x);
         assert(count == factorial(e));
     }
+    return true;
 }
 
 int main(int, char**)
 {
     test<bidirectional_iterator<int*> >();
     test<random_access_iterator<int*> >();
     test<int*>();
 
+#if TEST_STD_VER >= 20
+    static_assert(test<bidirectional_iterator<int*>>());
+    static_assert(test<random_access_iterator<int*>>());
+    static_assert(test<int*>());
+#endif
+
     return 0;
 }

libcxx/test/std/algorithms/alg.sorting/alg.permutation.generators/prev_permutation.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<BidirectionalIterator Iter>
 //   requires ShuffleIterator<Iter>
 //         && LessThanComparable<Iter::value_type>
-//   bool
+//   constexpr bool  // constexpr in C++20
 //   prev_permutation(Iter first, Iter last);
 
 #include <algorithm>
 #include <cassert>
 
 #include "test_macros.h"
 #include "test_iterators.h"
 
 #include <cstdio>
 
-int factorial(int x)
+TEST_CONSTEXPR_CXX14 int factorial(int x)
 {
     int r = 1;
     for (; x; --x)
         r *= x;
     return r;
 }
 
 template <class Iter>
-void
+TEST_CONSTEXPR_CXX20 bool
 test()
 {
     int ia[] = {6, 5, 4, 3, 2, 1};
     const int sa = sizeof(ia)/sizeof(ia[0]);
     int prev[sa];
     for (int e = 0; e <= sa; ++e)
     {
         int count = 0;
         bool x;
         do
         {
             std::copy(ia, ia+e, prev);
             x = std::prev_permutation(Iter(ia), Iter(ia+e));
             if (e > 1)
             {
                 if (x)
                     assert(std::lexicographical_compare(ia, ia+e, prev, prev+e));
                 else
                     assert(std::lexicographical_compare(prev, prev+e, ia, ia+e));
             }
             ++count;
         } while (x);
         assert(count == factorial(e));
     }
+    return true;
 }
 
 int main(int, char**)
 {
     test<bidirectional_iterator<int*> >();
     test<random_access_iterator<int*> >();
     test<int*>();
 
+#if TEST_STD_VER >= 20
+    static_assert(test<bidirectional_iterator<int*>>());
+    static_assert(test<random_access_iterator<int*>>());
+    static_assert(test<int*>());
+#endif
+
     return 0;
 }

libcxx/test/std/algorithms/alg.sorting/alg.permutation.generators/prev_permutation_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<BidirectionalIterator Iter, StrictWeakOrder<auto, Iter::value_type> Compare>
 //   requires ShuffleIterator<Iter>
 //         && CopyConstructible<Compare>
-//   bool
+//   constexpr bool  // constexpr in C++20
 //   prev_permutation(Iter first, Iter last, Compare comp);
 
 #include <algorithm>
 #include <functional>
 #include <cassert>
 
 #include "test_macros.h"
 #include "test_iterators.h"
 
 #include <cstdio>
 
-int factorial(int x)
+TEST_CONSTEXPR_CXX14 int factorial(int x)
 {
     int r = 1;
     for (; x; --x)
         r *= x;
     return r;
 }
 
 template <class Iter>
-void
+TEST_CONSTEXPR_CXX20 bool
 test()
 {
     typedef std::greater<int> C;
     int ia[] = {1, 2, 3, 4, 5, 6};
     const int sa = sizeof(ia)/sizeof(ia[0]);
     int prev[sa];
     for (int e = 0; e <= sa; ++e)
     {
for (int e = 0; e <= sa; ++e)
                     assert(std::lexicographical_compare(ia, ia+e, prev, prev+e, C()));
                 else
                     assert(std::lexicographical_compare(prev, prev+e, ia, ia+e, C()));
             }
             ++count;
         } while (x);
         assert(count == factorial(e));
     }
+    return true;
 }
 
 int main(int, char**)
 {
     test<bidirectional_iterator<int*> >();
     test<random_access_iterator<int*> >();
     test<int*>();
 
+#if TEST_STD_VER >= 20
+    static_assert(test<bidirectional_iterator<int*>>());
+    static_assert(test<random_access_iterator<int*>>());
+    static_assert(test<int*>());
+#endif
+
     return 0;
 }