Skip to main content

zero_client/json/
value.rs

1use crate::map::{self, Keys};
2use std::cell::Cell;
3use std::fmt;
4use std::sync::{Arc, LazyLock};
5
6/// A JSON value, the data model Zero syncs and stores.
7///
8/// Numbers are `f64`, as they are in JS: integers are exact up to 2^53.
9/// Objects are [`Object`]s, which keep their keys in JS property order.
10///
11/// Rust strings compare by code point, which for valid strings is the same
12/// as comparing by UTF-16 code unit, as JS `===` does. A Rust `String` can't
13/// hold a lone surrogate, which a JS string can (see `rust/PARITY.md`).
14///
15/// Cloning, comparing, writing, and dropping a value as deep as the parser
16/// allows ([`MAX_DEPTH`](super::MAX_DEPTH)) fit in a 2 MB thread stack:
17/// the first three go on over a heap stack past a hundred or so levels.
18/// `Debug` formatting still recurses.
19#[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    /// The value of `key` when this is an object that has it.
71    pub fn get(&self, key: &str) -> Option<&Value> {
72        self.as_object().and_then(|o| o.get(key))
73    }
74
75    /// The element at `index` when this is an array that long.
76    pub fn at(&self, index: usize) -> Option<&Value> {
77        self.as_array().and_then(|a| a.get(index))
78    }
79
80    /// The JS `typeof`-style name of the value's type, for error messages.
81    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
93/// How many levels deep cloning, comparing, and writing a value recurse
94/// before they go on over a heap stack. Values nest a few levels in
95/// practice, and these keep the recursive versions' speed for them.
96pub(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            // An object's values are shared, so this doesn't recurse.
107            Value::Object(o) => Value::Object(o.clone()),
108        }
109    }
110}
111
112/// Clones an array, recursing into nested arrays `depth` levels deep.
113fn 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    // The arrays being copied, each with what it has of its copy so far.
128    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
153/// Compares two values, recursing `depth` levels deep.
154fn 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
192/// Whether two values that aren't both arrays or both objects are equal.
193fn 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    /// The value as `JSON.stringify` writes it.
205    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/// A JSON object: string keys to [`Value`]s, with keys kept the way a JS
265/// object keeps its properties.
266///
267/// Keys are in JS property order: integer-like keys (array indices, such as
268/// `"0"` and `"10"`, but not `"01"`) first in ascending numeric order, then
269/// the others in the order they were first set. This is the order
270/// `Object.keys` and `JSON.stringify` use.
271///
272/// Setting a key that is already there replaces its value and keeps its
273/// place, as assigning to an existing property does in JS. Two objects are
274/// equal when they have the same keys with equal values, in any order.
275///
276/// The keys are kept apart from the values, in a list that objects with the
277/// same keys in the same order can share: the rows of a table share one, the
278/// table's layout, as JS engines' hidden classes do, so reading a row's
279/// column reaches its value without touching a copy of the column's name.
280/// Cloning an object is cheap: copies share their values until one of them
281/// is changed.
282#[derive(Clone)]
283pub struct Object {
284    keys: Arc<Keys>,
285    values: Arc<[Value]>,
286}
287
288impl Default for Object {
289    /// An empty object, which allocates nothing.
290    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/// An object being built, before its keys and values are shared.
301#[derive(Default)]
302pub(crate) struct ObjectBuilder {
303    keys: Keys,
304    values: Vec<Value>,
305    /// The keys of another object, which this one has had so far: its keys
306    /// are the first `values.len()` of them, and `keys` is empty. The parser
307    /// follows a recent object's keys, so that the rows of a table share
308    /// their keys without the keys being allocated.
309    following: Option<Arc<Keys>>,
310}
311
312impl ObjectBuilder {
313    /// The keys so far and the next key of the layout it follows, while it
314    /// follows one or has no keys yet.
315    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    /// Follows `layout`, whose first keys are the keys so far (see
325    /// `following`).
326    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    /// Sets the next key of the layout it follows to `value`.
337    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    /// Stops following a layout: the object gets its own keys.
343    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    /// [`Object::insert`].
353    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        // An integer-like key goes among the integer-like keys at the front,
359        // in numeric order.
360        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/// The keys of the objects a parse built last, most recent first, which
394/// the next objects follow when their keys match.
395#[derive(Default)]
396pub(crate) struct RecentKeys(Vec<Arc<Keys>>);
397
398impl RecentKeys {
399    const SIZE: usize = 8;
400
401    /// The most recent keys that start with `prefix` and then a key that
402    /// `is_next` accepts.
403    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    /// Makes `object`'s keys the most recent. An object that has the same
416    /// keys as a recent one, which it built its own of, shares them.
417    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
440/// The values, moved out when nothing else shares them.
441fn 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    /// An empty object. Its values are allocated once it has keys, so the
454    /// capacity isn't used.
455    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    /// Changes the keys, after which the object has its own.
481    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    /// Sets `key` to `value`, returning the value it replaced. A new key goes
494    /// after the others, or among the integer-like keys in numeric order.
495    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    /// Removes `key`, returning its value. The other keys keep their order.
507    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    /// The entries, in order.
516    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    /// The entry at `index`, in order.
529    pub fn get_index(&self, index: usize) -> Option<(&String, &Value)> {
530        Some((self.keys.names.get(index)?, &self.values[index]))
531    }
532
533    /// [`Object::get`], looking first at the position in `hint`, where the
534    /// key was in the last object looked up: the rows of a table have their
535    /// columns in the same places, so a comparator or a filter finds a
536    /// column without searching the names.
537    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    /// Shares `layout`'s keys when they are this object's keys in the same
549    /// order, so the two keep one list of them. Returns whether the keys
550    /// are shared now.
551    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    /// Whether the two have the same keys and `eq` holds for each key's
565    /// two values.
566    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    /// A key that repeats keeps its first place and its last value, as in a
616    /// JS object literal.
617    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
626/// The value of `key` if it is an array index (a canonical integer below
627/// 2^32 - 1), which JS orders before other property keys.
628pub(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/// Builds a [`Value`] from JSON-like syntax, for tests and fixtures:
645/// `json!({"a": [1, null, "x"]})`.
646#[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        // A change to an object whose keys are shared leaves the others'.
718        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    /// JSON as deep as the parser takes, its levels alternating between
751    /// arrays and objects with elements before and after the nested one
752    /// (the innermost level's are one level deeper).
753    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        // The default stack of a spawned thread; a debug build overflows it
777        // by a few thousand levels of recursion.
778        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}