rust - Mutating an item inside of nested loops

Question

I'm trying to write a program to evenly (or as close to possible) distribute points about the surface of a sphere. I'm trying to achieve this by placing N points randomly about a unit sphere, and then running multiple steps where the points repel each other.

The problem is in the loop over the points array. The code below loops over each point, and then the loop inside that, again loops over each point and calculates the repulsive force between each point pair.

for point in points.iter_mut() {
    point.movement = Quaternion::identity();
    for neighbour in &points {
        if neighbour.id == point.id {
            continue;
        }
        let angle = point.pos.angle(&neighbour.pos);
        let axis = point.pos.cross(&neighbour.pos);
        let force = -(1.0/(angle*angle)) * update_amt;
        point.movement = point.movement * Quaternion::angle_axis(angle, axis);
    }
}

I'm getting the error:

src/main.rs:71:27: 71:33 error: cannot borrow `points` as immutable because it is also borrowed as mutable
src/main.rs:71         for neighbour in &points {

and the explanation

the mutable borrow prevents subsequent moves, borrows, or modification of `points` until the borrow ends

I'm fairly new to Rust, coming from a C++ background, and I've got no idea how to make this kind of pattern work in Rust.

Any solutions to this would be greatly appreciated, as I'm now absolutely stuck for ideas.

Answer 1

There's a few ways one can write this.

One is your suggestion, of separating movements into a separate vector, since that ensures that the mutable borrow of the movement value doesn't force the compiler to conservatively disallow access to the rest of points to avoid mutable borrows from aliasing. In Rust, &mut reference can never alias: if values are accessible by exactly one path, it is guaranteed that any/all mutations will be memory safe, if there is aliasing it takes more effort (including runtime checks) to ensure that mutations are safe.

Another is to use indicies for the outer loop:

for i in 0..points.len() {
    let mut movement = Quaternion::identity();
    for neighbour in &points {
        if neighbour.id == points[i].id {
            continue
        }
        // ...
        movement = movement * Quaternion::angle_axis(angle, axis);
    }

    points[i].movement = movement
}

A third method is to change how the loops work: when considering the interaction between a point and its neighbour, update both the point and the neighbour at the same time. This allows one to iterate "triangularly": point 0 interacts with 1..n, point 1 interacts with 2..n, ... (where n = points.len()). This can be done in a way that the compiler understands won't alias.

First one must reset all movements to 1. The main loops then consist of an outer loop that selects the single element, and then one can "reborrow" the iterator for the inner loop. The outer loop cannot use for, since for will take ownership of the iterator, fortunately, though, while let allows one to write this neatly:

for point in &mut points {
    point.movement = Quaternion::identity()
}
let mut iter = points.iter_mut();
while let Some(point) = iter.next() {
    // this reborrows the iterator by converting back to a slice
    // (with a shorter lifetime) which is coerced to an iterator 
    // by `for`. This then iterates over the elements after `point`
    for neighbour in &mut iter[..] {
        // `neighbour` is automatically distinct from `point`

        let angle = point.pos.angle(&neighbour.pos);
        let axis = point.pos.cross(&neighbour.pos);
        let force = -(1.0 / (angle*angle)) * update_amt;
        point.movement = point.movement * Quaternion::angle_axis(angle, axis);
        neighbour.movement = neighbour.movement * Quaternion::angle_axis(angle, -axis);
    }
}

NB. that I believe that axis must be reversed for the neighbour update. (I haven't compiled this, but hopefully it's close.)

Theoretically, the latter offers an approximately 2× speed-up vs. any of the other suggestions so far. At least, it reduces the number of calculations of angle, axis & force from n * (n - 1) to n * (n - 1) / 2.