Returning a mutable reference in Rust

Question

I am learning Rust, so apologies if this is a trivial question. I have googled for an hour to no avail.

I have an array of enum values. I wish to find a random location within that array that matches a specific pattern and return a mutable reference to it, with the intent of modifying the element in that location.

enum Tile {
    Empty,
    ...  // Other enum values
}

fn random_empty_tile(arr: &mut [Tile]) -> &mut Tile {
    loop {
        let i = rand::thread_rng().gen_range(0, arr.len());
        let tile = &mut arr[i];
        if let Tile::Empty = tile {
            return tile;
        }
    }
}

The borrow checker complains about two specific things here. The first is the arr.len() call. This is disallowed because it requires taking an immutable reference to arr, and we already have a mutable reference to arr via the parameter. Therefore, no other references can be taken and the call is not allowed.

The second is return tile. This fails because the borrow checker cannot prove that the lifetime of this reference is the same as the lifetime of arr itself, so it's not safe to be returned.

I think the above descriptions of the errors are correct; I think I understand what is going wrong. Unfortunately I have no idea how to fix either of these problems. If someone could provide an idiomatic solution to achieve this behaviour, it would be greatly appreciated.

Ultimately, I wish to do the following:

let mut arr = [whatever];
let empty_element = random_empty_tile(&mut arr);
*empty_element = Tile::SomeOtherValue;

Thus mutating the array such that the empty value is replaced.

Answer 1

Answer to the problem

fn random_empty_tile(arr: &mut [Tile]) -> &mut Tile {
    let len = arr.len();
    let mut the_chosen_i = 0;
    loop {
        let i = rand::thread_rng().gen_range(0, len);
        let tile = &mut arr[i];
        if let Tile::Empty = tile {
            the_chosen_i = i;
            break;
        }
    }
    &mut arr[the_chosen_i]
}

will work. You are allowed to use a mutable borrow in the loop, just don't abuse it, from the borrowcheckers perpective. What you're effectively doing, is mutably re-borrowing an array repeatedly. As always, the compiler is super helpful, if you know how to use it.

To get to the root of the problem, lets look at just the first two iterations of our loop:

fn random_empty_tile_2<'arr>(arr: &'arr mut [Tile]) -> &'arr mut Tile {
   let len = arr.len();

   // First loop iteration
   {
       let i = thread_rng().gen_range(0, len);
       let tile = &mut arr[i]; // Lifetime: 'arr
       if let Tile::Empty = tile {
           return tile;
       }
   } 

   // Second loop iteration
   {
       let i = thread_rng().gen_range(0, len);
       let tile = &mut arr[i]; // Lifetime: 'arr
        if let Tile::Empty = tile {
           return tile;
       }
   }

   unreachable!();

}

The compiler tells us: The borrow of arr, called tile has to have the same lifetime as the array itself, called 'arr, as it is returned. In the next loop iteration, we again borrow arr for 'arr. This is a violation of the borrowcheckers rules.

Some comments

Your're not doing yourself a favor with all this mutability. This might manifest in the borrowchecker complaining later on in main, when you try to hold a mutable reference to a value in arr and use arr at the same time, as this is (of course, if you think about it!) disallowed.

Also, your algorithm for choosing a random empty tile is dangerously speculative. What if there's only one empty tile in a large array? Your implementation will take forever. Consider first filtering to all indices pointing to an empty tile, then choose a random index from this set, then return the entry this index points to. I wont provide code for this, you got this on your own :)