Page MenuHomePhabricator

[libc++][ranges] Implement ranges::binary_search and ranges::{lower, upper}_bound
ClosedPublic

Authored by philnik on Mar 17 2022, 2:52 PM.

Diff Detail

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes
Herald added a project: Restricted Project. · View Herald TranscriptMar 17 2022, 2:52 PM
Herald added a subscriber: mgorny. · View Herald Transcript
philnik requested review of this revision.Mar 17 2022, 2:52 PM
Herald added a project: Restricted Project. · View Herald TranscriptMar 17 2022, 2:52 PM
Herald added a reviewer: Restricted Project. · View Herald Transcript
var-const requested changes to this revision.Mar 23 2022, 6:16 PM
var-const added inline comments.
libcxx/docs/Status/RangesAlgorithms.csv
13–15

Can you please add a link to this patch?

libcxx/include/__algorithm/ranges_lower_bound.h
37

I think for consistency with other patches, it should use longer names (_Iterator, etc.).

42

Nit: can you split this function into ~3 logical blocks? I find it a little hard(er) to read as a monolithic block of code. I'd suggest a blank line before while (to separate the initial setup from the main part), before the return statement (similarly to make the main part stand out), and either before or after the call to std::advance.

libcxx/include/__algorithm/ranges_upper_bound.h
39

Nit: similar to another patch, can you name this lambda something like __comp_lhs_rhs_swapped? (or just __comp_swapped)

libcxx/test/std/algorithms/alg.sorting/alg.binary.search/binary.search/ranges.binary_search.pass.cpp
3

(please note that many comments in this file apply to other test files as well)

72

Similar to another patch, it probably makes sense to test that the comparator works when:

  • it takes the arguments by non-const lvalue;
  • its operator() is not const;
  • it returns something convertible to bool.
133

I'd add tests for:

  • 1 element range (too small to meaningfully divide in half);
  • even number of elements;
  • odd number of elements;
  • the searched-for element is the first one;
  • the searched-for element is the last one;
  • all elements other than the searched-for element are equal.
178

Please add return 0.

libcxx/test/std/algorithms/alg.sorting/alg.binary.search/upper.bound/ranges.upper_bound.pass.cpp
66

Optional: perhaps check the return type here as well?

This revision now requires changes to proceed.Mar 23 2022, 6:16 PM
var-const added inline comments.Mar 23 2022, 6:31 PM
libcxx/include/__algorithm/ranges_lower_bound.h
39

Have you considered sharing the implementation of the algorithm between the ranges and non-ranges versions? This algorithm, while not very complicated, isn't trivial and is quite prone to off-by-one errors. Personally, I'm on the fence.

(cc'ing @ldionne as well)

philnik updated this revision to Diff 422859.Apr 14 2022, 7:11 AM
philnik marked 9 inline comments as done.
  • Address comments
philnik added inline comments.Apr 14 2022, 7:11 AM
libcxx/include/__algorithm/ranges_lower_bound.h
39

Yes, but I think it's simple enough to not warrant sharing the implementation, but I'm on the fence too.

libcxx/test/std/algorithms/alg.sorting/alg.binary.search/binary.search/ranges.binary_search.pass.cpp
72

I'll add the convertible to bool tests once D122011 landed. Taking only non-const lvalues doesn't model indirect_strict_weak_order.

philnik updated this revision to Diff 424728.Apr 23 2022, 9:32 AM
  • Rebased
  • Fix linters

In general looks good, but some remarks.

libcxx/include/CMakeLists.txt
92

Were these files not already in CMakeLists.txt?

libcxx/test/std/algorithms/alg.sorting/alg.binary.search/binary.search/ranges.binary_search.pass.cpp
63

assert(base(ret)); looks wrong, I expect this should be assert(ret);

164

Please add some tests for the complexity requirements for comparisons and projections.
The same for lower_bound and upper_bound.

philnik marked 2 inline comments as done.Apr 24 2022, 8:43 AM
philnik added inline comments.
libcxx/include/CMakeLists.txt
92

I guess you mean the find things? Must have been a merge conflict.

libcxx/test/std/algorithms/alg.sorting/alg.binary.search/binary.search/ranges.binary_search.pass.cpp
164

How exactly would you like them to look like? The standard says that the complexity is log_2(last - first) + O(1) How could I (without a statistical analysis) find out what the constant is?

philnik updated this revision to Diff 424786.Apr 24 2022, 8:43 AM
philnik marked an inline comment as done.
  • Address comments
var-const accepted this revision as: var-const.Apr 27 2022, 7:02 PM

LGTM. Please check with @ldionne regarding whether it's best to share the implementation of the algorithm with the non-ranges version.

Mordante accepted this revision.Apr 28 2022, 8:29 AM

LGTM! But please address @var-const's request before landing.

libcxx/include/__algorithm/ranges_lower_bound.h
39

I don't have a strong opinion whether to combine these two versions or keep them separate. std::invoke requires C++17, but our implementation of std::invoke uses std::__invoke requires C++11. So it seems to be an issue to use invoke on C++03.

libcxx/test/std/algorithms/alg.sorting/alg.binary.search/binary.search/ranges.binary_search.pass.cpp
164

Good point O(1) makes it hard :-( std::search's O(1) can differ from std::lower_bound's O(1).

This revision is now accepted and ready to land.Apr 28 2022, 8:29 AM
philnik updated this revision to Diff 427083.May 4 2022, 11:31 AM
  • Try to fix GCC

Sorry for being MIA, but I do have a few comments. Some of them may apply to algorithms that we've shipped previously as well.

libcxx/include/__algorithm/ranges_lower_bound.h
39

I would really like to share this with the implementation in <__algorithm/__lower_bound.h>. I suspect it's not too difficult to do that, and we'll avoid duplicating code.

41

Shouldn't this be ranges::distance?

libcxx/include/__algorithm/ranges_upper_bound.h
50

Should we be forwarding __lhs and __rhs? I think we're not losing anything if we do it, and I suspect we might be required to (if so, then we're also missing a test case).

51

This is not ADL-proof. Same above. I think we should have ADL proofing tests for ranges algorithms.

philnik updated this revision to Diff 431042.May 20 2022, 1:38 PM
philnik marked 8 inline comments as done.
  • Address comments
libcxx/include/__algorithm/ranges_upper_bound.h
50

indirect_strict_weak_order requires that _Comp is equality preserving (meaning that cv ref qualifications still give the same output) and it's callable with l- and rvalues, so only the const-ness has to stay (unless I missed some requirement). Because of this I see no reason to make the code harder to read. I think this should actually just be auto& __lhs, auto& __rhs.

51

The design of projected isn't ADL-proof, so we can't add tests. If you want more context see https://wg21.link/P2538.

philnik added inline comments.May 20 2022, 1:40 PM
libcxx/include/__algorithm/ranges_upper_bound.h
50

Ignore the last part. Using auto& would just make the implementation weirder.

philnik updated this revision to Diff 431180.May 21 2022, 3:06 PM
  • Try to fix CI
philnik updated this revision to Diff 432066.May 25 2022, 11:53 AM
  • Try to fix CI
philnik updated this revision to Diff 432217.May 26 2022, 1:52 AM
  • Next try
philnik updated this revision to Diff 433724.Jun 2 2022, 5:43 AM
  • Rebased
  • Add benchmark
ldionne accepted this revision.Jun 2 2022, 9:16 AM

LGTM with my comments addressed. I don't think I need to see this again whatever you do for the auto const& issue.

libcxx/include/__algorithm/equal_range.h
54

Can you please make sure that we have a test for the STL classic algorithms that will fail if you make a copy of __comp here? You can just add auto __dummy = __comp; (void)__dummy; to test it.

libcxx/include/__algorithm/lower_bound.h
47–48

Can you please add a libc++ specific test to check that we diagnose if you pass something that isn't a proper function object to lower_bound (and the other algorithms in this patch too), please?

libcxx/include/__algorithm/ranges_upper_bound.h
50

If it's true that cv-qualification doesn't matter, perhaps we should make this auto const& instead? That definitely removes a mental burden when reading this sort of code, IMO.

philnik updated this revision to Diff 434332.Jun 5 2022, 9:18 AM
philnik marked 3 inline comments as done.
  • Address comments
libcxx/include/__algorithm/equal_range.h
54

We've got libcxx/algorithms/robust_against_copying_comparators.pass.cpp.

philnik updated this revision to Diff 434344.Jun 5 2022, 12:15 PM
  • Try to fix CI
EricWF added a subscriber: EricWF.Sat, Jun 11, 7:59 AM

Amazing tests. Unfortunately, this change causes breakages in std::lower_bound because ranges::distance is not a drop-in replacement for std::distance, and that breaks existing code as it switches between C++17 and C++20.
I'm working on minimizing a reproducer.

libcxx/test/std/algorithms/alg.sorting/alg.binary.search/binary.search/ranges.binary_search.pass.cpp
8

Great tests BTW.