Skip to main content

unityrs_core/env/
listing.rs

1// Ported from UnityPy 1.25.2 (MIT): UnityPy/environment.py, UnityPy/classes/PPtr.py. See THIRD_PARTY_LICENSES.
2//! UnityPy's `env.files` dict ([`Files`]) and the listings that walk it:
3//! [`Environment::files`] and [`Environment::objects`]. "Module docs"
4//! below are [`super`]'s.
5
6use std::collections::HashMap;
7use std::fmt;
8use std::mem::size_of;
9use std::sync::Arc;
10
11use super::Environment;
12use super::held::{self, Held};
13use super::watch::{Table, Under};
14use crate::error::Error;
15use crate::files::{File, SerializedFile};
16use crate::limits::{Charge, HASH_TABLE_SHARES, Meter};
17use crate::object::ObjectRef;
18use crate::pystr::py_lower;
19use crate::raw::RawStr;
20
21/// The iterator [`Environment::objects`] returns: a handle per nesting
22/// level (the position of the last `files` entry it stepped into, the
23/// bundle, the entry, the object index).
24pub struct Objects<'a> {
25    env: &'a Environment,
26    after: Option<u64>,
27    bundles: Vec<(File, usize)>,
28    current: Option<(Arc<SerializedFile>, usize)>,
29}
30
31const _: () = crate::send_sync::<Objects<'static>>();
32
33impl Objects<'_> {
34    /// Steps into `file`: a `SerializedFile`'s objects, a bundle's `files`
35    /// dict; anything else holds no objects (`environment.py:190-204`).
36    fn enter(&mut self, file: File) {
37        match file {
38            File::Serialized(sf) => self.current = Some((sf, 0)),
39            f @ (File::Bundle(_) | File::Web(_)) => self.bundles.push((f, 0)),
40            File::Raw(_) => {}
41        }
42    }
43}
44
45impl Iterator for Objects<'_> {
46    type Item = Result<ObjectRef, Error>;
47
48    fn next(&mut self) -> Option<Self::Item> {
49        loop {
50            if let Some((sf, k)) = &mut self.current {
51                if let Some(&idx) = sf.object_order().get(*k) {
52                    *k += 1;
53                    if let Some(o) = ObjectRef::new(sf.clone(), idx) {
54                        return Some(Ok(o));
55                    }
56                    continue;
57                }
58                self.current = None;
59            }
60            if let Some((b, j)) = self.bundles.last_mut() {
61                let Some(dir_index) = b.container_files().get(*j).map(|s| s.dir_index) else {
62                    self.bundles.pop();
63                    continue;
64                };
65                *j += 1;
66                let b = b.clone();
67                match b.container_entry(dir_index) {
68                    Ok(f) => self.enter(f),
69                    Err(e) => return Some(Err(e)),
70                }
71                continue;
72            }
73            let (at, entry) = self.env.file_after(self.after)?;
74            self.after = Some(at);
75            // `search`: a dependency file holds no listed objects.
76            if !entry.is_dependency {
77                self.enter(entry.file);
78            }
79        }
80    }
81}
82
83impl fmt::Debug for Objects<'_> {
84    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
85        f.debug_struct("Objects").finish_non_exhaustive()
86    }
87}
88
89/// One entry of [`Environment::files`]: UnityPy's `env.files[name]`, with
90/// the file's `is_dependency` flag.
91#[derive(Clone, Debug)]
92pub struct FileEntry {
93    /// The key: the source's name for a caller's load, the name asked for a
94    /// resource fallback's, the resolved source's name for `find_file`'s
95    /// (UnityPy keys the joined path).
96    pub name: RawStr,
97    /// The file.
98    pub file: File,
99    /// True for a `find_file` load with `is_dependency`
100    /// ([`Environment::objects`] and [`Environment::container`] skip it),
101    /// false for every other, and for a raw reader, to which UnityPy's
102    /// `parse_file` gives no `is_dependency` (`getattr(f, "is_dependency",
103    /// False)` reads it false).
104    pub is_dependency: bool,
105}
106
107const _: () = crate::send_sync::<FileEntry>();
108
109/// The iterator [`Environment::files`] returns: a cursor at the position
110/// of the last entry it yielded, which entries listed meanwhile do not
111/// disturb.
112#[derive(Debug)]
113pub struct FileEntries<'a> {
114    env: &'a Environment,
115    after: Option<u64>,
116}
117
118const _: () = crate::send_sync::<FileEntries<'static>>();
119
120impl Iterator for FileEntries<'_> {
121    type Item = FileEntry;
122
123    fn next(&mut self) -> Option<FileEntry> {
124        let (at, entry) = self.env.file_after(self.after)?;
125        self.after = Some(at);
126        Some(entry)
127    }
128}
129
130/// One `files` entry, with the loads of its rank and the charge for its
131/// share of the list and the indexes.
132struct Listed {
133    entry: Option<FileEntry>,
134    /// The key's position: the least load that listed it.
135    position: u64,
136    /// The load whose file is the value: the greatest that listed the key.
137    value: u64,
138    _charge: Charge,
139}
140
141/// The value under a matching key, including a ZIP's explicit None.
142pub(super) enum FileMatch {
143    File(File),
144    ZipNone,
145}
146
147/// `env.files`: a dict by rank, as the registry is ([`super::registry`]'s
148/// module docs, "Ranks"): each key at the least number of the loads that
149/// listed it, with the file of the greatest, whatever the order the loads
150/// list in (review round 16: the list took the order the threads listed
151/// in while the registry took the loads', so a load that took the lower
152/// number but listed last won `files` and lost the registry, for good).
153/// A list by position, an index of each key's position, and each key
154/// lower-cased to the least position of a key that lowers to it (the scan
155/// of `files` a top-level file's pointer makes, rule 4, as one lookup). A
156/// load's number is the position of at most the one key it lists, so
157/// positions are distinct.
158#[derive(Default)]
159pub(super) struct Files {
160    list: Vec<Listed>,
161    index: HashMap<RawStr, u64>,
162    lowered: HashMap<RawStr, u64>,
163    /// The running container preload walks' flags under lowered keys, set
164    /// in the step that publishes a key's change (`super::watch`).
165    watched: Table,
166}
167
168impl Files {
169    /// The entry at `position`.
170    fn at(&self, position: u64) -> Option<&Listed> {
171        let i = self
172            .list
173            .binary_search_by_key(&position, |l| l.position)
174            .ok()?;
175        self.list.get(i)
176    }
177
178    /// Key `name`, at `position`, listed again by load `load`
179    /// ([`Environment::list`]): it takes `file` (and `is_dependency`) only
180    /// if `load` is greater than its value's load, and moves to `load`, and
181    /// so does the least position of its lowered key `lowered`, if that is
182    /// less than its position. Returns the file it does not keep.
183    fn relist(
184        &mut self,
185        name: &RawStr,
186        position: u64,
187        file: Option<File>,
188        is_dependency: bool,
189        load: u64,
190        lowered: &RawStr,
191    ) -> Option<File> {
192        let Ok(i) = self.list.binary_search_by_key(&position, |l| l.position) else {
193            // Never: every key of the index is listed at its position.
194            return file;
195        };
196        let Some(entry) = self.list.get_mut(i) else {
197            return file;
198        };
199        let unused = if load > entry.value {
200            entry.value = load;
201            std::mem::replace(
202                &mut entry.entry,
203                file.map(|file| FileEntry {
204                    name: name.clone(),
205                    file,
206                    is_dependency,
207                }),
208            )
209            .map(|e| e.file)
210        } else {
211            file
212        };
213        if load < position {
214            let mut moved = self.list.remove(i);
215            moved.position = load;
216            let at = self.list.partition_point(|l| l.position < load);
217            self.list.insert(at, moved);
218            if let Some(p) = self.index.get_mut(name.as_bytes()) {
219                *p = load;
220            }
221            if let Some(least) = self.lowered.get_mut(lowered.as_bytes()) {
222                *least = (*least).min(load);
223            }
224        }
225        unused
226    }
227}
228
229impl Under for std::sync::RwLock<Files> {
230    /// Under the listing's write lock, which publishes every entry
231    /// ([`Environment::list`]).
232    fn with_table(&self, f: &mut dyn FnMut(&mut Table)) {
233        f(&mut held::write(self).watched);
234    }
235}
236
237/// What one listed load costs the `files` tables: three elements of the
238/// list and [`HASH_TABLE_SHARES`] buckets of each index (as a registry
239/// slot's share, [`registry`]).
240///
241/// [`registry`]: super::registry
242const LISTED_SHARE: u64 = 3 * size_of::<Listed>() as u64
243    + 2 * HASH_TABLE_SHARES * (size_of::<RawStr>() + size_of::<u64>() + 1) as u64;
244
245/// A listing charged and not yet published ([`Environment::charge_listing`]):
246/// its key, the key lowered, and its share of the tables.
247pub(super) struct Listing {
248    name: RawStr,
249    lowered: RawStr,
250    charge: Charge,
251}
252
253impl Environment {
254    fn files_read(&self) -> Held<std::sync::RwLockReadGuard<'_, Files>> {
255        held::read(&self.inner.files)
256    }
257
258    fn files_write(&self) -> Held<std::sync::RwLockWriteGuard<'_, Files>> {
259        held::write(&self.inner.files)
260    }
261
262    /// The entries of both tables of the walks' flags (the registry's and
263    /// the listing's), for a test.
264    #[cfg(test)]
265    pub(super) fn watch_entries(&self) -> usize {
266        self.inner.registry.watch_room().0 + self.files_read().watched.room().0
267    }
268
269    /// The first entry after position `after` (the first of all for
270    /// `None`), and its position.
271    fn file_after(&self, after: Option<u64>) -> Option<(u64, FileEntry)> {
272        let files = self.files_read();
273        let i = after.map_or(0, |a| files.list.partition_point(|l| l.position <= a));
274        files
275            .list
276            .get(i..)?
277            .iter()
278            .find_map(|l| l.entry.clone().map(|e| (l.position, e)))
279    }
280
281    /// Adds `file` to `files` under `name` with dict semantics by rank, as
282    /// the listing of load `load` ([`Files`]): a new key takes its place at
283    /// `load`; a known key takes `file` only if `load` is greater than its
284    /// value's load, and moves to `load` if that is less than its
285    /// position; the file it does not keep is dropped after the lock.
286    /// Charged to `meter`, the loaded file's: a new key's share of the list and the
287    /// indexes, and its lowered copy for rule 4's lookup (a key copied from
288    /// a resolver's name carries its own charge). Every load is charged so,
289    /// a caller's included (review round 2: a caller's load charged
290    /// nothing, and its lowered key was built on an unlimited meter). The
291    /// lowered key's change sets the running container preload walks'
292    /// flags under it in the step that publishes it, under the write lock
293    /// (`super::watch`, invariant W1: review round 5 decided before the
294    /// publication whether a walk ran, so a walk that started in between
295    /// kept a stale miss; review round 14 set the flags after the lock, so
296    /// a walk could find the entry while its kept miss of it still held).
297    pub(super) fn list(
298        &self,
299        name: RawStr,
300        file: File,
301        is_dependency: bool,
302        load: u64,
303        meter: &Arc<Meter>,
304    ) -> Result<(), Error> {
305        let listing = Self::charge_listing(name, meter)?;
306        self.publish_listing(listing, file, is_dependency, load);
307        Ok(())
308    }
309
310    /// The charged half of [`Self::list`]: every charge a listing makes,
311    /// to `meter`, before anything is published (a dependency's load under
312    /// `Lazy` charges its listing before it publishes its keys, the
313    /// registry's module docs, "A failed dependency load").
314    pub(super) fn charge_listing(name: RawStr, meter: &Arc<Meter>) -> Result<Listing, Error> {
315        let charge = meter.charge(LISTED_SHARE)?;
316        // The lowered key: a new key's index entry, and in every case the
317        // key a walk's lookup watches (`super::watch`).
318        let lowered = py_lower(&name, meter)?;
319        Ok(Listing {
320            name,
321            lowered,
322            charge,
323        })
324    }
325
326    /// The published half of [`Self::list`], which nothing can refuse.
327    pub(super) fn publish_listing(
328        &self,
329        listing: Listing,
330        file: File,
331        is_dependency: bool,
332        load: u64,
333    ) {
334        self.publish_value(listing, Some(file), is_dependency, load);
335    }
336
337    /// A ZIP load assigns None after its members finish; keep its dict
338    /// position while releasing the previous file and excluding its objects.
339    pub(super) fn list_zip_none(&self, name: RawStr, meter: &Arc<Meter>) -> Result<(), Error> {
340        let listing = Self::charge_listing(name, meter)?;
341        let load = self.inner.registry.next_load();
342        self.publish_value(listing, None, false, load);
343        Ok(())
344    }
345
346    fn publish_value(&self, listing: Listing, file: Option<File>, is_dependency: bool, load: u64) {
347        let Listing {
348            name,
349            lowered,
350            charge,
351        } = listing;
352        let key_hash = self.inner.registry.watches().hash(lowered.as_bytes());
353        #[cfg(test)]
354        self.inner.registry.hook(super::registry::Hook::Listing);
355        let unused = {
356            let mut files = self.files_write();
357            let unused = if let Some(&position) = files.index.get(name.as_bytes()) {
358                files.relist(&name, position, file, is_dependency, load, &lowered)
359            } else {
360                let at = files.list.partition_point(|l| l.position < load);
361                files.list.insert(
362                    at,
363                    Listed {
364                        entry: file.map(|file| FileEntry {
365                            name: name.clone(),
366                            file,
367                            is_dependency,
368                        }),
369                        position: load,
370                        value: load,
371                        _charge: charge,
372                    },
373                );
374                files.index.insert(name, load);
375                let least = files.lowered.entry(lowered).or_insert(load);
376                *least = (*least).min(load);
377                None
378            };
379            // The entry and the setting of the walks' flags under its
380            // lowered key are one step (`super::watch`, W1).
381            files.watched.notify(key_hash);
382            unused
383        };
384        #[cfg(test)]
385        self.inner.registry.hook(super::registry::Hook::Listed);
386        drop(unused);
387    }
388
389    /// `files`, in the order of the keys' positions (the least load that
390    /// listed each, `listing.rs`'s `Files`), as UnityPy's dict iterates when the loads
391    /// are made one after another in the order of their numbers: one entry per caller load, and with
392    /// [`EnvOptions::keep_resolver_loads`] one per file the resolver loaded
393    /// (module docs), a repeated key replacing the value in place. Each
394    /// entry is charged to its file's meter (its share of the list and the
395    /// indexes, its lowered key, and a resolver load's key copy, as a
396    /// registry slot's are, [`registry`]). An iterator, as the other
397    /// listings are (module docs): it takes the lock briefly per entry and
398    /// allocates nothing but the entry it yields.
399    ///
400    /// [`EnvOptions::keep_resolver_loads`]: super::EnvOptions::keep_resolver_loads
401    /// [`registry`]: super::registry
402    #[must_use]
403    pub fn files(&self) -> FileEntries<'_> {
404        FileEntries {
405            env: self,
406            after: None,
407        }
408    }
409
410    /// The first `files` entry whose key lower-cases to `clean` (the
411    /// Environment as a top-level file's container, rule 4), by the lowered
412    /// index ([`Files`]). An existing ZIP None value is a matching key: the
413    /// sibling scan stops there and must not fall back to the CAB registry
414    /// (UnityPy/classes/PPtr.py:75-88).
415    pub(super) fn files_match(&self, clean: &RawStr) -> Option<FileMatch> {
416        let files = self.files_read();
417        let at = *files.lowered.get(clean.as_bytes())?;
418        files.at(at).map(|l| match &l.entry {
419            Some(entry) => FileMatch::File(entry.file.clone()),
420            None => FileMatch::ZipNone,
421        })
422    }
423
424    /// `objects`: every object of every non-dependency file of
425    /// [`Self::files`], in its order, as an iterator (module docs: no
426    /// allocation per object). A file that fails to load or parse on the way
427    /// yields its error.
428    #[must_use]
429    pub fn objects(&self) -> Objects<'_> {
430        Objects {
431            env: self,
432            after: None,
433            bundles: Vec::new(),
434            current: None,
435        }
436    }
437}