Skip to content

Commit bf689d7

Browse files
cliffhallclaude
andcommitted
fix(filesystem): budget the closest-text search and score windows at EOF
Copilot round 1 on #5379. The search's guard counted line comparisons, but each comparison walks every distinct bigram of an oldText line, so it now budgets bigram lookups. Starting positions near the end of the file, where fewer lines than oldText has remain, are now scored, and the file's terminal newline lines up with oldText's, so a near match at the end of the file is found. Co-Authored-By: Claude Opus 5.5 <[email protected]> Signed-off-by: cliffhall <[email protected]>
1 parent c9e110b commit bf689d7

2 files changed

Lines changed: 71 additions & 25 deletions

File tree

‎src/filesystem/__tests__/edit-file-mismatch.test.ts‎

Lines changed: 30 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -137,9 +137,36 @@ describe("describeEditMismatch", () => {
137137
expect(message).not.toContain("Closest text");
138138
});
139139

140-
it("handles an empty file", () => {
140+
it("says so for an empty file", () => {
141141
const message = describeEditMismatch("", "x", 0, 1);
142-
expect(message).toContain("No line of the file resembles oldText.");
142+
expect(message).toContain("The file is empty.");
143+
expect(message).not.toContain("Closest text");
144+
});
145+
146+
it("finds a near match that ends at the end of the file", () => {
147+
const message = describeEditMismatch(
148+
"header\nalpha\nbeta\n",
149+
"alpha\nbeta\ngamma",
150+
0,
151+
1,
152+
);
153+
expect(message).toContain(
154+
"(lines 1-3 of 3):\n1: header\n2: alpha\n3: beta",
155+
);
156+
expect(message).toContain(
157+
'oldText line 3 ("gamma") runs past the end of the file, which ends at line 3.',
158+
);
159+
});
160+
161+
it("lines up a terminal newline in oldText with the file's", () => {
162+
const content = "function f() {\n return name;\n}\n";
163+
const message = describeEditMismatch(content, "return naem;\n}\n", 0, 1);
164+
expect(message).toContain("(lines 1-3 of 3):");
165+
expect(message).toContain(
166+
"oldText line 1 against file line 2:\n" +
167+
' oldText: "return naem;"\n' +
168+
' file: " return name;"',
169+
);
143170
});
144171

145172
it("caps the quoted region at 30 lines", () => {
@@ -158,7 +185,7 @@ describe("describeEditMismatch", () => {
158185
const message = describeEditMismatch(content, oldText, 1, 3);
159186
expect(message).toContain("edit 2 of 3");
160187
expect(message).toContain(
161-
"The file has 2000 lines, too many to search for the closest text.",
188+
"The file has 2000 lines, too many to search for the closest text to this oldText.",
162189
);
163190
expect(message).not.toContain("Closest text");
164191
});

‎src/filesystem/lib.ts‎

Lines changed: 41 additions & 22 deletions
Original file line numberDiff line numberDiff line change
@@ -733,10 +733,10 @@ function reindentLine(
733733
// differs from the file in a way the matcher does not tolerate (whitespace
734734
// inside a line, a typo, stale content) needs the file's real text to retry
735735
// with, so the error quotes the closest run of lines with their line
736-
// numbers. Finding it compares every window of the file against oldText, so
737-
// the search is skipped past a fixed number of line comparisons rather than
738-
// stalling the error on a huge file.
739-
const MISMATCH_SCAN_LIMIT = 1_000_000;
736+
// numbers. Finding it compares oldText against the lines at every position
737+
// of the file, so it is skipped past a fixed budget of bigram lookups rather
738+
// than stalling the error on a huge file or a huge oldText.
739+
const MISMATCH_WORK_LIMIT = 10_000_000;
740740
const MISMATCH_CONTEXT_LINES = 2;
741741
const MISMATCH_MAX_REGION_LINES = 30;
742742

@@ -783,10 +783,15 @@ export function describeEditMismatch(
783783
editCount: number,
784784
): string {
785785
const oldLines = normalizeLineEndings(oldText).split("\n");
786+
// The lines as the matcher sees them, so a terminal newline in oldText
787+
// lines up with the file's. The empty element after a terminal newline is
788+
// not a line of the file, so it is left out of what is counted and shown.
786789
const fileLines = content.split("\n");
787-
if (fileLines.length > 1 && fileLines[fileLines.length - 1] === "") {
788-
fileLines.pop();
789-
}
790+
const lineCount = content.endsWith("\n")
791+
? fileLines.length - 1
792+
: content === ""
793+
? 0
794+
: fileLines.length;
790795

791796
const parts = [
792797
`Could not find exact match for edit ${editIndex + 1} of ${editCount}. ` +
@@ -796,21 +801,30 @@ export function describeEditMismatch(
796801
`oldText:\n${oldText}`,
797802
];
798803

799-
const width = Math.min(oldLines.length, fileLines.length);
800-
const windows = fileLines.length - width + 1;
801-
if (windows * width > MISMATCH_SCAN_LIMIT) {
804+
if (lineCount === 0) {
805+
parts.push("The file is empty.");
806+
return parts.join("\n\n");
807+
}
808+
809+
const oldGrams = oldLines.map(lineGrams);
810+
let oldWork = 0;
811+
for (const line of oldGrams) oldWork += line.grams.size + 1;
812+
if (fileLines.length * oldWork > MISMATCH_WORK_LIMIT) {
802813
parts.push(
803-
`The file has ${fileLines.length} lines, too many to search for the ` +
804-
"closest text. Read the file and copy oldText from it exactly.",
814+
`The file has ${lineCount} lines, too many to search for the closest ` +
815+
"text to this oldText. Read the file and copy oldText from it exactly.",
805816
);
806817
return parts.join("\n\n");
807818
}
808819

809-
const oldGrams = oldLines.map(lineGrams);
820+
// Every starting line is scored, including those near the end where fewer
821+
// lines than oldText has remain, so a near match at the end of the file is
822+
// still found. The earliest start wins a tie.
810823
const fileGrams = fileLines.map(lineGrams);
811824
let best = 0;
812825
let bestScore = 0;
813-
for (let i = 0; i < windows; i++) {
826+
for (let i = 0; i < fileLines.length; i++) {
827+
const width = Math.min(oldLines.length, fileLines.length - i);
814828
let score = 0;
815829
for (let j = 0; j < width; j++) {
816830
score += lineSimilarity(oldGrams[j], fileGrams[i + j]);
@@ -829,10 +843,13 @@ export function describeEditMismatch(
829843
return parts.join("\n\n");
830844
}
831845

832-
const start = Math.max(0, best - MISMATCH_CONTEXT_LINES);
846+
const start = Math.min(
847+
Math.max(0, best - MISMATCH_CONTEXT_LINES),
848+
lineCount - 1,
849+
);
833850
const end = Math.min(
834-
fileLines.length,
835-
best + width + MISMATCH_CONTEXT_LINES,
851+
lineCount,
852+
best + oldLines.length + MISMATCH_CONTEXT_LINES,
836853
start + MISMATCH_MAX_REGION_LINES,
837854
);
838855
const numbered = fileLines
@@ -841,22 +858,24 @@ export function describeEditMismatch(
841858
const after = editIndex > 0 ? ", after the earlier edits in this call" : "";
842859
parts.push(
843860
`Closest text in the file (lines ${start + 1}-${end} of ` +
844-
`${fileLines.length}${after}):\n${numbered.join("\n")}`,
861+
`${lineCount}${after}):\n${numbered.join("\n")}`,
845862
);
846863

847864
// Some line differs beyond leading and trailing whitespace, or oldText runs
848865
// past the file's end: otherwise the line-by-line matcher would have
849-
// matched this window. Math.max only keeps the index a valid one.
866+
// matched here. Math.max only keeps the index a valid one.
850867
const differs = Math.max(
851868
0,
852869
oldLines.findIndex(
853-
(line, j) => j >= width || line.trim() !== fileLines[best + j].trim(),
870+
(line, j) =>
871+
best + j >= fileLines.length ||
872+
line.trim() !== fileLines[best + j].trim(),
854873
),
855874
);
856875
parts.push(
857-
differs >= width
876+
best + differs >= lineCount
858877
? `oldText line ${differs + 1} (${JSON.stringify(oldLines[differs])}) ` +
859-
`runs past the end of the file, which ends at line ${fileLines.length}.`
878+
`runs past the end of the file, which ends at line ${lineCount}.`
860879
: `First difference, oldText line ${differs + 1} against file line ` +
861880
`${best + differs + 1}:\n` +
862881
` oldText: ${JSON.stringify(oldLines[differs])}\n` +

0 commit comments

Comments
 (0)