waitprims_core/
jcs.rs

1//! RFC 8785 JSON Canonicalization Scheme (JCS).
2//!
3//! Ordinary `serde_json::to_string` and `jq -S` are not JCS. Public entry
4//! is raw JSON / bytes through a duplicate-aware parser. A `Value` may be
5//! encoded only after that parser has guaranteed uniqueness.
6
7use serde_json::{Map, Value};
8use thiserror::Error;
9
10/// Canonicalization failure.
11#[derive(Debug, Error)]
12pub enum JcsError {
13    /// Input is not well-formed JSON.
14    #[error("invalid JSON")]
15    InvalidJson,
16    /// An object member name was repeated.
17    #[error("duplicate object member name")]
18    DuplicateKey,
19    /// A lone UTF-16 surrogate is not permitted.
20    #[error("lone surrogate is not permitted in JCS")]
21    LoneSurrogate,
22    /// NaN or Infinity is not permitted.
23    #[error("non-finite numbers are not permitted in JCS")]
24    NonFiniteNumber,
25    /// An integer is not exactly representable as IEEE 754 binary64.
26    #[error("integer is outside the I-JSON IEEE 754 binary64 domain")]
27    IntegerOutsideIjson,
28    /// A value type cannot be canonicalized.
29    #[error("unsupported JSON value")]
30    Unsupported,
31}
32
33/// Parse JSON with I-JSON / RFC 8785 constraints, then canonicalize.
34pub fn canonicalize_json(raw: &str) -> Result<Vec<u8>, JcsError> {
35    canonicalize_bytes(raw.as_bytes())
36}
37
38/// Parse UTF-8 JSON bytes with I-JSON / RFC 8785 constraints, then canonicalize.
39pub fn canonicalize_bytes(raw: &[u8]) -> Result<Vec<u8>, JcsError> {
40    let text = std::str::from_utf8(raw).map_err(|_| JcsError::InvalidJson)?;
41    let value = parse_strict(text)?;
42    encode_unique(&value)
43}
44
45/// Encode a value that was produced by [`parse_strict`] (uniqueness guaranteed).
46pub(crate) fn encode_unique(value: &Value) -> Result<Vec<u8>, JcsError> {
47    let mut out = String::new();
48    encode(value, &mut out)?;
49    Ok(out.into_bytes())
50}
51
52/// Parse JSON, rejecting duplicate keys, lone surrogates, non-finite
53/// numbers, and integers outside the I-JSON binary64 domain.
54pub fn parse_strict(raw: &str) -> Result<Value, JcsError> {
55    let mut parser = Parser {
56        bytes: raw.as_bytes(),
57        pos: 0,
58    };
59    let value = parser.parse_value()?;
60    parser.skip_ws();
61    if parser.pos != parser.bytes.len() {
62        return Err(JcsError::InvalidJson);
63    }
64    Ok(value)
65}
66
67struct Parser<'a> {
68    bytes: &'a [u8],
69    pos: usize,
70}
71
72impl<'a> Parser<'a> {
73    fn parse_value(&mut self) -> Result<Value, JcsError> {
74        self.skip_ws();
75        let b = self.peek().ok_or(JcsError::InvalidJson)?;
76        match b {
77            b'n' => self.parse_literal(b"null", Value::Null),
78            b't' => self.parse_literal(b"true", Value::Bool(true)),
79            b'f' => self.parse_literal(b"false", Value::Bool(false)),
80            b'"' => Ok(Value::String(self.parse_string()?)),
81            b'[' => self.parse_array(),
82            b'{' => self.parse_object(),
83            b'-' | b'0'..=b'9' => self.parse_number(),
84            _ => Err(JcsError::InvalidJson),
85        }
86    }
87
88    fn parse_literal(&mut self, token: &[u8], value: Value) -> Result<Value, JcsError> {
89        if self.bytes.get(self.pos..self.pos + token.len()) != Some(token) {
90            return Err(JcsError::InvalidJson);
91        }
92        self.pos += token.len();
93        Ok(value)
94    }
95
96    fn parse_array(&mut self) -> Result<Value, JcsError> {
97        self.pos += 1;
98        self.skip_ws();
99        let mut items = Vec::new();
100        if self.peek() == Some(b']') {
101            self.pos += 1;
102            return Ok(Value::Array(items));
103        }
104        loop {
105            items.push(self.parse_value()?);
106            self.skip_ws();
107            match self.peek() {
108                Some(b',') => {
109                    self.pos += 1;
110                }
111                Some(b']') => {
112                    self.pos += 1;
113                    break;
114                }
115                _ => return Err(JcsError::InvalidJson),
116            }
117        }
118        Ok(Value::Array(items))
119    }
120
121    fn parse_object(&mut self) -> Result<Value, JcsError> {
122        self.pos += 1;
123        self.skip_ws();
124        let mut map = Map::new();
125        if self.peek() == Some(b'}') {
126            self.pos += 1;
127            return Ok(Value::Object(map));
128        }
129        loop {
130            self.skip_ws();
131            if self.peek() != Some(b'"') {
132                return Err(JcsError::InvalidJson);
133            }
134            let key = self.parse_string()?;
135            if map.contains_key(&key) {
136                return Err(JcsError::DuplicateKey);
137            }
138            self.skip_ws();
139            if self.peek() != Some(b':') {
140                return Err(JcsError::InvalidJson);
141            }
142            self.pos += 1;
143            let value = self.parse_value()?;
144            map.insert(key, value);
145            self.skip_ws();
146            match self.peek() {
147                Some(b',') => {
148                    self.pos += 1;
149                }
150                Some(b'}') => {
151                    self.pos += 1;
152                    break;
153                }
154                _ => return Err(JcsError::InvalidJson),
155            }
156        }
157        Ok(Value::Object(map))
158    }
159
160    fn parse_string(&mut self) -> Result<String, JcsError> {
161        self.pos += 1;
162        let mut out = String::new();
163        loop {
164            let b = self.next().ok_or(JcsError::InvalidJson)?;
165            match b {
166                b'"' => return Ok(out),
167                b'\\' => {
168                    let esc = self.next().ok_or(JcsError::InvalidJson)?;
169                    match esc {
170                        b'"' => out.push('"'),
171                        b'\\' => out.push('\\'),
172                        b'/' => out.push('/'),
173                        b'b' => out.push('\u{0008}'),
174                        b'f' => out.push('\u{000c}'),
175                        b'n' => out.push('\n'),
176                        b'r' => out.push('\r'),
177                        b't' => out.push('\t'),
178                        b'u' => out.push(self.parse_unicode_escape()?),
179                        _ => return Err(JcsError::InvalidJson),
180                    }
181                }
182                0x00..=0x1f => return Err(JcsError::InvalidJson),
183                _ => {
184                    // Continue a UTF-8 scalar starting at this byte.
185                    self.pos -= 1;
186                    let ch = self.next_char()?;
187                    out.push(ch);
188                }
189            }
190        }
191    }
192
193    fn parse_unicode_escape(&mut self) -> Result<char, JcsError> {
194        let unit = self.read_hex4()?;
195        if (0xd800..=0xdbff).contains(&unit) {
196            if self.peek() != Some(b'\\') {
197                return Err(JcsError::LoneSurrogate);
198            }
199            self.pos += 1;
200            if self.next() != Some(b'u') {
201                return Err(JcsError::LoneSurrogate);
202            }
203            let low = self.read_hex4()?;
204            if !(0xdc00..=0xdfff).contains(&low) {
205                return Err(JcsError::LoneSurrogate);
206            }
207            let cp = 0x10000 + (((u32::from(unit) - 0xd800) << 10) | (u32::from(low) - 0xdc00));
208            return char::from_u32(cp).ok_or(JcsError::LoneSurrogate);
209        }
210        if (0xdc00..=0xdfff).contains(&unit) {
211            return Err(JcsError::LoneSurrogate);
212        }
213        char::from_u32(u32::from(unit)).ok_or(JcsError::InvalidJson)
214    }
215
216    fn read_hex4(&mut self) -> Result<u16, JcsError> {
217        let mut value = 0u16;
218        for _ in 0..4 {
219            let b = self.next().ok_or(JcsError::InvalidJson)?;
220            let digit = match b {
221                b'0'..=b'9' => b - b'0',
222                b'a'..=b'f' => b - b'a' + 10,
223                b'A'..=b'F' => b - b'A' + 10,
224                _ => return Err(JcsError::InvalidJson),
225            };
226            value = (value << 4) | u16::from(digit);
227        }
228        Ok(value)
229    }
230
231    fn parse_number(&mut self) -> Result<Value, JcsError> {
232        let start = self.pos;
233        if self.peek() == Some(b'-') {
234            self.pos += 1;
235        }
236        if self.peek() == Some(b'0') {
237            self.pos += 1;
238            if matches!(self.peek(), Some(b'0'..=b'9')) {
239                return Err(JcsError::InvalidJson);
240            }
241        } else if matches!(self.peek(), Some(b'1'..=b'9')) {
242            self.pos += 1;
243            while matches!(self.peek(), Some(b'0'..=b'9')) {
244                self.pos += 1;
245            }
246        } else {
247            return Err(JcsError::InvalidJson);
248        }
249        let mut is_integer_token = true;
250        if self.peek() == Some(b'.') {
251            is_integer_token = false;
252            self.pos += 1;
253            if !matches!(self.peek(), Some(b'0'..=b'9')) {
254                return Err(JcsError::InvalidJson);
255            }
256            while matches!(self.peek(), Some(b'0'..=b'9')) {
257                self.pos += 1;
258            }
259        }
260        if matches!(self.peek(), Some(b'e' | b'E')) {
261            is_integer_token = false;
262            self.pos += 1;
263            if matches!(self.peek(), Some(b'+' | b'-')) {
264                self.pos += 1;
265            }
266            if !matches!(self.peek(), Some(b'0'..=b'9')) {
267                return Err(JcsError::InvalidJson);
268            }
269            while matches!(self.peek(), Some(b'0'..=b'9')) {
270                self.pos += 1;
271            }
272        }
273        let token =
274            std::str::from_utf8(&self.bytes[start..self.pos]).map_err(|_| JcsError::InvalidJson)?;
275        if is_integer_token {
276            let parsed: i128 = token.parse().map_err(|_| JcsError::IntegerOutsideIjson)?;
277            return Ok(Value::Number(ijson_int(parsed)?));
278        }
279        let number: f64 = token.parse().map_err(|_| JcsError::InvalidJson)?;
280        if !number.is_finite() {
281            return Err(JcsError::NonFiniteNumber);
282        }
283        Ok(Value::Number(
284            serde_json::Number::from_f64(number).ok_or(JcsError::NonFiniteNumber)?,
285        ))
286    }
287
288    fn next_char(&mut self) -> Result<char, JcsError> {
289        let rest =
290            std::str::from_utf8(&self.bytes[self.pos..]).map_err(|_| JcsError::InvalidJson)?;
291        let ch = rest.chars().next().ok_or(JcsError::InvalidJson)?;
292        self.pos += ch.len_utf8();
293        Ok(ch)
294    }
295
296    fn peek(&self) -> Option<u8> {
297        self.bytes.get(self.pos).copied()
298    }
299
300    fn next(&mut self) -> Option<u8> {
301        let b = self.peek()?;
302        self.pos += 1;
303        Some(b)
304    }
305
306    fn skip_ws(&mut self) {
307        while matches!(self.peek(), Some(b' ' | b'\t' | b'\n' | b'\r')) {
308            self.pos += 1;
309        }
310    }
311}
312
313fn ijson_int(value: i128) -> Result<serde_json::Number, JcsError> {
314    let as_float = value as f64;
315    if !as_float.is_finite() || as_float as i128 != value {
316        return Err(JcsError::IntegerOutsideIjson);
317    }
318    if let Ok(i) = i64::try_from(value) {
319        return Ok(serde_json::Number::from(i));
320    }
321    serde_json::Number::from_f64(as_float).ok_or(JcsError::IntegerOutsideIjson)
322}
323
324fn encode(value: &Value, out: &mut String) -> Result<(), JcsError> {
325    match value {
326        Value::Null => out.push_str("null"),
327        Value::Bool(true) => out.push_str("true"),
328        Value::Bool(false) => out.push_str("false"),
329        Value::String(s) => encode_string(s, out)?,
330        Value::Number(n) => encode_number(n, out)?,
331        Value::Array(items) => {
332            out.push('[');
333            for (i, item) in items.iter().enumerate() {
334                if i > 0 {
335                    out.push(',');
336                }
337                encode(item, out)?;
338            }
339            out.push(']');
340        }
341        Value::Object(map) => {
342            let mut keys: Vec<&String> = map.keys().collect();
343            keys.sort_by(|a, b| a.encode_utf16().cmp(b.encode_utf16()));
344            out.push('{');
345            for (i, key) in keys.iter().enumerate() {
346                if i > 0 {
347                    out.push(',');
348                }
349                encode_string(key, out)?;
350                out.push(':');
351                encode(&map[*key], out)?;
352            }
353            out.push('}');
354        }
355    }
356    Ok(())
357}
358
359fn encode_string(value: &str, out: &mut String) -> Result<(), JcsError> {
360    out.push('"');
361    for ch in value.chars() {
362        let code = ch as u32;
363        match ch {
364            '"' => out.push_str("\\\""),
365            '\\' => out.push_str("\\\\"),
366            '\u{0008}' => out.push_str("\\b"),
367            '\u{000c}' => out.push_str("\\f"),
368            '\n' => out.push_str("\\n"),
369            '\r' => out.push_str("\\r"),
370            '\t' => out.push_str("\\t"),
371            _ if (0xd800..=0xdfff).contains(&code) => return Err(JcsError::LoneSurrogate),
372            _ if code < 0x20 => {
373                out.push_str(&format!("\\u{code:04x}"));
374            }
375            _ => out.push(ch),
376        }
377    }
378    out.push('"');
379    Ok(())
380}
381
382fn encode_number(number: &serde_json::Number, out: &mut String) -> Result<(), JcsError> {
383    if let Some(i) = number.as_i64() {
384        let as_float = i as f64;
385        if as_float as i64 != i {
386            return Err(JcsError::IntegerOutsideIjson);
387        }
388        encode_f64(as_float, out)?;
389        return Ok(());
390    }
391    if let Some(u) = number.as_u64() {
392        let as_float = u as f64;
393        if as_float as u64 != u {
394            return Err(JcsError::IntegerOutsideIjson);
395        }
396        encode_f64(as_float, out)?;
397        return Ok(());
398    }
399    let f = number.as_f64().ok_or(JcsError::Unsupported)?;
400    encode_f64(f, out)
401}
402
403fn encode_f64(number: f64, out: &mut String) -> Result<(), JcsError> {
404    if !number.is_finite() {
405        return Err(JcsError::NonFiniteNumber);
406    }
407    if number == 0.0 {
408        out.push('0');
409        return Ok(());
410    }
411    let mut buffer = ryu_js::Buffer::new();
412    out.push_str(buffer.format_finite(number));
413    Ok(())
414}
415
416#[cfg(test)]
417mod tests {
418    use super::*;
419
420    #[test]
421    fn sorts_keys_and_elides_whitespace() {
422        let canonical = canonicalize_json("{\n  \"y\": 2,\n  \"x\": 1\n}\n").unwrap();
423        assert_eq!(canonical, br#"{"x":1,"y":2}"#);
424    }
425
426    #[test]
427    fn integer_valued_float_is_es_integer() {
428        let canonical = canonicalize_json("{\"n\": 50.0}").unwrap();
429        assert_eq!(canonical, br#"{"n":50}"#);
430    }
431
432    #[test]
433    fn rejects_duplicate_keys() {
434        let err = canonicalize_json("{\"a\":1,\"a\":2}").unwrap_err();
435        assert!(matches!(err, JcsError::DuplicateKey));
436    }
437
438    #[test]
439    fn rejects_lone_surrogate() {
440        let err = canonicalize_json("{\"a\":\"\\uD800\"}").unwrap_err();
441        assert!(matches!(err, JcsError::LoneSurrogate));
442    }
443
444    #[test]
445    fn rejects_integer_outside_ijson() {
446        let err = canonicalize_json("9007199254740993").unwrap_err();
447        assert!(matches!(err, JcsError::IntegerOutsideIjson));
448    }
449
450    #[test]
451    fn rejects_non_finite_exponent() {
452        let err = canonicalize_json("1e400").unwrap_err();
453        assert!(matches!(err, JcsError::NonFiniteNumber));
454    }
455
456    #[test]
457    fn accepts_exact_binary64_integer_bound() {
458        let canonical = canonicalize_json("9007199254740992").unwrap();
459        assert_eq!(canonical, b"9007199254740992");
460    }
461}
waitprims_core/jcs.rs

waitprims_core/
jcs.rs
