Cannot borrow mutably and immutably two different lines in a `Vec<Vec>`

help
#1 
// don't ask me why I'm doing that, the real algorithm is slightly
// more complicated!
let mut matrix: Vec<Vec<bool>> = ...;

for i in 0..5 {
    for j in 0..5 {
        if i == j {
            continue;
        }
        // this works
        for k in 0..5 {
            matrix[i][k] |= matrix[j][k];
        }
        // this doesn't work
        // or_assign(&mut matrix[i], &matrix[j]);
    }
}

playground

The borrow checker doesn't allow me to borrow both mutably matrix[i] and immutably matrix[j]. In the general case I would totally agree. However, i != j, so the borrow checker is wrong. The issue is that in my real code I'm using a Vec<BitVec>, so I can't manually use the innermost loops, but instead I want to use the or_assign function.

Is this the right way to tell the borrow checker that he is wrong, or is there a cleaner way?

// SAFETY: This works because i != j
let left: *mut _ = &mut matrix[i];
let left = unsafe { &mut *left };
let right = &matrix[i];
or_assign(left, right);
#2

I think the canonical safe solution is the split_at_mut method on slices. It's definitely arguable whether or not this is cleaner though.

Playground

1 Like
#3

I agree that split_at_mut is safest, though it's annoying to choose the split point.

Another option is to move it to a runtime check by using Vec<RefCell<Vec<bool>>>, so you can freely index multiple rows immutably, then borrow_mut() or borrow() as needed.

1 Like
#4

I would go as far as stating that split_at_mut should be mentioned in the diagnostic.

Using unsafe is reasonable for these kind of cases (IMO, and as long as you have an assert!(i != j)), but given that split_at_mut does this same operation under the covers, I would just use that.

2 Likes
#5

I totally fail to see how I would use split_at_mut here. i is sometime less than j, and sometime more than j. And I don't want slices of lines of my matrix, but references.

#6

@nathanwhit had a link to the playground showing how it would work, but basically you split your Vec<_> into two disjoint &mut [_] and then access the corresponding records in them. &mut [_] could have a method for disjoint mutable record access, but that is already enabled by split_at_mut, which is why it hasn't been proposed (I think) for inclusion in the std.

1 Like
#7

I think that version mixes up which part corresponds to index i, but here's how I would do it:

fn two_index_mut<T>(slice: &mut [T], i: usize, j: usize) -> (&mut T, &mut T) {
    assert!(i != j);
    if i < j {
        let (left, right) = slice.split_at_mut(j);
        (&mut left[i], &mut right[0])
    } else {
        let (left, right) = slice.split_at_mut(i);
        (&mut right[0], &mut left[j])
    }
}

playground

4 Likes
#8

So, basically, you are using explicit array indexing with iteration, which is almost always an anti-pattern.

Instead of insisting on indexing and then hacking the borrow checker after the fact, i.e. trying to force two single-element references through a slice-shaped hole, why not do the splitting beforehand? Playground:

for i in 0..5 {
    let (left, rest) = matrix.split_at_mut(i);
    let (middle, right) = rest.split_first_mut().unwrap();

    for elem in left.iter_mut().chain(right) {
        for k in 0..5 {
            elem[k] |= middle[k];
        }
        
        or_assign(elem, middle);
    }
}
2 Likes
#9

Thanks @H2CO3 that's exactly what I needed. No extra computation, or hard to understand logic in order to not write unsafe.

Also don't think that I'm using index because I prefer them, my first solution I was using matrix.iter().enumerate().

#10

Arf! I just realized that I'm not using Vec but IndexVec which means that I don't have access to split_at_mut. :frowning:

#11

It has a public field raw though, on which you still can call the aforementioned methods, can't you?

1 Like
#12

yes, perfect.

Ah no, I still need to be able to access to the index of elem (I didn't show it in the initial post).

#13

If you change that assert to assert!(i < slice.len() && j < slice.len() && i != j); then LLVM should be able to remove the if branch, greatly reducing the amount of assembly it compiles to. Bonus point: if you swap the if and else bodies and check instead for i > j it will be able to remove another instruction.
With this optimizations this method becomes as efficient as if it was written using unsafe.

But it has a pick2_mut method that does exactly what you want.

2 Likes