Index: libcxx/docs/DesignDocs/DebugMode.rst =================================================================== --- libcxx/docs/DesignDocs/DebugMode.rst +++ libcxx/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 Index: libcxx/docs/DesignDocs/UnspecifiedBehaviorRandomization.rst =================================================================== --- /dev/null +++ libcxx/docs/DesignDocs/UnspecifiedBehaviorRandomization.rst @@ -0,0 +1,86 @@ +================================== +Unspecified Behavior Randomization +================================== + +Background +========== + +Consider the follow snippet which steadily happens in tests: + + +.. code-block:: cpp + + std::vector> 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 `_ 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 `_ 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_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. Index: libcxx/docs/ReleaseNotes.rst =================================================================== --- libcxx/docs/ReleaseNotes.rst +++ libcxx/docs/ReleaseNotes.rst @@ -51,6 +51,8 @@ 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 ----------- Index: libcxx/docs/index.rst =================================================================== --- libcxx/docs/index.rst +++ libcxx/docs/index.rst @@ -177,6 +177,7 @@ DesignDocs/NoexceptPolicy DesignDocs/ThreadingSupportAPI DesignDocs/UniquePtrTrivialAbi + DesignDocs/UnspecifiedBehaviorRandomization DesignDocs/VisibilityMacros Index: libcxx/include/__algorithm/nth_element.h =================================================================== --- libcxx/include/__algorithm/nth_element.h +++ libcxx/include/__algorithm/nth_element.h @@ -13,6 +13,9 @@ #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> @@ -222,8 +225,13 @@ 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); + typedef typename __comp_ref_type<_Compare>::type _Comp_ref; + _VSTD::__nth_element<_Comp_ref>(__first, __nth, __last, __comp); + _LIBCPP_DEBUG_RANDOMIZE_RANGE(__first, __nth); + if (__nth != __last) { + _LIBCPP_DEBUG_RANDOMIZE_RANGE(++__nth, __last); + } } template Index: libcxx/include/__algorithm/partial_sort.h =================================================================== --- libcxx/include/__algorithm/partial_sort.h +++ libcxx/include/__algorithm/partial_sort.h @@ -15,6 +15,9 @@ #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> @@ -48,8 +51,10 @@ 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); + typedef typename __comp_ref_type<_Compare>::type _Comp_ref; + _VSTD::__partial_sort<_Comp_ref>(__first, __middle, __last, __comp); + _LIBCPP_DEBUG_RANDOMIZE_RANGE(__middle, __last); } template Index: libcxx/include/__algorithm/shuffle.h =================================================================== --- libcxx/include/__algorithm/shuffle.h +++ libcxx/include/__algorithm/shuffle.h @@ -25,6 +25,44 @@ _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(&__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; Index: libcxx/include/__algorithm/sort.h =================================================================== --- libcxx/include/__algorithm/sort.h +++ libcxx/include/__algorithm/sort.h @@ -14,6 +14,9 @@ #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 @@ -505,9 +508,10 @@ 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); + 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)); } else { _VSTD::__sort<_Comp_ref>(_VSTD::__unwrap_iter(__first), _VSTD::__unwrap_iter(__last), _Comp_ref(__comp)); } Index: libcxx/include/__config =================================================================== --- libcxx/include/__config +++ libcxx/include/__config @@ -848,7 +848,7 @@ // _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 @@ -859,6 +859,20 @@ # 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. // Index: libcxx/test/libcxx/algorithms/nth_element_stability.pass.cpp =================================================================== --- /dev/null +++ libcxx/test/libcxx/algorithms/nth_element_stability.pass.cpp @@ -0,0 +1,102 @@ +//===----------------------------------------------------------------------===// +// +// 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 +// +//===----------------------------------------------------------------------===// + +// + +// Test std::nth_element stability randomization + +// UNSUPPORTED: c++03 + +// ADDITIONAL_COMPILE_FLAGS: -D_LIBCPP_DEBUG=1 + +#include +#include +#include +#include +#include + +#include "test_macros.h" + +struct MyType { + int value = 0; + constexpr bool operator<(const MyType& other) const { return value < other.value; } +}; + +std::vector deterministic() { + static constexpr int kSize = 100; + std::vector 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()); + return v; +} + +void test_randomization() { + static constexpr int kSize = 100; + std::vector 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 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 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; +} Index: libcxx/test/libcxx/algorithms/partial_sort_stability.pass.cpp =================================================================== --- /dev/null +++ libcxx/test/libcxx/algorithms/partial_sort_stability.pass.cpp @@ -0,0 +1,102 @@ +//===----------------------------------------------------------------------===// +// +// 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 +// +//===----------------------------------------------------------------------===// + +// + +// Test std::partial_sort stability randomization + +// UNSUPPORTED: c++03 + +// ADDITIONAL_COMPILE_FLAGS: -D_LIBCPP_DEBUG=1 + +#include +#include +#include +#include +#include + +#include "test_macros.h" + +struct MyType { + int value = 0; + constexpr bool operator<(const MyType& other) const { return value < other.value; } +}; + +std::vector deterministic() { + static constexpr int kSize = 100; + std::vector 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()); + return v; +} + +void test_randomization() { + static constexpr int kSize = 100; + std::vector 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 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 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; +} Index: libcxx/test/libcxx/algorithms/sort_stability.pass.cpp =================================================================== --- /dev/null +++ libcxx/test/libcxx/algorithms/sort_stability.pass.cpp @@ -0,0 +1,99 @@ +//===----------------------------------------------------------------------===// +// +// 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 +// +//===----------------------------------------------------------------------===// + +// + +// Test std::sort stability randomization + +// UNSUPPORTED: c++03 + +// ADDITIONAL_COMPILE_FLAGS: -D_LIBCPP_DEBUG=1 + +#include +#include +#include +#include +#include + +#include "test_macros.h" + +struct EqualType { + int value = 0; + constexpr bool operator<(const EqualType&) const { return false; } +}; + +std::vector deterministic() { + static constexpr int kSize = 100; + std::vector 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()); + return v; +} + +void test_randomization() { + static constexpr int kSize = 100; + std::vector 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 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 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; +}