use super::{ListIx, Map, PrimArray, Value};
use crate::typetree::NodeId;
impl Value {
fn nests(&self) -> bool {
match self {
Self::List(items) => !items.is_empty(),
Self::Tuple(items) => !items.is_empty(),
Self::Dict(map) => !map.entries.is_empty(),
_ => false,
}
}
fn deep(&self) -> bool {
match self {
Self::List(items) => items.iter().any(Self::nests),
Self::Tuple(items) => items.iter().any(Self::nests),
Self::Dict(map) => map.entries.iter().any(|(_, v)| v.nests()),
_ => false,
}
}
fn take_items(&mut self) -> Pile {
match self {
Self::List(items) => Pile::Values(std::mem::take(items)),
Self::Tuple(items) => Pile::Values(std::mem::take(items).into_vec()),
Self::Dict(map) => Pile::Entries(std::mem::take(&mut map.entries)),
_ => Pile::Values(Vec::new()),
}
}
}
enum Pile {
Values(Vec<Value>),
Entries(Vec<(NodeId, Value)>),
}
impl Pile {
fn pop(&mut self) -> Option<Value> {
match self {
Self::Values(items) => items.pop(),
Self::Entries(entries) => entries.pop().map(|(_, v)| v),
}
}
fn is_empty(&self) -> bool {
match self {
Self::Values(items) => items.is_empty(),
Self::Entries(entries) => entries.is_empty(),
}
}
fn into_value(self) -> Value {
match self {
Self::Values(items) => Value::List(items),
Self::Entries(entries) => Value::Dict(Map {
list: ListIx::default(),
entries,
}),
}
}
fn put_back(&mut self, value: Value) {
match self {
Self::Values(items) => items.push(value),
Self::Entries(entries) => entries.push((NodeId(0), value)),
}
}
}
impl Drop for Value {
fn drop(&mut self) {
if !self.deep() {
return;
}
let mut pile = self.take_items();
let mut up: Option<Value> = None;
let mut saved = 0_usize;
loop {
let Some(mut value) = pile.pop() else {
let Some(mut link) = up.take() else {
break;
};
pile = link.take_items();
saved -= 1;
if saved > 0 {
up = pile.pop();
}
continue;
};
if !value.nests() {
continue;
}
let items = value.take_items();
drop(value);
if !pile.is_empty() {
if let Some(link) = up.take() {
pile.put_back(link);
}
up = Some(std::mem::replace(&mut pile, Pile::Values(Vec::new())).into_value());
saved += 1;
}
pile = items;
}
}
}
const INLINE_OPENS: usize = 16;
struct Stack<T> {
inline: [T; INLINE_OPENS],
len: usize,
spill: Vec<T>,
}
impl<T: Default> Stack<T> {
fn new() -> Self {
Self {
inline: Default::default(),
len: 0,
spill: Vec::new(),
}
}
fn push(&mut self, item: T) {
match self.inline.get_mut(self.len) {
Some(slot) => *slot = item,
None => self.spill.push(item),
}
self.len += 1;
}
fn last_mut(&mut self) -> Option<&mut T> {
let at = self.len.checked_sub(1)?;
match self.inline.get_mut(at) {
Some(slot) => Some(slot),
None => self.spill.last_mut(),
}
}
fn pop(&mut self) {
if self.len > INLINE_OPENS {
self.spill.pop();
}
self.len = self.len.saturating_sub(1);
}
}
impl crate::pin::Slices for Value {
fn each(&mut self, f: &mut dyn FnMut(crate::pin::Slice<'_>)) {
use crate::pin::Slice;
enum Open<'a> {
Items(std::slice::IterMut<'a, Value>),
Entries(std::slice::IterMut<'a, (NodeId, Value)>),
}
impl Default for Open<'_> {
fn default() -> Self {
Self::Items(std::slice::IterMut::default())
}
}
let mut opens: Stack<Open<'_>> = Stack::new();
let mut next = Some(self);
loop {
let value = if let Some(value) = next.take() {
value
} else {
let Some(open) = opens.last_mut() else {
break;
};
let item = match open {
Open::Items(items) => items.next(),
Open::Entries(entries) => entries.next().map(|(_, v)| v),
};
let Some(item) = item else {
opens.pop();
continue;
};
item
};
match value {
Self::Str(s) => f(Slice::Str(s)),
Self::Bytes(b) | Self::Prims(PrimArray::U8(b)) => f(Slice::Bytes(b)),
Self::List(items) => opens.push(Open::Items(items.iter_mut())),
Self::Tuple(items) => opens.push(Open::Items(items.iter_mut())),
Self::Dict(m) => opens.push(Open::Entries(m.entries.iter_mut())),
Self::Bool(_)
| Self::Int(_)
| Self::UInt(_)
| Self::F32(_)
| Self::F64(_)
| Self::Prims(_) => {}
}
}
}
}
#[cfg(test)]
mod tests {
use super::super::{ListIx, Map, Value};
use crate::typetree::NodeId;
#[test]
fn a_wide_list_of_short_lists_drops_in_linear_time() {
let n = 200_000;
let mut outer = Vec::with_capacity(2 * n);
outer.extend((0..n).map(|_| Value::List(Vec::new())));
outer.extend((0..n).map(|_| {
Value::List(vec![Value::Dict(Map {
list: ListIx::default(),
entries: vec![(NodeId(0), Value::Int(1))],
})])
}));
timed(Value::List(outer));
}
#[test]
fn a_deep_comb_drops_in_linear_time() {
let k = 2_000;
let mut value = Value::Int(0);
for _ in 0..512 {
let mut level: Vec<Value> = (0..k).map(|i| Value::List(vec![Value::Int(i)])).collect();
level.insert(level.len() / 2, value);
value = Value::List(level);
}
timed(value);
}
fn timed(value: Value) {
let start = std::time::Instant::now();
drop(value);
let took = start.elapsed();
assert!(
took < std::time::Duration::from_secs(5),
"dropped in {took:?}"
);
}
}