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

Question

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?

Entangle

Answer 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.

Moralist

Brilliant. Exactly what I was going to suggest. It may be worth noting that the "temporary" replacement of the slice ends up being permanent if self.data starts out empty (because you lose the original slice when split_last_mut returns None). Practically, this probably isn't an issue, because all empty slices are more or less equivalent, but it could lead to surprises if you were doing something tricky with the address of the data. – Zeeba

Return type of pop doesn't need to hold a mutable reference, i.e.: pub fn pop(&mut self) -> Option<&'a X>. – Housebreaker

Indeed, I added it myself, because otherwise data could as well be &'a [X] and the question becomes somewhat easier. – Moralist

Answer 2

For sub-question 2, you need to indicate the relation between &mut self and 'a otherwise they're considered unrelated. I don't know if there's a shortcut via lifetime elision but if you specify that self lives for 'a you're fine.

For sub-question 1, the compiler doesn't "see through" function calls (including indexing which desugars to a function call), so it does not know that &self.data[n - 1] and &mut self.data[0..n-1] are non-overlapping. You need to use split_mut_last.

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

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

playground

Saki

One pretty major downside with this is because pop must take &'a mut self, it seems like you won't be able to call .pop() twice because it needs a mutable reference with the entire lifetime of the stack. Example – Sussi