This is an archive of the discontinued LLVM Phabricator instance.

[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
114

could you please update the RangeAlgorithms.csv file?

libcxx/include/__algorithm/ranges_prev_permutation.h
40–62

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

55

std::move(__last)

59

std::move(__last)

libcxx/test/support/test_iterators.h
758

take the arguments by const ref, as indirectly_swappable requires const

760

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
40–62

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

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

760

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
123

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

libcxx/include/__algorithm/ranges_prev_permutation.h
40–62

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
736

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
45

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

63

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()?

140

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

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

758

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

763

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

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

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

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

ldionne added inline comments.
libcxx/include/__algorithm/ranges_prev_permutation.h
40–62

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