Yep

Maze making in Rust (part 1)

One of my aims while at the Recurse Center (RC) is to write a maze making program, using Jamis Buck’s Mazes for Programmers as my guide. This article summarises my first step in writing the program, that of creating a basic cell type. (Spoiler alert: I do not finish creating a basic cell type).

During this work I’ve been repeatedly taken off-guard by the concepts I’ve had to navigate in order to get even a partial implementation of the cell. The beauty of being at RC is that I’ve been able to take the time to dig into these one by one, rather than moving swiftly on once I’ve got something working.

This post covers the various misunderstandings and clarifications I made along the way about:

  1. Rust’s Option data type
  2. Recursive data types
  3. Indirection
  4. Pointers
  5. Indirection in relation to recursive data types
  6. Finally understanding how these things all fit together
  7. Understanding my misunderstandings
  8. Most recent (but probably not final) iteration of the Cell type

As much as I’ve summarised what I’ve learnt about these topics, I’ve also really dug into the particulars of what I was not understanding. So, for readers more interested in just seeing where I’ve got up to with the code implementation, it might be best to skip to the end of the post.

For those still up for tottering shakily between the above topics, read on!

Rust’s Option data type

The first step in Buck’s approach is to declare a cell type. This will be the building block for the maze. Depending on which algorithm you use, different walls of each cell will disappear or remain, eventually leaving you with a maze. Buck uses Ruby for the book’s code examples, so you get a nice simple declaration like this:

class Cell
	attr_reader :row, :column
	attr_accessor :north, :south, :east, :west

Here’s my naive initial attempt in Rust:

pub struct Cell {
    row: u8,
    column: u8,
    north: Cell,
    east: Cell,
    south: Cell,
    west: Cell
}

For anyone familiar with Rust and/or mazes, reading this code will be accompanied by internal sad trombone sound effects. This is partly because…

On reading the Rust docs I decide that Option is what to use in this scenario:

The Option type encodes the very common scenario in which a value could be something or it could be nothing.

Below is the second iteration, where I wrap Cell in Option. (I’ve also derived from the Debug trait for easy printing of the struct):

#[derive(Debug)]
pub struct Cell {
    row: u8,
    column: u8,
    north: Option<Cell>,
    east: Option<Cell>,
    south: Option<Cell>,
    west: Option<Cell>,
}

That’s the maybe-there-maybe-not-ness covered for neighbours, but alas the sad trombone plays on…

Recursive data types

On reading around this, it seems Rust is not happy with types that could infinitely recurse. Why?

The docs of E0072 have this to say:

When defining a recursive struct or enum, any use of the type being defined from inside the definition must occur behind a pointer (like Box, & or Rc). This is because structs and enums must have a well-defined size, and without the pointer, the size of the type would need to be unbounded.

Yes, those are words and I have read them. Computer words. After reading this, I can add to a few more questions to my initial one of “What on earth is indirection?” :

  1. Why do structs and enums require a well-defined size?
  2. Why do pointers keep the size of the type bounded?

I’ll start with indirection…

Indirection

Broadly, it seems that indirection means “rather than using a thing directly, use something else that references that thing” (at least according to this SO answer) . I’ve come across wrapping as a synonym, and it seemed abstraction was also a candidate for a synonym, until I read this post which gives strong arguments to the contrary.

What I’ve found most helpful in understanding indirection, is considering pointers as an example of indirection in action.

Pointers

For those who haven’t come across pointers before, I’ve found the following analogy useful for understanding them :

The relationship between a pointer and the value it refers to, is like that of a house and its address. The address allows you to locate the house, but it is not the house itself.

Or as one SO answer more tersely put it:

…a pointer is a variable that holds a memory address.

So we can take the initial description of indirection ( “rather than using a thing directly, use something else that references that thing”) and highlight how pointers demonstrate this:

“rather than using a thing (a value at a particular memory address) directly, use something else (a pointer that stores that particular memory address ) that references that thing”

At this point, I’m happy with having answered the first question “What on earth is indirection?”, but as is often the case, it’s raised a follow up question: “How on earth does indirection relate to recursive data types?”…

Indirection and recursive data types

Wikipedia’s entry on indirection points us in the right (ahem) direction:

Recursive data types are usually implemented using indirection, because otherwise if a value of a datatype can contain the entirety of another value of the same datatype, there is no limit to the size a value of this datatype could need.

This rephrased what’s in the rust docs, but I still didn’t really grok the issue, instead it generated a few more questions:

  1. Is the converse true? i.e. When datatypes contain values of different datatypes is a limit imposed on the size a value of the datatype could need?
  2. How does using indirection mean that the size required for a recursive data type becomes limited and/or predictable?

What I’m struggling with is the fact that the actual memory potentially taken up by a recursive type remains the same whether you use indirection or not. Using indirection the memory is still required, it’s just that it’s not directly held in the enclosing datatype as you’re instead holding a reference to the memory address instead - but the memory at that address still has the potential to be used, as does any remaining memory because in theory this datatype could be declared in a way that recurses infinitely (?)

At this point I really feel like I’m missing something about what is happening at compile time with different data types. So, I open up various articles on Rust memory management, what happens at compile time, Box pointers and recursion and so on and so forth. Then, when reading the final article, the pieces came together (not that they weren’t all there from the beginning in the initial error message!) and I wrote down the questions that got me to understanding:

Finally understanding how these things all fit together

With answering “yes” to these three questions I finally understood what was happening during compiling to throw the error I was seeing. From the compiler’s perspective, this is what happens after looking at the Cell struct as it's currently declared:

#[derive(Debug)]
pub struct Cell {
    row: u8,
    column: u8,
    north: Option<Cell>,
    east: Option<Cell>,
    south: Option<Cell>,
    west: Option<Cell>,
}

(Now imagine all of the below is said in the voice of the compiler...)

…and so on

With that perspective, I can see why the compiler would complain. If I was a compiler I too would like to finish compiling and would complain if I couldn’t. This leads to the question of why didn’t I understand the error message when it first appeared?

Understanding my misunderstandings

I’m never fully satisfied with a new understanding if I’m unsure why I didn’t understand it in the first place. So, I’m going to go back over the questions I raised leading up to this point (marked with ‘Q’) and try to provide answers (marked with ‘A’) to my past self.

Q

  1. Why do structs and enums require a well-defined size?
  2. Why do pointers keep the size of the type bounded?

A

  1. So the compiler knows how much memory to allocate to variables of this type
  2. Because a pointer is a known type, the compiler knows how much memory to allocate to it

Those two were fairly straight forward, but from here on we get onto the deeper misunderstandings that I had…

Q

…it seems Rust is not happy with types that could infinitely recurse. Why?

A
The lack of clarity in how I phrased the question indicates part of why I was getting confused. When I wrote ‘not happy with types’, I was not drawing any distinction in my mind between declaring a type in a way that caused infinite recursion at compile time and writing a program that created data structures that infinitely recursed. It’s not that Rust in general is not happy with types that could infinitely recurse (though in some cases I imagine it would complain). This particular error is from the Rust compiler not being happy if you declare a datatype in such a way that the compiler execution infinitely recurses and, therefore, can never finish compiling.

Q

  1. Is the converse true? i.e. When datatypes contain values of different datatypes is a limit imposed on the size a value of the datatype could need?
  2. How does using indirection mean that the size required for a recursive data type becomes limited and/or predictable?

A

  1. Rather than it being about the fact that it’s a different datatype setting a limit on its size, it’s about it being a known and defined datatype e.g. i32. In theory you could declare a struct with a field of a different type, and if that type was recursive and declared without using indirection, it would still fail to compile. So it’s not that difference is what’s required to address the error, it’s boundedness.
  2. Indirection, specifically using pointers, makes the datatype bounded because a pointer has a known size, as the range of possibly memory addresses is known in advance. The compiler can refer to this size and allocate that amount of memory to the variable.

Q

What I’m struggling with is the fact that the actual memory potentially taken up by a recursive type remains the same whether you use indirection or not. Using indirection the memory is still required, it’s just that it’s not directly held in the enclosing datatype as you’re instead holding a reference to the memory address instead - but the memory at that address still has the potential to be used, as does any remaining memory because in theory this datatype could be declared in a way that recurses infinitely.
I feel like I’m missing something …

A
We can see I’m basically saying “Declaring something as a pointer doesn’t stop you from using it in such a way in your program that it could infinitely recurse - so why does this resolve the error?” Again, I’m not really thinking about the distinction between memory allocation during execution and memory allocation at compile time. This error is only regarding memory allocation at compile time, so if it’s resolved at compile time then that’s totally sensible. This doesn’t preclude the possibility that a different error may come up later if you try to write code in a way that causes an infinite recursion. (I have no idea how these cases are handled in Rust, but at this point I am very much ready to move on. I suppose various kinds of stack and heap overflow errors?).

So we’ve just taken a confused and meandering path through recursive data types, Rust’s Option , indirection, pointers and compile time memory allocation. But what about the mazes??? Well, now I actually understand what the error message is saying, we can get round to implementing a fix.

The error message gave various options that could help resolve its complaint : Box, & and Rc (Rust’s error messages are one of the reasons I’m interested in the language - they’re so humane and considerate) .

Based on no investigation whatsoever, I went with Box, changing the declaration to this:

pub struct Cell {
    row: u8,
    column: u8,
    north: Option<Box<Cell>>,
    east: Option<Box<Cell>>,
    south: Option<Box<Cell>>,
    west: Option<Box<Cell>>,
}

Most recent (but probably not final) iteration of the Cell type:

#[derive(Debug)]
pub struct Cell {
    row: u8,
    column: u8,
    north: Option<Box<Cell>>,
    east: Option<Box<Cell>>,
    south: Option<Box<Cell>>,
    west: Option<Box<Cell>>,
}

fn main(){
    let cell_one: Cell = Cell {
        row: 1,
        column: 1,
        north:  None::<Box<Cell>>,
        east: None::<Box<Cell>>,
        south: None::<Box<Cell>>,
        west: None::<Box<Cell>>
    };
    let cell_two: Cell = Cell{
        row: 0,
        column: 0,
        north: Some(Box::new(cell_one)),
        east: None::<Box<Cell>>,
        south: None::<Box<Cell>>,
        west: None::<Box<Cell>>
    };
    println!("{:#?}", cell_two);
}