unityrs_core/value/
flat.rs1use super::{ListIx, Map, PrimArray, Value};
6use crate::typetree::NodeId;
7
8impl Value {
9 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 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 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
43enum 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 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 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
84impl Drop for Value {
96 fn drop(&mut self) {
97 if !self.deep() {
98 return;
99 }
100 let mut pile = self.take_items();
101 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 continue;
120 }
121 let items = value.take_items();
122 drop(value);
123 if !pile.is_empty() {
124 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
136const INLINE_OPENS: usize = 16;
139
140struct 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 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 #[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 #[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 assert!(
278 took < std::time::Duration::from_secs(5),
279 "dropped in {took:?}"
280 );
281 }
282}