manabrew_relay_protocol/
state_delta.rs

1use serde_json::{Map, Value};
2
3const LITERAL: &str = "$v";
4const KEYED: &str = "$k";
5const REMOVED: &str = "$d";
6const ORDER: &str = "$o";
7
8/// Stable key for an element of a keyed array. Cards carry `id`; zone entries
9/// carry `zone` plus `ownerId` and no id of their own, so a plain merge patch
10/// would replace the whole zone list whenever one card moved.
11fn element_key(value: &Value) -> Option<String> {
12    let object = value.as_object()?;
13    if let Some(id) = object.get("id").and_then(Value::as_str) {
14        return Some(id.to_string());
15    }
16    match (
17        object.get("zone").and_then(Value::as_str),
18        object.get("ownerId").and_then(Value::as_str),
19    ) {
20        (Some(zone), Some(owner)) => Some(format!("{zone}/{owner}")),
21        _ => None,
22    }
23}
24
25fn keyed_elements(values: &[Value]) -> Option<Vec<(String, &Value)>> {
26    let mut keys = Vec::with_capacity(values.len());
27    for value in values {
28        keys.push((element_key(value)?, value));
29    }
30    let mut seen: Vec<&str> = keys.iter().map(|(k, _)| k.as_str()).collect();
31    seen.sort_unstable();
32    let unique = seen.len();
33    seen.dedup();
34    (seen.len() == unique).then_some(keys)
35}
36
37fn find<'a>(entries: &'a [(String, &'a Value)], key: &str) -> Option<&'a Value> {
38    entries.iter().find_map(|(k, v)| (k == key).then_some(*v))
39}
40
41/// Patch turning `previous` into `next`, or `None` when they are equal.
42///
43/// A patch that is not an object is a literal replacement, so `null` and arrays
44/// survive without a delete sentinel colliding with real null fields.
45pub fn diff(previous: &Value, next: &Value) -> Option<Value> {
46    if previous == next {
47        return None;
48    }
49    match (previous, next) {
50        (Value::Object(before), Value::Object(after)) => {
51            let mut patch = Map::new();
52            for (key, value) in after {
53                match before.get(key) {
54                    Some(old) => {
55                        if let Some(inner) = diff(old, value) {
56                            patch.insert(key.clone(), inner);
57                        }
58                    }
59                    None => {
60                        patch.insert(key.clone(), literal(value));
61                    }
62                }
63            }
64            let removed: Vec<Value> = before
65                .keys()
66                .filter(|key| !after.contains_key(*key))
67                .map(|key| Value::String(key.clone()))
68                .collect();
69            if !removed.is_empty() {
70                patch.insert(REMOVED.to_string(), Value::Array(removed));
71            }
72            Some(Value::Object(patch))
73        }
74        (Value::Array(before), Value::Array(after)) => {
75            match (keyed_elements(before), keyed_elements(after)) {
76                (Some(before_keyed), Some(after_keyed)) => {
77                    Some(keyed_diff(&before_keyed, &after_keyed))
78                }
79                _ => Some(literal(next)),
80            }
81        }
82        _ => Some(literal(next)),
83    }
84}
85
86fn keyed_diff(before: &[(String, &Value)], after: &[(String, &Value)]) -> Value {
87    let mut changed = Map::new();
88    for (key, value) in after {
89        match find(before, key) {
90            Some(old) => {
91                if let Some(inner) = diff(old, value) {
92                    changed.insert(key.clone(), inner);
93                }
94            }
95            None => {
96                changed.insert(key.clone(), literal(value));
97            }
98        }
99    }
100    let removed: Vec<Value> = before
101        .iter()
102        .filter(|(key, _)| find(after, key).is_none())
103        .map(|(key, _)| Value::String(key.clone()))
104        .collect();
105
106    let mut patch = Map::new();
107    if !changed.is_empty() {
108        patch.insert(KEYED.to_string(), Value::Object(changed));
109    }
110    if !removed.is_empty() {
111        patch.insert(REMOVED.to_string(), Value::Array(removed));
112    }
113    let before_order: Vec<&str> = before.iter().map(|(k, _)| k.as_str()).collect();
114    let after_order: Vec<&str> = after.iter().map(|(k, _)| k.as_str()).collect();
115    if before_order != after_order {
116        patch.insert(
117            ORDER.to_string(),
118            Value::Array(
119                after_order
120                    .iter()
121                    .map(|k| Value::String((*k).into()))
122                    .collect(),
123            ),
124        );
125    } else if patch.is_empty() {
126        patch.insert(KEYED.to_string(), Value::Object(Map::new()));
127    }
128    Value::Object(patch)
129}
130
131/// Wrap a value that must replace rather than merge.
132fn literal(value: &Value) -> Value {
133    match value {
134        Value::Object(_) => {
135            let mut wrapper = Map::new();
136            wrapper.insert(LITERAL.to_string(), value.clone());
137            Value::Object(wrapper)
138        }
139        other => other.clone(),
140    }
141}
142
143fn is_keyed_patch(patch: &Map<String, Value>) -> bool {
144    patch.contains_key(KEYED) || patch.contains_key(ORDER)
145}
146
147/// Apply a patch produced by [`diff`].
148pub fn apply(previous: &Value, patch: &Value) -> Value {
149    let Value::Object(fields) = patch else {
150        return patch.clone();
151    };
152    if let Some(value) = fields.get(LITERAL) {
153        return value.clone();
154    }
155    if is_keyed_patch(fields) {
156        return apply_keyed(previous, fields);
157    }
158    let mut result = previous.as_object().cloned().unwrap_or_default();
159    if let Some(Value::Array(removed)) = fields.get(REMOVED) {
160        for key in removed.iter().filter_map(Value::as_str) {
161            result.remove(key);
162        }
163    }
164    for (key, inner) in fields {
165        if key == REMOVED {
166            continue;
167        }
168        let base = result.get(key).cloned().unwrap_or(Value::Null);
169        result.insert(key.clone(), apply(&base, inner));
170    }
171    Value::Object(result)
172}
173
174fn apply_keyed(previous: &Value, fields: &Map<String, Value>) -> Value {
175    let empty = Vec::new();
176    let before = previous.as_array().unwrap_or(&empty);
177    let mut order: Vec<String> = Vec::with_capacity(before.len());
178    let mut elements: Vec<(String, Value)> = Vec::with_capacity(before.len());
179    for value in before {
180        let key = element_key(value).unwrap_or_default();
181        order.push(key.clone());
182        elements.push((key, value.clone()));
183    }
184    if let Some(Value::Array(removed)) = fields.get(REMOVED) {
185        for key in removed.iter().filter_map(Value::as_str) {
186            elements.retain(|(k, _)| k != key);
187            order.retain(|k| k != key);
188        }
189    }
190    if let Some(Value::Object(changed)) = fields.get(KEYED) {
191        for (key, inner) in changed {
192            match elements.iter_mut().find(|(k, _)| k == key) {
193                Some((_, value)) => *value = apply(value, inner),
194                None => {
195                    elements.push((key.clone(), apply(&Value::Null, inner)));
196                    order.push(key.clone());
197                }
198            }
199        }
200    }
201    if let Some(Value::Array(new_order)) = fields.get(ORDER) {
202        order = new_order
203            .iter()
204            .filter_map(Value::as_str)
205            .map(str::to_string)
206            .collect();
207    }
208    let mut result = Vec::with_capacity(order.len());
209    for key in &order {
210        if let Some((_, value)) = elements.iter().find(|(k, _)| k == key) {
211            result.push(value.clone());
212        }
213    }
214    Value::Array(result)
215}
216
217/// Content fingerprint used to detect a client applying a patch to the wrong
218/// base. FNV-1a over key-sorted JSON so the node and the client agree without
219/// depending on map iteration order.
220pub fn fingerprint(state: &Value) -> String {
221    let mut canonical = String::new();
222    write_canonical(state, &mut canonical);
223    let mut hash: u64 = 0xcbf2_9ce4_8422_2325;
224    for byte in canonical.as_bytes() {
225        hash ^= u64::from(*byte);
226        hash = hash.wrapping_mul(0x0000_0100_0000_01b3);
227    }
228    format!("{hash:016x}")
229}
230
231fn write_canonical(value: &Value, out: &mut String) {
232    match value {
233        Value::Object(map) => {
234            let mut keys: Vec<&String> = map.keys().collect();
235            keys.sort_unstable();
236            out.push('{');
237            for (index, key) in keys.iter().enumerate() {
238                if index > 0 {
239                    out.push(',');
240                }
241                out.push_str(&Value::String((*key).clone()).to_string());
242                out.push(':');
243                write_canonical(&map[*key], out);
244            }
245            out.push('}');
246        }
247        Value::Array(items) => {
248            out.push('[');
249            for (index, item) in items.iter().enumerate() {
250                if index > 0 {
251                    out.push(',');
252                }
253                write_canonical(item, out);
254            }
255            out.push(']');
256        }
257        other => out.push_str(&other.to_string()),
258    }
259}
260
261#[cfg(test)]
262mod tests {
263    use super::*;
264    use serde_json::json;
265
266    fn round_trip(before: Value, after: Value) {
267        match diff(&before, &after) {
268            Some(patch) => assert_eq!(apply(&before, &patch), after, "patch {patch}"),
269            None => assert_eq!(before, after),
270        }
271    }
272
273    #[test]
274    fn null_fields_survive() {
275        round_trip(
276            json!({"power": 2, "toughness": null}),
277            json!({"power": null, "toughness": 3}),
278        );
279    }
280
281    #[test]
282    fn removed_fields_are_explicit() {
283        round_trip(json!({"a": 1, "b": 2}), json!({"a": 1}));
284    }
285
286    #[test]
287    fn card_moving_zones_does_not_resend_the_battlefield() {
288        let before = json!({"zones": [
289            {"zone": "battlefield", "ownerId": "player-0", "count": 2, "cards": [
290                {"id": "c1", "tapped": false, "text": "a long rules text"},
291                {"id": "c2", "tapped": false, "text": "another long rules text"}]},
292            {"zone": "graveyard", "ownerId": "player-0", "count": 0, "cards": []}]});
293        let mut after = before.clone();
294        after["zones"][0]["cards"][1]["tapped"] = json!(true);
295        let patch = diff(&before, &after).expect("changed");
296        assert_eq!(apply(&before, &patch), after);
297        let encoded = patch.to_string();
298        assert!(
299            !encoded.contains("long rules text"),
300            "resent card text: {encoded}"
301        );
302        assert!(encoded.len() < 120, "patch larger than expected: {encoded}");
303    }
304
305    #[test]
306    fn reordering_is_carried() {
307        let before = json!([{"id": "a"}, {"id": "b"}, {"id": "c"}]);
308        let after = json!([{"id": "c"}, {"id": "a"}]);
309        round_trip(before, after);
310    }
311
312    #[test]
313    fn arrays_without_stable_keys_are_replaced() {
314        round_trip(
315            json!({"types": ["Land"]}),
316            json!({"types": ["Creature", "Artifact"]}),
317        );
318    }
319
320    #[test]
321    fn object_replacing_a_scalar_is_literal() {
322        round_trip(json!({"a": 1}), json!({"a": {"b": 2}}));
323    }
324
325    #[test]
326    fn fingerprint_ignores_key_order() {
327        assert_eq!(
328            fingerprint(&json!({"a": 1, "b": {"c": 2, "d": 3}})),
329            fingerprint(&json!({"b": {"d": 3, "c": 2}, "a": 1}))
330        );
331    }
332
333    /// Round-trips every consecutive pair of a recorded production game.
334    /// Point `STATE_DELTA_FIXTURE` at a JSON array of state sequences; the
335    /// capture holds player data, so no fixture is checked in.
336    #[test]
337    fn recorded_states_round_trip() {
338        let Ok(path) = std::env::var("STATE_DELTA_FIXTURE") else {
339            return;
340        };
341        let raw = std::fs::read_to_string(path).expect("fixture");
342        let sequences: Vec<Vec<Value>> = serde_json::from_str(&raw).expect("fixture json");
343        let (mut full, mut delta, mut pairs) = (0usize, 0usize, 0usize);
344        let mut worst = 0usize;
345        for sequence in &sequences {
346            for pair in sequence.windows(2) {
347                let patch = diff(&pair[0], &pair[1]);
348                let rebuilt = match &patch {
349                    Some(patch) => apply(&pair[0], patch),
350                    None => pair[0].clone(),
351                };
352                assert_eq!(rebuilt, pair[1], "delta did not reproduce the state");
353                let size = patch.map_or(2, |p| p.to_string().len());
354                full += pair[1].to_string().len();
355                delta += size;
356                worst = worst.max(size);
357                pairs += 1;
358            }
359        }
360        println!(
361            "pairs {pairs}: full {:.1}MB, delta {:.1}MB, {:.0}x smaller, worst patch {worst}B",
362            full as f64 / 1e6,
363            delta as f64 / 1e6,
364            full as f64 / delta.max(1) as f64
365        );
366    }
367
368    #[test]
369    fn fingerprint_separates_different_states() {
370        assert_ne!(fingerprint(&json!({"a": 1})), fingerprint(&json!({"a": 2})));
371    }
372}
manabrew_relay_protocol/state_delta.rs

manabrew_relay_protocol/
state_delta.rs
