Repository Public
1// ORIX Docs2// File: Packages/ORIXDocsKit/Sources/DocReview/ParagraphDiff.swift3// Description: Token-level diff of two paragraphs, expressed as runs carrying insertion, deletion and formatting revisions.4//5// Author: Simon-Pierre Boucher6// Contact: contact@spboucher.ai7import Foundation8import DocModel910struct ParagraphDiff {11 /// Runs of the revised paragraph with the original text kept as deleted runs.12 var runs: [Run] = []13 var textChanged = false14 var wordsInserted = 0, wordsDeleted = 0, wordsEqual = 015 /// Descriptions of the character formatting differences found on unchanged text ("Bold added").16 var formatNotes: [String] = []17 /// Note references that face each other: (original note id, revised note id).18 var notePairs: [(String, String)] = []1920 mutating func note(_ s: String) { if !formatNotes.contains(s) { formatNotes.append(s) } }21}2223extension ComparisonContext {24 /// Diffs two paragraphs (already flattened). `ta` / `tb` may carry tokens computed earlier.25 func diff(_ a: Paragraph, _ b: Paragraph, ta: [Token]? = nil, tb: [Token]? = nil) -> ParagraphDiff {26 let ta = ta ?? tokens(a, side: .original), tb = tb ?? tokens(b, side: .revised)27 let matches = SequenceDiff.lcs(ta.map(\.key), tb.map(\.key), anchors: false, maxCost: 4096)28 var result = ParagraphDiff()29 let textA = a.plainText as NSString, textB = b.plainText as NSString30 let sameStyle = a.style == b.style31 var formatRevisions: [FormatKey: FormatRevision] = [:]3233 // Run boundaries, for walking both paragraphs in step.34 func spans(_ p: Paragraph) -> [Int] {35 var starts: [Int] = []36 var pos = 037 for r in p.runs { starts.append(pos); pos += r.length }38 starts.append(pos)39 return starts40 }41 let startsA = spans(a), startsB = spans(b)42 var cursorA = 0, cursorB = 043 func runIndex(_ starts: [Int], _ cursor: inout Int, _ offset: Int) -> Int {44 if cursor >= starts.count - 1 { cursor = max(0, starts.count - 2) }45 while cursor > 0 && starts[cursor] > offset { cursor -= 1 }46 while cursor < starts.count - 2 && starts[cursor + 1] <= offset { cursor += 1 }47 return cursor48 }4950 func append(_ run: Run) {51 guard !run.text.isEmpty else { return }52 if let last = result.runs.last, last.canMerge(with: run) { result.runs[result.runs.count - 1].text += run.text } else { result.runs.append(run) }53 }5455 func formatDiffers(_ ra: Run, _ rb: Run) -> Bool {56 guard options.compareFormatting else { return false }57 if ra.props == rb.props && ra.charStyle == rb.charStyle { return false }58 let oa = override(ra, side: .original), ob = override(rb, side: .revised)59 if oa == ob { return false }60 if sameStyle {61 let x = resolved(ra, paraStyle: a.style, side: .original), y = resolved(rb, paraStyle: b.style, side: .revised)62 if x == y { return false }63 let notes = FormatDescription.character(x, y)64 if notes.isEmpty { result.note("Character formatting changed") } else { notes.forEach { result.note($0) } }65 } else {66 let notes = FormatDescription.character(ResolvedChar(oa), ResolvedChar(ob))67 if notes.isEmpty { result.note("Character formatting changed") } else { notes.forEach { result.note($0) } }68 }69 return true70 }7172 func emitEqual(_ t: Token, _ u: Token) {73 guard !a.runs.isEmpty, !b.runs.isEmpty else { return }74 if t.len == u.len {75 var pos = 076 while pos < u.len {77 let ia = runIndex(startsA, &cursorA, t.loc + pos), ib = runIndex(startsB, &cursorB, u.loc + pos)78 let piece = max(1, min(u.len - pos, startsA[ia + 1] - (t.loc + pos), startsB[ib + 1] - (u.loc + pos)))79 emitPiece(a.runs[ia], b.runs[ib], NSRange(location: u.loc + pos, length: piece))80 pos += piece81 }82 } else {83 // Same key, different length (case folding or collapsed white space): the original formatting at the token start applies.84 let ia = runIndex(startsA, &cursorA, t.loc)85 var pos = 086 while pos < u.len {87 let ib = runIndex(startsB, &cursorB, u.loc + pos)88 let piece = max(1, min(u.len - pos, startsB[ib + 1] - (u.loc + pos)))89 emitPiece(a.runs[ia], b.runs[ib], NSRange(location: u.loc + pos, length: piece))90 pos += piece91 }92 }93 }9495 func emitPiece(_ ra: Run, _ rb: Run, _ range: NSRange) {96 var out = rb97 out.text = textB.substring(with: range)98 out.revision = nil99 out.formatRevision = nil100 if formatDiffers(ra, rb) {101 let key = FormatKey(props: ra.props, charStyle: ra.charStyle)102 if let f = formatRevisions[key] { out.formatRevision = f } else {103 let f = nextFormatRevision(previous: ra.props, charStyle: ra.charStyle)104 formatRevisions[key] = f105 out.formatRevision = f106 }107 }108 if let ia = ra.inline, let ib = rb.inline {109 if case .note(let x) = ia, case .note(let y) = ib { result.notePairs.append((x.id, y.id)) }110 else if ia != ib, options.compareFormatting, let d = FormatDescription.inlineObject(ia, ib) { result.note(d) }111 }112 append(out)113 }114115 func emitChange(_ p: Paragraph, _ toks: ArraySlice<Token>, _ kind: Revision.Kind) {116 guard let first = toks.first, let last = toks.last else { return }117 let words = toks.reduce(0) { $0 + ($1.isContent ? 1 : 0) }118 if options.ignoreWhitespace && toks.allSatisfy({ $0.kind == .space }) {119 // White-space-only difference: not a change. The revised spacing is kept as it is.120 if kind == .insertion { for r in p.slice(first.loc..<last.end) { var c = r; c.revision = nil; c.formatRevision = nil; append(c) } }121 return122 }123 let rev = nextRevision(kind)124 for r in p.slice(first.loc..<last.end) {125 var c = r126 c.revision = rev127 c.formatRevision = nil128 if kind == .deletion { adopt(&c) }129 append(c)130 }131 result.textChanged = true132 if kind == .insertion { result.wordsInserted += words } else { result.wordsDeleted += words }133 }134135 var i = 0, j = 0136 for (mi, mj) in matches {137 if i < mi { emitChange(a, ta[i..<mi], .deletion) }138 if j < mj { emitChange(b, tb[j..<mj], .insertion) }139 emitEqual(ta[mi], tb[mj])140 if tb[mj].isContent { result.wordsEqual += 1 }141 i = mi + 1; j = mj + 1142 }143 if i < ta.count { emitChange(a, ta[i..<ta.count], .deletion) }144 if j < tb.count { emitChange(b, tb[j..<tb.count], .insertion) }145 return result146 }147148 private struct FormatKey: Hashable { var props: CharProps; var charStyle: String? }149}150