[libc++][ranges] Make range algorithms support proxy iterators

[var-const]

Summary

Also test all the range algorithms to verify the support.

[var-const]

Updae

[var-const]

Rebase, remove unnecessary changes.

[var-const]

Remove unused variables.

[var-const]

libcxx/include/__algorithm/copy_backward.h

31

@philnik I think this was a bug; it wasn't caught because copy_backward tests never try the case where the sentinel isn't the same type as the iterator. This fix is enough to make robust_against_proxy_iterators pass; however, if I change test_iterators in copy_backward test to define class Sent as = sentinel_wrapper<In>, I get more breakages. Could you please look into this?

libcxx/include/__algorithm/inplace_merge.h

2

These changes are simple but very intrusive. The vast majority is replacing unqualified calls to swap with _IterOps<_AlgPolicy>::iter_swap, and calls to *i1 = std::move(*i2) with _IterOps<_AlgPolicy>::__iter_move(i2).

libcxx/include/__algorithm/iterator_operations.h

50

Should this be moved to a different file? Or perhaps this file should be renamed from iterator_operations.h to something more generic?

libcxx/include/__algorithm/ranges_fill.h

33

@philnik I think this was a bug -- please let me know if I'm missing something, or if you would prefer a different fix.

libcxx/include/__algorithm/sort.h

226

This is one case where the difference between ranges and classic versions isn't confined to iterator operations (but stable_sort would require a similar call to rotate).

libcxx/src/algorithm.cpp

16

@ldionne This gives me some concern. Do these changes look reasonable to you? If yes, should we also add specializations for _RangeAlgPolicy?

libcxx/test/std/algorithms/ranges_robust_against_proxy_iterators.compile.pass.cpp

152

Uninitialized memory algorithms don't work with ProxyIterator because it doesn't satisfy nothrow-input-iterator that requires the result of dereferencing the iterator to be the same as iter_reference_t. I'm not sure if it's possible to write a different valid proxy iterator that would satisfy that constraint but still require special handling in the implementation. @huixie90 What do you think?

[philnik]

libcxx/include/__algorithm/copy_backward.h

31

Since D128864 fixes this properly I would prefer if you revert the changes here and I enable the additional tests over there instead.

libcxx/include/__algorithm/inplace_merge.h

62

Why are you adding an alias here? It doesn't look like much of a benefit for two calls. Ditto for a lot of other places.

libcxx/include/__algorithm/iterator_operations.h

50

I'm already not very happy that we pull all the iterator operations in. We should avoid pulling whole algorithms in. Instead, I think the better option would be to rewrite min_element to support ranges like that:

template <class _Iter, class _Sent, class _Proj, class _Comp>
_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
_Iter __min_element(_Iter __first, _Sent __last, _Comp& __comp, _Proj& __proj) {
  if (__first == __last)
    return __first;

  _Iter __i = __first;
  while (++__i != __last)
    if (std::__invoke(__comp, std::__invoke(__proj, *__i), std::__invoke(__proj, *__first)))
      __first = __i;
  return __first;
}

template <class _ForwardIterator, class _Compare>
_LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 _ForwardIterator
min_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
{
  static_assert(__is_callable<_Compare, decltype(*__first), decltype(*__first)>::value,
              "The comparator has to be callable");
  auto __proj = __identity();
  return std::__min_element(__first, __last, __comp, __proj);
}

and update libcxx/algorithms/callable.verify.cpp.

libcxx/include/__algorithm/sort.h

142

Shouldn't this be is_same<decltype(*declval<_Iter>()), _Tp&>::value? Otherwise this would disable the optimization for (almost) all iterators, especially raw pointers. Also, could you qualify declval? While it's not strictly necessary it makes error messages a lot better.

226

As I already said above, I think the better alternative is to make __min_element work with both classic and ranges iterators.

libcxx/src/algorithm.cpp

16

I'm quite certain that this is an ABI break, since template parameters are mangled. I think you have to revert these changes and add a __sort_policy or something like that as a dispatch function. Regarding _RangeAlgPolicy I think we should wait a few releases and try things out in the unstable ABI before effectively killing the possibility of changing the ABI in any way (assuming we want to do that at all).

libcxx/test/std/algorithms/ranges_robust_against_proxy_iterators.compile.pass.cpp

1

IIUC some types of problems are only obvious when looking at the output of the algorithms, so I think it's not enough to ensure that the algorithms can be instantiated.

[huixie90]

libcxx/include/__algorithm/inplace_merge.h

68

should this call std::ranges::move for ranges policy? or Algs<_AlgPolicy>::move if that exists?

185

I guess we want to __rotate<AlgPolicy> when it exists , perhaps add a todo here?

202

while you are here, perhaps consider remove these stale comments?

libcxx/include/__algorithm/make_heap.h

28

we have two different patterns for these __ functions.

1. the __last has a different template parameter type. and the __ calls next to get the last iterator. the ranges counter part directly call it.
2. the __last has the same type and the ranges counter-part calls next then call into __ function.

The problem is that when these two patterns co-exists, let's say __a takes two different types, and __b takes the same type. If __a needs to call __b, it could fail because __b expecting the same type.

I think we should make all algorithms consistent.

libcxx/include/__algorithm/sort.h

142–166

I think you don't need to guard the is_same<decltype(*declval<_Iter>()), _Tp>::value

The algorithm is correct for proxy iterator, because of the correct use of value_type.
https://godbolt.org/z/c5Mh7aGxT

It'd only be would be wrong if it is using auto
https://godbolt.org/z/8xqzhPhve

Proxy Iterator needs to define value_type in the correct way to make these swap patterns work.

Normally these swap patterns need to be combined with iter_move (the triple-move swap), but here we are dealing with is_arithmetic types so moves are just copies

337–340

nit: here we know that __i2 is a pointer so std::move(*__it2) is actually ok? (to be confirmed)

560–596

hmm

libcxx/src/algorithm.cpp

18–52

Can we introduce some new names like __sort_with_al_policy, which is the common sharable code between classic and ranges, and we keep __sort only for classic algorithm which calls the __sort_with_al_policy with classic policy so that these symbols are stable and have the same behaviour

libcxx/test/std/algorithms/ranges_robust_against_proxy_iterators.compile.pass.cpp

14

It is great to have a test for iter_swap. But this test won't cover the iter_move. If an algorithm doesn't use iter_move but use std::move(*it), it would still compile (for copyable types) because value_type x = std::move(*it) would probably ends with copies.

For algorithms that do move stuff, we should probably test them with proxy iterator of move only types so that it will catch incorrect use of std::move

28–45

these tests are great and they can catch some problems immediately. and thanks for adding them.

However, since these tests don't actually verify the results of the algorithms, I think we should add additional tests in individual tests in the case-by-case manner.

For example, for sorting, we can test given a vector<int>, we can create a ProxyRange, sort the ProxyRange and verify the original vector is sorted

152

The nothrow-xxx-iterator explicitly requires std::same_as<std::remove_cvref_t<std::iter_reference_t<I>>, std::iter_value_t<I>>, which basically means value_type& == reference, which rules out all the proxy iterators. It makes sense for writing to uninitialized memory because we do need the address of *it to be something that we can write to (not the proxies). So for most uninitialized algorithms, they are designed not to work with proxies. So we can't test them.

However, there are two exceptions. for uninitialized_copy and uninitialized_move, the inputs and outputs are separate. So in theory the inputs can be ProxyRange and the outputs can be a simple array which does model nothrow-xxx-iterator

libcxx/test/support/test_iterators.h

881–882

hmm. the two overloads above should already cover this. see the test
https://github.com/llvm/llvm-project/blob/8922adf646eead207fb367dace80bba2abfab2ad/libcxx/test/support/test.support/test_proxy.pass.cpp#L63

or did I missing something?

895–896

thanks for adding this.
optional: consider add small test here as it gets more complicated now
test/support/test.support/test_proxy.pass.cpp

[var-const]

Address feedback:

• in sort.h, attach _AlgPolicy to the _Comp template argument for the functions where adding a new template parameter would break the ABI;
• run the test;
• other fixes.

Also fix the CI.

[var-const]

Different branch.

[var-const]

Rebase on main.

libcxx/include/__algorithm/copy_backward.h

31

Sure, reverted this (also commented out copy_backward in the robust test file and added a TODO).

libcxx/include/__algorithm/inplace_merge.h

62

Removed from here and elsewhere. If there are other places you'd like to change, please let me know.

68

Very good point, I thought about this. Added a TODO for now.

202

I'd rather not add unrelated changes to this patch -- it's already quite large.

libcxx/include/__algorithm/iterator_operations.h

50

Discussed offline. I slightly prefer the current approach, but not enough to spend too much time discussing this. Went with the approach you suggested.

libcxx/include/__algorithm/make_heap.h

28

This should be caught by testing, so I don't think it should cause any runtime issues, but it can definitely be confusing when reading the code. However, sometimes it reflects the nature of the algorithm -- for some algorithms it is essential that __last is a random-access or bidirectional iterator, and for those it makes sense to reflect that in the signature. For others, __last is only ever used to serve as a guard, so they can trivially support sentinels. Perhaps using different names rather than __last having two meanings would make this a little more readable?

libcxx/include/__algorithm/sort.h

142

Thanks a lot for catching this, it's a very unfortunate typo. I removed this condition altogether thanks to @huixie90's analysis below.

142–166

Thanks a lot for doing this analysis! This really makes things much simpler. I added a brief comment to the function as well.

337–340

This is a very good observation, thanks!

560–596

This is reverted now due to @philnik's comment (it breaks the ABI).

libcxx/src/algorithm.cpp

16

Thanks a lot for calling out the ABI break, I was concerned about that and it makes sense. There's no choice but to revert this change to the template instantiation and come up with a different approach.

For the different approach, I would strongly prefer to avoid:

• bloating the binary;
• duplicating internal sorting functions for ranges and non-ranges (maintenance hazard).

We discussed this offline, and you suggested (IIUC -- feel free to correct my summary) essentially to rename the functions that are being explicitly instantiated, then add one-liner functions with the old instantiated names that just forward arguments to the renamed functions. IIUC, inlining would make sure both the forwarding function _and_ the actual implementation function end up in the dylib, even though only the forwarding function is being instantiated. This sounds like a good approach, but I'm _really_ concerned about fiddling with the ABI so close to the branch cut. It would also take me a while to verify that this works correctly (i.e., no or negligible binary bloat, implementation functions are actually in the dylib).

With that in mind, I decided to go with a different approach. It might be suboptimal long-term, but it's easy to implement and shouldn't affect the ABI at all. I want to land this patch ASAP because the intrusive changes to sort and heap algorithms affect a few of the unimplemented ranges patches. As long as this patch makes things better and doesn't prevent us from using a different approach later, I think it should be good to land.

What I did was to keep the same number of template arguments in __sort, __sort5, and __insertion_sort_incomplete (the ones being explicitly instantiated) and attach the policy tag to the comparator instead. The way it works is:

• when invoked via the range algorithm, wrap the comparator inside a simple struct that holds a reference to the comparator and defines two nested typedefs, one for the policy and one for the comparator type;
• when invoked via the classic algorithm, just pass the pristine comparator like before. When unwrapping the comparator, the lack of a nested typedef for the policy is taken to mean _ClassicAlgPolicy.

It's certainly complicated and not pretty, but I think it solves the proxy iterator problem, shouldn't cause any performance regressions and leaves the door open for changing this in the future. What do you think?

18–52

So far I went with wrapping the policy tag, which seems to be the least verbose and least intrusive change (at the cost of some complexity). See one of my comments above in a thread started by @philnik for a bit more context. Please let me know what you think.

libcxx/test/std/algorithms/ranges_robust_against_proxy_iterators.compile.pass.cpp

1

I have somewhat mixed feelings about this. In short, I feel that the Pareto principle applies and this test would catch, say, 80% of the issues for 20% of the effort -- I expect that compilation issues are a lot more likely than subtle incorrect behavior.

I would be against adding specific test cases for proxy iterators across all algorithms. However, I think we have algorithms where ProxyIterator is simply added as one more iterator type to instantiate a test_iterators function, which I think is great and should offer sufficient testing. But even with that, I still feel this test file has value because it's compact. It's easy to maintain and extend (for example, adding another proxy iterator type to this file is way easier than going across all the ~100 algorithm test files). It's also way easier to verify that every relevant algorithm is tested in this file rather than going through all of our algorithm tests. I think those upsides outweigh the incomplete coverage.

I changed this to be a runtime test, but I don't want to block this patch on adding checks for the output -- I think it improves our test coverage even without those checks which we can add in a follow-up.

14

This is a great point and actually something I thought about -- we should probably test _all_ customization points. I'd prefer to do this in a follow-up, though -- I think this patch is already quite big and it makes the coverage strictly better even if it doesn't achieve one hundred percent coverage. Does that sound reasonable to you? To be clear, I plan to do the follow-up immediately after landing this. I want to land this patch ASAP because the changes to sort.h and friends are going to cause a lot of merge conflicts for the not-yet-implemented algorithms (e.g. inplace_merge).

By the way, do you think we should try to add all checks to the same ProxyIterator class or create a separate test iterator (and sentinel and range) for each customization point?

28–45

Please see my other comment above -- in short, I think it would be great to add ProxyIterator as one of the iterator types that instantiate test_iterators across our algorithms. I wouldn't add specific test cases, though, because I don't think those can be maintained well across all the ~100 algorithms. In either case, this is something that I feel should be done in a follow-up.

152

Thanks a lot for looking into this! It's very helpful. It seems that the following constraint:

requires constructible_from<iter_value_t<_OutputIterator>, iter_reference_t<_InputIterator>>

also prevents proxy iterators from being used with uninitialized_{copy,move}?

libcxx/test/support/test_iterators.h

881–882

I don't want to spend too much time investigating this just because of the deadline coming soon (although it's a pretty interesting issue). The test fails when the assigned type is const (which currently isn't tested).

My (unconfirmed) suspicion is that the implicitly-generated default operator= is a better match when the type on the right side is const Proxy&. Choosing between a template and a non-template function, overload resolution prefers a non-template function if both are an equally good match; const Proxy& is an exact match for the signature of the default operator=.

Confusingly, however, this works for the move assignment operator, even though the same logic about it being a better match seems to apply. cppreference says that "A deleted implicitly-declared move assignment operator is ignored by overload resolution". Presumably this doesn't apply to a deleted implicitly-declared _copy_ assignment operator, which would explain the difference in behavior.

[var-const]

libcxx/include/__algorithm/copy_backward.h

31

Now that I'm running this test, I'm also getting an error from move_backward. Hopefully the other patch will fix those as well; commented it out for now.

[var-const]

Diff properly (?)

[var-const]

Diff properly (?)

[philnik]

LGTM for now with the min_element change and green CI. I think there should be a few follow-up PRs to clean some things up though.

libcxx/include/__algorithm/iterator_operations.h

50

Am I missing something, or did you not update this part yet?

libcxx/include/__algorithm/sort.h

34–80

I'll try to make a follow-up PR to remove this, but as I said I'm Ok with it for now.

55

__enable_if_t?

73

__enable_if_t?

[var-const]

Fix the CI.

[var-const]

Changes to min_element + other feedback.

libcxx/include/__algorithm/iterator_operations.h

50

Sorry, looks like I messed up merging. Should be good now, thanks for checking.

[huixie90]

LGTM with green ci
we could follow up with more testing for iter_move

libcxx/include/__algorithm/make_heap.h

28

it won't trigger runtime issues , just compile time issues. It is not a matter of whether the Opts::next is called on the caller or here. I am not sure what is the best approach, I prefer to making all __ algorithms to take an iterator and a sentinel of different types (obviously it would still work if you pass two iterators of same type), so that both classic and ranges algorithms can call it and won't worry about calling opts::next. It is the __ algorithm to decide whether to call opts::next or not. But in any case, we could revisit later if we are getting confused

libcxx/include/__algorithm/nth_element.h

76

question: does this algorithm have the "robust against copy comparator test"? right now the comparator is copied several times but I guess this is fine

libcxx/include/__algorithm/pop_heap.h

39

should this call iter_move?

libcxx/include/__algorithm/sort.h

44

I am slightly concerned about the reference member because if we are going to copy the comparator around we have risk of having dangling reference. but I guess the trick is that we never copy the comparators?

54

> > in the end to support c++03?

71

where does the int come from? How can a policy be an int?

libcxx/test/std/algorithms/ranges_robust_against_proxy_iterators.compile.pass.cpp

14

not all algorithms support move only types. and I think it is sufficient to use Proxy<MoveOnly> for the test.

28–45

we don't need to test all 100 algorithms as most algorithms won't swap elements. I do agree that this test covers 80%+ problems. I just feel more confident if we actually checking that the result is correct. I think the "sorting" algorithms are worth checking the result

152

hmm. that is strange.
let's say the input range is

std::array a{1,2,3};
ProxyRange inputs{a};

and output is

std::array<Proxy<int>, 3> out;

iter_value_t<_OutputIterator> should be Proxy<int> and iter_reference_t<_InputIterator> should be Proxy<int&>
and Proxy<int> should be constructible from Proxy<int&>.
did I miss anything?

libcxx/test/support/test_iterators.h

881–882

hmm. I suspect the tests are relying on the implicit conversion from T to Proxy<T>. (my original assignment explicitly check if rhs is Proxy and your new one allows implicit conversions. The class wasn't designed for Proxy<T> = T but if that makes the test easier it would be fine. I will take a look later and it shouldn't block your patch.

[var-const]

Fix the CI.

[var-const]

Fix the CI.

[var-const]

Fix the CI.

[var-const]

Fix the CI, address feedback.

libcxx/include/__algorithm/nth_element.h

76

Yes, it is verified by the robust... test. _Compare is either a reference type, or, in debug mode, a small wrapper class that contains a reference member to the actual comparator (this is why _Compare is used explicitly to instantiate those functions -- deduction would deduce a non-reference type). Thus in either case, what's being passed around is a reference.

libcxx/include/__algorithm/pop_heap.h

39

Thanks for catching this, I missed it somehow.

libcxx/include/__algorithm/sort.h

44

It's a bit complicated, but there is always a value at the top of the call stack (in std::sort or ranges::sort), and all the functions down the call stack pass around a reference to the original value. _WrapAlgPolicy follows the same approach.

71

The expression is meaningless -- I just need to refer to _Wrapped::_AlgPolicy in a SFINAE context so that this specialization is preferred when _Wrapped is a _WrapAlgPolicy.

libcxx/test/support/test_iterators.h

881–882

Thanks!

[huixie90]

libcxx/include/__algorithm/sort.h

34

I would also mention the ABI stability in the comments

71

I was a bit confused and thought you are trying to distinguish between classic policy and range policy. Now I understand that it is for both and distinguish them from the unwrapped ones. Why can't you just do

template <class... _Ts>
struct _UnwrapAlgPolicy<_WrapAlgPolicy <Ts...>, void>{
// code
};

(we can also remove the second template argument void from here and the primary template)

[var-const]

Propagate _AlgPolicy to shuffle to fix the debug build.

[var-const]

Fix the CI.

[var-const]

libcxx/test/std/algorithms/ranges_robust_against_proxy_iterators.compile.pass.cpp

152

_OutputIterator would have to be a nothrow-forward-iterator, so IIUC its value_type cannot be Proxy.

[ldionne]

Thanks for the patch! I have a few comments that would ideally require a post-commit change, but apart from that everything LGTM.

libcxx/include/__algorithm/iterator_operations.h

64

Let's not fix this immediately, but we should use __advance, __next, etc. for all these names. I understand the reasoning that those are "reserved names" because they are used elsewhere in the library, however this is playing with fire. For example, std::next was introduced in C++11. Hence, users could technically #define next(...) in C++03 and use <algorithm> in a valid program. Right now, this would break since we are using the next name. To avoid having to even think about this, I would just throw __ in front of anything that's internal, period. It's less pretty, but it's simpler and more robust.

libcxx/include/__algorithm/ranges_fill.h

33

Can we add a test specifically for this bug?

libcxx/include/__algorithm/sort.h

123

_LIBCPP_HIDE_FROM_ABI?

545

Here is another approach that would maintain ABI compatibility, but in which nobody writing new code would actually use the explicitly instantiated functions in the dylib. I think it would be reasonable to investigate making this simplification after the LLVM 15 release is done (we should compile significant code bases and try to see if we notice regressions, and if not, we could do this *and* include the __sort instantiations only in the stable ABI).

//
// In this header:
//
template <class _AlgPolicy, class _RandomAccessIterator, class _Comp>
inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17
void __sort_impl(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp& __comp) {
  std::__debug_randomize_range<_AlgPolicy>(__first, __last);

  using _Comp_ref = typename __comp_ref_type<_Comp>::type;
  if (__libcpp_is_constant_evaluated()) {
    std::__partial_sort<_AlgPolicy, _Comp_ref>(__first, __last, __last, _Comp_ref(__comp));

  } else {
    typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
    difference_type __depth_limit = 2 * __log2i(__last - __first);
    std::__introsort<_AlgPolicy, _Compare>(__first, __last, __comp, __depth_limit);    
  }
}

//
// In algorithm.cpp:
//

// Only used for STL classic algorithms. We keep this name for ABI compatibility because we have
// been explicitly instantiating `__sort` functions in the shared library.
template <class _Compare, class _RandomAccessIterator>
void __sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) {
  std::__sort_impl<_ClassicAlgPolicy>(std::move(__first), std::move(__last), std::move(__comp));
}

// All the explicit instantiations
[...]

[alexfh]

Heads up: we see breakages that root-cause to this commit. I don't yet know how exactly it is related though. Investigating further.

[var-const]

In D129823#3664001, @alexfh wrote:

Heads up: we see breakages that root-cause to this commit. I don't yet know how exactly it is related though. Investigating further.

Thanks for the heads-up. Can you post more information about the breakage (ideally the compiler error, assuming it is a compiler error) while you're investigating?

[alexfh]

In D129823#3664195, @var-const wrote:

In D129823#3664001, @alexfh wrote:

Heads up: we see breakages that root-cause to this commit. I don't yet know how exactly it is related though. Investigating further.

Thanks for the heads-up. Can you post more information about the breakage (ideally the compiler error, assuming it is a compiler error) while you're investigating?

I'm still struggling to get an isolated reproducer, but now I think the crash is happening in v8 code around this line: https://source.chromium.org/chromium/chromium/src/+/master:v8/src/objects/objects.cc;l=6212;drc=cc136c19595fe0a1cde294d8df6cb1b61023012b (not sure about this code online being identical to what I'm looking at, but it seems quite similar at least in the function I pointed at).

[alexfh]

In D129823#3664218, @alexfh wrote:

In D129823#3664195, @var-const wrote:

In D129823#3664001, @alexfh wrote:

Heads up: we see breakages that root-cause to this commit. I don't yet know how exactly it is related though. Investigating further.

Thanks for the heads-up. Can you post more information about the breakage (ideally the compiler error, assuming it is a compiler error) while you're investigating?

I'm still struggling to get an isolated reproducer, but now I think the crash is happening in v8 code around this line: https://source.chromium.org/chromium/chromium/src/+/master:v8/src/objects/objects.cc;l=6212;drc=cc136c19595fe0a1cde294d8df6cb1b61023012b (not sure about this code online being identical to what I'm looking at, but it seems quite similar at least in the function I pointed at).

This is the relevant part of the stack trace:

#0  0x0000555559d547bd in void std::__u::__insertion_sort_3<std::__u::_ClassicAlgPolicy, v8::internal::EnumIndexComparator<v8::internal::GlobalDictionary>&, v8::internal::AtomicSlot>(v8::internal::AtomicSlot, v8::internal::AtomicSlot, v8::internal::EnumIndexComparator<v8::internal::GlobalDictionary>&) ()
#1  0x0000555559d544b5 in void std::__u::__introsort<std::__u::_ClassicAlgPolicy, v8::internal::EnumIndexComparator<v8::internal::GlobalDictionary>&, v8::internal::AtomicSlot>(v8::internal::AtomicSlot, v8::internal::AtomicSlot, v8::internal::EnumIndexComparator<v8::internal::GlobalDictionary>&, std::__u::iterator_traits<v8::internal::AtomicSlot>::difference_type) ()
#2  0x0000555559d363a3 in v8::internal::BaseNameDictionary<v8::internal::GlobalDictionary, v8::internal::GlobalDictionaryShape>::IterationIndices(v8::internal::Isolate*, v8::internal::Handle<v8::internal::GlobalDictionary>) ()
#3  0x0000555559bfce13 in v8::internal::Genesis::TransferNamedProperties(v8::internal::Handle<v8::internal::JSObject>, v8::internal::Handle<v8::internal::JSObject>) ()

And the crashing process is a nodejs binary.

[thakis]

We're also hitting this in Chromium. https://bugs.chromium.org/p/chromium/issues/detail?id=1346012 has instructions for reproing in chromium, and a bigger stack. We'll try to reduce this more.

[hans]

This comment was removed by hans.

[var-const]

@alexfh @thakis @hans How difficult/time consuming is this crash to reproduce currently? I presume this is something I cannot do because it would necessitate building Chromium from scratch, right?

[ldionne]

https://bugs.chromium.org/p/chromium/issues/detail?id=1346012 contains:

# Fatal error in ../../v8/src/objects/dictionary-inl.h, line 222
# Debug check failed: KeyAt(cage_base, entry).IsPropertyCell(cage_base).

What could cause this debug check to fail? A double-move? Something else? That information would be extremely useful in figuring out whether the issue is in libc++ or not.

[alexfh]

In D129823#3666479, @ldionne wrote:

... That information would be extremely useful in figuring out whether the issue is in libc++ or not.

Well, I'm pretty sure it's related to the libc++ change in case of v8 inside nodejs. The stack trace I posted earlier contains introsort and insertion_sort_3, which were affected by this patch. @eaeltsin is working on reproducing this with d8, which should be more compact than using nodejs.

[ldionne]

We think we understand the issue, and this should fix it: https://reviews.llvm.org/D130197

[ldionne]

In D129823#3666593, @alexfh wrote:

In D129823#3666479, @ldionne wrote:

... That information would be extremely useful in figuring out whether the issue is in libc++ or not.

Well, I'm pretty sure it's related to the libc++ change in case of v8 inside nodejs.

The larger point I was making is that sometimes, we make changes in libc++ and that exposes problems in user code. If that were the case and Chromium's code was incorrect, there's nothing we could do on our end. I don't think this applies here, however -- I think we found the issue in libc++.

The stack trace I posted earlier contains introsort and insertion_sort_3, which were affected by this patch. @eaeltsin is working on reproducing this with d8, which should be more compact than using nodejs.

@eaeltsin Can you try applying D130197 to see if that fixes the issue? We'll commit it nonetheless because it fixes issues with proxy iterators, but it would be good to confirm that it indeed fixes your issue so we can stop looking.

[eaeltsin]

Unfortunately not, this doesn't fix the issue I'm seeing.

I'm not yet ready with the reproducer.

What I'm doing is building d8 with disabled pointers compression and optimizations, and running it - it fails on init, no js test needed.

Sample stack trace - looks like the code reads from a bad address :

* thread #1, name = 'd8', stop reason = signal SIGSEGV: invalid address (fault address: 0xf)
  * frame #0: 0x00005555579e68b9 d8`void std::__u::__insertion_sort_3<std::__u::_ClassicAlgPolicy, v8::internal::EnumIndexComparator<v8::internal::GlobalDictionary>&, v8::internal::AtomicSlot>(v8::internal::AtomicSlot, v8::internal::AtomicSlot, v8::internal::EnumIndexComparator<v8::internal::GlobalDictionary>&) [inlined] v8::internal::TaggedField<v8::internal::Smi, 16>::load(cage_base=<unavailable>, host=HeapObject @ rdi, offset=0) at tagged-field-inl.h:67:20
    frame #1: 0x00005555579e68b9 d8`void std::__u::__insertion_sort_3<std::__u::_ClassicAlgPolicy, v8::internal::EnumIndexComparator<v8::internal::GlobalDictionary>&, v8::internal::AtomicSlot>(v8::internal::AtomicSlot, v8::internal::AtomicSlot, v8::internal::EnumIndexComparator<v8::internal::GlobalDictionary>&) [inlined] v8::internal::PropertyCell::property_details_raw(this=<unavailable>, cage_base=<unavailable>) const at property-cell-inl.h:25:1
    frame #2: 0x00005555579e68b9 d8`void std::__u::__insertion_sort_3<std::__u::_ClassicAlgPolicy, v8::internal::EnumIndexComparator<v8::internal::GlobalDictionary>&, v8::internal::AtomicSlot>(v8::internal::AtomicSlot, v8::internal::AtomicSlot, v8::internal::EnumIndexComparator<v8::internal::GlobalDictionary>&) [inlined] v8::internal::PropertyCell::property_details_raw(this=<unavailable>) const at property-cell-inl.h:25:1
    frame #3: 0x00005555579e68b9 d8`void std::__u::__insertion_sort_3<std::__u::_ClassicAlgPolicy, v8::internal::EnumIndexComparator<v8::internal::GlobalDictionary>&, v8::internal::AtomicSlot>(v8::internal::AtomicSlot, v8::internal::AtomicSlot, v8::internal::EnumIndexComparator<v8::internal::GlobalDictionary>&) [inlined] v8::internal::PropertyCell::property_details(this=<unavailable>) const at property-cell-inl.h:32:36
    frame #4: 0x00005555579e68b9 d8`void std::__u::__insertion_sort_3<std::__u::_ClassicAlgPolicy, v8::internal::EnumIndexComparator<v8::internal::GlobalDictionary>&, v8::internal::AtomicSlot>(v8::internal::AtomicSlot, v8::internal::AtomicSlot, v8::internal::EnumIndexComparator<v8::internal::GlobalDictionary>&) [inlined] v8::internal::PropertyDetails v8::internal::GlobalDictionaryShape::DetailsAt<v8::internal::GlobalDictionary>(dict=GlobalDictionary @ rbx, entry=<unavailable>) at dictionary-inl.h:338:29
    frame #5: 0x00005555579e68a8 d8`void std::__u::__insertion_sort_3<std::__u::_ClassicAlgPolicy, v8::internal::EnumIndexComparator<v8::internal::GlobalDictionary>&, v8::internal::AtomicSlot>(v8::internal::AtomicSlot, v8::internal::AtomicSlot, v8::internal::EnumIndexComparator<v8::internal::GlobalDictionary>&) [inlined] v8::internal::Dictionary<v8::internal::GlobalDictionary, v8::internal::GlobalDictionaryShape>::DetailsAt(this=0x00007fffffffcf10, entry=<unavailable>) at dictionary-inl.h:71:10
    frame #6: 0x00005555579e68a8 d8`void std::__u::__insertion_sort_3<std::__u::_ClassicAlgPolicy, v8::internal::EnumIndexComparator<v8::internal::GlobalDictionary>&, v8::internal::AtomicSlot>(v8::internal::AtomicSlot, v8::internal::AtomicSlot, v8::internal::EnumIndexComparator<v8::internal::GlobalDictionary>&) [inlined] v8::internal::EnumIndexComparator<v8::internal::GlobalDictionary>::operator(this=0x00007fffffffcf10, a=<unavailable>, b=<unavailable>)(unsigned long, unsigned long) at dictionary.h:376:14
    frame #7: 0x00005555579e688f d8`void std::__u::__insertion_sort_3<std::__u::_ClassicAlgPolicy, v8::internal::EnumIndexComparator<v8::internal::GlobalDictionary>&, v8::internal::AtomicSlot>(__first=AtomicSlot @ r15, __last=AtomicSlot @ r14, __comp=0x00007fffffffcf10) at sort.h:320:9
    frame #8: 0x00005555579e67e6 d8`void std::__u::__introsort<std::__u::_ClassicAlgPolicy, v8::internal::EnumIndexComparator<v8::internal::GlobalDictionary>&, v8::internal::AtomicSlot>(__first=AtomicSlot @ r15, __last=AtomicSlot @ 0x00007fffffffceb8, __comp=0x00007fffffffcf10, __depth=9) at sort.h:453:7 [artificial]
    frame #9: 0x00005555579e6588 d8`void std::__u::__introsort<std::__u::_ClassicAlgPolicy, v8::internal::EnumIndexComparator<v8::internal::GlobalDictionary>&, v8::internal::AtomicSlot>(__first=AtomicSlot @ r15, __last=AtomicSlot @ 0x00007fffffffceb8, __comp=0x00007fffffffcf10, __depth=9) at sort.h:590:7
    frame #10: 0x0000555557a0bc8b d8`v8::internal::BaseNameDictionary<v8::internal::GlobalDictionary, v8::internal::GlobalDictionaryShape>::IterationIndices(v8::internal::Isolate*, v8::internal::Handle<v8::internal::GlobalDictionary>) [inlined] void std::__u::__sort<v8::internal::EnumIndexComparator<v8::internal::GlobalDictionary>&, v8::internal::AtomicSlot>(__first=<unavailable>, __last=<unavailable>, __wrapped_comp=0x00007fffffffcf10) at sort.h:627:3
    frame #11: 0x0000555557a0bc5d d8`v8::internal::BaseNameDictionary<v8::internal::GlobalDictionary, v8::internal::GlobalDictionaryShape>::IterationIndices(v8::internal::Isolate*, v8::internal::Handle<v8::internal::GlobalDictionary>) at sort.h:687:5
    frame #12: 0x0000555557a0bc5d d8`v8::internal::BaseNameDictionary<v8::internal::GlobalDictionary, v8::internal::GlobalDictionaryShape>::IterationIndices(v8::internal::Isolate*, v8::internal::Handle<v8::internal::GlobalDictionary>) [inlined] void std::__u::sort[abi:v15000]<v8::internal::AtomicSlot, v8::internal::EnumIndexComparator<v8::internal::GlobalDictionary>>(__first=<unavailable>, __last=<unavailable>, __comp=EnumIndexComparator<v8::internal::GlobalDictionary> @ 0x00007fffffffcf10) at sort.h:694:3
    frame #13: 0x0000555557a0bc5d d8`v8::internal::BaseNameDictionary<v8::internal::GlobalDictionary, v8::internal::GlobalDictionaryShape>::IterationIndices(isolate=0x0000068f3fc40000, dictionary=<unavailable>) at objects.cc:6291:5
    frame #14: 0x000055555783465c d8`v8::internal::Genesis::TransferNamedProperties(this=0x00007fffffffd140, from=Handle<v8::internal::JSObject> @ 0x00007fffffffcf60, to=Handle<v8::internal::JSObject> @ 0x00007fffffffcfe8) at bootstrapper.cc:6240:9
    frame #15: 0x0000555557833ff9 d8`v8::internal::Genesis::HookUpGlobalObject(this=0x00007fffffffd140, global_object=<unavailable>) at bootstrapper.cc:1434:3
...

[var-const]

In D129823#3666811, @eaeltsin wrote:

Unfortunately not, this doesn't fix the issue I'm seeing.

Can you please try again with https://reviews.llvm.org/D130212? It looks like the first patch didn't fully fix the issue.

[eaeltsin]

Thanks Konstantin, now it works!

[var-const]

In D129823#3667454, @eaeltsin wrote:

Thanks Konstantin, now it works!

Excellent, thanks a lot for checking and reporting back! The credit for the second patch goes to @huixie90.

[alexfh]

In D129823#3667506, @var-const wrote:

In D129823#3667454, @eaeltsin wrote:

Thanks Konstantin, now it works!

Excellent, thanks a lot for checking and reporting back! The credit for the second patch goes to @huixie90.

And the final confirmation: our full test run didn't find any more issues related to this commit. Thanks again for the prompt fix!

[alexfh]

In D129823#3670225, @alexfh wrote:

In D129823#3667506, @var-const wrote:

In D129823#3667454, @eaeltsin wrote:

Thanks Konstantin, now it works!

Excellent, thanks a lot for checking and reporting back! The credit for the second patch goes to @huixie90.

And the final confirmation: our full test run didn't find any more issues related to this commit. Thanks again for the prompt fix!

Sad news: there's another problem caused by this commit (and not fixed by https://reviews.llvm.org/D130212), which wasn't detected initially. The problem is some sort of a data corruption happening in a version of MySQL. I think, the version we see this in should be close to this one: https://fossies.org/dox/mysql-8.0.29/varlen__sort_8h_source.html. A standalone repro is being worked on, but maybe the original code gives enough information to work with.

[var-const]

In D129823#3677825, @alexfh wrote:

In D129823#3670225, @alexfh wrote:

In D129823#3667506, @var-const wrote:

In D129823#3667454, @eaeltsin wrote:

Thanks Konstantin, now it works!

Excellent, thanks a lot for checking and reporting back! The credit for the second patch goes to @huixie90.

And the final confirmation: our full test run didn't find any more issues related to this commit. Thanks again for the prompt fix!

Sad news: there's another problem caused by this commit (and not fixed by https://reviews.llvm.org/D130212), which wasn't detected initially. The problem is some sort of a data corruption happening in a version of MySQL. I think, the version we see this in should be close to this one: https://fossies.org/dox/mysql-8.0.29/varlen__sort_8h_source.html. A standalone repro is being worked on, but maybe the original code gives enough information to work with.

Thank you for the heads-up. Unfortunately, the source doesn't really give us enough information to act upon. While the repro is in the works, do you happen to have any additional information about the issue, like a stack trace?

[alexfh]

In D129823#3677825, @alexfh wrote:

In D129823#3670225, @alexfh wrote:

In D129823#3667506, @var-const wrote:

In D129823#3667454, @eaeltsin wrote:

Thanks Konstantin, now it works!

Excellent, thanks a lot for checking and reporting back! The credit for the second patch goes to @huixie90.

And the final confirmation: our full test run didn't find any more issues related to this commit. Thanks again for the prompt fix!

Sad news: there's another problem caused by this commit (and not fixed by https://reviews.llvm.org/D130212), which wasn't detected initially. The problem is some sort of a data corruption happening in a version of MySQL. I think, the version we see this in should be close to this one: https://fossies.org/dox/mysql-8.0.29/varlen__sort_8h_source.html. A standalone repro is being worked on, but maybe the original code gives enough information to work with.

This code seems to be calling to sort with some custom iterators, which leads to the corruption of the data being sorted: https://github.com/mysql/mysql-server/blob/8.0/sql/handler.cc#L6779

[alexfh]

I think, this version is closer to where I see the problem: https://github.com/mysql/mysql-server/blob/a1bf3cfcecc85d3ae20828d9f78a710f3277ab40/sql/handler.cc#L6704

[var-const]

In D129823#3677925, @alexfh wrote:

I think, this version is closer to where I see the problem: https://github.com/mysql/mysql-server/blob/a1bf3cfcecc85d3ae20828d9f78a710f3277ab40/sql/handler.cc#L6704

We would need a repro case. varlen_element's move semantics look very suspicious, but it's hard to say whether this can actually cause the issue you're seeing.

[jgorbe]

Some more information about the problem. The stack trace looks like follows. The problem manifests as an ASan out of memory error because the move constructor in varlen_sort.h:59 is getting incorrect data and it's trying to allocate an absurdly big amount of memory.

==7713==ERROR: AddressSanitizer: out of memory: allocator is trying to allocate 0xc5600000e4e bytes
    #0 0x55deed3caedd in operator new[](unsigned long) third_party/llvm/llvm-project/compiler-rt/lib/asan/asan_new_delete.cpp:98:3
    #1 0x55deed6e733c in varlen_element MYSQLSRCHOME/include/varlen_sort.h:59:17
    #2 0x55deed6e733c in bool std::__u::__insertion_sort_incomplete<void varlen_sort<unsigned char, DsMrr_impl::dsmrr_fill_buffer()::$_3>(unsigned char*, unsigned char*, unsigned long, DsMrr_impl::dsmrr_fill_buffer()::$_3)::'lambda'(varlen_element const&, varlen_element const&)&, varlen_iterator>(DsMrr_impl::dsmrr_fill_buffer()::$_3, DsMrr_impl::dsmrr_fill_buffer()::$_3, unsigned char) third_party/crosstool/v18/stable/toolchain/bin/../include/c++/v1/__algorithm/sort.h:373:18
    #3 0x55deed6e4fcd in void std::__u::__introsort<std::__u::_ClassicAlgPolicy, void varlen_sort<unsigned char, DsMrr_impl::dsmrr_fill_buffer()::$_3>(unsigned char*, unsigned char*, unsigned long, DsMrr_impl::dsmrr_fill_buffer()::$_3)::'lambda'(varlen_element const&, varlen_element const&)&, varlen_iterator>(varlen_iterator, varlen_iterator, DsMrr_impl::dsmrr_fill_buffer()::$_3, std::__u::iterator_traits<varlen_iterator>::difference_type) third_party/crosstool/v18/stable/toolchain/bin/../include/c++/v1/__algorithm/sort.h:575:19
    #4 0x55deed6db70b in __sort<(lambda at MYSQLSRCHOME/include/varlen_sort.h:199:13) &, varlen_iterator> third_party/crosstool/v18/stable/toolchain/bin/../include/c++/v1/__algorithm/sort.h:627:3
    #5 0x55deed6db70b in __sort_impl<std::__u::_ClassicAlgPolicy, varlen_iterator, (lambda at MYSQLSRCHOME/include/varlen_sort.h:199:13)> third_party/crosstool/v18/stable/toolchain/bin/../include/c++/v1/__algorithm/sort.h:687:5
    #6 0x55deed6db70b in sort<varlen_iterator, (lambda at MYSQLSRCHOME/include/varlen_sort.h:199:13)> third_party/crosstool/v18/stable/toolchain/bin/../include/c++/v1/__algorithm/sort.h:694:3
    #7 0x55deed6db70b in varlen_sort<unsigned char, (lambda at MYSQLSRCHOME/sql/handler.cc:6738:7)> MYSQLSRCHOME/include/varlen_sort.h:197:3
    #8 0x55deed6db70b in DsMrr_impl::dsmrr_fill_buffer() MYSQLSRCHOME/sql/handler.cc:6736:3
    #9 0x55deed6da9c8 in DsMrr_impl::dsmrr_init(RANGE_SEQ_IF*, void*, unsigned int, unsigned int, HANDLER_BUFFER*) MYSQLSRCHOME/sql/handler.cc:6617:17
    #10 0x55deedf21bb6 in MultiRangeRowIterator::Init() MYSQLSRCHOME/sql/bka_iterator.cc:368:18
    #11 0x55deedf21100 in BKAIterator::ReadOuterRows() MYSQLSRCHOME/sql/bka_iterator.cc:228:22
    #12 0x55deedf2174a in BKAIterator::Read() MYSQLSRCHOME/sql/bka_iterator.cc:274:19
    #13 0x55deede3ed6b in Query_expression::ExecuteIteratorQuery(THD*) MYSQLSRCHOME/sql/sql_union.cc:1231:36
    #14 0x55deede3f4e4 in Query_expression::execute(THD*) MYSQLSRCHOME/sql/sql_union.cc:1284:10
    #15 0x55deedd5a4f6 in Sql_cmd_dml::execute_inner(THD*) MYSQLSRCHOME/sql/sql_select.cc:776:15
    #16 0x55deedd59381 in Sql_cmd_dml::execute(THD*) MYSQLSRCHOME/sql/sql_select.cc:574:7
    #17 0x55deedcb2863 in mysql_execute_command(THD*, bool) MYSQLSRCHOME/sql/sql_parse.cc:4438:29
    #18 0x55deedcae283 in dispatch_sql_command(THD*, Parser_state*) MYSQLSRCHOME/sql/sql_parse.cc:5037:19
    #19 0x55deedcaac9c in dispatch_command(THD*, COM_DATA const*, enum_server_command) MYSQLSRCHOME/sql/sql_parse.cc:1863:7
    #20 0x55deedcacd8b in do_command(THD*) MYSQLSRCHOME/sql/sql_parse.cc:1342:18
    #21 0x55deed3fe4f3 in handle_connection(void*) MYSQLSRCHOME/sql/conn_handler/connection_handler_per_thread.cc:310:13
    #22 0x55def2434649 in pfs_spawn_thread(void*) MYSQLSRCHOME/storage/perfschema/pfs.cc:2905:3
    #23 0x7f6af0285b54 in start_thread (/usr/grte/v5/lib64/libpthread.so.0+0xbb54) (BuildId: 64752de50ebd1a108f4b3f8d0d7e1a13)

sort.h:373 does

	      value_type __t(_Ops::__iter_move(__i));

When reaching this line the value of __i is correct. However, after the call to __iter_move, the varlen_element move constructor (source) gets incorrect values.

I've managed to get the test to pass by replacing occurrences of _Ops::__iter_move(iter) back to _VSTD::move(*iter) and I don't see anything particularly wrong with the affected mysql code so I suspect there's some remaining problem in __iter_move that hasn't been solved with the follow-up patches so far.

[huixie90]

In D129823#3677969, @jgorbe wrote:

Some more information about the problem. The stack trace looks like follows. The problem manifests as an ASan out of memory error because the move constructor in varlen_sort.h:59 is getting incorrect data and it's trying to allocate an absurdly big amount of memory.

==7713==ERROR: AddressSanitizer: out of memory: allocator is trying to allocate 0xc5600000e4e bytes
    #0 0x55deed3caedd in operator new[](unsigned long) third_party/llvm/llvm-project/compiler-rt/lib/asan/asan_new_delete.cpp:98:3
    #1 0x55deed6e733c in varlen_element MYSQLSRCHOME/include/varlen_sort.h:59:17
    #2 0x55deed6e733c in bool std::__u::__insertion_sort_incomplete<void varlen_sort<unsigned char, DsMrr_impl::dsmrr_fill_buffer()::$_3>(unsigned char*, unsigned char*, unsigned long, DsMrr_impl::dsmrr_fill_buffer()::$_3)::'lambda'(varlen_element const&, varlen_element const&)&, varlen_iterator>(DsMrr_impl::dsmrr_fill_buffer()::$_3, DsMrr_impl::dsmrr_fill_buffer()::$_3, unsigned char) third_party/crosstool/v18/stable/toolchain/bin/../include/c++/v1/__algorithm/sort.h:373:18
    #3 0x55deed6e4fcd in void std::__u::__introsort<std::__u::_ClassicAlgPolicy, void varlen_sort<unsigned char, DsMrr_impl::dsmrr_fill_buffer()::$_3>(unsigned char*, unsigned char*, unsigned long, DsMrr_impl::dsmrr_fill_buffer()::$_3)::'lambda'(varlen_element const&, varlen_element const&)&, varlen_iterator>(varlen_iterator, varlen_iterator, DsMrr_impl::dsmrr_fill_buffer()::$_3, std::__u::iterator_traits<varlen_iterator>::difference_type) third_party/crosstool/v18/stable/toolchain/bin/../include/c++/v1/__algorithm/sort.h:575:19
    #4 0x55deed6db70b in __sort<(lambda at MYSQLSRCHOME/include/varlen_sort.h:199:13) &, varlen_iterator> third_party/crosstool/v18/stable/toolchain/bin/../include/c++/v1/__algorithm/sort.h:627:3
    #5 0x55deed6db70b in __sort_impl<std::__u::_ClassicAlgPolicy, varlen_iterator, (lambda at MYSQLSRCHOME/include/varlen_sort.h:199:13)> third_party/crosstool/v18/stable/toolchain/bin/../include/c++/v1/__algorithm/sort.h:687:5
    #6 0x55deed6db70b in sort<varlen_iterator, (lambda at MYSQLSRCHOME/include/varlen_sort.h:199:13)> third_party/crosstool/v18/stable/toolchain/bin/../include/c++/v1/__algorithm/sort.h:694:3
    #7 0x55deed6db70b in varlen_sort<unsigned char, (lambda at MYSQLSRCHOME/sql/handler.cc:6738:7)> MYSQLSRCHOME/include/varlen_sort.h:197:3
    #8 0x55deed6db70b in DsMrr_impl::dsmrr_fill_buffer() MYSQLSRCHOME/sql/handler.cc:6736:3
    #9 0x55deed6da9c8 in DsMrr_impl::dsmrr_init(RANGE_SEQ_IF*, void*, unsigned int, unsigned int, HANDLER_BUFFER*) MYSQLSRCHOME/sql/handler.cc:6617:17
    #10 0x55deedf21bb6 in MultiRangeRowIterator::Init() MYSQLSRCHOME/sql/bka_iterator.cc:368:18
    #11 0x55deedf21100 in BKAIterator::ReadOuterRows() MYSQLSRCHOME/sql/bka_iterator.cc:228:22
    #12 0x55deedf2174a in BKAIterator::Read() MYSQLSRCHOME/sql/bka_iterator.cc:274:19
    #13 0x55deede3ed6b in Query_expression::ExecuteIteratorQuery(THD*) MYSQLSRCHOME/sql/sql_union.cc:1231:36
    #14 0x55deede3f4e4 in Query_expression::execute(THD*) MYSQLSRCHOME/sql/sql_union.cc:1284:10
    #15 0x55deedd5a4f6 in Sql_cmd_dml::execute_inner(THD*) MYSQLSRCHOME/sql/sql_select.cc:776:15
    #16 0x55deedd59381 in Sql_cmd_dml::execute(THD*) MYSQLSRCHOME/sql/sql_select.cc:574:7
    #17 0x55deedcb2863 in mysql_execute_command(THD*, bool) MYSQLSRCHOME/sql/sql_parse.cc:4438:29
    #18 0x55deedcae283 in dispatch_sql_command(THD*, Parser_state*) MYSQLSRCHOME/sql/sql_parse.cc:5037:19
    #19 0x55deedcaac9c in dispatch_command(THD*, COM_DATA const*, enum_server_command) MYSQLSRCHOME/sql/sql_parse.cc:1863:7
    #20 0x55deedcacd8b in do_command(THD*) MYSQLSRCHOME/sql/sql_parse.cc:1342:18
    #21 0x55deed3fe4f3 in handle_connection(void*) MYSQLSRCHOME/sql/conn_handler/connection_handler_per_thread.cc:310:13
    #22 0x55def2434649 in pfs_spawn_thread(void*) MYSQLSRCHOME/storage/perfschema/pfs.cc:2905:3
    #23 0x7f6af0285b54 in start_thread (/usr/grte/v5/lib64/libpthread.so.0+0xbb54) (BuildId: 64752de50ebd1a108f4b3f8d0d7e1a13)

sort.h:373 does

	      value_type __t(_Ops::__iter_move(__i));

When reaching this line the value of __i is correct. However, after the call to __iter_move, the varlen_element move constructor (source) gets incorrect values.

I've managed to get the test to pass by replacing occurrences of _Ops::__iter_move(iter) back to _VSTD::move(*iter) and I don't see anything particularly wrong with the affected mysql code so I suspect there's some remaining problem in __iter_move that hasn't been solved with the follow-up patches so far.

Hi,

Thank you very much for posting the analysis. I think the problem is this line
https://fossies.org/dox/mysql-8.0.29/varlen__sort_8h_source.html#l00187

It sets the iteartor_traits to be iterator_traits<varlen_element *>. The iterator_traits<varlen_element *>::reference is varlen_element& (note the reference here). However, its operator* does not return varlen_element&, but a prvalue varlen_element
https://fossies.org/dox/mysql-8.0.29/varlen__sort_8h_source.html#l00090

So this is technically UB because its iteartor_traits lied.

Note that we relied on the iterator_traits::reference to be correct to dispatch the iter_move
https://github.com/llvm/llvm-project/blob/78015047b22dd64f7c647ab7ce04d42e761e7b8f/libcxx/include/__algorithm/iterator_operations.h#L81

We could in theory dispatch on the decltype(*it), but this is somehow challenging in C++03 mode where decltype does not exist.
So in conclusion, it is mysql code that has UB. But it might still be better for us to keep the UB working.

@ldionne @var-const ,
what do you think?

[rupprecht]

Here is the repro we're discussing in the most recent comments: https://godbolt.org/z/xPhY4eE7a

It's quite long, so as an alternative to the godbolt link I'll post as an attachment instead of pasting inline:

repro.cc6 KBDownload

[var-const]

@alexfh @jgorbe @rupprecht Thank you for the additional details! I believe the analysis by @huixie90 is spot on and have prepared a patch based on it: https://reviews.llvm.org/D130538
Can you try out the patch to see if it resolves the issue you're seeing? It does fix the repro case for me.

[rupprecht]

In D129823#3678246, @var-const wrote:

@alexfh @jgorbe @rupprecht Thank you for the additional details! I believe the analysis by @huixie90 is spot on and have prepared a patch based on it: https://reviews.llvm.org/D130538
Can you try out the patch to see if it resolves the issue you're seeing? It does fix the repro case for me.

Thanks! Unfortunately, it just changes the failure that we now see from a crash to a weird runtime failure; incorrectly sorted results, I assume.

I have an alternative change to fix the UB and return varlen_element & instead of varlen_element (isn't that the eventual fix we should do anyway?), and initial tests seem to be passing now. I'm not sure what D130538 is missing.

[var-const]

In D129823#3678367, @rupprecht wrote:

In D129823#3678246, @var-const wrote:

@alexfh @jgorbe @rupprecht Thank you for the additional details! I believe the analysis by @huixie90 is spot on and have prepared a patch based on it: https://reviews.llvm.org/D130538
Can you try out the patch to see if it resolves the issue you're seeing? It does fix the repro case for me.

Thanks! Unfortunately, it just changes the failure that we now see from a crash to a weird runtime failure; incorrectly sorted results, I assume.

I have an alternative change to fix the UB and return varlen_element & instead of varlen_element (isn't that the eventual fix we should do anyway?), and initial tests seem to be passing now. I'm not sure what D130538 is missing.

Thank you for the update. Fixing the UB in MySQL would be vastly preferable.

[huixie90]

In D129823#3678367, @rupprecht wrote:

In D129823#3678246, @var-const wrote:

@alexfh @jgorbe @rupprecht Thank you for the additional details! I believe the analysis by @huixie90 is spot on and have prepared a patch based on it: https://reviews.llvm.org/D130538
Can you try out the patch to see if it resolves the issue you're seeing? It does fix the repro case for me.

Thanks! Unfortunately, it just changes the failure that we now see from a crash to a weird runtime failure; incorrectly sorted results, I assume.

I have an alternative change to fix the UB and return varlen_element & instead of varlen_element (isn't that the eventual fix we should do anyway?), and initial tests seem to be passing now. I'm not sure what D130538 is missing.

@rupprecht Thank you for trying the fix. You can't return varlen_element& because the function creates a temporary varlen_element on the fly. The fix is to remove the template specialization of std::iterator_traits<varlen_iterator> , which incorrectly defines the traits. instead , define some member typedef:

using value_type = varlen_element;
using reference = varlen_element;
using difference_type = ptrdiff_t;
using iterator_category = std::random_access_iterator_tag;
using pointer = void; // this one is also wrong because of wrong operator->

note (pointer type and operator-> also seem to be wrong but we don't use -> in our algorithms.
https://godbolt.org/z/T8cxffb3o

Also the fact that value_type being the same as reference is a bit suspicious as most proxy iterators have different types. but it might be fine since the code worked before.

Could you please send us a reproducer where the runtime behaviour is wrong? It might be another UB somewhere else which exposed by this patch. We don't want to blindly break user code even if it is UB so it would be good to see a reproducer.
(Please could you send the expected output of the reproducer as well because I don't fully understand what the class is supposed to do atm)

[ldionne]

Thanks everyone for chiming in on this issue. I am speaking to @var-const right now who summarized the issues to me. It looks like there is some UB in MySQL right now because their funky iterator type is lying about iterator_traits<It>::reference, and that's really the crux of the problem IMO. That needs to be fixed, and it's not something that libc++ can accommodate by making the code work.

However, it also seems like it's something that we can easily catch at compile-time instead, hence my suggestion to add a static_assert in D130538. It will still break Chromium via its MySQL dependency, however the error will clearly point out how it is broken and how to fix it.

@rupprecht If you are able to get us a reproduction of the failure on top of D130538 (without the static_assert), we'd be interested in taking a look to understand whether there's something more subtle at play. However, our current understanding is that D130538 + static_assert will work in all cases (i.e. either it will work as intended, or it will issue a compile-time diagnostic). If you see additional issues after we move forward with D130538, please let us know via the usual means. This has been really useful in finding subtle problems early and we definitely want to address such issues with the highest priority.

[rupprecht]

In D129823#3680525, @ldionne wrote:

Thanks everyone for chiming in on this issue. I am speaking to @var-const right now who summarized the issues to me. It looks like there is some UB in MySQL right now because their funky iterator type is lying about iterator_traits<It>::reference, and that's really the crux of the problem IMO. That needs to be fixed, and it's not something that libc++ can accommodate by making the code work.

However, it also seems like it's something that we can easily catch at compile-time instead, hence my suggestion to add a static_assert in D130538. It will still break Chromium via its MySQL dependency, however the error will clearly point out how it is broken and how to fix it.

Emphatic +1 to this, fixing the UB is better than hacking up libc++, and a static assert would be amazing here. I'd much rather handle a clear build breakage than spend hours/days hunting down the source of a weird runtime error.

@rupprecht If you are able to get us a reproduction of the failure on top of D130538 (without the static_assert), we'd be interested in taking a look to understand whether there's something more subtle at play. However, our current understanding is that D130538 + static_assert will work in all cases (i.e. either it will work as intended, or it will issue a compile-time diagnostic). If you see additional issues after we move forward with D130538, please let us know via the usual means. This has been really useful in finding subtle problems early and we definitely want to address such issues with the highest priority.

I am attempting to do this, although it's a little more challenging now that the failure is moved later -- it was relatively easy to provide the previous repro because the test runner crashed at the moment something went wrong; producing wrong results without crashing requires more specific knowledge of mysql internals.

[var-const]

In D129823#3680764, @rupprecht wrote:

Emphatic +1 to this, fixing the UB is better than hacking up libc++, and a static assert would be amazing here. I'd much rather handle a clear build breakage than spend hours/days hunting down the source of a weird runtime error.

I have added the static_assert to D130538.

In D129823#3680764, @rupprecht wrote:

I am attempting to do this, although it's a little more challenging now that the failure is moved later -- it was relatively easy to provide the previous repro because the test runner crashed at the moment something went wrong; producing wrong results without crashing requires more specific knowledge of mysql internals.

I couldn't get the repro code to behave incorrectly with D130538 patched in; it's possible that the problem is no longer in varlen_iterator or not in std::sort. So we would need a new repro case to make more progress on this.

[rupprecht]

In D129823#3680764, @rupprecht wrote:

In D129823#3680525, @ldionne wrote:

Thanks everyone for chiming in on this issue. I am speaking to @var-const right now who summarized the issues to me. It looks like there is some UB in MySQL right now because their funky iterator type is lying about iterator_traits<It>::reference, and that's really the crux of the problem IMO. That needs to be fixed, and it's not something that libc++ can accommodate by making the code work.

However, it also seems like it's something that we can easily catch at compile-time instead, hence my suggestion to add a static_assert in D130538. It will still break Chromium via its MySQL dependency, however the error will clearly point out how it is broken and how to fix it.

Emphatic +1 to this, fixing the UB is better than hacking up libc++, and a static assert would be amazing here. I'd much rather handle a clear build breakage than spend hours/days hunting down the source of a weird runtime error.

@rupprecht If you are able to get us a reproduction of the failure on top of D130538 (without the static_assert), we'd be interested in taking a look to understand whether there's something more subtle at play. However, our current understanding is that D130538 + static_assert will work in all cases (i.e. either it will work as intended, or it will issue a compile-time diagnostic). If you see additional issues after we move forward with D130538, please let us know via the usual means. This has been really useful in finding subtle problems early and we definitely want to address such issues with the highest priority.

I am attempting to do this, although it's a little more challenging now that the failure is moved later -- it was relatively easy to provide the previous repro because the test runner crashed at the moment something went wrong; producing wrong results without crashing requires more specific knowledge of mysql internals.

Sorry about the delay. I have a slightly evil reproducer, modified from my original one, that shows the incorrect sort result if we take the static_assert out of D130538 so we can keep using a buggy iterator: https://godbolt.org/z/xfhseoaW7 (also attached)

pre-sort
	 varlen_element[4] = 2436
	 varlen_element[5] = 2438
	 varlen_element[6] = 2439
	 varlen_element[7] = 2437
	 varlen_element[8] = 2440
post-sort
	 varlen_element[4] = 2436
	 varlen_element[5] = 2438 <-- should be a 2437 here
	 varlen_element[6] = 2439
	 varlen_element[7] = 2439 <-- oops, 2439 is here twice
	 varlen_element[8] = 2440

I don't know if there's anything interesting you want to look at here -- we should expect nothing less than incorrect results by writing a UB iterator. The iterator is fixed now, and the static_cast in D130538 catches the buggy version of the iterator.

In fact it looks like the assert has found a few more iterators that are either getting away with UB or have bad test coverage, so we're definitely glad the assert is there now.

repro-D129823-2.cpp6 KBDownload

[var-const]

@rupprecht Thanks a lot for the reproducer! The issue here is the varlen_element's heuristics for creating an independent copy of the underlying data. Currently, it's done in the move constructor, on the assumption that insertion sort inside std::sort would necessarily call the move constructor. However, this assumption is no longer true.

Previously, the temporary element would be created like this (simplified):

value_type temp = std::move(*iter);

*iter returns a prvalue varlen_element, which std::move then casts to an rvalue reference, which results in the move constructor being invoked.

After the rewrite, the call to std::move(*iter) is replaced by an internal function __iter_move which emulates C++20's iter_move. __iter_move notices that *iter returns a temporary and thus also returns a value; attempting to cast it to an rvalue reference would result in a dangling reference:

// simplified
template <class _Iter, enable_if_t<IterDerefReturnsPrvalue<_Iter>>
typename _Iter::value_type __iter_move(_Iter& __iter) {
  return *__iter;
}

Due to mandatory copy elision, the move constructor is no longer invoked:

value_type temp = __iter_move(iter);

Instead, the result of calling *iter is stored right in temp, with no copying or moving involved.

Since there was no call to the move constructor, now two varlen_elements are shallow copies of each other, sharing a pointer to the same underlying data. Thus, the value of the temporary changes when the value of the original iterator from which it was created changes; that's how the repro case ends up with two 2439 elements.

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/iterator_operations.h>
 #include <__algorithm/unwrap_iter.h>
 #include <__config>
 #include <__iterator/iterator_traits.h>
 #include <__iterator/reverse_iterator.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 _Iter1, class _Sent1, class _Iter2>
+template <class _AlgPolicy, class _Iter1, class _Sent1, class _Iter2>
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
 pair<_Iter1, _Iter2> __copy_backward_impl(_Iter1 __first, _Sent1 __last, _Iter2 __result) {
-  auto __ret = std::__copy(reverse_iterator<_Iter1>(__last),
-                           reverse_iterator<_Sent1>(__first),
+  auto __last_iter = _IterOps<_AlgPolicy>::next(__first, __last);
+  auto __ret = std::__copy(reverse_iterator<_Iter1>(__last_iter),
+                           reverse_iterator<_Iter1>(__first),
                            reverse_iterator<_Iter2>(__result));
   return pair<_Iter1, _Iter2>(__ret.first.base(), __ret.second.base());
 }
 
-template <class _Iter1, class _Sent1, class _Iter2>
+template <class _AlgPolicy, class _Iter1, class _Sent1, class _Iter2>
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
 pair<_Iter1, _Iter2> __copy_backward(_Iter1 __first, _Sent1 __last, _Iter2 __result) {
-  auto __ret = std::__copy_backward_impl(std::__unwrap_iter(__first),
+  auto __ret = std::__copy_backward_impl<_AlgPolicy>(std::__unwrap_iter(__first),
                                                      std::__unwrap_iter(__last),
                                                      std::__unwrap_iter(__result));
   return pair<_Iter1, _Iter2>(std::__rewrap_iter(__first, __ret.first), std::__rewrap_iter(__result, __ret.second));
 }
 
 template <class _BidirectionalIterator1, class _BidirectionalIterator2>
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17
 _BidirectionalIterator2
 copy_backward(_BidirectionalIterator1 __first, _BidirectionalIterator1 __last, _BidirectionalIterator2 __result) {
-  return std::__copy_backward(__first, __last, __result).second;
+  return std::__copy_backward<_ClassicAlgPolicy>(__first, __last, __result).second;
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_COPY_BACKWARD_H

libcxx/include/__algorithm/inplace_merge.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_INPLACE_MERGE_H
 #define _LIBCPP___ALGORITHM_INPLACE_MERGE_H
 
 #include <__algorithm/comp.h>
 #include <__algorithm/comp_ref_type.h>
+#include <__algorithm/iterator_operations.h>
 #include <__algorithm/lower_bound.h>
 #include <__algorithm/min.h>
 #include <__algorithm/move.h>
 #include <__algorithm/rotate.h>
 #include <__algorithm/upper_bound.h>
 #include <__config>
 #include <__iterator/advance.h>
 #include <__iterator/distance.h>
 #include <__iterator/iterator_traits.h>
 #include <__iterator/reverse_iterator.h>
-#include <__utility/swap.h>
 #include <memory>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 _LIBCPP_PUSH_MACROS
 #include <__undef_macros>
public:
     _LIBCPP_INLINE_VISIBILITY
     bool operator()(const _T1& __x) {return !__p_(__x);}
 
     template <class _T1, class _T2>
     _LIBCPP_INLINE_VISIBILITY
     bool operator()(const _T1& __x, const _T2& __y) {return __p_(__y, __x);}
 };
 
-template <class _Compare, class _InputIterator1, class _InputIterator2,
+template <class _AlgPolicy, class _Compare, class _InputIterator1, class _InputIterator2,
           class _OutputIterator>
 void __half_inplace_merge(_InputIterator1 __first1, _InputIterator1 __last1,
                           _InputIterator2 __first2, _InputIterator2 __last2,
                           _OutputIterator __result, _Compare __comp)
 {
+    using _Ops = _IterOps<_AlgPolicy>;
+
     for (; __first1 != __last1; ++__result)
     {
         if (__first2 == __last2)
         {
             _VSTD::move(__first1, __last1, __result);
             return;
         }
 
         if (__comp(*__first2, *__first1))
         {
-            *__result = _VSTD::move(*__first2);
+            *__result = _Ops::__iter_move(__first2);
             ++__first2;
         }
         else
         {
-            *__result = _VSTD::move(*__first1);
+            *__result = _Ops::__iter_move(__first1);
             ++__first1;
         }
     }
     // __first2 through __last2 are already in the right spot.
 }
 
-template <class _Compare, class _BidirectionalIterator>
+template <class _AlgPolicy, class _Compare, class _BidirectionalIterator>
 void
 __buffered_inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last,
                 _Compare __comp, typename iterator_traits<_BidirectionalIterator>::difference_type __len1,
                                  typename iterator_traits<_BidirectionalIterator>::difference_type __len2,
                 typename iterator_traits<_BidirectionalIterator>::value_type* __buff)
 {
+    using _Ops = _IterOps<_AlgPolicy>;
+
     typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
     __destruct_n __d(0);
     unique_ptr<value_type, __destruct_n&> __h2(__buff, __d);
     if (__len1 <= __len2)
     {
         value_type* __p = __buff;
         for (_BidirectionalIterator __i = __first; __i != __middle; __d.template __incr<value_type>(), (void) ++__i, (void) ++__p)
-            ::new ((void*)__p) value_type(_VSTD::move(*__i));
-        _VSTD::__half_inplace_merge<_Compare>(__buff, __p, __middle, __last, __first, __comp);
+            ::new ((void*)__p) value_type(_Ops::__iter_move(__i));
+        std::__half_inplace_merge<_AlgPolicy, _Compare>(__buff, __p, __middle, __last, __first, __comp);
     }
     else
     {
         value_type* __p = __buff;
         for (_BidirectionalIterator __i = __middle; __i != __last; __d.template __incr<value_type>(), (void) ++__i, (void) ++__p)
-            ::new ((void*)__p) value_type(_VSTD::move(*__i));
+            ::new ((void*)__p) value_type(_Ops::__iter_move(__i));
         typedef reverse_iterator<_BidirectionalIterator> _RBi;
         typedef reverse_iterator<value_type*> _Rv;
         typedef __invert<_Compare> _Inverted;
-        _VSTD::__half_inplace_merge<_Inverted>(_Rv(__p), _Rv(__buff),
+        std::__half_inplace_merge<_AlgPolicy, _Inverted>(_Rv(__p), _Rv(__buff),
                                     _RBi(__middle), _RBi(__first),
                                     _RBi(__last), _Inverted(__comp));
     }
 }
 
-template <class _Compare, class _BidirectionalIterator>
+template <class _AlgPolicy, class _Compare, class _BidirectionalIterator>
 void
 __inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last,
                 _Compare __comp, typename iterator_traits<_BidirectionalIterator>::difference_type __len1,
                                  typename iterator_traits<_BidirectionalIterator>::difference_type __len2,
                 typename iterator_traits<_BidirectionalIterator>::value_type* __buff, ptrdiff_t __buff_size)
 {
+    using _Ops = _IterOps<_AlgPolicy>;
+
     typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type;
     while (true)
     {
         // if __middle == __last, we're done
         if (__len2 == 0)
             return;
         if (__len1 <= __buff_size || __len2 <= __buff_size)
-            return _VSTD::__buffered_inplace_merge<_Compare>
+            return std::__buffered_inplace_merge<_AlgPolicy, _Compare>
                    (__first, __middle, __last, __comp, __len1, __len2, __buff);
         // shrink [__first, __middle) as much as possible (with no moves), returning if it shrinks to 0
         for (; true; ++__first, (void) --__len1)
         {
             if (__len1 == 0)
                 return;
             if (__comp(*__middle, *__first))
                 break;
while (true)
         _BidirectionalIterator __m2;  // "median" of [__middle, __last)
         difference_type __len11;      // distance(__first, __m1)
         difference_type __len21;      // distance(__middle, __m2)
         // binary search smaller range
         if (__len1 < __len2)
         {   // __len >= 1, __len2 >= 2
             __len21 = __len2 / 2;
             __m2 = __middle;
-            _VSTD::advance(__m2, __len21);
+            _Ops::advance(__m2, __len21);
             __m1 = _VSTD::__upper_bound<_Compare>(__first, __middle, *__m2, __comp);
-            __len11 = _VSTD::distance(__first, __m1);
+            __len11 = _Ops::distance(__first, __m1);
         }
         else
         {
             if (__len1 == 1)
             {   // __len1 >= __len2 && __len2 > 0, therefore __len2 == 1
                 // It is known *__first > *__middle
-                swap(*__first, *__middle);
+              _Ops::iter_swap(__first, __middle);
                 return;
             }
             // __len1 >= 2, __len2 >= 1
             __len11 = __len1 / 2;
             __m1 = __first;
-            _VSTD::advance(__m1, __len11);
+            _Ops::advance(__m1, __len11);
             __m2 = std::lower_bound(__middle, __last, *__m1, __comp);
-            __len21 = _VSTD::distance(__middle, __m2);
+            __len21 = _Ops::distance(__middle, __m2);
         }
         difference_type __len12 = __len1 - __len11;  // distance(__m1, __middle)
         difference_type __len22 = __len2 - __len21;  // distance(__m2, __last)
         // [__first, __m1) [__m1, __middle) [__middle, __m2) [__m2, __last)
         // swap middle two partitions
         __middle = _VSTD::rotate(__m1, __middle, __m2);
         // __len12 and __len21 now have swapped meanings
         // merge smaller range with recursive call and larger with tail recursion elimination
         if (__len11 + __len21 < __len12 + __len22)
         {
-            _VSTD::__inplace_merge<_Compare>(__first, __m1, __middle, __comp, __len11, __len21, __buff, __buff_size);
+            std::__inplace_merge<_AlgPolicy, _Compare>(
+                __first, __m1, __middle, __comp, __len11, __len21, __buff, __buff_size);
 //          _VSTD::__inplace_merge<_Compare>(__middle, __m2, __last, __comp, __len12, __len22, __buff, __buff_size);
             __first = __middle;
             __middle = __m2;
             __len1 = __len12;
             __len2 = __len22;
         }
         else
         {
-            _VSTD::__inplace_merge<_Compare>(__middle, __m2, __last, __comp, __len12, __len22, __buff, __buff_size);
+            std::__inplace_merge<_AlgPolicy, _Compare>(
+                __middle, __m2, __last, __comp, __len12, __len22, __buff, __buff_size);
 //          _VSTD::__inplace_merge<_Compare>(__first, __m1, __middle, __comp, __len11, __len21, __buff, __buff_size);
             __last = __middle;
             __middle = __m1;
             __len1 = __len11;
             __len2 = __len21;
         }
     }
 }
 
inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last,
     difference_type __len2 = _VSTD::distance(__middle, __last);
     difference_type __buf_size = _VSTD::min(__len1, __len2);
 // TODO: Remove the use of std::get_temporary_buffer
 _LIBCPP_SUPPRESS_DEPRECATED_PUSH
     pair<value_type*, ptrdiff_t> __buf = _VSTD::get_temporary_buffer<value_type>(__buf_size);
 _LIBCPP_SUPPRESS_DEPRECATED_POP
     unique_ptr<value_type, __return_temporary_buffer> __h(__buf.first);
     typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
-    return _VSTD::__inplace_merge<_Comp_ref>(__first, __middle, __last, __comp, __len1, __len2,
+    return _VSTD::__inplace_merge<_ClassicAlgPolicy, _Comp_ref>(__first, __middle, __last, __comp, __len1, __len2,
                                             __buf.first, __buf.second);
 }
 
 template <class _BidirectionalIterator>
 inline _LIBCPP_INLINE_VISIBILITY
 void
 inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last)
 {

libcxx/include/__algorithm/iterator_operations.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_ITERATOR_OPERATIONS_H
 #define _LIBCPP___ALGORITHM_ITERATOR_OPERATIONS_H
 
 #include <__algorithm/iter_swap.h>
+#include <__algorithm/min_element.h>
+#include <__algorithm/ranges_min_element.h>
 #include <__config>
 #include <__iterator/advance.h>
 #include <__iterator/distance.h>
 #include <__iterator/iter_move.h>
 #include <__iterator/iter_swap.h>
 #include <__iterator/iterator_traits.h>
 #include <__iterator/next.h>
 #include <__utility/forward.h>
 #include <__utility/move.h>
 #include <type_traits>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 template <class _AlgPolicy> struct _IterOps;
 
+template <class _AlgPolicy> struct _Algs;
+
 #if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
 struct _RangeAlgPolicy {};
 
 template <>
 struct _IterOps<_RangeAlgPolicy> {
   static constexpr auto advance = ranges::advance;
   static constexpr auto distance = ranges::distance;
   static constexpr auto __iter_move = ranges::iter_move;
   static constexpr auto iter_swap = ranges::iter_swap;
   static constexpr auto next = ranges::next;
   static constexpr auto __advance_to = ranges::advance;
 };
+
+template <>
+struct _Algs<_RangeAlgPolicy> {
+  static constexpr auto min_element = ranges::min_element;
+};
+
 #endif
 
 struct _ClassicAlgPolicy {};
 
 template <>
 struct _IterOps<_ClassicAlgPolicy> {
 
   // advance
   template <class _Iter, class _Distance>
   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
   static void advance(_Iter& __iter, _Distance __count) {
     std::advance(__iter, __count);
   }
 
   // distance
   template <class _Iter>
   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
   static typename iterator_traits<_Iter>::difference_type distance(_Iter __first, _Iter __last) {
     return std::distance(__first, __last);
struct _IterOps<_ClassicAlgPolicy> {
   // next
   template <class _Iterator>
   _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR_AFTER_CXX11
   _Iterator next(_Iterator, _Iterator __last) {
     return __last;
   }
 
   template <class _Iter>
-  _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR_AFTER_CXX11 void __advance_to(_Iter& __first, _Iter __last) {
+  _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR_AFTER_CXX11
+  void __advance_to(_Iter& __first, _Iter __last) {
     __first = __last;
   }
 };
 
+
+template <>
+struct _Algs<_ClassicAlgPolicy> {
+
+  // min_element
+  template <class _Iter>
+  _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR_AFTER_CXX11
+  _Iter min_element(_Iter __first, _Iter __last) {
+    return std::min_element(std::move(__first), std::move(__last));
+  }
+  template <class _Iter, class _Comp>
+  _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR_AFTER_CXX11
+  _Iter min_element(_Iter __first, _Iter __last, _Comp __comp) {
+    return std::min_element(std::move(__first), std::move(__last), std::move(__comp));
+  }
+
+};
+
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_ITERATOR_OPERATIONS_H

libcxx/include/__algorithm/make_heap.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_MAKE_HEAP_H
 #define _LIBCPP___ALGORITHM_MAKE_HEAP_H
 
 #include <__algorithm/comp.h>
 #include <__algorithm/comp_ref_type.h>
+#include <__algorithm/iterator_operations.h>
 #include <__algorithm/sift_down.h>
 #include <__config>
 #include <__iterator/iterator_traits.h>
 #include <__utility/move.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
-template <class _Compare, class _RandomAccessIterator>
+template <class _AlgPolicy, class _Compare, class _RandomAccessIterator>
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
 void __make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare& __comp) {
   using _CompRef = typename __comp_ref_type<_Compare>::type;
   _CompRef __comp_ref = __comp;
 
   using difference_type = typename iterator_traits<_RandomAccessIterator>::difference_type;
   difference_type __n = __last - __first;
   if (__n > 1) {
     // start from the first parent, there is no need to consider children
     for (difference_type __start = (__n - 2) / 2; __start >= 0; --__start) {
-        std::__sift_down<_CompRef>(__first, __comp_ref, __n, __first + __start);
+        std::__sift_down<_AlgPolicy, _CompRef>(__first, __comp_ref, __n, __first + __start);
     }
   }
 }
 
 template <class _RandomAccessIterator, class _Compare>
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17
 void make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) {
-  std::__make_heap(std::move(__first), std::move(__last), __comp);
+  std::__make_heap<_ClassicAlgPolicy>(std::move(__first), std::move(__last), __comp);
 }
 
 template <class _RandomAccessIterator>
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17
 void make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) {
   std::make_heap(std::move(__first), std::move(__last),
       __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_MAKE_HEAP_H

libcxx/include/__algorithm/nth_element.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_NTH_ELEMENT_H
 #define _LIBCPP___ALGORITHM_NTH_ELEMENT_H
 
 #include <__algorithm/comp.h>
 #include <__algorithm/comp_ref_type.h>
+#include <__algorithm/iterator_operations.h>
 #include <__algorithm/sort.h>
 #include <__config>
 #include <__debug>
 #include <__debug_utils/randomize_range.h>
 #include <__iterator/iterator_traits.h>
 #include <__utility/move.h>
-#include <__utility/swap.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 template<class _Compare, class _RandomAccessIterator>
 _LIBCPP_CONSTEXPR_AFTER_CXX11 bool
 __nth_element_find_guard(_RandomAccessIterator& __i, _RandomAccessIterator& __j,
                          _RandomAccessIterator __m, _Compare __comp)
 {
     // manually guard downward moving __j against __i
     while (true) {
         if (__i == --__j) {
             return false;
         }
         if (__comp(*__j, *__m)) {
             return true;  // found guard for downward moving __j, now use unguarded partition
         }
     }
 }
 
-template <class _Compare, class _RandomAccessIterator>
+template <class _AlgPolicy, class _Compare, class _RandomAccessIterator>
 _LIBCPP_CONSTEXPR_AFTER_CXX11 void
 __nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last, _Compare __comp)
 {
+    using _Ops = _IterOps<_AlgPolicy>;
+
     // _Compare is known to be a reference type
     typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
     const difference_type __limit = 7;
     while (true)
     {
         if (__nth == __last)
             return;
         difference_type __len = __last - __first;
         switch (__len)
         {
         case 0:
         case 1:
             return;
         case 2:
             if (__comp(*--__last, *__first))
-                swap(*__first, *__last);
+                _Ops::iter_swap(__first, __last);
             return;
         case 3:
             {
             _RandomAccessIterator __m = __first;
-            _VSTD::__sort3<_Compare>(__first, ++__m, --__last, __comp);
+            std::__sort3<_AlgPolicy, _Compare>(__first, ++__m, --__last, __comp);
             return;
             }
         }
         if (__len <= __limit)
         {
-            _VSTD::__selection_sort<_Compare>(__first, __last, __comp);
+            std::__selection_sort<_AlgPolicy, _Compare>(__first, __last, __comp);
             return;
         }
         // __len > __limit >= 3
         _RandomAccessIterator __m = __first + __len/2;
         _RandomAccessIterator __lm1 = __last;
-        unsigned __n_swaps = _VSTD::__sort3<_Compare>(__first, __m, --__lm1, __comp);
+        unsigned __n_swaps = std::__sort3<_AlgPolicy, _Compare>(__first, __m, --__lm1, __comp);
         // *__m is median
         // partition [__first, __m) < *__m and *__m <= [__m, __last)
         // (this inhibits tossing elements equivalent to __m around unnecessarily)
         _RandomAccessIterator __i = __first;
         _RandomAccessIterator __j = __lm1;
         // j points beyond range to be tested, *__lm1 is known to be <= *__m
         // The search going up is known to be guarded but the search coming down isn't.
         // Prime the downward search with a guard.
         if (!__comp(*__i, *__m))  // if *__first == *__m
         {
             // *__first == *__m, *__first doesn't go in first part
             if (_VSTD::__nth_element_find_guard<_Compare>(__i, __j, __m, __comp)) {
-                swap(*__i, *__j);
+                _Ops::iter_swap(__i, __j);
                 ++__n_swaps;
             } else {
                 // *__first == *__m, *__m <= all other elements
                 // Partition instead into [__first, __i) == *__first and *__first < [__i, __last)
                 ++__i;  // __first + 1
                 __j = __last;
                 if (!__comp(*__first, *--__j)) {  // we need a guard if *__first == *(__last-1)
                     while (true) {
                         if (__i == __j) {
                             return;  // [__first, __last) all equivalent elements
                         } else if (__comp(*__first, *__i)) {
-                            swap(*__i, *__j);
+                            _Ops::iter_swap(__i, __j);
                             ++__n_swaps;
                             ++__i;
                             break;
                         }
                         ++__i;
                     }
                 }
                 // [__first, __i) == *__first and *__first < [__j, __last) and __j == __last - 1
                 if (__i == __j) {
                     return;
                 }
                 while (true) {
                     while (!__comp(*__first, *__i))
                         ++__i;
                     while (__comp(*__first, *--__j))
                         ;
                     if (__i >= __j)
                         break;
-                    swap(*__i, *__j);
+                    _Ops::iter_swap(__i, __j);
                     ++__n_swaps;
                     ++__i;
                 }
                 // [__first, __i) == *__first and *__first < [__i, __last)
                 // The first part is sorted,
                 if (__nth < __i) {
                     return;
                 }
while (true)
                 // __m still guards upward moving __i
                 while (__comp(*__i, *__m))
                     ++__i;
                 // It is now known that a guard exists for downward moving __j
                 while (!__comp(*--__j, *__m))
                     ;
                 if (__i >= __j)
                     break;
-                swap(*__i, *__j);
+                _Ops::iter_swap(__i, __j);
                 ++__n_swaps;
                 // It is known that __m != __j
                 // If __m just moved, follow it
                 if (__m == __i)
                     __m = __j;
                 ++__i;
             }
         }
         // [__first, __i) < *__m and *__m <= [__i, __last)
         if (__i != __m && __comp(*__m, *__i))
         {
-            swap(*__i, *__m);
+            _Ops::iter_swap(__i, __m);
             ++__n_swaps;
         }
         // [__first, __i) < *__i and *__i <= [__i+1, __last)
         if (__nth == __i)
             return;
         if (__n_swaps == 0)
         {
             // We were given a perfectly partitioned sequence.  Coincidence?
while (true)
         else
         {
             // _VSTD::__nth_element<_Compare>(__i+1, __nth, __last, __comp);
             __first = ++__i;
         }
     }
 }
 
-template <class _RandomAccessIterator, class _Compare>
+template <class _AlgPolicy, class _RandomAccessIterator, class _Compare>
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17
 void __nth_element_impl(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last,
                         _Compare& __comp) {
   if (__nth == __last)
     return;
 
   std::__debug_randomize_range(__first, __last);
 
   using _Comp_ref = typename __comp_ref_type<_Compare>::type;
-  std::__nth_element<_Comp_ref>(__first, __nth, __last, __comp);
+  std::__nth_element<_AlgPolicy, _Comp_ref>(__first, __nth, __last, __comp);
 
   std::__debug_randomize_range(__first, __nth);
   if (__nth != __last) {
     std::__debug_randomize_range(++__nth, __last);
   }
 }
 
 template <class _RandomAccessIterator, class _Compare>
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17
 void nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last,
                  _Compare __comp) {
-  std::__nth_element_impl(std::move(__first), std::move(__nth), std::move(__last), __comp);
+  std::__nth_element_impl<_ClassicAlgPolicy>(std::move(__first), std::move(__nth), std::move(__last), __comp);
 }
 
 template <class _RandomAccessIterator>
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17
 void nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last) {
   std::nth_element(std::move(__first), std::move(__nth), std::move(__last), __less<typename
       iterator_traits<_RandomAccessIterator>::value_type>());
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_NTH_ELEMENT_H

libcxx/include/__algorithm/partial_sort.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_PARTIAL_SORT_H
 #define _LIBCPP___ALGORITHM_PARTIAL_SORT_H
 
 #include <__algorithm/comp.h>
 #include <__algorithm/comp_ref_type.h>
+#include <__algorithm/iterator_operations.h>
 #include <__algorithm/make_heap.h>
 #include <__algorithm/sift_down.h>
 #include <__algorithm/sort_heap.h>
 #include <__config>
 #include <__debug>
 #include <__debug_utils/randomize_range.h>
 #include <__iterator/iterator_traits.h>
-#include <__utility/swap.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
-template <class _Compare, class _RandomAccessIterator>
+template <class _AlgPolicy, class _Compare, class _RandomAccessIterator>
 _LIBCPP_CONSTEXPR_AFTER_CXX17 void
 __partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last,
                _Compare __comp)
 {
     if (__first == __middle)
         return;
-    _VSTD::__make_heap<_Compare>(__first, __middle, __comp);
+    std::__make_heap<_AlgPolicy, _Compare>(__first, __middle, __comp);
     typename iterator_traits<_RandomAccessIterator>::difference_type __len = __middle - __first;
     for (_RandomAccessIterator __i = __middle; __i != __last; ++__i)
     {
         if (__comp(*__i, *__first))
         {
-            swap(*__i, *__first);
-            _VSTD::__sift_down<_Compare>(__first, __comp, __len, __first);
+            _IterOps<_AlgPolicy>::iter_swap(__i, __first);
+            std::__sift_down<_AlgPolicy, _Compare>(__first, __comp, __len, __first);
         }
     }
-    _VSTD::__sort_heap<_Compare>(__first, __middle, __comp);
+    std::__sort_heap<_AlgPolicy, _Compare>(__first, __middle, __comp);
 }
 
 template <class _RandomAccessIterator, class _Compare>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 void
 partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last,
              _Compare __comp)
 {
   std::__debug_randomize_range(__first, __last);
   typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
-  _VSTD::__partial_sort<_Comp_ref>(__first, __middle, __last, __comp);
+  std::__partial_sort<_ClassicAlgPolicy, _Comp_ref>(__first, __middle, __last, __comp);
   std::__debug_randomize_range(__middle, __last);
 }
 
 template <class _RandomAccessIterator>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 void
 partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last)
 {
     _VSTD::partial_sort(__first, __middle, __last,
                         __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_PARTIAL_SORT_H

libcxx/include/__algorithm/partial_sort_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_PARTIAL_SORT_COPY_H
 #define _LIBCPP___ALGORITHM_PARTIAL_SORT_COPY_H
 
 #include <__algorithm/comp.h>
 #include <__algorithm/comp_ref_type.h>
+#include <__algorithm/iterator_operations.h>
 #include <__algorithm/make_heap.h>
 #include <__algorithm/sift_down.h>
 #include <__algorithm/sort_heap.h>
 #include <__config>
 #include <__iterator/iterator_traits.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
-template <class _Compare, class _InputIterator, class _RandomAccessIterator>
+template <class _AlgPolicy, class _Compare, class _InputIterator, class _RandomAccessIterator>
 _LIBCPP_CONSTEXPR_AFTER_CXX17 _RandomAccessIterator
 __partial_sort_copy(_InputIterator __first, _InputIterator __last,
                     _RandomAccessIterator __result_first, _RandomAccessIterator __result_last, _Compare __comp)
 {
     _RandomAccessIterator __r = __result_first;
     if (__r != __result_last)
     {
         for (; __first != __last && __r != __result_last; ++__first, (void) ++__r)
             *__r = *__first;
-        _VSTD::__make_heap<_Compare>(__result_first, __r, __comp);
+        std::__make_heap<_AlgPolicy, _Compare>(__result_first, __r, __comp);
         typename iterator_traits<_RandomAccessIterator>::difference_type __len = __r - __result_first;
         for (; __first != __last; ++__first)
             if (__comp(*__first, *__result_first))
             {
                 *__result_first = *__first;
-                _VSTD::__sift_down<_Compare>(__result_first, __comp, __len, __result_first);
+                std::__sift_down<_AlgPolicy, _Compare>(__result_first, __comp, __len, __result_first);
             }
-        _VSTD::__sort_heap<_Compare>(__result_first, __r, __comp);
+        std::__sort_heap<_AlgPolicy, _Compare>(__result_first, __r, __comp);
     }
     return __r;
 }
 
 template <class _InputIterator, class _RandomAccessIterator, class _Compare>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 _RandomAccessIterator
 partial_sort_copy(_InputIterator __first, _InputIterator __last,
                   _RandomAccessIterator __result_first, _RandomAccessIterator __result_last, _Compare __comp)
 {
     typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
-    return _VSTD::__partial_sort_copy<_Comp_ref>(__first, __last, __result_first, __result_last, __comp);
+    return std::__partial_sort_copy<_ClassicAlgPolicy, _Comp_ref>(
+        __first, __last, __result_first, __result_last, __comp);
 }
 
 template <class _InputIterator, class _RandomAccessIterator>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 _RandomAccessIterator
 partial_sort_copy(_InputIterator __first, _InputIterator __last,
                   _RandomAccessIterator __result_first, _RandomAccessIterator __result_last)
 {
     return _VSTD::partial_sort_copy(__first, __last, __result_first, __result_last,
                                    __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_PARTIAL_SORT_COPY_H

libcxx/include/__algorithm/pop_heap.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_POP_HEAP_H
 #define _LIBCPP___ALGORITHM_POP_HEAP_H
 
 #include <__algorithm/comp.h>
 #include <__algorithm/comp_ref_type.h>
+#include <__algorithm/iterator_operations.h>
 #include <__algorithm/push_heap.h>
 #include <__algorithm/sift_down.h>
 #include <__assert>
 #include <__config>
 #include <__iterator/iterator_traits.h>
 #include <__utility/move.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
-template <class _Compare, class _RandomAccessIterator>
+template <class _AlgPolicy, class _Compare, class _RandomAccessIterator>
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
 void __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare& __comp,
     typename iterator_traits<_RandomAccessIterator>::difference_type __len) {
   _LIBCPP_ASSERT(__len > 0, "The heap given to pop_heap must be non-empty");
 
   using _CompRef = typename __comp_ref_type<_Compare>::type;
   _CompRef __comp_ref = __comp;
 
   using value_type = typename iterator_traits<_RandomAccessIterator>::value_type;
   if (__len > 1) {
     value_type __top = std::move(*__first);  // create a hole at __first
-    _RandomAccessIterator __hole = std::__floyd_sift_down<_CompRef>(__first, __comp_ref, __len);
+    _RandomAccessIterator __hole = std::__floyd_sift_down<_AlgPolicy, _CompRef>(__first, __comp_ref, __len);
     --__last;
 
     if (__hole == __last) {
       *__hole = std::move(__top);
     } else {
-      *__hole = std::move(*__last);
+      *__hole = _IterOps<_AlgPolicy>::__iter_move(__last);
       ++__hole;
       *__last = std::move(__top);
-      std::__sift_up<_CompRef>(__first, __hole, __comp_ref, __hole - __first);
+      std::__sift_up<_AlgPolicy, _CompRef>(__first, __hole, __comp_ref, __hole - __first);
     }
   }
 }
 
 template <class _RandomAccessIterator, class _Compare>
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17
 void pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) {
   typename iterator_traits<_RandomAccessIterator>::difference_type __len = __last - __first;
-  std::__pop_heap(std::move(__first), std::move(__last), __comp, __len);
+  std::__pop_heap<_ClassicAlgPolicy>(std::move(__first), std::move(__last), __comp, __len);
 }
 
 template <class _RandomAccessIterator>
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17
 void pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) {
   std::pop_heap(std::move(__first), std::move(__last),
       __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_POP_HEAP_H

libcxx/include/__algorithm/push_heap.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_PUSH_HEAP_H
 #define _LIBCPP___ALGORITHM_PUSH_HEAP_H
 
 #include <__algorithm/comp.h>
 #include <__algorithm/comp_ref_type.h>
+#include <__algorithm/iterator_operations.h>
 #include <__config>
 #include <__iterator/iterator_traits.h>
 #include <__utility/move.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
-template <class _Compare, class _RandomAccessIterator>
+template <class _AlgPolicy, class _Compare, class _RandomAccessIterator>
 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
 void __sift_up(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
         typename iterator_traits<_RandomAccessIterator>::difference_type __len) {
   using value_type = typename iterator_traits<_RandomAccessIterator>::value_type;
 
   if (__len > 1) {
     __len = (__len - 2) / 2;
     _RandomAccessIterator __ptr = __first + __len;
 
     if (__comp(*__ptr, *--__last)) {
-      value_type __t(std::move(*__last));
+      value_type __t(_IterOps<_AlgPolicy>::__iter_move(__last));
       do {
-        *__last = std::move(*__ptr);
+        *__last = _IterOps<_AlgPolicy>::__iter_move(__ptr);
         __last = __ptr;
         if (__len == 0)
           break;
         __len = (__len - 1) / 2;
         __ptr = __first + __len;
       } while (__comp(*__ptr, __t));
 
       *__last = std::move(__t);
     }
   }
 }
 
-template <class _RandomAccessIterator, class _Compare>
+template <class _AlgPolicy, class _RandomAccessIterator, class _Compare>
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
 void __push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare& __comp) {
   using _CompRef = typename __comp_ref_type<_Compare>::type;
   typename iterator_traits<_RandomAccessIterator>::difference_type __len = __last - __first;
-  std::__sift_up<_CompRef>(std::move(__first), std::move(__last), __comp, __len);
+  std::__sift_up<_AlgPolicy, _CompRef>(std::move(__first), std::move(__last), __comp, __len);
 }
 
 template <class _RandomAccessIterator, class _Compare>
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17
 void push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) {
-  std::__push_heap(std::move(__first), std::move(__last), __comp);
+  std::__push_heap<_ClassicAlgPolicy>(std::move(__first), std::move(__last), __comp);
 }
 
 template <class _RandomAccessIterator>
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17
 void push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) {
   std::push_heap(std::move(__first), std::move(__last),
       __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_PUSH_HEAP_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>
 

 
 namespace __copy_backward {
 struct __fn {
 
   template <bidirectional_iterator _InIter1, sentinel_for<_InIter1> _Sent1, bidirectional_iterator _InIter2>
     requires indirectly_copyable<_InIter1, _InIter2>
   _LIBCPP_HIDE_FROM_ABI constexpr
   copy_backward_result<_InIter1, _InIter2> operator()(_InIter1 __first, _Sent1 __last, _InIter2 __result) const {
-    auto __ret = std::__copy_backward(std::move(__first), std::move(__last), std::move(__result));
+    auto __ret = std::__copy_backward<_RangeAlgPolicy>(std::move(__first), std::move(__last), std::move(__result));
     return {std::move(__ret.first), std::move(__ret.second)};
   }
 
   template <bidirectional_range _Range, bidirectional_iterator _Iter>
     requires indirectly_copyable<iterator_t<_Range>, _Iter>
   _LIBCPP_HIDE_FROM_ABI constexpr
   copy_backward_result<borrowed_iterator_t<_Range>, _Iter> operator()(_Range&& __r, _Iter __result) const {
-    auto __ret = std::__copy_backward(ranges::begin(__r),
+    auto __ret = std::__copy_backward<_RangeAlgPolicy>(ranges::begin(__r),
                                                        ranges::end(__r),
                                                        std::move(__result));
     return {std::move(__ret.first), std::move(__ret.second)};
   }
 };
 } // namespace __copy_backward
 
 inline namespace __cpo {
   inline constexpr auto copy_backward = __copy_backward::__fn{};
 } // namespace __cpo
 } // namespace ranges
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
 
 #endif // _LIBCPP___ALGORITHM_RANGES_COPY_BACKWARD_H

libcxx/include/__algorithm/ranges_fill.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
 //
 //===----------------------------------------------------------------------===//
 

 _LIBCPP_BEGIN_NAMESPACE_STD
 
 namespace ranges {
 namespace __fill {
 struct __fn {
   template <class _Type, output_iterator<const _Type&> _Iter, sentinel_for<_Iter> _Sent>
   _LIBCPP_HIDE_FROM_ABI constexpr
   _Iter operator()(_Iter __first, _Sent __last, const _Type& __value) const {
-    if constexpr(random_access_iterator<_Iter>) {
+    if constexpr(random_access_iterator<_Iter> && sized_sentinel_for<_Sent, _Iter>) {
       return ranges::fill_n(__first, __last - __first, __value);
     } else {
       for (; __first != __last; ++__first)
         *__first = __value;
       return __first;
     }
   }
 

libcxx/include/__algorithm/ranges_make_heap.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_MAKE_HEAP_H
 #define _LIBCPP___ALGORITHM_RANGES_MAKE_HEAP_H
 
+#include <__algorithm/iterator_operations.h>
 #include <__algorithm/make_heap.h>
 #include <__algorithm/make_projected.h>
 #include <__concepts/same_as.h>
 #include <__config>
 #include <__functional/identity.h>
 #include <__functional/invoke.h>
 #include <__functional/ranges_operations.h>
 #include <__iterator/concepts.h>

 
 struct __fn {
   template <class _Iter, class _Sent, class _Comp, class _Proj>
   _LIBCPP_HIDE_FROM_ABI constexpr static
   _Iter __make_heap_fn_impl(_Iter __first, _Sent __last, _Comp& __comp, _Proj& __proj) {
     auto __last_iter = ranges::next(__first, __last);
 
     auto&& __projected_comp = ranges::__make_projected_comp(__comp, __proj);
-    std::__make_heap(std::move(__first), __last_iter, __projected_comp);
+    std::__make_heap<_RangeAlgPolicy>(std::move(__first), __last_iter, __projected_comp);
 
     return __last_iter;
   }
 
   template <random_access_iterator _Iter, sentinel_for<_Iter> _Sent, class _Comp = ranges::less, class _Proj = identity>
     requires sortable<_Iter, _Comp, _Proj>
   _LIBCPP_HIDE_FROM_ABI constexpr
   _Iter operator()(_Iter __first, _Sent __last, _Comp __comp = {}, _Proj __proj = {}) const {

libcxx/include/__algorithm/ranges_nth_element.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_NTH_ELEMENT_H
 #define _LIBCPP___ALGORITHM_RANGES_NTH_ELEMENT_H
 
+#include <__algorithm/iterator_operations.h>
 #include <__algorithm/make_projected.h>
 #include <__algorithm/nth_element.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>

 
 struct __fn {
   template <class _Iter, class _Sent, class _Comp, class _Proj>
   _LIBCPP_HIDE_FROM_ABI constexpr static
   _Iter __nth_element_fn_impl(_Iter __first, _Iter __nth, _Sent __last, _Comp& __comp, _Proj& __proj) {
     auto __last_iter = ranges::next(__first, __last);
 
     auto&& __projected_comp = ranges::__make_projected_comp(__comp, __proj);
-    std::__nth_element_impl(std::move(__first), std::move(__nth), __last_iter, __projected_comp);
+    std::__nth_element_impl<_RangeAlgPolicy>(std::move(__first), std::move(__nth), __last_iter, __projected_comp);
 
     return __last_iter;
   }
 
   template <random_access_iterator _Iter, sentinel_for<_Iter> _Sent, class _Comp = ranges::less, class _Proj = identity>
     requires sortable<_Iter, _Comp, _Proj>
   _LIBCPP_HIDE_FROM_ABI constexpr
   _Iter operator()(_Iter __first, _Iter __nth, _Sent __last, _Comp __comp = {}, _Proj __proj = {}) const {

libcxx/include/__algorithm/ranges_pop_heap.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_POP_HEAP_H
 #define _LIBCPP___ALGORITHM_RANGES_POP_HEAP_H
 
+#include <__algorithm/iterator_operations.h>
 #include <__algorithm/make_projected.h>
 #include <__algorithm/pop_heap.h>
 #include <__concepts/same_as.h>
 #include <__config>
 #include <__functional/identity.h>
 #include <__functional/invoke.h>
 #include <__functional/ranges_operations.h>
 #include <__iterator/concepts.h>

 struct __fn {
   template <class _Iter, class _Sent, class _Comp, class _Proj>
   _LIBCPP_HIDE_FROM_ABI constexpr static
   _Iter __pop_heap_fn_impl(_Iter __first, _Sent __last, _Comp& __comp, _Proj& __proj) {
     auto __last_iter = ranges::next(__first, __last);
     auto __len = __last_iter - __first;
 
     auto&& __projected_comp = ranges::__make_projected_comp(__comp, __proj);
-    std::__pop_heap(std::move(__first), __last_iter, __projected_comp, __len);
+    std::__pop_heap<_RangeAlgPolicy>(std::move(__first), __last_iter, __projected_comp, __len);
 
     return __last_iter;
   }
 
   template <random_access_iterator _Iter, sentinel_for<_Iter> _Sent, class _Comp = ranges::less, class _Proj = identity>
     requires sortable<_Iter, _Comp, _Proj>
   _LIBCPP_HIDE_FROM_ABI constexpr
   _Iter operator()(_Iter __first, _Sent __last, _Comp __comp = {}, _Proj __proj = {}) const {

libcxx/include/__algorithm/ranges_push_heap.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_PUSH_HEAP_H
 #define _LIBCPP___ALGORITHM_RANGES_PUSH_HEAP_H
 
+#include <__algorithm/iterator_operations.h>
 #include <__algorithm/make_projected.h>
 #include <__algorithm/push_heap.h>
 #include <__concepts/same_as.h>
 #include <__config>
 #include <__functional/identity.h>
 #include <__functional/invoke.h>
 #include <__functional/ranges_operations.h>
 #include <__iterator/concepts.h>

 
 struct __fn {
   template <class _Iter, class _Sent, class _Comp, class _Proj>
   _LIBCPP_HIDE_FROM_ABI constexpr static
   _Iter __push_heap_fn_impl(_Iter __first, _Sent __last, _Comp& __comp, _Proj& __proj) {
     auto __last_iter = ranges::next(__first, __last);
 
     auto&& __projected_comp = ranges::__make_projected_comp(__comp, __proj);
-    std::__push_heap(std::move(__first), __last_iter, __projected_comp);
+    std::__push_heap<_RangeAlgPolicy>(std::move(__first), __last_iter, __projected_comp);
 
     return __last_iter;
   }
 
   template <random_access_iterator _Iter, sentinel_for<_Iter> _Sent, class _Comp = ranges::less, class _Proj = identity>
     requires sortable<_Iter, _Comp, _Proj>
   _LIBCPP_HIDE_FROM_ABI constexpr
   _Iter operator()(_Iter __first, _Sent __last, _Comp __comp = {}, _Proj __proj = {}) const {

libcxx/include/__algorithm/ranges_sort.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_SORT_H
 #define _LIBCPP___ALGORITHM_RANGES_SORT_H
 
+#include <__algorithm/iterator_operations.h>
 #include <__algorithm/make_projected.h>
 #include <__algorithm/sort.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>

 
 struct __fn {
   template <class _Iter, class _Sent, class _Comp, class _Proj>
   _LIBCPP_HIDE_FROM_ABI constexpr static
   _Iter __sort_fn_impl(_Iter __first, _Sent __last, _Comp& __comp, _Proj& __proj) {
     auto __last_iter = ranges::next(__first, __last);
 
     auto&& __projected_comp = ranges::__make_projected_comp(__comp, __proj);
-    std::__sort_impl(std::move(__first), __last_iter, __projected_comp);
+    std::__sort_impl<_RangeAlgPolicy>(std::move(__first), __last_iter, __projected_comp);
 
     return __last_iter;
   }
 
   template <random_access_iterator _Iter, sentinel_for<_Iter> _Sent, class _Comp = ranges::less, class _Proj = identity>
     requires sortable<_Iter, _Comp, _Proj>
   _LIBCPP_HIDE_FROM_ABI constexpr
   _Iter operator()(_Iter __first, _Sent __last, _Comp __comp = {}, _Proj __proj = {}) const {

libcxx/include/__algorithm/ranges_sort_heap.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_SORT_HEAP_H
 #define _LIBCPP___ALGORITHM_RANGES_SORT_HEAP_H
 
+#include <__algorithm/iterator_operations.h>
 #include <__algorithm/make_projected.h>
 #include <__algorithm/sort_heap.h>
 #include <__concepts/same_as.h>
 #include <__config>
 #include <__functional/identity.h>
 #include <__functional/invoke.h>
 #include <__functional/ranges_operations.h>
 #include <__iterator/concepts.h>

 
 struct __fn {
   template <class _Iter, class _Sent, class _Comp, class _Proj>
   _LIBCPP_HIDE_FROM_ABI constexpr static
   _Iter __sort_heap_fn_impl(_Iter __first, _Sent __last, _Comp& __comp, _Proj& __proj) {
     auto __last_iter = ranges::next(__first, __last);
 
     auto&& __projected_comp = ranges::__make_projected_comp(__comp, __proj);
-    std::__sort_heap(std::move(__first), __last_iter, __projected_comp);
+    std::__sort_heap<_RangeAlgPolicy>(std::move(__first), __last_iter, __projected_comp);
 
     return __last_iter;
   }
 
   template <random_access_iterator _Iter, sentinel_for<_Iter> _Sent, class _Comp = ranges::less, class _Proj = identity>
     requires sortable<_Iter, _Comp, _Proj>
   _LIBCPP_HIDE_FROM_ABI constexpr
   _Iter operator()(_Iter __first, _Sent __last, _Comp __comp = {}, _Proj __proj = {}) const {

libcxx/include/__algorithm/ranges_stable_sort.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_STABLE_SORT_H
 #define _LIBCPP___ALGORITHM_RANGES_STABLE_SORT_H
 
+#include <__algorithm/iterator_operations.h>
 #include <__algorithm/make_projected.h>
 #include <__algorithm/stable_sort.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>

 
 struct __fn {
   template <class _Iter, class _Sent, class _Comp, class _Proj>
   _LIBCPP_HIDE_FROM_ABI
   static _Iter __stable_sort_fn_impl(_Iter __first, _Sent __last, _Comp& __comp, _Proj& __proj) {
     auto __last_iter = ranges::next(__first, __last);
 
     auto&& __projected_comp = ranges::__make_projected_comp(__comp, __proj);
-    std::__stable_sort_impl(std::move(__first), __last_iter, __projected_comp);
+    std::__stable_sort_impl<_RangeAlgPolicy>(std::move(__first), __last_iter, __projected_comp);
 
     return __last_iter;
   }
 
   template <random_access_iterator _Iter, sentinel_for<_Iter> _Sent, class _Comp = ranges::less, class _Proj = identity>
     requires sortable<_Iter, _Comp, _Proj>
   _LIBCPP_HIDE_FROM_ABI
   _Iter operator()(_Iter __first, _Sent __last, _Comp __comp = {}, _Proj __proj = {}) const {

libcxx/include/__algorithm/sift_down.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_SIFT_DOWN_H
 #define _LIBCPP___ALGORITHM_SIFT_DOWN_H
 
+#include <__algorithm/iterator_operations.h>
 #include <__assert>
 #include <__config>
 #include <__iterator/iterator_traits.h>
 #include <__utility/move.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
-template <class _Compare, class _RandomAccessIterator>
+template <class _AlgPolicy, class _Compare, class _RandomAccessIterator>
 _LIBCPP_CONSTEXPR_AFTER_CXX11 void
 __sift_down(_RandomAccessIterator __first, _Compare __comp,
             typename iterator_traits<_RandomAccessIterator>::difference_type __len,
             _RandomAccessIterator __start)
 {
+    using _Ops = _IterOps<_AlgPolicy>;
+
     typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
     typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
     // left-child of __start is at 2 * __start + 1
     // right-child of __start is at 2 * __start + 2
     difference_type __child = __start - __first;
 
     if (__len < 2 || (__len - 2) / 2 < __child)
         return;
 
     __child = 2 * __child + 1;
     _RandomAccessIterator __child_i = __first + __child;
 
     if ((__child + 1) < __len && __comp(*__child_i, *(__child_i + difference_type(1)))) {
         // right-child exists and is greater than left-child
         ++__child_i;
         ++__child;
     }
 
     // check if we are in heap-order
     if (__comp(*__child_i, *__start))
         // we are, __start is larger than its largest child
         return;
 
-    value_type __top(_VSTD::move(*__start));
+    value_type __top(_Ops::__iter_move(__start));
     do
     {
         // we are not in heap-order, swap the parent with its largest child
-        *__start = _VSTD::move(*__child_i);
+        *__start = _Ops::__iter_move(__child_i);
         __start = __child_i;
 
         if ((__len - 2) / 2 < __child)
             break;
 
         // recompute the child based off of the updated parent
         __child = 2 * __child + 1;
         __child_i = __first + __child;
 
         if ((__child + 1) < __len && __comp(*__child_i, *(__child_i + difference_type(1)))) {
             // right-child exists and is greater than left-child
             ++__child_i;
             ++__child;
         }
 
         // check if we are in heap-order
     } while (!__comp(*__child_i, __top));
     *__start = _VSTD::move(__top);
 }
 
-template <class _Compare, class _RandomAccessIterator>
+template <class _AlgPolicy, class _Compare, class _RandomAccessIterator>
 _LIBCPP_CONSTEXPR_AFTER_CXX11 _RandomAccessIterator
 __floyd_sift_down(_RandomAccessIterator __first, _Compare __comp,
                   typename iterator_traits<_RandomAccessIterator>::difference_type __len)
 {
     using difference_type = typename iterator_traits<_RandomAccessIterator>::difference_type;
     _LIBCPP_ASSERT(__len >= 2, "shouldn't be called unless __len >= 2");
 
     _RandomAccessIterator __hole = __first;
     _RandomAccessIterator __child_i = __first;
     difference_type __child = 0;
 
     while (true) {
         __child_i += difference_type(__child + 1);
         __child = 2 * __child + 1;
 
         if ((__child + 1) < __len && __comp(*__child_i, *(__child_i + difference_type(1)))) {
             // right-child exists and is greater than left-child
             ++__child_i;
             ++__child;
         }
 
         // swap __hole with its largest child
-        *__hole = std::move(*__child_i);
+        *__hole = _IterOps<_AlgPolicy>::__iter_move(__child_i);
         __hole = __child_i;
 
         // if __hole is now a leaf, we're done
         if (__child > (__len - 2) / 2)
             return __hole;
     }
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_SIFT_DOWN_H

libcxx/include/__algorithm/sort.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_SORT_H
 #define _LIBCPP___ALGORITHM_SORT_H
 
 #include <__algorithm/comp.h>
 #include <__algorithm/comp_ref_type.h>
+#include <__algorithm/iterator_operations.h>
 #include <__algorithm/min_element.h>
 #include <__algorithm/partial_sort.h>
 #include <__algorithm/unwrap_iter.h>
 #include <__bits>
 #include <__config>
 #include <__debug>
 #include <__debug_utils/randomize_range.h>
 #include <__functional/operations.h>
 #include <__functional/ranges_operations.h>
 #include <__iterator/iterator_traits.h>
-#include <__utility/swap.h>
 #include <climits>
 #include <memory>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 // stable, 2-3 compares, 0-2 swaps
 
-template <class _Compare, class _ForwardIterator>
+template <class _AlgPolicy, class _Compare, class _ForwardIterator>
 _LIBCPP_CONSTEXPR_AFTER_CXX11 unsigned __sort3(_ForwardIterator __x, _ForwardIterator __y, _ForwardIterator __z,
                                                _Compare __c) {
+  using _Ops = _IterOps<_AlgPolicy>;
+
   unsigned __r = 0;
   if (!__c(*__y, *__x))   // if x <= y
   {
     if (!__c(*__z, *__y)) // if y <= z
       return __r;         // x <= y && y <= z
                           // x <= y && y > z
-    swap(*__y, *__z);     // x <= z && y < z
+    _Ops::iter_swap(__y, __z);     // x <= z && y < z
     __r = 1;
     if (__c(*__y, *__x))  // if x > y
     {
-      swap(*__x, *__y);   // x < y && y <= z
+      _Ops::iter_swap(__x, __y);   // x < y && y <= z
       __r = 2;
     }
     return __r;           // x <= y && y < z
   }
   if (__c(*__z, *__y))    // x > y, if y > z
   {
-    swap(*__x, *__z);     // x < y && y < z
+    _Ops::iter_swap(__x, __z);     // x < y && y < z
     __r = 1;
     return __r;
   }
-  swap(*__x, *__y);       // x > y && y <= z
+  _Ops::iter_swap(__x, __y);       // x > y && y <= z
   __r = 1;                // x < y && x <= z
   if (__c(*__z, *__y))    // if y > z
   {
-    swap(*__y, *__z);     // x <= y && y < z
+    _Ops::iter_swap(__y, __z);     // x <= y && y < z
     __r = 2;
   }
   return __r;
 }                         // x <= y && y <= z
 
 // stable, 3-6 compares, 0-5 swaps
 
-template <class _Compare, class _ForwardIterator>
+template <class _AlgPolicy, class _Compare, class _ForwardIterator>
 unsigned __sort4(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3, _ForwardIterator __x4,
                  _Compare __c) {
-  unsigned __r = _VSTD::__sort3<_Compare>(__x1, __x2, __x3, __c);
+  using _Ops = _IterOps<_AlgPolicy>;
+
+  unsigned __r = std::__sort3<_AlgPolicy, _Compare>(__x1, __x2, __x3, __c);
   if (__c(*__x4, *__x3)) {
-    swap(*__x3, *__x4);
+    _Ops::iter_swap(__x3, __x4);
     ++__r;
     if (__c(*__x3, *__x2)) {
-      swap(*__x2, *__x3);
+      _Ops::iter_swap(__x2, __x3);
       ++__r;
       if (__c(*__x2, *__x1)) {
-        swap(*__x1, *__x2);
+        _Ops::iter_swap(__x1, __x2);
         ++__r;
       }
     }
   }
   return __r;
 }
 
 // stable, 4-10 compares, 0-9 swaps
 
-template <class _Compare, class _ForwardIterator>
+template <class _AlgPolicy, class _Compare, class _ForwardIterator>
 _LIBCPP_HIDDEN unsigned __sort5(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3,
                                 _ForwardIterator __x4, _ForwardIterator __x5, _Compare __c) {
-  unsigned __r = _VSTD::__sort4<_Compare>(__x1, __x2, __x3, __x4, __c);
+  using _Ops = _IterOps<_AlgPolicy>;
+
+  unsigned __r = std::__sort4<_AlgPolicy, _Compare>(__x1, __x2, __x3, __x4, __c);
   if (__c(*__x5, *__x4)) {
-    swap(*__x4, *__x5);
+    _Ops::iter_swap(__x4, __x5);
     ++__r;
     if (__c(*__x4, *__x3)) {
-      swap(*__x3, *__x4);
+      _Ops::iter_swap(__x3, __x4);
       ++__r;
       if (__c(*__x3, *__x2)) {
-        swap(*__x2, *__x3);
+        _Ops::iter_swap(__x2, __x3);
         ++__r;
         if (__c(*__x2, *__x1)) {
-          swap(*__x1, *__x2);
+          _Ops::iter_swap(__x1, __x2);
           ++__r;
         }
       }
     }
   }
   return __r;
 }
 
 // The comparator being simple is a prerequisite for using the branchless optimization.
 template <class _Tp>
 struct __is_simple_comparator : false_type {};
 template <class _Tp>
 struct __is_simple_comparator<__less<_Tp>&> : true_type {};
 template <class _Tp>
 struct __is_simple_comparator<less<_Tp>&> : true_type {};
 template <class _Tp>
 struct __is_simple_comparator<greater<_Tp>&> : true_type {};
 #if _LIBCPP_STD_VER > 17
 template <>
 struct __is_simple_comparator<ranges::less&> : true_type {};
 template <>
 struct __is_simple_comparator<ranges::greater&> : true_type {};
 #endif
 
 template <class _Compare, class _Iter, class _Tp = typename iterator_traits<_Iter>::value_type>
 using __use_branchless_sort =
     integral_constant<bool, __is_cpp17_contiguous_iterator<_Iter>::value && sizeof(_Tp) <= sizeof(void*) &&
-                                is_arithmetic<_Tp>::value && __is_simple_comparator<_Compare>::value>;
+                                is_arithmetic<_Tp>::value && __is_simple_comparator<_Compare>::value &&
+                                is_same<decltype(*declval<_Iter>()), _Tp>::value>;
 
 // Ensures that __c(*__x, *__y) is true by swapping *__x and *__y if necessary.
 template <class _Compare, class _RandomAccessIterator>
 inline _LIBCPP_HIDE_FROM_ABI void __cond_swap(_RandomAccessIterator __x, _RandomAccessIterator __y, _Compare __c) {
   using value_type = typename iterator_traits<_RandomAccessIterator>::value_type;
   bool __r = __c(*__x, *__y);
   value_type __tmp = __r ? *__x : *__y;
   *__y = __r ? *__y : *__x;
   *__x = __tmp;
 }
 
 // Ensures that *__x, *__y and *__z are ordered according to the comparator __c,
 // under the assumption that *__y and *__z are already ordered.
 template <class _Compare, class _RandomAccessIterator>
 inline _LIBCPP_HIDE_FROM_ABI void __partially_sorted_swap(_RandomAccessIterator __x, _RandomAccessIterator __y,
                                                           _RandomAccessIterator __z, _Compare __c) {
   using value_type = typename iterator_traits<_RandomAccessIterator>::value_type;
   bool __r = __c(*__z, *__x);
   value_type __tmp = __r ? *__z : *__x;
   *__z = __r ? *__x : *__z;
   __r = __c(__tmp, *__y);
   *__x = __r ? *__x : *__y;
   *__y = __r ? *__y : __tmp;
 }
 
-template <class _Compare, class _RandomAccessIterator>
+template <class, class _Compare, class _RandomAccessIterator>
 inline _LIBCPP_HIDE_FROM_ABI __enable_if_t<__use_branchless_sort<_Compare, _RandomAccessIterator>::value, void>
 __sort3_maybe_branchless(_RandomAccessIterator __x1, _RandomAccessIterator __x2, _RandomAccessIterator __x3,
                          _Compare __c) {
   _VSTD::__cond_swap<_Compare>(__x2, __x3, __c);
   _VSTD::__partially_sorted_swap<_Compare>(__x1, __x2, __x3, __c);
 }
 
-template <class _Compare, class _RandomAccessIterator>
+template <class _AlgPolicy, class _Compare, class _RandomAccessIterator>
 inline _LIBCPP_HIDE_FROM_ABI __enable_if_t<!__use_branchless_sort<_Compare, _RandomAccessIterator>::value, void>
 __sort3_maybe_branchless(_RandomAccessIterator __x1, _RandomAccessIterator __x2, _RandomAccessIterator __x3,
                          _Compare __c) {
-  _VSTD::__sort3<_Compare>(__x1, __x2, __x3, __c);
+  std::__sort3<_AlgPolicy, _Compare>(__x1, __x2, __x3, __c);
 }
 
-template <class _Compare, class _RandomAccessIterator>
+template <class, class _Compare, class _RandomAccessIterator>
 inline _LIBCPP_HIDE_FROM_ABI __enable_if_t<__use_branchless_sort<_Compare, _RandomAccessIterator>::value, void>
 __sort4_maybe_branchless(_RandomAccessIterator __x1, _RandomAccessIterator __x2, _RandomAccessIterator __x3,
                          _RandomAccessIterator __x4, _Compare __c) {
   _VSTD::__cond_swap<_Compare>(__x1, __x3, __c);
   _VSTD::__cond_swap<_Compare>(__x2, __x4, __c);
   _VSTD::__cond_swap<_Compare>(__x1, __x2, __c);
   _VSTD::__cond_swap<_Compare>(__x3, __x4, __c);
   _VSTD::__cond_swap<_Compare>(__x2, __x3, __c);
 }
 
-template <class _Compare, class _RandomAccessIterator>
+template <class _AlgPolicy, class _Compare, class _RandomAccessIterator>
 inline _LIBCPP_HIDE_FROM_ABI __enable_if_t<!__use_branchless_sort<_Compare, _RandomAccessIterator>::value, void>
 __sort4_maybe_branchless(_RandomAccessIterator __x1, _RandomAccessIterator __x2, _RandomAccessIterator __x3,
                          _RandomAccessIterator __x4, _Compare __c) {
-  _VSTD::__sort4<_Compare>(__x1, __x2, __x3, __x4, __c);
+  std::__sort4<_AlgPolicy, _Compare>(__x1, __x2, __x3, __x4, __c);
 }
 
-template <class _Compare, class _RandomAccessIterator>
+template <class, class _Compare, class _RandomAccessIterator>
 inline _LIBCPP_HIDE_FROM_ABI __enable_if_t<__use_branchless_sort<_Compare, _RandomAccessIterator>::value, void>
 __sort5_maybe_branchless(_RandomAccessIterator __x1, _RandomAccessIterator __x2, _RandomAccessIterator __x3,
                          _RandomAccessIterator __x4, _RandomAccessIterator __x5, _Compare __c) {
   _VSTD::__cond_swap<_Compare>(__x1, __x2, __c);
   _VSTD::__cond_swap<_Compare>(__x4, __x5, __c);
   _VSTD::__partially_sorted_swap<_Compare>(__x3, __x4, __x5, __c);
   _VSTD::__cond_swap<_Compare>(__x2, __x5, __c);
   _VSTD::__partially_sorted_swap<_Compare>(__x1, __x3, __x4, __c);
   _VSTD::__partially_sorted_swap<_Compare>(__x2, __x3, __x4, __c);
 }
 
-template <class _Compare, class _RandomAccessIterator>
+template <class _AlgPolicy, class _Compare, class _RandomAccessIterator>
 inline _LIBCPP_HIDE_FROM_ABI __enable_if_t<!__use_branchless_sort<_Compare, _RandomAccessIterator>::value, void>
 __sort5_maybe_branchless(_RandomAccessIterator __x1, _RandomAccessIterator __x2, _RandomAccessIterator __x3,
                          _RandomAccessIterator __x4, _RandomAccessIterator __x5, _Compare __c) {
-  _VSTD::__sort5<_Compare>(__x1, __x2, __x3, __x4, __x5, __c);
+  std::__sort5<_AlgPolicy, _Compare>(__x1, __x2, __x3, __x4, __x5, __c);
 }
 
 // Assumes size > 0
-template <class _Compare, class _BidirectionalIterator>
+template <class _AlgPolicy, class _Compare, class _BidirectionalIterator>
 _LIBCPP_CONSTEXPR_AFTER_CXX11 void __selection_sort(_BidirectionalIterator __first, _BidirectionalIterator __last,
                                                     _Compare __comp) {
   _BidirectionalIterator __lm1 = __last;
   for (--__lm1; __first != __lm1; ++__first) {
-    _BidirectionalIterator __i = _VSTD::min_element(__first, __last, __comp);
+    _BidirectionalIterator __i = _Algs<_AlgPolicy>::min_element(__first, __last, __comp);
     if (__i != __first)
-      swap(*__first, *__i);
+      _IterOps<_AlgPolicy>::iter_swap(__first, __i);
   }
 }
 
-template <class _Compare, class _BidirectionalIterator>
+template <class _AlgPolicy, class _Compare, class _BidirectionalIterator>
 void __insertion_sort(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp) {
+  using _Ops = _IterOps<_AlgPolicy>;
+
   typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
   if (__first != __last) {
     _BidirectionalIterator __i = __first;
     for (++__i; __i != __last; ++__i) {
       _BidirectionalIterator __j = __i;
-      value_type __t(_VSTD::move(*__j));
+      value_type __t(_Ops::__iter_move(__j));
       for (_BidirectionalIterator __k = __i; __k != __first && __comp(__t, *--__k); --__j)
-        *__j = _VSTD::move(*__k);
+        *__j = _Ops::__iter_move(__k);
       *__j = _VSTD::move(__t);
     }
   }
 }
 
-template <class _Compare, class _RandomAccessIterator>
+template <class _AlgPolicy, class _Compare, class _RandomAccessIterator>
 void __insertion_sort_3(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) {
+  using _Ops = _IterOps<_AlgPolicy>;
+
   typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
   typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
   _RandomAccessIterator __j = __first + difference_type(2);
-  _VSTD::__sort3_maybe_branchless<_Compare>(__first, __first + difference_type(1), __j, __comp);
+  std::__sort3_maybe_branchless<_AlgPolicy, _Compare>(__first, __first + difference_type(1), __j, __comp);
   for (_RandomAccessIterator __i = __j + difference_type(1); __i != __last; ++__i) {
     if (__comp(*__i, *__j)) {
-      value_type __t(_VSTD::move(*__i));
+      value_type __t(_Ops::__iter_move(__i));
       _RandomAccessIterator __k = __j;
       __j = __i;
       do {
-        *__j = _VSTD::move(*__k);
+        *__j = _Ops::__iter_move(__k);
         __j = __k;
       } while (__j != __first && __comp(__t, *--__k));
       *__j = _VSTD::move(__t);
     }
     __j = __i;
   }
 }
 
-template <class _Compare, class _RandomAccessIterator>
+template <class _AlgPolicy, class _Compare, class _RandomAccessIterator>
 bool __insertion_sort_incomplete(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) {
+  using _Ops = _IterOps<_AlgPolicy>;
+
   typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
   switch (__last - __first) {
   case 0:
   case 1:
     return true;
   case 2:
     if (__comp(*--__last, *__first))
-      swap(*__first, *__last);
+      _IterOps<_AlgPolicy>::iter_swap(__first, __last);
     return true;
   case 3:
-    _VSTD::__sort3_maybe_branchless<_Compare>(__first, __first + difference_type(1), --__last, __comp);
+    std::__sort3_maybe_branchless<_AlgPolicy, _Compare>(__first, __first + difference_type(1), --__last, __comp);
     return true;
   case 4:
-    _VSTD::__sort4_maybe_branchless<_Compare>(__first, __first + difference_type(1), __first + difference_type(2),
-                                              --__last, __comp);
+    std::__sort4_maybe_branchless<_AlgPolicy, _Compare>(
+        __first, __first + difference_type(1), __first + difference_type(2), --__last, __comp);
     return true;
   case 5:
-    _VSTD::__sort5_maybe_branchless<_Compare>(__first, __first + difference_type(1), __first + difference_type(2),
-                                              __first + difference_type(3), --__last, __comp);
+    std::__sort5_maybe_branchless<_AlgPolicy, _Compare>(
+        __first, __first + difference_type(1), __first + difference_type(2), __first + difference_type(3),
+        --__last, __comp);
     return true;
   }
   typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
   _RandomAccessIterator __j = __first + difference_type(2);
-  _VSTD::__sort3_maybe_branchless<_Compare>(__first, __first + difference_type(1), __j, __comp);
+  std::__sort3_maybe_branchless<_AlgPolicy, _Compare>(__first, __first + difference_type(1), __j, __comp);
   const unsigned __limit = 8;
   unsigned __count = 0;
   for (_RandomAccessIterator __i = __j + difference_type(1); __i != __last; ++__i) {
     if (__comp(*__i, *__j)) {
-      value_type __t(_VSTD::move(*__i));
+      value_type __t(_Ops::__iter_move(__i));
       _RandomAccessIterator __k = __j;
       __j = __i;
       do {
-        *__j = _VSTD::move(*__k);
+        *__j = _Ops::__iter_move(__k);
         __j = __k;
       } while (__j != __first && __comp(__t, *--__k));
       *__j = _VSTD::move(__t);
       if (++__count == __limit)
         return ++__i == __last;
     }
     __j = __i;
   }
   return true;
 }
 
-template <class _Compare, class _BidirectionalIterator>
+template <class _AlgPolicy, class _Compare, class _BidirectionalIterator>
 void __insertion_sort_move(_BidirectionalIterator __first1, _BidirectionalIterator __last1,
                            typename iterator_traits<_BidirectionalIterator>::value_type* __first2, _Compare __comp) {
+  using _Ops = _IterOps<_AlgPolicy>;
+
   typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
   if (__first1 != __last1) {
     __destruct_n __d(0);
     unique_ptr<value_type, __destruct_n&> __h(__first2, __d);
     value_type* __last2 = __first2;
-    ::new ((void*)__last2) value_type(_VSTD::move(*__first1));
+    ::new ((void*)__last2) value_type(_Ops::__iter_move(__first1));
     __d.template __incr<value_type>();
     for (++__last2; ++__first1 != __last1; ++__last2) {
       value_type* __j2 = __last2;
       value_type* __i2 = __j2;
       if (__comp(*__first1, *--__i2)) {
-        ::new ((void*)__j2) value_type(_VSTD::move(*__i2));
+        ::new ((void*)__j2) value_type(_Ops::__iter_move(__i2));
         __d.template __incr<value_type>();
         for (--__j2; __i2 != __first2 && __comp(*__first1, *--__i2); --__j2)
-          *__j2 = _VSTD::move(*__i2);
-        *__j2 = _VSTD::move(*__first1);
+          *__j2 = _Ops::__iter_move(__i2);
+        *__j2 = _Ops::__iter_move(__first1);
       } else {
-        ::new ((void*)__j2) value_type(_VSTD::move(*__first1));
+        ::new ((void*)__j2) value_type(_Ops::__iter_move(__first1));
         __d.template __incr<value_type>();
       }
     }
     __h.release();
   }
 }
 
-template <class _Compare, class _RandomAccessIterator>
+template <class _AlgPolicy, class _Compare, class _RandomAccessIterator>
 void __introsort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
                  typename iterator_traits<_RandomAccessIterator>::difference_type __depth) {
+  using _Ops = _IterOps<_AlgPolicy>;
+
   typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
   typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
   const difference_type __limit =
       is_trivially_copy_constructible<value_type>::value && is_trivially_copy_assignable<value_type>::value ? 30 : 6;
   while (true) {
   __restart:
     difference_type __len = __last - __first;
     switch (__len) {
     case 0:
     case 1:
       return;
     case 2:
       if (__comp(*--__last, *__first))
-        swap(*__first, *__last);
+        _IterOps<_AlgPolicy>::iter_swap(__first, __last);
       return;
     case 3:
-      _VSTD::__sort3_maybe_branchless<_Compare>(__first, __first + difference_type(1), --__last, __comp);
+      std::__sort3_maybe_branchless<_AlgPolicy, _Compare>(__first, __first + difference_type(1), --__last, __comp);
       return;
     case 4:
-      _VSTD::__sort4_maybe_branchless<_Compare>(__first, __first + difference_type(1), __first + difference_type(2),
-                                                --__last, __comp);
+      std::__sort4_maybe_branchless<_AlgPolicy, _Compare>(
+          __first, __first + difference_type(1), __first + difference_type(2), --__last, __comp);
       return;
     case 5:
-      _VSTD::__sort5_maybe_branchless<_Compare>(__first, __first + difference_type(1), __first + difference_type(2),
-                                                __first + difference_type(3), --__last, __comp);
+      std::__sort5_maybe_branchless<_AlgPolicy, _Compare>(
+          __first, __first + difference_type(1), __first + difference_type(2), __first + difference_type(3),
+          --__last, __comp);
       return;
     }
     if (__len <= __limit) {
-      _VSTD::__insertion_sort_3<_Compare>(__first, __last, __comp);
+      std::__insertion_sort_3<_AlgPolicy, _Compare>(__first, __last, __comp);
       return;
     }
     // __len > 5
     if (__depth == 0) {
       // Fallback to heap sort as Introsort suggests.
-      _VSTD::__partial_sort<_Compare>(__first, __last, __last, __comp);
+      std::__partial_sort<_AlgPolicy, _Compare>(__first, __last, __last, __comp);
       return;
     }
     --__depth;
     _RandomAccessIterator __m = __first;
     _RandomAccessIterator __lm1 = __last;
     --__lm1;
     unsigned __n_swaps;
     {
       difference_type __delta;
       if (__len >= 1000) {
         __delta = __len / 2;
         __m += __delta;
         __delta /= 2;
-        __n_swaps = _VSTD::__sort5<_Compare>(__first, __first + __delta, __m, __m + __delta, __lm1, __comp);
+        __n_swaps = std::__sort5<_AlgPolicy, _Compare>(__first, __first + __delta, __m, __m + __delta, __lm1, __comp);
       } else {
         __delta = __len / 2;
         __m += __delta;
-        __n_swaps = _VSTD::__sort3<_Compare>(__first, __m, __lm1, __comp);
+        __n_swaps = std::__sort3<_AlgPolicy, _Compare>(__first, __m, __lm1, __comp);
       }
     }
     // *__m is median
     // partition [__first, __m) < *__m and *__m <= [__m, __last)
     // (this inhibits tossing elements equivalent to __m around unnecessarily)
     _RandomAccessIterator __i = __first;
     _RandomAccessIterator __j = __lm1;
     // j points beyond range to be tested, *__m is known to be <= *__lm1
if (!__comp(*__i, *__m)) // if *__first == *__m
           ++__i; // __first + 1
           __j = __last;
           if (!__comp(*__first, *--__j)) // we need a guard if *__first == *(__last-1)
           {
             while (true) {
               if (__i == __j)
                 return; // [__first, __last) all equivalent elements
               if (__comp(*__first, *__i)) {
-                swap(*__i, *__j);
+                _Ops::iter_swap(__i, __j);
                 ++__n_swaps;
                 ++__i;
                 break;
               }
               ++__i;
             }
           }
           // [__first, __i) == *__first and *__first < [__j, __last) and __j == __last - 1
           if (__i == __j)
             return;
           while (true) {
             while (!__comp(*__first, *__i))
               ++__i;
             while (__comp(*__first, *--__j))
               ;
             if (__i >= __j)
               break;
-            swap(*__i, *__j);
+            _Ops::iter_swap(__i, __j);
             ++__n_swaps;
             ++__i;
           }
           // [__first, __i) == *__first and *__first < [__i, __last)
           // The first part is sorted, sort the second part
           // _VSTD::__sort<_Compare>(__i, __last, __comp);
           __first = __i;
           goto __restart;
         }
         if (__comp(*__j, *__m)) {
-          swap(*__i, *__j);
+          _Ops::iter_swap(__i, __j);
           ++__n_swaps;
           break; // found guard for downward moving __j, now use unguarded partition
         }
       }
     }
     // It is known that *__i < *__m
     ++__i;
     // j points beyond range to be tested, *__m is known to be <= *__lm1
     // if not yet partitioned...
     if (__i < __j) {
       // known that *(__i - 1) < *__m
       // known that __i <= __m
       while (true) {
         // __m still guards upward moving __i
         while (__comp(*__i, *__m))
           ++__i;
         // It is now known that a guard exists for downward moving __j
         while (!__comp(*--__j, *__m))
           ;
         if (__i > __j)
           break;
-        swap(*__i, *__j);
+        _Ops::iter_swap(__i, __j);
         ++__n_swaps;
         // It is known that __m != __j
         // If __m just moved, follow it
         if (__m == __i)
           __m = __j;
         ++__i;
       }
     }
     // [__first, __i) < *__m and *__m <= [__i, __last)
     if (__i != __m && __comp(*__m, *__i)) {
-      swap(*__i, *__m);
+      _Ops::iter_swap(__i, __m);
       ++__n_swaps;
     }
     // [__first, __i) < *__i and *__i <= [__i+1, __last)
     // If we were given a perfect partition, see if insertion sort is quick...
     if (__n_swaps == 0) {
-      bool __fs = _VSTD::__insertion_sort_incomplete<_Compare>(__first, __i, __comp);
-      if (_VSTD::__insertion_sort_incomplete<_Compare>(__i + difference_type(1), __last, __comp)) {
+      bool __fs = std::__insertion_sort_incomplete<_AlgPolicy, _Compare>(__first, __i, __comp);
+      if (std::__insertion_sort_incomplete<_AlgPolicy, _Compare>(__i + difference_type(1), __last, __comp)) {
         if (__fs)
           return;
         __last = __i;
         continue;
       } else {
         if (__fs) {
           __first = ++__i;
           continue;
         }
       }
     }
     // sort smaller range with recursive call and larger with tail recursion elimination
     if (__i - __first < __last - __i) {
-      _VSTD::__introsort<_Compare>(__first, __i, __comp, __depth);
+      std::__introsort<_AlgPolicy, _Compare>(__first, __i, __comp, __depth);
       __first = ++__i;
     } else {
-      _VSTD::__introsort<_Compare>(__i + difference_type(1), __last, __comp, __depth);
+      std::__introsort<_AlgPolicy, _Compare>(__i + difference_type(1), __last, __comp, __depth);
       __last = __i;
     }
   }
 }
 
 template <typename _Number>
 inline _LIBCPP_HIDE_FROM_ABI _Number __log2i(_Number __n) {
   if (__n == 0)
     return 0;
   if (sizeof(__n) <= sizeof(unsigned))
     return sizeof(unsigned) * CHAR_BIT - 1 - __libcpp_clz(static_cast<unsigned>(__n));
   if (sizeof(__n) <= sizeof(unsigned long))
     return sizeof(unsigned long) * CHAR_BIT - 1 - __libcpp_clz(static_cast<unsigned long>(__n));
   if (sizeof(__n) <= sizeof(unsigned long long))
     return sizeof(unsigned long long) * CHAR_BIT - 1 - __libcpp_clz(static_cast<unsigned long long>(__n));
 
   _Number __log2 = 0;
   while (__n > 1) {
     __log2++;
     __n >>= 1;
   }
   return __log2;
 }
 
-template <class _Compare, class _RandomAccessIterator>
+template <class _AlgPolicy, class _Compare, class _RandomAccessIterator>
 void __sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) {
   typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
   difference_type __depth_limit = 2 * __log2i(__last - __first);
-  _VSTD::__introsort<_Compare>(__first, __last, __comp, __depth_limit);
+  std::__introsort<_AlgPolicy, _Compare>(__first, __last, __comp, __depth_limit);
 }
 
-template <class _Compare, class _Tp>
+template <class _AlgPolicy, class _Compare, class _Tp>
 inline _LIBCPP_INLINE_VISIBILITY void __sort(_Tp** __first, _Tp** __last, __less<_Tp*>&) {
   __less<uintptr_t> __comp;
-  _VSTD::__sort<__less<uintptr_t>&, uintptr_t*>((uintptr_t*)__first, (uintptr_t*)__last, __comp);
+  std::__sort<_AlgPolicy, __less<uintptr_t>&, uintptr_t*>((uintptr_t*)__first, (uintptr_t*)__last, __comp);
 }
 
-extern template _LIBCPP_FUNC_VIS void __sort<__less<char>&, char*>(char*, char*, __less<char>&);
+extern template _LIBCPP_FUNC_VIS void __sort<_ClassicAlgPolicy, __less<char>&, char*>(char*, char*, __less<char>&);
 #ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS
-extern template _LIBCPP_FUNC_VIS void __sort<__less<wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, __less<wchar_t>&);
+extern template _LIBCPP_FUNC_VIS void __sort<_ClassicAlgPolicy, __less<wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, __less<wchar_t>&);
 #endif
-extern template _LIBCPP_FUNC_VIS void __sort<__less<signed char>&, signed char*>(signed char*, signed char*, __less<signed char>&);
-extern template _LIBCPP_FUNC_VIS void __sort<__less<unsigned char>&, unsigned char*>(unsigned char*, unsigned char*, __less<unsigned char>&);
-extern template _LIBCPP_FUNC_VIS void __sort<__less<short>&, short*>(short*, short*, __less<short>&);
-extern template _LIBCPP_FUNC_VIS void __sort<__less<unsigned short>&, unsigned short*>(unsigned short*, unsigned short*, __less<unsigned short>&);
-extern template _LIBCPP_FUNC_VIS void __sort<__less<int>&, int*>(int*, int*, __less<int>&);
-extern template _LIBCPP_FUNC_VIS void __sort<__less<unsigned>&, unsigned*>(unsigned*, unsigned*, __less<unsigned>&);
-extern template _LIBCPP_FUNC_VIS void __sort<__less<long>&, long*>(long*, long*, __less<long>&);
-extern template _LIBCPP_FUNC_VIS void __sort<__less<unsigned long>&, unsigned long*>(unsigned long*, unsigned long*, __less<unsigned long>&);
-extern template _LIBCPP_FUNC_VIS void __sort<__less<long long>&, long long*>(long long*, long long*, __less<long long>&);
-extern template _LIBCPP_FUNC_VIS void __sort<__less<unsigned long long>&, unsigned long long*>(unsigned long long*, unsigned long long*, __less<unsigned long long>&);
-extern template _LIBCPP_FUNC_VIS void __sort<__less<float>&, float*>(float*, float*, __less<float>&);
-extern template _LIBCPP_FUNC_VIS void __sort<__less<double>&, double*>(double*, double*, __less<double>&);
-extern template _LIBCPP_FUNC_VIS void __sort<__less<long double>&, long double*>(long double*, long double*, __less<long double>&);
+extern template _LIBCPP_FUNC_VIS void __sort<_ClassicAlgPolicy, __less<signed char>&, signed char*>(signed char*, signed char*, __less<signed char>&);
+extern template _LIBCPP_FUNC_VIS void __sort<_ClassicAlgPolicy, __less<unsigned char>&, unsigned char*>(unsigned char*, unsigned char*, __less<unsigned char>&);
+extern template _LIBCPP_FUNC_VIS void __sort<_ClassicAlgPolicy, __less<short>&, short*>(short*, short*, __less<short>&);
+extern template _LIBCPP_FUNC_VIS void __sort<_ClassicAlgPolicy, __less<unsigned short>&, unsigned short*>(unsigned short*, unsigned short*, __less<unsigned short>&);
+extern template _LIBCPP_FUNC_VIS void __sort<_ClassicAlgPolicy, __less<int>&, int*>(int*, int*, __less<int>&);
+extern template _LIBCPP_FUNC_VIS void __sort<_ClassicAlgPolicy, __less<unsigned>&, unsigned*>(unsigned*, unsigned*, __less<unsigned>&);
+extern template _LIBCPP_FUNC_VIS void __sort<_ClassicAlgPolicy, __less<long>&, long*>(long*, long*, __less<long>&);
+extern template _LIBCPP_FUNC_VIS void __sort<_ClassicAlgPolicy, __less<unsigned long>&, unsigned long*>(unsigned long*, unsigned long*, __less<unsigned long>&);
+extern template _LIBCPP_FUNC_VIS void __sort<_ClassicAlgPolicy, __less<long long>&, long long*>(long long*, long long*, __less<long long>&);
+extern template _LIBCPP_FUNC_VIS void __sort<_ClassicAlgPolicy, __less<unsigned long long>&, unsigned long long*>(unsigned long long*, unsigned long long*, __less<unsigned long long>&);
+extern template _LIBCPP_FUNC_VIS void __sort<_ClassicAlgPolicy, __less<float>&, float*>(float*, float*, __less<float>&);
+extern template _LIBCPP_FUNC_VIS void __sort<_ClassicAlgPolicy, __less<double>&, double*>(double*, double*, __less<double>&);
+extern template _LIBCPP_FUNC_VIS void __sort<_ClassicAlgPolicy, __less<long double>&, long double*>(long double*, long double*, __less<long double>&);
 
-extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<char>&, char*>(char*, char*, __less<char>&);
+extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<_ClassicAlgPolicy, __less<char>&, char*>(char*, char*, __less<char>&);
 #ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS
-extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, __less<wchar_t>&);
+extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<_ClassicAlgPolicy, __less<wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, __less<wchar_t>&);
 #endif
-extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<signed char>&, signed char*>(signed char*, signed char*, __less<signed char>&);
-extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned char>&, unsigned char*>(unsigned char*, unsigned char*, __less<unsigned char>&);
-extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<short>&, short*>(short*, short*, __less<short>&);
-extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned short>&, unsigned short*>(unsigned short*, unsigned short*, __less<unsigned short>&);
-extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<int>&, int*>(int*, int*, __less<int>&);
-extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned>&, unsigned*>(unsigned*, unsigned*, __less<unsigned>&);
-extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<long>&, long*>(long*, long*, __less<long>&);
-extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned long>&, unsigned long*>(unsigned long*, unsigned long*, __less<unsigned long>&);
-extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<long long>&, long long*>(long long*, long long*, __less<long long>&);
-extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned long long>&, unsigned long long*>(unsigned long long*, unsigned long long*, __less<unsigned long long>&);
-extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<float>&, float*>(float*, float*, __less<float>&);
-extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<double>&, double*>(double*, double*, __less<double>&);
-extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<long double>&, long double*>(long double*, long double*, __less<long double>&);
+extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<_ClassicAlgPolicy, __less<signed char>&, signed char*>(signed char*, signed char*, __less<signed char>&);
+extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<_ClassicAlgPolicy, __less<unsigned char>&, unsigned char*>(unsigned char*, unsigned char*, __less<unsigned char>&);
+extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<_ClassicAlgPolicy, __less<short>&, short*>(short*, short*, __less<short>&);
+extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<_ClassicAlgPolicy, __less<unsigned short>&, unsigned short*>(unsigned short*, unsigned short*, __less<unsigned short>&);
+extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<_ClassicAlgPolicy, __less<int>&, int*>(int*, int*, __less<int>&);
+extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<_ClassicAlgPolicy, __less<unsigned>&, unsigned*>(unsigned*, unsigned*, __less<unsigned>&);
+extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<_ClassicAlgPolicy, __less<long>&, long*>(long*, long*, __less<long>&);
+extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<_ClassicAlgPolicy, __less<unsigned long>&, unsigned long*>(unsigned long*, unsigned long*, __less<unsigned long>&);
+extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<_ClassicAlgPolicy, __less<long long>&, long long*>(long long*, long long*, __less<long long>&);
+extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<_ClassicAlgPolicy, __less<unsigned long long>&, unsigned long long*>(unsigned long long*, unsigned long long*, __less<unsigned long long>&);
+extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<_ClassicAlgPolicy, __less<float>&, float*>(float*, float*, __less<float>&);
+extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<_ClassicAlgPolicy, __less<double>&, double*>(double*, double*, __less<double>&);
+extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<_ClassicAlgPolicy, __less<long double>&, long double*>(long double*, long double*, __less<long double>&);
 
-extern template _LIBCPP_FUNC_VIS unsigned __sort5<__less<long double>&, long double*>(long double*, long double*, long double*, long double*, long double*, __less<long double>&);
+extern template _LIBCPP_FUNC_VIS unsigned __sort5<_ClassicAlgPolicy, __less<long double>&, long double*>(long double*, long double*, long double*, long double*, long double*, __less<long double>&);
 
-template <class _RandomAccessIterator, class _Comp>
+template <class _AlgPolicy, class _RandomAccessIterator, class _Comp>
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17
 void __sort_impl(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp& __comp) {
   std::__debug_randomize_range(__first, __last);
   using _Comp_ref = typename __comp_ref_type<_Comp>::type;
   if (__libcpp_is_constant_evaluated()) {
-    std::__partial_sort<_Comp_ref>(__first, __last, __last, _Comp_ref(__comp));
+    std::__partial_sort<_AlgPolicy, _Comp_ref>(__first, __last, __last, _Comp_ref(__comp));
   } else {
-    std::__sort<_Comp_ref>(std::__unwrap_iter(__first), std::__unwrap_iter(__last), _Comp_ref(__comp));
+    std::__sort<_AlgPolicy, _Comp_ref>(std::__unwrap_iter(__first), std::__unwrap_iter(__last), _Comp_ref(__comp));
   }
 }
 
 template <class _RandomAccessIterator, class _Comp>
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17
 void sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp __comp) {
-  std::__sort_impl(std::move(__first), std::move(__last), __comp);
+  std::__sort_impl<_ClassicAlgPolicy>(std::move(__first), std::move(__last), __comp);
 }
 
 template <class _RandomAccessIterator>
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17
 void sort(_RandomAccessIterator __first, _RandomAccessIterator __last) {
   std::sort(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_SORT_H

libcxx/include/__algorithm/sort_heap.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_SORT_HEAP_H
 #define _LIBCPP___ALGORITHM_SORT_HEAP_H
 
 #include <__algorithm/comp.h>
 #include <__algorithm/comp_ref_type.h>
+#include <__algorithm/iterator_operations.h>
 #include <__algorithm/pop_heap.h>
 #include <__config>
 #include <__iterator/iterator_traits.h>
 #include <__utility/move.h>
 #include <type_traits> // swap
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
-template <class _Compare, class _RandomAccessIterator>
+template <class _AlgPolicy, class _Compare, class _RandomAccessIterator>
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
 void __sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare& __comp) {
   using _CompRef = typename __comp_ref_type<_Compare>::type;
   _CompRef __comp_ref = __comp;
 
   using difference_type = typename iterator_traits<_RandomAccessIterator>::difference_type;
   for (difference_type __n = __last - __first; __n > 1; --__last, (void) --__n)
-    std::__pop_heap<_CompRef>(__first, __last, __comp_ref, __n);
+    std::__pop_heap<_AlgPolicy, _CompRef>(__first, __last, __comp_ref, __n);
 }
 
 template <class _RandomAccessIterator, class _Compare>
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17
 void sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) {
-  std::__sort_heap(std::move(__first), std::move(__last), __comp);
+  std::__sort_heap<_ClassicAlgPolicy>(std::move(__first), std::move(__last), __comp);
 }
 
 template <class _RandomAccessIterator>
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17
 void sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) {
   std::sort_heap(std::move(__first), std::move(__last),
       __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_SORT_HEAP_H

libcxx/include/__algorithm/stable_sort.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_STABLE_SORT_H
 #define _LIBCPP___ALGORITHM_STABLE_SORT_H
 
 #include <__algorithm/comp.h>
 #include <__algorithm/comp_ref_type.h>
 #include <__algorithm/inplace_merge.h>
+#include <__algorithm/iterator_operations.h>
 #include <__algorithm/sort.h>
 #include <__config>
 #include <__iterator/iterator_traits.h>
 #include <__utility/move.h>
-#include <__utility/swap.h>
 #include <memory>
 #include <type_traits>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
-template <class _Compare, class _InputIterator1, class _InputIterator2>
+template <class _AlgPolicy, class _Compare, class _InputIterator1, class _InputIterator2>
 void
 __merge_move_construct(_InputIterator1 __first1, _InputIterator1 __last1,
         _InputIterator2 __first2, _InputIterator2 __last2,
         typename iterator_traits<_InputIterator1>::value_type* __result, _Compare __comp)
 {
+    using _Ops = _IterOps<_AlgPolicy>;
+
     typedef typename iterator_traits<_InputIterator1>::value_type value_type;
     __destruct_n __d(0);
     unique_ptr<value_type, __destruct_n&> __h(__result, __d);
     for (; true; ++__result)
     {
         if (__first1 == __last1)
         {
             for (; __first2 != __last2; ++__first2, (void) ++__result, __d.template __incr<value_type>())
-                ::new ((void*)__result) value_type(_VSTD::move(*__first2));
+                ::new ((void*)__result) value_type(_Ops::__iter_move(__first2));
             __h.release();
             return;
         }
         if (__first2 == __last2)
         {
             for (; __first1 != __last1; ++__first1, (void) ++__result, __d.template __incr<value_type>())
-                ::new ((void*)__result) value_type(_VSTD::move(*__first1));
+                ::new ((void*)__result) value_type(_Ops::__iter_move(__first1));
             __h.release();
             return;
         }
         if (__comp(*__first2, *__first1))
         {
-            ::new ((void*)__result) value_type(_VSTD::move(*__first2));
+            ::new ((void*)__result) value_type(_Ops::__iter_move(__first2));
             __d.template __incr<value_type>();
             ++__first2;
         }
         else
         {
-            ::new ((void*)__result) value_type(_VSTD::move(*__first1));
+            ::new ((void*)__result) value_type(_Ops::__iter_move(__first1));
             __d.template __incr<value_type>();
             ++__first1;
         }
     }
 }
 
-template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
+template <class _AlgPolicy, class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
 void
 __merge_move_assign(_InputIterator1 __first1, _InputIterator1 __last1,
         _InputIterator2 __first2, _InputIterator2 __last2,
         _OutputIterator __result, _Compare __comp)
 {
+    using _Ops = _IterOps<_AlgPolicy>;
+
     for (; __first1 != __last1; ++__result)
     {
         if (__first2 == __last2)
         {
             for (; __first1 != __last1; ++__first1, (void) ++__result)
-                *__result = _VSTD::move(*__first1);
+                *__result = _Ops::__iter_move(__first1);
             return;
         }
         if (__comp(*__first2, *__first1))
         {
-            *__result = _VSTD::move(*__first2);
+            *__result = _Ops::__iter_move(__first2);
             ++__first2;
         }
         else
         {
-            *__result = _VSTD::move(*__first1);
+            *__result = _Ops::__iter_move(__first1);
             ++__first1;
         }
     }
     for (; __first2 != __last2; ++__first2, (void) ++__result)
-        *__result = _VSTD::move(*__first2);
+        *__result = _Ops::__iter_move(__first2);
 }
 
-template <class _Compare, class _RandomAccessIterator>
+template <class _AlgPolicy, class _Compare, class _RandomAccessIterator>
 void
 __stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
               typename iterator_traits<_RandomAccessIterator>::difference_type __len,
               typename iterator_traits<_RandomAccessIterator>::value_type* __buff, ptrdiff_t __buff_size);
 
-template <class _Compare, class _RandomAccessIterator>
+template <class _AlgPolicy, class _Compare, class _RandomAccessIterator>
 void
 __stable_sort_move(_RandomAccessIterator __first1, _RandomAccessIterator __last1, _Compare __comp,
                    typename iterator_traits<_RandomAccessIterator>::difference_type __len,
                    typename iterator_traits<_RandomAccessIterator>::value_type* __first2)
 {
+    using _Ops = _IterOps<_AlgPolicy>;
+
     typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
     switch (__len)
     {
     case 0:
         return;
     case 1:
-        ::new ((void*)__first2) value_type(_VSTD::move(*__first1));
+        ::new ((void*)__first2) value_type(_Ops::__iter_move(__first1));
         return;
     case 2:
         __destruct_n __d(0);
         unique_ptr<value_type, __destruct_n&> __h2(__first2, __d);
         if (__comp(*--__last1, *__first1))
         {
-            ::new ((void*)__first2) value_type(_VSTD::move(*__last1));
+            ::new ((void*)__first2) value_type(_Ops::__iter_move(__last1));
             __d.template __incr<value_type>();
             ++__first2;
-            ::new ((void*)__first2) value_type(_VSTD::move(*__first1));
+            ::new ((void*)__first2) value_type(_Ops::__iter_move(__first1));
         }
         else
         {
-            ::new ((void*)__first2) value_type(_VSTD::move(*__first1));
+            ::new ((void*)__first2) value_type(_Ops::__iter_move(__first1));
             __d.template __incr<value_type>();
             ++__first2;
-            ::new ((void*)__first2) value_type(_VSTD::move(*__last1));
+            ::new ((void*)__first2) value_type(_Ops::__iter_move(__last1));
         }
         __h2.release();
         return;
     }
     if (__len <= 8)
     {
-        _VSTD::__insertion_sort_move<_Compare>(__first1, __last1, __first2, __comp);
+        std::__insertion_sort_move<_AlgPolicy, _Compare>(__first1, __last1, __first2, __comp);
         return;
     }
     typename iterator_traits<_RandomAccessIterator>::difference_type __l2 = __len / 2;
     _RandomAccessIterator __m = __first1 + __l2;
-    _VSTD::__stable_sort<_Compare>(__first1, __m, __comp, __l2, __first2, __l2);
-    _VSTD::__stable_sort<_Compare>(__m, __last1, __comp, __len - __l2, __first2 + __l2, __len - __l2);
-    _VSTD::__merge_move_construct<_Compare>(__first1, __m, __m, __last1, __first2, __comp);
+    std::__stable_sort<_AlgPolicy, _Compare>(__first1, __m, __comp, __l2, __first2, __l2);
+    std::__stable_sort<_AlgPolicy, _Compare>(__m, __last1, __comp, __len - __l2, __first2 + __l2, __len - __l2);
+    std::__merge_move_construct<_AlgPolicy, _Compare>(__first1, __m, __m, __last1, __first2, __comp);
 }
 
 template <class _Tp>
 struct __stable_sort_switch
 {
     static const unsigned value = 128*is_trivially_copy_assignable<_Tp>::value;
 };
 
-template <class _Compare, class _RandomAccessIterator>
+template <class _AlgPolicy, class _Compare, class _RandomAccessIterator>
 void
 __stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
               typename iterator_traits<_RandomAccessIterator>::difference_type __len,
               typename iterator_traits<_RandomAccessIterator>::value_type* __buff, ptrdiff_t __buff_size)
 {
     typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
     typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
     switch (__len)
     {
     case 0:
     case 1:
         return;
     case 2:
         if (__comp(*--__last, *__first))
-            swap(*__first, *__last);
+            _IterOps<_AlgPolicy>::iter_swap(__first, __last);
         return;
     }
     if (__len <= static_cast<difference_type>(__stable_sort_switch<value_type>::value))
     {
-        _VSTD::__insertion_sort<_Compare>(__first, __last, __comp);
+        std::__insertion_sort<_AlgPolicy, _Compare>(__first, __last, __comp);
         return;
     }
     typename iterator_traits<_RandomAccessIterator>::difference_type __l2 = __len / 2;
     _RandomAccessIterator __m = __first + __l2;
     if (__len <= __buff_size)
     {
         __destruct_n __d(0);
         unique_ptr<value_type, __destruct_n&> __h2(__buff, __d);
-        _VSTD::__stable_sort_move<_Compare>(__first, __m, __comp, __l2, __buff);
+        std::__stable_sort_move<_AlgPolicy, _Compare>(__first, __m, __comp, __l2, __buff);
         __d.__set(__l2, (value_type*)nullptr);
-        _VSTD::__stable_sort_move<_Compare>(__m, __last, __comp, __len - __l2, __buff + __l2);
+        std::__stable_sort_move<_AlgPolicy, _Compare>(__m, __last, __comp, __len - __l2, __buff + __l2);
         __d.__set(__len, (value_type*)nullptr);
-        _VSTD::__merge_move_assign<_Compare>(__buff, __buff + __l2, __buff + __l2, __buff + __len, __first, __comp);
+        std::__merge_move_assign<_AlgPolicy, _Compare>(
+            __buff, __buff + __l2, __buff + __l2, __buff + __len, __first, __comp);
 //         _VSTD::__merge<_Compare>(move_iterator<value_type*>(__buff),
 //                                  move_iterator<value_type*>(__buff + __l2),
 //                                  move_iterator<_RandomAccessIterator>(__buff + __l2),
 //                                  move_iterator<_RandomAccessIterator>(__buff + __len),
 //                                  __first, __comp);
         return;
     }
-    _VSTD::__stable_sort<_Compare>(__first, __m, __comp, __l2, __buff, __buff_size);
-    _VSTD::__stable_sort<_Compare>(__m, __last, __comp, __len - __l2, __buff, __buff_size);
-    _VSTD::__inplace_merge<_Compare>(__first, __m, __last, __comp, __l2, __len - __l2, __buff, __buff_size);
+    std::__stable_sort<_AlgPolicy, _Compare>(__first, __m, __comp, __l2, __buff, __buff_size);
+    std::__stable_sort<_AlgPolicy, _Compare>(__m, __last, __comp, __len - __l2, __buff, __buff_size);
+    std::__inplace_merge<_AlgPolicy, _Compare>(__first, __m, __last, __comp, __l2, __len - __l2, __buff, __buff_size);
 }
 
-template <class _RandomAccessIterator, class _Compare>
+template <class _AlgPolicy, class _RandomAccessIterator, class _Compare>
 inline _LIBCPP_HIDE_FROM_ABI
 void __stable_sort_impl(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare& __comp) {
   using value_type = typename iterator_traits<_RandomAccessIterator>::value_type;
   using difference_type = typename iterator_traits<_RandomAccessIterator>::difference_type;
 
   difference_type __len = __last - __first;
   pair<value_type*, ptrdiff_t> __buf(0, 0);
   unique_ptr<value_type, __return_temporary_buffer> __h;
   if (__len > static_cast<difference_type>(__stable_sort_switch<value_type>::value)) {
 // TODO: Remove the use of std::get_temporary_buffer
 _LIBCPP_SUPPRESS_DEPRECATED_PUSH
       __buf = std::get_temporary_buffer<value_type>(__len);
 _LIBCPP_SUPPRESS_DEPRECATED_POP
       __h.reset(__buf.first);
   }
 
   using _Comp_ref = typename __comp_ref_type<_Compare>::type;
-  std::__stable_sort<_Comp_ref>(__first, __last, __comp, __len, __buf.first, __buf.second);
+  std::__stable_sort<_AlgPolicy, _Comp_ref>(__first, __last, __comp, __len, __buf.first, __buf.second);
 }
 
 template <class _RandomAccessIterator, class _Compare>
 inline _LIBCPP_HIDE_FROM_ABI
 void stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) {
-  std::__stable_sort_impl(std::move(__first), std::move(__last), __comp);
+  std::__stable_sort_impl<_ClassicAlgPolicy>(std::move(__first), std::move(__last), __comp);
 }
 
 template <class _RandomAccessIterator>
 inline _LIBCPP_HIDE_FROM_ABI
 void stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last) {
   std::stable_sort(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_STABLE_SORT_H

libcxx/src/algorithm.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
 //
 //===----------------------------------------------------------------------===//
 
+#include <__algorithm/iterator_operations.h>
 #include <algorithm>
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 // TODO(varconst): this currently doesn't benefit `ranges::sort` because it uses `ranges::less` instead of `__less`.
 
-template void __sort<__less<char>&, char*>(char*, char*, __less<char>&);
+template void __sort<_ClassicAlgPolicy, __less<char>&, char*>(char*, char*, __less<char>&);
 #ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS
-template void __sort<__less<wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, __less<wchar_t>&);
+template void __sort<_ClassicAlgPolicy, __less<wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, __less<wchar_t>&);
 #endif
-template void __sort<__less<signed char>&, signed char*>(signed char*, signed char*, __less<signed char>&);
-template void __sort<__less<unsigned char>&, unsigned char*>(unsigned char*, unsigned char*, __less<unsigned char>&);
-template void __sort<__less<short>&, short*>(short*, short*, __less<short>&);
-template void __sort<__less<unsigned short>&, unsigned short*>(unsigned short*, unsigned short*, __less<unsigned short>&);
-template void __sort<__less<int>&, int*>(int*, int*, __less<int>&);
-template void __sort<__less<unsigned>&, unsigned*>(unsigned*, unsigned*, __less<unsigned>&);
-template void __sort<__less<long>&, long*>(long*, long*, __less<long>&);
-template void __sort<__less<unsigned long>&, unsigned long*>(unsigned long*, unsigned long*, __less<unsigned long>&);
-template void __sort<__less<long long>&, long long*>(long long*, long long*, __less<long long>&);
-template void __sort<__less<unsigned long long>&, unsigned long long*>(unsigned long long*, unsigned long long*, __less<unsigned long long>&);
-template void __sort<__less<float>&, float*>(float*, float*, __less<float>&);
-template void __sort<__less<double>&, double*>(double*, double*, __less<double>&);
-template void __sort<__less<long double>&, long double*>(long double*, long double*, __less<long double>&);
+template void __sort<_ClassicAlgPolicy, __less<signed char>&, signed char*>(signed char*, signed char*, __less<signed char>&);
+template void __sort<_ClassicAlgPolicy, __less<unsigned char>&, unsigned char*>(unsigned char*, unsigned char*, __less<unsigned char>&);
+template void __sort<_ClassicAlgPolicy, __less<short>&, short*>(short*, short*, __less<short>&);
+template void __sort<_ClassicAlgPolicy, __less<unsigned short>&, unsigned short*>(unsigned short*, unsigned short*, __less<unsigned short>&);
+template void __sort<_ClassicAlgPolicy, __less<int>&, int*>(int*, int*, __less<int>&);
+template void __sort<_ClassicAlgPolicy, __less<unsigned>&, unsigned*>(unsigned*, unsigned*, __less<unsigned>&);
+template void __sort<_ClassicAlgPolicy, __less<long>&, long*>(long*, long*, __less<long>&);
+template void __sort<_ClassicAlgPolicy, __less<unsigned long>&, unsigned long*>(unsigned long*, unsigned long*, __less<unsigned long>&);
+template void __sort<_ClassicAlgPolicy, __less<long long>&, long long*>(long long*, long long*, __less<long long>&);
+template void __sort<_ClassicAlgPolicy, __less<unsigned long long>&, unsigned long long*>(unsigned long long*, unsigned long long*, __less<unsigned long long>&);
+template void __sort<_ClassicAlgPolicy, __less<float>&, float*>(float*, float*, __less<float>&);
+template void __sort<_ClassicAlgPolicy, __less<double>&, double*>(double*, double*, __less<double>&);
+template void __sort<_ClassicAlgPolicy, __less<long double>&, long double*>(long double*, long double*, __less<long double>&);
 
-template bool __insertion_sort_incomplete<__less<char>&, char*>(char*, char*, __less<char>&);
+template bool __insertion_sort_incomplete<_ClassicAlgPolicy, __less<char>&, char*>(char*, char*, __less<char>&);
 #ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS
-template bool __insertion_sort_incomplete<__less<wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, __less<wchar_t>&);
+template bool __insertion_sort_incomplete<_ClassicAlgPolicy, __less<wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, __less<wchar_t>&);
 #endif
-template bool __insertion_sort_incomplete<__less<signed char>&, signed char*>(signed char*, signed char*, __less<signed char>&);
-template bool __insertion_sort_incomplete<__less<unsigned char>&, unsigned char*>(unsigned char*, unsigned char*, __less<unsigned char>&);
-template bool __insertion_sort_incomplete<__less<short>&, short*>(short*, short*, __less<short>&);
-template bool __insertion_sort_incomplete<__less<unsigned short>&, unsigned short*>(unsigned short*, unsigned short*, __less<unsigned short>&);
-template bool __insertion_sort_incomplete<__less<int>&, int*>(int*, int*, __less<int>&);
-template bool __insertion_sort_incomplete<__less<unsigned>&, unsigned*>(unsigned*, unsigned*, __less<unsigned>&);
-template bool __insertion_sort_incomplete<__less<long>&, long*>(long*, long*, __less<long>&);
-template bool __insertion_sort_incomplete<__less<unsigned long>&, unsigned long*>(unsigned long*, unsigned long*, __less<unsigned long>&);
-template bool __insertion_sort_incomplete<__less<long long>&, long long*>(long long*, long long*, __less<long long>&);
-template bool __insertion_sort_incomplete<__less<unsigned long long>&, unsigned long long*>(unsigned long long*, unsigned long long*, __less<unsigned long long>&);
-template bool __insertion_sort_incomplete<__less<float>&, float*>(float*, float*, __less<float>&);
-template bool __insertion_sort_incomplete<__less<double>&, double*>(double*, double*, __less<double>&);
-template bool __insertion_sort_incomplete<__less<long double>&, long double*>(long double*, long double*, __less<long double>&);
+template bool __insertion_sort_incomplete<_ClassicAlgPolicy, __less<signed char>&, signed char*>(signed char*, signed char*, __less<signed char>&);
+template bool __insertion_sort_incomplete<_ClassicAlgPolicy, __less<unsigned char>&, unsigned char*>(unsigned char*, unsigned char*, __less<unsigned char>&);
+template bool __insertion_sort_incomplete<_ClassicAlgPolicy, __less<short>&, short*>(short*, short*, __less<short>&);
+template bool __insertion_sort_incomplete<_ClassicAlgPolicy, __less<unsigned short>&, unsigned short*>(unsigned short*, unsigned short*, __less<unsigned short>&);
+template bool __insertion_sort_incomplete<_ClassicAlgPolicy, __less<int>&, int*>(int*, int*, __less<int>&);
+template bool __insertion_sort_incomplete<_ClassicAlgPolicy, __less<unsigned>&, unsigned*>(unsigned*, unsigned*, __less<unsigned>&);
+template bool __insertion_sort_incomplete<_ClassicAlgPolicy, __less<long>&, long*>(long*, long*, __less<long>&);
+template bool __insertion_sort_incomplete<_ClassicAlgPolicy, __less<unsigned long>&, unsigned long*>(unsigned long*, unsigned long*, __less<unsigned long>&);
+template bool __insertion_sort_incomplete<_ClassicAlgPolicy, __less<long long>&, long long*>(long long*, long long*, __less<long long>&);
+template bool __insertion_sort_incomplete<_ClassicAlgPolicy, __less<unsigned long long>&, unsigned long long*>(unsigned long long*, unsigned long long*, __less<unsigned long long>&);
+template bool __insertion_sort_incomplete<_ClassicAlgPolicy, __less<float>&, float*>(float*, float*, __less<float>&);
+template bool __insertion_sort_incomplete<_ClassicAlgPolicy, __less<double>&, double*>(double*, double*, __less<double>&);
+template bool __insertion_sort_incomplete<_ClassicAlgPolicy, __less<long double>&, long double*>(long double*, long double*, __less<long double>&);
 
-template unsigned __sort5<__less<long double>&, long double*>(long double*, long double*, long double*, long double*, long double*, __less<long double>&);
+template unsigned __sort5<_ClassicAlgPolicy, __less<long double>&, long double*>(long double*, long double*, long double*, long double*, long double*, __less<long double>&);
 
 _LIBCPP_END_NAMESPACE_STD

libcxx/test/std/algorithms/ranges_robust_against_proxy_iterators.compile.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03, c++11, c++14, c++17
+// UNSUPPORTED: libcpp-has-no-incomplete-ranges
+
+// <algorithm>
+//
+// Range algorithms should work with proxy iterators. For example, the implementations should use `iter_swap` (which is
+// a customization point) rather than plain `swap` (which might not work with certain valid iterators).
+
+#include <algorithm>
+
+#include <array>
+#include <concepts>
+#include <initializer_list>
+#include <iterator>
+#include <memory>
+#include <random>
+#include <ranges>
+
+#include "test_iterators.h"
+
+template <class Func, std::ranges::range Input, class ...Args>
+void test(Func&& func, Input& in, Args&& ...args) {
+  func(in.begin(), in.end(), std::forward<Args>(args)...);
+  func(in, std::forward<Args>(args)...);
+}
+
+template <class Func, std::ranges::range Input, class ...Args>
+void test(Func&& func, Input& in1, Input& in2, Args&& ...args) {
+  func(in1.begin(), in1.end(), in2.begin(), in2.end(), std::forward<Args>(args)...);
+  func(in1, in2, std::forward<Args>(args)...);
+}
+
+template <class Func, std::ranges::range Input, class ...Args>
+void test_mid(Func&& func, Input& in, std::ranges::iterator_t<Input> mid, Args&& ...args) {
+  func(in.begin(), mid, in.end(), std::forward<Args>(args)...);
+  func(in, mid, std::forward<Args>(args)...);
+}
+
+void test_all() {
+  std::array input = {1, 2, 3};
+  ProxyRange in{input};
+  std::array input2 = {4, 5, 6};
+  ProxyRange in2{input2};
+
+  auto mid = in.begin() + 1;
+
+  std::array output = {4, 5, 6};
+  ProxyIterator out{output.begin()};
+  //auto out2 = output.begin() + 1;
+
+  int num = 2;
+  Proxy<int&> x{num};
+  int count = 1;
+
+  auto unary_pred = [](const Proxy<int>& x) { return x.getData() > 0; };
+  auto binary_pred = [](const Proxy<int>& lhs, const Proxy<int>& rhs) { return lhs.getData() == rhs.getData(); };
+  auto binary_func = [](const Proxy<int>& lhs, const Proxy<int>&) -> Proxy<int> { return lhs.getData(); };
+  //auto gen = [] { return Proxy<int>(42); };
+  //std::mt19937 rand_gen;
+
+  test(std::ranges::any_of, in, unary_pred);
+  test(std::ranges::all_of, in, unary_pred);
+  test(std::ranges::none_of, in, unary_pred);
+  test(std::ranges::find, in, x);
+  test(std::ranges::find_if, in, unary_pred);
+  test(std::ranges::find_if_not, in, unary_pred);
+  test(std::ranges::find_first_of, in, in2);
+  test(std::ranges::adjacent_find, in);
+  test(std::ranges::mismatch, in, in2);
+  test(std::ranges::equal, in, in2);
+  test(std::ranges::lexicographical_compare, in, in2);
+  //test(std::ranges::partition_point, unary_pred);
+  test(std::ranges::lower_bound, in, x);
+  test(std::ranges::upper_bound, in, x);
+  //test(std::ranges::equal_range, in, x);
+  test(std::ranges::binary_search, in, x);
+
+  test(std::ranges::min_element, in);
+  test(std::ranges::max_element, in);
+  test(std::ranges::minmax_element, in);
+  test(std::ranges::count, in, x);
+  test(std::ranges::count_if, in, unary_pred);
+  test(std::ranges::search, in, in2);
+  test(std::ranges::search_n, in, count, x);
+  test(std::ranges::find_end, in, in2);
+  test(std::ranges::is_partitioned, in, unary_pred);
+  test(std::ranges::is_sorted, in);
+  test(std::ranges::is_sorted_until, in);
+  //test(std::ranges::includes, in, in2);
+  //test(std::ranges::is_heap, in);
+  //test(std::ranges::is_heap_until, in);
+  //test(std::ranges::is_permutation, in, in2);
+  test(std::ranges::for_each, in, std::identity{});
+  std::ranges::for_each_n(in.begin(), count, std::identity{});
+  test(std::ranges::copy, in, out);
+  std::ranges::copy_n(in.begin(), count, out);
+  test(std::ranges::copy_if, in, out, unary_pred);
+  test(std::ranges::copy_backward, in, out);
+  test(std::ranges::move, in, out);
+  test(std::ranges::move_backward, in, out);
+  test(std::ranges::fill, in, x);
+  std::ranges::fill_n(in.begin(), count, x);
+  test(std::ranges::transform, in, out, std::identity{});
+  test(std::ranges::transform, in, in2, out, binary_func);
+  //test(std::ranges::generate, in, gen);
+  //std::ranges::generate_n(in.begin(), count, gen);
+  //test(std::ranges::remove_copy, in, out, x);
+  //test(std::ranges::remove_copy_if, in, out, unary_pred);
+  test(std::ranges::replace, in, x, x);
+  test(std::ranges::replace_if, in, unary_pred, x);
+  //test(std::ranges::replace_copy, in, out, x, x);
+  //test(std::ranges::replace_copy_if, in, out, unary_pred, x);
+  //test(std::ranges::swap_ranges, in, in2);
+  test(std::ranges::reverse_copy, in, out);
+  test_mid(std::ranges::rotate_copy, in, mid, out);
+  //test(std::ranges::sample, in, out, count, rand_gen);
+  //test(std::ranges::unique_copy, in, out, binary_pred);
+  //test(std::ranges::partition_copy, in, out, out2, unary_pred);
+  //test_mid(std::ranges::partial_sort_copy, in, in2, binary_pred);
+  test(std::ranges::merge, in, in2, out);
+  test(std::ranges::set_difference, in, in2, out);
+  test(std::ranges::set_intersection, in, in2, out);
+  test(std::ranges::set_symmetric_difference, in, in2, out);
+  test(std::ranges::set_union, in, in2, out);
+  test(std::ranges::remove, in, x);
+  test(std::ranges::remove_if, in, unary_pred);
+  test(std::ranges::reverse, in);
+  //test_mid(std::ranges::rotate, in, mid);
+  //test(std::ranges::shuffle, in, rand_gen);
+  //test(std::ranges::unique, in);
+  //test(std::ranges::partition, in, binary_pred);
+  //test(std::ranges::stable_partition, in, binary_pred);
+  test(std::ranges::sort, in);
+  // TODO: `stable_sort` requires `ranges::rotate` to be implemented.
+  //test(std::ranges::stable_sort, in);
+  //test_mid(std::ranges::partial_sort, in, mid);
+  test_mid(std::ranges::nth_element, in, mid);
+  //test_mid(std::ranges::inplace_merge, in, mid);
+  test(std::ranges::make_heap, in);
+  test(std::ranges::push_heap, in, binary_pred);
+  test(std::ranges::pop_heap, in, binary_pred);
+  test(std::ranges::sort_heap, in, binary_pred);
+  //test(std::ranges::prev_permutation, in, binary_pred);
+  //test(std::ranges::next_permutation, in, binary_pred);
+}

libcxx/test/support/test_iterators.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
 //
 //===----------------------------------------------------------------------===//
 
struct Proxy {
   // const assignment required to make ProxyIterator model std::indirectly_writable
   template <class Other>
     requires(IsProxy<std::decay_t<Other>> && std::assignable_from<const T&, decltype(std::declval<Other>().getData())>)
   constexpr const Proxy& operator=(Other&& other) const {
     data = std::forward<Other>(other).getData();
     return *this;
   }
 
+  // If `T` is a reference type, the default assignment operator will be deleted.
+  constexpr Proxy& operator=(const Proxy& rhs) {
+    data = rhs.data;
+    return *this;
+  }
+
   // no specialised swap function that takes const Proxy& and no specialised const member swap
   // Calling swap(Proxy<T>{}, Proxy<T>{}) would fail (pass prvalues)
 
   // Compare operators are defined for the convenience of the tests
   friend constexpr bool operator==(const Proxy&, const Proxy&)
-    requires std::equality_comparable<T>
+    requires (std::equality_comparable<T> && !std::is_reference_v<T>)
   = default;
 
+  // Helps compare e.g. `Proxy<int>` and `Proxy<int&>`. Note that the default equality comparison operator is deleted
+  // when `T` is a reference type.
+  template <class U>
+  friend constexpr bool operator==(const Proxy& lhs, const Proxy<U>& rhs)
+    requires std::equality_comparable_with<std::decay_t<T>, std::decay_t<U>> {
+    return lhs.data == rhs.data;
+  }
+
   friend constexpr auto operator<=>(const Proxy&, const Proxy&)
-    requires std::three_way_comparable<T>
+    requires (std::three_way_comparable<T> && !std::is_reference_v<T>)
   = default;
+
+  // Helps compare e.g. `Proxy<int>` and `Proxy<int&>`. Note that the default 3-way comparison operator is deleted when
+  // `T` is a reference type.
+  template <class U>
+  friend constexpr auto operator<=>(const Proxy& lhs, const Proxy<U>& rhs)
+    requires std::three_way_comparable_with<std::decay_t<T>, std::decay_t<U>> {
+    return lhs.data <=> rhs.data;
+  }
 };
 
 // This is to make ProxyIterator model `std::indirectly_readable`
 template <class T, class U, template <class> class TQual, template <class> class UQual>
   requires requires { typename std::common_reference_t<TQual<T>, UQual<U>>; }
 struct std::basic_common_reference<Proxy<T>, Proxy<U>, TQual, UQual> {
   using type = Proxy<std::common_reference_t<TQual<T>, UQual<U>>>;
 };

 // iter_value_t -> Proxy<int>
 // iter_move    -> Proxy<int&&>
 template <class Base>
 struct ProxyIteratorBase {};
 
 template <class Base>
   requires std::derived_from<
       typename std::iterator_traits<Base>::iterator_category,
-      std::input_iterator_tag> 
+      std::input_iterator_tag>
 struct ProxyIteratorBase<Base> {
   using iterator_category = std::input_iterator_tag;
 };
 
 template <std::input_iterator Base>
 consteval auto get_iterator_concept() {
   if constexpr (std::random_access_iterator<Base>) {
     return std::random_access_iterator_tag{};
struct ProxyIterator : ProxyIteratorBase<Base> {
   using value_type       = Proxy<std::iter_value_t<Base>>;
   using difference_type  = std::iter_difference_t<Base>;
 
   ProxyIterator()
     requires std::default_initializable<Base>
   = default;
 
   constexpr ProxyIterator(Base base) : base_{std::move(base)} {}
-  
-  template <class T> 
+  template <class T>
     requires std::constructible_from<Base, T&&>
   constexpr ProxyIterator(T&& t) : base_{std::forward<T>(t)} {}
 
   friend constexpr decltype(auto) base(const ProxyIterator& p) { return base(p.base_); }
 
   // Specialization of iter_move
   // If operator* returns Proxy<Foo&>, iter_move will return Proxy<Foo&&>
   // Note std::move(*it) returns Proxy<Foo&>&&, which is not what we want as
struct ProxyIterator : ProxyIteratorBase<Base> {
   friend constexpr difference_type operator-(const ProxyIterator& x, const ProxyIterator& y)
     requires std::random_access_iterator<Base> {
     return x.base_ - y.base_;
   }
 };
 
 static_assert(std::indirectly_readable<ProxyIterator<int*>>);
 static_assert(std::indirectly_writable<ProxyIterator<int*>, Proxy<int>>);
+static_assert(std::indirectly_writable<ProxyIterator<int*>, Proxy<int&>>);
 
 template <class BaseSent>
 struct ProxySentinel {
   BaseSent base_;
 
   ProxySentinel() = default;
   constexpr ProxySentinel(BaseSent base) : base_{std::move(base)} {}