From 4c2d3d4808827d12415e629bff27833c80de72d7 Mon Sep 17 00:00:00 2001 From: eunhhu Date: Mon, 28 Sep 2026 05:22:14 +0100 Subject: Slice a keyed list: fold and walk over a range of keys A fold whose kind has PURE_FOLD_SLICED (128), and a walk whose argument has PURE_EACH_SLICED (bit 0), first take two numbers, a low and a high key, and run for the items of their list (keyed by a number) whose keys are from low up to before high, found by key: the range is the program's meaning, not an optimization, so their blocks may fault (items out of the slice never run). A fold a leaf at a time now leaves out the lanes of a leaf outside the items it runs for, and a leaf that would fault runs item by item over those items alone. Slices are neither shaped nor given automatic ranges. ranges now checks a count over a slice whose test divides (a division by zero failing it only when inside the slice) against a model, the same on the item-by-item path, and a walk over a slice. --- core/module.c | 64 +++++++++++++++++++++++++++++----------- core/module.h | 5 ++++ core/test-module.c | 42 +++++++++++++++++++------- docs/design/008-module-format.md | 5 ++++ 4 files changed, 87 insertions(+), 29 deletions(-) diff --git a/core/module.c b/core/module.c index 8e2534e..d80b19f 100644 --- a/core/module.c +++ b/core/module.c @@ -202,8 +202,13 @@ PURE_COLD static bool names_arg(const PureModule *m, unsigned kind, uint32_t arg 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_DISTINCT && 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_FOLD: case A_EACH: { /* a slice's list is keyed by a number */ + uint32_t list = arg >> 8 & 0xFF, flags = arg & 0xFF; + bool sliced = kind == A_FOLD ? flags & PURE_FOLD_SLICED : flags & PURE_EACH_SLICED; + return (kind == A_FOLD ? (flags & 0x7F) <= PURE_FOLD_DISTINCT : flags <= PURE_EACH_SLICED) && + state_of(m, list, PURE_STATE_LIST) && arg >> 16 && + (!sliced || (m->state_key[list] && field_type(m, list, m->state_key[list] - 1u) == T_NUM)); + } case A_LOCAL: /* a slot, and a number or an index of a list */ return (arg & 0xFF) < PURE_MODULE_LOCALS && (arg >> 8 & 0xFF) <= 1 && ((arg >> 8 & 0xFF) ? state_of(m, arg >> 16, PURE_STATE_LIST) : !(arg >> 16)); @@ -324,7 +329,7 @@ PURE_COLD static const char *verify_code(const PureModule *m, PureBlock block, i 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; + unsigned how = arg & 0x7F; /* 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, locals, &inner) @@ -359,6 +364,9 @@ PURE_COLD static const char *verify_code(const PureModule *m, PureBlock block, i need[0] = field_type(m, arg, m->state_key[arg] - 1u); } else if (need[0] == T_LOCAL) { need[0] = arg >> 8 & 0xFF ? T_INDEX : T_NUM; + } else if ((kind == A_FOLD && arg & PURE_FOLD_SLICED) || (kind == A_EACH && arg & PURE_EACH_SLICED)) { + need[0] = need[1] = T_NUM; /* a slice's low and high keys */ + pops = 2; } if (height < (int)pops) REFUSE("stack underflow"); height -= (int)pops; @@ -375,7 +383,7 @@ PURE_COLD static const char *verify_code(const PureModule *m, PureBlock block, i REFUSE(type == T_CURSOR ? "cursor of another text" : "index of another list"); } unsigned char out = signature[op->op].out; - if (kind == A_FOLD && (arg & 0xFF) == PURE_FOLD_FIRST) { /* an index of its list */ + if (kind == A_FOLD && (arg & 0x7F) == PURE_FOLD_FIRST) { /* an index of its list */ out = T_INDEX; of = O_ARG; owner = arg >> 8 & 0xFF; @@ -545,10 +553,10 @@ PURE_COLD static bool conjuncts(const PureModule *m, PureBlock block, const Node /* The shape of a planned fold in a column, if it has one (see PureShape). */ PURE_COLD static void shape_fold(PureModule *m, uint32_t pc) { PureOp *fold = &m->code[pc]; - unsigned how = fold->arg & 0xFF; + unsigned how = fold->arg & 0x7F; int list = (int)(fold->arg >> 8 & 0xFF); PureBlock block = {pc + 1, fold->arg >> 16}; - if (!fold->plan || m->shapes == PURE_MODULE_SHAPES || how == PURE_FOLD_DISTINCT) return; + if (!fold->plan || m->shapes == PURE_MODULE_SHAPES || how == PURE_FOLD_DISTINCT || fold->arg & PURE_FOLD_SLICED) return; Node *nodes = malloc(block.length * sizeof(*nodes)); int roots[PURE_MODULE_STACK], tests[16]; unsigned count = 0, tested = 0; @@ -718,13 +726,14 @@ PURE_COLD static void range_code(PureModule *m, PureBlock block, int input) { for (uint32_t pc = block.start; pc < block.start + block.length; ++pc) { PureOp *op = &m->code[pc]; PureRange range; - if (op->op == PURE_OP_FOLD) { - if (op->plan && block_range(m, (PureBlock){pc + 1, op->arg >> 16}, (int)(op->arg >> 8 & 0xFF), false, &range)) + if (op->op == PURE_OP_FOLD) { /* a slice has its range already */ + if (op->plan && !(op->arg & PURE_FOLD_SLICED) && + block_range(m, (PureBlock){pc + 1, op->arg >> 16}, (int)(op->arg >> 8 & 0xFF), false, &range)) op->range = keep_range(m, &range); pc += op->arg >> 16; continue; } - if (op->op != PURE_OP_EACH) continue; + if (op->op != PURE_OP_EACH || op->arg & PURE_EACH_SLICED) continue; uint32_t end = pc + 1 + (op->arg >> 16); int height = 0; for (uint32_t at = pc + 1; at < end; ++at) { @@ -1688,12 +1697,16 @@ static PureResult fold_runs(const PureModule *m, double *values, PureBlock inner PureRun items; Memo memo; memo.known = 0; - /* Items from and to (a range's): whole leaves, whose items out of range the test leaves out. */ + /* The items from and up to before to (a slice's, or a range's): a leaf + * at a time, its lanes out of them left out (a slice's may fault: the + * leaf then runs item by item, its items in them alone). */ for (bool more = from < to && pure_list_run(list, from, &items); more && !fold->done && items.start < to; more = pure_list_next(list, &items)) { + unsigned first = from > items.start ? (unsigned)(from - items.start) : 0, + last = to - items.start < items.count ? (unsigned)(to - items.start) : items.count; Lanes out[2]; if (!run_lanes(m, values, inner, per, &items, out, store, &memo, NULL)) { - PureResult status = fold_rows(m, values, inner, per, items.start, items.start + items.count, fold); + PureResult status = fold_rows(m, values, inner, per, items.start + first, items.start + last, fold); if (status != PURE_OK) return status; continue; } @@ -1702,23 +1715,31 @@ static PureResult fold_runs(const PureModule *m, double *values, PureBlock inner const double *c = lanes_of(counts, scratch[0], &items), *v = lanes_of(&out[0], scratch[1], &items); if (fold->how == PURE_FOLD_COUNT) { size_t counted = 0; - for (unsigned i = 0; i < items.count; ++i) counted += c[i] != 0; + for (unsigned i = first; i < last; ++i) counted += c[i] != 0; fold->total += (double)counted; fold->any = fold->any || counted; } else if (fold->how == PURE_FOLD_SUM) { double total = fold->total; bool any = fold->any; - for (unsigned i = 0; i < items.count; ++i) + for (unsigned i = first; i < last; ++i) if (c[i] != 0) total += v[i], any = true; fold->total = total; fold->any = any; } else - for (unsigned i = 0; i < items.count && !fold->done; ++i) + for (unsigned i = first; i < last && !fold->done; ++i) if (!fold_in(fold, items.start + i, v[i], c[i])) return PURE_ALLOCATION; } return PURE_OK; } +/* The positions of the items whose keys are from low up to before high. */ +static void slice_of(const PureList *list, unsigned key, double low, double high, size_t *from, size_t *to) { + bool found; + *from = pure_list_seek(list, key, (PureCell){low, NULL, 0}, &found); + *to = pure_list_seek(list, key, (PureCell){high, NULL, 0}, &found); + if (*to < *from) *to = *from; +} + /* The positions of the items whose keys a range allows: its bounds run * alone, then found by key. false when a bound faults: the test then runs * for every item, as written (and faults as it would). */ @@ -2236,15 +2257,19 @@ static PureResult run(const PureModule *m, double *values, PureBlock block, Even PureBlock inner = {pc, arg >> 16}; PureList *list = app->lists[arg >> 8 & 0xFF]; pc += inner.length; - Fold fold = {arg & 0xFF, 0, false, false, {0}}; + Fold fold = {arg & 0x7F, 0, false, false, {0}}; Event per = *ev; per.outer = ev->row; + size_t from = 0, to = pure_list_count(list); + if (arg & PURE_FOLD_SLICED) { /* the items with keys from low up to before high */ + double high = stack[--sp].num, low = stack[--sp].num; + slice_of(list, m->state_key[arg >> 8 & 0xFF] - 1u, low, high, &from, &to); + } if (!op->shape || !fold_shaped(m, values, op, list, &per, &fold)) { - size_t from = 0, to = pure_list_count(list); if (op->range) /* only the items a range of keys allows can count */ range_bounds(m, values, &m->range[op->range - 1], list, m->state_key[arg >> 8 & 0xFF] - 1u, &per, &from, &to); status = op->plan ? fold_runs(m, values, inner, list, &per, &fold, from, to) - : fold_rows(m, values, inner, &per, 0, pure_list_count(list), &fold); + : fold_rows(m, values, inner, &per, from, to, &fold); free(fold.seen.keys); if (status != PURE_OK) return status; } @@ -2265,7 +2290,10 @@ static PureResult run(const PureModule *m, double *values, PureBlock block, Even pc += inner.length; Event per = *ev; per.walk = &walk; - if (op->range) /* a where that bounds the key: only the items in bounds */ + if (arg & PURE_EACH_SLICED) { /* the items with keys from low up to before high */ + double high = stack[--sp].num, low = stack[--sp].num; + slice_of(app->lists[walk.list], m->state_key[walk.list] - 1u, low, high, &walk.at, &walk.end); + } else if (op->range) /* a where that bounds the key: only the items in bounds */ range_bounds(m, values, &m->range[op->range - 1], app->lists[walk.list], m->state_key[walk.list] - 1u, &per, &walk.at, &walk.end); while (walk.at < walk.end && walk.at < pure_list_count(app->lists[walk.list])) { diff --git a/core/module.h b/core/module.h index a93cd69..6132e23 100644 --- a/core/module.h +++ b/core/module.h @@ -61,6 +61,11 @@ enum { PURE_MODULE_LOCALS = 64 }; * (distinct counts the different values, -0 as 0); first gives the index of * the first item whose block leaves a non-zero number. */ typedef enum { PURE_FOLD_COUNT, PURE_FOLD_SUM, PURE_FOLD_MAX, PURE_FOLD_MIN, PURE_FOLD_FIRST, PURE_FOLD_DISTINCT } PureFold; +/* A slice: a fold whose kind has PURE_FOLD_SLICED, or a walk whose argument + * has PURE_EACH_SLICED, first takes two numbers, a low and a high key, and + * runs for the items of its list (keyed by a number) whose keys are from + * low up to before high, found by key. */ +enum { PURE_FOLD_SLICED = 0x80, PURE_EACH_SLICED = 1 }; /* TEXT_COMPARE's argument: the relation, in the order of the number * comparisons (LT LE GT GE EQ NE); texts order by their bytes. */ typedef enum { PURE_LESS, PURE_LESS_EQUAL, PURE_GREATER, PURE_GREATER_EQUAL, PURE_EQUAL, PURE_NOT_EQUAL } PureRelation; diff --git a/core/test-module.c b/core/test-module.c index 846d7aa..11e7362 100644 --- a/core/test-module.c +++ b/core/test-module.c @@ -2889,7 +2889,7 @@ static const RF range_fields[] = {{"key", 0, 0}, {"a", 0, 0}, {"b", 0, 0}}; static const R range_records[] = {{"K", range_fields, 3}}; static const F bounds_fields[] = {{"lo", 3}, {"hi", 3}}; static const I range_inputs[] = {{"bounds", NULL, PURE_KIND_MESSAGE, false, bounds_fields, 2}, KEY("walk", "KeyW"), - KEY("drift", "KeyD")}; + KEY("drift", "KeyD"), KEY("slice", "KeyS")}; #define KEYED(field) {IG, ITEM(R_L, field), 0} static const O range_code[] = { /* 0 v0 = count(x in l where x.key >= lo && x.key < hi) */ @@ -2925,11 +2925,18 @@ static const O range_code[] = { {EACH, WALKING(R_L, 13), 0}, {ROW, R_L, 0}, KEYED(0), {L, R_HI, 0}, {PURE_OP_LT, 0, 0}, {JZ, 116, 0}, {L, R_HI, 0}, {C, 0, 1}, {PURE_OP_SUB, 0, 0}, {ST, R_HI, 0}, {L, R_N, 0}, {C, 0, 1}, {ADD, 0, 0}, {ST, R_N, 0}, + /* 116 v5 = count(x in l[lo .. hi] where x.a / x.b > 0): a slice, whose items alone may fault */ + {L, R_LO, 0}, {L, R_HI, 0}, {FOLD, FOLDING(PURE_FOLD_COUNT | PURE_FOLD_SLICED, R_L, 7), 0}, {ROW, R_L, 0}, KEYED(1), + {ROW, R_L, 0}, KEYED(2), {DIV, 0, 0}, {C, 0, 0}, {GT, 0, 0}, + /* 126 on slice: for x in l[lo .. hi] { x.b = x.b * 2 } */ + {L, R_LO, 0}, {L, R_HI, 0}, {EACH, WALKING(R_L, 6) | PURE_EACH_SLICED, 0}, {ROW, R_L, 0}, {ROW, R_L, 0}, KEYED(2), + {C, 0, 2}, {MUL, 0, 0}, {IS, ITEM(R_L, 2), 0}, }; #undef KEYED -static const V range_views[] = {{"v0", 0, 10}, {"v1", 10, 17}, {"v2", 27, 6}, {"v3", 33, 12}, {"v4", 45, 13}}; -static const W range_tables[] = {{"t", 2 | (R_L + 1) << 8, 0, 58, 14}, {"c", 0, 6, 72, 2}}; -static const H range_handlers[] = {{1, 74, 4}, {3, 78, 24}, {5, 102, 14}}; +static const V range_views[] = {{"v0", 0, 10}, {"v1", 10, 17}, {"v2", 27, 6}, {"v3", 33, 12}, {"v4", 45, 13}, + {"v5", 116, 10}}; +static const W range_tables[] = {{"t", 2 | (R_L + 1) << 8, 0, 58, 14}, {"c", 0, 7, 72, 2}}; +static const H range_handlers[] = {{1, 74, 4}, {3, 78, 24}, {5, 102, 14}, {7, 126, 9}}; static bool same_lists(const PureApp *a, const PureApp *b) { const PureList *x = a->lists[R_L], *y = b->lists[R_L]; @@ -2941,11 +2948,12 @@ static bool same_lists(const PureApp *a, const PureApp *b) { } static void ranges(void) { - Spec spec = {range_numbers, 3, range_inputs, 3, range_views, 5, range_handlers, 3, range_code, LEN(range_code), NULL, 0, + Spec spec = {range_numbers, 3, range_inputs, 4, range_views, 6, range_handlers, 4, range_code, LEN(range_code), NULL, 0, range_lists, 1, NULL, 0, NULL, 0, range_records, 1, range_tables, 2}; CHECK(load(spec, &module_a) == PURE_OK && load(spec, &module_b) == PURE_OK); CHECK(module_a.code[0].range && module_a.code[10].range && module_a.code[27].range && module_a.code[33].range && - !module_a.code[45].range && module_a.view_range[5] && module_a.code[78].range && !module_a.code[102].range); + !module_a.code[45].range && module_a.view_range[6] && module_a.code[78].range && !module_a.code[102].range && + !module_a.code[118].range && module_a.code[118].plan); for (uint32_t i = 0; i < module_b.code_count; ++i) module_b.code[i].range = 0; memset(module_b.view_range, 0, sizeof(module_b.view_range)); uint32_t seed = 0x7a45e11u; @@ -2967,7 +2975,19 @@ static void ranges(void) { put_double(payload + 8, hi); CHECK(pure_app_message(&a, 0, NULL, -1, (PureSpan){payload, 16}) == PURE_OK && pure_app_message(&b, 0, NULL, -1, (PureSpan){payload, 16}) == PURE_OK); - for (uint32_t v = 0; v < 5; ++v) { + /* The slice: its items alone, a division by zero among them failing it. */ + size_t sliced = 0; + bool divided = true; + for (size_t i = 0; i < pure_list_count(a.lists[R_L]); ++i) { + double k = pure_list_get(a.lists[R_L], i, 0).num, x = pure_list_get(a.lists[R_L], i, 1).num, + y = pure_list_get(a.lists[R_L], i, 2).num; + if (k < lo || k >= hi) continue; + if (y == 0) divided = false; + else sliced += x / y > 0; + } + double shown; + CHECK(pure_app_view(&a, 5, &shown) == divided && (!divided || shown == (double)sliced)); + for (uint32_t v = 0; v < 6; ++v) { double x = 0, y = 0; bool ok_a = pure_app_view(&a, v, &x), ok_b = pure_app_view(&b, v, &y); if (!same_number(ok_a, x, ok_b, y)) { @@ -2976,13 +2996,13 @@ static void ranges(void) { } ++compared; } - size_t rows = pure_app_rows(&a, 5); - CHECK(rows == pure_app_rows(&b, 5)); + size_t rows = pure_app_rows(&a, 6); + CHECK(rows == pure_app_rows(&b, 6)); for (size_t row = 0; row < rows; ++row) { double x, y; - CHECK(pure_app_cell(&a, 6, row, &x) && pure_app_cell(&b, 6, row, &y) && x == y); + CHECK(pure_app_cell(&a, 7, row, &x) && pure_app_cell(&b, 7, row, &y) && x == y); } - unsigned input = 1 + next_random(&seed) % 2; + unsigned input = 1 + next_random(&seed) % 3; PureResult went_a = pure_app_input(&a, input, PURE_EDGE_DOWN), went_b = pure_app_input(&b, input, PURE_EDGE_DOWN); CHECK(went_a == went_b && same_lists(&a, &b) && !memcmp(a.values, b.values, 3 * sizeof(double))); walked += input == 1; diff --git a/docs/design/008-module-format.md b/docs/design/008-module-format.md index dbac460..36423b2 100644 --- a/docs/design/008-module-format.md +++ b/docs/design/008-module-format.md @@ -191,6 +191,11 @@ text, 끝이 맞지 않는 바이트는 메시지를 `limit`으로 실패시킨 건너뛴 항목이 돌렸을 일이 없어야 하기 때문이다. 걷기의 경계는 블록이 쓰는 상태·지역 칸·리스트를 읽지 않을 때만 쓴다(경계는 걷기 전에 한 번 계산하고, where는 항목마다 다시 읽는다). 경계가 결함을 내면 범위 없이 쓰인 대로 돈다. +**조각.** 종류에 128(PURE_FOLD_SLICED)을 더한 집계와 인자의 비트 0(PURE_EACH_SLICED)을 켠 걷기는 먼저 수 두 개(낮은 키, 높은 +키)를 꺼내, 수로 키를 둔 리스트에서 키가 낮은 키부터 높은 키 앞까지인 항목만 돈다(키로 찾은 두 위치 사이). 범위를 뜻으로 적은 +것이라 블록이 결함을 낼 수 있어도 되고(조각 밖의 항목은 돌지 않는다), 잎 단위 실행은 조각 밖의 레인을 빼며, 결함이 날 잎은 조각 +안의 항목만 하나씩 돈다. + **지역 칸.** 이벤트는 수나 인덱스를 담는 칸 64개를 0으로 시작해 핸들러들과 그 안의 걷기·집계가 함께 쓴다(LOCAL_LOAD·LOCAL_STORE). 상태가 아니라 저장되지 않고, 이름공간을 쓰지 않으며, 보기에는 없다. 한 칸은 한 핸들러에서 한 가지로 쓰여 검증된 타입을 지킨다. 잎 단위 실행에서는 모두에 같은 값이고, 한 번의 통과로 답하는 집계에서는 키 쪽에만 온다. -- cgit v1.2.3