From b6061fa10436bad78d7601a36712101dfe873643 Mon Sep 17 00:00:00 2001 From: eunhhu Date: Sat, 26 Sep 2026 16:38:12 +0100 Subject: Add keyed lists and text comparison A list state may name a key field of its record (the flags word of its entry: field + 1). A keyed list keeps its items in key order, numbers by value and texts by their bytes, each key once: LIST_APPEND places an item by halving and fails with the new fault exists (PURE_CONFLICT) when the key is there; LIST_FIND gives the index of a key's item and LIST_HAS whether it is there. The verifier refuses inserting by position and changing a key. Maps, sets and sorted maps are one list with an order rule, so tables, filters, folds, indices, storage and replacement stay as they are. A module that opens over a list not in its key order (one that was not keyed, keyed by another field, or stored so) puts it in order, moves its indices with their items and stores it again; two items with one key refuse the module rather than drop one. TEXT_COMPARE compares two texts by their bytes under one of the six relations. --- prototypes/connections/module-list.c | 61 ++++++++++ prototypes/connections/module-list.h | 9 ++ prototypes/connections/module.c | 106 +++++++++++++++-- prototypes/connections/module.h | 12 +- prototypes/connections/pure-run.c | 2 +- prototypes/connections/test-module.c | 214 ++++++++++++++++++++++++++++++++++- 6 files changed, 389 insertions(+), 15 deletions(-) (limited to 'prototypes') diff --git a/prototypes/connections/module-list.c b/prototypes/connections/module-list.c index 8ac44c1..148dc61 100644 --- a/prototypes/connections/module-list.c +++ b/prototypes/connections/module-list.c @@ -236,6 +236,67 @@ PureCell pure_list_get(const PureList *list, size_t at, unsigned field) { return list->items[at][field]; } +/* How two cells of a field order: numbers by value (-0 and +0 are one key), + * texts by their bytes. */ +static int order(const PureList *list, unsigned field, PureCell a, PureCell b) { + if (!list->text_fields[field]) return (a.num > b.num) - (a.num < b.num); + size_t shorter = a.size < b.size ? a.size : b.size; + int bytes = shorter ? memcmp(a.text, b.text, shorter) : 0; + return bytes ? (bytes > 0) - (bytes < 0) : (a.size > b.size) - (a.size < b.size); +} + +size_t pure_list_seek(const PureList *list, unsigned field, PureCell key, bool *found) { + size_t low = 0, high = list->count; + while (low < high) { + size_t middle = low + (high - low) / 2; + if (order(list, field, list->items[middle][field], key) < 0) low = middle + 1; + else high = middle; + } + *found = low < list->count && !order(list, field, list->items[low][field], key); + return low; +} + +/* Positions sorted by their items' field, stably (spare holds count). */ +PURE_COLD static void merge_sort(const PureList *list, unsigned field, size_t *at, size_t *spare, size_t count) { + if (count < 2) return; + size_t half = count / 2, i = 0, j = half, k = 0; + merge_sort(list, field, at, spare, half); + merge_sort(list, field, at + half, spare, count - half); + while (i < half && j < count) + spare[k++] = order(list, field, list->items[at[j]][field], list->items[at[i]][field]) < 0 ? at[j++] : at[i++]; + while (i < half) spare[k++] = at[i++]; + while (j < count) spare[k++] = at[j++]; + memcpy(at, spare, count * sizeof(*at)); +} + +PURE_COLD PureResult pure_list_sorted(const PureList *list, unsigned field, PureList **out, size_t *moved) { + *out = NULL; + bool ordered = true; + for (size_t i = 1; i < list->count && ordered; ++i) + ordered = order(list, field, list->items[i - 1][field], list->items[i][field]) < 0; + if (ordered) return PURE_OK; + size_t *at = malloc(2 * list->count * sizeof(*at)); + if (!at) return PURE_ALLOCATION; + for (size_t i = 0; i < list->count; ++i) at[i] = i; + merge_sort(list, field, at, at + list->count, list->count); + PureResult result = PURE_OK; + for (size_t i = 1; i < list->count && result == PURE_OK; ++i) + if (!order(list, field, list->items[at[i - 1]][field], list->items[at[i]][field])) result = PURE_CONFLICT; + PureList *sorted = result == PURE_OK ? pure_list_new(list->fields, list->text_fields) : NULL; + if (result == PURE_OK && !sorted) result = PURE_ALLOCATION; + for (size_t i = 0; result == PURE_OK && i < list->count; ++i) { + result = pure_list_insert(sorted, i, list->items[at[i]], NULL); + moved[at[i]] = i; + } + free(at); + if (result != PURE_OK) { + pure_list_free(sorted); + return result; + } + *out = sorted; + return PURE_OK; +} + void pure_undo_rollback(PureUndo *undo, size_t mark) { Entry *entries = undo->entries; for (size_t i = undo->count; i-- > mark;) { diff --git a/prototypes/connections/module-list.h b/prototypes/connections/module-list.h index 6e41c57..9052679 100644 --- a/prototypes/connections/module-list.h +++ b/prototypes/connections/module-list.h @@ -34,6 +34,15 @@ 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); +/* 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. */ +size_t pure_list_seek(const PureList *, unsigned field, PureCell key, bool *found); +/* The list's items ordered by field, as a keyed list keeps them: *out is NULL + * when they already are, or a new list in that order with moved[position + * before] = position after for every item. CONFLICT when two items have the + * same key (nothing is made). */ +PureResult pure_list_sorted(const PureList *, unsigned field, PureList **out, size_t *moved); /* A list may keep a stored copy in a draft: header bytes, then each item's * fields in order (a number as its binary64 bits, little-endian; a text as a * u32le length and its bytes). Every change splices the draft as well, and a diff --git a/prototypes/connections/module.c b/prototypes/connections/module.c index d616b9f..3490ba9 100644 --- a/prototypes/connections/module.c +++ b/prototypes/connections/module.c @@ -9,18 +9,19 @@ enum { STATE_BYTES = 16, COLLECTION_BYTES = 12, INPUT_BYTES = 16, FIELD_BYTES = 8, CONSTANT_BYTES = 8, RECORD_BYTES = 8, RECORD_FIELD_BYTES = 16, VIEW_BYTES = 16, HANDLER_BYTES = 12, OP_BYTES = 16 }; -/* T_FIELD and T_ITEM stand for the type of the message or record field named. */ -enum { T_NUM = 1, T_BYTES = 2, T_TEXT = 3, T_CURSOR = 4, T_FIELD = 5, T_INDEX = 6, T_ITEM = 7 }; +/* T_FIELD and T_ITEM stand for the type of the message or record field + * named, T_KEY for the type of the named keyed list's key. */ +enum { T_NUM = 1, T_BYTES = 2, T_TEXT = 3, T_CURSOR = 4, T_FIELD = 5, T_INDEX = 6, T_ITEM = 7, T_KEY = 8 }; enum { FROM_PAYLOAD, FROM_DOCUMENT, FROM_COPY, FROM_CONSTANT, FROM_TEXT, FROM_ARENA }; /* Where an opcode may appear. */ enum { IN_VIEW = 1, IN_HANDLER = 2, IN_MESSAGE = 4, IN_KEYED = 8, IN_TEXT = 16, IN_ROW = 32 }; enum { READ = IN_VIEW | IN_HANDLER }; /* What an argument names: nothing (it is 0), a state of one type (A_STATE + * the type), a list and one of its record's fields, a message field, the - * collection, a constant, a unit, the column's row, a branch target or a - * stack depth. */ + * collection, a constant, a unit, the column's row, a branch target, a stack + * depth, a fold, a relation or a keyed list. */ 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_FOLD }; + A_ROW, A_TARGET, A_DEPTH, A_FOLD, A_RELATION, A_KEYED }; /* A fold's block is verified as a column that leaves one number (count) or * two (a value and whether to include it), a table's filter as a column that * leaves one: these stand for a view type. */ @@ -93,6 +94,9 @@ static const struct { unsigned char pops, in[3], out, where, arg, of; } signatur [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}, + [PURE_OP_TEXT_COMPARE] = {2, {T_TEXT, T_TEXT}, T_NUM, READ, A_RELATION, O_ANY}, + [PURE_OP_LIST_FIND] = {1, {T_KEY}, T_INDEX, READ, A_KEYED, O_ARG}, + [PURE_OP_LIST_HAS] = {1, {T_KEY}, T_NUM, READ, A_KEYED, O_ANY}, }; #undef NUMS #undef STATE @@ -174,6 +178,8 @@ 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_FOLD: return (arg & 0xFF) <= PURE_FOLD_FIRST && state_of(m, arg >> 8 & 0xFF, PURE_STATE_LIST) && arg >> 16; + case A_RELATION: return arg <= PURE_NOT_EQUAL; + case A_KEYED: return state_of(m, arg, PURE_STATE_LIST) && m->state_key[arg]; case A_NONE: case A_TARGET: case A_DEPTH: return true; default: return state_of(m, arg, (uint8_t)(kind - A_STATE)); } @@ -249,6 +255,10 @@ PURE_COLD static const char *verify_block(const PureModule *m, PureBlock block, if ((kind == A_NONE && arg) || (op->op == PURE_OP_CONST ? !isfinite(op->value) : op->value != 0)) REFUSE("non-canonical operand"); if (!names_arg(m, kind, arg, shape, row)) REFUSE("operand names no such state, field, constant or unit"); + /* A keyed list places its items by key, and an item's key stays. */ + if (op->op == PURE_OP_LIST_INSERT && m->state_key[arg]) REFUSE("insert by position into a keyed list"); + if (op->op == PURE_OP_ITEM_SET && m->state_key[list_of(arg)] == item_field(arg) + 1) + REFUSE("change of a keyed list's key"); /* PICK copies the value arg below the top; SLIDE drops arg values under the top. */ if (kind == A_DEPTH) { bool pick = op->op == PURE_OP_PICK; @@ -286,6 +296,8 @@ PURE_COLD static const char *verify_block(const PureModule *m, PureBlock block, pops += record->count; } else if (op->op == PURE_OP_ITEM_SET) { need[pops++] = field_type(m, list_of(arg), item_field(arg)); + } else if (need[0] == T_KEY) { + need[0] = field_type(m, arg, m->state_key[arg] - 1u); } if (height < (int)pops) REFUSE("stack underflow"); height -= (int)pops; @@ -393,11 +405,14 @@ PURE_COLD PureResult pure_module_load(const void *bytes, size_t size, PureModule out->initial[i] = read_double(at + 8); if (!isfinite(out->initial[i])) REFUSE("non-finite initial value", i); } else { + /* Flags: a mark (cursor), or a keyed list's key field + 1. */ uint32_t flags = read32(at + 12); - if ((flags && (out->state_type[i] != PURE_STATE_CURSOR || flags != PURE_CURSOR_STAYS)) || + bool cursor = out->state_type[i] == PURE_STATE_CURSOR, list = out->state_type[i] == PURE_STATE_LIST; + if ((flags && !(cursor && flags == PURE_CURSOR_STAYS) && !(list && flags <= PURE_RECORD_FIELDS)) || read32(at + 8) > UINT16_MAX) REFUSE("state reference", i); out->state_ref[i] = (uint16_t)read32(at + 8); - out->state_flags[i] = (uint8_t)flags; + out->state_flags[i] = cursor ? (uint8_t)flags : 0; + out->state_key[i] = list ? (uint8_t)flags : 0; } } for (uint32_t i = 0; i < out->collections; ++i, at += COLLECTION_BYTES) { @@ -484,7 +499,8 @@ PURE_COLD PureResult pure_module_load(const void *bytes, size_t size, PureModule for (uint32_t i = 0; i < out->states; ++i) if ((out->state_type[i] == PURE_STATE_TEXT && out->state_ref[i] >= out->constants) || (out->state_type[i] == PURE_STATE_CURSOR && !state_of(out, out->state_ref[i], PURE_STATE_TEXT)) || - (out->state_type[i] == PURE_STATE_LIST && out->state_ref[i] >= out->records) || + (out->state_type[i] == PURE_STATE_LIST && + (out->state_ref[i] >= out->records || out->state_key[i] > out->record[out->state_ref[i]].count)) || (out->state_type[i] == PURE_STATE_INDEX && !state_of(out, out->state_ref[i], PURE_STATE_LIST))) REFUSE("state reference", i); /* A table names its list in place of code; its columns follow it. */ @@ -599,7 +615,8 @@ typedef struct { static PureResult fault(PureApp *app, PureFault kind, uint32_t pc) { app->fault = kind; app->fault_pc = pc; - return kind == PURE_FAULT_LIMIT ? PURE_LIMIT : kind == PURE_FAULT_NOT_FOUND ? PURE_NOT_FOUND : PURE_INVALID; + return kind == PURE_FAULT_LIMIT ? PURE_LIMIT : kind == PURE_FAULT_NOT_FOUND ? PURE_NOT_FOUND : + kind == PURE_FAULT_EXISTS ? PURE_CONFLICT : PURE_INVALID; } static bool reserve(PureArena *arena, size_t more) { @@ -904,6 +921,12 @@ static PureResult run(const PureModule *m, double *values, PureBlock block, Even return status; cells[f] = (PureCell){stack[base + f].num, (unsigned char *)span.data, span.size}; } + if (m->state_key[arg]) { /* a keyed list places the item by its key */ + bool found; + unsigned key = m->state_key[arg] - 1u; + at = pure_list_seek(list, key, cells[key], &found); + if (found) { arena->used = mark; kind = PURE_FAULT_EXISTS; goto failed; } + } status = pure_list_insert(list, at, cells, &app->undo); arena->used = mark; if (status != PURE_OK) goto refused; @@ -978,6 +1001,42 @@ static PureResult run(const PureModule *m, double *values, PureBlock block, Even stack[sp++].bytes.owner = (uint16_t)(arg >> 8 & 0xFF); /* first: the list the index is in */ continue; } + case PURE_OP_TEXT_COMPARE: { + /* Texts order by their bytes: a shorter text before a longer one it begins. */ + PureBytes right = stack[--sp].bytes, left = stack[sp - 1].bytes; + size_t mark = arena->used; + PureSpan a, b; + if (!reserve(arena, (size_t)(left.length + right.length))) return PURE_ALLOCATION; + if ((status = contiguous(app, arena, left, &a)) != PURE_OK || + (status = contiguous(app, arena, right, &b)) != PURE_OK) return status; + size_t shorter = a.size < b.size ? a.size : b.size; + int order = shorter ? memcmp(a.data, b.data, shorter) : 0; + if (!order) order = (a.size > b.size) - (a.size < b.size); + arena->used = mark; + stack[sp - 1].num = arg == PURE_LESS ? order < 0 : arg == PURE_LESS_EQUAL ? order <= 0 : + arg == PURE_GREATER ? order > 0 : arg == PURE_GREATER_EQUAL ? order >= 0 : + arg == PURE_EQUAL ? order == 0 : order != 0; + continue; + } + case PURE_OP_LIST_FIND: case PURE_OP_LIST_HAS: { + /* A keyed list's item by key, found by halving: FIND gives its index, HAS whether it is there. */ + unsigned key = m->state_key[arg] - 1u; + size_t mark = arena->used; + PureCell cell = {top->num, NULL, 0}; + if (text_field(m, arg, key)) { + PureSpan span; + if ((status = contiguous(app, arena, top->bytes, &span)) != PURE_OK) return status; + cell = (PureCell){0, (unsigned char *)span.data, span.size}; + } + bool found; + size_t at = pure_list_seek(app->lists[arg], key, cell, &found); + arena->used = mark; + if (op->op == PURE_OP_LIST_HAS) { top->num = found; continue; } + if (!found) { kind = PURE_FAULT_NOT_FOUND; goto failed; } + top->num = (double)at; + top->bytes.owner = (uint16_t)arg; + 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; @@ -1489,6 +1548,25 @@ PURE_COLD static PureResult open_module(PureApp *app, const PureModule *module) } else if (!(lists[i] = new_list(module, module->state_ref[i]))) result = PURE_ALLOCATION; } else values[i] = kept[i] >= 0 ? app->values[kept[i]] : module->initial[i]; } + /* A keyed list keeps its items in key order: one that was not keyed, or + * keyed by another field, is put in order and its indices follow their + * items. Two items with one key refuse the module: nothing is dropped. */ + size_t *moved[PURE_MODULE_STATES] = {0}; + for (uint32_t i = 0; i < module->states && result == PURE_OK; ++i) { + if (module->state_type[i] != PURE_STATE_LIST || !module->state_key[i]) continue; + size_t count = pure_list_count(lists[i]); + PureList *sorted = NULL; + if (count && !(moved[i] = malloc(count * sizeof(**moved)))) result = PURE_ALLOCATION; + else result = pure_list_sorted(lists[i], module->state_key[i] - 1u, &sorted, moved[i]); + if (!sorted) { + free(moved[i]); + moved[i] = NULL; + continue; + } + if (kept[i] < 0 || lists[i] != app->lists[kept[i]]) pure_list_free(lists[i]); + lists[i] = sorted; + rewrite[i] = list_drafts[i] != NULL; + } /* A cursor or index keeps its position only while its text or list is the * one it belonged to. */ for (uint32_t i = 0; i < module->states; ++i) { @@ -1498,8 +1576,14 @@ PURE_COLD static PureResult open_module(PureApp *app, const PureModule *module) values[i] = same ? app->values[kept[i]] : 0; } if (result == PURE_OK && stored) result = pure_save_open_values(app, module, values, kept, texts, lists); - /* Store the lists whose record changed last, so that a failure can put - * every draft back as it was. */ + for (uint32_t i = 0; i < module->states; ++i) { + uint32_t list = module->state_ref[i]; + if (module->state_type[i] == PURE_STATE_INDEX && moved[list] && values[i] < (double)pure_list_count(lists[list])) + values[i] = (double)moved[list][(size_t)values[i]]; + } + for (uint32_t i = 0; i < module->states; ++i) free(moved[i]); + /* Store the lists whose record or order changed last, so that a failure + * can put every draft back as it was. */ for (uint32_t i = 0; i < module->states; ++i) if (rewrite[i]) { before[i] = pure_draft_version(list_drafts[i]); diff --git a/prototypes/connections/module.h b/prototypes/connections/module.h index 4264710..09a8540 100644 --- a/prototypes/connections/module.h +++ b/prototypes/connections/module.h @@ -37,7 +37,7 @@ 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_FOLD, + PURE_OP_PICK, PURE_OP_SLIDE, PURE_OP_FOLD, PURE_OP_TEXT_COMPARE, PURE_OP_LIST_FIND, PURE_OP_LIST_HAS, PURE_OP_COUNT } PureOpcode; /* FOLD's argument: the kind (bits 0-7), the list state (8-15) and the length @@ -46,6 +46,9 @@ typedef enum { * 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; +/* 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; 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; @@ -61,9 +64,11 @@ enum { PURE_CURSOR_STAYS = 1 }; typedef enum { PURE_VIEW_NUM = 0, PURE_VIEW_TEXT = 1, PURE_VIEW_TABLE = 2 } PureViewType; typedef enum { PURE_UNIT_CHAR = 0, PURE_UNIT_LINE = 1 } PureUnit; typedef enum { PURE_EDGE_DOWN, PURE_EDGE_UP } PureEdge; +/* EXISTS: an item with that key is already in the keyed list (the event + * reports PURE_CONFLICT). */ typedef enum { PURE_FAULT_NONE, PURE_FAULT_DIVIDE, PURE_FAULT_NON_FINITE, PURE_FAULT_CLAMP, - PURE_FAULT_LIMIT, PURE_FAULT_NOT_FOUND, PURE_FAULT_ENCODING + 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; @@ -91,6 +96,9 @@ typedef struct { uint8_t state_type[PURE_MODULE_STATES]; uint16_t state_ref[PURE_MODULE_STATES]; /* text: constant; cursor: text; list: record; index: list */ uint8_t state_flags[PURE_MODULE_STATES]; /* cursor: PURE_CURSOR_STAYS */ + /* A keyed list: its key field + 1 (0: none). Its items stay in key order + * (numbers by value, texts by bytes), each key once, and keys do not change. */ + uint8_t state_key[PURE_MODULE_STATES]; PureInputShape input[PURE_MODULE_INPUTS]; PureField field[PURE_MODULE_FIELDS]; double initial[PURE_MODULE_STATES]; diff --git a/prototypes/connections/pure-run.c b/prototypes/connections/pure-run.c index 6e4a6e1..d97d277 100644 --- a/prototypes/connections/pure-run.c +++ b/prototypes/connections/pure-run.c @@ -14,7 +14,7 @@ * Text states and text views print as JSON strings; cursors as byte positions; * lists as arrays of objects; indices as positions; a table view as an array * with an object of its columns per row. A failed view or cell is null. */ -static const char *const fault_names[] = {"none", "divide", "non_finite", "clamp", "limit", "not_found", "encoding"}; +static const char *const fault_names[] = {"none", "divide", "non_finite", "clamp", "limit", "not_found", "encoding", "exists"}; static bool load(const char *path, PureModule *module) { FILE *file = fopen(path, "rb"); diff --git a/prototypes/connections/test-module.c b/prototypes/connections/test-module.c index 07a0cbb..11d0660 100644 --- a/prototypes/connections/test-module.c +++ b/prototypes/connections/test-module.c @@ -1981,6 +1981,216 @@ static void pointing(void) { remove_store(path); } +/* Keyed lists: items in key order (texts by bytes, numbers by value), each + * key once; found by key; a list that becomes keyed is put in order with + * its indices following their items, or refused when two items share a key. */ +enum { FIND = PURE_OP_LIST_FIND, HAS = PURE_OP_LIST_HAS, TCMP = PURE_OP_TEXT_COMPARE, + PEOPLE = 1, K_AT = 2, SCORES = 3, K_NAME = 0, K_VISITS = 1u << 16 }; +static const S keyed_nums[] = {{"n", 0}}; +static const T keyed_states[] = {{"people", 3 | 1 << 8, 0}, {"at", 4, 1}, {"scores", 3 | 1 << 8, 1}}; +static const T unkeyed_states[] = {{"people", 3, 0}, {"at", 4, 1}, {"scores", 3, 1}}; +static const RF person_fields[] = {{"name", 1, 0}, {"visits", 0, 0}}; +static const RF score_fields[] = {{"score", 0, 0}}; +static const R keyed_records[] = {{"person", person_fields, 2}, {"score", score_fields, 1}}; +static const char *const keyed_constants[] = {"", "bob", "m"}; +static const I keyed_inputs[] = { + {"typed", NULL, PURE_KIND_TEXT, false, NULL, 0}, {"seek", NULL, PURE_KIND_TEXT, false, NULL, 0}, + {"has", NULL, PURE_KIND_TEXT, false, NULL, 0}, KEY("drop", "Delete"), KEY("bump", "KeyB"), + KEY("two", "KeyN"), KEY("zero", "KeyO"), KEY("minus_zero", "KeyM"), {"twice", NULL, PURE_KIND_TEXT, false, NULL, 0}, +}; +static const O keyed_code[] = { + {TI, 0, 0}, {C, 0, 0}, {LA, PEOPLE, 0}, {TI, 0, 0}, {FIND, PEOPLE, 0}, {XS, K_AT, 0}, /* 0 typed: add, point at it */ + {TI, 0, 0}, {FIND, PEOPLE, 0}, {XS, K_AT, 0}, /* 6 seek */ + {TI, 0, 0}, {HAS, PEOPLE, 0}, {ST, 0, 0}, /* 9 has */ + {XL, K_AT, 0}, {LR, PEOPLE, 0}, /* 12 drop */ + {XL, K_AT, 0}, {XL, K_AT, 0}, {IG, PEOPLE | K_VISITS, 0}, {C, 0, 1}, {ADD, 0, 0}, /* 14 bump */ + {IS, PEOPLE | K_VISITS, 0}, + {C, 0, 2}, {LA, SCORES, 0}, {C, 0, 0}, {LA, SCORES, 0}, {C, 0, -0.0}, {LA, SCORES, 0}, /* 20 two, zero, minus_zero */ + {TI, 0, 0}, {C, 0, 0}, {LA, PEOPLE, 0}, {TI, 0, 0}, {C, 0, 0}, {LA, PEOPLE, 0}, /* 26 twice: always exists */ + {LC, PEOPLE, 0}, /* 32 view count */ + {XL, K_AT, 0}, {XN, 0, 0}, /* 33 view position */ + {XL, K_AT, 0}, {IG, PEOPLE | K_NAME, 0}, {TK, 1, 0}, {TCMP, PURE_EQUAL, 0}, /* 35 view is_bob */ + {XL, K_AT, 0}, {IG, PEOPLE | K_NAME, 0}, {TK, 2, 0}, {TCMP, PURE_LESS, 0}, /* 39 view before_m */ + {LC, SCORES, 0}, /* 43 view scores */ + {XL, K_AT, 0}, {IG, PEOPLE | K_NAME, 0}, /* 44 view current */ +}; +static const H keyed_handlers[] = {{1, 0, 6}, {3, 6, 3}, {5, 9, 3}, {7, 12, 2}, {9, 14, 6}, {11, 20, 2}, {13, 22, 2}, + {15, 24, 2}, {17, 26, 6}}; +static const V keyed_views[] = {{"count", 32, 1}, {"position", 33, 2}, {"is_bob", 35, 4}, {"before_m", 39, 4}, + {"scores_count", 43, 1}}; +static const V keyed_text_views[] = {{"current", 44, 2}}; +/* Unkeyed, the same states: typed appends and points at the new last item. */ +static const O unkeyed_code[] = {{TI, 0, 0}, {C, 0, 0}, {LA, PEOPLE, 0}, {XE, PEOPLE, 0}, {XS, K_AT, 0}}; +static const H unkeyed_handlers[] = {{1, 0, 5}}; + +static Spec keyed_spec(const T *states, const O *code, size_t count, const H *handlers, size_t nhandlers) { + bool views = code == keyed_code; + return (Spec){keyed_nums, 1, keyed_inputs, LEN(keyed_inputs), keyed_views, views ? LEN(keyed_views) : 0, handlers, + nhandlers, code, count, NULL, 0, states, LEN(keyed_states), keyed_constants, LEN(keyed_constants), + keyed_text_views, views ? 1 : 0, keyed_records, 2, NULL, 0}; +} + +static PureResult type_text(PureApp *app, uint32_t input, const char *text) { + return pure_app_text(app, input, (PureSpan){(const unsigned char *)text, strlen(text)}); +} + +/* A list's first field (text) of every item, comma separated. */ +static const char *names_of(const PureApp *app, uint32_t list) { + static char out[512]; + size_t used = 0; + for (size_t at = 0; at < pure_list_count(app->lists[list]); ++at) { + PureCell cell = pure_list_get(app->lists[list], at, 0); + CHECK(used + cell.size + 2 < sizeof(out)); + if (at) out[used++] = ','; + if (cell.size) memcpy(out + used, cell.text, cell.size); + used += cell.size; + } + out[used] = 0; + return out; +} + +static void keyed(void) { + CHECK(load(keyed_spec(keyed_states, keyed_code, LEN(keyed_code), keyed_handlers, LEN(keyed_handlers)), &module_a) == PURE_OK); + PureApp app; + CHECK(pure_app_start(&app, &module_a, (PureData){0}) == PURE_OK); + for (const char *const *word = (const char *const[]){"m", "b", "z", "a", NULL}; *word; ++word) + CHECK(type_text(&app, 0, *word) == PURE_OK); + CHECK(!strcmp(names_of(&app, PEOPLE), "a,b,m,z") && app.values[K_AT] == 0 && !strcmp(view_text(&app, 5), "a")); + /* A key once: the add fails, and so does an event whose second add repeats its first. */ + CHECK(type_text(&app, 0, "b") == PURE_CONFLICT && app.fault == PURE_FAULT_EXISTS); + CHECK(type_text(&app, 8, "c") == PURE_CONFLICT && !strcmp(names_of(&app, PEOPLE), "a,b,m,z") && app.values[K_AT] == 0); + CHECK(type_text(&app, 1, "z") == PURE_OK && app.values[K_AT] == 3 && !strcmp(view_text(&app, 5), "z")); + CHECK(type_text(&app, 1, "q") == PURE_NOT_FOUND && app.fault == PURE_FAULT_NOT_FOUND && app.values[K_AT] == 3); + CHECK(type_text(&app, 2, "m") == PURE_OK && app.values[0] == 1); + CHECK(type_text(&app, 2, "c") == PURE_OK && app.values[0] == 0); + CHECK(pure_app_input(&app, 4, PURE_EDGE_DOWN) == PURE_OK && pure_list_get(app.lists[PEOPLE], 3, 1).num == 1); + CHECK(pure_app_input(&app, 3, PURE_EDGE_DOWN) == PURE_OK && !strcmp(names_of(&app, PEOPLE), "a,b,m")); + CHECK(app.values[K_AT] == 2 && number_view(&app, 2) == 0 && number_view(&app, 3) == 0); /* "m": not bob, not before m */ + CHECK(type_text(&app, 1, "b") == PURE_OK && number_view(&app, 2) == 0 && number_view(&app, 3) == 1); + CHECK(type_text(&app, 0, "bob") == PURE_OK && number_view(&app, 2) == 1 && number_view(&app, 3) == 1); + /* Bytes order texts: a text before the longer ones it begins, UTF-8 after ASCII, the empty text first. */ + CHECK(type_text(&app, 0, "\xea\xb0\x80") == PURE_OK && type_text(&app, 0, "ab") == PURE_OK); + CHECK(type_text(&app, 0, "") == PURE_OK && type_text(&app, 0, "") == PURE_CONFLICT); + CHECK(!strcmp(names_of(&app, PEOPLE), ",a,ab,b,bob,m,\xea\xb0\x80") && app.values[K_AT] == 0); + /* Numbers order by value, and -0 is the key 0. */ + CHECK(pure_app_input(&app, 5, PURE_EDGE_DOWN) == PURE_OK && pure_app_input(&app, 6, PURE_EDGE_DOWN) == PURE_OK); + CHECK(pure_app_input(&app, 7, PURE_EDGE_DOWN) == PURE_CONFLICT && number_view(&app, 4) == 2); + CHECK(pure_list_get(app.lists[SCORES], 0, 0).num == 0 && !signbit(pure_list_get(app.lists[SCORES], 0, 0).num) && + pure_list_get(app.lists[SCORES], 1, 0).num == 2); + + /* Replacing: unkeyed, the list stays as it is and takes appends at its end. */ + CHECK(load(keyed_spec(unkeyed_states, unkeyed_code, LEN(unkeyed_code), unkeyed_handlers, 1), &module_b) == PURE_OK); + CHECK(pure_app_replace(&app, &module_b) == PURE_OK && type_text(&app, 0, "c") == PURE_OK); + CHECK(!strcmp(names_of(&app, PEOPLE), ",a,ab,b,bob,m,\xea\xb0\x80,c") && app.values[K_AT] == 7); + CHECK(pure_app_point(&app, K_AT, 6) == PURE_OK); /* at the Korean name */ + /* Keyed again: put in order, the index following its item. */ + CHECK(pure_app_replace(&app, &module_a) == PURE_OK && !strcmp(names_of(&app, PEOPLE), ",a,ab,b,bob,c,m,\xea\xb0\x80")); + CHECK(app.values[K_AT] == 7 && !strcmp(view_text(&app, 5), "\xea\xb0\x80")); + /* Two items with one key cannot become keyed: the app keeps its module and items. */ + CHECK(pure_app_replace(&app, &module_b) == PURE_OK && type_text(&app, 0, "a") == PURE_OK); + CHECK(pure_app_replace(&app, &module_a) == PURE_CONFLICT && app.module == &module_b && pure_list_count(app.lists[PEOPLE]) == 9); + pure_app_stop(&app); + + /* Stored: a list that becomes keyed is stored in order, once. */ + char *path = new_store(); + CHECK(pure_app_start(&app, &module_b, pure_tree_data(path)) == PURE_OK); + for (const char *const *word = (const char *const[]){"m", "b", "z", NULL}; *word; ++word) + CHECK(type_text(&app, 0, *word) == PURE_OK); + CHECK(pure_app_point(&app, K_AT, 1) == PURE_OK); + pure_app_stop(&app); + for (int round = 0; round < 2; ++round) { + CHECK(pure_app_start(&app, &module_a, pure_tree_data(path)) == PURE_OK); + CHECK(!strcmp(names_of(&app, PEOPLE), "b,m,z") && app.values[K_AT] == 0); + pure_app_stop(&app); + } + CHECK(pure_app_start(&app, &module_b, pure_tree_data(path)) == PURE_OK && type_text(&app, 0, "m") == PURE_OK); + pure_app_stop(&app); + CHECK(pure_app_start(&app, &module_a, pure_tree_data(path)) == PURE_CONFLICT); + CHECK(pure_app_start(&app, &module_b, pure_tree_data(path)) == PURE_OK && !strcmp(names_of(&app, PEOPLE), "b,m,z,m")); + pure_app_stop(&app); + remove_store(path); + static const char *const words[] = {"a", "b", "ab", "", "\xea\xb0\x80", "zz"}; + for (uint32_t seed = 1; seed <= 3; ++seed) + stored_equivalence(keyed_spec(keyed_states, keyed_code, LEN(keyed_code), keyed_handlers, LEN(keyed_handlers)), + words, LEN(words), seed * 0x9e3779b9u); + + /* What a keyed list and a text comparison may not be. */ + static const O insert[] = {{XF, PEOPLE, 0}, {TK, 0, 0}, {C, 0, 0}, {LI, PEOPLE, 0}}; + static const O set_key[] = {{XL, K_AT, 0}, {TK, 0, 0}, {IS, PEOPLE | K_NAME, 0}}; + static const O find_number[] = {{C, 0, 1}, {FIND, PEOPLE, 0}, {XS, K_AT, 0}}; + static const O find[] = {{TI, 0, 0}, {FIND, PEOPLE, 0}, {XS, K_AT, 0}}; + static const O relation[] = {{TI, 0, 0}, {TI, 0, 0}, {TCMP, PURE_NOT_EQUAL + 1, 0}, {ST, 0, 0}}; + static const O compare_numbers[] = {{C, 0, 1}, {C, 0, 1}, {TCMP, PURE_EQUAL, 0}, {ST, 0, 0}}; + static const T far_key[] = {{"people", 3 | 3 << 8, 0}, {"at", 4, 1}, {"scores", 3, 1}}; + static const T keyed_index[] = {{"people", 3, 0}, {"at", 4 | 1 << 8, 1}, {"scores", 3, 1}}; + static const struct { const T *states; const O *code; size_t count; const char *reason; } refused[] = { + {keyed_states, insert, LEN(insert), "insert by position into a keyed list"}, + {keyed_states, set_key, LEN(set_key), "change of a keyed list's key"}, + {keyed_states, find_number, LEN(find_number), "operand type"}, + {unkeyed_states, find, LEN(find), "no such state"}, + {keyed_states, relation, LEN(relation), "no such state"}, + {keyed_states, compare_numbers, LEN(compare_numbers), "operand type"}, + {far_key, unkeyed_code, LEN(unkeyed_code), "state reference"}, + {keyed_index, unkeyed_code, LEN(unkeyed_code), "state reference"}, + }; + for (size_t i = 0; i < LEN(refused); ++i) { + H handler = {1, 0, (uint32_t)refused[i].count}; + if (load(keyed_spec(refused[i].states, refused[i].code, refused[i].count, &handler, 1), &module_b) != PURE_INVALID || + !strstr(error, refused[i].reason)) { + fprintf(stderr, "keyed case %zu: expected '%s', got '%s'\n", i, refused[i].reason, error); + abort(); + } + } +} + +/* Damaged keyed modules: whatever loads keeps every keyed list in strict key + * order and every index on an item. */ +static void keyed_mutations(void) { + static unsigned char valid[65536], bytes[65536]; + size_t size = build(valid, keyed_spec(keyed_states, keyed_code, LEN(keyed_code), keyed_handlers, LEN(keyed_handlers))); + static const char *const words[] = {"a", "b", "ab", "", "\xea\xb0\x80"}; + uint32_t state = 0x6c8e9cf5u; + 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 < 24; ++e) { + uint32_t input = next_random(&state) % module_b.inputs; + if (module_b.input[input].kind == PURE_KIND_TEXT) type_text(&app, input, words[next_random(&state) % LEN(words)]); + 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); + } + for (uint32_t s = 0; s < module_b.states; ++s) { + if (module_b.state_type[s] == PURE_STATE_INDEX) { + size_t count = pure_list_count(app.lists[module_b.state_ref[s]]); + CHECK(app.values[s] == floor(app.values[s]) && app.values[s] >= 0 && + app.values[s] <= (count ? (double)(count - 1) : 0)); + } + if (module_b.state_type[s] != PURE_STATE_LIST || !module_b.state_key[s]) continue; + unsigned key = module_b.state_key[s] - 1u; + bool text = module_b.record_field_text[module_b.record[module_b.state_ref[s]].first + key]; + for (size_t at = 1; at < pure_list_count(app.lists[s]); ++at) { + PureCell a = pure_list_get(app.lists[s], at - 1, key), b = pure_list_get(app.lists[s], at, key); + if (!text) { CHECK(a.num < b.num); continue; } + size_t shorter = a.size < b.size ? a.size : b.size; + int order = shorter ? memcmp(a.text, b.text, shorter) : 0; + CHECK(order < 0 || (!order && a.size < b.size)); + } + } + } + pure_app_stop(&app); + } + printf("{\"keyed_module_mutations\":20000,\"accepted_after_damage\":%u}\n", accepted); +} + int main(void) { behaviour(); faults(); @@ -1994,6 +2204,8 @@ int main(void) { lists(); folds(); filters(); + keyed(); + keyed_mutations(); fold_mutations(); pointing(); list_mutations(); @@ -2002,6 +2214,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-folds-filters\"}"); + 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-filters-keyed-lists-text-order\"}"); return 0; } -- cgit v1.2.3