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.

1 files changed, 35 insertions, 6 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나 리스트에 속해야
   하고, 밀어 넣는 커서·인덱스도 그렇다. 명령별 분기 대신 이 한 규칙으로 확인한다. 커서·인덱스가 아닌 값은