How to deal with mutable self reference?

Says I need to do something with a recursive structure, with the code as follows:

// The original tree structure with self recursion
pub struct Node<T> {
    pub payload: T,
    pub children: Vec<Self>,
}

// The representation of `Node` inside `Forest`
pub struct Node1<T> {
    pub payload: T,
    pub children: Vec<usize>,
}

// The group of `Node1` with same property
pub struct NodeGroup<T> {
    pub nodes: Vec<Node1<T>>,
}

// A memoization table for `Node`s, to reuse the result
// of `Node`s with same property.
pub struct Forest<T> {
    pub groups: Vec<NodeGroup<T>>,
    pub root: Option<usize>,
    // Some states maintained in the root
    // ...
}

pub struct Algorithm<T> {
    pub forest: Forest<T>,
}

impl<T> Algorithm<T> {
    pub fn new() -> Self {
        Self {
            forest: Forest {
                groups: Vec::new(),
                root: None,
            },
        }
    }

    pub fn do_group(&mut self, group: &mut NodeGroup<T>) {
        for node in group.nodes.iter_mut() {
            self.do_node(node);
        }
    }

    pub fn do_node(&mut self, node: &mut Node1<T>) {
        for child in node.children.iter() {
            let group = &mut self.forest.groups[*child];
            self.do_group(group);
        }

        // Do something on node
    }
}

It will raise error as:

error[E0499]: cannot borrow `*self` as mutable more than once at a time
  --> src/main.rs:80:13
   |
79 |             let group = &mut self.forest.groups[*child];
   |                              ------------------ first mutable borrow occurs here
80 |             self.do_group(group);
   |             ^^^^^^^^^^^^^^-----^
   |             |             |
   |             |             first borrow later used here
   |             second mutable borrow occurs here

For more information about this error, try `rustc --explain E0499`.

This can be fixed easily with interior mutability, but I'm wondering if there is a more general way to solve the problem.

Think about what happens when you call rewrite_tree: it starts looping through self.tree.children, then calls rewrite_tree again on self. But self is the same, so self.tree.children is the same, so you loop again on the same Vec, and you get infinite recursion.

My guess is that you don't want a tree field, and instead you want to iterate through the tree argument given to rewrite_tree (in fact just removing self. from the for loop iterator makes it compiles fine).

This is actually a simplified version of code.

The actual Tree maintains a complex context in the root node, thus I have to keep it as a field of TreeRewriter, or pass it as an argument everywhere. Both of them cannot compile fine.

Another solution is to use a lightweight Pointer type to reference the nodes and apply the mutation with flattened Pointers, which will work but is not quite reasonable.

Either you made an error while simplifying, or your algorithm is flawed though, because this is actually unconditonal recursion. Rust Playground

Which tree? The one in the TreeRewriter or the one passed to rewrite?

Can't you separate the tree root from the children if you only care about its context?

I don't see why they can't compile though. It would be helpful to have an example that showed the actual problem. Surely however both of them at the same time can't compile.

Have edited the example above, hope will help.

The code of pass it as an argument everywhere is as follows:


fn do2<T>(forest: &mut Forest<T>) {
    do_group2(forest, &mut forest.groups[forest.root.unwrap()]);
}

fn do_group2<T>(forest: &mut Forest<T>, group: &mut NodeGroup<T>) {
    for node in group.nodes.iter_mut() {
        do_node2(forest, node);
    }
}

fn do_node2<T>(forest: &mut Forest<T>, node: &mut Node1<T>) {
    // Do something    
}

And the error:

error[E0499]: cannot borrow `*forest` as mutable more than once at a time
  --> src/main.rs:88:5
   |
88 |     do_group2(forest, &mut forest.groups[forest.root.unwrap()]);
   |     ---------^^^^^^^^^^^^^^-------------^^^^^^^^^^^^^^^^^^^^^^^
   |     |                      |
   |     |                      first mutable borrow occurs here
   |     second mutable borrow occurs here
   |     first borrow later used by call

error[E0499]: cannot borrow `forest.groups` as mutable more than once at a tim

I think the root cause is that you cannot mutably borrow both a structure and its field at the same time, which occurs a lot when using a self-referencing struct.

Looks like the fundamental problem here is that you're trying to iterate over elements of forest while also trying to mutate them, and this can't work. I can't think of a way to solve this in general, do you perhaps have some information on what you need when mutating node?

For example, inserting some Node1s to NodeGroup, generating some new NodeGroups and inserting them to Forest, modifying the internal state of iterated elements.

Then you surely can't hold a Node1 or NodeGroup while you're doing that, as mutating the Forest (actually, the forest.groups field) would invalidate them.

1 Like

This literally fucks the shit out of me. I've fixed this by cloning the stuff everywhere, which is a very bad workaround.

It seems I have to use Arc<Mutex> instead of this. :smiling_face_with_tear:

No, you'll need to re-think your design instead. If you work around borrow checking by introducing a Mutex within the same thread, you'll likely get all tangled up in control flow and it'll deadlock or panic. Mutating stuff while iterating through it is wrong, and you shouldn't be doing it.

Maybe you could design a two-pass algorithm instead, where you first collect the modifications and nodes in the order they should be applied/visited over an immutable structure, and then you would apply those modifications. For example:

pub enum ModificationKind {
    Insert,
    Delete,
    Mutate,
}

pub struct Modification {
    pub group_idx: usize,
    pub node_idx: usize,
    pub kind: ModificationKind,
}

impl<T> Algorithm<T> {
    pub fn do_group(&self, group_idx: usize) -> Vec<Modification> {
        let group = &self.forest.groups[group_idx];
        (0..group.nodes.len()).flat_map(|node_idx| self.do_node(group_idx, node_idx)).collect()
    }

    pub fn do_node(&self, group_idx: usize, node_idx: usize) -> Vec<Modification> {
        let node = &self.forest.groups[group_idx].nodes[node_idx];
        let mut modifications: Vec<_> = node.children
            .iter()
            .flat_map(|&child_idx| self.do_group(child_idx))
            .collect();

        // indicate that something needs to be done with `node`
        modifications.push(Modification {
            kind: ModificationKind::Delete,
            group_idx,
            node_idx,
        });
        
        modifications
    }
    
    pub fn apply(&mut self, modifications: &[Modification]) {
        // ...
    }
}
4 Likes

Thanks.

This is the solution I've mentioned above.

It works but, in my opinion, I may have a better choice with recursion rather than this.