//! The retained tree: nodes, props, children, and the event queue jolt polls. //! //! This is the same shape `crates/jolt-vidya/src/tree.rs` holds and //! `crates/jolt-tui` holds again — a tree the caller mutates between frames and //! a painter walks during one. Nothing here knows what paints it. const std = @import("std"); const Allocator = std.mem.Allocator; /// A prop value. The three types jolt's FFI vocabulary can carry. pub const Value = union(enum) { str: []u8, num: f64, boolean: bool, }; /// One queued event, drained by `poll`. pub const Event = struct { node: u32, /// Static: `click`, `change`, `toggled`, `activate`. name: []const u8, text: []u8, num: f64, }; pub const Node = struct { tag: []u8 = &.{}, props: std.StringHashMapUnmanaged(Value) = .empty, children: std.ArrayList(u32) = .empty, parent: u32 = 0, alive: bool = false, /// Bumped every time this slot is handed out again. Widget identity is /// `(generation, index)` rather than the index alone, so a node freed and /// reallocated in the same frame does not inherit the widget state of the /// node that used to live here — which is the bug class the reconciler /// notes in frq's deps.edn describe from the other side. generation: u32 = 0, /// Persistent edit buffer for `entry` nodes, kept across frames because a /// text field owns its contents between the caller's writes. entry: ?std.ArrayList(u8) = null, /// Whether `entry` has been seeded from the `text` prop yet. entry_seeded: bool = false, }; pub const Tree = struct { gpa: Allocator, /// Slot 0 is never handed out — 0 is how this ABI spells "no node", the /// same way `vidya_node_new` answers 0 on failure. nodes: std.ArrayList(Node) = .empty, free: std.ArrayList(u32) = .empty, events: std.ArrayList(Event) = .empty, /// Read position in `events`; the queue compacts when it drains. head: usize = 0, current: ?Event = null, pub fn init(gpa: Allocator) !Tree { var self: Tree = .{ .gpa = gpa }; // Slot 0: the null node. Slot 1: the root, which is never freed. try self.nodes.append(gpa, .{}); const root_id = try self.alloc("window"); std.debug.assert(root_id == 1); return self; } pub fn deinit(self: *Tree) void { for (self.nodes.items) |*n| self.release(n); self.nodes.deinit(self.gpa); self.free.deinit(self.gpa); for (self.events.items) |e| self.gpa.free(e.text); self.events.deinit(self.gpa); if (self.current) |e| self.gpa.free(e.text); self.current = null; } fn release(self: *Tree, n: *Node) void { if (n.tag.len != 0) self.gpa.free(n.tag); n.tag = &.{}; self.clearProps(n); n.props.deinit(self.gpa); n.props = .empty; n.children.deinit(self.gpa); n.children = .empty; if (n.entry) |*buf| buf.deinit(self.gpa); n.entry = null; n.entry_seeded = false; } fn clearProps(self: *Tree, n: *Node) void { var it = n.props.iterator(); while (it.next()) |kv| { self.gpa.free(kv.key_ptr.*); if (kv.value_ptr.* == .str) self.gpa.free(kv.value_ptr.str); } n.props.clearRetainingCapacity(); } pub fn root(self: *Tree) u32 { _ = self; return 1; } pub fn get(self: *Tree, id: u32) ?*Node { if (id == 0 or id >= self.nodes.items.len) return null; const n = &self.nodes.items[id]; return if (n.alive) n else null; } fn alloc(self: *Tree, tag: []const u8) !u32 { const owned = try self.gpa.dupe(u8, tag); errdefer self.gpa.free(owned); if (self.free.pop()) |id| { const n = &self.nodes.items[id]; n.* = .{ .tag = owned, .alive = true, // Reuse never repeats an identity. .generation = n.generation +% 1, }; return id; } const id: u32 = @intCast(self.nodes.items.len); try self.nodes.append(self.gpa, .{ .tag = owned, .alive = true }); return id; } pub fn new(self: *Tree, tag: []const u8) u32 { return self.alloc(tag) catch 0; } /// Free a node and everything under it. Detaches from its parent first, so /// a caller that frees a subtree still holds a consistent tree. pub fn free_node(self: *Tree, id: u32) void { if (id <= 1) return; // never free the null slot or the root const n = self.get(id) orelse return; const parent = n.parent; if (self.get(parent)) |p| { if (std.mem.indexOfScalar(u32, p.children.items, id)) |i| { _ = p.children.orderedRemove(i); } } self.freeSubtree(id); } fn freeSubtree(self: *Tree, id: u32) void { const n = self.get(id) orelse return; // Copy the child list: releasing the node frees the backing array. const kids = self.gpa.dupe(u32, n.children.items) catch &.{}; defer if (kids.len != 0) self.gpa.free(kids); for (kids) |c| self.freeSubtree(c); const node = &self.nodes.items[id]; self.release(node); node.alive = false; node.parent = 0; self.free.append(self.gpa, id) catch {}; } /// The identity a painter keys widget state by: never repeated after reuse. pub fn widgetId(self: *Tree, id: u32) usize { const gen: usize = if (id < self.nodes.items.len) self.nodes.items[id].generation else 0; return (gen << 32) | @as(usize, id); } // ── Props ─────────────────────────────────────────────────────────────── fn put(self: *Tree, n: *Node, key: []const u8, value: Value) !void { const gop = try n.props.getOrPut(self.gpa, key); if (gop.found_existing) { if (gop.value_ptr.* == .str) self.gpa.free(gop.value_ptr.str); } else { gop.key_ptr.* = self.gpa.dupe(u8, key) catch |e| { _ = n.props.remove(key); return e; }; } gop.value_ptr.* = value; } pub fn setStr(self: *Tree, id: u32, key: []const u8, value: []const u8) void { const n = self.get(id) orelse return; const owned = self.gpa.dupe(u8, value) catch return; self.put(n, key, .{ .str = owned }) catch self.gpa.free(owned); // A caller writing `text` is authoritative over an entry's contents. if (std.mem.eql(u8, key, "text")) n.entry_seeded = false; } pub fn setNum(self: *Tree, id: u32, key: []const u8, value: f64) void { const n = self.get(id) orelse return; self.put(n, key, .{ .num = value }) catch {}; } pub fn setBool(self: *Tree, id: u32, key: []const u8, value: bool) void { const n = self.get(id) orelse return; self.put(n, key, .{ .boolean = value }) catch {}; } pub fn clear(self: *Tree, id: u32) void { const n = self.get(id) orelse return; self.clearProps(n); } pub fn getStr(self: *Tree, id: u32, key: []const u8) []const u8 { const n = self.get(id) orelse return ""; const v = n.props.get(key) orelse return ""; return switch (v) { .str => |s| s, else => "", }; } pub fn getNum(self: *Tree, id: u32, key: []const u8) f64 { const n = self.get(id) orelse return 0; const v = n.props.get(key) orelse return 0; return switch (v) { .num => |x| x, .boolean => |b| if (b) 1 else 0, .str => 0, }; } pub fn getBool(self: *Tree, id: u32, key: []const u8) bool { const n = self.get(id) orelse return false; const v = n.props.get(key) orelse return false; return switch (v) { .boolean => |b| b, .num => |x| x != 0, .str => |s| s.len != 0, }; } // ── Children ──────────────────────────────────────────────────────────── /// Detach `child` from whatever parent currently holds it. fn detach(self: *Tree, child: u32) void { const c = self.get(child) orelse return; if (self.get(c.parent)) |p| { if (std.mem.indexOfScalar(u32, p.children.items, child)) |i| { _ = p.children.orderedRemove(i); } } c.parent = 0; } /// True when `ancestor` is `node` or is above it — a cycle check, because /// appending a node into its own subtree makes a walk that never returns. fn contains(self: *Tree, ancestor: u32, node: u32) bool { var walk = node; var guard_count: usize = 0; while (walk != 0) : (guard_count += 1) { if (walk == ancestor) return true; if (guard_count > self.nodes.items.len) return true; // already cyclic const n = self.get(walk) orelse return false; walk = n.parent; } return false; } pub fn append(self: *Tree, parent: u32, child: u32) bool { if (parent == child) return false; _ = self.get(child) orelse return false; const p = self.get(parent) orelse return false; if (self.contains(child, parent)) return false; self.detach(child); const pp = self.get(parent).?; pp.children.append(self.gpa, child) catch return false; self.get(child).?.parent = parent; _ = p; return true; } pub fn remove(self: *Tree, parent: u32, child: u32) void { const p = self.get(parent) orelse return; if (std.mem.indexOfScalar(u32, p.children.items, child)) |i| { _ = p.children.orderedRemove(i); if (self.get(child)) |c| c.parent = 0; } } pub fn insertAfter(self: *Tree, parent: u32, child: u32, sibling: u32) bool { if (parent == child) return false; _ = self.get(child) orelse return false; _ = self.get(parent) orelse return false; if (self.contains(child, parent)) return false; self.detach(child); const p = self.get(parent).?; // A sibling of 0, or one that is not here, means the front — which is // what "insert after nothing" means to a reconciler walking a list. const at: usize = if (sibling == 0) 0 else if (std.mem.indexOfScalar(u32, p.children.items, sibling)) |i| i + 1 else p.children.items.len; p.children.insert(self.gpa, at, child) catch return false; self.get(child).?.parent = parent; return true; } pub fn replace(self: *Tree, parent: u32, old_child: u32, new_child: u32) bool { if (old_child == new_child) return true; _ = self.get(new_child) orelse return false; const p = self.get(parent) orelse return false; const at = std.mem.indexOfScalar(u32, p.children.items, old_child) orelse return false; if (self.contains(new_child, parent)) return false; self.detach(new_child); const pp = self.get(parent).?; // `detach` may have shifted the list if new_child was a sibling. const idx = std.mem.indexOfScalar(u32, pp.children.items, old_child) orelse at; pp.children.items[idx] = new_child; self.get(new_child).?.parent = parent; if (self.get(old_child)) |o| o.parent = 0; return true; } pub fn childCount(self: *Tree, id: u32) u32 { const n = self.get(id) orelse return 0; return @intCast(n.children.items.len); } pub fn childAt(self: *Tree, id: u32, index: u32) u32 { const n = self.get(id) orelse return 0; if (index >= n.children.items.len) return 0; return n.children.items[index]; } // ── Events ────────────────────────────────────────────────────────────── pub fn emit(self: *Tree, node: u32, name: []const u8, text: []const u8, num: f64) void { const owned = self.gpa.dupe(u8, text) catch return; self.events.append(self.gpa, .{ .node = node, .name = name, .text = owned, .num = num, }) catch self.gpa.free(owned); } /// Dequeue one event. True while there was one; the accessors below then /// describe it until the next poll. pub fn poll(self: *Tree) bool { if (self.current) |e| { self.gpa.free(e.text); self.current = null; } if (self.head >= self.events.items.len) { // Drained: reset rather than grow the backing array forever. self.events.clearRetainingCapacity(); self.head = 0; return false; } self.current = self.events.items[self.head]; self.head += 1; return true; } // ── Debugging ─────────────────────────────────────────────────────────── pub fn dump(self: *Tree, id: u32, out: *std.ArrayList(u8), depth: usize) void { const n = self.get(id) orelse return; out.appendNTimes(self.gpa, ' ', depth * 2) catch return; out.print(self.gpa, "<{s} #{d}", .{ n.tag, id }) catch return; var it = n.props.iterator(); while (it.next()) |kv| { switch (kv.value_ptr.*) { .str => |s| out.print(self.gpa, " {s}=\"{s}\"", .{ kv.key_ptr.*, s }) catch return, .num => |x| out.print(self.gpa, " {s}={d}", .{ kv.key_ptr.*, x }) catch return, .boolean => |b| out.print(self.gpa, " {s}={}", .{ kv.key_ptr.*, b }) catch return, } } out.appendSlice(self.gpa, ">\n") catch return; const kids = self.gpa.dupe(u32, n.children.items) catch return; defer self.gpa.free(kids); for (kids) |c| self.dump(c, out, depth + 1); } }; // ── Tests ─────────────────────────────────────────────────────────────────── // // The tree is the half worth testing without a window: everything here is what // a reconciler does to it between frames. const testing = std.testing; fn childrenOf(t: *Tree, id: u32) []const u32 { return (t.get(id) orelse unreachable).children.items; } test "root exists and is not freeable" { var t = try Tree.init(testing.allocator); defer t.deinit(); try testing.expectEqual(@as(u32, 1), t.root()); t.free_node(t.root()); try testing.expect(t.get(t.root()) != null); } test "props round-trip and coerce" { var t = try Tree.init(testing.allocator); defer t.deinit(); const n = t.new("label"); t.setStr(n, "text", "hello"); t.setNum(n, "size", 12.5); t.setBool(n, "active", true); try testing.expectEqualStrings("hello", t.getStr(n, "text")); try testing.expectEqual(@as(f64, 12.5), t.getNum(n, "size")); try testing.expect(t.getBool(n, "active")); // A bool reads as a number and a number as a bool; a missing prop is zero. try testing.expectEqual(@as(f64, 1), t.getNum(n, "active")); try testing.expectEqual(@as(f64, 0), t.getNum(n, "absent")); try testing.expectEqualStrings("", t.getStr(n, "absent")); // Overwriting a string frees the old one rather than leaking it. t.setStr(n, "text", "goodbye"); try testing.expectEqualStrings("goodbye", t.getStr(n, "text")); t.clear(n); try testing.expectEqualStrings("", t.getStr(n, "text")); } test "append moves a child rather than duplicating it" { var t = try Tree.init(testing.allocator); defer t.deinit(); const a = t.new("box"); const b = t.new("box"); const c = t.new("label"); try testing.expect(t.append(t.root(), a)); try testing.expect(t.append(t.root(), b)); try testing.expect(t.append(a, c)); try testing.expectEqualSlices(u32, &.{c}, childrenOf(&t, a)); // Re-appending elsewhere detaches from the old parent. try testing.expect(t.append(b, c)); try testing.expectEqualSlices(u32, &.{}, childrenOf(&t, a)); try testing.expectEqualSlices(u32, &.{c}, childrenOf(&t, b)); try testing.expectEqual(b, t.get(c).?.parent); } test "a node cannot be appended into its own subtree" { var t = try Tree.init(testing.allocator); defer t.deinit(); const a = t.new("box"); const b = t.new("box"); try testing.expect(t.append(t.root(), a)); try testing.expect(t.append(a, b)); // Both the direct cycle and the deeper one are refused; a walk that never // returns is a hang in the painter, not an error the caller would see. try testing.expect(!t.append(a, a)); try testing.expect(!t.append(b, a)); try testing.expectEqualSlices(u32, &.{b}, childrenOf(&t, a)); } test "insert_after places by sibling, and 0 means the front" { var t = try Tree.init(testing.allocator); defer t.deinit(); const p = t.new("box"); _ = t.append(t.root(), p); const a = t.new("label"); const b = t.new("label"); const c = t.new("label"); _ = t.append(p, a); _ = t.append(p, b); try testing.expect(t.insertAfter(p, c, a)); try testing.expectEqualSlices(u32, &.{ a, c, b }, childrenOf(&t, p)); const d = t.new("label"); try testing.expect(t.insertAfter(p, d, 0)); try testing.expectEqualSlices(u32, &.{ d, a, c, b }, childrenOf(&t, p)); } test "replace keeps position, including when the new child is a sibling" { var t = try Tree.init(testing.allocator); defer t.deinit(); const p = t.new("box"); _ = t.append(t.root(), p); const a = t.new("label"); const b = t.new("label"); const c = t.new("label"); _ = t.append(p, a); _ = t.append(p, b); _ = t.append(p, c); // Replacing with a node already in the list must not leave it twice, and // must not shift the slot out from under the index it was found at. try testing.expect(t.replace(p, a, c)); try testing.expectEqualSlices(u32, &.{ c, b }, childrenOf(&t, p)); try testing.expectEqual(@as(u32, 0), t.get(a).?.parent); } test "free takes the subtree and detaches from the parent" { var t = try Tree.init(testing.allocator); defer t.deinit(); const p = t.new("box"); _ = t.append(t.root(), p); const a = t.new("box"); const b = t.new("label"); _ = t.append(p, a); _ = t.append(a, b); t.free_node(a); try testing.expect(t.get(a) == null); try testing.expect(t.get(b) == null); try testing.expectEqualSlices(u32, &.{}, childrenOf(&t, p)); } test "a reused id is never the same widget identity" { var t = try Tree.init(testing.allocator); defer t.deinit(); const a = t.new("button"); _ = t.append(t.root(), a); const first = t.widgetId(a); t.free_node(a); const b = t.new("button"); // The id comes back — that is the point of the free list — but the identity // a painter keys widget state by must not, or the new node inherits the old // one's cursor, scroll position and animation. try testing.expectEqual(a, b); try testing.expect(first != t.widgetId(b)); } test "events queue in order and drain once" { var t = try Tree.init(testing.allocator); defer t.deinit(); const a = t.new("button"); t.emit(a, "click", "", 0); t.emit(a, "change", "typed", 3); try testing.expect(t.poll()); try testing.expectEqualStrings("click", t.current.?.name); try testing.expect(t.poll()); try testing.expectEqualStrings("change", t.current.?.name); try testing.expectEqualStrings("typed", t.current.?.text); try testing.expectEqual(@as(f64, 3), t.current.?.num); try testing.expect(!t.poll()); try testing.expect(t.current == null); } test "dump shows the shape" { var t = try Tree.init(testing.allocator); defer t.deinit(); const l = t.new("label"); t.setStr(l, "text", "hi"); _ = t.append(t.root(), l); var out: std.ArrayList(u8) = .empty; defer out.deinit(testing.allocator); t.dump(t.root(), &out, 0); try testing.expectEqualStrings( \\ \\