av_receipts/
jcs.rs

1//! RFC 8785 — JSON Canonicalization Scheme (JCS).
2//!
3//! Rules implemented (and tested against the RFC's own vectors):
4//! - object keys sorted by **UTF-16 code units** (surrogate order, not byte
5//!   order — they differ for supplementary-plane characters);
6//! - numbers serialized with ECMAScript `ToString(Number)` semantics
7//!   (shortest round-trip digits; decimal notation for exponents in
8//!   (-7, 21); `e+`/`e-` exponential outside; `-0` → `0`);
9//! - strings minimally escaped (`\"`, `\\`, `\b`, `\f`, `\n`, `\r`, `\t`,
10//!   `\u00XX` for other controls; everything else literal UTF-8);
11//! - no insignificant whitespace.
12//!
13//! Integers beyond ±2^53 are **rejected** (not silently rounded): JCS numbers
14//! are IEEE-754 doubles and precision loss would corrupt canonical hashes
15//! (silent-error class D13.4).
16
17use serde_json::Value;
18use std::fmt::Write as _;
19
20/// Canonicalization failures.
21#[derive(Debug, thiserror::Error, PartialEq, Eq)]
22#[non_exhaustive]
23pub enum JcsError {
24    /// Integer outside the exactly-representable double range.
25    #[error("integer {0} outside ±2^53; JCS would lose precision")]
26    UnsafeInteger(String),
27    /// Non-finite number (unreachable via `serde_json::Value`, kept for defense).
28    #[error("non-finite number cannot be canonicalized")]
29    NonFinite,
30    /// Round-40 F5: value nesting exceeds `MAX_NESTED_DEPTH`.
31    ///
32    /// Current call sites all feed `canonicalize` a `Value` that was
33    /// parsed by `serde_json::from_slice` (default recursion limit
34    /// 128), or serialized from a typed struct with bounded depth,
35    /// so this cap is transitively already enforced. The cap here is
36    /// defense-in-depth against a future caller that pipes an
37    /// unbounded-parsed `Value` (e.g. `serde_json::Deserializer::
38    /// disable_recursion_limit`) or a merged deep tree — without
39    /// this bound, `write_value` would recurse until the OS stack
40    /// overflows.
41    #[error("value nesting exceeds {0}; JCS refuses to recurse further")]
42    TooDeep(usize),
43}
44
45/// Round-40 F5: matches `av_receipts::receipt::MAX_NESTED_DEPTH`
46/// (128), which is also the serde_json default parser recursion
47/// limit — anything a legit strict-load receipt could carry.
48const MAX_NESTED_DEPTH: usize = 128;
49
50/// Canonicalize a JSON value per RFC 8785. Returns the canonical UTF-8 string.
51pub fn canonicalize(value: &Value) -> Result<String, JcsError> {
52    // Typical receipt canonicalizes to a few hundred bytes; pre-allocate to
53    // avoid the growth-doubling churn on the first few pushes.
54    let mut out = String::with_capacity(512);
55    write_value(value, &mut out, 0)?;
56    Ok(out)
57}
58
59fn write_value(value: &Value, out: &mut String, depth: usize) -> Result<(), JcsError> {
60    if depth > MAX_NESTED_DEPTH {
61        return Err(JcsError::TooDeep(MAX_NESTED_DEPTH));
62    }
63    match value {
64        Value::Null => out.push_str("null"),
65        Value::Bool(true) => out.push_str("true"),
66        Value::Bool(false) => out.push_str("false"),
67        Value::Number(n) => write_number(n, out)?,
68        Value::String(s) => write_string(s, out),
69        Value::Array(items) => {
70            out.push('[');
71            for (i, item) in items.iter().enumerate() {
72                if i > 0 {
73                    out.push(',');
74                }
75                write_value(item, out, depth + 1)?;
76            }
77            out.push(']');
78        }
79        Value::Object(map) => {
80            // Sort keys by UTF-16 code-unit sequence.
81            let mut keys: Vec<&String> = map.keys().collect();
82            keys.sort_by(|a, b| utf16_cmp(a, b));
83            out.push('{');
84            for (i, key) in keys.iter().enumerate() {
85                if i > 0 {
86                    out.push(',');
87                }
88                write_string(key, out);
89                out.push(':');
90                if let Some(v) = map.get(*key) {
91                    write_value(v, out, depth + 1)?;
92                }
93            }
94            out.push('}');
95        }
96    }
97    Ok(())
98}
99
100/// Compare two strings by their UTF-16 code-unit sequences (RFC 8785 §3.2.3).
101fn utf16_cmp(a: &str, b: &str) -> std::cmp::Ordering {
102    a.encode_utf16().cmp(b.encode_utf16())
103}
104
105fn write_string(s: &str, out: &mut String) {
106    out.push('"');
107    for ch in s.chars() {
108        match ch {
109            '"' => out.push_str("\\\""),
110            '\\' => out.push_str("\\\\"),
111            '\u{0008}' => out.push_str("\\b"),
112            '\u{000C}' => out.push_str("\\f"),
113            '\n' => out.push_str("\\n"),
114            '\r' => out.push_str("\\r"),
115            '\t' => out.push_str("\\t"),
116            c if (c as u32) < 0x20 => {
117                let _ = write!(out, "\\u{:04x}", c as u32);
118            }
119            c => out.push(c),
120        }
121    }
122    out.push('"');
123}
124
125use av_core::error::JCS_SAFE_MAX;
126
127fn write_number(n: &serde_json::Number, out: &mut String) -> Result<(), JcsError> {
128    if let Some(u) = n.as_u64() {
129        if u > JCS_SAFE_MAX {
130            return Err(JcsError::UnsafeInteger(u.to_string()));
131        }
132        let _ = write!(out, "{u}");
133        return Ok(());
134    }
135    if let Some(i) = n.as_i64() {
136        if i < -(JCS_SAFE_MAX as i64) {
137            return Err(JcsError::UnsafeInteger(i.to_string()));
138        }
139        let _ = write!(out, "{i}");
140        return Ok(());
141    }
142    let f = n.as_f64().ok_or(JcsError::NonFinite)?;
143    if !f.is_finite() {
144        return Err(JcsError::NonFinite);
145    }
146    out.push_str(&ecma_number(f));
147    Ok(())
148}
149
150/// ECMAScript `ToString(Number)` (ECMA-262 §6.1.6.1.20) for finite doubles.
151///
152/// Digits come from ryu (shortest **correctly-rounded** representation —
153/// Rust's `{:e}`/Grisu is shortest but not always correctly rounded, which the
154/// RFC 8785 Appendix vectors catch); the ECMAScript layout rules are then
155/// applied to (digits, k).
156fn ecma_number(f: f64) -> String {
157    if f == 0.0 {
158        return "0".to_owned(); // covers -0.0 per ES semantics
159    }
160    if f < 0.0 {
161        let mut s = String::with_capacity(24);
162        s.push('-');
163        s.push_str(&ecma_number(-f));
164        return s;
165    }
166    let mut buf = ryu::Buffer::new();
167    let printed = buf.format_finite(f);
168    let (digits, k) = digits_and_k(printed);
169    let digits = digits.as_str();
170    let n = digits.len() as i64;
171
172    if (1..=21).contains(&k) && n <= k {
173        // Integer: digits followed by k-n zeros.
174        let mut s = String::from(digits);
175        for _ in 0..(k - n) {
176            s.push('0');
177        }
178        s
179    } else if (1..=21).contains(&k) {
180        // Decimal point inside the digits; 1 <= k < n here so the split is in-bounds.
181        #[allow(clippy::cast_possible_truncation, clippy::cast_sign_loss)]
182        let (int_part, frac_part) = digits.split_at(k as usize);
183        format!("{int_part}.{frac_part}")
184    } else if (-5..=0).contains(&k) {
185        // 0.000ddd… (ECMA-262: −6 < k ≤ 0)
186        let mut s = String::from("0.");
187        for _ in 0..(-k) {
188            s.push('0');
189        }
190        s.push_str(digits);
191        s
192    } else {
193        // Exponential: d[.ddd]e±(k-1)
194        let exp_val = k - 1;
195        let sign = if exp_val >= 0 { "+" } else { "-" };
196        let (first, rest) = digits.split_at(1);
197        if rest.is_empty() {
198            format!("{first}e{sign}{}", exp_val.abs())
199        } else {
200            format!("{first}.{rest}e{sign}{}", exp_val.abs())
201        }
202    }
203}
204
205/// Decompose a ryu-printed positive finite float (`"123.45"`, `"1.5e-7"`,
206/// `"12.0"`) into shortest digit string and ECMAScript `k` (value =
207/// 0.digits × 10^k).
208fn digits_and_k(printed: &str) -> (String, i64) {
209    let (mantissa, e) = match printed.split_once(['e', 'E']) {
210        Some((m, exp)) => (m, exp.parse::<i64>().unwrap_or(0)),
211        None => (printed, 0),
212    };
213    let (int_part, frac_part) = match mantissa.split_once('.') {
214        Some((i, f)) => (i, f),
215        None => (mantissa, ""),
216    };
217    let int_stripped = int_part.trim_start_matches('0');
218    let (raw, k) = if int_stripped.is_empty() {
219        let lead_zeros = frac_part.len() - frac_part.trim_start_matches('0').len();
220        (
221            frac_part.trim_start_matches('0').to_owned(),
222            e - lead_zeros as i64,
223        )
224    } else {
225        (
226            format!("{int_stripped}{frac_part}"),
227            int_stripped.len() as i64 + e,
228        )
229    };
230    let digits = raw.trim_end_matches('0');
231    if digits.is_empty() {
232        ("0".to_owned(), k)
233    } else {
234        (digits.to_owned(), k)
235    }
236}
237
238#[cfg(test)]
239mod tests {
240    #![allow(clippy::unwrap_used, clippy::expect_used, clippy::panic)]
241
242    use super::*;
243    use serde_json::json;
244
245    /// RFC 8785 Appendix B number vectors (IEEE-754 bit patterns → canonical text).
246    #[test]
247    fn rfc8785_appendix_b_numbers() {
248        let vectors: &[(u64, &str)] = &[
249            (0x0000000000000000, "0"),
250            (0x8000000000000000, "0"), // -0 → 0
251            (0x0000000000000001, "5e-324"),
252            (0x8000000000000001, "-5e-324"),
253            (0x7fefffffffffffff, "1.7976931348623157e+308"),
254            (0xffefffffffffffff, "-1.7976931348623157e+308"),
255            (0x4340000000000000, "9007199254740992"),
256            (0xc340000000000000, "-9007199254740992"),
257            (0x444b1ae4d6e2ef50, "1e+21"),
258            (0x3eb0c6f7a0b5ed8d, "0.000001"),
259            (0x3e7ad7f29abcaf48, "1e-7"),
260            (0x41b3de4355555553, "333333333.3333332"),
261            (0x41b3de4355555554, "333333333.33333325"),
262            (0x41b3de4355555555, "333333333.3333333"),
263            (0x41b3de4355555556, "333333333.3333334"),
264            (0x41b3de4355555557, "333333333.33333343"),
265            (0xbecbf647612f3696, "-0.0000033333333333333333"),
266            (0x43143ff3c1cb0959, "1424953923781206.2"),
267        ];
268        for (bits, expected) in vectors {
269            let f = f64::from_bits(*bits);
270            assert_eq!(&ecma_number(f), expected, "bits {bits:#018x}");
271        }
272    }
273
274    #[test]
275    fn integer_forms() {
276        assert_eq!(ecma_number(1.0), "1");
277        assert_eq!(ecma_number(42.0), "42");
278        assert_eq!(ecma_number(100000.0), "100000");
279        assert_eq!(ecma_number(1e20), "100000000000000000000");
280        assert_eq!(ecma_number(1e21), "1e+21");
281        assert_eq!(ecma_number(-1e21), "-1e+21");
282    }
283
284    #[test]
285    fn fraction_forms() {
286        assert_eq!(ecma_number(0.5), "0.5");
287        assert_eq!(ecma_number(0.000001), "0.000001");
288        assert_eq!(ecma_number(0.0000001), "1e-7");
289        assert_eq!(ecma_number(1.5), "1.5");
290        assert_eq!(ecma_number(1.2345678901234567), "1.2345678901234567");
291    }
292
293    /// RFC 8785 §3.2.3 key-sorting example (UTF-16 order incl. supplementary chars).
294    #[test]
295    fn rfc8785_key_sorting() {
296        // Keys via JSON escapes (editor normalization must not corrupt the vector):
297        // \u20AC €, \uD83D\uDE02 😂 (U+1F602), \uFB33 דּ (precomposed).
298        // UTF-16 code-unit order: 20AC < D83D < FB33 — differs from code-point
299        // order, where 1F602 would sort last.
300        let v: Value = serde_json::from_str(r#"{"\uFB33": 3, "\uD83D\uDE02": 2, "\u20AC": 1}"#).unwrap();
301        let c = canonicalize(&v).unwrap();
302        assert_eq!(c, "{\"\u{20ac}\":1,\"\u{1f602}\":2,\"\u{fb33}\":3}");
303    }
304
305    /// RFC 8785 Appendix A weird-input vector.
306    #[test]
307    fn rfc8785_structure_vector() {
308        let input = r#"{
309          "numbers": [333333333.33333329, 1E30, 4.50, 2e-3, 0.000000000000000000000000001],
310          "string": "\u20ac$\u000F\u000aA'\u0042\u0022\u005c\\\"\/",
311          "literals": [null, true, false]
312        }"#;
313        let v: Value = serde_json::from_str(input).unwrap();
314        let c = canonicalize(&v).unwrap();
315        let expected = "{\"literals\":[null,true,false],\"numbers\":[333333333.3333333,1e+30,4.5,0.002,1e-27],\"string\":\"€$\\u000f\\nA'B\\\"\\\\\\\\\\\"/\"}";
316        assert_eq!(c, expected);
317    }
318
319    #[test]
320    fn string_escapes() {
321        let v = json!({"a": "line\nbreak\ttab\u{0001}ctl\"quote\\back"});
322        let c = canonicalize(&v).unwrap();
323        assert_eq!(c, "{\"a\":\"line\\nbreak\\ttab\\u0001ctl\\\"quote\\\\back\"}");
324    }
325
326    #[test]
327    fn unsafe_integers_rejected() {
328        let over = serde_json::Number::from((1u64 << 53) + 1);
329        let v = Value::Number(over);
330        assert_eq!(
331            canonicalize(&v),
332            Err(JcsError::UnsafeInteger(((1u64 << 53) + 1).to_string()))
333        );
334        let under = serde_json::Number::from(-(1i64 << 53) - 1);
335        assert!(canonicalize(&Value::Number(under)).is_err());
336        // Exactly ±2^53 is fine.
337        assert!(canonicalize(&json!(1u64 << 53)).is_ok());
338        assert!(canonicalize(&json!(-(1i64 << 53))).is_ok());
339    }
340
341    #[test]
342    fn insertion_order_does_not_matter() {
343        // serde_json preserve_order keeps insertion order, so these two Values
344        // have different internal order — canonical output must be identical.
345        let a: Value = serde_json::from_str(r#"{"z":1,"a":2,"m":{"y":1,"b":2}}"#).unwrap();
346        let b: Value = serde_json::from_str(r#"{"a":2,"m":{"b":2,"y":1},"z":1}"#).unwrap();
347        assert_eq!(canonicalize(&a).unwrap(), canonicalize(&b).unwrap());
348    }
349
350    #[test]
351    fn canonicalization_is_idempotent() {
352        let v = json!({"b": [1.5, "x", {"k": 1e21}], "a": null});
353        let once = canonicalize(&v).unwrap();
354        let reparsed: Value = serde_json::from_str(&once).unwrap();
355        let twice = canonicalize(&reparsed).unwrap();
356        assert_eq!(once, twice);
357    }
358
359    #[test]
360    fn empty_containers() {
361        assert_eq!(canonicalize(&json!({})).unwrap(), "{}");
362        assert_eq!(canonicalize(&json!([])).unwrap(), "[]");
363        assert_eq!(canonicalize(&json!("")).unwrap(), "\"\"");
364    }
365
366    #[test]
367    fn space_at_boundary_u0020_is_not_escaped() {
368        // The escape guard is `< 0x20`: space (U+0020) sits at the boundary
369        // and must stay literal, not become "\u0020". This detects the
370        // <-vs-<= off-by-one silently corrupting canonical output.
371        let v = json!({"a": "a b"});
372        assert_eq!(canonicalize(&v).unwrap(), "{\"a\":\"a b\"}");
373        // And U+001F just below the boundary DOES get escaped.
374        let v2 = json!({"a": "a\u{001f}b"});
375        assert_eq!(canonicalize(&v2).unwrap(), "{\"a\":\"a\\u001fb\"}");
376    }
377
378    #[test]
379    fn positive_zero_never_prints_with_a_minus_sign() {
380        // ES semantics: both zeros print "0". The `f == 0.0` early return
381        // covers -0.0 too (IEEE: -0.0 == 0.0), and it must stay ahead of the
382        // sign-handling branch — dropping or reordering it would send -0.0
383        // through ryu and emit "-0".
384        assert_eq!(ecma_number(0.0), "0");
385        assert_eq!(ecma_number(-0.0), "0");
386    }
387
388    /// Round-40 F5: recursion is capped at `MAX_NESTED_DEPTH`. All
389    /// current call sites feed `canonicalize` a `Value` parsed by
390    /// serde_json (default limit 128) so this cap is transitively
391    /// redundant today, but a future caller that pipes a
392    /// disable_recursion_limit-parsed Value would otherwise
393    /// stack-overflow. Build a nested array manually (bypassing
394    /// serde_json's parser cap) and assert `TooDeep` is returned
395    /// cleanly rather than the process crashing.
396    /// Round-40 F5 (object branch): the array test above leaves the
397    /// `write_value(v, out, depth + 1)` recursion in the *object* arm
398    /// unpinned — a mutant that stops incrementing depth there would
399    /// canonicalize unbounded object nesting and stack-overflow on
400    /// hostile input. Same construction, maps instead of arrays.
401    #[test]
402    fn canonicalize_refuses_pathologically_nested_objects() {
403        let mut v = Value::Null;
404        for _ in 0..MAX_NESTED_DEPTH + 10 {
405            let mut map = serde_json::Map::new();
406            map.insert("k".to_owned(), v);
407            v = Value::Object(map);
408        }
409        assert_eq!(canonicalize(&v), Err(JcsError::TooDeep(MAX_NESTED_DEPTH)));
410    }
411
412    #[test]
413    fn canonicalize_refuses_pathologically_nested_arrays() {
414        let mut v = Value::Array(vec![Value::Null]);
415        for _ in 0..MAX_NESTED_DEPTH + 10 {
416            v = Value::Array(vec![v]);
417        }
418        assert_eq!(canonicalize(&v), Err(JcsError::TooDeep(MAX_NESTED_DEPTH)));
419    }
420
421    #[test]
422    fn canonicalize_accepts_depths_up_to_the_cap() {
423        // Build a nested tree at exactly MAX_NESTED_DEPTH to lock
424        // in the boundary behaviour. `MAX_NESTED_DEPTH + 1` is the
425        // cutoff; MAX itself must still succeed.
426        let mut v = Value::Null;
427        for _ in 0..MAX_NESTED_DEPTH {
428            v = Value::Array(vec![v]);
429        }
430        assert!(canonicalize(&v).is_ok());
431    }
432}
av_receipts/jcs.rs

av_receipts/
jcs.rs
