use std::sync::Arc;
use bytes::Bytes;
use super::dict::{STEPS, VISITS};
use crate::budget::DecodeBuf;
use crate::error::{LimitError, LimitKind};
use crate::files::SerializedType;
use crate::limits::{Limits, Meter, MeteredVec};
use crate::raw::RawStr;
use crate::stream::Endian;
use crate::typetree::{NodeList, NodeRow, Tree};
use crate::value::Parsed;
use crate::walk::{
ReadCtx, ReadDetail, ReadError, ReadOptions, RefTypes, WriteCtx, WriteError, WriteRules, boost,
python,
};
struct Steps {
what: String,
read: u64,
write: u64,
}
fn measure(rows: Vec<NodeRow>, data: &[u8], refs: &[SerializedType]) -> Vec<Steps> {
let tree = Tree::compile(
NodeList::trusted(rows).unwrap().into_shared().unwrap(),
&Limits::default(),
)
.unwrap();
let data = Bytes::copy_from_slice(data);
let options = ReadOptions::default();
let meter = Meter::unlimited();
let ctx = ReadCtx {
endian: Endian::Little,
ref_types: RefTypes::List(refs),
options: &options,
meter: &meter,
};
let limits = Limits::default();
let mut out = Vec::new();
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_or_else(|e| panic!("{reader}: {e}"));
let read = STEPS.with(std::cell::Cell::get);
for rules in [WriteRules::UnityPy, WriteRules::MirrorReader] {
let wctx = WriteCtx {
endian: Endian::Little,
ref_types: RefTypes::List(refs),
rules,
limits: &limits,
};
let mut buf = DecodeBuf::new(&meter, 0, u64::MAX, LimitKind::InputMemory).unwrap();
STEPS.with(|s| s.set(0));
super::write::write(&p, &tree, &wctx, &mut buf)
.unwrap_or_else(|e| panic!("{reader} {rules:?}: {e}"));
out.push(Steps {
what: format!("{reader} read, {rules:?} write"),
read,
write: STEPS.with(std::cell::Cell::get),
});
}
}
out
}
fn ref_types(classes: impl Iterator<Item = String>) -> Vec<SerializedType> {
classes
.map(|c| {
let rows = vec![NodeRow::new(0, "Empty", "Base")];
SerializedType::ref_type(
114,
RawStr::from(c.as_str()),
RawStr::from(""),
RawStr::from(""),
Some(NodeList::trusted(rows).unwrap().into_shared().unwrap()),
)
})
.collect()
}
fn string(out: &mut Vec<u8>, s: &str) {
out.extend_from_slice(&i32::try_from(s.len()).unwrap().to_le_bytes());
out.extend_from_slice(s.as_bytes());
out.resize(out.len().next_multiple_of(4), 0);
}
fn type_rows(rows: &mut Vec<NodeRow>, level: i32, extra: u32) {
rows.push(NodeRow::new(level, "ReferencedType", "type"));
for i in 0..extra {
rows.push(NodeRow::new(level + 1, "int", format!("f{i}").as_str()));
}
for name in ["class", "ns", "asm"] {
rows.push(NodeRow::new(level + 1, "string", name));
}
}
fn type_data(out: &mut Vec<u8>, extra: u32, class: &str) {
for i in 0..extra {
out.extend_from_slice(&i.to_le_bytes());
}
string(out, class);
string(out, "");
string(out, "");
}
fn check(steps: &[Steps], bound: u64, what: &str) {
for s in steps {
assert!(
s.read <= bound && s.write <= bound,
"{}: {} read and {} write steps for {what} (bound {bound})",
s.what,
s.read,
s.write
);
}
}
#[test]
fn references_into_as_many_ref_types_resolve_in_linear_steps() {
const N: u32 = 1 << 12;
let refs = ref_types((0..N).map(|i| format!("C{i}")));
let mut rows = vec![
NodeRow::new(0, "Base", "Base"),
NodeRow::new(1, "vector", "refs"),
NodeRow::new(2, "Array", "Array"),
NodeRow::new(3, "int", "size"),
NodeRow::new(3, "ReferencedObject", "data"),
];
type_rows(&mut rows, 4, 0);
rows.push(NodeRow::new(4, "ReferencedObjectData", "data"));
let mut data = N.to_le_bytes().to_vec();
for i in 0..N {
type_data(&mut data, 0, &format!("C{i}"));
}
let steps = measure(rows, &data, &refs);
check(&steps, 32 * u64::from(N), "N references into N ref types");
}
#[test]
fn a_type_resolves_once_for_all_its_data_children() {
const D: u32 = 1 << 12;
const T: u32 = 1 << 12;
let refs = ref_types(std::iter::once("C".to_owned()));
let mut rows = vec![
NodeRow::new(0, "Base", "Base"),
NodeRow::new(1, "ReferencedObject", "o"),
];
type_rows(&mut rows, 2, T);
for i in 0..D {
rows.push(NodeRow::new(
2,
"ReferencedObjectData",
format!("data{i}").as_str(),
));
}
let mut data = Vec::new();
type_data(&mut data, T, "C");
let steps = measure(rows, &data, &refs);
check(&steps, 16 * u64::from(D + T), "D data children of one type");
}
#[test]
fn siblings_share_one_referenced_object_in_linear_steps() {
const K: u32 = 1 << 12;
const N: u32 = 1 << 12;
let refs = ref_types(std::iter::once("C".to_owned()));
let mut rows = vec![NodeRow::new(0, "Base", "Base")];
let mut data = Vec::new();
for _ in 0..K {
rows.push(NodeRow::new(1, "ReferencedObject", "a"));
type_rows(&mut rows, 2, 0);
rows.push(NodeRow::new(2, "ReferencedObjectData", "data"));
type_data(&mut data, 0, "");
}
rows.push(NodeRow::new(1, "ReferencedObject", "a"));
type_rows(&mut rows, 2, N);
rows.push(NodeRow::new(2, "ReferencedObjectData", "data"));
type_data(&mut data, N, "C");
let steps = measure(rows, &data, &refs);
check(&steps, 16 * u64::from(K + N), "K siblings sharing one dict");
}
const BOUND: u64 = 1 << 14;
fn bounded() -> Limits {
Limits {
max_values_per_object: BOUND,
..Limits::default()
}
}
fn refused() -> LimitError {
LimitError::refused(LimitKind::ValuesPerObject, BOUND + 1, BOUND)
}
fn compile(rows: Vec<NodeRow>) -> Arc<Tree> {
Tree::compile(
NodeList::trusted(rows).unwrap().into_shared().unwrap(),
&Limits::default(),
)
.unwrap()
}
fn read_visits(
reader: &str,
tree: &Arc<Tree>,
data: &[u8],
refs: &[SerializedType],
limits: Limits,
) -> (Result<Parsed, ReadError>, u64) {
let data = Bytes::copy_from_slice(data);
let options = ReadOptions {
limits,
..ReadOptions::default()
};
let meter = Meter::unlimited();
let ctx = ReadCtx {
endian: Endian::Little,
ref_types: RefTypes::List(refs),
options: &options,
meter: &meter,
};
VISITS.with(|s| s.set(0));
let got = match reader {
"boost" => boost::read(&data, tree, &ctx),
_ => python::read(&data, 0, tree, &ctx),
};
(got, VISITS.with(std::cell::Cell::get))
}
fn write_visits(
p: &Parsed,
tree: &Tree,
refs: &[SerializedType],
rules: WriteRules,
limits: &Limits,
) -> (Result<(), WriteError>, u64) {
let ctx = WriteCtx {
endian: Endian::Little,
ref_types: RefTypes::List(refs),
rules,
limits,
};
let meter = Meter::unlimited();
let mut buf = DecodeBuf::new(&meter, 0, u64::MAX, LimitKind::InputMemory).unwrap();
VISITS.with(|s| s.set(0));
let got = super::write::write(p, tree, &ctx, &mut buf);
(got, VISITS.with(std::cell::Cell::get))
}
fn assert_read_refused(what: &str, got: &Result<Parsed, ReadError>, visits: u64) {
match got {
Err(ReadError {
detail: ReadDetail::Limit(l),
..
}) => assert_eq!(*l, refused(), "{what}"),
Err(e) => panic!("{what}: {e}, not the values bound"),
Ok(_) => panic!("{what}: read whole, {visits} loop turns past a bound of {BOUND}"),
}
assert!(visits <= 2 * BOUND, "{what}: {visits} loop turns");
}
fn assert_write_refused(what: &str, got: &Result<(), WriteError>, visits: u64) {
match got {
Err(WriteError::Limit(l)) => assert_eq!(*l, refused(), "{what}"),
Err(e) => panic!("{what}: {e}, not the values bound"),
Ok(()) => panic!("{what}: written whole, {visits} loop turns past a bound of {BOUND}"),
}
assert!(visits <= 2 * BOUND, "{what}: {visits} loop turns");
}
#[test]
fn skipped_data_children_count_against_the_values_bound() {
const N: u32 = 64;
const K: u32 = 1024;
let refs = ref_types(std::iter::once("C".to_owned()));
let mut rows = vec![
NodeRow::new(0, "Base", "Base"),
NodeRow::new(1, "vector", "refs"),
NodeRow::new(2, "Array", "Array"),
NodeRow::new(3, "int", "size"),
NodeRow::new(3, "ReferencedObject", "data"),
];
type_rows(&mut rows, 4, 0);
for i in 0..K {
rows.push(NodeRow::new(
4,
"ReferencedObjectData",
format!("d{i}").as_str(),
));
}
let tree = compile(rows);
let mut data = N.to_le_bytes().to_vec();
for _ in 0..N {
type_data(&mut data, 0, "");
}
assert!(u64::from(N * K) > 2 * BOUND && u64::from(N * 5) < BOUND);
for reader in ["boost", "python"] {
let (got, visits) = read_visits(reader, &tree, &data, &refs, bounded());
assert_read_refused(reader, &got, visits);
let (p, _) = read_visits(reader, &tree, &data, &refs, Limits::default());
let p = p.unwrap_or_else(|e| panic!("{reader}, unbounded: {e}"));
let (got, visits) = write_visits(&p, &tree, &refs, WriteRules::MirrorReader, &bounded());
assert_write_refused(&format!("{reader} read, MirrorReader write"), &got, visits);
}
}
#[test]
fn skipped_registries_count_against_the_values_bound() {
const N: u32 = 64;
const K: u32 = 1024;
let mut rows = vec![
NodeRow::new(0, "Base", "Base"),
NodeRow::new(1, "vector", "v"),
NodeRow::new(2, "Array", "Array"),
NodeRow::new(3, "int", "size"),
NodeRow::new(3, "Foo", "data"),
NodeRow::new(4, "int", "x"),
];
for i in 0..K {
rows.push(NodeRow::new(
4,
"ManagedReferencesRegistry",
format!("r{i}").as_str(),
));
}
let tree = compile(rows);
let mut data = N.to_le_bytes().to_vec();
for i in 0..N {
data.extend_from_slice(&i.to_le_bytes());
}
assert!(u64::from(N * (K - 1)) > 2 * BOUND && u64::from(N * 4) < BOUND);
for reader in ["boost", "python"] {
let (got, visits) = read_visits(reader, &tree, &data, &[], bounded());
assert_read_refused(reader, &got, visits);
let (p, _) = read_visits(reader, &tree, &data, &[], Limits::default());
let p = p.unwrap_or_else(|e| panic!("{reader}, unbounded: {e}"));
for rules in [WriteRules::UnityPy, WriteRules::MirrorReader] {
let (got, visits) = write_visits(&p, &tree, &[], rules, &bounded());
assert_write_refused(&format!("{reader} read, {rules:?} write"), &got, visits);
}
}
}
#[test]
fn one_value_written_through_many_same_named_children_counts_against_the_values_bound() {
const K: u32 = 64;
const N: u32 = 4096;
for first in ["Empty", "int"] {
let mut rows = vec![NodeRow::new(0, "Base", "Base")];
for elem in std::iter::repeat_n(first, K as usize - 1).chain(std::iter::once("int")) {
rows.push(NodeRow::new(1, "vector", "a"));
rows.push(NodeRow::new(2, "Array", "Array"));
rows.push(NodeRow::new(3, "int", "size"));
rows.push(NodeRow::new(3, elem, "data"));
}
let tree = compile(rows);
let mut data = vec![0; 4 * (K as usize - 1)];
data.extend_from_slice(&N.to_le_bytes());
for i in 0..N {
data.extend_from_slice(&i.to_le_bytes());
}
assert!(u64::from(K * N) > 2 * BOUND && u64::from(2 * (K + N)) < BOUND);
for reader in ["boost", "python"] {
let (p, _) = read_visits(reader, &tree, &data, &[], bounded());
let p = p.unwrap_or_else(|e| panic!("{first}, {reader}: {e}"));
for rules in [WriteRules::UnityPy, WriteRules::MirrorReader] {
let (got, visits) = write_visits(&p, &tree, &[], rules, &bounded());
let what = format!("vector<{first}>s, {reader} read, {rules:?} write");
assert_write_refused(&what, &got, visits);
}
}
}
}
#[test]
fn registries_skipped_on_a_value_that_is_not_a_dict_count_too() {
const N: u32 = 64;
const K: u32 = 1024;
let mut rows = vec![
NodeRow::new(0, "Base", "Base"),
NodeRow::new(1, "vector", "a"),
NodeRow::new(2, "Array", "Array"),
NodeRow::new(3, "int", "size"),
NodeRow::new(3, "Foo", "data"),
NodeRow::new(4, "ManagedReferencesRegistry", "real"),
];
for i in 0..K {
rows.push(NodeRow::new(
4,
"ManagedReferencesRegistry",
format!("r{i}").as_str(),
));
}
rows.extend([
NodeRow::new(1, "vector", "a"),
NodeRow::new(2, "Array", "Array"),
NodeRow::new(3, "int", "size"),
NodeRow::new(3, "int", "data"),
]);
let tree = compile(rows);
let mut data = vec![0; 4];
data.extend_from_slice(&N.to_le_bytes());
for i in 0..N {
data.extend_from_slice(&i.to_le_bytes());
}
assert!(u64::from(N * K) > 2 * BOUND && u64::from(2 * N) < BOUND);
for reader in ["boost", "python"] {
let (p, _) = read_visits(reader, &tree, &data, &[], bounded());
let p = p.unwrap_or_else(|e| panic!("{reader}: {e}"));
for rules in [WriteRules::UnityPy, WriteRules::MirrorReader] {
let (got, visits) = write_visits(&p, &tree, &[], rules, &bounded());
assert_write_refused(&format!("{reader} read, {rules:?} write"), &got, visits);
}
}
}
#[test]
fn classes_written_from_values_that_are_not_dicts_count_against_the_values_bound() {
const N: u32 = (1 << 12) + 1;
let read_with = compile(vec![
NodeRow::new(0, "Base", "Base"),
NodeRow::new(1, "vector", "v"),
NodeRow::new(2, "Array", "Array"),
NodeRow::new(3, "int", "size"),
NodeRow::new(3, "int", "data"),
]);
let write_with = |child: &str| {
let mut rows = vec![
NodeRow::new(0, "Base", "Base"),
NodeRow::new(1, "vector", "v"),
NodeRow::new(2, "Array", "Array"),
NodeRow::new(3, "int", "size"),
NodeRow::new(3, "Foo", "data"),
];
for name in ["real", "imag", "numerator", "denominator"] {
rows.push(NodeRow::new(4, child, name));
}
compile(rows)
};
let (empty, ints) = (write_with("Empty"), write_with("int"));
let mut data = N.to_le_bytes().to_vec();
for i in 0..N {
data.extend_from_slice(&i.to_le_bytes());
}
assert!(u64::from(4 * N) > BOUND && u64::from(4 * N) < 2 * BOUND);
let none = Limits {
max_values_per_object: 0,
..Limits::default()
};
for reader in ["boost", "python"] {
let (p, _) = read_visits(reader, &read_with, &data, &[], Limits::default());
let p = p.unwrap_or_else(|e| panic!("{reader}: {e}"));
for rules in [WriteRules::UnityPy, WriteRules::MirrorReader] {
let what = format!("{reader} read, {rules:?} write");
let (got, visits) = write_visits(&p, &empty, &[], rules, &bounded());
assert_write_refused(&what, &got, visits);
let (got, _) = write_visits(&p, &ints, &[], rules, &none);
got.unwrap_or_else(|e| panic!("{what}, ints under a bound of 0: {e}"));
}
}
}
#[test]
fn a_referenced_objects_repeated_names_count_against_the_values_bound() {
const N: u32 = 1 << 14;
let refs = ref_types(std::iter::once("C".to_owned()));
let mut rows = vec![
NodeRow::new(0, "Base", "Base"),
NodeRow::new(1, "ReferencedObject", "o"),
];
type_rows(&mut rows, 2, 0);
for _ in 0..2 {
rows.extend([
NodeRow::new(2, "vector", "x"),
NodeRow::new(3, "Array", "Array"),
NodeRow::new(4, "int", "size"),
NodeRow::new(4, "string", "data"),
]);
}
rows.push(NodeRow::new(2, "ReferencedObjectData", "data"));
let tree = compile(rows);
let mut data = Vec::new();
type_data(&mut data, 0, "");
data.extend_from_slice(&0_u32.to_le_bytes());
data.extend_from_slice(&N.to_le_bytes());
for _ in 0..N {
string(&mut data, "");
}
assert_eq!(u64::from(N), BOUND);
let (got, visits) = read_visits("boost", &tree, &data, &refs, bounded());
assert_read_refused("boost", &got, visits);
let (p, _) = read_visits("boost", &tree, &data, &refs, Limits::default());
let p = p.unwrap_or_else(|e| panic!("boost, unbounded: {e}"));
for rules in [WriteRules::UnityPy, WriteRules::MirrorReader] {
let (got, visits) = write_visits(&p, &tree, &refs, rules, &bounded());
assert_write_refused(&format!("boost read, {rules:?} write"), &got, visits);
}
}
#[test]
fn a_list_past_its_first_reservation_grows_in_logarithmic_moves() {
const LEN: usize = 1 << 20;
let meter = Meter::unlimited();
let mut items: MeteredVec<u8> = MeteredVec::new(&meter);
let first = super::first_reserve(LEN, usize::MAX, 1, Limits::default().max_prealloc);
items.reserve_exact(first).unwrap();
let mut moves = 0;
for _ in 0..LEN {
let capacity = items.capacity();
super::grow_step(&mut items, LEN).unwrap();
moves += u32::from(items.capacity() != capacity);
items.push(0).unwrap();
}
assert_eq!(items.capacity(), LEN);
assert_eq!(moves, 4);
}
#[test]
fn a_classs_children_are_scanned_once_at_its_trees_compile() {
use crate::typetree::tree::{INFO_READS, LEAF_SCANS};
let scans = || LEAF_SCANS.with(std::cell::Cell::get);
let infos = || INFO_READS.with(std::cell::Cell::get);
let read = |width: u32| {
let mut rows = vec![
NodeRow::new(0, "Base", "Base"),
NodeRow::new(1, "Wide", "wide"),
];
for i in 0..width {
rows.push(NodeRow::new(2, "int", format!("f{i}").as_str()));
}
LEAF_SCANS.with(|s| s.set(0));
let tree = compile(rows);
let at_compile = scans();
assert_eq!(at_compile, u64::from(width) + 1, "width {width}");
let reads: Vec<_> = (0..8)
.map(|_| {
INFO_READS.with(|s| s.set(0));
let (got, visits) = read_visits("boost", &tree, &[1, 2], &[], Limits::default());
(format!("{:?}", got.unwrap_err()), visits, infos())
})
.collect();
assert_eq!(scans(), at_compile, "width {width}");
assert!(
reads.iter().all(|r| *r == reads[0]),
"width {width}: {reads:?}"
);
reads[0].clone()
};
let (narrow, wide) = (read(16), read(4096));
assert!(narrow.2 < 16, "{narrow:?}");
assert_eq!(narrow, wide);
}