use std::collections::HashMap;
use std::sync::Arc;
use crate::files::SerializedType;
use crate::limits::{Charge, ChargeError, Limits, Meter, MeteredVec, hash_table_cost};
use crate::raw::RawStr;
use crate::typetree::{NodeId, Tree};
use crate::value::{ListIx, Map, Value, ValueBuilder};
use super::{
OpenWork, Out, ReadDetail, ReadError, ReadErrorKind, RefTypes, VALUE_WORK, Work, charge_error,
};
use crate::error::LimitError;
const NONE: u32 = u32::MAX;
#[cfg(test)]
std::thread_local! {
pub(super) static STEPS: std::cell::Cell<u64> = const { std::cell::Cell::new(0) };
}
#[inline]
pub(crate) fn steps(n: usize) {
#[cfg(test)]
STEPS.with(|s| s.set(s.get().saturating_add(n as u64)));
#[cfg(not(test))]
let _ = n;
}
#[cfg(test)]
std::thread_local! {
pub(super) static VISITS: std::cell::Cell<u64> = const { std::cell::Cell::new(0) };
}
#[inline]
pub(crate) fn visit() {
#[cfg(test)]
VISITS.with(|s| s.set(s.get().saturating_add(1)));
}
pub const DICT_FIRST: usize = 16;
#[derive(Debug)]
pub(crate) struct Dict {
pub(crate) entries: MeteredVec<(NodeId, Value)>,
slots: Option<MeteredVec<u32>>,
most: usize,
preserve_fields: bool,
}
impl Dict {
pub(crate) fn new(
builder: &ValueBuilder,
children: usize,
keyed: bool,
at: u64,
) -> Result<Self, ReadError> {
let mut entries = builder.vec();
entries
.reserve_exact(children.min(DICT_FIRST))
.map_err(|e| charge_error(at, e))?;
Ok(Self {
entries,
slots: keyed.then(|| builder.vec()),
most: children,
preserve_fields: false,
})
}
pub(crate) fn preserve_fields(&mut self, preserve: bool) {
self.preserve_fields = preserve;
}
pub(crate) fn position(&self, slot: u32) -> Option<usize> {
let at = self
.slots
.as_ref()?
.as_slice()
.get(slot as usize)
.copied()?;
(at != NONE).then_some(at as usize)
}
pub(crate) fn set(
&mut self,
work: &mut Work<'_>,
key: NodeId,
slot: u32,
value: Out,
at: u64,
) -> Result<(), ReadError> {
self.set_inline(work, key, slot, value, at)
}
#[allow(
clippy::inline_always,
reason = "measured: a per-value call of the reader"
)]
#[inline(always)]
pub(crate) fn set_inline(
&mut self,
work: &mut Work<'_>,
key: NodeId,
slot: u32,
value: Out,
at: u64,
) -> Result<(), ReadError> {
steps(1);
if let Some(pos) = self.position(slot).filter(|_| !self.preserve_fields) {
work.discard();
value.set_entry(&mut self.entries, pos);
return Ok(());
}
let pos = self.entries.len();
if pos == self.entries.capacity() {
steps(pos);
self.entries
.reserve_within(1, self.most)
.map_err(|e| charge_error(at, e))?;
}
value
.push_entry(&mut self.entries, key)
.map_err(|e| charge_error(at, e))?;
if let Some(slots) = &mut self.slots {
let slot = slot as usize;
let more = (slot + 1).saturating_sub(slots.len());
if more > 0 {
work.steps(more, at)?;
steps(more);
slots.reserve(more).map_err(|e| charge_error(at, e))?;
for _ in 0..more {
slots.push(NONE).map_err(|e| charge_error(at, e))?;
}
}
if let Some(s) = slots.as_mut_slice().get_mut(slot) {
*s = u32::try_from(pos).unwrap_or(NONE);
}
}
Ok(())
}
pub(crate) fn finish(
mut self,
builder: &ValueBuilder,
list: ListIx,
at: u64,
) -> Result<Out, ReadError> {
self.entries
.shrink_to_fit()
.map_err(|e| charge_error(at, e))?;
Ok(Out::Built(builder.map(list, self.entries)))
}
}
#[derive(Debug)]
pub(crate) struct Trees {
trees: MeteredVec<Arc<Tree>>,
}
impl Trees {
pub(crate) fn new(builder: &ValueBuilder, root: &Arc<Tree>) -> Result<Self, ReadError> {
let mut trees = builder.vec();
trees.push(root.clone()).map_err(|e| charge_error(0, e))?;
Ok(Self { trees })
}
pub(crate) fn index(
&mut self,
builder: &mut ValueBuilder,
tree: &Arc<Tree>,
at: u64,
) -> Result<ListIx, ReadError> {
let ix = builder
.list_index(tree.list())
.map_err(|e| charge_error(at, e))?;
if ix as usize == self.trees.len() {
self.trees
.push(tree.clone())
.map_err(|e| charge_error(at, e))?;
}
Ok(ix)
}
pub(crate) fn name(&self, list: ListIx, key: NodeId) -> &[u8] {
self.trees
.as_slice()
.get(list as usize)
.map_or(&[], |t| t.list().name(key))
}
pub(crate) fn field<'v>(
&self,
map: &'v Map,
name: &[u8],
work: &mut OpenWork<'_>,
constructed: bool,
) -> Result<Option<&'v Value>, LimitError> {
for (k, v) in map.entries().iter().rev() {
steps(1);
work.steps(1)?;
let raw = self.name(map.list(), *k);
if if constructed {
super::write::cleans_to(raw, name)
} else {
raw == name
} {
return Ok(Some(v));
}
}
Ok(None)
}
}
#[derive(Debug)]
pub(crate) enum FindError {
Charge(ChargeError),
Work(LimitError),
}
impl From<LimitError> for FindError {
fn from(l: LimitError) -> Self {
Self::Work(l)
}
}
fn names_len(t: &SerializedType) -> usize {
[&t.class_name, &t.namespace, &t.assembly]
.into_iter()
.map(|n| n.as_ref().map_or(0, |n| n.as_bytes().len()))
.sum()
}
fn names_match(t: &SerializedType, cls: &Value, ns: &Value, asm: &Value) -> bool {
let eq = |v: &Value, s: &Option<RawStr>| match (v, s) {
(Value::Str(a), Some(b)) => a.as_bytes() == b.as_bytes(),
_ => false,
};
eq(cls, &t.class_name) && eq(ns, &t.namespace) && eq(asm, &t.assembly)
}
pub(crate) struct RefIndex<'a> {
list: &'a [SerializedType],
scanned: usize,
table: Option<RefTable<'a>>,
}
const SCANNED_REFS: usize = 8;
struct RefTable<'a> {
first: HashMap<[&'a [u8]; 3], usize>,
longest: [usize; 3],
_charge: Charge,
}
impl<'a> RefIndex<'a> {
pub(crate) fn new(refs: RefTypes<'a>) -> Self {
let list = match refs {
RefTypes::List(l) => l,
RefTypes::NoFile | RefTypes::Absent => &[],
};
Self {
list,
scanned: 0,
table: None,
}
}
pub(crate) fn find(
&mut self,
meter: &Arc<Meter>,
work: &mut OpenWork<'_>,
cls: &Value,
ns: &Value,
asm: &Value,
) -> Result<Option<&'a SerializedType>, FindError> {
let (Value::Str(c), Value::Str(n), Value::Str(a)) = (cls, ns, asm) else {
return Ok(None);
};
if self.table.is_none() && self.scanned >= self.list.len() && self.list.len() > SCANNED_REFS
{
self.table = Some(RefTable::build(self.list, meter, work)?);
}
if let Some(t) = &self.table {
steps(1);
let key = [c.as_bytes(), n.as_bytes(), a.as_bytes()];
if key.iter().zip(t.longest).any(|(k, l)| k.len() > l) {
work.add(VALUE_WORK)?;
return Ok(None);
}
work.add(VALUE_WORK.saturating_add(as_u64(key.iter().map(|k| k.len()).sum())))?;
let first: &HashMap<[&[u8]; 3], usize> = &t.first;
return Ok(first.get(&key).and_then(|i| self.list.get(*i)));
}
for (i, r) in self.list.iter().enumerate() {
steps(1);
work.add(VALUE_WORK.saturating_add(as_u64(names_len(r))))?;
if names_match(r, cls, ns, asm) {
self.scanned = self.scanned.saturating_add(i + 1);
return Ok(Some(r));
}
}
self.scanned = self.scanned.saturating_add(self.list.len());
Ok(None)
}
}
fn as_u64(n: usize) -> u64 {
u64::try_from(n).unwrap_or(u64::MAX)
}
impl<'a> RefTable<'a> {
fn build(
list: &'a [SerializedType],
meter: &Arc<Meter>,
work: &mut OpenWork<'_>,
) -> Result<Self, FindError> {
let n = list.len();
let charge = meter
.charge(hash_table_cost(n, size_of::<([&[u8]; 3], usize)>()))
.map_err(FindError::Charge)?;
let mut first = HashMap::with_capacity(n);
let mut longest = [0; 3];
for (i, r) in list.iter().enumerate() {
steps(1);
work.add(VALUE_WORK.saturating_add(as_u64(names_len(r))))?;
let (Some(c), Some(ns), Some(a)) = (&r.class_name, &r.namespace, &r.assembly) else {
continue;
};
let key = [c.as_bytes(), ns.as_bytes(), a.as_bytes()];
for (l, k) in longest.iter_mut().zip(key) {
*l = (*l).max(k.len());
}
first.entry(key).or_insert(i);
}
Ok(Self {
first,
longest,
_charge: charge,
})
}
}
#[derive(Clone)]
pub(crate) enum RefNode {
Tree(Arc<Tree>),
NoTree,
}
pub(crate) fn ref_tree(t: &SerializedType, limits: &Limits, at: u64) -> Result<RefNode, ReadError> {
match t.tree(limits) {
None => Ok(RefNode::NoTree),
Some(Ok(tree)) => Ok(RefNode::Tree(tree)),
Some(Err(e)) => Err(ReadError {
kind: ReadErrorKind::Other,
at,
detail: ReadDetail::Tree(e),
}),
}
}
#[cfg(test)]
mod tests {
use bytes::Bytes;
use super::STEPS;
use crate::limits::{Limits, Meter};
use crate::stream::Endian;
use crate::typetree::{NodeList, NodeRow, Tree};
use crate::value::Value;
use crate::walk::{ReadCtx, ReadOptions, RefTypes, boost, python};
#[test]
fn late_repeats_read_in_linear_map_steps() {
const N: u32 = 1 << 16;
const REPEATS: u32 = 4096;
let distinct = N - REPEATS;
let mut rows = vec![NodeRow::new(0, "Base", "Base")];
for i in 0..N {
let name = format!("n{}", if i < distinct { i } else { i - distinct });
rows.push(NodeRow::new(1, "int", name.as_str()));
}
let tree = Tree::compile(
NodeList::trusted(rows).unwrap().into_shared().unwrap(),
&Limits::default(),
)
.unwrap();
let data: Vec<u8> = (0..N).flat_map(u32::to_le_bytes).collect();
let data = Bytes::from(data);
let options = ReadOptions::default();
let meter = Meter::unlimited();
let ctx = ReadCtx {
endian: Endian::Little,
ref_types: RefTypes::List(&[]),
options: &options,
meter: &meter,
};
for reader in ["boost", "python"] {
STEPS.with(|s| s.set(0));
let p = match reader {
"boost" => boost::read(&data, &tree, &ctx),
_ => python::read(&data, 0, &tree, &ctx),
}
.unwrap();
let steps = STEPS.with(std::cell::Cell::get);
assert!(
steps <= 6 * u64::from(N),
"{reader}: {steps} map steps for {N} children"
);
let Value::Dict(m) = p.value() else {
panic!("{reader}: not a dict")
};
assert_eq!(m.len(), distinct as usize, "{reader}");
for (i, (name, v)) in p.entries(m).enumerate() {
let i = u32::try_from(i).unwrap();
assert_eq!(name, format!("n{i}").as_bytes(), "{reader}: position {i}");
let last = if i < REPEATS { distinct + i } else { i };
assert_eq!(v, &Value::Int(i64::from(last)), "{reader}: n{i}");
}
}
}
}