1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236
//! 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. #![no_std] #![forbid(unsafe_code)] // Warn about desired lints that would otherwise be allowed by default. #![warn( // Groups future_incompatible, nonstandard_style, rust_2018_compatibility, // unsure if needed with edition="2018" rust_2018_idioms, unused, clippy::all, clippy::pedantic, clippy::restriction, // Individual lints not included in above groups and desired. macro_use_extern_crate, missing_copy_implementations, missing_debug_implementations, missing_docs, // missing_doc_code_examples, // maybe someday private_doc_tests, single_use_lifetimes, // annoying hits on invisible derived impls trivial_casts, trivial_numeric_casts, // unreachable_pub, unused_import_braces, unused_lifetimes, unused_qualifications, unused_results, variant_size_differences, )] // Exclude (re-allow) undesired lints included in above groups. #![allow( // explicit_outlives_requirements, // annoying hits on invisible derived impls clippy::non_ascii_literal, // clippy::must_use_candidate, // excessively pedantic // clippy::missing_errors_doc, // for now // For when clippy::restriction is on: clippy::else_if_without_else, // clippy::missing_inline_in_public_items, clippy::implicit_return, clippy::missing_docs_in_private_items, )] use core::ops::DerefMut; /// Implement this for your tree node type, with `Link` as your tree link type /// that dereferences to your node type. /// /// The `Link` type may be the same as the `Self` type, when possible, which /// might be convenient. Or, they can be different. /// /// Many `Self` types should be able to implement these methods without needing /// any extra state beyond their normal state. pub trait DeepSafeDrop<Link> { /// Supply the first child and replace the link to it with a non-link, if /// the current state of `self` has at least one child. fn take_first_child(&mut self) -> Option<Link>; /// Supply the first child and replace the link to it with a given /// replacement that links to the parent of `self`, if the current state of /// `self` has at least one child. fn replace_first_child_with_parent(&mut self, parent: Link) -> ReplacedFirstChild<Link>; /// Supply the next child and replace the link to it with a non-link, if the /// current state of `self` has another child that has not been supplied /// yet. fn take_next_child(&mut self) -> Option<Link>; } /// Result of `DeepSafeDrop::replace_first_child_with_parent`. #[derive(Debug)] pub enum ReplacedFirstChild<Link> { /// There was a first child and it was replaced by the parent. Yes { /// The first child that was taken. first_child: Link }, /// There was not any child, so no replacement was done, so the parent must /// be returned back. No { /// The same parent that was given to the function call. returned_parent: Link }, } /// Exists only to do the `debug_assert`. fn take_first_child<T, L>(thing: &mut T) -> Option<L> where T: DeepSafeDrop<L> + ?Sized, { let first_child = thing.take_first_child(); debug_assert!(matches!(thing.take_first_child(), None)); first_child } /// A node's first-child link is reused as the parent link. fn take_parent<L, N>(node: &mut N) -> Option<L> where N: DeepSafeDrop<L> + ?Sized, { take_first_child(node) } /// Return the nearest ancestor that has a next child if any, or the root /// ancestor even when it does not have a next child. Drop any ancestors in the /// upwards path that do not have a child but that do have a parent. fn take_ancestor_next_child<L>(parent: L) -> (L, Option<L>) where L: DerefMut, L::Target: DeepSafeDrop<L>, { let mut ancestor = parent; loop { if let Some(next_child) = ancestor.take_next_child() { break (ancestor, Some(next_child)); } else if let Some(grandancestor) = take_parent(&mut *ancestor) { // `ancestor` is now a leaf node so drop it here. drop(ancestor); ancestor = grandancestor; } else { break (ancestor, None); } } } /// The main algorithm. fn main_deep_safe_drop<L>(top: L) where L: DerefMut, L::Target: DeepSafeDrop<L>, { use ReplacedFirstChild::*; let mut parent = top; if let Some(mut cur) = take_first_child(&mut *parent) { loop { match cur.replace_first_child_with_parent(parent) { Yes { first_child } => { parent = cur; cur = first_child; } No { returned_parent } => { parent = returned_parent; // `cur` is a leaf node so drop it here. drop(cur); let (ancestor, ancestor_child) = take_ancestor_next_child(parent); parent = ancestor; if let Some(ancestor_child) = ancestor_child { cur = ancestor_child; } else { // Done. `parent` is now `top` which is now mutated to // no longer have any children, so, when dropping it is // completed by the compiler after this function // returns, recursion into children cannot occur and so // stack overflow cannot occur. drop(parent); break; } } } } } } /// To be called from your `Drop::drop` implementations, to ensure that stack /// overflow is avoided. /// /// The `RootNode` type may be different than the primary `Link::Target` node /// type, when possible, which might be convenient. Or, they can be the same. #[inline] pub fn deep_safe_drop<RootNode, Link>(root: &mut RootNode) where RootNode: DeepSafeDrop<Link> + ?Sized, Link: DerefMut, Link::Target: DeepSafeDrop<Link>, { if let Some(child) = take_first_child(root) { main_deep_safe_drop(child); while let Some(child) = root.take_next_child() { main_deep_safe_drop(child); } } } #[cfg(test)] mod tests;