How to fight this borrow checker?

I am trying to create math expression evaluator, I am facing this barrow checker problem

Code

struct Parser {
    pub source: String,
    lexer: Lexer,
    n: usize,
    tokens: Vec<Token>,
}

impl Parser {
    fn addition(&mut self) -> ExprType {
        let left = self.multiply();
        if self.match_token(&[TokenType::PLUS, TokenType::MINUS]) {
            let operator = self.previous();
            let right = self.multiply();
            return ExprType::Binary(Binary {
                left: Box::new(left),
                right: Box::new(right),
                operator,
            });
        }
        return left
    }
    fn multiply(&mut self) -> ExprType  {
        let left = self.term();
        if self.match_token(&[TokenType::STAR, TokenType::PLUS]) {
            let operator = self.previous();
            let right = self.term();
            return ExprType::Binary(Binary{
                left: Box::new(left),
                right: Box::new(right),
                operator,
            });
        }
        return left;
    }

    fn term(&mut self) -> ExprType {
        if self.match_token(&[TokenType::NUMBER]) {
            let t = self.previous();
            match &t.literal {
                Some(val) => {
                    return ExprType::Literal(Literal { value: val });
                }
                None => panic!("literal value is None but Token is number"),
            }
        }
        panic!("Unexpected token {:?}", self.peek());
    }

    fn match_token(&mut self, types: &[TokenType]) -> bool {
        for t in types.iter() {
            if self.check(t) {
                self.increment();
                return true;
            }
        }
        return false;
    }
    fn check(&mut self, t: &TokenType) -> bool {
        if self.at_end() {
            return false;
        }
        match self.peek() {
            Some(t1) => match &t1.tt {
                t => true,
                _ => false,
            },
            _ => false,
        }
    }

    fn at_end(&mut self) -> bool {
        if let None = self.next_token() {
            return true;
        }
        return false;
    }
    fn next_token(&mut self) -> Option<&Token> {
        if self.n > self.tokens.len() {
            return Some(&self.tokens[self.n]);
        }
        return self.get_token();
    }

    fn get_token(&mut self) -> Option<&Token> {
        let token = self.lexer.next();
        match token.tt {
            TokenType::EOL => {
                return None;
            }
            _ => self.tokens.push(token),
        };
        return self.tokens.last();
    }

    fn previous(&self) -> &Token {
        return &self.tokens[self.n - 1];
    }

    fn peek(&mut self) -> Option<&Token> {
        return self.next_token();
    }

    fn increment(&mut self) {
        self.n += 1;
    }
}

Error

error[E0499]: cannot borrow `*self` as mutable more than once at a time
  --> src/parser/parser.rs:15:12
   |
13 |     fn addition(&mut self) -> ExprType {
   |                 - let's call the lifetime of this reference `'1`
14 |         let left = self.multiply();
   |                    ---- first mutable borrow occurs here
15 |         if self.match_token(&[TokenType::PLUS, TokenType::MINUS]) {
   |            ^^^^ second mutable borrow occurs here
...
24 |         return left
   |                ---- returning this value requires that `*self` is borrowed for `'1`

error[E0502]: cannot borrow `*self` as immutable because it is also borrowed as mutable
  --> src/parser/parser.rs:16:28
   |
13 |     fn addition(&mut self) -> ExprType {
   |                 - let's call the lifetime of this reference `'1`
14 |         let left = self.multiply();
   |                    ---- mutable borrow occurs here
15 |         if self.match_token(&[TokenType::PLUS, TokenType::MINUS]) {
16 |             let operator = self.previous();
   |                            ^^^^ immutable borrow occurs here
...
24 |         return left
   |                ---- returning this value requires that `*self` is borrowed for `'1`

error[E0499]: cannot borrow `*self` as mutable more than once at a time
  --> src/parser/parser.rs:17:25
   |
13 |     fn addition(&mut self) -> ExprType {
   |                 - let's call the lifetime of this reference `'1`
14 |         let left = self.multiply();
   |                    ---- first mutable borrow occurs here
...
17 |             let right = self.multiply();
   |                         ^^^^ second mutable borrow occurs here
...
24 |         return left
   |                ---- returning this value requires that `*self` is borrowed for `'1`

error[E0499]: cannot borrow `*self` as mutable more than once at a time
  --> src/parser/parser.rs:28:12
   |
26 |     fn multiply(&mut self) -> ExprType  {
   |                 - let's call the lifetime of this reference `'1`
27 |         let left = self.term();
   |                    ---- first mutable borrow occurs here
28 |         if self.match_token(&[TokenType::STAR, TokenType::PLUS]) {
   |            ^^^^ second mutable borrow occurs here
...
37 |         return left;
   |                ---- returning this value requires that `*self` is borrowed for `'1`

error[E0502]: cannot borrow `*self` as immutable because it is also borrowed as mutable
  --> src/parser/parser.rs:29:28
   |
26 |     fn multiply(&mut self) -> ExprType  {
   |                 - let's call the lifetime of this reference `'1`
27 |         let left = self.term();
   |                    ---- mutable borrow occurs here
28 |         if self.match_token(&[TokenType::STAR, TokenType::PLUS]) {
29 |             let operator = self.previous();
   |                            ^^^^ immutable borrow occurs here
...
37 |         return left;
   |                ---- returning this value requires that `*self` is borrowed for `'1`

error[E0499]: cannot borrow `*self` as mutable more than once at a time
  --> src/parser/parser.rs:30:25
   |
26 |     fn multiply(&mut self) -> ExprType  {
   |                 - let's call the lifetime of this reference `'1`
27 |         let left = self.term();
   |                    ---- first mutable borrow occurs here
...
30 |             let right = self.term();
   |                         ^^^^ second mutable borrow occurs here
...
37 |         return left;
   |                ---- returning this value requires that `*self` is borrowed for `'1`
pub trait Expr {
    fn accept<V>(self, visitor: impl Visitor<V>) -> V;
}

pub struct Binary<'a> {
    left: Box<ExprType<'a>>,
    right: Box<ExprType<'a>>,
    operator: &'a Token,
}

pub enum ExprType<'a> {
    Binary(Binary<'a>),
    Literal(Literal<'a>),
}
impl<'a> Expr for Binary<'a> {
    fn accept<V>(self, mut visitor: impl Visitor<V>) -> V {
        return visitor.visit_binary_operation(self);
    }
}

pub struct Literal<'a> {
    value: &'a Value,
}

impl<'a> Expr for Literal<'a> {
    fn accept<V>(self, mut visitor: impl Visitor<V>) -> V {
        return visitor.visit_literal(self);
    }
}

trait Visitor<T> {
    fn visit_binary_operation(&mut self, expr: impl Expr) -> T;
    fn visit_literal(&mut self, expr: impl Expr) -> T;
}

Borrow checker is your teacher not enemy, try to learn from it not fight. First of all, the ExprType seems to contains some reference with lifetime. Can I see its definition?

5 Likes

The issue is as the error says:

cannot borrow `*self` as mutable more than once at a time

Your various functions apparently contain some sort of lifetime, and you can only make multiple borrows with immutable references.

I am new to rust and borrow checker is totally new concept to me
I have edited the post to include ExprType

thanks for replying :slight_smile:

Is the only modification you perform in the parser modifying the integer n? In that case the simplest approach would probably be to use a Cell<usize> instead.

This would allow you to not borrow mutably and thus allow your types to return multiple references.

1 Like

Alternatively split the lexer and token storage into two parts, so you can borrow the token storage mutably while borrowing the lexer code immutably.

3 Likes

That seems the only reason you need mutability is due to use of .increment(&mut self) and it spreads mutability requirement to the whole struct. Moreover n is internal implementation detail. To localize mutability internally to only Parser::n you may use Cell.

struct Parser {
   ...
   n: Cell<usize>
}

 ... 
 fn increment(&self) {
   self.n.set(self.n.get()+1);
 }
...

Otherwise you might implement separate iterator struct which contains this n value, spitting immutable and mutable parts.

1 Like

Yes, I am now modifying n, in future I like to implement Lazy lexer, so It only scan the source on demand
so, vec also needs to mutable

Generally you can't return multiple references from functions that take &mut self, so you need to use special types such as Cell that allow modification through shared references by limiting the type to be single threaded, or you need to refactor the code such that the things that return references don't need to modify anything.

1 Like

like this ?

struct Parser {
    pub source: String,
    lexer: Lexer,
}

struct TokenCache {
    n: usize,
    tokens: Vec<Token>,
}

Yeah, then functions on Parser can take &self and return shared references, while the TokenCache can be modified and not return references.

1 Like

Should I implement Lexer as Iterator ?

If you want to, go ahead, but I wouldn't say it's especially important in this case...

Besides iterators take mutable references to allow them to modify an internal counter such as your n.

It's probably simpler not to.

1 Like

I think It is better to implement a simpler one, then I will refactor to include Lazy lexer

Thanks, @alice for your help. :slight_smile:

For easiest beginner solution, just get rid of all those lifetime annotations and the ExprType owns all it have. I said easiest beginner but it can be most practical and idiomatic solution. Manual lifetime annotation is expert feature and you don't need to use it right now. if the tokens can be expensive to clone, try wrap them with Rc/Arc.

If you really want to dive into lifetimed solution, it seems it's better to add more layers on the architecture. tokens: &'a [Token] at the bottom, and both Parser<'a> and ExprType<'a>-s on top of if. It doesn't seems a good solution to have AST nodes referencing the parser itself, they should only references tokens.

1 Like