Sources/OrgIndex/IndexStore.swift
351 lines · 15831 bytes
1import Foundation
2import GRDB
3
4/// What the index knows about a file without reading it.
5public struct FileState: Sendable, Equatable {
6 public let kind: FileKind
7 public let size: Int
8 public let mtime: Double
9 public let hash: String
10 public let settingsVersion: Int
11}
12
13/// A heading as found by a query. `contentHash` is the hash of the text the offsets refer to,
14/// so a caller can tell whether they still apply to an open buffer.
15public struct IndexedHeading: Sendable, Hashable {
16 public let location: HeadingLocation
17 public let level: Int
18 /// Titles from the top-level ancestor down to the heading itself.
19 public let outlinePath: [String]
20}
21
22public struct HeadingLocation: Sendable, Hashable {
23 public let path: String
24 public let ordinal: Int
25 public let title: String
26 public let start: Int
27 public let contentHash: String
28
29 public init(path: String, ordinal: Int, title: String, start: Int, contentHash: String) {
30 self.path = path
31 self.ordinal = ordinal
32 self.title = title
33 self.start = start
34 self.contentHash = contentHash
35 }
36}
37
38/// One reconciliation's worth of changes, applied in a single transaction.
39public struct IndexChange: Sendable {
40 public var records: [FileRecord] = []
41 /// Unchanged content with a new modification time.
42 public var touches: [(path: String, mtime: Double)] = []
43 /// Renamed files whose content didn't change.
44 public var moves: [(from: String, to: String, mtime: Double)] = []
45 public var removals: [String] = []
46
47 public init() {}
48
49 public var isEmpty: Bool { records.isEmpty && touches.isEmpty && moves.isEmpty && removals.isEmpty }
50}
51
52/// The SQLite index. A cache: deleting it loses nothing that the files don't hold.
53public final class IndexStore: Sendable {
54 let database: DatabaseQueue
55
56 /// `path` nil opens an in-memory index.
57 public init(path: String? = nil) throws {
58 database = try path.map { try DatabaseQueue(path: $0) } ?? DatabaseQueue()
59 try Self.migrator.migrate(database)
60 }
61
62 static var migrator: DatabaseMigrator {
63 var migrator = DatabaseMigrator()
64 migrator.registerMigration("v1") { db in
65 try db.execute(sql: """
66 CREATE TABLE files (
67 id INTEGER PRIMARY KEY,
68 path TEXT NOT NULL UNIQUE,
69 root TEXT NOT NULL,
70 kind TEXT NOT NULL,
71 size INTEGER NOT NULL,
72 mtime REAL NOT NULL,
73 hash TEXT NOT NULL,
74 settings_version INTEGER NOT NULL,
75 parsed_at REAL NOT NULL
76 );
77 CREATE INDEX files_root ON files(root);
78 CREATE TABLE headings (
79 id INTEGER PRIMARY KEY,
80 file_id INTEGER NOT NULL REFERENCES files(id) ON DELETE CASCADE,
81 ordinal INTEGER NOT NULL,
82 parent_ordinal INTEGER,
83 start_offset INTEGER NOT NULL,
84 end_offset INTEGER NOT NULL,
85 level INTEGER NOT NULL,
86 todo TEXT,
87 is_done INTEGER NOT NULL,
88 priority TEXT,
89 title TEXT NOT NULL,
90 outline_path TEXT NOT NULL,
91 org_id TEXT,
92 archived INTEGER NOT NULL
93 );
94 CREATE INDEX headings_file ON headings(file_id);
95 CREATE INDEX headings_org_id ON headings(org_id);
96 CREATE TABLE tags (
97 heading_id INTEGER NOT NULL REFERENCES headings(id) ON DELETE CASCADE,
98 tag TEXT NOT NULL,
99 inherited INTEGER NOT NULL
100 );
101 CREATE INDEX tags_heading ON tags(heading_id);
102 CREATE TABLE properties (
103 heading_id INTEGER NOT NULL REFERENCES headings(id) ON DELETE CASCADE,
104 key TEXT NOT NULL,
105 value TEXT NOT NULL,
106 inherited INTEGER NOT NULL
107 );
108 CREATE INDEX properties_heading ON properties(heading_id);
109 CREATE TABLE timestamps (
110 heading_id INTEGER NOT NULL REFERENCES headings(id) ON DELETE CASCADE,
111 kind TEXT NOT NULL,
112 start_at TEXT NOT NULL,
113 end_at TEXT,
114 repeater TEXT,
115 warning TEXT
116 );
117 CREATE INDEX timestamps_heading ON timestamps(heading_id);
118 CREATE TABLE clocks (
119 heading_id INTEGER NOT NULL REFERENCES headings(id) ON DELETE CASCADE,
120 start_at TEXT NOT NULL,
121 end_at TEXT,
122 minutes INTEGER
123 );
124 CREATE INDEX clocks_heading ON clocks(heading_id);
125 CREATE TABLE links (
126 heading_id INTEGER NOT NULL REFERENCES headings(id) ON DELETE CASCADE,
127 type TEXT NOT NULL,
128 target TEXT NOT NULL
129 );
130 CREATE INDEX links_heading ON links(heading_id);
131 CREATE VIRTUAL TABLE headings_fts USING fts5(title, body, tokenize = 'unicode61 remove_diacritics 2');
132 CREATE TRIGGER headings_fts_delete AFTER DELETE ON headings BEGIN
133 DELETE FROM headings_fts WHERE rowid = old.id;
134 END;
135 """)
136 }
137 return migrator
138 }
139
140 // MARK: - Writing
141
142 public func write(_ record: FileRecord) throws {
143 var change = IndexChange()
144 change.records = [record]
145 try apply(change)
146 }
147
148 public func apply(_ change: IndexChange) throws {
149 guard !change.isEmpty else { return }
150 try database.write { db in
151 for path in change.removals {
152 try db.execute(sql: "DELETE FROM files WHERE path = ?", arguments: [path])
153 }
154 for move in change.moves {
155 try db.execute(sql: "UPDATE files SET path = ?, mtime = ? WHERE path = ?", arguments: [move.to, move.mtime, move.from])
156 }
157 for touch in change.touches {
158 try db.execute(sql: "UPDATE files SET mtime = ? WHERE path = ?", arguments: [touch.mtime, touch.path])
159 }
160 for record in change.records {
161 try insert(record, db)
162 }
163 }
164 }
165
166 private func insert(_ record: FileRecord, _ db: Database) throws {
167 try db.execute(sql: "DELETE FROM files WHERE path = ?", arguments: [record.path])
168 try db.execute(
169 sql: """
170 INSERT INTO files (path, root, kind, size, mtime, hash, settings_version, parsed_at)
171 VALUES (?, ?, ?, ?, ?, ?, ?, ?)
172 """,
173 arguments: [record.path, record.root, record.kind.rawValue, record.size, record.mtime, record.hash,
174 record.settingsVersion, Date().timeIntervalSince1970]
175 )
176 let fileID = db.lastInsertedRowID
177 for heading in record.headings {
178 try db.execute(
179 sql: """
180 INSERT INTO headings (file_id, ordinal, parent_ordinal, start_offset, end_offset, level, todo,
181 is_done, priority, title, outline_path, org_id, archived)
182 VALUES (?, ?, ?, ?, ?, ?, ?, ?, ?, ?, ?, ?, ?)
183 """,
184 arguments: [fileID, heading.ordinal, heading.parent, heading.start, heading.end, heading.level, heading.todo,
185 heading.isDone, heading.priority, heading.title, heading.outlinePath.joined(separator: "\u{1F}"),
186 heading.orgID, heading.archived]
187 )
188 let id = db.lastInsertedRowID
189 try db.execute(sql: "INSERT INTO headings_fts (rowid, title, body) VALUES (?, ?, ?)", arguments: [id, heading.title, heading.body])
190 for tag in heading.tags {
191 try db.execute(sql: "INSERT INTO tags VALUES (?, ?, ?)", arguments: [id, tag.name, tag.inherited])
192 }
193 for property in heading.properties {
194 try db.execute(sql: "INSERT INTO properties VALUES (?, ?, ?, ?)", arguments: [id, property.key, property.value, property.inherited])
195 }
196 for stamp in heading.timestamps {
197 try db.execute(
198 sql: "INSERT INTO timestamps VALUES (?, ?, ?, ?, ?, ?)",
199 arguments: [id, stamp.kind.rawValue, stamp.start, stamp.end, stamp.repeater, stamp.warning]
200 )
201 }
202 for clock in heading.clocks {
203 try db.execute(sql: "INSERT INTO clocks VALUES (?, ?, ?, ?)", arguments: [id, clock.start, clock.end, clock.minutes])
204 }
205 for link in heading.links {
206 try db.execute(sql: "INSERT INTO links VALUES (?, ?, ?)", arguments: [id, link.type, link.target])
207 }
208 }
209 }
210
211 // MARK: - Reading
212
213 /// Indexed files under `root`, by path.
214 public func fileStates(root: String) throws -> [String: FileState] {
215 try database.read { db in
216 let rows = try Row.fetchAll(db, sql: "SELECT path, kind, size, mtime, hash, settings_version FROM files WHERE root = ?", arguments: [root])
217 var states: [String: FileState] = [:]
218 for row in rows {
219 states[row["path"]] = FileState(
220 kind: FileKind(rawValue: row["kind"]) ?? .org,
221 size: row["size"], mtime: row["mtime"], hash: row["hash"], settingsVersion: row["settings_version"]
222 )
223 }
224 return states
225 }
226 }
227
228 public func files() throws -> [(path: String, kind: FileKind)] {
229 try database.read { db in
230 try Row.fetchAll(db, sql: "SELECT path, kind FROM files ORDER BY path").map {
231 (path: $0["path"], kind: FileKind(rawValue: $0["kind"]) ?? .org)
232 }
233 }
234 }
235
236 // MARK: - Queries
237 //
238 // `overlay` holds records for open documents with unsaved edits, keyed by path. Their rows
239 // replace that file's indexed rows in every query.
240
241 /// Headings whose title or body contain every word of `query` as a word prefix.
242 public func search(_ query: String, overlay: [String: FileRecord] = [:], limit: Int = 50) throws -> [HeadingLocation] {
243 let terms = query.split(whereSeparator: \.isWhitespace).map(String.init)
244 guard !terms.isEmpty else { return [] }
245 let match = terms.map { "\"" + $0.replacingOccurrences(of: "\"", with: "\"\"") + "\"*" }.joined(separator: " ")
246 let indexed = try database.read { db in
247 try Row.fetchAll(
248 db,
249 sql: """
250 SELECT f.path, f.hash, h.ordinal, h.title, h.start_offset
251 FROM headings_fts
252 JOIN headings h ON h.id = headings_fts.rowid
253 JOIN files f ON f.id = h.file_id
254 WHERE headings_fts MATCH ?
255 ORDER BY bm25(headings_fts)
256 LIMIT ?
257 """,
258 arguments: [match, limit + overlay.count * 10]
259 ).map(location)
260 }
261 // Unsaved buffers get the same word-prefix matching as the full-text index.
262 let prefixes = terms.flatMap(Self.words)
263 let live = overlay.values.sorted { $0.path < $1.path }.flatMap { record in
264 record.headings.filter { heading in
265 let words = Self.words(heading.title + "\n" + heading.body)
266 return prefixes.allSatisfy { prefix in words.contains { $0.hasPrefix(prefix) } }
267 }.map { location(record, $0) }
268 }
269 return Array((live + indexed.filter { overlay[$0.path] == nil }).prefix(limit))
270 }
271
272 /// Headings down to `maxLevel` in org files (not archives or conflict copies), with their
273 /// levels and outline paths, in file order: refile targets.
274 public func outline(maxLevel: Int) throws -> [IndexedHeading] {
275 try database.read { db in
276 try Row.fetchAll(
277 db,
278 sql: """
279 SELECT f.path, f.hash, h.ordinal, h.title, h.start_offset, h.level, h.outline_path
280 FROM headings h JOIN files f ON f.id = h.file_id
281 WHERE h.level <= ? AND f.kind = 'org' ORDER BY f.path, h.ordinal
282 """,
283 arguments: [maxLevel]
284 ).map { row in
285 IndexedHeading(
286 location: location(row), level: row["level"],
287 outlinePath: (row["outline_path"] as String).split(separator: "\u{1F}", omittingEmptySubsequences: false).map(String.init)
288 )
289 }
290 }
291 }
292
293 /// Headings with `:ID: id`. More than one means the ID is duplicated.
294 public func headings(withID id: String, overlay: [String: FileRecord] = [:]) throws -> [HeadingLocation] {
295 let indexed = try database.read { db in
296 try Row.fetchAll(
297 db,
298 sql: """
299 SELECT f.path, f.hash, h.ordinal, h.title, h.start_offset
300 FROM headings h JOIN files f ON f.id = h.file_id
301 WHERE h.org_id = ? ORDER BY f.path, h.ordinal
302 """,
303 arguments: [id]
304 ).map(location)
305 }
306 let live = overlay.values.sorted { $0.path < $1.path }.flatMap { record in
307 record.headings.filter { $0.orgID == id }.map { location(record, $0) }
308 }
309 return indexed.filter { overlay[$0.path] == nil } + live
310 }
311
312 /// IDs used by more than one heading.
313 public func duplicateIDs(overlay: [String: FileRecord] = [:]) throws -> [String: [HeadingLocation]] {
314 let indexed = try database.read { db in
315 try Row.fetchAll(
316 db,
317 sql: """
318 SELECT h.org_id, f.path, f.hash, h.ordinal, h.title, h.start_offset
319 FROM headings h JOIN files f ON f.id = h.file_id
320 WHERE h.org_id IN (SELECT org_id FROM headings WHERE org_id IS NOT NULL GROUP BY org_id HAVING count(*) > 1)
321 OR (h.org_id IS NOT NULL AND ? > 0)
322 ORDER BY f.path, h.ordinal
323 """,
324 arguments: [overlay.count]
325 ).map { (id: $0["org_id"] as String, location: location($0)) }
326 }
327 var byID: [String: [HeadingLocation]] = [:]
328 for row in indexed where overlay[row.location.path] == nil {
329 byID[row.id, default: []].append(row.location)
330 }
331 for record in overlay.values.sorted(by: { $0.path < $1.path }) {
332 for heading in record.headings {
333 if let id = heading.orgID { byID[id, default: []].append(location(record, heading)) }
334 }
335 }
336 return byID.filter { $0.value.count > 1 }
337 }
338
339 /// Lower-cased runs of letters and digits, as the unicode61 tokenizer splits them.
340 static func words(_ text: String) -> [String] {
341 text.lowercased().split { !$0.isLetter && !$0.isNumber }.map(String.init)
342 }
343
344 private func location(_ row: Row) -> HeadingLocation {
345 HeadingLocation(path: row["path"], ordinal: row["ordinal"], title: row["title"], start: row["start_offset"], contentHash: row["hash"])
346 }
347
348 private func location(_ record: FileRecord, _ heading: HeadingRecord) -> HeadingLocation {
349 HeadingLocation(path: record.path, ordinal: heading.ordinal, title: heading.title, start: heading.start, contentHash: record.hash)
350 }
351}