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. --- docs/design/008-module-format.md | 7 ++- prototypes/connections/module.c | 62 +++++++++++++++++-- prototypes/connections/module.h | 7 ++- prototypes/connections/test-module.c | 111 ++++++++++++++++++++++++++++++++++- 4 files changed, 180 insertions(+), 7 deletions(-) diff --git a/docs/design/008-module-format.md b/docs/design/008-module-format.md index 5474541..761077a 100644 --- a/docs/design/008-module-format.md +++ b/docs/design/008-module-format.md @@ -96,6 +96,7 @@ v5는 값을 가진 채 합류하는 분기(조건식)와, 리스트 항목마 | 62 | ROW | → i | 열이 계산하는 행. `인자`는 그 표의 리스트 상태. 열 전용 | | 63 | PICK | … → … v | `인자`개 아래의 값을 복사해 올린다(0이면 맨 위). 타입과 대상도 그대로 | | 64 | SLIDE | … v → v | 맨 위 값 아래의 `인자`개(1 이상)를 버린다 | +| 65 | FOLD | → n | 집계. `인자`의 비트 0–7은 종류(0 count, 1 sum, 2 max, 3 min), 8–15는 리스트 상태, 16–31은 뒤따르는 블록의 길이 L. 그 L개 명령이 항목마다 그 리스트의 열처럼 돈다(`ROW`가 항목). count는 블록이 남긴 수가 0이 아닌 항목을 세고, sum·max·min은 블록이 남긴 값과 포함 여부(0이 아니면 포함)로 계산한다. 포함된 항목이 없으면 count·sum은 0, max·min은 `not_found` | `f`는 레코드 필드의 타입(수 또는 text)이다. 수 연산 결과가 유한하지 않으면 실패한다. 실패하면 그 이벤트의 모든 핸들러가 한 일이 취소된다. @@ -118,10 +119,14 @@ v5는 값을 가진 채 합류하는 분기(조건식)와, 리스트 항목마 합류 지점에는 모든 경로가 같은 스택(높이, 타입, 커서·인덱스의 대상)을 가져와야 한다. 그래서 조건식처럼 값이 합류를 건너가도 타입이 섞이지 않는다. 앞에 남은, 값을 가진 합류는 한 번에 8개까지다. 모든 명령에 도달할 수 있어야 하고, 핸들러는 값을 남기지 않으며 보기와 열은 자기 타입의 값 하나를 남긴다. +- 집계(FOLD)의 블록은 그 리스트의 열로 따로 검증한다. 읽기만 하고(효과는 거절), count는 수 하나, sum·max·min은 수 둘을 + 남긴다. 블록 안에 다시 집계를 둘 수 없다(비용 상한). 둘레의 블록은 FOLD와 그 블록을 명령 하나로 보고, 앞의 분기가 + 블록 안으로 들어오지 못한다. 블록은 둘레 블록 안에 끝나야 한다. - 표는 리스트 상태를 가리키고 열은 앞에 나온 표를 가리킨다. 표 밖의 이름은 한 이름공간이고, 열 이름은 표 안에서만 유일하다. -검증된 모듈은 실행 중 스택·타입 검사가 필요 없고, 이벤트 하나의 명령 수는 핸들러 길이 이하다. +검증된 모듈은 실행 중 스택·타입 검사가 필요 없고, 이벤트 하나의 명령 수는 핸들러 길이 이하다. 집계가 있으면 +블록 길이 × 항목 수(최대 65,536)만큼 더 돈다. 집계 안에 집계가 없으므로 이 곱이 상한이다. ## 실행 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