Repository Public
1// SP Notes Core2// File: Tests/SPNotesDocumentTests/CanvasTests.swift3// Description: The spn-canvas-1 model (lossless round trip, editing helpers), the three-way merge by element id4// (cases, properties, randomised convergence) and the automatic layouts.5//6// Author: Simon-Pierre Boucher7// Contact: contact@spboucher.ai8import Foundation9import CoreGraphics10import Testing11@testable import SPNotesDocument1213func canvasNode(_ id: String, _ x: Double = 0, _ y: Double = 0, w: Double = 100, h: Double = 60, text: String? = nil) -> CanvasNode {14 var n = CanvasNode(id: id, kind: .text, x: x, y: y, w: w, h: h)15 n.text = text ?? id16 return n17}1819@Suite struct CanvasModelTests {20 static let sample = """21 {"format":"spn-canvas-1","theme":{"grid":true,"step":8.0},22 "nodes":[23 {"id":"a","kind":"text","x":10,"y":20.5,"w":200,"h":80,"z":0,"text":"Bonjour","color":null,"locked":true},24 {"id":"b","kind":"shape","x":-300,"y":0,"w":120,"h":120,"z":2,"shape":"diamond","color":"#3157D5"},25 {"id":"c","kind":"hologram","x":1e3,"y":2,"w":3,"h":4,"z":1,"payload":{"deep":[1,{"k":null}]}},26 {"id":"d","kind":"page","x":0,"y":0,"w":10,"h":10,"z":3,"pageId":"7d0e0d3c-0000-4000-8000-000000000001"}27 ],28 "edges":[29 {"id":"e1","from":"a","to":"b","label":"cause","kind":"arrow","color":"#ff0000","weight":3},30 {"id":"e2","from":"b","to":"c"},31 {"id":"e3","from":"c","to":"d","kind":"zigzag","label":null}32 ],33 "viewport":{"x":-12.5,"y":40,"zoom":1.25,"rotation":0}}34 """3536 @Test func roundTripIsLossless() throws {37 let source = try JSONValue(jsonString: Self.sample)38 let doc = try CanvasDocument(data: Data(Self.sample.utf8))39 let out = try JSONValue(data: doc.jsonData())40 #expect(out.semanticallyEquals(source))41 // Absent optional keys stay absent, explicit nulls stay null, integers stay integers.42 let text = String(decoding: doc.jsonData(), as: UTF8.self)43 #expect(text.contains(#"{"from":"b","id":"e2","to":"c"}"#))44 #expect(text.contains(#""color":null"#) && text.contains(#""label":null"#))45 #expect(text.contains(#""x":1000"#) && text.contains(#""y":20.5"#) && text.contains(#""step":8"#))46 #expect(try CanvasDocument(data: doc.jsonData()) == doc)47 #expect(try JSONDecoder().decode(CanvasDocument.self, from: JSONEncoder().encode(doc)) == doc)48 }4950 @Test func typedAccess() throws {51 var doc = try CanvasDocument(data: Data(Self.sample.utf8))52 let a = try #require(doc.node(id: "a"))53 #expect(a.kind == .text && a.x == 10 && a.y == 20.5 && a.w == 200 && a.h == 80 && a.z == 0 && a.text == "Bonjour")54 #expect(a.color == nil && a["color"] == .null && a["locked"] == true && a.pageId == nil && a.shape == nil)55 #expect(a.frame == CGRect(x: 10, y: 20.5, width: 200, height: 80) && a.center == CGPoint(x: 110, y: 60.5))56 #expect(doc.node(id: "b")?.shape == .diamond && doc.node(id: "b")?.kind == .shape)57 let c = try #require(doc.node(id: "c"))58 #expect(c.kind.rawValue == "hologram" && !c.kind.isKnown && c.x == 1000)59 #expect(doc.node(id: "d")?.pageId == "7d0e0d3c-0000-4000-8000-000000000001")60 let e1 = try #require(doc.edge(id: "e1"))61 #expect(e1.from == "a" && e1.to == "b" && e1.label == "cause" && e1.kind == .arrow && e1.color == "#ff0000" && e1["weight"] == 3)62 #expect(doc.edge(id: "e2")?.kind == nil && doc.edge(id: "e2")?.label == nil)63 #expect(doc.edge(id: "e3")?.kind?.isKnown == false)64 #expect(doc.viewport.x == -12.5 && doc.viewport.y == 40 && doc.viewport.zoom == 1.25)65 #expect(doc["theme"]?["grid"] == true)6667 doc.updateNode(id: "a") { $0.x = 11; $0.text = nil; $0.latex = "x^2"; $0["locked"] = nil }68 doc.viewport.zoom = 269 let out = try JSONValue(data: doc.jsonData())70 #expect(out["nodes"]?.arrayValue?[0] == ["id": "a", "kind": "text", "x": 11, "y": 20.5, "w": 200, "h": 80, "z": 0, "color": .null, "latex": "x^2"])71 #expect(out["viewport"] == ["x": -12.5, "y": 40, "zoom": 2, "rotation": 0])72 // The id cannot be changed through the subscript.73 doc.updateNode(id: "a") { $0["id"] = "zzz" }74 #expect(doc.node(id: "a") != nil)75 }7677 @Test func emptyAndTolerantReading() throws {78 #expect(String(decoding: CanvasDocument.empty.jsonData(), as: UTF8.self) ==79 #"{"edges":[],"format":"spn-canvas-1","nodes":[],"viewport":{"x":0,"y":0,"zoom":1}}"#)80 let bare = try CanvasDocument(data: Data(#"{"format":"spn-canvas-1"}"#.utf8))81 #expect(bare.nodes.isEmpty && bare.edges.isEmpty && bare.viewport == CanvasViewport() && bare.bounds.isNull)82 #expect(try CanvasDocument(data: Data(#"{"format":"spn-canvas-1","viewport":{"zoom":0}}"#.utf8)).viewport.zoom == 1)83 #expect(throws: CanvasError.unsupportedFormat("spn-canvas-9")) { try CanvasDocument(data: Data(#"{"format":"spn-canvas-9"}"#.utf8)) }84 #expect(throws: CanvasError.unsupportedFormat(nil)) { try CanvasDocument(data: Data("{}".utf8)) }85 #expect(throws: CanvasError.self) { try CanvasDocument(data: Data(#"{"format":"spn-canvas-1","nodes":{}}"#.utf8)) }86 #expect(throws: CanvasError.self) { try CanvasDocument(data: Data(#"{"format":"spn-canvas-1","nodes":[{"kind":"text"}]}"#.utf8)) }87 #expect(throws: CanvasError.self) { try CanvasDocument(data: Data(#"{"format":"spn-canvas-1","edges":[7]}"#.utf8)) }88 #expect(throws: DocumentError.self) { try CanvasDocument(data: Data("nope".utf8)) }89 }9091 @Test func editingHelpers() throws {92 var doc = CanvasDocument.empty93 check(doc.addNode(canvasNode("a", 0, 0)))94 check(doc.addNode(canvasNode("b", 200, 0)))95 check(doc.addNode(canvasNode("c", 50, 30)))96 check(!doc.addNode(canvasNode("a", 9, 9)))97 #expect(doc.nodes.map(\.z) == [0, 1, 2])98 check(doc.addEdge(CanvasEdge(id: "ab", from: "a", to: "b", label: "x")))99 check(doc.addEdge(CanvasEdge(id: "bc", from: "b", to: "c", kind: .line)))100 check(!doc.addEdge(CanvasEdge(id: "ab", from: "a", to: "c")))101 check(!doc.addEdge(CanvasEdge(id: "ax", from: "a", to: "missing")))102 #expect(doc.edges(of: "b").map(\.id) == ["ab", "bc"] && doc.danglingEdges.isEmpty)103 #expect(doc.bounds == CGRect(x: 0, y: 0, width: 300, height: 90))104 #expect(doc.nodes(in: CGRect(x: 60, y: 40, width: 10, height: 10)).map(\.id) == ["a", "c"])105 #expect(doc.node(at: CGPoint(x: 60, y: 40))?.id == "c")106 check(doc.sendToBack(id: "c"))107 #expect(doc.node(at: CGPoint(x: 60, y: 40))?.id == "a" && doc.nodesBackToFront.map(\.id) == ["c", "a", "b"])108 check(doc.bringToFront(id: "c"))109 #expect(doc.nodesBackToFront.map(\.id) == ["a", "b", "c"])110 doc.normalizeZ()111 #expect(doc.nodes.map(\.z) == [0, 1, 2])112 check(!doc.bringToFront(id: "nope") && !doc.sendToBack(id: "nope") && !doc.updateNode(id: "nope") { _ in })113 check(doc.updateEdge(id: "ab") { $0.label = nil; $0.color = "#000000" })114 #expect(doc.edge(id: "ab")?.jsonValue == ["id": "ab", "from": "a", "to": "b", "color": "#000000"])115 #expect(doc.removeNode(id: "b") == ["ab", "bc"])116 #expect(doc.nodes.map(\.id) == ["a", "c"] && doc.edges.isEmpty && doc.removeNode(id: "b") == nil)117 check(doc.addEdge(CanvasEdge(id: "ac", from: "a", to: "c")))118 check(doc.removeEdge(id: "ac") && !doc.removeEdge(id: "ac"))119 }120}121122@Suite struct CanvasMergeTests {123 var base: CanvasDocument {124 var d = CanvasDocument.empty125 for (i, id) in ["a", "b", "c", "d"].enumerated() { d.addNode(canvasNode(id, Double(i) * 200, 0)) }126 d.addEdge(CanvasEdge(id: "ab", from: "a", to: "b"))127 d.addEdge(CanvasEdge(id: "cd", from: "c", to: "d"))128 return d129 }130 func edit(_ d: CanvasDocument, _ change: (inout CanvasDocument) -> Void) -> CanvasDocument {131 var d = d132 change(&d)133 return d134 }135 func merge(_ l: CanvasDocument, _ r: CanvasDocument) -> CanvasMergeResult { CanvasDocument.merge(base: base, local: l, remote: r) }136137 @Test func trivialCases() {138 let x = edit(base) { $0.updateNode(id: "a") { $0.text = "A" }; $0.removeNode(id: "d"); $0.addNode(canvasNode("n")) }139 #expect(merge(x, base) == CanvasMergeResult(merged: x, conflicts: []))140 #expect(merge(base, x) == CanvasMergeResult(merged: x, conflicts: []))141 #expect(merge(x, x) == CanvasMergeResult(merged: x, conflicts: []))142 #expect(merge(base, base).merged == base && merge(base, base).isClean)143 // The same change against an unrelated base.144 #expect(CanvasDocument.merge(base: .empty, local: x, remote: x).merged == x)145 }146147 @Test func differentElementsCombine() throws {148 let l = edit(base) {149 $0.updateNode(id: "a") { $0.x = 5; $0.text = "A" }150 $0.addNode(canvasNode("l1", 0, 300))151 $0.addEdge(CanvasEdge(id: "al1", from: "a", to: "l1"))152 $0.removeEdge(id: "ab")153 }154 let r = edit(base) {155 $0.updateNode(id: "b") { $0.color = "#ff0000" }156 $0.addNode(canvasNode("r1", 0, 600))157 $0.updateEdge(id: "cd") { $0.label = "puis" }158 $0["theme"] = "dark"159 }160 let m = merge(l, r)161 #expect(m.isClean)162 #expect(m.merged.nodes.map(\.id) == ["a", "b", "c", "d", "l1", "r1"])163 #expect(m.merged.edges.map(\.id) == ["cd", "al1"])164 #expect(m.merged.node(id: "a") == l.node(id: "a") && m.merged.node(id: "b") == r.node(id: "b"))165 #expect(m.merged.edge(id: "cd")?.label == "puis" && m.merged["theme"] == "dark")166 // Whichever side is called local, a clean merge gives the same bytes.167 #expect(merge(r, l).merged.jsonData() == m.merged.jsonData())168 // Both sides making the same change is not a conflict.169 let same = edit(base) { $0.updateNode(id: "c") { $0.y = 9 }; $0.removeNode(id: "a") }170 let other = edit(same) { $0.updateNode(id: "d") { $0.w = 1 } }171 #expect(merge(same, other) == CanvasMergeResult(merged: other, conflicts: []))172 // Different fields of the same node are still one element: conflict (per-id granularity).173 #expect(!merge(edit(base) { $0.updateNode(id: "a") { $0.x = 1 } }, edit(base) { $0.updateNode(id: "a") { $0.y = 1 } }).isClean)174 }175176 @Test func sameElementEditedOnBothSidesIsAConflictKeepingBoth() throws {177 let l = edit(base) { $0.updateNode(id: "a") { $0.text = "mine" }; $0.updateEdge(id: "cd") { $0.label = "L" }; $0.updateNode(id: "b") { $0.x = 1 } }178 let r = edit(base) { $0.updateNode(id: "a") { $0.text = "theirs" }; $0.updateEdge(id: "cd") { $0.label = "R" }; $0.updateNode(id: "c") { $0.x = 2 } }179 let m = merge(l, r)180 #expect(m.conflicts.map(\.id) == ["a", "cd"] && m.conflicts.map(\.kind) == [.node, .edge] && m.conflicts.allSatisfy { $0.reason == .bothEdited })181 #expect(m.merged.node(id: "a")?.text == "mine" && m.merged.edge(id: "cd")?.label == "L")182 #expect(m.conflicts[0].localNode?.text == "mine" && m.conflicts[0].remoteNode?.text == "theirs")183 #expect(m.conflicts[0].base == base.node(id: "a")?.jsonValue)184 #expect(m.conflicts[1].localEdge?.label == "L" && m.conflicts[1].remoteEdge?.label == "R" && m.conflicts[1].localNode == nil)185 // The unconflicted edits of both sides are still combined.186 #expect(m.merged.node(id: "b")?.x == 1 && m.merged.node(id: "c")?.x == 2)187 // Settling a conflict with the remote version.188 let settled = m.merged.resolving(m.conflicts[0], takingRemote: true).resolving(m.conflicts[1], takingRemote: true)189 #expect(settled.node(id: "a")?.text == "theirs" && settled.edge(id: "cd")?.label == "R")190 #expect(m.merged.resolving(m.conflicts[0], takingRemote: false) == m.merged)191 // Added on both sides with the same id and different values.192 let both = merge(edit(base) { $0.addNode(canvasNode("n", 1, 1)) }, edit(base) { $0.addNode(canvasNode("n", 2, 2)) })193 #expect(both.conflicts.count == 1 && both.conflicts[0].base == nil && both.merged.node(id: "n")?.x == 1)194 }195196 @Test func editedAndDeletedKeepsTheEditedVersion() throws {197 let edited = edit(base) { $0.updateNode(id: "c") { $0.text = "important" } }198 let deleted = edit(base) { $0.removeNode(id: "c") }199 for (l, r, deletedLocally) in [(edited, deleted, false), (deleted, edited, true)] {200 let m = merge(l, r)201 #expect(m.conflicts.count == 1 && m.conflicts[0].reason == .editedAndDeleted && m.conflicts[0].id == "c")202 #expect((m.conflicts[0].local == nil) == deletedLocally && (m.conflicts[0].remote == nil) == !deletedLocally)203 #expect(m.merged.node(id: "c")?.text == "important")204 // The deleting side removed the edge cd, untouched by the other: it goes, and nothing dangles.205 #expect(m.merged.edge(id: "cd") == nil && m.merged.danglingEdges.isEmpty)206 let gone = m.merged.resolving(m.conflicts[0], takingRemote: !deletedLocally)207 #expect(gone.node(id: "c") == nil)208 }209 let e = merge(edit(base) { $0.removeEdge(id: "ab") }, edit(base) { $0.updateEdge(id: "ab") { $0.label = "x" } })210 #expect(e.conflicts.map(\.reason) == [.editedAndDeleted] && e.merged.edge(id: "ab")?.label == "x")211 }212213 @Test func edgesNeverDangle() throws {214 let deleted = edit(base) { $0.removeNode(id: "d") }215 // The other side attached a NEW edge to the deleted node: the node comes back, reported.216 let linked = edit(base) { $0.addEdge(CanvasEdge(id: "ad", from: "a", to: "d", label: "new")) }217 for (l, r) in [(deleted, linked), (linked, deleted)] {218 let m = merge(l, r)219 #expect(m.conflicts.count == 1 && m.conflicts[0].kind == .node && m.conflicts[0].id == "d" && m.conflicts[0].reason == .deletedButReferenced)220 #expect((m.conflicts[0].local == nil) == (l == deleted) && (m.conflicts[0].remote == nil) == (r == deleted))221 #expect(m.merged.nodes.map(\.id) == ["a", "b", "c", "d"] && m.merged.node(id: "d") == base.node(id: "d"))222 #expect(m.merged.edge(id: "ad")?.label == "new" && m.merged.danglingEdges.isEmpty)223 // cd was removed with the node by one side and untouched by the other: it stays removed.224 #expect(m.merged.edge(id: "cd") == nil)225 }226 // The other side EDITED an edge of the deleted node: edge conflict (edited / deleted), node restored for it.227 let relabeled = edit(base) { $0.updateEdge(id: "cd") { $0.label = "keep" } }228 let m = merge(deleted, relabeled)229 #expect(Set(m.conflicts.map(\.id)) == ["cd", "d"] && m.merged.edge(id: "cd")?.label == "keep" && m.merged.node(id: "d") != nil)230 #expect(m.merged.danglingEdges.isEmpty)231 // A raw deletion that left the edge behind on the deleting side, other side untouched elsewhere: the232 // unchanged edge is dropped silently.233 let raw = edit(base) { $0.nodes.removeAll { $0.id == "d" } }234 let elsewhere = edit(base) { $0.updateNode(id: "a") { $0.x = 77 } }235 let n = merge(raw, elsewhere)236 #expect(n.isClean && n.merged.edge(id: "cd") == nil && n.merged.danglingEdges.isEmpty && n.merged.node(id: "a")?.x == 77)237 }238239 @Test func viewportAndTopLevelFields() throws {240 let lv = edit(base) { $0.viewport = CanvasViewport(x: 1, y: 1, zoom: 2); $0.updateNode(id: "a") { $0.x = 1 } }241 let rv = edit(base) { $0.viewport = CanvasViewport(x: 9, y: 9, zoom: 3); $0.updateNode(id: "b") { $0.x = 1 } }242 #expect(merge(lv, rv).isClean && merge(lv, rv).merged.viewport.zoom == 2)243 let onlyNode = edit(base) { $0.updateNode(id: "a") { $0.x = 1 } }244 #expect(merge(onlyNode, rv).merged.viewport.zoom == 3 && merge(onlyNode, rv).isClean)245246 var b = base247 b["theme"] = "light"248 b["grid"] = 8249 let l = edit(b) { $0["theme"] = "dark"; $0["grid"] = nil; $0["mine"] = 1; $0.updateNode(id: "a") { $0.x = 1 } }250 let r = edit(b) { $0["theme"] = "sepia"; $0["grid"] = 16; $0["theirs"] = [1, 2]; $0.updateNode(id: "b") { $0.x = 1 } }251 let m = CanvasDocument.merge(base: b, local: l, remote: r)252 #expect(m.conflicts.map(\.id) == ["grid", "theme"] && m.conflicts.allSatisfy { $0.kind == .field })253 #expect(m.conflicts.map(\.reason) == [.editedAndDeleted, .bothEdited])254 #expect(m.merged["theme"] == "dark" && m.merged["grid"] == nil && m.merged["mine"] == 1 && m.merged["theirs"] == [1, 2])255 #expect(m.conflicts[1].remote == "sepia")256 #expect(m.merged.resolving(m.conflicts[0], takingRemote: true)["grid"] == 16)257 #expect(m.merged.jsonValue["format"] == "spn-canvas-1")258 }259260 // MARK: Randomised261262 static var seeds: [UInt64] {263 if let only = UInt64(ProcessInfo.processInfo.environment["SPN_RANDOM_ONLY"] ?? "") { return [only] }264 let extra = UInt64(ProcessInfo.processInfo.environment["SPN_RANDOM_SEEDS"] ?? "") ?? 0265 return Array(1...400) + (0..<extra).map { 1000 + $0 }266 }267268 static func randomBase(_ rng: inout SplitMix64) -> CanvasDocument {269 var d = CanvasDocument.empty270 let n = 4 + rng.int(8)271 for i in 0..<n { d.addNode(canvasNode("n\(i)", Double(rng.int(2000)), Double(rng.int(2000)) + 0.5)) }272 for e in 0..<rng.int(n) {273 let a = rng.int(n), b = rng.int(n)274 if a != b { d.addEdge(CanvasEdge(id: "e\(e)", from: "n\(a)", to: "n\(b)", label: rng.chance(50) ? "l\(e)" : nil)) }275 }276 if rng.chance(30) { d["extra"] = ["k": .int(Int64(rng.int(9)))] }277 return d278 }279280 /// Random edits. With `side` 0 or 1 the script only touches the elements of that side (even or odd index in281 /// the base), never deletes a node that has edges, and only links its own surviving nodes; with nil anything.282 static func randomEdits(_ base: CanvasDocument, side: Int?, tag: String, _ rng: inout SplitMix64) -> CanvasDocument {283 var d = base284 func mine(_ index: Int) -> Bool { side.map { index % 2 == $0 } ?? true }285 let nodeIds = base.nodes.enumerated().filter { mine($0.offset) }.map(\.element.id)286 let edgeIds = base.edges.enumerated().filter { mine($0.offset) }.map(\.element.id)287 var added: [String] = []288 for step in 0..<(1 + rng.int(8)) {289 switch rng.int(8) {290 case 0, 1:291 guard !nodeIds.isEmpty else { continue }292 d.updateNode(id: nodeIds[rng.int(nodeIds.count)]) { $0.x = Double(rng.int(3000)); $0.y = Double(rng.int(3000)) / 4 }293 case 2:294 guard !nodeIds.isEmpty else { continue }295 d.updateNode(id: nodeIds[rng.int(nodeIds.count)]) { $0.text = "\(tag)\(step)"; if rng.chance(30) { $0.color = "#00ff00" } }296 case 3:297 guard !nodeIds.isEmpty else { continue }298 let id = nodeIds[rng.int(nodeIds.count)]299 if side == nil || base.edges(of: id).isEmpty { d.removeNode(id: id) }300 case 4:301 let id = "\(tag)-n\(step)"302 d.addNode(canvasNode(id, Double(rng.int(500)), Double(rng.int(500))))303 added.append(id)304 case 5:305 guard !edgeIds.isEmpty else { continue }306 d.updateEdge(id: edgeIds[rng.int(edgeIds.count)]) { $0.label = "\(tag)\(step)" }307 case 6:308 guard !edgeIds.isEmpty else { continue }309 d.removeEdge(id: edgeIds[rng.int(edgeIds.count)])310 default:311 let pool = (nodeIds + added).filter { d.node(id: $0) != nil }312 guard pool.count >= 2 else { continue }313 let a = pool[rng.int(pool.count)], b = pool[rng.int(pool.count)]314 if a != b { d.addEdge(CanvasEdge(id: "\(tag)-e\(step)", from: a, to: b)) }315 }316 }317 return d318 }319320 @Test func randomDisjointEditsMergeCleanAndCommute() {321 for seed in Self.seeds {322 var rng = SplitMix64(seed: seed)323 let base = Self.randomBase(&rng)324 var l = Self.randomEdits(base, side: 0, tag: "L", &rng)325 let r = Self.randomEdits(base, side: 1, tag: "R", &rng)326 if rng.chance(40) { l.viewport = CanvasViewport(x: Double(rng.int(100)), y: 3, zoom: 1.5) }327 let m = CanvasDocument.merge(base: base, local: l, remote: r)328 let w = CanvasDocument.merge(base: base, local: r, remote: l)329 #expect(m.isClean && w.isClean, "seed \(seed): \(m.conflicts.map(\.id))")330 #expect(m.merged.jsonData() == w.merged.jsonData(), "seed \(seed): not commutative")331 #expect(m.merged.danglingEdges.isEmpty, "seed \(seed): dangling edge")332 #expect(Set(m.merged.nodes.map(\.id)).count == m.merged.nodes.count && Set(m.merged.edges.map(\.id)).count == m.merged.edges.count, "seed \(seed): duplicate id")333 // Every change of each side is in the result.334 for (side, other) in [(l, r), (r, l)] {335 for n in side.nodes where base.node(id: n.id) != n { #expect(m.merged.node(id: n.id) == n, "seed \(seed): lost node edit \(n.id)") }336 for e in side.edges where base.edge(id: e.id) != e { #expect(m.merged.edge(id: e.id) == e, "seed \(seed): lost edge edit \(e.id)") }337 for n in base.nodes where side.node(id: n.id) == nil { #expect(m.merged.node(id: n.id) == nil, "seed \(seed): deletion undone \(n.id)") }338 for e in base.edges where side.edge(id: e.id) == nil { #expect(m.merged.edge(id: e.id) == nil, "seed \(seed): deletion undone \(e.id)") }339 _ = other340 }341 // Convergence: once both replicas hold the result, further merges change nothing.342 #expect(CanvasDocument.merge(base: l, local: m.merged, remote: w.merged) == CanvasMergeResult(merged: m.merged, conflicts: []), "seed \(seed)")343 #expect(CanvasDocument.merge(base: base, local: m.merged, remote: r).merged.jsonData() == m.merged.jsonData(), "seed \(seed): not idempotent")344 // The result survives serialization.345 #expect((try? CanvasDocument(data: m.merged.jsonData())) == m.merged, "seed \(seed)")346 }347 }348349 @Test func randomOverlappingEditsNeverLoseAnElement() {350 var conflicted = 0351 for seed in Self.seeds {352 var rng = SplitMix64(seed: seed &+ 50_000)353 let base = Self.randomBase(&rng)354 let l = Self.randomEdits(base, side: nil, tag: "L", &rng)355 let r = Self.randomEdits(base, side: nil, tag: "R", &rng)356 let m = CanvasDocument.merge(base: base, local: l, remote: r)357 if !m.isClean { conflicted += 1 }358 #expect(m.merged.danglingEdges.isEmpty, "seed \(seed): dangling edge")359 #expect(Set(m.merged.nodes.map(\.id)).count == m.merged.nodes.count && Set(m.merged.edges.map(\.id)).count == m.merged.edges.count, "seed \(seed): duplicate id")360361 func audit(_ kind: CanvasConflict.Kind, _ ids: Set<String>, _ value: (CanvasDocument, String) -> JSONValue?) {362 for id in ids {363 let b = value(base, id), lv = value(l, id), rv = value(r, id), mv = value(m.merged, id)364 let carried = m.conflicts.filter { $0.kind == kind && $0.id == id }365 // A version written by a side is either the merged one or carried by a conflict.366 for (side, v) in [("local", lv), ("remote", rv)] {367 guard let v, v != b, v != mv else { continue }368 #expect(carried.contains { $0.local == v || $0.remote == v }, "seed \(seed): \(side) version of \(kind) \(id) lost")369 }370 // An element missing from the result was deleted by a side while the other left it alone371 // (or it is an untouched edge of a deleted node).372 if mv == nil, lv != nil || rv != nil {373 let deletedCleanly = (lv == nil && (rv == nil || rv == b)) || (rv == nil && lv == b)374 let orphan = kind == .edge && [lv, rv].allSatisfy { $0 == nil || $0 == b }375 #expect(deletedCleanly || orphan, "seed \(seed): \(kind) \(id) vanished")376 }377 // A deletion is either applied or reported.378 if (lv == nil) != (rv == nil), b != nil, mv != nil {379 let survivor = lv ?? rv380 #expect(survivor == b ? !carried.isEmpty || kind == .node : !carried.isEmpty, "seed \(seed): deletion of \(kind) \(id) ignored silently")381 }382 }383 }384 audit(.node, Set((base.nodes + l.nodes + r.nodes).map(\.id))) { $0.node(id: $1)?.jsonValue }385 audit(.edge, Set((base.edges + l.edges + r.edges).map(\.id))) { $0.edge(id: $1)?.jsonValue }386 // A restored node is always reported.387 for n in m.merged.nodes where l.node(id: n.id) == nil || r.node(id: n.id) == nil {388 if base.node(id: n.id) != nil { #expect(m.conflicts.contains { $0.kind == .node && $0.id == n.id }, "seed \(seed): node \(n.id) restored silently") }389 }390 // Deterministic.391 #expect(CanvasDocument.merge(base: base, local: l, remote: r) == m, "seed \(seed)")392 }393 #expect(conflicted > 20, "the generator should produce conflicts (\(conflicted))")394 }395}396397@Suite struct CanvasLayoutTests {398 func pile(_ n: Int, edges: Bool = true) -> CanvasDocument {399 var d = CanvasDocument.empty400 for i in 0..<n { d.addNode(canvasNode("n\(i)", Double(i % 3), Double(i % 2), w: 80 + Double(i % 4) * 40, h: 40 + Double(i % 3) * 30)) }401 if edges { for i in 1..<n { d.addEdge(CanvasEdge(id: "e\(i)", from: "n\((i - 1) / 2)", to: "n\(i)")) } }402 return d403 }404 func finite(_ d: CanvasDocument) -> Bool {405 d.nodes.allSatisfy { [$0["x"], $0["y"]].allSatisfy { ($0?.doubleValue ?? .nan).isFinite } }406 }407408 @Test func gridDoesNotOverlapAndKeepsEverythingElse() {409 let d = pile(11)410 let g = CanvasLayout.grid(d, columns: 4, spacing: 20, origin: CGPoint(x: 100, y: -50))411 #expect(CanvasLayout.overlapArea(g) == 0)412 #expect(g.nodes.map(\.id) == d.nodes.map(\.id) && g.edges == d.edges && g.viewport == d.viewport)413 #expect(zip(g.nodes, d.nodes).allSatisfy { $0.w == $1.w && $0.h == $1.h && $0.z == $1.z && $0.text == $1.text })414 #expect(g.nodes[0].frame.origin == CGPoint(x: 100, y: -50))415 // Rows of 4: same y inside a row, columns aligned, at least `spacing` apart.416 #expect(Set(g.nodes[0..<4].map(\.y)).count == 1 && g.nodes[4].x == g.nodes[0].x && g.nodes[8].x == g.nodes[0].x)417 for i in g.nodes.indices { for j in g.nodes.indices where j > i {418 let a = g.nodes[i].frame.insetBy(dx: -9.99, dy: -9.99), b = g.nodes[j].frame.insetBy(dx: -9.99, dy: -9.99)419 #expect(!a.intersects(b), "\(i) and \(j) closer than the spacing")420 } }421 // Default column count, pinned nodes, degenerate inputs.422 let auto = CanvasLayout.grid(d)423 #expect(CanvasLayout.overlapArea(auto) == 0 && Set(auto.nodes.map(\.x)).count == 4)424 let pinned = CanvasLayout.grid(d, pinned: ["n3", "n7"])425 #expect(pinned.node(id: "n3") == d.node(id: "n3") && pinned.node(id: "n7") == d.node(id: "n7"))426 #expect(CanvasLayout.grid(.empty) == .empty)427 #expect(CanvasLayout.grid(pile(1), columns: 0, spacing: -.infinity).nodes[0].frame.origin == .zero)428 #expect(CanvasLayout.grid(d, columns: 99).nodes.map(\.y).allSatisfy { $0 == 0 })429 #expect(finite(CanvasLayout.grid(d, spacing: .nan)))430 }431432 @Test func forceDirectedSpreadsThePileAndIsDeterministic() {433 let d = pile(12)434 let before = CanvasLayout.energy(d), overlapBefore = CanvasLayout.overlapArea(d)435 let a = CanvasLayout.forceDirected(d, iterations: 300, seed: 7)436 #expect(finite(a))437 #expect(CanvasLayout.energy(a) < before * 0.05, "energy \(before) → \(CanvasLayout.energy(a))")438 #expect(CanvasLayout.overlapArea(a) < overlapBefore * 0.02, "overlap \(overlapBefore) → \(CanvasLayout.overlapArea(a))")439 // More iterations do not make it worse than a few.440 #expect(CanvasLayout.energy(a) <= CanvasLayout.energy(CanvasLayout.forceDirected(d, iterations: 5, seed: 7)))441 // Same seed, same bytes; only positions changed.442 #expect(CanvasLayout.forceDirected(d, iterations: 300, seed: 7).jsonData() == a.jsonData())443 #expect(a.edges == d.edges && zip(a.nodes, d.nodes).allSatisfy { $0.id == $1.id && $0.w == $1.w && $0.h == $1.h && $0.text == $1.text })444 // Connected cards end closer than unconnected ones on average.445 func dist(_ x: String, _ y: String) -> Double {446 let p = a.node(id: x)!.center, q = a.node(id: y)!.center447 return Double(hypot(p.x - q.x, p.y - q.y))448 }449 let linked = a.edges.map { dist($0.from, $0.to) }450 #expect(linked.max()! < 1500)451 // Zero iterations change nothing.452 #expect(CanvasLayout.forceDirected(d, iterations: 0) == d && CanvasLayout.forceDirected(d, iterations: -3) == d)453 }454455 @Test func coincidentNodesSeparateBySeed() {456 var d = CanvasDocument.empty457 for i in 0..<6 { d.nodes.append(canvasNode("n\(i)", 50, 50)) }458 let a = CanvasLayout.forceDirected(d, iterations: 120, seed: 1)459 let b = CanvasLayout.forceDirected(d, iterations: 120, seed: 1)460 let c = CanvasLayout.forceDirected(d, iterations: 120, seed: 2)461 #expect(finite(a) && finite(c) && a == b)462 #expect(a != c, "another seed separates the pile in other directions")463 #expect(Set(a.nodes.map { "\($0.x),\($0.y)" }).count == 6)464 #expect(CanvasLayout.overlapArea(a) < CanvasLayout.overlapArea(d) * 0.05)465 }466467 @Test func pinnedAndDegenerateCases() {468 let d = pile(8)469 let a = CanvasLayout.forceDirected(d, iterations: 100, seed: 3, pinned: ["n0", "n5"])470 #expect(a.node(id: "n0") == d.node(id: "n0") && a.node(id: "n5") == d.node(id: "n5") && a.node(id: "n1") != d.node(id: "n1"))471 #expect(CanvasLayout.forceDirected(.empty) == .empty)472 let one = pile(1)473 #expect(CanvasLayout.forceDirected(one) == one)474 // Two cards far apart joined by an edge are pulled together; without the edge they stay.475 var far = CanvasDocument.empty476 far.addNode(canvasNode("a", 0, 0))477 far.addNode(canvasNode("b", 5000, 0))478 #expect(CanvasLayout.forceDirected(far) == far)479 far.addEdge(CanvasEdge(id: "ab", from: "a", to: "b"))480 let near = CanvasLayout.forceDirected(far, iterations: 400)481 #expect(near.node(id: "b")!.x - near.node(id: "a")!.x < 1000 && CanvasLayout.overlapArea(near) == 0)482 // Hostile numbers: zero and negative sizes, self loops, dangling edges, absurd parameters.483 var odd = CanvasDocument.empty484 odd.nodes = [canvasNode("a", 0, 0, w: 0, h: 0), canvasNode("b", 0, 0, w: -5, h: -5), canvasNode("c", 1e12, -1e12)]485 odd.edges = [CanvasEdge(id: "s", from: "a", to: "a"), CanvasEdge(id: "x", from: "a", to: "ghost"), CanvasEdge(id: "y", from: "a", to: "c")]486 for forces in [CanvasLayout.Forces(), CanvasLayout.Forces(spacing: .nan, repulsion: 1e9, attraction: 1e9, maxStep: .infinity),487 CanvasLayout.Forces(spacing: -1, repulsion: -1, attraction: 0, maxStep: 0)] {488 #expect(finite(CanvasLayout.forceDirected(odd, iterations: 50, seed: 9, forces: forces)))489 }490 var rng = CanvasLayoutRandom(seed: 5)491 var stepped = d492 CanvasLayout.step(&stepped, temperature: .nan, random: &rng)493 #expect(stepped == d)494 CanvasLayout.step(&stepped, random: &rng)495 #expect(stepped != d && finite(stepped))496 var r1 = CanvasLayoutRandom(seed: 5), r2 = CanvasLayoutRandom(seed: 5)497 #expect((0..<50).allSatisfy { _ in let v = r1.signedUnit(); return v == r2.signedUnit() && v >= -1 && v <= 1 })498 }499}500