Yesterday I decided to switch my project's Strings over to &str. In the process I forgot to make my parser functions return Expr<'a> instead of plain Expr, and started getting "cannot borrow *self as mutable more than once at a time".
I dug into it and also asked an AI about it the explanation I got was that this comes down to lifetime elision: when I don't write Expr<'a> explicitly, the compiler treats it as Expr<'s> instead, tied to the &mut self borrow rather than the struct's own lifetime, and that's what causes the conflict. That part made sense, but when I pushed for more detail and asked follow-up questions, some of the answers started getting inconsistent/wonky so I figured it's worth double-checking here with actual humans, which honestly always feels more reliable to me anyway.
The broken version (simplified):
fn factor(&mut self) -> Expr { // no 'a here
let mut expr = self.unary();
while self.match_token(&[TokenType::Slash, TokenType::Star]) {
let right = self.unary();
expr = Expr::Binary { left: Box::new(expr), operator, right: Box::new(right) }
}
expr
}
With elision this desugars to fn factor<'s>(&'s mut self) -> Expr<'s>, so the returned Expr gets tied to that specific &mut self borrow. Since I keep expr alive across the loop, the borrow never closes, and the second &mut self call (match_token) inside the loop conflicts with it.
Fix: explicitly annotate the return type as Expr<'a>, tying it to the Parser<'a>'s own lifetime instead. That lets each &mut self borrow close cleanly after every call.
Questions for you all:
- Is this explanation technically accurate, or am I missing something?
- I've still got
consume/advance/previousreturning&Token<'a>should I refactor those to return ownedToken<'a>(via Clone) to avoid running into the same trap down the line, or is returning a reference fine for this kind of parser design?
Full code below:
use crate::expr::{Expr, LiteralValue};
use crate::token::{Token, TokenType};
#[derive(Debug)]
enum ParserError {
UnexpectedToken(String),
Undefined(String),
}
#[derive(Debug)]
pub struct Parser<'a> {
tokens: Vec<Token<'a>>,
current: usize,
}
impl<'a> Parser<'a> {
pub fn new(tokens: Vec<Token<'a>>) -> Self {
Self { tokens, current: 0 }
}
fn peek(&self) -> &Token<'a> {
self.tokens.get(self.current).unwrap()
}
fn is_at_end(&self) -> bool {
self.peek().token_type == TokenType::Eof
}
fn previous(&self) -> &Token<'a> {
self.tokens.get(self.current - 1).unwrap()
}
fn advance(&mut self) -> &Token<'a> {
if !self.is_at_end() {
self.current += 1;
}
self.previous()
}
fn check(&self, typ: TokenType) -> bool {
!self.is_at_end() && self.peek().token_type == typ
}
fn match_token(&mut self, typ: &[TokenType]) -> bool {
if typ.iter().any(|f| self.check(*f)) {
self.advance();
true
} else {
false
}
}
pub fn expression(&mut self) -> Expr<'a> {
self.equality()
}
fn primary(&mut self) -> Result<Expr<'a>, ParserError> {
let token = self.advance().token_type;
match token {
TokenType::False => Ok(Expr::literal(LiteralValue::Bool(false))),
TokenType::True => Ok(Expr::literal(LiteralValue::Bool(true))),
TokenType::Nil => Ok(Expr::literal(LiteralValue::Nil)),
TokenType::Number => {
let value = self.previous().literal.unwrap();
Ok(Expr::literal(LiteralValue::Number(value.parse::<f64>().unwrap())))
}
TokenType::String => {
let value = self.previous().literal.unwrap();
Ok(Expr::literal(LiteralValue::String(value)))
}
TokenType::LeftParen => {
let expr = self.expression();
self.consume(
TokenType::RightParen,
"Expect ')' after expression".to_string(),
)
.unwrap();
Ok(Expr::grouping(Box::new(expr)))
}
_ => Err(ParserError::Undefined(String::from("Undefined type"))),
}
}
fn consume(&mut self, typ: TokenType, message: String) -> Result<&Token<'a>, std::io::Error> {
if self.check(typ) {
Ok(self.advance())
} else {
Err(std::io::Error::new(
std::io::ErrorKind::AlreadyExists,
message,
))
}
}
fn unary(&mut self) -> Expr<'a> {
if self.match_token(&[TokenType::Bang, TokenType::Minus]) {
let operator = self.previous().token_type;
let right = self.unary();
return Expr::unary(operator, Box::new(right));
}
self.primary().unwrap()
}
fn equality(&mut self) -> Expr<'a> {
let mut expr = self.comparison();
while self.match_token(&[TokenType::BangEqual, TokenType::EqualEqual]) {
let operator = self.previous().token_type;
let right = self.comparison();
expr = Expr::Binary {
left: Box::new(expr),
operator,
right: Box::new(right),
};
}
expr
}
fn comparison(&mut self) -> Expr<'a> {
let mut expr = self.term();
while self.match_token(&[
TokenType::Greater,
TokenType::GreaterEqual,
TokenType::Less,
TokenType::LessEqual,
]) {
let operator = self.previous().token_type;
let right = self.term();
expr = Expr::binary(Box::new(expr), operator, Box::new(right));
}
expr
}
fn term(&mut self) -> Expr<'a> {
let mut expr = self.factor();
while self.match_token(&[TokenType::Minus, TokenType::Plus]) {
let operator = self.previous().token_type;
let right = self.factor();
expr = Expr::Binary {
left: Box::new(expr),
operator,
right: Box::new(right),
}
}
expr
}
fn factor(&mut self) -> Expr<'a> {
let mut expr = self.unary();
while self.match_token(&[TokenType::Slash, TokenType::Star]) {
let operator = self.previous().token_type;
let right = self.unary();
expr = Expr::Binary {
left: Box::new(expr),
operator,
right: Box::new(right),
}
}
expr
}
}
use crate::token::TokenType;
#[derive(Debug, Clone)]
pub enum LiteralValue<'a> {
Number(f64),
String(&'a str),
Bool(bool),
Nil,
}
#[derive(Debug, Clone)]
pub enum Expr<'a> {
Binary {
left: Box<Expr<'a>>,
operator: TokenType,
right: Box<Expr<'a>>,
},
Grouping {
expression: Box<Expr<'a>>,
},
Literal {
value: LiteralValue<'a>,
},
Unary {
operator: TokenType,
right: Box<Expr<'a>>,
},
}
impl<'a> Expr<'a> {
pub fn binary(left: Box<Expr<'a>>, operator: TokenType, right: Box<Expr<'a>>) -> Self {
Self::Binary { left, operator, right }
}
pub fn grouping(expression: Box<Expr<'a>>) -> Expr<'a> {
Self::Grouping { expression }
}
pub fn literal(value: LiteralValue<'a>) -> Expr<'a> {
Self::Literal { value }
}
pub fn unary(operator: TokenType, right: Box<Expr<'a>>) -> Expr<'a> {
Self::Unary { operator, right }
}
}