Keep a walk's range only when its body moves no state its bound reads

A walk whose where bounds a keyed list's key finds the bound once, when
the walk begins, if its body writes nothing the bound reads. The body's
writes counted only states stored and lists changed, not what those
changes move with them: an insert or remove moves the indices into the
list, a text's change the cursors in it. A walk bounded by an index
into a list its body inserts into saw the bound it began with: of five
rows it took one (review 004, F1). Those states now count as written,
and a bound that moves an index (whose list is whichever the index's
is) is kept only when the body changes no list.

build/module-probe runs a module twice from the same keys, as it loads
and with every range let go, and says which state first differs.
check.py's module_ranges runs the review's case (all rows twice: done
10, at 10) and a walk whose bound its body cannot move, still ranged.
The probe finds the difference in the runtime before this.

4 files changed, 188 insertions, 4 deletions

diff --git a/Makefile b/Makefile
index e5d8451..d14510e 100644
--- a/Makefile
+++ b/Makefile
@@ -85,6 +85,10 @@ $(BUILD)/test-message-json: serve/test-message-json.c serve/message-json.c $(BUI
 	$(CC) $(CPPFLAGS) $(CFLAGS) $(INCLUDES) -Iserve serve/test-message-json.c serve/message-json.c $(BUILD)/libpure.a \
 		$(LDFLAGS) -lm $(LDLIBS) -o $@
 
+# A module run ranged and not from the same inputs, compared (tests/check.py).
+$(BUILD)/module-probe: tests/module-probe.c $(BUILD)/libpure.a $(HEADERS)
+	$(CC) $(CPPFLAGS) $(CFLAGS) $(INCLUDES) tests/module-probe.c $(BUILD)/libpure.a $(LDFLAGS) -lm $(LDLIBS) -o $@
+
 $(BUILD)/test-log: store/test-log.c store/store-log.c $(HEADERS)
 	@mkdir -p $(BUILD)
 	$(CC) $(CPPFLAGS) $(CFLAGS) $(INCLUDES) -DPURE_STORE_TEST store/test-log.c store/store-log.c $(LDFLAGS) $(LDLIBS) -o $@
@@ -96,7 +100,8 @@ $(BUILD)/test-tree-store: store/test-tree-store.c $(STORE) $(HEADERS)
 # The HTTP host's checks build their apps with aup (the sibling checkout) and
 # compare documents with the earlier document server.
 AUP ?= ../aup
-check: all $(BUILD)/test-module $(BUILD)/test-tree-store $(BUILD)/test-log $(BUILD)/test-link $(BUILD)/test-message-json
+check: all $(BUILD)/test-module $(BUILD)/test-tree-store $(BUILD)/test-log $(BUILD)/test-link $(BUILD)/test-message-json \
+		$(BUILD)/module-probe
 	$(BUILD)/test-tree-store
 	$(BUILD)/test-log
 	$(BUILD)/test-module
diff --git a/core/module.c b/core/module.c
index 8ac3b48..574d6af 100644
--- a/core/module.c
+++ b/core/module.c
@@ -690,8 +690,10 @@ PURE_COLD static uint8_t keep_range(PureModule *m, const PureRange *range) {
 }
 
 /* Whether a walk's bounds read nothing its block writes: the states and
- * locals it stores, the lists it changes. A bound is found once, before
- * the walk; the walk's where reads it anew for every item. */
+ * locals it stores, the lists it changes, and what those changes move with
+ * them (an insert or remove moves the indices into the list, a text's
+ * change the cursors in it). A bound is found once, before the walk; the
+ * walk's where reads it anew for every item. */
 PURE_COLD static bool bounds_fixed(const PureModule *m, const PureRange *range, PureBlock body) {
     uint64_t states = 0, locals = 0, lists = 0;
     for (uint32_t pc = body.start; pc < body.start + body.length; ++pc) {
@@ -707,15 +709,24 @@ PURE_COLD static bool bounds_fixed(const PureModule *m, const PureRange *range,
         default: break;
         }
     }
+    for (uint32_t s = 0; s < m->states; ++s) {
+        uint32_t ref = m->state_ref[s];
+        if ((m->state_type[s] == PURE_STATE_INDEX && lists >> (ref & 63) & 1) ||
+            (m->state_type[s] == PURE_STATE_CURSOR && states >> (ref & 63) & 1))
+            states |= (uint64_t)1 << (s & 63);
+    }
     for (unsigned side = 0; side < 2; ++side) {
         PureBlock bound = side ? range->upper : range->lower;
         if (!(side ? range->upper_relation : range->lower_relation)) continue;
         for (uint32_t pc = bound.start; pc < bound.start + bound.length; ++pc) {
             const PureOp *op = &m->code[pc];
             int list = list_read(op);
-            if ((op->op == PURE_OP_LOAD || op->op == PURE_OP_INDEX_LOAD) && states >> (op->arg & 63) & 1) return false;
+            if ((op->op == PURE_OP_LOAD || op->op == PURE_OP_INDEX_LOAD || op->op == PURE_OP_CUR_LOAD) &&
+                states >> (op->arg & 63) & 1)
+                return false;
             if (op->op == PURE_OP_LOCAL_LOAD && locals >> (op->arg & 63) & 1) return false;
             if (list >= 0 && lists >> (list & 63) & 1) return false;
+            if (op->op == PURE_OP_INDEX_MOVE && lists) return false; /* the count of its index's list, whichever */
         }
     }
     return true;
diff --git a/tests/check.py b/tests/check.py
index 84cf0c7..cbcf6cb 100644
--- a/tests/check.py
+++ b/tests/check.py
@@ -946,6 +946,60 @@ print(json.dumps(check.server_links_udp(Path({str(aup)!r}), Path({str(pure)!r}),
     return json.loads(done.stdout.strip().splitlines()[-1])
 
 
+RANGES_SOURCE = """record Item { id = 0 }
+state rows: list of Item by id
+state other: list of Item by id
+state at: index of other
+state limit = 2
+state done = 0
+state below = 0
+input seed = key KeyS
+input go = key KeyG
+input count = key KeyC
+on seed.down {
+  rows.add(Item { id: 0 })
+  rows.add(Item { id: 1 })
+  rows.add(Item { id: 2 })
+  rows.add(Item { id: 3 })
+  rows.add(Item { id: 4 })
+  other.add(Item { id: 100 })
+}
+on go.down {
+  for r in rows where r.id <= at.position {
+    other.add(Item { id: -r.id - 1 - done })
+    done = done + 1
+  }
+}
+on count.down {
+  for r in rows where r.id <= limit {
+    below = below + 1
+  }
+}
+view total = done
+view counted = below
+"""
+
+
+def module_ranges(aup, pure, work):
+    """A walk whose where reads an index into a list its body inserts into:
+    each insert before the index's item moves the index on, so the walk's
+    bound moves with it and all five rows pass, twice (review 004, F1). The
+    module runs ranged and not from the same keys (build/module-probe), and
+    the two must end the same, state for state; a walk whose bound its body
+    cannot move stays ranged."""
+    source, module = work / 'ranges.aup', work / 'ranges.pmod'
+    source.write_text(RANGES_SOURCE)
+    compile_module(aup, source, module)
+    done = subprocess.run([str(pure / 'build/module-probe'), str(module), 'seed', 'go', 'count', 'go'],
+                          capture_output=True, text=True, timeout=60)
+    assert done.returncode == 0, done.stderr
+    row = json.loads(done.stdout)
+    states = row['states']
+    assert states['done'] == 10 and states['at'] == 10 and states['below'] == 3, row
+    assert row['ranged'] >= 1, row
+    return row
+
+
 def server_links_refused(aup, pure, work):
     """A link to an input the receiver's app does not have: the receiver
     says so (REFUSED), and the sender says it once on stderr, as a wire says
@@ -2471,6 +2525,7 @@ def main():
     report = {}
     with tempfile.TemporaryDirectory(prefix='pure-check-') as directory:
         work = Path(directory)
+        report['module_ranges'] = module_ranges(aup, pure, work)
         report['server_parity_requests'] = sum(server_parity(aup, pure, work, range(args.seeds), threads=threads)
                                                for threads in (1, 3))
         report['server_pipelined_answers'] = server_pipelining(aup, pure, work)
diff --git a/tests/module-probe.c b/tests/module-probe.c
new file mode 100644
index 0000000..72d06b2
--- /dev/null
+++ b/tests/module-probe.c
@@ -0,0 +1,113 @@
+/* A module run twice from the same inputs: once as it loads, once with none
+ * of its walks and folds ranged (every op's range let go). A range may only
+ * skip items the walk's or fold's test would refuse, so the two must end
+ * the same: state for state, item for item, byte for byte. For
+ * tests/check.py.
+ *
+ *   module-probe FILE.pmod INPUT...
+ *
+ * Each INPUT is a key input's name, pressed. The module must not read the
+ * clock (now): the two runs are not at the same time. Prints a line of
+ * JSON: the inputs applied, the ops ranged, and each number state's value;
+ * exits 1 at the first difference, naming the state. */
+#include "module.h"
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+typedef struct { unsigned char *bytes; size_t size; } Bytes;
+
+static bool keep(void *context, PureSpan span) {
+    Bytes *b = context;
+    unsigned char *grown = realloc(b->bytes, b->size + span.size + 1);
+    if (!grown) return false;
+    memcpy(grown + b->size, span.data, span.size);
+    b->bytes = grown, b->size += span.size;
+    return true;
+}
+
+static bool same_text(const PureDraft *a, const PureDraft *b) {
+    size_t size = pure_draft_size(a);
+    Bytes x = {0}, y = {0};
+    bool same = size == pure_draft_size(b) && pure_draft_read(a, 0, size, keep, &x) == PURE_OK &&
+                pure_draft_read(b, 0, size, keep, &y) == PURE_OK && x.size == y.size &&
+                (!x.size || !memcmp(x.bytes, y.bytes, x.size));
+    free(x.bytes), free(y.bytes);
+    return same;
+}
+
+static bool same_cell(PureCell a, PureCell b) {
+    return !memcmp(&a.num, &b.num, sizeof(a.num)) && a.size == b.size && (!a.size || !memcmp(a.text, b.text, a.size));
+}
+
+/* The first state the two apps hold differently, or -1. */
+static int differs(const PureModule *m, const PureApp *a, const PureApp *b) {
+    for (uint32_t s = 0; s < m->states; ++s) {
+        bool same = true;
+        switch (m->state_type[s]) {
+        case PURE_STATE_TEXT: same = same_text(a->texts[s], b->texts[s]); break;
+        case PURE_STATE_LIST: {
+            size_t count = pure_list_count(a->lists[s]);
+            unsigned fields = m->record[m->state_ref[s]].count;
+            same = count == pure_list_count(b->lists[s]);
+            for (size_t at = 0; same && at < count; ++at)
+                for (unsigned f = 0; same && f < fields; ++f)
+                    same = same_cell(pure_list_get(a->lists[s], at, f), pure_list_get(b->lists[s], at, f));
+            break;
+        }
+        default: same = !memcmp(&a->values[s], &b->values[s], sizeof(double)); break;
+        }
+        if (!same) return (int)s;
+    }
+    return -1;
+}
+
+int main(int argc, char **argv) {
+    PureModule modules[2] = {0};
+    PureApp apps[2] = {0};
+    char error[256];
+    unsigned ranged = 0;
+    if (argc < 2) {
+        fputs("module-probe FILE.pmod INPUT...\n", stderr);
+        return 2;
+    }
+    for (int k = 0; k < 2; ++k) {
+        if (pure_module_read(argv[1], &modules[k], error, sizeof(error)) != PURE_OK) {
+            fprintf(stderr, "module-probe: %s\n", error);
+            return 2;
+        }
+        for (uint32_t pc = 0; pc < modules[k].code_count; ++pc) {
+            if (!k) ranged += modules[k].code[pc].range != 0;
+            else modules[k].code[pc].range = 0;
+        }
+        if (pure_app_start(&apps[k], &modules[k], (PureData){0}) != PURE_OK) {
+            fprintf(stderr, "module-probe: the app does not start\n");
+            return 2;
+        }
+    }
+    for (int i = 2; i < argc; ++i) {
+        int input = pure_module_input(&modules[0], argv[i]);
+        if (input < 0) {
+            fprintf(stderr, "module-probe: no input %s\n", argv[i]);
+            return 2;
+        }
+        PureResult results[2];
+        for (int k = 0; k < 2; ++k) results[k] = pure_app_input(&apps[k], (uint32_t)input, PURE_EDGE_DOWN);
+        int state = differs(&modules[0], &apps[0], &apps[1]);
+        if (results[0] != results[1] || state >= 0) {
+            fprintf(stderr, "module-probe: after %s (input %d): %s differs ranged and not (results %d, %d)\n", argv[i],
+                    i - 1, state >= 0 ? modules[0].state_names[state] : "the result", results[0], results[1]);
+            return 1;
+        }
+    }
+    printf("{\"inputs\":%d,\"ranged\":%u,\"states\":{", argc - 2, ranged);
+    for (uint32_t s = 0, shown = 0; s < modules[0].states; ++s)
+        if (modules[0].state_type[s] == PURE_STATE_NUM || modules[0].state_type[s] == PURE_STATE_INDEX)
+            printf("%s\"%s\":%.17g", shown++ ? "," : "", modules[0].state_names[s], apps[0].values[s]);
+    printf("}}\n");
+    for (int k = 0; k < 2; ++k) {
+        pure_app_stop(&apps[k]);
+        pure_module_release(&modules[k]);
+    }
+    return 0;
+}