3 ms·
Not the author, and still new to Rust, but I think this approach is interesting in Rust as well. Consider visiting a tree: enum Tree { Branch(Box<T
by ridiculous_fish 6y ago
Not the author, and still new to Rust, but I think this approach is interesting in Rust as well.
Consider visiting a tree:
enum Tree {
Branch(Box<Tree>, Box<Tree>), // left, right
Leaf(i32)
}
fn postorder_visit(t: &mut Tree, f: fn(&mut Tree)) {
// ???
}
A recursive implementation of `postorder_visit` is trivial but risks stack overflow. A heap-allocated stack (say, `Vec<&mut Tree>`) runs into problems with the borrow checker, which knows about the C stack, but not your stack.
So an overflow-safe implementation must use unsafe, but still wants to have confidence in ordered destruction. You could make it a `Vec<*mut Tree>`, but now there are zero checks!
The idea here is, in debug mode only, replace `Box` with `Rc` that checks its refcount upon drop, and `&mut Tree` with Rc as well. Now your debug mode does not require unsafe, and your release mode is fast. You have dynamically enforced ownership in a regime inaccessible to the borrow checker.
- btschaegg 6y agoSince I'm still starting out with Rust, there's probably just something I'm missing here, but couldn't you easily solve that with `Cell<T>` or `RefCell<T>`?
- ridiculous_fish 6y agoI hope to see an expert answer to this question. In my lame attempt, Cell was too awkward and RefCell was also awkward with a side of runtime cost.
- deleted 6y ago[deleted]