Sources/OrgCore/Commands/EmacsBuffer.swift
500 lines · 19691 bytes
1import Foundation
2
3/// A whole-text buffer with Emacs's point and marker rules, for porting org commands that
4/// edit several lines. Offsets are UTF-16, as everywhere in `OrgCore`.
5///
6/// Inserting at point moves point past the text; a marker at the insertion point stays before
7/// it unless the insertion is `insertBeforeMarkers`. Deleting a range moves positions inside
8/// it to its start. `saveExcursion` restores point from a marker, as Emacs does.
9final class EmacsBuffer {
10 final class Marker {
11 var position: Int
12 /// Inserting at the marker moves it past the text, as `set-marker-insertion-type` t.
13 let advances: Bool
14 init(_ position: Int, advances: Bool = false) {
15 self.position = position
16 self.advances = advances
17 }
18 }
19
20 struct UserError: Error {
21 let message: String
22 }
23
24 private(set) var text: NSMutableString
25 var point: Int
26 private var markers: [Marker] = []
27 let settings: OrgSettings
28 private var visibleCache: [String: VisibleLine] = [:]
29 /// Groups of the last successful match, as Emacs's match data.
30 var lastMatch: [Range<Int>?] = []
31 /// The clock and calendar commands see.
32 var now = Date()
33 var calendar = Calendar.current
34 /// `org-last-inserted-timestamp`.
35 var lastInsertedTimestamp: String?
36
37 let options: EditingOptions
38
39 init(_ text: String, point: Int, settings: OrgSettings = .default, options: EditingOptions = .org) {
40 self.text = NSMutableString(string: text)
41 self.point = point
42 self.settings = settings
43 self.options = options
44 unchangedPrefix = self.text.length
45 unchangedSuffix = self.text.length
46 }
47
48 /// Lengths of the start and end of the text no edit has touched, so the result's diff can
49 /// look only between them.
50 private(set) var unchangedPrefix: Int
51 private(set) var unchangedSuffix: Int
52
53 private func touched(_ range: Range<Int>) {
54 unchangedPrefix = min(unchangedPrefix, range.lowerBound)
55 unchangedSuffix = min(unchangedSuffix, length - range.upperBound)
56 }
57
58 /// The text as a `String` backed by an immutable `NSString`, copied once per change rather
59 /// than per regexp search; regexps read it without converting.
60 var string: String {
61 if let cachedString { return cachedString as String }
62 let copy = text.copy() as! NSString
63 cachedString = copy
64 return copy as String
65 }
66
67 private var cachedString: NSString?
68 var length: Int { text.length }
69
70 func character(at offset: Int) -> unichar? {
71 offset >= 0 && offset < length ? text.character(at: offset) : nil
72 }
73
74 static let newline = unichar(10)
75
76 // MARK: - Markers
77
78 func marker(_ position: Int, advances: Bool = false) -> Marker {
79 let marker = Marker(position, advances: advances)
80 markers.append(marker)
81 return marker
82 }
83
84 func release(_ marker: Marker) {
85 markers.removeAll { $0 === marker }
86 }
87
88 /// Runs `body` and puts point back where it was, following edits as a marker does.
89 @discardableResult
90 func saveExcursion<T>(_ body: () throws -> T) rethrows -> T {
91 let saved = marker(point)
92 defer {
93 point = saved.position
94 release(saved)
95 }
96 return try body()
97 }
98
99 // MARK: - Editing
100
101 /// `insert` at point.
102 func insert(_ string: String) {
103 let count = (string as NSString).length
104 guard count > 0 else { return }
105 touched(point..<point)
106 text.insert(string, at: point)
107 cachedString = nil
108 for marker in markers where marker.position > point || (marker.advances && marker.position == point) { marker.position += count }
109 point += count
110 }
111
112 /// `insert-before-markers` at point: markers at point move past the text too.
113 func insertBeforeMarkers(_ string: String) {
114 let count = (string as NSString).length
115 guard count > 0 else { return }
116 touched(point..<point)
117 text.insert(string, at: point)
118 cachedString = nil
119 for marker in markers where marker.position >= point { marker.position += count }
120 point += count
121 }
122
123 func deleteRegion(_ start: Int, _ end: Int) {
124 let (lower, upper) = (min(start, end), max(start, end))
125 guard upper > lower else { return }
126 touched(lower..<upper)
127 text.deleteCharacters(in: NSRange(lower..<upper))
128 cachedString = nil
129 func map(_ position: Int) -> Int {
130 position <= lower ? position : position >= upper ? position - (upper - lower) : lower
131 }
132 point = map(point)
133 for marker in markers { marker.position = map(marker.position) }
134 }
135
136 func substring(_ start: Int, _ end: Int) -> String {
137 text.substring(with: NSRange(min(start, end)..<max(start, end)))
138 }
139
140 /// `replace-match` over `range`: positions strictly inside go to its start, positions at
141 /// or after its end shift with the text.
142 func replace(_ range: Range<Int>, with replacement: String) {
143 let delta = (replacement as NSString).length - range.count
144 touched(range)
145 text.replaceCharacters(in: NSRange(range), with: replacement)
146 cachedString = nil
147 func map(_ position: Int) -> Int {
148 if position >= range.upperBound, position > range.lowerBound { return position + delta }
149 return position > range.lowerBound ? range.lowerBound : position
150 }
151 point = map(point)
152 for marker in markers { marker.position = map(marker.position) }
153 }
154
155 // MARK: - Motion
156
157 var bolp: Bool { point == 0 || character(at: point - 1) == Self.newline }
158 var eolp: Bool { point == length || character(at: point) == Self.newline }
159 var bobp: Bool { point == 0 }
160 var eobp: Bool { point == length }
161
162 func lineStart(_ offset: Int) -> Int {
163 var at = min(offset, length)
164 while at > 0, character(at: at - 1) != Self.newline { at -= 1 }
165 return at
166 }
167
168 func lineEnd(_ offset: Int) -> Int {
169 var at = max(offset, 0)
170 while at < length, character(at: at) != Self.newline { at += 1 }
171 return at
172 }
173
174 func beginningOfLine() { point = lineStart(point) }
175 func endOfLine() { point = lineEnd(point) }
176
177 /// `forward-line`: to the start of the line `n` lines away, stopping at the buffer ends.
178 @discardableResult
179 func forwardLine(_ n: Int) -> Int {
180 point = lineStart(point)
181 var remaining = n
182 while remaining > 0 {
183 let end = lineEnd(point)
184 if end == length {
185 point = length
186 return remaining
187 }
188 point = end + 1
189 remaining -= 1
190 }
191 while remaining < 0 {
192 if point == 0 { return remaining }
193 point = lineStart(point - 1)
194 remaining += 1
195 }
196 return 0
197 }
198
199 func skipForward(_ set: Set<unichar>) {
200 while let c = character(at: point), set.contains(c) { point += 1 }
201 }
202
203 func skipBackward(_ set: Set<unichar>) {
204 while let c = character(at: point - 1), set.contains(c) { point -= 1 }
205 }
206
207 static let blanks: Set<unichar> = [32, 9]
208 static let whitespace: Set<unichar> = [32, 9, 10, 13]
209
210 /// Display column of point, counting only what Emacs shows.
211 var currentColumn: Int {
212 let start = lineStart(point)
213 return visibleLine(start).column(at: point - start)
214 }
215
216 /// The display widths of the line starting at `start`, seen with three lines on either
217 /// side so that links spanning lines are whole. Cached by that text.
218 func visibleLine(_ start: Int) -> VisibleLine {
219 let (from, to) = saveExcursion { () -> (Int, Int) in
220 point = start
221 forwardLine(-3)
222 let from = point
223 point = start
224 forwardLine(3)
225 return (from, lineEnd(point))
226 }
227 let context = substring(from, to)
228 let range = (start - from)..<(lineEnd(start) - from)
229 let key = context + "\u{0}\(range.lowerBound)"
230 if let cached = visibleCache[key] { return cached }
231 let line = VisibleLine(context, line: range, options: options, settings: settings)
232 if visibleCache.count > 256 { visibleCache.removeAll() }
233 visibleCache[key] = line
234 return line
235 }
236
237 /// `move-to-column`: as far as `target` on this line, or the line's end. With `force`, a
238 /// tab spanning `target` becomes spaces (`indent-tabs-mode` nil) so point lands on it.
239 func moveToColumn(_ target: Int, force: Bool = false) {
240 let start = lineStart(point)
241 point = start + visibleLine(start).offset(ofColumn: target)
242 guard force, currentColumn > target, character(at: point - 1) == 9 else { return }
243 let tabEnd = currentColumn
244 point -= 1
245 let tabStart = currentColumn
246 deleteRegion(point, point + 1)
247 insert(String(repeating: " ", count: tabEnd - tabStart))
248 point -= tabEnd - target
249 }
250
251 // MARK: - Outline
252
253 /// Stars of a heading line starting at `lineStart`, or nil.
254 func headingLevel(atLine lineStart: Int) -> Int? {
255 var at = lineStart
256 while character(at: at) == 42 { at += 1 }
257 return at > lineStart && character(at: at) == 32 ? at - lineStart : nil
258 }
259
260 var atHeading: Bool { headingLevel(atLine: lineStart(point)) != nil }
261
262 /// Start of the first heading line after `offset`'s line, or nil.
263 func nextHeadingStart(after offset: Int) -> Int? {
264 var line = lineEnd(offset)
265 while line < length {
266 line += 1
267 if headingLevel(atLine: line) != nil { return line }
268 line = lineEnd(line)
269 }
270 return nil
271 }
272
273 /// Start of the last heading line before `offset`'s line, or nil.
274 func previousHeadingStart(before offset: Int) -> Int? {
275 var line = lineStart(offset)
276 while line > 0 {
277 line = lineStart(line - 1)
278 if headingLevel(atLine: line) != nil { return line }
279 }
280 return nil
281 }
282
283 /// `org-outline-level`: the level of the heading at or before point's line, or 0.
284 var outlineLevel: Int {
285 let start = lineStart(point)
286 if let level = headingLevel(atLine: start) { return level }
287 return previousHeadingStart(before: start).flatMap { headingLevel(atLine: $0) } ?? 0
288 }
289
290 var currentLevel: Int? { outlineLevel > 0 ? outlineLevel : nil }
291
292 var beforeFirstHeading: Bool { outlineLevel == 0 }
293
294 /// `org-back-to-heading`.
295 @discardableResult
296 func backToHeading() throws -> Int {
297 let start = lineStart(point)
298 if headingLevel(atLine: start) != nil {
299 point = start
300 } else if let previous = previousHeadingStart(before: start) {
301 point = previous
302 } else {
303 throw UserError(message: "Before first headline at position \(point + 1) in buffer")
304 }
305 return point
306 }
307
308 /// `outline-next-heading`: the next heading line, or the buffer end. True when found.
309 @discardableResult
310 func outlineNextHeading() -> Bool {
311 if bolp, !eobp { point += 1 }
312 // A heading line starting at point counts, as `re-search-forward "^\\*+ "` would.
313 if bolp, headingLevel(atLine: point) != nil { return true }
314 guard let next = nextHeadingStart(after: point) else {
315 point = length
316 return false
317 }
318 point = next
319 return true
320 }
321
322 /// `outline-previous-heading`: the previous heading line, or the buffer start.
323 func outlinePreviousHeading() {
324 // `re-search-backward` matches must end by point: a heading on this line counts once
325 // point is past its stars and space.
326 let start = lineStart(point)
327 if let level = headingLevel(atLine: start), point >= start + level + 1 {
328 point = start
329 return
330 }
331 point = previousHeadingStart(before: point) ?? 0
332 }
333
334 /// `org-end-of-subtree`.
335 @discardableResult
336 func endOfSubtree(toHeading: Bool = false) -> Int {
337 if beforeFirstHeading {
338 point = length
339 } else {
340 let start = try! backToHeading()
341 let level = headingLevel(atLine: start)!
342 var next = nextHeadingStart(after: start)
343 while let candidate = next, headingLevel(atLine: candidate)! > level {
344 next = nextHeadingStart(after: candidate)
345 }
346 point = next ?? length
347 }
348 if !toHeading, let c = character(at: point - 1), c == 10 || c == 13 {
349 point -= 1
350 skipBackward([10, 13, 9, 32])
351 }
352 return point
353 }
354
355 /// `org-get-next-sibling`.
356 func nextSibling() -> Int? {
357 let level = outlineLevel
358 outlineNextHeading()
359 while !eobp, outlineLevel > level { outlineNextHeading() }
360 return eobp || outlineLevel < level ? nil : point
361 }
362
363 /// `org-get-previous-sibling`.
364 func previousSibling() -> Int? {
365 let start = point
366 let level = outlineLevel
367 outlinePreviousHeading()
368 guard point != start, atHeading else { return nil }
369 while outlineLevel > level, !bobp { outlinePreviousHeading() }
370 return outlineLevel < level ? nil : point
371 }
372
373 /// `org--line-empty-p -1`.
374 var previousLineEmpty: Bool {
375 guard !bobp else { return false }
376 return saveExcursion {
377 forwardLine(-1)
378 skipForward(Self.blanks)
379 return eolp
380 }
381 }
382
383 // MARK: - Regular expressions
384
385 static let lookingOptions: NSRegularExpression.MatchingOptions = [.anchored, .withoutAnchoringBounds, .withTransparentBounds]
386 static let searchOptions: NSRegularExpression.MatchingOptions = [.withoutAnchoringBounds, .withTransparentBounds]
387 nonisolated(unsafe) private static var cache: [String: NSRegularExpression] = [:]
388 private static let cacheLock = NSLock()
389
390 /// A compiled Emacs-style pattern: `^` and `$` match at line boundaries, and a leading `^`
391 /// also matches at the end of a buffer that ends with a newline, as in Emacs.
392 static func regex(_ pattern: String, caseInsensitive: Bool) -> NSRegularExpression {
393 let key = (caseInsensitive ? "i" : "c") + pattern
394 return cacheLock.withLock {
395 if let cached = cache[key] { return cached }
396 let source = pattern.hasPrefix("^") ? "(?:(?<=\\n)|(?<![\\s\\S]))" + pattern.dropFirst() : pattern
397 let compiled = try! NSRegularExpression(pattern: source, options: caseInsensitive ? [.anchorsMatchLines, .caseInsensitive] : [.anchorsMatchLines])
398 cache[key] = compiled
399 return compiled
400 }
401 }
402
403 /// `looking-at`: the groups of `pattern` matched at point (`^` and `$` match at lines),
404 /// or nil. Unmatched groups are nil.
405 func lookingAt(_ pattern: String) -> [Range<Int>?]? {
406 let regex = Self.regex(pattern, caseInsensitive: false)
407 guard let match = regex.firstMatch(in: string, options: Self.lookingOptions, range: NSRange(point..<length)) else { return nil }
408 lastMatch = (0..<match.numberOfRanges).map { i in
409 let range = match.range(at: i)
410 return range.location == NSNotFound ? nil : range.location..<NSMaxRange(range)
411 }
412 return lastMatch
413 }
414
415 /// `org-complex-heading-regexp`: 1 stars, 2 keyword, 3 priority, 4 title, 5 tags.
416 var complexHeadingPattern: String {
417 "^(\\*+)(?: +(\(keywordAlternation)))?(?: +(\\[#(?:[A-Z]|[0-9]|[1-5][0-9]|6[0-4])\\]))?(?: +(.*?))??(?:[ \t]+(:[[:alnum:]_@#%:]+:))?[ \t]*$"
418 }
419
420 /// `org-todo-line-regexp`: 1 stars, 2 keyword, 3 title.
421 var todoLinePattern: String {
422 "^(\\*+)(?: +(\(keywordAlternation)))?(?: +(.*?))?[ \t]*$"
423 }
424
425 private var keywordAlternation: String {
426 keywordsInOrder.map { NSRegularExpression.escapedPattern(for: $0) }.joined(separator: "|")
427 }
428
429 /// `org-todo-keywords-1`.
430 var keywordsInOrder: [String] {
431 settings.todoSequences.flatMap { ($0.active + $0.done).map(\.name) }
432 }
433
434 // MARK: - Tags
435
436 /// `org-align-tags` on the line at `offset`, moving point and markers on the line as the
437 /// tag alignment rules say.
438 func alignTags(onLineAt offset: Int) {
439 let start = lineStart(offset)
440 let end = lineEnd(offset)
441 let line = substring(start, end)
442 var plain = LineBuffer(line, caret: nil)
443 OrgCore.alignTags(&plain, options: options)
444 guard plain.string != line else { return }
445 func map(_ position: Int) -> Int {
446 guard position >= start, position <= end else {
447 return position > end ? position + (plain.string as NSString).length - (line as NSString).length : position
448 }
449 var buffer = LineBuffer(line, caret: position - start)
450 OrgCore.alignTags(&buffer, options: options)
451 return start + buffer.caret!
452 }
453 let newPoint = map(point)
454 let newMarkers = markers.map { map($0.position) }
455 touched(start..<end)
456 text.replaceCharacters(in: NSRange(start..<end), with: plain.string)
457 cachedString = nil
458 point = newPoint
459 for (marker, position) in zip(markers, newMarkers) { marker.position = position }
460 }
461}
462
463/// Runs a buffer-editing body against a context and turns the result into one minimal edit
464/// and the new caret. A user error becomes `.failed`.
465func commitBuffer(_ context: EditContext, _ body: (EmacsBuffer) throws -> Void) -> CommandStep {
466 let buffer = EmacsBuffer(context.text, point: context.caret, settings: context.tree.settings, options: context.options)
467 buffer.now = context.now
468 buffer.calendar = context.calendar
469 do {
470 try body(buffer)
471 } catch let error as EmacsBuffer.UserError {
472 return .failed(error.message)
473 } catch {
474 return .failed("\(error)")
475 }
476 // Only the span between the untouched start and end can differ.
477 let oldText = context.text.utf16
478 let oldCount = oldText.count
479 let newCount = buffer.length
480 let lower = min(buffer.unchangedPrefix, oldCount, newCount)
481 let window = max(0, min(buffer.unchangedSuffix, oldCount - lower, newCount - lower))
482 let old = Array(oldText[oldText.index(oldText.startIndex, offsetBy: lower)..<oldText.index(oldText.startIndex, offsetBy: oldCount - window)])
483 var newBuffer = [unichar](repeating: 0, count: newCount - window - lower)
484 buffer.text.getCharacters(&newBuffer, range: NSRange(lower..<(newCount - window)))
485 let new = newBuffer
486 var prefix = 0
487 let shorter = min(old.count, new.count)
488 while prefix < shorter, old[prefix] == new[prefix] { prefix += 1 }
489 var suffix = 0
490 while suffix < shorter - prefix, old[old.count - 1 - suffix] == new[new.count - 1 - suffix] { suffix += 1 }
491 // Keep surrogate pairs whole.
492 while prefix > 0, prefix < old.count, UTF16.isTrailSurrogate(old[prefix]) { prefix -= 1 }
493 while suffix > 0, UTF16.isTrailSurrogate(old[old.count - suffix]) { suffix -= 1 }
494 let caret = buffer.point
495 guard old.count != new.count || prefix != old.count else {
496 return .commit(EditResult(baseRevision: context.revision, edits: [], selection: [caret..<caret]))
497 }
498 let edit = TextEdit(range: (lower + prefix)..<(lower + old.count - suffix), replacement: String(decoding: new[prefix..<(new.count - suffix)], as: UTF16.self))
499 return .commit(EditResult(baseRevision: context.revision, edits: [edit], selection: [caret..<caret]))
500}