Repository Public
1// SP Notes Core2// File: Sources/SPNotesDocument/Merge.swift3// Description: Conservative three-way merge of notes by top-level block identity: a diff3 over the sequences of4// block ids plus a per-block content rule; anything ambiguous is a conflict.5//6// Author: Simon-Pierre Boucher7// Contact: contact@spboucher.ai8import Foundation910enum Merger {11 struct Block {12 var identity: String13 var node: PMNode14 var canonical: String15 }1617 /// Top-level blocks with their identity: the block id, or the content (plus occurrence rank) when there is none.18 /// Nil when two blocks carry the same id.19 static func blocks(_ doc: NoteDocument) -> [Block]? {20 var out: [Block] = []21 var seen = Set<String>()22 var occurrences: [String: Int] = [:]23 for node in doc.pmNode().content ?? [] {24 let canonical = node.jsonValue.canonicalString()25 let identity: String26 if let id = BlockID.usable(node.attrs?["id"]) {27 identity = "id:" + id28 } else {29 let n = occurrences[canonical, default: 0]30 occurrences[canonical] = n + 131 identity = "content:\(n):" + canonical32 }33 guard seen.insert(identity).inserted else { return nil }34 out.append(Block(identity: identity, node: node, canonical: canonical))35 }36 return out37 }3839 /// For each index of `a`, the index of its partner in `b` along a longest common subsequence (nil when unmatched).40 static func lcsMatches(_ a: [String], _ b: [String]) -> [Int?] {41 var match = [Int?](repeating: nil, count: a.count)42 var lo = 043 while lo < a.count, lo < b.count, a[lo] == b[lo] { match[lo] = lo; lo += 1 }44 var ha = a.count, hb = b.count45 while ha > lo, hb > lo, a[ha - 1] == b[hb - 1] { ha -= 1; hb -= 1; match[ha] = hb }46 let n = ha - lo, m = hb - lo47 guard n > 0, m > 0 else { return match }48 var table = [[Int32]](repeating: [Int32](repeating: 0, count: m + 1), count: n + 1)49 for i in stride(from: n - 1, through: 0, by: -1) {50 for j in stride(from: m - 1, through: 0, by: -1) {51 table[i][j] = a[lo + i] == b[lo + j] ? table[i + 1][j + 1] + 1 : max(table[i + 1][j], table[i][j + 1])52 }53 }54 var i = 0, j = 055 while i < n, j < m {56 if a[lo + i] == b[lo + j] { match[lo + i] = lo + j; i += 1; j += 1 }57 else if table[i + 1][j] >= table[i][j + 1] { i += 1 } else { j += 1 }58 }59 return match60 }6162 /// diff3 over identity sequences; nil on an ordering conflict.63 static func mergeOrder(base: [String], mine: [String], theirs: [String]) -> [String]? {64 let mm = lcsMatches(base, mine), mt = lcsMatches(base, theirs)65 var out: [String] = []66 var b = 0, m = 0, t = 067 while true {68 // Stable run: base, mine and theirs agree position by position.69 while b < base.count, mm[b] == m, mt[b] == t { out.append(base[b]); b += 1; m += 1; t += 1 }70 if b == base.count, m == mine.count, t == theirs.count { return out }71 // Unstable chunk up to the next base element matched on both sides.72 var nb = b73 while nb < base.count, !(mm[nb] != nil && mt[nb] != nil && mm[nb]! >= m && mt[nb]! >= t) { nb += 1 }74 let nm = nb < base.count ? mm[nb]! : mine.count75 let nt = nb < base.count ? mt[nb]! : theirs.count76 let cb = Array(base[b..<nb]), cm = Array(mine[m..<nm]), ct = Array(theirs[t..<nt])77 if cm == cb { out += ct } else if ct == cb || cm == ct { out += cm } else { return nil }78 if nb == b, nm == m, nt == t { return nil } // no progress: defensive, cannot happen with monotonic matches79 b = nb; m = nm; t = nt80 }81 }8283 static func merge(base: NoteDocument, mine: NoteDocument, theirs: NoteDocument) -> MergeResult {84 if mine.isStructurallyEqual(to: theirs) { return .merged(mine) }85 if base.isStructurallyEqual(to: mine) { return .merged(theirs) }86 if base.isStructurallyEqual(to: theirs) { return .merged(mine) }87 // The doc node itself (attributes, unknown keys) is merged as a single value.88 func shell(_ d: NoteDocument) -> String {89 var n = d.pmNode()90 n.content = nil91 return n.jsonValue.canonicalString()92 }93 let (sb, sm, st) = (shell(base), shell(mine), shell(theirs))94 guard sm == sb || st == sb || sm == st else { return .conflict }95 let rootSource = sm == sb ? theirs : mine9697 guard let bb = blocks(base), let bm = blocks(mine), let bt = blocks(theirs) else { return .conflict }98 let ib = Dictionary(uniqueKeysWithValues: bb.map { ($0.identity, $0) })99 let im = Dictionary(uniqueKeysWithValues: bm.map { ($0.identity, $0) })100 let it = Dictionary(uniqueKeysWithValues: bt.map { ($0.identity, $0) })101102 // Per-block content rule; `expected` is the exact set of blocks the result must hold.103 var expected: [String: PMNode] = [:]104 for identity in Set(ib.keys).union(im.keys).union(it.keys) {105 switch (ib[identity], im[identity], it[identity]) {106 case (let b?, let m?, let t?):107 if m.canonical == b.canonical { expected[identity] = t.node }108 else if t.canonical == b.canonical || m.canonical == t.canonical { expected[identity] = m.node }109 else { return .conflict }110 case (let b?, let m?, nil):111 if m.canonical != b.canonical { return .conflict } // edited here, deleted there112 case (let b?, nil, let t?):113 if t.canonical != b.canonical { return .conflict }114 case (nil, let m?, let t?):115 if m.canonical != t.canonical { return .conflict }116 expected[identity] = m.node117 case (nil, let m?, nil): expected[identity] = m.node118 case (nil, nil, let t?): expected[identity] = t.node119 default: break // deleted on both sides120 }121 }122 guard let order = mergeOrder(base: bb.map(\.identity), mine: bm.map(\.identity), theirs: bt.map(\.identity)) else { return .conflict }123 // The order must hold every expected block exactly once and nothing else, or a change would be lost.124 guard order.count == expected.count, Set(order).count == order.count, order.allSatisfy({ expected[$0] != nil }) else { return .conflict }125126 var root = rootSource.pmNode()127 let content = order.map { expected[$0]! }128 guard !content.isEmpty else { return .conflict }129 root.content = content130 // Ids must stay unique across the merged blocks (nested ids included).131 var ids = Set<String>()132 var duplicate = false133 TextTools.walk(root) { n in134 if Schema.idTypes.contains(n.type), let id = BlockID.usable(n.attrs?["id"]), !ids.insert(id).inserted { duplicate = true }135 }136 return duplicate ? .conflict : .merged(NoteDocument(node: root))137 }138}139