[libc++] Unspecified behavior randomization in libc++
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.
Differential Revision: https://reviews.llvm.org/D96946
NOKEYCHECK=True
GitOrigin-RevId: a45d2287adf7942a26be02193731701e61eda7b4
diff --git a/docs/DesignDocs/DebugMode.rst b/docs/DesignDocs/DebugMode.rst
index abcd5e5..faf7b8e 100644
--- a/docs/DesignDocs/DebugMode.rst
+++ b/docs/DesignDocs/DebugMode.rst
@@ -58,6 +58,15 @@
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