# Suffix matching and segment planning

## Scope, sources and deliberate changes

This stage implements private `longest_match` and `select_segments`. There is no public diff, residual-byte generation, compressed patch assembly or CLI. The caller supplies one suffix array from Commit 7 and reuses it for all queries. The trusted index must describe the same immutable old Bytes in unsigned lexicographic order and include the empty suffix. Query entry validates index count/query position, and each examined suffix position is checked before indexing. Sortedness/permutation are not revalidated for every query; construction is the internal caller's responsibility.

BSDiff 4.3 bsdiff.c was read from the existing cache and SHA-256 reverified as fc0a6e634ef77dcf14bf36c7b6d1e57ba1ac5c4809073dfaacb3b5f7ab277eb7. `matchlen`/`search` motivate the query; the main scan's oldscore/scsc, Sf/lenf, Sb/lenb and Ss/lens correspond to rolling offset score, forward_choice, backward_choice and overlap_cut. The scan threshold remains eight. Complete Colin Percival copyright and BSD-2-Clause notice are retained in both derived MoonBit files and tools/oracle/BSDIFF-LICENSE.txt. No other implementation's code was adopted.

One intentional search change is required by the longest-match contract. Upstream memcmp compares only the minimum remaining length, so a shorter prefix suffix compares equal. Static trace: for old=aaaa and query=aaaa, sorted positions [4,3,2,1,0], the original search narrows through aa and a to the empty/a endpoints, yielding length one rather than four. This is a source-level trace, not a new C oracle execution. Our lower_bound compares complete suffix/query lexicographic order, using remaining lengths after equal prefix bytes. The maximum LCP is then among the predecessor and successor. The predecessor is considered first; the right/lower_bound candidate wins an equal length if present. This is deterministic, not a smallest-old-position rule. Examples: aaaa/aaaa selects (0,4); aaaa/a selects (3,1); abcabc/abc selects (3,3). No slices or suffix copies are made by the library query.

## Scan state, scoring and coverage

`scan` is the next query position, `length` its most recent match length, and `last_scan` the start of the still-unemitted new interval. `last_pos` is the old cursor at that interval start. `offset=pos-scan` identifies the previous selected alignment. The rolling old_score adds matches at that alignment through a monotone scored endpoint, and removes the departing scan byte when scanning advances. It follows the reference heuristic, not a globally optimal patch-size search. A query stops scanning when its nonzero match equals old_score or exceeds old_score+8. Otherwise scan advances one byte. At the next outer iteration the previous match length is skipped.

Forward and backward choices maximize 2*equal_bytes - span_length, including the zero-length choice; strict improvement keeps the earliest/shortest maximizing length. This permits a selected diff interval to contain unequal bytes and future nonzero residuals. For overlapping front/back spans, the cut maximizes front-prefix agreements plus back-suffix agreements; the earliest maximizing cut is used. The incremental overlap score adds a front agreement and subtracts a back agreement. Example front abXX / back YYcd against abcd assigns two bytes to each; identical alternatives choose cut zero.

A DiffSegment records new_start, old_start, diff_length, extra_length and Int64 seek. Its new interval is [last_scan, scan-back): front bytes use old_start, the rest are literal extra. Then last_scan becomes scan-back. Overlap is split before emission, ensuring nonnegative lengths and no new-byte overlap or gap. The seek equals (pos-back) - (last_pos+front), so applying diff_length then seek reaches the next segment's old_start. It may be negative. All generated old starts are within the old buffer, unlike the broader out-of-range cursor semantics accepted by apply.

Initially the uncovered boundary is zero; final emission has scan=new length and back=0, so coverage ends exactly at the new length. Empty target returns an empty plan. Empty old data becomes a legitimate extra-only plan. Zero-output cursor-adjustment segments can occur (the block-move vector begins with one); they are not blanket-rejected. If an outer iteration does not advance scan, length must be positive and the next iteration skips it. A defensive scan_progress error rejects a zero-length/no-progress state. The finite shared work quota additionally bounds every metered loop.

## Numeric checks, growth and work

All raw positions are Int32 and bounded by explicit remaining lengths. Search uses lo+(hi-lo)/2. LCP positions add an index only while below both remaining lengths. A matched length is <= new length - scan, so scan+length is representable. Forward limits give last_scan+front<=scan and last_pos+front<=old length. Backward limits give back<=scan-last_scan and back<=pos. Overlap is computed by subtracting the gap before adding any lengths; front is reduced by overlap-cut and back by cut. Hence all overlap read ranges lie in their input buffers.

Scores, 2*score-length, old offsets and seeks use Int64. Rolling score has at most input-length additions/removals per outer scan, so even score+8 fits Int64. Byte-alignment checks add an Int32 position to an offset formed from two Int32 positions in Int64, test the resulting old range, then narrow. Seeks convert operands before subtraction/addition. No negation of an arbitrary extreme cursor is used.

The segment cap is an explicit internal 0..2147483647 value, checked before each Array push; zero permits an empty plan only. Segment storage is O(number of emitted segments), bounded by this caller-selected cap, with no residual/extra payload copies. Queries use O(1) extra storage and worst-case O((L+1)*log(n+1)) byte work, with L=min(old length, new length-query position); repeated long prefixes can be costly. This stage does not promise optimal or uniformly fast matching.

MatchBudget is a separate explicit mutable counter, not Limits::for_apply's unmeasured match placeholder. Negative initial values are invalid; zero is exhausted. One unit is deducted before each binary-search iteration, LCP/order byte inspection, alignment score attempt, forward/backward/overlap iteration, outer/inner scan iteration, and segment push. An overlap iteration can perform two byte comparisons for its one logical unit. The same object is passed throughout a scan and across queries, never reset by search. Already spent work remains spent on failure. This is an algorithmic progress quota, not every machine operation, whole-process CPU/time or peak-memory protection. SortBudget's existing separate contract is unchanged. Full generating-call accumulation and defaults remain for Commit 11.

## Independent evidence

The MoonBit test-only naive matcher enumerates every old position including the empty suffix and directly computes byte LCPs. It checks maximum length and that the returned position actually realizes it, without forcing positions for uncontracted ties. Explicit tests assert the deterministic ties above and the shorter-prefix correction. Small forward/backward/overlap cases have manually calculated scores and cuts.

`testdata/matching/segments.json` fixes three complete plans: actual overlap, block move, and entirely unmatched data. `scripts/check_matching_vectors.py` independently reconstructs them with Python byte sorting and exhaustive evaluation of every forward/backward length and overlap cut. The generated white-box tests compare every segment field. Formatting-only whitespace/trailing commas are tolerated, but literal tokens remain checked. The overlap vector exercises one actual overlap and yields [(0,0,14,0,15),(14,29,11,0,-9)]. The block move reuses all 64 bytes with an initial zero-output seek and a subsequent -64 seek. The unmatched vector has exactly one four-byte extra-only segment.

Complete scanning tests also inspect old/new ranges, every segment boundary, cursor transitions, total coverage, and deterministic repeats; they do not reconstruct every output byte from new input and call that matching evidence. Identical data selects one all-diff segment. A one-byte replacement in a 62-byte input reuses at least 50 diff bytes and explicitly includes unequal-byte residual positions. Insertion, deletion, prepend/append, truncation, repetition, long prefixes and binary 00/ff are represented. Input and index snapshots, different interleaved calls and failed-budget recovery are checked.

Native finite enumeration uses all 31 strings of length 0..4 over {00,ff}: 961 old/new pairs, 3999 position queries (including ends), and 961 coverage checks. Random validation uses 64 pairs, old length i/new length 63-i, using the existing UInt32 LCG with seeds 20261107+i / 20261108+i; every query is checked naively. Repetition cases are 256/2048/8192 A bytes followed by an inserted B and must reuse exactly the whole old input.

## Toolchain restoration and validation

Actual starting HEAD: f906ee5d29cce496365b9c9c9c3590cdb3c4bb49, master, clean. The old temporary compiler files were missing. The global compiler (0.10.13) was detected during inventory and not used for project validation. Restored the exact toolchain into ignored _build/toolchain-0.10.19 from https://cli.moonbitlang.com/binaries/0.10.19%2Bbee578715/moonbit-windows-x86_64.zip and matching encoded core URL. The binary zip matched both its published checksum and the earlier SHA-256 13dcc26ff3009e93da4d3bdb2f41a9961179d60a621f1b8c56fecea24d6cdf96; core zip hash is 218da5676a8cc0070dd171ae957997eadc8e840b42404af2dda197f513361ba8. Literal + version URLs returned 403, and a changed latest archive was refused. The restored compiler reports moon 0.1.20261102 (ea07287 2026-11-02), moonc v0.10.19+bee578715 (2026-11-02), moonrun 0.1.20261102 (ea07287 2026-11-02). The isolated registry/core bundle were initialized; dependency resolution remains moonzip 0.3.5, moonbase 0.4.2, mooncrypt 0.4.7, moondate/moonseed 0.1.0. Global installation unchanged.

Set MOON_HOME to the restored absolute directory and prepend its bin to PATH; initialize MSVC for Windows native. Commands:

```sh
python scripts/check_matching_vectors.py
moon test matching_wbtest.mbt matching_vectors_wbtest.mbt --target native --deny-warn
moon test matching_wbtest.mbt matching_vectors_wbtest.mbt --filter 'matching-compact*' --target wasm-gc --deny-warn
moon test suffix_array_wbtest.mbt --filter 'suffix-compact*' --target native --deny-warn
```

2026-11-07 results: native matching 9/9, native compact suffix regression 5/5, Wasm-GC compact matching 7/7. JS initially passed the four compact tests, then the seven-test compact group after complete vector addition. A subsequent development command also ran all nine tests on JS (including the two native-labelled enumeration/repetition tests), 9/9 passed; after adding further state/budget assertions, the affected state test was rerun on JS and passed 1/1. These repeated runs do not increase independent case counts.

moon info/fmt/fmt --check, native check --deny-warn/build and git diff --check passed. The root .mbti remains unchanged. CI adds offline independent-vector checks and compact JS/Wasm-GC matching with nonzero-test checks; the existing native full suite discovers all nine new tests. Remote CI has not run. No apply/large-compression matrix, C oracle rebuild, upstream patch regeneration, historical probe, resource measurement or formal performance benchmark was rerun. No public diff or patch assembly is claimed.