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#[derive(Clone, Debug, PartialEq, Default)]
15pub enum Value {
16    #[default]
17    Null,
18    Bool(bool),
19    Number(f64),
20    String(String),
21    Array(Vec<Value>),
22    Object(Object),
23}
24
25impl Value {
26    pub fn is_null(&self) -> bool {
27        matches!(self, Value::Null)
28    }
29
30    pub fn as_str(&self) -> Option<&str> {
31        match self {
32            Value::String(s) => Some(s),
33            _ => None,
34        }
35    }
36
37    pub fn as_f64(&self) -> Option<f64> {
38        match self {
39            Value::Number(n) => Some(*n),
40            _ => None,
41        }
42    }
43
44    pub fn as_bool(&self) -> Option<bool> {
45        match self {
46            Value::Bool(b) => Some(*b),
47            _ => None,
48        }
49    }
50
51    pub fn as_array(&self) -> Option<&Vec<Value>> {
52        match self {
53            Value::Array(a) => Some(a),
54            _ => None,
55        }
56    }
57
58    pub fn as_object(&self) -> Option<&Object> {
59        match self {
60            Value::Object(o) => Some(o),
61            _ => None,
62        }
63    }
64
65    /// The value of `key` when this is an object that has it.
66    pub fn get(&self, key: &str) -> Option<&Value> {
67        self.as_object().and_then(|o| o.get(key))
68    }
69
70    /// The element at `index` when this is an array that long.
71    pub fn at(&self, index: usize) -> Option<&Value> {
72        self.as_array().and_then(|a| a.get(index))
73    }
74
75    /// The JS `typeof`-style name of the value's type, for error messages.
76    pub fn type_name(&self) -> &'static str {
77        match self {
78            Value::Null => "null",
79            Value::Bool(_) => "boolean",
80            Value::Number(_) => "number",
81            Value::String(_) => "string",
82            Value::Array(_) => "array",
83            Value::Object(_) => "object",
84        }
85    }
86}
87
88impl fmt::Display for Value {
89    /// The value as `JSON.stringify` writes it.
90    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
91        f.write_str(&super::stringify(self))
92    }
93}
94
95impl From<bool> for Value {
96    fn from(b: bool) -> Self {
97        Value::Bool(b)
98    }
99}
100
101impl From<f64> for Value {
102    fn from(n: f64) -> Self {
103        Value::Number(n)
104    }
105}
106
107impl From<i64> for Value {
108    fn from(n: i64) -> Self {
109        Value::Number(n as f64)
110    }
111}
112
113impl From<i32> for Value {
114    fn from(n: i32) -> Self {
115        Value::Number(n.into())
116    }
117}
118
119impl From<&str> for Value {
120    fn from(s: &str) -> Self {
121        Value::String(s.to_owned())
122    }
123}
124
125impl From<String> for Value {
126    fn from(s: String) -> Self {
127        Value::String(s)
128    }
129}
130
131impl From<Vec<Value>> for Value {
132    fn from(a: Vec<Value>) -> Self {
133        Value::Array(a)
134    }
135}
136
137impl From<Object> for Value {
138    fn from(o: Object) -> Self {
139        Value::Object(o)
140    }
141}
142
143impl<T: Into<Value>> From<Option<T>> for Value {
144    fn from(v: Option<T>) -> Self {
145        v.map_or(Value::Null, Into::into)
146    }
147}
148
149/// A JSON object: string keys to [`Value`]s, with keys kept the way a JS
150/// object keeps its properties.
151///
152/// Keys are in JS property order: integer-like keys (array indices, such as
153/// `"0"` and `"10"`, but not `"01"`) first in ascending numeric order, then
154/// the others in the order they were first set. This is the order
155/// `Object.keys` and `JSON.stringify` use.
156///
157/// Setting a key that is already there replaces its value and keeps its
158/// place, as assigning to an existing property does in JS. Two objects are
159/// equal when they have the same keys with equal values, in any order.
160///
161/// The keys are kept apart from the values, in a list that objects with the
162/// same keys in the same order can share: the rows of a table share one, the
163/// table's layout, as JS engines' hidden classes do, so reading a row's
164/// column reaches its value without touching a copy of the column's name.
165/// Cloning an object is cheap: copies share their values until one of them
166/// is changed.
167#[derive(Clone)]
168pub struct Object {
169    keys: Arc<Keys>,
170    values: Arc<[Value]>,
171}
172
173impl Default for Object {
174    /// An empty object, which allocates nothing.
175    fn default() -> Self {
176        static KEYS: LazyLock<Arc<Keys>> = LazyLock::new(Arc::default);
177        static VALUES: LazyLock<Arc<[Value]>> = LazyLock::new(|| Arc::new([]));
178        Object {
179            keys: KEYS.clone(),
180            values: VALUES.clone(),
181        }
182    }
183}
184
185/// An object being built, before its keys and values are shared.
186#[derive(Default)]
187pub(crate) struct ObjectBuilder {
188    keys: Keys,
189    values: Vec<Value>,
190    /// The keys of another object, which this one has had so far: its keys
191    /// are the first `values.len()` of them, and `keys` is empty. The parser
192    /// follows a recent object's keys, so that the rows of a table share
193    /// their keys without the keys being allocated.
194    following: Option<Arc<Keys>>,
195}
196
197impl ObjectBuilder {
198    /// The keys so far and the next key of the layout it follows, while it
199    /// follows one or has no keys yet.
200    pub(crate) fn prefix(&self) -> Option<(&[String], Option<&String>)> {
201        let n = self.values.len();
202        match &self.following {
203            Some(layout) => Some((&layout.names[..n], layout.names.get(n))),
204            None if n == 0 => Some((&[], None)),
205            None => None,
206        }
207    }
208
209    /// Follows `layout`, whose first keys are the keys so far (see
210    /// `following`).
211    pub(crate) fn follow(&mut self, layout: Arc<Keys>) {
212        debug_assert!(
213            self.prefix()
214                .is_some_and(|(p, _)| *p == layout.names[..p.len()])
215        );
216        self.values
217            .reserve(layout.names.len().saturating_sub(self.values.len()));
218        self.following = Some(layout);
219    }
220
221    /// Sets the next key of the layout it follows to `value`.
222    pub(crate) fn push_expected(&mut self, value: Value) {
223        debug_assert!(self.prefix().is_some_and(|(_, next)| next.is_some()));
224        self.values.push(value);
225    }
226
227    /// Stops following a layout: the object gets its own keys.
228    fn own_keys(&mut self) {
229        if let Some(layout) = self.following.take() {
230            for name in &layout.names[..self.values.len()] {
231                let at = self.keys.names.len();
232                self.keys.insert(at, name.clone());
233            }
234        }
235    }
236
237    /// [`Object::insert`].
238    pub(crate) fn insert(&mut self, key: String, value: Value) -> Option<Value> {
239        self.own_keys();
240        if let Some(i) = self.keys.position(&key) {
241            return Some(std::mem::replace(&mut self.values[i], value));
242        }
243        // An integer-like key goes among the integer-like keys at the front,
244        // in numeric order.
245        let at = match array_index(&key) {
246            Some(n) => self
247                .keys
248                .names
249                .iter()
250                .position(|k| array_index(k).is_none_or(|m| m > n))
251                .unwrap_or(self.values.len()),
252            None => self.values.len(),
253        };
254        self.keys.insert(at, key);
255        self.values.insert(at, value);
256        None
257    }
258
259    pub(crate) fn build(mut self) -> Object {
260        if self.values.is_empty() {
261            return Object::new();
262        }
263        let keys = match self.following.take() {
264            Some(layout) if layout.names.len() == self.values.len() => layout,
265            layout => {
266                self.following = layout;
267                self.own_keys();
268                Arc::new(self.keys)
269            }
270        };
271        Object {
272            keys,
273            values: self.values.into(),
274        }
275    }
276}
277
278/// The keys of the objects a parse built last, most recent first, which
279/// the next objects follow when their keys match.
280#[derive(Default)]
281pub(crate) struct RecentKeys(Vec<Arc<Keys>>);
282
283impl RecentKeys {
284    const SIZE: usize = 8;
285
286    /// The most recent keys that start with `prefix` and then a key that
287    /// `is_next` accepts.
288    pub(crate) fn find_next(
289        &self,
290        prefix: &[String],
291        mut is_next: impl FnMut(&str) -> bool,
292    ) -> Option<Arc<Keys>> {
293        let n = prefix.len();
294        self.0
295            .iter()
296            .find(|k| k.names.len() > n && k.names[..n] == *prefix && is_next(&k.names[n]))
297            .cloned()
298    }
299
300    /// Makes `object`'s keys the most recent. An object that has the same
301    /// keys as a recent one, which it built its own of, shares them.
302    pub(crate) fn remember(&mut self, object: &mut Object) {
303        if object.is_empty() {
304            return;
305        }
306        let same = self
307            .0
308            .iter()
309            .position(|k| Arc::ptr_eq(k, &object.keys))
310            .or_else(|| {
311                let i = self.0.iter().position(|k| k.names == object.keys.names)?;
312                object.keys = self.0[i].clone();
313                Some(i)
314            });
315        match same {
316            Some(i) => self.0[..=i].rotate_right(1),
317            None => {
318                self.0.truncate(Self::SIZE - 1);
319                self.0.insert(0, object.keys.clone());
320            }
321        }
322    }
323}
324
325/// The values, moved out when nothing else shares them.
326fn into_vec(mut values: Arc<[Value]>) -> Vec<Value> {
327    match Arc::get_mut(&mut values) {
328        Some(owned) => owned.iter_mut().map(std::mem::take).collect(),
329        None => values.to_vec(),
330    }
331}
332
333impl Object {
334    pub fn new() -> Self {
335        Self::default()
336    }
337
338    /// An empty object. Its values are allocated once it has keys, so the
339    /// capacity isn't used.
340    pub fn with_capacity(_capacity: usize) -> Self {
341        Self::default()
342    }
343
344    pub fn len(&self) -> usize {
345        self.values.len()
346    }
347
348    pub fn is_empty(&self) -> bool {
349        self.values.is_empty()
350    }
351
352    pub fn get(&self, key: &str) -> Option<&Value> {
353        self.keys.position(key).map(|i| &self.values[i])
354    }
355
356    pub fn get_mut(&mut self, key: &str) -> Option<&mut Value> {
357        let i = self.keys.position(key)?;
358        Some(&mut Arc::make_mut(&mut self.values)[i])
359    }
360
361    pub fn contains_key(&self, key: &str) -> bool {
362        self.keys.position(key).is_some()
363    }
364
365    /// Changes the keys, after which the object has its own.
366    fn edit<R>(&mut self, f: impl FnOnce(&mut ObjectBuilder) -> R) -> R {
367        let Object { keys, values } = std::mem::take(self);
368        let mut builder = ObjectBuilder {
369            keys: Arc::unwrap_or_clone(keys),
370            values: into_vec(values),
371            following: None,
372        };
373        let result = f(&mut builder);
374        *self = builder.build();
375        result
376    }
377
378    /// Sets `key` to `value`, returning the value it replaced. A new key goes
379    /// after the others, or among the integer-like keys in numeric order.
380    pub fn insert(&mut self, key: impl Into<String>, value: Value) -> Option<Value> {
381        let key = key.into();
382        if let Some(i) = self.keys.position(&key) {
383            return Some(std::mem::replace(
384                &mut Arc::make_mut(&mut self.values)[i],
385                value,
386            ));
387        }
388        self.edit(|b| b.insert(key, value))
389    }
390
391    /// Removes `key`, returning its value. The other keys keep their order.
392    pub fn remove(&mut self, key: &str) -> Option<Value> {
393        let i = self.keys.position(key)?;
394        self.edit(|b| {
395            b.keys.remove(i);
396            Some(b.values.remove(i))
397        })
398    }
399
400    /// The entries, in order.
401    pub fn iter(&self) -> map::Iter<'_, Value> {
402        map::Iter::new(&self.keys.names, &self.values)
403    }
404
405    pub fn keys(&self) -> impl DoubleEndedIterator<Item = &String> + ExactSizeIterator + Clone {
406        self.keys.names.iter()
407    }
408
409    pub fn values(&self) -> impl DoubleEndedIterator<Item = &Value> + ExactSizeIterator + Clone {
410        self.values.iter()
411    }
412
413    /// The entry at `index`, in order.
414    pub fn get_index(&self, index: usize) -> Option<(&String, &Value)> {
415        Some((self.keys.names.get(index)?, &self.values[index]))
416    }
417
418    /// [`Object::get`], looking first at the position in `hint`, where the
419    /// key was in the last object looked up: the rows of a table have their
420    /// columns in the same places, so a comparator or a filter finds a
421    /// column without searching the names.
422    pub(crate) fn get_hinted(&self, key: &str, hint: &Cell<usize>) -> Option<&Value> {
423        if let Some((k, v)) = self.get_index(hint.get())
424            && k == key
425        {
426            return Some(v);
427        }
428        let i = self.keys.position(key)?;
429        hint.set(i);
430        Some(&self.values[i])
431    }
432
433    /// Shares `layout`'s keys when they are this object's keys in the same
434    /// order, so the two keep one list of them. Returns whether the keys
435    /// are shared now.
436    pub(crate) fn share_keys(&mut self, layout: &Object) -> bool {
437        if Arc::ptr_eq(&self.keys, &layout.keys) {
438            return true;
439        }
440        if self.keys.names != layout.keys.names {
441            return false;
442        }
443        self.keys = layout.keys.clone();
444        true
445    }
446}
447
448impl PartialEq for Object {
449    fn eq(&self, other: &Self) -> bool {
450        if Arc::ptr_eq(&self.keys, &other.keys) {
451            return Arc::ptr_eq(&self.values, &other.values) || self.values == other.values;
452        }
453        self.len() == other.len() && self.iter().all(|(k, v)| other.get(k) == Some(v))
454    }
455}
456
457impl fmt::Debug for Object {
458    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
459        f.debug_map().entries(self.iter()).finish()
460    }
461}
462
463impl<'a> IntoIterator for &'a Object {
464    type Item = (&'a String, &'a Value);
465    type IntoIter = map::Iter<'a, Value>;
466    fn into_iter(self) -> Self::IntoIter {
467        self.iter()
468    }
469}
470
471impl IntoIterator for Object {
472    type Item = (String, Value);
473    type IntoIter = map::IntoIter<Value>;
474    fn into_iter(self) -> Self::IntoIter {
475        map::IntoIter::new(Arc::unwrap_or_clone(self.keys).names, into_vec(self.values))
476    }
477}
478
479impl<K: Into<String>> FromIterator<(K, Value)> for Object {
480    /// A key that repeats keeps its first place and its last value, as in a
481    /// JS object literal.
482    fn from_iter<I: IntoIterator<Item = (K, Value)>>(iter: I) -> Self {
483        let mut o = ObjectBuilder::default();
484        for (k, v) in iter {
485            o.insert(k.into(), v);
486        }
487        o.build()
488    }
489}
490
491/// The value of `key` if it is an array index (a canonical integer below
492/// 2^32 - 1), which JS orders before other property keys.
493pub(crate) fn array_index(key: &str) -> Option<u32> {
494    let bytes = key.as_bytes();
495    let (&first, rest) = bytes.split_first()?;
496    if !first.is_ascii_digit() || bytes.len() > 10 || (first == b'0' && !rest.is_empty()) {
497        return None;
498    }
499    let mut n = u64::from(first - b'0');
500    for &c in rest {
501        if !c.is_ascii_digit() {
502            return None;
503        }
504        n = n * 10 + u64::from(c - b'0');
505    }
506    (n < 0xFFFF_FFFF).then_some(n as u32)
507}
508
509/// Builds a [`Value`] from JSON-like syntax, for tests and fixtures:
510/// `json!({"a": [1, null, "x"]})`.
511#[macro_export]
512macro_rules! json {
513    (null) => { $crate::json::Value::Null };
514    ([ $($e:tt),* $(,)? ]) => { $crate::json::Value::Array(vec![ $( $crate::json!($e) ),* ]) };
515    ({ $($k:literal : $v:tt),* $(,)? }) => {{
516        #[allow(unused_mut)]
517        let mut o = $crate::json::Object::new();
518        $( o.insert($k, $crate::json!($v)); )*
519        $crate::json::Value::Object(o)
520    }};
521    ($e:expr) => { $crate::json::Value::from($e) };
522}
523
524#[cfg(test)]
525mod tests {
526    use super::*;
527
528    #[test]
529    fn keys_follow_js_property_order() {
530        let mut o = Object::new();
531        for k in ["b", "10", "a", "2", "01", "4294967295", "4294967294", "0"] {
532            o.insert(k, Value::Null);
533        }
534        let keys: Vec<_> = o.keys().map(String::as_str).collect();
535        assert_eq!(
536            keys,
537            ["0", "2", "10", "4294967294", "b", "a", "01", "4294967295"]
538        );
539        o.remove("2");
540        o.insert("3", Value::Null);
541        let keys: Vec<_> = o.keys().map(String::as_str).collect();
542        assert_eq!(
543            keys,
544            ["0", "3", "10", "4294967294", "b", "a", "01", "4294967295"]
545        );
546    }
547
548    #[test]
549    fn parsed_objects_with_the_same_keys_share_them() {
550        let text = r#"[{"a":1,"b":2},{"a":3,"b":4},{"a":5},{"a":6,"b":7,"c":8},
551            {"b":1,"a":2},{"a":1,"a":2,"b":3},{"\u0061":1,"b\"":2},{"1":0,"0":1,"a":2},
552            {"a":9,"b":10}]"#;
553        let Value::Array(objects) = crate::json::parse(text).unwrap() else {
554            panic!("an array");
555        };
556        let objects: Vec<&Object> = objects.iter().map(|v| v.as_object().unwrap()).collect();
557        let entries: Vec<Vec<(&str, f64)>> = objects
558            .iter()
559            .map(|o| {
560                o.iter()
561                    .map(|(k, v)| (k.as_str(), v.as_f64().unwrap()))
562                    .collect()
563            })
564            .collect();
565        assert_eq!(
566            entries,
567            [
568                vec![("a", 1.0), ("b", 2.0)],
569                vec![("a", 3.0), ("b", 4.0)],
570                vec![("a", 5.0)],
571                vec![("a", 6.0), ("b", 7.0), ("c", 8.0)],
572                vec![("b", 1.0), ("a", 2.0)],
573                vec![("a", 2.0), ("b", 3.0)],
574                vec![("a", 1.0), ("b\"", 2.0)],
575                vec![("0", 1.0), ("1", 0.0), ("a", 2.0)],
576                vec![("a", 9.0), ("b", 10.0)],
577            ]
578        );
579        let shared = |i: usize, j: usize| Arc::ptr_eq(&objects[i].keys, &objects[j].keys);
580        assert!(shared(0, 1) && shared(0, 8) && shared(0, 5));
581        assert!(!shared(0, 2) && !shared(0, 3) && !shared(0, 4));
582        // A change to an object whose keys are shared leaves the others'.
583        let mut changed = objects[1].clone();
584        changed.insert("z", Value::Null);
585        assert_eq!(objects[0].keys().collect::<Vec<_>>(), ["a", "b"]);
586        assert_eq!(changed.keys().collect::<Vec<_>>(), ["a", "b", "z"]);
587    }
588
589    #[test]
590    fn a_change_to_a_copy_leaves_the_original() {
591        let mut original = Object::new();
592        original.insert("a", Value::from(1.0));
593        original.insert("b", Value::from(2.0));
594        let changes: [fn(&mut Object); 4] = [
595            |o| _ = o.insert("a", Value::from(9.0)),
596            |o| _ = o.insert("1", Value::Null),
597            |o| _ = o.remove("b"),
598            |o| *o.get_mut("a").unwrap() = Value::Null,
599        ];
600        for change in changes {
601            let mut copy = original.clone();
602            change(&mut copy);
603            assert_ne!(copy, original);
604            let keys: Vec<_> = original.iter().collect();
605            assert_eq!(
606                keys,
607                [
608                    (&"a".to_owned(), &Value::from(1.0)),
609                    (&"b".to_owned(), &Value::from(2.0))
610                ]
611            );
612        }
613    }
614}