tricu

arena.zig (5908B)

---

 const std = @import("std");
 const tree = @import("tree.zig");
 
 pub const ReductionFrame = struct {
     kind: enum { function, discriminator, argument, update },
     redex: u32,
 };
 
 pub const Arena = struct {
     allocator: std.mem.Allocator,
     nodes: std.ArrayList(tree.Node),
     // Opt-in collection: every externally retained ID must be in roots.
     gc_enabled: bool = false,
     roots: std.ArrayList(u32) = .empty,
     free: std.ArrayList(u32) = .empty,
     allocations: usize = 0,
     // Allocation headroom, not a memory limit. Tests can select a small policy
     // to force collections at suspension/allocation boundaries.
     gc_min_interval: usize = 1 << 20,
     gc_live_multiplier: usize = 1,
     gc_interval: usize = 1 << 20,
     collections: usize = 0,
     last_live: usize = 0,
     marks: std.ArrayList(bool) = .empty,
     grey: std.ArrayList(u32) = .empty,
     reduction_frames: std.ArrayList(ReductionFrame) = .empty,
     reduction_roots: std.ArrayList(u32) = .empty,
 
     pub fn init(allocator: std.mem.Allocator) Arena {
         return .{
             .allocator = allocator,
             .nodes = .empty,
         };
     }
 
     pub fn deinit(self: *Arena) void {
         self.nodes.deinit(self.allocator);
         self.roots.deinit(self.allocator);
         self.free.deinit(self.allocator);
         self.marks.deinit(self.allocator);
         self.grey.deinit(self.allocator);
         self.reduction_frames.deinit(self.allocator);
         self.reduction_roots.deinit(self.allocator);
     }
 
     inline fn allocSlot(self: *Arena) !u32 {
         if (self.free.items.len != 0) {
             const idx = self.free.items[self.free.items.len - 1];
             self.free.items.len -= 1;
             self.allocations += 1;
             return idx;
         }
         if (self.nodes.items.len >= std.math.maxInt(u32)) return error.OutOfMemory;
         const idx: u32 = @intCast(self.nodes.items.len);
         _ = try self.nodes.addOne(self.allocator);
         self.allocations += 1;
         return idx;
     }
 
     pub inline fn alloc(self: *Arena, node: tree.Node) !u32 {
         const idx = try self.allocSlot();
         self.nodes.items[idx] = node;
         return idx;
     }
 
     // Reduction allocates applications in its hottest path. Scalar operands
     // avoid constructing and then copying a temporary padded tagged union.
     pub inline fn allocApp(self: *Arena, func: u32, arg: u32) !u32 {
         const idx = try self.allocSlot();
         self.nodes.items[idx] = .{ .app = .{ .func = func, .arg = arg } };
         return idx;
     }
 
     pub fn get(self: *Arena, idx: u32) *tree.Node {
         return &self.nodes.items[idx];
     }
 
     pub fn len(self: *const Arena) u32 {
         return @intCast(self.nodes.items.len);
     }
 
     pub fn collectionDue(self: *const Arena) bool {
         return self.gc_enabled and self.allocations >= self.gc_interval;
     }
 
     pub fn setGcPolicy(self: *Arena, minimum: usize, multiplier: usize) error{InvalidData}!void {
         if (minimum == 0 or multiplier == 0) return error.InvalidData;
         self.gc_min_interval = minimum;
         self.gc_live_multiplier = multiplier;
         self.gc_interval = @max(minimum, self.last_live *| multiplier);
     }
 
     // Inline the per-edge duplicate check; shared edges normally need no enqueue.
     inline fn mark(self: *Arena, idx: u32) !void {
         if (self.marks.items[idx]) return;
         // Mark on enqueue so shared children occupy the work stack only once.
         try self.grey.append(self.allocator, idx);
         self.marks.items[idx] = true;
     }
 
     /// Non-moving mark/sweep. Only reduction safepoints collect automatically;
     /// construction never collects, so newly allocated children can be linked
     /// without temporary root registrations. Failure before sweep changes no IDs.
     pub fn collect(self: *Arena, temporary_roots: []const u32) !void {
         try self.marks.resize(self.allocator, self.nodes.items.len);
         @memset(self.marks.items, false);
         self.grey.clearRetainingCapacity();
         for (self.roots.items) |idx| try self.mark(idx);
         for (temporary_roots) |idx| try self.mark(idx);
         var live: usize = 0;
         var end: usize = 0;
         while (self.grey.pop()) |idx| {
             live += 1;
             end = @max(end, @as(usize, idx) + 1);
             switch (self.nodes.items[idx]) {
                 .leaf => {},
                 .stem => |s| try self.mark(s.child),
                 .fork => |f| {
                     try self.mark(f.left);
                     try self.mark(f.right);
                 },
                 .app => |a| {
                     try self.mark(a.func);
                     try self.mark(a.arg);
                 },
             }
         }
         try self.free.ensureTotalCapacity(self.allocator, end - live);
         // Free-list entries outside its logical length are never read. Rebuild
         // without poisoning the previous list only to overwrite it immediately.
         self.free.items.len = 0;
         // Dead trailing slots need neither sweeping nor free-list entries.
         // IDs of live nodes never change; backing capacity remains available.
         // Slice truncation keeps bounds checks without touching dead backing
         // storage. alloc/allocApp initialize a recycled slot before publishing it.
         self.nodes.items = self.nodes.items[0..end];
         var i = end;
         while (i > 0) {
             i -= 1;
             if (!self.marks.items[i]) {
                 self.free.appendAssumeCapacity(@intCast(i));
             }
         }
         self.last_live = live;
         self.allocations = 0;
         self.collections += 1;
         // Amortize scanning a large live graph; this is not a hard RSS bound.
         // Recompute rather than retaining a transient live-heap peak forever.
         self.gc_interval = @max(self.gc_min_interval, live *| self.gc_live_multiplier);
     }
 };