From eed3b0d022a5145be06d87140a747da1a82f0f9d Mon Sep 17 00:00:00 2001 From: eunhhu Date: Mon, 28 Sep 2026 04:31:43 +0100 Subject: Walk a list in a handler, and fill a list with a message's rows EACH runs the block that follows in a handler once for every item its list has when it begins, in order, with ROW the item: the block may change states, the list's items (a field, or removing one) and other lists, but may not insert into the list it walks, hold another walk or reply, so a walk runs at most its items times its block. Removing the walked item, or one before it, moves the walk with it, so no item is skipped. A fold in the block reads the walked item as OUTER_ROW, as a fold in a column reads its row. SQL's UPDATE ... WHERE and DELETE ... WHERE are a walk. A message field may now be rows (type 5, naming a list state): records laid out as the list's stored form, filling that list, whose flags hold PURE_LIST_ROWS and whose name is the field's path (order.lines), when the message arrives; rows that are not whole fail it (limit). A list of rows is emptied when every event ends, is never saved, and its changes are not logged for undoing, so a handler walks, folds and counts a message's rows as any list, and may use one as a scratch table within its event. An output has no rows. pure_list_clear lets a list's items go. walks checks a shop against a model over 3,000 random events: orders whose rows each take stock and are logged, all or nothing (997 applied, 1,322 failed and undone, by an item not stocked or not enough of it), and a clean that walks the stock removing items (83 while walking, 32 of them before the walked item). Nine refusals are checked, and 20,000 damaged walk modules run safely with no rows left after any event; all under ASan and UBSan too. --- core/module-list.c | 8 ++ core/module-list.h | 2 + core/module.c | 157 ++++++++++++++++++++++++++-------- core/module.h | 29 +++++-- 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(); -- cgit v1.2.3