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