intermediate changes

ref:6047a064234457e5084bb81c38d0758e4de103c3

5 files changed, 69 insertions, 10 deletions

diff --git a/contrib/libs/cxxsupp/libcxx/include/__algorithm/comp_ref_type.h b/contrib/libs/cxxsupp/libcxx/include/__algorithm/comp_ref_type.h
index a3a3866f14..e95c26054d 100644
--- a/contrib/libs/cxxsupp/libcxx/include/__algorithm/comp_ref_type.h
+++ b/contrib/libs/cxxsupp/libcxx/include/__algorithm/comp_ref_type.h
@@ -11,6 +11,11 @@
 
 #include <__config>
 
+#ifdef _LIBCPP_DEBUG
+#  include <__debug>
+#  include <__utility/declval.h>
+#endif
+
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
diff --git a/contrib/libs/cxxsupp/libcxx/include/__algorithm/nth_element.h b/contrib/libs/cxxsupp/libcxx/include/__algorithm/nth_element.h
index bec6355ba9..63feba1ea6 100644
--- a/contrib/libs/cxxsupp/libcxx/include/__algorithm/nth_element.h
+++ b/contrib/libs/cxxsupp/libcxx/include/__algorithm/nth_element.h
@@ -16,6 +16,10 @@
 #include <__iterator/iterator_traits.h>
 #include <__utility/swap.h>
 
+#if defined(_LIBCPP_DEBUG_RANDOMIZE_UNSPECIFIED_STABILITY)
+#  include <__algorithm/shuffle.h>
+#endif
+
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
@@ -222,8 +226,13 @@ 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);
+  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 <class _RandomAccessIterator>
diff --git a/contrib/libs/cxxsupp/libcxx/include/__algorithm/partial_sort.h b/contrib/libs/cxxsupp/libcxx/include/__algorithm/partial_sort.h
index b1d2e1a79c..622624ec4f 100644
--- a/contrib/libs/cxxsupp/libcxx/include/__algorithm/partial_sort.h
+++ b/contrib/libs/cxxsupp/libcxx/include/__algorithm/partial_sort.h
@@ -18,6 +18,10 @@
 #include <__iterator/iterator_traits.h>
 #include <__utility/swap.h>
 
+#if defined(_LIBCPP_DEBUG_RANDOMIZE_UNSPECIFIED_STABILITY)
+#  include <__algorithm/shuffle.h>
+#endif
+
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
@@ -48,8 +52,10 @@ 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);
+  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 <class _RandomAccessIterator>
diff --git a/contrib/libs/cxxsupp/libcxx/include/__algorithm/shuffle.h b/contrib/libs/cxxsupp/libcxx/include/__algorithm/shuffle.h
index 292e60d791..7f6ad50e24 100644
--- a/contrib/libs/cxxsupp/libcxx/include/__algorithm/shuffle.h
+++ b/contrib/libs/cxxsupp/libcxx/include/__algorithm/shuffle.h
@@ -25,6 +25,40 @@ _LIBCPP_PUSH_MACROS
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
+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
+  }
+};
+
 #if _LIBCPP_STD_VER <= 14 || defined(_LIBCPP_ENABLE_CXX17_REMOVED_RANDOM_SHUFFLE) \
   || defined(_LIBCPP_BUILDING_LIBRARY)
 class _LIBCPP_TYPE_VIS __rs_default;
diff --git a/contrib/libs/cxxsupp/libcxx/include/__algorithm/sort.h b/contrib/libs/cxxsupp/libcxx/include/__algorithm/sort.h
index c0b602b2bb..24d0a4935b 100644
--- a/contrib/libs/cxxsupp/libcxx/include/__algorithm/sort.h
+++ b/contrib/libs/cxxsupp/libcxx/include/__algorithm/sort.h
@@ -18,6 +18,10 @@
 #include <__utility/swap.h>
 #include <memory>
 
+#if defined(_LIBCPP_DEBUG_RANDOMIZE_UNSPECIFIED_STABILITY)
+#  include <__algorithm/shuffle.h>
+#endif
+
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
@@ -529,12 +533,13 @@ 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));
-    } else {
-        _VSTD::__sort<_Comp_ref>(_VSTD::__unwrap_iter(__first), _VSTD::__unwrap_iter(__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));
+  }
 }
 
 template <class _RandomAccessIterator>