How do I avoid double borrow in this loop in a loop?

I am coming back to rust after a long hiatus, and I want to convert some code I wrote in another language into rust. But the borrow checker is not happy with my attempt.

I have tried to reduce this code sample to the minimum to demonstrate my problem

struct Node2{
    value: f64,
    is_active: bool,
    has_active_inputs: bool,
    input_connection_ids: Vec<usize>,
    active_sum: f64,
}

struct Connection2 {
    in_node_id: usize,
    out_node_id: usize,
    weight: f64,
    enabled: bool
}

struct Network2 {
    genome: Vec<Connection2>,
    nodes: Vec<Node2>,
}

impl Network2 {
    fn activation_pulse(mut self) -> Network2 {
        for node in self.nodes.iter_mut() {
            node.has_active_inputs = false;
            node.active_sum = 0.;

            for i_conn in &node.input_connection_ids {
                let conn = &self.genome[*i_conn];
                let in_node = &self.nodes[conn.in_node_id];
                if in_node.is_active && conn.enabled {
                    let to_add = conn.weight * in_node.value;
                    node.has_active_inputs = true;
                    node.active_sum += to_add;
                }
            }
        }

        self
    }
}

Compiler complains that self.nodes is borrowed twice.
What is the "rust" way of doing this? I would prefer to avoid any copying if I can.

I’m not claiming this is “the rust way” or particularly beautiful… just the first thing I had working, and with the added benefit of at least not turning the inner for loop into a loop over indices:


impl Network2 {
    fn activation_pulse(mut self) -> Network2 {
        let nodes = &mut self.nodes[..];
        for i in 0..nodes.len() {
            let Node2 {
                ref mut has_active_inputs,
                ref mut active_sum,
                ref input_connection_ids,
                ..
            } = nodes[i];
            *has_active_inputs = false;
            *active_sum = 0.;

            for i_conn in input_connection_ids {
                let conn = &self.genome[*i_conn];
                let Node2 {
                    is_active: in_node_is_active,
                    value: in_node_value,
                    ..
                } = nodes[conn.in_node_id];
                if in_node_is_active && conn.enabled {
                    let to_add = conn.weight * in_node_value;
                    *has_active_inputs = true;
                    *active_sum += to_add;
                }
            }
        }

        self
    }
}

Edit: At the (hopefully properly optimized out) cost of duplicating some indexing operations, perhaps this is a bit nicer

impl Network2 {
    fn activation_pulse(mut self) -> Network2 {
        let nodes = &mut self.nodes[..];
        for i in 0..nodes.len() {
            nodes[i].has_active_inputs = false;
            nodes[i].active_sum = 0.;

            for i_conn in &nodes[i].input_connection_ids {
                let conn = &self.genome[*i_conn];
                let in_node = conn.in_node_id;
                if nodes[in_node].is_active && conn.enabled {
                    let to_add = conn.weight * nodes[in_node].value;
                    nodes[i].has_active_inputs = true;
                    nodes[i].active_sum += to_add;
                }
            }
        }

        self
    }
}
1 Like

I didn't know you could unpack a struct like that, cool!
I don't think I fully understand why this works, but my code doesn't.
At a guess, you never actually borrow a node, or a vector of nodes, just get references to the internal fields?
I will have to meditate on this for a bit.

The magical detail about this code is that rustc can track that distinct fields are borrowed if you borrow from the result of indexing into a slice in particular.

E.g.

fn test(mut x: Vec<(i32, i32)>, i: usize, j: usize) {
    let x_slice = &mut x[..];

    // i and j may even be the same, but this works

    let a: &mut i32 = &mut x_slice[i].0;
    let b: &mut i32 = &mut x_slice[j].1;

    // use both a and b together
    println!("{:?} {:?}", a, b);
}

But this ability of the compiler breaks quickly and in many ways.

Using indexing into the Vec directly which uses the trait-based IndexMut implementation for Vec<T> instead of built-in indexing operator for slices:

fn test(mut x: Vec<(i32, i32)>, i: usize, j: usize) {

    let a: &mut i32 = &mut x[i].0;
    let b: &mut i32 = &mut x[j].1;

    // use both a and b together
    println!("{:?} {:?}", a, b);
}
error[E0499]: cannot borrow `x` as mutable more than once at a time
 --> src/lib.rs:4:28
  |
3 |     let a: &mut i32 = &mut x[i].0;
  |                            - first mutable borrow occurs here
4 |     let b: &mut i32 = &mut x[j].1;
  |                            ^ second mutable borrow occurs here
...
7 |     println!("{:?} {:?}", a, b);
  |                           - first borrow later used here

Or creating an intermediate reference to the whole item [or the whole slice] (e.g. by not using built-in indexing but get_mut):

fn test(mut x: Vec<(i32, i32)>, i: usize, j: usize) {
    let x_slice = &mut x[..];

    // i and j may even be the same, but this works

    let a: &mut i32 = &mut x_slice.get_mut(i).unwrap().0;
    let b: &mut i32 = &mut x_slice[j].1;

    // use both a and b together
    println!("{:?} {:?}", a, b);
}
error[E0499]: cannot borrow `x_slice[_].1` as mutable more than once at a time
  --> src/lib.rs:7:23
   |
6  |     let a: &mut i32 = &mut x_slice.get_mut(i).unwrap().0;
   |                            ------- first mutable borrow occurs here
7  |     let b: &mut i32 = &mut x_slice[j].1;
   |                       ^^^^^^^^^^^^^^^^^ second mutable borrow occurs here
...
10 |     println!("{:?} {:?}", a, b);
   |                           - first borrow later used here

error[E0503]: cannot use `*x_slice` because it was mutably borrowed
  --> src/lib.rs:7:28
   |
6  |     let a: &mut i32 = &mut x_slice.get_mut(i).unwrap().0;
   |                            ------- `*x_slice` is borrowed here
7  |     let b: &mut i32 = &mut x_slice[j].1;
   |                            ^^^^^^^^^^ use of borrowed `*x_slice`
...
10 |     println!("{:?} {:?}", a, b);
   |                           - borrow later used here

4 Likes

Of course if this is done, then it’s all quite simple: Replace node with some node_ix and i_conn with some i_conn_ix, then indexing and double-indexing everywhere where a new access to nodes is in conflict with previous ones, and it unsurprisingly works because everything that’s ever kept around are the indices.


impl Network2 {
    fn activation_pulse(mut self) -> Network2 {
        for node_ix in 0..self.nodes.len() {
            let node = &mut self.nodes[node_ix];
            node.has_active_inputs = false;
            node.active_sum = 0.;

            for i_conn_ix in 0..node.input_connection_ids.len() {
                let conn = &self.genome[self.nodes[node_ix].input_connection_ids[i_conn_ix]];
                let in_node = &self.nodes[conn.in_node_id];
                if in_node.is_active && conn.enabled {
                    let to_add = conn.weight * in_node.value;
                    let node = &mut self.nodes[node_ix];
                    node.has_active_inputs = true;
                    node.active_sum += to_add;
                }
            }
        }

        self
    }
}
2 Likes

This is very helpful, thanks!

I did some experimenting and even this is not allowed

fn test(mut x: Vec<(i32, i32)>, i: usize, j: usize) {
    let x_slice = &mut x[..];
    
    let a: &mut i32 = &mut x_slice[i].0;
    let b: &mut i32 = &mut x_slice[j].0;

    // use both a and b together
    println!("{:?} {:?}", a, b);
}

presumably because i and j might be the same index and thus the borrows of the first element of the tuple could be a double borrow.

Good observation. I didn’t call out this case because that registered in my mind as an “obviously problematic” case, i.e. there’s true potential for creating aliasing &mut i32 references this way. In the direction of “how’d I do this though if I knew the two indices were distinct” there’s some very convenient unstable APIs we’ll eventially have in the form of “get_many_mut”. (There’s also existing, less convenient, but still safe ways to do this by splitting the slice.)

Why is it neccesary to say let node = &mut self.nodes[node_ix]; twice?

It’s the other conflicting accesses to self.nodes. Let me mark them all


impl Network2 {
    fn activation_pulse(mut self) -> Network2 {
        for node_ix in 0..self.nodes.len() {
            let node = &mut self.nodes[node_ix]; // here (node_ix)
            node.has_active_inputs = false;
            node.active_sum = 0.;

            for i_conn_ix in 0..node.input_connection_ids.len() {
                let conn = &self.genome[self.nodes[node_ix].input_connection_ids[i_conn_ix]];  // here (node_ix)
                let in_node = &self.nodes[conn.in_node_id]; // here (conn.in_node_id)
                if in_node.is_active && conn.enabled {
                    let to_add = conn.weight * in_node.value;
                    let node = &mut self.nodes[node_ix]; // here (node_ix)
                    node.has_active_inputs = true;
                    node.active_sum += to_add;
                }
            }
        }

        self
    }
}

The second let node = &mut self.nodes[node_ix] is at a point in the code that follows the access to self.nodes[conn.in_node_id], so it needs to be a new indexing operation and cannot re-use the previous one. (Under the assumption that we aren’t ising the disjoint-fields kind of reasoning my previous code examples had used.)


Looking at this, the second indexing at

let conn = &self.genome[self.nodes[node_ix].input_connection_ids[i_conn_ix]];

seems redundant though, as it always follows previous accesses to nodes(node_ix). We can get rid of that technically (although it doesn’t make the code nicer) by restructuring as follows:

impl Network2 {
    fn activation_pulse(mut self) -> Network2 {
        for node_ix in 0..self.nodes.len() {
            let mut node = &mut self.nodes[node_ix]; // here (node_ix)
            node.has_active_inputs = false;
            node.active_sum = 0.;

            for i_conn_ix in 0..node.input_connection_ids.len() {
                let conn = &self.genome[node.input_connection_ids[i_conn_ix]];
                let in_node = &self.nodes[conn.in_node_id]; // here (conn.in_node_id)
                if in_node.is_active && conn.enabled {
                    let to_add = conn.weight * in_node.value;
                    node = &mut self.nodes[node_ix]; // here (node_ix)
                    node.has_active_inputs = true;
                    node.active_sum += to_add;
                } else {
                    node = &mut self.nodes[node_ix]; // here (node_ix)
                }
            }
        }

        self
    }
}

Why do you need the outer loop? In the example you show, you only need to iterate the connections vector, look up and modify the downsteam nodes.

If you have more operations on the downstream node, you can iterate over them after the first loop.

impl Network2 {
    fn activation_pulse(mut self) -> Network2 {
		for conn in self.genome.iter() {
			let in_node = &self.nodes[conn.in_node_id]; // here (conn.in_node_id)
			if in_node.is_active && conn.enabled {
				let to_add = conn.weight * in_node.value;
				let out_node = &mut self.nodes[node_ix]; // here (node_ix)
				out_node.has_active_inputs = true;
				out_node.active_sum += to_add;
			}
		}
        self
    }
}

Or, if it has to be activated after inputs (if you model electric network), then maybe its more reasonable to iterate over the network like in Dijkstra algorithm (or breadth-first search), keeping a queue (simple vector) of nodes to process. Except in your case it's better to keep outgoing connections ids rather than incoming:

struct Node2{
    value: f64,
    is_active: bool,
    has_active_inputs: bool,
    output_connections: Vec<usize>,
    active_sum: f64,
}

Example code, assuming nodes turn on if incoming value is greater than some threshold.

	fn activation_pulse(mut self) -> Network2 {
		// (to_id, delta)
		let mut q: Vec<(usize, f64)> = vec![];
		for node in self.nodes.iter().filter(|n| n.is_active) {
			for c_id in node.output_connections.iter() {
				let con = &self.genome[*c_id];
				if !con.enabled { continue; }
				let delta = node.active_sum * con.weight;
				if delta >= DELTA_THRESHOLD { q.push((con.out_node_id, delta)); }
			}
		}

		while let Some((to_id, in_delta)) = q.pop() {
			let node = &mut self.nodes[to_id];
			node.active_sum += in_delta;

			// if the logic is to turn on node depending on the input:
			if node.active_sum > ACTIVITY_THRESHOLD { node.is_active = true; }
			if !node.is_active { continue; }

			for con_id in node.output_connections.iter() {
				let con = &self.genome[*con_id];
				if !con.enabled { continue; }
				let out_delta = in_delta * con.weight;
				if out_delta > DELTA_THRESHOLD { q.push((con.in_node_id, out_delta)); }
			}
		}
        self
    }

This can create an infinite loop, but if con.weight < 1 and DELTA_THRESHOLD > 0.0, this will eventually die out.

I actually have no idea why I have it as a nested loop. It might be a hold over from when I had a completely different structure.
I have since changed it to a single loop. Thanks!

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.