a73x

b5c91a0e

feat: layout.zig grows the wall's container tree

a73x   2026-08-24 13:36

Commit message
feat: layout.zig grows the wall's container tree

A pure layer-1 module that owns pane geometry: an i3-style nestable
split tree (`.beside` / `.stacked`) with weighted children, flattening
to the `Rect` list every tile claims. The remainder rule reproduces
`layoutStripes`' "leftover rows to the earliest children" exactly, so
the stripe cut survives as the degenerate single-container tree — the
wallview swap that replaces stripes with this tree will move no pixel.

Rails (one column per `.beside` gap) are reported alongside rects so
relayout can paint them; tiles never touch them. Floors arrive as a
parameter so the module knows nothing of protocol minimums or label
arithmetic — a leaf under the floor is `error.TooSmall`, and the caller
refuses the operation rather than shrinking a pane below the daemon's
floor. Fullscreen is a rect assignment, not a tree change: the focus
tile gets the terminal, every other tile gets 0×0.

Co-Authored-By: Claude Fable 5 <noreply@anthropic.com>
build.zig
Old New
@@ -209,6 +209,10 @@ const mod_table = [_]ModSpec{
209 // types in, and knows nothing about transports — which is what lets its 209 // types in, and knows nothing about transports — which is what lets its
210 // tests drive every painter through a pipe with no daemon anywhere. 210 // tests drive every painter through a pipe with no daemon anywhere.
211 .{ .name = "paint", .path = "src/paint.zig", .layer = 1, .imports = &.{ "engine", "protocol" } }, 211 .{ .name = "paint", .path = "src/paint.zig", .layer = 1, .imports = &.{ "engine", "protocol" } },
212 // The container tree that owns the wall's pane geometry. Pure: no tty,
213 // no engine, no imports — floors arrive as a parameter so wallview can
214 // pass the protocol minimums without this module knowing they are that.
215 .{ .name = "layout", .path = "src/layout.zig", .layer = 1 },
212 // What a press, a drag and a release MEAN, and nothing else: no tty, no 216 // What a press, a drag and a release MEAN, and nothing else: no tty, no
213 // transport, no engine, no allocation. It imports nothing at all, and is 217 // transport, no engine, no allocation. It imports nothing at all, and is
214 // still layer 1 rather than 0 — layer 0 is this program's vocabulary 218 // still layer 1 rather than 0 — layer 0 is this program's vocabulary
@@ -537,12 +541,12 @@ fn docGate(b: *std.Build, target: std.Build.ResolvedTarget, check_step: *std.Bui
537 /// escape pins. mux and exe are executable roots but carry the argument 541 /// escape pins. mux and exe are executable roots but carry the argument
538 /// parsers — a test that is never built is not a test (decisions.md). 542 /// parsers — a test that is never built is not a test (decisions.md).
539 const test_order = [_][]const u8{ 543 const test_order = [_][]const u8{
540 "script", "select", "protocol", "client_core", "interact", "engine", "pty", 544 "script", "select", "protocol", "client_core", "interact", "engine", "pty",
541 "delta", "cmd", "wall", "shellint", "replica", "keymap", "webhub", 545 "delta", "cmd", "wall", "shellint", "replica", "keymap", "webhub",
542 "wallview", "sockpath", "muxa", "server", "client", "proxy", "mux", 546 "wallview", "sockpath", "muxa", "server", "client", "proxy", "mux",
543 "quic", "quic_server", "exe", "testtmp", "quic_client", "predict", "rawmode", 547 "quic", "quic_server", "exe", "testtmp", "quic_client", "predict", "rawmode",
544 "delaypipe", "xdg", "spawn", "handoff", "paint", "render", "ptyclient", 548 "delaypipe", "xdg", "spawn", "handoff", "paint", "layout", "render",
545 "webhub_main", "wsclient", 549 "ptyclient", "webhub_main", "wsclient",
546 }; 550 };
547 551
548 comptime { 552 comptime {
docscheck.budget
Old New
@@ -8,6 +8,7 @@ engine.zig 0
8 handoff.zig 0 8 handoff.zig 0
9 interact.zig 0 9 interact.zig 0
10 keymap.zig 0 10 keymap.zig 0
11 layout.zig 0
11 main.zig 0 12 main.zig 0
12 muxa.zig 0 13 muxa.zig 0
13 mux_main.zig 0 14 mux_main.zig 0
src/layout.zig
Old New
@@ -0,0 +1,482 @@
1 //! The wall's container tree: where pane rects come from. An i3-style
2 //! nestable split tree — `.beside` children share columns left→right,
3 //! `.stacked` children share rows top→-bottom — that flattens to the
4 //! `Rect` list every tile claims. Who claims them is wallview's
5 //! business; the tree answers geometry and nothing else.
6 //!
7 //! The remainder rule reproduces `layoutStripes`' "leftover rows to the
8 //! earliest children" exactly (wallview.zig's stripe era), so the
9 //! stripe cut survives as the degenerate single-container tree — the
10 //! wallview swap moves no pixel. Rails (one column per `.beside` gap) are reported
11 //! alongside the rects so relayout can paint them; tiles never touch
12 //! rails because their clears are span-bounded (paint.zig).
13 //!
14 //! Floors are a parameter, not a constant: wallview passes the protocol
15 //! minimums plus its label-row arithmetic. A leaf whose rect would fall
16 //! under the floor is `error.TooSmall`, and the caller refuses the
17 //! operation rather than shrinking a pane below the daemon's floor.
18
19 const std = @import("std");
20
21 pub const Orient = enum { beside, stacked };
22 pub const Dir = enum { left, down, up, right };
23
24 pub const Rect = struct { top: u16, left: u16, rows: u16, cols: u16 };
25
26 pub const Rail = struct { col: u16, top: u16, rows: u16 };
27
28 pub const Placed = struct { tile: u8, rect: Rect };
29
30 pub const Flat = struct {
31 placed: []Placed,
32 rails: []Rail,
33
34 pub fn deinit(self: *Flat, alloc: std.mem.Allocator) void {
35 alloc.free(self.placed);
36 alloc.free(self.rails);
37 }
38
39 pub fn rectOf(self: Flat, tile: u8) ?Rect {
40 for (self.placed) |p| {
41 if (p.tile == tile) return p.rect;
42 }
43 return null;
44 }
45 };
46
47 pub const Floors = struct { rows: u16, cols: u16 };
48
49 const Node = union(enum) {
50 leaf: u8,
51 container: *Container,
52 };
53
54 const Container = struct {
55 orient: Orient,
56 children: std.ArrayListUnmanaged(*Node),
57 weights: std.ArrayListUnmanaged(u32),
58 };
59
60 pub const Tree = struct {
61 alloc: std.mem.Allocator,
62 root: ?*Node = null,
63
64 pub fn init(alloc: std.mem.Allocator) Tree {
65 return .{ .alloc = alloc };
66 }
67
68 pub fn deinit(self: *Tree) void {
69 if (self.root) |r| self.freeNode(r);
70 self.root = null;
71 }
72
73 fn freeNode(self: *Tree, node: *Node) void {
74 switch (node.*) {
75 .leaf => {},
76 .container => |c| {
77 for (c.children.items) |child| self.freeNode(child);
78 c.children.deinit(self.alloc);
79 c.weights.deinit(self.alloc);
80 self.alloc.destroy(c);
81 },
82 }
83 self.alloc.destroy(node);
84 }
85
86 pub fn count(self: *const Tree) usize {
87 if (self.root) |r| return countLeaves(r);
88 return 0;
89 }
90
91 fn countLeaves(node: *const Node) usize {
92 return switch (node.*) {
93 .leaf => 1,
94 .container => |c| blk: {
95 var n: usize = 0;
96 for (c.children.items) |child| n += countLeaves(child);
97 break :blk n;
98 },
99 };
100 }
101
102 pub fn addFirst(self: *Tree, tile: u8) !void {
103 std.debug.assert(self.root == null);
104 const node = try self.alloc.create(Node);
105 node.* = .{ .leaf = tile };
106 self.root = node;
107 }
108
109 const Found = struct { node: *Node, parent: ?*Container, index: usize };
110
111 fn findLeaf(self: *const Tree, tile: u8) ?Found {
112 if (self.root) |r| return findLeafIn(r, null, 0, tile);
113 return null;
114 }
115
116 fn findLeafIn(node: *Node, parent: ?*Container, index: usize, tile: u8) ?Found {
117 switch (node.*) {
118 .leaf => |t| {
119 if (t == tile) return .{ .node = node, .parent = parent, .index = index };
120 return null;
121 },
122 .container => |c| {
123 for (c.children.items, 0..) |child, i| {
124 if (findLeafIn(child, c, i, tile)) |f| return f;
125 }
126 return null;
127 },
128 }
129 }
130
131 /// Insert `tile` as the next sibling of the focused leaf in its parent
132 /// container. If the focused leaf IS the root, the root becomes a
133 /// `.stacked` container holding `[old, new]` — matching today's stripes.
134 pub fn insert(self: *Tree, focus: u8, tile: u8) !void {
135 const found = self.findLeaf(focus) orelse return error.NotFound;
136 if (found.parent) |p| {
137 const new_node = try self.alloc.create(Node);
138 new_node.* = .{ .leaf = tile };
139 const w = p.weights.items[found.index];
140 try p.children.insert(self.alloc, found.index + 1, new_node);
141 try p.weights.insert(self.alloc, found.index + 1, w);
142 } else {
143 // Root is a leaf — wrap it in a stacked container. The old
144 // node stays a leaf child; a new node holds the container.
145 const c = try self.alloc.create(Container);
146 c.* = .{ .orient = .stacked, .children = .empty, .weights = .empty };
147 try c.children.append(self.alloc, found.node);
148 const new_node = try self.alloc.create(Node);
149 new_node.* = .{ .leaf = tile };
150 try c.children.append(self.alloc, new_node);
151 try c.weights.append(self.alloc, 1);
152 try c.weights.append(self.alloc, 1);
153 const c_node = try self.alloc.create(Node);
154 c_node.* = .{ .container = c };
155 self.root = c_node;
156 }
157 }
158
159 /// Replace the focused leaf with a two-child container of the forced
160 /// orientation holding `[old, new]`, weights `{1,1}`. The old leaf node
161 /// stays a leaf; a new node holds the container and takes its slot.
162 fn split(self: *Tree, focus: u8, tile: u8, orient: Orient) !void {
163 const found = self.findLeaf(focus) orelse return error.NotFound;
164
165 const c = try self.alloc.create(Container);
166 c.* = .{ .orient = orient, .children = .empty, .weights = .empty };
167 try c.children.append(self.alloc, found.node);
168 const new_node = try self.alloc.create(Node);
169 new_node.* = .{ .leaf = tile };
170 try c.children.append(self.alloc, new_node);
171 try c.weights.append(self.alloc, 1);
172 try c.weights.append(self.alloc, 1);
173
174 const c_node = try self.alloc.create(Node);
175 c_node.* = .{ .container = c };
176
177 if (found.parent) |p| {
178 p.children.items[found.index] = c_node;
179 } else {
180 self.root = c_node;
181 }
182 }
183
184 pub fn splitRight(self: *Tree, focus: u8, tile: u8) !void {
185 try self.split(focus, tile, .beside);
186 }
187
188 pub fn splitBelow(self: *Tree, focus: u8, tile: u8) !void {
189 try self.split(focus, tile, .stacked);
190 }
191
192 /// Delete the leaf; a container left with one child dissolves — the child
193 /// takes its place in the grandparent (or becomes root).
194 pub fn remove(self: *Tree, tile: u8) void {
195 const found = self.findLeaf(tile) orelse return;
196 if (found.parent) |p| {
197 self.alloc.destroy(found.node);
198 _ = p.children.orderedRemove(found.index);
199 _ = p.weights.orderedRemove(found.index);
200 if (p.children.items.len == 1) {
201 const sole = p.children.items[0];
202 self.replaceContainer(p, sole);
203 }
204 } else {
205 self.alloc.destroy(found.node);
206 self.root = null;
207 }
208 }
209
210 /// Replace the node holding `c` with `sole` in the grandparent, or make
211 /// `sole` the root. Then free `c` and its node (but not `sole`).
212 fn replaceContainer(self: *Tree, c: *Container, sole: *Node) void {
213 if (self.root) |r| {
214 if (r.* == .container and r.container == c) {
215 self.root = sole;
216 c.children.deinit(self.alloc);
217 c.weights.deinit(self.alloc);
218 self.alloc.destroy(c);
219 self.alloc.destroy(r);
220 return;
221 }
222 }
223 self.replaceContainerIn(self.root.?, c, sole);
224 }
225
226 fn replaceContainerIn(self: *Tree, node: *Node, c: *Container, sole: *Node) void {
227 switch (node.*) {
228 .leaf => {},
229 .container => |cont| {
230 for (cont.children.items) |child| {
231 switch (child.*) {
232 .container => |cc| {
233 if (cc == c) {
234 child.* = sole.*;
235 self.alloc.destroy(sole);
236 c.children.deinit(self.alloc);
237 c.weights.deinit(self.alloc);
238 self.alloc.destroy(c);
239 return;
240 }
241 self.replaceContainerIn(child, c, sole);
242 },
243 .leaf => {},
244 }
245 }
246 },
247 }
248 }
249
250 pub fn flatten(
251 self: *const Tree,
252 alloc: std.mem.Allocator,
253 rows: u16,
254 cols: u16,
255 floors: Floors,
256 fullscreen: ?u8,
257 ) error{ TooSmall, OutOfMemory }!Flat {
258 var placed = std.ArrayList(Placed).empty;
259 var rails = std.ArrayList(Rail).empty;
260 errdefer {
261 placed.deinit(alloc);
262 rails.deinit(alloc);
263 }
264
265 if (self.root) |r| {
266 if (fullscreen) |fs_tile| {
267 try flattenFullscreen(alloc, &placed, r, rows, cols, fs_tile);
268 } else {
269 try flattenNode(alloc, &placed, &rails, r, 0, 0, rows, cols, floors);
270 }
271 }
272
273 return .{
274 .placed = try placed.toOwnedSlice(alloc),
275 .rails = try rails.toOwnedSlice(alloc),
276 };
277 }
278 };
279
280 fn flattenFullscreen(
281 alloc: std.mem.Allocator,
282 placed: *std.ArrayList(Placed),
283 node: *const Node,
284 rows: u16,
285 cols: u16,
286 fs_tile: u8,
287 ) error{OutOfMemory}!void {
288 switch (node.*) {
289 .leaf => |t| {
290 if (t == fs_tile) {
291 try placed.append(alloc, .{ .tile = t, .rect = .{ .top = 0, .left = 0, .rows = rows, .cols = cols } });
292 } else {
293 try placed.append(alloc, .{ .tile = t, .rect = .{ .top = 0, .left = 0, .rows = 0, .cols = 0 } });
294 }
295 },
296 .container => |c| {
297 for (c.children.items) |child| {
298 try flattenFullscreen(alloc, placed, child, rows, cols, fs_tile);
299 }
300 },
301 }
302 }
303
304 fn flattenNode(
305 alloc: std.mem.Allocator,
306 placed: *std.ArrayList(Placed),
307 rails: *std.ArrayList(Rail),
308 node: *const Node,
309 top: u16,
310 left: u16,
311 rows: u16,
312 cols: u16,
313 floors: Floors,
314 ) error{ TooSmall, OutOfMemory }!void {
315 switch (node.*) {
316 .leaf => |t| {
317 if (rows < floors.rows or cols < floors.cols) return error.TooSmall;
318 try placed.append(alloc, .{ .tile = t, .rect = .{ .top = top, .left = left, .rows = rows, .cols = cols } });
319 },
320 .container => |c| {
321 const n = c.children.items.len;
322 if (n == 0) return;
323
324 var total_weight: u64 = 0;
325 for (c.weights.items) |w| total_weight += w;
326
327 switch (c.orient) {
328 .stacked => {
329 var base = try alloc.alloc(u16, n);
330 defer alloc.free(base);
331 var sum: u64 = 0;
332 for (c.weights.items, 0..) |w, i| {
333 base[i] = @intCast(@as(u64, rows) * w / total_weight);
334 sum += base[i];
335 }
336 var rem = rows - @as(u16, @intCast(sum));
337 var i: usize = 0;
338 while (rem > 0 and i < n) : (i += 1) {
339 base[i] += 1;
340 rem -= 1;
341 }
342 var cur_top = top;
343 for (c.children.items, 0..) |child, ci| {
344 try flattenNode(alloc, placed, rails, child, cur_top, left, base[ci], cols, floors);
345 cur_top += base[ci];
346 }
347 },
348 .beside => {
349 // Reserve n-1 columns for rails, then split cols by weight.
350 const rail_count: u16 = @intCast(n - 1);
351 const avail = cols - rail_count;
352 var base = try alloc.alloc(u16, n);
353 defer alloc.free(base);
354 var sum: u64 = 0;
355 for (c.weights.items, 0..) |w, i| {
356 base[i] = @intCast(@as(u64, avail) * w / total_weight);
357 sum += base[i];
358 }
359 var rem = avail - @as(u16, @intCast(sum));
360 var i: usize = 0;
361 while (rem > 0 and i < n) : (i += 1) {
362 base[i] += 1;
363 rem -= 1;
364 }
365 var cur_left = left;
366 for (c.children.items, 0..) |child, ci| {
367 try flattenNode(alloc, placed, rails, child, top, cur_left, rows, base[ci], floors);
368 cur_left += base[ci];
369 if (ci < n - 1) {
370 try rails.append(alloc, .{ .col = cur_left, .top = top, .rows = rows });
371 cur_left += 1;
372 }
373 }
374 },
375 }
376 },
377 }
378 }
379
380 // ======================================================================
381 // TESTS
382 // ======================================================================
383
384 test "a lone tile owns the whole terminal, no rails" {
385 var t = Tree.init(std.testing.allocator);
386 defer t.deinit();
387 try t.addFirst(7);
388 var f = try t.flatten(std.testing.allocator, 24, 80, .{ .rows = 2, .cols = 2 }, null);
389 defer f.deinit(std.testing.allocator);
390 try std.testing.expectEqual(@as(usize, 1), f.placed.len);
391 try std.testing.expectEqual(Rect{ .top = 0, .left = 0, .rows = 24, .cols = 80 }, f.rectOf(7).?);
392 try std.testing.expectEqual(@as(usize, 0), f.rails.len);
393 }
394
395 test "a stacked cut reproduces layoutStripes' remainder-at-the-top rule" {
396 var t = Tree.init(std.testing.allocator);
397 defer t.deinit();
398 try t.addFirst(0);
399 try t.insert(0, 1);
400 try t.insert(1, 2);
401 var f = try t.flatten(std.testing.allocator, 25, 80, .{ .rows = 2, .cols = 2 }, null);
402 defer f.deinit(std.testing.allocator);
403 try std.testing.expectEqual(Rect{ .top = 0, .left = 0, .rows = 9, .cols = 80 }, f.rectOf(0).?);
404 try std.testing.expectEqual(Rect{ .top = 9, .left = 0, .rows = 8, .cols = 80 }, f.rectOf(1).?);
405 try std.testing.expectEqual(Rect{ .top = 17, .left = 0, .rows = 8, .cols = 80 }, f.rectOf(2).?);
406 }
407
408 test "a beside cut spends one column per rail" {
409 var t = Tree.init(std.testing.allocator);
410 defer t.deinit();
411 try t.addFirst(0);
412 try t.splitRight(0, 1);
413 var f = try t.flatten(std.testing.allocator, 24, 81, .{ .rows = 2, .cols = 2 }, null);
414 defer f.deinit(std.testing.allocator);
415 try std.testing.expectEqual(Rect{ .top = 0, .left = 0, .rows = 24, .cols = 40 }, f.rectOf(0).?);
416 try std.testing.expectEqual(Rect{ .top = 0, .left = 41, .rows = 24, .cols = 40 }, f.rectOf(1).?);
417 try std.testing.expectEqual(Rail{ .col = 40, .top = 0, .rows = 24 }, f.rails[0]);
418 }
419
420 test "splitBelow nests: 1 beside (2 over 3)" {
421 var t = Tree.init(std.testing.allocator);
422 defer t.deinit();
423 try t.addFirst(0);
424 try t.splitRight(0, 1);
425 try t.splitBelow(1, 2);
426 var f = try t.flatten(std.testing.allocator, 24, 81, .{ .rows = 2, .cols = 2 }, null);
427 defer f.deinit(std.testing.allocator);
428 try std.testing.expectEqual(Rect{ .top = 0, .left = 0, .rows = 24, .cols = 40 }, f.rectOf(0).?);
429 try std.testing.expectEqual(Rect{ .top = 0, .left = 41, .rows = 12, .cols = 40 }, f.rectOf(1).?);
430 try std.testing.expectEqual(Rect{ .top = 12, .left = 41, .rows = 12, .cols = 40 }, f.rectOf(2).?);
431 }
432
433 test "remove collapses a single-child container into its parent" {
434 var t = Tree.init(std.testing.allocator);
435 defer t.deinit();
436 try t.addFirst(0);
437 try t.splitRight(0, 1);
438 try t.splitBelow(1, 2);
439 t.remove(2);
440 var f = try t.flatten(std.testing.allocator, 24, 81, .{ .rows = 2, .cols = 2 }, null);
441 defer f.deinit(std.testing.allocator);
442 try std.testing.expectEqual(Rect{ .top = 0, .left = 41, .rows = 24, .cols = 40 }, f.rectOf(1).?);
443 t.remove(1);
444 try std.testing.expectEqual(@as(usize, 1), t.count());
445 }
446
447 test "a cut under the floors is refused, rails included" {
448 var t = Tree.init(std.testing.allocator);
449 defer t.deinit();
450 try t.addFirst(0);
451 try t.splitRight(0, 1);
452 try std.testing.expectError(error.TooSmall, t.flatten(std.testing.allocator, 24, 4, .{ .rows = 2, .cols = 2 }, null));
453 }
454
455 test "fullscreen is a rect assignment, not a tree change" {
456 var t = Tree.init(std.testing.allocator);
457 defer t.deinit();
458 try t.addFirst(0);
459 try t.splitRight(0, 1);
460 var f = try t.flatten(std.testing.allocator, 24, 81, .{ .rows = 2, .cols = 2 }, 1);
461 defer f.deinit(std.testing.allocator);
462 try std.testing.expectEqual(Rect{ .top = 0, .left = 0, .rows = 24, .cols = 81 }, f.rectOf(1).?);
463 try std.testing.expectEqual(Rect{ .top = 0, .left = 0, .rows = 0, .cols = 0 }, f.rectOf(0).?);
464 try std.testing.expectEqual(@as(usize, 0), f.rails.len);
465 var g = try t.flatten(std.testing.allocator, 24, 81, .{ .rows = 2, .cols = 2 }, null);
466 defer g.deinit(std.testing.allocator);
467 try std.testing.expectEqual(@as(u16, 40), g.rectOf(0).?.cols);
468 }
469
470 test "insert lands beside the focus, along the container's orientation" {
471 var t = Tree.init(std.testing.allocator);
472 defer t.deinit();
473 try t.addFirst(0);
474 try t.splitRight(0, 1);
475 try t.insert(0, 2);
476 var f = try t.flatten(std.testing.allocator, 24, 82, .{ .rows = 2, .cols = 2 }, null);
477 defer f.deinit(std.testing.allocator);
478 const r0 = f.rectOf(0).?;
479 const r2 = f.rectOf(2).?;
480 const r1 = f.rectOf(1).?;
481 try std.testing.expect(r0.left < r2.left and r2.left < r1.left);
482 }