This is an archive of the discontinued LLVM Phabricator instance.

[libc++][ranges] Implement `ranges::is_permutation`
ClosedPublic

Authored by var-const on Jun 7 2022, 2:36 AM.

Details

Diff Detail

Event Timeline

philnik created this revision.Jun 7 2022, 2:36 AM
Herald added a project: Restricted Project. · View Herald TranscriptJun 7 2022, 2:36 AM
Herald added a subscriber: mgorny. · View Herald Transcript
philnik requested review of this revision.Jun 7 2022, 2:36 AM
Herald added a project: Restricted Project. · View Herald TranscriptJun 7 2022, 2:36 AM
Herald added a reviewer: Restricted Project. · View Herald Transcript
var-const requested changes to this revision.Jun 9 2022, 6:58 PM
var-const added inline comments.
libcxx/docs/Status/RangesAlgorithms.csv
31–36

Missing link.

libcxx/include/__algorithm/is_permutation.h
122

Question: using __invoke slightly changes the behavior of the non-ranges version of the algorithm as well, right?

213–214

Optional: can you use using like other similar places that were refactored in this patch?

libcxx/include/__algorithm/ranges_is_permutation.h
27

Please add the language version/no incomplete ranges guard.

45

Nit: please move the iterators (and add the include).

55

Can we do the same optimization in the iterator version (by checking sized_sentinel_for)?

60

Should this go to the else branch of the if constexpr?

libcxx/include/algorithm
1797

Missing synopsis.

libcxx/test/std/algorithms/alg.nonmodifying/alg.is_permutation/ranges.is_permutation.pass.cpp
9

Missing synopsis.

88

Please also check with a single-element range.

96

Nit: there's an unnecessary blank line.

110

Please also add test cases that use a non-default projection or a non-default predicate.

191

Should be ranges of different sizes or similar. Also, is there a reason that these test cases aren't part of the test function?

This revision now requires changes to proceed.Jun 9 2022, 6:58 PM
philnik marked 4 inline comments as done.Jun 21 2022, 6:30 AM
philnik added inline comments.
libcxx/include/__algorithm/is_permutation.h
122

Any changes to the behaviour should be negated by the __is_callable check.

var-const commandeered this revision.Jul 29 2022, 11:09 PM
var-const edited reviewers, added: philnik; removed: var-const.
var-const retitled this revision from [libc++] Implement ranges::is_permutation to [libc++][ranges] Implement `ranges::is_permutation`.Jul 29 2022, 11:13 PM

Changes to is_permutation.h:

  • refactor out the common part of __is_partition overloads taking 3 and 4 iterators;
  • rename __is_partition to __is_partition3 and __is_partition4 depending on the number of iterators;
  • to optimize __is_partition for constant-time distance, replace the existing tag dispatch based on iterator category with a custom trait. This works with ranges and covers more cases in C++20 mode;
  • fix the bug in the optimization above which would prevent it from being selected by overload resolution (incorrect iterator types in the signature) unless all iterator types are the same;
  • use _IterOps in __is_partition;
  • other miscellaneous cleanup.

Changes to the tests:

  • check SFINAE on the predicate;
  • add tests for a custom predicate;
  • add tests for a custom projection;
  • add more complexity tests and use counting_{projection,predicate};
  • add a couple more test cases.

Also address the existing feedback and rebase on main.

var-const added inline comments.Jul 29 2022, 11:22 PM
libcxx/include/__algorithm/is_permutation.h
154–155

I think this was a bug -- the type of __last1 should be _RandomAccessIterator1, not 2. This would only work if both iterator types are the same, IIUC.

Test the constant-time distance optimization with different iterator types.

var-const updated this revision to Diff 448788.Jul 30 2022, 2:31 AM

Reduce the number of iterations in constexpr std::sort tests to prevent
Clang from exceeding the maximum step limit.

var-const updated this revision to Diff 448789.Jul 30 2022, 2:39 AM

Increase the constexpr evaluation steps limit on constexpr std::sort tests;
now that there is one extra function in the is_permutation call stack, it
started to exceed the default limit.

var-const updated this revision to Diff 448812.Jul 30 2022, 2:36 PM

Fix the CI.

var-const updated this revision to Diff 448820.Jul 30 2022, 4:13 PM

Fix the CI.

var-const updated this revision to Diff 448842.Jul 31 2022, 1:52 AM

Fix the CI and rebase.

var-const updated this revision to Diff 449180.Aug 1 2022, 8:41 PM

"Fix" the constexpr step limit again.

ldionne requested changes to this revision.Aug 2 2022, 2:11 PM
ldionne added inline comments.
libcxx/include/__algorithm/is_permutation.h
34–63

Is this #if wrong, or is the #endif comment wrong?

59

I would suggest naming this __is_permutation_impl or something like that. I think it expresses most clearly what the function actually does.

Otherwise, I was trying to understand how it was different from std::equal_range (which has very little in common).

100

Here and elsewhere.

101–107

FWIW I think this is a reimplementation of std::mismatch.

I don't mind whether we refactor this now or after (or not at all if it turns out not to be a good idea). But we should at least look into it.

175–181

Instead, why not have just two versions of __is_permutation4 and use enable_if_t? I don't think you need this function at all.

libcxx/include/__algorithm/ranges_is_permutation.h
42

I would suggest looking into naming __is_permutation4 and __is_permutation3 just __is_permutation. That way, they can be called as std::__is_permutation<Policy>, which is nicely consistent with what we do for other algorithms.

69–72

Is this still needed here, or do we handle this in __is_permutation?

This revision now requires changes to proceed.Aug 2 2022, 2:11 PM
var-const updated this revision to Diff 449922.Aug 4 2022, 3:20 AM
var-const marked 6 inline comments as done.

Address feedback.

var-const added inline comments.Aug 4 2022, 3:22 AM
libcxx/include/__algorithm/is_permutation.h
34–63

Fixed. I think the #if is correct -- we only guard sized_sentinel_for with the language version, so it's okay to use regardless of whether ranges are enabled, and it covers more cases than the more simplistic check in the #else branch.

101–107

I'd like to try it out, but would leave it to a follow-up patch.

175–181

The _ConstTimeDistance == true overload relies on the ability to delegate to the _ConstTimeDistance == false overload (which is easy because it can pass false_type directly instead of using the trait). It seems like it would be more difficult to achieve with enable_if (unless there's some approach I didn't think of).

libcxx/include/__algorithm/ranges_is_permutation.h
42

Done. I found myself getting confused between all the different overloads, but it's a good point that having a single name would be consistent with other algorithms.

69–72

Unfortunately, I think it's still necessary. It's possible for the range to be a sized_range without the sentinel satisfying sized_sentinel_for -- e.g. the range type could define size() member function but the sentinel is just a forward iterator that doesn't support subtracting (on which sized_sentinel_for relies).

ldionne accepted this revision.Aug 4 2022, 5:43 AM
This revision is now accepted and ready to land.Aug 4 2022, 5:43 AM
This revision was automatically updated to reflect the committed changes.

That was the last algorithm in RangesAlgorithms.csv - congratulations! :)

That was the last algorithm in RangesAlgorithms.csv - congratulations! :)

Thank you! There are more range algorithms added in C++23, but we're now finished with what was in the original One Ranges Proposal.