Crate deep_safe_drop

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.

Is no_std and so can be used in constrained environments (e.g. without heap allocation).

Provides:

• deep_safe_drop function to be called from your Drop::drop implementations.

• DeepSafeDrop trait to be implemented by your types that use deep_safe_drop.

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.

Enums

ReplacedFirstChild

Result of DeepSafeDrop::replace_first_child_with_parent.

Traits

DeepSafeDrop

Implement this for your tree node type, with Link as your tree link type that dereferences to your node type.

Functions

deep_safe_drop

To be called from your Drop::drop implementations, to ensure that stack overflow is avoided.