Skip to main content

kizz_core/
key.rs

1// Copyright (c) 2026 Sakura Industries LLC.
2//
3// SPDX-License-Identifier: AGPL-3.0-only
4
5//! Step keys.
6//!
7//! A step's key is a BLAKE3 hash, derived with the versioned context string
8//! [`STEP_KEY_CONTEXT`], of a CBOR encoding, written with `minicbor`, of exactly
9//! these values, in this order:
10//!
11//! 1. the task program hash, covering the block and every loaded module;
12//! 2. the absolute working directory;
13//! 3. the arguments;
14//! 4. the environment passed to the process;
15//! 5. the `stdin` content;
16//! 6. the capture mode;
17//! 7. the ignore patterns;
18//! 8. the `track` patterns;
19//! 9. whether `timestamps` is set;
20//! 10. the `machine` names, sorted and without repeats;
21//! 11. whether `untraced` is set;
22//! 12. the occurrence number, which counts identical commands earlier in the same task
23//!     run.
24//!
25//! The encoding is deterministic: one definite-length array of the twelve values,
26//! definite lengths throughout, and the environment as a map sorted by name. So the
27//! same step always produces the same key. `always`, `stream`, `expect`, and `network`
28//! are not in the key, because they change what kizz does with a step, not what the
29//! command does. `timestamps` is in the key, because a record made without it keeps the
30//! timestamps of its latest cache hit. The `machine` names are in the key, like the
31//! `track` patterns, because they decide what the cache check compares.
32
33use std::{collections::HashMap, convert::Infallible, os::unix::ffi::OsStrExt as _};
34
35use kizz_store::StepKey;
36use kizz_trace::CaptureMode;
37use minicbor::{Encoder, encode};
38
39use crate::{runtime::ProgramHash, step::StepSpec};
40
41/// The context string from which step keys are derived. A change to the values in
42/// the key or to their encoding changes the version at its end.
43pub const STEP_KEY_CONTEXT: &str = "kizz step key, version 4";
44
45/// The number of values in the key's encoding.
46const KEY_VALUES: u64 = 12;
47
48/// A step whose key values could not be encoded.
49#[derive(Debug, Clone, PartialEq, Eq, thiserror::Error)]
50#[error("cannot encode the step key of `{command}`: {message}")]
51pub struct KeyError {
52    /// The command, as messages show it.
53    pub command: String,
54    /// What went wrong.
55    pub message: String,
56}
57
58/// The error of an encoder that writes into memory.
59type EncodeError = encode::Error<Infallible>;
60
61/// The length of a list, as CBOR encodes it.
62fn length(len: usize) -> Result<u64, EncodeError> {
63    u64::try_from(len).map_err(|_| encode::Error::message("a list is too long to encode"))
64}
65
66/// The code of a capture mode in the key.
67const fn capture_code(capture: CaptureMode) -> u8 {
68    match capture {
69        CaptureMode::Split => 0,
70        CaptureMode::Merged => 1,
71    }
72}
73
74/// Encode a list of strings as a definite-length array.
75fn strings(
76    e: &mut Encoder<Vec<u8>>,
77    items: &[String],
78) -> Result<(), EncodeError> {
79    e.array(length(items.len())?)?;
80    for item in items {
81        e.str(item)?;
82    }
83    Ok(())
84}
85
86/// The encoding of the key values of `spec` in the task program `program`, up to and
87/// excluding the occurrence number. Identical commands have identical bytes here.
88fn encode_identity(
89    program: ProgramHash,
90    spec: &StepSpec,
91) -> Result<Vec<u8>, EncodeError> {
92    let mut e = Encoder::new(Vec::new());
93    e.array(KEY_VALUES)?;
94    e.bytes(program.as_bytes())?;
95    e.bytes(spec.cwd.as_path().as_os_str().as_bytes())?;
96    strings(&mut e, &spec.argv)?;
97    e.map(length(spec.env.len())?)?;
98    for (name, value) in &spec.env {
99        e.str(name)?.str(value)?;
100    }
101    match &spec.stdin {
102        Some(text) => e.str(text)?,
103        None => e.null()?,
104    };
105    e.u8(capture_code(spec.capture))?;
106    strings(&mut e, &spec.ignore)?;
107    strings(&mut e, &spec.track)?;
108    e.bool(spec.timestamps)?;
109    strings(&mut e, &spec.machine)?;
110    e.bool(spec.untraced)?;
111    Ok(e.into_writer())
112}
113
114/// The key of a step from the encoding of its identity and its occurrence number.
115fn derive(
116    identity: Vec<u8>,
117    occurrence: u32,
118) -> Result<StepKey, EncodeError> {
119    let mut e = Encoder::new(identity);
120    e.u32(occurrence)?;
121    Ok(StepKey(blake3::derive_key(STEP_KEY_CONTEXT, e.writer())))
122}
123
124/// The error for `spec` when its key cannot be encoded.
125fn key_error(
126    spec: &StepSpec,
127    error: &EncodeError,
128) -> KeyError {
129    KeyError {
130        command: spec.command(),
131        message: error.to_string(),
132    }
133}
134
135/// The key of `spec`, the step at `occurrence` among identical commands of a run of
136/// the task program `program`.
137///
138/// # Errors
139///
140/// Returns [`KeyError`] when a list in the step is too long to encode.
141pub fn step_key(
142    program: ProgramHash,
143    spec: &StepSpec,
144    occurrence: u32,
145) -> Result<StepKey, KeyError> {
146    encode_identity(program, spec)
147        .and_then(|identity| derive(identity, occurrence))
148        .map_err(|error| key_error(spec, &error))
149}
150
151/// Counts identical commands in one run of a task, so a command repeated in the
152/// task gets one key for each occurrence.
153#[derive(Debug, Default)]
154pub struct Occurrences {
155    /// How many times each identity has been seen in the run.
156    seen: HashMap<Vec<u8>, u32>,
157}
158
159impl Occurrences {
160    /// No commands seen yet.
161    #[must_use]
162    pub fn new() -> Self {
163        Self::default()
164    }
165
166    /// The key and the occurrence number of the next step of the run, `spec` in the
167    /// task program `program`, counting it.
168    ///
169    /// # Errors
170    ///
171    /// Returns [`KeyError`] when a list in the step is too long to encode.
172    pub fn next_key(
173        &mut self,
174        program: ProgramHash,
175        spec: &StepSpec,
176    ) -> Result<(StepKey, u32), KeyError> {
177        let identity = encode_identity(program, spec).map_err(|error| key_error(spec, &error))?;
178        let count = self.seen.entry(identity.clone()).or_insert(0);
179        let occurrence = *count;
180        *count = count.saturating_add(1);
181        let key = derive(identity, occurrence).map_err(|error| key_error(spec, &error))?;
182        Ok((key, occurrence))
183    }
184}
185
186/// Unit tests for the key encoding.
187#[cfg(test)]
188#[allow(
189    clippy::disallowed_macros,
190    clippy::disallowed_methods,
191    reason = "test code: the tests assert and lock"
192)]
193mod tests {
194    use std::collections::BTreeMap;
195
196    use kizz_trace::AbsolutePath;
197
198    use super::*;
199
200    /// A step that runs `echo hi` in `/work`.
201    fn spec() -> StepSpec {
202        StepSpec {
203            argv: vec!["echo".to_owned(), "hi".to_owned()],
204            stdin: None,
205            env: BTreeMap::new(),
206            cwd: AbsolutePath::new("/work").unwrap(),
207            capture: CaptureMode::Split,
208            stream: false,
209            always: false,
210            untraced: false,
211            network: false,
212            ignore: Vec::new(),
213            track: Vec::new(),
214            timestamps: false,
215            machine: Vec::new(),
216            expect: None,
217        }
218    }
219
220    #[test]
221    fn the_encoding_is_one_definite_array_in_the_documented_order() {
222        let program = ProgramHash::from_bytes([7; 32]);
223        let mut step = spec();
224        step.env.insert("B".to_owned(), "2".to_owned());
225        step.env.insert("A".to_owned(), "1".to_owned());
226        let identity = encode_identity(program, &step).unwrap();
227        let mut expected = vec![0x8C, 0x58, 0x20];
228        expected.extend_from_slice(&[7; 32]);
229        expected.extend_from_slice(b"\x45/work");
230        expected.extend_from_slice(b"\x82\x64echo\x62hi");
231        expected.extend_from_slice(b"\xa2\x61A\x611\x61B\x612");
232        // No stdin, split capture, no ignore or track patterns, no `timestamps`, and
233        // no `machine` names, and tracing enabled.
234        expected.extend_from_slice(&[0xF6, 0x00, 0x80, 0x80, 0xF4, 0x80, 0xF4]);
235        assert_eq!(identity, expected);
236        step.timestamps = true;
237        let with_timestamps = encode_identity(program, &step).unwrap();
238        assert_eq!(with_timestamps.iter().rev().nth(2), Some(&0xF5));
239        assert_eq!(with_timestamps.len(), identity.len());
240        step.timestamps = false;
241        step.machine = vec!["kernel".to_owned(), "memory".to_owned()];
242        let with_machine = encode_identity(program, &step).unwrap();
243        assert!(with_machine.ends_with(b"\xF4\x82\x66kernel\x66memory\xF4"));
244        assert_ne!(
245            step_key(program, &step, 0).unwrap(),
246            step_key(program, &spec(), 0).unwrap()
247        );
248    }
249
250    #[test]
251    fn occurrences_count_identical_commands_only() {
252        let program = ProgramHash::from_bytes([1; 32]);
253        let mut occurrences = Occurrences::new();
254        let (first, zero) = occurrences.next_key(program, &spec()).unwrap();
255        let mut other = spec();
256        other.argv.push("there".to_owned());
257        let (_, other_zero) = occurrences.next_key(program, &other).unwrap();
258        let (second, one) = occurrences.next_key(program, &spec()).unwrap();
259        assert_eq!((zero, other_zero, one), (0, 0, 1));
260        assert_ne!(first, second);
261        assert_eq!(first, step_key(program, &spec(), 0).unwrap());
262        assert_eq!(second, step_key(program, &spec(), 1).unwrap());
263    }
264}