1use 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#[derive(Clone, Debug, PartialEq, Eq, Hash)]
69pub struct ScriptIdent {
70 pub assembly: RawStr,
72 pub namespace: RawStr,
74 pub class: RawStr,
76}
77
78#[derive(Clone, Copy, Debug)]
80pub struct TreeRequest<'a> {
81 pub class_id: i32,
83 pub version: &'a UnityVersion,
85 pub script: Option<&'a ScriptIdent>,
87}
88
89#[derive(Clone, Debug, PartialEq, Eq, thiserror::Error)]
101#[error("{provider}: {detail}")]
102#[non_exhaustive]
103pub struct ProviderError {
104 pub python_exception: Option<PythonException>,
107 pub provider: &'static str,
109 pub detail: Arc<str>,
112 pub limit: Option<crate::LimitError>,
116 pub memory: Option<crate::budget::BudgetExceeded>,
124 pub allocator: Option<crate::budget::AllocError>,
127}
128
129impl ProviderError {
130 #[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
145pub trait TypeTreeProvider: Send + Sync + fmt::Debug {
147 fn name(&self) -> &'static str;
149 fn tree(&self, req: &TreeRequest<'_>) -> Result<Option<Arc<Tree>>, ProviderError>;
167 fn why_none(&self, class_id: i32, version: Option<&UnityVersion>) -> Option<NoTree> {
172 let _ = (class_id, version);
173 None
174 }
175 fn accepts_scripts(&self) -> bool {
179 false
180 }
181 fn common_strings(&self) -> Option<&CommonStrings> {
185 None
186 }
187}
188
189#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
191pub enum TreeSource {
192 Embedded,
194 Provider(&'static str),
196 Explicit,
198}
199
200#[derive(Clone, Debug)]
202pub struct TreeRef {
203 pub tree: Arc<Tree>,
205 pub source: TreeSource,
207}
208
209trait 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
235struct CacheKey {
238 class_id: i32,
239 packed: Packed,
240 script: Option<[Bytes; 3]>,
241}
242
243#[cfg(test)]
244thread_local! {
245 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
298struct 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
327pub struct ProviderChain {
330 providers: Vec<Arc<dyn TypeTreeProvider>>,
331 cache: RwLock<Cache>,
332 max_entries: usize,
333 max_bytes: u64,
334}
335
336const BUCKET: u64 = (size_of::<CacheKey>() + size_of::<CacheValue>() + 1) as u64;
338
339fn 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 pub const DEFAULT_CACHE_ENTRIES: usize = 1 << 16;
359 pub const DEFAULT_CACHE_BYTES: u64 = 64 << 20;
361
362 #[must_use]
364 pub fn empty() -> Self {
365 Self::new(Vec::new())
366 }
367
368 #[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 #[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 #[must_use]
398 pub fn is_empty(&self) -> bool {
399 self.providers.is_empty()
400 }
401
402 #[must_use]
406 pub fn accepts_scripts(&self) -> bool {
407 self.providers.iter().any(|p| p.accepts_scripts())
408 }
409
410 #[must_use]
414 pub fn common_strings(&self) -> Option<&CommonStrings> {
415 self.providers.iter().find_map(|p| p.common_strings())
416 }
417
418 #[must_use]
420 pub fn cached(&self) -> usize {
421 self.cache.read().map_or(0, |c| c.map.len())
422 }
423
424 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 #[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 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 #[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 assert!(input.is_unique());
613 }
614
615 #[test]
616 fn a_lookup_copies_nothing_but_the_key_it_keeps() {
617 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 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 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 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 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 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 #[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}