Sources/OrgCore/LineDiff.swift

  1import Foundation
  2
  3// Line diffs: Myers over line ids, for merges, diffs and commands' edits.
  4
  5/// Edits, in `old` coordinates and ascending order, that turn `old` into `new` line by line.
  6public func lineEdits(from old: String, to new: String) -> [TextEdit] {
  7    let oldLines = textLines(old)
  8    let newLines = textLines(new)
  9    var ids = LineIDs()
 10    let pairs = matchingLines(ids.encode(oldLines), ids.encode(newLines))
 11    var offsets = [0]
 12    for line in oldLines { offsets.append(offsets.last! + line.utf16.count) }
 13    var edits: [TextEdit] = []
 14    var i = 0, j = 0
 15    for (pi, pj) in pairs + [(oldLines.count, newLines.count)] {
 16        if i < pi || j < pj {
 17            edits.append(TextEdit(range: offsets[i]..<offsets[pi], replacement: newLines[j..<pj].joined()))
 18        }
 19        i = pi + 1
 20        j = pj + 1
 21    }
 22    return edits
 23}
 24
 25/// Lines with their endings.
 26public func textLines(_ text: String) -> [String] {
 27    var lines: [String] = []
 28    var current = ""
 29    for scalar in text.unicodeScalars {
 30        current.unicodeScalars.append(scalar)
 31        if scalar == "\n" {
 32            lines.append(current)
 33            current = ""
 34        }
 35    }
 36    if !current.isEmpty { lines.append(current) }
 37    return lines
 38}
 39
 40public struct LineIDs {
 41    private var ids: [String: Int] = [:]
 42
 43    public init() {}
 44
 45    public mutating func encode(_ lines: [String]) -> [Int] {
 46        lines.map { line in
 47            if let id = ids[line] { return id }
 48            let id = ids.count
 49            ids[line] = id
 50            return id
 51        }
 52    }
 53}
 54
 55/// Matched index pairs of a longest common subsequence, ascending. Common prefix and suffix
 56/// are matched directly; Myers' algorithm handles the middle. When the middle differs by more
 57/// than the memory budget allows, it is treated as having no matches.
 58public func matchingLines(_ a: [Int], _ b: [Int]) -> [(Int, Int)] {
 59    var prefix = 0
 60    while prefix < a.count, prefix < b.count, a[prefix] == b[prefix] { prefix += 1 }
 61    var suffix = 0
 62    while suffix < a.count - prefix, suffix < b.count - prefix, a[a.count - 1 - suffix] == b[b.count - 1 - suffix] {
 63        suffix += 1
 64    }
 65    var pairs = (0..<prefix).map { ($0, $0) }
 66    let middleA = Array(a[prefix..<(a.count - suffix)])
 67    let middleB = Array(b[prefix..<(b.count - suffix)])
 68    pairs += myers(middleA, middleB).map { ($0.0 + prefix, $0.1 + prefix) }
 69    pairs += (0..<suffix).map { (a.count - suffix + $0, b.count - suffix + $0) }
 70    return pairs
 71}
 72
 73private func myers(_ a: [Int], _ b: [Int]) -> [(Int, Int)] {
 74    let n = a.count, m = b.count
 75    guard n > 0, m > 0 else { return [] }
 76    let maxD = n + m
 77    let offset = maxD + 1
 78    // Each step keeps a copy of the frontier for backtracking; cap that at ~20M entries.
 79    let budget = max(1, 20_000_000 / (2 * maxD + 3))
 80    var v = [Int](repeating: 0, count: 2 * maxD + 3)
 81    var trace: [[Int]] = []
 82    var found = false
 83    search: for d in 0...min(maxD, budget) {
 84        trace.append(v)
 85        for k in stride(from: -d, through: d, by: 2) {
 86            var x = (k == -d || (k != d && v[offset + k - 1] < v[offset + k + 1])) ? v[offset + k + 1] : v[offset + k - 1] + 1
 87            var y = x - k
 88            while x < n, y < m, a[x] == b[y] {
 89                x += 1
 90                y += 1
 91            }
 92            v[offset + k] = x
 93            if x >= n, y >= m {
 94                found = true
 95                break search
 96            }
 97        }
 98    }
 99    guard found else { return [] }
100
101    var pairs: [(Int, Int)] = []
102    var x = n, y = m
103    for d in stride(from: trace.count - 1, through: 0, by: -1) {
104        let v = trace[d]
105        let k = x - y
106        let previousK = (k == -d || (k != d && v[offset + k - 1] < v[offset + k + 1])) ? k + 1 : k - 1
107        let previousX = v[offset + previousK]
108        let previousY = previousX - previousK
109        while x > previousX, y > previousY {
110            pairs.append((x - 1, y - 1))
111            x -= 1
112            y -= 1
113        }
114        if d > 0 {
115            x = previousX
116            y = previousY
117        }
118    }
119    return pairs.reversed()
120}
121
122
123/// An edit spanning several lines as the lines it changes, so what lies between (a folded
124/// heading) is left alone: a command changing the text in two places gives two edits. For
125/// editors applying edits; commands still return one.
126public func splitByLines(_ edit: TextEdit, in text: String) -> [TextEdit] {
127    let ns = text as NSString
128    let start = ns.lineRange(for: NSRange(location: edit.range.lowerBound, length: 0)).location
129    var end = edit.range.upperBound
130    if end < ns.length, end == 0 || ns.character(at: end - 1) != 10 {
131        end = NSMaxRange(ns.lineRange(for: NSRange(location: end, length: 0)))
132    }
133    let old = ns.substring(with: NSRange(start..<end))
134    guard old.utf16.lazy.filter({ $0 == 10 }).count >= 2 else { return [edit] }
135    let new = ns.substring(with: NSRange(start..<edit.range.lowerBound)) + edit.replacement + ns.substring(with: NSRange(edit.range.upperBound..<end))
136    let edits = lineEdits(from: old, to: new).map { TextEdit(range: ($0.range.lowerBound + start)..<($0.range.upperBound + start), replacement: $0.replacement) }
137    return edits.isEmpty ? [edit] : edits
138}