Sources/OrgSwift/AST/OrgParser.swift
442 lines · 19010 bytes
1import Foundation
2
3/// Parses org source into an ``OrgDocument``.
4///
5/// This is the prototype of the AST split: parsing happens once, here, and renderers walk the
6/// result. It is deliberately a separate pipeline from the shipped ``OrgRenderer`` (which goes
7/// straight from source to an HTML string) so the two can be compared before anything migrates.
8public enum OrgParser {
9
10 public static func parse(_ source: String) -> OrgDocument {
11 var document = OrgDocument()
12 let lines = source
13 .replacingOccurrences(of: "\r\n", with: "\n")
14 .replacingOccurrences(of: "\r", with: "\n")
15 .components(separatedBy: "\n")
16 var index = 0
17 let latexEnds = latexEndLines(lines)
18 var pendingCaption: String?
19 var pendingName: String?
20 var pendingAttrs: [(key: String, value: String)] = []
21
22 func flushPending() {
23 pendingCaption = nil
24 pendingName = nil
25 pendingAttrs = []
26 }
27
28 /// Append a block, wrapping it in `.captioned` when an affiliated `#+CAPTION:` or
29 /// `#+NAME:` precedes it — org's exporter turns that pairing into a `<figure>`.
30 func append(_ element: OrgElement) {
31 if pendingCaption != nil || pendingName != nil {
32 document.elements.append(.captioned(
33 name: pendingName,
34 caption: pendingCaption.map(parseInline),
35 content: element
36 ))
37 } else {
38 document.elements.append(element)
39 }
40 }
41
42 while index < lines.count {
43 let line = lines[index]
44 let trimmed = line.trimmingCharacters(in: .whitespaces)
45
46 if trimmed.isEmpty { index += 1; continue }
47
48 // Comments.
49 if trimmed == "#" || trimmed.hasPrefix("# ") { index += 1; continue }
50
51 // Property drawers are heading metadata; org's exporter drops them.
52 if trimmed == ":PROPERTIES:" {
53 index += 1
54 while index < lines.count,
55 lines[index].trimmingCharacters(in: .whitespaces) != ":END:" {
56 index += 1
57 }
58 if index < lines.count { index += 1 }
59 continue
60 }
61
62 // Affiliated keywords and document metadata.
63 if let directive = orgKeywordDirective(in: trimmed) {
64 switch directive.keyword {
65 case "caption": pendingCaption = directive.value
66 case "name": pendingName = directive.value
67 case "attr_html": pendingAttrs = parseAttributes(directive.value)
68 default: document.keywords.append((directive.keyword, directive.value))
69 }
70 index += 1
71 continue
72 }
73
74 // Blocks: #+begin_… / #+end_…
75 if trimmed.lowercased().hasPrefix("#+begin_") {
76 let (element, next) = parseBlock(lines, from: index)
77 if let element { append(element) }
78 index = next
79 flushPending()
80 continue
81 }
82
83 // Heading.
84 if let match = trimmed.firstMatch(of: /^(\*{1,6})\s+(.+)$/) {
85 document.elements.append(.heading(parseHeading(stars: match.1.count, rest: String(match.2))))
86 index += 1
87 flushPending()
88 continue
89 }
90
91 // Horizontal rule.
92 if isOrgHorizontalRule(trimmed) {
93 document.elements.append(.horizontalRule)
94 index += 1
95 flushPending()
96 continue
97 }
98
99 // Footnote definition.
100 if let def = orgFootnoteDefinition(in: trimmed) {
101 document.elements.append(.footnoteDefinition(label: def.label, content: parseInline(def.text)))
102 index += 1
103 flushPending()
104 continue
105 }
106
107 // A standalone image link, promoted to a figure by an affiliated caption/attrs.
108 if let path = standaloneOrgImage(in: trimmed) {
109 document.elements.append(.figure(OrgFigure(
110 source: path,
111 caption: pendingCaption.map(parseInline),
112 attributes: pendingAttrs
113 )))
114 index += 1
115 flushPending()
116 continue
117 }
118
119 // Table.
120 if isTableLine(trimmed) {
121 let (table, next) = parseTable(lines, from: index)
122 append(.table(table))
123 index = next
124 flushPending()
125 continue
126 }
127
128 // List.
129 if isListMarkerLine(trimmed), !isIndentedContinuationLine(line) {
130 let (list, next) = parseList(lines, from: index)
131 document.elements.append(.list(list))
132 index = next
133 flushPending()
134 continue
135 }
136
137 // A LaTeX block: \begin{name} alone on its line, through the matching \end{name}.
138 if let (raw, next) = parseLatexBlock(lines, from: index, ends: latexEnds) {
139 append(.latexBlock(raw))
140 index = next
141 flushPending()
142 continue
143 }
144
145 // Paragraph: consume until a blank line or a line that starts another construct.
146 var paragraph: [String] = []
147 while index < lines.count {
148 let candidate = lines[index]
149 let candidateTrimmed = candidate.trimmingCharacters(in: .whitespaces)
150 // The first line is always taken: nothing above claimed it, and
151 // leaving it would parse the same line forever.
152 if !paragraph.isEmpty,
153 candidateTrimmed.isEmpty || startsNewConstruct(candidateTrimmed, raw: candidate)
154 || latexEnd(candidateTrimmed) != nil
155 || latexBlockEnd(lines, from: index, ends: latexEnds) != nil { break }
156 paragraph.append(candidateTrimmed)
157 index += 1
158 }
159 if !paragraph.isEmpty {
160 document.elements.append(.paragraph(parseInline(paragraph.joined(separator: " "))))
161 }
162 flushPending()
163 }
164
165 return document
166 }
167
168 /// Would this line begin a construct other than the paragraph currently being consumed?
169 private static func startsNewConstruct(_ trimmed: String, raw: String) -> Bool {
170 // A keyword or a comment; `#12 fixed this` is prose.
171 if trimmed.hasPrefix("#+") || trimmed == "#" || trimmed.hasPrefix("# ") { return true }
172 if trimmed.firstMatch(of: /^\*{1,6}\s+/) != nil { return true }
173 if isOrgHorizontalRule(trimmed) { return true }
174 if isTableLine(trimmed) { return true }
175 if orgFootnoteDefinition(in: trimmed) != nil { return true }
176 if isListMarkerLine(trimmed), !isIndentedContinuationLine(raw) { return true }
177 return false
178 }
179
180 // MARK: - LaTeX block
181
182 /// The environment a `\begin{name}` line opens, as go-org's lexer reads it (any case).
183 private static func latexBegin(_ trimmed: String) -> String? {
184 guard trimmed.hasPrefix("\\") else { return nil }
185 return trimmed.firstMatch(of: /^\\begin\{([^}]+)\}$/.ignoresCase()).map { String($0.1).lowercased() }
186 }
187
188 /// The environment a `\end{name}` line closes. Like go-org's, it ends a paragraph
189 /// whether or not a block is open.
190 private static func latexEnd(_ trimmed: String) -> String? {
191 guard trimmed.hasPrefix("\\") else { return nil }
192 return trimmed.firstMatch(of: /^\\end\{([^}]+)\}$/.ignoresCase()).map { String($0.1).lowercased() }
193 }
194
195 /// Each environment's `\end{name}` lines, in order, found in one pass so an opener
196 /// looks its closer up rather than scanning to the end of the document.
197 private static func latexEndLines(_ lines: [String]) -> [String: [Int]] {
198 var ends: [String: [Int]] = [:]
199 for (index, line) in lines.enumerated() {
200 if let name = latexEnd(line.trimmingCharacters(in: .whitespaces)) { ends[name, default: []].append(index) }
201 }
202 return ends
203 }
204
205 /// The line closing the block a `\begin{name}` line at `start` opens, if one follows.
206 private static func latexBlockEnd(_ lines: [String], from start: Int, ends: [String: [Int]]) -> Int? {
207 guard let name = latexBegin(lines[start].trimmingCharacters(in: .whitespaces)),
208 let candidates = ends[name] else { return nil }
209 var low = 0, high = candidates.count
210 while low < high {
211 let mid = (low + high) / 2
212 if candidates[mid] <= start { low = mid + 1 } else { high = mid }
213 }
214 return low < candidates.count ? candidates[low] : nil
215 }
216
217 private static func parseLatexBlock(
218 _ lines: [String], from start: Int, ends: [String: [Int]]
219 ) -> (String, Int)? {
220 guard let end = latexBlockEnd(lines, from: start, ends: ends) else { return nil }
221 let indent = leadingWidth(lines[start])
222 let raw = lines[start...end].map { dropLeading($0, min(indent, leadingWidth($0))) }
223 return (raw.joined(separator: "\n"), end + 1)
224 }
225
226 // MARK: - Heading
227
228 private static func parseHeading(stars: Int, rest: String) -> OrgHeading {
229 var body = rest
230 var todo: String?
231 var priority: Character?
232
233 for keyword in ["TODO", "DONE"] where body == keyword || body.hasPrefix("\(keyword) ") {
234 todo = keyword
235 body = String(body.dropFirst(keyword.count)).trimmingCharacters(in: .whitespaces)
236 break
237 }
238 if let match = body.firstMatch(of: /^\[#([A-Z])\]\s*/) {
239 priority = Character(String(match.1))
240 body = String(body[match.range.upperBound...])
241 }
242 let (title, tags) = splitHeadingTags(body)
243 return OrgHeading(level: stars, todo: todo, priority: priority,
244 title: parseInline(title), tags: tags)
245 }
246
247 // MARK: - Blocks
248
249 private static func parseBlock(_ lines: [String], from start: Int) -> (OrgElement?, Int) {
250 let opener = lines[start].trimmingCharacters(in: .whitespaces)
251 let lower = opener.lowercased()
252 let name = String(lower.dropFirst("#+begin_".count)).split(separator: " ").first.map(String.init) ?? ""
253 let argument = opener
254 .split(separator: " ", maxSplits: 1, omittingEmptySubsequences: true)
255 .dropFirst().first.map { String($0).trimmingCharacters(in: .whitespaces) }
256
257 var body: [String] = []
258 var index = start + 1
259 while index < lines.count {
260 let trimmed = lines[index].trimmingCharacters(in: .whitespaces).lowercased()
261 if trimmed == "#+end_\(name)" { index += 1; break }
262 body.append(lines[index])
263 index += 1
264 }
265
266 switch name {
267 case "src":
268 return (.srcBlock(language: argument?.isEmpty == false ? argument : nil,
269 code: body.joined(separator: "\n")), index)
270 case "example":
271 return (.exampleBlock(body.joined(separator: "\n")), index)
272 case "quote":
273 return (.quoteBlock(parse(body.joined(separator: "\n")).elements), index)
274 case "center":
275 return (.centerBlock(parse(body.joined(separator: "\n")).elements), index)
276 case "verse":
277 return (.verseBlock(body.map(parseInline)), index)
278 case "export":
279 return (.exportBlock(backend: (argument ?? "").lowercased(),
280 raw: body.joined(separator: "\n")), index)
281 default:
282 return (.specialBlock(name: name, content: parse(body.joined(separator: "\n")).elements), index)
283 }
284 }
285
286 // MARK: - Table
287
288 private static func parseTable(_ lines: [String], from start: Int) -> (OrgTable, Int) {
289 var rows: [OrgTableRow] = []
290 var alignments: [OrgAlignment?] = []
291 var index = start
292
293 while index < lines.count {
294 let trimmed = lines[index].trimmingCharacters(in: .whitespaces)
295 guard isTableLine(trimmed) else { break }
296
297 // A separator row's columns are divided by `+`, not `|`, so it needs its own
298 // split — `|:---+---:|` is two columns, which splitting on `|` would miss.
299 let separatorCells = parseOrgTableSeparatorRow(trimmed)
300 let cells = separatorCells.allSatisfy(isTableSeparatorCell)
301 ? separatorCells : parseTableRow(trimmed)
302 if !cells.isEmpty, cells.allSatisfy(isTableSeparatorCell) {
303 rows.append(.rule)
304 let parsed = cells.map { cell -> OrgAlignment? in
305 switch tableAlignment(for: cell) {
306 case "left": return .left
307 case "center": return .center
308 case "right": return .right
309 default: return nil
310 }
311 }
312 if alignments.isEmpty || alignments.allSatisfy({ $0 == nil }) { alignments = parsed }
313 } else {
314 rows.append(.cells(cells.map(parseInline)))
315 }
316 index += 1
317 }
318 return (OrgTable(rows: rows, alignments: alignments), index)
319 }
320
321 // MARK: - List
322
323 private static func parseList(_ lines: [String], from start: Int) -> (OrgList, Int) {
324 var block: [String] = []
325 var index = start
326 var pendingBlanks: [String] = []
327 // A top-level marker of the other kind starts a *separate* list: an ordered list
328 // followed by a bullet list is two lists, not one with mixed items.
329 let startsOrdered = orderedListItem(in: lines[start].trimmingCharacters(in: .whitespaces)) != nil
330
331 while index < lines.count {
332 let line = lines[index]
333 let trimmed = line.trimmingCharacters(in: .whitespaces)
334 if trimmed.isEmpty {
335 pendingBlanks.append(line); index += 1; continue
336 }
337 if isListMarkerLine(trimmed), !isIndentedContinuationLine(line) {
338 guard (orderedListItem(in: trimmed) != nil) == startsOrdered else { break }
339 block.append(contentsOf: pendingBlanks); pendingBlanks = []
340 block.append(line); index += 1; continue
341 }
342 if isIndentedContinuationLine(line) {
343 block.append(contentsOf: pendingBlanks); pendingBlanks = []
344 block.append(line); index += 1; continue
345 }
346 break
347 }
348 return (buildList(block), index)
349 }
350
351 /// Group a list block's lines into items, recursing for nested lists.
352 private static func buildList(_ lines: [String]) -> OrgList {
353 let base = lines.filter { !$0.trimmingCharacters(in: .whitespaces).isEmpty }
354 .map(leadingWidth).min() ?? 0
355 let normalized = lines.map { dropLeading($0, base) }
356
357 var groups: [[String]] = []
358 var current: [String] = []
359 for line in normalized {
360 if isListMarkerLine(line) {
361 if !current.isEmpty { groups.append(current) }
362 current = [line]
363 } else if !current.isEmpty {
364 current.append(line)
365 }
366 }
367 if !current.isEmpty { groups.append(current) }
368
369 let firstMarker = groups.first?.first ?? ""
370 var kind: OrgListKind = orderedListItem(in: firstMarker) != nil ? .ordered : .unordered
371 if stripMarker(firstMarker).contains(" :: ") { kind = .description }
372
373 let items = groups.map { buildItem($0, kind: kind) }
374 return OrgList(kind: kind, items: items)
375 }
376
377 private static func buildItem(_ lines: [String], kind: OrgListKind) -> OrgListItem {
378 var head = stripMarker(lines[0])
379 var checkbox: OrgCheckbox?
380 if head.hasPrefix("[ ] ") { checkbox = .off; head = String(head.dropFirst(4)) }
381 else if head.hasPrefix("[X] ") || head.hasPrefix("[x] ") { checkbox = .on; head = String(head.dropFirst(4)) }
382 else if head.hasPrefix("[-] ") { checkbox = .partial; head = String(head.dropFirst(4)) }
383
384 // `term :: definition` splits on the item's first line only, as org requires.
385 var term: [OrgObject]?
386 if kind == .description, let range = head.range(of: " :: ") {
387 term = parseInline(String(head[..<range.lowerBound]))
388 head = String(head[range.upperBound...])
389 }
390
391 // The item's body is outdented to column 0 and parsed as a document of its own, so an
392 // item holds whatever a document holds — several paragraphs, a nested list, a source
393 // block, a table — in source order.
394 let rest = Array(lines.dropFirst())
395 let childIndent = rest.filter { !$0.trimmingCharacters(in: .whitespaces).isEmpty }
396 .map(leadingWidth).min() ?? 0
397 let body = ([head] + rest.map { dropLeading($0, childIndent) }).joined(separator: "\n")
398
399 return OrgListItem(checkbox: checkbox, term: term, content: parse(body).elements)
400 }
401
402 // MARK: - Helpers
403
404 private static func parseAttributes(_ value: String) -> [(key: String, value: String)] {
405 guard let regex = try? NSRegularExpression(pattern: #":([A-Za-z_][A-Za-z0-9_-]*)\s+("[^"]*"|\S+)"#) else {
406 return []
407 }
408 let ns = value as NSString
409 return regex.matches(in: value, range: NSRange(location: 0, length: ns.length)).map { m in
410 var raw = ns.substring(with: m.range(at: 2))
411 if raw.count >= 2, raw.hasPrefix("\""), raw.hasSuffix("\"") { raw = String(raw.dropFirst().dropLast()) }
412 return (ns.substring(with: m.range(at: 1)).lowercased(), raw)
413 }
414 }
415
416 private static func stripMarker(_ line: String) -> String {
417 let trimmed = line.trimmingCharacters(in: .whitespaces)
418 if trimmed.hasPrefix("- ") || trimmed.hasPrefix("+ ") { return String(trimmed.dropFirst(2)) }
419 if let match = trimmed.firstMatch(of: /^\d+[.)]\s+(.*)$/) { return String(match.1) }
420 return trimmed
421 }
422
423 private static func leadingWidth(_ line: String) -> Int {
424 var count = 0
425 for ch in line {
426 if ch == " " { count += 1 } else if ch == "\t" { count += 8 } else { break }
427 }
428 return count
429 }
430
431 private static func dropLeading(_ line: String, _ n: Int) -> String {
432 var dropped = 0
433 var index = line.startIndex
434 while index < line.endIndex, dropped < n {
435 if line[index] == " " { dropped += 1 }
436 else if line[index] == "\t" { dropped += 8 }
437 else { break }
438 index = line.index(after: index)
439 }
440 return String(line[index...])
441 }
442}