kotej/Sources/KotejEngine/TextDiff.swift

import Foundation

/// Line-by-line alignment of two texts, for the side-by-side file view.
public enum TextDiff {
    public enum Kind: Sendable, Equatable {
        case equal, changed, added, removed
    }

    /// What a changed line actually differs in. Knowing that a difference is only
    /// whitespace or only a comment is usually enough to skip it.
    public enum ChangeKind: Sendable, Equatable {
        /// Only spacing or line endings changed.
        case whitespace
        /// Only the comments changed; the code is the same.
        case comment
        /// A real change.
        case content
    }

    /// One row of the side-by-side view. A nil number means "no line on that side".
    public struct Row: Sendable, Equatable {
        public let kind: Kind
        public let leftNumber: Int?
        public let rightNumber: Int?
        public let left: String
        public let right: String
        /// Only meaningful for `.changed` rows.
        public let changeKind: ChangeKind
        /// Character offsets of the part that actually differs, so the exact
        /// characters can be highlighted rather than the whole line.
        public let leftHighlight: Range<Int>?
        public let rightHighlight: Range<Int>?

        init(kind: Kind, leftNumber: Int?, rightNumber: Int?, left: String, right: String,
             changeKind: ChangeKind = .content,
             leftHighlight: Range<Int>? = nil, rightHighlight: Range<Int>? = nil) {
            self.kind = kind
            self.leftNumber = leftNumber
            self.rightNumber = rightNumber
            self.left = left
            self.right = right
            self.changeKind = changeKind
            self.leftHighlight = leftHighlight
            self.rightHighlight = rightHighlight
        }
    }

    /// Classifies a changed pair and locates the differing characters.
    static func describe(left: String, right: String, syntax: CommentSyntax?)
        -> (ChangeKind, Range<Int>?, Range<Int>?) {
        let (leftRange, rightRange) = inlineRanges(left, right)

        // Whitespace first: it subsumes the others when nothing else moved.
        if left.filter({ !$0.isWhitespace }) == right.filter({ !$0.isWhitespace }) {
            return (.whitespace, leftRange, rightRange)
        }
        if let syntax {
            let strippedLeft = syntax.stripping(left).trimmingCharacters(in: .whitespaces)
            let strippedRight = syntax.stripping(right).trimmingCharacters(in: .whitespaces)
            if strippedLeft == strippedRight {
                return (.comment, leftRange, rightRange)
            }
        }
        return (.content, leftRange, rightRange)
    }

    /// The differing middle of two lines, after trimming what they share at each
    /// end. Nil when one side is empty, where highlighting adds nothing.
    static func inlineRanges(_ left: String, _ right: String) -> (Range<Int>?, Range<Int>?) {
        let l = Array(left), r = Array(right)
        guard !l.isEmpty, !r.isEmpty else { return (nil, nil) }

        var prefix = 0
        while prefix < l.count, prefix < r.count, l[prefix] == r[prefix] { prefix += 1 }

        var suffix = 0
        while suffix < l.count - prefix, suffix < r.count - prefix,
              l[l.count - 1 - suffix] == r[r.count - 1 - suffix] { suffix += 1 }

        let leftRange = prefix..<(l.count - suffix)
        let rightRange = prefix..<(r.count - suffix)
        // Identical lines have nothing to point at.
        if leftRange.isEmpty && rightRange.isEmpty { return (nil, nil) }
        return (leftRange, rightRange)
    }

    /// Aligns both texts. Common prefixes and suffixes are matched cheaply first,
    /// so a one-line change in a big file costs almost nothing; only the middle
    /// needs the quadratic pass, and beyond `limit` lines that middle is reported
    /// as one changed block rather than hanging the UI.
    public static func rows(left: String, right: String,
                            syntax: CommentSyntax? = nil, limit: Int = 3_000) -> [Row] {
        let leftLines = split(left)
        let rightLines = split(right)

        var prefix = 0
        while prefix < leftLines.count, prefix < rightLines.count,
              leftLines[prefix] == rightLines[prefix] { prefix += 1 }

        var suffix = 0
        while suffix < leftLines.count - prefix, suffix < rightLines.count - prefix,
              leftLines[leftLines.count - 1 - suffix] == rightLines[rightLines.count - 1 - suffix] {
            suffix += 1
        }

        var rows: [Row] = []
        for i in 0..<prefix {
            rows.append(Row(kind: .equal, leftNumber: i + 1, rightNumber: i + 1,
                            left: leftLines[i], right: rightLines[i]))
        }

        let leftMiddle = Array(leftLines[prefix..<(leftLines.count - suffix)])
        let rightMiddle = Array(rightLines[prefix..<(rightLines.count - suffix)])

        if leftMiddle.count > limit || rightMiddle.count > limit {
            rows.append(contentsOf: blockRows(leftMiddle, rightMiddle, leftStart: prefix,
                                              rightStart: prefix, syntax: syntax))
        } else {
            rows.append(contentsOf: align(leftMiddle, rightMiddle, leftStart: prefix,
                                          rightStart: prefix, syntax: syntax))
        }

        for i in 0..<suffix {
            let leftIndex = leftLines.count - suffix + i
            let rightIndex = rightLines.count - suffix + i
            rows.append(Row(kind: .equal, leftNumber: leftIndex + 1, rightNumber: rightIndex + 1,
                            left: leftLines[leftIndex], right: rightLines[rightIndex]))
        }
        return rows
    }

    private static func split(_ text: String) -> [String] {
        text.replacingOccurrences(of: "\r\n", with: "\n").components(separatedBy: "\n")
    }

    /// Longest common subsequence over the differing middle section.
    private static func align(_ left: [String], _ right: [String],
                              leftStart: Int, rightStart: Int, syntax: CommentSyntax?) -> [Row] {
        guard !left.isEmpty || !right.isEmpty else { return [] }

        // lengths[i][j] = LCS length of left[i...] and right[j...]
        var lengths = [[Int]](repeating: [Int](repeating: 0, count: right.count + 1), count: left.count + 1)
        if !left.isEmpty && !right.isEmpty {
            for i in stride(from: left.count - 1, through: 0, by: -1) {
                for j in stride(from: right.count - 1, through: 0, by: -1) {
                    lengths[i][j] = left[i] == right[j]
                        ? lengths[i + 1][j + 1] + 1
                        : max(lengths[i + 1][j], lengths[i][j + 1])
                }
            }
        }

        var rows: [Row] = []
        var i = 0, j = 0
        // Pending one-sided runs are paired up as "changed" so a modified line
        // shows opposite its old version instead of as a delete plus an insert.
        var removed: [(Int, String)] = []
        var added: [(Int, String)] = []

        func flush() {
            let shared = min(removed.count, added.count)
            for k in 0..<shared {
                let (change, leftRange, rightRange) = describe(left: removed[k].1,
                                                               right: added[k].1, syntax: syntax)
                rows.append(Row(kind: .changed,
                                leftNumber: removed[k].0, rightNumber: added[k].0,
                                left: removed[k].1, right: added[k].1,
                                changeKind: change,
                                leftHighlight: leftRange, rightHighlight: rightRange))
            }
            for k in shared..<removed.count {
                rows.append(Row(kind: .removed, leftNumber: removed[k].0, rightNumber: nil,
                                left: removed[k].1, right: ""))
            }
            for k in shared..<added.count {
                rows.append(Row(kind: .added, leftNumber: nil, rightNumber: added[k].0,
                                left: "", right: added[k].1))
            }
            removed.removeAll()
            added.removeAll()
        }

        while i < left.count && j < right.count {
            if left[i] == right[j] {
                flush()
                rows.append(Row(kind: .equal, leftNumber: leftStart + i + 1, rightNumber: rightStart + j + 1,
                                left: left[i], right: right[j]))
                i += 1; j += 1
            } else if lengths[i + 1][j] >= lengths[i][j + 1] {
                removed.append((leftStart + i + 1, left[i])); i += 1
            } else {
                added.append((rightStart + j + 1, right[j])); j += 1
            }
        }
        while i < left.count { removed.append((leftStart + i + 1, left[i])); i += 1 }
        while j < right.count { added.append((rightStart + j + 1, right[j])); j += 1 }
        flush()
        return rows
    }

    /// Fallback for very large differing sections: pair the lines positionally.
    private static func blockRows(_ left: [String], _ right: [String],
                                  leftStart: Int, rightStart: Int, syntax: CommentSyntax?) -> [Row] {
        var rows: [Row] = []
        for index in 0..<max(left.count, right.count) {
            let leftLine = index < left.count ? left[index] : nil
            let rightLine = index < right.count ? right[index] : nil
            switch (leftLine, rightLine) {
            case let (l?, r?):
                if l == r {
                    rows.append(Row(kind: .equal,
                                    leftNumber: leftStart + index + 1, rightNumber: rightStart + index + 1,
                                    left: l, right: r))
                } else {
                    let (change, leftRange, rightRange) = describe(left: l, right: r, syntax: syntax)
                    rows.append(Row(kind: .changed,
                                    leftNumber: leftStart + index + 1, rightNumber: rightStart + index + 1,
                                    left: l, right: r, changeKind: change,
                                    leftHighlight: leftRange, rightHighlight: rightRange))
                }
            case let (l?, nil):
                rows.append(Row(kind: .removed, leftNumber: leftStart + index + 1, rightNumber: nil,
                                left: l, right: ""))
            case let (nil, r?):
                rows.append(Row(kind: .added, leftNumber: nil, rightNumber: rightStart + index + 1,
                                left: "", right: r))
            default:
                break
            }
        }
        return rows
    }
}