Page MenuHomePhabricator

[libc++][ranges] Implement `ranges::{prev, next}_permutation`
ClosedPublic

Authored by var-const on Jul 15 2022, 8:12 AM.

Diff Detail

Event Timeline

philnik created this revision.Jul 15 2022, 8:12 AM
Herald added a project: Restricted Project. · View Herald TranscriptJul 15 2022, 8:12 AM
Herald added a subscriber: mgorny. · View Herald Transcript
philnik requested review of this revision.Jul 15 2022, 8:12 AM
Herald added a project: Restricted Project. · View Herald Transcript
Herald added a reviewer: Restricted Project. · View Herald Transcript
huixie90 added inline comments.Jul 15 2022, 10:36 AM
libcxx/include/CMakeLists.txt
116

could you please update the RangeAlgorithms.csv file?

libcxx/include/__algorithm/ranges_prev_permutation.h
41–63

I think this algorithm is complex enough to reuse the classic one. what do you think?

56

std::move(__last)

60

std::move(__last)

libcxx/test/support/test_iterators.h
758 ↗(On Diff #444987)

take the arguments by const ref, as indirectly_swappable requires const

760 ↗(On Diff #444987)

why does the rhs counter not incremented?

philnik updated this revision to Diff 445453.Jul 18 2022, 4:26 AM
philnik marked 6 inline comments as done.
  • Address comments
libcxx/include/__algorithm/ranges_prev_permutation.h
41–63

I think it's harder to combine the two than to use separate ones. The algorithms isn't that long, and I would have to teach reverse to dispatch between versions. If that changes we can still think about combining the two.

libcxx/test/support/test_iterators.h
758 ↗(On Diff #444987)

Weird that this didn't show in the test. Maybe I just missed it.

760 ↗(On Diff #444987)

Because that would increment the counter two times per swap.

var-const requested changes to this revision.Jul 19 2022, 10:42 AM
var-const added inline comments.
libcxx/include/CMakeLists.txt
127

Looks like this line is unsorted (might be what the CI is complaining about).

libcxx/include/__algorithm/ranges_prev_permutation.h
41–63

I'd also prefer reuse, but don't want to block this patch on this.

46

Nit: can you add a blank line before this line?

49

Nit: blank line above.

54

Nit: blank line above.

58

Nit: blank line above.

72

Nit: move?

libcxx/include/algorithm
878

Please also add the definition of the result types to the synopsis.

libcxx/test/std/algorithms/alg.sorting/alg.permutation.generators/ranges.next_permutation.pass.cpp
46

Does the argument have to be forwarded, perhaps? (here and in the other concept above)

64

There's a bunch of references to prev_permutation here. I presume this is simply a copy-pasting issue? (if there's a reason to test them here, please point it out)

122

Question: why is static_assert here instead of the common pattern of asserting test() in main()?

141

return 0; (unless something changed recently in that regard)

libcxx/test/std/algorithms/alg.sorting/alg.permutation.generators/ranges.prev_permutation.pass.cpp
92

Is the output of prev_permutation deterministic? If yes, I'd prefer several simple test cases that check the exact output.

libcxx/test/support/test_iterators.h
755 ↗(On Diff #445453)

Nit: this creates an object with uninitialized variables (counter_ and potentially iter_), maybe value-initialize those?

758 ↗(On Diff #445453)

Would it be possible to just inherit from Iter and add the constructor and the iter_swap specialization in the derived class?

763 ↗(On Diff #445453)

(I wish we had something like Boost.Iterator to cut down on this boilerplate. Of course, it's not related to this patch)

This revision now requires changes to proceed.Jul 19 2022, 10:42 AM
philnik updated this revision to Diff 446091.Jul 20 2022, 2:42 AM
philnik marked 11 inline comments as done.
  • Address comments
libcxx/test/std/algorithms/alg.sorting/alg.permutation.generators/ranges.next_permutation.pass.cpp
46

I don't think so, since {prev, next}_permutation only supports copyable iterators/ranges.

122

The static_asserts are here because putting them anywhere else would hit the constant evaluation step limit.

libcxx/test/std/algorithms/alg.sorting/alg.permutation.generators/ranges.prev_permutation.pass.cpp
92

Yes, the output is deterministic. This test checks the exact output of prev_permutation. It checks after every call to ranges::prev_permutation that it's lexicographically less than the input. It's also checked that there were N! rounds. Since there are N! permutations of a range, every input to prev_permutation has to have resulted in the permutation before the input.

libcxx/test/support/test_iterators.h
755 ↗(On Diff #445453)

These are uninitialized on purpose. Algorithms aren't allowed to read from a default-constructed allocator and the tests always have to provide one. If these are uninitialized for any reason the constexpr tests will fail. That wouldn't be the case if I value-initialized them.

758 ↗(On Diff #445453)

Inheriting wouldn't work with raw pointers. (inheriting was actually my initial design)

ldionne added inline comments.
libcxx/include/__algorithm/ranges_prev_permutation.h
41–63

I think we should reuse. Teaching reverse about _AlgPolicy should be trivial.

libcxx/test/std/algorithms/alg.sorting/alg.permutation.generators/ranges.prev_permutation.pass.cpp
92

I think this is a clever way to test this. Maybe a little bit too clever to be the only test we have. I'd be OK with this approach if it were also augmented with a small number (e.g. 10 with boundary conditions) of explicit input/output comparisons. Does that sound reasonable?

Also, a comment explaining what the testing methodology here would be really helpful.

var-const retitled this revision from [libc++] Implement ranges::{prev, next}_permutation to [libc++][ranges] Implement `ranges::{prev, next}_permutation`.Jul 30 2022, 4:25 PM
var-const commandeered this revision.Jul 30 2022, 7:10 PM
var-const edited reviewers, added: philnik; removed: var-const.
var-const marked 2 inline comments as done.Jul 31 2022, 1:11 AM
var-const added inline comments.
libcxx/test/std/algorithms/alg.sorting/alg.permutation.generators/ranges.prev_permutation.pass.cpp
92

I refactored this function into several and added comments. However, it adds a lot of complexity and takes a while to run (I had to increase the number of constexpr steps and reduce the length of the input array since the growth factor is factorial).

var-const updated this revision to Diff 448841.Jul 31 2022, 1:39 AM
var-const marked an inline comment as done.
  • Make ranges::{next,prev}_permutation delegate to the classic algorithm;
  • modify the classic {next,prev}_permutation and their dependencies to support _AlgPolicy;
  • refactor and comment the test functions that run all possible permutations of a given sequence;
  • increase the constexpr evaluation step limit for the new tests and move the static_assert back to main like in most other tests;
  • add test cases with expected output;
  • add tests for a custom predicate and a custom projection;
  • remove the SwapCountingIterator and replace its usages with the existing adl::Iterator::TrackSwaps.
var-const updated this revision to Diff 448901.Jul 31 2022, 6:37 PM

Reduce the input size used for the exhaustive permutation checks to avoid
hitting constexpr step limit in Clang; remove the Clang command-line option
because it's unrecognized by GCC.

var-const updated this revision to Diff 448909.Jul 31 2022, 8:47 PM

Fix the CI.

var-const updated this revision to Diff 448936.Aug 1 2022, 12:52 AM

Fix the CI.

ldionne accepted this revision.Aug 2 2022, 2:28 PM
ldionne added inline comments.
libcxx/test/std/algorithms/alg.sorting/alg.permutation.generators/ranges.prev_permutation.pass.cpp
88

Applies in a few places.

This revision is now accepted and ready to land.Aug 2 2022, 2:28 PM
var-const marked an inline comment as done.Aug 2 2022, 10:44 PM
This revision was automatically updated to reflect the committed changes.

There are still a few tests for these commented out, e.g. in:
libcxx/test/std/algorithms/ranges_robust_against_dangling.pass.cpp
libcxx/test/std/algorithms/ranges_robust_against_proxy_iterators.pass.cpp
libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp

There are still a few tests for these commented out, e.g. in:
libcxx/test/std/algorithms/ranges_robust_against_dangling.pass.cpp
libcxx/test/std/algorithms/ranges_robust_against_proxy_iterators.pass.cpp
libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp

Thanks! I plan to uncomment any remaining ones in a dedicated patch once all the remaining algorithms land.

There are still a few tests for these commented out, e.g. in:
libcxx/test/std/algorithms/ranges_robust_against_dangling.pass.cpp
libcxx/test/std/algorithms/ranges_robust_against_proxy_iterators.pass.cpp
libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp

Thanks! I plan to uncomment any remaining ones in a dedicated patch once all the remaining algorithms land.

Follow-up: https://reviews.llvm.org/D131235