diff options
| -rw-r--r-- | core/module.c | 281 | ||||
| -rw-r--r-- | core/module.h | 31 | ||||
| -rw-r--r-- | core/test-module.c | 124 | ||||
| -rw-r--r-- | docs/design/008-module-format.md | 9 |
4 files changed, 410 insertions, 35 deletions
diff --git a/core/module.c b/core/module.c index dc65a51..8e2534e 100644 --- a/core/module.c +++ b/core/module.c @@ -202,7 +202,7 @@ 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_FIRST && state_of(m, arg >> 8 & 0xFF, PURE_STATE_LIST) && arg >> 16; + 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_LOCAL: /* a slot, and a number or an index of a list */ return (arg & 0xFF) < PURE_MODULE_LOCALS && (arg >> 8 & 0xFF) <= 1 && @@ -548,7 +548,7 @@ PURE_COLD static void shape_fold(PureModule *m, uint32_t pc) { unsigned how = fold->arg & 0xFF; int list = (int)(fold->arg >> 8 & 0xFF); PureBlock block = {pc + 1, fold->arg >> 16}; - if (!fold->plan || m->shapes == PURE_MODULE_SHAPES) return; + if (!fold->plan || m->shapes == PURE_MODULE_SHAPES || how == PURE_FOLD_DISTINCT) return; Node *nodes = malloc(block.length * sizeof(*nodes)); int roots[PURE_MODULE_STACK], tests[16]; unsigned count = 0, tested = 0; @@ -608,6 +608,141 @@ PURE_COLD static bool locals_agree(const PureModule *m, PureBlock block) { return true; } +/* Whether a node's subtree cannot fault: no division, no overflow of a sum + * or product, no key or item that may be missing (an item read through the + * item itself or the column's row is there). */ +PURE_COLD static bool faultless(const PureModule *m, PureBlock block, const Node *nodes, int at) { + const PureOp *op = &m->code[block.start + at]; + switch (op->op) { + case PURE_OP_CONST: case PURE_OP_LOAD: case PURE_OP_FIELD: case PURE_OP_LOCAL_LOAD: case PURE_OP_ROW: + case PURE_OP_OUTER_ROW: case PURE_OP_LIST_COUNT: case PURE_OP_INDEX_FIRST: case PURE_OP_INDEX_LAST: + case PURE_OP_INDEX_LOAD: case PURE_OP_INDEX_NUM: case PURE_OP_LT: case PURE_OP_LE: case PURE_OP_GT: case PURE_OP_GE: + case PURE_OP_EQ: case PURE_OP_NE: case PURE_OP_AND: case PURE_OP_OR: case PURE_OP_NOT: case PURE_OP_NEG: + case PURE_OP_FLOOR: case PURE_OP_MIN: case PURE_OP_MAX: case PURE_OP_LIST_HAS: + break; + case PURE_OP_ITEM_GET: { + uint8_t index = m->code[block.start + nodes[at].kid[0]].op; + if (index != PURE_OP_ROW && index != PURE_OP_OUTER_ROW) return false; + break; + } + default: return false; + } + for (unsigned k = 0; k < 3; ++k) + if (nodes[at].kid[k] >= 0 && !faultless(m, block, nodes, nodes[at].kid[k])) return false; + return true; +} + +/* The range of a keyed list's keys a planned block's test allows (see + * PureRange): a filter's other parts may fault, a fold's or walk's may not; + * a fold's value (the first of two) neither. */ +PURE_COLD static bool block_range(const PureModule *m, PureBlock block, int list, bool faults, PureRange *out) { + if (!m->state_key[list] || field_type(m, (uint32_t)list, m->state_key[list] - 1u) != T_NUM || !block.length) return false; + uint32_t key = m->state_key[list] - 1u; + Node *nodes = malloc(block.length * sizeof(*nodes)); + int roots[PURE_MODULE_STACK], tests[16]; + unsigned count = 0, tested = 0; + bool ok = nodes && block_tree(m, block, list, nodes, roots, &count) && count >= 1 && + conjuncts(m, block, nodes, roots[count - 1], tests, &tested) && + (faults || count == 1 || faultless(m, block, nodes, roots[0])); + PureRange range = {0}; + for (unsigned k = 0; ok && k < tested; ++k) { + const Node *node = &nodes[tests[k]]; + uint8_t op = m->code[block.start + tests[k]].op; + bool bounded = false; + for (unsigned side = 0; side < 2 && !bounded && op >= PURE_OP_LT && op <= PURE_OP_EQ; ++side) { + int item = node->kid[side], value = node->kid[1 - side]; + const PureOp *get = &m->code[block.start + item]; + if (get->op != PURE_OP_ITEM_GET || list_of(get->arg) != (uint32_t)list || item_field(get->arg) != key || + m->code[block.start + nodes[item].kid[0]].op != PURE_OP_ROW || nodes[value].item) + continue; + static const uint8_t flipped[] = {[PURE_OP_LT] = PURE_OP_GT, [PURE_OP_LE] = PURE_OP_GE, + [PURE_OP_GT] = PURE_OP_LT, [PURE_OP_GE] = PURE_OP_LE, [PURE_OP_EQ] = PURE_OP_EQ}; + uint8_t relation = side ? flipped[op] : op; /* the key REL the value */ + PureBlock bound = {nodes[value].first, block.start + (uint32_t)value + 1 - nodes[value].first}; + bool lower = relation == PURE_OP_GT || relation == PURE_OP_GE || relation == PURE_OP_EQ, + upper = relation == PURE_OP_LT || relation == PURE_OP_LE || relation == PURE_OP_EQ; + if ((lower && range.lower_relation) || (upper && range.upper_relation)) continue; /* one of each */ + if (lower) range.lower_relation = relation == PURE_OP_EQ ? PURE_OP_GE : relation, range.lower = bound; + if (upper) range.upper_relation = relation == PURE_OP_EQ ? PURE_OP_LE : relation, range.upper = bound; + bounded = true; + } + if (!bounded && !faults && !faultless(m, block, nodes, tests[k])) ok = false; + } + free(nodes); + if (!ok || (!range.lower_relation && !range.upper_relation)) return false; + *out = range; + return true; +} + +PURE_COLD static uint8_t keep_range(PureModule *m, const PureRange *range) { + if (m->ranges == PURE_MODULE_RANGES) return 0; + m->range[m->ranges++] = *range; + return m->ranges; +} + +/* Whether a walk's bounds read nothing its block writes: the states and + * locals it stores, the lists it changes. A bound is found once, before + * the walk; the walk's where reads it anew for every item. */ +PURE_COLD static bool bounds_fixed(const PureModule *m, const PureRange *range, PureBlock body) { + uint64_t states = 0, locals = 0, lists = 0; + for (uint32_t pc = body.start; pc < body.start + body.length; ++pc) { + const PureOp *op = &m->code[pc]; + switch (op->op) { + case PURE_OP_STORE: case PURE_OP_CUR_STORE: case PURE_OP_INDEX_STORE: case PURE_OP_TEXT_INSERT: + case PURE_OP_TEXT_REMOVE: case PURE_OP_TEXT_SET: + states |= (uint64_t)1 << (op->arg & 63); + break; + case PURE_OP_LOCAL_STORE: locals |= (uint64_t)1 << (op->arg & 63); break; + case PURE_OP_LIST_APPEND: case PURE_OP_LIST_INSERT: case PURE_OP_LIST_REMOVE: lists |= (uint64_t)1 << (op->arg & 63); break; + case PURE_OP_ITEM_SET: lists |= (uint64_t)1 << (list_of(op->arg) & 63); break; + default: break; + } + } + for (unsigned side = 0; side < 2; ++side) { + PureBlock bound = side ? range->upper : range->lower; + if (!(side ? range->upper_relation : range->lower_relation)) continue; + for (uint32_t pc = bound.start; pc < bound.start + bound.length; ++pc) { + const PureOp *op = &m->code[pc]; + int list = list_read(op); + if ((op->op == PURE_OP_LOAD || op->op == PURE_OP_INDEX_LOAD) && states >> (op->arg & 63) & 1) return false; + if (op->op == PURE_OP_LOCAL_LOAD && locals >> (op->arg & 63) & 1) return false; + if (list >= 0 && lists >> (list & 63) & 1) return false; + } + } + return true; +} + +/* A walk whose block begins with its where (a test, then a jump to the + * block's end when it fails) and a planned fold: the range their test allows. */ +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)) + op->range = keep_range(m, &range); + pc += op->arg >> 16; + continue; + } + if (op->op != PURE_OP_EACH) continue; + uint32_t end = pc + 1 + (op->arg >> 16); + int height = 0; + for (uint32_t at = pc + 1; at < end; ++at) { + const PureOp *next = &m->code[at]; + if (next->op == PURE_OP_JZ) { + PureBlock where = {pc + 1, at - pc - 1}; + if (height == 1 && next->arg == end && block_has_lanes(m, where, input) && + block_range(m, where, (int)(op->arg >> 8 & 0xFF), false, &range) && + bounds_fixed(m, &range, (PureBlock){at + 1, end - at - 1})) + op->range = keep_range(m, &range); + break; + } + if (!has_lanes(m, next, input) || next->op == PURE_OP_PICK || next->op == PURE_OP_SLIDE) break; + height += 1 - (int)arity(next->op); + } + } +} + PURE_COLD PureResult pure_module_read(const char *path, PureModule *out, char *error, size_t error_size) { FILE *file = fopen(path, "rb"); unsigned char *bytes = NULL; @@ -916,6 +1051,10 @@ PURE_COLD PureResult pure_module_load(const void *bytes, size_t size, PureModule plan_folds(out, out->view_code[i], given); out->view_plan[i] = out->view_type[i] == PURE_VIEW_TABLE && out->view_code[i].length && block_has_lanes(out, out->view_code[i], given); + PureRange range; + if (out->view_plan[i] && block_range(out, out->view_code[i], out->view_list[i], true, &range)) + out->view_range[i] = keep_range(out, &range); + if (out->view_type[i] != PURE_VIEW_TABLE) range_code(out, out->view_code[i], given); /* A fold in a column runs for every row: one pass may answer them all. */ for (uint32_t pc = out->view_code[i].start; out->view_table[i] && pc < out->view_code[i].start + out->view_code[i].length; ++pc) if (out->code[pc].op == PURE_OP_FOLD) { @@ -925,7 +1064,9 @@ PURE_COLD PureResult pure_module_load(const void *bytes, size_t size, PureModule } for (uint32_t i = 0; i < out->handlers; ++i) { int input = event_input(out->handler[i].event); - plan_folds(out, out->handler[i].code, input >= 0 && out->input[input].kind == PURE_KIND_MESSAGE ? input : -1); + input = input >= 0 && out->input[input].kind == PURE_KIND_MESSAGE ? input : -1; + plan_folds(out, out->handler[i].code, input); + range_code(out, out->handler[i].code, input); } return PURE_OK; refused: @@ -975,8 +1116,9 @@ 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; +/* A walk (EACH): the list, the item it runs for, where it ends (items the + * walk removes move it), and whether that item left. */ +typedef struct { uint32_t list; size_t at, end; bool removed; } Walk; typedef struct { PureApp *app; const PureInputShape *shape; /* message, or NULL */ @@ -1458,21 +1600,66 @@ static bool run_lanes(const PureModule *m, const double *values, PureBlock block return true; } -/* A fold's running value: what count, sum, max, min or first has so far. */ -typedef struct { unsigned how; double total; bool any, done; } Fold; +/* The values a distinct fold has seen: open addressing over their bits (-0 + * as 0), UINT64_MAX free (no finite number's bits). */ +typedef struct { uint64_t *keys; size_t capacity, count; } Seen; + +/* A fold's running value: what count, sum, max, min, first or distinct has so far. */ +typedef struct { unsigned how; double total; bool any, done; Seen seen; } Fold; -/* One item: its value, and whether it counts (for count and first, the value is). */ -static void fold_in(Fold *fold, size_t row, double value, double counts) { - if (counts == 0) return; +static size_t seen_slot(uint64_t bits, size_t capacity) { + bits ^= bits >> 33, bits *= 0xff51afd7ed558ccdu, bits ^= bits >> 33; + return (size_t)bits & (capacity - 1); +} + +/* Whether value is new to the set (added); false without memory too (*full). */ +static bool seen_new(Seen *seen, double value, bool *full) { + uint64_t bits; + value = value == 0 ? 0 : value; + memcpy(&bits, &value, sizeof(bits)); + if (2 * (seen->count + 1) > seen->capacity) { /* half the slots free */ + size_t capacity = seen->capacity ? 2 * seen->capacity : 64; + uint64_t *keys = malloc(capacity * sizeof(*keys)); + if (!keys) { *full = true; return false; } + memset(keys, 0xFF, capacity * sizeof(*keys)); + for (size_t i = 0; i < seen->capacity; ++i) { + if (seen->keys[i] == UINT64_MAX) continue; + size_t at = seen_slot(seen->keys[i], capacity); + while (keys[at] != UINT64_MAX) at = (at + 1) & (capacity - 1); + keys[at] = seen->keys[i]; + } + free(seen->keys); + seen->keys = keys; + seen->capacity = capacity; + } + size_t at = seen_slot(bits, seen->capacity); + for (; seen->keys[at] != UINT64_MAX; at = (at + 1) & (seen->capacity - 1)) + if (seen->keys[at] == bits) return false; + seen->keys[at] = bits; + ++seen->count; + return true; +} + +/* One item: its value, and whether it counts (for count and first, the + * value is). false without memory (a distinct fold's set). */ +static bool fold_in(Fold *fold, size_t row, double value, double counts) { + if (counts == 0) return true; unsigned how = fold->how; if (how == PURE_FOLD_FIRST) { fold->total = (double)row; fold->any = fold->done = true; - return; + return true; + } + if (how == PURE_FOLD_DISTINCT) { + bool full = false; + fold->total += seen_new(&fold->seen, value, &full); + fold->any = true; + return !full; } fold->total = how == PURE_FOLD_COUNT ? fold->total + 1 : how == PURE_FOLD_SUM ? fold->total + value : !fold->any ? value : how == PURE_FOLD_MAX ? maximum(fold->total, value) : minimum(fold->total, value); fold->any = true; + return true; } /* The fold's block for its items from first to last, one at a time. */ @@ -1486,7 +1673,7 @@ static PureResult fold_rows(const PureModule *m, double *values, PureBlock inner PureResult status = run(m, values, inner, per, out); per->arena->used = mark; if (status != PURE_OK) return status; - fold_in(fold, row, out[0].num, one ? out[0].num : out[1].num); + if (!fold_in(fold, row, out[0].num, one ? out[0].num : out[1].num)) return PURE_ALLOCATION; } return PURE_OK; } @@ -1495,13 +1682,15 @@ static PureResult fold_rows(const PureModule *m, double *values, PureBlock inner * fault goes item by item. The items join the fold in order, so a sum adds * as it would one at a time. */ static PureResult fold_runs(const PureModule *m, double *values, PureBlock inner, const PureList *list, Event *per, - Fold *fold) { + Fold *fold, size_t from, size_t to) { double store[PURE_MODULE_STACK][PURE_LIST_RUN], scratch[2][PURE_LIST_RUN]; bool one = fold->how == PURE_FOLD_COUNT || fold->how == PURE_FOLD_FIRST; PureRun items; Memo memo; memo.known = 0; - for (bool more = pure_list_run(list, 0, &items); more && !fold->done; more = pure_list_next(list, &items)) { + /* Items from and to (a range's): whole leaves, whose items out of range the test leaves out. */ + for (bool more = from < to && pure_list_run(list, from, &items); more && !fold->done && items.start < to; + more = pure_list_next(list, &items)) { 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); @@ -1524,11 +1713,42 @@ static PureResult fold_runs(const PureModule *m, double *values, PureBlock inner fold->total = total; fold->any = any; } else - for (unsigned i = 0; i < items.count && !fold->done; ++i) fold_in(fold, items.start + i, v[i], c[i]); + for (unsigned i = 0; i < items.count && !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 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). */ +static bool range_bounds(const PureModule *m, double *values, const PureRange *range, const PureList *list, unsigned key, + Event *ev, size_t *from, size_t *to) { + PureApp *app = ev->app; + PureFault fault = app->fault; + uint32_t fault_pc = app->fault_pc; + bool ok = true; + *from = 0; + *to = pure_list_count(list); + for (unsigned side = 0; side < 2 && ok; ++side) { + uint8_t relation = side ? range->upper_relation : range->lower_relation; + if (!relation) continue; + Slot bound; + size_t mark = ev->arena->used; + ok = run(m, values, side ? range->upper : range->lower, ev, &bound) == PURE_OK; + ev->arena->used = mark; + if (!ok) break; + bool found; + size_t at = pure_list_seek(list, key, (PureCell){bound.num, NULL, 0}, &found); + at += (relation == PURE_OP_GT || relation == PURE_OP_LE) && found; /* past the key itself */ + if (side) *to = at < *to ? at : *to; + else *from = at; + } + app->fault = fault, app->fault_pc = fault_pc; + if (*from > *to) *from = *to; + return ok; +} + /* ---- Passes: a shaped fold in a column answered for every row -------- * A fold in a column runs once per row, over its whole list each time. A * shaped one (PureShape) is answered from one pass over the list instead, @@ -1640,7 +1860,7 @@ static Group *group_of(struct PurePass *pass, double key, unsigned how, bool add } size_t at = group_slot(order_bits(key), pass->capacity); while (pass->groups[at].used) at = (at + 1) & (pass->capacity - 1); - pass->groups[at] = (Group){key, {how, 0, false, false}, true}; + pass->groups[at] = (Group){key, {how, 0, false, false, {0}}, true}; ++pass->count; return &pass->groups[at]; } @@ -1664,7 +1884,7 @@ static bool group_pass(const PureModule *m, double *values, PureBlock inner, con if (c[i] == 0) continue; Group *group = group_of(pass, keys[i], how, true); if (!group) return false; - if (!group->fold.done) fold_in(&group->fold, items.start + i, v[i], c[i]); + if (!group->fold.done && !fold_in(&group->fold, items.start + i, v[i], c[i])) return false; } } return true; @@ -1973,6 +2193,7 @@ static PureResult run(const PureModule *m, double *values, PureBlock block, Even 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; + if (at < ev->walk->end && ev->walk->end != SIZE_MAX) --ev->walk->end; } continue; } @@ -2015,15 +2236,22 @@ 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}; + Fold fold = {arg & 0xFF, 0, false, false, {0}}; Event per = *ev; per.outer = ev->row; if (!op->shape || !fold_shaped(m, values, op, list, &per, &fold)) { - status = op->plan ? fold_runs(m, values, inner, 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); + free(fold.seen.keys); if (status != PURE_OK) return status; } - if (!fold.any && fold.how >= PURE_FOLD_MAX) { kind = PURE_FAULT_NOT_FOUND; goto failed; } + if (!fold.any && (fold.how == PURE_FOLD_MAX || fold.how == PURE_FOLD_MIN || fold.how == PURE_FOLD_FIRST)) { + kind = PURE_FAULT_NOT_FOUND; + goto failed; + } if (!isfinite(fold.total)) { kind = PURE_FAULT_NON_FINITE; goto failed; } stack[sp].num = fold.total; stack[sp++].bytes.owner = (uint16_t)(arg >> 8 & 0xFF); /* first: the list the index is in */ @@ -2033,11 +2261,14 @@ static PureResult run(const PureModule *m, double *values, PureBlock block, Even /* 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}; + Walk walk = {arg >> 8 & 0xFF, 0, SIZE_MAX, false}; pc += inner.length; Event per = *ev; per.walk = &walk; - while (walk.at < pure_list_count(app->lists[walk.list])) { + 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])) { size_t mark = arena->used; per.row = walk.at; walk.removed = false; @@ -2734,7 +2965,11 @@ static struct PureRows *filtered(PureApp *app, uint32_t table) { Memo memo; memo.known = 0; if (!argue(app, table, &ev)) return NULL; - for (bool more = pure_list_run(list, 0, &run); more; more = pure_list_next(list, &run)) { + size_t from = 0, to = pure_list_count(list); + if (m->view_range[table]) /* items out of the range fail the filter: they are not read */ + range_bounds(m, (double *)app->values, &m->range[m->view_range[table] - 1], list, + m->state_key[m->view_list[table]] - 1u, &ev, &from, &to); + for (bool more = from < to && pure_list_run(list, from, &run); more && run.start < to; more = pure_list_next(list, &run)) { Lanes keep; if (run_lanes(m, app->values, m->view_code[table], &ev, &run, &keep, store, &memo, NULL)) { const double *kept = lanes_of(&keep, scratch, &run); diff --git a/core/module.h b/core/module.h index b8f8e98..a93cd69 100644 --- a/core/module.h +++ b/core/module.h @@ -57,9 +57,10 @@ enum { PURE_MODULE_LOCALS = 64 }; /* 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; 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 } PureFold; + * max, min and distinct take a value and an include flag from their block + * (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; /* 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; @@ -107,11 +108,13 @@ typedef enum { PURE_FAULT_LIMIT, PURE_FAULT_NOT_FOUND, PURE_FAULT_ENCODING, PURE_FAULT_EXISTS } PureFault; -/* plan and shape are the runtime's, set at load: a fold whose block has a - * form for every instruction that works on a leaf of its list at once runs - * so (plan), and one in a column may be answered for every row from one - * pass over its list (shape: its PureShape + 1). */ -typedef struct { double value; uint32_t arg; uint8_t op, plan, shape; } PureOp; +/* plan, shape and range are the runtime's, set at load: a fold whose block + * has a form for every instruction that works on a leaf of its list at once + * runs so (plan), one in a column may be answered for every row from one + * pass over its list (shape: its PureShape + 1), and a fold or a walk whose + * test bounds a keyed list's key reads only the items in bounds (range: its + * PureRange + 1). */ +typedef struct { double value; uint32_t arg; uint8_t op, plan, shape, range; } 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; uint16_t rows; uint32_t offset; } PureField; @@ -136,6 +139,15 @@ typedef struct { uint16_t first, count; } PureRecord; enum { PURE_SHAPE_GROUP = 1, PURE_SHAPE_RANK = 2, PURE_MODULE_SHAPES = 64 }; typedef struct { uint8_t form, relation; uint16_t field; uint32_t test; PureBlock key; } PureShape; +/* A test (a fold's, a walk's where, a filter) that ANDs comparisons of a + * keyed list's item key with values reading no item: lower (the key GT or + * GE it) and upper (LT or LE; a relation of 0: none; EQ is both). Only the + * items with keys in bounds can pass it, so only those are read: a filter + * leaves the rest out anyway, and a fold's or walk's other parts cannot + * fault (what the skipped items would have run). */ +enum { PURE_MODULE_RANGES = 64 }; +typedef struct { uint8_t lower_relation, upper_relation; PureBlock lower, upper; } PureRange; + typedef struct { uint16_t states, inputs, views, handlers, fields, collections, constants, records, record_fields; uint32_t code_count; @@ -161,6 +173,9 @@ typedef struct { uint8_t view_arguments[PURE_MODULE_VIEWS]; /* the input of a view's arguments + 1 (a column's: its table's), or 0 */ PureShape shape[PURE_MODULE_SHAPES]; uint8_t shapes; + PureRange range[PURE_MODULE_RANGES]; + uint8_t ranges; + uint8_t view_range[PURE_MODULE_VIEWS]; /* a table's filter's PureRange + 1, or 0 */ PureHandler handler[PURE_MODULE_HANDLERS]; /* The code and the text constants, sized to the module in one block * (storage) that load takes and pure_module_release gives back. */ diff --git a/core/test-module.c b/core/test-module.c index 3c9dfa1..846d7aa 100644 --- a/core/test-module.c +++ b/core/test-module.c @@ -2266,7 +2266,7 @@ static void gen_own(Gen *g, int depth) { * key the row gives, ANDed with the item's own tests, and an own value. */ static void gen_shaped(Gen *g, int list) { static const uint8_t relations[] = {PURE_OP_EQ, PURE_OP_EQ, PURE_OP_LT, PURE_OP_LE, PURE_OP_GT, PURE_OP_GE}; - unsigned how = roll(g, 5) < 2 ? PURE_FOLD_COUNT : roll(g, 5), before = roll(g, 3) ? 0 : 1 + roll(g, 2), + unsigned how = roll(g, 5) < 2 ? PURE_FOLD_COUNT : roll(g, 6), before = roll(g, 3) ? 0 : 1 + roll(g, 2), after = roll(g, 3) ? 0 : 1; size_t at = g->count; put_op(g, PURE_OP_FOLD, 0, 0); @@ -2305,7 +2305,7 @@ static void gen_shaped(Gen *g, int list) { /* A fold over list leaving a number (first's index as one), in a column of L (outer) or not. */ static void gen_fold(Gen *g, int list, int outer) { - unsigned how = roll(g, 5); + unsigned how = roll(g, 6); /* count, sum, max, min, first, distinct */ size_t at = g->count; put_op(g, PURE_OP_FOLD, 0, 0); int fold_list = g->fold_list, fold_outer = g->outer; @@ -2424,7 +2424,7 @@ static void lane_folds(void) { pure_module_release(&module_a); pure_module_release(&module_b); } - CHECK(planned > folds / 2 && faults > 100 && cells > 1000 && shaped[PURE_SHAPE_GROUP] > 150 && + CHECK(planned > folds / 2 && faults > 100 && cells > 1000 && shaped[PURE_SHAPE_GROUP] > 80 && shaped[PURE_SHAPE_RANK] > 100 && passes > 60); printf("{\"lane_folds\":%u,\"planned\":%u,\"groups\":%u,\"ranks\":%u,\"passes\":%u,\"faults_alike\":%u," "\"cells\":%u}\n", folds, planned, shaped[PURE_SHAPE_GROUP], shaped[PURE_SHAPE_RANK], passes, faults, cells); @@ -2876,6 +2876,123 @@ static void locals(void) { printf("{\"locals\":{\"events\":80}}\n"); } +/* ---- Key ranges ----------------------------------------------------------- + * Folds, a filter and walks whose tests bound a keyed list's key read only + * the items in bounds; each answers as the same module reading every item: + * two bounds, one, an equality, a bound on the right, a test that may fault + * (no range), a walk that changes and removes items in its range, and a + * walk whose body moves its own bound (no range). */ +enum { R_LO = 0, R_HI = 1, R_N = 2, R_L = 3 }; +static const S range_numbers[] = {{"lo", 0}, {"hi", 0}, {"n", 0}}; +static const T range_lists[] = {{"l", 3 | 1 << 8, 0}}; +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")}; +#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) */ + {FOLD, FOLDING(PURE_FOLD_COUNT, R_L, 9), 0}, {ROW, R_L, 0}, KEYED(0), {L, R_LO, 0}, {PURE_OP_GE, 0, 0}, + {ROW, R_L, 0}, KEYED(0), {L, R_HI, 0}, {PURE_OP_LT, 0, 0}, {PURE_OP_AND, 0, 0}, + /* 10 v1 = sum(x.a for x in l where x.key > lo && x.key <= hi && x.b > 0) */ + {FOLD, FOLDING(PURE_FOLD_SUM, R_L, 16), 0}, {ROW, R_L, 0}, KEYED(1), + {ROW, R_L, 0}, KEYED(0), {L, R_LO, 0}, {GT, 0, 0}, {ROW, R_L, 0}, KEYED(0), {L, R_HI, 0}, {PURE_OP_LE, 0, 0}, + {PURE_OP_AND, 0, 0}, {ROW, R_L, 0}, KEYED(2), {C, 0, 0}, {GT, 0, 0}, {PURE_OP_AND, 0, 0}, + /* 27 v2 = first(x in l where x.key == lo).position */ + {FOLD, FOLDING(PURE_FOLD_FIRST, R_L, 4), 0}, {ROW, R_L, 0}, KEYED(0), {L, R_LO, 0}, {EQ, 0, 0}, {XN, 0, 0}, + /* 33 v3 = min(x.b for x in l where hi > x.key && x.key >= lo) */ + {FOLD, FOLDING(PURE_FOLD_MIN, R_L, 11), 0}, {ROW, R_L, 0}, KEYED(2), + {L, R_HI, 0}, {ROW, R_L, 0}, KEYED(0), {GT, 0, 0}, {ROW, R_L, 0}, KEYED(0), {L, R_LO, 0}, {PURE_OP_GE, 0, 0}, + {PURE_OP_AND, 0, 0}, + /* 45 v4 = count(x in l where x.key >= lo && x.a / x.b > 0): a test that may fault */ + {FOLD, FOLDING(PURE_FOLD_COUNT, R_L, 12), 0}, {ROW, R_L, 0}, KEYED(0), {L, R_LO, 0}, {PURE_OP_GE, 0, 0}, + {ROW, R_L, 0}, KEYED(1), {ROW, R_L, 0}, KEYED(2), {DIV, 0, 0}, {C, 0, 0}, {GT, 0, 0}, {PURE_OP_AND, 0, 0}, + /* 58 table t: each x in l where x.key >= lo && x.key < hi && x.a > 1 */ + {ROW, R_L, 0}, KEYED(0), {L, R_LO, 0}, {PURE_OP_GE, 0, 0}, {ROW, R_L, 0}, KEYED(0), {L, R_HI, 0}, {PURE_OP_LT, 0, 0}, + {PURE_OP_AND, 0, 0}, {ROW, R_L, 0}, KEYED(1), {C, 0, 1}, {GT, 0, 0}, {PURE_OP_AND, 0, 0}, + /* 72 column c = x.b */ + {ROW, R_L, 0}, KEYED(2), + /* 74 on bounds: lo = bounds.lo; hi = bounds.hi */ + {FIELD, 0, 0}, {ST, R_LO, 0}, {FIELD, 1, 0}, {ST, R_HI, 0}, + /* 78 on walk: for x in l where x.key >= lo && x.key < hi { x.a = x.a + 1; if x.b < 0 { l.remove(x) } } */ + {EACH, WALKING(R_L, 23), 0}, + {ROW, R_L, 0}, KEYED(0), {L, R_LO, 0}, {PURE_OP_GE, 0, 0}, {ROW, R_L, 0}, KEYED(0), {L, R_HI, 0}, {PURE_OP_LT, 0, 0}, + {PURE_OP_AND, 0, 0}, {JZ, 102, 0}, + {ROW, R_L, 0}, {ROW, R_L, 0}, KEYED(1), {C, 0, 1}, {ADD, 0, 0}, {IS, ITEM(R_L, 1), 0}, + {ROW, R_L, 0}, KEYED(2), {C, 0, 0}, {PURE_OP_LT, 0, 0}, {JZ, 102, 0}, {ROW, R_L, 0}, {LR, R_L, 0}, + /* 102 on drift: for x in l where x.key < hi { hi = hi - 1; n = n + 1 }: its bound moves */ + {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}, +}; +#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 bool same_lists(const PureApp *a, const PureApp *b) { + const PureList *x = a->lists[R_L], *y = b->lists[R_L]; + if (pure_list_count(x) != pure_list_count(y)) return false; + for (size_t i = 0; i < pure_list_count(x); ++i) + for (unsigned f = 0; f < 3; ++f) + if (pure_list_get(x, i, f).num != pure_list_get(y, i, f).num) return false; + return true; +} + +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, + 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); + 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; + unsigned compared = 0, walked = 0; + for (unsigned round = 0; round < 60; ++round) { + PureApp a, b; + CHECK(pure_app_start(&a, &module_a, (PureData){0}) == PURE_OK && pure_app_start(&b, &module_b, (PureData){0}) == PURE_OK); + double key = (double)(next_random(&seed) % 5); + for (size_t i = 0, items = next_random(&seed) % 400; i < items; ++i) { + key += 1 + next_random(&seed) % 3; + PureCell cells[3] = {{key, NULL, 0}, {(double)(next_random(&seed) % 9) - 3, NULL, 0}, + {(double)(next_random(&seed) % 7) - 3, NULL, 0}}; + CHECK(pure_list_insert(a.lists[R_L], i, cells, NULL) == PURE_OK && pure_list_insert(b.lists[R_L], i, cells, NULL) == PURE_OK); + } + for (unsigned step = 0; step < 12; ++step) { + unsigned char payload[16]; + double lo = (double)(next_random(&seed) % 900) - 50, hi = lo + (double)(next_random(&seed) % 400) - 20; + put_double(payload, lo); + 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) { + 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)) { + fprintf(stderr, "range round %u view %u: %d %g / %d %g\n", round, v, ok_a, x, ok_b, y); + abort(); + } + ++compared; + } + size_t rows = pure_app_rows(&a, 5); + CHECK(rows == pure_app_rows(&b, 5)); + 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); + } + unsigned input = 1 + next_random(&seed) % 2; + 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; + } + pure_app_stop(&a); + pure_app_stop(&b); + } + printf("{\"ranges\":{\"compared\":%u,\"walks\":%u}}\n", compared, walked); +} + /* Damaged fold and filter modules: whatever loads runs safely. */ static void fold_mutations(void) { static unsigned char valid[65536], bytes[65536]; @@ -3801,6 +3918,7 @@ int main(void) { walk_mutations(); view_arguments(); locals(); + ranges(); keyed(); keyed_mutations(); snapshots(); diff --git a/docs/design/008-module-format.md b/docs/design/008-module-format.md index 7fb8641..dbac460 100644 --- a/docs/design/008-module-format.md +++ b/docs/design/008-module-format.md @@ -99,7 +99,7 @@ v5에는 뒤에 집계(FOLD), 걸러진 표, 마크, 그리고 **키 있는 리� | 62 | ROW | → i | 열이 계산하는 행. `인자`는 그 표의 리스트 상태. 열 전용 | | 63 | PICK | … → … v | `인자`개 아래의 값을 복사해 올린다(0이면 맨 위). 타입과 대상도 그대로 | | 64 | SLIDE | … v → v | 맨 위 값 아래의 `인자`개(1 이상)를 버린다 | -| 65 | FOLD | → n 또는 i | 집계. `인자`의 비트 0–7은 종류(0 count, 1 sum, 2 max, 3 min, 4 first), 8–15는 리스트 상태, 16–31은 뒤따르는 블록의 길이 L. 그 L개 명령이 항목마다 그 리스트의 열처럼 돈다(`ROW`가 항목). count는 블록이 남긴 수가 0이 아닌 항목을 세고, sum·max·min은 블록이 남긴 값과 포함 여부(0이 아니면 포함)로 계산한다. first는 블록이 0이 아닌 수를 남긴 첫 항목의 인덱스(그 리스트의 인덱스)이고 거기서 멈춘다. 포함된 항목이 없으면 count·sum은 0, max·min·first는 `not_found` | +| 65 | FOLD | → n 또는 i | 집계. `인자`의 비트 0–7은 종류(0 count, 1 sum, 2 max, 3 min, 4 first, 5 distinct: 포함된 항목의 서로 다른 값의 수, −0은 0), 8–15는 리스트 상태, 16–31은 뒤따르는 블록의 길이 L. 그 L개 명령이 항목마다 그 리스트의 열처럼 돈다(`ROW`가 항목). count는 블록이 남긴 수가 0이 아닌 항목을 세고, sum·max·min은 블록이 남긴 값과 포함 여부(0이 아니면 포함)로 계산한다. first는 블록이 0이 아닌 수를 남긴 첫 항목의 인덱스(그 리스트의 인덱스)이고 거기서 멈춘다. 포함된 항목이 없으면 count·sum은 0, max·min·first는 `not_found` | | 66 | TEXT_COMPARE | t t → n | 바이트 순서로 비교해 0 또는 1. `인자`는 관계(0 LT, 1 LE, 2 GT, 3 GE, 4 EQ, 5 NE, 수 비교 명령의 순서). 앞이 같으면 짧은 쪽이 앞이다 | | 67 | LIST_FIND | k → i | 키 있는 리스트 `인자`에서 키가 k인 항목의 인덱스. 반씩 나눠 찾는다. 없으면 `not_found` | | 68 | LIST_HAS | k → n | 그 키의 항목이 있으면 1, 없으면 0 | @@ -184,6 +184,13 @@ text, 끝이 맞지 않는 바이트는 메시지를 `limit`으로 실패시킨� 인자는 잎 단위 실행에서 모두에 같은 값이고, 한 번의 통과로 답하는 열의 집계(PureShape)에서는 행이 주는 키 쪽에만 올 수 있다 (통과는 인자에 따라 달라지지 않는다). +**키 범위.** 걸러진 표의 필터, 집계, 걷기의 where(블록 처음의 조건과, 거짓이면 블록 끝으로 가는 JZ)가 키 있는 리스트의 키를 항목을 +읽지 않는 값과 비교하는 조건들(`>=`·`>`와 `<`·`<=`, `==`)을 AND로 가지면, 로드할 때 그 범위를 기록하고 실행할 때 경계 값을 한 번 +계산해 키로 찾은 위치 사이의 항목만 읽는다(O(log n + k)). 범위 밖 항목은 그 조건에서 떨어지므로 필터에서는 언제나 같다(결함 난 +항목도 빠진다). 집계와 걷기에는 나머지 부분이 결함을 낼 수 없을 때만 쓴다(나누기, 넘칠 수 있는 합·곱, 없을 수 있는 키가 없다): +건너뛴 항목이 돌렸을 일이 없어야 하기 때문이다. 걷기의 경계는 블록이 쓰는 상태·지역 칸·리스트를 읽지 않을 때만 쓴다(경계는 +걷기 전에 한 번 계산하고, where는 항목마다 다시 읽는다). 경계가 결함을 내면 범위 없이 쓰인 대로 돈다. + **지역 칸.** 이벤트는 수나 인덱스를 담는 칸 64개를 0으로 시작해 핸들러들과 그 안의 걷기·집계가 함께 쓴다(LOCAL_LOAD·LOCAL_STORE). 상태가 아니라 저장되지 않고, 이름공간을 쓰지 않으며, 보기에는 없다. 한 칸은 한 핸들러에서 한 가지로 쓰여 검증된 타입을 지킨다. 잎 단위 실행에서는 모두에 같은 값이고, 한 번의 통과로 답하는 집계에서는 키 쪽에만 온다. |