jcs.rsRFC 8785 (JCS) canonical JSON that never loses a digit.
Numbers keep their lexeme through parsing. A number is written the
JCS way (ECMAScript Number.prototype.toString, via ryu-js) only when
that text has exactly the value of the original; otherwise, as for a
bigint beyond 2^53 or a numeric(38,20), it is written as a JSON
string holding every digit of its value, in the same ECMAScript
layout, so no digit is lost and equal values give equal bytes
(contract Cache).
Generic canonicalizers go through f64 and silently round (review #2).
12use std::fmt::Write;
Nesting deeper than this is refused rather than risking the stack.
15const MAX_DEPTH: usize = 256;
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 }
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 }
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}
The JCS form of lexeme when a double holds its value exactly;
otherwise the value as a JSON string, in the same ECMAScript layout
with every significant digit, so equal values give equal bytes
(…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}
A decimal value as sign, significant digits and exponent, so two
spellings of one value compare equal (1.10 and 1.1, 1e2 and
100). The value is digits × 10^exponent, with no leading or
trailing zero in digits unless it is 0.
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 }
ECMA-262 Number::toString's layout (§6.1.6.1.20) over all of
digits: with k digits and the point after the n-th, plain
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}
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}