diff options
Diffstat (limited to 'prototypes/connections')
| -rw-r--r-- | prototypes/connections/module-list.c | 61 | ||||
| -rw-r--r-- | prototypes/connections/module-list.h | 9 | ||||
| -rw-r--r-- | prototypes/connections/module.c | 106 | ||||
| -rw-r--r-- | prototypes/connections/module.h | 12 | ||||
| -rw-r--r-- | prototypes/connections/pure-run.c | 2 | ||||
| -rw-r--r-- | prototypes/connections/test-module.c | 214 |
6 files changed, 389 insertions, 15 deletions
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; } |