SPB Git

Repository Public

ParagraphDiff.swift 7.2 KB 150 lines swift

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
Files main
Menu

Theme