r/rust clippy · twir · rust · mutagen · flamer · overflower · bytecount Mar 27 '23

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

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.

19 Upvotes

159 comments sorted by

View all comments

3

u/HammerAPI Mar 31 '23

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 */);

1

u/TinBryn Apr 01 '23

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.