PureXML/Sources/XSLT/XSLTNumbering.swift

/// The full `xsl:number` of XSLT 1.0 section 7.7: `level` single/multiple/any
/// with `count` and `from` patterns, an explicit `value` expression, and the
/// format-token engine (alternating separators and `1`/`01`/`a`/`A`/`i`/`I`
/// tokens, the last token reused, `.` as the default separator).
enum XSLTNumbering {
    typealias Tree = PureXML.Model.TreeNode

    /// The numbers `xsl:number` renders for `node`, computed per level with
    /// `matches` deciding pattern membership (the transformer's match cache).
    static func numbers(
        of node: Tree,
        level: String,
        count: String?,
        from: String?,
        siblingCache: SiblingPositionCache? = nil,
        matches: (Tree, String) -> Bool,
    ) -> [Int] {
        func matchesCount(_ candidate: Tree) -> Bool {
            if let count {
                return matches(candidate, count)
            }
            return candidate.kind == node.kind && candidate.name?.description == node.name?.description
        }
        func matchesFrom(_ candidate: Tree) -> Bool {
            from.map { matches(candidate, $0) } ?? false
        }
        // The count test is the same for every candidate of this call, so the
        // sibling-position cache can key by it. An explicit count is identified
        // by its pattern; the default count by the node's kind and name (a NUL
        // prefix keeps it out of the pattern-string space).
        let patternKey = count ?? "\u{0}\(node.kind):\(node.name?.description ?? "")"
        func position(of candidate: Tree) -> Int {
            siblingPosition(of: candidate, matching: matchesCount, cache: siblingCache, patternKey: patternKey)
        }
        switch level {
        case "multiple":
            var counts: [Int] = []
            var current: Tree? = node
            while let candidate = current, !matchesFrom(candidate) {
                if matchesCount(candidate) {
                    counts.append(position(of: candidate))
                }
                current = candidate.parent
            }
            return counts.reversed()
        case "any":
            var total = 0
            walkPreceding(node) { candidate in
                if matchesFrom(candidate) {
                    return false
                }
                if matchesCount(candidate) {
                    total += 1
                }
                return true
            }
            return [total]
        default: // single
            var current: Tree? = node
            while let candidate = current {
                // The count node may be the from node itself when it matches both
                // patterns (7.7), so test count before stopping at the boundary.
                if matchesCount(candidate) {
                    return [position(of: candidate)]
                }
                if matchesFrom(candidate) {
                    break
                }
                current = candidate.parent
            }
            return []
        }
    }

    /// 1 + the count of preceding siblings the count pattern matches, i.e. the
    /// node's one-based rank among the parent's matching children. With a cache,
    /// each parent's matching children are ranked once and reused, so numbering
    /// a wide list is linear rather than quadratic.
    private static func siblingPosition(
        of node: Tree,
        matching matchesCount: (Tree) -> Bool,
        cache: SiblingPositionCache?,
        patternKey: String,
    ) -> Int {
        guard let parent = node.parent else { return 1 }
        if let cache {
            return cache.rank(of: node, in: parent, patternKey: patternKey, matching: matchesCount)
        }
        var position = 1
        for sibling in parent.children {
            if sibling === node {
                break
            }
            if matchesCount(sibling) {
                position += 1
            }
        }
        return position
    }

    /// Caches, per parent and count pattern, the one-based rank of each matching
    /// child among the parent's matching children, so `xsl:number` level single
    /// and multiple do not rescan the child list for every numbered node.
    final class SiblingPositionCache {
        /// parent -> count pattern -> child -> one-based rank among matches.
        private var ranks: [ObjectIdentifier: [String: [ObjectIdentifier: Int]]] = [:]

        func rank(of node: Tree, in parent: Tree, patternKey: String, matching matchesCount: (Tree) -> Bool) -> Int {
            let parentIdentity = ObjectIdentifier(parent)
            if let table = ranks[parentIdentity]?[patternKey] {
                return table[ObjectIdentifier(node)] ?? 1
            }
            var built: [ObjectIdentifier: Int] = [:]
            var rank = 0
            for child in parent.children where matchesCount(child) {
                rank += 1
                built[ObjectIdentifier(child)] = rank
            }
            ranks[parentIdentity, default: [:]][patternKey] = built
            return built[ObjectIdentifier(node)] ?? 1
        }
    }

    /// Visits `node` and everything before it in document order (ancestors
    /// included), nearest first; the visitor returns false to stop.
    private static func walkPreceding(_ node: Tree, _ visit: (Tree) -> Bool) {
        var current: Tree? = node
        while let candidate = current {
            if !visit(candidate) {
                return
            }
            if let parent = candidate.parent {
                // The preceding siblings, nearest first. Find the candidate's
                // index in the child list once, then walk the children before it
                // directly, rather than rescanning the whole list for each
                // preceding sibling (which made `xsl:number level="any"` cubic
                // over a wide fan-out).
                let index = parent.children.firstIndex { $0 === candidate } ?? 0
                for visited in parent.children[..<index].reversed() where !visitSubtreeReversed(visited, visit) {
                    return
                }
            }
            current = candidate.parent
        }
    }

    private static func visitSubtreeReversed(_ node: Tree, _ visit: (Tree) -> Bool) -> Bool {
        for child in node.children.reversed() where !visitSubtreeReversed(child, visit) {
            return false
        }
        return visit(node)
    }

    // MARK: Format tokens

    /// Renders `numbers` with the 7.7.1 format engine. An empty list (a
    /// single/multiple level whose count pattern matched nothing) renders as
    /// the empty string, punctuation included.
    static func format(_ numbers: [Int], _ format: String, _ grouping: (separator: String, size: Int)? = nil) -> String {
        guard !numbers.isEmpty else { return "" }
        let pieces = tokenize(format.isEmpty ? "1" : format)
        var result = pieces.prefix
        var lastToken = "1"
        var lastSeparator = "."
        for (offset, number) in numbers.enumerated() {
            if offset > 0 {
                result += offset - 1 < pieces.separators.count ? pieces.separators[offset - 1] : lastSeparator
            }
            let token = offset < pieces.tokens.count ? pieces.tokens[offset] : lastToken
            result += render(number, token, grouping)
            if offset < pieces.tokens.count {
                lastToken = pieces.tokens[offset]
            }
            if offset > 0, offset - 1 < pieces.separators.count {
                lastSeparator = pieces.separators[offset - 1]
            }
        }
        return result + pieces.suffix
    }

    private struct FormatPieces {
        var prefix = ""
        var tokens: [String] = []
        var separators: [String] = []
        var suffix = ""
    }

    /// Splits a format string into leading punctuation, alternating format
    /// tokens and separators, and trailing punctuation.
    private static func tokenize(_ format: String) -> FormatPieces {
        var pieces = FormatPieces()
        var currentSeparator = ""
        var sawToken = false
        var index = format.startIndex
        while index < format.endIndex {
            if format[index].isLetter || format[index].isNumber {
                var token = ""
                while index < format.endIndex, format[index].isLetter || format[index].isNumber {
                    token.append(format[index])
                    index = format.index(after: index)
                }
                if sawToken {
                    pieces.separators.append(currentSeparator)
                } else {
                    pieces.prefix = currentSeparator
                }
                currentSeparator = ""
                pieces.tokens.append(token)
                sawToken = true
            } else {
                currentSeparator.append(format[index])
                index = format.index(after: index)
            }
        }
        pieces.suffix = currentSeparator
        if !sawToken {
            pieces.prefix = ""
            pieces.suffix = currentSeparator
        }
        return pieces
    }

    /// One number in one token's style.
    static func render(_ number: Int, _ token: String, _ grouping: (separator: String, size: Int)? = nil) -> String {
        switch token.first {
        case "A": return alphabetic(number, base: 65, letters: 26)
        case "a": return alphabetic(number, base: 97, letters: 26)
        case "I": return roman(number).uppercased()
        case "i": return roman(number)
        case "\u{3B1}": return alphabetic(number, base: 0x3B1, letters: 25)
        default:
            var digits = String(number)
            let width = token.count
            if digits.count < width {
                digits = String(repeating: "0", count: width - digits.count) + digits
            }
            return grouped(digits, grouping)
        }
    }

    /// Digit grouping per `grouping-separator`/`grouping-size`, applied from
    /// the right.
    private static func grouped(_ digits: String, _ grouping: (separator: String, size: Int)?) -> String {
        guard let grouping, grouping.size > 0, digits.count > grouping.size else { return digits }
        var groups: [String] = []
        var rest = digits[...]
        while rest.count > grouping.size {
            groups.append(String(rest.suffix(grouping.size)))
            rest = rest.dropLast(grouping.size)
        }
        groups.append(String(rest))
        return groups.reversed().joined(separator: grouping.separator)
    }

    private static func alphabetic(_ number: Int, base: UInt32, letters: Int) -> String {
        var value = number
        var result = ""
        while value > 0 {
            let remainder = UInt32((value - 1) % letters)
            if let scalar = Unicode.Scalar(base + remainder) {
                result = String(Character(scalar)) + result
            }
            value = (value - 1) / letters
        }
        return result
    }

    private static func roman(_ number: Int) -> String {
        let table: [(Int, String)] = [
            (1000, "m"), (900, "cm"), (500, "d"), (400, "cd"), (100, "c"), (90, "xc"),
            (50, "l"), (40, "xl"), (10, "x"), (9, "ix"), (5, "v"), (4, "iv"), (1, "i"),
        ]
        var value = number
        var result = ""
        for (amount, numeral) in table {
            while value >= amount {
                result += numeral
                value -= amount
            }
        }
        return result
    }
}