When coming to rust from other languages, the borrow checker can be frustrating. Common, ingrained ways of doing things just don’t work, and you have to find the “idiomatic rust” way. I guess this is a good thing, and helps prevent the “all my python code looks like bash scripts” problem, whereby you take your patterns for one language and shoehorn them into whatever language you are actually using, but it doesn’t stop it being frustrating…

One pattern I get into quite a bit is the nested loop, where you loop over a collection, and within that loop, loop over it (or a subset) again.

Here is a trivial example you might see in a turn based game. Each player takes their turn (outer loop). When a player acts, the other players see the move, so get a call with the move the other player just made (inner loop). The simple implementation in rust doesn’t compile:

Common code:

trait Player {
    fn get_id(&self)->u32;
    fn act(&mut self)->i32;
    fn see_action(&mut self, player_id:u32, action:i32);
}

struct SimplePlayer {
    id:u32,
    other_player_actions:Vec<i32>
}

impl SimplePlayer {
    pub fn new(player_id:u32) -> SimplePlayer {
        SimplePlayer {
            id:player_id,
            other_player_actions:vec![]
        }
    }
}

impl Player for SimplePlayer {
    fn get_id(&self) ->u32 {
        self.id
    }
    fn act(&mut self) ->i32 {
        if self.other_player_actions.len() == 0 {
            42
        } else {
            self.other_player_actions.iter().sum()
        }
    }
    fn see_action(&mut self, _player_id:u32, action:i32) {
        self.other_player_actions.push(action);
    }
}

Broken loop:

fn main() {
    
    let mut players:Vec<Box<dyn Player>> = Vec::new();
    players.push(Box::new(SimplePlayer::new(1)));
    players.push(Box::new(SimplePlayer::new(2)));
    players.push(Box::new(SimplePlayer::new(3)));
    
    for player in players.iter() {
        let action = player.act();
        for p in players.iter() {
            p.see_action(player.get_id(), action);
        }
    }
    
}

There are several ways around this:

  1. Iterate over a range for the outer loop.
  2. Restructure
  3. Use interior mutability

Let’s look at each of these in turn.

1) Iterate over a range for the outer loop

We can change the outer loop to iterate over a range representing the indices into the Players Vec, and just get a mutable reference to a player for the small scope in which it is needed.

    for player_num in 0..players.len() {
        let action = players.get_mut(player_num).unwrap().act();
        let player_id = players.get(player_num).unwrap().get_id();
        for p in players.iter_mut() {
            p.see_action(player_id, action);
        }
    }

This is the easiest way out here - we don’t need to create a mutable iterator at the top level. If it wasn’t for the inner loop, a mutable iterator would be a bit less code, but with nested loops, itersting over a range allows us to only borrow each player mutably for the short time we are mutating it. When we run the second loop, we have nothing borrowed, so can create a mutable iterator.

2) Restructure

Many times, a nested loop can be replaced with a different program structure. In this case, instead of calling each player to tell it about each event from another player, we can create a game state which is visible to each player.

In our trivial game simulation, the players don’t need to know the moves of the other players until it is thier turn to act. This allows us to refactor the player trait to take in the list of moves as an argument to act.

trait Player {
    fn get_id(&self)->u32;
    fn act(&mut self, moves:&Vec<(u32,i32)>)->i32;
}

struct SimplePlayer {
    id:u32,
}

impl SimplePlayer {
    pub fn new(player_id:u32) -> SimplePlayer {
        SimplePlayer {
            id:player_id
        }
    }
}

impl Player for SimplePlayer {
    fn get_id(&self) ->u32 {
        self.id
    }
    fn act(&mut self, moves:&Vec<(u32,i32)>) ->i32 {
        if moves.len() == 0 {
            42
        } else {
            moves.iter().map(|(_,x)| x).sum()
        }
    }
}

This negates the need to have an inner loop.

 	let mut moves:Vec<(u32,i32)> = vec![];
    
    for player in players.iter_mut() {
        let action = player.act(&moves);
        moves.push((player.get_id(), action));
    }

3. Use interior mutability

Interior mutability moves the borrow checking from compile time to runtime. When we know we won’t have multiple mutable borrows at the same time, but are not able to prove it to the compiler, we can use this to get our program to work. We don’t need to do this here, because as the examples above show, the desired goal can be achieved without it. The rust book has a better example for the use of RefCell with the MockMessenger

For reference, here is an example using RefCell to achieve this.

We change the SimplePlayer to hold a *RefCell<Vec>* rather than a *Vec*

struct SimplePlayer {
    id:u32,
    other_player_actions:RefCell<Vec<i32>>
}

impl Player for SimplePlayer {
    fn get_id(&self) ->u32 {
        self.id
    }
    fn act(&self) ->i32 {
        if self.other_player_actions.borrow().len() == 0 {
            42
        } else {
            self.other_player_actions.borrow().iter().sum()
        }
    }
    fn see_action(&self, _player_id:u32, action:i32) {
        self.other_player_actions.borrow_mut().push(action);
    }
}

Now the original loop works as expected. Here is the full code:

use std::cell::RefCell;

trait Player {
    fn get_id(&self)->u32;
    fn act(&self)->i32;
    fn see_action(&self, player_id:u32, action:i32);
}

struct SimplePlayer {
    id:u32,
    other_player_actions:RefCell<Vec<i32>>
}

impl SimplePlayer {
    pub fn new(player_id:u32) -> SimplePlayer {
        SimplePlayer {
            id:player_id,
            other_player_actions:RefCell::new(vec![])
        }
    }
}

impl Player for SimplePlayer {
    fn get_id(&self) ->u32 {
        self.id
    }
    fn act(&self) ->i32 {
        if self.other_player_actions.borrow().len() == 0 {
            42
        } else {
            self.other_player_actions.borrow().iter().sum()
        }
    }
    fn see_action(&self, _player_id:u32, action:i32) {
        self.other_player_actions.borrow_mut().push(action);
    }
}

fn main() {
    
    let mut players:Vec<Box<dyn Player>> = Vec::new();
    players.push(Box::new(SimplePlayer::new(1)));
    players.push(Box::new(SimplePlayer::new(2)));
    players.push(Box::new(SimplePlayer::new(3)));
    
    for player in players.iter() {
        let action = player.act();
        for p in players.iter() {
            p.see_action(player.get_id(), action);
        }
    }
    
}

Thanks for reading. If you have any questions, suggestions, or to point out any mistakes, please contact me at the email address below. I’d love to hear from you.