Skip to main content

unityrs_core/walk/
mod.rs

1// Ported from UnityPy 1.25.2 (MIT): UnityPy/helpers/TypeTreeHelper.py, UnityPyBoost/TypeTreeHelper.cpp, UnityPy/files/ObjectReader.py. See THIRD_PARTY_LICENSES.
2//! Reading and writing values through a typetree.
3//!
4//! `TypeTreeHelper.read_typetree` (`helpers/TypeTreeHelper.py:123-158`) picks
5//! a reader by the object's size: with `byte_size > 0` UnityPyBoost reads the
6//! object's bytes and nothing else ([`boost`]); with `byte_size == 0` the
7//! pure-Python reader starts at `byte_start` in the whole file and may read on
8//! past the object ([`python`]). Then `check_read` compares the bytes read
9//! with `byte_size`, in either direction. UnityPyBoost has no writer, so
10//! [`write`](mod@write) ports UnityPy's pure-Python `write_typetree` (`:161-179`,
11//! `:407-458`), which does not mirror the reader (plan section 3.11).
12//!
13//! **Memory.** Every allocation a read makes for the value (a list, a map, a
14//! tuple, a primitive run) is charged to [`ReadCtx::meter`], the input's,
15//! before it is made, at [`crate::limits::heap_cost`] of its capacity, and
16//! the charges ride in the [`Parsed`] (grow through
17//! [`crate::limits::MeteredVec`], then hand its charge to the `Parsed`). A
18//! refused charge is [`ReadDetail::Charge`] (kind `other`). The writer's
19//! output grows the same way. What a read reserves before the bytes it holds
20//! are read is bounded apart from the tree's width and the read's depth: a
21//! dict at most [`DICT_FIRST`] entries, growing as its children are set;
22//! the lists a read holds open at once, `max_prealloc` elements in all
23//! (`Work::first_room`), each growing geometrically as it is filled (review
24//! round 7 and its sweep: a dict reserved one entry a child, and each list
25//! open `max_prealloc` of its own, so a `ReferencedObject` re-entering a
26//! wide ref type, or vectors nested in vectors, held that many times over
27//! for a few bytes of data; `tests/walk_reentry.rs`).
28//!
29//! **Work.** Every read and every write counts what it does toward its
30//! open's work ([`crate::limits::Limits::max_decode_work`], the bound every
31//! other kind of the open's work counts toward), whatever its outcome:
32//! [`VALUE_WORK`] for each value it builds, writes or skips, and for each
33//! element of a primitive run a read holds as a run, or each primitive a
34//! write writes, its bytes (`Work`); each byte of a string a write copies,
35//! or passes over to find its characters; [`STEP_WORK`] for each step that
36//! builds no value: a slot a dict's table of positions grows by, an entry a
37//! lookup by name passes, a name a writer's table indexes or probes (and
38//! the bytes of a name it compares or hashes); and its ref-type lookups, a
39//! ref type a lookup compares or indexes, or a probe, [`VALUE_WORK`] and the
40//! name bytes it reads (`dict::RefIndex`). Objects may share their bytes,
41//! and a read refused by a bound of its own (`max_zero_size_elements`,
42//! `max_values_per_object`) keeps nothing, so K objects over the same bytes
43//! repeated it K times with no bound on the input (fix pass 4's sweep: every
44//! object of a small file over one vector of 2^22 empty elements, each
45//! refused after 2^20); every object searches its file's one list of ref
46//! types again, so K objects over R ref types took K x R steps (fix pass 5's
47//! sweep); and a read failing at a class's first child had passed over all
48//! of its children to size its dict (review round 6: K objects over a class
49//! of `k` children, K x `k` steps; review round 7: the pass that stayed for
50//! a class whose children repeat a name refused such reads with
51//! `DecodeWork` where UnityPy read each to its own failure). No read or
52//! write passes over a class's children before it reads or writes them.
53//!
54//! Each step is counted before it is taken, on the read's or the write's
55//! `OpenWork`, which adds the steps to the open's meter a chunk
56//! ([`WORK_CHUNK`]) at a time, in one atomic check-and-add: a chunk that
57//! would take the open past its allowance is refused, and the read or the
58//! write fails with [`LimitKind::DecodeWork`] (kind `other` for a read); one
59//! whose own work, counted when it ends, took the open past its allowance
60//! fails too (its own failure first, if it has one). So the reads and writes
61//! that succeed never do more work together than the allowance, on any
62//! number of threads, and each one in progress does at most a chunk and one
63//! step past it before it stops (review round 6: a read added its work only
64//! when it ended, so two reads on two threads both passed the start's check
65//! and ran to their end past the allowance). Once the open's work has passed
66//! its allowance, a read or a write is refused before it starts
67//! (`tests/walk_work.rs`, `tests/walk_prepass.rs`).
68//!
69//! Owner: the scaffold for the types in this file (frozen); package B owns
70//! [`read_typetree`]'s body and the three submodules.
71
72pub mod boost;
73mod dict;
74pub mod emit;
75mod fields;
76pub mod python;
77mod read;
78pub use fields::FieldProgress;
79pub(crate) use read::read_with_fields;
80pub use read::{read_typetree, read_typetree_with_reader};
81mod work;
82pub mod write;
83
84pub use dict::DICT_FIRST;
85pub(crate) use dict::steps;
86pub(crate) use work::{OpenWork, Work, limit_refused};
87pub use work::{STEP_WORK, VALUE_WORK, WORK_CHUNK};
88
89#[cfg(test)]
90mod dict_tests;
91#[cfg(test)]
92mod linear_tests;
93#[cfg(test)]
94mod prepass_tests;
95
96use std::sync::Arc;
97
98use crate::error::{LimitError, LimitKind};
99use crate::files::SerializedType;
100use crate::limits::{ChargeError, Limits, Meter, MeteredVec};
101use crate::provider::{NoTree, ProviderError};
102use crate::raw::RawStr;
103use crate::stream::{Endian, StreamRefusal};
104use crate::typetree::{NodeId, TreeError};
105use crate::value::{Built, Parsed, Value};
106
107/// How a float32 signalling NaN reaches the value.
108#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, Hash)]
109pub enum FloatMode {
110    /// As UnityPyBoost delivers it: `PyFloat_FromDouble` on x86-64 quiets a
111    /// signalling NaN (`7f800001` becomes `7fc00001`; `CANONICAL_DUMP.md`
112    /// section 7). The oracle's behaviour, and the default.
113    #[default]
114    UnityPy,
115    /// The file's bits; `save_typetree(parse())` then round-trips them.
116    Lossless,
117}
118
119/// The writer's alignment rules.
120#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, Hash)]
121pub enum WriteRules {
122    /// UnityPy's `write_value`: an array element whose node carries the align
123    /// flag aligns after *every* element, where the reader aligns once after a
124    /// run. The oracle's L3 behaviour, and the default.
125    #[default]
126    UnityPy,
127    /// Write as the reader that built the value reads ([`Parsed::read_by`]).
128    /// For UnityPyBoost's: align once after a flagged primitive or `pair`
129    /// run, write no data where the reader skipped it (a `class` whose size
130    /// field is 0, or a matched ref type with no tree), and take a type name
131    /// to its first NUL. For the pure-Python reader's: take a type name
132    /// whole, write a flagged array's elements as `read_value_array` reads
133    /// them (each kind without its own trailing alignment, the run aligned
134    /// once after; a `pair`'s primitive, string or bytes children without
135    /// their own flags, its 16-bit ones unswapped; a class's registry
136    /// children with no registry check; a run of 16-bit integers with their
137    /// signedness swapped), align no empty string after itself (so not at
138    /// all where that reader reads no flag: a run's element, a flagged
139    /// `pair` run's child), and write no data for an empty `class` or a
140    /// matched ref type with no tree. A value either reader reads through a tree that
141    /// repeats no name writes back to bytes the same reader reads as the
142    /// same value (padding as zeros), unless the pure-Python reader moved
143    /// its position other than forward over what it holds (a negative
144    /// `TypelessData` length, or one past the end) or started at a position
145    /// not a multiple of 4 (it aligns to the file, the writer to the
146    /// object); a repeated name keeps only its last value, so no writer
147    /// gives back the others' bytes (plan 3.11; a `PARITY.md` Tier C
148    /// option; `tests/walk_mirror.rs`).
149    MirrorReader,
150}
151
152/// The walker's options.
153#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
154pub struct ReadOptions {
155    /// Float32 signalling NaNs.
156    pub floats: FloatMode,
157    /// Depth, value-count and zero-size bounds.
158    pub limits: Limits,
159}
160
161/// `assetsfile.ref_types` as the reader sees it (UnityPyBoost
162/// `TypeTreeHelper.cpp:585-681`; the pure-Python writer, `TypeTreeHelper.py:88-109`).
163#[derive(Clone, Copy, Debug)]
164pub enum RefTypes<'a> {
165    /// No assets file at all (UnityPyBoost: `ref_type` error on use).
166    NoFile,
167    /// The file has no `ref_types` attribute (format below 20).
168    Absent,
169    /// The file's ref types, in file order (may be empty).
170    List(&'a [SerializedType]),
171}
172
173/// What the reader needs besides the bytes and the tree.
174#[derive(Clone, Copy, Debug)]
175pub struct ReadCtx<'a> {
176    /// The file's byte order.
177    pub endian: Endian,
178    /// For `ReferencedObject` data.
179    pub ref_types: RefTypes<'a>,
180    /// Floats and limits.
181    pub options: &'a ReadOptions,
182    /// The input's meter: every allocation of the value is charged here
183    /// first, and the [`Parsed`] keeps the charges (the object's file's
184    /// [`crate::files::SerializedFile::meter`]).
185    pub meter: &'a Arc<Meter>,
186}
187
188/// What the writer needs besides the value and the tree.
189#[derive(Clone, Copy, Debug)]
190pub struct WriteCtx<'a> {
191    /// The file's byte order.
192    pub endian: Endian,
193    /// For `ReferencedObject` data.
194    pub ref_types: RefTypes<'a>,
195    /// Alignment rules.
196    pub rules: WriteRules,
197    /// The depth and values bounds (`max_value_depth`,
198    /// `max_values_per_object`).
199    pub limits: &'a Limits,
200}
201
202/// The canonical dump's L2 error kinds (`CANONICAL_DUMP.md` section 4.3).
203#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
204pub enum L2Kind {
205    /// No tree: none embedded, none from a provider.
206    NoTypetree,
207    /// The read ended `bytes_read` bytes in, and that is not `byte_size`.
208    CheckRead,
209    /// A read (not an alignment) past the object's end, on the Boost path.
210    OutOfBounds,
211    /// A negative length.
212    NegativeLength,
213    /// A `ReferencedObject` whose type is not in `ref_types`, or no `ref_types`.
214    RefType,
215    /// The value does not fit its tree (an encoder bug).
216    Encode,
217    /// Anything else, our limits included.
218    Other,
219}
220
221impl L2Kind {
222    /// The dump's string for the kind.
223    #[must_use]
224    pub fn as_str(self) -> &'static str {
225        match self {
226            Self::NoTypetree => "no_typetree",
227            Self::CheckRead => "check_read",
228            Self::OutOfBounds => "out_of_bounds",
229            Self::NegativeLength => "negative_length",
230            Self::RefType => "ref_type",
231            Self::Encode => "encode",
232            Self::Other => "other",
233        }
234    }
235}
236/// A reader failure, with its kind decided structurally (never parsed from a message).
237#[derive(Clone, Debug, PartialEq, Eq, thiserror::Error)]
238#[error("{kind:?} at byte {at}: {detail}")]
239pub struct ReadError {
240    /// The dump's kind.
241    pub kind: ReadErrorKind,
242    /// Offset from the start of the read.
243    pub at: u64,
244    /// What happened.
245    pub detail: ReadDetail,
246}
247/// A reader failure's L2 kind.
248#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
249pub enum ReadErrorKind {
250    /// `out_of_bounds`.
251    OutOfBounds,
252    /// `negative_length`.
253    NegativeLength,
254    /// `ref_type`.
255    RefType,
256    /// `other`.
257    Other,
258}
259/// What a reader failure was.
260#[derive(Clone, Debug, PartialEq, Eq, thiserror::Error)]
261#[non_exhaustive]
262pub enum ReadDetail {
263    /// A read needed bytes past the end.
264    #[error("needs {need} bytes past the end")]
265    Eof {
266        /// Bytes needed.
267        need: u64,
268        /// Actual reader exception category (`struct.error` for Python reads).
269        exception: &'static str,
270    },
271    /// UnityPyBoost's failed read, retaining the function whose public
272    /// exception class and message apply.
273    #[error("{method} out of bounds (needs {need} bytes)")]
274    BoostEof {
275        /// The C++ reader function name.
276        method: &'static str,
277        /// Bytes requested by the read.
278        need: u64,
279        /// Actual Boost exception category for this read.
280        exception: &'static str,
281    },
282    /// A negative length.
283    #[error("negative length {0}")]
284    NegativeLength(i64),
285    /// Boost's `ValueError` for an `Array` node without two children.
286    #[error("Array node must have 2 children")]
287    ArrayChildren,
288    /// Boost's `ValueError` for a `pair` node without two children.
289    #[error("Pair node must have 2 children")]
290    PairChildren,
291    /// `ReferencedObject` data with no `ref_types` to resolve it.
292    #[error("no SerializedFile.ref_types")]
293    NoRefTypes {
294        /// The reader selected by the object's byte size.
295        reader: crate::value::ReadBy,
296        /// Whether this format omits the `ref_types` attribute (below 20).
297        absent: bool,
298    },
299    /// `ReferencedObject` data whose `(class, ns, asm)` is not in `ref_types`.
300    #[error("Failed to get ref type node")]
301    RefTypeNotFound,
302    /// The pure-Python reader's array path only: an aligned `ReferencedObject`
303    /// element whose class is empty or whose matched ref type has no tree
304    /// (type trees disabled) calls `read_value(None, ...)`, an `AttributeError`
305    /// (kind `other`). UnityPyBoost and the pure-Python scalar path skip
306    /// `data` instead, as for an empty class (plan R14).
307    #[error("'NoneType' object has no attribute 'm_MetaFlag'")]
308    RefTypeNoTree,
309    /// A Python exception category, sometimes followed by its diagnostic:
310    /// malformed-child `IndexError`, aligned-array `TypeError`, attribute
311    /// access failures, or an unpack format's `struct.error`.
312    #[error("python reader: {0}")]
313    Python(&'static str),
314    /// The stream reader's refusal (a file loaded from a path): a negative
315    /// or huge `byte_start`, or a `TypelessData` length below -1 on the
316    /// pure-Python path (kind `other`).
317    #[error("{}: {}", .0.exception(), .0)]
318    Stream(StreamRefusal),
319    /// A bound from [`Limits`] on work or depth.
320    #[error(transparent)]
321    Limit(LimitError),
322    /// The input's meter or the budget refused the value's memory.
323    #[error(transparent)]
324    Charge(ChargeError),
325    /// A ref type's tree did not compile.
326    #[error(transparent)]
327    Tree(TreeError),
328}
329/// Why reading an object failed: the L2 outcome other than success.
330#[derive(Clone, Debug, PartialEq, Eq, thiserror::Error)]
331#[non_exhaustive]
332pub enum ParseError {
333    /// No tree for the class: UnityPy raises the exception `why` names
334    /// (its TPK's; review round 11: nothing told them apart).
335    #[error("no typetree for class {class_id}")]
336    NoTypeTree {
337        /// The object's class.
338        class_id: i32,
339        /// Which exception: `None` where no provider says (with no provider
340        /// at all; UnityPy always has its TPK).
341        why: Option<NoTree>,
342    },
343    /// The reader failed; no value.
344    #[error(transparent)]
345    Read(#[from] ReadError),
346    /// The read finished but did not end at `byte_size`. The value rides
347    /// along: it is what `parse_as_dict(check_read=False)` returns. Shared,
348    /// not copied, when the error is cloned (a published result is handed to
349    /// every caller), and still charged to its input while any copy lives.
350    #[error("Expected to read {expected} bytes, but only read {} bytes", .parsed.bytes_read)]
351    CheckRead {
352        /// `byte_size`.
353        expected: u32,
354        /// The full value and where the read ended.
355        parsed: Arc<Parsed>,
356    },
357    /// The object's tree did not compile.
358    #[error(transparent)]
359    Tree(#[from] TreeError),
360    /// A provider failed.
361    #[error(transparent)]
362    Provider(#[from] ProviderError),
363    /// The `MonoBehaviour` script hook's dereference of `m_Script` failed
364    /// with anything but a null pointer, which UnityPy raises
365    /// (`files/ObjectReader.py:332-350`; [`crate::env::Environment::object_tree`]).
366    /// Carried by value so reporting a failed dereference allocates nothing.
367    #[error("m_Script: {0}")]
368    Deref(crate::env::DerefError),
369}
370
371impl From<crate::budget::AllocError> for ReadDetail {
372    fn from(error: crate::budget::AllocError) -> Self {
373        Self::Charge(error.into())
374    }
375}
376
377impl From<crate::budget::AllocError> for ParseError {
378    fn from(error: crate::budget::AllocError) -> Self {
379        Self::Tree(error.into())
380    }
381}
382
383impl crate::once::CellError for ParseError {
384    fn is_transient(&self) -> bool {
385        match self {
386            Self::Read(r) => match &r.detail {
387                ReadDetail::Charge(c) => c.is_transient(),
388                ReadDetail::Tree(t) => t.is_transient(),
389                _ => false,
390            },
391            Self::Tree(t) => t.is_transient(),
392            // A provider is caller code: its failure is not the input's.
393            Self::Provider(_) => true,
394            Self::Deref(d) => d.is_transient(),
395            Self::NoTypeTree { .. } | Self::CheckRead { .. } => false,
396        }
397    }
398
399    fn is_meter_refusal(&self) -> bool {
400        match self {
401            Self::Read(r) => match &r.detail {
402                ReadDetail::Charge(c) => c.is_meter_refusal(),
403                ReadDetail::Tree(t) => t.is_meter_refusal(),
404                _ => false,
405            },
406            Self::Tree(t) => t.is_meter_refusal(),
407            Self::Deref(d) => d.is_meter_refusal(),
408            Self::Provider(_) | Self::NoTypeTree { .. } | Self::CheckRead { .. } => false,
409        }
410    }
411
412    fn heap_bytes(&self) -> u64 {
413        match self {
414            // The value's own heap rides in its `Parsed`'s charge.
415            Self::CheckRead { .. } => crate::error::heap_of(std::mem::size_of::<Parsed>() + 16),
416            Self::Provider(p) => crate::error::heap_of(p.detail.len()),
417            Self::Deref(d) => d.heap_bytes(),
418            _ => 0,
419        }
420    }
421
422    /// A [`Limits`] bound, so kind `other` (R16).
423    fn work_refused(limit: LimitError) -> Self {
424        Self::Read(ReadError {
425            kind: ReadErrorKind::Other,
426            at: 0,
427            detail: ReadDetail::Limit(limit),
428        })
429    }
430}
431
432impl ParseError {
433    /// The canonical dump's kind for this outcome. A read that ended before
434    /// its start (a negative `bytes_read`, the pure-Python reader's after a
435    /// negative `TypelessData` length) is `other`: the oracle reads the count
436    /// from the message with `(\d+)`, which takes no sign
437    /// (`tools/parity/dump_records.py` `error_kind`; plan 3.10).
438    #[must_use]
439    pub fn l2_kind(&self) -> L2Kind {
440        match self {
441            Self::NoTypeTree { .. } => L2Kind::NoTypetree,
442            Self::CheckRead { parsed, .. } if parsed.bytes_read < 0 => L2Kind::Other,
443            Self::CheckRead { .. } => L2Kind::CheckRead,
444            Self::Read(e) => match e.kind {
445                ReadErrorKind::OutOfBounds => L2Kind::OutOfBounds,
446                ReadErrorKind::NegativeLength => L2Kind::NegativeLength,
447                ReadErrorKind::RefType => L2Kind::RefType,
448                ReadErrorKind::Other => L2Kind::Other,
449            },
450            Self::Tree(_) | Self::Provider(_) | Self::Deref(_) => L2Kind::Other,
451        }
452    }
453}
454
455/// Why writing a value failed (the dump's L3 `"error"`). Each variant
456/// stands for the exceptions [`Self::exceptions`] names, the classes UnityPy
457/// 1.25.2's `write_typetree` raises there; a variant UnityPy has no
458/// counterpart for names none.
459#[derive(Clone, Debug, PartialEq, Eq, thiserror::Error)]
460#[non_exhaustive]
461pub enum WriteError {
462    /// A child name missing from the dict, or a `ReferencedObject`'s `type`
463    /// or one of its names (`KeyError`).
464    #[error("missing key {0:?}")]
465    MissingKey(RawStr),
466    /// A value of the wrong type for its node. `expected` says what the node
467    /// takes, and which exception UnityPy raises: `struct.error` for `int`
468    /// and `float`; `AttributeError` for a `str` (`value.encode`), an
469    /// attribute, a ref type with a tree (`None.m_MetaFlag`) and a `type`
470    /// that is not a dict (`getattr(typ, "class")`); `TypeError` for
471    /// `bytes`, a sized iterable (`len`) and a `ReferencedObject`'s dict
472    /// (`value[...]`); `TypeError`, `KeyError` or `IndexError` for a
473    /// sequence of two (`value[0]` of an `int`, a `dict` or a short
474    /// sequence). A modelled attribute is the writer's own refusal of a
475    /// dunder name, which UnityPy reads and may write (`PARITY.md` section
476    /// 19.3).
477    #[error("{node:?}: expected {expected}")]
478    TypeMismatch {
479        /// The node's name.
480        node: RawStr,
481        /// What the node takes.
482        expected: &'static str,
483    },
484    /// An integer outside its node's width (`struct.error`), or a finite
485    /// float that overflows `f32` (`OverflowError`).
486    #[error("{node:?}: value out of range")]
487    OutOfRange {
488        /// The node's name.
489        node: RawStr,
490    },
491    /// `ReferencedObject` data with no assets file, or an empty `ref_types`
492    /// list (the writer raises where the reader does not; `TypeTreeHelper.py:99-100`):
493    /// `ValueError`.
494    #[error("SerializedFile has no ref_types")]
495    NoRefTypes,
496    /// `ReferencedObject` data against a file with no `ref_types` attribute
497    /// ([`RefTypes::Absent`]: a `SerializedFile` below format 20, which
498    /// UnityPy never sets it on, `files/SerializedFile.py:306-308`): reading
499    /// `assetfile.ref_types` raises `AttributeError` (`TypeTreeHelper.py:99`).
500    #[error("'SerializedFile' object has no attribute 'ref_types'")]
501    NoRefTypesAttribute,
502    /// `ReferencedObject` data whose type is not in `ref_types`
503    /// (`ValueError`).
504    #[error("Referenced type not found")]
505    RefTypeNotFound,
506    /// A malformed node the writer reached: a `pair`'s or an `Array`'s
507    /// missing child (`IndexError`), or a matched ref type's rows that make
508    /// no tree, which UnityPy refuses when it parses the file (an
509    /// `IndexError` too, [`TreeError`]).
510    #[error("malformed node {0:?}")]
511    Malformed(RawStr),
512    /// The object has no tree to write with: UnityPy raises the same
513    /// exception for a write as for a read (`files/ObjectReader.py:264-307`;
514    /// the read side's [`ParseError::NoTypeTree`]).
515    #[error("no typetree for class {class_id}")]
516    NoTypeTree {
517        /// The object's class.
518        class_id: i32,
519        /// Which exception, as the read side's.
520        why: Option<NoTree>,
521    },
522    /// Resolving the object's tree failed (a tree that does not compile, a
523    /// provider's failure): the writer never ran.
524    #[error("typetree: {0}")]
525    Tree(Box<ParseError>),
526    /// A bound from [`Limits`].
527    #[error(transparent)]
528    Limit(LimitError),
529    /// The input's meter or the budget refused the output's memory.
530    #[error(transparent)]
531    Charge(ChargeError),
532}
533
534impl WriteError {
535    /// The classes, by `__name__` (`error` is `struct.error`), of the
536    /// exceptions UnityPy 1.25.2's `write_typetree` (`TypeTreeHelper.py:407-458`
537    /// and `streams/EndianBinaryWriter.py`) raises where the writer reports
538    /// this error, as the variants' docs give them; `tests/walk_fixtures.rs`
539    /// checks against this every raise in the cases, the value cases and
540    /// W2's matrix `tools/fixtures/walk.py` records.
541    /// None for an error UnityPy has no counterpart for: a bound of
542    /// [`Limits`] or a refused charge (`PARITY.md` section 19.3), a dunder
543    /// attribute ([`Self::TypeMismatch`]), and a tree that failed before the
544    /// writer ran ([`Self::Tree`]: the read side's error); a
545    /// [`Self::NoTypeTree`] with no `why` says nothing of UnityPy's.
546    #[must_use]
547    pub fn exceptions(&self) -> &'static [&'static str] {
548        match self {
549            Self::MissingKey(_) => &["KeyError"],
550            Self::TypeMismatch { expected, .. } => match *expected {
551                "int" | "float" => &["error"],
552                "str"
553                | "an object with this attribute"
554                | "a ref type with a tree"
555                | "a dict or an object with class, ns and asm" => &["AttributeError"],
556                "bytes" | "a sized iterable" | "dict" => &["TypeError"],
557                "a sequence of two" => &["TypeError", "KeyError", "IndexError"],
558                _ => &[],
559            },
560            Self::OutOfRange { .. } => &["error", "OverflowError"],
561            Self::NoRefTypes | Self::RefTypeNotFound => &["ValueError"],
562            Self::NoRefTypesAttribute => &["AttributeError"],
563            Self::Malformed(_) => &["IndexError"],
564            Self::NoTypeTree { why, .. } => match why {
565                Some(NoTree::UnknownClass) => &["KeyError"],
566                Some(NoTree::NoEntry) => &["ValueError"],
567                Some(NoTree::NoReleaseRoot) => &["AssertionError"],
568                Some(NoTree::NoVersion) => &["NotImplementedError"],
569                None => &[],
570            },
571            Self::Tree(_) | Self::Limit(_) | Self::Charge(_) => &[],
572        }
573    }
574}
575
576/// The stream reader's refusal at `at` bytes into a read (kind `other`, as
577/// the oracle maps a `ValueError` or `OverflowError` it names no kind for).
578pub(crate) fn stream_refused(at: u64, e: StreamRefusal) -> ReadError {
579    ReadError {
580        kind: ReadErrorKind::Other,
581        at,
582        detail: ReadDetail::Stream(e),
583    }
584}
585
586/// A value as a reader returns it to its parent: one that owns no heap
587/// (a scalar, a string or bytes sliced from the file), pushed as it is, or
588/// a [`Built`] list, map, tuple or run that carries its charge (plan 3.9).
589/// A plain scalar costs no charge record, so the hot path stays one move.
590#[derive(Debug)]
591pub(crate) enum Out {
592    /// Owns no heap.
593    Plain(Value),
594    /// Owns heap, with its charge.
595    Built(Built),
596}
597
598impl Out {
599    /// Appends to a list's or a tuple's items, the charge going along.
600    #[inline]
601    pub(crate) fn push_to(self, items: &mut MeteredVec<Value>) -> Result<(), ChargeError> {
602        match self {
603            Self::Plain(v) => items.push(v),
604            Self::Built(b) => items.push_built(b),
605        }
606    }
607
608    /// Appends a dict entry, the charge going along.
609    #[inline]
610    pub(crate) fn push_entry(
611        self,
612        entries: &mut MeteredVec<(NodeId, Value)>,
613        key: NodeId,
614    ) -> Result<(), ChargeError> {
615        match self {
616            Self::Plain(v) => entries.push((key, v)),
617            Self::Built(b) => entries.push_entry(key, b),
618        }
619    }
620
621    /// Replaces entry `pos`'s value (`PyDict_SetItem` on a key already in
622    /// the dict: first position, last value).
623    pub(crate) fn set_entry(self, entries: &mut MeteredVec<(NodeId, Value)>, pos: usize) {
624        match self {
625            Self::Plain(v) => {
626                if let Some(e) = entries.as_mut_slice().get_mut(pos) {
627                    e.1 = v;
628                }
629            }
630            Self::Built(b) => {
631                entries.set_entry(pos, b);
632            }
633        }
634    }
635
636    /// The `Built` a [`crate::value::ValueBuilder::finish`] takes. A plain
637    /// value owns no heap, so `scalar` always takes it; were one to own
638    /// heap, the read fails rather than keep it uncharged.
639    pub(crate) fn into_built(
640        self,
641        builder: &crate::value::ValueBuilder,
642        at: u64,
643    ) -> Result<Built, ReadError> {
644        match self {
645            Self::Built(b) => Ok(b),
646            Self::Plain(v) => builder.scalar(v).map_err(|_| ReadError {
647                kind: ReadErrorKind::Other,
648                at,
649                detail: ReadDetail::Python("a plain value owned heap"),
650            }),
651        }
652    }
653}
654
655/// UnityPyBoost's float widening: `PyFloat_FromDouble((double)f)`
656/// (UnityPy TypeTreeHelper.cpp:172-175) on x86-64 sets a signalling NaN's
657/// quiet bit; [`FloatMode::Lossless`] keeps the file's bits.
658pub(crate) fn f32_bits(bits: u32, mode: FloatMode) -> u32 {
659    let nan = bits & 0x7f80_0000 == 0x7f80_0000 && bits & 0x007f_ffff != 0;
660    if nan && mode == FloatMode::UnityPy {
661        bits | 0x0040_0000
662    } else {
663        bits
664    }
665}
666
667/// An `i64` as a Python `int`'s value variant.
668pub(crate) fn int(v: i64) -> Value {
669    Value::Int(v)
670}
671
672/// A `u64` as a Python `int`'s value variant: `UInt` only above `i64::MAX`.
673pub(crate) fn uint(v: u64) -> Value {
674    i64::try_from(v).map_or(Value::UInt(v), Value::Int)
675}
676
677/// `CPython` 3.11's `PyUnicode_GET_LENGTH(cls) == 0` on whatever object the
678/// reader made for a `ReferencedObject`'s `class` (UnityPy
679/// TypeTreeHelper.cpp:637): the macro reads the third machine word of the
680/// object, which is a `str`'s length, an `int`'s or a `bool`'s `ob_size`
681/// (0 only for zero and `False`), a `float`'s value bits, a `bytes`',
682/// `list`'s or `tuple`'s `ob_size` and a `dict`'s `ma_used`; so it is 0
683/// exactly for an empty string, `0`, `False`, `+0.0`, and an empty bytes,
684/// list, tuple or dict (plan R14).
685pub(crate) fn py_size_field_is_zero(v: &Value) -> bool {
686    match v {
687        Value::Str(s) => s.is_empty(),
688        Value::Int(i) => *i == 0,
689        Value::UInt(_) => false,
690        Value::Bool(b) => !*b,
691        Value::F32(b) => f64::from(f32::from_bits(*b)).to_bits() == 0,
692        Value::F64(b) => *b == 0,
693        Value::Bytes(b) => b.is_empty(),
694        Value::Prims(p) => p.is_empty(),
695        Value::List(l) => l.is_empty(),
696        Value::Tuple(t) => t.is_empty(),
697        Value::Dict(m) => m.is_empty(),
698    }
699}
700
701/// A [`Limits`] bound crossed while reading: kind `other` (R16).
702pub(crate) fn limit_error(at: u64, kind: LimitKind, value: u64, max: u64) -> ReadError {
703    ReadError {
704        kind: ReadErrorKind::Other,
705        at,
706        detail: ReadDetail::Limit(LimitError::refused(kind, value, max)),
707    }
708}
709
710/// A refused charge while reading: kind `other` (plan 3.10, "Bounds").
711pub(crate) fn charge_error(at: u64, e: ChargeError) -> ReadError {
712    ReadError {
713        kind: ReadErrorKind::Other,
714        at,
715        detail: ReadDetail::Charge(e),
716    }
717}
718
719/// The capacity a list of `len` elements may reserve before its elements
720/// are read: `min(len, remaining / min_size, room)`, `room` what the read's
721/// open lists leave of `max_prealloc` (plan 3.10, "Bounds";
722/// `Work::first_room`); it then grows by [`grow_step`].
723pub(crate) fn first_reserve(len: usize, remaining: usize, min_size: u32, room: usize) -> usize {
724    let backed = if min_size == 0 {
725        usize::MAX
726    } else {
727        remaining / (min_size as usize)
728    };
729    len.min(backed).min(room)
730}
731
732/// Before pushing element `items.len()` of `len`: grows a full vector
733/// geometrically, never past `len`, so the list holds no spare capacity once
734/// it is complete, and, past its first reservation, no more than twice what
735/// it has filled; growths that move it copy each element a bounded number
736/// of times (review round 7's sweep: growing by exact steps of
737/// `max_prealloc`, a list of `n` elements made `n` / `max_prealloc` moves,
738/// some `n`² / `max_prealloc` copies in all, unless the allocator grew it
739/// in place).
740pub(crate) fn grow_step<T>(items: &mut MeteredVec<T>, len: usize) -> Result<(), ChargeError> {
741    if items.len() < items.capacity() {
742        return Ok(());
743    }
744    items.reserve_within(1, len)
745}