diff options
Diffstat (limited to 'prototypes/connections')
| -rw-r--r-- | prototypes/connections/module.c | 62 | ||||
| -rw-r--r-- | prototypes/connections/module.h | 7 | ||||
| -rw-r--r-- | prototypes/connections/test-module.c | 111 |
3 files changed, 174 insertions, 6 deletions
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; } |