diff options
Diffstat (limited to 'prototypes')
| -rw-r--r-- | prototypes/connections/Makefile | 8 | ||||
| -rw-r--r-- | prototypes/connections/edit-module.c | 184 | ||||
| -rw-r--r-- | prototypes/connections/module-store.c | 44 | ||||
| -rw-r--r-- | prototypes/connections/module-store.h | 7 | ||||
| -rw-r--r-- | prototypes/connections/module.c | 466 | ||||
| -rw-r--r-- | prototypes/connections/module.h | 74 | ||||
| -rw-r--r-- | prototypes/connections/pure-run.c | 2 | ||||
| -rw-r--r-- | prototypes/connections/test-module.c | 420 |
8 files changed, 1044 insertions, 161 deletions
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 <inttypes.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +/* 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 <math.h> #include <stdio.h> +#include <stdlib.h> #include <string.h> -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 <stdbool.h> #include <stddef.h> #include <stdint.h> -/* 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; } |