Sources/OrgSwift/AST/OrgInlineParser.swift
431 lines · 20142 bytes
1import Foundation
2
3// Inline parsing into `[OrgObject]`.
4//
5// The shipped renderer does inline work by regex-substituting HTML into an escaped string,
6// using placeholder tokens to protect what must not be re-scanned. That works for one output
7// format but bakes HTML into the parse. Here the same constructs become a tree, so `*bold
8// /italic/*` nests properly and every renderer decides its own representation.
9
10extension OrgParser {
11
12 /// Inline objects reduced to their plain text — for alt text, previews, or assertions.
13 public static func plain(_ objects: [OrgObject]) -> String {
14 objects.map { object in
15 switch object {
16 case .text(let text): return text
17 case .verbatim(let text), .code(let text): return text
18 case .bold(let c), .italic(let c), .underline(let c), .strikeThrough(let c), .superscript(let c):
19 return plain(c)
20 case .link(let link):
21 if let description = link.description { return plain(description) }
22 switch link.target {
23 case .external(let value), .file(let value), .id(let value): return value
24 }
25 case .image(let figure): return figure.alt ?? ""
26 case .timestamp(let stamp): return stamp.displayValue
27 case .math(let math): return math.source
28 case .footnoteRef, .lineBreak: return ""
29 }
30 }.joined()
31 }
32
33 /// Parse a run of inline org text into objects.
34 public static func parseInline(_ text: String) -> [OrgObject] {
35 var objects: [OrgObject] = []
36 var plain = ""
37 let chars = Array(text)
38 var i = 0
39 let lastEnd = lastEnvironmentEnd(text)
40 // A closer that is missing once is missing for every later opener of its kind.
41 var missing: Set<String> = []
42 func noteMissing<T>(_ closer: String) -> T? {
43 missing.insert(closer)
44 return nil
45 }
46
47 func flushPlain() {
48 if !plain.isEmpty { objects.append(.text(plain)); plain = "" }
49 }
50
51 while i < chars.count {
52 // Bracket links: [[target]] or [[target][description]]
53 if chars[i] == "[", i + 1 < chars.count, chars[i + 1] == "[",
54 !missing.contains("]]"), let link = scanLink(chars, from: i) ?? noteMissing("]]") {
55 flushPlain()
56 objects.append(link.object)
57 i = link.next
58 continue
59 }
60
61 // LaTeX fragments: $…$, $$…$$, \(…\), \[…\], \begin{…}…\end{…}
62 if chars[i] == "$" || chars[i] == "\\", let math = scanMath(chars, from: i, lastEnd: lastEnd, missing: &missing) {
63 if case .text(let text) = math.object {
64 plain += text
65 } else {
66 flushPlain()
67 objects.append(math.object)
68 }
69 i = math.next
70 continue
71 }
72
73 // Footnote reference: [fn:label] or [fn:label:inline]
74 if chars[i] == "[", let note = scanFootnote(chars, from: i) {
75 flushPlain()
76 objects.append(note.object)
77 i = note.next
78 continue
79 }
80
81 // Timestamps: <2024-01-15 Mon 10:30> or [2024-01-15 Mon]
82 if chars[i] == "<" || chars[i] == "[", let stamp = scanTimestamp(chars, from: i) {
83 flushPlain()
84 objects.append(stamp.object)
85 i = stamp.next
86 continue
87 }
88
89 // Bare URL autolink.
90 if chars[i] == "h", let url = scanBareURL(chars, from: i) {
91 flushPlain()
92 objects.append(url.object)
93 i = url.next
94 continue
95 }
96
97 // Bare email autolink, at a word boundary so `a.b@c.d` is not matched mid-token.
98 if isWordCharacter(chars[i]), i == 0 || !isEmailBoundaryCharacter(chars[i - 1]),
99 let email = scanEmail(chars, from: i) {
100 flushPlain()
101 objects.append(email.object)
102 i = email.next
103 continue
104 }
105
106 // Emphasis: *bold* /italic/ _underline_ +strike+ =verbatim= ~code~
107 if let marker = emphasisMarker(chars[i]), boundaryBefore(chars, i),
108 let span = scanEmphasis(chars, from: i, marker: chars[i]) {
109 flushPlain()
110 switch marker {
111 case .bold: objects.append(.bold(parseInline(span.body)))
112 case .italic: objects.append(.italic(parseInline(span.body)))
113 case .underline: objects.append(.underline(parseInline(span.body)))
114 case .strike: objects.append(.strikeThrough(parseInline(span.body)))
115 case .verbatim: objects.append(.verbatim(span.body))
116 case .code: objects.append(.code(span.body))
117 }
118 i = span.next
119 continue
120 }
121
122 // Superscript: x^2 or x^{group}
123 if chars[i] == "^", i > 0, isWordCharacter(chars[i - 1]),
124 let sup = scanSuperscript(chars, from: i) {
125 flushPlain()
126 objects.append(.superscript(parseInline(sup.body)))
127 i = sup.next
128 continue
129 }
130
131 plain.append(chars[i])
132 i += 1
133 }
134 flushPlain()
135 return objects
136 }
137
138 // MARK: - Scanners
139
140 private enum Emphasis { case bold, italic, underline, strike, verbatim, code }
141
142 private static func emphasisMarker(_ c: Character) -> Emphasis? {
143 switch c {
144 case "*": return .bold
145 case "/": return .italic
146 case "_": return .underline
147 case "+": return .strike
148 case "=": return .verbatim
149 case "~": return .code
150 default: return nil
151 }
152 }
153
154 /// The character before an opening marker. org allows the start of the run,
155 /// whitespace, or one of `-({'"` — the same set orgo uses, which is what the
156 /// conformance corpus is generated from.
157 private static func boundaryBefore(_ chars: [Character], _ i: Int) -> Bool {
158 i == 0 || chars[i - 1].isWhitespace || preChars.contains(chars[i - 1])
159 }
160
161 private static let preChars: Set<Character> = ["-", "(", "{", "'", "\""]
162
163 /// The character after a closing marker, likewise from orgo. Note `[` is in the
164 /// set and `]` is not, which looks backwards until you remember a link's
165 /// description is parsed as its own run, so a `]` never follows a closer.
166 private static let postChars: Set<Character> =
167 ["-", ".", ",", ";", ":", "!", "?", ")", "}", "[", "\"", "'"]
168
169 private static func isWordCharacter(_ c: Character) -> Bool {
170 c.isLetter || c.isNumber
171 }
172
173 private static func scanEmphasis(_ chars: [Character], from start: Int, marker: Character)
174 -> (body: String, next: Int)? {
175 // org's border rule: the body may not begin with whitespace, so an opener followed by
176 // a space is not an opener at all.
177 guard start + 1 < chars.count, !chars[start + 1].isWhitespace else { return nil }
178
179 var j = start + 1
180 var body = ""
181 while j < chars.count {
182 // The body may not end with whitespace either — which is what makes the closer of
183 // `=ssh.mode = "system"=` the last `=` and not the middle one.
184 if chars[j] == marker, let last = body.last, !last.isWhitespace {
185 // The closer must end the run or be followed by space/punctuation.
186 let after = j + 1 < chars.count ? chars[j + 1] : " "
187 if after.isWhitespace || postChars.contains(after) {
188 return (body, j + 1)
189 }
190 }
191 if chars[j] == "\n" { return nil }
192 body.append(chars[j])
193 j += 1
194 }
195 return nil
196 }
197
198 private static func scanLink(_ chars: [Character], from start: Int) -> (object: OrgObject, next: Int)? {
199 var j = start + 2
200 var target = ""
201 while j < chars.count, !(chars[j] == "]" && j + 1 < chars.count && (chars[j + 1] == "]" || chars[j + 1] == "[")) {
202 target.append(chars[j]); j += 1
203 }
204 guard j < chars.count else { return nil }
205
206 var description: String?
207 if chars[j + 1] == "[" {
208 j += 2
209 var text = ""
210 var depth = 0
211 while j < chars.count {
212 if chars[j] == "[" { depth += 1 }
213 if chars[j] == "]" {
214 if depth == 0 { break }
215 depth -= 1
216 }
217 text.append(chars[j]); j += 1
218 }
219 description = text
220 }
221 // Consume the closing ]]
222 while j < chars.count, chars[j] == "]" { j += 1 }
223
224 let object = makeLinkObject(target: target, description: description)
225 return (object, j)
226 }
227
228 private static func makeLinkObject(target rawTarget: String, description: String?) -> OrgObject {
229 let target = rawTarget.hasPrefix("file:") ? String(rawTarget.dropFirst(5)) : rawTarget
230
231 // A description that is itself an image makes the image the link's content — the
232 // build-badge form. It arrives bracket-wrapped from `[[dest][[img]]]`, so unwrap any
233 // balanced brackets before deciding.
234 if let description {
235 var inner = description
236 while inner.hasPrefix("["), inner.hasSuffix("]"), inner.count > 2 {
237 inner = String(inner.dropFirst().dropLast())
238 }
239 let wasWrapped = inner != description
240 let imageSource = inner.hasPrefix("file:") ? String(inner.dropFirst(5)) : inner
241 if isImagePath(imageSource),
242 wasWrapped || inner.hasPrefix("file:") || inner.hasPrefix("http://") || inner.hasPrefix("https://") {
243 return .link(OrgLink(target: linkTarget(target),
244 description: [.image(OrgFigure(source: imageSource))]))
245 }
246 return .link(OrgLink(target: linkTarget(target), description: parseInline(description)))
247 }
248
249 if isImagePath(target) { return .image(OrgFigure(source: target)) }
250 return .link(OrgLink(target: linkTarget(target), description: nil))
251 }
252
253 private static func linkTarget(_ target: String) -> OrgLinkTarget {
254 if target.hasPrefix("id:") { return .id(String(target.dropFirst(3))) }
255 if target.hasPrefix("http://") || target.hasPrefix("https://")
256 || target.hasPrefix("mailto:") || target.hasPrefix("#") {
257 return .external(target)
258 }
259 return .file(target)
260 }
261
262 private static func isImagePath(_ path: String) -> Bool {
263 let lower = path.lowercased()
264 return [".png", ".jpg", ".jpeg", ".gif", ".webp", ".svg", ".bmp", ".heic"]
265 .contains { lower.hasSuffix($0) }
266 }
267
268 private static func scanFootnote(_ chars: [Character], from start: Int) -> (object: OrgObject, next: Int)? {
269 guard chars[start...].starts(with: "[fn:") else { return nil }
270 let rest = String(chars[start...])
271 guard let match = rest.firstMatch(of: /^\[fn:([A-Za-z0-9_-]+)(?::([^\]]*))?\]/) else { return nil }
272 let label = String(match.1)
273 // An inline footnote defines its note where it is used; parse that text as content.
274 let inline = match.2.map { parseInline(String($0)) }
275 let consumed = rest.distance(from: rest.startIndex, to: match.range.upperBound)
276 return (.footnoteRef(label: label, inline: inline), start + consumed)
277 }
278
279 private static func scanTimestamp(_ chars: [Character], from start: Int) -> (object: OrgObject, next: Int)? {
280 let active = chars[start] == "<"
281 let closing: Character = active ? ">" : "]"
282 var j = start + 1
283 var body = ""
284 while j < chars.count, chars[j] != closing {
285 // No timestamp is this long; stopping here keeps a run of brackets linear.
286 if chars[j] == "\n" || body.count > 64 { return nil }
287 body.append(chars[j]); j += 1
288 }
289 guard j < chars.count else { return nil }
290 guard let dateMatch = body.firstMatch(of: /(\d{4}-\d{2}-\d{2})/) else { return nil }
291
292 let date = String(dateMatch.1)
293 var time: String?
294 var endTime: String?
295 if let timeMatch = body.firstMatch(of: /(\d{2}:\d{2})(?:-(\d{2}:\d{2}))?/) {
296 time = String(timeMatch.1)
297 if let end = timeMatch.2 { endTime = String(end) }
298 }
299 var next = j + 1
300
301 // A multi-day range joins two stamps with `--`; org models that as one timestamp
302 // carrying an end, so consume the second stamp here rather than leaving `--` as text.
303 var endDate: String?
304 let opening: Character = active ? "<" : "["
305 if next + 2 < chars.count, chars[next] == "-", chars[next + 1] == "-", chars[next + 2] == opening {
306 var k = next + 3
307 var second = ""
308 while k < chars.count, chars[k] != closing { second.append(chars[k]); k += 1 }
309 if k < chars.count, let endMatch = second.firstMatch(of: /(\d{4}-\d{2}-\d{2})/) {
310 endDate = String(endMatch.1)
311 next = k + 1
312 }
313 }
314
315 return (.timestamp(OrgTimestamp(date: date, time: time, endTime: endTime,
316 endDate: endDate, active: active)), next)
317 }
318
319 private static func scanBareURL(_ chars: [Character], from start: Int) -> (object: OrgObject, next: Int)? {
320 // Matched on the word alone, after a cheap prefix test: copying the rest of the run
321 // at every `h` made long text quadratic.
322 guard chars[start...].starts(with: "http") else { return nil }
323 let rest = String(chars[start..<(chars[start...].firstIndex(where: \.isWhitespace) ?? chars.count)])
324 guard let match = rest.firstMatch(of: /^https?:\/\/[^\s<>()\[\]]+/) else { return nil }
325 var url = String(rest[match.range])
326 while let last = url.last, ".,;:!?".contains(last) { url.removeLast() }
327 return (.link(OrgLink(target: .external(url), description: nil)), start + url.count)
328 }
329
330 /// Characters that keep an email from starting here, mirroring the shipped renderer's
331 /// `(?<![\w.%+\-])` guard.
332 private static func isEmailBoundaryCharacter(_ c: Character) -> Bool {
333 c.isLetter || c.isNumber || c == "_" || c == "." || c == "%" || c == "+" || c == "-"
334 }
335
336 private static func scanEmail(_ chars: [Character], from start: Int) -> (object: OrgObject, next: Int)? {
337 // An address needs its @ after a run of local-part characters; anything else is
338 // refused before the rest of the run is copied.
339 let local = chars[start...].prefix(while: { $0.isASCII && ($0.isLetter || $0.isNumber || "._%+-".contains($0)) })
340 guard !local.isEmpty, start + local.count < chars.count, chars[start + local.count] == "@" else { return nil }
341 let rest = String(chars[start..<(chars[start...].firstIndex(where: \.isWhitespace) ?? chars.count)])
342 guard let match = rest.firstMatch(of: /^[A-Za-z0-9._%+\-]+@[A-Za-z0-9.\-]+\.[A-Za-z]{2,}/) else {
343 return nil
344 }
345 let address = String(rest[match.range])
346 // A trailing character that cannot end an address belongs to the sentence, not the link.
347 guard !address.hasSuffix("."), !address.hasSuffix("-") else { return nil }
348 return (.link(OrgLink(target: .external("mailto:\(address)"),
349 description: [.text(address)])), start + address.count)
350 }
351
352 /// A LaTeX fragment, found as go-org finds one: the first closing pair after the opener,
353 /// anywhere later in the run. A `$…$` whose body starts or ends with a space is consumed
354 /// but stays prose, org's rule for keeping "$5 and $10" a sentence.
355 private static func scanMath(
356 _ chars: [Character], from start: Int, lastEnd: (offset: Int, name: String)?,
357 missing: inout Set<String>
358 ) -> (object: OrgObject, next: Int)? {
359 guard start + 2 < chars.count else { return nil }
360 let opener: String
361 switch (chars[start], chars[start + 1]) {
362 case ("$", "$"): opener = "$$"
363 case ("$", _): opener = "$"
364 case ("\\", "("): opener = #"\("#
365 case ("\\", "["): opener = #"\["#
366 default: return scanEnvironment(chars, from: start, lastEnd: lastEnd)
367 }
368 let closer = ["$$": "$$", "$": "$", #"\("#: #"\)"#, #"\["#: #"\]"#][opener]!
369 let body = start + opener.count
370 guard !missing.contains(closer) else { return nil }
371 guard let close = firstIndex(of: Array(closer), in: chars, from: body) else {
372 missing.insert(closer)
373 return nil
374 }
375 let tex = String(chars[body..<close])
376 let source = opener + tex + closer
377 let next = close + closer.count
378 // The server's border test, which is ASCII space only: a no-break space is TeX.
379 let space: Set<Character> = [" ", "\t", "\n", "\r"]
380 if opener == "$", tex.first.map(space.contains) != false || tex.last.map(space.contains) != false {
381 return (.text(source), next)
382 }
383 let display = opener != "$" && opener != #"\("#
384 return (.math(OrgMath(tex: tex, display: display, source: source)), next)
385 }
386
387 /// `\begin{name}…\end{name}` inline. go-org matches the last `\end{…}` greedily and
388 /// requires its name to be the opener's, then ends the fragment at the first `\end{name}`.
389 private static func scanEnvironment(
390 _ chars: [Character], from start: Int, lastEnd: (offset: Int, name: String)?
391 ) -> (object: OrgObject, next: Int)? {
392 guard let lastEnd, lastEnd.offset > start,
393 Array(chars[start...].prefix(7)) == Array(#"\begin{"#) else { return nil }
394 let name = chars[(start + 7)...].prefix(while: { $0.isASCII && ($0.isLetter || $0.isNumber) || $0 == "_" })
395 guard !name.isEmpty, start + 7 + name.count < chars.count, chars[start + 7 + name.count] == "}",
396 String(name) == lastEnd.name else { return nil }
397 let closer = Array(#"\end{"# + String(name) + "}")
398 guard let close = firstIndex(of: closer, in: chars, from: start + 8 + name.count) else { return nil }
399 let source = String(chars[start..<(close + closer.count)])
400 return (.math(OrgMath(tex: source, display: true, source: source)), close + closer.count)
401 }
402
403 /// Where the run's last `\end{name}` starts, in characters, and its name.
404 private static func lastEnvironmentEnd(_ text: String) -> (offset: Int, name: String)? {
405 guard text.contains(#"\end{"#), let last = text.matches(of: /\\end\{(\w+)\}/).last else { return nil }
406 return (text.distance(from: text.startIndex, to: last.range.lowerBound), String(last.1))
407 }
408
409 private static func firstIndex(of needle: [Character], in chars: [Character], from start: Int) -> Int? {
410 guard !needle.isEmpty, chars.count >= needle.count, start <= chars.count - needle.count else { return nil }
411 for i in start...(chars.count - needle.count) where chars[i] == needle[0] {
412 if (1..<needle.count).allSatisfy({ chars[i + $0] == needle[$0] }) { return i }
413 }
414 return nil
415 }
416
417 private static func scanSuperscript(_ chars: [Character], from start: Int) -> (body: String, next: Int)? {
418 var j = start + 1
419 guard j < chars.count else { return nil }
420 if chars[j] == "{" {
421 j += 1
422 var body = ""
423 while j < chars.count, chars[j] != "}" { body.append(chars[j]); j += 1 }
424 guard j < chars.count else { return nil }
425 return (body, j + 1)
426 }
427 var body = ""
428 while j < chars.count, isWordCharacter(chars[j]) { body.append(chars[j]); j += 1 }
429 return body.isEmpty ? nil : (body, j)
430 }
431}