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