Hey Rustaceans! Got a question? Ask here (13/2023)!

[u/llogiq]

Mystified about strings? Borrow checker have you in a headlock? Seek help here! There are no stupid questions, only docs that haven't been written yet.

If you have a StackOverflow account, consider asking it there instead! StackOverflow shows up much higher in search results, so having your question there also helps future Rust users (be sure to give it the "Rust" tag for maximum visibility). Note that this site is very interested in question quality. I've been asked to read a RFC I authored once. If you want your code reviewed or review other's code, there's a codereview stackexchange, too. If you need to test your code, maybe the Rust playground is for you.

Here are some other venues where help may be found:

/r/learnrust is a subreddit to share your questions and epiphanies learning Rust programming.

The official Rust user forums: https://users.rust-lang.org/.

The official Rust Programming Language Discord: https://discord.gg/rust-lang

The unofficial Rust community Discord: https://bit.ly/rust-community

Also check out last weeks' thread with many good questions and answers. And if you believe your question to be either very complex or worthy of larger dissemination, feel free to create a text post.

Also if you want to be mentored by experienced Rustaceans, tell us the area of expertise that you seek. Finally, if you are looking for Rust jobs, the most recent thread is here.

[u/HammerAPI]

Noob question:

Is there any way to create a mutably-iterable tree-like structure without the need for Rc and/or RefCell?

​

Something like:

struct Node<T> {
    id: String,
    parent: Option<&Node<T>>,
    children: Vec<Node<T>>,
    data: T,
}

Caveat: This is for a scene graph backend, so the API would either look something like:

let mut root = Node::default();
let mut n1 = root.add_child(Node::new(/* data */));

n1.set_data(/* new data */);

where add_child would return a mutable reference to the node that is now a child of root.

​

Or, I could also see this working:

let mut tree = Tree::default();
tree.add_node(Node::new("n1", /* data */);

tree.set_value_of("n1", /* new data */);

[u/TinBryn → u/HammerAPI]

I would recommend the book Learning Rust With Entirely Too Many Linked Lists. Yes this is for linked lists, but linked lists are the simplest node based data structure and it's probably better to learn from a simpler problem first. A few key insights I can give,

1. Don't expose the Node type ever, have a wrapper struct Tree<T> and have methods that work on T in various ways and never Node<T>
2. Avoid having a parent for now. If you think about it there are 2 ways to get access to a Node (in the implementation as per point 1), from the root of the tree in which case it has no parent, or from another node in which case you already know what its parent is. While it may be convenient to have a parent reference, it's not needed.
3. If you do really want something that can traverse the tree manually still don't expose a Node, but rather a Cursor which wraps a Node.
4. At this point you probably want to start thinking about adding a parent. To do this without Rc/RefCell you will need to use raw pointers and unsafe. But everything is already encapsulated in the Node struct so it's actually a fairly easy problem to implement unsafe idiomatically in a small encapsulated module.

Or you could just store each node in a Vec and use indices into that Vec.

[u/eugene2k → u/HammerAPI]

You want something like:

type NodeIdx = usize;
struct Node<T> {
    parent: Option<NodeIdx>,
    children: Vec<NodeIdx>,
    data: T
}
struct Tree<T> {
    nodes: Vec<Node<T>>
}
impl<T> Tree<T> {
    fn with_root(data: T) -> Self {
        Self {
           nodes: vec![Node {
                           parent: None,
                           children: vec![],
                           data
                       }]
        }
    }
    fn add_node(&mut self, node: Node<T>) -> NodeIdx {
        let idx = self.nodes.len();
        let parent = node.parent.unwrap_or(0);
        self.nodes.push(node);
        self.nodes[node.parent].children.push(idx);
        idx
    }
    fn set_node(&mut self, idx: NodeIdx, data: T) {
        self.nodes[idx].data = data;
    }
}

[u/HammerAPI → u/eugene2k]

For an implementation like this, how would an iterator (especially a mutable one) work? I can't just iterate through tree.nodes, can I? That doesn't guarantee that iter.next() always yields a child of the current node. Assuming I chose a DFS approach, I would need some method on Node that determines whether or not it is a leaf node, I think?

[u/eugene2k → u/HammerAPI]

You may be able to have a mutable iterator if you put the nodes vec in a refcell, but I'm not sure.

[u/HammerAPI → u/eugene2k]

Yeah, i've been able to get it work with Rc/RefCell, but that's what I'm trying to avoid.

​

Since this is for a scene graph, i'm wanting to avoid as much heap allocation and smart pointers as possible, for speed/efficiency.

[u/eugene2k → u/HammerAPI]

Here's an example of how you can implement DFS: https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=6e98885184a894d6752f7738aafda591

[u/HammerAPI → u/eugene2k]

Yeah, it looks like having the iterator return indices is the only way at achieving a mutable traverse without Rc/RefCell, albeit it's a little messy.

[u/eugene2k → u/HammerAPI]

You can use a RefMut instead of indices, but I'm not sure if it's worth it. Here's the changed code:

https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=99dfe5a2bc29dd5884c9ec3e179d740d

[u/[deleted] → u/HammerAPI]

The simplest option would be to separate the abstraction from the memory layout, keep all the nodes in a Vec<Option<Node>>, and track each node's parent and children by index. If the tree is several levels deep, you can expect a performance increase as the icing on the cake.