Page MenuHomePhabricator

[libc++] Implement [P0769] "Add shift to algorithm" (shift_left, shift_right)

Authored by Quuxplusone on Dec 25 2020, 11:26 PM.



I believe this is a complete implementation of std::shift_left and std::shift_right from

Some test cases copied-with-modification from D60027.

Diff Detail

Event Timeline

Quuxplusone created this revision.Dec 25 2020, 11:26 PM
Quuxplusone requested review of this revision.Dec 25 2020, 11:26 PM
Herald added a reviewer: Restricted Project. · View Herald TranscriptDec 25 2020, 11:26 PM

Rebased on main. @ldionne ping! :)

ldionne requested changes to this revision.Jan 11 2021, 2:56 PM

Can you also grab the tests from Generally speaking, while programmatic tests (like the two nested loops you used) are great because it gives us great coverage, however I try to strike a balance and also have at least some basic and really dumb test cases written entirely manually. This avoids the risk of a bug in the tests.

For some reason, that revision doesn't show up in the "Open Libc++ Reviews" query. I'll try to understand why and fix it.


int k = 0;

This revision now requires changes to proceed.Jan 11 2021, 2:56 PM
Quuxplusone edited the summary of this revision. (Show Details)

Merged some test cases from D60027.

zoecarver accepted this revision.Jan 11 2021, 5:11 PM

@Quuxplusone I like this patch a lot better than mine. It seems like this implementation is essentially following the sample in the paper. I was meaning to update mine to use that approach but didn't find the time/remember. Anyway, this looks good to me, thanks!

ldionne requested changes to this revision.Jan 18 2021, 2:29 PM

I'm not done with the review, but I figured I might as well give you the feedback I have right away.

It generally looks good, but I think you might have forgotten about n < 0 in both algorithms.


shift_right isn't constexpr in the paper (haven't looked at why yet). We're not allowed to add this as an extension.


Just constexpr should be OK, since this is only enabled after C++17 anyway.


Should we use n <= 0 here instead? This would make it clearer that nothing happens when n < 0.

And actually, it seems to me that the random access iterator path doesn't behave correctly when n < 0. Indeed, we'll move [__first + __n, __last) (where __first + __n lies *before* __first since __n is negative) into __first. If I'm not mistaken, please fix and add tests for this to both algorithms.


inline is unnecessary here, a template already has the right linkage. Applies above too.


If __n is negative, __m is out-of-bounds, and the call to move_backwards is UB anyway because last is inside (first, m]. Please fix and add tests to cover this case.


Do you mean an __n-element window [__trail, __lead) instead (half-open interval)?


Note to self: haven't reviewed this in detail yet.


Remove constexpr

This revision now requires changes to proceed.Jan 18 2021, 2:29 PM
Quuxplusone marked 7 inline comments as done.Jan 18 2021, 4:01 PM
Quuxplusone added inline comments.

The P-numbered paper doesn't match what was actually landed in .
What was landed looks vastly more "C++ library-esque": constexpr in the right places, more UB instead of special-case defined behavior, etc.

3274 n >= 0 is a precondition on both algorithms.


This is how all of the algorithms are done, though, from all_of on line 852 all the way to prev_permutation on line 5840. I don't know why they all use inline, but shift_right shouldn't be a special case.

3310 n >= 0 is a precondition.


Yes. Also, it's not really "sliding"; it's kind of... leapfrogging? Glitching? We process the window [0, n) and then [n, 2*n) and then [2*n, 3*n) and so on. So this description is already kind of askew. But I'll happily change ( to [, anyway.


Not done because I assume this comment was based on the P-numbered paper (the standard standard does have constexpr)

Quuxplusone marked 5 inline comments as done.


ldionne accepted this revision.Jan 25 2021, 8:18 AM

The P-numbered paper doesn't match what was actually landed in .

Ah ah. How confusing. Now it makes more sense.

This revision is now accepted and ready to land.Jan 25 2021, 8:18 AM