Mutable and lifetime problem in recursive function

[davyzhu]

Hi, I tried to write a recursive backtrack function. As compiler suggested, I put life time 'a all over the function. But compile still failed. Any suggestion? Thanks!

Original program is much longer, and I paste it on Playground.

struct LinesInfo {
}

struct Point {
}

struct Solution<'a> {
    current: Vec<&'a Point>,
}

impl LinesInfo {
    fn backtrack<'a>(&'a self, sol: &'a mut Solution<'a>) {
        let candidates:Vec<&Point> = Vec::new();
        for c in candidates {
            sol.current.push(c);
            self.backtrack(sol);
            sol.current.pop();
        }
    }
}

fn main() {}

error[E0499]: cannot borrow `sol.current` as mutable more than once at a time
  --> src\main.rs:15:13
   |
12 |     fn backtrack<'a>(&'a self, sol: &'a mut Solution<'a>) {
   |                  -- lifetime `'a` defined here
...
15 |             sol.current.push(c);
   |             ^^^^^^^^^^^ second mutable borrow occurs here
16 |             self.backtrack(sol);
   |             -------------------
   |             |              |
   |             |              first mutable borrow occurs here
   |             argument requires that `*sol` is borrowed for `'a`

Other Two Errors

error[E0499]: cannot borrow `*sol` as mutable more than once at a time
  --> src\main.rs:16:28
   |
12 |     fn backtrack<'a>(&'a self, sol: &'a mut Solution<'a>) {
   |                  -- lifetime `'a` defined here
...
16 |             self.backtrack(sol);
   |             ---------------^^^-
   |             |              |
   |             |              `*sol` was mutably borrowed here in the previous iteration of the loop
   |             argument requires that `*sol` is borrowed for `'a`

error[E0499]: cannot borrow `sol.current` as mutable more than once at a time
  --> src\main.rs:17:13

   |
12 |     fn backtrack<'a>(&'a self, sol: &'a mut Solution<'a>) {
   |                  -- lifetime `'a` defined here
...
16 |             self.backtrack(sol);
   |             -------------------
   |             |              |
   |             |              first mutable borrow occurs here
   |             argument requires that `*sol` is borrowed for `'a`
17 |             sol.current.pop();
   |             ^^^^^^^^^^^ second mutable borrow occurs here

[quinedot]

I didn't dig very deep on this one, so perhaps there's something more optimal, but here's what I ended up with:

    fn backtrack<'a: 'b, 'b>(
        &'a self,
        sol: &mut Solution<'b>,

Playground.

Reasoning: Is often best to leave the lifetimes unconstrained if that doesn't cause a problem, for maximum flexibility. In that case this isn't possible, because "self flows into sol". This means that &self needs to be valid for at least as long as the Solution, so that's what I've gone with. You can read it as:

• &self has lifetime 'a
• And the Solution has lifetime 'b, which is not necessarily the same
• And 'a is valid for at least all the places 'b is valid
• And the lifetime of the reference sol: &Solution is only restricted by being well-formed
  • I.e. it can't last longer than the thing it points to, Solution<'b>
  • It doesn't have to be equal to 'a or 'b though

The hazard with just putting a 'a everywhere is that this forces everywhere with the 'a to have the same lifetime, which is often overly constricting. The other pitfall you hit was that you can leave the <'lifetime> off of Solution altogether, when in this case it needed to be part of your constraints. (You can do this with references too, as I have done in fact, but it's less visible and easier to forget about with generic structs since you aren't forced to write <'_>.)

[davyzhu]

Very clear and highly informative! Thank you!