commit 372a5c516991a81012d7b7031dc39f4b88b81db1
parent 06108bc2948c70884037f64dd333fae93f07df2c
Author: Ashymad <szymon.mikulicz@posteo.net>
Date: Tue, 27 Feb 2024 21:56:32 +0100
Implement a trie for identifiers
Diffstat:
8 files changed, 115 insertions(+), 58 deletions(-)
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.root_module.addImport("linenoize", linenoize);
-
// 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 = "12201240f2e3bd999a7846b8d408c2b59243f2ea427efe5cdb99091d28bb9ebc9287",
- },
- },
-}
diff --git a/zlox/src/compiler.zig b/zlox/src/compiler.zig
@@ -3,8 +3,9 @@ const scanner = @import("scanner.zig");
pub const CompilerError = scanner.ScannerError;
-pub fn compile(source: []const u8) CompilerError!void {
- var Scanner = scanner.Scanner.init(source);
+pub fn compile(source: []const u8, allocator: std.mem.Allocator) !void {
+ var Scanner = try scanner.Scanner.init(source, allocator);
+ defer Scanner.deinit();
var line: i32 = -1;
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(.{}){};
@@ -32,15 +35,14 @@ pub fn runFile(allocator: std.mem.Allocator, path: []const u8) anyerror!void {
}
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);
+ try VM.interpret(std.mem.span(line), allocator);
+ _ = 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,
@@ -54,11 +55,30 @@ pub const Token = struct {
line: i32,
};
-const keywords: [][]const u8 = [_][]const u8{"while"};
-
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 };
+ pub fn init(source: []const u8, allocator: std.mem.Allocator) !@This() {
+ var this = @This(){ .start = source.ptr, .current = source.ptr, .end = source.ptr + source.len, .line = 0, .identifiers = try trie.TrieTable(TokenType).init(allocator) };
+ try this.identifiers.put("and", TokenType.AND);
+ try this.identifiers.put("class", TokenType.CLASS);
+ try this.identifiers.put("else", TokenType.ELSE);
+ try this.identifiers.put("false", TokenType.FALSE);
+ try this.identifiers.put("for", TokenType.FOR);
+ try this.identifiers.put("fun", TokenType.FUN);
+ try this.identifiers.put("if", TokenType.IF);
+ try this.identifiers.put("nil", TokenType.NIL);
+ try this.identifiers.put("or", TokenType.OR);
+ try this.identifiers.put("print", TokenType.PRINT);
+ try this.identifiers.put("return", TokenType.RETURN);
+ try this.identifiers.put("super", TokenType.SUPER);
+ try this.identifiers.put("this", TokenType.THIS);
+ try this.identifiers.put("true", TokenType.TRUE);
+ try this.identifiers.put("var", TokenType.VAR);
+ try this.identifiers.put("while", TokenType.WHILE);
+ return this;
+ }
+
+ pub fn deinit(self: *@This()) void {
+ self.identifiers.deinit();
}
pub fn scanToken(self: *@This()) ScannerError!Token {
@@ -141,18 +161,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 (self.identifiers.get(self.start[0..(@intFromPtr(self.current) - @intFromPtr(self.start))])) |tok| {
+ return tok;
+ } else {
+ return TokenType.IDENTIFIER;
+ }
}
fn advance(self: *@This()) u8 {
@@ -191,6 +204,7 @@ pub const Scanner = struct {
return Token{ .type = tokentype, .lexeme = self.start[0..(@intFromPtr(self.current) - @intFromPtr(self.start))], .line = self.line };
}
+ identifiers: trie.TrieTable(TokenType),
start: [*]const u8,
current: [*]const u8,
end: [*]const u8,
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,19 @@ 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" {
+ var allocator = std.heap.GeneralPurposeAllocator(.{}){};
+ defer std.debug.assert(allocator.deinit() == std.heap.Check.ok);
+
+ var tr = try Trie(u8).init(allocator.allocator());
+ defer tr.deinit();
+
+ try tr.put("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,50 @@
-pub fn Trie(comptime T: type) type {
+const std = @import("std");
+
+pub fn TrieTable(comptime T: type) type {
return struct {
- len: S,
- data: []T,
- allocator: std.mem.Allocator,
+ value: ?T,
+ data: [26]?*@This(),
+ allocator: ?std.heap.ArenaAllocator,
+
+ pub fn init(allocator: std.mem.Allocator) !@This() {
+ return @This(){ .value = null, .data = [_]?*@This(){null} ** 26, .allocator = std.heap.ArenaAllocator.init(allocator) };
+ }
+
+ pub fn put(self: *@This(), word: []const u8, value: T) !void {
+ var this = self;
+ const allo = self.allocator.?.allocator();
+ for (word) |ch| {
+ const idx = ch - 'a';
+ if (this.data[idx]) |val| {
+ this = val;
+ } else {
+ var new = try allo.create(@This());
+ new.value = null;
+ new.data = [_]?*@This(){null} ** 26;
+ new.allocator = null;
+ this.data[idx] = new;
+ this = new;
+ }
+ }
+ this.value = value;
+ }
+
+ pub fn get(self: *const @This(), word: []const u8) ?T {
+ var this = self;
+ for (word) |ch| {
+ if (ch < 'a' or ch > 'z') return null;
+ const idx = ch - 'a';
+ if (this.data[idx]) |val| {
+ this = val;
+ } else {
+ return null;
+ }
+ }
+ return this.value;
+ }
+
+ pub fn deinit(self: *@This()) void {
+ self.allocator.?.deinit();
+ }
+ };
+}
diff --git a/zlox/src/vm.zig b/zlox/src/vm.zig
@@ -35,8 +35,8 @@ 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) !void {
+ try compiler.compile(source, allocator);
self.resetStack();
}
@@ -59,7 +59,7 @@ pub const VM = struct {
self.stackTop += 1;
}
- fn pop(self: *@This()) value.Value {
+ pub fn pop(self: *@This()) value.Value {
self.stackTop -= 1;
return self.stackTop[0];
}
@@ -86,8 +86,6 @@ pub const VM = struct {
const instruction: u8 = self.read_byte();
switch (instruction) {
@intFromEnum(OP.RETURN) => {
- value.printValue(self.pop());
- std.debug.print("\n", .{});
return;
},
@intFromEnum(OP.CONSTANT) => {
