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