Cannot Borrow twice, looking for workaround

Question

My code represents a graph in a vector. Each element in the vector (I dubbed it Node) has a vector of "parents" within the same graph. And it computes its output value with memoization, when needed, by asking its parents to calculate theirs and then aggregating the values.

I consider this a "legal" use case where the Borrow checker gets in the way. If the vector represents a valid, acyclic graph, there is no reason, not to implement it as I do.

struct Node {
    parents: Vec<usize>,
    output: Option<i8>
}

type Cluster = Vec<Node>;

impl Node {
    fn new(ps:&[usize]) -> Self {
        Node {
            parents: ps.to_vec(),
            output: None
        }
    }
    fn calc(&mut self,cluster: &mut Cluster) -> i8 {
        match self.output {
            Some(out) => out,
            None => {
                let mut acc: i32 = 0;
                for parent_index in &self.parents {
                    acc += (cluster[*parent_index].calc(cluster)) as i32;
                }
                let out = (acc / self.parents.len() as i32) as i8;
                self.output = Some(out);
                out
            }
        }
    }
    fn reset(&mut self) {
        self.output = None;
    }
    fn set(&mut self, value: i8) {
        self.output = Some(value);
    }
}

fn main() {
    //                         input 0           input 1        hidden 0          output 0
    let mut c: Cluster = vec![Node::new(&[]), Node::new(&[]), Node::new(&[0,1]), Node::new(&[2])];
    c[0].set(42);
    c[1].set(11);
    let result = c[3].calc(&mut c);
    println!("result = {}", result);
}

error[E0499]: cannot borrow *cluster as mutable more than once at a time

Of course, the code above is just the minimal reproducable show case of my problem. So, any ideas, how I can teach the Rust bear this new trick?

score 3 · Accepted Answer · answered Sep 08 '22 at 14:38

I consider this a "legal" use case where the Borrow checker gets in the way. If the vector represents a valid, acyclic graph, there is no reason, not to implement it as I do.

Mutable aliasing is never considered legal in Rust. The main problem comes from the signature of calc.

fn calc(&mut self: &mut Node, cluster: &mut Cluster) -> i8

A method taking a mutable borrow for a node as well as a mutable borrow to the cluster containing that node violates the aliasing rule. Rust requires these borrows to be exclusive, as it may take advantage of that exclusivity when manipulating these values.

In any case, the way to decompose this problem is to get to the largest common denominator and have the function borrow only that value once. In this case, we can rewrite calc as a function which receives a mutable borrow of the cluster and a node index.

fn calc(cluster: &mut Cluster, node_index: usize) -> i8 {
    match cluster[node_index].output {
        Some(out) => out,
        None => {
            let mut acc: i32 = 0;
            let parents = cluster[node_index].parents.clone(); // ¹
            for parent_index in &parents {
                acc += (calc(cluster, *parent_index)) as i32;
            }
            let out = (acc / parents.len() as i32) as i8;
            cluster[node_index].output = Some(out);
            out
        }
    }
}

The main function becomes:

let mut c: Cluster = vec![
    // input 0
    Node::new(&[]),
    // input 1
    Node::new(&[]),
    // hidden 0
    Node::new(&[0, 1]),
    // output 0
    Node::new(&[2]),
];
c[0].set(42);
c[1].set(11);
let result = calc(&mut c, 3);
println!("result = {}", result);

Playground

¹ This implementation requires making a copy of the parent indices, since they were also borrowed alongside the rest of the values. Further decomposition of these structs to only mutably borrow what you need to modify in the function may help to avoid this copy.

Cannot Borrow twice, looking for workaround

1 Answers1