Sources/OrgCore/Parser/Parser.swift
449 lines · 16791 bytes
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) }
24 let ends = Parser.matchEnds(info)
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) }
33 self.init(lines: lines, info: info, blockEnds: Parser.matchEnds(info), 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]) -> [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 .dynamicBegin: isEnd = { $0 == .dynamicEnd }
51 case .drawerBegin: isEnd = { $0 == .drawerEnd }
52 default: isEnd = nil
53 }
54 if let isEnd {
55 var j = k + 1
56 while j < info.count {
57 if case .heading = info[j].cls { break }
58 if isEnd(info[j].cls) { ends[k] = j; break }
59 j += 1
60 }
61 // Block contents are verbatim, so nothing inside starts another element.
62 if let end = ends[k], !isDrawer(info[k].cls) { k = end }
63 }
64 k += 1
65 }
66 return ends
67 }
68
69 static func isDrawer(_ cls: LineClass) -> Bool {
70 if case .drawerBegin = cls { return true }
71 return false
72 }
73
74 mutating func run() -> OrgTree {
75 builder.start(.document)
76 if !lines.isEmpty, !isHeading(0) {
77 builder.start(.zerothSection)
78 parseContent(limit: lines.count)
79 builder.finish()
80 }
81 while i < lines.count, case .heading(let level) = info[i].cls {
82 parseSection(level: level)
83 }
84 builder.finish()
85 return OrgTree(green: builder.build(), settings: settings)
86 }
87
88 func isHeading(_ k: Int) -> Bool {
89 if case .heading = info[k].cls { return true }
90 return false
91 }
92
93 mutating func parseSection(level: Int) {
94 builder.start(.section)
95 headingLine(lines[i])
96 i += 1
97 if i < lines.count, info[i].cls == .planning {
98 single(.planning)
99 }
100 if i < lines.count, case .drawerBegin(let name) = info[i].cls, name.uppercased() == "PROPERTIES",
101 let end = blockEnds[i] {
102 propertyDrawer(end: end)
103 }
104 parseContent(limit: lines.count)
105 while i < lines.count, case .heading(let child) = info[i].cls, child > level {
106 parseSection(level: child)
107 }
108 builder.finish()
109 }
110
111 mutating func propertyDrawer(end: Int) {
112 builder.start(.propertyDrawer)
113 line(i)
114 i += 1
115 while i < end {
116 if info[i].cls == .blank {
117 line(i)
118 } else {
119 builder.start(.nodeProperty)
120 line(i)
121 builder.finish()
122 }
123 i += 1
124 }
125 line(i)
126 i += 1
127 builder.finish()
128 }
129
130 /// Elements until `limit` or the next heading.
131 mutating func parseContent(limit: Int) {
132 while i < limit, !isHeading(i) {
133 element(limit: limit, floor: nil)
134 }
135 }
136
137 static let affiliatedKeys: Set<String> = ["NAME", "CAPTION", "RESULTS", "HEADER", "PLOT"]
138
139 /// One element starting at `i`. `floor` is the indent of the enclosing list item, if any:
140 /// non-blank lines at or left of it end the element.
141 mutating func element(limit: Int, floor: Int?) {
142 switch info[i].cls {
143 case .blank:
144 line(i)
145 i += 1
146 case .blockBegin, .dynamicBegin:
147 if let end = blockEnds[i], end < limit {
148 builder.start(info[i].cls == .dynamicBegin ? .dynamicBlock : .block)
149 while i <= end {
150 line(i)
151 i += 1
152 }
153 builder.finish()
154 } else {
155 paragraph(limit: limit, floor: floor)
156 }
157 case .drawerBegin:
158 if let end = blockEnds[i], end < limit {
159 builder.start(.drawer)
160 line(i)
161 i += 1
162 parseContent(limit: end)
163 line(i)
164 i += 1
165 builder.finish()
166 } else {
167 paragraph(limit: limit, floor: floor)
168 }
169 case .keyword(let key):
170 let affiliated = Self.affiliatedKeys.contains(key) || key.hasPrefix("ATTR_")
171 single(affiliated ? .affiliatedKeyword : .keyword)
172 case .comment:
173 consecutive(.comment, limit: limit, floor: floor) { $0 == .comment }
174 case .fixedWidth:
175 consecutive(.fixedWidth, limit: limit, floor: floor) { $0 == .fixedWidth }
176 case .horizontalRule:
177 single(.horizontalRule)
178 case .clock:
179 single(.clock)
180 case .tableRow:
181 table(limit: limit, floor: floor)
182 case .footnoteDefinition:
183 footnoteDefinition(limit: limit)
184 case .listItem:
185 list(limit: limit, floor: floor)
186 default:
187 paragraph(limit: limit, floor: floor)
188 }
189 }
190
191 /// Kinds whose single line holds inline objects (timestamps on planning and clock lines).
192 static let inlineLineKinds: Set<SyntaxKind> = [.planning, .clock]
193
194 mutating func single(_ kind: SyntaxKind) {
195 builder.start(kind)
196 if Self.inlineLineKinds.contains(kind) {
197 let rest = whitespace(lines[i].content)
198 inline(rest)
199 builder.token(.newline, lines[i].ending)
200 } else {
201 line(i)
202 }
203 i += 1
204 builder.finish()
205 }
206
207 /// Source text from `start` through the end of line `last`, including its line ending.
208 func span(from start: Substring.Index, through last: Int) -> Substring {
209 let base = lines[last].ending.base
210 return base[start..<lines[last].ending.endIndex]
211 }
212
213 mutating func consecutive(_ kind: SyntaxKind, limit: Int, floor: Int?, matching: (LineClass) -> Bool) {
214 builder.start(kind)
215 repeat {
216 line(i)
217 i += 1
218 } while i < limit && matching(info[i].cls) && within(floor, i)
219 builder.finish()
220 }
221
222 mutating func table(limit: Int, floor: Int?) {
223 builder.start(.table)
224 while i < limit, info[i].cls == .tableRow, within(floor, i) {
225 tableRow()
226 }
227 while i < limit, info[i].cls == .keyword(key: "TBLFM"), within(floor, i) {
228 single(.tableFormula)
229 }
230 builder.finish()
231 }
232
233 /// A rule row (`|---+---|`) is one text token. Other rows alternate `|` markers and cells;
234 /// every pair of pipes gets a cell, even an empty one, so columns line up.
235 mutating func tableRow() {
236 if !reusableRows.isEmpty {
237 let content = lines[i].content
238 if let row = reusableRows[content.base[content.startIndex..<lines[i].ending.endIndex]] {
239 builder.node(row)
240 i += 1
241 return
242 }
243 }
244 builder.start(.tableRow)
245 let rest = whitespace(lines[i].content)
246 if rest.hasPrefix("|-") {
247 builder.token(.text, rest)
248 } else {
249 var cellStart = rest.startIndex
250 var index = rest.startIndex
251 while index < rest.endIndex {
252 if rest[index] == "|" {
253 if index > rest.startIndex { tableCell(rest[cellStart..<index]) }
254 builder.token(.marker, "|")
255 cellStart = rest.index(after: index)
256 }
257 index = rest.index(after: index)
258 }
259 if cellStart < rest.endIndex { tableCell(rest[cellStart...]) }
260 }
261 builder.token(.newline, lines[i].ending)
262 builder.finish()
263 i += 1
264 }
265
266 mutating func tableCell(_ text: Substring) {
267 builder.start(.tableCell)
268 inline(text)
269 builder.finish()
270 }
271
272 mutating func footnoteDefinition(limit: Int) {
273 var end = i + 1
274 while end < limit, info[end].cls == .plain { end += 1 }
275 let content = lines[i].content
276 let close = content.firstIndex(of: "]")!
277 builder.start(.footnoteDefinition)
278 builder.token(.marker, content[...close])
279 inline(span(from: content.index(after: close), through: end - 1))
280 builder.finish()
281 i = end
282 }
283
284 mutating func list(limit: Int, floor: Int?) {
285 let base = info[i].indent
286 builder.start(.plainList)
287 while i < limit, info[i].cls == .listItem, info[i].indent == base, within(floor, i) {
288 item(base: base, limit: limit)
289 }
290 builder.finish()
291 }
292
293 /// An item's first line, then everything indented past its bullet. One blank line stays
294 /// inside the item when the item or list continues after it; two end the list.
295 mutating func item(base: Int, limit: Int) {
296 builder.start(.item)
297 var rest = whitespace(lines[i].content)
298 let bullet = rest.prefix { $0 != " " && $0 != "\t" }
299 builder.token(.bullet, bullet)
300 rest = whitespace(rest.dropFirst(bullet.count))
301 if let box = checkbox(rest) {
302 builder.token(.checkbox, box)
303 rest = whitespace(rest.dropFirst(box.count))
304 }
305 // The rest of the bullet line and its continuation lines are the item's first paragraph.
306 var end = i + 1
307 while end < limit, within(base, end), continuesParagraph(end) { end += 1 }
308 if rest.isEmpty, end == i + 1 {
309 builder.token(.newline, lines[i].ending)
310 } else {
311 builder.start(.paragraph)
312 inline(span(from: rest.startIndex, through: end - 1))
313 builder.finish()
314 }
315 i = end
316 while i < limit, !isHeading(i) {
317 if info[i].cls == .blank {
318 var j = i
319 while j < limit, info[j].cls == .blank { j += 1 }
320 guard j - i < 2, j < limit else { break }
321 let continuesItem = info[j].indent > base
322 let nextSibling = info[j].cls == .listItem && info[j].indent == base
323 guard continuesItem || nextSibling else { break }
324 line(i)
325 i += 1
326 if nextSibling { break }
327 continue
328 }
329 guard info[i].indent > base else { break }
330 element(limit: limit, floor: base)
331 }
332 builder.finish()
333 }
334
335 /// `[ ]`, `[X]`, `[x]` or `[-]`, followed by whitespace or end of line.
336 func checkbox(_ s: Substring) -> Substring? {
337 guard s.count >= 3, s.first == "[", "Xx -".contains(s.dropFirst().first!),
338 s.dropFirst(2).first == "]" else { return nil }
339 let after = s.dropFirst(3)
340 guard after.isEmpty || after.first == " " || after.first == "\t" else { return nil }
341 return s.prefix(3)
342 }
343
344 /// The paragraph's lines are one inline run, so emphasis and links can cross a line break.
345 mutating func paragraph(limit: Int, floor: Int?) {
346 var end = i + 1
347 while end < limit, within(floor, end), continuesParagraph(end) { end += 1 }
348 builder.start(.paragraph)
349 inline(span(from: lines[i].content.startIndex, through: end - 1))
350 builder.finish()
351 i = end
352 }
353
354 /// Lines that don't start an element of their own.
355 func continuesParagraph(_ k: Int) -> Bool {
356 switch info[k].cls {
357 case .plain, .planning, .blockEnd, .dynamicEnd, .drawerEnd:
358 return true
359 case .blockBegin, .dynamicBegin, .drawerBegin:
360 return blockEnds[k] == nil
361 default:
362 return false
363 }
364 }
365
366 func within(_ floor: Int?, _ k: Int) -> Bool {
367 guard let floor else { return true }
368 return info[k].indent > floor
369 }
370
371 // MARK: - Tokens
372
373 /// A whole line as leading whitespace, content and line ending.
374 mutating func line(_ k: Int) {
375 let rest = whitespace(lines[k].content)
376 builder.token(.text, rest)
377 builder.token(.newline, lines[k].ending)
378 }
379
380 mutating func whitespace(_ s: Substring) -> Substring {
381 let ws = s.prefix { $0 == " " || $0 == "\t" }
382 builder.token(.whitespace, ws)
383 return s.dropFirst(ws.count)
384 }
385
386 mutating func headingLine(_ raw: RawLine) {
387 builder.start(.heading)
388 var rest = raw.content
389 let stars = rest.prefix { $0 == "*" }
390 builder.token(.stars, stars)
391 rest = whitespace(rest.dropFirst(stars.count))
392
393 // As org: a keyword counts only before a space or the end of the line, not a tab.
394 let word = rest.prefix { $0 != " " && $0 != "\t" }
395 let afterWord = rest.dropFirst(word.count).first
396 if !word.isEmpty, afterWord == nil || afterWord == " ", settings.todoKeywordNames.contains(String(word)) {
397 builder.token(.todoKeyword, word)
398 rest = whitespace(rest.dropFirst(word.count))
399 }
400
401 if let cookie = priorityCookie(rest) {
402 builder.token(.priority, cookie)
403 rest = whitespace(rest.dropFirst(cookie.count))
404 }
405
406 let parts = splitTags(rest)
407 if !parts.title.isEmpty {
408 builder.start(.title)
409 inline(parts.title)
410 builder.finish()
411 }
412 builder.token(.whitespace, parts.gap)
413 builder.token(.tags, parts.tags)
414 builder.token(.whitespace, parts.trailing)
415 builder.token(.newline, raw.ending)
416 builder.finish()
417 }
418
419 /// `[#A]` or `[#10]`, followed by whitespace or end of line.
420 func priorityCookie(_ s: Substring) -> Substring? {
421 guard s.hasPrefix("[#"), let close = s.firstIndex(of: "]") else { return nil }
422 let value = s[s.index(s.startIndex, offsetBy: 2)..<close]
423 let valid = (value.count == 1 && value.first!.isLetter && value.first!.isUppercase)
424 || (!value.isEmpty && value.allSatisfy { $0.isASCII && $0.isNumber })
425 guard valid else { return nil }
426 let after = s[s.index(after: close)...]
427 guard after.isEmpty || after.first == " " || after.first == "\t" else { return nil }
428 return s[...close]
429 }
430
431 func splitTags(_ s: Substring) -> (title: Substring, gap: Substring, tags: Substring, trailing: Substring) {
432 let trimmed = s.trimmingTrailingWhitespace
433 let trailing = s[trimmed.endIndex...]
434 let none = (title: trimmed, gap: Substring(), tags: Substring(), trailing: trailing)
435 guard trimmed.last == ":" else { return none }
436 let tagStart = trimmed.lastIndex { $0 == " " || $0 == "\t" }.map { trimmed.index(after: $0) } ?? trimmed.startIndex
437 let tags = trimmed[tagStart...]
438 guard tags.count >= 3, tags.first == ":", isTagString(tags) else { return none }
439 let before = trimmed[..<tagStart]
440 let title = before.trimmingTrailingWhitespace
441 return (title, before[title.endIndex...], tags, trailing)
442 }
443
444 func isTagString(_ tags: Substring) -> Bool {
445 tags.dropFirst().dropLast().split(separator: ":", omittingEmptySubsequences: false).allSatisfy { tag in
446 !tag.isEmpty && tag.allSatisfy { $0.isLetter || $0.isNumber || "_@#%".contains($0) }
447 }
448 }
449}