Mutable tree with mutable DFS


#1

Hi,

I am writing a mutable tree and a depth first search function to mutate nodes. I wrote the following:

use std::cell::RefCell;
use std::rc::Rc;

#[derive(Default)]
pub struct MutableTreeNode {
    key: String,
    children: Vec<Rc<RefCell<MutableTreeNode>>>
}

impl MutableTreeNode {
    pub fn new() -> MutableTreeNode {
        ::std::default::Default::default()
    }
}

fn dfs(root: MutableTreeNode, cb: &Fn(Rc<RefCell<MutableTreeNode>>)) {
    let mut stack = Vec::<Rc<RefCell<MutableTreeNode>>>::new();

    // ignore root during this DFS; use children
    let root_children = root.children;
    for child in root_children {
        stack.push(child);
    }
    while !stack.is_empty() {
        let node = stack.pop().unwrap();
        cb(node);
        let node_mut = node.borrow_mut();
        let node_children = &node_mut.children;
        for child in node_children {
            stack.push(child);
        }
    }
}

I am getting the error for stack.push(child):

   = note: expected type `std::rc::Rc<std::cell::RefCell<MutableTreeNode>>`
              found type `&std::rc::Rc<std::cell::RefCell<MutableTreeNode>>`

My question is whether the type Vec<Rc<RefCell<MutableTreeNode>>> for children will allow for mutability during DFS and, if so, how I can address the error.

I am new to Rust. Thanks!


#2

To fix the error, change stack.push(child) to stack.push(child.clone()) – the clone in this case is just Rc::clone, which bumps the reference count.

edit: More generally, this approach should work, but it would be more efficient to avoid Rc altogether in favor of just having a stack of indices into the array; that way you wouldn’t need a separate heap allocation for each node.


#3

@comex To what array are you referring? The children field of MutableTreeNode?


#4

I believe @comex is referring to taking a memory pool-like approach. So you’d have something like this:

struct Tree<T> {
  nodes: Vec<TreeNode<T>>,
  head_index: Option<usize>,
}

struct TreeNode<T> {
  data: T,
  children_indices: Vec<usize>,
}

Then you’d access a node’s children by using the node’s indices.


#5

I see, this is an interesting approach. I might have to steal use it myself :slight_smile:


#6

The Rust compiler has to deal with this issue on a massive scale, so it’s used all over the place to both keep the borrow checker happy and manage the non-trivial object lifetimes. I’ve skimmed through my fair share of rustc source code in the past when trying to use it as a library and thought it was a cool solution.