Eventually, a bird's got to leave the nest.
This chapter is entirely dedicated to the problem of nested environments, as they are one of the most complicated challenges a programming language implementation has to face.
Apparently, creating nested environments is just a matter of building a hierarchy of them, but the introduction of functions that use outer variables (closures) uncovers the real problem, which is how long environments should live and who owns them. This is particularly important in Rust, where the compiler is extremely strict with memory allocation and ownership.
We will start from the current state of the code and implement a first solution that imitates the Java code. We will discuss why it doesn't work in Rust and implement a new solution that passes the tests. At the end of the chapter, we will see that the code still has important limitations, and that the future introduction of functions will require yet another implementation.
So far, we implemented a single environment that is created at the beginning of the life of the interpreter and passed down to every statement that is executed.
With blocks, we need to change the rules of the game. The example that Robert Nystrom provides in his book is the following:
var a = "global a";
var b = "global b";
var c = "global c";
{
var a = "outer a";
var b = "outer b";
{
var a = "inner a"; 1
print a; // inner a 2
print b; // outer b
print c; // global c
}
print a; // outer a 3
print b; // outer b
print c; // global c
}
print a; // global a
print b; // global b
print c; // global cWhich can be distilled into the following requirements:
There is however an important detail of the Lox implementation: assigning a variable changes it in the scope where it was declared, which may be an outer one. An example of this behaviour would be the following:
var a = "global a";
var b = "global b";
var c = "global c";
{
a = "inner a"; 1
print a; // inner a
}
print a; // inner a 2
print b; // global b
print c; // global cPlease note that the block assigns 1 the variable instead of declaring it, and that this affects 2 the variable defined in the outer environment.
Let's have a look at what the book says. First of all, assignment must not create a new variable: "The key difference between assignment and definition is that assignment is not allowed to create a new variable. In terms of our implementation, that means it’s a runtime error if the key doesn’t already exist in the environment’s variable map." (8.4 Assignment).
Moreover, assignment is called recursively through the hierarchy: "[...] variable lookup and assignment work with existing variables and they need to walk the chain to find them." (8.5 Scope).
The Java implementation of Lox satisfies these requirements with a simple design: each environment holds a reference to its parent. Every Java reference can be shared and mutated, and the Garbage Collector frees an environment when nothing is pointing to it any more. This design allows the author to implement closures in chapter 10 without changing anything, even though chapter 11 will fix a subtle bug related to lexical scoping. At that point, the Java implementation introduces a static resolver that computes where each variable lives.
In Rust, a simple implementation that uses references doesn't work. A child environment that can change the variables of its parent needs a mutable reference (&mut) to it, and a mutable reference is exclusive: as long as the child holds it, nothing else can access the parent.
To show the problem in a clear way, we will now implement this solution with an immutable reference. We will see that it allows us to define blocks and to pass every test that doesn't attempt to change variables defined in the parent.
We can try to follow the Java strategy by storing a reference to the parent inside the struct Environment:
src/environment.rs #[derive(Debug)]
pub struct Environment {
pub struct Environment<'a> {
parent: Option<&'a Self>,
values: HashMap<String, Value>,
}Please note that Rust forces us to introduce a lifetime parameter in both the struct and the field. Every reference in Rust has a lifetime, but in a structure the compiler cannot infer the lifetimes, as it is just a type declaration, so we need to be explicit.
The use of Self hides the details of lifetimes, so let's expand that:
src/environment.rs pub struct Environment<'a> {
parent: Option<&'a Environment<'a>>,
values: HashMap<String, Value>,
}Please note that here 'a is not the lifetime of the environment, but the lifetime of the internal borrow.
Why do we use the same lifetime for both the borrow (&'a) and for the parent's own borrow (Environment<'a>)? Can't we use two different lifetimes? The recursive nature of the type makes it impossible. Let's see what would happen:
src/environment.rs // An environment that borrows
// its parent for 'a.
pub struct Environment<'a> {
// Borrows for 'a
// |
// | Another environment that
// | borrows its parent for 'b.
// | |
// v v
parent: Option<&'a Environment<'b>>,
values: HashMap<String, Value>,
}This is the core issue: the parent environment is another environment and thus borrows its own parent for a certain lifetime 'b, which is however not known. Therefore, we need to declare it:
src/environment.rs // An environment that borrows
// for 'a another environment that
// borrows another environment for 'b.
pub struct Environment<'a, 'b> {
// Borrows for 'a
// |
// | Another environment that
// | borrows its parent for 'b.
// | |
// | | The definition of Environment requires
// | | now two lifetimes, the second being how
// | | long the grandparent borrows its own parent.
// | | This causes the definition to become
// | | `pub struct Environment<'a, 'b, 'c>`.
// | | |
// v v v
parent: Option<&'a Environment<'b, 'c>>,
values: HashMap<String, Value>,
}The problem is now clearly visible. Every lifetime we add for the parent requires another one for the parent's parent, so the list of parameters would never end.
Therefore, we go back to the definition that uses a single lifetime:
src/environment.rs pub struct Environment<'a> {
parent: Option<&'a Environment<'a>>,
values: HashMap<String, Value>,
}The fact that both the borrow and the parent have the same lifetime signature means that:
'a through &'a.'a (Environment<'a>).It is important to note that this is not a problem at the moment. Consider the ancestor of all environments, the global environment. This is borrowed by execute in main before any blocks started, and main needs it again when the block ends. Inside a block, the child's borrow of its parent environment is used only to read (immutable borrow), and the compiler considers the borrow ended when the child is dropped at the end of the block itself. Since the borrow is ended, the code after the block can use the global environment again. Because of the single lifetime 'a used in the structure, the compiler considers the whole hierarchy at any depth of nesting as a set of borrows that last as long as the current environment. This is exactly what will change with a mutable borrow.
Now that Environment has a lifetime we need to specify it when we implement the structure as well:
src/environment.rs impl Environment {
impl<'a> Environment<'a> {
...
}Given that we added a new field we need to change the initialisation method:
src/environment.rs impl<'a> Environment<'a> {
pub fn new() -> Self {
Self {
parent: None,
values: HashMap::new(),
}
}We can also add a method that attaches a parent to an existing environment:
src/environment.rs impl<'a> Environment<'a> {
// Assign the given parent to the environment.
pub fn add_parent(&mut self, parent: &'a Self) {
self.parent = Some(parent);
}Please note that we need to explicitly declare the lifetime of parent as it is part of the type declaration. At this point, we can connect the new environment we create for a block to the parent environment:
src/statement.rs pub fn execute(
Statement::Block(v) => {
let mut local_env = Environment::new();
// Link the local environment
// with the parent one.
local_env.add_parent(env);
for statement in v.iter() {
execute(statement, &mut local_env, output)?;
}
}However, the variable retrieval mechanism doesn't use the parent environment yet, so we need to change that logic:
src/environment.rs impl<'a> Environment<'a> {
pub fn get(&self, name: &str) -> EnvironmentResult<Value> {
self.values
.get(name)
.cloned()
.ok_or_else(|| EnvironmentError {
message: format!("Undefined variable {}.", name),
})
// Use the internal value storage
// to retrieve the value of the key.
let value = self.values.get(name).cloned();
// Extract the actual value if
// present, otherwise query the
// parent environment.
// If no value is present and there
// is no parent environment,
// return an error.
let Some(v) = value else {
// Find the parent environment.
let Some(p) = self.parent else {
// There is no parent environment.
return Err(EnvironmentError {
message: format!("Undefined variable {}.", name),
});
};
// Return the value from the
// parent environment.
return p.get(name);
};
Ok(v)
}To test these changes we can create some tests with a hierarchy of environments:
src/environment.rs mod tests {
#[test]
// Test that the method `get` works
// correctly when used to retrieve the
// value of a variable defined in the
// parent environment and not in the
// child one.
fn test_get_variable_from_parent() {
let mut parent = Environment::new();
let mut child = Environment::new();
// Define the variable in the parent
// environment without using a method
// of Environment to avoid cyclic
// test definitions.
parent.values.insert(
String::from("somevar"),
Value::String(String::from("parent")),
);
// Connect child and parent environments.
child.add_parent(&parent);
assert_eq!(
child.get("somevar"),
Ok(Value::String(String::from("parent")))
);
}
#[test]
// Test that the method `get` works
// correctly when used to retrieve the
// value of a variable defined both in
// the child environment and in the
// parent one.
fn test_get_variable_from_parent_shadow() {
let mut parent = Environment::new();
let mut child = Environment::new();
// Define the variable in the child
// environment without using a method
// of Environment to avoid cyclic
// test definitions.
child.values.insert(
String::from("somevar"),
Value::String(String::from("child")),
);
// Define the variable in the parent
// environment without using a method
// of Environment to avoid cyclic
// test definitions.
parent.values.insert(
String::from("somevar"),
Value::String(String::from("parent")),
);
// Connect child and parent environments.
child.add_parent(&parent);
assert_eq!(
child.get("somevar"),
Ok(Value::String(String::from("child")))
);
}
#[test]
// Test that the method `get` works
// correctly when used to retrieve the
// value of a variable defined in the
// grandparent environment, not in the
// child one, not in the parent one.
fn test_get_variable_from_grandparent() {
let mut grandparent = Environment::new();
let mut parent = Environment::new();
let mut child = Environment::new();
// Define the variable in the grandparent
// environment without using a method
// of Environment to avoid cyclic
// test definitions.
grandparent.values.insert(
String::from("somevar"),
Value::String(String::from("grandparent")),
);
// Connect parent and grandparent environments.
parent.add_parent(&grandparent);
// Connect child and parent environments.
child.add_parent(&parent);
assert_eq!(
child.get("somevar"),
Ok(Value::String(String::from("grandparent")))
);
}
#[test]
// Test that the method `get` works
// correctly when used to retrieve the
// value of a variable defined in the
// grandparent environment and in the
// parent one, but not in the child one.
fn test_get_variable_from_grandparent_shadow() {
let mut grandparent = Environment::new();
let mut parent = Environment::new();
let mut child = Environment::new();
// Define the variable in the parent
// environment without using a method
// of Environment to avoid cyclic
// test definitions.
parent.values.insert(
String::from("somevar"),
Value::String(String::from("parent")),
);
// Define the variable in the grandparent
// environment without using a method
// of Environment to avoid cyclic
// test definitions.
grandparent.values.insert(
String::from("somevar"),
Value::String(String::from("grandparent")),
);
// Connect parent and grandparent environments.
parent.add_parent(&grandparent);
// Connect child and parent environments.
child.add_parent(&parent);
assert_eq!(
child.get("somevar"),
Ok(Value::String(String::from("parent")))
);
}
#[test]
fn test_get_error_with_hierarchy() {
let parent = Environment::new();
let mut child = Environment::new();
// Connect child and parent environments.
child.add_parent(&parent);
assert_eq!(
child.get("somevar"),
Err(EnvironmentError {
message: String::from("Undefined variable somevar."),
})
);
}We can also test the statement execution logic:
src/statement/tests/block.rs #[test]
// Test that the function `execute` works
// correctly when the statement is a
// block statement that contains correct
// statements and that defining a variable
// in the local environment shadows
// a variable with the same name in
// the parent environment.
fn test_define_variable_shadows_parent() {
// The parent environment.
let mut env = Environment::new();
// The name of the variable
// we are going to use.
let var_name = String::from("somevar");
// Define the variable in the
// parent environment.
env.define(var_name.clone(), Value::Boolean(true));
// The value we are going to use.
let var_value = 42.0;
// A token for the printed variable name.
let identifier_token = Token {
ttype: TokenType::Identifier,
lexeme: var_name.clone(),
literal: TokenLiteral::Null,
line: 1,
};
// The statement we are going to process
// contains a block.
let statement = Statement::Block(vec![
Statement::Var(
var_name.clone(),
Expression::Literal(Literal::Number(var_value)),
),
Statement::Print(Expression::Variable(identifier_token)),
]);
// Execute the statement.
let (result, output) = run_execute(&statement, &mut env);
assert_eq!(result, Ok(()));
assert_eq!(output, vec![Value::Number(var_value)]);
assert_eq!(env.get(&var_name).unwrap(), Value::Boolean(true));
}
#[test]
// Test that the function `execute` works
// correctly when the statement is a
// block statement that contains correct
// statements and that a variable defined
// in the parent environment can be read
// from the local one.
fn test_read_variable_from_parent() {
// The parent environment.
let mut env = Environment::new();
// The name of the variable
// we are going to use.
let var_name = String::from("somevar");
// Define the variable in the
// parent environment.
env.define(var_name.clone(), Value::Boolean(true));
// A token for the printed variable name.
let identifier_token = Token {
ttype: TokenType::Identifier,
lexeme: var_name,
literal: TokenLiteral::Null,
line: 1,
};
// The statement we are going to process
// contains a block.
let statement = Statement::Block(vec![Statement::Print(Expression::Variable(
identifier_token,
))]);
// Execute the statement.
let (result, output) = run_execute(&statement, &mut env);
assert_eq!(result, Ok(()));
assert_eq!(output, vec![Value::Boolean(true)]);
}This code passes some of the tests in stage 10 of the CodeCrafters challenge. It passes test case 3 that runs the following code:
var bar = "global bar";
var world = "global world";
var hello = "global hello";
{
var bar = "outer bar";
var world = "outer world";
{
var bar = "inner bar";
print bar;
print world;
print hello;
}
print bar;
print world;
print hello;
}
print bar;
print world;
print hello;However, it doesn't pass test case 4:
{
var foo = "outer foo"; 1
var world = "outer world";
{
foo = "modified foo"; 2
var world = "inner world";
print foo;
print world;
}
print foo;
print world;
}
print foo;The line 2 in the test does something new that we haven't seen yet. It tries to modify a variable defined in an outer scope 1. The current code can retrieve values from a parent, but cannot change them, as the parent is added to an environment with an immutable reference:
src/environment.rs #[derive(Debug)]
pub struct Environment<'a> {
parent: Option<&'a Self>,
values: HashMap<String, Value>,
}It is worth capturing this problem in a unit test, so that we can quickly verify alternative solutions in the future:
src/statement/tests/block.rs #[test]
// Test that the function `execute` works
// correctly when the statement is a
// block statement that contains correct
// statements and that assigning a variable
// in the local environment affects
// the variable defined in the parent
// environment if the local one doesn't
// contain it.
fn test_assign_variable_affects_parent() {
// The parent environment.
let mut env = Environment::new();
// The name of the variable
// we are going to use.
let var_name = String::from("somevar");
// Define the variable in the
// parent environment.
env.define(var_name.clone(), Value::Boolean(true));
// A token for the printed variable name.
let identifier_token = Token {
ttype: TokenType::Identifier,
lexeme: var_name.clone(),
literal: TokenLiteral::Null,
line: 1,
};
// The statement we are going to process
// contains a block.
let statement = Statement::Block(vec![Statement::Expression(Expression::Assignment {
identifier: identifier_token,
expression: Box::new(Expression::Literal(Literal::Boolean(false))),
})]);
// Execute the statement.
let (result, output) = run_execute(&statement, &mut env);
assert_eq!(result, Ok(()));
assert!(output.is_empty());
assert_eq!(env.get(&var_name).unwrap(), Value::Boolean(false));
}This test fails, exposing the issue we discussed.
This is the point where the current solution proves ineffective, and we need to change something in the code to support this new requirement. As we mentioned previously, we might try to change Environment to contain a mutable reference to the parent, but this is where Rust cannot follow Java. Let's have a look at the problem in detail.
As we know, Rust allows code to create any number of immutable references to the same value or a mutable one, never both. If we change the code to store a mutable reference to the parent we run into trouble:
src/environment.rs #[derive(Debug)]
pub struct Environment<'a> {
parent: Option<&'a mut Environment<'a>>,
values: HashMap<String, Value>,
}Should we try to change the struct as shown above and adjust add_parent to receive parent: &'a mut Self the compiler would stop with the following error:
error: lifetime may not live long enough
--> src/statement.rs:24:13
|
15 | env: &mut Environment,
| --- - let's call the lifetime of this reference `'1`
| has type `&mut Environment<'2>`
...
24 | local_env.add_parent(env);
| ^^^^^^^^^^^^^^^^^^^^^^^^^ argument requires that `'1` must outlive `'2`
Taking into account what we previously discussed regarding lifetimes, the problem is rather simple.
Remember that the core idea was that the parent was considered as short-lived and the borrow was ended when the child was freed. With a mutable reference (&mut Self, expanded to &'a mut Environment<'a>), the compiler cannot treat the parent in the same way.
Going back to the simple example of the global environment, we would have the following sequence of events:
execute.Intuitively, the problem is that the child might have written into the global environment something that has the same lifetime as the child itself. Once the block ends, that lifetime ends and the global environment would be left with content that is not stored in valid memory any more.
This means that the borrow cannot be released, which in turn means that the global environment is not usable, even after the child block is ended.
In Rust terms, the problem we discussed is related to variance [docs], and the discussion revolves around the question: "If the type Sub is a subtype of the type Super, is the generic type F<Sub> a subtype of F<Super>?". Variance is about how subtyping extends from type parameters to generic types.
Let's consider type theory for a minute using inheritance (which is something we don't have in Rust). The classic example is that Cat is a subtype of Animal (a cat is an animal and more). Consider the following:
Cat is Animal, so Source<Cat> is valid for Source<Animal>. This is reading, and what we expressed is called covariance.Cat is Animal, so Sink<Animal> is valid for Sink<Cat>. This is writing, and what we expressed is called contravariance.Therefore, if I need to both read and write I need precisely the original type, not a subtype, not a supertype. If I need a box full of animals where I can put animals I cannot use a box of/for cats: a dog would not be accepted. Conversely, if I need a box of cats where I can put cats I cannot use a box of/for animals: it might contain a dog.
When we have composed types that allow us to both read and write the two requirements go in opposite directions and the only type that satisfies both is the original type. This is called invariance: the type parameter cannot be replaced by a sub- or supertype.
Let's look now at our specific case: references in Rust.
Rust considers the lifetime a parameter of any reference and type that contains them. In Rust, two types like &'a i64 and &'b i64 are considered different as Vec<i32> and Vec<i64> are. In other languages, subtyping comes mainly from inheritance (with classes or interfaces). Rust has no such concept, so subtyping is mostly connected to lifetimes. Therefore, references in the form &'a T have two parameters, 'a and T. The parameter 'a is not related to the contained type, it is a property of the reference (how long the reference lasts). The reference "device" is always used and never replaced, so a reference is always covariant in 'a.
Immutable references are covariant over both 'a and T. As immutable references are used to read a type, the analysis is:
'long is longer than 'short ('long is a subtype of 'short), then &'long T can be used where &'short T is needed: covariant. This is, intuitively, the idea that if I need a container that lasts for at least a short time I can pass a container that lives a long time.Sub specialises Super (Sub is a subtype of Super), then &'a Sub can be used where &'a Super is needed: covariant. Intuitively, if I want a pointer to read Super I can pass a pointer to Sub.Mutable references are covariant over 'a but invariant over T. As mutable references are used to both read and write a type, the analysis is:
'long is longer than 'short ('long is a subtype of 'short), then &'long mut T can be used where &'short mut T is needed: covariant. This works as before because we are not affecting the lifetime of the reference (we are not "writing" it). Intuitively, I still need a container that lasts for at least a short time, so I can pass a container that lives a long time.Sub specialises Super (Sub is a subtype of Super), then &'a mut Sub cannot be used where &'a mut Super is needed, and vice-versa: invariant. Intuitively, if I want a pointer to read and write Super I cannot pass a pointer to read and write Sub. The read part is fine, but the write part is not, because I might write a different subtype. Conversely, if I want a pointer to read and write Sub I cannot pass a pointer to read and write Super. The write part is fine, but the read part is not, because I might find something that is not a Sub.Let's now look at a more specific example: &'a mut Container<'b>. The compiler is happy to use 'long instead of 'short in the &'a part, as we saw above. A long-lived pointer to an environment works well where I need a short-lived pointer to an environment. However, it cannot use Container<'long> where Container<'short> is needed in the mut Container<'b> part: writing something short-lived in a place that expects long-lived entities is wrong.
Last, the concrete example we have in the code: &'a mut Environment<'a>. Here, we have the constraint imposed by recursion that both the length of the borrow and the lifetime of the contained elements are the same: 'a. Therefore, since the invariance of the second part is more restrictive, the whole type can only accept types with precisely the requested lifetime. This means that if we need &'short mut Environment<'short> we cannot use &'long mut Environment<'long> and vice-versa.
When we connect environments through the child-parent relationship we have precisely this problem: a short-lived Environment<'short> (the environment of a block) cannot contain &'long mut Environment<'long> (the environment of the enclosing block).
For a deeper dive into the matter of subtyping in type theory, you can read chapter 15 "Subtyping" in Types and Programming Languages by Benjamin C. Pierce.
Since the problem is that we cannot have shared mutable ownership of environments, a solution is to accept that and to take it to the other extreme of the ownership spectrum. When a block is entered, the local environment takes ownership of the entire chain of environments (the outer environment, its parent, its grandparent, and so on) for the duration of the block and releases it at the end.
Let's start changing the struct Environment so that it can optionally host an owned parent:
src/environment.rs #[derive(Debug)]
pub struct Environment<'a> {
pub struct Environment {
parent: Option<&'a Self>,
parent: Option<Box<Self>>,
values: HashMap<String, Value>,
}To capture the parent, we cannot use Option<Self>. Rather, we need Option<Box<Self>>. This is a classic problem of recursive definition: the compiler needs to know the size of a type, and if a struct contains itself this would result in having infinite size. Using a Box [docs] is a simple solution, as it is equivalent to using a pointer in C/C++, but with the addition of ownership.
We also drop the explicit lifetime signature. Lifetimes exist only to rule the duration of a borrow, and here the structure doesn't contain any. This means that the lifetime signatures disappear from the implementation of the struct and from the signature of add_parent, and it requires a couple of further adjustments to the code:
src/environment.rs impl<'a> Environment<'a> {
impl Environment {
...
// Assign the given parent to the environment.
pub fn add_parent(&mut self, parent: &'a Self) {
pub fn add_parent(&mut self, parent: &Self) {
self.parent = Some(parent);
self.parent = Some(Box::new(parent));
}
pub fn get(&self, name: &str) -> EnvironmentResult<Value> {
let Some(v) = value else {
// Find the parent environment.
let Some(p) = self.parent else {
let Some(p) = &self.parent else {
// There is no parent environment.
return Err(EnvironmentError {
message: format!("Undefined variable {}.", name),
});
};
// Return the value from the
// parent environment.
return p.get(name);
};
...Please note that we need to bind p to a reference. The method get borrows self, so it cannot move parent out of it. Previously, the code worked because Option<&Self> is Copy, so it was copying a pointer. Modern Rust allows us to use &self.parent which automatically transforms p into a reference [docs]. An alternative way to do it is with let Some(ref p).
Unfortunately, this version of add_parent is not acceptable, and the compiler fails with the message expected Environment, found &Environment. A Box owns its content, and we cannot build ownership out of the borrow &Self. Whenever you need an owned value and you have a borrow, the obvious solution is to clone the value, so we can try to go down that route:
src/environment.rs #[derive(Debug)]
#[derive(Debug, Clone)]
pub struct Environment {
parent: Option<Box<Self>>,
values: HashMap<String, Value>,
}
impl Environment {
// Assign the given parent to the environment.
pub fn add_parent(&mut self, parent: &Self) {
self.parent = Some(Box::new(parent));
self.parent = Some(Box::new(parent.clone()));
}This clearly means that the child environment is taking a full snapshot of the whole hierarchy, and this is the major issue of this solution, as we will see shortly.
Now we have finally overcome the limitation we had before. The code can access the parent in a mutable way because the child has full ownership of it, so we can rewrite Environment::assign in a recursive way, walking the hierarchy of environments to find where a variable was defined.
src/environment.rs impl Environment {
// Assign a new value to an existing
// variable. Return an error if the
// variable is not defined.
// Assign a new value to an existing variable.
// If the variable doesn't exist in the current
// environment it tries to assign it in the
// parent environment.
// If the variable doesn't exist and there
// is no parent environment it returns
// an error.
pub fn assign(&mut self, name: &str, value: Value) -> EnvironmentResult<()> {
let current = self.values.get_mut(name).ok_or_else(|| EnvironmentError {
message: format!("Undefined variable {}.", name),
})?;
if let Some(current) = self.values.get_mut(name) {
*current = value;
return Ok(());
}
*current = value;
// Find the parent environment.
let Some(p) = &mut self.parent else {
// There is no parent environment.
return Err(EnvironmentError {
message: format!("Undefined variable {}.", name),
});
};
Ok(())
// Assign the value in the
// parent environment.
p.assign(name, value)
}The compiler is satisfied: the local environment is now the sole owner of the whole hierarchy of environments as we are working on a full copy. Let's write a test for the new assignment logic:
src/environment.rs mod tests {
#[test]
// Test that the method `assign` works
// correctly when used to assign a value
// to a variable defined in the parent
// environment and not in the child one.
fn test_assign_variable_in_parent() {
let mut parent = Environment::new();
let mut child = Environment::new();
// Define the variable in the parent
// environment without using a method
// of Environment to avoid cyclic
// test definitions.
parent.values.insert(
String::from("somevar"),
Value::String(String::from("parent")),
);
// Connect child and parent environments.
child.add_parent(&parent);
// Assign the variable in the child.
assert_eq!(
child.assign("somevar", Value::String(String::from("child"))),
Ok(())
);
assert_eq!(
parent.values.get("somevar"),
Some(&Value::String(String::from("child")))
);
}Unfortunately this test fails. The first assertion is successful, which shows that the code found somevar and changed it, but the second assertion still shows the old value of the variable. Let's have a look at the CodeCrafters integration suite, where test 4 still fails. The integration test runs the following code:
{
var foo = "outer foo";
var world = "outer world";
{
foo = "modified foo"; 1
var world = "inner world";
print foo; 2
print world;
}
print foo; 3
print world;
}
print foo;The output of the test is:
[your_program] modified foo
[your_program] inner world
[your_program] outer foo
[your_program] outer worldThis shows that the code at 1 didn't modify the variable in the parent environment, so the code at 2 and 3 print two different outputs. They should have both printed modified foo as the local environment should have been able to modify the parent environment.
The reason is simple: to take ownership of the parent we were forced to clone it, and therefore the whole hierarchy. So, while the code at 1 is changing the variable in its parent environment, the parent it is acting upon is a copy of the original one, and the copy is dropped together with the local environment when the block ends before 3.
Therefore, we need to find a way to take ownership of the whole chain of environments without having to clone them. We need to use some sort of "temporary ownership", something that allows us to take ownership of a value and to put it back once we are done modifying it. This controlled ownership transfer comes in the form of std::mem::take [docs].
The function allows us to do precisely what was described, that is to move a value leaving a placeholder in its place. This is the only new concept we need to introduce: as we will see, the part where we put it back in place is almost trivial and doesn't require any special function.
What we did so far with Environment is still valid, because Box is a good way to take ownership of the parent. The function std::mem::take uses Default::default to generate a placeholder for the taken value, so we need to derive Default [docs]. This creates an implementation of the function that relies on each field of the structure to implement the trait, and in this case we have Option, whose default is None [docs], and HashMap, whose default is an empty hash map [docs].
src/environment.rs // The Environment derives Default
// in order to use std::mem::take
// which leaves an empty environment in place
// of the one that has been moved out.
#[derive(Debug, Clone)]
#[derive(Debug, Default)]
pub struct Environment {
parent: Option<Box<Self>>,
values: HashMap<String, Value>,
}Given we now derive Default, we can replace the implementation of Environment::new with a call to Environment::default. Having a constructor with the name new is a convention in Rust, even though in this case default provides the same service. If we have two constructors it's a good idea to have comments that clarify what each does.
src/environment.rs impl Environment {
pub fn new() -> Self {
Self {
parent: None,
values: HashMap::new(),
}
Self::default()
}Let's discuss the rest of the implementation. The plan is to have something like the following when we process a block:
src/statement.rs pub fn execute(
match statement {
Statement::Block(v) => {
// TAKE OWNERSHIP OF THE PARENT
// AND STORE IT INTO THE CHILD.
// REPLACE THE PARENT WITH A
// PLACEHOLDER.
// EXECUTE THE STATEMENT, POTENTIALLY
// MUTATING IT ASSIGNING VARIABLES.
// KEEP THE RESULT
// RESTORE THE PARENT.
// RETURN THE RESULT.
}Please note that we will have to make sure the parent is restored even if the statement execution fails. What we are doing here cannot be checked by the compiler at compile time, and it's our responsibility to leave everything as it was before we swapped the parent environment with the placeholder.
Given the structure above, we could keep the method add_parent and adapt its signature to receive parent: Self instead of parent: &Self. However, such a function would be dangerous: a double call would silently overwrite the old parent and therefore drop it and the whole hierarchy. A better idea is to introduce a constructor that accepts the parent: being an associated function, it will be impossible to call it twice.
src/environment.rs impl Environment {
// Assign the given parent to the environment.
pub fn add_parent(&mut self, parent: &Self) {
self.parent = Some(Box::new(parent.clone()));
}
// Create a new environment that
// takes ownership of the parent.
pub fn new_with_parent(parent: Self) -> Self {
Self {
parent: Some(Box::new(parent)),
values: HashMap::new(),
}
}How can we restore the parent once we terminate the execution of the block? Since we get the parent environment as an &mut parameter of execute we just need to overwrite it. We therefore need a simple method that extracts the parent from the child environment:
src/environment.rs impl Environment {
// Consume the environment and give
// back ownership of the parent.
pub fn restore_parent(self) -> Option<Self> {
self.parent.map(|p| *p)
}The code of restore_parent deserves an explanation. The code self.parent moves the field out of self, and map runs the given closure only if the value is Some. Inside the closure, *p moves the parent environment out of the Box. So, the function is just unboxing the parent and returning it. Please note that restore_parent owns self instead of borrowing it, which is what allows us to perform such transformations.
The Rust language defines two primitive reference types to access data indirectly: immutable references &T and mutable references &mut T. They are directly connected to ownership [docs], as through them one always borrows a value, in a shared/immutable way for &T and in an exclusive/mutable way for &mut T. Passing references always means passing a pointer, even though in the case of fat pointers like &[T] this also includes metadata (e.g. the length).
Since references like pi: &T or pm: &mut T borrow, the dereference syntax *pi/*pm is used to refer to a place [docs] in memory that the current code doesn't own. Nothing happens to the pointer when we prefix it with a *: what actually happens to the value stored at that address depends on the context. It is important to discuss what happens when reading it, as this involves the trait Copy.
In Rust, a type decides if its values are passed by copy or by move. The only difference between the two is the validity of the source after the operation. After you move something, the compiler considers the source invalid, but this is a pure semantic distinction: compiled code always copies the value bitwise.
When we read the content of a reference with let v = *pi a copy is triggered: we are trying to access something we do not own, so the value cannot be moved. Here, if the type T is Copy, the value is copied bitwise, but if it's not we get the error E0507: cannot move out of *pi which is behind a shared reference. The move is forbidden as the owner would be left with an invalid value, and this is true for both immutable and mutable references.
Conversely, a value that we own can not only be moved, but also partially moved [docs], which is what happens if we move a single field out of a struct. After a partial move the source struct cannot be used as a whole any more, but the remaining fields are perfectly accessible. When the struct goes out of scope, only the fields that haven't been moved are dropped. This works only if the struct doesn't implement Drop [docs], but we won't discuss this here.
Smart pointers [docs] are "data structures that act like a pointer but also have additional metadata and capabilities". For example, Rc [docs] adds reference counting. Usually, smart pointers implement the trait Deref [docs], so the dereferencing operation *p becomes *Deref::deref(&p) which means that what we end up with is a place behind a shared reference. Because of that, we cannot move the value out of a smart pointer either.
However, Box is a special type as the behaviour of * on it is implemented natively rather than through Deref. The compiler knows that a Box exclusively owns its value and therefore allows us to move it out of the box through the dereferencing operation.
This is precisely what *p does in restore_parent: it dereferences a Box<Environment> which, because of the special implementation of Box, moves the Environment out of the box and consumes the latter.
The removal of add_parent affects multiple tests. In particular, we must now swap the creation of the child and the parent as the assignment of the latter happens at creation time.
src/environment.rs mod tests {
#[test]
// Test that the method `get` works
// correctly when used to retrieve the
// value of a variable defined in the
// parent environment and not in the
// child one.
fn test_get_variable_from_parent() {
let mut parent = Environment::new();
let mut child = Environment::new();
// Define the variable in the parent
// environment without using a method
// of Environment to avoid cyclic
// test definitions.
parent.values.insert(
String::from("somevar"),
Value::String(String::from("parent")),
);
// Connect child and parent environments.
child.add_parent(&parent);
// Create a child environment
// connected with the parent.
let child = Environment::new_with_parent(parent);
assert_eq!(
child.get("somevar"),
Ok(Value::String(String::from("parent")))
);
}
#[test]
// Test that the method `get` works
// correctly when used to retrieve the
// value of a variable defined both in
// the child environment and in the
// parent one.
fn test_get_variable_from_parent_shadow() {
let mut parent = Environment::new();
let mut child = Environment::new();
// Define the variable in the child
// environment without using a method
// of Environment to avoid cyclic
// test definitions.
child.values.insert(
String::from("somevar"),
Value::String(String::from("child")),
);
// Define the variable in the parent
// environment without using a method
// of Environment to avoid cyclic
// test definitions.
parent.values.insert(
String::from("somevar"),
Value::String(String::from("parent")),
);
// Connect child and parent environments.
child.add_parent(&parent);
// Create a child environment
// connected with the parent.
let mut child = Environment::new_with_parent(parent);
// Define the variable in the child
// environment without using a method
// of Environment to avoid cyclic
// test definitions.
child.values.insert(
String::from("somevar"),
Value::String(String::from("child")),
);
assert_eq!(
child.get("somevar"),
Ok(Value::String(String::from("child")))
);
}
#[test]
// Test that the method `get` works
// correctly when used to retrieve the
// value of a variable defined in the
// grandparent environment, not in the
// child one, not in the parent one.
fn test_get_variable_from_grandparent() {
let mut grandparent = Environment::new();
let mut parent = Environment::new();
let mut child = Environment::new();
// Define the variable in the grandparent
// environment without using a method
// of Environment to avoid cyclic
// test definitions.
grandparent.values.insert(
String::from("somevar"),
Value::String(String::from("grandparent")),
);
// Connect parent and grandparent environments.
parent.add_parent(&grandparent);
// Create a parent environment
// connected with the grandparent.
let parent = Environment::new_with_parent(grandparent);
// Connect child and parent environments.
child.add_parent(&parent);
// Create a child environment
// connected with the parent.
let child = Environment::new_with_parent(parent);
assert_eq!(
child.get("somevar"),
Ok(Value::String(String::from("grandparent")))
);
}
#[test]
// Test that the method `get` works
// correctly when used to retrieve the
// value of a variable defined in the
// grandparent environment and in the
// parent one, but not in the child one.
fn test_get_variable_from_grandparent_shadow() {
let mut grandparent = Environment::new();
let mut parent = Environment::new();
let mut child = Environment::new();
// Define the variable in the parent
// environment without using a method
// of Environment to avoid cyclic
// test definitions.
parent.values.insert(
String::from("somevar"),
Value::String(String::from("parent")),
);
// Define the variable in the grandparent
// environment without using a method
// of Environment to avoid cyclic
// test definitions.
grandparent.values.insert(
String::from("somevar"),
Value::String(String::from("grandparent")),
);
// Connect parent and grandparent environments.
parent.add_parent(&grandparent);
// Connect child and parent environments.
child.add_parent(&parent);
// Create a parent environment
// connected with the grandparent.
let mut parent = Environment::new_with_parent(grandparent);
// Define the variable in the parent
// environment without using a method
// of Environment to avoid cyclic
// test definitions.
parent.values.insert(
String::from("somevar"),
Value::String(String::from("parent")),
);
// Create a child environment
// connected with the parent.
let child = Environment::new_with_parent(parent);
assert_eq!(
child.get("somevar"),
Ok(Value::String(String::from("parent")))
);
}
#[test]
fn test_get_error_with_hierarchy() {
let parent = Environment::new();
let mut child = Environment::new();
// Connect child and parent environments.
child.add_parent(&parent);
// Create a child environment
// connected with the parent.
let child = Environment::new_with_parent(parent);
assert_eq!(
child.get("somevar"),
Err(EnvironmentError {
message: String::from("Undefined variable somevar."),
})
);
}The new assignment logic needs to be tested:
src/environment.rs mod tests {
#[test]
// Test that the method `assign` returns
// the correct error when used to assign a
// value to a variable that doesn't exist
// in any environment of the hierarchy.
fn test_assign_error_with_hierarchy() {
let parent = Environment::new();
// Create a child environment
// connected with the parent.
let mut child = Environment::new_with_parent(parent);
assert_eq!(
child.assign("somevar", Value::Boolean(true)),
Err(EnvironmentError {
message: String::from("Undefined variable somevar."),
})
);
}
#[test]
// Test that the method `restore_parent`
// gives back the parent environment
// and drops the child one.
fn test_restore_parent() {
let mut parent = Environment::new();
// Define the variable in the parent
// environment without using a method
// of Environment to avoid cyclic
// test definitions.
parent
.values
.insert(String::from("somevar"), Value::Boolean(true));
// Create a child environment
// connected with the parent.
let mut child = Environment::new_with_parent(parent);
// Define a variable in the child
// environment without using a method
// of Environment to avoid cyclic
// test definitions.
child
.values
.insert(String::from("childvar"), Value::Boolean(false));
let parent = child.restore_parent().unwrap();
assert_eq!(parent.values.get("somevar"), Some(&Value::Boolean(true)));
assert_eq!(parent.values.get("childvar"), None);
}
#[test]
// Test that the method `restore_parent`
// returns None if there is no parent.
fn test_restore_parent_no_parent() {
let environment = Environment::new();
assert!(environment.restore_parent().is_none());
}With this code in place, we can finally apply the strategy we discussed when opening a block, that is to take ownership of the environments hierarchy that will be released when the block ends.
src/statement.rs pub fn execute(
statement: &Statement,
env: &mut Environment,
output: &mut impl FnMut(Value),
) -> EvaluationResult<()> {
match statement {
Statement::Block(v) => {
let mut local_env = Environment::new();
// Create a local environment for this
// block. Assign the given environment
// to it as parent.
let mut local_env = Environment::new_with_parent(std::mem::take(env));
// Link the local environment
// with the parent one.
local_env.add_parent(env);
// Avoid returning early with `?`. The
// parent environment has to be put
// back even if a statement fails.
let result = v
.iter()
.try_for_each(|statement| execute(statement, &mut local_env, output));
for statement in v.iter() {
execute(statement, &mut local_env, output)?;
}
// Restore the parent environment.
*env = local_env
.restore_parent()
.expect("Parent environment not present.");
result?;
}
Statement::Expression(expression) => {
evaluate(expression, env)?;
}
Statement::Print(expression) => output(evaluate(expression, env)?),
Statement::Var(name, expression) => {
let value = evaluate(expression, env)?;
env.define(name.clone(), value);
}
}
Ok(())
}As we mentioned, the strategy around errors changed. Using std::mem::take, we replace the parent environment with the default value of Environment, so we need to make sure the operation is reversed, whatever happens in the rest of the code. So, while we could previously use the ? operator to return early, now we need to use Iterator::try_for_each [docs] to apply the given closure to each item of the iterator and stop at the first error. After that we can restore the parent environment and finally act according to the result of the operation. Please note that when we run local_env.restore_parent we are dropping the local environment.
This code passes all the tests we created for blocks.
Stage 10 - Scopes
This version of the code passes Stage 10 of the extension "Statements & state".
The solution we just implemented works well with the current set of language features, but will prove incorrect as soon as we introduce functions.
Functions are closures, that is entities that can remember the scope where they were created. Robert Nystrom gives us a great example in chapter 10 of his book:
fun makeCounter() {
var i = 0;
fun count() {
i = i + 1;
print i;
}
return count;
}
var counter = makeCounter();
counter(); // 1
counter(); // 2As you can see, the function is somehow linked to the environment that existed at its creation time. If the function count created its own environment, the final print would output 1.
Another example highlights the fact that functions are part of the environment as well:
fun isEven(n) { if (n == 0) return true; return isOdd(n - 1); }
fun isOdd(n) { if (n == 0) return false; return isEven(n - 1); }Both functions are linked to the global environment, so that when we run isEven, the call to isOdd is successful. When isEven was created, isOdd didn't exist.
Both examples make it clear that there is a live connection between the function and the outer environment: the environment cannot be copied into the function when this is defined. Another simple example is that of functions calling themselves recursively.
We could actually extend the book example shown above with two different counters:
fun makeCounter() {
var i = 0;
fun count() {
i = i + 1;
print i;
}
return count;
}
var counter1 = makeCounter();
var counter2 = makeCounter();
counter1(); // 1
counter1(); // 2
counter2(); // 1Here, it is evident that there are two independent versions of the environment inside makeCounter and that each variable counter1 and counter2 is connected to one of them.
This adds two new requirements to environments:
The current code, however, won't be able to satisfy them, as environments have a single owner and they are dropped when the block that defined them ends. We will therefore revisit the system when we implement functions and closures, with a deeper dive into the subtle problems of scoping.