Earlier this week, I ran into a confusing situation with lifetimes and the borrow checker while working on my Lox interpreter. It took me a little while to figure out, and it's an instructive situation.

Here's a reduced-down version of what I was working on. It's an interpreter, so there is a scanner which produces tokens. Ideally these tokens are references back into the underlying original string so that you can avoid any more memory allocation.

Simple enough, I thought, so I implemented a Scanner which produced Tokens:

/// An overly simplified Scanner, containing just
/// enough fields to produce fake tokens.
struct Scanner<'source> {
    source: &'source str,
    count: usize,
}

/// An overly simplified Token, containing just
/// a reference to a str to reproduce the error.
struct Token<'source> {
    lexeme: &'source str,
}

impl Scanner<'_> {
    /// next_token produces a fake token which
    /// reproduces the error; you'd want to do
    /// some real scanning here, of course!
    pub fn next_token(&mut self) -> Token {
        self.count += 1;
        Token { lexeme: self.source }
    }
}

fn main() {
    let source = "x = 10";
    let mut scanner = Scanner { source, count: 0 };

    let token = scanner.next_token();
    println!("token: {}", token.lexeme);
}

This compiles, and it has a sprinkling of named lifetimes within it. Those are important so that the compiler can reason about how long the references will live. If you have a reference in a struct, it always needs a lifetime annotation, unless it falls under one of the three lifetime elision rules, which we'll get to.

For now, though, let's do something more with our scanner. We'll get a second token in main, the way you might see in a parser where you keep the current and previous tokens:

fn main() {
    let source = "x = 10";
    let mut scanner = Scanner { source, count: 0 };

    let previous = scanner.next_token();
    let current = scanner.next_token();

    println!("previous: {}", previous.lexeme);
    println!("current: {}", current.lexeme);
}

Now this looks like it should work, since all the tokens will live as long as the source, which lives as long as the main function does. However, we get this output when we try to compile it:

error[E0499]: cannot borrow `scanner` as mutable more than once at a time
  --> lifetime.rs:29:19
   |
28 |     let previous = scanner.next_token();
   |                    -------------------- first mutable borrow occurs here
29 |     let current = scanner.next_token();
   |                   ^^^^^^^^^^^^^^^^^^^^ second mutable borrow occurs here
30 |
31 |     println!("previous: {}", previous.lexeme);
   |                              --------------- first borrow later used here

error: aborting due to previous error

For more information about this error, try `rustc --explain E0499`.

Somehow, we're trying to hold onto two mutable references to scanner at the same time! But why?

It comes down to those lifetime elision rules. There are three lifetime elision rules, which apply to both impl blocks and fns:

1. Each parameter that's a reference gets a lifetime. These are input lifetimes.
2. If there's exactly one input lifetime parameter, that lifetime is used for all output lifetimes.
3. If there are multiple input lifetime parameters but one is &self or &mut self, the self lifetime "wins" and is used for all output lifetimes.

So what's happening here is that next_token gets implicit lifetimes assigned to it, and those end up forcing a longer lifetime than we really need on the borrow. To understand it, we can write out what the elision rules would do for us. We apply rule 1 to know that we'll need an input lifetime for both self (let's call it 'scanner) and for the source/lexeme (let's call it 'source). We also know from rule 3 that since Token has a lifetime parameter and is returned, it will be the same as the reference itself.

So we end up with this:

impl<'source, 'scanner> Scanner<'source> {
    /// next_token produces a fake token which
    /// reproduces the error; you'd want to do
    /// some real scanning here, of course!
    pub fn next_token(&'scanner mut self) -> Token<'scanner> {
        self.count += 1;
        Token { lexeme: self.source }
    }
}

If we compile it with this implementation instead, we get the same compiler error. But this is clearly not what we want: we don't want tokens to live as long as the reference to the scanner, we want them to live as long as the source! Since their lifetime is linked to the mutable reference to the scanner, it forces that reference to be held for at least as long as the tokens are.

We can fix this pretty simply by instead annotating with the correct lifetime on the returned Token. You can also omit the 'scanner lifetime, but I chose to leave it in here to be a little more explicit for clarity in this example.

impl<'source, 'scanner> Scanner<'source> {
    /// next_token produces a fake token which
    /// reproduces the error; you'd want to do
    /// some real scanning here, of course!
    pub fn next_token(&'scanner mut self) -> Token<'source> {
        self.count += 1;
        Token { lexeme: self.source }
    }
}

And with that small change, the whole thing compiles! Of course, in retrospect, it's really clear that I should have specified the lifetime parameter for Token in the first place, but you live and learn.