vm.zig (27522B)
1 const std = @import("std"); 2 3 const table = @import("lib::table.zig"); 4 const list = @import("lib::list.zig"); 5 const utils = @import("lib::utils.zig"); 6 const callbacks = @import("vm::callbacks.zig"); 7 const native = @import("vm::native.zig"); 8 const debug = @import("debug.zig"); 9 const compiler = @import("compiler.zig"); 10 const hash = @import("hash.zig"); 11 12 const OP = @import("op.zig").OP; 13 const Value = @import("value.zig").Value; 14 const GC = @import("gc.zig").GC; 15 const Obj = GC.Obj; 16 const Chunk = Obj.Chunk; 17 18 const InterpreterError = Obj.Error || compiler.CompilerError || callbacks.Error || error{ CompileError, RuntimeError, StackOverflow, IndexOutOfBounds, Overflow, DivisionByZero }; 19 20 pub const VM = struct { 21 objects: GC, 22 globals: Globals, 23 allocator: std.mem.Allocator, 24 initializer: *Obj.String, 25 26 pub const CALLSTACK = 64; 27 pub const STACK = 256; 28 pub const Compiler = compiler.Compiler(STACK); 29 30 pub const Global = struct { 31 val: Value, 32 con: bool, 33 34 const Self = @This(); 35 36 pub fn is_var(g: Self) bool { 37 return !g.con; 38 } 39 40 pub fn make_var(v: Value) Self { 41 return Self{ 42 .val = v, 43 .con = false, 44 }; 45 } 46 47 pub fn make_con(v: Value) Self { 48 return Self{ 49 .val = v, 50 .con = true, 51 }; 52 } 53 }; 54 55 const Globals = table.Table(*Obj.String, Global, hash.hash_t(*Obj.String), Obj.String.eql); 56 57 const CallFrame = struct { 58 callee: *Obj.Function, 59 ip: [*]const u8, 60 slots: [*]Value, 61 chunk: *const Chunk, 62 63 pub fn init(callee: *Obj.Function, slots: [*]Value) @This() { 64 return @This(){ 65 .callee = callee, 66 .ip = callee.chunk.ptr().code.ptr().data.ptr, 67 .chunk = callee.chunk.ptr(), 68 .slots = slots, 69 }; 70 } 71 }; 72 73 fn defineNative(self: *@This(), comptime name: []const u8, arity_min: u8, arity_max: u8, fun: Obj.Native.Fn) !void { 74 const nameObj = try self.objects.emplace(.String, null, &.{name}); 75 GC.exclude(nameObj.cast()); 76 77 const funObj = try self.objects.emplace_cast(.Native, "B::" ++ name, Obj.Native.Arg{ 78 .fun = fun, 79 .arity_min = arity_min, 80 .arity_max = arity_max, 81 }); 82 GC.exclude(funObj); 83 _ = try self.globals.set(nameObj, Global.make_con(Value.init(funObj))); 84 } 85 86 fn gc_callback(self_ptr: *anyopaque) void { 87 const self: *@This() = @ptrCast(@alignCast(self_ptr)); 88 89 self.globals.for_each(self, struct { 90 pub fn fun(this: @TypeOf(self), name: *Obj.String, val: Global) void { 91 this.objects.mark("G", name); 92 this.objects.mark("G", val.val); 93 } 94 }.fun); 95 } 96 97 pub fn init(allocator: std.mem.Allocator, io: std.Io) !@This() { 98 var self = @This(){ 99 .globals = Globals.init(allocator), 100 .objects = try GC.init(allocator, io), 101 .allocator = allocator, 102 .initializer = undefined, 103 }; 104 105 self.initializer = try self.objects.emplace(.String, null, &.{"init"}); 106 107 GC.exclude(self.initializer.cast()); 108 109 try self.defineNative("clock", 0, 0, native.Clock.clock); 110 try self.defineNative("put", 1, 1, native.put); 111 try self.defineNative("typeof", 1, 1, native.typeof); 112 try self.defineNative("table", 0, Obj.Native.ArityMax, native.table); 113 try self.defineNative("list", 0, Obj.Native.ArityMax, native.list); 114 try self.defineNative("rungc", 0, 0, native.rungc); 115 try self.defineNative("len", 1, 1, native.len); 116 117 native.Clock.set_start(io); 118 119 return self; 120 } 121 122 pub fn interpret(self: *@This(), source: []const u8, dbg: bool) InterpreterError!void { 123 try self.objects.push_callback(&VM.gc_callback, self); 124 defer self.objects.pop_callback(); 125 126 const chunk = try Compiler.compile(source, &self.objects); 127 128 if (dbg) try debug.disassembleChunk(chunk); 129 130 try Interpreter(CALLSTACK, Compiler.Stack).run(self, chunk, dbg); 131 } 132 133 fn Interpreter(callstack_size: comptime_int, stack_size: comptime_int) type { 134 return struct { 135 const List = list.List(*Obj.Upvalue); 136 const Self = @This(); 137 138 frames: [callstack_size]CallFrame, 139 frameCount: usize, 140 stackTop: [*]Value, 141 stack: [stack_size]Value, 142 vm: *VM, 143 upvalues: List, 144 145 pub fn run(vm: *VM, chunk: *Obj.Chunk, dbg: bool) InterpreterError!void { 146 var self = @This(){ 147 .frames = @splat(undefined), 148 .frameCount = 0, 149 .stack = @splat(Value.init({})), 150 .stackTop = undefined, 151 .vm = vm, 152 .upvalues = List.init(vm.allocator), 153 }; 154 self.stackTop = &self.stack; 155 156 try vm.objects.push_callback(&Self.gc_callback, &self); 157 defer vm.objects.pop_callback(); 158 159 defer self.upvalues.deinit(); 160 161 self.push(Value.init(chunk.cast())); 162 163 const function = try vm.objects.emplace(.Function, null, .{ .chunk = chunk }); 164 _ = self.pop(); 165 self.push(Value.init(function.cast())); 166 167 try self.callFunction(function, 0); 168 try self.execute(dbg); 169 } 170 171 pub fn gc_callback(self_ptr: *anyopaque) void { 172 const self: *@This() = @ptrCast(@alignCast(self_ptr)); 173 174 var stack_ptr: [*]Value = &self.stack; 175 while (stack_ptr != self.stackTop) : (stack_ptr += 1) { 176 self.vm.objects.mark("S", stack_ptr[0]); 177 } 178 179 var frame_idx: usize = 0; 180 while (frame_idx < self.frameCount) : (frame_idx += 1) { 181 self.vm.objects.mark("F", self.frames[frame_idx].callee); 182 } 183 184 var iter = self.upvalues.iter(); 185 while (iter.next()) |upval| { 186 self.vm.objects.mark("U", upval); 187 } 188 } 189 190 fn frame(self: anytype) utils.copy_const(@TypeOf(self), *CallFrame) { 191 return &self.frames[self.frameCount - 1]; 192 } 193 194 fn ip(self: *const @This()) [*]const u8 { 195 return self.frame().ip; 196 } 197 198 fn ip_add(self: *@This(), adv: usize) void { 199 self.frame().ip += adv; 200 } 201 202 fn ip_sub(self: *@This(), adv: usize) void { 203 self.frame().ip -= adv; 204 } 205 206 fn read_byte(self: *@This()) u8 { 207 const out: u8 = self.ip()[0]; 208 self.ip_add(1); 209 return out; 210 } 211 212 fn read_short(self: *@This()) u16 { 213 const msb: u16 = self.read_byte(); 214 const lsb: u16 = self.read_byte(); 215 return (msb << 8) | lsb; 216 } 217 218 fn read_constant(self: *@This()) Value { 219 return self.frame().chunk.constants.ptr().get(self.read_byte()).?; 220 } 221 222 fn read_string(self: *@This()) *Obj.String { 223 return self.read_constant().obj.cast(.String) catch unreachable; 224 } 225 226 fn push(self: *@This(), val: Value) void { 227 self.stackTop[0] = val; 228 self.stackTop += 1; 229 } 230 231 fn pop(self: *@This()) Value { 232 self.stackTop -= 1; 233 return self.stackTop[0]; 234 } 235 236 fn peek(self: *@This(), distance: usize) Value { 237 return (self.stackTop - (1 + distance))[0]; 238 } 239 240 fn pook(self: *@This(), distance: usize, val: Value) void { 241 (self.stackTop - (1 + distance))[0] = val; 242 } 243 244 fn callValue(self: *@This(), callee: Value, argCount: u8) !void { 245 if (callee.cast_if(Obj.Type.Function)) |fun| { 246 try self.callFunction(fun, argCount); 247 } else if (callee.cast_if(Obj.Type.Native)) |nat| { 248 try self.callNative(nat, argCount); 249 } else if (callee.cast_if(Obj.Type.Class)) |cls| { 250 try self.callClass(cls, argCount); 251 } else { 252 self.runtimeError("Can only call functions and classes", .{}); 253 return InterpreterError.RuntimeError; 254 } 255 } 256 257 fn callClass(self: *@This(), callee: *Obj.Class, argCount: u8) !void { 258 const instance = try self.vm.objects.emplace(.Instance, GC.name_of(callee.cast()), callee); 259 260 const initializer = instance.method(&self.vm.objects, self.vm.initializer) catch 261 if (argCount != 0) { 262 self.runtimeError("Expected 0 arguments but got {d}", .{argCount}); 263 return InterpreterError.RuntimeError; 264 } else { 265 self.pook(argCount, Value.init(instance.cast())); 266 return; 267 }; 268 269 try self.callFunction(initializer, argCount); 270 } 271 272 fn callFunction(self: *@This(), callee: *Obj.Function, argCount: u8) !void { 273 if (argCount != callee.arity) { 274 self.runtimeError("Expected {d} arguments but got {d}", .{ callee.arity, argCount }); 275 return InterpreterError.RuntimeError; 276 } 277 if (self.frameCount == callstack_size - 1) 278 return InterpreterError.StackOverflow; 279 self.frameCount += 1; 280 self.frames[self.frameCount - 1] = CallFrame.init(callee, self.stackTop - argCount - 1); 281 } 282 283 fn callNative(self: *@This(), obj: *Obj.Native, argCount: u8) !void { 284 if (argCount < obj.arity_min or argCount > obj.arity_max) { 285 self.runtimeError("Expected from {d} to {d} arguments but got {d}", .{ obj.arity_min, obj.arity_max, argCount }); 286 return InterpreterError.RuntimeError; 287 } 288 const result = try obj.call(&self.vm.objects, argCount, self.stackTop - argCount); 289 self.stackTop -= argCount + 1; 290 self.push(result); 291 return; 292 } 293 294 fn captureUpvalue(self: *@This(), slot: u8, closed: bool) !*Obj.Upvalue { 295 var iter = self.upvalues.iter(); 296 297 while (iter.next()) |val| { 298 if (val.slot == slot) 299 return val; 300 if (val.slot > slot) 301 break; 302 } 303 _ = iter.next(); 304 305 const new = try self.vm.objects.emplace(.Upvalue, null, .{ 306 .val = &self.frame().slots[slot], 307 .slot = slot, 308 .closed = closed, 309 }); 310 try iter.push(new); 311 return new; 312 } 313 314 fn closeUpvalues(self: *@This(), slot: u8) !void { 315 var iter = self.upvalues.iter(); 316 317 while (iter.next()) |upval| { 318 if (upval.slot < slot) break; 319 320 try upval.close(self.vm.allocator); 321 iter.pop(); 322 } 323 } 324 325 fn binary_op(self: *@This(), comptime in_tag: anytype, comptime out_tag: anytype, op: callbacks.Type(in_tag, out_tag)) InterpreterError!void { 326 const b = self.peek(0); 327 const a = self.peek(1); 328 if (a.is(in_tag) and b.is(in_tag)) { 329 const val = Value.init(try op.call(a.get(in_tag), b.get(in_tag))); 330 _ = self.pop(); 331 _ = self.pop(); 332 self.push(val); 333 } else { 334 self.runtimeError("Operands have invalid types, expected: {s}", .{@tagName(in_tag)}); 335 return InterpreterError.RuntimeError; 336 } 337 } 338 339 fn instruction_idx(self: *const @This()) usize { 340 return @intFromPtr(self.ip()) - @intFromPtr(self.frame().chunk.code.ptr().data.ptr); 341 } 342 343 fn current_slot(self: *const @This()) u8 { 344 return @intCast((@intFromPtr(self.stackTop) - @intFromPtr(self.frame().slots)) / @sizeOf(@TypeOf(self.stackTop[0]))); 345 } 346 347 fn execute(self: *@This(), dbg: bool) !void { 348 while (true) { 349 if (dbg) { 350 std.debug.print(" ", .{}); 351 var stackPtr: [*]Value = &self.stack; 352 while (stackPtr != self.stackTop) : (stackPtr += 1) { 353 std.debug.print("[{f}]", .{stackPtr[0]}); 354 } 355 std.debug.print("\n", .{}); 356 _ = try debug.disassembleInstruction(self.frame().chunk, self.instruction_idx()); 357 } 358 const instruction: u8 = self.read_byte(); 359 switch (instruction) { 360 @intFromEnum(OP.PRINT) => { 361 std.debug.print("{f}\n", .{self.pop()}); 362 }, 363 @intFromEnum(OP.RETURN) => { 364 const result = self.pop(); 365 if (self.frameCount == 1) { 366 _ = self.pop(); 367 return; 368 } 369 try self.closeUpvalues(0); 370 self.stackTop = self.frame().slots; 371 self.frameCount -= 1; 372 self.push(result); 373 }, 374 @intFromEnum(OP.POP) => _ = self.pop(), 375 @intFromEnum(OP.CONSTANT) => self.push(self.read_constant()), 376 @intFromEnum(OP.NEGATE) => { 377 if (!self.peek(0).is(Value.number)) { 378 self.runtimeError("Operand must be a number.", .{}); 379 return InterpreterError.RuntimeError; 380 } 381 self.push(Value.init(-self.pop().number)); 382 }, 383 @intFromEnum(OP.ADD) => { 384 if (self.peek(0).is(Obj.Type.String)) { 385 try self.binary_op(Obj.Type.String, Obj.Type.String, callbacks.concatenate(&self.vm.objects)); 386 } else { 387 try self.binary_op(Value.number, Value.number, callbacks.add); 388 } 389 }, 390 @intFromEnum(OP.JUMP_IF_FALSE) => { 391 const offset = self.read_short(); 392 if (!self.peek(0).isTruthy()) { 393 self.ip_add(offset); 394 } 395 }, 396 @intFromEnum(OP.JUMP) => { 397 self.ip_add(self.read_short()); 398 }, 399 @intFromEnum(OP.JUMP_POP) => { 400 self.ip_add(@intFromFloat(self.pop().number)); 401 }, 402 @intFromEnum(OP.LOOP) => { 403 self.ip_sub(self.read_short()); 404 }, 405 @intFromEnum(OP.GET_LOCAL) => { 406 self.push(self.frame().slots[self.read_byte()]); 407 }, 408 @intFromEnum(OP.SET_LOCAL) => { 409 self.frame().slots[self.read_byte()] = self.peek(0); 410 }, 411 @intFromEnum(OP.GET_PROPERTY) => { 412 var val = self.peek(0); 413 if (val.cast_if(Obj.Type.Instance)) |instance| { 414 const field = self.read_string(); 415 const prop = instance.fields.ptr().get(field) catch 416 Value.init((instance.method(&self.vm.objects, field) catch { 417 self.runtimeError("Undefined property '{f}'", .{field}); 418 return InterpreterError.RuntimeError; 419 }).cast()); 420 _ = self.pop(); 421 self.push(prop); 422 } else { 423 self.runtimeError("Only instances have properties, found: {s}", .{self.peek(0).typeName()}); 424 return InterpreterError.RuntimeError; 425 } 426 }, 427 @intFromEnum(OP.SET_PROPERTY) => { 428 if (self.peek(1).cast_if(Obj.Type.Instance)) |instance| { 429 _ = try instance.fields.ptr().set(self.read_string(), self.peek(0)); 430 const val = self.pop(); 431 _ = self.pop(); 432 self.push(val); 433 } else { 434 self.runtimeError("Only instances have properties, found: {s}", .{self.peek(0).typeName()}); 435 return InterpreterError.RuntimeError; 436 } 437 }, 438 @intFromEnum(OP.GET_GLOBAL) => { 439 const name = self.read_string(); 440 const global = self.vm.globals.get(name) catch { 441 self.runtimeError("Undefined variable: '{s}'", .{name.slice()}); 442 return InterpreterError.RuntimeError; 443 }; 444 self.push(global.val); 445 }, 446 @intFromEnum(OP.SET_GLOBAL) => { 447 const name = self.read_string(); 448 const replaced = self.vm.globals.replace_if(name, Global.make_var(self.peek(0)), Global.is_var) catch { 449 self.runtimeError("Undefined variable: '{s}'", .{name.slice()}); 450 return InterpreterError.RuntimeError; 451 }; 452 if (!replaced) { 453 self.runtimeError("Cannot assign to a constant: '{s}'", .{name.slice()}); 454 return InterpreterError.RuntimeError; 455 } 456 }, 457 @intFromEnum(OP.GET_UPVALUE) => { 458 const closure = self.frame().callee; 459 const index = self.read_byte(); 460 self.push(closure.upvalues.get(index).?.location.get()); 461 }, 462 @intFromEnum(OP.SET_UPVALUE) => { 463 const closure = self.frame().callee; 464 const index = self.read_byte(); 465 closure.upvalues.get(index).?.location.set(self.peek(0)); 466 }, 467 @intFromEnum(OP.CLOSE_UPVALUE) => { 468 try self.closeUpvalues(self.current_slot()); 469 _ = self.pop(); 470 }, 471 @intFromEnum(OP.GET_INDEX) => { 472 const key = self.pop(); 473 const col = self.pop(); 474 var pushed = false; 475 476 if (col.cast_if(Value.obj)) |obj| { 477 switch (obj.type) { 478 inline .Table, .String, .List => |tp| { 479 self.push((obj.cast(tp) catch unreachable).get(key) catch Value.init({})); 480 pushed = true; 481 }, 482 else => {}, 483 } 484 } 485 486 if (!pushed) { 487 self.runtimeError("Cannot index a value of type {s}", .{col.typeName()}); 488 return InterpreterError.RuntimeError; 489 } 490 }, 491 @intFromEnum(OP.SET_INDEX) => { 492 const val = self.pop(); 493 const key = self.pop(); 494 const col = self.pop(); 495 var pushed = false; 496 497 if (col.cast_if(Value.obj)) |obj| { 498 switch (obj.type) { 499 inline .Table, .List => |tp| { 500 var m = obj.cast(tp) catch unreachable; 501 if (val.is(Value.nil)) { 502 m.delete(key); 503 } else { 504 _ = try m.set(key, val); 505 } 506 pushed = true; 507 }, 508 else => {}, 509 } 510 } 511 if (!pushed) { 512 self.runtimeError("Cannot index a value of type {s}", .{col.typeName()}); 513 return InterpreterError.RuntimeError; 514 } 515 self.push(val); 516 }, 517 @intFromEnum(OP.CALL) => { 518 const argCount = self.read_byte(); 519 try self.callValue(self.peek(argCount), argCount); 520 }, 521 @intFromEnum(OP.CLOSURE) => { 522 const chunk = try self.read_constant().obj.cast(.Chunk); 523 const arity = self.read_byte(); 524 const count = self.read_byte(); 525 526 const closure = try self.vm.objects.emplace(.Function, GC.name_of(chunk.cast()), .{ 527 .chunk = chunk, 528 .arity = arity, 529 .upvalues = count, 530 }); 531 532 self.push(Value.init(closure.cast())); 533 534 for (closure.upvalues.ptr()) |*upvalue| { 535 const tp = self.read_byte(); 536 const slot = self.read_byte(); 537 const U = Compiler.Upvalue.Type; 538 upvalue.* = switch (tp) { 539 @intFromEnum(U.local) => try self.captureUpvalue(slot, false), 540 @intFromEnum(U.immediate) => try self.captureUpvalue(slot, true), 541 @intFromEnum(U.remote) => self.frame().callee.upvalues.get(slot), 542 @intFromEnum(U.empty) => null, 543 else => return InterpreterError.RuntimeError, 544 }; 545 } 546 }, 547 @intFromEnum(OP.METHOD) => { 548 const name = self.read_string(); 549 const offset = self.read_byte(); 550 const method = try self.pop().obj.cast(.Function); 551 const class = try self.peek(offset).obj.cast(.Class); 552 _ = try class.methods.ptr().set(name, method); 553 }, 554 @intFromEnum(OP.INHERIT) => { 555 const val = self.peek(0); 556 if (val.cast_if(Obj.Type.Class)) |super| { 557 const sub = self.peek(1).obj.cast(.Class) catch unreachable; 558 try sub.methods.ptr().addAll(super.methods.ptr()); 559 } else { 560 self.runtimeError("A class can only inherit from another class. Wrong type: {s}", .{val.typeName()}); 561 } 562 }, 563 @intFromEnum(OP.GET_SUPER) => { 564 const name = self.read_string(); 565 const super = try self.pop().obj.cast(.Class); 566 const this = try self.pop().obj.cast(.Instance); 567 568 self.push(Value.init((switch (try super.method(name)) { 569 .Static => |sta| sta, 570 .Unbound => |unb| try unb.bind(&self.vm.objects, this), 571 }).cast())); 572 }, 573 @intFromEnum(OP.DEFINE_GLOBAL) => _ = try self.vm.globals.set(self.read_string(), Global.make_var(self.pop())), 574 @intFromEnum(OP.DEFINE_GLOBAL_CONSTANT) => _ = try self.vm.globals.set(self.read_string(), Global.make_con(self.pop())), 575 @intFromEnum(OP.SUBTRACT) => try self.binary_op(Value.number, Value.number, callbacks.sub), 576 @intFromEnum(OP.MULTIPLY) => try self.binary_op(Value.number, Value.number, callbacks.mul), 577 @intFromEnum(OP.DIVIDE) => try self.binary_op(Value.number, Value.number, callbacks.div), 578 @intFromEnum(OP.TRUE) => self.push(Value.init(true)), 579 @intFromEnum(OP.FALSE) => self.push(Value.init(false)), 580 @intFromEnum(OP.EQUAL) => self.push(Value.init(self.pop().eql(self.pop()))), 581 @intFromEnum(OP.LESS) => try self.binary_op(Value.number, Value.bool, callbacks.less), 582 @intFromEnum(OP.GREATER) => try self.binary_op(Value.number, Value.bool, callbacks.more), 583 @intFromEnum(OP.NIL) => self.push(Value.init({})), 584 @intFromEnum(OP.NOT) => self.push(Value.init(!self.pop().isTruthy())), 585 else => return InterpreterError.CompileError, 586 } 587 } 588 } 589 590 fn runtimeError(self: *@This(), comptime fmt: []const u8, args: anytype) void { 591 var i = self.frameCount - 1; 592 while (true) : (i -= 1) { 593 const fram = self.frames[i]; 594 const idx = @intFromPtr(fram.ip) - @intFromPtr(fram.chunk.code.ptr().data.ptr); 595 std.debug.print("[line {d}] in {f}\n", .{ fram.chunk.lines.ptr().get(idx) orelse 1, fram.callee }); 596 if (i == 0) break; 597 } 598 std.debug.print(fmt ++ "\n", args); 599 } 600 }; 601 } 602 603 pub fn deinit(self: *@This()) void { 604 self.objects.deinit(); 605 self.globals.deinit(); 606 } 607 };