0

I am trying to build a path from the root to leaf nodes in a tree-like data structure. The path is represented by an array (path) of mutable references to nodes:

fn build_path(&mut self, index: Index, shift: Shift) {
    debug_assert!(shift.0 >= BITS_PER_LEVEL);

    let mut path: [Option<&mut Node<T>>; MAX_HEIGHT] = new_path!();
    let mut path_i = 0;

    let mut node = self;
    let mut shift = shift;

    while shift.0 != BITS_PER_LEVEL {
        let cnode = node;

        let child = match *cnode {
            Node::Leaf { .. } => unreachable!(),
            Node::RelaxedBranch { .. } => unreachable!(),
            Node::Branch { ref mut children, len: _ } => {
                let i = index.child(shift);
                children[i].as_mut().unwrap()
            }
        };

        path[path_i] = Some(cnode);
        path_i = path_i + 1;

        node = Arc::make_mut(child);
        shift = shift.dec();
    }
}

The borrow-checker spits out a compilation error:

error[E0499]: cannot borrow `*cnode` as mutable more than once at a time
   --> src/main.rs:108:33
    |
102 | Node::Branch { ref mut children, len: _ } => {
    |                ---------------- first mutable borrow occurs here
...
108 | path[path_i] = Some(cnode);
    |                     ^^^^^ second mutable borrow occurs here
...
113 | }
    | - first borrow ends here

How should I approach this problem? I have tried various workarounds, but unfortunately none of them worked.

Edit #1

Here is a link to the rust playground with an executable code snippet: https://play.rust-lang.org/?gist=0e2a208a5fe5472229db30ac3d44c60d&version=nightly&mode=debug

Edit #2

I just to want to emphasize, that iterating over the data structure itself is not an issue. What I want to achieve is to have an array (see variable path in the build_path method) of mutable references to the nodes of a tree.

Araz Abishov
  • 1,661
  • 3
  • 15
  • 26
  • Please review how to create a [MCVE] and then [edit] your question to include it. We cannot tell what crates, types, traits, fields, etc. are present in the code. Ideally, produce something that reproduces your error on the [Rust Playground](https://play.rust-lang.org). Note that you can probably **remove** unneeded code from your question, *reducing* the problem to a very small test case. – Shepmaster Jun 10 '18 at 21:35
  • I believe your question is answered by the answers of [Cannot obtain a mutable reference when iterating a recursive structure: cannot borrow as mutable more than once at a time](https://stackoverflow.com/q/37986640/155423). If you disagree, please [edit] your question to explain the differences. Otherwise, we can mark this question as already answered. – Shepmaster Jun 10 '18 at 21:35
  • Recommended reading on this topic, in case you've not already stumbled across these: https://rust-leipzig.github.io/architecture/2016/12/20/idiomatic-trees-in-rust/ and http://smallcultfollowing.com/babysteps/blog/2015/04/06/modeling-graphs-in-rust-using-vector-indices/ – Joe Clay Jun 11 '18 at 08:17
  • Thanks a lot for replies. @Shepmaster Valid points, I have updated my question with a simplified example and created a gist on rust playground. The question you have linked involves only iteration over recursive data structure, but doesn't consider building a data structure (array) consisting of visited nodes. That's exactly where I am facing issues. If you comment out lines 108 and 109 in the playground sample, borrow-checker will be happy, but that's what I actually need to solve. – Araz Abishov Jun 11 '18 at 18:17
  • I just to want to emphasize, that iterating over data structure is *not* an issue. I am following similar approach as in the accepted answer to the question @Shepmaster has linked. Building an array of visited nodes *while* iterating over data structure, that's where the problem lies. – Araz Abishov Jun 11 '18 at 18:26
  • @ArazAbishov *Questions seeking debugging help ("why isn't this code working?") must include the desired behavior, a specific problem or error and **the shortest code** necessary to reproduce it **in the question itself**.* — If you don't care to put the effort in to create this [MCVE], then this question is off-topic for Stack Overflow. – Shepmaster Jun 11 '18 at 22:13
  • I believe your question is answered by the answers of [Is there a way to iterate over a mutable tree to get a random node?](https://stackoverflow.com/q/49057270/155423). If you disagree, please [edit] your question to explain the differences. Otherwise, we can mark this question as already answered. – Shepmaster Jun 11 '18 at 22:50
  • @Shepmaster I have updated the question again to include more details. I have taken a look into the question you have linked, and it seems that the answer is that in a tree like data structure you can't have a mutable iter (or a collection of mutable references). I will try to investigate this further, but I still don't have a firm answer to my own problem. Thanks. – Araz Abishov Jun 13 '18 at 08:43
  • 1
    You cannot achieve this without unsafe code or internal mutability. – Sebastian Redl Jun 13 '18 at 08:57
  • 2
    A more accurate way to put it might be that you can't have a collection of mutable references to *overlapping subtrees*. With internal mutability (`RefCell`), simultaneous mutable references to distinct nodes would be fine and safe. – trent Jun 13 '18 at 10:55
  • @trentcl Thanks a bunch! The point regarding overlapping subtrees makes so much sense now. I will try to experiment with RefCell and report back if it works. – Araz Abishov Jun 13 '18 at 11:05
  • 1
    If you are able to get it working (and you agree that this question is a duplicate of the other one), please consider writing an answer to the other question using `RefCell`! Keeping related answers together may help future readers who have similar questions. – trent Jun 13 '18 at 11:42

0 Answers0