File size: 4,050 Bytes
ec3a520 735a30f ec3a520 735a30f ec3a520 735a30f ec3a520 124d540 fcffddc | 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 108 109 110 111 112 113 114 115 116 | // 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(/^\$\$\n?([\s\S]*?)\n?\$\$$/gm, '$1') // display math -> its source
.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()
}
// A `$...$` formula is ONE token: its source contains spaces (`\|`, `x + y`), so
// splitting on whitespace let the diff align *inside* a formula and render half
// of its LaTeX as inserted text.
const TOKEN_RE = /(?<!\$)\$(?![\s$])[^$\n]*[^\s$]\$(?!\$)|\S+|\s+/g
function tokenize(s) {
return s.match(TOKEN_RE) || []
}
// Word diff over *styled* segments: [{ text, markKey }], where markKey encodes
// the inline marks on that run ('' = none). Two tokens are equal only when both
// the word and its formatting match, so turning a word into a link (or bolding
// it) registers as a change — a plain-text diff sees those as identical and
// renders nothing at all.
//
// Returns [{ type, text, oldStart, oldEnd, newStart, newEnd }] with char offsets
// into the concatenated old / new text.
export function styledWordDiff(oldSegs, newSegs) {
const toTokens = segs => {
const out = []
for (const seg of segs || []) {
for (const text of tokenize(seg.text)) out.push({ text, markKey: seg.markKey || '' })
}
return out
}
const a = toTokens(oldSegs)
const b = toTokens(newSegs)
const same = (x, y) => x.text === y.text && x.markKey === y.markKey
let merged
if (a.length * b.length > 250000) {
merged = [
{ type: 'del', tokens: a },
{ type: 'ins', tokens: b },
]
} else {
const ops = arrayDiff(a, b, same)
merged = []
for (const op of ops) {
const token = op.type === 'del' ? a[op.aIdx] : b[op.bIdx]
const last = merged[merged.length - 1]
if (last && last.type === op.type) last.tokens.push(token)
else merged.push({ type: op.type, tokens: [token] })
}
}
let oldOff = 0
let newOff = 0
return merged.map(op => {
const text = op.tokens.map(t => t.text).join('')
const out = {
type: op.type,
text,
oldStart: oldOff,
oldEnd: op.type === 'ins' ? oldOff : oldOff + text.length,
newStart: newOff,
newEnd: op.type === 'del' ? newOff : newOff + text.length,
}
if (op.type !== 'ins') oldOff += text.length
if (op.type !== 'del') newOff += text.length
return out
})
}
// Marks -> a comparable key. Both sides must agree, so only mark identity and
// the link target matter (a PM link mark also carries target/rel).
export function markKeyOf(names) {
return [...new Set(names)].sort().join(',')
}
// 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
}
|