A lifetime/borrowing question

I don't understand why I run into this lifetime/borrowing error.

fn generate takes a slice of &mut [Apple] and then the slice is looped twice by index. Finally, the slice is passed to the Generator struct in the second loop.

// playground link: https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=606a52a3fd157921e945a2d7ab5ad3fe

struct Apple<'a> {
    s: &'a String,
struct Generator<'a> {
    apples: &'a mut [Apple<'a>],

impl<'a> Generator<'a> {
    fn new(apples: &'a mut [Apple<'a>]) -> Self {
        Self { apples }

fn generate(apples: &mut [Apple]) {
    let len = apples.len();

    for a_idx in 0..len {
        for b_idx in a_idx + 1..len {
            let gen = Generator::new(apples);

// Error
   Compiling playground v0.0.1 (/playground)
error: lifetime may not live long enough
  --> src/lib.rs:20:23
15 | fn generate(apples: &mut [Apple]) {
   |             ------  - let's call the lifetime of this reference `'1`
   |             |
   |             has type `&mut [Apple<'2>]`
20 |             let gen = Generator::new(apples);
   |                       ^^^^^^^^^^^^^^^^^^^^^^ argument requires that `'1` must outlive `'2`

error[E0499]: cannot borrow `*apples` as mutable more than once at a time
  --> src/lib.rs:20:38
15 | fn generate(apples: &mut [Apple]) {
   |             ------ has type `&mut [Apple<'2>]`
20 |             let gen = Generator::new(apples);
   |                       ---------------^^^^^^-
   |                       |              |
   |                       |              `*apples` was mutably borrowed here in the previous iteration of the loop
   |                       argument requires that `*apples` is borrowed for `'2`

For more information about this error, try `rustc --explain E0499`.
error: could not compile `playground` (lib) due to 2 previous errors

&'a mut [Apple<'a>] means the Apple<'_>s are borrowed forever. You can use a separate lifetime.

The reproduction is too small to give much feedback, but you may be overusing references.

Thank you very much.

After reading both

  1. Borrowing something forever - Learning Rust
  2. &'a Struct<'a> and covariance - Learning Rust

I do understand that by using &'a mut Thing<'a>, I cannot do a lot of things to Thing<'a> as it is somehow borrowed exclusively forever.

However, I am still failed to understand why is that.
I guess I don't understand deep down what lifetime is and thus could't see the differences between
&'a mut Thing<'a> and &'g mut Thing<'a>. Why does use two lifetimes fix the problem?

This ended up pretty long but hopefully it answers your question. The TL;DR is...

  • In generator, the caller chooses the lifetimes of the arguments; in particular, the inner lifetime on Apple<'_> -- call it 'a -- is invariant and can't change. All caller chosen lifetimes are longer than the function itself.

  • When the definition of Generator says the lifetimes are the same, the compiler enforces that, so in the loop you're trying to get an &'a mut [Apple<'a>]. It can't be shorter than 'a due to invariance. That would make the slice borrowed, well, "forever" for one, but definitely longer than one loop -- longer than the entire function call.

  • So the second time through the loop, the slice is still mutably -- exclusively -- borrowed.

    • There's another error ("part 3" below), but addressing it alone doesn't actually solve the problem (spoilers).
  • If you remove the requirement that the lifetimes are the same, you can reborrow the slice for &'local mut [Apples<'a>], where 'local is only as long as the inside of the loop. Then it's no longer borrowed on the second or subsequent times through the loop.

    • And the other error goes away without doing anything

Part 1: Lifetime beneath &mut are invariant

&'r mut Apple<'a> has to be invariant in 'a -- that means, 'a is fixed and can't be coerced to something shorter or longer -- for soundness. (The same is true of anything inside a &mut _). For example:[1]

// Longer would lead to UB (probably obvious)
fn send_it_away<'r, 'a>(apple: &'r mut Apple<'a>) {
    let apple: &mut Apple<'static> = apple;
    let owned = std::mem::replace(apple, Apple::<'static> { s: "bye" });
    thread::spawn(move || loop { println!("{}", owned.s); });

fn main() {
    let local = "Hi".to_string();
    let mut apple = Apple { s: &*local };
    send_it_away(&mut apple);
    // The apple we sent away now reads deallocated memory
// Shorter would *also* lead to UB (probably less obvious)
fn replace<'r>(slice: &'r mut [Apple<'static>]) {
    let local = "Hi".to_string();
    let slot: &mut Apple<'_> = &mut slice[0];
    // If the inner lifetime could shrink, this assignment would succeed
    // (i.e. if `'_` in the line above could be shorter than `'static`)
    *slot = Apple { s: &*local };
// But `local` drops at the end of the function and now `slice[0]`
// contains a dangling reference (which is UB)

Part 2: &mut are exclusive references

Despite the name, &mut _ are not just mutable references; they are exclusive references. If you have a &'r mut X, for the entirety of 'r, all access to the X place must go through the &'r mut X in one sense or another.

Combined with invariance, this means that if you get ahold of a &'a mut [Apple<'a>], all access to the slice full of Apple<'a>s must be through that particular &'a mut _. You can't take fresh references to the slice or do anything else prohibited by the slice being exclusively borrowed.

Since the Apple<'a>s aren't valid after 'a expires, this is why they are "borrowed forever".

Part 3 (sorta): Elided lifetimes and lifetime annotations

If you use the same named lifetime in two different places, the compiler takes this as an instruction to make sure they're equal. So in your struct definition alone, there's red flag:

struct Generator<'a> {
    apples: &'a mut [Apple<'a>], // <-- Anti-pattern

But let's see how it applies in the function that actually throws an error:

// fn generate(apples: &mut [Apple]) {
// - A more explicit version is:
// fn generate(apples: &mut [Apple<'_>]) {
// - elided input lifetimes get distinct parameters, so this is:
// fn generate<'r, 'a>(apples: &'r mut [Apple<'a>]) {
// - there's an implicit `'a: 'r` bound ("'a outlives 'r"), 
//   ("'a is longer (or the same) as 'r") because you can't
//   reference something invalid, so this is *mostly* the same as:
fn generate<'r, 'a: 'r>(apples: &'r mut[Apple<'a>]) {

When we give them names, the error change a bit. Here's the first one:

15 | fn generate<'r, 'a: 'r>(apples: &'r mut [Apple<'a>]) {
   |             --  -- lifetime `'a` defined here
   |             |
   |             lifetime `'r` defined here
20 |             let gen = Generator::new(apples);
   |                       ^^^^^^^^^^^^^^^^^^^^^^ argument requires that `'r` must outlive `'a`
   = help: consider adding the following bound: `'r: 'a`

The Generator definition demands that the lifetimes be the same, but the function accepts references where the outer lifetime 'r is shorter than the inner lifetime 'a. 'a can't be shrunk to match 'r due to invariance (and it would be invalid to extend 'r too), and that's what this first error is about.

It says "try adding 'r: 'a", but 'r: 'a when you already have 'a: 'r means that 'a == 'r. Generator said the lifetimes have to match, but they might not; that's the error.

You can make this error go away by only accepting things with the same lifetimes...

fn generate<'a>(apples: &'a mut [Apple<'a>]) {

But the other error remains. This error is due to the "borrowed forever" problem. The first time through the loop, you reborrow the *&'a mut [Apple<'a>] as the same &'a mut [Apple<'a>] (the lifetimes have to stay the same, and can't change due to the invariance). That lifetime is chosen by the caller, and longer than this function body. Then the next time through the loop, you try to do it again -- but you can't, it's still exclusively borrowed.

Or if you prefer, you try to move the &'a mut [Apple<'a>] (&mut _ are not Copy), but can't move it twice. (But the error is phrased in terms of reborrowing.)

So making the lifetimes the same on the function doesn't really help... hence the "sorta". But maybe this section helps explain why you got the errors you did.

Part 4: The fix (hopefully)

The fix was to get rid of the &'a mut ... 'a anti-pattern. The function signature doesn't force the lifetimes to be the same either. But it would actually still compile if you did! You don't want that (the caller's slice is borrowed forever if you do that), but it still compiles. So what's going on?

Because the lifetimes don't have to be the same anymore, you can reborrow the &'r mut [Apple<'a>] for some &'local mut [Apple<'a>]. The inner lifetime is invariant, but the outer lifetime isn't, and the outer lifetime isn't being forced by the Generator definition to be the same as the inner lifetime either.

So every time through the loop...

    for a_idx in 0..len {
        for b_idx in a_idx + 1..len { // --------+ You only need the
            let gen = Generator::new(apples); // | reborrow of `*apples` 
        } // ------------------------------------+ for this one line

...you get a local lifetime that ends at the end of the loop, when gen drops.[2]

Why did I say "hopefully"? Well, if you try to make gen stick around for longer than once through the loop...

    for a_idx in 0..len {
        let mut v = Vec::new();
        for b_idx in a_idx + 1..len {
            let gen = Generator::new(apples);

...then you're trying to get two &mut [...]s to the same slice of Apples at the same time. The exclusivity of &mut kicks in and the compiler doesn't allow it.

  1. I'm not bothering to compile all of my examples; pardon any mistakes ↩︎

  2. This works even if the lifetimes were the same coming into the function, though again, you don't want to do that. ↩︎