Merge branch 'worktree-agent-aaf6bc066598a6622' into ccr-0054c02e-dfdvnd

7 files changed, 292 insertions, 3 deletions

diff --git a/Makefile b/Makefile
index d5caa92..519d4d2 100644
--- a/Makefile
+++ b/Makefile
@@ -7,6 +7,8 @@
 #   make test            the whole suite (tests/test.sh)
 #   make check           the minimal suite, for iterating (tests/test.sh -q)
 #   make test JOBS=4     the same, four sections at a time
+#   make parity          compile the test programs with zc0 and with the self-hosted
+#                        compiler and compare what they print (src/tools/parity.sh)
 #   make genome          build/core/genome.bin from src/, with the fixpoint check
 #   make lsp             build/bin/zclsp, the language server
 #   make web             build/web/: the page, its script and zc.wasm
@@ -143,6 +145,11 @@ run:
 	$(CC) $(CFLAGS) $(MICRO_THREADS) src/micro/micro.c $(PORT) -Isrc/core -Isrc/micro -I$(B)/run --embed-dir=$(B)/run -o $(B)/run/zymr$(EXE)
 	@echo "built $(B)/run/zymr$(EXE)"
 
+# the two compilers on the same programs: whatever zc0 accepts must print the same
+# under both. work files go to build/parity/.
+parity: $(BIN)/zc0$(EXE) $(BIN)/mkgenome$(EXE) $(BIN)/zy$(EXE)
+	bash src/tools/parity.sh
+
 # JOBS sets how many sections run at once: make test JOBS=4
 test:
 	bash tests/test.sh -j $(or $(JOBS),1)
@@ -154,4 +161,4 @@ check:
 clean:
 	rm -rf $(B)
 
-.PHONY: all lsp genome js lspimage vsix web run test check clean
+.PHONY: all lsp genome js lspimage vsix web run parity test check clean
diff --git a/ONBOARD.md b/ONBOARD.md
index a0ed367..5b05862 100644
--- a/ONBOARD.md
+++ b/ONBOARD.md
@@ -163,6 +163,10 @@ make check
 make test JOBS=4
 ```
 
+`make parity` compiles the programs in `tests/programs/` and `examples/` with zc0 and
+with the self-hosted compiler and diffs their output; `tests/programs/parity_ops.zc`
+pins operator precedence. it uses `build/`, and skips what zc0 rejects.
+
 the suite builds its own map, bootstrap and cores in a scratch directory, so it
 does not depend on what is in `build/`. on a host without the arm64 jit the
 language server is interpreted and slow; `ZC_TEST_TIMEOUT_SCALE` stretches the
diff --git a/README.md b/README.md
index 0b59a6b..44ee129 100644
--- a/README.md
+++ b/README.md
@@ -31,13 +31,14 @@ run these commands from the repository root. everything built or generated goes
 make
 build/bin/zy < examples/hello.zc
 make test JOBS=4
+make parity
 make genome
 make web
 make js
 make run PROG=examples/hello.zc
 ```
 
-the cores embed their genome with c23 `#embed`, so the c compiler has to be clang 19 or gcc 15 or later. `src/tools/findcc.sh` finds one (`CC` set on the command line or in the environment is used as given, and must support it too). `make genome` bootstraps the compiler, compares two self-compiled images, and writes `build/core/genome.bin` only after they agree; `make` reruns it whenever a source of the genome changes, and the cores that embed it are rebuilt after it. `make check` runs the smaller suite while iterating. `ONBOARD.md` is a reading and verification order for getting to know the code.
+the cores embed their genome with c23 `#embed`, so the c compiler has to be clang 19 or gcc 15 or later. `src/tools/findcc.sh` finds one (`CC` set on the command line or in the environment is used as given, and must support it too). `make genome` bootstraps the compiler, compares two self-compiled images, and writes `build/core/genome.bin` only after they agree; `make` reruns it whenever a source of the genome changes, and the cores that embed it are rebuilt after it. `make check` runs the smaller suite while iterating. `make parity` (`src/tools/parity.sh`, `--help` for options) compiles the test and example programs with zc0 and with the self-hosted compiler and compares what they print, which the fixpoint check cannot see; programs zc0 rejects are skipped and counted, intended differences are listed in `tests/parity.known`, and work files go to `build/parity/`. `ONBOARD.md` is a reading and verification order for getting to know the code.
 
 ### command-line help
 
diff --git a/src/tools/parity.sh b/src/tools/parity.sh
new file mode 100755
index 0000000..2739a85
--- /dev/null
+++ b/src/tools/parity.sh
@@ -0,0 +1,160 @@
+#!/bin/bash
+# compiles the same programs with both compilers and compares what they print.
+# zc0 (stage 0, in c) compiles runtime + program into an image that runs on a
+# microcore with the image embedded; the self-hosted compiler compiles the
+# same source inside the vm (build/bin/zy < prog.zc). a program zc0 rejects is
+# outside its subset and is skipped. for every other program the two outputs
+# must be equal. the bootstrap's fixpoint cannot see a language rule both
+# compilers got wrong the same way, but this can see one they disagree on.
+#
+# the image is built the way src/tools/zcc builds a run-only program, on the
+# default map so that it behaves like the resident compiler's programs do:
+# rt.zc, core.zc, src/runtime/run.zc, a `namespace;` (the program starts in the
+# global namespace, as under zy) and the program go through build/bin/zc0,
+# build/bin/mkgenome checks the image, and a microcore embeds it (c23 #embed).
+# the core is compiled per program (about a second); it is kept under
+# build/parity/ and reused until the program, the compilers or the runtime change.
+#
+# stdin: zy reads the program from stdin and the program then reads what follows
+# a backtick that starts a line (see examples/learn/24-backtick.zc); the image
+# gets that same text, or nothing when the source has no such line.
+#
+# tests/parity.known lists the programs that differ on purpose (zc0 has no
+# ownership analysis, for one). they are still compared and shown as known, and
+# do not fail the run; one that agrees again is reported as stale.
+set -e
+usage() {
+    printf '%s\n' 'usage: src/tools/parity.sh [-v] [-t SECONDS] [FILE.zc...]' \
+        'compiles each program with zc0 and with the self-hosted compiler and compares stdout.' \
+        'without FILE the corpus is tests/programs/*.zc, examples/*.zc and examples/learn/*.zc.' \
+        'a program zc0 rejects is skipped and counted. both runs see the same stdin:' \
+        'the text after a backtick line in the source, else nothing.' \
+        'prints one line per mismatch and a summary; exit status 1 when anything differs' \
+        '(programs listed in tests/parity.known are shown but do not count).' \
+        'options:' \
+        '  -v          also list the skipped programs and why' \
+        '  -t SECONDS  time limit for each run (default 30); a program that hits it on both sides is skipped' \
+        '  --help, -h  show this help and exit' \
+        'work files are under build/parity/. environment: CC selects the c compiler (one with #embed).'
+}
+verbose=0; limit=30
+while [ $# -gt 0 ]; do
+    case "$1" in
+        --help|-h) usage; exit 0 ;;
+        -v) verbose=1; shift ;;
+        -t) [ $# -ge 2 ] || { echo "parity: -t needs a number of seconds" >&2; exit 2; }
+            case "$2" in ''|*[!0-9]*|0) echo "parity: -t needs a positive number of seconds" >&2; exit 2 ;; esac
+            limit=$2; shift 2 ;;
+        --) shift; break ;;
+        -*) echo "parity: unknown option $1; use --help for usage" >&2; exit 2 ;;
+        *) break ;;
+    esac
+done
+cd "$(dirname "$0")/../.."
+for f in "$@"; do [ -f "$f" ] || { echo "parity: no such file: $f" >&2; exit 2; }; done
+if [ $# -gt 0 ]; then progs=("$@"); else progs=(tests/programs/*.zc examples/*.zc examples/learn/*.zc); fi
+
+make -s build/bin/zc0 build/bin/mkgenome build/bin/zy >&2
+CC=${CC:-$(sh src/tools/findcc.sh)}
+root=$PWD
+ZC0=build/bin/zc0; MKG=build/bin/mkgenome; ZY=build/bin/zy
+W=build/parity
+KNOWN=tests/parity.known
+mkdir -p "$W"
+# what every image starts with, and how many lines that is (zc0 counts from the top)
+SRCS="src/runtime/rt.zc src/core/core.zc src/runtime/run.zc"
+{ cat $SRCS; echo 'namespace;'; } > "$W/prefix.new"
+if cmp -s "$W/prefix.new" "$W/prefix.zc"; then rm "$W/prefix.new"; else mv "$W/prefix.new" "$W/prefix.zc"; fi
+nprefix=$(wc -l < "$W/prefix.zc")
+# what the compiled image depends on besides the program
+DEPS="$ZC0 $MKG $W/prefix.zc src/micro/micro.c src/micro/port_linux.c src/micro/micro_port.h src/core/fops.h src/core/bops.h src/core/stack.h src/core/genome.h build/core/map/memmap.h"
+
+# one line of a program's output: newlines as /, control bytes as ?, cut to 60 columns
+short() {
+    local s
+    s=$(head -c 400 "$1" | tr '\n' '/' | tr -c '[:print:]' '?')
+    if [ ${#s} -gt 60 ]; then s="${s:0:60}..."; fi
+    printf '%s' "$s"
+}
+stale() { # $1 = built file: missing, or older than a dependency or the program $2?
+    local d
+    [ -x "$1" ] || return 0
+    for d in $DEPS "$2"; do [ "$d" -nt "$1" ] && return 0; done
+    return 1
+}
+isknown() { [ -f "$KNOWN" ] && grep -q "^$1[ #]" "$KNOWN"; }
+reason() { grep "^$1[ #]" "$KNOWN" | head -n1 | sed 's/^[^#]*# *//'; }
+# zc0 reports lines of the whole input; the program's own line is what helps
+rebase() {
+    local msg=$1 re='^zc0: line ([0-9]+): (.*)$'
+    if [[ $msg =~ $re ]]; then msg="zc0: line $(( BASH_REMATCH[1] - nprefix )): ${BASH_REMATCH[2]}"; fi
+    printf '%s' "$msg"
+}
+
+mkdir -p "$W/root"
+for f in *; do [ "$f" = build ] || ln -sfn "$root/$f" "$W/root/$f"; done
+compared=0; differ=0; known=0; skipped=0; timedout=0; broken=0
+skips=""
+for p in "${progs[@]}"; do
+    name=${p%.zc}; name=${name//\//_}
+    d=$W/$name
+    mkdir -p "$d"
+    if ! cat "$W/prefix.zc" "$p" | "$ZC0" > "$d/img.bin" 2> "$d/zc0.err"; then
+        skipped=$((skipped+1))
+        skips="$skips$p: $(rebase "$(head -n1 "$d/zc0.err")")"$'\n'
+        continue
+    fi
+    if stale "$d/run" "$p"; then
+        if ! "$MKG" < "$d/img.bin" > "$d/genome.bin" 2> "$d/build.err"; then
+            echo "broken: $p: zc0 accepts it but mkgenome rejects the image: $(head -n1 "$d/build.err")"
+            broken=$((broken+1)); continue
+        fi
+        if ! $CC -O2 -w -fwrapv -pthread -DZY_THREADS src/micro/micro.c src/micro/port_linux.c \
+                -Isrc/core -Ibuild/core/map -Isrc/micro --embed-dir="$d" -o "$d/run" 2> "$d/build.err"; then
+            echo "broken: $p: the c compiler failed on the zc0 image: $(head -n1 "$d/build.err")"
+            broken=$((broken+1)); continue
+        fi
+    fi
+    # the image already holds the program. both sides then read the same stdin
+    sed -n '/^`/,$p' "$p" | tail -c +2 > "$d/stdin"
+    # from a directory that shows the repository through links, so that a program that
+    # reads a file by its path finds it, and one that writes a file leaves it under build/
+    find "$W/root" -mindepth 1 -maxdepth 1 ! -type l -exec rm -rf {} +
+    case $p in /*) pabs=$p ;; *) pabs=$root/$p ;; esac
+    rc0=0; rcy=0
+    ( cd "$W/root" && timeout -k 1 "$limit" "$root/$d/run" < "$root/$d/stdin" > "$root/$d/out0" 2> "$root/$d/err0" ) || rc0=$?
+    ( cd "$W/root" && timeout -k 1 "$limit" "$root/$ZY" < "$pabs" > "$root/$d/outy" 2> "$root/$d/erry" ) || rcy=$?
+    if [ $rc0 = 124 ] && [ $rcy = 124 ]; then
+        timedout=$((timedout+1))
+        skips="$skips$p: no result within ${limit}s on either side"$'\n'
+        continue
+    fi
+    compared=$((compared+1))
+    msg=""
+    if [ $rc0 = 124 ] || [ $rcy = 124 ]; then
+        [ $rc0 = 124 ] && a="(timed out after ${limit}s)" || a="[$(short "$d/out0")]"
+        [ $rcy = 124 ] && b="(timed out after ${limit}s)" || b="[$(short "$d/outy")]"
+        msg="$p: zc0 $a, self-hosted $b"
+    elif ! cmp -s "$d/out0" "$d/outy"; then
+        msg="$p: zc0 [$(short "$d/out0")], self-hosted [$(short "$d/outy")]"
+    fi
+    if [ -z "$msg" ]; then
+        isknown "$p" && echo "stale: $p agrees now; remove it from $KNOWN"
+    elif isknown "$p"; then
+        known=$((known+1))
+        echo "known: $msg ($(reason "$p"))"
+    else
+        differ=$((differ+1))
+        echo "differ: $msg"
+    fi
+done
+if [ $verbose = 1 ] && [ -n "$skips" ]; then
+    echo "skipped:"
+    printf '%s' "$skips" | sed 's/^/    /'
+fi
+extra=""
+[ $timedout -gt 0 ] && extra="$extra, $timedout skipped (timeout)"
+[ $known -gt 0 ] && extra="$extra, $known known ($KNOWN)"
+[ $broken -gt 0 ] && extra="$extra, $broken did not build"
+echo "parity: $compared compared, $differ differ, $skipped skipped (outside zc0)$extra"
+[ $differ -eq 0 ] && [ $broken -eq 0 ]
diff --git a/tests/drivers/cli_help_test.py b/tests/drivers/cli_help_test.py
index 97eebea..1231f74 100644
--- a/tests/drivers/cli_help_test.py
+++ b/tests/drivers/cli_help_test.py
@@ -14,7 +14,7 @@ commands = []
 if args.group in ('binaries', 'all'):
     commands += [[str(Path(args.bin_dir) / name)] for name in ['zy', 'zym', 'zclsp', 'zc0', 'mkgenome', 'genmap']]
 if args.group in ('scripts', 'all'):
-    commands += [['bash', name] for name in ['tinyvm.sh', 'src/tools/zcc', 'src/tools/automap.sh', 'src/tools/findcc.sh', 'src/tools/bootstrap-check.sh', 'src/tools/mklsp.sh', 'src/tools/mklspwasm.sh', 'src/tools/mkvsix.sh', 'src/web/build.sh', 'src/baremetal/run.sh']]
+    commands += [['bash', name] for name in ['tinyvm.sh', 'src/tools/zcc', 'src/tools/automap.sh', 'src/tools/findcc.sh', 'src/tools/bootstrap-check.sh', 'src/tools/parity.sh', 'src/tools/mklsp.sh', 'src/tools/mklspwasm.sh', 'src/tools/mkvsix.sh', 'src/web/build.sh', 'src/baremetal/run.sh']]
 if args.group in ('js', 'all'):
     commands += [['node', name] for name in [str(Path(args.js_dir) / 'tinyvm.js'), 'src/js/mklayout.js', 'src/js/extract_lsp.js']]
 
diff --git a/tests/parity.known b/tests/parity.known
new file mode 100644
index 0000000..0a73eb3
--- /dev/null
+++ b/tests/parity.known
@@ -0,0 +1,15 @@
+# programs where zc0 and the self-hosted compiler print different things on purpose.
+# src/tools/parity.sh still runs them and shows the difference as known, and it does
+# not fail the run; when one starts to agree it says so, and its line can go.
+# one program per line: the path, then # and the reason.
+#
+# zc0 reads types and ownership tags and throws them away. it has no ownership
+# analysis and no memdebug checks, so it neither warns about, traps on nor frees what
+# the self-hosted compiler does.
+tests/programs/doublefree.zc # memdebug on: only the self-hosted compiler emits the double free check
+tests/programs/scrub.zc # ownership: the analyzer warns about the use after free, zc0 runs it
+tests/programs/uaf.zc # ownership: the analyzer warns about the use after free; zc0 prints nothing
+tests/programs/uaf_in.zc # memdebug on: only the self-hosted compiler emits the use after free check
+examples/lists.zc # ownership: the block's owner frees at its end, zc0 never frees
+# the next program reads a local it never sets when stdin is empty, so it prints stack garbage
+tests/programs/bench_strings.zc # reads the repeat count from stdin; with none, acc is uninitialized
diff --git a/tests/programs/parity_ops.zc b/tests/programs/parity_ops.zc
new file mode 100644
index 0000000..1c3c760
--- /dev/null
+++ b/tests/programs/parity_ops.zc
@@ -0,0 +1,102 @@
+// operator precedence and associativity, the same in both compilers. every binary
+// operator is placed next to its neighbours in the table and between two of the same
+// kind, so a wrong binding changes a printed number. src/tools/parity.sh compiles
+// this program with zc0 and with the self-hosted compiler and compares the output.
+// it stays inside zc0's subset: no ?: (zc0 has none), no types beyond int.
+//
+// the table, tightest first: unary - ! ~ * &, then * / %, + -, << >>, < > <= >=,
+// == !=, &, ^, |, &&, ||, then the assignments, which group to the right. every
+// binary operator groups to the left. the expected output follows the c rules and
+// was checked by compiling the same expressions with a c compiler.
+namespace;
+include rt;
+
+int trace, calls;
+int seen(int v) { calls++; trace = trace * 10 + v; return v; }
+int id(int v) { return v; }
+int out(int v) { rt.put_n(v); rt.put_c(32); return v; }
+int endl() { rt.put_c(10); return 0; }
+
+int main() {
+	// operands the compilers cannot fold away
+	int a = id(2), b = id(3), c = id(4), e = id(5), z = id(0), one = id(1);
+
+	// * / % against + -, and left grouping
+	out(a + b * c); out(a * b + c); out(a - b * c); out(a * b - c); out((a + b) * c);
+	out(id(100) - 30 - 20); out(1 - 2 + 3); out(id(100) / 5 / 2); out(id(20) / 3 * 3);
+	out(a * b % c); out(id(100) % 7 % 3); out(id(100) / 10 % 4); out(id(7) % 4 * 3);
+	endl();
+
+	// + - against << >>, and left grouping
+	out(one << a + one); out(id(32) >> a - one); out(one << a << b); out(id(256) >> a >> one);
+	out(one << b * a); out(id(8) >> one << one);
+	endl();
+
+	// shifts against < > <= >=, and the relational chain
+	out(one << a < e); out(id(16) >> one > 7); out(a < b < c); out(e > c > b);
+	out(z <= e <= z); out(a >= b >= z);
+	endl();
+
+	// relations against == !=, and the equality chain
+	out(a < b == one); out(one == a > b); out(e == e == one); out(b != c != one);
+	out(id(3) > a == one < a);
+	endl();
+
+	// == against & ^ |
+	out(c & c == c); out(one | a == a); out(b ^ b == b); out(a == a & one); out(c != z | z);
+	endl();
+
+	// & ^ | against each other, and against + and <<
+	out(c | b & one); out(id(7) ^ e & b); out(one | 6 ^ b); out(id(6) & b | 8);
+	out(a + 6 & c); out(one & b << one); out(id(12) | one << a);
+	endl();
+
+	// && and || against | & and each other; the result of both is 0 or 1
+	out(one || z && z); out(z && z || one); out(z || one && one || z); out(z && one | one);
+	out(one || z & z); out(b && c); out(b & c); out(z || id(9)); out(id(7) && id(8) && z);
+	out(a < b && c < e || z); out(z == z || z && z);
+	endl();
+
+	// unary operators
+	out(-a * b); out(- -b); out(-a + e); out(!z + one); out(!a == z); out(!!id(7));
+	out(~z & 255); out(~one + one); out(~a & 7); out(-a * -b); out(a - -b); out(-id(7) % 4);
+	out(!(a < b) + one); out(*&a + one); out(-*&b);
+	endl();
+
+	// assignment groups to the right and takes the whole expression on its right
+	int x, y, w;
+	x = y = w = id(7); out(x); out(y); out(w);
+	x = id(10); x -= 3 - 1; out(x);
+	x *= a + b; out(x);
+	x <<= one + one; out(x);
+	x |= one << b; out(x);
+	x += y -= 2; out(x); out(y);
+	x = id(100); x /= a * b; out(x);
+	x %= 7 - 2; out(x);
+	x = id(6); x &= 3 | 8; out(x);
+	x ^= 1 + 2 * 3; out(x);
+	x = id(255); x >>= 2 + 2; out(x);
+	endl();
+
+	// division, remainder and shifts of negative numbers
+	out(id(0) - 7 / 2); out((id(0) - 7) / 2); out((id(0) - 7) % 3); out(id(7) % (id(0) - 3));
+	out((id(0) - 8) >> 1); out((id(0) - 8) << 1);
+	endl();
+
+	// short circuit: how many operands ran, and in what order
+	calls = 0; trace = 0; x = seen(0) && seen(1); out(x); out(calls); out(trace);
+	calls = 0; trace = 0; x = seen(1) || seen(2); out(x); out(calls); out(trace);
+	calls = 0; trace = 0; x = seen(1) || seen(2) && seen(3); out(x); out(calls); out(trace);
+	calls = 0; trace = 0; x = seen(0) || seen(2) && seen(3); out(x); out(calls); out(trace);
+	calls = 0; trace = 0; x = seen(0) && seen(2) || seen(3); out(x); out(calls); out(trace);
+	calls = 0; trace = 0; x = seen(1) && seen(0) || seen(2) && seen(3); out(x); out(calls); out(trace);
+	calls = 0; trace = 0; x = seen(1) | seen(2) && seen(0) & seen(3); out(x); out(calls); out(trace);
+	endl();
+
+	// operands run left to right whatever their binding
+	calls = 0; trace = 0; x = seen(1) + seen(2) * seen(3) - seen(4); out(x); out(calls); out(trace);
+	calls = 0; trace = 0; x = seen(1) << seen(2) < seen(3) == seen(4); out(x); out(calls); out(trace);
+	calls = 0; trace = 0; x = out(seen(1) - seen(2)) * out(seen(3)); out(x); out(calls); out(trace);
+	endl();
+	return 0;
+}