[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/docs/Cxx2aStatusIssuesStatus.csv

 "`3221 <https://wg21.link/LWG3221>`__","Result of ``year_month``\  arithmetic with ``months``\  is ambiguous","Belfast","|Complete|","8.0"
 "`3235 <https://wg21.link/LWG3235>`__","``parse``\  manipulator without abbreviation is not callable","Belfast","",""
 "`3246 <https://wg21.link/LWG3246>`__","What are the constraints on the template parameter of ``basic_format_arg``\ ?","Belfast","",""
 "`3253 <https://wg21.link/LWG3253>`__","``basic_syncbuf::basic_syncbuf()``\  should not be explicit","Belfast","",""
 "`3245 <https://wg21.link/LWG3245>`__","Unnecessary restriction on ``'%p'``\  parse specifier","Belfast","",""
 "`3244 <https://wg21.link/LWG3244>`__","Constraints for ``Source``\  in |sect|\ [fs.path.req] insufficiently constrainty","Belfast","",""
 "`3241 <https://wg21.link/LWG3241>`__","``chrono-spec``\  grammar ambiguity in |sect|\ [time.format]","Belfast","",""
 "`3257 <https://wg21.link/LWG3257>`__","Missing feature testing macro update from P0858","Belfast","",""
-"`3256 <https://wg21.link/LWG3256>`__","Feature testing macro for ``constexpr``\  algorithms","Belfast","",""
+"`3256 <https://wg21.link/LWG3256>`__","Feature testing macro for ``constexpr``\  algorithms","Belfast","|Complete|","13.0"
 "`3273 <https://wg21.link/LWG3273>`__","Specify ``weekday_indexed``\  to range of ``[0, 7]``\ ","Belfast","",""
 "`3070 <https://wg21.link/LWG3070>`__","``path::lexically_relative``\  causes surprising results if a filename can also be a  *root-name*","Belfast","",""
 "`3266 <https://wg21.link/LWG3266>`__","``to_chars(bool)``\  should be deleted","Belfast","",""
 "`3272 <https://wg21.link/LWG3272>`__","``%I%p``\  should parse/format ``duration``\  since midnight","Belfast","",""
 "`3259 <https://wg21.link/LWG3259>`__","The definition of *constexpr iterators* should be adjusted","Belfast","",""
 "`3103 <https://wg21.link/LWG3103>`__","Errors in taking subview of ``span``\  should be ill-formed where possible","Belfast","",""
 "`3274 <https://wg21.link/LWG3274>`__","Missing feature test macro for ``<span>``\ ","Belfast","",""
 "`3276 <https://wg21.link/LWG3276>`__","Class ``split_view::outer_iterator::value_type``\  should inherit from ``view_interface``\ ","Belfast","",""

libcxx/docs/Cxx2aStatusPaperStatus.csv

 "`P0556R3 <https://wg21.link/P0556R3>`__","LWG","Integral power-of-2 operations","Rapperswil","|Complete|","9.0"
 "`P0619R4 <https://wg21.link/P0619R4>`__","LWG","Reviewing Deprecated Facilities of C++17 for C++20","Rapperswil","|Partial| [#note-P0619]_",""
 "`P0646R1 <https://wg21.link/P0646R1>`__","LWG","Improving the Return Value of Erase-Like Algorithms","Rapperswil","|Complete|","10.0"
 "`P0722R3 <https://wg21.link/P0722R3>`__","CWG","Efficient sized delete for variable sized classes","Rapperswil","|Complete|","9.0"
 "`P0758R1 <https://wg21.link/P0758R1>`__","LWG","Implicit conversion traits and utility functions","Rapperswil","|Complete|",""
 "`P0759R1 <https://wg21.link/P0759R1>`__","LWG","fpos Requirements","Rapperswil","|Complete|","11.0"
 "`P0769R2 <https://wg21.link/P0769R2>`__","LWG","Add shift to <algorithm>","Rapperswil","|Complete|","12.0"
 "`P0788R3 <https://wg21.link/P0788R3>`__","LWG","Standard Library Specification in a Concepts and Contracts World","Rapperswil","*Removed in Cologne*","n/a"
-"`P0879R0 <https://wg21.link/P0879R0>`__","LWG","Constexpr for swap and swap related functions Also resolves LWG issue 2800.","Rapperswil","",""
+"`P0879R0 <https://wg21.link/P0879R0>`__","LWG","Constexpr for swap and swap related functions Also resolves LWG issue 2800.","Rapperswil","|Complete|","13.0"
 "`P0887R1 <https://wg21.link/P0887R1>`__","LWG","The identity metafunction","Rapperswil","|Complete|","8.0"
 "`P0892R2 <https://wg21.link/P0892R2>`__","CWG","explicit(bool)","Rapperswil","",""
 "`P0898R3 <https://wg21.link/P0898R3>`__","LWG","Standard Library Concepts","Rapperswil","|In Progress|",""
 "`P0935R0 <https://wg21.link/P0935R0>`__","LWG","Eradicating unnecessarily explicit default constructors from the standard library","Rapperswil","|Complete|","12.0"
 "`P0941R2 <https://wg21.link/P0941R2>`__","CWG","Integrating feature-test macros into the C++ WD","Rapperswil","|In Progress|",""
 "`P1023R0 <https://wg21.link/P1023R0>`__","LWG","constexpr comparison operators for std::array","Rapperswil","|Complete|","8.0"
 "`P1025R1 <https://wg21.link/P1025R1>`__","CWG","Update The Reference To The Unicode Standard","Rapperswil","",""
 "`P1120R0 <https://wg21.link/P1120R0>`__","CWG","Consistency improvements for <=> and other comparison operators","Rapperswil","",""

libcxx/docs/FeatureTestMacroTable.rst

.. table:: Current Status
     ``__cpp_lib_bitops``                              *unimplemented*
     ------------------------------------------------- -----------------
     ``__cpp_lib_bounded_array_traits``                ``201902L``
     ------------------------------------------------- -----------------
     ``__cpp_lib_char8_t``                             ``201811L``
     ------------------------------------------------- -----------------
     ``__cpp_lib_concepts``                            *unimplemented*
     ------------------------------------------------- -----------------
-    ``__cpp_lib_constexpr_algorithms``                *unimplemented*
+    ``__cpp_lib_constexpr_algorithms``                ``201806L``
     ------------------------------------------------- -----------------
     ``__cpp_lib_constexpr_complex``                   *unimplemented*
     ------------------------------------------------- -----------------
     ``__cpp_lib_constexpr_dynamic_alloc``             ``201907L``
     ------------------------------------------------- -----------------
     ``__cpp_lib_constexpr_functional``                ``201907L``
     ------------------------------------------------- -----------------
     ``__cpp_lib_constexpr_iterator``                  *unimplemented*

libcxx/include/__memory/pointer_traits.h

 struct __rebind_pointer {
 #ifndef _LIBCPP_CXX03_LANG
     typedef typename pointer_traits<_From>::template rebind<_To>        type;
 #else
     typedef typename pointer_traits<_From>::template rebind<_To>::other type;
 #endif
 };
 
+// to_address
+
+template <bool _UsePointerTraits> struct __to_address_helper;
+
+template <> struct __to_address_helper<true> {
+    template <class _Pointer>
+    using __return_type = decltype(pointer_traits<_Pointer>::to_address(_VSTD::declval<const _Pointer&>()));
+
+    template <class _Pointer>
+    _LIBCPP_CONSTEXPR
+    static __return_type<_Pointer>
+    __do_it(const _Pointer &__p) _NOEXCEPT { return pointer_traits<_Pointer>::to_address(__p); }
+};
+
+template <class _Pointer, bool _Dummy = true>
+using __choose_to_address = __to_address_helper<_IsValidExpansion<__to_address_helper<_Dummy>::template __return_type, _Pointer>::value>;
+
+template <class _Tp>
+inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
+_Tp*
+__to_address(_Tp* __p) _NOEXCEPT
+{
+    static_assert(!is_function<_Tp>::value, "_Tp is a function type");
+    return __p;
+}
+
+template <class _Pointer>
+inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
+typename __choose_to_address<_Pointer>::template __return_type<_Pointer>
+__to_address(const _Pointer& __p) _NOEXCEPT
+{
+    return __choose_to_address<_Pointer>::__do_it(__p);
+}
+
+template <> struct __to_address_helper<false> {
+    template <class _Pointer>
+    using __return_type = typename pointer_traits<_Pointer>::element_type*;
+
+    template <class _Pointer>
+    _LIBCPP_CONSTEXPR
+    static __return_type<_Pointer>
+    __do_it(const _Pointer &__p) _NOEXCEPT { return _VSTD::__to_address(__p.operator->()); }
+};
+
+
+#if _LIBCPP_STD_VER > 17
+template <class _Tp>
+inline _LIBCPP_INLINE_VISIBILITY constexpr
+_Tp*
+to_address(_Tp* __p) _NOEXCEPT
+{
+    static_assert(!is_function_v<_Tp>, "_Tp is a function type");
+    return __p;
+}
+
+template <class _Pointer>
+inline _LIBCPP_INLINE_VISIBILITY constexpr
+auto
+to_address(const _Pointer& __p) _NOEXCEPT
+{
+    return _VSTD::__to_address(__p);
+}
+#endif
+
 _LIBCPP_END_NAMESPACE_STD
 
 _LIBCPP_POP_MACROS
 
 #endif  // _LIBCPP___MEMORY_POINTER_TRAITS_H

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

 _ForwardIterator
 search_n(_ForwardIterator __first, _ForwardIterator __last, _Size __count, const _Tp& __value_)
 {
     typedef typename iterator_traits<_ForwardIterator>::value_type __v;
     return _VSTD::search_n(__first, __last, _VSTD::__convert_to_integral(__count),
                            __value_, __equal_to<__v, _Tp>());
 }
 
-// copy
-template <class _Iter>
-inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
-_Iter
-__unwrap_iter(_Iter __i)
-{
-    return __i;
-}
+// __unwrap_iter
 
-template <class _Tp>
-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();
-}
+// The job of __unwrap_iter is to lower iterators-that-are-tantamount-to-pointers
+// (such as vector<T>::iterator) into pointers, to reduce the number of template
+// instantiations and to enable pointer-based optimizations e.g. in std::copy.
+// In debug mode, we don't do this.
 
-#if _LIBCPP_DEBUG_LEVEL < 2
+template <class _Iter, bool = __is_cpp17_contiguous_iterator<_Iter>::value>
+struct __unwrap_iter_impl {
+    static _LIBCPP_CONSTEXPR _Iter
+    __apply(_Iter __i) _NOEXCEPT {
+        return __i;
+    }
+};
 
-template <class _Tp>
-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();
-}
+#if _LIBCPP_DEBUG_LEVEL < 2
 
-template <class _Tp>
-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();
-}
+template <class _Iter>
+struct __unwrap_iter_impl<_Iter, true> {
+    static _LIBCPP_CONSTEXPR decltype(_VSTD::__to_address(declval<_Iter>()))
+    __apply(_Iter __i) _NOEXCEPT {
+        return _VSTD::__to_address(__i);
+    }
+};
 
-#else
+#endif  // _LIBCPP_DEBUG_LEVEL < 2
 
-template <class _Tp>
+template<class _Iter, class _Impl = __unwrap_iter_impl<_Iter> >
 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)
+decltype(_Impl::__apply(_VSTD::declval<_Iter>()))
+__unwrap_iter(_Iter __i) _NOEXCEPT
 {
-    return __i;
+    return _Impl::__apply(__i);
 }
 
-#endif  // _LIBCPP_DEBUG_LEVEL < 2
+// copy
 
 template <class _InputIterator, class _OutputIterator>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 _OutputIterator
 __copy_constexpr(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
 {
     for (; __first != __last; ++__first, (void) ++__result)
         *__result = *__first;

     return _VSTD::__move_constexpr(__first, __last, __result);
 }
 
 template <class _Tp, class _Up>
 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,
+    is_trivially_move_assignable<_Up>::value,
     _Up*
 >::type
 __move(_Tp* __first, _Tp* __last, _Up* __result)
 {
     if (__libcpp_is_constant_evaluated())
         return _VSTD::__move_constexpr(__first, __last, __result);
     const size_t __n = static_cast<size_t>(__last - __first);
     if (__n > 0)

     return _VSTD::__move_backward_constexpr(__first, __last, __result);
 }
 
 template <class _Tp, class _Up>
 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,
+    is_trivially_move_assignable<_Up>::value,
     _Up*
 >::type
 __move_backward(_Tp* __first, _Tp* __last, _Up* __result)
 {
     if (__libcpp_is_constant_evaluated())
         return _VSTD::__move_backward_constexpr(__first, __last, __result);
     const size_t __n = static_cast<size_t>(__last - __first);
     if (__n > 0)

 void
 __insertion_sort(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
 {
     typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
     if (__first != __last)
     {
         _BidirectionalIterator __i = __first;
         for (++__i; __i != __last; ++__i)
         {
             _BidirectionalIterator __j = __i;
             value_type __t(_VSTD::move(*__j));
             for (_BidirectionalIterator __k = __i; __k != __first && __comp(__t,  *--__k); --__j)
                 *__j = _VSTD::move(*__k);
             *__j = _VSTD::move(__t);
         }
     }
 }

         __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;

                     // [__first, __i) == *__first and *__first < [__j, __last) and __j == __last - 1
                     if (__i == __j)
                         return;
                     while (true)
                     {
                         while (!__comp(*__first, *__i))
                             ++__i;
                         while (__comp(*__first, *--__j))
                             ;
                         if (__i >= __j)
                             break;
                         swap(*__i, *__j);
                         ++__n_swaps;
                         ++__i;
                     }
                     // [__first, __i) == *__first and *__first < [__i, __last)
                     // The first part is sorted, sort the second part

         {
             _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>&))

 template<class _Compare, class _RandomAccessIterator>
 _LIBCPP_CONSTEXPR_AFTER_CXX11 bool
 __nth_element_partloop(_RandomAccessIterator __first, _RandomAccessIterator __last,
                        _RandomAccessIterator& __i, _RandomAccessIterator& __j,
                        unsigned& __n_swaps, _Compare __comp)
 {
     // *__first == *__m, *__m <= all other elements
     // Partition instead into [__first, __i) == *__first and *__first < [__i, __last)
     ++__i;  // __first + 1
     __j = __last;
     if (!__comp(*__first, *--__j))  // we need a guard if *__first == *(__last-1)
     {
         while (true)
         {
             if (__i == __j)
                 return true;  // [__first, __last) all equivalent elements
             if (__comp(*__first, *__i))

                 while (__comp(*__i, *__m))
                     ++__i;
                 // It is now known that a guard exists for downward moving __j
                 while (!__comp(*--__j, *__m))
                     ;
                 if (__i >= __j)
                     break;
                 swap(*__i, *__j);
                 ++__n_swaps;
                 // It is known that __m != __j
                 // If __m just moved, follow it
                 if (__m == __i)
                     __m = __j;
                 ++__i;
             }
         }
         // [__first, __i) < *__m and *__m <= [__i, __last)

 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 _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;
+    if (__libcpp_is_constant_evaluated()) {
+        _VSTD::__partial_sort<_Comp_ref>(__first, __last, __last, _Comp_ref(__comp));
+    } else {
+        _VSTD::__sort<_Comp_ref>(_VSTD::__unwrap_iter(__first), _VSTD::__unwrap_iter(__last), _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)

     return _VSTD::__includes<_Comp_ref>(__first1, __last1, __first2, __last2, __comp);
 }
 
 template <class _InputIterator1, class _InputIterator2>
 _LIBCPP_NODISCARD_EXT inline
 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 bool
 includes(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2)
 {
     return _VSTD::includes(__first1, __last1, __first2, __last2,
                           __less<typename iterator_traits<_InputIterator1>::value_type,
                                  typename iterator_traits<_InputIterator2>::value_type>());
 }
 
 // set_union
 
 template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>

libcxx/include/filesystem

 #ifndef _LIBCPP_NO_HAS_CHAR8_T
       is_same<typename __is_pathable<_Source>::__char_type, char8_t>::value ||
 #endif
       is_same<typename __is_pathable<_Source>::__char_type, char>::value,
       "u8path(Source const&) requires Source have a character type of type "
       "'char' or 'char8_t'");
 #if defined(_LIBCPP_WIN32API)
   using _Traits = __is_pathable<_Source>;
-  return u8path(__unwrap_iter(_Traits::__range_begin(__s)), __unwrap_iter(_Traits::__range_end(__s)));
+  return u8path(_VSTD::__unwrap_iter(_Traits::__range_begin(__s)), _VSTD::__unwrap_iter(_Traits::__range_end(__s)));
 #else
   return path(__s);
 #endif
 }
 
 class _LIBCPP_TYPE_VIS path::iterator {
 public:
   enum _ParserState : unsigned char {

libcxx/include/iterator

 
 #include <__config>
 #include <iosfwd> // for forward declarations of vector and string.
 #include <__functional_base>
 #include <type_traits>
 #include <cstddef>
 #include <initializer_list>
 #include <__memory/base.h>
+#include <__memory/pointer_traits.h>
 #include <version>
 
 #include <__debug>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 template <class _Iter>
 struct _LIBCPP_TEMPLATE_VIS iterator_traits;
 
 struct _LIBCPP_TEMPLATE_VIS input_iterator_tag {};
 struct _LIBCPP_TEMPLATE_VIS output_iterator_tag {};
 struct _LIBCPP_TEMPLATE_VIS forward_iterator_tag       : public input_iterator_tag {};
 struct _LIBCPP_TEMPLATE_VIS bidirectional_iterator_tag : public forward_iterator_tag {};
 struct _LIBCPP_TEMPLATE_VIS random_access_iterator_tag : public bidirectional_iterator_tag {};
 #if _LIBCPP_STD_VER > 17
-// TODO(EricWF)  contiguous_iterator_tag is provided as an extension prior to
-//  C++20 to allow optimizations for users providing wrapped iterator types.
-struct _LIBCPP_TEMPLATE_VIS contiguous_iterator_tag: public random_access_iterator_tag { };
+struct _LIBCPP_TEMPLATE_VIS contiguous_iterator_tag    : public random_access_iterator_tag {};
 #endif
 
 template <class _Iter>
 struct __iter_traits_cache {
   using type = _If<
     __is_primary_template<iterator_traits<_Iter> >::value,
     _Iter,
     iterator_traits<_Iter>

 private:
     struct __two {char __lx; char __lxx;};
     template <class _Up> static __two __test(...);
     template <class _Up> static char __test(typename _Up::iterator_category* = nullptr);
 public:
     static const bool value = sizeof(__test<_Tp>(nullptr)) == 1;
 };
 
+template <class _Tp>
+struct __has_iterator_concept
+{
+private:
+    struct __two {char __lx; char __lxx;};
+    template <class _Up> static __two __test(...);
+    template <class _Up> static char __test(typename _Up::iterator_concept* = nullptr);
+public:
+    static const bool value = sizeof(__test<_Tp>(nullptr)) == 1;
+};
+
 template <class _Iter, bool> struct __iterator_traits_impl {};
 
 template <class _Iter>
 struct __iterator_traits_impl<_Iter, true>
 {
     typedef typename _Iter::difference_type   difference_type;
     typedef typename _Iter::value_type        value_type;
     typedef typename _Iter::pointer           pointer;
struct _LIBCPP_TEMPLATE_VIS iterator_traits<_Tp*>
     typedef random_access_iterator_tag iterator_category;
 #if _LIBCPP_STD_VER > 17
     typedef contiguous_iterator_tag    iterator_concept;
 #endif
 };
 
 template <class _Tp, class _Up, bool = __has_iterator_category<iterator_traits<_Tp> >::value>
 struct __has_iterator_category_convertible_to
-    : public integral_constant<bool, is_convertible<typename iterator_traits<_Tp>::iterator_category, _Up>::value>
+    : _BoolConstant<is_convertible<typename iterator_traits<_Tp>::iterator_category, _Up>::value>
+{};
+
+template <class _Tp, class _Up>
+struct __has_iterator_category_convertible_to<_Tp, _Up, false> : false_type {};
+
+template <class _Tp, class _Up, bool = __has_iterator_concept<_Tp>::value>
+struct __has_iterator_concept_convertible_to
+    : _BoolConstant<is_convertible<typename _Tp::iterator_concept, _Up>::value>
 {};
 
 template <class _Tp, class _Up>
-struct __has_iterator_category_convertible_to<_Tp, _Up, false> : public false_type {};
+struct __has_iterator_concept_convertible_to<_Tp, _Up, false> : false_type {};
 
 template <class _Tp>
 struct __is_cpp17_input_iterator : public __has_iterator_category_convertible_to<_Tp, input_iterator_tag> {};
 
 template <class _Tp>
 struct __is_cpp17_forward_iterator : public __has_iterator_category_convertible_to<_Tp, forward_iterator_tag> {};
 
 template <class _Tp>
 struct __is_cpp17_bidirectional_iterator : public __has_iterator_category_convertible_to<_Tp, bidirectional_iterator_tag> {};
 
 template <class _Tp>
 struct __is_cpp17_random_access_iterator : public __has_iterator_category_convertible_to<_Tp, random_access_iterator_tag> {};
 
 #if _LIBCPP_STD_VER > 17
 template <class _Tp>
-struct __is_cpp17_contiguous_iterator : public __has_iterator_category_convertible_to<_Tp, contiguous_iterator_tag> {};
+struct __is_cpp17_contiguous_iterator : _Or<
+    __has_iterator_category_convertible_to<_Tp, contiguous_iterator_tag>,
+    __has_iterator_concept_convertible_to<_Tp, contiguous_iterator_tag>
+> {};
 #else
 template <class _Tp>
-struct __is_cpp17_contiguous_iterator : public false_type {};
+struct __is_cpp17_contiguous_iterator : false_type {};
 #endif
 
+// Any native pointer which is an iterator is also a contiguous iterator.
+template <class _Up>
+struct __is_cpp17_contiguous_iterator<_Up*> : true_type {};
+
 
 template <class _Tp>
 struct __is_exactly_cpp17_input_iterator
     : public integral_constant<bool,
          __has_iterator_category_convertible_to<_Tp, input_iterator_tag>::value &&
         !__has_iterator_category_convertible_to<_Tp, forward_iterator_tag>::value> {};
 
 #ifndef _LIBCPP_HAS_NO_DEDUCTION_GUIDES

 
 protected:
     _Iter current;
 public:
     typedef _Iter                                            iterator_type;
     typedef typename iterator_traits<_Iter>::difference_type difference_type;
     typedef typename iterator_traits<_Iter>::reference       reference;
     typedef typename iterator_traits<_Iter>::pointer         pointer;
+    typedef _If<__is_cpp17_random_access_iterator<_Iter>::value,
+        random_access_iterator_tag,
+        typename iterator_traits<_Iter>::iterator_category>  iterator_category;
+    typedef _If<__is_cpp17_random_access_iterator<_Iter>::value,
+        random_access_iterator_tag,
+        bidirectional_iterator_tag>                          iterator_concept;
 
     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
     reverse_iterator() : __t(), current() {}
     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
     explicit reverse_iterator(_Iter __x) : __t(__x), current(__x) {}
     template <class _Up>
         _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
         reverse_iterator(const reverse_iterator<_Up>& __u) : __t(__u.base()), current(__u.base()) {}

 
 template <class _Iter>
 class _LIBCPP_TEMPLATE_VIS move_iterator
 {
 private:
     _Iter __i;
 public:
     typedef _Iter                                            iterator_type;
-    typedef typename iterator_traits<iterator_type>::iterator_category iterator_category;
     typedef typename iterator_traits<iterator_type>::value_type value_type;
     typedef typename iterator_traits<iterator_type>::difference_type difference_type;
     typedef iterator_type pointer;
+    typedef _If<__is_cpp17_random_access_iterator<_Iter>::value,
+        random_access_iterator_tag,
+        typename iterator_traits<_Iter>::iterator_category>  iterator_category;
+    typedef input_iterator_tag                               iterator_concept;
+
 #ifndef _LIBCPP_CXX03_LANG
     typedef typename iterator_traits<iterator_type>::reference __reference;
     typedef typename conditional<
             is_reference<__reference>::value,
             typename remove_reference<__reference>::type&&,
             __reference
         >::type reference;
 #else

 __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 _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
-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
-typename enable_if
-<
-    is_trivially_copy_assignable<_Tp>::value,
-    __wrap_iter<_Tp*>
->::type
-__unwrap_iter(__wrap_iter<_Tp*> __i);
-
-#endif
-
 template <class _Iter>
 class __wrap_iter
 {
 public:
     typedef _Iter                                                      iterator_type;
-    typedef typename iterator_traits<iterator_type>::iterator_category iterator_category;
     typedef typename iterator_traits<iterator_type>::value_type        value_type;
     typedef typename iterator_traits<iterator_type>::difference_type   difference_type;
     typedef typename iterator_traits<iterator_type>::pointer           pointer;
     typedef typename iterator_traits<iterator_type>::reference         reference;
+    typedef typename iterator_traits<iterator_type>::iterator_category iterator_category;
+#if _LIBCPP_STD_VER > 17
+    typedef _If<__is_cpp17_contiguous_iterator<_Iter>::value,
+                contiguous_iterator_tag, iterator_category>            iterator_concept;
+#endif
 private:
     iterator_type __i;
 public:
     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG __wrap_iter() _NOEXCEPT
 #if _LIBCPP_STD_VER > 11
                 : __i{}
 #endif
     {
#endif
     _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 _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 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 friend
-  typename enable_if
-  <
-      is_trivially_copy_assignable<_Tp>::value,
-      __wrap_iter<_Tp*>
-  >::type
-  __unwrap_iter(__wrap_iter<_Tp*> __i);
+#if _LIBCPP_STD_VER <= 17
+template <class _It>
+struct __is_cpp17_contiguous_iterator<__wrap_iter<_It> > : __is_cpp17_contiguous_iterator<_It> {};
 #endif
-};
+
+template <class _Iter>
+_LIBCPP_CONSTEXPR
+_EnableIf<__is_cpp17_contiguous_iterator<_Iter>::value, decltype(_VSTD::__to_address(declval<_Iter>()))>
+__to_address(__wrap_iter<_Iter> __w) _NOEXCEPT {
+    return _VSTD::__to_address(__w.base());
+}
 
 template <class _Iter1, class _Iter2>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG
 bool
 operator==(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT
 {
     return __x.base() == __y.base();
 }

libcxx/include/memory

#if !defined(_LIBCPP_HAS_NO_THREADS) && \
     defined(__ATOMIC_ACQUIRE) &&        \
     (__has_builtin(__atomic_load_n) || defined(_LIBCPP_COMPILER_GCC))
     return __atomic_load_n(__value, __ATOMIC_ACQUIRE);
 #else
     return *__value;
 #endif
 }
 
-template <bool _UsePointerTraits> struct __to_address_helper;
-
-template <> struct __to_address_helper<true> {
-    template <class _Pointer>
-    using __return_type = decltype(pointer_traits<_Pointer>::to_address(_VSTD::declval<const _Pointer&>()));
-
-    template <class _Pointer>
-    _LIBCPP_CONSTEXPR
-    static __return_type<_Pointer>
-    __do_it(const _Pointer &__p) _NOEXCEPT { return pointer_traits<_Pointer>::to_address(__p); }
-};
-
-template <class _Pointer, bool _Dummy = true>
-using __choose_to_address = __to_address_helper<_IsValidExpansion<__to_address_helper<_Dummy>::template __return_type, _Pointer>::value>;
-
-
-template <class _Tp>
-inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
-_Tp*
-__to_address(_Tp* __p) _NOEXCEPT
-{
-    static_assert(!is_function<_Tp>::value, "_Tp is a function type");
-    return __p;
-}
-
-template <class _Pointer>
-inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
-typename __choose_to_address<_Pointer>::template __return_type<_Pointer>
-__to_address(const _Pointer& __p) _NOEXCEPT {
-  return __choose_to_address<_Pointer>::__do_it(__p);
-}
-
-template <> struct __to_address_helper<false> {
-    template <class _Pointer>
-    using __return_type = typename pointer_traits<_Pointer>::element_type*;
-
-    template <class _Pointer>
-    _LIBCPP_CONSTEXPR
-    static __return_type<_Pointer>
-    __do_it(const _Pointer &__p) _NOEXCEPT { return _VSTD::__to_address(__p.operator->()); }
-};
-
-
-#if _LIBCPP_STD_VER > 17
-template <class _Tp>
-inline _LIBCPP_INLINE_VISIBILITY constexpr
-_Tp*
-to_address(_Tp* __p) _NOEXCEPT
-{
-    static_assert(!is_function_v<_Tp>, "_Tp is a function type");
-    return __p;
-}
-
-template <class _Pointer>
-inline _LIBCPP_INLINE_VISIBILITY constexpr
-auto
-to_address(const _Pointer& __p) _NOEXCEPT
-{
-    return _VSTD::__to_address(__p);
-}
-#endif
-
 template <class _Tp> class allocator;
 
 #if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_ALLOCATOR_MEMBERS)
 template <>
 class _LIBCPP_TEMPLATE_VIS _LIBCPP_DEPRECATED_IN_CXX17 allocator<void>
 {
 public:
     typedef void*             pointer;

libcxx/include/version

 // # define __cpp_lib_bind_front                           201907L
 // # define __cpp_lib_bit_cast                             201806L
 // # define __cpp_lib_bitops                               201907L
 # define __cpp_lib_bounded_array_traits                 201902L
 # if !defined(_LIBCPP_NO_HAS_CHAR8_T)
 #   define __cpp_lib_char8_t                            201811L
 # endif
 // # define __cpp_lib_concepts                             202002L
-// # define __cpp_lib_constexpr_algorithms                 201806L
+# define __cpp_lib_constexpr_algorithms                 201806L
 // # define __cpp_lib_constexpr_complex                    201711L
 # define __cpp_lib_constexpr_dynamic_alloc              201907L
 # define __cpp_lib_constexpr_functional                 201907L
 // # define __cpp_lib_constexpr_iterator                   201811L
 // # define __cpp_lib_constexpr_memory                     201811L
 # define __cpp_lib_constexpr_numeric                    201911L
 // # define __cpp_lib_constexpr_string                     201907L
 // # define __cpp_lib_constexpr_string_view                201811L

libcxx/test/libcxx/iterators/contiguous_iterators.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
+//
+//===----------------------------------------------------------------------===//
+//
+
+// <iterator>
+
+// __is_cpp17_contiguous_iterator<_Tp>
+
+// __is_cpp17_contiguous_iterator determines if an iterator is contiguous,
+// either because it advertises itself as such (in C++20) or because it
+// is a pointer type or a known trivial wrapper around a pointer type,
+// such as __wrap_iter<T*>.
+//
+
+#include <cassert>
+#include <deque>
+#include <initializer_list>
+#include <iterator>
+#include <string>
+#include <vector>
+
+#include "test_macros.h"
+#include "test_iterators.h"
+
+#if TEST_STD_VER >= 17
+#include <string_view>
+#endif
+
+#if TEST_STD_VER >= 20
+#include <span>
+#endif
+
+#if TEST_STD_VER >= 11
+#define DELETE_FUNCTION = delete
+#else
+#define DELETE_FUNCTION
+#endif
+
+class T;  // incomplete
+
+class my_input_iterator
+{
+    struct tag : std::input_iterator_tag {};
+    typedef my_input_iterator Self;
+    int *state_;
+public:
+    typedef tag iterator_category;
+    typedef int value_type;
+    typedef int difference_type;
+    typedef int* pointer;
+    typedef int& reference;
+
+    my_input_iterator();
+    reference operator*() const;
+    pointer operator->() const;
+
+    Self& operator++();
+    Self operator++(int);
+    friend bool operator==(const Self&, const Self&);
+    friend bool operator!=(const Self&, const Self&);
+};
+
+class my_random_access_iterator
+{
+    struct tag : std::random_access_iterator_tag {};
+    typedef my_random_access_iterator Self;
+    int *state_;
+public:
+    typedef tag iterator_category;
+    typedef int value_type;
+    typedef int difference_type;
+    typedef int* pointer;
+    typedef int& reference;
+
+    my_random_access_iterator();
+    reference operator*() const;
+    pointer operator->() const;
+    reference operator[](difference_type) const;
+
+    Self& operator++();
+    Self operator++(int);
+    Self& operator--();
+    Self operator--(int);
+    friend Self& operator+=(Self&, difference_type);
+    friend Self& operator-=(Self&, difference_type);
+    friend Self operator+(Self, difference_type);
+    friend Self operator+(difference_type, Self);
+    friend Self operator-(Self, difference_type);
+    friend difference_type operator-(Self, Self);
+    friend bool operator==(const Self&, const Self&);
+    friend bool operator!=(const Self&, const Self&);
+    friend bool operator<(const Self&, const Self&);
+    friend bool operator>(const Self&, const Self&);
+    friend bool operator<=(const Self&, const Self&);
+    friend bool operator>=(const Self&, const Self&);
+};
+
+#if TEST_STD_VER >= 20
+class my_contiguous_iterator
+{
+    struct tag : std::contiguous_iterator_tag {};
+    typedef my_contiguous_iterator Self;
+    int *state_;
+public:
+    typedef tag iterator_category;
+    typedef int value_type;
+    typedef int difference_type;
+    typedef int* pointer;
+    typedef int& reference;
+    typedef int element_type;  // enable to_address via pointer_traits
+
+    my_contiguous_iterator();
+    reference operator*() const;
+    pointer operator->() const;
+    reference operator[](difference_type) const;
+
+    Self& operator++();
+    Self operator++(int);
+    Self& operator--();
+    Self operator--(int);
+    friend Self& operator+=(Self&, difference_type);
+    friend Self& operator-=(Self&, difference_type);
+    friend Self operator+(Self, difference_type);
+    friend Self operator+(difference_type, Self);
+    friend Self operator-(Self, difference_type);
+    friend difference_type operator-(Self, Self);
+    friend bool operator==(const Self&, const Self&);
+    friend bool operator!=(const Self&, const Self&);
+    friend bool operator<(const Self&, const Self&);
+    friend bool operator>(const Self&, const Self&);
+    friend bool operator<=(const Self&, const Self&);
+    friend bool operator>=(const Self&, const Self&);
+};
+#endif
+
+int main(int, char**)
+{
+//  basic tests
+    static_assert(( std::__is_cpp17_contiguous_iterator<char *>::value), "");
+    static_assert(( std::__is_cpp17_contiguous_iterator<const char *>::value), "");
+    static_assert(( std::__is_cpp17_contiguous_iterator<int *>::value), "");
+    static_assert(( std::__is_cpp17_contiguous_iterator<int **>::value), "");
+    static_assert(( std::__is_cpp17_contiguous_iterator<T *>::value), "");
+
+    static_assert((!std::__is_cpp17_contiguous_iterator<my_input_iterator>::value), "");
+    static_assert((!std::__is_cpp17_contiguous_iterator<my_random_access_iterator>::value), "");
+#if TEST_STD_VER >= 20
+    static_assert(( std::__is_cpp17_contiguous_iterator<my_contiguous_iterator>::value), "");
+#endif
+
+    // move_iterator changes value category, which makes it pretty sketchy to use in optimized codepaths
+    static_assert((!std::__is_cpp17_contiguous_iterator<std::move_iterator<char *> >::value), "");
+    static_assert((!std::__is_cpp17_contiguous_iterator<std::move_iterator<const char *> >::value), "");
+    static_assert((!std::__is_cpp17_contiguous_iterator<std::move_iterator<int *> >::value), "");
+    static_assert((!std::__is_cpp17_contiguous_iterator<std::move_iterator<T *> >::value), "");
+    static_assert((!std::__is_cpp17_contiguous_iterator<std::move_iterator<my_random_access_iterator> >::value), "");
+#if TEST_STD_VER >= 20
+    static_assert((!std::__is_cpp17_contiguous_iterator<std::move_iterator<my_contiguous_iterator> >::value), "");
+#endif
+
+    static_assert((!std::__is_cpp17_contiguous_iterator<std::reverse_iterator<char *> >::value), "");
+    static_assert((!std::__is_cpp17_contiguous_iterator<std::reverse_iterator<const char *> >::value), "");
+    static_assert((!std::__is_cpp17_contiguous_iterator<std::reverse_iterator<int *> >::value), "");
+    static_assert((!std::__is_cpp17_contiguous_iterator<std::reverse_iterator<T *> >::value), "");
+    static_assert((!std::__is_cpp17_contiguous_iterator<std::reverse_iterator<my_random_access_iterator> >::value), "");
+#if TEST_STD_VER >= 20
+    static_assert((!std::__is_cpp17_contiguous_iterator<std::reverse_iterator<my_contiguous_iterator> >::value), "");
+#endif
+
+    static_assert(( std::__is_cpp17_contiguous_iterator<std::__wrap_iter<char *> >::value), "");
+    static_assert(( std::__is_cpp17_contiguous_iterator<std::__wrap_iter<const char *> >::value), "");
+    static_assert(( std::__is_cpp17_contiguous_iterator<std::__wrap_iter<int *> >::value), "");
+
+    static_assert(( std::__is_cpp17_contiguous_iterator<std::__wrap_iter<T *> >::value), "");
+    static_assert(( std::__is_cpp17_contiguous_iterator<std::__wrap_iter<std::__wrap_iter<T *> > >::value), "");
+    static_assert((!std::__is_cpp17_contiguous_iterator<std::__wrap_iter<std::reverse_iterator<T *> > >::value), "");
+
+    static_assert((!std::__is_cpp17_contiguous_iterator<std::__wrap_iter<my_random_access_iterator> >::value), "");
+    static_assert((!std::__is_cpp17_contiguous_iterator<std::__wrap_iter<std::__wrap_iter<my_random_access_iterator> > >::value), "");
+    static_assert((!std::__is_cpp17_contiguous_iterator<std::__wrap_iter<std::reverse_iterator<my_random_access_iterator> > >::value), "");
+
+#if TEST_STD_VER >= 20
+    static_assert(( std::__is_cpp17_contiguous_iterator<std::__wrap_iter<my_contiguous_iterator> >::value), "");
+    static_assert(( std::__is_cpp17_contiguous_iterator<std::__wrap_iter<std::__wrap_iter<my_contiguous_iterator> > >::value), "");
+    static_assert((!std::__is_cpp17_contiguous_iterator<std::__wrap_iter<std::reverse_iterator<my_contiguous_iterator> > >::value), "");
+#endif
+
+//  iterators in the libc++ test suite
+    static_assert((!std::__is_cpp17_contiguous_iterator<output_iterator       <char *> >::value), "");
+    static_assert((!std::__is_cpp17_contiguous_iterator<input_iterator        <char *> >::value), "");
+    static_assert((!std::__is_cpp17_contiguous_iterator<forward_iterator      <char *> >::value), "");
+    static_assert((!std::__is_cpp17_contiguous_iterator<bidirectional_iterator<char *> >::value), "");
+    static_assert((!std::__is_cpp17_contiguous_iterator<random_access_iterator<char *> >::value), "");
+#if TEST_STD_VER >= 20
+    static_assert(( std::__is_cpp17_contiguous_iterator<contiguous_iterator   <char *> >::value), "");
+#endif
+    static_assert((!std::__is_cpp17_contiguous_iterator<ThrowingIterator      <char *> >::value), "");
+    static_assert((!std::__is_cpp17_contiguous_iterator<NonThrowingIterator   <char *> >::value), "");
+
+//
+//  iterators from libc++'s containers
+//
+
+//  vector
+    static_assert(( std::__is_cpp17_contiguous_iterator<std::vector<int>::iterator>                   ::value), "");
+    static_assert(( std::__is_cpp17_contiguous_iterator<std::vector<int>::const_iterator>             ::value), "");
+    static_assert((!std::__is_cpp17_contiguous_iterator<std::vector<int>::reverse_iterator>           ::value), "");
+    static_assert((!std::__is_cpp17_contiguous_iterator<std::vector<int>::const_reverse_iterator>     ::value), "");
+    static_assert(( std::__is_cpp17_contiguous_iterator<std::__wrap_iter<std::vector<int>::iterator> >::value), "");
+
+//  string
+    static_assert(( std::__is_cpp17_contiguous_iterator<std::string::iterator>              ::value), "");
+    static_assert(( std::__is_cpp17_contiguous_iterator<std::string::const_iterator>        ::value), "");
+    static_assert((!std::__is_cpp17_contiguous_iterator<std::string::reverse_iterator>      ::value), "");
+    static_assert((!std::__is_cpp17_contiguous_iterator<std::string::const_reverse_iterator>::value), "");
+    static_assert(( std::__is_cpp17_contiguous_iterator<std::wstring::iterator>              ::value), "");
+    static_assert(( std::__is_cpp17_contiguous_iterator<std::wstring::const_iterator>        ::value), "");
+    static_assert((!std::__is_cpp17_contiguous_iterator<std::wstring::reverse_iterator>      ::value), "");
+    static_assert((!std::__is_cpp17_contiguous_iterator<std::wstring::const_reverse_iterator>::value), "");
+
+//  deque is random-access but not contiguous
+    static_assert((!std::__is_cpp17_contiguous_iterator<std::deque<int>::iterator>                   ::value), "");
+    static_assert((!std::__is_cpp17_contiguous_iterator<std::deque<int>::const_iterator>             ::value), "");
+    static_assert((!std::__is_cpp17_contiguous_iterator<std::deque<int>::reverse_iterator>           ::value), "");
+    static_assert((!std::__is_cpp17_contiguous_iterator<std::deque<int>::const_reverse_iterator>     ::value), "");
+    static_assert((!std::__is_cpp17_contiguous_iterator<std::__wrap_iter<std::deque<int>::iterator> >::value), "");
+
+//  vector<bool> is random-access but not contiguous
+    static_assert((!std::__is_cpp17_contiguous_iterator<std::vector<bool>::iterator>                   ::value), "");
+    static_assert((!std::__is_cpp17_contiguous_iterator<std::vector<bool>::const_iterator>             ::value), "");
+    static_assert((!std::__is_cpp17_contiguous_iterator<std::vector<bool>::reverse_iterator>           ::value), "");
+    static_assert((!std::__is_cpp17_contiguous_iterator<std::vector<bool>::const_reverse_iterator>     ::value), "");
+    static_assert((!std::__is_cpp17_contiguous_iterator<std::__wrap_iter<std::vector<bool>::iterator> >::value), "");
+
+#if TEST_STD_VER >= 11
+    static_assert(( std::__is_cpp17_contiguous_iterator<std::initializer_list<int>::iterator>      ::value), "");
+    static_assert(( std::__is_cpp17_contiguous_iterator<std::initializer_list<int>::const_iterator>::value), "");
+#endif
+
+#if TEST_STD_VER >= 17
+    static_assert(( std::__is_cpp17_contiguous_iterator<std::string_view::iterator>      ::value), "");
+    static_assert(( std::__is_cpp17_contiguous_iterator<std::string_view::const_iterator>::value), "");
+#endif
+
+#if TEST_STD_VER >= 20
+    static_assert(( std::__is_cpp17_contiguous_iterator<std::span<      int>::iterator>        ::value), "");
+    static_assert((!std::__is_cpp17_contiguous_iterator<std::span<      int>::reverse_iterator>::value), "");
+    static_assert(( std::__is_cpp17_contiguous_iterator<std::span<const int>::iterator>        ::value), "");
+    static_assert((!std::__is_cpp17_contiguous_iterator<std::span<const int>::reverse_iterator>::value), "");
+#endif
+
+    return 0;
+}

libcxx/test/libcxx/iterators/trivial_iterators.pass.cpp

//  iterators in the libc++ test suite
     static_assert((!std::__libcpp_is_trivial_iterator<NonThrowingIterator   <char *> >::value), "");
 
 
 //  Iterator classification
     static_assert(( std::__is_cpp17_input_iterator        <char *>::value), "" );
     static_assert(( std::__is_cpp17_forward_iterator      <char *>::value), "" );
     static_assert(( std::__is_cpp17_bidirectional_iterator<char *>::value), "" );
     static_assert(( std::__is_cpp17_random_access_iterator<char *>::value), "" );
+    static_assert(( std::__is_cpp17_contiguous_iterator   <char *>::value), "" );
     static_assert((!std::__is_exactly_cpp17_input_iterator<char *>::value), "" );
 
     static_assert(( std::__is_cpp17_input_iterator        <input_iterator<char *> >::value), "" );
     static_assert((!std::__is_cpp17_forward_iterator      <input_iterator<char *> >::value), "" );
     static_assert((!std::__is_cpp17_bidirectional_iterator<input_iterator<char *> >::value), "" );
     static_assert((!std::__is_cpp17_random_access_iterator<input_iterator<char *> >::value), "" );
+    static_assert((!std::__is_cpp17_contiguous_iterator   <input_iterator<char *> >::value), "" );
     static_assert(( std::__is_exactly_cpp17_input_iterator<input_iterator<char *> >::value), "" );
 
     static_assert(( std::__is_cpp17_input_iterator        <forward_iterator<char *> >::value), "" );
     static_assert(( std::__is_cpp17_forward_iterator      <forward_iterator<char *> >::value), "" );
     static_assert((!std::__is_cpp17_bidirectional_iterator<forward_iterator<char *> >::value), "" );
     static_assert((!std::__is_cpp17_random_access_iterator<forward_iterator<char *> >::value), "" );
+    static_assert((!std::__is_cpp17_contiguous_iterator   <forward_iterator<char *> >::value), "" );
     static_assert((!std::__is_exactly_cpp17_input_iterator<forward_iterator<char *> >::value), "" );
 
     static_assert(( std::__is_cpp17_input_iterator        <bidirectional_iterator<char *> >::value), "" );
     static_assert(( std::__is_cpp17_forward_iterator      <bidirectional_iterator<char *> >::value), "" );
     static_assert(( std::__is_cpp17_bidirectional_iterator<bidirectional_iterator<char *> >::value), "" );
     static_assert((!std::__is_cpp17_random_access_iterator<bidirectional_iterator<char *> >::value), "" );
+    static_assert((!std::__is_cpp17_contiguous_iterator   <bidirectional_iterator<char *> >::value), "" );
     static_assert((!std::__is_exactly_cpp17_input_iterator<bidirectional_iterator<char *> >::value), "" );
 
     static_assert(( std::__is_cpp17_input_iterator        <random_access_iterator<char *> >::value), "" );
     static_assert(( std::__is_cpp17_forward_iterator      <random_access_iterator<char *> >::value), "" );
     static_assert(( std::__is_cpp17_bidirectional_iterator<random_access_iterator<char *> >::value), "" );
     static_assert(( std::__is_cpp17_random_access_iterator<random_access_iterator<char *> >::value), "" );
+    static_assert((!std::__is_cpp17_contiguous_iterator   <random_access_iterator<char *> >::value), "" );
     static_assert((!std::__is_exactly_cpp17_input_iterator<random_access_iterator<char *> >::value), "" );
 
     static_assert(( std::__is_cpp17_input_iterator        <my_input_iterator<char *> >::value), "" );
     static_assert((!std::__is_cpp17_forward_iterator      <my_input_iterator<char *> >::value), "" );
     static_assert((!std::__is_cpp17_bidirectional_iterator<my_input_iterator<char *> >::value), "" );
     static_assert((!std::__is_cpp17_random_access_iterator<my_input_iterator<char *> >::value), "" );
+    static_assert((!std::__is_cpp17_contiguous_iterator   <my_input_iterator<char *> >::value), "" );
     static_assert(( std::__is_exactly_cpp17_input_iterator<my_input_iterator<char *> >::value), "" );
 
 //
 //  iterators from libc++'s containers
 //
 
 //  vector
     static_assert(( std::__libcpp_is_trivial_iterator<std::vector<char>::iterator>              ::value), "");

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

for (unsigned i = 0; i < N; ++i)
         ia[i].reset(new int(i));
     std::unique_ptr<int> ib[N];
 
     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(*ib[i] == static_cast<int>(i));
 }
+
+struct TMBNTC {
+    int *p;
+    constexpr TMBNTC(int& copies) : p(&copies) {}
+    constexpr TMBNTC(const TMBNTC&) = default;
+    TEST_CONSTEXPR_CXX14 TMBNTC& operator=(TMBNTC&&) = default;
+    TEST_CONSTEXPR_CXX14 TMBNTC& operator=(const TMBNTC&) { ++*p; return *this; }
+};
+
+TEST_CONSTEXPR_CXX20 bool
+test_trivial_moveassign_but_no_trivial_copyassign()
+{
+    int copies = 0;
+    TMBNTC ia[] = { copies, copies, copies, copies };
+    TMBNTC ib[] = { copies, copies, copies, copies };
+    std::copy(ia, ia+4, ib);
+    assert(copies == 4);
+    copies = 0;
+    std::copy_backward(ia, ia+4, ib+4);
+    assert(copies == 4);
+
+    copies = 0;
+    std::move(ia, ia+4, ib);
+    assert(copies == 0);
+    std::move_backward(ia, ia+4, ib+4);
+    assert(copies == 0);
+
+    return true;
+}
+
+struct TCBNTM {
+    int *p;
+    constexpr TCBNTM(int& moves) : p(&moves) {}
+    constexpr TCBNTM(const TCBNTM&) = default;
+    TEST_CONSTEXPR_CXX14 TCBNTM& operator=(TCBNTM&&) { ++*p; return *this; }
+    TEST_CONSTEXPR_CXX14 TCBNTM& operator=(const TCBNTM&) = default;
+};
+
+TEST_CONSTEXPR_CXX20 bool
+test_trivial_copyassign_but_no_trivial_moveassign()
+{
+    int moves = 0;
+    TCBNTM ia[] = { moves, moves, moves, moves };
+    TCBNTM ib[] = { moves, moves, moves, moves };
+    std::move(ia, ia+4, ib);
+    assert(moves == 4);
+    moves = 0;
+    std::move_backward(ia, ia+4, ib+4);
+    assert(moves == 4);
+
+    moves = 0;
+    std::copy(ia, ia+4, ib);
+    assert(moves == 0);
+    std::copy_backward(ia, ia+4, ib+4);
+    assert(moves == 0);
+
+    return true;
+}
+
 #endif
 
 int main(int, char**)
 {
     test<bidirectional_iterator<const int*>, bidirectional_iterator<int*> >();
     test<bidirectional_iterator<const int*>, random_access_iterator<int*> >();
     test<bidirectional_iterator<const int*>, int*>();
 
#if TEST_STD_VER >= 11
 
     test1<random_access_iterator<std::unique_ptr<int>*>, bidirectional_iterator<std::unique_ptr<int>*> >();
     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>*>();
+
+    test_trivial_moveassign_but_no_trivial_copyassign();
+    test_trivial_copyassign_but_no_trivial_moveassign();
 #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*>());
+
+    static_assert(test_trivial_moveassign_but_no_trivial_copyassign());
+    static_assert(test_trivial_copyassign_but_no_trivial_moveassign());
 #endif  // TEST_STD_VER > 17
 
   return 0;
 }

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;
+}

libcxx/test/std/iterators/predef.iterators/move.iterators/move.iterator/types.pass.cpp

test()
     static_assert((std::is_same<typename R::difference_type, typename T::difference_type>::value), "");
     static_assert((std::is_same<typename R::pointer, It>::value), "");
     static_assert((std::is_same<typename R::value_type, typename T::value_type>::value), "");
 #if TEST_STD_VER >= 11
     static_assert((std::is_same<typename R::reference, typename R::value_type&&>::value), "");
 #else
     static_assert((std::is_same<typename R::reference, typename T::reference>::value), "");
 #endif
+#if TEST_STD_VER > 17
+    if constexpr (std::is_same_v<typename T::iterator_category, std::contiguous_iterator_tag>) {
+        static_assert((std::is_same<typename R::iterator_category, std::random_access_iterator_tag>::value), "");
+    } else {
         static_assert((std::is_same<typename R::iterator_category, typename T::iterator_category>::value), "");
     }
+#else
+    static_assert((std::is_same<typename R::iterator_category, typename T::iterator_category>::value), "");
+#endif
+}
 
 int main(int, char**)
 {
     test<input_iterator<char*> >();
     test<forward_iterator<char*> >();
     test<bidirectional_iterator<char*> >();
     test<random_access_iterator<char*> >();
     test<char*>();
#if TEST_STD_VER >= 11
     }
     {
         typedef DummyIt<int, int&&> T;
         typedef std::move_iterator<T> It;
         static_assert(std::is_same<It::reference, int&&>::value, "");
     }
 #endif
 
+#if TEST_STD_VER > 17
+    test<contiguous_iterator<char*>>();
+    static_assert(std::is_same_v<typename std::move_iterator<forward_iterator<char*>>::iterator_concept, std::input_iterator_tag>);
+    static_assert(std::is_same_v<typename std::move_iterator<bidirectional_iterator<char*>>::iterator_concept, std::input_iterator_tag>);
+    static_assert(std::is_same_v<typename std::move_iterator<random_access_iterator<char*>>::iterator_concept, std::input_iterator_tag>);
+    static_assert(std::is_same_v<typename std::move_iterator<contiguous_iterator<char*>>::iterator_concept, std::input_iterator_tag>);
+    static_assert(std::is_same_v<typename std::move_iterator<char*>::iterator_concept, std::input_iterator_tag>);
+#endif
+
   return 0;
 }

libcxx/test/std/iterators/predef.iterators/reverse.iterators/reverse.iterator/types.pass.cpp

test()
     typedef std::reverse_iterator<It> R;
     typedef std::iterator_traits<It> T;
     find_current<It> q; q.test(); // Just test that we can access `.current` from derived classes
     static_assert((std::is_same<typename R::iterator_type, It>::value), "");
     static_assert((std::is_same<typename R::value_type, typename T::value_type>::value), "");
     static_assert((std::is_same<typename R::difference_type, typename T::difference_type>::value), "");
     static_assert((std::is_same<typename R::reference, typename T::reference>::value), "");
     static_assert((std::is_same<typename R::pointer, typename std::iterator_traits<It>::pointer>::value), "");
+#if TEST_STD_VER > 17
+    if constexpr (std::is_same_v<typename T::iterator_category, std::contiguous_iterator_tag>) {
+        static_assert((std::is_same<typename R::iterator_category, std::random_access_iterator_tag>::value), "");
+    } else {
         static_assert((std::is_same<typename R::iterator_category, typename T::iterator_category>::value), "");
     }
+#else
+    static_assert((std::is_same<typename R::iterator_category, typename T::iterator_category>::value), "");
+#endif
+}
 
 int main(int, char**)
 {
     test<bidirectional_iterator<char*> >();
     test<random_access_iterator<char*> >();
     test<char*>();
 
+#if TEST_STD_VER > 17
+    test<contiguous_iterator<char*>>();
+    static_assert(std::is_same_v<typename std::reverse_iterator<bidirectional_iterator<char*>>::iterator_concept, std::bidirectional_iterator_tag>);
+    static_assert(std::is_same_v<typename std::reverse_iterator<random_access_iterator<char*>>::iterator_concept, std::random_access_iterator_tag>);
+    static_assert(std::is_same_v<typename std::reverse_iterator<contiguous_iterator<char*>>::iterator_concept, std::random_access_iterator_tag>);
+    static_assert(std::is_same_v<typename std::reverse_iterator<char*>::iterator_concept, std::random_access_iterator_tag>);
+#endif
+
     return 0;
 }

libcxx/test/std/language.support/support.limits/support.limits.general/algorithm.version.pass.cpp

 
 # ifndef __cpp_lib_clamp
 #   error "__cpp_lib_clamp should be defined in c++20"
 # endif
 # if __cpp_lib_clamp != 201603L
 #   error "__cpp_lib_clamp should have the value 201603L in c++20"
 # endif
 
-# if !defined(_LIBCPP_VERSION)
-#   ifndef __cpp_lib_constexpr_algorithms
-#     error "__cpp_lib_constexpr_algorithms should be defined in c++20"
-#   endif
-#   if __cpp_lib_constexpr_algorithms != 201806L
-#     error "__cpp_lib_constexpr_algorithms should have the value 201806L in c++20"
-#   endif
-# else // _LIBCPP_VERSION
-#   ifdef __cpp_lib_constexpr_algorithms
-#     error "__cpp_lib_constexpr_algorithms should not be defined because it is unimplemented in libc++!"
-#   endif
-# endif
+# ifndef __cpp_lib_constexpr_algorithms
+#   error "__cpp_lib_constexpr_algorithms should be defined in c++20"
+# endif
+# if __cpp_lib_constexpr_algorithms != 201806L
+#   error "__cpp_lib_constexpr_algorithms should have the value 201806L in c++20"
+# endif
 
 # if !defined(_LIBCPP_VERSION)
 #   ifndef __cpp_lib_parallel_algorithm
 #     error "__cpp_lib_parallel_algorithm should be defined in c++20"
 #   endif
 #   if __cpp_lib_parallel_algorithm != 201603L
 #     error "__cpp_lib_parallel_algorithm should have the value 201603L in c++20"
 #   endif

 
 # ifndef __cpp_lib_clamp
 #   error "__cpp_lib_clamp should be defined in c++2b"
 # endif
 # if __cpp_lib_clamp != 201603L
 #   error "__cpp_lib_clamp should have the value 201603L in c++2b"
 # endif
 
-# if !defined(_LIBCPP_VERSION)
-#   ifndef __cpp_lib_constexpr_algorithms
-#     error "__cpp_lib_constexpr_algorithms should be defined in c++2b"
-#   endif
-#   if __cpp_lib_constexpr_algorithms != 201806L
-#     error "__cpp_lib_constexpr_algorithms should have the value 201806L in c++2b"
-#   endif
-# else // _LIBCPP_VERSION
-#   ifdef __cpp_lib_constexpr_algorithms
-#     error "__cpp_lib_constexpr_algorithms should not be defined because it is unimplemented in libc++!"
-#   endif
-# endif
+# ifndef __cpp_lib_constexpr_algorithms
+#   error "__cpp_lib_constexpr_algorithms should be defined in c++2b"
+# endif
+# if __cpp_lib_constexpr_algorithms != 201806L
+#   error "__cpp_lib_constexpr_algorithms should have the value 201806L in c++2b"
+# endif
 
 # if !defined(_LIBCPP_VERSION)
 #   ifndef __cpp_lib_parallel_algorithm
 #     error "__cpp_lib_parallel_algorithm should be defined in c++2b"
 #   endif
 #   if __cpp_lib_parallel_algorithm != 201603L
 #     error "__cpp_lib_parallel_algorithm should have the value 201603L in c++2b"
 #   endif

libcxx/test/std/language.support/support.limits/support.limits.general/version.version.pass.cpp

 #     error "__cpp_lib_concepts should have the value 202002L in c++20"
 #   endif
 # else // _LIBCPP_VERSION
 #   ifdef __cpp_lib_concepts
 #     error "__cpp_lib_concepts should not be defined because it is unimplemented in libc++!"
 #   endif
 # endif
 
-# if !defined(_LIBCPP_VERSION)
-#   ifndef __cpp_lib_constexpr_algorithms
-#     error "__cpp_lib_constexpr_algorithms should be defined in c++20"
-#   endif
-#   if __cpp_lib_constexpr_algorithms != 201806L
-#     error "__cpp_lib_constexpr_algorithms should have the value 201806L in c++20"
-#   endif
-# else // _LIBCPP_VERSION
-#   ifdef __cpp_lib_constexpr_algorithms
-#     error "__cpp_lib_constexpr_algorithms should not be defined because it is unimplemented in libc++!"
-#   endif
+# ifndef __cpp_lib_constexpr_algorithms
+#   error "__cpp_lib_constexpr_algorithms should be defined in c++20"
+# endif
+# if __cpp_lib_constexpr_algorithms != 201806L
+#   error "__cpp_lib_constexpr_algorithms should have the value 201806L in c++20"
 # endif
 
 # if !defined(_LIBCPP_VERSION)
 #   ifndef __cpp_lib_constexpr_complex
 #     error "__cpp_lib_constexpr_complex should be defined in c++20"
 #   endif
 #   if __cpp_lib_constexpr_complex != 201711L
 #     error "__cpp_lib_constexpr_complex should have the value 201711L in c++20"

 #     error "__cpp_lib_concepts should have the value 202002L in c++2b"
 #   endif
 # else // _LIBCPP_VERSION
 #   ifdef __cpp_lib_concepts
 #     error "__cpp_lib_concepts should not be defined because it is unimplemented in libc++!"
 #   endif
 # endif
 
-# if !defined(_LIBCPP_VERSION)
-#   ifndef __cpp_lib_constexpr_algorithms
-#     error "__cpp_lib_constexpr_algorithms should be defined in c++2b"
-#   endif
-#   if __cpp_lib_constexpr_algorithms != 201806L
-#     error "__cpp_lib_constexpr_algorithms should have the value 201806L in c++2b"
-#   endif
-# else // _LIBCPP_VERSION
-#   ifdef __cpp_lib_constexpr_algorithms
-#     error "__cpp_lib_constexpr_algorithms should not be defined because it is unimplemented in libc++!"
-#   endif
+# ifndef __cpp_lib_constexpr_algorithms
+#   error "__cpp_lib_constexpr_algorithms should be defined in c++2b"
+# endif
+# if __cpp_lib_constexpr_algorithms != 201806L
+#   error "__cpp_lib_constexpr_algorithms should have the value 201806L in c++2b"
 # endif
 
 # if !defined(_LIBCPP_VERSION)
 #   ifndef __cpp_lib_constexpr_complex
 #     error "__cpp_lib_constexpr_complex should be defined in c++2b"
 #   endif
 #   if __cpp_lib_constexpr_complex != 201711L
 #     error "__cpp_lib_constexpr_complex should have the value 201711L in c++2b"

libcxx/test/support/test_iterators.h

 template <class T, class U>
 inline TEST_CONSTEXPR_CXX14
 typename std::iterator_traits<T>::difference_type
 operator-(const random_access_iterator<T>& x, const random_access_iterator<U>& y)
 {
     return x.base() - y.base();
 }
 
+#if TEST_STD_VER >= 20
+template <class It>
+class contiguous_iterator
+{
+    It it_;
+
+    template <class U> friend class contiguous_iterator;
+public:
+    typedef          std::contiguous_iterator_tag              iterator_category;
+    typedef typename std::iterator_traits<It>::value_type      value_type;
+    typedef typename std::iterator_traits<It>::difference_type difference_type;
+    typedef It                                                 pointer;
+    typedef typename std::iterator_traits<It>::reference       reference;
+    typedef typename std::iterator_traits<It>::value_type      element_type;
+
+    TEST_CONSTEXPR_CXX14 It base() const {return it_;}
+
+    TEST_CONSTEXPR_CXX14 contiguous_iterator() : it_() {}
+    explicit TEST_CONSTEXPR_CXX14 contiguous_iterator(It it) : it_(it) {}
+    template <class U>
+        TEST_CONSTEXPR_CXX14 contiguous_iterator(const contiguous_iterator<U>& u) :it_(u.it_) {}
+
+    TEST_CONSTEXPR_CXX14 reference operator*() const {return *it_;}
+    TEST_CONSTEXPR_CXX14 pointer operator->() const {return it_;}
+
+    TEST_CONSTEXPR_CXX14 contiguous_iterator& operator++() {++it_; return *this;}
+    TEST_CONSTEXPR_CXX14 contiguous_iterator operator++(int)
+        {contiguous_iterator tmp(*this); ++(*this); return tmp;}
+
+    TEST_CONSTEXPR_CXX14 contiguous_iterator& operator--() {--it_; return *this;}
+    TEST_CONSTEXPR_CXX14 contiguous_iterator operator--(int)
+        {contiguous_iterator tmp(*this); --(*this); return tmp;}
+
+    TEST_CONSTEXPR_CXX14 contiguous_iterator& operator+=(difference_type n) {it_ += n; return *this;}
+    TEST_CONSTEXPR_CXX14 contiguous_iterator operator+(difference_type n) const
+        {contiguous_iterator tmp(*this); tmp += n; return tmp;}
+    friend TEST_CONSTEXPR_CXX14 contiguous_iterator operator+(difference_type n, contiguous_iterator x)
+        {x += n; return x;}
+    TEST_CONSTEXPR_CXX14 contiguous_iterator& operator-=(difference_type n) {return *this += -n;}
+    TEST_CONSTEXPR_CXX14 contiguous_iterator operator-(difference_type n) const
+        {contiguous_iterator tmp(*this); tmp -= n; return tmp;}
+
+    TEST_CONSTEXPR_CXX14 reference operator[](difference_type n) const {return it_[n];}
+
+    template <class T>
+    void operator,(T const &) DELETE_FUNCTION;
+
+    friend TEST_CONSTEXPR_CXX14
+    difference_type operator-(const contiguous_iterator& x, const contiguous_iterator& y) {
+        return x.base() - y.base();
+    }
+
+    friend TEST_CONSTEXPR_CXX14
+    difference_type operator<(const contiguous_iterator& x, const contiguous_iterator& y) {
+        return x.base() < y.base();
+    }
+    friend TEST_CONSTEXPR_CXX14
+    difference_type operator>(const contiguous_iterator& x, const contiguous_iterator& y) {
+        return x.base() > y.base();
+    }
+    friend TEST_CONSTEXPR_CXX14
+    difference_type operator<=(const contiguous_iterator& x, const contiguous_iterator& y) {
+        return x.base() <= y.base();
+    }
+    friend TEST_CONSTEXPR_CXX14
+    difference_type operator>=(const contiguous_iterator& x, const contiguous_iterator& y) {
+        return x.base() >= y.base();
+    }
+    friend TEST_CONSTEXPR_CXX14
+    difference_type operator==(const contiguous_iterator& x, const contiguous_iterator& y) {
+        return x.base() == y.base();
+    }
+    friend TEST_CONSTEXPR_CXX14
+    difference_type operator!=(const contiguous_iterator& x, const contiguous_iterator& y) {
+        return x.base() != y.base();
+    }
+};
+#endif
+
 template <class Iter>
 inline TEST_CONSTEXPR_CXX14 Iter base(output_iterator<Iter> i) { return i.base(); }
 
 template <class Iter>
 inline TEST_CONSTEXPR_CXX14 Iter base(input_iterator<Iter> i) { return i.base(); }
 
 template <class Iter>
 inline TEST_CONSTEXPR_CXX14 Iter base(forward_iterator<Iter> i) { return i.base(); }
 
 template <class Iter>
 inline TEST_CONSTEXPR_CXX14 Iter base(bidirectional_iterator<Iter> i) { return i.base(); }
 
 template <class Iter>
 inline TEST_CONSTEXPR_CXX14 Iter base(random_access_iterator<Iter> i) { return i.base(); }
 
+#if TEST_STD_VER >= 20
+template <class Iter>
+inline TEST_CONSTEXPR_CXX14 Iter base(contiguous_iterator<Iter> i) { return i.base(); }
+#endif
+
 template <class Iter>    // everything else
 inline TEST_CONSTEXPR_CXX14 Iter base(Iter i) { return i; }
 
 template <typename T>
 struct ThrowingIterator {
     typedef std::bidirectional_iterator_tag iterator_category;
     typedef ptrdiff_t                       difference_type;
     typedef const T                         value_type;

libcxx/utils/generate_feature_test_macro_components.py

feature_test_macros = [ add_version_header(x) for x in [
     "name": "__cpp_lib_concepts",
     "values": { "c++20": 202002 },
     "headers": ["concepts"],
     "unimplemented": True,
   }, {
     "name": "__cpp_lib_constexpr_algorithms",
     "values": { "c++20": 201806 },
     "headers": ["algorithm"],
-    "unimplemented": True,
   }, {
     "name": "__cpp_lib_constexpr_complex",
     "values": { "c++20": 201711 },
     "headers": ["complex"],
     "unimplemented": True,
   }, {
     "name": "__cpp_lib_constexpr_dynamic_alloc",
     "values": { "c++20": 201907 },