TP3/v-TP3-STRCMP.md

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.

1. 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.

1. 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).

2. 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 LOOPs 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 [a<b]+[a<=b]+[a>b]+[a>=b] is always 2, so [a<b] and [a>b] 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 <len><chars>, 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.