Mutable reborrow in a loop an element of an array via `index_mut` and by `get_mut`

Hello everyone! I'm working on suffix tree so I've got a problem walking along the tree.

Code example

The borrow checker says me mutable borrow starts here in previous iteration of loop, I understand what it's talking about. This leads to the situation when a program could have two mutable references to the same piece of data but in my case there is one reference current so the case can be considered as re-borrowing which is legal as far as I got.

The borrow checker doesn't raise any error if I replace get_mut by getting an element by index e.g. call index_mut. I don't see the difference between the methods from the point of the mutability. Both of them accept &mut self. Both of them return a mutable references but get_mut returns Option<&mut T>.

What is the difference between the methods? Is this re-borrowing or not?

P.S. I can't just proceed with getting an element by index because I need to write a wrapper for the array which doesn't work as well but I removed from the example to keep it simple.

The [] operator on arrays and slices is a compiler builtin, without actually calling Index/IndexMut. In fact, the implementations of those traits just use the operator, commented "N.B., use intrinsic indexing." If you literally call index_mut instead of using [], it has the same error as with get_mut.

1 Like

Ok, I saw the comment in the implementation of SliceIndex for usize but didn't realize.

Does that mean that I don't have reborrowing here?

I'm not sure exactly what that means from the borrowck perspective, but my intuition is just that it can see more of the data relationships when it's all local, rather than involving function calls.

I found that your example code is accepted if you add else { break } -- in this case I think it's moving current into the expression, and then it either gets reassigned or never accessed again.

I think I got the picture. This piece of code:

if let Some(ref mut id) = current.1.get_mut(0).unwrap() {
    current = id;
}

Do the same as this piece of code

current = if let Some(ref mut id) = current.1.get_mut(0).unwrap() {
    id
} else {
	current
}

A function which can wrap this code looks so:

fn next<'a>(current: &'a mut Node) -> &'a mut Node {
	if let Some(ref mut id) = current.1.get_mut(0).unwrap() {
    	id
	} else {
		current
	} 
}

So it's not clear how long the returned reference is able to live at compile time as the inner field's lifetime (e.g. id) may differ from the life time of the current reference and we can't determine that at compile time (at least for now). We could rewrite this function in such way:

fn next<'out, 'a: 'out>(current: &'a mut Node) -> &'out mut Node {
	if let Some(ref mut id) = current.1.get_mut(0).unwrap() {
    	id
	} else {
		current
	} 
}

This way we say that we return a mutable reference which has lifetime shorter than 'a but the borrow checker again says that we try to borrow current twice because prediction of chosen branch of the fork is impossible at compile time so compiler regards both.

Updated code snippet

Correct me if I'm wrong, please.

I believe that this is at least in part a scoping problem with how long the borrow within the if let lasts. (These used to be more common before we had NNL - non-lexical lifetimes.)

Here's a version of your next function that compiles, at the cost of being rather redundant.

After this snippet I'm again in the middle of nowhere. My explanation doesn't work so I have no idea why my origin code snippet is invalid.

Your original code builds successfully when compiled with -Z polonius, the experimental next-generation borrow checker in the nightly toolchain.

This means your original code should be valid, but limitations in the current borrow checker prevent it from finding the correct ending points for certain borrows that cross branches and/or function boundaries.

2 Likes

I have a reason to use a little piece of unsafe code then. Many thanks!