Maze making in Rust (part 2)

26 May, 2023

Welcome to the second instalment of my journey into maze making in Rust.

At the end of the first instalment, I triumphed over declaring recursive data types, learnt a lot about indirection and clarified my mental model for compile time vs run time errors. However, I was also unable to print one of the cells that I’d declared, with Rust complaining about ownership.

So, that’s today’s job:

Understanding why the code won’t compile
Fixing it
Running it so I can print both cells.

We'll get to these (mostly)* through the below steps

Outlining the problem
Analysing the borrow error
First attempt at resolving the error
Successful attempt at resolving the error
Ownership Post Script

*I say mostly because my "understanding why the code won't compile" turns out to be very very partial.

Outlining the problem

Problematic code:

#[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_one);
    println!("{:#?}", cell_two);
}

On calling rustc src/cell.rs I get the below error:

 error[E0382]: borrow of moved value: `cell_one`

On commenting out the first print macro, everything compiles and prints fine.

I’ve never had to think about ownership, borrowing or manage memory before, so I was expecting to make this kind of mistake pretty early on. Time to dive into the error message.

Analysing the borrow error

Let’s break down the full error message and try to unpick it:

error[E0382]: borrow of moved value: `cell_one`
  --> src/cell.rs:28:23
   |
12 |     let cell_one: Cell = Cell {
   |         -------- move occurs because `cell_one` has type `Cell`, which does not implement the `Copy` trait
...
23 |         north: Some(Box::new(cell_one)),
   |                              -------- value moved here
...
28 |     println!("{:#?}", cell_one);
   |                       ^^^^^^^^ value borrowed here after move
   |

At this point, I think I am kind of in the clear in terms of the seriousness of the issue.

When I first saw this I feared it was rooted in how the cell types were relating to one other on a fundamental level - I thought maybe <Box> was not the correct type of indirection to use for my maze, and that I’d have to dive into <Box> ,Rc, Cell, RefCell and so on.

This may still be true, but that’s not really what the error message is complaining about.

On reading the error properly, it’s more concerned with me using cell_one in my print statement, when ownership of cell_one has been passed into cell_two, specifically cell_two ’s north field.

At least, that’s my hypothesis.

First attempt at resolving the error

How can I resolve this? What if, instead of trying to pass cell_one directly into the print, I pass a reference to cell_one ? In Rust you can use the & to declare that you only want to reference a value, and that you don’t want to take ownership of it.

So I updated this:
println!(“{:#?}”, cell_one);
To this:
println!(“{:#?}”, &cell_one);

And I run rustc src/cell.rs again.
And I get exactly the same error message again.
Boo.

Ok so, clearly, it doesn’t matter that I’m just using a reference to it, you can only do that before a value has changed ownership.

Successful attempt at resolving the error

Maybe I can try accessing it via what I know currently owns it, cell_two.
Lets go from this:
println!(“{:#?}”, &cell_one);
To this:
println!(“{:#?}”, cell_two.north);

E0382 has been banished!
Instead, we’re left with a very reasonable warning from the compiler about unread fields:

warning: fields `row`, `column`, `east`, `south` and `west` are never read
 --> src/cell.rs:3:5
  |
2 | pub struct Cell {
  |            ---- fields in this struct
3 |     row: u8,
  |     ^^^
4 |     column: u8,
  |     ^^^^^^
5 |     north: Option<Box<Cell>>,
6 |     east: Option<Box<Cell>>,
  |     ^^^^
7 |     south: Option<Box<Cell>>,
  |     ^^^^^
8 |     west: Option<Box<Cell>>,
  |     ^^^^
  |

Now we’ve successfully compiled it, let’s run the code again and gaze upon the glory of our labours:

$ ./cell
Some(
    Cell {
        row: 1,
        column: 1,
        north: None,
        east: None,
        south: None,
        west: None,
    },
)
Cell {
    row: 0,
    column: 0,
    north: Some(
        Cell {
            row: 1,
            column: 1,
            north: None,
            east: None,
            south: None,
            west: None,
        },
    ),
    east: None,
    south: None,
    west: None,
}

Blinding.
And in doing this I have realised I had visibility on cell_one all along because I was able to see it as a field inside cell_two 🙈

At this point I’ve done the main thing I set out to achieve, which was fixing the error and getting visibility on both the cells I’d created. As I said earlier, I may still face issues based on my uninformed choice of using <Box>, but I’ll kick that can down the road for now.

Next step is to implement fields and methods for linking and unlinking cells…

Ownership Post Script

When I said this:

Ok so, clearly, it doesn’t matter that I’m just using a reference to it, you can only do that before a value has changed ownership.

I wasn’t totally confident of my understanding of why using a reference didn’t work. Was it really because you can only do that before a value has changed ownership? I wasn’t sure.

In the interests of thoroughness I’m going to circle back to that and check I properly understand why having println!(“{:#?}”, &cell_one); didn’t compile.

To expand on my initial description, I don’t think this worked because:

By the time I tried to pass a reference to cell_one to the print macro (i.e. println!(“{:#?}”, &cell_one) ), cell_one had already been declared as the value for a field in cell_two
Therefore the ownership of cell_one has been transferred to cell_two
So when I was calling &cell_one it was pointless - you can’t make a reference to a value that no longer exists (this is a hand-wavy description , but hopefully it makes sense)

Is there a way I can prove or disprove this hypothesis? Yes:

Move (“{:#?}”, &cell_one) to before cell_one ’s ownership has been transferred to cell_two
Expect to see that the code compiles

Before (not working):

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_one \n {:#?}", &cell_one); // <- move this up...
    println!(" cell_two \n {:#?}", cell_two);
}

After (hopefully working):

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>>
    };
    println!(" cell_one \n {:#?}", &cell_one); // <- ...so it makes a cell_one reference before its ownership is transferred to cell_two
    
     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 \n {:#?}", cell_two);
}

Does this compile without errors? Yes!

So that’s a partial confirmation of my understanding for why the use of a reference didn’t work.

Is there a further way I can prove or disprove this hypothesis?

Yes:

Replace println!(“{:#?}”, &cell_one) with println!(“{:#?}”, cell_one)
Expect to see that the code does not compile

I expect it to not compile because:

Calling println!(“{:#?}”, cell_one) should pass the ownership of cell_one to println!()
Then cell_two tries to use cell_one for its north field …
… it cannot, because it does not own it

To test this hypothesis we go from this:

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>>
    };
    println!(" cell_one \n {:#?}", &cell_one); // <- reference, &cell_one
    
     let cell_two: Cell = Cell{
        row: 0,
        column: 0,
        north: Some(Box::new(cell_one)), // <- use directly, cell_one
        east: None::<Box<Cell>>,
        south: None::<Box<Cell>>,
        west: None::<Box<Cell>>
    };

    println!(" cell_two \n {:#?}", cell_two);
}

To this:

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>>
    };
    println!(" cell_one \n {:#?}", cell_one); // <- use directly, transferring ownership of cell_one to println!() ?
    
     let cell_two: Cell = Cell{
        row: 0,
        column: 0,
        north: Some(Box::new(cell_one)), // <- meaning it's unavailable here?
        east: None::<Box<Cell>>,
        south: None::<Box<Cell>>,
        west: None::<Box<Cell>>
    };

    println!(" cell_two \n {:#?}", cell_two);
}

Let’s see if I’m right…

I’m not right.

It compiles.

Gah.

I suppose having gaps in my understanding of ownership is unsurprising given this is my first practical use of it. I'll park this for the time being and take it to the helpful folks at Rust ’n’ Rainbows next week.

Post Post Script

Is Box::new playing a part in this unexpected behaviour?