From efba82d75e4357c7e82b027b04a5ec9937f8443b Mon Sep 17 00:00:00 2001 From: eunhhu Date: Fri, 25 Sep 2026 11:48:51 +0100 Subject: Add typed messages and keyed documents to Pure modules Module format v2 adds byte values, message inputs with u32 and bytes-tail fields, one keyed byte collection, replies and require. The verifier checks every operand's type and the context each operation may run in, and allows branches and joins only at an empty stack, so typed values never merge. A message event opens its key's working version through a PureData host, conflicts early on a stale base revision, runs its handlers, and commits only if they succeed; a failed event leaves documents and states unchanged. Replies lend payload or document extents, and a document reply is copied before commit. pure_tree_data implements the host on tree store drafts, and pure-edit-module offers the document CLI contract of pure-edit from a module. test-module adds document semantics on an in-memory host (not found, create, conflict before bounds, limits, short payloads, busy commits, stable replies, require, state rollback), typed verifier rules, and 20,000 damaged message modules run safely under ASan/UBSan. --- prototypes/connections/Makefile | 8 +- prototypes/connections/edit-module.c | 184 ++++++++++++++ prototypes/connections/module-store.c | 44 ++++ prototypes/connections/module-store.h | 7 + prototypes/connections/module.c | 466 ++++++++++++++++++++++++++-------- prototypes/connections/module.h | 74 +++++- prototypes/connections/pure-run.c | 2 +- prototypes/connections/test-module.c | 420 ++++++++++++++++++++++++++---- 8 files changed, 1044 insertions(+), 161 deletions(-) create mode 100644 prototypes/connections/edit-module.c create mode 100644 prototypes/connections/module-store.c create mode 100644 prototypes/connections/module-store.h (limited to 'prototypes') diff --git a/prototypes/connections/Makefile b/prototypes/connections/Makefile index cce12d3..7d955f3 100644 --- a/prototypes/connections/Makefile +++ b/prototypes/connections/Makefile @@ -116,13 +116,17 @@ $(BUILD)/test-splice: test-splice.c program.c $(CORE) $(HOST) $(HEADERS) | $(BUI $(CC) $(CPPFLAGS) $(CFLAGS) -DPURE_RUNTIME_METRICS -DPURE_STORE_TEST test-splice.c program.c $(CORE) $(HOST) $(LDFLAGS) $(LDLIBS) -o $@ # Pure module format v1: loader/verifier/executor, its tests and a test host. -$(BUILD)/test-module: test-module.c module.c module.h result.h | $(BUILD) +$(BUILD)/test-module: test-module.c module.c module.h state.h result.h | $(BUILD) $(CC) $(CPPFLAGS) $(CFLAGS) test-module.c module.c $(LDFLAGS) -lm $(LDLIBS) -o $@ $(BUILD)/pure-run: pure-run.c module.c module.h result.h | $(BUILD) $(CC) $(CPPFLAGS) $(CFLAGS) pure-run.c module.c $(LDFLAGS) -lm $(LDLIBS) -o $@ -check-module: $(BUILD)/test-module $(BUILD)/pure-run +# The document CLI contract driven by a module on the tree store. +$(BUILD)/pure-edit-module: edit-module.c module.c module-store.c store-tree.c module.h module-store.h $(HEADERS) | $(BUILD) + $(CC) $(CPPFLAGS) $(CFLAGS) edit-module.c module.c module-store.c store-tree.c $(LDFLAGS) -lm $(LDLIBS) -o $@ + +check-module: $(BUILD)/test-module $(BUILD)/pure-run $(BUILD)/pure-edit-module $(BUILD)/test-module $(BUILD)/test-tree-store: test-tree-store.c store-tree.c $(HEADERS) | $(BUILD) diff --git a/prototypes/connections/edit-module.c b/prototypes/connections/edit-module.c new file mode 100644 index 0000000..d934345 --- /dev/null +++ b/prototypes/connections/edit-module.c @@ -0,0 +1,184 @@ +#define _POSIX_C_SOURCE 200809L +#include "module-store.h" +#include "store.h" +#include +#include +#include +#include + +/* The document CLI contract of edit.c, driven by a verified Pure module + * instead of a document program. The module declares keyed messages named + * show and edit; edit has u32 fields start and remove and a bytes tail. */ +static bool number(const char *text, uint64_t limit, uint64_t *out) { + if (!*text) return false; + uint64_t value = 0; + for (; *text; ++text) { + if (*text < '0' || *text > '9') return false; + unsigned digit = (unsigned)(*text - '0'); + if (digit > limit || value > (limit - digit) / 10) return false; + value = value * 10 + digit; + } + *out = value; + return true; +} + +static const char *message(PureResult status) { + switch (status) { + case PURE_OK: return "ok"; + case PURE_NOT_FOUND: return "not_found"; + case PURE_CONFLICT: return "conflict"; + case PURE_BUSY: return "busy"; + case PURE_BUDGET: return "payload_budget"; + case PURE_LIMIT: return "limit"; + case PURE_UNCERTAIN: return "durability_unknown"; + case PURE_DENIED: return "denied"; + case PURE_ALLOCATION: return "allocation"; + case PURE_INVALID: return "invalid"; + default: return "failed"; + } +} + +static bool valid_key(const char *key) { + size_t length = strlen(key); + if (!length || length > 64) return false; + for (size_t i = 0; i < length; ++i) { + char c = key[i]; + if (!((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9') || + c == '-' || c == '_')) return false; + } + return true; +} + +static void put32(unsigned char *to, uint32_t value) { + for (unsigned i = 0; i < 4; ++i) to[i] = (unsigned char)(value >> (8 * i)); +} + +static int field(const PureModule *m, int input, const char *name, uint8_t type) { + const PureInputShape *shape = &m->input[input]; + for (uint32_t i = 0; i < shape->field_count; ++i) + if (!strcmp(m->field[shape->field_start + i].name, name) && m->field[shape->field_start + i].type == type) + return (int)(shape->field_start + i); + return -1; +} + +static bool write_span(void *context, PureSpan span) { + return fwrite(span.data, 1, span.size, context) == span.size; +} + +static bool count_span(void *context, PureSpan span) { + *(size_t *)context += span.size; + return true; +} + +int main(int argc, char **argv) { + const char *module_path = NULL, *store_path = NULL; + size_t budget = 4u * 1024u * 1024u; + int at = 1; + for (; at + 1 < argc && !strncmp(argv[at], "--", 2); at += 2) { + uint64_t value; + if (!strcmp(argv[at], "--store")) store_path = argv[at + 1]; + else if (!strcmp(argv[at], "--module")) module_path = argv[at + 1]; + else if (!strcmp(argv[at], "--budget") && number(argv[at + 1], SIZE_MAX, &value)) budget = (size_t)value; + else goto usage; + } + if (!module_path || !store_path || at >= argc) goto usage; + bool show = !strcmp(argv[at], "show"), edit = !strcmp(argv[at], "edit"); + if ((!show && !edit && strcmp(argv[at], "apply")) || + argc - at != (show ? 2 : edit ? 6 : 4)) goto usage; + uint64_t expected = 0, offset = 0, remove = 0; + if (!show && !number(argv[at + 2], INT64_MAX, &expected)) goto usage; + if (edit && (!number(argv[at + 3], UINT32_MAX, &offset) || !number(argv[at + 4], UINT32_MAX, &remove))) goto usage; + + static unsigned char image[1 << 17]; + static PureModule module; + char error[160]; + FILE *source = fopen(module_path, "rb"); + size_t image_size = source ? fread(image, 1, sizeof(image), source) : 0; + if (!source || ferror(source) || image_size == sizeof(image)) { + if (source) fclose(source); + fputs("Module: cannot read module\n", stderr); + return 2; + } + fclose(source); + if (pure_module_load(image, image_size, &module, error, sizeof(error)) != PURE_OK) { + fprintf(stderr, "Module: %s\n", error); + return 2; + } + int input = pure_module_input(&module, show ? "show" : "edit"); + if (input < 0 || module.input[input].kind != PURE_KIND_MESSAGE || !module.input[input].keyed) { + fprintf(stderr, "Module: needs a keyed message named %s\n", show ? "show" : "edit"); + return 2; + } + const PureInputShape *shape = &module.input[input]; + int start_field = field(&module, input, "start", PURE_FIELD_U32); + int remove_field = field(&module, input, "remove", PURE_FIELD_U32); + size_t prefix = edit ? shape->prefix : 0; + if (edit && (start_field < 0 || remove_field < 0 || !shape->field_count || + module.field[shape->field_start + shape->field_count - 1].type != PURE_FIELD_BYTES)) { + fputs("edit requires u32 fields start and remove and trailing insertion bytes; use apply for a custom input\n", stderr); + return 2; + } + FILE *file = NULL; + size_t length = 0; + if (!show) { + file = fopen(argv[at + (edit ? 5 : 3)], "rb"); + if (!file) { perror("input"); return 2; } + long bytes; + if (fseek(file, 0, SEEK_END) || (bytes = ftell(file)) < 0 || + (uintmax_t)bytes > PURE_OBJECT_LIMIT - prefix || fseek(file, 0, SEEK_SET)) { + fputs("input must be a seekable file within the request size limit\n", stderr); + fclose(file); return 2; + } + length = (size_t)bytes; + } + if (pure_store_init(store_path) != PURE_OK) { + if (file) fclose(file); + fputs("cannot initialize store\n", stderr); return 2; + } + const char *key = argv[at + 1]; + if (!valid_key(key) || prefix + length > budget) { + if (file) fclose(file); + fprintf(stderr, "%s\n", valid_key(key) ? "payload_budget" : "invalid"); return 2; + } + unsigned char *payload = NULL; + if (!show) { + payload = calloc(1, prefix + length ? prefix + length : 1); + if (!payload) { fclose(file); fputs("allocation\n", stderr); return 2; } + if (edit) { + put32(payload + module.field[start_field].offset, (uint32_t)offset); + put32(payload + module.field[remove_field].offset, (uint32_t)remove); + } + bool valid = !length || fread(payload + prefix, 1, length, file) == length; + if (fgetc(file) != EOF || ferror(file)) valid = false; + if (fclose(file)) valid = false; + if (!valid) { + free(payload); + fputs("input changed or could not be read; nothing was applied\n", stderr); return 2; + } + } + PureApp app; + pure_app_start(&app, &module, pure_tree_data(store_path)); + PureResult status = pure_app_message(&app, (uint32_t)input, key, show ? -1 : (int64_t)expected, + (PureSpan){payload, prefix + length}); + size_t reply = 0; + if (status == PURE_OK) status = pure_app_reply(&app, count_span, &reply); + if (status == PURE_OK && show && reply > budget) { status = PURE_BUDGET; app.revision = 0; } + int exit_code = 0; + if (status != PURE_OK) { + fprintf(stderr, "{\"error\":\"%s\",\"revision\":\"%" PRId64 "\"}\n", message(status), app.revision); + exit_code = status == PURE_CONFLICT ? 3 : 2; + } else if (show) { + if (pure_app_reply(&app, write_span, stdout) != PURE_OK) exit_code = 2; + fprintf(stderr, "{\"revision\":\"%" PRId64 "\",\"bytes\":%zu}\n", app.revision, reply); + } else if (printf("{\"revision\":\"%" PRId64 "\",\"reply_bytes\":%zu}\n", app.revision, reply) < 0) exit_code = 2; + if (fflush(stdout)) exit_code = 2; + pure_app_finish(&app); + free(payload); + return exit_code; +usage: + fputs("pure-edit-module --module FILE --store DIRECTORY [--budget BYTES] show KEY\n" + "pure-edit-module --module FILE --store DIRECTORY [--budget BYTES] edit KEY REVISION BYTE_OFFSET REMOVE_BYTES INSERT_FILE\n" + "pure-edit-module --module FILE --store DIRECTORY [--budget BYTES] apply KEY REVISION INPUT_FILE\n" + "edit uses the module's start and remove fields; apply accepts its raw message bytes.\n", stderr); + return 2; +} diff --git a/prototypes/connections/module-store.c b/prototypes/connections/module-store.c new file mode 100644 index 0000000..941957b --- /dev/null +++ b/prototypes/connections/module-store.c @@ -0,0 +1,44 @@ +#include "module-store.h" + +static PureResult open_document(void *context, uint32_t collection, const char *key, + void **document, int64_t *revision) { + (void)collection; /* v2 modules have one collection: the store's key space */ + PureDraft *draft; + PureResult result = pure_draft_open(context, key, &draft); + if (result != PURE_OK) return result; + pure_draft_hold(draft, true); /* values read in the event stay readable */ + *document = draft; + *revision = pure_draft_revision(draft); + return PURE_OK; +} + +static PureVersion version(void *context, void *document) { + (void)context; + return pure_draft_version(document); +} + +static PureResult read(void *context, void *document, PureVersion at, size_t offset, size_t length, + bool (*visit)(void *, PureSpan), void *visit_context) { + (void)context; + return pure_draft_read_version(document, at, offset, length, visit, visit_context); +} + +static PureResult splice(void *context, void *document, size_t offset, size_t remove, PureSpan insert) { + (void)context; + return pure_draft_splice(document, offset, remove, insert); +} + +static PureResult commit(void *context, void *document, int64_t *revision) { + (void)context; + return pure_draft_commit(document, revision); +} + +static void close_document(void *context, void *document) { + (void)context; + pure_draft_close(document); +} + +PureData pure_tree_data(const char *path) { + return (PureData){.context = (void *)path, .open = open_document, .version = version, + .read = read, .splice = splice, .commit = commit, .close = close_document}; +} diff --git a/prototypes/connections/module-store.h b/prototypes/connections/module-store.h new file mode 100644 index 0000000..5f1c1a8 --- /dev/null +++ b/prototypes/connections/module-store.h @@ -0,0 +1,7 @@ +#ifndef PURE_MODULE_STORE_H +#define PURE_MODULE_STORE_H +#include "module.h" +/* Keyed module collections on the selected tree store: one event opens the + * message key as a held draft and commits it. The path outlives the app. */ +PureData pure_tree_data(const char *path); +#endif diff --git a/prototypes/connections/module.c b/prototypes/connections/module.c index 1d4d8a7..fbae2fd 100644 --- a/prototypes/connections/module.c +++ b/prototypes/connections/module.c @@ -1,15 +1,52 @@ #include "module.h" #include #include +#include #include -enum { STATE_BYTES = 16, TABLE_BYTES = 12, OP_BYTES = 16, KEY_INPUT = 1 }; -static const unsigned char magic[8] = {'P','U','R','E','M','O','D','1'}; -/* Operand stack effect per opcode, in PureOpcode order. */ -static const unsigned char pops[PURE_OP_COUNT] = - {0,0,0,2,2,2,2,1,2,2,2,2,2,2,2,2,1,2,2,3,1,1,0}; -static const unsigned char pushes[PURE_OP_COUNT] = - {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0}; +enum { STATE_BYTES = 16, COLLECTION_BYTES = 12, INPUT_BYTES = 16, FIELD_BYTES = 8, + TABLE_BYTES = 12, OP_BYTES = 16 }; +enum { T_NUM = 1, T_BYTES = 2, T_FIELD = 3 /* type of the named field */ }; +enum { FROM_PAYLOAD, FROM_DOCUMENT, FROM_COPY }; +/* Where an opcode may appear. */ +enum { IN_VIEW = 1, IN_HANDLER = 2, IN_MESSAGE = 4, IN_KEYED = 8 }; +static const unsigned char magic[8] = {'P','U','R','E','M','O','D','2'}; + +/* Operand types popped (bottom to top), the type pushed, and where allowed. */ +static const struct { unsigned char pops, in[3], out, where; } signature[PURE_OP_COUNT] = { + [PURE_OP_CONST] = {0, {0}, T_NUM, IN_VIEW | IN_HANDLER}, + [PURE_OP_LOAD] = {0, {0}, T_NUM, IN_VIEW | IN_HANDLER}, + [PURE_OP_DT] = {0, {0}, T_NUM, IN_HANDLER}, + [PURE_OP_ADD] = {2, {T_NUM, T_NUM}, T_NUM, IN_VIEW | IN_HANDLER}, + [PURE_OP_SUB] = {2, {T_NUM, T_NUM}, T_NUM, IN_VIEW | IN_HANDLER}, + [PURE_OP_MUL] = {2, {T_NUM, T_NUM}, T_NUM, IN_VIEW | IN_HANDLER}, + [PURE_OP_DIV] = {2, {T_NUM, T_NUM}, T_NUM, IN_VIEW | IN_HANDLER}, + [PURE_OP_NEG] = {1, {T_NUM}, T_NUM, IN_VIEW | IN_HANDLER}, + [PURE_OP_LT] = {2, {T_NUM, T_NUM}, T_NUM, IN_VIEW | IN_HANDLER}, + [PURE_OP_LE] = {2, {T_NUM, T_NUM}, T_NUM, IN_VIEW | IN_HANDLER}, + [PURE_OP_GT] = {2, {T_NUM, T_NUM}, T_NUM, IN_VIEW | IN_HANDLER}, + [PURE_OP_GE] = {2, {T_NUM, T_NUM}, T_NUM, IN_VIEW | IN_HANDLER}, + [PURE_OP_EQ] = {2, {T_NUM, T_NUM}, T_NUM, IN_VIEW | IN_HANDLER}, + [PURE_OP_NE] = {2, {T_NUM, T_NUM}, T_NUM, IN_VIEW | IN_HANDLER}, + [PURE_OP_AND] = {2, {T_NUM, T_NUM}, T_NUM, IN_VIEW | IN_HANDLER}, + [PURE_OP_OR] = {2, {T_NUM, T_NUM}, T_NUM, IN_VIEW | IN_HANDLER}, + [PURE_OP_NOT] = {1, {T_NUM}, T_NUM, IN_VIEW | IN_HANDLER}, + [PURE_OP_MIN] = {2, {T_NUM, T_NUM}, T_NUM, IN_VIEW | IN_HANDLER}, + [PURE_OP_MAX] = {2, {T_NUM, T_NUM}, T_NUM, IN_VIEW | IN_HANDLER}, + [PURE_OP_CLAMP] = {3, {T_NUM, T_NUM, T_NUM}, T_NUM, IN_VIEW | IN_HANDLER}, + [PURE_OP_STORE] = {1, {T_NUM}, 0, IN_HANDLER}, + [PURE_OP_JZ] = {1, {T_NUM}, 0, IN_HANDLER}, + [PURE_OP_JMP] = {0, {0}, 0, IN_HANDLER}, + [PURE_OP_FIELD] = {0, {0}, T_FIELD, IN_MESSAGE}, + [PURE_OP_DOC] = {0, {0}, T_BYTES, IN_KEYED}, + [PURE_OP_DOC_SIZE] = {0, {0}, T_NUM, IN_KEYED}, + [PURE_OP_LEN] = {1, {T_BYTES}, T_NUM, IN_HANDLER}, + [PURE_OP_REPLACE] = {3, {T_NUM, T_NUM, T_BYTES}, 0, IN_KEYED}, + [PURE_OP_REPLY] = {1, {T_BYTES}, 0, IN_MESSAGE}, + [PURE_OP_REQUIRE] = {1, {T_NUM}, 0, IN_HANDLER}, +}; + +static uint32_t read16(const unsigned char *p) { return (uint32_t)p[0] | (uint32_t)p[1] << 8; } static uint32_t read32(const unsigned char *p) { return (uint32_t)p[0] | (uint32_t)p[1] << 8 | (uint32_t)p[2] << 16 | (uint32_t)p[3] << 24; @@ -36,6 +73,18 @@ static bool key_name(const char *key) { return false; } +/* A document key: 1..64 bytes of [A-Za-z0-9_-], as every Pure store accepts. */ +static bool document_key(const char *key) { + size_t length = key ? strlen(key) : 0; + if (!length || length > 64) return false; + for (size_t i = 0; i < length; ++i) { + char c = key[i]; + if (!((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9') || + c == '-' || c == '_')) return false; + } + return true; +} + /* Strings are [u8 length][bytes]; a name is an ASCII identifier of 1..31 bytes. */ static bool name_at(const unsigned char *strings, uint32_t size, uint32_t offset, bool identifier, char out[PURE_MODULE_NAME]) { @@ -52,49 +101,72 @@ static bool name_at(const unsigned char *strings, uint32_t size, uint32_t offset return true; } -static bool merge(int16_t *height, uint32_t at, int value) { - if (height[at] < 0) height[at] = (int16_t)value; - return height[at] == value; -} +/* The input whose handler this is, or -1 for frame. */ +static int event_input(uint32_t event) { return event ? (int)((event - 1) / 2) : -1; } -/* Every instruction is reachable, every path meets the same stack height at a - * join, and the block ends with 0 (handler) or 1 (view) values. Branches only - * move forward, so one pass in order sees all incoming edges first. */ -static bool verify_block(const PureModule *m, PureBlock block, bool view, +/* Types and heights are checked per instruction. Branches go forward within + * the block and every join happens with an empty operand stack, so control + * flow never merges typed values. Handlers end empty, views with one number. */ +static bool verify_block(const PureModule *m, PureBlock block, bool view, uint32_t event, char *error, size_t size, unsigned index) { if (block.start > m->code_count || block.length > m->code_count - block.start) return reject(error, size, "code range outside module", index); if (view && !block.length) return reject(error, size, "empty view", index); - int16_t height[PURE_MODULE_CODE + 1]; - for (uint32_t i = 0; i <= block.length; ++i) height[i] = -1; - height[0] = 0; - for (uint32_t i = 0; i < block.length; ++i) { - const PureOp *op = &m->code[block.start + i]; - int h = height[i]; - if (h < 0) return reject(error, size, "unreachable instruction", block.start + i); - if (op->op >= PURE_OP_COUNT) return reject(error, size, "unknown opcode", block.start + i); - if (view && (op->op == PURE_OP_DT || op->op >= PURE_OP_STORE)) - return reject(error, size, "view with an effect or branch", block.start + i); - if (h < pops[op->op]) return reject(error, size, "stack underflow", block.start + i); - int next = h - pops[op->op] + pushes[op->op]; - if (next > PURE_MODULE_STACK) return reject(error, size, "stack overflow", block.start + i); - bool uses_arg = op->op == PURE_OP_LOAD || op->op == PURE_OP_STORE || - op->op == PURE_OP_JZ || op->op == PURE_OP_JMP; + int input = view ? -1 : event_input(event); + const PureInputShape *shape = input >= 0 ? &m->input[input] : NULL; + unsigned where = view ? IN_VIEW : IN_HANDLER; + if (shape && shape->kind == PURE_KIND_MESSAGE) where |= IN_MESSAGE | (shape->keyed ? IN_KEYED : 0); + unsigned char types[PURE_MODULE_STACK], target[PURE_MODULE_CODE + 1] = {0}; + int height = 0; + bool reachable = true; + for (uint32_t i = 0; i <= block.length; ++i) { + uint32_t pc = block.start + i; + if (!reachable && target[i]) { reachable = true; height = 0; } + else if (target[i] && height) return reject(error, size, "join with a non-empty stack", pc); + if (i == block.length) break; + if (!reachable) return reject(error, size, "unreachable instruction", pc); + const PureOp *op = &m->code[pc]; + if (op->op >= PURE_OP_COUNT) return reject(error, size, "unknown opcode", pc); + unsigned allowed = signature[op->op].where; + if (!(allowed & where)) { + if (view) return reject(error, size, "view with an effect or branch", pc); + if (allowed & IN_KEYED) return reject(error, size, "document operation outside a keyed message handler", pc); + return reject(error, size, "message operation outside a message handler", pc); + } + bool uses_arg = op->op == PURE_OP_LOAD || op->op == PURE_OP_STORE || op->op == PURE_OP_JZ || + op->op == PURE_OP_JMP || op->op == PURE_OP_FIELD || op->op == PURE_OP_DOC || + op->op == PURE_OP_DOC_SIZE || op->op == PURE_OP_REPLACE; if ((!uses_arg && op->arg) || (op->op != PURE_OP_CONST && op->value != 0) || (op->op == PURE_OP_CONST && !isfinite(op->value))) - return reject(error, size, "non-canonical operand", block.start + i); + return reject(error, size, "non-canonical operand", pc); if ((op->op == PURE_OP_LOAD || op->op == PURE_OP_STORE) && op->arg >= m->states) - return reject(error, size, "unknown state", block.start + i); + return reject(error, size, "unknown state", pc); + if (op->op == PURE_OP_FIELD && op->arg >= shape->field_count) + return reject(error, size, "unknown field", pc); + if ((op->op == PURE_OP_DOC || op->op == PURE_OP_DOC_SIZE || op->op == PURE_OP_REPLACE) && + op->arg >= m->collections) return reject(error, size, "unknown collection", pc); + unsigned pops = signature[op->op].pops; + if (height < (int)pops) return reject(error, size, "stack underflow", pc); + for (unsigned k = 0; k < pops; ++k) + if (types[height - (int)pops + (int)k] != signature[op->op].in[k]) + return reject(error, size, "operand type", pc); + height -= (int)pops; + unsigned char out = signature[op->op].out; + if (out == T_FIELD) out = m->field[shape->field_start + op->arg].type == PURE_FIELD_U32 ? T_NUM : T_BYTES; + if (out) { + if (height == PURE_MODULE_STACK) return reject(error, size, "stack overflow", pc); + types[height++] = out; + } if (op->op == PURE_OP_JZ || op->op == PURE_OP_JMP) { - if (op->arg <= block.start + i || op->arg > block.start + block.length) - return reject(error, size, "branch not forward within its block", block.start + i); - if (!merge(height, op->arg - block.start, next)) - return reject(error, size, "stack height differs at branch target", block.start + i); + if (op->arg <= pc || op->arg > block.start + block.length) + return reject(error, size, "branch not forward within its block", pc); + if (height) return reject(error, size, "branch with a non-empty stack", pc); + target[op->arg - block.start] = 1; + if (op->op == PURE_OP_JMP) reachable = false; } - if (op->op != PURE_OP_JMP && !merge(height, i + 1, next)) - return reject(error, size, "stack height differs at join", block.start + i); } - if (height[block.length] != (view ? 1 : 0)) + if (!reachable) return reject(error, size, "block end is unreachable", index); + if (view ? height != 1 || types[0] != T_NUM : height != 0) return reject(error, size, view ? "view must leave one value" : "handler must leave no value", index); return true; } @@ -105,70 +177,114 @@ PureResult pure_module_load(const void *bytes, size_t size, PureModule *out, if (error_size) error[0] = 0; memset(out, 0, sizeof(*out)); if (!p || size < PURE_MODULE_HEADER || memcmp(p, magic, sizeof(magic))) - return reject(error, error_size, "not a Pure module v1", 0), PURE_INVALID; - out->states = (uint16_t)(p[8] | p[9] << 8); - out->inputs = (uint16_t)(p[10] | p[11] << 8); - out->views = (uint16_t)(p[12] | p[13] << 8); - out->handlers = (uint16_t)(p[14] | p[15] << 8); + return reject(error, error_size, "not a Pure module v2", 0), PURE_INVALID; + out->states = (uint16_t)read16(p + 8); + out->inputs = (uint16_t)read16(p + 10); + out->views = (uint16_t)read16(p + 12); + out->handlers = (uint16_t)read16(p + 14); out->code_count = read32(p + 16); uint32_t strings = read32(p + 20); - if (read32(p + 24) || read32(p + 28)) - return reject(error, error_size, "reserved header bytes", 24), PURE_INVALID; + out->fields = (uint16_t)read16(p + 24); + out->collections = (uint16_t)read16(p + 26); + if (read32(p + 28)) return reject(error, error_size, "reserved header bytes", 28), PURE_INVALID; if (out->states > PURE_MODULE_STATES || out->inputs > PURE_MODULE_INPUTS || out->views > PURE_MODULE_VIEWS || out->handlers > PURE_MODULE_HANDLERS || - out->code_count > PURE_MODULE_CODE || strings > PURE_MODULE_STRINGS) + out->code_count > PURE_MODULE_CODE || strings > PURE_MODULE_STRINGS || + out->fields > PURE_MODULE_FIELDS || out->collections > PURE_MODULE_COLLECTIONS) return reject(error, error_size, "module exceeds a limit", 8), PURE_LIMIT; size_t expected = PURE_MODULE_HEADER + (size_t)out->states * STATE_BYTES + - ((size_t)out->inputs + out->views + out->handlers) * TABLE_BYTES + + (size_t)out->collections * COLLECTION_BYTES + (size_t)out->inputs * INPUT_BYTES + + (size_t)out->fields * FIELD_BYTES + ((size_t)out->views + out->handlers) * TABLE_BYTES + (size_t)out->code_count * OP_BYTES + strings; if (size != expected) return reject(error, error_size, "module size", (unsigned)expected), PURE_INVALID; const unsigned char *at = p + PURE_MODULE_HEADER; - const unsigned char *table = at + (size_t)out->states * STATE_BYTES + - ((size_t)out->inputs + out->views + out->handlers) * TABLE_BYTES; - const unsigned char *text = table + (size_t)out->code_count * OP_BYTES; - for (uint32_t i = 0; i < out->code_count; ++i, table += OP_BYTES) { - if (table[1] || table[2] || table[3]) - return reject(error, error_size, "instruction padding", i), PURE_INVALID; - out->code[i] = (PureOp){.op = table[0], .arg = read32(table + 4), .value = read_double(table + 8)}; - } + const unsigned char *text = p + size - strings; for (uint32_t i = 0; i < out->states; ++i, at += STATE_BYTES) { out->initial[i] = read_double(at + 8); - if (!name_at(text, strings, read32(at), true, out->state_names[i]) || read32(at + 4)) + if (!name_at(text, strings, read32(at), true, out->state_names[i])) return reject(error, error_size, "state name", i), PURE_INVALID; + if (read32(at + 4)) return reject(error, error_size, "state type", i), PURE_INVALID; if (!isfinite(out->initial[i])) return reject(error, error_size, "non-finite initial value", i), PURE_INVALID; } - for (uint32_t i = 0; i < out->inputs; ++i, at += TABLE_BYTES) { + for (uint32_t i = 0; i < out->collections; ++i, at += COLLECTION_BYTES) { + if (!name_at(text, strings, read32(at), true, out->collection_names[i])) + return reject(error, error_size, "collection name", i), PURE_INVALID; + if (read32(at + 4) != 1 || read32(at + 8) != 1) + return reject(error, error_size, "collection must hold bytes by key", i), PURE_INVALID; + } + uint32_t next_field = 0; + const unsigned char *fields = at + (size_t)out->inputs * INPUT_BYTES; + for (uint32_t i = 0; i < out->inputs; ++i, at += INPUT_BYTES) { + PureInputShape *shape = &out->input[i]; + shape->kind = at[4]; + shape->keyed = at[5]; + shape->field_start = (uint16_t)read16(at + 12); + shape->field_count = (uint16_t)read16(at + 14); if (!name_at(text, strings, read32(at), true, out->input_names[i])) return reject(error, error_size, "input name", i), PURE_INVALID; - if (read32(at + 4) != KEY_INPUT || !name_at(text, strings, read32(at + 8), false, out->input_keys[i]) || - !key_name(out->input_keys[i])) return reject(error, error_size, "input key", i), PURE_INVALID; - for (uint32_t k = 0; k < i; ++k) - if (!strcmp(out->input_keys[k], out->input_keys[i])) - return reject(error, error_size, "duplicate key", i), PURE_INVALID; + if (read16(at + 6) || at[5] > 1) return reject(error, error_size, "input flags", i), PURE_INVALID; + if (shape->kind == PURE_KIND_KEY) { + if (shape->keyed || shape->field_start || shape->field_count || + !name_at(text, strings, read32(at + 8), false, out->input_keys[i]) || + !key_name(out->input_keys[i])) return reject(error, error_size, "input key", i), PURE_INVALID; + for (uint32_t k = 0; k < i; ++k) + if (out->input[k].kind == PURE_KIND_KEY && !strcmp(out->input_keys[k], out->input_keys[i])) + return reject(error, error_size, "duplicate key", i), PURE_INVALID; + continue; + } + if (shape->kind != PURE_KIND_MESSAGE || read32(at + 8) || shape->field_start != next_field || + shape->field_count > out->fields - next_field) + return reject(error, error_size, "message shape", i), PURE_INVALID; + /* Fixed u32le fields in order, then at most one bytes tail. */ + for (uint32_t f = 0; f < shape->field_count; ++f) { + const unsigned char *entry = fields + (size_t)(next_field + f) * FIELD_BYTES; + PureField *field = &out->field[next_field + f]; + field->type = (uint8_t)read32(entry + 4); + if (!name_at(text, strings, read32(entry), true, field->name) || + (field->type != PURE_FIELD_U32 && field->type != PURE_FIELD_BYTES) || read32(entry + 4) > 2 || + (field->type == PURE_FIELD_BYTES && f + 1 != shape->field_count)) + return reject(error, error_size, "message field", next_field + f), PURE_INVALID; + for (uint32_t k = 0; k < f; ++k) + if (!strcmp(out->field[next_field + k].name, field->name)) + return reject(error, error_size, "duplicate field", next_field + f), PURE_INVALID; + field->offset = shape->prefix; + if (field->type == PURE_FIELD_U32) shape->prefix += 4; + } + next_field += shape->field_count; } + if (next_field != out->fields) return reject(error, error_size, "unused message fields", next_field), PURE_INVALID; + at = fields + (size_t)out->fields * FIELD_BYTES; for (uint32_t i = 0; i < out->views; ++i, at += TABLE_BYTES) { if (!name_at(text, strings, read32(at), true, out->view_names[i])) return reject(error, error_size, "view name", i), PURE_INVALID; out->view_code[i] = (PureBlock){read32(at + 4), read32(at + 8)}; } for (uint32_t i = 0; i < out->handlers; ++i, at += TABLE_BYTES) { - out->handler[i] = (PureHandler){read32(at), {read32(at + 4), read32(at + 8)}}; - if (out->handler[i].event > 2u * out->inputs) + uint32_t event = read32(at); + out->handler[i] = (PureHandler){event, {read32(at + 4), read32(at + 8)}}; + int input = event_input(event); + if (event > 2u * out->inputs || (input >= 0 && out->input[input].kind == PURE_KIND_MESSAGE && !(event & 1))) return reject(error, error_size, "handler event", i), PURE_INVALID; } - /* States, inputs and views share one namespace. */ - const char *names[PURE_MODULE_STATES + PURE_MODULE_INPUTS + PURE_MODULE_VIEWS]; + for (uint32_t i = 0; i < out->code_count; ++i, at += OP_BYTES) { + if (at[1] || at[2] || at[3]) return reject(error, error_size, "instruction padding", i), PURE_INVALID; + out->code[i] = (PureOp){.op = at[0], .arg = read32(at + 4), .value = read_double(at + 8)}; + } + /* States, collections, inputs and views share one namespace. */ + const char *names[PURE_MODULE_STATES + PURE_MODULE_COLLECTIONS + PURE_MODULE_INPUTS + PURE_MODULE_VIEWS]; size_t count = 0; for (uint32_t i = 0; i < out->states; ++i) names[count++] = out->state_names[i]; + for (uint32_t i = 0; i < out->collections; ++i) names[count++] = out->collection_names[i]; for (uint32_t i = 0; i < out->inputs; ++i) names[count++] = out->input_names[i]; for (uint32_t i = 0; i < out->views; ++i) names[count++] = out->view_names[i]; for (size_t i = 0; i < count; ++i) for (size_t k = 0; k < i; ++k) if (!strcmp(names[i], names[k])) return reject(error, error_size, "duplicate name", (unsigned)i), PURE_INVALID; for (uint32_t i = 0; i < out->views; ++i) - if (!verify_block(out, out->view_code[i], true, error, error_size, i)) return PURE_INVALID; + if (!verify_block(out, out->view_code[i], true, 0, error, error_size, i)) return PURE_INVALID; for (uint32_t i = 0; i < out->handlers; ++i) - if (!verify_block(out, out->handler[i].code, false, error, error_size, i)) return PURE_INVALID; + if (!verify_block(out, out->handler[i].code, false, out->handler[i].event, error, error_size, i)) + return PURE_INVALID; return PURE_OK; } @@ -186,41 +302,123 @@ int pure_module_view(const PureModule *m, const char *name) { return find(m->vie static double minimum(double a, double b) { return a < b || (a == b && signbit(a)) ? a : b; } static double maximum(double a, double b) { return a > b || (a == b && !signbit(a)) ? a : b; } -/* Run a verified block. Stack bounds were proven at load. */ -static PureFault run(const PureModule *m, double *values, PureBlock block, double dt, - double *result, uint32_t *fault_pc) { - double stack[PURE_MODULE_STACK]; +typedef struct { double num; PureBytes bytes; } Slot; +typedef struct { + PureApp *app; + const PureInputShape *shape; /* message, or NULL */ + double dt; + bool modified, exists; +} Event; + +static PureResult fault(PureApp *app, PureFault kind, uint32_t pc) { + if (app) { app->fault = kind; app->fault_pc = pc; } + return kind == PURE_FAULT_LIMIT ? PURE_LIMIT : kind == PURE_FAULT_NOT_FOUND ? PURE_NOT_FOUND : PURE_INVALID; +} + +static bool gather(void *context, PureSpan span) { + unsigned char **out = context; + memcpy(*out, span.data, span.size); + *out += span.size; + return true; +} + +/* A contiguous copy of a document range, for inserting a document value. */ +static PureResult materialize(PureApp *app, PureBytes value, unsigned char **out) { + *out = malloc(value.length ? (size_t)value.length : 1); + if (!*out) return PURE_ALLOCATION; + unsigned char *cursor = *out; + PureResult result = app->data.read(app->data.context, app->document, value.version, + (size_t)value.offset, (size_t)value.length, gather, &cursor); + if (result != PURE_OK) { free(*out); *out = NULL; } + return result; +} + +/* Run a verified block. Types and stack bounds were proven at load. */ +static PureResult run(const PureModule *m, double *values, PureBlock block, Event *ev, double *result) { + Slot stack[PURE_MODULE_STACK]; size_t sp = 0; + PureApp *app = ev ? ev->app : NULL; uint32_t pc = block.start, end = block.start + block.length; while (pc < end) { const PureOp *op = &m->code[pc]; double a, b, value; switch (op->op) { - case PURE_OP_CONST: stack[sp++] = op->value; ++pc; continue; - case PURE_OP_LOAD: stack[sp++] = values[op->arg]; ++pc; continue; - case PURE_OP_DT: stack[sp++] = dt; ++pc; continue; - case PURE_OP_STORE: values[op->arg] = stack[--sp]; ++pc; continue; - case PURE_OP_JZ: pc = stack[--sp] == 0 ? op->arg : pc + 1; continue; + case PURE_OP_CONST: stack[sp++].num = op->value; ++pc; continue; + case PURE_OP_LOAD: stack[sp++].num = values[op->arg]; ++pc; continue; + case PURE_OP_DT: stack[sp++].num = ev->dt; ++pc; continue; + case PURE_OP_STORE: values[op->arg] = stack[--sp].num; ++pc; continue; + case PURE_OP_JZ: pc = stack[--sp].num == 0 ? op->arg : pc + 1; continue; case PURE_OP_JMP: pc = op->arg; continue; - case PURE_OP_NEG: stack[sp - 1] = -stack[sp - 1]; ++pc; continue; - case PURE_OP_NOT: stack[sp - 1] = stack[sp - 1] == 0; ++pc; continue; + case PURE_OP_NEG: stack[sp - 1].num = -stack[sp - 1].num; ++pc; continue; + case PURE_OP_NOT: stack[sp - 1].num = stack[sp - 1].num == 0; ++pc; continue; case PURE_OP_CLAMP: { - double high = stack[--sp], low = stack[--sp]; - if (low > high) { *fault_pc = pc; return PURE_FAULT_CLAMP; } - stack[sp - 1] = maximum(low, minimum(stack[sp - 1], high)); + double high = stack[--sp].num, low = stack[--sp].num; + if (low > high) return fault(app, PURE_FAULT_CLAMP, pc); + stack[sp - 1].num = maximum(low, minimum(stack[sp - 1].num, high)); ++pc; continue; } + case PURE_OP_FIELD: { + const PureField *field = &m->field[ev->shape->field_start + op->arg]; + if (field->type == PURE_FIELD_U32) { + const unsigned char *p = app->payload.data + field->offset; + stack[sp++].num = (double)read32(p); + } else { + stack[sp++].bytes = (PureBytes){FROM_PAYLOAD, {0, 0}, field->offset, + app->payload.size - field->offset}; + } + ++pc; + continue; + } + case PURE_OP_DOC: { + if (!ev->exists) return fault(app, PURE_FAULT_NOT_FOUND, pc); + PureVersion version = app->data.version(app->data.context, app->document); + stack[sp++].bytes = (PureBytes){FROM_DOCUMENT, version, 0, version.bytes}; + ++pc; + continue; + } + case PURE_OP_DOC_SIZE: + stack[sp++].num = (double)app->data.version(app->data.context, app->document).bytes; + ++pc; + continue; + case PURE_OP_LEN: stack[sp - 1].num = (double)stack[sp - 1].bytes.length; ++pc; continue; + case PURE_OP_REPLACE: { + PureBytes insert = stack[--sp].bytes; + double last = stack[--sp].num, first = stack[--sp].num; + double size = (double)app->data.version(app->data.context, app->document).bytes; + if (first != floor(first) || last != floor(last) || first < 0 || last < first || last > size) + return fault(app, PURE_FAULT_LIMIT, pc); + unsigned char *copy = NULL; + PureSpan span = {app->payload.data + insert.offset, (size_t)insert.length}; + if (insert.source == FROM_DOCUMENT) { + PureResult copied = materialize(app, insert, ©); + if (copied != PURE_OK) return copied; + span.data = copy; + } + PureResult spliced = app->data.splice(app->data.context, app->document, (size_t)first, + (size_t)(last - first), span); + free(copy); + if (spliced == PURE_LIMIT) return fault(app, PURE_FAULT_LIMIT, pc); + if (spliced != PURE_OK) return spliced; + ev->modified = ev->exists = true; + ++pc; + continue; + } + case PURE_OP_REPLY: app->reply = stack[--sp].bytes; app->has_reply = true; ++pc; continue; + case PURE_OP_REQUIRE: + if (stack[--sp].num == 0) return fault(app, PURE_FAULT_LIMIT, pc); + ++pc; + continue; default: break; } - b = stack[--sp]; - a = stack[sp - 1]; + b = stack[--sp].num; + a = stack[sp - 1].num; switch (op->op) { case PURE_OP_ADD: value = a + b; break; case PURE_OP_SUB: value = a - b; break; case PURE_OP_MUL: value = a * b; break; case PURE_OP_DIV: - if (b == 0) { *fault_pc = pc; return PURE_FAULT_DIVIDE; } + if (b == 0) return fault(app, PURE_FAULT_DIVIDE, pc); value = a / b; break; case PURE_OP_LT: value = a < b; break; @@ -234,21 +432,30 @@ static PureFault run(const PureModule *m, double *values, PureBlock block, doubl case PURE_OP_MIN: value = minimum(a, b); break; default: value = maximum(a, b); break; } - if (!isfinite(value)) { *fault_pc = pc; return PURE_FAULT_NON_FINITE; } - stack[sp - 1] = value; + if (!isfinite(value)) return fault(app, PURE_FAULT_NON_FINITE, pc); + stack[sp - 1].num = value; ++pc; } - if (result) *result = stack[0]; - return PURE_FAULT_NONE; + if (result) *result = stack[0].num; + return PURE_OK; } -void pure_app_start(PureApp *app, const PureModule *module) { - *app = (PureApp){.module = module, .fault_pc = UINT32_MAX}; +void pure_app_start(PureApp *app, const PureModule *module, PureData data) { + *app = (PureApp){.module = module, .data = data, .fault_pc = UINT32_MAX}; memcpy(app->values, module->initial, sizeof(double) * module->states); } +void pure_app_finish(PureApp *app) { + if (app->document) app->data.close(app->data.context, app->document); + free(app->copied); + app->document = NULL; + app->copied = NULL; + app->has_reply = false; + app->payload = (PureSpan){0}; +} + /* All handlers of one event run in module order against a pending copy. */ -static PureResult dispatch(PureApp *app, uint32_t event, double dt) { +static PureResult dispatch(PureApp *app, uint32_t event, Event *ev) { const PureModule *m = app->module; double pending[PURE_MODULE_STATES]; memcpy(pending, app->values, sizeof(pending)); @@ -256,8 +463,8 @@ static PureResult dispatch(PureApp *app, uint32_t event, double dt) { app->fault_pc = UINT32_MAX; for (uint32_t i = 0; i < m->handlers; ++i) { if (m->handler[i].event != event) continue; - app->fault = run(m, pending, m->handler[i].code, dt, NULL, &app->fault_pc); - if (app->fault) return PURE_INVALID; + PureResult result = run(m, pending, m->handler[i].code, ev, NULL); + if (result != PURE_OK) return result; } memcpy(app->values, pending, sizeof(pending)); ++app->events; @@ -265,25 +472,84 @@ static PureResult dispatch(PureApp *app, uint32_t event, double dt) { } PureResult pure_app_frame(PureApp *app) { - PureResult result = dispatch(app, 0, 1.0 / 60.0); + Event ev = {.app = app, .dt = 1.0 / 60.0}; + PureResult result = dispatch(app, 0, &ev); if (result == PURE_OK) ++app->ticks; return result; } PureResult pure_app_input(PureApp *app, uint32_t input, PureEdge edge) { - if (input >= app->module->inputs || (edge != PURE_EDGE_DOWN && edge != PURE_EDGE_UP)) return PURE_INVALID; - return dispatch(app, 1 + 2 * input + (edge == PURE_EDGE_UP), 0); + if (input >= app->module->inputs || app->module->input[input].kind != PURE_KIND_KEY || + (edge != PURE_EDGE_DOWN && edge != PURE_EDGE_UP)) return PURE_INVALID; + Event ev = {.app = app}; + return dispatch(app, 1 + 2 * input + (edge == PURE_EDGE_UP), &ev); +} + +PureResult pure_app_message(PureApp *app, uint32_t input, const char *key, int64_t base, PureSpan payload) { + pure_app_finish(app); + const PureModule *m = app->module; + app->fault = PURE_FAULT_NONE; + app->fault_pc = UINT32_MAX; + app->revision = 0; + if (input >= m->inputs || m->input[input].kind != PURE_KIND_MESSAGE || base < -1 || + (payload.size && !payload.data) || (m->input[input].keyed ? !document_key(key) : key != NULL)) + return PURE_INVALID; + const PureInputShape *shape = &m->input[input]; + if (payload.size < shape->prefix) return fault(app, PURE_FAULT_LIMIT, UINT32_MAX); + app->payload = payload; + if (shape->keyed && m->collections) { + if (!app->data.open) return PURE_INVALID; + PureResult opened = app->data.open(app->data.context, 0, key, &app->document, &app->revision); + if (opened != PURE_OK) { app->document = NULL; pure_app_finish(app); return opened; } + if (base >= 0 && base != app->revision) { pure_app_finish(app); return PURE_CONFLICT; } + } + Event ev = {.app = app, .shape = shape, .exists = app->revision > 0}; + double before[PURE_MODULE_STATES]; + memcpy(before, app->values, sizeof(before)); + uint64_t events = app->events; + PureResult result = dispatch(app, 1 + 2 * input, &ev); + if (result != PURE_OK) { pure_app_finish(app); return result; } + if (ev.modified) { + if (base < 0) result = PURE_INVALID; + /* Commit rebases the working version; keep a document reply by copying it. */ + if (result == PURE_OK && app->has_reply && app->reply.source == FROM_DOCUMENT) { + unsigned char *copy; + result = materialize(app, app->reply, ©); + if (result == PURE_OK) { + app->copied = copy; + app->reply = (PureBytes){FROM_COPY, {0, 0}, 0, app->reply.length}; + } + } + if (result == PURE_OK) result = app->data.commit(app->data.context, app->document, &app->revision); + if (result != PURE_OK) { + /* A failed commit leaves the stored document; states stay as before. */ + memcpy(app->values, before, sizeof(before)); + app->events = events; + if (result != PURE_UNCERTAIN) pure_app_finish(app); + } + } + return result; +} + +PureResult pure_app_reply(const PureApp *app, bool (*visit)(void *, PureSpan), void *context) { + if (!app->has_reply || !app->reply.length) return PURE_OK; + const PureBytes *r = &app->reply; + if (r->source == FROM_PAYLOAD) + return visit(context, (PureSpan){app->payload.data + r->offset, (size_t)r->length}), PURE_OK; + if (r->source == FROM_COPY) return visit(context, (PureSpan){app->copied, (size_t)r->length}), PURE_OK; + return app->data.read(app->data.context, app->document, r->version, (size_t)r->offset, + (size_t)r->length, visit, context); } bool pure_app_view(const PureApp *app, uint32_t view, double *out) { if (view >= app->module->views) return false; double values[PURE_MODULE_STATES]; - uint32_t pc; memcpy(values, app->values, sizeof(values)); - return run(app->module, values, app->module->view_code[view], 0, out, &pc) == PURE_FAULT_NONE; + return run(app->module, values, app->module->view_code[view], NULL, out) == PURE_OK; } void pure_app_replace(PureApp *app, const PureModule *module) { + pure_app_finish(app); double values[PURE_MODULE_STATES]; for (uint32_t i = 0; i < module->states; ++i) { int old = pure_module_state(app->module, module->state_names[i]); diff --git a/prototypes/connections/module.h b/prototypes/connections/module.h index ab2d6fc..16306e5 100644 --- a/prototypes/connections/module.h +++ b/prototypes/connections/module.h @@ -1,43 +1,61 @@ #ifndef PURE_MODULE_H #define PURE_MODULE_H +#include "flow.h" #include "result.h" +#include "state.h" #include #include #include -/* Pure module format v1 (docs/design/008-module-format.md). A toolchain such - * as aup produces it; Pure verifies it completely before anything executes, so - * a loaded module cannot overflow the stack, branch backwards or name a - * missing state. Fixed capacity: no allocation in load, run or replace. */ +/* Pure module format v2 (docs/design/008-module-format.md). A toolchain such + * as aup produces it; Pure verifies it completely before anything executes: + * operand types, stack heights, forward-only branches, names and effects. + * Fixed capacity: loading and running allocate nothing except a copied reply. */ enum { PURE_MODULE_STATES = 32, PURE_MODULE_INPUTS = 8, PURE_MODULE_VIEWS = 24, PURE_MODULE_HANDLERS = 64, PURE_MODULE_CODE = 512, PURE_MODULE_STACK = 64, - PURE_MODULE_NAME = 32, PURE_MODULE_STRINGS = 32768, PURE_MODULE_HEADER = 32 + PURE_MODULE_NAME = 32, PURE_MODULE_STRINGS = 32768, PURE_MODULE_HEADER = 32, + PURE_MODULE_FIELDS = 32, PURE_MODULE_COLLECTIONS = 1 }; typedef enum { PURE_OP_CONST, PURE_OP_LOAD, PURE_OP_DT, PURE_OP_ADD, PURE_OP_SUB, PURE_OP_MUL, PURE_OP_DIV, PURE_OP_NEG, PURE_OP_LT, PURE_OP_LE, PURE_OP_GT, PURE_OP_GE, PURE_OP_EQ, PURE_OP_NE, PURE_OP_AND, PURE_OP_OR, PURE_OP_NOT, PURE_OP_MIN, - PURE_OP_MAX, PURE_OP_CLAMP, PURE_OP_STORE, PURE_OP_JZ, PURE_OP_JMP, PURE_OP_COUNT + PURE_OP_MAX, PURE_OP_CLAMP, PURE_OP_STORE, PURE_OP_JZ, PURE_OP_JMP, + PURE_OP_FIELD, PURE_OP_DOC, PURE_OP_DOC_SIZE, PURE_OP_LEN, PURE_OP_REPLACE, + PURE_OP_REPLY, PURE_OP_REQUIRE, PURE_OP_COUNT } PureOpcode; +typedef enum { PURE_KIND_KEY = 1, PURE_KIND_MESSAGE = 2 } PureInputKind; +typedef enum { PURE_FIELD_U32 = 1, PURE_FIELD_BYTES = 2 } PureFieldType; typedef enum { PURE_EDGE_DOWN, PURE_EDGE_UP } PureEdge; typedef enum { - PURE_FAULT_NONE, PURE_FAULT_DIVIDE, PURE_FAULT_NON_FINITE, PURE_FAULT_CLAMP + PURE_FAULT_NONE, PURE_FAULT_DIVIDE, PURE_FAULT_NON_FINITE, PURE_FAULT_CLAMP, + PURE_FAULT_LIMIT, PURE_FAULT_NOT_FOUND } PureFault; typedef struct { double value; uint32_t arg; uint8_t op; } PureOp; typedef struct { uint32_t start, length; } PureBlock; typedef struct { uint32_t event; PureBlock code; } PureHandler; +typedef struct { char name[PURE_MODULE_NAME]; uint8_t type; uint32_t offset; } PureField; +typedef struct { + uint8_t kind; + bool keyed; + uint16_t field_start, field_count; + uint32_t prefix; /* fixed payload bytes before an optional bytes tail */ +} PureInputShape; typedef struct { - uint16_t states, inputs, views, handlers; + uint16_t states, inputs, views, handlers, fields, collections; uint32_t code_count; char state_names[PURE_MODULE_STATES][PURE_MODULE_NAME]; char input_names[PURE_MODULE_INPUTS][PURE_MODULE_NAME]; char view_names[PURE_MODULE_VIEWS][PURE_MODULE_NAME]; + char collection_names[PURE_MODULE_COLLECTIONS][PURE_MODULE_NAME]; char input_keys[PURE_MODULE_INPUTS][PURE_MODULE_NAME]; + PureInputShape input[PURE_MODULE_INPUTS]; + PureField field[PURE_MODULE_FIELDS]; double initial[PURE_MODULE_STATES]; PureBlock view_code[PURE_MODULE_VIEWS]; PureHandler handler[PURE_MODULE_HANDLERS]; @@ -52,19 +70,53 @@ int pure_module_state(const PureModule *, const char *name); int pure_module_input(const PureModule *, const char *name); int pure_module_view(const PureModule *, const char *name); -/* One app instance: state values of a module. Every event is atomic: on a - * fault the values are exactly those before the event. */ +/* Keyed collections live in a data host (for example the tree store). One + * event opens at most one document, the message's key, at its current + * version; edits stay in that working version until the event commits it. */ +typedef struct { + void *context; + PureResult (*open)(void *context, uint32_t collection, const char *key, + void **document, int64_t *revision); + PureVersion (*version)(void *context, void *document); + PureResult (*read)(void *context, void *document, PureVersion, size_t offset, size_t length, + bool (*visit)(void *, PureSpan), void *visit_context); + PureResult (*splice)(void *context, void *document, size_t offset, size_t remove, PureSpan insert); + PureResult (*commit)(void *context, void *document, int64_t *revision); + void (*close)(void *context, void *document); +} PureData; + +/* A byte value: a range of the event's payload, of a document version, or of + * a reply copied before commit. Internal to one event. */ +typedef struct { uint8_t source; PureVersion version; uint64_t offset, length; } PureBytes; + +/* One app instance: state values of a module and at most one open event. + * Every event is atomic: on failure states and documents are unchanged. */ typedef struct { const PureModule *module; + PureData data; double values[PURE_MODULE_STATES]; PureFault fault; uint32_t fault_pc; uint64_t ticks, events; + /* Current message event, kept until pure_app_finish. */ + void *document; + PureSpan payload; + bool has_reply; + PureBytes reply; + unsigned char *copied; + int64_t revision; } PureApp; -void pure_app_start(PureApp *, const PureModule *); +void pure_app_start(PureApp *, const PureModule *, PureData data); PureResult pure_app_frame(PureApp *); PureResult pure_app_input(PureApp *, uint32_t input, PureEdge); +/* Deliver a message. base is the revision the sender edited, or -1 for none; + * a handler that edits the document needs one. payload stays alive until + * pure_app_finish. On return app->revision is the document's revision. */ +PureResult pure_app_message(PureApp *, uint32_t input, const char *key, int64_t base, PureSpan payload); +/* Visit the reply of the last message in order, without copying. */ +PureResult pure_app_reply(const PureApp *, bool (*visit)(void *, PureSpan), void *context); +void pure_app_finish(PureApp *); bool pure_app_view(const PureApp *, uint32_t view, double *out); /* Switch to another verified module. States keep their value by name; new * states start at their initial value. The module must outlive the app. */ diff --git a/prototypes/connections/pure-run.c b/prototypes/connections/pure-run.c index 9059a1e..71b7d0a 100644 --- a/prototypes/connections/pure-run.c +++ b/prototypes/connections/pure-run.c @@ -48,7 +48,7 @@ int main(int argc, char **argv) { } unsigned active = 0; PureApp app; - pure_app_start(&app, &modules[active]); + pure_app_start(&app, &modules[active], (PureData){0}); char line[4096]; int status = 0; while (fgets(line, sizeof(line), stdin)) { diff --git a/prototypes/connections/test-module.c b/prototypes/connections/test-module.c index fc0d1d4..fb3d304 100644 --- a/prototypes/connections/test-module.c +++ b/prototypes/connections/test-module.c @@ -7,13 +7,16 @@ #define CHECK(x) do { if (!(x)) { fprintf(stderr, "%s:%d: %s\n", __FILE__, __LINE__, #x); abort(); } } while (0) typedef struct { const char *name; double initial; } S; -typedef struct { const char *name, *key; } I; +typedef struct { const char *name; uint32_t type; } F; +/* kind 0 is a key input; otherwise PURE_KIND_MESSAGE with fields. */ +typedef struct { const char *name, *key; int kind; bool keyed; const F *fields; size_t nfields; } I; +#define KEY(name, key) {name, key, 0, false, NULL, 0} typedef struct { const char *name; uint32_t start, length; } V; typedef struct { uint32_t event, start, length; } H; typedef struct { uint8_t op; uint32_t arg; double value; } O; typedef struct { const S *s; size_t ns; const I *in; size_t ni; const V *v; size_t nv; - const H *h; size_t nh; const O *o; size_t no; + const H *h; size_t nh; const O *o; size_t no; const char *const *c; size_t nc; } Spec; static unsigned char *put32(unsigned char *p, uint32_t v) { @@ -28,15 +31,20 @@ static unsigned char *put_double(unsigned char *p, double value) { return put32(p + 4, (uint32_t)(bits >> 32)); } -/* Test-side encoder for format v1; the toolchain has its own. */ +/* Test-side encoder for format v2; the toolchain has its own. */ static size_t build(unsigned char *out, Spec spec) { unsigned char strings[4096]; size_t used = 0; - uint32_t offset[256]; + const char *text[512]; + uint32_t offset[512]; size_t names = 0; - const char *text[256]; for (size_t i = 0; i < spec.ns; ++i) text[names++] = spec.s[i].name; - for (size_t i = 0; i < spec.ni; ++i) { text[names++] = spec.in[i].name; text[names++] = spec.in[i].key; } + for (size_t i = 0; i < spec.nc; ++i) text[names++] = spec.c[i]; + for (size_t i = 0; i < spec.ni; ++i) { + text[names++] = spec.in[i].name; + if (!spec.in[i].kind) text[names++] = spec.in[i].key; + for (size_t f = 0; f < spec.in[i].nfields; ++f) text[names++] = spec.in[i].fields[f].name; + } for (size_t i = 0; i < spec.nv; ++i) text[names++] = spec.v[i].name; for (size_t i = 0; i < names; ++i) { size_t length = strlen(text[i]); @@ -45,19 +53,39 @@ static size_t build(unsigned char *out, Spec spec) { memcpy(strings + used, text[i], length); used += length; } + size_t fields = 0; + for (size_t i = 0; i < spec.ni; ++i) fields += spec.in[i].nfields; unsigned char *p = out; - memcpy(p, "PUREMOD1", 8); + memset(p, 0, 32); + memcpy(p, "PUREMOD2", 8); p[8] = (unsigned char)spec.ns; p[9] = (unsigned char)(spec.ns >> 8); - p[10] = (unsigned char)spec.ni; p[11] = 0; - p[12] = (unsigned char)spec.nv; p[13] = 0; - p[14] = (unsigned char)spec.nh; p[15] = 0; + p[10] = (unsigned char)spec.ni; p[12] = (unsigned char)spec.nv; p[14] = (unsigned char)spec.nh; put32(p + 16, (uint32_t)spec.no); put32(p + 20, (uint32_t)used); - memset(p + 24, 0, 8); + p[24] = (unsigned char)fields; p[26] = (unsigned char)spec.nc; p += 32; size_t n = 0; for (size_t i = 0; i < spec.ns; ++i) { p = put32(p, offset[n++]); p = put32(p, 0); p = put_double(p, spec.s[i].initial); } - for (size_t i = 0; i < spec.ni; ++i) { p = put32(p, offset[n++]); p = put32(p, 1); p = put32(p, offset[n++]); } + for (size_t i = 0; i < spec.nc; ++i) { p = put32(p, offset[n++]); p = put32(p, 1); p = put32(p, 1); } + uint32_t field_offsets[64], field_start = 0; + size_t nf = 0; + for (size_t i = 0; i < spec.ni; ++i) { + const I *in = &spec.in[i]; + p = put32(p, offset[n++]); + *p++ = (unsigned char)(in->kind ? in->kind : 1); *p++ = in->keyed; *p++ = 0; *p++ = 0; + p = put32(p, in->kind ? 0 : offset[n++]); + uint32_t first = in->kind ? field_start : 0; /* key inputs have no fields */ + *p++ = (unsigned char)first; *p++ = (unsigned char)(first >> 8); + *p++ = (unsigned char)in->nfields; *p++ = 0; + for (size_t f = 0; f < in->nfields; ++f) field_offsets[nf++] = offset[n++]; + field_start += (uint32_t)in->nfields; + } + nf = 0; + for (size_t i = 0; i < spec.ni; ++i) + for (size_t f = 0; f < spec.in[i].nfields; ++f) { + p = put32(p, field_offsets[nf++]); + p = put32(p, spec.in[i].fields[f].type); + } for (size_t i = 0; i < spec.nv; ++i) { p = put32(p, offset[n++]); p = put32(p, spec.v[i].start); p = put32(p, spec.v[i].length); } for (size_t i = 0; i < spec.nh; ++i) { p = put32(p, spec.h[i].event); p = put32(p, spec.h[i].start); p = put32(p, spec.h[i].length); } for (size_t i = 0; i < spec.no; ++i) { @@ -79,7 +107,7 @@ static PureResult load(Spec spec, PureModule *out) { } #define LEN(a) (sizeof(a) / sizeof(*(a))) -#define SPEC(s, in, v, h, o) ((Spec){s, LEN(s), in, LEN(in), v, LEN(v), h, LEN(h), o, LEN(o)}) +#define SPEC(s, in, v, h, o) ((Spec){s, LEN(s), in, LEN(in), v, LEN(v), h, LEN(h), o, LEN(o), NULL, 0}) enum { C = PURE_OP_CONST, L = PURE_OP_LOAD, DT = PURE_OP_DT, ADD = PURE_OP_ADD, MUL = PURE_OP_MUL, DIV = PURE_OP_DIV, GT = PURE_OP_GT, MIN = PURE_OP_MIN, @@ -87,7 +115,7 @@ enum { C = PURE_OP_CONST, L = PURE_OP_LOAD, DT = PURE_OP_DT, ADD = PURE_OP_ADD, JMP = PURE_OP_JMP, NEG = PURE_OP_NEG }; static const S counter_states[] = {{"count", 0}, {"x", 3}}; -static const I counter_inputs[] = {{"tap", "Space"}, {"move", "ArrowRight"}}; +static const I counter_inputs[] = {KEY("tap", "Space"), KEY("move", "ArrowRight")}; static const V counter_views[] = {{"label", 0, 1}, {"width", 1, 6}}; static const O counter_code[] = { {L, 0, 0}, /* 0 view label */ @@ -112,7 +140,7 @@ static void behaviour(void) { static const V views[] = {{"label", 0, 1}, {"width", 26, 7}}; CHECK(load(SPEC(counter_states, counter_inputs, views, counter_handlers, counter_code), &module_a) == PURE_OK); PureApp app; - pure_app_start(&app, &module_a); + pure_app_start(&app, &module_a, (PureData){0}); double value; CHECK(pure_app_view(&app, 1, &value) && value == 40); for (int i = 0; i < 25; ++i) CHECK(pure_app_input(&app, 0, PURE_EDGE_DOWN) == PURE_OK); @@ -134,7 +162,7 @@ static void behaviour(void) { static const V no_views[1]; static const H no_handlers[1]; static const O no_code[1]; - CHECK(load((Spec){next_states, 2, no_inputs, 0, no_views, 0, no_handlers, 0, no_code, 0}, &module_b) == PURE_OK); + CHECK(load((Spec){next_states, 2, no_inputs, 0, no_views, 0, no_handlers, 0, no_code, 0, NULL, 0}, &module_b) == PURE_OK); pure_app_replace(&app, &module_b); CHECK(app.module == &module_b && app.values[0] == 7 && app.values[1] == 25); pure_app_replace(&app, &module_a); @@ -144,7 +172,7 @@ static void behaviour(void) { /* A fault leaves every state exactly as before the event. */ static void faults(void) { static const S states[] = {{"a", 1}, {"b", 2}}; - static const I inputs[] = {{"one", "KeyA"}, {"two", "KeyB"}, {"three", "Digit3"}}; + static const I inputs[] = {KEY("one", "KeyA"), KEY("two", "KeyB"), KEY("three", "Digit3")}; static const O code[] = { {C, 0, 9}, {ST, 0, 0}, {C, 0, 1}, {C, 0, 0}, {DIV, 0, 0}, {ST, 1, 0}, /* 0 divide */ {C, 0, 9}, {ST, 0, 0}, {C, 0, 1e308}, {C, 0, 10}, {MUL, 0, 0}, {ST, 1, 0}, /* 6 overflow */ @@ -157,7 +185,7 @@ static void faults(void) { static const V views[] = {{"low", 21, 4}, {"high", 25, 4}}; CHECK(load(SPEC(states, inputs, views, handlers, code), &module_a) == PURE_OK); PureApp app; - pure_app_start(&app, &module_a); + pure_app_start(&app, &module_a, (PureData){0}); const PureFault expected[] = {PURE_FAULT_DIVIDE, PURE_FAULT_NON_FINITE, PURE_FAULT_CLAMP}; for (uint32_t i = 0; i < 3; ++i) { CHECK(pure_app_input(&app, i, PURE_EDGE_DOWN) == PURE_INVALID && app.fault == expected[i]); @@ -178,9 +206,9 @@ static void rejections(void) { static const S bad_name[] = {{"1a", 0}}; static const S long_name[] = {{"abcdefghijklmnopqrstuvwxyz012345", 0}}; static const S non_finite[] = {{"a", INFINITY}}; - static const I i1[] = {{"k", "Space"}}; - static const I bad_key[] = {{"k", "KeyAA"}}; - static const I dup_key[] = {{"k", "Space"}, {"j", "Space"}}; + static const I i1[] = {KEY("k", "Space")}; + static const I bad_key[] = {KEY("k", "KeyAA")}; + static const I dup_key[] = {KEY("k", "Space"), KEY("j", "Space")}; static const V clash[] = {{"a", 0, 1}}; static const V v_store[] = {{"v", 0, 2}}; static const V v_dt[] = {{"v", 2, 1}}; @@ -208,28 +236,28 @@ static void rejections(void) { for (int i = 0; i < 65; ++i) overflow[i] = (O){C, 0, 1}; overflow[65] = (O){ST, 0, 0}; const Rejection cases[] = { - {"duplicate name", {dup, 2, i1, 0, clash, 0, none, 0, load_a, 0}, PURE_INVALID}, - {"state name", {bad_name, 1, i1, 0, clash, 0, none, 0, load_a, 0}, PURE_INVALID}, - {"state name", {long_name, 1, i1, 0, clash, 0, none, 0, load_a, 0}, PURE_INVALID}, - {"non-finite initial value", {non_finite, 1, i1, 0, clash, 0, none, 0, load_a, 0}, PURE_INVALID}, - {"input key", {s1, 1, bad_key, 1, clash, 0, none, 0, load_a, 0}, PURE_INVALID}, - {"duplicate key", {s1, 1, dup_key, 2, clash, 0, none, 0, load_a, 0}, PURE_INVALID}, - {"duplicate name", {s1, 1, i1, 0, clash, 1, none, 0, load_a, 1}, PURE_INVALID}, - {"view with an effect", {s1, 1, i1, 0, v_store, 1, none, 0, store, 3}, PURE_INVALID}, - {"view with an effect", {s1, 1, i1, 0, v_dt, 1, none, 0, store, 3}, PURE_INVALID}, - {"empty view", {s1, 1, i1, 0, v_empty, 1, none, 0, store, 3}, PURE_INVALID}, - {"handler event", {s1, 1, i1, 1, clash, 0, h_bad_event, 1, store, 3}, PURE_INVALID}, - {"branch not forward", {s1, 1, i1, 0, clash, 0, h_two, 1, back, 2}, PURE_INVALID}, - {"branch not forward", {s1, 1, i1, 0, clash, 0, h_two, 1, beyond, 2}, PURE_INVALID}, - {"stack underflow", {s1, 1, i1, 0, clash, 0, h_all, 1, under, 1}, PURE_INVALID}, - {"stack height differs", {s1, 1, i1, 0, clash, 0, h_five, 1, join, 5}, PURE_INVALID}, - {"handler must leave no value", {s1, 1, i1, 0, clash, 0, h_two, 1, leftover, 2}, PURE_INVALID}, - {"unknown state", {s1, 1, i1, 0, clash, 0, h_two, 1, unknown_state, 2}, PURE_INVALID}, - {"non-canonical operand", {s1, 1, i1, 0, clash, 0, h_two, 1, nan_const, 2}, PURE_INVALID}, - {"non-canonical operand", {s1, 1, i1, 0, clash, 0, h0, 1, noncanon, 3}, PURE_INVALID}, - {"unreachable instruction", {s1, 1, i1, 0, clash, 0, h_four, 1, unreachable, 4}, PURE_INVALID}, - {"unknown opcode", {s1, 1, i1, 0, clash, 0, h_two, 1, bad_op, 2}, PURE_INVALID}, - {"stack overflow", {s1, 1, i1, 0, clash, 0, (H[]){{0, 0, 66}}, 1, overflow, 66}, PURE_INVALID}, + {"duplicate name", {dup, 2, i1, 0, clash, 0, none, 0, load_a, 0, NULL, 0}, PURE_INVALID}, + {"state name", {bad_name, 1, i1, 0, clash, 0, none, 0, load_a, 0, NULL, 0}, PURE_INVALID}, + {"state name", {long_name, 1, i1, 0, clash, 0, none, 0, load_a, 0, NULL, 0}, PURE_INVALID}, + {"non-finite initial value", {non_finite, 1, i1, 0, clash, 0, none, 0, load_a, 0, NULL, 0}, PURE_INVALID}, + {"input key", {s1, 1, bad_key, 1, clash, 0, none, 0, load_a, 0, NULL, 0}, PURE_INVALID}, + {"duplicate key", {s1, 1, dup_key, 2, clash, 0, none, 0, load_a, 0, NULL, 0}, PURE_INVALID}, + {"duplicate name", {s1, 1, i1, 0, clash, 1, none, 0, load_a, 1, NULL, 0}, PURE_INVALID}, + {"view with an effect", {s1, 1, i1, 0, v_store, 1, none, 0, store, 3, NULL, 0}, PURE_INVALID}, + {"view with an effect", {s1, 1, i1, 0, v_dt, 1, none, 0, store, 3, NULL, 0}, PURE_INVALID}, + {"empty view", {s1, 1, i1, 0, v_empty, 1, none, 0, store, 3, NULL, 0}, PURE_INVALID}, + {"handler event", {s1, 1, i1, 1, clash, 0, h_bad_event, 1, store, 3, NULL, 0}, PURE_INVALID}, + {"branch not forward", {s1, 1, i1, 0, clash, 0, h_two, 1, back, 2, NULL, 0}, PURE_INVALID}, + {"branch not forward", {s1, 1, i1, 0, clash, 0, h_two, 1, beyond, 2, NULL, 0}, PURE_INVALID}, + {"stack underflow", {s1, 1, i1, 0, clash, 0, h_all, 1, under, 1, NULL, 0}, PURE_INVALID}, + {"join with a non-empty stack", {s1, 1, i1, 0, clash, 0, h_five, 1, join, 5, NULL, 0}, PURE_INVALID}, + {"handler must leave no value", {s1, 1, i1, 0, clash, 0, h_two, 1, leftover, 2, NULL, 0}, PURE_INVALID}, + {"unknown state", {s1, 1, i1, 0, clash, 0, h_two, 1, unknown_state, 2, NULL, 0}, PURE_INVALID}, + {"non-canonical operand", {s1, 1, i1, 0, clash, 0, h_two, 1, nan_const, 2, NULL, 0}, PURE_INVALID}, + {"non-canonical operand", {s1, 1, i1, 0, clash, 0, h0, 1, noncanon, 3, NULL, 0}, PURE_INVALID}, + {"unreachable instruction", {s1, 1, i1, 0, clash, 0, h_four, 1, unreachable, 4, NULL, 0}, PURE_INVALID}, + {"unknown opcode", {s1, 1, i1, 0, clash, 0, h_two, 1, bad_op, 2, NULL, 0}, PURE_INVALID}, + {"stack overflow", {s1, 1, i1, 0, clash, 0, (H[]){{0, 0, 66}}, 1, overflow, 66, NULL, 0}, PURE_INVALID}, }; for (size_t i = 0; i < LEN(cases); ++i) { PureResult result = load(cases[i].spec, &module_a); @@ -241,9 +269,9 @@ static void rejections(void) { static S many[33]; static char many_names[33][8]; for (unsigned i = 0; i < 33; ++i) { snprintf(many_names[i], 8, "s%u", i % 100u); many[i] = (S){many_names[i], 0}; } - CHECK(load((Spec){many, 33, i1, 0, clash, 0, none, 0, load_a, 0}, &module_a) == PURE_LIMIT); + CHECK(load((Spec){many, 33, i1, 0, clash, 0, none, 0, load_a, 0, NULL, 0}, &module_a) == PURE_LIMIT); static unsigned char bytes[65536]; - size_t size = build(bytes, (Spec){s1, 1, i1, 0, clash, 0, none, 0, load_a, 0}); + size_t size = build(bytes, (Spec){s1, 1, i1, 0, clash, 0, none, 0, load_a, 0, NULL, 0}); CHECK(pure_module_load(bytes, size - 1, &module_a, error, sizeof(error)) == PURE_INVALID); CHECK(pure_module_load(bytes, size + 1, &module_a, error, sizeof(error)) == PURE_INVALID); bytes[0] = 'X'; @@ -272,7 +300,7 @@ static void mutations(void) { if (pure_module_load(bytes, size, &module_a, error, sizeof(error)) != PURE_OK) continue; ++accepted; PureApp app; - pure_app_start(&app, &module_a); + pure_app_start(&app, &module_a, (PureData){0}); for (unsigned e = 0; e < 16; ++e) { if (e % 3 == 0) pure_app_frame(&app); else pure_app_input(&app, e % 4, e & 1 ? PURE_EDGE_UP : PURE_EDGE_DOWN); @@ -283,12 +311,310 @@ static void mutations(void) { printf("{\"module_mutations\":20000,\"accepted_after_damage\":%u}\n", accepted); } +static Spec editor_spec; + +/* An in-memory data host: every splice makes a new immutable version. */ +typedef struct { char key[65]; unsigned char *bytes; size_t size; int64_t revision; } Stored; +typedef struct { + Stored docs[8]; + size_t count, limit; + bool busy; + unsigned opened, closed; +} Memory; +typedef struct { + Memory *memory; + int index; /* -1 for an absent key */ + int64_t base; + unsigned char *versions[64]; + size_t sizes[64], count; +} Doc; + +static Stored *stored(Memory *m, const char *key) { + for (size_t i = 0; i < m->count; ++i) if (!strcmp(m->docs[i].key, key)) return &m->docs[i]; + return NULL; +} + +static PureResult fake_open(void *context, uint32_t collection, const char *key, void **out, int64_t *revision) { + Memory *m = context; + CHECK(collection == 0); + Doc *d = calloc(1, sizeof(*d)); + Stored *s = stored(m, key); + d->memory = m; + d->index = s ? (int)(s - m->docs) : -1; + if (!s) { + CHECK(m->count < 8); + d->index = (int)m->count; + snprintf(m->docs[m->count++].key, 65, "%s", key); + s = &m->docs[d->index]; + } + d->base = s->revision; + d->versions[0] = malloc(s->size + 1); + memcpy(d->versions[0], s->bytes ? s->bytes : (unsigned char *)"", s->size); + d->sizes[0] = s->size; + d->count = 1; + ++m->opened; + *out = d; + *revision = s->revision; + return PURE_OK; +} + +static PureVersion fake_version(void *context, void *document) { + (void)context; + Doc *d = document; + return (PureVersion){d->count - 1, d->sizes[d->count - 1]}; +} + +/* Two spans per read, so replies arrive in pieces. */ +static PureResult fake_read(void *context, void *document, PureVersion at, size_t offset, size_t length, + bool (*visit)(void *, PureSpan), void *visit_context) { + (void)context; + Doc *d = document; + CHECK(at.ref < d->count && at.bytes == d->sizes[at.ref] && offset + length <= at.bytes); + size_t half = length / 2; + if (half && !visit(visit_context, (PureSpan){d->versions[at.ref] + offset, half})) return PURE_OK; + if (length - half) visit(visit_context, (PureSpan){d->versions[at.ref] + offset + half, length - half}); + return PURE_OK; +} + +static PureResult fake_splice(void *context, void *document, size_t offset, size_t remove, PureSpan insert) { + Memory *m = context; + Doc *d = document; + size_t size = d->sizes[d->count - 1], next = size - remove + insert.size; + if (next > m->limit) return PURE_LIMIT; + CHECK(d->count < 64); + unsigned char *bytes = malloc(next + 1); + memcpy(bytes, d->versions[d->count - 1], offset); + if (insert.size) memcpy(bytes + offset, insert.data, insert.size); + memcpy(bytes + offset + insert.size, d->versions[d->count - 1] + offset + remove, size - offset - remove); + d->versions[d->count] = bytes; + d->sizes[d->count++] = next; + return PURE_OK; +} + +static PureResult fake_commit(void *context, void *document, int64_t *revision) { + Memory *m = context; + Doc *d = document; + Stored *s = &m->docs[d->index]; + *revision = s->revision; + if (m->busy) return PURE_BUSY; + if (s->revision != d->base) return PURE_CONFLICT; + free(s->bytes); + s->size = d->sizes[d->count - 1]; + s->bytes = malloc(s->size + 1); + memcpy(s->bytes, d->versions[d->count - 1], s->size); + *revision = ++s->revision; + /* Like a tree draft, a commit rebases: earlier versions are gone. */ + for (size_t i = 0; i + 1 < d->count; ++i) { free(d->versions[i]); d->versions[i] = NULL; d->sizes[i] = 0; } + d->versions[0] = d->versions[d->count - 1]; + d->sizes[0] = d->sizes[d->count - 1]; + d->count = 1; + d->base = s->revision; + return PURE_OK; +} + +static void fake_close(void *context, void *document) { + Memory *m = context; + Doc *d = document; + for (size_t i = 0; i < d->count; ++i) free(d->versions[i]); + free(d); + ++m->closed; +} + +static PureData fake_data(Memory *m) { + return (PureData){m, fake_open, fake_version, fake_read, fake_splice, fake_commit, fake_close}; +} + +typedef struct { unsigned char bytes[256]; size_t size, spans; } Collected; + +static bool count_bytes(void *context, PureSpan span) { + *(size_t *)context += span.size; + return true; +} + +static bool collect(void *context, PureSpan span) { + Collected *c = context; + CHECK(c->size + span.size <= sizeof(c->bytes)); + memcpy(c->bytes + c->size, span.data, span.size); + c->size += span.size; + ++c->spans; + return true; +} + +static bool replied(const PureApp *app, const char *text) { + Collected c = {{0}, 0, 0}; + CHECK(pure_app_reply(app, collect, &c) == PURE_OK); + return c.size == strlen(text) && !memcmp(c.bytes, text, c.size); +} + +static PureSpan edit_payload(unsigned char *buffer, uint32_t start, uint32_t remove, const char *insert) { + put32(buffer, start); + put32(buffer + 4, remove); + memcpy(buffer + 8, insert, strlen(insert)); + return (PureSpan){buffer, 8 + strlen(insert)}; +} + +enum { FIELD = PURE_OP_FIELD, DOC = PURE_OP_DOC, SIZE = PURE_OP_DOC_SIZE, LEN_ = PURE_OP_LEN, + REPL = PURE_OP_REPLACE, REPLY = PURE_OP_REPLY, REQ = PURE_OP_REQUIRE, LE = PURE_OP_LE }; + +/* The document editor as a module: show replies the document, edit splices + * start .. start + remove with insert, replies insert and counts edits. A + * keep message replies the document read before its own edit; guarded edits + * require the final size to stay within 8 bytes. */ +static void messages(void) { + static const F edit_fields[] = {{"start", 1}, {"remove", 1}, {"insert", 2}}; + static const I inputs[] = { + {"show", NULL, PURE_KIND_MESSAGE, true, NULL, 0}, + {"edit", NULL, PURE_KIND_MESSAGE, true, edit_fields, 3}, + {"keep", NULL, PURE_KIND_MESSAGE, true, edit_fields + 2, 1}, + {"guarded", NULL, PURE_KIND_MESSAGE, true, edit_fields, 3}, + KEY("tick", "Space"), + }; + static const S states[] = {{"edits", 0}}; + static const char *const collections[] = {"documents"}; + static const O code[] = { + {DOC, 0, 0}, {REPLY, 0, 0}, /* 0 show */ + {FIELD, 0, 0}, {FIELD, 0, 0}, {FIELD, 1, 0}, {ADD, 0, 0}, {FIELD, 2, 0}, /* 2 edit */ + {REPL, 0, 0}, {FIELD, 2, 0}, {REPLY, 0, 0}, {L, 0, 0}, {C, 0, 1}, {ADD, 0, 0}, {ST, 0, 0}, + {DOC, 0, 0}, {REPLY, 0, 0}, {C, 0, 0}, {C, 0, 0}, {FIELD, 0, 0}, {REPL, 0, 0}, /* 14 keep: prepend */ + {FIELD, 0, 0}, {FIELD, 0, 0}, {FIELD, 1, 0}, {ADD, 0, 0}, {FIELD, 2, 0}, /* 20 guarded */ + {REPL, 0, 0}, {L, 0, 0}, {C, 0, 1}, {ADD, 0, 0}, {ST, 0, 0}, + {SIZE, 0, 0}, {C, 0, 8}, {LE, 0, 0}, {REQ, 0, 0}, + }; + static const H handlers[] = {{1, 0, 2}, {3, 2, 12}, {5, 14, 6}, {7, 20, 14}}; + static const V views[] = {{"count", 0, 0}}; + Spec spec = {states, 1, inputs, 5, views, 0, handlers, 4, code, LEN(code), collections, 1}; + editor_spec = spec; + PureResult loaded = load(spec, &module_a); + if (loaded != PURE_OK) { fprintf(stderr, "%s\n", error); abort(); } + Memory memory = {.limit = 100}; + PureApp app; + pure_app_start(&app, &module_a, fake_data(&memory)); + unsigned char buffer[64]; + + CHECK(pure_app_message(&app, 0, "doc", -1, (PureSpan){0}) == PURE_NOT_FOUND && app.revision == 0); + CHECK(pure_app_message(&app, 1, "doc", 0, edit_payload(buffer, 0, 0, "hello")) == PURE_OK); + CHECK(app.revision == 1 && replied(&app, "hello") && app.values[0] == 1); + CHECK(pure_app_message(&app, 0, "doc", -1, (PureSpan){0}) == PURE_OK && app.revision == 1 && replied(&app, "hello")); + /* stale base conflicts before bounds; bounds fail as limit; nothing changes */ + CHECK(pure_app_message(&app, 1, "doc", 0, edit_payload(buffer, 99, 0, "x")) == PURE_CONFLICT && app.revision == 1); + CHECK(pure_app_message(&app, 1, "doc", 1, edit_payload(buffer, 99, 0, "x")) == PURE_LIMIT && app.revision == 1); + CHECK(pure_app_message(&app, 1, "doc", 1, edit_payload(buffer, 2, 9, "x")) == PURE_LIMIT); + CHECK(pure_app_message(&app, 1, "doc", 1, (PureSpan){buffer, 7}) == PURE_LIMIT && app.revision == 0); + CHECK(pure_app_message(&app, 1, "doc", -1, edit_payload(buffer, 0, 0, "x")) == PURE_INVALID); + CHECK(pure_app_message(&app, 1, "bad/key", 1, edit_payload(buffer, 0, 0, "x")) == PURE_INVALID); + CHECK(pure_app_message(&app, 4, "doc", 1, (PureSpan){0}) == PURE_INVALID); + CHECK(memory.docs[0].revision == 1 && memory.docs[0].size == 5 && app.values[0] == 1); + /* A busy commit changes neither the document nor the states. */ + memory.busy = true; + CHECK(pure_app_message(&app, 1, "doc", 1, edit_payload(buffer, 5, 0, "!")) == PURE_BUSY); + memory.busy = false; + CHECK(memory.docs[0].size == 5 && app.values[0] == 1 && app.events == 2); + /* The size limit of the data host fails as limit. */ + memory.limit = 6; + CHECK(pure_app_message(&app, 1, "doc", 1, edit_payload(buffer, 5, 0, "!!")) == PURE_LIMIT); + memory.limit = 100; + /* A reply read before the event's own edit keeps its content after commit. */ + CHECK(pure_app_message(&app, 2, "doc", 1, (PureSpan){(const unsigned char *)">> ", 3}) == PURE_OK); + CHECK(app.revision == 2 && replied(&app, "hello")); + CHECK(pure_app_message(&app, 0, "doc", -1, (PureSpan){0}) == PURE_OK && replied(&app, ">> hello")); + /* require: an edit that would exceed 8 bytes changes nothing */ + CHECK(pure_app_message(&app, 3, "doc", 2, edit_payload(buffer, 8, 0, "!")) == PURE_LIMIT); + CHECK(memory.docs[0].size == 8 && app.values[0] == 1); + CHECK(pure_app_message(&app, 3, "doc", 2, edit_payload(buffer, 0, 3, "")) == PURE_OK && app.revision == 3); + CHECK(app.values[0] == 2); + /* Another key is its own document. */ + CHECK(pure_app_message(&app, 1, "other", 0, edit_payload(buffer, 0, 0, "abc")) == PURE_OK && app.revision == 1); + pure_app_finish(&app); + CHECK(memory.opened == memory.closed); + for (size_t i = 0; i < memory.count; ++i) free(memory.docs[i].bytes); + + /* Verifier rules for typed operations. */ + static const O field_in_key[] = {{FIELD, 0, 0}, {ST, 0, 0}}; + static const H key_handler[] = {{9, 0, 2}}; + Spec bad = spec; + bad.o = field_in_key; bad.no = 2; bad.h = key_handler; bad.nh = 1; + CHECK(load(bad, &module_b) == PURE_INVALID && strstr(error, "message operation outside")); + static const O num_insert[] = {{C, 0, 0}, {C, 0, 0}, {C, 0, 1}, {REPL, 0, 0}}; + static const H edit_handler[] = {{3, 0, 4}}; + bad.o = num_insert; bad.no = 4; bad.h = edit_handler; + CHECK(load(bad, &module_b) == PURE_INVALID && strstr(error, "operand type")); + static const O bytes_state[] = {{FIELD, 2, 0}, {ST, 0, 0}}; + static const H edit_handler2[] = {{3, 0, 2}}; + bad.o = bytes_state; bad.no = 2; bad.h = edit_handler2; + CHECK(load(bad, &module_b) == PURE_INVALID && strstr(error, "operand type")); + static const O far_field[] = {{FIELD, 3, 0}, {REPLY, 0, 0}}; + bad.o = far_field; bad.h = edit_handler2; + CHECK(load(bad, &module_b) == PURE_INVALID && strstr(error, "unknown field")); + static const I unkeyed[] = {{"note", NULL, PURE_KIND_MESSAGE, false, NULL, 0}}; + static const O doc_read[] = {{DOC, 0, 0}, {REPLY, 0, 0}}; + static const H note_handler[] = {{1, 0, 2}}; + bad = (Spec){states, 1, unkeyed, 1, views, 0, note_handler, 1, doc_read, 2, collections, 1}; + CHECK(load(bad, &module_b) == PURE_INVALID && strstr(error, "document operation outside")); + static const F tail_first[] = {{"insert", 2}, {"start", 1}}; + static const I misplaced[] = {{"edit", NULL, PURE_KIND_MESSAGE, true, tail_first, 2}}; + bad = (Spec){states, 1, misplaced, 1, views, 0, NULL, 0, NULL, 0, collections, 1}; + CHECK(load(bad, &module_b) == PURE_INVALID && strstr(error, "message field")); + static const H even[] = {{2, 0, 0}}; + bad = (Spec){states, 1, inputs, 1, views, 0, even, 1, NULL, 0, collections, 1}; + CHECK(load(bad, &module_b) == PURE_INVALID && strstr(error, "handler event")); + static const V field_view[] = {{"v", 0, 1}}; + static const O field_only[] = {{FIELD, 0, 0}}; + bad = (Spec){states, 1, inputs, 2, field_view, 1, NULL, 0, field_only, 1, collections, 1}; + CHECK(load(bad, &module_b) == PURE_INVALID && strstr(error, "view with an effect")); + static const O branch_value[] = {{C, 0, 1}, {C, 0, 1}, {JZ, 3, 0}, {ST, 0, 0}}; + static const H frame_handler[] = {{0, 0, 4}}; + bad = (Spec){states, 1, inputs, 0, views, 0, frame_handler, 1, branch_value, 4, NULL, 0}; + CHECK(load(bad, &module_b) == PURE_INVALID && strstr(error, "branch with a non-empty stack")); +} + +/* Damaged message modules either fail to load or run messages safely. */ +static void message_mutations(void) { + static unsigned char valid[65536], bytes[65536]; + size_t size = build(valid, editor_spec); + uint32_t state = 0x9e3779b9u; + unsigned accepted = 0; + for (unsigned round = 0; round < 20000; ++round) { + memcpy(bytes, valid, size); + unsigned flips = 1 + next_random(&state) % 3; + for (unsigned f = 0; 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; + Memory memory = {.limit = 64}; + PureApp app; + pure_app_start(&app, &module_b, fake_data(&memory)); + unsigned char payload[32]; + for (unsigned e = 0; e < 12; ++e) { + for (size_t k = 0; k < sizeof(payload); ++k) payload[k] = (unsigned char)next_random(&state); + put32(payload, next_random(&state) % 12); + put32(payload + 4, next_random(&state) % 4); + PureSpan span = {payload, next_random(&state) % sizeof(payload)}; + uint32_t input = next_random(&state) % 5; + if (module_b.input[input].kind == PURE_KIND_MESSAGE) { + int64_t base = (int64_t)(next_random(&state) % 4) - 1; + if (pure_app_message(&app, input, "doc", base, span) == PURE_OK) { + size_t reply = 0; + CHECK(pure_app_reply(&app, count_bytes, &reply) == PURE_OK && reply <= 256); + } + } else pure_app_input(&app, input, e & 1 ? PURE_EDGE_UP : PURE_EDGE_DOWN); + pure_app_frame(&app); + for (uint32_t s = 0; s < module_b.states; ++s) CHECK(isfinite(app.values[s])); + } + pure_app_finish(&app); + CHECK(memory.opened == memory.closed); + for (size_t i = 0; i < memory.count; ++i) free(memory.docs[i].bytes); + } + printf("{\"message_module_mutations\":20000,\"accepted_after_damage\":%u}\n", accepted); +} + int main(void) { behaviour(); faults(); rejections(); mutations(); + messages(); + message_mutations(); 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\"}"); + puts("{\"module_tests\":\"verified-load-atomic-events-faults-signed-zero-if-else-replace-by-name-rejections-mutations-messages-documents-typed-verification\"}"); return 0; } -- cgit v1.2.3