krz/orgstar

Line index, and cheaper block bands while typing !63

merged merged by cmc on 2026-10-06 00:31 UTC · krz/orgstar:line-index into main

5 files changed, +176 −11

Layout: unified · split

Sources/OrgEditorAppKit/Keys.swift +2
@@ -21,6 +21,8 @@ final class OrgTextView: NSTextView {
21 var lineNumberFont = NSFont.monospacedDigitSystemFont(ofSize: 11, weight: .regular) 21 var lineNumberFont = NSFont.monospacedDigitSystemFont(ofSize: 11, weight: .regular)
22 var lineNumberColor = NSColor.tertiaryLabelColor 22 var lineNumberColor = NSColor.tertiaryLabelColor
23 var currentLineNumberColor = NSColor.labelColor 23 var currentLineNumberColor = NSColor.labelColor
24 /// Line starts, kept by the editor, for the line numbers.
25 var lineIndex: LineIndex?
24 var showsLineNumbers = false { 26 var showsLineNumbers = false {
25 didSet { if showsLineNumbers != oldValue { updateGutter() } } 27 didSet { if showsLineNumbers != oldValue { updateGutter() } }
26 } 28 }
Sources/OrgEditorAppKit/LineIndex.swift added +72
@@ -0,0 +1,72 @@
1#if os(macOS)
2import Foundation
3
4/// Where each line of the text starts (UTF-16), kept up to date edit by edit, so line numbers
5/// come from a search instead of counting newlines from the top.
6final class LineIndex {
7 /// Sorted; the first line starts at 0.
8 private(set) var starts: [Int] = [0]
9
10 init(_ text: NSString = "") { reset(text) }
11
12 func reset(_ text: NSString) {
13 starts = [0]
14 appendStarts(in: text, from: 0, to: text.length)
15 }
16
17 private func appendStarts(in text: NSString, from: Int, to end: Int) {
18 var location = from
19 while location < end {
20 let found = text.range(of: "\n", options: .literal, range: NSRange(location: location, length: end - location))
21 guard found.location != NSNotFound else { break }
22 starts.append(found.location + 1)
23 location = found.location + 1
24 }
25 }
26
27 var lineCount: Int { starts.count }
28
29 /// The line (from 1) holding `offset`.
30 func line(of offset: Int) -> Int {
31 var low = 0
32 var high = starts.count
33 while low < high {
34 let mid = (low + high) / 2
35 if starts[mid] <= offset { low = mid + 1 } else { high = mid }
36 }
37 return max(1, low)
38 }
39
40 /// `old` (in the text before) became `newLength` characters of `text` (the text after).
41 func replace(_ old: Range<Int>, newLength: Int, in text: NSString) {
42 let delta = newLength - old.count
43 // Starts after a newline inside the old range go; starts after it move.
44 let first = firstIndex(after: old.lowerBound)
45 let last = firstIndex(after: old.upperBound)
46 var inserted: [Int] = []
47 var location = old.lowerBound
48 let end = old.lowerBound + newLength
49 while location < end {
50 let found = text.range(of: "\n", options: .literal, range: NSRange(location: location, length: end - location))
51 guard found.location != NSNotFound else { break }
52 inserted.append(found.location + 1)
53 location = found.location + 1
54 }
55 if delta != 0 {
56 for i in last..<starts.count { starts[i] += delta }
57 }
58 starts.replaceSubrange(first..<last, with: inserted)
59 }
60
61 /// The index of the first start greater than `offset`.
62 private func firstIndex(after offset: Int) -> Int {
63 var low = 0
64 var high = starts.count
65 while low < high {
66 let mid = (low + high) / 2
67 if starts[mid] <= offset { low = mid + 1 } else { high = mid }
68 }
69 return low
70 }
71}
72#endif
Sources/OrgEditorAppKit/LineNumbers.swift +2 −7
@@ -9,7 +9,7 @@ extension OrgTextView {
9 func updateGutter() { 9 func updateGutter() {
10 var width: CGFloat = 0 10 var width: CGFloat = 0
11 if showsLineNumbers { 11 if showsLineNumbers {
12 let lines = (string as NSString).components(separatedBy: "\n").count 12 let lines = lineIndex?.lineCount ?? 1
13 let digits = max(2, String(lines).count) 13 let digits = max(2, String(lines).count)
14 width = ceil(("0" as NSString).size(withAttributes: [.font: lineNumberFont]).width * CGFloat(digits) + 16) 14 width = ceil(("0" as NSString).size(withAttributes: [.font: lineNumberFont]).width * CGFloat(digits) + 16)
15 } 15 }
@@ -30,17 +30,12 @@ extension OrgTextView {
30 guard let start = layout.textLayoutFragment(for: CGPoint(x: 0, y: max(0, rect.minY - origin.y)))?.rangeInElement.location 30 guard let start = layout.textLayoutFragment(for: CGPoint(x: 0, y: max(0, rect.minY - origin.y)))?.rangeInElement.location
31 ?? layout.textViewportLayoutController.viewportRange?.location else { return } 31 ?? layout.textViewportLayoutController.viewportRange?.location else { return }
32 32
33 var counted = 0
34 var line = 1
35 layout.enumerateTextLayoutFragments(from: start, options: []) { fragment in 33 layout.enumerateTextLayoutFragments(from: start, options: []) { fragment in
36 let frame = fragment.layoutFragmentFrame 34 let frame = fragment.layoutFragmentFrame
37 if frame.minY + origin.y > rect.maxY { return false } 35 if frame.minY + origin.y > rect.maxY { return false }
38 let offset = content.offset(from: documentStart, to: fragment.rangeInElement.location) 36 let offset = content.offset(from: documentStart, to: fragment.rangeInElement.location)
39 guard offset <= text.length else { return false } 37 guard offset <= text.length else { return false }
40 while counted < offset { 38 let line = lineIndex?.line(of: offset) ?? 1
41 if text.character(at: counted) == 10 { line += 1 }
42 counted += 1
43 }
44 let label = NSAttributedString(string: "\(line)", attributes: [ 39 let label = NSAttributedString(string: "\(line)", attributes: [
45 .font: lineNumberFont, 40 .font: lineNumberFont,
46 .foregroundColor: offset == caretLine ? currentLineNumberColor : lineNumberColor, 41 .foregroundColor: offset == caretLine ? currentLineNumberColor : lineNumberColor,
Sources/OrgEditorAppKit/OrgEditor.swift +48 −4
@@ -52,6 +52,8 @@ public final class OrgEditor: NSObject {
52 52
53 let hidden = HiddenRanges() 53 let hidden = HiddenRanges()
54 let folded = FoldedHeadings() 54 let folded = FoldedHeadings()
55 /// Where lines start, for line numbers.
56 let lines = LineIndex()
55 /// Blocks drawn on a shaded band. 57 /// Blocks drawn on a shaded band.
56 let shaded = HiddenRanges() 58 let shaded = HiddenRanges()
57 private(set) var theme = Theme() 59 private(set) var theme = Theme()
@@ -143,6 +145,9 @@ public final class OrgEditor: NSObject {
143 isLoading = true 145 isLoading = true
144 textView.textStorage?.setAttributedString(NSAttributedString(string: text, attributes: theme.base)) 146 textView.textStorage?.setAttributedString(NSAttributedString(string: text, attributes: theme.base))
145 isLoading = false 147 isLoading = false
148 lines.reset(text as NSString)
149 orgTextView?.lineIndex = lines
150 orgTextView?.updateGutter()
146 styledUpTo = 0 151 styledUpTo = 0
147 styleNextChunk(Self.firstStyleChunk) 152 styleNextChunk(Self.firstStyleChunk)
148 scheduleStyling() 153 scheduleStyling()
@@ -699,6 +704,36 @@ public final class OrgEditor: NSObject {
699 704
700 // MARK: - Editing 705 // MARK: - Editing
701 706
707 private var blockCheck: DispatchWorkItem?
708
709 /// Looks for blocks over the whole file once typing pauses, catching what moving the
710 /// ranges can't see (a block's end found far away).
711 private func scheduleBlockCheck() {
712 blockCheck?.cancel()
713 let work = DispatchWorkItem { [weak self] in self?.settleBlocks() }
714 blockCheck = work
715 DispatchQueue.main.asyncAfter(deadline: .now() + 0.3, execute: work)
716 }
717
718 func settleBlocks() {
719 blockCheck?.cancel()
720 guard isOrg else { return }
721 let blocks = Presentation.shadedBlocks(document.tree)
722 guard blocks != shaded.all else { return }
723 shaded.set(blocks)
724 textLayoutManager.invalidateLayout(for: textLayoutManager.documentRange)
725 }
726
727 /// Whether the lines around `range`, and the line after it (a deleted newline joins it to
728 /// them), hold a block delimiter or a fixed-width line.
729 static func mayChangeBlocks(_ text: NSString, _ range: Range<Int>) -> Bool {
730 let start = min(range.lowerBound, text.length)
731 let end = min(range.upperBound + 1, text.length)
732 let lines = text.lineRange(for: NSRange(location: start, length: end - start))
733 let content = text.substring(with: lines)
734 return content.contains("#+") || content.range(of: "(^|\\n)([ \\t]*:|\\*)", options: .regularExpression) != nil
735 }
736
702 fileprivate func storageEdited(range: NSRange, delta: Int) { 737 fileprivate func storageEdited(range: NSRange, delta: Int) {
703 guard !isLoading, let storage = textView.textStorage else { return } 738 guard !isLoading, let storage = textView.textStorage else { return }
704 markActive = false 739 markActive = false
@@ -733,15 +768,24 @@ public final class OrgEditor: NSObject {
733 let oldMapped = oldAffected.lowerBound..<(oldAffected.upperBound >= edit.range.upperBound ? oldAffected.upperBound + delta : newEnd) 768 let oldMapped = oldAffected.lowerBound..<(oldAffected.upperBound >= edit.range.upperBound ? oldAffected.upperBound + delta : newEnd)
734 restyle(min(oldMapped.lowerBound, newAffected.lowerBound)..<min(max(oldMapped.upperBound, newAffected.upperBound), newText.length), in: storage) 769 restyle(min(oldMapped.lowerBound, newAffected.lowerBound)..<min(max(oldMapped.upperBound, newAffected.upperBound), newText.length), in: storage)
735 let oldShaded = shaded.all 770 let oldShaded = shaded.all
736 if isOrg { shaded.set(Presentation.shadedBlocks(document.tree)) } 771 if isOrg {
772 // Walking the tree for blocks costs more than typing; only an edit on a line that
773 // could start or end one (`#+…`, `: …`) needs it, others move the ranges.
774 if Self.mayChangeBlocks(oldText, edit.range) || Self.mayChangeBlocks(newText, edit.range.lowerBound..<newEnd) {
775 shaded.set(Presentation.shadedBlocks(document.tree))
776 } else {
777 shaded.set(oldShaded.map { mapRange($0, through: edit) })
778 }
779 scheduleBlockCheck()
780 }
737 if hidden.all != oldHidden.map({ mapRange($0, through: edit) }) 781 if hidden.all != oldHidden.map({ mapRange($0, through: edit) })
738 || shaded.all != oldShaded.map({ mapRange($0, through: edit) }) { 782 || shaded.all != oldShaded.map({ mapRange($0, through: edit) }) {
739 textLayoutManager.invalidateLayout(for: textLayoutManager.documentRange) 783 textLayoutManager.invalidateLayout(for: textLayoutManager.documentRange)
740 } 784 }
741 onEditTiming?(clock.now - start) 785 onEditTiming?(clock.now - start)
742 if edit.replacement.contains("\n") || (oldText.substring(with: NSRange(edit.range)) as String).contains("\n") { 786 let lineCount = lines.lineCount
743 orgTextView?.updateGutter() 787 lines.replace(edit.range, newLength: edit.replacement.utf16.count, in: newText)
744 } 788 if lines.lineCount != lineCount { orgTextView?.updateGutter() }
745 orgTextView?.redrawLineNumbers() 789 orgTextView?.redrawLineNumbers()
746 onChange?() 790 onChange?()
747 } 791 }
Tests/OrgEditorAppKitTests/LineIndexTests.swift added +52
@@ -0,0 +1,52 @@
1import Foundation
2import Testing
3import OrgPresentation
4@testable import OrgEditorAppKit
5
6struct LineIndexTests {
7 func naive(_ text: String) -> [Int] {
8 var starts = [0]
9 for (i, u) in text.utf16.enumerated() where u == 10 { starts.append(i + 1) }
10 return starts
11 }
12
13 @Test func followsRandomEdits() {
14 var generator = SystemRandomNumberGenerator()
15 let pieces = ["a", "bc\n", "\n", "\n\n", "xyz", "é\n", "😀", ""]
16 var text = "first\nsecond\n\nthird"
17 let index = LineIndex(text as NSString)
18 for _ in 0..<2000 {
19 let ns = text as NSString
20 let start = Int.random(in: 0...ns.length, using: &generator)
21 let end = min(ns.length, start + Int.random(in: 0...6, using: &generator))
22 let replacement = pieces.randomElement(using: &generator)!
23 text = ns.replacingCharacters(in: NSRange(location: start, length: end - start), with: replacement)
24 index.replace(start..<end, newLength: (replacement as NSString).length, in: text as NSString)
25 #expect(index.starts == naive(text))
26 if index.starts != naive(text) { return }
27 }
28 #expect(index.line(of: 0) == 1)
29 #expect(index.line(of: (text as NSString).length) == naive(text).count)
30 }
31}
32
33@MainActor
34struct ShadedBlockTests {
35 /// Bands after edits match a full search once typing settles.
36 @Test func incrementalMatchesFull() {
37 var generator = SystemRandomNumberGenerator()
38 let pieces = ["x", "word ", "\n", "#+begin_src sh\n", "#+end_src\n", ": fixed\n", "* H\n", "#+begin_quote\n", "#+end_quote\n", ""]
39 let h = Harness("* A\n#+begin_src sh\nls\n#+end_src\ntext\n: one\n* B\nbody\n")
40 for _ in 0..<400 {
41 let length = h.editor.document.text.utf16.count
42 let start = Int.random(in: 0...length, using: &generator)
43 let end = min(length, start + Int.random(in: 0...5, using: &generator))
44 let piece = pieces.randomElement(using: &generator)!
45 h.textView.insertText(piece, replacementRange: NSRange(location: start, length: end - start))
46 h.editor.settleBlocks()
47 let full = Presentation.shadedBlocks(h.editor.document.tree)
48 #expect(h.editor.shaded.all == full, "\(h.editor.document.text)")
49 if h.editor.shaded.all != full { return }
50 }
51 }
52}