datumesh_core/
json.rs

1//! Strict JSON (SPEC 6.1, I-JSON) and the RFC 8785 JSON Canonicalization Scheme (SPEC 6.2).
2//!
3//! [`parse`] accepts exactly the texts SPEC 6.1 accepts and reports failures in the order it
4//! defines. [`Value::to_jcs`] writes the RFC 8785 serialisation, including ECMAScript number
5//! formatting, so it is a complete JCS even though Datumesh objects never contain JSON numbers.
6
7use crate::error::{err, ErrorCode, Result};
8use core::cmp::Ordering;
9
10/// The deepest nesting of arrays and objects accepted (SPEC 6.1).
11pub(crate) const MAX_DEPTH: usize = 64;
12
13mod number {
14    /// A JSON number: the text it was written as, and its IEEE 754 double value. Only
15    /// [`parse`](super::parse) makes one, so the text is always JSON number syntax and the
16    /// value finite. The type cannot be named outside the crate; read a number with
17    /// [`Value::as_number_text`](super::Value::as_number_text).
18    #[derive(Clone, Debug, PartialEq)]
19    pub struct Number {
20        pub(super) text: String,
21        pub(super) value: f64,
22    }
23}
24
25use number::Number;
26
27/// A parsed JSON value. Object members keep their text order; names are unique.
28#[derive(Clone, Debug, PartialEq)]
29pub enum Value {
30    /// `null`
31    Null,
32    /// `true` or `false`
33    Bool(bool),
34    /// A number, as parsed. Read it with [`Value::as_number_text`]; a number can only come
35    /// from [`parse`].
36    Number(Number),
37    /// A string.
38    String(String),
39    /// An array.
40    Array(Vec<Value>),
41    /// An object, members in text order.
42    Object(Vec<(String, Value)>),
43}
44
45impl Value {
46    /// The member named `name` of an object.
47    pub fn get(&self, name: &str) -> Option<&Value> {
48        match self {
49            Value::Object(m) => m.iter().find(|(k, _)| k == name).map(|(_, v)| v),
50            _ => None,
51        }
52    }
53
54    /// The string, if this is one.
55    pub fn as_str(&self) -> Option<&str> {
56        match self {
57            Value::String(s) => Some(s),
58            _ => None,
59        }
60    }
61
62    /// The members, if this is an object.
63    pub fn as_object(&self) -> Option<&[(String, Value)]> {
64        match self {
65            Value::Object(m) => Some(m),
66            _ => None,
67        }
68    }
69
70    /// The number exactly as written in the parsed text (e.g. `1.50`, `1E3`), if this is a
71    /// number. [`Value::to_jcs`] writes its double value in ECMAScript form instead.
72    pub fn as_number_text(&self) -> Option<&str> {
73        match self {
74            Value::Number(n) => Some(&n.text),
75            _ => None,
76        }
77    }
78
79    /// The JSON type name, for messages.
80    pub(crate) fn kind(&self) -> &'static str {
81        match self {
82            Value::Null => "null",
83            Value::Bool(_) => "a boolean",
84            Value::Number(_) => "a number",
85            Value::String(_) => "a string",
86            Value::Array(_) => "an array",
87            Value::Object(_) => "an object",
88        }
89    }
90
91    /// The RFC 8785 canonical serialisation as UTF-8 bytes.
92    pub fn to_jcs(&self) -> Vec<u8> {
93        let mut out = String::new();
94        write_jcs(self, &mut out);
95        out.into_bytes()
96    }
97}
98
99/// An object's members sorted as JCS sorts them (UTF-16 code units of the names).
100pub(crate) fn jcs_sorted(members: &[(String, Value)]) -> Vec<&(String, Value)> {
101    let mut v: Vec<&(String, Value)> = members.iter().collect();
102    v.sort_by(|a, b| utf16_cmp(&a.0, &b.0));
103    v
104}
105
106/// Compares two strings by their UTF-16 code units (RFC 8785 3.2.3).
107pub(crate) fn utf16_cmp(a: &str, b: &str) -> Ordering {
108    a.encode_utf16().cmp(b.encode_utf16())
109}
110
111/// Parses `bytes` as strict JSON (SPEC 6.1).
112///
113/// Failures, in the order SPEC 6.1 reports them: a byte order mark, invalid UTF-8, nesting
114/// deeper than 64 levels, then the first in text order of a syntax error, a number that
115/// overflows a double, or a duplicate member (detected when its object closes), and last a
116/// lone surrogate. All are `E_PARSE_JSON` except duplicates (`E_PARSE_DUPLICATE_KEY`).
117pub fn parse(bytes: &[u8]) -> Result<Value> {
118    if bytes.starts_with(&[0xEF, 0xBB, 0xBF]) {
119        return err(ErrorCode::ParseJson, "$", "byte order mark");
120    }
121    let text = match core::str::from_utf8(bytes) {
122        Ok(t) => t,
123        Err(e) => return err(ErrorCode::ParseJson, "$", format!("invalid UTF-8 at byte {}", e.valid_up_to())),
124    };
125    check_depth(text.as_bytes())?;
126    let mut p = Parser { b: text.as_bytes(), i: 0, lone_surrogate: false };
127    p.ws();
128    let v = p.value()?;
129    p.ws();
130    if p.i != p.b.len() {
131        return p.syntax("extra data after the value");
132    }
133    if p.lone_surrogate {
134        return err(ErrorCode::ParseJson, "$", "lone surrogate");
135    }
136    Ok(v)
137}
138
139fn check_depth(b: &[u8]) -> Result<()> {
140    let mut depth: usize = 0;
141    let mut in_str = false;
142    let mut esc = false;
143    for &c in b {
144        if in_str {
145            if esc {
146                esc = false;
147            } else if c == b'\\' {
148                esc = true;
149            } else if c == b'"' {
150                in_str = false;
151            }
152            continue;
153        }
154        match c {
155            b'"' => in_str = true,
156            b'[' | b'{' => {
157                depth += 1;
158                if depth > MAX_DEPTH {
159                    return err(ErrorCode::ParseJson, "$", format!("nested deeper than {MAX_DEPTH} levels"));
160                }
161            }
162            b']' | b'}' => depth = depth.saturating_sub(1),
163            _ => {}
164        }
165    }
166    Ok(())
167}
168
169struct Parser<'a> {
170    b: &'a [u8],
171    i: usize,
172    lone_surrogate: bool,
173}
174
175impl Parser<'_> {
176    fn syntax<T>(&self, what: &str) -> Result<T> {
177        err(ErrorCode::ParseJson, "$", format!("{what} at byte {}", self.i))
178    }
179
180    fn peek(&self) -> Option<u8> {
181        self.b.get(self.i).copied()
182    }
183
184    fn ws(&mut self) {
185        while let Some(b' ' | b'\t' | b'\n' | b'\r') = self.peek() {
186            self.i += 1;
187        }
188    }
189
190    fn lit(&mut self, word: &[u8], v: Value) -> Result<Value> {
191        if self.b.get(self.i..self.i + word.len()) == Some(word) {
192            self.i += word.len();
193            Ok(v)
194        } else {
195            self.syntax("invalid literal")
196        }
197    }
198
199    // Depth is bounded by `check_depth`, so recursion is at most MAX_DEPTH deep.
200    fn value(&mut self) -> Result<Value> {
201        match self.peek() {
202            Some(b'{') => self.object(),
203            Some(b'[') => self.array(),
204            Some(b'"') => Ok(Value::String(self.string()?.0)),
205            Some(b't') => self.lit(b"true", Value::Bool(true)),
206            Some(b'f') => self.lit(b"false", Value::Bool(false)),
207            Some(b'n') => self.lit(b"null", Value::Null),
208            Some(b'-' | b'0'..=b'9') => self.number(),
209            Some(_) => self.syntax("unexpected character"),
210            None => self.syntax("unexpected end of text"),
211        }
212    }
213
214    fn array(&mut self) -> Result<Value> {
215        self.i += 1;
216        let mut items = Vec::new();
217        self.ws();
218        if self.peek() == Some(b']') {
219            self.i += 1;
220            return Ok(Value::Array(items));
221        }
222        loop {
223            self.ws();
224            items.push(self.value()?);
225            self.ws();
226            match self.peek() {
227                Some(b',') => self.i += 1,
228                Some(b']') => {
229                    self.i += 1;
230                    return Ok(Value::Array(items));
231                }
232                _ => return self.syntax("expected ',' or ']'"),
233            }
234        }
235    }
236
237    fn object(&mut self) -> Result<Value> {
238        self.i += 1;
239        let mut members: Vec<(String, Value)> = Vec::new();
240        let mut units: Vec<Vec<u16>> = Vec::new();
241        self.ws();
242        if self.peek() == Some(b'}') {
243            self.i += 1;
244            return Ok(Value::Object(members));
245        }
246        loop {
247            self.ws();
248            if self.peek() != Some(b'"') {
249                return self.syntax("expected a member name");
250            }
251            let (name, name_units) = self.string()?;
252            self.ws();
253            if self.peek() != Some(b':') {
254                return self.syntax("expected ':'");
255            }
256            self.i += 1;
257            self.ws();
258            let v = self.value()?;
259            members.push((name, v));
260            units.push(name_units);
261            self.ws();
262            match self.peek() {
263                Some(b',') => self.i += 1,
264                Some(b'}') => {
265                    self.i += 1;
266                    break;
267                }
268                _ => return self.syntax("expected ',' or '}'"),
269            }
270        }
271        // Duplicates are detected when the object closes (SPEC 6.1), comparing unescaped names.
272        let mut order: Vec<usize> = (0..units.len()).collect();
273        order.sort_by(|&a, &b| units[a].cmp(&units[b]).then(a.cmp(&b)));
274        let mut dup: Option<usize> = None;
275        for w in order.windows(2) {
276            if units[w[0]] == units[w[1]] {
277                let second = w[0].max(w[1]);
278                dup = Some(dup.map_or(second, |d| d.min(second)));
279            }
280        }
281        if let Some(d) = dup {
282            let name = members.get(d).map(|m| m.0.as_str()).unwrap_or("");
283            return err(ErrorCode::ParseDuplicateKey, "$", format!("duplicate member '{name}'"));
284        }
285        Ok(Value::Object(members))
286    }
287
288    fn hex4(&mut self) -> Result<u16> {
289        let mut v: u16 = 0;
290        for _ in 0..4 {
291            let d = match self.peek() {
292                Some(c @ b'0'..=b'9') => c - b'0',
293                Some(c @ b'a'..=b'f') => c - b'a' + 10,
294                Some(c @ b'A'..=b'F') => c - b'A' + 10,
295                _ => return self.syntax("invalid \\u escape"),
296            };
297            v = (v << 4) | u16::from(d);
298            self.i += 1;
299        }
300        Ok(v)
301    }
302
303    /// Returns the string and its UTF-16 code units (lone surrogates kept in the units,
304    /// replaced by U+FFFD in the string and remembered as an error for later).
305    fn string(&mut self) -> Result<(String, Vec<u16>)> {
306        self.i += 1;
307        let mut units: Vec<u16> = Vec::new();
308        loop {
309            let c = match self.peek() {
310                None => return self.syntax("unterminated string"),
311                Some(c) => c,
312            };
313            match c {
314                b'"' => {
315                    self.i += 1;
316                    break;
317                }
318                b'\\' => {
319                    self.i += 1;
320                    let e = match self.peek() {
321                        Some(e) => e,
322                        None => return self.syntax("unterminated string"),
323                    };
324                    self.i += 1;
325                    let u = match e {
326                        b'"' => 0x22,
327                        b'\\' => 0x5C,
328                        b'/' => 0x2F,
329                        b'b' => 0x08,
330                        b'f' => 0x0C,
331                        b'n' => 0x0A,
332                        b'r' => 0x0D,
333                        b't' => 0x09,
334                        b'u' => self.hex4()?,
335                        _ => {
336                            self.i -= 1;
337                            return self.syntax("invalid escape");
338                        }
339                    };
340                    units.push(u);
341                }
342                0x00..=0x1F => return self.syntax("control character in string"),
343                _ => {
344                    // Copy one UTF-8 encoded character (input is valid UTF-8).
345                    let len = match c {
346                        0x00..=0x7F => 1,
347                        0xC0..=0xDF => 2,
348                        0xE0..=0xEF => 3,
349                        _ => 4,
350                    };
351                    let chunk = self.b.get(self.i..self.i + len).unwrap_or(&[]);
352                    match core::str::from_utf8(chunk).ok().and_then(|s| s.chars().next()) {
353                        Some(ch) => {
354                            let mut buf = [0u16; 2];
355                            units.extend_from_slice(ch.encode_utf16(&mut buf));
356                        }
357                        None => return self.syntax("invalid UTF-8"),
358                    }
359                    self.i += len;
360                }
361            }
362        }
363        let mut s = String::with_capacity(units.len());
364        for r in char::decode_utf16(units.iter().copied()) {
365            match r {
366                Ok(ch) => s.push(ch),
367                Err(_) => {
368                    self.lone_surrogate = true;
369                    s.push('\u{FFFD}');
370                }
371            }
372        }
373        Ok((s, units))
374    }
375
376    fn number(&mut self) -> Result<Value> {
377        let start = self.i;
378        if self.peek() == Some(b'-') {
379            self.i += 1;
380        }
381        match self.peek() {
382            Some(b'0') => self.i += 1,
383            Some(b'1'..=b'9') => {
384                while let Some(b'0'..=b'9') = self.peek() {
385                    self.i += 1;
386                }
387            }
388            _ => return self.syntax("invalid number"),
389        }
390        if self.peek() == Some(b'.') {
391            self.i += 1;
392            if !matches!(self.peek(), Some(b'0'..=b'9')) {
393                return self.syntax("invalid number");
394            }
395            while let Some(b'0'..=b'9') = self.peek() {
396                self.i += 1;
397            }
398        }
399        if let Some(b'e' | b'E') = self.peek() {
400            self.i += 1;
401            if let Some(b'+' | b'-') = self.peek() {
402                self.i += 1;
403            }
404            if !matches!(self.peek(), Some(b'0'..=b'9')) {
405                return self.syntax("invalid number");
406            }
407            while let Some(b'0'..=b'9') = self.peek() {
408                self.i += 1;
409            }
410        }
411        let text = core::str::from_utf8(self.b.get(start..self.i).unwrap_or(&[])).unwrap_or("");
412        let value: f64 = match text.parse() {
413            Ok(v) => v,
414            Err(_) => return self.syntax("invalid number"),
415        };
416        if !value.is_finite() {
417            return err(ErrorCode::ParseJson, "$", format!("number out of IEEE 754 range: {text}"));
418        }
419        Ok(Value::Number(Number { text: text.to_string(), value }))
420    }
421}
422
423enum Piece<'a> {
424    Value(&'a Value),
425    Text(&'static str),
426    Key(&'a str),
427}
428
429// Iterative, so that a deeply nested value built in memory cannot exhaust the stack.
430fn write_jcs(v: &Value, out: &mut String) {
431    let mut stack = vec![Piece::Value(v)];
432    while let Some(p) = stack.pop() {
433        match p {
434            Piece::Text(t) => out.push_str(t),
435            Piece::Key(k) => {
436                write_string(k, out);
437                out.push(':');
438            }
439            Piece::Value(Value::Null) => out.push_str("null"),
440            Piece::Value(Value::Bool(true)) => out.push_str("true"),
441            Piece::Value(Value::Bool(false)) => out.push_str("false"),
442            Piece::Value(Value::Number(n)) => out.push_str(&format_number(n.value)),
443            Piece::Value(Value::String(s)) => write_string(s, out),
444            Piece::Value(Value::Array(items)) => {
445                out.push('[');
446                stack.push(Piece::Text("]"));
447                for (i, item) in items.iter().enumerate().rev() {
448                    stack.push(Piece::Value(item));
449                    if i > 0 {
450                        stack.push(Piece::Text(","));
451                    }
452                }
453            }
454            Piece::Value(Value::Object(members)) => {
455                out.push('{');
456                stack.push(Piece::Text("}"));
457                for (i, (k, val)) in jcs_sorted(members).into_iter().enumerate().rev() {
458                    stack.push(Piece::Value(val));
459                    stack.push(Piece::Key(k));
460                    if i > 0 {
461                        stack.push(Piece::Text(","));
462                    }
463                }
464            }
465        }
466    }
467}
468
469/// Checks that an already-parsed value nests at most [`MAX_DEPTH`] arrays and objects
470/// (SPEC 6.1 applies the parser's limit to values accepted in parsed form). `E_PARSE_JSON`.
471pub(crate) fn check_value_depth(v: &Value) -> Result<()> {
472    let mut stack: Vec<(&Value, usize)> = vec![(v, 0)];
473    while let Some((v, d)) = stack.pop() {
474        let children: Box<dyn Iterator<Item = &Value>> = match v {
475            Value::Array(items) => Box::new(items.iter()),
476            Value::Object(members) => Box::new(members.iter().map(|(_, x)| x)),
477            _ => continue,
478        };
479        if d + 1 > MAX_DEPTH {
480            return err(ErrorCode::ParseJson, "$", format!("nested deeper than {MAX_DEPTH} levels"));
481        }
482        stack.extend(children.map(|c| (c, d + 1)));
483    }
484    Ok(())
485}
486
487/// Writes a JSON string as RFC 8785 does: only `"`, `\` and C0 controls are escaped.
488pub(crate) fn write_string(s: &str, out: &mut String) {
489    out.push('"');
490    for c in s.chars() {
491        match c {
492            '"' => out.push_str("\\\""),
493            '\\' => out.push_str("\\\\"),
494            '\u{08}' => out.push_str("\\b"),
495            '\u{09}' => out.push_str("\\t"),
496            '\u{0A}' => out.push_str("\\n"),
497            '\u{0C}' => out.push_str("\\f"),
498            '\u{0D}' => out.push_str("\\r"),
499            c if (c as u32) < 0x20 => {
500                const HEX: &[u8; 16] = b"0123456789abcdef";
501                let n = c as usize;
502                out.push_str("\\u00");
503                out.push(char::from(HEX[(n >> 4) & 0xF]));
504                out.push(char::from(HEX[n & 0xF]));
505            }
506            c => out.push(c),
507        }
508    }
509    out.push('"');
510}
511
512fn split_sci(sci: &str) -> (String, i64) {
513    let (mantissa, exp) = sci.split_once('e').unwrap_or((sci, "0"));
514    (mantissa.chars().filter(char::is_ascii_digit).collect(), exp.parse().unwrap_or(0))
515}
516
517/// The ECMAScript digits of a positive finite double: the fewest digits that round-trip
518/// and, among those, the closest to the value, ties to even (ECMA-262 Number::toString).
519///
520/// `{:e}` gives the fewest digits but breaks ties upwards; `{:.N e}` rounds the exact value
521/// half to even. The latter is used whenever it round-trips at the same length.
522fn shortest_digits(v: f64) -> (String, i64) {
523    let shortest = split_sci(&format!("{v:e}"));
524    let k = shortest.0.len();
525    let exact_text = format!("{:.*e}", k.saturating_sub(1), v);
526    if exact_text.parse::<f64>() == Ok(v) {
527        let exact = split_sci(&exact_text);
528        if exact.0.len() == k {
529            return exact;
530        }
531    }
532    shortest
533}
534
535/// Formats a finite double as ECMAScript `Number.prototype.toString` does (RFC 8785 3.2.2.3).
536///
537/// Rust's `{:e}` formatting yields the shortest digit string that round-trips; this lays
538/// those digits out by the ECMAScript rules.
539pub(crate) fn format_number(v: f64) -> String {
540    if v == 0.0 || !v.is_finite() {
541        // -0 serialises as 0; non-finite values never reach here from `parse`.
542        return "0".to_string();
543    }
544    let mut out = String::new();
545    if v < 0.0 {
546        out.push('-');
547    }
548    let (digits, exp) = shortest_digits(v.abs());
549    let k = digits.len() as i64;
550    let n = exp + 1;
551    if k <= n && n <= 21 {
552        out.push_str(&digits);
553        for _ in 0..(n - k) {
554            out.push('0');
555        }
556    } else if 0 < n && n <= 21 {
557        let (a, b) = digits.split_at(n as usize);
558        out.push_str(a);
559        out.push('.');
560        out.push_str(b);
561    } else if -6 < n && n <= 0 {
562        out.push_str("0.");
563        for _ in 0..(-n) {
564            out.push('0');
565        }
566        out.push_str(&digits);
567    } else {
568        let (a, b) = digits.split_at(1);
569        out.push_str(a);
570        if !b.is_empty() {
571            out.push('.');
572            out.push_str(b);
573        }
574        out.push('e');
575        let e = n - 1;
576        out.push(if e < 0 { '-' } else { '+' });
577        out.push_str(&e.abs().to_string());
578    }
579    out
580}
581
582#[cfg(test)]
583mod tests {
584    use super::*;
585
586    /// RFC 8785 Appendix B, directly on the formatter (tests/rfc8785.rs covers it through
587    /// `parse` and `to_jcs`).
588    #[test]
589    fn format_number_appendix_b() {
590        let cases: [(u64, &str); 24] = [
591            (0x0000000000000000, "0"),
592            (0x8000000000000000, "0"),
593            (0x0000000000000001, "5e-324"),
594            (0x8000000000000001, "-5e-324"),
595            (0x7fefffffffffffff, "1.7976931348623157e+308"),
596            (0xffefffffffffffff, "-1.7976931348623157e+308"),
597            (0x4340000000000000, "9007199254740992"),
598            (0xc340000000000000, "-9007199254740992"),
599            (0x4430000000000000, "295147905179352830000"),
600            (0x44b52d02c7e14af5, "9.999999999999997e+22"),
601            (0x44b52d02c7e14af6, "1e+23"),
602            (0x44b52d02c7e14af7, "1.0000000000000001e+23"),
603            (0x444b1ae4d6e2ef4e, "999999999999999700000"),
604            (0x444b1ae4d6e2ef4f, "999999999999999900000"),
605            (0x444b1ae4d6e2ef50, "1e+21"),
606            (0x3eb0c6f7a0b5ed8c, "9.999999999999997e-7"),
607            (0x3eb0c6f7a0b5ed8d, "0.000001"),
608            (0x41b3de4355555553, "333333333.3333332"),
609            (0x41b3de4355555554, "333333333.33333325"),
610            (0x41b3de4355555555, "333333333.3333333"),
611            (0x41b3de4355555556, "333333333.3333334"),
612            (0x41b3de4355555557, "333333333.33333343"),
613            (0xbecbf647612f3696, "-0.0000033333333333333333"),
614            (0x43143ff3c1cb0959, "1424953923781206.2"),
615        ];
616        for (bits, want) in cases {
617            assert_eq!(format_number(f64::from_bits(bits)), want, "{bits:016x}");
618        }
619    }
620
621    #[test]
622    fn value_depth_limit() {
623        let mut v = Value::Null;
624        for _ in 0..MAX_DEPTH {
625            v = Value::Array(vec![v]);
626        }
627        assert!(check_value_depth(&v).is_ok());
628        let v = Value::Array(vec![v]);
629        assert_eq!(check_value_depth(&v).unwrap_err().code(), ErrorCode::ParseJson);
630    }
631}
datumesh_core/json.rs

datumesh_core/
json.rs
