How to refactor mutable borrow with immutable at same time?

I am sorry to have such a long codes to show my problem. When I wrote some simplified codes, the error gones.

I want to match unary expression and primary expression. The unary expression is a operator plus unary or primary expression. For example, in !false, the ! is a operator, false is a primary expression, !false is a unary expression. and the unary expression will match right side first, if my unary expression is !!!false, the process will be:

(!!! + false) -> (!! + true) -> (! + false) -> true

I wrote recursive function to solve it, there will be more expressions in the future, and the state of process tokens (line, current position) will be saved in ParserContext:

pub fn unary(context: &mut ParserContext) -> MyResult<Box<dyn Expr>> {
    // match such as +1、!false, and `is_match` has side effect.
    if is_match(context, TokenType::Bang) || is_match(context, TokenType::Minus) {
        if let Some(operate) = get_prev_token(context) {
            let right = unary(context).unwrap();
                           // ^^^ my first question is about here
            return Ok(Box::new(Unary::new(operate, right)));
                                       // ^^^ my second question is about here.
        }
    }

    // match literal, such as number, string, (1 + 1)
    primary(context)
}

those codes got two errors, and I have two questions:

  1. E0502 shows me that we should't have any other references to the variable before trying to access it mutably, but I need to do that in my situation, I want validate some conditions first, and then call unary recursively, I have no idea how to refactor it, so I am very curious the replacement to realize it in Rust.
  2. I fixed the second error by adding some lifetime annotations, but I am not sure is that a right way to solve it, or maybe I should avoid write codes like this?
-  pub fn unary(context: &mut ParserContext) -> MyResult<Box<dyn Expr>> {
+ pub fn unary<'a>(context: &'a mut ParserContext) -> MyResult<Box<dyn Expr + 'a>> {

pub struct Unary<'a> {
     operator: &'a Token,
-    right: Box<dyn Expr>,
+    right: Box<dyn Expr + 'a>,
}

impl<'a> Unary<'a> {
-    pub fn new(operator: &'a Token, right: Box<dyn Expr>) -> Self {
+   pub fn new(operator: &'a Token, right: Box<dyn Expr + 'a>) -> Self {

        Self { operator, right }
    }
}

use std::error::Error;

type MyResult<T> = Result<T, Box<dyn Error>>;

fn main() {}

struct ParserContext {
    tokens: Vec<Token>,
    current: usize,
}

pub struct Token {
    token_type: TokenType,
    lexeme: String,
    literal: String,
    line: usize,
}

impl Token {
    pub fn get_token_type(&self) -> TokenType {
        self.token_type
    }
    pub fn new(token_type: TokenType, lexeme: &str, literal: &str, line: usize) -> Self {
        Self {
            token_type,
            lexeme: String::from(lexeme),
            literal: String::from(literal),
            line,
        }
    }
}

#[derive(PartialEq, Clone, Copy)]
enum TokenType {
    LeftParen,
    RightParen,
    Minus,
    Plus,
    Bang,
    BangEqual,
    Nil,
}

pub trait Expr {}

impl Expr for Unary<'_> {}
impl Expr for Literal {}

pub enum LiteralType {
    Nil,
}

pub struct Literal {
    val: String,
    t: LiteralType,
}

impl Literal {
    pub fn new(val: &str, t: LiteralType) -> Self {
        Self {
            val: val.to_owned(),
            t,
        }
    }
}

pub struct Unary<'a> {
    operator: &'a Token,
    right: Box<dyn Expr>,
}

impl<'a> Unary<'a> {
    pub fn new(operator: &'a Token, right: Box<dyn Expr>) -> Self {
        Self { operator, right }
    }
}

pub fn unary(context: &mut ParserContext) -> MyResult<Box<dyn Expr>> {
    // match such as +1、!false
    if is_match(context, TokenType::Bang) || is_match(context, TokenType::Minus) {
        if let Some(operate) = get_prev_token(context) {
            let right = unary(context).unwrap();
            return Ok(Box::new(Unary::new(operate, right)));
        }
    }

    // match literal, such as number, string, (1 + 1)
    primary(context)
}

pub fn is_match(context: &mut ParserContext, token_type: TokenType) -> bool {
    match get_current_token(context).map(|token| token.get_token_type()) {
        Some(t) if t == token_type => {
            context.current += 1;
            true
        }
        _ => false,
    }
}

pub fn primary(_context: &mut ParserContext) -> MyResult<Box<dyn Expr>> {
    unimplemented!()
}

pub fn get_prev_token(context: &ParserContext) -> Option<&Token> {
    context.tokens.get(context.current - 1)
}

pub fn get_current_token(context: &ParserContext) -> Option<&Token> {
    context.tokens.get(context.current)
}

(Playground)

Errors:

   Compiling playground v0.0.1 (/playground)
error[E0502]: cannot borrow `*context` as mutable because it is also borrowed as immutable
  --> src/main.rs:82:25
   |
81 |         if let Some(operate) = get_prev_token(context) {
   |                                               ------- immutable borrow occurs here
82 |             let right = unary(context).unwrap();
   |                         ^^^^^^^^^^^^^^ mutable borrow occurs here
83 |             return Ok(Box::new(Unary::new(operate, right)));
   |                    ---------------------------------------- returning this value requires that `*context` is borrowed for `'static`

error: lifetime may not live long enough
  --> src/main.rs:83:20
   |
78 | pub fn unary(context: &mut ParserContext) -> MyResult<Box<dyn Expr>> {
   |                       - let's call the lifetime of this reference `'1`
...
83 |             return Ok(Box::new(Unary::new(operate, right)));
   |                    ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ returning this value requires that `'1` must outlive `'static`
   |
help: to declare that the trait object captures data from argument `context`, you can add an explicit `'_` lifetime bound
   |
78 | pub fn unary(context: &mut ParserContext) -> MyResult<Box<dyn Expr + '_>> {
   |                                                                    ++++

error[E0502]: cannot borrow `*context` as mutable because it is also borrowed as immutable
  --> src/main.rs:88:5
   |
81 |         if let Some(operate) = get_prev_token(context) {
   |                                               ------- immutable borrow occurs here
82 |             let right = unary(context).unwrap();
83 |             return Ok(Box::new(Unary::new(operate, right)));
   |                    ---------------------------------------- returning this value requires that `*context` is borrowed for `'static`
...
88 |     primary(context)
   |     ^^^^^^^^^^^^^^^^ mutable borrow occurs here

For more information about this error, try `rustc --explain E0502`.
error: could not compile `playground` due to 3 previous errors

I'm fairly sure that the second part, where you replace Box<dyn Expr> with Box<dyn Expr + 'a> is correct.

Box<dyn Expr> implicitly is Box<dyn Expr + 'static>, and given the implied 'static lifetime on the function return value (MyResult<Box<dyn Expr>>), rustc wants the the return value to be 'static.

By adding the 'a to the parameter and the return value, it tells Rust that the return value needs to live as long as 'a (instead of 'static), and the 'a lifetime is attached to the context parameter's lifetime.

Normally adding lifetime annotations tell the compiler to extend the lifetime of a borrowed value, in this case it's actually decreasing it.


The first part, the let Some(operate) is borrowing from context. If we can free up context (e.g. by cloning Token) it would work. But I'm guessing you want to not clone Token since it's got Strings in it.

One way is to not hold on to the borrow, and then re-get operate afterwards:

if get_prev_token(context).is_some() {
    let right = unary(context).unwrap();
    let operate = get_prev_token(context).expect("unreachable");
    return Ok(Box::new(Unary::new(operate, right)));
}

But when doing that, you run into, now right is borrowing context, and you can't get operate because context is being borrowed (playground):

82 |             let right = unary(context).unwrap();
   |                               ------- mutable borrow occurs here
83 |             let operate = get_prev_token(context).expect("unreachable");
   |                                          ^^^^^^^ immutable borrow occurs here
84 |             return Ok(Box::new(Unary::new(operate, right)));
   |                    ---------------------------------------- returning this value requires that `*context` is borrowed for `'a`

That's because the returned right is borrowing context for the 'a we introduced in place of 'static.

I haven't got time right now to think of hold to solve it, but perhaps someone else will -- maybe something along the lines of fn unary<'a>(left: Option<&'a Token>, context: &'a mut ParserContext).


When I wrote some simplified codes, the error gones.

usually that's a good thing :smile:

1 Like

The compiler is probably saving you from dangling references. If you need to update ParserContext::token in primary, it will invalidate all the token borrows you're trying to hold on to. (The Vec could reallocate and move all its contents.)

If you don't need to, you could perhaps put current in a Cell and make all the functions immutable.

My medium level observation is that there is a lot of getter-like operation going on that's not very idiomatic within a single module, as it requires borrowing the whole struct. (Getting rid of them probably won't fix this particular problem, though.)

My higher level suggestion is to find a string interning library or such [1], so you can make Token cheap to clone, and then get rid of all the lifetimes holding structs you can.


  1. or maybe even just use Arc<str> instead of String ↩ī¸Ž

3 Likes

I am struggling in the ownership of Rust for those days, Even though I solved this problem by the help of great friends here, I blocked again when I parse factor expression. I think I was go the wrong way about writing codes, now I change the function's return type, after that, all thing be simple!

I changed Expr to enum type to hold all AST nodes:

pub enum Expr {
    Binary {
        left: Box<Expr>,
        right: Box<Expr>,
        operate: Token,
    },
    Unary {
        right: Box<Expr>,
        operator: Token,
    },
    Grouping {
        expression: Box<Expr>,
    },
    Literal {
        val: TokenLiteral,
    },
}

and then, return the Option<Expr> instead of MyResult<Box<dyn Expr>>, and also change Token 's properties from String to Arc<String> to make clone cheap.

   fn unary(&mut self) -> Option<Expr> {
        if self.is_match_one_of([TokenType::Bang, TokenType::Minus]) {
            let operator = self.previous().clone();
            let right = self.unary()?;
            return Some(Expr::Unary {
                right: Box::new(right),
                operator,
            });
        }

        self.primary()
    }

Thanks everyone !!!