Repository Public
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