Satisfying the Rust borrow checker with structs

Question

I'm trying to learn Rust, and as you can imagine, the borrow checker is my biggest adversary. So here's my setup, it's a kind of crate for the game battleship. The game is based on the Battlefield struct, which consists of Cells. A Cell can reference a Ship and a Ship has a vector of all Cells it's referenced by, so it's a bi-directional read-only relationship.

pub struct Battlefield<'a> {
    cells: Vec<Vec<Cell<'a>>>,
}

#[derive(Debug, PartialEq)]
pub struct Cell<'a> {
    ship: Option<&'a Ship<'a>>
}

#[derive(Debug, PartialEq)]
pub struct Ship<'a> {
    length: usize,
    cells: Vec<&'a Cell<'a>>,
}

My problem is Battlefield's place_ship function:

impl<'a> Battlefield<'a> {
    pub fn place_ship(&mut self,
                      ship: &'a mut Ship,
                      x: usize,
                      y: usize,
                      orientation: Orientation)
                      -> PlaceResult {
        // check ship placement in bounds
        // check affected cells are free
        // set cells' ship ref to ship
        // add cell refs to ship's cells field
    }
}

It makes sense to me and I don't think there's an ownership problem here, but I'm wrong it seems:

#[cfg(test)]
mod tests {
    use super::{Battlefield, X, Y};
    use super::Orientation::*;
    use super::super::ship::Ship;

    #[test]
    fn assert_ship_placement_only_in_bounds() {
        let mut ship = Ship::new(3);
        let mut bf = Battlefield::new();

        assert_eq!(Ok(()), bf.place_ship(&mut ship, 0, 0, Horizontal));
        assert_eq!(Ok(()), bf.place_ship(&mut ship, 5, 5, Vertical));
    }
}

src/battlefield.rs:166:47: 166:51 error: cannot borrow `ship` as mutable more than once at a time [E0499]
src/battlefield.rs:166         assert_eq!(Ok(()), bf.place_ship(&mut ship, 5, 5, Vertical));
                                                                 ^~~~
src/battlefield.rs:165:47: 165:51 note: first mutable borrow occurs here
src/battlefield.rs:165         assert_eq!(Ok(()), bf.place_ship(&mut ship, 0, 0, Horizontal));
                                                                 ^~~~

I know this is just a short excerpt, but the whole code is too much to post here. The project can be found here (standard build with 'cargo build').

Answer 1

From the signature of Battlefield::place_ship, the compiler must suppose that the function may store a mutable reference to ship in self (the Battlefield<'a> object). That's because you're linking the lifetime of the ship parameter with the lifetime parameter of Battlefield, and the compiler only looks at the high-level interface of a struct, so that all structs that look the same behave the same (otherwise, adding a field to a struct, even if all fields are private, might be a breaking change!).

If you change the declaration of ship from ship: &'a mut Ship to ship: &mut Ship<'a>, you'll see that the error goes away (if the method's body does nothing with the parameter). However, if you try to store a copy of this pointer in Cell's ship field, this will no longer work, as now the compiler cannot prove that the Ship will live long enough.

You'll keep running into issues with lifetimes, because what you're trying to do will not work with simple references. Right now, there's a contradiction in your definitions of Battlefield, Cell and Ship: you're declaring that Battlefield holds Cells who references Ships that outlive the Battlefield. However, at the same time, you're declaring that Ship references Cells that outlive the Ship. The only way this will work is if you declare the Battlefield and the Ships on the same let statement (as the compiler will assign the same lifetime to all values).

let (mut ship, mut bf) = (Ship::new(3), Battlefield::new());

You'll also need to change &mut self to &'a mut self to assign a Cell from self to a Ship. But then as soon as you call place_ship, you'll effectively end up locking the Battlefield, as the compiler will suppose that the Battlefield may store a mutable reference to itself (which it can because it takes a mutable reference to itself as a parameter!).

A better approach would be to use reference counting instead of simple references combined with interior mutability instead of explicit mutability. Reference counting means that you won't have to deal with lifetimes (though here's you'd have to break cycles with weak pointers in order to avoid memory leaks). Interior mutability means that you can pass immutable references instead of mutable references; this will avoid cannot borrow x as mutable more than once compiler errors since there will be no mutable borrows at all.