[libc++] Rationalize our treatment of contiguous iterators and __unwrap_iter().

[• Quuxplusone]

Summary

• Continue exposing contiguous_iterator_tag only in C++20.
• Implement C++20's changes to reverse_iterator, so that it won't be accidentally counted as a contiguous iterator (and test this).
• Implement C++20's changes to move_iterator as well (and test them).
• move_iterator should not be contiguous. This fixes a bug where we optimized std::copy-of-move-iterators in an observable way. Add a regression test for that bugfix.
• Add libcxx tests for __is_cpp17_contiguous_iterator of all relevant standard iterator types (in all modes).
• Expose {reverse,move}_iterator::iterator_concept only in C++20 mode. I initially exposed it in all modes, but now that contiguous_iterator_tag is C++20-only, I think this makes more sense.

I expect this to solve the issue reported by @rnk in D92776. They should just be able to write a conforming contiguous iterator according to https://stackoverflow.com/questions/65712091/in-c20-how-do-i-write-a-contiguous-iterator
libc++ will guarantee that it works (i.e. is optimized in std::copy) in C++20 mode, but will continue not to support user-defined contiguous iterators in C++17.

I would perhaps like to rename __unwrap_iter(x) to something like __unwrap_contiguous_iter(x) or __lower_contiguous_iter(x), to better reflect its purpose; but I didn't want to do that in this patch because it would just add icky diffs at all the call-sites.

[• Quuxplusone]

Improve the contiguous_iterators.pass.cpp test, including a test case for exactly what I'd expect Chromium to write in their code to enable contiguous-iterator-ness.

[• Quuxplusone]

Tests failed. Let's try this again.

[• Quuxplusone]

In the new test, make TCBNTM and TMBNTC copy-constructible, because if they're not, then you can't make an array of them pre-C++17. ("error: copying array element of type 'TMBNTC'...")

[• Quuxplusone]

Rebase, and fix my new test's constexprness in C++11 mode.

[ldionne]

I like this - I find it cleaner than a "private contract" with some specific users that they are allowed to overload __unwrap_iter. But I'd like to know why can't we leave that only enabled in C++20 mode. @rnk Would it be acceptable for Chrome to compile with C++20? It seems like an optimization that would justify the work to upgrade?

As a matter of policy, I'm a bit reluctant to say "let's add this as an extension because our very important client Chrome is using it". I don't think it's a great way to make decisions. The only reason why I could see us doing it here is because Chrome previously had a free-pass with __unwrap_iter and we broke them. But my preference would be to avoid adding those extensions pre-C++20. @rnk can you comment?

libcxx/include/algorithm

1642

Can you name this __apply? Or we could use operator(). Either seems closer to conventions than __f.

libcxx/include/iterator

609

Isn't this check made redundant by the following check for __has_iterator_category_convertible_to<_Tp, contiguous_iterator_tag>?

618

I take it that you're not using just true_type here in case someone specializes iterator_traits<MyFoo*> to have a non random-access iterator_category?

789–790

A test should be added for that.

1241–1244

A test should be added for that.

[rnk]

In D94807#2520226, @ldionne wrote:

I like this - I find it cleaner than a "private contract" with some specific users that they are allowed to overload __unwrap_iter. But I'd like to know why can't we leave that only enabled in C++20 mode. @rnk Would it be acceptable for Chrome to compile with C++20? It seems like an optimization that would justify the work to upgrade?

As a matter of policy, I'm a bit reluctant to say "let's add this as an extension because our very important client Chrome is using it". I don't think it's a great way to make decisions. The only reason why I could see us doing it here is because Chrome previously had a free-pass with __unwrap_iter and we broke them. But my preference would be to avoid adding those extensions pre-C++20. @rnk can you comment?

Chrome hasn't yet migrated to C++17 yet: https://crbug.com/752720 The major blocker is that nacl compilers are still used somewhere, so I'm pretty sure we are not ready to enable C++20.

In the discussion on the bug with the author of these checked iterators, they seemed OK with relying on implementation details, including re-opening the std::__1 namespaces with the necessary macros to make the __unwrap_iter overload work. I think the optimization only has to work with bundled libc++ version. If that is not in use, the optimization is disabled. I think we might be OK without a properly supported way to do this until we make it to C++20. NaCl is supposed to go away in 2021, so at that point we could probably spring forward and use the officially supported mechanism.

[ldionne]

In D94807#2520593, @rnk wrote:

In the discussion on the bug with the author of these checked iterators, they seemed OK with relying on implementation details, including re-opening the std::__1 namespaces with the necessary macros to make the __unwrap_iter overload work. I think the optimization only has to work with bundled libc++ version. If that is not in use, the optimization is disabled. I think we might be OK without a properly supported way to do this until we make it to C++20. NaCl is supposed to go away in 2021, so at that point we could probably spring forward and use the officially supported mechanism.

Okay, so if I'm reading this correctly, we basically don't have anything to do as requested on D92776.

Arthur, some of this stuff landed in C++20, so we can still do it, but in C++20 only. Are you OK with that?

[• Quuxplusone]

libcxx/include/algorithm

1642

I definitely object to operator(); I prefer named functions whenever possible. I don't object to __apply; I just picked __f because it was short. (We don't seem to have any instances of either __f or __apply with this connotation in the codebase. We do have quite a few __test, but that name seems inappropriate here because this is a transformation, not a SFINAE test.)

libcxx/include/iterator

444

@ldionne wrote:

Arthur, some of this stuff landed in C++20, so we can still do it, but in C++20 only. Are you OK with that?

Yes, I believe so, unless I run into a problem with that.
The important subtlety here remains, even if we ignore Chromium. The way I've got the code structured now, in both C++03 and C++20,

• The std::copy-to-memmove optimization happens only for iterators where __unwrap_iter(it) returns a native pointer T*.
• __unwrap_iter(it) returns native pointers only for contiguous iterators, i.e., __is_cpp17_contiguous_iterator<It>::value is true and _VSTD::__to_address(it) exists.
• We want the std::copy-to-memmove optimization to happen for vector<int>::iterator i.e. __wrap_iter<int*>.

So even in C++03 mode, where std::contiguous_iterator_tag does not exist, we must ensure that __is_cpp17_contiguous_iterator<int*>::value && __is_cpp17_contiguous_iterator<__wrap_iter<int*>>::value.

I think that's a good state of affairs, and I think I can physically make it happen. But if I come back and say "oops, actually that's physically impossible because...," then I'll ask to revisit this.

609

It's not completely redundant — it rejects user-defined iterator types with iterator_category=input_iterator_tag and iterator_concept=contiguous_iterator_tag. However, I can't point to any such types in the wild, and I didn't write any unit tests for such types, so I agree — I'll remove the redundancy. Let someone put it back if they run into such a case in the wild.

618

As the comment indicated, my intent had been to make sure this specialization didn't accidentally accept types like int(*)(), void*,... which are syntactically _Up* but not actually iterators.
However, writing tests for this revealed that if you try to ask __is_cpp17_contiguous_iterator<void*> it just blows up anyway, because instantiating iterator_traits<void*> is ill-formed.
So as above, I agree — I'll just do true_type here and let someone "fix" the corner case for real, if they ever run into it.

I hadn't realized that __has_iterator_category_convertible_to wasn't SFINAE-friendly. (It barfs on most non-iterator types.)

[ldionne]

libcxx/include/iterator

609

That would be a weird and misleading iterator, wouldn't it?

618

I hadn't realized that __has_iterator_category_convertible_to wasn't SFINAE-friendly. (It barfs on most non-iterator types.)

This is surprising to me. Perhaps we should fix it.

[• Quuxplusone]

libcxx/include/iterator

444

@ldionne: It would be almost trivial, if there were a way to expose contiguous_iterator_tag only to the implementation, e.g.

struct __libcpp_contiguous_iterator_tag : random_access_iterator_tag {};
#if _LIBCPP_STD_VER > 17
using contiguous_iterator_tag = __libcpp_contiguous_iterator_tag;
#endif

Is that snippet acceptable? and/or have you got another acceptable idea?
If not, then it's still possible to achieve our goal, but with an increased number of codepaths that differ when #if _LIBCPP_STD_VER > 17.

[• Quuxplusone]

Update with the same patch that I rolled into D93661 last week. Still waiting for buildkite to unbork itself and finish a build.

[ldionne]

libcxx/include/iterator

444

Yes, it's acceptable IMO.

[ldionne]

Except for the comment nitpick, this LGTM. Please update and submit. Thanks a lot!

libcxx/include/iterator

606–607

I think the comment at the top of libcxx/test/libcxx/iterators/contiguous_iterators.pass.cpp should come here instead, it helps understanding what's going on.

[• Quuxplusone]

Split out the regression test into its own test file.
Hide move_iterator::iterator_concept in C++17-and-earlier. (I had done this for __wrap_iter::iterator_concept and iterator_traits::iterator_concept, but forgotten to do it for move_iterator and reverse_iterator).
Poke buildkite one last time before (I hope) finally landing this patch.

[• Quuxplusone]

libcxx/include/iterator

618

Agreed, but not fixed in this patch.

libcxx/include/CMakeLists.txt

 set(files
   __availability
   __bit_reference
   __bsd_locale_defaults.h
   __bsd_locale_fallbacks.h
   __debug
   __errc
   __functional_03
   __functional_base
   __functional_base_03
   __hash_table
   __libcpp_version
   __locale
   __memory/allocator_traits.h
   __memory/base.h
-  __memory/pointer_traits.h
   __memory/utilities.h
   __mutex_base
   __node_handle
   __nullptr
   __split_buffer
   __sso_allocator
   __std_stream
   __string

libcxx/include/__memory/allocator_traits.h

 // -*- C++ -*-
 //===----------------------------------------------------------------------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef _LIBCPP___MEMORY_ALLOCATOR_TRAITS_H
 #define _LIBCPP___MEMORY_ALLOCATOR_TRAITS_H
 
 #include <__config>
 #include <__memory/base.h>
-#include <__memory/pointer_traits.h>
 #include <type_traits>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
 _LIBCPP_PUSH_MACROS
 #include <__undef_macros>

libcxx/include/__memory/base.h

 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 void destroy_at(_Tp* __loc) {
     _LIBCPP_ASSERT(__loc, "null pointer given to destroy_at");
     __loc->~_Tp();
 }
 
 #endif
 
+// pointer_traits
+
+template <class _Tp, class = void>
+struct __has_element_type : false_type {};
+
+template <class _Tp>
+struct __has_element_type<_Tp,
+              typename __void_t<typename _Tp::element_type>::type> : true_type {};
+
+template <class _Ptr, bool = __has_element_type<_Ptr>::value>
+struct __pointer_traits_element_type;
+
+template <class _Ptr>
+struct __pointer_traits_element_type<_Ptr, true>
+{
+    typedef _LIBCPP_NODEBUG_TYPE typename _Ptr::element_type type;
+};
+
+template <template <class, class...> class _Sp, class _Tp, class ..._Args>
+struct __pointer_traits_element_type<_Sp<_Tp, _Args...>, true>
+{
+    typedef _LIBCPP_NODEBUG_TYPE typename _Sp<_Tp, _Args...>::element_type type;
+};
+
+template <template <class, class...> class _Sp, class _Tp, class ..._Args>
+struct __pointer_traits_element_type<_Sp<_Tp, _Args...>, false>
+{
+    typedef _LIBCPP_NODEBUG_TYPE _Tp type;
+};
+
+template <class _Tp, class = void>
+struct __has_difference_type : false_type {};
+
+template <class _Tp>
+struct __has_difference_type<_Tp,
+            typename __void_t<typename _Tp::difference_type>::type> : true_type {};
+
+template <class _Ptr, bool = __has_difference_type<_Ptr>::value>
+struct __pointer_traits_difference_type
+{
+    typedef _LIBCPP_NODEBUG_TYPE ptrdiff_t type;
+};
+
+template <class _Ptr>
+struct __pointer_traits_difference_type<_Ptr, true>
+{
+    typedef _LIBCPP_NODEBUG_TYPE typename _Ptr::difference_type type;
+};
+
+template <class _Tp, class _Up>
+struct __has_rebind
+{
+private:
+    struct __two {char __lx; char __lxx;};
+    template <class _Xp> static __two __test(...);
+    _LIBCPP_SUPPRESS_DEPRECATED_PUSH
+    template <class _Xp> static char __test(typename _Xp::template rebind<_Up>* = 0);
+    _LIBCPP_SUPPRESS_DEPRECATED_POP
+public:
+    static const bool value = sizeof(__test<_Tp>(0)) == 1;
+};
+
+template <class _Tp, class _Up, bool = __has_rebind<_Tp, _Up>::value>
+struct __pointer_traits_rebind
+{
+#ifndef _LIBCPP_CXX03_LANG
+    typedef _LIBCPP_NODEBUG_TYPE typename _Tp::template rebind<_Up> type;
+#else
+    typedef _LIBCPP_NODEBUG_TYPE typename _Tp::template rebind<_Up>::other type;
+#endif
+};
+
+template <template <class, class...> class _Sp, class _Tp, class ..._Args, class _Up>
+struct __pointer_traits_rebind<_Sp<_Tp, _Args...>, _Up, true>
+{
+#ifndef _LIBCPP_CXX03_LANG
+    typedef _LIBCPP_NODEBUG_TYPE typename _Sp<_Tp, _Args...>::template rebind<_Up> type;
+#else
+    typedef _LIBCPP_NODEBUG_TYPE typename _Sp<_Tp, _Args...>::template rebind<_Up>::other type;
+#endif
+};
+
+template <template <class, class...> class _Sp, class _Tp, class ..._Args, class _Up>
+struct __pointer_traits_rebind<_Sp<_Tp, _Args...>, _Up, false>
+{
+    typedef _Sp<_Up, _Args...> type;
+};
+
+template <class _Ptr>
+struct _LIBCPP_TEMPLATE_VIS pointer_traits
+{
+    typedef _Ptr                                                     pointer;
+    typedef typename __pointer_traits_element_type<pointer>::type    element_type;
+    typedef typename __pointer_traits_difference_type<pointer>::type difference_type;
+
+#ifndef _LIBCPP_CXX03_LANG
+    template <class _Up> using rebind = typename __pointer_traits_rebind<pointer, _Up>::type;
+#else
+    template <class _Up> struct rebind
+        {typedef typename __pointer_traits_rebind<pointer, _Up>::type other;};
+#endif  // _LIBCPP_CXX03_LANG
+
+private:
+    struct __nat {};
+public:
+    _LIBCPP_INLINE_VISIBILITY
+    static pointer pointer_to(typename conditional<is_void<element_type>::value,
+                                           __nat, element_type>::type& __r)
+        {return pointer::pointer_to(__r);}
+};
+
+template <class _Tp>
+struct _LIBCPP_TEMPLATE_VIS pointer_traits<_Tp*>
+{
+    typedef _Tp*      pointer;
+    typedef _Tp       element_type;
+    typedef ptrdiff_t difference_type;
+
+#ifndef _LIBCPP_CXX03_LANG
+    template <class _Up> using rebind = _Up*;
+#else
+    template <class _Up> struct rebind {typedef _Up* other;};
+#endif
+
+private:
+    struct __nat {};
+public:
+    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
+    static pointer pointer_to(typename conditional<is_void<element_type>::value,
+                                      __nat, element_type>::type& __r) _NOEXCEPT
+        {return _VSTD::addressof(__r);}
+};
+
+template <class _From, class _To>
+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_BASE_H

libcxx/include/__memory/pointer_traits.h

-// -*- C++ -*-
-//===----------------------------------------------------------------------===//
-//
-// 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
-//
-//===----------------------------------------------------------------------===//
-
-#ifndef _LIBCPP___MEMORY_POINTER_TRAITS_H
-#define _LIBCPP___MEMORY_POINTER_TRAITS_H
-
-#include <__config>
-#include <type_traits>
-
-#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
-#pragma GCC system_header
-#endif
-
-_LIBCPP_PUSH_MACROS
-#include <__undef_macros>
-
-_LIBCPP_BEGIN_NAMESPACE_STD
-
-template <class _Tp, class = void>
-struct __has_element_type : false_type {};
-
-template <class _Tp>
-struct __has_element_type<_Tp,
-              typename __void_t<typename _Tp::element_type>::type> : true_type {};
-
-template <class _Ptr, bool = __has_element_type<_Ptr>::value>
-struct __pointer_traits_element_type;
-
-template <class _Ptr>
-struct __pointer_traits_element_type<_Ptr, true>
-{
-    typedef _LIBCPP_NODEBUG_TYPE typename _Ptr::element_type type;
-};
-
-template <template <class, class...> class _Sp, class _Tp, class ..._Args>
-struct __pointer_traits_element_type<_Sp<_Tp, _Args...>, true>
-{
-    typedef _LIBCPP_NODEBUG_TYPE typename _Sp<_Tp, _Args...>::element_type type;
-};
-
-template <template <class, class...> class _Sp, class _Tp, class ..._Args>
-struct __pointer_traits_element_type<_Sp<_Tp, _Args...>, false>
-{
-    typedef _LIBCPP_NODEBUG_TYPE _Tp type;
-};
-
-template <class _Tp, class = void>
-struct __has_difference_type : false_type {};
-
-template <class _Tp>
-struct __has_difference_type<_Tp,
-            typename __void_t<typename _Tp::difference_type>::type> : true_type {};
-
-template <class _Ptr, bool = __has_difference_type<_Ptr>::value>
-struct __pointer_traits_difference_type
-{
-    typedef _LIBCPP_NODEBUG_TYPE ptrdiff_t type;
-};
-
-template <class _Ptr>
-struct __pointer_traits_difference_type<_Ptr, true>
-{
-    typedef _LIBCPP_NODEBUG_TYPE typename _Ptr::difference_type type;
-};
-
-template <class _Tp, class _Up>
-struct __has_rebind
-{
-private:
-    struct __two {char __lx; char __lxx;};
-    template <class _Xp> static __two __test(...);
-    _LIBCPP_SUPPRESS_DEPRECATED_PUSH
-    template <class _Xp> static char __test(typename _Xp::template rebind<_Up>* = 0);
-    _LIBCPP_SUPPRESS_DEPRECATED_POP
-public:
-    static const bool value = sizeof(__test<_Tp>(0)) == 1;
-};
-
-template <class _Tp, class _Up, bool = __has_rebind<_Tp, _Up>::value>
-struct __pointer_traits_rebind
-{
-#ifndef _LIBCPP_CXX03_LANG
-    typedef _LIBCPP_NODEBUG_TYPE typename _Tp::template rebind<_Up> type;
-#else
-    typedef _LIBCPP_NODEBUG_TYPE typename _Tp::template rebind<_Up>::other type;
-#endif
-};
-
-template <template <class, class...> class _Sp, class _Tp, class ..._Args, class _Up>
-struct __pointer_traits_rebind<_Sp<_Tp, _Args...>, _Up, true>
-{
-#ifndef _LIBCPP_CXX03_LANG
-    typedef _LIBCPP_NODEBUG_TYPE typename _Sp<_Tp, _Args...>::template rebind<_Up> type;
-#else
-    typedef _LIBCPP_NODEBUG_TYPE typename _Sp<_Tp, _Args...>::template rebind<_Up>::other type;
-#endif
-};
-
-template <template <class, class...> class _Sp, class _Tp, class ..._Args, class _Up>
-struct __pointer_traits_rebind<_Sp<_Tp, _Args...>, _Up, false>
-{
-    typedef _Sp<_Up, _Args...> type;
-};
-
-template <class _Ptr>
-struct _LIBCPP_TEMPLATE_VIS pointer_traits
-{
-    typedef _Ptr                                                     pointer;
-    typedef typename __pointer_traits_element_type<pointer>::type    element_type;
-    typedef typename __pointer_traits_difference_type<pointer>::type difference_type;
-
-#ifndef _LIBCPP_CXX03_LANG
-    template <class _Up> using rebind = typename __pointer_traits_rebind<pointer, _Up>::type;
-#else
-    template <class _Up> struct rebind
-        {typedef typename __pointer_traits_rebind<pointer, _Up>::type other;};
-#endif  // _LIBCPP_CXX03_LANG
-
-private:
-    struct __nat {};
-public:
-    _LIBCPP_INLINE_VISIBILITY
-    static pointer pointer_to(typename conditional<is_void<element_type>::value,
-                                           __nat, element_type>::type& __r)
-        {return pointer::pointer_to(__r);}
-};
-
-template <class _Tp>
-struct _LIBCPP_TEMPLATE_VIS pointer_traits<_Tp*>
-{
-    typedef _Tp*      pointer;
-    typedef _Tp       element_type;
-    typedef ptrdiff_t difference_type;
-
-#ifndef _LIBCPP_CXX03_LANG
-    template <class _Up> using rebind = _Up*;
-#else
-    template <class _Up> struct rebind {typedef _Up* other;};
-#endif
-
-private:
-    struct __nat {};
-public:
-    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
-    static pointer pointer_to(typename conditional<is_void<element_type>::value,
-                                      __nat, element_type>::type& __r) _NOEXCEPT
-        {return _VSTD::addressof(__r);}
-};
-
-template <class _From, class _To>
-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
-};
-
-_LIBCPP_END_NAMESPACE_STD
-
-_LIBCPP_POP_MACROS
-
-#endif  // _LIBCPP___MEMORY_POINTER_TRAITS_H

libcxx/include/algorithm

 _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;
-}
-
-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();
-}
+// __unwrap_iter
+
+// 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.
+
+template <class _Iter, bool = __is_cpp17_contiguous_iterator<_Iter>::value>
+struct __unwrap_iter_impl {
+    static _LIBCPP_CONSTEXPR _Iter
+    __f(_Iter __i) _NOEXCEPT {
+        return __i;
+    }
+};
 
 #if _LIBCPP_DEBUG_LEVEL < 2
 
-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();
-}
-
-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>()))
+    __f(_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::__f(_VSTD::declval<_Iter>()))
+__unwrap_iter(_Iter __i) _NOEXCEPT
 {
-    return __i;
+    return _Impl::__f(__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)

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

 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 { };
-#endif
+
+// 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 {};
 
 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> : public false_type {};
+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_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> {};
-#else
 template <class _Tp>
-struct __is_cpp17_contiguous_iterator : public false_type {};
-#endif
+struct __is_cpp17_contiguous_iterator : _And<
+    __has_iterator_category_convertible_to<_Tp, random_access_iterator_tag>,
+    _Or<
+        __has_iterator_category_convertible_to<_Tp, contiguous_iterator_tag>,
+        __has_iterator_concept_convertible_to<_Tp, contiguous_iterator_tag>
+    >
+> {};
+
+// Any native pointer which is an iterator is also a contiguous iterator.
+template <class _Up>
+struct __is_cpp17_contiguous_iterator<_Up*> : __has_iterator_category_convertible_to<_Up*, random_access_iterator_tag> {};
 
 
 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> {};
 

 
 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;
+    typedef _If<__is_cpp17_contiguous_iterator<_Iter>::value,
+                contiguous_iterator_tag, iterator_category>            iterator_concept;
 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);
-#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

 #include <iterator>
 #include <__functional_base>
 #include <iosfwd>
 #include <tuple>
 #include <stdexcept>
 #include <cstring>
 #include <__memory/allocator_traits.h>
 #include <__memory/base.h>
-#include <__memory/pointer_traits.h>
 #include <__memory/utilities.h>
 #if !defined(_LIBCPP_HAS_NO_ATOMIC_HEADER)
 #  include <atomic>
 #endif
 #include <version>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
#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/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>
+
+// __libcpp_is_trivial_iterator determines if an iterator is a "trivial" one,
+// that can be used w/o worrying about its operations throwing exceptions.
+// Pointers are trivial iterators. Libc++ has three "iterator wrappers":
+// reverse_iterator, move_iterator, and __wrap_iter. If the underlying iterator
+// is trivial, then those are as well.
+//
+
+#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&);
+};
+
+class my_contiguous_iterator
+{
+    struct tag : std::contiguous_iterator_tag {};  // available in all modes as an extension
+    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&);
+};
+
+
+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<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), "");
+    static_assert(( std::__is_cpp17_contiguous_iterator<my_contiguous_iterator>::value), "");
+
+    // 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), "");
+    static_assert((!std::__is_cpp17_contiguous_iterator<std::move_iterator<my_contiguous_iterator> >::value), "");
+
+    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), "");
+    static_assert((!std::__is_cpp17_contiguous_iterator<std::reverse_iterator<my_contiguous_iterator> >::value), "");
+
+    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<my_random_access_iterator> >::value), "");
+    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<T *> > >::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::__wrap_iter<my_contiguous_iterator> > >::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<std::reverse_iterator<my_random_access_iterator> > >::value), "");
+    static_assert((!std::__is_cpp17_contiguous_iterator<std::__wrap_iter<std::reverse_iterator<my_contiguous_iterator> > >::value), "");
+
+
+//  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), "");
+    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), "");
+
+//  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), "");
+
+#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;
 }