Text keys (023): a list knows the text field it is keyed by; an event's list keyed by a text is HASHED from its first item, its table's slots holding the texts' hashes (FNV-1a), a match the key cell's bytes too; HAS and a field by key read the table; its order made by a merge sort (the first eight bytes as a number, then all). A FIND whose index only an ITEM_SET of its list takes, the code between in a line finding by key alone, sets the item where it was found (PLAN_ROW: a HASHED list's slot, no position made). words 453 to 217 ms (5.8x C)

text_keys_equivalence: adds, has, fields by key, sets where found, positions, runs, removes and clears against a tree keyed by the text

5 files changed, 256 insertions, 29 deletions

diff --git a/core/module-list.c b/core/module-list.c
index 9f576a8..5f6cf0c 100644
--- a/core/module-list.c
+++ b/core/module-list.c
@@ -116,6 +116,7 @@ struct PureList {
     bool full;
     uint32_t *ranks;
     size_t ranks_room;
+    int text_key;      /* the text field it is keyed by (its layout's key -1), or -1: HASHED by its texts' hashes (023) */
 };
 
 /* The log of an event's changes: a removed item's cells wait in the log's
@@ -1182,6 +1183,20 @@ static bool make_flat(PureList *list) {
     return true;
 }
 
+static int order(const Layout *l, unsigned field, PureCell a, PureCell b);
+
+/* The field a HASHED list is keyed by: its text key, else its number key. */
+static int hashed_field(const PureList *list) { return list->text_key >= 0 ? list->text_key : list->layout.key; }
+
+/* A key's bits in a HASHED list's table: a number's (key_bits), or its
+ * text's hash (FNV-1a over its bytes; never VACANT). */
+static uint64_t cell_bits(const PureList *list, PureCell key) {
+    if (list->text_key < 0) return key_bits(key.num);
+    uint64_t h = UINT64_C(0xcbf29ce484222325);
+    for (size_t i = 0; i < key.size; ++i) h = (h ^ key.text[i]) * UINT64_C(0x100000001b3);
+    return h == VACANT ? h ^ 2 : h;
+}
+
 /* Cell from of a column of cells w bytes wide copied to cell to of another. */
 static inline void cell_copy(void *to_column, size_t to, const void *from_column, size_t from, size_t w) {
     char *t = (char *)to_column + to * w;
@@ -1194,13 +1209,17 @@ static inline void cell_copy(void *to_column, size_t to, const void *from_column
     }
 }
 
-/* A HASHED list's slot of key (its cells there), or SIZE_MAX. */
-static size_t hashed_slot(const PureList *list, double key) {
-    uint64_t bits = key_bits(key);
+/* A HASHED list's slot of key (its cells there; a text's where its bytes are the key's too), or SIZE_MAX. */
+static size_t hashed_slot(const PureList *list, PureCell key) {
+    uint64_t bits = cell_bits(list, key);
     size_t mask = list->member_capacity - 1;
     for (size_t at = member_slot(bits, mask);; at = (at + 1) & mask) {
-        if (list->members[at] == bits) return at;
-        if (list->members[at] == VACANT) return SIZE_MAX;
+        if (list->members[at] == bits) {
+            if (list->text_key < 0) return at;
+            PureCell there = array_cell(list, at, (unsigned)list->text_key);
+            if (there.size == key.size && (!key.size || !memcmp(there.text, key.text, key.size))) return at;
+        } else if (list->members[at] == VACANT)
+            return SIZE_MAX;
     }
 }
 
@@ -1221,11 +1240,10 @@ static bool hashed_table(PureList *list, size_t capacity) {
     }
     for (size_t i = 0; i < capacity; ++i) table[i] = VACANT;
     bool hashed = list->form == HASHED;
-    const double *keys = list->columns[l->key];
     size_t mask = capacity - 1, rows = hashed ? list->member_capacity : list->count;
     for (size_t row = 0; row < rows; ++row) {
         if (hashed && list->members[row] == VACANT) continue;
-        uint64_t bits = hashed ? list->members[row] : key_bits(keys[row]);
+        uint64_t bits = hashed ? list->members[row] : cell_bits(list, array_cell(list, row, (unsigned)hashed_field(list)));
         size_t at = member_slot(bits, mask);
         while (table[at] != VACANT) at = (at + 1) & mask;
         table[at] = bits;
@@ -1246,7 +1264,7 @@ static bool hashed_table(PureList *list, size_t capacity) {
  * not be (made FLAT twice since it was cleared, or packed) or without
  * memory: it stays FLAT. */
 static bool make_hashed(PureList *list) {
-    if (list->layout.key < 0 || list->pack || list->flattened >= 2) return false;
+    if (hashed_field(list) < 0 || list->pack || list->flattened >= 2) return false;
     size_t capacity = 16;
     while (capacity < 2 * (list->count + 1)) capacity *= 2;
     if (!hashed_table(list, capacity)) return false;
@@ -1261,12 +1279,11 @@ static bool hashed_large(const PureList *list) {
     return 2 * (list->count + 1) > list->member_capacity && 2 * list->member_capacity * row_width(&list->layout) > ARRAYS_LARGE;
 }
 
-/* An item (its cells the list's own, its key not there) into a HASHED
- * list at its key's slot; false without memory (as it was). */
-static bool hashed_add(PureList *list, const PureCell *item) {
+/* An item (its cells the list's own, its key not there, its bits those)
+ * into a HASHED list at its key's slot; false without memory (as it was). */
+static bool hashed_add(PureList *list, const PureCell *item, uint64_t bits) {
     const Layout *l = &list->layout;
     if (2 * (list->count + 1) > list->member_capacity && !hashed_table(list, 2 * list->member_capacity)) return false;
-    uint64_t bits = key_bits(item[l->key].num);
     size_t mask = list->member_capacity - 1, at = member_slot(bits, mask);
     while (list->members[at] != VACANT) at = (at + 1) & mask;
     list->members[at] = bits;
@@ -1298,9 +1315,30 @@ static bool make_ordered(PureList *list) {
     }
     for (size_t slot = 0, i = 0; slot < list->member_capacity; ++slot) {
         uint64_t bits = list->members[slot];
-        if (bits != VACANT) a[i++] = (Ordered){bits >> 63 ? ~bits : bits | UINT64_C(1) << 63, (uint32_t)slot};
+        if (bits == VACANT) continue;
+        if (list->text_key >= 0) { /* a text's first eight bytes, as a number in their order (past its end, 0) */
+            PureCell text = array_cell(list, slot, (unsigned)list->text_key);
+            bits = 0;
+            for (size_t c = 0; c < 8; ++c) bits = bits << 8 | (c < text.size ? text.text[c] : 0);
+            a[i++] = (Ordered){bits, (uint32_t)slot};
+        } else
+            a[i++] = (Ordered){bits >> 63 ? ~bits : bits | UINT64_C(1) << 63, (uint32_t)slot};
+    }
+    for (size_t width = 1; list->text_key >= 0 && width < n; width *= 2) { /* texts: merged in order (their first bytes, then all), a run's width doubling */
+        for (size_t low = 0; low < n; low += 2 * width) {
+            size_t middle = low + width < n ? low + width : n, high = low + 2 * width < n ? low + 2 * width : n, i = low, j = middle, k = low;
+            while (i < middle && j < high)
+                b[k++] = (a[j].key != a[i].key ? a[j].key < a[i].key
+                                               : order(l, (unsigned)list->text_key, array_cell(list, a[j].slot, (unsigned)list->text_key),
+                                                       array_cell(list, a[i].slot, (unsigned)list->text_key)) < 0)
+                             ? a[j++] : a[i++];
+            while (i < middle) b[k++] = a[i++];
+            while (j < high) b[k++] = a[j++];
+        }
+        Ordered *t = a;
+        a = b, b = t;
     }
-    for (unsigned shift = 0; n && shift < 64; shift += 8) {
+    for (unsigned shift = 0; list->text_key < 0 && n && shift < 64; shift += 8) {
         size_t counts[256] = {0};
         for (size_t i = 0; i < n; ++i) ++counts[a[i].key >> shift & 255];
         if (counts[a[0].key >> shift & 255] == n) continue;
@@ -1320,6 +1358,7 @@ static bool make_ordered(PureList *list) {
     arrays_free(list);
     memcpy(list->columns, columns, sizeof(columns));
     list->room = room;
+    if (list->text_key >= 0) members_drop(list); /* a text's hashes are no key set of a FLAT list (searched by its texts) */
     list->form = FLAT;
     list->moved = 0;
     ++list->flattened;
@@ -1554,6 +1593,7 @@ PureList *pure_list_new(unsigned fields, const uint8_t *kinds) {
     }
     l->leaf_size = at;
     l->key = -1;
+    list->text_key = -1;
     list->id = __atomic_add_fetch(&lists_made, 1, __ATOMIC_RELAXED);
     return list;
 }
@@ -1570,7 +1610,12 @@ static bool rekey(PureList *list, Node **place) {
 
 PureResult pure_list_keyed(PureList *list, int field) {
     Layout *l = &list->layout;
-    int key = field >= 0 && (unsigned)field < l->fields && l->kinds[field] == PURE_CELL_NUMBER ? field : -1;
+    int key = field >= 0 && (unsigned)field < l->fields && l->kinds[field] == PURE_CELL_NUMBER ? field : -1,
+        text = field >= 0 && (unsigned)field < l->fields && pure_cell_text(l->kinds[field]) ? field : -1;
+    if (text != list->text_key) {
+        if (list->form == HASHED && !make_ordered(list)) return PURE_ALLOCATION;
+        list->text_key = text;
+    }
     if (key == l->key) return PURE_OK;
     if (list->count && !make_tree(list)) return PURE_ALLOCATION;
     if (list->arrays) arrays_free(list); /* its columns as wide as the new key wants */
@@ -1689,7 +1734,7 @@ bool pure_list_hashed(PureList *list) {
 }
 
 bool pure_list_contains(const PureList *list, double key, bool *found) {
-    if (!list->members) return false;
+    if (!list->members || list->text_key >= 0) return false; /* a text's hashes: pure_list_contains_text */
     if (list->bitmap) {
         *found = small_key(key) && (size_t)key / 64 < list->member_capacity &&
                  list->members[(size_t)key / 64] >> ((size_t)key % 64) & 1;
@@ -1702,6 +1747,37 @@ bool pure_list_contains(const PureList *list, double key, bool *found) {
     return true;
 }
 
+static bool own_cell(const PureList *list, unsigned field, PureCell from, PureCell *to);
+
+bool pure_list_contains_text(const PureList *list, PureCell key, bool *found) {
+    if (list->form != HASHED || list->text_key < 0) return false;
+    *found = hashed_slot(list, key) != SIZE_MAX;
+    return true;
+}
+
+size_t pure_list_find_row(const PureList *list, unsigned field, PureCell key, bool *found) {
+    if (list->form == HASHED && (int)field == hashed_field(list)) {
+        size_t slot = hashed_slot(list, key);
+        *found = slot != SIZE_MAX;
+        return slot;
+    }
+    return pure_list_seek(list, field, key, found);
+}
+
+PureResult pure_list_set_row(PureList *list, size_t row, unsigned field, PureCell value, PureUndo *undo) {
+    const Layout *l = &list->layout;
+    if (list->form != HASHED || undo || (int)field == hashed_field(list)) return pure_list_set(list, row, field, value, undo);
+    PureCell copy, old = array_cell(list, row, field); /* at its key's slot, as found (no position made) */
+    uint8_t need = narrows(l->kinds[field]) && (list->width[field] == 1 || list->width[field] == 4) ? width_of(value.num) : 0;
+    if (need > list->width[field] && !widen(list, field, need)) return PURE_ALLOCATION;
+    if (!own_cell(list, field, value, &copy)) return PURE_ALLOCATION;
+    list->bytes += cell_bytes(l, field, copy) - cell_bytes(l, field, old);
+    array_put(list, row, field, copy);
+    let_go_text(list, old.text);
+    ++list->version;
+    return PURE_OK;
+}
+
 /* An event's arrays are its items, as a tree's nodes are: neither counts
  * here (the stored bytes stand for both), so a list's room runs out at the
  * same item whatever it keeps them in (021). */
@@ -1747,8 +1823,8 @@ bool pure_list_lookup(const PureList *list, unsigned key_field, PureCell key, un
         *cell = array_cell(list, (size_t)key.num, field);
         return true;
     }
-    if (list->form == HASHED && (int)key_field == list->layout.key) { /* at its key's slot, by its table */
-        size_t slot = hashed_slot(list, key.num);
+    if (list->form == HASHED && (int)key_field == hashed_field(list)) { /* at its key's slot, by its table */
+        size_t slot = hashed_slot(list, key);
         if (slot == SIZE_MAX) return false;
         *cell = array_cell(list, slot, field);
         return true;
@@ -2176,20 +2252,37 @@ PureResult pure_list_insert(PureList *list, size_t at, const PureCell *cells, Pu
 PureResult pure_list_add(PureList *list, const PureCell *cells, PureUndo *undo, size_t *at, bool *exists) {
     const Layout *l = &list->layout;
     *exists = false;
-    if (l->key < 0) return PURE_INVALID; /* searched and inserted apart, then */
+    if (l->key < 0) { /* by a text key: an event's list HASHED by its texts' hashes; else searched and inserted apart */
+        if (list->text_key < 0 || at || undo || list->journaled || list->pack || !list->arrays) return PURE_INVALID;
+        if (list->form == FLAT && !make_hashed(list)) return PURE_INVALID;
+        if (list->form != HASHED) return PURE_INVALID;
+        if (hashed_slot(list, cells[list->text_key]) != SIZE_MAX) return *exists = true, PURE_OK;
+        if (hashed_large(list)) return make_ordered(list) ? PURE_INVALID : PURE_ALLOCATION;
+        if (list->count == PURE_LIST_ITEMS) return PURE_LIMIT;
+        PureCell item[16];
+        unsigned owned = 0;
+        for (; owned < l->fields; ++owned)
+            if (!own_cell(list, owned, cells[owned], &item[owned])) break;
+        if (owned < l->fields || !arrays_fit(list, cells) || !hashed_add(list, item, cell_bits(list, cells[list->text_key]))) {
+            for (unsigned f = 0; f < owned; ++f) free_text(item[f].text);
+            return PURE_ALLOCATION;
+        }
+        list->bytes += cells_bytes(l, item);
+        return PURE_OK;
+    }
     if (!logged(list, undo)) return PURE_ALLOCATION;
     if (list->form != TREE) {
         double key = cells[l->key].num;
         bool found = false;
         if (list->form == HASHED) { /* by its table, at its end: no position, unless asked */
-            if (hashed_slot(list, key) != SIZE_MAX && !at) return *exists = true, PURE_OK;
+            if (hashed_slot(list, cells[l->key]) != SIZE_MAX && !at) return *exists = true, PURE_OK;
             if (!at && !hashed_large(list)) {
                 if (list->count == PURE_LIST_ITEMS) return PURE_LIMIT;
                 PureCell item[16];
                 unsigned owned = 0;
                 for (; owned < l->fields; ++owned)
                     if (!own_cell(list, owned, cells[owned], &item[owned])) break;
-                if (owned < l->fields || !arrays_fit(list, cells) || !hashed_add(list, item)) {
+                if (owned < l->fields || !arrays_fit(list, cells) || !hashed_add(list, item, cell_bits(list, cells[l->key]))) {
                     for (unsigned f = 0; f < owned; ++f) free_text(item[f].text);
                     return PURE_ALLOCATION;
                 }
diff --git a/core/module-list.h b/core/module-list.h
index 3ae468f..369e8ed 100644
--- a/core/module-list.h
+++ b/core/module-list.h
@@ -159,6 +159,12 @@ bool pure_list_suits(PureList *, unsigned needs, unsigned narrow);
 bool pure_list_full(PureList *);
 /* Whether key is there, by the set: false when the list keeps none (search it then). */
 bool pure_list_contains(const PureList *, double key, bool *found);
+/* Whether a HASHED list keyed by a text has key (false: it is not one; search it). */
+bool pure_list_contains_text(const PureList *list, PureCell key, bool *found);
+/* Where key is, for a set of the item found (pure_list_set_row): a HASHED
+ * list's slot (no position made), else its position (pure_list_seek). */
+size_t pure_list_find_row(const PureList *list, unsigned field, PureCell key, bool *found);
+PureResult pure_list_set_row(PureList *list, size_t row, unsigned field, PureCell value, PureUndo *undo);
 /* The bytes it keeps beside its items for that. */
 size_t pure_list_extra(const PureList *);
 /* An event's list (empty, never shared, journaled or undone) may keep its
diff --git a/core/module-run.h b/core/module-run.h
index 74f188b..fac77a4 100644
--- a/core/module-run.h
+++ b/core/module-run.h
@@ -6,7 +6,7 @@
 #include "module.h"
 
 /* An item's or a key's op->plan: its cell a text; a FIND joined to the ITEM_GET after it. */
-enum { PLAN_TEXT = 1, PLAN_JOINED = 2 };
+enum { PLAN_TEXT = 1, PLAN_JOINED = 2, PLAN_ROW = 4 };
 
 /* An item instruction's argument: its list and its field. */
 static inline uint32_t list_of(uint32_t arg) { return arg & 0xFFFF; }
diff --git a/core/module.c b/core/module.c
index bc9fb8f..2228725 100644
--- a/core/module.c
+++ b/core/module.c
@@ -1371,6 +1371,48 @@ PURE_COLD PureResult pure_module_load(const void *bytes, size_t size, PureModule
         if (op->op == PURE_OP_LIST_FIND && next->op == PURE_OP_ITEM_GET && list_of(next->arg) == op->arg && !landed[pc + 1])
             op->plan |= PLAN_JOINED;
     }
+    /* A FIND whose index waits on the stack for an ITEM_SET of its list,
+     * the code between in a line (no jump in or out) that touches no list but
+     * to find by key (joined, or HAS): the item is set where it was found, a
+     * HASHED list's slot, no position made (PLAN_ROW, docs/design/023). */
+    for (uint32_t pc = 0; pc < out->code_count; ++pc) {
+        PureOp *find = &out->code[pc];
+        if (find->op != PURE_OP_LIST_FIND || find->plan & PLAN_JOINED) continue;
+        int height = 1;
+        for (uint32_t at = pc + 1; at < out->code_count && height >= 1 && !landed[at]; ++at) {
+            const PureOp *o = &out->code[at];
+            int pops = -1, pushes = 1;
+            switch (o->op) {
+            case PURE_OP_CONST: case PURE_OP_LOAD: case PURE_OP_LOCAL_LOAD: case PURE_OP_TEXT_CONST: case PURE_OP_TEXT_LOAD:
+            case PURE_OP_FIELD: case PURE_OP_LIST_COUNT:
+                pops = 0;
+                break;
+            case PURE_OP_NEG: case PURE_OP_NOT: case PURE_OP_FLOOR: case PURE_OP_NUM_TEXT: case PURE_OP_I64_NEG:
+            case PURE_OP_I64_FROM: case PURE_OP_NUM_FROM: case PURE_OP_LIST_HAS:
+                pops = 1;
+                break;
+            case PURE_OP_ADD: case PURE_OP_SUB: case PURE_OP_MUL: case PURE_OP_DIV: case PURE_OP_MIN: case PURE_OP_MAX:
+            case PURE_OP_MOD: case PURE_OP_AND: case PURE_OP_OR: 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_CONCAT: case PURE_OP_TEXT_COMPARE:
+            case PURE_OP_I64_ADD: case PURE_OP_I64_SUB: case PURE_OP_I64_MUL: case PURE_OP_I64_DIV: case PURE_OP_I64_MOD:
+            case PURE_OP_I64_MIN: case PURE_OP_I64_MAX: case PURE_OP_I64_COMPARE:
+                pops = 2;
+                break;
+            case PURE_OP_LIST_FIND: /* joined: its ITEM_GET with it (a key in, the field out) */
+                if (o->plan & PLAN_JOINED && !landed[at + 1]) pops = 1, ++at;
+                break;
+            case PURE_OP_ITEM_SET:
+                if (height == 2 && list_of(o->arg) == find->arg) {
+                    find->plan |= PLAN_ROW;
+                    out->code[at].plan |= PLAN_ROW;
+                }
+                break;
+            default: break;
+            }
+            if (pops < 0) break;
+            height += pushes - pops;
+        }
+    }
     free(landed);
     /* The lists an index state refers to: their inserts tell where (move_indices). */
     for (uint32_t i = 0; i < out->states; ++i)
@@ -2822,10 +2864,10 @@ static inline __attribute__((always_inline)) int step(Frame *frame, const PureOp
         Held before = list_held(app, app->lists[list]);
         PureSpan span = {0};
         status = op->plan & PLAN_TEXT ? contiguous(app, arena, value.bytes, &span) : PURE_OK;
-        if (status == PURE_OK)
-            status = pure_list_set(app->lists[list], at, field,
-                                   (PureCell){.i64 = value.i64, .text = (unsigned char *)span.data, .size = span.size},
-                                   undo_for(app, list));
+        PureCell cell = {.i64 = value.i64, .text = (unsigned char *)span.data, .size = span.size};
+        if (status == PURE_OK) /* where its FIND found it (PLAN_ROW: a HASHED list's slot), else its position */
+            status = op->plan & PLAN_ROW ? pure_list_set_row(app->lists[list], at, field, cell, undo_for(app, list))
+                                         : pure_list_set(app->lists[list], at, field, cell, undo_for(app, list));
         arena->used = mark;
         if (status != PURE_OK) REFUSED;
         if (!grows(app, before, list_held(app, app->lists[list]))) { kind = PURE_FAULT_MEMORY; FAILED; }
@@ -2912,12 +2954,14 @@ static inline __attribute__((always_inline)) int step(Frame *frame, const PureOp
             else if ((status = keep_bytes(arena, value.text, value.size, &top->bytes)) != PURE_OK) STOPPED(status);
             NEXT;
         }
-        /* An event's list keeps its keys as a set: HAS asks it alone (020). */
-        if (op->op == PURE_OP_LIST_HAS && pure_list_contains(app->lists[arg], cell.num, &found)) {
+        /* An event's list keeps its keys as a set: HAS asks it alone (020); a text key's HASHED list, its table. */
+        if (op->op == PURE_OP_LIST_HAS && (op->plan & PLAN_TEXT ? pure_list_contains_text(app->lists[arg], cell, &found)
+                                                                 : pure_list_contains(app->lists[arg], cell.num, &found))) {
+            arena->used = mark;
             top->num = found;
             NEXT;
         }
-        size_t at = pure_list_seek(app->lists[arg], key, cell, &found);
+        size_t at = op->plan & PLAN_ROW ? pure_list_find_row(app->lists[arg], key, cell, &found) : pure_list_seek(app->lists[arg], key, cell, &found);
         arena->used = mark;
         if (op->op == PURE_OP_LIST_HAS) { top->num = found; NEXT; }
         if (!found) { kind = PURE_FAULT_NOT_FOUND; FAILED; }
diff --git a/core/test-module.c b/core/test-module.c
index 3fc0985..371fca5 100644
--- a/core/test-module.c
+++ b/core/test-module.c
@@ -1404,6 +1404,89 @@ static double some_number(unsigned event, uint32_t r) {
     }
 }
 
+/* An item into a list keyed by its text field 0, as the executor does: added at once (HASHED), else found and inserted. */
+static PureResult text_add(PureList *list, const PureCell *cells, bool *exists) {
+    PureResult result = pure_list_add(list, cells, NULL, NULL, exists);
+    if (result != PURE_INVALID) return result;
+    size_t at = pure_list_seek(list, 0, cells[0], exists);
+    return *exists ? PURE_OK : pure_list_insert(list, at, cells, NULL);
+}
+
+/* An event's list keyed by a text (HASHED by its texts' hashes, docs/design
+ * 023) against a tree keyed so: adds, has, a field by key, a set where its
+ * key was found, positions, runs, removes, and the event's end. */
+static void text_keys_equivalence(void) {
+    static const uint8_t fields[3] = {PURE_CELL_TEXT, PURE_CELL_NUMBER, PURE_CELL_TEXT};
+    uint32_t seed = 0x74657874u;
+    size_t hashed = 0, steps = 0;
+    PureList *a = pure_list_new(3, fields), *t = pure_list_new(3, fields);
+    CHECK(a && t && pure_list_keyed(a, 0) == PURE_OK && pure_list_keyed(t, 0) == PURE_OK && pure_list_arrays(a));
+    for (unsigned event = 0; event < 120; ++event) {
+        unsigned changes = 20 + next_random(&seed) % (event % 5 == 0 ? 3000 : 300), words = 1 + next_random(&seed) % 2000;
+        for (unsigned c = 0; c < changes; ++c, ++steps) {
+            uint32_t r = next_random(&seed);
+            char key[24], other[16];
+            size_t size = (size_t)snprintf(key, sizeof(key), r % 7 ? "w%u" : "%u-word", (r >> 3) % words);
+            size_t other_size = (size_t)snprintf(other, sizeof(other), "o%u", r % 97);
+            PureCell cells[3] = {{.text = (unsigned char *)key, .size = size}, {.num = (double)(r % 1000)},
+                                 {.text = (unsigned char *)other, .size = r % 5 ? other_size : 0}};
+            size_t n = pure_list_count(t);
+            unsigned op = next_random(&seed) % (event % 4 == 1 ? 10 : 16); /* some events by key alone: HASHED stays */
+            if (op < 5) {
+                bool ea, et;
+                CHECK(text_add(a, cells, &ea) == PURE_OK && text_add(t, cells, &et) == PURE_OK && ea == et);
+            } else if (op < 8) { /* has, and fields by key */
+                bool ha, ht, fa, ft;
+                PureCell ca, ct;
+                if (!pure_list_contains_text(a, cells[0], &ha)) (void)pure_list_seek(a, 0, cells[0], &ha);
+                (void)pure_list_seek(t, 0, cells[0], &ht);
+                CHECK(ha == ht);
+                fa = pure_list_lookup(a, 0, cells[0], 1, &ca);
+                ft = pure_list_lookup(t, 0, cells[0], 1, &ct);
+                CHECK(fa == ft && fa == ht && (!fa || ca.i64 == ct.i64));
+                fa = pure_list_lookup(a, 0, cells[0], 2, &ca);
+                ft = pure_list_lookup(t, 0, cells[0], 2, &ct);
+                CHECK(fa == ft && (!fa || (ca.size == ct.size && (!ca.size || !memcmp(ca.text, ct.text, ca.size)))));
+            } else if (op < 10) { /* set where its key was found (a slot, in a HASHED list) */
+                bool fa, ft;
+                size_t ra = pure_list_find_row(a, 0, cells[0], &fa), rt = pure_list_seek(t, 0, cells[0], &ft);
+                CHECK(fa == ft);
+                if (fa) {
+                    unsigned field = r % 2 ? 1 : 2;
+                    CHECK(pure_list_set_row(a, ra, field, cells[field], NULL) == PURE_OK &&
+                          pure_list_set(t, rt, field, cells[field], NULL) == PURE_OK);
+                }
+            } else if (op < 12 && n) { /* by position: in order now */
+                size_t at = next_random(&seed) % n;
+                PureCell x = pure_list_get(a, at, 0), y = pure_list_get(t, at, 0), w = pure_list_get(a, at, 1), z = pure_list_get(t, at, 1);
+                CHECK(x.size == y.size && !memcmp(x.text, y.text, x.size) && w.i64 == z.i64);
+            } else if (op < 14 && n) { /* a run from somewhere */
+                size_t at = next_random(&seed) % n;
+                PureRun ra, rt;
+                CHECK(pure_list_run(a, at, &ra) && pure_list_run(t, at, &rt));
+                PureSpan sa = ra.column[0].texts[at - ra.start], st = rt.column[0].texts[at - rt.start];
+                CHECK(sa.size == st.size && (!sa.size || !memcmp(sa.data, st.data, sa.size)));
+            } else if (op < 16 && n) { /* remove */
+                size_t at = next_random(&seed) % n;
+                CHECK(pure_list_remove(a, at, NULL) == PURE_OK && pure_list_remove(t, at, NULL) == PURE_OK);
+            }
+            hashed += pure_list_form(a) == 3;
+        }
+        CHECK(pure_list_count(a) == pure_list_count(t) && pure_list_size(a) == pure_list_size(t));
+        for (size_t i = 0; i < pure_list_count(t); i += 1 + i / 64)
+            for (unsigned f = 0; f < 3; ++f) {
+                PureCell x = pure_list_get(a, i, f), y = pure_list_get(t, i, f);
+                CHECK(f == 1 ? x.i64 == y.i64 : x.size == y.size && (!x.size || !memcmp(x.text, y.text, x.size)));
+            }
+        pure_list_clear(a);
+        pure_list_clear(t);
+    }
+    pure_list_free(a);
+    pure_list_free(t);
+    CHECK(hashed > 10000);
+    printf("{\"text_keys\":{\"steps\":%zu,\"hashed\":%zu}}\n", steps, hashed);
+}
+
 static void arrays_equivalence(void) {
     static const uint8_t fields[3] = {PURE_CELL_NUMBER, PURE_CELL_TEXT, PURE_CELL_NUMBER};
     uint32_t seed = 0x61727261u;
@@ -6280,6 +6363,7 @@ int main(void) {
     list_trees();
     key_sets();
     keyed_journal();
+    text_keys_equivalence();
     arrays_equivalence();
     packed_lists();
     folds();