How to make RefCell's Ref live long enough

Question

I'm working on an interpreter in Rust for a programming language. Everything was going fine until I decided to implement closures, which caused some massive headaches because now each closure value needs to have a mutable reference of the environment it was defined in. I finally got it to mostly work with RefCell, but I'm now running into one more error that I can't figure out how to solve.

error: `e` does not live long enough
   --> src/interpreter.rs:163:23
    |
163 |             let val = e.lookup(&name);
    |                       ^ does not live long enough
...
169 |         }
    |         - borrowed value only lives until here
    |
note: borrowed value must be valid for the lifetime 'b as defined on the body at 147:93...
   --> src/interpreter.rs:147:94
    |
147 | fn eval_expr<'a, 'b, 'c>(ast: &'a Expr, env: &'b RefEnv<'b>) -> Result<Value<'b>, Error<'c>> {
    |                                                                                              ^

error: aborting due to previous error

Here is the relevant code:

use std::collections::HashMap;
use std::cell::RefCell;
#[derive(Clone, Debug)]
pub enum Value<'a> {
    Number(f64),
    UserFunc(Definition, Enviroment<'a>),
}

#[derive(Clone, Debug)]
pub struct Definition;

pub enum Expr {
    Name(String),
}

// Nothing to do with the problem
pub enum Error {
    UndefinedName(String),
}

#[derive(Debug, Clone)]
pub struct Enviroment<'a> {
    current_frame: HashMap<String, Option<Value<'a>>>,
    prev: Option<&'a Enviroment<'a>>,
}
impl<'a> Enviroment<'a> {
    pub fn new() -> Enviroment<'a> {
        Enviroment {
            current_frame: HashMap::new(),
            prev: None,
        }
    }
    pub fn extend(bindings: Vec<(String, Value<'a>)>,
                  prev: Option<&'a Enviroment<'a>>)
                  -> Enviroment<'a> {
        let mut frame = HashMap::new();
        for (key, val) in bindings {
            frame.insert(key, Some(val));
        }
        Enviroment {
            current_frame: frame,
            prev: prev,
        }
    }
    pub fn lookup(&self, name: &str) -> Option<Option<Value>> {
        let val = self.current_frame.get(&String::from(name));
        if val.is_some() {
            val.cloned()
        } else {
            if let Some(prev) = self.prev {
                prev.lookup(name)
            } else {
                None
            }
        }
    }
}

type RefEnv<'a> = RefCell<Enviroment<'a>>;

fn eval_expr<'a, 'b>(ast: &'a Expr, env: &'b RefEnv<'b>) -> Result<Value<'b>, Error> {
    match *ast {
        Expr::Name(ref name) => {
            let e = env.borrow();
            let val = e.lookup(&name);
            if let Some(Some(v)) = val {
                Ok(v)
            } else {
                Err(Error::UndefinedName(format!("{} is not defined", name)))
            }
        }
    }
}

fn main() {}

How can I change the code to make it compile?

Answer 1

This isn't really a problem regarding RefCell or Ref. You have this method:

impl<'a> Enviroment<'a> {
    pub fn lookup(&self, name: &str) -> Option<Option<Value>>;
}

After lifetime elision is reversed, that is equivalent to:

impl<'a> Enviroment<'a> {
    pub fn lookup<'b, 'c>(&'b self, name: &'c str) -> Option<Option<Value<'b>>>;
}

Which means that the Value is only guaranteed to contain values that live as long as the Environment. What you really want is to tie the Value to whatever the Environment references:

impl<'a> Enviroment<'a> {
    pub fn lookup(&self, name: &str) -> Option<Option<Value<'a>>>;
}

This allows your example code to compile.