Page MenuHomePhabricator

[libc++][ranges] implement `std::ranges::equal_range`
ClosedPublic

Authored by huixie90 on Jul 14 2022, 12:35 PM.

Details

Summary

[libc++][ranges] implement std::ranges::equal_range

Diff Detail

Event Timeline

huixie90 created this revision.Jul 14 2022, 12:35 PM
Herald added a project: Restricted Project. · View Herald TranscriptJul 14 2022, 12:35 PM
huixie90 updated this revision to Diff 444967.Jul 15 2022, 6:53 AM

added tests

huixie90 updated this revision to Diff 444968.Jul 15 2022, 6:54 AM

update status csv

huixie90 published this revision for review.Jul 15 2022, 6:56 AM
Herald added a project: Restricted Project. · View Herald Transcript
Herald added a reviewer: Restricted Project. · View Herald Transcript
huixie90 updated this revision to Diff 445000.Jul 15 2022, 8:47 AM

try again to fix CI

huixie90 updated this revision to Diff 445088.Jul 15 2022, 12:01 PM

try again to fix CI

huixie90 updated this revision to Diff 445304.Jul 17 2022, 1:36 AM

try again

var-const requested changes to this revision.Jul 17 2022, 1:53 AM

Thanks!

libcxx/include/__algorithm/equal_range.h
43

Why not use __make_projected? Wouldn't this cause a visible change in behavior for the classic algorithm (now accepting a pointer-to-member as the comparator)? (alternatively, you could do a static_assert(__is_callable) like in e.g. lower_bound).

52

Does this need to be forwarded, or not?

52

You probably need to pass _Compare explicitly as well, I'm not sure why it wasn't done before (_Compare is normally a reference, so type deduction would decay it to a value).

56

Nit: make_pair?

64

Why is this cast necessary, and does it work in debug mode? (when _Comp_ref is a struct)

libcxx/include/__algorithm/upper_bound.h
50

Move?

57

Please don't remove the inlines -- this could increase binary size. We plan to do some investigation and potentially make a dedicated patch to clean up these unwanted inlines.

libcxx/test/std/algorithms/alg.sorting/alg.binary.search/equal.range/ranges_equal_range.pass.cpp
40

Do these have to be forwarded as well?

55

Nit: I know it's a pattern, but perhaps we could rename this? RangeRange looks a little awkward.

71

Nit: s/N1/N/.

96

Nit: consider s/is in the middle/would be in the middle/.

120

Ultranit: s/exact/exactly/.

164

This can be omitted -- I'll merge the robust_against_dangling patch very soon.

192

Optional: share this comparator across the two test cases?

This revision now requires changes to proceed.Jul 17 2022, 1:53 AM
philnik added inline comments.Jul 17 2022, 4:36 AM
libcxx/include/__algorithm/equal_range.h
52

You don't have to (and can't really) pass _Compare explicitly. __lower_bound_impl always takes the comparator by reference instead of by value. I don't know why this hasn't been done this way before, but that makes a lot more sense that explicitly passing the template parameter around everywhere.

var-const added inline comments.Jul 17 2022, 10:18 AM
libcxx/include/__algorithm/equal_range.h
52

I think it was done that way to support _Comp_ref resolving to either a reference type (in a regular build) or a non-reference type (in a debug build). Does that not apply here?

philnik added inline comments.Jul 17 2022, 10:43 AM
libcxx/include/__algorithm/equal_range.h
52

That does apply, but why wouldn't you just pass _Comp_ref by reference? The only thing may be that passing it by value is more efficient, but I would expect the functions to be inlined anyways, so it shouldn't matter.

huixie90 updated this revision to Diff 445349.Jul 17 2022, 1:56 PM
huixie90 marked 12 inline comments as done.

address feedback

libcxx/include/__algorithm/equal_range.h
43

__make_projected cannot be used here because the __comp takes two arguments but we only want to apply __proj to only one of arguments. And tricky thing is sometimes we want to apply __proj for the first argument (see line above) and sometimes we want to apply __proj to the second argument (see few lines below).

It is just much easier to pass in the comp and proj and explicitly write how to apply the projection. I will add static_assert

52

re "Does this need to be forwarded, or not?"
I think it is not. the same expression used the variables twice and you cannot decide which one is executed first so forwarding them just introduces possibility of use-after-move

re pass _Compare explicitly, I agree with @philnik , we shouldn't explicit specify the template argument here and should let it deduced. would decay it to a value is not correct anymore as both functions take arguments by reference.

Actually "explicit specifying the template argument creates problems". My intent of __upper_bound is taking comp by forwarding reference, but explicitly specifying the template arguments makes it pass by rvalue reference. (which triggers some ci failure)

56

Extra nit nit: make_pair in c++03 does extra copies. since it is similar readability, perhaps just leave it as it is? (the original code on the left uses the constructor)

64

I added static_cast to fix a CI failure but it was in the wrong place. The problem is the one I explained above. In debug mode, the _Comp_ref is debug_less and the __equal_range deduced _Compare to debug_less . then later, it calls __upper_bound<policy, _Compare>
However, __upper_bound meant to take __comp by forwarding reference T&&. But by explicitly specifying the template argument _Compare, it changes the meaning and makes it take the rvalue-reference debug_less&&. But in the context of __equal_range, __comp is an l-value expression of type debug_less&&. And an lvalue cannot be bond to an r-value reference input, thus caused failure.

So we should not really explicit specifying template arguments now as most algorithms takes _Compare by reference (either lvalue reference or forwarding reference). and explicit writing the type can only cause harm.

It was useful in the past because they used to take _Compare by value. But now we are trying our best not to make copies so _Compare are mostly passed by references. If the passing-by-reference causes performance regression, we should revisit all the algorithms. But explicit writing the template argument does not help because you cannot stop them being passed by reference

Here I will just remove the explicit template argument and leave the static_cast. In normal build it does nothing because it casts an l-value to an lvalue reference. In debug mode, it will construct the temporary debug_less struct

huixie90 updated this revision to Diff 445431.Jul 18 2022, 2:31 AM

update one more caller

var-const accepted this revision.Jul 19 2022, 7:51 PM
var-const added inline comments.
libcxx/include/__algorithm/equal_range.h
64

Hmm, using an rvalue reference as the argument type looks promising. The _Comp_ref quirk makes things pretty inconvenient, in the future it would be great to clean it up as much as possible without losing the functionality.

libcxx/include/__algorithm/upper_bound.h
60

@philnik has previously pointed out in one of my patches that this could make the classic algorithm more permissive than mandated by the standard by accepting move-only iterator types. FWIW, I worked around that by adding a static_assert(is_copy_constructible<>::value).

Feel free to address in a follow-up.

This revision is now accepted and ready to land.Jul 19 2022, 7:51 PM
huixie90 updated this revision to Diff 446268.Jul 20 2022, 2:38 PM
huixie90 marked an inline comment as done.

add static_assert

huixie90 updated this revision to Diff 446271.Jul 20 2022, 2:48 PM

fix merge conflicts

I think the CI failure is unrelated and was fixed in main, so rebasing would hopefully fix it.

var-const accepted this revision.Jul 20 2022, 11:09 PM
var-const accepted this revision.Jul 22 2022, 1:40 AM
This revision was automatically updated to reflect the committed changes.