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/// Edits, in `old` coordinates and ascending order, that turn `old` into `new` line by line.
 63public func lineEdits(from old: String, to new: String) -> [TextEdit] {
 64    let oldLines = textLines(old)
 65    let newLines = textLines(new)
 66    var ids = LineIDs()
 67    let pairs = matchingLines(ids.encode(oldLines), ids.encode(newLines))
 68    var offsets = [0]
 69    for line in oldLines { offsets.append(offsets.last! + line.utf16.count) }
 70    var edits: [TextEdit] = []
 71    var i = 0, j = 0
 72    for (pi, pj) in pairs + [(oldLines.count, newLines.count)] {
 73        if i < pi || j < pj {
 74            edits.append(TextEdit(range: offsets[i]..<offsets[pi], replacement: newLines[j..<pj].joined()))
 75        }
 76        i = pi + 1
 77        j = pj + 1
 78    }
 79    return edits
 80}
 81
 82/// Lines with their endings.
 83func textLines(_ text: String) -> [String] {
 84    var lines: [String] = []
 85    var current = ""
 86    for scalar in text.unicodeScalars {
 87        current.unicodeScalars.append(scalar)
 88        if scalar == "\n" {
 89            lines.append(current)
 90            current = ""
 91        }
 92    }
 93    if !current.isEmpty { lines.append(current) }
 94    return lines
 95}
 96
 97struct LineIDs {
 98    private var ids: [String: Int] = [:]
 99
100    mutating func encode(_ lines: [String]) -> [Int] {
101        lines.map { line in
102            if let id = ids[line] { return id }
103            let id = ids.count
104            ids[line] = id
105            return id
106        }
107    }
108}
109
110/// Matched index pairs of a longest common subsequence, ascending. Common prefix and suffix
111/// are matched directly; Myers' algorithm handles the middle. When the middle differs by more
112/// than the memory budget allows, it is treated as having no matches.
113func matchingLines(_ a: [Int], _ b: [Int]) -> [(Int, Int)] {
114    var prefix = 0
115    while prefix < a.count, prefix < b.count, a[prefix] == b[prefix] { prefix += 1 }
116    var suffix = 0
117    while suffix < a.count - prefix, suffix < b.count - prefix, a[a.count - 1 - suffix] == b[b.count - 1 - suffix] {
118        suffix += 1
119    }
120    var pairs = (0..<prefix).map { ($0, $0) }
121    let middleA = Array(a[prefix..<(a.count - suffix)])
122    let middleB = Array(b[prefix..<(b.count - suffix)])
123    pairs += myers(middleA, middleB).map { ($0.0 + prefix, $0.1 + prefix) }
124    pairs += (0..<suffix).map { (a.count - suffix + $0, b.count - suffix + $0) }
125    return pairs
126}
127
128private func myers(_ a: [Int], _ b: [Int]) -> [(Int, Int)] {
129    let n = a.count, m = b.count
130    guard n > 0, m > 0 else { return [] }
131    let maxD = n + m
132    let offset = maxD + 1
133    // Each step keeps a copy of the frontier for backtracking; cap that at ~20M entries.
134    let budget = max(1, 20_000_000 / (2 * maxD + 3))
135    var v = [Int](repeating: 0, count: 2 * maxD + 3)
136    var trace: [[Int]] = []
137    var found = false
138    search: for d in 0...min(maxD, budget) {
139        trace.append(v)
140        for k in stride(from: -d, through: d, by: 2) {
141            var x = (k == -d || (k != d && v[offset + k - 1] < v[offset + k + 1])) ? v[offset + k + 1] : v[offset + k - 1] + 1
142            var y = x - k
143            while x < n, y < m, a[x] == b[y] {
144                x += 1
145                y += 1
146            }
147            v[offset + k] = x
148            if x >= n, y >= m {
149                found = true
150                break search
151            }
152        }
153    }
154    guard found else { return [] }
155
156    var pairs: [(Int, Int)] = []
157    var x = n, y = m
158    for d in stride(from: trace.count - 1, through: 0, by: -1) {
159        let v = trace[d]
160        let k = x - y
161        let previousK = (k == -d || (k != d && v[offset + k - 1] < v[offset + k + 1])) ? k + 1 : k - 1
162        let previousX = v[offset + previousK]
163        let previousY = previousX - previousK
164        while x > previousX, y > previousY {
165            pairs.append((x - 1, y - 1))
166            x -= 1
167            y -= 1
168        }
169        if d > 0 {
170            x = previousX
171            y = previousY
172        }
173    }
174    return pairs.reversed()
175}