Skip to content

Commit ab67c01

Browse files
committed
fix(apply-diff): fall back to a full-file search when :start_line: is stale
What: when a hinted block fails inside the ±40-line window around its :start_line:, retry the same match over the whole file before reporting failure. The fallback accepts a match only when exactly one position scores at or above diffFuzzyThreshold (verbatim by default), and reuses the line-number-stripped variant as a second candidate. When several positions qualify, the block still fails and the error now names the duplicate count instead of implying the text is absent. Why: a file that grows after the line number was read makes the hint point hundreds of lines away from its target, so a verbatim SEARCH block failed with a low similarity score even though the text was present elsewhere. This is the reported #985 symptom, most visible when an agent plans several large Markdown diffs from one read. Impact: additive only, on the failure path of hinted blocks. Unhinted blocks and blocks that match in-window are untouched. Refusing duplicates means a stale hint can never silently edit another occurrence. Fixes #985
1 parent 159c42e commit ab67c01

2 files changed

Lines changed: 278 additions & 1 deletion

File tree

‎src/core/diff/strategies/__tests__/multi-search-replace.spec.ts‎

Lines changed: 173 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1631,4 +1631,177 @@ function sum(a, b) {
16311631
expect(errorMsg).toContain("Search Range: start to end")
16321632
})
16331633
})
1634+
1635+
describe("stale :start_line: hint fallback (#985)", () => {
1636+
const strategy = new MultiSearchReplaceDiffStrategy()
1637+
1638+
const firstFailureError = (result: Awaited<ReturnType<typeof strategy.applyDiff>>) => {
1639+
if (result.success || !result.failParts?.[0]) {
1640+
throw new Error("Expected a failed part")
1641+
}
1642+
1643+
const failedPart = result.failParts[0]
1644+
return "error" in failedPart ? failedPart.error : ""
1645+
}
1646+
1647+
// A file that grew by 200 lines after the hint was read: the target sits far outside
1648+
// the ±40-line buffer around the stale hint.
1649+
const grownFile = [
1650+
"# Doc",
1651+
...Array.from({ length: 200 }, (_, index) => `filler ${index + 1}`),
1652+
"## Section B",
1653+
"body b",
1654+
"## Section C",
1655+
"body c",
1656+
].join("\n")
1657+
1658+
it("applies the block at its real position when the SEARCH text is unique elsewhere in the file", async () => {
1659+
const diff =
1660+
"<<<<<<< SEARCH\n" +
1661+
":start_line:5\n" +
1662+
"-------\n" +
1663+
"## Section B\n" +
1664+
"body b\n" +
1665+
"=======\n" +
1666+
"## Section B\n" +
1667+
"updated b\n" +
1668+
">>>>>>> REPLACE"
1669+
1670+
const result = await strategy.applyDiff(grownFile, diff)
1671+
1672+
expect(result.success).toBe(true)
1673+
if (!result.success) {
1674+
throw new Error("Expected the stale hint to fall back to a full-file match")
1675+
}
1676+
expect(result.content).toContain("## Section B\nupdated b")
1677+
expect(result.content).not.toContain("body b")
1678+
// The 200 filler lines are untouched: the fallback moved the edit, it did not rewrite the file.
1679+
expect(result.content.split("\n")).toHaveLength(grownFile.split("\n").length)
1680+
})
1681+
1682+
it("still fails when the SEARCH text is absent from the whole file", async () => {
1683+
const diff =
1684+
"<<<<<<< SEARCH\n" +
1685+
":start_line:5\n" +
1686+
"-------\n" +
1687+
"## Section Z\n" +
1688+
"body z\n" +
1689+
"=======\n" +
1690+
"## Section Z\n" +
1691+
"updated z\n" +
1692+
">>>>>>> REPLACE"
1693+
1694+
const result = await strategy.applyDiff(grownFile, diff)
1695+
1696+
expect(result.success).toBe(false)
1697+
const error = firstFailureError(result)
1698+
expect(error).toContain("No sufficiently similar match found at line: 5")
1699+
expect(error).toContain("Search Range: starting at line 5")
1700+
expect(error).not.toContain("LIKELY CAUSE: the SEARCH text matches")
1701+
})
1702+
1703+
it("refuses to guess when the SEARCH text matches several places in the file", async () => {
1704+
const duplicatedFile = [
1705+
"# Doc",
1706+
...Array.from({ length: 200 }, (_, index) => `filler ${index + 1}`),
1707+
"## Section B",
1708+
"body b",
1709+
...Array.from({ length: 100 }, (_, index) => `more ${index + 1}`),
1710+
"## Section B",
1711+
"body b again",
1712+
].join("\n")
1713+
const diff =
1714+
"<<<<<<< SEARCH\n" +
1715+
":start_line:5\n" +
1716+
"-------\n" +
1717+
"## Section B\n" +
1718+
"=======\n" +
1719+
"## Section B renamed\n" +
1720+
">>>>>>> REPLACE"
1721+
1722+
const result = await strategy.applyDiff(duplicatedFile, diff)
1723+
1724+
expect(result.success).toBe(false)
1725+
const error = firstFailureError(result)
1726+
expect(error).toContain("No sufficiently similar match found at line: 5")
1727+
expect(error).toContain("LIKELY CAUSE: the SEARCH text matches 2 separate places in the file")
1728+
})
1729+
1730+
it("keeps later hinted blocks aligned when an earlier block grows the file", async () => {
1731+
const original = ["# Doc", "## Section A", "body a", "## Section B", "body b"].join("\n")
1732+
const inserted = Array.from({ length: 60 }, (_, index) => `inserted ${index + 1}`)
1733+
const diff =
1734+
"<<<<<<< SEARCH\n" +
1735+
":start_line:2\n" +
1736+
"-------\n" +
1737+
"## Section A\n" +
1738+
"body a\n" +
1739+
"=======\n" +
1740+
"## Section A\n" +
1741+
inserted.map((line) => `${line}\n`).join("") +
1742+
">>>>>>> REPLACE\n\n" +
1743+
"<<<<<<< SEARCH\n" +
1744+
":start_line:4\n" +
1745+
"-------\n" +
1746+
"## Section B\n" +
1747+
"body b\n" +
1748+
"=======\n" +
1749+
"## Section B\n" +
1750+
"updated b\n" +
1751+
">>>>>>> REPLACE"
1752+
1753+
const result = await strategy.applyDiff(original, diff)
1754+
1755+
expect(result.success).toBe(true)
1756+
if (!result.success) {
1757+
throw new Error("Expected both blocks to apply")
1758+
}
1759+
const lines = result.content.split("\n")
1760+
expect(lines[0]).toBe("# Doc")
1761+
expect(lines[1]).toBe("## Section A")
1762+
// The first block inserted 60 lines, so the second block's stale hint is 59 lines off.
1763+
expect(lines[61]).toBe("inserted 60")
1764+
expect(lines[62]).toBe("## Section B")
1765+
expect(lines[63]).toBe("updated b")
1766+
expect(result.content).not.toContain("body b")
1767+
})
1768+
1769+
it("does not fall back when no :start_line: hint was given", async () => {
1770+
// Without a hint the search already covers the whole file, so the outcome must be the
1771+
// pre-existing one and must not gain the duplicate-match diagnosis.
1772+
const original = ["## Section B", "body b", "## Section B", "body b again"].join("\n")
1773+
const diff =
1774+
"<<<<<<< SEARCH\n" + "## Section B\n" + "=======\n" + "## Section B renamed\n" + ">>>>>>> REPLACE"
1775+
1776+
const result = await strategy.applyDiff(original, diff)
1777+
1778+
expect(result.success).toBe(true)
1779+
if (!result.success) {
1780+
throw new Error("Expected the unhinted block to match")
1781+
}
1782+
expect(result.content).toBe(["## Section B", "body b", "## Section B renamed", "body b again"].join("\n"))
1783+
})
1784+
1785+
it("honours a relaxed fuzzyThreshold in the full-file retry", async () => {
1786+
const relaxed = new MultiSearchReplaceDiffStrategy(0.9)
1787+
const diff =
1788+
"<<<<<<< SEARCH\n" +
1789+
":start_line:5\n" +
1790+
"-------\n" +
1791+
"## Section B\n" +
1792+
"body B\n" +
1793+
"=======\n" +
1794+
"## Section B\n" +
1795+
"updated b\n" +
1796+
">>>>>>> REPLACE"
1797+
1798+
const result = await relaxed.applyDiff(grownFile, diff)
1799+
1800+
expect(result.success).toBe(true)
1801+
if (!result.success) {
1802+
throw new Error("Expected the relaxed threshold to accept the near match")
1803+
}
1804+
expect(result.content).toContain("## Section B\nupdated b")
1805+
})
1806+
})
16341807
})

‎src/core/diff/strategies/multi-search-replace.ts‎

Lines changed: 105 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -74,6 +74,37 @@ function fuzzySearch(lines: string[], searchChunk: string, startIndex: number, e
7474
return { bestScore, bestMatchIndex, bestMatchContent }
7575
}
7676

77+
/**
78+
* Returns every position in `lines` whose slice scores at least `threshold` against
79+
* `searchChunk`, so a full-file retry can tell a unique match from a duplicated one.
80+
*/
81+
function findAllMatches(lines: string[], searchChunk: string, threshold: number) {
82+
const searchLen = searchChunk.split(/\r?\n/).length
83+
const matches: { index: number; score: number; content: string }[] = []
84+
85+
for (let index = 0; index + searchLen <= lines.length; index++) {
86+
const content = lines.slice(index, index + searchLen).join("\n")
87+
const score = getSimilarity(content, searchChunk)
88+
if (score >= threshold) {
89+
matches.push({ index, score, content })
90+
}
91+
}
92+
93+
return matches
94+
}
95+
96+
interface StaleHintCandidate {
97+
searchContent: string
98+
replaceContent: string
99+
}
100+
101+
interface StaleHintResolution {
102+
/** Set only when exactly one position qualifies, so the hint can be overridden safely. */
103+
match?: StaleHintCandidate & { matchIndex: number; bestMatchScore: number; bestMatchContent: string }
104+
/** Number of qualifying positions found by the best candidate; 0 means absent. */
105+
matchCount: number
106+
}
107+
77108
export class MultiSearchReplaceDiffStrategy implements DiffStrategy {
78109
private fuzzyThreshold: number
79110
private bufferLines: number
@@ -347,6 +378,55 @@ export class MultiSearchReplaceDiffStrategy implements DiffStrategy {
347378
return repaired || diffContent
348379
}
349380

381+
/**
382+
* Recovers from a stale `:start_line:` hint. The buffered search only covers a window around the
383+
* hint, so a file that grew since the line number was read fails even when the SEARCH text is
384+
* still present verbatim. Retries over the whole file and accepts the match only when exactly one
385+
* position qualifies, so a stale hint can never silently edit a different occurrence.
386+
*/
387+
private resolveStaleHint(
388+
resultLines: string[],
389+
searchContent: string,
390+
replaceContent: string,
391+
): StaleHintResolution {
392+
const candidates: StaleHintCandidate[] = [{ searchContent, replaceContent }]
393+
394+
// Mirror the in-window fallback: retry with line numbers stripped when the plain form fails.
395+
const aggressiveSearchContent = stripLineNumbers(searchContent, true)
396+
if (aggressiveSearchContent !== searchContent) {
397+
candidates.push({
398+
searchContent: aggressiveSearchContent,
399+
replaceContent: stripLineNumbers(replaceContent, true),
400+
})
401+
}
402+
403+
let matchCount = 0
404+
405+
for (const candidate of candidates) {
406+
const matches = findAllMatches(resultLines, candidate.searchContent, this.fuzzyThreshold)
407+
if (matches.length === 0) {
408+
continue
409+
}
410+
411+
if (matches.length === 1) {
412+
const [match] = matches
413+
return {
414+
match: {
415+
...candidate,
416+
matchIndex: match.index,
417+
bestMatchScore: match.score,
418+
bestMatchContent: match.content,
419+
},
420+
matchCount: 1,
421+
}
422+
}
423+
424+
matchCount = matches.length
425+
}
426+
427+
return { matchCount }
428+
}
429+
350430
async applyDiff(
351431
originalContent: string,
352432
diffContent: string,
@@ -513,6 +593,25 @@ export class MultiSearchReplaceDiffStrategy implements DiffStrategy {
513593
bestMatchContent = midContent
514594
}
515595

596+
// A stale :start_line: hint bounds the search to a window around it, so a file that grew
597+
// since the hint was read can miss a unique match. Retry over the whole file first.
598+
let staleHintDuplicateCount = 0
599+
600+
if ((matchIndex === -1 || bestMatchScore < this.fuzzyThreshold) && startLine) {
601+
const staleHint = this.resolveStaleHint(resultLines, searchContent, replaceContent)
602+
staleHintDuplicateCount = staleHint.matchCount
603+
604+
if (staleHint.match) {
605+
matchIndex = staleHint.match.matchIndex
606+
bestMatchScore = staleHint.match.bestMatchScore
607+
bestMatchContent = staleHint.match.bestMatchContent
608+
searchContent = staleHint.match.searchContent
609+
replaceContent = staleHint.match.replaceContent
610+
searchLines = searchContent.split(/\r?\n/)
611+
replaceLines = replaceContent ? replaceContent.split(/\r?\n/) : []
612+
}
613+
}
614+
516615
// Try aggressive line number stripping as a fallback if regular matching fails
517616
if (matchIndex === -1 || bestMatchScore < this.fuzzyThreshold) {
518617
// Strip both search and replace content once (simultaneously)
@@ -560,6 +659,11 @@ export class MultiSearchReplaceDiffStrategy implements DiffStrategy {
560659
const malformedMarkerHint = looksLikeMalformedMarker
561660
? `\n- LIKELY CAUSE: the first line of your search content looks like a malformed start-line marker and was therefore searched for as literal file text${separatorSwallowed ? ', together with the "-------" line after it' : ""}. The only recognized form is ":start_line:<number>" on the line immediately after "<<<<<<< SEARCH", optionally followed by a "-------" line. Remove or correct that line and retry.`
562661
: ""
662+
// A duplicated match is refused rather than guessed between, so say so instead of implying absence.
663+
const duplicateHint =
664+
staleHintDuplicateCount > 1
665+
? `\n- LIKELY CAUSE: the SEARCH text matches ${staleHintDuplicateCount} separate places in the file, so the stale :start_line: hint cannot pick one. Include more surrounding lines to make the match unique.`
666+
: ""
563667

564668
diffResults.push({
565669
success: false,
@@ -574,7 +678,7 @@ export class MultiSearchReplaceDiffStrategy implements DiffStrategy {
574678
`- Search Length: ${searchChunk.length} characters\n` +
575679
`- Best Match Location: ${bestMatchLocation}\n` +
576680
`- Best Match Length: ${bestMatchContent ? bestMatchContent.length : 0} characters\n` +
577-
`- Tried both standard and aggressive line number stripping${malformedMarkerHint}\n` +
681+
`- Tried both standard and aggressive line number stripping${malformedMarkerHint}${duplicateHint}\n` +
578682
`- Tip: Use the read_file tool to get the latest content of the file before attempting ` +
579683
`to use the apply_diff tool again, as the file content may have changed\n` +
580684
`- Tip: The SEARCH block must contain complete, whole lines — partial-line (substring) matching is not supported. ` +

0 commit comments

Comments
 (0)