1//! RFC 8785 (JCS) canonical JSON that never loses a digit.
2//!
3//! Numbers keep their lexeme through parsing. A number is written the
4//! JCS way (ECMAScript `Number.prototype.toString`, via ryu-js) only when
5//! that text has exactly the value of the original; otherwise, as for a
6//! `bigint` beyond 2^53 or a `numeric(38,20)`, it is written as a JSON
7//! string holding every digit of its value, in the same ECMAScript
8//! layout, so no digit is lost and equal values give equal bytes
9//! (contract *Cache*).
10//! Generic canonicalizers go through f64 and silently round (review #2).
11
12use std::fmt::Write;
13
14/// Nesting deeper than this is refused rather than risking the stack.
15const MAX_DEPTH: usize = 256;
16
17enum Value<'a> {
18    Literal(&'a str),
19    Number(&'a str),
20    String(String),
21    Array(Vec<Value<'a>>),
22    Object(Vec<(String, Value<'a>)>),
23}
24
25pub fn canonicalize(json: &str) -> Result<String, String> {
26    let mut parser = Parser { input: json, pos: 0 };
27    let value = parser.value(0)?;
28    parser.whitespace();
29    if parser.pos != json.len() {
30        return Err(format!("trailing characters at byte {}", parser.pos));
31    }
32    let mut out = String::with_capacity(json.len());
33    write(&value, &mut out)?;
34    Ok(out)
35}
36
37struct Parser<'a> {
38    input: &'a str,
39    pos: usize,
40}
41
42impl<'a> Parser<'a> {
43    fn peek(&self) -> Option<u8> {
44        self.input.as_bytes().get(self.pos).copied()
45    }
46
47    fn whitespace(&mut self) {
48        while matches!(self.peek(), Some(b' ' | b'\t' | b'\n' | b'\r')) {
49            self.pos += 1;
50        }
51    }
52
53    fn expect(&mut self, byte: u8) -> Result<(), String> {
54        if self.peek() == Some(byte) {
55            self.pos += 1;
56            Ok(())
57        } else {
58            Err(format!("expected {:?} at byte {}", byte as char, self.pos))
59        }
60    }
61
62    fn value(&mut self, depth: usize) -> Result<Value<'a>, String> {
63        if depth > MAX_DEPTH {
64            return Err(format!("nested deeper than {MAX_DEPTH}"));
65        }
66        self.whitespace();
67        match self.peek() {
68            Some(b'{') => self.object(depth),
69            Some(b'[') => self.array(depth),
70            Some(b'"') => self.string().map(Value::String),
71            Some(b'-' | b'0'..=b'9') => self.number(),
72            _ => {
73                for literal in ["null", "true", "false"] {
74                    if self.input[self.pos..].starts_with(literal) {
75                        self.pos += literal.len();
76                        return Ok(Value::Literal(literal));
77                    }
78                }
79                Err(format!("unexpected input at byte {}", self.pos))
80            }
81        }
82    }
83
84    fn object(&mut self, depth: usize) -> Result<Value<'a>, String> {
85        self.expect(b'{')?;
86        let mut members = Vec::new();
87        self.whitespace();
88        if self.peek() == Some(b'}') {
89            self.pos += 1;
90            return Ok(Value::Object(members));
91        }
92        loop {
93            self.whitespace();
94            let key = self.string()?;
95            self.whitespace();
96            self.expect(b':')?;
97            members.push((key, self.value(depth + 1)?));
98            self.whitespace();
99            match self.peek() {
100                Some(b',') => self.pos += 1,
101                Some(b'}') => {
102                    self.pos += 1;
103                    return Ok(Value::Object(members));
104                }
105                _ => return Err(format!("expected ',' or '}}' at byte {}", self.pos)),
106            }
107        }
108    }
109
110    fn array(&mut self, depth: usize) -> Result<Value<'a>, String> {
111        self.expect(b'[')?;
112        let mut items = Vec::new();
113        self.whitespace();
114        if self.peek() == Some(b']') {
115            self.pos += 1;
116            return Ok(Value::Array(items));
117        }
118        loop {
119            items.push(self.value(depth + 1)?);
120            self.whitespace();
121            match self.peek() {
122                Some(b',') => self.pos += 1,
123                Some(b']') => {
124                    self.pos += 1;
125                    return Ok(Value::Array(items));
126                }
127                _ => return Err(format!("expected ',' or ']' at byte {}", self.pos)),
128            }
129        }
130    }
131
132    /// Finds the string's end, then lets serde_json decode its escapes.
133    fn string(&mut self) -> Result<String, String> {
134        let start = self.pos;
135        self.expect(b'"')?;
136        loop {
137            match self.peek() {
138                None => return Err("unterminated string".into()),
139                Some(b'"') => break,
140                Some(b'\\') => self.pos += 2,
141                Some(_) => self.pos += 1,
142            }
143        }
144        self.pos += 1;
145        serde_json::from_str(&self.input[start..self.pos]).map_err(|e| format!("bad string: {e}"))
146    }
147
148    fn number(&mut self) -> Result<Value<'a>, String> {
149        let start = self.pos;
150        let bytes = self.input.as_bytes();
151        let digits = |p: &mut usize| {
152            let s = *p;
153            while bytes.get(*p).is_some_and(u8::is_ascii_digit) {
154                *p += 1;
155            }
156            *p > s
157        };
158        let mut p = self.pos;
159        if bytes.get(p) == Some(&b'-') {
160            p += 1;
161        }
162        if bytes.get(p) == Some(&b'0') {
163            p += 1;
164        } else if !digits(&mut p) {
165            return Err(format!("bad number at byte {start}"));
166        }
167        if bytes.get(p) == Some(&b'.') {
168            p += 1;
169            if !digits(&mut p) {
170                return Err(format!("bad number at byte {start}"));
171            }
172        }
173        if matches!(bytes.get(p), Some(b'e' | b'E')) {
174            p += 1;
175            if matches!(bytes.get(p), Some(b'+' | b'-')) {
176                p += 1;
177            }
178            if !digits(&mut p) {
179                return Err(format!("bad number at byte {start}"));
180            }
181        }
182        self.pos = p;
183        Ok(Value::Number(&self.input[start..p]))
184    }
185}
186
187fn write(value: &Value, out: &mut String) -> Result<(), String> {
188    match value {
189        Value::Literal(l) => out.push_str(l),
190        Value::Number(n) => out.push_str(&number(n)),
191        Value::String(s) => out.push_str(&serde_json::to_string(s).expect("a str serializes")),
192        Value::Array(items) => {
193            out.push('[');
194            for (i, item) in items.iter().enumerate() {
195                if i > 0 {
196                    out.push(',');
197                }
198                write(item, out)?;
199            }
200            out.push(']');
201        }
202        Value::Object(members) => {
203            // JCS orders keys by their UTF-16 code units.
204            let mut sorted: Vec<&(String, Value)> = members.iter().collect();
205            sorted.sort_by(|a, b| a.0.encode_utf16().cmp(b.0.encode_utf16()));
206            if let Some(w) = sorted.windows(2).find(|w| w[0].0 == w[1].0) {
207                return Err(format!("the key {:?} appears twice", w[0].0));
208            }
209            out.push('{');
210            for (i, (key, value)) in sorted.into_iter().enumerate() {
211                if i > 0 {
212                    out.push(',');
213                }
214                out.push_str(&serde_json::to_string(key).expect("a str serializes"));
215                out.push(':');
216                write(value, out)?;
217            }
218            out.push('}');
219        }
220    }
221    Ok(())
222}
223
224/// The JCS form of `lexeme` when a double holds its value exactly;
225/// otherwise the value as a JSON string, in the same ECMAScript layout
226/// with every significant digit, so equal values give equal bytes
227/// (`…890.10` and `…890.1`, `1e400` and `10e399`).
228fn number(lexeme: &str) -> String {
229    let decimal = Decimal::parse(lexeme);
230    if let Ok(f) = lexeme.parse::<f64>()
231        && f.is_finite()
232    {
233        let js = if f == 0.0 { "0".to_owned() } else { ryu_js::Buffer::new().format_finite(f).to_owned() };
234        if Decimal::parse(&js) == decimal {
235            return js;
236        }
237    }
238    // An exponent beyond i64 cannot come from Postgres; keep it as written.
239    let text = decimal.map_or_else(|| lexeme.to_owned(), |d| d.to_ecmascript());
240    let mut quoted = String::with_capacity(text.len() + 2);
241    let _ = write!(quoted, "\"{text}\"");
242    quoted
243}
244
245/// A decimal value as sign, significant digits and exponent, so two
246/// spellings of one value compare equal (`1.10` and `1.1`, `1e2` and
247/// `100`). The value is `digits × 10^exponent`, with no leading or
248/// trailing zero in `digits` unless it is `0`.
249#[derive(PartialEq, Debug)]
250struct Decimal {
251    negative: bool,
252    digits: String,
253    exponent: i64,
254}
255
256impl Decimal {
257    fn parse(lexeme: &str) -> Option<Decimal> {
258        let (negative, rest) = match lexeme.strip_prefix('-') {
259            Some(r) => (true, r),
260            None => (false, lexeme),
261        };
262        let (mantissa, exp) = match rest.find(['e', 'E']) {
263            Some(i) => (&rest[..i], Some(&rest[i + 1..])),
264            None => (rest, None),
265        };
266        let (int, frac) = mantissa.split_once('.').unwrap_or((mantissa, ""));
267        let mut digits: String = format!("{int}{frac}").trim_start_matches('0').to_owned();
268        if digits.is_empty() {
269            return Some(Decimal { negative: false, digits: "0".into(), exponent: 0 });
270        }
271        let exp = match exp {
272            Some(e) => e.parse::<i64>().ok()?,
273            None => 0,
274        };
275        let mut exponent = exp.checked_sub(frac.len() as i64)?;
276        while digits.ends_with('0') {
277            digits.pop();
278            exponent = exponent.checked_add(1)?;
279        }
280        Some(Decimal { negative, digits, exponent })
281    }
282
283    /// ECMA-262 Number::toString's layout (§6.1.6.1.20) over all of
284    /// `digits`: with k digits and the point after the n-th, plain
285    /// notation for -6 < n ≤ 21, else one digit, the rest, and `e±(n-1)`.
286    fn to_ecmascript(&self) -> String {
287        let k = self.digits.len() as i64;
288        let n = k + self.exponent;
289        let d = &self.digits;
290        let mut out = String::with_capacity(d.len() + 8);
291        if self.negative {
292            out.push('-');
293        }
294        if k <= n && n <= 21 {
295            out.push_str(d);
296            out.extend(std::iter::repeat_n('0', (n - k) as usize));
297        } else if 0 < n && n <= 21 {
298            let (int, frac) = d.split_at(n as usize);
299            let _ = write!(out, "{int}.{frac}");
300        } else if -6 < n && n <= 0 {
301            out.push_str("0.");
302            out.extend(std::iter::repeat_n('0', (-n) as usize));
303            out.push_str(d);
304        } else {
305            let (first, rest) = d.split_at(1);
306            out.push_str(first);
307            if !rest.is_empty() {
308                let _ = write!(out, ".{rest}");
309            }
310            let e = n - 1;
311            let _ = write!(out, "e{}{}", if e < 0 { '-' } else { '+' }, e.unsigned_abs());
312        }
313        out
314    }
315}
316
317#[cfg(test)]
318mod tests {
319    use super::*;
320
321    fn c(json: &str) -> String {
322        canonicalize(json).unwrap()
323    }
324
325    #[test]
326    fn sorts_keys_and_drops_whitespace() {
327        assert_eq!(c(r#"{ "id": 1, "body": "hi", "a": [ true, null ] }"#), r#"{"a":[true,null],"body":"hi","id":1}"#);
328    }
329
330    #[test]
331    fn numbers_take_their_ecmascript_form() {
332        assert_eq!(c("[1.0e0, 1.10, 100, 1e21, 1E-7, -0, 0.1, 123456789012345]"), r#"[1,1.1,100,1e+21,1e-7,0,0.1,123456789012345]"#);
333    }
334
335    #[test]
336    fn numbers_a_double_cannot_hold_become_strings() {
337        assert_eq!(c("9007199254740993"), r#""9007199254740993""#);
338        assert_eq!(c("12345678901234567890.12345678901234567891"), r#""12345678901234567890.12345678901234567891""#);
339        assert_eq!(c("9007199254740992"), "9007199254740992");
340    }
341
342    #[test]
343    fn equal_values_kept_as_strings_give_equal_bytes() {
344        // A numeric's scale pads zeros that carry no value, as `1.10` and
345        // `1.1` already share one number form.
346        assert_eq!(c("12345678901234567890.10000000000000000000"), r#""12345678901234567890.1""#);
347        assert_eq!(c("12345678901234567890.1"), r#""12345678901234567890.1""#);
348        assert_eq!(c("1e400"), r#""1e+400""#);
349        assert_eq!(c("10e399"), r#""1e+400""#);
350        assert_eq!(c("1E-400"), r#""1e-400""#);
351        assert_eq!(c("0.00000000000000000000e5"), "0");
352    }
353
354    #[test]
355    fn strings_take_the_ecmascript_layout() {
356        // Number.prototype.toString's layout, with every digit kept:
357        // plain below 1e21 and from 1e-6, else one digit before the point.
358        assert_eq!(c("123456789012345678901"), r#""123456789012345678901""#);
359        assert_eq!(c("-1234567890123456789012.3"), r#""-1.2345678901234567890123e+21""#);
360        assert_eq!(c("0.000001234567890123456789"), r#""0.000001234567890123456789""#);
361        assert_eq!(c("0.0000001234567890123456789"), r#""1.234567890123456789e-7""#);
362        assert_eq!(c("-0.30000000000000001"), r#""-0.30000000000000001""#);
363    }
364
365    #[test]
366    fn keys_order_by_utf16_code_units() {
367        // U+FFFF sorts after U+10000 in UTF-16 (a surrogate pair starts
368        // 0xD800), though before it in UTF-8.
369        assert_eq!(c("{\"\u{ffff}\":1,\"\u{10000}\":2}"), "{\"\u{10000}\":2,\"\u{ffff}\":1}");
370    }
371
372    #[test]
373    fn strings_escape_the_jcs_way() {
374        assert_eq!(c(r#""a\u0001\n\"\/é""#), "\"a\\u0001\\n\\\"/é\"");
375    }
376
377    #[test]
378    fn refuses_bad_json() {
379        for bad in ["{", "[1,]", "01", "1.", "-", "{\"a\":1,\"a\":2}", "nul", "1 2", "\"\\x\""] {
380            assert!(canonicalize(bad).is_err(), "{bad}");
381        }
382        assert!(canonicalize(&"[".repeat(300)).is_err());
383    }
384}