Page MenuHomePhabricator

[libc++] [P0202] constexpr set_union, set_difference, set_symmetric_difference, merge
ClosedPublic

Authored by Quuxplusone on Nov 27 2020, 7:17 PM.

Details

Summary

These had been waiting on the ability to use std::copy from constexpr code (which in turn had been waiting on the ability to use is_constant_evaluated() to switch between memmove and non-memmove implementations of std::copy). That work landed a while ago, so these algorithms can all be constexpr in C++20 now.

While I'm in the area, update the tests. (This part has scope-crept a ton.)

According to my research, here are the remaining algorithms that P0202+P0879 marked "constexpr," which are still not implemented as "constexpr" by libc++. We'd have to implement these before we could advertise the __cpp_lib_constexpr_algorithms feature-test macro:

reverse partition sort nth_element next_permutation prev_permutation
push_heap pop_heap make_heap sort_heap partial_sort partial_sort_copy

Diff Detail

Event Timeline

Quuxplusone created this revision.Nov 27 2020, 7:17 PM
Herald added a reviewer: Restricted Project. · View Herald TranscriptNov 27 2020, 7:17 PM
Quuxplusone requested review of this revision.Nov 27 2020, 7:17 PM
zoecarver added inline comments.Nov 27 2020, 9:36 PM
libcxx/test/std/algorithms/alg.sorting/alg.merge/merge.pass.cpp
40 ↗(On Diff #308132)

I think the previous version was a bit easier to read. Especially if we have a dozen assertions in some test function, we can't use this method, and in my opinion, it would be better to make these uniforms.

libcxx/test/std/algorithms/alg.sorting/alg.set.operations/includes/includes_comp.pass.cpp
25–26

Can we make this test constexpr too?

libcxx/test/std/algorithms/alg.sorting/alg.set.operations/set.difference/set_difference.pass.cpp
26 ↗(On Diff #308132)

What I'd really like to do is rather than adding a test_constexpr function, simply modify the existing "test" function to be constexpr and return true at the end. If there's an assertion that fires while the constexpr is being evaluated, it will no longer be a valid constexpr and therefore will fail to compile. I think we agreed we should (as much as possible) try to have the same tests for constexpr and non-constexpr.

Address review comments on constexprifying includes*.pass.cpp, and on assert(X); return true; versus return X;.

Quuxplusone marked 2 inline comments as done.Nov 28 2020, 7:39 AM
Quuxplusone added inline comments.
libcxx/test/std/algorithms/alg.sorting/alg.set.operations/includes/includes_comp.pass.cpp
25–26

It turns out that we can! So in the latest revision of this PR, I'm proposing that in the specific case of std::includes, we can eliminate test_constexpr and do everything in test.

libcxx/test/std/algorithms/alg.sorting/alg.set.operations/set.difference/set_difference.pass.cpp
26 ↗(On Diff #308132)

Yes, we should try to have the same tests run for constexpr and non-constexpr. My nod to that in this PR is to have all the main routines call both assert(test_constexpr()) and static_assert(test_constexpr()). In general I didn't mess with the existing non-constexpr tests, except to change the _comp versions to pass a non-default comparator.

The stumbling block for messing with the existing non-constexpr tests is that we have to be careful not to break them in C++03 mode, which means no C++11-isms.

The existing tests also leave a lot to be desired — e.g. they don't test at all with non-trivially-copyable types — so I was also semi-consciously operating in the mode of "Someone will have to fix these tests later, but it doesn't have to be me right now." ;) I suppose I could scope-creep this PR to "rewrite all the set-combination-algo tests at the same time," and/or volunteer to write a followup PR for that.

(But if we're going to rewrite the set-algo tests, we should do it not before landing the missing constexpr set algos that are included in this PR. I don't want a period where the set_union tests have to look gratuitously different from the set_intersection tests. So rewriting the tests should happen either in this PR right here, or in a followup, but not in a prerequisite.)

zoecarver added inline comments.Nov 28 2020, 11:18 AM
libcxx/test/std/algorithms/alg.sorting/alg.set.operations/includes/includes_comp.pass.cpp
25–26

This is great! Let's do this for all the tests.

57

Why is this needed?

89

There's no reason to assert here. The only reason we static_assert in the other one is to force constant evaluation.

libcxx/test/std/algorithms/alg.sorting/alg.set.operations/set.difference/set_difference.pass.cpp
26 ↗(On Diff #308132)

The stumbling block for messing with the existing non-constexpr tests is that we have to be careful not to break them in C++03 mode, which means no C++11-isms.

What C++11-isms are you getting stuck on?

IMHO the tests for this patch should be pretty simple. I think it would be great to improve the tests as you suggested, but I agree, that doesn't need to be part of this patch. I think/hope you can just follow the model in includes.pass.cpp. There's no regression for non-constexpr and we're testing the same thing in both "modes."

Quuxplusone marked an inline comment as done.Nov 28 2020, 12:21 PM
Quuxplusone added inline comments.
libcxx/test/std/algorithms/alg.sorting/alg.set.operations/includes/includes_comp.pass.cpp
25–26

Well, look at the existing "merge.pass.cpp" for example. It's extremely silly. The test for std::includes was really the one special case, where the existing test (was still very silly, but) happened to be constexpr-friendly already.

57

Suppose we remove the guard. And suppose we compile this file as C++14. Then, do_tests is marked constexpr, but it unconditionally calls test<input_iterator<const int*>, input_iterator<const int*>>(), which never returns a compile-time-constant result. My understanding of C++ formalities is that this would make it IFNDR.

Adding the bool parameter makes it probably not IFNDR, since now there's a compile-time-constant path through this function even in C++14.

Constexpr is a huge pain. :P

Could you please update the status page together with the corresponding note (https://libcxx.llvm.org/docs/Cxx2aStatus.html#note-p0202)?

zoecarver added inline comments.Nov 28 2020, 12:47 PM
libcxx/test/std/algorithms/alg.sorting/alg.set.operations/includes/includes_comp.pass.cpp
25–26

What about merge.pass.cpp isn't constexpr friendly? The only thing I see is std::reverse which we should make constexpr anyway, maybe as part of this patch or a different patch that lands before this one. Otherwise, maybe it makes sense to just write out std::reverse inline.

57

I see what you're getting at. std::includes is marked as _LIBCPP_CONSTEXPR_AFTER_CXX17 so let's change TEST_CONSTEXPR_CXX14 to TEST_CONSTEXPR_CXX20 (or whatever the equivalent is).

Quuxplusone added inline comments.Nov 28 2020, 1:06 PM
libcxx/test/std/algorithms/alg.sorting/alg.merge/merge.pass.cpp
75 ↗(On Diff #308164)

@zoecarver: "What about merge.pass.cpp isn't constexpr-friendly?" The use of std::shuffle here, and also perhaps new and delete. ;)

Update the docs.
Make another adjustment to the constexpr stuff in "includes.pass.cpp"; re-upload the diff to poke the buildbot.

curdeius added inline comments.Nov 28 2020, 1:16 PM
libcxx/docs/Cxx2aStatusPaperStatus.csv
7 ↗(On Diff #308188)

Version ?

zoecarver added inline comments.Nov 28 2020, 1:33 PM
libcxx/test/std/algorithms/alg.sorting/alg.merge/merge.pass.cpp
75 ↗(On Diff #308164)

OK, let's make this a fixed-size array so we don't have the new/delete. I don't think there's any reason we need this test to run on 100000 elements.

We could simply replace std::shuffle with:

for (auto i = n-1; i > 0; --i)
  swap(ic[i], ic[randomness() % (i+1)]);

I know this requires a bit of test modification, but I think this is the way we should try to do these tests.

Or, better yet, we could add a test utility random engine that is constexpr.

Quuxplusone marked an inline comment as done.

Updated set_intersection.pass.cpp and set_intersection_comp.pass.cpp to perform all the tests as constexpr in C++20. @zoecarver, I propose to rewrite all of the set-algo tests (union, difference, symmetric_difference, merge) in this same way, using this same small test input, using these custom Trivial and NonTrivial class types. Thoughts?

Quuxplusone marked 6 inline comments as done.Dec 1 2020, 7:53 PM
Quuxplusone edited the summary of this revision. (Show Details)Dec 2 2020, 5:09 PM

I'm fine with the current testing approach, if there's a commitment to go back and use the same tests for both constexpr and non-constexpr after the fact. There's a few algorithms that contain tests using <random> -- those can be split off to a separate function and run in the runtime context only.

Personally, my approach would have been to do the groundwork and make the tests constexpr friendly first, and then submit a patch to actually run them in constexpr context. If you want to proceed the other way around, I'm fine with that. But the test coverage for constexpr algorithms can't be as naive as it is in this patch.

Quuxplusone edited the summary of this revision. (Show Details)
  • Finished updating all the tests.
  • Drive-by update the comment-synopsis in <algorithm> to match what's implemented so far. The one in <numeric> is already up-to-date.

I am no longer "planning changes" on this PR; this is what I'd propose to land, if it meets with approval.

Thanks for all the test overhaul! Probably better done as a follow-up patch, but this format will make it easier to add move-only tests.

libcxx/test/std/algorithms/alg.sorting/alg.merge/merge.pass.cpp
48 ↗(On Diff #309334)

Why do we divide this by 10? Let's make these tests as simple as possible.

Nit: no friend, no pass-by-reference.

libcxx/test/std/algorithms/alg.sorting/alg.merge/merge_comp.pass.cpp
9 ↗(On Diff #309334)

What happened to all the other unsupported compilers?

44 ↗(On Diff #309334)

Can we put these all into a header?

61 ↗(On Diff #309334)

I think these will work in C++03.

Quuxplusone marked 5 inline comments as done.Dec 3 2020, 1:44 PM
Quuxplusone added inline comments.
libcxx/test/std/algorithms/alg.sorting/alg.merge/merge.pass.cpp
48 ↗(On Diff #309334)

Because we want to be able to treat 41 and 42 as "the same" for purposes of set merging, but then distinguish them in lexicographical_compare, to verify that they got merged in the proper order. (E.g., the set_union tests verify that indeed set_union is not commutative.)

libcxx/test/std/algorithms/alg.sorting/alg.merge/merge_comp.pass.cpp
9 ↗(On Diff #309334)

// UNSUPPORTED: clang-8 was good enough for ee95c7020cebe4668a501f24305a76a044df5266, so I expect it's also good enough here.

I strongly suspect that the test harness somehow knows that UNSUPPORTED: clang-8 implies UNSUPPORTED: clang-7 and so on.
I have no particular explanation for what's the deal with apple-clang-9, apple-clang-10.
Alternatively, it's possible that no buildbot runs clang-7 anymore?

44 ↗(On Diff #309334)

We could, but they're small enough that I think that could wait until we want to use them elsewhere.

Also, note that the classes in the comparator tests are deliberately not <-comparable, just to verify that we never accidentally try to use their operator<. So we really have 4 different classes here, not just 2.

Background on my reluctance here: In the process of writing this PR I discovered TrackedValue, which @ldionne wrote back in 2015, put in a header, and then never used again. (I wanted to make NonTrivial just a pair<Trivial, TrackedValue> or something like that; but it turned out that TrackedValue wasn't constexpr, so I couldn't use it anyway.)

61 ↗(On Diff #309334)

Officially, neither static_assert nor is_trivially_copyable are present in C++11. test/libcxx/containers/sequences/vector.bool/trivial_for_purposes_of_call.pass.cpp is unsupported in C++03 and I can't see any reason it would be unsupported except for its reliance on the is_trivially_ type-traits.

zoecarver added inline comments.Dec 3 2020, 1:57 PM
libcxx/test/std/algorithms/alg.sorting/alg.merge/merge_comp.pass.cpp
61 ↗(On Diff #309334)

libc++ provides many of these things in C++03. Even rvalues and variadics work.

zoecarver added inline comments.Dec 3 2020, 2:06 PM
libcxx/test/std/algorithms/alg.sorting/alg.merge/merge_comp.pass.cpp
44 ↗(On Diff #309334)

It looks like this is used in 10 different places. Yes, it's a small class so maybe we don't want to put it in a header for that reason, but if there's a bug that we need to fix later or something needs to be changed, I'd rather update one header than 10 different test files. Additionally, if there is a bug that is only revealed in one of the tests, the other nine classes won't be updated. @ldionne what do you think?

ldionne added inline comments.Dec 4 2020, 7:56 AM
libcxx/test/std/algorithms/alg.sorting/alg.merge/merge_comp.pass.cpp
9 ↗(On Diff #309334)

Alternatively, it's possible that no buildbot runs clang-7 anymore?

That's it. The test harness does not do anything special w.r.t. clang versions. It couldn't, because a bug could exist in clang-7 but not clang-6, so it would be invalid to assume that the clang-7 Lit feature implies the clang-6 Lit feature, for example. The truth is that nobody cares about libc++ "working" with several of the compilers we claim to support. For example, I doubt anyone really builds libc++ with GCC 5, except perhaps in some fake CI setups -- but nobody actually ships that, and I'd be scared if they did.

44 ↗(On Diff #309334)

I think I would put them in a header e.g. in test/std/algorithms/alg.sorting/ so that they are shared across these tests. Lifting the utilities all the way into test/support might not make sense, though, since they are kinda specific to the sort of tests you're trying to write here.

@Quuxplusone @zoecarver Would that make sense to you both?

Quuxplusone marked 5 inline comments as done.Dec 4 2020, 10:08 AM
Quuxplusone added inline comments.
libcxx/test/std/algorithms/alg.sorting/alg.merge/merge_comp.pass.cpp
44 ↗(On Diff #309334)

I still think it's unnecessary, but I don't object. Of course, the naming part is hard. I propose (and will update the PR with, unless someone stops me) "alg.sorting/sortable_helpers.h" containing TrivialSortable/NonTrivialSortable and TrivialSortableWithComp/NonTrivialSortableWithComp.

I still feel moderately strongly that TrivialSortableWithComp/NonTrivialSortableWithComp should not have a well-formed operator<, and so must remain a different pair of classes from the former two. It'd be easy enough to give the T::less comparator some different behavior from T::operator<, so that if the algo accidentally used the wrong one, the test would detect that bug at runtime; but, it wouldn't be able to detect a bug in which the algo was wrongly constrained to require operator<, unless we actually instantiate the algo with a non-operator<-comparable type.

61 ↗(On Diff #309334)

I'll update the patch and see what buildkite thinks of it.

ldionne added inline comments.Dec 4 2020, 10:24 AM
libcxx/test/std/algorithms/alg.sorting/alg.merge/merge_comp.pass.cpp
44 ↗(On Diff #309334)

I propose (and will update the PR with, unless someone stops me) "alg.sorting/sortable_helpers.h" containing TrivialSortable/NonTrivialSortable and TrivialSortableWithComp/NonTrivialSortableWithComp.

That sounds good to me. I think it's reasonably important to reduce copy/paste in the test suite. There's a lot of it, and it tends to get out of sync.

Note that I'm not trying to say we should create reusable abstractions for all tests, all the time. I don't want TrivialSortableWithComp & friends to be thought of as reusable abstractions. I just want to regroup where the code lives in a single place, so that when we change it in one location, everywhere gets the change.

I still feel moderately strongly that TrivialSortableWithComp/NonTrivialSortableWithComp should not have a well-formed operator<

We agree.

Quuxplusone marked an inline comment as done.

Pull out the helper "sortable element" classes into "sortable_helpers.h".

ldionne accepted this revision.Dec 4 2020, 10:41 AM

This LGTM if CI passes. However, since there's a bunch of stuff unrelated to the primary concern of the patch (which is to implement P0202), can you please split it up into separate commits? Ideally, those would have been separate reviews from the start to make it easier, but now the patch has been reviewed, so I guess there's no point in splitting it :-) For the commits, I suggest:

  1. A NFC commit to update the synopsis of stuff that had gotten out of date
  2. A commit to update includes.pass.cpp
  3. A commit with the rest, which actually implements P0202

I won't bite if you want to land everything at once, though. I'm mostly trying to make an example to make sure we keep this in mind for future libc++ patches.

Also, I think we could improve the test coverage of all those algorithms by testing a wider array of inputs. I don't request that you do that, but if you do feel like doing it, the patch will be welcome. Thanks for the work!

This revision is now accepted and ready to land.Dec 4 2020, 10:41 AM
zoecarver accepted this revision.Dec 4 2020, 11:05 AM

I'm good with landing this now. I would kind of like to make the tests a little less complicated, but I think they're OK as-is.

libcxx/test/std/algorithms/alg.sorting/sortable_helpers.h
34 ↗(On Diff #309574)

Super nit: I feel like it's a bit cleaner to say:

TEST_CONSTEXPR bool operator<(NonTrivialSortable b) {
  return value / 10 < b.value / 10;
}

No friend; no reference.

Grr, the sortable elements' operator= must be TEST_CONSTEXPR_CXX14 instead of TEST_CONSTEXPR. But then I think we'll be good to go!

b0eed2d079b2 (HEAD -> D92255) [libc++] Update the commented "synopsis" in <algorithm> to match current reality.
6501f415622b [libc++] [P0202] constexpr set_union, set_difference, set_symmetric_difference, merge
92832f000c0f [libc++] Slightly improve constexpr test coverage for std::includes.
libcxx/test/std/algorithms/alg.sorting/sortable_helpers.h
34 ↗(On Diff #309574)

I like hidden-friend, though, so I won't change it. Let someone else do that later if they want to. ;)
(Hidden-friend is also a tiny bit harder to screw up by forgetting a const, IMVHO, because it treats both parameters the same.)