Add `[_]::shift_{left,right}`

[scottmcm]

Proposal

Problem statement

There's currently no efficient and safe way to remove from a slice and insert a replacement value at a different location, in general. It's some easy unsafe code, but it's be nice to offer it in a more optimized version than rotate+replace (since rotate, while linear, is more expensive than `memmove).

Motivating examples or use cases

Inspired by the conversation in #t-libs > `remove_insert() for `Vec`, or more generally for `&mut [T]` @ 💬.

They specifically wanted to optimize remove+insert on a Vec-like type, to avoid two large memmoves when the positions are close by. But this can be done on slice instead, making it more generally applicable as a building block plus simplifing the interface from what was originally discussed there.

Solution sketch

impl<T> [T] {
    pub fn shift_left<const N: usize>(&mut self, inserted: [T; N]) -> [T; N];
    pub fn shift_right<const N: usize>(&mut self, inserted: [T; N]) -> [T; N];
}

Example:

let mut a = [1, 2, 3, 4, 5];
assert_eq!(a.shift_left([7, 8]), [1, 2]);
assert_eq!(a, [3, 4, 5, 7, 8]);

let mut a = [1, 2, 3, 4, 5];
assert_eq!(a.shift_right([7, 8]), [4, 5]);
assert_eq!(a, [7, 8, 1, 2, 3]);

This would be

• trivially a nop for N == 0, just like << 0 and >> 0.
• panic for N > self.len().
• same as self.as_mut_array().replace(inserted) for N == self.len().
• handles the scalar case just fine via .shift_left([3]) without adding overhead.
• always implemented with
  • ptr::read the returned values
  • ptr::copy (overlapping!) the middle N places
  • ptr::write the inserted values
  • none of which can panic, so there's no droppage concerns.
• named to match the existing rotate_left+rotate_right, as the same intuitions apply

Alternatives

• Only support a single value
  • but that makes it less general as a building block, and supporting arrays doesn't make it any less efficient
• Allow passing in the insert/remove positions
  • but that makes the interface more complex (two usizes mean potential confusion over which is which), isn't necessary (since one can always sub-slice the slice), and would add cost in the implementation (which would need to compare the positions and branch to decide what to do)
• Do nothing
  • certainly always possible, since others can write this themselves, but I do think a "safe memmove" is a valuable offering for core

Links and related work

rust-embedded/heapless#635

What happens now?

This issue contains an API change proposal (or ACP) and is part of the libs-api team feature lifecycle. Once this issue is filed, the libs-api team will review open proposals as capability becomes available. Current response times do not have a clear estimate, but may be up to several months.

Possible responses

The libs team may respond in various different ways. First, the team will consider the problem (this doesn't require any concrete solution or alternatives to have been proposed):

• We think this problem seems worth solving, and the standard library might be the right place to solve it.
• We think that this probably doesn't belong in the standard library.

Second, if there's a concrete solution:

• We think this specific solution looks roughly right, approved, you or someone else should implement this. (Further review will still happen on the subsequent implementation PR.)
• We're not sure this is the right solution, and the alternatives or other materials don't give us enough information to be sure about that. Here are some questions we have that aren't answered, or rough ideas about alternatives we'd want to see discussed.

[programmerjake]

a concern that also applies to rotate_left/rotate_right: they should probably be named rotate/shift_towards_start/end since left/right are swapped in RTL languages.

[Darksonn]

A concern is that you can call it on a Vec, but this does not do what I would expect Vec::shift_left() to do.

[MoSal]

@programmerjake

MSB/LSB are not swapped in RTL languages (not the one(s) I'm familiar with anyway).

[programmerjake]

@programmerjake

MSB/LSB are not swapped in RTL languages (not the one(s) I'm familiar with anyway).

this is array order, not bit order.

[programmerjake]

e.g. ‏ [1, 2, 3] ‎ -- I wrote ‏ `[1, 2, 3]` ‎ -- on my computer that renders as [3 ,2 ,1]

[MoSal]

(partially off-topic)

@programmerjake

Fair. I was thinking of memory order, not how [] arrays are represented in a BiDi RTL-dired paragraph.

From what I hear, there is a move, at least in some nations, to teach "Maths" explicitly and exclusively in LTR to remove any confusion, and prepare students for the future. Although the confusion in mind is more about cases like a - b, where you need an explicit ⇒ a - b or a - b ⇐ to disambiguate, especially for those leaning Maths in more than one language.

But in any case, and to avoid going too off-topic. My point was that I don't think native speakers of RTL languages would be really confused about left/right in this context, although start/end is indeed more logically explicit and accurate.

[scottmcm]

they should probably be named rotate/shift_towards_start/end since left/right are swapped in RTL languages.

The last time this came up we ended up saying that that distinction is important for strings but that for slices (and bits) it was fine to continue using left/right.

[kennytm]

this sounds more like a funnel shift operation (i.e. #642) than just a "shift" which I though it would be filled with a constant like T::default().

there is a similar method Simd<T, N>::shift_elements_left::<OFFSET>(Self, T) which pads with a single element

[scottmcm]

I also considered other names like slide_{for,back}ward, but liked the parallel with rotate.

And you can always write .shift_left([0; N]) for something almost the same as << N.

[joshtriplett]

We talked about this in today's @rust-lang/libs-api meeting.

We had the idea that this could potentially be done without panicking, with a well-defined semantic:

let mut arr = [100];
let ret = slice.shift_right([1, 2, 3]);
assert_eq!(arr, [1]);
assert_eq!(ret, [2, 3, 100]);

Our conclusion from the meeting was: if it's possible to do this without appreciable runtime performance impact, we'd love to avoid a panic. If doing this would add runtime performance impact, we're happy to ship the panicking version.

Either way, we're happy to accept this.

[scottmcm]

Tracking issue: rust-lang/rust#151772