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

[var-const]

Summary

Instead of using reverse_iterator, share the optimization between the 4 algorithms. The key observation here that memmove applies to both copy and move identically, and to their _backward versions very similarly. All algorithms now follow the same pattern along the lines of:

if constexpr (can_memmove<InIter, OutIter>) {
  memmove(first, last, out);
} else {
  naive_implementation(first, last, out);
}

A follow-up will delete unconstrained_reverse_iterator.

This patch removes duplication and divergence between std::copy, std::move and std::move_backward. It also improves testing:

• the test for whether the optimization is used only applied to std::copy and, more importantly, was essentially a no-op because it would still pass if the optimization was not used;
• there were no tests to make sure the optimization is not used when the effect would be visible.

[ldionne]

libcxx/include/__algorithm/copy_move_common.h

29–30

We do need a different trait to implement std::copy and std::move. We can't check is_trivially_move_assignable or is_trivially_copy_assignable for both algorithms.

43

I would use std::memmove instead. We're not using this optimization during constexpr anyway.

107

I think this is actually insufficient. There's another bug that we rewrap iterators and sentinels, leading to running the algorithm on a non-sensical range (delimited by [unwrapped-iterator, wrapped-sentinel)).

See the TODO: some algorithms calls std::__copy in libcxx/test/std/algorithms/alg.sorting/sortable_helpers.h. I'm not 100% sure what's the right fix, but I would maybe explore querying whether __unwrap_range can be called on [iter, sent) -- that would require changes to the semantics of __unwrap_range, though. Or maybe you could call __unwrap_range unconditionally and have it be a no-op if it can't unwrap.

That also makes me think that __can_unwrap should actually be called __can_rewrap, and then everything makes a bit more sense.

TLDR: Rename __can_unwrap to __can_rewrap, and then use __unwrap_range instead of __unwrap_iter for __first and __last. That way, we'll either unwrap both or none of them, and we'll know that we're able to rewrap them after.

128–132

Same above. It's easier to read enable_if when they are in the template argument list, and it's what we try to do in new code elsewhere in the library.

[var-const]

Finalize

[var-const]

Fix the CI.

[var-const]

Fix the CI.

[var-const]

Address feedback

libcxx/include/__algorithm/copy_move_common.h

107

Renamed the trait and replaced __unwrap_iter with __unwrap_range.

Or maybe you could call __unwrap_range unconditionally and have it be a no-op if it can't unwrap.

I might be misreading it, but it seems to already be the case. __unwrap_range only calls __unwrap_iter either if both the iterator and the sentinel are the same type or if the end iterator can be created in constant time; otherwise, it simply returns the given arguments.

128–132

Thanks for explaining!

libcxx/include/__algorithm/move.h

80

I'm not sure if this optimization is still pulling its weight in complexity now that we no longer use reverse iterators in the implementation. I also don't really like that it only applies to the case where both the input and the output iterators are reverse, even though these are orthogonal.

[var-const]

Fix the CI.

[ldionne]

libcxx/include/__algorithm/copy.h

65

I think we can get rid of __is_reverse_iterator in this patch too.

A folllow-up patch should get rid of __unconstrained_reverse_iterator, but that may require a bit of additional work in e.g. inplace_merge. Still worth doing.

libcxx/include/__algorithm/copy_move_common.h

2

Draft from our discussion just now:

template <class _AlgPolicy>
struct __copy_loop {
  template <class _InIter, class _Sentinel, class _OutIter>
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
  pair<_InIter, _OutIter>
  operator()(_InIter __first, _Sentinel __last, _OutIter __result) const {
    while (__first != __last) {
      *__result = *__first;
      ++__first;
      ++__result;
    }

    return pair<_InIter, _OutIter>(std::move(__first), std::move(__result));
  }
};

template <class _AlgPolicy>
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, class = __enable_if_t<
    is_trivially_assignable<_Out&, _In&>::value
  > >
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
  pair<_In*, _Out*>
  operator()(_In* __first, _In* __last, _Out* __result) const {
    const size_t __n = static_cast<size_t>(__last - __first);
    std::memmove(__result, __first, __n * sizeof(_Out));

    return pair<_In*, _Out*>(__last, __result + __n);
  }
};

template <class _F1, class _F2>
struct __overload : _F1, _F2 {
    using _F1::operator();
    using _F2::operator();
};

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_AFTER_CXX14
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 pair<_InIter, _OutIter>(
      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_AFTER_CXX14
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 _NaiveAlgorithm, class _OptimizedAlgorithm, class _InIter, class _Sent, class _OutIter>
_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX14
pair<_InIter, _OutIter>
__dispatch_copy_or_move(_InIter __first, _Sent __last, _OutIter __out_first) {
  if (__libcpp_is_constant_evaluated()) {
    return std::__unwrap_and_dispatch<_NaiveAlgorithm>(std::move(__first), std::move(__last), std::move(__out_first));
  }

  using _Algorithm = std::__overload<_NaiveAlgorithm, _OptimizedAlgorithm>;
  return std::__unwrap_and_dispatch<_Algorithm>(std::move(__first), std::move(__last), std::move(__out_first));
}


template <class _AlgPolicy, class _InIter, class _Sent, class _OutIter>
pair<_InIter, _OutIter>
inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
__copy(_InIter __first, _Sent __last, _OutIter __result) {
  return std::__dispatch_copy_or_move<__copy_loop<_AlgPolicy>, __copy_trivial<_AlgPolicy> >(
      std::move(__first), std::move(__last), std::move(__result));
}

template <class _InputIterator, class _OutputIterator>
inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
_OutputIterator
copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result) {
  return std::__copy<_ClassicAlgPolicy>(__first, __last, __result).second;
}

98

Per your comment just now: maybe we can take T* in the trivial version of __run since contiguous iterators are already unwrapped by unwrap_iter by the time we get there. That would simplify the sfinae and perhaps more.

libcxx/include/__algorithm/ranges_move_backward.h

18–19

Not needed anymore.

libcxx/include/__algorithm/unwrap_iter.h

36 ↗

(On Diff #451203)

Not sure whether the reordering is worth doing. Neutral on this.

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

106–107

I don't think that's still the case?

[var-const]

Feedback, add tests.

libcxx/include/__algorithm/copy_move_common.h

84

Now that our implementation no longer relies on reverse iterators, I don't think the extra complexity is justified.

libcxx/include/__algorithm/unwrap_iter.h

36 ↗

(On Diff #451203)

In that case, I'd keep it -- I think it makes more sense to place _re_wrapping after unwrapping.

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

106–107

Yes, this is fixed now!

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

1

Should all be covered now.

[var-const]

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

74

This test was actually incorrect -- because unwrapping iterators uses to_address to reduce them to pointers, the fact that this iterator is not incrementable doesn't matter -- it would work if the implementation chooses to forward to memmove just fine.

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

10

I think these tests can be made to work pre-C++20, but it would be painful, partially because contiguous_iterator_tag is a C++20 addition. Please let me know if you think it's worth the trouble.

67

I have manually verified that this check works -- if I change NonTrivialCopy/Move to become trivial, this test will no longer compile, complaining that contiguous_iterator cannot be converted to void*.

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

38

I don't think it's possible to test this any other way, since it is by design that whether the optimization was applied is not observable by normal means. While it is undefined behavior to add things to the std namespace for user code, I would consider tests to be part of the implementation (and in any case, we control the implementation). This logic would break if the optimization changes, e.g. if the call to memmove were to be replaced by __builtin_memmove, but in that case the test will start failing, so I don't think that's a significant problem.

[philnik]

libcxx/include/__algorithm/copy.h

24–32

Could you clang-format all the changes?

34

Why did you rename _Sent to _Sentinel? AFAIK we settled on _Sent for the naming in the ranges algorithms. Same for _InputIterator and similar stuff.

59

Why does copy get an _AlgPolicy now? AFAICT it's never used anywhere, which means it just produces duplicate code.

libcxx/include/__algorithm/copy_backward.h

38

std::make_pair?

58–67

?!

libcxx/include/__algorithm/copy_move_common.h

21

Could you use the granularized includes instead?

35

Why did you get rid of calling __builtin_memmove during constant evaluation?

116

Sentinels are always copy-constructible.

151

libcxx/include/__algorithm/move_backward.h

42

Why constexpr since 20? Others are marked as constexpr since 14.

65

Please add a static_assert to make sure the iterators are copyable.

libcxx/include/__algorithm/unwrap_iter.h

36 ↗

(On Diff #456586)

Why did you move this code?

libcxx/include/__algorithm/unwrap_range.h

34 ↗

(On Diff #456586)

AFAICT this isn't correct. Lines 43-45 should handle this case just fine. Also, why not _v?

35 ↗

(On Diff #456586)

Why the indentation change? This file was properly clang-formatted before.

[ldionne]

I am quite happy with this patch. There are a few nits, but other than that, LGTM. Thanks for the numerous iterations offline on this one.

@philnik I'll let you give final approval once you're satisfied.

libcxx/include/__algorithm/copy.h

59

For consistency.

To address the code size concern, I think what we should do is change __copy above like so:

template <class _AlgPolicy, class _InIter, class _Sent, class _OutIter>
pair<_InIter, _OutIter>
inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14
__copy(_InIter __first, _Sent __last, _OutIter __result) {
  // NOTE: There is no difference between the ranges and the STL classic version of this algorithm,
  //       so we always use _ClassicAlgPolicy to reduce code bloat.
  return std::__dispatch_copy_or_move<__copy_loop<_ClassicAlgPolicy>, __copy_trivial<_ClassicAlgPolicy> >(
      std::move(__first), std::move(__last), std::move(__result));
}

libcxx/include/__algorithm/copy_move_common.h

35

GCC didn't support it, which added a bunch of complexity. So now what we do instead is unwrap the iterators and use the loop version when we're inside constant evaluation. The performance during constant evaluation is less of a concern than performance at runtime.

libcxx/include/__algorithm/unwrap_iter.h

36 ↗

(On Diff #451203)

Please land it as a separate NFC patch, that should solve the issue and close this thread.

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

10

I don't think it's worth the trouble.

51

65

[philnik]

libcxx/include/__algorithm/copy.h

59

This isn't just affecting copy though. This also results in multiple versions for all the set algorithms. I really don't think that this bit of consistency is worth lots of extra instantiations for these algorithms.

libcxx/include/__algorithm/copy_move_common.h

35

AFAICT the only complexity added by GCC not supporting it is an extra #ifndef _LIBCPP_COMPILER_GCC. How does calling __builtin_memmove result in worse runtime performance? IMO we shouldn't massively pessimize constant evaluation performance for removing a few lines of code.

For example:

#include <cstddef>

constexpr void copy_arrays(int* begin, int* end, int* out) {
#ifdef USE_MEMMOVE
  ::__builtin_memmove(out, begin, static_cast<std::size_t>(end - begin));
#else
  while (begin != end) {
    *out = *begin;
    ++begin;
    ++out;
  }
#endif
}

constexpr bool use_data() {
  int a[100000] = {};
  int b[100000] = {};
  ::copy_arrays(a, a + 100000, b);

  return true;
}

static_assert(use_data());

Without using __builtin_memmove takes 200ms to compile, with __builtin_memmove is takes 30ms.

[huixie90]

LGMT with nits and with green CI

libcxx/include/__algorithm/copy.h

24–32

would it be possible to make this not a template?

34–35

I understand it is not a problem but putting a completely unconstrained overload into the __overload struct makes me a bit concerned. I understand it is working right now because the other overload's signature takes a pointer, which is more specific than this one. Having said that, I don't think putting a constraint helps it in any way.

51

would it be possible to put __copy_trivial definition inside this header? AFAICT, the common header only reuses __copy_trivial_impl not __copy_trivial

libcxx/include/__algorithm/copy_move_common.h

105–108

AFAIK, this is not an aggregate pre c++17 and you will need a constructor

110–119

nit: would _Lazy<_And<... work here?

143

extra nit and not an issue: I don't like the name Naive but I don't anything better

libcxx/include/__algorithm/move.h

32

question: if the input is a contiguous iterator pointing to a trivially copyable/moveable type, but the iterator has specialised iter_move ( yes it is very contrived), would the move dispatch to the overload that unwraps the contiguous iterator to pointer and call memmove without going through the specialised iter_move?

[var-const]

Address feedback

libcxx/include/__algorithm/copy.h

34

Restored _Sent. I didn't think this qualifies as a range algorithm, but now that you mention it, I presume it does (I still don't think having two different name conventions is a good idea).

34–35

Yes, the idea is that pointers are more specialized. I actually had mutually-exclusive constraints in an earlier revision, but relying on pointers seems to provide a nice simplification.

51

I'd rather keep everything related to the memmove optimization in one place. One of the goals of this patch was to make these details leak out as little as possible into the actual algorithms.

libcxx/include/__algorithm/copy_backward.h

38

I think @huixie90 pointed out previously that make_pair creates copies of the arguments in C++03 mode.

58–67

Thanks for noticing! I started working on this patch a while ago, this is probably a rudiment from that time.

libcxx/include/__algorithm/copy_move_common.h

35

The original form of this code was (with slight NFC reformatting):

if (__libcpp_is_constant_evaluated()
#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);

Unless I'm missing something obvious, __builtin_memmove was never called during constant evaluation.

110–119

Probably. What would be the advantage of using _Lazy here?

116

This isn't necessarily a sentinel in the C++20-concept sense. This can be instantiated with e.g. a pair of input iterators that aren't copyable.

libcxx/include/__algorithm/unwrap_iter.h

36 ↗

(On Diff #456586)

@philnik I find that logically, *re*wrapping has to go after unwrapping, since *re* implies adding something that was previously removed. I originally had more changes to this file, but those went away eventually. I reverted the change from this patch and will submit it separately.

libcxx/include/__algorithm/unwrap_range.h

34 ↗

(On Diff #456586)

Hmm, I remember adding this to avoid a compilation error, but it looks like that error no longer applies. Removed.

[var-const]

libcxx/include/__algorithm/move.h

32

I think this is a great point, thanks. I'm inclined to leave it as is for this patch because it's a preexistent thing, but I will address it in a follow-up.

libcxx/include/__algorithm/move_backward.h

42

This is preexisting and I'd rather not change it in this patch.

[philnik]

libcxx/include/__algorithm/copy_backward.h

38

Then we should just remove the #ifndef _LIBCPP_CXX03_LANG, since we require rvalue support in C++03. See D133013.

58–67

Ah OK, so it was just a merge conflict probably.

libcxx/include/__algorithm/copy_move_common.h

35

To me it looks like it was called when the type is_trivially_copyable.

116

C++17 input iterators are always copyable and input_iterators can't be their own sentinel if they aren't copyable .

[var-const]

Address feedback, fix CI.

libcxx/include/__algorithm/copy.h

59

Now because of using __builtin_memmove, it's necessary to get the value_type of the iterator, so _AlgPolicy is now necessary for copy as well.

libcxx/include/__algorithm/copy_backward.h

38

Thanks for doing the change!

libcxx/include/__algorithm/copy_move_common.h

35

Okay, I restored using __builtin_memmove during constant evaluation, with the necessary additional conditions. I also added a test to make sure the is_trivially_copyable condition is honored.

I'm still not sure if it's worth the extra complexity (although now the complexity is all in one place, making this a little more manageable). @ldionne What do you think? I'm somewhat on the fence and can be convinced either way.

[ldionne]

libcxx/include/__algorithm/copy_move_common.h

35

Yeah, I think restoring the __builtin_memmove behavior is probably worth it given the surprising (to me) compile-time speedup.

55–88

IMO those should be defined in copy.h, move.h, copy_backward.h and move_backward.h instead.

libcxx/include/__algorithm/move.h

32

Is this really something we should fix? Aren't we allowed to bypass the iterator's iter_move?

[philnik]

LGTM with comments addressed and a green CI.

libcxx/include/__algorithm/copy_backward.h

62

Please static_assert that the iterators are copyable.

libcxx/include/__algorithm/copy_move_common.h

59

It's a weird quirk of clang-format right now and I don't know exactly why it does this, but these spaces can be removed and clang-format won't add them again. I think it's because of SpacesInAngles: Keep, but that shouldn't mean they are kept after a an opening one. Anyways, if you feel like removing these it would be nice, but not a must from my side.

libcxx/include/__algorithm/move_backward.h

66–67

Please also static_assert here.

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

26

Maybe use a requires since the test requires C++20 anyways?

107

This is technically still ill-formed, since the return type has to be element_type*, but I guess it's OK for us to do it in this case.

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

24

To make it less prone to failing when we change includes, could you move the <type_traits> include down and static_assert the trivially_copyable later? It should still catch a problem before anything unpredictable happens. AFAICT you don't actually need the <cstring> include. <cstddef> should suffice for size_t.

51

Also requires here.

69

What is this Foo for? Shouldn't the compiler be able to deduce the correct type?

libcxx/test/std/strings/basic.string/string.modifiers/string_insert/size_pointer_size.pass.cpp

9–11 ↗

(On Diff #457753)

Why is this required? Did it hit the constexpr limit without the __builtin_memmove? In that case, please remove the bumped limit again.

[philnik]

Sorry, I know I approved it before, but I just noticed that this patch still regresses on some optimizations (in particular optimizing reverse_iterator<contiguous-iterator>), so maybe I'm missing more and I'm also questioning the usefulness of the changes more and more, so I'd like some clarification. What exactly is the goal of the refactoring here? How does the refactored code do the job better than forwarding copy_backward, move and move_backward to copy? The answers to these questions would probably also be good to have in the commit message. I first thought that his patch removed some of the complication in copy.h, but the longer I think about it it the more it looks to me like it's just shifting the complexity around.

[var-const]

Feedback + rebase

[var-const]

In D130695#3783138, @philnik wrote:

Sorry, I know I approved it before, but I just noticed that this patch still regresses on some optimizations (in particular optimizing reverse_iterator<contiguous-iterator>), so maybe I'm missing more and I'm also questioning the usefulness of the changes more and more, so I'd like some clarification. What exactly is the goal of the refactoring here? How does the refactored code do the job better than forwarding copy_backward, move and move_backward to copy? The answers to these questions would probably also be good to have in the commit message. I first thought that his patch removed some of the complication in copy.h, but the longer I think about it it the more it looks to me like it's just shifting the complexity around.

The main motivation is to reduce complexity and remove code duplication. Majority of the remaining complexity is due to having to support C++03. The ideal state I envision is essentially something like

if constexpr (__can_memmove<_InIter, _OutIter>) {
  return __memmove(__first, __last, __out);
} else {
  return __copy_loop(__first, __last, __out);
}

in every algorithm (as a side note, I really hope we get Clang to support if constexpr in C++03 mode at some point). This patch brings this as close to that state as I could within the limitations of C++03.

As for specific improvements:

• the optimization was fully duplicated between std::copy and std::move. Moreover, std::move_backward had a divergent, less thorough implementation of the optimization. Now the duplication is removed and everything related to this optimization is encapsulated in one place.
• all 4 algorithms now have symmetrical, self-contained implementations which makes them easier to read and debug.
• reverse_iterator is no longer used in the implementation, which makes it significantly easier to understand and removes artificial types from backtraces. Using reverse_iterator has lead to at least one serious bug already.
• unconstrainted_reverse_iterator can now be removed (which I intend to do in a follow-up), removing a lot of code duplication and complexity.
• the test for whether the optimization is used only applied to std::copy and, more importantly, was essentially a no-op because it would still pass if the optimization was not used;
• there were no tests to make sure the optimization is not used when the effect would be visible.

Regarding the reverse_iterator optimization you mention, I think it was solution for a problem that the previous approach introduced and that is no longer applicable. The optimization was very limited in that it would only apply to the case where both the input and the output iterators were reverse iterators. I see no inherent reason why users would reverse both the input and the output sequence rather than just one of them, outside of the artificial case where our implementation itself would do the wrapping. If this optimization were to be restored, it would have to apply equally to input and output iterators. I don’t think, however, it would be pulling its weight.

libcxx/include/__algorithm/move.h

32

Hmm, inlining the definition from the standard a little bit, it looks like:

Effects: [...] For each non-negative integer `n < N`, performs `*(result + n) = ranges​::​iter_­move(first + n)`.

I'm not sure if there's anything that would allow us to bypass this?
(see https://eel.is/c++draft/alg.move)

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

26

Good point.

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

24

Replaced the <cstring> include (it's from the previous iteration which used memmove). I'd prefer to keep the static assertion close to the point of class definition, though. Can you elaborate on how the test might fail if we change includes?

libcxx/test/std/strings/basic.string/string.modifiers/string_insert/size_pointer_size.pass.cpp

9–11 ↗

(On Diff #457753)

It failed on CI. I'll remove the flags and see if the current state stays within the limit or not.

[philnik]

The main motivation is to reduce complexity and remove code duplication. Majority of the remaining complexity is due to having to support C++03. The ideal state I envision is essentially something like

if constexpr (__can_memmove<_InIter, _OutIter>) {
  return __memmove(__first, __last, __out);
} else {
  return __copy_loop(__first, __last, __out);
}

in every algorithm (as a side note, I really hope we get Clang to support if constexpr in C++03 mode at some point). This patch brings this as close to that state as I could within the limitations of C++03.

It would definitely be nice if we could write it that simple. Unfortunately we can't currently.

As for specific improvements:

• the optimization was fully duplicated between std::copy and std::move. Moreover, std::move_backward had a divergent, less thorough implementation of the optimization. Now the duplication is removed and everything related to this optimization is encapsulated in one place.

That would also be the case if we forward to std::copy though, right?

• all 4 algorithms now have symmetrical, self-contained implementations which makes them easier to read and debug.

I'm not sure this is actually simpler to debug. I haven't checked the current backtrace, so maybe it's worse, but here is one similar to what I encountered while working on D132505:

* thread #1, name = 't.tmp.exe', stop reason = signal SIGSEGV: invalid address (fault address: 0x0)
  * frame #0: 0x000055555555967c t.tmp.exe`std::__1::pair<std::__1::__deque_iterator<int, int const*, int const&, int const* const*, long, 1024l>, std::__1::__deque_iterator<int, int*, int&, int**, long, 1024l>> std::__1::__copy_loop<std::__1::_ClassicAlgPolicy>::operator()[abi:v16000]<std::__1::__deque_iterator<int, int const*, int const&, int const* const*, long, 1024l>, std::__1::__deque_iterator<int, int*, int&, int**, long, 1024l>, 0>(std::__1::__deque_iterator<int, int const*, int const&, int const* const*, long, 1024l>, std::__1::__deque_iterator<int, int const*, int const&, int const* const*, long, 1024l>, std::__1::__deque_iterator<int, int*, int&, int**, long, 1024l>) const [inlined] std::__1::__segmented_iterator_traits<std::__1::__deque_iterator<int, int*, int&, int**, long, 1024l>>::__end[abi:v16000](__iter=0x0000000000000000) at deque:406:91
    frame #1: 0x000055555555967c t.tmp.exe`std::__1::pair<std::__1::__deque_iterator<int, int const*, int const&, int const* const*, long, 1024l>, std::__1::__deque_iterator<int, int*, int&, int**, long, 1024l>> std::__1::__copy_loop<std::__1::_ClassicAlgPolicy>::operator()[abi:v16000]<std::__1::__deque_iterator<int, int const*, int const&, int const* const*, long, 1024l>, std::__1::__deque_iterator<int, int*, int&, int**, long, 1024l>, 0>(std::__1::__deque_iterator<int, int const*, int const&, int const* const*, long, 1024l>, std::__1::__deque_iterator<int, int const*, int const&, int const* const*, long, 1024l>, std::__1::__deque_iterator<int, int*, int&, int**, long, 1024l>) const at copy.h:83:27
    frame #2: 0x0000555555559662 t.tmp.exe`std::__1::pair<std::__1::__deque_iterator<int, int const*, int const&, int const* const*, long, 1024l>, std::__1::__deque_iterator<int, int*, int&, int**, long, 1024l>> std::__1::__copy_loop<std::__1::_ClassicAlgPolicy>::operator()[abi:v16000]<std::__1::__deque_iterator<int, int const*, int const&, int const* const*, long, 1024l>, std::__1::__deque_iterator<int, int*, int&, int**, long, 1024l>, 0>(std::__1::__deque_iterator<int, int const*, int const&, int const* const*, long, 1024l>, std::__1::__deque_iterator<int, int const*, int const&, int const* const*, long, 1024l>, std::__1::__deque_iterator<int, int*, int&, int**, long, 1024l>) const [inlined] std::__1::pair<int const*, std::__1::__deque_iterator<int, int*, int&, int**, long, 1024l>> std::__1::__unwrap_and_dispatch[abi:v16000]<std::__1::__overload<std::__1::__copy_loop<std::__1::_ClassicAlgPolicy>, std::__1::__copy_trivial>, int const*, int const*, std::__1::__deque_iterator<int, int*, int&, int**, long, 1024l>, 0>(__first=0x0000000000000000, __last=0x0000000000000000, __out_first=__deque_iterator<int, int *, int &, int **, long, 1024L> @ 0x0000000001c45b10) at copy_move_common.h:81:19
    frame #3: 0x0000555555559662 t.tmp.exe`std::__1::pair<std::__1::__deque_iterator<int, int const*, int const&, int const* const*, long, 1024l>, std::__1::__deque_iterator<int, int*, int&, int**, long, 1024l>> std::__1::__copy_loop<std::__1::_ClassicAlgPolicy>::operator()[abi:v16000]<std::__1::__deque_iterator<int, int const*, int const&, int const* const*, long, 1024l>, std::__1::__deque_iterator<int, int*, int&, int**, long, 1024l>, 0>(std::__1::__deque_iterator<int, int const*, int const&, int const* const*, long, 1024l>, std::__1::__deque_iterator<int, int const*, int const&, int const* const*, long, 1024l>, std::__1::__deque_iterator<int, int*, int&, int**, long, 1024l>) const [inlined] std::__1::pair<int const*, std::__1::__deque_iterator<int, int*, int&, int**, long, 1024l>> std::__1::__dispatch_copy_or_move[abi:v16000]<std::__1::_ClassicAlgPolicy, std::__1::__copy_loop<std::__1::_ClassicAlgPolicy>, std::__1::__copy_trivial, int const*, int const*, std::__1::__deque_iterator<int, int*, int&, int**, long, 1024l>>(__first=0x0000000000000000, __last=0x0000000000000000, __out_first=__deque_iterator<int, int *, int &, int **, long, 1024L> @ 0x0000000001c13090) at copy_move_common.h:119:10
    frame #4: 0x0000555555559662 t.tmp.exe`std::__1::pair<std::__1::__deque_iterator<int, int const*, int const&, int const* const*, long, 1024l>, std::__1::__deque_iterator<int, int*, int&, int**, long, 1024l>> std::__1::__copy_loop<std::__1::_ClassicAlgPolicy>::operator()[abi:v16000]<std::__1::__deque_iterator<int, int const*, int const&, int const* const*, long, 1024l>, std::__1::__deque_iterator<int, int*, int&, int**, long, 1024l>, 0>(std::__1::__deque_iterator<int, int const*, int const&, int const* const*, long, 1024l>, std::__1::__deque_iterator<int, int const*, int const&, int const* const*, long, 1024l>, std::__1::__deque_iterator<int, int*, int&, int**, long, 1024l>) const [inlined] std::__1::pair<int const*, std::__1::__deque_iterator<int, int*, int&, int**, long, 1024l>> std::__1::__copy[abi:v16000]<std::__1::_ClassicAlgPolicy, int const*, int const*, std::__1::__deque_iterator<int, int*, int&, int**, long, 1024l>>(__first=0x0000000000000000, __last=0x0000000000000000, __result=__deque_iterator<int, int *, int &, int **, long, 1024L> @ 0x0000000001c13090) at copy.h:108:10
    frame #5: 0x0000555555559662 t.tmp.exe`std::__1::pair<std::__1::__deque_iterator<int, int const*, int const&, int const* const*, long, 1024l>, std::__1::__deque_iterator<int, int*, int&, int**, long, 1024l>> std::__1::__copy_loop<std::__1::_ClassicAlgPolicy>::operator(this=0x00007fffffffda18, __first=__deque_iterator<int, const int *, const int &, const int *const *, long, 1024L> @ 0x00000000019d5fd0, __last=__deque_iterator<int, const int *, const int &, const int *const *, long, 1024L> @ 0x00000000019d5fd0, __result=__deque_iterator<int, int *, int &, int **, long, 1024L> @ 0x00007fffffffda00)[abi:v16000]<std::__1::__deque_iterator<int, int const*, int const&, int const* const*, long, 1024l>, std::__1::__deque_iterator<int, int*, int&, int**, long, 1024l>, 0>(std::__1::__deque_iterator<int, int const*, int const&, int const* const*, long, 1024l>, std::__1::__deque_iterator<int, int const*, int const&, int const* const*, long, 1024l>, std::__1::__deque_iterator<int, int*, int&, int**, long, 1024l>) const at copy.h:50:22
    frame #6: 0x00005555555554cc t.tmp.exe`void testN<std::__1::deque<int, std::__1::allocator<int>>>(int, int) [inlined] std::__1::pair<std::__1::__deque_iterator<int, int const*, int const&, int const* const*, long, 1024l>, std::__1::__deque_iterator<int, int*, int&, int**, long, 1024l>> std::__1::__unwrap_and_dispatch[abi:v16000]<std::__1::__overload<std::__1::__copy_loop<std::__1::_ClassicAlgPolicy>, std::__1::__copy_trivial>, std::__1::__deque_iterator<int, int const*, int const&, int const* const*, long, 1024l>, std::__1::__deque_iterator<int, int const*, int const&, int const* const*, long, 1024l>, std::__1::__deque_iterator<int, int*, int&, int**, long, 1024l>, 0>(__first=<unavailable>, __last=<unavailable>, __out_first=<unavailable>) at copy_move_common.h:81:19
    frame #7: 0x000055555555549e t.tmp.exe`void testN<std::__1::deque<int, std::__1::allocator<int>>>(int, int) [inlined] std::__1::pair<std::__1::__deque_iterator<int, int const*, int const&, int const* const*, long, 1024l>, std::__1::__deque_iterator<int, int*, int&, int**, long, 1024l>> std::__1::__dispatch_copy_or_move[abi:v16000]<std::__1::_ClassicAlgPolicy, std::__1::__copy_loop<std::__1::_ClassicAlgPolicy>, std::__1::__copy_trivial, std::__1::__deque_iterator<int, int const*, int const&, int const* const*, long, 1024l>, std::__1::__deque_iterator<int, int const*, int const&, int const* const*, long, 1024l>, std::__1::__deque_iterator<int, int*, int&, int**, long, 1024l>>(__first=<unavailable>, __last=<unavailable>, __out_first=<unavailable>) at copy_move_common.h:119:10
    frame #8: 0x000055555555549e t.tmp.exe`void testN<std::__1::deque<int, std::__1::allocator<int>>>(int, int) [inlined] std::__1::pair<std::__1::__deque_iterator<int, int const*, int const&, int const* const*, long, 1024l>, std::__1::__deque_iterator<int, int*, int&, int**, long, 1024l>> std::__1::__copy[abi:v16000]<std::__1::_ClassicAlgPolicy, std::__1::__deque_iterator<int, int const*, int const&, int const* const*, long, 1024l>, std::__1::__deque_iterator<int, int const*, int const&, int const* const*, long, 1024l>, std::__1::__deque_iterator<int, int*, int&, int**, long, 1024l>>(__first=<unavailable>, __last=<unavailable>, __result=<unavailable>) at copy.h:108:10
    frame #9: 0x000055555555549e t.tmp.exe`void testN<std::__1::deque<int, std::__1::allocator<int>>>(int, int) [inlined] std::__1::__deque_iterator<int, int*, int&, int**, long, 1024l> std::__1::copy[abi:v16000]<std::__1::__deque_iterator<int, int const*, int const&, int const* const*, long, 1024l>, std::__1::__deque_iterator<int, int*, int&, int**, long, 1024l>>(__first=<unavailable>, __last=<unavailable>, __result=<unavailable>) at copy.h:115:10
    frame #10: 0x000055555555549e t.tmp.exe`void testN<std::__1::deque<int, std::__1::allocator<int>>>(start=0, N=0) at copy.pass.cpp:56:5
    frame #11: 0x000055555555520d t.tmp.exe`main((null)=<unavailable>, (null)=<unavailable>) at copy.pass.cpp:77:13
    frame #12: 0x00007ffff7b2d20a libc.so.6`___lldb_unnamed_symbol3135 + 122
    frame #13: 0x00007ffff7b2d2bc libc.so.6`__libc_start_main + 124
    frame #14: 0x0000555555555121 t.tmp.exe`_start + 33

• reverse_iterator is no longer used in the implementation, which makes it significantly easier to understand and removes artificial types from backtraces. Using reverse_iterator has lead to at least one serious bug already.

AFAICT this was a language bug that will get fixed. When it's fixed I don't think we'd need an __unconstrained_reverse_iterator to forward using an iterator wrapper. Not that that helps us currently.

• unconstrainted_reverse_iterator can now be removed (which I intend to do in a follow-up), removing a lot of code duplication and complexity.

Do you already have that follow-up? I don't know how much extra complexity will result in removing __unconstrained_reverse_iterator.

• the test for whether the optimization is used only applied to std::copy and, more importantly, was essentially a no-op because it would still pass if the optimization was not used;
• there were no tests to make sure the optimization is not used when the effect would be visible.

I agree with you here. The tests are definitely a huge improvement. The only gripe I have with them is that they have UB, but I guess it would be a huge red flag if that wasn't the case.

Regarding the reverse_iterator optimization you mention, I think it was solution for a problem that the previous approach introduced and that is no longer applicable. The optimization was very limited in that it would only apply to the case where both the input and the output iterators were reverse iterators. I see no inherent reason why users would reverse both the input and the output sequence rather than just one of them, outside of the artificial case where our implementation itself would do the wrapping. If this optimization were to be restored, it would have to apply equally to input and output iterators. I don’t think, however, it would be pulling its weight.

This optimization was reported as a performance bug. See https://github.com/llvm/llvm-project/issues/33687. This was one of the reasons the overload was introduced. If we remove this optimization we should at least comment there that it was removed any why.

Just to be clear, I'm not against this change. I don't know which way to implement copy and friends is the right way, but I want to make sure we don't regress unexpectedly in some area.

Another thing to consider is that I think D132505 could implement the algorithm once instead of four times if we use the "forward with iterator wrappers" approach and adding specializations for the wrappers. D132505 is an improvement either way, so I'm not that concerned. I also haven't tried to implement the forwarding version, so take it with a grain of salt. Other suggestions to remove the duplicates are always appreciated!

libcxx/include/__algorithm/move.h

32

The contiguous_iterator concept guarantees that ranges::iter_move(a) has the same type, value category and effects as std::move(*a). AFAICT it would be UB to add an overload to std::move, so a specialized ranges::iter_move() that does anything else than casting to an rvalue would be UB.

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

24

It would break if <type_traits> would include copy for some reason. https://godbolt.org/z/P9Eq13ErY

[ldionne]

In D130695#3805381, @philnik wrote:

• unconstrainted_reverse_iterator can now be removed (which I intend to do in a follow-up), removing a lot of code duplication and complexity.

Do you already have that follow-up? I don't know how much extra complexity will result in removing __unconstrained_reverse_iterator.

We looked at it briefly and it didn't seem to incur much penalty. FWIW, I think removing the need for __unconstrained_reverse_iterator (and generally speaking the use of reverse_iterator as an implementation detail of low-level algorithms) is by far the most important motivation, at least for me.

[var-const]

It would definitely be nice if we could write it that simple. Unfortunately we can't currently.

I really hope we would be able to at some point. The code structure from this patch, while far from this ideal, can be transformed into this form in a straightforward way.

By the way, are there any C++11-and-later features that you feel would *really* make a difference if they were available in C++03? I gave it some thought, and if constexpr seemed to be number one (and number 2 would be auto and decltype(auto) as the return type of a function).

That would also be the case if we forward to std::copy though, right?

Not really. The code structure in this patch is basically:

std::copy          -> <memmove>
std::copy_backward -> <memmove>
std::move          -> <memmove>
std::move_backward -> <memmove>

All implementations are independent of each other, can be read in isolation, and are symmetrical. If I know how copy is implemented, I pretty much know how the other 3 are implemented as well.

With forwarding, the structure is

std::copy                                  -> <memmove>
std::copy_backward -> std::copy            -> <memmove>
std::move          -> std::copy            -> <memmove>
std::move_backward -> std::copy (or move?) -> <memmove>

It is inherently more complicated. Now knowing the implementation of copy doesn't tell me anything about the implementation of copy_backward. And move, IIUC, is even worse because it *sometimes* uses its own implementation and *sometimes* forwards to copy. This is even ignoring the issue of reverse iterators for the moment.

I'm not sure this is actually simpler to debug. I haven't checked the current backtrace, so maybe it's worse, but here is one similar to what I encountered while working on D132505:

I ran a simple test. The current state is:

* thread #1, queue = 'com.apple.main-thread', stop reason = EXC_BAD_ACCESS (code=1, address=0x0)
  * frame #0: 0x00000001000020ad t.tmp.exe`std::__1::pair<std::__1::__unconstrained_reverse_iterator<std::__1::__list_iterator<int, void*> >, std::__1::__unconstrained_reverse_iterator<int*> > std::__1::__copy_impl[abi:v16000]<std::__1::__unconstrained_reverse_iterator<std::__1::__list_iterator<int, void*> >, std::__1::__unconstrained_reverse_iterator<std::__1::__list_iterator<int, void*> >, std::__1::__unconstrained_reverse_iterator<int*> >(__first=__unconstrained_reverse_iterator<std::__1::__list_iterator<int, void *> > @ 0x00007ff7bfefeed8, __last=__unconstrained_reverse_iterator<std::__1::__list_iterator<int, void *> > @ 0x00007ff7bfefeed0, __result=__unconstrained_reverse_iterator<int *> @ 0x00007ff7bfefeec8) at copy.h:39:6
    frame #1: 0x0000000100001e80 t.tmp.exe`std::__1::pair<std::__1::__unconstrained_reverse_iterator<std::__1::__list_iterator<int, void*> >, std::__1::__unconstrained_reverse_iterator<int*> > std::__1::__copy[abi:v16000]<std::__1::__unconstrained_reverse_iterator<std::__1::__list_iterator<int, void*> >, std::__1::__unconstrained_reverse_iterator<std::__1::__list_iterator<int, void*> >, std::__1::__unconstrained_reverse_iterator<int*>, 0>(__first=__unconstrained_reverse_iterator<std::__1::__list_iterator<int, void *> > @ 0x00007ff7bfefef98, __last=__unconstrained_reverse_iterator<std::__1::__list_iterator<int, void *> > @ 0x00007ff7bfefef90, __result=__unconstrained_reverse_iterator<int *> @ 0x00007ff7bfefef88) at copy.h:96:18
    frame #2: 0x0000000100001d9f t.tmp.exe`std::__1::pair<std::__1::__list_iterator<int, void*>, int*> std::__1::__copy_backward[abi:v16000]<std::__1::_ClassicAlgPolicy, std::__1::__list_iterator<int, void*>, int*, 0>(__first=__list_iterator<int, void *> @ 0x00007ff7bfeff028, __last=__list_iterator<int, void *> @ 0x00007ff7bfeff020, __result=0x00007ff7bfeff0e0) at copy_backward.h:36:16
    frame #3: 0x0000000100001b95 t.tmp.exe`int* std::__1::copy_backward[abi:v16000]<std::__1::__list_iterator<int, void*>, int*>(__first=__list_iterator<int, void *> @ 0x00007ff7bfeff088, __last=__list_iterator<int, void *> @ 0x00007ff7bfeff080, __result=0x00007ff7bfeff0e0) at copy_backward.h:57:10
    frame #4: 0x0000000100001ac9 t.tmp.exe`foo() at copy.pass.cpp:93:3
    frame #5: 0x0000000100001c6b t.tmp.exe`main((null)=1, (null)=0x00007ff7bfeff280) at copy.pass.cpp:102:3
    frame #6: 0x00000001000454fe dyld`start + 462

With this patch it becomes

* thread #1, queue = 'com.apple.main-thread', stop reason = EXC_BAD_ACCESS (code=1, address=0x0)
  * frame #0: 0x0000000100003b31 t.tmp.exe`std::__1::pair<std::__1::__list_iterator<int, void*>, int*> std::__1::__copy_backward_loop<std::__1::_ClassicAlgPolicy>::operator(this=0x00007ff7bfefef40, __first=__list_iterator<int, void *> @ 0x00007ff7bfefeec8, __last=__list_iterator<int, void *> @ 0x00007ff7bfefeec0, __result=0x00007ff7bfeff0c8)[abi:v16000]<std::__1::__list_iterator<int, void*>, std::__1::__list_iterator<int, void*>, int*>(std::__1::__list_iterator<int, void*>, std::__1::__list_iterator<int, void*>, int*) const at copy_backward.h:36:8
    frame #1: 0x000000010000398f t.tmp.exe`std::__1::pair<std::__1::__list_iterator<int, void*>, int*> std::__1::__unwrap_and_dispatch[abi:v16000]<std::__1::__overload<std::__1::__copy_backward_loop<std::__1::_ClassicAlgPolicy>, std::__1::__copy_backward_trivial>, std::__1::__list_iterator<int, void*>, std::__1::__list_iterator<int, void*>, int*, 0>(__first=__list_iterator<int, void *> @ 0x00007ff7bfefef88, __last=__list_iterator<int, void *> @ 0x00007ff7bfefef80, __out_first=0x00007ff7bfeff0e0) at copy_move_common.h:81:19
    frame #2: 0x00000001000038dd t.tmp.exe`std::__1::pair<std::__1::__list_iterator<int, void*>, int*> std::__1::__dispatch_copy_or_move[abi:v16000]<std::__1::_ClassicAlgPolicy, std::__1::__copy_backward_loop<std::__1::_ClassicAlgPolicy>, std::__1::__copy_backward_trivial, std::__1::__list_iterator<int, void*>, std::__1::__list_iterator<int, void*>, int*>(__first=__list_iterator<int, void *> @ 0x00007ff7bfefefd8, __last=__list_iterator<int, void *> @ 0x00007ff7bfefefd0, __out_first=0x00007ff7bfeff0e0) at copy_move_common.h:119:10
    frame #3: 0x000000010000384d t.tmp.exe`std::__1::pair<std::__1::__list_iterator<int, void*>, int*> std::__1::__copy_backward[abi:v16000]<std::__1::_ClassicAlgPolicy, std::__1::__list_iterator<int, void*>, std::__1::__list_iterator<int, void*>, int*>(__first=__list_iterator<int, void *> @ 0x00007ff7bfeff028, __last=__list_iterator<int, void *> @ 0x00007ff7bfeff020, __result=0x00007ff7bfeff0e0) at copy_backward.h:55:10
    frame #4: 0x000000010000365d t.tmp.exe`int* std::__1::copy_backward[abi:v16000]<std::__1::__list_iterator<int, void*>, int*>(__first=__list_iterator<int, void *> @ 0x00007ff7bfeff088, __last=__list_iterator<int, void *> @ 0x00007ff7bfeff080, __result=0x00007ff7bfeff0e0) at copy_backward.h:68:10
    frame #5: 0x0000000100003579 t.tmp.exe`foo() at copy.pass.cpp:93:3
    frame #6: 0x000000010000372b t.tmp.exe`main((null)=1, (null)=0x00007ff7bfeff280) at copy.pass.cpp:102:3
    frame #7: 0x000000010004d4fe dyld`start + 462

I find the types way more readable now that they are no longer wrapped in __unconstrained_reverse_iterator.

AFAICT this was a language bug that will get fixed.

I mean the wrong return value for ranges::{copy,move}_backward (see D130968). We even had wrong tests for those (i.e., the tests were testing for the *wrong* value). This sort of confusion of whether we are talking about the begin/end of the actual range or the reversed range is inherent when using reverse iterators. I take it as empirical evidence that using reverse iterators in the implementation adds complexity and potential to introduce bugs.

Do you already have that follow-up? I don't know how much extra complexity will result in removing __unconstrained_reverse_iterator.

Not yet. The change amounts to a couple additional functions in inplace_merge.

This optimization was reported as a performance bug. See https://github.com/llvm/llvm-project/issues/33687. This was one of the reasons the overload was introduced. If we remove this optimization we should at least comment there that it was removed any why.

Reading the original issue, I'm not convinced we should fix this at all. Unfortunately, it doesn't really explain the actual problem the issue author had, which would be the most important part. As for open source examples, it seems that the vector::insert function could easily use copy_backward instead of copying with reverse iterators, and ToolbarActionBar::GetActions() doesn't seem like the kind of function where this kind of microoptimization could ever matter. Addressing this issue is not just a matter of putting in the effort. We are paying real costs for the added complexity, and by extension so are our users (when we introduce a bug, for example) -- and note that this applies to pretty much *all* of our users, whereas the optimization would benefit only a certain subset. I can certainly be convinced otherwise by some concrete, real-world examples.

In any case, if we do this optimization at all, it should apply equally to the input and the output sequence. If that is too complicated to implement, I'll take it as further evidence that this optimization doesn't justify the added cost.

Just to be clear, I'm not against this change. I don't know which way to implement copy and friends is the right way, but I want to make sure we don't regress unexpectedly in some area.

It sounds like we can agree that if constexpr would be the best way if it were feasible. I really hope it becomes feasible at some point in the future.

Another thing to consider is that I think D132505 could implement the algorithm once instead of four times if we use the "forward with iterator wrappers" approach and adding specializations for the wrappers. D132505 is an improvement either way, so I'm not that concerned. I also haven't tried to implement the forwarding version, so take it with a grain of salt. Other suggestions to remove the duplicates are always appreciated!

I don't particularly like this sort of decorator pattern, although it can definitely be the lesser of two evils (for D132505, it's likely justified, though I haven't looked closely yet).

libcxx/include/__algorithm/move.h

32

@philnik Thanks a lot for digging this up! Looks like we don't have to do anything (thankfully, because it would complicate the logic quite a bit).

[var-const]

Feedback.

[philnik]

By the way, are there any C++11-and-later features that you feel would *really* make a difference if they were available in C++03? I gave it some thought, and if constexpr seemed to be number one (and number 2 would be auto and decltype(auto) as the return type of a function).

Other than concepts (would probably a bit too much to ask), lambdas would definitely be my number one. It would just be so much nicer to use algorithms instead of raw loops everywhere. C++11 attributes would also be quite nice.

AFAICT this was a language bug that will get fixed.

I mean the wrong return value for ranges::{copy,move}_backward (see D130968). We even had wrong tests for those (i.e., the tests were testing for the *wrong* value). This sort of confusion of whether we are talking about the begin/end of the actual range or the reversed range is inherent when using reverse iterators. I take it as empirical evidence that using reverse iterators in the implementation adds complexity and potential to introduce bugs.

Yeah, I don't think this was because of reverse_iterators. My intuition about what {copy, move}_backward should return is just backwards.

[var-const]

Fix the CI.

[var-const]

Fix the CI.

[var-const]

Fix the CI.

[var-const]

Fix the CI.

[var-const]

Rebase

[var-const]

Fix the CI.

[mstorsjo]

I suspect issues in this commit. If Clang is built on top of libc++ with this change in, Clang misbehaves (produces incorrect behaviour and then crashes) - I have bisected the issue down to this exact commit.

I don't know exactly what/why etc yet.

[mstorsjo]

In D130695#3829567, @mstorsjo wrote:

I suspect issues in this commit. If Clang is built on top of libc++ with this change in, Clang misbehaves (produces incorrect behaviour and then crashes) - I have bisected the issue down to this exact commit.

I don't know exactly what/why etc yet.

I don't think I'll be able to spend time on figuring out exactly what this patch breaks, but to reproduce the issue:

1. Build libc++
2. Build clang using the libc++ from 1. as standard C++ library
3. Use clang from 2. to build a trivial C++ application

The test application I've tried to build in step 3 is https://github.com/mstorsjo/llvm-mingw/blob/master/test/hello-cpp.cpp, with a trivial compilation command like i686-w64-mingw32-clang++ hello-cpp.cpp -o i686/hello-cpp.exe. When building this trivial C++ example, Clang incorrectly produces these diagnostics:

In file included from hello-cpp.cpp:19:
In file included from D:/a/_temp/msys64/llvm-mingw/include/c++/v1/iostream:43:
In file included from D:/a/_temp/msys64/llvm-mingw/include/c++/v1/ios:221:
In file included from D:/a/_temp/msys64/llvm-mingw/include/c++/v1/__locale:15:
In file included from D:/a/_temp/msys64/llvm-mingw/include/c++/v1/__memory/shared_ptr.h:22:
In file included from D:/a/_temp/msys64/llvm-mingw/include/c++/v1/__memory/allocation_guard.h:14:
In file included from D:/a/_temp/msys64/llvm-mingw/include/c++/v1/__memory/allocator_traits.h:14:
In file included from D:/a/_temp/msys64/llvm-mingw/include/c++/v1/__memory/construct_at.h:20:
D:/a/_temp/msys64/llvm-mingw/include/c++/v1/new:285:12: error: no matching function for call to '__libcpp_operator_new'
    return __libcpp_operator_new(__size, __align_val);
           ^~~~~~~~~~~~~~~~~~~~~
D:/a/_temp/msys64/llvm-mingw/include/c++/v1/new:262:7: note: candidate template ignored: substitution failure: deduced incomplete pack <size_t, (no value)> for template parameter '_Args'
void* __libcpp_operator_new(_Args ...__args) {
      ^
D:/a/_temp/msys64/llvm-mingw/include/c++/v1/new:326:14: error: no matching function for call to '__libcpp_operator_delete'
      return __libcpp_operator_delete(__ptr, __align_val);
             ^~~~~~~~~~~~~~~~~~~~~~~~
D:/a/_temp/msys64/llvm-mingw/include/c++/v1/new:272:6: note: candidate template ignored: substitution failure: deduced incomplete pack <void *, (no value)> for template parameter '_Args'
void __libcpp_operator_delete(_Args ...__args) {
     ^

And after that, Clang crashes. See https://github.com/mstorsjo/llvm-mingw/actions/runs/3166862572/jobs/5158428014 for the issue in action.

Note that while this could look like an issue in the libc++ headers that Clang is including here, the same issue does not appear when Clang is built on top of a preexisting libstdc++ or older libc++.

I haven't tested, but would presume that the same issue appears when Clang targets other OSes too.

[var-const]

@mstorsjo Thank you for the report! The patch has been reverted by @vitalybuka. The reverting commit links to some sanitizer findings which are hopefully related to the Clang breakage you were seeing. I'll investigate.

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

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_t< is_trivially_assignable<_Out&, _In&>::value, int > = 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_t< is_trivially_assignable<_Out&, _In&>::value, int > = 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/enable_if.h>
+#include <__type_traits/integral_constant.h>
+#include <__type_traits/is_constant_evaluated.h>
+#include <__type_traits/is_copy_constructible.h>
+#include <__type_traits/is_trivially_assignable.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
+
+// `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 _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
+  using _InValue = typename _IterOps<_AlgPolicy>::template __value_type<_InIter>;
+  // In Clang, `__builtin_memmove` only supports fully trivially copyable types (just having trivial copy assignment is
+  // insufficient).
+  if (__libcpp_is_constant_evaluated() && !is_trivially_copyable<_InValue>::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_t< is_trivially_assignable<_Out&, _In&&>::value, int > = 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_t< is_trivially_assignable<_Out&, _In&&>::value, int > = 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) {
   typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
-  return std::__set_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp).second;
+  return std::__set_difference<_ClassicAlgPolicy, _Comp_ref>(
+      __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) {
   typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
-  return std::__set_symmetric_difference<_Comp_ref>(
+  return std::__set_symmetric_difference<_ClassicAlgPolicy, _Comp_ref>(
              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) {
   typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
-  return std::__set_union<_Comp_ref>(
+  return std::__set_union<_ClassicAlgPolicy, _Comp_ref>(
              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/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" }

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>
+
+// These tests checks that `std::copy` and `std::move` (including their variations like `copy_n`) don't forward to
+// `std::memmove` when doing so would be observable.
+
+#include <algorithm>
+#include <cassert>
+#include <iterator>
+#include <ranges>
+#include <type_traits>
+
+#include "test_iterators.h"
+#include "test_macros.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*>>>);
+
+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>);
+
+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>);
+
+// Unwrapping the iterator inside `std::copy` and similar algorithms relies on `to_address`. If the `memmove`
+// optimization is used, the result of the call to `to_address` will be passed to `memmove`. This test deliberately
+// specializes `to_address` for `contiguous_iterator` to return a type that doesn't implicitly convert to `void*`, so
+// that a call to `memmove` would fail to compile.
+template <>
+struct std::pointer_traits<::contiguous_iterator<NonTrivialCopyAssignment*>> {
+  static constexpr ::contiguous_iterator<NonTrivialCopyAssignment*>
+  to_address(const ::contiguous_iterator<NonTrivialCopyAssignment*>& iter) {
+    return iter;
+  }
+};
+template <>
+struct std::pointer_traits<::contiguous_iterator<NonTrivialMoveAssignment*>> {
+  static constexpr ::contiguous_iterator<NonTrivialMoveAssignment*>
+  to_address(const ::contiguous_iterator<NonTrivialMoveAssignment*>& iter) {
+    return iter;
+  }
+};
+
+template <class InIter, template <class> class SentWrapper, class OutIter, size_t W1, size_t W2, class Func>
+constexpr void test_one(Func func) {
+  using Value = typename std::iterator_traits<InIter>::value_type;
+
+  {
+    const size_t N = 4;
+
+    Value input[N] = {Value{1}, {2}, {3}, {4}};
+    Value 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 size_t N = 0;
+
+    Value input[1]  = {1};
+    Value output[1] = {2};
+
+    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(output[0] == Value(2));
+  }
+}
+
+template <class InIter, template <class> class SentWrapper, class OutIter, size_t W1, size_t W2>
+constexpr void test_copy() {
+  // 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);
+    });
+  }
+
+  // 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);
+  });
+}
+
+template <class InIter, template <class> class SentWrapper, class OutIter, size_t W1, size_t W2>
+constexpr void test_move() {
+  if constexpr (std::same_as<InIter, SentWrapper<InIter>>) {
+    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::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 <class T, size_t W1, size_t W2>
+constexpr void test_copy_with_type() {
+  using CopyIter = contiguous_iterator<T*>;
+
+  test_copy<CopyIter, std::type_identity_t, CopyIter, W1, W2>();
+  test_copy<CopyIter, sized_sentinel, CopyIter, W1, W2>();
+  test_copy<CopyIter, std::type_identity_t, T*, W1, W2>();
+  test_copy<T*, std::type_identity_t, CopyIter, W1, W2>();
+}
+
+template <class T, size_t W1, size_t W2>
+constexpr void test_move_with_type() {
+  using MoveIter = contiguous_iterator<T*>;
+
+  test_move<MoveIter, std::type_identity_t, MoveIter, W1, W2>();
+  test_move<MoveIter, sized_sentinel, MoveIter, W1, W2>();
+  test_move<MoveIter, std::type_identity_t, T*, W1, W2>();
+  test_move<T*, std::type_identity_t, MoveIter, W1, W2>();
+}
+
+template <size_t W1, size_t W2>
+constexpr void test_copy_and_move() {
+  test_copy_with_type<NonTrivialCopyAssignment, W1, W2>();
+  test_copy_with_type<NonTrivialCopyCtr, W1, W2>();
+
+  test_move_with_type<NonTrivialMoveAssignment, W1, W2>();
+  test_move_with_type<NonTrivialMoveCtr, W1, W2>();
+}
+
+constexpr bool test() {
+  test_copy_and_move<0, 0>();
+  test_copy_and_move<0, 2>();
+  test_copy_and_move<2, 0>();
+  test_copy_and_move<2, 2>();
+  test_copy_and_move<2, 4>();
+  test_copy_and_move<4, 4>();
+
+  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
+
+// <algorithm>
+
+// These tests checks 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 overload is a better match than the actual `builtin_memmove`, so it should hijack the call inside `std::copy`
+// and similar algorithms.
+void* __builtin_memmove(Foo* dst, Foo* src, size_t count) {
+  memmove_called = true;
+  return __builtin_memmove(static_cast<void*>(dst), static_cast<void*>(src), count);
+}
+
+#include <algorithm>
+#include <cassert>
+#include <iterator>
+#include <ranges>
+#include <type_traits>
+
+#include "test_iterators.h"
+
+static_assert(std::is_trivially_copyable_v<Foo>);
+
+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>
+void test_one(Func func) {
+  {
+    const size_t N = 4;
+
+    Foo input[N] = {{1}, {2}, {3}, {4}};
+    Foo 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));
+
+    assert(!memmove_called);
+    func(in, sent, out, N);
+
+    assert(std::equal(input, input + N, output));
+    assert(memmove_called);
+    memmove_called = false;
+  }
+
+  {
+    const size_t N = 0;
+
+    Foo input[1]  = {1};
+    Foo output[1] = {2};
+
+    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));
+
+    assert(!memmove_called);
+    func(in, sent, out, N);
+
+    assert(output[0] == 2);
+    assert(memmove_called);
+    memmove_called = false;
+  }
+}
+
+template <class InIter, template <class> class SentWrapper, class OutIter, size_t W1, size_t W2>
+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 <class InIter, template <class> class SentWrapper, class OutIter>
+void test_all_permutations_with_initer_sent_outiter() {
+  test_copy_and_move<InIter, SentWrapper, OutIter, 0, 0>();
+  test_copy_and_move<InIter, SentWrapper, OutIter, 0, 2>();
+  test_copy_and_move<InIter, SentWrapper, OutIter, 2, 0>();
+  test_copy_and_move<InIter, SentWrapper, OutIter, 2, 2>();
+  test_copy_and_move<InIter, SentWrapper, OutIter, 2, 4>();
+  test_copy_and_move<InIter, SentWrapper, OutIter, 4, 4>();
+}
+
+template <class InIter, template <class> class SentWrapper>
+void test_all_permutations_with_initer_sent() {
+  test_all_permutations_with_initer_sent_outiter<InIter, SentWrapper, Foo*>();
+  test_all_permutations_with_initer_sent_outiter<InIter, SentWrapper, contiguous_iterator<Foo*>>();
+}
+
+template <class InIter>
+void test_all_permutations_with_initer() {
+  test_all_permutations_with_initer_sent<InIter, std::type_identity_t>();
+  test_all_permutations_with_initer_sent<InIter, sized_sentinel>();
+}
+
+void test() {
+  test_all_permutations_with_initer<Foo*>();
+  test_all_permutations_with_initer<contiguous_iterator<Foo*>>();
+}
+
+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/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/std/algorithms/alg.modifying.operations/alg.copy/ranges.copy.pass.cpp

 
 template <class Out>
 constexpr void test_in_iterators() {
   test_iterators<cpp20_input_iterator<int*>, Out, sentinel_wrapper<cpp20_input_iterator<int*>>>();
   test_sentinels<forward_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<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>();
   test_iterators<ProxyIterator<contiguous_iterator<int*>>, Out>();
 }
 
 constexpr bool test() {
   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 ranges::dangling is returned

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

constexpr void test_iterators() {
     }
   }
 }
 
 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_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

 //===----------------------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 // <algorithm>

 
 template <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};
test_proxy_in_iterators<ProxyIterator<contiguous_iterator<int*>>>();
     assert((out == std::array{1, 2, 3, 4}));
   }
 
   { // check that an iterator is returned with a borrowing range
     std::array in {1, 2, 3, 4};
     std::array<int, 4> out;
     std::same_as<std::ranges::in_out_result<int*, int*>> auto ret =
         std::ranges::move_backward(std::views::all(in), out.data() + out.size());
     assert(ret.in == in.data() + in.size());
     assert(ret.out == out.data());
     assert(in == out);
   }
 
   { // check that every element is moved exactly once
     struct MoveOnce {
       bool moved = false;
       constexpr MoveOnce() = default;