verticopolis_engine/
canonical.rs

1//! Canonical JSON and the digest the conformance suite compares: object
2//! keys sorted, numbers and strings written one way, so two equal values
3//! always give the same text and the same hash on any platform.
4use serde_json::Value;
5use sha2::{Digest, Sha256};
6
7use crate::jsmath::number_to_string;
8
9/// Escape a string as `JSON.stringify` does: short escapes for `"`, `\`,
10/// and the five named controls, `\u00xx` for other controls, `\udxxx` for an
11/// unpaired surrogate (which a Rust `str` cannot hold, so none appear), and
12/// everything else as is.
13fn write_string(out: &mut String, s: &str) {
14    out.push('"');
15    for c in s.chars() {
16        match c {
17            '"' => out.push_str("\\\""),
18            '\\' => out.push_str("\\\\"),
19            '\u{8}' => out.push_str("\\b"),
20            '\t' => out.push_str("\\t"),
21            '\n' => out.push_str("\\n"),
22            '\u{c}' => out.push_str("\\f"),
23            '\r' => out.push_str("\\r"),
24            c if (c as u32) < 0x20 => out.push_str(&format!("\\u{:04x}", c as u32)),
25            c => out.push(c),
26        }
27    }
28    out.push('"');
29}
30
31/// UTF-16 code unit order, the order `Array.prototype.sort` gives string keys.
32fn utf16_cmp(a: &str, b: &str) -> std::cmp::Ordering {
33    a.encode_utf16().cmp(b.encode_utf16())
34}
35
36/// An array index as a JavaScript object key: `"0"` or a decimal without a
37/// leading zero, below 2^32 - 1. A JavaScript object visits such keys first,
38/// in numeric order, then its other keys in insertion order.
39fn array_index(k: &str) -> Option<u32> {
40    if k.is_empty() || (k.len() > 1 && k.starts_with('0')) || !k.bytes().all(|b| b.is_ascii_digit())
41    {
42        return None;
43    }
44    k.parse::<u32>().ok().filter(|&n| n != u32::MAX)
45}
46
47/// Where a key sorts among an object's keys in JavaScript: an array index at
48/// its number, every other key after all of them (the sort is stable, so
49/// those keep insertion order).
50pub(crate) fn js_key_rank(k: &str) -> u64 {
51    array_index(k).map_or(1u64 << 32, u64::from)
52}
53
54/// How `write_value` orders an object's keys.
55#[derive(Clone, Copy)]
56enum KeyOrder {
57    /// UTF-16 code unit order, the canonical text.
58    Sorted,
59    /// The order `JSON.stringify` visits a JavaScript object built with the
60    /// map's keys in insertion order.
61    Js,
62}
63
64fn write_value(out: &mut String, v: &Value, order: KeyOrder) {
65    match v {
66        Value::Null => out.push_str("null"),
67        Value::Bool(b) => out.push_str(if *b { "true" } else { "false" }),
68        Value::Number(n) => {
69            let x = n.as_f64().expect("finite number");
70            assert!(x.is_finite(), "canonicalJson: non-finite number");
71            out.push_str(&number_to_string(x));
72        }
73        Value::String(s) => write_string(out, s),
74        Value::Array(items) => {
75            out.push('[');
76            for (i, item) in items.iter().enumerate() {
77                if i > 0 {
78                    out.push(',');
79                }
80                write_value(out, item, order);
81            }
82            out.push(']');
83        }
84        Value::Object(map) => {
85            let mut keys: Vec<&String> = map.keys().collect();
86            match order {
87                KeyOrder::Sorted => keys.sort_by(|a, b| utf16_cmp(a, b)),
88                // Stable, so the other keys keep insertion order.
89                KeyOrder::Js => keys.sort_by_key(|k| js_key_rank(k)),
90            }
91            out.push('{');
92            for (i, k) in keys.iter().enumerate() {
93                if i > 0 {
94                    out.push(',');
95                }
96                write_string(out, k);
97                out.push(':');
98                write_value(out, &map[*k], order);
99            }
100            out.push('}');
101        }
102    }
103}
104
105/// [`js_json`] of `v`, appended to `out`. The streamed `.vctower` writer
106/// builds its text from several values this way (#1338).
107pub(crate) fn write_js_json(out: &mut String, v: &Value) {
108    write_value(out, v, KeyOrder::Js);
109}
110
111/// A string written as `JSON.stringify` writes it, appended to `out`.
112pub(crate) fn write_js_string(out: &mut String, s: &str) {
113    write_string(out, s);
114}
115
116/// The canonical text of a value: keys in UTF-16 code unit order, numbers and
117/// strings as JavaScript's `JSON.stringify` writes them.
118pub fn canonical_json(v: &Value) -> String {
119    let mut out = String::new();
120    write_value(&mut out, v, KeyOrder::Sorted);
121    out
122}
123
124#[doc(hidden)]
125/// `JSON.stringify` of the value as JavaScript would hold it: every map in
126/// insertion order (serde_json's `preserve_order`), except that keys that are
127/// array indices come first in numeric order, as in any JavaScript object.
128/// Numbers and strings are written as in [`canonical_json`]. This is the text
129/// the web game's writers compress, so the engine's `.vctower` matches it.
130pub fn js_json(v: &Value) -> String {
131    let mut out = String::new();
132    write_value(&mut out, v, KeyOrder::Js);
133    out
134}
135
136/// The first 16 hex digits of the SHA-256 of the value's canonical JSON. Two
137/// games with equal [state views](crate::snapshot::state_view) have equal
138/// digests.
139pub fn digest(v: &Value) -> String {
140    let hash = Sha256::digest(canonical_json(v).as_bytes());
141    let mut hex = String::with_capacity(16);
142    for byte in &hash[..8] {
143        hex.push_str(&format!("{:02x}", byte));
144    }
145    hex
146}
147
148#[cfg(test)]
149mod tests {
150    use super::*;
151    use serde_json::json;
152
153    #[test]
154    fn sorts_keys_by_utf16_units_at_every_depth() {
155        let v = json!({"b": 1, "a": {"10": 1, "9": 2, "Z": 3}});
156        assert_eq!(canonical_json(&v), r#"{"a":{"10":1,"9":2,"Z":3},"b":1}"#);
157    }
158
159    #[test]
160    fn js_order_puts_array_indices_first_then_insertion_order() {
161        let v: Value = serde_json::from_str(
162            r#"{"b":1,"10":2,"a":{"z":1,"y":2},"9":3,"01":4,"-1":5,"4294967295":6,"4294967294":7}"#,
163        )
164        .unwrap();
165        assert_eq!(
166            js_json(&v),
167            r#"{"9":3,"10":2,"4294967294":7,"b":1,"a":{"z":1,"y":2},"01":4,"-1":5,"4294967295":6}"#
168        );
169    }
170
171    #[test]
172    fn prints_numbers_as_js_does() {
173        let v = json!([-0.0, 0.1, 1e21, 1e-7, 123456789.125]);
174        assert_eq!(canonical_json(&v), "[0,0.1,1e+21,1e-7,123456789.125]");
175    }
176
177    #[test]
178    fn escapes_strings_as_json_stringify_does() {
179        let v = json!("\"\\/\u{8}\t\n\u{c}\r\u{1}\u{1f}\u{1F600}\u{7f}\u{2028}é");
180        assert_eq!(
181            canonical_json(&v),
182            "\"\\\"\\\\/\\b\\t\\n\\f\\r\\u0001\\u001f\u{1F600}\u{7f}\u{2028}é\""
183        );
184    }
185
186    #[test]
187    fn digest_is_sixteen_hex_digits_of_sha256() {
188        assert_eq!(digest(&json!({"a": 1})), "015abd7f5cc57a2d");
189    }
190}
verticopolis_engine/canonical.rs

verticopolis_engine/
canonical.rs
