Skip to main content

kizz_store/
store.rs

1// Copyright (c) 2026 Sakura Industries LLC.
2//
3// SPDX-License-Identifier: AGPL-3.0-only
4
5//! The cache database: `SurrealKV`, embedded, in the `db` directory of the cache.
6//!
7//! A [`Store`] is shared by the threads of one process. Every read and write goes
8//! through a [`Txn`], which sees a consistent snapshot; a write transaction changes
9//! nothing until [`Txn::commit`], and then changes every record it wrote or none.
10//!
11//! `SurrealKV` commits and closes asynchronously on a Tokio runtime, so the store owns a
12//! small runtime and waits for each commit and for the close. After each commit the
13//! store hands the write-ahead log to the operating system, so a committed record
14//! survives a crash of the process.
15//!
16//! The store starts no thread of its own ("Kizz never panics"), so it cannot fail
17//! when the system cannot start one. Its runtime is a current-thread runtime, which
18//! runs `SurrealKV`'s tasks on the threads that call the store, while they wait for a
19//! commit or the close. Kizz builds `SurrealKV` from a patched copy in
20//! `vendor/surrealkv`, and the store opens it with the copy's direct clock,
21//! [`ClockMode::Direct`], which reads the system clock on every reading instead of
22//! keeping a thread that brings it up to date. Its stall thresholds, [`STALL_THRESHOLD`],
23//! are so high that `SurrealKV` never paces or stalls a write, which a cache of small
24//! records does not need. When it replays several log segments after a crash,
25//! the copy starts a thread when it can and otherwise replays them on the thread
26//! that opens the store.
27//!
28//! The store waits for `SurrealKV` with `Runtime::block_on` only after it checks,
29//! with `Handle::try_current`, that the calling thread is in no runtime, because
30//! `block_on` panics when it is called within an asynchronous execution context
31//! ("Kizz never panics"); a call from inside a runtime is
32//! [`StoreError::InsideRuntime`] instead. Its runtime never panics when it is
33//! dropped either: inside an asynchronous context, where dropping a Tokio runtime
34//! panics, it shuts down in the background instead.
35//!
36//! When the store creates the database it writes [`SCHEMA_VERSION`] and the current
37//! [`CacheIdentity`] into it. It refuses to open a database with another version,
38//! and then one whose identity differs from the current one or that has none,
39//! because the cache is not portable between machines and users. It never wipes a
40//! cache by itself:
41//! `kizz cache reset --all` does, after asking, through [`Store::inventory`], which
42//! counts the entries of a cache of any schema version and reads its identity, and
43//! [`Store::wipe`].
44
45use std::{
46    collections::BTreeSet,
47    fs, io,
48    path::{Path, PathBuf},
49};
50
51use surrealkv::{
52    ClockMode, Durability, LSMIterator as _, Mode, Options, ReadOptions, Transaction, Tree,
53    TreeBuilder,
54};
55
56use crate::{
57    identity::{CacheIdentity, IdentityDifference, IdentityKey, identity_differences_text},
58    records::{
59        Family, PositionKey, Record, RecordKey, SchemaKey, SchemaVersion, TaskId, database_key,
60    },
61};
62
63/// The name of the database directory in the cache directory.
64pub const DATABASE_DIR: &str = "db";
65
66/// The name a wiped database directory has while [`Store::wipe`] removes it.
67const WIPED_DIR: &str = "db.wiped";
68
69/// The number of immutable memory tables, and of level-0 files, at which `SurrealKV`
70/// would stall writes, as the store sets it: the largest number there is.
71///
72/// `SurrealKV` paces writes once a count passes 2 below its memory-table threshold
73/// or 4 below its level-0 threshold, and stalls them at the threshold, so with this
74/// value it would take more than `usize::MAX - 4` memory tables or files in one
75/// database, which no process can hold: write pacing, which waited on a thread in
76/// published `SurrealKV`, never runs, and no write stalls.
77pub const STALL_THRESHOLD: usize = usize::MAX;
78
79/// The options the store opens the database in `path` with: the direct clock, which
80/// starts no thread, and stall thresholds that keep write pacing from running.
81fn tree_options(path: PathBuf) -> Options {
82    Options::new_with_clock(ClockMode::Direct)
83        .with_path(path)
84        .with_memtable_stall_threshold(STALL_THRESHOLD)
85        .with_l0_stall_threshold(STALL_THRESHOLD)
86}
87
88/// The version of the record encoding that this build of kizz reads and writes.
89///
90/// Version 2 replaced the first step record with the full one: the step
91/// specification, the observations with their path states, and why the step ran.
92/// Version 3 added the cache check's reasons, with the differences it found, when
93/// each record's observations were written, and the failure message of a missing
94/// or non-executable program. Version 4 added the reason a run's result was not
95/// cached, which marks a record that is never a cache hit, and the exit of a
96/// command that could not start. Version 5 added explanations: the verdict of the
97/// most recent build in step positions, the parts of the task program and how
98/// output names the task in task records, and the position, build, and time of
99/// each last writer. Version 6 added the reason for the result of a command that
100/// exited with a code of its own after the build was interrupted, which, like a
101/// command that a signal stopped then, is never a cache hit. Version 7 added the
102/// owners of step records: the tasks that produced or used each record, which path
103/// resets and `kizz cache clean` use. Version 8 added task programs as last
104/// writers: each last writer names its task and either the step that wrote the path,
105/// with its position, or the task program, and explanations name a task program
106/// that last wrote a changed input. Version 9 added the owner, as user and group
107/// numbers, to every regular-file state, the mode and owner to every directory
108/// state, and the permission and owner changes that a cache check finds. Version 10
109/// added the `timestamps` option to the step specification, the modification and
110/// change times to every directory state, and the timestamp change that a cache
111/// check finds. Version 11 keeps directory listings in the order the file system
112/// returned their entries, with a hash of that order and a hash of the same entries
113/// sorted, and adds the names of the entries that changed and the order change to
114/// what a cache check finds. Version 12 adds the reason for a run in which files
115/// changed after the command first read them or ran them, which lists each such
116/// file and whether the command wrote it, and, like the other reasons a run's
117/// result is not cached, marks a record that is never a cache hit. Version 13 adds
118/// the xattr access bit, the extended attributes recorded with a path whose
119/// attributes the command read or listed, each name with a hash of its value, for
120/// the path and, for a symbolic link, for what it points to, and the change that
121/// lists the attributes that appeared, disappeared, or changed. Version 14 adds the
122/// numbers of the system calls that a command made and that the tracer does not
123/// know to every step record, whether or not its result was cached, and the reason
124/// for a run that made such calls, which, like the other reasons a run's result is
125/// not cached, marks a record that is never a cache hit. Version 15 adds the
126/// connections that a command made to IPv4 and IPv6 addresses and to Unix sockets,
127/// by path or abstract name, to every step record, whether or not its result was
128/// cached; they never keep a result out of the cache. Version 16 adds the cache
129/// identity, in the `meta/` family: the host name, the effective user and group, the
130/// supplementary groups, the umask, the machine architecture, and the CPU model of
131/// the process that created the database, which every later open compares with the
132/// current values. Version 17 adds the machine state that a command started with to
133/// every step record, the `machine` names to the step specification, the machine
134/// state values that a cache check finds changed, and the reasons that name a change
135/// of the `machine` names or of the machine state. Version 18 adds the reason of a
136/// command that runs because its task is marked `cache=never`, to step records and
137/// to the explanations of step positions. Version 19 adds the reason of a command
138/// that runs because `kizz run --no-cache` was given, to step records and to the
139/// explanations of step positions. Version 20 records explicit untraced execution
140/// and its explanation, with a distinct key and no reuse across builds.
141pub const SCHEMA_VERSION: u32 = 20;
142
143/// Why a store operation failed.
144#[derive(Debug, thiserror::Error)]
145pub enum StoreError {
146    /// The database directory could not be created.
147    #[error("cannot create the cache database directory `{}`", path.display())]
148    CreateDir {
149        /// The database directory.
150        path: PathBuf,
151        /// The cause.
152        #[source]
153        source: io::Error,
154    },
155    /// The runtime that drives the database could not start.
156    #[error("cannot start the cache database runtime")]
157    Runtime(#[source] io::Error),
158    /// The database reported an error.
159    #[error("the cache database failed")]
160    Database(#[from] surrealkv::Error),
161    /// Another transaction committed a change to a record this one wrote, so this
162    /// one changed nothing.
163    #[error("a concurrent transaction changed the same cache records; nothing was written")]
164    Conflict,
165    /// The store was called from inside an asynchronous execution context, where
166    /// waiting for the database would panic, so it did not wait.
167    #[error("the cache database cannot be waited for from inside an asynchronous task")]
168    InsideRuntime,
169    /// A record could not be encoded.
170    #[error("cannot encode a {family}: {message}")]
171    Encode {
172        /// The family of the record.
173        family: Family,
174        /// What went wrong.
175        message: String,
176    },
177    /// A stored record could not be decoded.
178    #[error("cannot decode a stored {family}")]
179    Decode {
180        /// The family of the record.
181        family: Family,
182        /// The cause.
183        #[source]
184        source: minicbor::decode::Error,
185    },
186    /// A stored key is not a key of its family.
187    #[error("the cache database holds a malformed {family} key")]
188    MalformedKey {
189        /// The family of the key.
190        family: Family,
191    },
192    /// The database was written with another schema version.
193    #[error(
194        "the cache database at `{}` has schema version {found}, but this kizz uses schema \
195         version {expected}; run `kizz cache reset --all` to wipe the cache",
196        path.display()
197    )]
198    SchemaMismatch {
199        /// The database directory.
200        path: PathBuf,
201        /// The version stored in the database.
202        found: u32,
203        /// The version this build uses, [`SCHEMA_VERSION`].
204        expected: u32,
205    },
206    /// The database was stamped with another cache identity: another machine or user
207    /// created it.
208    #[error(
209        "the cache database at `{}` belongs to another machine or user, so kizz refuses to \
210         use it: {}; the cache is not portable between machines and users; run `kizz cache \
211         reset --all` to wipe the cache, or set `KIZZ_CACHE_DIR` to use another cache",
212        path.display(),
213        identity_differences_text(differences)
214    )]
215    IdentityMismatch {
216        /// The database directory.
217        path: PathBuf,
218        /// Each value that differs, stored and current, in the order of the fields of
219        /// [`CacheIdentity`].
220        differences: Vec<IdentityDifference>,
221    },
222    /// The database has this schema version but no cache identity, so kizz cannot
223    /// tell which machine and user it belongs to.
224    #[error(
225        "the cache database at `{}` has no cache identity, so kizz cannot tell which machine \
226         and user it belongs to and refuses to use it; the cache is not portable between \
227         machines and users; run `kizz cache reset --all` to wipe the cache, or set \
228         `KIZZ_CACHE_DIR` to use another cache",
229        path.display()
230    )]
231    IdentityMissing {
232        /// The database directory.
233        path: PathBuf,
234    },
235    /// The database directory could not be removed.
236    #[error("cannot remove the cache database `{}`", path.display())]
237    Wipe {
238        /// The directory that could not be removed.
239        path: PathBuf,
240        /// The cause.
241        #[source]
242        source: io::Error,
243    },
244}
245
246/// How many entries of each family a set of cache entries holds, and how many tasks
247/// they belong to.
248#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
249pub struct EntryCounts {
250    /// The distinct tasks of the task records, step positions, and learned order,
251    /// and the tasks taken out of the owners of step records.
252    pub tasks: usize,
253    /// Step records.
254    pub steps: usize,
255    /// Step records that are kept but lose owners, apart from the step records
256    /// counted in [`EntryCounts::steps`].
257    pub shared_steps: usize,
258    /// Step positions.
259    pub positions: usize,
260    /// Task records.
261    pub task_records: usize,
262    /// Learned-order entries.
263    pub orders: usize,
264    /// Last-writer entries.
265    pub writers: usize,
266}
267
268impl EntryCounts {
269    /// Whether there is no entry at all and no step record loses an owner.
270    #[must_use]
271    pub const fn is_empty(&self) -> bool {
272        self.steps == 0
273            && self.shared_steps == 0
274            && self.positions == 0
275            && self.task_records == 0
276            && self.orders == 0
277            && self.writers == 0
278    }
279}
280
281/// What a whole cache holds, as [`Store::inventory`] counts it.
282#[derive(Debug, Clone, Default, PartialEq, Eq)]
283pub struct Inventory {
284    /// The entries of every family but the database facts: the schema version and the
285    /// cache identity.
286    pub entries: EntryCounts,
287    /// The schema version stored in the database, or `None` when there is no
288    /// database or it holds no readable version.
289    pub schema_version: Option<u32>,
290    /// The cache identity stored in the database, or `None` when there is no
291    /// database or it holds no readable identity.
292    pub identity: Option<CacheIdentity>,
293}
294
295/// The cache database, shared by the threads of one process.
296pub struct Store {
297    /// The `SurrealKV` tree. Declared before the runtime so that it is dropped first.
298    tree: Tree,
299    /// The runtime that drives the tree's commits and background work.
300    runtime: StoreRuntime,
301    /// The database directory.
302    path: PathBuf,
303    /// Whether the tree has been closed.
304    closed: bool,
305}
306
307impl std::fmt::Debug for Store {
308    fn fmt(
309        &self,
310        f: &mut std::fmt::Formatter<'_>,
311    ) -> std::fmt::Result {
312        f.debug_struct("Store")
313            .field("path", &self.path)
314            .finish_non_exhaustive()
315    }
316}
317
318impl Store {
319    /// Opens the database in the `db` directory of `cache_dir`, creating it, with the
320    /// current schema version and the current [`CacheIdentity`], if it does not exist.
321    ///
322    /// An existing database's schema version is checked first, then its identity.
323    ///
324    /// # Errors
325    ///
326    /// [`StoreError::SchemaMismatch`] when the database has another schema version,
327    /// [`StoreError::IdentityMismatch`] when it has another identity,
328    /// [`StoreError::IdentityMissing`] when it has this schema version but no
329    /// identity, and another [`StoreError`] when the database cannot be created or
330    /// opened.
331    pub fn open(cache_dir: &Path) -> Result<Self, StoreError> {
332        let store = Self::open_tree(cache_dir)?;
333        store.check_stamp(&CacheIdentity::current())?;
334        Ok(store)
335    }
336
337    /// Counts the entries of the database in the `db` directory of `cache_dir`,
338    /// whatever its schema version, by their keys alone, and reads its schema version
339    /// and its identity when it can, without decoding another record or changing
340    /// anything. A cache without a database has no entries.
341    ///
342    /// # Errors
343    ///
344    /// A [`StoreError`] when the database cannot be opened or read.
345    pub fn inventory(cache_dir: &Path) -> Result<Inventory, StoreError> {
346        if !cache_dir.join(DATABASE_DIR).is_dir() {
347            return Ok(Inventory::default());
348        }
349        let store = Self::open_tree(cache_dir)?;
350        let inventory = {
351            let txn = store.read()?;
352            let schema_version = txn
353                .inner
354                .get(database_key::<SchemaVersion>(&SchemaKey))?
355                .and_then(|bytes| decode::<SchemaVersion>(&bytes).ok())
356                .map(|schema| schema.version);
357            let identity = txn
358                .inner
359                .get(database_key::<CacheIdentity>(&IdentityKey))?
360                .and_then(|bytes| decode::<CacheIdentity>(&bytes).ok());
361            let task_keys = txn.raw_keys(Family::Task)?;
362            let position_keys = txn.raw_keys(Family::Position)?;
363            let order_keys = txn.raw_keys(Family::Order)?;
364            let tasks: BTreeSet<TaskId> = task_keys
365                .iter()
366                .chain(&order_keys)
367                .filter_map(|key| TaskId::decode_key(key))
368                .chain(
369                    position_keys
370                        .iter()
371                        .filter_map(|key| PositionKey::decode_key(key))
372                        .map(|key| key.task),
373                )
374                .collect();
375            Inventory {
376                entries: EntryCounts {
377                    tasks: tasks.len(),
378                    steps: txn.raw_keys(Family::Step)?.len(),
379                    shared_steps: 0,
380                    positions: position_keys.len(),
381                    task_records: task_keys.len(),
382                    orders: order_keys.len(),
383                    writers: txn.raw_keys(Family::Writer)?.len(),
384                },
385                schema_version,
386                identity,
387            }
388        };
389        store.close()?;
390        Ok(inventory)
391    }
392
393    /// Wipes the whole cache database in the `db` directory of `cache_dir`, whatever
394    /// its schema version and identity; the next [`Store::open`] creates an empty one,
395    /// stamped with the current identity. The caller holds the cache lock, so no
396    /// process has the database open.
397    ///
398    /// The directory is first renamed, in one step, so a crash during the removal
399    /// leaves no partial database behind, only a directory that the next wipe
400    /// removes.
401    ///
402    /// # Errors
403    ///
404    /// [`StoreError::Wipe`] when the directory cannot be renamed or removed.
405    pub fn wipe(cache_dir: &Path) -> Result<(), StoreError> {
406        let path = cache_dir.join(DATABASE_DIR);
407        let wiped = cache_dir.join(WIPED_DIR);
408        let remove = |dir: &Path| {
409            match fs::remove_dir_all(dir) {
410                Err(error) if error.kind() != io::ErrorKind::NotFound => {
411                    Err(StoreError::Wipe {
412                        path: dir.to_path_buf(),
413                        source: error,
414                    })
415                },
416                _ => Ok(()),
417            }
418        };
419        remove(&wiped)?;
420        match fs::rename(&path, &wiped) {
421            Ok(()) => remove(&wiped),
422            Err(error) if error.kind() == io::ErrorKind::NotFound => Ok(()),
423            Err(error) => {
424                Err(StoreError::Wipe {
425                    path,
426                    source: error,
427                })
428            },
429        }
430    }
431
432    /// Opens the database in the `db` directory of `cache_dir`, creating it if it does
433    /// not exist, without checking or writing the schema version.
434    fn open_tree(cache_dir: &Path) -> Result<Self, StoreError> {
435        let path = cache_dir.join(DATABASE_DIR);
436        fs::create_dir_all(&path).map_err(|source| {
437            StoreError::CreateDir {
438                path: path.clone(),
439                source,
440            }
441        })?;
442        // A current-thread runtime starts no thread: the tree's tasks run on the
443        // threads that wait in `block_on`.
444        let runtime = tokio::runtime::Builder::new_current_thread()
445            .enable_all()
446            .build()
447            .map_err(StoreError::Runtime)?;
448        let tree = {
449            // The tree starts its background tasks on the runtime it is opened in.
450            let _entered = runtime.enter();
451            TreeBuilder::with_options(tree_options(path.clone())).build()?
452        };
453        Ok(Self {
454            tree,
455            runtime: StoreRuntime(Some(runtime)),
456            path,
457            closed: false,
458        })
459    }
460
461    /// The database directory.
462    #[must_use]
463    pub fn path(&self) -> &Path {
464        &self.path
465    }
466
467    /// Begins a read-only transaction.
468    ///
469    /// # Errors
470    ///
471    /// [`StoreError::Database`] when the database cannot begin one.
472    pub fn read(&self) -> Result<Txn<'_>, StoreError> {
473        Ok(Txn {
474            store: self,
475            inner: self.tree.begin_with_mode(Mode::ReadOnly)?,
476        })
477    }
478
479    /// Begins a read-write transaction, which changes nothing until it is committed.
480    ///
481    /// # Errors
482    ///
483    /// [`StoreError::Database`] when the database cannot begin one.
484    pub fn write(&self) -> Result<Txn<'_>, StoreError> {
485        Ok(Txn {
486            store: self,
487            inner: self.tree.begin_with_mode(Mode::ReadWrite)?,
488        })
489    }
490
491    /// Closes the database, after every commit that has started.
492    ///
493    /// # Errors
494    ///
495    /// [`StoreError::Database`] when closing fails.
496    pub fn close(mut self) -> Result<(), StoreError> {
497        self.close_inner()
498    }
499
500    /// Closes the tree once.
501    fn close_inner(&mut self) -> Result<(), StoreError> {
502        if self.closed {
503            return Ok(());
504        }
505        self.closed = true;
506        wait_for(&self.runtime, self.tree.close())??;
507        Ok(())
508    }
509
510    /// Writes the schema version and `current`, the identity of this process, into a
511    /// new database, in one transaction, or checks the version of an existing one
512    /// first and then its identity against `current`.
513    ///
514    /// A database of this schema version always gets its identity in the transaction
515    /// that creates it, so one that has none is refused: kizz cannot tell whose
516    /// cache it is, and only `kizz cache reset --all` makes it usable again.
517    fn check_stamp(
518        &self,
519        current: &CacheIdentity,
520    ) -> Result<(), StoreError> {
521        let mut txn = self.write()?;
522        match txn.get::<SchemaVersion>(&SchemaKey)? {
523            Some(SchemaVersion {
524                version: SCHEMA_VERSION,
525            }) => {},
526            Some(SchemaVersion { version }) => {
527                return Err(StoreError::SchemaMismatch {
528                    path: self.path.clone(),
529                    found: version,
530                    expected: SCHEMA_VERSION,
531                });
532            },
533            None => {
534                txn.put(&SchemaKey, &SchemaVersion {
535                    version: SCHEMA_VERSION,
536                })?;
537                txn.put(&IdentityKey, current)?;
538                return txn.commit();
539            },
540        }
541        let Some(stored) = txn.get::<CacheIdentity>(&IdentityKey)? else {
542            return Err(StoreError::IdentityMissing {
543                path: self.path.clone(),
544            });
545        };
546        let differences = stored.differences(current);
547        if differences.is_empty() {
548            Ok(())
549        } else {
550            Err(StoreError::IdentityMismatch {
551                path: self.path.clone(),
552                differences,
553            })
554        }
555    }
556}
557
558impl Drop for Store {
559    fn drop(&mut self) {
560        // Nothing can report a failure here; the next open recovers from the log.
561        let _ignored: Result<(), StoreError> = self.close_inner();
562    }
563}
564
565/// A transaction on the [`Store`]: a consistent snapshot of the records, and for a
566/// write transaction, the changes to commit. Dropping it without committing discards
567/// the changes.
568pub struct Txn<'s> {
569    /// The store.
570    store: &'s Store,
571    /// The `SurrealKV` transaction.
572    inner: Transaction,
573}
574
575impl std::fmt::Debug for Txn<'_> {
576    fn fmt(
577        &self,
578        f: &mut std::fmt::Formatter<'_>,
579    ) -> std::fmt::Result {
580        f.debug_struct("Txn")
581            .field("store", &self.store)
582            .finish_non_exhaustive()
583    }
584}
585
586impl Txn<'_> {
587    /// The record of type `R` at `key`, if there is one.
588    ///
589    /// # Errors
590    ///
591    /// [`StoreError::Database`] when the read fails, and [`StoreError::Decode`] when
592    /// the stored record cannot be decoded.
593    pub fn get<R: Record>(
594        &self,
595        key: &R::Key,
596    ) -> Result<Option<R>, StoreError> {
597        self.inner
598            .get(database_key::<R>(key))?
599            .map(|bytes| decode::<R>(&bytes))
600            .transpose()
601    }
602
603    /// Writes `record` at `key`, replacing any record there, when the transaction
604    /// commits.
605    ///
606    /// # Errors
607    ///
608    /// [`StoreError::Encode`] when the record cannot be encoded, and
609    /// [`StoreError::Database`] when the transaction is read-only.
610    pub fn put<R: Record>(
611        &mut self,
612        key: &R::Key,
613        record: &R,
614    ) -> Result<(), StoreError> {
615        let bytes = minicbor::to_vec(record).map_err(|error| {
616            StoreError::Encode {
617                family: R::FAMILY,
618                message: error.to_string(),
619            }
620        })?;
621        self.inner.set(database_key::<R>(key), bytes)?;
622        Ok(())
623    }
624
625    /// Deletes the record of type `R` at `key`, if there is one, when the transaction
626    /// commits.
627    ///
628    /// # Errors
629    ///
630    /// [`StoreError::Database`] when the transaction is read-only.
631    pub fn delete<R: Record>(
632        &mut self,
633        key: &R::Key,
634    ) -> Result<(), StoreError> {
635        self.inner.delete(database_key::<R>(key))?;
636        Ok(())
637    }
638
639    /// Every record of type `R` whose key, after the family prefix, starts with
640    /// `prefix`, in key order. An empty prefix selects the whole family.
641    ///
642    /// # Errors
643    ///
644    /// [`StoreError::Database`] when the scan fails, [`StoreError::MalformedKey`] and
645    /// [`StoreError::Decode`] when a stored key or record cannot be decoded.
646    pub fn scan<R: Record>(
647        &self,
648        prefix: &[u8],
649    ) -> Result<Vec<(R::Key, R)>, StoreError> {
650        let family = R::FAMILY.prefix();
651        let mut start = family.to_vec();
652        start.extend_from_slice(prefix);
653        let mut options = ReadOptions::new();
654        options.set_iterate_upper_bound(prefix_end(&start));
655        options.set_iterate_lower_bound(Some(start));
656        let mut iter = self.inner.range_with_options(&options)?;
657        let mut records = Vec::new();
658        let mut valid = iter.seek_first()?;
659        while valid {
660            let key = iter
661                .key()
662                .user_key()
663                .strip_prefix(family)
664                .and_then(R::Key::decode_key)
665                .ok_or(StoreError::MalformedKey { family: R::FAMILY })?;
666            let record = decode::<R>(&iter.value()?)?;
667            records.push((key, record));
668            valid = iter.next()?;
669        }
670        Ok(records)
671    }
672
673    /// The key of every entry of `family`, after the family prefix, in key order,
674    /// without decoding a key or a record.
675    fn raw_keys(
676        &self,
677        family: Family,
678    ) -> Result<Vec<Vec<u8>>, StoreError> {
679        let start = family.prefix().to_vec();
680        let mut options = ReadOptions::new();
681        options.set_iterate_upper_bound(prefix_end(&start));
682        options.set_iterate_lower_bound(Some(start));
683        let mut iter = self.inner.range_with_options(&options)?;
684        let mut keys = Vec::new();
685        let mut valid = iter.seek_first()?;
686        while valid {
687            if let Some(key) = iter.key().user_key().strip_prefix(family.prefix()) {
688                keys.push(key.to_vec());
689            }
690            valid = iter.next()?;
691        }
692        Ok(keys)
693    }
694
695    /// Commits every change of the transaction, or none of them.
696    ///
697    /// # Errors
698    ///
699    /// [`StoreError::Conflict`] when a concurrent transaction committed a change to a
700    /// record this one wrote, and [`StoreError::Database`] when the commit fails; in
701    /// both cases nothing was written.
702    pub fn commit(mut self) -> Result<(), StoreError> {
703        self.inner.set_durability(Durability::Eventual);
704        match wait_for(&self.store.runtime, self.inner.commit())? {
705            Ok(()) => {},
706            Err(surrealkv::Error::TransactionWriteConflict) => return Err(StoreError::Conflict),
707            Err(error) => return Err(error.into()),
708        }
709        // Hand the log to the operating system, so the commit survives a crash of
710        // this process.
711        self.store.tree.flush_wal(false)?;
712        Ok(())
713    }
714}
715
716/// The store's runtime, which never panics when it is dropped ("Kizz never
717/// panics").
718///
719/// Dropping a Tokio runtime waits for its blocking pool, which panics with "Cannot
720/// drop a runtime in a context where blocking is not allowed" inside an
721/// asynchronous context. Kizz drops no store there, but should one be dropped
722/// there, its runtime shuts down in the background, with
723/// `Runtime::shutdown_background`, which does not wait, instead; elsewhere it shuts
724/// down as usual. The runtime is `None` only while it is dropped.
725struct StoreRuntime(Option<tokio::runtime::Runtime>);
726
727impl StoreRuntime {
728    /// The runtime, until it is dropped.
729    const fn get(&self) -> Option<&tokio::runtime::Runtime> {
730        self.0.as_ref()
731    }
732}
733
734impl Drop for StoreRuntime {
735    fn drop(&mut self) {
736        if let Some(runtime) = self.0.take()
737            && tokio::runtime::Handle::try_current().is_ok()
738        {
739            runtime.shutdown_background();
740        }
741    }
742}
743
744/// Runs `future` to its end on `runtime` with `Runtime::block_on`, after checking
745/// that the calling thread is in no runtime, where `block_on` would panic.
746///
747/// # Errors
748///
749/// [`StoreError::InsideRuntime`] when the calling thread is in a runtime; the
750/// future is dropped without running. [`StoreError::Runtime`] for a runtime that
751/// is already gone, which only a store being dropped has.
752fn wait_for<F: Future>(
753    runtime: &StoreRuntime,
754    future: F,
755) -> Result<F::Output, StoreError> {
756    if tokio::runtime::Handle::try_current().is_ok() {
757        return Err(StoreError::InsideRuntime);
758    }
759    let Some(runtime) = runtime.get() else {
760        return Err(StoreError::Runtime(io::Error::other(
761            "the cache database runtime has shut down",
762        )));
763    };
764    Ok(runtime.block_on(future))
765}
766
767/// Decodes a stored record of type `R`.
768fn decode<R: Record>(bytes: &[u8]) -> Result<R, StoreError> {
769    minicbor::decode(bytes).map_err(|source| {
770        StoreError::Decode {
771            family: R::FAMILY,
772            source,
773        }
774    })
775}
776
777/// The first key after every key that starts with `prefix`, or `None` when no such
778/// key exists because the prefix is all `0xFF` bytes.
779fn prefix_end(prefix: &[u8]) -> Option<Vec<u8>> {
780    let mut end = prefix.to_vec();
781    while let Some(last) = end.pop() {
782        if let Some(next) = last.checked_add(1) {
783            end.push(next);
784            return Some(end);
785        }
786    }
787    None
788}
789
790/// Unit tests for the parts of the store that need no database.
791#[cfg(test)]
792#[allow(clippy::disallowed_macros, reason = "test code: the tests assert")]
793mod tests {
794    use std::cell::Cell;
795
796    use super::*;
797
798    /// The store's runtime, dropped inside an asynchronous context, where dropping a
799    /// Tokio runtime panics with "Cannot drop a runtime in a context where blocking
800    /// is not allowed", shuts down in the background instead, and the context goes
801    /// on; dropped outside one, it shuts down as usual.
802    #[test]
803    fn the_runtime_drops_without_a_panic_inside_an_asynchronous_context() {
804        let outer = tokio::runtime::Builder::new_current_thread()
805            .build()
806            .unwrap();
807        let inside = StoreRuntime(Some(
808            tokio::runtime::Builder::new_current_thread()
809                .build()
810                .unwrap(),
811        ));
812        assert!(inside.get().is_some());
813        outer.block_on(async move { drop(inside) });
814        let outside = StoreRuntime(Some(
815            tokio::runtime::Builder::new_current_thread()
816                .build()
817                .unwrap(),
818        ));
819        drop(outside);
820        let gone = StoreRuntime(None);
821        assert!(matches!(
822            wait_for(&gone, async { 5 }),
823            Err(StoreError::Runtime(_))
824        ));
825    }
826
827    /// Waiting for the database from inside a runtime is
828    /// [`StoreError::InsideRuntime`], where `Runtime::block_on` would panic, and
829    /// the future never runs; outside a runtime, it runs to its end.
830    #[test]
831    fn waiting_inside_a_runtime_is_an_error() {
832        let outer = tokio::runtime::Builder::new_current_thread()
833            .build()
834            .unwrap();
835        let runtime = StoreRuntime(Some(
836            tokio::runtime::Builder::new_current_thread()
837                .build()
838                .unwrap(),
839        ));
840        let ran = Cell::new(false);
841        let entered = outer.enter();
842        let inside = wait_for(&runtime, async { ran.set(true) });
843        assert!(
844            matches!(inside, Err(StoreError::InsideRuntime)),
845            "{inside:?}"
846        );
847        assert!(!ran.get());
848        assert_eq!(
849            StoreError::InsideRuntime.to_string(),
850            "the cache database cannot be waited for from inside an asynchronous task"
851        );
852        drop(entered);
853        assert_eq!(wait_for(&runtime, async { 5 }).unwrap(), 5);
854    }
855
856    #[test]
857    fn prefix_end_is_the_first_key_after_the_prefix() {
858        assert_eq!(prefix_end(b"task/"), Some(b"task0".to_vec()));
859        assert_eq!(prefix_end(b"a\xFF\xFF"), Some(b"b".to_vec()));
860        assert_eq!(prefix_end(b"\xFF\xFF"), None);
861        assert_eq!(prefix_end(b""), None);
862    }
863
864    #[test]
865    fn schema_mismatch_names_both_versions_and_the_reset_command() {
866        let message = StoreError::SchemaMismatch {
867            path: PathBuf::from("/cache/db"),
868            found: 5,
869            expected: SCHEMA_VERSION,
870        }
871        .to_string();
872        assert!(message.contains("schema version 5"), "{message}");
873        assert!(
874            message.contains(&format!("schema version {SCHEMA_VERSION}")),
875            "{message}"
876        );
877        assert!(message.contains("`kizz cache reset --all`"), "{message}");
878        assert!(message.contains("/cache/db"), "{message}");
879    }
880
881    /// The identity mismatch names each difference, stored and current, says that the
882    /// cache is not portable, and gives both ways on.
883    #[test]
884    fn identity_mismatch_names_each_difference_and_both_ways_on() {
885        let message = StoreError::IdentityMismatch {
886            path: PathBuf::from("/cache/db"),
887            differences: vec![
888                IdentityDifference {
889                    part: crate::IdentityPart::Host,
890                    stored: String::from(r#""old-host""#),
891                    current: String::from(r#""new-host""#),
892                },
893                IdentityDifference {
894                    part: crate::IdentityPart::Umask,
895                    stored: String::from("0022"),
896                    current: String::from("0077"),
897                },
898            ],
899        }
900        .to_string();
901        assert_eq!(
902            message,
903            "the cache database at `/cache/db` belongs to another machine or user, so kizz \
904             refuses to use it: host name: \"old-host\" in the cache, \"new-host\" now; umask: \
905             0022 in the cache, 0077 now; the cache is not portable between machines and users; \
906             run `kizz cache reset --all` to wipe the cache, or set `KIZZ_CACHE_DIR` to use \
907             another cache"
908        );
909    }
910
911    /// The missing-identity error says that the identity is missing, that the cache
912    /// is not portable, and gives both ways on.
913    #[test]
914    fn identity_missing_says_so_and_gives_both_ways_on() {
915        let message = StoreError::IdentityMissing {
916            path: PathBuf::from("/cache/db"),
917        }
918        .to_string();
919        assert_eq!(
920            message,
921            "the cache database at `/cache/db` has no cache identity, so kizz cannot tell \
922             which machine and user it belongs to and refuses to use it; the cache is not \
923             portable between machines and users; run `kizz cache reset --all` to wipe the \
924             cache, or set `KIZZ_CACHE_DIR` to use another cache"
925        );
926    }
927
928    /// The check that every open makes refuses a stored identity whose CPU models
929    /// differ from the current ones, also for the lists that the joined text of earlier
930    /// versions showed alike, naming the CPU model alone; its error text shows the
931    /// stored and the current list differently; and it accepts the stored models
932    /// themselves.
933    #[test]
934    fn the_open_check_refuses_and_tells_apart_cpu_models_that_once_showed_alike() {
935        let base = CacheIdentity::current();
936        for collision in crate::identity::colliding_cpu_models() {
937            let dir = tempfile::tempdir().unwrap();
938            let store = Store::open(dir.path()).unwrap();
939            let stored = CacheIdentity {
940                cpu_models: collision.stored,
941                ..base.clone()
942            };
943            let current = CacheIdentity {
944                cpu_models: collision.current,
945                ..base.clone()
946            };
947            let mut txn = store.write().unwrap();
948            txn.put(&IdentityKey, &stored).unwrap();
949            txn.commit().unwrap();
950            store.check_stamp(&stored).unwrap();
951            let error = store.check_stamp(&current).unwrap_err();
952            let message = error.to_string();
953            match error {
954                StoreError::IdentityMismatch { path, differences } => {
955                    assert_eq!(path, dir.path().join(DATABASE_DIR));
956                    assert_eq!(differences, vec![IdentityDifference {
957                        part: crate::IdentityPart::CpuModel,
958                        stored: String::from(collision.stored_text),
959                        current: String::from(collision.current_text),
960                    }]);
961                },
962                other => panic!("expected an identity mismatch, got {other:?}"),
963            }
964            assert_ne!(collision.stored_text, collision.current_text);
965            let shown = format!(
966                "refuses to use it: CPU model: {} in the cache, {} now; the cache is not",
967                collision.stored_text, collision.current_text
968            );
969            assert!(message.contains(&shown), "{message}");
970            store.close().unwrap();
971        }
972    }
973
974    /// Version 20 adds explicit untraced execution to step specifications and
975    /// explanations.
976    #[test]
977    fn schema_version_20_records_untraced_execution() {
978        assert_eq!(SCHEMA_VERSION, 20);
979    }
980
981    /// The store's thresholds keep write pacing from running: `SurrealKV` paces a
982    /// write only while a count of immutable memory tables passes its threshold less
983    /// 2, or a count of level-0 files its threshold less 4 (`StallThresholds::new`
984    /// and `WriteStallController::check` in `vendor/surrealkv/src/stall.rs`), and
985    /// both counts are lengths of collections in memory, which never pass
986    /// `isize::MAX`.
987    #[test]
988    fn write_pacing_cannot_run_under_the_store_thresholds() {
989        let options = tree_options(PathBuf::from("/cache/db"));
990        assert_eq!(options.memtable_stall_threshold, STALL_THRESHOLD);
991        assert_eq!(options.l0_stall_threshold, STALL_THRESHOLD);
992        let memtable_soft_limit = options.memtable_stall_threshold.saturating_sub(2).max(1);
993        let l0_soft_limit = options.l0_stall_threshold.saturating_sub(4).max(1);
994        let longest = usize::try_from(isize::MAX).unwrap();
995        assert!(memtable_soft_limit > longest);
996        assert!(l0_soft_limit > longest);
997    }
998}