Sources/OrgCore/Commands/SparseTree.swift
277 lines · 15334 bytes
1import Foundation
2
3// Sparse trees (`org-sparse-tree`, C-c /, Org 9.8.7): `org-occur` and the trees built on it,
4// and `org-match-sparse-tree`. Matches are shown as `org-fold-show-context` does with the
5// default `ancestors` detail, after `org-cycle-overview`.
6
7public enum SparseTree {
8 /// Where each match leaves point (org shows the context there), and the text to highlight.
9 public struct Matches: Sendable, Equatable {
10 public var points: [Int] = []
11 public var highlights: [Range<Int>] = []
12 }
13
14 /// `org-occur`: matches of `pattern` (ICU), each kept when `keep` says so.
15 static func occur(_ buffer: EmacsBuffer, _ pattern: String, caseInsensitive: Bool, keep: ((EmacsBuffer, [Range<Int>?]) -> Bool)? = nil) -> Matches {
16 var matches = Matches()
17 buffer.point = 0
18 while buffer.point <= buffer.length, let match = buffer.searchForward(pattern, caseInsensitive: caseInsensitive) {
19 let whole = match[0]!
20 buffer.point = whole.upperBound
21 let kept = buffer.saveExcursion { keep?(buffer, match) ?? true }
22 if kept {
23 matches.points.append(whole.upperBound)
24 matches.highlights.append(whole)
25 }
26 if whole.isEmpty {
27 guard buffer.point < buffer.length else { break }
28 buffer.point += 1
29 }
30 }
31 return matches
32 }
33
34 /// `org-occur` with a regexp in Emacs syntax.
35 public static func occur(_ regexp: String, in text: String) throws -> Matches {
36 guard !regexp.isEmpty else { throw EmacsBuffer.UserError(message: "Regexp cannot be empty") }
37 let pattern = EmacsRegex.translate(regexp)
38 guard (try? NSRegularExpression(pattern: pattern)) != nil else { throw EmacsBuffer.UserError(message: "Invalid regexp") }
39 return occur(EmacsBuffer(text, point: 0), pattern, caseInsensitive: true)
40 }
41
42 /// `org-show-todo-tree`: headings with an unfinished keyword, or with `keywords`
43 /// (`KWD1|KWD2`).
44 public static func todo(_ keywords: String?, in text: String, settings: OrgSettings) -> Matches {
45 let buffer = EmacsBuffer(text, point: 0, settings: settings)
46 let words: [String]
47 let after: String
48 if let keywords {
49 words = keywords.split(separator: "|").map(String.init).filter { !$0.isEmpty }
50 after = "(?:[ \\t]|$)"
51 } else {
52 words = buffer.keywordsInOrder.filter { !settings.isDone($0) }
53 after = "\\b\\s"
54 }
55 guard !words.isEmpty else { return Matches() }
56 let alternation = words.map(NSRegularExpression.escapedPattern(for:)).joined(separator: "|")
57 let pattern = "^\\*+ " + " *" + (keywords == nil ? "\\b(" + alternation + ")" : "(" + alternation + ")") + after
58 return occur(buffer, pattern, caseInsensitive: false)
59 }
60
61 /// `org-match-sparse-tree`: headings matching a tags/property match, their stars
62 /// highlighted.
63 public static func match(_ match: String, in text: String, now: Date, calendar: Calendar) -> Matches {
64 let source = AgendaSource(path: "", text: text)
65 let matcher = TagsMatcher(match)
66 var matches = Matches()
67 for heading in source.headings where matcher.matches(heading, in: source, now: now, calendar: calendar) {
68 let stars = (text as NSString).substring(from: heading.start).prefix { $0 == "*" }.utf16.count
69 matches.points.append(heading.start)
70 matches.highlights.append(heading.start..<(heading.start + stars))
71 }
72 return matches
73 }
74
75 /// The day of an Org time string, as days since the epoch in `calendar`.
76 static func day(_ stamp: String, calendar: Calendar) -> Int? {
77 guard let c = EmacsBuffer.parseTimeString(stamp), let date = calendar.date(from: DateComponents(year: c.year, month: c.month, day: c.day)) else { return nil }
78 return calendar.dateComponents([.day], from: Date(timeIntervalSince1970: 0), to: date).day
79 }
80
81 /// `org-time-string-to-time`.
82 static func time(_ stamp: String, calendar: Calendar) -> Date? {
83 guard let c = EmacsBuffer.parseTimeString(stamp) else { return nil }
84 return calendar.date(from: c)
85 }
86
87 /// `org-check-deadlines`: deadlines past due or due within `days`, in entries not done.
88 public static func deadlines(within days: Int, in text: String, settings: OrgSettings, now: Date, calendar: Calendar) -> Matches {
89 let buffer = EmacsBuffer(text, point: 0, settings: settings)
90 let today = calendar.dateComponents([.day], from: Date(timeIntervalSince1970: 0), to: calendar.startOfDay(for: now)).day ?? 0
91 return occur(buffer, "\\bDEADLINE: *<([^>]+)>", caseInsensitive: false) { buffer, match in
92 let stamp = buffer.substring(match[1]!.lowerBound, match[1]!.upperBound)
93 guard let day = day(stamp, calendar: calendar), day - today <= days else { return false }
94 return !entryIsDone(buffer, settings: settings)
95 }
96 }
97
98 /// `org-entry-is-done-p`.
99 static func entryIsDone(_ buffer: EmacsBuffer, settings: OrgSettings) -> Bool {
100 guard (try? buffer.backToHeading()) != nil, let m = buffer.lookingAt("\\*+ +(\\S+)") else { return false }
101 return settings.isDone(buffer.substring(m[1]!.lowerBound, m[1]!.upperBound))
102 }
103
104 /// `org-check-before-date`, `org-check-after-date` and `org-check-dates-range` on
105 /// SCHEDULED and DEADLINE: planning times `from` or later and before `to`.
106 public static func planning(from: String?, to: String?, in text: String, calendar: Calendar) -> Matches {
107 let buffer = EmacsBuffer(text, point: 0)
108 let low = from.flatMap { time($0, calendar: calendar) }
109 let high = to.flatMap { time($0, calendar: calendar) }
110 return occur(buffer, "\\b(?:DEADLINE|SCHEDULED): *<([^>]+)>", caseInsensitive: false) { buffer, match in
111 guard buffer.lookingAtLine("^[ \\t]*(?:SCHEDULED|DEADLINE|CLOSED):"),
112 let at = time(buffer.substring(match[1]!.lowerBound, match[1]!.upperBound), calendar: calendar) else { return false }
113 if let low, at < low { return false }
114 if let high, !(at < high) { return false }
115 return true
116 }
117 }
118
119 /// What stays hidden: `org-cycle-overview`, then each point's context shown (its heading
120 /// line, or its entry, and its ancestors' heading lines), then archived subtrees folded.
121 public static func hidden(_ points: [Int], in text: String, tree: OrgTree) -> [Range<Int>] {
122 let ns = text as NSString
123 var lineStarts: [Int] = []
124 var offset = 0
125 while offset < ns.length {
126 lineStarts.append(offset)
127 offset = NSMaxRange(ns.lineRange(for: NSRange(location: offset, length: 0)))
128 }
129 if lineStarts.isEmpty { return [] }
130 func lineIndex(_ position: Int) -> Int {
131 var low = 0, high = lineStarts.count - 1
132 while low < high {
133 let mid = (low + high + 1) / 2
134 if lineStarts[mid] <= position { low = mid } else { high = mid - 1 }
135 }
136 return low
137 }
138 let model = DocumentModel(tree: tree)
139 let headings = model.headings
140 var visible = [Bool](repeating: false, count: lineStarts.count)
141 let firstHeadingLine = headings.first.map { lineIndex($0.headingRange.lowerBound) } ?? lineStarts.count
142 for i in 0..<firstHeadingLine { visible[i] = true }
143 for heading in headings where heading.level == 1 { visible[lineIndex(heading.headingRange.lowerBound)] = true }
144 let headingStarts = headings.map(\.headingRange.lowerBound)
145 func headingIndex(at position: Int) -> Int? {
146 headingStarts.lastIndex { $0 <= position }
147 }
148 for point in points {
149 let line = lineIndex(min(point, ns.length))
150 guard let h = headingIndex(at: lineStarts[line]) else { continue }
151 if lineStarts[line] == headingStarts[h] {
152 visible[line] = true
153 } else {
154 let bodyEnd = h + 1 < headings.count ? headingStarts[h + 1] : ns.length
155 for i in lineIndex(headingStarts[h])..<lineStarts.count where lineStarts[i] < bodyEnd { visible[i] = true }
156 }
157 var parent = headings[h].parent
158 while let p = parent {
159 visible[lineIndex(headingStarts[p])] = true
160 parent = headings[p].parent
161 }
162 }
163 for (index, heading) in headings.enumerated() where heading.localTags.contains("ARCHIVE") {
164 let end = headings[(index + 1)...].first { $0.level <= heading.level }?.headingRange.lowerBound ?? ns.length
165 let first = lineIndex(heading.headingRange.lowerBound) + 1
166 for i in first..<lineStarts.count where lineStarts[i] < end { visible[i] = false }
167 }
168 var ranges: [Range<Int>] = []
169 var start: Int?
170 for i in lineStarts.indices {
171 if !visible[i], start == nil { start = lineStarts[i] }
172 if visible[i], let s = start {
173 ranges.append(s..<lineStarts[i])
174 start = nil
175 }
176 }
177 if let s = start { ranges.append(s..<ns.length) }
178 return ranges
179 }
180}
181
182/// C-c /: `org-sparse-tree`. The editor shows the result.
183public struct SparseTreeCommand: OrgCommand {
184 public init() {}
185 public var id: String { "org.sparse-tree" }
186 public var title: String { "Sparse Tree…" }
187 public func applies(in context: EditContext) -> Bool { true }
188
189 static let menu = FastSelection(items: [
190 .option(key: "r", name: "regexp"), .option(key: "t", name: "todo"), .option(key: "T", name: "todo keyword"),
191 .option(key: "m", name: "match"), .option(key: "p", name: "property"), .newline,
192 .option(key: "d", name: "deadlines"), .option(key: "b", name: "before date"), .option(key: "a", name: "after date"),
193 .option(key: "D", name: "dates range"),
194 ], multiple: false)
195
196 public func run(in context: EditContext) -> CommandStep {
197 guard let kind = context.answers["sparse"] else {
198 return .prompt(Prompt(key: "sparse", message: "Sparse tree: [r]egexp [t]odo [T]odo-kwd [m]atch [p]roperty [d]eadlines [b]efore-date [a]fter-date [D]ates range", fast: Self.menu))
199 }
200 let text = context.text
201 let settings = context.tree.settings
202 func ask(_ key: String, _ message: String, choices: [String] = [], date: Bool = false) -> CommandStep? {
203 context.answers[key] == nil ? .prompt(Prompt(key: key, message: message, choices: choices, requireMatch: false, date: date ? .init(defaultDate: nil) : nil)) : nil
204 }
205 func dateString(_ answer: String) -> String {
206 let read = ReadDate.read(answer, default: nil, now: context.now, calendar: context.calendar)
207 let base = String(format: "%04d-%02d-%02d", read.year, read.month, read.day)
208 return read.timeGiven ? base + String(format: " %02d:%02d", read.hour, read.minute) : base
209 }
210 let matches: SparseTree.Matches
211 let message: String?
212 switch kind {
213 case "r", "R", "/":
214 if let step = ask("regexp", "Regexp:") { return step }
215 do {
216 matches = try SparseTree.occur(context.answers["regexp"]!, in: text)
217 } catch let error as EmacsBuffer.UserError {
218 return .failed(error.message)
219 } catch {
220 return .failed("\(error)")
221 }
222 message = "\(matches.points.count) match(es) for regexp \(context.answers["regexp"]!)"
223 case "t":
224 matches = SparseTree.todo(nil, in: text, settings: settings)
225 message = "\(matches.points.count) TODO entries found"
226 case "T":
227 let buffer = EmacsBuffer(text, point: 0, settings: settings)
228 if let step = ask("keyword", "Keyword (or KWD1|KWD2|...):", choices: buffer.keywordsInOrder) { return step }
229 matches = SparseTree.todo(context.answers["keyword"]!, in: text, settings: settings)
230 message = "\(matches.points.count) TODO entries found"
231 case "m":
232 if let step = ask("match", "Match:") { return step }
233 matches = SparseTree.match(context.answers["match"]!, in: text, now: context.now, calendar: context.calendar)
234 message = nil
235 case "p", "P":
236 if let step = ask("property", "Property:", choices: SortEntries.propertyKeys(text)) { return step }
237 let name = context.answers["property"]!
238 let values = SparseTreeCommand.propertyValues(name, in: text)
239 if let step = ask("value", "Value:", choices: values) { return step }
240 var value = context.answers["value"]!
241 if value.range(of: "^\\{.*\\}$", options: .regularExpression) == nil { value = "\"" + value + "\"" }
242 matches = SparseTree.match(name.replacingOccurrences(of: "-", with: "\\-") + "=" + value, in: text, now: context.now, calendar: context.calendar)
243 message = nil
244 case "d":
245 matches = SparseTree.deadlines(within: 14, in: text, settings: settings, now: context.now, calendar: context.calendar)
246 message = "\(matches.points.count) deadlines past-due or due within 14 days"
247 case "b", "a":
248 if let step = ask("date", "Date:", date: true) { return step }
249 let date = dateString(context.answers["date"]!)
250 matches = kind == "b" ? SparseTree.planning(from: nil, to: date, in: text, calendar: context.calendar)
251 : SparseTree.planning(from: date, to: nil, in: text, calendar: context.calendar)
252 message = "\(matches.points.count) entries \(kind == "b" ? "before" : "after") \(date)"
253 case "D":
254 if let step = ask("start", "Range starts:", date: true) { return step }
255 if let step = ask("end", "Range end:", date: true) { return step }
256 let start = dateString(context.answers["start"]!)
257 let end = dateString(context.answers["end"]!)
258 matches = SparseTree.planning(from: start, to: end, in: text, calendar: context.calendar)
259 message = "\(matches.points.count) entries between \(start) and \(end)"
260 default:
261 return .failed("No such sparse tree command \"\(kind)\"")
262 }
263 let effects: [Effect] = [.sparseTree(show: matches.points, highlights: matches.highlights)] + (message.map { [.message($0)] } ?? [])
264 return .commit(EditResult(baseRevision: context.revision, edits: [], effects: effects))
265 }
266
267 /// `org-property-values`: the values `name` has in the text.
268 static func propertyValues(_ name: String, in text: String) -> [String] {
269 let pattern = "(?mi)^[ \\t]*:" + NSRegularExpression.escapedPattern(for: name) + ":[ \\t]+(.*?)[ \\t]*$"
270 var values: [String] = []
271 for m in (try! NSRegularExpression(pattern: pattern)).matches(in: text, range: NSRange(location: 0, length: (text as NSString).length)) {
272 let value = (text as NSString).substring(with: m.range(at: 1))
273 if !values.contains(value) { values.append(value) }
274 }
275 return values
276 }
277}