1

I'm trying to write a simple variable environment stack for an interpreter. The design is essentially a linked list of hashmap, where each hashmap represents a nested scope, starting from global. My API for the local scope is to use RAII, so that only when the local scope goes out of scope, one can work with the previous scope. (rust playground)

use std::collections::HashMap;

struct Env<'a, T> {
    map: HashMap<String, T>,
    parent: Option<&'a mut Env<'a, T>>
}

impl<'a, T> Env<'a, T> {
    fn new() -> Self {
        Self {map: HashMap::new(), parent: None}
    }

    fn insert(&mut self, key: String, val: T) {
        self.map.insert(key, val);
    }

    fn get(&self, key: &str) -> Option<&T> {
        self.map.get(key).or_else(|| self.parent.as_ref().map(|parent| parent.get(key)).flatten())
    }

    fn get_mut(&mut self, key: &str) -> Option<&mut T> {
        self.map.get_mut(key).or_else(|| self.parent.as_mut().map(|parent| parent.get_mut(key)).flatten())
    }

    fn new_scope(&'a mut self) -> Env<'a, T> {
        Env { map: HashMap::new(), parent: Some(self) }
    }
}

#[test]
fn test() {
    let mut global = Env::new();
    global.insert("x".to_string(), "global x");
    println!("{:?}", global.get("x")); // global x
    println!("{:?}", global.get("y")); // none
    global.get_mut("x").map(|val| *val = "new global x");
    println!("{:?}", global.get("x")); // new global x
    {
        let mut local = global.new_scope();
        println!("{:?}", local.get("x")); // new global x
        local.get_mut("x").map(|val| *val = "new new global x");
        println!("{:?}", local.get("x")); // new new global x
        local.insert("x".to_string(), "local x");
        println!("{:?}", local.get("x")); // local x
        local.insert("y".to_string(), "y");
        println!("{:?}", local.get("y")); // y
    }
    // the following lines causes compiler error
    // i don't get it b/c `local` is already out of scope!!
    println!("{:?}", global.get("x")); // global x
    println!("{:?}", global.get("y")); // none
    global.insert("y".to_string(), "global y");
    println!("{:?}", global.get("y")); // global y
}

What I am not getting is that the compiler's complaint:

error[E0502]: cannot borrow `global` as immutable because it is also borrowed as mutable
  --> src/env2.rs:50:22
   |
39 |         let mut local = global.new_scope();
   |                         ------------------ mutable borrow occurs here
...
50 |     println!("{:?}", global.get("x")); // global x
   |                      ^^^^^^^^^^^^^^^
   |                      |
   |                      immutable borrow occurs here
   |                      mutable borrow later used here

line 39 occurs in the block scope, so the variable local is already dropped by line 50. My understanding is this should be OK, since local is already out of scope. In fact, even if local is not dropped, as long as local is no longer in use, it should still be OK, as in

fn main() {
    let mut x = 3;
    let mut_x = &mut x;
    *mut_x += 1;
    // mut_x is no longer in use
    let ref_x = &x;
    println!("{}", ref_x);
}

What am I missing here? So my questions are

  1. why the compiler is complaining when local is not only in use anymore but also out of scope?

  2. what is the fix? (i don't want to use RefCell due to performance overhead)

Thanks!

techhara
  • 77
  • 5
  • This should work: store `Option>` and then put `global = local.parent` at the bottom of the small block. But in general, `&'a T<'a>` is usually wrong. – drewtato Jun 07 '23 at 16:23
  • @drewtato `&'a T<'a>` is usually fine, only the mutable `&'a mut T<'a>` is problematic. – Chayim Friedman Jun 07 '23 at 16:49
  • 1
    @ChayimFriedman `&'a T<'a>` has the possibility to be useful, but usually when people use it, they are trying to express `&'a T<'b>` without an infinite quantity of lifetime arguments, which is not correct. – drewtato Jun 07 '23 at 16:56

0 Answers0