Safe dropping of deep trees that otherwise could cause stack overflow.
Does not require any allocation and reuses existing space of a tree to enable working back up a tree branch, instead of the stack.
no_std and so can be used in constrained environments (e.g. without
deep_safe_dropfunction to be called from your
DeepSafeDroptrait to be implemented by your types that use
Stack overflow is avoided by mutating a tree to become a leaf, i.e. no longer have any children, before the compiler does its automatic recursive dropping of fields. Instead of using recursive function calls (i.e. recording the continuations on the limited stack) to enable working back up a tree branch (as the compiler's dropping does, which is what could otherwise cause stack overflows), we reuse a link of each node to record which parent node must be worked back up to. Thus, we are guaranteed to already have the amount of space needed for our "continuations", no matter how extremely deep it may need to be, and it is OK to reuse this space because the links it previously contained are already being dropped anyway.
See the included tests for some examples.
Implement this for your tree node type, with
To be called from your