Incremental tokenizer + link-ref scan to reach true O(n) streaming (limitation K)

[jonathanKingston]

Type: performance · Area: src/block-tokenizer.ts, src/link-references.ts, src/streaming*.ts · Follow-up to #21 / #23

Summary

After #23 the committed-prefix DOM work is O(tail) per commit, but two pure-string scans remain O(prefix) per update (issue #21 limitation K):

• tokenizeBlocks(content) — every update, in splitForStreaming.
• parseLinkReferenceDefinitions(complete) — every commit, in FrozenTailRenderer.update.

So total streaming cost is still Θ(n²). Measured share of wall-clock (jsdom, plain prose, fixed chunk): ~4% at 9 KB, ~17% at 37 KB, ~32% at 74 KB — negligible for typical messages, dominant for very large ones.

Approach — resume from an index, don't re-scan the prefix

content is append-only (the raw stream only grows), and the frozen boundary is always a clean top-level block boundary where the tokenizer carries no open-block state. So both scans can resume from a saved offset:

• Tokenizer: cache the token array + a resumeOffset (the last settled top-level boundary — the same "settled" property settledTailStart/tokenStraddles already compute), re-tokenize only content[resumeOffset:], and splice. Safe because a suffix tokenized in isolation from a clean boundary is byte-identical to tokenizing the whole and slicing (the same property Layer 2 already relies on).
• Link-refs: accumulate the map incrementally — keep [0, resumeOffset), scan only the suffix per commit, merge with first-definition-wins (add a label only if absent) to preserve CommonMark semantics. The forward-reference fallback still fires (a genuinely new def appears in the suffix).

Result: per-update work becomes O(tail); total streaming is genuinely Θ(n).

Caveats / prior art

• More invasive than perf(streaming): incremental committed-prefix rendering (fixes #21) #23 — adds a resume mode to tokenizeBlocks and threads a small cache (offset + token array + partial ref map). Do it parity-first behind the same convergence-fuzz safety net.
• The perf(streaming): incremental committed-prefix rendering (fixes #21) #23 review already caught the failure mode this must defend against: a non-append-only rewrite (message regeneration/edit) invalidates a resumed cache. Reuse the frozenSource startsWith guard added in that fix — if content is no longer a prefix of what was cached, reset and re-scan.

Acceptance

• Per-update tokenize + link-ref cost is O(tail), not O(prefix), across the benched range; add a scaling case at ≥100 KB where these scans currently dominate.
• Byte-identical output; exhaustive convergence fuzz passes; in-place-rewrite guard test passes.

References

• src/streaming-frozen-tail.ts header (limitation K), frozenSource guard
• src/block-tokenizer.ts — tokenizeBlocks, streamingHoldStart
• src/link-references.ts — parseLinkReferenceDefinitions