Sources/OrgDocument/Merge.swift

  1import OrgCore
  2
  3public struct MergeConflict: Sendable, Equatable {
  4    public let base: String
  5    public let ours: String
  6    public let theirs: String
  7}
  8
  9public enum MergeResult: Sendable, Equatable {
 10    case merged(String)
 11    case conflict([MergeConflict])
 12}
 13
 14/// Line-based three-way merge. Lines keep their endings, so CRLF and a missing final newline
 15/// survive. A region changed on one side takes that side; changed the same way on both, takes
 16/// it once; changed differently, is a conflict.
 17public func threeWayMerge(base: String, ours: String, theirs: String) -> MergeResult {
 18    let baseLines = textLines(base)
 19    let ourLines = textLines(ours)
 20    let theirLines = textLines(theirs)
 21    var ids = LineIDs()
 22    let baseIDs = ids.encode(baseLines)
 23    let ourIDs = ids.encode(ourLines)
 24    let theirIDs = ids.encode(theirLines)
 25
 26    var toOurs = [Int?](repeating: nil, count: baseLines.count)
 27    for (b, o) in matchingLines(baseIDs, ourIDs) { toOurs[b] = o }
 28    var toTheirs = [Int?](repeating: nil, count: baseLines.count)
 29    for (b, t) in matchingLines(baseIDs, theirIDs) { toTheirs[b] = t }
 30
 31    var merged: [String] = []
 32    var conflicts: [MergeConflict] = []
 33    var nextBase = 0, nextOurs = 0, nextTheirs = 0
 34
 35    func resolve(_ baseEnd: Int, _ oursEnd: Int, _ theirsEnd: Int) {
 36        let b = baseLines[nextBase..<baseEnd]
 37        let o = ourLines[nextOurs..<oursEnd]
 38        let t = theirLines[nextTheirs..<theirsEnd]
 39        if o.elementsEqual(b) {
 40            merged += t
 41        } else if t.elementsEqual(b) || o.elementsEqual(t) {
 42            merged += o
 43        } else {
 44            conflicts.append(MergeConflict(base: b.joined(), ours: o.joined(), theirs: t.joined()))
 45        }
 46    }
 47
 48    // A base line kept by both sides is a fixed point; everything between fixed points is
 49    // resolved as one region.
 50    for k in baseLines.indices {
 51        guard let o = toOurs[k], let t = toTheirs[k], o >= nextOurs, t >= nextTheirs else { continue }
 52        resolve(k, o, t)
 53        merged.append(baseLines[k])
 54        nextBase = k + 1
 55        nextOurs = o + 1
 56        nextTheirs = t + 1
 57    }
 58    resolve(baseLines.count, ourLines.count, theirLines.count)
 59    return conflicts.isEmpty ? .merged(merged.joined()) : .conflict(conflicts)
 60}
 61
 62/// One line of a diff, with its ending.
 63public struct DiffLine: Sendable, Equatable {
 64    public enum Kind: Sendable, Equatable { case same, removed, added }
 65    public let kind: Kind
 66    public let text: String
 67}
 68
 69/// The lines of `old` and `new` in order: kept, removed from `old`, added in `new`.
 70public func lineDiff(old: String, new: String) -> [DiffLine] {
 71    let oldLines = textLines(old)
 72    let newLines = textLines(new)
 73    var ids = LineIDs()
 74    let pairs = matchingLines(ids.encode(oldLines), ids.encode(newLines))
 75    var result: [DiffLine] = []
 76    var i = 0, j = 0
 77    for (pi, pj) in pairs + [(oldLines.count, newLines.count)] {
 78        result += oldLines[i..<pi].map { DiffLine(kind: .removed, text: $0) }
 79        result += newLines[j..<pj].map { DiffLine(kind: .added, text: $0) }
 80        if pi < oldLines.count, pj < newLines.count { result.append(DiffLine(kind: .same, text: oldLines[pi])) }
 81        i = pi + 1
 82        j = pj + 1
 83    }
 84    return result
 85}
 86
 87/// `ours` and `theirs` merged against `base` where they don't conflict, as `threeWayMerge`
 88/// does, with each conflict between git's markers. Without a base, every difference is a
 89/// conflict.
 90public func mergeWithMarkers(base: String?, ours: String, theirs: String, oursLabel: String, theirsLabel: String) -> String {
 91    func block(_ o: String, _ t: String) -> String {
 92        func ended(_ s: String) -> String { s.isEmpty || s.hasSuffix("\n") ? s : s + "\n" }
 93        return "<<<<<<< \(oursLabel)\n" + ended(o) + "=======\n" + ended(t) + ">>>>>>> \(theirsLabel)\n"
 94    }
 95    guard let base else {
 96        var out = ""
 97        var o = "", t = ""
 98        func flush() {
 99            if !o.isEmpty || !t.isEmpty { out += block(o, t) }
100            o = ""
101            t = ""
102        }
103        for line in lineDiff(old: ours, new: theirs) {
104            switch line.kind {
105            case .same:
106                flush()
107                out += line.text
108            case .removed: o += line.text
109            case .added: t += line.text
110            }
111        }
112        flush()
113        return out
114    }
115    let baseLines = textLines(base)
116    let ourLines = textLines(ours)
117    let theirLines = textLines(theirs)
118    var ids = LineIDs()
119    let baseIDs = ids.encode(baseLines)
120    var toOurs = [Int?](repeating: nil, count: baseLines.count)
121    for (b, o) in matchingLines(baseIDs, ids.encode(ourLines)) { toOurs[b] = o }
122    var toTheirs = [Int?](repeating: nil, count: baseLines.count)
123    for (b, t) in matchingLines(baseIDs, ids.encode(theirLines)) { toTheirs[b] = t }
124    var merged = ""
125    var nextBase = 0, nextOurs = 0, nextTheirs = 0
126    func resolve(_ baseEnd: Int, _ oursEnd: Int, _ theirsEnd: Int) {
127        let b = baseLines[nextBase..<baseEnd], o = ourLines[nextOurs..<oursEnd], t = theirLines[nextTheirs..<theirsEnd]
128        if o.elementsEqual(b) {
129            merged += t.joined()
130        } else if t.elementsEqual(b) || o.elementsEqual(t) {
131            merged += o.joined()
132        } else {
133            merged += block(o.joined(), t.joined())
134        }
135    }
136    for k in baseLines.indices {
137        guard let o = toOurs[k], let t = toTheirs[k], o >= nextOurs, t >= nextTheirs else { continue }
138        resolve(k, o, t)
139        merged += baseLines[k]
140        nextBase = k + 1
141        nextOurs = o + 1
142        nextTheirs = t + 1
143    }
144    resolve(baseLines.count, ourLines.count, theirLines.count)
145    return merged
146}