diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt --- a/libcxx/include/CMakeLists.txt +++ b/libcxx/include/CMakeLists.txt @@ -304,6 +304,7 @@ __coroutine/trivial_awaitables.h __debug __debug_utils/randomize_range.h + __debug_utils/strict_weak_ordering_check.h __exception/exception.h __exception/exception_ptr.h __exception/nested_exception.h diff --git a/libcxx/include/__algorithm/sort.h b/libcxx/include/__algorithm/sort.h --- a/libcxx/include/__algorithm/sort.h +++ b/libcxx/include/__algorithm/sort.h @@ -23,6 +23,7 @@ #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> @@ -920,6 +921,7 @@ } else { std::__sort_dispatch<_AlgPolicy>(std::__unwrap_iter(__first), std::__unwrap_iter(__last), __comp); } + std::__check_strict_weak_ordering_sorted<_AlgPolicy>(std::__unwrap_iter(__first), std::__unwrap_iter(__last), __comp); } template diff --git a/libcxx/include/__algorithm/sort_heap.h b/libcxx/include/__algorithm/sort_heap.h --- a/libcxx/include/__algorithm/sort_heap.h +++ b/libcxx/include/__algorithm/sort_heap.h @@ -14,6 +14,7 @@ #include <__algorithm/iterator_operations.h> #include <__algorithm/pop_heap.h> #include <__config> +#include <__debug_utils/strict_weak_ordering_check.h> #include <__iterator/iterator_traits.h> #include <__type_traits/is_copy_assignable.h> #include <__type_traits/is_copy_constructible.h> @@ -28,11 +29,13 @@ template inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 void __sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare&& __comp) { + _RandomAccessIterator __saved_last = __last; __comp_ref_type<_Compare> __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<_AlgPolicy>(__first, __last, __comp_ref, __n); + std::__check_strict_weak_ordering_sorted<_ClassicAlgPolicy>(__first, __saved_last, __comp_ref); } template diff --git a/libcxx/include/__algorithm/stable_sort.h b/libcxx/include/__algorithm/stable_sort.h --- a/libcxx/include/__algorithm/stable_sort.h +++ b/libcxx/include/__algorithm/stable_sort.h @@ -15,6 +15,7 @@ #include <__algorithm/iterator_operations.h> #include <__algorithm/sort.h> #include <__config> +#include <__debug_utils/strict_weak_ordering_check.h> #include <__iterator/iterator_traits.h> #include <__memory/destruct_n.h> #include <__memory/temporary_buffer.h> @@ -259,6 +260,7 @@ } std::__stable_sort<_AlgPolicy, __comp_ref_type<_Compare> >(__first, __last, __comp, __len, __buf.first, __buf.second); + std::__check_strict_weak_ordering_sorted<_ClassicAlgPolicy>(__first, __last, __comp); } template diff --git a/libcxx/include/__debug b/libcxx/include/__debug --- a/libcxx/include/__debug +++ b/libcxx/include/__debug @@ -23,6 +23,10 @@ # define _LIBCPP_DEBUG_RANDOMIZE_UNSPECIFIED_STABILITY #endif +#if defined(_LIBCPP_ENABLE_DEBUG_MODE) && !defined(_LIBCPP_DEBUG_STRICT_WEAK_ORDERING_CHECK) +# define _LIBCPP_DEBUG_STRICT_WEAK_ORDERING_CHECK +#endif + #if defined(_LIBCPP_ENABLE_DEBUG_MODE) && !defined(_LIBCPP_DEBUG_ITERATOR_BOUNDS_CHECKING) # define _LIBCPP_DEBUG_ITERATOR_BOUNDS_CHECKING #endif diff --git a/libcxx/include/__debug_utils/strict_weak_ordering_check.h b/libcxx/include/__debug_utils/strict_weak_ordering_check.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__debug_utils/strict_weak_ordering_check.h @@ -0,0 +1,73 @@ +//===----------------------------------------------------------------------===// +// +// 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___LIBCXX_DEBUG_STRICT_WEAK_ORDERING_CHECK +#define _LIBCPP___LIBCXX_DEBUG_STRICT_WEAK_ORDERING_CHECK + +#include <__config> + +#ifdef _LIBCPP_DEBUG_STRICT_WEAK_ORDERING_CHECK +# include <__algorithm/comp_ref_type.h> +# include <__algorithm/is_sorted.h> +# include <__assert> +# include <__iterator/iterator_traits.h> +# include <__type_traits/is_constant_evaluated.h> +#endif + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +_LIBCPP_BEGIN_NAMESPACE_STD + +template +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 +void __check_strict_weak_ordering_sorted(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp& __comp) { +#ifdef _LIBCPP_DEBUG_STRICT_WEAK_ORDERING_CHECK + typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; + using _Comp_ref = __comp_ref_type<_Comp>; + if (!__libcpp_is_constant_evaluated()) { + // Check if the range is actually sorted. + _LIBCPP_ASSERT((std::is_sorted<_RandomAccessIterator, _Comp_ref>(__first, __last, _Comp_ref(__comp))), "The range is not sorted after the sort, your comparator is not a valid strict-weak ordering"); + // Limit the number of elements we need to check. + difference_type __size = __last - __first > difference_type(100) ? difference_type(100) : __last - __first; + difference_type __p = 0; + while (__p < __size) { + difference_type __q = __p + difference_type(1); + // Find first element that is greater than *(__first+__p). + while (__q < __size && !__comp(*(__first + __p), *(__first + __q))) { + ++__q; + } + // Check that the elements from __p to __q are equal between each other. + for (difference_type __b = __p; __b < __q; ++__b) { + for (difference_type __a = __p; __a <= __b; ++__a) { + _LIBCPP_ASSERT(!__comp(*(__first + __a), *(__first + __b)), "Your comparator is not a valid strict-weak ordering"); + _LIBCPP_ASSERT(!__comp(*(__first + __b), *(__first + __a)), "Your comparator is not a valid strict-weak ordering"); + } + } + // Check that elements between __p and __q are less than between __q and __size. + for (difference_type __a = __p; __a < __q; ++__a) { + for (difference_type __b = __q; __b < __size; ++__b) { + _LIBCPP_ASSERT(__comp(*(__first + __a), *(__first + __b)), "Your comparator is not a valid strict-weak ordering"); + _LIBCPP_ASSERT(!__comp(*(__first + __b), *(__first + __a)), "Your comparator is not a valid strict-weak ordering"); + } + } + // Skip these equal elements. + __p = __q; + } + } +#else + (void)__first; + (void)__last; + (void)__comp; +#endif +} + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP___LIBCXX_DEBUG_STRICT_WEAK_ORDERING_CHECK diff --git a/libcxx/include/module.modulemap.in b/libcxx/include/module.modulemap.in --- a/libcxx/include/module.modulemap.in +++ b/libcxx/include/module.modulemap.in @@ -1115,6 +1115,7 @@ module __debug_utils { module randomize_range { private header "__debug_utils/randomize_range.h" } + module strict_weak_ordering_check { private header "__debug_utils/strict_weak_ordering_check.h" } } module limits { 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 --- 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 @@ -11,23 +11,26 @@ // REQUIRES: has-unix-headers // UNSUPPORTED: c++03, c++11, c++14, c++17 // XFAIL: availability-verbose_abort-missing -// ADDITIONAL_COMPILE_FLAGS: -D_LIBCPP_ENABLE_ASSERTIONS=1 +// ADDITIONAL_COMPILE_FLAGS: -D_LIBCPP_ENABLE_ASSERTIONS=1 -D_LIBCPP_DEBUG_STRICT_WEAK_ORDERING_CHECK // This test uses a specific combination of an invalid comparator and sequence of values to -// ensure that our sorting functions do not go out-of-bounds in that case. Instead, we should -// fail loud with an assertion. The specific issue we're looking for here is when the comparator -// does not satisfy the following property: +// ensure that our sorting functions do not go out-of-bounds and satisfy strict weak ordering in that case. +// Instead, we should fail loud with an assertion. The specific issue we're looking for here is when the comparator +// does not satisfy the strict weak ordering: // -// comp(a, b) implies that !comp(b, a) -// -// In other words, -// -// a < b implies that !(b < a) +// Irreflexivity: comp(a, a) is false +// Antisymmetry: comp(a, b) implies that !comp(b, a) +// Transitivity: comp(a, b), comp(b, c) imply comp(a, c) +// Transitivity of equivalence: !comp(a, b), !comp(b, a), !comp(b, c), !comp(c, b) imply !comp(a, c), !comp(c, a) // // If this is not satisfied, we have seen issues in the past where the std::sort implementation // would proceed to do OOB reads. +// Other algorithms like std::stable_sort, std::sort_heap do not go out of bounds but can produce +// incorrect results, we also want to assert on that. +// Sometimes std::sort does not go out of bounds as well, for example, right now if transitivity +// of equivalence is not met, std::sort can only produce incorrect result but would not fail. -// When the debug mode is enabled, this test fails because we actually catch that the comparator +// When the debug mode is enabled, this test fails because we actually catch on the fly 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 @@ -35,9 +38,11 @@ #include #include #include +#include #include #include #include +#include #include #include #include @@ -48,7 +53,7 @@ # include "bad_comparator_values.dat" ; -int main(int, char**) { +void check_oob_sort_read() { 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(); })) { auto values = std::views::split(line, ' '); @@ -93,20 +98,27 @@ std::vector copy; for (auto const& e : elements) copy.push_back(e.get()); - std::stable_sort(copy.begin(), copy.end(), checked_predicate); // doesn't go OOB even with invalid comparator + TEST_LIBCPP_ASSERT_FAILURE(std::stable_sort(copy.begin(), copy.end(), checked_predicate), "not a valid strict-weak ordering"); + } + { + std::vector copy; + for (auto const& e : elements) + copy.push_back(e.get()); + std::make_heap(copy.begin(), copy.end(), checked_predicate); // doesn't go OOB even with invalid comparator + TEST_LIBCPP_ASSERT_FAILURE(std::sort_heap(copy.begin(), copy.end(), checked_predicate), "not a valid strict-weak ordering"); } { std::vector copy; for (auto const& e : elements) copy.push_back(e.get()); - std::partial_sort(copy.begin(), copy.begin(), copy.end(), checked_predicate); // doesn't go OOB even with invalid comparator + TEST_LIBCPP_ASSERT_FAILURE(std::partial_sort(copy.begin(), copy.end(), copy.end(), checked_predicate), "not a valid strict-weak ordering"); } { std::vector copy; for (auto const& e : elements) copy.push_back(e.get()); std::vector results(copy.size(), nullptr); - std::partial_sort_copy(copy.begin(), copy.end(), results.begin(), results.end(), checked_predicate); // doesn't go OOB even with invalid comparator + TEST_LIBCPP_ASSERT_FAILURE(std::partial_sort_copy(copy.begin(), copy.end(), results.begin(), results.end(), checked_predicate), "not a valid strict-weak ordering"); } { std::vector copy; @@ -126,20 +138,27 @@ std::vector copy; for (auto const& e : elements) copy.push_back(e.get()); - std::ranges::stable_sort(copy, checked_predicate); // doesn't go OOB even with invalid comparator + TEST_LIBCPP_ASSERT_FAILURE(std::ranges::stable_sort(copy, checked_predicate), "not a valid strict-weak ordering"); } { std::vector copy; for (auto const& e : elements) copy.push_back(e.get()); - std::ranges::partial_sort(copy, copy.begin(), checked_predicate); // doesn't go OOB even with invalid comparator + std::ranges::make_heap(copy, checked_predicate); // doesn't go OOB even with invalid comparator + TEST_LIBCPP_ASSERT_FAILURE(std::ranges::sort_heap(copy, checked_predicate), "not a valid strict-weak ordering"); + } + { + std::vector copy; + for (auto const& e : elements) + copy.push_back(e.get()); + TEST_LIBCPP_ASSERT_FAILURE(std::ranges::partial_sort(copy, copy.end(), checked_predicate), "not a valid strict-weak ordering"); } { std::vector copy; for (auto const& e : elements) copy.push_back(e.get()); std::vector results(copy.size(), nullptr); - std::ranges::partial_sort_copy(copy, results, checked_predicate); // doesn't go OOB even with invalid comparator + TEST_LIBCPP_ASSERT_FAILURE(std::ranges::partial_sort_copy(copy, results, checked_predicate), "not a valid strict-weak ordering"); } { std::vector copy; @@ -147,6 +166,54 @@ copy.push_back(e.get()); std::ranges::nth_element(copy, copy.end(), checked_predicate); // doesn't go OOB even with invalid comparator } +} + +// Nans in floats do not satisfy strict weak ordering by breaking transitivity of equivalence. +std::vector generate_float_data() { + std::vector floats(50); + for (int i = 0; i < 50; ++i) { + floats[i] = static_cast(i); + } + floats.push_back(std::numeric_limits::quiet_NaN()); + std::shuffle(floats.begin(), floats.end(), std::default_random_engine()); + return floats; +} + +void check_nan_floats() { + auto floats = generate_float_data(); + TEST_LIBCPP_ASSERT_FAILURE(std::sort(floats.begin(), floats.end()), "not a valid strict-weak ordering"); + floats = generate_float_data(); + TEST_LIBCPP_ASSERT_FAILURE(std::stable_sort(floats.begin(), floats.end()), "not a valid strict-weak ordering"); + floats = generate_float_data(); + std::make_heap(floats.begin(), floats.end()); + TEST_LIBCPP_ASSERT_FAILURE(std::sort_heap(floats.begin(), floats.end()), "not a valid strict-weak ordering"); + TEST_LIBCPP_ASSERT_FAILURE(std::ranges::sort(generate_float_data()), "not a valid strict-weak ordering"); + TEST_LIBCPP_ASSERT_FAILURE(std::ranges::stable_sort(generate_float_data()), "not a valid strict-weak ordering"); + floats = generate_float_data(); + std::ranges::make_heap(floats); + TEST_LIBCPP_ASSERT_FAILURE(std::ranges::sort_heap(floats), "not a valid strict-weak ordering"); +} + +void check_irreflexive() { + std::vector v(1); + TEST_LIBCPP_ASSERT_FAILURE(std::sort(v.begin(), v.end(), std::greater_equal()), "not a valid strict-weak ordering"); + TEST_LIBCPP_ASSERT_FAILURE(std::stable_sort(v.begin(), v.end(), std::greater_equal()), "not a valid strict-weak ordering"); + std::make_heap(v.begin(), v.end(), std::greater_equal()); + TEST_LIBCPP_ASSERT_FAILURE(std::sort_heap(v.begin(), v.end(), std::greater_equal()), "not a valid strict-weak ordering"); + TEST_LIBCPP_ASSERT_FAILURE(std::ranges::sort(v, std::greater_equal()), "not a valid strict-weak ordering"); + TEST_LIBCPP_ASSERT_FAILURE(std::ranges::stable_sort(v, std::greater_equal()), "not a valid strict-weak ordering"); + std::ranges::make_heap(v, std::greater_equal()); + TEST_LIBCPP_ASSERT_FAILURE(std::ranges::sort_heap(v, std::greater_equal()), "not a valid strict-weak ordering"); +} + +int main(int, char**) { + + check_oob_sort_read(); + + check_nan_floats(); + + check_irreflexive(); return 0; } + diff --git a/libcxx/test/libcxx/private_headers.verify.cpp b/libcxx/test/libcxx/private_headers.verify.cpp --- a/libcxx/test/libcxx/private_headers.verify.cpp +++ b/libcxx/test/libcxx/private_headers.verify.cpp @@ -342,6 +342,7 @@ #include <__coroutine/noop_coroutine_handle.h> // expected-error@*:* {{use of private header from outside its module: '__coroutine/noop_coroutine_handle.h'}} #include <__coroutine/trivial_awaitables.h> // expected-error@*:* {{use of private header from outside its module: '__coroutine/trivial_awaitables.h'}} #include <__debug_utils/randomize_range.h> // expected-error@*:* {{use of private header from outside its module: '__debug_utils/randomize_range.h'}} +#include <__debug_utils/strict_weak_ordering_check.h> // expected-error@*:* {{use of private header from outside its module: '__debug_utils/strict_weak_ordering_check.h'}} #include <__exception/exception.h> // expected-error@*:* {{use of private header from outside its module: '__exception/exception.h'}} #include <__exception/exception_ptr.h> // expected-error@*:* {{use of private header from outside its module: '__exception/exception_ptr.h'}} #include <__exception/nested_exception.h> // expected-error@*:* {{use of private header from outside its module: '__exception/nested_exception.h'}} diff --git a/libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/sort.heap/complexity.pass.cpp b/libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/sort.heap/complexity.pass.cpp --- a/libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/sort.heap/complexity.pass.cpp +++ b/libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/sort.heap/complexity.pass.cpp @@ -69,7 +69,6 @@ LIBCPP_ASSERT(stats.compared <= n * logn); #endif LIBCPP_ASSERT(std::is_sorted(first, last)); - LIBCPP_ASSERT(stats.compared <= 2 * n * logn); } return 0; } diff --git a/libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/sort.heap/ranges_sort_heap.pass.cpp b/libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/sort.heap/ranges_sort_heap.pass.cpp --- a/libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/sort.heap/ranges_sort_heap.pass.cpp +++ b/libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/sort.heap/ranges_sort_heap.pass.cpp @@ -207,7 +207,7 @@ { // `std::ranges::dangling` is returned. [[maybe_unused]] std::same_as decltype(auto) result = - std::ranges::sort_heap(std::array{2, 1, 3}); + std::ranges::sort_heap(std::array{3, 1, 2}); } return true; @@ -263,7 +263,6 @@ LIBCPP_ASSERT(stats.compared <= n * logn); #endif LIBCPP_ASSERT(std::is_sorted(first, last, &MyInt::Comp)); - LIBCPP_ASSERT(stats.compared <= 2 * n * logn); } } diff --git a/libcxx/test/std/algorithms/ranges_robust_against_dangling.pass.cpp b/libcxx/test/std/algorithms/ranges_robust_against_dangling.pass.cpp --- a/libcxx/test/std/algorithms/ranges_robust_against_dangling.pass.cpp +++ b/libcxx/test/std/algorithms/ranges_robust_against_dangling.pass.cpp @@ -201,6 +201,7 @@ dangling_1st(std::ranges::make_heap, in); dangling_1st(std::ranges::push_heap, in); dangling_1st(std::ranges::pop_heap, in); + dangling_1st(std::ranges::make_heap, in); dangling_1st(std::ranges::sort_heap, in); dangling_1st>(std::ranges::prev_permutation, in); dangling_1st>(std::ranges::next_permutation, in); diff --git a/libcxx/test/std/algorithms/robust_against_proxy_iterators_lifetime_bugs.pass.cpp b/libcxx/test/std/algorithms/robust_against_proxy_iterators_lifetime_bugs.pass.cpp --- a/libcxx/test/std/algorithms/robust_against_proxy_iterators_lifetime_bugs.pass.cpp +++ b/libcxx/test/std/algorithms/robust_against_proxy_iterators_lifetime_bugs.pass.cpp @@ -145,7 +145,7 @@ assert(lifetime_cache.contains(this) && lifetime_cache.contains(&rhs)); assert(!rhs.moved_from_); - v_ = rhs.v_; + *v_ = *rhs.v_; moved_from_ = false; return *this; @@ -157,7 +157,7 @@ assert(!rhs.moved_from_); rhs.moved_from_ = true; - v_ = rhs.v_; + *v_ = *rhs.v_; moved_from_ = false; return *this; diff --git a/libcxx/utils/data/ignore_format.txt b/libcxx/utils/data/ignore_format.txt --- a/libcxx/utils/data/ignore_format.txt +++ b/libcxx/utils/data/ignore_format.txt @@ -305,6 +305,7 @@ libcxx/include/cuchar libcxx/include/__debug libcxx/include/__debug_utils/randomize_range.h +libcxx/include/__debug_utils/strict_weak_ordering_check.h libcxx/include/deque libcxx/include/errno.h libcxx/include/expected diff --git a/llvm/utils/gn/secondary/libcxx/include/BUILD.gn b/llvm/utils/gn/secondary/libcxx/include/BUILD.gn --- a/llvm/utils/gn/secondary/libcxx/include/BUILD.gn +++ b/llvm/utils/gn/secondary/libcxx/include/BUILD.gn @@ -378,6 +378,7 @@ "__coroutine/trivial_awaitables.h", "__debug", "__debug_utils/randomize_range.h", + "__debug_utils/strict_weak_ordering_check.h", "__exception/exception.h", "__exception/exception_ptr.h", "__exception/nested_exception.h",