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(/!\[[^\]]*\]\([^)]*\)/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
  })
}