It's been a couple years since I tried Advent of Code in Rust, and last time all the problems naturally suited to tree-based solutions kicked my butt so I thought I'd try again and see whether I'd learned how to better use Rc and RefCell.
I'm on 2022 Day 7, in which we simulate a filesystem browser. In my initial testing however, I've written a weird bug -- I try to change directory with fn cd(from: &mut Rc<RefCell<Self>>, dir: impl AsRef<str>), and during that function call one of the child nodes loses its parent. I think this may be due to something about upgrading a Weak causing something to drop? Or perhaps the *from = Rc::clone(d) (84) is the problem?
The failing test is at line 277, and I think the problematic code is around line 79: Rust Playground
I know the code is really rough, I plan to go back and lint and refactor once I can figure out why this test won't pass.
If anyone has time to take a look I would sure appreciate it, because I've been staring at this on and off for weeks and am spinning my wheels at this point. I'm trying to stick with std for now, and I plan to try the arena-style approach next, but wanted to start with Rc. Thanks for any pointers, and especially if there's an obvious concept that I seem to have misunderstood!
This is a link to an unpopulated playground; you need to use the "Share" tab to generate a permalink.
This seems plausible. When you do this store, the original Rc will be dropped; if it was the last strong reference then its contents will be dropped immediately, breaking corresponding Weaks.
In this playground, you're never trying to read parent; the error occurs because you try to descend into a child of a leaf node.
It's worth noting, however, that line 46 (let mut node = grandparent) moves out of the grandparent variable, so that the only strong reference to the root node is stored in node. When change_to_child then replaces the value of node with a clone of parent, there are no more strong references to the root and it is dropped.
Initially, gp has a strong count of 1 (main::node) and parent has a strong count of 2 (main::parent, main::node.children[0])
node is then pointed at parent, which causes gp to be dropped due to a strong count of 0.
The next log statement shows parent with a strong count of 2 (main::node, main::parent)
node is pointed at child; parent is not dropped because it is still reachable through main::parent
The final log statement shows child with a valid parent pointer (strong count 1)
change_to_child() returns an error b/c there is no child to descend into
main prepares for returning by dropping its local variables, reducing the strong counts of parent and child to zero and dropping them.
main returns with an error
The debug value of main's error return is printed.
In summary, if you're going to use a tree structure with Weak backlinks, you need to take special care to keep a strong reference to the root somewhere or else risk the subtrees becoming orphaned during traversal.
Clearly more coffee required, that was wrong playground link (that was one I made from scratch in trying to recreate the issue). Interestingly, the playground link that you commented on does not display the surprising behavior that prompted this post, which is why I escalated to posting about it. Strike two, quite embarrassing, I'm sorry.
The correct and verified playground link with the failing test in question (now added above as well) is: Rust Playground
Thanks for your instructional and thorough post -- I think the lessons you've taught me apply to the problem well and will likely point me towards the issue!
Yeah; it's the same basic issue— You're not keeping a strong reference to the root of your virtual file system. If you change line 270 to this, the test passes:
After reading your post I figured this out independently (making an identical change) and was racing to post this in triumph and gratitude, but you beat me to it Thank you.
correct one: Rust Playground
Thank you.