Crate deep_safe_drop
source ·Expand description
§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 call-stack.
No unsafe
code.
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 yourDrop::drop
implementations. -
DeepSafeDrop
trait to be implemented by your node types that usedeep_safe_drop
. -
Link
trait to be implemented by your link types involved inDeepSafeDrop
.
Stack overflow is avoided by mutating a tree to become a leaf, i.e. no longer have any children, doing the same mutation to children recursively but iteratively, dropping leaf nodes as they’re encountered, mutating children to become leafs, before the implicit compiler-added dropping does its automatic final dropping of fields via recursive calls, so that all nodes, including the root, have become a leaf by the time it does for each, and thereby recursive calls to that final dropping are not done.
Instead of using recursive function calls (i.e. recording the continuations on the limited call-stack) to enable working back up a tree branch to traverse to other branches (as the compiler-added final 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.
A simple example of the mutation steps (nodes are dropped when removed as leafs):
Initial: Step 1: Step 2: Step 3:
a a a a
⭨ ⭦ ⭦
b b b
⭩ ⭨ ⭧ ⭨ ⭨
c d c d d
⭩ ⭨ ⭨
e f f
Note: Initially, a
links to b
and b
links to c
, but, at Step 1 and after, c
links to b
and b
links to a
. This is the reuse of a node’s link space to save the parent for later
traversing back “up” to it, which enables transitioning to Steps 2 & 3. All steps are
transitioned to via a loop in the same single function call, by moving cursors down and “up” a
tree.
See the tests for some examples of incorporating for different types and different shapes.
Enums§
- Result of
DeepSafeDrop::set_parent_at_index_0
.
Traits§
- Implement this for your tree node type, with
Link
as your tree link type that references or is your node type. - Implement this for your tree link type, with
Node
as your tree node type.
Functions§
- To be called from your
Drop::drop
implementations, to ensure that stack overflow is avoided.