[libc++] Minor fixups in the new introsort code.

[• Quuxplusone]

Summary

ADL-proof. (This is a sneaky one because it exists only in a codepath that is taken for non-pointer-type iterators, so I don't think it's physically possible for robust_against_adl.pass.cpp to catch it.)
Don't copy comparators.
Don't provide explicit arguments to std::min_element (but luckily we don't need to, because we know _Compare is cheap-to-copy at this point because we're inside a double-underscored algorithm).

This should fix the issue reported on D113413 by @haowei.

[nilayvaish]

Can you explain when do we need to use _Comp_ref? Why is adding _Compare sufficient?

[nilayvaish]

So I was writiing https://reviews.llvm.org/D114135 in parallel. I have added a test which fails with out the change. I am wondering if we should add it. Error message from the failed test below:

In file included from llvm-project/build/include/c++/v1/__algorithm/nth_element.h:15,

from llvm-project/build/include/c++/v1/algorithm:714,
from llvm-project/libcxx/test/std/algorithms/alg.sorting/alg.sort/sort/sort_comp.pass.cpp:17:

llvm-project/build/include/c++/v1/__algorithm/sort.h: In instantiation of ‘void std::1::sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _Compare = unique_ptr_less<int>&; _RandomAccessIterator = int*]’:
llvm-project/build/include/c++/v1/__algorithm/sort.h:543:29: required from ‘constexpr void std::1::sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = std::1::wrap_iter<int*>; _Compare = unique_ptr_less<int>]’
llvm-project/libcxx/test/std/algorithms/alg.sorting/alg.sort/sort/sort_comp.pass.cpp:80:73: required from here
llvm-project/build/include/c++/v1/algorithm/sort.h:483:21: error: use of deleted function ‘unique_ptr_less<int>::unique_ptr_less(const unique_ptr_less<int>&)’

483 |   _VSTD::__introsort(__first, __last, __comp, __depth_limit);

[• Quuxplusone]

@nilayvaish wrote:

Can you explain when do we need to use _Comp_ref? Why is adding _Compare sufficient?

See D93562, where I wrote:

Basically, libc++ algorithms have an invariant that "_Compare is either an lvalue reference type or __debug_less<T&> (which works like reference_wrapper and is cheap to copy)." It would actually be very nice if we could just make the invariant that "_Compare is a value type that is cheap to copy (e.g. reference_wrapper<T>)," and then we'd never need to specify <_Compare> on any helper ever again...

In short, when you have a _Compare that was passed to you by the user, you need to _Comp_ref it before passing it further down. If you're already further down, like inside __introsort, then _Compare was passed to you by a higher-level libc++ function and therefore is safe to use without further _Comp_ref'ing.

In D93562 I also wrote:

We could still add a QoI test for this in libcxx/test/libcxx/; leave the comparator copyable but have it count how many times it was copied, and then assert that the number of copies was 1. I'm not volunteering.

I guess I've volunteered now. ;)

[haowei]

Thanks for working on this. It confirmed fixed the build issue we saw on our side.

libcxx/include/__algorithm/sort.h

 // Assumes size > 0
 template <class _Compare, class _BidirectionalIterator>
 _LIBCPP_CONSTEXPR_AFTER_CXX11 void
 __selection_sort(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
 {
     _BidirectionalIterator __lm1 = __last;
     for (--__lm1; __first != __lm1; ++__first)
     {
-        _BidirectionalIterator __i = _VSTD::min_element<_BidirectionalIterator, _Compare&>(__first, __last, __comp);
+        _BidirectionalIterator __i = _VSTD::min_element(__first, __last, __comp);
         if (__i != __first)
             swap(*__first, *__i);
     }
 }
 
 template <class _Compare, class _BidirectionalIterator>
 void
 __insertion_sort(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
if (__first1 != __last1)
         }
         __h.release();
     }
 }
 
 template <class _Compare, class _RandomAccessIterator>
 void
 __introsort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
-            typename _VSTD::iterator_traits<_RandomAccessIterator>::difference_type __depth)
+            typename iterator_traits<_RandomAccessIterator>::difference_type __depth)
 {
     typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
     typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
     const difference_type __limit = is_trivially_copy_constructible<value_type>::value &&
                                     is_trivially_copy_assignable<value_type>::value ? 30 : 6;
-    typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
     while (true)
     {
     __restart:
         difference_type __len = __last - __first;
         switch (__len)
         {
         case 0:
         case 1:
__restart:
         {
             _VSTD::__insertion_sort_3<_Compare>(__first, __last, __comp);
             return;
         }
         // __len > 5
         if (__depth == 0)
         {
           // Fallback to heap sort as Introsort suggests.
-          _VSTD::__partial_sort<_Comp_ref>(__first, __last, __last, _Comp_ref(__comp));
+          _VSTD::__partial_sort<_Compare>(__first, __last, __last, __comp);
           return;
         }
         --__depth;
         _RandomAccessIterator __m = __first;
         _RandomAccessIterator __lm1 = __last;
         --__lm1;
         unsigned __n_swaps;
         {
inline _LIBCPP_HIDE_FROM_ABI _Number __log2i(_Number __n) {
   }
   return __log2;
 }
 
 template <class _Compare, class _RandomAccessIterator>
 void __sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) {
   typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
   difference_type __depth_limit = 2 * __log2i(__last - __first);
-  __introsort(__first, __last, __comp, __depth_limit);
+  _VSTD::__introsort<_Compare>(__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;