[libc++] Forward ranges::sort to instantiations in the dylib

[philnik]

Summary

This patch removes _WrapAlgPolicy and related functionality. Instead, we explicitly forward to __sort now if we have an instantiation inside the dylib. If we don't we just call __introsort.

[philnik]

Try to fix CI

[philnik]

Next try

[ldionne]

I generally like this change, but I think we want to clean up the situation with __sort5 and friends before we do it.

libcxx/src/algorithm.cpp

13–17

Basically, don't rely on the (way too subtle) trick where you're avoiding deadly recursion because you're passing the third template argument to __sort.

36–43

I don't think these symbols could actually be called previously, because they are only used from __sort, which is in the dylib as well.

I would actually start with that patch since it'll simplify the rest of this patch. I would not ship this in LLVM 16 though, to give us a bit of time to find potential issues with it.

[philnik]

Address comments

[ldionne]

This is awesome! This is a big simplification, thanks for working on it!

libcxx/include/__algorithm/sort.h

108–109

839–840

libcxx/src/algorithm.cpp

25–26

I would keep them aligned cause it's just a list of things, and use // clang-format off if needed.

[var-const]

@philnik Thank you for the clean-up!

libcxx/include/__algorithm/sort.h

 #include <__debug>
 #include <__debug_utils/randomize_range.h>
 #include <__functional/operations.h>
 #include <__functional/ranges_operations.h>
 #include <__iterator/iterator_traits.h>
 #include <__memory/destruct_n.h>
 #include <__memory/unique_ptr.h>
 #include <__type_traits/conditional.h>
+#include <__type_traits/disjunction.h>
 #include <__type_traits/is_arithmetic.h>
 #include <__utility/move.h>
 #include <__utility/pair.h>
 #include <climits>
 #include <cstdint>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
-// Wraps an algorithm policy tag and a comparator in a single struct, used to pass the policy tag around without
-// changing the number of template arguments (to keep the ABI stable). This is only used for the "range" policy tag.
-//
-// To create an object of this type, use `_WrapAlgPolicy<T, C>::type` -- see the specialization below for the rationale.
-template <class _PolicyT, class _CompT, class = void>
-struct _WrapAlgPolicy {
-  using type = _WrapAlgPolicy;
-
-  using _AlgPolicy = _PolicyT;
-  using _Comp = _CompT;
-  _Comp& __comp;
-
-  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14
-  _WrapAlgPolicy(_Comp& __c) : __comp(__c) {}
-};
-
-// Specialization for the "classic" policy tag that avoids creating a struct and simply defines an alias for the
-// comparator. When unwrapping, a pristine comparator is always considered to have the "classic" tag attached. Passing
-// the pristine comparator where possible allows using template instantiations from the dylib.
-template <class _PolicyT, class _CompT>
-struct _WrapAlgPolicy<_PolicyT, _CompT, __enable_if_t<std::is_same<_PolicyT, _ClassicAlgPolicy>::value> > {
-  using type = _CompT;
-};
-
-// Unwraps a pristine functor (e.g. `std::less`) as if it were wrapped using `_WrapAlgPolicy`. The policy tag is always
-// set to "classic".
-template <class _CompT>
-struct _UnwrapAlgPolicy {
-  using _AlgPolicy = _ClassicAlgPolicy;
-  using _Comp = _CompT;
-
-  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 static
-  _Comp __get_comp(_Comp __comp) { return __comp; }
-};
-
-// Unwraps a `_WrapAlgPolicy` struct.
-template <class... _Ts>
-struct _UnwrapAlgPolicy<_WrapAlgPolicy<_Ts...> > {
-  using _Wrapped = _WrapAlgPolicy<_Ts...>;
-  using _AlgPolicy = typename _Wrapped::_AlgPolicy;
-  using _Comp = typename _Wrapped::_Comp;
-
-  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 static
-  _Comp __get_comp(_Wrapped& __w) { return __w.__comp; }
-};
-
 // stable, 2-3 compares, 0-2 swaps
 
 template <class _AlgPolicy, class _Compare, class _ForwardIterator>
 _LIBCPP_HIDE_FROM_ABI
 _LIBCPP_CONSTEXPR_SINCE_CXX14 unsigned __sort3(_ForwardIterator __x, _ForwardIterator __y, _ForwardIterator __z,
                                                _Compare __c) {
   using _Ops = _IterOps<_AlgPolicy>;
 
if (__c(*__x3, *__x2)) {
       }
     }
   }
   return __r;
 }
 
 // stable, 4-10 compares, 0-9 swaps
 
-template <class _WrappedComp, class _ForwardIterator>
-_LIBCPP_HIDDEN unsigned __sort5(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3,
-                                _ForwardIterator __x4, _ForwardIterator __x5, _WrappedComp __wrapped_comp) {
-  using _Unwrap = _UnwrapAlgPolicy<_WrappedComp>;
-  using _AlgPolicy = typename _Unwrap::_AlgPolicy;
+template <class _AlgPolicy, class _Comp, class _ForwardIterator>
+_LIBCPP_HIDE_FROM_ABI unsigned __sort5(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3,
+                                _ForwardIterator __x4, _ForwardIterator __x5, _Comp __comp) {
   using _Ops = _IterOps<_AlgPolicy>;
 
-  using _Compare = typename _Unwrap::_Comp;
-  _Compare __c = _Unwrap::__get_comp(__wrapped_comp);
-
-  unsigned __r = std::__sort4<_AlgPolicy, _Compare>(__x1, __x2, __x3, __x4, __c);
-  if (__c(*__x5, *__x4)) {
+  unsigned __r = std::__sort4<_AlgPolicy, _Comp>(__x1, __x2, __x3, __x4, __comp);
+  if (__comp(*__x5, *__x4)) {
     _Ops::iter_swap(__x4, __x5);
     ++__r;
-    if (__c(*__x4, *__x3)) {
+    if (__comp(*__x4, *__x3)) {
       _Ops::iter_swap(__x3, __x4);
       ++__r;
-      if (__c(*__x3, *__x2)) {
+      if (__comp(*__x3, *__x2)) {
         _Ops::iter_swap(__x2, __x3);
         ++__r;
-        if (__c(*__x2, *__x1)) {
+        if (__comp(*__x2, *__x1)) {
           _Ops::iter_swap(__x1, __x2);
           ++__r;
         }
       }
     }
   }
   return __r;
 }
 
-template <class _AlgPolicy, class _Compare, class _ForwardIterator>
-_LIBCPP_HIDE_FROM_ABI unsigned __sort5_wrap_policy(
-    _ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3, _ForwardIterator __x4, _ForwardIterator __x5,
-    _Compare __c) {
-  using _WrappedComp = typename _WrapAlgPolicy<_AlgPolicy, _Compare>::type;
-  _WrappedComp __wrapped_comp(__c);
-  return std::__sort5<_WrappedComp, _ForwardIterator>(
-      std::move(__x1), std::move(__x2), std::move(__x3), std::move(__x4), std::move(__x5), __wrapped_comp);
-}
-
 // The comparator being simple is a prerequisite for using the branchless optimization.
 template <class _Tp>
 struct __is_simple_comparator : false_type {};
 template <class _Tp>
 struct __is_simple_comparator<__less<_Tp>&> : true_type {};
 template <class _Tp>
 struct __is_simple_comparator<less<_Tp>&> : true_type {};
 template <class _Tp>
__sort5_maybe_branchless(
   std::__partially_sorted_swap<_Compare>(__x1, __x3, __x4, __c);
   std::__partially_sorted_swap<_Compare>(__x2, __x3, __x4, __c);
 }
 
 template <class _AlgPolicy, class _Compare, class _RandomAccessIterator>
 inline _LIBCPP_HIDE_FROM_ABI __enable_if_t<!__use_branchless_sort<_Compare, _RandomAccessIterator>::value, void>
 __sort5_maybe_branchless(_RandomAccessIterator __x1, _RandomAccessIterator __x2, _RandomAccessIterator __x3,
                          _RandomAccessIterator __x4, _RandomAccessIterator __x5, _Compare __c) {
-  std::__sort5_wrap_policy<_AlgPolicy, _Compare>(__x1, __x2, __x3, __x4, __x5, __c);
+  std::__sort5<_AlgPolicy, _Compare, _RandomAccessIterator>(
+      std::move(__x1), std::move(__x2), std::move(__x3), std::move(__x4), std::move(__x5), __c);
 }
 
 // Assumes size > 0
 template <class _AlgPolicy, class _Compare, class _BidirectionalIterator>
 _LIBCPP_HIDE_FROM_ABI
 _LIBCPP_CONSTEXPR_SINCE_CXX14 void __selection_sort(_BidirectionalIterator __first, _BidirectionalIterator __last,
                                                     _Compare __comp) {
   _BidirectionalIterator __lm1 = __last;
if (__comp(*__i, *__j)) {
         *__j = _Ops::__iter_move(__k);
         __j = __k;
       } while (__comp(__t, *--__k)); // No need for bounds check due to the assumption stated above.
       *__j = std::move(__t);
     }
   }
 }
 
-template <class _WrappedComp, class _RandomAccessIterator>
-_LIBCPP_HIDDEN bool __insertion_sort_incomplete(
-    _RandomAccessIterator __first, _RandomAccessIterator __last, _WrappedComp __wrapped_comp) {
-  using _Unwrap = _UnwrapAlgPolicy<_WrappedComp>;
-  using _AlgPolicy = typename _Unwrap::_AlgPolicy;
+template <class _AlgPolicy, class _Comp, class _RandomAccessIterator>
+_LIBCPP_HIDE_FROM_ABI bool __insertion_sort_incomplete(
+    _RandomAccessIterator __first, _RandomAccessIterator __last, _Comp __comp) {
   using _Ops = _IterOps<_AlgPolicy>;
 
-  using _Compare = typename _Unwrap::_Comp;
-  _Compare __comp = _Unwrap::__get_comp(__wrapped_comp);
-
   typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
   switch (__last - __first) {
   case 0:
   case 1:
     return true;
   case 2:
     if (__comp(*--__last, *__first))
       _Ops::iter_swap(__first, __last);
     return true;
   case 3:
-    std::__sort3_maybe_branchless<_AlgPolicy, _Compare>(__first, __first + difference_type(1), --__last, __comp);
+    std::__sort3_maybe_branchless<_AlgPolicy, _Comp>(__first, __first + difference_type(1), --__last, __comp);
     return true;
   case 4:
-    std::__sort4_maybe_branchless<_AlgPolicy, _Compare>(
+    std::__sort4_maybe_branchless<_AlgPolicy, _Comp>(
         __first, __first + difference_type(1), __first + difference_type(2), --__last, __comp);
     return true;
   case 5:
-    std::__sort5_maybe_branchless<_AlgPolicy, _Compare>(
+    std::__sort5_maybe_branchless<_AlgPolicy, _Comp>(
         __first, __first + difference_type(1), __first + difference_type(2), __first + difference_type(3),
         --__last, __comp);
     return true;
   }
   typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
   _RandomAccessIterator __j = __first + difference_type(2);
-  std::__sort3_maybe_branchless<_AlgPolicy, _Compare>(__first, __first + difference_type(1), __j, __comp);
+  std::__sort3_maybe_branchless<_AlgPolicy, _Comp>(__first, __first + difference_type(1), __j, __comp);
   const unsigned __limit = 8;
   unsigned __count = 0;
   for (_RandomAccessIterator __i = __j + difference_type(1); __i != __last; ++__i) {
     if (__comp(*__i, *__j)) {
       value_type __t(_Ops::__iter_move(__i));
       _RandomAccessIterator __k = __j;
       __j = __i;
       do {
while (true) {
     auto __ret =
         _UseBitSetPartition
             ? std::__bitset_partition<_AlgPolicy, _RandomAccessIterator, _Compare>(__first, __last, __comp)
             : std::__partition_with_equals_on_right<_AlgPolicy, _RandomAccessIterator, _Compare>(__first, __last, __comp);
     _RandomAccessIterator __i = __ret.first;
     // [__first, __i) < *__i and *__i <= [__i+1, __last)
     // If we were given a perfect partition, see if insertion sort is quick...
     if (__ret.second) {
-      using _WrappedComp = typename _WrapAlgPolicy<_AlgPolicy, _Compare>::type;
-      _WrappedComp __wrapped_comp(__comp);
-      bool __fs = std::__insertion_sort_incomplete<_WrappedComp>(__first, __i, __wrapped_comp);
-      if (std::__insertion_sort_incomplete<_WrappedComp>(__i + difference_type(1), __last, __wrapped_comp)) {
+      bool __fs = std::__insertion_sort_incomplete<_AlgPolicy, _Compare>(__first, __i, __comp);
+      if (std::__insertion_sort_incomplete<_AlgPolicy, _Compare>(__i + difference_type(1), __last, __comp)) {
         if (__fs)
           return;
         __last = __i;
         continue;
       } else {
         if (__fs) {
           __first = ++__i;
           continue;
inline _LIBCPP_HIDE_FROM_ABI _Number __log2i(_Number __n) {
   _Number __log2 = 0;
   while (__n > 1) {
     __log2++;
     __n >>= 1;
   }
   return __log2;
 }
 
 template <class _WrappedComp, class _RandomAccessIterator>
-_LIBCPP_HIDDEN void __sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _WrappedComp __wrapped_comp) {
-  typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
-  difference_type __depth_limit = 2 * std::__log2i(__last - __first);
-
-  using _Unwrap = _UnwrapAlgPolicy<_WrappedComp>;
-  using _AlgPolicy = typename _Unwrap::_AlgPolicy;
-  using _Compare = typename _Unwrap::_Comp;
-  _Compare __comp = _Unwrap::__get_comp(__wrapped_comp);
-  // Only use bitset partitioning for arithmetic types.  We should also check
-  // that the default comparator is in use so that we are sure that there are no
-  // branches in the comparator.
-  std::__introsort<_AlgPolicy,
-                   _Compare,
-                   _RandomAccessIterator,
-                   __use_branchless_sort<_Compare, _RandomAccessIterator>::value>(
-      __first, __last, __comp, __depth_limit);
-}
-
-template <class _Compare, class _Tp>
-inline _LIBCPP_INLINE_VISIBILITY void __sort(_Tp** __first, _Tp** __last, __less<_Tp*>&) {
-  __less<uintptr_t> __comp;
-  std::__sort<__less<uintptr_t>&, uintptr_t*>((uintptr_t*)__first, (uintptr_t*)__last, __comp);
-}
+void __sort(_RandomAccessIterator, _RandomAccessIterator, _WrappedComp);
 
 extern template _LIBCPP_FUNC_VIS void __sort<__less<char>&, char*>(char*, char*, __less<char>&);
 #ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS
 extern template _LIBCPP_FUNC_VIS void __sort<__less<wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, __less<wchar_t>&);
 #endif
 extern template _LIBCPP_FUNC_VIS void __sort<__less<signed char>&, signed char*>(signed char*, signed char*, __less<signed char>&);
 extern template _LIBCPP_FUNC_VIS void __sort<__less<unsigned char>&, unsigned char*>(unsigned char*, unsigned char*, __less<unsigned char>&);
 extern template _LIBCPP_FUNC_VIS void __sort<__less<short>&, short*>(short*, short*, __less<short>&);
 extern template _LIBCPP_FUNC_VIS void __sort<__less<unsigned short>&, unsigned short*>(unsigned short*, unsigned short*, __less<unsigned short>&);
 extern template _LIBCPP_FUNC_VIS void __sort<__less<int>&, int*>(int*, int*, __less<int>&);
 extern template _LIBCPP_FUNC_VIS void __sort<__less<unsigned>&, unsigned*>(unsigned*, unsigned*, __less<unsigned>&);
 extern template _LIBCPP_FUNC_VIS void __sort<__less<long>&, long*>(long*, long*, __less<long>&);
 extern template _LIBCPP_FUNC_VIS void __sort<__less<unsigned long>&, unsigned long*>(unsigned long*, unsigned long*, __less<unsigned long>&);
 extern template _LIBCPP_FUNC_VIS void __sort<__less<long long>&, long long*>(long long*, long long*, __less<long long>&);
 extern template _LIBCPP_FUNC_VIS void __sort<__less<unsigned long long>&, unsigned long long*>(unsigned long long*, unsigned long long*, __less<unsigned long long>&);
 extern template _LIBCPP_FUNC_VIS void __sort<__less<float>&, float*>(float*, float*, __less<float>&);
 extern template _LIBCPP_FUNC_VIS void __sort<__less<double>&, double*>(double*, double*, __less<double>&);
 extern template _LIBCPP_FUNC_VIS void __sort<__less<long double>&, long double*>(long double*, long double*, __less<long double>&);
 
-extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<char>&, char*>(char*, char*, __less<char>&);
+template <class _AlgPolicy, class _RandomAccessIterator, class _Comp>
+_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void
+__sort_dispatch(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp& __comp) {
+  typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
+  difference_type __depth_limit = 2 * std::__log2i(__last - __first);
+
+  // Only use bitset partitioning for arithmetic types.  We should also check
+  // that the default comparator is in use so that we are sure that there are no
+  // branches in the comparator.
+  std::__introsort<_AlgPolicy,
+                   _Comp&,
+                   _RandomAccessIterator,
+                   __use_branchless_sort<_Comp, _RandomAccessIterator>::value>(
+      __first, __last, __comp, __depth_limit);
+}
+
+template <class _Type, class... _Options>
+using __is_any_of = _Or<is_same<_Type, _Options>...>;
+
+template <class _Type>
+using __sort_is_specialized_in_library = __is_any_of<
+    _Type,
+    char,
 #ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS
-extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, __less<wchar_t>&);
+    wchar_t,
+#endif
+    signed char,
+    unsigned char,
+    short,
+    unsigned short,
+    int,
+    unsigned int,
+    long,
+    unsigned long,
+    long long,
+    unsigned long long,
+    float,
+    double,
+    long double>;
+
+template <class _AlgPolicy, class _Type, __enable_if_t<__sort_is_specialized_in_library<_Type>::value, int> = 0>
+_LIBCPP_HIDE_FROM_ABI void __sort_dispatch(_Type* __first, _Type* __last, __less<_Type>& __comp) {
+  std::__sort<__less<_Type>&, _Type*>(__first, __last, __comp);
+}
+
+template <class _AlgPolicy, class _Type, __enable_if_t<__sort_is_specialized_in_library<_Type>::value, int> = 0>
+_LIBCPP_HIDE_FROM_ABI void __sort_dispatch(_Type* __first, _Type* __last, less<_Type>&) {
+  __less<_Type> __comp;
+  std::__sort<__less<_Type>&, _Type*>(__first, __last, __comp);
+}
+
+#if _LIBCPP_STD_VER >= 14
+template <class _AlgPolicy, class _Type, __enable_if_t<__sort_is_specialized_in_library<_Type>::value, int> = 0>
+_LIBCPP_HIDE_FROM_ABI void __sort_dispatch(_Type* __first, _Type* __last, less<>&) {
+  __less<_Type> __comp;
+  std::__sort<__less<_Type>&, _Type*>(__first, __last, __comp);
+}
 #endif
-extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<signed char>&, signed char*>(signed char*, signed char*, __less<signed char>&);
-extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned char>&, unsigned char*>(unsigned char*, unsigned char*, __less<unsigned char>&);
-extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<short>&, short*>(short*, short*, __less<short>&);
-extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned short>&, unsigned short*>(unsigned short*, unsigned short*, __less<unsigned short>&);
-extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<int>&, int*>(int*, int*, __less<int>&);
-extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned>&, unsigned*>(unsigned*, unsigned*, __less<unsigned>&);
-extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<long>&, long*>(long*, long*, __less<long>&);
-extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned long>&, unsigned long*>(unsigned long*, unsigned long*, __less<unsigned long>&);
-extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<long long>&, long long*>(long long*, long long*, __less<long long>&);
-extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned long long>&, unsigned long long*>(unsigned long long*, unsigned long long*, __less<unsigned long long>&);
-extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<float>&, float*>(float*, float*, __less<float>&);
-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>&);
+#if _LIBCPP_STD_VER >= 20
+template <class _AlgPolicy, class _Type, __enable_if_t<__sort_is_specialized_in_library<_Type>::value, int> = 0>
+_LIBCPP_HIDE_FROM_ABI void __sort_dispatch(_Type* __first, _Type* __last, ranges::less&) {
+  __less<_Type> __comp;
+  std::__sort<__less<_Type>&, _Type*>(__first, __last, __comp);
+}
+#endif
 
 template <class _AlgPolicy, class _RandomAccessIterator, class _Comp>
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
 void __sort_impl(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp& __comp) {
   std::__debug_randomize_range<_AlgPolicy>(__first, __last);
 
-  using _Comp_ref = __comp_ref_type<_Comp>;
   if (__libcpp_is_constant_evaluated()) {
     std::__partial_sort<_AlgPolicy>(__first, __last, __last, __comp);
-
   } else {
-    using _WrappedComp = typename _WrapAlgPolicy<_AlgPolicy, _Comp_ref>::type;
-    _Comp_ref __comp_ref(__comp);
-    _WrappedComp __wrapped_comp(__comp_ref);
-    std::__sort<_WrappedComp>(std::__unwrap_iter(__first), std::__unwrap_iter(__last), __wrapped_comp);
+    std::__sort_dispatch<_AlgPolicy>(__first, __last, __comp);
   }
 }
 
 template <class _RandomAccessIterator, class _Comp>
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
 void sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp __comp) {
   std::__sort_impl<_ClassicAlgPolicy>(std::move(__first), std::move(__last), __comp);
 }

libcxx/src/algorithm.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
 //
 //===----------------------------------------------------------------------===//
 
 #include <algorithm>
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
-// TODO(varconst): this currently doesn't benefit `ranges::sort` because it uses `ranges::less` instead of `__less`.
+template <class Comp, class RandomAccessIterator>
+void __sort(RandomAccessIterator first, RandomAccessIterator last, Comp comp) {
+  std::__sort_dispatch<_ClassicAlgPolicy, RandomAccessIterator, Comp>(first, last, comp);
+}
 
 template void __sort<__less<char>&, char*>(char*, char*, __less<char>&);
 #ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS
 template void __sort<__less<wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, __less<wchar_t>&);
 #endif
 template void __sort<__less<signed char>&, signed char*>(signed char*, signed char*, __less<signed char>&);
 template void __sort<__less<unsigned char>&, unsigned char*>(unsigned char*, unsigned char*, __less<unsigned char>&);
 template void __sort<__less<short>&, short*>(short*, short*, __less<short>&);
 template void __sort<__less<unsigned short>&, unsigned short*>(unsigned short*, unsigned short*, __less<unsigned short>&);
 template void __sort<__less<int>&, int*>(int*, int*, __less<int>&);
 template void __sort<__less<unsigned>&, unsigned*>(unsigned*, unsigned*, __less<unsigned>&);
 template void __sort<__less<long>&, long*>(long*, long*, __less<long>&);
 template void __sort<__less<unsigned long>&, unsigned long*>(unsigned long*, unsigned long*, __less<unsigned long>&);
 template void __sort<__less<long long>&, long long*>(long long*, long long*, __less<long long>&);
 template void __sort<__less<unsigned long long>&, unsigned long long*>(unsigned long long*, unsigned long long*, __less<unsigned long long>&);
 template void __sort<__less<float>&, float*>(float*, float*, __less<float>&);
 template void __sort<__less<double>&, double*>(double*, double*, __less<double>&);
 template void __sort<__less<long double>&, long double*>(long double*, long double*, __less<long double>&);
 
-template bool __insertion_sort_incomplete<__less<char>&, char*>(char*, char*, __less<char>&);
+// TODO: Were the __insertion_sort_incomplete and __sort5 specializations ever visible?
+
+template <class Comp, class RandomAccessIterator>
+bool __insertion_sort_incomplete(RandomAccessIterator first, RandomAccessIterator last, Comp comp) {
+  return std::__insertion_sort_incomplete<_ClassicAlgPolicy>(first, last, comp);
+}
+
+template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<char>&, char*>(char*, char*, __less<char>&);
 #ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS
-template bool __insertion_sort_incomplete<__less<wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, __less<wchar_t>&);
+template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, __less<wchar_t>&);
 #endif
-template bool __insertion_sort_incomplete<__less<signed char>&, signed char*>(signed char*, signed char*, __less<signed char>&);
-template bool __insertion_sort_incomplete<__less<unsigned char>&, unsigned char*>(unsigned char*, unsigned char*, __less<unsigned char>&);
-template bool __insertion_sort_incomplete<__less<short>&, short*>(short*, short*, __less<short>&);
-template bool __insertion_sort_incomplete<__less<unsigned short>&, unsigned short*>(unsigned short*, unsigned short*, __less<unsigned short>&);
-template bool __insertion_sort_incomplete<__less<int>&, int*>(int*, int*, __less<int>&);
-template bool __insertion_sort_incomplete<__less<unsigned>&, unsigned*>(unsigned*, unsigned*, __less<unsigned>&);
-template bool __insertion_sort_incomplete<__less<long>&, long*>(long*, long*, __less<long>&);
-template bool __insertion_sort_incomplete<__less<unsigned long>&, unsigned long*>(unsigned long*, unsigned long*, __less<unsigned long>&);
-template bool __insertion_sort_incomplete<__less<long long>&, long long*>(long long*, long long*, __less<long long>&);
-template bool __insertion_sort_incomplete<__less<unsigned long long>&, unsigned long long*>(unsigned long long*, unsigned long long*, __less<unsigned long long>&);
-template bool __insertion_sort_incomplete<__less<float>&, float*>(float*, float*, __less<float>&);
-template bool __insertion_sort_incomplete<__less<double>&, double*>(double*, double*, __less<double>&);
-template bool __insertion_sort_incomplete<__less<long double>&, long double*>(long double*, long double*, __less<long double>&);
+template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<signed char>&, signed char*>(signed char*, signed char*, __less<signed char>&);
+template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned char>&, unsigned char*>(unsigned char*, unsigned char*, __less<unsigned char>&);
+template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<short>&, short*>(short*, short*, __less<short>&);
+template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned short>&, unsigned short*>(unsigned short*, unsigned short*, __less<unsigned short>&);
+template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<int>&, int*>(int*, int*, __less<int>&);
+template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned>&, unsigned*>(unsigned*, unsigned*, __less<unsigned>&);
+template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<long>&, long*>(long*, long*, __less<long>&);
+template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned long>&, unsigned long*>(unsigned long*, unsigned long*, __less<unsigned long>&);
+template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<long long>&, long long*>(long long*, long long*, __less<long long>&);
+template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned long long>&, unsigned long long*>(unsigned long long*, unsigned long long*, __less<unsigned long long>&);
+template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<float>&, float*>(float*, float*, __less<float>&);
+template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<double>&, double*>(double*, double*, __less<double>&);
+template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<long double>&, long double*>(long double*, long double*, __less<long double>&);
+
+template <class Comp, class ForwardIterator>
+unsigned
+__sort5(ForwardIterator __x1,
+        ForwardIterator __x2,
+        ForwardIterator __x3,
+        ForwardIterator __x4,
+        ForwardIterator __x5,
+        Comp __comp) {
+  return std::__sort5<_ClassicAlgPolicy, Comp, ForwardIterator>(__x1, __x2, __x3, __x4, __x5, __comp);
+}
 
-template unsigned __sort5<__less<long double>&, long double*>(long double*, long double*, long double*, long double*, long double*, __less<long double>&);
+template _LIBCPP_FUNC_VIS unsigned __sort5<__less<long double>&, long double*>(long double*, long double*, long double*, long double*, long double*, __less<long double>&);
 
 _LIBCPP_END_NAMESPACE_STD