Repository Public
1// SP Notes Core2// File: Tests/SPNotesDocumentTests/MergeTests.swift3// Description: Three-way merge by top-level block identity: combined changes and every conflict case.4//5// Author: Simon-Pierre Boucher6// Contact: contact@spboucher.ai7import Foundation8import Testing9@testable import SPNotesDocument1011@Suite struct MergeTests {12 /// Five paragraphs a…e with ids.13 let base = md("a\n\nb\n\nc\n\nd\n\ne")1415 func edit(_ d: NoteDocument, _ line: Int, _ text: String) -> NoteDocument {16 var d = d17 d.replaceText(in: 0..<d.lines[line].inlineLength, at: line, with: text)18 return d19 }20 func insert(_ d: NoteDocument, _ at: Int, _ text: String) -> NoteDocument {21 var d = d22 d.lines.insert(.paragraph(text: text), at: at)23 return d24 }25 func remove(_ d: NoteDocument, _ line: Int) -> NoteDocument {26 var d = d27 d.lines.remove(at: line)28 return d29 }30 func move(_ d: NoteDocument, _ from: Int, _ to: Int) -> NoteDocument {31 var d = d32 let line = d.lines.remove(at: from)33 d.lines.insert(line, at: to)34 return d35 }36 func merged(_ mine: NoteDocument, _ theirs: NoteDocument, base b: NoteDocument? = nil) -> String {37 switch NoteDocument.merge(base: b ?? base, mine: mine, theirs: theirs) {38 case .merged(let d):39 let issues = d.schemaViolations(strict: true)40 return issues.isEmpty ? d.plainText().replacingOccurrences(of: "\n", with: " ") : "INVALID \(issues)"41 case .conflict: return "CONFLICT"42 }43 }4445 @Test func trivialCases() {46 let m = edit(base, 1, "B")47 #expect(merged(base, base) == "a b c d e")48 #expect(merged(m, base) == "a B c d e" && merged(base, m) == "a B c d e" && merged(m, m) == "a B c d e")49 #expect(NoteDocument.merge(base: base, mine: m, theirs: base) == .merged(m))50 // Identical changes made on both sides, even against an unrelated base.51 #expect(merged(m, m, base: md("x")) == "a B c d e")52 }5354 @Test func independentChangesAreCombined() {55 #expect(merged(edit(base, 0, "A"), edit(base, 4, "E")) == "A b c d E")56 #expect(merged(edit(base, 1, "B"), edit(base, 2, "C")) == "a B C d e")57 #expect(merged(insert(base, 1, "x"), remove(base, 3)) == "a x b c e")58 #expect(merged(insert(base, 0, "x"), insert(base, 5, "y")) == "x a b c d e y")59 #expect(merged(remove(base, 0), remove(base, 4)) == "b c d")60 #expect(merged(remove(base, 2), remove(base, 2)) == "a b d e")61 #expect(merged(insert(insert(base, 2, "x"), 3, "y"), edit(remove(base, 0), 3, "E")) == "b x y c d E")62 // An edit and an insertion right next to it.63 #expect(merged(edit(base, 1, "B"), insert(base, 2, "x")) == "a B x c d e")64 }6566 @Test func movesCombineWithEditsElsewhereAndOfTheMovedBlock() {67 #expect(merged(move(base, 4, 0), edit(base, 2, "C")) == "e a b C d")68 #expect(merged(move(base, 4, 0), edit(base, 4, "E")) == "E a b c d")69 #expect(merged(edit(base, 0, "A"), move(base, 0, 3)) == "b c d A e")70 #expect(merged(move(base, 0, 4), move(base, 0, 4)) == "b c d e a")71 }7273 @Test func conflicts() {74 #expect(merged(edit(base, 1, "B1"), edit(base, 1, "B2")) == "CONFLICT")75 #expect(merged(edit(base, 1, "B1"), remove(base, 1)) == "CONFLICT", "edited here, deleted there")76 #expect(merged(remove(base, 1), edit(base, 1, "B1")) == "CONFLICT")77 #expect(merged(insert(base, 2, "x"), insert(base, 2, "y")) == "CONFLICT", "two insertions at the same place")78 #expect(merged(move(base, 4, 0), move(base, 4, 2)) == "CONFLICT", "moved to two places")79 #expect(merged(move(base, 4, 0), remove(base, 4)) == "CONFLICT", "moved here, deleted there")80 #expect(merged(insert(base, 1, "x"), remove(base, 0)) == "CONFLICT" || merged(insert(base, 1, "x"), remove(base, 0)) == "x b c d e")81 #expect(merged(remove(remove(remove(remove(base, 0), 0), 0), 0), edit(remove(base, 4), 0, "A")) == "CONFLICT")82 }8384 @Test func nothingIsEverDropped() {85 // Every non-conflicting result holds each side's own changes.86 var r = SplitMix64(seed: 2026)87 var mergedCount = 088 for i in 0..<600 {89 func mutate(_ d: NoteDocument, _ tag: String) -> (NoteDocument, added: [String], removed: [String]) {90 var d = d, added: [String] = [], removed: [String] = []91 for n in 0..<(1 + r.int(3)) {92 let line = r.int(d.lines.count)93 switch r.int(4) {94 case 0: let t = "\(tag)\(i)e\(n)"; removed.append(d.lines[line].displayString); d = edit(d, line, t); added.append(t)95 case 1: let t = "\(tag)\(i)i\(n)"; d = insert(d, line, t); added.append(t)96 case 2: if d.lines.count > 1 { removed.append(d.lines[line].displayString); d = remove(d, line) }97 default: d = move(d, line, r.int(d.lines.count))98 }99 }100 return (d, added.filter { t in d.lines.contains { $0.displayString == t } }, removed)101 }102 let (mine, mineAdded, mineRemoved) = mutate(base, "m")103 let (theirs, theirsAdded, theirsRemoved) = mutate(base, "t")104 guard case .merged(let result) = NoteDocument.merge(base: base, mine: mine, theirs: theirs) else { continue }105 mergedCount += 1106 let texts = result.lines.map(\.displayString)107 for t in mineAdded + theirsAdded { #expect(texts.contains(t), "case \(i): lost \(t)") }108 for t in mineRemoved + theirsRemoved where ["a", "b", "c", "d", "e"].contains(t) { #expect(!texts.contains(t), "case \(i): \(t) came back") }109 #expect(Set(texts).count == texts.count, "case \(i): duplicated block")110 #expect(result.schemaViolations(strict: true).isEmpty)111 // Merging is symmetric.112 #expect(NoteDocument.merge(base: base, mine: theirs, theirs: mine) == .merged(result), "case \(i): not symmetric")113 }114 #expect(mergedCount > 100)115 }116117 @Test func blocksAreWholeTopLevelNodes() throws {118 let b = md("# T\n\n- a\n- b\n\n---\n\n> q\n\nfin")119 var mine = b120 mine.replaceText(in: 0..<1, at: 1, with: "A")121 var theirs = b122 theirs.replaceText(in: 0..<1, at: 4, with: "Q")123 theirs.insertBlockAtom(.horizontalRule(), after: 5)124 #expect(merged(mine, theirs, base: b) == "T A b Q fin")125 guard case .merged(let d) = NoteDocument.merge(base: b, mine: mine, theirs: theirs) else { Issue.record("conflict"); return }126 #expect(sexp(d) == #"h1("T") ul(li(p("A")) li(p("b"))) hr bq(p("Q")) p("fin") hr"#)127 // Two edits inside the same list are a conflict: the list is one block.128 var other = b129 other.replaceText(in: 0..<1, at: 2, with: "B")130 #expect(merged(mine, other, base: b) == "CONFLICT")131 // Blocks without an id (rules) are matched by content: deleting one on a side works.132 var noRule = b133 noRule.deleteLine(at: 3)134 #expect(merged(noRule, mine, base: b) == "T A b Q fin".replacingOccurrences(of: "Q", with: "q"))135 }136137 @Test func duplicatedIdsAndRootChanges() throws {138 var dup = base139 dup.lines[1].attrs["id"] = dup.lines[0].attrs["id"]140 #expect(merged(edit(dup, 0, "A"), edit(dup, 4, "E"), base: dup) == "CONFLICT")141 let b = try NoteDocument(json: Data(#"{"type":"doc","attrs":{"v":1},"content":[{"type":"paragraph","attrs":{"id":"aaaaaaaaaa"},"content":[{"type":"text","text":"a"}]},{"type":"paragraph","attrs":{"id":"bbbbbbbbbb"}}]}"#.utf8))142 let m = try NoteDocument(json: Data(#"{"type":"doc","attrs":{"v":2},"content":[{"type":"paragraph","attrs":{"id":"aaaaaaaaaa"},"content":[{"type":"text","text":"a"}]},{"type":"paragraph","attrs":{"id":"bbbbbbbbbb"}}]}"#.utf8))143 let t = try NoteDocument(json: Data(#"{"type":"doc","attrs":{"v":1},"content":[{"type":"paragraph","attrs":{"id":"aaaaaaaaaa"},"content":[{"type":"text","text":"A"}]},{"type":"paragraph","attrs":{"id":"bbbbbbbbbb"}}]}"#.utf8))144 guard case .merged(let d) = NoteDocument.merge(base: b, mine: m, theirs: t) else { Issue.record("conflict"); return }145 #expect(d.pmNode().attrs == ["v": 2] && d.plainText() == "A")146 let t2 = try NoteDocument(json: Data(#"{"type":"doc","attrs":{"v":3},"content":[{"type":"paragraph","attrs":{"id":"aaaaaaaaaa"},"content":[{"type":"text","text":"A"}]},{"type":"paragraph","attrs":{"id":"bbbbbbbbbb"}}]}"#.utf8))147 #expect(NoteDocument.merge(base: b, mine: m, theirs: t2) == .conflict)148 // Deleting everything on one side while the other edits is a conflict, never an empty document.149 #expect(NoteDocument.merge(base: b, mine: NoteDocument(lines: []), theirs: t) == .conflict)150 }151}152