SPB Git

Repository Public

CanvasTests.swift 31.5 KB 500 lines swift

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

Theme