File size: 3,318 Bytes
ec3a520 fcffddc ec3a520 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 | // Word-level diff between the current text of a suggestion's anchored range and
// its replacement markdown — used to render suggestions inline (strikethrough
// deletions, phantom insertions) like track changes.
// Flatten markdown to the plain text a reader would see.
export function flattenMarkdown(md) {
return String(md || '')
.replace(/```\w*\n?([\s\S]*?)```/g, '$1')
.replace(/!\[[^\]]*\]\([^)]*\)/g, '[figure]')
.replace(/\[([^\]]*)\]\([^)]*\)/g, '$1')
.replace(/\*\*([^*]+)\*\*/g, '$1')
.replace(/\*([^*]+)\*/g, '$1')
.replace(/~~([^~]+)~~/g, '$1')
.replace(/`([^`]+)`/g, '$1')
.replace(/^#{1,6}\s+/gm, '')
.replace(/^\s*[-*]\s+/gm, '')
.replace(/^\s*\d+[.)]\s+/gm, '')
.replace(/^>\s?/gm, '')
.replace(/\n{2,}/g, '\n')
.trim()
}
function tokenize(s) {
return s.match(/\S+|\s+/g) || []
}
// Generic LCS diff over arrays. Returns ops: [{type: 'eq'|'del'|'ins', aIdx?, bIdx?}]
export function arrayDiff(a, b, eq) {
const n = a.length
const m = b.length
const dp = Array.from({ length: n + 1 }, () => new Uint16Array(m + 1))
for (let i = n - 1; i >= 0; i--) {
for (let j = m - 1; j >= 0; j--) {
dp[i][j] = eq(a[i], b[j]) ? dp[i + 1][j + 1] + 1 : Math.max(dp[i + 1][j], dp[i][j + 1])
}
}
const ops = []
let i = 0
let j = 0
while (i < n && j < m) {
if (eq(a[i], b[j])) ops.push({ type: 'eq', aIdx: i++, bIdx: j++ })
else if (dp[i + 1][j] >= dp[i][j + 1]) ops.push({ type: 'del', aIdx: i++ })
else ops.push({ type: 'ins', bIdx: j++ })
}
while (i < n) ops.push({ type: 'del', aIdx: i++ })
while (j < m) ops.push({ type: 'ins', bIdx: j++ })
return ops
}
// Returns merged ops: [{ type: 'eq'|'del'|'ins', text, oldStart, oldEnd }]
// oldStart/oldEnd are char offsets into oldStr ('ins' has oldStart === oldEnd).
export function wordDiff(oldStr, newStr) {
const a = tokenize(oldStr)
const b = tokenize(newStr)
let ops
if (a.length * b.length > 250000) {
// too big for LCS — degrade to replace-everything
ops = [
{ type: 'del', tokens: a },
{ type: 'ins', tokens: b },
]
} else {
// LCS table
const n = a.length
const m = b.length
const dp = Array.from({ length: n + 1 }, () => new Uint16Array(m + 1))
for (let i = n - 1; i >= 0; i--) {
for (let j = m - 1; j >= 0; j--) {
dp[i][j] = a[i] === b[j] ? dp[i + 1][j + 1] + 1 : Math.max(dp[i + 1][j], dp[i][j + 1])
}
}
ops = []
let i = 0
let j = 0
const push = (type, token) => {
const last = ops[ops.length - 1]
if (last && last.type === type) last.tokens.push(token)
else ops.push({ type, tokens: [token] })
}
while (i < n && j < m) {
if (a[i] === b[j]) {
push('eq', a[i])
i++
j++
} else if (dp[i + 1][j] >= dp[i][j + 1]) {
push('del', a[i])
i++
} else {
push('ins', b[j])
j++
}
}
while (i < n) push('del', a[i++])
while (j < m) push('ins', b[j++])
}
// annotate char offsets in oldStr
let off = 0
return ops.map(op => {
const text = op.tokens.join('')
const out = { type: op.type, text, oldStart: off, oldEnd: op.type === 'ins' ? off : off + text.length }
if (op.type !== 'ins') off += text.length
return out
})
}
|