027's 4f-4: loops nested to any depth: the load counts a module's deepest nesting (nesting), a run keeping PURE_MODULE_NESTING (8) on its stack as before and a module nesting deeper running in the executor that calls, its loops in its app's room (PureApp.deep, grown to it), so run()'s hot path is as it was; the JIT compiles modules nesting 8 at most; a function's nesting counted without a cap (u32), its frame sized to it; unit test: 40 loops nested, run to their end (2^20 rounds) and stopped by the work budget (2^40), 8 still on the stack; counts: b42 against b41 with batches BFS -0.12%, without BFS +0.09%, the rest within 0.001%; the bank's queries (s41 and s42 in turns, six each) in_credit +1.04%, per_branch +0.60%, ranks +0.36%, the rest within 0.01% (their spread: the bank has no functions, so none runs the changed executor, and s42's in_credit is within s41's own earlier six); 008 and 027

5 files changed, 83 insertions, 20 deletions

diff --git a/core/module-jit.c b/core/module-jit.c
index 8208095..bd04361 100644
--- a/core/module-jit.c
+++ b/core/module-jit.c
@@ -5788,7 +5788,9 @@ struct PureJit *pure_jit_make(const PureModule *m) {
     const char *enabled = getenv("PURE_JIT");
     /* What it makes keeps its lists' and states' sets in a word each: a module of more states runs in the executor
      * alone (027's 4f-2). */
-    if ((enabled && !strcmp(enabled, "0")) || !m->height || !m->code_count || m->states > JIT_STATES) return NULL;
+    if ((enabled && !strcmp(enabled, "0")) || !m->height || !m->code_count || m->states > JIT_STATES ||
+        m->nesting > PURE_MODULE_NESTING) /* (its loops' tables hold PURE_MODULE_NESTING) */
+        return NULL;
     Made *made = NULL;
     size_t count = 0, room = 0;
     bool ok = true;
diff --git a/core/module-run.h b/core/module-run.h
index cff3f71..e79aa59 100644
--- a/core/module-run.h
+++ b/core/module-run.h
@@ -135,7 +135,7 @@ typedef struct {
     PureFault kind;    /* a fault's */
     PureResult status; /* what refused or stopped it */
     uint32_t fault_pc; /* the instruction that faulted or refused */
-    Loop *loops;       /* PURE_MODULE_NESTING of them, apart: a walk points into its loop */
+    Loop *loops;       /* the module's nesting of them (PURE_MODULE_NESTING on the stack, more the app's), apart: a walk points into its loop */
     /* The run of a tree compiled code read an item from last (pure_run_item):
      * the list as it was (its version), its positions and each field's cells. */
     struct { const PureList *list; uint64_t version; size_t start, count; const void *columns[16]; } run;
diff --git a/core/module.c b/core/module.c
index 3d38966..71a0a25 100644
--- a/core/module.c
+++ b/core/module.c
@@ -581,7 +581,6 @@ PURE_COLD static const char *verify_code(const PureModule *m, PureBlock block, i
         if (op->op == PURE_OP_LIST_REMOVE && walking(walked, walks, arg) && (int)arg != row)
             REFUSE("remove from a list an outer walk walks");
         if (nest && op->op == PURE_OP_REPLY) REFUSE("reply inside a loop");
-        if (nest == PURE_MODULE_NESTING && (op->op == PURE_OP_EACH || op->op == PURE_OP_LOOP)) REFUSE("loops nested deeper than 8");
         if (op->op == PURE_OP_BREAK && !nest) REFUSE("break outside a loop");
         if (op->op == PURE_OP_BREAK && height) REFUSE("break with values on the stack");
         if (op->op == PURE_OP_ITEM_SET && m->state_key[list_of(arg)] == item_field(arg) + 1)
@@ -1513,6 +1512,20 @@ PURE_COLD static void range_code(PureModule *m, PureBlock block, int input) {
     }
 }
 
+/* How deep the loops of m's verified code nest (its blocks apart, each loop's within its own); UINT32_MAX without room. */
+static uint32_t nesting_of(const PureModule *m) {
+    uint32_t *ends = malloc(((size_t)m->code_count + 1) * sizeof(*ends)), depth = 0, most = 0;
+    if (!ends) return UINT32_MAX;
+    for (uint32_t pc = 0; pc < m->code_count; ++pc) {
+        while (depth && pc >= ends[depth - 1]) --depth;
+        if (m->code[pc].op != PURE_OP_EACH && m->code[pc].op != PURE_OP_LOOP) continue;
+        ends[depth++] = pc + 1 + (m->code[pc].arg >> 16);
+        if (depth > most) most = depth;
+    }
+    free(ends);
+    return most;
+}
+
 /* A name and its place among those of one namespace, in order of name and then of place. */
 typedef struct { const char *name; size_t index; } Named;
 static int by_name(const void *a, const void *b) {
@@ -1527,13 +1540,14 @@ static void states_add(uint64_t *set, uint32_t state) { set[state >> 6] |= UINT6
 /* What a function's code names (027's 2c), read before it is verified (its arguments bounded here): the event's lists,
  * the registers and the values held by name each call has its own of, the lists not an event's it changes, its locals
  * and how deep its loops nest; the functions it calls (calls, a bit each). */
-PURE_COLD static void function_names(PureModule *m, uint32_t fn, uint64_t *calls) {
+PURE_COLD static bool function_names(PureModule *m, uint32_t fn, uint64_t *calls) {
     PureFunction *f = &m->function[fn];
     uint64_t *lists = m->function_lists + (size_t)fn * m->state_words, *registers = m->function_registers + (size_t)fn * m->state_words,
              *changes = m->function_changes + (size_t)fn * m->state_words;
-    uint32_t end = f->code.start + f->code.length, ends[PURE_MODULE_NESTING];
+    if (f->code.start > m->code_count || f->code.length > m->code_count - f->code.start) return true; /* refused as it is verified */
+    uint32_t end = f->code.start + f->code.length, *ends = malloc(((size_t)f->code.length + 1) * sizeof(*ends));
     unsigned depth = 0;
-    if (f->code.start > m->code_count || f->code.length > m->code_count - f->code.start) return; /* refused as it is verified */
+    if (!ends) return false;
     for (uint32_t pc = f->code.start; pc < end; ++pc) {
         const PureOp *op = &m->code[pc];
         uint32_t arg = op->arg, list = UINT32_MAX;
@@ -1551,9 +1565,9 @@ PURE_COLD static void function_names(PureModule *m, uint32_t fn, uint64_t *calls
         case PURE_OP_ITEM_GET: case PURE_OP_ITEM_SET: case PURE_OP_APPEND_IN: list = list_of(arg); break;
         case PURE_OP_EACH: case PURE_OP_FOLD: case PURE_OP_LOOP: case PURE_OP_LOCAL_LOAD: case PURE_OP_LOCAL_STORE:
             if (op->op == PURE_OP_EACH || op->op == PURE_OP_FOLD) list = arg >> 8 & 0xFF;
-            if ((op->op == PURE_OP_EACH || op->op == PURE_OP_LOOP) && depth < PURE_MODULE_NESTING) {
+            if (op->op == PURE_OP_EACH || op->op == PURE_OP_LOOP) { /* (a loop an instruction at least: depth within ends) */
                 ends[depth++] = pc + 1 + (arg >> 16);
-                if (depth > f->nesting) f->nesting = (uint8_t)depth;
+                if (depth > f->nesting) f->nesting = depth;
             }
             if (op->op == PURE_OP_EACH || op->op == PURE_OP_FOLD) break;
             if ((arg & 0xFF) < PURE_MODULE_LOCALS && (arg & 0xFF) >= f->locals) f->locals = (uint8_t)((arg & 0xFF) + 1);
@@ -1565,6 +1579,8 @@ PURE_COLD static void function_names(PureModule *m, uint32_t fn, uint64_t *calls
         }
         if (event_list_state(m, list)) states_add(bound_list(m, list) ? registers : lists, list);
     }
+    free(ends);
+    return true;
 }
 
 PURE_COLD PureResult pure_module_read(const char *path, PureModule *out, char *error, size_t error_size) {
@@ -2082,7 +2098,11 @@ PURE_COLD PureResult pure_module_load(const void *bytes, size_t size, PureModule
     }
     /* What each function names, and the lists it changes with those the functions it calls change (until none adds). */
     uint64_t calls[PURE_MODULE_FUNCTIONS] = {0};
-    for (uint32_t i = 0; i < out->functions; ++i) function_names(out, i, &calls[i]);
+    for (uint32_t i = 0; i < out->functions; ++i)
+        if (!function_names(out, i, &calls[i])) {
+            result = PURE_ALLOCATION;
+            REFUSE("out of memory", i);
+        }
     for (bool more = out->functions > 0; more;) {
         more = false;
         for (uint32_t i = 0; i < out->functions; ++i)
@@ -2233,7 +2253,13 @@ PURE_COLD PureResult pure_module_load(const void *bytes, size_t size, PureModule
     for (uint32_t i = 0; i < out->views; ++i)
         for (uint32_t pc = out->view_code[i].start; pc < out->view_code[i].start + out->view_code[i].length; ++pc)
             if (out->code[pc].op == PURE_OP_KEPT_GET) out->view_body[i] = true;
-    out->runner = out->calls ? 2 : out->batches ? 1 : 0;
+    /* How deep its loops nest (027's 4f-4): past what a run keeps on its stack, its blocks run in the executor that calls,
+     * its loops in its app's room. */
+    if ((out->nesting = nesting_of(out)) == UINT32_MAX) {
+        result = PURE_ALLOCATION;
+        REFUSE("out of memory", 0);
+    }
+    out->runner = out->calls || out->nesting > PURE_MODULE_NESTING ? 2 : out->batches ? 1 : 0;
     out->jit = pure_jit_make(out); /* none: the executor runs it all */
     return PURE_OK;
 refused:
@@ -4829,10 +4855,21 @@ static __attribute__((noinline, cold)) void unwind_calls(Frame *frame, Call *top
 /* The executor's run of a block of a module with functions (027's 2c): run_batches' steps and batches, and calls: a
  * CALL opens its function's frame and its block runs on in this loop, a RETURN closes it. Its own copy of the steps,
  * as run_batches is. */
+/* Room for a run's loops nested deeper than PURE_MODULE_NESTING (027's 4f-4): the app's, grown to nesting; NULL without. */
+static __attribute__((cold, noinline)) Loop *deep_loops(PureApp *app, uint32_t nesting) {
+    if (app->deep_room < nesting) {
+        Loop *grown = realloc(app->deep, nesting * sizeof(*grown));
+        if (!grown) return NULL;
+        app->deep = grown, app->deep_room = nesting;
+    }
+    return app->deep;
+}
+
 static __attribute__((noinline, aligned(64))) PureResult run_calls(const PureModule *m, PureValue *values, PureBlock block, Event *ev,
                                                       Slot *result) {
     Slot stack[PURE_MODULE_STACK];
-    Loop loops[PURE_MODULE_NESTING];
+    Loop few[PURE_MODULE_NESTING], *loops = m->nesting > PURE_MODULE_NESTING ? deep_loops(ev->app, m->nesting) : few;
+    if (!loops) return PURE_ALLOCATION;
     Frame frame;
     open_frame(&frame, m, values, block, ev, stack, loops);
     Call *top = NULL;
@@ -5161,6 +5198,7 @@ void pure_app_stop(PureApp *app) {
     pure_draft_close(app->stored_values);
     free(app->carried);
     free(app->by_input);
+    free(app->deep);
     pure_draft_close(app->stored_links);
     pure_draft_close(app->stored_seq);
     pure_save_close_start(app);
diff --git a/core/module.h b/core/module.h
index 26259fe..8a84ddb 100644
--- a/core/module.h
+++ b/core/module.h
@@ -194,6 +194,8 @@ enum { PURE_FOLD_SLICED = 0x80, PURE_EACH_SLICED = 1 };
  * Loops (LOOP and EACH) nest 8 deep. Within a walk, code that a loop runs
  * may change the items of any list but not add to or remove from a list an
  * outer walk walks; the innermost walk may remove from its own. */
+/* PURE_MODULE_NESTING: the loops nested that a run keeps on its stack; a module nesting deeper (027's 4f-4) runs in the
+ * executor that calls, its loops in its app's room (PureApp.deep). */
 enum { PURE_LOOP_INTEGER = 256, PURE_MODULE_NESTING = 8 };
 /* What a unit (an event, or a view's evaluation) may run when its app sets
  * no work budget (pure_app_work), and what an event may hold for what it
@@ -331,7 +333,8 @@ typedef struct {
     uint16_t first;
     uint8_t params, results;
     uint32_t held;
-    uint8_t height, locals, nesting;
+    uint8_t height, locals;
+    uint32_t nesting;
 } PureFunction;
 typedef struct { char name[PURE_MODULE_NAME]; uint8_t type; uint16_t rows; uint32_t offset; } PureField;
 typedef struct {
@@ -441,6 +444,7 @@ typedef struct {
     uint8_t *signature_type;
     uint16_t *signature_record;
     bool calls; /* it has functions: its blocks run in the executor that calls (module.c) */
+    uint32_t nesting; /* its loops' deepest nesting (set at load) */
 } PureModule;
 
 /* Whether a state of m is transient (PURE_STATE_TRANSIENT). */
@@ -623,6 +627,8 @@ typedef struct {
     struct { unsigned char **blocks; size_t *sizes; unsigned count, at; size_t used; } calls;
     struct PureSpare { PureList **lists; unsigned count, capacity; } *spare;
     PureValue *pending; /* the values an event works on until it ends */
+    void *deep; /* a run's loops, a module nesting past PURE_MODULE_NESTING's (its nesting of them) */
+    uint32_t deep_room;
     PureVersion *marked_texts; /* where the event running began: each text's version, each stored list's journal, */
     size_t *marked_lists;
     /* Each input's: its last number sent and as saved, and where the event running began; one block (by_input) for
diff --git a/core/test-module.c b/core/test-module.c
index 5bd1c8b..cb8e228 100644
--- a/core/test-module.c
+++ b/core/test-module.c
@@ -7100,14 +7100,17 @@ static void loops(void) {
         deep[3 * d + 1] = (O){C, 0, 1};
         deep[3 * d + 2] = (O){LOOP, BODY(0, 26 - 3 * d - 3), 0};
     }
-    O deeper[9 * 3 + 2];
-    for (unsigned d = 0; d < 9; ++d) {
+    enum { DEEPER = 40 }; /* nested past what a run keeps on its stack (027's 4f-4): its app's room */
+    O deeper[DEEPER * 3 + 4];
+    for (unsigned d = 0; d < DEEPER; ++d) {
         deeper[3 * d] = (O){C, 0, 0};
-        deeper[3 * d + 1] = (O){C, 0, 1};
-        deeper[3 * d + 2] = (O){LOOP, BODY(0, 29 - 3 * d - 3), 0};
+        deeper[3 * d + 1] = (O){C, 0, 2}; /* each twice: the innermost 2^40 times past any budget, so its first fault */
+        deeper[3 * d + 2] = (O){LOOP, BODY(0, DEEPER * 3 + 4 - 3 * d - 3), 0};
     }
-    deeper[27] = (O){C, 0, 1};
-    deeper[28] = (O){ST, S_, 0};
+    deeper[3 * DEEPER] = (O){PURE_OP_LOAD, S_, 0};
+    deeper[3 * DEEPER + 1] = (O){C, 0, 1};
+    deeper[3 * DEEPER + 2] = (O){PURE_OP_ADD, 0, 0};
+    deeper[3 * DEEPER + 3] = (O){ST, S_, 0};
     const struct { const O *code; size_t count; const char *why; } refused[] = {
         {outside, LEN(outside), "break outside a loop"},
         {valued, LEN(valued), "break with values on the stack"},
@@ -7116,7 +7119,6 @@ static void loops(void) {
         {flagged, LEN(flagged), "no such state"},
         {two_ways, LEN(two_ways), "local used as two things"},
         {into_outer, LEN(into_outer), "insert into the list walked"},
-        {deeper, LEN(deeper), "loops nested deeper than 8"},
     };
     for (size_t i = 0; i < LEN(refused); ++i) {
         H one[] = {{1, 0, (uint32_t)refused[i].count}};
@@ -7136,7 +7138,22 @@ static void loops(void) {
     nested.no = LEN(deep);
     nested.h = eight;
     nested.nh = 1;
-    CHECK(load(nested, &module_b) == PURE_OK); /* eight deep is allowed */
+    CHECK(load(nested, &module_b) == PURE_OK && module_b.nesting == 8 && module_b.runner != 2); /* on the stack */
+    H forty[] = {{1, 0, LEN(deeper)}};
+    nested.o = deeper, nested.no = LEN(deeper), nested.h = forty;
+    CHECK(load(nested, &module_b) == PURE_OK && module_b.nesting == DEEPER && module_b.runner == 2 && !module_b.jit);
+    PureApp deep_app;
+    CHECK(pure_app_start(&deep_app, &module_b, (PureData){0}) == PURE_OK);
+    pure_app_work(&deep_app, 100000); /* (2^40 rounds would never end) */
+    CHECK(press(&deep_app, 0) == PURE_LIMIT && deep_app.fault == PURE_FAULT_WORK && deep_app.values[S_].num == 0);
+    pure_app_work(&deep_app, 0);
+    pure_app_stop(&deep_app);
+    for (unsigned d = 0; d < DEEPER; ++d) deeper[3 * d + 1] = (O){C, 0, d % 2 ? 1 : 2}; /* 2^20 rounds */
+    CHECK(load(nested, &module_b) == PURE_OK && pure_app_start(&deep_app, &module_b, (PureData){0}) == PURE_OK);
+    pure_app_work(&deep_app, UINT64_C(1) << 40);
+    CHECK(press(&deep_app, 0) == PURE_OK && deep_app.values[S_].num == 1 << 20 && press(&deep_app, 0) == PURE_OK &&
+          deep_app.values[S_].num == 2 << 20);
+    pure_app_stop(&deep_app);
     pure_module_release(&module_b);
     pure_module_release(&module_a);
 #undef BODY