[libcxx] adds concepts `std::totally_ordered` and `std::totally_ordered_with`

[cjdb]

Summary

Implements parts of:

• P0898R3 Standard Library Concepts
• P1754 Rename concepts to standard_case for C++20, while we still can

[• Quuxplusone]

libcxx/test/std/concepts/comparison/concepts.totallyordered/totally_ordered.compile.pass.cpp

104 ↗

(On Diff #331988)

I don't think these tests belong here; but if they do, then it would be nice to see some negative tests too, e.g. after struct A {}; we should have !std::totally_ordered<std::vector<A>> and !std::totally_ordered<std::optional<A>>.

[cjdb]

applies most of @Quuxplusone's feedback (the rest to be addressed in comments).

[cjdb]

In D98983#2638556, @Quuxplusone wrote:

All of these .compile.pass.cpp tests should be .pass.cpp. It's harmless to run them, and we don't want to accidentally nerf any runtime asserts that might sneak in over the years.

@EricWF and I were talking about this yesterday, interestingly. We agree, but we also agreed this should happen after everything is merged so it all remains consistent. WDYT?

libcxx/include/concepts

377

Nice catch.

395

An interesting (and scary) observation. I'd suggest emailing Library Evolution and Library about this.

libcxx/test/std/concepts/comparison/concepts.totallyordered/totally_ordered.compile.pass.cpp

34 ↗

(On Diff #331988)

This is a subsumption check, so the fact it's not being used is by design :-)
I've added a comment to explain this since I agree that wasn't clear.

90 ↗

(On Diff #331988)

Whitespace is dictated by clang-format, and I don't care to fight with it. I'll be marking other formatting comments as done from now on.

104 ↗

(On Diff #331988)

I don't think these tests belong here

Right, they belong in vector tests, etc.. @ldionne asked me to put them here (as I've linked in other patches), so here they are. I think a separate (set?) of patches should migrate these to their proper homes.

then it would be nice to see some negative tests too, e.g. after struct A {}; we should have !std::totally_ordered<std::vector<A>> and !std::totally_ordered<std::optional<A>>.

Done.

[curdeius]

libcxx/include/concepts

385

Using __partially_ordered_with here means that the same expression validity is checked twice (e.g. t < u and u < t, but here the type of t and u is the same, _Tp).
It changes nothing for the correctness (I hope), but may be slightly less efficient.
Would it make sense to split __partially_ordered_with into a "one-way" concept, something along these lines (the name is bad):

template<class _Tp, class _Up>
concept __oneway_ordered_with =p
  requires(const remove_reference_t<_Tp>& __t, const remove_reference_t<_Up>& __u) {
    { __t <  __u } -> __boolean_testable;
    { __t >  __u } -> __boolean_testable;
    { __t <= __u } -> __boolean_testable;
    { __t >= __u } -> __boolean_testable;
};

template<class _Tp, class _Up>
concept __partially_ordered_with = __oneway_ordered_with<__Tp> && __oneway_ordered_with<__Up>;

template<class _Tp>
concept totally_ordered = equality_comparable<_Tp> && __oneway_ordered_with<_Tp, _Tp>;

[curdeius]

libcxx/include/concepts

393

Would it make sense to add a helper for const remove_reference_t<_Tp>& as it starts repeating a lot?

[• Quuxplusone]

libcxx/include/concepts

393

I'm ambivalent on all these refactoring ideas, but I'll at least offer a bikeshed name on this one. ;)

template<class _Tp>
using __const_ref_t = const remove_reference_t<_Tp>&;

    ... totally_ordered<common_reference_t<__const_ref_t<_Tp>, __const_ref_t<_Up>>> ...

[cjdb]

applies @curdeius' feedback

libcxx/include/concepts

385

I'd prefer to stay true to spec for now, and experiment on compile-time impact if the need arises.

393

Aesthetically, I don't like it, but I think it's a good way to prevent mistakes, so done.

[Mordante]

For now a few comments, I'll have a closer look later.

libcxx/include/concepts

217

Minor bikeshed; since the standard type traits start with a verb I would like to do the same here. This "trait" is like make_signed_t so I would suggest __make_const_lvalue_ref.

libcxx/test/std/concepts/comparison/concepts.totallyordered/totally_ordered.compile.pass.cpp

45 ↗

(On Diff #332378)

This feels wrong, when a double has a NaN value there's no total order. I wonder whether this is a bug in the Standard.

[cjdb]

libcxx/include/concepts

217

If we're going to add more characters, does this still benefit us over const remove_reference_t<_Tp>&?

libcxx/test/std/concepts/comparison/concepts.totallyordered/totally_ordered.compile.pass.cpp

45 ↗

(On Diff #332378)

It's a common misconception that floating-point numbers can't model totally_ordered because of NaN.

From cmp.concept:

t < u, t <= u, t > u, t >= u, u < t, u <= t, u > t, and u >= t have the same domain.

NaN is outside this domain, which I believe is documented by floating-point specifications.

Andrew Sutton sums this up in his CppCon 2019 talk. Specifically:

Concepts do not hide preconditions. Syntactic operations are not total operations. Floating point types are totally ordered even though NaN exists.... because there's a precondition on the algorithms that use the operation.... Random-access iterators are totally ordered, even though the relation is really sparse.

[• Quuxplusone]

libcxx/include/concepts

217

IMHO even __const_lvalue_ref<T> has already lost the benefit of brevity. I wanted __const_ref_t<T> to be the spelling that creates a "const T ref"; I see no point to saying lvalue because, what, you expected a const rvalue ref? 😛I thought the trailing _t would be noncontroversial, but actually if people prefer __const_ref<T> or even _ConstRef<T> I think that's great.
Anyway, sounds like a huge bikeshed and I don't want to block anything either way.

[• Quuxplusone]

libcxx/test/std/concepts/comparison/concepts.totallyordered/totally_ordered.compile.pass.cpp

45 ↗

(On Diff #332378)

+1 @cjdb. A Concept like totally_ordered is ultimately just a way of organizing source code, like saying "does it make sense to have a std::set of these things." You can make a std::set<double> just fine. It does misbehave badly if you try to put NaN into it; but, you just have to remember not to do that.

Andrew Sutton wrote:

Random-access iterators are totally ordered, even though the relation is really sparse

Now that's stretching the philosophy to the breaking point, I think ;) but sure, it can make sense to have a std::set<std::deque<T>::iterator>, as long as you're careful to put into it only iterators from a single container and never let them become invalidated.

Or come at it from the other side: Concepts describe the requirements of algorithms, i.e. what cases the algorithm needs to worry about. If the places-where-the-natural-ordering-fails also happen to be places-where-our-algorithms-don't-care-about-the-result (maybe because they're UB), then the concept remains useful in practice.

[Mordante]

No real blockers for me, but I'd like to see the patch pass the CI before approving.

libcxx/include/concepts

217

I also don't want to start a big bikeshed, but I personally prefer names to be clear. But it's no blocker for me.

libcxx/test/std/concepts/comparison/concepts.totallyordered/totally_ordered.compile.pass.cpp

45 ↗

(On Diff #332378)

It's a common misconception that floating-point numbers can't model totally_ordered because of NaN.

From cmp.concept:

t < u, t <= u, t > u, t >= u, u < t, u <= t, u > t, and u >= t have the same domain.

NaN is outside this domain, which I believe is documented by floating-point specifications.

I hadn't read that part, but http://eel.is/c++draft/concepts#concept.totallyordered-1

Given a type T, let a, b, and c be lvalues of type const remove_­reference_­t<T>.
T models totally_­ordered only if

Exactly one of bool(a < b), bool(a > b), or bool(a == b) is true.

Andrew Sutton sums this up in his CppCon 2019 talk. Specifically:

Thanks for the link. I haven't seen this talk yet and Andrew's talks are usually very informative.

As said I think the code is good, just wonder about the Standard.

libcxx/test/std/concepts/comparison/types.h

9 ↗

(On Diff #332378)

Why differs the include guard from the filename? Is this a copy-paste error?

[• Quuxplusone]

libcxx/test/std/concepts/comparison/concepts.totallyordered/totally_ordered.compile.pass.cpp

45 ↗

(On Diff #332378)

Exactly one of bool(a < b), bool(a > b), or bool(a == b) is true

This gets into the ongoing philosophical discussion about the provenance of values inside an algorithm (Howard Hinnant was talking about this a year or two ago). An algorithm might ask for permission to use a certain operation, but the caller still might put restrictions on where and how the algorithm gets to use that operation. Consider: We'd really like int to model both default_constructible and totally_ordered, right? Yet consider this template:

template<class T> requires default_constructible<T> && totally_ordered<T>
bool example() {
    T a, b;
    return bool(a < b) || bool(a > b) || bool(a == b);
}

Yet example<int>() may return false — https://godbolt.org/z/b83665obM — because actually it has undefined behavior. Concepts don't close every wild-west loophole in C++.

[cjdb]

gets gcc working

[cjdb]

further changes

[cjdb]

libcxx/test/std/concepts/comparison/types.h

9 ↗

(On Diff #332378)

I renamed the file and forgot to update the guard. Fixed!

[zoecarver]

Just a few comments right now. I'll try to do a more in-depth review later.

libcxx/include/type_traits

4508

Why is this guarded on C++11?

libcxx/test/std/concepts/comparison/concepts.totallyordered/totally_ordered.pass.cpp

13 ↗

(On Diff #333055)

Is this actually stated below? Maybe just say "concept totally_ordered"

115 ↗

(On Diff #333055)

Then do we need to include all those extra headers (i.e., std::vector)?

libcxx/test/std/concepts/comparison/concepts.totallyordered/totally_ordered_with.pass.cpp

1011 ↗

(On Diff #333055)

Nit: I don't think we want/need the space between these. This isn't run in C++03 mode.

[cjdb]

libcxx/include/type_traits

4508

We did something similar in the common_reference patch where @ldionne and I agreed that it could be guarded on C++11 (I don't recall why). If you really want it in C++11 mode, I'll need to know what the C++03 guard is.

libcxx/test/std/concepts/comparison/concepts.totallyordered/totally_ordered.pass.cpp

115 ↗

(On Diff #333055)

Yes, see immediately above.

libcxx/test/std/concepts/comparison/concepts.totallyordered/totally_ordered_with.pass.cpp

1011 ↗

(On Diff #333055)

https://github.com/llvm/llvm-project/blob/main/libcxx/.clang-format#L5

[cjdb]

applies some of @zoecarver's feedback

[cjdb]

s/__const_lvalue_reference/__make_const_lvalue_reference/g

[cjdb]

Are there any further blockers on this patch? I think I've replied to all the feedback.

libcxx/include/concepts

217

I added make.

[zoecarver]

libcxx/include/type_traits

4508

No, I'm saying we might as well remove the guard altogether. Just to make it easier to read/remove code bloat. All the compilers we support allow templated type aliases in C++03. WDYT?

libcxx/test/std/concepts/comparison/concepts.totallyordered/totally_ordered.pass.cpp

115 ↗

(On Diff #333055)

Aha, I see.

libcxx/test/std/concepts/comparison/concepts.totallyordered/totally_ordered_with.pass.cpp

1011 ↗

(On Diff #333055)

I guess we need that... hmm. It's too bad that we have to have (bad) C++03 styles for all of our code. Anyway, that's a bigger discussion/problem.

[Mordante]

LGTM! I'll already approve so @zoecarver can give the final approval.

libcxx/include/type_traits

4508

remove_reference_t is C++14 when switching to C++11 the code needs to be changed to typename remove_reference<_Tp>::type. I've no strong preference whether or not to allow __make_const_lvalue_ref in C++03.

[cjdb]

applies @zoecarver's suggestion

[cjdb]

Completes feedback.

[• Quuxplusone]

libcxx/test/std/concepts/concepts.compare/concepts.totallyordered/totally_ordered.pass.cpp

79

Wrong formatting.

[zoecarver]

This mostly looks good to me. I want to read over the logic part one more time while looking at the standard, but I think this is pretty much good to go. Sorry for being slow with reviewing.

libcxx/test/std/concepts/concepts.compare/concepts.totallyordered/totally_ordered.pass.cpp

103

Nit: > > -> >>

116

I think I brought this up before, but do you want to create a bug for spaceship support and then put a link to it in all the tests that need to be updated? That way you could just do a cmd+f to find all the places that mention the bug ID and need to be updated, rather than searching through all "FIXME" comments.

libcxx/test/std/concepts/concepts.compare/concepts.totallyordered/totally_ordered_with.pass.cpp

95

Also weird formatting here and on L92 (among other places around here).

libcxx/test/std/concepts/concepts.compare/types.h

13

Why do we now need to include <string>?

[zoecarver]

libcxx/test/std/concepts/concepts.compare/concepts.totallyordered/totally_ordered.pass.cpp

116

Just to be clear, I'm not asking you to do this. I'm just suggesting it, as you are likely the one who will be updating these tests ;)

[zoecarver]

Okay, this (finally) looks good to me. As we discussed, I think cutting down these tests a bit in the future will help me review it more quickly (and it would make me feel more confident that I haven't overlooked something). Maybe we should have a larger discussion about how we want to do concept tests in the discord channel. I think it would be beneficial to everyone to solidify some guidelines.

[zoecarver]

(Also, please run this through clang-format or fix the formatting issues I pointed out earlier before you commit.)

[cjdb]

In D98983#2665813, @zoecarver wrote:

(Also, please run this through clang-format or fix the formatting issues I pointed out earlier before you commit.)

This is the product of clang-format. Per @ldionne's musings in D99691, manually overriding clang-format is going to become a hard error in the future.

In D98983#2665810, @zoecarver wrote:

Okay, this (finally) looks good to me. As we discussed, I think cutting down these tests a bit in the future will help me review it more quickly (and it would make me feel more confident that I haven't overlooked something). Maybe we should have a larger discussion about how we want to do concept tests in the discord channel. I think it would be beneficial to everyone to solidify some guidelines.

Yes, future patches will have a reduced set of tests for the most part, because they're not (a) testing the boundary of the language and library, and (b) testing a completely novel compiler feature with minimal field experience. D96477 is an example of this plan.
Having said that, a discussion would be welcome to make sure everyone's on the same page.

libcxx/test/std/concepts/concepts.compare/concepts.totallyordered/totally_ordered.pass.cpp

116

It's a good idea, and I'd love to do that, but apparently that's not what Buganizer is used for (at least, according to @mclow.lists).

libcxx/test/std/concepts/concepts.compare/types.h

13

Removed.

[cjdb]

updates per @zoecarver's feedback (just for the record)

[ldionne]

libcxx/test/std/concepts/concepts.compare/concepts.totallyordered/totally_ordered_with.pass.cpp

639

@cjdb It would be great to go back and reduce the duplication in those tests by using e.g. templates or macros or whatever tool you see fit to make the structure of the tests emerge.