aboutsummaryrefslogtreecommitdiffstats
path: root/core
diff options
context:
space:
mode:
Diffstat (limited to 'core')
-rw-r--r--core/module-list.c53
-rw-r--r--core/module-list.h13
-rw-r--r--core/module.c455
-rw-r--r--core/module.h5
-rw-r--r--core/test-module.c207
5 files changed, 685 insertions, 48 deletions
diff --git a/core/module-list.c b/core/module-list.c
index 6e13de0..55c6812 100644
--- a/core/module-list.c
+++ b/core/module-list.c
@@ -23,7 +23,7 @@
* (the path) and retires the ones it replaced, and retires a text it lets go
* instead of freeing it. A share is then a root and a count, however long
* the list. */
-enum { FANOUT = 32, DEPTH = 16, SPARE_NODES = 8 };
+enum { FANOUT = PURE_LIST_RUN, DEPTH = 16, SPARE_NODES = 8 };
typedef struct Node {
uint64_t made; /* the list's share count when made: shared once below it */
@@ -720,16 +720,55 @@ PureCell pure_list_get(const PureList *list, size_t at, unsigned field) {
return cell_at(&list->layout, leaf_of(list, at, &within), (unsigned)within, field);
}
-bool pure_list_run(const PureList *list, size_t at, PureRun *run) {
- const Layout *l = &list->layout;
- if (at >= list->count) return false;
- size_t within;
- const Node *leaf = leaf_of(list, at, &within);
- run->start = at - within;
+static void open_run(const Layout *l, const Node *leaf, PureRun *run) {
run->count = leaf->count;
for (unsigned f = 0; f < l->fields; ++f)
if (l->text_fields[f]) run->column[f].texts = texts(l, leaf, f);
else run->column[f].numbers = numbers(l, leaf, f);
+}
+
+bool pure_list_run(const PureList *list, size_t at, PureRun *run) {
+ if (at >= list->count) return false;
+ const Node *node = list->root;
+ size_t start = 0;
+ unsigned depth = 0;
+ while (!node->leaf) {
+ unsigned i = 0;
+ while (i + 1 < node->count && at - start >= child(node, i)->items) start += child(node, i)->items, ++i;
+ run->path[depth] = node;
+ run->taken[depth++] = (uint8_t)i;
+ node = child(node, i);
+ }
+ run->path[depth] = node;
+ run->depth = depth;
+ run->start = start;
+ open_run(&list->layout, node, run);
+ return true;
+}
+
+/* Up to the nearest node with a child after the one taken, then down its
+ * first children to a leaf. The leaf after it (a sibling) is fetched ahead:
+ * leaves copied at different times lie far apart in memory. */
+bool pure_list_next(const PureList *list, PureRun *run) {
+ size_t start = run->start + run->count;
+ unsigned depth = run->depth;
+ while (depth && run->taken[depth - 1] + 1u >= ((const Node *)run->path[depth - 1])->count) --depth;
+ if (!depth) return false;
+ const Node *parent = run->path[depth - 1], *node = child(parent, ++run->taken[depth - 1]);
+ while (!node->leaf) {
+ run->path[depth] = parent = node;
+ run->taken[depth++] = 0;
+ node = child(node, 0);
+ }
+ unsigned after = run->taken[depth - 1] + 1u;
+ if (after < parent->count) {
+ const char *leaf = (const char *)child(parent, after);
+ for (size_t at = 0; at < list->layout.leaf_size; at += 64) __builtin_prefetch(leaf + at);
+ }
+ run->path[depth] = node;
+ run->depth = depth;
+ run->start = start;
+ open_run(&list->layout, node, run);
return true;
}
diff --git a/core/module-list.h b/core/module-list.h
index a3f4ad6..e370b97 100644
--- a/core/module-list.h
+++ b/core/module-list.h
@@ -37,9 +37,14 @@ typedef struct {
size_t start;
unsigned count;
union { const double *numbers; const PureSpan *texts; } column[16];
+ /* Where the run is in the list's tree, for the next one. */
+ const void *path[16];
+ uint8_t taken[16];
+ unsigned depth;
} PureRun;
-enum { PURE_LIST_ITEMS = 1 << 24 };
+/* A list holds up to PURE_LIST_ITEMS items, a run up to PURE_LIST_RUN. */
+enum { PURE_LIST_ITEMS = 1 << 24, PURE_LIST_RUN = 32 };
PureList *pure_list_new(unsigned fields, const uint8_t *text_fields);
void pure_list_free(PureList *);
@@ -63,9 +68,11 @@ PureResult pure_list_insert(PureList *, size_t at, const PureCell *cells, PureUn
PureResult pure_list_remove(PureList *, size_t at, PureUndo *);
PureResult pure_list_set(PureList *, size_t at, unsigned field, PureCell value, PureUndo *);
PureCell pure_list_get(const PureList *, size_t at, unsigned field);
-/* The run holding position at (false past the end): for reading item after
- * item without finding each. Valid until the list changes. */
+/* The run holding position at (false past the end), and the run after
+ * run (false at the end): for reading item after item without finding each.
+ * Valid until the list changes. */
bool pure_list_run(const PureList *, size_t at, PureRun *);
+bool pure_list_next(const PureList *, PureRun *);
/* In a list ordered by field (a keyed list): the first position whose item's
* field does not order below key (numbers by value, texts by bytes), and
* whether that item's field is key. */
diff --git a/core/module.c b/core/module.c
index 32d0629..36e13c3 100644
--- a/core/module.c
+++ b/core/module.c
@@ -399,6 +399,40 @@ PURE_COLD static const char *verify_block(const PureModule *m, PureBlock block,
return why;
}
+/* Whether an instruction has a form that works on the items of a run at
+ * once: numbers and indexes, with no branch and no text. */
+PURE_COLD static bool has_lanes(const PureModule *m, const PureOp *op) {
+ switch (op->op) {
+ case PURE_OP_CONST: case PURE_OP_ADD: case PURE_OP_SUB: case PURE_OP_MUL: case PURE_OP_DIV: case PURE_OP_NEG:
+ 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_MIN: case PURE_OP_MAX: case PURE_OP_CLAMP:
+ case PURE_OP_FLOOR: case PURE_OP_MOD: case PURE_OP_LOAD: case PURE_OP_LIST_COUNT: case PURE_OP_INDEX_LOAD:
+ case PURE_OP_INDEX_MOVE: case PURE_OP_INDEX_FIRST: case PURE_OP_INDEX_LAST: case PURE_OP_INDEX_NUM:
+ case PURE_OP_ROW: case PURE_OP_OUTER_ROW: case PURE_OP_PICK: case PURE_OP_SLIDE:
+ return true;
+ case PURE_OP_ITEM_GET: return field_type(m, list_of(op->arg), item_field(op->arg)) == T_NUM;
+ case PURE_OP_LIST_FIND: case PURE_OP_LIST_HAS: return field_type(m, op->arg, m->state_key[op->arg] - 1u) == T_NUM;
+ default: return false;
+ }
+}
+
+PURE_COLD static bool block_has_lanes(const PureModule *m, PureBlock block) {
+ for (uint32_t pc = block.start; pc < block.start + block.length; ++pc)
+ if (!has_lanes(m, &m->code[pc])) return false;
+ return true;
+}
+
+/* A fold in a verified block whose own block has lane forms throughout runs
+ * a leaf of its list at a time. */
+PURE_COLD static void plan_folds(PureModule *m, PureBlock block) {
+ for (uint32_t pc = block.start; pc < block.start + block.length; ++pc) {
+ PureOp *op = &m->code[pc];
+ if (op->op != PURE_OP_FOLD) continue;
+ op->plan = block_has_lanes(m, (PureBlock){pc + 1, op->arg >> 16});
+ pc += op->arg >> 16;
+ }
+}
+
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;
@@ -668,6 +702,12 @@ PURE_COLD PureResult pure_module_load(const void *bytes, size_t size, PureModule
bad = i;
if ((why = verify_block(out, out->handler[i].code, -1, -1, -1, out->handler[i].event, &bad))) goto refused;
}
+ for (uint32_t i = 0; i < out->views; ++i) {
+ plan_folds(out, out->view_code[i]);
+ out->view_plan[i] = out->view_type[i] == PURE_VIEW_TABLE && out->view_code[i].length &&
+ block_has_lanes(out, out->view_code[i]);
+ }
+ for (uint32_t i = 0; i < out->handlers; ++i) plan_folds(out, out->handler[i].code);
return PURE_OK;
refused:
if (error_size) snprintf(error, error_size, "%s (%u)", why, bad);
@@ -906,6 +946,339 @@ static PureResult send(PureApp *app, uint32_t output, const Slot *fields, const
return PURE_OK;
}
+static PureResult run(const PureModule *m, double *values, PureBlock block, Event *ev, Slot *result);
+
+/* ---- Folds and filters a leaf at a time ------------------------------
+ * A block whose instructions all have lane forms (has_lanes) runs for a run
+ * of its list's items at once: each value is one per item (a lane), the
+ * items' own positions, or one for all. An item for which run would fault
+ * makes the whole run go again item by item through run, so a fold faults,
+ * and a filter leaves an item out, exactly as they would have; the lanes
+ * only see what run would compute. */
+typedef struct {
+ const double *lane; /* a value per item, or NULL */
+ double value; /* without lanes: the value for all */
+ bool rows; /* without lanes: the items' own positions */
+ uint16_t owner; /* an index's list */
+} Lanes;
+
+static bool uniform(const Lanes *v) { return !v->lane && !v->rows; }
+
+/* A lookup by a value for all items reads no item of the run: every run of
+ * a fold (or a filter) finds the same, so it is made once, by instruction. */
+enum { MEMO = 64 };
+typedef struct { double value[MEMO]; uint64_t known; } Memo;
+
+static bool recalled(const Memo *memo, uint32_t slot, double *value) {
+ if (slot >= MEMO || !(memo->known >> slot & 1)) return false;
+ *value = memo->value[slot];
+ return true;
+}
+
+static void remember(Memo *memo, uint32_t slot, double value) {
+ if (slot >= MEMO) return;
+ memo->value[slot] = value;
+ memo->known |= (uint64_t)1 << slot;
+}
+
+/* A value per item, in scratch when it is not one already. */
+static const double *lanes_of(const Lanes *v, double *scratch, const PureRun *items) {
+ if (v->lane) return v->lane;
+ for (unsigned i = 0; i < items->count; ++i) scratch[i] = v->rows ? (double)(items->start + i) : v->value;
+ return scratch;
+}
+
+/* a op b as run computes it; false where run faults. */
+static bool number_op(uint8_t op, double a, double b, double *out) {
+ double value;
+ switch (op) {
+ case PURE_OP_ADD: value = a + b; break;
+ case PURE_OP_SUB: value = a - b; break;
+ case PURE_OP_MUL: value = a * b; break;
+ case PURE_OP_DIV:
+ if (b == 0) return false;
+ value = a / b;
+ break;
+ case PURE_OP_LT: value = a < b; break;
+ case PURE_OP_LE: value = a <= b; break;
+ case PURE_OP_GT: value = a > b; break;
+ case PURE_OP_GE: value = a >= b; break;
+ case PURE_OP_EQ: value = a == b; break;
+ case PURE_OP_NE: value = a != b; break;
+ case PURE_OP_AND: value = a != 0 && b != 0; break;
+ case PURE_OP_OR: value = a != 0 || b != 0; break;
+ case PURE_OP_MIN: value = minimum(a, b); break;
+ case PURE_OP_MOD:
+ if (b == 0) return false;
+ value = fmod(a, b);
+ if (value != 0 && (value < 0) != (b < 0)) value += b;
+ else if (value == 0) value = copysign(0.0, b);
+ break;
+ default: value = maximum(a, b); break;
+ }
+ *out = value;
+ return isfinite(value);
+}
+
+/* a op b for every item into out: a loop per operation, reading a value for
+ * all with stride 0. false where run faults for some item. */
+static bool lanes_op(uint8_t op, const double *a, size_t sa, const double *b, size_t sb, double *out, unsigned n) {
+ bool bad = false;
+#define EACH(expr) for (unsigned i = 0; i < n; ++i) { double x = a[i * sa], y = b[i * sb]; out[i] = (expr); }
+ switch (op) {
+ case PURE_OP_ADD: EACH(x + y) break;
+ case PURE_OP_SUB: EACH(x - y) break;
+ case PURE_OP_MUL: EACH(x * y) break;
+ case PURE_OP_LT: EACH(x < y) return true;
+ case PURE_OP_LE: EACH(x <= y) return true;
+ case PURE_OP_GT: EACH(x > y) return true;
+ case PURE_OP_GE: EACH(x >= y) return true;
+ case PURE_OP_EQ: EACH(x == y) return true;
+ case PURE_OP_NE: EACH(x != y) return true;
+ case PURE_OP_AND: EACH(x != 0 && y != 0) return true;
+ case PURE_OP_OR: EACH(x != 0 || y != 0) return true;
+ case PURE_OP_MIN: EACH(minimum(x, y)) return true;
+ case PURE_OP_MAX: EACH(maximum(x, y)) return true;
+ default:
+ for (unsigned i = 0; i < n; ++i) bad |= !number_op(op, a[i * sa], b[i * sb], &out[i]);
+ return !bad;
+ }
+#undef EACH
+ for (unsigned i = 0; i < n; ++i) bad |= !isfinite(out[i]);
+ return !bad;
+}
+
+/* The block for the items of a run at once, as a column of their list:
+ * result holds what it leaves (lanes may point into store, a row of lanes
+ * per stack depth, or into the list's leaf). false when run would fault for
+ * some item. */
+static bool run_lanes(const PureModule *m, const double *values, PureBlock block, const Event *ev, const PureRun *items,
+ Lanes *result, double (*store)[PURE_LIST_RUN], Memo *memo) {
+ PureApp *app = ev->app;
+ Lanes stack[PURE_MODULE_STACK];
+ double scratch[2][PURE_LIST_RUN];
+ size_t sp = 0;
+ unsigned n = items->count;
+ for (uint32_t pc = block.start, end = block.start + block.length; pc < end; ++pc) {
+ const PureOp *op = &m->code[pc];
+ uint32_t arg = op->arg;
+ Lanes *top = sp ? &stack[sp - 1] : stack;
+ double *out = store[sp ? sp - 1 : 0]; /* where the top's new lanes go */
+ switch (op->op) {
+ case PURE_OP_CONST: stack[sp++] = (Lanes){NULL, op->value, false, 0}; continue;
+ case PURE_OP_LOAD: stack[sp++] = (Lanes){NULL, values[arg], false, 0}; continue;
+ case PURE_OP_INDEX_LOAD: stack[sp++] = (Lanes){NULL, values[arg], false, m->state_ref[arg]}; continue;
+ case PURE_OP_ROW: stack[sp++] = (Lanes){NULL, 0, true, (uint16_t)arg}; continue;
+ case PURE_OP_OUTER_ROW: stack[sp++] = (Lanes){NULL, (double)ev->outer, false, (uint16_t)arg}; continue;
+ case PURE_OP_LIST_COUNT: stack[sp++] = (Lanes){NULL, (double)pure_list_count(app->lists[arg]), false, 0}; continue;
+ case PURE_OP_INDEX_FIRST: case PURE_OP_INDEX_LAST: {
+ size_t last = op->op == PURE_OP_INDEX_LAST ? pure_list_count(app->lists[arg]) : 0;
+ stack[sp++] = (Lanes){NULL, last ? (double)(last - 1) : 0, false, (uint16_t)arg};
+ continue;
+ }
+ case PURE_OP_INDEX_NUM: continue;
+ case PURE_OP_PICK: stack[sp] = stack[sp - 1 - arg]; ++sp; continue;
+ case PURE_OP_SLIDE: {
+ /* The top moves down: lanes kept in a depth it leaves come along. */
+ Lanes moved = stack[sp - 1];
+ size_t to = sp - 1 - arg;
+ if ((uintptr_t)moved.lane >= (uintptr_t)store[to + 1] && (uintptr_t)moved.lane < (uintptr_t)store[sp]) {
+ memcpy(store[to], moved.lane, n * sizeof(double));
+ moved.lane = store[to];
+ }
+ stack[to] = moved;
+ sp = to + 1;
+ continue;
+ }
+ case PURE_OP_ITEM_GET: {
+ uint32_t list = list_of(arg), field = item_field(arg);
+ const PureList *from = app->lists[list];
+ size_t count = pure_list_count(from);
+ if (top->rows) { /* the items themselves: the leaf's column */
+ *top = (Lanes){items->column[field].numbers, 0, false, 0};
+ continue;
+ }
+ if (!top->lane) {
+ top->owner = 0;
+ if (recalled(memo, pc - block.start, &top->value)) continue;
+ if (top->value >= (double)count) return false;
+ top->value = pure_list_get(from, (size_t)top->value, field).num;
+ remember(memo, pc - block.start, top->value);
+ continue;
+ }
+ for (unsigned i = 0; i < n; ++i) {
+ if (top->lane[i] >= (double)count) return false;
+ out[i] = pure_list_get(from, (size_t)top->lane[i], field).num;
+ }
+ *top = (Lanes){out, 0, false, 0};
+ continue;
+ }
+ case PURE_OP_LIST_FIND: case PURE_OP_LIST_HAS: {
+ const PureList *keyed = app->lists[arg];
+ unsigned key = m->state_key[arg] - 1u;
+ bool find = op->op == PURE_OP_LIST_FIND, found;
+ if (uniform(top)) {
+ double value;
+ if (!recalled(memo, pc - block.start, &value)) {
+ size_t at = pure_list_seek(keyed, key, (PureCell){top->value, NULL, 0}, &found);
+ if (find && !found) return false;
+ remember(memo, pc - block.start, value = find ? (double)at : found);
+ }
+ *top = (Lanes){NULL, value, false, find ? (uint16_t)arg : 0};
+ continue;
+ }
+ const double *keys = lanes_of(top, scratch[0], items);
+ for (unsigned i = 0; i < n; ++i) {
+ size_t at = pure_list_seek(keyed, key, (PureCell){keys[i], NULL, 0}, &found);
+ if (find && !found) return false;
+ out[i] = find ? (double)at : found;
+ }
+ *top = (Lanes){out, 0, false, find ? (uint16_t)arg : 0};
+ continue;
+ }
+ case PURE_OP_INDEX_MOVE: {
+ Lanes by = stack[--sp];
+ top = &stack[sp - 1];
+ out = store[sp - 1];
+ size_t count = pure_list_count(app->lists[top->owner]);
+ double last = count ? (double)(count - 1) : 0;
+ if (uniform(top) && uniform(&by)) {
+ if (by.value != floor(by.value)) return false;
+ top->value = maximum(0, minimum(top->value + by.value, last));
+ continue;
+ }
+ const double *at = lanes_of(top, scratch[0], items), *step = lanes_of(&by, scratch[1], items);
+ for (unsigned i = 0; i < n; ++i) {
+ if (step[i] != floor(step[i])) return false;
+ out[i] = maximum(0, minimum(at[i] + step[i], last));
+ }
+ *top = (Lanes){out, 0, false, top->owner};
+ continue;
+ }
+ case PURE_OP_NEG: case PURE_OP_NOT: case PURE_OP_FLOOR: {
+ if (uniform(top)) {
+ top->value = op->op == PURE_OP_NEG ? -top->value : op->op == PURE_OP_NOT ? top->value == 0 : floor(top->value);
+ top->owner = 0;
+ continue;
+ }
+ const double *a = lanes_of(top, scratch[0], items);
+ if (op->op == PURE_OP_NEG) for (unsigned i = 0; i < n; ++i) out[i] = -a[i];
+ else if (op->op == PURE_OP_NOT) for (unsigned i = 0; i < n; ++i) out[i] = a[i] == 0;
+ else for (unsigned i = 0; i < n; ++i) out[i] = floor(a[i]);
+ *top = (Lanes){out, 0, false, 0};
+ continue;
+ }
+ case PURE_OP_CLAMP: {
+ Lanes high = stack[--sp], low = stack[--sp];
+ top = &stack[sp - 1];
+ out = store[sp - 1];
+ if (uniform(top) && uniform(&low) && uniform(&high)) {
+ if (low.value > high.value) return false;
+ top->value = maximum(low.value, minimum(top->value, high.value));
+ continue;
+ }
+ double spare[PURE_LIST_RUN];
+ const double *x = lanes_of(top, scratch[0], items), *lo = lanes_of(&low, scratch[1], items),
+ *hi = lanes_of(&high, spare, items);
+ for (unsigned i = 0; i < n; ++i) {
+ if (lo[i] > hi[i]) return false;
+ out[i] = maximum(lo[i], minimum(x[i], hi[i]));
+ }
+ *top = (Lanes){out, 0, false, 0};
+ continue;
+ }
+ default: { /* two numbers */
+ Lanes b = stack[--sp];
+ top = &stack[sp - 1];
+ out = store[sp - 1];
+ if (uniform(top) && uniform(&b)) {
+ if (!number_op(op->op, top->value, b.value, &top->value)) return false;
+ top->owner = 0;
+ continue;
+ }
+ const double *x = top->rows ? lanes_of(top, scratch[0], items) : top->lane ? top->lane : &top->value;
+ const double *y = b.rows ? lanes_of(&b, scratch[1], items) : b.lane ? b.lane : &b.value;
+ if (!lanes_op(op->op, x, uniform(top) ? 0 : 1, y, uniform(&b) ? 0 : 1, out, n)) return false;
+ *top = (Lanes){out, 0, false, 0};
+ continue;
+ }
+ }
+ }
+ memcpy(result, stack, sp * sizeof(*stack));
+ 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;
+
+/* 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;
+ unsigned how = fold->how;
+ if (how == PURE_FOLD_FIRST) {
+ fold->total = (double)row;
+ fold->any = fold->done = true;
+ return;
+ }
+ 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;
+}
+
+/* The fold's block for its items from first to last, one at a time. */
+static PureResult fold_rows(const PureModule *m, double *values, PureBlock inner, Event *per, size_t first,
+ size_t last, Fold *fold) {
+ bool one = fold->how == PURE_FOLD_COUNT || fold->how == PURE_FOLD_FIRST;
+ for (size_t row = first; row < last && !fold->done; ++row) {
+ Slot out[2];
+ size_t mark = per->arena->used;
+ per->row = row;
+ 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);
+ }
+ return PURE_OK;
+}
+
+/* The fold's block a leaf of its list at a time; a run where an item would
+ * 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) {
+ 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)) {
+ Lanes out[2];
+ if (!run_lanes(m, values, inner, per, &items, out, store, &memo)) {
+ PureResult status = fold_rows(m, values, inner, per, items.start, items.start + items.count, fold);
+ if (status != PURE_OK) return status;
+ continue;
+ }
+ const Lanes *counts = &out[one ? 0 : 1];
+ if (uniform(counts) && counts->value == 0) continue;
+ 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;
+ 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)
+ 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) fold_in(fold, items.start + i, v[i], c[i]);
+ }
+ return PURE_OK;
+}
+
static PureResult run(const PureModule *m, double *values, PureBlock block, Event *ev, Slot *result) {
Slot stack[PURE_MODULE_STACK];
size_t sp = 0;
@@ -1157,32 +1530,20 @@ static PureResult run(const PureModule *m, double *values, PureBlock block, Even
continue;
}
case PURE_OP_FOLD: {
- /* The block that follows runs once per item, as a column of the list. */
- unsigned how = arg & 0xFF;
+ /* The block that follows runs once per item, as a column of the
+ * list: a leaf of it at a time when planned so. */
PureBlock inner = {pc, arg >> 16};
PureList *list = app->lists[arg >> 8 & 0xFF];
pc += inner.length;
- double total = 0;
- bool any = false;
+ Fold fold = {arg & 0xFF, 0, false, false};
Event per = *ev;
per.outer = ev->row;
- 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 || how == PURE_FOLD_FIRST ? value == 0 : out[1].num == 0) continue;
- if (how == PURE_FOLD_FIRST) { total = (double)row; any = true; break; }
- 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;
+ status = op->plan ? fold_runs(m, values, inner, list, &per, &fold)
+ : fold_rows(m, values, inner, &per, 0, pure_list_count(list), &fold);
+ if (status != PURE_OK) return status;
+ if (!fold.any && fold.how >= PURE_FOLD_MAX) { 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 */
continue;
}
@@ -1766,6 +2127,24 @@ static PureResult evaluate(PureApp *app, uint32_t view, size_t row, Slot *out) {
return result;
}
+static bool keep_row(struct PureRows *rows, size_t item) {
+ if (rows->count == rows->capacity) {
+ size_t capacity = rows->capacity ? 2 * rows->capacity : 16;
+ size_t *grown = realloc(rows->items, capacity * sizeof(*grown));
+ if (!grown) return false;
+ rows->items = grown;
+ rows->capacity = capacity;
+ }
+ rows->items[rows->count++] = item;
+ return true;
+}
+
+/* The item kept when the filter, run for it alone, keeps it; false without room. */
+static bool keep_evaluated(PureApp *app, uint32_t table, struct PureRows *rows, size_t item) {
+ Slot kept;
+ return evaluate(app, table, item, &kept) != PURE_OK || kept.num == 0 || keep_row(rows, item);
+}
+
/* A filtered table's items, as fresh as the app's states: the filter runs
* once per item after each change (an item it fails on is left out), not
* once per cell. NULL for a table without a filter, or without room. */
@@ -1783,18 +2162,28 @@ static struct PureRows *filtered(PureApp *app, uint32_t table) {
}
if (rows->changes == app->changes) return rows;
rows->count = 0;
- for (size_t item = 0, items = pure_list_count(app->lists[m->view_list[table]]); item < items; ++item) {
- Slot keep;
- if (evaluate(app, table, item, &keep) != PURE_OK || keep.num == 0) continue;
- if (rows->count == rows->capacity) {
- size_t capacity = rows->capacity ? 2 * rows->capacity : 16;
- size_t *grown = realloc(rows->items, capacity * sizeof(*grown));
- if (!grown) return NULL;
- rows->items = grown;
- rows->capacity = capacity;
- }
- rows->items[rows->count++] = item;
- }
+ /* A leaf of the list at a time when the filter has lane forms; a leaf
+ * where an item would fault goes item by item, leaving that item out. */
+ const PureList *list = app->lists[m->view_list[table]];
+ PureRun run;
+ if (m->view_plan[table]) {
+ double store[PURE_MODULE_STACK][PURE_LIST_RUN], scratch[PURE_LIST_RUN];
+ Event ev = {.app = app, .arena = &app->view_arena};
+ Memo memo;
+ memo.known = 0;
+ for (bool more = pure_list_run(list, 0, &run); more; more = pure_list_next(list, &run)) {
+ Lanes keep;
+ if (run_lanes(m, app->values, m->view_code[table], &ev, &run, &keep, store, &memo)) {
+ const double *kept = lanes_of(&keep, scratch, &run);
+ for (unsigned i = 0; i < run.count; ++i)
+ if (kept[i] != 0 && !keep_row(rows, run.start + i)) return NULL;
+ } else
+ for (size_t item = run.start; item < run.start + run.count; ++item)
+ if (!keep_evaluated(app, table, rows, item)) return NULL;
+ }
+ } else
+ for (size_t item = 0, items = pure_list_count(list); item < items; ++item)
+ if (!keep_evaluated(app, table, rows, item)) return NULL;
rows->changes = app->changes;
return rows;
}
diff --git a/core/module.h b/core/module.h
index 328c358..9a491c9 100644
--- a/core/module.h
+++ b/core/module.h
@@ -84,7 +84,9 @@ typedef enum {
PURE_FAULT_LIMIT, PURE_FAULT_NOT_FOUND, PURE_FAULT_ENCODING, PURE_FAULT_EXISTS
} PureFault;
-typedef struct { double value; uint32_t arg; uint8_t op; } PureOp;
+/* plan is 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. */
+typedef struct { double value; uint32_t arg; uint8_t op, plan; } 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; uint32_t offset; } PureField;
@@ -120,6 +122,7 @@ typedef struct {
uint16_t view_table[PURE_MODULE_VIEWS]; /* a column's table view + 1, or 0 */
uint16_t view_list[PURE_MODULE_VIEWS]; /* the list of a table or column */
PureBlock view_code[PURE_MODULE_VIEWS];
+ uint8_t view_plan[PURE_MODULE_VIEWS]; /* a table's filter runs a leaf of its list at once (as a fold may) */
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 e6df3ad..b222597 100644
--- a/core/test-module.c
+++ b/core/test-module.c
@@ -950,15 +950,30 @@ static void model_copy(Model *to, const Model *from) {
if (from->count) memcpy(to->items, from->items, from->count * sizeof(*to->items));
}
+static bool same_item(const Model *m, size_t i, double key, PureSpan text) {
+ return key == m->items[i].key && text.size == m->items[i].size && (!text.size || !memcmp(text.data, m->items[i].text, text.size));
+}
+
+/* The items by position, and run after run from the first and from a middle one. */
static bool same_items(const PureList *list, const Model *m) {
if (pure_list_count(list) != m->count) return false;
for (size_t i = 0; i < m->count; ++i) {
PureCell key = pure_list_get(list, i, 0), text = pure_list_get(list, i, 1);
- if (key.num != m->items[i].key || text.size != m->items[i].size ||
- (text.size && memcmp(text.text, m->items[i].text, text.size)))
- return false;
+ if (!same_item(m, i, key.num, (PureSpan){text.text, text.size})) return false;
}
- return true;
+ PureRun run;
+ for (size_t from = 0; from < m->count; from += m->count / 2 + 1) {
+ size_t at = 0;
+ bool more = pure_list_run(list, from, &run);
+ if (!more || from < run.start || from >= run.start + run.count) return false;
+ for (at = run.start; more; more = pure_list_next(list, &run)) {
+ if (run.start != at || !run.count || run.count > PURE_LIST_RUN) return false;
+ for (unsigned i = 0; i < run.count; ++i, ++at)
+ if (!same_item(m, at, run.column[0].numbers[i], run.column[1].texts[i])) return false;
+ }
+ if (at != m->count) return false;
+ }
+ return !pure_list_run(list, m->count, &run);
}
typedef struct { unsigned char *bytes; size_t size, capacity; } Grown;
@@ -2159,6 +2174,189 @@ static void filters(void) {
}
}
+/* ---- Folds and filters a leaf at a time --------------------------------
+ * Random well-typed folds (plain views, a table's columns reading their row,
+ * a handler storing them), filters and lists: a module whose folds run a
+ * leaf at a time answers bit for bit as the same module run item by item,
+ * faults included (their kind and instruction). */
+typedef struct { O code[8192]; size_t count; uint32_t seed; int fold_list, outer; } Gen;
+enum { LANE_K = 0, LANE_L = 4, LANE_M = 5 };
+
+static void put_op(Gen *g, uint8_t op, uint32_t arg, double value) {
+ CHECK(g->count < LEN(g->code));
+ g->code[g->count++] = (O){op, arg, value};
+}
+
+static unsigned roll(Gen *g, unsigned n) { return next_random(&g->seed) % n; }
+
+static void gen_num(Gen *g, int depth);
+
+/* An index of list: the fold's item, the column's row, a key found, an end, or one moved. */
+static void gen_index(Gen *g, int list, int depth) {
+ unsigned choice = roll(g, depth <= 0 ? 3 : 7);
+ if (choice == 0 && list == g->fold_list) put_op(g, PURE_OP_ROW, (uint32_t)list, 0);
+ else if (choice == 1 && list == LANE_L && g->outer >= 0) put_op(g, PURE_OP_OUTER_ROW, LANE_L, 0);
+ else if (choice >= 3 && choice <= 4 && list == LANE_L) {
+ gen_num(g, depth - 1);
+ put_op(g, PURE_OP_LIST_FIND, LANE_L, 0);
+ } else if (choice == 5) {
+ gen_index(g, list, depth - 1);
+ gen_num(g, depth - 1);
+ put_op(g, PURE_OP_INDEX_MOVE, 0, 0);
+ } else
+ put_op(g, roll(g, 2) ? PURE_OP_INDEX_FIRST : PURE_OP_INDEX_LAST, (uint32_t)list, 0);
+}
+
+static void gen_num(Gen *g, int depth) {
+ static const double pool[] = {0, -0.0, 1, -1, 2, 0.5, 3, 7, 100, -3.5, 1e308, -1e308, 4, 10};
+ static const uint8_t binary[] = {PURE_OP_ADD, PURE_OP_SUB, PURE_OP_MUL, PURE_OP_DIV, PURE_OP_LT, PURE_OP_LE,
+ PURE_OP_GT, PURE_OP_GE, PURE_OP_EQ, PURE_OP_NE, PURE_OP_AND, PURE_OP_OR,
+ PURE_OP_MIN, PURE_OP_MAX, PURE_OP_MOD};
+ static const uint8_t unary[] = {PURE_OP_NEG, PURE_OP_NOT, PURE_OP_FLOOR};
+ switch (roll(g, depth <= 0 ? 4 : 12)) {
+ case 0: put_op(g, C, 0, pool[roll(g, LEN(pool))]); return;
+ case 1: put_op(g, L, LANE_K, 0); return;
+ case 2: case 3: { /* a field of an item */
+ int list = depth <= 0 || roll(g, 3) ? g->fold_list : roll(g, 2) ? LANE_L : LANE_M;
+ gen_index(g, list, depth - 1);
+ put_op(g, PURE_OP_ITEM_GET, (uint32_t)list | (uint32_t)roll(g, list == LANE_L ? 3 : 2) << 16, 0);
+ return;
+ }
+ case 4: put_op(g, PURE_OP_LIST_COUNT, roll(g, 2) ? LANE_L : LANE_M, 0); return;
+ case 5:
+ gen_index(g, roll(g, 2) ? LANE_L : LANE_M, depth - 1);
+ put_op(g, PURE_OP_INDEX_NUM, 0, 0);
+ return;
+ case 6: gen_num(g, depth - 1); put_op(g, PURE_OP_LIST_HAS, LANE_L, 0); return;
+ case 7: gen_num(g, depth - 1); put_op(g, unary[roll(g, LEN(unary))], 0, 0); return;
+ case 8: gen_num(g, depth - 1); gen_num(g, depth - 1); gen_num(g, depth - 1); put_op(g, CL, 0, 0); return;
+ case 9: gen_num(g, depth - 1); put_op(g, PURE_OP_PICK, 0, 0); put_op(g, binary[roll(g, LEN(binary))], 0, 0); return;
+ case 10: gen_num(g, depth - 1); gen_num(g, depth - 1); put_op(g, PURE_OP_SLIDE, 1, 0); return;
+ default: gen_num(g, depth - 1); gen_num(g, depth - 1); put_op(g, binary[roll(g, LEN(binary))], 0, 0); return;
+ }
+}
+
+/* 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);
+ size_t at = g->count;
+ put_op(g, PURE_OP_FOLD, 0, 0);
+ int fold_list = g->fold_list, fold_outer = g->outer;
+ g->fold_list = list, g->outer = outer;
+ if (how != PURE_FOLD_COUNT && how != PURE_FOLD_FIRST) gen_num(g, 3);
+ gen_num(g, 3);
+ g->fold_list = fold_list, g->outer = fold_outer;
+ g->code[at].arg = FOLDING(how, list, g->count - at - 1);
+ if (how == PURE_FOLD_FIRST) put_op(g, PURE_OP_INDEX_NUM, 0, 0);
+}
+
+static bool same_number(bool a_ok, double a, bool b_ok, double b) {
+ return a_ok == b_ok && (!a_ok || !memcmp(&a, &b, sizeof(a)));
+}
+
+static void lane_folds(void) {
+ static const S numbers[] = {{"k", 3}, {"h0", 0}, {"h1", 0}, {"h2", 0}};
+ static const T lists[] = {{"l", 3 | 1 << 8, 0}, {"m", 3, 1}};
+ static const RF l_fields[] = {{"key", 0, 0}, {"a", 0, 0}, {"b", 0, 0}}, m_fields[] = {{"x", 0, 0}, {"y", 0, 0}};
+ static const R records[] = {{"lrec", l_fields, 3}, {"mrec", m_fields, 2}};
+ static const I inputs[] = {KEY("go", "KeyG")};
+ static const double values[] = {0, -0.0, 1, -1, 2, 3, 0.5, -2.5, 5, 10, 1e308, -7};
+ enum { VIEWS = 6, COLUMNS = 3, HANDLED = 3 };
+ static Gen g;
+ uint32_t seed = 0x1a2b3c4du;
+ unsigned planned = 0, folds = 0, faults = 0, cells = 0;
+ for (unsigned round = 0; round < 300; ++round) {
+ g = (Gen){.seed = next_random(&seed), .fold_list = -1, .outer = -1};
+ V views[VIEWS];
+ char names[VIEWS + 1 + COLUMNS][4];
+ W tables[1 + COLUMNS];
+ for (unsigned v = 0; v < VIEWS; ++v) {
+ snprintf(names[v], sizeof(names[v]), "v%u", v);
+ views[v] = (V){names[v], (uint32_t)g.count, 0};
+ gen_fold(&g, roll(&g, 3) ? LANE_L : LANE_M, -1);
+ views[v].length = (uint32_t)(g.count - views[v].start);
+ }
+ tables[0] = (W){"t", 2 | (LANE_L + 1) << 8, 0, (uint32_t)g.count, 0};
+ g.fold_list = LANE_L;
+ gen_num(&g, 3);
+ g.fold_list = -1;
+ tables[0].length = (uint32_t)(g.count - tables[0].start);
+ for (unsigned c = 0; c < COLUMNS; ++c) {
+ snprintf(names[VIEWS + 1 + c], sizeof(names[0]), "c%u", c);
+ tables[1 + c] = (W){names[VIEWS + 1 + c], 0, VIEWS + 1, (uint32_t)g.count, 0};
+ gen_fold(&g, roll(&g, 3) ? LANE_L : LANE_M, LANE_L);
+ tables[1 + c].length = (uint32_t)(g.count - tables[1 + c].start);
+ }
+ H handler = {1, (uint32_t)g.count, 0};
+ for (unsigned h = 0; h < HANDLED; ++h) {
+ gen_fold(&g, roll(&g, 2) ? LANE_L : LANE_M, -1);
+ put_op(&g, ST, 1 + h, 0);
+ }
+ handler.length = (uint32_t)(g.count - handler.start);
+ Spec spec = {numbers, LEN(numbers), inputs, LEN(inputs), views, VIEWS, &handler, 1, g.code, g.count, NULL, 0,
+ lists, LEN(lists), NULL, 0, NULL, 0, records, LEN(records), tables, LEN(tables)};
+ if (load(spec, &module_a) != PURE_OK || load(spec, &module_b) != PURE_OK) {
+ fprintf(stderr, "lane round %u: %s\n", round, error);
+ abort();
+ }
+ for (uint32_t i = 0; i < module_b.code_count; ++i) {
+ folds += module_a.code[i].op == PURE_OP_FOLD;
+ planned += module_a.code[i].plan;
+ module_b.code[i].plan = 0;
+ }
+ planned += module_a.view_plan[VIEWS];
+ memset(module_b.view_plan, 0, sizeof(module_b.view_plan));
+ PureApp a, b;
+ CHECK(pure_app_start(&a, &module_a, (PureData){0}) == PURE_OK && pure_app_start(&b, &module_b, (PureData){0}) == PURE_OK);
+ size_t l_items = roll(&g, 4) ? roll(&g, 200) : 0, m_items = roll(&g, 4) ? roll(&g, 100) : 0;
+ for (size_t i = 0; i < l_items + m_items; ++i) {
+ bool in_l = i < l_items;
+ PureCell cells_[3] = {{in_l ? 2.0 * (double)i : values[roll(&g, LEN(values))], NULL, 0},
+ {values[roll(&g, LEN(values))], NULL, 0}, {values[roll(&g, LEN(values))], NULL, 0}};
+ PureList *list_a = a.lists[in_l ? LANE_L : LANE_M], *list_b = b.lists[in_l ? LANE_L : LANE_M];
+ CHECK(pure_list_insert(list_a, pure_list_count(list_a), cells_, NULL) == PURE_OK &&
+ pure_list_insert(list_b, pure_list_count(list_b), cells_, NULL) == PURE_OK);
+ }
+ for (unsigned v = 0; v < VIEWS; ++v) {
+ double x = 0, y = 0;
+ bool ok_a = pure_app_view(&a, v, &x), ok_b = pure_app_view(&b, v, &y);
+ faults += !ok_a;
+ if (!same_number(ok_a, x, ok_b, y)) {
+ fprintf(stderr, "lane round %u view %u: %d %g / %d %g\n", round, v, ok_a, x, ok_b, y);
+ abort();
+ }
+ }
+ size_t rows = pure_app_rows(&a, VIEWS);
+ CHECK(rows == pure_app_rows(&b, VIEWS));
+ for (size_t row = 0; row < rows; ++row) {
+ size_t item_a, item_b;
+ CHECK(pure_app_row_item(&a, VIEWS, row, &item_a) && pure_app_row_item(&b, VIEWS, row, &item_b) && item_a == item_b);
+ for (unsigned c = 0; c < COLUMNS; ++c) {
+ double x = 0, y = 0;
+ bool ok_a = pure_app_cell(&a, VIEWS + 1 + c, row, &x), ok_b = pure_app_cell(&b, VIEWS + 1 + c, row, &y);
+ ++cells;
+ if (!same_number(ok_a, x, ok_b, y)) {
+ fprintf(stderr, "lane round %u column %u row %zu: %d %g / %d %g\n", round, c, row, ok_a, x, ok_b, y);
+ abort();
+ }
+ }
+ }
+ PureResult went_a = pure_app_input(&a, 0, PURE_EDGE_DOWN), went_b = pure_app_input(&b, 0, PURE_EDGE_DOWN);
+ if (went_a != went_b || a.fault != b.fault || a.fault_pc != b.fault_pc || memcmp(a.values, b.values, 4 * sizeof(double))) {
+ fprintf(stderr, "lane round %u handler: %d %d %u / %d %d %u\n", round, went_a, a.fault, a.fault_pc, went_b, b.fault,
+ b.fault_pc);
+ abort();
+ }
+ faults += went_a != PURE_OK;
+ pure_app_stop(&a);
+ pure_app_stop(&b);
+ pure_module_release(&module_a);
+ pure_module_release(&module_b);
+ }
+ CHECK(planned > folds / 2 && faults > 100 && cells > 1000);
+ printf("{\"lane_folds\":%u,\"planned\":%u,\"faults_alike\":%u,\"cells\":%u}\n", folds, planned, faults, cells);
+}
+
/* Damaged fold and filter modules: whatever loads runs safely. */
static void fold_mutations(void) {
static unsigned char valid[65536], bytes[65536];
@@ -3079,6 +3277,7 @@ int main(void) {
list_trees();
folds();
filters();
+ lane_folds();
keyed();
keyed_mutations();
snapshots();
generated by cgit v1.2.3 (git 2.46.0) at 2026-10-20 13:33:42 +0000