Modify a struct while iterating over an Iterable in the struct

Question

I am implementing a rolling prime sieve in Rust. The struct looks like this:

struct Sieve {
    window_index: u32,
    window_size: u32,
    board: BitVec,
    primes: Vec<u32>,
}

There is a moving 'window' in which prime multiples are marked on a board of size window_size, and any numbers encountered that are unmarked are known to be prime.

When the window is moved, the new board needs to be re-initialized with all the multiples of the previously discovered primes marked.

let square_optimization = (self.window_index + self.window_size).integer_sqrt();
for &prime in self.primes.iter().filter(|&&p| p < square_optimization) {
    let remainder = self.window_index % prime;
    let start_prime = if remainder > 0 { self.window_index + prime - remainder } else { remainder };
    if start_prime > self.window_index + self.window_size { return; }

    for i in (start_prime % self.window_size..self.window_size).step_by(prime as usize) {
        self.board.set(i as usize, true)
    }
}

The exact logic doesn't matter, however you can see that there is an immutable borrow of self.primes and a mutable borrow of self.board. The compiler is happy. The problem appears when extracting the logic into a function:

fn mark_multiples(&mut self, prime: u32) {
    let remainder = self.window_index % prime;
    let start_prime = if remainder > 0 { self.window_index + prime - remainder } else { remainder };
    if start_prime > self.window_index + self.window_size { return; }

    for i in (start_prime % self.window_size..self.window_size).step_by(prime as usize) {
        self.board.set(i as usize, true)
    }
}

fn compute_chunk(&mut self) {
    let square_optimization = (self.window_index + self.window_size).integer_sqrt();
    for &prime in self.primes.iter().filter(|&&p| p < square_optimization) {
        self.mark_multiples(prime)
    }

    // do work
}

error[E0502]: cannot borrow `*self` as mutable because it is also borrowed as immutable
  --> src/lib.rs:54:13
   |
53 |         for &prime in self.primes.iter().filter(|&&p| p < square_optimization) {
   |                       --------------------------------------------------------
   |                       |
   |                       immutable borrow occurs here
   |                       immutable borrow later used here
54 |             self.mark_multiples(prime)
   |             ^^^^^^^^^^^^^^^^^^^^^^^^^^ mutable borrow occurs here

Why does the borrow checker get confused here? Is self not mutably borrowed in the first case?

I haven't come across a language in which method extraction doesn't "just work" but being new to rust, no, I'm not sure. — arlyon, Aug 12 '19 at 10:26
`mark_multiples` mutably borrows the entirety of `self`, but `prime` is also immutably borrowed *from* self. What would happen to `prime` if the implementation of `mark_multiples` decided to replace `self` and drop the original version? Now, *you* know that your function doesn't do this, but the compiler doesn't! — Joe Clay, Aug 12 '19 at 10:44
Rust references work like read-write locks. You either exclusively acquire (`&mut`) it mutably, or you acquire a shared lock (`&`) immutably. Exclusive and shared can't happen simultaneously. — SOFe, Aug 12 '19 at 10:54
@arlyon, method extraction indeed does *not* “just work” in Rust, because the borrow checker works separately in each function, only considering the signature for their interfaces. So you can extract functions, but if you pass them references to more than they actually touch, they may start to conflict where the mixed code didn't. This is very intentional, because it allows you to refactor the function bodies with confidence that you are not creating a conflict with code in some caller. — Jan Hudec, Aug 12 '19 at 11:24

Peter Varo · Accepted Answer · 2019-08-13T08:40:38.160

Why? Because self.primes borrowed immutably (because of Vec::iter, i.e. the newly created iterator, Iter is referencing the vector which is owned by self) and while this is happening mark_multiples tries to borrow self as mutable. The borrowing rules are simple and straightforward:

You could have arbitrary number of immutable borrows of an object at a given time, or
You could have a single mutable borrow of an object at a given time.

Thus, you cannot have a mutable borrow of self, while you still hold an immutable borrow of it, and that's exactly the reason why the compiler refuses to compile your code.

Why is this safety feature considered any good here? If what you want would be allowed for you that would mean, you could potentially change the values of self.primes in the method self.mark_multiples while you iterate over it in self.compute_chunk. You could easily run into referencing invalid memory locations!

Modify a struct while iterating over an Iterable in the struct

1 Answers1