This is an archive of the discontinued LLVM Phabricator instance.

[libc++][ranges] Implement `ranges::rotate`.
ClosedPublic

Authored by var-const on Jul 29 2022, 4:49 AM.

Details

Reviewers
philnik
huixie90
ldionne
Group Reviewers
Restricted Project
Commits
rG36c746ca2d5b: [libc++][ranges] Implement `ranges::rotate`.
Summary

Also fix ranges::stable_sort and ranges::inplace_merge to support
proxy iterators now that their internal implementations can correctly
dispatch rotate.

Diff Detail

Event Timeline

var-const created this revision.Jul 29 2022, 4:49 AM
Herald added a project: Restricted Project. · View Herald TranscriptJul 29 2022, 4:49 AM
Herald added a subscriber: mgorny. · View Herald Transcript
var-const requested review of this revision.Jul 29 2022, 4:49 AM
Herald added a project: Restricted Project. · View Herald TranscriptJul 29 2022, 4:49 AM
Herald added a reviewer: Restricted Project. · View Herald Transcript
var-const updated this revision to Diff 448586.Jul 29 2022, 4:50 AM

Use the actual patch number.

var-const updated this revision to Diff 448589.Jul 29 2022, 5:03 AM

Undo unnecessary change, fix the CI.

libcxx/include/__algorithm/algorithm_family.h
58

While swap_ranges is a very simple algorithm, the range version and the classic version take a different number of parameters (the range version takes __last2 as well). I can try unifying them but not sure if it's worth pursuing.

libcxx/include/__algorithm/move.h
114

The changes to move.h and move_backward.h are essentially to pass around _AlgPolicy to be able to call _IterOps::__iter_move instead of plain std::move(*iter).

libcxx/include/__algorithm/ranges_move.h
39

Now that we dispatch to iter_move, I think it should take care of this case.

libcxx/include/__algorithm/rotate.h
197

The sentinel has to be converted into an iterator early in the call stack to accommodate for the early returns below. This simplifies the other internal functions in this file significantly because they can still accept __last as an iterator and return the same type.

libcxx/include/__iterator/reverse_iterator.h
397

The lack of iter_move was caught by the robust_against_proxy_iterators tests in the implementation of inplace_merge.

var-const updated this revision to Diff 448590.Jul 29 2022, 5:11 AM

Mark the new test as unsupported pre-C++20.

ldionne added inline comments.Jul 29 2022, 8:57 AM
libcxx/include/__algorithm/algorithm_family.h
32

Doesn't it become possible to remove this entirely now that __move accepts a _AlgPolicy? I guess we'd have to also accept an _AlgPolicy in __swap_ranges, and then we can get rid of this and use __swap_ranges<_AlgPolicy> and __move<_AlgPolicy> instead?

34–35

Non blocking, but I don't understand the purpose of this TODO. Isn't that already the case with __move right above?

libcxx/include/__algorithm/rotate.h
192

Why not do class _IterCategory = _IterOps<_AlgPolicy>::__iterator_category since you added it to _IterOps? Then it doesn't need to be passed explicitly when calling __rotate from rotate(), but also from ranges::rotate and from inplace_merge.

In fact, I think you can straight up just call __rotate_impl with the category without even making it a template argument of __rotate.

200–201

Couldn't we instead return _Ret(__last_iter, __last_iter)? That would save us from advancing the iterator all the way to __last twice.

var-const updated this revision to Diff 448764.Jul 29 2022, 7:56 PM
var-const marked 4 inline comments as done.

Address feedback, fix the CI.

libcxx/include/__algorithm/algorithm_family.h
32

Done. Also made ranges::swap_ranges delegate to the internal function.

(I originally hesitated to do that because the ranges and classic versions of swap_ranges take a different number of arguments, but it was easy to accommodate for)

34–35

Thanks for flagging this, this has encouraged me to dig a little more and now it looks like the return value is equivalent; removed the TODO.

Most of the time, the range algorithm returns the same iterator value as the classic algorithm plus an additional value (very often the last iterator); for example, the classic version would return out + N, whereas the ranges version would return {last, out + N}. Thus, it's trivial to convert the ranges result type to classic by simply dropping a value.

In this case, however, the return value is specified differently -- classic version returns last2 and the range version returns first2 + M, where M is defined as min(last1 - first1, last2 - first2). I do think, however, that the two are actually equivalent.

var-const updated this revision to Diff 448765.Jul 29 2022, 7:58 PM

Rebase on main.

Fix the CI.

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

Rebase on main.

ldionne accepted this revision.Aug 2 2022, 2:37 PM
This revision is now accepted and ready to land.Aug 2 2022, 2:37 PM
var-const updated this revision to Diff 449544.Aug 2 2022, 10:39 PM

Rebase on main.

var-const updated this revision to Diff 449613.Aug 3 2022, 2:48 AM

Restart CI.

This revision was automatically updated to reflect the committed changes.