Skip to main content

unityrs_core/
provider.rs

1// Ported from UnityPy 1.25.2 (MIT): UnityPy/helpers/Tpk.py, UnityPy/files/ObjectReader.py. See THIRD_PARTY_LICENSES.
2//! Typetree providers for stripped files, keyed by `(class, version)`.
3//!
4//! UnityPy's order (`files/ObjectReader.py:285-307`): an explicit `nodes=`
5//! tree; else the type record's own tree; else the class tree for
6//! `(class_id, version)` from the TPK (`helpers/Tpk.py:42-55`), and, only
7//! for that TPK tree (`generate_monobehaviour_node` is called inside
8//! `if not node:`, `ObjectReader.py:296-304`), the script generator's tree
9//! when its root is `MonoBehaviour` and the generator answers. An embedded
10//! or explicit `MonoBehaviour` tree is never replaced. Only a `ValueError` is
11//! swallowed there; the script lookup dereferences `m_Script` through the
12//! Environment, so it lives in [`crate::env::Environment::object_tree`], and
13//! runs only when a provider [`TypeTreeProvider::accepts_scripts`]. The cache key is the class and the packed version
14//! integer, as UnityPy's `CLASSES_CACHE` is (`Tpk.py:16`, `:44`): rabex keys
15//! by class alone, so the first version to ask fixes a class's tree for every
16//! later version (`docs/spikes/rabex.md` section 5).
17//! The TPK itself is not here: `unityrs-tpk` (package A) loads one from a
18//! path and implements [`TypeTreeProvider`]. With no provider, a stripped
19//! object is `no_typetree`. Where no provider has a class's tree, which of
20//! UnityPy's exceptions that is ([`NoTree`]: the TPK's `KeyError`,
21//! `ValueError` or `AssertionError`, or the comparison's
22//! `NotImplementedError` for a file with no version) is
23//! [`ProviderChain::why_none`]'s answer (review round 11: nothing public
24//! told them apart, and a binding must raise UnityPy's).
25//! **The cache.** [`ProviderChain`] caches *answers only*, as UnityPy does
26//! (`Tpk.py:42-54` raises before `CLASSES_CACHE[key] = node` on a miss): a
27//! miss is asked again next time, so input-chosen keys that find nothing
28//! leave nothing behind. The key's class and version are still the input's
29//! choice, and one context's chain outlives every input it reads, so the
30//! cache is bounded in entries and bytes ([`ProviderChain::with_cache_bound`]);
31//! when full it stops adding, which changes no answer. A lookup reads the
32//! cache with a key *borrowed* from the request, so a hit (or a miss) copies
33//! nothing, however long the request's script names are. An answer is kept
34//! only when the cache has room for it, and that is decided from the
35//! borrowed request (its key's size, whether it is already cached, whether
36//! the cache is full) before anything is copied: only an answer that is
37//! kept copies its key's strings, so a key over the byte bound, or any key
38//! once the cache is full, costs no copy, a cached key never keeps an
39//! input's buffer alive, and the copies count against the cache's byte
40//! bound. Each entry is counted at four buckets of the table, which covers
41//! the table at rest and while it doubles (`limits::HASH_TABLE_SHARES`).
42//! A provider is caller code: the chain calls it with no lock held, so a
43//! provider may itself call [`ProviderChain::lookup`].
44//!
45use std::borrow::Borrow;
46use std::collections::HashMap;
47use std::fmt;
48use std::hash::{Hash, Hasher};
49use std::mem::size_of;
50use std::sync::{Arc, RwLock};
51
52use bytes::Bytes;
53
54use crate::limits::{HASH_TABLE_SHARES, heap_cost};
55use crate::raw::RawStr;
56use crate::typetree::Tree;
57use crate::typetree::commonstring::CommonStrings;
58use crate::version::{Packed, UnityVersion};
59
60mod exception;
61pub mod generator;
62mod no_tree;
63pub use exception::PythonException;
64
65pub use no_tree::NoTree;
66
67/// A `MonoBehaviour`'s script, for script-tree providers.
68#[derive(Clone, Debug, PartialEq, Eq, Hash)]
69pub struct ScriptIdent {
70    /// `m_AssemblyName`.
71    pub assembly: RawStr,
72    /// `m_Namespace`.
73    pub namespace: RawStr,
74    /// `m_ClassName`.
75    pub class: RawStr,
76}
77
78/// What a provider is asked for.
79#[derive(Clone, Copy, Debug)]
80pub struct TreeRequest<'a> {
81    /// The object's class.
82    pub class_id: i32,
83    /// The file's version (chain 2).
84    pub version: &'a UnityVersion,
85    /// For a `MonoBehaviour` whose `m_Script` resolved: its script.
86    pub script: Option<&'a ScriptIdent>,
87}
88
89/// A provider failure.
90///
91/// Construct with [`ProviderError::new`] and set optional provenance fields;
92/// the struct may gain fields in future releases.
93/// ```compile_fail,E0639
94/// use unityrs_core::provider::ProviderError;
95/// let error = ProviderError {
96///     provider: "custom", detail: "failure".into(),
97///     limit: None, memory: None, allocator: None,
98/// };
99/// ```
100#[derive(Clone, Debug, PartialEq, Eq, thiserror::Error)]
101#[error("{provider}: {detail}")]
102#[non_exhaustive]
103pub struct ProviderError {
104    /// Optional Python exception type, message and ancestry from a generator. Only
105    /// `ValueError` and its subclasses are swallowed by MonoBehaviour fallback.
106    pub python_exception: Option<PythonException>,
107    /// The provider's name.
108    pub provider: &'static str,
109    /// What failed. Shared, so a clone allocates nothing: a provider keeps
110    /// each entry's failure and hands every later request a clone of it.
111    pub detail: Arc<str>,
112    /// The bound the failure crossed, when it was one (a TPK tree deeper
113    /// than [`crate::limits::Limits::max_tree_depth`] is
114    /// [`crate::LimitKind::TreeDepth`]); `detail` is then its message.
115    pub limit: Option<crate::LimitError>,
116    /// The refusal, when the failure was memory the provider was refused (by
117    /// the allocator, or a budget); `detail` is then its message. It depends
118    /// on what else was held at that moment, not on the request, so a
119    /// provider never keeps it as the request's answer (the next ask tries
120    /// again), and a reader treats it as the caller's out-of-memory, never
121    /// as a missing tree (the canonical dump's `crash` record, the oracle's
122    /// `MemoryError`).
123    pub memory: Option<crate::budget::BudgetExceeded>,
124    /// An allocator refusal, separate from a provider budget refusal. No
125    /// additional heap storage is needed to preserve its provenance.
126    pub allocator: Option<crate::budget::AllocError>,
127}
128
129impl ProviderError {
130    /// A provider failure with no limit or memory refusal attached.
131    /// Set the corresponding public field when the failure has provenance.
132    #[must_use]
133    pub fn new(provider: &'static str, detail: Arc<str>) -> Self {
134        Self {
135            python_exception: None,
136            provider,
137            detail,
138            limit: None,
139            memory: None,
140            allocator: None,
141        }
142    }
143}
144
145/// A source of class (or script) trees.
146pub trait TypeTreeProvider: Send + Sync + fmt::Debug {
147    /// A short name; the dump's `l2.source` is `"tpk"` for the TPK provider.
148    fn name(&self) -> &'static str;
149    /// The tree for `req`, or `Ok(None)` wherever UnityPy builds no node
150    /// list, which the caller turns into `no_typetree`. For a TPK that is
151    /// four cases: a class the TPK does not hold (`KeyError`); a version
152    /// below the class's first entry, and a picked entry that is `None` (the
153    /// class removed at that version), both `ValueError`
154    /// (`helpers/Tpk.py:472-481`); and a picked entry with no release root
155    /// (`AssertionError`, `Tpk.py:64`), which [`Self::why_none`] tells
156    /// apart. The pick is UnityPy's floor over
157    /// **every** entry in its stored order, `None` and release-less entries
158    /// included: a provider never steps back past one of them to an earlier
159    /// entry that has a tree.
160    /// Every request that maps to one tree of the provider's data gets the
161    /// same `Arc` (UnityPy's `NODES_CACHE`, `Tpk.py:58-88`, which shares one
162    /// tree among the TPK class entries of one class record; the TPK
163    /// provider shares one among the entries of one release root), so the
164    /// trees a chain caches are bounded by the provider's data, not by the
165    /// versions an input names.
166    fn tree(&self, req: &TreeRequest<'_>) -> Result<Option<Arc<Tree>>, ProviderError>;
167    /// Why the class tree of `class_id` at `version` is none ([`NoTree`]),
168    /// where [`Self::tree`] answers `Ok(None)`; `version` is `None` for a
169    /// file below format 7, which [`Self::tree`] is never asked about. `None`
170    /// where the provider has the tree, or does not say (the default).
171    fn why_none(&self, class_id: i32, version: Option<&UnityVersion>) -> Option<NoTree> {
172        let _ = (class_id, version);
173        None
174    }
175    /// Whether this provider answers script requests (`TreeRequest::script`):
176    /// UnityPy's `env.typetree_generator`. Only then does the Environment
177    /// dereference a `MonoBehaviour`'s `m_Script` (P3; the TPK provider does not).
178    fn accepts_scripts(&self) -> bool {
179        false
180    }
181    /// The common strings blob typetrees index (UnityPy's
182    /// `get_common_strings()`, its TPK's table), when this provider has them:
183    /// a TPK provider does.
184    fn common_strings(&self) -> Option<&CommonStrings> {
185        None
186    }
187}
188
189/// Where an object's tree came from.
190#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
191pub enum TreeSource {
192    /// The type record's own tree (`"embedded"`).
193    Embedded,
194    /// A provider, by name (`"tpk"` for the TPK).
195    Provider(&'static str),
196    /// A `nodes=` override.
197    Explicit,
198}
199
200/// A resolved tree.
201#[derive(Clone, Debug)]
202pub struct TreeRef {
203    /// The tree.
204    pub tree: Arc<Tree>,
205    /// Its source.
206    pub source: TreeSource,
207}
208
209/// A cache key, owned or borrowed from a request: UnityPy's
210/// `(class, packed version)` plus the script.
211trait KeyView {
212    fn class_id(&self) -> i32;
213    fn packed(&self) -> &Packed;
214    fn script(&self) -> Option<[&[u8]; 3]>;
215}
216
217impl Hash for dyn KeyView + '_ {
218    fn hash<H: Hasher>(&self, h: &mut H) {
219        self.class_id().hash(h);
220        self.packed().hash(h);
221        self.script().hash(h);
222    }
223}
224
225impl PartialEq for dyn KeyView + '_ {
226    fn eq(&self, other: &Self) -> bool {
227        self.class_id() == other.class_id()
228            && self.packed() == other.packed()
229            && self.script() == other.script()
230    }
231}
232
233impl Eq for dyn KeyView + '_ {}
234
235/// The key an answer is kept under: its strings copied out of the input's
236/// buffer.
237struct CacheKey {
238    class_id: i32,
239    packed: Packed,
240    script: Option<[Bytes; 3]>,
241}
242
243#[cfg(test)]
244thread_local! {
245    /// Keys copied on this thread (the tests count them).
246    static KEY_COPIES: std::cell::Cell<usize> = const { std::cell::Cell::new(0) };
247}
248
249impl CacheKey {
250    fn copy_of(req: &TreeRequest<'_>) -> Self {
251        #[cfg(test)]
252        KEY_COPIES.with(|n| n.set(n.get() + 1));
253        let own = |s: &RawStr| Bytes::copy_from_slice(s.as_bytes());
254        Self {
255            class_id: req.class_id,
256            packed: req.version.packed().clone(),
257            script: req
258                .script
259                .map(|s| [own(&s.assembly), own(&s.namespace), own(&s.class)]),
260        }
261    }
262}
263
264impl KeyView for CacheKey {
265    fn class_id(&self) -> i32 {
266        self.class_id
267    }
268    fn packed(&self) -> &Packed {
269        &self.packed
270    }
271    fn script(&self) -> Option<[&[u8]; 3]> {
272        self.script
273            .as_ref()
274            .map(|[a, n, c]| [&a[..], &n[..], &c[..]])
275    }
276}
277
278impl Hash for CacheKey {
279    fn hash<H: Hasher>(&self, h: &mut H) {
280        (self as &dyn KeyView).hash(h);
281    }
282}
283
284impl PartialEq for CacheKey {
285    fn eq(&self, other: &Self) -> bool {
286        (self as &dyn KeyView) == (other as &dyn KeyView)
287    }
288}
289
290impl Eq for CacheKey {}
291
292impl<'a> Borrow<dyn KeyView + 'a> for CacheKey {
293    fn borrow(&self) -> &(dyn KeyView + 'a) {
294        self
295    }
296}
297
298/// A request's key, borrowed: looking it up copies nothing.
299struct RequestKey<'r, 'a>(&'r TreeRequest<'a>);
300
301impl KeyView for RequestKey<'_, '_> {
302    fn class_id(&self) -> i32 {
303        self.0.class_id
304    }
305    fn packed(&self) -> &Packed {
306        self.0.version.packed()
307    }
308    fn script(&self) -> Option<[&[u8]; 3]> {
309        self.0.script.map(|s| {
310            [
311                s.assembly.as_bytes(),
312                s.namespace.as_bytes(),
313                s.class.as_bytes(),
314            ]
315        })
316    }
317}
318
319type CacheValue = (Arc<Tree>, &'static str);
320
321#[derive(Default)]
322struct Cache {
323    map: HashMap<CacheKey, CacheValue>,
324    bytes: u64,
325}
326
327/// Providers in order, with a bounded cache of their answers keyed by
328/// `(class, packed version, script)` (module docs).
329pub struct ProviderChain {
330    providers: Vec<Arc<dyn TypeTreeProvider>>,
331    cache: RwLock<Cache>,
332    max_entries: usize,
333    max_bytes: u64,
334}
335
336/// One bucket of the cache's table: a key, a value and its control byte.
337const BUCKET: u64 = (size_of::<CacheKey>() + size_of::<CacheValue>() + 1) as u64;
338
339/// What keeping the answer to `req` costs, computed from the borrowed
340/// request before anything is copied: [`HASH_TABLE_SHARES`] buckets of the
341/// table (at rest and while it doubles), plus the heap its key would own
342/// (each copied string and a big version's limbs, at [`heap_cost`]).
343fn entry_cost(req: &TreeRequest<'_>) -> u64 {
344    let len = |n: usize| heap_cost(u64::try_from(n).unwrap_or(u64::MAX));
345    let strings = req.script.map_or(0, |s| {
346        len(s.assembly.len())
347            .saturating_add(len(s.namespace.len()))
348            .saturating_add(len(s.class.len()))
349    });
350    (HASH_TABLE_SHARES * BUCKET)
351        .saturating_add(strings)
352        .saturating_add(len(req.version.packed().heap_bytes()))
353}
354
355impl ProviderChain {
356    /// The cache's default bound in entries: far more than a TPK has
357    /// classes at the versions one run meets.
358    pub const DEFAULT_CACHE_ENTRIES: usize = 1 << 16;
359    /// The cache's default bound in bytes.
360    pub const DEFAULT_CACHE_BYTES: u64 = 64 << 20;
361
362    /// No providers: stripped objects are `no_typetree`.
363    #[must_use]
364    pub fn empty() -> Self {
365        Self::new(Vec::new())
366    }
367
368    /// Providers asked in order; the first answer wins. The cache has the
369    /// default bounds.
370    #[must_use]
371    pub fn new(providers: Vec<Arc<dyn TypeTreeProvider>>) -> Self {
372        Self::with_cache_bound(
373            providers,
374            Self::DEFAULT_CACHE_ENTRIES,
375            Self::DEFAULT_CACHE_BYTES,
376        )
377    }
378
379    /// Providers asked in order, with a cache of at most `entries` answers
380    /// and `bytes` bytes (each entry costs its slot, at the table's worst load,
381    /// plus the heap its key owns).
382    #[must_use]
383    pub fn with_cache_bound(
384        providers: Vec<Arc<dyn TypeTreeProvider>>,
385        entries: usize,
386        bytes: u64,
387    ) -> Self {
388        Self {
389            providers,
390            cache: RwLock::new(Cache::default()),
391            max_entries: entries,
392            max_bytes: bytes,
393        }
394    }
395
396    /// Whether the chain has no provider.
397    #[must_use]
398    pub fn is_empty(&self) -> bool {
399        self.providers.is_empty()
400    }
401
402    /// Whether a provider answers script requests (UnityPy has an
403    /// `env.typetree_generator`): only then does
404    /// [`crate::env::Environment::object_tree`] dereference `m_Script`.
405    #[must_use]
406    pub fn accepts_scripts(&self) -> bool {
407        self.providers.iter().any(|p| p.accepts_scripts())
408    }
409
410    /// The common strings of the first provider that has them, which blob
411    /// typetrees read in place of [`crate::typetree::commonstring::COMMON_STRINGS`]
412    /// (UnityPy reads its TPK's).
413    #[must_use]
414    pub fn common_strings(&self) -> Option<&CommonStrings> {
415        self.providers.iter().find_map(|p| p.common_strings())
416    }
417
418    /// Answers cached now.
419    #[must_use]
420    pub fn cached(&self) -> usize {
421        self.cache.read().map_or(0, |c| c.map.len())
422    }
423
424    /// The first provider's answer for `req`. An answer is cached while the
425    /// cache has room; a miss is not cached. Providers are asked with no lock
426    /// held. A script request asks only the providers that
427    /// [`TypeTreeProvider::accepts_scripts`]: UnityPy asks its
428    /// `typetree_generator` alone for a script's tree
429    /// (`files/ObjectReader.py:346-350`), never the TPK, whose class tree is
430    /// the one the request would replace.
431    pub fn lookup(&self, req: &TreeRequest<'_>) -> Result<Option<TreeRef>, ProviderError> {
432        let hit = self
433            .cache
434            .read()
435            .ok()
436            .and_then(|c| c.map.get(&RequestKey(req) as &dyn KeyView).cloned());
437        if let Some((tree, name)) = hit {
438            return Ok(Some(TreeRef {
439                tree,
440                source: TreeSource::Provider(name),
441            }));
442        }
443        for provider in &self.providers {
444            if req.script.is_some() && !provider.accepts_scripts() {
445                continue;
446            }
447            if let Some(tree) = provider.tree(req)? {
448                let name = provider.name();
449                self.publish(req, (tree.clone(), name));
450                return Ok(Some(TreeRef {
451                    tree,
452                    source: TreeSource::Provider(name),
453                }));
454            }
455        }
456        Ok(None)
457    }
458
459    /// Why no provider answers the class tree of `class_id` at `version`
460    /// ([`TypeTreeProvider::why_none`]): the reason of the last provider
461    /// that states one, the one a fallback that raised in turn would leave
462    /// (UnityPy has one TPK). Asked only where [`Self::lookup`] found none;
463    /// nothing is cached.
464    #[must_use]
465    pub fn why_none(&self, class_id: i32, version: Option<&UnityVersion>) -> Option<NoTree> {
466        self.providers
467            .iter()
468            .rev()
469            .find_map(|p| p.why_none(class_id, version))
470    }
471
472    fn publish(&self, req: &TreeRequest<'_>, value: CacheValue) {
473        // Whether the answer is kept is decided from the borrowed request;
474        // only then is the key copied (a copy, not caller code, so it may
475        // run under the lock), so a key the cache will not keep is never
476        // copied.
477        let cost = entry_cost(req);
478        let Ok(mut cache) = self.cache.write() else {
479            return;
480        };
481        if cache.map.contains_key(&RequestKey(req) as &dyn KeyView)
482            || cache.map.len() >= self.max_entries
483            || cache.bytes.saturating_add(cost) > self.max_bytes
484        {
485            return;
486        }
487        cache.bytes = cache.bytes.saturating_add(cost);
488        cache.map.insert(CacheKey::copy_of(req), value);
489    }
490}
491
492impl Default for ProviderChain {
493    fn default() -> Self {
494        Self::empty()
495    }
496}
497
498impl fmt::Debug for ProviderChain {
499    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
500        let names: Vec<&str> = self.providers.iter().map(|p| p.name()).collect();
501        f.debug_struct("ProviderChain")
502            .field("providers", &names)
503            .finish_non_exhaustive()
504    }
505}
506
507#[cfg(test)]
508mod tests {
509    use std::sync::atomic::{AtomicUsize, Ordering};
510    use std::sync::{Arc, OnceLock, Weak, mpsc};
511
512    use super::{ProviderChain, ProviderError, ScriptIdent, TreeRequest, TypeTreeProvider};
513    use crate::raw::RawStr;
514    use crate::typetree::{NodeList, NodeRow, Tree};
515    use crate::version::UnityVersion;
516
517    /// Answers class 1 with a tree and misses everything else, counting
518    /// calls; with `chain` set it looks up class 2 through the chain from
519    /// inside its own call (a re-entrant provider).
520    #[derive(Debug, Default)]
521    struct Counting {
522        calls: AtomicUsize,
523        chain: OnceLock<Weak<ProviderChain>>,
524    }
525
526    impl TypeTreeProvider for Counting {
527        fn name(&self) -> &'static str {
528            "counting"
529        }
530
531        fn accepts_scripts(&self) -> bool {
532            true
533        }
534
535        fn tree(&self, req: &TreeRequest<'_>) -> Result<Option<Arc<Tree>>, ProviderError> {
536            self.calls.fetch_add(1, Ordering::Relaxed);
537            if req.class_id == 1 {
538                if let Some(chain) = self.chain.get().and_then(Weak::upgrade) {
539                    let inner = TreeRequest {
540                        class_id: 2,
541                        ..*req
542                    };
543                    chain.lookup(&inner)?;
544                }
545                let list = NodeList::trusted(vec![NodeRow::new(0, "Base", "Base")]).unwrap();
546                return Ok(Some(Tree::for_tests(list.into_shared().unwrap())));
547            }
548            Ok(None)
549        }
550    }
551
552    fn request(class_id: i32, version: &UnityVersion) -> TreeRequest<'_> {
553        TreeRequest {
554            class_id,
555            version,
556            script: None,
557        }
558    }
559
560    #[test]
561    fn answers_are_cached_and_misses_are_not() {
562        let p = Arc::new(Counting::default());
563        let chain = ProviderChain::new(vec![p.clone()]);
564        let v = UnityVersion::from_packed(1);
565        assert!(chain.lookup(&request(1, &v)).unwrap().is_some());
566        assert!(chain.lookup(&request(1, &v)).unwrap().is_some());
567        assert_eq!(p.calls.load(Ordering::Relaxed), 1, "the answer was cached");
568        assert!(chain.lookup(&request(7, &v)).unwrap().is_none());
569        assert!(chain.lookup(&request(7, &v)).unwrap().is_none());
570        assert_eq!(p.calls.load(Ordering::Relaxed), 3, "a miss is asked again");
571        assert_eq!(chain.cached(), 1, "misses leave nothing behind");
572    }
573
574    #[test]
575    fn the_cache_stops_at_its_bound_and_answers_stay_the_same() {
576        let p = Arc::new(Counting::default());
577        let chain = ProviderChain::with_cache_bound(vec![p.clone()], 2, u64::MAX);
578        for packed in 0..10 {
579            let v = UnityVersion::from_packed(packed);
580            assert!(chain.lookup(&request(1, &v)).unwrap().is_some());
581        }
582        assert_eq!(chain.cached(), 2);
583        let bytes = ProviderChain::with_cache_bound(vec![p], usize::MAX, 1);
584        let v = UnityVersion::from_packed(1);
585        assert!(bytes.lookup(&request(1, &v)).unwrap().is_some());
586        assert_eq!(
587            bytes.cached(),
588            0,
589            "an entry over the byte bound is not kept"
590        );
591    }
592
593    #[test]
594    fn a_cached_key_does_not_keep_the_inputs_buffer() {
595        let p = Arc::new(Counting::default());
596        let chain = ProviderChain::new(vec![p]);
597        let v = UnityVersion::from_packed(1);
598        let input = bytes::Bytes::from(vec![b'x'; 1 << 20]);
599        let script = ScriptIdent {
600            assembly: RawStr::from_shared(input.slice(0..3)),
601            namespace: RawStr::from_shared(input.slice(3..6)),
602            class: RawStr::from_shared(input.slice(6..9)),
603        };
604        let req = TreeRequest {
605            class_id: 1,
606            version: &v,
607            script: Some(&script),
608        };
609        assert!(chain.lookup(&req).unwrap().is_some());
610        drop(script);
611        // The only handle left on the buffer is ours: the cache copied.
612        assert!(input.is_unique());
613    }
614
615    #[test]
616    fn a_lookup_copies_nothing_but_the_key_it_keeps() {
617        // Round 3: every lookup copied the request's script strings (and a
618        // big version's limbs) before it looked in the cache, hits included.
619        let copies = || super::KEY_COPIES.with(std::cell::Cell::get);
620        let p = Arc::new(Counting::default());
621        let chain = ProviderChain::new(vec![p]);
622        let v = UnityVersion::from_packed(1);
623        let long = RawStr::from_shared(bytes::Bytes::from(vec![b'n'; 1 << 20]));
624        let script = ScriptIdent {
625            assembly: long.clone(),
626            namespace: long.clone(),
627            class: long,
628        };
629        let req = |class_id| TreeRequest {
630            class_id,
631            version: &v,
632            script: Some(&script),
633        };
634        let before = copies();
635        assert!(chain.lookup(&req(1)).unwrap().is_some());
636        assert_eq!(copies() - before, 1, "the answer kept copies its key once");
637        for _ in 0..10 {
638            assert!(chain.lookup(&req(1)).unwrap().is_some());
639            assert!(chain.lookup(&req(7)).unwrap().is_none());
640        }
641        assert_eq!(copies() - before, 1, "hits and misses copy nothing");
642        assert_eq!(chain.cached(), 1);
643    }
644
645    #[test]
646    fn a_key_the_cache_will_not_keep_is_never_copied() {
647        // Round 4: `publish` copied the request's strings before it found
648        // the entry too big or the cache full, so such a key was copied on
649        // every lookup.
650        let copies = || super::KEY_COPIES.with(std::cell::Cell::get);
651        let v = UnityVersion::from_packed(1);
652        let long = RawStr::from_shared(bytes::Bytes::from(vec![b'n'; 1 << 20]));
653        let script = ScriptIdent {
654            assembly: long.clone(),
655            namespace: long.clone(),
656            class: long,
657        };
658        let req = TreeRequest {
659            class_id: 1,
660            version: &v,
661            script: Some(&script),
662        };
663        // Too big: three 1 MiB names against a 2 MiB bound.
664        let too_big = ProviderChain::with_cache_bound(
665            vec![Arc::new(Counting::default())],
666            usize::MAX,
667            2 << 20,
668        );
669        let before = copies();
670        for _ in 0..10 {
671            assert!(too_big.lookup(&req).unwrap().is_some());
672        }
673        assert_eq!(copies() - before, 0, "an entry over the byte bound");
674        assert_eq!(too_big.cached(), 0);
675        // Full: a one-entry cache that already holds another answer.
676        let full =
677            ProviderChain::with_cache_bound(vec![Arc::new(Counting::default())], 1, u64::MAX);
678        assert!(full.lookup(&request(1, &v)).unwrap().is_some());
679        let before = copies();
680        for _ in 0..10 {
681            assert!(full.lookup(&req).unwrap().is_some());
682        }
683        assert_eq!(copies() - before, 0, "a full cache");
684        assert_eq!(full.cached(), 1);
685    }
686
687    #[test]
688    fn the_byte_bound_covers_the_table_at_rest_and_while_it_doubles() {
689        // Round 4: an entry was counted at three buckets. A doubling table
690        // holds up to 16/7 buckets per key at rest and 24/7 while the old
691        // and the doubled table are both live, so three fell short at every
692        // growth. Bucket counts are read from the map's capacity (hashbrown:
693        // 7/8 of the buckets from 8 buckets up, one less below).
694        let buckets = |cap: usize| match cap {
695            0 => 0,
696            c if c < 7 => c + 1,
697            c => c / 7 * 8,
698        };
699        let p = Arc::new(Counting::default());
700        let chain = ProviderChain::new(vec![p]);
701        let mut held = 0;
702        let mut grew = 0;
703        for packed in 0..20_000 {
704            let v = UnityVersion::from_packed(packed);
705            assert!(chain.lookup(&request(1, &v)).unwrap().is_some());
706            let cache = chain.cache.read().unwrap();
707            let now = buckets(cache.map.capacity());
708            // While it grew, the old table and the new one were both live.
709            let peak = if now > held {
710                grew += 1;
711                held + now
712            } else {
713                now
714            };
715            assert!(
716                u64::try_from(peak).unwrap() * super::BUCKET <= cache.bytes,
717                "{} keys: {peak} buckets of {} bytes above the {} counted",
718                cache.map.len(),
719                super::BUCKET,
720                cache.bytes
721            );
722            held = now;
723        }
724        assert!(grew >= 10, "the table doubled {grew} times");
725    }
726
727    #[test]
728    fn a_thread_holding_a_lock_a_provider_needs_does_not_wait_on_the_chain() {
729        // Plan 4.1: a provider is caller code (a Python one takes the GIL).
730        // Thread A's lookup runs a provider that needs `gil`; thread B holds
731        // `gil` and looks up another class through the same chain. Had the
732        // chain held its cache lock across A's provider, B would wait on it
733        // while holding what A's provider waits for.
734        #[derive(Debug)]
735        struct NeedsLock {
736            gil: Arc<std::sync::Mutex<()>>,
737            started: Arc<std::sync::Barrier>,
738        }
739        impl TypeTreeProvider for NeedsLock {
740            fn name(&self) -> &'static str {
741                "needs-lock"
742            }
743            fn tree(&self, req: &TreeRequest<'_>) -> Result<Option<Arc<Tree>>, ProviderError> {
744                if req.class_id == 1 {
745                    self.started.wait();
746                    let _held = self.gil.lock().unwrap();
747                }
748                let list = NodeList::trusted(vec![NodeRow::new(0, "Base", "Base")]).unwrap();
749                Ok(Some(Tree::for_tests(list.into_shared().unwrap())))
750            }
751        }
752        let (tx, rx) = mpsc::channel();
753        std::thread::spawn(move || {
754            let gil = Arc::new(std::sync::Mutex::new(()));
755            let started = Arc::new(std::sync::Barrier::new(2));
756            let chain = Arc::new(ProviderChain::new(vec![Arc::new(NeedsLock {
757                gil: gil.clone(),
758                started: started.clone(),
759            })]));
760            let a = {
761                let chain = chain.clone();
762                std::thread::spawn(move || {
763                    let v = UnityVersion::from_packed(1);
764                    chain.lookup(&request(1, &v)).map(|t| t.is_some())
765                })
766            };
767            let held = gil.lock().unwrap();
768            started.wait();
769            let v = UnityVersion::from_packed(1);
770            let b = chain.lookup(&request(2, &v)).map(|t| t.is_some());
771            drop(held);
772            let _ = tx.send((a.join().unwrap(), b));
773        });
774        let got = unityrs_testkit::guard::recv(
775            &rx,
776            "two lookups, one needing a lock the other holds (a chain lock held across a \
777             provider deadlocks them)",
778        );
779        assert_eq!(got, (Ok(true), Ok(true)));
780    }
781
782    #[test]
783    fn a_provider_may_call_the_chain_from_inside_its_answer() {
784        let (tx, rx) = mpsc::channel();
785        std::thread::spawn(move || {
786            let p = Arc::new(Counting::default());
787            let chain = Arc::new(ProviderChain::new(vec![p.clone()]));
788            let _ = p.chain.set(Arc::downgrade(&chain));
789            let v = UnityVersion::from_packed(1);
790            let got = chain.lookup(&request(1, &v)).map(|t| t.is_some());
791            let _ = tx.send(got);
792        });
793        let got = unityrs_testkit::guard::recv(
794            &rx,
795            "a lookup whose provider calls the chain (a chain lock held across the provider \
796             deadlocks it)",
797        );
798        assert_eq!(got, Ok(true));
799    }
800}