DzLox

:)
git clone https://git.sr.ht/~ashymad/DzLox
Log | Files | Refs | Submodules | LICENSE

gc.zig (9005B)

      1 const std = @import("std");
      2 
      3 const list = @import("lib::list.zig");
      4 const utils = @import("lib::utils.zig");
      5 
      6 const Value = @import("value.zig").Value;
      7 const VM = @import("vm.zig").VM;
      8 const Packed = @import("lib::packed.zig").Packed;
      9 
     10 const DBG_STRESS = false;
     11 const DBG_LOG = false;
     12 const DBG_NAME = true;
     13 const GC_HEAP_GROW_FACTOR = 2;
     14 
     15 pub const GC = struct {
     16     pub const Color = enum(u8) {
     17         White,
     18         Black,
     19         None,
     20     };
     21 
     22     pub const Name = Packed(?[]const u8);
     23 
     24     pub const Obj = if (DBG_NAME)
     25         @import("obj.zig").Obj(packed struct {
     26             color: Color = Color.White,
     27             name: Name = Name.init(null),
     28 
     29             pub fn format(self: anytype, writer: *std.Io.Writer) !void {
     30                 if (self.name.ptr()) |nam| {
     31                     _ = try writer.write(":");
     32                     _ = try writer.write(nam);
     33                 }
     34             }
     35         })
     36     else
     37         @import("obj.zig").Obj(packed struct {
     38             color: Color = Color.White,
     39         });
     40 
     41     const Self = @This();
     42 
     43     const ObjList = list.List(*Obj);
     44     const CallbackList = list.List(Callback);
     45     const GreyList = list.List(*Obj);
     46 
     47     pub const Callback = struct {
     48         pub const Arg = *anyopaque;
     49         pub const Fn = *const fn (Arg) void;
     50 
     51         arg: Arg,
     52         @"fn": Fn,
     53 
     54         pub fn call(self: *const @This()) void {
     55             self.@"fn"(self.arg);
     56         }
     57     };
     58 
     59     allocator: std.mem.Allocator,
     60     io: std.Io,
     61     pool: Obj.String.Pool,
     62     objs: ObjList,
     63     callbacks: CallbackList,
     64     greys: GreyList,
     65     allocated: usize,
     66     next: usize,
     67 
     68     fn dbg_print(comptime fmt: []const u8, args: anytype) void {
     69         if (DBG_LOG) {
     70             std.debug.print("[GC] " ++ fmt, args);
     71         }
     72     }
     73 
     74     pub fn init(allocator: std.mem.Allocator, io: std.Io) !Self {
     75         return Self{
     76             .allocator = allocator,
     77             .io = io,
     78             .pool = Obj.String.Pool.init(allocator),
     79             .objs = ObjList.init(allocator),
     80             .callbacks = CallbackList.init(allocator),
     81             .greys = GreyList.init(allocator),
     82             .allocated = 0,
     83             .next = 1024 * 1024,
     84         };
     85     }
     86 
     87     pub fn collect(self: *Self) void {
     88         if (self.callbacks.len() > 0) {
     89             self.mark_roots();
     90             self.trace_references();
     91             self.table_remove_white();
     92             self.sweep();
     93             self.next = self.allocated * GC_HEAP_GROW_FACTOR;
     94         }
     95     }
     96 
     97     fn trace_references(self: *Self) void {
     98         while (true) {
     99             const grey = self.greys.pop(0) catch break;
    100             switch (grey.type) {
    101                 inline else => |tp| self.blacken_obj(grey.cast(tp) catch unreachable),
    102             }
    103         }
    104     }
    105 
    106     fn blacken_obj(self: *Self, obj: anytype) void {
    107         const T = @TypeOf(obj);
    108 
    109         switch (T) {
    110             *Obj.Table => {
    111                 obj.table.ptr().for_each(self, struct {
    112                     pub fn fun(s: *Self, key: Obj.Table.Table.Key, val: Obj.Table.Table.Value) void {
    113                         s.mark("t", key);
    114                         s.mark("t", val);
    115                     }
    116                 }.fun);
    117             },
    118             *Obj.Function => {
    119                 self.mark("f", obj.chunk.ptr());
    120                 for (obj.upvalues.ptr()) |upvalue_ptr|
    121                     if (upvalue_ptr) |upvalue|
    122                         self.mark("f", upvalue);
    123             },
    124             *Obj.Chunk => {
    125                 for (obj.constants.ptr().slice()) |constant|
    126                     self.mark("h", constant);
    127             },
    128             *Obj.List => {
    129                 var iter = obj.list.ptr().iter();
    130                 while (iter.next()) |val| {
    131                     self.mark("l", val);
    132                 }
    133             },
    134             *Obj.Upvalue => {
    135                 if (obj.closed)
    136                     self.mark("u", obj.location.get());
    137             },
    138             *Obj.Instance => {
    139                 self.mark("i", obj.cls.ptr());
    140                 obj.fields.ptr().for_each(self, struct {
    141                     pub fn fun(s: *Self, key: Obj.Instance.Fields.Key, val: Obj.Instance.Fields.Value) void {
    142                         s.mark("i", key);
    143                         s.mark("i", val);
    144                     }
    145                 }.fun);
    146                 obj.bound.ptr().for_each(self, struct {
    147                     pub fn fun(s: *Self, key: Obj.Class.Methods.Key, val: Obj.Class.Methods.Value) void {
    148                         s.mark("i", key);
    149                         s.mark("i", val);
    150                     }
    151                 }.fun);
    152             },
    153             *Obj.Class => {
    154                 obj.methods.ptr().for_each(self, struct {
    155                     pub fn fun(s: *Self, key: Obj.Class.Methods.Key, val: Obj.Class.Methods.Value) void {
    156                         s.mark("k", key);
    157                         s.mark("k", val);
    158                     }
    159                 }.fun);
    160             },
    161             else => {},
    162         }
    163     }
    164 
    165     fn mark_roots(self: *Self) void {
    166         var iter = self.callbacks.iter();
    167         while (iter.next()) |cb|
    168             cb.call();
    169     }
    170 
    171     fn table_remove_white(self: *Self) void {
    172         const Table = Obj.String.Pool.Table;
    173         const table = &self.pool.table;
    174 
    175         table.for_each(table, struct {
    176             pub fn fun(tbl: *Table, key: Table.Key, _: Table.Value) void {
    177                 const obj = key.cast();
    178                 if (obj.fields.color == .White)
    179                     _ = tbl.delete(key);
    180             }
    181         }.fun);
    182     }
    183 
    184     fn sweep(self: *Self) void {
    185         var iter = self.objs.iter();
    186         while (iter.next()) |obj| {
    187             if (obj.fields.color == .White) {
    188                 iter.pop();
    189                 dbg_obj("O", "free", obj, false);
    190                 switch (obj.type) {
    191                     inline else => |tp| self.allocated -= @sizeOf(tp.get()),
    192                 }
    193                 if (obj.cast_if(.String)) |str| self.allocated -= str.len;
    194                 obj.free(self.allocator);
    195             } else if (obj.fields.color == .Black) {
    196                 obj.fields.color = .White;
    197             }
    198         }
    199     }
    200 
    201     pub fn push_callback(self: *Self, callback: Callback.Fn, arg: Callback.Arg) !void {
    202         try self.callbacks.push(0, Callback{ .@"fn" = callback, .arg = arg });
    203     }
    204 
    205     pub fn swap_callback(self: *Self, callback: Callback.Fn, arg: Callback.Arg) !void {
    206         try self.callbacks.set(0, Callback{ .@"fn" = callback, .arg = arg });
    207     }
    208 
    209     pub fn pop_callback(self: *Self) void {
    210         _ = self.callbacks.pop(0) catch return;
    211     }
    212 
    213     pub fn dbg_obj(info: []const u8, msg: []const u8, obj: anytype, comptime prin: bool) void {
    214         if (prin) {
    215             dbg_print("[{s}] {s: >5}: {s: <8} 0x{x} {f}\n", .{
    216                 info,
    217                 msg,
    218                 @tagName(obj.type),
    219                 @intFromPtr(obj),
    220                 obj,
    221             });
    222         } else {
    223             dbg_print("[{s}] {s: >5}: {s: <8} 0x{x}\n", .{
    224                 info,
    225                 msg,
    226                 @tagName(obj.type),
    227                 @intFromPtr(obj),
    228             });
    229         }
    230     }
    231 
    232     pub fn emplace(
    233         self: *Self,
    234         comptime tp: Obj.Type,
    235         name: ?[]const u8,
    236         arg: tp.get().Arg,
    237     ) (ObjList.Error || tp.get().Error || Obj.String.Pool.Error)!*tp.get() {
    238         if (tp == .String)
    239             if (self.pool.find(arg)) |obj|
    240                 return obj;
    241 
    242         const chd = try tp.get().init(arg, self.allocator);
    243 
    244         self.allocated += @sizeOf(tp.get());
    245         if (tp == .String) self.allocated += chd.len;
    246 
    247         if (DBG_STRESS or self.allocated > self.next) {
    248             self.collect();
    249         }
    250 
    251         if (tp == .String)
    252             try self.pool.put(chd);
    253 
    254         const obj = chd.cast();
    255 
    256         if (DBG_NAME)
    257             obj.fields.name = Name.init(name);
    258 
    259         dbg_obj("O", "new", obj, true);
    260 
    261         try self.objs.push(0, obj);
    262 
    263         return chd;
    264     }
    265 
    266     pub fn mark(self: *Self, msg: []const u8, arg: anytype) void {
    267         if (Obj.from(arg)) |obj| {
    268             if (obj.fields.color == .White) {
    269                 dbg_obj(msg, "mark", obj, true);
    270                 obj.fields.color = .Black;
    271                 self.greys.push(-1, obj) catch @panic("Grey stack overflow");
    272             }
    273         }
    274     }
    275 
    276     pub fn name_of(obj: *Obj) ?[]const u8 {
    277         return if (DBG_NAME) obj.fields.name.ptr() else null;
    278     }
    279 
    280     pub fn exclude(obj: *Obj) void {
    281         obj.fields.color = .None;
    282     }
    283 
    284     pub fn emplace_cast(self: *Self, comptime tp: Obj.Type, name: ?[]const u8, arg: tp.get().Arg) !*Obj {
    285         return (try self.emplace(tp, name, arg)).cast();
    286     }
    287 
    288     pub fn deinit(self: *Self) void {
    289         self.callbacks.deinit();
    290         self.greys.deinit();
    291         while (true) {
    292             const el = self.objs.pop(0) catch break;
    293             dbg_obj("O", "free", el, false);
    294             el.free(self.allocator);
    295         }
    296         self.objs.deinit();
    297         self.pool.free();
    298     }
    299 };