use crate::map::{self, Keys};
use std::cell::Cell;
use std::fmt;
use std::sync::{Arc, LazyLock};
#[derive(Debug, Default)]
pub enum Value {
#[default]
Null,
Bool(bool),
Number(f64),
String(String),
Array(Vec<Value>),
Object(Object),
}
impl Value {
pub fn is_null(&self) -> bool {
matches!(self, Value::Null)
}
pub fn as_str(&self) -> Option<&str> {
match self {
Value::String(s) => Some(s),
_ => None,
}
}
pub fn as_f64(&self) -> Option<f64> {
match self {
Value::Number(n) => Some(*n),
_ => None,
}
}
pub fn as_bool(&self) -> Option<bool> {
match self {
Value::Bool(b) => Some(*b),
_ => None,
}
}
pub fn as_array(&self) -> Option<&Vec<Value>> {
match self {
Value::Array(a) => Some(a),
_ => None,
}
}
pub fn as_object(&self) -> Option<&Object> {
match self {
Value::Object(o) => Some(o),
_ => None,
}
}
pub fn get(&self, key: &str) -> Option<&Value> {
self.as_object().and_then(|o| o.get(key))
}
pub fn at(&self, index: usize) -> Option<&Value> {
self.as_array().and_then(|a| a.get(index))
}
pub fn type_name(&self) -> &'static str {
match self {
Value::Null => "null",
Value::Bool(_) => "boolean",
Value::Number(_) => "number",
Value::String(_) => "string",
Value::Array(_) => "array",
Value::Object(_) => "object",
}
}
}
pub(crate) const RECURSION_DEPTH: usize = 128;
impl Clone for Value {
fn clone(&self) -> Value {
match self {
Value::Null => Value::Null,
Value::Bool(b) => Value::Bool(*b),
Value::Number(n) => Value::Number(*n),
Value::String(s) => Value::String(s.clone()),
Value::Array(a) => Value::Array(clone_array(a, RECURSION_DEPTH)),
Value::Object(o) => Value::Object(o.clone()),
}
}
}
fn clone_array(array: &[Value], depth: usize) -> Vec<Value> {
if depth == 0 {
return clone_array_iteratively(array);
}
array
.iter()
.map(|v| match v {
Value::Array(a) => Value::Array(clone_array(a, depth - 1)),
v => v.clone(),
})
.collect()
}
fn clone_array_iteratively(array: &[Value]) -> Vec<Value> {
let mut stack = vec![(array.iter(), Vec::with_capacity(array.len()))];
loop {
let (rest, copy) = stack
.last_mut()
.expect("the outermost array is on the stack");
match rest.next() {
Some(Value::Array(a)) => stack.push((a.iter(), Vec::with_capacity(a.len()))),
Some(v) => copy.push(v.clone()),
None => {
let (_, done) = stack.pop().expect("checked above");
match stack.last_mut() {
Some((_, parent)) => parent.push(Value::Array(done)),
None => return done,
}
}
}
}
}
impl PartialEq for Value {
fn eq(&self, other: &Value) -> bool {
eq_within(self, other, RECURSION_DEPTH)
}
}
fn eq_within(a: &Value, b: &Value, depth: usize) -> bool {
match (a, b) {
(Value::Array(x), Value::Array(y)) if depth > 0 => {
x.len() == y.len() && x.iter().zip(y).all(|(x, y)| eq_within(x, y, depth - 1))
}
(Value::Object(x), Value::Object(y)) if depth > 0 => {
x.eq_by(y, |x, y| eq_within(x, y, depth - 1))
}
(Value::Array(_), Value::Array(_)) | (Value::Object(_), Value::Object(_)) => {
eq_iteratively(a, b)
}
_ => eq_scalar(a, b),
}
}
fn eq_iteratively<'a>(a: &'a Value, b: &'a Value) -> bool {
let mut pairs = vec![(a, b)];
while let Some((a, b)) = pairs.pop() {
let same = match (a, b) {
(Value::Array(x), Value::Array(y)) => {
x.len() == y.len() && {
pairs.extend(x.iter().zip(y));
true
}
}
(Value::Object(x), Value::Object(y)) => x.eq_by(y, |x, y| {
pairs.push((x, y));
true
}),
_ => eq_scalar(a, b),
};
if !same {
return false;
}
}
true
}
fn eq_scalar(a: &Value, b: &Value) -> bool {
match (a, b) {
(Value::Null, Value::Null) => true,
(Value::Bool(x), Value::Bool(y)) => x == y,
(Value::Number(x), Value::Number(y)) => x == y,
(Value::String(x), Value::String(y)) => x == y,
_ => false,
}
}
impl fmt::Display for Value {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.write_str(&super::stringify(self))
}
}
impl From<bool> for Value {
fn from(b: bool) -> Self {
Value::Bool(b)
}
}
impl From<f64> for Value {
fn from(n: f64) -> Self {
Value::Number(n)
}
}
impl From<i64> for Value {
fn from(n: i64) -> Self {
Value::Number(n as f64)
}
}
impl From<i32> for Value {
fn from(n: i32) -> Self {
Value::Number(n.into())
}
}
impl From<&str> for Value {
fn from(s: &str) -> Self {
Value::String(s.to_owned())
}
}
impl From<String> for Value {
fn from(s: String) -> Self {
Value::String(s)
}
}
impl From<Vec<Value>> for Value {
fn from(a: Vec<Value>) -> Self {
Value::Array(a)
}
}
impl From<Object> for Value {
fn from(o: Object) -> Self {
Value::Object(o)
}
}
impl<T: Into<Value>> From<Option<T>> for Value {
fn from(v: Option<T>) -> Self {
v.map_or(Value::Null, Into::into)
}
}
#[derive(Clone)]
pub struct Object {
keys: Arc<Keys>,
values: Arc<[Value]>,
}
impl Default for Object {
fn default() -> Self {
static KEYS: LazyLock<Arc<Keys>> = LazyLock::new(Arc::default);
static VALUES: LazyLock<Arc<[Value]>> = LazyLock::new(|| Arc::new([]));
Object {
keys: KEYS.clone(),
values: VALUES.clone(),
}
}
}
#[derive(Default)]
pub(crate) struct ObjectBuilder {
keys: Keys,
values: Vec<Value>,
following: Option<Arc<Keys>>,
}
impl ObjectBuilder {
pub(crate) fn prefix(&self) -> Option<(&[String], Option<&String>)> {
let n = self.values.len();
match &self.following {
Some(layout) => Some((&layout.names[..n], layout.names.get(n))),
None if n == 0 => Some((&[], None)),
None => None,
}
}
pub(crate) fn follow(&mut self, layout: Arc<Keys>) {
debug_assert!(
self.prefix()
.is_some_and(|(p, _)| *p == layout.names[..p.len()])
);
self.values
.reserve(layout.names.len().saturating_sub(self.values.len()));
self.following = Some(layout);
}
pub(crate) fn push_expected(&mut self, value: Value) {
debug_assert!(self.prefix().is_some_and(|(_, next)| next.is_some()));
self.values.push(value);
}
fn own_keys(&mut self) {
if let Some(layout) = self.following.take() {
for name in &layout.names[..self.values.len()] {
let at = self.keys.names.len();
self.keys.insert(at, name.clone());
}
}
}
pub(crate) fn insert(&mut self, key: String, value: Value) -> Option<Value> {
self.own_keys();
if let Some(i) = self.keys.position(&key) {
return Some(std::mem::replace(&mut self.values[i], value));
}
let at = match array_index(&key) {
Some(n) => self
.keys
.names
.iter()
.position(|k| array_index(k).is_none_or(|m| m > n))
.unwrap_or(self.values.len()),
None => self.values.len(),
};
self.keys.insert(at, key);
self.values.insert(at, value);
None
}
pub(crate) fn build(mut self) -> Object {
if self.values.is_empty() {
return Object::new();
}
let keys = match self.following.take() {
Some(layout) if layout.names.len() == self.values.len() => layout,
layout => {
self.following = layout;
self.own_keys();
Arc::new(self.keys)
}
};
Object {
keys,
values: self.values.into(),
}
}
}
#[derive(Default)]
pub(crate) struct RecentKeys(Vec<Arc<Keys>>);
impl RecentKeys {
const SIZE: usize = 8;
pub(crate) fn find_next(
&self,
prefix: &[String],
mut is_next: impl FnMut(&str) -> bool,
) -> Option<Arc<Keys>> {
let n = prefix.len();
self.0
.iter()
.find(|k| k.names.len() > n && k.names[..n] == *prefix && is_next(&k.names[n]))
.cloned()
}
pub(crate) fn remember(&mut self, object: &mut Object) {
if object.is_empty() {
return;
}
let same = self
.0
.iter()
.position(|k| Arc::ptr_eq(k, &object.keys))
.or_else(|| {
let i = self.0.iter().position(|k| k.names == object.keys.names)?;
object.keys = self.0[i].clone();
Some(i)
});
match same {
Some(i) => self.0[..=i].rotate_right(1),
None => {
self.0.truncate(Self::SIZE - 1);
self.0.insert(0, object.keys.clone());
}
}
}
}
fn into_vec(mut values: Arc<[Value]>) -> Vec<Value> {
match Arc::get_mut(&mut values) {
Some(owned) => owned.iter_mut().map(std::mem::take).collect(),
None => values.to_vec(),
}
}
impl Object {
pub fn new() -> Self {
Self::default()
}
pub fn with_capacity(_capacity: usize) -> Self {
Self::default()
}
pub fn len(&self) -> usize {
self.values.len()
}
pub fn is_empty(&self) -> bool {
self.values.is_empty()
}
pub fn get(&self, key: &str) -> Option<&Value> {
self.keys.position(key).map(|i| &self.values[i])
}
pub fn get_mut(&mut self, key: &str) -> Option<&mut Value> {
let i = self.keys.position(key)?;
Some(&mut Arc::make_mut(&mut self.values)[i])
}
pub fn contains_key(&self, key: &str) -> bool {
self.keys.position(key).is_some()
}
fn edit<R>(&mut self, f: impl FnOnce(&mut ObjectBuilder) -> R) -> R {
let Object { keys, values } = std::mem::take(self);
let mut builder = ObjectBuilder {
keys: Arc::unwrap_or_clone(keys),
values: into_vec(values),
following: None,
};
let result = f(&mut builder);
*self = builder.build();
result
}
pub fn insert(&mut self, key: impl Into<String>, value: Value) -> Option<Value> {
let key = key.into();
if let Some(i) = self.keys.position(&key) {
return Some(std::mem::replace(
&mut Arc::make_mut(&mut self.values)[i],
value,
));
}
self.edit(|b| b.insert(key, value))
}
pub fn remove(&mut self, key: &str) -> Option<Value> {
let i = self.keys.position(key)?;
self.edit(|b| {
b.keys.remove(i);
Some(b.values.remove(i))
})
}
pub fn iter(&self) -> map::Iter<'_, Value> {
map::Iter::new(&self.keys.names, &self.values)
}
pub fn keys(&self) -> impl DoubleEndedIterator<Item = &String> + ExactSizeIterator + Clone {
self.keys.names.iter()
}
pub fn values(&self) -> impl DoubleEndedIterator<Item = &Value> + ExactSizeIterator + Clone {
self.values.iter()
}
pub fn get_index(&self, index: usize) -> Option<(&String, &Value)> {
Some((self.keys.names.get(index)?, &self.values[index]))
}
pub(crate) fn get_hinted(&self, key: &str, hint: &Cell<usize>) -> Option<&Value> {
if let Some((k, v)) = self.get_index(hint.get())
&& k == key
{
return Some(v);
}
let i = self.keys.position(key)?;
hint.set(i);
Some(&self.values[i])
}
pub(crate) fn share_keys(&mut self, layout: &Object) -> bool {
if Arc::ptr_eq(&self.keys, &layout.keys) {
return true;
}
if self.keys.names != layout.keys.names {
return false;
}
self.keys = layout.keys.clone();
true
}
}
impl Object {
fn eq_by<'a>(
&'a self,
other: &'a Object,
mut eq: impl FnMut(&'a Value, &'a Value) -> bool,
) -> bool {
if Arc::ptr_eq(&self.keys, &other.keys) {
return Arc::ptr_eq(&self.values, &other.values)
|| self
.values
.iter()
.zip(other.values.iter())
.all(|(a, b)| eq(a, b));
}
self.len() == other.len()
&& self
.iter()
.all(|(k, v)| other.get(k).is_some_and(|w| eq(v, w)))
}
}
impl PartialEq for Object {
fn eq(&self, other: &Self) -> bool {
self.eq_by(other, |a, b| a == b)
}
}
impl fmt::Debug for Object {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_map().entries(self.iter()).finish()
}
}
impl<'a> IntoIterator for &'a Object {
type Item = (&'a String, &'a Value);
type IntoIter = map::Iter<'a, Value>;
fn into_iter(self) -> Self::IntoIter {
self.iter()
}
}
impl IntoIterator for Object {
type Item = (String, Value);
type IntoIter = map::IntoIter<Value>;
fn into_iter(self) -> Self::IntoIter {
map::IntoIter::new(Arc::unwrap_or_clone(self.keys).names, into_vec(self.values))
}
}
impl<K: Into<String>> FromIterator<(K, Value)> for Object {
fn from_iter<I: IntoIterator<Item = (K, Value)>>(iter: I) -> Self {
let mut o = ObjectBuilder::default();
for (k, v) in iter {
o.insert(k.into(), v);
}
o.build()
}
}
pub(crate) fn array_index(key: &str) -> Option<u32> {
let bytes = key.as_bytes();
let (&first, rest) = bytes.split_first()?;
if !first.is_ascii_digit() || bytes.len() > 10 || (first == b'0' && !rest.is_empty()) {
return None;
}
let mut n = u64::from(first - b'0');
for &c in rest {
if !c.is_ascii_digit() {
return None;
}
n = n * 10 + u64::from(c - b'0');
}
(n < 0xFFFF_FFFF).then_some(n as u32)
}
#[macro_export]
macro_rules! json {
(null) => { $crate::json::Value::Null };
([ $($e:tt),* $(,)? ]) => { $crate::json::Value::Array(vec![ $( $crate::json!($e) ),* ]) };
({ $($k:literal : $v:tt),* $(,)? }) => {{
#[allow(unused_mut)]
let mut o = $crate::json::Object::new();
$( o.insert($k, $crate::json!($v)); )*
$crate::json::Value::Object(o)
}};
($e:expr) => { $crate::json::Value::from($e) };
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn keys_follow_js_property_order() {
let mut o = Object::new();
for k in ["b", "10", "a", "2", "01", "4294967295", "4294967294", "0"] {
o.insert(k, Value::Null);
}
let keys: Vec<_> = o.keys().map(String::as_str).collect();
assert_eq!(
keys,
["0", "2", "10", "4294967294", "b", "a", "01", "4294967295"]
);
o.remove("2");
o.insert("3", Value::Null);
let keys: Vec<_> = o.keys().map(String::as_str).collect();
assert_eq!(
keys,
["0", "3", "10", "4294967294", "b", "a", "01", "4294967295"]
);
}
#[test]
fn parsed_objects_with_the_same_keys_share_them() {
let text = r#"[{"a":1,"b":2},{"a":3,"b":4},{"a":5},{"a":6,"b":7,"c":8},
{"b":1,"a":2},{"a":1,"a":2,"b":3},{"\u0061":1,"b\"":2},{"1":0,"0":1,"a":2},
{"a":9,"b":10}]"#;
let Value::Array(objects) = crate::json::parse(text).unwrap() else {
panic!("an array");
};
let objects: Vec<&Object> = objects.iter().map(|v| v.as_object().unwrap()).collect();
let entries: Vec<Vec<(&str, f64)>> = objects
.iter()
.map(|o| {
o.iter()
.map(|(k, v)| (k.as_str(), v.as_f64().unwrap()))
.collect()
})
.collect();
assert_eq!(
entries,
[
vec![("a", 1.0), ("b", 2.0)],
vec![("a", 3.0), ("b", 4.0)],
vec![("a", 5.0)],
vec![("a", 6.0), ("b", 7.0), ("c", 8.0)],
vec![("b", 1.0), ("a", 2.0)],
vec![("a", 2.0), ("b", 3.0)],
vec![("a", 1.0), ("b\"", 2.0)],
vec![("0", 1.0), ("1", 0.0), ("a", 2.0)],
vec![("a", 9.0), ("b", 10.0)],
]
);
let shared = |i: usize, j: usize| Arc::ptr_eq(&objects[i].keys, &objects[j].keys);
assert!(shared(0, 1) && shared(0, 8) && shared(0, 5));
assert!(!shared(0, 2) && !shared(0, 3) && !shared(0, 4));
let mut changed = objects[1].clone();
changed.insert("z", Value::Null);
assert_eq!(objects[0].keys().collect::<Vec<_>>(), ["a", "b"]);
assert_eq!(changed.keys().collect::<Vec<_>>(), ["a", "b", "z"]);
}
#[test]
fn a_change_to_a_copy_leaves_the_original() {
let mut original = Object::new();
original.insert("a", Value::from(1.0));
original.insert("b", Value::from(2.0));
let changes: [fn(&mut Object); 4] = [
|o| _ = o.insert("a", Value::from(9.0)),
|o| _ = o.insert("1", Value::Null),
|o| _ = o.remove("b"),
|o| *o.get_mut("a").unwrap() = Value::Null,
];
for change in changes {
let mut copy = original.clone();
change(&mut copy);
assert_ne!(copy, original);
let keys: Vec<_> = original.iter().collect();
assert_eq!(
keys,
[
(&"a".to_owned(), &Value::from(1.0)),
(&"b".to_owned(), &Value::from(2.0))
]
);
}
}
fn deepest(innermost: &str) -> String {
let depth = crate::json::MAX_DEPTH - 1;
let mut text = String::new();
for level in 0..depth {
text.push_str(if level % 2 == 0 {
"[1,"
} else {
r#"{"a":"x","b":"#
});
}
text.push_str(innermost);
for level in (0..depth).rev() {
text.push_str(if level % 2 == 0 {
r#",{"z":null}]"#
} else {
r#","c":[true]}"#
});
}
text
}
#[test]
fn values_as_deep_as_the_parser_takes_fit_in_a_thread_stack() {
std::thread::Builder::new()
.stack_size(2 << 20)
.spawn(|| {
let text = deepest("0");
let value = crate::json::parse(&text).unwrap();
assert_eq!(crate::json::stringify(&value), text);
let copy = value.clone();
assert!(copy == value);
let other = crate::json::parse(&deepest("1")).unwrap();
assert!(other != value);
assert!(crate::json::parse(&format!("[{text}]")).is_err());
})
.unwrap()
.join()
.unwrap();
}
}