ACP: slice shift_move

[edwloef]

Proposal

Problem statement

I propose adding a method to efficiently move an element in a slice from one index to another, while shifting the rest of the elements to fill the gap. In effect, swap and shift_move could be understood to be counterpart to Vec's swap_remove and remove.

Motivating examples or use cases

• changing the layering order of a floating window in mayland (unimplemented, similar usage in smithay)
• reordering drag-and-droppable elements in graphical user interfaces (example: dragking)

Solution sketch

impl<T> [T] {
    pub fn shift_move(&mut self, from: usize, to: usize) {
        if from > to {
            self[to..=from].rotate_right(1);
        } else {
            self[from..=to].rotate_left(1);
        }
    }
}

Alternatives

• In a Vec you can remove the from index and insert it into the to index afterwards, however this is more expensive than shift_move, and the compiler fails to optimize out allocation checks.

• This is written with existing API's, however I believe including this functionality would still be useful. It's very simple to implement, however using such a function provides much clearer intent, is much more discoverable than its implementation, and to me seems too small to justify its own crate.

Links and related work

• internals: https://internals.rust-lang.org/t/idea-shift-move-to-efficiently-move-elements-in-a-vec/22184
• IndexMap includes a similar function move_index (added in Add move_index to change the position of an entry indexmap-rs/indexmap#176). Maybe there could be discussion whether shift_move or move_index is the better-suited name?
• The initial version proposed in the internals link is no longer necessary since optimize slice::ptr_rotate for small rotates rust#135847

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.

[joshtriplett]

We discussed this in today's @rust-lang/libs-api meeting. We didn't have consensus to add this:

• We felt it was a little niche, and could exist in a library (or a helper function in programs that need it).
• The name wasn't necessarily self-explanatory, and we couldn't come up with an obvious name that was self-explanatory.
• It could lead to quadratic behavior if misused.
• We felt that many applications using this would know which direction they needed to rotate (and would often be going to the beginning or end).

[scottmcm]

Parent calls this slide, FWIW: https://youtu.be/qH6sSOr-yk8?t=560

That also points out that the correct signature includes returning the Range where everything ended up.

But I agree that it doesn't necessarily need to be added to the library. It was a motivating example for why the rotates were added originally, but the combinations of other algorithms -- like the gather example he talks about in the video -- are always harder to know where to stop, so leaving them out is a better default.