What is Rust's borrow checker really complaining about here?

Question

Consider a simple selection sort on a &mut Vec<&mut String>:

fn selection_sort(collection: &mut Vec<&mut String>) {
    for i in 0..collection.len() {
        let mut least_element = i;
        for j in (i + 1)..collection.len() {
            if collection[j] < collection[least_element] {
                least_element = j;
            }
        }

        collection.swap(least_element, i);
    }
}

This loop should work, based on this and that – yet the borrow throws this error:

error[E0596]: cannot borrow data in a `&` reference as mutable
  --> src/main.rs:58:28
   |
58 |             if chunks[j] < chunks[least_element] {
   |                            ^^^^^^^^^^^^^^^^^^^ cannot borrow as mutable
   |
   = help: trait `IndexMut` is required to modify indexed content

Or in newer versions of Rust:

error[E0596]: cannot borrow data in an index of `std::vec::Vec<&mut std::string::String>` as mutable
 --> src/lib.rs:5:32
  |
5 |             if collection[j] < collection[least_element] {
  |                                ^^^^^^^^^^^^^^^^^^^^^^^^^ cannot borrow as mutable
  |
  = help: trait `IndexMut` is required to modify indexed content, but it is not implemented for `std::vec::Vec<&mut std::string::String>`

Wouldn't it make more sense to have a & reference be mutable?

The IndexMut documentation doesn't use an example I understand well and has a pretty large example that doesn't seem to clearly demonstrate how to use IndexMut, especially in the context of a selection sort, or swapping elements.

Error 0596 explains it occurs when trying to borrow from an immutable value, yet least_element is mutable. If i is changed to mut i this also does compile (and the compiler recommends removing mut from i).

Is there a Rustacean who can illuminate this?

Answer 1

When you try to access collection[j], the compiler returns a &mut String because that's the type of the vector's elements. When you try to access collection[least_element], the borrow checker doesn't know if least_element != j, and having two mutable references of the same element would be undefined behavior. You can either use std::ops::Index which returns a &&mut String (and it's safe to have two immutable references to the same mutable reference), directly borrowing the elements (&collection[j] < &collection[least_element]) or, if possible, changing the type of collection to Vec<&String> or Vec<String>.