commit 943c350baf98205945d065bb36f13418ad714d3b
parent 178c73563c5c855333dc303d829d01cb337846b9
Author: Ashymad <szymon.mikulicz@posteo.net>
Date: Tue, 9 Apr 2024 22:56:09 +0200
HashTable + String interning
Diffstat:
7 files changed, 208 insertions(+), 90 deletions(-)
diff --git a/zlox/src/chunk.zig b/zlox/src/chunk.zig
@@ -29,8 +29,6 @@ pub const Chunk = struct {
.code = try array.Array(u8, usize, 8).init(allocator),
.constants = try ValueArray.init(allocator),
.lines = try array.RLEArray(i32, 8).init(allocator),
- .allocator = allocator,
- .objects = null,
};
}
@@ -45,30 +43,15 @@ pub const Chunk = struct {
pub fn addConstant(self: *@This(), val: value.Value) Error!u8 {
try self.constants.add(val);
- self.addObject(val);
return self.constants.len - 1;
}
- pub fn addObject(self: *@This(), val: value.Value) void {
- if (val.is(value.Value.obj)) {
- val.obj.next = self.objects;
- self.objects = val.obj;
- }
- }
-
pub fn deinit(self: *@This()) void {
self.constants.deinit();
self.lines.deinit();
self.code.deinit();
-
- while (self.objects) |obj| {
- self.objects = obj.next;
- obj.free(self.allocator);
- }
}
- objects: ?*Obj,
- allocator: std.mem.Allocator,
code: array.Array(u8, usize, 8),
constants: ValueArray,
lines: array.RLEArray(i32, 8),
diff --git a/zlox/src/compiler.zig b/zlox/src/compiler.zig
@@ -6,7 +6,7 @@ const Value = @import("value.zig").Value;
const Obj = @import("obj.zig").Obj;
const debug = @import("debug.zig");
-pub const CompilerError = scanner.ScannerError || Chunk.Error || Value.ParseNumberError || error{ UnexpectedToken, NotAnExpression };
+pub const CompilerError = Obj.Error || scanner.ScannerError || Chunk.Error || Value.ParseNumberError || error{ UnexpectedToken, NotAnExpression };
const Precedence = enum {
NONE,
@@ -40,6 +40,16 @@ pub const Compiler = struct {
panicMode: bool,
compilingChunk: Chunk,
allocator: std.mem.Allocator,
+ objects: Obj.List,
+
+ pub const Result = struct {
+ chunk: Chunk,
+ objects: Obj.List,
+ pub fn deinit(self: *@This()) void {
+ self.objects.deinit();
+ self.chunk.deinit();
+ }
+ };
const ParseFn = *const fn (*@This()) void;
@@ -238,7 +248,7 @@ pub const Compiler = struct {
}
fn string(self: *@This()) void {
- self.emitConstant(Value.init(Obj.init(.String, self.previous.lexeme[1 .. self.previous.lexeme.len - 1], self.allocator) catch |err| {
+ self.emitConstant(Value.init(self.objects.emplace(.String, &[_][]const u8{self.previous.lexeme[1 .. self.previous.lexeme.len - 1]}) catch |err| {
self.lastError = err;
self.errorAtPrevious("Couldn't allocate object");
return;
@@ -315,15 +325,16 @@ pub const Compiler = struct {
// emit bytecode
}
- pub fn compile(source: []const u8, allocator: std.mem.Allocator) CompilerError!Chunk {
- 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 = try Chunk.init(allocator), .allocator = allocator };
+ pub fn compile(source: []const u8, allocator: std.mem.Allocator) CompilerError!Result {
+ 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 = try Chunk.init(allocator), .allocator = allocator, .objects = Obj.List.init(allocator) };
errdefer self.compilingChunk.deinit();
+ errdefer self.objects.deinit();
self.advance();
self.expression();
self.consume(scanner.TokenType.EOF, "Expected end of expression.");
self.endCompiler();
- return if (self.hadError) self.lastError else self.compilingChunk;
+ return if (self.hadError) self.lastError else Result{ .chunk = self.compilingChunk, .objects = self.objects };
}
};
diff --git a/zlox/src/hash.zig b/zlox/src/hash.zig
@@ -1,20 +1,35 @@
const Obj = @import("obj.zig").Obj;
-pub fn hash_t(T: type) fn (T) u32 {
+pub fn hash_append_t(T: type) fn (u32, T) u32 {
return switch (T) {
[]const u8, [*]const u8, []u8, [*]u8 => struct {
- pub fn fun(key: T) u32 {
- var ret: u32 = 2166136261;
- for (key) |char| {
+ pub fn fun(old: u32, val: T) u32 {
+ var ret = old;
+ for (val) |char| {
ret ^= char;
- ret *= 16777619;
+ ret *%= 16777619;
}
return ret;
}
}.fun,
- Obj, *Obj, *const Obj => struct {
- pub fn fun(key: T) u32 {
- return key.hash;
+ else => @compileError("Unsupported type"),
+ };
+}
+
+pub fn hash_append(ret: u32, val: anytype) u32 {
+ return hash_append_t(@TypeOf(val))(ret, val);
+}
+
+pub fn hash_t(T: type) fn (T) u32 {
+ return switch (T) {
+ []const u8, [*]const u8, []u8, [*]u8 => struct {
+ pub fn fun(val: T) u32 {
+ return hash_append_t(T)(2166136261, val);
+ }
+ }.fun,
+ Obj.String, *Obj.String, *const Obj.String => struct {
+ pub fn fun(val: T) u32 {
+ return val.hash;
}
}.fun,
else => @compileError("Unsupported type"),
diff --git a/zlox/src/obj.zig b/zlox/src/obj.zig
@@ -1,51 +1,94 @@
const std = @import("std");
const utils = @import("comptime_utils.zig");
-const hash = @import("hash.zig").hash;
+const hash = @import("hash.zig");
+const table = @import("table.zig");
pub const Obj = packed struct {
const Super = @This();
- pub const Error = error{IllegalCastError};
+ pub const Error = table.TableError || error{ OutOfMemory, IllegalCastError, NotFound };
type: Type,
- next: ?*Super = null,
- hash: u32,
- pub const List = struct {};
+ pub const List = struct {
+ const Self = @This();
+ const Element = struct {
+ obj: *Super,
+ next: ?*@This(),
+ };
+
+ tip: ?*Element,
+ allocator: std.mem.Allocator,
+ map: String.Table,
+
+ pub fn init(allocator: std.mem.Allocator) Self {
+ return Self{ .tip = null, .allocator = allocator, .map = String.Table.init(allocator) };
+ }
+
+ pub fn push(self: *Self, val: *Super) Error!void {
+ var new_tip = try self.allocator.create(Element);
+ new_tip.next = self.tip;
+ new_tip.obj = val;
+ self.tip = new_tip;
+ }
+
+ pub fn emplace(self: *Self, comptime tp: Type, arg: tp.get().Arg) Error!*Super {
+ var newObj = true;
+ const obj = switch (tp) {
+ .String => (try String.intern(arg, &self.map, &newObj, self.allocator)).cast(),
+ };
+ if (newObj) try self.push(obj);
+ return obj;
+ }
+
+ pub fn pop(self: *Self) ?*Element {
+ if (self.tip) |tip| {
+ self.tip = tip.next;
+ tip.obj.free(self.allocator);
+ return tip;
+ }
+ return null;
+ }
+
+ pub fn deinit(self: *Self) void {
+ while (self.pop()) |tip| {
+ self.allocator.destroy(tip);
+ }
+ self.map.deinit();
+ }
+ };
pub const String = packed struct {
const Self = @This();
- const Arg = []const u8;
+ pub const Table = table.Table(*Self, void, hash.hash_t(*const Self), Self.eql);
+ pub const Arg = []const []const u8;
obj: Super,
len: usize,
+ hash: u32,
fn data(self: anytype) utils.copy_const(@TypeOf(self), [*]u8) {
const p: utils.copy_const(@TypeOf(self), [*]u8) = @ptrCast(self);
return p + @sizeOf(Self);
}
- fn new(len: usize, allocator: std.mem.Allocator) !*Self {
- const ret: *Self = @ptrCast(try allocator.alignedAlloc(u8, @alignOf(Self), @sizeOf(Self) + len));
- ret.* = Self{ .obj = Super{
- .type = Super.Type.String,
- .hash = 0,
- }, .len = len };
+ fn new(arg: Arg, params: ArgParams, allocator: std.mem.Allocator) Error!*Self {
+ const ret: *Self = @ptrCast(try allocator.alignedAlloc(u8, @alignOf(Self), @sizeOf(Self) + params.len));
+ ret.* = Self{
+ .obj = Super{
+ .type = Super.Type.String,
+ },
+ .len = 0,
+ .hash = params.hash,
+ };
+ for (arg) |el| {
+ @memcpy(ret.data() + ret.len, el);
+ ret.len += el.len;
+ }
return ret;
}
- fn rehash(self: *Self) void {
- self.obj.hash = hash(self.slice());
- }
pub fn slice(self: *const Self) []const u8 {
return self.data()[0..self.len];
}
- pub fn cat(self: *const Self, other: *const Self, allocator: std.mem.Allocator) !*Self {
- var ret = try new(self.len + other.len, allocator);
- @memcpy(ret.data(), self.slice());
- @memcpy(ret.data() + self.len, other.slice());
- ret.rehash();
- return ret;
- }
-
pub fn cast(self: *Self) *Super {
return @ptrCast(self);
}
@@ -55,12 +98,54 @@ pub const Obj = packed struct {
pub fn eql(self: *const Self, other: *const Self) bool {
return @intFromPtr(self) == @intFromPtr(other);
}
- pub fn init(string: Arg, allocator: std.mem.Allocator) !*Self {
- var ret = try new(string.len, allocator);
- @memcpy(ret.data(), string);
- ret.rehash();
+
+ const ArgParams = struct { len: usize, hash: u32 };
+
+ fn map_check(m_arg: Arg, m_params: ArgParams) struct {
+ arg: Arg,
+ params: ArgParams,
+ pub fn check(self: *const @This(), k2: *const Self) bool {
+ if (k2.hash == self.params.hash and k2.len == self.params.len) {
+ var idx: usize = 0;
+ for (self.arg) |el| {
+ if (!std.mem.eql(u8, k2.data()[idx .. idx + el.len], el))
+ return false;
+ idx += el.len;
+ }
+ return true;
+ }
+ return false;
+ }
+ } {
+ return @TypeOf(map_check(m_arg, m_params)){ .arg = m_arg, .params = m_params };
+ }
+
+ fn arg_params(arg: Arg) ArgParams {
+ var ret = ArgParams{ .len = 0, .hash = hash.hash_t([]const u8)(&.{}) };
+
+ for (arg) |el| {
+ ret.len += el.len;
+ ret.hash = hash.hash_append(ret.hash, el);
+ }
return ret;
}
+
+ pub fn intern(arg: Arg, map: *Table, isNewKey: *bool, allocator: std.mem.Allocator) Error!*Self {
+ const params = arg_params(arg);
+
+ try map.checkCapacity();
+ const entry = Table.find_(map.entries, params.hash, map_check(arg, params));
+ isNewKey.* = entry.* != Table.Entry.some;
+ if (isNewKey.*) {
+ _ = map.set_(entry, try new(arg, params, allocator), {});
+ }
+ return entry.some.key;
+ }
+
+ pub fn init(arg: Arg, allocator: std.mem.Allocator) Error!*Self {
+ return try new(arg, arg_params(arg), allocator);
+ }
+
fn free(self: *const Self, allocator: std.mem.Allocator) void {
const p: [*]align(@alignOf(Self)) const u8 = @ptrCast(self);
allocator.free(p[0 .. @sizeOf(Self) + self.len]);
diff --git a/zlox/src/table.zig b/zlox/src/table.zig
@@ -5,9 +5,9 @@ pub const TableError = error{ OutOfMemory, KeyError };
pub fn Table(K: type, V: type, hash_fn: fn (K) u32, cmp_fn: fn (K, K) bool) type {
return struct {
const Self = @This();
- const MaxLoad = 0.75;
+ const MaxLoad: f32 = 0.75;
- const Entry = union(enum) {
+ pub const Entry = union(enum) {
const Some = struct {
key: K,
value: V,
@@ -34,14 +34,14 @@ pub fn Table(K: type, V: type, hash_fn: fn (K) u32, cmp_fn: fn (K, K) bool) type
fn adjustCapacity(self: *Self, newsize: usize) TableError!void {
const entries = try self.allocator.alloc(Entry, newsize);
- for (entries) |entry| {
- entry = .none;
+ for (entries) |*entry| {
+ entry.* = .none;
}
self.count = 0;
for (self.entries) |entry| {
switch (entry) {
.some => |some| {
- (find(entries, some.key)) = entry;
+ find(entries, some.key).* = entry;
self.count += 1;
},
else => {},
@@ -50,17 +50,27 @@ pub fn Table(K: type, V: type, hash_fn: fn (K) u32, cmp_fn: fn (K, K) bool) type
self.allocator.free(self.entries);
self.entries = entries;
}
+ const find_check = struct {
+ k: K,
+ pub fn check(self: *const @This(), k2: K) bool {
+ return cmp_fn(self.k, k2);
+ }
+ };
+
+ pub fn find(entries: []Entry, key: K) *Entry {
+ return find_(entries, hash_fn(key), find_check{ .k = key });
+ }
- fn find(entries: []Entry, key: K) *Entry {
- const idx = hash_fn(key) % entries.len;
+ pub fn find_(entries: []Entry, hash: u32, check: anytype) *Entry {
+ var idx = hash % entries.len;
var tomb: ?*Entry = null;
while (true) {
const entry = &entries[idx];
- switch (entry) {
- .some => |some| if (cmp_fn(some.key, key)) return entry,
- .tomb => tomb = if (tomb) |_| tomb else entry,
- .none => return if (tomb) |_| tomb else entry,
+ switch (entry.*) {
+ .some => |some| if (check.check(some.key)) return entry,
+ .tomb => tomb = if (tomb) |t| t else entry,
+ .none => return if (tomb) |t| t else entry,
}
idx = (idx + 1) % entries.len;
}
@@ -75,21 +85,33 @@ pub fn Table(K: type, V: type, hash_fn: fn (K) u32, cmp_fn: fn (K, K) bool) type
}
}
- pub fn set(self: *Self, key: K, val: V) TableError!bool {
- if (self.count + 1 > self.entries.len * MaxLoad) {
- try self.adjustCapacity(self.growCapacity());
- }
- var entry = find(self.entries, key);
- const isNewKey = switch (entry) {
- .none => self.count += 1 or true,
+ pub fn set_(self: *Self, entry: *Entry, key: K, val: V) bool {
+ const isNewKey = switch (entry.*) {
+ .none => blk: {
+ self.count += 1;
+ break :blk true;
+ },
.tomb => true,
.some => false,
};
- entry.some = Entry.Some{ .key = key, .value = val };
+ entry.* = Entry{ .some = Entry.Some{ .key = key, .value = val } };
return isNewKey;
}
+ pub fn checkCapacity(self: *Self) TableError!void {
+ const len: f32 = @floatFromInt(self.entries.len);
+ const count: f32 = @floatFromInt(self.count);
+ if (count + 1.0 > len * MaxLoad) {
+ try self.adjustCapacity(self.growCapacity());
+ }
+ }
+
+ pub fn set(self: *Self, key: K, val: V) TableError!bool {
+ try self.checkCapacity();
+ return set_(find(self.entries, key), key, val);
+ }
+
pub fn get(self: *const Self, key: K) TableError!V {
if (self.entries.len == 0)
return TableError.KeyError;
diff --git a/zlox/src/vm.zig b/zlox/src/vm.zig
@@ -12,6 +12,7 @@ pub const InterpreterError = compiler.CompilerError || Callback.Error || error{
pub const VM = struct {
ip: [*]const u8,
chunk: *Chunk,
+ objects: *Obj.List,
stack: stackType,
stackTop: [*]Value,
@@ -22,25 +23,27 @@ pub const VM = struct {
var ret = @This(){
.ip = undefined,
.chunk = undefined,
- .stack = [_]Value{Value{ .number = 0 }} ** stackSize,
+ .objects = undefined,
+ .stack = [_]Value{Value.init({})} ** stackSize,
.stackTop = undefined,
};
ret.stackTop = &ret.stack;
return ret;
}
- pub fn interpretChunk(self: *@This(), chunk: *Chunk, allocator: std.mem.Allocator) InterpreterError!void {
+ pub fn interpretChunk(self: *@This(), chunk: *Chunk) InterpreterError!void {
self.resetStack();
self.chunk = chunk;
self.ip = chunk.code.data.ptr;
- try self.run(true, allocator);
+ try self.run(true);
}
pub fn interpret(self: *@This(), source: []const u8, allocator: std.mem.Allocator) InterpreterError!void {
- var chunk = try compiler.Compiler.compile(source, allocator);
- defer chunk.deinit();
+ var result = try compiler.Compiler.compile(source, allocator);
+ defer result.deinit();
+ self.objects = &result.objects;
- try self.interpretChunk(&chunk, allocator);
+ try self.interpretChunk(&result.chunk);
self.resetStack();
}
@@ -87,7 +90,7 @@ pub const VM = struct {
return @intFromPtr(self.ip) - @intFromPtr(self.chunk.code.data.ptr);
}
- fn run(self: *@This(), comptime dbg: bool, allocator: std.mem.Allocator) !void {
+ fn run(self: *@This(), comptime dbg: bool) !void {
while (true) {
if (dbg) {
std.debug.print(" ", .{});
@@ -120,8 +123,7 @@ pub const VM = struct {
},
@intFromEnum(OP.ADD) => {
if (self.peek(0).is(Obj.Type.String)) {
- try self.binary_op(Obj.Type.String, Obj.Type.String, Callback.concatenate(allocator));
- self.chunk.addObject(self.peek(0));
+ try self.binary_op(Obj.Type.String, Obj.Type.String, Callback.concatenate(self.objects));
} else {
try self.binary_op(Value.number, Value.number, Callback.add);
}
diff --git a/zlox/src/vm_callbacks.zig b/zlox/src/vm_callbacks.zig
@@ -5,12 +5,12 @@ const Obj = @import("obj.zig").Obj;
const Number = Value.tagType(.number);
const Bool = Value.tagType(.bool);
-pub const Error = error{OutOfMemory};
+pub const Error = Obj.Error;
pub fn Type(comptime in_tag: anytype, comptime out_tag: anytype) type {
if (@TypeOf(in_tag) == Obj.Type) {
return struct {
- allocator: std.mem.Allocator,
+ objects: *Obj.List,
_call: *const fn (self: *const @This(), Value.tagType(in_tag), Value.tagType(in_tag)) Error!Value.tagType(out_tag),
pub fn call(self: *const @This(), a: Value.tagType(in_tag), b: Value.tagType(in_tag)) Error!Value.tagType(out_tag) {
return self._call(self, a, b);
@@ -23,11 +23,11 @@ pub fn Type(comptime in_tag: anytype, comptime out_tag: anytype) type {
}
}
-pub fn concatenate(allocator: std.mem.Allocator) Type(Obj.Type.String, Obj.Type.String) {
+pub fn concatenate(objects: *Obj.List) Type(Obj.Type.String, Obj.Type.String) {
const Ret = Type(Obj.Type.String, Obj.Type.String);
- const ret = Ret{ .allocator = allocator, ._call = struct {
+ const ret = Ret{ .objects = objects, ._call = struct {
pub fn concatenate(self: *const Ret, lhs: *Obj, rhs: *Obj) Error!*Obj {
- return (try (lhs.cast(.String) catch unreachable).cat(rhs.cast(.String) catch unreachable, self.allocator)).cast();
+ return try self.objects.emplace(.String, &[_][]const u8{ (lhs.cast(.String) catch unreachable).slice(), (rhs.cast(.String) catch unreachable).slice() });
}
}.concatenate };
return ret;
