docs/plans/2026-10-04-incremental-reparse.md
458 lines · 20593 bytes
1# Incremental Reparse Implementation Plan
2
3> **For agentic workers:** REQUIRED SUB-SKILL: Use superpowers:subagent-driven-development (recommended) or superpowers:executing-plans to implement this plan task-by-task. Steps use checkbox (`- [ ]`) syntax for tracking.
4
5**Goal:** Given the old tree and one `TextEdit`, produce the new tree without a full parse, always equal to a full parse of the new text.
6
7**Architecture:** Three strategies, tried in order. (1) Full parse when the edit touches a settings keyword line, or moves a block or heading boundary in a file that has settings keywords. (2) Element: when the edit sits inside one leaf element (paragraph, heading, table row, block, keyword, ...) and every line of that element keeps its class and indent, reparse just that element and copy the path from the root. (3) Sections: reparse from the top-level section before the edit until a later top-level heading still ends the reparsed run, and reuse the old top-level sections around it; top-level sections parse independently because blocks and drawers never cross a heading. A randomized differential test compares every result with a full parse.
8
9**Tech Stack:** Swift 6.2 tools, Swift Testing, Foundation only.
10
11**Spec:** `docs/design.md`, "Incremental reparse".
12
13## Global Constraints
14
15- The result always equals a full parse of the new text (green trees compare equal).
16- Edits use UTF-16 ranges on unicode scalar boundaries; `TextEdit.apply` works on scalars so an edit between `\r` and `\n` stays exact.
17- Gate: 0 mismatches over 100,000 random edits in a release build (`ORGSTAR_FUZZ_EDITS=100000 swift test -c release --filter incrementalEqualsFull`).
18
19## Deviation from the spec
20
21The spec reparses structural edits from the innermost enclosing section. This plan uses top-level sections: simpler, provably independent, and enough for the differential gate. A file that is one large top-level section reparses whole on a structural edit; the performance plan measures that case and narrows the window if the 16 ms gate needs it.
22
23## File structure
24
25| File | Responsibility |
26| --- | --- |
27| `Sources/OrgCore/Parser/Parser.swift` | `Parser(text:settings:)` to parse part of a file with known settings |
28| `Sources/OrgCore/Parser/Incremental.swift` | `TextEdit`, `OrgParser.reparse`, strategies, `Parser.reparseElement` |
29| `Tests/OrgCoreTests/IncrementalTests.swift` | Strategy tests and the differential fuzz test |
30
31---
32
33### Task 1: Incremental reparse
34
35**Files:**
36- Modify: `Sources/OrgCore/Parser/Parser.swift`
37- Create: `Sources/OrgCore/Parser/Incremental.swift`
38- Test: `Tests/OrgCoreTests/IncrementalTests.swift`
39
40**Interfaces:**
41- Consumes: `Parser`, `splitRawLines`, `classifyLine`, `SyntaxNode`, `GreenNode`, `randomDocument`/`fragments`/`SeededGenerator` from `RoundTripTests.swift`.
42- Produces: `TextEdit(range:replacement:)` with `apply(to:)`; `OrgParser.reparse(_:oldText:edit:defaults:) -> OrgTree`; internal `OrgParser.reparseWithStrategy` returning `(tree, ReparseStrategy)` with `.element`, `.sections`, `.full`; `Parser(text:settings:)`; `Parser.reparseElement(_:text:settings:) -> GreenNode?`.
43
44- [ ] **Step 1: Write the failing tests**
45
46```swift
47import Foundation
48import Testing
49@testable import OrgCore
50
51/// Reparses `text` after an edit, checks the result against a full parse, and returns the
52/// strategy used.
53@discardableResult
54func checkReparse(_ text: String, _ range: Range<Int>, _ replacement: String) -> ReparseStrategy {
55 let old = OrgParser.parse(text)
56 let edit = TextEdit(range: range, replacement: replacement)
57 let result = OrgParser.reparseWithStrategy(old, oldText: text, edit: edit)
58 let expected = OrgParser.parse(edit.apply(to: text))
59 #expect(result.tree.text == expected.text)
60 #expect(result.tree.green == expected.green)
61 return result.strategy
62}
63
64/// UTF-16 offsets of every unicode scalar boundary.
65func scalarOffsets(_ text: String) -> [Int] {
66 var offsets = [0]
67 var offset = 0
68 for scalar in text.unicodeScalars {
69 offset += scalar.utf16.count
70 offsets.append(offset)
71 }
72 return offsets
73}
74
75struct IncrementalTests {
76 @Test func applyKeepsCRLFHalves() {
77 #expect(TextEdit(range: 1..<1, replacement: "x").apply(to: "\r\n") == "\rx\n")
78 #expect(TextEdit(range: 1..<3, replacement: "").apply(to: "a😀b") == "ab")
79 }
80
81 @Test func typingInAParagraphReparsesOneElement() {
82 #expect(checkReparse("* a\nhello world\n* b\n", 10..<10, "big ") == .element)
83 #expect(checkReparse("- item *one*\n - two\n", 8..<8, "x") == .element)
84 }
85
86 @Test func typingAtTheStartOfAnItemParagraph() {
87 #expect(checkReparse(" >\n1. one", 6..<6, " ") != .element)
88 }
89
90 @Test func changingATodoKeywordReparsesOneElement() {
91 #expect(checkReparse("* TODO a\nbody\n", 2..<6, "DONE") == .element)
92 }
93
94 @Test func newHeadingReparsesSections() {
95 #expect(checkReparse("* a\nx\ny\n* b\n", 6..<6, "* c\n") == .sections)
96 }
97
98 @Test func joiningParagraphsReparsesSections() {
99 #expect(checkReparse("a\n\nb\n", 1..<2, "") == .sections)
100 }
101
102 @Test func runGrowsUntilAHeadingEndsIt() {
103 #expect(checkReparse("** a\n** b\n* c\n", 0..<0, "* x\n") == .sections)
104 }
105
106 @Test func settingsLineForcesFullParse() {
107 #expect(checkReparse("#+TODO: A | B\n* A x\n", 8..<9, "C") == .full)
108 }
109
110 @Test func exposingAKeywordInsideABlockForcesFullParse() {
111 let text = "#+begin_example\n#+TODO: X\n#+end_example\n* X a\n"
112 #expect(checkReparse(text, 26..<40, "") == .full)
113 }
114
115 @Test func editsAtTheEdges() {
116 checkReparse("", 0..<0, "* a\n")
117 checkReparse("* a\n", 0..<4, "")
118 checkReparse("* a", 3..<3, "\n")
119 checkReparse("a\r\nb\r\n", 1..<1, "x")
120 }
121
122 /// Set `ORGSTAR_FUZZ_EDITS` to run more (the phase 1 gate is 100,000 in a release build) and
123 /// `ORGSTAR_FUZZ_SEED` to try another sequence.
124 @Test func incrementalEqualsFull() {
125 let environment = ProcessInfo.processInfo.environment
126 var rng = SeededGenerator(state: UInt64(environment["ORGSTAR_FUZZ_SEED"] ?? "") ?? 20261005)
127 let count = Int(environment["ORGSTAR_FUZZ_EDITS"] ?? "") ?? 3_000
128 let small = ["a", " ", "*", "/", "=", "[", "]", "<", ">", "-", ":", "|", "#", "+", "\n", "\r\n", "😀", "é"]
129 for n in 0..<count {
130 let text = randomDocument(&rng)
131 let offsets = scalarOffsets(text)
132 let a = offsets.randomElement(using: &rng)!
133 let later = offsets.filter { $0 >= a && $0 <= a + 12 }
134 let b = Bool.random(using: &rng) ? a : later.randomElement(using: &rng)!
135 let replacement: String
136 if Int.random(in: 0..<10, using: &rng) < 7 {
137 replacement = (0..<Int.random(in: 0...2, using: &rng)).map { _ in small.randomElement(using: &rng)! }.joined()
138 } else {
139 replacement = fragments.randomElement(using: &rng)! + (Bool.random(using: &rng) ? "\n" : "")
140 }
141 let old = OrgParser.parse(text)
142 let edit = TextEdit(range: a..<b, replacement: replacement)
143 let tree = OrgParser.reparse(old, oldText: text, edit: edit)
144 let expected = OrgParser.parse(edit.apply(to: text))
145 #expect(tree.green == expected.green, "edit \(n): \(a)..<\(b) \(replacement.debugDescription) in \(text.debugDescription)")
146 }
147 }
148}
149```
150
151- [ ] **Step 2: Run to verify failure**
152
153Run: `swift test --filter IncrementalTests`
154Expected: build failure, `cannot find 'TextEdit' in scope`.
155
156- [ ] **Step 3: Let the parser take known settings**
157
158```diff
159@@ -16,10 +16,25 @@ struct Parser {
160 var i = 0
161
162 init(text: String, defaults: OrgSettings) {
163- lines = splitRawLines(text)
164- info = lines.map { classifyLine($0.content) }
165- blockEnds = Parser.matchEnds(info)
166- settings = SettingsScanner.scan(lines: lines, info: info, blockEnds: blockEnds, defaults: defaults)
167+ let lines = splitRawLines(text)
168+ let info = lines.map { classifyLine($0.content) }
169+ let ends = Parser.matchEnds(info)
170+ let settings = SettingsScanner.scan(lines: lines, info: info, blockEnds: ends, defaults: defaults)
171+ self.init(lines: lines, info: info, blockEnds: ends, settings: settings)
172+ }
173+
174+ /// Parses part of a document with the settings already read from the whole file.
175+ init(text: String, settings: OrgSettings) {
176+ let lines = splitRawLines(text)
177+ let info = lines.map { classifyLine($0.content) }
178+ self.init(lines: lines, info: info, blockEnds: Parser.matchEnds(info), settings: settings)
179+ }
180+
181+ private init(lines: [RawLine], info: [ClassifiedLine], blockEnds: [Int: Int], settings: OrgSettings) {
182+ self.lines = lines
183+ self.info = info
184+ self.blockEnds = blockEnds
185+ self.settings = settings
186 }
187
188 static func matchEnds(_ info: [ClassifiedLine]) -> [Int: Int] {
189```
190
191- [ ] **Step 4: Implement `Incremental.swift`**
192
193```swift
194import Foundation
195
196public struct TextEdit: Sendable, Equatable {
197 /// UTF-16 range in the old text, on unicode scalar boundaries.
198 public let range: Range<Int>
199 public let replacement: String
200
201 public init(range: Range<Int>, replacement: String) {
202 self.range = range
203 self.replacement = replacement
204 }
205
206 /// Works on unicode scalars, so an edit between "\r" and "\n" stays exact.
207 public func apply(to text: String) -> String {
208 let scalars = text.unicodeScalars
209 let start = String.Index(utf16Offset: range.lowerBound, in: text)
210 let end = String.Index(utf16Offset: range.upperBound, in: text)
211 return String(scalars[..<start]) + replacement + String(scalars[end...])
212 }
213}
214
215enum ReparseStrategy: Equatable {
216 /// One element reparsed in place; everything else reused.
217 case element
218 /// A run of top-level sections reparsed; the sections before and after reused.
219 case sections
220 case full
221}
222
223extension OrgParser {
224 /// The tree for `edit.apply(to: oldText)`, reusing as much of `old` as stays valid. Always
225 /// equal to a full parse of the new text.
226 public static func reparse(_ old: OrgTree, oldText: String, edit: TextEdit, defaults: OrgSettings = .default) -> OrgTree {
227 reparseWithStrategy(old, oldText: oldText, edit: edit, defaults: defaults).tree
228 }
229
230 static func reparseWithStrategy(
231 _ old: OrgTree, oldText: String, edit: TextEdit, defaults: OrgSettings = .default
232 ) -> (tree: OrgTree, strategy: ReparseStrategy) {
233 let newText = edit.apply(to: oldText)
234 let context = EditContext(oldText: oldText, newText: newText, edit: edit)
235 if context.touchesSettings() { return (parse(newText, defaults: defaults), .full) }
236 if let tree = context.reparseElement(old) { return (tree, .element) }
237 if let tree = context.reparseSections(old) { return (tree, .sections) }
238 return (parse(newText, defaults: defaults), .full)
239 }
240}
241
242private struct EditContext {
243 let oldText: String
244 let newText: String
245 let edit: TextEdit
246 /// Change in UTF-16 length.
247 var delta: Int { edit.replacement.utf16.count - edit.range.count }
248
249 static let settingsKeys: Set<String> = ["TODO", "SEQ_TODO", "TYP_TODO", "PRIORITIES"]
250
251 /// Elements that parse the same in isolation as in place, as long as their lines keep
252 /// their classes.
253 static let leafKinds: Set<SyntaxKind> = [
254 .paragraph, .heading, .tableRow, .planning, .clock, .keyword, .affiliatedKeyword, .horizontalRule,
255 .nodeProperty, .block, .comment, .fixedWidth, .footnoteDefinition,
256 ]
257
258 /// File settings must be read again when an edited line is a settings keyword, or when it
259 /// moves a block or heading boundary in a file that has settings keywords: that can hide or
260 /// expose a keyword inside a block.
261 func touchesSettings() -> Bool {
262 let start = lineStart(oldText, edit.range.lowerBound)
263 let oldLines = classes(slice(oldText, start, lineEnd(oldText, edit.range.upperBound)))
264 let newLines = classes(slice(newText, start, lineEnd(newText, edit.range.lowerBound + edit.replacement.utf16.count)))
265 var movesBoundary = false
266 for line in oldLines + newLines {
267 switch line.cls {
268 case .keyword(let key) where Self.settingsKeys.contains(key):
269 return true
270 case .blockBegin, .blockEnd, .dynamicBegin, .dynamicEnd, .heading:
271 movesBoundary = true
272 default:
273 break
274 }
275 }
276 return movesBoundary && Self.settingsKeys.contains { newText.range(of: "#+\($0):", options: .caseInsensitive) != nil }
277 }
278
279 // MARK: - Element
280
281 func reparseElement(_ old: OrgTree) -> OrgTree? {
282 guard let leaf = leaf(in: old.root) else { return nil }
283 let start = lineStart(oldText, leaf.range.lowerBound)
284 // An element that starts mid-line (an item's paragraph) follows tokens that would absorb
285 // whitespace typed at its start.
286 guard start == leaf.range.lowerBound || edit.range.lowerBound > leaf.range.lowerBound else { return nil }
287 let oldEnd = leaf.range.upperBound
288 let newEnd = oldEnd + delta
289 let newLength = newText.utf16.count
290 guard newEnd > leaf.range.lowerBound, newEnd <= newLength else { return nil }
291 // The element must still end at a line end.
292 if newEnd < newLength {
293 let utf16 = newText.utf16
294 guard utf16[utf16.index(utf16.startIndex, offsetBy: newEnd - 1)] == 0x0A else { return nil }
295 }
296 let oldClasses = classes(slice(oldText, start, oldEnd))
297 let newClasses = classes(slice(newText, start, newEnd))
298 guard oldClasses.count == newClasses.count,
299 zip(oldClasses, newClasses).allSatisfy({ $0.cls == $1.cls && $0.indent == $1.indent }) else { return nil }
300 let text = String(slice(newText, leaf.range.lowerBound, newEnd))
301 guard let green = Parser.reparseElement(leaf.kind, text: text, settings: old.settings) else { return nil }
302 return OrgTree(green: replacing(leaf, with: green), settings: old.settings)
303 }
304
305 /// The outermost leaf element containing the edit.
306 func leaf(in root: SyntaxNode) -> SyntaxNode? {
307 let range = edit.range
308 var current = root
309 while let child = current.children.first(where: {
310 $0.range.lowerBound <= range.lowerBound && range.lowerBound < $0.range.upperBound
311 && range.upperBound <= $0.range.upperBound
312 }) {
313 if Self.leafKinds.contains(child.kind) { return child }
314 current = child
315 }
316 return nil
317 }
318
319 /// Copies the path from the root down to `target`, swapping in `green`.
320 func replacing(_ target: SyntaxNode, with green: GreenNode) -> GreenNode {
321 var node = target
322 var replacement = green
323 while let parent = node.parent {
324 var children = parent.green.children
325 let index = children.firstIndex {
326 if case .node(let child) = $0 { return child === node.green }
327 return false
328 }!
329 children[index] = .node(replacement)
330 replacement = GreenNode(kind: parent.kind, children: children)
331 node = parent
332 }
333 return replacement
334 }
335
336 // MARK: - Sections
337
338 /// Reparses from the top-level section before the edit up to the first later top-level
339 /// heading that still ends the reparsed run, then reuses the old sections from there.
340 /// Top-level sections parse independently: blocks and drawers never cross a heading.
341 func reparseSections(_ old: OrgTree) -> OrgTree? {
342 let units = old.root.children
343 guard !units.isEmpty else { return nil }
344 let anchor = max(0, lineStart(oldText, edit.range.lowerBound) - 1)
345 guard let startIndex = units.firstIndex(where: { $0.range.contains(anchor) }) else { return nil }
346 let start = units[startIndex].range.lowerBound
347 var endIndex = units.firstIndex { $0.range.lowerBound > edit.range.upperBound } ?? units.count
348 let newLength = newText.utf16.count
349 while true {
350 let newEnd = endIndex < units.count ? units[endIndex].range.lowerBound + delta : newLength
351 var parser = Parser(text: String(slice(newText, start, newEnd)), settings: old.settings)
352 let window = parser.run().green
353 if endIndex == units.count || endsRun(window, next: units[endIndex].green) {
354 let children = units[..<startIndex].map { GreenElement.node($0.green) }
355 + window.children
356 + units[endIndex...].map { GreenElement.node($0.green) }
357 return OrgTree(green: GreenNode(kind: .document, children: children), settings: old.settings)
358 }
359 endIndex += 1
360 }
361 }
362
363 /// Whether the heading of `next` ends the last section of the reparsed window.
364 func endsRun(_ window: GreenNode, next: GreenNode) -> Bool {
365 guard case .node(let last)? = window.children.last, last.kind == .section else { return true }
366 return headingLevel(next) <= headingLevel(last)
367 }
368
369 func headingLevel(_ section: GreenNode) -> Int {
370 for case .node(let heading) in section.children where heading.kind == .heading {
371 for case .token(let token) in heading.children where token.kind == .stars {
372 return token.text.count
373 }
374 }
375 return 0
376 }
377
378 // MARK: - Text helpers
379
380 func classes(_ text: Substring) -> [ClassifiedLine] {
381 splitRawLines(String(text)).map { classifyLine($0.content) }
382 }
383
384 func slice(_ text: String, _ from: Int, _ to: Int) -> Substring {
385 text[String.Index(utf16Offset: from, in: text)..<String.Index(utf16Offset: to, in: text)]
386 }
387
388 /// UTF-16 offset of the start of the line containing `offset`.
389 func lineStart(_ text: String, _ offset: Int) -> Int {
390 let utf16 = text.utf16
391 var index = utf16.index(utf16.startIndex, offsetBy: offset)
392 while index > utf16.startIndex {
393 let before = utf16.index(before: index)
394 if utf16[before] == 0x0A { break }
395 index = before
396 }
397 return utf16.distance(from: utf16.startIndex, to: index)
398 }
399
400 /// UTF-16 offset just past the newline ending the line containing `offset`.
401 func lineEnd(_ text: String, _ offset: Int) -> Int {
402 let utf16 = text.utf16
403 var index = utf16.index(utf16.startIndex, offsetBy: offset)
404 while index < utf16.endIndex {
405 let current = utf16[index]
406 index = utf16.index(after: index)
407 if current == 0x0A { break }
408 }
409 return utf16.distance(from: utf16.startIndex, to: index)
410 }
411}
412
413extension Parser {
414 /// One element of `kind` parsed from exactly `text`, or nil if `text` doesn't parse as a
415 /// single element of that kind.
416 static func reparseElement(_ kind: SyntaxKind, text: String, settings: OrgSettings) -> GreenNode? {
417 var parser = Parser(text: text, settings: settings)
418 let count = parser.lines.count
419 guard count > 0 else { return nil }
420 switch kind {
421 case .paragraph:
422 parser.paragraph(limit: count, floor: nil)
423 case .heading:
424 guard count == 1 else { return nil }
425 parser.headingLine(parser.lines[0])
426 parser.i = 1
427 case .tableRow:
428 guard count == 1 else { return nil }
429 parser.tableRow()
430 case .planning, .clock, .keyword, .affiliatedKeyword, .horizontalRule, .nodeProperty:
431 guard count == 1 else { return nil }
432 parser.single(kind)
433 case .block, .comment, .fixedWidth, .footnoteDefinition:
434 parser.element(limit: count, floor: nil)
435 default:
436 return nil
437 }
438 guard parser.i == count else { return nil }
439 let green = parser.builder.build()
440 return green.kind == kind ? green : nil
441 }
442}
443```
444
445- [ ] **Step 5: Run all tests, then the gate**
446
447Run: `swift test`
448Expected: all pass.
449
450Run: `ORGSTAR_FUZZ_EDITS=100000 swift test -c release --filter incrementalEqualsFull`, and again with `ORGSTAR_FUZZ_SEED=1`, `2`, `3`.
451Expected: pass. A failure prints the edit and the document; reduce it to a unit test before fixing.
452
453- [ ] **Step 6: Commit**
454
455```bash
456git add Sources Tests
457git commit -m "Add incremental reparse"
458```