lib/ui/src/tree/splice.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const arrange = @import("arrange");
3
4 const abi = @import("../abi/root.zig");
5 const capacity_mod = @import("capacity.zig");
6 const map_mod = @import("map.zig");
7 const survey_mod = @import("survey.zig");
8 const view_mod = @import("view.zig");
9
10 const Capacity = capacity_mod.Capacity;
11 const Map = map_mod.Map;
12 const Node = abi.Node;
13 const Report = survey_mod.Report;
14 const Retained = survey_mod.Retained;
15 const View = view_mod.View;
16
17 /// `Scratch` holds the work arrays for a splice, which writes a new preorder node array in the
18 /// order of the flat tree. While the splice emits nodes, `Scratch.place` maps publish indices to
19 /// written indices. After the emit and trailer phases, the splice reuses that slice for the
20 /// compact dirty index list, which `Store.dirty` returns as new preorder indices. After the
21 /// splice, `Scratch.dirty` holds one packed prior entry per written node: the low 31 bits name
22 /// the node's index in the previously retained tree, the high bit says its revision changed or
23 /// its id is new, and all low bits set means there was no retained node. The correspondence
24 /// describes only the immediately preceding retained tree, and remains valid until the next
25 /// publish modifies the scratch arrays.
26 pub const Scratch = struct {
27 place: []u32,
28 atom_remap: []u32,
29 text_remap: []u32,
30 dirty: []u32,
31 };
32
33 pub const Outcome = struct {
34 /// `Outcome.bytes` is the length of the envelope written into the block. It is the publish
35 /// buffer's length when no node carries the `retained` flag, and the full block size otherwise.
36 bytes: u32 = 0,
37 /// `Outcome.dirty` is the number of indices written to the beginning of `Scratch.place`,
38 /// each naming a dirty node's position in the newly written preorder node array.
39 dirty: u32 = 0,
40 };
41
42 /// `unbound` marks a remap entry that has no copy yet.
43 pub const unbound: u32 = std.math.maxInt(u32);
44 pub const prior_dirty: u32 = 0x8000_0000;
45 pub const prior_absent: u32 = 0x7fff_ffff;
46
47 fn packedPrior(old: ?u32, dirty: bool) u32 {
48 const index = old orelse prior_absent;
49 return index | (if (dirty) prior_dirty else @as(u32, 0));
50 }
51
52 fn collectDirty(place: []u32, prior: []const u32) u32 {
53 var count: u32 = 0;
54 for (prior, 0..) |entry, at| {
55 if (entry & prior_dirty == 0) continue;
56 place[count] = @intCast(at);
57 count += 1;
58 }
59 return count;
60 }
61
62 const Frame = struct {
63 last: u32,
64 slot: u32,
65 };
66
67 /// `splice` is exported as `tree.graft`. It writes an accepted publish into `block` and leaves
68 /// `block_map` indexing the written nodes. It takes the `Report` that `admit` returned for that
69 /// publish and the same `Retained`. When no node carries the `retained` flag, it copies the
70 /// publish bytes whole and keeps the map `admit` filled, so `block_map` must be that map. It marks
71 /// dirty each node whose id the retained tree lacks or holds at another revision, and skips the
72 /// descendants of a node whose revision matches. Otherwise it rebuilds the tree. It copies the
73 /// publish tables, replaces each placeholder with the retained subtree of the same id, copies that
74 /// subtree's declarations, classes, atoms, texts, and runs with their indices remapped, and
75 /// rebuilds `block_map`. It marks dirty each other node whose id the retained tree lacks or holds
76 /// at another revision, and never a node of a retained subtree. It returns no error, because
77 /// `admit` already checked every bound.
78 pub fn splice(
79 block: []align(8) u8,
80 block_map: *Map,
81 capacity: Capacity,
82 report: Report,
83 retained: Retained,
84 scratch: Scratch,
85 ) Outcome {
86 if (!report.reuses_retained) return bulk(block, block_map, report.view, retained, scratch);
87 var sink = Sink{
88 .block = block,
89 .capacity = capacity,
90 .atom_remap = scratch.atom_remap,
91 .text_remap = scratch.text_remap,
92 };
93 return rebuild(&sink, block_map, report.view, retained, scratch);
94 }
95
96 fn bulk(
97 block: []align(8) u8,
98 block_map: *Map,
99 view: View,
100 retained: Retained,
101 scratch: Scratch,
102 ) Outcome {
103 const length: u32 = @intCast(view.bytes.len);
104 std.debug.assert(length <= block.len);
105 std.debug.assert(block_map.count == view.nodes.len);
106 @memcpy(block[0..length], view.bytes);
107 markPrior(view, retained, scratch.dirty);
108 return .{ .bytes = length, .dirty = collectDirty(scratch.place, scratch.dirty[0..view.nodes.len]) };
109 }
110
111 fn markPrior(view: View, retained: Retained, prior: []u32) void {
112 var index: u32 = 0;
113 while (index < view.nodes.len) {
114 const node = view.nodes[index];
115 const old = retained.map.lookup(retained.view.nodes, node.id);
116 if (old != null and retained.view.nodes[old.?].revision == node.revision) {
117 const span = node.subtree_count + 1;
118 for (0..span) |offset| prior[index + offset] = old.? + @as(u32, @intCast(offset));
119 index += span;
120 continue;
121 }
122 prior[index] = packedPrior(old, true);
123 index += 1;
124 }
125 }
126
127 const Sink = struct {
128 block: []align(8) u8,
129 capacity: Capacity,
130 atom_remap: []u32,
131 text_remap: []u32,
132 header: abi.Header = .{},
133 nodes: u32 = 0,
134 declarations: u32 = 0,
135 classes: u32 = 0,
136 texts: u32 = 0,
137 runs: u32 = 0,
138 atoms: u32 = 0,
139 strings: u32 = 0,
140
141 fn table(self: *const Sink, comptime T: type, entry: usize, count: u32) []T {
142 const base: [*]T = @ptrCast(@alignCast(self.block.ptr + self.capacity.offsets[entry]));
143 return base[0..count];
144 }
145
146 fn nodeTable(self: *const Sink) []Node {
147 return self.table(Node, 0, self.capacity.limits.nodes);
148 }
149
150 fn declarationTable(self: *const Sink) []abi.Declaration {
151 return self.table(abi.Declaration, 1, self.capacity.limits.declarations);
152 }
153
154 fn classTable(self: *const Sink) []u32 {
155 return self.table(u32, 2, self.capacity.limits.classes);
156 }
157
158 fn textTable(self: *const Sink) []abi.TextRecord {
159 return self.table(abi.TextRecord, 3, self.capacity.limits.texts);
160 }
161
162 fn runTable(self: *const Sink) []abi.TextRun {
163 return self.table(abi.TextRun, 4, self.capacity.limits.runs);
164 }
165
166 fn relationTable(self: *const Sink) []abi.Relation {
167 return self.table(abi.Relation, 5, self.capacity.limits.relations);
168 }
169
170 fn atomTable(self: *const Sink) []abi.Atom {
171 return self.table(abi.Atom, 6, self.capacity.limits.atoms);
172 }
173
174 fn stringTable(self: *const Sink) []u8 {
175 return self.table(u8, 7, self.capacity.limits.string_bytes);
176 }
177
178 fn solvedRootTable(self: *const Sink) []abi.SolvedRoot {
179 return self.table(abi.SolvedRoot, 8, self.capacity.limits.solved_roots);
180 }
181
182 fn solvedRectTable(self: *const Sink) []abi.Rect {
183 return self.table(abi.Rect, 9, self.capacity.limits.solved_rects);
184 }
185
186 fn span(self: *const Sink, entry: usize, count: u32) abi.Span {
187 return .{ .offset = self.capacity.offsets[entry], .count = count };
188 }
189
190 fn pushDeclarations(self: *Sink, source: []const abi.Declaration) u32 {
191 const first = self.declarations;
192 @memcpy(self.declarationTable()[first..][0..source.len], source);
193 self.declarations += @intCast(source.len);
194 return first;
195 }
196
197 fn pushAtom(self: *Sink, source: View, atom: u32) u32 {
198 if (atom == abi.atom_absent) return abi.atom_absent;
199 if (self.atom_remap[atom] != unbound) return self.atom_remap[atom];
200 const text = source.text(atom);
201 const offset = self.strings;
202 @memcpy(self.stringTable()[offset..][0..text.len], text);
203 self.strings += @intCast(text.len);
204 self.atomTable()[self.atoms] = .{ .offset = offset, .len = @intCast(text.len) };
205 self.atoms += 1;
206 self.atom_remap[atom] = self.atoms - 1;
207 return self.atoms - 1;
208 }
209
210 fn pushText(self: *Sink, source: View, index: u32) u32 {
211 if (self.text_remap[index] != unbound) return self.text_remap[index];
212 var record = source.texts[index];
213 const runs = source.runs[record.run_first..][0..record.run_count];
214 record.content = self.pushAtom(source, record.content);
215 record.run_first = self.runs;
216 for (runs, 0..) |run, offset| {
217 var copy = run;
218 const held = source.declarations[run.declaration_first..][0..run.declaration_count];
219 copy.declaration_first = self.pushDeclarations(held);
220 self.runTable()[self.runs + offset] = copy;
221 }
222 self.runs += @intCast(runs.len);
223 self.textTable()[self.texts] = record;
224 self.texts += 1;
225 self.text_remap[index] = self.texts - 1;
226 return self.texts - 1;
227 }
228 };
229
230 fn rebuild(
231 sink: *Sink,
232 block_map: *Map,
233 publish: View,
234 retained: Retained,
235 scratch: Scratch,
236 ) Outcome {
237 seed(sink, publish);
238 @memset(scratch.atom_remap[0..retained.view.atoms.len], unbound);
239 @memset(scratch.text_remap[0..retained.view.texts.len], unbound);
240 emit(sink, publish, retained, scratch);
241 trailers(sink, publish, scratch.place);
242 header(sink, publish);
243 @memcpy(sink.block[0..abi.header_bytes], std.mem.asBytes(&sink.header));
244 rebuildMap(block_map, sink.nodeTable()[0..sink.nodes]);
245 return .{ .bytes = sink.capacity.buffer_bytes, .dirty = collectDirty(scratch.place, scratch.dirty[0..sink.nodes]) };
246 }
247
248 fn seed(sink: *Sink, publish: View) void {
249 @memcpy(sink.declarationTable()[0..publish.declarations.len], publish.declarations);
250 @memcpy(sink.classTable()[0..publish.classes.len], publish.classes);
251 @memcpy(sink.textTable()[0..publish.texts.len], publish.texts);
252 @memcpy(sink.runTable()[0..publish.runs.len], publish.runs);
253 @memcpy(sink.atomTable()[0..publish.atoms.len], publish.atoms);
254 @memcpy(sink.stringTable()[0..publish.strings.len], publish.strings);
255 sink.declarations = @intCast(publish.declarations.len);
256 sink.classes = @intCast(publish.classes.len);
257 sink.texts = @intCast(publish.texts.len);
258 sink.runs = @intCast(publish.runs.len);
259 sink.atoms = @intCast(publish.atoms.len);
260 sink.strings = @intCast(publish.strings.len);
261 }
262
263 fn emit(sink: *Sink, publish: View, retained: Retained, scratch: Scratch) void {
264 var stack: [arrange.max_depth]Frame = undefined;
265 var depth: u32 = 0;
266 var index: u32 = 0;
267 while (index < publish.nodes.len) : (index += 1) {
268 depth = close(sink, stack[0..], depth, index);
269 const node = publish.nodes[index];
270 const parent = if (index == 0) 0 else scratch.place[node.parent];
271 scratch.place[index] = sink.nodes;
272 if (abi.holds(node.flags, .retained)) {
273 const source = retained.map.lookup(retained.view.nodes, node.id).?;
274 graft(sink, retained.view, source, parent, scratch.dirty);
275 continue;
276 }
277 emitNode(sink, publish, index, parent);
278 const old = retained.map.lookup(retained.view.nodes, node.id);
279 const changed = old == null or retained.view.nodes[old.?].revision != node.revision;
280 scratch.dirty[sink.nodes - 1] = packedPrior(old, changed);
281 stack[depth] = .{ .last = index + node.subtree_count, .slot = sink.nodes - 1 };
282 depth += 1;
283 }
284 _ = close(sink, stack[0..], depth, std.math.maxInt(u32));
285 }
286
287 fn close(sink: *Sink, stack: []Frame, depth: u32, index: u32) u32 {
288 var open = depth;
289 while (open > 0 and stack[open - 1].last < index) {
290 open -= 1;
291 const slot = stack[open].slot;
292 sink.nodeTable()[slot].subtree_count = sink.nodes - slot - 1;
293 }
294 return open;
295 }
296
297 fn emitNode(sink: *Sink, publish: View, index: u32, parent: u32) void {
298 var record = publish.nodes[index];
299 record.parent = parent;
300 record.subtree_count = 0;
301 sink.nodeTable()[sink.nodes] = record;
302 sink.nodes += 1;
303 }
304
305 fn graft(sink: *Sink, source: View, root: u32, parent: u32, prior: []u32) void {
306 const span = source.nodes[root].subtree_count + 1;
307 const base = sink.nodes;
308 var offset: u32 = 0;
309 while (offset < span) : (offset += 1) {
310 var record = source.nodes[root + offset];
311 std.debug.assert(!abi.holds(record.flags, .retained));
312 record.parent = if (offset == 0) parent else base + (record.parent - root);
313 rebind(sink, source, &record);
314 sink.nodeTable()[base + offset] = record;
315 prior[base + offset] = root + offset;
316 sink.nodes += 1;
317 }
318 sink.nodeTable()[base].subtree_count = span - 1;
319 }
320
321 fn rebind(sink: *Sink, source: View, record: *Node) void {
322 const held = source.declarations[record.declaration_first..][0..record.declaration_count];
323 record.declaration_first = sink.pushDeclarations(held);
324 const classes = source.classes[record.class_first..][0..record.class_count];
325 const first = sink.classes;
326 for (classes, 0..) |class, offset| {
327 sink.classTable()[first + offset] = sink.pushAtom(source, class);
328 }
329 sink.classes += @intCast(classes.len);
330 record.class_first = first;
331 record.identifier = sink.pushAtom(source, record.identifier);
332 record.name = sink.pushAtom(source, record.name);
333 record.action = sink.pushAtom(source, record.action);
334 if (record.text != abi.text_absent) record.text = sink.pushText(source, record.text);
335 }
336
337 fn trailers(sink: *Sink, publish: View, place: []const u32) void {
338 for (publish.relations, 0..) |relation, index| {
339 var copy = relation;
340 copy.subject = place[relation.subject];
341 copy.object = place[relation.object];
342 sink.relationTable()[index] = copy;
343 }
344 for (publish.solved_roots, 0..) |root, index| {
345 var copy = root;
346 copy.node = place[root.node];
347 sink.solvedRootTable()[index] = copy;
348 }
349 @memcpy(sink.solvedRectTable()[0..publish.solved_rects.len], publish.solved_rects);
350 }
351
352 fn header(sink: *Sink, publish: View) void {
353 sink.header = publish.header;
354 sink.header.buffer_bytes = sink.capacity.buffer_bytes;
355 sink.header.nodes = sink.span(0, sink.nodes);
356 sink.header.declarations = sink.span(1, sink.declarations);
357 sink.header.classes = sink.span(2, sink.classes);
358 sink.header.texts = sink.span(3, sink.texts);
359 sink.header.runs = sink.span(4, sink.runs);
360 sink.header.relations = sink.span(5, @intCast(publish.relations.len));
361 sink.header.atoms = sink.span(6, sink.atoms);
362 sink.header.strings = sink.span(7, sink.strings);
363 sink.header.solved_roots = sink.span(8, @intCast(publish.solved_roots.len));
364 sink.header.solved_rects = sink.span(9, @intCast(publish.solved_rects.len));
365 }
366
367 fn rebuildMap(block_map: *Map, nodes: []const Node) void {
368 block_map.reset();
369 var index: u32 = 0;
370 while (index < nodes.len) : (index += 1) {
371 const inserted = block_map.insert(nodes, index);
372 std.debug.assert(inserted);
373 }
374 }