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').

but the whole code is too much to post here — I guarantee that you can make the code small enough to post here while still reproducing the same error. See minimal reproducible example. — Shepmaster
Probably a duplicate of stackoverflow.com/q/32300132/155423; maybe stackoverflow.com/q/20698384/155423 or stackoverflow.com/q/28833622/155423 or stackoverflow.com/q/29893978/155423. Or any question about mutable aliasing. Like the error says, you cannot borrow anything as mutable more than once at a time. — Shepmaster
"bi-directional" - "I don't think there's an ownership problem" - There's always an ownership problem once you've got bidirectional relationships. — Sebastian Redl
@SebastianRedl why thank you for this constructive comment. Good thing you remembered to keep the "read-only" out of your quote...! I may be a noob when it comes to rust, but a non-mut ref has nothing to do with ownership. — Leopard2A5
@Leopard2A5 References, mut or non-mut, affect ownership exactly the same way: the owner must keep the object alive until the references are gone. Mut or non-mut just influences what other references may be taken. Yes, mut references make bi-directional even more difficult because of aliasing issues, but Rust makes any kind of bi-directional relationship difficult. Just look at how tricky it is to implement a doubly linked list. The bottom line is that in Rust, it is very often the best choice to redesign until the bi-directional relationships are gone. — Sebastian Redl

Francis Gagné Francis Gagné · Accepted Answer · 2016-09-17T21:34:27

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.

Satisfying the Rust borrow checker with structs

1 Answers