a73x

layout: collectLeafIds propagates allocation failure instead of truncating

3262d8a5   forge/collect-leaf-ids-oom → main

2 files changed

src/client/layout.zig
Old New
@@ -273,7 +273,7 @@ pub const Tree = struct {
273 if (focus) |fid| { 273 if (focus) |fid| {
274 var ids: std.ArrayListUnmanaged(u8) = .{}; 274 var ids: std.ArrayListUnmanaged(u8) = .{};
275 defer ids.deinit(self.alloc); 275 defer ids.deinit(self.alloc);
276 collectLeafIds(self.alloc, self.root, &ids); 276 try collectLeafIds(self.alloc, self.root, &ids);
277 for (ids.items, 0..) |id, k| { 277 for (ids.items, 0..) |id, k| {
278 if (id == fid) { 278 if (id == fid) {
279 try writer.print("focus {d}\n", .{k}); 279 try writer.print("focus {d}\n", .{k});
@@ -305,12 +305,16 @@ pub const Tree = struct {
305 /// containers collapse. Removals ALL happen before any rewrite, so old ids 305 /// containers collapse. Removals ALL happen before any rewrite, so old ids
306 /// stay addressable through the removal pass; the rewrite is one pass, so a 306 /// stay addressable through the removal pass; the rewrite is one pass, so a
307 /// new id cannot collide with a not-yet-rewritten old one. 307 /// new id cannot collide with a not-yet-rewritten old one.
308 pub fn remapLeaves(self: *Tree, map: []const ?u8) void { 308 ///
309 /// `error.OutOfMemory` leaves the tree UNTOUCHED: the only allocation is
310 /// the id list, and it is taken before the first mutation, so a caller that
311 /// gives up on the error is giving up on a tree it never modified.
312 pub fn remapLeaves(self: *Tree, map: []const ?u8) std.mem.Allocator.Error!void {
309 // Collect ids first because removal mutates the tree and may 313 // Collect ids first because removal mutates the tree and may
310 // collapse containers, invalidating node pointers. 314 // collapse containers, invalidating node pointers.
311 var ids: std.ArrayListUnmanaged(u8) = .{}; 315 var ids: std.ArrayListUnmanaged(u8) = .{};
312 defer ids.deinit(self.alloc); 316 defer ids.deinit(self.alloc);
313 collectLeafIds(self.alloc, self.root, &ids); 317 try collectLeafIds(self.alloc, self.root, &ids);
314 318
315 // Pass 1: removals. All null-mapped leaves are removed before any 319 // Pass 1: removals. All null-mapped leaves are removed before any
316 // id rewrite, so the old ids remain addressable throughout. 320 // id rewrite, so the old ids remain addressable throughout.
@@ -696,12 +700,17 @@ fn countLeadingSpaces(line: []const u8) usize {
696 return i; 700 return i;
697 } 701 }
698 702
699 fn collectLeafIds(alloc: std.mem.Allocator, node: ?*const Node, ids: *std.ArrayListUnmanaged(u8)) void { 703 /// Depth-first leaf ids, in encounter order. The allocation failure is
704 /// PROPAGATED, never swallowed: a short list is not a smaller tree, it is a
705 /// wrong answer about this one. Dropping a leaf here made `serialize` write a
706 /// `focus K` naming a different pane, and made `remapLeaves` skip a removal so
707 /// a pane the wall no longer has stayed in the saved tree.
708 fn collectLeafIds(alloc: std.mem.Allocator, node: ?*const Node, ids: *std.ArrayListUnmanaged(u8)) std.mem.Allocator.Error!void {
700 const n = node orelse return; 709 const n = node orelse return;
701 switch (n.*) { 710 switch (n.*) {
702 .leaf => |t| ids.append(alloc, t) catch {}, 711 .leaf => |t| try ids.append(alloc, t),
703 .container => |c| { 712 .container => |c| {
704 for (c.children.items) |child| collectLeafIds(alloc, child, ids); 713 for (c.children.items) |child| try collectLeafIds(alloc, child, ids);
705 }, 714 },
706 } 715 }
707 } 716 }
@@ -1255,7 +1264,7 @@ test "remapLeaves: null removes, containers collapse, ids rewrite in one pass" {
1255 try t.splitBelow(1, 2); 1264 try t.splitBelow(1, 2);
1256 // Leaf 1 has no wall line; 0 and 2 map to tiles 2 and 0 (a swap, the 1265 // Leaf 1 has no wall line; 0 and 2 map to tiles 2 and 0 (a swap, the
1257 // collision-prone case a two-pass rewrite gets wrong). 1266 // collision-prone case a two-pass rewrite gets wrong).
1258 t.remapLeaves(&[_]?u8{ 2, null, 0 }); 1267 try t.remapLeaves(&[_]?u8{ 2, null, 0 });
1259 try std.testing.expectEqual(@as(usize, 2), t.count()); 1268 try std.testing.expectEqual(@as(usize, 2), t.count());
1260 const f = try t.flatten(alloc, 24, 80, .{ .rows = 2, .cols = 3 }, null); 1269 const f = try t.flatten(alloc, 24, 80, .{ .rows = 2, .cols = 3 }, null);
1261 defer f.deinit(alloc); 1270 defer f.deinit(alloc);
@@ -1264,6 +1273,58 @@ test "remapLeaves: null removes, containers collapse, ids rewrite in one pass" {
1264 try std.testing.expect(f.rectOf(1) == null); 1273 try std.testing.expect(f.rectOf(1) == null);
1265 } 1274 }
1266 1275
1276 test "serialize: a failed leaf-id collection refuses rather than misnaming the focus" {
1277 const alloc = std.testing.allocator;
1278 var t = Tree.init(alloc);
1279 defer t.deinit();
1280 try t.addFirst(0);
1281 try t.splitRight(0, 1);
1282 try t.splitBelow(1, 2); // encounter order: 0, 1, 2
1283 const spellings = [_][]const u8{ "a", "b", "c" };
1284 var buf: std.ArrayListUnmanaged(u8) = .{};
1285 defer buf.deinit(alloc);
1286
1287 // The tree is built through the test allocator and only the id list is
1288 // taken through the failing one, so the failure lands on exactly the
1289 // allocation under test. `buf` keeps the test allocator: the node lines
1290 // are written before the id walk and are not what this pins.
1291 var failing = std.testing.FailingAllocator.init(alloc, .{ .fail_index = 0 });
1292 t.alloc = failing.allocator();
1293 const err = t.serialize(&spellings, 2, buf.writer(alloc));
1294 t.alloc = alloc;
1295
1296 try std.testing.expectError(error.OutOfMemory, err);
1297 // Not "focus 0" or a missing focus line pointing the next attach at the
1298 // wrong pane: a truncated walk finds leaf 2 at no index, or at the index
1299 // of whichever leaf survived the truncation.
1300 try std.testing.expect(std.mem.indexOf(u8, buf.items, "focus") == null);
1301 }
1302
1303 test "remapLeaves: a failed leaf-id collection leaves the tree untouched" {
1304 const alloc = std.testing.allocator;
1305 var t = Tree.init(alloc);
1306 defer t.deinit();
1307 try t.addFirst(0);
1308 try t.splitRight(0, 1);
1309 try t.splitBelow(1, 2);
1310
1311 var failing = std.testing.FailingAllocator.init(alloc, .{ .fail_index = 0 });
1312 t.alloc = failing.allocator();
1313 const err = t.remapLeaves(&[_]?u8{ 2, null, 0 });
1314 t.alloc = alloc;
1315
1316 try std.testing.expectError(error.OutOfMemory, err);
1317 // All three leaves still there under their original ids: the collection
1318 // is taken before the first removal, so the caller that gives up gets the
1319 // tree it handed in, not one with an arbitrary prefix of the map applied.
1320 try std.testing.expectEqual(@as(usize, 3), t.count());
1321 const f = try t.flatten(alloc, 24, 80, .{ .rows = 2, .cols = 3 }, null);
1322 defer f.deinit(alloc);
1323 try std.testing.expect(f.rectOf(0) != null);
1324 try std.testing.expect(f.rectOf(1) != null);
1325 try std.testing.expect(f.rectOf(2) != null);
1326 }
1327
1267 test "parse: a zero-weight child degrades to null, not a divide by zero" { 1328 test "parse: a zero-weight child degrades to null, not a divide by zero" {
1268 const alloc = std.testing.allocator; 1329 const alloc = std.testing.allocator;
1269 // Root cells are read and discarded, so only a non-root zero is a 1330 // Root cells are read and discarded, so only a non-root zero is a
src/tui/wall_layout.zig
Old New
@@ -410,7 +410,11 @@ fn seedAttempt(
410 parsed.deinit(alloc); 410 parsed.deinit(alloc);
411 return null; 411 return null;
412 } 412 }
413 parsed.tree.remapLeaves(map); 413 parsed.tree.remapLeaves(map) catch {
414 plan.deinit(alloc);
415 parsed.deinit(alloc);
416 return null;
417 };
414 if (base == 1 and entry_at == null) { 418 if (base == 1 and entry_at == null) {
415 const anchor: u8 = if (focus) |f| @intCast(f) else @intCast(base); 419 const anchor: u8 = if (focus) |f| @intCast(f) else @intCast(base);
416 parsed.tree.insert(anchor, 0) catch { 420 parsed.tree.insert(anchor, 0) catch {