Borrowing mutable references in closure to sort vector

Question

Although I understand Rust's approach to memory safety, the ownership concepts, and have no problem with references in general, I'm struggling to figure out how Rust wants me to solve a seemingly trivial problem.

This code is a minimal example.

A struct:

pub struct S {
    value: Option<i8>,
}

with a getter that computes a value the first time, then returns the stored value:

use rand::Rng;
impl S {
    fn get_value(&mut self) -> i8 {
        if let Some(v) = self.value {
            return v;
        }

        let v = rand::thread_rng().gen::<i8>();
        self.value = Some(v);
        v
    }
}

Of course, get_value() needs a mutable reference &mut self, because it modifies self.

This mutability is the source of my struggling when I want to sort a vector of references to S, by the result of get_value(). Because I want to sort by get_value(), the comparison function used by sort_by will need mutable references.

My first attempt:

fn main() {
    let mut a = S {value: None};
    let mut b = S {value: None};
    let mut c = S {value: None};

    let mut v = vec![&mut a, &mut b, &mut c];

    v.sort_by( |a, b| a.get_value().cmp(&b.get_value()) );
}

Throws:

error[E0596]: cannot borrow `**a` as mutable, as it is behind a `&` reference
  --> src/main.rs:27:20
   |
27 |     v.sort_by( |a, b| a.get_v().cmp(&b.get_v()) );
   |                 -     ^ `a` is a `&` reference, so the data it refers to cannot be borrowed as mutable
   |                 |
   |                 help: consider changing this to be a mutable reference: `&mut &mut S`

My initial thought was that having a vector of mutable references in the first place would allow the comparison function to use mutable references. My getter function however borrows a mutable reference to a mutable reference, that's why the error says cannot borrow '**a'.

The help suggests to change |a,b| so that they are &mut &mut S references.

Is &mut &mut the same as &&mut? Does it mean I should change it into |mut a:&&mut S, mut b:&&mut S|?

Answer 1

The closure in sort_by(<closure>) has the signature FnMut(&T, &T) -> Ordering because the items must be immutable for the duration of the sort. If it was possible to mutate items during the sort then how would you ever be able to tell when the collection is actually sorted? It becomes impossible to verify the correctness of the sort!

Furthermore, sort_by is a comparison-based sort which means it will visit every item in the collection at least once, so every item will be initialized throughout the sort, so you're not really gaining anything by using a lazy-initialization getter in this scenario.

If for some reason you want to stick with the lazy-initialization getter for other reasons then my suggestion is just to initialize all the items prior to sorting them:

use rand::Rng;

pub struct S {
    value: Option<i8>,
}

impl S {
    fn get_value(&mut self) -> i8 {
        if let Some(v) = self.value {
            return v;
        }

        let v = rand::thread_rng().gen::<i8>();
        self.value = Some(v);
        v
    }
}

fn main() {
    let mut a = S { value: None };
    let mut b = S { value: None };
    let mut c = S { value: None };

    let mut v = vec![&mut a, &mut b, &mut c];

    // initialize all items, it's what would
    // happen in the sort below if it allowed
    // mutating items mid-sort anyway
    v.iter_mut().for_each(|i| {
        i.get_value();
    });

    // sort initialized items without mutating them
    v.sort_by(|a, b| a.value.cmp(&b.value));
}

playground

Answer 2

Assuming your example is simplified, and the mutability is actually necessary in your real code, this might be a good case for interior mutability, e.g. with a Cell:

use std::cell::Cell;

pub struct S {
    value: Cell<Option<i8>>,
}

Which means you can update your getter method so it doesn't take a mutable self reference:

impl S {
    fn get_value(&self) -> i8 {
        if let Some(v) = self.value.get() {
            return v;
        }

        let v = rand::thread_rng().gen::<i8>();
        self.value.set(Some(v));
        v
    }
}

And you can get rid of some of the other mutable references too:

fn main() {
    let a = S { value: Cell::default() };
    let b = S { value: Cell::default() };
    let c = S { value: Cell::default() };

    let mut v = vec![&a, &b, &c];

    v.sort_by(|a, b| a.get_value().cmp(&b.get_value()));
}