Page MenuHomePhabricator

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

Authored by Quuxplusone on Nov 17 2021, 7:31 PM.



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.

Diff Detail

Event Timeline

Quuxplusone requested review of this revision.Nov 17 2021, 7:31 PM
Quuxplusone created this revision.
Herald added 1 blocking reviewer(s): Restricted Project. · View Herald Transcript
nilayvaish accepted this revision.Nov 17 2021, 8:06 PM

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

So I was writiing 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
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);

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. ;)

ldionne accepted this revision.Nov 18 2021, 8:00 AM
This revision is now accepted and ready to land.Nov 18 2021, 8:00 AM

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