This is an archive of the discontinued LLVM Phabricator instance.

[libc++][ranges] Implement ranges::max
ClosedPublic

Authored by philnik on Mar 18 2022, 5:53 AM.

Details

Diff Detail

Event Timeline

philnik created this revision.Mar 18 2022, 5:53 AM
Herald added a project: Restricted Project. · View Herald TranscriptMar 18 2022, 5:53 AM
Herald added a subscriber: mgorny. · View Herald Transcript
philnik requested review of this revision.Mar 18 2022, 5:53 AM
Herald added a project: Restricted Project. · View Herald TranscriptMar 18 2022, 5:53 AM
Herald added a reviewer: Restricted Project. · View Herald Transcript

In general looks good, but several small issues.

libcxx/include/__algorithm/ranges_max.h
52

I don't like the name __comp2 has no meaning. How about __comp_lhs_rhs_swapped.
That name give a hint what's about to happen and it makes easier to understand why __min_element_impl is used.

52

Why are you using auto&& without std::forward?

libcxx/test/std/algorithms/alg.sorting/alg.min.max/ranges.max.pass.cpp
38

There are other occurrences of Min in this file.

91

IMO This is clearer.

97

I'm not convinced this is valid. Taking the address of one beyond i when i isn't an array.
Are you sure this is valid? If not we should fix this also in the original min test.

libcxx/test/std/algorithms/alg.sorting/alg.min.max/ranges.min.pass.cpp
12 ↗(On Diff #416475)

I noticed this line on other files too, it will be removed in D122099

philnik updated this revision to Diff 416781.Mar 20 2022, 7:27 AM
philnik marked 3 inline comments as done.
  • Address comments
philnik added inline comments.Mar 20 2022, 7:27 AM
libcxx/include/__algorithm/ranges_max.h
52

It's not 100% clear to me if cv qualifications have to stay. I'm pretty sure that __comp has to be callable with lvalues. If cv-qualifications don't have to be kept, the I can use const auto&.

libcxx/test/std/algorithms/alg.sorting/alg.min.max/ranges.max.pass.cpp
97

https://compiler-explorer.com/z/rTTce8YKh At least clang and MSVC only complain if I try to get a two-past-the-end pointer. GCC doesn't complain for some reason.

Mordante added inline comments.Mar 20 2022, 11:54 AM
libcxx/include/__algorithm/ranges_max.h
52

I'm also not 100% sure I know that ranges does some "interesting" things with &&. Maybe @var-const or @ldionne knows for sure.

libcxx/test/std/algorithms/alg.sorting/alg.min.max/ranges.max.pass.cpp
97

Based on [expr.add].4 (http://eel.is/c++draft/expr.add#4), my conclusion is that 4.3 applies and the behaviour is undefined.
But it's odd that Clang and MSVC accept it. Still I'm not convinced it's not a compiler bug since GCC accepts every value, including 42 and -42.
(Changing int i; to int i[1]; makes the code valid.

var-const requested changes to this revision.Mar 21 2022, 11:37 PM
var-const added inline comments.
libcxx/docs/Status/RangesAlgorithms.csv
19

Nit: can you add a link to this patch as well?

libcxx/include/__algorithm/ranges_max.h
51

Very optional nit: personally, I usually prefer to separate any initial error handling from the main body of the function by a blank line (so in this case, I would add a blank line after the assertion). However, it's really a personal preference thing, so feel free to ignore if you don't feel it makes a difference.

52

I think there's an important nuance in how equivalent elements are handled. IIUC, min_element returns the rightmost of equivalent elements, whereas max needs to return the leftmost -- therefore, with the arguments swapped, we will get the correct behavior for max. Can you please add a comment to that effect (assuming my reasoning is correct)?

52

Do we have tests to make sure a comparator that takes the argument by lvalue works? (if not, please add them)

I think ranges often use forwarding references simply to avoid providing several overloads for different types of references (sort of similar in spirit to how the "take-by-value-and-move" idiom allows not writing two overloads for rvalue and const lvalue). This seems to apply here, but @ldionne would know better.

68

Nit: move __first and __last?

libcxx/test/std/algorithms/alg.sorting/alg.min.max/ranges.max.pass.cpp
97

+1 for using int i[1], which is clearly valid and adds very little boilerplate.

215

Hmm, I don't see the equivalent test for the initializer_list overload, but perhaps I'm just not seeing it?

This revision now requires changes to proceed.Mar 21 2022, 11:37 PM
philnik updated this revision to Diff 418271.Mar 25 2022, 10:24 AM
philnik marked 8 inline comments as done.
  • Address comments
libcxx/include/__algorithm/ranges_max.h
52

Both should return the leftmost element. I'm not sure how you got to the rightmost element by swapping the arguments. Did you think of less-or-equal maybe?

52

I think the && part is only interesting for returning ranges::dangling. A comparator that only takes the arguments by lvalue isn't allowed. See std::indirect_strict_weak_order for details.

var-const accepted this revision as: var-const.Apr 1 2022, 9:59 PM
var-const added inline comments.
libcxx/include/__algorithm/ranges_max.h
52

Never mind, I misread that.

philnik updated this revision to Diff 420027.Apr 3 2022, 12:17 AM
  • Fix modules build
Mordante accepted this revision.Apr 3 2022, 7:19 AM

LGTM!

This revision is now accepted and ready to land.Apr 3 2022, 7:19 AM
This revision was landed with ongoing or failed builds.Apr 3 2022, 8:05 AM
This revision was automatically updated to reflect the committed changes.
ldionne added inline comments.May 20 2022, 9:08 AM
libcxx/include/__algorithm/ranges_max_element.h
39

I just stumbled upon this, but this is not ADL-safe. Can you please fix and add a test? It is probably worth checking in other algorithms too if there is the same problem, while we're at it.