[libcxx] Add strict weak ordering checks to sorting algorithms

[danlark]

Summary

This is the implementation of the first proposal of strict weak ordering checks described in https://discourse.llvm.org/t/rfc-strict-weak-ordering-checks-in-the-debug-libc/70217

This targets the most vulnerable algorithms like std::sort

[danlark]

Fix includes

[danlark]

Fix incorrect tests and ADL lookups

[danlark]

Merge all changes I had about includes and tests

[danlark]

Follow the standard library lint

[philnik]

libcxx/include/__debug_utils/strict_weak_ordering_check.h

15

IMO we shouldn't include stuff based on whether we are in debug mode or not.

29

If you never use the _AlgPolicy there is no point in passing it.

33

50

Could we print the indices/types if they can be printed instead of just saying "you are wrong"?

libcxx/include/module.modulemap.in

1117–1119

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

172

Could you use a struct which violates the condition instead? floating-point types specifically are almost trivial to diagnose at compile-time. A struct which uses a float should be hard enough to diagnose (at least from the library).

libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/sort.heap/complexity.pass.cpp

72

Could this be extended by a constant instead?

libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/sort.heap/ranges_sort_heap.pass.cpp

210

Why is this changed?

266

Could this be extended by a constant instead?

libcxx/utils/data/ignore_format.txt

308

Please clang-format the header.

[danlark]

Address comments

libcxx/include/__debug_utils/strict_weak_ordering_check.h

15

This is consistent with __debug_utils/randomize_range. I believe the intention is not to expose more headers than needed for compile times

50

This information might be incorrect. As said in the RFC, quadratic algorithm can show if there is a problem, not the triple that violates the condition

In this case we figured out a pair in the range that we think consist of equal elements to be comparable, say, it can be with the epsilon float sorting (2 elements are considered equal if their diff is no more than eps)

eps/2, eps, 2eps

We will detect a pair eps/2, 2eps and we will show it to the user. It does not explain much on what happened.

libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/sort.heap/ranges_sort_heap.pass.cpp

210

Because 2, 1, 3 is not a max heap, calling sort_heap is incorrect in this case

[danlark]

Remove arg policy

[philnik]

libcxx/include/__debug_utils/strict_weak_ordering_check.h

15

I can't remember why I did it that way, but the compile times for these headers are mot likely not relevant. This is also not the style in the rest of the code base.

libcxx/utils/data/ignore_format.txt

308

When the header is formatted this change shouldn't be necessary.

[danlark]

Fix comments

[danlark]

Ping

[danlark]

Ping

[philnik]

LGTM

[danlark]

I don't have commit rights, can you help me submit the change?

Danila Kutenin
[e-mail]

[danlark]

Ping

[Mordante]

In D150264#4380575, @danlark wrote:

I don't have commit rights, can you help me submit the change?

Danila Kutenin
[e-mail]

I tried to land this patch on your behalf, but there are some merge conflicts. Can you rebase the patch on main?

libcxx/test/libcxx/private_headers.verify.cpp

345

This file is removed upstream, can you revert this hunk before rebasing?

llvm/utils/gn/secondary/libcxx/include/BUILD.gn

381

FYI this is done automatically.

[danlark]

Rebase to head

[danlark]

In D150264#4392972, @Mordante wrote:

In D150264#4380575, @danlark wrote:

I don't have commit rights, can you help me submit the change?

Danila Kutenin
[e-mail]

I tried to land this patch on your behalf, but there are some merge conflicts. Can you rebase the patch on main?

All done, thanks!

[Mordante]

In D150264#4393925, @danlark wrote:

In D150264#4392972, @Mordante wrote:

In D150264#4380575, @danlark wrote:

I don't have commit rights, can you help me submit the change?

Danila Kutenin
[e-mail]

I tried to land this patch on your behalf, but there are some merge conflicts. Can you rebase the patch on main?

All done, thanks!

Thanks! I'll wait for the current CI run to finish and land the patch when it's green.

[Mordante]

The build failure is a test that is a bit flaky. Landed on your behalf.

[ldionne]

libcxx/include/__algorithm/sort.h

703

Sorry for being so late to the party, but I think there's a problem here. We should decide whether we want to use these added facilities or __comp_ref_type to catch these kinds of issues. Right now, we have a weird situation where both can potentially be used at the same time. This means that we have the following mechanisms in place and enabled independently:

1. The assertions I added that ensure that we would not dereference iterators out-of-bounds inside std::sort. Those are arguably hardening assertions, not only debug mode assertions.
2. The existing __comp_ref_type mechanism which aims to catch invalid strict weak orders at the predicate level.
3. The new mechanism introduced by this patch.

Is there a reason why we'd want to have these three severely overlapping mechanisms (and especially within the same algorithm)?

[ldionne]

libcxx/include/__algorithm/sort.h

703

CC @var-const

[philnik]

libcxx/include/__algorithm/sort.h

703

I think they are complementary. All of them have their strengths and weaknesses.

• The assertions are relatively light weight, but miss a lot of the strict weak ordering issues. As you said yourself, these can be considered hardening asserts.
• The __comp_ref_type catches a lot more issues, but can't check across multiple pairs.
• This new check is very expensive, making it only suitable for a subrange and only in debug mode, but it catches a lot of the strict weak ordering issues.

I think the assertions aren't useful to combine with __comp_ref_type and the new checks, but also don't hurt. Having both for larger ranges makes sense, since the __comp_ref_type can check the whole range.

[ldionne]

libcxx/include/__algorithm/sort.h

703

Ok, that's something I could go with. However, in that case we need to reinstate the invalid_comparator.pass.cpp test to do what it did before. It was a hardening test that ensures that we don't go OOB inside these algorithms when the comparator is wrong. The goal was to ensure that we don't do that bad thing even when the debug mode is disabled. After this patch, however, that test became a test for the newly introduced strict weak order checks, which only make sense in debug mode.

@danlark Do you think you could pick that up?

[danlark]

libcxx/include/__algorithm/sort.h

703

I think we still check for what you ask in the comment:

Line 87:

TEST_LIBCPP_ASSERT_FAILURE(std::sort(copy.begin(), copy.end(), checked_predicate), "Would read out of bounds");

The test checks that out of bound reads check fires first. Then if it is not able to identify anything, the strict weak ordering check asserts.

libcxx/include/CMakeLists.txt

set(files
   __condition_variable/condition_variable.h
   __config
   __coroutine/coroutine_handle.h
   __coroutine/coroutine_traits.h
   __coroutine/noop_coroutine_handle.h
   __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
   __exception/operations.h
   __exception/terminate.h
   __expected/bad_expected_access.h
   __expected/expected.h
   __expected/unexpect.h

libcxx/include/__algorithm/sort.h

 #include <__algorithm/unwrap_iter.h>
 #include <__assert>
 #include <__bit/blsr.h>
 #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 <__type_traits/conditional.h>
 #include <__type_traits/disjunction.h>
 #include <__type_traits/is_arithmetic.h>
 #include <__utility/move.h>
 #include <__utility/pair.h>

 template <class _AlgPolicy, class _Compare, class _RandomAccessIterator, bool _UseBitSetPartition>
 void __introsort(_RandomAccessIterator __first,
                  _RandomAccessIterator __last,
                  _Compare __comp,
                  typename iterator_traits<_RandomAccessIterator>::difference_type __depth,
                  bool __leftmost = true) {
   using _Ops = _IterOps<_AlgPolicy>;
   typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
   using _Comp_ref = __comp_ref_type<_Compare>;
   // Upper bound for using insertion sort for sorting.
   _LIBCPP_CONSTEXPR difference_type __limit = 24;
   // Lower bound for using Tuckey's ninther technique for median computation.
   _LIBCPP_CONSTEXPR difference_type __ninther_threshold = 128;
   while (true) {
     difference_type __len = __last - __first;
     switch (__len) {
     case 0:
void __sort_impl(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp& __comp) {
   std::__debug_randomize_range<_AlgPolicy>(__first, __last);
 
   if (__libcpp_is_constant_evaluated()) {
     std::__partial_sort<_AlgPolicy>(
         std::__unwrap_iter(__first), std::__unwrap_iter(__last), std::__unwrap_iter(__last), __comp);
   } 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 <class _RandomAccessIterator, class _Comp>
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
 void sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp __comp) {
   std::__sort_impl<_ClassicAlgPolicy>(std::move(__first), std::move(__last), __comp);
 }
 

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 <__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>
 #include <__utility/move.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 template <class _AlgPolicy, class _Compare, class _RandomAccessIterator>
 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 <class _RandomAccessIterator, class _Compare>
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
 void sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) {
   static_assert(std::is_copy_constructible<_RandomAccessIterator>::value, "Iterators must be copy constructible.");
   static_assert(std::is_copy_assignable<_RandomAccessIterator>::value, "Iterators must be copy assignable.");
 

libcxx/include/__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 <__debug_utils/strict_weak_ordering_check.h>
 #include <__iterator/iterator_traits.h>
 #include <__memory/destruct_n.h>
 #include <__memory/temporary_buffer.h>
 #include <__memory/unique_ptr.h>
 #include <__type_traits/is_trivially_copy_assignable.h>
 #include <__utility/move.h>
 #include <__utility/pair.h>
 #include <new>

 // 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);
   }
 
   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 <class _RandomAccessIterator, class _Compare>
 inline _LIBCPP_HIDE_FROM_ABI
 void stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) {
   std::__stable_sort_impl<_ClassicAlgPolicy>(std::move(__first), std::move(__last), __comp);
 }
 

libcxx/include/__debug

 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 #if defined(_LIBCPP_ENABLE_DEBUG_MODE) && !defined(_LIBCPP_CXX03_LANG) && !defined(_LIBCPP_DEBUG_RANDOMIZE_UNSPECIFIED_STABILITY)
 # 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
 
 #ifdef _LIBCPP_ENABLE_DEBUG_MODE
 #   define _LIBCPP_DEBUG_ASSERT(x, m) _LIBCPP_ASSERT(::std::__libcpp_is_constant_evaluated() || (x), m)
 #else
 #   define _LIBCPP_DEBUG_ASSERT(x, m) ((void)0)

libcxx/include/__debug_utils/strict_weak_ordering_check.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___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 <class _AlgPolicy, class _RandomAccessIterator, class _Comp>
+_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

libcxx/include/module.modulemap.in

   }
   module latch {
     @requires_LIBCXX_ENABLE_THREADS@
     header "latch"
     export *
   }
 
   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 {
     header "limits"
     export *
   }
   module list {
     header "list"
     export initializer_list

libcxx/test/libcxx/algorithms/alg.sorting/assert.sort.invalid_comparator.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
 //
 //===----------------------------------------------------------------------===//
 
 // REQUIRES: stdlib=libc++
 
 // 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:
-//
-//    comp(a, b) implies that !comp(b, a)
-//
-// In other words,
-//
-//    a < b implies that !(b < a)
+// 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:
+//
+//    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
 
 #include <algorithm>
 #include <cassert>
 #include <cstddef>
+#include <limits>
 #include <map>
 #include <memory>
 #include <ranges>
+#include <random>
 #include <set>
 #include <string>
 #include <vector>
 
 #include "check_assertion.h"
 
 std::string DATA =
 #   include "bad_comparator_values.dat"
 ;
 
-int main(int, char**) {
+void check_oob_sort_read() {
     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()));
         it = std::next(it);
// Check the classic sorting algorithms
         for (auto const& e : elements)
             copy.push_back(e.get());
         TEST_LIBCPP_ASSERT_FAILURE(std::sort(copy.begin(), copy.end(), checked_predicate), "Would read out of bounds");
     }
     {
         std::vector<std::size_t*> 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<std::size_t*> 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<std::size_t*> 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<std::size_t*> copy;
         for (auto const& e : elements)
             copy.push_back(e.get());
         std::vector<std::size_t*> 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<std::size_t*> copy;
         for (auto const& e : elements)
             copy.push_back(e.get());
         std::nth_element(copy.begin(), copy.end(), copy.end(), checked_predicate); // doesn't go OOB even with invalid comparator
     }
 
     // Check the Ranges sorting algorithms
     {
         std::vector<std::size_t*> copy;
         for (auto const& e : elements)
             copy.push_back(e.get());
         TEST_LIBCPP_ASSERT_FAILURE(std::ranges::sort(copy, checked_predicate), "Would read out of bounds");
     }
     {
         std::vector<std::size_t*> 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<std::size_t*> 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<std::size_t*> 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<std::size_t*> copy;
         for (auto const& e : elements)
             copy.push_back(e.get());
         std::vector<std::size_t*> 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<std::size_t*> copy;
         for (auto const& e : elements)
             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<float> generate_float_data() {
+    std::vector<float> floats(50);
+    for (int i = 0; i < 50; ++i) {
+        floats[i] = static_cast<float>(i);
+    }
+    floats.push_back(std::numeric_limits<float>::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<int> v(1);
+    TEST_LIBCPP_ASSERT_FAILURE(std::sort(v.begin(), v.end(), std::greater_equal<int>()), "not a valid strict-weak ordering");
+    TEST_LIBCPP_ASSERT_FAILURE(std::stable_sort(v.begin(), v.end(), std::greater_equal<int>()), "not a valid strict-weak ordering");
+    std::make_heap(v.begin(), v.end(), std::greater_equal<int>());
+    TEST_LIBCPP_ASSERT_FAILURE(std::sort_heap(v.begin(), v.end(), std::greater_equal<int>()), "not a valid strict-weak ordering");
+    TEST_LIBCPP_ASSERT_FAILURE(std::ranges::sort(v, std::greater_equal<int>()), "not a valid strict-weak ordering");
+    TEST_LIBCPP_ASSERT_FAILURE(std::ranges::stable_sort(v, std::greater_equal<int>()), "not a valid strict-weak ordering");
+    std::ranges::make_heap(v, std::greater_equal<int>());
+    TEST_LIBCPP_ASSERT_FAILURE(std::ranges::sort_heap(v, std::greater_equal<int>()), "not a valid strict-weak ordering");
+}
+
+int main(int, char**) {
+
+    check_oob_sort_read();
+
+    check_nan_floats();
+
+    check_irreflexive();
 
     return 0;
 }
+

libcxx/test/libcxx/private_headers.verify.cpp

 #include <__concepts/swappable.h> // expected-error@*:* {{use of private header from outside its module: '__concepts/swappable.h'}}
 #include <__concepts/totally_ordered.h> // expected-error@*:* {{use of private header from outside its module: '__concepts/totally_ordered.h'}}
 #include <__condition_variable/condition_variable.h> // expected-error@*:* {{use of private header from outside its module: '__condition_variable/condition_variable.h'}}
 #include <__coroutine/coroutine_handle.h> // expected-error@*:* {{use of private header from outside its module: '__coroutine/coroutine_handle.h'}}
 #include <__coroutine/coroutine_traits.h> // expected-error@*:* {{use of private header from outside its module: '__coroutine/coroutine_traits.h'}}
 #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'}}
 #include <__exception/operations.h> // expected-error@*:* {{use of private header from outside its module: '__exception/operations.h'}}
 #include <__exception/terminate.h> // expected-error@*:* {{use of private header from outside its module: '__exception/terminate.h'}}
 #include <__expected/bad_expected_access.h> // expected-error@*:* {{use of private header from outside its module: '__expected/bad_expected_access.h'}}
 #include <__expected/expected.h> // expected-error@*:* {{use of private header from outside its module: '__expected/expected.h'}}
 #include <__expected/unexpect.h> // expected-error@*:* {{use of private header from outside its module: '__expected/unexpect.h'}}

libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/sort.heap/complexity.pass.cpp

for (int logn = 10; logn <= 20; ++logn) {
     stats = {};
     std::sort_heap(first, last);
     LIBCPP_ASSERT(stats.copied == 0);
     LIBCPP_ASSERT(stats.moved <= 2 * n + n * logn);
 #ifndef _LIBCPP_ENABLE_DEBUG_MODE
     LIBCPP_ASSERT(stats.compared <= n * logn);
 #endif
     LIBCPP_ASSERT(std::is_sorted(first, last));
-    LIBCPP_ASSERT(stats.compared <= 2 * n * logn);
   }
   return 0;
 }

libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/sort.heap/ranges_sort_heap.pass.cpp

std::array expected = {1, 2, 3};
       auto in = input;
       auto last = std::ranges::sort_heap(in, [](int i, int j) { return BooleanTestable{i < j}; });
       verify_sorted(in, last, expected);
     }
   }
 
   { // `std::ranges::dangling` is returned.
     [[maybe_unused]] std::same_as<std::ranges::dangling> decltype(auto) result =
-        std::ranges::sort_heap(std::array{2, 1, 3});
+        std::ranges::sort_heap(std::array{3, 1, 2});
   }
 
   return true;
 }
 
 struct Stats {
   int compared = 0;
   int copied   = 0;
for (int logn = 10; logn <= 20; ++logn) {
     stats = {};
     std::ranges::sort_heap(first, last, &MyInt::Comp);
     LIBCPP_ASSERT(stats.copied == 0);
     LIBCPP_ASSERT(stats.moved <= 2 * n + n * logn);
 #ifndef _LIBCPP_ENABLE_DEBUG_MODE
     LIBCPP_ASSERT(stats.compared <= n * logn);
 #endif
     LIBCPP_ASSERT(std::is_sorted(first, last, &MyInt::Comp));
-    LIBCPP_ASSERT(stats.compared <= 2 * n * logn);
   }
 }
 
 int main(int, char**) {
   test();
   static_assert(test());
   test_complexity();
   return 0;
 }

libcxx/test/std/algorithms/ranges_robust_against_dangling.pass.cpp

if (!std::is_constant_evaluated())
     dangling_1st(std::ranges::stable_sort, in);
   dangling_1st(std::ranges::partial_sort, in, mid);
   dangling_1st(std::ranges::nth_element, in, mid);
   if (!std::is_constant_evaluated())
     dangling_1st(std::ranges::inplace_merge, in, mid);
   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<prev_permutation_result<dangling>>(std::ranges::prev_permutation, in);
   dangling_1st<next_permutation_result<dangling>>(std::ranges::next_permutation, in);
 
   return true;
 }
 
 int main(int, char**) {
   test_all();
   static_assert(test_all());
 
   return 0;
 }

libcxx/test/std/algorithms/robust_against_proxy_iterators_lifetime_bugs.pass.cpp

Reference(Reference&& rhs) noexcept : v_(rhs.v_) {
 
       lifetime_cache.insert(this);
     }
 
     Reference& operator=(const Reference& rhs) {
       assert(lifetime_cache.contains(this) && lifetime_cache.contains(&rhs));
       assert(!rhs.moved_from_);
 
-      v_ = rhs.v_;
+      *v_ = *rhs.v_;
       moved_from_ = false;
 
       return *this;
     }
 
     Reference& operator=(Reference&& rhs) noexcept {
       assert(lifetime_cache.contains(this) && lifetime_cache.contains(&rhs));
 
       assert(!rhs.moved_from_);
       rhs.moved_from_ = true;
 
-      v_ = rhs.v_;
+      *v_ = *rhs.v_;
       moved_from_ = false;
 
       return *this;
     }
 
     operator Value() const {
       assert(lifetime_cache.contains(this));
       assert(!moved_from_);

libcxx/utils/data/ignore_format.txt

 libcxx/include/__coroutine/coroutine_traits.h
 libcxx/include/__coroutine/noop_coroutine_handle.h
 libcxx/include/__coroutine/trivial_awaitables.h
 libcxx/include/cstddef
 libcxx/include/ctype.h
 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
 libcxx/include/__expected/expected.h
 libcxx/include/experimental/__config
 libcxx/include/experimental/iterator
 libcxx/include/experimental/map
 libcxx/include/experimental/__memory

llvm/utils/gn/secondary/libcxx/include/BUILD.gn

sources = [
       "__condition_variable/condition_variable.h",
       "__config",
       "__coroutine/coroutine_handle.h",
       "__coroutine/coroutine_traits.h",
       "__coroutine/noop_coroutine_handle.h",
       "__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",
       "__exception/operations.h",
       "__exception/terminate.h",
       "__expected/bad_expected_access.h",
       "__expected/expected.h",
       "__expected/unexpect.h",