Sources/OrgCore/Parser/Incremental.swift
427 lines · 20735 bytes
1import Foundation
2
3public struct TextEdit: Sendable, Equatable {
4 /// UTF-16 range in the old text, on unicode scalar boundaries.
5 public let range: Range<Int>
6 public let replacement: String
7
8 public init(range: Range<Int>, replacement: String) {
9 self.range = range
10 self.replacement = replacement
11 }
12
13 /// Works on unicode scalars, so an edit between "\r" and "\n" stays exact.
14 public func apply(to text: String) -> String {
15 let scalars = text.unicodeScalars
16 let start = String.Index(utf16Offset: range.lowerBound, in: text)
17 let end = String.Index(utf16Offset: range.upperBound, in: text)
18 return String(scalars[..<start]) + replacement + String(scalars[end...])
19 }
20}
21
22enum ReparseStrategy: Equatable {
23 /// One element reparsed in place; everything else reused.
24 case element
25 /// A run of elements in one section's body reparsed; everything else reused.
26 case region
27 /// A run of top-level sections reparsed; the sections before and after reused.
28 case sections
29 case full
30}
31
32extension OrgParser {
33 /// The tree for `edit.apply(to: oldText)`, reusing as much of `old` as stays valid. Always
34 /// equal to a full parse of the new text.
35 public static func reparse(_ old: OrgTree, oldText: String, edit: TextEdit, defaults: OrgSettings = .default) -> OrgTree {
36 reparseWithStrategy(old, oldText: oldText, edit: edit, defaults: defaults).tree
37 }
38
39 static func reparseWithStrategy(
40 _ old: OrgTree, oldText: String, edit: TextEdit, defaults: OrgSettings = .default
41 ) -> (tree: OrgTree, strategy: ReparseStrategy) {
42 let newText = edit.apply(to: oldText)
43 let context = ReparseContext(oldText: oldText, newText: newText, edit: edit, alphabetical: defaults.listAllowAlphabetical)
44 if context.touchesSettings() { return (parse(newText, defaults: defaults), .full) }
45 if let tree = context.reparseElement(old) { return (tree, .element) }
46 if let tree = context.reparseRegion(old) { return (tree, .region) }
47 if let tree = context.reparseSections(old) { return (tree, .sections) }
48 return (parse(newText, defaults: defaults), .full)
49 }
50}
51
52private struct ReparseContext {
53 let oldText: String
54 let newText: String
55 let edit: TextEdit
56 /// `org-list-allow-alphabetical`, for classifying lines.
57 let alphabetical: Bool
58 /// Change in UTF-16 length.
59 var delta: Int { edit.replacement.utf16.count - edit.range.count }
60
61 static let settingsKeys: Set<String> = ["TODO", "SEQ_TODO", "TYP_TODO", "PRIORITIES", "STARTUP"]
62
63 /// Elements that parse the same in isolation as in place, as long as their lines keep
64 /// their classes.
65 static let leafKinds: Set<SyntaxKind> = [
66 .paragraph, .heading, .tableRow, .planning, .clock, .keyword, .affiliatedKeyword, .horizontalRule,
67 .nodeProperty, .block, .comment, .fixedWidth, .footnoteDefinition,
68 ]
69
70 /// File settings must be read again when an edited line is a settings keyword, or when it
71 /// moves a block or heading boundary in a file that has settings keywords: that can hide or
72 /// expose a keyword inside a block.
73 func touchesSettings() -> Bool {
74 let start = lineStart(oldText, edit.range.lowerBound)
75 let oldLines = classes(slice(oldText, start, lineEnd(oldText, edit.range.upperBound)))
76 let newLines = classes(slice(newText, start, lineEnd(newText, edit.range.lowerBound + edit.replacement.utf16.count)))
77 // Radio targets make links all through the file.
78 if slice(oldText, start, lineEnd(oldText, edit.range.upperBound)).contains("<<<")
79 || slice(newText, start, lineEnd(newText, edit.range.lowerBound + edit.replacement.utf16.count)).contains("<<<")
80 || slice(oldText, start, lineEnd(oldText, edit.range.upperBound)).contains(">>>") { return true }
81 var movesBoundary = false
82 for line in oldLines + newLines {
83 switch line.cls {
84 case .keyword(let key) where Self.settingsKeys.contains(key):
85 return true
86 case .blockBegin, .blockEnd, .dynamicBegin, .dynamicEnd, .latexBegin, .latexEnd, .heading:
87 movesBoundary = true
88 default:
89 break
90 }
91 }
92 return movesBoundary && Self.settingsKeys.contains { newText.range(of: "#+\($0):", options: .caseInsensitive) != nil }
93 }
94
95 // MARK: - Element
96
97 func reparseElement(_ old: OrgTree) -> OrgTree? {
98 guard let leaf = leaf(in: old.root) else { return nil }
99 let start = lineStart(oldText, leaf.range.lowerBound)
100 // An element that starts mid-line (an item's paragraph) follows tokens that would absorb
101 // whitespace typed at its start.
102 guard start == leaf.range.lowerBound || edit.range.lowerBound > leaf.range.lowerBound else { return nil }
103 // An item's first paragraph: its line can turn into a counter, checkbox or tag.
104 if start != leaf.range.lowerBound {
105 let oldLine = slice(oldText, leaf.range.lowerBound, lineEnd(oldText, leaf.range.lowerBound))
106 let newLine = slice(newText, leaf.range.lowerBound, lineEnd(newText, leaf.range.lowerBound))
107 for line in [oldLine, newLine] where line.contains("::") || line.hasPrefix("[@") || line.hasPrefix("[") {
108 return nil
109 }
110 }
111 let oldEnd = leaf.range.upperBound
112 let newEnd = oldEnd + delta
113 let newLength = newText.utf16.count
114 guard newEnd > leaf.range.lowerBound, newEnd <= newLength else { return nil }
115 // The element must still end at a line end.
116 if newEnd < newLength {
117 let utf16 = newText.utf16
118 guard utf16[utf16.index(utf16.startIndex, offsetBy: newEnd - 1)] == 0x0A else { return nil }
119 }
120 let oldClasses = classes(slice(oldText, start, oldEnd))
121 let newClasses = classes(slice(newText, start, newEnd))
122 guard oldClasses.count == newClasses.count,
123 zip(oldClasses, newClasses).allSatisfy({ $0.cls == $1.cls && $0.indent == $1.indent }) else { return nil }
124 let text = String(slice(newText, leaf.range.lowerBound, newEnd))
125 guard let green = Parser.reparseElement(leaf.kind, text: text, settings: old.settings) else { return nil }
126 return OrgTree(green: replacing(leaf, with: green), settings: old.settings)
127 }
128
129 /// The outermost leaf element containing the edit.
130 func leaf(in root: SyntaxNode) -> SyntaxNode? {
131 let range = edit.range
132 var current = root
133 while let child = current.child(containing: range.lowerBound), range.upperBound <= child.range.upperBound {
134 if Self.leafKinds.contains(child.kind) { return child }
135 current = child
136 }
137 return nil
138 }
139
140 /// Copies the path from the root down to `target`, swapping in `green`.
141 func replacing(_ target: SyntaxNode, with green: GreenNode) -> GreenNode {
142 var node = target
143 var replacement = green
144 while let parent = node.parent {
145 var children = parent.green.children
146 let index = children.firstIndex {
147 if case .node(let child) = $0 { return child === node.green }
148 return false
149 }!
150 children[index] = .node(replacement)
151 replacement = GreenNode(kind: parent.kind, children: children)
152 node = parent
153 }
154 return replacement
155 }
156
157 // MARK: - Body region
158
159 /// Reparses a window of the innermost section's own body (the elements between its heading
160 /// lines and its first child section) and splices it into the old section.
161 ///
162 /// The window starts one element before the element holding the line before the edit. It ends at the first
163 /// later element boundary that the reparse reproduces at the same shifted offset. The
164 /// window is parsed one element past that boundary, so every decision about where an element
165 /// ends was made with the following line in view; from a reproduced boundary on, elements
166 /// parse the same as before. Edits that touch heading lines, the first line after a heading
167 /// (where planning lines and property drawers are only recognized), or that add an end
168 /// delimiter (which could pair with a begin line before the window) are left to the
169 /// section strategy.
170 func reparseRegion(_ old: OrgTree) -> OrgTree? {
171 let start = lineStart(oldText, edit.range.lowerBound)
172 let oldLines = classes(slice(oldText, start, lineEnd(oldText, edit.range.upperBound)))
173 let newLines = classes(slice(newText, start, lineEnd(newText, edit.range.lowerBound + edit.replacement.utf16.count)))
174 for line in oldLines + newLines {
175 if case .heading = line.cls { return nil }
176 }
177 for line in newLines {
178 switch line.cls {
179 case .blockEnd, .dynamicEnd, .drawerEnd: return nil
180 default: break
181 }
182 }
183
184 // The innermost section or zeroth section holding the edited lines.
185 let damaged = start..<max(lineEnd(oldText, edit.range.upperBound), start + 1)
186 var container = old.root
187 while let child = container.child(containing: damaged.lowerBound),
188 child.kind == .section || child.kind == .zerothSection,
189 damaged.upperBound <= child.range.upperBound {
190 container = child
191 }
192 guard container.kind == .section || container.kind == .zerothSection else { return nil }
193
194 // Body children with their offsets.
195 var body: [(element: GreenElement, offset: Int)] = []
196 var bodyStart = container.range.lowerBound
197 var bodyEnd = container.range.upperBound
198 var offset = container.range.lowerBound
199 var prefixCount = 0
200 for (index, element) in container.green.children.enumerated() {
201 defer { offset += element.length }
202 if case .node(let node) = element {
203 if [.heading, .planning, .propertyDrawer].contains(node.kind), body.isEmpty {
204 prefixCount = index + 1
205 bodyStart = offset + node.length
206 continue
207 }
208 if node.kind == .section {
209 bodyEnd = offset
210 break
211 }
212 }
213 body.append((element, offset))
214 }
215 // The first body line of a heading section can become a planning line or drawer.
216 let firstEditable = container.kind == .section ? lineEnd(oldText, bodyStart) : bodyStart
217 guard start >= firstEditable, edit.range.upperBound <= bodyEnd, !body.isEmpty else { return nil }
218
219 // Window start: the body element holding the line before the edit, and one more before
220 // it, which could absorb the window's first line if that line changes meaning (a drawer
221 // that loses its end turns into paragraph text).
222 let anchor = max(bodyStart, start - 1)
223 guard var first = body.lastIndex(where: { $0.offset <= anchor }) else { return nil }
224 while first > 0, case .token = body[first].element { first -= 1 }
225 if first > 0 {
226 first -= 1
227 while first > 0, case .token = body[first].element { first -= 1 }
228 }
229 let windowStart = body[first].offset
230
231 var next = body.firstIndex { $0.offset > edit.range.upperBound } ?? body.count
232 var attempts = 0
233 while attempts < 8 {
234 attempts += 1
235 // Parse through one node past the candidate boundary.
236 var verifyEnd = next
237 while verifyEnd < body.count, case .token = body[verifyEnd].element { verifyEnd += 1 }
238 let boundary = next < body.count ? body[next].offset : bodyEnd
239 let oldWindowEnd = verifyEnd < body.count ? body[verifyEnd].offset + body[verifyEnd].element.length : bodyEnd
240 let rows = reusableRows(body[first..<min(verifyEnd + 1, body.count)].map(\.element))
241 guard let window = parseBody(slice(newText, windowStart, oldWindowEnd + delta), settings: old.settings, rows: rows) else { return nil }
242 if window.unmatchedBegin, oldWindowEnd < bodyEnd {
243 next = body.count
244 continue
245 }
246 // The reparsed elements up to the boundary, if the reparse has one there.
247 let target = boundary + delta - windowStart
248 var reparsed: [GreenElement] = []
249 var at = 0
250 for element in window.elements where at < target {
251 reparsed.append(element)
252 at += element.length
253 }
254 guard at == target else {
255 next += 1
256 if next > body.count { return nil }
257 continue
258 }
259 let before = container.green.children[..<(prefixCount + first)]
260 let after = next < body.count ? Array(body[next...].map(\.element)) : []
261 let tail = container.green.children[(prefixCount + body.count)...]
262 let green = GreenNode(kind: container.kind, children: Array(before) + reparsed + after + Array(tail))
263 // A full parse has no zeroth section for empty text.
264 if green.children.isEmpty { return nil }
265 return OrgTree(green: replacing(container, with: green), settings: old.settings)
266 }
267 return nil
268 }
269
270 /// Rows of the tables among `elements`, keyed by their text.
271 func reusableRows(_ elements: [GreenElement]) -> [Substring: GreenNode] {
272 var rows: [Substring: GreenNode] = [:]
273 for case .node(let table) in elements where table.kind == .table {
274 for case .node(let row) in table.children where row.kind == .tableRow {
275 rows[Substring(row.text)] = row
276 }
277 }
278 return rows
279 }
280
281 /// Body elements parsed from `text`, or nil if the text holds a heading.
282 func parseBody(_ text: Substring, settings: OrgSettings, rows: [Substring: GreenNode] = [:]) -> (elements: [GreenElement], unmatchedBegin: Bool)? {
283 var parser = Parser(text: String(text), settings: settings)
284 parser.reusableRows = rows
285 let count = parser.lines.count
286 parser.builder.start(.zerothSection)
287 parser.parseContent(limit: count)
288 guard parser.i == count else { return nil }
289 parser.builder.finish()
290 var unmatched = false
291 for (index, line) in parser.info.enumerated() {
292 switch line.cls {
293 case .blockBegin, .dynamicBegin, .drawerBegin, .latexBegin:
294 if parser.blockEnds[index] == nil { unmatched = true }
295 default:
296 break
297 }
298 }
299 return (parser.builder.build().children, unmatched)
300 }
301
302 // MARK: - Sections
303
304 /// Reparses from the top-level section before the edit up to the first later top-level
305 /// heading that still ends the reparsed run, then reuses the old sections from there.
306 /// Top-level sections parse independently: blocks and drawers never cross a heading.
307 func reparseSections(_ old: OrgTree) -> OrgTree? {
308 let units = old.root.children
309 guard !units.isEmpty else { return nil }
310 let anchor = max(0, lineStart(oldText, edit.range.lowerBound) - 1)
311 guard let startIndex = units.firstIndex(where: { $0.range.contains(anchor) }) else { return nil }
312 let start = units[startIndex].range.lowerBound
313 var endIndex = units.firstIndex { $0.range.lowerBound > edit.range.upperBound } ?? units.count
314 let newLength = newText.utf16.count
315 while true {
316 let newEnd = endIndex < units.count ? units[endIndex].range.lowerBound + delta : newLength
317 var parser = Parser(text: String(slice(newText, start, newEnd)), settings: old.settings)
318 let window = parser.run().green
319 if endIndex == units.count || endsRun(window, next: units[endIndex].green) {
320 let children = units[..<startIndex].map { GreenElement.node($0.green) }
321 + window.children
322 + units[endIndex...].map { GreenElement.node($0.green) }
323 return OrgTree(green: GreenNode(kind: .document, children: children), settings: old.settings)
324 }
325 endIndex += 1
326 }
327 }
328
329 /// Whether the heading of `next` ends the last section of the reparsed window.
330 func endsRun(_ window: GreenNode, next: GreenNode) -> Bool {
331 guard case .node(let last)? = window.children.last, last.kind == .section else { return true }
332 return headingLevel(next) <= headingLevel(last)
333 }
334
335 func headingLevel(_ section: GreenNode) -> Int {
336 for case .node(let heading) in section.children where heading.kind == .heading {
337 for case .token(let token) in heading.children where token.kind == .stars {
338 return token.text.count
339 }
340 }
341 return 0
342 }
343
344 // MARK: - Text helpers
345
346 func classes(_ text: Substring) -> [ClassifiedLine] {
347 splitRawLines(String(text)).map { classifyLine($0.content, alphabetical: alphabetical) }
348 }
349
350 func slice(_ text: String, _ from: Int, _ to: Int) -> Substring {
351 text[String.Index(utf16Offset: from, in: text)..<String.Index(utf16Offset: to, in: text)]
352 }
353
354 /// UTF-16 offset of the start of the line containing `offset`.
355 func lineStart(_ text: String, _ offset: Int) -> Int {
356 let utf16 = text.utf16
357 var index = utf16.index(utf16.startIndex, offsetBy: offset)
358 while index > utf16.startIndex {
359 let before = utf16.index(before: index)
360 if utf16[before] == 0x0A { break }
361 index = before
362 }
363 return utf16.distance(from: utf16.startIndex, to: index)
364 }
365
366 /// UTF-16 offset just past the newline ending the line containing `offset`.
367 func lineEnd(_ text: String, _ offset: Int) -> Int {
368 let utf16 = text.utf16
369 var index = utf16.index(utf16.startIndex, offsetBy: offset)
370 while index < utf16.endIndex {
371 let current = utf16[index]
372 index = utf16.index(after: index)
373 if current == 0x0A { break }
374 }
375 return utf16.distance(from: utf16.startIndex, to: index)
376 }
377}
378
379extension Parser {
380 /// One element of `kind` parsed from exactly `text`, or nil if `text` doesn't parse as a
381 /// single element of that kind.
382 static func reparseElement(_ kind: SyntaxKind, text: String, settings: OrgSettings) -> GreenNode? {
383 var parser = Parser(text: text, settings: settings)
384 let count = parser.lines.count
385 guard count > 0 else { return nil }
386 switch kind {
387 case .paragraph:
388 parser.paragraph(limit: count, floor: nil)
389 case .heading:
390 guard count == 1 else { return nil }
391 parser.headingLine(parser.lines[0])
392 parser.i = 1
393 case .tableRow:
394 guard count == 1 else { return nil }
395 parser.tableRow()
396 case .planning, .clock, .keyword, .affiliatedKeyword, .horizontalRule, .nodeProperty:
397 guard count == 1 else { return nil }
398 parser.single(kind)
399 case .block, .comment, .fixedWidth, .footnoteDefinition:
400 parser.element(limit: count, floor: nil)
401 default:
402 return nil
403 }
404 guard parser.i == count else { return nil }
405 let green = parser.builder.build()
406 return green.kind == kind ? green : nil
407 }
408}
409
410extension TextEdit {
411 /// The one edit between two texts: everything between their common prefix and suffix.
412 public static func between(_ old: String, _ new: String) -> [TextEdit] {
413 let a = Array(old.utf16)
414 let b = Array(new.utf16)
415 var prefix = 0
416 while prefix < a.count, prefix < b.count, a[prefix] == b[prefix] { prefix += 1 }
417 var suffix = 0
418 while suffix < a.count - prefix, suffix < b.count - prefix, a[a.count - 1 - suffix] == b[b.count - 1 - suffix] { suffix += 1 }
419 // Keep the edit on scalar boundaries.
420 while prefix > 0, (prefix < a.count && UTF16.isTrailSurrogate(a[prefix])) || (prefix < b.count && UTF16.isTrailSurrogate(b[prefix])) { prefix -= 1 }
421 while suffix > 0, suffix < a.count, UTF16.isLeadSurrogate(a[a.count - suffix - 1]) { suffix -= 1 }
422 if prefix == a.count, prefix == b.count { return [] }
423 let replacement = String(utf16CodeUnits: Array(b[prefix..<(b.count - suffix)]), count: b.count - suffix - prefix)
424 return [TextEdit(range: prefix..<(a.count - suffix), replacement: replacement)]
425 }
426
427}