Drop on Node should not be recursive

[apoelstra]

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 on Node. This should be manually implemented as something that uses a post-order iterator to replace each node with Inner::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.

[uncomputable]

Does that mean that dropping a deeply nested node can result in a stack overflow, as of now?

[apoelstra]

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.

[uncomputable]

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?

[apoelstra]

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.