sim_lib_scene/
diff.rs

1//! Scene diff and patch application.
2//!
3//! A scene diff is itself a scene value (a `scene/patch` node), so it can be
4//! snapshotted, sent over the wire, or replayed like any other Scene. [`diff`]
5//! produces a patch that records the minimal set-and-remove operations turning
6//! `old` into `new`; [`apply`] replays a patch onto a scene. The contract is
7//! exactness: `apply(old, diff(old, new))` reconstructs `new` exactly.
8//!
9//! The diff descends through equal-length sequences and through map keys, so
10//! moving or editing one node re-emits only that node. Length-changing
11//! sequences and type changes fall back to a whole-value set at that path,
12//! which still reconstructs exactly. Maps whose keys are REORDERED (the same
13//! keys in a new order) also fall back to a whole-value set: a key-matched
14//! descent emits no ops for a pure reorder, yet `apply` preserves the old key
15//! order, so a fallback is required for `apply(old, diff(old,new)) == new` to
16//! hold exactly. Path addressing (the `k`/`i` wire form and the
17//! navigate/set/remove logic) is the shared `sim_value::path` primitive.
18
19use sim_kernel::{Error, Expr, Result, Symbol};
20use sim_value::path::{Path, PathError, Segment, remove_at, set_at};
21
22use crate::model::node;
23
24const OP_KEY: &str = "op";
25const PATH_KEY: &str = "path";
26const VALUE_KEY: &str = "value";
27const OPS_KEY: &str = "ops";
28const OP_SET: &str = "set";
29const OP_REMOVE: &str = "remove";
30
31enum Op {
32    Set { path: Path, value: Expr },
33    Remove { path: Path },
34}
35
36/// Build the patch that turns `old` into `new`.
37pub fn diff(old: &Expr, new: &Expr) -> Expr {
38    let mut ops = Vec::new();
39    diff_value(old, new, &mut Path::new(), &mut ops);
40    let op_exprs = ops.into_iter().map(op_to_expr).collect();
41    node("patch", vec![(OPS_KEY, Expr::List(op_exprs))])
42}
43
44/// Apply `patch` to `scene`, returning the reconstructed scene.
45pub fn apply(scene: &Expr, patch: &Expr) -> Result<Expr> {
46    let ops = parse_ops(patch)?;
47    let mut result = scene.clone();
48    for op in ops {
49        result = match op {
50            Op::Set { path, value } => set_at(&result, &path, value).map_err(map_path_error)?,
51            Op::Remove { path } => remove_at(&result, &path).map_err(map_path_error)?,
52        };
53    }
54    Ok(result)
55}
56
57fn diff_value(old: &Expr, new: &Expr, path: &mut Path, ops: &mut Vec<Op>) {
58    // Compare STRUCTURALLY, not with `==`: `Expr`'s equality is canonical and
59    // ignores map key order, which would hide a pure reorder from the differ and
60    // leave `apply` reconstructing the old order.
61    if structural_eq(old, new) {
62        return;
63    }
64    match (old, new) {
65        (Expr::Map(old_entries), Expr::Map(new_entries)) => {
66            // A pure key reorder (same keys, new order) yields zero per-key ops
67            // but `apply` would keep the old order. Re-emit the whole map so the
68            // new order is reconstructed exactly.
69            if same_keys_reordered(old_entries, new_entries) {
70                ops.push(Op::Set {
71                    path: path.clone(),
72                    value: new.clone(),
73                });
74                return;
75            }
76            for (key, old_value) in old_entries {
77                match find_value(new_entries, key) {
78                    Some(new_value) => {
79                        path.0.push(Segment::Key(key.clone()));
80                        diff_value(old_value, new_value, path, ops);
81                        path.0.pop();
82                    }
83                    None => {
84                        path.0.push(Segment::Key(key.clone()));
85                        ops.push(Op::Remove { path: path.clone() });
86                        path.0.pop();
87                    }
88                }
89            }
90            for (key, new_value) in new_entries {
91                if find_value(old_entries, key).is_none() {
92                    path.0.push(Segment::Key(key.clone()));
93                    ops.push(Op::Set {
94                        path: path.clone(),
95                        value: new_value.clone(),
96                    });
97                    path.0.pop();
98                }
99            }
100        }
101        (Expr::List(old_items), Expr::List(new_items))
102        | (Expr::Vector(old_items), Expr::Vector(new_items))
103        | (Expr::Set(old_items), Expr::Set(new_items))
104            if old_items.len() == new_items.len() =>
105        {
106            for (index, (old_item, new_item)) in old_items.iter().zip(new_items).enumerate() {
107                path.0.push(Segment::Index(index));
108                diff_value(old_item, new_item, path, ops);
109                path.0.pop();
110            }
111        }
112        _ => ops.push(Op::Set {
113            path: path.clone(),
114            value: new.clone(),
115        }),
116    }
117}
118
119fn find_value<'a>(entries: &'a [(Expr, Expr)], key: &Expr) -> Option<&'a Expr> {
120    entries
121        .iter()
122        .find_map(|(entry_key, value)| (entry_key == key).then_some(value))
123}
124
125/// Order-sensitive equality. Unlike `Expr::eq` (canonical, which ignores map
126/// key order and set/sequence ordering), this treats a reordering as a
127/// difference, so the differ can reconstruct the EXACT structure of `new`.
128fn structural_eq(a: &Expr, b: &Expr) -> bool {
129    match (a, b) {
130        (Expr::Map(ae), Expr::Map(be)) => {
131            ae.len() == be.len()
132                && ae
133                    .iter()
134                    .zip(be)
135                    .all(|((ak, av), (bk, bv))| structural_eq(ak, bk) && structural_eq(av, bv))
136        }
137        (Expr::List(ai), Expr::List(bi))
138        | (Expr::Vector(ai), Expr::Vector(bi))
139        | (Expr::Set(ai), Expr::Set(bi)) => {
140            ai.len() == bi.len() && ai.iter().zip(bi).all(|(x, y)| structural_eq(x, y))
141        }
142        _ => a == b,
143    }
144}
145
146/// True when `old` and `new` carry exactly the same keys (as a set) but in a
147/// different order. Add/remove cases (different key sets) are left to the
148/// per-key set/remove loops, which reconstruct exactly for them.
149fn same_keys_reordered(old: &[(Expr, Expr)], new: &[(Expr, Expr)]) -> bool {
150    if old.len() != new.len() {
151        return false;
152    }
153    let order_differs = old
154        .iter()
155        .zip(new)
156        .any(|((old_key, _), (new_key, _))| old_key != new_key);
157    if !order_differs {
158        return false;
159    }
160    // Same length and order differs: confirm the key SETS match (otherwise it is
161    // an add+remove of equal count, handled by the per-key loops).
162    old.iter()
163        .all(|(old_key, _)| find_value(new, old_key).is_some())
164        && new
165            .iter()
166            .all(|(new_key, _)| find_value(old, new_key).is_some())
167}
168
169fn patch_error(message: &str) -> Error {
170    Error::HostError(format!("scene patch apply error: {message}"))
171}
172
173fn map_path_error(error: PathError) -> Error {
174    Error::HostError(format!("scene patch apply error: {error:?}"))
175}
176
177fn op_to_expr(op: Op) -> Expr {
178    let mut entries = Vec::new();
179    match op {
180        Op::Set { path, value } => {
181            entries.push(sym_entry(OP_KEY, Expr::Symbol(Symbol::new(OP_SET))));
182            entries.push(sym_entry(PATH_KEY, path.to_expr()));
183            entries.push(sym_entry(VALUE_KEY, value));
184        }
185        Op::Remove { path } => {
186            entries.push(sym_entry(OP_KEY, Expr::Symbol(Symbol::new(OP_REMOVE))));
187            entries.push(sym_entry(PATH_KEY, path.to_expr()));
188        }
189    }
190    Expr::Map(entries)
191}
192
193fn sym_entry(key: &str, value: Expr) -> (Expr, Expr) {
194    (Expr::Symbol(Symbol::new(key)), value)
195}
196
197fn parse_ops(patch: &Expr) -> Result<Vec<Op>> {
198    let Expr::Map(entries) = patch else {
199        return Err(patch_error("patch is not a map"));
200    };
201    let ops_expr = find_value(entries, &Expr::Symbol(Symbol::new(OPS_KEY)))
202        .ok_or_else(|| patch_error("patch is missing an 'ops' entry"))?;
203    let Expr::List(op_exprs) = ops_expr else {
204        return Err(patch_error("patch 'ops' is not a list"));
205    };
206    op_exprs.iter().map(parse_op).collect()
207}
208
209fn parse_op(op: &Expr) -> Result<Op> {
210    let Expr::Map(entries) = op else {
211        return Err(patch_error("op is not a map"));
212    };
213    let op_name = match find_value(entries, &Expr::Symbol(Symbol::new(OP_KEY))) {
214        Some(Expr::Symbol(symbol)) => symbol.name.clone(),
215        _ => return Err(patch_error("op is missing an 'op' symbol")),
216    };
217    let path = match find_value(entries, &Expr::Symbol(Symbol::new(PATH_KEY))) {
218        Some(path_expr) => Path::from_expr(path_expr).map_err(map_path_error)?,
219        None => return Err(patch_error("op is missing a 'path'")),
220    };
221    match &*op_name {
222        OP_SET => {
223            let value = find_value(entries, &Expr::Symbol(Symbol::new(VALUE_KEY)))
224                .ok_or_else(|| patch_error("set op is missing a 'value'"))?
225                .clone();
226            Ok(Op::Set { path, value })
227        }
228        OP_REMOVE => Ok(Op::Remove { path }),
229        other => Err(patch_error(&format!("unknown op '{other}'"))),
230    }
231}
sim_lib_scene/diff.rs

sim_lib_scene/
diff.rs
