[libc++] Avoid dereferencing a const iterator in std::sort

[ldionne]

Summary

This is a workaround to provide a grace period for folks that were
broken by D147089. As a fly-by, also apply comments by Mark I had
somehow missed in the review.

libcxx/include/__algorithm/sort.h

for (_RandomAccessIterator __i = __first + difference_type(1); __i != __last; ++__i) {
     _RandomAccessIterator __j = __i - difference_type(1);
     if (__comp(*__i, *__j)) {
       value_type __t(_Ops::__iter_move(__i));
       _RandomAccessIterator __k = __j;
       __j = __i;
       do {
         *__j = _Ops::__iter_move(__k);
         __j = __k;
-        _LIBCPP_ASSERT(__k != __leftmost, "Would read out of bounds, is your comparator a valid strict-weak ordering?");
+        _LIBCPP_ASSERT(__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 _AlgPolicy, class _Comp, class _RandomAccessIterator>
 _LIBCPP_HIDE_FROM_ABI bool __insertion_sort_incomplete(
__bitset_partition(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) {
   const _RandomAccessIterator __end = __last; (void)__end;  //
 
   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.
     do {
       ++__first;
-      _LIBCPP_ASSERT(__first != __end, "Would read out of bounds, is your comparator a valid strict-weak ordering?");
+      _LIBCPP_ASSERT(__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)) {
     }
   }
   // Find the last element less than or equal to the pivot.
   if (__first < __last) {
     // It will be always guarded because __introsort will do the median-of-three
     // before calling this.
     do {
-      _LIBCPP_ASSERT(__last != __begin, "Would read out of bounds, is your comparator a valid strict-weak ordering?");
+      _LIBCPP_ASSERT(__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
   // entire range without swapping elements.  This implies the range is already
   // partitioned.
   bool __already_partitioned = __first >= __last;
__partition_with_equals_on_right(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) {
   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.
   do {
     ++__first;
-    _LIBCPP_ASSERT(__first != __end, "Would read out of bounds, is your comparator a valid strict-weak ordering?");
+    _LIBCPP_ASSERT(__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)) {
     while (__first < __last && !__comp(*--__last, __pivot))
       ;
   } else {
     // Guarded.
     do {
-      _LIBCPP_ASSERT(__last != __begin, "Would read out of bounds, is your comparator a valid strict-weak ordering?");
+      _LIBCPP_ASSERT(__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
   // last element less than the pivot, then we have covered the entire range
   // without swapping elements.  This implies the range is already partitioned.
   bool __already_partitioned = __first >= __last;
   // Go through the remaining elements.  Swap pairs of elements (one to the
   // right of the pivot and the other to left of the pivot) that are not on the
   // correct side of the pivot.
   while (__first < __last) {
     _Ops::iter_swap(__first, __last);
     do {
       ++__first;
-      _LIBCPP_ASSERT(__first != __end, "Would read out of bounds, is your comparator a valid strict-weak ordering?");
+      _LIBCPP_ASSERT(__first != __end, "Would read out of bounds, does your comparator satisfy the strict-weak ordering requirement?");
     } while (__comp(*__first, __pivot));
     do {
-      _LIBCPP_ASSERT(__last != __begin, "Would read out of bounds, is your comparator a valid strict-weak ordering?");
+      _LIBCPP_ASSERT(__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);
   if (__begin != __pivot_pos) {
     *__begin = _Ops::__iter_move(__pivot_pos);
   }
   *__pivot_pos = std::move(__pivot);
   return std::make_pair(__pivot_pos, __already_partitioned);
 }
 
 // Similar to the above function.  Elements equivalent to the pivot are put to
 // the left of the pivot.  Returns the iterator to the pivot element.
 template <class _AlgPolicy, class _RandomAccessIterator, class _Compare>
 _LIBCPP_HIDE_FROM_ABI _RandomAccessIterator
 __partition_with_equals_on_left(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) {
   using _Ops = _IterOps<_AlgPolicy>;
   typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
   typedef typename std::iterator_traits<_RandomAccessIterator>::value_type value_type;
-  const _RandomAccessIterator __begin = __first;            // used for bounds checking, those are not moved around
+  // 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.
     do {
       ++__first;
-      _LIBCPP_ASSERT(__first != __end, "Would read out of bounds, is your comparator a valid strict-weak ordering?");
+      _LIBCPP_ASSERT(__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)) {
     }
   }
 
   if (__first < __last) {
     // It will be always guarded because __introsort will do the
     // median-of-three before calling this.
     do {
-      _LIBCPP_ASSERT(__last != __begin, "Would read out of bounds, is your comparator a valid strict-weak ordering?");
+      _LIBCPP_ASSERT(__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);
     do {
       ++__first;
-      _LIBCPP_ASSERT(__first != __end, "Would read out of bounds, is your comparator a valid strict-weak ordering?");
+      _LIBCPP_ASSERT(__first != __end, "Would read out of bounds, does your comparator satisfy the strict-weak ordering requirement?");
     } while (!__comp(__pivot, *__first));
     do {
-      _LIBCPP_ASSERT(__last != __begin, "Would read out of bounds, is your comparator a valid strict-weak ordering?");
+      _LIBCPP_ASSERT(__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) {
     *__begin = _Ops::__iter_move(__pivot_pos);
   }
   *__pivot_pos = std::move(__pivot);

libcxx/test/libcxx/algorithms/alg.sorting/assert.sort.invalid_comparator.pass.cpp

 //
 //    comp(a, b) implies that !comp(b, a)
 //
 // In other words,
 //
 //    a < b implies that !(b < a)
 //
 // If this is not satisfied, we have seen issues in the past where the std::sort implementation
-// would proceed to do OOB reads.
+// would proceed to do OOB reads (rdar://106897934).
 
 // When the debug mode is enabled, this test fails because we actually catch that the comparator
 // is not a strict-weak ordering before we catch that we'd dereference out-of-bounds inside std::sort,
 // which leads to different errors than the ones tested below.
 // XFAIL: libcpp-has-debug-mode
 
 #include <algorithm>
 #include <cassert>
 #include <cstddef>
 #include <map>
 #include <memory>
 #include <ranges>
 #include <set>
 #include <string>
 #include <vector>
 
+#include "bad_comparator_values.h"
 #include "check_assertion.h"
 
-std::string DATA =
-#   include "bad_comparator_values.dat"
-;
-
 int main(int, char**) {
     std::map<std::size_t, std::map<std::size_t, bool>> comparison_results; // terrible for performance, but really convenient
     for (auto line : std::views::split(DATA, '\n') | std::views::filter([](auto const& line) { return !line.empty(); })) {
         auto values = std::views::split(line, ' ');
         auto it = values.begin();
         std::size_t left = std::stol(std::string((*it).data(), (*it).size()));
         it = std::next(it);
         std::size_t right = std::stol(std::string((*it).data(), (*it).size()));

libcxx/test/libcxx/algorithms/alg.sorting/bad_comparator_values.h

-R"(
+//===----------------------------------------------------------------------===//
+//
+// 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 TEST_LIBCXX_ALGORITHMS_ALG_SORTING_BAD_COMPARATOR_VALUES_H
+#define TEST_LIBCXX_ALGORITHMS_ALG_SORTING_BAD_COMPARATOR_VALUES_H
+
+#include <string_view>
+
+inline constexpr std::string_view DATA = R"(
 0 0 0
 0 1 1
 0 2 1
 0 3 1
 0 4 1
 0 5 1
 0 6 1
 0 7 1

 58 51 1
 58 52 1
 58 53 1
 58 54 1
 58 55 1
 58 56 1
 58 57 1
 58 58 0
-)"
+)";
+
+#endif // TEST_LIBCXX_ALGORITHMS_ALG_SORTING_BAD_COMPARATOR_VALUES_H