Greetings, my student. It has been a long time, longer than we would like.
We have been caught up in great battles of wizards in faraway lands… to cavort with witches and the deer of Eastnor and witness lightning dance in the air, and thence to the land of the Finns, a great Assembly where some of the mightiest sorcerers of our art compete to show who best commands the thunder of Ukko.
But now we return… and today’s secrets might be some of the most important.
- riddles past
- memory
- a quick primer on memory in Rust
- values and references
- two other types of language
- ownership and borrowing
- the borrow checker
- fourth orb to ponder
riddles past
First, though, shall we have a quick look at the orbs?
The second orb
In part 2, we were learning about names and scopes; I posed a program, and asked you to figure out what it says. The answer is XYZZY, a magic word of fine vintage. How does it work?
The second orb
Here’s the program:
fn main() {
let spell = "Y";
{
let spell = "X";
print!("{}", spell);
}
{
print!("{}", spell);
let spell = "Z";
print!("{}{}", spell, spell);
}
print!("{}", spell);
}
On the first line we store "Y" behind the name spell in the outer scope.
We enter the inner scope, and assign "X" to spell, which shadows the spell of the outer scope. Then we print. The most recent definition of spell available in this scope contains "X", so we print X.
We exit this scope. The inner assignment of spell is dropped, falling away to reveal the spell outside.
We enter a new scope. Now when we print spell, there are no assignments in this scope, but there’s one in the next scope up, which has "Y" behind it. So we’re at ‘XY’.
Now we assign "Z" to the name spell, once again shadowing the outer spell. The print here prints it twice, so we are at ‘XYZZ’.
We exit the scope, and the assignment falls away, once again leaving spell as Y. We print this Y, and we get XYZZY.
That is logically what’s going on. But does the compiler actually do all of this? Let’s drop it into Compiler Explorer and find out. I kind of expected it to be able to see that the program just stores the whole string XYZZY somewhere, but no, it doesn’t seem to be able to simply optimise that away. In fact it produces four separate calls to the print function. Either this machinery is just too opaque or there is some reason the compiler can’t safely make this optimisation.
The third orb
In the third orb, I suggested you could write a program which draws an expanding box by clearing the screen and waiting. Here’s one such program:
fn print_room(width: u32, height: u32) {
print_horizontal_wall(width);
for _ in 0..height {
print!("#");
for _ in 0..width {
print!(".");
}
println!("#");
}
print_horizontal_wall(width);
}
fn print_horizontal_wall(width: u32) {
for _ in 0..width + 2 {
print!("#")
}
//print a newline to end the row
println!();
}
fn clear_console() {
print!("{esc}c", esc = 27 as char);
}
fn main() {
for tick in 0..60 {
clear_console();
print_room(tick, 10);
std::thread::sleep(std::time::Duration::from_millis(1000 / 60));
}
}
Each time around, the loop clears away all the current text in the console, prints a slightly bigger room, and then tells the operating system that it’s done with its work for now but please could it be woken up in 1/60 seconds.
Previously our computations were pretty abstract, all we cared to see was the final answer… but here we’re placing our program in the world, and worrying about how much time things take. (Can we be sure that the operating system, which is juggling this and hundreds of other programs, will give us a consistent framerate?) Time will be immensely important later when we do more graphics stuff. But we won’t worry about that yet.
No, there is another part of the temple we need to build in our minds at this point… something we’ve been dancing around a little in the story so far.
It’s almost time to introduce arrays, structs and other ways to make more complicated types. But first, it’s time to talk about memory.
memory
So computers have ‘memory’. You probably know already that this stores all the things the computer is actively doing. If you don’t have enough RAM, your computer can run out and slow down or crash. Better download some more… And of course it’s too damn expensive these days. But from the perspective of a programmer, by which of course we mean a sorcerer schooled in the Arts, what is memory?
Let’s start as simple as we can and build up.
a peek down a level
Memory is how your computer holds on to calculations so it can use the results later.
Although I usually try to say on the Rust level of abstraction, I think it’s quite helpful to know what memory looks like to the CPU. From a program’s point of view, we can think of it as a huuuuuuuuuuuuuuuuuuuuuuuuuge long list of bytes. Every single one of those bytes has an “address”, which is basically just a number.
It might be something like this:
address: 00 01 02 03 04 05 06 07 08 09 0A 0B 0C 0D
data: 01001101 01100001 01100111 01110011 00100000 01101001 01110011 00100000 01100011 01110101 01110100 01100101 00100001 00100001
So the address numbers just go up, and each number points to a specific byte. The CPU runs instructions like ‘get me the byte at 0x0B’ or ‘put this value in 0x03’.
In this little example, memory addresses are only one byte, which means that the computer could only hold a maximum of 256 bytes of memory. Most modern computers are ‘64-bit’, which means they use eight bytes to represent a memory address, for example 0xCAFEBABEDEADBEEF or 0xBAAAAAAAAAAAAAAD. The type of number used for memory addresses has the special type usize in Rust; on a 64-bit computer that’s equivalent to a u64, on a 32-bit computer it’s a u32, and so on.
However…
For logical purposes, it doesn’t really matter what form a memory address takes. All we need to know is that we can put things down and keep an address to look them up again later.
Now, I’m leaving out a lot of details here. For one thing, we also have tiny bits of memory inside the CPU called ‘registers’ and ‘caches’. And there are many fiddly details: virtual memory, address spaces, cache lines, alignment, etc. etc.; perhaps we will come back to these things later.
All of that is implementation details, though. Important when you want to write fast code… but logically, all you need to know is that you can put things in memory and look them up with addresses. So let’s try to understand the abstraction that all that stuff is working to create.
a quick primer on memory in Rust
Goodness, are we going to have to go around writing out all our 0xDEADBEEF values by hand? Fortunately not; in modern programming languages, all of that is tucked away out of sight.
In Rust, there are two areas of memory. They’re called the stack and the heap. If you’re, hypothetically speaking, a Netrunner player, these words might ring a bell… and unfortunately they will give you the wrong intuition, sorry :p
the stack
So far we’ve mostly been messing with the stack. When we write something like…
fn main() {
let homura: u8 = 0x68; //ASCII 'h'
}
…in principle, Rust will pick some little bit of memory to store that value. The place where let bindings go is called the stack.
Under the hood, it works in a very simple way: the stack is just all the different values we’ve named, concatenated one after the other in the order we assigned them, in a specially set aside space of memory.
You don’t really need to know more than that, but just for fun, let’s have a look at how the stack actually works. It goes like this:
- the program stores the memory address of the end of the stack (which we call the ‘stack pointer’, since it points to the end of the stack)
- whenever you create a new variable, it gets stuck on the end of the stack, and the program moves the ‘end of the stack’ address to a lower memory address
- when you exit a scope, everything in that scope gets removed from the stack, and the ‘end of stack’ address jumps back up
So, let’s say the stack is something like this…
06 ????????
07 ????????
08 ????????
09 ???????? <- STACK POINTER (new stuff goes here)
0A 01101001 <- some variable
0B 00100001
And we want to store a new value like let homura: u8 = 0x68. The u8 type has the size one byte. So we move the stack pointer down a byte, and fill in the value. 0x68 is 01000100 in binary. The result is…
07 ????????
08 ???????? <- STACK POINTER (new stuff goes here)
09 01000100 <- foo (least significant byte)
0A 01101001 <- some other variable
0B 00100001
Now homura has moved into the address 0x09. She’ll be starting school soon, wonder if she’ll meet anyone cool…
The compiler knows that if, later on, we ask for the value of homura, it can read it from 0x09. That’s the basic idea! It’s pretty simple. The stack gets longer and longer as we define more variables. If we define too many variables and the stack runs out of memory, it’s called a ‘stack overflow’ and the program crashes. But usually, there’s loads of space and the only time a stack overflow happens is heavy recursion.
the heap
Although the stack is super nice, super simple and super easy to understand, it’s got some limitations. In particular, everything on the stack must have a fixed size that never ever changes. And there’s a very strict order in which things must be created or destroyed—you can’t really just delete something from the middle of the stack and use that space for something else. It can also be troublesome with very large blocks of data.
There is another place to put things in Rust known as the ‘heap’. This is basically all the memory that isn’t the stack.
Some operations will allocate stuff on the heap, which basically means invoking machinery which says ‘hey, give me some memory of this size’; a piece of the heap will be duly carved out.
There are lots of different types in the Rust standard library which use the heap, such as Box, Rc, Vec and String. We’ll meet some of them later in this series. For now, though, we won’t complicate things too much; let’s stick with stack-allocated values, there will be plenty to think about!
values and references
OK, we know that variables live in memory, and much like fossil fuel CEOs, they have names and addresses. But what can we do with that?
Like lots of languages, Rust can have types which point to other types. In Rust, the main type that does this is known as a reference. If foo is something, then &foo is a reference to foo.
It’s kind of like this. A regular variable just has a name point directly to a value…
name -----> value
But for a reference, the value is itself something which points to a value, so it’s more like this…
name -----> reference -----> value
To get at the value behind the reference, you can dereference it with the * operator, not to be confused with multiplication…
fn main() {
//the latitude, if you're wondering
let jeff_bezos_house: f32 = 34.086111;
//behind this name is a reference to the number
let address = &jeff_bezos_house;
//this makes a copy of the number and stores it in 'found_him'.
let found_him = *address;
}
Just like regular variables, references can be mutable or immutable. You write a mutable reference with &mut:
fn main() {
//mutable because jeff bezos is not immortal
let mut jeff_bezos_alive = true;
println!("Is Jeff alive? {jeff_bezos_alive}");
let target = &mut jeff_bezos_alive;
//we have an address again, but this time we can do things
//to the value on the other side!
//dereference the address and assign a value through it
*target = false;
//prints false; the original value has been
//modified through the reference!
println!("Is Jeff alive now?? {jeff_bezos_alive}");
}
Now, whyever would you want something like that?
The basic and universal answer is that, in a complex program, it may be useful to have multiple names in the program which at least soemtimes refer to the same thing. You can build complicated structures of things pointing to other things.
But more specifically, for Rust, the reason has to do with its ‘ownership’ model. Strap in.
two other types of language
In older languages such as C, you told the compiler exactly when to delete something from memory (aka ‘freeing’ it).
But this could be a problem: let’s say another part of the program has some reference (in C, this would be called a ‘pointer’; the difference isn’t that important) to the thing you just deleted. Before you deleted the thing, all would be well: the reference points to the thing you’d expect. But after you deleted it, it’s not there anymore! The program could put some entirely different thing in that memory address.
This is known as a ‘use after free’ bug, and hackers love to find them, because you can use it to start poking around in places you’re not supposed to, or change bits of the program state. Great way to take control!
‘Garbage collected’ languages work differently. The program has some additional machinery called a ‘runtime’, which keeps track of how many references exist to everything in the program. Every so often, the program stops for a moment, and a special piece of machinery called the ‘garbage collector’ goes around and checks if anything has zero references and deletes it… and then, checks again because maybe the thing that just got deleted was holding a reference to another thing, and so on. This means you can never have a ‘use after free’, because nothing will be freed while it’s still used.
Garbage collectors are very clever creations, and a great deal of research has gone into making them work as well as they do. But they do incur an overhead which makes your program have to do a bunch of extra work all the time, and when performance is very important (e.g. in a game) they can cause unpredictable hitches which you generally do not want. Plus, someone has to actually implement the garbage collector, which means using a language that isn’t garbage-collected.
ownership and borrowing
Rust was invented to have a secret third option. You don’t manually manage memory (unless you go into unsafe Rust, but we won’t be doing that for a while!), but you also don’t need to have a garbage collector. How can that work?
So, remember how we said that names live in scopes, and when a name goes out of scope it disappears?
fn main() {
//here is a scope...
{
let bar = 2;
println!("Bar is fine to print here: {bar}");
}
println!("But printing {bar} here will give a compiler error.");
//this won't compile!
}
That’s basically the whole trick. The confusing jargon term for this system, which comes from C++, is RAII (standing for Resource Acquisition Is Initialisation). When you leave a scope and invalidate a name, the memory assigned to store that value also gets freed.
A particular consequence of this is that, without references or copying, functions ‘eat’ their arguments.
functions eat things
I can’t actually demonstrate this with numbers or string slices since they are what are called Copy types, so lets quickly introduce another type. We can declare a new type like this, using the struct keyword:
struct Edible;
Once this is written in your program, the world of Rust just got slightly bigger: there are now Edibles in it. Yum. (Like function declarations, it doesn’t matter where in the file you put this declaration, as long as it’s outside any scopes.)
We’ll go way more into the subject of creating new types very soon, but for now, Edible is a ‘unit type’, which means you can create a new Edible just by writing Edible:
struct Edible;
fn main() {
let tasty_thing = Edible;
}
The rule is this: there can only be one name which authoritatively owns the value.
So, if we assign the value of tasty_thing to another variable, Rust will move the value of the Edible to that new name, and the old name will be invalidated.
fn main() {
let your_tasty_thing = Edible;
//moves the value to the new name
let my_tasty_thing = your_tasty_thing;
//this will fail because the value has already been moved!
let someone_elses_tasty_thing = your_tasty_thing;
}
If you try to compile this, the compiler will tell you that you’re using something after it’s been moved. (It will also suggest a way to fix this, but don’t worry about that for now.)
This ‘move’ is only an abstract, logical thing. The compiler will not necessarily actually move the data someplace else in memory (though it might!). It just changes the name for the value.
The main reason this matters is that the same thing applies to function arguments. If we write a function which takes Edibles as input ‘by value’…
fn eat(food: Edible) {
println!("Omnomnomnomnom");
//doesn't matter what we do here
}
then, if we call this function, the argument gets moved into the function scope and dropped at the end.
fn main() {
let your_cake = Edible;
eat(your_cake);
//fails because your_cake has been moved!
let cake_you_have = your_cake;
}
To be clear, these rules don’t apply to anything that is Copy, which mostly includes simple things like numbers, but also includes references. If something is Copy, you can have it and eat it just fine. I’ll save further discussion of what it means to ‘be Copy’ for later, when we talk about another feature called ‘traits’.
immutable references let you look without touching
OK, but what if we want to pass something to a function without eating it? This can be done by making the argument be a reference instead!
//this function takes a reference to an Edible, not an Edible
fn examine(food: &Edible) {
println!("I'll give it back, don't worry!");
}
fn main() {
let your_cake = Edible;
examine(&your_cake);//only a reference gets eaten
let cake_you_have = your_cake; //works just fine
}
mutable references are side effects
We can also use mutable references to allow functions to modify things outside of their scope. For example, in an RPG you might have something like this…
fn inflict_damage(health: &mut i32, damage: i32) {
println!("You get hit for {damage} damage. Ouch!")
*health = *health - damage;
}
fn main() {
let mut your_health = 1000;
println!("You have {your_health} health."); //1000
inflict_damage(&mut your_health, 100);
println!("You have {your_health} health."); //900
}
By feeding functions mutable references, we can give them side effects! (Functional programmers in the audience are tutting and shaking their heads.)
the borrow checker
Although we can borrow values, there are some restrictions. These mostly exist in order to prevent certain types of bugs in multi-threaded programming, where two parts of the program are trying to interact with the same piece of memory at the same time. Rust is designed to make this easy as possible, and it can only do this with certain restrictions baked into the language.
Even though we won’t be doing multithreading for a while, it’s important to explain them here, so you don’t get caught by surprise!
The very important rule is this…
at any time, there can be either:
- any number of immutable references
or
- only one mutable reference
to the same value, never both.
The Rust compiler is generally pretty smart these days: if you create a mutable reference, it will invalidate any immutable references you might have created, and vice versa. So doing this is actually fine…
fn main() {
//needs to be mutable or we can't create mutable references
let mut house = 10;
//fine, there are no references
let ref_1 = &house;
//fine, there are only immutable references
let ref_2 = &house;
//fine since we can drop all immutable references
let mutable_ref = &mut house;
//fine since we can drop the mutable reference
let ref_3 = &house;
}
But if you refer to an immutable reference you created earlier, then we have trouble!
fn main() {
//needs to be mutable or we can't create mutable references
let mut house = 10;
//fine, there are no references
let immutable_ref = &house;
//not allowed!! since the immutable ref is still in use
let mutable_ref = &mut house;
//this line means we can't drop immutable_ref
let mouse = *immutable_ref;
}
If you try to compile this, the compiler will give you a nice colourful explanation of the problem. I can’t reproduce the colours on here but here’s what it looks like
error[E0502]: cannot borrow `house` as mutable because it is also borrowed as immutable
--> src/main.rs:44:23
|
5 | let immutable_ref = &house;
| ------ immutable borrow occurs here
...
8 | let mutable_ref = &mut house;
| ^^^^^^^^^^ mutable borrow occurs here
...
11 | let mouse = *immutable_ref;
| -------------- immutable borrow later used here
In the old days of Rust, the compiler wasn’t nearly so clever about this, and people would complain about having to ‘fight the borrow checker’ all the time. But now this kind of problem comes up only rarely. In the course of making Shaderland there was maybe only one time when I felt I had to do anything annoying to keep the borrow checker happy.
shaking it all about
Note that there is one other way for functions not to permanently eat stuff: if they have a return value, that pops back out into the enclosing scope and doesn’t get deleted. Which we can fold into our metaphor, and I’m very sorry for this…
fn eat_and_shit_out(food: Edible) -> Edible {
food
}
fn main() {
let tasty_thing = Edible;
let bezoar = eat_and_shit_out(tasty_thing);
//the value has now moved into bezoar, unchanged
}
You can also return references, if you want to.
fn inspect(thing: &Edible) -> &Edible {
thing
}
lifetimes
This is an advanced topic and one we’ll cover in much more detail later on.
All that stuff above about how Rust prevents use-after-free and so on? Only works if the references can be proven not to stick around after the thing they’re referring to. The way Rust does this is… I mean I know I’ve been doing a bit of a silly occultism theme through all this but this is maybe the most magical thing going on here.
Essentially, everything in Rust has a ‘lifetime’. This is a slightly nebulous thing but it’s basically a way of keeping track of which order you can delete things.
We write lifetimes with an apostrophe like 'l, and you most often see them on references: &'l Thing is a reference to a Thing and that reference has lifetime 'l. (If you don’t write the lifetime, Rust will still be figuring it out behind the scenes; this is an implicit lifetime.)
Lifetimes relate to other lifetimes; indeed, they don’t do very much else. Saying 'l1: 'l2 means that lifetime 'l1 cannot live longer than 'l2. Which is to say, everything with lifetime 'l1 must be deleted before anything of 'l2 gets deleted. If the compiler can’t prove this is true on a type level, then the program won’t compile.
Why bring this up now? Occasionally, usually when you’re passing references around, Rust will require you to declare explicitly which lifetime is being used. We’ll see an example of this in the Orb.
fourth orb to ponder
We have just finished drawing one of the most important magic circles in our ritual! However, it will be hard to get an intuition for this until you start using it. And to do that, there are still a few more runes we need to draw.
Still, we can always make a horribly perverse maze. (Seriously, this feels mean, nobody should write Rust like this.) Watch out for the shadows!
//we'll learn more about enums next time
//but the short version is this lets you say a type can be one of a fixed list of things
#[derive(Debug)]
enum Room {
Treasure,
Doom,
}
//always goes to the room on the left
//note that we need to make the lifetime explicit here!
fn left<'a>(l: &'a Room, _r: &'a Room) -> &'a Room {
l
}
//always goes to the room on the right
fn right<'a>(_l: &'a Room, r: &'a Room) -> &'a Room {
r
}
//a silly rusty maze
//one reference leads to treasure, the other to certain doom
fn main() {
let amazing_wizard_orb = Room::Treasure;
let doom = Room::Doom;
let (l, r) = {
let a = left(&amazing_wizard_orb, &doom);
let b = right(&amazing_wizard_orb, &doom);
let c = left(b, a);
//a shadow attacks!
let b = left(c, a);
let d = right(c, b);
//a shadow attacks!
let b = right(b, a);
let e = left(b, d);
//a shadow attacks!
let d = right(b, c);
let f = left(d, e);
let g = right(c, f);
//a shadow attacks!
let f = right(c, b);
let h = left(f, g);
let i = right(g, h);
let j = left(g, i);
//a shadow attacks!
let h = right(i,j);
let k = left(i,f);
let l = left(k,h);
let r = right(k,h);
(l, r)
};
//uncomment this line to take the left path
//println!("I took the left path, and found my way to {l:?}");
//uncomment this line to take the right path
//println!("I took the right path, and found my way to {r:?}");
}
Can you figure out which path to take to get through the maze?
Next time, we’ll look at this ‘defining new types’ business, and finally get to arrays!
Comments