Read a tree's items in compiled code from a run the frame keeps, start a run at the finger's leaf, and move indices only for a list an index refers to (021)

- The frame keeps the run compiled code read a tree's item from last (the
  list as it was: its version); an item it holds is read from its column,
  else pure_run_item takes the item's run and steps.
- pure_list_run starts at the leaf the finger keeps when it holds the
  position (a slice found by key just before): no second descent; the
  run after it is found from the root (PureRun.pathless).
- LIST_APPEND and LIST_REMOVE move index states only for a list one
  refers to.
- A search (core only): 89 ms compiled (answers the executor's).

5 files changed, 88 insertions, 8 deletions

diff --git a/core/module-jit.c b/core/module-jit.c
index a6ab7f1..8e50eb0 100644
--- a/core/module-jit.c
+++ b/core/module-jit.c
@@ -557,13 +557,38 @@ static void compile_op(Block *k, uint32_t pc) {
         bind(e, done);
         return;
     }
-    case PURE_OP_ITEM_GET: { /* a FLAT list's cell by its column */
+    case PURE_OP_ITEM_GET: { /* a FLAT list's cell by its column, a tree's from the run kept */
         if (op->plan & PLAN_TEXT) break;
-        int slow = new_label(e), done = new_label(e);
+        int slow = new_label(e), done = new_label(e), flat = new_label(e), refill = new_label(e);
+        size_t field = item_field(arg) * sizeof(void *);
         load64(e, X10, X24, list_of(arg) * sizeof(PureList *));
         load8(e, X12, X10, pure_list_layout[LIST_FORM_AT]);
         cmp_w_imm(e, X12, 1); /* FLAT */
-        b_cond(e, NE, slow);
+        b_cond(e, EQ, flat);
+        cbnz_w(e, X12, slow); /* DENSE */
+        load_d(e, D0, X20, AT(height - 1));
+        fp2(e, FCVTZU_X, X13, D0);
+        load64(e, X11, X19, offsetof(Frame, run.list));
+        cmp_reg(e, X11, X10);
+        b_cond(e, NE, refill);
+        load64(e, X11, X19, offsetof(Frame, run.version));
+        load64(e, X12, X10, pure_list_layout[LIST_VERSION_AT]);
+        cmp_reg(e, X11, X12);
+        b_cond(e, NE, refill);
+        load64(e, X11, X19, offsetof(Frame, run.start));
+        sub_reg(e, X14, X13, X11);
+        load64(e, X11, X19, offsetof(Frame, run.count));
+        cmp_reg(e, X14, X11);
+        b_cond(e, HS, refill);
+        load64(e, X15, X19, offsetof(Frame, run.columns) + field);
+        load64_index(e, X9, X15, X14);
+        store64(e, X9, X20, AT(height - 1));
+        b(e, done);
+        bind(e, refill);
+        call_step(k, (uintptr_t)pure_run_item, pc, height);
+        cbnz_w(e, X0, k->exit);
+        b(e, done);
+        bind(e, flat);
         load_d(e, D0, X20, AT(height - 1));
         fp2(e, FCVTZU_X, X13, D0);
         load64(e, X12, X10, pure_list_layout[LIST_COUNT_AT]);
diff --git a/core/module-list.c b/core/module-list.c
index 7bf05e1..b3a9ed3 100644
--- a/core/module-list.c
+++ b/core/module-list.c
@@ -1137,7 +1137,8 @@ unsigned pure_list_form(const PureList *list) { return list->form; }
 const size_t pure_list_layout[] = {
     [LIST_COUNT_AT] = offsetof(PureList, count), [LIST_MEMBERS_AT] = offsetof(PureList, members),
     [LIST_MEMBER_CAPACITY_AT] = offsetof(PureList, member_capacity), [LIST_BITMAP_AT] = offsetof(PureList, bitmap),
-    [LIST_FORM_AT] = offsetof(PureList, form), [LIST_COLUMNS_AT] = offsetof(PureList, columns)};
+    [LIST_FORM_AT] = offsetof(PureList, form), [LIST_COLUMNS_AT] = offsetof(PureList, columns),
+    [LIST_VERSION_AT] = offsetof(PureList, version)};
 
 bool pure_list_lookup(const PureList *list, unsigned key_field, PureCell key, unsigned field, PureCell *cell) {
     bool found;
@@ -1757,6 +1758,7 @@ static void open_array_run(const PureList *list, size_t at, PureRun *run) {
     run->start = at;
     run->count = list->form == DENSE ? 1 : (unsigned)(list->count - at < PURE_LIST_RUN ? list->count - at : PURE_LIST_RUN);
     run->depth = 0;
+    run->pathless = false;
     for (unsigned f = 0; f < l->fields; ++f)
         if (pure_cell_text(l->kinds[f])) run->column[f].texts = (const PureSpan *)list->columns[f] + row;
         else if (l->kinds[f] == PURE_CELL_INTEGER) run->column[f].integers = (const int64_t *)list->columns[f] + row;
@@ -1772,6 +1774,16 @@ bool pure_list_run(const PureList *list, size_t at, PureRun *run) {
             return true;
         }
     }
+    size_t within;
+    const Node *kept = fingered(list, at, &within); /* a slice's first item, found by key just before */
+    if (kept) {
+        run->path[0] = kept;
+        run->depth = 0;
+        run->pathless = true; /* the run after it found from the root */
+        run->start = at - within;
+        open_run(&list->layout, kept, run);
+        return true;
+    }
     const Node *node = list->root;
     size_t start = 0;
     unsigned depth = 0;
@@ -1785,6 +1797,7 @@ bool pure_list_run(const PureList *list, size_t at, PureRun *run) {
     run->path[depth] = node;
     run->depth = depth;
     run->start = start;
+    run->pathless = false;
     open_run(&list->layout, node, run);
     return true;
 }
@@ -1798,6 +1811,23 @@ bool pure_list_next(const PureList *list, PureRun *run) {
         open_array_run(list, run->start + run->count, run);
         return true;
     }
+    if (run->pathless) { /* the next from the root, with its path */
+        size_t at = run->start + run->count;
+        if (at >= list->count) return false;
+        const Node *node = list->root;
+        size_t start = 0;
+        unsigned depth = 0;
+        while (!node->leaf) {
+            unsigned i = child_at(node, at - start);
+            start += guide(node)->before[i];
+            run->path[depth] = node;
+            run->taken[depth++] = (uint8_t)i;
+            node = child(node, i);
+        }
+        run->path[depth] = node, run->depth = depth, run->start = start, run->pathless = false;
+        open_run(&list->layout, node, run);
+        return true;
+    }
     size_t start = run->start + run->count;
     unsigned depth = run->depth;
     while (depth && run->taken[depth - 1] + 1u >= ((const Node *)run->path[depth - 1])->count) --depth;
diff --git a/core/module-list.h b/core/module-list.h
index 0addcf0..6251786 100644
--- a/core/module-list.h
+++ b/core/module-list.h
@@ -37,10 +37,13 @@ typedef struct {
     size_t start;
     unsigned count;
     union { const double *numbers; const int64_t *integers; const PureSpan *texts; } column[16];
-    /* Where the run is in the list's tree, for the next one. */
+    /* Where the run is in the list's tree, for the next one (path[depth]
+     * its leaf); pathless: its leaf alone is known (the next is found from
+     * the root). */
     const void *path[16];
     uint8_t taken[16];
     unsigned depth;
+    bool pathless;
 } PureRun;
 
 /* A list holds up to PURE_LIST_ITEMS items, a run up to PURE_LIST_RUN. */
diff --git a/core/module-run.h b/core/module-run.h
index 453c342..8844685 100644
--- a/core/module-run.h
+++ b/core/module-run.h
@@ -64,6 +64,9 @@ typedef struct {
     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 */
+    /* 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;
 } Frame;
 
 /* How a step went: on to the next instruction; a fault (kind at fault_pc);
@@ -87,11 +90,14 @@ int pure_run_each(Frame *, uint32_t pc);
 int pure_run_loop(Frame *, uint32_t pc);
 void pure_run_break(Frame *);
 int pure_run_iterate(Frame *);
+/* ITEM_GET at pc whose list is a tree its kept run does not hold: the
+ * item's run kept, then the step. */
+int pure_run_item(Frame *, uint32_t pc);
 
 /* Where a list keeps what compiled code reads of it (module-list.c owns the
  * layout and says where): its item count, its key set (the words, how many,
  * whether they are bits), its form (pure_list_form) and its arrays. */
-enum { LIST_COUNT_AT, LIST_MEMBERS_AT, LIST_MEMBER_CAPACITY_AT, LIST_BITMAP_AT, LIST_FORM_AT, LIST_COLUMNS_AT };
+enum { LIST_COUNT_AT, LIST_MEMBERS_AT, LIST_MEMBER_CAPACITY_AT, LIST_BITMAP_AT, LIST_FORM_AT, LIST_COLUMNS_AT, LIST_VERSION_AT };
 extern const size_t pure_list_layout[];
 
 /* A module's code compiled (AArch64 Linux; elsewhere, or with PURE_JIT=0 in
diff --git a/core/module.c b/core/module.c
index ff6f131..c486d45 100644
--- a/core/module.c
+++ b/core/module.c
@@ -2788,7 +2788,7 @@ static inline __attribute__((always_inline)) int step(Frame *frame, const PureOp
         if (status == PURE_INVALID) status = pure_list_insert(list, at, cells, undo_for(app, arg));
         arena->used = mark;
         if (status != PURE_OK) REFUSED;
-        move_indices(m, values, arg, pure_list_count(list), at, true);
+        if (m->state_indexed[arg]) move_indices(m, values, arg, pure_list_count(list), at, true);
         if (!grows(app, before, list_held(app, list))) { kind = PURE_FAULT_MEMORY; FAILED; }
         NEXT;
     }
@@ -2798,7 +2798,7 @@ static inline __attribute__((always_inline)) int step(Frame *frame, const PureOp
         if ((status = pure_list_remove(app->lists[arg], at, undo_for(app, arg))) != PURE_OK) REFUSED;
         /* the item goes, its cells kept to undo and its record to save */
         if (!grows(app, before, list_held(app, app->lists[arg]))) { kind = PURE_FAULT_MEMORY; FAILED; }
-        move_indices(m, values, arg, pure_list_count(app->lists[arg]), at, false);
+        if (m->state_indexed[arg]) move_indices(m, values, arg, pure_list_count(app->lists[arg]), at, false);
         if (ev->walk && ev->walk->list == arg) { /* the walk goes on with the item after */
             if (at < ev->walk->at) --ev->walk->at;
             else if (at == ev->walk->at) ev->walk->removed = true;
@@ -3049,6 +3049,22 @@ int pure_run_loop(Frame *frame, uint32_t pc) {
 
 void pure_run_break(Frame *frame) { (void)leave_loop(frame); }
 
+int pure_run_item(Frame *frame, uint32_t pc) {
+    const PureOp *op = &frame->m->code[pc];
+    const PureList *list = frame->app->lists[list_of(op->arg)];
+    size_t at = (size_t)frame->stack[frame->sp - 1].num;
+    PureRun run;
+    if (at < pure_list_count(list) && !pure_list_form(list) && pure_list_run(list, at, &run)) {
+        uint64_t id;
+        frame->run.list = list;
+        pure_list_stamp(list, &id, &frame->run.version);
+        frame->run.start = run.start, frame->run.count = run.count;
+        for (unsigned f = 0; f < 16; ++f) frame->run.columns[f] = run.column[f].numbers;
+    }
+    uint32_t next;
+    return step(frame, op, pc, &next);
+}
+
 int pure_run_iterate(Frame *frame) {
     uint32_t next = UINT32_MAX;
     int how = iterate(frame, &next);