commit f97fe0c55e92b6097a11fa61b07c66935baa6fc3
parent 97c253e1bb720ec2b6c5a44bd973dbb62557c8df
Author: Szymon Mikulicz <szymon.mikulicz@aptiv.com>
Date: Thu, 29 Aug 2024 10:07:01 +0200
Closures finished
Diffstat:
9 files changed, 168 insertions(+), 44 deletions(-)
diff --git a/zlox/src/chunk.zig b/zlox/src/chunk.zig
@@ -36,6 +36,7 @@ pub const OP = enum(u8) {
GET_INDEX,
CALL,
CLOSURE,
+ CLOSE_UPVALUE
};
pub const Chunk = struct {
diff --git a/zlox/src/compiler.zig b/zlox/src/compiler.zig
@@ -60,9 +60,10 @@ pub fn Compiler(size: comptime_int) type {
const upvalues_size = std.math.maxInt(u8);
const Local = struct {
- name: scanner.Token,
- depth: ?usize,
- con: bool,
+ name: scanner.Token = scanner.Token.Empty,
+ depth: ?usize = null,
+ con: bool = true,
+ captured: bool = false,
};
const ParseFn = *const fn (*Self, bool) void;
@@ -310,6 +311,7 @@ pub fn Compiler(size: comptime_int) type {
}
while(!self.match(Token.RIGHT_BRACKET)) {
self.consume(Token.COMMA, "Expect ',' between expressions");
+ if (self.match(Token.RIGHT_BRACKET)) break;
self.expression();
argCount += 1;
if(!isList) {
@@ -364,8 +366,8 @@ pub fn Compiler(size: comptime_int) type {
fn resolveUpvalue(self: *Self, name: scanner.Token) ?u8 {
if (self.enclosing) |enclosing| {
- std.debug.print("Resolving '{s}' in '{s}'\n", .{name.lexeme, enclosing.currentFunction});
if (enclosing.resolveLocal(name)) |local| {
+ enclosing.locals[local].captured = true;
return self.addUpvalue(local, true) catch null;
} else if (enclosing.resolveUpvalue(name)) |upvalue| {
return self.addUpvalue(upvalue, false) catch null;
@@ -379,7 +381,6 @@ pub fn Compiler(size: comptime_int) type {
for (self.upvalues[0..count], 0..) |upvalue, i| {
if (upvalue.index == idx and upvalue.isLocal == isLocal) {
- std.debug.print("Found existing at {d}\n", .{i});
return @intCast(i);
}
}
@@ -390,7 +391,6 @@ pub fn Compiler(size: comptime_int) type {
return self.lastError;
}
- std.debug.print("New {s} upvalue in {s} idx {d} at {d} \n", .{if (isLocal) "local" else "upvalue", self.currentFunction, idx, count});
self.upvalues[count] = .{.index = idx, .isLocal = isLocal};
self.currentFunction.upvalue_count += 1;
return count;
@@ -639,7 +639,7 @@ pub fn Compiler(size: comptime_int) type {
self.errorAt(name, "Too many variables in function");
return;
}
- self.locals[self.localCount] = Local {.name = name, .depth = null, .con = con};
+ self.locals[self.localCount] = Local {.name = name, .con = con};
self.localCount += 1;
}
@@ -912,7 +912,11 @@ pub fn Compiler(size: comptime_int) type {
} else {
self.errorAt(self.locals[self.localCount-1].name, "Unitialized variable at scope end");
}
- self.emitOP(OP.POP);
+ if (self.locals[self.localCount-1].captured) {
+ self.emitOP(OP.CLOSE_UPVALUE);
+ } else {
+ self.emitOP(OP.POP);
+ }
self.localCount -= 1;
}
}
@@ -940,7 +944,7 @@ pub fn Compiler(size: comptime_int) type {
}
fn init(scan: *scanner.Scanner, objects: *GC, fun: *Obj.Function) Self {
- return Self{
+ var self = Self{
.scanner = scan,
.current = scanner.Token.Empty,
.previous = scanner.Token.Empty,
@@ -949,12 +953,14 @@ pub fn Compiler(size: comptime_int) type {
.lastError = scanner.ScannerError.EmptyToken,
.currentFunction = fun,
.objects = objects,
- .locals = [_]Local{Local{.name = scanner.Token.Empty, .depth = 0, .con = true}} ** size,
+ .locals = [_]Local{Local{}} ** size,
.localCount = 1,
.scopeDepth = 0,
.enclosing = null,
.upvalues = [_]Upvalue{Upvalue{.index = 0, .isLocal = false}} ** upvalues_size,
};
+ self.locals[0].depth = 0;
+ return self;
}
fn init_enclosed(enclosing: *Self, fun: *Obj.Function) Self {
diff --git a/zlox/src/debug.zig b/zlox/src/debug.zig
@@ -12,7 +12,7 @@ pub fn disassembleChunk(ch: *const chunk.Chunk, name: []const u8) Error!void {
var offset: usize = 0;
while (offset < ch.code.len) {
- offset = try disassembleInstruction(ch, offset);
+ offset = try _disassembleInstruction(ch, offset, true);
}
print("\\= {s} =/\n", .{name});
}
@@ -27,6 +27,10 @@ pub fn print_offset(ch: *const chunk.Chunk, offset: usize) !void {
}
pub fn disassembleInstruction(ch: *const chunk.Chunk, offset: usize) Error!usize {
+ return _disassembleInstruction(ch, offset, false);
+}
+
+fn _disassembleInstruction(ch: *const chunk.Chunk, offset: usize, print_fn: bool) Error!usize {
try print_offset(ch, offset);
const OP = chunk.OP;
@@ -47,11 +51,11 @@ pub fn disassembleInstruction(ch: *const chunk.Chunk, offset: usize) Error!usize
@intFromEnum(OP.GREATER) => simpleInstruction(name, offset),
@intFromEnum(OP.NIL) => simpleInstruction(name, offset),
@intFromEnum(OP.NOT) => simpleInstruction(name, offset),
- @intFromEnum(OP.CONSTANT) => try constantInstruction(name, ch, offset),
- @intFromEnum(OP.DEFINE_GLOBAL) => try constantInstruction(name, ch, offset),
- @intFromEnum(OP.DEFINE_GLOBAL_CONSTANT) => try constantInstruction(name, ch, offset),
- @intFromEnum(OP.GET_GLOBAL) => try constantInstruction(name, ch, offset),
- @intFromEnum(OP.SET_GLOBAL) => try constantInstruction(name, ch, offset),
+ @intFromEnum(OP.CONSTANT) => try constantInstruction(name, ch, offset, print_fn),
+ @intFromEnum(OP.DEFINE_GLOBAL) => try constantInstruction(name, ch, offset, print_fn),
+ @intFromEnum(OP.DEFINE_GLOBAL_CONSTANT) => try constantInstruction(name, ch, offset, print_fn),
+ @intFromEnum(OP.GET_GLOBAL) => try constantInstruction(name, ch, offset, print_fn),
+ @intFromEnum(OP.SET_GLOBAL) => try constantInstruction(name, ch, offset, print_fn),
@intFromEnum(OP.PRINT) => simpleInstruction(name, offset),
@intFromEnum(OP.POP) => simpleInstruction(name, offset),
@intFromEnum(OP.GET_LOCAL) => try byteInstruction(name, ch, offset),
@@ -65,7 +69,8 @@ pub fn disassembleInstruction(ch: *const chunk.Chunk, offset: usize) Error!usize
@intFromEnum(OP.SET_INDEX) => simpleInstruction(name, offset),
@intFromEnum(OP.GET_INDEX) => simpleInstruction(name, offset),
@intFromEnum(OP.CALL) => try byteInstruction(name, ch, offset),
- @intFromEnum(OP.CLOSURE) => try closureInstruction(name, ch, offset),
+ @intFromEnum(OP.CLOSURE) => try closureInstruction(name, ch, offset, print_fn),
+ @intFromEnum(OP.CLOSE_UPVALUE) => simpleInstruction(name, offset),
else => blk: {
print("Unknown opcode {d} {s}\n", .{op, name});
break :blk offset + 1;
@@ -78,11 +83,11 @@ fn simpleInstruction(name: []const u8, offset: usize) usize {
return offset + 1;
}
-fn constantInstruction(name: []const u8, ch: *const chunk.Chunk, offset: usize) Error!usize {
+fn constantInstruction(name: []const u8, ch: *const chunk.Chunk, offset: usize, print_fn: bool) Error!usize {
const constant = try ch.code.get(offset + 1);
const constval = try ch.constants.get(constant);
print("{s:<32} {d:4} '{s}'\n", .{ name, constant, constval});
- if (constval.is(Obj.Type.Function)) {
+ if (print_fn and constval.is(Obj.Type.Function)) {
const function = constval.obj.cast(.Function) catch unreachable;
if (function.name) |str| {
try disassembleChunk(function.chunk, str.slice());
@@ -108,7 +113,7 @@ fn jumpInstruction(name: []const u8, sign: bool, ch: *const chunk.Chunk, offset:
return offset + 3;
}
-fn closureInstruction(name: []const u8, ch: *const chunk.Chunk, offset: usize) Error!usize {
+fn closureInstruction(name: []const u8, ch: *const chunk.Chunk, offset: usize, print_fn: bool) Error!usize {
var off = offset + 1;
const constant = try ch.code.get(off);
const val = try ch.constants.get(constant);
@@ -121,10 +126,12 @@ fn closureInstruction(name: []const u8, ch: *const chunk.Chunk, offset: usize) E
print("{s:<38}|-> {s} {d}\n", .{ "", if (isLocal == 1) "local" else "upvalue", idx});
off += 2;
}
- if (function.name) |str| {
- try disassembleChunk(function.chunk, str.slice());
- } else {
- try disassembleChunk(function.chunk, "<anon>");
+ if (print_fn) {
+ if (function.name) |str| {
+ try disassembleChunk(function.chunk, str.slice());
+ } else {
+ try disassembleChunk(function.chunk, "<anon>");
+ }
}
return off + 1;
diff --git a/zlox/src/hash.zig b/zlox/src/hash.zig
@@ -35,7 +35,7 @@ pub fn hash_append(ret: u32, val: anytype) u32 {
pub fn hash_t(T: type) fn (T) u32 {
return switch (T) {
- *Obj.Table, *const Obj.Table, *Obj.String, *const Obj.String => struct {
+ *Obj.String, *const Obj.String => struct {
pub fn fun(val: T) u32 {
return val.hash;
}
@@ -44,7 +44,6 @@ pub fn hash_t(T: type) fn (T) u32 {
pub fn fun(val: T) u32 {
return switch (val.type) {
.String => hash_append_t([]const u8)(hash(val.cast(.String) catch unreachable), "\x01"),
- .Table => hash_append_t([]const u8)(hash(val.cast(.Table) catch unreachable), "\x02"),
inline else => |tag| @panic("hash_t(Obj." ++ @tagName(tag) ++ "): Unsupported type"),
};
}
diff --git a/zlox/src/list.zig b/zlox/src/list.zig
@@ -1,4 +1,5 @@
const std = @import("std");
+const utils = @import("comptime_utils.zig");
pub fn List(T: type) type {
return struct {
@@ -112,6 +113,49 @@ pub fn List(T: type) type {
}
}
+ pub fn insert_before(self: *Self, element: ?*Element, val: T) Error!void {
+ if(element) |el| {
+ if(el.prev) |prev| {
+ const new = try self.allocator.create(Element);
+ new.* = .{.val = val, .next = el, .prev = prev};
+ prev.next = new;
+ el.prev = new;
+ self.len += 1;
+ return;
+ }
+ }
+ try self.push(val);
+ }
+
+ pub fn insert_after(self: *Self, element: ?*Element, val: T) Error!void {
+ if(element) |el| {
+ if(el.next) |next| {
+ const new = try self.allocator.create(Element);
+ new.* = .{.val = val, .next = next, .prev = el};
+ next.prev = new;
+ el.next = new;
+ self.len += 1;
+ return;
+ }
+ }
+ try self.push_end(val);
+ }
+
+ pub fn format(self: *const Self, comptime fmt: []const u8, options: std.fmt.FormatOptions, writer: anytype) utils.fn_error(@TypeOf(writer).write)!void {
+ _ = try writer.write("[");
+ var end = self.end;
+ while (end) |el| : (end = el.prev) {
+ if (el.val) |v| {
+ try v.format(fmt, options, writer);
+ } else {
+ _ = try writer.write("-");
+ }
+ if (el.prev) |_| _ = try writer.write(", ");
+ }
+ _ = try writer.writeAll("]");
+ }
+
+
fn _pop(self: *Self) Error!?T {
if (self.tip) |tip| {
if (tip.next) |next| {
@@ -154,5 +198,22 @@ pub fn List(T: type) type {
pub fn push(self: *Self, val: T) Error!void {
return self._push(val);
}
+
+ fn _push_end(self: *Self, val: ?T) Error!void {
+ const new_end = try self.allocator.create(Element);
+ if (self.tip == null) {
+ self.tip = new_end;
+ }
+ if (self.end) |old_end| {
+ old_end.next = new_end;
+ }
+ new_end.* = Element{.val = val, .prev = self.end, .next = null};
+ self.end = new_end;
+ self.len += 1;
+ }
+
+ pub fn push_end(self: *Self, val: T) Error!void {
+ return self._push_end(val);
+ }
};
}
diff --git a/zlox/src/main.zig b/zlox/src/main.zig
@@ -39,7 +39,7 @@ pub fn runFile(allocator: std.mem.Allocator, path: []const u8) anyerror!void {
const text = try file.reader().readAllAlloc(allocator, 999999);
defer allocator.free(text);
- try VM.interpret(text, true);
+ try VM.interpret(text, false);
}
pub fn repl(allocator: std.mem.Allocator, dbg: bool) anyerror!void {
diff --git a/zlox/src/obj/table.zig b/zlox/src/obj/table.zig
@@ -14,7 +14,6 @@ pub const Table = packed struct {
obj: Super,
table: *Self.Table,
- hash: u32,
len: usize,
pub fn init(_: Arg, allocator: std.mem.Allocator) Error!*Self {
@@ -24,7 +23,6 @@ pub const Table = packed struct {
.type = Super.Type.Table,
},
.table = try allocator.create(Self.Table),
- .hash = 0,
.len = 0,
};
self.table.* = Self.Table.init(allocator);
@@ -36,7 +34,6 @@ pub const Table = packed struct {
}
pub fn set(self: *Self, key: Value, val: Value) Error!bool {
- self.hash +%= hash.hash(key) +% hash.hash(val);
self.len += 1;
return self.table.set(key, val);
}
@@ -46,8 +43,6 @@ pub const Table = packed struct {
}
pub fn delete(self: *Self, key: Value) void {
- const val = self.table.get(key) catch return;
- self.hash -%= hash.hash(key) -% hash.hash(val);
if (self.table.delete(key)) self.len -= 1;
}
diff --git a/zlox/src/obj/upvalue.zig b/zlox/src/obj/upvalue.zig
@@ -7,11 +7,13 @@ const Super = @import("../obj.zig").Obj;
pub const Upvalue = packed struct {
const Self = @This();
- pub const Arg = *Value;
+ pub const Arg = struct {val: *Value, slot: u8};
pub const Error = error { OutOfMemory };
obj: Super,
location: *Value,
+ closed: bool,
+ slot: u8,
pub fn init(arg: Arg, allocator: std.mem.Allocator) Error!*Self {
const self: *Self = try allocator.create(Self);
@@ -19,17 +21,29 @@ pub const Upvalue = packed struct {
.obj = Super{
.type = Super.Type.Upvalue,
},
- .location = arg,
+ .location = arg.val,
+ .closed = false,
+ .slot = arg.slot
};
return self;
}
+ pub fn close(self: *Self, allocator: std.mem.Allocator) Error!void {
+ if (!self.closed) {
+ const new = try allocator.create(Value);
+ new.* = self.location.*;
+ self.location = new;
+ self.closed = true;
+ }
+ }
+
+
pub fn cast(self: anytype) utils.copy_const(@TypeOf(self), *Super) {
return @ptrCast(self);
}
- pub fn format(_: *const Self, comptime _: []const u8, _: std.fmt.FormatOptions, writer: anytype) !void {
- _ = try writer.writeAll("<upvalue>");
+ pub fn format(self: *const Self, comptime _: []const u8, _: std.fmt.FormatOptions, writer: anytype) !void {
+ try writer.print("<Upvalue{{{} at 0x{x}, {}, {}}}>", .{self.location.*, @intFromPtr(self.location), self.closed, self.slot});
}
pub fn eql(_: *const Self, _: *const Self) bool {
@@ -37,6 +51,7 @@ pub const Upvalue = packed struct {
}
pub fn free(self: *const Self, allocator: std.mem.Allocator) void {
+ if (self.closed) allocator.destroy(self.location);
allocator.destroy(self);
}
};
diff --git a/zlox/src/vm.zig b/zlox/src/vm.zig
@@ -8,6 +8,7 @@ const Obj = @import("obj.zig").Obj;
const GC = @import("gc.zig").GC;
const Callback = @import("vm/callbacks.zig");
const table = @import("table.zig");
+const list = @import("list.zig");
const hash = @import("hash.zig");
const utils = @import("comptime_utils.zig");
const vm_native = @import("vm/native.zig");
@@ -103,11 +104,14 @@ pub const VM = struct {
fn Interpreter(callstack_size: comptime_int, stack_size: comptime_int) type {
return struct {
+ const List = list.List(*Obj.Upvalue);
+
frames: [callstack_size]CallFrame,
frameCount: usize,
stackTop: [*]Value,
stack: [stack_size]Value,
vm: *VM,
+ open_upvalues: List,
pub fn run(vm: *VM, function: *Obj.Function, dbg: bool) InterpreterError!void {
var self = @This(){
@@ -115,8 +119,12 @@ pub const VM = struct {
.frameCount = 1,
.stack = [_]Value{Value.init({})} ** stack_size,
.stackTop = undefined,
- .vm = vm
+ .vm = vm,
+ .open_upvalues = List.init(vm.allocator)
};
+
+ defer self.open_upvalues.free();
+
self.stackTop = &self.stack;
self.frames[0] = CallFrame.init(.Function, function, self.stackTop);
self.push(Value.init(function.cast()));
@@ -220,8 +228,27 @@ pub const VM = struct {
return;
}
- fn captureUpvalue(self: *@This(), local: *Value) !*Obj.Upvalue {
- return self.vm.objects.emplace(.Upvalue, local);
+ fn captureUpvalue(self: *@This(), slot: u8) !*Obj.Upvalue {
+ var upvalue = self.open_upvalues.tip;
+ while(upvalue) |el| : (upvalue = el.next) {
+ const val = el.val.?;
+ if (val.slot == slot)
+ return val;
+ if (val.slot > slot)
+ break;
+ }
+ const new = try self.vm.objects.emplace(.Upvalue, .{.val = &self.frame().slots[slot], .slot = slot});
+ try self.open_upvalues.insert_after(upvalue, new);
+ return new;
+ }
+
+ fn closeUpvalues(self: *@This(), slot: u8) !void {
+ while(self.open_upvalues.tip) |el| {
+ if (el.val.?.slot < slot) break;
+
+ const upval = self.open_upvalues.pop() catch unreachable;
+ try upval.close(self.vm.allocator);
+ }
}
fn binary_op(self: *@This(), comptime in_tag: anytype, comptime out_tag: anytype, op: Callback.Type(in_tag, out_tag)) InterpreterError!void {
@@ -239,6 +266,10 @@ pub const VM = struct {
return @intFromPtr(self.ip()) - @intFromPtr(self.frame().chunk.code.data.ptr);
}
+ fn current_slot(self: *const @This()) u8 {
+ return @intCast((@intFromPtr(self.stackTop) - @intFromPtr(self.frame().slots)) / @sizeOf(@TypeOf(self.stackTop[0])));
+ }
+
fn execute(self: *@This(), dbg: bool) !void {
while (true) {
if (dbg) {
@@ -261,6 +292,7 @@ pub const VM = struct {
_ = self.pop();
return;
}
+ try self.closeUpvalues(0);
self.stackTop = self.frame().slots;
self.frameCount -= 1;
self.push(result);
@@ -323,11 +355,17 @@ pub const VM = struct {
},
@intFromEnum(OP.GET_UPVALUE) => {
const closure = try self.frame().callee.cast(.Closure);
- self.push(closure.upvalues[self.read_byte()].?.location.*);
+ const index = self.read_byte();
+ self.push(closure.upvalues[index].?.location.*);
},
@intFromEnum(OP.SET_UPVALUE) => {
const closure = try self.frame().callee.cast(.Closure);
- closure.upvalues[self.read_byte()].?.location.* = self.peek(0);
+ const index = self.read_byte();
+ closure.upvalues[index].?.location.* = self.peek(0);
+ },
+ @intFromEnum(OP.CLOSE_UPVALUE) => {
+ try self.closeUpvalues(self.current_slot());
+ _ = self.pop();
},
@intFromEnum(OP.GET_INDEX) => {
const key = self.pop();
@@ -380,11 +418,13 @@ pub const VM = struct {
const function = try self.read_constant().obj.cast(.Function);
const closure = try self.vm.objects.emplace(.Closure, function);
for(closure.upvalues[0..closure.upvalues_len]) |*upvalue| {
- if(self.read_byte() == 1) {
- upvalue.* = try self.captureUpvalue(&self.frame().slots[self.read_byte()]);
+ const isLocal = self.read_byte();
+ const slot = self.read_byte();
+ if(isLocal == 1) {
+ upvalue.* = try self.captureUpvalue(slot);
} else {
const callee = try self.frame().callee.cast(.Closure);
- upvalue.* = callee.upvalues[self.read_byte()];
+ upvalue.* = callee.upvalues[slot];
}
}
self.push(Value.init(closure.cast()));
