Mutable reference to container object within iterator loop

Question

I'm writing a game engine. In the engine, I've got a game state which contains the list of entities in the game.

I want to provide a function on my gamestate update which will in turn tell each entity to update. Each entity needs to be able to refer to the gamestate in order to correctly update itself.

Here's a simplified version of what I have so far.

pub struct GameState {
    pub entities: Vec<Entity>,
}

impl GameState {
    pub fn update(&mut self) {
        for mut t in self.entities.iter_mut() {
            t.update(self);
        }
    }
}

pub struct Entity {
    pub value: i64,
}

impl Entity {
    pub fn update(&mut self, container: &GameState) {
        self.value += container.entities.len() as i64;
    }
}

fn main() {
    let mut c = GameState { entities: vec![] };

    c.entities.push(Entity { value: 1 });
    c.entities.push(Entity { value: 2 });
    c.entities.push(Entity { value: 3 });

    c.update();
}

The problem is the borrow checker doesn't like me passing the gamestate to the entity:

error[E0502]: cannot borrow `*self` as immutable because `self.entities` is also borrowed as mutable
 --> example.rs:8:22
  |
7 |         for mut t in self.entities.iter_mut() {
  |                      ------------- mutable borrow occurs here
8 |             t.update(self);
  |                      ^^^^ immutable borrow occurs here
9 |         }
  |         - mutable borrow ends here

error: aborting due to previous error

Can anyone give me some suggestions on better ways to design this that fits with Rust better?

Thanks!

Answer 1

First, let's answer the question you didn't ask: Why is this not allowed?

The answer lies around the guarantees that Rust makes about & and &mut pointers. A & pointer is guaranteed to point to an immutable object, i.e. it's impossible for the objects behind the pointer to mutate while you can use that pointer. A &mut pointer is guaranteed to be the only active pointer to an object, i.e. you can be sure that nobody is going to observe or mutate the object while you're mutating it.

Now, let's look at the signature of Entity::update:

impl Entity {
    pub fn update(&mut self, container: &GameState) {
        // ...
    }
}

This method takes two parameters: a &mut Entity and a &GameState. But hold on, we can get another reference to self through the &GameState! For example, suppose that self is the first entity. If we do this:

impl Entity {
    pub fn update(&mut self, container: &GameState) {
        let self_again = &container.entities[0];
        // ...
    }
}

then self and self_again alias each other (i.e. they refer to the same thing), which is not allowed as per the rules I mentioned above because one of the pointers is a mutable pointer.

What can you do about this?

One option is to remove an entity from the entities vector before calling update on it, then inserting it back after the call. This solves the aliasing problem because we can't get another alias to the entity from the game state. However, removing the entity from the vector and reinserting it are operations with linear complexity (the vector needs to shift all the following items), and if you do it for each entity, then the main update loop runs in quadratic complexity. You can work around that by using a different data structure; this can be as simple as a Vec<Option<Entity>>, where you simply take the Entity from each Option, though you might want to wrap this into a type that hides all None values to external code. A nice consequence is that when an entity has to interact with other entities, it will automatically skip itself when iterating on the entities vector, since it's no longer there!

A variation on the above is to simply take ownership of the whole vector of entities and temporarily replace the game state's vector of entities with an empty one.

impl GameState {
    pub fn update(&mut self) {
        let mut entities = std::mem::replace(&mut self.entities, vec![]);
        for mut t in entities.iter_mut() {
            t.update(self);
        }
        self.entities = entities;
    }
}

This has one major downside: Entity::update will not be able to interact with the other entities.

Another option is to wrap each entity in a RefCell.

use std::cell::RefCell;

pub struct GameState {
    pub entities: Vec<RefCell<Entity>>,
}

impl GameState {
    pub fn update(&mut self) {
        for t in self.entities.iter() {
            t.borrow_mut().update(self);
        }
    }
}

By using RefCell, we can avoid retaining a mutable borrow on self. Here, we can use iter instead of iter_mut to iterate on entities. In return, we now need to call borrow_mut to obtain a mutable pointer to the value wrapped in the RefCell.

RefCell essentially performs borrow checking at runtime. This means that you can end up writing code that compiles fine but panics at runtime. For example, if we write Entity::update like this:

impl Entity {
    pub fn update(&mut self, container: &GameState) {
        for entity in container.entities.iter() {
            self.value += entity.borrow().value;
        }
    }
}

the program will panic:

thread 'main' panicked at 'already mutably borrowed: BorrowError', ../src/libcore/result.rs:788

That's because we end up calling borrow on the entity that we're currently updating, which is still borrowed by the borrow_mut call done in GameState::update. Entity::update doesn't have enough information to know which entity is self, so you would have to use try_borrow or borrow_state (which are both unstable as of Rust 1.12.1) or pass additional data to Entity::update to avoid panics with this approach.