Make rotate a constexpr

[zoecarver]

Summary

This patch makes std::rotate a constexpr. This way it can be used in other constexpr functions such as shift_left and shift_right.

[ldionne]

libcxx/include/algorithm

2360

This function can be made constexpr in all standard modes that support generalized constexpr (so C++14 and above).

That holds for all helper functions below.

2419

Ditto.

2433

Ditto.

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

427

Typo: test_constexpr

441

It would be nice if we could run all the same tests for constexpr and non-constexpr. It's not clear to me why we can't just run test<....> in a constexpr context. As for test1, it allocates memory but it might be possible to change the test to avoid that?

Generally speaking, I'd like for us to develop a fairly mechanical way of testing things in a constexpr context, since we're going to have to do that for almost all of <algorithm>. I think it's important to have the same test coverage for constexpr and non-constexpr (whenever it makes sense, of course).

[zoecarver]

libcxx/include/algorithm

2360

Was std::rotate updated as a paper or an issue? Or have we decided to extend constexpr support back to C++14 independent of the standard?

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

441

I agree. What if we decided that we test constexpr by adding return true to the end of the test function and modifying the function to be a constexpr that returns a bool. This should work for almost all <algorithm> tests.

[mclow.lists]

rotate and a bunch of other algorithms were made constexpr in P0202, adopted in ABQ.

We've done some of them already; we should do the rest.

[mclow.lists]

libcxx/include/algorithm

2360

We don't have the freedom to add constexpr to things in the standard.
We do have the freedom to add noexcept.

Odd, but that's the world we've got.

[ldionne]

libcxx/include/algorithm

2360

My comment was only about helper functions. Make the helper functions constexpr whenever possible, but only mark the actual algorithm std::rotate constexpr when the Standard says so.

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

441

Yes, something along those lines is what I was thinking about. Can you see if that works?

[zoecarver]

In D65721#1617250, @mclow.lists wrote:

rotate and a bunch of other algorithms were made constexpr in P0202, adopted in ABQ.

We've done some of them already; we should do the rest.

That paper says:

Note for editor: All the functions in [algorithms.general] must be marked with constexpr, except functions shuffle, sample, stable_sort, stable_partition, inplace_merge, functions accepting ExecutionPolicy and algorithms that have ValueSwappable requirement(20.5.3.2):

std::rotate is not one of the updated functions in that paper. It is updated in the standard, though.

We have only done a very few of them. I am starting to make my way through the list. There are several papers which update various algorithms IIRC.

[zoecarver]

• update constexpr tests (now they have full test coverage in a constexpr context)
• add constexpr to internal functions
• upgrade move functions to be constexpr

[zoecarver]

libcxx/include/algorithm

1892

I am concerned we are losing performance for those who do not have is_constant_evaluated and are not in a constexpr context.

2360

Ah, I see. Good call. Done.

[zoecarver]

libcxx/include/iterator

1612

What was the reasoning behind _LIBCPP_CONSTEXPR_IF_NODEBUG? I updated it to _LIBCPP_CONSTEXPR but, I want to make sure that is OK.

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

441

It does.

[zoecarver]

• fix tests
• make internal functions always constexpr

[ldionne]

libcxx/include/algorithm

1892

This doesn't work because is_constant_evaluated is not a macro. We have the macro _LIBCPP_HAS_NO_BUILTIN_IS_CONSTANT_EVALUATED that tells you whether std::is_constant_evaluated is supported.

[zoecarver]

• Rebase off master.
• Use _LIBCPP_HAS_NO_BUILTIN_IS_CONSTANT_EVALUATED

[ldionne]

libcxx/include/algorithm

1682

Does this break the library when used with the debug mode? There must have been a reason why we added _LIBCPP_CONSTEXPR_IF_NODEBUG in the first place?

@EricWF Do we care about this? If not, it looks like now's the time to remove the debug mode (for something better) as we discussed.

1896

I don't see the point of this #elif, can you explain?

1952

This needs to be constexpr in C++20 and above only, since it's part of the API.

libcxx/include/iterator

1397

Please keep the previous formatting.

[zoecarver]

libcxx/include/algorithm

1682

I think it should be the opposite: the tests fail in debug mode because this is no longer constexpr. I'll test it, though.

1896

After C++17 the standard says some users of this function should be constexpr so, we have to support that. But before C++20, if _LIBCPP_HAS_NO_BUILTIN_IS_CONSTANT_EVALUATED we probably want to take the fast path even if it means no constexpr. WDYT?

[zoecarver]

libcxx/include/algorithm

1682

The tests all pass with _LIBCPP_DEBUG=1.

1865

These all need to be _LIBCPP_CONSTEXPR_AFTER_CXX17. Otherwise, the compiler will complain about the loops in pre C++20 mode.

[zoecarver]

• Rebase off master
• Revert formatting change
• Make everything _LIBCPP_CONSTEXPR_AFTER_CXX17

[ldionne]

Your comment about loops made me think about generalized constexpr in C++14. Can you run the tests with your patch in C++11 and C++14 to make sure it works? I would expect failures due to the lack of generalized constexpr in C++11.

libcxx/include/algorithm

1682

Can you try with _LIBCPP_DEBUG=2? It's a different debug level. I know it's kind of confusing.

1865

I don't see why. Loops are allowed in constexpr since C++14. I guess we would need to use _LIBCPP_CONSTEXPR_AFTER_CXX14 then.

Essentially, the rule I'm trying to go for is: make private helpers constexpr as often as they can be, and make public APIs constexpr when the standard requires them to.

1896

Hmm, interesting. Yeah, that makes sense, however it also means that we might be pessimizing the runtime version in C++20 just because the compiler doesn't have is_constant_evaluated. I'm not 100% sure what the best approach is, however I would tend to say: In C++20, we are conforming w.r.t. constexpr algorithms only when the compiler supports is_constant_evaluated, otherwise we are non-conforming in favour of performance. In other words, when is_constant_evaluated isn't provided, we would not properly provide constexpr in these algorithms, and we'd always use the fast-but-not-constexpr version. This would avoid silent pessimizations, but would reduce our conformance level with older compilers. I don't think it's a huge deal because libc++ should normally be used with a recent compiler anyway, but this merits some thinking.

If we go down that route, we could simply use __libcpp_is_constant_evaluated() instead of the logic you have here.

[zoecarver]

libcxx/include/algorithm

1682

All tests pass :)

1865

I didn't think to check, you're right loops in constexpr in C++14 work fine.

Essentially, the rule I'm trying to go for is: make private helpers constexpr as often as they can be, and make public APIs constexpr when the standard requires them to.

Great, I think this is a good idea.

1896

My thinking here is that it's doubtful (especially at this point in time) that someone will be enabling C++20 on a compiler that isn't fairly recent.

But, this is actually a moot point because I just realized after P0202 we can use memmove in a constexpr context. So, we can remove __move_constexpr altogether.

[zoecarver]

• Make some things _LIBCPP_CONSTEXPR_AFTER_CXX14
• Remove *_constexpr functions

[ldionne]

libcxx/include/algorithm

1883

Wait, this doesn't work at all because memmove isn't constexpr. You still need the _constexpr functions, I just meant that it was reasonable to not try to use their constexpr version when is_constant_evaluated() isn't supported by the compiler.

I would expect that your tests fail with the patch as it is (and if not there's something I don't understand, so please LMK).

[zoecarver]

libcxx/include/algorithm

1883

You're right. I was looking at an earlier version of the paper where memmove was constexpr and then ran the tests in C++17 mode (when the constexpr bits weren't enabled) and thought, "this is great!"

Anyway, we could use __builtin_memmove after in Clang 8+ (which is constexpr).

[zoecarver]

• Rebase off master
• Add back move_constexpr and move_backward_constexpr

[zoecarver]

• Pass correct args to __move_constexpr

[ldionne]

libcxx/include/algorithm

2500

This can't be constexpr in C++14 since it uses __rotate_forward, which is only marked as constexpr starting in C++17 and above.

libcxx/test/std/algorithms/alg.modifying.operations/alg.move/move.pass.cpp

137

I would remove && !defined(_LIBCPP_HAS_NO_BUILTIN_IS_CONSTANT_EVALUATED) -- the test suite isn't supposed to have libc++ or compiler specific knowledge. If the test fails with some older compilers (e.g. clang 5), we can mark it as unsupported on that compiler.

[zoecarver]

• Update comment about P0202 in 2a status

[zoecarver]

libcxx/include/algorithm

2500

If it can take one of the first two paths, then it can be constexpr. I think it makes sense to support it in C++14 when possible.

libcxx/test/std/algorithms/alg.modifying.operations/alg.move/move.pass.cpp

137

__builtin_is_constant_evalutated is actually pretty new. It was only added to clang in the last year IIRC. I think this will be a long list of compilers. The clang that ships on the latest macOS (Apple clang 11) doesn't even support it. It may be worth adding something to test_macros. WDYT?

[zoecarver]

• Use __libcpp_is_constant_evaluated instead of is_constant_evaluated.

[ldionne]

libcxx/include/algorithm

1892

You don't need #if _LIBCPP_HAS_NO_BUILTIN_IS_CONSTANT_EVALUATED anymore if you're using __libcpp_is_constant_evaluated() -- IIUC.

2500

Geez, you're right. I really glanced too quickly here.

libcxx/test/std/algorithms/alg.modifying.operations/alg.move/move.pass.cpp

137

My preference would still be to say // UNSUPPORTED: c++2a && apple-clang-11 (and the same for all unsupported compilers). The reason is that these UNSUPPORTED annotations are easy to get rid of as time goes by and we stop caring about older compilers. As such, it's easy-to-remove tech debt in the test suite.

On the other hand, if we engineer the test suite such that it can be run with compilers that don't support is_constant_evaluated(), we add complexity to the test suite itself, and removing it will require making sure that e.g. nobody's using the test suite with a compiler that doesn't support is_constant_evaluated(). Also, in theory, we should do the same for all features that involve compiler support, which isn't really scalable.

So.. my preference would be to be aggressive with compilers that don't support required features -- after all, libc++ is normally shipped alongside a matching Clang.

[zoecarver]

libcxx/include/algorithm

1892

Yep, you're right.

libcxx/test/std/algorithms/alg.modifying.operations/alg.move/move.pass.cpp

137

Fair enough. I'll use UNSUPPORTED.

Why the C++2a part, though? I think I'll leave the TEST_STD_VER > 17 condition because that's what the standard says so, we shouldn't need the C++2a condition.

Also, I think we should support clang-8 and up. What are the corresponding apple-clang versions?

[zoecarver]

• Remove "has builtin" check in __move.
• Replace #if in test with UNSUPPORTED.

[ldionne]

This almost LGTM. You can commit after fixing those comments and I'll adjust the markup for AppleClang as needed.

libcxx/include/algorithm

1940

Same here, _LIBCPP_HAS_NO_BUILTIN_IS_CONSTANT_EVALUATED isn't needed.

libcxx/test/std/algorithms/alg.modifying.operations/alg.move/move_backward.pass.cpp

87

Same as above, please remove && !defined(_LIBCPP_HAS_NO_BUILTIN_IS_CONSTANT_EVALUATED)

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

440

Same as above for && !defined(_LIBCPP_HAS_NO_BUILTIN_IS_CONSTANT_EVALUATED).

[zoecarver]

@ldionne thanks for your patience with this patch. It's great to finally get it in.

[ldionne]

Re-committed as 3ed89b51da38f081fedb57727076262abb81d149 with UNSUPPORTED markup.

@zoecarver Thanks to you for the contribution and for being patient with the review. Greatly appreciated.

libcxx/include/algorithm

 {
     typedef typename iterator_traits<_ForwardIterator>::value_type __v;
     return _VSTD::search_n(__first, __last, __convert_to_integral(__count),
                            __value_, __equal_to<__v, _Tp>());
 }
 
 // copy
 template <class _Iter>
-inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
+inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
 _Iter
 __unwrap_iter(_Iter __i)
 {
     return __i;
 }
 
 template <class _Tp>
-inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
+inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
 typename enable_if
 <
     is_trivially_copy_assignable<_Tp>::value,
     _Tp*
 >::type
 __unwrap_iter(move_iterator<_Tp*> __i)
 {
     return __i.base();
 }
 
 #if _LIBCPP_DEBUG_LEVEL < 2
 
 template <class _Tp>
-inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG
+inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
 typename enable_if
 <
     is_trivially_copy_assignable<_Tp>::value,
     _Tp*
 >::type
 __unwrap_iter(__wrap_iter<_Tp*> __i)
 {
     return __i.base();
 }
 
 template <class _Tp>
-inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG
+inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
 typename enable_if
 <
     is_trivially_copy_assignable<_Tp>::value,
     const _Tp*
 >::type
 __unwrap_iter(__wrap_iter<const _Tp*> __i)
 {
     return __i.base();
 }
 
 #else
 
 template <class _Tp>
-inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG
+inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
 typename enable_if
 <
     is_trivially_copy_assignable<_Tp>::value,
     __wrap_iter<_Tp*>
 >::type
 __unwrap_iter(__wrap_iter<_Tp*> __i)
 {
     return __i;

 {
     typedef decltype(__convert_to_integral(__orig_n)) _IntegralSize;
     _IntegralSize __n = __orig_n;
     return _VSTD::copy(__first, __first + __n, __result);
 }
 
 // move
 
+// __move_constexpr exists so that __move doesn't call itself when delegating to the constexpr
+// version of __move.
 template <class _InputIterator, class _OutputIterator>
-inline _LIBCPP_INLINE_VISIBILITY
+inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
 _OutputIterator
-__move(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
+__move_constexpr(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
 {
     for (; __first != __last; ++__first, (void) ++__result)
         *__result = _VSTD::move(*__first);
     return __result;
 }
 
+template <class _InputIterator, class _OutputIterator>
+inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
+_OutputIterator
+__move(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
+{
+    return __move_constexpr(__first, __last, __result);
+}
+
 template <class _Tp, class _Up>
-inline _LIBCPP_INLINE_VISIBILITY
+inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
 typename enable_if
 <
     is_same<typename remove_const<_Tp>::type, _Up>::value &&
     is_trivially_copy_assignable<_Up>::value,
     _Up*
 >::type
 __move(_Tp* __first, _Tp* __last, _Up* __result)
 {
+    if (__libcpp_is_constant_evaluated())
+        return __move_constexpr(__first, __last, __result);
     const size_t __n = static_cast<size_t>(__last - __first);
     if (__n > 0)
         _VSTD::memmove(__result, __first, __n * sizeof(_Up));
     return __result + __n;
 }
 
 template <class _InputIterator, class _OutputIterator>
-inline _LIBCPP_INLINE_VISIBILITY
+inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 _OutputIterator
 move(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
 {
     return _VSTD::__move(__unwrap_iter(__first), __unwrap_iter(__last), __unwrap_iter(__result));
 }
 
 // move_backward
 
+// __move_backward_constexpr exists so that __move_backward doesn't call itself when delegating to
+// the constexpr version of __move_backward.
 template <class _InputIterator, class _OutputIterator>
-inline _LIBCPP_INLINE_VISIBILITY
+inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
 _OutputIterator
-__move_backward(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
+__move_backward_constexpr(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
 {
     while (__first != __last)
         *--__result = _VSTD::move(*--__last);
     return __result;
 }
 
+template <class _InputIterator, class _OutputIterator>
+inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
+_OutputIterator
+__move_backward(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
+{
+    return __move_backward_constexpr(__first, __last, __result);
+}
+
 template <class _Tp, class _Up>
-inline _LIBCPP_INLINE_VISIBILITY
+inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
 typename enable_if
 <
     is_same<typename remove_const<_Tp>::type, _Up>::value &&
     is_trivially_copy_assignable<_Up>::value,
     _Up*
 >::type
 __move_backward(_Tp* __first, _Tp* __last, _Up* __result)
 {
+    if (__libcpp_is_constant_evaluated())
+        return __move_backward_constexpr(__first, __last, __result);
     const size_t __n = static_cast<size_t>(__last - __first);
     if (__n > 0)
     {
         __result -= __n;
         _VSTD::memmove(__result, __first, __n * sizeof(_Up));
     }
     return __result;
 }
 
 template <class _BidirectionalIterator1, class _BidirectionalIterator2>
-inline _LIBCPP_INLINE_VISIBILITY
+inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 _BidirectionalIterator2
 move_backward(_BidirectionalIterator1 __first, _BidirectionalIterator1 __last,
               _BidirectionalIterator2 __result)
 {
     return _VSTD::__move_backward(__unwrap_iter(__first), __unwrap_iter(__last), __unwrap_iter(__result));
 }
 
 // iter_swap
reverse_copy(_BidirectionalIterator __first, _BidirectionalIterator __last, _OutputIterator __result)
     for (; __first != __last; ++__result)
         *__result = *--__last;
     return __result;
 }
 
 // rotate
 
 template <class _ForwardIterator>
-_ForwardIterator
+_LIBCPP_CONSTEXPR_AFTER_CXX11 _ForwardIterator
 __rotate_left(_ForwardIterator __first, _ForwardIterator __last)
 {
     typedef typename iterator_traits<_ForwardIterator>::value_type value_type;
     value_type __tmp = _VSTD::move(*__first);
     _ForwardIterator __lm1 = _VSTD::move(_VSTD::next(__first), __last, __first);
     *__lm1 = _VSTD::move(__tmp);
     return __lm1;
 }
 
 template <class _BidirectionalIterator>
-_BidirectionalIterator
+_LIBCPP_CONSTEXPR_AFTER_CXX11 _BidirectionalIterator
 __rotate_right(_BidirectionalIterator __first, _BidirectionalIterator __last)
 {
     typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
     _BidirectionalIterator __lm1 = _VSTD::prev(__last);
     value_type __tmp = _VSTD::move(*__lm1);
     _BidirectionalIterator __fp1 = _VSTD::move_backward(__first, __lm1, __last);
     *__first = _VSTD::move(__tmp);
     return __fp1;
 }
 
 template <class _ForwardIterator>
-_ForwardIterator
+_LIBCPP_CONSTEXPR_AFTER_CXX14 _ForwardIterator
 __rotate_forward(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last)
 {
     _ForwardIterator __i = __middle;
     while (true)
     {
         swap(*__first, *__i);
         ++__first;
         if (++__i == __last)
if (__first != __middle)
                 __middle = __i;
         }
     }
     return __r;
 }
 
 template<typename _Integral>
 inline _LIBCPP_INLINE_VISIBILITY
-_Integral
+_LIBCPP_CONSTEXPR_AFTER_CXX14 _Integral
 __algo_gcd(_Integral __x, _Integral __y)
 {
     do
     {
         _Integral __t = __x % __y;
         __x = __y;
         __y = __t;
     } while (__y);
     return __x;
 }
 
 template<typename _RandomAccessIterator>
-_RandomAccessIterator
+_LIBCPP_CONSTEXPR_AFTER_CXX14 _RandomAccessIterator
 __rotate_gcd(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last)
 {
     typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
     typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
 
     const difference_type __m1 = __middle - __first;
     const difference_type __m2 = __last - __middle;
     if (__m1 == __m2)
     {
for (_RandomAccessIterator __p = __first + __g; __p != __first;)
         } while (__p2 != __p);
         *__p1 = _VSTD::move(__t);
     }
     return __first + __m2;
 }
 
 template <class _ForwardIterator>
 inline _LIBCPP_INLINE_VISIBILITY
-_ForwardIterator
+_LIBCPP_CONSTEXPR_AFTER_CXX11 _ForwardIterator
 __rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last,
          _VSTD::forward_iterator_tag)
 {
     typedef typename _VSTD::iterator_traits<_ForwardIterator>::value_type value_type;
     if (_VSTD::is_trivially_move_assignable<value_type>::value)
     {
         if (_VSTD::next(__first) == __middle)
             return _VSTD::__rotate_left(__first, __last);
     }
     return _VSTD::__rotate_forward(__first, __middle, __last);
 }
 
 template <class _BidirectionalIterator>
 inline _LIBCPP_INLINE_VISIBILITY
-_BidirectionalIterator
+_LIBCPP_CONSTEXPR_AFTER_CXX11 _BidirectionalIterator
 __rotate(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last,
          _VSTD::bidirectional_iterator_tag)
 {
     typedef typename _VSTD::iterator_traits<_BidirectionalIterator>::value_type value_type;
     if (_VSTD::is_trivially_move_assignable<value_type>::value)
     {
         if (_VSTD::next(__first) == __middle)
             return _VSTD::__rotate_left(__first, __last);
         if (_VSTD::next(__middle) == __last)
             return _VSTD::__rotate_right(__first, __last);
     }
     return _VSTD::__rotate_forward(__first, __middle, __last);
 }
 
 template <class _RandomAccessIterator>
 inline _LIBCPP_INLINE_VISIBILITY
-_RandomAccessIterator
+_LIBCPP_CONSTEXPR_AFTER_CXX11 _RandomAccessIterator
 __rotate(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last,
          _VSTD::random_access_iterator_tag)
 {
     typedef typename _VSTD::iterator_traits<_RandomAccessIterator>::value_type value_type;
     if (_VSTD::is_trivially_move_assignable<value_type>::value)
     {
         if (_VSTD::next(__first) == __middle)
             return _VSTD::__rotate_left(__first, __last);
         if (_VSTD::next(__middle) == __last)
             return _VSTD::__rotate_right(__first, __last);
         return _VSTD::__rotate_gcd(__first, __middle, __last);
     }
     return _VSTD::__rotate_forward(__first, __middle, __last);
 }
 
 template <class _ForwardIterator>
 inline _LIBCPP_INLINE_VISIBILITY
-_ForwardIterator
+_LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator
 rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last)
 {
     if (__first == __middle)
         return __last;
     if (__middle == __last)
         return __first;
     return _VSTD::__rotate(__first, __middle, __last,
                            typename _VSTD::iterator_traits<_ForwardIterator>::iterator_category());

libcxx/include/iterator

 
 template <class _Iter>
 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG
 __wrap_iter<_Iter>
 operator+(typename __wrap_iter<_Iter>::difference_type, __wrap_iter<_Iter>) _NOEXCEPT;
 
 template <class _Ip, class _Op> _Op _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 copy(_Ip, _Ip, _Op);
 template <class _B1, class _B2> _B2 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 copy_backward(_B1, _B1, _B2);
-template <class _Ip, class _Op> _Op _LIBCPP_INLINE_VISIBILITY move(_Ip, _Ip, _Op);
-template <class _B1, class _B2> _B2 _LIBCPP_INLINE_VISIBILITY move_backward(_B1, _B1, _B2);
+template <class _Ip, class _Op> _Op _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 move(_Ip, _Ip, _Op);
+template <class _B1, class _B2> _B2 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 move_backward(_B1, _B1, _B2);
 
 #if _LIBCPP_DEBUG_LEVEL < 2
 
 template <class _Tp>
-_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG
+_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
 typename enable_if
 <
     is_trivially_copy_assignable<_Tp>::value,
     _Tp*
 >::type
 __unwrap_iter(__wrap_iter<_Tp*>);
 
 #else
 
 template <class _Tp>
-inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG
+inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
 typename enable_if
 <
     is_trivially_copy_assignable<_Tp>::value,
     __wrap_iter<_Tp*>
 >::type
 __unwrap_iter(__wrap_iter<_Tp*> __i);
 
 #endif
#endif
 
     template <class _Iter1>
     _LIBCPP_CONSTEXPR_IF_NODEBUG friend
     __wrap_iter<_Iter1>
     operator+(typename __wrap_iter<_Iter1>::difference_type, __wrap_iter<_Iter1>) _NOEXCEPT;
 
     template <class _Ip, class _Op> friend _LIBCPP_CONSTEXPR_AFTER_CXX17 _Op copy(_Ip, _Ip, _Op);
     template <class _B1, class _B2> friend _LIBCPP_CONSTEXPR_AFTER_CXX17 _B2 copy_backward(_B1, _B1, _B2);
-    template <class _Ip, class _Op> friend _Op move(_Ip, _Ip, _Op);
-    template <class _B1, class _B2> friend _B2 move_backward(_B1, _B1, _B2);
+    template <class _Ip, class _Op> friend _LIBCPP_CONSTEXPR_AFTER_CXX17 _Op move(_Ip, _Ip, _Op);
+    template <class _B1, class _B2> friend _LIBCPP_CONSTEXPR_AFTER_CXX17 _B2 move_backward(_B1, _B1, _B2);
 
 #if _LIBCPP_DEBUG_LEVEL < 2
     template <class _Tp>
-    _LIBCPP_CONSTEXPR_IF_NODEBUG friend
+    _LIBCPP_CONSTEXPR friend
     typename enable_if
     <
         is_trivially_copy_assignable<_Tp>::value,
         _Tp*
     >::type
     __unwrap_iter(__wrap_iter<_Tp*>);
 #else
   template <class _Tp>
-  inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG
+  inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
   typename enable_if
   <
       is_trivially_copy_assignable<_Tp>::value,
       __wrap_iter<_Tp*>
   >::type
   __unwrap_iter(__wrap_iter<_Tp*> __i);
 #endif
 };

libcxx/test/std/algorithms/alg.modifying.operations/alg.move/move.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<InputIterator InIter, typename OutIter>
 //   requires OutputIterator<OutIter, RvalueOf<InIter::reference>::type>
 //   OutIter
 //   move(InIter first, InIter last, OutIter result);
 
+// UNSUPPORTED: clang-6, clang-7
+// UNSUPPORTED: apple-clang-9, apple-clang-10, apple-clang-11
+// UNSUPPORTED: gcc-5, gcc-6, gcc-7, gcc-8
+
 #include <algorithm>
 #include <cassert>
 #include <memory>
 
 #include "test_macros.h"
 #include "test_iterators.h"
 
 template <class InIter, class OutIter>
-void
+_LIBCPP_CONSTEXPR_AFTER_CXX17 bool
 test()
 {
     const unsigned N = 1000;
-    int ia[N];
+    int ia[N] = {};
     for (unsigned i = 0; i < N; ++i)
         ia[i] = i;
     int ib[N] = {0};
 
     OutIter r = std::move(InIter(ia), InIter(ia+N), OutIter(ib));
     assert(base(r) == ib+N);
     for (unsigned i = 0; i < N; ++i)
         assert(ia[i] == ib[i]);
+
+    return true;
 }
 
 #if TEST_STD_VER >= 11
 template <class InIter, class OutIter>
 void
 test1()
 {
     const unsigned N = 100;
#if TEST_STD_VER >= 11
     test1<std::unique_ptr<int>*, output_iterator<std::unique_ptr<int>*> >();
     test1<std::unique_ptr<int>*, input_iterator<std::unique_ptr<int>*> >();
     test1<std::unique_ptr<int>*, forward_iterator<std::unique_ptr<int>*> >();
     test1<std::unique_ptr<int>*, bidirectional_iterator<std::unique_ptr<int>*> >();
     test1<std::unique_ptr<int>*, random_access_iterator<std::unique_ptr<int>*> >();
     test1<std::unique_ptr<int>*, std::unique_ptr<int>*>();
 #endif // TEST_STD_VER >= 11
 
+#if TEST_STD_VER > 17
+    static_assert(test<input_iterator<const int*>, input_iterator<int*> >());
+    static_assert(test<input_iterator<const int*>, forward_iterator<int*> >());
+    static_assert(test<input_iterator<const int*>, bidirectional_iterator<int*> >());
+    static_assert(test<input_iterator<const int*>, random_access_iterator<int*> >());
+    static_assert(test<input_iterator<const int*>, int*>());
+
+    static_assert(test<forward_iterator<const int*>, input_iterator<int*> >());
+    static_assert(test<forward_iterator<const int*>, forward_iterator<int*> >());
+    static_assert(test<forward_iterator<const int*>, bidirectional_iterator<int*> >());
+    static_assert(test<forward_iterator<const int*>, random_access_iterator<int*> >());
+    static_assert(test<forward_iterator<const int*>, int*>());
+
+    static_assert(test<bidirectional_iterator<const int*>, input_iterator<int*> >());
+    static_assert(test<bidirectional_iterator<const int*>, forward_iterator<int*> >());
+    static_assert(test<bidirectional_iterator<const int*>, bidirectional_iterator<int*> >());
+    static_assert(test<bidirectional_iterator<const int*>, random_access_iterator<int*> >());
+    static_assert(test<bidirectional_iterator<const int*>, int*>());
+
+    static_assert(test<random_access_iterator<const int*>, input_iterator<int*> >());
+    static_assert(test<random_access_iterator<const int*>, forward_iterator<int*> >());
+    static_assert(test<random_access_iterator<const int*>, bidirectional_iterator<int*> >());
+    static_assert(test<random_access_iterator<const int*>, random_access_iterator<int*> >());
+    static_assert(test<random_access_iterator<const int*>, int*>());
+
+    static_assert(test<const int*, input_iterator<int*> >());
+    static_assert(test<const int*, forward_iterator<int*> >());
+    static_assert(test<const int*, bidirectional_iterator<int*> >());
+    static_assert(test<const int*, random_access_iterator<int*> >());
+    static_assert(test<const int*, int*>());
+#endif  // TEST_STD_VER > 17
+
   return 0;
 }

libcxx/test/std/algorithms/alg.modifying.operations/alg.move/move_backward.pass.cpp

 #include <algorithm>
 #include <cassert>
 #include <memory>
 
 #include "test_macros.h"
 #include "test_iterators.h"
 
 template <class InIter, class OutIter>
-void
+_LIBCPP_CONSTEXPR_AFTER_CXX17 bool
 test()
 {
     const unsigned N = 1000;
-    int ia[N];
+    int ia[N] = {};
     for (unsigned i = 0; i < N; ++i)
         ia[i] = i;
     int ib[N] = {0};
 
     OutIter r = std::move_backward(InIter(ia), InIter(ia+N), OutIter(ib+N));
     assert(base(r) == ib);
     for (unsigned i = 0; i < N; ++i)
         assert(ia[i] == ib[i]);
+
+    return true;
 }
 
 #if TEST_STD_VER >= 11
 template <class InIter, class OutIter>
 void
 test1()
 {
     const unsigned N = 100;
#if TEST_STD_VER >= 11
     test1<random_access_iterator<std::unique_ptr<int>*>, random_access_iterator<std::unique_ptr<int>*> >();
     test1<random_access_iterator<std::unique_ptr<int>*>, std::unique_ptr<int>*>();
 
     test1<std::unique_ptr<int>*, bidirectional_iterator<std::unique_ptr<int>*> >();
     test1<std::unique_ptr<int>*, random_access_iterator<std::unique_ptr<int>*> >();
     test1<std::unique_ptr<int>*, std::unique_ptr<int>*>();
 #endif // TEST_STD_VER >= 11
 
+#if TEST_STD_VER > 17
+    static_assert(test<bidirectional_iterator<const int*>, bidirectional_iterator<int*> >());
+    static_assert(test<bidirectional_iterator<const int*>, random_access_iterator<int*> >());
+    static_assert(test<bidirectional_iterator<const int*>, int*>());
+
+    static_assert(test<random_access_iterator<const int*>, bidirectional_iterator<int*> >());
+    static_assert(test<random_access_iterator<const int*>, random_access_iterator<int*> >());
+    static_assert(test<random_access_iterator<const int*>, int*>());
+
+    static_assert(test<const int*, bidirectional_iterator<int*> >());
+    static_assert(test<const int*, random_access_iterator<int*> >());
+    static_assert(test<const int*, int*>());
+#endif  // TEST_STD_VER > 17
+
   return 0;
 }

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

 #include <algorithm>
 #include <cassert>
 #include <memory>
 
 #include "test_macros.h"
 #include "test_iterators.h"
 
 template <class Iter>
-void
+_LIBCPP_CONSTEXPR_AFTER_CXX17 bool
 test()
 {
     int ia[] = {0};
     const int sa = static_cast<int>(sizeof(ia)/sizeof(ia[0]));
     Iter r = std::rotate(Iter(ia), Iter(ia), Iter(ia));
     assert(base(r) == ia);
     assert(ia[0] == 0);
     r = std::rotate(Iter(ia), Iter(ia), Iter(ia+sa));
test()
     r = std::rotate(Iter(ig), Iter(ig+sg), Iter(ig+sg));
     assert(base(r) == ig);
     assert(ig[0] == 3);
     assert(ig[1] == 4);
     assert(ig[2] == 5);
     assert(ig[3] == 0);
     assert(ig[4] == 1);
     assert(ig[5] == 2);
+
+    return true;
 }
 
 #if TEST_STD_VER >= 11
 
 template <class Iter>
 void
 test1()
 {
test1()
     assert(*ig[5] == 2);
 }
 
 #endif  // TEST_STD_VER >= 11
 
 int main(int, char**)
 {
     test<forward_iterator<int*> >();
     test<bidirectional_iterator<int*> >();
     test<random_access_iterator<int*> >();
     test<int*>();
 
 #if TEST_STD_VER >= 11
 
     test1<forward_iterator<std::unique_ptr<int>*> >();
     test1<bidirectional_iterator<std::unique_ptr<int>*> >();
     test1<random_access_iterator<std::unique_ptr<int>*> >();
     test1<std::unique_ptr<int>*>();
 
 #endif
 
+#if TEST_STD_VER > 17
+    static_assert(test<forward_iterator<int*> >());
+    static_assert(test<bidirectional_iterator<int*> >());
+    static_assert(test<random_access_iterator<int*> >());
+    static_assert(test<int*>());
+#endif  // TEST_STD_VER > 17
+
   return 0;
 }

libcxx/www/cxx2a_status.html

-->
   <tr><td><a href="https://wg21.link/P2116">P2116</a></td><td>LWG</td><td>Remove tuple-like protocol support from fixed-extent span</td><td>Prague</td><td>Complete</td><td>11.0</td></tr>
 <!--   <tr><td></td><td></td><td></td><td></td><td></td><td></td></tr> -->
   </table>
 
 <p><i>[ Note: "Nothing to do" means that no library changes were needed to implement this change -- end note]</i></p>
 
 <p>The missing bits in P0600 are in [mem.res.class], [mem.poly.allocator.class], and [container.node.overview]</p>
 
-<p>The missing bits in P0202 are in <tt>copy</tt>, <tt>copy_backwards</tt>, <tt>move</tt>, and <tt>move_backwards</tt> (and the ones that call them: <tt>copy_n</tt>, <tt>rotate_copy</tt>, <tt>merge</tt>, <tt>set_union</tt>, <tt>set_difference</tt>, and <tt>set_symmetric_difference</tt>). This is because the first four algorithms have specializations that call <tt>memmove</tt> which is not constexpr. See <a href="https://bugs.llvm.org/show_bug.cgi?id=25165">Bug 25165</a></p>
+<p>The missing bits in P0202 are in <tt>copy</tt> and <tt>copy_backwards</tt> (and the ones that call them: <tt>copy_n</tt>, <tt>rotate_copy</tt>, <tt>merge</tt>, <tt>set_union</tt>, <tt>set_difference</tt>, and <tt>set_symmetric_difference</tt>). This is because the first four algorithms have specializations that call <tt>memmove</tt> which is not constexpr. See <a href="https://bugs.llvm.org/show_bug.cgi?id=25165">Bug 25165</a></p>
 
 
   <h3>Library Working group Issues Status</h3>
 <!--   <I>Note: "NAD" means that the issue was deemed "Not a defect"</I> -->
   <table id="issues" border="1">
   <tr><th>Issue #</th><th>Issue Name</th><th>Meeting</th><th>Status</th></tr>
 <!--
   <tr><td><a href="https://wg21.link/LWG1214">1214</a></td><td>Insufficient/inconsistent key immutability requirements for associative containers</td><td>Urbana</td><td></td></tr>