[libc++] Make _LIBCPP_DEBUG_RANDOMIZE_RANGE a function

[Mordante]

LGTM once the CI passes. I think it would be good for @ldionne to also have a look so I leave the final approval to him.

libcxx/include/__debug

30–31

Not your change, but I'm not really fond of this structure, where:

• we include headers
• write code
• include more headers

Is there a reason why we can't move this code below the second set of includes and thus not have a small namespace std section?

[ldionne]

I like this! I've been meaning to do this but didn't get around to it. I have some comments though.

libcxx/include/__debug

16

We'll need to include __algorithm/shuffle.h. For that reason, I think we need to pull this into another header (to avoid a bunch of headers suddenly including std::shuffle).

33–39

For unused params warning.

[philnik]

• Address comments

[var-const]

libcxx/include/__libcxx/debug_randomize_range.h

22 ↗

(On Diff #439215)

Also HIDE_FROM_ABI?

[ldionne]

LGTM once CI is green and all comments have been applied.

libcxx/include/CMakeLists.txt

328

Let's call this __debug_utils/randomize_range.h for now, and eventually we can actually rename it to __debug/randomize_range.h, and rename the current __debug header to something else. WDYT? __libcxx/ definitely looks out of place.

libcxx/include/__algorithm/partial_sort.h

22–23

This can be removed (here and in the other headers).

libcxx/include/__libcxx/debug_randomize_range.h

12 ↗

(On Diff #439215)

Maybe guard this include with #ifdef _LIBCPP_DEBUG_RANDOMIZE_UNSPECIFIED_STABILITY?

[philnik]

• Address comments

[philnik]

• Generate files

[philnik]

• Fix includes

[philnik]

• Try to fix Modules

[philnik]

It looks like the ARM runners are currently broken and I've got a bad clang trunk. I'm landing this, but I'll keep an eye on the bootstrapping build.

libcxx/include/CMakeLists.txt

set(files
   __concepts/swappable.h
   __concepts/totally_ordered.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
   __errc
   __filesystem/copy_options.h
   __filesystem/directory_entry.h
   __filesystem/directory_iterator.h
   __filesystem/directory_options.h
   __filesystem/file_status.h
   __filesystem/file_time_type.h
   __filesystem/file_type.h
set(files
   __iterator/projected.h
   __iterator/readable_traits.h
   __iterator/reverse_access.h
   __iterator/reverse_iterator.h
   __iterator/size.h
   __iterator/sortable.h
   __iterator/unreachable_sentinel.h
   __iterator/wrap_iter.h
   __locale
   __mbstate_t.h
   __memory/addressof.h
   __memory/allocate_at_least.h
   __memory/allocation_guard.h
   __memory/allocator.h
   __memory/allocator_arg_t.h
   __memory/allocator_traits.h
   __memory/assume_aligned.h

libcxx/include/__algorithm/nth_element.h

 #define _LIBCPP___ALGORITHM_NTH_ELEMENT_H
 
 #include <__algorithm/comp.h>
 #include <__algorithm/comp_ref_type.h>
 #include <__algorithm/sort.h>
 #include <__config>
 #include <__debug>
 #include <__iterator/iterator_traits.h>
+#include <__libcxx/debug_randomize_range.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
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 template<class _Compare, class _RandomAccessIterator>
 _LIBCPP_CONSTEXPR_AFTER_CXX11 bool
__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)
 {
-  _LIBCPP_DEBUG_RANDOMIZE_RANGE(__first, __last);
+  std::__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);
+  std::__debug_randomize_range(__first, __nth);
   if (__nth != __last) {
-    _LIBCPP_DEBUG_RANDOMIZE_RANGE(++__nth, __last);
+    std::__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

 #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>
 #include <__config>
 #include <__debug>
 #include <__iterator/iterator_traits.h>
+#include <__libcxx/debug_randomize_range.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
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 template <class _Compare, class _RandomAccessIterator>
 _LIBCPP_CONSTEXPR_AFTER_CXX17 void
 __partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last,

 }
 
 template <class _RandomAccessIterator, class _Compare>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 void
 partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last,
              _Compare __comp)
 {
-  _LIBCPP_DEBUG_RANDOMIZE_RANGE(__first, __last);
+  std::__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);
+  std::__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/sort.h

 #include <__algorithm/partial_sort.h>
 #include <__algorithm/unwrap_iter.h>
 #include <__bits>
 #include <__config>
 #include <__debug>
 #include <__functional/operations.h>
 #include <__functional/ranges_operations.h>
 #include <__iterator/iterator_traits.h>
+#include <__libcxx/debug_randomize_range.h>
 #include <__utility/swap.h>
 #include <climits>
 #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
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 // stable, 2-3 compares, 0-2 swaps
 

 extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<double>&, double*>(double*, double*, __less<double>&);
 extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<long double>&, long double*>(long double*, long double*, __less<long double>&);
 
 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 _Comp>
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17
 void __sort_impl(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp& __comp) {
-  _LIBCPP_DEBUG_RANDOMIZE_RANGE(__first, __last);
+  std::__debug_randomize_range(__first, __last);
   using _Comp_ref = typename __comp_ref_type<_Comp>::type;
   if (__libcpp_is_constant_evaluated()) {
     std::__partial_sort<_Comp_ref>(__first, __last, __last, _Comp_ref(__comp));
   } else {
     std::__sort<_Comp_ref>(std::__unwrap_iter(__first), std::__unwrap_iter(__last), _Comp_ref(__comp));
   }
 }
 

libcxx/include/__debug

 // -*- C++ -*-
 //===----------------------------------------------------------------------===//
 //
 // 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___DEBUG
 #define _LIBCPP___DEBUG
 
 #include <__assert>
 #include <__config>
 #include <cstddef>
 #include <type_traits>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 // Catch invalid uses of the legacy _LIBCPP_DEBUG toggle.
 #if defined(_LIBCPP_DEBUG) && _LIBCPP_DEBUG != 0 && !defined(_LIBCPP_ENABLE_DEBUG_MODE)
 #   error "Enabling the debug mode now requires having configured the library with support for the debug mode"
 #endif
 
 #if defined(_LIBCPP_ENABLE_DEBUG_MODE) && !defined(_LIBCPP_CXX03_LANG) && !defined(_LIBCPP_DEBUG_RANDOMIZE_UNSPECIFIED_STABILITY)
 # define _LIBCPP_DEBUG_RANDOMIZE_UNSPECIFIED_STABILITY
 #endif
 
-// TODO: Define this as a function instead
-#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 (!__builtin_is_constant_evaluated())                                                                   \
-        std::shuffle(__first, __last, __libcpp_debug_randomizer());                                             \
-    } while (false)
-#else
-# define _LIBCPP_DEBUG_RANDOMIZE_RANGE(__first, __last)                                                         \
-    do {                                                                                                        \
-    } while (false)
-#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)
 #endif
 
 #if defined(_LIBCPP_ENABLE_DEBUG_MODE) || defined(_LIBCPP_BUILDING_LIBRARY)
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 struct _LIBCPP_TYPE_VIS __c_node;
 
 struct _LIBCPP_TYPE_VIS __i_node
 {
     void* __i_;
     __i_node* __next_;
     __c_node* __c_;

libcxx/include/__debug_utils/randomize_range.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_RANDOMIZE_RANGE_H
+#define _LIBCPP___LIBCXX_DEBUG_RANDOMIZE_RANGE_H
+
+#include <__config>
+
+#ifdef _LIBCPP_DEBUG_RANDOMIZE_UNSPECIFIED_STABILITY
+#  include <__algorithm/shuffle.h>
+#endif
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#  pragma GCC system_header
+#endif
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+template <class _Iterator>
+_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 void __debug_randomize_range(_Iterator __first, _Iterator __last) {
+#ifdef _LIBCPP_DEBUG_RANDOMIZE_UNSPECIFIED_STABILITY
+#  ifdef _LIBCPP_CXX03_LANG
+#    error Support for unspecified stability is only for C++11 and higher
+#  endif
+
+  if (!__libcpp_is_constant_evaluated())
+    std::shuffle(__first, __last, __libcpp_debug_randomizer());
+#else
+  (void)__first;
+  (void)__last;
+#endif
+}
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP___LIBCXX_DEBUG_RANDOMIZE_RANGE_H

libcxx/include/module.modulemap.in

module __iterator {
       module wrap_iter             { private header "__iterator/wrap_iter.h" }
     }
   }
   module latch {
     @requires_LIBCXX_ENABLE_THREADS@
     header "latch"
     export *
   }
+
+  module __debug_utils {
+    module randomize_range { private header "__debug_utils/randomize_range.h" }
+  }
+
   module limits {
     header "limits"
     export *
   }
   module list {
     header "list"
     export initializer_list
     export *

libcxx/test/libcxx/private_headers.verify.cpp

 #include <__concepts/same_as.h> // expected-error@*:* {{use of private header from outside its module: '__concepts/same_as.h'}}
 #include <__concepts/semiregular.h> // expected-error@*:* {{use of private header from outside its module: '__concepts/semiregular.h'}}
 #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 <__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 <__errc> // expected-error@*:* {{use of private header from outside its module: '__errc'}}
 #include <__filesystem/copy_options.h> // expected-error@*:* {{use of private header from outside its module: '__filesystem/copy_options.h'}}
 #include <__filesystem/directory_entry.h> // expected-error@*:* {{use of private header from outside its module: '__filesystem/directory_entry.h'}}
 #include <__filesystem/directory_iterator.h> // expected-error@*:* {{use of private header from outside its module: '__filesystem/directory_iterator.h'}}
 #include <__filesystem/directory_options.h> // expected-error@*:* {{use of private header from outside its module: '__filesystem/directory_options.h'}}
 #include <__filesystem/file_status.h> // expected-error@*:* {{use of private header from outside its module: '__filesystem/file_status.h'}}
 #include <__filesystem/file_time_type.h> // expected-error@*:* {{use of private header from outside its module: '__filesystem/file_time_type.h'}}
 #include <__filesystem/file_type.h> // expected-error@*:* {{use of private header from outside its module: '__filesystem/file_type.h'}}