Skip to main content

reflex/
meta_update.rs

1//! `meta.db` writes of an incremental index run.
2//!
3//! A run writes only what changed: the rows of added, modified and touched files,
4//! the rows of deleted files (by id), the walk positions that moved, the dirty
5//! flags that flipped, and this branch's hash rows. Every function here runs on a
6//! connection inside a transaction the caller holds, so one run commits once.
7
8use std::collections::HashMap;
9
10use anyhow::{Context, Result};
11use rusqlite::{Connection, OptionalExtension};
12
13use crate::cache::{FileRow, WALK_SEQ_GAP};
14
15/// What `meta.db` holds about one indexed file.
16#[derive(Debug, Clone)]
17pub struct StoredFile {
18    pub id: i64,
19    pub size: u64,
20    pub mtime_ns: i64,
21    pub hash: String,
22    pub walk_seq: i64,
23    pub dirty: bool,
24    /// For the statistics of a run that changes nothing.
25    pub language: String,
26    pub line_count: usize,
27}
28
29impl StoredFile {
30    /// Whether `md` describes the file as it was indexed (same rule as the
31    /// freshness check: an unknown mtime is never equal).
32    pub fn stat_matches(&self, st: &crate::cache::FileStat) -> bool {
33        self.mtime_ns != 0 && self.size == st.size() && self.mtime_ns == st.mtime_ns()
34    }
35}
36
37/// Every `files` row, by path.
38pub fn load_stored_files(conn: &Connection) -> Result<HashMap<String, StoredFile>> {
39    let mut stmt = conn.prepare(
40        "SELECT path, id, size, mtime_ns, hash, walk_seq, dirty_at_index, language, line_count
41             FROM files",
42    )?;
43    let rows = stmt.query_map([], stored_file)?;
44    rows.collect::<Result<HashMap<_, _>, _>>()
45        .context("Failed to read files rows")
46}
47
48fn stored_file(r: &rusqlite::Row<'_>) -> rusqlite::Result<(String, StoredFile)> {
49    Ok((
50        r.get::<_, String>(0)?,
51        StoredFile {
52            id: r.get(1)?,
53            size: r.get::<_, i64>(2)? as u64,
54            mtime_ns: r.get(3)?,
55            hash: r.get(4)?,
56            walk_seq: r.get(5)?,
57            dirty: r.get::<_, i64>(6)? != 0,
58            language: r.get(7)?,
59            line_count: r.get::<_, i64>(8)? as usize,
60        },
61    ))
62}
63
64/// The `files` rows at each of `paths` or under it (a directory): what a library
65/// update needs, by index lookups.
66pub fn load_rows_under(conn: &Connection, paths: &[String]) -> Result<HashMap<String, StoredFile>> {
67    const COLUMNS: &str =
68        "path, id, size, mtime_ns, hash, walk_seq, dirty_at_index, language, line_count";
69    let mut exact = conn.prepare_cached(&format!("SELECT {COLUMNS} FROM files WHERE path = ?"))?;
70    // `p/` < every path under `p` < `p0` ('0' follows '/').
71    let mut under = conn.prepare_cached(&format!(
72        "SELECT {COLUMNS} FROM files WHERE path > ? AND path < ?"
73    ))?;
74    let mut out = HashMap::new();
75    for p in paths {
76        for row in exact.query_map([p], stored_file)? {
77            let (path, file) = row?;
78            out.insert(path, file);
79        }
80        for row in under.query_map([format!("{p}/"), format!("{p}0")], stored_file)? {
81            let (path, file) = row?;
82            out.insert(path, file);
83        }
84    }
85    Ok(out)
86}
87
88/// Number of `files` rows.
89pub fn count_files(conn: &Connection) -> Result<usize> {
90    Ok(conn.query_row("SELECT COUNT(*) FROM files", [], |r| r.get::<_, i64>(0))? as usize)
91}
92
93/// Rows of `files` in `walk_seq` order, probed by value: the first row at or after
94/// `seq` (or, with `before`, the last row before it) whose id is not in `skip`.
95pub fn row_near_seq(
96    conn: &Connection,
97    seq: i64,
98    before: bool,
99    skip: &std::collections::HashSet<i64>,
100) -> Result<Option<(i64, String, i64)>> {
101    let sql = if before {
102        "SELECT id, path, walk_seq FROM files WHERE walk_seq < ? ORDER BY walk_seq DESC LIMIT 16"
103    } else {
104        "SELECT id, path, walk_seq FROM files WHERE walk_seq >= ? ORDER BY walk_seq LIMIT 16"
105    };
106    let mut stmt = conn.prepare_cached(sql)?;
107    let mut from = seq;
108    loop {
109        let rows: Vec<(i64, String, i64)> = stmt
110            .query_map([from], |r| Ok((r.get(0)?, r.get(1)?, r.get(2)?)))?
111            .collect::<Result<_, _>>()?;
112        let Some(last) = rows.last().map(|r| r.2) else {
113            return Ok(None);
114        };
115        let full = rows.len() == 16;
116        if let Some(row) = rows.into_iter().find(|r| !skip.contains(&r.0)) {
117            return Ok(Some(row));
118        }
119        if !full {
120            return Ok(None);
121        }
122        // Sixteen skipped rows in a row: continue past them.
123        from = if before { last } else { last + 1 };
124    }
125}
126
127/// Upsert `rows` (keeping each path's id); returns their ids, in order.
128pub fn upsert_files(conn: &Connection, rows: &[FileRow], now: i64) -> Result<Vec<i64>> {
129    let mut stmt = conn.prepare_cached(
130        "INSERT INTO files
131             (path, last_indexed, language, line_count, size, mtime_ns, hash,
132              dirty_at_index, walk_seq)
133         VALUES (?, ?, ?, ?, ?, ?, ?, ?, ?)
134         ON CONFLICT(path) DO UPDATE SET
135             last_indexed = excluded.last_indexed,
136             language = excluded.language,
137             line_count = excluded.line_count,
138             size = excluded.size,
139             mtime_ns = excluded.mtime_ns,
140             hash = excluded.hash,
141             dirty_at_index = excluded.dirty_at_index,
142             walk_seq = excluded.walk_seq
143         RETURNING id",
144    )?;
145    let mut ids = Vec::with_capacity(rows.len());
146    for row in rows {
147        let id: i64 = stmt.query_row(
148            rusqlite::params![
149                row.path,
150                now,
151                row.language,
152                row.line_count as i64,
153                row.size as i64,
154                row.mtime_ns,
155                row.hash,
156                row.dirty as i64,
157                row.walk_seq,
158            ],
159            |r| r.get(0),
160        )?;
161        ids.push(id);
162    }
163    Ok(ids)
164}
165
166/// `UPDATE files SET walk_seq` for each `(id, walk_seq)`.
167pub fn set_walk_seqs(conn: &Connection, updates: &[(i64, i64)]) -> Result<()> {
168    let mut stmt = conn.prepare_cached("UPDATE files SET walk_seq = ? WHERE id = ?")?;
169    for (id, seq) in updates {
170        stmt.execute(rusqlite::params![seq, id])?;
171    }
172    Ok(())
173}
174
175/// `UPDATE files SET dirty_at_index` for each `(id, dirty)`.
176pub fn set_dirty_flags(conn: &Connection, updates: &[(i64, bool)]) -> Result<()> {
177    let mut stmt = conn.prepare_cached("UPDATE files SET dirty_at_index = ? WHERE id = ?")?;
178    for (id, dirty) in updates {
179        stmt.execute(rusqlite::params![*dirty as i64, id])?;
180    }
181    Ok(())
182}
183
184/// `UPDATE files SET size, mtime_ns, dirty_at_index` for files whose bytes are
185/// unchanged (a `touch`, or an edit reverted byte for byte).
186pub fn refresh_stats(conn: &Connection, updates: &[(i64, u64, i64, bool)]) -> Result<()> {
187    let mut stmt = conn.prepare_cached(
188        "UPDATE files SET size = ?, mtime_ns = ?, dirty_at_index = ? WHERE id = ?",
189    )?;
190    for (id, size, mtime_ns, dirty) in updates {
191        stmt.execute(rusqlite::params![*size as i64, mtime_ns, *dirty as i64, id])?;
192    }
193    Ok(())
194}
195
196/// Delete the rows of `ids`; the cascades remove their branch, dependency,
197/// export and symbol rows and null importers' resolved ids.
198pub fn delete_files(conn: &Connection, ids: &[i64]) -> Result<()> {
199    let mut stmt = conn.prepare_cached("DELETE FROM files WHERE id = ?")?;
200    for id in ids {
201        stmt.execute([id])?;
202    }
203    Ok(())
204}
205
206/// `statistics` key: the branch whose `file_branches` rows the last completed run
207/// synced with `files`. Written in the transaction that syncs them; a run on that
208/// branch then needs to touch only the rows it rewrites.
209pub const SYNCED_BRANCH_KEY: &str = "synced_branch";
210
211/// Make `branch_id`'s rows name every file with its current hash: inserts the
212/// missing ones and updates the stale ones, leaving the rest alone. Records
213/// `branch` as the synced branch.
214pub fn sync_branch_rows(
215    conn: &Connection,
216    branch_id: i64,
217    branch: &str,
218    now: i64,
219) -> Result<usize> {
220    let changed = conn.execute(
221        "INSERT OR REPLACE INTO file_branches (file_id, branch_id, hash, last_indexed)
222         SELECT f.id, ?1, f.hash, ?2 FROM files f
223         WHERE NOT EXISTS (
224             SELECT 1 FROM file_branches fb
225             WHERE fb.file_id = f.id AND fb.branch_id = ?1 AND fb.hash = f.hash)",
226        rusqlite::params![branch_id, now],
227    )?;
228    set_statistic(conn, SYNCED_BRANCH_KEY, branch, now)?;
229    Ok(changed)
230}
231
232/// Point `branch_id`'s rows of the given files at their hashes: `(file id, hash)`.
233/// A run on the branch that last synced every row (see [`sync_branch_rows`]) needs
234/// only the rows it rewrote.
235pub fn set_branch_rows(
236    conn: &Connection,
237    branch_id: i64,
238    rows: &[(i64, &str)],
239    now: i64,
240) -> Result<()> {
241    let mut stmt = conn.prepare_cached(
242        "INSERT OR REPLACE INTO file_branches (file_id, branch_id, hash, last_indexed)
243         VALUES (?, ?, ?, ?)",
244    )?;
245    for (id, hash) in rows {
246        stmt.execute(rusqlite::params![id, branch_id, hash, now])?;
247    }
248    Ok(())
249}
250
251/// `statistics.value` for `key`, if set.
252pub fn get_statistic(conn: &Connection, key: &str) -> Result<Option<String>> {
253    Ok(conn
254        .query_row("SELECT value FROM statistics WHERE key = ?", [key], |r| {
255            r.get(0)
256        })
257        .optional()?)
258}
259
260/// Set `statistics.value` for `key`.
261pub fn set_statistic(conn: &Connection, key: &str, value: &str, now: i64) -> Result<()> {
262    conn.execute(
263        "INSERT OR REPLACE INTO statistics (key, value, updated_at) VALUES (?, ?, ?)",
264        rusqlite::params![key, value, now],
265    )?;
266    Ok(())
267}
268
269/// The walk position each file should have, given each file's stored position
270/// (`None` for a new file) in the current walk order.
271///
272/// Changes as few positions as possible: the longest run of stored positions that
273/// is already increasing is kept, and every other file gets a value between its
274/// kept neighbours. When a gap is too narrow, every file is renumbered at
275/// [`WALK_SEQ_GAP`] spacing (what a full build writes).
276pub fn plan_walk_seq(stored: &[Option<i64>]) -> Vec<i64> {
277    let n = stored.len();
278    // The usual case: every file has a position and they already increase.
279    if stored.iter().all(Option::is_some) && stored.windows(2).all(|w| w[0] < w[1]) {
280        return stored.iter().map(|v| v.expect("checked")).collect();
281    }
282    let renumber = || (0..n).map(|i| i as i64 * WALK_SEQ_GAP).collect::<Vec<_>>();
283
284    // Longest strictly increasing subsequence of the stored values (patience).
285    let known: Vec<(usize, i64)> = stored
286        .iter()
287        .enumerate()
288        .filter_map(|(i, v)| v.map(|v| (i, v)))
289        .collect();
290    if known.is_empty() {
291        return renumber();
292    }
293    let mut tails: Vec<usize> = Vec::new(); // index into `known` of each pile's top
294    let mut prev: Vec<Option<usize>> = vec![None; known.len()];
295    for k in 0..known.len() {
296        let v = known[k].1;
297        let pos = tails.partition_point(|&t| known[t].1 < v);
298        if pos > 0 {
299            prev[k] = Some(tails[pos - 1]);
300        }
301        if pos == tails.len() {
302            tails.push(k);
303        } else {
304            tails[pos] = k;
305        }
306    }
307    let mut keep = vec![false; n];
308    let mut cur = tails.last().copied();
309    while let Some(k) = cur {
310        keep[known[k].0] = true;
311        cur = prev[k];
312    }
313
314    let mut out: Vec<i64> = vec![0; n];
315    let mut i = 0;
316    let mut lo: Option<i64> = None; // value of the last kept file before `i`
317    while i < n {
318        if keep[i] {
319            let v = stored[i].expect("kept files have a value");
320            out[i] = v;
321            lo = Some(v);
322            i += 1;
323            continue;
324        }
325        // A run of files to place, up to the next kept file (or the end).
326        let start = i;
327        while i < n && !keep[i] {
328            i += 1;
329        }
330        let count = (i - start) as i64;
331        let hi = (i < n).then(|| stored[i].expect("kept files have a value"));
332        let (base, step) = match (lo, hi) {
333            (Some(lo), Some(hi)) => {
334                let step = (hi - lo) / (count + 1);
335                if step < 1 {
336                    return renumber();
337                }
338                (lo, step)
339            }
340            (Some(lo), None) => (lo, WALK_SEQ_GAP),
341            (None, Some(hi)) => match hi.checked_sub((count + 1) * WALK_SEQ_GAP) {
342                Some(base) => (base, WALK_SEQ_GAP),
343                None => return renumber(),
344            },
345            (None, None) => return renumber(),
346        };
347        for (j, slot) in out[start..i].iter_mut().enumerate() {
348            match base.checked_add((j as i64 + 1) * step) {
349                Some(v) => *slot = v,
350                None => return renumber(),
351            }
352        }
353    }
354    out
355}
356
357#[cfg(test)]
358mod tests {
359    use super::*;
360
361    fn increasing(v: &[i64]) -> bool {
362        v.windows(2).all(|w| w[0] < w[1])
363    }
364
365    #[test]
366    fn unchanged_order_keeps_every_value() {
367        let stored = [Some(0), Some(10), Some(20)];
368        assert_eq!(plan_walk_seq(&stored), vec![0, 10, 20]);
369    }
370
371    #[test]
372    fn a_new_file_goes_between_its_neighbours() {
373        let g = WALK_SEQ_GAP;
374        let stored = [Some(0), None, Some(g), Some(2 * g)];
375        let out = plan_walk_seq(&stored);
376        assert!(increasing(&out));
377        assert_eq!(out[0], 0);
378        assert_eq!(out[2], g);
379        assert_eq!(out[3], 2 * g);
380    }
381
382    #[test]
383    fn new_files_at_either_end() {
384        let g = WALK_SEQ_GAP;
385        let stored = [None, None, Some(0), Some(g), None];
386        let out = plan_walk_seq(&stored);
387        assert!(increasing(&out), "{out:?}");
388        assert_eq!(&out[2..4], &[0, g]);
389    }
390
391    #[test]
392    fn a_moved_file_is_the_only_one_renumbered() {
393        let g = WALK_SEQ_GAP;
394        // The file at position 3 used to come first.
395        let stored = [Some(g), Some(2 * g), Some(3 * g), Some(0), Some(4 * g)];
396        let out = plan_walk_seq(&stored);
397        assert!(increasing(&out), "{out:?}");
398        let changed = out
399            .iter()
400            .zip(&stored)
401            .filter(|(a, b)| Some(**a) != **b)
402            .count();
403        assert_eq!(changed, 1);
404    }
405
406    #[test]
407    fn a_full_gap_renumbers() {
408        let stored = [Some(0), None, None, Some(2)];
409        let out = plan_walk_seq(&stored);
410        assert!(increasing(&out));
411        assert_eq!(
412            out,
413            vec![0, WALK_SEQ_GAP, 2 * WALK_SEQ_GAP, 3 * WALK_SEQ_GAP]
414        );
415    }
416
417    #[test]
418    fn random_orders_always_come_out_increasing() {
419        let mut state = 12345u64;
420        let mut next = || {
421            state = state
422                .wrapping_mul(6364136223846793005)
423                .wrapping_add(1442695040888963407);
424            (state >> 33) as i64
425        };
426        for _ in 0..200 {
427            let n = (next() % 40) as usize;
428            let stored: Vec<Option<i64>> = (0..n)
429                .map(|_| {
430                    if next() % 4 == 0 {
431                        None
432                    } else {
433                        Some(next() % 1000 * WALK_SEQ_GAP / 7)
434                    }
435                })
436                .collect();
437            // Distinct stored values, as in the table.
438            let mut seen = std::collections::HashSet::new();
439            let stored: Vec<Option<i64>> = stored
440                .into_iter()
441                .map(|v| v.filter(|x| seen.insert(*x)))
442                .collect();
443            let out = plan_walk_seq(&stored);
444            assert_eq!(out.len(), n);
445            assert!(increasing(&out), "{stored:?} -> {out:?}");
446        }
447    }
448}