Skip to content

EVIDENCE-stringwall-slice6.adoc

Latest commit

 

History

History
137 lines (112 loc) · 5.72 KB

EVIDENCE-stringwall-slice6.adoc

File metadata and controls

137 lines (112 loc) · 5.72 KB
Raw

Phase F — string-wall slice 6: string_find (evidence)

Important

Slice landed: substring search (read-side, no allocation). string_find(haystack, needle) — already wired in resolve/typecheck/interp — gained a wasm-backend lowering: a nested scan returning the first-occurrence index or -1.

Also fixes an interp bug: the interp’s string_find called String.get needle 0 before its nlen = 0 guard, so an empty needle crashed the interpreter with an uncaught Invalid_argument (the nlen = 0 branch was dead code). The guard is now reordered so an empty needle returns 0 (standard) — making the two backends agree.

Sixth slice of the variable-string backend wall (proposals/MIGRATION-PLAN.adoc §"The two walls", Phase F). With this, all the name-dispatched string builtins that have a faithful trap-free wasm analogue are lowered.
Table of Contents

Two changes

  1. lib/interp.ml — bugfix. Move the length guards (nlen = 0 → 0, nlen > hlen → -1) ahead of String.get needle 0. Before:

    match String.index_opt haystack (String.get needle 0) with   (* raises on "" *)
| None -> -1
| Some _ -> let hlen = ... and nlen = ... in
            if nlen = 0 then 0 else ...                       (* dead code *)

    After: compute hlen/nlen first; if nlen = 0 then 0 else if nlen > hlen then -1 else (index_opt-guarded scan). Behaviour is identical for every non-empty needle (the index_opt fast-path is preserved); only the empty needle changes — from uncaught crash to 0.

  2. lib/codegen.ml — wasm lowering. Nested scan, no allocation:

    hlen = haystack[0]; nlen = needle[0]; res = -1; i = 0
loop (outer):
  if res != -1: break                       ;; already found
  if i > hlen - nlen: break                 ;; past last start (covers nlen>hlen: bound < 0)
  m = 1; j = 0
  loop (inner): if j >= nlen: break
                m = m & (haystack[i+j] == needle[j])   ;; AND-accumulate, no early break
                j++
  res = m ? i : res                          ;; branchless Select; first match only
  i++
return res

Control flow is flat-safe — there is no Br out of an If. The inner loop AND-accumulates the match over all nlen bytes (rather than breaking early), the outer loop’s two exits are top-of-loop BrIf`s, and the result update is a branchless `Select. Because the outer loop exits on res != -1 at the top of the next iteration, res keeps the FIRST match. For nlen = 0 the inner loop runs zero times (m stays 1) and the first outer iteration sets res = 0, matching the fixed oracle; for nlen > hlen the bound is negative so the outer loop exits immediately with res = -1.

Gate evidence

Gate 1 — builds

dune build bin/main.exe exit 0.

Gate 2 — parity (wasm vs interpreter oracle)

Same inputs through both backends agree across found / not-found / first-occurrence / needle-longer / empty-needle / empty-haystack. Interp oracle (post-fix) confirmed against the real library API; wasm executed under Node.

Expression interp wasm

string_find("hello", "ll")

2

2

string_find("hello", "o")

4

4

string_find("hello", "xyz")

-1

-1

string_find("abcabc", "bc") (first occ)

1

1

string_find("hello", "hellox") (longer)

-1

-1

string_find("hello", "") (was a crash)

0

0

string_find("", "x") (empty haystack)

-1

-1

string_find("", "") (both empty)

0

0

The packed fixture tests/codegen/string_find.affine returns 73811 (each result +1 packed as a 4-bit nibble); both backends produce it.

Tests added

  • test/test_e2e.ml — group "E2E String-wall slice 6 (string_find)": seven interp-oracle cases, including the empty-needle case that previously crashed the interpreter. Runs under dune runtest.

  • tests/codegen/string_find.affine + tests/codegen/test_string_find.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-6 string harnesses), no sibling regressions.

Corpus impact

Substring search (delimiter detection, contains-style predicates, simple parsing) now lowers to wasm. With slices 1-6, every name-dispatched string builtin with a faithful trap-free wasm analogue is lowered: string_length, string_char_code_at, char_to_int, string_from_char_code, string_sub, to_lowercase, to_uppercase, trim, string_find.

What remains (and the decision still pending)

  • int_to_string / float_to_string — name-dispatched decimal rendering. int_to_string is the obvious next autonomous slice (digit loop + sign; INT_MIN is the one i32 edge — handle it by extracting digits in negative space to avoid the un-negatable magnitude). float_to_string needs the float story, so it stays host-side under the float-wall convention.

  • Concatenation (` / `OpConcat`) and polymorphic `slice`* — still gated on the *type-access* design decision (`lib/codegen.ml` has no per-expression type information; ` already lowers to *list concat). Owner call: thread typed-AST into codegen, or add a dedicated string_concat builtin. See proposals/EVIDENCE-stringwall-slice5.adoc §"remaining string ops".

  • string_get / int_to_char — deferred (raise on out-of-range; no trap-free wasm analogue without a declared-clamp convention).

Next slices (variable-string backend wall)

  1. int_to_string — decimal rendering (autonomous; the last clean name-dispatched op).

  2. Concatenation / slice — gated on the type-access design decision.

Then the effect-codegen wall (module-state / Date.now / Console.log).