rickub
nandi/jolt-nativepublic⑂ Fork 0
⑂ main
Branches
main View all branches → View all tags →
Commits
⬇ Clone ▾
git clone https://git.rickub.com/nandi/jolt-native.git
git clone ssh://git@rickub.com/nandi/jolt-native.git

Host key fingerprint (ed25519): SHA256:iycHnxEyq0Q7uyVpB7JlznP0G7JrTPXLYRcAU5CSLhc — verify it before your first connect.

tree.zig · 555 lines · 20.6 KBZig Blame HistoryRaw
Paint the tree ABI a third way: Zig and dvui 7289263 nandi 9d ago1//! The retained tree: nodes, props, children, and the event queue jolt polls.
2//!
3//! This is the same shape `crates/jolt-vidya/src/tree.rs` holds and
4//! `crates/jolt-tui` holds again — a tree the caller mutates between frames and
5//! a painter walks during one. Nothing here knows what paints it.
6
7const std = @import("std");
8
9const Allocator = std.mem.Allocator;
10
11/// A prop value. The three types jolt's FFI vocabulary can carry.
12pub const Value = union(enum) {
13 str: []u8,
14 num: f64,
15 boolean: bool,
16};
17
18/// One queued event, drained by `poll`.
19pub const Event = struct {
20 node: u32,
21 /// Static: `click`, `change`, `toggled`, `activate`.
22 name: []const u8,
23 text: []u8,
24 num: f64,
25};
26
27pub const Node = struct {
28 tag: []u8 = &.{},
29 props: std.StringHashMapUnmanaged(Value) = .empty,
30 children: std.ArrayList(u32) = .empty,
31 parent: u32 = 0,
32 alive: bool = false,
33 /// Bumped every time this slot is handed out again. Widget identity is
34 /// `(generation, index)` rather than the index alone, so a node freed and
35 /// reallocated in the same frame does not inherit the widget state of the
36 /// node that used to live here — which is the bug class the reconciler
37 /// notes in frq's deps.edn describe from the other side.
38 generation: u32 = 0,
39 /// Persistent edit buffer for `entry` nodes, kept across frames because a
40 /// text field owns its contents between the caller's writes.
41 entry: ?std.ArrayList(u8) = null,
42 /// Whether `entry` has been seeded from the `text` prop yet.
43 entry_seeded: bool = false,
44};
45
46pub const Tree = struct {
47 gpa: Allocator,
48 /// Slot 0 is never handed out — 0 is how this ABI spells "no node", the
49 /// same way `vidya_node_new` answers 0 on failure.
50 nodes: std.ArrayList(Node) = .empty,
51 free: std.ArrayList(u32) = .empty,
52 events: std.ArrayList(Event) = .empty,
53 /// Read position in `events`; the queue compacts when it drains.
54 head: usize = 0,
55 current: ?Event = null,
56
57 pub fn init(gpa: Allocator) !Tree {
58 var self: Tree = .{ .gpa = gpa };
59 // Slot 0: the null node. Slot 1: the root, which is never freed.
60 try self.nodes.append(gpa, .{});
61 const root_id = try self.alloc("window");
62 std.debug.assert(root_id == 1);
63 return self;
64 }
65
66 pub fn deinit(self: *Tree) void {
67 for (self.nodes.items) |*n| self.release(n);
68 self.nodes.deinit(self.gpa);
69 self.free.deinit(self.gpa);
70 for (self.events.items) |e| self.gpa.free(e.text);
71 self.events.deinit(self.gpa);
72 if (self.current) |e| self.gpa.free(e.text);
73 self.current = null;
74 }
75
76 fn release(self: *Tree, n: *Node) void {
77 if (n.tag.len != 0) self.gpa.free(n.tag);
78 n.tag = &.{};
79 self.clearProps(n);
80 n.props.deinit(self.gpa);
81 n.props = .empty;
82 n.children.deinit(self.gpa);
83 n.children = .empty;
84 if (n.entry) |*buf| buf.deinit(self.gpa);
85 n.entry = null;
86 n.entry_seeded = false;
87 }
88
89 fn clearProps(self: *Tree, n: *Node) void {
90 var it = n.props.iterator();
91 while (it.next()) |kv| {
92 self.gpa.free(kv.key_ptr.*);
93 if (kv.value_ptr.* == .str) self.gpa.free(kv.value_ptr.str);
94 }
95 n.props.clearRetainingCapacity();
96 }
97
98 pub fn root(self: *Tree) u32 {
99 _ = self;
100 return 1;
101 }
102
103 pub fn get(self: *Tree, id: u32) ?*Node {
104 if (id == 0 or id >= self.nodes.items.len) return null;
105 const n = &self.nodes.items[id];
106 return if (n.alive) n else null;
107 }
108
109 fn alloc(self: *Tree, tag: []const u8) !u32 {
110 const owned = try self.gpa.dupe(u8, tag);
111 errdefer self.gpa.free(owned);
112 if (self.free.pop()) |id| {
113 const n = &self.nodes.items[id];
114 n.* = .{
115 .tag = owned,
116 .alive = true,
117 // Reuse never repeats an identity.
118 .generation = n.generation +% 1,
119 };
120 return id;
121 }
122 const id: u32 = @intCast(self.nodes.items.len);
123 try self.nodes.append(self.gpa, .{ .tag = owned, .alive = true });
124 return id;
125 }
126
127 pub fn new(self: *Tree, tag: []const u8) u32 {
128 return self.alloc(tag) catch 0;
129 }
130
131 /// Free a node and everything under it. Detaches from its parent first, so
132 /// a caller that frees a subtree still holds a consistent tree.
133 pub fn free_node(self: *Tree, id: u32) void {
134 if (id <= 1) return; // never free the null slot or the root
135 const n = self.get(id) orelse return;
136 const parent = n.parent;
137 if (self.get(parent)) |p| {
138 if (std.mem.indexOfScalar(u32, p.children.items, id)) |i| {
139 _ = p.children.orderedRemove(i);
140 }
141 }
142 self.freeSubtree(id);
143 }
144
145 fn freeSubtree(self: *Tree, id: u32) void {
146 const n = self.get(id) orelse return;
147 // Copy the child list: releasing the node frees the backing array.
148 const kids = self.gpa.dupe(u32, n.children.items) catch &.{};
149 defer if (kids.len != 0) self.gpa.free(kids);
150 for (kids) |c| self.freeSubtree(c);
151 const node = &self.nodes.items[id];
152 self.release(node);
153 node.alive = false;
154 node.parent = 0;
155 self.free.append(self.gpa, id) catch {};
156 }
157
158 /// The identity a painter keys widget state by: never repeated after reuse.
159 pub fn widgetId(self: *Tree, id: u32) usize {
160 const gen: usize = if (id < self.nodes.items.len) self.nodes.items[id].generation else 0;
161 return (gen << 32) | @as(usize, id);
162 }
163
164 // ── Props ───────────────────────────────────────────────────────────────
165
166 fn put(self: *Tree, n: *Node, key: []const u8, value: Value) !void {
167 const gop = try n.props.getOrPut(self.gpa, key);
168 if (gop.found_existing) {
169 if (gop.value_ptr.* == .str) self.gpa.free(gop.value_ptr.str);
170 } else {
171 gop.key_ptr.* = self.gpa.dupe(u8, key) catch |e| {
172 _ = n.props.remove(key);
173 return e;
174 };
175 }
176 gop.value_ptr.* = value;
177 }
178
179 pub fn setStr(self: *Tree, id: u32, key: []const u8, value: []const u8) void {
180 const n = self.get(id) orelse return;
181 const owned = self.gpa.dupe(u8, value) catch return;
182 self.put(n, key, .{ .str = owned }) catch self.gpa.free(owned);
183 // A caller writing `text` is authoritative over an entry's contents.
184 if (std.mem.eql(u8, key, "text")) n.entry_seeded = false;
185 }
186
187 pub fn setNum(self: *Tree, id: u32, key: []const u8, value: f64) void {
188 const n = self.get(id) orelse return;
189 self.put(n, key, .{ .num = value }) catch {};
190 }
191
192 pub fn setBool(self: *Tree, id: u32, key: []const u8, value: bool) void {
193 const n = self.get(id) orelse return;
194 self.put(n, key, .{ .boolean = value }) catch {};
195 }
196
197 pub fn clear(self: *Tree, id: u32) void {
198 const n = self.get(id) orelse return;
199 self.clearProps(n);
200 }
201
202 pub fn getStr(self: *Tree, id: u32, key: []const u8) []const u8 {
203 const n = self.get(id) orelse return "";
204 const v = n.props.get(key) orelse return "";
205 return switch (v) {
206 .str => |s| s,
207 else => "",
208 };
209 }
210
211 pub fn getNum(self: *Tree, id: u32, key: []const u8) f64 {
212 const n = self.get(id) orelse return 0;
213 const v = n.props.get(key) orelse return 0;
214 return switch (v) {
215 .num => |x| x,
216 .boolean => |b| if (b) 1 else 0,
217 .str => 0,
218 };
219 }
220
221 pub fn getBool(self: *Tree, id: u32, key: []const u8) bool {
222 const n = self.get(id) orelse return false;
223 const v = n.props.get(key) orelse return false;
224 return switch (v) {
225 .boolean => |b| b,
226 .num => |x| x != 0,
227 .str => |s| s.len != 0,
228 };
229 }
230
231 // ── Children ────────────────────────────────────────────────────────────
232
233 /// Detach `child` from whatever parent currently holds it.
234 fn detach(self: *Tree, child: u32) void {
235 const c = self.get(child) orelse return;
236 if (self.get(c.parent)) |p| {
237 if (std.mem.indexOfScalar(u32, p.children.items, child)) |i| {
238 _ = p.children.orderedRemove(i);
239 }
240 }
241 c.parent = 0;
242 }
243
244 /// True when `ancestor` is `node` or is above it — a cycle check, because
245 /// appending a node into its own subtree makes a walk that never returns.
246 fn contains(self: *Tree, ancestor: u32, node: u32) bool {
247 var walk = node;
248 var guard_count: usize = 0;
249 while (walk != 0) : (guard_count += 1) {
250 if (walk == ancestor) return true;
251 if (guard_count > self.nodes.items.len) return true; // already cyclic
252 const n = self.get(walk) orelse return false;
253 walk = n.parent;
254 }
255 return false;
256 }
257
258 pub fn append(self: *Tree, parent: u32, child: u32) bool {
259 if (parent == child) return false;
260 _ = self.get(child) orelse return false;
261 const p = self.get(parent) orelse return false;
262 if (self.contains(child, parent)) return false;
263 self.detach(child);
264 const pp = self.get(parent).?;
265 pp.children.append(self.gpa, child) catch return false;
266 self.get(child).?.parent = parent;
267 _ = p;
268 return true;
269 }
270
271 pub fn remove(self: *Tree, parent: u32, child: u32) void {
272 const p = self.get(parent) orelse return;
273 if (std.mem.indexOfScalar(u32, p.children.items, child)) |i| {
274 _ = p.children.orderedRemove(i);
275 if (self.get(child)) |c| c.parent = 0;
276 }
277 }
278
279 pub fn insertAfter(self: *Tree, parent: u32, child: u32, sibling: u32) bool {
280 if (parent == child) return false;
281 _ = self.get(child) orelse return false;
282 _ = self.get(parent) orelse return false;
283 if (self.contains(child, parent)) return false;
284 self.detach(child);
285 const p = self.get(parent).?;
286 // A sibling of 0, or one that is not here, means the front — which is
287 // what "insert after nothing" means to a reconciler walking a list.
288 const at: usize = if (sibling == 0)
289 0
290 else if (std.mem.indexOfScalar(u32, p.children.items, sibling)) |i|
291 i + 1
292 else
293 p.children.items.len;
294 p.children.insert(self.gpa, at, child) catch return false;
295 self.get(child).?.parent = parent;
296 return true;
297 }
298
299 pub fn replace(self: *Tree, parent: u32, old_child: u32, new_child: u32) bool {
300 if (old_child == new_child) return true;
301 _ = self.get(new_child) orelse return false;
302 const p = self.get(parent) orelse return false;
303 const at = std.mem.indexOfScalar(u32, p.children.items, old_child) orelse return false;
304 if (self.contains(new_child, parent)) return false;
305 self.detach(new_child);
306 const pp = self.get(parent).?;
307 // `detach` may have shifted the list if new_child was a sibling.
308 const idx = std.mem.indexOfScalar(u32, pp.children.items, old_child) orelse at;
309 pp.children.items[idx] = new_child;
310 self.get(new_child).?.parent = parent;
311 if (self.get(old_child)) |o| o.parent = 0;
312 return true;
313 }
314
315 pub fn childCount(self: *Tree, id: u32) u32 {
316 const n = self.get(id) orelse return 0;
317 return @intCast(n.children.items.len);
318 }
319
320 pub fn childAt(self: *Tree, id: u32, index: u32) u32 {
321 const n = self.get(id) orelse return 0;
322 if (index >= n.children.items.len) return 0;
323 return n.children.items[index];
324 }
325
326 // ── Events ──────────────────────────────────────────────────────────────
327
328 pub fn emit(self: *Tree, node: u32, name: []const u8, text: []const u8, num: f64) void {
329 const owned = self.gpa.dupe(u8, text) catch return;
330 self.events.append(self.gpa, .{
331 .node = node,
332 .name = name,
333 .text = owned,
334 .num = num,
335 }) catch self.gpa.free(owned);
336 }
337
338 /// Dequeue one event. True while there was one; the accessors below then
339 /// describe it until the next poll.
340 pub fn poll(self: *Tree) bool {
341 if (self.current) |e| {
342 self.gpa.free(e.text);
343 self.current = null;
344 }
345 if (self.head >= self.events.items.len) {
346 // Drained: reset rather than grow the backing array forever.
347 self.events.clearRetainingCapacity();
348 self.head = 0;
349 return false;
350 }
351 self.current = self.events.items[self.head];
352 self.head += 1;
353 return true;
354 }
355
356 // ── Debugging ───────────────────────────────────────────────────────────
357
358 pub fn dump(self: *Tree, id: u32, out: *std.ArrayList(u8), depth: usize) void {
359 const n = self.get(id) orelse return;
360 out.appendNTimes(self.gpa, ' ', depth * 2) catch return;
361 out.print(self.gpa, "<{s} #{d}", .{ n.tag, id }) catch return;
362 var it = n.props.iterator();
363 while (it.next()) |kv| {
364 switch (kv.value_ptr.*) {
365 .str => |s| out.print(self.gpa, " {s}=\"{s}\"", .{ kv.key_ptr.*, s }) catch return,
366 .num => |x| out.print(self.gpa, " {s}={d}", .{ kv.key_ptr.*, x }) catch return,
367 .boolean => |b| out.print(self.gpa, " {s}={}", .{ kv.key_ptr.*, b }) catch return,
368 }
369 }
370 out.appendSlice(self.gpa, ">\n") catch return;
371 const kids = self.gpa.dupe(u32, n.children.items) catch return;
372 defer self.gpa.free(kids);
373 for (kids) |c| self.dump(c, out, depth + 1);
374 }
375};
376
377// ── Tests ───────────────────────────────────────────────────────────────────
378//
379// The tree is the half worth testing without a window: everything here is what
380// a reconciler does to it between frames.
381
382const testing = std.testing;
383
384fn childrenOf(t: *Tree, id: u32) []const u32 {
385 return (t.get(id) orelse unreachable).children.items;
386}
387
388test "root exists and is not freeable" {
389 var t = try Tree.init(testing.allocator);
390 defer t.deinit();
391 try testing.expectEqual(@as(u32, 1), t.root());
392 t.free_node(t.root());
393 try testing.expect(t.get(t.root()) != null);
394}
395
396test "props round-trip and coerce" {
397 var t = try Tree.init(testing.allocator);
398 defer t.deinit();
399 const n = t.new("label");
400 t.setStr(n, "text", "hello");
401 t.setNum(n, "size", 12.5);
402 t.setBool(n, "active", true);
403 try testing.expectEqualStrings("hello", t.getStr(n, "text"));
404 try testing.expectEqual(@as(f64, 12.5), t.getNum(n, "size"));
405 try testing.expect(t.getBool(n, "active"));
406 // A bool reads as a number and a number as a bool; a missing prop is zero.
407 try testing.expectEqual(@as(f64, 1), t.getNum(n, "active"));
408 try testing.expectEqual(@as(f64, 0), t.getNum(n, "absent"));
409 try testing.expectEqualStrings("", t.getStr(n, "absent"));
410 // Overwriting a string frees the old one rather than leaking it.
411 t.setStr(n, "text", "goodbye");
412 try testing.expectEqualStrings("goodbye", t.getStr(n, "text"));
413 t.clear(n);
414 try testing.expectEqualStrings("", t.getStr(n, "text"));
415}
416
417test "append moves a child rather than duplicating it" {
418 var t = try Tree.init(testing.allocator);
419 defer t.deinit();
420 const a = t.new("box");
421 const b = t.new("box");
422 const c = t.new("label");
423 try testing.expect(t.append(t.root(), a));
424 try testing.expect(t.append(t.root(), b));
425 try testing.expect(t.append(a, c));
426 try testing.expectEqualSlices(u32, &.{c}, childrenOf(&t, a));
427 // Re-appending elsewhere detaches from the old parent.
428 try testing.expect(t.append(b, c));
429 try testing.expectEqualSlices(u32, &.{}, childrenOf(&t, a));
430 try testing.expectEqualSlices(u32, &.{c}, childrenOf(&t, b));
431 try testing.expectEqual(b, t.get(c).?.parent);
432}
433
434test "a node cannot be appended into its own subtree" {
435 var t = try Tree.init(testing.allocator);
436 defer t.deinit();
437 const a = t.new("box");
438 const b = t.new("box");
439 try testing.expect(t.append(t.root(), a));
440 try testing.expect(t.append(a, b));
441 // Both the direct cycle and the deeper one are refused; a walk that never
442 // returns is a hang in the painter, not an error the caller would see.
443 try testing.expect(!t.append(a, a));
444 try testing.expect(!t.append(b, a));
445 try testing.expectEqualSlices(u32, &.{b}, childrenOf(&t, a));
446}
447
448test "insert_after places by sibling, and 0 means the front" {
449 var t = try Tree.init(testing.allocator);
450 defer t.deinit();
451 const p = t.new("box");
452 _ = t.append(t.root(), p);
453 const a = t.new("label");
454 const b = t.new("label");
455 const c = t.new("label");
456 _ = t.append(p, a);
457 _ = t.append(p, b);
458 try testing.expect(t.insertAfter(p, c, a));
459 try testing.expectEqualSlices(u32, &.{ a, c, b }, childrenOf(&t, p));
460 const d = t.new("label");
461 try testing.expect(t.insertAfter(p, d, 0));
462 try testing.expectEqualSlices(u32, &.{ d, a, c, b }, childrenOf(&t, p));
463}
464
465test "replace keeps position, including when the new child is a sibling" {
466 var t = try Tree.init(testing.allocator);
467 defer t.deinit();
468 const p = t.new("box");
469 _ = t.append(t.root(), p);
470 const a = t.new("label");
471 const b = t.new("label");
472 const c = t.new("label");
473 _ = t.append(p, a);
474 _ = t.append(p, b);
475 _ = t.append(p, c);
476 // Replacing with a node already in the list must not leave it twice, and
477 // must not shift the slot out from under the index it was found at.
478 try testing.expect(t.replace(p, a, c));
479 try testing.expectEqualSlices(u32, &.{ c, b }, childrenOf(&t, p));
480 try testing.expectEqual(@as(u32, 0), t.get(a).?.parent);
481}
482
483test "free takes the subtree and detaches from the parent" {
484 var t = try Tree.init(testing.allocator);
485 defer t.deinit();
486 const p = t.new("box");
487 _ = t.append(t.root(), p);
488 const a = t.new("box");
489 const b = t.new("label");
490 _ = t.append(p, a);
491 _ = t.append(a, b);
492 t.free_node(a);
493 try testing.expect(t.get(a) == null);
494 try testing.expect(t.get(b) == null);
495 try testing.expectEqualSlices(u32, &.{}, childrenOf(&t, p));
496}
497
498test "a reused id is never the same widget identity" {
499 var t = try Tree.init(testing.allocator);
500 defer t.deinit();
501 const a = t.new("button");
502 _ = t.append(t.root(), a);
503 const first = t.widgetId(a);
504 t.free_node(a);
505 const b = t.new("button");
506 // The id comes back — that is the point of the free list — but the identity
507 // a painter keys widget state by must not, or the new node inherits the old
508 // one's cursor, scroll position and animation.
509 try testing.expectEqual(a, b);
510 try testing.expect(first != t.widgetId(b));
511}
512
513test "events queue in order and drain once" {
514 var t = try Tree.init(testing.allocator);
515 defer t.deinit();
516 const a = t.new("button");
517 t.emit(a, "click", "", 0);
518 t.emit(a, "change", "typed", 3);
519 try testing.expect(t.poll());
520 try testing.expectEqualStrings("click", t.current.?.name);
521 try testing.expect(t.poll());
522 try testing.expectEqualStrings("change", t.current.?.name);
523 try testing.expectEqualStrings("typed", t.current.?.text);
524 try testing.expectEqual(@as(f64, 3), t.current.?.num);
525 try testing.expect(!t.poll());
526 try testing.expect(t.current == null);
527}
528
529test "dump shows the shape" {
530 var t = try Tree.init(testing.allocator);
531 defer t.deinit();
532 const l = t.new("label");
533 t.setStr(l, "text", "hi");
534 _ = t.append(t.root(), l);
535 var out: std.ArrayList(u8) = .empty;
536 defer out.deinit(testing.allocator);
537 t.dump(t.root(), &out, 0);
538 try testing.expectEqualStrings(
539 \\<window #1>
540 \\ <label #2 text="hi">
541 \\
542 , out.items);
543}
544
545test "a bad id is a miss, not an index" {
546 var t = try Tree.init(testing.allocator);
547 defer t.deinit();
548 try testing.expect(t.get(0) == null);
549 try testing.expect(t.get(9999) == null);
550 try testing.expectEqual(@as(u32, 0), t.childCount(9999));
551 try testing.expectEqual(@as(u32, 0), t.childAt(9999, 0));
552 try testing.expect(!t.append(9999, 1));
553 t.setStr(9999, "text", "ignored");
554 t.free_node(9999);
555}