Reapply "[libc++][ranges]Refactor `copy{,_backward}` and `move{,_backward}`"

[var-const]

Summary

This reverts commit a6e1080b87db8fbe0e1afadd96af5a3c0bd5e279.

Fix the conditions when the memmove optimization can be applied and refactor them out into a reusable type trait, fix and significantly expand the tests.

[var-const]

Apply the fix.

[var-const]

Expand testing.

[ldionne]

libcxx/include/__algorithm/copy_move_common.h

38

I would make this a proper boolean trait instead. It may make it easier to reuse elsewhere outside of SFINAE contexts.

39–45

After our discussion about is_trivially_copyable and is_trivially_<operation>, I think I would change this to:

(is_same<_In, _Out>::value && is_trivially_copyable<_In>::value) ||
(
  sizeof(_In) == sizeof(_Out) &&
  is_integral<_In>::value && is_integral<_Out>::value &&
  !(is_same<remove-cv(_In), bool>::value || is_same<remove-cv(_Out), bool>::value)
)

I read this as "first, the obviously correct case", and then "special casing for integral types that we know have the same value representation".

And then we could rename this to __type_traits/is_always_bitcastable? It's ugly but I think it conveys the idea of what we're trying to do here, which is essentially tell types for which bit_cast<To>(From) is *always* valid and never UB. This trait should also be documented (via comment).

libcxx/test/libcxx/algorithms/alg.modifying.operations/copy_move_nontrivial.pass.cpp

127

Why not this? That will make the testing below more complicated for bool but I think it makes sense.

[ldionne]

libcxx/test/libcxx/algorithms/alg.modifying.operations/copy_move_nontrivial.pass.cpp

152–153

I would do something like this?

static constexpr T array[N] = {...};
return array + i;

Another option would be to use a file-scope variable template.

[philnik]

libcxx/include/__algorithm/copy_move_common.h

52

Does this fix https://llvm.org/PR28901?

[var-const]

Address feedback, further expand testing.

libcxx/include/__algorithm/copy_move_common.h

52

Hmm, I couldn't immediately see how that issue is related, could you please double-check the link? If the link is correct, then I'm missing some context, sorry.

[var-const]

libcxx/include/__algorithm/copy_move_common.h

41

I think the volatile condition is only relevant for memmove and friends -- bit_cast is happy to convert between volatile and non-volatile, and __are_always_bitcastable should probably follow suit.

libcxx/include/__type_traits/are_always_bitcastable.h

25

This is my attempt to formalize the trait. Some things that I think are worth calling out:

• the way this is formulated is symmetrical -- not only T has to be bit-castable to U, but also U to T. Without this requirement, I wasn't sure how to express that the object size needs to be the same (if U is larger, then U can represent all values of T, so having this as just a one-way relationship didn't seem to work);

• related to the previous point, there is no precedent (that I found) for a type trait with a "plural" name (i.e., prefixed with are and not is). I chose the plural prefix to stress that this is a symmetric relationship between types;

• I chose to discard cv-qualifiers (IIUC, they don't affect bit_cast). memmove and friends don't work with volatile types, so this trait isn't fully sufficient to check whether memmove can be called;

• please double-check my reasoning. Part of the reason I tried to go through every possible case is to make it easier to notice if any of my assumptions are wrong.

33

Do we still need this in new code?

33

Do we need to inherit from integral_constant for internal traits?

45–47

This is the closest I could get to a "formal" definition of what this trait is trying to do. Please let me know what you think.

67

From testing, this currently isn't true -- somehow e.g. int[1] is considered bit-castable to itself.

68

(or so I think)

libcxx/test/libcxx/algorithms/alg.modifying.operations/copy_move_trivial.pass.cpp

237

Please let me know if you think this test is overkill (or alternatively, if you'd like to test more types -- I'm operating on the assumption that if it works for one signed/unsigned pair, it works for all of them).

libcxx/test/libcxx/type_traits/are_always_bitcastable.compile.pass.cpp

13

Please let me know if you think these tests are overkill.

16

I think it's better to avoid including this file from <type_traits> -- users shouldn't pay the extra compilation penalty for our internal stuff (even if that penalty is very small).

205

This is the behavior that we want, right?

211

I found it surprising, but arrays are currently considered bit-convertible. What do you think?

[var-const]

Fix the CI.

[philnik]

libcxx/include/__algorithm/copy_move_common.h

52

Not sure why the LLVM redirect is broken on this, here is the github link I meant: https://github.com/llvm/llvm-project/issues/28901

[ldionne]

I'll have another look but this LGTM w/ comments applied. Thanks a lot for all the work on this patch, the rabbit hole is much deeper than I initially thought.

libcxx/include/__algorithm/copy_move_common.h

42

Do we have a test with an _In and/or an _Out that is volatile?

libcxx/include/__type_traits/are_always_bitcastable.h

2

@jfb Just tagging you here in case you're curious to take a look. Your pair of eyes on this file would certainly be a bonus.

28

I would also add a mention of http://eel.is/c++draft/basic.types.general#3 which blesses what we're doing here with trivially copyable types.

33

_LIBCPP_TEMPLATE_VIS isn't needed, not because it's new code, but because this gives default visibility to a struct that doesn't require any visibility. There's nothing to give visibility to.

Do we need to inherit from integral_constant for internal traits?

No.

45–47

I think I like this.

60–62

libcxx/test/libcxx/algorithms/alg.modifying.operations/copy_move_trivial.pass.cpp

16–17

If it's just a warning, you could use // ADDITIONAL_COMPILE_FLAGS(gcc): -Wno-whatever.

libcxx/test/libcxx/type_traits/are_always_bitcastable.compile.pass.cpp

16

I would argue that's a "libc++ policy" decision and it's contrary to what we had agreed on when we started granularizing headers. IIRC, we had decided that a header like <foo> should include everything inside <__foo/*.h>, regardless of whether it's public API or not. That being said, that simply doesn't work -- I've run into cases where including everything inside <__foo/*.h> leads to circular dependencies, so this is something we'll likely have to revisit. The status quo is also that we are not systematically including all of <__foo/*.h>. So I'm fine with what you've done.

63–66

Then you get the same benefit for eliminating repetition, but IMO this is less arbitrary. And for the "same types" case, we're just instantiating the same function twice (well once really because compiler memoization).

68–71

IMO this doesn't pull its weight.

205

I think so, because references are not objects.

211

I think that for the purpose of this trait, we should probably also enforce that the two types are std::is_trivially_assignable_v<To, From>, and that would handle the array case. WDYT?

Perhaps this means that the name and purpose of the trait must change a tiny bit, maybe something like __copy_assignment_is_bitcast? Basically anything that will hint at the fact that this does a bit more than checking whether the two types are bit-castable, since we're also taking into account other unrelated language rules like t = u being valid. We should make sure to have a test that would catch it if our std::copy suddenly started to accept things that are not assignable to each other just because we are using std::memcpy under the hood.

[var-const]

Address feedback.

[var-const]

Link to the GitHub issue about volatile pointers.

[ldionne]

The title of the commit could be changed to "Reapply" instead of "Revert Revert" -- that's always a bit confusing IMO.

[ldionne]

libcxx/include/__type_traits/is_assignment_equivalent_to_bitcast.h

37–80 ↗

(On Diff #482744)

// This is the trait for the core type property, separate from syntactic requirements
template <class _From, class _To> // those are cv-unqualified types always
struct __is_always_bitcastable {
  static constexpr bool value = 
     // basic case, only one type, check that it's trivially copyable
     (is_same< _From, _To >::value && is_trivially_copyable<_From>::value) ||
     (
       sizeof(_From) == sizeof(_To) &&
       is_integral<_From>::value &&
       is_integral<_To>::value &&
       !is_same<_To, bool>::value
     );
};

// Then inside std::copy, do:
enable_if_t<
  is_assignable<_From, _To>::value && __is_always_bitcastable<_From, _To>::value
>
It copy(...) {
  // use memcpy, which we know is valid since __is_always_bitcastable is true
}

That should also make the tests for this trait less weird, since now it will be natural that array types are always bitcastable, per the definition of trivially-copyable.

libcxx/test/libcxx/type_traits/is_assignment_equivalent_to_bitcast.compile.pass.cpp

70–75 ↗

(On Diff #482744)

Let's inline this into check below? It's only used once.

[var-const]

Address feedback

[var-const]

libcxx/include/__algorithm/copy_move_common.h

42

Yes (the very last test case in copy_move_nontrivial.pass.cpp).

52

Yes, it fixes the compilation error when passing pointers to volatile. Thanks for finding the issue!

libcxx/include/__type_traits/are_always_bitcastable.h

28

Slightly rephrased as

In other words, `From` and `To` have the same value representation and the set of values of `From` is a subset of the set of values of `To`.

(I think that having the same object representation can be implied, but the bit about having the set of values is important because e.g. a boolean and its corresponding integer type are said to have the same value representation)

I'm not sure about adding that particular section. It explicitly blesses the simple case (copying between objects of the same type), but this trait is primarily for conversions.

libcxx/include/__type_traits/is_assignment_equivalent_to_bitcast.h

37–80 ↗

(On Diff #482744)

Done. Please check the new rationale for (rejecting) pointers. Arrays are accepted now like we discussed.

libcxx/test/libcxx/algorithms/alg.modifying.operations/copy_move_trivial.pass.cpp

16–17

I'm no longer getting that when running the buildbot locally. Perhaps the warning doesn't cover the case when the ambiguating function is a template. I'll wait for CI to be sure.

libcxx/test/libcxx/type_traits/are_always_bitcastable.compile.pass.cpp

16

Thanks for explaining the additional context!

211

I went with __is_assignment_equivalent_to_bitcast which is quite a mouthful -- happy to improve the name.

We might split this into two traits (one that doesn't check for is_trivially_assignable but checks everything else, and the other is a conjunction of the first trait and is_trivially_assignable), but I'd wait until we have a use case for that (assuming it's a good idea in the first place).

[var-const]

libcxx/test/libcxx/algorithms/alg.modifying.operations/copy_move_trivial.pass.cpp

16–17

Hmm, the CI still gets the error, and apparently it's a bona fide error, not just a warning. Unfortunately, I had to mark GCC as unsupported again.

[var-const]

Mark GCC as unsupported to fix the CI.

[var-const]

libcxx/include/valarray

4935

@ldionne I'm getting

$ "diff" "-w" "/llvm/libcxx/test/libcxx/transitive_includes/cxx2b.csv" "/llvm/build/generic-cxx2b/test/libcxx/Output/transitive_includes.sh.cpp.dir/t.tmp/transitive_includes.csv"
# command output:
*** /llvm/libcxx/test/libcxx/transitive_includes/cxx2b.csv
--- /llvm/build/generic-cxx2b/test/libcxx/Output/transitive_includes.sh.cpp.dir/t.tmp/transitive_includes.csv
***************
*** 722,728 ****
  valarraycmath
  valarraycstddef
  valarraycstdlib
- valarraycstring
  valarrayinitializer_list
  valarraylimits
  valarraynew
--- 722,727 ----

error: command failed with exit status: 1

What's the reason this is only defined in C++20 and below?

[philnik]

libcxx/include/valarray

4935

We've decided to remove all transitive includes from C++2b, since it's not considered stable. You can just remove the valarray cstring line from Cxx2b.csv.

[var-const]

Fix CI and rebase.

[var-const]

Fix CI.

[var-const]

Fix CI.

[var-const]

Rebase

[var-const]

Rebase

[var-const]

Try to fix the GCC crashes on the CI.

[var-const]

Fix the CI.

[var-const]

Rebase

[asbirlea]

Heads-up that we're seeing crashes due to the recommit of this change.
msan reports "use-of-uninitialized-value" in multiple places, where input is clearly initialized.

[var-const]

In D139235#4078362, @asbirlea wrote:

Heads-up that we're seeing crashes due to the recommit of this change.
msan reports "use-of-uninitialized-value" in multiple places, where input is clearly initialized.

Thank you for the heads-up. Can you provide more details?

[ldionne]

In D139235#4078375, @var-const wrote:

In D139235#4078362, @asbirlea wrote:

Heads-up that we're seeing crashes due to the recommit of this change.
msan reports "use-of-uninitialized-value" in multiple places, where input is clearly initialized.

Thank you for the heads-up. Can you provide more details?

This is going to be extremely difficult to back out since we've made changes on top of that. Please work with us to understand this issue and fix it forward ASAP. In particular, we will want to make sure it lands in LLVM 16 as early as possible.

Thanks!

[rupprecht]

Not a breakage report, but just a comment in case it wasn't expected/intended: it looks like this increases the conformance requirement for custom iterators passed to std::copy and friends. From a couple tests, it seems like gcc/libstdc++ already has stricter requirements than libc++, so the conformance requirement is being matched between libc++ and libstdc++ now. As an example:

struct MyIterator {
    using iterator_category = std::forward_iterator_tag;
    using value_type = float;
    // These two lines are now also needed
    // using pointer = float*;
    // using reference = const float&;
    using difference_type = std::ptrdiff_t;
    value_type operator*();
    MyIterator& operator++();
    friend bool operator==(const MyIterator&, const MyIterator&);
    friend bool operator!=(const MyIterator&, const MyIterator&);
};

void func() {
    std::vector<float> dest;
    std::copy(MyIterator(), MyIterator(), std::back_inserter(dest));
}

https://godbolt.org/z/jTdbT4xcP

It seems pretty clear the change here is correct, this is just an FYI of the impact & in case anyone else bumps into this.

[alexfh]

We've found the cause of the problems @asbirlea reported above: violation of aliasing rules. Something similar to this snippet: https://gcc.godbolt.org/z/3Y9GEMW4e

Thus, again, the change is correct, but it's worth mentioning in the release notes that more aggressive optimizations in std::copy and friends may expose a lot more UB around std::vector and not only.

[var-const]

@alexfh @asbirlea @rupprecht Thank you for calling this out. Added notes about potential breakages of existing code to the release notes in https://github.com/llvm/llvm-project/commit/abda3e523ade7377b03a25dc2b6192dbe855c567

libcxx/include/CMakeLists.txt

 set(files
   __algorithm/adjacent_find.h
   __algorithm/all_of.h
   __algorithm/any_of.h
   __algorithm/binary_search.h
   __algorithm/clamp.h
   __algorithm/comp.h
   __algorithm/comp_ref_type.h
   __algorithm/copy.h
   __algorithm/copy_backward.h
   __algorithm/copy_if.h
+  __algorithm/copy_move_common.h
   __algorithm/copy_n.h
   __algorithm/count.h
   __algorithm/count_if.h
   __algorithm/equal.h
   __algorithm/equal_range.h
   __algorithm/fill.h
   __algorithm/fill_n.h
   __algorithm/find.h
set(files
   __type_traits/add_lvalue_reference.h
   __type_traits/add_pointer.h
   __type_traits/add_rvalue_reference.h
   __type_traits/add_volatile.h
   __type_traits/aligned_storage.h
   __type_traits/aligned_union.h
   __type_traits/alignment_of.h
   __type_traits/apply_cv.h
+  __type_traits/are_always_bitcastable.h
   __type_traits/can_extract_key.h
   __type_traits/common_reference.h
   __type_traits/common_type.h
   __type_traits/conditional.h
   __type_traits/conjunction.h
   __type_traits/copy_cv.h
   __type_traits/copy_cvref.h
   __type_traits/decay.h

libcxx/include/__algorithm/copy.h

 //===----------------------------------------------------------------------===//
 //
 // 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___ALGORITHM_COPY_H
 #define _LIBCPP___ALGORITHM_COPY_H
 
-#include <__algorithm/unwrap_iter.h>
-#include <__algorithm/unwrap_range.h>
+#include <__algorithm/copy_move_common.h>
+#include <__algorithm/iterator_operations.h>
 #include <__config>
-#include <__iterator/iterator_traits.h>
-#include <__iterator/reverse_iterator.h>
 #include <__utility/move.h>
 #include <__utility/pair.h>
-#include <cstring>
-#include <type_traits>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
-// copy
-
+struct __copy_loop {
   template <class _InIter, class _Sent, class _OutIter>
-inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14
-pair<_InIter, _OutIter> __copy_impl(_InIter __first, _Sent __last, _OutIter __result) {
+  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 pair<_InIter, _OutIter>
+  operator()(_InIter __first, _Sent __last, _OutIter __result) const {
     while (__first != __last) {
       *__result = *__first;
       ++__first;
       ++__result;
     }
-  return pair<_InIter, _OutIter>(std::move(__first), std::move(__result));
-}
 
-template <class _InValueT,
-          class _OutValueT,
-          class = __enable_if_t<is_same<__remove_const_t<_InValueT>, _OutValueT>::value
-                             && is_trivially_copy_assignable<_OutValueT>::value> >
-inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14
-pair<_InValueT*, _OutValueT*> __copy_impl(_InValueT* __first, _InValueT* __last, _OutValueT* __result) {
-  if (__libcpp_is_constant_evaluated()
-// TODO: Remove this once GCC supports __builtin_memmove during constant evaluation
-#ifndef _LIBCPP_COMPILER_GCC
-      && !is_trivially_copyable<_InValueT>::value
-#endif
-     )
-    return std::__copy_impl<_InValueT*, _InValueT*, _OutValueT*>(__first, __last, __result);
-  const size_t __n = static_cast<size_t>(__last - __first);
-  if (__n > 0)
-    ::__builtin_memmove(__result, __first, __n * sizeof(_OutValueT));
-  return std::make_pair(__first + __n, __result + __n);
+    return std::make_pair(std::move(__first), std::move(__result));
   }
+};
 
-template <class _InIter, class _OutIter,
-          __enable_if_t<is_same<__remove_const_t<__iter_value_type<_InIter> >, __iter_value_type<_OutIter> >::value
-                      && __is_cpp17_contiguous_iterator<typename _InIter::iterator_type>::value
-                      && __is_cpp17_contiguous_iterator<typename _OutIter::iterator_type>::value
-                      && is_trivially_copy_assignable<__iter_value_type<_OutIter> >::value
-                      && __is_reverse_iterator<_InIter>::value
-                      && __is_reverse_iterator<_OutIter>::value, int> = 0>
-inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14
-pair<_InIter, _OutIter>
-__copy_impl(_InIter __first, _InIter __last, _OutIter __result) {
-  auto __first_base = std::__unwrap_iter(__first.base());
-  auto __last_base = std::__unwrap_iter(__last.base());
-  auto __result_base = std::__unwrap_iter(__result.base());
-  auto __result_first = __result_base - (__first_base - __last_base);
-  std::__copy_impl(__last_base, __first_base, __result_first);
-  return std::make_pair(__last, _OutIter(std::__rewrap_iter(__result.base(), __result_first)));
+struct __copy_trivial {
+  // At this point, the iterators have been unwrapped so any `contiguous_iterator` has been unwrapped to a pointer.
+  template <class _In, class _Out, __enable_if_memmovable<_In, _Out> = 0>
+  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 pair<_In*, _Out*>
+  operator()(_In* __first, _In* __last, _Out* __result) const {
+    return std::__copy_trivial_impl(__first, __last, __result);
   }
+};
 
-template <class _InIter, class _Sent, class _OutIter,
-          __enable_if_t<!(is_copy_constructible<_InIter>::value
-                       && is_copy_constructible<_Sent>::value
-                       && is_copy_constructible<_OutIter>::value), int> = 0 >
-inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14
-pair<_InIter, _OutIter> __copy(_InIter __first, _Sent __last, _OutIter __result) {
-  return std::__copy_impl(std::move(__first), std::move(__last), std::move(__result));
-}
-
-template <class _InIter, class _Sent, class _OutIter,
-          __enable_if_t<is_copy_constructible<_InIter>::value
-                     && is_copy_constructible<_Sent>::value
-                     && is_copy_constructible<_OutIter>::value, int> = 0>
+template <class _AlgPolicy, class _InIter, class _Sent, class _OutIter>
+pair<_InIter, _OutIter>
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14
-pair<_InIter, _OutIter> __copy(_InIter __first, _Sent __last, _OutIter __result) {
-  auto __range = std::__unwrap_range(__first, __last);
-  auto __ret   = std::__copy_impl(std::move(__range.first), std::move(__range.second), std::__unwrap_iter(__result));
-  return std::make_pair(
-      std::__rewrap_range<_Sent>(__first, __ret.first), std::__rewrap_iter(__result, __ret.second));
+__copy(_InIter __first, _Sent __last, _OutIter __result) {
+  return std::__dispatch_copy_or_move<_AlgPolicy, __copy_loop, __copy_trivial>(
+      std::move(__first), std::move(__last), std::move(__result));
 }
 
 template <class _InputIterator, class _OutputIterator>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20
 _OutputIterator
 copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result) {
-  return std::__copy(__first, __last, __result).second;
+  return std::__copy<_ClassicAlgPolicy>(__first, __last, __result).second;
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_COPY_H

libcxx/include/__algorithm/copy_backward.h

 //===----------------------------------------------------------------------===//
 //
 // 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___ALGORITHM_COPY_BACKWARD_H
 #define _LIBCPP___ALGORITHM_COPY_BACKWARD_H
 
-#include <__algorithm/copy.h>
+#include <__algorithm/copy_move_common.h>
 #include <__algorithm/iterator_operations.h>
-#include <__algorithm/ranges_copy.h>
-#include <__algorithm/unwrap_iter.h>
-#include <__concepts/same_as.h>
 #include <__config>
-#include <__iterator/iterator_traits.h>
-#include <__iterator/reverse_iterator.h>
-#include <__ranges/subrange.h>
 #include <__utility/move.h>
 #include <__utility/pair.h>
-#include <cstring>
-#include <type_traits>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
-template <class _AlgPolicy, class _InputIterator, class _OutputIterator,
-          __enable_if_t<is_same<_AlgPolicy, _ClassicAlgPolicy>::value, int> = 0>
-inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 pair<_InputIterator, _OutputIterator>
-__copy_backward(_InputIterator __first, _InputIterator __last, _OutputIterator __result) {
-  auto __ret = std::__copy(
-      __unconstrained_reverse_iterator<_InputIterator>(__last),
-      __unconstrained_reverse_iterator<_InputIterator>(__first),
-      __unconstrained_reverse_iterator<_OutputIterator>(__result));
-  return pair<_InputIterator, _OutputIterator>(__ret.first.base(), __ret.second.base());
+template <class _AlgPolicy>
+struct __copy_backward_loop {
+  template <class _InIter, class _Sent, class _OutIter>
+  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 pair<_InIter, _OutIter>
+  operator()(_InIter __first, _Sent __last, _OutIter __result) const {
+    auto __last_iter          = _IterOps<_AlgPolicy>::next(__first, __last);
+    auto __original_last_iter = __last_iter;
+
+    while (__first != __last_iter) {
+      *--__result = *--__last_iter;
+    }
+
+    return std::make_pair(std::move(__original_last_iter), std::move(__result));
   }
+};
 
-#if _LIBCPP_STD_VER > 17
-template <class _AlgPolicy, class _Iter1, class _Sent1, class _Iter2,
-          __enable_if_t<is_same<_AlgPolicy, _RangeAlgPolicy>::value, int> = 0>
-_LIBCPP_HIDE_FROM_ABI constexpr pair<_Iter1, _Iter2> __copy_backward(_Iter1 __first, _Sent1 __last, _Iter2 __result) {
-  auto __last_iter     = _IterOps<_AlgPolicy>::next(__first, std::move(__last));
-  auto __reverse_range = std::__reverse_range(std::ranges::subrange(std::move(__first), __last_iter));
-  auto __ret           = ranges::copy(std::move(__reverse_range), std::make_reverse_iterator(__result));
-  return std::make_pair(__last_iter, __ret.out.base());
+struct __copy_backward_trivial {
+  // At this point, the iterators have been unwrapped so any `contiguous_iterator` has been unwrapped to a pointer.
+  template <class _In, class _Out, __enable_if_memmovable<_In, _Out> = 0>
+  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 pair<_In*, _Out*>
+  operator()(_In* __first, _In* __last, _Out* __result) const {
+    return std::__copy_backward_trivial_impl(__first, __last, __result);
+  }
+};
+
+template <class _AlgPolicy, class _BidirectionalIterator1, class _Sentinel, class _BidirectionalIterator2>
+_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
+pair<_BidirectionalIterator1, _BidirectionalIterator2>
+__copy_backward(_BidirectionalIterator1 __first, _Sentinel __last, _BidirectionalIterator2 __result) {
+  return std::__dispatch_copy_or_move<_AlgPolicy, __copy_backward_loop<_AlgPolicy>, __copy_backward_trivial>(
+      std::move(__first), std::move(__last), std::move(__result));
 }
-#endif // _LIBCPP_STD_VER > 17
 
 template <class _BidirectionalIterator1, class _BidirectionalIterator2>
-inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _BidirectionalIterator2
-copy_backward(_BidirectionalIterator1 __first, _BidirectionalIterator1 __last, _BidirectionalIterator2 __result) {
-  return std::__copy_backward<_ClassicAlgPolicy>(__first, __last, __result).second;
+inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
+_BidirectionalIterator2
+copy_backward(_BidirectionalIterator1 __first, _BidirectionalIterator1 __last,
+              _BidirectionalIterator2 __result)
+{
+  static_assert(std::is_copy_constructible<_BidirectionalIterator1>::value &&
+                std::is_copy_constructible<_BidirectionalIterator1>::value, "Iterators must be copy constructible.");
+
+  return std::__copy_backward<_ClassicAlgPolicy>(
+      std::move(__first), std::move(__last), std::move(__result)).second;
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_COPY_BACKWARD_H

libcxx/include/__algorithm/copy_move_common.h

+//===----------------------------------------------------------------------===//
+//
+// 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___ALGORITHM_COPY_MOVE_COMMON_H
+#define _LIBCPP___ALGORITHM_COPY_MOVE_COMMON_H
+
+#include <__algorithm/iterator_operations.h>
+#include <__algorithm/unwrap_iter.h>
+#include <__algorithm/unwrap_range.h>
+#include <__config>
+#include <__iterator/iterator_traits.h>
+#include <__memory/pointer_traits.h>
+#include <__type_traits/are_always_bitcastable.h>
+#include <__type_traits/enable_if.h>
+#include <__type_traits/is_constant_evaluated.h>
+#include <__type_traits/is_copy_constructible.h>
+#include <__type_traits/is_trivially_copyable.h>
+#include <__type_traits/is_volatile.h>
+#include <__utility/move.h>
+#include <__utility/pair.h>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#  pragma GCC system_header
+#endif
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+// Type trait.
+
+template <class _In, class _Out>
+using __enable_if_memmovable = __enable_if_t<
+    // If the types are always bitcastable, it's valid to do a bitwise copy between them and the result is equivalent to
+    // using built-in assignment.
+    __are_always_bitcastable<_In, _Out>::value &&
+    // `memmove` doesn't accept `volatile` pointers, make sure the optimization SFINAEs away in that case.
+    !is_volatile<_In>::value &&
+    !is_volatile<_Out>::value
+, int>;
+
+// `memmove` algorithms implementation.
+
+template <class _In, class _Out>
+_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 pair<_In*, _Out*>
+__copy_trivial_impl(_In* __first, _In* __last, _Out* __result) {
+  const size_t __n = static_cast<size_t>(__last - __first);
+  ::__builtin_memmove(__result, __first, __n * sizeof(_Out));
+
+  return std::make_pair(__last, __result + __n);
+}
+
+template <class _In, class _Out>
+_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 pair<_In*, _Out*>
+__copy_backward_trivial_impl(_In* __first, _In* __last, _Out* __result) {
+  const size_t __n = static_cast<size_t>(__last - __first);
+  __result -= __n;
+
+  ::__builtin_memmove(__result, __first, __n * sizeof(_Out));
+
+  return std::make_pair(__last, __result);
+}
+
+// Iterator unwrapping and dispatching to the correct overload.
+
+template <class _F1, class _F2>
+struct __overload : _F1, _F2 {
+  using _F1::operator();
+  using _F2::operator();
+};
+
+template <class _InIter, class _Sent, class _OutIter, class = void>
+struct __can_rewrap : false_type {};
+
+template <class _InIter, class _Sent, class _OutIter>
+struct __can_rewrap<_InIter,
+                    _Sent,
+                    _OutIter,
+                    // Note that sentinels are always copy-constructible.
+                    __enable_if_t< is_copy_constructible<_InIter>::value &&
+                                   is_copy_constructible<_OutIter>::value > > : true_type {};
+
+template <class _Algorithm,
+          class _InIter,
+          class _Sent,
+          class _OutIter,
+          __enable_if_t<__can_rewrap<_InIter, _Sent, _OutIter>::value, int> = 0>
+_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17 pair<_InIter, _OutIter>
+__unwrap_and_dispatch(_InIter __first, _Sent __last, _OutIter __out_first) {
+  auto __range  = std::__unwrap_range(__first, std::move(__last));
+  auto __result = _Algorithm()(std::move(__range.first), std::move(__range.second), std::__unwrap_iter(__out_first));
+  return std::make_pair(std::__rewrap_range<_Sent>(std::move(__first), std::move(__result.first)),
+                                 std::__rewrap_iter(std::move(__out_first), std::move(__result.second)));
+}
+
+template <class _Algorithm,
+          class _InIter,
+          class _Sent,
+          class _OutIter,
+          __enable_if_t<!__can_rewrap<_InIter, _Sent, _OutIter>::value, int> = 0>
+_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17 pair<_InIter, _OutIter>
+__unwrap_and_dispatch(_InIter __first, _Sent __last, _OutIter __out_first) {
+  return _Algorithm()(std::move(__first), std::move(__last), std::move(__out_first));
+}
+
+template <class _IterOps, class _InValue, class _OutIter, class = void>
+struct __can_copy_without_conversion : false_type {};
+
+template <class _IterOps, class _InValue, class _OutIter>
+struct __can_copy_without_conversion<
+    _IterOps,
+    _InValue,
+    _OutIter,
+    __enable_if_t<is_same<_InValue, typename _IterOps::template __value_type<_OutIter> >::value> > : true_type {};
+
+template <class _AlgPolicy,
+          class _NaiveAlgorithm,
+          class _OptimizedAlgorithm,
+          class _InIter,
+          class _Sent,
+          class _OutIter>
+_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17 pair<_InIter, _OutIter>
+__dispatch_copy_or_move(_InIter __first, _Sent __last, _OutIter __out_first) {
+#ifdef _LIBCPP_COMPILER_GCC
+  // GCC doesn't support `__builtin_memmove` during constant evaluation.
+  if (__libcpp_is_constant_evaluated()) {
+    return std::__unwrap_and_dispatch<_NaiveAlgorithm>(std::move(__first), std::move(__last), std::move(__out_first));
+  }
+#else
+  // In Clang, `__builtin_memmove` only supports fully trivially copyable types (just having trivial copy assignment is
+  // insufficient). Also, conversions are not supported.
+  if (__libcpp_is_constant_evaluated()) {
+    using _InValue = typename _IterOps<_AlgPolicy>::template __value_type<_InIter>;
+    if (!is_trivially_copyable<_InValue>::value ||
+        !__can_copy_without_conversion<_IterOps<_AlgPolicy>, _InValue, _OutIter>::value) {
+      return std::__unwrap_and_dispatch<_NaiveAlgorithm>(std::move(__first), std::move(__last), std::move(__out_first));
+    }
+  }
+#endif // _LIBCPP_COMPILER_GCC
+
+  using _Algorithm = __overload<_NaiveAlgorithm, _OptimizedAlgorithm>;
+  return std::__unwrap_and_dispatch<_Algorithm>(std::move(__first), std::move(__last), std::move(__out_first));
+}
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP___ALGORITHM_COPY_MOVE_COMMON_H

libcxx/include/__algorithm/move.h

 //===----------------------------------------------------------------------===//
 //
 // 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___ALGORITHM_MOVE_H
 #define _LIBCPP___ALGORITHM_MOVE_H
 
+#include <__algorithm/copy_move_common.h>
 #include <__algorithm/iterator_operations.h>
-#include <__algorithm/unwrap_iter.h>
 #include <__config>
-#include <__iterator/iterator_traits.h>
-#include <__iterator/reverse_iterator.h>
 #include <__utility/move.h>
 #include <__utility/pair.h>
-#include <cstring>
-#include <type_traits>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
-// move
-
-template <class _AlgPolicy, class _InIter, class _Sent, class _OutIter>
-inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX17
-pair<_InIter, _OutIter> __move_impl(_InIter __first, _Sent __last, _OutIter __result) {
+template <class _AlgPolicy>
+struct __move_loop {
+  template <class _InIter, class _Sent, class _OutIter>
+  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 pair<_InIter, _OutIter>
+  operator()(_InIter __first, _Sent __last, _OutIter __result) const {
     while (__first != __last) {
       *__result = _IterOps<_AlgPolicy>::__iter_move(__first);
       ++__first;
       ++__result;
     }
     return std::make_pair(std::move(__first), std::move(__result));
   }
+};
 
-template <class _AlgPolicy,
-          class _InType,
-          class _OutType,
-          class = __enable_if_t<is_same<__remove_const_t<_InType>, _OutType>::value
-                             && is_trivially_move_assignable<_OutType>::value> >
-inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14
-pair<_InType*, _OutType*> __move_impl(_InType* __first, _InType* __last, _OutType* __result) {
-  if (__libcpp_is_constant_evaluated()
-// TODO: Remove this once GCC supports __builtin_memmove during constant evaluation
-#ifndef _LIBCPP_COMPILER_GCC
-   && !is_trivially_copyable<_InType>::value
-#endif
-     )
-    return std::__move_impl<_AlgPolicy, _InType*, _InType*, _OutType*>(__first, __last, __result);
-  const size_t __n = static_cast<size_t>(__last - __first);
-  ::__builtin_memmove(__result, __first, __n * sizeof(_OutType));
-  return std::make_pair(__first + __n, __result + __n);
-}
-
-template <class>
-struct __is_trivially_move_assignable_unwrapped_impl : false_type {};
-
-template <class _Type>
-struct __is_trivially_move_assignable_unwrapped_impl<_Type*> : is_trivially_move_assignable<_Type> {};
-
-template <class _Iter>
-struct __is_trivially_move_assignable_unwrapped
-    : __is_trivially_move_assignable_unwrapped_impl<decltype(std::__unwrap_iter<_Iter>(std::declval<_Iter>()))> {};
-
-template <class _AlgPolicy,
-          class _InIter,
-          class _OutIter,
-          __enable_if_t<is_same<__remove_const_t<typename iterator_traits<_InIter>::value_type>,
-                                typename iterator_traits<_OutIter>::value_type>::value
-                     && __is_cpp17_contiguous_iterator<_InIter>::value
-                     && __is_cpp17_contiguous_iterator<_OutIter>::value
-                     && is_trivially_move_assignable<__iter_value_type<_OutIter> >::value, int> = 0>
-inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17
-pair<reverse_iterator<_InIter>, reverse_iterator<_OutIter> >
-__move_impl(reverse_iterator<_InIter> __first,
-            reverse_iterator<_InIter> __last,
-            reverse_iterator<_OutIter> __result) {
-  auto __first_base = std::__unwrap_iter(__first.base());
-  auto __last_base = std::__unwrap_iter(__last.base());
-  auto __result_base = std::__unwrap_iter(__result.base());
-  auto __result_first = __result_base - (__first_base - __last_base);
-  std::__move_impl<_AlgPolicy>(__last_base, __first_base, __result_first);
-  return std::make_pair(__last, reverse_iterator<_OutIter>(std::__rewrap_iter(__result.base(), __result_first)));
-}
-
-template <class _AlgPolicy, class _InIter, class _Sent, class _OutIter>
-inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14
-__enable_if_t<is_copy_constructible<_InIter>::value
-           && is_copy_constructible<_Sent>::value
-           && is_copy_constructible<_OutIter>::value, pair<_InIter, _OutIter> >
-__move(_InIter __first, _Sent __last, _OutIter __result) {
-  auto __ret = std::__move_impl<_AlgPolicy>(
-      std::__unwrap_iter(__first), std::__unwrap_iter(__last), std::__unwrap_iter(__result));
-  return std::make_pair(std::__rewrap_iter(__first, __ret.first), std::__rewrap_iter(__result, __ret.second));
+struct __move_trivial {
+  // At this point, the iterators have been unwrapped so any `contiguous_iterator` has been unwrapped to a pointer.
+  template <class _In, class _Out, __enable_if_memmovable<_In, _Out> = 0>
+  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 pair<_In*, _Out*>
+  operator()(_In* __first, _In* __last, _Out* __result) const {
+    return std::__copy_trivial_impl(__first, __last, __result);
   }
+};
 
 template <class _AlgPolicy, class _InIter, class _Sent, class _OutIter>
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14
-__enable_if_t<!is_copy_constructible<_InIter>::value
-           || !is_copy_constructible<_Sent>::value
-           || !is_copy_constructible<_OutIter>::value, pair<_InIter, _OutIter> >
+pair<_InIter, _OutIter>
 __move(_InIter __first, _Sent __last, _OutIter __result) {
-  return std::__move_impl<_AlgPolicy>(std::move(__first), std::move(__last), std::move(__result));
+  return std::__dispatch_copy_or_move<_AlgPolicy, __move_loop<_AlgPolicy>, __move_trivial>(
+      std::move(__first), std::move(__last), std::move(__result));
 }
 
 template <class _InputIterator, class _OutputIterator>
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
 _OutputIterator move(_InputIterator __first, _InputIterator __last, _OutputIterator __result) {
-  return std::__move<_ClassicAlgPolicy>(__first, __last, __result).second;
+  static_assert(is_copy_constructible<_InputIterator>::value, "Iterators has to be copy constructible.");
+  static_assert(is_copy_constructible<_OutputIterator>::value, "The output iterator has to be copy constructible.");
+
+  return std::__move<_ClassicAlgPolicy>(
+      std::move(__first), std::move(__last), std::move(__result)).second;
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_MOVE_H

libcxx/include/__algorithm/move_backward.h

 //===----------------------------------------------------------------------===//
 //
 // 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___ALGORITHM_MOVE_BACKWARD_H
 #define _LIBCPP___ALGORITHM_MOVE_BACKWARD_H
 
+#include <__algorithm/copy_move_common.h>
 #include <__algorithm/iterator_operations.h>
-#include <__algorithm/unwrap_iter.h>
 #include <__config>
 #include <__utility/move.h>
-#include <cstring>
-#include <type_traits>
+#include <__utility/pair.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
-template <class _AlgPolicy, class _InputIterator, class _OutputIterator>
-inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX17
-_OutputIterator
-__move_backward_constexpr(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
-{
-    while (__first != __last)
-        *--__result = _IterOps<_AlgPolicy>::__iter_move(--__last);
-    return __result;
-}
-
-template <class _AlgPolicy, class _InputIterator, class _OutputIterator>
-inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX17
-_OutputIterator
-__move_backward_impl(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
-{
-    return _VSTD::__move_backward_constexpr<_AlgPolicy>(__first, __last, __result);
-}
+template <class _AlgPolicy>
+struct __move_backward_loop {
+  template <class _InIter, class _Sent, class _OutIter>
+  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 pair<_InIter, _OutIter>
+  operator()(_InIter __first, _Sent __last, _OutIter __result) const {
+    auto __last_iter          = _IterOps<_AlgPolicy>::next(__first, __last);
+    auto __original_last_iter = __last_iter;
+
+    while (__first != __last_iter) {
+      *--__result = _IterOps<_AlgPolicy>::__iter_move(--__last_iter);
+    }
+
+    return std::make_pair(std::move(__original_last_iter), std::move(__result));
+  }
+};
+
+struct __move_backward_trivial {
+  // At this point, the iterators have been unwrapped so any `contiguous_iterator` has been unwrapped to a pointer.
+  template <class _In, class _Out, __enable_if_memmovable<_In, _Out> = 0>
+  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 pair<_In*, _Out*>
+  operator()(_In* __first, _In* __last, _Out* __result) const {
+    return std::__copy_backward_trivial_impl(__first, __last, __result);
+  }
+};
+
+template <class _AlgPolicy, class _BidirectionalIterator1, class _Sentinel, class _BidirectionalIterator2>
+_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
+pair<_BidirectionalIterator1, _BidirectionalIterator2>
+__move_backward(_BidirectionalIterator1 __first, _Sentinel __last, _BidirectionalIterator2 __result) {
+  static_assert(std::is_copy_constructible<_BidirectionalIterator1>::value &&
+                std::is_copy_constructible<_BidirectionalIterator1>::value, "Iterators must be copy constructible.");
 
-template <class _AlgPolicy, class _Tp, class _Up>
-inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX17
-typename enable_if
-<
-    is_same<__remove_const_t<_Tp>, _Up>::value &&
-    is_trivially_move_assignable<_Up>::value,
-    _Up*
->::type
-__move_backward_impl(_Tp* __first, _Tp* __last, _Up* __result)
-{
-    const size_t __n = static_cast<size_t>(__last - __first);
-    if (__n > 0)
-    {
-        __result -= __n;
-        _VSTD::memmove(__result, __first, __n * sizeof(_Up));
-    }
-    return __result;
-}
-
-template <class _AlgPolicy, class _BidirectionalIterator1, class _BidirectionalIterator2>
-inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20
-_BidirectionalIterator2
-__move_backward(_BidirectionalIterator1 __first, _BidirectionalIterator1 __last,
-                _BidirectionalIterator2 __result)
-{
-    if (__libcpp_is_constant_evaluated()) {
-        return _VSTD::__move_backward_constexpr<_AlgPolicy>(__first, __last, __result);
-    } else {
-        return _VSTD::__rewrap_iter(__result,
-            _VSTD::__move_backward_impl<_AlgPolicy>(_VSTD::__unwrap_iter(__first),
-                                                    _VSTD::__unwrap_iter(__last),
-                                                    _VSTD::__unwrap_iter(__result)));
-    }
+  return std::__dispatch_copy_or_move<_AlgPolicy, __move_backward_loop<_AlgPolicy>, __move_backward_trivial>(
+      std::move(__first), std::move(__last), std::move(__result));
 }
 
 template <class _BidirectionalIterator1, class _BidirectionalIterator2>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20
 _BidirectionalIterator2
 move_backward(_BidirectionalIterator1 __first, _BidirectionalIterator1 __last,
               _BidirectionalIterator2 __result)
 {
-  return std::__move_backward<_ClassicAlgPolicy>(std::move(__first), std::move(__last), std::move(__result));
+  return std::__move_backward<_ClassicAlgPolicy>(
+      std::move(__first), std::move(__last), std::move(__result)).second;
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_MOVE_BACKWARD_H

libcxx/include/__algorithm/ranges_copy.h

 //===----------------------------------------------------------------------===//
 //
 // 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___ALGORITHM_RANGES_COPY_H
 #define _LIBCPP___ALGORITHM_RANGES_COPY_H
 
 #include <__algorithm/copy.h>
 #include <__algorithm/in_out_result.h>
+#include <__algorithm/iterator_operations.h>
 #include <__config>
 #include <__functional/identity.h>
 #include <__iterator/concepts.h>
 #include <__ranges/access.h>
 #include <__ranges/concepts.h>
 #include <__ranges/dangling.h>
 #include <__utility/move.h>
 #include <__utility/pair.h>

 
 namespace __copy {
 struct __fn {
 
   template <input_iterator _InIter, sentinel_for<_InIter> _Sent, weakly_incrementable _OutIter>
     requires indirectly_copyable<_InIter, _OutIter>
   _LIBCPP_HIDE_FROM_ABI constexpr
   copy_result<_InIter, _OutIter> operator()(_InIter __first, _Sent __last, _OutIter __result) const {
-    auto __ret = std::__copy(std::move(__first), std::move(__last), std::move(__result));
+    auto __ret = std::__copy<_RangeAlgPolicy>(std::move(__first), std::move(__last), std::move(__result));
     return {std::move(__ret.first), std::move(__ret.second)};
   }
 
   template <input_range _Range, weakly_incrementable _OutIter>
     requires indirectly_copyable<iterator_t<_Range>, _OutIter>
   _LIBCPP_HIDE_FROM_ABI constexpr
   copy_result<borrowed_iterator_t<_Range>, _OutIter> operator()(_Range&& __r, _OutIter __result) const {
-    auto __ret = std::__copy(ranges::begin(__r), ranges::end(__r), std::move(__result));
+    auto __ret = std::__copy<_RangeAlgPolicy>(ranges::begin(__r), ranges::end(__r), std::move(__result));
     return {std::move(__ret.first), std::move(__ret.second)};
   }
 };
 } // namespace __copy
 
 inline namespace __cpo {
   inline constexpr auto copy = __copy::__fn{};
 } // namespace __cpo
 } // namespace ranges
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP_STD_VER > 17
 
 #endif // _LIBCPP___ALGORITHM_RANGES_COPY_H

libcxx/include/__algorithm/ranges_copy_backward.h

 //===----------------------------------------------------------------------===//
 //
 // 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___ALGORITHM_RANGES_COPY_BACKWARD_H
 #define _LIBCPP___ALGORITHM_RANGES_COPY_BACKWARD_H
 
 #include <__algorithm/copy_backward.h>
 #include <__algorithm/in_out_result.h>
 #include <__algorithm/iterator_operations.h>
 #include <__config>
 #include <__iterator/concepts.h>
-#include <__iterator/reverse_iterator.h>
 #include <__ranges/access.h>
 #include <__ranges/concepts.h>
 #include <__ranges/dangling.h>
 #include <__utility/move.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif

libcxx/include/__algorithm/ranges_copy_n.h

 //===----------------------------------------------------------------------===//
 //
 // 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___ALGORITHM_RANGES_COPY_N_H
 #define _LIBCPP___ALGORITHM_RANGES_COPY_N_H
 
 #include <__algorithm/copy.h>
 #include <__algorithm/in_out_result.h>
+#include <__algorithm/iterator_operations.h>
 #include <__algorithm/ranges_copy.h>
 #include <__config>
 #include <__functional/identity.h>
 #include <__iterator/concepts.h>
 #include <__iterator/incrementable_traits.h>
 #include <__iterator/unreachable_sentinel.h>
 #include <__iterator/wrap_iter.h>
 #include <__utility/move.h>
while (__n != 0) {
       --__n;
     }
     return {std::move(__first), std::move(__result)};
   }
 
   template <random_access_iterator _InIter, class _DiffType, random_access_iterator _OutIter>
   _LIBCPP_HIDE_FROM_ABI constexpr static
   copy_n_result<_InIter, _OutIter> __go(_InIter __first, _DiffType __n, _OutIter __result) {
-    auto __ret = std::__copy(__first, __first + __n, __result);
+    auto __ret = std::__copy<_RangeAlgPolicy>(__first, __first + __n, __result);
     return {__ret.first, __ret.second};
   }
 
   template <input_iterator _Ip, weakly_incrementable _Op>
     requires indirectly_copyable<_Ip, _Op>
   _LIBCPP_HIDE_FROM_ABI constexpr
   copy_n_result<_Ip, _Op> operator()(_Ip __first, iter_difference_t<_Ip> __n, _Op __result) const {
     return __go(std::move(__first), __n, std::move(__result));

libcxx/include/__algorithm/ranges_move.h

 //===----------------------------------------------------------------------===//
 //
 // 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___ALGORITHM_RANGES_MOVE_H
 #define _LIBCPP___ALGORITHM_RANGES_MOVE_H
 
 #include <__algorithm/in_out_result.h>
 #include <__algorithm/iterator_operations.h>
 #include <__algorithm/move.h>
 #include <__config>
 #include <__iterator/concepts.h>
-#include <__iterator/iter_move.h>
 #include <__ranges/access.h>
 #include <__ranges/concepts.h>
 #include <__ranges/dangling.h>
 #include <__utility/move.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif

libcxx/include/__algorithm/ranges_move_backward.h

 //===----------------------------------------------------------------------===//
 //
 // 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___ALGORITHM_RANGES_MOVE_BACKWARD_H
 #define _LIBCPP___ALGORITHM_RANGES_MOVE_BACKWARD_H
 
 #include <__algorithm/in_out_result.h>
-#include <__algorithm/ranges_move.h>
+#include <__algorithm/iterator_operations.h>
+#include <__algorithm/move_backward.h>
 #include <__config>
 #include <__iterator/concepts.h>
 #include <__iterator/iter_move.h>
 #include <__iterator/next.h>
-#include <__iterator/reverse_iterator.h>
 #include <__ranges/access.h>
 #include <__ranges/concepts.h>
 #include <__ranges/dangling.h>
 #include <__utility/move.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 #if _LIBCPP_STD_VER > 17
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 namespace ranges {
 
 template <class _InIter, class _OutIter>
 using move_backward_result = in_out_result<_InIter, _OutIter>;
 
 namespace __move_backward {
 struct __fn {
 
   template <class _InIter, class _Sent, class _OutIter>
   _LIBCPP_HIDE_FROM_ABI constexpr static
   move_backward_result<_InIter, _OutIter> __move_backward_impl(_InIter __first, _Sent __last, _OutIter __result) {
-    auto __last_iter = ranges::next(__first, std::move(__last));
-    auto __ret = ranges::move(std::make_reverse_iterator(__last_iter),
-                              std::make_reverse_iterator(__first),
-                              std::make_reverse_iterator(__result));
-    return {std::move(__last_iter), std::move(__ret.out.base())};
+    auto __ret = std::__move_backward<_RangeAlgPolicy>(std::move(__first), std::move(__last), std::move(__result));
+    return {std::move(__ret.first), std::move(__ret.second)};
   }
 
   template <bidirectional_iterator _InIter, sentinel_for<_InIter> _Sent, bidirectional_iterator _OutIter>
     requires indirectly_movable<_InIter, _OutIter>
   _LIBCPP_HIDE_FROM_ABI constexpr
   move_backward_result<_InIter, _OutIter> operator()(_InIter __first, _Sent __last, _OutIter __result) const {
     return __move_backward_impl(std::move(__first), std::move(__last), std::move(__result));
   }

libcxx/include/__algorithm/ranges_set_difference.h

 //===----------------------------------------------------------------------===//
 //
 // 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___ALGORITHM_RANGES_SET_DIFFERENCE_H
 #define _LIBCPP___ALGORITHM_RANGES_SET_DIFFERENCE_H
 
 #include <__algorithm/in_out_result.h>
+#include <__algorithm/iterator_operations.h>
 #include <__algorithm/make_projected.h>
 #include <__algorithm/set_difference.h>
 #include <__config>
 #include <__functional/identity.h>
 #include <__functional/invoke.h>
 #include <__functional/ranges_operations.h>
 #include <__iterator/concepts.h>
 #include <__iterator/mergeable.h>
_LIBCPP_HIDE_FROM_ABI constexpr set_difference_result<_InIter1, _OutIter> operator()(
       _InIter1 __first1,
       _Sent1 __last1,
       _InIter2 __first2,
       _Sent2 __last2,
       _OutIter __result,
       _Comp __comp   = {},
       _Proj1 __proj1 = {},
       _Proj2 __proj2 = {}) const {
-    auto __ret = std::__set_difference(
+    auto __ret = std::__set_difference<_RangeAlgPolicy>(
         __first1, __last1, __first2, __last2, __result, ranges::__make_projected_comp(__comp, __proj1, __proj2));
     return {std::move(__ret.first), std::move(__ret.second)};
   }
 
   template <
       input_range _Range1,
       input_range _Range2,
       weakly_incrementable _OutIter,
       class _Comp  = less,
       class _Proj1 = identity,
       class _Proj2 = identity>
     requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _OutIter, _Comp, _Proj1, _Proj2>
   _LIBCPP_HIDE_FROM_ABI constexpr set_difference_result<borrowed_iterator_t<_Range1>, _OutIter>
     operator()(
         _Range1&& __range1,
         _Range2&& __range2,
         _OutIter __result,
         _Comp __comp   = {},
         _Proj1 __proj1 = {},
         _Proj2 __proj2 = {}) const {
-    auto __ret = std::__set_difference(
+    auto __ret = std::__set_difference<_RangeAlgPolicy>(
         ranges::begin(__range1),
         ranges::end(__range1),
         ranges::begin(__range2),
         ranges::end(__range2),
         __result,
         ranges::__make_projected_comp(__comp, __proj1, __proj2));
     return {std::move(__ret.first), std::move(__ret.second)};
   }

libcxx/include/__algorithm/ranges_set_symmetric_difference.h

 //===----------------------------------------------------------------------===//
 //
 // 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___ALGORITHM_RANGES_SET_SYMMETRIC_DIFFERENCE_H
 #define _LIBCPP___ALGORITHM_RANGES_SET_SYMMETRIC_DIFFERENCE_H
 
 #include <__algorithm/in_in_out_result.h>
+#include <__algorithm/iterator_operations.h>
 #include <__algorithm/make_projected.h>
 #include <__algorithm/set_symmetric_difference.h>
 #include <__config>
 #include <__functional/identity.h>
 #include <__functional/invoke.h>
 #include <__functional/ranges_operations.h>
 #include <__iterator/concepts.h>
 #include <__iterator/mergeable.h>
_LIBCPP_HIDE_FROM_ABI constexpr set_symmetric_difference_result<_InIter1, _InIter2, _OutIter> operator()(
       _InIter1 __first1,
       _Sent1 __last1,
       _InIter2 __first2,
       _Sent2 __last2,
       _OutIter __result,
       _Comp __comp   = {},
       _Proj1 __proj1 = {},
       _Proj2 __proj2 = {}) const {
-    auto __ret = std::__set_symmetric_difference(
+    auto __ret = std::__set_symmetric_difference<_RangeAlgPolicy>(
         std::move(__first1),
         std::move(__last1),
         std::move(__first2),
         std::move(__last2),
         std::move(__result),
         ranges::__make_projected_comp(__comp, __proj1, __proj2));
     return {std::move(__ret.__in1_), std::move(__ret.__in2_), std::move(__ret.__out_)};
   }
_LIBCPP_HIDE_FROM_ABI constexpr set_symmetric_difference_result<borrowed_iterator_t<_Range1>,
                                                                   _OutIter>
     operator()(
         _Range1&& __range1,
         _Range2&& __range2,
         _OutIter __result,
         _Comp __comp   = {},
         _Proj1 __proj1 = {},
         _Proj2 __proj2 = {}) const {
-    auto __ret = std::__set_symmetric_difference(
+    auto __ret = std::__set_symmetric_difference<_RangeAlgPolicy>(
         ranges::begin(__range1),
         ranges::end(__range1),
         ranges::begin(__range2),
         ranges::end(__range2),
         std::move(__result),
         ranges::__make_projected_comp(__comp, __proj1, __proj2));
     return {std::move(__ret.__in1_), std::move(__ret.__in2_), std::move(__ret.__out_)};
   }

libcxx/include/__algorithm/ranges_set_union.h

 //===----------------------------------------------------------------------===//
 //
 // 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___ALGORITHM_RANGES_SET_UNION_H
 #define _LIBCPP___ALGORITHM_RANGES_SET_UNION_H
 
 #include <__algorithm/in_in_out_result.h>
+#include <__algorithm/iterator_operations.h>
 #include <__algorithm/make_projected.h>
 #include <__algorithm/set_union.h>
 #include <__config>
 #include <__functional/identity.h>
 #include <__functional/invoke.h>
 #include <__functional/ranges_operations.h>
 #include <__iterator/concepts.h>
 #include <__iterator/iterator_traits.h>
_LIBCPP_HIDE_FROM_ABI constexpr set_union_result<_InIter1, _InIter2, _OutIter> operator()(
       _InIter1 __first1,
       _Sent1 __last1,
       _InIter2 __first2,
       _Sent2 __last2,
       _OutIter __result,
       _Comp __comp   = {},
       _Proj1 __proj1 = {},
       _Proj2 __proj2 = {}) const {
-    auto __ret = std::__set_union(
+    auto __ret = std::__set_union<_RangeAlgPolicy>(
         std::move(__first1),
         std::move(__last1),
         std::move(__first2),
         std::move(__last2),
         std::move(__result),
         ranges::__make_projected_comp(__comp, __proj1, __proj2));
     return {std::move(__ret.__in1_), std::move(__ret.__in2_), std::move(__ret.__out_)};
   }
_LIBCPP_HIDE_FROM_ABI constexpr set_union_result<borrowed_iterator_t<_Range1>,
                                                    _OutIter>
     operator()(
         _Range1&& __range1,
         _Range2&& __range2,
         _OutIter __result,
         _Comp __comp   = {},
         _Proj1 __proj1 = {},
         _Proj2 __proj2 = {}) const {
-    auto __ret = std::__set_union(
+    auto __ret = std::__set_union<_RangeAlgPolicy>(
         ranges::begin(__range1),
         ranges::end(__range1),
         ranges::begin(__range2),
         ranges::end(__range2),
         std::move(__result),
         ranges::__make_projected_comp(__comp, __proj1, __proj2));
     return {std::move(__ret.__in1_), std::move(__ret.__in2_), std::move(__ret.__out_)};
   }

libcxx/include/__algorithm/rotate.h

 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 _BidirectionalIterator
 __rotate_right(_BidirectionalIterator __first, _BidirectionalIterator __last)
 {
     typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
     using _Ops = _IterOps<_AlgPolicy>;
 
     _BidirectionalIterator __lm1 = _Ops::prev(__last);
     value_type __tmp = _Ops::__iter_move(__lm1);
-    _BidirectionalIterator __fp1 = std::__move_backward<_AlgPolicy>(__first, __lm1, std::move(__last));
+    _BidirectionalIterator __fp1 = std::__move_backward<_AlgPolicy>(__first, __lm1, std::move(__last)).second;
     *__first = _VSTD::move(__tmp);
     return __fp1;
 }
 
 template <class _AlgPolicy, class _ForwardIterator>
 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17 _ForwardIterator
 __rotate_forward(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last)
 {

libcxx/include/__algorithm/set_difference.h

 //===----------------------------------------------------------------------===//
 //
 // 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___ALGORITHM_SET_DIFFERENCE_H
 #define _LIBCPP___ALGORITHM_SET_DIFFERENCE_H
 
 #include <__algorithm/comp.h>
 #include <__algorithm/comp_ref_type.h>
 #include <__algorithm/copy.h>
+#include <__algorithm/iterator_operations.h>
 #include <__config>
 #include <__functional/identity.h>
 #include <__functional/invoke.h>
 #include <__iterator/iterator_traits.h>
 #include <__utility/move.h>
 #include <__utility/pair.h>
 #include <type_traits>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
-template < class _Comp, class _InIter1, class _Sent1, class _InIter2, class _Sent2, class _OutIter>
+template <class _AlgPolicy, class _Comp, class _InIter1, class _Sent1, class _InIter2, class _Sent2, class _OutIter>
 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 pair<__remove_cvref_t<_InIter1>, __remove_cvref_t<_OutIter> >
 __set_difference(
     _InIter1&& __first1, _Sent1&& __last1, _InIter2&& __first2, _Sent2&& __last2, _OutIter&& __result, _Comp&& __comp) {
   while (__first1 != __last1 && __first2 != __last2) {
     if (__comp(*__first1, *__first2)) {
       *__result = *__first1;
       ++__first1;
       ++__result;
     } else if (__comp(*__first2, *__first1)) {
       ++__first2;
     } else {
       ++__first1;
       ++__first2;
     }
   }
-  return std::__copy(std::move(__first1), std::move(__last1), std::move(__result));
+  return std::__copy<_AlgPolicy>(std::move(__first1), std::move(__last1), std::move(__result));
 }
 
 template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _OutputIterator set_difference(
     _InputIterator1 __first1,
     _InputIterator1 __last1,
     _InputIterator2 __first2,
     _InputIterator2 __last2,
     _OutputIterator __result,
     _Compare __comp) {
-  return std::__set_difference<__comp_ref_type<_Compare> >(__first1, __last1, __first2, __last2, __result, __comp)
+  return std::__set_difference<_ClassicAlgPolicy, __comp_ref_type<_Compare> >(
+      __first1, __last1, __first2, __last2, __result, __comp)
       .second;
 }
 
 template <class _InputIterator1, class _InputIterator2, class _OutputIterator>
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _OutputIterator set_difference(
     _InputIterator1 __first1,
     _InputIterator1 __last1,
     _InputIterator2 __first2,
     _InputIterator2 __last2,
     _OutputIterator __result) {
-  return std::__set_difference(
+  return std::__set_difference<_ClassicAlgPolicy>(
       __first1,
       __last1,
       __first2,
       __last2,
       __result,
       __less<typename iterator_traits<_InputIterator1>::value_type,
              typename iterator_traits<_InputIterator2>::value_type>()).second;
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_SET_DIFFERENCE_H

libcxx/include/__algorithm/set_symmetric_difference.h

 //===----------------------------------------------------------------------===//
 //
 // 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___ALGORITHM_SET_SYMMETRIC_DIFFERENCE_H
 #define _LIBCPP___ALGORITHM_SET_SYMMETRIC_DIFFERENCE_H
 
 #include <__algorithm/comp.h>
 #include <__algorithm/comp_ref_type.h>
 #include <__algorithm/copy.h>
+#include <__algorithm/iterator_operations.h>
 #include <__config>
 #include <__iterator/iterator_traits.h>
 #include <__utility/move.h>
 #include <__utility/pair.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 template <class _InIter1, class _InIter2, class _OutIter>
 struct __set_symmetric_difference_result {
   _InIter1 __in1_;
   _InIter2 __in2_;
   _OutIter __out_;
 
   // need a constructor as C++03 aggregate init is hard
   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
   __set_symmetric_difference_result(_InIter1&& __in_iter1, _InIter2&& __in_iter2, _OutIter&& __out_iter)
       : __in1_(std::move(__in_iter1)), __in2_(std::move(__in_iter2)), __out_(std::move(__out_iter)) {}
 };
 
-template <class _Compare, class _InIter1, class _Sent1, class _InIter2, class _Sent2, class _OutIter>
+template <class _AlgPolicy, class _Compare, class _InIter1, class _Sent1, class _InIter2, class _Sent2, class _OutIter>
 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __set_symmetric_difference_result<_InIter1, _InIter2, _OutIter>
 __set_symmetric_difference(
     _InIter1 __first1, _Sent1 __last1, _InIter2 __first2, _Sent2 __last2, _OutIter __result, _Compare&& __comp) {
   while (__first1 != __last1) {
     if (__first2 == __last2) {
-      auto __ret1 = std::__copy_impl(std::move(__first1), std::move(__last1), std::move(__result));
+      auto __ret1 = std::__copy<_AlgPolicy>(std::move(__first1), std::move(__last1), std::move(__result));
       return __set_symmetric_difference_result<_InIter1, _InIter2, _OutIter>(
           std::move(__ret1.first), std::move(__first2), std::move((__ret1.second)));
     }
     if (__comp(*__first1, *__first2)) {
       *__result = *__first1;
       ++__result;
       ++__first1;
     } else {
       if (__comp(*__first2, *__first1)) {
         *__result = *__first2;
         ++__result;
       } else {
         ++__first1;
       }
       ++__first2;
     }
   }
-  auto __ret2 = std::__copy_impl(std::move(__first2), std::move(__last2), std::move(__result));
+  auto __ret2 = std::__copy<_AlgPolicy>(std::move(__first2), std::move(__last2), std::move(__result));
   return __set_symmetric_difference_result<_InIter1, _InIter2, _OutIter>(
       std::move(__first1), std::move(__ret2.first), std::move((__ret2.second)));
 }
 
 template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>
 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _OutputIterator set_symmetric_difference(
     _InputIterator1 __first1,
     _InputIterator1 __last1,
     _InputIterator2 __first2,
     _InputIterator2 __last2,
     _OutputIterator __result,
     _Compare __comp) {
-  return std::__set_symmetric_difference<__comp_ref_type<_Compare> >(
+  return std::__set_symmetric_difference<_ClassicAlgPolicy, __comp_ref_type<_Compare> >(
              std::move(__first1),
              std::move(__last1),
              std::move(__first2),
              std::move(__last2),
              std::move(__result),
              __comp)
       .__out_;
 }

libcxx/include/__algorithm/set_union.h

 //===----------------------------------------------------------------------===//
 //
 // 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___ALGORITHM_SET_UNION_H
 #define _LIBCPP___ALGORITHM_SET_UNION_H
 
 #include <__algorithm/comp.h>
 #include <__algorithm/comp_ref_type.h>
 #include <__algorithm/copy.h>
+#include <__algorithm/iterator_operations.h>
 #include <__config>
 #include <__iterator/iterator_traits.h>
 #include <__utility/move.h>
 #include <__utility/pair.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 template <class _InIter1, class _InIter2, class _OutIter>
 struct __set_union_result {
   _InIter1 __in1_;
   _InIter2 __in2_;
   _OutIter __out_;
 
   // need a constructor as C++03 aggregate init is hard
   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
   __set_union_result(_InIter1&& __in_iter1, _InIter2&& __in_iter2, _OutIter&& __out_iter)
       : __in1_(std::move(__in_iter1)), __in2_(std::move(__in_iter2)), __out_(std::move(__out_iter)) {}
 };
 
-template <class _Compare, class _InIter1, class _Sent1, class _InIter2, class _Sent2, class _OutIter>
+template <class _AlgPolicy, class _Compare, class _InIter1, class _Sent1, class _InIter2, class _Sent2, class _OutIter>
 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __set_union_result<_InIter1, _InIter2, _OutIter> __set_union(
     _InIter1 __first1, _Sent1 __last1, _InIter2 __first2, _Sent2 __last2, _OutIter __result, _Compare&& __comp) {
   for (; __first1 != __last1; ++__result) {
     if (__first2 == __last2) {
-      auto __ret1 = std::__copy_impl(std::move(__first1), std::move(__last1), std::move(__result));
+      auto __ret1 = std::__copy<_AlgPolicy>(std::move(__first1), std::move(__last1), std::move(__result));
       return __set_union_result<_InIter1, _InIter2, _OutIter>(
           std::move(__ret1.first), std::move(__first2), std::move((__ret1.second)));
     }
     if (__comp(*__first2, *__first1)) {
       *__result = *__first2;
       ++__first2;
     } else {
       if (!__comp(*__first1, *__first2)) {
         ++__first2;
       }
       *__result = *__first1;
       ++__first1;
     }
   }
-  auto __ret2 = std::__copy_impl(std::move(__first2), std::move(__last2), std::move(__result));
+  auto __ret2 = std::__copy<_AlgPolicy>(std::move(__first2), std::move(__last2), std::move(__result));
   return __set_union_result<_InIter1, _InIter2, _OutIter>(
       std::move(__first1), std::move(__ret2.first), std::move((__ret2.second)));
 }
 
 template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>
 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _OutputIterator set_union(
     _InputIterator1 __first1,
     _InputIterator1 __last1,
     _InputIterator2 __first2,
     _InputIterator2 __last2,
     _OutputIterator __result,
     _Compare __comp) {
-  return std::__set_union<__comp_ref_type<_Compare> >(
+  return std::__set_union<_ClassicAlgPolicy, __comp_ref_type<_Compare> >(
              std::move(__first1),
              std::move(__last1),
              std::move(__first2),
              std::move(__last2),
              std::move(__result),
              __comp)
       .__out_;
 }

libcxx/include/__iterator/reverse_iterator.h

void iter_swap(const reverse_iterator& __x, const reverse_iterator<_Iter2>& __y)
           noexcept(ranges::iter_swap(--declval<_Iter&>(), --declval<_Iter2&>()))) {
       auto __xtmp = __x.base();
       auto __ytmp = __y.base();
       ranges::iter_swap(--__xtmp, --__ytmp);
     }
 #endif // _LIBCPP_STD_VER > 17
 };
 
-template <class _Iter>
-struct __is_reverse_iterator : false_type {};
-
-template <class _Iter>
-struct __is_reverse_iterator<reverse_iterator<_Iter> > : true_type {};
-
 template <class _Iter1, class _Iter2>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX17
 bool
 operator==(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y)
 #if _LIBCPP_STD_VER > 17
     requires requires {
       { __x.base() == __y.base() } -> convertible_to<bool>;
     }
public:
   }
 
   _LIBCPP_HIDE_FROM_ABI friend constexpr bool
   operator>=(const __unconstrained_reverse_iterator& __lhs, const __unconstrained_reverse_iterator& __rhs) {
     return __lhs.base() <= __rhs.base();
   }
 };
 
-template <class _Iter>
-struct __is_reverse_iterator<__unconstrained_reverse_iterator<_Iter>> : true_type {};
-
 #endif // _LIBCPP_STD_VER <= 17
 
 template <template <class> class _RevIter1, template <class> class _RevIter2, class _Iter>
 struct __unwrap_reverse_iter_impl {
   using _UnwrappedIter = decltype(__unwrap_iter_impl<_Iter>::__unwrap(std::declval<_Iter>()));
   using _ReverseWrapper = _RevIter1<_RevIter2<_Iter> >;
 
   static _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR _ReverseWrapper

libcxx/include/__type_traits/are_always_bitcastable.h

+//===----------------------------------------------------------------------===//
+//
+// 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___TYPE_TRAITS_ARE_ALWAYS_BITCASTABLE_H
+#define _LIBCPP___TYPE_TRAITS_ARE_ALWAYS_BITCASTABLE_H
+
+#include <__config>
+#include <__type_traits/integral_constant.h>
+#include <__type_traits/is_integral.h>
+#include <__type_traits/is_same.h>
+#include <__type_traits/is_trivially_copyable.h>
+#include <__type_traits/remove_cv.h>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#  pragma GCC system_header
+#endif
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+// Checks whether `_Tp` and `_Up` are always bit-castable to one another. This means that all possible values of `_Tp`
+// are representable by `_Up` and vice versa, and built-in assignment between objects of types `_Tp` and `_Up` produces
+// the same value as using `bit_cast` to cast between the types.
+//
+// Note that cv-qualifiers are ignored for the given types.
+template <class _MaybeQualifiedT, class _MaybeQualifiedU,
+          class _Tp = __remove_cv_t<_MaybeQualifiedT>,
+          class _Up = __remove_cv_t<_MaybeQualifiedU> >
+struct _LIBCPP_TEMPLATE_VIS __are_always_bitcastable : public integral_constant<bool,
+    // First, the simple case -- `T` and `U` are the same type that is trivially copyable.
+    (is_same<_Tp, _Up>::value && is_trivially_copyable<_Tp>::value) ||
+
+    // Beyond the simple case, we say that one type is bit-castable to another if:
+    // - (1) Every possible value of `T` has a corresponding value in the `U` type and vice versa;
+    // - (2) Assignment between objects of types `T` and `U` is valid and trivial;
+    // - (3) When the corresponding values are not the same value (as, for example, between an unsigned and a signed
+    //   integer, where a large positive value of the unsigned integer corresponds to a negative value in the signed
+    //   integer type), the value of `U` that results from a bitwise copy of `T` is the same what would be produced by
+    //   the built-in assignment.
+    //
+    // To summarize, two types are "always bit-castable" if `u = t` is a valid trivial expression that produces the same
+    // value as `bit_cast<U>(t)` for any possible value of `t`, and conversely for `t = u` (assuming `t` and `u` are
+    // objects of types `T` and `U`, respectively).
+    //
+    // In practice, that means:
+    // - all integral types (except `bool`, see below) -- that is, character types and `int` types, both signed and
+    //   unsigned...
+    // - ...that have the same size.
+    //
+    // Other trivially-copyable types can't be validly bit-cast outside of their own type:
+    // - floating-point types normally have different sizes and thus aren't bit-castable between each other (fails #1);
+    // - integral types and floating-point types use different representations, so for example bit-casting an integral
+    //   `1` to `float` results in a very small less-than-one value, unlike built-in assignment that produces `1.0`
+    //   (fails #3);
+    // - booleans normally use only a single bit of their possible value range; bit-casting an integer to a boolean will
+    //   result in a boolean object with an incorrect representation, and such an object may compare both `true` and
+    //   `false` in different contexts (fails #3);
+    // - pointers between different types are not assignable to each other (fails #2);
+    // - enumeration types may have different ranges of possible values (fails #1 and #2);
+    // - structs and unions of different types can never be trivially assigned to each other, even if they have the
+    //   exact same representation -- any conversion between the two would have to be user-defined and thus non-trivial
+    //   (fails #2);
+    // - arrays can't be assigned to each other using built-in assignment (fails #2);
+    // - there is no need to consider `nullptr_t` for practical purposes.
+    (
+      sizeof(_Tp) == sizeof(_Up) &&
+      is_integral<_Tp>::value &&
+      is_integral<_Up>::value &&
+      !is_same<_Tp, bool>::value &&
+      !is_same<_Up, bool>::value
+    )
+> {};
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP___TYPE_TRAITS_ARE_ALWAYS_BITCASTABLE_H

libcxx/include/algorithm

 
 */
 
 #include <__assert> // all public C++ headers provide the assertion handler
 #include <__bits>
 #include <__config>
 #include <__debug>
 #include <cstddef>
-#include <cstring>
 #include <type_traits>
 #include <version>
 
 #include <__algorithm/adjacent_find.h>
 #include <__algorithm/all_of.h>
 #include <__algorithm/any_of.h>
 #include <__algorithm/binary_search.h>
 #include <__algorithm/clamp.h>

 
 #if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 17
 #  include <chrono>
 #endif
 
 #if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 20
 #  include <atomic>
 #  include <concepts>
+#  include <cstring>
 #  include <iterator>
 #  include <memory>
 #  include <stdexcept>
 #  include <utility>
 #endif
 
 #endif // _LIBCPP_ALGORITHM

libcxx/include/module.modulemap.in

module __algorithm {
       module any_of                          { private header "__algorithm/any_of.h" }
       module binary_search                   { private header "__algorithm/binary_search.h" }
       module clamp                           { private header "__algorithm/clamp.h" }
       module comp                            { private header "__algorithm/comp.h" }
       module comp_ref_type                   { private header "__algorithm/comp_ref_type.h" }
       module copy                            { private header "__algorithm/copy.h" }
       module copy_backward                   { private header "__algorithm/copy_backward.h" }
       module copy_if                         { private header "__algorithm/copy_if.h" }
+      module copy_move_common                { private header "__algorithm/copy_move_common.h" }
       module copy_n                          { private header "__algorithm/copy_n.h" }
       module count                           { private header "__algorithm/count.h" }
       module count_if                        { private header "__algorithm/count_if.h" }
       module equal                           { private header "__algorithm/equal.h" }
       module equal_range                     { private header "__algorithm/equal_range.h" }
       module fill                            { private header "__algorithm/fill.h" }
       module fill_n                          { private header "__algorithm/fill_n.h" }
       module find                            { private header "__algorithm/find.h" }
module type_traits {
     module add_lvalue_reference                { private header "__type_traits/add_lvalue_reference.h" }
     module add_pointer                         { private header "__type_traits/add_pointer.h" }
     module add_rvalue_reference                { private header "__type_traits/add_rvalue_reference.h" }
     module add_volatile                        { private header "__type_traits/add_volatile.h" }
     module aligned_storage                     { private header "__type_traits/aligned_storage.h" }
     module aligned_union                       { private header "__type_traits/aligned_union.h" }
     module alignment_of                        { private header "__type_traits/alignment_of.h" }
     module apply_cv                            { private header "__type_traits/apply_cv.h" }
+    module are_always_bitcastable              { private header "__type_traits/are_always_bitcastable.h" }
     module can_extract_key                     { private header "__type_traits/can_extract_key.h" }
     module common_reference                    { private header "__type_traits/common_reference.h" }
     module common_type                         { private header "__type_traits/common_type.h" }
     module conditional                         { private header "__type_traits/conditional.h" }
     module conjunction                         { private header "__type_traits/conjunction.h" }
     module copy_cv                             { private header "__type_traits/copy_cv.h" }
     module copy_cvref                          { private header "__type_traits/copy_cvref.h" }
     module decay                               { private header "__type_traits/decay.h" }

libcxx/include/valarray

 
 _LIBCPP_END_NAMESPACE_STD
 
 _LIBCPP_POP_MACROS
 
 #if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 20
 #  include <algorithm>
 #  include <concepts>
+#  include <cstring>
 #  include <functional>
 #endif
 
 #endif // _LIBCPP_VALARRAY

libcxx/test/libcxx/algorithms/alg.modifying.operations/copy.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
-//
-//===----------------------------------------------------------------------===//
-
-// UNSUPPORTED: c++03, c++11, c++14, c++17
-
-// When the debug mode is enabled, we don't unwrap iterators in std::copy
-// so we don't get this optimization.
-// UNSUPPORTED: libcpp-has-debug-mode
-
-// <algorithm>
-
-// This test checks that std::copy forwards to memmove when appropriate.
-
-#include <algorithm>
-#include <cassert>
-#include <iterator>
-#include <ranges>
-#include <type_traits>
-
-struct S {
-  int i;
-  constexpr S(int i_) : i(i_) {}
-  S(const S&) = default;
-  S(S&&) = delete;
-  constexpr S& operator=(const S&) = default;
-  S& operator=(S&&) = delete;
-  constexpr bool operator==(const S&) const = default;
-};
-
-static_assert(std::is_trivially_copyable_v<S>);
-
-template <class T>
-struct NotIncrementableIt {
-  T* i;
-  using iterator_category = std::contiguous_iterator_tag;
-  using iterator_concept = std::contiguous_iterator_tag;
-  using value_type = T;
-  using difference_type = ptrdiff_t;
-  using pointer = T*;
-  using reference = T&;
-
-  constexpr NotIncrementableIt() = default;
-  constexpr NotIncrementableIt(T* i_) : i(i_) {}
-
-  friend constexpr bool operator==(const NotIncrementableIt& lhs, const NotIncrementableIt& rhs) {
-    return lhs.i == rhs.i;
-  }
-
-  constexpr T& operator*() { return *i; }
-  constexpr T& operator*() const { return *i; }
-  constexpr T* operator->() { return i; }
-  constexpr T* operator->() const { return i; }
-
-  constexpr NotIncrementableIt& operator++() {
-    assert(false);
-    return *this;
-  }
-
-  constexpr NotIncrementableIt& operator++(int) {
-    assert(false);
-    return *this;
-  }
-
-  constexpr NotIncrementableIt& operator--() {
-    assert(false);
-    return *this;
-  }
-
-  friend constexpr NotIncrementableIt operator+(const NotIncrementableIt& it, difference_type size) { return it.i + size; }
-  friend constexpr difference_type operator-(const NotIncrementableIt& x, const NotIncrementableIt& y) { return x.i - y.i; }
-  friend constexpr NotIncrementableIt operator-(const NotIncrementableIt& x, difference_type size) { return NotIncrementableIt(x.i - size); }
-};
-
-static_assert(std::__is_cpp17_contiguous_iterator<NotIncrementableIt<S>>::value);
-
-template <size_t N, class Iter, std::enable_if_t<N == 0>* = nullptr>
-constexpr auto wrap_n_times(Iter i) {
-  return i;
-}
-
-template <size_t N, class Iter, std::enable_if_t<N != 0>* = nullptr>
-constexpr auto wrap_n_times(Iter i) {
-  return std::make_reverse_iterator(wrap_n_times<N - 1>(i));
-}
-
-static_assert(std::is_same_v<decltype(wrap_n_times<2>(std::declval<int*>())),
-                             std::reverse_iterator<std::reverse_iterator<int*>>>);
-
-template <size_t InCount, size_t OutCount, class Iter>
-constexpr void test_normal() {
-  {
-    S a[] = {1, 2, 3, 4};
-    S b[] = {0, 0, 0, 0};
-    std::copy(wrap_n_times<InCount>(Iter(a)), wrap_n_times<InCount>(Iter(a + 4)), wrap_n_times<OutCount>(Iter(b)));
-    assert(std::equal(a, a + 4, b));
-  }
-  {
-    S a[] = {1, 2, 3, 4};
-    S b[] = {0, 0, 0, 0};
-    std::ranges::copy(wrap_n_times<InCount>(Iter(a)),
-                      wrap_n_times<InCount>(Iter(a + 4)),
-                      wrap_n_times<OutCount>(Iter(b)));
-    assert(std::equal(a, a + 4, b));
-  }
-  {
-    S a[] = {1, 2, 3, 4};
-    S b[] = {0, 0, 0, 0};
-    auto range = std::ranges::subrange(wrap_n_times<InCount>(Iter(a)), wrap_n_times<InCount>(Iter(a + 4)));
-    std::ranges::copy(range, Iter(b));
-    assert(std::equal(a, a + 4, b));
-  }
-}
-
-template <size_t InCount, size_t OutCount, class Iter>
-constexpr void test_reverse() {
-  {
-    S a[] = {1, 2, 3, 4};
-    S b[] = {0, 0, 0, 0};
-    std::copy(std::make_reverse_iterator(wrap_n_times<InCount>(Iter(a + 4))),
-              std::make_reverse_iterator(wrap_n_times<InCount>(Iter(a))),
-              std::make_reverse_iterator(wrap_n_times<OutCount>(Iter(b + 4))));
-    assert(std::equal(a, a + 4, b));
-  }
-  {
-    S a[] = {1, 2, 3, 4};
-    S b[] = {0, 0, 0, 0};
-    std::ranges::copy(std::make_reverse_iterator(wrap_n_times<InCount>(Iter(a + 4))),
-                      std::make_reverse_iterator(wrap_n_times<InCount>(Iter(a))),
-                      std::make_reverse_iterator(wrap_n_times<OutCount>(Iter(b + 4))));
-    assert(std::equal(a, a + 4, b));
-  }
-  {
-    S a[] = {1, 2, 3, 4};
-    S b[] = {0, 0, 0, 0};
-    auto range = std::ranges::subrange(wrap_n_times<InCount>(std::make_reverse_iterator(Iter(a + 4))),
-                                       wrap_n_times<InCount>(std::make_reverse_iterator(Iter(a))));
-    std::ranges::copy(range, std::make_reverse_iterator(wrap_n_times<OutCount>(Iter(b + 4))));
-    assert(std::equal(a, a + 4, b));
-  }
-}
-
-template <size_t InCount, size_t OutCount>
-constexpr void test_normal_reverse() {
-  test_normal<InCount, OutCount, S*>();
-  test_normal<InCount, OutCount, NotIncrementableIt<S>>();
-  test_reverse<InCount, OutCount, S*>();
-  test_reverse<InCount, OutCount, NotIncrementableIt<S>>();
-}
-
-template <size_t InCount>
-constexpr void test_out_count() {
-  test_normal_reverse<InCount, 0>();
-  test_normal_reverse<InCount, 2>();
-  test_normal_reverse<InCount, 4>();
-  test_normal_reverse<InCount, 6>();
-  test_normal_reverse<InCount, 8>();
-}
-
-constexpr bool test() {
-  test_out_count<0>();
-  test_out_count<2>();
-  test_out_count<4>();
-  test_out_count<6>();
-  test_out_count<8>();
-
-  return true;
-}
-
-int main(int, char**) {
-  test();
-  static_assert(test());
-
-  return 0;
-}

libcxx/test/libcxx/algorithms/alg.modifying.operations/copy_move_nontrivial.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
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03, c++11, c++14, c++17
+
+// <algorithm>
+
+#include <cassert>
+#include <cstddef>
+
+// These tests check that `std::copy` and `std::move` (including their variations like `copy_n`) don't forward to
+// `std::memmove` when doing so would be observable.
+
+// This template is a better match than the actual `builtin_memmove` (it can match the pointer type exactly, without an
+// implicit conversion to `void*`), so it should hijack the call inside `std::copy` and similar algorithms if it's made.
+template <class Dst, class Src>
+constexpr void* __builtin_memmove(Dst*, Src*, size_t) {
+  assert(false);
+  return nullptr;
+}
+
+#include <algorithm>
+#include <cassert>
+#include <cstdint>
+#include <iterator>
+#include <ranges>
+#include <type_traits>
+
+#include "test_iterators.h"
+#include "test_macros.h"
+
+// S1 and S2 are simple structs that are convertible to each other and have the same bit representation.
+struct S1 {
+  int x;
+
+  constexpr S1() = default;
+  constexpr S1(int set_x) : x(set_x) {}
+
+  friend constexpr bool operator==(const S1& lhs, const S1& rhs) { return lhs.x == rhs.x; }
+};
+
+struct S2 {
+  int x;
+
+  constexpr S2() = default;
+  constexpr S2(int set_x) : x(set_x) {}
+  constexpr S2(S1 from) : x(from.x) {}
+
+  friend constexpr bool operator==(const S1& lhs, const S2& rhs) { return lhs.x == rhs.x; }
+  friend constexpr bool operator==(const S2& lhs, const S2& rhs) { return lhs.x == rhs.x; }
+};
+
+// U1 and U2 are simple unions that are convertible to each other and have the same bit representation.
+union U1 {
+  int x;
+
+  constexpr U1() = default;
+  constexpr U1(int set_x) : x(set_x) {}
+
+  friend constexpr bool operator==(const U1& lhs, const U1& rhs) { return lhs.x == rhs.x; }
+};
+
+union U2 {
+  int x;
+
+  constexpr U2() = default;
+  constexpr U2(int set_x) : x(set_x) {}
+  constexpr U2(U1 from) : x(from.x) {}
+
+  friend constexpr bool operator==(const U1& lhs, const U2& rhs) { return lhs.x == rhs.x; }
+  friend constexpr bool operator==(const U2& lhs, const U2& rhs) { return lhs.x == rhs.x; }
+};
+
+struct NonTrivialMoveAssignment {
+  int i;
+
+  constexpr NonTrivialMoveAssignment() = default;
+  constexpr NonTrivialMoveAssignment(int set_i) : i(set_i) {}
+
+  constexpr NonTrivialMoveAssignment(NonTrivialMoveAssignment&& rhs) = default;
+  constexpr NonTrivialMoveAssignment& operator=(NonTrivialMoveAssignment&& rhs) noexcept {
+    i = rhs.i;
+    return *this;
+  }
+
+  constexpr friend bool operator==(const NonTrivialMoveAssignment&, const NonTrivialMoveAssignment&) = default;
+};
+
+static_assert(!std::is_trivially_move_assignable_v<NonTrivialMoveAssignment>);
+static_assert(!std::is_trivially_assignable<NonTrivialMoveAssignment&, NonTrivialMoveAssignment&>::value);
+
+struct NonTrivialMoveCtr {
+  int i;
+
+  constexpr NonTrivialMoveCtr() = default;
+  constexpr NonTrivialMoveCtr(int set_i) : i(set_i) {}
+
+  constexpr NonTrivialMoveCtr(NonTrivialMoveCtr&& rhs) noexcept : i(rhs.i) {}
+  constexpr NonTrivialMoveCtr& operator=(NonTrivialMoveCtr&& rhs) = default;
+
+  constexpr friend bool operator==(const NonTrivialMoveCtr&, const NonTrivialMoveCtr&) = default;
+};
+
+static_assert(std::is_trivially_move_assignable_v<NonTrivialMoveCtr>);
+static_assert(!std::is_trivially_copyable_v<NonTrivialMoveCtr>);
+
+struct NonTrivialCopyAssignment {
+  int i;
+
+  constexpr NonTrivialCopyAssignment() = default;
+  constexpr NonTrivialCopyAssignment(int set_i) : i(set_i) {}
+
+  constexpr NonTrivialCopyAssignment(const NonTrivialCopyAssignment& rhs) = default;
+  constexpr NonTrivialCopyAssignment& operator=(const NonTrivialCopyAssignment& rhs) {
+    i = rhs.i;
+    return *this;
+  }
+
+  constexpr friend bool operator==(const NonTrivialCopyAssignment&, const NonTrivialCopyAssignment&) = default;
+};
+
+static_assert(!std::is_trivially_copy_assignable_v<NonTrivialCopyAssignment>);
+
+struct NonTrivialCopyCtr {
+  int i;
+
+  constexpr NonTrivialCopyCtr() = default;
+  constexpr NonTrivialCopyCtr(int set_i) : i(set_i) {}
+
+  constexpr NonTrivialCopyCtr(const NonTrivialCopyCtr& rhs) : i(rhs.i) {}
+  constexpr NonTrivialCopyCtr& operator=(const NonTrivialCopyCtr& rhs) = default;
+
+  constexpr friend bool operator==(const NonTrivialCopyCtr&, const NonTrivialCopyCtr&) = default;
+};
+
+static_assert(std::is_trivially_copy_assignable_v<NonTrivialCopyCtr>);
+static_assert(!std::is_trivially_copyable_v<NonTrivialCopyCtr>);
+
+template <class T>
+constexpr T make(int from) {
+  return T(from);
+}
+
+template <typename PtrT, typename T = std::remove_pointer_t<PtrT>>
+static T make_internal_array[5] = {T(), T(), T(), T(), T()};
+
+template <class T>
+requires std::is_pointer_v<T>
+constexpr T make(int i) {
+  if constexpr (!std::same_as<std::remove_pointer_t<T>, void>) {
+    return make_internal_array<T> + i;
+  } else {
+    return make_internal_array<int> + i;
+  }
+}
+
+template <class InIter, template <class> class SentWrapper, class OutIter, class Func>
+constexpr void test_one(Func func) {
+  using From = typename std::iterator_traits<InIter>::value_type;
+  using To = typename std::iterator_traits<OutIter>::value_type;
+
+  {
+    const size_t N = 5;
+
+    From input[N] = {make<From>(0), make<From>(1), make<From>(2), make<From>(3), make<From>(4)};
+    To output[N];
+
+    auto in     = InIter(input);
+    auto in_end = InIter(input + N);
+    auto sent   = SentWrapper<decltype(in_end)>(in_end);
+    auto out    = OutIter(output);
+
+    func(in, sent, out, N);
+    if constexpr (!std::same_as<To, bool>) {
+      assert(std::equal(input, input + N, output));
+    } else {
+      bool expected[N] = {false, true, true, true, true};
+      assert(std::equal(output, output + N, expected));
+    }
+  }
+
+  {
+    const size_t N = 0;
+
+    From input[1]  = {make<From>(1)};
+    To output[1] = {make<To>(2)};
+
+    auto in     = InIter(input);
+    auto in_end = InIter(input + N);
+    auto sent   = SentWrapper<decltype(in_end)>(in_end);
+    auto out    = OutIter(output);
+
+    func(in, sent, out, N);
+    assert(output[0] == make<To>(2));
+  }
+}
+
+template <class InIter, template <class> class SentWrapper, class OutIter>
+constexpr void test_copy() {
+  // Classic.
+  if constexpr (std::same_as<InIter, SentWrapper<InIter>>) {
+    test_one<InIter, SentWrapper, OutIter>([](auto first, auto last, auto out, size_t) {
+      std::copy(first, last, out);
+    });
+    test_one<InIter, SentWrapper, OutIter>([](auto first, auto last, auto out, size_t n) {
+      std::copy_backward(first, last, out + n);
+    });
+    test_one<InIter, SentWrapper, OutIter>([](auto first, auto, auto out, size_t n) {
+      std::copy_n(first, n, out);
+    });
+  }
+
+  // Ranges.
+  test_one<InIter, SentWrapper, OutIter>([](auto first, auto last, auto out, size_t) {
+    std::ranges::copy(first, last, out);
+  });
+  test_one<InIter, SentWrapper, OutIter>([](auto first, auto last, auto out, size_t n) {
+    std::ranges::copy_backward(first, last, out + n);
+  });
+  test_one<InIter, SentWrapper, OutIter>([](auto first, auto, auto out, size_t n) {
+    std::ranges::copy_n(first, n, out);
+  });
+}
+
+template <class InIter, template <class> class SentWrapper, class OutIter>
+constexpr void test_move() {
+  if constexpr (std::same_as<InIter, SentWrapper<InIter>>) {
+    test_one<InIter, SentWrapper, OutIter>([](auto first, auto last, auto out, size_t) {
+      std::move(first, last, out);
+    });
+    test_one<InIter, SentWrapper, OutIter>([](auto first, auto last, auto out, size_t n) {
+      std::move_backward(first, last, out + n);
+    });
+  }
+
+  // Ranges.
+  test_one<InIter, SentWrapper, OutIter>([](auto first, auto last, auto out, size_t) {
+    std::ranges::move(first, last, out);
+  });
+  test_one<InIter, SentWrapper, OutIter>([](auto first, auto last, auto out, size_t n) {
+    std::ranges::move_backward(first, last, out + n);
+  });
+}
+
+template <class From, class To = From>
+constexpr void test_copy_with_type() {
+  using FromIter = contiguous_iterator<From*>;
+  using ToIter = contiguous_iterator<To*>;
+
+  test_copy<FromIter, std::type_identity_t, ToIter>();
+  test_copy<FromIter, sized_sentinel, ToIter>();
+  test_copy<FromIter, std::type_identity_t, To*>();
+  test_copy<From*, std::type_identity_t, To*>();
+  test_copy<From*, std::type_identity_t, ToIter>();
+}
+
+template <class From, class To = From>
+constexpr void test_move_with_type() {
+  using FromIter = contiguous_iterator<From*>;
+  using ToIter = contiguous_iterator<To*>;
+
+  test_move<FromIter, std::type_identity_t, ToIter>();
+  test_move<FromIter, sized_sentinel, ToIter>();
+  test_move<FromIter, std::type_identity_t, To*>();
+  test_move<From*, std::type_identity_t, To*>();
+  test_move<From*, std::type_identity_t, ToIter>();
+}
+
+template <class From, class To>
+constexpr void test_copy_and_move() {
+  test_copy_with_type<From, To>();
+  test_move_with_type<From, To>();
+}
+
+template <class From, class To>
+constexpr void test_both_directions() {
+  test_copy_and_move<From, To>();
+  if (!std::same_as<From, To>) {
+    test_copy_and_move<To, From>();
+  }
+}
+
+constexpr bool test() {
+  test_copy_with_type<NonTrivialCopyAssignment>();
+  test_move_with_type<NonTrivialMoveAssignment>();
+
+  // Copying from a smaller type into a larger type and vice versa.
+  test_both_directions<char, int>();
+  test_both_directions<std::int32_t, std::int64_t>();
+
+  // Copying between types with different representations.
+  test_both_directions<int, float>();
+  test_both_directions<bool, char>();
+
+  // Copying between different structs with the same represenation (there is no way to guarantee the representation is
+  // the same).
+  test_copy_and_move<S1, S2>();
+  // Copying between different unions with the same represenation.
+  test_copy_and_move<U1, U2>();
+
+  // Copying from a regular pointer to a void pointer (these are not considered trivially copyable).
+  test_copy_and_move<int*, void*>();
+  // Copying from a non-const pointer to a const pointer (these are not considered trivially copyable).
+  test_copy_and_move<int*, const int*>();
+
+  // `memmove` does not support volatile pointers.
+  if (!std::is_constant_evaluated()) {
+    test_both_directions<volatile int, int>();
+  }
+
+  return true;
+}
+
+int main(int, char**) {
+  test();
+  static_assert(test());
+
+  return 0;
+}

libcxx/test/libcxx/algorithms/alg.modifying.operations/copy_move_trivial.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
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03, c++11, c++14, c++17
+// When the debug mode is enabled, we don't unwrap iterators in `std::copy` and similar algorithms so we don't get this
+// optimization.
+// UNSUPPORTED: libcpp-has-debug-mode
+// In the modules build, adding another overload of `memmove` doesn't work.
+// UNSUPPORTED: modules-build
+// GCC complains about "ambiguating" `__builtin_memmove`.
+// UNSUPPORTED: gcc
+
+// <algorithm>
+
+// These tests check that `std::copy` and `std::move` (including their variations like `copy_n`) forward to
+// `memmove` when possible.
+
+#include <cstddef>
+
+struct Foo {
+  int i = 0;
+
+  Foo() = default;
+  Foo(int set_i) : i(set_i) {}
+
+  friend bool operator==(const Foo&, const Foo&) = default;
+};
+
+static bool memmove_called = false;
+
+// This template is a better match than the actual `builtin_memmove` (it can match the pointer type exactly, without an
+// implicit conversion to `void*`), so it should hijack the call inside `std::copy` and similar algorithms if it's made.
+template <class Dst, class Src>
+constexpr void* __builtin_memmove(Dst* dst, Src* src, size_t count) {
+  memmove_called = true;
+  return __builtin_memmove(static_cast<void*>(dst), static_cast<const void*>(src), count);
+}
+
+#include <algorithm>
+#include <cassert>
+#include <cstdint>
+#include <iterator>
+#include <ranges>
+#include <type_traits>
+
+#include "test_iterators.h"
+
+static_assert(std::is_trivially_copyable_v<Foo>);
+
+// To test pointers to functions.
+void Func() {}
+using FuncPtr = decltype(&Func);
+
+// To test pointers to members.
+struct S {
+  int mem_obj = 0;
+  void MemFunc() {}
+};
+using MemObjPtr = decltype(&S::mem_obj);
+using MemFuncPtr = decltype(&S::MemFunc);
+
+// To test bitfields.
+struct BitfieldS {
+  unsigned char b1 : 3;
+  unsigned char : 2;
+  unsigned char b2 : 5;
+  friend bool operator==(const BitfieldS&, const BitfieldS&) = default;
+};
+
+// To test non-default alignment.
+struct AlignedS {
+  alignas(64) int x;
+  alignas(8) int y;
+  friend bool operator==(const AlignedS&, const AlignedS&) = default;
+};
+
+template <class T>
+T make(int from) {
+  return T(from);
+}
+
+template <class T>
+requires (std::is_pointer_v<T> && !std::is_function_v<std::remove_pointer_t<T>>)
+T make(int i) {
+  static std::remove_pointer_t<T> arr[8];
+  return arr + i;
+}
+
+template <class T>
+requires std::same_as<T, FuncPtr>
+FuncPtr make(int) {
+  return &Func;
+}
+
+template <class T>
+requires std::same_as<T, MemObjPtr>
+MemObjPtr make(int) {
+  return &S::mem_obj;
+}
+
+template <class T>
+requires std::same_as<T, MemFuncPtr>
+MemFuncPtr make(int) {
+  return &S::MemFunc;
+}
+
+template <class T>
+requires std::same_as<T, BitfieldS>
+BitfieldS make(int x) {
+  BitfieldS result;
+  result.b1 = x;
+  result.b2 = x;
+  return result;
+}
+
+template <class T>
+requires std::same_as<T, AlignedS>
+AlignedS make(int x) {
+  AlignedS result;
+  result.x = x;
+  result.y = x;
+  return result;
+}
+
+template <class InIter, template <class> class SentWrapper, class OutIter, class Func>
+void test_one(Func func) {
+  using From = std::iter_value_t<InIter>;
+  using To = std::iter_value_t<OutIter>;
+
+  // Normal case.
+  {
+    const size_t N = 4;
+
+    From input[N] = {make<From>(1), make<From>(2), make<From>(3), make<From>(4)};
+    To output[N];
+
+    auto in     = InIter(input);
+    auto in_end = InIter(input + N);
+    auto sent   = SentWrapper<decltype(in_end)>(in_end);
+    auto out    = OutIter(output);
+
+    assert(!memmove_called);
+    func(in, sent, out, N);
+    assert(memmove_called);
+    memmove_called = false;
+
+    assert(std::equal(input, input + N, output, [](const From& lhs, const To& rhs) {
+        // Prevents warnings/errors due to mismatched signed-ness.
+        if constexpr (std::convertible_to<From, To>) {
+          return static_cast<To>(lhs) == rhs;
+        } else if constexpr (std::convertible_to<To, From>) {
+          return lhs == static_cast<From>(rhs);
+        }
+    }));
+  }
+
+  // Empty input sequence.
+  {
+    const size_t N = 0;
+
+    From input[1]  = {make<From>(1)};
+    To output[1] = {make<To>(2)};
+
+    auto in     = InIter(input);
+    auto in_end = InIter(input + N);
+    auto sent   = SentWrapper<decltype(in_end)>(in_end);
+    auto out    = OutIter(output);
+
+    assert(!memmove_called);
+    func(in, sent, out, N);
+
+    assert(memmove_called);
+    memmove_called = false;
+    assert(output[0] == make<To>(2));
+  }
+}
+
+template <class InIter, template <class> class SentWrapper, class OutIter>
+void test_copy_and_move() {
+  // Classic.
+  if constexpr (std::same_as<InIter, SentWrapper<InIter>>) {
+    test_one<InIter, SentWrapper, OutIter>([](auto first, auto last, auto out, size_t) {
+      std::copy(first, last, out);
+    });
+    test_one<InIter, SentWrapper, OutIter>([](auto first, auto last, auto out, size_t n) {
+      std::copy_backward(first, last, out + n);
+    });
+    test_one<InIter, SentWrapper, OutIter>([](auto first, auto, auto out, size_t n) {
+      std::copy_n(first, n, out);
+    });
+    test_one<InIter, SentWrapper, OutIter>([](auto first, auto last, auto out, size_t) {
+      std::move(first, last, out);
+    });
+    test_one<InIter, SentWrapper, OutIter>([](auto first, auto last, auto out, size_t n) {
+      std::move_backward(first, last, out + n);
+    });
+  }
+
+  // Ranges.
+  test_one<InIter, SentWrapper, OutIter>([](auto first, auto last, auto out, size_t) {
+    std::ranges::copy(first, last, out);
+  });
+  test_one<InIter, SentWrapper, OutIter>([](auto first, auto last, auto out, size_t n) {
+    std::ranges::copy_backward(first, last, out + n);
+  });
+  test_one<InIter, SentWrapper, OutIter>([](auto first, auto, auto out, size_t n) {
+    std::ranges::copy_n(first, n, out);
+  });
+  test_one<InIter, SentWrapper, OutIter>([](auto first, auto last, auto out, size_t) {
+    std::ranges::move(first, last, out);
+  });
+  test_one<InIter, SentWrapper, OutIter>([](auto first, auto last, auto out, size_t n) {
+    std::ranges::move_backward(first, last, out + n);
+  });
+}
+
+template <class From, class To, template <class> class SentWrapper>
+void test_all_permutations_from_to_sent() {
+  test_copy_and_move<From*, SentWrapper, To*>();
+  test_copy_and_move<contiguous_iterator<From*>, SentWrapper, To*>();
+  test_copy_and_move<From*, SentWrapper, contiguous_iterator<To*>>();
+  test_copy_and_move<contiguous_iterator<From*>, SentWrapper, contiguous_iterator<To*>>();
+
+  if (!std::same_as<From, To>) {
+    test_copy_and_move<To*, SentWrapper, From*>();
+    test_copy_and_move<contiguous_iterator<To*>, SentWrapper, From*>();
+    test_copy_and_move<To*, SentWrapper, contiguous_iterator<From*>>();
+    test_copy_and_move<contiguous_iterator<To*>, SentWrapper, contiguous_iterator<From*>>();
+  }
+}
+
+void test_different_signedness() {
+  auto check = [](auto alg) {
+    // Signed -> unsigned.
+    {
+      constexpr int N = 3;
+      constexpr auto min_value = std::numeric_limits<int>::min();
+
+      int in[N] = {-1, min_value / 2, min_value};
+      unsigned int out[N];
+      unsigned int expected[N] = {
+        static_cast<unsigned int>(in[0]),
+        static_cast<unsigned int>(in[1]),
+        static_cast<unsigned int>(in[2]),
+      };
+
+      assert(!memmove_called);
+      alg(in, in + N, out, N);
+      assert(memmove_called);
+      memmove_called = false;
+
+      assert(std::equal(out, out + N, expected));
+    }
+
+    // Unsigned -> signed.
+    {
+      constexpr int N = 3;
+      constexpr auto max_signed = std::numeric_limits<int>::max();
+      constexpr auto max_unsigned = std::numeric_limits<unsigned int>::max();
+
+      unsigned int in[N] = {static_cast<unsigned int>(max_signed) + 1, max_unsigned / 2, max_unsigned};
+      int out[N];
+      int expected[N] = {
+        static_cast<int>(in[0]),
+        static_cast<int>(in[1]),
+        static_cast<int>(in[2]),
+      };
+
+      assert(!memmove_called);
+      alg(in, in + N, out, N);
+      assert(memmove_called);
+      memmove_called = false;
+
+      assert(std::equal(out, out + N, expected));
+    }
+  };
+
+  check([](auto first, auto last, auto out, size_t) {
+    std::copy(first, last, out);
+  });
+  check([](auto first, auto last, auto out, size_t n) {
+    std::copy_backward(first, last, out + n);
+  });
+  check([](auto first, auto, auto out, size_t n) {
+    std::copy_n(first, n, out);
+  });
+  check([](auto first, auto last, auto out, size_t) {
+    std::move(first, last, out);
+  });
+  check([](auto first, auto last, auto out, size_t n) {
+    std::move_backward(first, last, out + n);
+  });
+
+  // Ranges.
+  check([](auto first, auto last, auto out, size_t) {
+    std::ranges::copy(first, last, out);
+  });
+  check([](auto first, auto last, auto out, size_t n) {
+    std::ranges::copy_backward(first, last, out + n);
+  });
+  check([](auto first, auto, auto out, size_t n) {
+    std::ranges::copy_n(first, n, out);
+  });
+  check([](auto first, auto last, auto out, size_t) {
+    std::ranges::move(first, last, out);
+  });
+  check([](auto first, auto last, auto out, size_t n) {
+    std::ranges::move_backward(first, last, out + n);
+  });
+}
+
+void test() {
+  // Built-in.
+  test_all_permutations_from_to_sent<int, int, std::type_identity_t>();
+  // User-defined.
+  test_all_permutations_from_to_sent<Foo, Foo, std::type_identity_t>();
+
+  // Conversions.
+  test_all_permutations_from_to_sent<char32_t, std::int32_t, sized_sentinel>();
+  test_all_permutations_from_to_sent<std::int32_t, std::uint32_t, sized_sentinel>();
+
+  // Copying between regular pointers.
+  test_copy_and_move<int**, std::type_identity_t, int**>();
+
+  // Copying between pointers to functions.
+  test_copy_and_move<FuncPtr*, std::type_identity_t, FuncPtr*>();
+
+  // Copying between pointers to members.
+  test_copy_and_move<MemObjPtr*, std::type_identity_t, MemObjPtr*>();
+  test_copy_and_move<MemFuncPtr*, std::type_identity_t, MemFuncPtr*>();
+
+  // Copying structs with bitfields.
+  test_copy_and_move<BitfieldS*, std::type_identity_t, BitfieldS*>();
+
+  // Copying objects with non-default alignment.
+  test_copy_and_move<AlignedS*, std::type_identity_t, AlignedS*>();
+
+  // Copying integers with different signedness produces the same results as built-in assignment.
+  test_different_signedness();
+}
+
+int main(int, char**) {
+  test();
+  // The test relies on a global variable, so it cannot be made `constexpr`; the `memmove` optimization is not used in
+  // `constexpr` mode anyway.
+
+  return 0;
+}

libcxx/test/libcxx/algorithms/alg.modifying.operations/copy_move_unwrap_reverse.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03, c++11, c++14, c++17
+
+// <algorithm>
+
+// These tests checks that `std::copy` and `std::move` (including their variations like `copy_n`) can unwrap multiple
+// layers of reverse iterators.
+
+#include <algorithm>
+#include <cassert>
+#include <cstdint>
+#include <iterator>
+#include <ranges>
+#include <type_traits>
+
+#include "test_iterators.h"
+
+template <size_t N, class Iter>
+requires (N == 0)
+constexpr auto wrap_n_times(Iter i) {
+  return i;
+}
+
+template <size_t N, class Iter>
+requires (N != 0)
+constexpr auto wrap_n_times(Iter i) {
+  return std::make_reverse_iterator(wrap_n_times<N - 1>(i));
+}
+
+static_assert(std::is_same_v<decltype(wrap_n_times<2>(std::declval<int*>())),
+                             std::reverse_iterator<std::reverse_iterator<int*>>>);
+
+template <class InIter, template <class> class SentWrapper, class OutIter, size_t W1, size_t W2, class Func>
+constexpr void test_one(Func func) {
+  using From = std::iter_value_t<InIter>;
+  using To = std::iter_value_t<OutIter>;
+
+  const size_t N = 4;
+
+  From input[N] = {{1}, {2}, {3}, {4}};
+  To output[N];
+
+  auto in     = wrap_n_times<W1>(InIter(input));
+  auto in_end = wrap_n_times<W1>(InIter(input + N));
+  auto sent   = SentWrapper<decltype(in_end)>(in_end);
+  auto out    = wrap_n_times<W2>(OutIter(output));
+
+  func(in, sent, out, N);
+
+  assert(std::equal(input, input + N, output, [](const From& lhs, const To& rhs) {
+        // Prevents warnings/errors due to mismatched signed-ness.
+        return lhs == static_cast<From>(rhs);
+    }));
+}
+
+template <class InIter, template <class> class SentWrapper, class OutIter, size_t W1, size_t W2>
+constexpr void test_copy_and_move() {
+  // Classic.
+  if constexpr (std::same_as<InIter, SentWrapper<InIter>>) {
+    test_one<InIter, SentWrapper, OutIter, W1, W2>([](auto first, auto last, auto out, size_t) {
+      std::copy(first, last, out);
+    });
+    test_one<InIter, SentWrapper, OutIter, W1, W2>([](auto first, auto last, auto out, size_t n) {
+      std::copy_backward(first, last, out + n);
+    });
+    test_one<InIter, SentWrapper, OutIter, W1, W2>([](auto first, auto, auto out, size_t n) {
+      std::copy_n(first, n, out);
+    });
+    test_one<InIter, SentWrapper, OutIter, W1, W2>([](auto first, auto last, auto out, size_t) {
+      std::move(first, last, out);
+    });
+    test_one<InIter, SentWrapper, OutIter, W1, W2>([](auto first, auto last, auto out, size_t n) {
+      std::move_backward(first, last, out + n);
+    });
+  }
+
+  // Ranges.
+  test_one<InIter, SentWrapper, OutIter, W1, W2>([](auto first, auto last, auto out, size_t) {
+    std::ranges::copy(first, last, out);
+  });
+  test_one<InIter, SentWrapper, OutIter, W1, W2>([](auto first, auto last, auto out, size_t n) {
+    std::ranges::copy_backward(first, last, out + n);
+  });
+  test_one<InIter, SentWrapper, OutIter, W1, W2>([](auto first, auto, auto out, size_t n) {
+    std::ranges::copy_n(first, n, out);
+  });
+  test_one<InIter, SentWrapper, OutIter, W1, W2>([](auto first, auto last, auto out, size_t) {
+    std::ranges::move(first, last, out);
+  });
+  test_one<InIter, SentWrapper, OutIter, W1, W2>([](auto first, auto last, auto out, size_t n) {
+    std::ranges::move_backward(first, last, out + n);
+  });
+}
+
+template <size_t W1, size_t W2, class From, class To, template <class> class SentWrapper>
+constexpr void test_all_permutations_with_counts_from_to_sent() {
+  test_copy_and_move<From*, SentWrapper, To*, W1, W2>();
+  test_copy_and_move<contiguous_iterator<From*>, SentWrapper, To*, W1, W2>();
+  test_copy_and_move<From*, SentWrapper, contiguous_iterator<To*>, W1, W2>();
+  test_copy_and_move<contiguous_iterator<From*>, SentWrapper, contiguous_iterator<To*>, W1, W2>();
+
+  if (!std::same_as<From, To>) {
+    test_copy_and_move<To*, SentWrapper, From*, W1, W2>();
+    test_copy_and_move<contiguous_iterator<To*>, SentWrapper, From*, W1, W2>();
+    test_copy_and_move<To*, SentWrapper, contiguous_iterator<From*>, W1, W2>();
+    test_copy_and_move<contiguous_iterator<To*>, SentWrapper, contiguous_iterator<From*>, W1, W2>();
+  }
+}
+
+template <size_t W1, size_t W2>
+constexpr void test_all_permutations_with_counts() {
+  test_all_permutations_with_counts_from_to_sent<W1, W2, int, int, std::type_identity_t>();
+  test_all_permutations_with_counts_from_to_sent<W1, W2, int, int, sized_sentinel>();
+  test_all_permutations_with_counts_from_to_sent<W1, W2, std::int32_t, std::uint32_t, std::type_identity_t>();
+  test_all_permutations_with_counts_from_to_sent<W1, W2, std::int32_t, std::uint32_t, sized_sentinel>();
+}
+
+constexpr bool test() {
+  test_all_permutations_with_counts<0, 0>();
+  test_all_permutations_with_counts<0, 2>();
+  test_all_permutations_with_counts<2, 0>();
+  test_all_permutations_with_counts<2, 2>();
+  test_all_permutations_with_counts<2, 4>();
+  test_all_permutations_with_counts<4, 4>();
+
+  return true;
+}
+
+int main(int, char**) {
+  test();
+  static_assert(test());
+
+  return 0;
+}

libcxx/test/libcxx/private_headers.verify.cpp

 #include <__algorithm/any_of.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/any_of.h'}}
 #include <__algorithm/binary_search.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/binary_search.h'}}
 #include <__algorithm/clamp.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/clamp.h'}}
 #include <__algorithm/comp.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/comp.h'}}
 #include <__algorithm/comp_ref_type.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/comp_ref_type.h'}}
 #include <__algorithm/copy.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/copy.h'}}
 #include <__algorithm/copy_backward.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/copy_backward.h'}}
 #include <__algorithm/copy_if.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/copy_if.h'}}
+#include <__algorithm/copy_move_common.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/copy_move_common.h'}}
 #include <__algorithm/copy_n.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/copy_n.h'}}
 #include <__algorithm/count.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/count.h'}}
 #include <__algorithm/count_if.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/count_if.h'}}
 #include <__algorithm/equal.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/equal.h'}}
 #include <__algorithm/equal_range.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/equal_range.h'}}
 #include <__algorithm/fill.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/fill.h'}}
 #include <__algorithm/fill_n.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/fill_n.h'}}
 #include <__algorithm/find.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/find.h'}}

libcxx/test/libcxx/type_traits/are_always_bitcastable.compile.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
+//
+//===----------------------------------------------------------------------===//
+//
+// <type_traits>
+//
+// UNSUPPORTED: c++03, c++11, c++14, c++17
+//
+// __are_always_bitcastable<_Tp, _Up>
+
+#include "test_macros.h"
+TEST_CLANG_DIAGNOSTIC_IGNORED("-Wprivate-header")
+#include <__type_traits/are_always_bitcastable.h>
+
+#include <climits>
+#include <cstdint>
+#ifndef TEST_HAS_NO_WIDE_CHARACTERS
+#include <cwchar>
+#endif
+#include "type_algorithms.h"
+
+// To test pointers to functions.
+void Func1() {}
+using FuncPtr1 = decltype(&Func1);
+int Func2() { return 0; }
+using FuncPtr2 = decltype(&Func2);
+
+template <bool Expected, class T, class U>
+constexpr void check_one() {
+  static_assert(std::__are_always_bitcastable<T, U>::value == Expected);
+}
+
+template <bool Expected, class T, class U>
+constexpr void check_with_volatile() {
+  check_one<Expected, T, U>();
+  check_one<Expected, volatile T, U>();
+  check_one<Expected, T, volatile U>();
+  check_one<Expected, volatile T, volatile U>();
+}
+
+template <bool Expected, class T, class U>
+constexpr void check_with_cv() {
+  check_with_volatile<Expected, T, U>();
+  check_with_volatile<Expected, const T, U>();
+  check_with_volatile<Expected, T, const U>();
+  check_with_volatile<Expected, const T, const U>();
+}
+
+template <bool Expected, class Types1, class Types2>
+constexpr void check_with_expected() {
+  meta::for_each(Types1{}, []<class T>() {
+    meta::for_each(Types2{}, []<class U>() {
+      check_with_cv<Expected, T, U>();
+    });
+  });
+}
+
+template <class Types>
+constexpr void check() {
+  check_with_expected<true, Types, Types>();
+}
+
+template <class T>
+constexpr void check_simple() {
+  check<meta::type_list<T>>();
+}
+
+template <class Types1, class Types2>
+constexpr void check_false() {
+  check_with_expected<false, Types1, Types2>();
+  check_with_expected<false, Types2, Types1>();
+}
+
+constexpr void test() {
+  // Arithmetic types.
+  {
+    // Bit-castable arithmetic types.
+
+    // 8-bit types.
+    using integral_8 = meta::type_list<char8_t, int8_t, uint8_t>;
+    using chars = meta::type_list<char, unsigned char, signed char>;
+#if CHAR_BIT == 8
+    check<meta::concatenate_t<integral_8, chars>>();
+#else
+    check<integral_8>();
+    check<chars>();
+#endif
+
+    // 16-bit types.
+    using integral_16 = meta::type_list<char16_t, int16_t, uint16_t>;
+#if !defined(TEST_HAS_NO_WIDE_CHARACTERS) && __WCHAR_WIDTH__ == 16
+    check<meta::concatenate_t<integral_16, meta::type_list<wchar_t>>>();
+#else
+    check<integral_16>();
+#endif
+
+    // 32-bit types.
+    using integral_32 = meta::type_list<char32_t, int32_t, uint32_t>;
+#if !defined(TEST_HAS_NO_WIDE_CHARACTERS) && __WCHAR_WIDTH__ == 32
+    check<meta::concatenate_t<integral_32, meta::type_list<wchar_t>>>();
+#else
+    check<integral_32>();
+#endif
+
+    // 64-bit types.
+    using integral_64 = meta::type_list<int64_t, uint64_t>;
+    check<integral_64>();
+
+    // 128-bit types.
+#ifndef TEST_HAS_NO_INT128
+    check<meta::type_list<__int128_t, __uint128_t>>();
+#endif
+
+    // Bool.
+    check_simple<bool>();
+
+    // Non-bit-castable arithmetic types.
+
+    // Floating-point.
+    check_false<meta::floating_point_types, meta::integral_types>();
+    check_false<meta::type_list<float>, meta::type_list<double, long double>>();
+    check_false<meta::type_list<double>, meta::type_list<float, long double>>();
+    check_false<meta::type_list<long double>, meta::type_list<float, double>>();
+
+    // Different sizes.
+    check_false<integral_8, meta::concatenate_t<integral_16, integral_32, integral_64>>();
+    check_false<integral_16, meta::concatenate_t<integral_8, integral_32, integral_64>>();
+    check_false<integral_32, meta::concatenate_t<integral_8, integral_16, integral_64>>();
+    check_false<integral_64, meta::concatenate_t<integral_8, integral_16, integral_32>>();
+
+    // Different representations -- bool.
+    check_false<meta::type_list<bool>, meta::concatenate_t<
+      meta::character_types,
+      meta::signed_integer_types,
+      meta::unsigned_integer_types,
+      meta::floating_point_types>>();
+
+    // Different representations -- floating point vs. integral.
+    check_false<meta::floating_point_types, meta::integral_types>();
+  }
+
+  // Enumerations.
+  {
+    enum E1 { Value1 };
+    enum E2 { Value2 };
+    check_simple<E1>();
+    check_false<meta::type_list<E1>, meta::type_list<E2>>();
+
+    enum class ScopedE1 { Value1 };
+    enum class ScopedE2 { Value1 };
+    check_simple<ScopedE1>();
+    check_false<meta::type_list<ScopedE1>, meta::type_list<ScopedE2>>();
+  }
+
+  // Pointers.
+  {
+    check_simple<int*>();
+    check_false<meta::type_list<int*>, meta::type_list<const int*, long*, void*>>();
+
+    check_simple<FuncPtr1>();
+    check_false<meta::type_list<FuncPtr1>, meta::type_list<FuncPtr2>>();
+  }
+
+  // Pointers to members.
+  {
+    struct S {
+      int mem_obj1 = 0;
+      long mem_obj2 = 0;
+      void MemFunc1() {}
+      int MemFunc2() { return 0; }
+    };
+    using MemObjPtr1 = decltype(&S::mem_obj1);
+    using MemObjPtr2 = decltype(&S::mem_obj2);
+    using MemFuncPtr1 = decltype(&S::MemFunc1);
+    using MemFuncPtr2 = decltype(&S::MemFunc2);
+
+    check_simple<MemObjPtr1>();
+    check_simple<MemFuncPtr1>();
+    check_false<meta::type_list<MemObjPtr1>, meta::type_list<MemObjPtr2>>();
+    check_false<meta::type_list<MemFuncPtr1>, meta::type_list<MemFuncPtr2>>();
+  }
+
+  // Trivial classes.
+  {
+    struct S1 {};
+    check_simple<S1>();
+    struct S2 {};
+    check_false<meta::type_list<S1>, meta::type_list<S2>>();
+  }
+
+  // Trivial unions.
+  {
+    union U1 {};
+    check_simple<U1>();
+    union U2 {};
+    check_false<meta::type_list<U1>, meta::type_list<U2>>();
+  }
+
+  // References.
+  {
+    check_false<meta::type_list<int&>, meta::type_list<int&>>();
+  }
+
+  /* TODO: uncomment before merging.
+  // Arrays.
+  {
+    check_false<meta::type_list<int[1]>, meta::type_list<int[1]>>();
+  }
+  */
+}

libcxx/test/std/algorithms/alg.modifying.operations/alg.copy/ranges.copy_backward.pass.cpp

constexpr void test_sentinels() {
   test_iterators<InIter, OutIter, sized_sentinel<InIter>>();
 }
 
 template <class Out>
 constexpr void test_in_iterators() {
   test_sentinels<bidirectional_iterator<int*>, Out>();
   test_sentinels<random_access_iterator<int*>, Out>();
   test_sentinels<contiguous_iterator<int*>, Out>();
+  test_sentinels<int*, Out>();
 }
 
 template <class Out>
 constexpr void test_proxy_in_iterators() {
   test_sentinels<ProxyIterator<bidirectional_iterator<int*>>, Out>();
   test_sentinels<ProxyIterator<random_access_iterator<int*>>, Out>();
   test_sentinels<ProxyIterator<contiguous_iterator<int*>>, Out>();
 }
 
 constexpr bool test() {
   test_in_iterators<bidirectional_iterator<int*>>();
   test_in_iterators<random_access_iterator<int*>>();
   test_in_iterators<contiguous_iterator<int*>>();
+  test_in_iterators<int*>();
 
   test_proxy_in_iterators<ProxyIterator<bidirectional_iterator<int*>>>();
   test_proxy_in_iterators<ProxyIterator<random_access_iterator<int*>>>();
   test_proxy_in_iterators<ProxyIterator<contiguous_iterator<int*>>>();
 
   { // check that ranges::dangling is returned
     std::array<int, 4> out;
     std::same_as<std::ranges::in_out_result<std::ranges::dangling, int*>> auto ret =

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

 
 template <class Out>
 constexpr void test_in_iterators() {
   test_iterators<cpp20_input_iterator<int*>, Out, sentinel_wrapper<cpp20_input_iterator<int*>>>();
   test_iterators<forward_iterator<int*>, Out>();
   test_iterators<bidirectional_iterator<int*>, Out>();
   test_iterators<random_access_iterator<int*>, Out>();
   test_iterators<contiguous_iterator<int*>, Out>();
+  test_iterators<int*, Out>();
 }
 
 template <class Out>
 constexpr void test_proxy_in_iterators() {
   test_iterators<ProxyIterator<cpp20_input_iterator<int*>>, Out, sentinel_wrapper<ProxyIterator<cpp20_input_iterator<int*>>>>();
   test_iterators<ProxyIterator<forward_iterator<int*>>, Out>();
   test_iterators<ProxyIterator<bidirectional_iterator<int*>>, Out>();
   test_iterators<ProxyIterator<random_access_iterator<int*>>, Out>();
constexpr bool test() {
   test_in_iterators<cpp17_output_iterator<int*>>();
   test_in_iterators<cpp20_output_iterator<int*>>();
   test_in_iterators<cpp17_input_iterator<int*>>();
   test_in_iterators<cpp20_input_iterator<int*>>();
   test_in_iterators<forward_iterator<int*>>();
   test_in_iterators<bidirectional_iterator<int*>>();
   test_in_iterators<random_access_iterator<int*>>();
   test_in_iterators<contiguous_iterator<int*>>();
+  test_in_iterators<int*>();
 
   test_proxy_in_iterators<ProxyIterator<cpp20_input_iterator<int*>>>();
   test_proxy_in_iterators<ProxyIterator<forward_iterator<int*>>>();
   test_proxy_in_iterators<ProxyIterator<bidirectional_iterator<int*>>>();
   test_proxy_in_iterators<ProxyIterator<random_access_iterator<int*>>>();
   test_proxy_in_iterators<ProxyIterator<contiguous_iterator<int*>>>();
 
   { // check that a move-only type works

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

 template <class In, class Out, class Sent = In>
 constexpr void test_iterators() {
   // simple test
   test<In, Out, Sent, 4>({1, 2, 3, 4});
   // check that an empty range works
   test<In, Out, Sent, 0>({});
 }
 
+template <class InIter, class OutIter>
+constexpr void test_sentinels() {
+  test_iterators<InIter, OutIter, InIter>();
+  test_iterators<InIter, OutIter, sentinel_wrapper<InIter>>();
+  test_iterators<InIter, OutIter, sized_sentinel<InIter>>();
+}
+
 template <class Out>
 constexpr void test_in_iterators() {
-  test_iterators<bidirectional_iterator<int*>, Out, sentinel_wrapper<bidirectional_iterator<int*>>>();
-  test_iterators<bidirectional_iterator<int*>, Out>();
-  test_iterators<random_access_iterator<int*>, Out>();
-  test_iterators<contiguous_iterator<int*>, Out>();
+  test_sentinels<bidirectional_iterator<int*>, Out>();
+  test_sentinels<random_access_iterator<int*>, Out>();
+  test_sentinels<contiguous_iterator<int*>, Out>();
+  test_sentinels<int*, Out>();
 }
 
 template <class Out>
 constexpr void test_proxy_in_iterators() {
   test_iterators<ProxyIterator<bidirectional_iterator<int*>>, Out, sentinel_wrapper<ProxyIterator<bidirectional_iterator<int*>>>>();
   test_iterators<ProxyIterator<bidirectional_iterator<int*>>, Out>();
   test_iterators<ProxyIterator<random_access_iterator<int*>>, Out>();
   test_iterators<ProxyIterator<contiguous_iterator<int*>>, Out>();
struct IteratorWithMoveIter {
 
   constexpr bool operator==(const IteratorWithMoveIter& other) const = default;
 };
 
 constexpr bool test() {
   test_in_iterators<bidirectional_iterator<int*>>();
   test_in_iterators<random_access_iterator<int*>>();
   test_in_iterators<contiguous_iterator<int*>>();
+  test_in_iterators<int*>();
 
   test_proxy_in_iterators<ProxyIterator<bidirectional_iterator<int*>>>();
   test_proxy_in_iterators<ProxyIterator<random_access_iterator<int*>>>();
   test_proxy_in_iterators<ProxyIterator<contiguous_iterator<int*>>>();
 
   { // check that a move-only type works
     {
       MoveOnly a[] = {1, 2, 3};