Sources/OrgCore/Parser/Parser.swift
548 lines · 21431 bytes
33 symbols in this file
OrgParserparseParsermatchEndsisDrawerrunisHeadingparseSectionpropertyDrawerparseContentelementinlineTasksinglespanconsecutivetabletableElEndisTableLinetableRowtableCellfootnoteDefinitionlistitemcheckboxparagraphcontinuesParagraphwithinlinewhitespaceheadingLinepriorityCookiesplitTagsisTagString
1public enum OrgParser {
2 public static func parse(_ text: String, defaults: OrgSettings = .default) -> OrgTree {
3 var parser = Parser(text: text, defaults: defaults)
4 return parser.run()
5 }
6}
7
8struct Parser {
9 let lines: [RawLine]
10 let info: [ClassifiedLine]
11 /// Begin line → end line, for blocks, dynamic blocks and drawers that are closed before the
12 /// next heading.
13 let blockEnds: [Int: Int]
14 let settings: OrgSettings
15 var builder = GreenBuilder()
16 var i = 0
17 /// Table rows from a previous version, by their line text. A row parses from its own line
18 /// alone, so a row with the same text can be reused instead of scanned again.
19 var reusableRows: [Substring: GreenNode] = [:]
20
21 init(text: String, defaults: OrgSettings) {
22 let lines = splitRawLines(text)
23 let info = lines.map { classifyLine($0.content, alphabetical: defaults.listAllowAlphabetical) }
24 let ends = Parser.matchEnds(info, lines)
25 let settings = SettingsScanner.scan(lines: lines, info: info, blockEnds: ends, defaults: defaults)
26 self.init(lines: lines, info: info, blockEnds: ends, settings: settings)
27 }
28
29 /// Parses part of a document with the settings already read from the whole file.
30 init(text: String, settings: OrgSettings) {
31 let lines = splitRawLines(text)
32 let info = lines.map { classifyLine($0.content, alphabetical: settings.listAllowAlphabetical) }
33 self.init(lines: lines, info: info, blockEnds: Parser.matchEnds(info, lines), settings: settings)
34 }
35
36 private init(lines: [RawLine], info: [ClassifiedLine], blockEnds: [Int: Int], settings: OrgSettings) {
37 self.lines = lines
38 self.info = info
39 self.blockEnds = blockEnds
40 self.settings = settings
41 }
42
43 static func matchEnds(_ info: [ClassifiedLine], _ lines: [RawLine]) -> [Int: Int] {
44 var ends: [Int: Int] = [:]
45 var k = 0
46 while k < info.count {
47 let isEnd: ((LineClass) -> Bool)?
48 switch info[k].cls {
49 case .blockBegin(let name): isEnd = { $0 == .blockEnd(name: name) }
50 case .latexBegin(let name):
51 // `\end{NAME}` ending a line, the first line's own included.
52 let closer = "\\end{" + name + "}"
53 var j = k
54 while j < info.count {
55 if j > k, case .heading = info[j].cls { break }
56 let content = lines[j].content.trimmingTrailingWhitespace
57 if content.hasSuffix(closer), j > k || content.count > closer.count + 7 + name.count { ends[k] = j; break }
58 j += 1
59 }
60 k += 1
61 continue
62 case .dynamicBegin: isEnd = { $0 == .dynamicEnd }
63 case .drawerBegin: isEnd = { $0 == .drawerEnd }
64 default: isEnd = nil
65 }
66 if let isEnd {
67 var j = k + 1
68 while j < info.count {
69 if case .heading = info[j].cls { break }
70 if isEnd(info[j].cls) { ends[k] = j; break }
71 j += 1
72 }
73 // Block contents are verbatim, so nothing inside starts another element.
74 if let end = ends[k], !isDrawer(info[k].cls) { k = end }
75 }
76 k += 1
77 }
78 return ends
79 }
80
81 static func isDrawer(_ cls: LineClass) -> Bool {
82 if case .drawerBegin = cls { return true }
83 return false
84 }
85
86 mutating func run() -> OrgTree {
87 builder.start(.document)
88 if !lines.isEmpty, !isHeading(0) {
89 builder.start(.zerothSection)
90 // A property drawer first in the file, after comments and blank lines, holds the
91 // file's properties.
92 while i < lines.count, info[i].cls == .blank || info[i].cls == .comment {
93 if info[i].cls == .blank { line(i); i += 1 } else { consecutive(.comment, limit: lines.count, floor: nil) { $0 == .comment } }
94 }
95 if i < lines.count, case .drawerBegin(let name) = info[i].cls, name.uppercased() == "PROPERTIES", let end = blockEnds[i] {
96 propertyDrawer(end: end)
97 }
98 parseContent(limit: lines.count)
99 builder.finish()
100 }
101 while i < lines.count, case .heading(let level) = info[i].cls {
102 parseSection(level: level)
103 }
104 builder.finish()
105 return OrgTree(green: builder.build(), settings: settings)
106 }
107
108 func isHeading(_ k: Int) -> Bool {
109 if case .heading = info[k].cls { return true }
110 return false
111 }
112
113 mutating func parseSection(level: Int) {
114 builder.start(.section)
115 headingLine(lines[i])
116 i += 1
117 if i < lines.count, info[i].cls == .planning {
118 single(.planning)
119 }
120 if i < lines.count, case .drawerBegin(let name) = info[i].cls, name.uppercased() == "PROPERTIES",
121 let end = blockEnds[i] {
122 propertyDrawer(end: end)
123 }
124 parseContent(limit: lines.count)
125 while i < lines.count, case .heading(let child) = info[i].cls, child > level {
126 parseSection(level: child)
127 }
128 builder.finish()
129 }
130
131 mutating func propertyDrawer(end: Int) {
132 builder.start(.propertyDrawer)
133 line(i)
134 i += 1
135 while i < end {
136 if info[i].cls == .blank {
137 line(i)
138 } else {
139 builder.start(.nodeProperty)
140 line(i)
141 builder.finish()
142 }
143 i += 1
144 }
145 line(i)
146 i += 1
147 builder.finish()
148 }
149
150 /// Elements until `limit` or the next heading.
151 mutating func parseContent(limit: Int) {
152 while i < limit, !isHeading(i) {
153 element(limit: limit, floor: nil)
154 }
155 }
156
157 static let affiliatedKeys: Set<String> = ["NAME", "CAPTION", "RESULTS", "HEADER", "PLOT"]
158
159 /// One element starting at `i`. `floor` is the indent of the enclosing list item, if any:
160 /// non-blank lines at or left of it end the element.
161 mutating func element(limit: Int, floor: Int?) {
162 switch info[i].cls {
163 case .blank:
164 line(i)
165 i += 1
166 case .blockBegin, .dynamicBegin, .latexBegin:
167 if let end = blockEnds[i], end < limit {
168 let kind: SyntaxKind = switch info[i].cls {
169 case .dynamicBegin: .dynamicBlock
170 case .latexBegin: .latexEnvironment
171 default: .block
172 }
173 builder.start(kind)
174 while i <= end {
175 line(i)
176 i += 1
177 }
178 builder.finish()
179 } else {
180 paragraph(limit: limit, floor: floor)
181 }
182 case .drawerBegin:
183 if let end = blockEnds[i], end < limit {
184 builder.start(.drawer)
185 line(i)
186 i += 1
187 parseContent(limit: end)
188 line(i)
189 i += 1
190 builder.finish()
191 } else {
192 paragraph(limit: limit, floor: floor)
193 }
194 case .inlineTask:
195 inlineTask(limit: limit)
196 case .keyword(let key):
197 let affiliated = Self.affiliatedKeys.contains(key) || key.hasPrefix("ATTR_")
198 single(affiliated ? .affiliatedKeyword : .keyword)
199 case .comment:
200 consecutive(.comment, limit: limit, floor: floor) { $0 == .comment }
201 case .fixedWidth:
202 consecutive(.fixedWidth, limit: limit, floor: floor) { $0 == .fixedWidth }
203 case .horizontalRule:
204 single(.horizontalRule)
205 case .clock:
206 single(.clock)
207 case .tableRow:
208 table(limit: limit, floor: floor)
209 case .tableElRule:
210 if let end = tableElEnd(limit: limit, floor: floor) {
211 builder.start(.tableEl)
212 while i < end {
213 line(i)
214 i += 1
215 }
216 while i < limit, info[i].cls == .keyword(key: "TBLFM"), within(floor, i) {
217 single(.tableFormula)
218 }
219 builder.finish()
220 } else {
221 paragraph(limit: limit, floor: floor)
222 }
223 case .diarySexp:
224 single(.diarySexp)
225 case .footnoteDefinition:
226 footnoteDefinition(limit: limit)
227 case .listItem:
228 list(limit: limit, floor: floor)
229 default:
230 paragraph(limit: limit, floor: floor)
231 }
232 }
233
234 /// An inline task: its heading line, and with an END line before the next heading, the
235 /// elements up to it and that line.
236 mutating func inlineTask(limit: Int) {
237 builder.start(.inlineTask)
238 headingLine(lines[i])
239 i += 1
240 var end: Int?
241 var k = i
242 while k < limit, !isHeading(k) {
243 if info[k].cls == .inlineTaskEnd { end = k; break }
244 if case .inlineTask = info[k].cls { break }
245 k += 1
246 }
247 if let end {
248 if i < end, info[i].cls == .planning { single(.planning) }
249 if i < end, case .drawerBegin(let name) = info[i].cls, name.uppercased() == "PROPERTIES", let drawerEnd = blockEnds[i], drawerEnd < end {
250 propertyDrawer(end: drawerEnd)
251 }
252 parseContent(limit: end)
253 headingLine(lines[i])
254 i += 1
255 }
256 builder.finish()
257 }
258
259 /// Kinds whose single line holds inline objects (timestamps on planning and clock lines).
260 static let inlineLineKinds: Set<SyntaxKind> = [.planning, .clock]
261
262 mutating func single(_ kind: SyntaxKind) {
263 builder.start(kind)
264 if Self.inlineLineKinds.contains(kind) {
265 let rest = whitespace(lines[i].content)
266 inline(rest)
267 builder.token(.newline, lines[i].ending)
268 } else {
269 line(i)
270 }
271 i += 1
272 builder.finish()
273 }
274
275 /// Source text from `start` through the end of line `last`, including its line ending.
276 func span(from start: Substring.Index, through last: Int) -> Substring {
277 let base = lines[last].ending.base
278 return base[start..<lines[last].ending.endIndex]
279 }
280
281 mutating func consecutive(_ kind: SyntaxKind, limit: Int, floor: Int?, matching: (LineClass) -> Bool) {
282 builder.start(kind)
283 repeat {
284 line(i)
285 i += 1
286 } while i < limit && matching(info[i].cls) && within(floor, i)
287 builder.finish()
288 }
289
290 mutating func table(limit: Int, floor: Int?) {
291 builder.start(.table)
292 while i < limit, info[i].cls == .tableRow, within(floor, i) {
293 tableRow()
294 }
295 while i < limit, info[i].cls == .keyword(key: "TBLFM"), within(floor, i) {
296 single(.tableFormula)
297 }
298 builder.finish()
299 }
300
301 /// Where the table.el table starting at line `i` ends, as `org-element--current-element`
302 /// decides: a full rule first and last, at least two lines, every line starting with `+`
303 /// or `|`. Nil for none.
304 func tableElEnd(limit: Int, floor: Int?) -> Int? {
305 guard i + 1 < limit else { return nil }
306 func isTableLine(_ k: Int) -> Bool {
307 guard within(floor, k) else { return false }
308 let first = lines[k].content.drop { $0 == " " || $0 == "\t" }.first
309 return first == "+" || first == "|"
310 }
311 var k = i + 1
312 while k < limit, isTableLine(k) { k += 1 }
313 if k == i + 1 { return nil }
314 return info[k - 1].cls == .tableElRule ? k : nil
315 }
316
317 /// A rule row (`|---+---|`) is one text token. Other rows alternate `|` markers and cells;
318 /// every pair of pipes gets a cell, even an empty one, so columns line up.
319 mutating func tableRow() {
320 if !reusableRows.isEmpty {
321 let content = lines[i].content
322 if let row = reusableRows[content.base[content.startIndex..<lines[i].ending.endIndex]] {
323 builder.node(row)
324 i += 1
325 return
326 }
327 }
328 builder.start(.tableRow)
329 let rest = whitespace(lines[i].content)
330 if rest.hasPrefix("|-") {
331 builder.token(.text, rest)
332 } else {
333 var cellStart = rest.startIndex
334 var index = rest.startIndex
335 while index < rest.endIndex {
336 if rest[index] == "|" {
337 if index > rest.startIndex { tableCell(rest[cellStart..<index]) }
338 builder.token(.marker, "|")
339 cellStart = rest.index(after: index)
340 }
341 index = rest.index(after: index)
342 }
343 if cellStart < rest.endIndex { tableCell(rest[cellStart...]) }
344 }
345 builder.token(.newline, lines[i].ending)
346 builder.finish()
347 i += 1
348 }
349
350 mutating func tableCell(_ text: Substring) {
351 builder.start(.tableCell)
352 inline(text)
353 builder.finish()
354 }
355
356 mutating func footnoteDefinition(limit: Int) {
357 var end = i + 1
358 while end < limit, info[end].cls == .plain { end += 1 }
359 let content = lines[i].content
360 let close = content.firstIndex(of: "]")!
361 builder.start(.footnoteDefinition)
362 builder.token(.marker, content[...close])
363 inline(span(from: content.index(after: close), through: end - 1))
364 builder.finish()
365 i = end
366 }
367
368 mutating func list(limit: Int, floor: Int?) {
369 let base = info[i].indent
370 builder.start(.plainList)
371 while i < limit, info[i].cls == .listItem, info[i].indent == base, within(floor, i) {
372 item(base: base, limit: limit)
373 }
374 builder.finish()
375 }
376
377 /// An item's first line, then everything indented past its bullet. One blank line stays
378 /// inside the item when the item or list continues after it; two end the list.
379 mutating func item(base: Int, limit: Int) {
380 builder.start(.item)
381 var rest = whitespace(lines[i].content)
382 let bullet = rest.prefix { $0 != " " && $0 != "\t" }
383 builder.token(.bullet, bullet)
384 rest = whitespace(rest.dropFirst(bullet.count))
385 if let counter = rest.prefixMatch(of: /\[@(?:start:)?(?:[0-9]+|[A-Za-z])\]/) {
386 builder.token(.counter, rest[counter.range])
387 rest = whitespace(rest[counter.range.upperBound...])
388 }
389 if let box = checkbox(rest) {
390 builder.token(.checkbox, box)
391 rest = whitespace(rest.dropFirst(box.count))
392 }
393 // A description item's tag: up to the last ` ::` on the line, for `-`, `+` and `*`.
394 if "-+*".contains(bullet), let m = rest.prefixMatch(of: /(.*)([ \t]+::)(?:[ \t]+|$)/.anchorsMatchLineEndings()) {
395 builder.start(.itemTag)
396 inline(rest[m.1.startIndex..<m.1.endIndex])
397 builder.finish()
398 let separator = rest[m.2.startIndex..<m.2.endIndex]
399 let blank = separator.prefix { $0 == " " || $0 == "\t" }
400 builder.token(.whitespace, blank)
401 builder.token(.marker, separator.dropFirst(blank.count))
402 rest = whitespace(rest[m.2.endIndex...])
403 }
404 // The rest of the bullet line and its continuation lines are the item's first paragraph.
405 var end = i + 1
406 while end < limit, within(base, end), continuesParagraph(end) { end += 1 }
407 if rest.isEmpty, end == i + 1 {
408 builder.token(.newline, lines[i].ending)
409 } else {
410 builder.start(.paragraph)
411 inline(span(from: rest.startIndex, through: end - 1))
412 builder.finish()
413 }
414 i = end
415 while i < limit, !isHeading(i) {
416 if info[i].cls == .blank {
417 var j = i
418 while j < limit, info[j].cls == .blank { j += 1 }
419 guard j - i < 2, j < limit else { break }
420 let continuesItem = info[j].indent > base
421 let nextSibling = info[j].cls == .listItem && info[j].indent == base
422 guard continuesItem || nextSibling else { break }
423 line(i)
424 i += 1
425 if nextSibling { break }
426 continue
427 }
428 guard info[i].indent > base else { break }
429 element(limit: limit, floor: base)
430 }
431 builder.finish()
432 }
433
434 /// `[ ]`, `[X]`, `[x]` or `[-]`, followed by whitespace or end of line.
435 func checkbox(_ s: Substring) -> Substring? {
436 guard s.count >= 3, s.first == "[", "Xx -".contains(s.dropFirst().first!),
437 s.dropFirst(2).first == "]" else { return nil }
438 let after = s.dropFirst(3)
439 guard after.isEmpty || after.first == " " || after.first == "\t" else { return nil }
440 return s.prefix(3)
441 }
442
443 /// The paragraph's lines are one inline run, so emphasis and links can cross a line break.
444 mutating func paragraph(limit: Int, floor: Int?) {
445 var end = i + 1
446 while end < limit, within(floor, end), continuesParagraph(end) { end += 1 }
447 builder.start(.paragraph)
448 inline(span(from: lines[i].content.startIndex, through: end - 1))
449 builder.finish()
450 i = end
451 }
452
453 /// Lines that don't start an element of their own.
454 func continuesParagraph(_ k: Int) -> Bool {
455 switch info[k].cls {
456 case .plain, .planning, .blockEnd, .dynamicEnd, .drawerEnd, .latexEnd:
457 return true
458 case .blockBegin, .dynamicBegin, .drawerBegin, .latexBegin:
459 return blockEnds[k] == nil
460 default:
461 return false
462 }
463 }
464
465 func within(_ floor: Int?, _ k: Int) -> Bool {
466 guard let floor else { return true }
467 return info[k].indent > floor
468 }
469
470 // MARK: - Tokens
471
472 /// A whole line as leading whitespace, content and line ending.
473 mutating func line(_ k: Int) {
474 let rest = whitespace(lines[k].content)
475 builder.token(.text, rest)
476 builder.token(.newline, lines[k].ending)
477 }
478
479 mutating func whitespace(_ s: Substring) -> Substring {
480 let ws = s.prefix { $0 == " " || $0 == "\t" }
481 builder.token(.whitespace, ws)
482 return s.dropFirst(ws.count)
483 }
484
485 mutating func headingLine(_ raw: RawLine) {
486 builder.start(.heading)
487 var rest = raw.content
488 let stars = rest.prefix { $0 == "*" }
489 builder.token(.stars, stars)
490 rest = whitespace(rest.dropFirst(stars.count))
491
492 // As org: a keyword counts only before a space or the end of the line, not a tab.
493 let word = rest.prefix { $0 != " " && $0 != "\t" }
494 let afterWord = rest.dropFirst(word.count).first
495 if !word.isEmpty, afterWord == nil || afterWord == " ", settings.todoKeywordNames.contains(String(word)) {
496 builder.token(.todoKeyword, word)
497 rest = whitespace(rest.dropFirst(word.count))
498 }
499
500 if let cookie = priorityCookie(rest) {
501 builder.token(.priority, cookie)
502 rest = whitespace(rest.dropFirst(cookie.count))
503 }
504
505 let parts = splitTags(rest)
506 if !parts.title.isEmpty {
507 builder.start(.title)
508 inline(parts.title)
509 builder.finish()
510 }
511 builder.token(.whitespace, parts.gap)
512 builder.token(.tags, parts.tags)
513 builder.token(.whitespace, parts.trailing)
514 builder.token(.newline, raw.ending)
515 builder.finish()
516 }
517
518 /// `[#A]` or `[#10]`, followed by whitespace or end of line.
519 func priorityCookie(_ s: Substring) -> Substring? {
520 guard s.hasPrefix("[#"), let close = s.firstIndex(of: "]") else { return nil }
521 let value = s[s.index(s.startIndex, offsetBy: 2)..<close]
522 let valid = (value.count == 1 && value.first!.isLetter && value.first!.isUppercase)
523 || (!value.isEmpty && value.allSatisfy { $0.isASCII && $0.isNumber })
524 guard valid else { return nil }
525 let after = s[s.index(after: close)...]
526 guard after.isEmpty || after.first == " " || after.first == "\t" else { return nil }
527 return s[...close]
528 }
529
530 func splitTags(_ s: Substring) -> (title: Substring, gap: Substring, tags: Substring, trailing: Substring) {
531 let trimmed = s.trimmingTrailingWhitespace
532 let trailing = s[trimmed.endIndex...]
533 let none = (title: trimmed, gap: Substring(), tags: Substring(), trailing: trailing)
534 guard trimmed.last == ":" else { return none }
535 let tagStart = trimmed.lastIndex { $0 == " " || $0 == "\t" }.map { trimmed.index(after: $0) } ?? trimmed.startIndex
536 let tags = trimmed[tagStart...]
537 guard tags.count >= 3, tags.first == ":", isTagString(tags) else { return none }
538 let before = trimmed[..<tagStart]
539 let title = before.trimmingTrailingWhitespace
540 return (title, before[title.endIndex...], tags, trailing)
541 }
542
543 func isTagString(_ tags: Substring) -> Bool {
544 tags.dropFirst().dropLast().split(separator: ":", omittingEmptySubsequences: false).allSatisfy { tag in
545 !tag.isEmpty && tag.allSatisfy { $0.isLetter || $0.isNumber || "_@#%".contains($0) }
546 }
547 }
548}