SPB Git

Repository Public

BlockComparer.swift 20.1 KB 357 lines swift

1// ORIX Docs2// File: Packages/ORIXDocsKit/Sources/DocReview/BlockComparer.swift3// Description: Block-level alignment of two block lists (LCS on fingerprints, similarity pairing of the gaps, move detection)4//              and construction of the merged blocks with tracked changes.5//6// Author: Simon-Pierre Boucher7// Contact: contact@spboucher.ai8import Foundation9import DocModel1011/// Thresholds of the block alignment. They are documented in docs/architecture/review.md.12enum ComparisonTuning {13    /// Two unmatched blocks of a gap are one edited block when the Dice similarity of their word bags reaches this value.14    static let modifiedSimilarity = 0.515    /// Gaps up to this many cell pairs are paired optimally (dynamic programming); larger gaps use a forward window.16    static let optimalPairingCells = 10_00017    /// Width of the forward window used on large gaps.18    static let pairingWindow = 3219    /// An exact move needs at least this many UTF-16 units of text and this many words.20    static let moveMinLength = 2421    static let moveMinWords = 422    /// A move with edits needs this similarity, and a longer block.23    static let fuzzyMoveSimilarity = 0.8524    static let fuzzyMoveMinLength = 4025    static let fuzzyMoveMinWords = 826    /// Fuzzy move search is skipped when (deleted blocks × inserted blocks) exceeds this.27    static let fuzzyMoveMaxPairs = 250_00028}2930struct BlockListResult {31    var merged: [Block] = []32    var rows: [AlignedRow] = []33    /// True when at least one change was recorded.34    var changed = false35}3637extension ComparisonContext {38    private enum Entry { case equal(Int, Int), modified(Int, Int), deleted(Int), inserted(Int) }3940    func compareBlocks(_ A: [Block], _ B: [Block], scope: Scope) -> BlockListResult {41        let keysA = A.map { blockKey($0, side: .original) }, keysB = B.map { blockKey($0, side: .revised) }42        let matches = SequenceDiff.lcs(keysA, keysB, anchors: true)4344        // Lazily computed tokens and bags of the blocks that end up in a gap.45        var tokA = [[Token]?](repeating: nil, count: A.count), tokB = [[Token]?](repeating: nil, count: B.count)46        var bagA = [[Int]?](repeating: nil, count: A.count), bagB = [[Int]?](repeating: nil, count: B.count)47        func bagOfA(_ i: Int) -> [Int] {48            if let b = bagA[i] { return b }49            var out: [Int] = []50            switch A[i] {51            case .paragraph(let p): let t = tokens(p, side: .original); tokA[i] = t; out = bag(t)52            case .table(let t): out = tableBag(t, side: .original)53            default: break54            }55            bagA[i] = out56            return out57        }58        func bagOfB(_ j: Int) -> [Int] {59            if let b = bagB[j] { return b }60            var out: [Int] = []61            switch B[j] {62            case .paragraph(let p): let t = tokens(p, side: .revised); tokB[j] = t; out = bag(t)63            case .table(let t): out = tableBag(t, side: .revised)64            default: break65            }66            bagB[j] = out67            return out68        }69        func comparable(_ i: Int, _ j: Int) -> Bool {70            switch (A[i], B[j]) {71            case (.paragraph, .paragraph), (.table, .table): return true72            default: return false73            }74        }75        func similarity(_ i: Int, _ j: Int) -> Double {76            guard comparable(i, j) else { return 0 }77            return diceSimilarity(bagOfA(i), bagOfB(j))78        }7980        // 1. Entries in document order: matches, and the gaps between them paired by similarity.81        var entries: [Entry] = []82        entries.reserveCapacity(max(A.count, B.count))83        func gap(_ a0: Int, _ a1: Int, _ b0: Int, _ b1: Int) {84            let n = a1 - a0, m = b1 - b085            if n == 0 { for j in b0..<b1 { entries.append(.inserted(j)) }; return }86            if m == 0 { for i in a0..<a1 { entries.append(.deleted(i)) }; return }87            var pairs: [(Int, Int)] = []88            if scope.forcePairSingles && n == 1 && m == 1 && comparable(a0, b0) {89                pairs = [(a0, b0)]90            } else if n * m <= ComparisonTuning.optimalPairingCells {91                // Order-preserving pairing that maximises the total similarity of the pairs above the threshold.92                var w = [Double](repeating: 0, count: n * m)93                for i in 0..<n { for j in 0..<m { let s = similarity(a0 + i, b0 + j); w[i * m + j] = s >= ComparisonTuning.modifiedSimilarity ? s : 0 } }94                var dp = [Double](repeating: 0, count: (n + 1) * (m + 1))95                for i in stride(from: n - 1, through: 0, by: -1) {96                    for j in stride(from: m - 1, through: 0, by: -1) {97                        var best = max(dp[(i + 1) * (m + 1) + j], dp[i * (m + 1) + j + 1])98                        if w[i * m + j] > 0 { best = max(best, w[i * m + j] + dp[(i + 1) * (m + 1) + j + 1]) }99                        dp[i * (m + 1) + j] = best100                    }101                }102                var i = 0, j = 0103                while i < n && j < m {104                    let here = dp[i * (m + 1) + j]105                    if w[i * m + j] > 0 && here == w[i * m + j] + dp[(i + 1) * (m + 1) + j + 1] { pairs.append((a0 + i, b0 + j)); i += 1; j += 1 }106                    else if here == dp[(i + 1) * (m + 1) + j] { i += 1 } else { j += 1 }107                }108            } else {109                var next = b0110                for i in a0..<a1 where next < b1 {111                    var bestJ = -1112                    var best = 0.0113                    for j in next..<min(b1, next + ComparisonTuning.pairingWindow) {114                        let s = similarity(i, j)115                        if s >= ComparisonTuning.modifiedSimilarity && s > best { best = s; bestJ = j }116                    }117                    if bestJ >= 0 { pairs.append((i, bestJ)); next = bestJ + 1 }118                }119            }120            var i = a0, j = b0121            for (pi, pj) in pairs {122                while i < pi { entries.append(.deleted(i)); i += 1 }123                while j < pj { entries.append(.inserted(j)); j += 1 }124                entries.append(.modified(pi, pj))125                i = pi + 1; j = pj + 1126            }127            while i < a1 { entries.append(.deleted(i)); i += 1 }128            while j < b1 { entries.append(.inserted(j)); j += 1 }129        }130        var pa = 0, pb = 0131        for (mi, mj) in matches {132            gap(pa, mi, pb, mj)133            entries.append(.equal(mi, mj))134            pa = mi + 1; pb = mj + 1135        }136        gap(pa, A.count, pb, B.count)137138        // 2. Moves among the blocks left as deleted and inserted.139        var movedTo: [Int: Int] = [:]      // original index → revised index140        var movedFrom: [Int: Int] = [:]    // revised index → original index141        var fuzzyMoves: Set<Int> = []      // revised indexes of moves with edits142        if scope.isBody && options.detectMoves {143            var deleted: [Int] = [], inserted: [Int] = []144            for e in entries {145                switch e {146                case .deleted(let i): if case .paragraph = A[i] { deleted.append(i) }147                case .inserted(let j): if case .paragraph = B[j] { inserted.append(j) }148                default: break149                }150            }151            if !deleted.isEmpty && !inserted.isEmpty {152                func substantial(_ p: Paragraph, _ minLength: Int, _ minWords: Int) -> Bool {153                    let t = p.visibleText.trimmingCharacters(in: .whitespacesAndNewlines)154                    return t.utf16.count >= minLength && Tokenizer.quickWordCount(t) >= minWords155                }156                var waiting: [Int: [Int]] = [:]157                for j in inserted.reversed() { waiting[keysB[j], default: []].append(j) }   // popLast yields the earliest158                var restDeleted: [Int] = []159                for i in deleted {160                    if case .paragraph(let p) = A[i], substantial(p, ComparisonTuning.moveMinLength, ComparisonTuning.moveMinWords),161                       let j = waiting[keysA[i]]?.popLast() {162                        movedTo[i] = j; movedFrom[j] = i163                    } else { restDeleted.append(i) }164                }165                let restInserted = inserted.filter { movedFrom[$0] == nil }166                if !restDeleted.isEmpty && !restInserted.isEmpty && restDeleted.count * restInserted.count <= ComparisonTuning.fuzzyMoveMaxPairs {167                    let candidatesB = restInserted.filter { j in168                        if case .paragraph(let p) = B[j] { return substantial(p, ComparisonTuning.fuzzyMoveMinLength, ComparisonTuning.fuzzyMoveMinWords) }169                        return false170                    }171                    for i in restDeleted {172                        guard case .paragraph(let p) = A[i], substantial(p, ComparisonTuning.fuzzyMoveMinLength, ComparisonTuning.fuzzyMoveMinWords) else { continue }173                        var bestJ = -1174                        var best = 0.0175                        for j in candidatesB where movedFrom[j] == nil {176                            let s = similarity(i, j)177                            if s >= ComparisonTuning.fuzzyMoveSimilarity && s > best { best = s; bestJ = j }178                        }179                        if bestJ >= 0 { movedTo[i] = bestJ; movedFrom[bestJ] = i; fuzzyMoves.insert(bestJ) }180                    }181                }182            }183        }184185        // 3. Merged blocks, rows and changes.186        var out = BlockListResult()187        out.merged.reserveCapacity(entries.count)188        out.rows.reserveCapacity(entries.count)189        let before = changes.count190        for e in entries {191            switch e {192            case .equal(let i, let j), .modified(let i, let j):193                let count = changes.count194                switch (A[i], B[j]) {195                case let (.paragraph(x), .paragraph(y)):196                    out.merged.append(.paragraph(comparePair(x, y, i, j, scope: scope, ta: tokA[i], tb: tokB[j])))197                    out.rows.append(AlignedRow(kind: changes.count == count ? .equal : .modified, original: i, revised: j, merged: out.merged.count - 1))198                case let (.table(x), .table(y)):199                    let blocks = compareTables(x, y, i, j, scope: scope)200                    if blocks.count == 2 {201                        out.merged.append(blocks[0])202                        out.rows.append(AlignedRow(kind: .deleted, original: i, revised: nil, merged: out.merged.count - 1))203                        out.merged.append(blocks[1])204                        out.rows.append(AlignedRow(kind: .inserted, original: nil, revised: j, merged: out.merged.count - 1))205                    } else {206                        out.merged.append(contentsOf: blocks)207                        out.rows.append(AlignedRow(kind: changes.count == count ? .equal : .modified, original: i, revised: j, merged: out.merged.count - 1))208                    }209                default:210                    compareAtomic(A[i], B[j], i, j, scope: scope)211                    out.merged.append(B[j])212                    out.rows.append(AlignedRow(kind: changes.count == count ? .equal : .modified, original: i, revised: j, merged: out.merged.count - 1))213                }214            case .deleted(let i):215                let text = Excerpt.short(Excerpt.display(A[i]))216                switch A[i] {217                case .paragraph(let p):218                    let words = Tokenizer.quickWordCount(p.visibleText)219                    out.merged.append(.paragraph(marked(p, .deletion, fromOriginal: true)))220                    if let j = movedTo[i] {221                        wordsMoved += words222                        out.rows.append(AlignedRow(kind: .movedFrom, original: i, revised: j, merged: out.merged.count - 1))223                    } else {224                        wordsDeleted += words225                        add(.deleted, scope: scope, original: i, revised: nil, before: text, detail: "Paragraph deleted")226                        out.rows.append(AlignedRow(kind: .deleted, original: i, revised: nil, merged: out.merged.count - 1))227                    }228                case .table(let t):229                    wordsDeleted += words(of: t)230                    out.merged.append(.table(marked(t, .deletion, fromOriginal: true)))231                    add(.deleted, scope: scope, original: i, revised: nil, before: text, detail: "Table deleted (\(t.rows.count) rows × \(t.columnCount) columns)")232                    out.rows.append(AlignedRow(kind: .deleted, original: i, revised: nil, merged: out.merged.count - 1))233                default:234                    // The model has no tracked deletion for breaks and generated blocks: reported, not kept in the merged document.235                    add(.structure, scope: scope, original: i, revised: nil, before: text, detail: "\(atomicName(A[i])) removed")236                    out.rows.append(AlignedRow(kind: .deleted, original: i, revised: nil, merged: nil))237                }238            case .inserted(let j):239                let text = Excerpt.short(Excerpt.display(B[j]))240                switch B[j] {241                case .paragraph(let p):242                    out.merged.append(.paragraph(marked(p, .insertion, fromOriginal: false)))243                    if let i = movedFrom[j] {244                        let fuzzy = fuzzyMoves.contains(j)245                        add(.moved, scope: scope, original: i, revised: j, before: Excerpt.short(Excerpt.display(A[i])), after: text,246                            detail: "Paragraph moved from block \(i + 1) to block \(j + 1)" + (fuzzy ? ", with edits" : ""))247                        out.rows.append(AlignedRow(kind: .movedTo, original: i, revised: j, merged: out.merged.count - 1))248                    } else {249                        wordsInserted += Tokenizer.quickWordCount(p.visibleText)250                        add(.inserted, scope: scope, original: nil, revised: j, after: text, detail: "Paragraph inserted")251                        out.rows.append(AlignedRow(kind: .inserted, original: nil, revised: j, merged: out.merged.count - 1))252                    }253                case .table(let t):254                    wordsInserted += words(of: t)255                    out.merged.append(.table(marked(t, .insertion, fromOriginal: false)))256                    add(.inserted, scope: scope, original: nil, revised: j, after: text, detail: "Table inserted (\(t.rows.count) rows × \(t.columnCount) columns)")257                    out.rows.append(AlignedRow(kind: .inserted, original: nil, revised: j, merged: out.merged.count - 1))258                default:259                    out.merged.append(B[j])260                    add(.structure, scope: scope, original: nil, revised: j, after: text, detail: "\(atomicName(B[j])) inserted")261                    out.rows.append(AlignedRow(kind: .inserted, original: nil, revised: j, merged: out.merged.count - 1))262                }263            }264        }265        out.changed = changes.count != before266        return out267    }268269    func words(of t: Table) -> Int {270        var n = 0271        for row in t.rows { for cell in row.cells { for p in cell.paragraphs { n += Tokenizer.quickWordCount(p.visibleText) } } }272        return n273    }274275    private func atomicName(_ b: Block) -> String {276        switch b {277        case .pageBreak(let br): return br.kind == .page ? "Page break" : "Column break"278        case .sectionBreak: return "Section break"279        case .toc(let t): return t.kind == .contents ? "Table of contents" : (t.kind == .figures ? "List of figures" : "List of tables")280        case .bibliography: return "Bibliography"281        case .paragraph: return "Paragraph"282        case .table: return "Table"283        }284    }285286    private func compareAtomic(_ a: Block, _ b: Block, _ i: Int, _ j: Int, scope: Scope) {287        guard options.compareFormatting else { return }288        switch (a, b) {289        case let (.sectionBreak(x), .sectionBreak(y)):290            if x.kind != y.kind { add(.structure, scope: scope, original: i, revised: j, before: x.kind.rawValue, after: y.kind.rawValue, detail: "Section break \(x.kind.rawValue) → \(y.kind.rawValue)") }291        case let (.toc(x), .toc(y)):292            var notes: [String] = []293            if x.title != y.title { notes.append("title “\(x.title ?? "")” → “\(y.title ?? "")”") }294            if x.maxLevel != y.maxLevel { notes.append("depth \(x.maxLevel) → \(y.maxLevel)") }295            if !notes.isEmpty { add(.structure, scope: scope, original: i, revised: j, before: x.title ?? "", after: y.title ?? "", detail: "Generated list: " + notes.joined(separator: "; ")) }296        case let (.bibliography(x), .bibliography(y)):297            if x.title != y.title { add(.structure, scope: scope, original: i, revised: j, before: x.title ?? "", after: y.title ?? "", detail: "Bibliography title changed") }298        default: break299        }300    }301302    /// Compares two paragraphs that face each other and returns the merged paragraph (the revised one, with tracked changes).303    func comparePair(_ a: Paragraph, _ b: Paragraph, _ i: Int, _ j: Int, scope: Scope, ta: [Token]? = nil, tb: [Token]? = nil) -> Paragraph {304        if a.runs == b.runs && a.style == b.style && a.props == b.props && a.list == b.list {305            wordsEqual += Tokenizer.quickWordCount(b.visibleText)306            return b307        }308        let d = diff(a, b, ta: ta, tb: tb)309        wordsEqual += d.wordsEqual; wordsInserted += d.wordsInserted; wordsDeleted += d.wordsDeleted310        var merged = b311        merged.runs = d.runs312        merged.markRevision = nil313        let textA = Excerpt.display(a), textB = Excerpt.display(b)314        if d.textChanged {315            let (x, y) = Excerpt.pair(textA, textB)316            var parts: [String] = []317            if d.wordsInserted > 0 { parts.append("\(d.wordsInserted) word\(d.wordsInserted == 1 ? "" : "s") inserted") }318            if d.wordsDeleted > 0 { parts.append("\(d.wordsDeleted) word\(d.wordsDeleted == 1 ? "" : "s") deleted") }319            add(.modified, scope: scope, original: i, revised: j, before: x, after: y, detail: parts.isEmpty ? "Punctuation or spacing changed" : parts.joined(separator: ", "))320        }321        if options.compareFormatting {322            let shortB = Excerpt.short(textB)323            var notes = d.formatNotes324            if a.style != b.style {325                add(.style, scope: scope, original: i, revised: j, before: Excerpt.short(textA), after: shortB, detail: "Style \(a.style) → \(b.style)")326                if a.props != b.props { notes.append(contentsOf: FormatDescription.paragraph(ResolvedPara(a.props), ResolvedPara(b.props))) }327            } else if a.props != b.props, let o = original, let r = revised {328                notes.append(contentsOf: FormatDescription.paragraph(o.styles.paraProps(style: a.style, direct: a.props), r.styles.paraProps(style: b.style, direct: b.props)))329            } else if a.props != b.props {330                notes.append(contentsOf: FormatDescription.paragraph(ResolvedPara(a.props), ResolvedPara(b.props)))331            }332            if let l = FormatDescription.list(a.list, b.list) { notes.append(l) }333            if !notes.isEmpty {334                var unique: [String] = []335                for n in notes where !unique.contains(n) { unique.append(n) }336                add(.formatting, scope: scope, original: i, revised: j, before: Excerpt.short(textA), after: shortB, detail: unique.joined(separator: "; "))337            }338        }339        for (x, y) in d.notePairs { compareNotes(x, y, hostOriginal: i, hostRevised: j, scope: scope) }340        return merged341    }342343    /// Compares the content of two notes whose references face each other; the merged note is stored under the revised id.344    func compareNotes(_ aID: String, _ bID: String, hostOriginal: Int?, hostRevised: Int?, scope: Scope) {345        guard !comparedNotes.contains(bID), let o = original, let r = revised, let na = o.notes[aID], let nb = r.notes[bID] else { return }346        comparedNotes.insert(bID)347        if na.paragraphs == nb.paragraphs { return }348        var s = Scope(story: .note(bID), label: nb.kind == .footnote ? "Footnote" : "Endnote")349        s.fixedOriginal = scope.isBody ? hostOriginal : scope.fixedOriginal350        s.fixedRevised = scope.isBody ? hostRevised : scope.fixedRevised351        let res = compareBlocks(na.paragraphs.map { .paragraph($0) }, nb.paragraphs.map { .paragraph($0) }, scope: s)352        var note = nb353        note.paragraphs = res.merged.compactMap(\.paragraph)354        mergedNotes[bID] = note355    }356}357
Files main
Menu

Theme