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}