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

[mumbleskates]

Summary

Implements parts of P1614, including synth-three-way and three way comparison for std::pair.

[mumbleskates]

libcxx/include/__utility/pair.h

332–333

It's true that the NaN tests do not cause the old code to fail, but I have rewritten it to match the standard anyway as requested.

libcxx/test/libcxx/compare/synthesized.pass.cpp

21 ↗

(On Diff #365069)

Are the UNSUPPORTED comment annotations programmatically processed? It's not completely clear to me if the comment has effect or is conventional. I'll delete these guards assuming you mean that it has effect.

34 ↗

(On Diff #365069)

Having a cast operator to std::weak_ordering is totally insufficient for an ordering; you also have to totally satisfy that comparison against the comparison-unspecified-zero argument type is boolean-testable for all comparison operators, otherwise it fails to satisfy the concept.

Not only that, the concept requires that the above is satisfied, and that the result type of the three way comparison is understood by std::common_comparison_category, which only knows about std::partial_ordering, std::weak_ordering, and std::strong_ordering. The most rigorous attempt I have made to produce a new comparison category either fails to be recognized due to the above and falls back to rewritten comparisons using the custom three way return type (which works! the type is, so to speak, on the council but not granted the rank of master) or is IFNDR.

I've added a test for types that define a valid operator<=> but are lacking operator==.

[mumbleskates]

Always gate synth-three-way on concepts

[mumbleskates]

Include __compare/ordering.h in non-review code and include __compare/synth_three_way.h in <compare> to solve module errors

[mumbleskates]

Actually don't include synth_three_way in <compare>; instead include the functionality for testing from where it is officially exposed

[mumbleskates]

rebase

[mumbleskates]

• modularization fixes in non-review code

[mumbleskates]

• misc. updates from feedback
• rebase

[cjdb]

I've just noticed the commit rename: [P1614] only holds meaning to folks who know what the proposal number corresponds to, and it also means that we can only search history for patches related to P1614, rather than the effort. What we do for ranges is this:

[libcxx][ranges] commit summary

Long commit message

Implements part of P1614 '<paper title>'.

Would you mind doing the same here please? I think a good tag would be [comparison] or [spaceship].

[mumbleskates]

• add signed/unsigned comparison tests for synth-three-way

[mumbleskates]

• rebase

[mumbleskates]

• rebase

[• Quuxplusone]

LGTM modulo testing comments, which I think are easy to address.

libcxx/include/__utility/pair.h

315

Before this line, I'd appreciate the addition of a comment line just for ease of comparing against the Standard:

// [pairs.spec], specialized algorithms

libcxx/include/utility

107

Nit: I think // C++20 is indented by 4 too many spaces.
I'd also cuddle the angle-brackets >> on line 106.

libcxx/test/libcxx/library/description/conventions/expos.only.func/synth_three_way.pass.cpp

13

This isn't particularly close to the actual declaration of synth-three-way. Personally I'd just write

// constexpr auto __synth_three_way = ...;

libcxx/test/std/utilities/utility/pairs/pairs.spec/three_way_comparison.pass.cpp

48–56

How about:

using P = std::pair<int, double>;
using nan = std::numeric_limits<double>::quiet_NaN();
ASSERT_SAME_TYPE(decltype(P() <=> P()), std::partial_ordering);
assert((P(1, 1.0) <=> P(1, 2.0)) == std::partial_ordering::less);
assert((P(1, 1.0) <=> P(1, 1.0)) == std::partial_ordering::equivalent);
assert((P(1, -0.0) <=> P(1, 0.0)) == std::partial_ordering::equivalent);
assert((P(1, 2.0) <=> P(1, 1.0)) == std::partial_ordering::greater);
assert((P(1, nan) <=> P(2, nan)) == std::partial_ordering::less);  // because 1 < 2
assert((P(2, nan) <=> P(1, nan)) == std::partial_ordering::greater);  // because 2 > 1
assert((P(1, nan) <=> P(1, nan)) == std::partial_ordering::unordered);
assert((P(1, nan) <=> P(1, 1.0)) == std::partial_ordering::unordered);

And then finally I think we should have a SFINAE test, basically like this (IIUC):

template<class T> concept HasEqual = requires(T t) { t == t; };
template<class T> concept HasLess = requires(T t) { t < t; };
template<class T> concept HasSpaceship = requires(T t) { t <=> t; };

struct NoCompare {};
static_assert(HasEqual<std::pair<int, NoCompare>>);
static_assert(!HasLess<std::pair<int, NoCompare>>);
static_assert(!HasSpaceship<std::pair<int, NoCompare>>);

This SFINAE behavior is a bit bizarre, but it's Standard-conforming IIUC: (p == p) is well-formed, it's just going to hard-error if you actually evaluate it.

[mumbleskates]

• refactor three way comparison test for pair
• comment nits

libcxx/include/utility

107

Nit: I think // C++20 is indented by 4 too many spaces.

It's aligned perfectly with the other comparison operators above it for me. There are no tabs in this file, and dedenting it by 4 doesn't line it up with anything so I'm not sure what you're seeing.

I'd also cuddle the angle-brackets >> on line 106.

Done.

libcxx/test/std/utilities/utility/pairs/pairs.spec/three_way_comparison.pass.cpp

48–56

assert((P(1, nan) <=> P(1, 1.0)) == std::partial_ordering::unordered);

This cannot be evaluated constexpr by GCC, and needs its own non-constexpr-only function. As this is annoying and doesn't particularly add any information that we don't already get by comparing NaN <=> NaN to get unordered, I've been leaving these cases out. (GCC rules that A @ B can't be evaluated constexpr if only one of the operands is NaN; there are similar rules for inf.)

This SFINAE behavior is a bit bizarre, but it's Standard-conforming IIUC: (p == p) is well-formed, it's just going to hard-error if you actually evaluate it.

Would it be better to define operator== in NoCompare to make this less strange? How about this, which achieves the same end but is less weird:

struct NoRelative {
  constexpr bool operator==(const NoRelative&) const = default;
};
static_assert(HasEqual<std::pair<int, NoRelative>>);
static_assert(!HasLess<std::pair<int, NoRelative>>);
static_assert(!HasSpaceship<std::pair<int, NoRelative>>);

[mumbleskates]

There's a CI failure but it looks like an unrelated flake.

[• Quuxplusone]

libcxx/test/std/utilities/utility/pairs/pairs.spec/three_way_comparison.pass.cpp

48–56

This cannot be evaluated constexpr by GCC, and needs its own non-constexpr-only function. As this is annoying and doesn't particularly add any information that we don't already get by comparing NaN <=> NaN to get unordered, I've been leaving these cases out. (GCC rules that A @ B can't be evaluated constexpr if only one of the operands is NaN; there are similar rules for inf.)

Well, that's weird of GCC. I'm still weakly in favor of including these test cases — hiding the GCC-failing ones under #ifdef __clang__ or if (!std::is_constant_evaluated()) or XFAIL: gcc or whatever — but I don't think it's blocking.
I do ask that you adopt my spelling of nan in the tests, even if you delete some of the nan-related lines. The current PR's lines 58-63 are pretty hard to read. (Also, )<=> should be ) <=>; but that'll be more obvious once the numeric_limits cruft is reduced.)

I've just realized that I missed an important test case:

assert((P(nan, 1) <=> P(nan, 2)) == std::partial_ordering::unordered);

This shows that when the .first comparison is unordered, we do not go on to tiebreak using the .second.

How about this, which achieves the same end but is less weird

Sounds good to me. Just, you don't need a definition of the function in order to test the concepts. A declaration will suffice:

struct NoRelative {
  bool operator==(const NoRelative&) const;
};
static_assert(HasEqual<std::pair<int, NoRelative>>);
static_assert(!HasLess<std::pair<int, NoRelative>>);
static_assert(!HasSpaceship<std::pair<int, NoRelative>>);

Perhaps even add >:

struct NoRelative {
  bool operator==(const NoRelative&) const;
  bool operator>(const NoRelative&) const;
};
static_assert(HasEqual<std::pair<int, NoRelative>>);
static_assert(!HasLess<std::pair<int, NoRelative>>);
static_assert(!HasSpaceship<std::pair<int, NoRelative>>);

[mumbleskates]

• more test updates

[mumbleskates]

Also revised the synth_three_way.pass test with similar improvements.

libcxx/test/std/utilities/utility/pairs/pairs.spec/three_way_comparison.pass.cpp

48–56

I do ask that you adopt my spelling of nan in the tests, even if you delete some of the nan-related lines.

Your spelling with using does not work at all because quiet_NaN is a function, not a type; it seems it works just fine with constexpr double nan = ...; though.

Perhaps even add >

I added a second test for that one as well, which seems fine to me.

[Mordante]

LGTM, modulo two small formatting issues. Also a suggestion to improve the tests on non GCC platforms.

libcxx/include/__utility/pair.h

334

Please place return __c; on a new line. Not sure whether this contradicts @cjdb's comment, but in libc++ we normally don't put an if and a return on one line.

libcxx/test/std/utilities/utility/pairs/pairs.spec/three_way_comparison.pass.cpp

16

We normally start with this line, can you move it above // <utility>?

97

How do you feel about this work-around and move these two tests back in test()?
When you do that make sure to start a CI run before committing.

[mumbleskates]

• gate gcc tests on TEST_COMPILER_GCC and is_constant_evaluated

libcxx/test/std/utilities/utility/pairs/pairs.spec/three_way_comparison.pass.cpp

16

That hasn't been my observation, all the adjacent tests (for tuple, for example) already have this line at the end where it is here. I put it where it is to match surrounding code. Grepping around the rest of the project shows no consistency at all in its placement so I'd like to prefer just matching the adjacent files.

97

Yeah that looks good, I'll make the change.

[mumbleskates]

libcxx/include/__utility/pair.h

334

Yes this was written to be spelled exactly as it appears in the standard, so that does contradict.

[mumbleskates]

libcxx/include/__utility/pair.h

334

Reference: https://eel.is/c++draft/pairs.spec#2

[ldionne]

libcxx/include/__compare/synth_three_way.h

29

I believe this needs to be _LIBCPP_HIDE_FROM_ABI inline. The inline is to avoid ODR violations (we're defining a global in a header!) and the _LIBCPP_HIDE_FROM_ABI is to avoid the symbol leaking into the ABI of clients (inline variables result in weak defs being exported from programs that use them, which is pretty bad).

I don't have enough time to investigate the details right now but I could do that tomorrow.

libcxx/test/std/utilities/utility/pairs/pairs.spec/three_way_comparison.pass.cpp

2

If we remove libcxx/test/libcxx/library/description/conventions/expos.only.func/synth_three_way.pass.cpp, do we lose any coverage? (I assume the answer is yes). If so, is it possible to add that test coverage in libcxx/test/std/utilities/utility/pairs/pairs.spec/three_way_comparison.pass.cpp without mentioning implementation details of libc++ instead?

In libc++, we've historically written tests using only what the Standard mentions, and libcxx/test/libcxx is typically for testing libc++ specific behavior, but not for testing libc++ implementation details (we don't generally test those, or if we do, we still aim for 100% test coverage of the standard facility).

[mumbleskates]

libcxx/include/__compare/synth_three_way.h

29

It appears to work just fine if the lambda is defined as _LIBCPP_HIDE_FROM_ABI inline constexpr auto __synth_three_way = []<... but it's not completely clear to me what effect this has.

libcxx/test/std/utilities/utility/pairs/pairs.spec/three_way_comparison.pass.cpp

2

I think synth-three-way is pretty well "mentioned" in the spec, and its behavior pretty thoroughly described there; I would argue that the only "implementation detail" we are depending on here is what the functor is actually named.

I can see an argument for moving the synth-three-way test out of test/libcxx/library and into test/std somewhere, that would be fine. It's my personal preference to test the minutiae of how synth-three-way actually behaves in that file, and to test that usages of the functor in the publicly exposed standards fall back on it correctly without worrying about every possible corner case.

Is there a good way to determine coverage as you mentioned? Does this include conditions in templates and SFINAE testing? The concept of "coverage" here is pretty complex.

[• Quuxplusone]

libcxx/include/__compare/synth_three_way.h

29

constexpr globals, like const globals, are "implicitly static by default." So inline is observable for public STL globals like std::nullopt, because you can say things like

void print_address() { printf("%p\n", (void*)&std::nullopt); }

and it needs to come out to the same address in every translation unit.
For internal implementation details like __synth_three_way, I cannot think of any way that the difference between (implicitly static) and (explicitly inline) could be observed by the user... but, if the library itself were to use __synth_three_way inside another inline function like

inline void some_other_library_thing() { ~~~ __synth_three_way(...) ~~~ }

then that would technically be an ODR violation, because the two different definitions of inline void some_other_library_thing() would end up referring to different internal-linkage __synth_three_ways, and that's an ODR violation. So yes, inline constexpr SGTM.

I don't really understand _LIBCPP_HIDE_FROM_ABI either, but we put it on everything, so, it's a good idea. ;)

libcxx/include/__utility/pair.h

315

You added the comment line on 323, but I think it should be moved upward to ~line 312. operator== is also part of [pairs.spec].

334

FWIW, I would also prefer to see the return on its own line. I don't think "spell it exactly as in the standard" means "all the way down to the whitespace."

[• Quuxplusone]

libcxx/test/std/utilities/utility/pairs/pairs.spec/three_way_comparison.pass.cpp

112–113

Here and throughout: for consistency with elsewhere in the test suite,

test();
static_assert(test());

[mumbleskates]

• address comments

libcxx/include/__compare/synth_three_way.h

29

Cool that makes sense. I wasn't really thinking about it in terms of a value but I guess it technically could have an address in an unoptimized build and it's better to just avoid that.

libcxx/include/__utility/pair.h

315

Oh good call, I forgot about that.

libcxx/test/std/utilities/utility/pairs/pairs.spec/three_way_comparison.pass.cpp

2

I do want to clean this up and address this better if we want to figure out a consistent ground rule to base the tests on, including a full list of what behaviors need to be tested where and making sure they all get covered somewhere. There are at least 8 more places other than pair where synth-three-way is used so I want to make sure we're testing the right surface without introducing too much fragility if we find new cases that need fixing in the future. However this might be best suited for a follow-up diff.

[Mordante]

libcxx/test/std/utilities/utility/pairs/pairs.spec/three_way_comparison.pass.cpp

16

Guess I've been looking at other files, but if this matches the local style it's fine by me.

[ldionne]

libcxx/test/std/utilities/utility/pairs/pairs.spec/three_way_comparison.pass.cpp

16

We are (unfortunately) pretty inconsistent about how we do this in the library right now -- that's been my observation since I started working on it.

[Mordante]

libcxx/test/std/utilities/utility/pairs/pairs.spec/three_way_comparison.pass.cpp

16

IMO unless we have tooling to aid us it's very hard to get consistency. (Not that should stop us from trying to be consistent.)

[mumbleskates]

libcxx/test/std/utilities/utility/pairs/pairs.spec/three_way_comparison.pass.cpp

16

agreed