Skip to main content

kizz_core/
engine.rs

1// Copyright (c) 2026 Sakura Industries LLC.
2//
3// SPDX-License-Identifier: AGPL-3.0-only
4
5//! The engine side of the step executor.
6//!
7//! An [`Engine`] holds what every task of one build shares: the tracer, the store,
8//! where live output goes, the cancellation flag, the caller's home directory, the
9//! in-memory cache of file states and hashes, the results of the `always` steps
10//! that already ran, the results that were not cached, and the tracer failures of
11//! the build. For each run of a task program, [`Engine::task`] makes a
12//! [`TaskSteps`], the [`StepExecutor`] that the runtime hands each `run()` call to.
13//! For each step it:
14//!
15//! 1. derives the step key, counting identical commands earlier in the run;
16//! 2. compiles the step's ignore and `track` patterns, and checks that a bare program
17//!    name has a `PATH` in the step's environment;
18//! 3. returns the tracer failure that the build keeps for the step key, if any;
19//! 4. decides whether the step runs, with the cache check;
20//! 5. on a cache hit, returns the recorded exit status and raw output, with `cached` set,
21//!    storing new metadata the check found;
22//! 6. otherwise looks the program up through the `PATH` of the step's environment,
23//!    recording every location checked, queries the machine state that the command starts
24//!    with, through the tracer's machine query, notes that the step ran, and runs the
25//!    command through the tracer;
26//! 7. drops the cached hash of every path the step wrote, and records the state of every
27//!    touched path, concurrently, applying the step's ignore and `track` patterns; and
28//! 8. stores the step record, with the machine state, under the step key; a result that
29//!    is not cached replaces any older record with a record marked as not cached.
30//!
31//! The cache check ("Cache check"): with no record for the key, the step runs, and
32//! the reason is that it never ran. With a record, every recorded observation is
33//! compared with the file system by [`check`]; the step is a
34//! hit only when nothing changed, and otherwise it runs, with every difference as
35//! the reason.
36//!
37//! Machine state ("Machine state"): a cache hit queries no machine state to record.
38//! When the record names parts of the machine state, with `run(..., machine =
39//! [...])`, the check queries the current state for the record's working directory
40//! and compares each value of those parts with the recorded one; a difference makes
41//! the step run, and the reason names each changed value, old and new. Each step key
42//! is compared at most once per build, and not after its step ran in the build, so a
43//! step that names a part that changes all the time, such as `memory`, runs at most
44//! once per build and the build still settles.
45//!
46//! A step marked `always` runs at most once per build, when a pass first reaches it:
47//! the first time its key comes up in the build, normally in the first pass, and it
48//! is recorded like any other step. Every later time in the same build, whatever
49//! changed, its first result is returned again without running ("Commands that
50//! always run"). A key first reached in a later pass runs once then. Every step of a
51//! task marked `cache=never` runs the same way, as if it were marked `always`, and
52//! its reason names the task option. With [`Engine::with_no_cache`] (`kizz run
53//! --no-cache`), every step runs the same way too, without a cache check, and is
54//! still recorded; its reason names the option, unless the step is marked `always`,
55//! its task is marked `cache=never`, or it never ran, whose reasons come first. The
56//! option never makes a step cached.
57//!
58//! Step events ("Running one task with `kizz run`"): a run made with
59//! [`TaskSteps::with_events`] tells its [`StepEvents`] when a step starts to run,
60//! before its command starts and so before any of its output, and when a step comes
61//! from the cache, with the result that the step returns. With
62//! [`Engine::with_echo_every_step`], every command's output is echoed live, as if
63//! every `run()` had `stream = True`; the option is in no step key or record.
64//!
65//! Observation reports ("Running one task with `kizz run`"): with
66//! [`Engine::with_report`] (`kizz run --output`), every request asks the tracer for
67//! the process tree, and each run of a task program keeps, in the order its steps
68//! came, the [`CommandInput`] of each step ([`TaskSteps::commands`]): a step that
69//! ran, or whose program kizz did not find, with its outcome, its tree, and every
70//! location that the lookup checked with its outcome, named through the tracer's
71//! error-name query; and a cache hit as cached, with its recorded outcome and no
72//! observations. Without it, as in every build, no request asks for the tree and
73//! nothing more is kept. The option is in no step key or record.
74//!
75//! Results that are not cached ("Results that are not cached"): a command killed by
76//! a signal, every run that returns once cancellation has been requested, whether a
77//! signal ended it or it exited with a code after it handled the interrupt, a run
78//! that the tracer reports as incompletely traced, a run in which a file changed
79//! after the command first read it or ran it, and a command that could not start
80//! for a reason other than a missing or non-executable program. A run that made a
81//! system call that the tracer does not know is not cached either, unless the build
82//! caches such results (`kizz build --cache-unknown-syscalls`, see
83//! [`Engine::with_cache_unknown_system_calls`]); the tracer reports only the
84//! numbers of such calls, and the record lists them either way. After it records
85//! the states, the engine compares the first-read metadata that the tracer noted
86//! with them (see [`changed_after_read`]); a change, when no other reason applies,
87//! is the reason, and lists each changed file with whether the command wrote it.
88//! Their record is marked with why, which makes it a record that is never a cache
89//! hit and replaces any older record of the step key, so no older result is
90//! replayed. The engine also keeps the paths such a command touched, with their
91//! states, in memory for the rest of the build: when the step comes up again, it
92//! runs again only if one of them changed, and otherwise its result is returned
93//! again without running. In a later build, the marked record makes the step run
94//! again, with that stated as the reason.
95//!
96//! A run's connections to IPv4 and IPv6 addresses and to Unix sockets, which the
97//! tracer reports, never keep its result out of the cache: the record lists them,
98//! and the engine keeps each run that made any for the build's warnings (see
99//! [`Engine::connections`]). A cache hit runs nothing, so it adds no warning.
100//!
101//! Unchecked steps ("Exit codes and failure"): with [`Engine::with_fail_unchecked`],
102//! a task run that leaves a non-zero exit unchecked fails when its program ends.
103//! Which unchecked steps warn is the build's to say, from the results that stand
104//! when it settles (see [`BuildReport::unchecked`](crate::BuildReport::unchecked)).
105//!
106//! A missing or non-executable program fails the task and is recorded like any
107//! other failure, with every path checked and the failure message, which a cache hit
108//! fails with again.
109//!
110//! Commands that ran ("Order of execution"): a step is noted as ran, with its
111//! decision, its warning for a repeated reason and its step event, only once kizz is
112//! about to record that its program is missing or not executable, or to ask the
113//! tracer to run its command: after the lookup and the query of the machine state.
114//! A `run()` that fails before that point has no decision, so it is neither a
115//! command that ran nor a cached one, and it does no work for its pass. A bare
116//! program name without `PATH` in the step's environment and a malformed pattern
117//! fail the task without a record; kizz checks both from the step's own values
118//! before the cache check, so every pass fails such a call the same way, and kizz
119//! never attempts it. The other failures before that point are failures of kizz's
120//! own state: the store's reads of the cache check and of the explanation, and the
121//! locks of the build's shared state. They leave nothing in the build's memories,
122//! neither an `always` result nor a compared machine state, so a later pass
123//! evaluates the call again, since that state can change. A tracer failure counts as
124//! a command that ran, because the engine cannot tell whether the tracer started
125//! anything, and it leaves no record; the engine keeps it by step key for the rest
126//! of the build, so a later pass returns the same failure before the cache check,
127//! without a decision and without asking the tracer again. A record that cannot be
128//! stored belongs to a command that ran, and the engine does not keep it.
129//!
130//! Explanations ("Explaining decisions"): before a step runs, the engine turns the
131//! cache check's reason into an [`Explanation`] (see [`explain`](crate::explain)), and
132//! each step's [`StepDecision`] is kept for the line `kizz build` prints. For a task
133//! run made with [`Engine::task_for`], which knows its [`TaskIdentity`], the engine
134//! also stores, with each step record it writes, a last-writer record for every path
135//! the step wrote and the step-position record with the explanation; a cached step's
136//! position is stored when [`TaskSteps::finish`] stores the task record, which also
137//! removes the positions the run no longer reached. [`Engine::program_wrote`] stores
138//! a task program as the last writer of each file it changed through `fs.write` or
139//! `fs.write_json`. A step that re-runs in consecutive builds for the same
140//! self-inflicted reason adds a [`RepeatedWarning`].
141//!
142//! Owners ("Cleaning up the cache"): every step record carries the tasks that own
143//! it, by [`TaskId`]. A run made with [`Engine::task_for`] adds
144//! its task to the owners of the record it stores, in the transaction that stores
145//! it, and keeps the owners of the record it replaces under the same key, a record
146//! marked as not cached included; a run without a task identity
147//! adds no owner and keeps the others. A step noted as cached, whether a hit on a
148//! stored record or a result reused within the build, makes its task an owner of
149//! the record under its key in the transaction of [`TaskSteps::finish`] that stores
150//! its position; a hit that refreshes a record's observations keeps its owners. So
151//! after a build, every task that stores a step position for a key owns the record
152//! under that key. A path reset and `kizz cache clean` use the owners (see
153//! [`cleanup`](crate::cleanup)).
154//!
155//! Shared state ("Kizz never panics"): the engine's state that the threads of a
156//! build share is locked with `kizz_threads::lock_within`, never with
157//! `Mutex::lock`, which may panic when the calling thread holds the lock; a lock
158//! that stays held for the engine's lock patience, `kizz_threads::LOCK_PATIENCE`
159//! unless [`Engine::with_lock_patience`] sets another, is an error of the step, or
160//! of the call that reads the state. The state of one task run lives in `Cell`s
161//! that the private `cells` module changes, never in a `RefCell`, whose borrows
162//! panic while the cell is borrowed.
163
164use std::{
165    cell::Cell,
166    collections::{BTreeSet, HashMap, HashSet},
167    ffi::OsString,
168    fmt, mem,
169    net::SocketAddr,
170    path::PathBuf,
171    sync::{
172        Mutex, MutexGuard,
173        atomic::{AtomicU64, Ordering},
174    },
175    time::{Duration, Instant, SystemTime},
176};
177
178use kizz_store::{
179    AccessBits, BuildId, Capture, Connection, ContentHash, DiskRecord, Explanation,
180    FileSystemRecord, KernelRecord, LastWriter, LimitRecord, MachineChange, MachinePart,
181    MachineStateRecord, MemoryRecord, NotCachedReason, Observation, PathKey, PositionKey,
182    ProgramPath, Reason, RecordedOutput, RunReason, StepExit, StepKey, StepPosition, StepRecord,
183    StepSpecRecord, Store, StoreError, TaskId, TaskRecord, Txn, Verdict, WrittenBy,
184    machine_changes,
185};
186use kizz_threads::{LOCK_PATIENCE, LockError};
187use kizz_trace::{
188    AbsolutePath, AccessKind, Accesses, Cancellation, CaptureMode, CapturedOutput, EchoSink,
189    FirstReads, MachineState, Observations, ProcessTree, RunRequest, RunResult, Termination,
190    TraceError, Tracer,
191};
192
193use crate::{
194    cells,
195    check::{Checked, check},
196    execute::run_tree,
197    explain::{
198        Baseline, InputContext, RepeatedWarning, StepDecision, TaskIdentity, carried_from,
199        changed_inputs, spec_reasons,
200    },
201    files::FileChanges,
202    key::Occurrences,
203    lookup::{NoPathError, ProgramLookup, check_path, search_step_program},
204    observe::{changed_after_read, observe},
205    patterns::PathPatterns,
206    pool::WorkerPool,
207    report::{CommandInput, CommandOutcome, Execution},
208    runtime::ProgramHash,
209    states::FileStates,
210    step::{StepError, StepExecutor, StepOutcome, StepSpec},
211};
212
213/// Follows the steps of a task run as they start or come from the cache, for the
214/// live output of `kizz run`.
215pub trait StepEvents {
216    /// The step `decision` starts to run: its command has not started yet, so this
217    /// comes before any of its output.
218    fn step_started(
219        &self,
220        _decision: &StepDecision,
221    ) {
222    }
223
224    /// The step `decision` came from the cache, or was returned again within the
225    /// build, and returns `result`: its stored exit status and output, or its stored
226    /// failure.
227    fn step_cached(
228        &self,
229        _decision: &StepDecision,
230        _result: &Result<StepOutcome, StepError>,
231    ) {
232    }
233}
234
235/// Follows no step.
236#[derive(Debug, Clone, Copy, Default)]
237pub struct NoStepEvents;
238
239impl StepEvents for NoStepEvents {}
240
241/// Which commands' output the engine echoes live.
242#[derive(Debug, Clone, Copy, PartialEq, Eq)]
243enum LiveOutput {
244    /// Only the output of a `run()` with `stream = True`, as in a build.
245    Streamed,
246    /// Every command's output, as if every `run()` had `stream = True`, as `kizz
247    /// run` asks.
248    Every,
249}
250
251impl LiveOutput {
252    /// Whether the output of `step` is echoed live.
253    const fn echoes(
254        self,
255        step: &StepSpec,
256    ) -> bool {
257        step.stream || matches!(self, Self::Every)
258    }
259}
260
261/// What the engine keeps of each command for an observation report.
262#[derive(Debug, Clone, Copy, PartialEq, Eq)]
263enum ReportKeeping {
264    /// Nothing, and no request asks for the process tree, as in a build.
265    Nothing,
266    /// The command of each step, with its outcome, its process tree and the
267    /// lookup's observations, as `kizz run --output` asks.
268    Commands,
269}
270
271/// The identity of the most recent build this process started, so every build
272/// gets a larger one than the last.
273static LAST_BUILD: AtomicU64 = AtomicU64::new(0);
274
275/// A new build identity: now, in nanoseconds since the Unix epoch, or one more
276/// than the last build of this process when that is larger.
277fn next_build() -> BuildId {
278    let now = now_nanos();
279    let mut last = LAST_BUILD.load(Ordering::SeqCst);
280    loop {
281        let id = now.max(last.saturating_add(1));
282        match LAST_BUILD.compare_exchange_weak(last, id, Ordering::SeqCst, Ordering::SeqCst) {
283            Ok(_) => return BuildId(id),
284            Err(current) => last = current,
285        }
286    }
287}
288
289/// A result that was not cached, kept in memory for the rest of the build.
290#[derive(Debug, Clone)]
291struct NotCachedRun {
292    /// Why it was not cached.
293    why: NotCachedReason,
294    /// Whether tracing was deliberately disabled, rather than failing to observe a run.
295    untraced: bool,
296    /// Every touched path that no ignore pattern matched, with its state.
297    observations: Vec<Observation>,
298    /// When the engine began recording the states, in nanoseconds since the Unix
299    /// epoch.
300    recorded_at_nanos: u64,
301    /// What the step returned.
302    result: Result<StepOutcome, StepError>,
303}
304
305/// A run of a step that made system calls that the tracer does not know, as the
306/// engine keeps it for the build's warnings.
307#[derive(Debug, Clone, PartialEq, Eq)]
308pub struct UnknownCalls {
309    /// The step key.
310    pub key: StepKey,
311    /// The number of each such call, sorted and without repeats.
312    pub numbers: Vec<u32>,
313    /// Whether the result was cached: only when the build caches such results and
314    /// no other reason kept it out of the cache.
315    pub cached: bool,
316}
317
318/// A run of a step that connected to IPv4 or IPv6 addresses or to Unix sockets, as
319/// the engine keeps it for the build's warnings.
320#[derive(Debug, Clone, PartialEq, Eq)]
321pub struct StepConnections {
322    /// The step key.
323    pub key: StepKey,
324    /// Each connection, sorted and without repeats.
325    pub connections: Vec<Connection>,
326    /// Whether the result was cached: connections never keep it out of the cache,
327    /// but another reason may.
328    pub cached: bool,
329}
330
331/// What every task of a build shares to run, check, and record its steps.
332pub struct Engine<'a> {
333    /// Runs and traces the commands.
334    tracer: &'a dyn Tracer,
335    /// Holds the step records.
336    store: &'a Store,
337    /// Where live output goes for steps with `stream = True`.
338    echo: &'a dyn EchoSink,
339    /// Stops a running command when set.
340    cancel: Cancellation,
341    /// The caller's home directory, which a leading `~/` in a pattern means.
342    home: Option<AbsolutePath>,
343    /// The file states and hashes of the build.
344    states: FileStates,
345    /// The `always` steps that already ran in the build, by step key, with their
346    /// result, which is `None` until the run ends.
347    always_ran: Mutex<HashMap<StepKey, Option<Result<StepOutcome, StepError>>>>,
348    /// The results of the build that were not cached, by step key.
349    not_cached: Mutex<HashMap<StepKey, NotCachedRun>>,
350    /// The tracer failures of the build, by step key: a step whose request the
351    /// tracer failed returns the same failure every later time it comes up in the
352    /// build, before the cache check, without a decision and without asking the
353    /// tracer again.
354    tracer_failed: Mutex<HashMap<StepKey, StepError>>,
355    /// The identity of the build.
356    build: BuildId,
357    /// The warnings for steps that re-ran in consecutive builds for the same
358    /// self-inflicted reason, in the order they ran.
359    warnings: Mutex<Vec<RepeatedWarning>>,
360    /// Whether a run that made system calls that the tracer does not know is cached
361    /// as if it had made none.
362    cache_unknown_system_calls: bool,
363    /// The runs of the build that made system calls that the tracer does not know,
364    /// in the order they ended.
365    unknown_calls: Mutex<Vec<UnknownCalls>>,
366    /// The runs of the build that made connections, in the order they ended.
367    connections: Mutex<Vec<StepConnections>>,
368    /// Whether a task run that leaves a step unchecked fails when its program
369    /// ends, as `kizz build --fail-unchecked` asks.
370    fail_unchecked: bool,
371    /// The command that runs the engine, as messages name it with one of its
372    /// options: `kizz build` unless [`Engine::with_command_name`] sets another, such
373    /// as `kizz run`.
374    command_name: &'static str,
375    /// The step keys whose recorded machine state the build already compared, or
376    /// whose step ran in the build. The machine state is compared at most once per
377    /// step key and build, so a step that names a part that changes all the time,
378    /// such as `memory`, runs at most once per build, and the build still settles.
379    machine_compared: Mutex<HashSet<StepKey>>,
380    /// How long a lock of the shared state above may stay held by another holder
381    /// before the step or the reader that waits for it fails: [`LOCK_PATIENCE`]
382    /// unless [`Engine::with_lock_patience`] sets another.
383    lock_patience: Duration,
384    /// Whether every step runs, as if it were marked `always`, and is still
385    /// recorded, as `kizz run --no-cache` asks.
386    no_cache: bool,
387    /// Which commands' output is echoed live: every command's, as if every `run()`
388    /// had `stream = True`, as `kizz run` asks, or only that of a `run()` with
389    /// `stream = True`.
390    live_output: LiveOutput,
391    /// Whether every request asks for the process tree and each task run keeps the
392    /// commands of its steps for the observation report, as `kizz run --output`
393    /// asks.
394    report: ReportKeeping,
395}
396
397impl fmt::Debug for Engine<'_> {
398    fn fmt(
399        &self,
400        f: &mut fmt::Formatter<'_>,
401    ) -> fmt::Result {
402        f.debug_struct("Engine")
403            .field("store", &self.store)
404            .field("home", &self.home)
405            .field("states", &self.states)
406            .field("always_ran", &self.always_ran)
407            .field("not_cached", &self.not_cached)
408            .field("tracer_failed", &self.tracer_failed)
409            .field("build", &self.build)
410            .field("warnings", &self.warnings)
411            .field(
412                "cache_unknown_system_calls",
413                &self.cache_unknown_system_calls,
414            )
415            .field("unknown_calls", &self.unknown_calls)
416            .field("connections", &self.connections)
417            .field("fail_unchecked", &self.fail_unchecked)
418            .field("command_name", &self.command_name)
419            .field("machine_compared", &self.machine_compared)
420            .field("lock_patience", &self.lock_patience)
421            .field("no_cache", &self.no_cache)
422            .field("live_output", &self.live_output)
423            .field("report", &self.report)
424            .finish_non_exhaustive()
425    }
426}
427
428/// What the engine's field `always_ran` holds, as a [`LockError`] names it.
429const ALWAYS_RAN: &str = "the results of the build's `always` steps";
430
431/// What the engine's field `not_cached` holds, as a [`LockError`] names it.
432const NOT_CACHED: &str = "the build's results that were not cached";
433
434/// What the engine's field `tracer_failed` holds, as a [`LockError`] names it.
435const TRACER_FAILED: &str = "the build's tracer failures";
436
437/// What the engine's field `warnings` holds, as a [`LockError`] names it.
438const WARNINGS: &str = "the build's warnings for repeated reasons";
439
440/// What the engine's field `unknown_calls` holds, as a [`LockError`] names it.
441const UNKNOWN_CALLS: &str = "the build's runs that made unknown system calls";
442
443/// What the engine's field `connections` holds, as a [`LockError`] names it.
444const CONNECTIONS: &str = "the build's runs that made connections";
445
446/// What the engine's field `machine_compared` holds, as a [`LockError`] names it.
447const MACHINE_COMPARED: &str = "the build's compared machine states";
448
449/// Lock `mutex`, which guards `what`, whether or not a thread panicked while
450/// holding it, with `kizz_threads::lock_within`, which never panics, waiting at
451/// most `patience` while another holder keeps it.
452fn lock<'m, T>(
453    mutex: &'m Mutex<T>,
454    what: &'static str,
455    patience: Duration,
456) -> Result<MutexGuard<'m, T>, LockError> {
457    kizz_threads::lock_within(mutex, what, patience)
458}
459
460/// [`lock`], with a lock that stays held as the error of the step.
461fn step_lock<'m, T>(
462    mutex: &'m Mutex<T>,
463    what: &'static str,
464    patience: Duration,
465) -> Result<MutexGuard<'m, T>, StepError> {
466    lock(mutex, what, patience).map_err(StepError::new)
467}
468
469impl<'a> Engine<'a> {
470    /// An engine for one build that runs commands with `tracer`, echoes live output
471    /// to `echo`, stops commands when `cancel` is set, stores records in `store`,
472    /// expands `~/` in patterns to `home`, the caller's home directory, and runs its
473    /// parallel work, hashing included, on `pool`.
474    #[must_use]
475    pub fn new(
476        tracer: &'a dyn Tracer,
477        store: &'a Store,
478        echo: &'a dyn EchoSink,
479        cancel: Cancellation,
480        home: Option<AbsolutePath>,
481        pool: &WorkerPool,
482    ) -> Self {
483        Self {
484            tracer,
485            store,
486            echo,
487            cancel,
488            home,
489            states: FileStates::new(pool.clone()),
490            always_ran: Mutex::new(HashMap::new()),
491            not_cached: Mutex::new(HashMap::new()),
492            tracer_failed: Mutex::new(HashMap::new()),
493            build: next_build(),
494            warnings: Mutex::new(Vec::new()),
495            cache_unknown_system_calls: false,
496            unknown_calls: Mutex::new(Vec::new()),
497            connections: Mutex::new(Vec::new()),
498            fail_unchecked: false,
499            command_name: "kizz build",
500            machine_compared: Mutex::new(HashSet::new()),
501            lock_patience: LOCK_PATIENCE,
502            no_cache: false,
503            live_output: LiveOutput::Streamed,
504            report: ReportKeeping::Nothing,
505        }
506    }
507
508    /// The engine, whose readers and steps wait at most `patience` for its shared
509    /// state while another holder keeps it locked, and then fail with a
510    /// [`LockError`] or a step error, instead of [`LOCK_PATIENCE`]. Tests use a
511    /// short patience to reach those errors without waiting for the default.
512    #[must_use]
513    pub const fn with_lock_patience(
514        mut self,
515        patience: Duration,
516    ) -> Self {
517        self.lock_patience = patience;
518        self
519    }
520
521    /// Hold the build's warnings for repeated reasons locked until the returned
522    /// guard is dropped, so a test of a caller can reach what a reader does when
523    /// the engine's state stays locked; only builds with debug assertions, such as
524    /// tests, have it.
525    ///
526    /// # Errors
527    ///
528    /// A [`LockError`] when the warnings stay locked for the engine's patience.
529    #[cfg(debug_assertions)]
530    pub fn hold_warnings(&self) -> Result<impl Sized + '_, LockError> {
531        lock(&self.warnings, WARNINGS, self.lock_patience)
532    }
533
534    /// The engine, which caches the result of a run that made system calls that
535    /// the tracer does not know, as if it had made none, when `cache` is set, as
536    /// `kizz build --cache-unknown-syscalls` asks. Without it, such a result is not
537    /// cached unless no other reason applies. The option is in no step key or
538    /// record.
539    #[must_use]
540    pub const fn with_cache_unknown_system_calls(
541        mut self,
542        cache: bool,
543    ) -> Self {
544        self.cache_unknown_system_calls = cache;
545        self
546    }
547
548    /// Whether the engine caches the results of runs that made system calls that
549    /// the tracer does not know.
550    #[must_use]
551    pub const fn caches_unknown_system_calls(&self) -> bool {
552        self.cache_unknown_system_calls
553    }
554
555    /// The engine, which runs every step as if it were marked `always` when
556    /// `no_cache` is set, as `kizz run --no-cache` asks: no cache check decides
557    /// whether a step runs, every result is still recorded as usual, and the reason
558    /// of a step that has a record names the option, unless the step is marked
559    /// `always` or its task `cache=never`. Nothing makes a step cached that would
560    /// run without it. The option is in no step key or record.
561    #[must_use]
562    pub const fn with_no_cache(
563        mut self,
564        no_cache: bool,
565    ) -> Self {
566        self.no_cache = no_cache;
567        self
568    }
569
570    /// The engine, which echoes every command's output live when `echo` is set, as
571    /// if every `run()` had `stream = True`, as `kizz run` asks. Without it, only
572    /// the output of a `run()` with `stream = True` is echoed. The option is in no
573    /// step key or record.
574    #[must_use]
575    pub const fn with_echo_every_step(
576        mut self,
577        echo: bool,
578    ) -> Self {
579        self.live_output = if echo {
580            LiveOutput::Every
581        } else {
582            LiveOutput::Streamed
583        };
584        self
585    }
586
587    /// The engine, which asks the tracer for the process tree of every command and
588    /// keeps the commands of each task run for the observation report when `report`
589    /// is set, as `kizz run --output` asks (see [`TaskSteps::commands`]). Without
590    /// it, no request asks for the tree and nothing more is kept. The option is in
591    /// no step key or record.
592    #[must_use]
593    pub const fn with_report(
594        mut self,
595        report: bool,
596    ) -> Self {
597        self.report = if report {
598            ReportKeeping::Commands
599        } else {
600            ReportKeeping::Nothing
601        };
602        self
603    }
604
605    /// Whether the engine keeps what the observation report needs.
606    #[must_use]
607    pub const fn reports(&self) -> bool {
608        matches!(self.report, ReportKeeping::Commands)
609    }
610
611    /// The tracer that runs the commands, whose error-name query names the
612    /// outcomes of a report.
613    pub(crate) fn tracer(&self) -> &'a dyn Tracer {
614        self.tracer
615    }
616
617    /// The runs of the build that made system calls that the tracer does not know,
618    /// in the order they ended, each with whether its result was cached.
619    ///
620    /// # Errors
621    ///
622    /// A [`LockError`] when the runs stay locked.
623    pub fn unknown_system_calls(&self) -> Result<Vec<UnknownCalls>, LockError> {
624        Ok(lock(&self.unknown_calls, UNKNOWN_CALLS, self.lock_patience)?.clone())
625    }
626
627    /// The runs of the build that connected to IPv4 or IPv6 addresses or to Unix
628    /// sockets, in the order they ended, each with its connections and whether its
629    /// result was cached. A cache hit is no run, so it adds nothing.
630    ///
631    /// # Errors
632    ///
633    /// A [`LockError`] when the runs stay locked.
634    pub fn connections(&self) -> Result<Vec<StepConnections>, LockError> {
635        Ok(lock(&self.connections, CONNECTIONS, self.lock_patience)?.clone())
636    }
637
638    /// The engine, which makes a task run that leaves a step unchecked fail when
639    /// its program ends, when `fail` is set, as `kizz build --fail-unchecked` asks.
640    /// Without it, an unchecked step only warns. The option is in no step key or
641    /// record.
642    #[must_use]
643    pub const fn with_fail_unchecked(
644        mut self,
645        fail: bool,
646    ) -> Self {
647        self.fail_unchecked = fail;
648        self
649    }
650
651    /// Whether a task run that leaves a step unchecked fails.
652    #[must_use]
653    pub const fn fails_unchecked(&self) -> bool {
654        self.fail_unchecked
655    }
656
657    /// The engine, whose messages name the command that runs it as `name`, such as
658    /// `kizz run`, with the option they mention, as in the failure of a task that
659    /// `--fail-unchecked` fails. Without it, they name `kizz build`. The name is in
660    /// no step key or record.
661    #[must_use]
662    pub const fn with_command_name(
663        mut self,
664        name: &'static str,
665    ) -> Self {
666        self.command_name = name;
667        self
668    }
669
670    /// The command that runs the engine, as messages name it: `kizz build` unless
671    /// [`Engine::with_command_name`] set another.
672    #[must_use]
673    pub const fn command_name(&self) -> &'static str {
674        self.command_name
675    }
676
677    /// The identity of the build.
678    #[must_use]
679    pub const fn build(&self) -> BuildId {
680        self.build
681    }
682
683    /// Whether cancellation was requested, so the build starts nothing new.
684    #[must_use]
685    pub fn is_cancelled(&self) -> bool {
686        self.cancel.is_cancelled()
687    }
688
689    /// The store that holds the build's records.
690    #[must_use]
691    pub(crate) const fn store(&self) -> &'a Store {
692        self.store
693    }
694
695    /// The warnings for steps that re-ran in consecutive builds for the same
696    /// self-inflicted reason, in the order they ran, one per step.
697    ///
698    /// # Errors
699    ///
700    /// A [`LockError`] when the warnings stay locked.
701    pub fn warnings(&self) -> Result<Vec<RepeatedWarning>, LockError> {
702        Ok(lock(&self.warnings, WARNINGS, self.lock_patience)?.clone())
703    }
704
705    /// Keep `warning`, unless the same step already has one in this build.
706    fn warn(
707        &self,
708        warning: RepeatedWarning,
709    ) -> Result<(), StepError> {
710        let mut warnings = step_lock(&self.warnings, WARNINGS, self.lock_patience)?;
711        let known = warnings.iter().any(|known| {
712            known.task.as_ref().map(|task| &task.task)
713                == warning.task.as_ref().map(|task| &task.task)
714                && known.position == warning.position
715                && known.command == warning.command
716        });
717        if !known {
718            warnings.push(warning);
719        }
720        Ok(())
721    }
722
723    /// The number of files whose content this engine has hashed, to record steps
724    /// and to check the cache.
725    #[must_use]
726    pub fn files_hashed(&self) -> u64 {
727        self.states.files_hashed()
728    }
729
730    /// The file states and hashes of the build.
731    #[must_use]
732    pub const fn file_states(&self) -> &FileStates {
733        &self.states
734    }
735
736    /// Store the program of the task `task` as the last writer of each file in
737    /// `changes`, the files it changed through `fs.write` and `fs.write_json` in this
738    /// build, with the time of each change, and drop their cached hashes. A file
739    /// whose last writer wrote it later, such as a step that the program ran after
740    /// its write, keeps that writer.
741    ///
742    /// # Errors
743    ///
744    /// A [`StoreError`] when a record cannot be read or written.
745    pub fn program_wrote(
746        &self,
747        task: &TaskId,
748        changes: &FileChanges,
749    ) -> Result<(), StoreError> {
750        if changes.is_empty() {
751            return Ok(());
752        }
753        let mut written = Accesses::new();
754        for file in changes.files() {
755            written.record(file.path.clone(), AccessKind::Write);
756        }
757        self.states.forget_written(&written);
758        let mut txn = self.store.write()?;
759        for file in changes.files() {
760            let key = PathKey(file.path.as_path().to_path_buf());
761            if txn
762                .get::<LastWriter>(&key)?
763                .is_some_and(|entry| entry.written_at_nanos > file.at_nanos)
764            {
765                continue;
766            }
767            txn.put(&key, &LastWriter {
768                task: task.clone(),
769                by: WrittenBy::Program,
770                build: self.build,
771                written_at_nanos: file.at_nanos,
772            })?;
773        }
774        txn.commit()
775    }
776
777    /// The steps of the build whose last result was not cached, with why, sorted by
778    /// step key.
779    ///
780    /// # Errors
781    ///
782    /// A [`LockError`] when the results stay locked.
783    pub fn not_cached(&self) -> Result<Vec<(StepKey, NotCachedReason)>, LockError> {
784        let mut steps: Vec<_> = lock(&self.not_cached, NOT_CACHED, self.lock_patience)?
785            .iter()
786            .map(|(key, run)| (*key, run.why.clone()))
787            .collect();
788        steps.sort_by_key(|(key, _)| *key);
789        Ok(steps)
790    }
791
792    /// Whether a result was explicitly untraced, so it needs no incomplete-trace warning.
793    ///
794    /// # Errors
795    ///
796    /// Returns a lock error when the build's results stay locked.
797    pub fn was_untraced(
798        &self,
799        key: &StepKey,
800    ) -> Result<bool, LockError> {
801        Ok(lock(&self.not_cached, NOT_CACHED, self.lock_patience)?
802            .get(key)
803            .is_some_and(|run| run.untraced))
804    }
805
806    /// The step executor of one run of a task program whose hash is `program` and
807    /// whose directory is `task_dir`, without a task identity: its steps are checked,
808    /// run, recorded, and explained, but no step position, last writer, or task
809    /// record is stored for them, and no task becomes an owner of their records,
810    /// whose other owners are kept. Builds use [`Engine::task_for`].
811    #[must_use]
812    pub fn task(
813        &self,
814        program: ProgramHash,
815        task_dir: AbsolutePath,
816    ) -> TaskSteps<'_> {
817        TaskSteps {
818            engine: self,
819            program,
820            task_dir,
821            identity: None,
822            occurrences: Cell::new(Occurrences::new()),
823            keys: Cell::new(Vec::new()),
824            decisions: Cell::new(Vec::new()),
825            cached_positions: Cell::new(Vec::new()),
826            cache_never: false,
827            commands: Cell::new(Vec::new()),
828            events: &NoStepEvents,
829        }
830    }
831
832    /// The step executor of one run of the task `identity`, which stores the step
833    /// positions and last writers of its steps, makes the task an owner of the
834    /// record of every step it runs or finds cached, and stores its task record when
835    /// the run ends with [`TaskSteps::finish`].
836    #[must_use]
837    pub fn task_for(
838        &self,
839        identity: TaskIdentity,
840    ) -> TaskSteps<'_> {
841        TaskSteps {
842            engine: self,
843            program: identity.program,
844            task_dir: identity.dir.clone(),
845            identity: Some(identity),
846            occurrences: Cell::new(Occurrences::new()),
847            keys: Cell::new(Vec::new()),
848            decisions: Cell::new(Vec::new()),
849            cached_positions: Cell::new(Vec::new()),
850            cache_never: false,
851            commands: Cell::new(Vec::new()),
852            events: &NoStepEvents,
853        }
854    }
855
856    /// The result of the `always` step `key` when it already ran in this build, as
857    /// a result that did not run; otherwise mark it as running and return `None`.
858    fn first_always_result(
859        &self,
860        key: StepKey,
861    ) -> Result<Option<Result<StepOutcome, StepError>>, StepError> {
862        let mut ran = step_lock(&self.always_ran, ALWAYS_RAN, self.lock_patience)?;
863        Ok(match ran.get(&key) {
864            Some(Some(result)) => Some(result.clone()),
865            Some(None) => {
866                Some(Err(StepError::new(
867                    "an `always` step came up again while its one run in the build had not ended",
868                )))
869            },
870            None => {
871                ran.insert(key, None);
872                None
873            },
874        })
875    }
876
877    /// Keep `result`, the result of the one run of the `always` step `key` in this
878    /// build, to return every later time the step comes up in the build.
879    fn finish_always(
880        &self,
881        key: StepKey,
882        result: &Result<StepOutcome, StepError>,
883    ) -> Result<(), StepError> {
884        let result = result.clone().map(|outcome| {
885            StepOutcome {
886                cached: true,
887                ..outcome
888            }
889        });
890        step_lock(&self.always_ran, ALWAYS_RAN, self.lock_patience)?.insert(key, Some(result));
891        Ok(())
892    }
893
894    /// Take back what the step `key` marked in the build's memories, as `marks`
895    /// says, before it failed without being noted as ran: its `always` run, which
896    /// had not ended, and its compared machine state. So a later pass evaluates the
897    /// call again, with the cache check, instead of returning a result of a run that
898    /// never started.
899    fn forget_marks(
900        &self,
901        key: StepKey,
902        marks: Marks,
903    ) -> Result<(), StepError> {
904        if marks.always {
905            let mut ran = step_lock(&self.always_ran, ALWAYS_RAN, self.lock_patience)?;
906            if matches!(ran.get(&key), Some(None)) {
907                ran.remove(&key);
908            }
909        }
910        if marks.compared {
911            step_lock(&self.machine_compared, MACHINE_COMPARED, self.lock_patience)?.remove(&key);
912        }
913        Ok(())
914    }
915
916    /// The tracer failure that a run of the step `key` met earlier in this build,
917    /// if one did.
918    fn tracer_failure(
919        &self,
920        key: StepKey,
921    ) -> Result<Option<StepError>, StepError> {
922        Ok(
923            step_lock(&self.tracer_failed, TRACER_FAILED, self.lock_patience)?
924                .get(&key)
925                .cloned(),
926        )
927    }
928
929    /// Keep `failure`, the tracer failure of the run of the step `key`, to return
930    /// every later time the step comes up in the build.
931    fn remember_tracer_failure(
932        &self,
933        key: StepKey,
934        failure: &StepError,
935    ) -> Result<(), StepError> {
936        step_lock(&self.tracer_failed, TRACER_FAILED, self.lock_patience)?
937            .insert(key, failure.clone());
938        Ok(())
939    }
940}
941
942/// The step executor of one run of a task program.
943pub struct TaskSteps<'a> {
944    /// The engine.
945    engine: &'a Engine<'a>,
946    /// The hash of the task program.
947    program: ProgramHash,
948    /// The task directory, at which relative patterns are anchored.
949    task_dir: AbsolutePath,
950    /// The task's identity, when the run stores step positions, last writers, and a
951    /// task record.
952    identity: Option<TaskIdentity>,
953    /// Counts identical commands in the run.
954    occurrences: Cell<Occurrences>,
955    /// The key of each step of the run, in order.
956    keys: Cell<Vec<StepKey>>,
957    /// What the build decided about each step of the run, in order.
958    decisions: Cell<Vec<StepDecision>>,
959    /// The step positions of the cached steps, stored by [`TaskSteps::finish`],
960    /// which also makes the task an owner of the record each of them names.
961    cached_positions: Cell<Vec<(PositionKey, StepPosition)>>,
962    /// Whether the task is marked `cache=never`, so every step runs as if it were
963    /// marked `always`.
964    cache_never: bool,
965    /// The command of each step of the run that reached a decision, and of each
966    /// step whose bare program name has no `PATH`, in order, with its step key,
967    /// kept for the observation report only when the engine writes one
968    /// ([`Engine::with_report`]).
969    commands: Cell<Vec<(StepKey, CommandInput)>>,
970    /// Follows the steps as they start or come from the cache.
971    events: &'a dyn StepEvents,
972}
973
974impl fmt::Debug for TaskSteps<'_> {
975    fn fmt(
976        &self,
977        f: &mut fmt::Formatter<'_>,
978    ) -> fmt::Result {
979        f.debug_struct("TaskSteps")
980            .field("engine", &self.engine)
981            .field("program", &self.program)
982            .field("task_dir", &self.task_dir)
983            .field("identity", &self.identity)
984            .field("keys", &cells::cloned(&self.keys))
985            .field("decisions", &cells::cloned(&self.decisions))
986            .field("cache_never", &self.cache_never)
987            .finish_non_exhaustive()
988    }
989}
990
991/// What is known about a step before it runs.
992struct Pending {
993    /// The step key.
994    key: StepKey,
995    /// The number of identical commands earlier in the run.
996    occurrence: u32,
997    /// Why the step runs.
998    reason: RunReason,
999    /// The step's ignore patterns.
1000    ignore: PathPatterns,
1001    /// The step's `track` patterns.
1002    track: PathPatterns,
1003    /// The position of the step in the task's run.
1004    position: u32,
1005    /// Why the step runs, explained.
1006    explanation: Explanation,
1007    /// The self-inflicted inputs that made the step run in its task's previous
1008    /// build, for its step position.
1009    carried: Vec<PathBuf>,
1010}
1011
1012/// Whether a step runs, as the cache check decided.
1013enum Decision {
1014    /// The step runs, for this reason; with the recorded state the cache check
1015    /// compared, when it compared one.
1016    Run(RunReason, Option<Baseline>),
1017    /// The record is a cache hit.
1018    Hit {
1019        /// The record.
1020        record: Box<StepRecord>,
1021        /// The comparison of its observations with the file system.
1022        checked: Checked,
1023        /// When the check began, in nanoseconds since the Unix epoch.
1024        checked_at_nanos: u64,
1025    },
1026    /// A result of this build that was not cached is returned again, because
1027    /// nothing it touched changed.
1028    Replay(Result<StepOutcome, StepError>),
1029}
1030
1031/// What a step marked in the build's memories before it was noted as ran, which
1032/// [`Engine::forget_marks`] takes back when the step fails before that point.
1033#[derive(Debug, Clone, Copy, Default)]
1034struct Marks {
1035    /// The step marked its `always` run in the build as started.
1036    always: bool,
1037    /// The step added its key to the build's compared machine states.
1038    compared: bool,
1039}
1040
1041/// How a step that the cache check let run ended: before it was noted as ran, or
1042/// after.
1043enum Attempt {
1044    /// The step failed before it was noted as ran: kizz neither recorded it nor
1045    /// asked the tracer to run it, and it has no decision.
1046    NotStarted(StepError),
1047    /// The step was noted as ran, because kizz was about to record that its
1048    /// program is missing or not executable or to ask the tracer to run it, and
1049    /// this is its result.
1050    Ran(Result<StepOutcome, StepError>),
1051}
1052
1053/// How a step ended, before its record is stored.
1054struct Finished {
1055    /// The program that ran, if one was found.
1056    program: Option<AbsolutePath>,
1057    /// Every path touched, the locations the lookup checked included.
1058    accesses: Accesses,
1059    /// How the command ended.
1060    exit: StepExit,
1061    /// The raw captured output.
1062    output: CapturedOutput,
1063    /// How long the command ran.
1064    duration: Duration,
1065    /// When the command started.
1066    ran_at: SystemTime,
1067    /// The failure message of a missing or non-executable program, or of a command
1068    /// that could not start.
1069    failure: Option<String>,
1070    /// The first-read metadata the tracer noted, empty for a command that did not
1071    /// run.
1072    first_reads: FirstReads,
1073    /// The numbers of the system calls that the command made and that the tracer
1074    /// does not know, sorted and without repeats; empty for a command that did not
1075    /// run.
1076    unknown_system_calls: Vec<u32>,
1077    /// The connections that the command made, sorted and without repeats; empty
1078    /// for a command that did not run.
1079    connections: Vec<Connection>,
1080    /// The machine state that the command started with, queried right before the
1081    /// lookup of its program.
1082    machine: MachineStateRecord,
1083}
1084
1085/// The machine state `state` that the tracer reported, as a record keeps it.
1086fn machine_record(state: &MachineState) -> MachineStateRecord {
1087    MachineStateRecord {
1088        kernel: state.kernel.as_ref().map(|kernel| {
1089            KernelRecord {
1090                release: kernel.release.clone(),
1091                version: kernel.version.clone(),
1092            }
1093        }),
1094        limits: state.limits.as_ref().map(|limits| {
1095            limits
1096                .iter()
1097                .map(|limit| {
1098                    LimitRecord {
1099                        resource: limit.resource.clone(),
1100                        soft: limit.soft,
1101                        hard: limit.hard,
1102                    }
1103                })
1104                .collect()
1105        }),
1106        affinity: state.affinity.clone(),
1107        memory: state.memory.map(|memory| {
1108            MemoryRecord {
1109                total: memory.total,
1110                available: memory.available,
1111            }
1112        }),
1113        filesystem: state.filesystem.map(|filesystem| {
1114            FileSystemRecord {
1115                kind: filesystem.kind,
1116                flags: filesystem.flags,
1117            }
1118        }),
1119        disk: state.disk.map(|disk| {
1120            DiskRecord {
1121                size: disk.size,
1122                free: disk.free,
1123            }
1124        }),
1125    }
1126}
1127
1128/// The connection `connection` that the tracer reported, as a record keeps it.
1129fn stored_connection(connection: &kizz_trace::Connection) -> Connection {
1130    match connection {
1131        kizz_trace::Connection::Ip(SocketAddr::V4(address)) => {
1132            Connection::Ipv4 {
1133                address: address.ip().octets(),
1134                port: address.port(),
1135            }
1136        },
1137        kizz_trace::Connection::Ip(SocketAddr::V6(address)) => {
1138            Connection::Ipv6 {
1139                address: address.ip().octets(),
1140                port: address.port(),
1141                scope: address.scope_id(),
1142            }
1143        },
1144        kizz_trace::Connection::UnixPath(path) => {
1145            Connection::UnixPath {
1146                path: path.as_path().to_path_buf(),
1147            }
1148        },
1149        kizz_trace::Connection::UnixAbstract(name) => {
1150            Connection::UnixAbstract { name: name.clone() }
1151        },
1152    }
1153}
1154
1155/// The connections `connections` that the tracer reported, as a record keeps them:
1156/// sorted and without repeats.
1157fn stored_connections(connections: &BTreeSet<kizz_trace::Connection>) -> Vec<Connection> {
1158    connections
1159        .iter()
1160        .map(stored_connection)
1161        .collect::<BTreeSet<_>>()
1162        .into_iter()
1163        .collect()
1164}
1165
1166/// A step error from a store error.
1167fn store_error(error: &StoreError) -> StepError {
1168    StepError::new(format_args!("cannot record the step in the cache: {error}"))
1169}
1170
1171/// The paths in `checked`, as a list for messages.
1172fn checked_list(checked: &Accesses) -> String {
1173    checked
1174        .iter()
1175        .map(|(path, _)| path.to_string())
1176        .collect::<Vec<_>>()
1177        .join(", ")
1178}
1179
1180/// The message of a step whose program `name` the lookup did not find.
1181fn missing_program_message(
1182    name: &str,
1183    lookup: &ProgramLookup,
1184) -> String {
1185    let checked = checked_list(lookup.checked());
1186    match lookup {
1187        ProgramLookup::NotExecutable { candidate, .. } => {
1188            format!("program `{name}` is not executable: {candidate}; checked {checked}")
1189        },
1190        ProgramLookup::NotFound { .. } | ProgramLookup::Found { .. } => {
1191            format!(
1192                "program `{name}` was not found in the task environment's PATH; checked \
1193                 {checked}"
1194            )
1195        },
1196    }
1197}
1198
1199/// The message of a step whose found program the tracer reports as missing or not
1200/// executable, as `error` says, with the locations `checked` that the lookup
1201/// checked, when it checked any.
1202fn missing_message(
1203    error: &TraceError,
1204    checked: Option<&str>,
1205) -> String {
1206    match checked {
1207        None => error.to_string(),
1208        Some(list) => format!("{error}; checked {list}"),
1209    }
1210}
1211
1212/// The capture mode as the store records it.
1213const fn capture(mode: CaptureMode) -> Capture {
1214    match mode {
1215        CaptureMode::Split => Capture::Split,
1216        CaptureMode::Merged => Capture::Merged,
1217    }
1218}
1219
1220/// Captured output as the store records it.
1221fn recorded_output(output: CapturedOutput) -> RecordedOutput {
1222    match output {
1223        CapturedOutput::Split { stdout, stderr } => RecordedOutput::Split { stdout, stderr },
1224        CapturedOutput::Merged { output } => RecordedOutput::Merged { output },
1225    }
1226}
1227
1228/// Recorded output as the program receives it.
1229fn captured_output(output: RecordedOutput) -> CapturedOutput {
1230    match output {
1231        RecordedOutput::Split { stdout, stderr } => CapturedOutput::Split { stdout, stderr },
1232        RecordedOutput::Merged { output } => CapturedOutput::Merged { output },
1233    }
1234}
1235
1236/// A duration in nanoseconds.
1237fn nanos(duration: Duration) -> u64 {
1238    u64::try_from(duration.as_nanos()).unwrap_or(u64::MAX)
1239}
1240
1241/// A time in nanoseconds since the Unix epoch.
1242fn epoch_nanos(time: SystemTime) -> u64 {
1243    nanos(
1244        time.duration_since(SystemTime::UNIX_EPOCH)
1245            .unwrap_or_default(),
1246    )
1247}
1248
1249/// Now, in nanoseconds since the Unix epoch.
1250fn now_nanos() -> u64 {
1251    epoch_nanos(SystemTime::now())
1252}
1253
1254/// How a command that ran ended, as the store records it.
1255const fn step_exit(termination: Termination) -> StepExit {
1256    match termination {
1257        Termination::Exited(code) => StepExit::Exited { code },
1258        Termination::Signaled(signal) => StepExit::Signaled { signal },
1259    }
1260}
1261
1262/// The request that runs `step` with the found program `program`: its exact
1263/// arguments, environment, working directory, `stdin`, capture mode and echo,
1264/// which `live_output` decides, with the process tree only when `tree` is set,
1265/// which a build never asks for and `kizz run --output` does.
1266fn run_request(
1267    step: &StepSpec,
1268    program: AbsolutePath,
1269    live_output: LiveOutput,
1270    tree: bool,
1271) -> RunRequest {
1272    RunRequest {
1273        program,
1274        args: step_argv(step),
1275        env: step
1276            .env
1277            .iter()
1278            .map(|(name, value)| (OsString::from(name), OsString::from(value)))
1279            .collect(),
1280        cwd: step.cwd.clone(),
1281        stdin: step.stdin.as_ref().map(|text| text.as_bytes().to_vec()),
1282        capture: step.capture,
1283        echo: live_output.echoes(step),
1284        tree,
1285        terminal: false,
1286    }
1287}
1288
1289/// The arguments of `step`, starting with its program as given.
1290fn step_argv(step: &StepSpec) -> Vec<OsString> {
1291    step.argv.iter().map(OsString::from).collect()
1292}
1293
1294/// The command of `step`, which ran, or whose program kizz did not find, for the
1295/// observation report: with the found program `program`, if any, how it ended,
1296/// the tracer's `tree`, or `None` when kizz started no process, and the lookup's
1297/// observations `lookup`.
1298fn ran_command(
1299    step: &StepSpec,
1300    program: Option<AbsolutePath>,
1301    outcome: CommandOutcome,
1302    tree: Option<ProcessTree>,
1303    lookup: Observations,
1304) -> CommandInput {
1305    CommandInput {
1306        argv: step_argv(step),
1307        program,
1308        cwd: step.cwd.clone(),
1309        execution: Execution::Ran {
1310            outcome,
1311            tree,
1312            lookup,
1313        },
1314    }
1315}
1316
1317/// The command of `step`, a cache hit on `record`, for the observation report:
1318/// cached, with the recorded program and outcome, and no observations.
1319fn cached_command(
1320    step: &StepSpec,
1321    record: &StepRecord,
1322) -> CommandInput {
1323    CommandInput {
1324        argv: step_argv(step),
1325        program: record
1326            .program
1327            .as_ref()
1328            .and_then(|program| AbsolutePath::new(&program.0).ok()),
1329        cwd: step.cwd.clone(),
1330        execution: Execution::Cached {
1331            outcome: recorded_outcome(record),
1332        },
1333    }
1334}
1335
1336/// How the run that `record` recorded ended, as a report names it, with the
1337/// recorded failure as the message of a command that did not start.
1338fn recorded_outcome(record: &StepRecord) -> CommandOutcome {
1339    let failure = || record.failure.clone().unwrap_or_default();
1340    match record.exit {
1341        StepExit::Exited { code } => CommandOutcome::Exited(code),
1342        StepExit::Signaled { signal } => CommandOutcome::Signaled(signal),
1343        StepExit::ProgramNotFound => CommandOutcome::NotFound(failure()),
1344        StepExit::ProgramNotExecutable => CommandOutcome::NotExecutable(failure()),
1345        StepExit::NotStarted => CommandOutcome::StartFailed(failure()),
1346    }
1347}
1348
1349/// What a step whose record is `record` returns on a cache hit: the recorded exit
1350/// status and raw output, with `cached` set, or the recorded failure of a missing or
1351/// non-executable program.
1352fn replay(record: StepRecord) -> Result<StepOutcome, StepError> {
1353    let termination = match record.exit {
1354        StepExit::Exited { code } => Termination::Exited(code),
1355        StepExit::Signaled { signal } => Termination::Signaled(signal),
1356        StepExit::ProgramNotFound | StepExit::ProgramNotExecutable | StepExit::NotStarted => {
1357            let program = record.spec.argv.first().map_or("", String::as_str);
1358            return Err(StepError::new(record.failure.unwrap_or_else(|| {
1359                format!("program `{program}` could not be run")
1360            })));
1361        },
1362    };
1363    Ok(StepOutcome {
1364        termination,
1365        output: captured_output(record.output),
1366        cached: true,
1367    })
1368}
1369
1370impl<'a> TaskSteps<'a> {
1371    /// The step executor, which tells `events` when each step starts to run and
1372    /// when each comes from the cache, as `kizz run` asks for its live output.
1373    #[must_use]
1374    pub const fn with_events(
1375        mut self,
1376        events: &'a dyn StepEvents,
1377    ) -> Self {
1378        self.events = events;
1379        self
1380    }
1381}
1382
1383impl TaskSteps<'_> {
1384    /// The step executor, which runs every step as if it were marked `always`, with
1385    /// the reason that names the task option, when `never` says that the task is
1386    /// marked `cache=never`. The option is in no step key.
1387    #[must_use]
1388    pub const fn with_cache_never(
1389        mut self,
1390        never: bool,
1391    ) -> Self {
1392        self.cache_never = never;
1393        self
1394    }
1395
1396    /// The key of each step so far, in order.
1397    #[must_use]
1398    pub fn keys(&self) -> Vec<StepKey> {
1399        cells::cloned(&self.keys)
1400    }
1401
1402    /// What the build decided about each step so far, in order: why each one ran,
1403    /// or that it was cached.
1404    #[must_use]
1405    pub fn decisions(&self) -> Vec<StepDecision> {
1406        cells::cloned(&self.decisions)
1407    }
1408
1409    /// The command of each step so far that reached a decision, in order, for the
1410    /// observation report: a step that ran, or whose program kizz did not find,
1411    /// with its outcome, its process tree and the lookup's observations, and a step
1412    /// that came from the cache as cached. A step whose bare program name has no
1413    /// `PATH` is in it too, as a command that started no process, although it has
1414    /// no decision. Empty unless the engine writes a report
1415    /// ([`Engine::with_report`]).
1416    #[must_use]
1417    pub fn commands(&self) -> Vec<CommandInput> {
1418        cells::update(&self.commands, |commands| {
1419            commands
1420                .iter()
1421                .map(|(_, command)| command.clone())
1422                .collect()
1423        })
1424    }
1425
1426    /// Keep the command that `command` makes, the command of the step `key`, for
1427    /// the observation report, when the engine writes one; otherwise make nothing.
1428    fn keep(
1429        &self,
1430        key: StepKey,
1431        command: impl FnOnce() -> CommandInput,
1432    ) {
1433        if self.engine.reports() {
1434            let command = command();
1435            cells::update(&self.commands, |commands| commands.push((key, command)));
1436        }
1437    }
1438
1439    /// The command of `step`, whose key is `key`, which returns `result` again
1440    /// without running, for the observation report: cached, with the program and
1441    /// outcome of the latest command of the run under the same key, or else with
1442    /// the outcome of `result` and no program; a failure then reads as a start
1443    /// that failed, with its message.
1444    fn replayed_command(
1445        &self,
1446        key: StepKey,
1447        step: &StepSpec,
1448        result: &Result<StepOutcome, StepError>,
1449    ) -> CommandInput {
1450        let earlier = cells::update(&self.commands, |commands| {
1451            commands
1452                .iter()
1453                .rev()
1454                .find(|(kept, _)| *kept == key)
1455                .map(|(_, command)| command.clone())
1456        });
1457        let (program, outcome) = match earlier {
1458            Some(CommandInput {
1459                program,
1460                execution: Execution::Cached { outcome } | Execution::Ran { outcome, .. },
1461                ..
1462            }) => (program, outcome),
1463            None => {
1464                let outcome = match result {
1465                    Ok(outcome) => CommandOutcome::from_termination(outcome.termination),
1466                    Err(error) => CommandOutcome::StartFailed(error.to_string()),
1467                };
1468                (None, outcome)
1469            },
1470        };
1471        CommandInput {
1472            argv: step_argv(step),
1473            program,
1474            cwd: step.cwd.clone(),
1475            execution: Execution::Cached { outcome },
1476        }
1477    }
1478
1479    /// End the run of the task: store the step positions of its cached steps, add
1480    /// the task to the owners of the record each of them names, remove the positions
1481    /// beyond its last step, and store its task record, all in one transaction, with
1482    /// `succeeded` saying whether the run succeeded. Without a task identity this
1483    /// stores nothing.
1484    ///
1485    /// Every way a step is noted as cached makes its task an owner here: a hit on a
1486    /// stored record, and a result reused within the build, an `always` result or a
1487    /// result that was not cached, whose run stored the record under the key. A
1488    /// record that the task already owns is not written again for its owners. A step
1489    /// that ran stored its position and became its record's owner when it ran.
1490    ///
1491    /// # Errors
1492    ///
1493    /// A [`StoreError`] when the records cannot be written.
1494    pub fn finish(
1495        &self,
1496        succeeded: bool,
1497    ) -> Result<(), StoreError> {
1498        let Some(identity) = &self.identity else {
1499            return Ok(());
1500        };
1501        let steps = u32::try_from(cells::update(&self.keys, |keys| keys.len())).unwrap_or(u32::MAX);
1502        let mut txn = self.engine.store.write()?;
1503        for (key, position) in self.cached_positions.take() {
1504            if let Some(mut record) = txn.get::<StepRecord>(&position.step)?
1505                && record.owners.insert(identity.id.clone())
1506            {
1507                txn.put(&position.step, &record)?;
1508            }
1509            txn.put(&key, &position)?;
1510        }
1511        for (key, _) in txn.scan::<StepPosition>(&identity.id.key_prefix())? {
1512            if key.task == identity.id && key.position >= steps {
1513                txn.delete::<StepPosition>(&key)?;
1514            }
1515        }
1516        txn.put(
1517            &identity.id,
1518            &identity.task_record(succeeded, self.engine.build, steps),
1519        )?;
1520        txn.commit()
1521    }
1522
1523    /// The patterns `patterns` of a step, anchored at the task directory.
1524    fn patterns(
1525        &self,
1526        patterns: &[String],
1527    ) -> Result<PathPatterns, StepError> {
1528        PathPatterns::new(patterns, &self.task_dir, self.engine.home.as_ref())
1529            .map_err(StepError::new)
1530    }
1531
1532    /// The record stored under `key`, if there is one.
1533    fn record(
1534        &self,
1535        key: &StepKey,
1536    ) -> Result<Option<StepRecord>, StepError> {
1537        self.engine
1538            .store
1539            .read()
1540            .and_then(|txn| txn.get::<StepRecord>(key))
1541            .map_err(|error| store_error(&error))
1542    }
1543
1544    /// Store `record`, the record of a cache hit with refreshed observations, under
1545    /// `key`, keeping the owners of the record stored there; and forget any result
1546    /// of the build under `key` that was not cached.
1547    fn put(
1548        &self,
1549        key: &StepKey,
1550        record: &mut StepRecord,
1551    ) -> Result<(), StepError> {
1552        let write = |record: &mut StepRecord| -> Result<(), StoreError> {
1553            let mut txn = self.engine.store.write()?;
1554            if let Some(stored) = txn.get::<StepRecord>(key)? {
1555                record.owners.extend(stored.owners);
1556            }
1557            txn.put(key, record)?;
1558            txn.commit()
1559        };
1560        write(record).map_err(|error| store_error(&error))?;
1561        step_lock(
1562            &self.engine.not_cached,
1563            NOT_CACHED,
1564            self.engine.lock_patience,
1565        )?
1566        .remove(key);
1567        Ok(())
1568    }
1569
1570    /// Store `record`, the record of a run of the step `pending`, and, with a task
1571    /// identity, a last-writer record for every path the step wrote and the step's
1572    /// position with its explanation, all in one transaction; then forget any
1573    /// result of the build under its key that was not cached.
1574    ///
1575    /// The record keeps the owners of the record it replaces under the same key,
1576    /// whether the run is a run for changed inputs or one whose result is not
1577    /// cached, and with a task identity it adds the task to them, in the same
1578    /// transaction, so the task owns the record that its step position names.
1579    fn put_run(
1580        &self,
1581        pending: &Pending,
1582        record: &mut StepRecord,
1583    ) -> Result<(), StepError> {
1584        let write = |record: &mut StepRecord| -> Result<(), StoreError> {
1585            let mut txn = self.engine.store.write()?;
1586            if let Some(stored) = txn.get::<StepRecord>(&pending.key)? {
1587                record.owners.extend(stored.owners);
1588            }
1589            if let Some(identity) = &self.identity {
1590                record.owners.insert(identity.id.clone());
1591            }
1592            txn.put(&pending.key, record)?;
1593            if let Some(identity) = &self.identity {
1594                for observation in &record.observations {
1595                    if observation.access.contains(AccessBits::WRITE) {
1596                        txn.put(&PathKey(observation.path.clone()), &LastWriter {
1597                            task: identity.id.clone(),
1598                            by: WrittenBy::Step {
1599                                step: pending.key,
1600                                position: pending.position,
1601                            },
1602                            build: self.engine.build,
1603                            written_at_nanos: record.recorded_at_nanos,
1604                        })?;
1605                    }
1606                }
1607                txn.put(
1608                    &PositionKey {
1609                        task: identity.id.clone(),
1610                        position: pending.position,
1611                    },
1612                    &StepPosition {
1613                        step: pending.key,
1614                        build: self.engine.build,
1615                        verdict: Verdict::Ran(pending.explanation.clone()),
1616                        carried: pending.carried.clone(),
1617                    },
1618                )?;
1619            }
1620            txn.commit()
1621        };
1622        write(record).map_err(|error| store_error(&error))?;
1623        step_lock(
1624            &self.engine.not_cached,
1625            NOT_CACHED,
1626            self.engine.lock_patience,
1627        )?
1628        .remove(&pending.key);
1629        Ok(())
1630    }
1631
1632    /// Whether the step `step` runs as if it were marked `always`: it is, its task
1633    /// is marked `cache=never`, or the engine runs every step (`kizz run
1634    /// --no-cache`).
1635    const fn runs_always(
1636        &self,
1637        step: &StepSpec,
1638    ) -> bool {
1639        step.untraced || step.always || self.cache_never || self.engine.no_cache
1640    }
1641
1642    /// Decide whether the step `step`, whose key is `key`, runs; `marks` gains
1643    /// what the decision marked in the build's memories: the start of an `always`
1644    /// run, and the comparison of the record's machine state.
1645    fn decide(
1646        &self,
1647        key: StepKey,
1648        step: &StepSpec,
1649        marks: &mut Marks,
1650    ) -> Result<Decision, StepError> {
1651        let remembered = step_lock(
1652            &self.engine.not_cached,
1653            NOT_CACHED,
1654            self.engine.lock_patience,
1655        )?
1656        .get(&key)
1657        .cloned();
1658        if self.runs_always(step) {
1659            let known = remembered.is_some() || self.record(&key)?.is_some();
1660            if let Some(first) = self.engine.first_always_result(key)? {
1661                return Ok(Decision::Replay(first));
1662            }
1663            marks.always = true;
1664            let reason = if step.untraced {
1665                RunReason::Untraced
1666            } else if !known {
1667                RunReason::NeverRun
1668            } else if self.cache_never {
1669                RunReason::TaskCacheNever
1670            } else if step.always {
1671                RunReason::Always
1672            } else {
1673                RunReason::RunNoCache
1674            };
1675            return Ok(Decision::Run(reason, None));
1676        }
1677        if let Some(run) = remembered {
1678            let checked = check(
1679                &run.observations,
1680                run.recorded_at_nanos,
1681                step.timestamps,
1682                &self.engine.states,
1683                self.engine.tracer,
1684            );
1685            return Ok(if checked.is_hit() {
1686                Decision::Replay(run.result)
1687            } else {
1688                Decision::Run(
1689                    RunReason::NotCached {
1690                        why: run.why,
1691                        differences: checked.differences,
1692                    },
1693                    Some(Baseline::new(&run.observations, run.recorded_at_nanos)),
1694                )
1695            });
1696        }
1697        let Some(record) = self.record(&key)? else {
1698            return Ok(Decision::Run(RunReason::NeverRun, None));
1699        };
1700        let checked_at_nanos = now_nanos();
1701        let checked = check(
1702            &record.observations,
1703            record.recorded_at_nanos,
1704            record.spec.timestamps,
1705            &self.engine.states,
1706            self.engine.tracer,
1707        );
1708        if let Some(why) = record.not_cached {
1709            // The record of a run of an earlier build whose result was not cached:
1710            // never a hit, so the step runs again, with that as the reason.
1711            return Ok(Decision::Run(
1712                RunReason::NotCached {
1713                    why,
1714                    differences: checked.differences,
1715                },
1716                Some(Baseline::new(
1717                    &record.observations,
1718                    record.recorded_at_nanos,
1719                )),
1720            ));
1721        }
1722        let machine = self.changed_machine(key, &record, marks)?;
1723        Ok(if checked.is_hit() && machine.is_empty() {
1724            Decision::Hit {
1725                record: Box::new(record),
1726                checked,
1727                checked_at_nanos,
1728            }
1729        } else {
1730            Decision::Run(
1731                RunReason::InputsChanged {
1732                    differences: checked.differences,
1733                    machine,
1734                },
1735                Some(Baseline::new(
1736                    &record.observations,
1737                    record.recorded_at_nanos,
1738                )),
1739            )
1740        })
1741    }
1742
1743    /// The values of the machine state that the record `record`, stored under
1744    /// `key`, names and that changed since it was made, which the machine query of
1745    /// the tracer reads for the record's working directory.
1746    ///
1747    /// A record that names no part compares nothing and queries nothing. Nor does a
1748    /// record whose machine state the build already compared, or whose step already
1749    /// ran in the build: each step key is compared at most once per build. A
1750    /// comparison adds the key to the build's compared machine states, which
1751    /// `marks` notes.
1752    fn changed_machine(
1753        &self,
1754        key: StepKey,
1755        record: &StepRecord,
1756        marks: &mut Marks,
1757    ) -> Result<Vec<MachineChange>, StepError> {
1758        let parts = MachinePart::parts(&record.spec.machine);
1759        if parts.is_empty()
1760            || !step_lock(
1761                &self.engine.machine_compared,
1762                MACHINE_COMPARED,
1763                self.engine.lock_patience,
1764            )?
1765            .insert(key)
1766        {
1767            return Ok(Vec::new());
1768        }
1769        marks.compared = true;
1770        let current = machine_record(&self.engine.tracer.machine_state(&record.spec.cwd));
1771        Ok(machine_changes(&parts, &record.machine, &current))
1772    }
1773
1774    /// The step-position record of the step at `position`, before this decision.
1775    fn stored_position(
1776        &self,
1777        txn: &Txn<'_>,
1778        position: u32,
1779    ) -> Result<Option<StepPosition>, StoreError> {
1780        match &self.identity {
1781            Some(identity) => {
1782                txn.get::<StepPosition>(&PositionKey {
1783                    task: identity.id.clone(),
1784                    position,
1785                })
1786            },
1787            None => Ok(None),
1788        }
1789    }
1790
1791    /// Explain why the step at `position`, whose key is `key` and whose
1792    /// specification is `spec`, runs for `reason`, with `baseline`, the recorded
1793    /// state the cache check compared; and return the self-inflicted inputs its
1794    /// position carries from the task's previous build.
1795    fn explain(
1796        &self,
1797        position: u32,
1798        key: StepKey,
1799        spec: &StepSpecRecord,
1800        reason: &RunReason,
1801        baseline: Option<&Baseline>,
1802    ) -> Result<(Explanation, Vec<PathBuf>), StoreError> {
1803        let txn = self.engine.store.read()?;
1804        let previous = self.stored_position(&txn, position)?;
1805        let context = InputContext {
1806            identity: self.identity.as_ref(),
1807            position,
1808            key,
1809            build: self.engine.build,
1810            baseline,
1811        };
1812        let reasons = match reason {
1813            RunReason::NeverRun => self.never_run(&txn, previous.as_ref(), key, spec)?,
1814            RunReason::Always => vec![Reason::Always],
1815            RunReason::TaskCacheNever => vec![Reason::TaskCacheNever],
1816            RunReason::RunNoCache => vec![Reason::RunNoCache],
1817            RunReason::Untraced => vec![Reason::Untraced],
1818            RunReason::InputsChanged {
1819                differences,
1820                machine,
1821            } => {
1822                let mut reasons = Vec::new();
1823                if !differences.is_empty() || machine.is_empty() {
1824                    reasons.push(Reason::InputsChanged {
1825                        inputs: changed_inputs(&txn, &context, differences)?,
1826                    });
1827                }
1828                if !machine.is_empty() {
1829                    reasons.push(Reason::MachineChanged {
1830                        changes: machine.clone(),
1831                    });
1832                }
1833                reasons
1834            },
1835            RunReason::NotCached { why, differences } => {
1836                vec![Reason::NotCached {
1837                    why: why.clone(),
1838                    inputs: changed_inputs(&txn, &context, differences)?,
1839                }]
1840            },
1841        };
1842        let carried = carried_from(previous.as_ref(), self.engine.build);
1843        let mut explanation = Explanation {
1844            reasons,
1845            repeated: Vec::new(),
1846        };
1847        explanation.repeated = explanation
1848            .self_inflicted()
1849            .into_iter()
1850            .filter(|path| carried.binary_search(path).is_ok())
1851            .collect();
1852        Ok((explanation, carried))
1853    }
1854
1855    /// The reasons of a step key with no record: what changed since the
1856    /// specification the task used at the same position last time, `previous`, or
1857    /// that the step never ran.
1858    fn never_run(
1859        &self,
1860        txn: &Txn<'_>,
1861        previous: Option<&StepPosition>,
1862        key: StepKey,
1863        spec: &StepSpecRecord,
1864    ) -> Result<Vec<Reason>, StoreError> {
1865        let Some(previous) = previous.filter(|previous| previous.step != key) else {
1866            return Ok(vec![Reason::NeverRun]);
1867        };
1868        let Some(old) = txn.get::<StepRecord>(&previous.step)? else {
1869            return Ok(vec![Reason::NeverRun]);
1870        };
1871        let old_task = match &self.identity {
1872            Some(identity) => txn.get::<TaskRecord>(&identity.id)?,
1873            None => None,
1874        };
1875        let reasons = spec_reasons(
1876            &old.spec,
1877            spec,
1878            old_task.as_ref(),
1879            self.identity.as_ref().map(|identity| &identity.parts),
1880        );
1881        Ok(if reasons.is_empty() {
1882            vec![Reason::NeverRun]
1883        } else {
1884            reasons
1885        })
1886    }
1887
1888    /// Note that the step `step` at `position`, whose key is `key`, was cached and
1889    /// returns `result`, and tell the run's step events; its position is stored,
1890    /// and its task becomes an owner of the record under `key`, when the run
1891    /// finishes, unless it already ran in this build with the same key, whose
1892    /// reasons it keeps and whose record its run made it an owner of.
1893    fn note_cached(
1894        &self,
1895        position: u32,
1896        key: StepKey,
1897        step: &StepSpec,
1898        result: &Result<StepOutcome, StepError>,
1899    ) -> Result<(), StepError> {
1900        let decision = StepDecision {
1901            position,
1902            command: step.command(),
1903            verdict: Verdict::Cached,
1904        };
1905        self.events.step_cached(&decision, result);
1906        cells::update(&self.decisions, |decisions| decisions.push(decision));
1907        let Some(identity) = &self.identity else {
1908            return Ok(());
1909        };
1910        let previous = self
1911            .engine
1912            .store
1913            .read()
1914            .and_then(|txn| self.stored_position(&txn, position))
1915            .map_err(|error| store_error(&error))?;
1916        if let Some(previous) = &previous
1917            && previous.build == self.engine.build
1918            && previous.step == key
1919            && matches!(previous.verdict, Verdict::Ran(_))
1920        {
1921            return Ok(());
1922        }
1923        let stored = StepPosition {
1924            step: key,
1925            build: self.engine.build,
1926            verdict: Verdict::Cached,
1927            carried: carried_from(previous.as_ref(), self.engine.build),
1928        };
1929        let cached = (
1930            PositionKey {
1931                task: identity.id.clone(),
1932                position,
1933            },
1934            stored,
1935        );
1936        cells::update(&self.cached_positions, |positions| positions.push(cached));
1937        Ok(())
1938    }
1939
1940    /// Note that the step `step` of `pending` ran, warn when it re-ran in
1941    /// consecutive builds for the same self-inflicted reason, and tell the run's
1942    /// step events that it starts, before its command starts. This comes only once
1943    /// kizz is about to record that the program is missing or not executable, or to
1944    /// ask the tracer to run the command; a step that fails before it has no
1945    /// decision.
1946    fn note_ran(
1947        &self,
1948        step: &StepSpec,
1949        pending: &Pending,
1950    ) -> Result<(), StepError> {
1951        let command = step.command();
1952        if !pending.explanation.repeated.is_empty() {
1953            self.engine.warn(RepeatedWarning {
1954                task: self.identity.as_ref().map(TaskIdentity::label),
1955                position: pending.position,
1956                command: command.clone(),
1957                paths: pending.explanation.repeated.clone(),
1958            })?;
1959        }
1960        let decision = StepDecision {
1961            position: pending.position,
1962            command,
1963            verdict: Verdict::Ran(pending.explanation.clone()),
1964        };
1965        self.events.step_started(&decision);
1966        cells::update(&self.decisions, |decisions| decisions.push(decision));
1967        Ok(())
1968    }
1969
1970    /// Return the result of the cache hit on `record`, stored under `key`, after
1971    /// storing the new metadata in `checked` when it has any, with the owners of the
1972    /// stored record. The task becomes an owner when [`TaskSteps::finish`] stores
1973    /// the step's position, and only if it is not one already.
1974    fn hit(
1975        &self,
1976        key: &StepKey,
1977        mut record: StepRecord,
1978        checked: Checked,
1979        checked_at_nanos: u64,
1980    ) -> Result<StepOutcome, StepError> {
1981        if checked.refresh {
1982            record.observations = checked.observations;
1983            record.recorded_at_nanos = checked_at_nanos;
1984            self.put(key, &mut record)?;
1985        }
1986        replay(record)
1987    }
1988
1989    /// Select traced or explicit untraced execution and invalidate unknown writes.
1990    fn run_command(
1991        &self,
1992        step: &StepSpec,
1993        request: &RunRequest,
1994    ) -> Result<RunResult, TraceError> {
1995        if step.untraced {
1996            let result =
1997                self.engine
1998                    .tracer
1999                    .run_untraced(request, self.engine.echo, &self.engine.cancel);
2000            // The command may have written any path, including on failure.
2001            self.engine.states.clear();
2002            result
2003        } else {
2004            self.engine
2005                .tracer
2006                .run(request, self.engine.echo, &self.engine.cancel)
2007        }
2008    }
2009
2010    /// Run `step` with the found program `program`; `checked` holds the locations
2011    /// the lookup checked, `lookup` the same locations with their outcomes when the
2012    /// engine writes a report, and `machine` the machine state the command starts
2013    /// with. When the engine writes a report, the request asks for the process
2014    /// tree, and the step's command is kept with its outcome, tree and lookup. A
2015    /// tracer failure is kept for the rest of the build under the step key.
2016    fn run(
2017        &self,
2018        step: &StepSpec,
2019        pending: &Pending,
2020        program: AbsolutePath,
2021        checked: Accesses,
2022        lookup: Observations,
2023        machine: MachineStateRecord,
2024    ) -> Result<StepOutcome, StepError> {
2025        let tree = self.engine.reports();
2026        let request = run_request(step, program.clone(), self.engine.live_output, tree);
2027        let ran_at = SystemTime::now();
2028        let started = Instant::now();
2029        let result = self.run_command(step, &request);
2030        let duration = started.elapsed();
2031        let lookup_checked = (!checked.is_empty()).then(|| checked_list(&checked));
2032        self.keep_run(
2033            step,
2034            pending,
2035            &request,
2036            &result,
2037            lookup_checked.as_deref(),
2038            lookup,
2039        );
2040        let mut accesses = checked;
2041        match result {
2042            Ok(result) => {
2043                let why = self.not_cached_reason(&result);
2044                accesses.merge(result.accesses);
2045                self.engine.states.forget_written(&accesses);
2046                let outcome = StepOutcome {
2047                    termination: result.termination,
2048                    output: result.output.clone(),
2049                    cached: false,
2050                };
2051                let finished = Finished {
2052                    program: Some(program),
2053                    accesses,
2054                    exit: step_exit(result.termination),
2055                    output: result.output,
2056                    duration,
2057                    ran_at,
2058                    failure: None,
2059                    first_reads: result.first_reads,
2060                    unknown_system_calls: result.unknown_system_calls.into_iter().collect(),
2061                    connections: stored_connections(&result.connections),
2062                    machine,
2063                };
2064                self.finish_run(step, pending, finished, why, Ok(outcome.clone()))?;
2065                Ok(outcome)
2066            },
2067            Err(error) if error.is_missing_program() => {
2068                if let Some(touched) = error.accesses() {
2069                    accesses.merge(touched.clone());
2070                }
2071                self.engine.states.forget_written(&accesses);
2072                let exit = if matches!(error, TraceError::ProgramNotFound { .. }) {
2073                    StepExit::ProgramNotFound
2074                } else {
2075                    StepExit::ProgramNotExecutable
2076                };
2077                let message = missing_message(&error, lookup_checked.as_deref());
2078                self.store(step, pending, Finished {
2079                    program: Some(program),
2080                    accesses,
2081                    exit,
2082                    output: CapturedOutput::empty(step.capture),
2083                    duration,
2084                    ran_at,
2085                    failure: Some(message.clone()),
2086                    first_reads: FirstReads::new(),
2087                    unknown_system_calls: Vec::new(),
2088                    connections: Vec::new(),
2089                    machine,
2090                })?;
2091                Err(StepError::new(message))
2092            },
2093            Err(error) if !error.is_tracer_failure() => {
2094                if let Some(touched) = error.accesses() {
2095                    accesses.merge(touched.clone());
2096                }
2097                self.engine.states.forget_written(&accesses);
2098                let message = error.to_string();
2099                let failure = StepError::new(&message);
2100                let finished = Finished {
2101                    program: Some(program),
2102                    accesses,
2103                    exit: StepExit::NotStarted,
2104                    output: CapturedOutput::empty(step.capture),
2105                    duration,
2106                    ran_at,
2107                    failure: Some(message.clone()),
2108                    first_reads: FirstReads::new(),
2109                    unknown_system_calls: Vec::new(),
2110                    connections: Vec::new(),
2111                    machine,
2112                };
2113                let why = NotCachedReason::StartFailed { message };
2114                self.finish_run(step, pending, finished, Some(why), Err(failure.clone()))?;
2115                Err(failure)
2116            },
2117            Err(error) => self.tracer_failed(pending.key, &error),
2118        }
2119    }
2120
2121    /// The result of the run of the step `key` that the tracer failed with
2122    /// `error`. A tracer failure leaves no record, and the engine cannot tell
2123    /// whether anything started, so the build keeps it under `key`: the step returns
2124    /// it again in a later pass, without a decision and without asking the tracer.
2125    fn tracer_failed(
2126        &self,
2127        key: StepKey,
2128        error: &TraceError,
2129    ) -> Result<StepOutcome, StepError> {
2130        let failure = StepError::new(error);
2131        self.engine.remember_tracer_failure(key, &failure)?;
2132        Err(failure)
2133    }
2134
2135    /// Keep the command of `step`, which ran as `request` and gave `result`, for
2136    /// the observation report, when the engine writes one: with how it ended, its
2137    /// process tree, which [`run_tree`] completes with everything that the run
2138    /// reports, or the tree of the tracer's error, and the lookup's observations
2139    /// `lookup`. A missing or non-executable program's message names the
2140    /// locations `checked`, as the step's failure does.
2141    fn keep_run(
2142        &self,
2143        step: &StepSpec,
2144        pending: &Pending,
2145        request: &RunRequest,
2146        result: &Result<RunResult, TraceError>,
2147        checked: Option<&str>,
2148        lookup: Observations,
2149    ) {
2150        self.keep(pending.key, || {
2151            let (outcome, tree) = match result {
2152                Ok(result) => {
2153                    (
2154                        CommandOutcome::from_termination(result.termination),
2155                        Some(run_tree(request, result)),
2156                    )
2157                },
2158                Err(error) => {
2159                    let outcome = match error {
2160                        TraceError::ProgramNotFound { .. } => {
2161                            CommandOutcome::NotFound(missing_message(error, checked))
2162                        },
2163                        TraceError::ProgramNotExecutable { .. } => {
2164                            CommandOutcome::NotExecutable(missing_message(error, checked))
2165                        },
2166                        TraceError::StartFailed { .. } => {
2167                            CommandOutcome::StartFailed(error.to_string())
2168                        },
2169                        TraceError::Tracer { .. } => CommandOutcome::Failed(error.to_string()),
2170                    };
2171                    (outcome, error.tree().cloned())
2172                },
2173            };
2174            ran_command(step, Some(request.program.clone()), outcome, tree, lookup)
2175        });
2176    }
2177
2178    /// Why the result `result` of a run is not cached, or `None` when it is.
2179    ///
2180    /// Every run that returns once cancellation has been requested is interrupted,
2181    /// however it ended: by a signal, or with an exit code that the command chose
2182    /// after it handled the interrupt. A run that the tracer reports as incompletely
2183    /// traced is not cached for that reason; otherwise a run that made system calls
2184    /// that the tracer does not know is not cached for them, unless the build caches
2185    /// such results.
2186    fn not_cached_reason(
2187        &self,
2188        result: &RunResult,
2189    ) -> Option<NotCachedReason> {
2190        if self.engine.cancel.is_cancelled() {
2191            return Some(match result.termination {
2192                Termination::Signaled(signal) => NotCachedReason::Interrupted { signal },
2193                Termination::Exited(code) => NotCachedReason::InterruptedExited { code },
2194            });
2195        }
2196        if let Termination::Signaled(signal) = result.termination {
2197            return Some(NotCachedReason::Signaled { signal });
2198        }
2199        if let Some(reason) = &result.incomplete {
2200            return Some(NotCachedReason::Incomplete {
2201                detail: reason.to_string(),
2202            });
2203        }
2204        (!result.unknown_system_calls.is_empty() && !self.engine.cache_unknown_system_calls).then(
2205            || {
2206                NotCachedReason::UnknownSystemCalls {
2207                    numbers: result.unknown_system_calls.iter().copied().collect(),
2208                }
2209            },
2210        )
2211    }
2212
2213    /// Record the state of every path `finished` touched, and store the record of
2214    /// `step`, whose result is `result`, with the owners of the record it replaces
2215    /// and its task.
2216    ///
2217    /// The result is not cached for the reason `why`, or, when there is none, when
2218    /// a file changed after the command first read it or ran it, as the comparison
2219    /// of the first-read metadata with the recorded states finds. Such a record is
2220    /// marked with the reason and replaces any older record of its key, so no older
2221    /// result is replayed, and the result is kept in memory for the rest of the
2222    /// build, with the states of the paths it touched. A run that made system calls
2223    /// that the tracer does not know, and a run that made connections, is kept for
2224    /// the build's warnings, with whether its result was cached.
2225    fn finish_run(
2226        &self,
2227        step: &StepSpec,
2228        pending: &Pending,
2229        mut finished: Finished,
2230        why: Option<NotCachedReason>,
2231        result: Result<StepOutcome, StepError>,
2232    ) -> Result<(), StepError> {
2233        let first_reads = mem::take(&mut finished.first_reads);
2234        let mut record = self.record_of(step, pending, finished);
2235        let why = why.or_else(|| {
2236            let files = changed_after_read(&record.observations, &first_reads);
2237            (!files.is_empty()).then_some(NotCachedReason::ChangedAfterRead { files })
2238        });
2239        if !record.unknown_system_calls.is_empty() {
2240            step_lock(
2241                &self.engine.unknown_calls,
2242                UNKNOWN_CALLS,
2243                self.engine.lock_patience,
2244            )?
2245            .push(UnknownCalls {
2246                key: pending.key,
2247                numbers: record.unknown_system_calls.clone(),
2248                cached: why.is_none(),
2249            });
2250        }
2251        if !step.network && !record.connections.is_empty() {
2252            step_lock(
2253                &self.engine.connections,
2254                CONNECTIONS,
2255                self.engine.lock_patience,
2256            )?
2257            .push(StepConnections {
2258                key: pending.key,
2259                connections: record.connections.clone(),
2260                cached: why.is_none(),
2261            });
2262        }
2263        let Some(why) = why else {
2264            return self.put_run(pending, &mut record);
2265        };
2266        record.not_cached = Some(why.clone());
2267        self.put_run(pending, &mut record)?;
2268        let result = result.map(|outcome| {
2269            StepOutcome {
2270                cached: true,
2271                ..outcome
2272            }
2273        });
2274        step_lock(
2275            &self.engine.not_cached,
2276            NOT_CACHED,
2277            self.engine.lock_patience,
2278        )?
2279        .insert(pending.key, NotCachedRun {
2280            why,
2281            untraced: step.untraced,
2282            observations: record.observations,
2283            recorded_at_nanos: record.recorded_at_nanos,
2284            result,
2285        });
2286        Ok(())
2287    }
2288
2289    /// Record the state of every path `finished` touched and store the record of
2290    /// `step`, a command that did not run, with the owners of the record it
2291    /// replaces and its task.
2292    fn store(
2293        &self,
2294        step: &StepSpec,
2295        pending: &Pending,
2296        finished: Finished,
2297    ) -> Result<(), StepError> {
2298        let mut record = self.record_of(step, pending, finished);
2299        self.put_run(pending, &mut record)
2300    }
2301
2302    /// The specification of `step`, whose occurrence number is `occurrence`, as its
2303    /// record holds it.
2304    fn spec_record(
2305        &self,
2306        step: &StepSpec,
2307        occurrence: u32,
2308    ) -> StepSpecRecord {
2309        StepSpecRecord {
2310            program_hash: ContentHash(*self.program.as_bytes()),
2311            cwd: step.cwd.as_path().to_path_buf(),
2312            argv: step.argv.clone(),
2313            env: step.env.clone(),
2314            stdin: step.stdin.clone(),
2315            capture: capture(step.capture),
2316            stream: step.stream,
2317            always: step.always,
2318            untraced: step.untraced,
2319            ignore: step.ignore.clone(),
2320            track: step.track.clone(),
2321            timestamps: step.timestamps,
2322            expect: step.expect.clone(),
2323            occurrence,
2324            machine: step.machine.clone(),
2325        }
2326    }
2327
2328    /// The record of `step`, which ended as `finished`, with the state of every path
2329    /// it touched, as a cached result until [`TaskSteps::finish_run`] marks it. Its
2330    /// owners are empty until [`TaskSteps::put_run`] stores it.
2331    fn record_of(
2332        &self,
2333        step: &StepSpec,
2334        pending: &Pending,
2335        finished: Finished,
2336    ) -> StepRecord {
2337        let recorded_at_nanos = now_nanos();
2338        let observed = observe(
2339            &finished.accesses,
2340            &pending.ignore,
2341            &pending.track,
2342            &self.engine.states,
2343            self.engine.tracer,
2344        );
2345        StepRecord {
2346            spec: self.spec_record(step, pending.occurrence),
2347            program: finished
2348                .program
2349                .map(|program| ProgramPath(program.into_path_buf())),
2350            observations: observed.observations,
2351            ignored: observed.ignored,
2352            exit: finished.exit,
2353            output: recorded_output(finished.output),
2354            duration_nanos: nanos(finished.duration),
2355            ran_at_nanos: epoch_nanos(finished.ran_at),
2356            reason: pending.reason.clone(),
2357            recorded_at_nanos,
2358            failure: finished.failure,
2359            not_cached: None,
2360            owners: BTreeSet::new(),
2361            unknown_system_calls: finished.unknown_system_calls,
2362            connections: finished.connections,
2363            machine: finished.machine,
2364        }
2365    }
2366
2367    /// Keep the command of `step`, whose key is `key` and whose bare program name
2368    /// cannot be looked up without `PATH`, as `error` says, for the observation
2369    /// report: a command that started no process, whose program was not found.
2370    fn keep_no_path(
2371        &self,
2372        key: StepKey,
2373        step: &StepSpec,
2374        error: &NoPathError,
2375    ) {
2376        self.keep(key, || {
2377            ran_command(
2378                step,
2379                None,
2380                CommandOutcome::NotFound(error.to_string()),
2381                None,
2382                Observations::new(),
2383            )
2384        });
2385    }
2386
2387    /// Look the program of `step`, whose first argument is `name`, up and run it,
2388    /// or record that it is missing or not executable.
2389    ///
2390    /// Right before it runs the command, or records that the program is missing,
2391    /// it queries the machine state that the command starts with, which the record
2392    /// keeps whether or not the step names any part of it; the build compares the
2393    /// state of this step key no more in this build, which `marks` notes. Only then
2394    /// is the step noted as ran ([`TaskSteps::note_ran`]); a failure before that
2395    /// point, of the lookup or of the lock of the compared machine states, is
2396    /// [`Attempt::NotStarted`]. The lookup cannot fail for a missing `PATH`, which
2397    /// [`TaskSteps::execute`] checked before the cache check.
2398    ///
2399    /// When the engine writes a report, each checked location's outcome is named
2400    /// through the tracer's error-name query, and a step whose program kizz does not
2401    /// find is kept as a command that started no process, with every checked
2402    /// location.
2403    fn look_up_and_run(
2404        &self,
2405        step: &StepSpec,
2406        name: &str,
2407        pending: &Pending,
2408        marks: &mut Marks,
2409    ) -> Attempt {
2410        let report = self.engine.reports();
2411        let tracer = self.engine.tracer;
2412        let searched = search_step_program(name, &step.env, &step.cwd, |errno| {
2413            if report {
2414                tracer.error_name(errno)
2415            } else {
2416                kizz_trace::unnamed_error(errno)
2417            }
2418        });
2419        let search = match searched {
2420            Ok(search) => search,
2421            Err(error) => {
2422                self.keep_no_path(pending.key, step, &error);
2423                return Attempt::NotStarted(StepError::new(error));
2424            },
2425        };
2426        let observed = if report {
2427            search.checked().clone()
2428        } else {
2429            Observations::new()
2430        };
2431        let lookup = search.into_lookup();
2432        match step_lock(
2433            &self.engine.machine_compared,
2434            MACHINE_COMPARED,
2435            self.engine.lock_patience,
2436        ) {
2437            Ok(mut compared) => {
2438                if compared.insert(pending.key) {
2439                    marks.compared = true;
2440                }
2441            },
2442            Err(error) => return Attempt::NotStarted(error),
2443        }
2444        let machine = machine_record(&self.engine.tracer.machine_state(step.cwd.as_path()));
2445        if let Err(error) = self.note_ran(step, pending) {
2446            return Attempt::NotStarted(error);
2447        }
2448        let exit = match lookup {
2449            ProgramLookup::Found { program, checked } => {
2450                return Attempt::Ran(self.run(step, pending, program, checked, observed, machine));
2451            },
2452            ProgramLookup::NotFound { .. } => StepExit::ProgramNotFound,
2453            ProgramLookup::NotExecutable { .. } => StepExit::ProgramNotExecutable,
2454        };
2455        let message = missing_program_message(name, &lookup);
2456        self.keep(pending.key, || {
2457            let (program, outcome) = match &lookup {
2458                ProgramLookup::NotExecutable { candidate, .. } => {
2459                    (
2460                        Some(candidate.clone()),
2461                        CommandOutcome::NotExecutable(message.clone()),
2462                    )
2463                },
2464                ProgramLookup::NotFound { .. } | ProgramLookup::Found { .. } => {
2465                    (None, CommandOutcome::NotFound(message.clone()))
2466                },
2467            };
2468            ran_command(step, program, outcome, None, observed)
2469        });
2470        let stored = self.store(step, pending, Finished {
2471            program: None,
2472            accesses: lookup.checked().clone(),
2473            exit,
2474            output: CapturedOutput::empty(step.capture),
2475            duration: Duration::ZERO,
2476            ran_at: SystemTime::now(),
2477            failure: Some(message.clone()),
2478            first_reads: FirstReads::new(),
2479            unknown_system_calls: Vec::new(),
2480            connections: Vec::new(),
2481            machine,
2482        });
2483        Attempt::Ran(stored.and(Err(StepError::new(message))))
2484    }
2485}
2486
2487impl StepExecutor for TaskSteps<'_> {
2488    /// Run `step`, as the module documentation lists: a step that fails before it
2489    /// is noted as ran has no decision, and takes back what it marked in the
2490    /// build's memories: the start of an `always` run and a compared machine state.
2491    fn execute(
2492        &self,
2493        step: &StepSpec,
2494    ) -> Result<StepOutcome, StepError> {
2495        let Some(name) = step.argv.first() else {
2496            return Err(StepError::new("the step has no program"));
2497        };
2498        let position =
2499            u32::try_from(cells::update(&self.keys, |keys| keys.len())).unwrap_or(u32::MAX);
2500        let (key, occurrence) = cells::update(&self.occurrences, |occurrences| {
2501            occurrences.next_key(self.program, step)
2502        })
2503        .map_err(StepError::new)?;
2504        cells::update(&self.keys, |keys| keys.push(key));
2505        let ignore = self.patterns(&step.ignore)?;
2506        let track = self.patterns(&step.track)?;
2507        if let Err(error) = check_path(name, &step.env) {
2508            self.keep_no_path(key, step, &error);
2509            return Err(StepError::new(error));
2510        }
2511        if let Some(failure) = self.engine.tracer_failure(key)? {
2512            return Err(failure);
2513        }
2514        let mut marks = Marks::default();
2515        let decided = self.decide(key, step, &mut marks);
2516        let (reason, baseline) = match decided {
2517            Ok(Decision::Run(reason, baseline)) => (reason, baseline),
2518            Ok(Decision::Hit {
2519                record,
2520                checked,
2521                checked_at_nanos,
2522            }) => {
2523                self.keep(key, || cached_command(step, &record));
2524                let result = self.hit(&key, *record, checked, checked_at_nanos);
2525                self.note_cached(position, key, step, &result)?;
2526                return result;
2527            },
2528            Ok(Decision::Replay(result)) => {
2529                self.keep(key, || self.replayed_command(key, step, &result));
2530                self.note_cached(position, key, step, &result)?;
2531                return result;
2532            },
2533            Err(error) => return Err(self.not_started(key, marks, error)),
2534        };
2535        let spec = self.spec_record(step, occurrence);
2536        let attempt = match self.explain(position, key, &spec, &reason, baseline.as_ref()) {
2537            Ok((explanation, carried)) => {
2538                let pending = Pending {
2539                    key,
2540                    occurrence,
2541                    reason,
2542                    ignore,
2543                    track,
2544                    position,
2545                    explanation,
2546                    carried,
2547                };
2548                self.look_up_and_run(step, name, &pending, &mut marks)
2549            },
2550            Err(error) => Attempt::NotStarted(store_error(&error)),
2551        };
2552        let result = match attempt {
2553            Attempt::NotStarted(error) => return Err(self.not_started(key, marks, error)),
2554            Attempt::Ran(result) => result,
2555        };
2556        if self.runs_always(step) {
2557            self.engine.finish_always(key, &result)?;
2558        }
2559        result
2560    }
2561}
2562
2563impl TaskSteps<'_> {
2564    /// The error of the step `key`, which failed with `error` before it was noted
2565    /// as ran, after taking back what it marked in the build's memories, as `marks`
2566    /// says; when that fails too, the error names both failures.
2567    fn not_started(
2568        &self,
2569        key: StepKey,
2570        marks: Marks,
2571        error: StepError,
2572    ) -> StepError {
2573        match self.engine.forget_marks(key, marks) {
2574            Ok(()) => error,
2575            Err(forgotten) => StepError::new(format_args!("{error}; {forgotten}")),
2576        }
2577    }
2578}
2579
2580/// Unit tests of the locks of the engine's shared state.
2581#[cfg(test)]
2582#[allow(
2583    clippy::disallowed_macros,
2584    clippy::disallowed_methods,
2585    reason = "test code: the tests assert and lock"
2586)]
2587mod tests {
2588    use std::{
2589        sync::Mutex,
2590        time::{Duration, Instant},
2591    };
2592
2593    use kizz_threads::LOCK_PATIENCE;
2594
2595    use super::{WARNINGS, lock, step_lock};
2596
2597    /// The short patience of the tests, in place of the engine's default,
2598    /// [`LOCK_PATIENCE`], so a lock that stays held fails at once.
2599    const TEST_PATIENCE: Duration = Duration::from_millis(50);
2600
2601    /// State that stays locked, here by the calling thread itself, where
2602    /// `Mutex::lock` may panic, is an error that names the state, for a reader and
2603    /// for a step, once the patience has passed; free state locks. The patience is
2604    /// the short one of the tests, which the engine's lock path takes as a
2605    /// parameter, so the two waits take a fraction of a second, not twice
2606    /// [`LOCK_PATIENCE`].
2607    #[test]
2608    fn state_that_stays_locked_is_an_error_of_the_reader_and_the_step() {
2609        let started = Instant::now();
2610        let state = Mutex::new(vec![1]);
2611        let held = lock(&state, WARNINGS, TEST_PATIENCE).unwrap();
2612        let read = lock(&state, WARNINGS, TEST_PATIENCE).unwrap_err();
2613        assert_eq!(read.what(), WARNINGS);
2614        assert!(read.waited() >= TEST_PATIENCE, "{read:?}");
2615        let step = step_lock(&state, WARNINGS, TEST_PATIENCE).unwrap_err();
2616        assert!(
2617            step.message
2618                .starts_with("could not lock the build's warnings for repeated reasons"),
2619            "{step}"
2620        );
2621        drop(held);
2622        assert_eq!(*step_lock(&state, WARNINGS, TEST_PATIENCE).unwrap(), [1]);
2623        assert!(
2624            started.elapsed() < LOCK_PATIENCE,
2625            "the test waited {:?}",
2626            started.elapsed()
2627        );
2628    }
2629}