Skip to content
This repository was archived by the owner on Nov 13, 2026. It is now read-only.

Commit 7e918a1

Browse files
perf(tool/edit): use rolling rows instead of full matrix in levenshtein
BlockAnchorReplacer calls levenshtein() per line during fuzzy oldString matching, and it was allocating a full (n+1)x(m+1) matrix (via nested Array.from callbacks) on every call — unnecessary GC pressure on large files, since only the final distance is needed, not a full matrix for backtracking. Switched to two rolling 1D rows (O(min(n,m)) space instead of O(n*m)). Verified: existing edit tool suite (29/29 pass) plus a 20,000-case fuzz comparison against the original implementation confirms byte-identical output. Ref anomalyco#47604. Note: that issue also reports the module-level `locks` Map in edit.ts never evicting entries (slow memory leak over long sessions). Deliberately not touched here — safely evicting a lock out from under a potential concurrent holder needs more careful study than time allowed for this pass; a rushed fix risks breaking the mutual-exclusion guarantee entirely.
1 parent b45c3ea commit 7e918a1

1 file changed

Lines changed: 13 additions & 6 deletions

File tree

‎packages/opencode/src/tool/edit.ts‎

Lines changed: 13 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -221,24 +221,31 @@ const SINGLE_CANDIDATE_SIMILARITY_THRESHOLD = 0.65
221221
const MULTIPLE_CANDIDATES_SIMILARITY_THRESHOLD = 0.65
222222

223223
/**
224-
* Levenshtein distance algorithm implementation
224+
* Levenshtein distance algorithm implementation.
225+
*
226+
* Only the final distance is needed (no backtracking), so this uses two
227+
* rolling 1D rows instead of allocating a full (n+1)x(m+1) matrix. Callers
228+
* (BlockAnchorReplacer) run this per line, so avoiding an O(n*m) allocation
229+
* on every call matters for large files.
225230
*/
226231
function levenshtein(a: string, b: string): number {
227232
// Handle empty strings
228233
if (a === "" || b === "") {
229234
return Math.max(a.length, b.length)
230235
}
231-
const matrix = Array.from({ length: a.length + 1 }, (_, i) =>
232-
Array.from({ length: b.length + 1 }, (_, j) => (i === 0 ? j : j === 0 ? i : 0)),
233-
)
236+
let prev = new Array(b.length + 1)
237+
let curr = new Array(b.length + 1)
238+
for (let j = 0; j <= b.length; j++) prev[j] = j
234239

235240
for (let i = 1; i <= a.length; i++) {
241+
curr[0] = i
236242
for (let j = 1; j <= b.length; j++) {
237243
const cost = a[i - 1] === b[j - 1] ? 0 : 1
238-
matrix[i][j] = Math.min(matrix[i - 1][j] + 1, matrix[i][j - 1] + 1, matrix[i - 1][j - 1] + cost)
244+
curr[j] = Math.min(prev[j] + 1, curr[j - 1] + 1, prev[j - 1] + cost)
239245
}
246+
;[prev, curr] = [curr, prev]
240247
}
241-
return matrix[a.length][b.length]
248+
return prev[b.length]
242249
}
243250

244251
export const SimpleReplacer: Replacer = function* (_content, find) {

0 commit comments

Comments
 (0)