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).
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.
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.
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:
