This is an archive of the discontinued LLVM Phabricator instance.

[libc++][compare] Implement three_way_comparable[_with] concepts
ClosedPublic

Authored by rarutyun on Jun 1 2021, 11:29 AM.

Details

Summary

Implementation of three_way_comparable and three_way_comparable_with concepts from <compare> header.

Please note that I have temporarily removed <compare> header from <utility> due to cyclic dependency that prevents using <concepts> header in <compare> one.

I tried to quickly resolve those issues including applying suggestions from @cjdb and dive deeper by myself but the problem seems more complicated that we thought initially.

I am in progress to prepare the patch with resolving this cyclic dependency between headers but for now I decided to put all that I have to the review to unblock people that depend on that functionality. At first glance the patch with resolving cyclic dependency is not so small (unless I find the way to make it smaller and cleaner) so I don't want to mix everything to one review.

Diff Detail

Event Timeline

rarutyun requested review of this revision.Jun 1 2021, 11:29 AM
rarutyun created this revision.
Herald added a reviewer: Restricted Project. · View Herald TranscriptJun 1 2021, 11:29 AM
cjdb requested changes to this revision.Jun 1 2021, 11:41 AM

Thanks for working on this. To get an LGTM, please add test types for the following:

  • A type where operator<=> isn't declared.
  • A type where operator<=> is deleted.
  • A type where operator<=> is declared and operator== isn't.
  • A type where operator== is deleted.
  • A type where all the inequality operators are defined.
  • A type where all but one of the inequality operators are declared.
  • A type where all but one of the inequality operators are declared, and the missing one is deleted.

PTAL at the totally_ordered and totally_ordered_with tests for inspiration.

libcxx/test/libcxx/inclusions/utility.inclusions.compile.pass.cpp
25–27 ↗(On Diff #349031)

Please fix this before merging (same as above).

This revision now requires changes to proceed.Jun 1 2021, 11:41 AM
Quuxplusone requested changes to this revision.Jun 1 2021, 11:42 AM
Quuxplusone added a subscriber: Quuxplusone.
Quuxplusone added inline comments.
libcxx/test/std/language.support/cmp/cmp.concept/three_way_comparable.compile.pass.cpp
68

As usual, I don't think it's important to have hundreds of lines of similar/redundant test cases, and I do think it's important to have simple test cases for the corner cases:

  • What if the type provides <=> but no viable ==? And vice versa?
  • What if the type provides <=> with a non-comparison-category return type, such as int?
  • What if the type provides == with a non-boolean return type, such as int? such as void?
  • What if the type provides <=> but it works only on non-const objects?
  • What if the type provides all six C++17 comparison operators but no C++20 <=>?

etc.

libcxx/test/std/language.support/cmp/cmp.concept/three_way_comparable_with.compile.pass.cpp
77–80

Nit: Please avoid taking clang-format's advice in cases like this where it's clearly making the formatting worse.
Instead, try treating a clang-format diagnostic as a helpful hint that your lines may be too long. E.g. in this case you don't really need to test a const volatile noexcept abominable function type, right? This test clearly could be rewritten as static_assert(!check_three_way_comparable_with<int, int*>()) (or any similar pair of types; the only important thing here is that the expression a == b would be ill-formed).
Renaming check_three_way_comparable_with to simply check is another good way to improve the readability of this test file while also helping to make clang-format happy.

cjdb added inline comments.Jun 1 2021, 12:09 PM
libcxx/test/std/language.support/cmp/cmp.concept/three_way_comparable.compile.pass.cpp
68

As usual, the number of tests here are to ensure that all the sharp objects C++ has to offer are checked. I'll say it once again: concepts are a very new feature, and are relatively untested. Our spaceship operator is a a very new feature, and is relatively untested. As far as I'm aware, LLVM has zero other tests that check these two features interact. These tests ensure that nothing has been accidentally overlooked, and are a cheap way for the whole LLVM project to ensure everything is working as intended.

libcxx/test/std/language.support/cmp/cmp.concept/three_way_comparable_with.compile.pass.cpp
77–80

I'm sure @rarutyun's employer doesn't pay them to spend time overriding clang-format.

Thanks for working on this.

libcxx/include/compare
487

We typically omit the 'exposition only' comment here.
Can you also update the synopsis with the newly added code. When copying please make sure to remove non-ASCII characters. (The invisible hyphens come to mind.)

494

Please use __ugly_names: a -> __a, b -> __b.

507

Also __ugly_names here.

libcxx/test/std/language.support/cmp/cmp.concept/three_way_comparable.compile.pass.cpp
30

char8_t isn't available on all platforms, please guard with #ifnef _LIBCPP_HAS_NO_CHAR8_T.

32

Likewise for char16_t and char32_t using #ifndef _LIBCPP_HAS_NO_UNICODE_CHARS

36

To be complete it would be nice to test __int128_t. This should be guarded with #ifndef _LIBCPP_HAS_NO_INT128. __uin128_t uses the same guard.

68

I also like the verbose testing in this case since it's a new feature. I would like to reduce the amount of redundancy, All types here have basically the same three tests

// with default ordering
static_assert(std::three_way_comparable<T>);

// with explicit ordering
static_assert(std::three_way_comparable<T, std::strong_ordering>);
static_assert(std::three_way_comparable<T, std::weak_ordering>);

Can we move this to a template helper function?

zoecarver added inline comments.Jun 1 2021, 3:07 PM
libcxx/include/compare
494

__make_const_lvalue_ref should take care of making this a reference type (i.e., you can remove the "&").

507

Same comment as above.

libcxx/test/std/language.support/cmp/cmp.concept/three_way_comparable.compile.pass.cpp
78

Do we really need to assert that all these types are not three way comparable? That seems a bit excessive to me (it would be one thing if they were three way comparable, but they're not-- if we use this philosophy for testing, we can have tests of infinite size).

111

Can we get a type where this operator is only available on rvalue references? I think that would currently pass, but should not.

Wmbat added a subscriber: Wmbat.Jun 1 2021, 4:25 PM
cjdb added inline comments.Jun 1 2021, 4:46 PM
libcxx/test/std/language.support/cmp/cmp.concept/three_way_comparable.compile.pass.cpp
78

Please see my comment above.

Wmbat added a comment.EditedJun 2 2021, 3:20 PM

I would like to bring forward a potential change.

I was looking at how to implement compare_three_way and found out that it needs to be present in both <compare> and <functional> according to the standard draft ( <function> synopsis, <compare> synopsis ). It would mean that compare_three_way would need to be implemented in a different header and then included in both <compare> & <functional>, @cjdb recommends the use of a __compare/compare_three_way.h header

Since compare_three_way depends on the three_way_comparable_with concept ( see here ), we might also need to move three_way_comparable to __compare/compare_three_way.h as well. Doing so now might save us the refactor later down the line.

Any thoughts on this?

I was looking at how to implement compare_three_way and found out that it needs to be present in both <compare> and <functional> according to the standard draft ( <function> synopsis, <compare> synopsis).

Sounds like someone should file an LWG issue. I'm not aware of any other library facilities that are listed multiple times in different places in the Standard. This might be a cut-and-paste error.

tcanens added a subscriber: tcanens.Jun 3 2021, 5:34 PM

I was looking at how to implement compare_three_way and found out that it needs to be present in both <compare> and <functional> according to the standard draft ( <function> synopsis, <compare> synopsis).

Sounds like someone should file an LWG issue. I'm not aware of any other library facilities that are listed multiple times in different places in the Standard. This might be a cut-and-paste error.

This is the new way to say "this thing is provided if you include either header": https://github.com/cplusplus/draft/issues/3683

It's very much intentional that compare_three_way is available if you include either <functional> or <compare>.

Wmbat added a comment.Jun 4 2021, 12:27 PM

I was looking at how to implement compare_three_way and found out that it needs to be present in both <compare> and <functional> according to the standard draft ( <function> synopsis, <compare> synopsis).

Sounds like someone should file an LWG issue. I'm not aware of any other library facilities that are listed multiple times in different places in the Standard. This might be a cut-and-paste error.

This is the new way to say "this thing is provided if you include either header": https://github.com/cplusplus/draft/issues/3683

It's very much intentional that compare_three_way is available if you include either <functional> or <compare>.

Then, my proposition stands. We would have to either make <functional> include all of <compare> or make a separate header that contains everything that compare_three_way needs and have it be included by both <compare> and <functional>

cjdb added a comment.Jun 11 2021, 9:56 AM

Ping. @rarutyun this is blocking other work now; will you have time to work on this next week, or would you prefer I take over?

Ping. @rarutyun this is blocking other work now; will you have time to work on this next week, or would you prefer I take over?

Hi,

Yes, next week is exactly my plan. For this week I have so many deadlines for internal work. But now they are all passed and I can get back to this patch and another one.

rarutyun updated this revision to Diff 353133.Jun 18 2021, 5:17 PM

Partially apply comments. Others are in progress.

Will do my best to apply everything before next work week

rarutyun marked 8 inline comments as done.Jun 18 2021, 5:19 PM
cjdb added a comment.Jun 22 2021, 12:10 PM

I would like to bring forward a potential change.

I was looking at how to implement compare_three_way and found out that it needs to be present in both <compare> and <functional> according to the standard draft ( <function> synopsis, <compare> synopsis ). It would mean that compare_three_way would need to be implemented in a different header and then included in both <compare> & <functional>, @cjdb recommends the use of a __compare/compare_three_way.h header

Since compare_three_way depends on the three_way_comparable_with concept ( see here ), we might also need to move three_way_comparable to __compare/compare_three_way.h as well. Doing so now might save us the refactor later down the line.

Any thoughts on this?

Please move the concepts into their own header and include it in <compare>. You might need to break some other stuff out into their own self-contained headers too.

cjdb added a comment.Jun 29 2021, 5:58 PM

Ping @rarutyun, do you need assistance?

Ping @rarutyun, do you need assistance?

I am sorry for the delay. I was on vacation. I don't think I need assistance so far. I am working hard on that patch this week. If I face some troubles I will definitely let you know.

Thanks for proposing the help.

rarutyun updated this revision to Diff 358092.Jul 12 2021, 3:51 PM

I would like to bring forward a potential change.

I was looking at how to implement compare_three_way and found out that it needs to be present in both <compare> and <functional> according to the standard draft ( <function> synopsis, <compare> synopsis ). It would mean that compare_three_way would need to be implemented in a different header and then included in both <compare> & <functional>, @cjdb recommends the use of a __compare/compare_three_way.h header

Since compare_three_way depends on the three_way_comparable_with concept ( see here ), we might also need to move three_way_comparable to __compare/compare_three_way.h as well. Doing so now might save us the refactor later down the line.

Any thoughts on this?

Please move the concepts into their own header and include it in <compare>. You might need to break some other stuff out into their own self-contained headers too.

Do you want me to make those APIs available from <functional> in this review?

libcxx/include/utility
228 ↗(On Diff #358092)

Still struggling with cyclic dependencies.

cjdb added a comment.Jul 12 2021, 5:34 PM

Please move your header split into a standalone NFC patch. I'll review it promptly over there.

Please move your header split into a standalone NFC patch. I'll review it promptly over there.

Done. https://reviews.llvm.org/D106107

This is probably unblocked now that D107584 has landed!

This is probably unblocked now that D107584 has landed!

Thanks, will check today

This is probably unblocked now that D107584 has landed!

Thanks, will check today

Btw, @rarutyun, if you'd like me to commandeer and replace this PR with the relevant portion of D107036, I'd be happy to do that.

rarutyun updated this revision to Diff 366019.Aug 12 2021, 9:30 AM
rarutyun set the repository for this revision to rG LLVM Github Monorepo.

This is probably unblocked now that D107584 has landed!

Thanks, will check today

Checked. Locally it works. Review has been updated.

This is probably unblocked now that D107584 has landed!

Thanks, will check today

Btw, @rarutyun, if you'd like me to commandeer and replace this PR with the relevant portion of D107036, I'd be happy to do that.

Whatever works for you. You may say to me what should be applied.

rarutyun updated this revision to Diff 366037.Aug 12 2021, 11:04 AM

Clang-format suggests incorrect modifications that fail to compile if applied. Could you please suggest the file to look at for the best practice how to turn it off? I could you dedicated comment for that but I am not sure that's how you guys are doing that.

cjdb added a comment.Aug 12 2021, 11:12 AM

Clang-format suggests incorrect modifications that fail to compile if applied. Could you please suggest the file to look at for the best practice how to turn it off? I could you dedicated comment for that but I am not sure that's how you guys are doing that.

Run arc diff --nolint instead of arc diff.

Quuxplusone requested changes to this revision.Aug 12 2021, 3:09 PM

@rarutyun: I've marked the places where this is lacking bits you can take from D107036.
Re the testing issue, let's see what @ldionne wants.

libcxx/include/CMakeLists.txt
103

You'll also need to update module.modulemap and run the various Python generator scripts (which you can now do via ninja libcxx-generate-files or make libcxx-generate-files). Make sure to commit the changed and added new files.

libcxx/include/__compare/three_way_comparable.h
13–17

You're missing some IWYU here, e.g. same_as.h. You need to include these directly, for the benefit of the Modules build; it's not Modules-kosher to rely on the fact that totally_ordered.h happens to include same_as.h.
Check D107036 for the complete listing.

libcxx/include/compare
30–36

Right about here, please update the synopsis comment.
Check D107036 for the right thing.

140

a-z

libcxx/test/std/language.support/cmp/cmp.concept/three_way_comparable_with.compile.pass.cpp
77–80

@rarutyun, you wrote:

Clang-format suggests incorrect modifications that fail to compile if applied.

For generating the diff to upload, I use git show -U999 > x.diff and then "Upload file" into the Phab review. I don't use arc at all in my personal workflow. I don't know if this will help you, but at least I personally spend zero time wrestling with arc; some amount of time wrestling with git instead; and zero time wrestling with clang-format because clang-format is completely unused in my git workflow.

Re Chris's snipe: Don't worry about clang-format. Just write the code the way you'd write it naturally, and then act on Phab feedback (if any) from human libc++ maintainers. clang-format isn't the boss here. :)

Also, note that a massive number of these 230+242 lines can disappear entirely. I tentatively recommend just taking my 101+147 lines of more targeted testing from D107036 (although let's see if @ldionne has a strong preference for these, or wants both, or what). Either way, please delete or fix the misformatting throughout this file.

This revision now requires changes to proceed.Aug 12 2021, 3:09 PM
cjdb added inline comments.Aug 12 2021, 3:15 PM
libcxx/test/std/language.support/cmp/cmp.concept/three_way_comparable_with.compile.pass.cpp
77–80

Also, note that a massive number of these 230+242 lines can disappear entirely. I tentatively recommend just taking my 101+147 lines of more targeted testing from D107036 (although let's see if @ldionne has a strong preference for these, or wants both, or what). Either way, please delete or fix the misformatting throughout this file.

See https://reviews.llvm.org/D103478#inline-980152.

libcxx/test/std/language.support/cmp/cmp.concept/three_way_comparable_with.compile.pass.cpp
50

This specific line is failing on AArch64 and Arm. I suspect that those platforms have a 32-bit unsigned wchar_t, and so this line would be failing for the same reason that

static_assert(std::three_way_comparable<int, unsigned int>);

would fail. Therefore, the correct action is to remove this platform-dependent line (and lines 55 and 59 too). However, consider adding

static_assert(!std::three_way_comparable<int, unsigned int>);

as a sanity check; I think you're missing anything along those lines at the moment.

libcxx/include/__compare/three_way_comparable.h
35–36
requires(__make_const_lvalue_ref<_Tp> __t) {
    { __t <=> __t } -> __compares_as<_Cat>;

Let's keep it simple (and close to the reference implementation).

45

Let's eliminate this linebreak.

cjdb added inline comments.Aug 12 2021, 10:16 PM
libcxx/include/__compare/three_way_comparable.h
28

This comment is unnecessary.

35–36

We shouldn't deviate from what's in the standard. The concept is defined the way it is way for a reason.

libcxx/test/std/language.support/cmp/cmp.concept/three_way_comparable_with.compile.pass.cpp
50

Interesting. I'd prefer to section this test off using an include guard, if it's possible.

rarutyun updated this revision to Diff 366266.Aug 13 2021, 6:32 AM
rarutyun marked 7 inline comments as done.
rarutyun added inline comments.
libcxx/include/CMakeLists.txt
103

Yep, I figured it out from CI results. Done

libcxx/include/__compare/three_way_comparable.h
35–36

Agree with Christopher

rarutyun marked an inline comment as done.Aug 13 2021, 6:34 AM
rarutyun updated this revision to Diff 366289.Aug 13 2021, 8:17 AM
Quuxplusone accepted this revision.Aug 13 2021, 9:01 AM

LGTM % comments at this point.
I'm still unhappy with the testing story — >200 lines of "this kind of member function pointer isn't comparable, that kind of member function pointer isn't comparable..." — but since the code is correct, I'd rather land this as-is than continue with review.

libcxx/include/__compare/three_way_comparable.h
35–36

Ah, I see the reference implementation actually does use a and b; I must have simplified it on my end when I did D107036. Okay then.
(I do disagree that "the concept is defined the way it is for a reason"; it could have been done simpler without b, and had exactly the same semantics. But that's moot until someone files an editorial issue.)

libcxx/test/std/language.support/cmp/cmp.concept/three_way_comparable.compile.pass.cpp
111

remove linebreak plz

229

} // namespace user_defined

231

Please remove the main function. For .compile.pass.cpp tests, which aren't intended to be run (just compiled), we've settled on making sure they don't have a main.

libcxx/test/std/language.support/cmp/cmp.concept/three_way_comparable_with.compile.pass.cpp
50

Nah, just delete the bogus line.

122

} // namespace fundamentals
(and please fix the linebreaks throughout the above; thanks for taking care of the other file already)

241

} // namespace user_defined

243

and remove main

@rarutyun anything blocking this? Do you need help landing it?

rarutyun updated this revision to Diff 367195.Aug 18 2021, 6:35 AM
rarutyun marked 7 inline comments as done.Aug 18 2021, 6:44 AM
rarutyun added inline comments.
libcxx/test/std/language.support/cmp/cmp.concept/three_way_comparable_with.compile.pass.cpp
77–80

Avoiding clang-format. Now everything is written in one line and I agree that it looks better. I would not want to rename check_three_way_comparable_with to just check because I believe that decreases readability but if you insist I may do that.

I am not sure about reducing tests. Seems like different people have different opinions on that. I would prefer to leave it as is unless you have strong objections.

rarutyun updated this revision to Diff 367196.Aug 18 2021, 6:46 AM
rarutyun marked 2 inline comments as done.Aug 18 2021, 6:49 AM

@rarutyun anything blocking this? Do you need help landing it?

Review has been updated. Just was busy with other work.

Hi @cjdb @Quuxplusone. Any progress on this review?

I think I've addressed all important comments and the CI is green (except the clang format, which is not a boss here:) ).

cjdb accepted this revision.Aug 23 2021, 11:15 AM

Also LGTM, but since I'm not a co-approver, we'll need to wait for either @ldionne's approval or a second co-approver.

libcxx/include/__compare/three_way_comparable.h
13–17

For future reference: running bin/llvm-lit -sv /path/to/llvm-project/libcxx/test/ --param enable_modules=True will catch this for you.

This revision is now accepted and ready to land.Aug 23 2021, 11:15 AM

Also LGTM, but since I'm not a co-approver, we'll need to wait for either @ldionne's approval or a second co-approver.

Ok, Waiting for another required approval.

By the way as you might remember I don't have direct access to merge the code directly.

I am putting my data here:

name: Ruslan Arutyunyan
email: ruslan.arutyunyan@intel.com

Please let me know if you want me to get the write access directly into the repository.

ldionne accepted this revision.Aug 25 2021, 8:36 AM

I'll commit this. Thanks a lot for the patch.

@rarutyun Can you please rebase this onto main, it doesn't apply cleanly?

Please let me know if you want me to get the write access directly into the repository.

Yes, that would be useful!

rarutyun updated this revision to Diff 368853.EditedAug 26 2021, 5:06 AM

@rarutyun Can you please rebase this onto main, it doesn't apply cleanly?

@ldionne,

Sure, done.

rarutyun updated this revision to Diff 369417.Aug 30 2021, 5:07 AM

Rebased one more time.

@cjdb, @Quuxplusone @ldionne, could somebody merge it please?

My data:
name: Ruslan Arutyunyan
email: ruslan.arutyunyan@intel.com

I will request the permissions for direct merge for the next commit if you don't mind.

Rebased one more time.

@cjdb, @Quuxplusone @ldionne, could somebody merge it please?

My data:
name: Ruslan Arutyunyan
email: ruslan.arutyunyan@intel.com

I will request the permissions for direct merge for the next commit if you don't mind.

Yes, please do so. Thanks @mumbleskates for merging.