perf(runtime): avoid quadratic prefix rescans in fuzzy Edit matching #6049

What happened

Edit's line-trimmed fallback recomputes the character offset of each matching candidate by summing every preceding line. A repetitive file within the existing fuzzy limits therefore takes quadratic prefix work merely to reject an ambiguous edit. At 49,000 lines (686,000 UTF-16 units), the current implementation performs about 1.2 billion prefix additions before returning its expected ambiguity error.

This helper is used by filesystem-executor.ts and the filesystem worker's Edit operation. This is unnecessary CPU and Edit latency; I am not claiming a renderer hang or incorrect replacement.

How to reproduce

From a checkout of 2463d86c3, using Node 24.18.1:

node --input-type=module <<'JS'
import { computeEditedSource } from './packages/runtime/src/edit-replace.ts';
for (const lines of [1_000, 10_000, 30_000, 49_000]) {
  const source = '  repeated();\n'.repeat(lines);
  const start = performance.now();
  try {
    computeEditedSource(source, 'repeated();  ', 'next();', 'fixture.ts');
  } catch (error) {
    console.log(lines, performance.now() - start, error.message);
  }
}
JS

The trailing spaces in old_string make exact matching fail; all source lines then match the line-trimmed fallback. The 1,000,000-character / 50,000-line guards admit the fixture.

Ten measured calls per size and version (five per process after two warm-ups), in fresh processes ordered after/before/before/after on the same machine:

These are synthetic helper measurements, not end-to-end application timings. Both versions return the same ambiguity error. At 49,000 lines, median process CPU time is 653.61 ms before and 5.52 ms after.

Expected / proposed change

Advance one source offset while traversing lines, including non-matching lines, instead of rescanning each candidate's prefix. Keep the existing fuzzy limits, strategy order, candidate enumeration, ambiguity rejection, newline handling, and reported line ranges unchanged. This removes the quadratic offset calculation; it does not claim that every fuzzy strategy becomes linear for every query.

Validation prepared locally: the added CPU-budget regression fails on current main (2.69 CPU seconds for four edits) and passes with incremental offsets; 18,000 seeded before/after cases have identical results or error messages, including Unicode, mixed line endings, multiline snippets, and EOF cases.

Environment

• Maka: main 2463d86c386c6bafc483b3d838f3014f4fc9b664
• OS: macOS, arm64
• Node: 24.18.1
• Surface: Runtime Edit matching helper used by local and worker filesystem executors

Additional context

Searched existing issue/PR titles and bodies for lineTrimmedSpans, edit-replace, fuzzy editing, and quadratic Edit work; no overlapping open implementation was found. #5590 improved exact-match ambiguity handling; this is the separate remaining prefix rescan in the fuzzy path.

Automated report and local implementation by OpenAI Codex at @seekskyworld's direction.