Skip to content

EVIDENCE-stringwall-slice3.adoc

Latest commit

 

History

History
140 lines (110 loc) · 5.48 KB

EVIDENCE-stringwall-slice3.adoc

File metadata and controls

140 lines (110 loc) · 5.48 KB
Raw

Phase F — string-wall slice 3: string_sub (evidence)

Important

Slice landed: the runtime-length copy op. string_sub(s, start, length) — already wired in resolve/typecheck/interp — gained a wasm-backend lowering that introduces the two capabilities the rest of the string wall needs: a runtime-sized heap allocation and a byte-copy loop. Both are modelled on the existing list ++ lowering (the canonical allocate-then-copy idiom in lib/codegen.ml).

Third slice of the variable-string backend wall (proposals/MIGRATION-PLAN.adoc §"The two walls", Phase F). With runtime allocation + copy now in hand, the remaining write-side ops (concat, case-fold) and the read-side scans (startsWith, string_find) reuse these idioms.
Table of Contents

What was missing

Builtin resolve.ml typecheck.ml interp.ml codegen.ml (wasm)

string_char_code_at / char_to_int

✓

✓

✓

✓ (slice 1)

string_from_char_code

✓

✓

✓

✓ (slice 2)

string_sub

✓

✓

✓

was missing → added

Before this slice it failed at codegen:

Code generation error: (Codegen.UnboundVariable
   "Function or variable not found: string_sub")

The lowering (lib/codegen.ml)

Interp oracle (lib/interp.ml):

slen    = String.length s
start'  = max 0 (min start slen)
length' = max 0 (min length (slen - start'))
String.sub s start' length'

The wasm lowering, on the [len: i32 LE][utf8] ABI:

  1. Evaluate s (→ base pointer), start, length; load slen from [src+0].

  2. Clamp: start' = max(0, min(start, slen)), then length' = max(0, min(length, slen - start')). min/max use Select over the operand pair (the operands are locals/constants — no side effects, so evaluating both arms is safe, unlike the bounds-guarded load in slice 1).

  3. Runtime-sized allocation: dst = heap; heap = 4 + length'` — the bump allocator (`ensure_heap_ptr`) with a runtime byte count, exactly as list `+ allocates 4 + (la+lb)*4.

  4. Store length' at [dst+0].

  5. Copy loop (Block [ Loop [ k>=length' ? break; dst[4+k] = src[4+start'+k]; k; continue ] ]`), byte-wise via `I32Load8U` / `I32Store8`. Same `Block`/`Loop`/`BrIf 1`/`Br 0` idiom as the list-` element copy, with a 1-byte stride instead of 4.

  6. Return dst.

All clamps are non-negative (max 0), so no negative addresses are formed. length' = 0 exits the loop immediately and yields the empty string.

Gate evidence

Gate 1 — builds

dune build bin/main.exe exit 0. The previously-failing op now compiles and round-trips with the slice-1 reader.

Gate 2 — parity (wasm vs interpreter oracle)

Same inputs through both backends agree across normal extraction, both clamps, negative start, and zero length. Interp oracle confirmed against the real library API; wasm executed under Node.

Expression interp wasm

scca(string_sub("hello",1,3), 0) ('e')

101

101

scca(string_sub("hello",1,3), 2) ('l')

108

108

string_length(string_sub("hello",1,3))

3

3

string_length(string_sub("hello",0,5)) (full)

5

5

string_length(string_sub("hello",2,100)) (clamp length)

3

3

string_length(string_sub("hello",10,3)) (clamp start)

0

0

scca(string_sub("hello",-1,2), 0) (neg start → 0, 'h')

104

104

string_length(string_sub("hello",1,0)) (zero length)

0

0

(scca = string_char_code_at, the slice-1 reader.)

The packed fixture tests/codegen/string_sub.affine returns 6843501 (positional pack of three round-tripped bytes + four length probes); both backends produce it.

Tests added

  • test/test_e2e.ml — group "E2E String-wall slice 3 (string_sub)": eight interp-oracle cases (extraction, length, length-clamp, start-clamp, negative-start, zero-length). Runs under dune runtest. The interp consumer coverage mandated by .claude/CLAUDE.md §"Test-fixture hygiene".

  • tests/codegen/string_sub.affine + tests/codegen/test_string_sub.mjs — executable wasm parity, run by tools/run_codegen_wasm_tests.sh (CI).

Full tools/run_codegen_wasm_tests.sh run: all codegen WASM tests pass (slices 1, 2, and 3 string harnesses), no sibling regressions.

Corpus impact

The runtime-length allocation + byte-copy loop are now established string primitives. This unblocks substring extraction directly, and gives the next slices their building blocks:

  • Concatenation (` on strings, `string_concat`) — allocate `4 + la + lb`, copy both byte ranges (two copy loops, like list `).

  • Case-folding (to_lowercase / to_uppercase) — allocate 4 + slen, copy with a per-byte transform in the loop body.

  • Scans (startsWith, string_find) — comparison loops over slice-1 indexing; no allocation.

Next slices (variable-string backend wall)

  1. Concatenation — string_concat / ++ on strings (two copy loops into a 4 + la + lb allocation).

  2. Scans — string_find (substring search returning an index), the read-side loop with no allocation.

  3. Case-folding — to_lowercase / to_uppercase (copy-with-transform).

  4. slice — the polymorphic (array|string) JS-semantics variant with negative-index normalisation; needs compile-time array-vs-string dispatch.

Each slice: add the codegen arm, an interp-parity e2e group, and a tests/codegen/*.mjs executable check, then re-run the census and drop the gated count.