v-TP3-STRCMP — Session summary ============================== Tag: v-TP3-STRCMP Commit: (the commit that adds this file) Fixes: the commit immediately before it, "tests: re-anchor three nonvacuity mutations that item 1a invalidated" (see "Non-vacuity" below) Covers: v-TP3-STRCMP This is the resume point for the session that did "Next work" item 1b — string comparison with `= <> < <= > >=` — in full, and for the test-harness repair that running `tests/nonvacuity.sh` at the start of it turned up. Every claim below is pinned by a fixture in `shell/tests/fixtures/expected.tsv` and by the gate suite. What changed ------------ 1. String comparison — `= <> < <= > >=` with both operands strings (`v-TP3-STRCMP`). `ParseCmp` had one arm, the numeric one: both operands are loaded into `AX`/`CX`, `CMP AX,CX` sets the flags, and a six-entry `SETcc` table turns them into a 0/1. A string operand never reached that arm — it fell through to `LoadAtom`, which refuses a `TString` with `ENoLib` (102). The new arm is put **before** the constant-fold arm, because a string literal is not a kind-0 constant and the numeric arm's own dispatch would have swallowed it: IF (left.cls = TString) OR (right.cls = TString) THEN IF (left.cls # TString) OR (right.cls # TString) THEN Err (ETypeErr) ; (* a string compared with a number/char *) RETURN END ; EmPushStrAddr (left) ; EmPushStrAddr (right) ; DropC (EmCall (TU_CmpStr)) ; EmAddSp (4) ; EmOrAxAx () ; EmRelSetcc (op) ; r.kind := 2 ; r.cls := TBool ELSIF (left.kind = 0) AND (right.kind = 0) THEN ... constant fold ... ELSE LoadPair (left, right) ; EmCmpAxCx () ; EmRelSetcc (op) ; r.kind := 2 ; r.cls := TBool END The tail is not a second implementation: `EmRelSetcc` is the same six-arm table the numeric arm uses, factored out of `ParseCmp` when the string arm arrived. The two paths therefore cannot drift, which matters because the table's arms are two hex digits apart (`SETG` 9FH vs `SETGE` 9DH) and were swapped once already — see `EmRelSetcc`'s comment and `tests/nonvacuity.sh`'s `mutate_cc_swap`, which mutates exactly those two lines and now breaks the string comparison at the same time as the numeric one. 2. A new runtime entry — `cmpstr`, selector 18 (`Runtime.mod`, `Runtime.def` `E_CmpStr = 18`). It takes two string *addresses* on the stack (caller-pushed, caller-popped) and returns `AX = -1 / 0 / +1` for left < right / = / >. 83 bytes at image offset 585 (`0249h`..`029Bh`): 0249 55 push bp 024F 31 C9 xor cx,cx 024A 8B EC mov bp,sp 0251 31 D2 xor dx,dx 024C 53 push bx 0253 8B 5E 06 mov bx,[bp+6] 024D 51 push cx 0256 8A 0F mov cl,[bx] 024E 52 push dx 0258 8B 46 04 mov ax,[bp+4] 025B 8B F0 mov si,ax 025D 8A 14 mov dl,[si] 025F 39 D1 cmp cx,dx 0261 76 02 jbe 0265h 0263 8B CA mov cx,dx 0265 E3 0E jcxz 0275h 0267 43 inc bx 0268 46 inc si 0269 8A 07 mov al,[bx] 026B 8A 14 mov dl,[si] 026D 3A C2 cmp al,dl 026F 75 14 jne 0285h 0271 43 inc bx 0272 46 inc si 0273 E2 F4 loop 0269h 0275 8B 5E 06 mov bx,[bp+6] 0278 8A 0F mov cl,[bx] 027A 8B 46 04 mov ax,[bp+4] 027D 8B F0 mov si,ax 027F 31 D2 xor dx,dx 0281 8A 14 mov dl,[si] 0283 39 D1 cmp cx,dx 0285 B0 00 mov al,0 0287 B4 00 mov ah,0 0289 72 06 jb 0291h 028B 74 08 je 0295h 028D B0 01 mov al,1 028F EB 04 jmp 0295h 0291 B0 FF mov al,0FFh 0293 B4 FF mov ah,0FFh 0295 5A pop dx 0296 59 pop cx 0297 5B pop bx 0298 8B E5 mov sp,bp 029A 5D pop bp 029B C3 ret The layout is deliberate and each part is worth naming: - `min(lenL,lenR)` bytes are compared in order; the **first difference decides** (`jne cs_flag`). The byte compare is `CMP AL,DL`, i.e. **unsigned** — CF is the borrow out of AL−DL — which is what "lexicographic" means for characters. - If the common prefix is equal, the **lengths decide** (`cs_len` re-reads them; `cmp cx,dx` then falls into `cs_flag`). So a proper prefix is **less** than the string that continues it: `'ab' < 'abc'`, and the empty string is less than everything. - The lengths are re-read from the arguments rather than held in registers across the loop, so `CX` is free to be `LOOP`'s count. `JCXZ` skips the loop when `min = 0`: without it, `LOOP` with `CX = 0` runs 65536 times. - `CmpAlDl` is `3A C2`, not `38 C2`. `/r` puts the register field where the *left* operand is, so `3A C2` is `CMP AL,DL` and `38 C2` would be `CMP DL,AL`, i.e. the same bytes with the flags negated. 3. Harness re-baselines, all in this commit, because the runtime entry moves offsets and the fixtures add files: - `tests/RtProbe.mod`: the entry table widened from `[0..17]` to `[0..18]`, plus `names[18]`. - `tests/check_runtime.py`: `GOLDEN["cmpstr"] = "55 8B EC 53 51 52"` (the prologue minus `AX`, which is the result and is not saved). - `tests/runtime.golden`: re-blessed. **The diff is worth reading** and is exactly two things: eight absolute data-address fixups, each `+0x53`, because the data area starts after the code and the code grew by 83 bytes (`0x53`); and the appended `cmpstr` block at `0249h`. No existing instruction moved. - `tests/rt_exec.py`: `ENTS` gains `cmpstr`, plus a read-only smoke case. - `tests/check_8086.py`: `BRANCH_SITES["t48_strcmp"] = [4] * 30` and `["t49_strcmp_lit"] = [4] * 13`, with `BRANCH_WHY` text. - `tests/audit_helpers.py`: `"PushStrAddr": COMP` in `Compiler.mod`'s `NON_ONE_LINE` — see "Scope decisions" below. - `tests/fixtures/expected.tsv`: three new rows (below). 4. `tests/check_runtime.py`'s branch scan learned `LOOP`. `RE_BRANCH` was `^(?:j\w+|call|jmp)\s+...$`, so it saw every `Jcc`, `JMP` and `CALL` — but **not** `LOOP`. `LOOP` is a relative branch too, and its target has to land on an instruction boundary like any other. The runtime already contained **four** `LOOP`s when this was found (they are much older than this session); `cmpstr` added a fifth, and only then did the gap come into view. Widening the regex moved the checked-branch count from 57 to 62 — +5, one per `LOOP`. The bug that only execution could see ------------------------------------- The first `cmpstr` epilogue saved and restored **`AX`** with the other registers: PushAx ; PushBx ; PushCx ; PushDx ... PopDx ; PopCx ; PopBx ; PopAx That is wrong, and wrong in a way no static check can see: `AX` is the *result*, so there is nothing to save, and popping it back restores the **caller's** `AX` — which, for `a < b`, is the address of the *right* operand, still in `AX` from its `LEA`. Every ordering comparison then read a positive number: `=` and `<>` were correct (they test zero), while `<`, `<=`, `>`, `>=` over any `left < right` string came back as `FALSE TRUE TRUE TRUE FALSE FALSE`. Nothing about the bytes is malformed, the size is unchanged, every branch target is still on a boundary, and the whole compile matrix stayed green. It was caught only by *executing* `t48`, and confirmed by hand on qemu. The fix is the epilogue it has now — `PopDx ; PopCx ; PopBx ; MovSpBp ; PopBp ; RetR` — and the comment in `EmitCmpStr` records it so the next reader does not have to rediscover why `AX` is the one register this entry does not preserve. Semantics: what a comparison of strings MEANS here -------------------------------------------------- - **What the compiler compares is the sign of `−1/0/+1`, and that test is SIGNED.** `cmpstr` does the character work with *unsigned* byte compares (that is TP3's `cmpstr` / `vcompare`, TPSRC2 926-962 / TPSRC9 133), but the compiler only ever sees the signed result and runs the same signed `SETcc` table the numeric arm uses. Signed is load-bearing: `−1` is `0FFFFh`, so `SETB` (unsigned below) would be *false* on `−1` and every `a < b` would come back `FALSE`. `SETL`/`SETG`/`SETGE`/`SETLE` are the right four. - **Prefix rule.** A shorter string that is a prefix of a longer one is **less**: `'ab' < 'abc'`, `'' < 'ab'`. This is the tiebreak, and `t48` pins both directions as separate blocks. - **`1`-character literal is a `CHAR`, not a string.** ISO Modula-2 makes `'a'` a character constant, so `s = 'a'` is `TString` vs `TScalar` and is `ETypeErr` (56) — `t50`. The *empty* literal `''` is different: it is the zero-length **string**, and it works (`t49` uses it). This is the same rule `c := 'a'` already relied on. - **A string compared with a number or a character is `ETypeErr`.** The mixed-operand guard is new; before string comparison existed the program failed later and with the wrong diagnosis. `t50` pins the new one. Fixtures added -------------- t48_strcmp OK 1905 24 string = <> < <= > >=, both operands string variables. Output: 41, 14, 50, 14, 50, then the six as VALUES: FALSE TRUE TRUE TRUE FALSE FALSE t49_strcmp_lit OK 1006 15 the same operators with a string LITERAL on one or both sides, including the empty literal. Output: 61, 7, 15, then four as VALUES: TRUE FALSE TRUE TRUE t50_strcmp_type ERR 56 600 `s = 'a'`: a one-character literal is a CHAR, so this is the mixed-operand error `t48`'s output is deliberately **not** a count of the six operators. Each block weights them 1,2,4,8,16,32 for `=,<>,<,<=,>,>=`, so the printed sum is a signature of *which* ones held (`41` = `=`,`<=`,`>=`; `14` = `<>`,`<`,`<=`; `50` = `<>`,`>`,`>=`). A plain `+1` cannot do this: for any unequal pair `[ab]+[a>=b]` is always 2, so `[ab]` cancel and the first version of this fixture reported `3,3,3,3` while **every** ordering comparison was inverted. The weights are what made the `AX`-restore bug visible as a wrong *number* instead of a plausible one. Scope decisions and findings ---------------------------- - **`AX = −1/0/+1`, not flags.** The sketch in `v-TP3-STRIDX-VAR.md` said "a new runtime entry taking two addresses and leaving flags set is enough because `EmSetcc` reads live flags". That is not enough *here*, and the reason is in `EmitCmpStr`'s comment: this caller pushes two addresses and must drop them with `ADD SP,4`, which is in the CPU's arithmetic group and **destroys the flags**. TP3 can branch on flags straight after its `cmpstr` because TP3's `cmpstr` removes its own arguments (`MOV SP,BX`, TPSRC2 960), so there is no `ADD SP` to run. Returning a value in `AX` costs a few instructions inside the entry and keeps the flag convention entirely inside the compiler, where the one `EmRelSetcc` table already lives. - **`OR AX,AX` (`09 C0`), not `CMP AX,0` (`3D 00 00`).** Same flags (SF/ZF set, OF/CF cleared), but `tests/check_8086.py` reads every `3D 00 00` in the program region as an IF/WHILE/REPEAT test and requires a branch immediately after it — and `writeln (a = b)` is a comparison used as a **value**, not a test. `TEST AX,AX` (`85 C0`) is equivalent but has no mnemonic in the audit's name grammar, so `EmOrAxAx` it is. (A TP3 wrapper is literally `MOV AX,#1 / Jcc / DEC AX / OR AX,AX`: the same `SETcc` our numeric arm emits followed by the same `OR AX,AX`. This design moves that tail out of six per-operator runtime entries and into the one shared table. TP3 needs the six because its `cmpstr` is reached through `vcompare`'s vector table by type; we already have the operator as a number.) - **String literals travel inline in the code stream.** A literal has no storage, and a `.COM` image carries no initialised data (globals are left to the loader's zero fill), so `EmPushStrAddr` emits `JMP` over the bytes — `EB rel8` (rel8 = len+1) or `E9 rel16` when `len+1 > 127` — then a length byte, then the characters, and pushes the address of the **length byte** (`LEA AX,[here]; PUSH AX`, absolute into CS, which is where a `.COM`'s DS already is). This mirrors TPSRC9 `fullvar` (993), with **one extra byte**: TP3's constant is an `ARRAY [1..n] OF CHAR` and `estr2` (TPSRC10 85) emits it *without* a length byte because the length travelled on the stack instead. Every string in this runtime — variable or literal — is ``, which is what `rdstr` writes and what `cmpstr` reads, so a literal operand has to look the same. The jump exists only to keep the CPU from walking into the characters. - **Argument order is left first, right second** — left at `[BP+6]`, right at `[BP+4]` — the same order `strstore` takes its two. - **The audit's `Em*` naming rule bit again.** `audit_helpers.py` strips the first two characters of every emitter's name to find it in the grammar, so a `Compiler.mod` emitter whose name does not begin `Em` becomes a name the grammar has never heard of. `PushStrAddr` would have stripped to `shStrAddr`; it is `EmPushStrAddr`, a proper sibling of `EmPushVarAddr`. It also needed `"PushStrAddr": COMP` in `NON_ONE_LINE["Compiler.mod"]` (it has a parameter list, which the by-name audit excludes) — the same rule that bit `LeaDi` last session, documented in `audit_helpers.py`'s header. Non-vacuity: three mutations that had rotted, and a fifth `LOOP` -------------------------------------------------------------- `tests/run_all.sh` says to run `tests/nonvacuity.sh` directly after touching any of the checks, and it was red when this session ran it: **75 ok, 3 failed**. All three were pre-existing — they fail at the previous tag too — because `v-TP3-STRIDX-VAR` (item 1a, `s [i]`) changed the code the mutations match. `SUMMARY.md` at that same tag already claimed `non-vacuity: 78 ok, 0 failed`. The number of cases (78) was right; the "ok, 0 failed" was not, and one of the three failures (`EmBpDisp`) was of exactly the kind this file exists to catch — a mutation that had *silently stopped applying*, so the check it was supposed to prove non-vacuous was passing without being disturbed at all: 1. **`check_framedisp` / `EmBpDisp`.** The mutation restored the original `off MOD 100H`, always-disp8 bug by matching the old body verbatim. Item 1a gave `EmBpDisp` a `regf` parameter (the DI forms need reg 7), so the anchor no longer matched; the mutation silently applied *nothing*, the compiler rebuilt unmutated, and the check passed — reported as `NOT NON-VACUOUS`. Both `EmBpDisp` mutations are re-anchored, and both keep `regf`: the mutation is about the disp8/disp16 choice, and breaking the DI forms at the same time would be two faults wearing one label. 2. **`SaveLeft`.** The mutation made the park unreachable by matching the old kind-2 body. Item 1a added an `ELSIF left.kind = 5` branch, so the anchor missed and the case was reported `BROKEN CASE`. It now disables **both** guards, asserting each is unique — `IF left.kind = 2` reads like it can only be `SaveLeft`'s, but other routines branch on kind too. 3. **The string-assignment arm.** The mutation spliced the arm out between its guard and the `size > 2` refusal that follows it. Item 1a added `AND (r.cls = TString)` to that guard (so the new `s[i] := c` element arm is not swallowed by the whole-string one) and gave `ParseSub` a look-alike `IF symtab [r.idx].cls = TString THEN`. The shorter anchor therefore found `ParseSub`'s, ~800 lines earlier, and the splice deleted everything between the two — the compiler would not rebuild. The guard is now spelled out in full. Each repair was checked by hand: the truncation case again reports its named message (`no 8B access at [BP+128]`, offsets seen include `−128`), the left-operand case again makes `t34_arith` print `FAIL`, and the string-assignment case again makes `t39` red. The suite is **78 ok, 0 failed**. How to verify this session's work --------------------------------- cd shell && make # tpshell 195576 bytes, rc=0 cd shell && tests/run_all.sh # expect: OVERALL: ALL PASS cd shell && tests/nonvacuity.sh # expect: 78 ok, 0 failed At this tag the suite reports: compile matrix: 51 passed, 0 failed (of 51) independent .COM check: 45 checked, 0 failed execution: 45 passed, 0 failed (of 45) exec86: 45 passed, 0 failed (of 45), cross-checked against qemu audit_helpers: 112/112 agree (was 110) runtime entries: 52 passed, 0 failed (of 52) check_8086: 39 comparison sites, 35 lowered to a Boolean value, 57 to a branch; clause H 10 of 10; 45 of 45 fixtures swept, 8576 bytes runtime: 699 bytes, code 0..667 (668), 19 entries, 62 branches checked (was 616 bytes, 18 entries, 51 branches: +6 = cmpstr's Jcc/JMP, +5 = the five LOOPs the widened branch scan now sees) nonvacuity: 78 ok, 0 failed (was 75 ok, 3 failed) OVERALL: ALL PASS Each new behaviour was proven red before green: with the old `ParseCmp`, `t48` and `t49` both report `ERR 102` (`ENoLib`, "not implemented") at the first comparison, and `t50` fails with the *old* (wrong) diagnosis rather than `ETypeErr`. The `AX`-restore bug is the other kind of red — every byte and every size green, and only `t48`'s weighted sums show it. Next work --------- Item 1 (the rest of the string language): c. **Concatenation `+`** — the last piece of item 1, and the hardest. TP3's `addstr` (TPSRC9 194) reaches `xconcat` (TPSRC2 963); `addch` / `addch2` convert a one-character operand with `MOV AH,AL ; MOV AL,#01` then `PUSH AX` — *that* is how TP3 makes `s + 'a'` legal, where our compiler currently treats a one-character literal as a `CHAR` (the same rule `t50` pins). TP3 pushes strings inline on the stack; this model addresses them, so a result needs a scratch string and a length rule (TP3 caps at 255). This adds a runtime entry again, so `runtime.golden`, `check_runtime.py`, `rt_exec.py` (next selector is 19) and the branch count all move with it. Item 2 (the large one) is untouched: nested procedures / recursion, `var` parameters (the `SEG:OFF` push, RESUME-TP3.md 3.11), range/index checks (`TU_RANGE_CHECK`, `TU_INDEX_CHECK`), typed constants (3.14), `array` at its point of use (t14), `case` with subrange labels. Also still open from before this session: d. Harden the program-header parameter loop against non-advancing input (`program p(1;)`) with a `BOOLEAN` flag — NOT `EXIT`, which ICEs gm2. e. FreeDOS (`freedos.qcow2`, FD14-LiveCD) is still untried; it is the only third opinion on the `INT 21h` shim.