This is an archive of the discontinued LLVM Phabricator instance.

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

Authored by mumbleskates on Aug 8 2021, 5:59 PM.

Details

Summary

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

Diff Detail

Event Timeline

mumbleskates created this revision.Aug 8 2021, 5:59 PM
mumbleskates requested review of this revision.Aug 8 2021, 5:59 PM
Herald added a project: Restricted Project. · View Herald TranscriptAug 8 2021, 5:59 PM
Herald added a reviewer: Restricted Project. · View Herald Transcript

Add tests for std::pair::operator<=> and synth-three-way

Update to include the whole diff

Quuxplusone requested changes to this revision.Aug 9 2021, 8:01 AM
Quuxplusone added a subscriber: Quuxplusone.

Thanks for working on this! I hope to get D107584 landed later today or tomorrow so that you can rebase on it.

libcxx/include/__compare/__synthesized.h
9–10 ↗(On Diff #365069)

This header should be named __compare/synth_three_way.h (name after the component, and drop the leading underscores on the filename).

24 ↗(On Diff #365069)

Add a comment: // [expos.only.func]

26 ↗(On Diff #365069)

T, U => _Tp, _Up
Also, I'd like to see some discussion (here, and then in the commit message) about why __synth_three_way does not need to be a lambda object the way it's shown in the Standard. I suspect that since it's used for partly-program-defined types like std::pair<int, Holder<Incomplete>*>, the reason may have to do with suppressing ADL... although, no, that doesn't make sense, because we're doing ADL on __t < __u on lines 28 and 35 already.

42 ↗(On Diff #365069)

_VSTD::__synth_three_way (unless you change it back to a lambda)
also T, U => _Tp, _Up

libcxx/include/__utility/pair.h
15–16

(Once the underscores are removed, these will need to be re-alphabetized.)
Also, __com < __con.

337–338

ADL-proof: _VSTD::__synth_three_way, if __synth_three_way doesn't become a lambda.

Also, really evil user code could probably detect that you're calling __result == 0 instead of __result != 0 (since __synth_three_way_result<_T1> could be Widget); how about just using the exact implementation from the Standard, two-part if and all?

Before addressing this comment, please make the change I suggested in comparison.pass.cpp, and re-run your tests. Does my third NaN test case actually blow up this implementation?

libcxx/test/libcxx/compare/synthesized.pass.cpp
11 ↗(On Diff #365069)

Rename the file to synth_three_way.pass.cpp. Also I'd recommend putting it under something like
libcxx/test/libcxx/library/description/conventions/expos.only.func/synth_three_way.pass.cpp.
(We'd put it next to the tests for __decay_copy if we had any, but we don't.)

21 ↗(On Diff #365069)

This #if is true by definition, since the test is unsupported in earlier versions.

34 ↗(On Diff #365069)

Add:

static_assert(std::__synth_three_way(NoSpaceship{1}, NoSpaceship{1}) == std::weak_ordering::equivalent);
static_assert(std::__synth_three_way(NoSpaceship{2}, NoSpaceship{1}) == std::weak_ordering::greater);
ASSERT_SAME_TYPE(std::__synth_three_way_result<NoSpaceship, NoSpaceship>, std::weak_ordering);

Similarly for the other cases tested below.
Finally, unless someone proves that this is IFNDR, please also test

struct CustomSpaceship {
    struct Result { operator std::weak_ordering() const { return std::weak_ordering::equivalent; } };
    Result operator<=>(const CustomSpaceship&) const { return Result(); }
};
ASSERT_SAME_TYPE(decltype(std::__synth_three_way(CustomSpaceship{}, CustomSpaceship{})), CustomSpaceship::Result);
ASSERT_SAME_TYPE(std::__synth_three_way_result<CustomSpaceship, CustomSpaceship>, CustomSpaceship::Result);

and make sure you have a test along these lines for std::pair as well.

(You might find that CustomSpaceship doesn't synth-three-way as written, because it lacks an operator==. If so, well, I recommend adding a test for that too.)

libcxx/test/libcxx/utilities/utility/pairs/pairs.pair/comparison.pass.cpp
42

Could you use double as your type with partial ordering?
Let's also add a test where the unordered result is expected, e.g.

std::make_pair(1, 1.0) <=> std::make_pair(2, std::numeric_limits<double>::quiet_NaN())  // expect ::less
std::make_pair(1, 1.0) <=> std::make_pair(1, std::numeric_limits<double>::quiet_NaN())  // expect ::unordered
std::make_pair(1.0, 1) <=> std::make_pair(std::numeric_limits<double>::quiet_NaN(), 2)  // expect ::unordered
This revision now requires changes to proceed.Aug 9 2021, 8:01 AM
cjdb added inline comments.Aug 9 2021, 9:07 AM
libcxx/include/__compare/__synthesized.h
26 ↗(On Diff #365069)

There at least two advantages to it being a lambda:

  • no ADL issues
  • noexcept is correct by default (you're missing a noexcept specifier on this)
libcxx/include/__utility/pair.h
337–338

Also, really evil user code could probably detect that you're calling __result == 0 instead of __result != 0 (since __synth_three_way_result<_T1> could be Widget);

In which situation is this possible? If three_way_comparable is false, then it's weak_ordering. If the concept is true, then it's only allowed to be one of partial_ordering, weak_ordering, or strong_ordering.

339

Please replace the if-statement with a conditional operator or match the standard's if-statement.

Quuxplusone added inline comments.Aug 9 2021, 9:46 AM
libcxx/include/__compare/__synthesized.h
26 ↗(On Diff #365069)

noexcept is correct by default

If you mean "lambdas are noexcept(auto) by default," no, that's not true. They're constexpr by default, but not noexcept. If the Standard requires noexcept(auto) / expression-equivalency here, then we need to write code to implement it.
However, https://eel.is/c++draft/expos.only.func gives a reference implementation which is noexcept(false). Therefore, at least arguably (and maybe more than arguably), it would be detectably non-conforming to add noexcept(~~~) here.

libcxx/include/__utility/pair.h
337–338

Does my third NaN test case actually blow up this implementation?

No, because __result != 0 is equivalent to !(__result == 0), even in cases like that where !(__result < 0 || __result > 0).

In which situation is [Widget __result] possible?

Ah, right, it's not. OK.

Still, +1 to @cjdb's comment below: please match the Standard's reference implementation here anyway.

mumbleskates marked 6 inline comments as done.

Updates re feedback

libcxx/include/__compare/__synthesized.h
26 ↗(On Diff #365069)

Also, I'd like to see some discussion (here, and then in the commit message) about why __synth_three_way does not need to be a lambda object the way it's shown in the Standard. I suspect that since it's used for partly-program-defined types like std::pair<int, Holder<Incomplete>*>, the reason may have to do with suppressing ADL... although, no, that doesn't make sense, because we're doing ADL on __t < __u on lines 28 and 35 already.

Okay, I'm not 100% sure what the mechanical corner cases are here. However, since it is a "fake" function that I am only defining a common implementation of here so that it can be re-used in {tuple, list, array, vector, set, map, deque, ...}, I feel that the closer we can get to direct usage of the exact definition we have written here the better. Any observable way in which its lookup is a real process that can be observed is a negative. I felt that perhaps regular functions provide a more familiar way to do this, but I am less sure now and at this pass am more confident than I was the first time that templated lambdas are definitely available.

In the first version I have a suspicion that it is guaranteed to work despite ADL shenanigans because it first speaks of __synth_three_way_result, which refers to __synth_three_way in its same block. For now I'll both prepend _VSTD:: in pair.h and revert it to a lambda which I feel more confident about.

26 ↗(On Diff #365069)

...
However, https://eel.is/c++draft/expos.only.func gives a reference implementation which is noexcept(false). Therefore, at least arguably (and maybe more than arguably), it would be detectably non-conforming to add noexcept(~~~) here.

Yes, I'm unable to locate any place where synth-three-way needs to be noexcept; as far as I'm aware, every standard function that uses this mechanism is noexcept(false), and the expository definition of synth-three-way is also noexcept(false).

mumbleskates added inline comments.Aug 9 2021, 4:51 PM
libcxx/include/__utility/pair.h
337–338

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 edited the summary of this revision. (Show Details)Aug 9 2021, 6:40 PM

Always gate synth-three-way on concepts

mumbleskates updated this revision to Diff 365339.EditedAug 9 2021, 8:32 PM

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

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

mumbleskates retitled this revision from Implement std::pair::operator<=> to [libc++] [P1614] Implement std::pair::operator<=>.Aug 17 2021, 6:30 PM
mumbleskates updated this revision to Diff 367090.EditedAug 17 2021, 7:12 PM
mumbleskates marked 3 inline comments as done.

rebase

  • modularization fixes in non-review code
  • misc. updates from feedback
  • rebase
cjdb added a comment.Aug 22 2021, 3:18 PM

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 retitled this revision from [libc++] [P1614] Implement std::pair::operator<=> to [libc++][spaceship] Implement std::pair::operator<=>.Aug 22 2021, 8:07 PM
mumbleskates edited the summary of this revision. (Show Details)
mumbleskates edited the summary of this revision. (Show Details)
  • add signed/unsigned comparison tests for synth-three-way
mumbleskates edited the summary of this revision. (Show Details)Sep 5 2021, 9:52 PM

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

libcxx/include/__utility/pair.h
320

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
111

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
47–55 ↗(On Diff #370826)

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 marked 4 inline comments as done.
  • refactor three way comparison test for pair
  • comment nits
libcxx/include/utility
111

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
47–55 ↗(On Diff #370826)

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>>);

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

libcxx/test/std/utilities/utility/pairs/pairs.spec/three_way_comparison.pass.cpp
47–55 ↗(On Diff #370826)

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 marked an inline comment as done.
  • more test updates

Also revised the synth_three_way.pass test with similar improvements.

libcxx/test/std/utilities/utility/pairs/pairs.spec/three_way_comparison.pass.cpp
47–55 ↗(On Diff #370826)

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 accepted this revision.Sep 22 2021, 12:02 PM

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

libcxx/include/__utility/pair.h
339

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
15 ↗(On Diff #372328)

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

96 ↗(On Diff #372328)

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.

This revision is now accepted and ready to land.Sep 22 2021, 12:02 PM
mumbleskates marked 2 inline comments as done.
  • gate gcc tests on TEST_COMPILER_GCC and is_constant_evaluated
libcxx/test/std/utilities/utility/pairs/pairs.spec/three_way_comparison.pass.cpp
15 ↗(On Diff #372328)

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.

96 ↗(On Diff #372328)

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

mumbleskates added inline comments.Sep 22 2021, 1:56 PM
libcxx/include/__utility/pair.h
339

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

mumbleskates added inline comments.Sep 22 2021, 1:57 PM
libcxx/include/__utility/pair.h
339
ldionne added inline comments.Sep 22 2021, 2:41 PM
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
1 ↗(On Diff #374350)

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 added inline comments.Sep 22 2021, 3:04 PM
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
1 ↗(On Diff #374350)

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.

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
320

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].

339

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."

libcxx/test/std/utilities/utility/pairs/pairs.spec/three_way_comparison.pass.cpp
111–112 ↗(On Diff #374350)

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

test();
static_assert(test());
mumbleskates marked 6 inline comments as done.
  • 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
320

Oh good call, I forgot about that.

libcxx/test/std/utilities/utility/pairs/pairs.spec/three_way_comparison.pass.cpp
1 ↗(On Diff #374350)

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.

This revision was automatically updated to reflect the committed changes.
Mordante added inline comments.Sep 23 2021, 11:04 AM
libcxx/test/std/utilities/utility/pairs/pairs.spec/three_way_comparison.pass.cpp
15 ↗(On Diff #372328)

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

ldionne added inline comments.Sep 23 2021, 12:05 PM
libcxx/test/std/utilities/utility/pairs/pairs.spec/three_way_comparison.pass.cpp
15 ↗(On Diff #372328)

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 added inline comments.Sep 23 2021, 12:08 PM
libcxx/test/std/utilities/utility/pairs/pairs.spec/three_way_comparison.pass.cpp
15 ↗(On Diff #372328)

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 marked 4 inline comments as done.Sep 23 2021, 9:02 PM
mumbleskates added inline comments.
libcxx/test/std/utilities/utility/pairs/pairs.spec/three_way_comparison.pass.cpp
15 ↗(On Diff #372328)

agreed