SPB Git

Repository Public

CanvasMerge.swift 10.6 KB 203 lines swift

1// SP Notes Core2// File: Sources/SPNotesDocument/CanvasMerge.swift3// Description: Three-way merge of canvases by node and edge id. Edits of different elements combine; an element4//              edited differently on both sides is reported as a conflict and nothing is lost.5//6// Author: Simon-Pierre Boucher7// Contact: contact@spboucher.ai8import Foundation910/// One element the merge could not settle. The merged canvas holds one version; the others are carried here.11public struct CanvasConflict: Sendable, Hashable {12    public enum Kind: String, Sendable, Hashable { case node, edge, field }1314    public enum Reason: String, Sendable, Hashable {15        /// Changed differently on both sides (or added on both sides with different values).16        case bothEdited17        /// Deleted on one side, edited on the other. The edited version is the one kept in the merged canvas.18        case editedAndDeleted19        /// A node deleted on one side while the other side attached a new or edited edge to it. The node is20        /// restored in the merged canvas so that the edge stays valid.21        case deletedButReferenced22    }2324    public var kind: Kind25    /// Node id, edge id, or top-level field name.26    public var id: String27    public var reason: Reason28    /// The element in the common ancestor, on this device and on the server (nil = absent / deleted).29    public var base: JSONValue?30    public var local: JSONValue?31    public var remote: JSONValue?3233    public init(kind: Kind, id: String, reason: Reason, base: JSONValue?, local: JSONValue?, remote: JSONValue?) {34        self.kind = kind35        self.id = id36        self.reason = reason37        self.base = base38        self.local = local39        self.remote = remote40    }4142    /// The typed versions when the conflict is about a node.43    public var localNode: CanvasNode? { kind == .node ? local.flatMap { try? CanvasNode(json: $0) } : nil }44    public var remoteNode: CanvasNode? { kind == .node ? remote.flatMap { try? CanvasNode(json: $0) } : nil }45    /// The typed versions when the conflict is about an edge.46    public var localEdge: CanvasEdge? { kind == .edge ? local.flatMap { try? CanvasEdge(json: $0) } : nil }47    public var remoteEdge: CanvasEdge? { kind == .edge ? remote.flatMap { try? CanvasEdge(json: $0) } : nil }48}4950/// Result of `CanvasDocument.merge`.51public struct CanvasMergeResult: Sendable, Hashable {52    /// Always a usable canvas: on a conflict it holds the local version of the element (or the surviving one53    /// when the other side deleted it).54    public var merged: CanvasDocument55    public var conflicts: [CanvasConflict]56    /// Whether everything combined without conflict.57    public var isClean: Bool { conflicts.isEmpty }58}5960extension CanvasDocument {61    /// Three-way merge by element id.62    ///63    /// - An element (node, edge) or top-level field added, changed or deleted on one side only is taken; the same64    ///   change on both sides is taken once.65    /// - Changed differently on both sides: the merged canvas keeps the LOCAL version and the conflict carries both.66    /// - Edited on one side, deleted on the other: the merged canvas keeps the EDITED version (so no work67    ///   disappears silently) and the conflict records which side deleted it.68    /// - An edge left without one of its ends because a side deleted the node: dropped when that edge is unchanged69    ///   since the base (it would have been removed with the node); when the other side created or edited the edge,70    ///   the node is restored from the base and a `.deletedButReferenced` conflict is reported.71    /// - Viewport (per-device view state): local wins unless only the remote changed; never a conflict.72    /// - Order: base order, then the elements added by either side sorted by id, so a clean merge gives the same73    ///   bytes whichever side is called local. Stacking is decided by `z`, not by the order.74    /// - When a side equals the base the other side is returned untouched; when both sides are equal, that value.75    ///76    /// Elements sharing an id inside one canvas: the first occurrence counts.77    public static func merge(base: CanvasDocument, local: CanvasDocument, remote: CanvasDocument) -> CanvasMergeResult {78        if local == remote || remote == base { return CanvasMergeResult(merged: local, conflicts: []) }79        if local == base { return CanvasMergeResult(merged: remote, conflicts: []) }8081        var conflicts: [CanvasConflict] = []8283        func mergeElements(_ kind: CanvasConflict.Kind, _ b: [(String, JSONValue)], _ l: [(String, JSONValue)], _ r: [(String, JSONValue)]) -> [(String, JSONValue)] {84            let bm = Dictionary(b, uniquingKeysWith: { first, _ in first })85            let lm = Dictionary(l, uniquingKeysWith: { first, _ in first })86            let rm = Dictionary(r, uniquingKeysWith: { first, _ in first })87            func resolve(_ id: String) -> JSONValue? {88                let bv = bm[id], lv = lm[id], rv = rm[id]89                if lv == rv { return lv }90                if lv == bv { return rv }91                if rv == bv { return lv }92                if let lv, let rv {93                    conflicts.append(CanvasConflict(kind: kind, id: id, reason: .bothEdited, base: bv, local: lv, remote: rv))94                    return lv95                }96                conflicts.append(CanvasConflict(kind: kind, id: id, reason: .editedAndDeleted, base: bv, local: lv, remote: rv))97                return lv ?? rv98            }99            var out: [(String, JSONValue)] = []100            var seen = Set<String>()101            for (id, _) in b where seen.insert(id).inserted {102                if let v = resolve(id) { out.append((id, v)) }103            }104            let added = Set(l.map(\.0)).union(r.map(\.0)).subtracting(seen)105            for id in added.sorted(by: { $0.unicodeScalars.lexicographicallyPrecedes($1.unicodeScalars) }) {106                if let v = resolve(id) { out.append((id, v)) }107            }108            return out109        }110111        func nodePairs(_ d: CanvasDocument) -> [(String, JSONValue)] { d.nodes.map { ($0.id, $0.jsonValue) } }112        func edgePairs(_ d: CanvasDocument) -> [(String, JSONValue)] { d.edges.map { ($0.id, $0.jsonValue) } }113114        var nodes = mergeElements(.node, nodePairs(base), nodePairs(local), nodePairs(remote))115        var edges = mergeElements(.edge, edgePairs(base), edgePairs(local), edgePairs(remote))116117        // Edges whose end was deleted by a side.118        let baseNodes = Dictionary(nodePairs(base), uniquingKeysWith: { first, _ in first })119        let baseEdges = Dictionary(edgePairs(base), uniquingKeysWith: { first, _ in first })120        let localNodeIds = Set(local.nodes.map(\.id)), remoteNodeIds = Set(remote.nodes.map(\.id))121        var present = Set(nodes.map(\.0))122        var restored: [String] = []123        var kept: [(String, JSONValue)] = []124        for (id, value) in edges {125            let ends = [value["from"]?.stringValue, value["to"]?.stringValue].compactMap { $0 }126            let missing = ends.filter { !present.contains($0) && baseNodes[$0] != nil }127            if missing.isEmpty { kept.append((id, value)); continue }128            if baseEdges[id] == value { continue } // untouched edge of a deleted node: goes with it129            for nodeId in missing where !present.contains(nodeId) {130                present.insert(nodeId)131                restored.append(nodeId)132                conflicts.append(CanvasConflict(kind: .node, id: nodeId, reason: .deletedButReferenced, base: baseNodes[nodeId],133                                                local: localNodeIds.contains(nodeId) ? baseNodes[nodeId] : nil,134                                                remote: remoteNodeIds.contains(nodeId) ? baseNodes[nodeId] : nil))135            }136            kept.append((id, value))137        }138        edges = kept139        if !restored.isEmpty {140            // Back at their base position among the base elements.141            let want = present142            var seen = Set<String>()143            var ordered: [(String, JSONValue)] = []144            let current = Dictionary(nodes, uniquingKeysWith: { first, _ in first })145            for n in base.nodes where want.contains(n.id) && seen.insert(n.id).inserted {146                ordered.append((n.id, current[n.id] ?? n.jsonValue))147            }148            for (id, v) in nodes where seen.insert(id).inserted { ordered.append((id, v)) }149            nodes = ordered150        }151152        // Top-level fields.153        var fields: [String: JSONValue] = [:]154        let keys = Set(base.fields.keys).union(local.fields.keys).union(remote.fields.keys)155        for key in keys.sorted() {156            let bv = base.fields[key], lv = local.fields[key], rv = remote.fields[key]157            let value: JSONValue?158            if lv == rv || rv == bv { value = lv }159            else if lv == bv { value = rv }160            else {161                value = lv162                if key != "viewport" {163                    conflicts.append(CanvasConflict(kind: .field, id: key, reason: lv == nil || rv == nil ? .editedAndDeleted : .bothEdited,164                                                    base: bv, local: lv, remote: rv))165                }166            }167            if let value { fields[key] = value }168        }169        fields["format"] = .string(CanvasDocument.format)170171        var merged = CanvasDocument()172        merged.fields = fields173        // The values come from valid elements, so the typed initialisers cannot fail.174        merged.nodes = nodes.compactMap { try? CanvasNode(json: $0.1) }175        merged.edges = edges.compactMap { try? CanvasEdge(json: $0.1) }176        return CanvasMergeResult(merged: merged, conflicts: conflicts)177    }178179    /// The canvas with one conflict settled with the remote version (`merge` keeps the local one): the element180    /// is replaced by, or removed like, the conflict's `remote` value.181    public func resolving(_ conflict: CanvasConflict, takingRemote: Bool) -> CanvasDocument {182        var out = self183        let value = takingRemote ? conflict.remote : conflict.local184        switch conflict.kind {185        case .node:186            if let value, let node = try? CanvasNode(json: value) {187                if let i = out.nodes.firstIndex(where: { $0.id == conflict.id }) { out.nodes[i] = node } else { out.nodes.append(node) }188            } else {189                out.removeNode(id: conflict.id)190            }191        case .edge:192            if let value, let edge = try? CanvasEdge(json: value) {193                if let i = out.edges.firstIndex(where: { $0.id == conflict.id }) { out.edges[i] = edge } else { out.edges.append(edge) }194            } else {195                out.removeEdge(id: conflict.id)196            }197        case .field:198            if conflict.id != "format" { out.fields[conflict.id] = value }199        }200        return out201    }202}203
Files main
Menu

Theme