How to recur through a mutable associate method (for a recursive descent parser implementation)?

Question

I've been trying to implement a top-down recursive descent parser in Rust. But I'm also learning Rust and I'm in a stage where I'm most of the time fighting with the compiler or more specifically the borrow-checker.

I have the solution in mind and have already implemented it in a non-system GC language and it's working. But I'm having quite a few problems when trying to implement it in Rust. But I've pretty much already fixed most of it by doing exactly what the compiler wants me to do and going back and forth to the documentation and fixing up things. But this last error (or so I believe) is not going away easily. I've been trying to tackle it for two days and I'm getting quite frustrated with it, so here I am.

Here are the snippets of what I'm trying to do.

First, I have a struct called Parser implemented like this. The lifetime source is required for it, and I don't think the details of the Scanner struct are important except that it implements the Iterator trait over the items of type Token<'source>.

struct Parser<'source> {
    tokens: Scanner<'source>,
}

// it has an associated method called `peek`
// which is implemented similar to the `peek` of `Peekable` iterators
fn peek(&mut self) -> Option<&Token<'source>> {
  // there is a reason why i implemented it instead of using the `Peekable`
  // ...
}

Here is the recursive implementation of the associated methods in the struct.

// for reference, Expr looks like this
enum Expr<'a> {
    Unary(Token<'a>, Box<Expr<'a>>),
    Binary(Box<Expr<'a>>, Token<'a>, Box<Expr<'a>>),
    Grouping(Box<Expr<'a>>),
    Literal(Token<'a>),
}

impl<'source> Parser<'source> {
    fn expression(&mut self) -> Result<Expr<'source>, ParserError> {
        self.equality()
    }

    // there is actually more functions like this,  recursively referring another functions
    // but I've reduced it to 2 for simplicity
    // for example, this function parses equality expression
    fn equality(&mut self) -> Result<Expr<'source>, ParserError> {
        let mut left = self.unary()?;

        while let Some(Token::BangEqual | Token::EqualEqual) = self.tokens.peek() {
            // error: can't borrow self.tokens as mutable twice
            let op = self.tokens.next().unwrap();
            let right = self.unary()?; // error: can't borrow *self as mutable twice
            left = Expr::Binary(Box::new(left), op, Box::new(right));
        }

        Ok(left)
    }

    fn unary(&mut self) -> Result<Expr<'source>, ParserError> {
        while let Some(Token::Bang | Token::Plus | Token::Minus) = self.tokens.peek() {
            let op = self.tokens.next().unwrap();
            let right = self.unary()?;
            return Ok(Expr::Unary(op, Box::new(right)));
        }

        self.primary()
    }

    fn primary(&mut self) -> Result<Expr<'source>, ParserError> {
        match self.tokens.next() {
            Some(
                token
                @
                (Token::True
                | Token::False
                | Token::Nil
                | Token::String(_)
                | Token::Number(_)),
            ) => Ok(Expr::Literal(token)),
            Some(_) => {}, // implementation here is redacted, but it references back to the top `expression` function
            None => Err(ParserError::UnexpectedToken(Token::Error)),
        }
    }
}

What I've tried so far, is before all this, it had some more borrow-checker problems. But I've reduced it to the current state by adding lifetimes (I don't really know why, but it did work though 😬). Now, at the current state, I don't even know what to do next as the current compiler error is not very helpful. Fellow rustaceans, enlighten me, please.

Answer 1

Pre-answer note:

I've reduced it to the current state by adding lifetimes (I don't really know why, but it did work though 😬).

This suggests you don't have a strong handle on Rust's borrowing rules, which you really, really need if you're going to try zero-copy parsing. You should read over References and Borrowing and Validating References with Lifetimes in The Rust Programming Language.

The Problem

In your program, the peek() method receives self as a mutable reference and returns a reference. The mutable borrow of the caller lasts until that reference is dropped. Thus, when you do this:

while let Some(/* ... */) = self.tokens.peek() {
    // `self.tokens` is borrowed mutably for the entirety of each loop iteration.
}

You then immediately try to borrow self.tokens mutably again by calling next(). Rust doesn't know the semantics of these two calls -- all it knows is:

1. You mutated self.tokens, then returned an immutable reference (call it r) to its internal state.
2. You tried to mutate self.tokens again while a mutable reference was still held (through r -- r is immutable, but the call that produced it took a mutable reference).

Okay, so that's one issue -- you borrow using a mutable method, then try to call another mutable method while the borrow still lives. What if you waved a magic wand and peek() took &self instead of &mut self?

1. You borrowed self.tokens to call a method which returns an immutable reference r to its internal state.
2. You then tried to mutate self.tokens.

This is also illegal -- you can't mutate self while it is borrowed immutably.

The Solution(s)

In order to use mutable methods inside your while let, you have to drop the borrow. You don't show your token implementation, but if it just contains a &str, you can return by-value rather than by-reference:

fn peek(&mut self) -> Option<Token<'source>> { /* ... */ }

There are other possibilities, such as using interior mutability (Cell and RefCell), so that the methods can advance the token stream while still taking &self.

Here's short example program that exhibits your problem (playground), and a version which implements the solution I described (playground).