Compiler spuriously infers data needs to be borrowed as mutable

[edwardw]

All credits are due to this SO question. This code is tried:

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);
    }
}

I expect it to compile. Instead, rustc complains that the data needs to be borrowed as mutable, which is incorrect:

error[E0596]: cannot borrow data in a `&` reference 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

This happened on rustc-1.37.0, beta-1.38.0 and nightly-1.39.0.

[noncreature0714]

@edwardw Thank you for filing this issue! If there is a rustacean out there who is willing to do a bit of hand-holding, I'd love to help on this issue.

[Duddino]

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

[noncreature0714]

Not sure if this helps, but I needed a mutable Vec of Mutable Strings, because I wanted to modify the collection’s elements, and modify the contents of the elements, so having a &mut Vec<&mut String> made the most sense to me.

I stumbled across this while playing with collections of encrypted strings received out-of-order, where I wanted to sort them and decrypt... hence need the need for &mut Vec<&mut String>.

[Duddino]

You can use &mut Vec<String>

[Spoonbender]

triage: no change

the error message is different though!

error[[E0502]](https://doc.rust-lang.org/nightly/error-index.html#E0502): cannot borrow `*collection` as mutable because it is also borrowed as immutable
 --> src/lib.rs:5:32
  |
5 |             if collection[j] < collection[least_element] {
  |                ----------------^^^^^^^^^^---------------
  |                |               |
  |                |               mutable borrow occurs here
  |                immutable borrow occurs here
  |                immutable borrow later used here
  |
help: try adding a local storing this...
 --> src/lib.rs:5:32
  |
5 |             if collection[j] < collection[least_element] {
  |                                ^^^^^^^^^^^^^^^^^^^^^^^^^
help: ...and then using that local here
 --> src/lib.rs:5:16
  |
5 |             if collection[j] < collection[least_element] {
  |                ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

For more information about this error, try `rustc --explain E0502`.
error: could not compile `playground` due to previous error