Borrow checker logic

Here's a fairly simple code from an implementation that has some loops in which the loop iterator is being modified:

fn process(data: &mut Vec<u32>) {
    let some_read_only_fn = |j| data[(j * 2 + 1) % data.len()];
    for i in 0..data.len() {
        let _ = some_read_only_fn(i);
        data[i] = (i + 1) as u32;
    }
}

This code doesn't compile unless if you move the closure def. into the loop. This makes sense to me as a human: The loop's scope has a mutable borrow of data, hence the closure need to be inside to borrow the correct reference of data. But I can't really figure out what the compiler is doing here. reading similar questions, I also came across NLL, which I am not yet sure if it is related yet. So, all in all, can clarify: What is the compiler's checking logic, both with the closure inside and outside of the loop, yielding correct and incorrect compilations respectively?

Thanks!

Formally, what is happening is that some_read_only_fn is holding an immutable reference into data, which is valid for the entire body of fn process (and NLL can't really shorten this borrow because it's being called in the loop, so the borrow has to persist across iterations).

Meanwhile, doing data[i] = … inside the loop borrows data mutably, while there's still an immutable reference to it, which is not allowed.

When you move the creation of the closure into the loop, NLL is able to figure out that you no longer use the closure after you call it, so it can store its return value and end the immutable borrow right away, then mutably borrow data, which is now allowed as there's no other outstanding borrow into it.

I believe this wouldn't have compiled without NLL even if you had moved the closure into the loop, since lexically, the immutable borrow would have ended only at the end of the iteration.


By the way, since you are not modifying the length of the vector (i.e. you are not adding or removing elements, you only overwrite existing ones), you shouldn't take a &mut Vec<u32>. This makes it impossible to pass something that can coerce to a mutable slice but is not a vector (e.g. a statically-sized array). You should take a slice (&mut [u32]) instead.

3 Likes

Thanks for the explanation! I recently learned about NLL, so this explains the confusion.

Regarding your final point: I simplified the code here a bit. The reality is closer to this:

struct Data {
    a: u32, 
    b: Vec<u32>
}

fn process(data: &mut Vec<Data>) {
    for i in 0..data.len() {
        // remove or push from the inner field
        data[i].b.remove(some_index);
    }
}

As far as I know, this still justifies the use of Vec itself since the size of the entire data can change, despite the vector length of data being constant.

Hmm? No, if you aren't changing the number of Datas contained in data, you do not need &mut Vec. Just change it to &mut [Data] and you should see that it still compiles.

2 Likes

The vector inside data is stored separately on the heap from the Data struct, so it doesn't have any effect on the size of your outer vector.

1 Like

I don't think so.