Lifetime of mutable reference

I am learning Rust by implementing an interpreter for Lox, and got stuck while working on the nested environments:

fn evaluate(&self, env: &mut Environment) -> Result<Literal, RuntimeError> {
    let mut last_value = Literal::Null;
    let mut local_env: Environment<'_> = Environment {
        values: HashMap::new(),
        enclosing: Some(env),
    };

    for statement in self.stmts.iter() {
        let res = statement.evaluate(&mut local_env);
        match res {
            Ok(val) => {
                last_value = val;
            }
            Err(err) => {
                return Err(err);
            }
        }
    }

    Ok(last_value)
}

This function is to evaluate the block, thus it has its own scope where variable names live. This is what local_env is for. Each local_env has to know its parent (enclosing block) so if a variable name is not found in the current block, it can look it up one block above.

Environment struct is defined as:

pub struct Environment<'a> {
    pub values: HashMap<String, Literal>,

    pub enclosing: Option<&'a mut Environment<'a>>,
}

Where lifetime 'a is introduced so it satisfies the compiler, but I kinda understand what it means here: the reference to parent has to live at least as long as this particular Environment (the encompassing block includes the child block).

My issue is the error message in this setup on Some(env):

lifetime may not live long enough
this usage requires that `'1` must outlive `'2`

Where lifetime '1 refer to the reference, '2 refer to Environment. So, what i do now, is to introduce some lifetime for the function so '1 and '2 is the same:

fn evaluate<'a>(&self, env: &'a mut Environment<'a>) -> Result<Literal, RuntimeError>;

This results in the following error though:

statement.rs(61, 5): `local_env` dropped here while still borrowed
statement.rs(43, 13): binding `local_env` declared here
statement.rs(41, 17): lifetime `'a` defined here
statement.rs(49, 23): argument requires that `local_env` is borrowed for `'a`
error[E0499]: cannot borrow `self.env` as mutable more than once at a time
  --> src/interpreter.rs:28:27
   |
13 | impl<'a> Interpreter<'a> {
   |      -- lifetime `'a` defined here
...
28 |             stmt.evaluate(&mut self.env);
   |             --------------^^^^^^^^^^^^^-
   |             |             |
   |             |             `self.env` was mutably borrowed here in the previous iteration of the loop
   |             argument requires that `self.env` is borrowed for `'a`

This is where i am stuck, i was not able to understand what is the issue here. Line 61 is the end of fn envaluate, so local_env is dropped there, which is perfectly fine (local block variables are removed when leaving the block). I assume the key to understand this error is the fourth line of the error message: local_env is borowed for 'a, but i just cannot see this through.

I can't put in the time to see if it completely solves your problem at the moment, but try making the lifetimes in Environment and fn evaluate distinct:

pub struct Environment<'a, 'env> {
    pub values: HashMap<String, Literal>,
    pub enclosing: Option<&'a mut Environment<'env>>,
}

fn evaluate(&self, env: &mut Environment<'_, '_>) -> Result<Literal, RuntimeError>;

See here for why &'a mut Thing<'a> is an antipattern.

1 Like

Note that you didn't update enclosing to give two lifetime parameters to Environment, and there aren't two distinct ones that can be put there. This code won't compile and can't be made to. In general, this is a linked-list-ish structure and you can't make a linked list whose backbone is &muts because you need as many distinct lifetime parameters as nodes in the list.

However, it's possible with & since &'a Environment<'a> can be fine — so you make the data interior mutable:

pub struct Environment<'env> {
    pub values: RefCell<HashMap<String, Literal>>,
    pub enclosing: Option<&'env Environment<'env>>,
}

The key difference between this and the &mut approach, that makes the compiler accept it, is that without the &muts, it's not possible to change the value of enclosing itself, i.e. to change the structure of the list of environments. You can only change the values, which contain no references.

4 Likes

That worked!
I definitely need to linger on what just happened though:) Just for reference for other people, fn evaluate now looks like this:

fn evaluate<'a>(&self, env: &'a Environment<'a>) -> Result<Literal, RuntimeError> {
    let mut last_value = Literal::Null;
    let local_env: Environment<'_> = Environment {
        values: RefCell::new(HashMap::new()),
        enclosing: Some(env),
    };

    for statement in self.stmts.iter() {
        let res = statement.evaluate(&local_env);
        match res {
            ...
    }

    Ok(last_value)
}