Downcasting and borrowing Rc<RefCell<Trait>>

help
1

Hi all - I'm learning Rust at the moment by implementing the PragProg book Mazes for Programmers as an exercise. However, I'm running into some trouble refactoring some of my rust code into the more OO style that the book is written in - in the book, we start with a general "grid" class which contains "cells". Over time, the author adds in some inherited classes for both of these that I'm having trouble getting to work correctly through the trait system.

My current code base (https://github.com/rbudnar/rust-mazes/) appears to work well enough (although it's likely not rust-idiomatic). I'm attempting to refactor my "cell" struct to be behind a trait so that I can implement different kinds of cells (right now it's a square cell with N/S/E/W, I'm attempting to add polar cells at the moment). The current cell implementation is here: https://github.com/rbudnar/rust-mazes/blob/master/crate/src/grid/cell.rs

My problem lies in being able to link cells together after refactoring to a trait. I've defined a trait that looks like this:

pub type ICellStrong = Rc<RefCell<ICell>>;
pub type CellLinkWeak = Weak<RefCell<Cell>>; 
pub type CellLinkStrong = Rc<RefCell<Cell>>;

pub trait ICell {
    fn neighbors(&self) -> Vec<ICellStrong>;
    fn links(&self) -> Vec<Option<ICellStrong>>;
    fn link(&mut self, other: ICellStrong, bidir: bool); // <-- this method is causing problems with alreadyBorrowed errors
    fn as_any(&self) -> &dyn Any;
...
}

I've tried a number of variations of the link method, all which look something similar to this:

fn link(&mut self, other: ICellStrong, bidir: bool) {
        let _self: CellLinkStrong = self.self_rc.upgrade().unwrap();
        
        if let Some(nl) = other.borrow().as_any().downcast_ref::<Cell>() {
            let new_link = Rc::clone(&other);
            self.links2.push(Some(new_link));
        }

        if bidir {
            let _other: ICellStrong = self.self_rc.upgrade().unwrap() as ICellStrong;
            other.borrow_mut().link(Rc::clone(&_other), false);
        }
    }

// ... in the maze generation algorithm code:
 MazeAlgorithm for RecursiveBacktracker {
    fn on(&self, grid: &dyn Grid, rng_generator: &dyn RngWrapper) {
...
     let rand_neighbor = rand_element(&unvisited, rng_generator);
     current.borrow_mut().link(Rc::clone(rand_neighbor), true); // <--- I believe this borrow is causing issues 
}

Though the code does compile, running the above code winds up panicking with an already mutably borrowed: BorrowError. My attempts to resolve this have basically just pushed the error to different places.

What happens, in short, is this:

  1. the algorithm grabs one cell, looks through its neighbors, and eventually picks a neighbor to link to.
  2. I mutably borrow the current cell and call the link method
  3. the current cell pushes a link to the other cell and calls the link method on the other cell to provide a two way link.
  4. when the second cell is being linked, the code throws the already borrowed error, since the algorithm has already borrowed the current cell to initiate the link process.

I found a few insightful gems here and here, but I haven't been able to complete the second linking call successfully.

... Aaaand of course, as luck would have it - as I was typing this, I finally came up with something that doesn't panic. Silly me - in my algorithm, no one said I have to recursively link the cells (that's just what the book does). I've split the link calls out so that I'm not borrowing on top of a borrowed ref, like this:

// maze algorithm code
    current.borrow_mut().link(Rc::clone(rand_neighbor), true);
    rand_neighbor.borrow_mut().link(Rc::clone(&current), true);
//

// cell code for linking
fn link(&mut self, other: ICellStrong) {
        let _self: CellLinkStrong = self.self_rc.upgrade().unwrap();
        
        if let Some(nl) = other.borrow().as_any().downcast_ref::<Cell>() {
            let _other: CellLinkWeak = Rc::downgrade(&Rc::clone(&nl.self_rc.upgrade().unwrap()));
            self.links.push(Some(_other));
        }
    }

Of course, I did all that typing so I don't want to waste it. So I guess my question now would be - is there a better way to achieve what I'm doing, overall? In terms of the abstraction of the cell into a trait and allowing for polymorphic access to the cells by the various grid algorithms, that is (each algorithm does need some small slice of access to each kind of cell for manipulation purposes). I feel like I'm trying to force the OO paradigm on this and I might be giving myself more headaches than needed.

Oh and since I'm here... is there a common naming convention for traits? Interfaces in other languages are generally prepended with an I, as in ICell that I've done here.
Any other feedback for my learning purposes is highly appreciated (either on the above, or from the repo)!

2

I would strongly suggest you don't try to do OO in Rust, it was not designed with OO in mind, and the Rust borrow checker will fight you every step of the way. Instead use an OO language to do OO, and learn how to do things in Rust without using OO.

For example, instead of storing your cells like you did, you could store them like so.

Assuming you don't remove any cells:

struct Cell {
    neighbors: Vec<usize>, // store indicies into the Vec in Grid
}
struct Grid {
    cells: Vec<Cell>,
}

impl Grid {
    // because of how cells are stored, this method becomes trivial to write.
    fn link(&mut self, cell_a: usize, cell_b: usize) -> bool {
        if cell_b < self.cells.len() {
            if let Some(cell_a) = self.cells.get_mut(cell_a) {
                cell_a.neighbors.push(cell_b);
                return true; // the link was successful
            }
        }
        false // link failed
    }
}

If you do need to remove cells, the I will direct you to the generational-arena crate, which will allow you to efficiently add and remove cells without invalidating existing indices.

3

Can the same Grid actually contain both kinds of Cell?

4

I don't see why not, you could use either another vec or an enum to pick which cell you are storing.

5

That's an interesting idea, I think I'll give that a shot! I was basically translating the ruby implementation into rust and it was working well enough so I didn't give it much thought until I started getting to the parts where methods were getting overridden. I don't think I'll be removing cells. I do have to mask (basically, not add particular cells) them for generating mazes in a particular shape, but a mask is generated and THEN the grid is generated based on that.

I don't know that it makes sense to have all types of cell in each grid. The grid preparation methods change based on the cell type (polar/square/hexagonal cells all have differing neighbors), so I need different methods for each cell type and grid type (right now there's a grid trait and will be a different impl for each cell type).

6

Right, so what I was thinking of when I asked that question was something like this:

trait Cell {
    // stuff to do with a single cell
}

struct SquareCell {}
impl Cell for SquareCell {}

impl HexCell {}
impl Cell for HexCell {}

struct Grid<C> {
    cells: Vec<C>
}

impl<C: Cell> Grid<C> {
    fn new() -> Self {
        // use Cell methods to create the right kind of grid
    }
}

I.e., parameterize Grid on the type of cell it accepts so you don't have to dispatch on the cell type every time you go from grid to cell. But it really depends on what kind of operations you support.

I also agree that Vecs and indices make a lot of graph-y problems much more tractable :slight_smile:

7

I was just thinking about making the Grid generic instead of a trait, that also might be better. I'm not sure how I'd have different grid setup methods with that approach, but that sounds like an interesting idea.