diff options
| -rw-r--r-- | core/module-jit.c | 4 | ||||
| -rw-r--r-- | core/module-run.h | 2 | ||||
| -rw-r--r-- | core/module.c | 507 | ||||
| -rw-r--r-- | core/module.h | 50 | ||||
| -rw-r--r-- | core/test-module.c | 188 | ||||
| -rw-r--r-- | docs/design/008-module-format.md | 35 |
6 files changed, 740 insertions, 46 deletions
diff --git a/core/module-jit.c b/core/module-jit.c index 0254430..ae0f24c 100644 --- a/core/module-jit.c +++ b/core/module-jit.c @@ -5750,7 +5750,7 @@ static bool in_code(const PureModule *m, const PureOp *op) { } } -/* Whether a block is worth code: it has a loop, and its loops' blocks have +/* Whether a block is worth code: it has a loop and no call, and its loops' blocks have * code for every instruction. Each step a loop calls gives back what the * code keeps in registers (read again after it), and costs more than the * executor's own dispatch: a loop of steps (TPC-C's lines, 123) runs as @@ -5763,6 +5763,8 @@ static bool worth(const PureModule *m, PureBlock block) { int input = tier_input(m, block); for (uint32_t pc = block.start; pc < block.start + block.length; pc = after(&m->code[pc], pc)) { const PureOp *op = &m->code[pc]; + if (op->op == PURE_OP_CALL) return false; /* the executor's frames (module.c's run_calls) */ + if ((op->op == PURE_OP_LOCAL_LOAD || op->op == PURE_OP_LOCAL_STORE) && (op->arg >> 8 & 0xFF) == 4) return false; /* a list */ if (op->op == PURE_OP_EACH || op->op == PURE_OP_LOOP) { loops = true; uint32_t ends = pc + 1 + (op->arg >> 16); diff --git a/core/module-run.h b/core/module-run.h index dc4a023..4ae94a4 100644 --- a/core/module-run.h +++ b/core/module-run.h @@ -145,6 +145,8 @@ static inline uint32_t after(const PureOp *op, uint32_t pc) { * loop ended). STEP_BATCH: step leaves a LOOP planned PLAN_BATCH to its * caller (module.c). */ enum { STEP_SKIP = 4, STEP_DONE = 5, STEP_BATCH = 6 }; +/* STEP_CALL: step leaves a CALL to its caller (module.c's run_calls), and STEP_BACK a RETURN (027's 2c). */ +enum { STEP_CALL = 7, STEP_BACK = 8 }; int pure_run_step(Frame *, uint32_t pc); int pure_run_each(Frame *, uint32_t pc); int pure_run_loop(Frame *, uint32_t pc); diff --git a/core/module.c b/core/module.c index db0703c..fec9dd9 100644 --- a/core/module.c +++ b/core/module.c @@ -9,6 +9,7 @@ #include <stdlib.h> #include <string.h> +enum { FUNCTION_BYTES = 12, SIGNATURE_BYTES = 4 }; enum { STATE_BYTES = 16, COLLECTION_BYTES = 12, INPUT_BYTES = 16, FIELD_BYTES = 8, CONSTANT_BYTES = 8, RECORD_BYTES = 8, RECORD_FIELD_BYTES = 16, VIEW_BYTES = 16, HANDLER_BYTES = 12, OP_BYTES = 16 }; @@ -23,8 +24,9 @@ enum { FROM_PAYLOAD, FROM_DOCUMENT, FROM_COPY, FROM_CONSTANT, FROM_TEXT, FROM_AR /* IN_ARGUMENTS: fields read where nothing is done with them (a view's arguments, a message's fields in a fold). */ /* IN_LOCALS: a handler's locals, read in its walks and the folds in them. */ /* IN_COMPUTE: what a view's body may do too (018): loops, locals, and changes to an event's lists alone. */ +/* IN_FUNCTION: a function's code (027's 2c), a handler's but for a message. */ enum { IN_VIEW = 1, IN_HANDLER = 2, IN_MESSAGE = 4, IN_KEYED = 8, IN_TEXT = 16, IN_ROW = 32, IN_OUTER = 64, IN_ARGUMENTS = 128, - IN_LOCALS = 256, IN_COMPUTE = 512 }; + IN_LOCALS = 256, IN_COMPUTE = 512, IN_FUNCTION = 1024 }; enum { READ = IN_VIEW | IN_HANDLER }; /* What an argument names: nothing (it is 0), a state of one type (A_STATE + * the type), a list and one of its record's fields, a message field, the @@ -34,18 +36,20 @@ enum { READ = IN_VIEW | IN_HANDLER }; * (A_TYPE: 0 a number, 1 a bool, 2 an i64), how I64_BITS computes (A_BITS), * what a position is (A_POSITION: 0 a number, 1 an i64), what CONCAT joins * (A_JOINED: 0 texts, 1 bytes), how NUM_TEXT writes (A_FORMAT) or the value - * held by name (A_HELD). */ + * held by name (A_HELD), or a function (A_FUNCTION: CALL's, and RETURN's own). */ enum { A_NONE, A_STATE, A_ITEM = A_STATE + PURE_STATE_I64 + 1, A_FIELD, A_COLLECTION, A_CONSTANT, A_UNIT, A_ROW, A_TARGET, A_DEPTH, A_FOLD, A_RELATION, A_KEYED, A_OUTPUT, A_OUTER, A_EACH, A_LOCAL, A_VALUE, A_TYPE, - A_LOOP, A_BITS, A_POSITION, A_JOINED, A_FORMAT, A_HELD }; + A_LOOP, A_BITS, A_POSITION, A_JOINED, A_FORMAT, A_HELD, A_FUNCTION }; /* A fold's block is verified as a column that leaves one bool (count, first) * or a value and whether to include it (a bool): a number (FOLD_TWO) or an * i64 (FOLD_I64). A table's filter is verified as a column that leaves a * bool: these stand for a view type. A walk's block (EACH) is verified as * its handler's code that may read the item it runs for (WALK). In a view's * body a loop's block leaves nothing either (STEPS), and a walk's reads its - * item (STEPS_WALK); neither changes a state. */ -enum { FOLD_ONE = 100, FOLD_TWO, FOLD_I64, FILTER, WALK, STEPS, STEPS_WALK }; + * item (STEPS_WALK); neither changes a state. A function's block begins with + * its parameters on the stack and ends at RETURN alone (FUNCTION); the loops' + * blocks in it are a handler's code. */ +enum { FOLD_ONE = 100, FOLD_TWO, FOLD_I64, FILTER, WALK, STEPS, STEPS_WALK, FUNCTION }; /* The text or list an opcode works on: its cursor and index operands belong * to it, and so does a cursor or index it pushes. O_ANY: no rule. O_OPERAND: * it pushes a position in its operand's text or list. O_ARG: the argument. @@ -149,6 +153,11 @@ static const struct { unsigned char pops, in[3], out; unsigned short where; unsi /* APPEND_IN also takes as many values as the record of the list in the field has fields. */ [PURE_OP_APPEND_IN] = {1, {T_INDEX}, 0, IN_HANDLER | IN_COMPUTE, A_ITEM, O_LIST}, [PURE_OP_NUM_PARSE] = {1, {T_TEXT}, T_NUM, READ, A_NONE, O_ANY}, + /* CALL takes its function's parameters and gives its results; RETURN takes its function's results (verify_code). */ + [PURE_OP_CALL] = {0, {0}, 0, IN_HANDLER, A_FUNCTION, O_ANY}, + [PURE_OP_RETURN] = {0, {0}, 0, IN_FUNCTION, A_FUNCTION, O_ANY}, + [PURE_OP_CHAR_AT] = {2, {T_TEXT, T_I64}, T_I64, READ, A_NONE, O_ANY}, + [PURE_OP_CHAR] = {1, {T_I64}, T_TEXT, READ, A_NONE, O_ANY}, }; #undef NUMS #undef COMPARE @@ -362,17 +371,26 @@ static bool bound_list(const PureModule *m, uint32_t list) { return event_list_state(m, list) && m->state_flags[list] & PURE_LIST_BOUND >> 8; } -/* The stack type of a record field (the module's numbering). */ -static unsigned char record_type(const PureModule *m, uint32_t field) { +/* The stack type of a record field's type (PureRecordType), and of a record field (the module's numbering). */ +static unsigned char record_type_of(uint8_t type) { static const unsigned char types[] = {[PURE_RECORD_NUMBER] = T_NUM, [PURE_RECORD_TEXT] = T_TEXT, [PURE_RECORD_BOOL] = T_BOOL, [PURE_RECORD_I64] = T_I64, [PURE_RECORD_LIST] = T_LIST}; - return types[m->record_field_type[field]]; + return types[type]; +} +static unsigned char record_type(const PureModule *m, uint32_t field) { return record_type_of(m->record_field_type[field]); } + +/* The stack type of a function's signature item (a record field's type, or PURE_SIGNATURE_BYTES). */ +static unsigned char signature_stack_type(const PureModule *m, uint32_t item) { + return m->signature_type[item] == PURE_SIGNATURE_BYTES ? T_BYTES : record_type_of(m->signature_type[item]); } /* The record of the list value an instruction takes as its operand k (bottom 0). */ static unsigned list_wanted(const PureModule *m, const PureOp *op, unsigned k) { uint32_t arg = op->arg; switch (op->op) { + case PURE_OP_CALL: return m->signature_record[m->function[arg].first + k]; + case PURE_OP_LOCAL_STORE: return arg >> 16; + case PURE_OP_RETURN: return m->signature_record[m->function[arg].first + m->function[arg].params + k]; case PURE_OP_LIST_BIND: return m->state_ref[arg]; case PURE_OP_LIST_APPEND: return nested_record(m, m->record[m->state_ref[arg]].first + k); case PURE_OP_LIST_INSERT: return nested_record(m, m->record[m->state_ref[arg]].first + k - 1); /* the index first */ @@ -399,10 +417,10 @@ static bool text_field(const PureModule *m, uint32_t list, uint32_t field) { return m->record_field_type[m->record[m->state_ref[list]].first + field] == PURE_RECORD_TEXT; } -/* What a local holds (its argument's bits 8-15): a number, an index, a bool or an i64. */ +/* What a local holds (its argument's bits 8-15): a number, an index, a bool, an i64 or a list (027's 2c). */ static unsigned char local_type(uint32_t arg) { - static const unsigned char types[] = {T_NUM, T_INDEX, T_BOOL, T_I64}; - return types[arg >> 8 & 3]; + static const unsigned char types[] = {T_NUM, T_INDEX, T_BOOL, T_I64, T_LIST}; + return (arg >> 8 & 0xFF) <= 4 ? types[arg >> 8 & 0xFF] : T_NUM; } PURE_COLD static bool names_arg(const PureModule *m, unsigned kind, uint32_t arg, const PureInputShape *shape, int row, @@ -426,15 +444,17 @@ PURE_COLD static bool names_arg(const PureModule *m, unsigned kind, uint32_t arg return (kind == A_FOLD ? how <= PURE_FOLD_DISTINCT && (valued || !(flags & PURE_FOLD_INTEGER)) : flags <= PURE_EACH_SLICED) && state_of(m, list, PURE_STATE_LIST) && arg >> 16 && (!sliced || key == T_NUM || key == T_I64); } - case A_LOCAL: /* a slot, and a number, an index of a list, a bool or an i64 */ - return (arg & 0xFF) < PURE_MODULE_LOCALS && (arg >> 8 & 0xFF) <= 3 && - ((arg >> 8 & 0xFF) == 1 ? state_of(m, arg >> 16, PURE_STATE_LIST) : !(arg >> 16)); + case A_LOCAL: /* a slot, and a number, an index of a list, a bool, an i64 or a list of a record */ + return (arg & 0xFF) < PURE_MODULE_LOCALS && (arg >> 8 & 0xFF) <= 4 && + ((arg >> 8 & 0xFF) == 1 ? state_of(m, arg >> 16, PURE_STATE_LIST) : + (arg >> 8 & 0xFF) == 4 ? (arg >> 16) < m->records : !(arg >> 16)); case A_VALUE: return state_of(m, arg, PURE_STATE_NUM) || state_of(m, arg, PURE_STATE_BOOL) || state_of(m, arg, PURE_STATE_I64); case A_LOOP: return (arg & 0xFF) < PURE_MODULE_LOCALS && !(arg & 0xFE00); /* a slot, and whether i64s */ case A_TYPE: return arg <= 2; case A_BITS: return arg <= PURE_BITS_RIGHT; case A_POSITION: case A_JOINED: return arg <= 1; case A_HELD: return (arg & ~(uint32_t)PURE_HELD_APPEND) < PURE_MODULE_HELD; + case A_FUNCTION: return arg < m->functions; case A_FORMAT: { /* a type; a width, zeros, a form fitting it and digits for FIXED alone */ uint32_t type = arg & 3, form = arg >> PURE_FORMAT_FORM & 7, digits = arg >> PURE_FORMAT_DIGITS & 31; return type <= 2 && !(arg & 0xFC) && !(arg >> 25) && form <= PURE_FORMAT_FIXED && (type != 1 || !form) && @@ -468,17 +488,18 @@ static bool same_stack(const Join *join, int height, const unsigned char *types, * into it. Returns why the block is refused, with at moved to the * instruction when one is at fault, or NULL. */ PURE_COLD static const char *verify_block(const PureModule *, PureBlock, int view, int row, int outer, uint32_t event, - bool locals, unsigned nest, uint32_t walked, uint32_t *at); + bool locals, unsigned nest, uint32_t walked, int fn, uint32_t *at); /* target marks, per instruction of the block, a branch into it with an empty stack. */ /* outer: the row of the column a fold's block runs in (-1: none). */ /* locals: the block is a handler's, or runs in one (a walk, a fold): it reads the handler's locals. */ /* nest: the loops (LOOP, EACH) the block runs in; walked: a bit for each list the walks among them walk. */ +/* fn: the function whose code the block is (its own block, FUNCTION, or a loop's in it), or -1. */ PURE_COLD static const char *verify_code(const PureModule *m, PureBlock block, int view, int row, int outer, - uint32_t event, bool locals, unsigned nest, uint32_t walked, uint32_t *at, + uint32_t event, bool locals, unsigned nest, uint32_t walked, int fn, uint32_t *at, unsigned char *target) { #define REFUSE(why) do { *at = pc; return why; } while (0) - bool steps = view == STEPS || view == STEPS_WALK, handler = view < 0 || view == WALK || steps; + bool steps = view == STEPS || view == STEPS_WALK, handler = view < 0 || view == WALK || steps || view == FUNCTION; bool folding = view == FOLD_ONE || view == FOLD_TWO || view == FOLD_I64; /* A view outside a table computes (locals: its code reads them): a body, and the loops in it. */ bool body = steps || (!handler && !folding && view != FILTER && row < 0 && locals); @@ -494,11 +515,17 @@ PURE_COLD static const char *verify_code(const PureModule *m, PureBlock block, i if (shape && (!handler || steps) && (shape->kind == PURE_KIND_MESSAGE || shape->kind == PURE_KIND_ARGUMENTS)) where |= IN_ARGUMENTS; if (locals) where |= IN_LOCALS; + if (fn >= 0) where |= IN_FUNCTION; unsigned char types[PURE_MODULE_STACK], owners[PURE_MODULE_STACK]; Join joins[PURE_MODULE_JOINS]; unsigned open = 0; int height = 0; bool reachable = true; + if (view == FUNCTION) /* its parameters */ + for (const PureFunction *f = &m->function[fn]; height < f->params; ++height) { + types[height] = signature_stack_type(m, f->first + (uint32_t)height); + owners[height] = (unsigned char)(types[height] == T_LIST ? m->signature_record[f->first + height] : 0); + } for (uint32_t i = 0; i <= block.length; ++i) { uint32_t pc = block.start + i; /* Branches here brought an empty stack (target) or the stack of a join. */ @@ -524,6 +551,8 @@ PURE_COLD static const char *verify_code(const PureModule *m, PureBlock block, i if (op->op >= PURE_OP_COUNT) REFUSE("unknown opcode"); unsigned allowed = signature[op->op].where, kind = signature[op->op].arg, of = signature[op->op].of; if (!(allowed & where)) { + if (allowed & IN_FUNCTION) REFUSE("return outside a function"); + if (op->op == PURE_OP_CALL) REFUSE("call outside a handler or a function"); if (allowed & IN_ROW) REFUSE("row outside a column"); if (allowed & IN_OUTER) REFUSE("outer row outside a fold in a column"); if (allowed & IN_LOCALS) REFUSE("local outside a handler"); @@ -595,13 +624,14 @@ PURE_COLD static const char *verify_code(const PureModule *m, PureBlock block, i uint32_t list = arg >> 8 & 0xFF; /* A fold in a walk reads the walk's item as a fold in a column reads its row; a loop's block is its block's code. */ const char *why = kind == A_EACH ? verify_block(m, (PureBlock){pc + 1, skip}, body ? STEPS_WALK : WALK, (int)list, -1, - event, locals, nest + 1, walked | UINT32_C(1) << (list & 31), &inner) - : kind == A_LOOP ? verify_block(m, (PureBlock){pc + 1, skip}, body && !steps ? STEPS : view, row, - outer, event, locals, nest + 1, walked, &inner) + event, locals, nest + 1, walked | UINT32_C(1) << (list & 31), fn, &inner) + : kind == A_LOOP ? verify_block(m, (PureBlock){pc + 1, skip}, body && !steps ? STEPS : + view == FUNCTION ? -1 : view, row, outer, event, locals, nest + 1, + walked, fn, &inner) : verify_block(m, (PureBlock){pc + 1, skip}, how == PURE_FOLD_COUNT || how == PURE_FOLD_FIRST ? FOLD_ONE : arg & PURE_FOLD_INTEGER ? FOLD_I64 : FOLD_TWO, - (int)list, row, event, locals, nest, walked, &inner); + (int)list, row, event, locals, nest, walked, -1, &inner); if (why) { *at = inner; return why; } for (uint32_t k = i + 1; k <= i + skip; ++k) { const char *into = kind == A_FOLD ? "branch into a fold" : kind == A_EACH ? "branch into an each" : @@ -654,7 +684,17 @@ PURE_COLD static const char *verify_code(const PureModule *m, PureBlock block, i } else if (kind == A_LOOP) { need[0] = need[1] = arg & PURE_LOOP_INTEGER ? T_I64 : T_NUM; /* low and high */ pops = 2; + } else if (kind == A_FUNCTION) { /* a function's parameters, or the results its RETURN gives */ + const PureFunction *f = &m->function[arg]; + if (op->op == PURE_OP_RETURN && (int)arg != fn) REFUSE("return from another function"); + uint32_t first = f->first + (op->op == PURE_OP_RETURN ? f->params : 0); + pops = op->op == PURE_OP_RETURN ? f->results : f->params; + for (unsigned k = 0; k < pops; ++k) need[k] = signature_stack_type(m, first + k); } + /* A loop's block begins at the bottom of its run's stack: its operands are all the stack holds. */ + if ((kind == A_LOOP || kind == A_EACH) && height != (int)pops) REFUSE("loop above values"); + /* What a walk keeps to, a call keeps to as well: a call changes no list a walk around it walks. */ + if (op->op == PURE_OP_CALL && m->function[arg].changes & walked) REFUSE("call that changes a list walked"); if (height < (int)pops) REFUSE("stack underflow"); height -= (int)pops; for (unsigned k = 0; k < pops; ++k) @@ -686,11 +726,18 @@ PURE_COLD static const char *verify_code(const PureModule *m, PureBlock block, i if (integer) out = T_I64; if ((op->op == PURE_OP_CONCAT && arg) || (op->op == PURE_OP_BYTES_LOAD && (arg & 0xFF) < PURE_HELD_TEXT)) out = T_BYTES; else if (op->op == PURE_OP_BYTES_LOAD) out = T_TEXT; + if (op->op == PURE_OP_CALL) /* its results */ + for (uint32_t k = 0, first = m->function[arg].first + m->function[arg].params; k < m->function[arg].results; ++k) { + if (height == PURE_MODULE_STACK) REFUSE("stack overflow"); + types[height] = signature_stack_type(m, first + k); + owners[height] = (unsigned char)(types[height] == T_LIST ? m->signature_record[first + k] : 0); + ++height; + } if (out) { if (height == PURE_MODULE_STACK) REFUSE("stack overflow"); owners[height] = (unsigned char)(out != T_CURSOR && out != T_INDEX ? 0 : of == O_OPERAND ? owners[height] : owner); if (out == T_LIST) /* the record of its items */ - owners[height] = (unsigned char)(op->op == PURE_OP_LIST_VALUE ? m->state_ref[arg] : + owners[height] = (unsigned char)(op->op == PURE_OP_LIST_VALUE ? m->state_ref[arg] : op->op == PURE_OP_LOCAL_LOAD ? arg >> 16 : nested_record(m, m->record[m->state_ref[list_of(arg)]].first + item_field(arg))); types[height++] = out; } @@ -716,9 +763,12 @@ PURE_COLD static const char *verify_code(const PureModule *m, PureBlock block, i target[block.length] = 1; reachable = false; } + if (op->op == PURE_OP_RETURN) reachable = false; /* the rest of its stack let go */ i += skip; } - if (!reachable) return "block end is unreachable"; + if (view == FUNCTION) return reachable ? "function ends without return" : NULL; + if (!reachable && fn < 0) return "block end is unreachable"; + if (!reachable) return NULL; /* a loop's block in a function that returns */ if (view == FILTER) return height != 1 || types[0] != T_BOOL ? "filter must leave one bool" : NULL; if (view == FOLD_ONE) return height != 1 || types[0] != T_BOOL ? "fold block must leave one bool" : NULL; if (view == FOLD_TWO) @@ -733,11 +783,11 @@ PURE_COLD static const char *verify_code(const PureModule *m, PureBlock block, i } PURE_COLD static const char *verify_block(const PureModule *m, PureBlock block, int view, int row, int outer, - uint32_t event, bool locals, unsigned nest, uint32_t walked, uint32_t *at) { + uint32_t event, bool locals, unsigned nest, uint32_t walked, int fn, uint32_t *at) { if (block.start > m->code_count || block.length > m->code_count - block.start) return "code range outside module"; unsigned char *target = calloc((size_t)block.length + 1, 1); if (!target) return "out of memory"; - const char *why = verify_code(m, block, view, row, outer, event, locals, nest, walked, at, target); + const char *why = verify_code(m, block, view, row, outer, event, locals, nest, walked, fn, at, target); free(target); return why; } @@ -752,7 +802,7 @@ PURE_COLD static bool has_lanes(const PureModule *m, const PureOp *op, int input } case PURE_OP_CONST: return op->arg != 2; case PURE_OP_LOAD: return m->state_type[op->arg] != PURE_STATE_I64; - case PURE_OP_LOCAL_LOAD: return local_type(op->arg) != T_I64; + case PURE_OP_LOCAL_LOAD: return local_type(op->arg) != T_I64 && local_type(op->arg) != T_LIST; case PURE_OP_ADD: case PURE_OP_SUB: case PURE_OP_MUL: case PURE_OP_DIV: case PURE_OP_NEG: case PURE_OP_LT: case PURE_OP_LE: case PURE_OP_GT: case PURE_OP_GE: case PURE_OP_EQ: case PURE_OP_NE: case PURE_OP_AND: case PURE_OP_OR: case PURE_OP_NOT: case PURE_OP_MIN: case PURE_OP_MAX: case PURE_OP_CLAMP: @@ -842,7 +892,7 @@ PURE_COLD static bool batch_block(const PureModule *m, uint32_t start, uint32_t if (op->arg > arms) arms = op->arg; break; case PURE_OP_LOCAL_STORE: - if (local_type(op->arg) == T_I64) return false; + if (local_type(op->arg) == T_I64 || local_type(op->arg) == T_LIST) return false; if (at >= arms) sure[local / 64] |= bit; break; case PURE_OP_LOCAL_LOAD: @@ -1451,6 +1501,46 @@ PURE_COLD static void range_code(PureModule *m, PureBlock block, int input) { } } +/* What a function's code names (027's 2c), read before it is verified (its arguments bounded here): the event's lists, + * the registers and the values held by name each call has its own of, the lists not an event's it changes, its locals + * and how deep its loops nest; the functions it calls (calls, a bit each). */ +PURE_COLD static void function_names(const PureModule *m, PureFunction *f, uint64_t *calls) { + uint32_t end = f->code.start + f->code.length, ends[PURE_MODULE_NESTING]; + unsigned depth = 0; + if (f->code.start > m->code_count || f->code.length > m->code_count - f->code.start) return; /* refused as it is verified */ + for (uint32_t pc = f->code.start; pc < end; ++pc) { + const PureOp *op = &m->code[pc]; + uint32_t arg = op->arg, list = UINT32_MAX; + while (depth && pc >= ends[depth - 1]) --depth; + switch (op->op) { + case PURE_OP_LIST_APPEND: case PURE_OP_LIST_INSERT: case PURE_OP_LIST_REMOVE: + list = arg; + if (state_of(m, list, PURE_STATE_LIST) && !event_list_state(m, list)) f->changes |= UINT32_C(1) << list; + break; + case PURE_OP_LIST_COUNT: case PURE_OP_LIST_VALUE: case PURE_OP_LIST_BIND: case PURE_OP_INDEX_FIRST: case PURE_OP_INDEX_LAST: + case PURE_OP_INDEX_AT: case PURE_OP_BYTES_OF: case PURE_OP_ROW: case PURE_OP_OUTER_ROW: case PURE_OP_LIST_FIND: + case PURE_OP_LIST_HAS: + list = arg; + break; + case PURE_OP_ITEM_GET: case PURE_OP_ITEM_SET: case PURE_OP_APPEND_IN: list = list_of(arg); break; + case PURE_OP_EACH: case PURE_OP_FOLD: case PURE_OP_LOOP: case PURE_OP_LOCAL_LOAD: case PURE_OP_LOCAL_STORE: + if (op->op == PURE_OP_EACH || op->op == PURE_OP_FOLD) list = arg >> 8 & 0xFF; + if ((op->op == PURE_OP_EACH || op->op == PURE_OP_LOOP) && depth < PURE_MODULE_NESTING) { + ends[depth++] = pc + 1 + (arg >> 16); + if (depth > f->nesting) f->nesting = (uint8_t)depth; + } + if (op->op == PURE_OP_EACH || op->op == PURE_OP_FOLD) break; + if ((arg & 0xFF) < PURE_MODULE_LOCALS && (arg & 0xFF) >= f->locals) f->locals = (uint8_t)((arg & 0xFF) + 1); + if (op->op != PURE_OP_LOOP && (arg >> 8 & 0xFF) == 1) list = arg >> 16; /* an index's list */ + break; + case PURE_OP_BYTES_LOAD: case PURE_OP_BYTES_STORE: f->held |= UINT32_C(1) << (arg & 31); break; + case PURE_OP_CALL: if (arg < PURE_MODULE_FUNCTIONS) *calls |= UINT64_C(1) << arg; break; + default: break; + } + if (event_list_state(m, list)) *(bound_list(m, list) ? &f->registers : &f->lists) |= UINT32_C(1) << list; + } +} + PURE_COLD PureResult pure_module_read(const char *path, PureModule *out, char *error, size_t error_size) { FILE *file = fopen(path, "rb"); unsigned char *bytes = NULL; @@ -1479,7 +1569,8 @@ PURE_COLD PureResult pure_module_read(const char *path, PureModule *out, char *e void pure_module_release(PureModule *m) { pure_jit_free(m->jit); m->jit = NULL; - m->batches = false; + m->batches = m->calls = false; + m->runner = 0; free(m->height); m->height = NULL; free(m->reuse_from), free(m->reuse_length); @@ -1516,21 +1607,31 @@ PURE_COLD PureResult pure_module_load(const void *bytes, size_t size, PureModule out->records = (uint16_t)read16(p + 30); uint32_t constant_bytes = read32(p + 32); out->record_fields = (uint16_t)read16(p + 36); - if (read16(p + 38)) REFUSE("reserved header bytes", 38); + out->functions = (uint16_t)read16(p + 38); if (out->states > PURE_MODULE_STATES || out->inputs > PURE_MODULE_INPUTS || out->views > PURE_MODULE_VIEWS || out->handlers > PURE_MODULE_HANDLERS || out->code_count > PURE_MODULE_CODE || strings > PURE_MODULE_STRINGS || out->fields > PURE_MODULE_FIELDS || out->collections > PURE_MODULE_COLLECTIONS || out->constants > PURE_MODULE_CONSTANTS || constant_bytes > PURE_MODULE_CONSTANT_BYTES || - out->records > PURE_MODULE_RECORDS || out->record_fields > PURE_MODULE_RECORD_FIELDS) { + out->records > PURE_MODULE_RECORDS || out->record_fields > PURE_MODULE_RECORD_FIELDS || + out->functions > PURE_MODULE_FUNCTIONS) { result = PURE_LIMIT; REFUSE("module exceeds a limit", 8); } - size_t expected = PURE_MODULE_HEADER + (size_t)out->states * STATE_BYTES + + size_t functions_at = PURE_MODULE_HEADER + (size_t)out->states * STATE_BYTES + (size_t)out->collections * COLLECTION_BYTES + (size_t)out->inputs * INPUT_BYTES + (size_t)out->fields * FIELD_BYTES + (size_t)out->constants * CONSTANT_BYTES + (size_t)out->records * RECORD_BYTES + (size_t)out->record_fields * RECORD_FIELD_BYTES + - (size_t)out->views * VIEW_BYTES + (size_t)out->handlers * HANDLER_BYTES + + (size_t)out->views * VIEW_BYTES + (size_t)out->handlers * HANDLER_BYTES; + size_t signatures = 0; /* the functions' parameters' and results' items, in their order */ + if (size < functions_at + (size_t)out->functions * FUNCTION_BYTES) REFUSE("module size", functions_at); + for (uint32_t i = 0; i < out->functions; ++i) signatures += (size_t)p[functions_at + i * FUNCTION_BYTES + 8] + + p[functions_at + i * FUNCTION_BYTES + 9]; + if (signatures > PURE_MODULE_SIGNATURES) { + result = PURE_LIMIT; + REFUSE("module exceeds a limit", functions_at); + } + size_t expected = functions_at + (size_t)out->functions * FUNCTION_BYTES + signatures * SIGNATURE_BYTES + (size_t)out->code_count * OP_BYTES + strings + constant_bytes; if (size != expected) REFUSE("module size", expected); /* The code, the constants' offsets and lengths, then their bytes, in one block. */ @@ -1766,6 +1867,21 @@ PURE_COLD PureResult pure_module_load(const void *bytes, size_t size, PureModule (input >= 0 && (out->input[input].kind == PURE_KIND_OUTPUT || out->input[input].kind == PURE_KIND_ARGUMENTS))) REFUSE("handler event", i); } + /* Functions (027's 2c): a block and the counts of its parameters and results, whose types follow every function's. */ + for (uint32_t i = 0, item = 0; i < out->functions; ++i, at += FUNCTION_BYTES) { + out->function[i] = (PureFunction){.code = {read32(at), read32(at + 4)}, .first = (uint16_t)item, .params = at[8], + .results = at[9]}; + if (read16(at + 10)) REFUSE("function padding", i); + item += (uint32_t)at[8] + at[9]; + } + for (uint32_t k = 0; k < signatures; ++k, at += SIGNATURE_BYTES) { + out->signature_type[k] = at[0]; + out->signature_record[k] = (uint16_t)read16(at + 2); + if (at[1] || at[0] > PURE_SIGNATURE_BYTES || + (at[0] == PURE_RECORD_LIST ? out->signature_record[k] >= out->records : out->signature_record[k] != 0)) + REFUSE("function signature", k); + } + out->calls = out->functions > 0; for (uint32_t i = 0; i < out->code_count; ++i, at += OP_BYTES) { if (at[1] || at[2] || at[3]) REFUSE("instruction padding", i); out->code[i] = (PureOp){.op = at[0], .arg = read32(at + 4), .value = read_double(at + 8)}; @@ -1794,7 +1910,7 @@ PURE_COLD PureResult pure_module_load(const void *bytes, size_t size, PureModule bool computes = !table && !out->view_table[i]; /* a view outside a table may have a body */ if ((!table || out->view_code[i].length) && (why = verify_block(out, out->view_code[i], table ? FILTER : out->view_type[i], - table || out->view_table[i] ? out->view_list[i] : -1, -1, event, computes, 0, 0, &bad))) + table || out->view_table[i] ? out->view_list[i] : -1, -1, event, computes, 0, 0, -1, &bad))) goto refused; if (computes && !locals_agree(out, out->view_code[i])) { why = "local used as two things"; goto refused; } for (uint32_t pc = out->view_code[i].start; computes && pc < out->view_code[i].start + out->view_code[i].length; ++pc) { @@ -1807,9 +1923,29 @@ PURE_COLD PureResult pure_module_load(const void *bytes, size_t size, PureModule } if (out->view_lists[i]) out->view_body[i] = true; } + /* What each function names, and the lists it changes with those the functions it calls change (until none adds). */ + uint64_t calls[PURE_MODULE_FUNCTIONS] = {0}; + for (uint32_t i = 0; i < out->functions; ++i) function_names(out, &out->function[i], &calls[i]); + for (bool more = out->functions > 0; more;) { + more = false; + for (uint32_t i = 0; i < out->functions; ++i) + for (uint64_t left = calls[i]; left; left &= left - 1) { + uint32_t was = out->function[i].changes; + out->function[i].changes |= out->function[__builtin_ctzll(left)].changes; + more = more || out->function[i].changes != was; + } + } + for (uint32_t i = 0; i < out->functions; ++i) { + bad = i; + PureFunction *f = &out->function[i]; + if ((why = verify_block(out, f->code, FUNCTION, -1, -1, 0, true, 0, 0, (int)i, &bad))) goto refused; + if (!locals_agree(out, f->code)) { why = "local used as two things"; goto refused; } + for (uint32_t pc = f->code.start; pc < f->code.start + f->code.length; ++pc) /* its frame's stack: as the verifier went */ + if (out->height[pc] >= f->height) f->height = (uint8_t)(out->height[pc] + 1); + } for (uint32_t i = 0; i < out->handlers; ++i) { bad = i; - if ((why = verify_block(out, out->handler[i].code, -1, -1, -1, out->handler[i].event, true, 0, 0, &bad))) goto refused; + if ((why = verify_block(out, out->handler[i].code, -1, -1, -1, out->handler[i].event, true, 0, 0, -1, &bad))) goto refused; if (!locals_agree(out, out->handler[i].code)) { why = "local used as two things"; goto refused; } } for (uint32_t i = 0; i < out->views; ++i) { @@ -1907,6 +2043,7 @@ PURE_COLD PureResult pure_module_load(const void *bytes, size_t size, PureModule result = PURE_ALLOCATION; REFUSE("out of memory", 0); } + out->runner = out->calls ? 2 : out->batches ? 1 : 0; out->jit = pure_jit_make(out); /* none: the executor runs it all */ return PURE_OK; refused: @@ -2226,9 +2363,25 @@ static bool copy_out(void *context, PureSpan span) { } /* BYTES_STORE: the value held by name slot becomes v, or v after it (append); what it holds counts in the room. - * 1 where that passes the room (MEMORY), 2 out of memory, else 0. */ + * 1 where that passes the room (MEMORY), 2 out of memory, else 0. A value of the payload, the arguments or the constants + * lasts the event: it is held as it is (by_ref), nothing copied, until something is appended to it. */ +static int hold_copy(PureApp *app, PureArena *arena, unsigned slot, PureBytes v, bool append); static int hold(PureApp *app, PureArena *arena, unsigned slot, PureBytes v, bool append) { __typeof__(app->held[0]) *h = &app->held[slot]; + if (!append && (v.source == FROM_PAYLOAD || v.source == FROM_ARGUMENTS || v.source == FROM_CONSTANT)) { + if (!h->by_ref) (void)grows(app, (Held){0, h->size}, (Held){0, 0}); + h->ref = v, h->size = (size_t)v.length, h->by_ref = true; + return 0; + } + if (h->by_ref) { /* what it held as it was: copied first when v follows it */ + h->by_ref = false, h->size = 0; + int held = append ? hold_copy(app, arena, slot, h->ref, false) : 0; + if (held) return held; + } + return hold_copy(app, arena, slot, v, append); +} +static int hold_copy(PureApp *app, PureArena *arena, unsigned slot, PureBytes v, bool append) { + __typeof__(app->held[0]) *h = &app->held[slot]; size_t mark = arena->used, before = h->size, at = append ? h->size : 0, size = at + (size_t)v.length; if (v.source == FROM_HELD && v.owner == slot && v.length) { /* a part of itself: by way of the arena */ if (append_value(app, arena, v) != PURE_OK) return 2; @@ -3753,7 +3906,8 @@ static inline __attribute__((always_inline)) int step(Frame *frame, const PureOp NEXT; } case PURE_OP_BYTES_LOAD: - stack[sp++].bytes = (PureBytes){FROM_HELD, (uint16_t)(arg & 0xFF), {0, 0}, 0, app->held[arg & 0xFF].size}; + stack[sp++].bytes = app->held[arg & 0xFF].by_ref ? app->held[arg & 0xFF].ref + : (PureBytes){FROM_HELD, (uint16_t)(arg & 0xFF), {0, 0}, 0, app->held[arg & 0xFF].size}; NEXT; case PURE_OP_BYTES_STORE: { int held = hold(app, arena, arg & 0xFF, stack[--sp].bytes, arg & PURE_HELD_APPEND); @@ -3823,6 +3977,38 @@ static inline __attribute__((always_inline)) int step(Frame *frame, const PureOp if (!grows(app, before, (Held){0, pure_list_size(in)})) { kind = PURE_FAULT_MEMORY; FAILED; } NEXT; } + case PURE_OP_CALL: case PURE_OP_RETURN: /* run_calls' (the frames are its): no other run meets one */ + frame->fault_pc = pc; + return !batches ? STEP_FAULT : op->op == PURE_OP_CALL ? STEP_CALL : STEP_BACK; + case PURE_OP_CHAR_AT: { /* the character beginning at a byte position of a text (UTF-8: whole from there) */ + int64_t at = stack[--sp].i64; + PureBytes v = stack[sp - 1].bytes; + if (at < 0 || (uint64_t)at >= v.length) { kind = PURE_FAULT_LIMIT; FAILED; } + unsigned char b[4] = {0}; + Copy into = {b}; + v.offset += (uint64_t)at; + v.length = v.length - (uint64_t)at < 4 ? v.length - (uint64_t)at : 4; + if ((status = visit_value(app, arena, v, copy_out, &into)) != PURE_OK) STOPPED(status); + if ((b[0] & 0xC0) == 0x80) { kind = PURE_FAULT_LIMIT; FAILED; } /* within a character */ + stack[sp - 1].i64 = b[0] < 0x80 ? b[0] : b[0] < 0xE0 ? (b[0] & 0x1F) << 6 | (b[1] & 0x3F) : + b[0] < 0xF0 ? (b[0] & 0x0F) << 12 | (b[1] & 0x3F) << 6 | (b[2] & 0x3F) : + (b[0] & 0x07) << 18 | (b[1] & 0x3F) << 12 | (b[2] & 0x3F) << 6 | (b[3] & 0x3F); + NEXT; + } + case PURE_OP_CHAR: { /* the text of a code point */ + int64_t c = top->i64; + if (c < 0 || c > 0x10FFFF) { kind = PURE_FAULT_LIMIT; FAILED; } + if (c >= 0xD800 && c < 0xE000) { kind = PURE_FAULT_ENCODING; FAILED; } + unsigned char b[4]; + size_t n = c < 0x80 ? 1 : c < 0x800 ? 2 : c < 0x10000 ? 3 : 4; + if (n == 1) b[0] = (unsigned char)c; + else { + for (size_t k = n - 1; k > 0; --k, c >>= 6) b[k] = (unsigned char)(0x80 | (c & 0x3F)); + b[0] = (unsigned char)((0xF00 >> n & 0xF0) | c); /* 110x, 1110, 11110 */ + } + if ((status = keep_bytes(arena, b, n, &top->bytes)) != PURE_OK) STOPPED(status); + NEXT; + } default: break; } double b = stack[--sp].num, a = stack[sp - 1].num, value; @@ -3956,6 +4142,245 @@ static __attribute__((noinline)) PureResult run_compiled(PureCompiled code, cons return finish(&frame, code(&frame), result); } +/* ---- Calls (027's 2c). A call's frame, in the app's blocks of frames (they never move: a loop points into its frame): + * the frame below, where the caller was (what follows its CALL, where its code ends, its loops, stack, locals and walk), + * where the blocks stood before it and its bytes (counted in the event's room); then what it keeps of the caller's own + * (the lists the function's code names, its held values) and the callee's stack, locals and loops. */ +typedef struct Call { + struct Call *below; + uint32_t back, end, function; + unsigned depth, block; + size_t sp, used, bytes, row; + Slot *stack; + Loop *loops; + PureValue *locals; + Walk *walk; +} Call; +typedef __typeof__(((PureApp *)0)->held[0]) Kept; + +/* Room for a frame of bytes among the app's blocks: where they stood before it, or NULL out of memory. */ +static void *frame_room(PureApp *app, size_t bytes, unsigned *block, size_t *used) { + __typeof__(app->calls) *c = &app->calls; + *block = c->at, *used = c->used; + if (c->count && c->sizes[c->at] - c->used >= bytes) { + void *room = c->blocks[c->at] + c->used; + c->used += bytes; + return room; + } + unsigned next = c->count ? c->at + 1 : 0; /* the blocks after the one in use are free */ + if (next < c->count && c->sizes[next] < bytes) free(c->blocks[next]), c->blocks[next] = NULL; + if (next == c->count) { + unsigned char **blocks = realloc(c->blocks, (c->count + 1) * sizeof(*blocks)); + if (blocks) c->blocks = blocks; + size_t *sizes = blocks ? realloc(c->sizes, (c->count + 1) * sizeof(*sizes)) : NULL; + if (!sizes) return NULL; + c->sizes = sizes; + c->blocks[c->count++] = NULL; + } + if (!c->blocks[next]) { + size_t size = (size_t)64 << 10 << (next < 8 ? next : 8); /* 64 KB, twice as much each block on to 16 MB */ + if (size < bytes) size = bytes; + if (!(c->blocks[next] = malloc(size))) return NULL; + c->sizes[next] = size; + } + c->at = next, c->used = bytes; + return c->blocks[next]; +} + +/* An empty list of an event's list state for a call: one a call let go, or a new one (NULL: out of memory). */ +static PureList *spare_list(PureApp *app, uint32_t state) { + __typeof__(app->spare[0]) *spare = &app->spare[state]; + return spare->count ? spare->lists[--spare->count] : new_list(app->module, app->module->state_ref[state]); +} + +/* A call's list let go: emptied (what it held no longer counted) and kept for the next calls. */ +static void let_list_go(PureApp *app, uint32_t state, PureList *list) { + Held before = list_held(app, list); + pure_list_clear(list); + (void)grows(app, before, list_held(app, list)); + __typeof__(app->spare[0]) *spare = &app->spare[state]; + if (spare->count == spare->capacity) { + unsigned capacity = spare->capacity ? 2 * spare->capacity : 4; + PureList **lists = realloc(spare->lists, capacity * sizeof(*lists)); + if (!lists) { pure_list_free(list); return; } + spare->lists = lists, spare->capacity = capacity; + } + spare->lists[spare->count++] = list; +} + +static void drop_spares(PureApp *app) { + for (unsigned i = 0; i < PURE_MODULE_STATES; ++i) { + for (unsigned k = 0; k < app->spare[i].count; ++k) pure_list_free(app->spare[i].lists[k]); + free(app->spare[i].lists); + app->spare[i].lists = NULL, app->spare[i].count = app->spare[i].capacity = 0; + } +} + +/* The first count of the lists and registers a function's code names given back what a call kept of them (its own + * lists let go). */ +static void restore_lists(PureApp *app, const PureFunction *f, PureList **kept, unsigned count) { + unsigned k = 0; + for (uint32_t left = f->lists | f->registers; left && k < count; left &= left - 1, ++k) { + uint32_t state = (uint32_t)__builtin_ctz(left); + if (!(f->registers >> state & 1)) let_list_go(app, state, app->lists[state]); + app->lists[state] = kept[k]; + } +} + +/* A frame closed: the caller's lists, registers and held values given back (the callee's let go), its locals and walk, + * the frame's room in the blocks and in the event's room. The frame below. */ +static Call *give_back(PureApp *app, Call *call, Event *ev) { + const PureFunction *f = &app->module->function[call->function]; + unsigned keeps = (unsigned)__builtin_popcount(f->lists | f->registers), j = 0; + PureList **kept = (PureList **)(call + 1); + Kept *held = (Kept *)(kept + keeps); + restore_lists(app, f, kept, keeps); + for (uint32_t left = f->held; left; left &= left - 1, ++j) { + Kept *h = &app->held[__builtin_ctz(left)]; + if (!h->by_ref) (void)grows(app, (Held){0, h->size}, (Held){0, 0}); + free(h->data); + *h = held[j]; + } + ev->locals = call->locals, ev->walk = call->walk, ev->row = call->row; + (void)grows(app, (Held){0, call->bytes}, (Held){0, 0}); + app->calls.at = call->block, app->calls.used = call->used; + return call->below; +} + +/* A bytes or text value a call would lose (held by name in a slot the callee has its own of): a copy in the arena. */ +static bool kept_apart(PureApp *app, PureArena *arena, const PureFunction *f, uint8_t type, PureBytes *v) { + if ((type != PURE_RECORD_TEXT && type != PURE_SIGNATURE_BYTES) || v->source != FROM_HELD || !(f->held >> v->owner & 1)) + return true; + size_t start = arena->used; + if (append_value(app, arena, *v) != PURE_OK) return false; + *v = (PureBytes){FROM_ARENA, 0, {0, 0}, start, v->length}; + return true; +} + +/* CALL (just before *pc): its function's frame open (*top), its block next. STEP_NEXT, or a fault (WORK, MEMORY) or a + * stop out of memory, nothing opened. */ +static __attribute__((noinline, cold)) int enter_call(Frame *frame, Call **top, uint32_t *pc) { + const PureModule *m = frame->m; + PureApp *app = frame->app; + Event *ev = frame->ev; + uint32_t function = m->code[*pc - 1].arg; + const PureFunction *f = &m->function[function]; + unsigned keeps = (unsigned)__builtin_popcount(f->lists | f->registers), holds = (unsigned)__builtin_popcount(f->held); + size_t bytes = (sizeof(Call) + keeps * sizeof(PureList *) + holds * sizeof(Kept) + f->height * sizeof(Slot) + + f->locals * sizeof(PureValue) + f->nesting * sizeof(Loop) + 15) & ~(size_t)15; + frame->fault_pc = *pc - 1; + if (!charge(app, f->code.length)) { frame->kind = PURE_FAULT_WORK; return STEP_FAULT; } + if (!grows(app, (Held){0, 0}, (Held){0, bytes})) { frame->kind = PURE_FAULT_MEMORY; return STEP_FAULT; } + unsigned block; + size_t used, base = frame->sp - f->params; + Call *call = frame_room(app, bytes, &block, &used); + if (!call) { frame->status = PURE_ALLOCATION; return STEP_RETURN; } + PureList **kept = (PureList **)(call + 1); + Kept *held = (Kept *)(kept + keeps); + Slot *stack = (Slot *)(held + holds); + PureValue *locals = (PureValue *)(stack + f->height); + bool whole = true; + unsigned k = 0; + for (unsigned i = 0; whole && i < f->params; ++i) { /* its arguments, its stack as it begins */ + stack[i] = frame->stack[base + i]; + whole = kept_apart(app, frame->arena, f, m->signature_type[f->first + i], &stack[i].bytes); + } + for (uint32_t left = f->lists | f->registers; whole && left; left &= left - 1, ++k) { /* its own lists, registers */ + uint32_t state = (uint32_t)__builtin_ctz(left); + PureList *own = f->registers >> state & 1 ? (app->unbound[state] ? app->unbound[state] : app->lists[state]) + : spare_list(app, state); + if (!own) { + restore_lists(app, f, kept, k); + whole = false; + break; + } + kept[k] = app->lists[state], app->lists[state] = own; + } + if (!whole) { + app->calls.at = block, app->calls.used = used; + frame->status = PURE_ALLOCATION; + return STEP_RETURN; + } + unsigned j = 0; + for (uint32_t left = f->held; left; left &= left - 1, ++j) { /* its held values, empty */ + Kept *h = &app->held[__builtin_ctz(left)]; + held[j] = *h; + *h = (Kept){0}; + } + *call = (Call){.below = *top, .back = *pc, .end = frame->end, .function = function, .depth = frame->depth, .block = block, + .sp = base, .used = used, .bytes = bytes, .row = ev->row, .stack = frame->stack, .loops = frame->loops, + .locals = ev->locals, .walk = ev->walk}; + if (f->locals) memset(locals, 0, f->locals * sizeof(*locals)); + frame->stack = stack, frame->sp = f->params, frame->loops = (Loop *)(locals + f->locals), frame->depth = 0; + frame->end = f->code.start + f->code.length; + ev->locals = locals, ev->walk = NULL; + *top = call; + *pc = f->code.start; + return STEP_NEXT; +} + +/* RETURN (just before *pc): its results in the place of the call's arguments, the frame closed, what follows the CALL + * next. STEP_NEXT, or a stop out of memory (the frame still open). */ +static __attribute__((noinline, cold)) int leave_call(Frame *frame, Call **top, uint32_t *pc) { + const PureModule *m = frame->m; + Call *call = *top; + const PureFunction *f = &m->function[call->function]; + Slot *results = frame->stack + frame->sp - f->results; + for (unsigned i = 0; i < f->results; ++i) + if (!kept_apart(frame->app, frame->arena, f, m->signature_type[f->first + f->params + i], &results[i].bytes)) { + frame->status = PURE_ALLOCATION; + return STEP_RETURN; + } + for (unsigned i = 0; i < f->results; ++i) call->stack[call->sp + i] = results[i]; + frame->stack = call->stack, frame->sp = call->sp + f->results, frame->loops = call->loops, frame->depth = call->depth; + frame->end = call->end; + *pc = call->back; + *top = give_back(frame->app, call, frame->ev); + return STEP_NEXT; +} + +/* Every frame still open closed (a run stopped in a call). */ +static __attribute__((noinline, cold)) void unwind_calls(Frame *frame, Call *top) { + while (top) top = give_back(frame->app, top, frame->ev); +} + +/* The executor's run of a block of a module with functions (027's 2c): run_batches' steps and batches, and calls: a + * CALL opens its function's frame and its block runs on in this loop, a RETURN closes it. Its own copy of the steps, + * as run_batches is. */ +static __attribute__((noinline, aligned(64))) PureResult run_calls(const PureModule *m, PureValue *values, PureBlock block, Event *ev, + Slot *result) { + Slot stack[PURE_MODULE_STACK]; + Loop loops[PURE_MODULE_NESTING]; + Frame frame; + open_frame(&frame, m, values, block, ev, stack, loops); + Call *top = NULL; + int how = STEP_NEXT; + for (uint32_t pc = block.start;;) { + if (pc >= frame.end) { + if (!frame.depth || (how = iterate(&frame, &pc)) != STEP_NEXT) break; + continue; + } + if ((how = step(&frame, &m->code[pc], pc, &pc, true)) == STEP_NEXT) continue; + if (how != STEP_CALL && how != STEP_BACK && how != STEP_BATCH) break; + Frame apart = frame; /* the frame's copy (no call sees the frame itself: its fields stay in registers) */ + if (how == STEP_CALL) how = enter_call(&apart, &top, &pc); + else if (how == STEP_BACK) how = leave_call(&apart, &top, &pc); + else { + uint32_t past = 0; + how = open_batches(&apart, pc - 1, &past); + pc = past; + } + frame = apart; + if (how != STEP_NEXT) break; + } + if (top) { + Frame apart = frame; + unwind_calls(&apart, top); + frame = apart; + } + return finish(&frame, how, result); +} + /* The executor's run of a block of a module with loops planned PLAN_BATCH: * run's, those loops in batches (module-batch.c). Its own copy of the * steps: in run's, a batch's way among them would cost every instruction @@ -3987,7 +4412,7 @@ static __attribute__((noinline, aligned(64))) PureResult run_batches(const PureM static __attribute__((aligned(64))) PureResult run(const PureModule *m, PureValue *values, PureBlock block, Event *ev, Slot *result) { PureCompiled code = m->jit ? pure_jit_code(m->jit, block) : NULL; if (code) return run_compiled(code, m, values, block, ev, result); - if (m->batches) return run_batches(m, values, block, ev, result); + if (m->runner) return m->runner == 2 ? run_calls(m, values, block, ev, result) : run_batches(m, values, block, ev, result); Slot stack[PURE_MODULE_STACK]; Loop loops[PURE_MODULE_NESTING]; Frame frame; @@ -4246,6 +4671,9 @@ void pure_app_stop(PureApp *app) { } pure_retired_free(&app->retired); for (unsigned i = 0; i < PURE_MODULE_HELD; ++i) free(app->held[i].data); + for (unsigned i = 0; i < app->calls.count; ++i) free(app->calls.blocks[i]); + free(app->calls.blocks), free(app->calls.sizes); + drop_spares(app); drop_nested(app); free(app->nested.list); free(app->nested.shared); @@ -4385,7 +4813,7 @@ static PureResult dispatch(PureApp *app, uint32_t event, Event *ev) { * holds for it the default room, or the budget when that is larger. */ app->grown = app->spent = 0; app->room = app->memory > PURE_GROWTH_DEFAULT ? app->memory : PURE_GROWTH_DEFAULT; - for (unsigned i = 0; m->held && i < PURE_MODULE_HELD; ++i) app->held[i].size = 0; + for (unsigned i = 0; m->held && i < PURE_MODULE_HELD; ++i) app->held[i].size = 0, app->held[i].by_ref = false; if (app->nested.count) unbind(app), drop_nested(app); /* a view's body bound some on the app itself */ Mark mark; mark_event(app, &mark); @@ -4734,7 +5162,7 @@ static PureResult evaluate(PureApp *app, uint32_t view, size_t row, Slot *out) { if (!own_lists(app, m->view_lists[view])) return PURE_ALLOCATION; app->grown = app->spent = 0; app->room = app->memory > PURE_GROWTH_DEFAULT ? app->memory : PURE_GROWTH_DEFAULT; - for (unsigned i = 0; m->held && i < PURE_MODULE_HELD; ++i) app->held[i].size = 0; + for (unsigned i = 0; m->held && i < PURE_MODULE_HELD; ++i) app->held[i].size = 0, app->held[i].by_ref = false; unbind(app); if (app->nested.count) drop_nested(app); } @@ -5429,6 +5857,7 @@ PURE_COLD PureResult pure_app_start(PureApp *app, const PureModule *module, Pure PURE_COLD PureResult pure_app_replace(PureApp *app, const PureModule *module) { unbind(app); /* lists are laid out again: none bound, the event's in records let go */ drop_nested(app); + drop_spares(app); pure_app_finish(app); if (app->open || app->pending_count) { PureResult saved = pure_app_save(app); /* the burst belongs to the module that made it */ diff --git a/core/module.h b/core/module.h index 52cd4d8..9ce354f 100644 --- a/core/module.h +++ b/core/module.h @@ -46,6 +46,7 @@ typedef enum { PURE_OP_I64_BITS, PURE_OP_BYTE_AT, PURE_OP_BYTES_OF, PURE_OP_INDEX_AT, PURE_OP_BYTES_SLICE, PURE_OP_BYTE, PURE_OP_BYTES_LOAD, PURE_OP_BYTES_STORE, PURE_OP_LIST_VALUE, PURE_OP_LIST_BIND, PURE_OP_APPEND_IN, PURE_OP_NUM_PARSE, + PURE_OP_CALL, PURE_OP_RETURN, PURE_OP_CHAR_AT, PURE_OP_CHAR, PURE_OP_COUNT } PureOpcode; /* A bool is its own type (docs/design/016-bool-and-i64.md), held as a @@ -110,10 +111,31 @@ enum { PURE_MODULE_HELD = 32, PURE_HELD_TEXT = 16, PURE_HELD_APPEND = 1 << 8 }; typedef enum { PURE_FORMAT_PLAIN, PURE_FORMAT_DECIMAL, PURE_FORMAT_HEX, PURE_FORMAT_HEX_UPPER, PURE_FORMAT_BINARY, PURE_FORMAT_OCTAL, PURE_FORMAT_FIXED } PureFormat; enum { PURE_FORMAT_WIDTH = 8, PURE_FORMAT_ZEROS = 1 << 16, PURE_FORMAT_FORM = 17, PURE_FORMAT_DIGITS = 20 }; +/* 027's stage 2c: functions and characters. A function (PureFunction) is a + * block CALL runs (its argument the function's number): the block begins with + * the call's arguments as its stack, its parameters' types, and RETURN ends + * it with its results on top (the rest of its stack let go), which take the + * arguments' place on the caller's stack. Each call has its own stack and + * locals (0 as it begins), and its own of what the function's code names: + * values held by name (empty), an event's lists (empty) and registers (bound + * to none); the caller's are as they were when the call returns. A function + * runs as a handler's code does but for a message (no field, document or + * reply); a handler and the functions run CALL (not a view), and a walk around + * a call keeps to what the callee changes as it keeps to its own block's + * changes. Calls nest as deep as the event's room allows: each counts its + * frame's bytes there (MEMORY past it) and its block's length as work. + * Outside a function, LOOP and EACH take their operands from a stack that + * holds nothing else: a loop's block begins at the bottom of its run's stack. + * CHAR_AT gives the character at a byte position of a text (an i64: its code + * point), failing as LIMIT where no character begins there; CHAR makes the + * text of a code point, failing as LIMIT outside 0-0x10FFFF and as ENCODING + * for a surrogate. */ +enum { PURE_MODULE_FUNCTIONS = 64, PURE_MODULE_SIGNATURES = 1024, PURE_SIGNATURE_BYTES = 5 }; /* A local: one of an event's PURE_MODULE_LOCALS slots, 0 when the event * begins and never saved. LOCAL_LOAD and LOCAL_STORE name the slot (bits - * 0-7), what it holds (bits 8-15: 0 a number, 1 an index, 2 a bool) and an index's - * list (bits 16-31); a handler uses a slot for one of them. A handler, the + * 0-7), what it holds (bits 8-15: 0 a number, 1 an index, 2 a bool, 3 an i64, + * 4 a list value, 027's 2c) and an index's list or a list's record (bits + * 16-31); a handler uses a slot for one of them. A handler, the * walks in it and the folds in those read locals; the handler and its walks * store them. */ enum { PURE_MODULE_LOCALS = 64 }; @@ -256,6 +278,17 @@ const char *pure_fault_name(PureFault); typedef struct { union { double value; int64_t integer; }; uint32_t arg; uint8_t op, plan, shape, range; } PureOp; typedef struct { uint32_t start, length; } PureBlock; typedef struct { uint32_t event; PureBlock code; } PureHandler; +/* A function's block and its parameters' and results' types, from first among the module's signature items: a record + * field's type (PureRecordType: a list's with its record) or PURE_SIGNATURE_BYTES. Set at load: the event's lists, + * registers and held values each call has its own of (a bit each), the lists not an event's it changes (or a function + * it calls does), and its frame: its stack's height at most, its locals and its loops. */ +typedef struct { + PureBlock code; + uint16_t first; + uint8_t params, results; + uint32_t lists, registers, held, changes; + uint8_t height, locals, nesting; +} PureFunction; typedef struct { char name[PURE_MODULE_NAME]; uint8_t type; uint16_t rows; uint32_t offset; } PureField; typedef struct { uint8_t kind; @@ -315,6 +348,7 @@ typedef struct { uint32_t batch_plan_count; /* in their loops' order */ struct PureJit *jit; /* its blocks compiled (module-jit.c, docs/design/021), or NULL */ bool batches; /* a loop of it is planned to run in batches (module-batch.c, docs/design/024) */ + uint8_t runner; /* which executor runs its blocks: 0 run's own steps, 1 with batches, 2 with calls (module.c) */ bool held; /* it holds bytes or texts by name (BYTES_STORE): events and views empty them as they begin */ PureInputShape input[PURE_MODULE_INPUTS]; PureField field[PURE_MODULE_FIELDS]; @@ -347,6 +381,11 @@ typedef struct { PureValue record_field_default[PURE_MODULE_RECORD_FIELDS]; /* a number (a bool's 0 or 1), an i64, a text constant's index * or a list's record (LIST, its i64) */ bool record_nested[PURE_MODULE_RECORDS]; /* a record with a LIST field (set at load) */ + uint16_t functions; + PureFunction function[PURE_MODULE_FUNCTIONS]; + uint8_t signature_type[PURE_MODULE_SIGNATURES]; + uint16_t signature_record[PURE_MODULE_SIGNATURES]; + bool calls; /* it has functions: its blocks run in the executor that calls (module.c) */ } PureModule; /* Whether a state of m is transient (PURE_STATE_TRANSIENT). */ @@ -540,11 +579,16 @@ typedef struct { PureRetired retired; /* list items let go since it was made */ bool reading; /* a reader: its states are a snapshot's */ /* The values an event or a view's body holds by name (BYTES_STORE): emptied as it begins. */ - struct { unsigned char *data; size_t size, capacity; } held[PURE_MODULE_HELD]; + /* A value of the event's payload, arguments or constants is held as it is (by_ref: ref, nothing copied). */ + struct { unsigned char *data; size_t size, capacity; PureBytes ref; bool by_ref; } held[PURE_MODULE_HELD]; /* The lists in records an event or a view's body made (LIST fields: a value is a number here, 1 on), how many * values share each, and the bound lists' own (a register's list while another is bound to it). */ struct { PureList **list; uint32_t *shared; size_t count, capacity; } nested; PureList *unbound[PURE_MODULE_STATES]; + /* Calls (027's 2c): the frames of those open, in blocks that never move (code points into a frame), the block in + * use and how much of it; and the event's lists calls let go, emptied, each state's for its next calls. */ + struct { unsigned char **blocks; size_t *sizes; unsigned count, at; size_t used; } calls; + struct { PureList **lists; unsigned count, capacity; } spare[PURE_MODULE_STATES]; } PureApp; PureResult pure_app_start(PureApp *, const PureModule *, PureData data); diff --git a/core/test-module.c b/core/test-module.c index f45cada..893aeab 100644 --- a/core/test-module.c +++ b/core/test-module.c @@ -62,12 +62,18 @@ typedef struct { const char *name; const RF *fields; size_t nfields; } R; /* A further view: a table (type 2, start = list state) or a column of the * view numbered table - 1. */ typedef struct { const char *name; uint32_t type, table, start, length; } W; +/* A function (027's 2c): its block, and its parameters' then its results' types (a record field's: 0 a number, 1 a + * text, 2 a bool, 3 an i64, 4 a list whose record is beside it; 5 bytes). */ +typedef struct { uint32_t start, length; uint8_t params, results, types[16]; uint16_t records[16]; } FN; typedef struct { const S *s; size_t ns; const I *in; size_t ni; const V *v; size_t nv; const H *h; size_t nh; const O *o; size_t no; const char *const *c; size_t nc; const T *t; size_t nt; const char *const *k; size_t nk; const V *tv; size_t ntv; const R *r; size_t nr; const W *w; size_t nw; } Spec; +/* The functions the next build writes (load_functions sets them a moment). */ +static const FN *spec_fn; +static size_t spec_nfn; static unsigned char *put32(unsigned char *p, uint32_t v) { for (unsigned i = 0; i < 4; ++i) p[i] = (unsigned char)(v >> (8 * i)); @@ -125,7 +131,7 @@ static size_t build(unsigned char *out, Spec spec) { put32(p + 16, (uint32_t)spec.no); put32(p + 20, (uint32_t)used); p[24] = (unsigned char)fields; p[26] = (unsigned char)spec.nc; p[28] = (unsigned char)spec.nk; - p[30] = (unsigned char)spec.nr; p[36] = (unsigned char)record_fields; + p[30] = (unsigned char)spec.nr; p[36] = (unsigned char)record_fields; p[38] = (unsigned char)spec_nfn; put32(p + 32, (uint32_t)blob_used); p += 40; size_t n = 0; @@ -203,6 +209,16 @@ static size_t build(unsigned char *out, Spec spec) { p = put32(p, w->length); } for (size_t i = 0; i < spec.nh; ++i) { p = put32(p, spec.h[i].event); p = put32(p, spec.h[i].start); p = put32(p, spec.h[i].length); } + for (size_t i = 0; i < spec_nfn; ++i) { + p = put32(p, spec_fn[i].start); + p = put32(p, spec_fn[i].length); + *p++ = spec_fn[i].params; *p++ = spec_fn[i].results; *p++ = 0; *p++ = 0; + } + for (size_t i = 0; i < spec_nfn; ++i) + for (unsigned k = 0; k < (unsigned)spec_fn[i].params + spec_fn[i].results; ++k) { + *p++ = spec_fn[i].types[k]; *p++ = 0; + *p++ = (unsigned char)spec_fn[i].records[k]; *p++ = (unsigned char)(spec_fn[i].records[k] >> 8); + } for (size_t i = 0; i < spec.no; ++i) { *p++ = spec.o[i].op; *p++ = 0; *p++ = 0; *p++ = 0; p = put32(p, spec.o[i].arg); @@ -222,6 +238,13 @@ static PureResult load(Spec spec, PureModule *out) { return pure_module_load(bytes, size, out, error, sizeof(error)); } +static PureResult load_functions(Spec spec, const FN *fns, size_t count, PureModule *out) { + spec_fn = fns, spec_nfn = count; + PureResult result = load(spec, out); + spec_fn = NULL, spec_nfn = 0; + return result; +} + #define LEN(a) (sizeof(a) / sizeof(*(a))) #define SPEC(s, in, v, h, o) ((Spec){s, LEN(s), in, LEN(in), v, LEN(v), h, LEN(h), o, LEN(o), NULL, 0, NULL, 0, NULL, 0, NULL, 0, NULL, 0, NULL, 0}) @@ -6318,6 +6341,168 @@ static void lists_in_records(void) { printf("{\"lists_in_records\":{\"rounds\":3,\"refused\":%zu}}\n", LEN(refused) + 1); } +/* Functions and characters (027's 2c): a function calls itself; each call has its own locals, lists, registers and + * held values (a caller's as they were when it returns); a walk goes on around a call; calls count as work and memory; + * the verifier keeps to a function's types and to what a walk around a call keeps to. */ +enum { CALL = PURE_OP_CALL, RET = PURE_OP_RETURN, CHAT = PURE_OP_CHAR_AT, CHAR_ = PURE_OP_CHAR, FN_TEXT = 1, FN_I64 = 3, + FN_LIST = 4 }; +#define I64_LOCAL(slot) ((uint32_t)(slot) | 3u << 8) +#define WALK_OF(list, length) ((uint32_t)(list) << 8 | (uint32_t)(length) << 16) +#define LIST_LOCAL(slot, record) ((uint32_t)(slot) | 4u << 8 | (uint32_t)(record) << 16) +static void functions_and_characters(void) { + static const S nums[] = {{"n", 0}}; + static const RF leaf_fields[] = {{"v", 3, 0}}; + static const RF node_fields[] = {{"v", 3, 0}, {"kids", 4, 1}}; /* kids: a list of Node */ + static const R records[] = {{"Leaf", leaf_fields, 1}, {"Node", node_fields, 2}}; + enum { IV = 1, SAID, OWN, NODES, KIDS, R_, STORED, NONE }; + static const T others[] = {{"i", PURE_STATE_I64, 0}, {"said", 1, 0}, {"let.own", 3 | (uint32_t)PURE_LIST_ROWS << 8, 0}, + {"let.nodes", 3 | (uint32_t)PURE_LIST_ROWS << 8, 1}, {"let.kids", 3 | (uint32_t)PURE_LIST_ROWS << 8, 1}, + {"let.r", 3 | (uint32_t)(PURE_LIST_ROWS | PURE_LIST_BOUND) << 8, 1}, {"stored", 3, 0}, + {"let.none", 3 | (uint32_t)PURE_LIST_ROWS << 8, 1}}; + static const char *const constants[] = {"", "a\xc3\xa9\xe2\x82\xac\xf0\x9f\x98\x80"}; /* a รฉ โฌ ๐ */ + static const I inputs[] = {KEY("fib", "KeyF"), KEY("tree", "KeyT"), KEY("own", "KeyO"), KEY("held", "KeyH"), + KEY("chars", "KeyC"), KEY("deep", "KeyD")}; + enum { LS_ = PURE_OP_LOCAL_STORE, LL_ = PURE_OP_LOCAL_LOAD }; + const O code[] = { + /* 0 fib(n): n < 2 ? n : fib(n - 1) + fib(n - 2) */ + {LS_, I64_LOCAL(0), 0}, {LL_, I64_LOCAL(0), 0}, IC(2), {ICMP, PURE_LESS, 0}, {JZ, 7, 0}, + {LL_, I64_LOCAL(0), 0}, {RET, 0, 0}, + {LL_, I64_LOCAL(0), 0}, IC(1), {ISUB, 0, 0}, {CALL, 0, 0}, {LL_, I64_LOCAL(0), 0}, IC(2), {ISUB, 0, 0}, {CALL, 0, 0}, + {IADD, 0, 0}, {RET, 0, 0}, + /* 17 sum(xs): the v of every node in xs and under it, by a walk of its register that calls itself */ + {BIND, R_, 0}, IC(0), {LS_, I64_LOCAL(0), 0}, {EACH, WALK_OF(R_, 9), 0}, + {LL_, I64_LOCAL(0), 0}, {ROW, R_, 0}, {IG, ITEM(R_, 0), 0}, {IADD, 0, 0}, {ROW, R_, 0}, {IG, ITEM(R_, 1), 0}, {CALL, 1, 0}, + {IADD, 0, 0}, {LS_, I64_LOCAL(0), 0}, + {LL_, I64_LOCAL(0), 0}, {RET, 1, 0}, + /* 32 own(n): own.append(n); n == 0 ? own.count : own(n - 1) * 10 + own.count (each call's own list holds one) */ + {LS_, I64_LOCAL(0), 0}, {LL_, I64_LOCAL(0), 0}, {LA, OWN, 0}, {LL_, I64_LOCAL(0), 0}, IC(0), {ICMP, PURE_EQUAL, 0}, + {JZ, 42, 0}, {LC, OWN, 0}, {IFROM, 0, 0}, {RET, 2, 0}, + {LL_, I64_LOCAL(0), 0}, IC(1), {ISUB, 0, 0}, {CALL, 2, 0}, IC(10), {IMUL, 0, 0}, {LC, OWN, 0}, {IFROM, 0, 0}, {IADD, 0, 0}, + {RET, 2, 0}, + /* 52 held(t, k): s = t + "k"; k == 0 ? s : held(s, k - 1) + s (each call's s its own) */ + {LS_, I64_LOCAL(0), 0}, {LL_, I64_LOCAL(0), 0}, {NTX, 2, 0}, {CAT, 0, 0}, {HST, 16, 0}, + {LL_, I64_LOCAL(0), 0}, IC(0), {ICMP, PURE_EQUAL, 0}, {JZ, 63, 0}, {HLD, 16, 0}, {RET, 3, 0}, + {HLD, 16, 0}, {LL_, I64_LOCAL(0), 0}, IC(1), {ISUB, 0, 0}, {CALL, 3, 0}, {HLD, 16, 0}, {CAT, 0, 0}, {RET, 3, 0}, + /* 71 deep(n): deep(n + 1), never returning */ + IC(1), {IADD, 0, 0}, {CALL, 4, 0}, {RET, 4, 0}, + /* 75 handler fib: i = fib(20) */ + IC(20), {CALL, 0, 0}, {ST, IV, 0}, + /* 78 handler tree: kids = [4, 1 [2 [4], 3]]; i = sum(kids) + r[0].v, r bound by the handler around the calls */ + IC(4), {LV, NONE, 0}, {LA, KIDS, 0}, IC(2), {LV, KIDS, 0}, {LA, NODES, 0}, IC(3), {LV, NONE, 0}, {LA, NODES, 0}, + {LV, NONE, 0}, {CALL, 1, 0}, {ST, IV, 0}, /* sum of nothing: 0 */ + IC(1), {LV, NODES, 0}, {LA, KIDS, 0}, {LV, KIDS, 0}, {BIND, R_, 0}, + {LV, KIDS, 0}, {LS_, LIST_LOCAL(0, 1), 0}, {LL_, LIST_LOCAL(0, 1), 0}, {CALL, 1, 0}, /* by way of a local */ + {XF, R_, 0}, {IG, ITEM(R_, 0), 0}, {IADD, 0, 0}, {ST, IV, 0}, /* 14 + 4 */ + /* 103 handler own: own = [7]; i = own(3); n = own.count */ + IC(7), {LA, OWN, 0}, IC(3), {CALL, 2, 0}, {ST, IV, 0}, {LC, OWN, 0}, {ST, 0, 0}, + /* 110 handler held: said = held("", 2) */ + {TK, 0, 0}, IC(2), {CALL, 3, 0}, {PURE_OP_TEXT_SET, SAID, 0}, + /* 114 handler chars: i = the code points at 0, 1, 3 and 6, packed; said = char(...) joined, the constant again */ + {TK, 1, 0}, IC(0), {CHAT, 0, 0}, {TK, 1, 0}, IC(1), {CHAT, 0, 0}, {IADD, 0, 0}, {TK, 1, 0}, IC(3), {CHAT, 0, 0}, + {IADD, 0, 0}, {TK, 1, 0}, IC(6), {CHAT, 0, 0}, {IADD, 0, 0}, {ST, IV, 0}, + IC(0x61), {CHAR_, 0, 0}, IC(0xE9), {CHAR_, 0, 0}, {CAT, 0, 0}, IC(0x20AC), {CHAR_, 0, 0}, {CAT, 0, 0}, IC(0x1F600), {CHAR_, 0, 0}, + {CAT, 0, 0}, {PURE_OP_TEXT_SET, SAID, 0}, + /* 142 handler deep: own = [5]; deep(0) */ + IC(5), {LA, OWN, 0}, IC(0), {CALL, 4, 0}, {ST, IV, 0}, + }; + static const FN fns[] = {{0, 17, 1, 1, {FN_I64, FN_I64}, {0}}, {17, 15, 1, 1, {FN_LIST, FN_I64}, {1, 0}}, + {32, 20, 1, 1, {FN_I64, FN_I64}, {0}}, {52, 19, 2, 1, {FN_TEXT, FN_I64, FN_TEXT}, {0}}, + {71, 4, 1, 1, {FN_I64, FN_I64}, {0}}}; + static const H handlers[] = {{1, 75, 3}, {3, 78, 25}, {5, 103, 7}, {7, 110, 4}, {9, 114, 28}, {11, 142, 5}}; + CHECK(LEN(code) == 147); + Spec spec = {nums, 1, inputs, LEN(inputs), NULL, 0, handlers, LEN(handlers), code, LEN(code), NULL, 0, + others, LEN(others), constants, LEN(constants), NULL, 0, records, 2, NULL, 0}; + if (load_functions(spec, fns, LEN(fns), &module_b) != PURE_OK) { fprintf(stderr, "functions: %s\n", error); abort(); } + CHECK(module_b.function[2].lists == UINT32_C(1) << OWN && module_b.function[1].registers == UINT32_C(1) << R_ && + module_b.function[3].held == UINT32_C(1) << 16 && module_b.runner == 2); + PureApp app; + CHECK(pure_app_start(&app, &module_b, (PureData){0}) == PURE_OK); + for (int round = 0; round < 3; ++round) { /* the frames' room used again, each event alike */ + CHECK(pure_app_input(&app, 0, PURE_EDGE_DOWN) == PURE_OK && app.values[IV].i64 == 6765); + CHECK(pure_app_input(&app, 1, PURE_EDGE_DOWN) == PURE_OK && app.values[IV].i64 == 18); + CHECK(pure_app_input(&app, 2, PURE_EDGE_DOWN) == PURE_OK && app.values[IV].i64 == 1111 && app.values[0].num == 1); + CHECK(pure_app_input(&app, 3, PURE_EDGE_DOWN) == PURE_OK && !strcmp(state_text(&app, SAID), "210212")); + CHECK(pure_app_input(&app, 4, PURE_EDGE_DOWN) == PURE_OK && app.values[IV].i64 == 0x61 + 0xE9 + 0x20AC + 0x1F600 && + !strcmp(state_text(&app, SAID), constants[1])); + } + /* A call without end: the room runs out (MEMORY) where the work does not; with a smaller work budget, WORK. Either + * way nothing changed, and the lists are the app's own again. */ + uint64_t before = (uint64_t)app.values[IV].i64; + CHECK(pure_app_input(&app, 5, PURE_EDGE_DOWN) == PURE_BUDGET && app.fault == PURE_FAULT_MEMORY); + CHECK((uint64_t)app.values[IV].i64 == before && pure_list_count(app.lists[OWN]) == 0 && app.calls.at == 0 && !app.calls.used); + pure_app_work(&app, 100000); + CHECK(pure_app_input(&app, 5, PURE_EDGE_DOWN) == PURE_LIMIT && app.fault == PURE_FAULT_WORK); + CHECK(pure_app_input(&app, 2, PURE_EDGE_DOWN) == PURE_OK && app.values[IV].i64 == 1111 && app.values[0].num == 1); + pure_app_stop(&app); + /* Characters that fail: within one (รฉ at 2), past the end, a surrogate, past U+10FFFF, below 0. */ + const O chars_bad[][3] = {{{TK, 1, 0}, IC(2), {CHAT, 0, 0}}, {{TK, 1, 0}, IC(10), {CHAT, 0, 0}}, + {IC(0xD800), {CHAR_, 0, 0}, {PURE_OP_TEXT_SET, SAID, 0}}, {IC(0x110000), {CHAR_, 0, 0}, {PURE_OP_TEXT_SET, SAID, 0}}, + {IC(-1), {CHAR_, 0, 0}, {PURE_OP_TEXT_SET, SAID, 0}}}; + static const PureFault chars_fault[] = {PURE_FAULT_LIMIT, PURE_FAULT_LIMIT, PURE_FAULT_ENCODING, PURE_FAULT_LIMIT, PURE_FAULT_LIMIT}; + for (size_t k = 0; k < LEN(chars_bad); ++k) { + O one[4] = {chars_bad[k][0], chars_bad[k][1], chars_bad[k][2], {ST, IV, 0}}; + H go = {1, 0, chars_bad[k][2].op == CHAT ? 4 : 3}; + Spec bad = {nums, 1, inputs, 1, NULL, 0, &go, 1, one, LEN(one), NULL, 0, others, LEN(others), constants, LEN(constants), + NULL, 0, records, 2, NULL, 0}; + if (load(bad, &module_a) != PURE_OK) { fprintf(stderr, "chars %zu: %s\n", k, error); abort(); } + CHECK(pure_app_start(&app, &module_a, (PureData){0}) == PURE_OK); + CHECK(pure_app_input(&app, 0, PURE_EDGE_DOWN) != PURE_OK && app.fault == chars_fault[k]); + pure_app_stop(&app); + } + /* Refused: no return; a result of another type; code after a return; RETURN outside a function; a call with an + * argument of another type, in a view, or changing a list a walk around it walks; a message's field in a function; + * a loop above values; a signature's type or record. */ + const struct { O code[6]; uint32_t count; FN fn; const char *why; } refused[] = { + {{IC(1), {ST, IV, 0}}, 2, {0, 2, 0, 0, {0}, {0}}, "function ends without return"}, + {{{C, 0, 1}, {RET, 0, 0}}, 2, {0, 2, 0, 1, {FN_I64}, {0}}, "operand type"}, + {{{RET, 0, 0}, {C, 0, 0}}, 2, {0, 2, 0, 0, {0}, {0}}, "unreachable instruction"}, + {{{C, 0, 1}, {CALL, 0, 0}, {RET, 0, 0}}, 3, {0, 3, 1, 0, {FN_I64}, {0}}, "operand type"}, + {{IC(1), {LA, STORED, 0}, {RET, 0, 0}}, 3, {0, 3, 0, 0, {0}, {0}}, NULL}, + {{{PURE_OP_FIELD, 0, 0}, {RET, 0, 0}}, 2, {0, 2, 0, 0, {0}, {0}}, "message operation outside a message handler"}, + {{IC(0), IC(1), IC(0), IC(1), {PURE_OP_LOOP, PURE_LOOP_INTEGER, 0}, {RET, 0, 0}}, 6, + {0, 6, 0, 0, {0}, {0}}, "loop above values"}, + {{{RET, 0, 0}}, 1, {0, 1, 0, 0, {6}, {0}}, "function signature"}, + }; + for (size_t k = 0; k < LEN(refused); ++k) { + FN fn = refused[k].fn; + if (k == 7) fn.params = 1; + O all[12]; + uint32_t n = refused[k].count; + memcpy(all, refused[k].code, n * sizeof(O)); + H go = {1, n, 1}; + all[n] = (O){C, 0, 0}; /* a handler that stores nothing: C, ST */ + all[n + 1] = (O){ST, 0, 0}; + go.length = 2; + if (k == 4) { /* the call in a walk of the list it appends to */ + all[n] = (O){EACH, WALK_OF(STORED, 1), 0}, all[n + 1] = (O){CALL, 0, 0}; + } + Spec bad = {nums, 1, inputs, 1, NULL, 0, &go, 1, all, n + 2, NULL, 0, others, LEN(others), constants, LEN(constants), + NULL, 0, records, 2, NULL, 0}; + const char *why = refused[k].why ? refused[k].why : "call that changes a list walked"; + if (load_functions(bad, &fn, 1, &module_a) == PURE_OK || !strstr(error, why)) { + fprintf(stderr, "functions: refused %zu: %s\n", k, error); + abort(); + } + } + static const O in_view[] = {{CALL, 0, 0}, {RET, 0, 0}, {RET, 0, 0}}; + static const V call_view[] = {{"v", 0, 1}}; + static const FN nothing = {1, 1, 0, 0, {0}, {0}}; + Spec viewed = {nums, 1, inputs, 1, call_view, 1, NULL, 0, in_view, 2, NULL, 0, others, LEN(others), constants, LEN(constants), + NULL, 0, records, 2, NULL, 0}; + CHECK(load_functions(viewed, ¬hing, 1, &module_a) != PURE_OK && strstr(error, "call outside a handler or a function")); + static const H returning = {1, 2, 1}; + Spec handler_return = {nums, 1, inputs, 1, NULL, 0, &returning, 1, in_view, 3, NULL, 0, others, + LEN(others), constants, LEN(constants), NULL, 0, records, 2, NULL, 0}; + CHECK(load_functions(handler_return, ¬hing, 1, &module_a) != PURE_OK && strstr(error, "return outside a function")); + /* A handler's loop above values: its block would begin above them (once past the run's stack). */ + const O above[] = {IC(0), IC(0), IC(1), {PURE_OP_LOOP, PURE_LOOP_INTEGER, 0}, {ST, IV, 0}}; + static const H whole = {1, 0, 5}; + Spec looped = {nums, 1, inputs, 1, NULL, 0, &whole, 1, above, LEN(above), NULL, 0, others, LEN(others), constants, + LEN(constants), NULL, 0, records, 2, NULL, 0}; + CHECK(load(looped, &module_a) != PURE_OK && strstr(error, "loop above values")); + printf("{\"functions_and_characters\":{\"rounds\":3,\"refused\":%zu}}\n", LEN(refused) + 3); +} + /* A timer's tick sees the time the host set; floor and a floored modulo * take it apart. now is for handlers only. */ enum { NOW = PURE_OP_NOW, FLOOR = PURE_OP_FLOOR, MOD = PURE_OP_MOD }; @@ -6694,6 +6879,7 @@ int main(void) { bits_and_bytes(); formats_and_held(); lists_in_records(); + functions_and_characters(); memory_budget(); work_budget(); fold_mutations(); diff --git a/docs/design/008-module-format.md b/docs/design/008-module-format.md index 642da9b..4c561f8 100644 --- a/docs/design/008-module-format.md +++ b/docs/design/008-module-format.md @@ -24,7 +24,8 @@ v6์๋ ๋ค์ **i64**๊ฐ ๋ํด์ก๋ค([016](016-bool-and-i64.md)์ 2๋จ๊ณ): ๊ทธ ๋ค [027](027-computation-core.md)์ 1๋จ๊ณ๋ก **๋นํธ ์ฐ์ฐ, ์๋ฆฌ์ ๋ฐ์ดํธ, i64 ๋ฆฌ์คํธ์ ๋ฐ์ดํธ, ์๋ฆฌ๋ก ์ฐพ์ ํญ๋ชฉ**์ด ๋ํด์ก๋ค(์ ๋ช
๋ น ๋ท, 90โ93). 2a๋ก **๋ฐ์ดํธ ์๋ฅด๊ธฐ, ํ ๋ฐ์ดํธ, ์ด๋ฆ์ผ๋ก ๋ด์ ๋ฐ์ดํธ์ text**(94โ97), CONCAT์ ๋ฐ์ดํธ, NUM_TEXT์ ํ์์ด ๋ํด์ก๋ค. 2b๋ก **๋ ์ฝ๋ ์์ ๋ฆฌ์คํธ**(๋ ์ฝ๋ ํ๋์ ํ์
4, 98โ100), ๋ ์ง์คํฐ(๋ฆฌ์คํธ ์ํ์ ํ๋๊ทธ 512), ๊ฒฝ๋ก ์ด๋ฆ์ ๋ ์ฝ๋ ํ๋, **์ ์ฝ๊ธฐ**(101)๊ฐ -๋ํด์ก๋ค. ํ์ ๊ทธ๋๋ก๋ค. +๋ํด์ก๋ค. 2c๋ก **ํจ์**(CALLยทRETURN, 102โ103, ๋จธ๋ฆฌ๋ง์ ํจ์ ์์ ํจ์ ํ)์ **๊ธ์**(CHAR_ATยทCHAR, 104โ105)๊ฐ ๋ํด์ก๋ค. ํ์ +๊ทธ๋๋ก๋ค(0์ด๋ ๋จธ๋ฆฌ๋ง ์๋ฆฌ์ ํจ์ ์, ํจ์๊ฐ ์๋ ๋ชจ๋์ ๋ฐฐ์น๊ฐ ๊ฐ๋ค). **๋ ์ฝ๋ ์์ ๋ฆฌ์คํธ**(027์ 2b). - ๋ ์ฝ๋ ํ๋์ ํ์
4(LIST)๋ ํญ๋ชฉ๋ค์ ๋ ์ฝ๋๋ฅผ ๊ธฐ๋ณธ๊ฐ ์๋ฆฌ(i64)์ ๋๋ค. @@ -38,6 +39,15 @@ v6์๋ ๋ค์ **i64**๊ฐ ๋ํด์ก๋ค([016](016-bool-and-i64.md)์ 2๋จ๊ณ): ์ฝ๊ธฐ๋ง ํ๋ค. - ๋ ์ฝ๋ ํ๋์ ์ด๋ฆ์ ๊ฒฝ๋ก์ผ ์ ์๋ค(`at.x`). ํผ์น ๋ ์ฝ๋ ์์ ๋ ์ฝ๋๋ค. +**ํจ์**(027์ 2c). +- ํจ์๋ CALL์ด ๋๋ ๋ธ๋ก์ด๋ค. ๋ถ๋ฅด๋ ์ชฝ ์คํ์ ์ธ์๋ค์ด ๊ทธ ๋ธ๋ก์ ์ฒซ ์คํ(๋งค๊ฐ๋ณ์์ ํ์
)์ด ๋๊ณ , RETURN์ด ๋งจ ์์ ๊ฒฐ๊ณผ๋ค์ + ๋ด๋ฉฐ ๋๋๋ค(์คํ์ ๋๋จธ์ง๋ ๋ฒ๋ฆฐ๋ค). ๊ฒฐ๊ณผ๋ ๋ถ๋ฅด๋ ์ชฝ ์คํ์์ ์ธ์์ ์๋ฆฌ๋ฅผ ๊ฐ๋๋ค. +- ๋ถ๋ฆ๋ง๋ค ์ ๊ฒ์ด ์๋ค. ์คํ๊ณผ ์ง์ญ ์นธ(0์์ ์์)์ด ๊ทธ๋ ๊ณ , ํจ์์ ์ฝ๋๊ฐ ์ด๋ฆ์ ๋๋ ๊ฒ๋ ๊ทธ๋ ๋ค. ์ด๋ฆ์ผ๋ก ๋ด์ ๊ฐ(๋น์ด + ์์), ์ด๋ฒคํธ์ ๋ฆฌ์คํธ(๋น์ด ์์), ๋ ์ง์คํฐ(์๋ฌด๊ฒ์๋ ๋ฌถ์ด์ง ์๊ณ ์์)๋ค. ๋ถ๋ฅด๋ ์ชฝ์ ๊ฒ์ ๋ถ๋ฆ์ด ๋์์ฌ ๋ ๊ทธ๋๋ก๋ค. +- ํจ์์ ์ฝ๋๋ ๋ฉ์์ง๊ฐ ์๋ ํธ๋ค๋ฌ์ ์ฝ๋๋ค(ํ๋, ๋ฌธ์, ์๋ต์ด ์๋ค). ์ํ๋ฅผ ๋ฐ๊ฟ ์ ์๋ค. CALL์ ํธ๋ค๋ฌ์ ํจ์์ ์ฝ๋์๋ง + ์๋ค(๋ณด๊ธฐ์๋ ์๋ค). +- ๋ถ๋ฆ์ ๊น์ด๋ ์ด๋ฒคํธ์ ๋ชซ์ด ๋ฌถ๋๋ค. ๋ถ๋ฆ๋ง๋ค ๊ทธ ํ๋ ์์ ๋ฐ์ดํธ๋ฅผ ๋ชซ์ ์ธ๊ณ (๋์ผ๋ฉด `memory`), ๋ธ๋ก ๊ธธ์ด๋ฅผ ์คํ๋์ ์ผ๋ค. + ## ๋ฐ์ดํธ ๋ฐฐ์น ๋ชจ๋ ์ ์๋ little-endian์ด๊ณ , ์ค์๋ IEEE binary64 ๋นํธ ๊ทธ๋๋ก๋ค. @@ -48,7 +58,7 @@ v6์๋ ๋ค์ **i64**๊ฐ ๋ํด์ก๋ค([016](016-bool-and-i64.md)์ 2๋จ๊ณ): | 8 | u16 ์ํ, u16 ์
๋ ฅ, u16 ๋ณด๊ธฐ, u16 ํธ๋ค๋ฌ | | 16 | u32 ๋ช
๋ น ์, u32 ๋ฌธ์์ด ๋ฐ์ดํธ ์ | | 24 | u16 ํ๋, u16 ์ปฌ๋ ์
, u16 ์์, u16 ๋ ์ฝ๋ | -| 32 | u32 ์์ ๋ธ๋กญ ๋ฐ์ดํธ ์, u16 ๋ ์ฝ๋ ํ๋, u16 0 | +| 32 | u32 ์์ ๋ธ๋กญ ๋ฐ์ดํธ ์, u16 ๋ ์ฝ๋ ํ๋, u16 ํจ์ | | 40 | ์ํ ร 16 B: u32 ์ด๋ฆ, u32 ํ์
(๋นํธ 0โ7: 0 ์, 1 text, 2 ์ปค์, 3 ๋ฆฌ์คํธ, 4 ์ธ๋ฑ์ค, 5 bool, 6 i64. ๋นํธ 8: ์ ์ฅํ์ง ์๋ ์ํ(transient, [018](018-lifetimes-and-computation.md)), ๊ทธ ์๋ 0. ๋ฉ์์ง์ ํ ๋ชฉ๋ก์ transient๊ฐ ์๋๊ณ , transient text๋ ๋ฆฌ์คํธ๋ฅผ ๊ฐ๋ฆฌํค๋ ์ปค์์ ์ธ๋ฑ์ค๋ transient๋ค), 8 B ๊ฐ: ์์ bool์ f64 ์ด๊ธฐ๊ฐ(bool์ 0์ด๋ 1), i64๋ ์ด๊ธฐ๊ฐ(๋ถํธ ์๋ little-endian), text๋ u32 ์ด๊ธฐ ์์, ์ปค์๋ u32 ๋์ text ์ํ์ u32 ํ๋๊ทธ(1์ด๋ฉด ๋งํฌ: ๊ทธ ์๋ฆฌ์ ๋ฃ์ ๊ธ ์์ ๋จ๋๋ค), ๋ฆฌ์คํธ๋ u32 ๋ ์ฝ๋์ u32 ํค(0์ด๋ฉด ์์, ์๋๋ฉด ํค ํ๋ + 1, 256์ด๋ฉด ๋ฉ์์ง์ ํ ๋ชฉ๋ก: ์ด๋ฆ์ ๊ทธ ํ๋์ ๊ฒฝ๋ก `์
๋ ฅ.ํ๋`์ด๊ณ ํค๊ฐ ์๋ค), ์ธ๋ฑ์ค๋ u32 ๋์ ๋ฆฌ์คํธ ์ํ | | | ์ปฌ๋ ์
ร 12 B: u32 ์ด๋ฆ, u32 1(๋ฐ์ดํธ), u32 1(ํค๋ณ) | | | ์
๋ ฅ ร 16 B: u32 ์ด๋ฆ, u8 ์ข
๋ฅ(1 ํค, 2 ๋ฉ์์ง, 3 text, 4 ํ์ด๋จธ, 5 ์ถ๋ ฅ: ์ฑ์ด ๋ณด๋ด๋ ๋ฉ์์ง, ๋ชจ์์ ๋ฉ์์ง์ ๊ฐ๊ณ ํธ๋ค๋ฌ๊ฐ ์๋ค, 6 ์ธ์: ํ ๋ณด๊ธฐ๊ฐ ๋ฐ๋ ์ธ์, ๋ชจ์์ ๋ฉ์์ง์ ๊ฐ๊ณ ํธ๋ค๋ฌ๊ฐ ์์ผ๋ฉฐ ์ด๋ฆ์ `๋ณด๊ธฐ.args`), u8 ํค๋ณ ์ฌ๋ถ, u16 0, u32 ํค ์ด๋ฆ(ํค ์
๋ ฅ)ยท์ฃผ๊ธฐ(ํ์ด๋จธ, 1 msโ24์๊ฐ์ ms๋ก)ยท๋ณด๊ธฐ ๋ฒํธ(์ธ์) ๋๋ 0, u16 ์ฒซ ํ๋, u16 ํ๋ ์ | @@ -58,6 +68,8 @@ v6์๋ ๋ค์ **i64**๊ฐ ๋ํด์ก๋ค([016](016-bool-and-i64.md)์ 2๋จ๊ณ): | | ๋ ์ฝ๋ ํ๋ ร 16 B: u32 ์ด๋ฆ, u32 ํ์
(0 ์, 1 text, 2 bool, 3 i64), 8 B ๊ธฐ๋ณธ๊ฐ: ์์ bool์ f64(bool์ 0์ด๋ 1), i64๋ ์ ์, text๋ u32 ์์ | | | ๋ณด๊ธฐ ร 16 B: u32 ์ด๋ฆ, u8 ํ์
(0 ์, 1 text, 2 ํ, 3 bool, 4 i64), u8 ๊ฑธ๋ฌ์ง ํ์ ๋ฆฌ์คํธ ์ํ + 1(๊ทธ ๋ฐ์๋ 0), u16 ํ(์ด์ด๋ฉด ๊ทธ ํ ๋ณด๊ธฐ + 1, ์๋๋ฉด 0), u32 ์์ ๋ช
๋ น, u32 ๋ช
๋ น ์. ํ๋ ์์ ๋ช
๋ น ์๋ฆฌ์ ๋ฆฌ์คํธ ์ํ, ๋ช
๋ น ์ 0. ๊ฑธ๋ฌ์ง ํ๋ ํ์
๋ค์ ๋ฐ์ดํธ์ ๋ฆฌ์คํธ ์ํ + 1, ์์ยท๋ช
๋ น ์์ ํํฐ ๋ธ๋ก | | | ํธ๋ค๋ฌ ร 12 B: u32 ์ด๋ฒคํธ, u32 ์์ ๋ช
๋ น, u32 ๋ช
๋ น ์ | +| | ํจ์ ร 12 B: u32 ์์ ๋ช
๋ น, u32 ๋ช
๋ น ์, u8 ๋งค๊ฐ๋ณ์ ์, u8 ๊ฒฐ๊ณผ ์, u16 0 | +| | ์๋ช
ํญ๋ชฉ ร 4 B: ํจ์๋ง๋ค ๋งค๊ฐ๋ณ์, ๊ทธ๋ค์ ๊ฒฐ๊ณผ์ ์ฐจ๋ก๋ก. u8 ํ์
(๋ ์ฝ๋ ํ๋์ ํ์
: 0 ์, 1 text, 2 bool, 3 i64, 4 ๋ฆฌ์คํธ, ๊ทธ๋ฆฌ๊ณ 5 ๋ฐ์ดํธ), u8 0, u16 ๋ฆฌ์คํธ์ ๋ ์ฝ๋(๊ทธ ๋ฐ์๋ 0) | | | ๋ช
๋ น ร 16 B: u8 opcode, 0 3๋ฐ์ดํธ, u32 ์ธ์, f64 ๊ฐ | | | ๋ฌธ์์ด: `[u8 ๊ธธ์ด][๋ฐ์ดํธ]`์ ์ฐ์ | | | ์์ ๋ธ๋กญ (์ต๋ 8 KiB) | @@ -153,6 +165,10 @@ v6์๋ ๋ค์ **i64**๊ฐ ๋ํด์ก๋ค([016](016-bool-and-i64.md)์ 2๋จ๊ณ): | 99 | LIST_BIND | l โ | ๋ฌถ์ด๋ ๋ฆฌ์คํธ ์ํ `์ธ์`(๋ ์ง์คํฐ)๊ฐ ๊ทธ ๋ฆฌ์คํธ๋ฅผ ์ฝ๊ฒ ํ๋ค | | 100 | APPEND_IN | i fโฆ โ | ๋ฆฌ์คํธ ์ํ `์ธ์`์ ๋นํธ 0โ15(์ด๋ฒคํธ์ ๋ฆฌ์คํธ)์์ ์ธ๋ฑ์ค์ ํญ๋ชฉ, ๊ทธ ํ๋(๋นํธ 16โ31, ๋ฆฌ์คํธ ํ๋)์ ๋ด๊ธด ๋ฆฌ์คํธ์ ํญ๋ชฉ์ ๋ง๋ถ์ธ๋ค. ๊ทธ ๋ฆฌ์คํธ๋ฅผ ๋ค๋ฅธ ๊ฐ์ด ๋๋ ๊ฐ์ง๋ฉด ๋จผ์ ์ ๊ฒ์ผ๋ก ๋ณต์ฌํ๋ค | | 101 | NUM_PARSE | t โ n | JSON์ ์๋ก ์ด text์ ๊ฐ์ฅ ๊ฐ๊น์ด ์. ๊ทธ๋ฐ text๊ฐ ์๋๊ฑฐ๋ ์ ํํ์ง ์์ผ๋ฉด `limit` | +| 102 | CALL | aโฆ โ rโฆ | ํจ์ `์ธ์`๋ฅผ ๋ถ๋ฅธ๋ค. ๋งค๊ฐ๋ณ์๋ฅผ ๊บผ๋ด๊ณ ๊ฒฐ๊ณผ๋ฅผ ๋๋๋ค. ์ "ํจ์" | +| 103 | RETURN | โฆ rโฆ โ | ํจ์ `์ธ์`(์์ )๋ฅผ ๋๋ธ๋ค. ๋งจ ์์ ๊ฒฐ๊ณผ๊ฐ ๋ถ๋ฅธ ์ชฝ์ผ๋ก ๊ฐ๋ค | +| 104 | CHAR_AT | t q โ q | text์ ๋ฐ์ดํธ ์๋ฆฌ q(i64)์์ ์์ํ๋ ๊ธ์์ ์ฝ๋ ํฌ์ธํธ(i64). ๊ธ์๊ฐ ์์ํ์ง ์๋ ์๋ฆฌ๋ ๋ฐ์ด๋ฉด `limit` | +| 105 | CHAR | q โ t | ์ฝ๋ ํฌ์ธํธ ํ๋์ text. 0โ0x10FFFF ๋ฐ์ด๋ฉด `limit`, ์๋ก๊ฒ์ดํธ๋ฉด `encoding` | bool์ ์คํ ์ค์ ์์ ์นธ์ ๋ 0์ด๋ 1์ด๊ณ , i64๋ ๊ฐ์ 8๋ฐ์ดํธ์ ์ ์๋ค. CONST์ ์ธ์ 2๋ i64 ์์(๊ฐ์ 8๋ฐ์ดํธ), NUM_TEXT์ ์ธ์ 2๋ i64์ 10์ง ๊ธ์๋ค. LOADยทSTOREยท์ง์ญ ์นธยทํญ๋ชฉยทFIELDยทSEND๋ i64๋ฅผ ์์ฒ๋ผ ์ฎ๊ธด๋ค. FOLD์ ์ข
๋ฅ์ 64(PURE_FOLD_INTEGER)๋ฅผ @@ -212,6 +228,13 @@ bool์ ์คํ ์ค์ ์์ ์นธ์ ๋ 0์ด๋ 1์ด๊ณ , i64๋ ๊ฐ์ 8๋ฐ์ด๏ฟฝ (์ฝ๊ธฐ๋ฟ: ์๋ต๊ณผ ๋ฌธ์ ์ฐ์ฐ์ ํธ๋ค๋ฌ ์์ ์ ์ฝ๋์๋ง ์๋ค). - ํ๋ ๋ฆฌ์คํธ ์ํ๋ฅผ ๊ฐ๋ฆฌํค๊ณ ์ด์ ์์ ๋์จ ํ๋ฅผ ๊ฐ๋ฆฌํจ๋ค. ํ ๋ฐ์ ์ด๋ฆ์ ํ ์ด๋ฆ๊ณต๊ฐ์ด๊ณ , ์ด ์ด๋ฆ์ ํ ์์์๋ง ์ ์ผํ๋ค. +- ๋ฐ๋ณต(LOOP, EACH)์ ์ ํผ์ฐ์ฐ์ ๋ง๊ณ ๋ ๋น ์คํ์์ ์ฐ๋ค. ๋ฐ๋ณต์ ๋ธ๋ก์ ๊ทธ ์คํ์ ์คํ ๋ฐ๋ฅ์์ ์์ํ๋ฏ๋ก, ์๋์ ๊ฐ์ ๋ ๋ฐ๋ณต์ + ์คํ์ 64์นธ์ ๋์ ์ ์์๋ค(๊ฒ์ฆ์ ์ง๋ ๋ชจ๋์ด ์คํ๊ธฐ๋ฅผ ์ฃฝ์๋ค. 2c์์ ์ฐพ์ ๋ง์๋ค). +- ํจ์(2c): ๋ธ๋ก์ ๋งค๊ฐ๋ณ์๋ฅผ ์คํ์ ๋๊ณ ์์ํ๊ณ , ๋ชจ๋ ๊ธธ์ด RETURN์ผ๋ก ๋๋๋ค. RETURN์ ์๊ธฐ ํจ์์ ๊ฒฐ๊ณผ ํ์
์ ๋งจ ์์์ + ๊บผ๋ธ๋ค. ์์ ๋ฐ๋ณต ๋ธ๋ก์ ํธ๋ค๋ฌ์ ์ฝ๋๋ก ๊ฒ์ฆํ๋ค. CALL์ ๋งค๊ฐ๋ณ์์ ํ์
(๋ฆฌ์คํธ๋ ๊ทธ ๋ ์ฝ๋๊น์ง)๋๋ก ๊บผ๋ด๊ณ ๊ฒฐ๊ณผ๋ฅผ ๋๋๋ค. + ๋ก๋ํ ๋ ํจ์๋ง๋ค ๊ทธ ์ฝ๋๊ฐ ์ด๋ฆ์ ๋๋ ์ด๋ฒคํธ์ ๋ฆฌ์คํธ, ๋ ์ง์คํฐ, ๋ด์ ๊ฐ๊ณผ ์ง์ญ ์นธ์ ์, ๋ฐ๋ณต์ ๊น์ด, ์คํ ๋์ด๋ฅผ ์ ๋๋ค. + ๋ ์ด๋ฒคํธ์ ๋ฆฌ์คํธ๊ฐ ์๋ ๋ฆฌ์คํธ ๊ฐ์ด๋ฐ ๊ทธ ํจ์๊ฐ(๊ทธ๊ฒ์ด ๋ถ๋ฅด๋ ํจ์๋ค์ด) ๋ฃ๊ฑฐ๋ ์ง์ฐ๋ ๊ฒ์ ๋ชจ์๋ค. ๋๋ ์ ๊ฑท๊ธฐ๊ฐ ๋๋ ๋ฆฌ์คํธ๋ฅผ + ๋ฐ๊พธ๋ ๋ถ๋ฆ์ ๊ฑฐ์ ํ๋ค(`call that changes a list walked`). ๊ฒ์ฆ๋ ๋ชจ๋์ ์คํ ์ค ์คํยทํ์
๊ฒ์ฌ๊ฐ ํ์ ์๋ค. ์ด๋ฒคํธ ํ๋๊ฐ ๋๋ ๋ช
๋ น ์๋ ์คํ๋ ์์ฐ์ด ๋ฌถ๋๋ค: ์ฑ์ด ์ ํ์ง ์์ผ๋ฉด 2^28 ๋ช
๋ น์ด๋ค(018: ์ธ๋ ๋ฐ๋ณต์ด ๋ค์ด์ ๊ตฌ์กฐ๋ง์ผ๋ก๋ ๋ฌถ์ด์ง ์๋๋ค). ์ง๊ณ์ ๊ฑท๊ธฐ๋ ์์ํ ๋ ๋ธ๋ก ๊ธธ์ด ร ํญ๋ชฉ ์๋ฅผ, LOOP๋ ๋ ๋๋ง๋ค @@ -221,6 +244,14 @@ bool์ ์คํ ์ค์ ์์ ์นธ์ ๋ 0์ด๋ 1์ด๊ณ , i64๋ ๊ฐ์ 8๋ฐ์ด๏ฟฝ ## ์คํ +**๋ถ๋ฆ**(027์ 2c). ํจ์๊ฐ ์๋ ๋ชจ๋์ ๋ธ๋ก์ ๋ถ๋ฆ์ ์๋ ์คํ๊ธฐ(`run_calls`)๊ฐ ๋๋ค. CALL์ ์ฑ์ ํ๋ ์ ๋ธ๋ก(์ฎ๊ฒจ์ง์ง ์๋๋ค: +๋ฐ๋ณต์ด ํ๋ ์ ์์ ๊ฐ๋ฆฌํจ๋ค)์ ํ๋ ์์ ์ฐ๋ค. ๋ถ๋ฅธ ์ชฝ์ ์๋ฆฌ(CALL ๋ค์, ์ฝ๋์ ๋, ๋ฐ๋ณต, ์คํ, ์ง์ญ ์นธ, ๊ฑท๊ธฐ)์, ํจ์๊ฐ ์ด๋ฆ์ +๋๋ ๋ถ๋ฅธ ์ชฝ์ ๋ฆฌ์คํธยท๋ ์ง์คํฐยท๋ด์ ๊ฐ์ ํ๋ ์์ ๋๊ณ , ํจ์์ ๊ฒ์ ์๋ก ์ค๋ค. ์ด๋ฒคํธ์ ๋ฆฌ์คํธ๋ ์์ ๋ถ๋ฆ์ด ๋น์ ๋ ๊ฒ์ ๋ค์ +์ด๋ค. RETURN์ ๊ฒฐ๊ณผ๋ฅผ ๋ถ๋ฅธ ์ชฝ ์คํ์ ๋๊ณ ๋ถ๋ฅธ ์ชฝ์ ๊ฒ์ ๋๋ ค์ค๋ค. ๋ถ๋ฆ ์์์ ๋ฉ์ถ ์คํ์ ์ด๋ฆฐ ํ๋ ์์ ๋ชจ๋ ๋ซ๋๋ค. ๋ถ๋ฅธ ์ชฝ์ +๋ด์ ๊ฐ์ ๊ฐ๋ฆฌํค๋ ์ธ์์ ํจ์์ ๋ด์ ๊ฐ์ ๊ฐ๋ฆฌํค๋ ๊ฒฐ๊ณผ๋ ๊ทธ ๊ฐ์ด ์ฌ๋ผ์ง๊ธฐ ์ ์ ์ด๋ฒคํธ ๊ณต๊ฐ์ผ๋ก ๋ณต์ฌํ๋ค. ํ์ด๋ก๋, ์ธ์, +์์์ ๊ฐ์ ์ด๋ฒคํธ ๋์ ๊ทธ๋๋ก์ด๋ฏ๋ก ์ด๋ฆ์ผ๋ก ๋ด์ ๋ ๋ณต์ฌํ์ง ์๋๋ค(๋ง๋ถ์ผ ๋ ์ฒ์ ๋ณต์ฌํ๋ค). ํจ์๊ฐ ๋ ๋ธ๋ก์ ์ปดํ์ผํ์ง +์๋๋ค(JIT์ ๋ถ๋ฆ์ด ์๋ ๋ธ๋ก๋ง). + `PureApp`์ ๋ชจ๋ ์ฐธ์กฐ, ์ํ ๊ฐ, text ์ํ draft, ๋ฆฌ์คํธ, ์ด๋ฆฐ ์ด๋ฒคํธ ํ๋๋ฅผ ๊ฐ์ง๋ค(3,128 B, `PureModule`์ ์์ ๋ธ๋กญ์ ํฌํจํด 28,600 B). text ์ํ๋ ์ ์ฅ์ ํ์ผ์ด ์๋ draft๋ผ 1 MiB ํ
์คํธ๋ ์กฐ๊ฐ ํธ๋ฆฌ๋ก ํธ์งํ๋ค. ์ปค์๋ ๋ฐ์ดํธ ์์น์ด๋ฉฐ ํญ์ ๊ธ์ ๊ฒฝ๊ณ์ ์๋ค. ๋ฃ๊ธฐ๋ ๊ทธ ์์น ์ดํ์ ์ปค์๋ฅผ ๋ค๋ก(์ฝ์
์์น์ ์ปค์ ํฌํจ, ๋งํฌ๋ ์ ์๋ฆฌ) ๋ฐ๊ณ , ์ง์ฐ๊ธฐ๋ ๋ฒ์ |