[libcxx][RFC] Unspecified behavior randomization in libcxx

[danlark]

Summary

This effort is dedicated to deflake the tests of the users which depend
on the unspecified behavior of algorithms and containers. This also
might help updating the sorting algorithm in libcxx which has the
quadratic worst case in the future or at least create a new one under
flag.

For detailed design, please see the design doc I provide in the patch

Email: [e-mail], Author: Danila Kutenin. I don't have commit
rights

[danlark]

Fix unused parameters

[ldionne]

First of all, thanks for writing a design document and explaining the purpose of your patch. Let me try to understand the use case a bit better.

So basically, let's say you're trying to adopt a new implementation of std::sort internally. You change that, but then you realize that a bunch of tests break because they were relying on the exact order of equal elements after std::sort, which is really unspecified. But since those tests are failing, you can't use the new std::sort implementation until all the tests have been fixed. So, in order to make that transition easier and allow fixing tests one by one, you add this feature. You then turn it on locally for some projects/tests inside your organization, and you fix them one by one. Once you're done, you can switch the algorithm implementation, and turn off the randomization. Is that the idea?

The main problem I see with this reasoning is that it doesn't really help libc++ as a project to migrate to a new algorithm. Libc++ is used by plenty of people who might be relying on the order of elements after calling std::sort, and they'll never know about this setting before we break their code. Are we comfortable with breaking such users? I mean, we're technically allowed to by the Standard, but still. I *think* I'd be fine with that, but this needs a bit of discussion.

Technically speaking, there's a few things on my mind while reviewing this:

1. Is there a bad interaction because we instantiate some algorithms in the dylib. I checked and I don't think that's the case.
2. Is there a way we can achieve the same with some sort of sanitizer or tool external to libc++ instead? If we could do that, I think it would certainly deliver more value in the long term, and it would certainly be more powerful than manually-added checks in libc++.
3. How can we minimize the complexity we're adding to libc++? This is the Standard Library, and literally everybody wants to add their "very small tweak" to it. If we're not very aggressive about reducing complexity, it becomes a mess. For example, do you really need to be able to specify the seed? Can you explain why? And in case it almost always makes sense to specify a seed, can we make it mandatory instead? I'm trying to reduce the number of configurations we have to maintain.
4. If we do this, then does it make sense to group it with other features such as the Debug mode? It seems to me that this effort, iterator invalidation checking and other similar checks kind of fall into the same bucket of "things that turn silent misuses into loud failures so you diagnose them before they hit prod". If we decide to go ahead with your patch, I think it would be useful to have a wider vision for how we handle these sorts of additions in the future.

Requesting changes so it shows up properly in the queue. Let's have a discussion.

Thanks!

libcxx/docs/DesignDocs/UnspecifiedBehaviorRandomization.rst

19

all elements in the vector

20–22

Do you mean that it prevents libc++ from changing the implementation of algorithms like std::sort? I think it's useful to try and use the term "implementation" here, because just saying "algorithm" isn't clear (std::sort is commonly referred to as an "algorithm", but you really mean the underlying implementation of it).

31

LLVM

44

turn it on, or alternatively enable it

50

within a run

libcxx/include/algorithm

3113 ↗

(On Diff #324583)

Why are we making this a template?

3127–3132 ↗

(On Diff #324583)

I'm far from being a PRNG expert - can you explain what you're doing here?

[danlark]

Address comments

[danlark]

In D96946#2571506, @ldionne wrote:

First of all, thanks for writing a design document and explaining the purpose of your patch. Let me try to understand the use case a bit better.

So basically, let's say you're trying to adopt a new implementation of std::sort internally. You change that, but then you realize that a bunch of tests break because they were relying on the exact order of equal elements after std::sort, which is really unspecified. But since those tests are failing, you can't use the new std::sort implementation until all the tests have been fixed. So, in order to make that transition easier and allow fixing tests one by one, you add this feature. You then turn it on locally for some projects/tests inside your organization, and you fix them one by one. Once you're done, you can switch the algorithm implementation, and turn off the randomization. Is that the idea?

Yes, that's a correct understanding except switching off the randomization would not happen. It should be a by default feature for us to preserve new cases of stability dependencies in some debug builds, in release builds, we are not going to do any randomization but we can guarantee that new sorting algorithm works as best as we can test.

The main problem I see with this reasoning is that it doesn't really help libc++ as a project to migrate to a new algorithm. Libc++ is used by plenty of people who might be relying on the order of elements after calling std::sort, and they'll never know about this setting before we break their code. Are we comfortable with breaking such users? I mean, we're technically allowed to by the Standard, but still. I *think* I'd be fine with that, but this needs a bit of discussion.

Technically speaking, there's a few things on my mind while reviewing this:

1. Is there a bad interaction because we instantiate some algorithms in the dylib. I checked and I don't think that's the case.
2. Is there a way we can achieve the same with some sort of sanitizer or tool external to libc++ instead? If we could do that, I think it would certainly deliver more value in the long term, and it would certainly be more powerful than manually-added checks in libc++.
3. How can we minimize the complexity we're adding to libc++? This is the Standard Library, and literally everybody wants to add their "very small tweak" to it. If we're not very aggressive about reducing complexity, it becomes a mess. For example, do you really need to be able to specify the seed? Can you explain why? And in case it almost always makes sense to specify a seed, can we make it mandatory instead? I'm trying to reduce the number of configurations we have to maintain.
4. If we do this, then does it make sense to group it with other features such as the Debug mode? It seems to me that this effort, iterator invalidation checking and other similar checks kind of fall into the same bucket of "things that turn silent misuses into loud failures so you diagnose them before they hit prod". If we decide to go ahead with your patch, I think it would be useful to have a wider vision for how we handle these sorts of additions in the future.

Requesting changes so it shows up properly in the queue. Let's have a discussion.

Thanks!

I think we should at some point break users in algorithms, for example, in sorting because we are not compliant now and new algorithms just evolve. Providing an option to migrate is possibly the best we can do

1. No, no bad interaction
2. That's possible for the compiler to introduce some hooks before calling std::sort, however, I thought, it would be easier just to introduce an option if they ever wonder why their tests are failing after the migration to a new version of libc++. Ideally this should be another type of sanitizer which I scared to suggest, to be honest, and patching libcxx seemed much easier and relevant
3. The idea for seed was to have reproducible results no matter. I am fine with removing it if you feel this is an unnecessary complication. Having random seed per run was the initial idea so that the tests become flaky and the users notice
4. I am fine with moving it under debug, I did not do it right away because DEBUG mode is deterministic currently and I thought another option is still good. If you are ok with moving it under debug, me too

libcxx/include/algorithm

3113 ↗

(On Diff #324583)

Because there is no algorithm.cpp and I decided not to create one because of such feature. It is needed to instantiate static const void* const __seed_static; and inline variables are only a C++17 feature, before that it was a common trick to put the static variable definition in header

See

template <class _Void>
const void* const __random_unspecified_behavior_gen_<_Void>::__seed_static =
    &__seed_static;

3127–3132 ↗

(On Diff #324583)

It's some very simple PCG random generator, I switched to a more simple linear congruential in order to remove complexity

[danlark]

Ping @ldionne

Sorry for not pinging for so long

So, overall I am ok with putting this under _LIBCPP_DEBUG 2 but separate option would be better because the users do not want unstable results until they really do.

What do you think? Given the discussions in the C++ standard committee, I think this is a reasonable approach to give the users opportunities to upgrade to something better and show how it could be done. Having std::sort from 2005 and not updating/offering something better and standard compliant feels just wrong.

[tschuett]

It is similar to

llvm::sort

https://lists.llvm.org/pipermail/llvm-dev/2018-April/122576.html

[danlark]

Hi, is this still going and are you interested? I see https://reviews.llvm.org/D93233 and this infrastructure will help all users to migrate and avoid Hyrum's Law dependencies if they see problems

I can remove SEED if needed.

[danlark]

@ldionne call of last hope, if I should continue the effort :)

Even with D113413 many users are likely to complain that new libcxx broke their tests. Yes, they should not depend on the ordering, however, there is no infrastructure to guarantee that behavior at scale. Providing an option to handle in separate builds and gradual rollout may help them to write better code overall.

It's not an ABI contract but I am pretty sure this will rise quite heavily when we decide to switch the implementation.

[• Quuxplusone]

FWIW, I think this wouldn't be too bad. I'm also not convinced it has much benefit. But here are some minor tweaks that I think would minorly increase its minor benefit and minorly decrease its minor cost:

#if _LIBCPP_DEBUG_RANDOMIZE
 #ifdef _LIBCPP_CXX03_LANG
  #error "Randomization of unspecified behavior is available only in C++11 and later"
 #endif
 #define _LIBCPP_DEBUG_RANDOMIZE_RANGE(__first, __last) do { if (!__libcpp_is_constant_evaluated()) _VSTD::shuffle(__first, __last, __libcpp_debug_randomizer()); } while (0)
#else
 #define _LIBCPP_DEBUG_RANDOMIZE_RANGE(__first, __last) (void)0
#endif

This makes the changes to sort, nth_element, and partial_sort into one-line diffs.
Also, unless I'm missing something, you should apply the one-line diff also to std::partition.
I'd make the name of the macro involve DEBUG, but I wouldn't literally enable this as part of _LIBCPP_DEBUG=1 or 2 or whatever.

Anyway, as usual, I'm offering tweaks that I think should improve this PR's chances, but making these tweaks is no guarantee of future results. ldionne is still the one to decide whether this whole direction is worthwhile at all.

[ldionne]

In D96946#3124857, @danlark wrote:

@ldionne call of last hope, if I should continue the effort :)

Sorry for dropping the ball here.

Yes, let's make this happen. I think this is useful. IMO, it would make most sense for it to be enabled unconditionally if the debug mode is enabled too instead of having a separate toggle just for it. I'm soon going to be cleaning up the debug mode (and in particular making sure it works at all), so this would become supported better. WDYT?

libcxx/docs/DesignDocs/UnspecifiedBehaviorRandomization.rst

31

32

39

Can we rename this to _LIBCPP_DEBUG_RANDOMIZE_UNSPECIFIED_STABILITY instead, since it is tied to the debug mode (if we apply my suggestions here)?

libcxx/docs/UsingLibcxx.rst

244–250 ↗

(On Diff #324677)

This should be moved to the documentation of the debug mode. In particular, I would like it if it were NOT advertised as something that can be tweaked by users. Users should only select the debug mode level.

libcxx/include/__config

861–876

What would you think of enabling this automatically when the debug mode is enabled?

#if _LIBCPP_DEBUG_LEVEL >= 2
# define _LIBCPP_RANDOMIZE_UNSPECIFIED_STABILITY
#endif

864

libcxx/include/algorithm

3125 ↗

(On Diff #324677)

3131–3132 ↗

(On Diff #324677)

3136–3137 ↗

(On Diff #324677)

We don't generally qualify types when in namespace std. Applies elsewhere.

3138 ↗

(On Diff #324677)

3139 ↗

(On Diff #324677)

3150–3151 ↗

(On Diff #324677)

3153–3154 ↗

(On Diff #324677)

[• Quuxplusone]

libcxx/include/algorithm

3113 ↗

(On Diff #324583)

Seems like it would be way simpler to just do the other C++ singleton trick, which is "make the thing a function-local static variable":

    _LIBCPP_ALWAYS_INLINE static result_type __seed() {
#ifdef _LIBCPP_RANDOMIZE_UNSPECIFIED_STABILITY_SEED
      return _LIBCPP_RANDOMIZE_UNSPECIFIED_STABILITY_SEED;
#else
      static char __x;
      return reinterpret_cast<uintptr_t>(&__x);
#endif
    }

I see no reason for any of the helper machinery here; it looks like we're just trying to generate a "random seed" from an address, so let's just do that. No global variables, no templates (not even any unnecessary casts!), nice and simple.

[ldionne]

libcxx/include/algorithm

3113 ↗

(On Diff #324583)

Yeah, agreed, IMO that seems cleaner.

[ldionne]

@danlark
Oh yeah, sorry for the spam, but can you add a release note mentioning that we added this feature in LLVM 14?

[danlark]

All comments are done

I can also write a test for std::partition but maybe later

libcxx/docs/DesignDocs/UnspecifiedBehaviorRandomization.rst

39

done

libcxx/docs/UsingLibcxx.rst

244–250 ↗

(On Diff #324677)

Thanks, done

libcxx/include/__config

861–876

I like it

libcxx/include/algorithm

3150–3151 ↗

(On Diff #324677)

removed in favor of simpler version

3153–3154 ↗

(On Diff #324677)

irrelevant, removed

[danlark]

Improve one comment

[ldionne]

LGTM but we'll need to get CI to pass.

libcxx/docs/ReleaseNotes.rst

54

Let's break this line similarly to surrounding paragraphs.

libcxx/include/__algorithm/nth_element.h

16–18

Can you move this after the initial set of includes (on line 21 roughly) so that we can still keep the rest of the headers sorted easily? Applies everywhere.

libcxx/include/__config

867–874

Personally I preferred the previous version where you had these checks inlined in the algorithms. I should have said it, sorry for the churn. Anyway, feel free to do it however you prefer.

873

If you keep this, let's make it do { } while (false).

[danlark]

Improve the library build support

[danlark]

I hope this is the last update

[danlark]

libcxx/include/__algorithm/shuffle.h

28

Question, windows DLLs were not able to build the tests without _LIBCPP_BUILDING_LIBRARY as I guess because of constructor/destructor ABI of trivial types, should I leave it like that?

Linux and MacOS seem fine without it

libcxx/include/__config

867–874

I actually prefer the macro, the change looks cleaner

[ldionne]

libcxx/include/__algorithm/shuffle.h

28

Oh, I actually meant to leave a comment here but forgot. Let's include this unconditionally, in other words remove the #if defined altogether.

When _LIBCPP_DEBUG_RANDOMIZE_UNSPECIFIED_STABILITY is not used, this is simply going to be an unused type, which doesn't hurt. But at least we'll know it parses properly.

libcxx/include/__config

876

[danlark]

Remove the ifdef for __libcpp_debug_randomizer

libcxx/include/__algorithm/shuffle.h

28

Thanks!

[ldionne]

Let's land this once CI is passing.

I want to thank you for spending time on this issue and being patient with the long review times you experienced. We have a lot of things going on and can only focus on so many things at once, and we always have to prioritize things. I'm glad we finally finished this.

[danlark]

Fix CI and linter

Feel free to revert or ask me to revert the linter changes in __config, clang-format was noisy :)

[• Quuxplusone]

libcxx/include/__algorithm/shuffle.h

28

Btw, I hope that the long-long-term plan is to split up <random> into <__random/*.h>, and then we could just #include <__random/minstd_rand0.h> and eliminate this type altogether. If you can think of a reason we shouldn't plan on doing that, this would be a good time to mention it.
(I guess one reason is that minstd_rand0 comes with its own operator<<, which drags in <iosfwd>; but that's work-aroundable if we need to; we'd just split the operator<< stuff into its own header.)

libcxx/test/libcxx/algorithms/nth_element_stability.pass.cpp

73

This lambda is just std::less<MyType>(), right?

[ldionne]

libcxx/include/__algorithm/shuffle.h

28

Ah, so you do like the modularization of headers, then? 😄

We can address this later when we modularize <random> (yes, that is the long term goal).

libcxx/test/libcxx/algorithms/nth_element_stability.pass.cpp

19–23

Just for posterity, we try to keep includes sorted. Fixed upon committing.

73

Fixed upon committing.

[• Quuxplusone]

libcxx/include/__algorithm/shuffle.h

28

If we hadn't already decided to modularize everything regardless of motivation, then this would strike me as good motivation to split out a lightweight <__random_base>, and it could have been done right in this PR instead of being a project in itself. 😉
(danlark: No action needed. :))

I guess I could volunteer to split up <random>... Once D110738 and D111514 land, I'll launch that project.

[MaskRay]

I wonder whether it is useful to allocate some probability to a deterministic reorder, e.g. reversed order (see D98445 I added ld.lld --shuffle-sections=-1).

libcxx/docs/DesignDocs/UnspecifiedBehaviorRandomization.rst

39

This and a few other works should use reST inline literals. Created D119052

libcxx/docs/DesignDocs/DebugMode.rst

 - ``std::unordered_map``
 - ``std::unordered_multimap``
 - ``std::unordered_set``
 - ``std::unordered_multiset``
 
 The remaining containers do not currently support iterator debugging.
 Patches welcome.
 
+Randomizing Unspecified Behavior (``_LIBCPP_DEBUG == 1``)
+---------------------------------------------------------
+This also enables the randomization of unspecified behavior, for
+example, for equal elements in ``std::sort`` or randomizing both parts of
+the partition after ``std::nth_element`` call. This effort helps you to migrate
+to potential future faster versions of these algorithms and deflake your tests
+which depend on such behavior. To fix the seed, use
+``_LIBCPP_DEBUG_RANDOMIZE_UNSPECIFIED_STABILITY_SEED=seed`` definition.
+
 Handling Assertion Failures
 ===========================
 When a debug assertion fails the assertion handler is called via the
 ``std::__libcpp_debug_function`` function pointer. It is possible to override
 this function pointer using a different handler function. Libc++ provides a
 the default handler, ``std::__libcpp_abort_debug_handler``, which aborts the
 program. The handler may not return. Libc++ can be changed to use a custom
 assertion handler as follows.

libcxx/docs/DesignDocs/UnspecifiedBehaviorRandomization.rst

+==================================
+Unspecified Behavior Randomization
+==================================
+
+Background
+==========
+
+Consider the follow snippet which steadily happens in tests:
+
+
+.. code-block:: cpp
+
+    std::vector<std::pair<int, int>> v(SomeData());
+    std::sort(v.begin(), v.end(), [](const auto& lhs, const auto& rhs) {
+       return lhs.first < rhs.first;
+    });
+
+Under this assumption all elements in the vector whose first elements are equal
+do not guarantee any order. Unfortunately, this prevents libcxx introducing
+other implementatiosn because tests might silently fail and the users might
+heavily depend on the stability of implementations.
+
+Goal
+===================
+
+Provide functionality for randomizing the unspecified behavior so that the users
+can test and migrate their components and libcxx can introduce new sorting
+algorithms and optimizations to the containers.
+
+For example, as of LLVM version 13, libcxx sorting algorithm takes
+`O(n^2) worst case <https://llvm.org/PR20837>`_ but according
+to the standard its worst case should be `O(n log n)`. This effort helps users
+to gradually fix their tests while updating to new faster algorithms.
+
+Design
+======
+
+* Introduce new macro `_LIBCPP_DEBUG_RANDOMIZE_UNSPECIFIED_STABILITY` which should
+  be a part of the libcxx config.
+* This macro randomizes the unspecified behavior of algorithms and containers.
+  For example, for sorting algorithm the input range is shuffled and then
+  sorted.
+* This macro is off by default because users should enable it only for testing
+  purposes and/or migrations if they happen to libcxx.
+* This feature is only available for C++11 and further because of
+  `std::shuffle` availability.
+* We may use `ASLR <https://en.wikipedia.org/wiki/Address_space_layout_randomization>`_ or
+  static `std::random_device` for seeding the random number generator. This
+  guarantees the same stability guarantee within a run but not through different
+  runs, for example, for tests become flaky and eventually be seen as broken.
+  For platforms which do not support ASLR, the seed is fixed during build.
+* The users can fix the seed of the random number generator by providing
+  `_LIBCPP_DEBUG_RANDOMIZE_UNSPECIFIED_STABILITY_SEED=seed` definition.
+
+This comes with some side effects if any of the flags is on:
+
+* Computation penalty, we think users are OK with that if they use this feature.
+* Non reproducible results if they don't use the fixed seed.
+
+
+Impact
+------------------
+
+Google has measured couple of thousands of tests to be dependent on the
+stability of sorting and selection algorithms. As we also plan on updating
+(or least, providing under flag more) sorting algorithms, this effort helps
+doing it gradually and sustainably. This is also bad for users to depend on the
+unspecified behavior in their tests, this effort helps to turn this flag in
+debug mode.
+
+Potential breakages
+-------------------
+
+None if the flag is off. If the flag is on, it may lead to some non-reproducible
+results, for example, for caching.
+
+Currently supported randomization
+---------------------------------
+
+* `std::sort`, there is no guarantee on the order of equal elements
+* `std::partial_sort`, there is no guarantee on the order of equal elements and
+   on the order of the remaining part
+* `std::nth_element`, there is no guarantee on the order from both sides of the
+   partition
+
+Patches welcome.

libcxx/docs/ReleaseNotes.rst

 - There's a new CMake option ``LIBCXX_ENABLE_UNICODE`` to disable Unicode
   support in the ``<format>`` header. This only affects the estimation of the
   output width of the format functions.
 
 - Support for building libc++ on top of a C Standard Library that does not support ``wchar_t`` was
   added. This is useful for building libc++ in an embedded setting, and it adds itself to the various
   freestanding-friendly options provided by libc++.
 
+- ``_LIBCPP_DEBUG`` equals to ``1`` enables the randomization of unspecified behavior of standard algorithms (e.g. equal elements in ``std::sort`` or randomization of both sides of partition for ``std::nth_element``)
+
 API Changes
 -----------
 
 - The functions ``std::atomic<T*>::fetch_(add|sub)`` and
   ``std::atomic_fetch_(add|sub)`` no longer accept a function pointer. While
   this is technically an API break, the invalid syntax isn't supported by
   libstc++ and MSVC STL.  See https://godbolt.org/z/49fvzz98d.
 

libcxx/docs/index.rst

.. toctree::
    DesignDocs/DebugMode
    DesignDocs/ExperimentalFeatures
    DesignDocs/ExtendedCXX03Support
    DesignDocs/FeatureTestMacros
    DesignDocs/FileTimeType
    DesignDocs/NoexceptPolicy
    DesignDocs/ThreadingSupportAPI
    DesignDocs/UniquePtrTrivialAbi
+   DesignDocs/UnspecifiedBehaviorRandomization
    DesignDocs/VisibilityMacros
 
 
 Build Bots and Test Coverage
 ============================
 
 * `Buildkite CI pipeline <https://buildkite.com/llvm-project/libcxx-ci>`_
 * `LLVM Buildbot Builders <http://lab.llvm.org:8011>`_

libcxx/include/__algorithm/nth_element.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_NTH_ELEMENT_H
 #define _LIBCPP___ALGORITHM_NTH_ELEMENT_H
 
 #include <__config>
 #include <__algorithm/comp.h>
 #include <__algorithm/comp_ref_type.h>
 #include <__algorithm/sort.h>
+#if defined(_LIBCPP_DEBUG_RANDOMIZE_UNSPECIFIED_STABILITY)
+#  include <__algorithm/shuffle.h>
+#endif
 #include <__iterator/iterator_traits.h>
 #include <__utility/swap.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
__nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last, _Compare __comp)
     }
 }
 
 template <class _RandomAccessIterator, class _Compare>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 void
 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last, _Compare __comp)
 {
-    typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
-    _VSTD::__nth_element<_Comp_ref>(__first, __nth, __last, __comp);
+  _LIBCPP_DEBUG_RANDOMIZE_RANGE(__first, __last);
+  _LIBCPP_DEBUG_RANDOMIZE_RANGE(__first, __nth);
+  if (__nth != __last) {
+    _LIBCPP_DEBUG_RANDOMIZE_RANGE(++__nth, __last);
+  }
 }
 
 template <class _RandomAccessIterator>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 void
 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last)
 {
     _VSTD::nth_element(__first, __nth, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_NTH_ELEMENT_H

libcxx/include/__algorithm/partial_sort.h

 #define _LIBCPP___ALGORITHM_PARTIAL_SORT_H
 
 #include <__config>
 #include <__algorithm/comp.h>
 #include <__algorithm/comp_ref_type.h>
 #include <__algorithm/make_heap.h>
 #include <__algorithm/sift_down.h>
 #include <__algorithm/sort_heap.h>
+#if defined(_LIBCPP_DEBUG_RANDOMIZE_UNSPECIFIED_STABILITY)
+#  include <__algorithm/shuffle.h>
+#endif
 #include <__iterator/iterator_traits.h>
 #include <__utility/swap.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD

 }
 
 template <class _RandomAccessIterator, class _Compare>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 void
 partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last,
              _Compare __comp)
 {
-    typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
-    _VSTD::__partial_sort<_Comp_ref>(__first, __middle, __last, __comp);
+  _LIBCPP_DEBUG_RANDOMIZE_RANGE(__first, __last);
+  _LIBCPP_DEBUG_RANDOMIZE_RANGE(__middle, __last);
 }
 
 template <class _RandomAccessIterator>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 void
 partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last)
 {
     _VSTD::partial_sort(__first, __middle, __last,
                        __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_PARTIAL_SORT_H

libcxx/include/__algorithm/shuffle.h

 #pragma GCC system_header
 #endif
 
 _LIBCPP_PUSH_MACROS
 #include <__undef_macros>
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
+#if defined(_LIBCPP_DEBUG_RANDOMIZE_UNSPECIFIED_STABILITY)
+
+class _LIBCPP_TYPE_VIS __libcpp_debug_randomizer {
+public:
+  __libcpp_debug_randomizer() {
+    __state = __seed();
+    __inc = __state + 0xda3e39cb94b95bdbULL;
+    __inc = (__inc << 1) | 1;
+  }
+  typedef uint_fast32_t result_type;
+
+  static const result_type _Min = 0;
+  static const result_type _Max = 0xFFFFFFFF;
+
+  _LIBCPP_HIDE_FROM_ABI result_type operator()() {
+    uint_fast64_t __oldstate = __state;
+    __state = __oldstate * 6364136223846793005ULL + __inc;
+    return __oldstate >> 32;
+  }
+
+  static _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR result_type min() { return _Min; }
+  static _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR result_type max() { return _Max; }
+
+private:
+  uint_fast64_t __state;
+  uint_fast64_t __inc;
+  _LIBCPP_HIDE_FROM_ABI static uint_fast64_t __seed() {
+#  ifdef _LIBCPP_DEBUG_RANDOMIZE_UNSPECIFIED_STABILITY_SEED
+    return _LIBCPP_DEBUG_RANDOMIZE_UNSPECIFIED_STABILITY_SEED;
+#  else
+    static char __x;
+    return reinterpret_cast<uintptr_t>(&__x);
+#  endif
+  }
+};
+
+#endif
+
 #if _LIBCPP_STD_VER <= 14 || defined(_LIBCPP_ENABLE_CXX17_REMOVED_RANDOM_SHUFFLE) \
   || defined(_LIBCPP_BUILDING_LIBRARY)
 class _LIBCPP_TYPE_VIS __rs_default;
 
 _LIBCPP_FUNC_VIS __rs_default __rs_get();
 
 class _LIBCPP_TYPE_VIS __rs_default
 {

libcxx/include/__algorithm/sort.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_H
 #define _LIBCPP___ALGORITHM_SORT_H
 
 #include <__config>
 #include <__algorithm/comp.h>
 #include <__algorithm/comp_ref_type.h>
 #include <__algorithm/min_element.h>
 #include <__algorithm/partial_sort.h>
+#if defined(_LIBCPP_DEBUG_RANDOMIZE_UNSPECIFIED_STABILITY)
+#  include <__algorithm/shuffle.h>
+#endif
 #include <__algorithm/unwrap_iter.h>
 #include <__utility/swap.h>
 #include <memory>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 

 
 _LIBCPP_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 _RandomAccessIterator, class _Compare>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 void
 sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
 {
-    typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
-    if (__libcpp_is_constant_evaluated()) {
-        _VSTD::__partial_sort<_Comp_ref>(__first, __last, __last, _Comp_ref(__comp));
+  _LIBCPP_DEBUG_RANDOMIZE_RANGE(__first, __last);
     } else {
         _VSTD::__sort<_Comp_ref>(_VSTD::__unwrap_iter(__first), _VSTD::__unwrap_iter(__last), _Comp_ref(__comp));
     }
 }
 
 template <class _RandomAccessIterator>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 void
 sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
 {
     _VSTD::sort(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_SORT_H

libcxx/include/__config

 #else  // _LIBCPP_HAS_NO_STRONG_ENUMS
 #  define _LIBCPP_DECLARE_STRONG_ENUM(x) enum class _LIBCPP_ENUM_VIS x
 #  define _LIBCPP_DECLARE_STRONG_ENUM_EPILOG(x)
 #endif // _LIBCPP_HAS_NO_STRONG_ENUMS
 
 // _LIBCPP_DEBUG potential values:
 //  - undefined: No assertions. This is the default.
 //  - 0:         Basic assertions
-//  - 1:         Basic assertions + iterator validity checks.
+//  - 1:         Basic assertions + iterator validity checks + unspecified behavior randomization.
 #if !defined(_LIBCPP_DEBUG)
 # define _LIBCPP_DEBUG_LEVEL 0
 #elif _LIBCPP_DEBUG == 0
 # define _LIBCPP_DEBUG_LEVEL 1
 #elif _LIBCPP_DEBUG == 1
 # define _LIBCPP_DEBUG_LEVEL 2
 #else
 # error Supported values for _LIBCPP_DEBUG are 0 and 1
 #endif
 
+#if _LIBCPP_DEBUG_LEVEL >= 2 &&                        \
+    !defined(_LIBCPP_CXX03_LANG)
+# define _LIBCPP_DEBUG_RANDOMIZE_UNSPECIFIED_STABILITY
+#endif
+
+#if defined(_LIBCPP_DEBUG_RANDOMIZE_UNSPECIFIED_STABILITY)
+#  if defined(_LIBCPP_CXX03_LANG)
+#    error Support for unspecified stability is only for C++11 and higher
+#  endif
+#  define _LIBCPP_DEBUG_RANDOMIZE_RANGE(__first, __last) do { if (!__libcpp_is_constant_evaluated()) _VSTD::shuffle(__first, __last, __libcpp_debug_randomizer()); } while (0)
+#else
+#  define _LIBCPP_DEBUG_RANDOMIZE_RANGE(__first, __last) (void)0
+#endif
+
 // Libc++ allows disabling extern template instantiation declarations by
 // means of users defining _LIBCPP_DISABLE_EXTERN_TEMPLATE.
 //
 // Furthermore, when the Debug mode is enabled, we disable extern declarations
 // when building user code because we don't want to use the functions compiled
 // in the library, which might not have had the debug mode enabled when built.
 // However, some extern declarations need to be used, because code correctness
 // depends on it (several instances in <locale>). Those special declarations
 // are declared with _LIBCPP_EXTERN_TEMPLATE_EVEN_IN_DEBUG_MODE, which is enabled

libcxx/test/libcxx/algorithms/nth_element_stability.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
+//
+//===----------------------------------------------------------------------===//
+
+// <algorithm>
+
+// Test std::nth_element stability randomization
+
+// UNSUPPORTED: c++03
+
+// ADDITIONAL_COMPILE_FLAGS: -D_LIBCPP_DEBUG=1
+
+#include <algorithm>
+#include <array>
+#include <iterator>
+#include <cassert>
+#include <vector>
+
+#include "test_macros.h"
+
+struct MyType {
+  int value = 0;
+  constexpr bool operator<(const MyType& other) const { return value < other.value; }
+};
+
+std::vector<MyType> deterministic() {
+  static constexpr int kSize = 100;
+  std::vector<MyType> v;
+  v.resize(kSize);
+  for (int i = 0; i < kSize; ++i) {
+    v[i].value = (i % 2 ? i : kSize / 2 + i);
+  }
+  std::__nth_element(v.begin(), v.begin() + kSize / 2, v.end(), std::less<MyType>());
+  return v;
+}
+
+void test_randomization() {
+  static constexpr int kSize = 100;
+  std::vector<MyType> v;
+  v.resize(kSize);
+  for (int i = 0; i < kSize; ++i) {
+    v[i].value = (i % 2 ? i : kSize / 2 + i);
+  }
+  auto deterministic_v = deterministic();
+  std::nth_element(v.begin(), v.begin() + kSize / 2, v.end());
+  bool all_equal = true;
+  for (int i = 0; i < kSize; ++i) {
+    if (v[i].value != deterministic_v[i].value) {
+      all_equal = false;
+    }
+  }
+  assert(!all_equal);
+}
+
+void test_same() {
+  static constexpr int kSize = 100;
+  std::vector<MyType> v;
+  v.resize(kSize);
+  for (int i = 0; i < kSize; ++i) {
+    v[i].value = (i % 2 ? i : kSize / 2 + i);
+  }
+  auto snapshot_v = v;
+  auto snapshot_custom_v = v;
+  std::nth_element(v.begin(), v.begin() + kSize / 2, v.end());
+  std::nth_element(snapshot_v.begin(), snapshot_v.begin() + kSize / 2, snapshot_v.end());
+  std::nth_element(snapshot_custom_v.begin(), snapshot_custom_v.begin() + kSize / 2, snapshot_custom_v.end(),
+                   [](const MyType& lhs, const MyType& rhs) { return lhs.value < rhs.value; });
+  bool all_equal = true;
+  for (int i = 0; i < kSize; ++i) {
+    if (v[i].value != snapshot_v[i].value || v[i].value != snapshot_custom_v[i].value) {
+      all_equal = false;
+    }
+    if (i < kSize / 2) {
+      assert(v[i].value <= v[kSize / 2].value);
+    }
+  }
+  assert(all_equal);
+}
+
+#if TEST_STD_VER > 17
+constexpr bool test_constexpr() {
+  std::array<MyType, 10> v;
+  for (int i = 9; i >= 0; --i) {
+    v[9 - i].value = i;
+  }
+  std::nth_element(v.begin(), v.begin() + 5, v.end());
+  return std::is_partitioned(v.begin(), v.end(), [&](const MyType& m) { return m.value <= v[5].value; });
+}
+#endif
+
+int main(int, char**) {
+  test_randomization();
+  test_same();
+#if TEST_STD_VER > 17
+  static_assert(test_constexpr(), "");
+#endif
+  return 0;
+}

libcxx/test/libcxx/algorithms/partial_sort_stability.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
+//
+//===----------------------------------------------------------------------===//
+
+// <algorithm>
+
+// Test std::partial_sort stability randomization
+
+// UNSUPPORTED: c++03
+
+// ADDITIONAL_COMPILE_FLAGS: -D_LIBCPP_DEBUG=1
+
+#include <algorithm>
+#include <array>
+#include <iterator>
+#include <cassert>
+#include <vector>
+
+#include "test_macros.h"
+
+struct MyType {
+  int value = 0;
+  constexpr bool operator<(const MyType& other) const { return value < other.value; }
+};
+
+std::vector<MyType> deterministic() {
+  static constexpr int kSize = 100;
+  std::vector<MyType> v;
+  v.resize(kSize);
+  for (int i = 0; i < kSize; ++i) {
+    v[i].value = (i % 2 ? 1 : kSize / 2 + i);
+  }
+  std::__partial_sort(v.begin(), v.begin() + kSize / 2, v.end(), std::less<MyType>());
+  return v;
+}
+
+void test_randomization() {
+  static constexpr int kSize = 100;
+  std::vector<MyType> v;
+  v.resize(kSize);
+  for (int i = 0; i < kSize; ++i) {
+    v[i].value = (i % 2 ? 1 : kSize / 2 + i);
+  }
+  auto deterministic_v = deterministic();
+  std::partial_sort(v.begin(), v.begin() + kSize / 2, v.end());
+  bool all_equal = true;
+  for (int i = 0; i < kSize; ++i) {
+    if (v[i].value != deterministic_v[i].value) {
+      all_equal = false;
+    }
+  }
+  assert(!all_equal);
+}
+
+void test_same() {
+  static constexpr int kSize = 100;
+  std::vector<MyType> v;
+  v.resize(kSize);
+  for (int i = 0; i < kSize; ++i) {
+    v[i].value = (i % 2 ? 1 : kSize / 2 + i);
+  }
+  auto snapshot_v = v;
+  auto snapshot_custom_v = v;
+  std::partial_sort(v.begin(), v.begin() + kSize / 2, v.end());
+  std::partial_sort(snapshot_v.begin(), snapshot_v.begin() + kSize / 2, snapshot_v.end());
+  std::partial_sort(snapshot_custom_v.begin(), snapshot_custom_v.begin() + kSize / 2, snapshot_custom_v.end(),
+                    [](const MyType& lhs, const MyType& rhs) { return lhs.value < rhs.value; });
+  bool all_equal = true;
+  for (int i = 0; i < kSize; ++i) {
+    if (v[i].value != snapshot_v[i].value || v[i].value != snapshot_custom_v[i].value) {
+      all_equal = false;
+    }
+    if (i < kSize / 2) {
+      assert(v[i].value == 1);
+    }
+  }
+  assert(all_equal);
+}
+
+#if TEST_STD_VER > 17
+constexpr bool test_constexpr() {
+  std::array<MyType, 10> v;
+  for (int i = 9; i >= 0; --i) {
+    v[9 - i].value = i;
+  }
+  std::partial_sort(v.begin(), v.begin() + 5, v.end());
+  return std::is_sorted(v.begin(), v.begin() + 5);
+}
+#endif
+
+int main(int, char**) {
+  test_randomization();
+  test_same();
+#if TEST_STD_VER > 17
+  static_assert(test_constexpr(), "");
+#endif
+  return 0;
+}

libcxx/test/libcxx/algorithms/sort_stability.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
+//
+//===----------------------------------------------------------------------===//
+
+// <algorithm>
+
+// Test std::sort stability randomization
+
+// UNSUPPORTED: c++03
+
+// ADDITIONAL_COMPILE_FLAGS: -D_LIBCPP_DEBUG=1
+
+#include <algorithm>
+#include <array>
+#include <iterator>
+#include <cassert>
+#include <vector>
+
+#include "test_macros.h"
+
+struct EqualType {
+  int value = 0;
+  constexpr bool operator<(const EqualType&) const { return false; }
+};
+
+std::vector<EqualType> deterministic() {
+  static constexpr int kSize = 100;
+  std::vector<EqualType> v;
+  v.resize(kSize);
+  for (int i = 0; i < kSize; ++i) {
+    v[i].value = kSize / 2 - i * (i % 2 ? -1 : 1);
+  }
+  std::__sort(v.begin(), v.end(), std::less<EqualType>());
+  return v;
+}
+
+void test_randomization() {
+  static constexpr int kSize = 100;
+  std::vector<EqualType> v;
+  v.resize(kSize);
+  for (int i = 0; i < kSize; ++i) {
+    v[i].value = kSize / 2 - i * (i % 2 ? -1 : 1);
+  }
+  auto deterministic_v = deterministic();
+  std::sort(v.begin(), v.end());
+  bool all_equal = true;
+  for (int i = 0; i < kSize; ++i) {
+    if (v[i].value != deterministic_v[i].value) {
+      all_equal = false;
+    }
+  }
+  assert(!all_equal);
+}
+
+void test_same() {
+  static constexpr int kSize = 100;
+  std::vector<EqualType> v;
+  v.resize(kSize);
+  for (int i = 0; i < kSize; ++i) {
+    v[i].value = kSize / 2 - i * (i % 2 ? -1 : 1);
+  }
+  auto snapshot_v = v;
+  auto snapshot_custom_v = v;
+  std::sort(v.begin(), v.end());
+  std::sort(snapshot_v.begin(), snapshot_v.end());
+  std::sort(snapshot_custom_v.begin(), snapshot_custom_v.end(),
+            [](const EqualType&, const EqualType&) { return false; });
+  bool all_equal = true;
+  for (int i = 0; i < kSize; ++i) {
+    if (v[i].value != snapshot_v[i].value || v[i].value != snapshot_custom_v[i].value) {
+      all_equal = false;
+    }
+  }
+  assert(all_equal);
+}
+
+#if TEST_STD_VER > 17
+constexpr bool test_constexpr() {
+  std::array<EqualType, 10> v;
+  for (int i = 9; i >= 0; --i) {
+    v[9 - i].value = i;
+  }
+  std::sort(v.begin(), v.end());
+  return std::is_sorted(v.begin(), v.end());
+}
+#endif
+
+int main(int, char**) {
+  test_randomization();
+  test_same();
+#if TEST_STD_VER > 17
+  static_assert(test_constexpr(), "");
+#endif
+  return 0;
+}