Remove panic from rotate_left and rotate_right?

It seems unnessasry to me to have a panic for these functions for slices. Why can they not just wrap around as expected? I did a quick test of the implementations and checked everything worked.

I did the change here: GitHub - spencer3035/rust: Empowering everyone to build reliable and efficient software.

3 Likes

In this case it would be more appropriate to add wrapped methods, like wrapping_rotate_left and wrapping_rotate_right, and maybe a checked variant as well (checked_rotate_left and checked_rotate_right), in analogy to wrapping_add and checked_add for integers in the stdlib.

4 Likes

Removing a documented panic case from standard library APIs because it "seems unnecessary" is a bit like removing the panic from the assert! macro because it "seems unnecessary". Surely, one can just remove that pescy panic assert!(false) produces, as the rest of its implementation doesn't need it, right? No. Users could have been relying on that (documented) panic to make their program safe against invalid states or adverserial inputs!

11 Likes

If you want modulo, you should call it yourself. % by a runtime value is surprisingly expensive -- far more than the easily predicted assert, on modern platforms -- so there's no reason to impose that cost on everyone doing the normal thing of just not making such a big index in the first place.

(Why do you even want to have it wrap? How'd you end up in that scenario?)

3 Likes

What's the reason you think these functions are "expected" to wrap around? What's the difference with, say, slice indexing, which doesn't wrap around?

2 Likes

I think having them wrap around is mathematically reasonable; rotation is a modular operation, where if you rotate a list of N items N times individually, you get back the original list.

I also think the cost of % is still relevant, and additionally the presence of a rotation amount larger than the slice size could easily indicate a bug in a program that’s better complained about than glossed over. Adding % at the call site is possible; removing it from within the callee would only happen via compiler optimization if the rotation amount is a constant.

8 Likes

I find the expectation reasonable; integer rotations (of bits) do have that behaviour in Rust.

I don't quite buy the performance argument either: The panicking behaviour requires branching on n > slice.len() anyway, so making that branch instead compute the remainder and resume wouldn't hurt current code any more than removing an assert!(n <= slice.len()) would.

However, preserving documented stable behaviour seems more important. Are there any other examples where panics on some inputs have been removed later?

edit: Oh, slice rotates actually allow n == v.len() (behaving the same as n == 0), so a rotation not panicking does not even mean the argument is a valid index to the slice.

7 Likes

This, especially because it takes usize.

If you compute the rotation amount in such a way that you get -1 as usize, that will have a jump in the behaviour for any slice length that's not a power of two.

Run this and observe the jump in behaviour: https://play.rust-lang.org/?version=stable&mode=release&edition=2021&gist=513898cf45d7603a980b5afa741aab35

(integer rotations don't have that problem because the integers are always power-of-two bits today)

5 Likes

Besides that behavior in other languages, the term "rotate" would imply that it can be done indefinately. Especially that the rotation of vec.len() is valid seems to imply that as well.

Thank you for all the replies.

It seems inconclusive if the modulo operation would result in more performance loss than the assert. I may do some testing later on this.

I partially understand the argument that it should remain for stability reasons (although I would disagree with someone who was relying on a panic rather than proper error handling). But I also see value in making functions take the largest reasonable range of inputs to make the user experience more streamlined.

Perhaps an alternative compromise would be to make a rotate() function similar to the following:

pub fn rotate(&mut self, rot: isize) {
    if self.is_empty() {
        return;
    }
    if rot >= 0 {
        let rot = (rot % self.len()) as usize;
        self.rotate_right(rot);
    } else {
        let rot = (rot.abs() % self.len()) as usize;
        self.rotate_left(rot);
    }
}

That way we get a function that does not panic and also has more generic behavior. I think this is more elegant than making a wrapping version of both existing rotate functions.

No, that's because it takes fenceposts, not indexes.

It's like how my_slice.split_at(my_slice.len()) is legal. It's not modulo, just a fencepost.

1 Like

Maybe the wrapping version should be mod len + 1 then?

Rotating is an operation that should be possible to make periodic. If the number of elements is len, the number of fenceposts is len + 1

I think such a method would make sense, although your implementation is overcomplicated. Exactly because of the modular nature of rotations, one can express it with either rotate_left or rotate_right only, using Euclidean division:

pub fn rotate(&mut self, rot: isize) {
    if self.is_empty() {
        return;
    }
    self.rotate_right(rot.rem_euclid(self.len() as isize) as usize)
}

Playground

4 Likes

But why does it take a fencepost? "split" takes an index that points between two elements, so there are clearly len + 1 valid distinct inputs.

However, for rotate, there are only len distinct rotations to consider, so I would expect only len valid inputs (if wrap-around is not desired). The fact that slice.rotate accepts len + 1 different inputs does seem very inconsistent to me. Conceptually rotating by len is the shortest rotate that "wraps around", so I would expect rotating by len and by len + 1 to behave consistently -- either both go modulo len or neither does.

10 Likes

Well, mostly because I originally wrote it as a single rotate (without _left and _right variants), following http://elementsofprogramming.com/eop_coloredlinks.pdf#section.10.4, which takes a fencepost :upside_down_face:

I suppose the most direct answer for why that'd be fenceposts (not just indexes) is this Lemma:

Lemma 10.21 The inverse of a k-rotation of n elements is an (n − k)-rotation.

which doesn't cover a zero-rotation unless an n-rotation of n elements is also legal.

And the simplest rotate implementation is

fn rotate<T>(x: &mut [T], k: usize) {
    x[..k].reverse();
    x[k..].reverse();
    x.reverse();
}

which naturally takes fenceposts, not indexes.

7 Likes

@scottmcm that seems like an implementation detail to me, given that the exposed interface is rotate_left/rotate_right.

It also covers a zero rotation if k is an unbounded integer. :slight_smile: In fact the lemma becomes trivial then: the inverse of a k rotation is a -k rotation, and rotations that are equal modulo n are identical, so -k and n-k are the same.

2 Likes

Isn't "an index that points between two elements" a different, less precise, way to define a fencepost (since index 0 and len are not actually between two elements)?

Yes, that is what a fencepost is. That's why fenceposts make sense for "split".

But that reasoning does not apply to rotations.

This is a really elegant solution. I think it would be preferred to use the underlying call to rotate::ptr_rotate in order to avoid the assert in the original implmentations, but it would ideally use this method.

I don't buy this as a counter-argument.

It is very often the case that if you overflow an integer:

  • it will panic in debug mode
  • you will get wrong answers in release mode

It's not specific to slice rotations. So it is not a convincing argument in favor of making slice rotation try to detect such overflows in its inputs post-factum.

2 Likes