SPB Git

Repository Public

Merge.swift 7.0 KB 139 lines swift

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

Theme