Borrow checker error in a loop inside a recursive function with lifetime bounds

Question

Why does the borrow checker complain about this code?

fn foo<'a>(v: &mut Vec<&'a str>, buf: &'a mut String) {
    loop {
        foo(v, buf);
    }
}

error[E0499]: cannot borrow `*buf` as mutable more than once at a time
 --> src/main.rs:3:16
  |
3 |         foo(v, buf);
  |                ^^^ mutable borrow starts here in previous iteration of loop
4 |     }
5 | }
  | - mutable borrow ends here

If I remove the lifetime bound, the code compiles fine.

fn foo(v: &mut Vec<&str>, buf: &mut String) {
    loop {
        foo(v, buf);
    }
}

This isn't a duplicate of Mutable borrow in a loop, because there is no return value in my case.

I'm pretty sure that my final goal isn't achievable in safe Rust, but right now I want to better understand how the borrow checker works and I can not understand why adding a lifetime bound between parameters extends the lifetime of the borrow in this code.

Sorry for awful title, but I have no clue how to describe the problem in other words. Looks like all of this conditions are required to reproduce this error. — magras
Actually this is a bit weird. But it's not about recursion. If you call another function with the same type signature, you'll have the same problem. — Peter Hall
As a hint, consider that it works with no lifetimes, and remember that the elided lifetimes are treated as all distinct within the function arguments. So without the lifetime annotations it's the same as fn foo<'a, 'b, 'c>(v: &'a mut Vec<&'b str>, buf: &'c mut String). The difference with your version that doesn't work is that you have re-used a lifetime for two of the arguments, tying them together. Neither of them can outlive the other. — Peter Hall
@PeterHall thank you for an advise, but in real function I need them to be bound. Actually lifetime sybtyping is enough, but in this example I made them equal for simplicity. — magras
But there could be workarounds, such as using an Rc<String> for the buf instead of the &mut String. Really depends on what you are really trying to do here. — Peter Hall

Calculator Calculator · Accepted Answer · 2018-07-24T21:14:17

The version with the explicit lifetime 'a ties the lifetime of the Vec to the lifetime of buf. This causes trouble when the Vec and the String are reborrowed. Reborrowing occurs when the arguments are passed to foo in the loop:

fn foo<'a>(v: &mut Vec<&'a str>, buf: &'a mut String) {
    loop {
        foo(&mut *v, &mut *buf);
    }
}

This is done implicitly by the compiler to prevent the arguments from being consumed when foo is called in the loop. If the arguments were actually moved, they could not be used anymore (e.g. for successive calls to foo) after the first recursive call to foo.

Forcing buf to be moved around resolves the error:

fn foo<'a>(v: &mut Vec<&'a str>, buf: &'a mut String) {
    foo_recursive(v, buf);
}

fn foo_recursive<'a>(v: &mut Vec<&'a str>, buf: &'a mut String) -> &'a mut String{
    let mut buf_temp = buf;
    loop {
        let buf_loop = buf_temp;
        buf_temp = foo_recursive(v, buf_loop);
        // some break condition
    }
    buf_temp
}

However, things will break again as soon as you try to actually use buf. Here is a distilled version of your example demonstrating why the compiler forbids successive mutable borrows of buf:

fn foo<'a>(v: &mut Vec<&'a str>, buf: &'a mut String) {
    bar(v, buf);
    bar(v, buf);
}

fn bar<'a>(v: &mut Vec<&'a str>, buf: &'a mut String) {
    if v.is_empty() {
        // first call: push slice referencing "A" into 'v'
        v.push(&buf[0..1]);
    } else {
        // second call: remove "A" while 'v' is still holding a reference to it - not allowed
        buf.clear();
    }
}

fn main() {
    foo(&mut vec![], &mut String::from("A"));
}

The calls to bar are the equivalents to the recursive calls to foo in your example. Again the compiler complains that *buf cannot be borrowed as mutable more than once at a time. The provided implementation of bar shows that the lifetime specification on bar would allow this function to be implemented in such a way that v enters an invalid state. The compiler understands by looking at the signature of bar alone that data from buf could potentially flow into v and rejects the code as potentially unsafe regardless of the actual implementation of bar.

Borrow checker error in a loop inside a recursive function with lifetime bounds

1 Answers