Can I reassign a mutable slice reference to a sub-slice of itself?

I'm implementing a stack-like structure, where the structure holds a mutable reference to a slice.

struct StackLike<'a, X> {
    data: &'a mut [X],
}

I'd like to be able to pop the last element off this stack, something like:

impl<'a, X> StackLike<'a, X> {
    pub fn pop(&mut self) -> Option<&'a X> {
        if self.data.is_empty() {
            return None;
        }
        let n = self.data.len();
        let result = &self.data[n - 1];
        self.data = &mut self.data[0..n - 1];
        Some(result)
    }
}

This fails:

error[E0495]: cannot infer an appropriate lifetime for lifetime parameter in function call due to conflicting requirements
  --> src/lib.rs:11:23
   |
11 |         let result = &self.data[n - 1];
   |                       ^^^^^^^^^^^^^^^^
   |
note: first, the lifetime cannot outlive the anonymous lifetime #1 defined on the method body at 6:5...
  --> src/lib.rs:6:5
   |
6  | /     pub fn pop(&mut self) -> Option<&'a X> {
7  | |         if self.data.is_empty() {
8  | |             return None;
9  | |         }
...  |
13 | |         Some(result)
14 | |     }
   | |_____^
note: ...so that reference does not outlive borrowed content
  --> src/lib.rs:11:23
   |
11 |         let result = &self.data[n - 1];
   |                       ^^^^^^^^^
note: but, the lifetime must be valid for the lifetime `'a` as defined on the impl at 5:6...
  --> src/lib.rs:5:6
   |
5  | impl<'a, X> StackLike<'a, X> {
   |      ^^
note: ...so that the expression is assignable
  --> src/lib.rs:13:9
   |
13 |         Some(result)
   |         ^^^^^^^^^^^^
   = note: expected  `std::option::Option<&'a X>`
              found  `std::option::Option<&X>`

Even a simplified version of pop that doesn't return a value and only shrinks the slice doesn't work.

impl<'a, X> StackLike<'a, X> {
    pub fn pop_no_return(&mut self) {
        if self.data.is_empty() {
            return;
        }
        let n = self.data.len();
        self.data = &mut self.data[0..n - 1];
    }
}

which gives

error[E0495]: cannot infer an appropriate lifetime for lifetime parameter in function call due to conflicting requirements
  --> src/lib.rs:11:26
   |
11 |         self.data = &mut self.data[0..n - 1];
   |                          ^^^^^^^^^^^^^^^^^^^
   |
note: first, the lifetime cannot outlive the anonymous lifetime #1 defined on the method body at 6:5...
  --> src/lib.rs:6:5
   |
6  | /     pub fn pop_no_return(&mut self) {
7  | |         if self.data.is_empty() {
8  | |             return;
9  | |         }
10 | |         let n = self.data.len();
11 | |         self.data = &mut self.data[0..n - 1];
12 | |     }
   | |_____^
note: ...so that reference does not outlive borrowed content
  --> src/lib.rs:11:26
   |
11 |         self.data = &mut self.data[0..n - 1];
   |                          ^^^^^^^^^
note: but, the lifetime must be valid for the lifetime `'a` as defined on the impl at 5:6...
  --> src/lib.rs:5:6
   |
5  | impl<'a, X> StackLike<'a, X> {
   |      ^^
note: ...so that reference does not outlive borrowed content
  --> src/lib.rs:11:21
   |
11 |         self.data = &mut self.data[0..n - 1];
   |                     ^^^^^^^^^^^^^^^^^^^^^^^^

Is there a way to make this work, or do I need to track the bounds of the slice I'm interested in more explicitly?

Solution 1:

I modified Masklinn's code slightly to allow multiple .pop()s to be called on the same stack:

struct StackLike<'a, X> {
    data: &'a mut [X],
}

impl<'a, X> StackLike<'a, X> {
    pub fn pop(&mut self) -> Option<&'a mut X> {
        let data = std::mem::replace(&mut self.data, &mut []);
        if let Some((last, subslice)) = data.split_last_mut() {
            self.data = subslice;
            Some(last)
        } else {
            None
        }
    }
}

fn main() {
    let mut data = [1, 2, 3, 4, 5];
    let mut stack = StackLike { data: &mut data };

    let x = stack.pop().unwrap();
    let y = stack.pop().unwrap();
    println!("X: {}, Y: {}", x, y);
}

The tricky part here is this line (I added a type annotation for explicitness):

let data: &'a mut [X] = std::mem::replace(&mut self.data, &mut []);

We replace self.data with an empty slice temporarily so that we can split the slice. If you were to write simply

let data: &'a mut [X] = self.data;

the compiler would be unhappy:

error[E0312]: lifetime of reference outlives lifetime of borrowed content...
  --> src/main.rs:7:33
   |
7  |         let data: &'a mut [X] = self.data;
   |                                 ^^^^^^^^^
   |
note: ...the reference is valid for the lifetime `'a` as defined on the impl at 5:6...
  --> src/main.rs:5:6
   |
5  | impl<'a,  X> StackLike<'a, X> {
   |      ^^
note: ...but the borrowed content is only valid for the anonymous lifetime #1 defined on the method body at 6:5
  --> src/main.rs:6:5
   |
6  | /     pub fn pop(&mut self) -> Option<&'a mut X> {
7  | |         let data: &'a mut [X] = self.data;
8  | |         if let Some((last, subslice)) = data.split_last_mut() {
9  | |             self.data = subslice;
...  |
13 | |         }
14 | |     }
   | |_____^

As far as I understand it, the problem is that self.data is a mutable reference, and mutable references are not Copy (remember, you can only have one at a time). And you cannot move out of self.data since self is a mutable reference, not an owner. So what the compiler tries to do is to reborrow self.data, which "infects" it with with the lifetime of &mut self. This is a dead end: we want the reference to live for 'a, but it is actually valid only for the lifetime of &mut self, and these lifetimes are generally unrelated (and they don't need to be related), which leaves the compiler perplexed.

To aid the compiler, we use std::mem::replace to explicitly move the slice out of self.data and temporarily replace it with an empty slice, which can be any lifetime. Now we can do anything with data without tangling it with the lifetime of &mut self.

Can I reassign a mutable slice reference to a sub-slice of itself?

Solution 1:

Related

Recent Posts