How to implement multiple mutable borrows of a vector in Rust?

Question

I am implementing matrices in Rust. The code is adapted for the example, but there might be minor mistakes:

#[derive(Debug, PartialEq)]
pub struct Matrix<T> {
    inner: Vec<Vec<T>>,
}

impl<T> Matrix<T> {
    pub fn dim(&self) -> (usize, usize) {
        if self.inner.len() == 0 {
            (0, 0)
        } else {
            (self.inner.len(), self.inner[0].len())
        }
    }
}

I want to have the ability to get quadrants of the matrix:

+----+----+
| Q1 | Q2 |
+----+----+
| Q3 | Q4 |
+----+----+

I introduced the Slice and SliceMut structures to borrow a part of the matrix:

pub struct Slice<'a, T: 'a> {
    matrix: &'a Matrix<T>,
    start: (usize, usize),
    end: (usize, usize),
}

pub struct SliceMut<'a, T: 'a> {
    matrix: &'a mut Matrix<T>,
    start: (usize, usize),
    end: (usize, usize),
}

Now I want to implement two functions:

• quadrants - to get a tuple of four slices
• quadrants_mut - to get a tuple of four mutable slices

I cannot mutably borrow one matrix several times in quadrants_mut:

fn quadrants_mut<'a, T>(matrix: &'a mut Matrix<T>) -> (SliceMut<'a, T>, SliceMut<'a, T>, SliceMut<'a, T>, SliceMut<'a, T>) {
    let (rows, cols) = matrix.dim();

    let mid_rows = rows / 2;
    let mid_cols = cols / 2;

    let a = SliceMut { matrix: matrix, start: (0, 0), end: (mid_rows, mid_cols) };
    let b = SliceMut { matrix: matrix, start: (0, mid_rows), end: (mid_cols, cols) };
    let c = SliceMut { matrix: matrix, start: (mid_rows, rows), end: (0, mid_cols) };
    let d = SliceMut { matrix: matrix, start: (mid_rows, rows), end: (mid_cols, cols) };

    (a, b, c, d)
}

When I try to compile that, I have an error:

error[E0499]: cannot borrow `*matrix` as mutable more than once at a time
  --> src/matrix/slice.rs:62:13
   |
59 |     let a = SliceMut { matrix: matrix, start: (0, 0), end: (mid_rows, mid_cols) };
   |                        ------ first mutable borrow occurs here
...
60 |     let b = SliceMut { matrix: matrix, start: (0, mid_rows), end: (mid_cols, cols) };
   |                        ^^^^^^ second mutable borrow occurs here
...
66 | }

I am trying to mutably borrow a matrix four times. How should I change the code to make it compile?

Answer 1

Safe Rust does not allow to have multiple mutable bindings at once. This is implemented with checking the binding type (whether it is mutable) and counting. The compiler is not so smart to understand your intentions fully and so it can be told that the slices you use will never intersect. By having multiple mutable references in your code, even to different parts of the data, you still violate the rule.

As a solution it is possible to have one reference and indexes which will give you quadrant data: its begin and end indexes, or just begin and count:

playground

pub struct SliceMut<'a, T: 'a> {
    matrix: &'a mut Matrix<T>,
    quadrants: Vec<(Range<usize>, Range<usize>)>,
}

fn quadrants_mut<'a, T>(matrix: &'a mut Matrix<T>) -> SliceMut<'a, T> {
    let (rows, cols) = matrix.dim();

    let mid_rows = rows / 2;
    let mid_cols = cols / 2;

    SliceMut {
        matrix: matrix,
        quadrants: vec![
            (0..0, mid_rows..mid_cols),
            (0..mid_rows, mid_cols..cols),
            (mid_rows..rows, 0..mid_cols),
            (mid_rows..rows, mid_cols..cols),
        ],
    }
}

As for split_at_mut, it uses unsafe Rust and implemented as the following:

#[inline]
fn split_at_mut(&mut self, mid: usize) -> (&mut [T], &mut [T]) {
    let len = self.len();
    let ptr = self.as_mut_ptr();

    unsafe {
        assert!(mid <= len);

        (from_raw_parts_mut(ptr, mid),
         from_raw_parts_mut(ptr.offset(mid as isize), len - mid))
    }
}

Answer 2

What you want to do, is definitely possible. However it's hard. Really hard.

Luckily, I'll only show how to do the easy part.

---

If you look at how split_at_mut is implemented, you can notice it requires you to create a parallel structure that mimics return value of quadrants_mut (i.e. SliceMut):

pub struct SliceMut<'a, T: 'a> {
    matrix: &'a mut Matrix<T>,
    start: (usize, usize),
    end: (usize, usize),
}

#[repr(C)]
struct MatrixRaw<T> {
    data: *const Matrix<T>,
    start: (usize, usize),
    end: (usize, usize),
}

Note the similarity between these two structures. If at any point they diverge, your mem::transmute will either stop working, or your safe code will experience segfaults.

Then we create a method that transmutes MatrixRaw into SliceMut.

#[inline]
pub unsafe fn from_raw_mat_mut<'a, T>(
    p: *mut Matrix<T>,
    start: (usize, usize),
    end: (usize, usize),
) -> SliceMut<'a, T> {
    mem::transmute(MatrixRaw {
        data: p,
        start: start,
        end: end,
    })
}

As a last step, we add an unsafe block to quadrant_mut:

unsafe {
    let a = from_raw_mat_mut(matrix, (0, 0), (mid_rows, mid_cols));
    let b = from_raw_mat_mut(matrix, (0, mid_rows), (mid_cols, cols));
    let c = from_raw_mat_mut(matrix, (mid_rows, rows), (0, mid_cols));
    let d = from_raw_mat_mut(matrix, (mid_rows, rows), (mid_cols, cols));

    (a, b, c, d)
}

Link to playground

---

HARD PART: Here comes the hard part - making sure your methods, and iterators, don't accidentally invalidate your data and invariants. This is extremely hard to achieve in the Matrix case.

Why? Well, because there isn't a nice way to say to your data, "don't touch these parts" like you can with an array. With an array, you just offset your data and you're pretty much good to go. But a Matrix? It's not impossible, but I suspect I don't know of a way that doesn't introduce performance penalties.