Skip to main content

byob_protocol/tree/
diff.rs

1//! Engine-side diff: a plugin may always send its whole view; clients get the patches that
2//! turn the old tree into the new one (JSON-pointer puts, appends, removes, row writes).
3
4use serde::Serialize;
5use serde_json::Value;
6
7use super::{Kind, Node, Patch, Target, pointer_segment};
8
9/// Changed rows of one table written as single puts; more become one `rows` patch.
10const ROW_PUTS: usize = 64;
11
12/// Patches that turn `old` into `new` (`apply(old, diff(old, new))` gives `new`); none if
13/// they are equal.
14pub fn diff(old: &Node, new: &Node) -> Vec<Patch> {
15    let mut out = Vec::new();
16    node(old, new, &mut String::new(), &mut out);
17    out
18}
19
20fn put(path: &str, field: &str, v: &impl Serialize, out: &mut Vec<Patch>) {
21    let path = if field.is_empty() { path.to_owned() } else { format!("{path}/{field}") };
22    out.push(Patch::Put { path, value: serde_json::to_value(v).unwrap_or(Value::Null) });
23}
24
25fn node(a: &Node, b: &Node, path: &mut String, out: &mut Vec<Patch>) {
26    if a == b {
27        return;
28    }
29    if a.key != b.key || a.type_name() != b.type_name() {
30        return put(path, "", b, out);
31    }
32    match (&a.kind, &b.kind) {
33        (Kind::Column { children: x }, Kind::Column { children: y }) | (Kind::Row { children: x }, Kind::Row { children: y }) => children(x, y, path, out),
34        (Kind::Card { title: t1, children: x }, Kind::Card { title: t2, children: y }) => {
35            if t1 != t2 {
36                put(path, "title", t2, out);
37            }
38            children(x, y, path, out);
39        }
40        (Kind::Table { name: n1, columns: c1, rows: r1, height: h1, select: s1 }, Kind::Table { name: n2, columns: c2, rows: r2, height: h2, select: s2 }) => {
41            if n1 != n2 {
42                put(path, "name", n2, out);
43            }
44            if c1 != c2 {
45                put(path, "columns", c2, out);
46            }
47            if h1 != h2 {
48                put(path, "height", h2, out);
49            }
50            if s1 != s2 {
51                put(path, "select", s2, out);
52            }
53            rows(r1, r2, path, out);
54        }
55        (Kind::Canvas { width: w1, height: h1, shapes: s1, action: a1 }, Kind::Canvas { width: w2, height: h2, shapes: s2, action: a2 }) => {
56            if w1 != w2 {
57                put(path, "width", w2, out);
58            }
59            if h1 != h2 {
60                put(path, "height", h2, out);
61            }
62            if a1 != a2 {
63                put(path, "action", a2, out);
64            }
65            if s1.len() == s2.len() {
66                for (i, (x, y)) in s1.iter().zip(s2).enumerate() {
67                    if x != y {
68                        put(path, &format!("shapes/{i}"), y, out);
69                    }
70                }
71            } else {
72                put(path, "shapes", s2, out);
73            }
74        }
75        (Kind::Grid { blocks: x, .. }, Kind::Grid { blocks: y, .. }) => {
76            // The small fields as for a leaf (without the blocks), then the blocks that changed.
77            let strip = |n: &Node| {
78                let mut v = serde_json::to_value(Node { key: n.key.clone(), kind: small_grid(&n.kind) }).unwrap_or(Value::Null);
79                if let Value::Object(o) = &mut v {
80                    o.remove("blocks");
81                }
82                v
83            };
84            match (strip(a), strip(b)) {
85                (Value::Object(p), Value::Object(q)) => {
86                    for (k, v) in &q {
87                        if p.get(k) != Some(v) {
88                            put(path, &pointer_segment(k), v, out);
89                        }
90                    }
91                    for k in p.keys() {
92                        if !q.contains_key(k) {
93                            // Back to its default.
94                            let default = match k.as_str() {
95                                "headers" => Value::Bool(true),
96                                "editable" => Value::Bool(false),
97                                "frozen_rows" | "frozen_cols" => Value::from(0),
98                                "widths" => Value::Object(serde_json::Map::new()),
99                                "name" => Value::String(String::new()),
100                                _ => Value::Null,
101                            };
102                            put(path, &pointer_segment(k), &default, out);
103                        }
104                    }
105                }
106                _ => return put(path, "", b, out),
107            }
108            if x.len() == y.len() {
109                for (i, (p, q)) in x.iter().zip(y).enumerate() {
110                    if p != q {
111                        put(path, &format!("blocks/{i}"), q, out);
112                    }
113                }
114            } else {
115                put(path, "blocks", y, out);
116            }
117        }
118        _ => leaf(a, b, path, out),
119    }
120}
121
122/// A grid without its blocks (the rest is small).
123fn small_grid(k: &Kind) -> Kind {
124    match k {
125        Kind::Grid { name, rows, cols, frozen_rows, frozen_cols, widths, default_width, editable, headers, height, selection, .. } => Kind::Grid {
126            name: name.clone(),
127            rows: *rows,
128            cols: *cols,
129            blocks: Vec::new(),
130            frozen_rows: *frozen_rows,
131            frozen_cols: *frozen_cols,
132            widths: widths.clone(),
133            default_width: *default_width,
134            editable: *editable,
135            headers: *headers,
136            height: *height,
137            selection: *selection,
138        },
139        other => other.clone(),
140    }
141}
142
143/// Small nodes: the fields that changed, or the whole node if fields came or went.
144fn leaf(a: &Node, b: &Node, path: &str, out: &mut Vec<Patch>) {
145    match (serde_json::to_value(a), serde_json::to_value(b)) {
146        (Ok(Value::Object(x)), Ok(Value::Object(y))) if x.len() == y.len() && x.keys().all(|k| y.contains_key(k)) => {
147            for (k, v) in &y {
148                if x.get(k) != Some(v) {
149                    put(path, &pointer_segment(k), v, out);
150                }
151            }
152        }
153        _ => put(path, "", b, out),
154    }
155}
156
157fn children(x: &[Node], y: &[Node], path: &mut String, out: &mut Vec<Patch>) {
158    let at = path.len();
159    if x.len() == y.len() {
160        for (i, (a, b)) in x.iter().zip(y).enumerate() {
161            path.push_str(&format!("/children/{i}"));
162            node(a, b, path, out);
163            path.truncate(at);
164        }
165        return;
166    }
167    // Added at the end.
168    if y.len() > x.len() && y.get(..x.len()) == Some(x) {
169        out.push(Patch::Append { at: Target::path(path.as_str()), nodes: y.get(x.len()..).unwrap_or_default().to_vec() });
170        return;
171    }
172    // One removed.
173    if x.len() == y.len() + 1 {
174        let i = x.iter().zip(y).position(|(a, b)| a != b).unwrap_or(y.len());
175        if x.get(i + 1..) == y.get(i..) {
176            out.push(Patch::Remove { at: Target::path(format!("{path}/children/{i}")) });
177            return;
178        }
179    }
180    put(path, "children", &y, out);
181}
182
183fn rows(x: &[Vec<Value>], y: &[Vec<Value>], path: &str, out: &mut Vec<Patch>) {
184    let common = x.len().min(y.len());
185    let changed: Vec<usize> = (0..common).filter(|&i| x.get(i) != y.get(i)).collect();
186    let resized = x.len() != y.len();
187    if changed.len() > ROW_PUTS {
188        let first = changed.first().copied().unwrap_or(0);
189        let rows = y.get(first..).unwrap_or_default().to_vec();
190        out.push(Patch::Rows { at: Target::path(path), start: first, rows, len: resized.then_some(y.len()) });
191        return;
192    }
193    for i in changed {
194        let (Some(a), Some(b)) = (x.get(i), y.get(i)) else { continue };
195        let cells: Vec<usize> = (0..b.len()).filter(|&j| a.get(j) != b.get(j)).collect();
196        if a.len() == b.len() && cells.len() * 2 <= b.len() {
197            for j in cells {
198                put(path, &format!("rows/{i}/{j}"), &b.get(j), out);
199            }
200        } else {
201            put(path, &format!("rows/{i}"), b, out);
202        }
203    }
204    if resized {
205        out.push(Patch::Rows { at: Target::path(path), start: common, rows: y.get(common..).unwrap_or_default().to_vec(), len: Some(y.len()) });
206    }
207}