Skip to main content

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}