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, ¤t))
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}