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

&&mut x cannot be mutated, as if it could, you could split a mutable reference, causing race conditions. Sadly, sorting is immutable reference only in Rust due to the fact that if values were to change during sorting, it could mess up the whole process. You might want to consider using something like std::cell::Cell for interior mutability since your case is perfectly safe (once a value is obtained it should never change). — Aplet123
If your value isn't created until its accessed, and then doesn't change, consider using OnceCell — kmdreko

Peter Hall Peter Hall · Accepted Answer · 2021-01-27T21:50:50

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

Borrowing mutable references in closure to sort vector

2 Answers