[Libcxx] Finish implementing Paper 0202R3

[ldionne]

Summary

cppreference lists the support for this paper as partial.
I found 4 functions which the paper marks as constexpr, but did not use the appropriate macro.

[mclow.lists]

I see no tests.

[Nicholas-Baron]

In D84275#2165639, @mclow.lists wrote:

I see no tests.

I apologize, as this is my first time contributing. I do not know where the tests for the other functions that were made constexpr are.
My testing plan would at least involve showing that the functions compile in a constexpr context in C++20 and not in earlier versions.

[miscco]

Thanks a lot for taking the time.

Unfortunately putting _LIBCPP_CONSTEXPR_AFTER_CXX17 in front of the function is only half way through the implementation. As you can see for example in move_backward the implementation falls back to _VSTD::__rotate which is also defined in <algorithm>.
Now to use move_backward in a constexpr context you need make all subsequent functions such as __rotate constexpr. Sometimes this is easy, sometimes it is just a rabbit hole ;)

Regarding the tests I would like to point you to the libcxx/test/std/algorithms subfolder. For example you can find the tests for move_backward here: libcxx/test/std/algorithms/alg.modifying.operations/alg.move/move_backward.pass.cpp

As you can see there is a convenient test() function. What you have to do is add TEST_CONSTEXPR_CXX20 before it and then in addition to calling it at runtime also call it inside a constexpr context. The easiest way to do so is to simply change the function return type to bool and add a return true at the end. Then you only need to duplicate all the calls to test via static_assert(test());

Note that you would also need to guard these C++20 additions via #if TEST_STD_VER >= 20. I appologize that the macros are a mess each using its own selection of after foo, >=foo and foo.

[ldionne]

In D84275#2165958, @miscco wrote:

[...]

Regarding the tests I would like to point you to the libcxx/test/std/algorithms subfolder. For example you can find the tests for move_backward here: libcxx/test/std/algorithms/alg.modifying.operations/alg.move/move_backward.pass.cpp

As you can see there is a convenient test() function. What you have to do is add TEST_CONSTEXPR_CXX20 before it and then in addition to calling it at runtime also call it inside a constexpr co

@Nicholas-Baron Indeed, thanks for working on your first contribution! What @miscco said above is great, and I would add that you probably want to go and add the tests first, then run the test suite and notice that the expected tests are failing. Then you can go ahead and add the required annotations to the library. One example of a patch that constexpr-ified a bunch of tests is https://reviews.llvm.org/D80452, you can take a look at that one.

Also, this appears to have some overlap with https://reviews.llvm.org/D65721. Perhaps you can coordinate with @zoecarver and pick up the work in D65721?

[Nicholas-Baron]

In D84275#2166781, @ldionne wrote:

[...]
Also, this appears to have some overlap with https://reviews.llvm.org/D65721. Perhaps you can coordinate with @zoecarver and pick up the work in D65721?

Thank you @Idionne for pointing me to that patch. This will help focus my efforts.
The move and move_backward functions are covered in that diff, so I will remove my changes to those functions.
However, merge and rotate_copy both are marked by the paper as constexpr, but are not addressed in the mentioned patch (and so I will address them here).

[Nicholas-Baron]

Removed parts covered in https://reviews.llvm.org/D65721 and uncommented a test.

[Nicholas-Baron]

Passed tests and made one internal function constexpr

[Nicholas-Baron]

The builds are failing with this line standing out
ld.lld: error: unable to find library -lcxxabi_shared

[zoecarver]

Hopefully, I can land D65721 sometime this week, and then you can rebase this patch on master. Otherwise, feel free to take anything you need from that patch.

libcxx/test/std/algorithms/alg.modifying.operations/alg.rotate/rotate_copy.pass.cpp

31

Rather than returning the tested condition, the convention is to simply assert that the result is what you expect and return true from the function. If the assertion fires the function will not be able to be evaluated as a constant expression and the test will fail.

[Nicholas-Baron]

Applied constexpr testing conventions suggested by @zoecarver.

[zoecarver]

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

36

Almost perfect. Can you make each check an individual assert? That makes it easier to figure out what went wrong if the tests start failing.

This should be:

assert(std::distance(...) == (...));
assert(*it == 0);
assert(std::equal(...));

[Nicholas-Baron]

Decomposed asserts in tests

[zoecarver]

libcxx/test/std/algorithms/alg.modifying.operations/alg.rotate/rotate_copy.pass.cpp

40

Do you think you could make this test a constexpr and return true at the end? That way we test the same thing in both constexpr and non-constexpr mode. TEST_CONSTEXPR should work in all modes.

[Nicholas-Baron]

Used TEST_CONSTEXPR on the merge and rotate_copy tests.

[Nicholas-Baron]

libcxx/test/std/algorithms/alg.modifying.operations/alg.rotate/rotate_copy.pass.cpp

40

Would this mean changing the call site as well to utilize the returned true or is ignoring the return value acceptable in this case?

[ldionne]

Commandeering to show exactly what we meant by the requested test changes, however we're very very close here. Thanks a lot for your contribution @Nicholas-Baron !

[ldionne]

Finish up the tests

[ldionne]

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

49

It would have been lovely to make all these tests constexpr as well, but they are using <random>. We could rework the tests to make more of it constexpr friendly if desired, but I think this is good enough as is for now.

[ldionne]

For the record, I tested this in all standard modes using

for std in c++11 c++14 c++17 c++2a; do ninja -C build check-cxx-deps && ./build/bin/llvm-lit -sv libcxx/test/std/algorithms --param std=$std; done

libcxx/include/algorithm

if (__middle == __last)
         return __first;
     return _VSTD::__rotate(__first, __middle, __last,
                            typename _VSTD::iterator_traits<_ForwardIterator>::iterator_category());
 }
 
 // rotate_copy
 
 template <class _ForwardIterator, class _OutputIterator>
-inline _LIBCPP_INLINE_VISIBILITY
+inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 _OutputIterator
 rotate_copy(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last, _OutputIterator __result)
 {
     return _VSTD::copy(__first, __middle, _VSTD::copy(__middle, __last, __result));
 }
 
 // min_element
 

 {
     return _VSTD::binary_search(__first, __last, __value_,
                              __less<typename iterator_traits<_ForwardIterator>::value_type, _Tp>());
 }
 
 // merge
 
 template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
+_LIBCPP_CONSTEXPR_AFTER_CXX17
 _OutputIterator
 __merge(_InputIterator1 __first1, _InputIterator1 __last1,
         _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
 {
     for (; __first1 != __last1; ++__result)
     {
         if (__first2 == __last2)
             return _VSTD::copy(__first1, __last1, __result);
         if (__comp(*__first2, *__first1))
         {
             *__result = *__first2;
             ++__first2;
         }
         else
         {
             *__result = *__first1;
             ++__first1;
         }
     }
     return _VSTD::copy(__first2, __last2, __result);
 }
 
 template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>
-inline _LIBCPP_INLINE_VISIBILITY
+inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 _OutputIterator
 merge(_InputIterator1 __first1, _InputIterator1 __last1,
       _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
 {
     typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
     return _VSTD::__merge<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp);
 }
 
 template <class _InputIterator1, class _InputIterator2, class _OutputIterator>
-inline _LIBCPP_INLINE_VISIBILITY
+inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 _OutputIterator
 merge(_InputIterator1 __first1, _InputIterator1 __last1,
       _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result)
 {
     typedef typename iterator_traits<_InputIterator1>::value_type __v1;
     typedef typename iterator_traits<_InputIterator2>::value_type __v2;
     return _VSTD::merge(__first1, __last1, __first2, __last2, __result, __less<__v1, __v2>());
 }

libcxx/test/std/algorithms/alg.modifying.operations/alg.rotate/rotate_copy.pass.cpp

 //   rotate_copy(InIter first, InIter middle, InIter last, OutIter result);
 
 #include <algorithm>
 #include <cassert>
 
 #include "test_macros.h"
 #include "test_iterators.h"
 
-// #if TEST_STD_VER > 17
-// TEST_CONSTEXPR bool test_constexpr() {
-//     int ia[] = {1, 3, 5, 2, 5, 6};
-//     int ib[std::size(ia)] = {0};
-//
-//     const size_t N = 2;
-//     const auto middle = std::begin(ia) + N;
-//     auto it = std::rotate_copy(std::begin(ia), middle, std::end(ia), std::begin(ib));
-//
-//     return std::distance(std::begin(ib), it) == std::size(ia)
-//         && std::equal   (std::begin(ia), middle,       std::begin(ib) + std::size(ia) - N)
-//         && std::equal   (middle,         std::end(ia), std::begin(ib))
-//            ;
-//     }
-// #endif
+#if TEST_STD_VER > 17
+TEST_CONSTEXPR bool test_constexpr() {
+  int ia[] = {1, 3, 5, 2, 5, 6};
+  int ib[std::size(ia)] = {0};
+
+  const size_t N = 2;
+  const auto middle = std::begin(ia) + N;
+  auto it =
+      std::rotate_copy(std::begin(ia), middle, std::end(ia), std::begin(ib));
+
+  assert(
+      std::distance(std::begin(ib), it) == std::size(ia) &&
+      std::equal(std::begin(ia), middle, std::begin(ib) + std::size(ia) - N) &&
+      std::equal(middle, std::end(ia), std::begin(ib)));
+  return true;
+}
+#endif
 
 template <class InIter, class OutIter>
 void
 test()
 {
     int ia[] = {0, 1, 2, 3};
     const unsigned sa = sizeof(ia)/sizeof(ia[0]);
     int ib[sa] = {0};
 
     OutIter r = std::rotate_copy(InIter(ia), InIter(ia), InIter(ia), OutIter(ib));
     assert(base(r) == ib);
int main(int, char**)
     test<random_access_iterator<const int*>, int*>();
 
     test<const int*, output_iterator<int*> >();
     test<const int*, forward_iterator<int*> >();
     test<const int*, bidirectional_iterator<int*> >();
     test<const int*, random_access_iterator<int*> >();
     test<const int*, int*>();
 
-// #if TEST_STD_VER > 17
-//    static_assert(test_constexpr());
-// #endif
+#if TEST_STD_VER > 17
+    static_assert(test_constexpr());
+#endif
 
     return 0;
 }

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

 
 #include <algorithm>
 #include <random>
 #include <cassert>
 
 #include "test_macros.h"
 #include "test_iterators.h"
 
-
-// #if TEST_STD_VER > 17
-// TEST_CONSTEXPR bool test_constexpr() {
-//           int ia[]       = {0, 1, 2, 3, 4};
-//           int ib[]       = {2, 4, 6, 8};
-//           int ic[]       = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
-//     const int expected[] = {0, 1, 2, 2, 3, 4, 4, 6, 8};
-//
-//     auto it = std::merge(std::begin(ia), std::end(ia), std::begin(ib), std::end(ib), std::begin(ic));
-//     return std::distance(std::begin(ic), it) == (std::size(ia) + std::size(ib))
-//         && *it == 0
-//         && std::equal(std::begin(ic), it, std::begin(expected), std::end(expected))
-//         ;
-//     }
-// #endif
+#if TEST_STD_VER > 17
+TEST_CONSTEXPR bool test_constexpr() {
+  int ia[] = {0, 1, 2, 3, 4};
+  int ib[] = {2, 4, 6, 8};
+  int ic[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
+  const int expected[] = {0, 1, 2, 2, 3, 4, 4, 6, 8};
+
+  auto it = std::merge(std::begin(ia), std::end(ia), std::begin(ib),
+                       std::end(ib), std::begin(ic));
+  assert(
+      std::distance(std::begin(ic), it) == (std::size(ia) + std::size(ib)) &&
+      *it == 0 &&
+      std::equal(std::begin(ic), it, std::begin(expected), std::end(expected)));
+  return true;
+}
+#endif
 
 std::mt19937 randomness;
 
 template <class InIter1, class InIter2, class OutIter>
 void
 test()
 {
     {
     unsigned N = 100000;
     int* ia = new int[N];
     int* ib = new int[N];
     int* ic = new int[2*N];
     for (unsigned i = 0; i < N; ++i)
         ia[i] = 2*i;
     for (unsigned i = 0; i < N; ++i)
int main(int, char**)
 
     test<const int*, const int*, output_iterator<int*> >();
     test<const int*, const int*, forward_iterator<int*> >();
     test<const int*, const int*, bidirectional_iterator<int*> >();
     test<const int*, const int*, random_access_iterator<int*> >();
     test<const int*, const int*, int*>();
 
 #if TEST_STD_VER > 17
-//  Not yet - waiting on std::copy
-//     static_assert(test_constexpr());
+    static_assert(test_constexpr());
 #endif
 
   return 0;
 }

libcxx/test/std/algorithms/alg.sorting/alg.merge/merge_comp.pass.cpp

 #include <functional>
 #include <random>
 #include <cassert>
 
 #include "test_macros.h"
 #include "test_iterators.h"
 #include "counting_predicates.h"
 
-// #if TEST_STD_VER > 17
-// TEST_CONSTEXPR bool test_constexpr() {
-//           int ia[]       = {0, 1, 2, 3, 4};
-//           int ib[]       = {2, 4, 6, 8};
-//           int ic[]       = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
-//     const int expected[] = {0, 1, 2, 2, 3, 4, 4, 6, 8};
-//
-//     auto it = std::merge(std::begin(ia), std::end(ia),
-//                          std::begin(ib), std::end(ib),
-//                          std::begin(ic), [](int a, int b) {return a == b; });
-//     return std::distance(std::begin(ic), it) == (std::size(ia) + std::size(ib))
-//         && *it == 0
-//         && std::equal(std::begin(ic), it, std::begin(expected), std::end(expected))
-//         ;
-//     }
-// #endif
+#if TEST_STD_VER > 17
+TEST_CONSTEXPR bool test_constexpr() {
+  int ia[] = {0, 1, 2, 3, 4};
+  int ib[] = {2, 4, 6, 8};
+  int ic[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
+  const int expected[] = {0, 1, 2, 2, 3, 4, 4, 6, 8};
+
+  auto it =
+      std::merge(std::begin(ia), std::end(ia), std::begin(ib), std::end(ib),
+                 std::begin(ic), [](int a, int b) { return a == b; });
+  assert(
+      std::distance(std::begin(ic), it) == (std::size(ia) + std::size(ib)) &&
+      *it == 0 &&
+      std::equal(std::begin(ic), it, std::begin(expected), std::end(expected)));
+  return true;
+}
+#endif
 
 std::mt19937 randomness;
 
 template <class InIter1, class InIter2, class OutIter>
 void
 test()
 {
     {
int main(int, char**)
 
     test<const int*, const int*, output_iterator<int*> >();
     test<const int*, const int*, forward_iterator<int*> >();
     test<const int*, const int*, bidirectional_iterator<int*> >();
     test<const int*, const int*, random_access_iterator<int*> >();
     test<const int*, const int*, int*>();
 
 #if TEST_STD_VER > 17
-//  Not yet - waiting on std::copy
-//     static_assert(test_constexpr());
+    static_assert(test_constexpr());
 #endif
 
   return 0;
 }