Open apoelstra opened 1 month ago
Does that mean that dropping a deeply nested node can result in a stack overflow, as of now?
Yep. It's not too hard to write a test case -- you can construct a take(take(take(...(unit)...)))
iteratively then do nothing with it but drop, and it'll blow out the stack inside the drop glue for Arc
.
Ok, wow. I thought that Drop
cannot stack-overflow because it is implemented in an iterative manner. Then I thought about that algorithm and I realized that it cannot be done in valid Rust. Every type has a distinct implementation of Drop
so the generic algorithm that works for all types has to be recursive, it seems. We can avoid recursion by manually implementing Drop
for a specific type. Is that correct?
Yes. To avoid recursion you need to manually implement Drop
in a way that you iterative drop its children leaving the original object "disabled" in some way (e.g. replacing it with a unit node using mem::replace) that the recursive drop logic will then be trivial.
We've done a great job eliminating recursion throughout the library, aside from in the typechecker. One subtle place is in the default
Drop
impl onNode
. This should be manually implemented as something that uses a post-order iterator to replace each node withInner::Unit
, iteratively dropping the original.I took a crack at this and couldn't figure it out after ten minutes but it's definitely possible.