preview.zig (7937B)
1 //! Bounded constructor snapshots. Labels belong to one snapshot, never the arena 2 //! or the owned-handle API. Frontier children remain undemanded at the node cap. 3 const std = @import("std"); 4 const Arena = @import("arena.zig").Arena; 5 const reduce = @import("reduce.zig"); 6 7 const Record = struct { label: u32, kind: u32, left: u32 = 0, right: u32 = 0 }; 8 const Labels = struct { 9 ids: [513]u32 = undefined, 10 len: usize = 0, 11 fn intern(self: *Labels, id: u32) u32 { 12 if (std.mem.indexOfScalar(u32, self.ids[0..self.len], id)) |index| return @intCast(index); 13 const index = self.len; 14 self.ids[index] = id; 15 self.len += 1; 16 return @intCast(index); 17 } 18 }; 19 20 // Binary v1: little-endian u32 version, root label, record count, truncated; 21 // followed by [label, constructor arity (0/1/2), left, right] records. 22 // Fuel is PER constructor demand, not a whole-snapshot fuel budget. 23 pub fn capture(arena: *Arena, root: u32, limit: u32, fuel: u64) ![]u8 { 24 return captureWithFuel(arena, root, limit, fuel); 25 } 26 pub fn captureUnboundedWork(arena: *Arena, root: u32, limit: u32) ![]u8 { 27 return captureWithFuel(arena, root, limit, null); 28 } 29 fn captureWithFuel(arena: *Arena, root: u32, limit: u32, fuel: ?u64) ![]u8 { 30 if (limit == 0 or limit > 256) return error.InvalidData; 31 const base = arena.roots.items.len; 32 try arena.roots.append(arena.allocator, root); 33 defer arena.roots.shrinkRetainingCapacity(base); 34 var labels: Labels = .{}; 35 var pending: [513]u32 = undefined; 36 pending[0] = labels.intern(root); 37 var pending_len: usize = 1; 38 var seen = [_]bool{false} ** 513; 39 var records: [256]Record = undefined; 40 var count: usize = 0; 41 var truncated = false; 42 while (pending_len > 0) { 43 pending_len -= 1; 44 const label = pending[pending_len]; 45 if (seen[label]) continue; 46 if (count == limit) { 47 truncated = true; 48 break; 49 } 50 const normal = if (fuel) |budget| try reduce.reduce(labels.ids[label], arena, budget) else try reduce.reduceUnbounded(labels.ids[label], arena); 51 const node = arena.get(normal).*; // Never retain a pointer over allocation/GC. 52 seen[label] = true; 53 var record = Record{ .label = label, .kind = 0 }; 54 switch (node) { 55 .leaf => {}, 56 .stem => |s| { 57 record.kind = 1; 58 record.left = labels.intern(s.child); 59 pending[pending_len] = record.left; 60 pending_len += 1; 61 }, 62 .fork => |f| { 63 record.kind = 2; 64 record.left = labels.intern(f.left); 65 record.right = labels.intern(f.right); 66 pending[pending_len] = record.right; 67 pending[pending_len + 1] = record.left; 68 pending_len += 2; 69 }, 70 .app => unreachable, 71 } 72 records[count] = record; 73 count += 1; 74 } 75 const bytes = try arena.allocator.alloc(u8, 16 + count * 16); 76 const header = [_]u32{ 1, 0, @intCast(count), @intFromBool(truncated) }; 77 for (header, 0..) |word, i| std.mem.writeInt(u32, bytes[i * 4 ..][0..4], word, .little); 78 for (records[0..count], 0..) |record, i| { 79 const words = [_]u32{ record.label, record.kind, record.left, record.right }; 80 for (words, 0..) |word, j| std.mem.writeInt(u32, bytes[16 + i * 16 + j * 4 ..][0..4], word, .little); 81 } 82 return bytes; 83 } 84 85 fn allocationProbe(allocator: std.mem.Allocator) !void { 86 var arena = Arena.init(allocator); 87 defer arena.deinit(); 88 const leaf = try arena.alloc(.leaf); 89 var root = leaf; 90 for (0..31) |_| root = try arena.alloc(.{ .fork = .{ .left = root, .right = root } }); 91 arena.gc_enabled = true; 92 try arena.setGcPolicy(1, 1); 93 const bytes = try captureUnboundedWork(&arena, root, 32); 94 defer allocator.free(bytes); 95 try std.testing.expectEqual(@as(usize, 16 + 32 * 16), bytes.len); 96 try std.testing.expectEqual(@as(u32, 0), std.mem.readInt(u32, bytes[12..16], .little)); 97 try std.testing.expectEqual(@as(usize, 0), arena.roots.items.len); 98 } 99 100 test "preview preserves sharing, survives GC, and cleans every allocation failure" { 101 try std.testing.checkAllAllocationFailures(std.testing.allocator, allocationProbe, .{}); 102 } 103 104 // Result serialization has a larger, explicitly bounded transport profile. 105 // It does not relax the interactive preview's limit or bound reduction work. 106 pub fn snapshotUnboundedWork(arena: *Arena, root: u32, limit: u32) ![]u8 { 107 if (limit == 0 or limit > 100000) return error.InvalidData; 108 const allocator = arena.allocator; 109 const base = arena.roots.items.len; 110 try arena.roots.append(allocator, root); 111 defer arena.roots.shrinkRetainingCapacity(base); 112 var ids: std.AutoArrayHashMapUnmanaged(u32, void) = .empty; 113 defer ids.deinit(allocator); 114 var seen: std.AutoHashMapUnmanaged(u32, void) = .empty; 115 defer seen.deinit(allocator); 116 var pending: std.ArrayList(u32) = .empty; 117 defer pending.deinit(allocator); 118 var records: std.ArrayList(Record) = .empty; 119 defer records.deinit(allocator); 120 try ids.put(allocator, root, {}); 121 try pending.append(allocator, 0); 122 var truncated = false; 123 while (pending.pop()) |label| { 124 if (seen.contains(label)) continue; 125 if (records.items.len == limit) { truncated = true; break; } 126 const normal = try reduce.reduceUnbounded(ids.keys()[label], arena); 127 const node = arena.get(normal).*; 128 try seen.put(allocator, label, {}); 129 var record = Record{ .label = label, .kind = 0 }; 130 var children: [2]u32 = undefined; 131 const count: usize = switch (node) { 132 .leaf => 0, 133 .stem => |s| blk: { children[0] = s.child; break :blk 1; }, 134 .fork => |f| blk: { children = .{ f.left, f.right }; break :blk 2; }, 135 .app => unreachable, 136 }; 137 record.kind = @intCast(count); 138 for (children[0..count], 0..) |child, i| { 139 try ids.put(allocator, child, {}); 140 const key: u32 = @intCast(ids.getIndex(child).?); 141 if (i == 0) record.left = key else record.right = key; 142 } 143 if (count == 2) try pending.append(allocator, record.right); 144 if (count >= 1) try pending.append(allocator, record.left); 145 try records.append(allocator, record); 146 } 147 const bytes = try allocator.alloc(u8, 16 + records.items.len * 16); 148 const header = [_]u32{ 1, 0, @intCast(records.items.len), @intFromBool(truncated) }; 149 for (header, 0..) |word, i| std.mem.writeInt(u32, bytes[i * 4 ..][0..4], word, .little); 150 for (records.items, 0..) |record, i| { 151 const words = [_]u32{ record.label, record.kind, record.left, record.right }; 152 for (words, 0..) |word, j| std.mem.writeInt(u32, bytes[16 + i * 16 + j * 4 ..][0..4], word, .little); 153 } 154 return bytes; 155 } 156 157 fn snapshotAllocationProbe(allocator: std.mem.Allocator) !void { 158 var arena = Arena.init(allocator); 159 defer arena.deinit(); 160 var root = try arena.alloc(.leaf); 161 for (0..600) |_| root = try arena.alloc(.{ .fork = .{ .left = root, .right = root } }); 162 const bytes = try snapshotUnboundedWork(&arena, root, 100000); 163 defer allocator.free(bytes); 164 try std.testing.expectEqual(@as(u32, 601), std.mem.readInt(u32, bytes[8..12], .little)); 165 try std.testing.expectEqual(@as(u32, 0), std.mem.readInt(u32, bytes[12..16], .little)); 166 const bounded = try snapshotUnboundedWork(&arena, root, 256); 167 defer allocator.free(bounded); 168 try std.testing.expectEqual(@as(u32, 1), std.mem.readInt(u32, bounded[12..16], .little)); 169 try std.testing.expectEqual(@as(usize, 0), arena.roots.items.len); 170 } 171 test "complete snapshot preserves sharing, bounds transport, and cleans allocation failures" { 172 try std.testing.checkAllAllocationFailures(std.testing.allocator, snapshotAllocationProbe, .{}); 173 }