krz/orgstar

Incremental reparse !4

merged merged by cmc on 2026-10-04 23:59 UTC · krz/orgstar:phase1-incremental-reparse into main

4 files changed, +828 −4

Layout: unified · split

Sources/OrgCore/Parser/Incremental.swift added +249
@@ -0,0 +1,249 @@
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 top-level sections reparsed; the sections before and after reused.
26 case sections
27 case full
28}
29
30extension OrgParser {
31 /// The tree for `edit.apply(to: oldText)`, reusing as much of `old` as stays valid. Always
32 /// equal to a full parse of the new text.
33 public static func reparse(_ old: OrgTree, oldText: String, edit: TextEdit, defaults: OrgSettings = .default) -> OrgTree {
34 reparseWithStrategy(old, oldText: oldText, edit: edit, defaults: defaults).tree
35 }
36
37 static func reparseWithStrategy(
38 _ old: OrgTree, oldText: String, edit: TextEdit, defaults: OrgSettings = .default
39 ) -> (tree: OrgTree, strategy: ReparseStrategy) {
40 let newText = edit.apply(to: oldText)
41 let context = EditContext(oldText: oldText, newText: newText, edit: edit)
42 if context.touchesSettings() { return (parse(newText, defaults: defaults), .full) }
43 if let tree = context.reparseElement(old) { return (tree, .element) }
44 if let tree = context.reparseSections(old) { return (tree, .sections) }
45 return (parse(newText, defaults: defaults), .full)
46 }
47}
48
49private struct EditContext {
50 let oldText: String
51 let newText: String
52 let edit: TextEdit
53 /// Change in UTF-16 length.
54 var delta: Int { edit.replacement.utf16.count - edit.range.count }
55
56 static let settingsKeys: Set<String> = ["TODO", "SEQ_TODO", "TYP_TODO", "PRIORITIES"]
57
58 /// Elements that parse the same in isolation as in place, as long as their lines keep
59 /// their classes.
60 static let leafKinds: Set<SyntaxKind> = [
61 .paragraph, .heading, .tableRow, .planning, .clock, .keyword, .affiliatedKeyword, .horizontalRule,
62 .nodeProperty, .block, .comment, .fixedWidth, .footnoteDefinition,
63 ]
64
65 /// File settings must be read again when an edited line is a settings keyword, or when it
66 /// moves a block or heading boundary in a file that has settings keywords: that can hide or
67 /// expose a keyword inside a block.
68 func touchesSettings() -> Bool {
69 let start = lineStart(oldText, edit.range.lowerBound)
70 let oldLines = classes(slice(oldText, start, lineEnd(oldText, edit.range.upperBound)))
71 let newLines = classes(slice(newText, start, lineEnd(newText, edit.range.lowerBound + edit.replacement.utf16.count)))
72 var movesBoundary = false
73 for line in oldLines + newLines {
74 switch line.cls {
75 case .keyword(let key) where Self.settingsKeys.contains(key):
76 return true
77 case .blockBegin, .blockEnd, .dynamicBegin, .dynamicEnd, .heading:
78 movesBoundary = true
79 default:
80 break
81 }
82 }
83 return movesBoundary && Self.settingsKeys.contains { newText.range(of: "#+\($0):", options: .caseInsensitive) != nil }
84 }
85
86 // MARK: - Element
87
88 func reparseElement(_ old: OrgTree) -> OrgTree? {
89 guard let leaf = leaf(in: old.root) else { return nil }
90 let start = lineStart(oldText, leaf.range.lowerBound)
91 // An element that starts mid-line (an item's paragraph) follows tokens that would absorb
92 // whitespace typed at its start.
93 guard start == leaf.range.lowerBound || edit.range.lowerBound > leaf.range.lowerBound else { return nil }
94 let oldEnd = leaf.range.upperBound
95 let newEnd = oldEnd + delta
96 let newLength = newText.utf16.count
97 guard newEnd > leaf.range.lowerBound, newEnd <= newLength else { return nil }
98 // The element must still end at a line end.
99 if newEnd < newLength {
100 let utf16 = newText.utf16
101 guard utf16[utf16.index(utf16.startIndex, offsetBy: newEnd - 1)] == 0x0A else { return nil }
102 }
103 let oldClasses = classes(slice(oldText, start, oldEnd))
104 let newClasses = classes(slice(newText, start, newEnd))
105 guard oldClasses.count == newClasses.count,
106 zip(oldClasses, newClasses).allSatisfy({ $0.cls == $1.cls && $0.indent == $1.indent }) else { return nil }
107 let text = String(slice(newText, leaf.range.lowerBound, newEnd))
108 guard let green = Parser.reparseElement(leaf.kind, text: text, settings: old.settings) else { return nil }
109 return OrgTree(green: replacing(leaf, with: green), settings: old.settings)
110 }
111
112 /// The outermost leaf element containing the edit.
113 func leaf(in root: SyntaxNode) -> SyntaxNode? {
114 let range = edit.range
115 var current = root
116 while let child = current.children.first(where: {
117 $0.range.lowerBound <= range.lowerBound && range.lowerBound < $0.range.upperBound
118 && range.upperBound <= $0.range.upperBound
119 }) {
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: - Sections
144
145 /// Reparses from the top-level section before the edit up to the first later top-level
146 /// heading that still ends the reparsed run, then reuses the old sections from there.
147 /// Top-level sections parse independently: blocks and drawers never cross a heading.
148 func reparseSections(_ old: OrgTree) -> OrgTree? {
149 let units = old.root.children
150 guard !units.isEmpty else { return nil }
151 let anchor = max(0, lineStart(oldText, edit.range.lowerBound) - 1)
152 guard let startIndex = units.firstIndex(where: { $0.range.contains(anchor) }) else { return nil }
153 let start = units[startIndex].range.lowerBound
154 var endIndex = units.firstIndex { $0.range.lowerBound > edit.range.upperBound } ?? units.count
155 let newLength = newText.utf16.count
156 while true {
157 let newEnd = endIndex < units.count ? units[endIndex].range.lowerBound + delta : newLength
158 var parser = Parser(text: String(slice(newText, start, newEnd)), settings: old.settings)
159 let window = parser.run().green
160 if endIndex == units.count || endsRun(window, next: units[endIndex].green) {
161 let children = units[..<startIndex].map { GreenElement.node($0.green) }
162 + window.children
163 + units[endIndex...].map { GreenElement.node($0.green) }
164 return OrgTree(green: GreenNode(kind: .document, children: children), settings: old.settings)
165 }
166 endIndex += 1
167 }
168 }
169
170 /// Whether the heading of `next` ends the last section of the reparsed window.
171 func endsRun(_ window: GreenNode, next: GreenNode) -> Bool {
172 guard case .node(let last)? = window.children.last, last.kind == .section else { return true }
173 return headingLevel(next) <= headingLevel(last)
174 }
175
176 func headingLevel(_ section: GreenNode) -> Int {
177 for case .node(let heading) in section.children where heading.kind == .heading {
178 for case .token(let token) in heading.children where token.kind == .stars {
179 return token.text.count
180 }
181 }
182 return 0
183 }
184
185 // MARK: - Text helpers
186
187 func classes(_ text: Substring) -> [ClassifiedLine] {
188 splitRawLines(String(text)).map { classifyLine($0.content) }
189 }
190
191 func slice(_ text: String, _ from: Int, _ to: Int) -> Substring {
192 text[String.Index(utf16Offset: from, in: text)..<String.Index(utf16Offset: to, in: text)]
193 }
194
195 /// UTF-16 offset of the start of the line containing `offset`.
196 func lineStart(_ text: String, _ offset: Int) -> Int {
197 let utf16 = text.utf16
198 var index = utf16.index(utf16.startIndex, offsetBy: offset)
199 while index > utf16.startIndex {
200 let before = utf16.index(before: index)
201 if utf16[before] == 0x0A { break }
202 index = before
203 }
204 return utf16.distance(from: utf16.startIndex, to: index)
205 }
206
207 /// UTF-16 offset just past the newline ending the line containing `offset`.
208 func lineEnd(_ text: String, _ offset: Int) -> Int {
209 let utf16 = text.utf16
210 var index = utf16.index(utf16.startIndex, offsetBy: offset)
211 while index < utf16.endIndex {
212 let current = utf16[index]
213 index = utf16.index(after: index)
214 if current == 0x0A { break }
215 }
216 return utf16.distance(from: utf16.startIndex, to: index)
217 }
218}
219
220extension Parser {
221 /// One element of `kind` parsed from exactly `text`, or nil if `text` doesn't parse as a
222 /// single element of that kind.
223 static func reparseElement(_ kind: SyntaxKind, text: String, settings: OrgSettings) -> GreenNode? {
224 var parser = Parser(text: text, settings: settings)
225 let count = parser.lines.count
226 guard count > 0 else { return nil }
227 switch kind {
228 case .paragraph:
229 parser.paragraph(limit: count, floor: nil)
230 case .heading:
231 guard count == 1 else { return nil }
232 parser.headingLine(parser.lines[0])
233 parser.i = 1
234 case .tableRow:
235 guard count == 1 else { return nil }
236 parser.tableRow()
237 case .planning, .clock, .keyword, .affiliatedKeyword, .horizontalRule, .nodeProperty:
238 guard count == 1 else { return nil }
239 parser.single(kind)
240 case .block, .comment, .fixedWidth, .footnoteDefinition:
241 parser.element(limit: count, floor: nil)
242 default:
243 return nil
244 }
245 guard parser.i == count else { return nil }
246 let green = parser.builder.build()
247 return green.kind == kind ? green : nil
248 }
249}
Sources/OrgCore/Parser/Parser.swift +19 −4
@@ -16,10 +16,25 @@ struct Parser {
16 var i = 0 16 var i = 0
17 17
18 init(text: String, defaults: OrgSettings) { 18 init(text: String, defaults: OrgSettings) {
19 lines = splitRawLines(text) 19 let lines = splitRawLines(text)
20 info = lines.map { classifyLine($0.content) } 20 let info = lines.map { classifyLine($0.content) }
21 blockEnds = Parser.matchEnds(info) 21 let ends = Parser.matchEnds(info)
22 settings = SettingsScanner.scan(lines: lines, info: info, blockEnds: blockEnds, defaults: defaults) 22 let settings = SettingsScanner.scan(lines: lines, info: info, blockEnds: ends, defaults: defaults)
23 self.init(lines: lines, info: info, blockEnds: ends, settings: settings)
24 }
25
26 /// Parses part of a document with the settings already read from the whole file.
27 init(text: String, settings: OrgSettings) {
28 let lines = splitRawLines(text)
29 let info = lines.map { classifyLine($0.content) }
30 self.init(lines: lines, info: info, blockEnds: Parser.matchEnds(info), settings: settings)
31 }
32
33 private init(lines: [RawLine], info: [ClassifiedLine], blockEnds: [Int: Int], settings: OrgSettings) {
34 self.lines = lines
35 self.info = info
36 self.blockEnds = blockEnds
37 self.settings = settings
23 } 38 }
24 39
25 static func matchEnds(_ info: [ClassifiedLine]) -> [Int: Int] { 40 static func matchEnds(_ info: [ClassifiedLine]) -> [Int: Int] {
Tests/OrgCoreTests/IncrementalTests.swift added +102
@@ -0,0 +1,102 @@
1import Foundation
2import Testing
3@testable import OrgCore
4
5/// Reparses `text` after an edit, checks the result against a full parse, and returns the
6/// strategy used.
7@discardableResult
8func checkReparse(_ text: String, _ range: Range<Int>, _ replacement: String) -> ReparseStrategy {
9 let old = OrgParser.parse(text)
10 let edit = TextEdit(range: range, replacement: replacement)
11 let result = OrgParser.reparseWithStrategy(old, oldText: text, edit: edit)
12 let expected = OrgParser.parse(edit.apply(to: text))
13 #expect(result.tree.text == expected.text)
14 #expect(result.tree.green == expected.green)
15 return result.strategy
16}
17
18/// UTF-16 offsets of every unicode scalar boundary.
19func scalarOffsets(_ text: String) -> [Int] {
20 var offsets = [0]
21 var offset = 0
22 for scalar in text.unicodeScalars {
23 offset += scalar.utf16.count
24 offsets.append(offset)
25 }
26 return offsets
27}
28
29struct IncrementalTests {
30 @Test func applyKeepsCRLFHalves() {
31 #expect(TextEdit(range: 1..<1, replacement: "x").apply(to: "\r\n") == "\rx\n")
32 #expect(TextEdit(range: 1..<3, replacement: "").apply(to: "a😀b") == "ab")
33 }
34
35 @Test func typingInAParagraphReparsesOneElement() {
36 #expect(checkReparse("* a\nhello world\n* b\n", 10..<10, "big ") == .element)
37 #expect(checkReparse("- item *one*\n - two\n", 8..<8, "x") == .element)
38 }
39
40 @Test func typingAtTheStartOfAnItemParagraph() {
41 #expect(checkReparse(" >\n1. one", 6..<6, " ") != .element)
42 }
43
44 @Test func changingATodoKeywordReparsesOneElement() {
45 #expect(checkReparse("* TODO a\nbody\n", 2..<6, "DONE") == .element)
46 }
47
48 @Test func newHeadingReparsesSections() {
49 #expect(checkReparse("* a\nx\ny\n* b\n", 6..<6, "* c\n") == .sections)
50 }
51
52 @Test func joiningParagraphsReparsesSections() {
53 #expect(checkReparse("a\n\nb\n", 1..<2, "") == .sections)
54 }
55
56 @Test func runGrowsUntilAHeadingEndsIt() {
57 #expect(checkReparse("** a\n** b\n* c\n", 0..<0, "* x\n") == .sections)
58 }
59
60 @Test func settingsLineForcesFullParse() {
61 #expect(checkReparse("#+TODO: A | B\n* A x\n", 8..<9, "C") == .full)
62 }
63
64 @Test func exposingAKeywordInsideABlockForcesFullParse() {
65 let text = "#+begin_example\n#+TODO: X\n#+end_example\n* X a\n"
66 #expect(checkReparse(text, 26..<40, "") == .full)
67 }
68
69 @Test func editsAtTheEdges() {
70 checkReparse("", 0..<0, "* a\n")
71 checkReparse("* a\n", 0..<4, "")
72 checkReparse("* a", 3..<3, "\n")
73 checkReparse("a\r\nb\r\n", 1..<1, "x")
74 }
75
76 /// Set `ORGSTAR_FUZZ_EDITS` to run more (the phase 1 gate is 100,000 in a release build) and
77 /// `ORGSTAR_FUZZ_SEED` to try another sequence.
78 @Test func incrementalEqualsFull() {
79 let environment = ProcessInfo.processInfo.environment
80 var rng = SeededGenerator(state: UInt64(environment["ORGSTAR_FUZZ_SEED"] ?? "") ?? 20261005)
81 let count = Int(environment["ORGSTAR_FUZZ_EDITS"] ?? "") ?? 3_000
82 let small = ["a", " ", "*", "/", "=", "[", "]", "<", ">", "-", ":", "|", "#", "+", "\n", "\r\n", "😀", "é"]
83 for n in 0..<count {
84 let text = randomDocument(&rng)
85 let offsets = scalarOffsets(text)
86 let a = offsets.randomElement(using: &rng)!
87 let later = offsets.filter { $0 >= a && $0 <= a + 12 }
88 let b = Bool.random(using: &rng) ? a : later.randomElement(using: &rng)!
89 let replacement: String
90 if Int.random(in: 0..<10, using: &rng) < 7 {
91 replacement = (0..<Int.random(in: 0...2, using: &rng)).map { _ in small.randomElement(using: &rng)! }.joined()
92 } else {
93 replacement = fragments.randomElement(using: &rng)! + (Bool.random(using: &rng) ? "\n" : "")
94 }
95 let old = OrgParser.parse(text)
96 let edit = TextEdit(range: a..<b, replacement: replacement)
97 let tree = OrgParser.reparse(old, oldText: text, edit: edit)
98 let expected = OrgParser.parse(edit.apply(to: text))
99 #expect(tree.green == expected.green, "edit \(n): \(a)..<\(b) \(replacement.debugDescription) in \(text.debugDescription)")
100 }
101 }
102}
docs/plans/2026-10-04-incremental-reparse.md added +458
@@ -0,0 +1,458 @@
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```