Skip to main content

unityrs_core/value/
flat.rs

1//! A value's depth without recursion: dropped, and its slices visited
2//! ([`crate::pin`]), with the same native stack at any depth, so a read
3//! runs on a thread of any stack size.
4
5use super::{ListIx, Map, PrimArray, Value};
6use crate::typetree::NodeId;
7
8impl Value {
9    /// Whether this value holds another value (a non-empty list, tuple or
10    /// dict).
11    fn nests(&self) -> bool {
12        match self {
13            Self::List(items) => !items.is_empty(),
14            Self::Tuple(items) => !items.is_empty(),
15            Self::Dict(map) => !map.entries.is_empty(),
16            _ => false,
17        }
18    }
19
20    /// Whether an item of this value holds values of its own: dropped as
21    /// is, it would drop a level below its items.
22    fn deep(&self) -> bool {
23        match self {
24            Self::List(items) => items.iter().any(Self::nests),
25            Self::Tuple(items) => items.iter().any(Self::nests),
26            Self::Dict(map) => map.entries.iter().any(|(_, v)| v.nests()),
27            _ => false,
28        }
29    }
30
31    /// The values this one holds, taken out of it (no allocation: its own
32    /// vector moves).
33    fn take_items(&mut self) -> Pile {
34        match self {
35            Self::List(items) => Pile::Values(std::mem::take(items)),
36            Self::Tuple(items) => Pile::Values(std::mem::take(items).into_vec()),
37            Self::Dict(map) => Pile::Entries(std::mem::take(&mut map.entries)),
38            _ => Pile::Values(Vec::new()),
39        }
40    }
41}
42
43/// Values waiting to be dropped: a value's own items.
44enum Pile {
45    Values(Vec<Value>),
46    Entries(Vec<(NodeId, Value)>),
47}
48
49impl Pile {
50    fn pop(&mut self) -> Option<Value> {
51        match self {
52            Self::Values(items) => items.pop(),
53            Self::Entries(entries) => entries.pop().map(|(_, v)| v),
54        }
55    }
56
57    fn is_empty(&self) -> bool {
58        match self {
59            Self::Values(items) => items.is_empty(),
60            Self::Entries(entries) => entries.is_empty(),
61        }
62    }
63
64    /// A value holding these, as any other: dropping it drops them.
65    fn into_value(self) -> Value {
66        match self {
67            Self::Values(items) => Value::List(items),
68            Self::Entries(entries) => Value::Dict(Map {
69                list: ListIx::default(),
70                entries,
71            }),
72        }
73    }
74
75    /// Adds `value` where one was just taken: never allocates.
76    fn put_back(&mut self, value: Value) {
77        match self {
78            Self::Values(items) => items.push(value),
79            Self::Entries(entries) => entries.push((NodeId(0), value)),
80        }
81    }
82}
83
84/// Dropped without recursion and without allocating, each value looked at
85/// once, so in time linear in the values held at any depth. The values
86/// waiting are a stack of piles, each a value's own vector of items: the
87/// innermost is taken from the end one value at a time, and a value with
88/// items of its own has them taken out (its vector moves) to become the
89/// innermost pile, the rest of the one it came from saved in a value of
90/// its own, along with the pile above that (pushed into the slot the value
91/// left free). A pile done, the one saved above it resumes. A value of any
92/// depth takes the same stack, so a read (and a failed read's partial
93/// values) may drop on a thread of any stack size, and the heap never goes
94/// above what the values held.
95impl Drop for Value {
96    fn drop(&mut self) {
97        if !self.deep() {
98            return;
99        }
100        let mut pile = self.take_items();
101        // The pile the current one came from, saved in a value; below the
102        // first, each saved pile's last item is the one saved above it.
103        let mut up: Option<Value> = None;
104        let mut saved = 0_usize;
105        loop {
106            let Some(mut value) = pile.pop() else {
107                let Some(mut link) = up.take() else {
108                    break;
109                };
110                pile = link.take_items();
111                saved -= 1;
112                if saved > 0 {
113                    up = pile.pop();
114                }
115                continue;
116            };
117            if !value.nests() {
118                // A scalar or an empty container: nothing below it.
119                continue;
120            }
121            let items = value.take_items();
122            drop(value);
123            if !pile.is_empty() {
124                // The slot `value` left takes the pile saved above.
125                if let Some(link) = up.take() {
126                    pile.put_back(link);
127                }
128                up = Some(std::mem::replace(&mut pile, Pile::Values(Vec::new())).into_value());
129                saved += 1;
130            }
131            pile = items;
132        }
133    }
134}
135
136/// Containers open in [`Value::each`] kept in place before any is kept on
137/// the heap: most values nest no deeper, so a visit allocates nothing.
138const INLINE_OPENS: usize = 16;
139
140/// A stack whose first [`INLINE_OPENS`] items are in place, any more on the
141/// heap: a value of any depth takes the same native stack. A slot past the
142/// top holds a spent item (`T::default()`, or one popped).
143struct Stack<T> {
144    inline: [T; INLINE_OPENS],
145    len: usize,
146    spill: Vec<T>,
147}
148
149impl<T: Default> Stack<T> {
150    fn new() -> Self {
151        Self {
152            inline: Default::default(),
153            len: 0,
154            spill: Vec::new(),
155        }
156    }
157
158    fn push(&mut self, item: T) {
159        match self.inline.get_mut(self.len) {
160            Some(slot) => *slot = item,
161            None => self.spill.push(item),
162        }
163        self.len += 1;
164    }
165
166    fn last_mut(&mut self) -> Option<&mut T> {
167        let at = self.len.checked_sub(1)?;
168        match self.inline.get_mut(at) {
169            Some(slot) => Some(slot),
170            None => self.spill.last_mut(),
171        }
172    }
173
174    fn pop(&mut self) {
175        if self.len > INLINE_OPENS {
176            self.spill.pop();
177        }
178        self.len = self.len.saturating_sub(1);
179    }
180}
181
182impl crate::pin::Slices for Value {
183    /// Its strings, `TypelessData` and `vector<UInt8>` runs, depth first in
184    /// order: the containers open above the one visited are iterators on a
185    /// stack of their own ([`Stack`]), so a value of any depth takes the
186    /// same native stack, and one no deeper than [`INLINE_OPENS`]
187    /// allocates nothing.
188    fn each(&mut self, f: &mut dyn FnMut(crate::pin::Slice<'_>)) {
189        use crate::pin::Slice;
190        enum Open<'a> {
191            Items(std::slice::IterMut<'a, Value>),
192            Entries(std::slice::IterMut<'a, (NodeId, Value)>),
193        }
194        impl Default for Open<'_> {
195            fn default() -> Self {
196                Self::Items(std::slice::IterMut::default())
197            }
198        }
199        let mut opens: Stack<Open<'_>> = Stack::new();
200        let mut next = Some(self);
201        loop {
202            let value = if let Some(value) = next.take() {
203                value
204            } else {
205                let Some(open) = opens.last_mut() else {
206                    break;
207                };
208                let item = match open {
209                    Open::Items(items) => items.next(),
210                    Open::Entries(entries) => entries.next().map(|(_, v)| v),
211                };
212                let Some(item) = item else {
213                    opens.pop();
214                    continue;
215                };
216                item
217            };
218            match value {
219                Self::Str(s) => f(Slice::Str(s)),
220                Self::Bytes(b) | Self::Prims(PrimArray::U8(b)) => f(Slice::Bytes(b)),
221                Self::List(items) => opens.push(Open::Items(items.iter_mut())),
222                Self::Tuple(items) => opens.push(Open::Items(items.iter_mut())),
223                Self::Dict(m) => opens.push(Open::Entries(m.entries.iter_mut())),
224                Self::Bool(_)
225                | Self::Int(_)
226                | Self::UInt(_)
227                | Self::F32(_)
228                | Self::F64(_)
229                | Self::Prims(_) => {}
230            }
231        }
232    }
233}
234
235#[cfg(test)]
236mod tests {
237    use super::super::{ListIx, Map, Value};
238    use crate::typetree::NodeId;
239
240    /// `vector<vector<Inner{int}>>`: `n` empty lists, then `n` lists of one
241    /// class each. Each nested value is taken apart once; a drop that looked
242    /// over the values still waiting at each one took `n * n` steps.
243    #[test]
244    fn a_wide_list_of_short_lists_drops_in_linear_time() {
245        let n = 200_000;
246        let mut outer = Vec::with_capacity(2 * n);
247        outer.extend((0..n).map(|_| Value::List(Vec::new())));
248        outer.extend((0..n).map(|_| {
249            Value::List(vec![Value::Dict(Map {
250                list: ListIx::default(),
251                entries: vec![(NodeId(0), Value::Int(1))],
252            })])
253        }));
254        timed(Value::List(outer));
255    }
256
257    /// A comb 512 levels deep, each level `k` lists of one value beside the
258    /// next level: each value is taken apart once, where a drop that walked
259    /// back over the levels saved took `k * 512 * 512` steps.
260    #[test]
261    fn a_deep_comb_drops_in_linear_time() {
262        let k = 2_000;
263        let mut value = Value::Int(0);
264        for _ in 0..512 {
265            let mut level: Vec<Value> = (0..k).map(|i| Value::List(vec![Value::Int(i)])).collect();
266            level.insert(level.len() / 2, value);
267            value = Value::List(level);
268        }
269        timed(value);
270    }
271
272    fn timed(value: Value) {
273        let start = std::time::Instant::now();
274        drop(value);
275        let took = start.elapsed();
276        // Linear: well under a second even unoptimized; worse: minutes.
277        assert!(
278            took < std::time::Duration::from_secs(5),
279            "dropped in {took:?}"
280        );
281    }
282}