From 602fee6edc1e8ecd35655d9a3b12c861de0428d4 Mon Sep 17 00:00:00 2001 From: tv Date: Mon, 16 Nov 2026 17:48:39 +0000 Subject: federation: JSON written one way MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit An event is the JCS encoding (RFC 8785) of a JSON object, within the limits federation 1 sets (`docs/federation.md`, Events). `jcs::read` gives the JSON bytes are only where they are what JCS writes of it: names sorted by their UTF-16 units and none twice, no whitespace, strings escaped as ECMAScript escapes them; and, beyond JCS, numbers only integers from −2⁵³ to 2⁵³, strings only whole Unicode characters, and objects and arrays nested up to 32 deep. Tests show what reads back and what is none, the order of names by UTF-16 units that byte order gets wrong, and the depth. --- src/federation/jcs.rs | 451 ++++++++++++++++++++++++++++++++++++++++++++++++++ src/federation/mod.rs | 1 + 2 files changed, 452 insertions(+) create mode 100644 src/federation/jcs.rs (limited to 'src') diff --git a/src/federation/jcs.rs b/src/federation/jcs.rs new file mode 100644 index 0000000..8b05994 --- /dev/null +++ b/src/federation/jcs.rs @@ -0,0 +1,451 @@ +//! JSON written one way: JCS (RFC 8785), as the federation has it (`docs/federation.md`, +//! Events). An object's names sorted by their UTF-16 units, no whitespace, strings escaped +//! as ECMAScript escapes them; and, beyond JCS, numbers only integers from −2⁵³ to 2⁵³, +//! strings only whole Unicode characters, and objects and arrays nested up to 32 deep. So +//! bytes read as JSON only where they are what that JSON writes. + +use std::cmp::Ordering; + +/// How deep objects and arrays nest, the outermost the first. +pub(crate) const DEPTH: usize = 32; + +/// The largest integer, and so the smallest by its sign. +pub(crate) const LARGEST_INTEGER: i64 = 1 << 53; + +/// A JSON value as the federation takes one. +#[derive(Clone, Debug, PartialEq, Eq)] +pub(crate) enum Json { + Null, + Bool(bool), + Int(i64), + Str(String), + Array(Vec), + /// Its members, their names in JCS's order (`names_order`), none twice. + Object(Vec<(String, Json)>), +} + +impl Json { + /// An object of `members`, sorted; `None` where a name is there twice. + pub(crate) fn object(mut members: Vec<(String, Json)>) -> Option { + members.sort_by(|a, b| names_order(&a.0, &b.0)); + if members.windows(2).any(|pair| pair[0].0 == pair[1].0) { + return None; + } + Some(Json::Object(members)) + } + + /// The member named `name`, of an object. + pub(crate) fn get(&self, name: &str) -> Option<&Json> { + match self { + Json::Object(members) => members + .iter() + .find(|(member, _)| member == name) + .map(|(_, value)| value), + _ => None, + } + } + + /// The names of an object's members, in order; none of anything else. + pub(crate) fn names(&self) -> Vec<&str> { + match self { + Json::Object(members) => members.iter().map(|(name, _)| name.as_str()).collect(), + _ => Vec::new(), + } + } + + /// The object without the member named `name`. + pub(crate) fn without(&self, name: &str) -> Json { + match self { + Json::Object(members) => Json::Object( + members + .iter() + .filter(|(member, _)| member != name) + .cloned() + .collect(), + ), + other => other.clone(), + } + } + + pub(crate) fn as_str(&self) -> Option<&str> { + match self { + Json::Str(text) => Some(text), + _ => None, + } + } + + pub(crate) fn as_int(&self) -> Option { + match self { + Json::Int(n) => Some(*n), + _ => None, + } + } + + pub(crate) fn as_bool(&self) -> Option { + match self { + Json::Bool(b) => Some(*b), + _ => None, + } + } + + pub(crate) fn as_array(&self) -> Option<&[Json]> { + match self { + Json::Array(items) => Some(items), + _ => None, + } + } + + pub(crate) fn is_object(&self) -> bool { + matches!(self, Json::Object(_)) + } + + /// Its bytes, as JCS writes them. + pub(crate) fn bytes(&self) -> Vec { + let mut out = Vec::new(); + write(self, &mut out); + out + } +} + +/// JCS's order of names: by their UTF-16 units. +pub(crate) fn names_order(a: &str, b: &str) -> Ordering { + a.encode_utf16().cmp(b.encode_utf16()) +} + +/// The JSON `bytes` are, where they are what JCS writes of it, within the federation's +/// limits. +pub(crate) fn read(bytes: &[u8]) -> Option { + let text = std::str::from_utf8(bytes).ok()?; + let mut parser = Parser { + text: text.as_bytes(), + at: 0, + }; + let value = parser.value(0)?; + if parser.at != parser.text.len() { + return None; + } + (value.bytes() == bytes).then_some(value) +} + +fn write(value: &Json, out: &mut Vec) { + match value { + Json::Null => out.extend_from_slice(b"null"), + Json::Bool(true) => out.extend_from_slice(b"true"), + Json::Bool(false) => out.extend_from_slice(b"false"), + Json::Int(n) => out.extend_from_slice(n.to_string().as_bytes()), + Json::Str(text) => write_string(text, out), + Json::Array(items) => { + out.push(b'['); + for (i, item) in items.iter().enumerate() { + if i > 0 { + out.push(b','); + } + write(item, out); + } + out.push(b']'); + } + Json::Object(members) => { + out.push(b'{'); + for (i, (name, item)) in members.iter().enumerate() { + if i > 0 { + out.push(b','); + } + write_string(name, out); + out.push(b':'); + write(item, out); + } + out.push(b'}'); + } + } +} + +/// A string as ECMAScript's `JSON.stringify` writes it (RFC 8785, 3.2.2.2). +fn write_string(text: &str, out: &mut Vec) { + out.push(b'"'); + for c in text.chars() { + match c { + '"' => out.extend_from_slice(b"\\\""), + '\\' => out.extend_from_slice(b"\\\\"), + '\u{8}' => out.extend_from_slice(b"\\b"), + '\t' => out.extend_from_slice(b"\\t"), + '\n' => out.extend_from_slice(b"\\n"), + '\u{c}' => out.extend_from_slice(b"\\f"), + '\r' => out.extend_from_slice(b"\\r"), + c if (c as u32) < 0x20 => { + out.extend_from_slice(format!("\\u{:04x}", c as u32).as_bytes()); + } + c => { + let mut buffer = [0; 4]; + out.extend_from_slice(c.encode_utf8(&mut buffer).as_bytes()); + } + } + } + out.push(b'"'); +} + +/// Reads JSON, any JSON within the federation's limits; whether it is written as JCS +/// writes it is asked after (`read`). +struct Parser<'a> { + text: &'a [u8], + at: usize, +} + +impl Parser<'_> { + fn peek(&self) -> Option { + self.text.get(self.at).copied() + } + + fn next(&mut self) -> Option { + let byte = self.peek()?; + self.at += 1; + Some(byte) + } + + fn eat(&mut self, expected: &[u8]) -> Option<()> { + let end = self.at.checked_add(expected.len())?; + (self.text.get(self.at..end)? == expected).then(|| self.at = end) + } + + fn space(&mut self) { + while matches!(self.peek(), Some(b' ' | b'\t' | b'\n' | b'\r')) { + self.at += 1; + } + } + + /// A value, inside `depth` objects and arrays. + fn value(&mut self, depth: usize) -> Option { + self.space(); + let value = match self.peek()? { + b'n' => self.eat(b"null").map(|()| Json::Null), + b't' => self.eat(b"true").map(|()| Json::Bool(true)), + b'f' => self.eat(b"false").map(|()| Json::Bool(false)), + b'"' => self.string().map(Json::Str), + b'[' => self.array(depth + 1), + b'{' => self.object(depth + 1), + b'-' | b'0'..=b'9' => self.integer().map(Json::Int), + _ => None, + }; + self.space(); + value + } + + fn array(&mut self, depth: usize) -> Option { + if depth > DEPTH { + return None; + } + self.eat(b"[")?; + let mut items = Vec::new(); + self.space(); + if self.peek()? == b']' { + self.at += 1; + return Some(Json::Array(items)); + } + loop { + items.push(self.value(depth)?); + match self.next()? { + b',' => {} + b']' => return Some(Json::Array(items)), + _ => return None, + } + } + } + + fn object(&mut self, depth: usize) -> Option { + if depth > DEPTH { + return None; + } + self.eat(b"{")?; + let mut members = Vec::new(); + self.space(); + if self.peek()? == b'}' { + self.at += 1; + return Some(Json::Object(members)); + } + loop { + self.space(); + let name = self.string()?; + self.space(); + self.eat(b":")?; + members.push((name, self.value(depth)?)); + match self.next()? { + b',' => {} + b'}' => return Json::object(members), + _ => return None, + } + } + } + + /// An integer from −2⁵³ to 2⁵³; none with a fraction or an exponent. + fn integer(&mut self) -> Option { + let negative = self.peek() == Some(b'-'); + if negative { + self.at += 1; + } + let start = self.at; + while matches!(self.peek(), Some(b'0'..=b'9')) { + self.at += 1; + } + let digits = &self.text[start..self.at]; + if digits.is_empty() || (digits.len() > 1 && digits[0] == b'0') { + return None; + } + if matches!(self.peek(), Some(b'.' | b'e' | b'E')) { + return None; + } + let mut n: i64 = 0; + for digit in digits { + n = n.checked_mul(10)?.checked_add(i64::from(digit - b'0'))?; + if n > LARGEST_INTEGER { + return None; + } + } + Some(if negative { -n } else { n }) + } + + /// A string of whole Unicode characters: a surrogate escaped alone is none. + fn string(&mut self) -> Option { + self.eat(b"\"")?; + let mut text = String::new(); + loop { + let start = self.at; + while !matches!(self.peek()?, b'"' | b'\\') { + if self.peek()? < 0x20 { + return None; + } + self.at += 1; + } + // The input is UTF-8, and `"` and `\` are never inside a character's bytes. + text.push_str(std::str::from_utf8(&self.text[start..self.at]).ok()?); + match self.next()? { + b'"' => return Some(text), + _ => text.push(self.escaped()?), + } + } + } + + /// The character an escape after `\` stands for. + fn escaped(&mut self) -> Option { + Some(match self.next()? { + b'"' => '"', + b'\\' => '\\', + b'/' => '/', + b'b' => '\u{8}', + b'f' => '\u{c}', + b'n' => '\n', + b'r' => '\r', + b't' => '\t', + b'u' => { + let unit = self.hex4()?; + match unit { + 0xd800..=0xdbff => { + self.eat(b"\\u")?; + let low = self.hex4()?; + if !(0xdc00..=0xdfff).contains(&low) { + return None; + } + let code = 0x10000 + ((unit - 0xd800) << 10) + (low - 0xdc00); + char::from_u32(code)? + } + 0xdc00..=0xdfff => return None, + unit => char::from_u32(unit)?, + } + } + _ => return None, + }) + } + + fn hex4(&mut self) -> Option { + let mut unit = 0; + for _ in 0..4 { + let digit = char::from(self.next()?).to_digit(16)?; + unit = unit * 16 + digit; + } + Some(unit) + } +} + +#[cfg(test)] +mod tests { + use super::*; + + fn reads(text: &str) -> bool { + read(text.as_bytes()).is_some() + } + + #[test] + fn what_jcs_writes_reads_back() { + for text in [ + r#"{"a":1,"b":[true,false,null],"c":{"d":"e"}}"#, + r#"[]"#, + r#"{}"#, + r#""\u001f\b\t\n\f\r\"\\""#, + "\"\u{2028}\u{7f}é𝄞/\"", + "-9007199254740992", + "9007199254740992", + "0", + ] { + assert!(reads(text), "{text}"); + } + } + + #[test] + fn json_written_otherwise_is_none() { + for text in [ + r#"{"b":1,"a":2}"#, + r#"{"a":1,"a":1}"#, + r#"{ "a":1}"#, + r#"[1, 2]"#, + "1.0", + "1e3", + "-0", + "01", + "9007199254740993", + "-9007199254740993", + r#""\ud800""#, + r#""\udc00\ud800""#, + r#""\u001F""#, + r#""\/""#, + r#""
""#, + r#""A""#, + "\"\u{1}\"", + "nul", + "[1]x", + "", + ] { + assert!(!reads(text), "{text}"); + } + assert_eq!(read(b"\"\xff\""), None); + } + + #[test] + fn names_are_sorted_by_their_utf16_units() { + // By UTF-8 bytes U+E000 comes first; by UTF-16 units U+10000 does. + let object = Json::object(vec![ + ("\u{e000}".to_owned(), Json::Int(1)), + ("\u{10000}".to_owned(), Json::Int(2)), + ]) + .expect("an object"); + let bytes = object.bytes(); + assert_eq!(bytes, "{\"\u{10000}\":2,\"\u{e000}\":1}".as_bytes()); + assert_eq!(read(&bytes), Some(object)); + assert!(!reads("{\"\u{e000}\":1,\"\u{10000}\":2}")); + } + + #[test] + fn objects_and_arrays_nest_up_to_32_deep() { + let nested = |depth: usize| format!("{}{}", "[".repeat(depth), "]".repeat(depth)); + assert!(reads(&nested(DEPTH))); + assert!(!reads(&nested(DEPTH + 1))); + let objects = |depth: usize| format!("{}1{}", r#"{"a":"#.repeat(depth), "}".repeat(depth)); + assert!(reads(&objects(DEPTH))); + assert!(!reads(&objects(DEPTH + 1))); + } + + #[test] + fn an_object_reads_without_a_member() { + let event = read(br#"{"a":1,"sig":"x"}"#).expect("an object"); + assert_eq!(event.without("sig").bytes(), br#"{"a":1}"#); + assert_eq!(event.get("a"), Some(&Json::Int(1))); + assert_eq!(event.names(), vec!["a", "sig"]); + } +} diff --git a/src/federation/mod.rs b/src/federation/mod.rs index 0005038..6485c8a 100644 --- a/src/federation/mod.rs +++ b/src/federation/mod.rs @@ -5,4 +5,5 @@ // Until a node runs it (stage 3), parts of it are used by nothing, or by tests alone. #![allow(dead_code)] +pub(crate) mod jcs; pub(crate) mod store; -- cgit v1.3.1