slop_ai/
diff.rs

1//! Recursive diff of two SLOP trees producing JSON Patch operations.
2//!
3//! Paths in generated ops use node IDs for children segments (not array indices),
4//! matching the SLOP patch convention.
5
6use crate::types::{PatchOp, PatchOpKind, SlopNode};
7
8/// RFC 6901 JSON Pointer escape for property-key segments.
9/// Node ID segments must not contain '/' or '~' and are not escaped.
10pub fn escape_pointer_segment(key: &str) -> String {
11    key.replace('~', "~0").replace('/', "~1")
12}
13
14/// Reverse of `escape_pointer_segment`.
15pub fn unescape_pointer_segment(segment: &str) -> String {
16    segment.replace("~1", "/").replace("~0", "~")
17}
18
19/// Recursively diff two trees and return patch operations.
20pub fn diff_nodes(old: &SlopNode, new: &SlopNode, base_path: &str) -> Vec<PatchOp> {
21    let mut ops = Vec::new();
22
23    // --- properties ---
24    diff_properties(old, new, base_path, &mut ops);
25
26    // --- affordances (replace entire list if changed) ---
27    let old_aff = old
28        .affordances
29        .as_ref()
30        .map(|a| serde_json::to_value(a).unwrap());
31    let new_aff = new
32        .affordances
33        .as_ref()
34        .map(|a| serde_json::to_value(a).unwrap());
35    if old_aff != new_aff {
36        match (&old_aff, &new_aff) {
37            (_, Some(val)) => ops.push(PatchOp {
38                op: if old_aff.is_some() {
39                    PatchOpKind::Replace
40                } else {
41                    PatchOpKind::Add
42                },
43                path: format!("{base_path}/affordances"),
44                value: Some(val.clone()),
45                index: None,
46            }),
47            (Some(_), None) => ops.push(PatchOp {
48                op: PatchOpKind::Remove,
49                path: format!("{base_path}/affordances"),
50                value: None,
51                index: None,
52            }),
53            (None, None) => {}
54        }
55    }
56
57    // --- meta (replace entire object if changed) ---
58    let old_meta = old.meta.as_ref().map(|m| serde_json::to_value(m).unwrap());
59    let new_meta = new.meta.as_ref().map(|m| serde_json::to_value(m).unwrap());
60    if old_meta != new_meta {
61        match (&old_meta, &new_meta) {
62            (_, Some(val)) => ops.push(PatchOp {
63                op: if old_meta.is_some() {
64                    PatchOpKind::Replace
65                } else {
66                    PatchOpKind::Add
67                },
68                path: format!("{base_path}/meta"),
69                value: Some(val.clone()),
70                index: None,
71            }),
72            (Some(_), None) => ops.push(PatchOp {
73                op: PatchOpKind::Remove,
74                path: format!("{base_path}/meta"),
75                value: None,
76                index: None,
77            }),
78            (None, None) => {}
79        }
80    }
81
82    // --- children (ordered; emit remove/add(index)/move to preserve order) ---
83    let old_children = old.children.as_deref().unwrap_or(&[]);
84    let new_children = new.children.as_deref().unwrap_or(&[]);
85
86    let old_ids: std::collections::HashMap<&str, &SlopNode> =
87        old_children.iter().map(|c| (c.id.as_str(), c)).collect();
88    let new_ids: std::collections::HashMap<&str, &SlopNode> =
89        new_children.iter().map(|c| (c.id.as_str(), c)).collect();
90
91    let mut working: Vec<String> = Vec::new();
92    for child in old_children {
93        if !new_ids.contains_key(child.id.as_str()) {
94            ops.push(PatchOp {
95                op: PatchOpKind::Remove,
96                path: format!("{base_path}/{}", child.id),
97                value: None,
98                index: None,
99            });
100        } else {
101            working.push(child.id.clone());
102        }
103    }
104
105    for (i, child) in new_children.iter().enumerate() {
106        if !old_ids.contains_key(child.id.as_str()) {
107            ops.push(PatchOp {
108                op: PatchOpKind::Add,
109                path: format!("{base_path}/{}", child.id),
110                value: Some(serde_json::to_value(child).unwrap()),
111                index: Some(i),
112            });
113            working.insert(i, child.id.clone());
114        }
115    }
116
117    for (i, child) in new_children.iter().enumerate() {
118        if working.get(i).map(String::as_str) == Some(child.id.as_str()) {
119            continue;
120        }
121        let current_idx = working.iter().position(|id| id == &child.id);
122        if let Some(ci) = current_idx {
123            ops.push(PatchOp {
124                op: PatchOpKind::Move,
125                path: format!("{base_path}/{}", child.id),
126                value: None,
127                index: Some(i),
128            });
129            let id = working.remove(ci);
130            working.insert(i, id);
131        }
132    }
133
134    for child in new_children {
135        if let Some(old_child) = old_ids.get(child.id.as_str()) {
136            let child_path = format!("{base_path}/{}", child.id);
137            ops.extend(diff_nodes(old_child, child, &child_path));
138        }
139    }
140
141    ops
142}
143
144fn diff_properties(old: &SlopNode, new: &SlopNode, base_path: &str, ops: &mut Vec<PatchOp>) {
145    let empty_map = serde_json::Map::new();
146    let old_props = old.properties.as_ref().unwrap_or(&empty_map);
147    let new_props = new.properties.as_ref().unwrap_or(&empty_map);
148
149    let mut all_keys: Vec<&String> = old_props.keys().chain(new_props.keys()).collect();
150    all_keys.sort();
151    all_keys.dedup();
152
153    for key in all_keys {
154        let old_val = old_props.get(key);
155        let new_val = new_props.get(key);
156        let esc = escape_pointer_segment(key);
157        match (old_val, new_val) {
158            (None, Some(v)) => ops.push(PatchOp {
159                op: PatchOpKind::Add,
160                path: format!("{base_path}/properties/{esc}"),
161                value: Some(v.clone()),
162                index: None,
163            }),
164            (Some(_), None) => ops.push(PatchOp {
165                op: PatchOpKind::Remove,
166                path: format!("{base_path}/properties/{esc}"),
167                value: None,
168                index: None,
169            }),
170            (Some(old_v), Some(new_v)) if old_v != new_v => ops.push(PatchOp {
171                op: PatchOpKind::Replace,
172                path: format!("{base_path}/properties/{esc}"),
173                value: Some(new_v.clone()),
174                index: None,
175            }),
176            _ => {}
177        }
178    }
179}
180
181#[cfg(test)]
182mod tests {
183    use super::*;
184    use crate::types::{Affordance, NodeMeta};
185    use serde_json::{json, Value};
186
187    fn node(id: &str) -> SlopNode {
188        SlopNode::new(id, "group")
189    }
190
191    fn node_with_props(id: &str, props: serde_json::Map<String, Value>) -> SlopNode {
192        SlopNode {
193            properties: Some(props),
194            ..SlopNode::new(id, "group")
195        }
196    }
197
198    fn props(pairs: Vec<(&str, Value)>) -> serde_json::Map<String, Value> {
199        pairs
200            .into_iter()
201            .map(|(k, v): (&str, Value)| (k.to_string(), v))
202            .collect()
203    }
204
205    #[test]
206    fn test_no_changes() {
207        let n = node_with_props("x", props(vec![("a", json!(1))]));
208        let ops = diff_nodes(&n, &n, "");
209        assert!(ops.is_empty());
210    }
211
212    #[test]
213    fn test_property_added() {
214        let old = node_with_props("x", props(vec![("a", json!(1))]));
215        let new = node_with_props("x", props(vec![("a", json!(1)), ("b", json!(2))]));
216        let ops = diff_nodes(&old, &new, "");
217        assert_eq!(ops.len(), 1);
218        assert_eq!(ops[0].op, PatchOpKind::Add);
219        assert_eq!(ops[0].path, "/properties/b");
220    }
221
222    #[test]
223    fn test_property_removed() {
224        let old = node_with_props("x", props(vec![("a", json!(1)), ("b", json!(2))]));
225        let new = node_with_props("x", props(vec![("a", json!(1))]));
226        let ops = diff_nodes(&old, &new, "");
227        assert_eq!(ops.len(), 1);
228        assert_eq!(ops[0].op, PatchOpKind::Remove);
229        assert_eq!(ops[0].path, "/properties/b");
230    }
231
232    #[test]
233    fn test_property_changed() {
234        let old = node_with_props("x", props(vec![("a", json!(1))]));
235        let new = node_with_props("x", props(vec![("a", json!(2))]));
236        let ops = diff_nodes(&old, &new, "");
237        assert_eq!(ops.len(), 1);
238        assert_eq!(ops[0].op, PatchOpKind::Replace);
239        assert_eq!(ops[0].value, Some(json!(2)));
240    }
241
242    #[test]
243    fn test_child_added() {
244        let old = SlopNode {
245            children: Some(vec![]),
246            ..node("x")
247        };
248        let child = node("c1");
249        let new = SlopNode {
250            children: Some(vec![child]),
251            ..node("x")
252        };
253        let ops = diff_nodes(&old, &new, "");
254        assert_eq!(ops.len(), 1);
255        assert_eq!(ops[0].op, PatchOpKind::Add);
256        assert_eq!(ops[0].path, "/c1");
257    }
258
259    #[test]
260    fn test_child_removed() {
261        let child = node("c1");
262        let old = SlopNode {
263            children: Some(vec![child]),
264            ..node("x")
265        };
266        let new = SlopNode {
267            children: Some(vec![]),
268            ..node("x")
269        };
270        let ops = diff_nodes(&old, &new, "");
271        assert_eq!(ops.len(), 1);
272        assert_eq!(ops[0].op, PatchOpKind::Remove);
273        assert_eq!(ops[0].path, "/c1");
274    }
275
276    #[test]
277    fn test_nested_diff() {
278        let old = SlopNode {
279            children: Some(vec![SlopNode {
280                children: Some(vec![node_with_props("b", props(vec![("x", json!(1))]))]),
281                ..node("a")
282            }]),
283            ..node("root")
284        };
285        let new = SlopNode {
286            children: Some(vec![SlopNode {
287                children: Some(vec![node_with_props("b", props(vec![("x", json!(2))]))]),
288                ..node("a")
289            }]),
290            ..node("root")
291        };
292        let ops = diff_nodes(&old, &new, "");
293        assert_eq!(ops.len(), 1);
294        assert_eq!(ops[0].path, "/a/b/properties/x");
295        assert_eq!(ops[0].value, Some(json!(2)));
296    }
297
298    #[test]
299    fn test_meta_changed() {
300        let old = SlopNode {
301            meta: Some(NodeMeta {
302                salience: Some(0.5),
303                ..NodeMeta::new()
304            }),
305            ..node("x")
306        };
307        let new = SlopNode {
308            meta: Some(NodeMeta {
309                salience: Some(0.9),
310                ..NodeMeta::new()
311            }),
312            ..node("x")
313        };
314        let ops = diff_nodes(&old, &new, "");
315        assert_eq!(ops.len(), 1);
316        assert_eq!(ops[0].op, PatchOpKind::Replace);
317        assert_eq!(ops[0].path, "/meta");
318    }
319
320    #[test]
321    fn test_affordances_changed() {
322        let old = SlopNode {
323            affordances: Some(vec![Affordance::new("open")]),
324            ..node("x")
325        };
326        let new = SlopNode {
327            affordances: Some(vec![Affordance::new("open"), Affordance::new("delete")]),
328            ..node("x")
329        };
330        let ops = diff_nodes(&old, &new, "");
331        assert_eq!(ops.len(), 1);
332        assert_eq!(ops[0].op, PatchOpKind::Replace);
333        assert_eq!(ops[0].path, "/affordances");
334    }
335}
slop_ai/diff.rs

slop_ai/
diff.rs
