This is an archive of the discontinued LLVM Phabricator instance.

[libc++] Refactor __less
ClosedPublic

Authored by philnik on Mar 3 2023, 4:25 PM.

Details

Reviewers
ldionne
Mordante
EricWF
Group Reviewers
Restricted Project
Commits
rG88632e480696: [libc++] Refactor __less
Summary

This simplifies the usage of __less by making the class not depend on the types compared, but instead the operator(). We can't remove the template completely because we explicitly instantiate std::__sort with __less<T>.

Diff Detail

Event Timeline

philnik created this revision.Mar 3 2023, 4:25 PM
Herald added a project: Restricted Project. · View Herald TranscriptMar 3 2023, 4:25 PM
Herald added a subscriber: mgrang. · View Herald Transcript
philnik requested review of this revision.Mar 3 2023, 4:25 PM
Herald added a project: Restricted Project. · View Herald TranscriptMar 3 2023, 4:25 PM
Herald added a reviewer: Restricted Project. · View Herald Transcript
EricWF requested changes to this revision.Mar 7 2023, 1:32 PM
EricWF added a subscriber: EricWF.

This cleanup seems incomplete. Why keep __less as a template at all given it's never actually used as one?

Also does the iterator's ::value_type always have to exactly match the type returned from dereferencing it?

libcxx/include/__algorithm/comp.h
37

This doesn't at all seem correct to me.

This takes away an explicit conversion

libcxx/include/__algorithm/includes.h
64

Is this correct? What if the iterator returns a type convertible to value_type?

This revision now requires changes to proceed.Mar 7 2023, 1:32 PM
EricWF added inline comments.Mar 7 2023, 1:32 PM
libcxx/include/__algorithm/comp.h
37

*The implicit conversion.

This cleanup seems incomplete. Why keep __less as a template at all given it's never actually used as one?

If you block other reviews on there not being a description, at least read it.

libcxx/include/__algorithm/includes.h
64

AFAICT the standard it either very silent on this, or says one should use less{} as the comparator, which does what __less<>{} does after this change. So this change is either a conforming change, or arguably a bugfix. Although funnily enough std::less{} isn't actually well-formed, and it doesn't specifically use ranges::less{} for the classic algorithms.

philnik updated this revision to Diff 503404.Mar 8 2023, 9:15 AM

Try to fix CI

ldionne requested changes to this revision.Mar 9 2023, 9:22 AM
ldionne added inline comments.
libcxx/include/__algorithm/comp.h
32–42

So there's actually a behavior change in this patch (the removal of implicit conversions noticed by @EricWF). However, I think it is desirable -- right now I don't think we are conforming in C++20. For example, take lower_bound: http://eel.is/c++draft/lower.bound#1. It specifically says Let comp be less{} and proj be identity{} for overloads with no parameters by those names., which implies that we should be using the transparent comparator, but we are not (before this patch).

I think this mandates a change everywhere along with tests. We should also confirm what's the expected behavior in prior Standards and make sure we conform in those as well.

33

Please add a comment explaining why it's empty.

This revision now requires changes to proceed.Mar 9 2023, 9:22 AM
philnik added inline comments.Apr 3 2023, 4:50 AM
libcxx/include/__algorithm/comp.h
32–42

I'm not actually convinced this behaviour change is reliably observable. AFAICT it would only be possible to observe with an input_iterator that returns a proxy reference which is comparable to the referenced type. Even then, an implementation is most likely allowed to call both operator<(value_type&, proxy) and operator<(value_type&, value_type&). I'd argue that this case is unspecified behaviour.

ldionne added inline comments.Apr 20 2023, 9:04 AM
libcxx/include/__algorithm/comp.h
32–42

I am not sure whether this is actually spelled out explicitly in the standard, but it's definitely observable: https://godbolt.org/z/51WKExTxK

At the very least, I think we need to provide this guarantee as a QOI, and so we should have tests for that under libcxx/test/libcxx if not in libcxx/test/std.

libcxx/src/algorithm.cpp
24–25

Clearer IMO

philnik updated this revision to Diff 527639.Jun 1 2023, 3:03 PM
philnik marked 7 inline comments as done.

Address comments

ldionne accepted this revision.Jun 2 2023, 10:54 AM
ldionne added inline comments.
libcxx/include/__algorithm/sort.h
889
895
902
910
libcxx/test/libcxx/algorithms/robust_against_using_non_transparent_comparators.pass.cpp
9

Let's add a comment explaining what this test does, in particular the fact that this is technically not mandated by the standard but we provide it as QOI.

29
philnik updated this revision to Diff 528026.Jun 2 2023, 3:36 PM

Try to fix CI

philnik updated this revision to Diff 528487.Jun 5 2023, 9:59 AM

Try to fix CI

philnik updated this revision to Diff 528591.Jun 5 2023, 3:06 PM

Try to fix CI

philnik updated this revision to Diff 528904.Jun 6 2023, 9:19 AM

Try to fix CI

This revision was not accepted when it landed; it landed in state Needs Review.Jun 6 2023, 1:59 PM
This revision was automatically updated to reflect the committed changes.