1use crate::map::{self, Keys};
2use std::cell::Cell;
3use std::fmt;
4use std::sync::{Arc, LazyLock};
5
6#[derive(Debug, Default)]
20pub enum Value {
21 #[default]
22 Null,
23 Bool(bool),
24 Number(f64),
25 String(String),
26 Array(Vec<Value>),
27 Object(Object),
28}
29
30impl Value {
31 pub fn is_null(&self) -> bool {
32 matches!(self, Value::Null)
33 }
34
35 pub fn as_str(&self) -> Option<&str> {
36 match self {
37 Value::String(s) => Some(s),
38 _ => None,
39 }
40 }
41
42 pub fn as_f64(&self) -> Option<f64> {
43 match self {
44 Value::Number(n) => Some(*n),
45 _ => None,
46 }
47 }
48
49 pub fn as_bool(&self) -> Option<bool> {
50 match self {
51 Value::Bool(b) => Some(*b),
52 _ => None,
53 }
54 }
55
56 pub fn as_array(&self) -> Option<&Vec<Value>> {
57 match self {
58 Value::Array(a) => Some(a),
59 _ => None,
60 }
61 }
62
63 pub fn as_object(&self) -> Option<&Object> {
64 match self {
65 Value::Object(o) => Some(o),
66 _ => None,
67 }
68 }
69
70 pub fn get(&self, key: &str) -> Option<&Value> {
72 self.as_object().and_then(|o| o.get(key))
73 }
74
75 pub fn at(&self, index: usize) -> Option<&Value> {
77 self.as_array().and_then(|a| a.get(index))
78 }
79
80 pub fn type_name(&self) -> &'static str {
82 match self {
83 Value::Null => "null",
84 Value::Bool(_) => "boolean",
85 Value::Number(_) => "number",
86 Value::String(_) => "string",
87 Value::Array(_) => "array",
88 Value::Object(_) => "object",
89 }
90 }
91}
92
93pub(crate) const RECURSION_DEPTH: usize = 128;
97
98impl Clone for Value {
99 fn clone(&self) -> Value {
100 match self {
101 Value::Null => Value::Null,
102 Value::Bool(b) => Value::Bool(*b),
103 Value::Number(n) => Value::Number(*n),
104 Value::String(s) => Value::String(s.clone()),
105 Value::Array(a) => Value::Array(clone_array(a, RECURSION_DEPTH)),
106 Value::Object(o) => Value::Object(o.clone()),
108 }
109 }
110}
111
112fn clone_array(array: &[Value], depth: usize) -> Vec<Value> {
114 if depth == 0 {
115 return clone_array_iteratively(array);
116 }
117 array
118 .iter()
119 .map(|v| match v {
120 Value::Array(a) => Value::Array(clone_array(a, depth - 1)),
121 v => v.clone(),
122 })
123 .collect()
124}
125
126fn clone_array_iteratively(array: &[Value]) -> Vec<Value> {
127 let mut stack = vec![(array.iter(), Vec::with_capacity(array.len()))];
129 loop {
130 let (rest, copy) = stack
131 .last_mut()
132 .expect("the outermost array is on the stack");
133 match rest.next() {
134 Some(Value::Array(a)) => stack.push((a.iter(), Vec::with_capacity(a.len()))),
135 Some(v) => copy.push(v.clone()),
136 None => {
137 let (_, done) = stack.pop().expect("checked above");
138 match stack.last_mut() {
139 Some((_, parent)) => parent.push(Value::Array(done)),
140 None => return done,
141 }
142 }
143 }
144 }
145}
146
147impl PartialEq for Value {
148 fn eq(&self, other: &Value) -> bool {
149 eq_within(self, other, RECURSION_DEPTH)
150 }
151}
152
153fn eq_within(a: &Value, b: &Value, depth: usize) -> bool {
155 match (a, b) {
156 (Value::Array(x), Value::Array(y)) if depth > 0 => {
157 x.len() == y.len() && x.iter().zip(y).all(|(x, y)| eq_within(x, y, depth - 1))
158 }
159 (Value::Object(x), Value::Object(y)) if depth > 0 => {
160 x.eq_by(y, |x, y| eq_within(x, y, depth - 1))
161 }
162 (Value::Array(_), Value::Array(_)) | (Value::Object(_), Value::Object(_)) => {
163 eq_iteratively(a, b)
164 }
165 _ => eq_scalar(a, b),
166 }
167}
168
169fn eq_iteratively<'a>(a: &'a Value, b: &'a Value) -> bool {
170 let mut pairs = vec![(a, b)];
171 while let Some((a, b)) = pairs.pop() {
172 let same = match (a, b) {
173 (Value::Array(x), Value::Array(y)) => {
174 x.len() == y.len() && {
175 pairs.extend(x.iter().zip(y));
176 true
177 }
178 }
179 (Value::Object(x), Value::Object(y)) => x.eq_by(y, |x, y| {
180 pairs.push((x, y));
181 true
182 }),
183 _ => eq_scalar(a, b),
184 };
185 if !same {
186 return false;
187 }
188 }
189 true
190}
191
192fn eq_scalar(a: &Value, b: &Value) -> bool {
194 match (a, b) {
195 (Value::Null, Value::Null) => true,
196 (Value::Bool(x), Value::Bool(y)) => x == y,
197 (Value::Number(x), Value::Number(y)) => x == y,
198 (Value::String(x), Value::String(y)) => x == y,
199 _ => false,
200 }
201}
202
203impl fmt::Display for Value {
204 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
206 f.write_str(&super::stringify(self))
207 }
208}
209
210impl From<bool> for Value {
211 fn from(b: bool) -> Self {
212 Value::Bool(b)
213 }
214}
215
216impl From<f64> for Value {
217 fn from(n: f64) -> Self {
218 Value::Number(n)
219 }
220}
221
222impl From<i64> for Value {
223 fn from(n: i64) -> Self {
224 Value::Number(n as f64)
225 }
226}
227
228impl From<i32> for Value {
229 fn from(n: i32) -> Self {
230 Value::Number(n.into())
231 }
232}
233
234impl From<&str> for Value {
235 fn from(s: &str) -> Self {
236 Value::String(s.to_owned())
237 }
238}
239
240impl From<String> for Value {
241 fn from(s: String) -> Self {
242 Value::String(s)
243 }
244}
245
246impl From<Vec<Value>> for Value {
247 fn from(a: Vec<Value>) -> Self {
248 Value::Array(a)
249 }
250}
251
252impl From<Object> for Value {
253 fn from(o: Object) -> Self {
254 Value::Object(o)
255 }
256}
257
258impl<T: Into<Value>> From<Option<T>> for Value {
259 fn from(v: Option<T>) -> Self {
260 v.map_or(Value::Null, Into::into)
261 }
262}
263
264#[derive(Clone)]
283pub struct Object {
284 keys: Arc<Keys>,
285 values: Arc<[Value]>,
286}
287
288impl Default for Object {
289 fn default() -> Self {
291 static KEYS: LazyLock<Arc<Keys>> = LazyLock::new(Arc::default);
292 static VALUES: LazyLock<Arc<[Value]>> = LazyLock::new(|| Arc::new([]));
293 Object {
294 keys: KEYS.clone(),
295 values: VALUES.clone(),
296 }
297 }
298}
299
300#[derive(Default)]
302pub(crate) struct ObjectBuilder {
303 keys: Keys,
304 values: Vec<Value>,
305 following: Option<Arc<Keys>>,
310}
311
312impl ObjectBuilder {
313 pub(crate) fn prefix(&self) -> Option<(&[String], Option<&String>)> {
316 let n = self.values.len();
317 match &self.following {
318 Some(layout) => Some((&layout.names[..n], layout.names.get(n))),
319 None if n == 0 => Some((&[], None)),
320 None => None,
321 }
322 }
323
324 pub(crate) fn follow(&mut self, layout: Arc<Keys>) {
327 debug_assert!(
328 self.prefix()
329 .is_some_and(|(p, _)| *p == layout.names[..p.len()])
330 );
331 self.values
332 .reserve(layout.names.len().saturating_sub(self.values.len()));
333 self.following = Some(layout);
334 }
335
336 pub(crate) fn push_expected(&mut self, value: Value) {
338 debug_assert!(self.prefix().is_some_and(|(_, next)| next.is_some()));
339 self.values.push(value);
340 }
341
342 fn own_keys(&mut self) {
344 if let Some(layout) = self.following.take() {
345 for name in &layout.names[..self.values.len()] {
346 let at = self.keys.names.len();
347 self.keys.insert(at, name.clone());
348 }
349 }
350 }
351
352 pub(crate) fn insert(&mut self, key: String, value: Value) -> Option<Value> {
354 self.own_keys();
355 if let Some(i) = self.keys.position(&key) {
356 return Some(std::mem::replace(&mut self.values[i], value));
357 }
358 let at = match array_index(&key) {
361 Some(n) => self
362 .keys
363 .names
364 .iter()
365 .position(|k| array_index(k).is_none_or(|m| m > n))
366 .unwrap_or(self.values.len()),
367 None => self.values.len(),
368 };
369 self.keys.insert(at, key);
370 self.values.insert(at, value);
371 None
372 }
373
374 pub(crate) fn build(mut self) -> Object {
375 if self.values.is_empty() {
376 return Object::new();
377 }
378 let keys = match self.following.take() {
379 Some(layout) if layout.names.len() == self.values.len() => layout,
380 layout => {
381 self.following = layout;
382 self.own_keys();
383 Arc::new(self.keys)
384 }
385 };
386 Object {
387 keys,
388 values: self.values.into(),
389 }
390 }
391}
392
393#[derive(Default)]
396pub(crate) struct RecentKeys(Vec<Arc<Keys>>);
397
398impl RecentKeys {
399 const SIZE: usize = 8;
400
401 pub(crate) fn find_next(
404 &self,
405 prefix: &[String],
406 mut is_next: impl FnMut(&str) -> bool,
407 ) -> Option<Arc<Keys>> {
408 let n = prefix.len();
409 self.0
410 .iter()
411 .find(|k| k.names.len() > n && k.names[..n] == *prefix && is_next(&k.names[n]))
412 .cloned()
413 }
414
415 pub(crate) fn remember(&mut self, object: &mut Object) {
418 if object.is_empty() {
419 return;
420 }
421 let same = self
422 .0
423 .iter()
424 .position(|k| Arc::ptr_eq(k, &object.keys))
425 .or_else(|| {
426 let i = self.0.iter().position(|k| k.names == object.keys.names)?;
427 object.keys = self.0[i].clone();
428 Some(i)
429 });
430 match same {
431 Some(i) => self.0[..=i].rotate_right(1),
432 None => {
433 self.0.truncate(Self::SIZE - 1);
434 self.0.insert(0, object.keys.clone());
435 }
436 }
437 }
438}
439
440fn into_vec(mut values: Arc<[Value]>) -> Vec<Value> {
442 match Arc::get_mut(&mut values) {
443 Some(owned) => owned.iter_mut().map(std::mem::take).collect(),
444 None => values.to_vec(),
445 }
446}
447
448impl Object {
449 pub fn new() -> Self {
450 Self::default()
451 }
452
453 pub fn with_capacity(_capacity: usize) -> Self {
456 Self::default()
457 }
458
459 pub fn len(&self) -> usize {
460 self.values.len()
461 }
462
463 pub fn is_empty(&self) -> bool {
464 self.values.is_empty()
465 }
466
467 pub fn get(&self, key: &str) -> Option<&Value> {
468 self.keys.position(key).map(|i| &self.values[i])
469 }
470
471 pub fn get_mut(&mut self, key: &str) -> Option<&mut Value> {
472 let i = self.keys.position(key)?;
473 Some(&mut Arc::make_mut(&mut self.values)[i])
474 }
475
476 pub fn contains_key(&self, key: &str) -> bool {
477 self.keys.position(key).is_some()
478 }
479
480 fn edit<R>(&mut self, f: impl FnOnce(&mut ObjectBuilder) -> R) -> R {
482 let Object { keys, values } = std::mem::take(self);
483 let mut builder = ObjectBuilder {
484 keys: Arc::unwrap_or_clone(keys),
485 values: into_vec(values),
486 following: None,
487 };
488 let result = f(&mut builder);
489 *self = builder.build();
490 result
491 }
492
493 pub fn insert(&mut self, key: impl Into<String>, value: Value) -> Option<Value> {
496 let key = key.into();
497 if let Some(i) = self.keys.position(&key) {
498 return Some(std::mem::replace(
499 &mut Arc::make_mut(&mut self.values)[i],
500 value,
501 ));
502 }
503 self.edit(|b| b.insert(key, value))
504 }
505
506 pub fn remove(&mut self, key: &str) -> Option<Value> {
508 let i = self.keys.position(key)?;
509 self.edit(|b| {
510 b.keys.remove(i);
511 Some(b.values.remove(i))
512 })
513 }
514
515 pub fn iter(&self) -> map::Iter<'_, Value> {
517 map::Iter::new(&self.keys.names, &self.values)
518 }
519
520 pub fn keys(&self) -> impl DoubleEndedIterator<Item = &String> + ExactSizeIterator + Clone {
521 self.keys.names.iter()
522 }
523
524 pub fn values(&self) -> impl DoubleEndedIterator<Item = &Value> + ExactSizeIterator + Clone {
525 self.values.iter()
526 }
527
528 pub fn get_index(&self, index: usize) -> Option<(&String, &Value)> {
530 Some((self.keys.names.get(index)?, &self.values[index]))
531 }
532
533 pub(crate) fn get_hinted(&self, key: &str, hint: &Cell<usize>) -> Option<&Value> {
538 if let Some((k, v)) = self.get_index(hint.get())
539 && k == key
540 {
541 return Some(v);
542 }
543 let i = self.keys.position(key)?;
544 hint.set(i);
545 Some(&self.values[i])
546 }
547
548 pub(crate) fn share_keys(&mut self, layout: &Object) -> bool {
552 if Arc::ptr_eq(&self.keys, &layout.keys) {
553 return true;
554 }
555 if self.keys.names != layout.keys.names {
556 return false;
557 }
558 self.keys = layout.keys.clone();
559 true
560 }
561}
562
563impl Object {
564 fn eq_by<'a>(
567 &'a self,
568 other: &'a Object,
569 mut eq: impl FnMut(&'a Value, &'a Value) -> bool,
570 ) -> bool {
571 if Arc::ptr_eq(&self.keys, &other.keys) {
572 return Arc::ptr_eq(&self.values, &other.values)
573 || self
574 .values
575 .iter()
576 .zip(other.values.iter())
577 .all(|(a, b)| eq(a, b));
578 }
579 self.len() == other.len()
580 && self
581 .iter()
582 .all(|(k, v)| other.get(k).is_some_and(|w| eq(v, w)))
583 }
584}
585
586impl PartialEq for Object {
587 fn eq(&self, other: &Self) -> bool {
588 self.eq_by(other, |a, b| a == b)
589 }
590}
591
592impl fmt::Debug for Object {
593 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
594 f.debug_map().entries(self.iter()).finish()
595 }
596}
597
598impl<'a> IntoIterator for &'a Object {
599 type Item = (&'a String, &'a Value);
600 type IntoIter = map::Iter<'a, Value>;
601 fn into_iter(self) -> Self::IntoIter {
602 self.iter()
603 }
604}
605
606impl IntoIterator for Object {
607 type Item = (String, Value);
608 type IntoIter = map::IntoIter<Value>;
609 fn into_iter(self) -> Self::IntoIter {
610 map::IntoIter::new(Arc::unwrap_or_clone(self.keys).names, into_vec(self.values))
611 }
612}
613
614impl<K: Into<String>> FromIterator<(K, Value)> for Object {
615 fn from_iter<I: IntoIterator<Item = (K, Value)>>(iter: I) -> Self {
618 let mut o = ObjectBuilder::default();
619 for (k, v) in iter {
620 o.insert(k.into(), v);
621 }
622 o.build()
623 }
624}
625
626pub(crate) fn array_index(key: &str) -> Option<u32> {
629 let bytes = key.as_bytes();
630 let (&first, rest) = bytes.split_first()?;
631 if !first.is_ascii_digit() || bytes.len() > 10 || (first == b'0' && !rest.is_empty()) {
632 return None;
633 }
634 let mut n = u64::from(first - b'0');
635 for &c in rest {
636 if !c.is_ascii_digit() {
637 return None;
638 }
639 n = n * 10 + u64::from(c - b'0');
640 }
641 (n < 0xFFFF_FFFF).then_some(n as u32)
642}
643
644#[macro_export]
647macro_rules! json {
648 (null) => { $crate::json::Value::Null };
649 ([ $($e:tt),* $(,)? ]) => { $crate::json::Value::Array(vec![ $( $crate::json!($e) ),* ]) };
650 ({ $($k:literal : $v:tt),* $(,)? }) => {{
651 #[allow(unused_mut)]
652 let mut o = $crate::json::Object::new();
653 $( o.insert($k, $crate::json!($v)); )*
654 $crate::json::Value::Object(o)
655 }};
656 ($e:expr) => { $crate::json::Value::from($e) };
657}
658
659#[cfg(test)]
660mod tests {
661 use super::*;
662
663 #[test]
664 fn keys_follow_js_property_order() {
665 let mut o = Object::new();
666 for k in ["b", "10", "a", "2", "01", "4294967295", "4294967294", "0"] {
667 o.insert(k, Value::Null);
668 }
669 let keys: Vec<_> = o.keys().map(String::as_str).collect();
670 assert_eq!(
671 keys,
672 ["0", "2", "10", "4294967294", "b", "a", "01", "4294967295"]
673 );
674 o.remove("2");
675 o.insert("3", Value::Null);
676 let keys: Vec<_> = o.keys().map(String::as_str).collect();
677 assert_eq!(
678 keys,
679 ["0", "3", "10", "4294967294", "b", "a", "01", "4294967295"]
680 );
681 }
682
683 #[test]
684 fn parsed_objects_with_the_same_keys_share_them() {
685 let text = r#"[{"a":1,"b":2},{"a":3,"b":4},{"a":5},{"a":6,"b":7,"c":8},
686 {"b":1,"a":2},{"a":1,"a":2,"b":3},{"\u0061":1,"b\"":2},{"1":0,"0":1,"a":2},
687 {"a":9,"b":10}]"#;
688 let Value::Array(objects) = crate::json::parse(text).unwrap() else {
689 panic!("an array");
690 };
691 let objects: Vec<&Object> = objects.iter().map(|v| v.as_object().unwrap()).collect();
692 let entries: Vec<Vec<(&str, f64)>> = objects
693 .iter()
694 .map(|o| {
695 o.iter()
696 .map(|(k, v)| (k.as_str(), v.as_f64().unwrap()))
697 .collect()
698 })
699 .collect();
700 assert_eq!(
701 entries,
702 [
703 vec![("a", 1.0), ("b", 2.0)],
704 vec![("a", 3.0), ("b", 4.0)],
705 vec![("a", 5.0)],
706 vec![("a", 6.0), ("b", 7.0), ("c", 8.0)],
707 vec![("b", 1.0), ("a", 2.0)],
708 vec![("a", 2.0), ("b", 3.0)],
709 vec![("a", 1.0), ("b\"", 2.0)],
710 vec![("0", 1.0), ("1", 0.0), ("a", 2.0)],
711 vec![("a", 9.0), ("b", 10.0)],
712 ]
713 );
714 let shared = |i: usize, j: usize| Arc::ptr_eq(&objects[i].keys, &objects[j].keys);
715 assert!(shared(0, 1) && shared(0, 8) && shared(0, 5));
716 assert!(!shared(0, 2) && !shared(0, 3) && !shared(0, 4));
717 let mut changed = objects[1].clone();
719 changed.insert("z", Value::Null);
720 assert_eq!(objects[0].keys().collect::<Vec<_>>(), ["a", "b"]);
721 assert_eq!(changed.keys().collect::<Vec<_>>(), ["a", "b", "z"]);
722 }
723
724 #[test]
725 fn a_change_to_a_copy_leaves_the_original() {
726 let mut original = Object::new();
727 original.insert("a", Value::from(1.0));
728 original.insert("b", Value::from(2.0));
729 let changes: [fn(&mut Object); 4] = [
730 |o| _ = o.insert("a", Value::from(9.0)),
731 |o| _ = o.insert("1", Value::Null),
732 |o| _ = o.remove("b"),
733 |o| *o.get_mut("a").unwrap() = Value::Null,
734 ];
735 for change in changes {
736 let mut copy = original.clone();
737 change(&mut copy);
738 assert_ne!(copy, original);
739 let keys: Vec<_> = original.iter().collect();
740 assert_eq!(
741 keys,
742 [
743 (&"a".to_owned(), &Value::from(1.0)),
744 (&"b".to_owned(), &Value::from(2.0))
745 ]
746 );
747 }
748 }
749
750 fn deepest(innermost: &str) -> String {
754 let depth = crate::json::MAX_DEPTH - 1;
755 let mut text = String::new();
756 for level in 0..depth {
757 text.push_str(if level % 2 == 0 {
758 "[1,"
759 } else {
760 r#"{"a":"x","b":"#
761 });
762 }
763 text.push_str(innermost);
764 for level in (0..depth).rev() {
765 text.push_str(if level % 2 == 0 {
766 r#",{"z":null}]"#
767 } else {
768 r#","c":[true]}"#
769 });
770 }
771 text
772 }
773
774 #[test]
775 fn values_as_deep_as_the_parser_takes_fit_in_a_thread_stack() {
776 std::thread::Builder::new()
779 .stack_size(2 << 20)
780 .spawn(|| {
781 let text = deepest("0");
782 let value = crate::json::parse(&text).unwrap();
783 assert_eq!(crate::json::stringify(&value), text);
784 let copy = value.clone();
785 assert!(copy == value);
786 let other = crate::json::parse(&deepest("1")).unwrap();
787 assert!(other != value);
788 assert!(crate::json::parse(&format!("[{text}]")).is_err());
789 })
790 .unwrap()
791 .join()
792 .unwrap();
793 }
794}