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?

I think that the compiler is going crazy trying to decide whether to use Index or IndexMut while deciding the override of PartialEq::lt to use. You can workaround with a couple of temporary variables such as let a = &collection[j]; let b = &collection[least_element]; if a < b ... — rodrigo
Or you can use std::ops::Index; and write if collection.index(j) < collection.index[least_element] ... — rodrigo
Or simply if collection[j].lt(&collection[least_element]) .... I'm starting to think that you may have found a compiler bug... — rodrigo
&collection[j] < &collection[least_element] also works. Don't know why though. — mcarton

Andrea Proone Andrea Proone · Accepted Answer · 2019-10-09T13:48:09

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

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

1 Answers