Borrow conflict in tree data structure

I'm trying to implement a form of mark-and-sweep iteration over an explicitly managed tree, and am running into an issue where the compiler flags my code as illegal because of conflicting borrowing:

use std::collections::*;
struct TreeNode {
    children: Vec<usize>,
    mark: bool,
    // further data elided
}
struct Tree {
    nodes: Vec<TreeNode>,
    marked: VecDeque<usize>,
}

impl Tree {
    pub fn process_marked(&mut self) {
        while let Some(current_node) = self.marked.pop_front() {
            // Do some processing (elided)
            // Mark self as done
            self.nodes[current_node].mark = false;
            // Mark children as needing work
            for child in &self.nodes[current_node].children {
                if !self.nodes[*child].mark {
                    self.nodes[*child].mark = true;
                    self.marked.push_back(*child);
                }
            }
        }
    }
}

To the best of my understanding, the assignment within the loop is safe, since we're not modifying a children array of a node. However, I am not sure how to tell the compiler this, and since it only sees that I am modifying a node, and that we also have an immutable reference to nodes live at this point, it simply says no. Any suggestions on how to work around this (preferably without touching unsafe)

Since slice-indexing is a primitive operation, you can use this approach to make the code work:

pub fn process_marked(&mut self) {
    while let Some(current_node) = self.marked.pop_front() {
        // Do some processing (elided)
        // Mark self as done
        self.nodes[current_node].mark = false;
        // Mark children as needing work
        let nodes = self.nodes.as_mut_slice();
        for child in &nodes[current_node].children {
            if !nodes[*child].mark {
                nodes[*child].mark = true;
                self.marked.push_back(*child);
            }
        }
    }
}

Here, nodes is a “&mut [TreeNode]”, and the compiler is allowing you to produce (even mutable) references to nodes[…].mark and nodes[…].children without conflict. Indexing Vec on the other hand works through the IndexMut trait, which makes the compiler more conservative/strict, in that it’s assuming that the code implementing the indexing itself could access the mark or children fields of any of the values.

1 Like

Thank you, that did the trick. Is there a good reference to learn more about how the borrow checker works in these sort of situations? I have run into issues like this more often and although I usually have a guess for a solution, I would love to really understand what the compiler is doing and how I can work with that better.

I’m not aware of any reference explaining this behavior in particular. I do remember trying out different kinds of partial re-borrows myself at some point in time; and AFAICT that’s what gave me the suspicion that this approach might work here.

Before remembering this kind of compiler-support, I did think about the fact that splitting the mutable borrow of the whole Vec<TreeNode> into a borrow of all the children fields on the one hand, and of all the mark fields on the other hand, should be possible to encapsulate in a safe API (using unsafe code and raw pointers internally). Before that, I thought about whether to suggest the possibility to split up the Vec<TreeNode> into two vecs, one containing all the mark fields, and another containing TreeNodes without the struct having any mark field.

Before that, I thought about suggesting an approach using split_at_mut to split the slice into a part before current_node and a part after current_node and using index calculations to still access the right elements; or alternatively an approach involving temporarily mem::takeing the children vec out of the node, iterating over it, and finally placing it back; or an approach involving using Cell<bool> or AtomicBool for the mark field.

I guess – besides the fact that a list of alternatives is interesting in and by itself – my main point here is, the trick I suggested here is by no means the first thing I thought of.

2 Likes

Works in 1.0.0 even.

I guess it's alluded to here, but not expanded upon. Mentioned in a few bugs like this one.

1 Like

Something else just reminded me, Box has a similar undocumented (AFAIK) ability:

pub struct Darn<T>(T);
impl<T> Deref for Darn<T> { /* ... */ }
impl<T> DerefMut for Darn<T> { /* ... */ }

// Compiles
fn example1(mut smaht: Box<Pair>) {
    let a = &mut smaht.a;
    let b = &mut smaht.b;
    println!("{} {}", a, b);
}

// Errors
fn example2(mut darn: Darn<Pair>) {
    let a = &mut darn.a;
    let b = &mut darn.b;
    println!("{} {}", a, b);
}

It was removed by RFC 130 and then re-added as part of NLL.