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

[Quuxplusone]

Summary

I believe this is a complete implementation of std::shift_left and std::shift_right from
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0769r2.pdf

Some test cases copied-with-modification from D60027.

[Quuxplusone]

Rebased on main. @ldionne ping! :)

[ldionne]

Can you also grab the tests from https://reviews.llvm.org/D60027? 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.

libcxx/test/std/algorithms/alg.modifying.operations/alg.shift/shift_left.pass.cpp

33

int k = 0;

[Quuxplusone]

Merged some test cases from D60027.

[zoecarver]

@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]

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.

libcxx/include/algorithm

310

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

3269

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

3274

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.

3296

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

3310

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.

3331

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

3336–3361

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

libcxx/test/std/algorithms/alg.modifying.operations/alg.shift/shift_right.pass.cpp

15

Remove constexpr

[Quuxplusone]

libcxx/include/algorithm

310

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

3274

http://eel.is/c++draft/alg.shift n >= 0 is a precondition on both algorithms.

3296

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

http://eel.is/c++draft/alg.shift n >= 0 is a precondition.

3331

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.

libcxx/test/std/algorithms/alg.modifying.operations/alg.shift/shift_right.pass.cpp

15

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

[Quuxplusone]

(->[
_LIBCPP_CONSTEXPR_AFTER_CXX17->constexpr

[ldionne]

The P-numbered paper doesn't match what was actually landed in http://eel.is/c++draft/alg.shift .

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