Helping others to help myself

30 May, 2023

The purpose of this post is to make myself feel better about not being able to solve a problem by stating it clearly so it's easier for the good samaritan(s) who respond to my request for help.

Contents:

• What do I want to happen, and why?
• How have I tried to make this happen?
• What did I expect to see?
• What am I seeing instead?
• How have I tried to resolve the issue so far?

What do I want to happen, and why?

What?

• I want to have a struct, called Cell
• This Cell type should know what other cells it's ‘linked’ to

Why?

• In my maze making program, cells make up the building blocks of a maze
• To know whether two cells form a passage, or if a wall separates them, cells need to know if they are linked to one another

How have I tried to make this happen?

Some context

So people know a bit about the other parts of the cell type. I initially declared the type as below, just specifying cell location in the overall maze grid and who its neighbouring cells are:

#[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>>,
}

This compiled, so next step is to check the basic behaviour works. The below code does this by:

• declaring two cells
• setting one cell as a neighbour to the other
• printing the second cell's state

fn main(){
    let mut 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 mut 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);
}

Again, this compiles and prints what I expect - great.

Adding in the ability to have links

Onto the actual issue I’m having, which is extending the Cell type, so that it can keep track of whether it is linked to other cells.

Below is the Ruby implementation for the functionality that I’m trying to emulate in Rust (I’m following along with Jamis Buick’s Mazes for Programmers, where all the examples are in Ruby).

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

def initialize(row, column)
    @row, @column = row, column
    @links = {} # hash attribute for keeping track of linked cells

In attempting to emulate this in Rust I updated the struct declaration with:

• new links field
• where links is a hash map
• and the keys for the hashmap are other cells
• and the values are booleans

So if two cells are linked then they will appear as keys in each other's links field, with the value set to true .

#[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>>,
    links: HashMap<Box<Cell>, bool> //new hash map field for keeping track of linked cells
}

The compiler was happy with this type declaration, so I went on to test the new links functionality. In the code below I added:

• cell_three, a new Cell struct
• an attempt to insert cell_three into cell_two’s links field

fn main(){
    let mut cell_one: Cell = Cell {
        row: 1,
        column: 1,
        north:  None::<Box<Cell>>,
        east: None::<Box<Cell>>,
        south: None::<Box<Cell>>,
        west: None::<Box<Cell>>,
        links: HashMap::new()
    };
    let mut 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>>,
        links: HashMap::new()
    };
    let mut cell_three: Cell = Cell{
        row: 0,
        column: 1,
        north: None::<Box<Cell>>,
        east: None::<Box<Cell>>,
        south: None::<Box<Cell>>,
        west: None::<Box<Cell>>,
        links: HashMap::new()
    };

    cell_two.links.insert(Box::new(cell_three), true);
    println!("{:#?}", cell_two);
}

What did I expect to see?

I expected that cell_three would be moved into the links field as a key, with its value set to true. (I was going to work out how all the ownership worked later, initially I just wanted to do a 'quick test' (quick test outcome: it was not a quick test)).

What am I seeing instead?

Alas, this does not compile and I have the below error:

error[E0599]: the method `insert` exists for struct `HashMap<Box<Cell>, bool>`, but its trait bounds were not satisfied

Some hints from the error message:

 note: the following trait bounds were not satisfied:
            `Box<Cell>: Eq`
            `Box<Cell>: Hash`

How have I tried to resolve the issue so far?

I did some un-disciplined debugging where I can’t recall what I tried or what error messages I received - classic flailing, basically.

I can at least recall the direction the flailing was headed towards / from / through / around:

• Based on the error message hint, I tried adding various traits into the derive annotation above the Cell type. This resulted in playing whack-a-mole with different trait errors, seemingly all the things I needed were mutually exclusive.
• Changing the links from HashMap to a BTreeMap. Pure desperation.
• Passing in references. Purer desperation.
• Looking into lifetime errors I had been getting and reading/playing around with adding explicit lifetime annotations. Purest desperation.

After a few hours I realised that there were clearly multiple, related, fundamental concepts that I was missing, so it’s time to reach out for help. At least I’ve described the problem clearly with this post.