Skip to main content

trilean_json_shape/
value.rs

1//! An ordered JSON value. Object keys keep the order of the input, which `serde_json::Value` does not without its
2//! `preserve_order` feature (and that feature adds `indexmap` to the graph), so opaque payloads keep their key order.
3
4use std::collections::HashMap;
5use std::fmt;
6
7use serde::de::{self, Deserialize, Deserializer, MapAccess, SeqAccess, Visitor};
8use serde::ser::{Serialize, SerializeMap, SerializeSeq, Serializer};
9
10/// The largest integer that a JavaScript number, and so a JSON document read by JavaScript, holds exactly.
11pub const MAX_SAFE_INTEGER: f64 = 9_007_199_254_740_991.0;
12
13/// A JSON value.
14///
15/// Numbers are finite `f64`s, each read as the nearest double to its literal, as `JSON.parse` reads it: an integer above 2^53 is rounded when it is read (which
16/// is why no integer type accepts one), `-0` and `0` are one value, and a number is not distinguishable from the
17/// same number written another way (`1e2` and `100`), so a document does not round-trip digit for digit. `Display`
18/// writes a number as `JSON.stringify` does, and so does `Serialize`, for every finite double. `Serialize` is written
19/// for `serde_json`'s serializers: a number that is not a whole number below 2^53 goes through
20/// `serde_json::value::RawValue`, which another serializer shows as that type's marker and not as a number.
21///
22/// An object is a list of pairs in input order, and a duplicate key keeps its first position and its last value, as
23/// `JSON.parse` does. `==` (from `PartialEq`) compares objects in that order and numbers as `f64`s; use
24/// [`Value::json_equal`] for JSON Schema's equality, which ignores key order.
25///
26/// Reading goes through serde, so the parser's own limits apply: `serde_json` refuses nesting deeper than 128 levels
27/// and an unpaired surrogate escape, which `JSON.parse` and so a JSON Schema validator in JavaScript accept. A value
28/// built another way has no depth limit, and `Display`, `json_equal`, `Drop` and validation recurse.
29/// [`Value::get`] is linear in the size of the object.
30#[derive(Clone, Debug, PartialEq)]
31pub enum Value {
32    Null,
33    Bool(bool),
34    Number(f64),
35    String(String),
36    Array(Vec<Value>),
37    Object(Vec<(String, Value)>),
38}
39
40impl Value {
41    /// The value under `key` when this is an object that has it.
42    pub fn get(&self, key: &str) -> Option<&Value> {
43        self.as_object()?
44            .iter()
45            .find(|(name, _)| name == key)
46            .map(|(_, value)| value)
47    }
48
49    pub fn as_str(&self) -> Option<&str> {
50        match self {
51            Value::String(text) => Some(text),
52            _ => None,
53        }
54    }
55
56    pub fn as_bool(&self) -> Option<bool> {
57        match self {
58            Value::Bool(flag) => Some(*flag),
59            _ => None,
60        }
61    }
62
63    pub fn as_f64(&self) -> Option<f64> {
64        match self {
65            Value::Number(number) => Some(*number),
66            _ => None,
67        }
68    }
69
70    pub fn as_array(&self) -> Option<&[Value]> {
71        match self {
72            Value::Array(items) => Some(items),
73            _ => None,
74        }
75    }
76
77    pub fn as_object(&self) -> Option<&[(String, Value)]> {
78        match self {
79            Value::Object(pairs) => Some(pairs),
80            _ => None,
81        }
82    }
83
84    /// The JSON Schema name of this value's type, with every number called `number`.
85    pub fn type_name(&self) -> &'static str {
86        match self {
87            Value::Null => "null",
88            Value::Bool(_) => "boolean",
89            Value::Number(_) => "number",
90            Value::String(_) => "string",
91            Value::Array(_) => "array",
92            Value::Object(_) => "object",
93        }
94    }
95
96    /// Whether two values are equal as JSON Schema defines it: objects regardless of key order, numbers by value.
97    /// Linear in the size of the values, times a logarithm for sorting object keys.
98    pub fn json_equal(&self, other: &Value) -> bool {
99        self.canonical() == other.canonical()
100    }
101
102    /// The text of the value with object keys in sorted order, so two values are equal as JSON Schema defines it
103    /// exactly when their canonical texts are equal.
104    pub fn canonical(&self) -> String {
105        match self {
106            Value::Array(items) => {
107                let parts: Vec<String> = items.iter().map(Value::canonical).collect();
108                format!("[{}]", parts.join(","))
109            }
110            Value::Object(pairs) => {
111                let mut sorted: Vec<&(String, Value)> = pairs.iter().collect();
112                sorted.sort_by(|left, right| left.0.cmp(&right.0));
113                let parts: Vec<String> = sorted
114                    .iter()
115                    .map(|(key, value)| {
116                        format!("{}:{}", Value::String(key.clone()), value.canonical())
117                    })
118                    .collect();
119                format!("{{{}}}", parts.join(","))
120            }
121            other => other.to_string(),
122        }
123    }
124}
125
126/// The shortest decimal digits that read back as `magnitude`, and the decimal exponent of the first digit, as
127/// ECMAScript's Number-to-string chooses them: Rust's shortest digits, except that where two shortest spellings are
128/// exactly as close to the double (it lies midway between them) ECMAScript takes the one whose last digit is even and
129/// Rust the larger.
130fn shortest_digits(magnitude: f64) -> (Vec<u8>, i32) {
131    let text = format!("{magnitude:e}");
132    let (mantissa, exponent) = text.split_once('e').unwrap_or((&text, "0"));
133    let mut digits: Vec<u8> = mantissa.bytes().filter(u8::is_ascii_digit).collect();
134    let mut exponent: i32 = exponent.parse().unwrap_or(0);
135    let length = digits.len();
136    // The exact expansion, to the digit after the shortest ones and well past it: a tie is a 5 there and zeros after.
137    let probe = format!("{magnitude:.*e}", length + 25);
138    let exact: Vec<u8> = probe
139        .split_once('e')
140        .map_or(&probe[..], |(mantissa, _)| mantissa)
141        .bytes()
142        .filter(u8::is_ascii_digit)
143        .collect();
144    let is_tie = |exact: &[u8]| {
145        exact[length] == b'5' && exact[length + 1..].iter().all(|digit| *digit == b'0')
146    };
147    if exact.len() > length + 1 && is_tie(&exact) {
148        // A double has finitely many digits: confirm the zeros run to the end of the exact expansion.
149        let full = format!("{magnitude:.800e}");
150        let full: Vec<u8> = full
151            .split_once('e')
152            .map_or(&full[..], |(mantissa, _)| mantissa)
153            .bytes()
154            .filter(u8::is_ascii_digit)
155            .collect();
156        if is_tie(&full) {
157            let mut lower = full[..length].to_vec();
158            let mut upper = lower.clone();
159            let mut carry = true;
160            for digit in upper.iter_mut().rev() {
161                if *digit == b'9' {
162                    *digit = b'0';
163                } else {
164                    *digit += 1;
165                    carry = false;
166                    break;
167                }
168            }
169            let mut upper_exponent = exponent;
170            if carry {
171                upper.insert(0, b'1');
172                upper.pop();
173                upper_exponent += 1;
174            }
175            let reads_back = |candidate: &[u8], exponent: i32| {
176                let text = format!(
177                    "{}.{}e{exponent}",
178                    char::from(candidate[0]),
179                    String::from_utf8_lossy(&candidate[1..])
180                );
181                text.parse::<f64>() == Ok(magnitude)
182            };
183            let even_lower = lower
184                .last()
185                .is_some_and(|digit| (digit - b'0').is_multiple_of(2));
186            let (chosen, chosen_exponent) = if even_lower {
187                (&mut lower, exponent)
188            } else {
189                (&mut upper, upper_exponent)
190            };
191            // Both spellings are equally close; the even one is the answer when it reads back as the same double,
192            // which it does unless the double sits at the edge between two spacings of the doubles.
193            if reads_back(chosen, chosen_exponent) {
194                digits = std::mem::take(chosen);
195                exponent = chosen_exponent;
196            }
197        }
198    }
199    while digits.len() > 1 && digits.last() == Some(&b'0') {
200        digits.pop();
201    }
202    (digits, exponent)
203}
204
205/// A number as `JSON.stringify` writes it (ECMAScript's Number-to-string): the shortest digits that read back as the
206/// double, written as digits and zeros for magnitudes from 1e-6 up to below 1e21 and with an exponent outside that.
207/// Both zeros are `0`, and NaN and the infinities are the texts `NaN`, `Infinity` and `-Infinity`.
208pub fn number_to_string(number: f64) -> String {
209    if number.is_nan() {
210        return "NaN".to_owned();
211    }
212    if number.is_infinite() {
213        return if number < 0.0 {
214            "-Infinity"
215        } else {
216            "Infinity"
217        }
218        .to_owned();
219    }
220    if number == 0.0 {
221        return "0".to_owned();
222    }
223    let (digits, exponent) = shortest_digits(number.abs());
224    let digits = String::from_utf8_lossy(&digits).into_owned();
225    let length = i32::try_from(digits.len()).unwrap_or(i32::MAX);
226    // The decimal point sits after `point` digits: the value is 0.DIGITS times 10 to the `point`.
227    let point = exponent + 1;
228    let sign = if number < 0.0 { "-" } else { "" };
229    let body = if length <= point && point <= 21 {
230        format!(
231            "{digits}{}",
232            "0".repeat(usize::try_from(point - length).unwrap_or(0))
233        )
234    } else if 0 < point && point <= 21 {
235        let split = usize::try_from(point).unwrap_or(0);
236        format!("{}.{}", &digits[..split], &digits[split..])
237    } else if -6 < point && point <= 0 {
238        format!(
239            "0.{}{digits}",
240            "0".repeat(usize::try_from(-point).unwrap_or(0))
241        )
242    } else {
243        let sign_of_exponent = if point - 1 < 0 { "-" } else { "+" };
244        let power = (point - 1).abs();
245        if digits.len() == 1 {
246            format!("{digits}e{sign_of_exponent}{power}")
247        } else {
248            format!(
249                "{}.{}e{sign_of_exponent}{power}",
250                &digits[..1],
251                &digits[1..]
252            )
253        }
254    };
255    format!("{sign}{body}")
256}
257
258impl fmt::Display for Value {
259    /// Compact JSON text, with numbers written as `JSON.stringify` writes them.
260    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
261        match self {
262            Value::Null => formatter.write_str("null"),
263            Value::Bool(flag) => write!(formatter, "{flag}"),
264            Value::Number(number) => formatter.write_str(&number_to_string(*number)),
265            Value::String(text) => {
266                formatter.write_str(&serde_json::to_string(text).map_err(|_| fmt::Error)?)
267            }
268            Value::Array(items) => {
269                formatter.write_str("[")?;
270                for (position, item) in items.iter().enumerate() {
271                    if position > 0 {
272                        formatter.write_str(",")?;
273                    }
274                    write!(formatter, "{item}")?;
275                }
276                formatter.write_str("]")
277            }
278            Value::Object(pairs) => {
279                formatter.write_str("{")?;
280                for (position, (key, value)) in pairs.iter().enumerate() {
281                    if position > 0 {
282                        formatter.write_str(",")?;
283                    }
284                    formatter.write_str(&serde_json::to_string(key).map_err(|_| fmt::Error)?)?;
285                    write!(formatter, ":{value}")?;
286                }
287                formatter.write_str("}")
288            }
289        }
290    }
291}
292
293struct ValueVisitor;
294
295impl<'de> Visitor<'de> for ValueVisitor {
296    type Value = Value;
297
298    fn expecting(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
299        formatter.write_str("any JSON value")
300    }
301
302    fn visit_unit<E: de::Error>(self) -> Result<Value, E> {
303        Ok(Value::Null)
304    }
305
306    fn visit_none<E: de::Error>(self) -> Result<Value, E> {
307        Ok(Value::Null)
308    }
309
310    fn visit_bool<E: de::Error>(self, flag: bool) -> Result<Value, E> {
311        Ok(Value::Bool(flag))
312    }
313
314    fn visit_i64<E: de::Error>(self, number: i64) -> Result<Value, E> {
315        Ok(Value::Number(number as f64))
316    }
317
318    fn visit_u64<E: de::Error>(self, number: u64) -> Result<Value, E> {
319        Ok(Value::Number(number as f64))
320    }
321
322    fn visit_f64<E: de::Error>(self, number: f64) -> Result<Value, E> {
323        if number.is_finite() {
324            Ok(Value::Number(number))
325        } else {
326            Err(E::custom("a JSON number must be finite"))
327        }
328    }
329
330    fn visit_str<E: de::Error>(self, text: &str) -> Result<Value, E> {
331        Ok(Value::String(text.to_owned()))
332    }
333
334    fn visit_string<E: de::Error>(self, text: String) -> Result<Value, E> {
335        Ok(Value::String(text))
336    }
337
338    fn visit_seq<A: SeqAccess<'de>>(self, mut sequence: A) -> Result<Value, A::Error> {
339        let mut items = Vec::new();
340        while let Some(item) = sequence.next_element::<Value>()? {
341            items.push(item);
342        }
343        Ok(Value::Array(items))
344    }
345
346    fn visit_map<A: MapAccess<'de>>(self, mut map: A) -> Result<Value, A::Error> {
347        let mut pairs: Vec<(String, Value)> = Vec::new();
348        let mut positions: HashMap<String, usize> = HashMap::new();
349        while let Some((key, value)) = map.next_entry::<String, Value>()? {
350            match positions.get(&key) {
351                Some(position) => pairs[*position].1 = value,
352                None => {
353                    positions.insert(key.clone(), pairs.len());
354                    pairs.push((key, value));
355                }
356            }
357        }
358        Ok(Value::Object(pairs))
359    }
360}
361
362impl<'de> Deserialize<'de> for Value {
363    fn deserialize<D: Deserializer<'de>>(deserializer: D) -> Result<Value, D::Error> {
364        deserializer.deserialize_any(ValueVisitor)
365    }
366}
367
368impl Serialize for Value {
369    fn serialize<S: Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
370        match self {
371            Value::Null => serializer.serialize_unit(),
372            Value::Bool(flag) => serializer.serialize_bool(*flag),
373            Value::Number(number) => {
374                // A whole number below 2^53 is its own digits. Every other number is written as the text
375                // `JSON.stringify` writes, which `serde_json`'s float writer does not give for every double (it
376                // writes `9e+18` and `1e-6` where `JSON.stringify` writes `9000000000000000000` and `0.000001`).
377                if number.fract() == 0.0 && number.abs() < MAX_SAFE_INTEGER {
378                    serializer.serialize_i64(*number as i64)
379                } else {
380                    serde_json::value::RawValue::from_string(number_to_string(*number))
381                        .map_err(serde::ser::Error::custom)?
382                        .serialize(serializer)
383                }
384            }
385            Value::String(text) => serializer.serialize_str(text),
386            Value::Array(items) => {
387                let mut sequence = serializer.serialize_seq(Some(items.len()))?;
388                for item in items {
389                    sequence.serialize_element(item)?;
390                }
391                sequence.end()
392            }
393            Value::Object(pairs) => {
394                let mut map = serializer.serialize_map(Some(pairs.len()))?;
395                for (key, value) in pairs {
396                    map.serialize_entry(key, value)?;
397                }
398                map.end()
399            }
400        }
401    }
402}