diff options
Diffstat (limited to 'core')
| -rw-r--r-- | core/module-list.c | 8 | ||||
| -rw-r--r-- | core/module-list.h | 2 | ||||
| -rw-r--r-- | core/module.c | 157 | ||||
| -rw-r--r-- | core/module.h | 29 | ||||
| -rw-r--r-- | core/test-module.c | 244 |
5 files changed, 393 insertions, 47 deletions
diff --git a/core/module-list.c b/core/module-list.c index 5df66f4..456a72e 100644 --- a/core/module-list.c +++ b/core/module-list.c @@ -492,6 +492,14 @@ void pure_list_free(PureList *list) { free(list); } +void pure_list_clear(PureList *list) { + if (!list->count) return; + let_go_tree(list, list->root); + list->root = NULL; + list->count = 0; + ++list->version; +} + size_t pure_list_count(const PureList *list) { return list->count; } PureList *pure_list_share(PureList *list, PureRetired *retired) { diff --git a/core/module-list.h b/core/module-list.h index 5e724b8..d29fe95 100644 --- a/core/module-list.h +++ b/core/module-list.h @@ -48,6 +48,8 @@ enum { PURE_LIST_ITEMS = 1 << 24, PURE_LIST_RUN = 32 }; PureList *pure_list_new(unsigned fields, const uint8_t *text_fields); void pure_list_free(PureList *); +/* Let every item go (retired where a shared copy may read it). */ +void pure_list_clear(PureList *); size_t pure_list_count(const PureList *); /* Share the items as they are with a read-only copy (for readers on other * threads), without copying them: from then on the list copies the nodes it diff --git a/core/module.c b/core/module.c index 07d98d4..20b1748 100644 --- a/core/module.c +++ b/core/module.c @@ -22,11 +22,12 @@ enum { READ = IN_VIEW | IN_HANDLER }; * depth, a fold, a relation, a keyed list, an output, or the row of the * column a fold runs in. */ enum { A_NONE, A_STATE, A_ITEM = A_STATE + PURE_STATE_INDEX + 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_ROW, A_TARGET, A_DEPTH, A_FOLD, A_RELATION, A_KEYED, A_OUTPUT, A_OUTER, A_EACH }; /* A fold's block is verified as a column that leaves one number (count) or * two (a value and whether to include it), a table's filter as a column that - * leaves one: these stand for a view type. */ -enum { FOLD_ONE = 100, FOLD_TWO, FILTER }; + * leaves one: 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). */ +enum { FOLD_ONE = 100, FOLD_TWO, FILTER, WALK }; /* 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. @@ -102,6 +103,7 @@ static const struct { unsigned char pops, in[3], out, where, arg, of; } signatur [PURE_OP_LIST_HAS] = {1, {T_KEY}, T_NUM, READ, A_KEYED, O_ANY}, [PURE_OP_NOW] = {0, {0}, T_NUM, IN_HANDLER, A_NONE, O_ANY}, [PURE_OP_SEND] = {0, {0}, 0, IN_HANDLER, A_OUTPUT, O_ANY}, + [PURE_OP_EACH] = {0, {0}, 0, IN_HANDLER, A_EACH, O_ANY}, [PURE_OP_FLOOR] = NUMS(1), [PURE_OP_MOD] = NUMS(2), }; #undef NUMS @@ -188,13 +190,14 @@ PURE_COLD static bool names_arg(const PureModule *m, unsigned kind, uint32_t arg switch (kind) { case A_ITEM: return state_of(m, list_of(arg), PURE_STATE_LIST) && item_field(arg) < m->record[m->state_ref[list_of(arg)]].count; - case A_FIELD: return arg < shape->field_count; + case A_FIELD: return arg < shape->field_count && m->field[shape->field_start + arg].type != PURE_FIELD_ROWS; case A_COLLECTION: return arg < m->collections; case A_CONSTANT: return arg < m->constants; case A_UNIT: return arg <= PURE_UNIT_LINE; case A_ROW: return (int)arg == row; case A_OUTER: return outer >= 0 && (int)arg == outer; case A_FOLD: return (arg & 0xFF) <= PURE_FOLD_FIRST && state_of(m, arg >> 8 & 0xFF, PURE_STATE_LIST) && arg >> 16; + case A_EACH: return !(arg & 0xFF) && state_of(m, arg >> 8 & 0xFF, PURE_STATE_LIST) && arg >> 16; case A_RELATION: return arg <= PURE_NOT_EQUAL; case A_KEYED: return state_of(m, arg, PURE_STATE_LIST) && m->state_key[arg]; case A_OUTPUT: return arg < m->inputs && m->input[arg].kind == PURE_KIND_OUTPUT; @@ -230,11 +233,12 @@ PURE_COLD static const char *verify_block(const PureModule *, PureBlock, int vie PURE_COLD static const char *verify_code(const PureModule *m, PureBlock block, int view, int row, int outer, uint32_t event, uint32_t *at, unsigned char *target) { #define REFUSE(why) do { *at = pc; return why; } while (0) - if (view >= 0 && !block.length) return "empty view"; - int input = view >= 0 ? -1 : event_input(event); + bool handler = view < 0 || view == WALK, folding = view == FOLD_ONE || view == FOLD_TWO; + if (!handler && !block.length) return "empty view"; + int input = handler ? event_input(event) : -1; const PureInputShape *shape = input >= 0 ? &m->input[input] : NULL; - unsigned where = view >= 0 ? IN_VIEW | (row >= 0 ? IN_ROW : 0) | (view >= FOLD_ONE && outer >= 0 ? IN_OUTER : 0) - : IN_HANDLER; + unsigned where = !handler ? IN_VIEW | (row >= 0 ? IN_ROW : 0) | (folding && outer >= 0 ? IN_OUTER : 0) + : IN_HANDLER | (view == WALK ? IN_ROW : 0); if (shape && shape->kind == PURE_KIND_MESSAGE) where |= IN_MESSAGE | (shape->keyed ? IN_KEYED : 0); if (shape && shape->kind == PURE_KIND_TEXT) where |= IN_TEXT; unsigned char types[PURE_MODULE_STACK], owners[PURE_MODULE_STACK]; @@ -269,8 +273,8 @@ PURE_COLD static const char *verify_code(const PureModule *m, PureBlock block, i if (allowed & IN_ROW) REFUSE("row outside a column"); if (allowed & IN_OUTER) REFUSE("outer row outside a fold in a column"); if (view == FILTER) REFUSE("filter with an effect"); - if (view >= FOLD_ONE) REFUSE("fold with an effect"); - if (view >= 0) REFUSE("view with an effect"); + if (folding) REFUSE("fold with an effect"); + if (!handler) REFUSE("view with an effect"); if (allowed & IN_KEYED) REFUSE("document operation outside a keyed message handler"); if (allowed & IN_TEXT) REFUSE("text input outside a text handler"); REFUSE("message operation outside a message handler"); @@ -281,6 +285,11 @@ PURE_COLD static const char *verify_code(const PureModule *m, PureBlock block, i if (!names_arg(m, kind, arg, shape, row, outer)) REFUSE("operand names no such state, field, constant or unit"); /* A keyed list places its items by key, and an item's key stays. */ if (op->op == PURE_OP_LIST_INSERT && m->state_key[arg]) REFUSE("insert by position into a keyed list"); + /* A walk ends: its list only shrinks while it runs, and it runs no walk within. */ + if (view == WALK && (op->op == PURE_OP_LIST_APPEND || op->op == PURE_OP_LIST_INSERT) && (int)arg == row) + REFUSE("insert into the list walked"); + if (view == WALK && op->op == PURE_OP_EACH) REFUSE("each inside each"); + if (view == WALK && op->op == PURE_OP_REPLY) REFUSE("reply inside each"); if (op->op == PURE_OP_ITEM_SET && m->state_key[list_of(arg)] == item_field(arg) + 1) REFUSE("change of a keyed list's key"); /* PICK copies the value arg below the top; SLIDE drops arg values under the top. */ @@ -295,19 +304,24 @@ PURE_COLD static const char *verify_code(const PureModule *m, PureBlock block, i continue; } uint32_t skip = 0; - if (kind == A_FOLD) { + if (kind == A_FOLD || kind == A_EACH) { uint32_t inner = pc; skip = arg >> 16; - if (view >= FOLD_ONE) REFUSE(view == FILTER ? "fold inside a filter" : "fold inside a fold"); - if (skip > block.length - i - 1) REFUSE("fold block outside its block"); + if (kind == A_FOLD && (folding || view == FILTER)) + REFUSE(view == FILTER ? "fold inside a filter" : "fold inside a fold"); + if (skip > block.length - i - 1) REFUSE(kind == A_FOLD ? "fold block outside its block" : "each block outside its block"); unsigned how = arg & 0xFF; - const char *why = verify_block(m, (PureBlock){pc + 1, skip}, - how == PURE_FOLD_COUNT || how == PURE_FOLD_FIRST ? FOLD_ONE : FOLD_TWO, - (int)(arg >> 8 & 0xFF), row, 0, &inner); + /* A fold in a walk reads the walk's item as a fold in a column reads its row. */ + const char *why = kind == A_EACH ? verify_block(m, (PureBlock){pc + 1, skip}, WALK, (int)(arg >> 8 & 0xFF), -1, + event, &inner) + : verify_block(m, (PureBlock){pc + 1, skip}, + how == PURE_FOLD_COUNT || how == PURE_FOLD_FIRST ? FOLD_ONE : FOLD_TWO, + (int)(arg >> 8 & 0xFF), row, 0, &inner); if (why) { *at = inner; return why; } for (uint32_t k = i + 1; k <= i + skip; ++k) { - if (target[k]) REFUSE("branch into a fold"); - for (unsigned j = 0; j < open; ++j) if (joins[j].target == block.start + k) REFUSE("branch into a fold"); + const char *into = kind == A_FOLD ? "branch into a fold" : "branch into an each"; + if (target[k]) REFUSE(into); + for (unsigned j = 0; j < open; ++j) if (joins[j].target == block.start + k) REFUSE(into); } } /* Operand types, bottom to top; record operations take their fields. */ @@ -378,13 +392,13 @@ PURE_COLD static const char *verify_code(const PureModule *m, PureBlock block, i } if (!reachable) return "block end is unreachable"; if (view == FILTER) return height != 1 || types[0] != T_NUM ? "filter must leave one number" : NULL; - if (view >= FOLD_ONE) { + if (folding) { int want = view - FOLD_ONE + 1; return height != want || types[0] != T_NUM || types[want - 1] != T_NUM ? "fold block must leave its numbers" : NULL; } unsigned char result = view == PURE_VIEW_TEXT ? T_TEXT : T_NUM; - if (view >= 0 ? height != 1 || types[0] != result : height != 0) - return view >= 0 ? "view must leave one value of its type" : "handler must leave no value"; + if (!handler ? height != 1 || types[0] != result : height != 0) + return !handler ? "view must leave one value of its type" : "handler must leave no value"; return NULL; #undef REFUSE } @@ -644,20 +658,24 @@ PURE_COLD PureResult pure_module_load(const void *bytes, size_t size, PureModule if (constant_bytes) memcpy(out->constant_data, p + size - constant_bytes, constant_bytes); for (uint32_t i = 0; i < out->states; ++i, at += STATE_BYTES) { out->state_type[i] = (uint8_t)read32(at + 4); - if (!name_at(text, strings, read32(at), NAME_IDENTIFIER, out->state_names[i])) REFUSE("state name", i); if (read32(at + 4) > PURE_STATE_INDEX) REFUSE("state type", i); + /* Flags: a mark (cursor), a keyed list's key field + 1, or a list of a message's rows. */ + uint32_t flags = out->state_type[i] == PURE_STATE_NUM ? 0 : read32(at + 12); + bool cursor = out->state_type[i] == PURE_STATE_CURSOR, list = out->state_type[i] == PURE_STATE_LIST; + bool rows = list && flags == PURE_LIST_ROWS; + /* A list of a message's rows is named by the field's path (input.field), no other state. */ + if (!name_at(text, strings, read32(at), rows ? NAME_PATH : NAME_IDENTIFIER, out->state_names[i]) || + (rows && !strchr(out->state_names[i], '.'))) + REFUSE("state name", i); if (out->state_type[i] == PURE_STATE_NUM) { out->initial[i] = read_double(at + 8); if (!isfinite(out->initial[i])) REFUSE("non-finite initial value", i); } else { - /* Flags: a mark (cursor), or a keyed list's key field + 1. */ - uint32_t flags = read32(at + 12); - bool cursor = out->state_type[i] == PURE_STATE_CURSOR, list = out->state_type[i] == PURE_STATE_LIST; - if ((flags && !(cursor && flags == PURE_CURSOR_STAYS) && !(list && flags <= PURE_RECORD_FIELDS)) || + if ((flags && !(cursor && flags == PURE_CURSOR_STAYS) && !(list && flags <= PURE_RECORD_FIELDS) && !rows) || read32(at + 8) > UINT16_MAX) REFUSE("state reference", i); out->state_ref[i] = (uint16_t)read32(at + 8); - out->state_flags[i] = cursor ? (uint8_t)flags : 0; - out->state_key[i] = list ? (uint8_t)flags : 0; + out->state_flags[i] = cursor ? (uint8_t)flags : rows ? PURE_LIST_ROWS >> 8 : 0; + out->state_key[i] = list && !rows ? (uint8_t)flags : 0; } } for (uint32_t i = 0; i < out->collections; ++i, at += COLLECTION_BYTES) { @@ -701,16 +719,27 @@ PURE_COLD PureResult pure_module_load(const void *bytes, size_t size, PureModule * in order, but the last variable field's: it takes the rest. */ uint32_t last = UINT32_MAX; for (uint32_t f = 0; f < shape->field_count; ++f) { - uint32_t type = read32(fields + (size_t)(next_field + f) * FIELD_BYTES + 4); - if (type == PURE_FIELD_BYTES || type == PURE_FIELD_TEXT) last = f; + uint32_t type = read32(fields + (size_t)(next_field + f) * FIELD_BYTES + 4) & 0xFF; + if (type == PURE_FIELD_BYTES || type == PURE_FIELD_TEXT || type == PURE_FIELD_ROWS) last = f; } for (uint32_t f = 0; f < shape->field_count; ++f) { const unsigned char *entry = fields + (size_t)(next_field + f) * FIELD_BYTES; PureField *field = &out->field[next_field + f]; - field->type = (uint8_t)read32(entry + 4); + uint32_t type = read32(entry + 4); + field->type = (uint8_t)type; + field->rows = (uint16_t)(type >> 8); /* a rows field's list state */ if (!name_at(text, strings, read32(entry), NAME_PATH, field->name) || field->type < PURE_FIELD_U32 || - read32(entry + 4) > PURE_FIELD_TEXT) + field->type > PURE_FIELD_ROWS || (field->type != PURE_FIELD_ROWS && type >> 8) || type >> 24) REFUSE("message field", next_field + f); + /* Rows fill the list named by the input's name and the field's path; an output sends none. */ + if (field->type == PURE_FIELD_ROWS) { + char path[2 * PURE_MODULE_NAME + 2]; + snprintf(path, sizeof(path), "%s.%s", out->input_names[i], field->name); + if (shape->kind == PURE_KIND_OUTPUT || field->rows >= out->states || + out->state_type[field->rows] != PURE_STATE_LIST || !(out->state_flags[field->rows] & PURE_LIST_ROWS >> 8) || + strcmp(out->state_names[field->rows], path)) + REFUSE("rows field", next_field + f); + } /* A name is a field or a group, never both (user and user.name). */ for (uint32_t k = 0; k < f; ++k) { const char *a = out->field[next_field + k].name, *b = field->name; @@ -884,6 +913,8 @@ static double minimum(double a, double b) { return a < b || (a == b && signbit(a static double maximum(double a, double b) { return a > b || (a == b && !signbit(a)) ? a : b; } typedef struct { double num; PureBytes bytes; } Slot; +/* A walk (EACH): the list, the item it runs for, and whether that item left. */ +typedef struct { uint32_t list; size_t at; bool removed; } Walk; typedef struct { PureApp *app; const PureInputShape *shape; /* message, or NULL */ @@ -893,6 +924,7 @@ typedef struct { double dt; size_t row; /* the row a column is evaluated for (in a fold, the fold's item) */ size_t outer; /* in a fold, the row of the column it runs in */ + Walk *walk; /* the walk the code runs in, or NULL */ bool modified, exists; uint32_t (*spans)[2]; /* a message's variable fields: start and size in the payload */ } Event; @@ -1074,6 +1106,13 @@ static PureResult send(PureApp *app, uint32_t output, const Slot *fields, const return PURE_OK; } +/* The undo log a list's changes go to: none for a list of a message's rows, + * which is emptied when the event ends whatever it did. */ +static PureUndo *undo_for(PureApp *app, uint32_t list) { + return app->module->state_flags[list] & PURE_LIST_ROWS >> 8 && app->module->state_type[list] == PURE_STATE_LIST + ? NULL : &app->undo; +} + static PureResult run(const PureModule *m, double *values, PureBlock block, Event *ev, Slot *result); /* ---- Folds and filters a leaf at a time ------------------------------ @@ -1841,7 +1880,7 @@ static PureResult run(const PureModule *m, double *values, PureBlock block, Even at = pure_list_seek(list, key, cells[key], &found); if (found) { arena->used = mark; kind = PURE_FAULT_EXISTS; goto failed; } } - status = pure_list_insert(list, at, cells, &app->undo); + status = pure_list_insert(list, at, cells, undo_for(app, arg)); arena->used = mark; if (status != PURE_OK) goto refused; move_indices(m, values, arg, pure_list_count(list), at, true); @@ -1849,8 +1888,12 @@ static PureResult run(const PureModule *m, double *values, PureBlock block, Even } case PURE_OP_LIST_REMOVE: { size_t at = (size_t)stack[--sp].num; - if ((status = pure_list_remove(app->lists[arg], at, &app->undo)) != PURE_OK) goto refused; + if ((status = pure_list_remove(app->lists[arg], at, undo_for(app, arg))) != PURE_OK) goto refused; move_indices(m, values, arg, pure_list_count(app->lists[arg]), at, false); + if (ev->walk && ev->walk->list == arg) { /* the walk goes on with the item after */ + if (at < ev->walk->at) --ev->walk->at; + else if (at == ev->walk->at) ev->walk->removed = true; + } continue; } case PURE_OP_ITEM_GET: { @@ -1871,7 +1914,7 @@ static PureResult run(const PureModule *m, double *values, PureBlock block, Even status = text_field(m, list, field) ? contiguous(app, arena, value.bytes, &span) : PURE_OK; if (status == PURE_OK) status = pure_list_set(app->lists[list], at, field, - (PureCell){value.num, (unsigned char *)span.data, span.size}, &app->undo); + (PureCell){value.num, (unsigned char *)span.data, span.size}, undo_for(app, list)); arena->used = mark; if (status != PURE_OK) goto refused; continue; @@ -1906,6 +1949,27 @@ static PureResult run(const PureModule *m, double *values, PureBlock block, Even stack[sp++].bytes.owner = (uint16_t)(arg >> 8 & 0xFF); /* first: the list the index is in */ continue; } + case PURE_OP_EACH: { + /* The block that follows runs for each item the list has, as the + * handler's code with ROW the item; the list only shrinks meanwhile. */ + PureBlock inner = {pc, arg >> 16}; + Walk walk = {arg >> 8 & 0xFF, 0, false}; + pc += inner.length; + Event per = *ev; + per.walk = &walk; + while (walk.at < pure_list_count(app->lists[walk.list])) { + size_t mark = arena->used; + per.row = walk.at; + walk.removed = false; + status = run(m, values, inner, &per, NULL); + arena->used = mark; + if (status != PURE_OK) return status; + if (!walk.removed) ++walk.at; + } + ev->modified = per.modified; + ev->exists = per.exists; + continue; + } case PURE_OP_TEXT_COMPARE: { /* Texts order by their bytes: a shorter text before a longer one it begins. */ PureBytes right = stack[--sp].bytes, left = stack[sp - 1].bytes; @@ -2235,6 +2299,13 @@ static void hear(PureApp *app, const char *source, uint64_t seq) { static PureResult keep_reply(PureApp *app); +/* Every list of a message's rows emptied: an event's rows are its own. */ +static void clear_rows(PureApp *app) { + const PureModule *m = app->module; + for (uint32_t i = 0; i < m->states; ++i) + if (m->state_type[i] == PURE_STATE_LIST && m->state_flags[i] & PURE_LIST_ROWS >> 8) pure_list_clear(app->lists[i]); +} + /* One event: every handler for it runs in module order against pending * states, all or nothing. A key, text or message event saves before it * returns unless saving is deferred; a frame leaves that to the next event @@ -2259,8 +2330,10 @@ static PureResult dispatch(PureApp *app, uint32_t event, Event *ev) { result = keep_reply(app); if (result != PURE_OK) { undo_event(app, &mark); + clear_rows(app); return result; } + clear_rows(app); memcpy(app->values, pending, sizeof(pending)); ++app->events; ++app->changes; @@ -2361,7 +2434,7 @@ static PureResult message(PureApp *app, uint32_t input, const char *key, int64_t const PureField *field = &m->field[shape->field_start + f]; if (field->type == PURE_FIELD_NUMBER && !isfinite(read_double(payload.data + field->offset))) return fault(app, PURE_FAULT_NON_FINITE, UINT32_MAX); - if (field->type != PURE_FIELD_BYTES && field->type != PURE_FIELD_TEXT) continue; + if (field->type != PURE_FIELD_BYTES && field->type != PURE_FIELD_TEXT && field->type != PURE_FIELD_ROWS) continue; size_t start = placed ? placed[2 * f] : at; if (start > payload.size) return fault(app, PURE_FAULT_LIMIT, UINT32_MAX); size_t size = placed ? placed[2 * f + 1] : field->offset == PURE_FIELD_REST ? payload.size - at : @@ -2391,6 +2464,16 @@ static PureResult message(PureApp *app, uint32_t input, const char *key, int64_t if (opened != PURE_OK) { app->document = NULL; return opened; } if (base >= 0 && base != app->revision) { pure_app_finish(app); return PURE_CONFLICT; } } + /* Its rows fill their lists (emptied when the event ends); rows that are not whole fail it. */ + for (uint32_t f = 0; f < shape->field_count; ++f) { + const PureField *field = &m->field[shape->field_start + f]; + if (field->type != PURE_FIELD_ROWS) continue; + PureResult filled = pure_list_read(app->lists[field->rows], payload.data + spans[f][0], spans[f][1]); + if (filled == PURE_OK) continue; + clear_rows(app); + pure_app_finish(app); + return filled == PURE_ALLOCATION ? filled : fault(app, PURE_FAULT_LIMIT, UINT32_MAX); + } app->payload = payload; Event ev = {.app = app, .shape = shape, .key = key, .base = base, .arena = &app->arena, .exists = app->revision > 0, .spans = spans}; @@ -2790,7 +2873,7 @@ PURE_COLD static PureResult open_module(PureApp *app, const PureModule *module) module->state_ref[i]); list_drafts[i] = app->list_drafts[kept[i]]; rewrite[i] = result == PURE_OK && list_drafts[i] && lists[i] != app->lists[kept[i]]; - } else if (stored) { + } else if (stored && !(module->state_flags[i] & PURE_LIST_ROWS >> 8)) { /* rows are never stored */ result = pure_save_open_list(app, module, i, &lists[i], &list_drafts[i], &saved[i]); } else if (!(lists[i] = new_list(module, module->state_ref[i]))) result = PURE_ALLOCATION; } else values[i] = kept[i] >= 0 ? app->values[kept[i]] : module->initial[i]; diff --git a/core/module.h b/core/module.h index 2da5c6b..44af5eb 100644 --- a/core/module.h +++ b/core/module.h @@ -38,9 +38,14 @@ typedef enum { PURE_OP_ITEM_GET, PURE_OP_ITEM_SET, PURE_OP_INDEX_LOAD, PURE_OP_INDEX_STORE, PURE_OP_INDEX_MOVE, PURE_OP_INDEX_FIRST, PURE_OP_INDEX_LAST, PURE_OP_INDEX_NUM, PURE_OP_ROW, PURE_OP_PICK, PURE_OP_SLIDE, PURE_OP_FOLD, PURE_OP_TEXT_COMPARE, PURE_OP_LIST_FIND, PURE_OP_LIST_HAS, - PURE_OP_NOW, PURE_OP_FLOOR, PURE_OP_MOD, PURE_OP_SEND, PURE_OP_OUTER_ROW, + PURE_OP_NOW, PURE_OP_FLOOR, PURE_OP_MOD, PURE_OP_SEND, PURE_OP_OUTER_ROW, PURE_OP_EACH, PURE_OP_COUNT } PureOpcode; +/* EACH's argument: the list state (bits 8-15) and the length of the block + * that follows (16-31), run in a handler once for every item the list had + * when it began, in order, with ROW the item; the block may change states, + * the list's items and other lists, but not insert into the list it walks + * (an item it removes, or one before it, moves the walk with it). */ /* FOLD's argument: the kind (bits 0-7), the list state (8-15) and the length * of the block that follows (16-31), run once per item as a column of that * list. count counts the items whose block leaves a non-zero number; sum, @@ -58,19 +63,25 @@ typedef enum { PURE_KIND_KEY = 1, PURE_KIND_MESSAGE = 2, PURE_KIND_TEXT = 3, PUR PURE_KIND_OUTPUT = 5 } PureInputKind; enum { PURE_TIMER_LONGEST = 86400000, PURE_SOURCE = 64 }; /* A message field: a u32le or a binary64 (fixed, at its offset in the - * payload's prefix), or bytes or text of any length. The prefix also holds - * each variable field's u32le length but the last one's (its offset is + * payload's prefix), or bytes, text or rows of any length. The prefix also + * holds each variable field's u32le length but the last one's (its offset is * PURE_FIELD_REST), which takes what follows the others; the variable * fields' bytes follow the prefix in declaration order. A text is UTF-8 and - * a number finite, or the message fails. */ -typedef enum { PURE_FIELD_U32 = 1, PURE_FIELD_BYTES = 2, PURE_FIELD_NUMBER = 3, PURE_FIELD_TEXT = 4 } PureFieldType; + * a number finite, or the message fails. Rows are records of a list of a + * message's rows (rows, a list state), laid out as a list's stored form: a + * message fills that list with them, and fails when they are not whole. */ +typedef enum { PURE_FIELD_U32 = 1, PURE_FIELD_BYTES = 2, PURE_FIELD_NUMBER = 3, PURE_FIELD_TEXT = 4, + PURE_FIELD_ROWS = 5 } PureFieldType; enum { PURE_FIELD_REST = UINT32_MAX }; typedef enum { PURE_STATE_NUM = 0, PURE_STATE_TEXT = 1, PURE_STATE_CURSOR = 2, PURE_STATE_LIST = 3, PURE_STATE_INDEX = 4 } PureStateType; /* A cursor that stays before text inserted at it (a mark); other cursors go - * after it (a caret). */ -enum { PURE_CURSOR_STAYS = 1 }; + * after it (a caret). A list of a message's rows (its state's flags hold + * PURE_LIST_ROWS beside the key byte; its name is the field's path): a + * message's rows field fills it as the message arrives, it is emptied when + * every event ends, and it is never saved nor logged for undoing. */ +enum { PURE_CURSOR_STAYS = 1, PURE_LIST_ROWS = 256 }; /* A table view has one row per item of a list, or per item its filter * keeps; its columns are number or text views evaluated for one row at a * time. */ @@ -91,7 +102,7 @@ typedef enum { typedef struct { double value; uint32_t arg; uint8_t op, plan, shape; } PureOp; typedef struct { uint32_t start, length; } PureBlock; typedef struct { uint32_t event; PureBlock code; } PureHandler; -typedef struct { char name[PURE_MODULE_NAME]; uint8_t type; uint32_t offset; } PureField; +typedef struct { char name[PURE_MODULE_NAME]; uint8_t type; uint16_t rows; uint32_t offset; } PureField; typedef struct { uint8_t kind; bool keyed; @@ -122,7 +133,7 @@ typedef struct { char input_keys[PURE_MODULE_INPUTS][PURE_MODULE_NAME]; uint8_t state_type[PURE_MODULE_STATES]; uint16_t state_ref[PURE_MODULE_STATES]; /* text: constant; cursor: text; list: record; index: list */ - uint8_t state_flags[PURE_MODULE_STATES]; /* cursor: PURE_CURSOR_STAYS */ + uint8_t state_flags[PURE_MODULE_STATES]; /* cursor: PURE_CURSOR_STAYS; list: PURE_LIST_ROWS >> 8 */ /* A keyed list: its key field + 1 (0: none). Its items stay in key order * (numbers by value, texts by bytes), each key once, and keys do not change. */ uint8_t state_key[PURE_MODULE_STATES]; diff --git a/core/test-module.c b/core/test-module.c index 6c76510..6117fe4 100644 --- a/core/test-module.c +++ b/core/test-module.c @@ -632,7 +632,7 @@ static void messages(void) { static const H note_handler[] = {{1, 0, 2}}; bad = (Spec){states, 1, unkeyed, 1, views, 0, note_handler, 1, doc_read, 2, collections, 1, NULL, 0, NULL, 0, NULL, 0, NULL, 0, NULL, 0}; CHECK(load(bad, &module_b) == PURE_INVALID && strstr(error, "document operation outside")); - static const F unknown_type[] = {{"insert", 5}, {"start", 1}}; + static const F unknown_type[] = {{"insert", 6}, {"start", 1}}; static const I misplaced[] = {{"edit", NULL, PURE_KIND_MESSAGE, true, unknown_type, 2}}; bad = (Spec){states, 1, misplaced, 1, views, 0, NULL, 0, NULL, 0, collections, 1, NULL, 0, NULL, 0, NULL, 0, NULL, 0, NULL, 0}; CHECK(load(bad, &module_b) == PURE_INVALID && strstr(error, "message field")); @@ -2427,6 +2427,246 @@ static void lane_folds(void) { "\"cells\":%u}\n", folds, planned, shaped[PURE_SHAPE_GROUP], shaped[PURE_SHAPE_RANK], passes, faults, cells); } +/* ---- Walks and a message's rows ---------------------------------------- + * A shop: stock is keyed by item; an order's rows (a message's rows field, + * filling the list order.lines) each take their quantity from the item's + * stock and are logged, all or nothing (an item not stocked, or not enough of + * it, fails the order); clean walks the stock, removing an item with none + * left, removing the first item for one with one left, and adding one to + * the others. Random events against a model: the walk visits every item + * still there when it comes, once, in order, and the rows are gone after + * every event. */ +enum { EACH = PURE_OP_EACH, W_N = 0, W_SUM = 1, W_STOCK = 2, W_LINES = 3, W_LOG = 4 }; +#define WALKING(list, length) ((uint32_t)(list) << 8 | (uint32_t)(length) << 16) +#define ITEM(list, field) ((uint32_t)(list) | (uint32_t)(field) << 16) +static const S walk_numbers[] = {{"n", 0}, {"sum", 0}}; +static const T walk_lists[] = {{"stock", 3 | 1 << 8, 0}, {"order.lines", 3 | (uint32_t)PURE_LIST_ROWS << 8, 1}, {"log", 3, 2}}; +static const RF stock_fields[] = {{"item", 0, 0}, {"left", 0, 0}}, line_fields[] = {{"item", 0, 0}, {"qty", 0, 0}}, + entry_fields[] = {{"item", 0, 0}, {"qty", 0, 0}}; +static const R walk_records[] = {{"Stock", stock_fields, 2}, {"Line", line_fields, 2}, {"Entry", entry_fields, 2}}; +static const F order_fields[] = {{"lines", PURE_FIELD_ROWS | W_LINES << 8}}, restock_fields[] = {{"item", 1}, {"left", 1}}; +static const I walk_inputs[] = {{"order", NULL, PURE_KIND_MESSAGE, false, order_fields, 1}, KEY("clean", "KeyC"), + {"restock", NULL, PURE_KIND_MESSAGE, false, restock_fields, 2}}; +static const O walk_code[] = { + /* 0 order: for l in order.lines { stock[l.item].left -= l.qty (not below 0); log.append(l) } */ + {EACH, WALKING(W_LINES, 20), 0}, + {ROW, W_LINES, 0}, {IG, ITEM(W_LINES, 0), 0}, {PURE_OP_LIST_FIND, W_STOCK, 0}, + {ROW, W_LINES, 0}, {IG, ITEM(W_LINES, 0), 0}, {PURE_OP_LIST_FIND, W_STOCK, 0}, {IG, ITEM(W_STOCK, 1), 0}, + {ROW, W_LINES, 0}, {IG, ITEM(W_LINES, 1), 0}, {PURE_OP_SUB, 0, 0}, + {PICK, 0, 0}, {C, 0, 0}, {PURE_OP_GE, 0, 0}, {REQ, 0, 0}, + {IS, ITEM(W_STOCK, 1), 0}, + {ROW, W_LINES, 0}, {IG, ITEM(W_LINES, 0), 0}, {ROW, W_LINES, 0}, {IG, ITEM(W_LINES, 1), 0}, {LA, W_LOG, 0}, + /* 21: n += 1; sum += sum(l.qty for l in order.lines) */ + {L, W_N, 0}, {C, 0, 1}, {ADD, 0, 0}, {ST, W_N, 0}, + {L, W_SUM, 0}, {FOLD, FOLDING(PURE_FOLD_SUM, W_LINES, 3), 0}, {ROW, W_LINES, 0}, {IG, ITEM(W_LINES, 1), 0}, + {C, 0, 1}, {ADD, 0, 0}, {ST, W_SUM, 0}, + /* 32 clean: for s in stock { if s.left == 0 { stock.remove(s) } else if s.left == 1 { stock.remove(stock.first) } + * else { s.left = s.left + 1 } } */ + {EACH, WALKING(W_STOCK, 22), 0}, + {ROW, W_STOCK, 0}, {IG, ITEM(W_STOCK, 1), 0}, {C, 0, 0}, {EQ, 0, 0}, {JZ, 41, 0}, + {ROW, W_STOCK, 0}, {LR, W_STOCK, 0}, {JMP, 55, 0}, + {ROW, W_STOCK, 0}, {IG, ITEM(W_STOCK, 1), 0}, {C, 0, 1}, {EQ, 0, 0}, {JZ, 49, 0}, + {XF, W_STOCK, 0}, {LR, W_STOCK, 0}, {JMP, 55, 0}, + {ROW, W_STOCK, 0}, {ROW, W_STOCK, 0}, {IG, ITEM(W_STOCK, 1), 0}, {C, 0, 1}, {ADD, 0, 0}, {IS, ITEM(W_STOCK, 1), 0}, + /* 55 restock: stock.add(Stock { item, left }) */ + {FIELD, 0, 0}, {FIELD, 1, 0}, {LA, W_STOCK, 0}, +}; +static const H walk_handlers[] = {{1, 0, 32}, {3, 32, 23}, {5, 55, 3}}; + +static Spec walk_spec(const O *code, size_t count, const I *inputs, size_t ninputs, const H *handlers, size_t nhandlers, + const T *lists, const V *views, size_t nviews) { + return (Spec){walk_numbers, LEN(walk_numbers), inputs, ninputs, views, nviews, handlers, nhandlers, code, count, NULL, 0, + lists, 3, NULL, 0, NULL, 0, walk_records, LEN(walk_records), NULL, 0}; +} + +typedef struct { double item, left; } StockItem; +typedef struct { StockItem stock[64]; size_t stocked; double log[4096][2]; size_t logged; double n, sum; } Shop; + +static bool same_shop(const PureApp *app, const Shop *shop) { + const PureList *stock = app->lists[W_STOCK], *log = app->lists[W_LOG]; + if (pure_list_count(stock) != shop->stocked || pure_list_count(log) != shop->logged || + pure_list_count(app->lists[W_LINES]) || app->values[W_N] != shop->n || app->values[W_SUM] != shop->sum) + return false; + for (size_t i = 0; i < shop->stocked; ++i) + if (pure_list_get(stock, i, 0).num != shop->stock[i].item || pure_list_get(stock, i, 1).num != shop->stock[i].left) + return false; + for (size_t i = 0; i < shop->logged; ++i) + if (pure_list_get(log, i, 0).num != shop->log[i][0] || pure_list_get(log, i, 1).num != shop->log[i][1]) return false; + return true; +} + +static size_t put_row(unsigned char *out, double item, double qty) { + put_double(out, item); + put_double(out + 8, qty); + return 16; +} + +static void walks(void) { + CHECK(load(walk_spec(walk_code, LEN(walk_code), walk_inputs, 3, walk_handlers, 3, walk_lists, NULL, 0), &module_a) == PURE_OK); + PureApp app; + CHECK(pure_app_start(&app, &module_a, (PureData){0}) == PURE_OK); + static Shop shop, before; + shop = (Shop){.stocked = 0}; + uint32_t seed = 0x5a1e5eedu; + unsigned orders = 0, failed = 0, cleaned = 0, removed = 0, earlier = 0; + for (unsigned round = 0; round < 3000; ++round) { + before = shop; + unsigned roll_ = next_random(&seed) % 10; + PureResult result; + bool ok = true; + if (roll_ < 3) { /* restock an item, maybe one there already */ + double item = (double)(next_random(&seed) % 12), left = (double)(next_random(&seed) % 4); + unsigned char payload[8]; + put32(payload, (uint32_t)item); + put32(payload + 4, (uint32_t)left); + result = pure_app_message(&app, 2, NULL, -1, (PureSpan){payload, 8}); + size_t at = 0; + while (at < shop.stocked && shop.stock[at].item < item) ++at; + if (at < shop.stocked && shop.stock[at].item == item) ok = false; + else { + memmove(&shop.stock[at + 1], &shop.stock[at], (shop.stocked - at) * sizeof(*shop.stock)); + shop.stock[at] = (StockItem){item, left}; + ++shop.stocked; + } + } else if (roll_ < 8) { /* an order of up to 6 lines */ + unsigned char payload[6 * 16]; + size_t size = 0, lines = next_random(&seed) % 7; + double qty_total = 0; + for (size_t k = 0; k < lines && ok; ++k) { + double item = (double)(next_random(&seed) % 13), qty = (double)(next_random(&seed) % 3); + size += put_row(payload + size, item, qty); + size_t at = 0; + while (at < shop.stocked && shop.stock[at].item != item) ++at; + if (at == shop.stocked || shop.stock[at].left - qty < 0) { ok = false; break; } + shop.stock[at].left -= qty; + shop.log[shop.logged][0] = item; + shop.log[shop.logged++][1] = qty; + qty_total += qty; + } + for (size_t k = 0; !ok && k < lines; ++k) /* the rest of the rows, for the payload */ + if (size < (k + 1) * 16) size += put_row(payload + size, (double)(next_random(&seed) % 13), 1); + result = pure_app_message(&app, 0, NULL, -1, (PureSpan){size ? payload : NULL, size}); + if (ok) { + shop.n += 1; + shop.sum += qty_total; + ++orders; + } + } else { /* clean */ + result = pure_app_input(&app, 1, PURE_EDGE_DOWN); + size_t at = 0; + while (at < shop.stocked) { + bool gone = false; + if (shop.stock[at].left == 0) { + memmove(&shop.stock[at], &shop.stock[at + 1], (shop.stocked - at - 1) * sizeof(*shop.stock)); + --shop.stocked; + gone = true; + ++removed; + } else if (shop.stock[at].left == 1) { + memmove(&shop.stock[0], &shop.stock[1], (shop.stocked - 1) * sizeof(*shop.stock)); + --shop.stocked; + if (at == 0) gone = true; + else --at, ++earlier; + ++removed; + } else + shop.stock[at].left += 1; + if (!gone) ++at; + } + ++cleaned; + pure_app_input(&app, 1, PURE_EDGE_UP); + } + if (!ok) { + shop = before; + ++failed; + } + if ((result == PURE_OK) != ok || !same_shop(&app, &shop)) { + fprintf(stderr, "walk round %u: result %d, expected %s\n", round, result, ok ? "ok" : "a fault"); + abort(); + } + if (shop.logged > 4000) { /* start over before the model's log fills */ + pure_app_stop(&app); + CHECK(pure_app_start(&app, &module_a, (PureData){0}) == PURE_OK); + shop = (Shop){.stocked = 0}; + } + } + /* Rows that are not whole fail the message and change nothing. */ + before = shop; + unsigned char short_row[12] = {0}, not_finite[16]; + put_double(not_finite, 1); + put_double(not_finite + 8, NAN); + CHECK(pure_app_message(&app, 0, NULL, -1, (PureSpan){short_row, 12}) == PURE_LIMIT && same_shop(&app, &before)); + CHECK(pure_app_message(&app, 0, NULL, -1, (PureSpan){not_finite, 16}) == PURE_LIMIT && same_shop(&app, &before)); + pure_app_stop(&app); + + /* What a walk and a rows field may not be. */ + static const F note_fields[] = {{"lines", PURE_FIELD_ROWS | W_LINES << 8}, {"text", 4}}; + static const I note_inputs[] = {{"order", NULL, PURE_KIND_MESSAGE, false, note_fields, 2}}; + static const O into_walked[] = {{EACH, WALKING(W_STOCK, 3), 0}, {C, 0, 1}, {C, 0, 2}, {LA, W_STOCK, 0}}; + static const O nested[] = {{EACH, WALKING(W_STOCK, 3), 0}, {EACH, WALKING(W_LOG, 2), 0}, {C, 0, 1}, {ST, W_N, 0}}; + static const O replied[] = {{EACH, WALKING(W_STOCK, 2), 0}, {FIELD, 1, 0}, {REPLY, 0, 0}}; + static const O rows_read[] = {{FIELD, 0, 0}, {PURE_OP_BYTES_FROM, 0, 0}, {REPLY, 0, 0}}; + static const O into_each[] = {{C, 0, 1}, {JZ, 3, 0}, {EACH, WALKING(W_STOCK, 2), 0}, {C, 0, 1}, {ST, W_N, 0}}; + static const O view_each[] = {{EACH, WALKING(W_STOCK, 2), 0}, {C, 0, 1}, {ST, W_N, 0}, {C, 0, 1}}; + static const H first3[] = {{1, 0, 4}}, first3b[] = {{1, 0, 3}}, first5[] = {{1, 0, 5}}; + static const V walk_view[] = {{"v", 0, 4}}; + static const T unnamed[] = {{"stock", 3 | 1 << 8, 0}, {"lines", 3 | (uint32_t)PURE_LIST_ROWS << 8, 1}, {"log", 3, 2}}; + static const F logged_rows[] = {{"lines", PURE_FIELD_ROWS | W_LOG << 8}}; + static const I logged_inputs[] = {{"order", NULL, PURE_KIND_MESSAGE, false, logged_rows, 1}}; + static const I sent_rows[] = {{"order", NULL, PURE_KIND_OUTPUT, false, order_fields, 1}}; + const struct { Spec spec; const char *reason; } refused[] = { + {walk_spec(into_walked, LEN(into_walked), note_inputs, 1, first3, 1, walk_lists, NULL, 0), "insert into the list walked"}, + {walk_spec(nested, LEN(nested), note_inputs, 1, first3, 1, walk_lists, NULL, 0), "each inside each"}, + {walk_spec(replied, LEN(replied), note_inputs, 1, first3b, 1, walk_lists, NULL, 0), "reply inside each"}, + {walk_spec(rows_read, LEN(rows_read), note_inputs, 1, first3b, 1, walk_lists, NULL, 0), "no such state, field"}, + {walk_spec(into_each, LEN(into_each), note_inputs, 1, first5, 1, walk_lists, NULL, 0), "branch into an each"}, + {walk_spec(view_each, LEN(view_each), note_inputs, 1, NULL, 0, walk_lists, walk_view, 1), "view with an effect"}, + {walk_spec(NULL, 0, note_inputs, 1, NULL, 0, unnamed, NULL, 0), "state name"}, + {walk_spec(NULL, 0, logged_inputs, 1, NULL, 0, walk_lists, NULL, 0), "rows field"}, + {walk_spec(NULL, 0, sent_rows, 1, NULL, 0, walk_lists, NULL, 0), "rows field"}, + }; + for (size_t i = 0; i < LEN(refused); ++i) + if (load(refused[i].spec, &module_b) != PURE_INVALID || !strstr(error, refused[i].reason)) { + fprintf(stderr, "walk case %zu: expected '%s', got '%s'\n", i, refused[i].reason, error); + abort(); + } + CHECK(orders > 300 && failed > 300 && cleaned > 200 && removed > 50 && earlier > 10); + printf("{\"walks\":{\"orders\":%u,\"failed\":%u,\"cleaned\":%u,\"removed_while_walking\":%u,\"removed_before\":%u}}\n", + orders, failed, cleaned, removed, earlier); +} + +/* Damaged walk modules: whatever loads runs safely, rows and all. */ +static void walk_mutations(void) { + static unsigned char valid[65536], bytes[65536]; + size_t size = build(valid, walk_spec(walk_code, LEN(walk_code), walk_inputs, 3, walk_handlers, 3, walk_lists, NULL, 0)); + uint32_t state = 0x2f6b1c3du; + unsigned accepted = 0; + for (unsigned round = 0; round < 20000; ++round) { + memcpy(bytes, valid, size); + for (unsigned f = 0, flips = 1 + next_random(&state) % 3; f < flips; ++f) + bytes[next_random(&state) % size] ^= (unsigned char)(1u << (next_random(&state) % 8)); + if (pure_module_load(bytes, size, &module_b, error, sizeof(error)) != PURE_OK) continue; + ++accepted; + PureApp app; + if (pure_app_start(&app, &module_b, (PureData){0}) != PURE_OK) continue; + unsigned char payload[96]; + for (unsigned e = 0; e < 24; ++e) { + uint32_t input = next_random(&state) % module_b.inputs; + size_t length = next_random(&state) % sizeof(payload); + for (size_t k = 0; k < length; ++k) payload[k] = (unsigned char)next_random(&state); + for (size_t k = 0; k + 16 <= length && next_random(&state) % 2; k += 16) + put_row(payload + k, (double)(next_random(&state) % 8), (double)(next_random(&state) % 3)); + if (module_b.input[input].kind == PURE_KIND_MESSAGE) + pure_app_message(&app, input, NULL, -1, (PureSpan){payload, length}); + else if (module_b.input[input].kind == PURE_KIND_KEY) + pure_app_input(&app, input, PURE_EDGE_DOWN); + for (uint32_t s_ = 0; s_ < module_b.states; ++s_) + if (module_b.state_type[s_] == PURE_STATE_LIST && module_b.state_flags[s_] & PURE_LIST_ROWS >> 8) + CHECK(!pure_list_count(app.lists[s_])); /* rows go with their event */ + } + pure_app_stop(&app); + } + printf("{\"walk_module_mutations\":20000,\"accepted_after_damage\":%u}\n", accepted); +} + /* Damaged fold and filter modules: whatever loads runs safely. */ static void fold_mutations(void) { static unsigned char valid[65536], bytes[65536]; @@ -3348,6 +3588,8 @@ int main(void) { folds(); filters(); lane_folds(); + walks(); + walk_mutations(); keyed(); keyed_mutations(); snapshots(); |