I'm trying to create a stack of environments (like when implementing an interpreter or compiler) where each Env has a reference to its parent, and a child Env should never outlive its parent. (And an Env will always have at most one child.)
I have the following code, but for some reason the compiler doesn't release the parent Env when the first child Env goes out of scope. How do I make this work? (Preferably without a cop-out solution like Rc<RefCell<>>)
struct Env<'a> {
parent: Option<&'a mut Env<'a>>,
}
fn main() {
let mut parent_env = Env{parent: None};
// This works:
{
let child_env_1 = Env{
parent: Some(&mut parent_env)
};
_ = child_env_1;
}
// But doing it a second time doesn't work:
{
// At this point, child_env_1 should have went out of scope
// and released the mutable reference to parent_env, no?
// Why does the compiler think parent_env is still borrowed?
let child_env_2 = Env{
parent: Some(&mut parent_env)
};
_ = child_env_2;
}
}
Rust playground:
Error:
Compiling playground v0.0.1 (/playground)
error[E0499]: cannot borrow `parent_env` as mutable more than once at a time
--> src/main.rs:22:26
|
11 | parent: Some(&mut parent_env)
| --------------- first mutable borrow occurs here
...
22 | parent: Some(&mut parent_env)
| ^^^^^^^^^^^^^^^
| |
| second mutable borrow occurs here
| first borrow later used here
For more information about this error, try `rustc --explain E0499`.
error: could not compile `playground` (bin "playground") due to 1 previous error
It's impossible to make a linked-list-stack of mutably borrowed Envs. [Update: This is not quite accurate; see below.] This is because having a &mut Env allows you to, in principle, replace the Env with a different Env (even if you don’t want to ever do that), and the borrow checking to allow that to happen soundly would require an unbounded list of different lifetimes, one for each parent stack frame. When you create &'a mut Env<'a> you collapse that list of lifetimes into a single lifetime, which gets the whole thing jammed up. (Even outside of stack-like cases, you should almost never write &'a mut SomeType<'a>, with the same lifetime in both places, because it causes the SomeType value to be exclusively borrowed forever.)
The necessary solution to implement an environment stack is to use & references and interior mutability instead, so that you can distinguish the immutable “spine” of the linked list from the mutable contents:
struct Env<'a> {
parent: Option<&'a Env<'a>>,
contents: RefCell<HashMap<Symbol, Value>>, // or whatever your application needs
}
When you do this, each time you create a new Env<'a> in the stack, the lifetime we are calling 'a gets shorter to reflect the new shorter-lived node. This is a valid thing to do, where it isn’t for &'a mut Env<'a>, because it's not possible to use the 'a lifetime to justify replacing any of the Envs, since there is not any &mut here. Formally, the type Env<'a> is “covariant in 'a” (whereas the case using &mut is “invariant in 'a”).
Note that in principle we could have a type that allows expressing parent in a way that it cannot be replaced. The closest thing we have today to this are trait objects: since you cannot really write to a dyn Trait it's then safe to coerce a &mut dyn Trait + 'long to a &mut dyn Trait + 'short. However we have no way to express this with other types.
If I create the stack based on immutable references, it will be possible to have more than one child created at the same time. I was trying to model it being possible to have only one child at a time. But it's definitely good enough for practical use, so thanks.
It seems like I would want to do something like this, could this possibly exist?
Obviously “yes, but no”. It would be pointless: compiler would have only one lifetime in the type which means what you want to create would still be impossible… and without that being possible what's the point of having such a type?
Yes and no. Your problem is related to that, but more fundamental. It looks that you are still at the stage where you you look on lifetimes as on “magic that would deliver what I want… somehow”.
But lifetimes are not magic! One doesn't need to know exact rules of covariant/contracvariant/invariant types to understand that what you want is impossible.
IOW: you want to stuff information about potentially endless number of possible lifetime configurations into one type.
But in Rust one lifetime argument may only carry one lifetime possibility! These things just simply couldn't work!
Covariant/contravariant/invariant lifetime add an interesting twist, because they allow one to shrink or expand lifetimes in types… but they still couldn't overcome that fundamental limitation: one lifetime sigil in type == one lifetime.
One may imagine an entirely different language where one lifetime sigil may hide endlessly complicated set of lifetimes “under the hood”, but that would be extremely clever… and extremely hard to understand.
Variadics may be a solution where you would be able to declare something like that:
Thanks for reminding me of this. @paul-andre Here is a demonstration of using trait objects to construct an environment linked list without interior mutability:
struct Frame<'a> {
value: Option<String>,
parent: &'a mut (dyn Env + 'a),
}
struct Nil;
trait Env {
fn get(&mut self) -> Option<&mut String>;
}
impl Env for Frame<'_> {
fn get(&mut self) -> Option<&mut String> {
match self.value {
Some(ref mut s) => Some(s),
None => self.parent.get(),
}
}
}
impl Env for Nil {
fn get(&mut self) -> Option<&mut String> {
None
}
}
/// Proof that we can write a recursive eval-like function with this
fn eval(env: &mut dyn Env, which: bool) -> String {
if which {
env.get().unwrap().clone()
} else {
eval(
&mut Frame {
value: Some(String::from("Hello")),
parent: env,
},
true,
)
}
}
fn main() {
let parent_env: &mut dyn Env = &mut Nil;
assert_eq!(eval(parent_env, false), "Hello");
}
(It's not necessary to have two different types Frame and Nil instead of using Option for parent links; I just did that because it’s a sort of simplicity to use dyn for both purposes instead of needing to use dynand an enum.)
Depending on your exact use case, you may be able to use my temp-stack crate, though I have to admit that the ergonomics around mutable stacks are not ideal: example.
Note that in principle we could have a type that allows expressing parent in a way that it cannot be replaced.
I'm using Pin<&mut _> for this purpose, which is more restrictive than necessary. The temp-inst crate that temp-stack is based on alternatively offers regular mutable references via a closure-based API, which panics if the object was replaced. (Unless it was restored afterwards, but then that would actually be fine.)
It would be possible to support this variant in temp-stack also; so far I hadn't encountered a use case with mutable stacks, actually.
Actually, I don't know. I wasn't excepting it to work... It shouldn't, I think, because at the second level, the lifetime 'b is replicated, and it becomes the equivalent of the original code. I don't know if this is a bug or not. If someone can explain, I'm very curious about the explanation
I'm not sure why it works, but it's very likely that it depends on the fact this is all inside the same function, so the borrow checker can assign lifetimes with a bit more freedom. If you try to pass the parent environment to a function after creating two levels (not sure why you need two and not just one...) of child environments it will break. Rust Playground
I think that, basically, adding more lifetime parameters means you have to nest deeper before you're forced to create a &'x mut Env<..., 'x, ...> (exclusively borrowing something forever).