im0o
a40bd6a01b
备份存的是「改动前」，所以一条记录的 diff 两端是它自己和更新一份的 状态（最新一条对比当前文件）。行级 diff 先掐公共前后缀再做 LCS，一次 改动通常只碰几行，表撑得住；大面积不同时退化成整段删增。 合并窗做在服务端而不是前端防抖：普通保存（opts.merge）发现最新备份 还在窗内就不新建，连点删除共享一条历史、一步撤回。窗锚定在这一串的 第一下，不滚雪球；还原、导入、撤回重做不合并，各占一条。合并时没有 备份文件，重载失败的还原改用刚读出的原文写回。顺带消除了备份名只精 确到秒、同秒保存互相覆盖的隐患。
104 lines
3.2 KiB
TypeScript
104 lines
3.2 KiB
TypeScript
/**
|
|
* 行级 diff，给历史记录的「这次改动改了什么」用。
|
|
*
|
|
* 先掐掉公共前后缀再对中段做 LCS：配置文件的一次改动通常只碰几行，中段一般
|
|
* 很小，LCS 的 O(n×m) 表因此撑得住。真遇到两份大面积不同的文件（中段乘积超过
|
|
* 上限），退化成「整段删除 + 整段新增」——依旧正确，只是不够精细。
|
|
*/
|
|
|
|
export interface DiffLine {
|
|
kind: 'same' | 'add' | 'del'
|
|
text: string
|
|
}
|
|
|
|
const LCS_LIMIT = 1_000_000
|
|
|
|
export function diffLines(before: string, after: string): DiffLine[] {
|
|
const a = before.split('\n')
|
|
const b = after.split('\n')
|
|
|
|
let start = 0
|
|
while (start < a.length && start < b.length && a[start] === b[start]) start += 1
|
|
let endA = a.length
|
|
let endB = b.length
|
|
while (endA > start && endB > start && a[endA - 1] === b[endB - 1]) {
|
|
endA -= 1
|
|
endB -= 1
|
|
}
|
|
|
|
return [
|
|
...a.slice(0, start).map((text): DiffLine => ({ kind: 'same', text })),
|
|
...diffMiddle(a.slice(start, endA), b.slice(start, endB)),
|
|
...a.slice(endA).map((text): DiffLine => ({ kind: 'same', text })),
|
|
]
|
|
}
|
|
|
|
function diffMiddle(a: string[], b: string[]): DiffLine[] {
|
|
const allDel = a.map((text): DiffLine => ({ kind: 'del', text }))
|
|
const allAdd = b.map((text): DiffLine => ({ kind: 'add', text }))
|
|
if (a.length === 0 || b.length === 0 || a.length * b.length > LCS_LIMIT) {
|
|
return [...allDel, ...allAdd]
|
|
}
|
|
|
|
// LCS 长度表倒着填，回溯时从头正着走
|
|
const w = b.length + 1
|
|
const table = new Uint32Array((a.length + 1) * w)
|
|
for (let i = a.length - 1; i >= 0; i -= 1) {
|
|
for (let j = b.length - 1; j >= 0; j -= 1) {
|
|
table[i * w + j] =
|
|
a[i] === b[j]
|
|
? table[(i + 1) * w + j + 1]! + 1
|
|
: Math.max(table[(i + 1) * w + j]!, table[i * w + j + 1]!)
|
|
}
|
|
}
|
|
|
|
const rows: DiffLine[] = []
|
|
let i = 0
|
|
let j = 0
|
|
while (i < a.length && j < b.length) {
|
|
if (a[i] === b[j]) {
|
|
rows.push({ kind: 'same', text: a[i]! })
|
|
i += 1
|
|
j += 1
|
|
} else if (table[(i + 1) * w + j]! >= table[i * w + j + 1]!) {
|
|
rows.push({ kind: 'del', text: a[i]! })
|
|
i += 1
|
|
} else {
|
|
rows.push({ kind: 'add', text: b[j]! })
|
|
j += 1
|
|
}
|
|
}
|
|
while (i < a.length) rows.push({ kind: 'del', text: a[i++]! })
|
|
while (j < b.length) rows.push({ kind: 'add', text: b[j++]! })
|
|
return rows
|
|
}
|
|
|
|
/**
|
|
* 折叠成只含改动的片段：每个片段是改动行加前后 context 行上下文，片段之间的
|
|
* 未改动区域丢弃（渲染端画省略号）。两份内容相同时返回空数组。
|
|
*/
|
|
export function diffHunks(rows: DiffLine[], context = 2): DiffLine[][] {
|
|
const keep = new Array<boolean>(rows.length).fill(false)
|
|
rows.forEach((row, index) => {
|
|
if (row.kind === 'same') return
|
|
const from = Math.max(0, index - context)
|
|
const to = Math.min(rows.length - 1, index + context)
|
|
for (let k = from; k <= to; k += 1) keep[k] = true
|
|
})
|
|
|
|
const hunks: DiffLine[][] = []
|
|
let current: DiffLine[] | null = null
|
|
rows.forEach((row, index) => {
|
|
if (!keep[index]) {
|
|
current = null
|
|
return
|
|
}
|
|
if (!current) {
|
|
current = []
|
|
hunks.push(current)
|
|
}
|
|
current.push(row)
|
|
})
|
|
return hunks
|
|
}
|