This is an archive of the discontinued LLVM Phabricator instance.

[libc++][spaceship] Implement std::tuple::operator<=>
ClosedPublic

Authored by mumbleskates on Aug 17 2021, 3:14 PM.

Details

Summary

Implement parts of P1614, including three-way comparison for tuples, and expand testing.

Diff Detail

Event Timeline

mumbleskates created this revision.Aug 17 2021, 3:14 PM
mumbleskates requested review of this revision.Aug 17 2021, 3:14 PM
Herald added a project: Restricted Project. · View Herald TranscriptAug 17 2021, 3:14 PM
Herald added a reviewer: Restricted Project. · View Herald Transcript
cjdb requested changes to this revision.Aug 17 2021, 4:24 PM

Thanks for writing this! Some comments, but it should get to LGTM stage pretty soon.

libcxx/CREDITS.TXT
27–29 ↗(On Diff #367034)

Please defer all of the changes in this file to a dedicated non-functional-change patch.

libcxx/include/tuple
134–142
1314
1318

I really like what you're doing here and wish that we could keep it, but I don't think it meshes with the fact we can compare tuples of different lengths.

1324

As much as I like auto return types, I think it'd be good to match the standard here.

1327

There isn't a constraints or mandates paragraph mentioned in operator<=>, so we can't do this. The note at the bottom states:

Also, all comparison operator functions are short circuited; they do not perform element accesses beyond what is required to determine the result of the comparison.

This implies that tuple{0, 1, 2} <=> tuple{0, 2} is allowed. This will have a knock-on effect for your tests.

libcxx/test/std/utilities/tuple/tuple.tuple/tuple.rel/three_way.pass.cpp
27

Since this type has exactly one use-case, please define it close to its point-of-use.

29

You can delete this line.

31

This should return the opposite of the other overload.

This revision now requires changes to proceed.Aug 17 2021, 4:24 PM
mumbleskates marked 8 inline comments as done.
  • changes from feedback
  • testing fix for GCC constexpr shenanigans
libcxx/include/tuple
1318

As far as I am aware, we cannot compare tuples of different lengths.

1324

Yeah I just wrote it this way because it's less wordy. I can change auto to the full return type here, but it will be exactly duplicated by the declared type of __result, the only thing that is ever returned. Since these are different functions I'll just copy it here, that's fine.

1327

The standard does not require operator<=> between tuples of different lengths to exist. The return type as written in the standard, common_comparison_category_t<synth-three-way-result <TTypes, UTypes>...>, is ill-formed if the tuples have different sizes.

I spent some time looking into this and everything that I can find indicates that comparisons between tuples with mismatching sizes are not defined in the standard.

libcxx/test/std/utilities/tuple/tuple.tuple/tuple.rel/three_way.pass.cpp
27

I would define it locally but those operators apparently have to be friends, and it's much more compact to define it here (because the friend operators can only be defined non-locally).

31

It's the equivalent of lhs > rhs (not >=), and CustomResult is emulating equality here so both of those ought to be false.

  • make synopsis signature match in style
mumbleskates retitled this revision from Implement std::tuple::operator<=> to [libc++] [P1614] Implement std::tuple::operator<=>.Aug 17 2021, 6:30 PM
  • modularization fixes in non-review code
cjdb added inline comments.Aug 19 2021, 4:26 PM
libcxx/include/tuple
1323

Comment unnecessary.

1327

Right, I get it now.

libcxx/test/std/utilities/tuple/tuple.tuple/tuple.rel/three_way.pass.cpp
31

Please have the type's name reflect that this is emulating equality.

libcxx/test/std/utilities/tuple/tuple.tuple/tuple.rel/three_way_incompatible.fail.cpp
25–26 ↗(On Diff #367089)

Please change this to a passing compile-time test and use a requires-expression. Similarly in other failure files.

mumbleskates marked 3 inline comments as done.
  • updates from feedback
mumbleskates marked an inline comment as done.Aug 20 2021, 6:25 PM
mumbleskates added inline comments.
libcxx/test/std/utilities/tuple/tuple.tuple/tuple.rel/three_way_incompatible.fail.cpp
25–26 ↗(On Diff #367089)

As discussed, this one is a compile-time pass test, and the others are now compile-time tests (but still fail tests, because in operator== and all previous iterations of other relational operators, incompatible sizes are eliminated by static_assert rather than by non-participation so we can't SFINAE or concept our way out of it.

Mordante requested changes to this revision.Aug 21 2021, 7:00 AM

Thanks for working on this.

libcxx/include/__compare/synth_three_way.h
1 ↗(On Diff #367935)

You can use the stack feature of Phabricator to make patch series. That makes reviewing the real changes easier.

libcxx/include/tuple
135–142

For clarity please s/until/removed in/

1318

Please use _VSTD::get.

libcxx/test/std/utilities/tuple/tuple.tuple/tuple.rel/three_way.pass.cpp
34

Please change the test to use our common idom to test these constexpr functions both runtime and compile time. See test/libcxx/ranges/range.adaptors/range.copy.wrap/arrow.pass.cpp for a simple example.

39

The empty string in the static_assert is not required in C++20, please remove it.

74

It would be nice to also mix signed and unsigned types.

This revision now requires changes to proceed.Aug 21 2021, 7:00 AM
mumbleskates marked 5 inline comments as done.
  • updates from feedback
mumbleskates marked 2 inline comments as done.Aug 22 2021, 2:10 PM
mumbleskates added inline comments.
libcxx/include/__compare/synth_three_way.h
1 ↗(On Diff #367935)

Unfortunately not finding any clear descriptions of how to do this in any documentation and at this point I'm more afraid of making a huge mess in phabricator notifications, already bad enough with my personal rivalry with arcanist.

libcxx/test/std/utilities/tuple/tuple.tuple/tuple.rel/three_way.pass.cpp
39

TIL

mumbleskates added inline comments.Aug 22 2021, 2:10 PM
libcxx/test/std/utilities/tuple/tuple.tuple/tuple.rel/three_way.pass.cpp
74

I threw in some indexes with matched unsigned types and unsigned <=> floating point. We probably can't do signed <=> unsigned integral types because <=> isn't defined, and the synth-three-way fallback generates promoted compile time errorwarnings about comparison with mixed signs. Not sure if we need to add any tests for this in synth-three-way, I think it's probably fine.

  • rebase onto std::pair differential
mumbleskates added inline comments.Aug 22 2021, 2:20 PM
libcxx/include/__compare/synth_three_way.h
1 ↗(On Diff #367935)

oh cool, i got it to work

  • Probably discovered something useful about GCC NaN: only NaN <=> non-NaN is non-constexpr, not NaN <=> NaN
  • fix braces
mumbleskates retitled this revision from [libc++] [P1614] Implement std::tuple::operator<=> to [libc++][spaceship] Implement std::tuple::operator<=>.Aug 22 2021, 8:08 PM
mumbleskates edited the summary of this revision. (Show Details)
Mordante added inline comments.Aug 23 2021, 10:05 AM
libcxx/test/std/utilities/tuple/tuple.tuple/tuple.rel/three_way.pass.cpp
74

I think it's good to add some of these tests, especially since it's rather new feature, not only in the library but also in the compilers. The warnings can be disabled by adding // ADDITIONAL_COMPILE_FLAGS: -Wno-sign-compare at the beginning of the file.

mumbleskates marked an inline comment as done.
  • add signed/unsigned comparison test (should synthesize)
mumbleskates added inline comments.Aug 24 2021, 8:54 AM
libcxx/test/std/utilities/tuple/tuple.tuple/tuple.rel/three_way.pass.cpp
74

I've added that test since it's small, but I think it is more important and useful to add these tests to synth-three-way directly, where the behavior is implemented (D107721), rather than wracking our brains anew about all the corner cases each time we use the functionality. I've also added the test to the parent differential above as mentioned.

Mordante accepted this revision as: Mordante.Aug 25 2021, 10:28 AM

LGTM!

libcxx/test/std/utilities/tuple/tuple.tuple/tuple.rel/three_way.pass.cpp
74

I see you added more detailed tests in D107721, thanks.

  • nit: modern static_assert in three_way_incompatible.compile.pass
  • rebase
Quuxplusone added inline comments.
libcxx/include/tuple
1328

ADL-proof: _VSTD::__tuple_compare_three_way. Admittedly I think ADL-proofing doesn't matter so much inside an operator that's already meant to be called via ADL. The only way I can see to trigger this ADL-bomb is something silly and probably-not-conforming like

struct Incomplete;
template<class T> struct Holder { T t; };
Holder<Incomplete> *a[2];
std::tuple<Holder<Incomplete>**> t0 = {a+0};
std::tuple<Holder<Incomplete>**> t1 = {a+1};
assert(std::operator<=>(t0, t1) < 0);  // silly, possibly non-conforming
libcxx/test/std/utilities/tuple/tuple.tuple/tuple.rel/eq_incompatible.compile.fail.cpp
21–24 ↗(On Diff #370827)

These error messages are weird. It should be complaining about how you can't write static_cast<void>(x); at file scope.

I recommend rewriting this test as a compile-only SFINAE test, like [UNTESTED CODE]

template<class T, class U>
constexpr bool are_comparable(long, T, U) { return false; }

template<class T, class U>
constexpr auto are_comparable(int, T t, U u)
    -> decltype(t < u)
{ return true; }

static_assert(are_comparable(1, std::tuple<int>(1), std::tuple<int>(2)));
static_assert(are_comparable(1, std::tuple<int>(1), std::tuple<long>(2)));
static_assert(!are_comparable(1, std::tuple<int>(1), std::tuple<int, int>(2)));
static_assert(!are_comparable(1, std::tuple<int, int>(1), std::tuple<int>(2)));

I see you did something like this in three_way_incompatible.compile.pass.cpp already (but of course there you get to use C++20 whereas here you need C++11).

libcxx/test/std/utilities/tuple/tuple.tuple/tuple.rel/three_way.pass.cpp
108

Throughout, please use constexpr double nan = std::numeric_limits<double>::quiet_NaN(); for readability.
This will eliminate many line-breaks.
In the tests where you use both float and double nan, I think it's fine to just have the one variable, because (float)nan is still going to be a float-typed NaN value.

173–174

This is somewhat counterintuitive, right? What is the behavior of T1() == T2() in this case — does it call tuple's operator==, or does it not exist? Should we test that?

  • gate gcc tests on TEST_COMPILER_GCC and is_constant_evaluated
mumbleskates marked an inline comment as done.Sep 22 2021, 1:48 PM
mumbleskates added inline comments.
libcxx/test/std/utilities/tuple/tuple.tuple/tuple.rel/eq_incompatible.compile.fail.cpp
21–24 ↗(On Diff #370827)

I can rewrite these as static_asserts or something instead of cast-to-void, but it is not possible to SFINAE test these cases because operator== (and, prior to c++20, all the other operators) are ruled out as ill-formed by static_assert, not by participation. cjdb had similar questions but it turns out none of the tests that are compile.fail can be written as compile.pass SFINAE (in the case of operator==, even in c++>=20).

libcxx/test/std/utilities/tuple/tuple.tuple/tuple.rel/three_way.pass.cpp
173–174

operator== does not fallback to be rewritten in terms of operator<=>, so yeah tuple's operator== is expectedly undefined in this case.

It doesn't really hurt to test it, but I think this would belong in the eq.pass test instead.

mumbleskates added inline comments.Sep 22 2021, 2:09 PM
libcxx/test/std/utilities/tuple/tuple.tuple/tuple.rel/three_way.pass.cpp
108

This is already done, to be clear.

mumbleskates marked 2 inline comments as done.
  • don't cast-to-void at top-level scope
  • adl-proofing
  • address comments
  • move and standardize the test for synth-three-way
mumbleskates added inline comments.Sep 24 2021, 12:38 AM
libcxx/test/std/library/description/conventions/expos.only.func/synth_three_way.pass.cpp
2

Well, this file reproducibly causes g++-11 to segfault at compile time. fantastic

libcxx/test/std/utilities/tuple/tuple.tuple/tuple.rel/three_way.pass.cpp
173–174

I just spent like 45 minutes trying to make this test work. it can be impossible to use == without error, as expected, but when a no-== type is part of a tuple i cannot get that to be detectable with sfinae or even with concepts and it's unclear to me why that is.

the operator is implemented as a call to a cascade of template functions in template classes, but the end result is still ill formed and (i would think) should be eliminated, and it's beyond my current ability to see why.

mumbleskates added inline comments.Sep 24 2021, 1:17 AM
libcxx/test/std/library/description/conventions/expos.only.func/synth_three_way.pass.cpp
2

The following minimal file causes g++-11 to segfault:

#include <tuple>

int main(int, char**) {
  auto t = std::tuple(1);
  return 0;
}

...basically it seems that g++-11 segfaults any time you try to do class template deduction with std::tuple at all.

  • work around a GCC segfault bug
Mordante added inline comments.Sep 24 2021, 10:46 AM
libcxx/test/std/library/description/conventions/expos.only.func/synth_three_way.pass.cpp
2

Alternatively you add a UNSUPPORTED: gcc-11. Then it would be nice if you file a bug report for GCC and add a comment with the bug number.

mumbleskates marked an inline comment as done.Sep 24 2021, 3:19 PM
mumbleskates added inline comments.
libcxx/test/std/library/description/conventions/expos.only.func/synth_three_way.pass.cpp
2

I worked around it and kind of like the result a little better, rewriting it into a single implementation just called synth_three_way that does the tuple thing and then using that.

The CI failure is once again our windows-dll testing host with "No space left on device"; I managed to get and submit the to the GCC tracker as well.

mumbleskates marked 2 inline comments as done.Sep 24 2021, 3:44 PM
mumbleskates added inline comments.
libcxx/test/std/utilities/tuple/tuple.tuple/tuple.rel/three_way.pass.cpp
173–174

Okay. operator== is not SFINAE-friendly, and does not eliminate itself from participation when the subsidiary types don't have the operator. std::pair doesn't do this either. It's probably possible for us to implement this but that seems entirely beyond the scope here, isn't especially standard, and would probably be a lot of work besides. Suffice to say that calling calling the operator== when any of the subsidiary types are missing that operator expectedly causes an error.

The main reason we can easily SFINAE-test operator<=> is because its return type is dependent on everything it's going to do, so all the steps it's going to take when it executes are in a way traced out ahead of time in the function's signature.

ldionne requested changes to this revision.Oct 5 2021, 3:03 PM

Thanks a lot for working on this. Also, thanks for your patience with the review and for providing such a nice test coverage. I have a few comments but the patch otherwise looks good to me, so let's finish this up and ship it!

libcxx/test/std/utilities/tuple/tuple.tuple/tuple.rel/eq_incompatible.compile.fail.cpp
1 ↗(On Diff #376098)

Please make those .compile.fail.cpp tests be .verify.cpp instead, since you are checking for diagnostics. Applies everywhere.

26–28 ↗(On Diff #376098)

Just make those expected-error-re@*:*. Using the filenames here is brittle as it breaks when we move stuff around. Applies here and elsewhere.

libcxx/test/std/utilities/tuple/tuple.tuple/tuple.rel/gt_incompatible.compile.fail.cpp
24 ↗(On Diff #376098)

All those expected-errors with 0-N are not very strong assertions, since the test would pass even if there was no error (because 0 errors is okay).

The more I read those tests, the more I question their benefit. The Standard says that the program is ill-formed if the tuples don't have the same size, and we usually don't test the ill-formedness of programs (because there are so many programs that are ill-formed, and it's difficult to draw the line of where to stop).

At the same time, I love test coverage and I think there *is* value in testing that comparing two differently-sized tuples doesn't compile. If it did compile, I'd be worried that something is wrong in our implementation. Perhaps I would suggest the following approach in a single file:

#include <tuple>

void f(std::tuple<int> t1, std::tuple<int, long> t2) {
  static_cast<void>(t1 == t2); // expected-error@*:* {{}}
  static_cast<void>(t1 != t2); // expected-error@*:* {{}}
  static_cast<void>(t1 > t2); // expected-error@*:* {{}}
  static_cast<void>(t1 >= t2); // expected-error@*:* {{}}
  static_cast<void>(t1 < t2); // expected-error@*:* {{}}
  static_cast<void>(t1 <= t2); // expected-error@*:* {{}}
}

IMO this is the most concise way to test that comparing tuples with different sizes doesn't compile. It isn't strongly tied to the libc++ implementation, too, so it can live in libcxx/test/std. WDYT?

This revision now requires changes to proceed.Oct 5 2021, 3:03 PM
Quuxplusone added inline comments.Oct 5 2021, 6:36 PM
libcxx/test/std/utilities/tuple/tuple.tuple/tuple.rel/gt_incompatible.compile.fail.cpp
24 ↗(On Diff #376098)

IMHO, if we can't rewrite these tests to be SFINAE-friendly as in three_way_incompatible.compile.pass.cpp (and previous comments already indicate: no, we can't), then we just shouldn't bother with them.

I believe your suggestion's 6 instances of // expected-error@*:* {{}} are equivalent to just 1 instance, right? Because if you're saying @*:* then it doesn't really matter what line(s) you put the comment on. But I agree that splitting that test into 6 different test files seems like overkill.

mumbleskates marked 4 inline comments as done.Oct 6 2021, 8:23 PM
mumbleskates added inline comments.
libcxx/test/std/utilities/tuple/tuple.tuple/tuple.rel/gt_incompatible.compile.fail.cpp
24 ↗(On Diff #376098)

Okay, I've tried consolidating these tests into a single compilation failure verify test for all six small operators as ldionne showed, and retained the SFINAE compile.pass test for three-way comparison.

This raises a new problem: when you test both == and !=, they hit the same static_assert and are consumed by the same error expectation, so only 5 errors are emitted for the 6 operators.

I agree with the idea that these should have less specific error expectations, but I am recalling the reasons I originally split these into their own files. I don't know enough about llvm-lit to know the best way to make this work without doing that, or if I should indeed just give up and make it one file per operator again.

  • reduce the scope of incompatible-size tuple comparison tests
ldionne accepted this revision.Oct 8 2021, 11:42 AM
  • also test size-incompatible < in all versions
ldionne accepted this revision.Oct 8 2021, 2:01 PM

LGTM with comments, let's ship this!

libcxx/test/std/utilities/tuple/tuple.tuple/tuple.rel/size_incompatible_comparison.verify.cpp
16

This is missing a mention of operator<.

23

Add a comment saying we rely on other operators being implemented in terms of those.

  • add missing comments
mumbleskates marked 2 inline comments as done.Oct 8 2021, 2:30 PM
This revision was not accepted when it landed; it landed in state Needs Review.Oct 8 2021, 4:30 PM
This revision was automatically updated to reflect the committed changes.
libcxx/include/tuple