Skip to content

Commit bd2da57

Browse files
ZOOWHZOOWH
authored
Merge 59b8f92 into e80e8a2 
2 parents e80e8a2 + 59b8f92 commit bd2da57

2 files changed

Lines changed: 251 additions & 7 deletions

File tree

‎src/agents/sessions/tools/edit-diff.test.ts‎

Lines changed: 100 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,100 @@
1+
import { describe, expect, it } from "vitest";
2+
import { applyEditsToNormalizedContent, normalizeToLF } from "./edit-diff.js";
3+
4+
function getMismatchMessage(
5+
content: string,
6+
edits: Array<{ oldText: string; newText: string }>,
7+
): string {
8+
try {
9+
applyEditsToNormalizedContent(normalizeToLF(content), edits, "test.ts");
10+
} catch (error) {
11+
return error instanceof Error ? error.message : String(error);
12+
}
13+
throw new Error("Expected edit mismatch");
14+
}
15+
16+
describe("applyEditsToNormalizedContent", () => {
17+
it("shows the closest matching line with expected, found, and difference marker", () => {
18+
const message = getMismatchMessage(
19+
"line one\nthis is a test line\nanother line here\nconst value = 42;\nfinal line\n",
20+
[{ oldText: "const value = 99;", newText: "" }],
21+
);
22+
23+
expect(message).toMatch(/near line 4 \(\d+% match\)/);
24+
expect(message).toContain('expected: "const value = 99;"');
25+
expect(message).toContain('found: "const value = 42;"');
26+
expect(message).toMatch(/\^{1,12}/);
27+
});
28+
29+
it("shows up to 3 best candidates sorted by similarity", () => {
30+
const message = getMismatchMessage(
31+
"function alpha() {}\nfunction beta() {}\nfunction bet() {}\nfunction delta() {}\n",
32+
[{ oldText: "function betaa() {}", newText: "" }],
33+
);
34+
35+
expect(message.match(/near line/g)).toHaveLength(3);
36+
expect(message.indexOf("near line 2")).toBeLessThan(message.indexOf("near line 3"));
37+
});
38+
39+
it("uses the most meaningful oldText line for multiline diagnostics", () => {
40+
const message = getMismatchMessage("header\nconst actualValue = 42;\nfooter\n", [
41+
{ oldText: "x\nconst actualValue = 99;\n", newText: "" },
42+
]);
43+
44+
expect(message).toContain("near line 2");
45+
expect(message).toContain('expected: "const actualValue = 99;"');
46+
});
47+
48+
it("calls out indentation differences", () => {
49+
const message = getMismatchMessage(" const value = 42;\n", [
50+
{ oldText: " const value = 42;", newText: "" },
51+
]);
52+
53+
expect(message).toContain("indentation differs (expected 12 spaces, found 6 spaces)");
54+
});
55+
56+
it("calls out escaping differences", () => {
57+
const message = getMismatchMessage('const pattern = "\\bword\\b";\n', [
58+
{ oldText: 'const pattern = "\\\\bword\\\\b";', newText: "" },
59+
]);
60+
61+
expect(message).toContain("escaping differs (expected 4 backslashes, found 2)");
62+
});
63+
64+
it("omits candidates below the similarity threshold", () => {
65+
const message = getMismatchMessage("abc\nxyz\n123\n", [
66+
{ oldText: "completely different text here", newText: "" },
67+
]);
68+
69+
expect(message).toContain("Could not find the exact text");
70+
expect(message).not.toContain("Closest matching lines");
71+
});
72+
73+
it("bounds candidate scanning and displayed line length", () => {
74+
const content = `${Array.from({ length: 1000 }, () => "unrelated").join("\n")}\n${"x".repeat(
75+
200_000,
76+
)}const value = 42;`;
77+
const message = getMismatchMessage(content, [{ oldText: "const value = 99;", newText: "" }]);
78+
79+
expect(message).not.toContain("const value = 42");
80+
expect(message.length).toBeLessThan(1000);
81+
});
82+
83+
it("does not split surrogate pairs at the displayed line boundary", () => {
84+
const message = getMismatchMessage(`${"x".repeat(119)}🙂found\n`, [
85+
{ oldText: `${"x".repeat(119)}🙂expected`, newText: "" },
86+
]);
87+
88+
expect(message).toContain("Closest matching lines");
89+
expect(message).not.toContain("\\ud83d");
90+
});
91+
92+
it("includes candidate hints for multi-edit failures", () => {
93+
const message = getMismatchMessage("alpha\nbeta\ngamma\n", [
94+
{ oldText: "alpha", newText: "A" },
95+
{ oldText: "bta", newText: "B" },
96+
]);
97+
98+
expect(message).toMatch(/Could not find edits\[1\][\s\S]*near line 2/);
99+
});
100+
});

‎src/agents/sessions/tools/edit-diff.ts‎

Lines changed: 151 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -6,6 +6,7 @@
66
import { constants } from "node:fs";
77
import { access, readFile } from "node:fs/promises";
88
import * as Diff from "diff";
9+
import { levenshteinDistance } from "../../../shared/levenshtein-distance.js";
910
import { resolveToCwd } from "./path-utils.js";
1011

1112
export function detectLineEnding(content: string): "\r\n" | "\n" {
@@ -255,14 +256,157 @@ function countOccurrences(content: string, oldText: string): number {
255256
return fuzzyContent.split(fuzzyOldText).length - 1;
256257
}
257258

258-
function getNotFoundError(path: string, editIndex: number, totalEdits: number): Error {
259-
if (totalEdits === 1) {
260-
return new Error(
261-
`Could not find the exact text in ${path}. The old text must match exactly including all whitespace and newlines.`,
262-
);
259+
const EDIT_CANDIDATE_LIMIT = 3;
260+
const EDIT_CANDIDATE_MAX_LINES = 1000;
261+
const EDIT_CANDIDATE_MAX_SCAN_CHARS = 128 * 1024;
262+
const EDIT_CANDIDATE_MAX_LINE_CHARS = 120;
263+
const EDIT_CANDIDATE_MIN_SCORE = 0.45;
264+
265+
interface EditCandidate {
266+
lineNumber: number;
267+
line: string;
268+
score: number;
269+
}
270+
271+
function truncateCandidateText(text: string, maxChars: number): string {
272+
if (text.length <= maxChars) {
273+
return text;
274+
}
275+
const cut =
276+
maxChars > 0 &&
277+
/[\uD800-\uDBFF]/.test(text[maxChars - 1]) &&
278+
/[\uDC00-\uDFFF]/.test(text[maxChars])
279+
? maxChars - 1
280+
: maxChars;
281+
return text.slice(0, cut);
282+
}
283+
284+
function getBoundedLines(text: string, maxLines: number, maxScanChars: number): string[] {
285+
return truncateCandidateText(text, maxScanChars)
286+
.split("\n", maxLines)
287+
.map((line) => truncateCandidateText(line, EDIT_CANDIDATE_MAX_LINE_CHARS));
288+
}
289+
290+
function scoreCandidate(expected: string, candidate: string): number {
291+
const normalizedExpected = expected.trim();
292+
const normalizedCandidate = candidate.trim();
293+
const maxLength = Math.max(normalizedExpected.length, normalizedCandidate.length);
294+
if (maxLength === 0) {
295+
return 0;
296+
}
297+
298+
// Length alone sets an upper bound on the possible similarity score.
299+
if (
300+
Math.min(normalizedExpected.length, normalizedCandidate.length) / maxLength <
301+
EDIT_CANDIDATE_MIN_SCORE
302+
) {
303+
return 0;
304+
}
305+
306+
return 1 - levenshteinDistance(normalizedExpected, normalizedCandidate) / maxLength;
307+
}
308+
309+
function describeIndentation(line: string): string {
310+
const indentation = line.match(/^[ \t]*/)?.[0] ?? "";
311+
if (!indentation) {
312+
return "none";
313+
}
314+
const tabs = indentation.match(/\t/g)?.length ?? 0;
315+
const spaces = indentation.length - tabs;
316+
return tabs === 0 ? `${spaces} spaces` : `${spaces} spaces and ${tabs} tabs`;
317+
}
318+
319+
function firstDifferenceIndex(left: string, right: string): number {
320+
const sharedLength = Math.min(left.length, right.length);
321+
for (let index = 0; index < sharedLength; index++) {
322+
if (left[index] !== right[index]) {
323+
return index;
324+
}
263325
}
326+
return left.length === right.length ? -1 : sharedLength;
327+
}
328+
329+
function describeCandidateDifference(expected: string, found: string): string {
330+
const expectedIndentation = expected.match(/^[ \t]*/)?.[0] ?? "";
331+
const foundIndentation = found.match(/^[ \t]*/)?.[0] ?? "";
332+
if (expectedIndentation !== foundIndentation) {
333+
return `indentation differs (expected ${describeIndentation(expected)}, found ${describeIndentation(found)})`;
334+
}
335+
336+
const expectedBackslashes = expected.match(/\\/g)?.length ?? 0;
337+
const foundBackslashes = found.match(/\\/g)?.length ?? 0;
338+
if (expectedBackslashes !== foundBackslashes) {
339+
return `escaping differs (expected ${expectedBackslashes} backslashes, found ${foundBackslashes})`;
340+
}
341+
342+
const differenceIndex = firstDifferenceIndex(expected, found);
343+
return differenceIndex === -1
344+
? "this line matches; surrounding lines differ"
345+
: `first difference at column ${differenceIndex + 1}`;
346+
}
347+
348+
function getCandidateHint(content: string, oldText: string): string {
349+
const expected = getBoundedLines(oldText, 32, 4096).reduce(
350+
(best, line) => (line.trim().length > best.trim().length ? line : best),
351+
"",
352+
);
353+
if (!expected.trim()) {
354+
return "";
355+
}
356+
const candidates = getBoundedLines(
357+
content,
358+
EDIT_CANDIDATE_MAX_LINES,
359+
EDIT_CANDIDATE_MAX_SCAN_CHARS,
360+
)
361+
.map((line, index): EditCandidate | undefined => {
362+
const score = scoreCandidate(expected, line);
363+
return score >= EDIT_CANDIDATE_MIN_SCORE ? { lineNumber: index + 1, line, score } : undefined;
364+
})
365+
.filter((candidate): candidate is EditCandidate => candidate !== undefined)
366+
.toSorted((left, right) => right.score - left.score || left.lineNumber - right.lineNumber)
367+
.slice(0, EDIT_CANDIDATE_LIMIT);
368+
if (candidates.length === 0) {
369+
return "";
370+
}
371+
const expectedDisplay = JSON.stringify(expected);
372+
return (
373+
"\nClosest matching lines:\n" +
374+
candidates
375+
.map((candidate) => {
376+
const foundDisplay = JSON.stringify(candidate.line);
377+
const differenceIndex = firstDifferenceIndex(expectedDisplay, foundDisplay);
378+
const markerIndex =
379+
differenceIndex === -1
380+
? Math.min(expectedDisplay.length, foundDisplay.length)
381+
: differenceIndex;
382+
const markerWidth = Math.max(
383+
1,
384+
Math.min(12, Math.max(expectedDisplay.length, foundDisplay.length) - markerIndex),
385+
);
386+
return [
387+
` near line ${candidate.lineNumber} (${Math.round(candidate.score * 100)}% match):`,
388+
` expected: ${expectedDisplay}`,
389+
` found: ${foundDisplay}`,
390+
` ${" ".repeat(markerIndex)}${"^".repeat(markerWidth)}`,
391+
` hint: ${describeCandidateDifference(expected, candidate.line)}`,
392+
].join("\n");
393+
})
394+
.join("\n")
395+
);
396+
}
397+
398+
function getNotFoundError(
399+
path: string,
400+
editIndex: number,
401+
totalEdits: number,
402+
content: string,
403+
oldText: string,
404+
): Error {
405+
const prefix =
406+
totalEdits === 1 ? "Could not find the exact text" : `Could not find edits[${editIndex}]`;
407+
const hint = getCandidateHint(content, oldText);
264408
return new Error(
265-
`Could not find edits[${editIndex}] in ${path}. The oldText must match exactly including all whitespace and newlines.`,
409+
`${prefix} in ${path}. The old text must match exactly including all whitespace and newlines.${hint}`,
266410
);
267411
}
268412

@@ -336,7 +480,7 @@ export function applyEditsToNormalizedContent(
336480
const edit = normalizedEdits[i];
337481
const matchResult = fuzzyFindText(replacementBaseContent, edit.oldText);
338482
if (!matchResult.found) {
339-
throw getNotFoundError(path, i, normalizedEdits.length);
483+
throw getNotFoundError(path, i, normalizedEdits.length, normalizedContent, edit.oldText);
340484
}
341485

342486
const occurrences = countOccurrences(replacementBaseContent, edit.oldText);

0 commit comments

Comments
 (0)