vendor/llvm-project/llvmorg-17-init-19304-gd0b54bb50e51

1 files changed, 196 insertions, 232 deletions

diff --git a/libcxx/include/__algorithm/sort.h b/libcxx/include/__algorithm/sort.h
index a7d2d55a06f8..3b594fa4d2a8 100644
--- a/libcxx/include/__algorithm/sort.h
+++ b/libcxx/include/__algorithm/sort.h
@@ -21,15 +21,15 @@
 #include <__bit/countl.h>
 #include <__bit/countr.h>
 #include <__config>
-#include <__debug>
 #include <__debug_utils/randomize_range.h>
+#include <__debug_utils/strict_weak_ordering_check.h>
 #include <__functional/operations.h>
 #include <__functional/ranges_operations.h>
 #include <__iterator/iterator_traits.h>
-#include <__memory/destruct_n.h>
-#include <__memory/unique_ptr.h>
 #include <__type_traits/conditional.h>
+#include <__type_traits/disjunction.h>
 #include <__type_traits/is_arithmetic.h>
+#include <__type_traits/is_constant_evaluated.h>
 #include <__utility/move.h>
 #include <__utility/pair.h>
 #include <climits>
@@ -41,52 +41,6 @@
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
-// Wraps an algorithm policy tag and a comparator in a single struct, used to pass the policy tag around without
-// changing the number of template arguments (to keep the ABI stable). This is only used for the "range" policy tag.
-//
-// To create an object of this type, use `_WrapAlgPolicy<T, C>::type` -- see the specialization below for the rationale.
-template <class _PolicyT, class _CompT, class = void>
-struct _WrapAlgPolicy {
-  using type = _WrapAlgPolicy;
-
-  using _AlgPolicy = _PolicyT;
-  using _Comp = _CompT;
-  _Comp& __comp;
-
-  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14
-  _WrapAlgPolicy(_Comp& __c) : __comp(__c) {}
-};
-
-// Specialization for the "classic" policy tag that avoids creating a struct and simply defines an alias for the
-// comparator. When unwrapping, a pristine comparator is always considered to have the "classic" tag attached. Passing
-// the pristine comparator where possible allows using template instantiations from the dylib.
-template <class _PolicyT, class _CompT>
-struct _WrapAlgPolicy<_PolicyT, _CompT, __enable_if_t<std::is_same<_PolicyT, _ClassicAlgPolicy>::value> > {
-  using type = _CompT;
-};
-
-// Unwraps a pristine functor (e.g. `std::less`) as if it were wrapped using `_WrapAlgPolicy`. The policy tag is always
-// set to "classic".
-template <class _CompT>
-struct _UnwrapAlgPolicy {
-  using _AlgPolicy = _ClassicAlgPolicy;
-  using _Comp = _CompT;
-
-  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 static
-  _Comp __get_comp(_Comp __comp) { return __comp; }
-};
-
-// Unwraps a `_WrapAlgPolicy` struct.
-template <class... _Ts>
-struct _UnwrapAlgPolicy<_WrapAlgPolicy<_Ts...> > {
-  using _Wrapped = _WrapAlgPolicy<_Ts...>;
-  using _AlgPolicy = typename _Wrapped::_AlgPolicy;
-  using _Comp = typename _Wrapped::_Comp;
-
-  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 static
-  _Comp __get_comp(_Wrapped& __w) { return __w.__comp; }
-};
-
 // stable, 2-3 compares, 0-2 swaps
 
 template <class _AlgPolicy, class _Compare, class _ForwardIterator>
@@ -130,77 +84,53 @@ _LIBCPP_CONSTEXPR_SINCE_CXX14 unsigned __sort3(_ForwardIterator __x, _ForwardIte
 
 template <class _AlgPolicy, class _Compare, class _ForwardIterator>
 _LIBCPP_HIDE_FROM_ABI
-unsigned __sort4(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3, _ForwardIterator __x4,
+void __sort4(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3, _ForwardIterator __x4,
                  _Compare __c) {
   using _Ops   = _IterOps<_AlgPolicy>;
-  unsigned __r = std::__sort3<_AlgPolicy, _Compare>(__x1, __x2, __x3, __c);
+  std::__sort3<_AlgPolicy, _Compare>(__x1, __x2, __x3, __c);
   if (__c(*__x4, *__x3)) {
     _Ops::iter_swap(__x3, __x4);
-    ++__r;
     if (__c(*__x3, *__x2)) {
       _Ops::iter_swap(__x2, __x3);
-      ++__r;
       if (__c(*__x2, *__x1)) {
         _Ops::iter_swap(__x1, __x2);
-        ++__r;
       }
     }
   }
-  return __r;
 }
 
 // stable, 4-10 compares, 0-9 swaps
 
-template <class _WrappedComp, class _ForwardIterator>
-_LIBCPP_HIDDEN unsigned __sort5(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3,
-                                _ForwardIterator __x4, _ForwardIterator __x5, _WrappedComp __wrapped_comp) {
-  using _Unwrap = _UnwrapAlgPolicy<_WrappedComp>;
-  using _AlgPolicy = typename _Unwrap::_AlgPolicy;
+template <class _AlgPolicy, class _Comp, class _ForwardIterator>
+_LIBCPP_HIDE_FROM_ABI void __sort5(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3,
+                                   _ForwardIterator __x4, _ForwardIterator __x5, _Comp __comp) {
   using _Ops = _IterOps<_AlgPolicy>;
 
-  using _Compare = typename _Unwrap::_Comp;
-  _Compare __c = _Unwrap::__get_comp(__wrapped_comp);
-
-  unsigned __r = std::__sort4<_AlgPolicy, _Compare>(__x1, __x2, __x3, __x4, __c);
-  if (__c(*__x5, *__x4)) {
+  std::__sort4<_AlgPolicy, _Comp>(__x1, __x2, __x3, __x4, __comp);
+  if (__comp(*__x5, *__x4)) {
     _Ops::iter_swap(__x4, __x5);
-    ++__r;
-    if (__c(*__x4, *__x3)) {
+    if (__comp(*__x4, *__x3)) {
       _Ops::iter_swap(__x3, __x4);
-      ++__r;
-      if (__c(*__x3, *__x2)) {
+      if (__comp(*__x3, *__x2)) {
         _Ops::iter_swap(__x2, __x3);
-        ++__r;
-        if (__c(*__x2, *__x1)) {
+        if (__comp(*__x2, *__x1)) {
           _Ops::iter_swap(__x1, __x2);
-          ++__r;
         }
       }
     }
   }
-  return __r;
-}
-
-template <class _AlgPolicy, class _Compare, class _ForwardIterator>
-_LIBCPP_HIDE_FROM_ABI unsigned __sort5_wrap_policy(
-    _ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3, _ForwardIterator __x4, _ForwardIterator __x5,
-    _Compare __c) {
-  using _WrappedComp = typename _WrapAlgPolicy<_AlgPolicy, _Compare>::type;
-  _WrappedComp __wrapped_comp(__c);
-  return std::__sort5<_WrappedComp, _ForwardIterator>(
-      std::move(__x1), std::move(__x2), std::move(__x3), std::move(__x4), std::move(__x5), __wrapped_comp);
 }
 
 // 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 <>
+struct __is_simple_comparator<__less<>&> : 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
+#if _LIBCPP_STD_VER >= 20
 template <>
 struct __is_simple_comparator<ranges::less&> : true_type {};
 template <>
@@ -209,7 +139,7 @@ struct __is_simple_comparator<ranges::greater&> : true_type {};
 
 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*) &&
+    integral_constant<bool, __libcpp_is_contiguous_iterator<_Iter>::value && sizeof(_Tp) <= sizeof(void*) &&
                                 is_arithmetic<_Tp>::value && __is_simple_comparator<_Compare>::value>;
 
 namespace __detail {
@@ -299,7 +229,8 @@ 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) {
-  std::__sort5_wrap_policy<_AlgPolicy, _Compare>(__x1, __x2, __x3, __x4, __x5, __c);
+  std::__sort5<_AlgPolicy, _Compare, _RandomAccessIterator>(
+      std::move(__x1), std::move(__x2), std::move(__x3), std::move(__x4), std::move(__x5), __c);
 }
 
 // Assumes size > 0
@@ -344,17 +275,18 @@ void __insertion_sort(_BidirectionalIterator __first, _BidirectionalIterator __l
 
 // Sort the iterator range [__first, __last) using the comparator __comp using
 // the insertion sort algorithm.  Insertion sort has two loops, outer and inner.
-// The implementation below has not bounds check (unguarded) for the inner loop.
+// The implementation below has no bounds check (unguarded) for the inner loop.
 // Assumes that there is an element in the position (__first - 1) and that each
 // element in the input range is greater or equal to the element at __first - 1.
 template <class _AlgPolicy, class _Compare, class _RandomAccessIterator>
 _LIBCPP_HIDE_FROM_ABI void
-__insertion_sort_unguarded(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) {
+__insertion_sort_unguarded(_RandomAccessIterator const __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;
   if (__first == __last)
     return;
+  const _RandomAccessIterator __leftmost = __first - difference_type(1); (void)__leftmost; // can be unused when assertions are disabled
   for (_RandomAccessIterator __i = __first + difference_type(1); __i != __last; ++__i) {
     _RandomAccessIterator __j = __i - difference_type(1);
     if (__comp(*__i, *__j)) {
@@ -364,22 +296,20 @@ __insertion_sort_unguarded(_RandomAccessIterator __first, _RandomAccessIterator
       do {
         *__j = _Ops::__iter_move(__k);
         __j = __k;
+        _LIBCPP_ASSERT_UNCATEGORIZED(
+            __k != __leftmost,
+            "Would read out of bounds, does your comparator satisfy the strict-weak ordering requirement?");
       } while (__comp(__t, *--__k)); // No need for bounds check due to the assumption stated above.
       *__j = std::move(__t);
     }
   }
 }
 
-template <class _WrappedComp, class _RandomAccessIterator>
-_LIBCPP_HIDDEN bool __insertion_sort_incomplete(
-    _RandomAccessIterator __first, _RandomAccessIterator __last, _WrappedComp __wrapped_comp) {
-  using _Unwrap = _UnwrapAlgPolicy<_WrappedComp>;
-  using _AlgPolicy = typename _Unwrap::_AlgPolicy;
+template <class _AlgPolicy, class _Comp, class _RandomAccessIterator>
+_LIBCPP_HIDE_FROM_ABI bool __insertion_sort_incomplete(
+    _RandomAccessIterator __first, _RandomAccessIterator __last, _Comp __comp) {
   using _Ops = _IterOps<_AlgPolicy>;
 
-  using _Compare = typename _Unwrap::_Comp;
-  _Compare __comp = _Unwrap::__get_comp(__wrapped_comp);
-
   typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
   switch (__last - __first) {
   case 0:
@@ -390,21 +320,21 @@ _LIBCPP_HIDDEN bool __insertion_sort_incomplete(
       _Ops::iter_swap(__first, __last);
     return true;
   case 3:
-    std::__sort3_maybe_branchless<_AlgPolicy, _Compare>(__first, __first + difference_type(1), --__last, __comp);
+    std::__sort3_maybe_branchless<_AlgPolicy, _Comp>(__first, __first + difference_type(1), --__last, __comp);
     return true;
   case 4:
-    std::__sort4_maybe_branchless<_AlgPolicy, _Compare>(
+    std::__sort4_maybe_branchless<_AlgPolicy, _Comp>(
         __first, __first + difference_type(1), __first + difference_type(2), --__last, __comp);
     return true;
   case 5:
-    std::__sort5_maybe_branchless<_AlgPolicy, _Compare>(
+    std::__sort5_maybe_branchless<_AlgPolicy, _Comp>(
         __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);
-  std::__sort3_maybe_branchless<_AlgPolicy, _Compare>(__first, __first + difference_type(1), __j, __comp);
+  std::__sort3_maybe_branchless<_AlgPolicy, _Comp>(__first, __first + difference_type(1), __j, __comp);
   const unsigned __limit = 8;
   unsigned __count = 0;
   for (_RandomAccessIterator __i = __j + difference_type(1); __i != __last; ++__i) {
@@ -425,37 +355,6 @@ _LIBCPP_HIDDEN bool __insertion_sort_incomplete(
   return true;
 }
 
-template <class _AlgPolicy, class _Compare, class _BidirectionalIterator>
-_LIBCPP_HIDE_FROM_ABI
-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(_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(std::move(*__i2));
-        __d.template __incr<value_type>();
-        for (--__j2; __i2 != __first2 && __comp(*__first1, *--__i2); --__j2)
-          *__j2 = std::move(*__i2);
-        *__j2 = _Ops::__iter_move(__first1);
-      } else {
-        ::new ((void*)__j2) value_type(_Ops::__iter_move(__first1));
-        __d.template __incr<value_type>();
-      }
-    }
-    __h.release();
-  }
-}
-
 template <class _AlgPolicy, class _RandomAccessIterator>
 inline _LIBCPP_HIDE_FROM_ABI void __swap_bitmap_pos(
     _RandomAccessIterator __first, _RandomAccessIterator __last, uint64_t& __left_bitset, uint64_t& __right_bitset) {
@@ -464,11 +363,11 @@ inline _LIBCPP_HIDE_FROM_ABI void __swap_bitmap_pos(
   // Swap one pair on each iteration as long as both bitsets have at least one
   // element for swapping.
   while (__left_bitset != 0 && __right_bitset != 0) {
-    difference_type tz_left  = __libcpp_ctz(__left_bitset);
-    __left_bitset            = __libcpp_blsr(__left_bitset);
-    difference_type tz_right = __libcpp_ctz(__right_bitset);
-    __right_bitset           = __libcpp_blsr(__right_bitset);
-    _Ops::iter_swap(__first + tz_left, __last - tz_right);
+    difference_type __tz_left  = __libcpp_ctz(__left_bitset);
+    __left_bitset              = __libcpp_blsr(__left_bitset);
+    difference_type __tz_right = __libcpp_ctz(__right_bitset);
+    __right_bitset             = __libcpp_blsr(__right_bitset);
+    _Ops::iter_swap(__first + __tz_left, __last - __tz_right);
   }
 }
 
@@ -533,9 +432,9 @@ inline _LIBCPP_HIDE_FROM_ABI void __bitset_partition_partial_blocks(
   // Record the comparison outcomes for the elements currently on the left side.
   if (__left_bitset == 0) {
     _RandomAccessIterator __iter = __first;
-    for (int j = 0; j < __l_size; j++) {
+    for (int __j = 0; __j < __l_size; __j++) {
       bool __comp_result = !__comp(*__iter, __pivot);
-      __left_bitset |= (static_cast<uint64_t>(__comp_result) << j);
+      __left_bitset |= (static_cast<uint64_t>(__comp_result) << __j);
       ++__iter;
     }
   }
@@ -543,9 +442,9 @@ inline _LIBCPP_HIDE_FROM_ABI void __bitset_partition_partial_blocks(
   // side.
   if (__right_bitset == 0) {
     _RandomAccessIterator __iter = __lm1;
-    for (int j = 0; j < __r_size; j++) {
+    for (int __j = 0; __j < __r_size; __j++) {
       bool __comp_result = __comp(*__iter, __pivot);
-      __right_bitset |= (static_cast<uint64_t>(__comp_result) << j);
+      __right_bitset |= (static_cast<uint64_t>(__comp_result) << __j);
       --__iter;
     }
   }
@@ -565,9 +464,9 @@ inline _LIBCPP_HIDE_FROM_ABI void __swap_bitmap_pos_within(
     while (__left_bitset != 0) {
       difference_type __tz_left = __detail::__block_size - 1 - __libcpp_clz(__left_bitset);
       __left_bitset &= (static_cast<uint64_t>(1) << __tz_left) - 1;
-      _RandomAccessIterator it = __first + __tz_left;
-      if (it != __lm1) {
-        _Ops::iter_swap(it, __lm1);
+      _RandomAccessIterator __it = __first + __tz_left;
+      if (__it != __lm1) {
+        _Ops::iter_swap(__it, __lm1);
       }
       --__lm1;
     }
@@ -578,9 +477,9 @@ inline _LIBCPP_HIDE_FROM_ABI void __swap_bitmap_pos_within(
     while (__right_bitset != 0) {
       difference_type __tz_right = __detail::__block_size - 1 - __libcpp_clz(__right_bitset);
       __right_bitset &= (static_cast<uint64_t>(1) << __tz_right) - 1;
-      _RandomAccessIterator it = __lm1 - __tz_right;
-      if (it != __first) {
-        _Ops::iter_swap(it, __first);
+      _RandomAccessIterator __it = __lm1 - __tz_right;
+      if (__it != __first) {
+        _Ops::iter_swap(__it, __first);
       }
       ++__first;
     }
@@ -601,15 +500,20 @@ __bitset_partition(_RandomAccessIterator __first, _RandomAccessIterator __last,
   using _Ops = _IterOps<_AlgPolicy>;
   typedef typename std::iterator_traits<_RandomAccessIterator>::value_type value_type;
   typedef typename std::iterator_traits<_RandomAccessIterator>::difference_type difference_type;
-  _LIBCPP_ASSERT(__last - __first >= difference_type(3), "");
+  _LIBCPP_ASSERT_UNCATEGORIZED(__last - __first >= difference_type(3), "");
+  const _RandomAccessIterator __begin = __first;            // used for bounds checking, those are not moved around
+  const _RandomAccessIterator __end = __last; (void)__end;  //
 
-  _RandomAccessIterator __begin = __first;
   value_type __pivot(_Ops::__iter_move(__first));
   // Find the first element greater than the pivot.
   if (__comp(__pivot, *(__last - difference_type(1)))) {
     // Not guarded since we know the last element is greater than the pivot.
-    while (!__comp(__pivot, *++__first)) {
-    }
+    do {
+      ++__first;
+      _LIBCPP_ASSERT_UNCATEGORIZED(
+          __first != __end,
+          "Would read out of bounds, does your comparator satisfy the strict-weak ordering requirement?");
+    } while (!__comp(__pivot, *__first));
   } else {
     while (++__first < __last && !__comp(__pivot, *__first)) {
     }
@@ -618,8 +522,12 @@ __bitset_partition(_RandomAccessIterator __first, _RandomAccessIterator __last,
   if (__first < __last) {
     // It will be always guarded because __introsort will do the median-of-three
     // before calling this.
-    while (__comp(__pivot, *--__last)) {
-    }
+    do {
+      _LIBCPP_ASSERT_UNCATEGORIZED(
+          __last != __begin,
+          "Would read out of bounds, does your comparator satisfy the strict-weak ordering requirement?");
+      --__last;
+    } while (__comp(__pivot, *__last));
   }
   // If the first element greater than the pivot is at or after the
   // last element less than or equal to the pivot, then we have covered the
@@ -683,14 +591,19 @@ __partition_with_equals_on_right(_RandomAccessIterator __first, _RandomAccessIte
   using _Ops = _IterOps<_AlgPolicy>;
   typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
   typedef typename std::iterator_traits<_RandomAccessIterator>::value_type value_type;
-  _LIBCPP_ASSERT(__last - __first >= difference_type(3), "");
-  _RandomAccessIterator __begin = __first;
+  _LIBCPP_ASSERT_UNCATEGORIZED(__last - __first >= difference_type(3), "");
+  const _RandomAccessIterator __begin = __first;            // used for bounds checking, those are not moved around
+  const _RandomAccessIterator __end = __last; (void)__end;  //
   value_type __pivot(_Ops::__iter_move(__first));
   // Find the first element greater or equal to the pivot.  It will be always
   // guarded because __introsort will do the median-of-three before calling
   // this.
-  while (__comp(*++__first, __pivot))
-    ;
+  do {
+    ++__first;
+    _LIBCPP_ASSERT_UNCATEGORIZED(
+        __first != __end,
+        "Would read out of bounds, does your comparator satisfy the strict-weak ordering requirement?");
+  } while (__comp(*__first, __pivot));
 
   // Find the last element less than the pivot.
   if (__begin == __first - difference_type(1)) {
@@ -698,8 +611,12 @@ __partition_with_equals_on_right(_RandomAccessIterator __first, _RandomAccessIte
       ;
   } else {
     // Guarded.
-    while (!__comp(*--__last, __pivot))
-      ;
+    do {
+      _LIBCPP_ASSERT_UNCATEGORIZED(
+          __last != __begin,
+          "Would read out of bounds, does your comparator satisfy the strict-weak ordering requirement?");
+      --__last;
+    } while (!__comp(*__last, __pivot));
   }
 
   // If the first element greater than or equal to the pivot is at or after the
@@ -711,10 +628,18 @@ __partition_with_equals_on_right(_RandomAccessIterator __first, _RandomAccessIte
   // correct side of the pivot.
   while (__first < __last) {
     _Ops::iter_swap(__first, __last);
-    while (__comp(*++__first, __pivot))
-      ;
-    while (!__comp(*--__last, __pivot))
-      ;
+    do {
+      ++__first;
+      _LIBCPP_ASSERT_UNCATEGORIZED(
+          __first != __end,
+          "Would read out of bounds, does your comparator satisfy the strict-weak ordering requirement?");
+    } while (__comp(*__first, __pivot));
+    do {
+      _LIBCPP_ASSERT_UNCATEGORIZED(
+          __last != __begin,
+          "Would read out of bounds, does your comparator satisfy the strict-weak ordering requirement?");
+      --__last;
+    } while (!__comp(*__last, __pivot));
   }
   // Move the pivot to its correct position.
   _RandomAccessIterator __pivot_pos = __first - difference_type(1);
@@ -733,12 +658,18 @@ __partition_with_equals_on_left(_RandomAccessIterator __first, _RandomAccessIter
   using _Ops = _IterOps<_AlgPolicy>;
   typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
   typedef typename std::iterator_traits<_RandomAccessIterator>::value_type value_type;
-  _RandomAccessIterator __begin = __first;
+  // TODO(LLVM18): Make __begin const, see https://reviews.llvm.org/D147089#4349748
+  _RandomAccessIterator __begin = __first;                  // used for bounds checking, those are not moved around
+  const _RandomAccessIterator __end = __last; (void)__end;  //
   value_type __pivot(_Ops::__iter_move(__first));
   if (__comp(__pivot, *(__last - difference_type(1)))) {
     // Guarded.
-    while (!__comp(__pivot, *++__first)) {
-    }
+    do {
+      ++__first;
+      _LIBCPP_ASSERT_UNCATEGORIZED(
+          __first != __end,
+          "Would read out of bounds, does your comparator satisfy the strict-weak ordering requirement?");
+    } while (!__comp(__pivot, *__first));
   } else {
     while (++__first < __last && !__comp(__pivot, *__first)) {
     }
@@ -747,15 +678,27 @@ __partition_with_equals_on_left(_RandomAccessIterator __first, _RandomAccessIter
   if (__first < __last) {
     // It will be always guarded because __introsort will do the
     // median-of-three before calling this.
-    while (__comp(__pivot, *--__last)) {
-    }
+    do {
+      _LIBCPP_ASSERT_UNCATEGORIZED(
+          __last != __begin,
+          "Would read out of bounds, does your comparator satisfy the strict-weak ordering requirement?");
+      --__last;
+    } while (__comp(__pivot, *__last));
   }
   while (__first < __last) {
     _Ops::iter_swap(__first, __last);
-    while (!__comp(__pivot, *++__first))
-      ;
-    while (__comp(__pivot, *--__last))
-      ;
+    do {
+      ++__first;
+      _LIBCPP_ASSERT_UNCATEGORIZED(
+          __first != __end,
+          "Would read out of bounds, does your comparator satisfy the strict-weak ordering requirement?");
+    } while (!__comp(__pivot, *__first));
+    do {
+      _LIBCPP_ASSERT_UNCATEGORIZED(
+          __last != __begin,
+          "Would read out of bounds, does your comparator satisfy the strict-weak ordering requirement?");
+      --__last;
+    } while (__comp(__pivot, *__last));
   }
   _RandomAccessIterator __pivot_pos = __first - difference_type(1);
   if (__begin != __pivot_pos) {
@@ -862,10 +805,8 @@ void __introsort(_RandomAccessIterator __first,
     // [__first, __i) < *__i and *__i <= [__i+1, __last)
     // If we were given a perfect partition, see if insertion sort is quick...
     if (__ret.second) {
-      using _WrappedComp = typename _WrapAlgPolicy<_AlgPolicy, _Compare>::type;
-      _WrappedComp __wrapped_comp(__comp);
-      bool __fs = std::__insertion_sort_incomplete<_WrappedComp>(__first, __i, __wrapped_comp);
-      if (std::__insertion_sort_incomplete<_WrappedComp>(__i + difference_type(1), __last, __wrapped_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;
@@ -904,84 +845,107 @@ inline _LIBCPP_HIDE_FROM_ABI _Number __log2i(_Number __n) {
   return __log2;
 }
 
-template <class _WrappedComp, class _RandomAccessIterator>
-_LIBCPP_HIDDEN void __sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _WrappedComp __wrapped_comp) {
+template <class _Comp, class _RandomAccessIterator>
+void __sort(_RandomAccessIterator, _RandomAccessIterator, _Comp);
+
+extern template _LIBCPP_EXPORTED_FROM_ABI void __sort<__less<char>&, char*>(char*, char*, __less<char>&);
+#ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS
+extern template _LIBCPP_EXPORTED_FROM_ABI void __sort<__less<wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, __less<wchar_t>&);
+#endif
+extern template _LIBCPP_EXPORTED_FROM_ABI void __sort<__less<signed char>&, signed char*>(signed char*, signed char*, __less<signed char>&);
+extern template _LIBCPP_EXPORTED_FROM_ABI void __sort<__less<unsigned char>&, unsigned char*>(unsigned char*, unsigned char*, __less<unsigned char>&);
+extern template _LIBCPP_EXPORTED_FROM_ABI void __sort<__less<short>&, short*>(short*, short*, __less<short>&);
+extern template _LIBCPP_EXPORTED_FROM_ABI void __sort<__less<unsigned short>&, unsigned short*>(unsigned short*, unsigned short*, __less<unsigned short>&);
+extern template _LIBCPP_EXPORTED_FROM_ABI void __sort<__less<int>&, int*>(int*, int*, __less<int>&);
+extern template _LIBCPP_EXPORTED_FROM_ABI void __sort<__less<unsigned>&, unsigned*>(unsigned*, unsigned*, __less<unsigned>&);
+extern template _LIBCPP_EXPORTED_FROM_ABI void __sort<__less<long>&, long*>(long*, long*, __less<long>&);
+extern template _LIBCPP_EXPORTED_FROM_ABI void __sort<__less<unsigned long>&, unsigned long*>(unsigned long*, unsigned long*, __less<unsigned long>&);
+extern template _LIBCPP_EXPORTED_FROM_ABI void __sort<__less<long long>&, long long*>(long long*, long long*, __less<long long>&);
+extern template _LIBCPP_EXPORTED_FROM_ABI void __sort<__less<unsigned long long>&, unsigned long long*>(unsigned long long*, unsigned long long*, __less<unsigned long long>&);
+extern template _LIBCPP_EXPORTED_FROM_ABI void __sort<__less<float>&, float*>(float*, float*, __less<float>&);
+extern template _LIBCPP_EXPORTED_FROM_ABI void __sort<__less<double>&, double*>(double*, double*, __less<double>&);
+extern template _LIBCPP_EXPORTED_FROM_ABI void __sort<__less<long double>&, long double*>(long double*, long double*, __less<long double>&);
+
+template <class _AlgPolicy, class _RandomAccessIterator, class _Comp>
+_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void
+__sort_dispatch(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp& __comp) {
   typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
   difference_type __depth_limit = 2 * std::__log2i(__last - __first);
 
-  using _Unwrap = _UnwrapAlgPolicy<_WrappedComp>;
-  using _AlgPolicy = typename _Unwrap::_AlgPolicy;
-  using _Compare = typename _Unwrap::_Comp;
-  _Compare __comp = _Unwrap::__get_comp(__wrapped_comp);
   // Only use bitset partitioning for arithmetic types.  We should also check
   // that the default comparator is in use so that we are sure that there are no
   // branches in the comparator.
   std::__introsort<_AlgPolicy,
-                   _Compare,
+                   _Comp&,
                    _RandomAccessIterator,
-                   __use_branchless_sort<_Compare, _RandomAccessIterator>::value>(
+                   __use_branchless_sort<_Comp, _RandomAccessIterator>::value>(
       __first, __last, __comp, __depth_limit);
 }
 
-template <class _Compare, class _Tp>
-inline _LIBCPP_INLINE_VISIBILITY void __sort(_Tp** __first, _Tp** __last, __less<_Tp*>&) {
-  __less<uintptr_t> __comp;
-  std::__sort<__less<uintptr_t>&, uintptr_t*>((uintptr_t*)__first, (uintptr_t*)__last, __comp);
-}
+template <class _Type, class... _Options>
+using __is_any_of = _Or<is_same<_Type, _Options>...>;
 
-extern template _LIBCPP_FUNC_VIS void __sort<__less<char>&, char*>(char*, char*, __less<char>&);
+template <class _Type>
+using __sort_is_specialized_in_library = __is_any_of<
+    _Type,
+    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>&);
+    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 bool __insertion_sort_incomplete<__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>&);
+    signed char,
+    unsigned char,
+    short,
+    unsigned short,
+    int,
+    unsigned int,
+    long,
+    unsigned long,
+    long long,
+    unsigned long long,
+    float,
+    double,
+    long double>;
+
+template <class _AlgPolicy, class _Type, __enable_if_t<__sort_is_specialized_in_library<_Type>::value, int> = 0>
+_LIBCPP_HIDE_FROM_ABI void __sort_dispatch(_Type* __first, _Type* __last, __less<>&) {
+  __less<_Type> __comp;
+  std::__sort<__less<_Type>&, _Type*>(__first, __last, __comp);
+}
+
+template <class _AlgPolicy, class _Type, __enable_if_t<__sort_is_specialized_in_library<_Type>::value, int> = 0>
+_LIBCPP_HIDE_FROM_ABI void __sort_dispatch(_Type* __first, _Type* __last, less<_Type>&) {
+  __less<_Type> __comp;
+  std::__sort<__less<_Type>&, _Type*>(__first, __last, __comp);
+}
+
+#if _LIBCPP_STD_VER >= 14
+template <class _AlgPolicy, class _Type, __enable_if_t<__sort_is_specialized_in_library<_Type>::value, int> = 0>
+_LIBCPP_HIDE_FROM_ABI void __sort_dispatch(_Type* __first, _Type* __last, less<>&) {
+  __less<_Type> __comp;
+  std::__sort<__less<_Type>&, _Type*>(__first, __last, __comp);
+}
+#endif
+
+#if _LIBCPP_STD_VER >= 20
+template <class _AlgPolicy, class _Type, __enable_if_t<__sort_is_specialized_in_library<_Type>::value, int> = 0>
+_LIBCPP_HIDE_FROM_ABI void __sort_dispatch(_Type* __first, _Type* __last, ranges::less&) {
+  __less<_Type> __comp;
+  std::__sort<__less<_Type>&, _Type*>(__first, __last, __comp);
+}
 #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 unsigned __sort5<__less<long double>&, long double*>(long double*, long double*, long double*, long double*, long double*, __less<long double>&);
 
 template <class _AlgPolicy, class _RandomAccessIterator, class _Comp>
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
 void __sort_impl(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp& __comp) {
   std::__debug_randomize_range<_AlgPolicy>(__first, __last);
 
-  using _Comp_ref = __comp_ref_type<_Comp>;
   if (__libcpp_is_constant_evaluated()) {
-    std::__partial_sort<_AlgPolicy>(__first, __last, __last, __comp);
-
+    std::__partial_sort<_AlgPolicy>(
+        std::__unwrap_iter(__first), std::__unwrap_iter(__last), std::__unwrap_iter(__last), __comp);
   } else {
-    using _WrappedComp = typename _WrapAlgPolicy<_AlgPolicy, _Comp_ref>::type;
-    _Comp_ref __comp_ref(__comp);
-    _WrappedComp __wrapped_comp(__comp_ref);
-    std::__sort<_WrappedComp>(std::__unwrap_iter(__first), std::__unwrap_iter(__last), __wrapped_comp);
+    std::__sort_dispatch<_AlgPolicy>(std::__unwrap_iter(__first), std::__unwrap_iter(__last), __comp);
   }
+  std::__check_strict_weak_ordering_sorted(std::__unwrap_iter(__first), std::__unwrap_iter(__last), __comp);
 }
 
 template <class _RandomAccessIterator, class _Comp>
@@ -993,7 +957,7 @@ void sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp __c
 template <class _RandomAccessIterator>
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
 void sort(_RandomAccessIterator __first, _RandomAccessIterator __last) {
-  std::sort(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
+  std::sort(__first, __last, __less<>());
 }
 
 _LIBCPP_END_NAMESPACE_STD