client/src/diff.js

// 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
}