use alloc::{borrow::Cow, vec, vec::Vec};
use core::{
hash::{Hash, Hasher},
mem, slice,
};
use crate::{Array, Object, Value};
pub(crate) type Member<'a> = (Cow<'a, str>, Value<'a>);
const DROP_RECURSION: usize = 32;
pub(crate) fn drop_items(items: &mut Vec<Value<'_>>) {
for value in items.drain(..) {
drop_bounded(value, DROP_RECURSION);
}
}
pub(crate) fn drop_members(members: &mut Vec<Member<'_>>) {
for (_, value) in members.drain(..) {
drop_bounded(value, DROP_RECURSION);
}
}
fn drop_bounded(value: Value<'_>, budget: usize) {
match value {
Value::Array(mut a) => {
let items = a.items_mut();
if budget == 0 {
dismantle(mem::take(items));
} else {
for child in items.drain(..) {
drop_bounded(child, budget - 1);
}
}
}
Value::Object(mut o) => {
let members = o.members_mut();
if budget == 0 {
dismantle(members.drain(..).map(|(_, v)| v).collect());
} else {
for (_, child) in members.drain(..) {
drop_bounded(child, budget - 1);
}
}
}
_ => {}
}
}
pub(crate) fn dismantle(mut stack: Vec<Value<'_>>) {
while let Some(value) = stack.pop() {
match value {
Value::Array(mut a) => stack.append(a.items_mut()),
Value::Object(mut o) => stack.extend(o.members_mut().drain(..).map(|(_, v)| v)),
_ => {}
}
}
}
enum Out<'a> {
Array(Vec<Value<'a>>),
Object(Vec<Member<'a>>, Cow<'a, str>),
}
impl<'a> Out<'a> {
#[inline]
fn push(&mut self, value: Value<'a>) {
match self {
Self::Array(items) => items.push(value),
Self::Object(members, key) => members.push((mem::take(key), value)),
}
}
#[inline]
fn into_value(self) -> Value<'a> {
match self {
Self::Array(items) => Value::Array(Array::from(items)),
Self::Object(members, _) => Value::Object(Object::from(members)),
}
}
}
enum Borrowed<'r, 'a> {
Array(slice::Iter<'r, Value<'a>>),
Object(slice::Iter<'r, Member<'a>>),
}
fn clone_shallow<'a>(value: &Value<'a>) -> Value<'a> {
match value {
Value::Null => Value::Null,
Value::Bool(b) => Value::Bool(*b),
Value::Number(n) => Value::Number(n.clone()),
Value::String(s) => Value::String(s.clone()),
Value::Array(_) => Value::Array(Array::new()),
Value::Object(_) => Value::Object(Object::new()),
}
}
fn clone_container<'a>(src: Borrowed<'_, 'a>, out: Out<'a>) -> Value<'a> {
let mut current = (src, out);
let mut parents = Vec::new();
loop {
let next = match &mut current.0 {
Borrowed::Array(it) => it.next(),
Borrowed::Object(it) => it.next().map(|(key, value)| {
if let Out::Object(_, pending) = &mut current.1 {
*pending = key.clone();
}
value
}),
};
match next {
Some(Value::Array(a)) if !a.is_empty() => {
let child = (
Borrowed::Array(a.iter()),
Out::Array(Vec::with_capacity(a.len())),
);
parents.push(mem::replace(&mut current, child));
}
Some(Value::Object(o)) if !o.is_empty() => {
let child = (
Borrowed::Object(o.as_slice().iter()),
Out::Object(Vec::with_capacity(o.len()), Cow::Borrowed("")),
);
parents.push(mem::replace(&mut current, child));
}
Some(value) => current.1.push(clone_shallow(value)),
None => {
let Some(parent) = parents.pop() else {
return current.1.into_value();
};
let done = mem::replace(&mut current, parent).1.into_value();
current.1.push(done);
}
}
}
}
pub(crate) fn clone_items<'a>(items: &[Value<'a>]) -> Vec<Value<'a>> {
let src = Borrowed::Array(items.iter());
match clone_container(src, Out::Array(Vec::with_capacity(items.len()))) {
Value::Array(mut a) => mem::take(a.items_mut()),
_ => Vec::new(),
}
}
pub(crate) fn clone_members<'a>(members: &[Member<'a>]) -> Vec<Member<'a>> {
let out = Out::Object(Vec::with_capacity(members.len()), Cow::Borrowed(""));
match clone_container(Borrowed::Object(members.iter()), out) {
Value::Object(mut o) => mem::take(o.members_mut()),
_ => Vec::new(),
}
}
pub(crate) fn eq(a: &Value<'_>, b: &Value<'_>) -> bool {
let mut stack = Vec::new();
let (mut x, mut y) = (a, b);
loop {
match (x, y) {
(Value::Null, Value::Null) => {}
(Value::Bool(p), Value::Bool(q)) if p == q => {}
(Value::Number(p), Value::Number(q)) if p == q => {}
(Value::String(p), Value::String(q)) if p == q => {}
(Value::Array(p), Value::Array(q)) if p.len() == q.len() => {
stack.extend(p.iter().zip(q.iter()));
}
(Value::Object(p), Value::Object(q)) if p.len() == q.len() => {
for ((pk, pv), (qk, qv)) in p.as_slice().iter().zip(q.as_slice()) {
if pk != qk {
return false;
}
stack.push((pv, qv));
}
}
_ => return false,
}
match stack.pop() {
Some((p, q)) => (x, y) = (p, q),
None => return true,
}
}
}
enum Pending<'r, 'a> {
Value(&'r Value<'a>),
Key(&'r str),
}
pub(crate) fn hash<H: Hasher>(value: &Value<'_>, state: &mut H) {
let mut stack: Vec<Pending<'_, '_>> = Vec::new();
let mut next = Some(Pending::Value(value));
while let Some(item) = next.take().or_else(|| stack.pop()) {
let value = match item {
Pending::Key(key) => {
key.hash(state);
continue;
}
Pending::Value(value) => value,
};
mem::discriminant(value).hash(state);
match value {
Value::Null => {}
Value::Bool(b) => b.hash(state),
Value::Number(n) => n.as_str().hash(state),
Value::String(s) => s.as_ref().hash(state),
Value::Array(a) => {
a.len().hash(state);
stack.extend(a.iter().rev().map(Pending::Value));
}
Value::Object(o) => {
o.len().hash(state);
for (key, child) in o.as_slice().iter().rev() {
stack.push(Pending::Value(child));
stack.push(Pending::Key(key));
}
}
}
}
}
enum Owned<'a> {
Array(vec::IntoIter<Value<'a>>),
Object(vec::IntoIter<Member<'a>>),
}
pub(crate) fn into_owned(value: Value<'_>) -> Value<'static> {
let (src, out) = match value {
Value::Array(mut a) if !a.is_empty() => {
let items = mem::take(a.items_mut());
let out = Out::Array(Vec::with_capacity(items.len()));
(Owned::Array(items.into_iter()), out)
}
Value::Object(mut o) if !o.is_empty() => {
let members = mem::take(o.members_mut());
let out = Out::Object(Vec::with_capacity(members.len()), Cow::Borrowed(""));
(Owned::Object(members.into_iter()), out)
}
other => return own_shallow(other),
};
let mut current = (src, out);
let mut parents = Vec::new();
loop {
let next = match &mut current.0 {
Owned::Array(it) => it.next(),
Owned::Object(it) => it.next().map(|(key, value)| {
if let Out::Object(_, pending) = &mut current.1 {
*pending = Cow::Owned(key.into_owned());
}
value
}),
};
match next {
Some(Value::Array(mut a)) if !a.is_empty() => {
let items = mem::take(a.items_mut());
let out = Out::Array(Vec::with_capacity(items.len()));
parents.push(mem::replace(
&mut current,
(Owned::Array(items.into_iter()), out),
));
}
Some(Value::Object(mut o)) if !o.is_empty() => {
let members = mem::take(o.members_mut());
let out = Out::Object(Vec::with_capacity(members.len()), Cow::Borrowed(""));
let child = (Owned::Object(members.into_iter()), out);
parents.push(mem::replace(&mut current, child));
}
Some(value) => current.1.push(own_shallow(value)),
None => {
let Some(parent) = parents.pop() else {
return current.1.into_value();
};
let done = mem::replace(&mut current, parent).1.into_value();
current.1.push(done);
}
}
}
}
fn own_shallow(value: Value<'_>) -> Value<'static> {
match value {
Value::Null => Value::Null,
Value::Bool(b) => Value::Bool(b),
Value::Number(n) => Value::Number(n.into_owned()),
Value::String(s) => Value::String(Cow::Owned(s.into_owned())),
Value::Array(_) => Value::Array(Array::new()),
Value::Object(_) => Value::Object(Object::new()),
}
}