commit 50d0fdf0163453fc3bdbc44236bf7cdf7be97f99
parent 71497aa899a0cb743e3a4157f32963df070dedda
Author: Szymon Mikulicz <szymon.mikulicz@posteo.net>
Date: Fri, 15 Mar 2024 12:44:00 +0100
Merge branch 'main' of github.com:Ashymad/dlox
Diffstat:
13 files changed, 621 insertions(+), 111 deletions(-)
diff --git a/zlox/.gitignore b/zlox/.gitignore
@@ -1,2 +1,5 @@
zig-cache/
zig-out/
+.cache/
+.envrc
+.tool-versions
diff --git a/zlox/build.zig b/zlox/build.zig
@@ -24,14 +24,6 @@ pub fn build(b: *std.Build) void {
.optimize = optimize,
});
- const linenoize = b.dependency("linenoize", .{ // <== as declared in build.zig.zon
- .target = target, // the same as passing `-Dtarget=<...>` to the library's build.zig script
- .optimize = optimize, // ditto for `-Doptimize=<...>`
- }).module("linenoise");
-
- // your executable config
- exe.addModule("linenoize", linenoize); // <== for zig project
-
// This declares intent for the executable to be installed into the
// standard location when the user invokes the "install" step (the default
// step when running `zig build`).
@@ -60,10 +52,12 @@ pub fn build(b: *std.Build) void {
const run_step = b.step("run", "Run the app");
run_step.dependOn(&run_cmd.step);
+ exe.linkLibC();
+ exe.linkSystemLibrary("linenoise");
// Creates a step for unit testing. This only builds the test executable
// but does not run it.
const unit_tests = b.addTest(.{
- .root_source_file = .{ .path = "src/main.zig" },
+ .root_source_file = .{ .path = "src/test.zig" },
.target = target,
.optimize = optimize,
});
diff --git a/zlox/build.zig.zon b/zlox/build.zig.zon
@@ -1,13 +0,0 @@
-.{
- .name = "zlox",
- .version = "0.1.0",
- .paths = .{
- "./src",
- },
- .dependencies = .{
- .linenoize = .{
- .url = "https://github.com/joachimschmidt557/linenoize/archive/refs/heads/master.tar.gz",
- .hash = "122095273d370fe3a29c2cd98027bae899065db6d759f3eacf049c4941af113b099c",
- },
- },
-}
diff --git a/zlox/src/chunk.zig b/zlox/src/chunk.zig
@@ -5,34 +5,42 @@ const array = @import("array.zig");
pub const OP = enum(u8) {
CONSTANT,
+ NIL,
+ TRUE,
+ FALSE,
+ EQUAL,
+ GREATER,
+ LESS,
RETURN,
NEGATE,
ADD,
SUBTRACT,
MULTIPLY,
DIVIDE,
+ NOT,
};
+pub const ChunkError = error{OutOfMemory};
+
pub const Chunk = struct {
- pub fn init(allocator: std.mem.Allocator) !@This() {
+ pub fn init(allocator: std.mem.Allocator) ChunkError!@This() {
return @This(){
.code = try array.Array(u8, usize, 8).init(allocator),
.constants = try ValueArray.init(allocator),
- .lines = try array.RLEArray(u32, 8).init(allocator),
+ .lines = try array.RLEArray(i32, 8).init(allocator),
};
}
- pub fn write(self: *@This(), byte: u8, line: u32) !void {
+ pub fn write(self: *@This(), byte: u8, line: i32) ChunkError!void {
try self.code.add(byte);
try self.lines.add(line);
}
- pub fn writeOP(self: *@This(), op: OP, line: u32) !void {
- try self.code.add(@intFromEnum(op));
- try self.lines.add(line);
+ pub fn writeOP(self: *@This(), op: OP, line: i32) ChunkError!void {
+ try self.write(@intFromEnum(op), line);
}
- pub fn addConstant(self: *@This(), val: value.Value) !u8 {
+ pub fn addConstant(self: *@This(), val: value.Value) ChunkError!u8 {
try self.constants.add(val);
return self.constants.len - 1;
}
@@ -45,5 +53,5 @@ pub const Chunk = struct {
code: array.Array(u8, usize, 8),
constants: ValueArray,
- lines: array.RLEArray(u32, 8),
+ lines: array.RLEArray(i32, 8),
};
diff --git a/zlox/src/compiler.zig b/zlox/src/compiler.zig
@@ -1,23 +1,316 @@
const std = @import("std");
const scanner = @import("scanner.zig");
+const chunk = @import("chunk.zig");
+const Value = @import("value.zig").Value;
+const debug = @import("debug.zig");
-pub const CompilerError = scanner.ScannerError;
+pub const CompilerError = scanner.ScannerError || chunk.ChunkError || Value.ParseNumberError || error{ UnexpectedToken, NotAnExpression };
-pub fn compile(source: []const u8) CompilerError!void {
- var Scanner = scanner.Scanner.init(source);
+const Precedence = enum {
+ NONE,
+ ASSIGNMENT, // =
+ TERNARY, // ? :
+ OR, // or
+ AND, // and
+ EQUALITY, // == !=
+ COMPARISON, // < > <= >=
+ TERM, // + -
+ FACTOR, // * /
+ UNARY, // ! -
+ CALL, // . ()
+ PRIMARY,
- var line: i32 = -1;
+ pub fn inc(self: @This()) @This() {
+ return @enumFromInt(@intFromEnum(self) + 1);
+ }
+
+ pub fn lessOrEq(self: @This(), rhs: @This()) bool {
+ return @intFromEnum(self) <= @intFromEnum(rhs);
+ }
+};
+
+pub const Compiler = struct {
+ current: scanner.Token,
+ previous: scanner.Token,
+ scanner: scanner.Scanner,
+ lastError: CompilerError,
+ hadError: bool,
+ panicMode: bool,
+ compilingChunk: *chunk.Chunk,
+
+ const ParseFn = *const fn (*@This()) void;
+
+ const ParseRule = struct {
+ prefix: ?ParseFn,
+ infix: ?ParseFn,
+ precedence: Precedence,
+ pub fn init(prefix: ?ParseFn, infix: ?ParseFn, precedence: Precedence) @This() {
+ return @This(){ .prefix = prefix, .infix = infix, .precedence = precedence };
+ }
+ };
+
+ const rules = init: {
+ var new: [@typeInfo(scanner.TokenType).Enum.fields.len]ParseRule = undefined;
+ for (&new, 0..) |*v, i| {
+ const T = scanner.TokenType;
+ const S = @This();
+ const R = ParseRule.init;
+ const P = Precedence;
+ const tok: T = @enumFromInt(i);
+ v.* = switch (tok) {
+ // zig fmt: off
+ T.LEFT_PAREN => R(S.grouping, null, P.NONE ),
+ T.RIGHT_PAREN => R(null, null, P.NONE ),
+ T.LEFT_BRACE => R(null, null, P.NONE ),
+ T.RIGHT_BRACE => R(null, null, P.NONE ),
+ T.COMMA => R(null, null, P.NONE ),
+ T.DOT => R(null, null, P.NONE ),
+ T.MINUS => R(S.unary, S.binary, P.TERM ),
+ T.PLUS => R(null, S.binary, P.TERM ),
+ T.COLON => R(null, null, P.NONE ),
+ T.SEMICOLON => R(null, null, P.NONE ),
+ T.SLASH => R(null, S.binary, P.FACTOR ),
+ T.STAR => R(null, S.binary, P.FACTOR ),
+ T.QUESTION => R(null, S.ternary, P.TERNARY ),
+ T.BANG => R(S.unary, null, P.NONE ),
+ T.BANG_EQUAL => R(null, S.binary, P.EQUALITY ),
+ T.EQUAL => R(null, null, P.NONE ),
+ T.EQUAL_EQUAL => R(null, S.binary, P.EQUALITY ),
+ T.GREATER => R(null, S.binary, P.COMPARISON ),
+ T.GREATER_EQUAL => R(null, S.binary, P.COMPARISON ),
+ T.LESS => R(null, S.binary, P.COMPARISON ),
+ T.LESS_EQUAL => R(null, S.binary, P.COMPARISON ),
+ T.IDENTIFIER => R(null, null, P.NONE ),
+ T.STRING => R(null, null, P.NONE ),
+ T.NUMBER => R(S.number, null, P.NONE ),
+ T.AND => R(null, null, P.NONE ),
+ T.CLASS => R(null, null, P.NONE ),
+ T.ELSE => R(null, null, P.NONE ),
+ T.FALSE => R(S.literal, null, P.NONE ),
+ T.FOR => R(null, null, P.NONE ),
+ T.FUN => R(null, null, P.NONE ),
+ T.IF => R(null, null, P.NONE ),
+ T.NIL => R(S.literal, null, P.NONE ),
+ T.OR => R(null, null, P.NONE ),
+ T.PRINT => R(null, null, P.NONE ),
+ T.RETURN => R(null, null, P.NONE ),
+ T.SUPER => R(null, null, P.NONE ),
+ T.THIS => R(null, null, P.NONE ),
+ T.TRUE => R(S.literal, null, P.NONE ),
+ T.VAR => R(null, null, P.NONE ),
+ T.WHILE => R(null, null, P.NONE ),
+ T.EOF => R(null, null, P.NONE ),
+ // zig fmt: on
+ };
+ }
+ break :init new;
+ };
+
+ fn getRule(tok: scanner.TokenType) *const ParseRule {
+ return &Compiler.rules[@intFromEnum(tok)];
+ }
+
+ fn advance(self: *@This()) void {
+ self.previous = self.current;
+
+ while (true) {
+ self.current = self.scanner.scanToken();
+
+ if (self.current.type) |_| {
+ break;
+ } else |err| {
+ self.lastError = err;
+ self.errorAtCurrent(scanner.ScannerErrorString(err));
+ }
+ }
+ }
+
+ fn currentChunk(self: *@This()) *chunk.Chunk {
+ return self.compilingChunk;
+ }
- while (true) {
- const token = try Scanner.scanToken();
- if (token.line != line) {
- std.debug.print("{d:4} ", .{token.line});
- line = token.line;
+ fn emitByte(self: *@This(), byte: u8) void {
+ self.currentChunk().write(byte, self.previous.line) catch |err| {
+ self.lastError = err;
+ self.errorAtCurrent("Out of Memory");
+ };
+ }
+
+ fn emitOP(self: *@This(), op: chunk.OP) void {
+ self.currentChunk().writeOP(op, self.previous.line) catch |err| {
+ self.lastError = err;
+ self.errorAtCurrent("Out of Memory");
+ };
+ }
+
+ fn emit(self: *@This(), op: chunk.OP, byte: u8) void {
+ self.emitOP(op);
+ self.emitByte(byte);
+ }
+
+ fn emit2OP(self: *@This(), op: chunk.OP, op2: chunk.OP) void {
+ self.emitOP(op);
+ self.emitOP(op2);
+ }
+
+ fn endCompiler(self: *@This()) void {
+ self.emitReturn();
+ if (!self.hadError) {
+ debug.disassembleChunk(self.currentChunk().*, "code") catch {
+ std.debug.print("Unable to disassemble chunk\n", .{});
+ };
+ }
+ }
+
+ fn emitReturn(self: *@This()) void {
+ self.emitOP(chunk.OP.RETURN);
+ }
+
+ fn errorAtCurrent(self: *@This(), message: []const u8) void {
+ self.errorAt(self.current, message);
+ }
+
+ fn errorAtPrevious(self: *@This(), message: []const u8) void {
+ self.errorAt(self.previous, message);
+ }
+
+ fn expression(self: *@This()) void {
+ self.parsePrecedence(Precedence.ASSIGNMENT);
+ }
+
+ fn parsePrecedence(self: *@This(), precedence: Precedence) void {
+ self.advance();
+ if (getRule(self.previous.type catch unreachable).prefix) |prefixRule| {
+ prefixRule(self);
} else {
- std.debug.print(" | ", .{});
+ self.lastError = CompilerError.NotAnExpression;
+ self.errorAtPrevious("Expect expression.");
+ return;
+ }
+
+ while (precedence.lessOrEq(getRule(self.current.type catch unreachable).precedence)) {
+ self.advance();
+ if (getRule(self.previous.type catch unreachable).infix) |infixRule| {
+ infixRule(self);
+ } else {
+ self.lastError = CompilerError.NotAnExpression;
+ self.errorAtPrevious("Expect expression.");
+ return;
+ }
}
- std.debug.print("{s:15} '{s}'\n", .{ @tagName(token.type), token.lexeme });
+ }
+
+ fn errorAt(self: *@This(), token: scanner.Token, message: []const u8) void {
+ if (self.panicMode) return;
+ self.panicMode = true;
+ std.debug.print("[{d}:{d}] Error", .{ token.line, token.column });
+ if (token.type) |tpe| {
+ if (tpe == scanner.TokenType.EOF) {
+ std.debug.print(" at end", .{});
+ } else {
+ std.debug.print(" at {s}", .{token.lexeme});
+ }
+ } else |_| {}
+ std.debug.print(": {s}\n", .{message});
+ self.hadError = true;
+ }
+
+ fn consume(self: *@This(), tok: scanner.TokenType, message: []const u8) void {
+ if (self.current.type) |tpe| {
+ if (tpe == tok) {
+ self.advance();
+ return;
+ }
+ } else |_| {}
+ self.lastError = CompilerError.UnexpectedToken;
+ self.errorAtCurrent(message);
+ }
+
+ fn number(self: *@This()) void {
+ self.emitConstant(Value.parseNumber(self.previous.lexeme) catch |err| {
+ self.lastError = err;
+ self.errorAtPrevious("Invalid numeric literal");
+ return;
+ });
+ }
+
+ fn emitConstant(self: *@This(), val: Value) void {
+ self.emit(chunk.OP.CONSTANT, self.makeConstant(val));
+ }
+
+ fn makeConstant(self: *@This(), val: Value) u8 {
+ return self.currentChunk().addConstant(val) catch |err| {
+ self.lastError = err;
+ self.errorAtPrevious("Too many constants in one chunk");
+ return 0;
+ };
+ }
+
+ fn grouping(self: *@This()) void {
+ self.expression();
+ self.consume(scanner.TokenType.RIGHT_PAREN, "Expected ')' after expression");
+ }
+
+ fn unary(self: *@This()) void {
+ const operatorType = self.previous.type catch unreachable;
+
+ self.parsePrecedence(Precedence.UNARY);
+
+ switch (operatorType) {
+ scanner.TokenType.MINUS => self.emitOP(chunk.OP.NEGATE),
+ scanner.TokenType.BANG => self.emitOP(chunk.OP.NOT),
+ else => unreachable,
+ }
+ }
+
+ fn literal(self: *@This()) void {
+ switch (self.previous.type catch unreachable) {
+ scanner.TokenType.FALSE => self.emitOP(chunk.OP.FALSE),
+ scanner.TokenType.TRUE => self.emitOP(chunk.OP.TRUE),
+ scanner.TokenType.NIL => self.emitOP(chunk.OP.NIL),
+ else => unreachable,
+ }
+ }
+
+ fn binary(self: *@This()) void {
+ const operatorType = self.previous.type catch unreachable;
+ self.parsePrecedence(getRule(operatorType).precedence.inc());
+
+ switch (operatorType) {
+ scanner.TokenType.PLUS => self.emitOP(chunk.OP.ADD),
+ scanner.TokenType.MINUS => self.emitOP(chunk.OP.SUBTRACT),
+ scanner.TokenType.STAR => self.emitOP(chunk.OP.MULTIPLY),
+ scanner.TokenType.SLASH => self.emitOP(chunk.OP.DIVIDE),
+ scanner.TokenType.BANG_EQUAL => self.emit2OP(chunk.OP.EQUAL, chunk.OP.NOT),
+ scanner.TokenType.EQUAL_EQUAL => self.emitOP(chunk.OP.EQUAL),
+ scanner.TokenType.GREATER => self.emitOP(chunk.OP.GREATER),
+ scanner.TokenType.GREATER_EQUAL => self.emit2OP(chunk.OP.LESS, chunk.OP.NOT),
+ scanner.TokenType.LESS => self.emitOP(chunk.OP.LESS),
+ scanner.TokenType.LESS_EQUAL => self.emit2OP(chunk.OP.GREATER, chunk.OP.NOT),
+ else => unreachable,
+ }
+ }
+
+ fn ternary(self: *@This()) void {
+ const operatorType = self.previous.type catch unreachable;
+ self.parsePrecedence(getRule(operatorType).precedence.inc());
+
+ // emit bytecode
+
+ self.consume(scanner.TokenType.COLON, "Expected ':' in ternary expression.");
+
+ self.parsePrecedence(getRule(operatorType).precedence.inc());
+
+ // emit bytecode
+ }
+
+ pub fn compile(source: []const u8, ch: *chunk.Chunk) CompilerError!void {
+ var self = @This(){ .scanner = try scanner.Scanner.init(source), .current = scanner.Token.Empty, .previous = scanner.Token.Empty, .panicMode = false, .hadError = false, .lastError = scanner.ScannerError.EmptyToken, .compilingChunk = ch };
+ self.advance();
+ self.expression();
+ self.consume(scanner.TokenType.EOF, "Expected end of expression.");
+ self.endCompiler();
- if (token.type == scanner.TokenType.EOF) break;
+ if (self.hadError) return self.lastError;
}
-}
+};
diff --git a/zlox/src/debug.zig b/zlox/src/debug.zig
@@ -29,6 +29,13 @@ pub fn disassembleInstruction(ch: chunk.Chunk, offset: usize) !usize {
@intFromEnum(OP.SUBTRACT) => simpleInstruction("OP_SUBTRACT", offset),
@intFromEnum(OP.DIVIDE) => simpleInstruction("OP_DIVIDE", offset),
@intFromEnum(OP.MULTIPLY) => simpleInstruction("OP_MULTIPLY", offset),
+ @intFromEnum(OP.TRUE) => simpleInstruction("OP_TRUE", offset),
+ @intFromEnum(OP.FALSE) => simpleInstruction("OP_FALSE", offset),
+ @intFromEnum(OP.EQUAL) => simpleInstruction("OP_EQUAL", offset),
+ @intFromEnum(OP.LESS) => simpleInstruction("OP_LESS", offset),
+ @intFromEnum(OP.GREATER) => simpleInstruction("OP_GREATER", offset),
+ @intFromEnum(OP.NIL) => simpleInstruction("OP_NIL", offset),
+ @intFromEnum(OP.NOT) => simpleInstruction("OP_NOT", offset),
@intFromEnum(OP.CONSTANT) => try constantInstruction("OP_CONSTANT", ch, offset),
else => blk: {
print("Unknown opcode {}\n", .{try ch.code.get(offset)});
@@ -45,7 +52,7 @@ fn simpleInstruction(name: []const u8, offset: usize) usize {
fn constantInstruction(name: []const u8, ch: chunk.Chunk, offset: usize) !usize {
const constant = try ch.code.get(offset + 1);
print("{s:<16} {d:4} '", .{ name, constant });
- value.printValue(try ch.constants.get(constant));
+ (try ch.constants.get(constant)).print();
print("'\n", .{});
return offset + 2;
}
diff --git a/zlox/src/main.zig b/zlox/src/main.zig
@@ -1,6 +1,9 @@
const std = @import("std");
const vm = @import("vm.zig");
-const Linenoise = @import("linenoize").Linenoise;
+const Linenoise = @cImport({
+ @cInclude("stddef.h");
+ @cInclude("linenoise.h");
+});
pub fn main() anyerror!u8 {
var gpa = std.heap.GeneralPurposeAllocator(.{}){};
@@ -27,20 +30,21 @@ pub fn runFile(allocator: std.mem.Allocator, path: []const u8) anyerror!void {
const file = try std.fs.cwd().openFile(path, .{});
defer file.close();
- var text = try file.reader().readAllAlloc(allocator, 999999);
+ const text = try file.reader().readAllAlloc(allocator, 999999);
defer allocator.free(text);
}
pub fn repl(allocator: std.mem.Allocator) anyerror!void {
- var ln = Linenoise.init(allocator);
- defer ln.deinit();
-
var VM = vm.VM.init();
defer VM.deinit();
- while (try ln.linenoise("lox> ")) |input| {
- defer allocator.free(input);
- try VM.interpret(input);
- try ln.history.add(input);
+ _ = Linenoise.linenoiseHistorySetMaxLen(100);
+
+ while (Linenoise.linenoise("lox> ")) |line| {
+ defer Linenoise.linenoiseFree(line);
+ VM.interpret(std.mem.span(line), allocator) catch |err| {
+ std.debug.print("Error: {}\n", .{err});
+ };
+ _ = Linenoise.linenoiseHistoryAdd(line);
}
}
diff --git a/zlox/src/scanner.zig b/zlox/src/scanner.zig
@@ -1,4 +1,5 @@
const std = @import("std");
+const trie = @import("trie.zig");
pub const TokenType = enum {
LEFT_PAREN,
@@ -9,9 +10,11 @@ pub const TokenType = enum {
DOT,
MINUS,
PLUS,
+ COLON,
SEMICOLON,
SLASH,
STAR,
+ QUESTION,
// One or two character tokens.
BANG,
BANG_EQUAL,
@@ -46,33 +49,63 @@ pub const TokenType = enum {
EOF,
};
-pub const ScannerError = error{ UnexpectedCharacter, UnknownCharacter, UnterminatedString };
+pub const ScannerError = error{ UnexpectedCharacter, UnknownCharacter, UnterminatedString, EmptyToken };
+
+pub fn ScannerErrorString(err: ScannerError) []const u8 {
+ return switch (err) {
+ ScannerError.UnknownCharacter => "Unknown Character",
+ ScannerError.UnexpectedCharacter => "Unexpected Character",
+ ScannerError.UnterminatedString => "Unterminated String",
+ ScannerError.EmptyToken => "Empty Token",
+ };
+}
pub const Token = struct {
- type: TokenType,
+ type: ScannerError!TokenType,
lexeme: []const u8,
line: i32,
-};
+ column: usize,
-const keywords: [][]const u8 = [_][]const u8{"while"};
+ pub const Empty = @This(){ .type = ScannerError.EmptyToken, .lexeme = "", .line = -1, .column = 0 };
+};
pub const Scanner = struct {
- pub fn init(source: []const u8) @This() {
- return @This(){ .start = source.ptr, .current = source.ptr, .end = source.ptr + source.len, .line = 0 };
- }
+ const identifiers = trie.LowercaseTrieTable(TokenType, .{
+ .{ "and", TokenType.AND },
+ .{ "class", TokenType.CLASS },
+ .{ "else", TokenType.ELSE },
+ .{ "false", TokenType.FALSE },
+ .{ "for", TokenType.FOR },
+ .{ "fun", TokenType.FUN },
+ .{ "if", TokenType.IF },
+ .{ "nil", TokenType.NIL },
+ .{ "or", TokenType.OR },
+ .{ "print", TokenType.PRINT },
+ .{ "return", TokenType.RETURN },
+ .{ "super", TokenType.SUPER },
+ .{ "this", TokenType.THIS },
+ .{ "true", TokenType.TRUE },
+ .{ "var", TokenType.VAR },
+ .{ "while", TokenType.WHILE },
+ });
+
+ pub fn init(source: []const u8) !@This() {
+ return @This(){ .start = source.ptr, .current = source.ptr, .end = source.ptr + source.len, .line_ptr = source.ptr, .line = 0 };
+ }
+
+ pub fn scanToken(self: *@This()) Token {
+ self.skipWhitespace();
- pub fn scanToken(self: *@This()) ScannerError!Token {
self.start = self.current;
if (self.isAtEnd()) return self.makeToken(TokenType.EOF);
- self.skipWhitespace();
-
switch (self.advance()) {
'(' => return self.makeToken(TokenType.LEFT_PAREN),
')' => return self.makeToken(TokenType.RIGHT_PAREN),
'{' => return self.makeToken(TokenType.LEFT_BRACE),
'}' => return self.makeToken(TokenType.RIGHT_BRACE),
+ ':' => return self.makeToken(TokenType.COLON),
';' => return self.makeToken(TokenType.SEMICOLON),
',' => return self.makeToken(TokenType.COMMA),
'.' => return self.makeToken(TokenType.DOT),
@@ -80,6 +113,7 @@ pub const Scanner = struct {
'+' => return self.makeToken(TokenType.PLUS),
'/' => return self.makeToken(TokenType.SLASH),
'*' => return self.makeToken(TokenType.STAR),
+ '?' => return self.makeToken(TokenType.QUESTION),
'!' => return self.makeToken(if (self.match('=')) TokenType.BANG_EQUAL else TokenType.BANG),
'=' => return self.makeToken(if (self.match('=')) TokenType.EQUAL_EQUAL else TokenType.EQUAL),
'<' => return self.makeToken(if (self.match('=')) TokenType.LESS_EQUAL else TokenType.LESS),
@@ -87,19 +121,19 @@ pub const Scanner = struct {
'"' => return self.string(),
'0'...'9' => return self.number(),
'a'...'z', 'A'...'Z', '_' => return self.identifier(),
- else => return ScannerError.UnknownCharacter,
+ else => return self.makeToken(ScannerError.UnknownCharacter),
}
- return ScannerError.UnexpectedCharacter;
+ return self.makeToken(ScannerError.UnexpectedCharacter);
}
- fn string(self: *@This()) ScannerError!Token {
+ fn string(self: *@This()) Token {
while (self.peek() != '"' and !self.isAtEnd()) {
if (self.peek() == '\n') self.line += 1;
_ = self.advance();
}
- if (self.isAtEnd()) return ScannerError.UnterminatedString;
+ if (self.isAtEnd()) return self.makeToken(ScannerError.UnterminatedString);
_ = self.advance();
@@ -113,6 +147,7 @@ pub const Scanner = struct {
'\n' => {
self.line += 1;
_ = self.advance();
+ self.line_ptr = self.current;
},
'/' => {
if (self.peekNext() == '/') {
@@ -141,18 +176,11 @@ pub const Scanner = struct {
}
fn identifierType(self: *const @This()) TokenType {
- return switch (self.start[0]) {
- 'a' => self.checkKeyword(1, "nd", TokenType.AND),
- else => TokenType.IDENTIFIER,
- };
- }
-
- fn checkKeyword(self: *const @This(), start: u8, rest: []const u8, token: TokenType) TokenType {
- return if (@intFromPtr(self.current) - @intFromPtr(self.start) == start + rest.len and
- std.mem.eql(u8, self.start[start .. start + rest.len], rest))
- token
- else
- TokenType.IDENTIFIER;
+ if (identifiers.get(self.lexeme())) |tok| {
+ return tok;
+ } else {
+ return TokenType.IDENTIFIER;
+ }
}
fn advance(self: *@This()) u8 {
@@ -187,12 +215,25 @@ pub const Scanner = struct {
return self.current == self.end;
}
- fn makeToken(self: *const @This(), tokentype: TokenType) Token {
- return Token{ .type = tokentype, .lexeme = self.start[0..(@intFromPtr(self.current) - @intFromPtr(self.start))], .line = self.line };
+ fn makeToken(self: *const @This(), tokentype: ScannerError!TokenType) Token {
+ return Token{ .type = tokentype, .lexeme = self.lexeme(), .line = self.line, .column = self.column() };
+ }
+
+ fn lexeme_len(self: *const @This()) usize {
+ return @intFromPtr(self.current) - @intFromPtr(self.start);
+ }
+
+ fn column(self: *const @This()) usize {
+ return @intFromPtr(self.start) - @intFromPtr(self.line_ptr);
+ }
+
+ fn lexeme(self: *const @This()) []const u8 {
+ return self.start[0..self.lexeme_len()];
}
start: [*]const u8,
current: [*]const u8,
end: [*]const u8,
+ line_ptr: [*]const u8,
line: i32,
};
diff --git a/zlox/src/test.zig b/zlox/src/test.zig
@@ -2,8 +2,9 @@ const std = @import("std");
const chunk = @import("chunk.zig");
const debug = @import("debug.zig");
const vm = @import("vm.zig");
+const Trie = @import("trie.zig").TrieTable;
-fn testChunk() anyerror!void {
+test "testChunk" {
var allocator = std.heap.GeneralPurposeAllocator(.{}){};
defer std.debug.assert(allocator.deinit() == std.heap.Check.ok);
var ch = try chunk.Chunk.init(allocator.allocator());
@@ -29,4 +30,13 @@ fn testChunk() anyerror!void {
try ch.writeOP(chunk.OP.RETURN, 123);
try VM.interpretChunk(&ch);
+
+ try std.testing.expect(VM.pop() == -((1.2 + 3.4) / 5.6));
+}
+
+test "testTrie" {
+ const tr = Trie(u8, .{.{ "test", 16 }});
+
+ try std.testing.expectEqual(tr.get("test").?, 16);
+ try std.testing.expectEqual(tr.get("tes"), null);
}
diff --git a/zlox/src/trie.zig b/zlox/src/trie.zig
@@ -1,5 +1,69 @@
-pub fn Trie(comptime T: type) type {
+const std = @import("std");
+
+pub fn TrieTable(comptime Key: type, comptime Value: type, size: comptime_int, get_idx: fn (Key) usize, comptime list: anytype) type {
+ const TrieLeaf = struct {
+ value: ?Value,
+ data: [size]?*@This(),
+ };
+
+ const max_len = comptime blk: {
+ var ret = 0;
+ for (list) |el| {
+ ret += el.@"0".len;
+ }
+ break :blk ret;
+ };
+
+ const precomputed = comptime blk: {
+ var allocated = [_]TrieLeaf{TrieLeaf{ .value = null, .data = [_]?*TrieLeaf{null} ** size }} ** max_len;
+ var allocated_i = 0;
+ var tip = TrieLeaf{ .value = null, .data = [_]?*TrieLeaf{null} ** size };
+
+ for (list) |el| {
+ var leaf = &tip;
+ for (el.@"0") |key| {
+ const idx = get_idx(key);
+ std.debug.assert(idx >= 0 and idx < size);
+ if (leaf.data[idx]) |val| {
+ leaf = val;
+ } else {
+ var new = &allocated[allocated_i];
+ allocated_i += 1;
+ new.value = null;
+ new.data = [_]?*TrieLeaf{null} ** size;
+ leaf.data[idx] = new;
+ leaf = new;
+ }
+ }
+ leaf.value = el.@"1";
+ }
+ break :blk .{ .allocated = allocated[0..allocated_i], .tip = tip };
+ };
+
return struct {
- len: S,
- data: []T,
- allocator: std.mem.Allocator,
+ const allocated = precomputed.allocated;
+ const tip = precomputed.tip;
+
+ pub fn get(word: []const Key) ?Value {
+ var this = &tip;
+ for (word) |key| {
+ const idx = get_idx(key);
+ if (idx < 0 or idx >= size) return null;
+ if (this.data[idx]) |val| {
+ this = val;
+ } else {
+ return null;
+ }
+ }
+ return this.value;
+ }
+ };
+}
+
+pub fn LowercaseTrieTable(comptime Value: type, comptime list: anytype) type {
+ return TrieTable(u8, Value, 26, struct {
+ pub fn idx(c: u8) usize {
+ return c - 'a';
+ }
+ }.idx, list);
+}
diff --git a/zlox/src/value.zig b/zlox/src/value.zig
@@ -1,10 +1,66 @@
const std = @import("std");
const array = @import("array.zig");
-pub const Value = f64;
+pub const Value = union(enum) {
+ number: f64,
+ bool: bool,
+ nil: void,
-pub fn printValue(value: Value) void {
- std.debug.print("{d}", .{value});
-}
+ pub const Tag = std.meta.Tag(@This());
+
+ pub fn print(self: @This()) void {
+ switch (self) {
+ .number => |val| std.debug.print("{d}", .{val}),
+ .bool => |val| std.debug.print("{s}", .{if (val) "true" else "false"}),
+ .nil => std.debug.print("nil", .{}),
+ }
+ }
+
+ pub fn is(self: @This(), comptime tag: Tag) bool {
+ return switch (self) {
+ tag => true,
+ else => false,
+ };
+ }
+
+ pub fn new(comptime tag: Tag, value: tagType(tag)) @This() {
+ return @unionInit(@This(), @tagName(tag), value);
+ }
+
+ pub fn get(self: @This(), comptime tag: Tag) tagType(tag) {
+ return @field(self, @tagName(tag));
+ }
+
+ pub fn set(self: *@This(), comptime tag: Tag, value: tagType(tag)) void {
+ @field(self, @tagName(tag)) = value;
+ }
+
+ pub fn tagType(comptime tag: Tag) type {
+ return @TypeOf(@field(@unionInit(@This(), @tagName(tag), undefined), @tagName(tag)));
+ }
+
+ pub const ParseNumberError = std.fmt.ParseFloatError;
+
+ pub fn parseNumber(str: []const u8) ParseNumberError!@This() {
+ return @This(){ .number = try std.fmt.parseFloat(tagType(Value.number), str) };
+ }
+
+ pub fn isTruthy(self: @This()) bool {
+ return switch (self) {
+ .nil => false,
+ .bool => |val| val,
+ else => true,
+ };
+ }
+
+ pub fn equal(self: @This(), other: @This()) bool {
+ if (@intFromEnum(self) != @intFromEnum(other)) return false;
+ return switch (self) {
+ .number => |x| x == other.number,
+ .bool => |x| x == other.bool,
+ .nil => true,
+ };
+ }
+};
pub const ValueArray = array.Array(Value, u8, 8);
diff --git a/zlox/src/vm.zig b/zlox/src/vm.zig
@@ -1,27 +1,27 @@
const Chunk = @import("chunk.zig").Chunk;
const OP = @import("chunk.zig").OP;
-const value = @import("value.zig");
+const Value = @import("value.zig").Value;
const std = @import("std");
const debug = @import("debug.zig");
const wrp = @import("wrap.zig");
const compiler = @import("compiler.zig");
-pub const InterpreterError = compiler.CompilerError || error{ CompileError, RuntimeError, IndexOutOfBounds, Overflow, DivisionByZero };
+pub const InterpreterError = compiler.CompilerError || error{ OutOfMemory, CompileError, RuntimeError, IndexOutOfBounds, Overflow, DivisionByZero };
pub const VM = struct {
ip: [*]const u8,
chunk: *const Chunk,
stack: stackType,
- stackTop: [*]value.Value,
+ stackTop: [*]Value,
const stackSize = 256;
- const stackType = [stackSize]value.Value;
+ const stackType = [stackSize]Value;
pub fn init() @This() {
var ret = @This(){
.ip = undefined,
.chunk = undefined,
- .stack = std.mem.zeroes(@This().stackType),
+ .stack = [_]Value{Value{ .number = 0 }} ** stackSize,
.stackTop = undefined,
};
ret.stackTop = &ret.stack;
@@ -35,8 +35,13 @@ pub const VM = struct {
try self.run(true);
}
- pub fn interpret(self: *@This(), source: []const u8) InterpreterError!void {
- try compiler.compile(source);
+ pub fn interpret(self: *@This(), source: []const u8, allocator: std.mem.Allocator) InterpreterError!void {
+ var chunk = try Chunk.init(allocator);
+ defer chunk.deinit();
+
+ try compiler.Compiler.compile(source, &chunk);
+
+ try self.interpretChunk(&chunk);
self.resetStack();
}
@@ -50,43 +55,56 @@ pub const VM = struct {
return out;
}
- fn read_constant(self: *@This()) value.Value {
+ fn read_constant(self: *@This()) Value {
return self.chunk.constants.data[self.read_byte()];
}
- fn push(self: *@This(), val: value.Value) void {
+ fn push(self: *@This(), val: Value) void {
self.stackTop[0] = val;
self.stackTop += 1;
}
- fn pop(self: *@This()) value.Value {
+ pub fn pop(self: *@This()) Value {
self.stackTop -= 1;
return self.stackTop[0];
}
- fn binary_op(self: *@This(), comptime op: fn (comptime T: type, value.Value, value.Value) value.Value) void {
+ pub fn peek(self: *const @This(), distance: usize) Value {
+ return (self.stackTop - (1 + distance))[0];
+ }
+
+ fn binary_op(self: *@This(), comptime in_tag: Value.Tag, comptime out_tag: Value.Tag, op: fn (type, Value.tagType(in_tag), Value.tagType(in_tag)) Value.tagType(out_tag)) !void {
const b = self.pop();
const a = self.pop();
- self.push(op(value.Value, a, b));
+ if (a.is(in_tag) and b.is(in_tag)) {
+ self.push(Value.new(out_tag, op(Value.tagType(in_tag), a.get(in_tag), b.get(in_tag))));
+ } else {
+ self.runtimeError("Operands have invalid types, expected: {s}", .{@tagName(in_tag)});
+ return InterpreterError.RuntimeError;
+ }
+ }
+
+ fn instruction_idx(self: *const @This()) usize {
+ return @intFromPtr(self.ip) - @intFromPtr(self.chunk.code.data.ptr);
}
fn run(self: *@This(), comptime dbg: bool) !void {
while (true) {
if (dbg) {
std.debug.print(" ", .{});
- var stackPtr: [*]value.Value = &self.stack;
+ var stackPtr: [*]Value = &self.stack;
while (stackPtr != self.stackTop) : (stackPtr += 1) {
std.debug.print("[ ", .{});
- value.printValue(stackPtr[0]);
+ stackPtr[0].print();
std.debug.print(" ]", .{});
}
std.debug.print("\n", .{});
}
- _ = try debug.disassembleInstruction(self.chunk.*, @intFromPtr(self.ip) - @intFromPtr(self.chunk.code.data.ptr));
+ _ = try debug.disassembleInstruction(self.chunk.*, self.instruction_idx());
const instruction: u8 = self.read_byte();
switch (instruction) {
@intFromEnum(OP.RETURN) => {
- value.printValue(self.pop());
+ self.pop().print();
std.debug.print("\n", .{});
return;
},
@@ -94,15 +112,34 @@ pub const VM = struct {
const constant = self.read_constant();
self.push(constant);
},
- @intFromEnum(OP.NEGATE) => self.push(-self.pop()),
- @intFromEnum(OP.ADD) => self.binary_op(wrp.add),
- @intFromEnum(OP.SUBTRACT) => self.binary_op(wrp.sub),
- @intFromEnum(OP.MULTIPLY) => self.binary_op(wrp.mul),
- @intFromEnum(OP.DIVIDE) => self.binary_op(wrp.div),
+ @intFromEnum(OP.NEGATE) => {
+ if (!self.peek(0).is(Value.number)) {
+ self.runtimeError("Operand must be a number.", .{});
+ return InterpreterError.RuntimeError;
+ }
+ self.push(Value{ .number = -self.pop().number });
+ },
+ @intFromEnum(OP.ADD) => try self.binary_op(Value.number, Value.number, wrp.add),
+ @intFromEnum(OP.SUBTRACT) => try self.binary_op(Value.number, Value.number, wrp.sub),
+ @intFromEnum(OP.MULTIPLY) => try self.binary_op(Value.number, Value.number, wrp.mul),
+ @intFromEnum(OP.DIVIDE) => try self.binary_op(Value.number, Value.number, wrp.div),
+ @intFromEnum(OP.TRUE) => self.push(Value{ .bool = true }),
+ @intFromEnum(OP.FALSE) => self.push(Value{ .bool = false }),
+ @intFromEnum(OP.EQUAL) => self.push(Value{ .bool = self.pop().equal(self.pop()) }),
+ @intFromEnum(OP.LESS) => try self.binary_op(Value.number, Value.bool, wrp.less),
+ @intFromEnum(OP.GREATER) => try self.binary_op(Value.number, Value.bool, wrp.more),
+ @intFromEnum(OP.NIL) => self.push(Value{ .nil = undefined }),
+ @intFromEnum(OP.NOT) => self.push(Value{ .bool = !self.pop().isTruthy() }),
else => return InterpreterError.CompileError,
}
}
}
+ fn runtimeError(self: *@This(), comptime fmt: []const u8, args: anytype) void {
+ std.debug.print(fmt, args);
+ std.debug.print("\n[line {d}] in script\n", .{self.chunk.lines.get(self.instruction_idx()) catch 0});
+ self.resetStack();
+ }
+
pub fn deinit(_: *@This()) void {}
};
diff --git a/zlox/src/wrap.zig b/zlox/src/wrap.zig
@@ -10,3 +10,9 @@ pub fn sub(comptime T: type, a: T, b: T) T {
pub fn div(comptime T: type, a: T, b: T) T {
return a / b;
}
+pub fn less(comptime T: type, a: T, b: T) bool {
+ return a < b;
+}
+pub fn more(comptime T: type, a: T, b: T) bool {
+ return a > b;
+}
