Automerge backed Markdown editor for the Atmosphere
Something went wrong. Try again.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169export interface TextDiffChange { readonly from: number readonly to: number readonly insert: string}
export interface TextDiffOptions { readonly maxCharWork?: number}
interface Line { readonly text: string; readonly from: number; readonly to: number }interface Point { readonly value: string; readonly from: number; readonly to: number }
const DEFAULT_MAX_CHAR_WORK = 200_000
/** Text-only diff. Equal lines are anchors, never identities or moves. */export function diffTextChanges(oldText: string, newText: string, options: TextDiffOptions = {}): TextDiffChange[] { if (options.maxCharWork !== undefined && (!Number.isSafeInteger(options.maxCharWork) || options.maxCharWork < 0)) throw new RangeError('Invalid text diff work budget') if (oldText === newText) return [] const oldLines = splitLines(oldText) const newLines = splitLines(newText) const oldCounts = counts(oldLines) const newCounts = counts(newLines) const newIndex = new Map<string, number>() for (let index = 0; index < newLines.length; index += 1) newIndex.set(newLines[index]!.text, index) const candidates: Array<{ old: number; next: number }> = [] for (let index = 0; index < oldLines.length; index += 1) { const line = oldLines[index]! const next = newIndex.get(line.text) if (oldCounts.get(line.text) === 1 && newCounts.get(line.text) === 1 && next !== undefined) candidates.push({ old: index, next }) } const anchors = lis(candidates) const result: TextDiffChange[] = [] let oldCursor = 0 let newCursor = 0 let work = 0 const limit = Math.max(0, Math.min(options.maxCharWork ?? DEFAULT_MAX_CHAR_WORK, DEFAULT_MAX_CHAR_WORK)) for (const anchor of anchors) { work = appendGap(result, oldText, newText, oldLines, newLines, oldCursor, anchor.old, newCursor, anchor.next, work, limit) oldCursor = anchor.old + 1 newCursor = anchor.next + 1 } appendGap(result, oldText, newText, oldLines, newLines, oldCursor, oldLines.length, newCursor, newLines.length, work, limit) return result}
function appendGap(result: TextDiffChange[], oldText: string, newText: string, oldLines: readonly Line[], newLines: readonly Line[], oldFromLine: number, oldToLine: number, newFromLine: number, newToLine: number, work: number, limit: number): number { const oldFrom = oldFromLine < oldLines.length ? oldLines[oldFromLine]!.from : oldText.length const oldTo = oldToLine > oldFromLine ? oldLines[oldToLine - 1]!.to : oldFrom const newFrom = newFromLine < newLines.length ? newLines[newFromLine]!.from : newText.length const newTo = newToLine > newFromLine ? newLines[newToLine - 1]!.to : newFrom if (oldFrom === oldTo || newFrom === newTo) { addChange(result, newText, oldFrom, oldTo, newFrom, newTo) return work } // Bound allocation before expanding long lines into code-point objects. if (work + (oldTo - oldFrom) * (newTo - newFrom) > limit) { appendEnvelope(result, oldText, newText, oldFrom, oldTo, newFrom, newTo) return work } const oldPoints = points(oldText.slice(oldFrom, oldTo), oldFrom) const newPoints = points(newText.slice(newFrom, newTo), newFrom) const product = oldPoints.length * newPoints.length if (work + product > limit) { appendEnvelope(result, oldText, newText, oldFrom, oldTo, newFrom, newTo) return work } appendLcs(result, oldPoints, newPoints, newText, oldFrom, newFrom) return work + product}
function appendEnvelope(result: TextDiffChange[], oldText: string, newText: string, oldFrom: number, oldTo: number, newFrom: number, newTo: number): void { let prefix = 0 while (oldFrom + prefix < oldTo && newFrom + prefix < newTo && oldText[oldFrom + prefix] === newText[newFrom + prefix]) prefix += 1 if (splitsSurrogate(oldText, oldFrom + prefix) || splitsSurrogate(newText, newFrom + prefix)) prefix -= 1 let suffix = 0 while (oldTo - suffix > oldFrom + prefix && newTo - suffix > newFrom + prefix && oldText[oldTo - suffix - 1] === newText[newTo - suffix - 1]) suffix += 1 if (splitsSurrogate(oldText, oldTo - suffix) || splitsSurrogate(newText, newTo - suffix)) suffix -= 1 addChange(result, newText, oldFrom + prefix, oldTo - suffix, newFrom + prefix, newTo - suffix)}
function splitsSurrogate(text: string, offset: number): boolean { return offset > 0 && offset < text.length && text.charCodeAt(offset - 1) >= 0xd800 && text.charCodeAt(offset - 1) <= 0xdbff && text.charCodeAt(offset) >= 0xdc00 && text.charCodeAt(offset) <= 0xdfff}
function appendLcs(result: TextDiffChange[], oldPoints: readonly Point[], newPoints: readonly Point[], newText: string, oldFrom: number, newFrom: number): void { const width = newPoints.length + 1 const table = new Uint32Array((oldPoints.length + 1) * width) for (let row = oldPoints.length - 1; row >= 0; row -= 1) { for (let column = newPoints.length - 1; column >= 0; column -= 1) { const at = row * width + column table[at] = oldPoints[row]!.value === newPoints[column]!.value ? table[(row + 1) * width + column + 1]! + 1 : Math.max(table[(row + 1) * width + column]!, table[row * width + column + 1]!) } } const matches: Array<[number, number]> = [] let row = 0 let column = 0 while (row < oldPoints.length && column < newPoints.length) { if (oldPoints[row]!.value === newPoints[column]!.value) { matches.push([row, column]); row += 1; column += 1 } else if (table[(row + 1) * width + column]! >= table[row * width + column + 1]!) row += 1 else column += 1 } let oldCursor = oldPoints[0]?.from ?? oldFrom let newCursor = newPoints[0]?.from ?? newFrom for (const [oldIndex, newIndex] of matches) { addChange(result, newText, oldCursor, oldPoints[oldIndex]!.from, newCursor, newPoints[newIndex]!.from) oldCursor = oldPoints[oldIndex]!.to newCursor = newPoints[newIndex]!.to } addChange(result, newText, oldCursor, oldPoints[oldPoints.length - 1]?.to ?? oldCursor, newCursor, newPoints[newPoints.length - 1]?.to ?? newCursor)}
function addChange(result: TextDiffChange[], newText: string, from: number, to: number, newFrom: number, newTo: number): void { if (from === to && newFrom === newTo) return const insert = newText.slice(newFrom, newTo) const previous = result[result.length - 1] if (previous && previous.to === from && previous.insert.length === 0 && insert.length === 0) result[result.length - 1] = { ...previous, to } else result.push({ from, to, insert })}
function splitLines(text: string): Line[] { const lines: Line[] = [] let from = 0 for (let index = 0; index < text.length; index += 1) { if (text[index] === '\n' || text[index] === '\r') { if (text[index] === '\r' && text[index + 1] === '\n') index += 1 lines.push({ text: text.slice(from, index + 1), from, to: index + 1 }) from = index + 1 } } if (from < text.length || lines.length === 0) lines.push({ text: text.slice(from), from, to: text.length }) return lines}
function points(text: string, offset: number): Point[] { const output: Point[] = [] for (let index = 0; index < text.length;) { const from = index const code = text.codePointAt(index)! index += code > 0xffff ? 2 : 1 output.push({ value: text.slice(from, index), from: offset + from, to: offset + index }) } return output}
function counts(lines: readonly Line[]): Map<string, number> { const output = new Map<string, number>() for (const line of lines) output.set(line.text, (output.get(line.text) ?? 0) + 1) return output}
function lis(items: readonly { old: number; next: number }[]): Array<{ old: number; next: number }> { const tails: number[] = [] const previous = new Array<number>(items.length).fill(-1) for (let index = 0; index < items.length; index += 1) { let low = 0; let high = tails.length while (low < high) { const middle = (low + high) >>> 1; if (items[tails[middle]!]!.next < items[index]!.next) low = middle + 1; else high = middle } if (low > 0) previous[index] = tails[low - 1]! tails[low] = index } const output: Array<{ old: number; next: number }> = [] for (let index = tails[tails.length - 1] ?? -1; index >= 0; index = previous[index]!) output.push(items[index]!) return output.reverse()}