[libc++] [P1614] Implement the first half of [cmp.alg]: strong_order, weak_order, partial_order.

[• Quuxplusone]

Summary

Re the behavior of std::strong_order for floating-point types, see
https://stackoverflow.com/questions/59348310/how-to-implement-the-totalorder-predicate-for-floating-point-values
https://stackoverflow.com/questions/69068075/what-is-the-purpose-of-if-x-and-y-represent-the-same-floating-point-datum-i
https://quuxplusone.github.io/blog/2021/09/05/float-format/

There's still an open question of what it should do for long double; I'm proposing to just leave it unimplemented in hopes that someone who cares about it will provide an implementation.

This PR does not implement std::strong_order_fallback et al. That will be a second PR. (It is now D111514.)

[• Quuxplusone]

libcxx/test/std/language.support/cmp/cmp.alg/strong_order.pass.cpp

354

This fails for float on the 32-bit x86 buildkite:
https://reviews.llvm.org/harbormaster/unit/view/1389305/
(And maybe other cases would fail after this one, but buildkite won't tell us.)
Anyone got any leads on why this might be? When I try it on Godbolt, it seems OK: https://godbolt.org/z/7eEcnWev7

[• Quuxplusone]

Skip signaling-NaN tests on x86-32 (x87 floating point).

libcxx/test/std/language.support/cmp/cmp.alg/strong_order.pass.cpp

354

Now I can reproduce it: https://godbolt.org/z/f17a5GzM9
The problem is that when -m32, the bit-pattern of numeric_limits<float>::signaling_NaN() depends on optimization level. At -O1 the bit-pattern is 0x7fa00000. At -O0 it is 0x7fe00000, which is actually not a signaling NaN at all!
This seems to be a problem with __builtin_nansf("") on -m32: https://godbolt.org/z/cTjqxeG1T
And googling that turns up: https://stackoverflow.com/questions/22816095/signalling-nan-was-corrupted-when-returning-from-x86-function-flds-fstps-of-x87

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=57484#c12

This issue is unfortunately unfixable. x87 and x86-32 ABI are just not designed to handle all details of IEEE 754 standard.

So it looks like the appropriate workaround here is just to ifdef out the offending NaN tests on x86-32 targets.

[• Quuxplusone]

strong_order depends on compare_three_way depends on three_way_comparable_with depends on Concepts, so UNSUPPORTED: libcpp-no-concepts and guard the header too.

[mumbleskates]

libcxx/test/std/language.support/cmp/cmp.alg/strong_order.pass.cpp

449

I could gin up some asserts for confirming the standard layout of an intel long double. Not 100% sure how to do that constexpr but I think it's doable.

long double on my ARM device(s) is a true iec559 quad precision type, and should be implementable in the same way as the others by bit_casting to __int128_t in this layout.

I find that layout for PPC long double hilarious, but thankfully the standard specifies that strong_order is not required at all for non-iec559 numeric types, so we can simply leave it out and don't have to worry about ever implementing those types unless it is added to the standard draft as a mandate in the future.

All this to say I'm happy to help pushing on this todo for our supported platforms, and I agree that we probably shouldn't get it in with this diff.

[mumbleskates]

libcxx/include/__compare/strong_order.h

97

Would it also be sensible for us to static_assert that quiet_NaN() and signaling_NaN() are ordered correctly by strong_order, or even perhaps SFINAE via a wrapper function that participates only when the behavior is as expected?

libcxx/test/std/language.support/cmp/cmp.alg/strong_order.pass.cpp

349–352

Now that we have bit_cast, is it not possible for us to flip the sign by round tripping it it through an integer and xor'ing it with the bits for -0.0 at compile time? (I am pretty sure that -0.0 has, in all iec559 encodings binary and decimal, only the sign bit set and all others zeroed out, which can also be checked via has_single_bit).

[• Quuxplusone]

libcxx/include/__compare/strong_order.h

97

Would it also be sensible for us to static_assert that quiet_NaN() and signaling_NaN() are ordered correctly by strong_order

Isn't that covered in the tests below? (I'll comment on the exact line.)

libcxx/test/std/language.support/cmp/cmp.alg/strong_order.pass.cpp

349–352

It appears that we can! https://godbolt.org/z/z163Ges6G
However, this requires a bit of metaprogramming to determine an integral type with the same width as F, and that's a bit more complicated than I really want to put into this test file. It would basically be repeating the conditional_t chain from lines 91–94 of strong_order.h.

auto copysign = [](F f, int sign) {
    using I = std::conditional_t<sizeof(F) == sizeof(int32_t), int32_t,
        std::conditional_t<sizeof(F) == sizeof(int64_t), int64_t, void>>;
    I mask = std::bit_cast<I>(F(-0.0));
    if (sign < 0) {
        return std::bit_cast<F>(std::bit_cast<I>(to) | mask);
    } else {
        return std::bit_cast<F>(std::bit_cast<I>(to) & ~mask);
    }
};

387

@mumbleskates: This is the exact line that compares quiet_NaN() against signaling_NaN() (and see line 395 too).
Notice that we're testing "positive quiet NaN" (which might not be literally quiet_NaN()) against "positive signaling NaN" (which might not be literally signaling_NaN()), and lines 361 and 370 are testing "negative quiet" against "negative signaling"; we never literally test the numeric_limits values directly. The Standard doesn't mandate (AFAIK) whether numeric_limits<F>::quiet_NaN() should have a positive or negative sign bit.

[mumbleskates]

libcxx/include/__compare/strong_order.h

97

I was thinking about in the library itself, such that the assertion runs at compile time for the user rather than only in our test suite's platform coverage. If that isn't part of our mandate of rigor and our CI tests are adequate for deploying the code everywhere then I suppose that would answer my question.

libcxx/test/std/language.support/cmp/cmp.alg/strong_order.pass.cpp

349–352

Okay, that's pretty cool! and could be helpful, depending on your thoughts on my other comments here.

387

Yeah, this all makes sense. I was mostly thinking in terms of getting this to also run statically, or check at our strong_ordering header's compile time whether these basic assumptions about the natural ordering of float payloads hold. Again not sure whether that's within our mandate, but recall that the iec559 standard recommends, but does not require, that the signaling bit be set to 1 for quiet and 0 for signaling; it may be reversed.

So yes, this also depends on how paranoid we are being. The only arch I have read about doing this for sure is PA-RISC, whose most recently released CPU came out in 2005, and any support for that platform is "out-of-tree" for LLVM.

[• Quuxplusone]

libcxx/test/std/language.support/cmp/cmp.alg/strong_order.pass.cpp

387

I think that adding static_assert to our actual libcxx/include/ headers would be a bad idea. Our libcxx/test/ tests will certainly catch such an issue, on any supported platform; and I would hope that anyone trying to use libc++ on a non-supported platform would at least think to run the tests first, just out of curiosity.

I did notice on Godbolt that apparently MSVC-on-Windows uses 0x7fc00000 for quiet-NaN (as usual) but 0x7fc00001 for signaling-NaN (which is not a signaling NaN on the platforms I'm familiar with).
https://godbolt.org/z/oh6ch1dGa

[mumbleskates]

libcxx/test/std/language.support/cmp/cmp.alg/strong_order.pass.cpp

387

Okay that makes sense. If there are really that many buggy underlying implementations of quiet_NaN and signaling_NaN we're an order of magnitude more likely to see those just be outright wrong in this way than we are to find platforms with different-looking NaNs then it isn't really very helpful for us to guard against it this way. Sounds good

[ldionne]

libcxx/include/__compare/partial_order.h

35

That speaks a bit more than go (even though I'm pretty sure I'm guilty of this name at some point too, I have a faint memory).

39

As a side note, usually we do this:

noexcept(noexcept(EXPRESSION))
-> decltype(      EXPRESSION)
{ return          EXPRESSION; }

67

Do you want to ADL-protect those?

libcxx/include/__compare/strong_order.h

41

Throughout: I've found it a bit surprising that the parameters are called e and f. I would've found a and b easier to follow and closer to what everyone does. Any reason?

59

So for long double, we're supposed to implement it using the ISO/IEC/IEEE 60559 algorithm but currently we fall back to the common operator< & friends. Are those equivalent, but the ISO/IEC/IEEE 60559 is simply more efficient? If that's the case, I think it's reasonable not to implement it immediately. However, if the current implementation isn't correct on long double, then we either can't ship it or we should error out explicitly if someone uses long double.

libcxx/include/__compare/weak_order.h

47

What am I missing here? We're never checking for is_iec559?

libcxx/include/__utility/priority_tag.h

22–23

Yeah, I agree.

libcxx/test/std/language.support/cmp/cmp.alg/strong_order.pass.cpp

112

General comment for all the floating point comparisons in this patch: is there an existing set of inputs with known comparison outputs we could use and feed as test data? IOW, if we had a list of floating points and how they compare to each other, we could use that to validate our implementation -- as long as we satisfy that almost exhaustive set of inputs, we'd know our algorithm is most likely implemented correctly.

[• Quuxplusone]

@ldionne ping — some responses to your comments; no planned changes yet.

libcxx/include/__compare/partial_order.h

35

FWIW, I wanted to stay away from "overloading" names that already have a different meaning in the STL. What we're doing here is very much not apply'ing anything (in the std::apply sense); we just need a name that is both a reasonable substitute for operator(), and reasonably Ctrl+F'able (so I also didn't want __f). I also have a faint memory of __go somewhere in libc++, but git grep says it's not there now.

Still, I think it would be nice for us to standardize on __go, for "overload sets like this that take __priority_tag"!

67

You mean __go? No, it's a member, so it needn't (and can't) be qualified.

libcxx/include/__compare/strong_order.h

41

The Standard calls them E and F, so I just went with that.
https://eel.is/c++draft/cmp.alg#1
I suspect the original etymology is just "Expression". :)
I'm not super strongly attached, but if we were to change them, I think I'd want _Tp __t, _Up __u over either _Tp __a, _Up __b (inconsistent) or _Ap __a, _Bp __b (unfamiliar).

59

"Are those equivalent[?]" — No; non-IEC559 types can't guarantee to order sNAN before qNAN, because we don't know anything about the bit layout of the type. However, what actually happens in this case is that we go to codegen the long else if ladder, and we get down to the bit_cast on line 101, and it blows up at compile-time because we're trying to bit_cast to void (line 93).
So, if sizeof(long double) == sizeof(double), then I think we do the right thing; and if sizeof(long double) > sizeof(double) (as on common platforms), regardless of whether it's IEC559 or not, then we already error out at compile time rather than do the wrong thing.

If you like, I could add a more explicit assertion, like

} else if constexpr (!(sizeof(_Dp) == sizeof(int32_t) || sizeof(_Dp) == sizeof(int64_t))) {
    static_assert(sizeof(_Dp) == 0, "Only 32-bit and 64-bit floating-point types are supported right now");

libcxx/include/__compare/weak_order.h

47

The weak_order algorithm doesn't benefit from knowing it's IEC559.
https://eel.is/c++draft/cmp.alg#2
We can't just compare the bits int-wise, the way we can for strong_order, because we need to arrange it so that std::weak_order(qNAN, sNAN) == std::weak_ordering::equivalent even when their bits are different. That motivates lines 55–66. And then the rest of the algorithm ends up being exactly the same no matter whether the type is IEC559 or not (because it's just the ordinary meaning of <=>, including the ordinary meaning of equivalence for positive+negative zeroes).

libcxx/test/std/language.support/cmp/cmp.alg/strong_order.pass.cpp

112

I don't know of an existing "test vector" for floating-point; but I claim that my lines 123–134 are pretty good if I do say so myself. ;) I'm covering INF, the whole range of normals, and positive and negative zero. The one hole, I guess, is that I'm not doing anything with subnormals (numbers whose magnitude is less than numeric_limits<F>::min()). I don't know how to generate such numbers, except through bit_cast. (But that is my own ignorance; there probably is a way I just don't know.)

[• Quuxplusone]

Mark https://wg21.link/LWG3324 as "Complete".

[ldionne]

libcxx/include/__compare/partial_order.h

35

Alright, I still prefer __apply but won't bikeshed here since it's mostly about personal preference. Let's agree on not having any standardized name for this for now :-).

39

Ping on this - please format consistently with the other places where we do this. It helps for grepping.

67

Reviewed my ADL 101 and you're right.

Note that you can, however, qualify it. Like this->__go or __fn::__go. No action needed.

libcxx/include/__compare/strong_order.h

41

Non-binding, but I'd like to use __t and __u if we can agree on that. We don't use __e very often, and we are pretty consistent about using __f to denote some sort of callable, which I find misleading here.

59

I'd be happy with the assertion.

[• Quuxplusone]

Address review comments. Rename E/F to T/U. Add a .verify.cpp test for the error message on std::strong_order(ld, ld).

Also, drive-by mark some spaceship issues as "Completed." (This will be committed as a separate git commit.)

[• Quuxplusone]

libcxx/include/__compare/partial_order.h

39

The difference was just the extra spaces I put around noexcept(noexcept( E )) and decltype( E ), right? Is this the way you want it now?

libcxx/include/__compare/strong_order.h

41

Done. (But it's easy to revert if anyone objects.)

59

Added a "temporary, TODO FIXME" .verify.cpp test to verify the current behavior.

[• Quuxplusone]

libcxx/test/std/language.support/cmp/cmp.alg/strong_order_long_double.verify.cpp

16–18

This test fails on arm7 (32-bit?) and Win32, where long double is 64 bits just like double.
It also fails on arm8 (64-bit?) for some reason I can't reproduce on Godbolt.
It also fails on AIX.
@ldionne: Any idea what XFAIL lines I should add here? Or shall I just eliminate this test again?

[ldionne]

LGTM with requested changes and CI passing. I think you had updates to the Status pages you wanted to do separately from this commit -- please don't forget to land those (I don't mind them being landed in the same commit FWIW).

libcxx/docs/Status/Cxx20Issues.csv

253

Do you mean 14.0 or 13.0 here?

libcxx/docs/Status/SpaceshipPapers.csv

5

Same question, 14.0 or 13.0?

libcxx/include/__compare/partial_order.h

26

_LIBCPP_HAS_NO_SPACESHIP_OPERATOR can be removed now.

39

Sorry, should have made it clearer, but the difference is the positioning of braces. This seems like a nitpick, but I've mass-modified these expressions in the past and having consistent formatting really helps.

libcxx/test/std/language.support/cmp/cmp.alg/strong_order_long_double.verify.cpp

16–18

What I did to figure this out is go to the various CI jobs that were failing and look for the following line in the Lit output: add Lit feature target=x86_64-pc-windows-msvc' as a result of parameter 'target_triple=x86_64-pc-windows-msvc' (and similarly for all failing platforms). I think what you want is:

// The following platforms have sizeof(long double) == sizeof(double), so this test doesn't apply to them.
// UNSUPPORTED: target={{arm64|armv8|armv7|powerpc|powerpc64}}-{{.+}}
// UNSUPPORTED: target=x86_64-pc-windows-{{.+}}

24–28

[• Quuxplusone]

Address @ldionne's review comments. Let's see if CI likes this now.

[• Quuxplusone]

libcxx/docs/Status/Cxx20Issues.csv

253

I believe I mean 13. This was D99309.

libcxx/include/__compare/partial_order.h

39

Aha. I didn't notice the braces. Fixed now, AFAICT.

[• Quuxplusone]

Stop static_assert'ing is_iec559 — it turns out that that's false for long double on AIX, but I bet the test still passes either way, so let's just verify that with buildkite.