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

sim_lib_scene/
diff.rs
