diff options
| -rw-r--r-- | docs/design/008-module-format.md | 41 | ||||
| -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 |
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; } |