Repository Public
1// ORIX Docs2// File: Packages/ORIXDocsKit/Sources/DocFormats/MarkdownInline.swift3// Description: Markdown inline parser: emphasis (CommonMark delimiter algorithm), code spans, links, images, autolinks, footnote4// references, pandoc citations, LaTeX math, strikethrough, sub/superscript, hard breaks, entities. Produces model runs.5//6// Author: Simon-Pierre Boucher7// Contact: contact@spboucher.ai8import Foundation9import DocModel10import DocContainer111213final class MarkdownInlineParser {14 enum Sty: Equatable { case bold, italic, strike, underline, sub, sup, mark, link(String) }1516 private struct Tok {17 enum Kind { case text, code, delim, bracket, open, close, lineBreak, object }18 var kind: Kind19 var text = ""20 var ch: Unicode.Scalar = " "21 var count = 0, orig = 022 var canOpen = false, canClose = false23 var opens: [Sty] = [], closes: [Sty] = []24 var sty: Sty?25 var inline: Inline?26 var image = false, active = true27 var source = 028 }2930 private unowned let host: MarkdownParser31 private let s: [Unicode.Scalar]32 private var i = 033 private var toks: [Tok] = []34 private var buf = String.UnicodeScalarView()35 private var brackets: [Int] = []36 /// Bracket openers below this stack position can no longer become links (links do not nest).37 private var inactiveBelow = 038 private let hasCitationMarker: Bool3940 init(_ text: String, host: MarkdownParser) {41 self.host = host42 s = Array(text.unicodeScalars)43 hasCitationMarker = s.contains("@")44 }4546 // MARK: Character classes4748 private func isWhitespace(_ u: Unicode.Scalar?) -> Bool { u.map { $0.properties.isWhitespace } ?? true }49 private func isPunctuation(_ u: Unicode.Scalar?) -> Bool {50 guard let u else { return false }51 switch u.properties.generalCategory {52 case .connectorPunctuation, .dashPunctuation, .openPunctuation, .closePunctuation, .initialPunctuation, .finalPunctuation,53 .otherPunctuation, .mathSymbol, .currencySymbol, .modifierSymbol, .otherSymbol: return true54 default: return false55 }56 }57 private func isASCIIPunctuation(_ u: Unicode.Scalar) -> Bool {58 let v = u.value59 return (v >= 33 && v <= 47) || (v >= 58 && v <= 64) || (v >= 91 && v <= 96) || (v >= 123 && v <= 126)60 }61 private func at(_ k: Int) -> Unicode.Scalar? { k >= 0 && k < s.count ? s[k] : nil }62 private func string(_ range: Range<Int>) -> String { String(String.UnicodeScalarView(s[range])) }63 private func flush() { if !buf.isEmpty { toks.append(Tok(kind: .text, text: String(buf))); buf = String.UnicodeScalarView() } }64 private func push(_ t: Tok) { flush(); toks.append(t) }65 private func find(_ u: Unicode.Scalar, from start: Int, limit: Int = 100_000) -> Int? {66 var k = start67 let end = min(s.count, start + limit)68 while k < end { if s[k] == "\\" { k += 2; continue }; if s[k] == u { return k }; k += 1 }69 return nil70 }7172 // MARK: Scanning7374 func parse() -> [Run] {75 while i < s.count {76 let c = s[i]77 switch c {78 case "\\": backslash()79 case "`": codeSpan()80 case "$": math()81 case "*", "_": delimiterRun(c)82 case "~": tilde()83 case "^": superscript()84 case "[": openBracket()85 case "!":86 if at(i + 1) == "[" {87 var t = Tok(kind: .bracket); t.image = true; t.source = i + 288 push(t); brackets.append(toks.count - 1); i += 289 } else { buf.append(c); i += 1 }90 case "]": closeBracket()91 case "<": angle()92 case "&":93 if let (scalar, length) = HTMLEntities.decode(s, at: i) { buf.append(scalar == "\u{FFFC}" ? "\u{FFFD}" : scalar); i += length } else { buf.append(c); i += 1 }94 case "\n": newline()95 case "h":96 if !bareURL() { buf.append(c); i += 1 }97 default: buf.append(c); i += 198 }99 }100 flush()101 processEmphasis(from: 0)102 return flatten()103 }104105 private func backslash() {106 guard let n = at(i + 1) else { buf.append("\\"); i += 1; return }107 if n == "\n" { push(Tok(kind: .lineBreak)); i += 2; skipLeadingSpaces(); return }108 if isASCIIPunctuation(n) { buf.append(n); i += 2 } else { buf.append("\\"); i += 1 }109 }110111 private func skipLeadingSpaces() { while i < s.count, s[i] == " " || s[i] == "\t" { i += 1 } }112113 private func newline() {114 var spaces = 0115 while let last = buf.last, last == " " || last == "\t" { buf.removeLast(); spaces += 1 }116 if spaces >= 2 { push(Tok(kind: .lineBreak)) } else { buf.append(" ") }117 i += 1118 skipLeadingSpaces()119 }120121 private func codeSpan() {122 var n = 0123 while at(i + n) == "`" { n += 1 }124 var k = i + n125 while k < s.count {126 if s[k] == "`" {127 var m = 0128 while at(k + m) == "`" { m += 1 }129 if m == n {130 var content = string((i + n)..<k).replacingOccurrences(of: "\n", with: " ")131 if content.hasPrefix(" "), content.hasSuffix(" "), content.contains(where: { $0 != " " }) { content = String(content.dropFirst().dropLast()) }132 push(Tok(kind: .code, text: content))133 i = k + m134 return135 }136 k += m137 } else { k += 1 }138 }139 for _ in 0..<n { buf.append("`") }140 i += n141 }142143 private func math() {144 if at(i + 1) == "$" {145 var k = i + 2146 while k + 1 < s.count, !(s[k] == "$" && s[k + 1] == "$") { k += s[k] == "\\" ? 2 : 1 }147 if k + 1 < s.count, k > i + 2 {148 let latex = string((i + 2)..<k).trimmingCharacters(in: .whitespacesAndNewlines)149 if !latex.isEmpty {150 var t = Tok(kind: .object); t.inline = .equation(Equation(latex: latex, display: true))151 push(t); i = k + 2; return152 }153 }154 buf.append("$"); buf.append("$"); i += 2155 return156 }157 // pandoc rule: the opening $ has a non-space to its right, the closing $ a non-space to its left and no digit after it.158 if let n = at(i + 1), !isWhitespace(n) {159 var k = i + 1160 let end = min(s.count, i + 4000)161 while k < end {162 if s[k] == "\\" { k += 2; continue }163 if s[k] == "\n", at(k + 1) == "\n" { break }164 if s[k] == "$" {165 let after = at(k + 1)166 let digitAfter = after.map { $0.value >= 48 && $0.value <= 57 } ?? false167 if !isWhitespace(s[k - 1]), !digitAfter, k > i + 1 {168 var t = Tok(kind: .object); t.inline = .equation(Equation(latex: string((i + 1)..<k).replacingOccurrences(of: "\n", with: " "), display: false))169 push(t); i = k + 1; return170 }171 break172 }173 k += 1174 }175 }176 buf.append("$"); i += 1177 }178179 private func delimiterRun(_ c: Unicode.Scalar) {180 var n = 0181 while at(i + n) == c { n += 1 }182 let before = at(i - 1), after = at(i + n)183 let left = !isWhitespace(after) && (!isPunctuation(after) || isWhitespace(before) || isPunctuation(before))184 let right = !isWhitespace(before) && (!isPunctuation(before) || isWhitespace(after) || isPunctuation(after))185 var t = Tok(kind: .delim)186 t.ch = c; t.count = n; t.orig = n187 if c == "_" {188 t.canOpen = left && (!right || isPunctuation(before))189 t.canClose = right && (!left || isPunctuation(after))190 } else { t.canOpen = left; t.canClose = right }191 push(t)192 i += n193 }194195 private func tilde() {196 var n = 0197 while at(i + n) == "~" { n += 1 }198 if n == 2 { delimiterRun("~"); return }199 if n == 1, let t = shortSpan(delimiter: "~", style: .sub) { push(t.0); push(t.1); push(t.2); return }200 for _ in 0..<n { buf.append("~") }201 i += n202 }203204 private func superscript() {205 if let t = shortSpan(delimiter: "^", style: .sup) { push(t.0); push(t.1); push(t.2); return }206 buf.append("^"); i += 1207 }208209 /// pandoc sub/superscript: `~text~` / `^text^` with no white space inside.210 private func shortSpan(delimiter: Unicode.Scalar, style: Sty) -> (Tok, Tok, Tok)? {211 var k = i + 1212 var content = String.UnicodeScalarView()213 while k < s.count, k - i < 80 {214 let u = s[k]215 if u == "\\", let n = at(k + 1) { content.append(n); k += 2; continue }216 if u == delimiter { break }217 if isWhitespace(u) || u == "[" || u == "]" { return nil }218 content.append(u); k += 1219 }220 guard k < s.count, s[k] == delimiter, !content.isEmpty else { return nil }221 i = k + 1222 var open = Tok(kind: .open); open.sty = style223 var close = Tok(kind: .close); close.sty = style224 return (open, Tok(kind: .text, text: String(content)), close)225 }226227 private func bareURL() -> Bool {228 guard at(i + 1) == "t", at(i + 2) == "t", at(i + 3) == "p" else { return false }229 var k = i + 4230 if at(k) == "s" { k += 1 }231 guard at(k) == ":", at(k + 1) == "/", at(k + 2) == "/" else { return false }232 if let b = at(i - 1), b.properties.isAlphabetic || (b.value >= 48 && b.value <= 57) { return false }233 k += 3234 let start = k235 while k < s.count, !isWhitespace(s[k]), s[k] != "<", s[k] != ">", s[k] != "]", s[k] != "[", s[k] != "\\" , s[k] != "*", s[k] != "`" { k += 1 }236 while k > start, let last = at(k - 1), ".,;:!?'\"".unicodeScalars.contains(last) || (last == ")" && !s[start..<k].contains("(")) { k -= 1 }237 guard k > start else { return false }238 let url = string(i..<k)239 emitLink(url: url, text: url)240 i = k241 return true242 }243244 private func emitLink(url: String, text: String) {245 guard let safe = LinkPolicy.sanitize(url) else { buf.append(contentsOf: text.unicodeScalars); return }246 var open = Tok(kind: .open); open.sty = .link(safe)247 var close = Tok(kind: .close); close.sty = .link(safe)248 push(open); push(Tok(kind: .text, text: text)); push(close)249 }250251 private func angle() {252 guard let end = find(">", from: i + 1, limit: 2000) else { buf.append("<"); i += 1; return }253 let inner = string((i + 1)..<end)254 let lower = inner.lowercased()255 func toggle(_ sty: Sty, open: Bool) { var t = Tok(kind: open ? .open : .close); t.sty = sty; push(t) }256 if !inner.contains(" "), !inner.contains("\n"), !inner.contains("<") {257 if let colon = inner.firstIndex(of: ":"), inner[..<colon].count >= 2, inner[..<colon].allSatisfy({ $0.isASCII && ($0.isLetter || $0.isNumber || "+.-".contains($0)) }), inner.first!.isLetter {258 emitLink(url: inner, text: inner); i = end + 1; return259 }260 if inner.contains("@"), !inner.hasPrefix("@"), !inner.hasSuffix("@"), !inner.contains("/"), inner.split(separator: "@").count == 2, inner.contains(".") {261 emitLink(url: "mailto:" + inner, text: inner); i = end + 1; return262 }263 }264 switch lower {265 case "br", "br/", "br /": push(Tok(kind: .lineBreak)); i = end + 1; return266 case "u": toggle(.underline, open: true); i = end + 1; return267 case "/u": toggle(.underline, open: false); i = end + 1; return268 case "sub": toggle(.sub, open: true); i = end + 1; return269 case "/sub": toggle(.sub, open: false); i = end + 1; return270 case "sup": toggle(.sup, open: true); i = end + 1; return271 case "/sup": toggle(.sup, open: false); i = end + 1; return272 case "mark": toggle(.mark, open: true); i = end + 1; return273 case "/mark": toggle(.mark, open: false); i = end + 1; return274 default: break275 }276 if lower.hasPrefix("!--") {277 // HTML comment: dropped. The empty comment is the separator our own exporter writes.278 var k = i + 4279 while k < s.count, !(s[k] == "-" && at(k + 1) == "-" && at(k + 2) == ">") { k += 1 }280 let body = string(min(s.count, i + 4)..<min(s.count, k)).trimmingCharacters(in: .whitespaces)281 if !body.isEmpty { host.warnings.add(.dropped, "HTML comments", "HTML comments in the Markdown source were dropped.") }282 i = min(s.count, k + 3)283 return284 }285 if lower.hasPrefix("a "), let name = attribute("id", in: inner) ?? attribute("name", in: inner), attribute("href", in: inner) == nil {286 // <a id="x"></a>: a bookmark.287 var k = end + 1288 if string(k..<min(s.count, k + 4)).lowercased() == "</a>" { k += 4 }289 var t = Tok(kind: .object); t.inline = .bookmark(name)290 push(t); i = k291 return292 }293 if let f = inner.unicodeScalars.first, f.properties.isAlphabetic || f == "/" {294 host.warnings.add(.approximated, "Raw HTML", "Inline HTML other than <br>, <u>, <sub>, <sup>, <mark> and anchors is kept as literal text.")295 }296 buf.append("<"); i += 1297 }298299 private func attribute(_ name: String, in tag: String) -> String? {300 var tokenizer = HTMLTokenizer("<" + tag + ">")301 if case .start(_, let attributes, _)? = tokenizer.next() { return attributes[name].flatMap { $0.isEmpty ? nil : $0 } }302 return nil303 }304305 // MARK: Brackets: links, images, footnotes, citations306307 private func openBracket() {308 if at(i + 1) == "^", let end = find("]", from: i + 2, limit: 200) {309 let label = string((i + 2)..<end)310 if !label.isEmpty, !label.contains(where: { $0.isWhitespace }), host.noteLabels.contains(label) {311 var t = Tok(kind: .object); t.inline = .note(NoteRef(kind: .footnote, id: pendingNotePrefix + label))312 push(t); i = end + 1313 return314 }315 }316 if hasCitationMarker, let end = find("]", from: i + 1, limit: 2000), s[(i + 1)..<end].contains("@") {317 let inner = string((i + 1)..<end)318 let next = at(end + 1)319 if inner.contains("@"), !inner.contains("["), next != "(", next != "[", let citation = CitationSyntax.parse(inner) {320 var t = Tok(kind: .object); t.inline = .citation(citation)321 push(t); i = end + 1322 return323 }324 }325 var t = Tok(kind: .bracket); t.source = i + 1326 push(t); brackets.append(toks.count - 1); i += 1327 }328329 private func closeBracket() {330 flush()331 guard let o = brackets.popLast() else { buf.append("]"); i += 1; return }332 let wasInactive = !toks[o].image && brackets.count < inactiveBelow333 inactiveBelow = min(inactiveBelow, brackets.count)334 guard toks[o].active, !wasInactive else { literalBracket(o); return }335 var target: String?336 var after = i + 1337 if at(i + 1) == "(", let (url, end) = inlineDestination(from: i + 2) {338 target = url; after = end339 } else if !host.references.isEmpty, i - toks[o].source <= 999 {340 // Reference links: only looked up when the document defines references, and labels are at most 999 characters.341 var label = string(toks[o].source..<i)342 if at(i + 1) == "[", let end = find("]", from: i + 2, limit: 1000) {343 let explicit = string((i + 2)..<end)344 if !explicit.isEmpty { label = explicit }345 if let ref = host.references[MarkdownParser.normalizeLabel(label)] { target = ref; after = end + 1 }346 } else if let ref = host.references[MarkdownParser.normalizeLabel(label)] { target = ref }347 }348 guard let url = target else { literalBracket(o); return }349 i = after350 processEmphasis(from: o + 1)351 if toks[o].image {352 let alt = toks[(o + 1)...].reduce(into: "") { acc, t in if t.kind == .text || t.kind == .code { acc += t.text } else if t.kind == .delim { acc += String(repeating: String(t.ch), count: t.count) } }353 toks.removeSubrange((o + 1)...)354 brackets.removeAll { $0 > o }355 if let image = host.images.resolve(src: url, alt: alt, warnings: &host.warnings) {356 toks[o] = Tok(kind: .object); toks[o].inline = .image(image)357 } else {358 toks[o] = Tok(kind: .text, text: alt)359 }360 return361 }362 for k in (o + 1)..<toks.count where toks[k].kind == .delim { toks[k].canOpen = false; toks[k].canClose = false }363 guard let safe = LinkPolicy.sanitize(url) else {364 host.warnings.add(.dropped, "Active content", "A link with a script or data scheme was removed; its text was kept.")365 toks[o] = Tok(kind: .text, text: "")366 return367 }368 toks[o] = Tok(kind: .open); toks[o].sty = .link(safe)369 var close = Tok(kind: .close); close.sty = .link(safe)370 toks.append(close)371 // Links do not nest: earlier link openers can no longer match.372 inactiveBelow = brackets.count373 }374375 private func literalBracket(_ o: Int) {376 toks[o] = Tok(kind: .text, text: toks[o].image ? "![" : "[")377 buf.append("]"); i += 1378 }379380 /// Parses `dest "title")` starting after the opening parenthesis. Returns the destination and the index after `)`.381 private func inlineDestination(from start: Int) -> (String, Int)? {382 var k = start383 while let u = at(k), isWhitespace(u) { k += 1 }384 var dest = String.UnicodeScalarView()385 if at(k) == "<" {386 k += 1387 while let u = at(k), u != ">", u != "\n" { if u == "\\", let n = at(k + 1) { dest.append(n); k += 2 } else { dest.append(u); k += 1 } }388 guard at(k) == ">" else { return nil }389 k += 1390 } else {391 var depth = 0392 while let u = at(k), !isWhitespace(u) {393 if u == "\\", let n = at(k + 1), isASCIIPunctuation(n) { dest.append(n); k += 2; continue }394 if u == "(" { depth += 1; if depth > 32 { return nil } } else if u == ")" { if depth == 0 { break }; depth -= 1 }395 dest.append(u); k += 1396 if k - start > 20_000_000 { return nil }397 }398 }399 while let u = at(k), isWhitespace(u) { k += 1 }400 if let q = at(k), q == "\"" || q == "'" || q == "(" {401 let closer: Unicode.Scalar = q == "(" ? ")" : q402 guard let end = find(closer, from: k + 1, limit: 4000) else { return nil }403 k = end + 1404 while let u = at(k), isWhitespace(u) { k += 1 }405 }406 guard at(k) == ")" else { return nil }407 return (HTMLEntities.decodeAll(String(dest)), k + 1)408 }409410 // MARK: Emphasis411412 private func processEmphasis(from lo: Int) {413 flush()414 let ds = (lo..<toks.count).filter { toks[$0].kind == .delim && (toks[$0].canOpen || toks[$0].canClose) }415 guard !ds.isEmpty else { return }416 var removed = Array(repeating: false, count: ds.count)417 var bottoms: [String: Int] = [:]418 var c = 0419 while c < ds.count {420 let closer = toks[ds[c]]421 guard !removed[c], closer.canClose, closer.count > 0 else { c += 1; continue }422 let key = "\(closer.ch)\(closer.canOpen)\(closer.orig % 3)"423 let bottom = bottoms[key] ?? -1424 var o = c - 1425 var found = false426 while o > bottom {427 if !removed[o] {428 let opener = toks[ds[o]]429 if opener.ch == closer.ch, opener.canOpen, opener.count > 0 {430 let odd = closer.ch != "~" && (closer.canOpen || opener.canClose) && (opener.orig + closer.orig) % 3 == 0431 && !(opener.orig % 3 == 0 && closer.orig % 3 == 0)432 if !odd { found = true; break }433 }434 }435 o -= 1436 }437 if found {438 let both = toks[ds[o]].count >= 2 && toks[ds[c]].count >= 2439 let use = closer.ch == "~" ? 2 : (both ? 2 : 1)440 let sty: Sty = closer.ch == "~" ? .strike : (use == 2 ? .bold : .italic)441 toks[ds[o]].opens.insert(sty, at: 0); toks[ds[o]].count -= use442 toks[ds[c]].closes.append(sty); toks[ds[c]].count -= use443 if o + 1 < c { for k in (o + 1)..<c { removed[k] = true } }444 if toks[ds[o]].count <= 0 { removed[o] = true }445 if toks[ds[c]].count <= 0 { removed[c] = true; c += 1 }446 } else {447 bottoms[key] = c - 1448 if !closer.canOpen { removed[c] = true }449 c += 1450 }451 }452 for d in ds { toks[d].canOpen = false; toks[d].canClose = false }453 }454455 // MARK: Runs456457 private func flatten() -> [Run] {458 var runs: [Run] = []459 var stack: [Sty] = []460 func props() -> (CharProps, String?) {461 var p = CharProps.none462 var style: String?463 for sty in stack {464 switch sty {465 case .bold: p.bold = true466 case .italic: p.italic = true467 case .strike: p.strikethrough = true468 case .underline: p.underline = true469 case .sub: p.vertical = .subscript470 case .sup: p.vertical = .superscript471 case .mark: p.highlight = RGBA(hex: 0xFFF59D)472 case .link(let url): p.link = url; style = StyleID.hyperlink473 }474 }475 return (p, style)476 }477 func text(_ t: String) {478 guard !t.isEmpty else { return }479 let (p, style) = props()480 runs.append(Run(t, props: p, charStyle: style))481 }482 func close(_ sty: Sty) { if let k = stack.lastIndex(of: sty) { stack.remove(at: k) } }483 for t in toks {484 switch t.kind {485 case .text: text(t.text)486 case .code:487 let (p, _) = props()488 runs.append(Run(t.text, props: p, charStyle: StyleID.inlineCode))489 case .delim:490 t.closes.forEach(close)491 if t.count > 0 { text(String(repeating: String(t.ch), count: t.count)) }492 stack.append(contentsOf: t.opens)493 case .bracket: text(t.image ? "![" : "[")494 case .open: if let sty = t.sty { stack.append(sty) }495 case .close: if let sty = t.sty { close(sty) }496 case .lineBreak: text(lineSeparatorCharacter)497 case .object: if let inline = t.inline { runs.append(Run(inline: inline)) }498 }499 }500 return runs501 }502}503