SPB Git

Repository Public

MathConverter.swift 42.8 KB 944 lines swift

1// ORIX Docs2// File: Packages/ORIXDocsKit/Sources/DocDOCX/MathConverter.swift3// Description: Math conversion between LaTeX, Office Math (OMML) and presentation MathML: public API, the math tree,4//              symbol tables, the LaTeX parser and the canonical LaTeX writer.5//6// Author: Simon-Pierre Boucher7// Contact: contact@spboucher.ai8import Foundation910public enum MathConverter {11    /// `<m:oMath>…</m:oMath>` for a LaTeX formula (the `m:` prefix is not declared here: the enclosing part declares it).12    /// Returns nil when the LaTeX cannot be parsed (unbalanced braces, unknown command or environment, nesting deeper than the cap).13    public static func omml(fromLatex latex: String) -> String? {14        MathStack.run {15            guard let nodes = MathLatexParser.parse(latex) else { return nil }16            return "<m:oMath>" + MathOMMLWriter.write(nodes) + "</m:oMath>"17        }18    }1920    /// LaTeX for an `<m:oMath>` or `<m:oMathPara>` element given as a string, with or without namespace declarations.21    /// Returns nil when the XML cannot be parsed.22    public static func latex(fromOMML xml: String) -> String? {23        var body = xml.trimmingCharacters(in: .whitespacesAndNewlines)24        if body.hasPrefix("<?xml"), let end = body.range(of: "?>") { body.removeSubrange(body.startIndex..<end.upperBound) }25        let wrapped = "<root xmlns:m=\"\(XMLNS.m)\" xmlns:w=\"\(XMLNS.w)\" xmlns:w14=\"\(XMLNS.w14)\" xmlns:mc=\"\(XMLNS.mc)\">" + body + "</root>"26        guard let root = try? XMLTree.parse(Data(wrapped.utf8), part: "OMML"), let node = root.children.first else { return nil }27        return latex(fromOMMLNode: node).latex28    }2930    /// Presentation MathML for a LaTeX formula. Returns nil when the LaTeX cannot be parsed.31    public static func mathML(fromLatex latex: String, display: Bool) -> String? {32        MathStack.run {33            guard let nodes = MathLatexParser.parse(latex) else { return nil }34            return "<math xmlns=\"http://www.w3.org/1998/Math/MathML\" display=\"\(display ? "block" : "inline")\">"35                + MathMLWriter.write(nodes) + "</math>"36        }37    }3839    /// LaTeX for a parsed `m:oMath` or `m:oMathPara` node. `unsupported` names the OMML elements that had no mapping;40    /// their content is still converted best-effort, never dropped.41    static func latex(fromOMMLNode node: XMLNode) -> (latex: String, unsupported: [String]) {42        MathStack.run {43            var reader = MathOMMLReader()44            if node.name == "m:oMathPara" {45                let parts = node.children.filter { $0.name == "m:oMath" }.map { MathLatexWriter.write(reader.nodes(of: $0, depth: 0)) }46                return (parts.joined(separator: " \\\\ "), reader.unsupported)47            }48            return (MathLatexWriter.write(reader.nodes(of: node, depth: 0)), reader.unsupported)49        }50    }51}5253/// The converters are recursive. Nesting is capped, and the work moves to a thread with a large stack when the caller's54/// stack is short (Swift concurrency and GCD threads have 512 KB), so hostile nesting cannot overflow the stack.55enum MathStack {56    private static let needed = 4 << 205758    private final class Job<T>: @unchecked Sendable {59        var body: (() -> T)?60        var result: T?61    }6263    static func remaining() -> Int {64        let me = pthread_self()65        let top = UInt(bitPattern: pthread_get_stackaddr_np(me))66        let size = pthread_get_stacksize_np(me)67        var marker = 068        let here = withUnsafeMutablePointer(to: &marker) { UInt(bitPattern: $0) }69        guard here <= top else { return 0 }70        return size - Int(top - here)71    }7273    static func run<T>(_ body: () -> T) -> T {74        if remaining() >= needed { return body() }75        return withoutActuallyEscaping(body) { escaping in76            let job = Job<T>()77            job.body = escaping78            let done = DispatchSemaphore(value: 0)79            let thread = Thread {80                job.result = job.body?()81                job.body = nil82                done.signal()83            }84            thread.stackSize = 16 << 2085            thread.start()86            done.wait()87            return job.result!88        }89    }90}9192// MARK: - Tree9394enum MathStyle: String, Sendable {95    case rm, bf, bfit, bb, cal, frak, sf, tt96    var command: String {97        switch self {98        case .rm: return "mathrm"99        case .bf: return "mathbf"100        case .bfit: return "boldsymbol"101        case .bb: return "mathbb"102        case .cal: return "mathcal"103        case .frak: return "mathfrak"104        case .sf: return "mathsf"105        case .tt: return "mathtt"106        }107    }108    /// OMML `m:scr` value for script styles.109    var scr: String? {110        switch self {111        case .bb: return "double-struck"112        case .cal: return "script"113        case .frak: return "fraktur"114        case .sf: return "sans-serif"115        case .tt: return "monospace"116        default: return nil117        }118    }119    /// OMML `m:sty` value for weight / slant styles.120    var sty: String? {121        switch self {122        case .rm: return "p"123        case .bf: return "b"124        case .bfit: return "bi"125        default: return nil126        }127    }128    var mathVariant: String {129        switch self {130        case .rm: return "normal"131        case .bf: return "bold"132        case .bfit: return "bold-italic"133        case .bb: return "double-struck"134        case .cal: return "script"135        case .frak: return "fraktur"136        case .sf: return "sans-serif"137        case .tt: return "monospace"138        }139    }140}141142enum MathFracType: String, Sendable { case bar, noBar, lin, skw }143144/// The math tree shared by the three notations.145indirect enum MathNode: Equatable, Sendable {146    case row([MathNode])147    /// One literal character (letter, digit, operator, symbol, space).148    case char(String)149    case text(String)150    /// A named operator: a LaTeX function name ("sin", "limsup") or a custom `\operatorname`.151    case funcName(String)152    case styled(MathStyle, MathNode)153    case frac(MathNode, MathNode, MathFracType)154    case sqrt(MathNode?, MathNode)155    case sup(MathNode, MathNode)156    case sub(MathNode, MathNode)157    case subsup(MathNode, MathNode, MathNode)158    /// Operator character, lower limit, upper limit, operand.159    case nary(String, MathNode?, MathNode?, MathNode)160    /// Opening character, closing character, separator, parts.161    case delim(String, String, String, [MathNode])162    /// LaTeX accent name ("hat", "vec" …).163    case accent(String, MathNode)164    case bar(top: Bool, MathNode)165    /// Function head (a `funcName`, possibly with scripts or limits) applied to an argument.166    case function(MathNode, MathNode)167    case under(MathNode, MathNode)168    case over(MathNode, MathNode)169    case groupChr(String, top: Bool, MathNode)170    case matrix([[MathNode]])171    case eqArray([[MathNode]])172    case boxed(MathNode)173    case phantom(MathNode)174175    var items: [MathNode] { if case .row(let r) = self { return r } else { return [self] } }176    var isEmptyRow: Bool { if case .row(let r) = self { return r.isEmpty } else { return false } }177    static let empty = MathNode.row([])178179    /// Depth of nested constructs (rows do not count). Stops descending once `limit` is exceeded.180    func nesting(limit: Int) -> Int {181        if limit < 0 { return 1 }182        func deepest(_ children: [MathNode?]) -> Int {183            var d = 0184            for case let c? in children { d = max(d, c.nesting(limit: limit - 1)); if d > limit { break } }185            return d186        }187        switch self {188        case .row(let r): return r.reduce(0) { max($0, $1.nesting(limit: limit)) }189        case .char, .text, .funcName: return 1190        case .styled(_, let a), .accent(_, let a), .bar(_, let a), .groupChr(_, _, let a), .boxed(let a), .phantom(let a): return 1 + deepest([a])191        case .frac(let a, let b, _), .sup(let a, let b), .sub(let a, let b), .function(let a, let b), .under(let a, let b), .over(let a, let b):192            return 1 + deepest([a, b])193        case .sqrt(let a, let b): return 1 + deepest([a, b])194        case .subsup(let a, let b, let c): return 1 + deepest([a, b, c])195        case .nary(_, let a, let b, let c): return 1 + deepest([a, b, c])196        case .delim(_, _, _, let parts): return 1 + deepest(parts)197        case .matrix(let rows), .eqArray(let rows): return 1 + deepest(rows.flatMap { $0 })198        }199    }200201    /// A row of one element collapses to that element; nested rows are flattened.202    static func make(_ nodes: [MathNode]) -> MathNode {203        var flat: [MathNode] = []204        for n in nodes { if case .row(let r) = n { flat.append(contentsOf: r) } else { flat.append(n) } }205        return flat.count == 1 ? flat[0] : .row(flat)206    }207}208209// MARK: - Tables210211enum MathTables {212    /// (LaTeX command, character). The first command listed for a character is the canonical one.213    static let symbolList: [(String, String)] = [214        ("alpha", "α"), ("beta", "β"), ("gamma", "γ"), ("delta", "δ"), ("epsilon", "ϵ"), ("varepsilon", "ε"), ("zeta", "ζ"), ("eta", "η"),215        ("theta", "θ"), ("vartheta", "ϑ"), ("iota", "ι"), ("kappa", "κ"), ("lambda", "λ"), ("mu", "μ"), ("nu", "ν"), ("xi", "ξ"), ("pi", "π"),216        ("varpi", "ϖ"), ("rho", "ρ"), ("varrho", "ϱ"), ("sigma", "σ"), ("varsigma", "ς"), ("tau", "τ"), ("upsilon", "υ"), ("phi", "ϕ"),217        ("varphi", "φ"), ("chi", "χ"), ("psi", "ψ"), ("omega", "ω"),218        ("Gamma", "Γ"), ("Delta", "Δ"), ("Theta", "Θ"), ("Lambda", "Λ"), ("Xi", "Ξ"), ("Pi", "Π"), ("Sigma", "Σ"), ("Upsilon", "Υ"),219        ("Phi", "Φ"), ("Psi", "Ψ"), ("Omega", "Ω"),220        ("times", "×"), ("div", "÷"), ("cdot", "⋅"), ("pm", "±"), ("mp", "∓"), ("ast", "∗"), ("star", "⋆"), ("circ", "∘"), ("bullet", "∙"),221        ("oplus", "⊕"), ("ominus", "⊖"), ("otimes", "⊗"), ("odot", "⊙"), ("cup", "∪"), ("cap", "∩"), ("setminus", "∖"), ("wedge", "∧"),222        ("land", "∧"), ("vee", "∨"), ("lor", "∨"), ("neg", "¬"), ("lnot", "¬"), ("dagger", "†"), ("ddagger", "‡"), ("sqcup", "⊔"), ("sqcap", "⊓"),223        ("leq", "≤"), ("le", "≤"), ("geq", "≥"), ("ge", "≥"), ("neq", "≠"), ("ne", "≠"), ("approx", "≈"), ("equiv", "≡"), ("sim", "∼"),224        ("simeq", "≃"), ("cong", "≅"), ("propto", "∝"), ("ll", "≪"), ("gg", "≫"), ("prec", "≺"), ("succ", "≻"), ("preceq", "⪯"), ("succeq", "⪰"),225        ("in", "∈"), ("notin", "∉"), ("ni", "∋"), ("subset", "⊂"), ("supset", "⊃"), ("subseteq", "⊆"), ("supseteq", "⊇"), ("perp", "⊥"),226        ("bot", "⊥"), ("parallel", "∥"), ("mid", "∣"), ("vdash", "⊢"), ("dashv", "⊣"), ("models", "⊨"), ("doteq", "≐"), ("asymp", "≍"),227        ("to", "→"), ("rightarrow", "→"), ("leftarrow", "←"), ("gets", "←"), ("leftrightarrow", "↔"), ("Rightarrow", "⇒"), ("Leftarrow", "⇐"),228        ("Leftrightarrow", "⇔"), ("mapsto", "↦"), ("uparrow", "↑"), ("downarrow", "↓"), ("longrightarrow", "⟶"), ("longleftarrow", "⟵"),229        ("Longrightarrow", "⟹"), ("implies", "⟹"), ("iff", "⟺"), ("Longleftrightarrow", "⟺"), ("hookrightarrow", "↪"), ("nearrow", "↗"),230        ("searrow", "↘"), ("rightharpoonup", "⇀"), ("rightleftharpoons", "⇌"),231        ("infty", "∞"), ("partial", "∂"), ("nabla", "∇"), ("forall", "∀"), ("exists", "∃"), ("nexists", "∄"), ("emptyset", "∅"),232        ("varnothing", "∅"), ("ell", "ℓ"), ("hbar", "ℏ"), ("Re", "ℜ"), ("Im", "ℑ"), ("aleph", "ℵ"), ("wp", "℘"), ("angle", "∠"),233        ("triangle", "△"), ("prime", "′"), ("top", "⊤"), ("ldots", "…"), ("dots", "…"), ("cdots", "⋯"), ("vdots", "⋮"), ("ddots", "⋱"),234        ("therefore", "∴"), ("because", "∵"), ("surd", "√"), ("degree", "°"), ("backslash", "\\"), ("langle", "⟨"), ("rangle", "⟩"),235        ("lfloor", "⌊"), ("rfloor", "⌋"), ("lceil", "⌈"), ("rceil", "⌉"), ("|", "‖"), ("Vert", "‖"), ("{", "{"), ("lbrace", "{"),236        ("}", "}"), ("rbrace", "}"), ("%", "%"), ("#", "#"), ("&", "&"), ("$", "$"), ("_", "_"), ("S", "§"), ("P", "¶"),237        ("copyright", "©"), ("pounds", "£"), ("textasciicircum", "^"), ("textasciitilde", "~"), ("vert", "|"), ("lvert", "|"), ("rvert", "|"),238        ("lVert", "‖"), ("rVert", "‖"),239        (",", "\u{2009}"), (":", "\u{205F}"), (">", "\u{205F}"), (";", "\u{2004}"), ("quad", "\u{2003}"), (" ", "\u{00A0}"), ("!", "\u{200B}"),240    ]241    static let symbols: [String: String] = Dictionary(symbolList, uniquingKeysWith: { a, _ in a })242243    static let naryList: [(String, String)] = [244        ("sum", "∑"), ("prod", "∏"), ("coprod", "∐"), ("int", "∫"), ("iint", "∬"), ("iiint", "∭"), ("oint", "∮"), ("bigcup", "⋃"),245        ("bigcap", "⋂"), ("bigoplus", "⨁"), ("bigotimes", "⨂"), ("bigvee", "⋁"), ("bigwedge", "⋀"), ("bigsqcup", "⨆"), ("biguplus", "⨄"),246        ("bigodot", "⨀"),247    ]248    static let nary: [String: String] = Dictionary(naryList, uniquingKeysWith: { a, _ in a })249    static let naryCommand: [String: String] = Dictionary(naryList.map { ($0.1, $0.0) }, uniquingKeysWith: { a, _ in a })250    static let integrals: Set<String> = ["∫", "∬", "∭", "∮"]251252    /// Character → LaTeX (without the trailing space; the writer separates control words from letters itself).253    static let latexForChar: [String: String] = {254        var d: [String: String] = [:]255        for (cmd, ch) in symbolList where d[ch] == nil {256            // Braces, the double bar and the ASCII specials are escaped characters, everything else is a control word or symbol.257            d[ch] = "\\" + cmd258        }259        d["|"] = "|"260        for (cmd, ch) in naryList { d[ch] = "\\" + cmd }261        d["−"] = "-"262        d[" "] = "\\ "263        d["∆"] = "\\Delta"; d["µ"] = "\\mu"; d["∕"] = "/"; d["〈"] = "\\langle"; d["〉"] = "\\rangle"264        d["\u{2329}"] = "\\langle"; d["\u{232A}"] = "\\rangle"; d["\u{2006}"] = "\\,"; d["\u{200A}"] = "\\,"; d["\u{2005}"] = "\\;"265        d["\u{2002}"] = "\\quad"; d["\u{22C5}"] = "\\cdot"; d["·"] = "\\cdot"266        for (ch, letter) in [("ℝ", "R"), ("ℂ", "C"), ("ℕ", "N"), ("ℤ", "Z"), ("ℚ", "Q"), ("ℙ", "P"), ("ℍ", "H")] { d[ch] = "\\mathbb{\(letter)}" }267        return d268    }()269270    /// Function name → text shown (and stored in OMML).271    static let functionList: [String] = ["sin", "cos", "tan", "cot", "sec", "csc", "arcsin", "arccos", "arctan", "sinh", "cosh", "tanh", "coth",272                                         "log", "ln", "lg", "exp", "lim", "limsup", "liminf", "max", "min", "sup", "inf", "det", "dim", "ker", "gcd",273                                         "arg", "deg", "hom", "Pr"]274    static let functions: Set<String> = Set(functionList)275    static let limitFunctions: Set<String> = ["lim", "limsup", "liminf", "max", "min", "sup", "inf", "det", "gcd", "Pr"]276    static func functionDisplay(_ name: String) -> String {277        switch name {278        case "limsup": return "lim sup"279        case "liminf": return "lim inf"280        default: return name281        }282    }283    static func functionName(display: String) -> String? {284        switch display {285        case "lim sup": return "limsup"286        case "lim inf": return "liminf"287        default: return functions.contains(display) ? display : nil288        }289    }290291    /// LaTeX accent name → combining character written in OMML.292    static let accentList: [(String, String)] = [("hat", "\u{0302}"), ("bar", "\u{0304}"), ("tilde", "\u{0303}"), ("vec", "\u{20D7}"),293                                                 ("dot", "\u{0307}"), ("ddot", "\u{0308}"), ("check", "\u{030C}"), ("breve", "\u{0306}"),294                                                 ("acute", "\u{0301}"), ("grave", "\u{0300}")]295    static let accents: [String: String] = Dictionary(accentList, uniquingKeysWith: { a, _ in a })296    static let accentAliases: [String: String] = ["widehat": "hat", "widetilde": "tilde", "overrightarrow": "vec"]297    /// Accent character (combining or spacing form) → LaTeX accent name.298    static let accentName: [String: String] = {299        var d: [String: String] = Dictionary(accentList.map { ($0.1, $0.0) }, uniquingKeysWith: { a, _ in a })300        for (ch, name) in [("^", "hat"), ("ˆ", "hat"), ("~", "tilde"), ("˜", "tilde"), ("¯", "bar"), ("‾", "bar"), ("\u{0305}", "bar"), ("ˉ", "bar"),301                           ("→", "vec"), ("\u{20D1}", "vec"), ("˙", "dot"), ("¨", "ddot"), ("ˇ", "check"), ("˘", "breve"), ("´", "acute"), ("`", "grave")] {302            d[ch] = name303        }304        return d305    }()306    /// Spacing character used for an accent in MathML.307    static let accentSpacing: [String: String] = ["hat": "^", "bar": "¯", "tilde": "~", "vec": "→", "dot": "˙", "ddot": "¨", "check": "ˇ",308                                                  "breve": "˘", "acute": "´", "grave": "`"]309310    static let styleCommands: [String: MathStyle] = ["mathrm": .rm, "mathbf": .bf, "boldsymbol": .bfit, "bm": .bfit, "mathbb": .bb, "mathcal": .cal,311                                                     "mathfrak": .frak, "mathsf": .sf, "mathtt": .tt, "mathscr": .cal, "textbf": .bf]312313    /// Characters that can stand as the unbraced operand of a function or big operator.314    static func isOperand(_ ch: String) -> Bool {315        guard let c = ch.first else { return false }316        return c.isLetter || c.isNumber || ch == "∞" || ch == "∂" || ch == "∇" || ch == "∅"317    }318319    /// (open, close) → matrix environment.320    static func matrixEnvironment(open: String, close: String) -> String? {321        switch (open, close) {322        case ("(", ")"): return "pmatrix"323        case ("[", "]"): return "bmatrix"324        case ("{", "}"): return "Bmatrix"325        case ("|", "|"): return "vmatrix"326        case ("‖", "‖"): return "Vmatrix"327        default: return nil328        }329    }330331    static func isFunctionHead(_ n: MathNode) -> Bool {332        switch n {333        case .funcName: return true334        case .sup(let b, _), .sub(let b, _), .subsup(let b, _, _): if case .funcName = b { return true } else { return false }335        case .under(let b, _), .over(let b, _):336            if case .funcName(let name) = b { return limitFunctions.contains(name) }337            if case .under(.funcName(let name), _) = b { return limitFunctions.contains(name) }338            return false339        default: return false340        }341    }342}343344// MARK: - LaTeX parser345346struct MathLatexParser {347    private struct Failure: Error {}348    /// Units of recursion (a brace group costs two, a command argument three): about 130 to 200 nested constructs.349    private static let maxDepth = 400350    static let maxNesting = 100351352    private let chars: [Character]353    private var i = 0354    private var depth = 0355    /// True while reading the optional argument of `\sqrt[…]` at brace depth zero.356    private var stopAtBracket = false357358    static func parse(_ latex: String) -> [MathNode]? {359        var p = MathLatexParser(chars: Array(latex))360        do {361            let rows = try p.alignedRows()362            p.skipSpace()363            guard p.i >= p.chars.count else { return nil }364            let nodes: [MathNode] = rows.count == 1 && rows[0].count == 1 ? rows[0][0].items : [.eqArray(rows)]365            // Each construct nests two XML elements in OMML; staying under 100 keeps our own output readable by the XML layer (256 levels).366            guard MathNode.row(nodes).nesting(limit: maxNesting) <= maxNesting else { return nil }367            return nodes368        } catch { return nil }369    }370371    private init(chars: [Character]) { self.chars = chars }372373    // Lexing helpers374375    private mutating func skipSpace() {376        while i < chars.count {377            if chars[i].isWhitespace { i += 1 }378            else if chars[i] == "%" { while i < chars.count, !chars[i].isNewline { i += 1 } }379            else { break }380        }381    }382383    /// The command at the cursor without consuming it: letters after a backslash, or one non-letter character.384    private func peekCommand() -> (name: String, end: Int)? {385        guard i < chars.count, chars[i] == "\\", i + 1 < chars.count else { return nil }386        var j = i + 1387        if chars[j].isASCII && chars[j].isLetter {388            while j < chars.count, chars[j].isASCII, chars[j].isLetter { j += 1 }389            return (String(chars[(i + 1)..<j]), j)390        }391        return (String(chars[j]), j + 1)392    }393394    private func atTerminator() -> Bool {395        guard i < chars.count else { return true }396        let c = chars[i]397        if c == "}" || c == "&" { return true }398        if c == "]" && stopAtBracket { return true }399        if let cmd = peekCommand()?.name, cmd == "\\" || cmd == "right" || cmd == "middle" || cmd == "end" { return true }400        return false401    }402403    private mutating func enter() throws { depth += 1; if depth > MathLatexParser.maxDepth { throw Failure() } }404    private mutating func leave() { depth -= 1 }405406    // Grammar407408    /// Rows separated by `\\`, cells separated by `&`.409    private mutating func alignedRows() throws -> [[MathNode]] {410        var rows: [[MathNode]] = [[]]411        while true {412            let cell = MathNode.make(try row())413            rows[rows.count - 1].append(cell)414            if i < chars.count, chars[i] == "&" { i += 1; continue }415            if let cmd = peekCommand(), cmd.name == "\\" {416                i = cmd.end417                skipSpace()418                // Optional vertical space argument: \\[2pt]419                if i < chars.count, chars[i] == "[", let close = chars[i...].firstIndex(of: "]"),420                   chars[(i + 1)..<close].allSatisfy({ $0.isNumber || $0.isLetter || $0 == "." || $0 == "-" }) { i = close + 1 }421                rows.append([])422                continue423            }424            break425        }426        // A trailing `\\` leaves an empty last row.427        if rows.count > 1, let last = rows.last, last.count == 1, last[0].isEmptyRow { rows.removeLast() }428        return rows429    }430431    private mutating func row() throws -> [MathNode] {432        var out: [MathNode] = []433        while true {434            skipSpace()435            if atTerminator() { break }436            let n = try term()437            if case .row(let r) = n { out.append(contentsOf: r) } else { out.append(n) }438        }439        return out440    }441442    /// An atom with its scripts, plus the operand of a function or big operator.443    private mutating func term() throws -> MathNode {444        try enter(); defer { leave() }445        skipSpace()446        var base: MathNode447        if i < chars.count, chars[i] == "^" || chars[i] == "_" || chars[i] == "'" { base = .empty } else { base = try atom() }448        var sub: MathNode?, sup: MathNode?449        var sawScript = false450        scripts: while true {451            skipSpace()452            guard i < chars.count else { break }453            switch chars[i] {454            case "^":455                i += 1456                let a = try argument()457                sup = sup.map { .make($0.items + a.items) } ?? a458                sawScript = true459            case "_":460                i += 1461                let a = try argument()462                sub = sub.map { .make($0.items + a.items) } ?? a463                sawScript = true464            case "'":465                var primes: [MathNode] = []466                while i < chars.count, chars[i] == "'" { primes.append(.char("′")); i += 1 }467                sup = .make((sup?.items ?? []) + primes)468                sawScript = true469            default: break scripts470            }471        }472        if case .nary(let op, nil, nil, let body) = base, body.isEmptyRow {473            let operand = try operand(parenthesised: false)474            return .nary(op, sub, sup, operand ?? .empty)475        }476        if sawScript { base = MathLatexParser.attach(base: base, sub: sub, sup: sup) }477        if MathTables.isFunctionHead(base), let arg = try operand(parenthesised: true) { return .function(base, arg) }478        return base479    }480481    static func attach(base: MathNode, sub: MathNode?, sup: MathNode?) -> MathNode {482        if case .funcName(let name) = base, MathTables.limitFunctions.contains(name) {483            var n = base484            if let sub { n = .under(n, sub) }485            if let sup { n = .over(n, sup) }486            return n487        }488        if case .groupChr(_, let top, _) = base {489            if !top, let sub, sup == nil { return .under(base, sub) }490            if top, let sup, sub == nil { return .over(base, sup) }491        }492        switch (sub, sup) {493        case (let s?, let p?): return .subsup(base, s, p)494        case (let s?, nil): return .sub(base, s)495        case (nil, let p?): return .sup(base, p)496        default: return base497        }498    }499500    /// The operand following a function head or a big operator, when the next token can be one.501    private mutating func operand(parenthesised: Bool) throws -> MathNode? {502        skipSpace()503        guard i < chars.count, !atTerminator() else { return nil }504        let c = chars[i]505        if c == "{" { return try argument() }506        if c == "(" && parenthesised {507            // `\sin(x + 1)`: everything up to the matching parenthesis is the argument.508            var items: [MathNode] = []509            var level = 0510            while true {511                skipSpace()512                if atTerminator() { break }513                let t = try term()514                items.append(contentsOf: t.items)515                if case .char("(") = t { level += 1 }516                if case .char(")") = t { level -= 1; if level == 0 { break } }517            }518            return .row(items)519        }520        if c == "\\" {521            guard let cmd = peekCommand()?.name else { return nil }522            if let ch = MathTables.symbols[cmd], !MathTables.isOperand(ch) { return nil }523            if cmd == "limits" || cmd == "nolimits" { return nil }524            return try term()525        }526        if MathTables.isOperand(String(c)) { return try term() }527        return nil528    }529530    /// `{…}` or a single token.531    private mutating func argument() throws -> MathNode {532        try enter(); defer { leave() }533        skipSpace()534        guard i < chars.count else { throw Failure() }535        if chars[i] == "{" { return try group() }536        if chars[i] == "}" || chars[i] == "&" { throw Failure() }537        return try atom()538    }539540    private mutating func group() throws -> MathNode {541        guard i < chars.count, chars[i] == "{" else { throw Failure() }542        i += 1543        let saved = stopAtBracket544        stopAtBracket = false545        defer { stopAtBracket = saved }546        let rows = try alignedRows()547        guard i < chars.count, chars[i] == "}" else { throw Failure() }548        i += 1549        if rows.count == 1 && rows[0].count == 1 { return .make(rows[0][0].items) }550        return .eqArray(rows)551    }552553    /// The raw text of a `{…}` argument (used by `\text`, `\begin`, `\operatorname`).554    private mutating func rawGroup() throws -> String {555        skipSpace()556        guard i < chars.count, chars[i] == "{" else { throw Failure() }557        i += 1558        var out = ""559        var level = 0560        while i < chars.count {561            let c = chars[i]562            if c == "\\", i + 1 < chars.count {563                let next = chars[i + 1]564                if next.isASCII && next.isLetter {565                    var j = i + 1566                    while j < chars.count, chars[j].isASCII, chars[j].isLetter { j += 1 }567                    let name = String(chars[(i + 1)..<j])568                    i = j569                    switch name {570                    case "textbackslash": out += "\\"571                    case "textasciicircum": out += "^"572                    case "textasciitilde": out += "~"573                    default: throw Failure()574                    }575                    if i + 1 < chars.count, chars[i] == "{", chars[i + 1] == "}" { i += 2 } else if i < chars.count, chars[i] == " " { i += 1 }576                } else {577                    out.append(next)578                    i += 2579                }580                continue581            }582            if c == "{" { level += 1 } else if c == "}" {583                if level == 0 { i += 1; return out }584                level -= 1585            }586            if c == "~" { out += "\u{00A0}" } else { out.append(c) }587            i += 1588        }589        throw Failure()590    }591592    private mutating func delimiter() throws -> String {593        skipSpace()594        guard i < chars.count else { throw Failure() }595        if let cmd = peekCommand() {596            i = cmd.end597            switch cmd.name {598            case "{", "lbrace": return "{"599            case "}", "rbrace": return "}"600            case "|", "Vert", "lVert", "rVert": return "‖"601            case "vert", "lvert", "rvert": return "|"602            case "backslash": return "\\"603            default:604                guard let ch = MathTables.symbols[cmd.name] else { throw Failure() }605                return ch606            }607        }608        let c = chars[i]609        i += 1610        switch c {611        case ".": return ""612        case "<": return "⟨"613        case ">": return "⟩"614        case "{", "}", "^", "_", "&": throw Failure()615        default: return String(c)616        }617    }618619    private mutating func atom() throws -> MathNode {620        try enter(); defer { leave() }621        skipSpace()622        guard i < chars.count else { throw Failure() }623        let c = chars[i]624        if c == "{" { return try group() }625        if c == "}" || c == "&" || c == "^" || c == "_" || c == "#" || c == "$" { throw Failure() }626        if c == "\\" { return try command() }627        i += 1628        switch c {629        case "-": return .char("−")630        case "~": return .char("\u{00A0}")631        case "'": return .char("′")632        default: return .char(String(c))633        }634    }635636    private mutating func command() throws -> MathNode {637        guard let cmd = peekCommand() else { throw Failure() }638        i = cmd.end639        let name = cmd.name640        if let ch = MathTables.symbols[name] { return .char(ch) }641        if let op = MathTables.nary[name] { return .nary(op, nil, nil, .empty) }642        if MathTables.functions.contains(name) { return .funcName(name) }643        if let style = MathTables.styleCommands[name] { return .styled(style, try argument()) }644        if let accent = MathTables.accents[name] != nil ? name : MathTables.accentAliases[name] { return .accent(accent, try argument()) }645        switch name {646        case "frac", "dfrac", "tfrac", "cfrac":647            let a = try argument(), b = try argument()648            return .frac(a, b, .bar)649        case "binom", "dbinom", "tbinom":650            let a = try argument(), b = try argument()651            return .delim("(", ")", "|", [.frac(a, b, .noBar)])652        case "genfrac":653            let l = try rawGroup(), r = try rawGroup()654            let thickness = try rawGroup()655            _ = try rawGroup()656            let a = try argument(), b = try argument()657            let zero = thickness.hasPrefix("0")658            let f = MathNode.frac(a, b, zero ? .noBar : .bar)659            return l.isEmpty && r.isEmpty ? f : .delim(l, r, "|", [f])660        case "sqrt":661            skipSpace()662            var index: MathNode?663            if i < chars.count, chars[i] == "[" {664                i += 1665                let saved = stopAtBracket666                stopAtBracket = true667                let inner = try row()668                stopAtBracket = saved669                guard i < chars.count, chars[i] == "]" else { throw Failure() }670                i += 1671                index = .make(inner)672            }673            return .sqrt(index, try argument())674        case "overline": return .bar(top: true, try argument())675        case "underline": return .bar(top: false, try argument())676        case "text", "mbox", "textrm", "textnormal", "textit", "mathit":677            if name == "mathit" { return try argument() }678            return .text(try rawGroup())679        case "operatorname":680            skipSpace()681            if i < chars.count, chars[i] == "*" { i += 1 }682            let raw = try rawGroup().trimmingCharacters(in: .whitespaces)683            guard !raw.isEmpty else { throw Failure() }684            return .funcName(MathTables.functionName(display: raw) ?? raw)685        case "left":686            let open = try delimiter()687            var parts: [MathNode] = []688            var sep = "|"689            while true {690                parts.append(.make(try row()))691                guard let next = peekCommand() else { throw Failure() }692                if next.name == "middle" {693                    i = next.end694                    sep = try delimiter()695                    continue696                }697                guard next.name == "right" else { throw Failure() }698                i = next.end699                break700            }701            return .delim(open, try delimiter(), sep, parts)702        case "overset", "stackrel":703            let top = try argument(), base = try argument()704            return .over(base, top)705        case "underset":706            let bottom = try argument(), base = try argument()707            return .under(base, bottom)708        case "underbrace": return .groupChr("⏟", top: false, try argument())709        case "overbrace": return .groupChr("⏞", top: true, try argument())710        case "overleftarrow": return .groupChr("←", top: true, try argument())711        case "boxed", "fbox": return .boxed(try argument())712        case "phantom", "hphantom", "vphantom": return .phantom(try argument())713        case "begin": return try environment()714        case "qquad": return .row([.char("\u{2003}"), .char("\u{2003}")])715        case "limits", "nolimits", "displaystyle", "textstyle", "scriptstyle", "scriptscriptstyle", "nonumber", "notag",716             "big", "Big", "bigg", "Bigg", "bigl", "bigr", "Bigl", "Bigr", "biggl", "biggr", "Biggl", "Biggr", "bigm", "Bigm":717            return .empty718        case "label", "tag":719            _ = try rawGroup()720            return .empty721        default: throw Failure()722        }723    }724725    private mutating func environment() throws -> MathNode {726        var name = try rawGroup()727        if name.hasSuffix("*") { name.removeLast() }728        if name == "array" { _ = try rawGroup() }729        let saved = stopAtBracket730        stopAtBracket = false731        defer { stopAtBracket = saved }732        let rows = try alignedRows()733        guard let end = peekCommand(), end.name == "end" else { throw Failure() }734        i = end.end735        var endName = try rawGroup()736        if endName.hasSuffix("*") { endName.removeLast() }737        guard endName == name else { throw Failure() }738        switch name {739        case "matrix", "array", "smallmatrix": return .matrix(rows)740        case "pmatrix": return .delim("(", ")", "|", [.matrix(rows)])741        case "bmatrix": return .delim("[", "]", "|", [.matrix(rows)])742        case "Bmatrix": return .delim("{", "}", "|", [.matrix(rows)])743        case "vmatrix": return .delim("|", "|", "|", [.matrix(rows)])744        case "Vmatrix": return .delim("‖", "‖", "|", [.matrix(rows)])745        case "cases": return .delim("{", "", "|", [.eqArray(rows)])746        case "aligned", "align", "split", "gathered", "gather", "eqnarray", "alignedat", "equation": return .eqArray(rows)747        default: throw Failure()748        }749    }750}751752// MARK: - LaTeX writer753754/// Writes the canonical LaTeX form: scripts always braced, `\frac{a}{b}`, control words separated from a following letter by one space.755struct MathLatexWriter {756    private var out = ""757758    static func write(_ nodes: [MathNode]) -> String {759        var w = MathLatexWriter()760        w.row(nodes)761        return w.out762    }763764    static func escapeText(_ s: String) -> String {765        var out = ""766        for c in s {767            switch c {768            case "{", "}", "%", "#", "&", "$", "_": out += "\\" + String(c)769            case "\\": out += "\\textbackslash{}"770            case "^": out += "\\textasciicircum{}"771            case "~": out += "\\textasciitilde{}"772            case "\u{00A0}": out += "~"773            default: out.append(c)774            }775        }776        return out777    }778779    private var endsWithControlWord: Bool {780        var sawLetter = false781        for c in out.reversed() {782            if c.isASCII && c.isLetter { sawLetter = true; continue }783            return sawLetter && c == "\\"784        }785        return false786    }787788    private mutating func emit(_ s: String) {789        guard let first = s.first else { return }790        if first.isASCII && first.isLetter && endsWithControlWord { out += " " }791        out += s792    }793794    private mutating func braced(_ n: MathNode) { emit("{"); row(n.items); emit("}") }795796    private mutating func row(_ nodes: [MathNode]) {797        for (k, n) in nodes.enumerated() {798            node(n)799            // An operator or function without operand must not swallow the next term when the LaTeX is read back.800            if k < nodes.count - 1 {801                switch n {802                case .nary(_, _, _, let body) where body.isEmptyRow: emit("{}")803                case .function(_, let arg) where arg.isEmptyRow: emit("{}")804                default: break805                }806            }807        }808    }809810    /// True when the parser reads the written form of `n` back as exactly one operand.811    private func isGrabbable(_ n: MathNode) -> Bool {812        if MathTables.isFunctionHead(n) { return false }813        switch n {814        case .row: return false815        case .char(let c): return MathTables.isOperand(c) && (MathTables.latexForChar[c].map { !$0.contains("{") } ?? true)816        case .sup(let b, _), .sub(let b, _), .subsup(let b, _, _): return !baseNeedsBraces(b) && isGrabbable(b)817        case .nary(_, _, _, let body): return !body.isEmptyRow818        case .function(_, let arg): return !arg.isEmptyRow819        case .frac(_, _, let type): return type == .bar || type == .noBar820        default: return true821        }822    }823824    private func baseNeedsBraces(_ b: MathNode) -> Bool {825        switch b {826        case .row, .sup, .sub, .subsup, .nary, .function, .under, .over, .groupChr: return true827        case .frac(_, _, let type): return type == .lin || type == .skw828        default: return false829        }830    }831832    private mutating func base(_ b: MathNode) {833        if baseNeedsBraces(b) { braced(b) } else { node(b) }834    }835836    private mutating func operand(_ n: MathNode, parenthesised: Bool) {837        if n.isEmptyRow { return }838        if parenthesised, case .row(let items) = n, case .char("(")? = items.first {839            var level = 0, closesAt = -1840            for (k, it) in items.enumerated() {841                if case .char("(") = it { level += 1 }842                if case .char(")") = it { level -= 1; if level == 0 { closesAt = k; break } }843            }844            if closesAt == items.count - 1 { row(items); return }845        }846        if isGrabbable(n) { node(n) } else { braced(n) }847    }848849    private mutating func delimiterToken(_ ch: String) {850        switch ch {851        case "": emit(".")852        case "(", ")", "[", "]", "|", "/": emit(ch)853        default: emit(MathTables.latexForChar[ch] ?? ch)854        }855    }856857    private mutating func rows(_ rows: [[MathNode]]) {858        for (r, cells) in rows.enumerated() {859            if r > 0 { emit("\\\\") }860            for (c, cell) in cells.enumerated() {861                if c > 0 { emit("&") }862                row(cell.items)863            }864        }865    }866867    private mutating func environment(_ name: String, _ r: [[MathNode]]) {868        emit("\\begin{\(name)}"); rows(r); emit("\\end{\(name)}")869    }870871    private mutating func node(_ n: MathNode) {872        switch n {873        case .row(let items): row(items)874        case .char(let c): emit(MathTables.latexForChar[c] ?? c)875        case .text(let s): emit("\\text{" + MathLatexWriter.escapeText(s) + "}")876        case .funcName(let name):877            if MathTables.functions.contains(name) { emit("\\" + name) } else { emit("\\operatorname{" + MathLatexWriter.escapeText(name) + "}") }878        case .styled(let style, let body): emit("\\" + style.command); braced(body)879        case .frac(let a, let b, let type):880            switch type {881            case .bar: emit("\\frac"); braced(a); braced(b)882            case .noBar: emit("\\genfrac{}{}{0pt}{}"); braced(a); braced(b)883            case .lin, .skw: braced(a); emit("/"); braced(b)884            }885        case .sqrt(let index, let body):886            emit("\\sqrt")887            if let index { emit("["); row(index.items); emit("]") }888            braced(body)889        case .sup(let b, let p): base(b); emit("^"); braced(p)890        case .sub(let b, let s): base(b); emit("_"); braced(s)891        case .subsup(let b, let s, let p): base(b); emit("_"); braced(s); emit("^"); braced(p)892        case .nary(let op, let sub, let sup, let body):893            emit(MathTables.naryCommand[op].map { "\\" + $0 } ?? (MathTables.latexForChar[op] ?? op))894            if let sub { emit("_"); braced(sub) }895            if let sup { emit("^"); braced(sup) }896            operand(body, parenthesised: false)897        case .delim(let open, let close, let sep, let parts):898            if parts.count == 1 {899                let inner = parts[0]900                if case .matrix(let r) = inner, let env = MathTables.matrixEnvironment(open: open, close: close) { environment(env, r); return }901                if open == "{" && close == "" {902                    if case .eqArray(let r) = inner { environment("cases", r); return }903                    if case .matrix(let r) = inner { environment("cases", r); return }904                }905                if open == "(" && close == ")", case .frac(let a, let b, .noBar) = inner { emit("\\binom"); braced(a); braced(b); return }906            }907            emit("\\left"); delimiterToken(open)908            for (k, part) in parts.enumerated() {909                if k > 0 { emit("\\middle"); delimiterToken(sep) }910                row(part.items)911            }912            emit("\\right"); delimiterToken(close)913        case .accent(let name, let body): emit("\\" + name); braced(body)914        case .bar(let top, let body): emit(top ? "\\overline" : "\\underline"); braced(body)915        case .function(let head, let arg):916            node(head)917            operand(arg, parenthesised: true)918        case .under(let b, let u):919            if MathTables.isFunctionHead(n) { node(b); emit("_"); braced(u) }920            else if case .groupChr(_, false, _) = b { node(b); emit("_"); braced(u) }921            else { emit("\\underset"); braced(u); braced(b) }922        case .over(let b, let o):923            if MathTables.isFunctionHead(n) { node(b); emit("^"); braced(o) }924            else if case .groupChr(_, true, _) = b { node(b); emit("^"); braced(o) }925            else { emit("\\overset"); braced(o); braced(b) }926        case .groupChr(let ch, let top, let body):927            switch (ch, top) {928            case ("⏟", false): emit("\\underbrace"); braced(body)929            case ("⏞", true): emit("\\overbrace"); braced(body)930            case ("←", true): emit("\\overleftarrow"); braced(body)931            case ("→", true): emit("\\vec"); braced(body)932            default:933                emit(top ? "\\overset" : "\\underset")934                emit("{"); emit(MathTables.latexForChar[ch] ?? ch); emit("}")935                braced(body)936            }937        case .matrix(let r): environment("matrix", r)938        case .eqArray(let r): environment("aligned", r)939        case .boxed(let body): emit("\\boxed"); braced(body)940        case .phantom(let body): emit("\\phantom"); braced(body)941        }942    }943}944
Files main
Menu

Theme