use std::borrow::Borrow;
use std::collections::HashMap;
use std::fmt;
use std::hash::{Hash, Hasher};
use std::mem::size_of;
use std::sync::{Arc, RwLock};
use bytes::Bytes;
use crate::limits::{HASH_TABLE_SHARES, heap_cost};
use crate::raw::RawStr;
use crate::typetree::Tree;
use crate::typetree::commonstring::CommonStrings;
use crate::version::{Packed, UnityVersion};
mod exception;
pub mod generator;
mod no_tree;
pub use exception::PythonException;
pub use no_tree::NoTree;
#[derive(Clone, Debug, PartialEq, Eq, Hash)]
pub struct ScriptIdent {
pub assembly: RawStr,
pub namespace: RawStr,
pub class: RawStr,
}
#[derive(Clone, Copy, Debug)]
pub struct TreeRequest<'a> {
pub class_id: i32,
pub version: &'a UnityVersion,
pub script: Option<&'a ScriptIdent>,
}
#[derive(Clone, Debug, PartialEq, Eq, thiserror::Error)]
#[error("{provider}: {detail}")]
#[non_exhaustive]
pub struct ProviderError {
pub python_exception: Option<PythonException>,
pub provider: &'static str,
pub detail: Arc<str>,
pub limit: Option<crate::LimitError>,
pub memory: Option<crate::budget::BudgetExceeded>,
pub allocator: Option<crate::budget::AllocError>,
}
impl ProviderError {
#[must_use]
pub fn new(provider: &'static str, detail: Arc<str>) -> Self {
Self {
python_exception: None,
provider,
detail,
limit: None,
memory: None,
allocator: None,
}
}
}
pub trait TypeTreeProvider: Send + Sync + fmt::Debug {
fn name(&self) -> &'static str;
fn tree(&self, req: &TreeRequest<'_>) -> Result<Option<Arc<Tree>>, ProviderError>;
fn why_none(&self, class_id: i32, version: Option<&UnityVersion>) -> Option<NoTree> {
let _ = (class_id, version);
None
}
fn accepts_scripts(&self) -> bool {
false
}
fn common_strings(&self) -> Option<&CommonStrings> {
None
}
}
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub enum TreeSource {
Embedded,
Provider(&'static str),
Explicit,
}
#[derive(Clone, Debug)]
pub struct TreeRef {
pub tree: Arc<Tree>,
pub source: TreeSource,
}
trait KeyView {
fn class_id(&self) -> i32;
fn packed(&self) -> &Packed;
fn script(&self) -> Option<[&[u8]; 3]>;
}
impl Hash for dyn KeyView + '_ {
fn hash<H: Hasher>(&self, h: &mut H) {
self.class_id().hash(h);
self.packed().hash(h);
self.script().hash(h);
}
}
impl PartialEq for dyn KeyView + '_ {
fn eq(&self, other: &Self) -> bool {
self.class_id() == other.class_id()
&& self.packed() == other.packed()
&& self.script() == other.script()
}
}
impl Eq for dyn KeyView + '_ {}
struct CacheKey {
class_id: i32,
packed: Packed,
script: Option<[Bytes; 3]>,
}
#[cfg(test)]
thread_local! {
static KEY_COPIES: std::cell::Cell<usize> = const { std::cell::Cell::new(0) };
}
impl CacheKey {
fn copy_of(req: &TreeRequest<'_>) -> Self {
#[cfg(test)]
KEY_COPIES.with(|n| n.set(n.get() + 1));
let own = |s: &RawStr| Bytes::copy_from_slice(s.as_bytes());
Self {
class_id: req.class_id,
packed: req.version.packed().clone(),
script: req
.script
.map(|s| [own(&s.assembly), own(&s.namespace), own(&s.class)]),
}
}
}
impl KeyView for CacheKey {
fn class_id(&self) -> i32 {
self.class_id
}
fn packed(&self) -> &Packed {
&self.packed
}
fn script(&self) -> Option<[&[u8]; 3]> {
self.script
.as_ref()
.map(|[a, n, c]| [&a[..], &n[..], &c[..]])
}
}
impl Hash for CacheKey {
fn hash<H: Hasher>(&self, h: &mut H) {
(self as &dyn KeyView).hash(h);
}
}
impl PartialEq for CacheKey {
fn eq(&self, other: &Self) -> bool {
(self as &dyn KeyView) == (other as &dyn KeyView)
}
}
impl Eq for CacheKey {}
impl<'a> Borrow<dyn KeyView + 'a> for CacheKey {
fn borrow(&self) -> &(dyn KeyView + 'a) {
self
}
}
struct RequestKey<'r, 'a>(&'r TreeRequest<'a>);
impl KeyView for RequestKey<'_, '_> {
fn class_id(&self) -> i32 {
self.0.class_id
}
fn packed(&self) -> &Packed {
self.0.version.packed()
}
fn script(&self) -> Option<[&[u8]; 3]> {
self.0.script.map(|s| {
[
s.assembly.as_bytes(),
s.namespace.as_bytes(),
s.class.as_bytes(),
]
})
}
}
type CacheValue = (Arc<Tree>, &'static str);
#[derive(Default)]
struct Cache {
map: HashMap<CacheKey, CacheValue>,
bytes: u64,
}
pub struct ProviderChain {
providers: Vec<Arc<dyn TypeTreeProvider>>,
cache: RwLock<Cache>,
max_entries: usize,
max_bytes: u64,
}
const BUCKET: u64 = (size_of::<CacheKey>() + size_of::<CacheValue>() + 1) as u64;
fn entry_cost(req: &TreeRequest<'_>) -> u64 {
let len = |n: usize| heap_cost(u64::try_from(n).unwrap_or(u64::MAX));
let strings = req.script.map_or(0, |s| {
len(s.assembly.len())
.saturating_add(len(s.namespace.len()))
.saturating_add(len(s.class.len()))
});
(HASH_TABLE_SHARES * BUCKET)
.saturating_add(strings)
.saturating_add(len(req.version.packed().heap_bytes()))
}
impl ProviderChain {
pub const DEFAULT_CACHE_ENTRIES: usize = 1 << 16;
pub const DEFAULT_CACHE_BYTES: u64 = 64 << 20;
#[must_use]
pub fn empty() -> Self {
Self::new(Vec::new())
}
#[must_use]
pub fn new(providers: Vec<Arc<dyn TypeTreeProvider>>) -> Self {
Self::with_cache_bound(
providers,
Self::DEFAULT_CACHE_ENTRIES,
Self::DEFAULT_CACHE_BYTES,
)
}
#[must_use]
pub fn with_cache_bound(
providers: Vec<Arc<dyn TypeTreeProvider>>,
entries: usize,
bytes: u64,
) -> Self {
Self {
providers,
cache: RwLock::new(Cache::default()),
max_entries: entries,
max_bytes: bytes,
}
}
#[must_use]
pub fn is_empty(&self) -> bool {
self.providers.is_empty()
}
#[must_use]
pub fn accepts_scripts(&self) -> bool {
self.providers.iter().any(|p| p.accepts_scripts())
}
#[must_use]
pub fn common_strings(&self) -> Option<&CommonStrings> {
self.providers.iter().find_map(|p| p.common_strings())
}
#[must_use]
pub fn cached(&self) -> usize {
self.cache.read().map_or(0, |c| c.map.len())
}
pub fn lookup(&self, req: &TreeRequest<'_>) -> Result<Option<TreeRef>, ProviderError> {
let hit = self
.cache
.read()
.ok()
.and_then(|c| c.map.get(&RequestKey(req) as &dyn KeyView).cloned());
if let Some((tree, name)) = hit {
return Ok(Some(TreeRef {
tree,
source: TreeSource::Provider(name),
}));
}
for provider in &self.providers {
if req.script.is_some() && !provider.accepts_scripts() {
continue;
}
if let Some(tree) = provider.tree(req)? {
let name = provider.name();
self.publish(req, (tree.clone(), name));
return Ok(Some(TreeRef {
tree,
source: TreeSource::Provider(name),
}));
}
}
Ok(None)
}
#[must_use]
pub fn why_none(&self, class_id: i32, version: Option<&UnityVersion>) -> Option<NoTree> {
self.providers
.iter()
.rev()
.find_map(|p| p.why_none(class_id, version))
}
fn publish(&self, req: &TreeRequest<'_>, value: CacheValue) {
let cost = entry_cost(req);
let Ok(mut cache) = self.cache.write() else {
return;
};
if cache.map.contains_key(&RequestKey(req) as &dyn KeyView)
|| cache.map.len() >= self.max_entries
|| cache.bytes.saturating_add(cost) > self.max_bytes
{
return;
}
cache.bytes = cache.bytes.saturating_add(cost);
cache.map.insert(CacheKey::copy_of(req), value);
}
}
impl Default for ProviderChain {
fn default() -> Self {
Self::empty()
}
}
impl fmt::Debug for ProviderChain {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
let names: Vec<&str> = self.providers.iter().map(|p| p.name()).collect();
f.debug_struct("ProviderChain")
.field("providers", &names)
.finish_non_exhaustive()
}
}
#[cfg(test)]
mod tests {
use std::sync::atomic::{AtomicUsize, Ordering};
use std::sync::{Arc, OnceLock, Weak, mpsc};
use super::{ProviderChain, ProviderError, ScriptIdent, TreeRequest, TypeTreeProvider};
use crate::raw::RawStr;
use crate::typetree::{NodeList, NodeRow, Tree};
use crate::version::UnityVersion;
#[derive(Debug, Default)]
struct Counting {
calls: AtomicUsize,
chain: OnceLock<Weak<ProviderChain>>,
}
impl TypeTreeProvider for Counting {
fn name(&self) -> &'static str {
"counting"
}
fn accepts_scripts(&self) -> bool {
true
}
fn tree(&self, req: &TreeRequest<'_>) -> Result<Option<Arc<Tree>>, ProviderError> {
self.calls.fetch_add(1, Ordering::Relaxed);
if req.class_id == 1 {
if let Some(chain) = self.chain.get().and_then(Weak::upgrade) {
let inner = TreeRequest {
class_id: 2,
..*req
};
chain.lookup(&inner)?;
}
let list = NodeList::trusted(vec![NodeRow::new(0, "Base", "Base")]).unwrap();
return Ok(Some(Tree::for_tests(list.into_shared().unwrap())));
}
Ok(None)
}
}
fn request(class_id: i32, version: &UnityVersion) -> TreeRequest<'_> {
TreeRequest {
class_id,
version,
script: None,
}
}
#[test]
fn answers_are_cached_and_misses_are_not() {
let p = Arc::new(Counting::default());
let chain = ProviderChain::new(vec![p.clone()]);
let v = UnityVersion::from_packed(1);
assert!(chain.lookup(&request(1, &v)).unwrap().is_some());
assert!(chain.lookup(&request(1, &v)).unwrap().is_some());
assert_eq!(p.calls.load(Ordering::Relaxed), 1, "the answer was cached");
assert!(chain.lookup(&request(7, &v)).unwrap().is_none());
assert!(chain.lookup(&request(7, &v)).unwrap().is_none());
assert_eq!(p.calls.load(Ordering::Relaxed), 3, "a miss is asked again");
assert_eq!(chain.cached(), 1, "misses leave nothing behind");
}
#[test]
fn the_cache_stops_at_its_bound_and_answers_stay_the_same() {
let p = Arc::new(Counting::default());
let chain = ProviderChain::with_cache_bound(vec![p.clone()], 2, u64::MAX);
for packed in 0..10 {
let v = UnityVersion::from_packed(packed);
assert!(chain.lookup(&request(1, &v)).unwrap().is_some());
}
assert_eq!(chain.cached(), 2);
let bytes = ProviderChain::with_cache_bound(vec![p], usize::MAX, 1);
let v = UnityVersion::from_packed(1);
assert!(bytes.lookup(&request(1, &v)).unwrap().is_some());
assert_eq!(
bytes.cached(),
0,
"an entry over the byte bound is not kept"
);
}
#[test]
fn a_cached_key_does_not_keep_the_inputs_buffer() {
let p = Arc::new(Counting::default());
let chain = ProviderChain::new(vec![p]);
let v = UnityVersion::from_packed(1);
let input = bytes::Bytes::from(vec![b'x'; 1 << 20]);
let script = ScriptIdent {
assembly: RawStr::from_shared(input.slice(0..3)),
namespace: RawStr::from_shared(input.slice(3..6)),
class: RawStr::from_shared(input.slice(6..9)),
};
let req = TreeRequest {
class_id: 1,
version: &v,
script: Some(&script),
};
assert!(chain.lookup(&req).unwrap().is_some());
drop(script);
assert!(input.is_unique());
}
#[test]
fn a_lookup_copies_nothing_but_the_key_it_keeps() {
let copies = || super::KEY_COPIES.with(std::cell::Cell::get);
let p = Arc::new(Counting::default());
let chain = ProviderChain::new(vec![p]);
let v = UnityVersion::from_packed(1);
let long = RawStr::from_shared(bytes::Bytes::from(vec![b'n'; 1 << 20]));
let script = ScriptIdent {
assembly: long.clone(),
namespace: long.clone(),
class: long,
};
let req = |class_id| TreeRequest {
class_id,
version: &v,
script: Some(&script),
};
let before = copies();
assert!(chain.lookup(&req(1)).unwrap().is_some());
assert_eq!(copies() - before, 1, "the answer kept copies its key once");
for _ in 0..10 {
assert!(chain.lookup(&req(1)).unwrap().is_some());
assert!(chain.lookup(&req(7)).unwrap().is_none());
}
assert_eq!(copies() - before, 1, "hits and misses copy nothing");
assert_eq!(chain.cached(), 1);
}
#[test]
fn a_key_the_cache_will_not_keep_is_never_copied() {
let copies = || super::KEY_COPIES.with(std::cell::Cell::get);
let v = UnityVersion::from_packed(1);
let long = RawStr::from_shared(bytes::Bytes::from(vec![b'n'; 1 << 20]));
let script = ScriptIdent {
assembly: long.clone(),
namespace: long.clone(),
class: long,
};
let req = TreeRequest {
class_id: 1,
version: &v,
script: Some(&script),
};
let too_big = ProviderChain::with_cache_bound(
vec![Arc::new(Counting::default())],
usize::MAX,
2 << 20,
);
let before = copies();
for _ in 0..10 {
assert!(too_big.lookup(&req).unwrap().is_some());
}
assert_eq!(copies() - before, 0, "an entry over the byte bound");
assert_eq!(too_big.cached(), 0);
let full =
ProviderChain::with_cache_bound(vec![Arc::new(Counting::default())], 1, u64::MAX);
assert!(full.lookup(&request(1, &v)).unwrap().is_some());
let before = copies();
for _ in 0..10 {
assert!(full.lookup(&req).unwrap().is_some());
}
assert_eq!(copies() - before, 0, "a full cache");
assert_eq!(full.cached(), 1);
}
#[test]
fn the_byte_bound_covers_the_table_at_rest_and_while_it_doubles() {
let buckets = |cap: usize| match cap {
0 => 0,
c if c < 7 => c + 1,
c => c / 7 * 8,
};
let p = Arc::new(Counting::default());
let chain = ProviderChain::new(vec![p]);
let mut held = 0;
let mut grew = 0;
for packed in 0..20_000 {
let v = UnityVersion::from_packed(packed);
assert!(chain.lookup(&request(1, &v)).unwrap().is_some());
let cache = chain.cache.read().unwrap();
let now = buckets(cache.map.capacity());
let peak = if now > held {
grew += 1;
held + now
} else {
now
};
assert!(
u64::try_from(peak).unwrap() * super::BUCKET <= cache.bytes,
"{} keys: {peak} buckets of {} bytes above the {} counted",
cache.map.len(),
super::BUCKET,
cache.bytes
);
held = now;
}
assert!(grew >= 10, "the table doubled {grew} times");
}
#[test]
fn a_thread_holding_a_lock_a_provider_needs_does_not_wait_on_the_chain() {
#[derive(Debug)]
struct NeedsLock {
gil: Arc<std::sync::Mutex<()>>,
started: Arc<std::sync::Barrier>,
}
impl TypeTreeProvider for NeedsLock {
fn name(&self) -> &'static str {
"needs-lock"
}
fn tree(&self, req: &TreeRequest<'_>) -> Result<Option<Arc<Tree>>, ProviderError> {
if req.class_id == 1 {
self.started.wait();
let _held = self.gil.lock().unwrap();
}
let list = NodeList::trusted(vec![NodeRow::new(0, "Base", "Base")]).unwrap();
Ok(Some(Tree::for_tests(list.into_shared().unwrap())))
}
}
let (tx, rx) = mpsc::channel();
std::thread::spawn(move || {
let gil = Arc::new(std::sync::Mutex::new(()));
let started = Arc::new(std::sync::Barrier::new(2));
let chain = Arc::new(ProviderChain::new(vec![Arc::new(NeedsLock {
gil: gil.clone(),
started: started.clone(),
})]));
let a = {
let chain = chain.clone();
std::thread::spawn(move || {
let v = UnityVersion::from_packed(1);
chain.lookup(&request(1, &v)).map(|t| t.is_some())
})
};
let held = gil.lock().unwrap();
started.wait();
let v = UnityVersion::from_packed(1);
let b = chain.lookup(&request(2, &v)).map(|t| t.is_some());
drop(held);
let _ = tx.send((a.join().unwrap(), b));
});
let got = unityrs_testkit::guard::recv(
&rx,
"two lookups, one needing a lock the other holds (a chain lock held across a \
provider deadlocks them)",
);
assert_eq!(got, (Ok(true), Ok(true)));
}
#[test]
fn a_provider_may_call_the_chain_from_inside_its_answer() {
let (tx, rx) = mpsc::channel();
std::thread::spawn(move || {
let p = Arc::new(Counting::default());
let chain = Arc::new(ProviderChain::new(vec![p.clone()]));
let _ = p.chain.set(Arc::downgrade(&chain));
let v = UnityVersion::from_packed(1);
let got = chain.lookup(&request(1, &v)).map(|t| t.is_some());
let _ = tx.send(got);
});
let got = unityrs_testkit::guard::recv(
&rx,
"a lookup whose provider calls the chain (a chain lock held across the provider \
deadlocks it)",
);
assert_eq!(got, Ok(true));
}
}