Page MenuHomePhabricator

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

Authored by cjdb on Mar 19 2021, 1:24 PM.

Details

Summary

Implements parts of:

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

Diff Detail

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes
Quuxplusone added inline comments.Mar 19 2021, 1:46 PM
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 updated this revision to Diff 332019.Mar 19 2021, 3:44 PM
cjdb marked 4 inline comments as done.

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

cjdb added a comment.Mar 19 2021, 3:45 PM

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 added inline comments.
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 added inline comments.Sat, Mar 20, 2:20 PM
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 added inline comments.Sat, Mar 20, 3:35 PM
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 updated this revision to Diff 332378.Mon, Mar 22, 11:47 AM
cjdb marked an inline comment as done.

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.

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 added inline comments.Tue, Mar 23, 12:26 PM
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 added inline comments.Tue, Mar 23, 1:11 PM
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 added inline comments.Tue, Mar 23, 1:23 PM
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.

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 added inline comments.Wed, Mar 24, 10:50 AM
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 falsehttps://godbolt.org/z/b83665obM — because actually it has undefined behavior. Concepts don't close every wild-west loophole in C++.

cjdb updated this revision to Diff 333046.Wed, Mar 24, 10:50 AM

gets gcc working

cjdb updated this revision to Diff 333055.Wed, Mar 24, 11:01 AM

further changes

cjdb marked 6 inline comments as done.Wed, Mar 24, 11:08 AM
cjdb added inline comments.
libcxx/test/std/concepts/comparison/types.h
9 ↗(On Diff #332378)

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

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 marked 3 inline comments as done.Fri, Mar 26, 12:13 PM
cjdb added inline comments.
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)
cjdb updated this revision to Diff 333606.Fri, Mar 26, 12:14 PM
cjdb marked an inline comment as done.

applies some of @zoecarver's feedback

cjdb updated this revision to Diff 333703.Sat, Mar 27, 5:15 PM
cjdb marked 3 inline comments as done.

s/__const_lvalue_reference/__make_const_lvalue_reference/g

cjdb added a comment.Sat, Mar 27, 5:16 PM

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 added inline comments.Mon, Mar 29, 7:46 PM
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 accepted this revision as: Mordante.Wed, Mar 31, 10:54 AM

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 updated this revision to Diff 334547.Wed, Mar 31, 2:56 PM
cjdb marked 4 inline comments as done.

applies @zoecarver's suggestion

cjdb added a comment.Wed, Mar 31, 2:56 PM

Completes feedback.

Quuxplusone resigned from this revision.Wed, Mar 31, 3:28 PM
Quuxplusone added inline comments.
libcxx/test/std/concepts/concepts.compare/concepts.totallyordered/totally_ordered.pass.cpp
79

Wrong formatting.

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 added inline comments.Thu, Apr 1, 10:04 PM
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 accepted this revision.Thu, Apr 1, 10:13 PM

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.

This revision is now accepted and ready to land.Thu, Apr 1, 10:13 PM

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

cjdb marked 6 inline comments as done.Thu, Apr 1, 11:07 PM

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

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 updated this revision to Diff 334897.Thu, Apr 1, 11:07 PM
cjdb marked 2 inline comments as done.

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

This revision was landed with ongoing or failed builds.Thu, Apr 1, 11:18 PM
This revision was automatically updated to reflect the committed changes.
ldionne added inline comments.Thu, Apr 8, 1:33 PM
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.