Skip to main content

kizz_store/
records.rs

1// Copyright (c) 2026 Sakura Industries LLC.
2//
3// SPDX-License-Identifier: AGPL-3.0-only
4
5//! The typed records of the cache database and the layout of their keys.
6//!
7//! Every record belongs to a [`Family`], and every key in the database starts with
8//! its family's prefix, so a family, or a part of one, is a prefix scan. The rest of
9//! the key is the record's [`RecordKey`]:
10//!
11//! | Family | Prefix | Rest of the key | Record |
12//! | --- | --- | --- | --- |
13//! | schema version | `meta/` | `schema-version` | [`SchemaVersion`] |
14//! | cache identity | `meta/` | `identity` | [`CacheIdentity`](crate::identity::CacheIdentity) |
15//! | step records | `step/` | the 32 bytes of the [`StepKey`] | [`StepRecord`](crate::step::StepRecord) |
16//! | step positions | `position/` | the [`TaskId`], then the position | [`StepPosition`] |
17//! | task records | `task/` | the [`TaskId`] | [`TaskRecord`] |
18//! | last writers | `writer/` | the absolute path, as a [`PathKey`] | [`LastWriter`] |
19//! | learned order | `order/` | the [`TaskId`] | [`LearnedOrder`] |
20//!
21//! A [`TaskId`] is the bytes of the absolute path of the task's `kizz.md`, a zero
22//! byte, which no path contains, and the task's index in the file as four big-endian
23//! bytes. Positions are four big-endian bytes too, so keys sort by path, then index,
24//! then position. Because keys start with absolute paths, every entry for the tasks
25//! and paths under a directory is the prefix scan of [`path_prefix`].
26//!
27//! Records are CBOR, encoded with `minicbor` by the rules of "Step keys": definite
28//! lengths, fields in a fixed order (struct fields are arrays, in index order), and
29//! sets and maps sorted by key, so the same record always has the same bytes.
30//!
31//! Step records hold the full step specification and the observations; their
32//! contents are in [`step`](crate::step). Later phases extend the other record
33//! contents, and a change of encoding raises [`SCHEMA_VERSION`](crate::SCHEMA_VERSION).
34
35use std::{
36    collections::BTreeSet,
37    ffi::OsStr,
38    fmt,
39    os::unix::ffi::OsStrExt as _,
40    path::{Path, PathBuf},
41};
42
43use minicbor::{Decode, Decoder, Encode, Encoder, bytes::ByteArray, decode, encode};
44
45use crate::{
46    explanation::{BuildId, Verdict},
47    step::{ContentHash, path_bytes, path_list},
48};
49
50/// The record families of the cache database.
51#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
52pub enum Family {
53    /// Facts about the database itself: the schema version and the cache identity.
54    Meta,
55    /// Step records, by step key.
56    Step,
57    /// Step positions: the step key each task used last time at each position.
58    Position,
59    /// Task records: the task program hash and a summary of the last run.
60    Task,
61    /// Last writers: for each path, the step that wrote it most recently.
62    Writer,
63    /// Learned order: for each task, the tasks whose outputs it consumed.
64    Order,
65}
66
67impl Family {
68    /// Every family.
69    pub const ALL: [Self; 6] = [
70        Self::Meta,
71        Self::Step,
72        Self::Position,
73        Self::Task,
74        Self::Writer,
75        Self::Order,
76    ];
77
78    /// The prefix of every key of this family. No prefix is a prefix of another.
79    #[must_use]
80    pub const fn prefix(self) -> &'static [u8] {
81        match self {
82            Self::Meta => b"meta/",
83            Self::Step => b"step/",
84            Self::Position => b"position/",
85            Self::Task => b"task/",
86            Self::Writer => b"writer/",
87            Self::Order => b"order/",
88        }
89    }
90
91    /// The name of the family in messages.
92    #[must_use]
93    pub const fn name(self) -> &'static str {
94        match self {
95            Self::Meta => "database fact",
96            Self::Step => "step record",
97            Self::Position => "step position",
98            Self::Task => "task record",
99            Self::Writer => "last writer",
100            Self::Order => "learned order",
101        }
102    }
103}
104
105impl fmt::Display for Family {
106    fn fmt(
107        &self,
108        f: &mut fmt::Formatter<'_>,
109    ) -> fmt::Result {
110        f.write_str(self.name())
111    }
112}
113
114/// The part of a database key after the family prefix.
115pub trait RecordKey: Sized {
116    /// Appends the key's bytes to `out`.
117    fn encode_key(
118        &self,
119        out: &mut Vec<u8>,
120    );
121
122    /// The key from its bytes, or `None` when they are not a key of this type.
123    fn decode_key(bytes: &[u8]) -> Option<Self>;
124}
125
126/// A typed record stored in the cache database.
127pub trait Record: Encode<()> + for<'b> Decode<'b, ()> {
128    /// The key of a record of this type.
129    type Key: RecordKey;
130
131    /// The family of this record type.
132    const FAMILY: Family;
133}
134
135/// The full database key of the record of type `R` at `key`.
136#[must_use]
137pub fn database_key<R: Record>(key: &R::Key) -> Vec<u8> {
138    let mut out = R::FAMILY.prefix().to_vec();
139    key.encode_key(&mut out);
140    out
141}
142
143/// The key prefix that selects every entry for the paths and tasks under `dir`, for
144/// the families keyed by absolute paths: step positions, task records, last writers,
145/// and learned order. The entry for `dir` itself is not under it.
146#[must_use]
147pub fn path_prefix(dir: &Path) -> Vec<u8> {
148    let mut out = dir.as_os_str().as_bytes().to_vec();
149    if out.last() != Some(&b'/') {
150        out.push(b'/');
151    }
152    out
153}
154
155/// The BLAKE3 hash that identifies a step, the key of its step record.
156#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
157pub struct StepKey(pub [u8; 32]);
158
159impl RecordKey for StepKey {
160    fn encode_key(
161        &self,
162        out: &mut Vec<u8>,
163    ) {
164        out.extend_from_slice(&self.0);
165    }
166
167    fn decode_key(bytes: &[u8]) -> Option<Self> {
168        bytes.try_into().ok().map(Self)
169    }
170}
171
172impl<C> Encode<C> for StepKey {
173    fn encode<W: encode::Write>(
174        &self,
175        e: &mut Encoder<W>,
176        _ctx: &mut C,
177    ) -> Result<(), encode::Error<W::Error>> {
178        e.bytes(&self.0)?.ok()
179    }
180}
181
182impl<'b, C> Decode<'b, C> for StepKey {
183    fn decode(
184        d: &mut Decoder<'b>,
185        ctx: &mut C,
186    ) -> Result<Self, decode::Error> {
187        ByteArray::<32>::decode(d, ctx).map(|bytes| Self(bytes.into()))
188    }
189}
190
191/// The identity of a task: the absolute path of its `kizz.md` and its index among the
192/// task blocks of that file.
193#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
194pub struct TaskId {
195    /// The absolute path of the task's `kizz.md`.
196    pub file: PathBuf,
197    /// The index of the task block in the file, counting from zero.
198    pub index: u32,
199}
200
201impl TaskId {
202    /// The key prefix of every step position of this task.
203    #[must_use]
204    pub fn key_prefix(&self) -> Vec<u8> {
205        let mut out = Vec::new();
206        self.encode_key(&mut out);
207        out
208    }
209}
210
211impl RecordKey for TaskId {
212    fn encode_key(
213        &self,
214        out: &mut Vec<u8>,
215    ) {
216        out.extend_from_slice(self.file.as_os_str().as_bytes());
217        out.push(0);
218        out.extend_from_slice(&self.index.to_be_bytes());
219    }
220
221    fn decode_key(bytes: &[u8]) -> Option<Self> {
222        let (path, index) = bytes.split_last_chunk::<4>()?;
223        let (separator, path) = path.split_last()?;
224        if *separator != 0 || path.contains(&0) {
225            return None;
226        }
227        Some(Self {
228            file: PathBuf::from(OsStr::from_bytes(path)),
229            index: u32::from_be_bytes(*index),
230        })
231    }
232}
233
234impl<C> Encode<C> for TaskId {
235    fn encode<W: encode::Write>(
236        &self,
237        e: &mut Encoder<W>,
238        _ctx: &mut C,
239    ) -> Result<(), encode::Error<W::Error>> {
240        e.array(2)?
241            .bytes(self.file.as_os_str().as_bytes())?
242            .u32(self.index)?
243            .ok()
244    }
245}
246
247impl<'b, C> Decode<'b, C> for TaskId {
248    fn decode(
249        d: &mut Decoder<'b>,
250        _ctx: &mut C,
251    ) -> Result<Self, decode::Error> {
252        if d.array()? != Some(2) {
253            return Err(decode::Error::message("a task ID is an array of two items"));
254        }
255        let file = PathBuf::from(OsStr::from_bytes(d.bytes()?));
256        let index = d.u32()?;
257        Ok(Self { file, index })
258    }
259}
260
261/// The key of a step position: a task and the position of a step in its run.
262#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
263pub struct PositionKey {
264    /// The task.
265    pub task: TaskId,
266    /// The position of the step in the task's run, counting from zero.
267    pub position: u32,
268}
269
270impl RecordKey for PositionKey {
271    fn encode_key(
272        &self,
273        out: &mut Vec<u8>,
274    ) {
275        self.task.encode_key(out);
276        out.extend_from_slice(&self.position.to_be_bytes());
277    }
278
279    fn decode_key(bytes: &[u8]) -> Option<Self> {
280        let (task, position) = bytes.split_last_chunk::<4>()?;
281        Some(Self {
282            task: TaskId::decode_key(task)?,
283            position: u32::from_be_bytes(*position),
284        })
285    }
286}
287
288/// The key of a last-writer entry: an absolute path.
289#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
290pub struct PathKey(pub PathBuf);
291
292impl RecordKey for PathKey {
293    fn encode_key(
294        &self,
295        out: &mut Vec<u8>,
296    ) {
297        out.extend_from_slice(self.0.as_os_str().as_bytes());
298    }
299
300    fn decode_key(bytes: &[u8]) -> Option<Self> {
301        Some(Self(PathBuf::from(OsStr::from_bytes(bytes))))
302    }
303}
304
305/// The key of the schema version, one of the two records of its family with the
306/// cache identity.
307#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
308pub struct SchemaKey;
309
310impl SchemaKey {
311    /// The bytes of the key after the family prefix.
312    const BYTES: &'static [u8] = b"schema-version";
313}
314
315impl RecordKey for SchemaKey {
316    fn encode_key(
317        &self,
318        out: &mut Vec<u8>,
319    ) {
320        out.extend_from_slice(Self::BYTES);
321    }
322
323    fn decode_key(bytes: &[u8]) -> Option<Self> {
324        (bytes == Self::BYTES).then_some(Self)
325    }
326}
327
328/// The version of the database's schema, written when the database is created.
329#[derive(Debug, Clone, Copy, PartialEq, Eq, Encode, Decode)]
330pub struct SchemaVersion {
331    /// The version.
332    #[n(0)]
333    pub version: u32,
334}
335
336impl Record for SchemaVersion {
337    type Key = SchemaKey;
338
339    const FAMILY: Family = Family::Meta;
340}
341
342/// The step key a task used last time at one step position, with what that build
343/// decided about the step, so a changed key is explained by comparing the step
344/// specifications and `kizz why` prints the reasons the most recent build stored.
345#[derive(Debug, Clone, PartialEq, Eq, Encode, Decode)]
346pub struct StepPosition {
347    /// The step key.
348    #[n(0)]
349    pub step: StepKey,
350    /// The build that last decided about the step at this position.
351    #[n(1)]
352    pub build: BuildId,
353    /// What that build decided. Within one build, a step that ran keeps its reasons
354    /// when a later pass finds it cached.
355    #[n(2)]
356    pub verdict: Verdict,
357    /// The self-inflicted inputs that made the step run in its task's previous
358    /// build, sorted, so a run in this build for the same reason gets the warning
359    /// for consecutive builds.
360    #[cbor(n(3), with = "path_list")]
361    pub carried: Vec<PathBuf>,
362}
363
364impl Record for StepPosition {
365    type Key = PositionKey;
366
367    const FAMILY: Family = Family::Position;
368}
369
370/// The hash of one module a task program loads.
371#[derive(Debug, Clone, PartialEq, Eq, Encode, Decode)]
372pub struct ModuleHash {
373    /// The absolute path of the module.
374    #[cbor(n(0), with = "path_bytes")]
375    pub path: PathBuf,
376    /// The BLAKE3 hash of its source.
377    #[n(1)]
378    pub hash: ContentHash,
379}
380
381/// What is recorded about a task: its program hash, the hashes of the program's
382/// parts, how output names the task, and a summary of its last run.
383#[derive(Debug, Clone, PartialEq, Eq, Encode, Decode)]
384pub struct TaskRecord {
385    /// The hash of the task program: its block and every module it loads.
386    #[cbor(n(0), with = "minicbor::bytes")]
387    pub program_hash: [u8; 32],
388    /// Whether the last run of the task succeeded.
389    #[n(1)]
390    pub succeeded: bool,
391    /// The build of the last run.
392    #[n(2)]
393    pub build: BuildId,
394    /// The number of steps of the last run; its step positions are those below it.
395    #[n(3)]
396    pub steps: u32,
397    /// The line of the block's opening fence, counting from 1.
398    #[n(4)]
399    pub line: u32,
400    /// The nearest heading above the block, if there is one.
401    #[n(5)]
402    pub heading: Option<String>,
403    /// The targets on the block, in the order written.
404    #[n(6)]
405    pub targets: Vec<String>,
406    /// The BLAKE3 hash of the block's source.
407    #[n(7)]
408    pub block: ContentHash,
409    /// The hash of every module the program loads, sorted by path.
410    #[n(8)]
411    pub modules: Vec<ModuleHash>,
412}
413
414impl Record for TaskRecord {
415    type Key = TaskId;
416
417    const FAMILY: Family = Family::Task;
418}
419
420/// What in a task wrote a path: one of its steps, or its program.
421#[derive(Debug, Clone, Copy, PartialEq, Eq, Encode, Decode)]
422pub enum WrittenBy {
423    /// A step of the task.
424    #[n(0)]
425    Step {
426        /// The step key.
427        #[n(0)]
428        step: StepKey,
429        /// The position of the step in its task's run, counting from zero.
430        #[n(1)]
431        position: u32,
432    },
433    /// The task program, through `fs.write` or `fs.write_json`.
434    #[n(1)]
435    Program,
436}
437
438/// The step or the task program that most recently wrote a path.
439#[derive(Debug, Clone, PartialEq, Eq, Encode, Decode)]
440pub struct LastWriter {
441    /// The task of the step or the program.
442    #[n(0)]
443    pub task: TaskId,
444    /// Whether a step of the task or its program wrote the path.
445    #[n(1)]
446    pub by: WrittenBy,
447    /// The build in which the path was written.
448    #[n(2)]
449    pub build: BuildId,
450    /// When the write happened, in nanoseconds since the Unix epoch: for a step,
451    /// when kizz recorded the state the step left, after the write, which is the
452    /// `recorded_at_nanos` of the step's record; for a program, when it wrote the
453    /// file.
454    #[n(3)]
455    pub written_at_nanos: u64,
456}
457
458impl Record for LastWriter {
459    type Key = PathKey;
460
461    const FAMILY: Family = Family::Writer;
462}
463
464/// The tasks whose outputs a task consumed, in sorted order.
465#[derive(Debug, Clone, PartialEq, Eq, Encode, Decode)]
466pub struct LearnedOrder {
467    /// The producers.
468    #[n(0)]
469    pub producers: BTreeSet<TaskId>,
470}
471
472impl Record for LearnedOrder {
473    type Key = TaskId;
474
475    const FAMILY: Family = Family::Order;
476}
477
478/// Unit tests for the key layout and the record encoding.
479#[cfg(test)]
480#[allow(
481    clippy::disallowed_macros,
482    clippy::disallowed_methods,
483    reason = "test code: the tests assert and lock"
484)]
485mod tests {
486    use super::*;
487
488    /// A task in `/work/<dir>/kizz.md`.
489    fn task(
490        dir: &str,
491        index: u32,
492    ) -> TaskId {
493        TaskId {
494            file: PathBuf::from(format!("/work/{dir}/kizz.md")),
495            index,
496        }
497    }
498
499    #[test]
500    fn no_family_prefix_is_a_prefix_of_another() {
501        for one in Family::ALL {
502            for other in Family::ALL {
503                if one != other {
504                    assert!(
505                        !other.prefix().starts_with(one.prefix()),
506                        "{one} and {other}"
507                    );
508                }
509            }
510        }
511    }
512
513    #[test]
514    fn keys_round_trip() {
515        let step = StepKey([7; 32]);
516        let mut bytes = Vec::new();
517        step.encode_key(&mut bytes);
518        assert_eq!(StepKey::decode_key(&bytes), Some(step));
519        assert_eq!(StepKey::decode_key(&bytes[1..]), None);
520
521        let id = task("a b", 3);
522        assert_eq!(TaskId::decode_key(&id.key_prefix()), Some(id.clone()));
523        assert_eq!(TaskId::decode_key(b"/x"), None);
524
525        let position = PositionKey {
526            task: id,
527            position: 9,
528        };
529        let mut bytes = Vec::new();
530        position.encode_key(&mut bytes);
531        assert_eq!(PositionKey::decode_key(&bytes), Some(position));
532
533        let path = PathKey(PathBuf::from("/work/out.bin"));
534        let mut bytes = Vec::new();
535        path.encode_key(&mut bytes);
536        assert_eq!(PathKey::decode_key(&bytes), Some(path));
537
538        let mut bytes = Vec::new();
539        SchemaKey.encode_key(&mut bytes);
540        assert_eq!(SchemaKey::decode_key(&bytes), Some(SchemaKey));
541        assert_eq!(SchemaKey::decode_key(b"other"), None);
542    }
543
544    #[test]
545    fn database_keys_start_with_the_family_prefix() {
546        assert_eq!(
547            database_key::<SchemaVersion>(&SchemaKey),
548            b"meta/schema-version"
549        );
550        let key = database_key::<TaskRecord>(&task("a", 1));
551        assert_eq!(key, b"task//work/a/kizz.md\0\0\0\0\x01");
552    }
553
554    #[test]
555    fn task_keys_sort_by_path_then_index_then_position() {
556        let key = |dir: &str, index: u32, position: u32| {
557            database_key::<StepPosition>(&PositionKey {
558                task: task(dir, index),
559                position,
560            })
561        };
562        let mut keys = vec![
563            key("b", 0, 0),
564            key("a", 1, 0),
565            key("a", 0, 256),
566            key("a", 0, 1),
567            key("a", 256, 0),
568        ];
569        keys.sort();
570        assert_eq!(keys, vec![
571            key("a", 0, 1),
572            key("a", 0, 256),
573            key("a", 1, 0),
574            key("a", 256, 0),
575            key("b", 0, 0),
576        ]);
577    }
578
579    #[test]
580    fn path_prefix_selects_only_paths_under_the_directory() {
581        let prefix = path_prefix(Path::new("/work/a"));
582        assert_eq!(prefix, b"/work/a/");
583        assert_eq!(path_prefix(Path::new("/work/a/")), b"/work/a/");
584        assert_eq!(path_prefix(Path::new("/")), b"/");
585        assert!(task("a", 0).key_prefix().starts_with(&prefix));
586        assert!(!task("ab", 0).key_prefix().starts_with(&prefix));
587    }
588
589    /// Encodes `record` twice, checks that both encodings are equal and decode back to
590    /// it, and returns them.
591    fn encode_stably<R: Record + PartialEq + fmt::Debug>(record: &R) -> Vec<u8> {
592        let first = minicbor::to_vec(record).unwrap();
593        let second = minicbor::to_vec(record).unwrap();
594        assert_eq!(first, second);
595        assert_eq!(&minicbor::decode::<R>(&first).unwrap(), record);
596        first
597    }
598
599    #[test]
600    fn records_encode_deterministically_and_round_trip() {
601        let version = encode_stably(&SchemaVersion { version: 1 });
602        // A definite-length array of one item, then the unsigned integer 1.
603        assert_eq!(version, [0x81, 0x01]);
604
605        let position = encode_stably(&StepPosition {
606            step: StepKey([1; 32]),
607            build: BuildId(5),
608            verdict: Verdict::Cached,
609            carried: vec![PathBuf::from("/work/a/out")],
610        });
611        // A definite-length array of four items, then the 32 bytes of the key.
612        assert_eq!(position.get(..3), Some(&[0x84, 0x58, 0x20][..]));
613
614        encode_stably(&TaskRecord {
615            program_hash: [2; 32],
616            succeeded: true,
617            build: BuildId(5),
618            steps: 2,
619            line: 3,
620            heading: Some("Build".to_owned()),
621            targets: vec!["ci".to_owned()],
622            block: ContentHash([4; 32]),
623            modules: vec![ModuleHash {
624                path: PathBuf::from("/work/lib.star"),
625                hash: ContentHash([5; 32]),
626            }],
627        });
628        let step_writer = encode_stably(&LastWriter {
629            task: task("a", 0),
630            by: WrittenBy::Step {
631                step: StepKey([3; 32]),
632                position: 1,
633            },
634            build: BuildId(5),
635            written_at_nanos: 6,
636        });
637        let program_writer = encode_stably(&LastWriter {
638            task: task("a", 0),
639            by: WrittenBy::Program,
640            build: BuildId(5),
641            written_at_nanos: 6,
642        });
643        // A definite-length array of four items, then the task; the two records
644        // differ only in who wrote the path.
645        assert_eq!(step_writer.first(), Some(&0x84));
646        assert_eq!(program_writer.first(), Some(&0x84));
647        assert_ne!(step_writer, program_writer);
648        assert_ne!(
649            minicbor::decode::<LastWriter>(&step_writer).unwrap().by,
650            WrittenBy::Program
651        );
652        assert_eq!(
653            minicbor::decode::<LastWriter>(&program_writer).unwrap().by,
654            WrittenBy::Program
655        );
656    }
657
658    #[test]
659    fn sets_encode_sorted_whatever_the_insertion_order() {
660        let forward = LearnedOrder {
661            producers: [task("a", 0), task("b", 0), task("c", 1)].into(),
662        };
663        let backward = LearnedOrder {
664            producers: [task("c", 1), task("b", 0), task("a", 0)].into(),
665        };
666        assert_eq!(encode_stably(&forward), encode_stably(&backward));
667    }
668}