unityrs_core/walk/dict.rs
1// Ported from UnityPy 1.25.2 (MIT): UnityPyBoost/TypeTreeHelper.cpp and
2// UnityPy/helpers/TypeTreeHelper.py. See THIRD_PARTY_LICENSES.
3
4//! What both readers share to build a dict and to resolve a
5//! `ReferencedObject`'s data: the linear `PyDict_SetItem` of plan 3.10
6//! ("Linear dicts") and the ref-type search ([`RefIndex`], which the writer
7//! shares too).
8//!
9//! **Linear dicts.** A class's entries grow in a metered vector as its
10//! children are read, as a Python dict grows as `PyDict_SetItem` fills it:
11//! a first reservation of at most [`DICT_FIRST`] entries, then
12//! geometrically, never past its children ([`Dict`]). A class whose
13//! children repeat a name, and a `ReferencedObject` (whose `type` is looked
14//! up by name), keep a table from each name's `slot` to its entry's
15//! position, so a repeated name overwrites its first entry in place
16//! (`PyDict_SetItem`: first position, last value) in O(1), and a name a
17//! skipped child would have set first lands where the first child actually
18//! read puts it. The table too grows as the children are set: a child's
19//! slot is at most the number of children before it. So a read makes no
20//! pass over a class's children before it reads them, and holds no entry or
21//! slot the tree sizes before its bytes are read (review round 7: a class
22//! reserved one entry a child before reading any, and every level of a
23//! `ReferencedObject` nested in its ref type held its own).
24
25use std::collections::HashMap;
26use std::sync::Arc;
27
28use crate::files::SerializedType;
29use crate::limits::{Charge, ChargeError, Limits, Meter, MeteredVec, hash_table_cost};
30use crate::raw::RawStr;
31use crate::typetree::{NodeId, Tree};
32use crate::value::{ListIx, Map, Value, ValueBuilder};
33
34use super::{
35 OpenWork, Out, ReadDetail, ReadError, ReadErrorKind, RefTypes, VALUE_WORK, Work, charge_error,
36};
37use crate::error::LimitError;
38
39/// No entry yet for a slot.
40const NONE: u32 = u32::MAX;
41
42#[cfg(test)]
43std::thread_local! {
44 /// Map steps this thread took: each slot a table of positions grows
45 /// by, each entry set or looked up, each entry a growth may copy, each
46 /// entry a lookup by name passes, each ref type or node list a search
47 /// passes; the writer's lookups too (the linear-work tests).
48 pub(super) static STEPS: std::cell::Cell<u64> = const { std::cell::Cell::new(0) };
49}
50
51/// Counts `n` map steps (tests only).
52#[inline]
53pub(crate) fn steps(n: usize) {
54 #[cfg(test)]
55 STEPS.with(|s| s.set(s.get().saturating_add(n as u64)));
56 #[cfg(not(test))]
57 let _ = n;
58}
59
60#[cfg(test)]
61std::thread_local! {
62 /// Loop turns this thread's walks took: each child a class's or a
63 /// `ReferencedObject`'s loop visits (read, written or skipped), in both
64 /// readers and the writer, and each element the writer's array loop
65 /// visits (the work tests: an instrument apart from the count that
66 /// bounds them, [`crate::limits::Limits::max_values_per_object`]).
67 pub(super) static VISITS: std::cell::Cell<u64> = const { std::cell::Cell::new(0) };
68}
69
70/// Counts one loop turn (tests only).
71#[inline]
72pub(crate) fn visit() {
73 #[cfg(test)]
74 VISITS.with(|s| s.set(s.get().saturating_add(1)));
75}
76
77/// The most entries a dict reserves before its first child is read: one
78/// for each child up to this many. A dict grows past it geometrically as its
79/// children are set, so a read holds no more than this many entries a dict
80/// that it has not filled, beyond as many again as it has filled (review
81/// round 7: every `ReferencedObject` level re-entering a ref type of `k`
82/// children held `k` entries reserved while the next level was read,
83/// gigabytes for a few kilobytes of data).
84pub const DICT_FIRST: usize = 16;
85
86/// One dict being read: its entries, and the position of each name's entry
87/// when its keys may repeat.
88#[derive(Debug)]
89pub(crate) struct Dict {
90 pub(crate) entries: MeteredVec<(NodeId, Value)>,
91 /// Each slot's entry position ([`NONE`]: not set yet), for a dict whose
92 /// keys may repeat or which is looked up by name; `None` when its
93 /// children's names are all distinct and its entries are only pushed.
94 /// It covers the slots set so far, and a child's slot is at most the
95 /// number of children before it, so it holds no more than one slot a
96 /// child read.
97 slots: Option<MeteredVec<u32>>,
98 /// The most entries it can come to: one a child.
99 most: usize,
100 preserve_fields: bool,
101}
102
103impl Dict {
104 /// Starts the dict of a node of `children` children, reserving at most
105 /// [`DICT_FIRST`] entries; `keyed` keeps each name's position (a class
106 /// whose children repeat a name, a `ReferencedObject`).
107 pub(crate) fn new(
108 builder: &ValueBuilder,
109 children: usize,
110 keyed: bool,
111 at: u64,
112 ) -> Result<Self, ReadError> {
113 let mut entries = builder.vec();
114 entries
115 .reserve_exact(children.min(DICT_FIRST))
116 .map_err(|e| charge_error(at, e))?;
117 Ok(Self {
118 entries,
119 slots: keyed.then(|| builder.vec()),
120 most: children,
121 preserve_fields: false,
122 })
123 }
124
125 pub(crate) fn preserve_fields(&mut self, preserve: bool) {
126 self.preserve_fields = preserve;
127 }
128
129 /// The entry position of `slot`, if set.
130 pub(crate) fn position(&self, slot: u32) -> Option<usize> {
131 let at = self
132 .slots
133 .as_ref()?
134 .as_slice()
135 .get(slot as usize)
136 .copied()?;
137 (at != NONE).then_some(at as usize)
138 }
139
140 /// `PyDict_SetItem(dict, name, value)`: a key already set keeps its
141 /// position and takes the value; a new one is appended. Entries that are
142 /// full grow geometrically, never past the dict's children, so growths
143 /// that move the entries copy them a bounded number of times (review
144 /// round 6's sweep: growing by exactly one, a dict reserved short relied
145 /// on the allocator's growing it in place). A slot past the table's end
146 /// grows the table to it, each slot a step of the read's work
147 /// ([`Work::steps`]), counted first.
148 pub(crate) fn set(
149 &mut self,
150 work: &mut Work<'_>,
151 key: NodeId,
152 slot: u32,
153 value: Out,
154 at: u64,
155 ) -> Result<(), ReadError> {
156 self.set_inline(work, key, slot, value, at)
157 }
158
159 /// [`Self::set`] inlined where it is called: UnityPyBoost's reader sets
160 /// each child where it reads it, its value moved into the entries
161 /// without a copy in between. The recursive reader calls [`Self::set`],
162 /// so its frames stay the size they were.
163 #[allow(
164 clippy::inline_always,
165 reason = "measured: a per-value call of the reader"
166 )]
167 #[inline(always)]
168 pub(crate) fn set_inline(
169 &mut self,
170 work: &mut Work<'_>,
171 key: NodeId,
172 slot: u32,
173 value: Out,
174 at: u64,
175 ) -> Result<(), ReadError> {
176 steps(1);
177 if let Some(pos) = self.position(slot).filter(|_| !self.preserve_fields) {
178 // The value it replaces was built and is not kept.
179 work.discard();
180 value.set_entry(&mut self.entries, pos);
181 return Ok(());
182 }
183 let pos = self.entries.len();
184 if pos == self.entries.capacity() {
185 // What the growth may copy (the linear-work tests).
186 steps(pos);
187 self.entries
188 .reserve_within(1, self.most)
189 .map_err(|e| charge_error(at, e))?;
190 }
191 value
192 .push_entry(&mut self.entries, key)
193 .map_err(|e| charge_error(at, e))?;
194 if let Some(slots) = &mut self.slots {
195 let slot = slot as usize;
196 let more = (slot + 1).saturating_sub(slots.len());
197 if more > 0 {
198 work.steps(more, at)?;
199 steps(more);
200 slots.reserve(more).map_err(|e| charge_error(at, e))?;
201 for _ in 0..more {
202 slots.push(NONE).map_err(|e| charge_error(at, e))?;
203 }
204 }
205 if let Some(s) = slots.as_mut_slice().get_mut(slot) {
206 *s = u32::try_from(pos).unwrap_or(NONE);
207 }
208 }
209 Ok(())
210 }
211
212 /// The finished dict, with no spare capacity: a dict whose children set
213 /// fewer entries than it grew to (a repeated name, a skipped child) gives
214 /// the rest back, charged before it moves
215 /// ([`MeteredVec::shrink_to_fit`]).
216 pub(crate) fn finish(
217 mut self,
218 builder: &ValueBuilder,
219 list: ListIx,
220 at: u64,
221 ) -> Result<Out, ReadError> {
222 self.entries
223 .shrink_to_fit()
224 .map_err(|e| charge_error(at, e))?;
225 Ok(Out::Built(builder.map(list, self.entries)))
226 }
227}
228
229/// The trees a read's maps are keyed by, in [`crate::Parsed::lists`]
230/// order: the root's, then each ref type's a `ReferencedObject` read
231/// through. A mirror of the builder's lists table, so a reader can name a
232/// map's keys (the `type` lookup of R14).
233#[derive(Debug)]
234pub(crate) struct Trees {
235 trees: MeteredVec<Arc<Tree>>,
236}
237
238impl Trees {
239 pub(crate) fn new(builder: &ValueBuilder, root: &Arc<Tree>) -> Result<Self, ReadError> {
240 let mut trees = builder.vec();
241 trees.push(root.clone()).map_err(|e| charge_error(0, e))?;
242 Ok(Self { trees })
243 }
244
245 /// The list index of `tree`'s keys, adding it to the builder's lists
246 /// (once per distinct tree) and to this mirror.
247 pub(crate) fn index(
248 &mut self,
249 builder: &mut ValueBuilder,
250 tree: &Arc<Tree>,
251 at: u64,
252 ) -> Result<ListIx, ReadError> {
253 let ix = builder
254 .list_index(tree.list())
255 .map_err(|e| charge_error(at, e))?;
256 if ix as usize == self.trees.len() {
257 self.trees
258 .push(tree.clone())
259 .map_err(|e| charge_error(at, e))?;
260 }
261 Ok(ix)
262 }
263
264 /// The name of `key` in a map keyed by list `list`.
265 pub(crate) fn name(&self, list: ListIx, key: NodeId) -> &[u8] {
266 self.trees
267 .as_slice()
268 .get(list as usize)
269 .map_or(&[], |t| t.list().name(key))
270 }
271
272 /// `map[name]`, a Python dict lookup by key string: each entry it
273 /// passes is a step of the open's work, counted before it is compared
274 /// (a key whose length differs from `name`'s is passed without reading
275 /// its bytes).
276 pub(crate) fn field<'v>(
277 &self,
278 map: &'v Map,
279 name: &[u8],
280 work: &mut OpenWork<'_>,
281 constructed: bool,
282 ) -> Result<Option<&'v Value>, LimitError> {
283 // Ordered object fields may repeat a name; construction overwrites
284 // with the final occurrence. Ordinary dict maps already have one.
285 for (k, v) in map.entries().iter().rev() {
286 steps(1);
287 work.steps(1)?;
288 let raw = self.name(map.list(), *k);
289 if if constructed {
290 super::write::cleans_to(raw, name)
291 } else {
292 raw == name
293 } {
294 return Ok(Some(v));
295 }
296 }
297 Ok(None)
298 }
299}
300
301/// A ref-type search's refusal: the table's memory, or the open's work.
302#[derive(Debug)]
303pub(crate) enum FindError {
304 /// The meter or the budget refused the table.
305 Charge(ChargeError),
306 /// The open's work passed its allowance ([`OpenWork`]).
307 Work(LimitError),
308}
309
310impl From<LimitError> for FindError {
311 fn from(l: LimitError) -> Self {
312 Self::Work(l)
313 }
314}
315
316/// The bytes of a ref type's three names.
317fn names_len(t: &SerializedType) -> usize {
318 [&t.class_name, &t.namespace, &t.assembly]
319 .into_iter()
320 .map(|n| n.as_ref().map_or(0, |n| n.as_bytes().len()))
321 .sum()
322}
323
324/// A ref type's `(class, ns, asm)` equal to the three values: each must be
325/// a Python `str` (a surrogate-escaped string compares equal exactly when
326/// its bytes do), as `PyUnicode_Compare` (UnityPy TypeTreeHelper.cpp:663)
327/// and the pure-Python `==` (UnityPy TypeTreeHelper.py:106) compare them;
328/// any other object never matches.
329fn names_match(t: &SerializedType, cls: &Value, ns: &Value, asm: &Value) -> bool {
330 let eq = |v: &Value, s: &Option<RawStr>| match (v, s) {
331 (Value::Str(a), Some(b)) => a.as_bytes() == b.as_bytes(),
332 _ => false,
333 };
334 eq(cls, &t.class_name) && eq(ns, &t.namespace) && eq(asm, &t.assembly)
335}
336
337/// `get_ref_type_node`'s search: the *first* ref type whose class,
338/// namespace and assembly equal the three values ([`names_match`]; UnityPy
339/// TypeTreeHelper.cpp:646-673, TypeTreeHelper.py:105-107), found in steps
340/// linear in the list plus the lookups of one read or one write. UnityPy
341/// scans the list for every lookup, so an object of `n` references into
342/// `n` ref types costs it `n`² comparisons (claude X, review round 2).
343/// Here each lookup scans as UnityPy does until this read's or write's
344/// scans have passed the list's length; then, for a list longer than
345/// [`SCANNED_REFS`], a table from each `(class, ns, asm)` to its first
346/// index is built, once, charged to the meter before it allocates, and
347/// every later lookup is one probe. A read or a write so costs at most
348/// twice what UnityPy's own scans cost it, and at most three steps a ref
349/// type plus one a lookup (or [`SCANNED_REFS`] a lookup).
350///
351/// That bounds one read or write; the open's work bounds them all: the
352/// index is one read's or write's, and every object of a file searches the
353/// file's one list again, so K objects over R ref types cost K x R steps
354/// that their values do not count (the sweep of fix pass 5). Each ref type
355/// a scan compares or the table indexes counts [`VALUE_WORK`] and the bytes
356/// of its three names, what a comparison or a hash reads of it at most, and
357/// each probe [`VALUE_WORK`] and the bytes of the key it hashes, on the
358/// read's or the write's [`OpenWork`], before the step is taken.
359pub(crate) struct RefIndex<'a> {
360 list: &'a [SerializedType],
361 /// The ref types the scans so far compared.
362 scanned: usize,
363 table: Option<RefTable<'a>>,
364}
365
366/// A list this long or shorter is only ever scanned: a lookup costs at most
367/// as many steps as a probe's hashing.
368const SCANNED_REFS: usize = 8;
369
370/// [`RefIndex`]'s table.
371struct RefTable<'a> {
372 first: HashMap<[&'a [u8]; 3], usize>,
373 /// The longest class, namespace and assembly: a longer value matches
374 /// nothing and is not hashed (a scan's comparison checks lengths first).
375 longest: [usize; 3],
376 _charge: Charge,
377}
378
379impl<'a> RefIndex<'a> {
380 /// Over `refs`' list (empty for no list: the callers check that first).
381 pub(crate) fn new(refs: RefTypes<'a>) -> Self {
382 let list = match refs {
383 RefTypes::List(l) => l,
384 RefTypes::NoFile | RefTypes::Absent => &[],
385 };
386 Self {
387 list,
388 scanned: 0,
389 table: None,
390 }
391 }
392
393 /// The first ref type whose names equal `(cls, ns, asm)`, the table
394 /// charged to `meter` when this lookup builds it, each step counted on
395 /// `work` before it is taken.
396 pub(crate) fn find(
397 &mut self,
398 meter: &Arc<Meter>,
399 work: &mut OpenWork<'_>,
400 cls: &Value,
401 ns: &Value,
402 asm: &Value,
403 ) -> Result<Option<&'a SerializedType>, FindError> {
404 let (Value::Str(c), Value::Str(n), Value::Str(a)) = (cls, ns, asm) else {
405 // A value that is not a `str` matches no ref type.
406 return Ok(None);
407 };
408 if self.table.is_none() && self.scanned >= self.list.len() && self.list.len() > SCANNED_REFS
409 {
410 self.table = Some(RefTable::build(self.list, meter, work)?);
411 }
412 if let Some(t) = &self.table {
413 steps(1);
414 let key = [c.as_bytes(), n.as_bytes(), a.as_bytes()];
415 if key.iter().zip(t.longest).any(|(k, l)| k.len() > l) {
416 work.add(VALUE_WORK)?;
417 return Ok(None);
418 }
419 work.add(VALUE_WORK.saturating_add(as_u64(key.iter().map(|k| k.len()).sum())))?;
420 let first: &HashMap<[&[u8]; 3], usize> = &t.first;
421 return Ok(first.get(&key).and_then(|i| self.list.get(*i)));
422 }
423 for (i, r) in self.list.iter().enumerate() {
424 steps(1);
425 work.add(VALUE_WORK.saturating_add(as_u64(names_len(r))))?;
426 if names_match(r, cls, ns, asm) {
427 self.scanned = self.scanned.saturating_add(i + 1);
428 return Ok(Some(r));
429 }
430 }
431 self.scanned = self.scanned.saturating_add(self.list.len());
432 Ok(None)
433 }
434}
435
436fn as_u64(n: usize) -> u64 {
437 u64::try_from(n).unwrap_or(u64::MAX)
438}
439
440impl<'a> RefTable<'a> {
441 /// Every ref type with all three names, first index kept, charged
442 /// before it allocates ([`hash_table_cost`]), each ref type counted on
443 /// `work` before it is indexed.
444 fn build(
445 list: &'a [SerializedType],
446 meter: &Arc<Meter>,
447 work: &mut OpenWork<'_>,
448 ) -> Result<Self, FindError> {
449 let n = list.len();
450 let charge = meter
451 .charge(hash_table_cost(n, size_of::<([&[u8]; 3], usize)>()))
452 .map_err(FindError::Charge)?;
453 let mut first = HashMap::with_capacity(n);
454 let mut longest = [0; 3];
455 for (i, r) in list.iter().enumerate() {
456 steps(1);
457 work.add(VALUE_WORK.saturating_add(as_u64(names_len(r))))?;
458 let (Some(c), Some(ns), Some(a)) = (&r.class_name, &r.namespace, &r.assembly) else {
459 continue;
460 };
461 let key = [c.as_bytes(), ns.as_bytes(), a.as_bytes()];
462 for (l, k) in longest.iter_mut().zip(key) {
463 *l = (*l).max(k.len());
464 }
465 first.entry(key).or_insert(i);
466 }
467 Ok(Self {
468 first,
469 longest,
470 _charge: charge,
471 })
472 }
473}
474
475/// What a matched ref type gives the data child: its compiled tree, or no
476/// tree (type trees disabled; UnityPy's `node is None`).
477#[derive(Clone)]
478pub(crate) enum RefNode {
479 /// Read the data with this tree.
480 Tree(Arc<Tree>),
481 /// No tree: the readers skip `data` (or, on the pure-Python array path,
482 /// raise [`ReadDetail::RefTypeNoTree`]).
483 NoTree,
484}
485
486/// The compiled tree of a matched ref type.
487pub(crate) fn ref_tree(t: &SerializedType, limits: &Limits, at: u64) -> Result<RefNode, ReadError> {
488 match t.tree(limits) {
489 None => Ok(RefNode::NoTree),
490 Some(Ok(tree)) => Ok(RefNode::Tree(tree)),
491 Some(Err(e)) => Err(ReadError {
492 kind: ReadErrorKind::Other,
493 at,
494 detail: ReadDetail::Tree(e),
495 }),
496 }
497}
498
499#[cfg(test)]
500mod tests {
501
502 use bytes::Bytes;
503
504 use super::STEPS;
505 use crate::limits::{Limits, Meter};
506 use crate::stream::Endian;
507 use crate::typetree::{NodeList, NodeRow, Tree};
508 use crate::value::Value;
509 use crate::walk::{ReadCtx, ReadOptions, RefTypes, boost, python};
510
511 /// Plan 3.10, linear dicts: a class of 2^16 children whose last 4,096
512 /// repeat the first 4,096 names reads in map steps linear in the
513 /// children (counted, not timed, the growth of its entries and of its
514 /// table of positions included; a dict that looked each name up among
515 /// its entries would
516 /// take some 2^31), each repeated name keeping its
517 /// first position and taking its last value, from both readers.
518 #[test]
519 fn late_repeats_read_in_linear_map_steps() {
520 const N: u32 = 1 << 16;
521 const REPEATS: u32 = 4096;
522 let distinct = N - REPEATS;
523 let mut rows = vec![NodeRow::new(0, "Base", "Base")];
524 for i in 0..N {
525 let name = format!("n{}", if i < distinct { i } else { i - distinct });
526 rows.push(NodeRow::new(1, "int", name.as_str()));
527 }
528 let tree = Tree::compile(
529 NodeList::trusted(rows).unwrap().into_shared().unwrap(),
530 &Limits::default(),
531 )
532 .unwrap();
533 let data: Vec<u8> = (0..N).flat_map(u32::to_le_bytes).collect();
534 let data = Bytes::from(data);
535 let options = ReadOptions::default();
536 let meter = Meter::unlimited();
537 let ctx = ReadCtx {
538 endian: Endian::Little,
539 ref_types: RefTypes::List(&[]),
540 options: &options,
541 meter: &meter,
542 };
543 for reader in ["boost", "python"] {
544 STEPS.with(|s| s.set(0));
545 let p = match reader {
546 "boost" => boost::read(&data, &tree, &ctx),
547 _ => python::read(&data, 0, &tree, &ctx),
548 }
549 .unwrap();
550 let steps = STEPS.with(std::cell::Cell::get);
551 assert!(
552 steps <= 6 * u64::from(N),
553 "{reader}: {steps} map steps for {N} children"
554 );
555 let Value::Dict(m) = p.value() else {
556 panic!("{reader}: not a dict")
557 };
558 assert_eq!(m.len(), distinct as usize, "{reader}");
559 for (i, (name, v)) in p.entries(m).enumerate() {
560 let i = u32::try_from(i).unwrap();
561 assert_eq!(name, format!("n{i}").as_bytes(), "{reader}: position {i}");
562 let last = if i < REPEATS { distinct + i } else { i };
563 assert_eq!(v, &Value::Int(i64::from(last)), "{reader}: n{i}");
564 }
565 }
566 }
567}