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.

7 files changed, 424 insertions, 21 deletions

diff --git a/docs/design/008-module-format.md b/docs/design/008-module-format.md
index ab42542..38eeb07 100644
--- a/docs/design/008-module-format.md
+++ b/docs/design/008-module-format.md
@@ -13,6 +13,8 @@ v3은 **text 상태와 커서**, text 상수, text 입력, text 보기를 더했
 v4는 **레코드**, 레코드의 **리스트** 상태, 리스트의 **인덱스** 상태를 더했다.
 v5는 값을 가진 채 합류하는 분기(조건식)와, 리스트 항목마다 행을 내는 **표 보기**, 한 번 계산한 값을 여러 번
 쓰게 하는 스택 복사(PICK·SLIDE, 툴체인의 함수 인라인용)를 더한다. 이전 판은 받지 않는다(생산자는 aup 하나다).
+v5에는 뒤에 집계(FOLD), 걸러진 표, 마크, 그리고 **키 있는 리스트**와 text 비교가 더해졌다. 모두 전의 v5 모듈이 그대로
+유효하도록 더한 것이다(새 명령과 이전에 0이던 자리의 값).
 
 ## 바이트 배치
 
@@ -25,7 +27,7 @@ v5는 값을 가진 채 합류하는 분기(조건식)와, 리스트 항목마�
 | 16 | u32 명령 수, u32 문자열 바이트 수 |
 | 24 | u16 필드, u16 컬렉션, u16 상수, u16 레코드 |
 | 32 | u32 상수 블롭 바이트 수, u16 레코드 필드, u16 0 |
-| 40 | 상태 × 16 B: u32 이름, u32 타입(0 수, 1 text, 2 커서, 3 리스트, 4 인덱스), 8 B 값: 수는 f64 초기값, text는 u32 초기 상수, 커서는 u32 대상 text 상태와 u32 플래그(1이면 마크: 그 자리에 넣은 글 앞에 남는다), 리스트는 u32 레코드, 인덱스는 u32 대상 리스트 상태 |
+| 40 | 상태 × 16 B: u32 이름, u32 타입(0 수, 1 text, 2 커서, 3 리스트, 4 인덱스), 8 B 값: 수는 f64 초기값, text는 u32 초기 상수, 커서는 u32 대상 text 상태와 u32 플래그(1이면 마크: 그 자리에 넣은 글 앞에 남는다), 리스트는 u32 레코드와 u32 키(0이면 없음, 아니면 키 필드 + 1), 인덱스는 u32 대상 리스트 상태 |
 | | 컬렉션 × 12 B: u32 이름, u32 1(바이트), u32 1(키별) |
 | | 입력 × 16 B: u32 이름, u8 종류(1 키, 2 메시지, 3 text), u8 키별 여부, u16 0, u32 키 이름(키 입력) 또는 0, u16 첫 필드, u16 필드 수 |
 | | 필드 × 8 B: u32 이름, u32 타입(1 u32le, 2 바이트 꼬리) |
@@ -83,11 +85,11 @@ v5는 값을 가진 채 합류하는 분기(조건식)와, 리스트 항목마�
 | 48 | BYTES_FROM | t → b | 같은 바이트 |
 | 49 | CUR_COUNT | c → n | 단위 `인자`로 커서 앞의 글자 수, 또는 1부터 센 줄 번호 |
 | 50 | LIST_COUNT | → n | 리스트 상태 `인자`의 항목 수 |
-| 51 | LIST_APPEND | f… → | 레코드 필드 값을 필드 순서대로 받아 끝에 붙인다. 핸들러 전용 |
-| 52 | LIST_INSERT | i f… → | 인덱스의 항목 앞에 넣는다(빈 리스트면 처음) |
+| 51 | LIST_APPEND | f… → | 레코드 필드 값을 필드 순서대로 받아 끝에 붙인다. 키 있는 리스트에서는 키 순서의 자리에 넣고, 그 키가 이미 있으면 `exists`. 핸들러 전용 |
+| 52 | LIST_INSERT | i f… → | 인덱스의 항목 앞에 넣는다(빈 리스트면 처음). 키 있는 리스트에는 쓸 수 없다 |
 | 53 | LIST_REMOVE | i → | 인덱스의 항목을 지운다. 없으면 `not_found` |
 | 54 | ITEM_GET | i → f | 항목의 필드. `인자`의 아래 16비트는 리스트 상태, 위는 필드 번호. 없으면 `not_found` |
-| 55 | ITEM_SET | i f → | 항목의 필드를 바꾼다. 핸들러 전용 |
+| 55 | ITEM_SET | i f → | 항목의 필드를 바꾼다. 키 있는 리스트의 키 필드는 바꿀 수 없다. 핸들러 전용 |
 | 56 | INDEX_LOAD | → i | 인덱스 상태 `인자` |
 | 57 | INDEX_STORE | i → | 인덱스 상태 `인자`. 핸들러 전용. 같은 이벤트에서 지우기 전에 얻은, 끝을 넘은 인덱스는 `not_found` |
 | 58 | INDEX_MOVE | i n → i | n만큼. 정수가 아니면 `limit`. 처음과 마지막 항목에서 멈춘다 |
@@ -97,8 +99,11 @@ v5는 값을 가진 채 합류하는 분기(조건식)와, 리스트 항목마�
 | 63 | PICK | … → … v | `인자`개 아래의 값을 복사해 올린다(0이면 맨 위). 타입과 대상도 그대로 |
 | 64 | SLIDE | … v → v | 맨 위 값 아래의 `인자`개(1 이상)를 버린다 |
 | 65 | FOLD | → n 또는 i | 집계. `인자`의 비트 0–7은 종류(0 count, 1 sum, 2 max, 3 min, 4 first), 8–15는 리스트 상태, 16–31은 뒤따르는 블록의 길이 L. 그 L개 명령이 항목마다 그 리스트의 열처럼 돈다(`ROW`가 항목). count는 블록이 남긴 수가 0이 아닌 항목을 세고, sum·max·min은 블록이 남긴 값과 포함 여부(0이 아니면 포함)로 계산한다. first는 블록이 0이 아닌 수를 남긴 첫 항목의 인덱스(그 리스트의 인덱스)이고 거기서 멈춘다. 포함된 항목이 없으면 count·sum은 0, max·min·first는 `not_found` |
+| 66 | TEXT_COMPARE | t t → n | 바이트 순서로 비교해 0 또는 1. `인자`는 관계(0 LT, 1 LE, 2 GT, 3 GE, 4 EQ, 5 NE, 수 비교 명령의 순서). 앞이 같으면 짧은 쪽이 앞이다 |
+| 67 | LIST_FIND | k → i | 키 있는 리스트 `인자`에서 키가 k인 항목의 인덱스. 반씩 나눠 찾는다. 없으면 `not_found` |
+| 68 | LIST_HAS | k → n | 그 키의 항목이 있으면 1, 없으면 0 |
 
-`f`는 레코드 필드의 타입(수 또는 text)이다. 수 연산 결과가 유한하지 않으면 실패한다. 실패하면 그 이벤트의 모든
+`f`는 레코드 필드의 타입(수 또는 text)이고, `k`는 그 리스트의 키 필드 타입이다. 수 연산 결과가 유한하지 않으면 실패한다. 실패하면 그 이벤트의 모든
 핸들러가 한 일이 취소된다.
 
 ## 로드할 때 검증하는 것
@@ -122,6 +127,9 @@ v5는 값을 가진 채 합류하는 분기(조건식)와, 리스트 항목마�
 - 집계(FOLD)의 블록은 그 리스트의 열로 따로 검증한다. 읽기만 하고(효과는 거절), count·first는 수 하나, sum·max·min은
   수 둘을 남긴다. first의 결과는 그 리스트의 인덱스 타입이다. 블록 안에 다시 집계를 둘 수 없다(비용 상한). 둘레의 블록은 FOLD와 그 블록을 명령 하나로 보고, 앞의 분기가
   블록 안으로 들어오지 못한다. 블록은 둘레 블록 안에 끝나야 한다.
+- 키 있는 리스트의 키는 레코드 안의 필드다(플래그 1–16이 필드 수 이하). 플래그는 커서(마크)와 리스트에만 있다.
+  키 있는 리스트에는 자리로 넣지(LIST_INSERT) 못하고, 키 필드를 바꾸지(ITEM_SET) 못한다. LIST_FIND·LIST_HAS는 키 있는
+  리스트만 가리키고 키 필드 타입의 값을 받는다. FIND의 결과는 그 리스트의 인덱스다.
 - 걸러진 표의 필터 블록은 그 리스트의 열로 검증한다. 읽기만 하고 수 하나를 남기며, 안에 집계를 둘 수 없다.
   타입 다음 바이트는 표에만 쓸 수 있다.
 - 표는 리스트 상태를 가리키고 열은 앞에 나온 표를 가리킨다. 표 밖의 이름은 한 이름공간이고, 열 이름은 표
@@ -143,6 +151,23 @@ v5는 값을 가진 채 합류하는 분기(조건식)와, 리스트 항목마�
 이벤트 동안 리스트 변경은 되돌리기 기록에 쌓이고, 실패하면 거꾸로 되돌리며 성공하면 지운 항목과 바뀐 text를 해제한다.
 항목의 text 필드를 읽으면 이벤트 공간에 복사한다.
 
+**키 있는 리스트**는 항목을 키 순서(수는 값, text는 바이트)로 두고 키마다 항목 하나만 둔다. 맵·집합·정렬된 맵을 따로
+두지 않는다. 리스트 하나가 순서의 규칙만 달리 가진다. 그래서 표 보기, 걸러진 표, 집계, 인덱스, 저장, 모듈 교체가 모두
+그대로다. 넣기(LIST_APPEND)는 반씩 나눠 찾은 자리에 넣고, 같은 키가 있으면 이벤트가 `exists`로 실패한다(호스트에는
+`PURE_CONFLICT`). 찾기는 O(log n)이다. −0과 +0은 한 키다. 키는 바뀌지 않으므로(검증기가 막는다) 순서는 넣기로만
+만들어진다.
+
+모듈을 열 때(시작과 교체) 키 있는 리스트가 키 순서가 아니면(키가 없던 리스트, 다른 필드가 키이던 리스트, 밖에서 바뀐
+저장본) 키 순서로 다시 놓고, 그 리스트의 인덱스는 자기 항목을 따라간다. 다시 놓은 리스트는 저장본도 다시 쓴다(레코드가
+바뀐 리스트와 같은 규칙). 같은 키의 항목이 둘 이상이면 모듈을 열지 않는다(`PURE_CONFLICT`). 데이터를 버려 맞추지 않는다.
+교체는 이전 모듈과 항목을 그대로 두고, 시작은 실패한다.
+
+검증(`test-module`): 넣기와 중복(한 이벤트에서 두 번째 넣기가 실패하면 첫 넣기도 되돌린다), 찾기·`has`·지우기, 바이트
+순서(빈 text가 처음, 앞이 같은 짧은 text가 먼저, UTF-8이 ASCII 뒤), −0과 0, 키 없는 모듈로 바꿨다 다시 키 있는 모듈로
+바꾸기(정렬, 인덱스가 항목을 따라감), 중복 키의 거절, 저장소에서 키가 생긴 리스트의 정렬과 그 저장본으로 다시 시작,
+키 있는 리스트 앱의 메모리·저장 대조(400단계 × 3, 재시작 포함), 검증 거절 8가지, 손상 모듈 20,000개(받아들인 모듈의
+키 있는 리스트는 늘 엄격한 키 순서다). aup는 무작위 3,600단계에서 text 키와 수 키 리스트가 파이썬 모델과 같음을 확인한다.
+
 키·frame·text 이벤트는 그 핸들러를 실행한다. 메시지 이벤트는 다음 순서로 처리한다.
 
 1. 입력 종류, 키 형식, 기준 리비전(`-1`은 없음)을 확인하고, 페이로드가 고정 부분보다 짧으면 `limit`.
@@ -152,7 +177,8 @@ v5는 값을 가진 채 합류하는 분기(조건식)와, 리스트 항목마�
    커밋이 실패하면 상태를 되돌린다. 결과 불명(`uncertain`)이면 상태만 되돌리고 그렇게 보고한다.
 
 모듈을 바꾸면(`pure_app_replace`) 상태는 이름과 종류가 같을 때 남는다. 레코드가 같으면 리스트를 그대로 쓰고,
-레코드가 바뀌었으면 항목마다 이름과 타입이 같은 필드를 옮기고 새 필드는 기본값으로 채운다. 커서와 인덱스는 대상
+레코드가 바뀌었으면 항목마다 이름과 타입이 같은 필드를 옮기고 새 필드는 기본값으로 채운다(키 있는 리스트는 그다음 키
+순서로 놓인다). 커서와 인덱스는 대상
 text·리스트가 남을 때만 위치를 유지한다.
 
 응답은 `pure_app_reply`로 순서대로 빌려준다. 페이로드와 문서의 익스텐트를 복사하지 않는다. 문서를 고친 이벤트의
@@ -248,6 +274,9 @@ text·리스트가 남을 때만 위치를 유지한다.
 실행기는 `-O2` text로 49.8 KB였다가 42.2 KB가 됐다. `module.c`가 34.0 → 27.0 KB, `module-list.c` 5.6 KB,
 `module-save.c` 4.8 KB, `module-text.c` 3.6 KB, `module-store.c` 1.2 KB다. 형식과 API는 그대로다.
 
+그 뒤 기능이 늘며 다시 49.9 KB다. 집계·걸러진 표·마크·가리키기가 `module.c`에 4.0 KB, 키 있는 리스트와 text 비교가
+3.7 KB(`module.c` +1.8 KB, `module-list.c`의 찾기·정렬 +1.9 KB)를 더했다. 기능 하나가 몇 KB인지를 기록해 둔다.
+
 - **검증기는 표를 읽는다.** 명령마다 인자가 무엇을 가리키는지(상태의 종류, 필드, 상수, 단위, 행, 분기, 깊이)와,
   어느 text나 리스트에 대해 동작하는지를 서명 표에 적는다. 커서·인덱스 피연산자는 모두 그 text나 리스트에 속해야
   하고, 밀어 넣는 커서·인덱스도 그렇다. 명령별 분기 대신 이 한 규칙으로 확인한다. 커서·인덱스가 아닌 값은
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;
 }