From cd3fcb9873e23c2d07bd4e9d02d2111c96959440 Mon Sep 17 00:00:00 2001 From: eunhhu Date: Sat, 26 Sep 2026 11:15:42 +0100 Subject: Add folds: counts, sums, maxima and minima over a list FOLD (opcode 65) runs the block that follows it once per item of a list, as a column of that list, and pushes the count of items whose block left a non-zero number, or the sum, maximum or minimum of the values the block left with an include flag; an empty maximum or minimum is not_found. The verifier checks the block as a column (reads only, one or two numbers left, no fold inside, so the work is bounded by block length times items) and treats it from outside as one instruction that nothing branches into. Views and handlers can now say how many tasks are open or what the scores add up to without keeping a second copy of it in state. The checks cover values, empty lists, filters, a fold inside arithmetic, six refusals and 20,000 damaged fold modules run under ASan and UBSan. --- prototypes/connections/module.c | 62 +++++++++++++++++-- prototypes/connections/module.h | 7 ++- prototypes/connections/test-module.c | 111 ++++++++++++++++++++++++++++++++++- 3 files changed, 174 insertions(+), 6 deletions(-) (limited to 'prototypes') diff --git a/prototypes/connections/module.c b/prototypes/connections/module.c index 7af1d5c..6a373a3 100644 --- a/prototypes/connections/module.c +++ b/prototypes/connections/module.c @@ -20,7 +20,10 @@ enum { READ = IN_VIEW | IN_HANDLER }; * collection, a constant, a unit, the column's row, a branch target or a * stack depth. */ 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_ROW, A_TARGET, A_DEPTH, A_FOLD }; +/* A fold's block is verified as a column that leaves one number (count) or + * two (a value and whether to include it): these stand for a view type. */ +enum { FOLD_ONE = 100, FOLD_TWO }; /* 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. @@ -88,6 +91,7 @@ static const struct { unsigned char pops, in[3], out, where, arg, of; } signatur /* Stack copies: their types come from the values they move. */ [PURE_OP_PICK] = {0, {0}, 0, READ, A_DEPTH, O_ANY}, [PURE_OP_SLIDE] = {0, {0}, 0, READ, A_DEPTH, O_ANY}, + [PURE_OP_FOLD] = {0, {0}, T_NUM, READ, A_FOLD, O_ANY}, }; #undef NUMS #undef STATE @@ -168,6 +172,7 @@ PURE_COLD static bool names_arg(const PureModule *m, unsigned kind, uint32_t arg case A_CONSTANT: return arg < m->constants; case A_UNIT: return arg <= PURE_UNIT_LINE; case A_ROW: return (int)arg == row; + case A_FOLD: return (arg & 0xFF) <= PURE_FOLD_MIN && state_of(m, arg >> 8 & 0xFF, PURE_STATE_LIST) && arg >> 16; case A_NONE: case A_TARGET: case A_DEPTH: return true; default: return state_of(m, arg, (uint8_t)(kind - A_STATE)); } @@ -188,8 +193,10 @@ static bool same_stack(const Join *join, int height, const unsigned char *types, * join, as in a conditional expression; at most 8 joins with a non-empty * stack are ahead at once. Handlers end empty, views with one value of their * type. A column (row is its list) may read the row it is evaluated for. - * Returns why the block is refused, with at moved to the instruction when - * one is at fault, or NULL. */ + * A fold's block is verified as a column of its list (reads only, no fold + * in it); the block around treats it as one instruction and may not branch + * 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 *m, PureBlock block, int view, int row, uint32_t event, uint32_t *at) { #define REFUSE(why) do { *at = pc; return why; } while (0) @@ -230,6 +237,7 @@ PURE_COLD static const char *verify_block(const PureModule *m, PureBlock block, unsigned allowed = signature[op->op].where, kind = signature[op->op].arg, of = signature[op->op].of; if (!(allowed & where)) { if (allowed & IN_ROW) REFUSE("row outside a column"); + if (view >= FOLD_ONE) REFUSE("fold with an effect"); if (view >= 0) 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"); @@ -250,6 +258,20 @@ PURE_COLD static const char *verify_block(const PureModule *m, PureBlock block, if (!pick) height = from + 1; continue; } + uint32_t skip = 0; + if (kind == A_FOLD) { + uint32_t inner = pc; + skip = arg >> 16; + if (view >= FOLD_ONE) REFUSE("fold inside a fold"); + if (skip > block.length - i - 1) REFUSE("fold block outside its block"); + const char *why = verify_block(m, (PureBlock){pc + 1, skip}, (arg & 0xFF) == PURE_FOLD_COUNT ? FOLD_ONE : FOLD_TWO, + (int)(arg >> 8 & 0xFF), 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"); + } + } /* Operand types, bottom to top; record operations take their fields. */ unsigned char need[PURE_RECORD_FIELDS + 2]; unsigned pops = signature[op->op].pops; @@ -297,8 +319,13 @@ PURE_COLD static const char *verify_block(const PureModule *m, PureBlock block, } if (op->op == PURE_OP_JMP) reachable = false; } + i += skip; } if (!reachable) return "block end is unreachable"; + if (view >= FOLD_ONE) { + 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"; @@ -909,6 +936,33 @@ static PureResult run(const PureModule *m, double *values, PureBlock block, Even values[arg] = position; continue; } + case PURE_OP_FOLD: { + /* The block that follows runs once per item, as a column of the list. */ + unsigned how = arg & 0xFF; + PureBlock inner = {pc, arg >> 16}; + PureList *list = app->lists[arg >> 8 & 0xFF]; + pc += inner.length; + double total = 0; + bool any = false; + Event per = *ev; + for (size_t row = 0, items = pure_list_count(list); row < items; ++row) { + Slot out[2]; + size_t mark = arena->used; + per.row = row; + status = run(m, values, inner, &per, out); + arena->used = mark; + if (status != PURE_OK) return status; + double value = out[0].num; + if (how == PURE_FOLD_COUNT ? value == 0 : out[1].num == 0) continue; + total = how == PURE_FOLD_COUNT ? total + 1 : how == PURE_FOLD_SUM ? total + value : + !any ? value : how == PURE_FOLD_MAX ? maximum(total, value) : minimum(total, value); + any = true; + } + if (!any && how >= PURE_FOLD_MAX) { kind = PURE_FAULT_NOT_FOUND; goto failed; } + if (!isfinite(total)) { kind = PURE_FAULT_NON_FINITE; goto failed; } + stack[sp++].num = total; + continue; + } case PURE_OP_PICK: stack[sp] = stack[sp - 1 - arg]; ++sp; continue; case PURE_OP_SLIDE: stack[sp - 1 - arg] = stack[sp - 1]; sp -= arg; continue; default: break; @@ -936,7 +990,7 @@ static PureResult run(const PureModule *m, double *values, PureBlock block, Even if (!isfinite(value)) { kind = PURE_FAULT_NON_FINITE; goto failed; } stack[sp - 1].num = value; } - if (result) *result = stack[0]; + if (result) memcpy(result, stack, sp * sizeof(*stack)); /* a view's value, or a fold block's numbers */ return PURE_OK; refused: kind = status == PURE_LIMIT ? PURE_FAULT_LIMIT : status == PURE_NOT_FOUND ? PURE_FAULT_NOT_FOUND : PURE_FAULT_NONE; diff --git a/prototypes/connections/module.h b/prototypes/connections/module.h index c27f836..6938350 100644 --- a/prototypes/connections/module.h +++ b/prototypes/connections/module.h @@ -37,9 +37,14 @@ typedef enum { PURE_OP_LIST_COUNT, PURE_OP_LIST_APPEND, PURE_OP_LIST_INSERT, PURE_OP_LIST_REMOVE, 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_PICK, PURE_OP_SLIDE, PURE_OP_FOLD, PURE_OP_COUNT } PureOpcode; +/* 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, + * max and min take a value and an include flag from their block. */ +typedef enum { PURE_FOLD_COUNT, PURE_FOLD_SUM, PURE_FOLD_MAX, PURE_FOLD_MIN } PureFold; typedef enum { PURE_KIND_KEY = 1, PURE_KIND_MESSAGE = 2, PURE_KIND_TEXT = 3 } PureInputKind; typedef enum { PURE_FIELD_U32 = 1, PURE_FIELD_BYTES = 2 } PureFieldType; diff --git a/prototypes/connections/test-module.c b/prototypes/connections/test-module.c index 950fa88..918978e 100644 --- a/prototypes/connections/test-module.c +++ b/prototypes/connections/test-module.c @@ -1756,6 +1756,113 @@ static void marks(void) { CHECK(load(bad, &module_b) == PURE_INVALID && strstr(error, "state reference")); } +/* Folds: a block run once per item of a list, as a column of it, gives a + * count, a sum, a maximum or a minimum; an empty maximum has no value. */ +enum { FOLD = PURE_OP_FOLD }; +#define FOLDING(kind, list, length) ((uint32_t)(kind) | (uint32_t)(list) << 8 | (uint32_t)(length) << 16) +static const RF fold_fields[] = {{"title", 1, 0}, {"done", 0, 0}, {"points", 0, 0}}; +static const R fold_records[] = {{"task", fold_fields, 3}}; +static const T fold_states[] = {{"tasks", 3, 0}, {"at", 4, 0}}; +static const char *const fold_constants[] = {""}; +static const I fold_inputs[] = {{"typed", NULL, PURE_KIND_TEXT, false, NULL, 0}, KEY("toggle", "KeyT")}; +enum { F_TITLE = 0, F_DONE = 1u << 16, F_POINTS = 2u << 16 }; +static const O fold_code[] = { + {TI, 0, 0}, {C, 0, 0}, {TI, 0, 0}, {CHR, 0, 0}, {LA, 0, 0}, {XE, 0, 0}, {XS, 1, 0}, /* 0 typed */ + {XL, 1, 0}, {XL, 1, 0}, {IG, F_DONE, 0}, {NOT, 0, 0}, {IS, F_DONE, 0}, /* 7 toggle */ + {FOLD, FOLDING(PURE_FOLD_COUNT, 0, 3), 0}, {ROW, 0, 0}, {IG, F_DONE, 0}, {NOT, 0, 0}, /* 12 open */ + {FOLD, FOLDING(PURE_FOLD_SUM, 0, 3), 0}, {ROW, 0, 0}, {IG, F_POINTS, 0}, {C, 0, 1}, /* 16 points */ + {FOLD, FOLDING(PURE_FOLD_MAX, 0, 4), 0}, {ROW, 0, 0}, {IG, F_TITLE, 0}, {CHR, 0, 0}, /* 20 longest */ + {C, 0, 1}, + {FOLD, FOLDING(PURE_FOLD_SUM, 0, 4), 0}, {ROW, 0, 0}, {IG, F_POINTS, 0}, {ROW, 0, 0}, /* 25 done_points */ + {IG, F_DONE, 0}, + {FOLD, FOLDING(PURE_FOLD_MIN, 0, 5), 0}, {ROW, 0, 0}, {IG, F_POINTS, 0}, {ROW, 0, 0}, /* 30 fewest_open */ + {IG, F_DONE, 0}, {NOT, 0, 0}, + {C, 0, 10}, {FOLD, FOLDING(PURE_FOLD_COUNT, 0, 1), 0}, {C, 0, 1}, {ADD, 0, 0}, /* 36 count_plus */ +}; +static const H fold_handlers[] = {{1, 0, 7}, {3, 7, 5}}; +static const V fold_views[] = {{"open", 12, 4}, {"points", 16, 4}, {"longest", 20, 5}, {"done_points", 25, 5}, + {"fewest_open", 30, 6}, {"count_plus", 36, 4}}; +static Spec fold_spec(const O *code, size_t count, const V *views, size_t nviews, const H *handlers, size_t nhandlers) { + return (Spec){NULL, 0, fold_inputs, LEN(fold_inputs), views, nviews, handlers, nhandlers, code, count, NULL, 0, + fold_states, 2, fold_constants, 1, NULL, 0, fold_records, 1, NULL, 0}; +} + +static void folds(void) { + CHECK(load(fold_spec(fold_code, LEN(fold_code), fold_views, LEN(fold_views), fold_handlers, 2), &module_a) == PURE_OK); + PureApp app; + double value; + CHECK(pure_app_start(&app, &module_a, (PureData){0}) == PURE_OK); + CHECK(number_view(&app, 0) == 0 && number_view(&app, 1) == 0 && !pure_app_view(&app, 2, &value)); + CHECK(number_view(&app, 3) == 0 && !pure_app_view(&app, 4, &value) && number_view(&app, 5) == 10); + const char *const words[] = {"a", "bbb", "\xea\xb0\x80\xea\xb0\x80"}; /* one, three and two characters */ + for (size_t i = 0; i < 3; ++i) + CHECK(pure_app_text(&app, 0, (PureSpan){(const unsigned char *)words[i], strlen(words[i])}) == PURE_OK); + CHECK(number_view(&app, 0) == 3 && number_view(&app, 1) == 6 && number_view(&app, 2) == 3); + CHECK(number_view(&app, 3) == 0 && number_view(&app, 4) == 1 && number_view(&app, 5) == 13); + CHECK(pure_app_input(&app, 1, PURE_EDGE_DOWN) == PURE_OK); /* the last task is done */ + CHECK(number_view(&app, 0) == 2 && number_view(&app, 3) == 2 && number_view(&app, 4) == 1); + CHECK(pure_app_point(&app, 1, 0) == PURE_OK && pure_app_input(&app, 1, PURE_EDGE_DOWN) == PURE_OK); + CHECK(pure_app_point(&app, 1, 1) == PURE_OK && pure_app_input(&app, 1, PURE_EDGE_DOWN) == PURE_OK); + CHECK(number_view(&app, 0) == 0 && number_view(&app, 3) == 6 && !pure_app_view(&app, 4, &value)); /* none open */ + pure_app_stop(&app); + + /* What a fold may not be. */ + static const O nested[] = {{FOLD, FOLDING(PURE_FOLD_COUNT, 0, 2), 0}, {FOLD, FOLDING(PURE_FOLD_COUNT, 0, 1), 0}, {C, 0, 1}}; + static const O into[] = {{C, 0, 1}, {JZ, 3, 0}, {FOLD, FOLDING(PURE_FOLD_COUNT, 0, 1), 0}, {C, 0, 1}}; + static const O effect[] = {{FOLD, FOLDING(PURE_FOLD_COUNT, 0, 3), 0}, {ROW, 0, 0}, {XS, 1, 0}, {C, 0, 1}, + {PURE_OP_REQUIRE, 0, 0}}; + static const O short_sum[] = {{FOLD, FOLDING(PURE_FOLD_SUM, 0, 1), 0}, {C, 0, 1}}; + static const O outside[] = {{FOLD, FOLDING(PURE_FOLD_COUNT, 0, 5), 0}, {C, 0, 1}}; + static const O not_list[] = {{FOLD, FOLDING(PURE_FOLD_COUNT, 1, 1), 0}, {C, 0, 1}}; + static const struct { const O *code; size_t count, length; bool handler; const char *reason; } refused[] = { + {nested, LEN(nested), 3, false, "fold inside a fold"}, + {into, LEN(into), 4, false, "branch into a fold"}, + {effect, LEN(effect), 5, true, "fold with an effect"}, + {short_sum, LEN(short_sum), 2, false, "fold block must leave its numbers"}, + {outside, LEN(outside), 2, false, "fold block outside its block"}, + {not_list, LEN(not_list), 2, false, "no such state"}, + }; + for (size_t i = 0; i < LEN(refused); ++i) { + V view = {"v", 0, (uint32_t)refused[i].length}; + H handler = {3, 0, (uint32_t)refused[i].length}; + Spec spec = refused[i].handler ? fold_spec(refused[i].code, refused[i].count, NULL, 0, &handler, 1) + : fold_spec(refused[i].code, refused[i].count, &view, 1, NULL, 0); + if (load(spec, &module_b) != PURE_INVALID || !strstr(error, refused[i].reason)) { + fprintf(stderr, "fold case %zu: expected '%s', got '%s'\n", i, refused[i].reason, error); + abort(); + } + } +} + +/* Damaged fold modules: whatever loads runs safely. */ +static void fold_mutations(void) { + static unsigned char valid[65536], bytes[65536]; + size_t size = build(valid, fold_spec(fold_code, LEN(fold_code), fold_views, LEN(fold_views), fold_handlers, 2)); + uint32_t state = 0x27d4eb2fu; + 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; + for (unsigned e = 0; e < 16; ++e) { + uint32_t input = next_random(&state) % 2; + if (module_b.input[input].kind == PURE_KIND_TEXT) pure_app_text(&app, input, (PureSpan){(const unsigned char *)"ab", 2}); + else if (module_b.input[input].kind == PURE_KIND_KEY) pure_app_input(&app, input, PURE_EDGE_DOWN); + for (uint32_t v = 0; v < module_b.views; ++v) { + double value; + if (module_b.view_type[v] == PURE_VIEW_TEXT) pure_app_view_text(&app, v, ignore_span, NULL); + else pure_app_view(&app, v, &value); + } + } + pure_app_stop(&app); + } + printf("{\"fold_module_mutations\":20000,\"accepted_after_damage\":%u}\n", accepted); +} + /* A host points at an item: the index a view shows as its position moves * there, as an event with no handler, saved like a key event; deferred, it * joins the burst and a failed save undoes it with the rest. */ @@ -1796,6 +1903,8 @@ int main(void) { marks(); text_mutations(); lists(); + folds(); + fold_mutations(); pointing(); list_mutations(); tables(); @@ -1803,6 +1912,6 @@ int main(void) { stored_states(); deferred(); printf("{\"sizeof_module\":%zu,\"sizeof_app\":%zu}\n", sizeof(PureModule), sizeof(PureApp)); - puts("{\"module_tests\":\"verified-load-atomic-events-faults-signed-zero-if-else-replace-by-name-rejections-mutations-messages-documents-typed-verification-text-cursors-utf8-views-rollback-replace-lists-indices-undo-migration-joins-tables-columns-pick-slide-stored-equivalence-crashes-frames-messages-migration-deferred-bursts-pointing-marks\"}"); + puts("{\"module_tests\":\"verified-load-atomic-events-faults-signed-zero-if-else-replace-by-name-rejections-mutations-messages-documents-typed-verification-text-cursors-utf8-views-rollback-replace-lists-indices-undo-migration-joins-tables-columns-pick-slide-stored-equivalence-crashes-frames-messages-migration-deferred-bursts-pointing-marks-folds\"}"); return 0; } -- cgit v1.2.3