Page MenuHomePhabricator

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

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

Details

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.

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 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;

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.

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

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.
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 marked 5 inline comments as done.

(->[
_LIBCPP_CONSTEXPR_AFTER_CXX17->constexpr

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

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.

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