From 35f9fd64350e5fffba727a9cb1df336ccb39d3be Mon Sep 17 00:00:00 2001 From: Louis Dionne Date: Wed, 17 May 2023 07:17:53 -0700 Subject: [PATCH] [libc++] Avoid dereferencing a const iterator in std::sort 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. Differential Revision: https://reviews.llvm.org/D150779 --- libcxx/include/__algorithm/sort.h | 25 +++++++++++----------- .../assert.sort.invalid_comparator.pass.cpp | 7 ++---- ...mparator_values.dat => bad_comparator_values.h} | 19 ++++++++++++++-- 3 files changed, 32 insertions(+), 19 deletions(-) rename libcxx/test/libcxx/algorithms/alg.sorting/{bad_comparator_values.dat => bad_comparator_values.h} (97%) diff --git a/libcxx/include/__algorithm/sort.h b/libcxx/include/__algorithm/sort.h index 3583c44..bcc1e97 100644 --- a/libcxx/include/__algorithm/sort.h +++ b/libcxx/include/__algorithm/sort.h @@ -295,7 +295,7 @@ __insertion_sort_unguarded(_RandomAccessIterator const __first, _RandomAccessIte 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); } @@ -507,7 +507,7 @@ __bitset_partition(_RandomAccessIterator __first, _RandomAccessIterator __last, // 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)) { @@ -518,7 +518,7 @@ __bitset_partition(_RandomAccessIterator __first, _RandomAccessIterator __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)); } @@ -593,7 +593,7 @@ __partition_with_equals_on_right(_RandomAccessIterator __first, _RandomAccessIte // 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. @@ -603,7 +603,7 @@ __partition_with_equals_on_right(_RandomAccessIterator __first, _RandomAccessIte } 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)); } @@ -619,10 +619,10 @@ __partition_with_equals_on_right(_RandomAccessIterator __first, _RandomAccessIte _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)); } @@ -643,14 +643,15 @@ __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; - 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)) { @@ -661,7 +662,7 @@ __partition_with_equals_on_left(_RandomAccessIterator __first, _RandomAccessIter // 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)); } @@ -669,10 +670,10 @@ __partition_with_equals_on_left(_RandomAccessIterator __first, _RandomAccessIter _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)); } diff --git a/libcxx/test/libcxx/algorithms/alg.sorting/assert.sort.invalid_comparator.pass.cpp b/libcxx/test/libcxx/algorithms/alg.sorting/assert.sort.invalid_comparator.pass.cpp index 570a6e1..a175890 100644 --- a/libcxx/test/libcxx/algorithms/alg.sorting/assert.sort.invalid_comparator.pass.cpp +++ b/libcxx/test/libcxx/algorithms/alg.sorting/assert.sort.invalid_comparator.pass.cpp @@ -25,7 +25,7 @@ // 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, @@ -42,12 +42,9 @@ #include #include +#include "bad_comparator_values.h" #include "check_assertion.h" -std::string DATA = -# include "bad_comparator_values.dat" -; - int main(int, char**) { std::map> 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(); })) { diff --git a/libcxx/test/libcxx/algorithms/alg.sorting/bad_comparator_values.dat b/libcxx/test/libcxx/algorithms/alg.sorting/bad_comparator_values.h similarity index 97% rename from libcxx/test/libcxx/algorithms/alg.sorting/bad_comparator_values.dat rename to libcxx/test/libcxx/algorithms/alg.sorting/bad_comparator_values.h index 05a4b21..19ea023 100644 --- a/libcxx/test/libcxx/algorithms/alg.sorting/bad_comparator_values.dat +++ b/libcxx/test/libcxx/algorithms/alg.sorting/bad_comparator_values.h @@ -1,4 +1,17 @@ -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 + +inline constexpr std::string_view DATA = R"( 0 0 0 0 1 1 0 2 1 @@ -3480,4 +3493,6 @@ R"( 58 56 1 58 57 1 58 58 0 -)" +)"; + +#endif // TEST_LIBCXX_ALGORITHMS_ALG_SORTING_BAD_COMPARATOR_VALUES_H -- 2.7.4