From 591d4ac404f3fd9e7b5bb8947a2ed0096683a41b Mon Sep 17 00:00:00 2001 From: cassowarii Date: Wed, 1 Jul 2026 21:26:53 -0700 Subject: [PATCH] LEXICAL CLOSURES --- src/compile/emit.c | 52 ++++++++++++-- src/compile/ir.c | 196 ++++++++++++++++++++++++++++++++++++++++++++------- src/compile/ir.h | 13 ++-- src/data/closure.c | 89 +++++++++++++++++++++++ src/data/closure.h | 15 ++++ src/data/data.c | 6 ++ src/data/hashtable.c | 18 ++--- src/data/reference.c | 49 +++++++++++++ src/data/reference.h | 11 +++ src/data/value.h | 9 ++- src/global.h | 4 +- src/mem/buffer.h | 6 ++ src/parse/parser.c | 8 ++- src/vm/bytecode.h | 5 ++ src/vm/exec.c | 111 +++++++++++++++++++++++++---- src/vm/exec.h | 1 + 16 files changed, 531 insertions(+), 62 deletions(-) create mode 100644 src/data/closure.c create mode 100644 src/data/closure.h create mode 100644 src/data/reference.c create mode 100644 src/data/reference.h diff --git a/src/compile/emit.c b/src/compile/emit.c index f208e3a..249daa8 100644 --- a/src/compile/emit.c +++ b/src/compile/emit.c @@ -162,11 +162,21 @@ void compile_stmt(sbVmCompiler *cm, sbIrStmt *stmt) { break; case IR_S_ASSIGN: compile_expr(cm, stmt->assign.expr); - EMIT(BC_ST_VAR); + if (stmt->assign.var->is_upvalue) { + EMIT(BC_ST_UPVAL); + } else if (stmt->assign.var->closed_over) { + EMIT(BC_ST_IND); + } else { + EMIT(BC_ST_VAR); + } EARG(stmt->assign.var->slot_id); break; case IR_S_ARG: - EMIT(BC_ST_ARG); + if (stmt->arg.var->closed_over) { + EMIT(BC_ST_ARG_IND); + } else { + EMIT(BC_ST_ARG); + } EARG(stmt->arg.var->slot_id); break; case IR_S_RETURN: @@ -224,12 +234,45 @@ void compile_expr(sbVmCompiler *cm, sbIrExpr *expr) { EMIT(BC_CALL); break; case IR_E_VAR: - EMIT(BC_LD_VAR); + if (expr->var->is_upvalue) { + EMIT(BC_LD_UPVAL); + } else if (expr->var->closed_over) { + EMIT(BC_LD_IND); + } else { + EMIT(BC_LD_VAR); + } EARG(expr->var->slot_id); break; case IR_E_FUNC: + if (expr->func.bound.size > 0) { + BUFFER_ITER(expr->func.bound, sbIrVariable*, var) { + if ((*var)->is_upvalue) { + /* the closure-generator expects a series of values + * of type reference to close over. BC_LD_UPVAL normally + * pushes whatever is *behind* the reference, which we + * don't want. UPREF will push the reference value + * itself from the closure so we can close over it + * a second time */ + EMIT(BC_LD_UPREF); + } else if ((*var)->closed_over) { + /* note: BC_LD_VAR here, not BC_LD_IND! this will push + * the pointer value, not the variable itself, because + * we want to put the pointer (well, the sbRef) inside + * the closure, not the value */ + EMIT(BC_LD_VAR); + } else { + PANIC("cannot have a direct variable in closure!"); + } + EARG((*var)->slot_id); + } + } EMIT(BC_LD_BLK); - EARG(expr->func->id); + EARG(expr->func.chunk->id); + if (expr->func.bound.size > 0) { + EMIT(BC_CLOSURE); + /* record number of variables we are closing over */ + EARG(expr->func.bound.size / sizeof(sbIrVariable*)); + } break; case IR_E_LIST: compile_list(cm, expr); @@ -250,6 +293,7 @@ void compile_expr(sbVmCompiler *cm, sbIrExpr *expr) { EMIT(BC_LD_IMM); EARG(expr->value.integer); } else { + /* TODO Deduplicate constants */ u32 constant_index = sbVmCompiler_add_constant(cm, &expr->value); EMIT(BC_LD_CONST); EARG(constant_index); diff --git a/src/compile/ir.c b/src/compile/ir.c index c635d44..16aca5d 100644 --- a/src/compile/ir.c +++ b/src/compile/ir.c @@ -48,7 +48,11 @@ void sbIrProgram_print(hIrProgram ir) { for (usize i = 0; i < nchunks; i++) { sbIrChunk *ck = ((sbIrChunk**)ir->chunks.data)[i]; - debug("\nCHUNK %d with %d variables\n", ck->id, ck->variable_count); + debug("\nCHUNK %d with %d variables", ck->id, ck->variable_count); + if (ck->num_upvalues > 0) { + debug(" and %d upvalues", ck->num_upvalues); + } + debug("\n"); usize nstmts = ck->stmts.size / sizeof(sbIrStmt*); for (usize j = 0; j < nstmts; j++) { @@ -96,6 +100,7 @@ static sbIrChunk *new_chunk(hIrProgram ir) { usize nchunks = ir->chunks.size / sizeof(sbIrChunk*); sbIrChunk *chunk = sbArena_alloc(&ir->arena, sizeof(sbIrChunk)); sbBuffer_initialize(&chunk->stmts, 1024); + sbBuffer_initialize(&chunk->closed_vars, 256); chunk->id = nchunks; chunk->program = ir; @@ -114,18 +119,126 @@ static void chunk_deinitialize(hIrChunk ck) { sbBuffer_deinitialize(&ck->stmts); } +/* find variables that already exist */ +static sbIrVariable *existing_var(hIrChunk ck, const char *name, usize name_len, usize *index_out) { + usize index = 0; + BUFFER_ITER(ck->program->varmapping, varmapentry, entry) { + if (sbstrncmp(name, entry->name, name_len) == 0) { + if (index_out) *index_out = index; + return entry->var; + } + index ++; + } + return NO_VAR; +} + +/* Create an 'upvalue' variable that refers to a normal variable from an outer scope. */ +static sbIrVariable *create_upvalue(sbIrChunk *ck, sbIrVariable *v, usize slot_id) { + sbIrVariable *new_var = sbArena_alloc(&ck->program->arena, sizeof(sbIrVariable)); + new_var->is_upvalue = TRUE; + + /* Upvalues have their own series of sequential IDs distinct from normal variables. */ + new_var->slot_id = slot_id; + + /* We always assume closed-over variables are initialized. (We should detect this and + * fail if not.) */ + new_var->initialized = TRUE; + + /* Upvalues actually can be closed over, but when initially created they won't be. */ + new_var->closed_over = FALSE; + + /* This tells us where in the sequence of nested scopes this variable exists. */ + new_var->mapping_index = v->mapping_index; + + return new_var; +} + +/* inside a function, when we find a variable from outer scope, we need to (A) mark the + * variable to say it needs to be stored on the heap / indirectly in a reference, and + * (B) we need to write down that our *function* closes over this variable so that at + * the place where the function is constructed we can tell the program to save the function + * value with that variable's value */ +static sbIrVariable *register_upvalue(hIrChunk ck, usize variable_index) { + varmapentry *e = &BUFFER_INDEX(ck->program->varmapping, varmapentry, variable_index); + debug("%s is an upvalue! (because %zu < %d)\n", e->name, variable_index, ck->lowest_var_id); + e->var->closed_over = TRUE; + + sbIrVariable *existing_upvalue = NULL; + BUFFER_ITER(ck->closed_vars, sbIrVariable*, var) { + if ((*var)->mapping_index == variable_index) { + existing_upvalue = *var; + break; + } + } + + if (!existing_upvalue) { + /* Record that we close over this index so that the outer function knows to record + * it when creating our closure. (It might, itself, need to close over stuff as + * well...) */ + sbIrVariable *upvalue_var = create_upvalue(ck, e->var, ck->num_upvalues); + sbBuffer_append(&ck->closed_vars, &upvalue_var, sizeof(sbIrVariable*)); + ck->num_upvalues ++; + return upvalue_var; + } else { + return existing_upvalue; + } +} + +/* When we have compiled a chunk and are inserting its ID into the code, we need + * to mark which variables are being bound into its closure -- ok, fine, but we + * also need to check if those variables are external *to us* also so that we can + * know whether we need to pull them from *our* upvalues or our normal variables + * (and also so that our outer function knows to close over them for us when it + * is creating us, even if we ourselves don't actually use them) */ +static sbIrVariable *bind_upvalue(hIrChunk ck, usize variable_index) { + if (variable_index >= ck->lowest_var_id) { + /* inner function wants one of our normal variables */ + return BUFFER_INDEX(ck->program->varmapping, varmapentry, variable_index).var; + } else { + /* need to close over this from *our* outer scope as well... */ + return register_upvalue(ck, variable_index); + } +} + +/* to look up a variable name in source code */ +static sbIrVariable *var_name(hIrChunk ck, const char *name, usize name_len) { + usize index; + sbIrVariable *v = existing_var(ck, name, name_len, &index); + + if (v == NO_VAR) { + /* TODO do a different thing here */ + chunk_error(ck, "unknown variable name! '%s'\n", name); + } + + if (index >= ck->lowest_var_id) { + /* normal variable in inner function scope */ + return v; + } else { + /* closed over variable from outer scope */ + return register_upvalue(ck, index); + } +} + /* we can introduce new variables into a scope using LET */ static sbIrVariable *create_var(hIrChunk ck, const char *name, usize name_len) { sbIrVariable *new_var = sbArena_alloc(&ck->program->arena, sizeof(sbIrVariable)); + sbIrVariable *already_existing = existing_var(ck, name, name_len, NULL); + if (already_existing != NO_VAR) { + // TODO this should probably just be a warning + chunk_error(ck, "redeclaration of variable '%s'!\n", name); + return NO_VAR; + } + usize nvars = ck->program->varmapping.size / sizeof(varmapentry); *new_var = (sbIrVariable) {0}; - new_var->slot_id = nvars - ck->lowest_var_id + 1; - if (new_var->slot_id > ck->variable_count) { + new_var->slot_id = nvars - ck->lowest_var_id; + new_var->mapping_index = nvars; + if (new_var->slot_id + 1 > ck->variable_count) { /* store max variable slot count used so we know how many * need to be allocated for our chunk */ - ck->variable_count = new_var->slot_id; + ck->variable_count = new_var->slot_id + 1; } sbBuffer_append(&ck->program->varmapping, &(varmapentry) { @@ -137,21 +250,6 @@ static sbIrVariable *create_var(hIrChunk ck, const char *name, usize name_len) { return new_var; } -/* find variables that already exist */ -static sbIrVariable *var_name(hIrChunk ck, const char *name, usize name_len) { - usize nvars = ck->program->varmapping.size / sizeof(varmapentry); - for (usize i = ck->lowest_var_id; i < nvars; i++) { - varmapentry *entry = &((varmapentry*)ck->program->varmapping.data)[i]; - if (sbstrncmp(name, entry->name, name_len) == 0) { - return entry->var; - } - } - - /* TODO do a different thing here */ - chunk_error(ck, "unknown variable name! '%s'\n", name); - return NO_VAR; -} - static sbIrLabel *new_label(hIrChunk ck) { sbIrLabel *l = sbArena_alloc(&ck->program->arena, sizeof(sbIrLabel)); ck->label_count ++; @@ -180,9 +278,25 @@ static sbIrExpr *expr_value(hIrChunk ck, hV *value) { } static sbIrExpr *expr_func(hIrChunk ck, sbIrChunk *func) { + /* when creating a 'literal' of a function 'func' inside another chunk 'ck', + * 'func' tells us which variables it closes over from the outer scope. we need + * to convert these into references to variables in ck's scope so that it knows + * which of its variables to save for this particular function. (it also knows + * to heap-allocate those variables as sbRef because their closed_over flag is + * set, but if we have multiple functions closing over different variables we + * need to know which is which, and also these closed variables might be upvalues + * to ck as well. */ + sbBuffer bound; + sbBuffer_initialize(&bound, 256); + BUFFER_ITER(func->closed_vars, sbIrVariable*, var) { + sbIrVariable *outer_ref = bind_upvalue(ck, (*var)->mapping_index); + sbBuffer_append(&bound, &outer_ref, sizeof(sbIrVariable*)); + } + return new_expr(ck, &(sbIrExpr) { .type = IR_E_FUNC, - .func = func, + .func.chunk = func, + .func.bound = bound, }); } @@ -609,12 +723,16 @@ static void compile_ast_stmt(hIrChunk ck, sbAst node, flag implicit_return) { if (node->seq.left->type != AST_NODE_NAME) PANIC("expected name for function in def!"); if (node->seq.right->type != AST_VAL_FUNC) PANIC("expected function body for function in def!"); sbAst func_node = node->seq.right; - if (func_node->seq.left->type != AST_NODE_MULTIVAL) PANIC("expected multival as function params!"); - if (func_node->seq.right->type != AST_NODE_SEQ) PANIC("expected SEQ node as function body!"); + sbAst params = func_node->seq.left; + sbAst body = func_node->seq.right; + if (params != NO_NODE && params->type != AST_NODE_MULTIVAL) { + PANIC("expected multival as function params!"); + } + if (body->type != AST_NODE_SEQ) PANIC("expected SEQ node as function body!"); const char *vname = sbSymbol_name(node->seq.left->symb); V1 = create_var(ck, vname, strlen(vname)); - C1 = compile_ast_function(ck->program, func_node->seq.left, func_node->seq.right); + C1 = compile_ast_function(ck->program, params, body); E1 = expr_func(ck, C1); put_assign(ck, V1, E1); break; @@ -811,14 +929,34 @@ static sbIrExpr *compile_ast_expr(hIrChunk ck, sbAst node) { } } +static void print_var(sbIrVariable *v) { + if (v->closed_over) { + debug("special "); + } + + if (v->is_upvalue) { + debug("upvalue %zu", v->slot_id); + } else { + debug("variable %zu", v->slot_id); + } +} + static void print_expr(sbIrExpr *e) { debug("("); switch(e->type) { case IR_E_VAR: - debug("variable %zu", e->var->slot_id); + print_var(e->var); break; case IR_E_FUNC: - debug("{ chunk %d }", e->func->id); + debug("{ chunk %d ", e->func.chunk->id); + if (e->func.bound.size > 0) { + debug("closing over "); + BUFFER_ITER(e->func.bound, sbIrVariable*, var) { + print_var(*var); + debug(", "); + } + } + debug("}"); break; case IR_E_VALUE: if (e->value.type == IT_NIL) { @@ -856,7 +994,9 @@ static void print_expr(sbIrExpr *e) { static void print_stmt(sbIrStmt *s) { switch (s->type) { case IR_S_ARG: - debug(" bind function argument to variable %zu\n", s->arg.var->slot_id); + debug(" bind function argument to "); + print_var(s->arg.var); + debug("\n"); if (s->arg.last) { debug(" (no function arguments left on the stack now)\n"); } @@ -891,7 +1031,9 @@ static void print_stmt(sbIrStmt *s) { debug("\n"); break; case IR_S_ASSIGN: - debug(" variable %zu = ", s->assign.var->slot_id); + debug(" "); + print_var(s->assign.var); + debug(" = "); print_expr(s->assign.expr); debug("\n"); break; diff --git a/src/compile/ir.h b/src/compile/ir.h index 057948e..f60f251 100644 --- a/src/compile/ir.h +++ b/src/compile/ir.h @@ -60,9 +60,9 @@ typedef struct sbIrLabel { typedef struct sbIrVariable { usize slot_id; flag initialized; - usize first_appearance; - usize last_appearance; - usize assigned_index; + flag closed_over; + flag is_upvalue; + usize mapping_index; } sbIrVariable; typedef struct sbIrJump { @@ -75,9 +75,12 @@ typedef struct sbIrExpr { sbIrExprType type; union { hV value; - struct sbIrChunk *func; sbIrVariable *var; struct { + struct sbIrChunk *chunk; + sbBuffer bound; + } func; + struct { sbAstOp type; struct sbIrExpr *left; struct sbIrExpr *right; @@ -119,10 +122,12 @@ typedef struct sbIrChunk { struct sbIrProgram *program; i32 id; i16 num_args; + i16 num_upvalues; flag variadic; i32 label_count; i32 variable_count; i32 lowest_var_id; + sbBuffer closed_vars; sbBuffer stmts; } sbIrChunk; diff --git a/src/data/closure.c b/src/data/closure.c new file mode 100644 index 0000000..e89942c --- /dev/null +++ b/src/data/closure.c @@ -0,0 +1,89 @@ +#include "data/closure.h" + +#include "data/reference.h" +#include "gc/gcinfo.h" + +#define FLAG_REAL (1ULL << 63) + +#define CLOSURES_PER_BLOCK 256 +#define INLINE_VAR_COUNT 16 + +/* TODO eliminate globals */ +sbPool g_closure_pool = {0}; + +typedef struct sbClosure { + GCINFO info; + usize num_vars; + union { + hRef internal_vars[INLINE_VAR_COUNT]; + hRef *external_vars; + }; +} sbClosure; + +static sbClosure *find_closure_by_handle(hRef handle); + +void sbClosure_sys_init() { + sbPool_initialize(&g_closure_pool, sizeof(sbClosure), CLOSURES_PER_BLOCK); +} + +void sbClosure_sys_deinit() { + //sbPool_deinitialize(&g_closure_pool); +} + +hClosure sbClosure_create(usize num_vars) { + usize index; + sbClosure *c = sbPool_alloc(&g_closure_pool, &index); + c->num_vars = num_vars; + if (num_vars > INLINE_VAR_COUNT) { + c->external_vars = calloc(num_vars, sizeof(hRef)); + } + return index | FLAG_REAL; +} + +/* set the variable in the closure behind the pointer */ +void sbClosure_set_var(hClosure which, usize index, hV *what) { + sbClosure *c = find_closure_by_handle(which); + if (c->num_vars <= INLINE_VAR_COUNT) { + sbRef_set_ref(c->internal_vars[index], what); + } else { + sbRef_set_ref(c->external_vars[index], what); + } +} + +/* set the pointer itself */ +void sbClosure_set_ref(hClosure which, usize index, hV *what) { + if (what->type != IT_REF) { + PANIC("must pass an indirect variable to be the subject of a closure"); + } + sbClosure *c = find_closure_by_handle(which); + if (c->num_vars <= INLINE_VAR_COUNT) { + c->internal_vars[index] = what->ref; + } else { + c->external_vars[index] = what->ref; + } +} + +hV *sbClosure_get_var(hClosure which, usize index) { + sbClosure *c = find_closure_by_handle(which); + if (c->num_vars <= INLINE_VAR_COUNT) { + return sbRef_deref(c->internal_vars[index]); + } else { + return sbRef_deref(c->external_vars[index]); + } +} + +hV sbClosure_get_ref(hClosure which, usize index) { + sbClosure *c = find_closure_by_handle(which); + if (c->num_vars <= INLINE_VAR_COUNT) { + return HVREF(c->internal_vars[index]); + } else { + return HVREF(c->external_vars[index]); + } +} + +/* --- */ + +static sbClosure *find_closure_by_handle(hRef handle) { + if (!(handle & FLAG_REAL)) PANIC("null closure"); + return sbPool_get_entry(&g_closure_pool, handle); +} diff --git a/src/data/closure.h b/src/data/closure.h new file mode 100644 index 0000000..29fe2d5 --- /dev/null +++ b/src/data/closure.h @@ -0,0 +1,15 @@ +#include "common.h" + +void sbClosure_sys_init(); + +void sbClosure_sys_deinit(); + +hClosure sbClosure_create(usize num_vars); + +void sbClosure_set_var(hClosure which, usize index, hV *var); + +void sbClosure_set_ref(hClosure which, usize index, hV *what); + +hV *sbClosure_get_var(hClosure which, usize index); + +hV sbClosure_get_ref(hClosure which, usize index); diff --git a/src/data/data.c b/src/data/data.c index 296fb36..9d8d5a9 100644 --- a/src/data/data.c +++ b/src/data/data.c @@ -4,10 +4,14 @@ #include "data/hashtable.h" #include "data/symbol.h" #include "data/list.h" +#include "data/reference.h" +#include "data/closure.h" void data_sys_init() { sbString_sys_init(); sbHash_sys_init(); + sbRef_sys_init(); + sbClosure_sys_init(); sbSymbol_sys_init(); sbList_sys_init(); } @@ -15,6 +19,8 @@ void data_sys_init() { void data_sys_deinit() { sbList_sys_deinit(); sbSymbol_sys_deinit(); + sbRef_sys_deinit(); + sbClosure_sys_init(); sbHash_sys_deinit(); sbString_sys_deinit(); } diff --git a/src/data/hashtable.c b/src/data/hashtable.c index 0fe91fe..b18fa8b 100644 --- a/src/data/hashtable.c +++ b/src/data/hashtable.c @@ -56,15 +56,17 @@ sbHashValue sbHash_hash_bytes(const char *bytes, usize length) { return result; } +flag is_flatly_hashable(hV *obj) { + return obj->type == IT_NIL + || obj->type == IT_BOOLEAN + || obj->type == IT_INTEGER /* todo: wrong for bigints */ + || obj->type == IT_REF + || obj->type == IT_SYMBOL; +} + sbHashValue sbHash_hash_obj(hV *obj) { - if (obj->type == IT_NIL) { - char zero = 0; - return sbHash_hash_bytes(&zero, 1); - } else if (obj->type == IT_SYMBOL) { - return sbHash_hash_bytes((char*)&obj->symbol, sizeof(obj->symbol)); - } else if (obj->type == IT_INTEGER) { - /* TODO bigint should be different i think */ - return sbHash_hash_bytes((char*)&obj->integer, sizeof(obj->integer)); + if (is_flatly_hashable(obj)) { + return sbHash_hash_bytes((char*)obj, sizeof(*obj)); } else if (obj->type == IT_STRING) { char scratch[8]; usize length; diff --git a/src/data/reference.c b/src/data/reference.c new file mode 100644 index 0000000..bab0021 --- /dev/null +++ b/src/data/reference.c @@ -0,0 +1,49 @@ +#include "data/reference.h" + +#include "gc/gcinfo.h" + +#define REFERENCES_PER_BLOCK 1024 + +/* TODO eliminate globals */ +sbPool g_reference_pool = {0}; + +typedef struct sbRef { + GCINFO info; + hV pointed_to; +} sbRef; + +static sbRef *find_ref_by_handle(hRef handle); + +void sbRef_sys_init() { + sbPool_initialize(&g_reference_pool, sizeof(sbRef), REFERENCES_PER_BLOCK); +} + +void sbRef_sys_deinit() { + //sbPool_deinitialize(&g_reference_pool); +} + +hRef sbRef_create(hV *var) { + usize index; + sbRef *r = sbPool_alloc(&g_reference_pool, &index); + sbV_retain(var); + r->pointed_to = *var; + return index; +} + +void sbRef_set_ref(hRef ref, hV *var) { + sbRef *value = find_ref_by_handle(ref); + sbV_release(&value->pointed_to); + sbV_retain(var); + value->pointed_to = *var; +} + +hV *sbRef_deref(hRef ref) { + sbRef *value = find_ref_by_handle(ref); + return &value->pointed_to; +} + +/* --- */ + +static sbRef *find_ref_by_handle(hRef handle) { + return sbPool_get_entry(&g_reference_pool, handle); +} diff --git a/src/data/reference.h b/src/data/reference.h new file mode 100644 index 0000000..67c13e0 --- /dev/null +++ b/src/data/reference.h @@ -0,0 +1,11 @@ +#include "common.h" + +void sbRef_sys_init(); + +void sbRef_sys_deinit(); + +hRef sbRef_create(hV *var); + +void sbRef_set_ref(hRef ref, hV *var); + +hV *sbRef_deref(hRef ref); diff --git a/src/data/value.h b/src/data/value.h index 9c615e0..61c1956 100644 --- a/src/data/value.h +++ b/src/data/value.h @@ -7,16 +7,19 @@ #define HVSTR(s) ((hV) { .type = IT_STRING, .string = s }) #define HVSYM(s) ((hV) { .type = IT_SYMBOL, .symbol = s }) #define HVBOOL(b) ((hV) { .type = IT_BOOLEAN, .boolean = b }) -#define HVFUNC(i) ((hV) { .type = IT_FUNCTION, .data = i }) #define HVLIST(l) ((hV) { .type = IT_LIST, .list = l }) +#define HVREF(r) ((hV) { .type = IT_REF, .ref = r }) #define HVNIL ((hV) { .type = IT_NIL }) #define HVNOTHING ((hV) {0}) +#define HVFUNC(i, c) ((hV) { .type = i, .closure = c }) typedef u64 hHash; typedef u64 hString; typedef u64 hSymbol; typedef i64 hInteger; typedef u64 hList; +typedef u64 hRef; +typedef u64 hClosure; enum intrinsic_type { IT_NOTHING, // sentinel for "no value here" @@ -35,13 +38,15 @@ enum intrinsic_type { }; typedef struct hV { - u64 type; + i64 type; union { hString string; hSymbol symbol; hHash hash; hList list; hInteger integer; + hClosure closure; + hRef ref; u64 boolean; double float_val; u64 data; diff --git a/src/global.h b/src/global.h index 6976391..3963451 100644 --- a/src/global.h +++ b/src/global.h @@ -3,9 +3,11 @@ #ifdef DEBUG #define PANIC(...) do { fprintf(stderr, "PANIC: " __VA_ARGS__); fprintf(stderr, "\n at " __FILE__ ":%d\n", __LINE__); abort(); } while (0) +#define CHECK(...) do { fprintf(stderr, "PANIC: " __VA_ARGS__); fprintf(stderr, "\n at " __FILE__ ":%d\n", __LINE__); abort(); } while (0) #define debug(...) printf(__VA_ARGS__) #else -#define PANIC(...) do { fprintf(stderr, "PANIC: " __VA_ARGS__); fprintf(stderr, "\n"); abort(); } while (0) +#define PANIC(...) do { fprintf(stderr, "BUGCHECK: " __VA_ARGS__); fprintf(stderr, "\n"); abort(); } while (0) +#define CHECK(...) 0 #define debug(...) 0 #endif diff --git a/src/mem/buffer.h b/src/mem/buffer.h index 3f93812..cbab2ac 100644 --- a/src/mem/buffer.h +++ b/src/mem/buffer.h @@ -7,6 +7,12 @@ * You can use sbBuffer to read in data you don't know the size of, then request a chunk * of that size from sbArena and copy it to there for long-term storage. */ +#define BUFFER_ITER(buf, type, var) \ + for (type *var = (type*)((buf).data); (var) < ((type*)(buf).data + (buf).size / sizeof(type)); var ++) +#define BUFFER_ITER_FROM(buf, type, var, from) \ + for (type *var = (type*)((buf).data + (from * sizeof(type))); (var) < ((type*)(buf).data + (buf).size / sizeof(type)); var ++) +#define BUFFER_INDEX(buf, type, index) (((type*)((buf).data))[index]) + typedef struct sbBuffer { usize size; usize capacity; diff --git a/src/parse/parser.c b/src/parse/parser.c index 0690d1d..b34fe1d 100644 --- a/src/parse/parser.c +++ b/src/parse/parser.c @@ -777,9 +777,11 @@ static sbAst parse_stmt(hParser pr) { /* def a b, c { ... } */ next_token(pr); sbAst name = parse_name(pr); - if (!expect(pr, T_LPAREN)) return syntax_error(pr); - sbAst params = parse_comma_exprs(pr, NULL); - if (!expect(pr, T_RPAREN)) return syntax_error(pr); + sbAst params = NO_NODE; + if (expect(pr, T_LPAREN)) { + params = parse_comma_exprs(pr, NULL); + if (!expect(pr, T_RPAREN)) return syntax_error(pr); + } sbAst body = parse_block(pr); sbAst func_node = seq_node(pr, AST_VAL_FUNC, params, body); return seq_node(pr, AST_NODE_DEF, name, func_node); diff --git a/src/vm/bytecode.h b/src/vm/bytecode.h index 769a364..6eb6cb5 100644 --- a/src/vm/bytecode.h +++ b/src/vm/bytecode.h @@ -10,13 +10,17 @@ typedef enum sbOpcode { BC_LD_CTX, // look up key in context object and push result BC_LD_VAR, // push value onto stack from variable BC_LD_UPVAL, // push value onto stack from closure + BC_LD_UPREF, // push pointer to closure value onto stack (to close over again) BC_LD_BLK, // push reference to function onto stack + BC_LD_IND, // push value behind pointer variable onto stack BC_LD_NIL, // push nil onto stack BC_LD_TRUE, // push true onto stack BC_LD_FALSE, // push false onto stack BC_ST_VAR, // pop value from stack into variable BC_ST_UPVAL, // pop value from stack into closure + BC_ST_IND, // pop and store as reference (closure/pointer construction) BC_ST_ARG, // decrement TOS and store NOS in variable + BC_ST_ARG_IND, // decrement TOS and store NOS in variable indirectly BC_POP, // pop value from stack BC_NPOP, // pop N values from stack given by top number BC_CALL, // push return address and jump to new block @@ -45,6 +49,7 @@ typedef enum sbOpcode { BC_OP_INDEX, // index [] BC_OP_SCOPE, // index :: BC_ALLOC_VARS, // create space in rstack for local variables + BC_CLOSURE, // create closure from top elements of stack BC_LIST_GATHER, // create list from count + list of values on stack BC_HASH_GATHER, // create hash from count + list of pairs of keys/values on stack BC_LONG_NUM = 0xFC, // next two bytes are a 16-bit number diff --git a/src/vm/exec.c b/src/vm/exec.c index 04d2a63..fd2f688 100644 --- a/src/vm/exec.c +++ b/src/vm/exec.c @@ -1,8 +1,10 @@ #include "vm/exec.h" #include "vm/operations.h" +#include "data/reference.h" +#include "data/closure.h" -void call_block(hVm vm, usize block_id); +void call_block(hVm vm, usize block_id, hClosure closure); void execute_instruction(hVm vm); void sbVm_initialize(hVm vm, usize stacksize, usize rstacksize, flag debugmode) { @@ -31,7 +33,7 @@ sbVmStatus sbVm_execute(hVm vm, sbVmProgram *pm) { /* Let's start at the very beginning. * A very good place to start. */ - call_block(vm, 0); + call_block(vm, 0, 0); while (vm->running) { execute_instruction(vm); @@ -49,7 +51,7 @@ sbVmStatus sbVm_execute(hVm vm, sbVmProgram *pm) { /* --- */ -void call_block(hVm vm, usize block_id) { +void call_block(hVm vm, usize block_id, hClosure closure) { sbVmBlock *blk = &vm->program->blocks[block_id]; sbVmStackFrame frame = { @@ -57,6 +59,7 @@ void call_block(hVm vm, usize block_id) { .last_fp = vm->fp, .last_rp = vm->rp, .block = blk, + .closure = closure, }; *(sbVmStackFrame*)vm->rp = frame; vm->fp = (sbVmStackFrame*)vm->rp; @@ -198,10 +201,27 @@ void execute_instruction(hVm vm) { break; case BC_LD_UPVAL: /* Hey, was there upval in there? */ - PANIC("todo"); + param = get_param(vm); + v = sbClosure_get_var(vm->fp->closure, param); + push_stack(vm, v); + break; + case BC_LD_UPREF: + param = get_param(vm); + res = sbClosure_get_ref(vm->fp->closure, param); + push_stack(vm, &res); + break; case BC_LD_BLK: param = get_param(vm); - push_stack(vm, &HVFUNC(param)); + push_stack(vm, &HVFUNC(param, 0)); + break; + case BC_LD_IND: + param = get_param(vm); + v = &vm->fp->locals[param]; + if (v->type != IT_REF) { + CHECK("indirect variables should be of type reference! (%lld)", v->type); + } + w = sbRef_deref(v->ref); + push_stack(vm, w); break; case BC_LD_NIL: push_stack(vm, &HVNIL); @@ -213,13 +233,29 @@ void execute_instruction(hVm vm) { pop_stack(vm); break; case BC_ST_UPVAL: - PANIC("todo"); + param = get_param(vm); + sbClosure_set_var(vm->fp->closure, param, pop_stack(vm)); + break; + case BC_ST_IND: + param = get_param(vm); + v = &vm->fp->locals[param]; + w = peek_stack(vm, 0); + if (v->type == IT_NOTHING) { + hRef new_ref = sbRef_create(w); + store_local(vm, param, &HVREF(new_ref)); + } else if (v->type == IT_REF) { + sbRef_set_ref(v->ref, w); + } else { + CHECK("indirect variables should be of type reference! (%lld)", v->type); + } + pop_stack(vm); + break; case BC_ST_ARG: param = get_param(vm); v = pop_stack(vm); /* argument count */ if (v->type != IT_INTEGER) { /* internal error! this should be generated correctly */ - PANIC("calling convention violation: number of args should be an integer"); + CHECK("calling convention violation: number of args should be an integer"); } w = pop_stack(vm); /* argument value */ store_local(vm, param, w); @@ -230,6 +266,31 @@ void execute_instruction(hVm vm) { push_stack(vm, v); } break; + case BC_ST_ARG_IND: + param = get_param(vm); + x = pop_stack(vm); /* argument count */ + if (x->type != IT_INTEGER) { + /* internal error! this should be generated correctly */ + CHECK("calling convention violation: number of args should be an integer"); + } + + v = &vm->fp->locals[param]; + w = peek_stack(vm, 0); /* argument value */ + if (v->type == IT_NOTHING) { + hRef new_ref = sbRef_create(w); + store_local(vm, param, &HVREF(new_ref)); + } else if (v->type == IT_REF) { + sbRef_set_ref(v->ref, w); + } else { + CHECK("indirect variables should be of type reference! (%lld)", v->type); + } + pop_stack(vm); + x->integer --; + if (x->integer > 0) { + /* if last integer, don't put the 0 count back on the stack */ + push_stack(vm, x); + } + break; case BC_POP: v = pop_stack(vm); break; @@ -239,25 +300,28 @@ void execute_instruction(hVm vm) { break; case BC_CALL: v = pop_stack(vm); - if (v->type != IT_FUNCTION) { + if (v->type <= 0) { /* We need to figure out exception support or some such. * User error should not panic. */ PANIC("attempt to call a non-function value"); } - call_block(vm, v->data); + call_block(vm, v->type, v->closure); break; case BC_NUMARG: param = get_param(vm); v = pop_stack(vm); if (v->type != IT_INTEGER) { /* internal error! this should be generated correctly */ - PANIC("calling convention violation: number of args should be an integer"); + CHECK("calling convention violation: number of args should be an integer"); } if (v->integer != param) { /* This should be an exception. */ PANIC("wrong number of arguments passed to function."); } - push_stack(vm, v); + if (v->integer > 0) { + /* when 0 arguments, leave this off */ + push_stack(vm, v); + } break; case BC_JMP: param = get_param(vm); @@ -383,11 +447,32 @@ void execute_instruction(hVm vm) { vm->rp += (param + 1) * sizeof(hV); vm->fp->num_locals += param; break; + case BC_CLOSURE: + param = get_param(vm); + hClosure c = sbClosure_create(param); + v = pop_stack(vm); /* function to close with */ + if (v->type <= 0) { + CHECK("internal violation: a function is required to create a closure!"); + } + while (param > 0) { + param --; + /* set_ref: the things on the stack should be the reference variables that + * have previously been being manipulated using the IND instructions */ + w = peek_stack(vm, 0); + if (w->type != IT_REF) { + CHECK("internal violation: closure should receive a set of reference variables (got %lld)", w->type); + } + sbClosure_set_ref(c, param, w); + pop_stack(vm); + } + v->closure = c; + push_stack(vm, v); + break; case BC_LIST_GATHER: v = pop_stack(vm); if (v->type != IT_INTEGER) { /* internal error! this should be generated correctly */ - PANIC("internal violation: LIST_GATHER should receive an integer on top of stack"); + CHECK("internal violation: LIST_GATHER should receive an integer on top of stack"); } param = v->integer; res = sbV_empty_list(param); @@ -402,7 +487,7 @@ void execute_instruction(hVm vm) { v = pop_stack(vm); if (v->type != IT_INTEGER) { /* internal error! this should be generated correctly */ - PANIC("internal violation: HASH_GATHER should receive an integer on top of stack"); + CHECK("internal violation: HASH_GATHER should receive an integer on top of stack"); } param = v->integer; res = sbV_empty_hash(param * 3 / 2); diff --git a/src/vm/exec.h b/src/vm/exec.h index 1c851d2..0b8b219 100644 --- a/src/vm/exec.h +++ b/src/vm/exec.h @@ -47,6 +47,7 @@ typedef struct sbVmStackFrame { struct sbVmStackFrame *last_fp; u8 *last_rp; const sbVmBlock *block; + hClosure closure; usize num_locals; hV locals[]; } sbVmStackFrame; -- 1.8.3.1