Skip to main content

kizz_core/
build.rs

1// Copyright (c) 2026 Sakura Industries LLC.
2//
3// SPDX-License-Identifier: AGPL-3.0-only
4
5//! Building the selected tasks in passes ("Order of execution", "Failure and
6//! interruption").
7//!
8//! [`build`] runs the selected tasks one at a time, in passes. The tasks start in
9//! the default order, which [`load`](crate::project::load) already gives them: a
10//! directory's `kizz.md` before those of its subdirectories, sibling directories in
11//! byte order of their names, and task blocks in file order. The learned order
12//! overrides it: a task whose stored [`LearnedOrder`] names producers among the
13//! selected tasks runs after them, and every other task keeps its default place
14//! ([`learned_order`]).
15//!
16//! Every pass tries every selected task, and a failed task does not stop the pass.
17//! Each task program runs again in every pass, and every `run()` goes through the
18//! engine's cache check, so a task whose recorded inputs changed runs those commands
19//! again, including a failed task whose looked-for paths have appeared, while a task
20//! whose inputs did not change is a cache hit, and a failed one fails again from the
21//! cache without running anything. A missing file is a dependency like any other,
22//! never a scheduling signal: nothing waits for a path to appear.
23//!
24//! A pass does work when a command runs in it or a task program changes a file in
25//! it through `fs.write` or `fs.write_json`; a write that leaves the file as it was
26//! is no change. After a pass that did work, another pass checks every selected
27//! task. The build ends when a pass does no work: it succeeds if no task failed in
28//! that pass, and otherwise it fails, listing each failed task with the paths it
29//! looked for and did not find. The pass limit is one more than the number of tasks
30//! ([`pass_limit`]); when the last pass it allows still does work, the build stops,
31//! naming the paths that keep changing and who writes them, and the files that task
32//! programs changed in it. A command marked
33//! `always` runs at most once per build, when a pass first reaches it, normally the
34//! first one, because the engine runs each `always` step key once per build; later
35//! passes reuse its result, and one first reached in a later pass, or with a new step
36//! key, runs once in that pass. Every command of a task marked `cache=never` runs
37//! the same way, because the engine runs it as if it were marked `always`; a task
38//! with a name and no targets is never selected, because selection goes by targets.
39//!
40//! When a task program ends, whether it succeeded or failed, each step it left
41//! unchecked, which exited with a non-zero code or was killed by a signal, had no
42//! `expect`, and whose result the program never checked, by reading its `rc` or
43//! `signal` or by encoding it, is in [`TaskResult::unchecked`], with its step key
44//! and whether the build ran a command under that key; a result from the cache
45//! counts like any other ("Exit codes and failure"). Only the unchecked steps that
46//! stand when the build settles warn, the final-state rule
47//! ([`BuildReport::unchecked`]): those of each task's latest run in the build,
48//! which in a settled build is its run in the final pass, because every pass tries
49//! every selected task. A task that runs again in a later pass replaces its
50//! earlier results, so a superseded unchecked step never warns, and a build that
51//! does not settle or is interrupted warns about none. With
52//! [`Engine::with_fail_unchecked`] (`kizz build --fail-unchecked`), a run whose
53//! program succeeded but left a step unchecked fails with
54//! [`TaskFailure::Unchecked`], which names every unchecked step; as for every
55//! failure, the final pass decides whether the build fails, and a program that
56//! failed keeps its own failure. Without the option, an unchecked step fails
57//! nothing.
58//!
59//! Once cancellation is requested, the build starts nothing new: no further task or
60//! command starts, the outcome is [`BuildOutcome::Interrupted`], and no learned
61//! order is stored.
62//!
63//! After every build that is not interrupted, kizz records, for each task that ran,
64//! the tasks whose outputs it consumed: the last writers of the paths its steps and
65//! its program read, checked, listed, or ran, including the paths written into a
66//! directory it listed, and the paths other task programs wrote in this build. A
67//! task program that changes a file is stored as the file's last writer when its run
68//! ends ([`Engine::program_wrote`]), so the order learned from it holds in a later
69//! build in which the program does not write the file.
70//! Each run of a task ends with [`TaskSteps::finish`], which stores the task record:
71//! the program hash and a summary of the run.
72//!
73//! The builder keeps the step keys under which the build ran a command in a field
74//! that only its own `&mut self` methods change, so no `RefCell` borrow, which
75//! would panic while the cell is borrowed, is needed ("Kizz never panics").
76
77use std::{
78    collections::{BTreeMap, BTreeSet, HashMap},
79    fs, io,
80    path::PathBuf,
81};
82
83use kizz_store::{
84    AccessBits, LastWriter, LearnedOrder, PathKey, PathState, Reason, StepKey, StepRecord, Store,
85    StoreError, TaskId, TaskLabel, Txn, Verdict, Writer, path_prefix,
86};
87use kizz_trace::{AbsolutePath, AccessKind, Accesses};
88
89use crate::{
90    engine::{Engine, NoStepEvents, StepEvents, TaskSteps},
91    explain::{StepDecision, TaskIdentity},
92    run::RunObservations,
93    runtime::{PrintSink, TaskFailure, TaskInfo, TaskProgram, UncheckedExit},
94    step::{StepError, StepExecutor, StepOutcome, StepSpec},
95};
96
97/// The message of a step that the build did not start because it was interrupted.
98pub const INTERRUPTED: &str = "the build was interrupted, so this command did not start";
99
100/// The number of passes a build may take: one more than the number of tasks.
101#[must_use]
102pub const fn pass_limit(tasks: usize) -> usize {
103    tasks.saturating_add(1)
104}
105
106/// The identity of the task `task`.
107#[must_use]
108pub fn task_id(task: &TaskInfo) -> TaskId {
109    TaskId {
110        file: task.file.as_path().to_path_buf(),
111        index: task.index,
112    }
113}
114
115/// The task `task` as explanations name it.
116#[must_use]
117pub fn task_label(task: &TaskInfo) -> TaskLabel {
118    TaskLabel {
119        task: task_id(task),
120        line: u32::try_from(task.line).unwrap_or(u32::MAX),
121        heading: task.heading.clone(),
122    }
123}
124
125/// Follows a build as it runs, for output.
126pub trait BuildEvents {
127    /// Pass `pass`, counting from 1, begins.
128    fn pass_started(
129        &self,
130        _pass: usize,
131    ) {
132    }
133
134    /// The run of a task in pass `pass` ended as `result` says.
135    fn task_finished(
136        &self,
137        _pass: usize,
138        _result: &TaskResult,
139    ) {
140    }
141}
142
143/// Follows nothing.
144#[derive(Debug, Clone, Copy, Default)]
145pub struct NoEvents;
146
147impl BuildEvents for NoEvents {}
148
149/// How one run of a task in a pass ended.
150#[derive(Debug, Clone, PartialEq, Eq)]
151pub struct TaskResult {
152    /// The task.
153    pub task: TaskInfo,
154    /// What the build decided about each step of the run, in order.
155    pub decisions: Vec<StepDecision>,
156    /// Whether the run succeeded, or why the task failed.
157    pub result: Result<(), TaskFailure>,
158    /// When the task failed, the paths it looked for and did not find, sorted.
159    pub missing: Vec<PathBuf>,
160    /// The files the task program changed through `fs.write` and `fs.write_json`
161    /// in the run, its modules' top-level code included, in the order it first
162    /// changed each, without repeats.
163    pub changed: Vec<AbsolutePath>,
164    /// The steps the run left unchecked, in the order they ran: each exited with a
165    /// non-zero code or was killed by a signal, had no `expect`, and the program
166    /// never read its result's `rc` or `signal` and never encoded the result.
167    pub unchecked: Vec<UncheckedStep>,
168}
169
170impl TaskResult {
171    /// Whether a command of the run ran, instead of coming from the cache.
172    #[must_use]
173    pub fn ran(&self) -> bool {
174        self.decisions
175            .iter()
176            .any(|decision| matches!(decision.verdict, Verdict::Ran(_)))
177    }
178
179    /// Whether the task program changed a file in the run.
180    #[must_use]
181    pub const fn changed_files(&self) -> bool {
182        !self.changed.is_empty()
183    }
184
185    /// Whether the run did work: a command ran, or the program changed a file.
186    #[must_use]
187    pub fn did_work(&self) -> bool {
188        self.ran() || self.changed_files()
189    }
190
191    /// Whether the task failed.
192    #[must_use]
193    pub const fn failed(&self) -> bool {
194        self.result.is_err()
195    }
196}
197
198/// A step that a task run left unchecked ("Exit codes and failure"): its task,
199/// its step key, the step itself, and whether the build ran a command under the
200/// key.
201#[derive(Debug, Clone, PartialEq, Eq)]
202pub struct UncheckedStep {
203    /// The task whose program left it unchecked.
204    pub task: TaskLabel,
205    /// The step key.
206    pub key: StepKey,
207    /// The step, with its command, how it ended, and its output.
208    pub exit: UncheckedExit,
209    /// Whether the build ran a command under the step key, in this run or in an
210    /// earlier run of the build; when it did not, every result under the key in
211    /// the build came from the cache of an earlier build.
212    pub ran: bool,
213}
214
215/// One pass of a build.
216#[derive(Debug, Clone, PartialEq, Eq)]
217pub struct Pass {
218    /// The number of the pass, counting from 1.
219    pub number: usize,
220    /// The run of each task the pass tried, in the order they ran.
221    pub tasks: Vec<TaskResult>,
222}
223
224impl Pass {
225    /// Whether a command ran during the pass.
226    #[must_use]
227    pub fn ran(&self) -> bool {
228        self.tasks.iter().any(TaskResult::ran)
229    }
230
231    /// Whether a task program changed a file during the pass.
232    #[must_use]
233    pub fn changed_files(&self) -> bool {
234        self.tasks.iter().any(TaskResult::changed_files)
235    }
236
237    /// Whether the pass did work: a command ran, or a task program changed a file.
238    #[must_use]
239    pub fn did_work(&self) -> bool {
240        self.ran() || self.changed_files()
241    }
242}
243
244/// A task that failed in the pass that ended the build.
245#[derive(Debug, Clone, PartialEq, Eq)]
246pub struct FailedTask {
247    /// The task.
248    pub task: TaskInfo,
249    /// Why it failed.
250    pub failure: TaskFailure,
251    /// The paths it looked for and did not find, sorted; any of them may be the
252    /// cause.
253    pub missing: Vec<PathBuf>,
254}
255
256/// An input that changed and made a step run in the last pass a build allows.
257#[derive(Debug, Clone, PartialEq, Eq)]
258pub struct ChangingInput {
259    /// The absolute path.
260    pub path: PathBuf,
261    /// The task whose step read it.
262    pub reader: TaskLabel,
263    /// The position of that step in its task's run, counting from zero.
264    pub position: u32,
265    /// Who last wrote it.
266    pub writer: Writer,
267}
268
269/// A file that a task program changed in the last pass a build allows.
270#[derive(Debug, Clone, PartialEq, Eq)]
271pub struct ProgramWrite {
272    /// The absolute path.
273    pub path: PathBuf,
274    /// The task whose program changed it.
275    pub writer: TaskLabel,
276}
277
278/// How a build ended.
279#[derive(Debug, Clone, PartialEq, Eq)]
280pub enum BuildOutcome {
281    /// A pass did no work, and no task failed in it.
282    Succeeded,
283    /// A pass did no work, and these tasks failed in it, in the order they ran.
284    Failed {
285        /// The failed tasks.
286        failures: Vec<FailedTask>,
287    },
288    /// The last pass the limit allows still did work.
289    NotSettled {
290        /// The pass limit.
291        limit: usize,
292        /// The changed inputs that made steps run in that pass, sorted by path.
293        changing: Vec<ChangingInput>,
294        /// The files that task programs changed in that pass, each with its task,
295        /// sorted by path, then by task.
296        written: Vec<ProgramWrite>,
297        /// The tasks that did work in that pass, in the order they ran.
298        worked: Vec<TaskInfo>,
299    },
300    /// Cancellation was requested, so the build started nothing new.
301    Interrupted,
302}
303
304/// What a build did.
305#[derive(Debug, Clone, PartialEq, Eq)]
306pub struct BuildReport {
307    /// The selected tasks, in the order every pass tried them.
308    pub order: Vec<TaskId>,
309    /// Every pass, in order, the one that ran nothing included.
310    pub passes: Vec<Pass>,
311    /// How the build ended.
312    pub outcome: BuildOutcome,
313}
314
315impl BuildReport {
316    /// The number of passes the build took to settle: the last pass that did work,
317    /// by running a command or by a task program changing a file, or 1 when no pass
318    /// did. The final pass, which did no work, only confirms that nothing changed,
319    /// so it adds to the count only when it is the only pass. A build that did not
320    /// settle or was interrupted reports every pass it tried.
321    #[must_use]
322    pub fn settled_in(&self) -> usize {
323        match self.outcome {
324            BuildOutcome::Succeeded | BuildOutcome::Failed { .. } => {
325                self.passes
326                    .iter()
327                    .rev()
328                    .find(|pass| pass.did_work())
329                    .map_or(1, |pass| pass.number)
330            },
331            BuildOutcome::NotSettled { .. } | BuildOutcome::Interrupted => self.passes.len(),
332        }
333    }
334
335    /// Whether the build succeeded.
336    #[must_use]
337    pub const fn succeeded(&self) -> bool {
338        matches!(self.outcome, BuildOutcome::Succeeded)
339    }
340
341    /// The unchecked steps that stand when the build settles, which warn (the
342    /// final-state rule, "Exit codes and failure"): those of each task's latest run
343    /// in the build. Every pass tries every selected task, so in a settled build
344    /// these are the runs of the final pass, in the order it ran the tasks and each
345    /// task its steps, each step once. A task that ran again in a later pass
346    /// replaced its earlier results, so an unchecked step of an earlier pass stands
347    /// only when the final pass still has it. A build that did not settle or was
348    /// interrupted has no settled state, so it has none.
349    #[must_use]
350    pub fn unchecked(&self) -> Vec<UncheckedStep> {
351        match self.outcome {
352            BuildOutcome::Succeeded | BuildOutcome::Failed { .. } => {
353                self.passes.last().map_or_default(|pass| {
354                    pass.tasks
355                        .iter()
356                        .flat_map(|result| result.unchecked.iter().cloned())
357                        .collect()
358                })
359            },
360            BuildOutcome::NotSettled { .. } | BuildOutcome::Interrupted => Vec::new(),
361        }
362    }
363}
364
365/// What one run of a task touched, for the learned order, and what it observed for
366/// the report of `kizz run --output`.
367#[derive(Debug, Clone, Default)]
368struct TaskTrace {
369    /// The key of each step of the run.
370    keys: Vec<StepKey>,
371    /// Every file access the program made: module loads and the `fs` and `env`
372    /// functions.
373    accesses: Accesses,
374    /// The commands of the run and the outcomes of its program's accesses, when the
375    /// engine writes a report ([`Engine::with_report`]), and otherwise `None`.
376    observed: Option<RunObservations>,
377}
378
379/// The step executor that starts nothing once the build is interrupted.
380struct CancelGuard<'s> {
381    /// The steps of the task run.
382    steps: &'s TaskSteps<'s>,
383    /// The engine, which knows whether cancellation was requested.
384    engine: &'s Engine<'s>,
385}
386
387impl StepExecutor for CancelGuard<'_> {
388    fn execute(
389        &self,
390        step: &StepSpec,
391    ) -> Result<StepOutcome, StepError> {
392        if self.engine.is_cancelled() {
393            return Err(StepError::new(INTERRUPTED));
394        }
395        self.steps.execute(step)
396    }
397}
398
399/// What every pass of one build shares.
400struct Builder<'b> {
401    /// The engine of the build.
402    engine: &'b Engine<'b>,
403    /// The caller environment, which `env.caller` and `env.inherit` read.
404    caller: &'b BTreeMap<String, String>,
405    /// Where the lines that task programs print go.
406    print: &'b dyn PrintSink,
407    /// Follows each step as it starts or comes from the cache: nothing in a build,
408    /// the live output of `kizz run`.
409    step_events: &'b dyn StepEvents,
410    /// The step keys under which the build ran a command so far, which only the
411    /// builder's own `&mut self` methods change, so it needs no `RefCell`.
412    ran: BTreeSet<StepKey>,
413}
414
415impl Builder<'_> {
416    /// Run the task `task` once: load its program, run it, and finish the run,
417    /// storing its program as the last writer of every file it changed.
418    ///
419    /// Each step the run left unchecked is in its result, with its step key and
420    /// whether the build ran a command under that key so far; when the engine
421    /// fails unchecked steps and the program succeeded, the run fails with every
422    /// unchecked step instead, before its task record is stored.
423    ///
424    /// For the whole load and run, modules included, the task's location is noted
425    /// through `kizz_threads::overflow`, so that an overflow of kizz's stack while the
426    /// program is evaluated names the task.
427    fn run_task(
428        &mut self,
429        task: &TaskInfo,
430    ) -> Result<(TaskResult, TaskTrace), StoreError> {
431        let _noted = kizz_threads::overflow::note_task(&crate::warning::location(
432            &task.relative_file,
433            task.line,
434            task.heading.as_deref(),
435        ));
436        let load = TaskProgram::load_noting(task.clone(), self.print, self.engine.reports());
437        let mut accesses = load.accesses;
438        let mut changes = load.changes;
439        let mut outcomes = load.outcomes;
440        let (result, decisions, keys, exits, commands) = match load.program {
441            Err(failure) => (Err(failure), Vec::new(), Vec::new(), Vec::new(), Vec::new()),
442            Ok(program) => {
443                let steps = self
444                    .engine
445                    .task_for(TaskIdentity::of(&program))
446                    .with_cache_never(task.cache_never)
447                    .with_events(self.step_events);
448                let executor = CancelGuard {
449                    steps: &steps,
450                    engine: self.engine,
451                };
452                let run = program.run(self.caller, &executor, self.print);
453                accesses.merge(run.accesses);
454                changes.merge(run.changes);
455                if let (Some(outcomes), Some(noted)) = (outcomes.as_mut(), run.outcomes) {
456                    outcomes.merge(noted);
457                }
458                let result = match run.result {
459                    Ok(()) if self.engine.fails_unchecked() && !run.unchecked.is_empty() => {
460                        Err(TaskFailure::Unchecked {
461                            exits: run.unchecked.clone(),
462                            invoked: self.engine.command_name(),
463                        })
464                    },
465                    other => other,
466                };
467                steps.finish(result.is_ok())?;
468                (
469                    result,
470                    steps.decisions(),
471                    steps.keys(),
472                    run.unchecked,
473                    steps.commands(),
474                )
475            },
476        };
477        let position_key = |position: u32| {
478            usize::try_from(position)
479                .ok()
480                .and_then(|position| keys.get(position))
481                .copied()
482        };
483        let ran = &mut self.ran;
484        for decision in &decisions {
485            if matches!(decision.verdict, Verdict::Ran(_))
486                && let Some(key) = position_key(decision.position)
487            {
488                ran.insert(key);
489            }
490        }
491        let unchecked: Vec<UncheckedStep> = exits
492            .into_iter()
493            .filter_map(|exit| {
494                let key = position_key(exit.position)?;
495                Some(UncheckedStep {
496                    task: task_label(task),
497                    key,
498                    ran: ran.contains(&key),
499                    exit,
500                })
501            })
502            .collect();
503        self.engine.program_wrote(&task_id(task), &changes)?;
504        let missing = if result.is_err() {
505            missing_paths(self.engine.store(), &keys, &accesses)?
506        } else {
507            Vec::new()
508        };
509        Ok((
510            TaskResult {
511                task: task.clone(),
512                decisions,
513                result,
514                missing,
515                changed: changes.paths(),
516                unchecked,
517            },
518            TaskTrace {
519                keys,
520                accesses,
521                observed: outcomes.map(|outcomes| {
522                    RunObservations {
523                        commands,
524                        task_program: outcomes
525                            .observations(|errno| self.engine.tracer().error_name(errno)),
526                    }
527                }),
528            },
529        ))
530    }
531
532    /// Run one pass, numbered `number`, over `tasks`, keeping what each run touched
533    /// in `traces`. Returns the pass and whether the build was interrupted.
534    fn pass(
535        &mut self,
536        number: usize,
537        tasks: &[TaskInfo],
538        traces: &mut BTreeMap<TaskId, TaskTrace>,
539        events: &dyn BuildEvents,
540    ) -> Result<(Pass, bool), StoreError> {
541        events.pass_started(number);
542        let mut results = Vec::new();
543        for task in tasks {
544            if self.engine.is_cancelled() {
545                break;
546            }
547            let (result, trace) = self.run_task(task)?;
548            traces.insert(task_id(task), trace);
549            events.task_finished(number, &result);
550            results.push(result);
551        }
552        let pass = Pass {
553            number,
554            tasks: results,
555        };
556        Ok((pass, self.engine.is_cancelled()))
557    }
558}
559
560/// Build `tasks`, the selected tasks in the default order, with `engine`, in
561/// passes until a pass does no work; `caller` is the caller environment, the lines
562/// task programs print go to `print`, and `events` follows the build.
563///
564/// # Errors
565///
566/// A [`StoreError`] when a record cannot be read or written.
567pub fn build(
568    engine: &Engine<'_>,
569    tasks: &[TaskInfo],
570    caller: &BTreeMap<String, String>,
571    print: &dyn PrintSink,
572    events: &dyn BuildEvents,
573) -> Result<BuildReport, StoreError> {
574    let store = engine.store();
575    let ordered: Vec<TaskInfo> = stored_order(store, tasks)?
576        .into_iter()
577        .filter_map(|index| tasks.get(index).cloned())
578        .collect();
579    let mut builder = Builder {
580        engine,
581        caller,
582        print,
583        step_events: &NoStepEvents,
584        ran: BTreeSet::new(),
585    };
586    let limit = pass_limit(ordered.len());
587    let mut passes: Vec<Pass> = Vec::new();
588    let mut traces = BTreeMap::new();
589    let outcome = loop {
590        let number = passes.len().saturating_add(1);
591        let (pass, interrupted) = builder.pass(number, &ordered, &mut traces, events)?;
592        let outcome = if interrupted {
593            Some(BuildOutcome::Interrupted)
594        } else if !pass.did_work() {
595            Some(settled(&pass))
596        } else if number >= limit {
597            Some(not_settled(&pass, limit))
598        } else {
599            None
600        };
601        passes.push(pass);
602        if let Some(outcome) = outcome {
603            break outcome;
604        }
605    };
606    if outcome != BuildOutcome::Interrupted {
607        learn(store, &traces)?;
608    }
609    Ok(BuildReport {
610        order: ordered.iter().map(task_id).collect(),
611        passes,
612        outcome,
613    })
614}
615
616/// Run `task` once with `engine`, as `kizz run` does: no other task and no further
617/// pass, even when its program changes a file; `caller` is the caller environment,
618/// the lines its program prints go to `print`, and `step_events` follows each step
619/// as it starts or comes from the cache.
620///
621/// The run stores what a build of that one task in one pass stores: the step
622/// records and positions, the task record, the task program as the last writer of
623/// each file it changed, and, unless the run was interrupted, the task's learned
624/// order. When the engine writes a report ([`Engine::with_report`]), it also
625/// returns the commands of the run and the outcomes of its program's accesses.
626///
627/// # Errors
628///
629/// A [`StoreError`] when a record cannot be read or written.
630pub(crate) fn run_task_once(
631    engine: &Engine<'_>,
632    task: &TaskInfo,
633    caller: &BTreeMap<String, String>,
634    print: &dyn PrintSink,
635    step_events: &dyn StepEvents,
636) -> Result<(TaskResult, Option<RunObservations>), StoreError> {
637    let mut builder = Builder {
638        engine,
639        caller,
640        print,
641        step_events,
642        ran: BTreeSet::new(),
643    };
644    let (result, mut trace) = builder.run_task(task)?;
645    let observed = trace.observed.take();
646    if !engine.is_cancelled() {
647        learn(engine.store(), &BTreeMap::from([(task_id(task), trace)]))?;
648    }
649    Ok((result, observed))
650}
651
652/// The outcome of a build whose pass `pass` did no work.
653fn settled(pass: &Pass) -> BuildOutcome {
654    let failures: Vec<FailedTask> = pass
655        .tasks
656        .iter()
657        .filter_map(|result| {
658            result.result.as_ref().err().map(|failure| {
659                FailedTask {
660                    task: result.task.clone(),
661                    failure: failure.clone(),
662                    missing: result.missing.clone(),
663                }
664            })
665        })
666        .collect();
667    if failures.is_empty() {
668        BuildOutcome::Succeeded
669    } else {
670        BuildOutcome::Failed { failures }
671    }
672}
673
674/// The outcome of a build whose pass `pass`, the last one `limit` allows, still did
675/// work.
676fn not_settled(
677    pass: &Pass,
678    limit: usize,
679) -> BuildOutcome {
680    let mut changing = Vec::new();
681    let mut written = Vec::new();
682    for result in &pass.tasks {
683        let reader = task_label(&result.task);
684        for decision in &result.decisions {
685            let Verdict::Ran(explanation) = &decision.verdict else {
686                continue;
687            };
688            for input in explanation.reasons.iter().flat_map(Reason::inputs) {
689                changing.push(ChangingInput {
690                    path: input.path.clone(),
691                    reader: reader.clone(),
692                    position: decision.position,
693                    writer: input.writer.clone(),
694                });
695            }
696        }
697        for path in &result.changed {
698            written.push(ProgramWrite {
699                path: path.as_path().to_path_buf(),
700                writer: reader.clone(),
701            });
702        }
703    }
704    changing.sort_by(|a, b| {
705        (&a.path, &a.reader.task, a.position).cmp(&(&b.path, &b.reader.task, b.position))
706    });
707    written.sort_by(|a, b| (&a.path, &a.writer.task).cmp(&(&b.path, &b.writer.task)));
708    written.dedup();
709    BuildOutcome::NotSettled {
710        limit,
711        changing,
712        written,
713        worked: pass
714            .tasks
715            .iter()
716            .filter(|result| result.did_work())
717            .map(|result| result.task.clone())
718            .collect(),
719    }
720}
721
722/// Whether the error `error` says that nothing exists at a path.
723fn is_missing(error: &io::Error) -> bool {
724    matches!(
725        error.kind(),
726        io::ErrorKind::NotFound | io::ErrorKind::NotADirectory
727    )
728}
729
730/// The paths a failed task run looked for and did not find: the paths its steps
731/// found absent, from the records of the step keys `keys`, and the paths its program
732/// checked through `accesses` that do not exist; never a path the task only wrote.
733///
734/// # Errors
735///
736/// A [`StoreError`] when a step record cannot be read.
737fn missing_paths(
738    store: &Store,
739    keys: &[StepKey],
740    accesses: &Accesses,
741) -> Result<Vec<PathBuf>, StoreError> {
742    let mut missing = BTreeSet::new();
743    let txn = store.read()?;
744    let keys: BTreeSet<&StepKey> = keys.iter().collect();
745    for key in keys {
746        let Some(record) = txn.get::<StepRecord>(key)? else {
747            continue;
748        };
749        for observation in record.observations {
750            if observation.state == PathState::Absent
751                && !observation.access.contains(AccessBits::WRITE)
752            {
753                missing.insert(observation.path);
754            }
755        }
756    }
757    for (path, kinds) in accesses {
758        if !kinds.contains(AccessKind::Write)
759            && fs::symlink_metadata(path.as_path()).is_err_and(|error| is_missing(&error))
760        {
761            missing.insert(path.as_path().to_path_buf());
762        }
763    }
764    Ok(missing.into_iter().collect())
765}
766
767/// The order of tasks whose producers, by index, are `producers`: `producers[i]`
768/// lists the tasks that must run before task `i`, and the indices are the default
769/// order. Each task, in the default order, runs once its producers have run, which
770/// are placed first, each in the same way and in their default order; every task
771/// without such an edge keeps its default place. A cycle of producers is broken
772/// where it closes: a producer already being placed is not waited for. Unknown
773/// indices and a task naming itself are ignored.
774#[must_use]
775pub fn learned_order(producers: &[Vec<usize>]) -> Vec<usize> {
776    /// Place `task` after its producers, unless it is placed or being placed.
777    fn place(
778        task: usize,
779        producers: &[Vec<usize>],
780        visiting: &mut BTreeSet<usize>,
781        order: &mut Vec<usize>,
782    ) {
783        if !visiting.insert(task) {
784            return;
785        }
786        let before: BTreeSet<usize> = producers
787            .get(task)
788            .map_or_default(|before| before.iter().copied().collect());
789        for producer in before {
790            if producer < producers.len() {
791                place(producer, producers, visiting, order);
792            }
793        }
794        order.push(task);
795    }
796
797    let mut visiting = BTreeSet::new();
798    let mut order = Vec::with_capacity(producers.len());
799    for task in 0..producers.len() {
800        place(task, producers, &mut visiting, &mut order);
801    }
802    order
803}
804
805/// The order of `tasks`, given in the default order, as indices: the learned order
806/// stored for them, which runs each task's selected producers first and keeps the
807/// default order elsewhere.
808///
809/// # Errors
810///
811/// A [`StoreError`] when a learned-order record cannot be read.
812fn stored_order(
813    store: &Store,
814    tasks: &[TaskInfo],
815) -> Result<Vec<usize>, StoreError> {
816    let ids: Vec<TaskId> = tasks.iter().map(task_id).collect();
817    let index: HashMap<&TaskId, usize> = ids.iter().enumerate().map(|(i, id)| (id, i)).collect();
818    let txn = store.read()?;
819    let mut producers = Vec::with_capacity(ids.len());
820    for id in &ids {
821        let before: Vec<usize> = txn.get::<LearnedOrder>(id)?.map_or_default(|order| {
822            order
823                .producers
824                .iter()
825                .filter_map(|producer| index.get(producer).copied())
826                .collect()
827        });
828        producers.push(before);
829    }
830    Ok(learned_order(&producers))
831}
832
833/// The paths a task run consumed, with whether it listed each one: every path its
834/// steps' records or its program accesses show it read, checked, listed, or ran.
835///
836/// # Errors
837///
838/// A [`StoreError`] when a step record cannot be read.
839fn consumed(
840    txn: &Txn<'_>,
841    trace: &TaskTrace,
842) -> Result<BTreeMap<PathBuf, bool>, StoreError> {
843    let mut paths: BTreeMap<PathBuf, bool> = BTreeMap::new();
844    let mut add = |path: PathBuf, listed: bool| {
845        let entry = paths.entry(path).or_insert(false);
846        *entry = *entry || listed;
847    };
848    let keys: BTreeSet<&StepKey> = trace.keys.iter().collect();
849    for key in keys {
850        let Some(record) = txn.get::<StepRecord>(key)? else {
851            continue;
852        };
853        for observation in record.observations {
854            if observation.access.0 & !AccessBits::WRITE != 0 {
855                let listed = observation.access.contains(AccessBits::LIST);
856                add(observation.path, listed);
857            }
858        }
859    }
860    for (path, kinds) in &trace.accesses {
861        if kinds.iter().any(|kind| kind != AccessKind::Write) {
862            add(
863                path.as_path().to_path_buf(),
864                kinds.contains(AccessKind::List),
865            );
866        }
867    }
868    Ok(paths)
869}
870
871/// Store the learned order of every task in `traces`: the tasks whose outputs its
872/// last run consumed, which are the last writers of the paths it consumed, the
873/// last writers of the paths written into a directory it listed, and the tasks whose
874/// programs wrote either in this build; never the task itself.
875///
876/// # Errors
877///
878/// A [`StoreError`] when a record cannot be read or written.
879fn learn(
880    store: &Store,
881    traces: &BTreeMap<TaskId, TaskTrace>,
882) -> Result<(), StoreError> {
883    let mut program_writes: BTreeMap<PathBuf, BTreeSet<TaskId>> = BTreeMap::new();
884    for (task, trace) in traces {
885        for (path, kinds) in &trace.accesses {
886            if kinds.contains(AccessKind::Write) {
887                program_writes
888                    .entry(path.as_path().to_path_buf())
889                    .or_default()
890                    .insert(task.clone());
891            }
892        }
893    }
894    let mut learned: Vec<(TaskId, BTreeSet<TaskId>)> = Vec::new();
895    {
896        let txn = store.read()?;
897        for (task, trace) in traces {
898            let mut producers = BTreeSet::new();
899            for (path, listed) in consumed(&txn, trace)? {
900                if let Some(writer) = txn.get::<LastWriter>(&PathKey(path.clone()))? {
901                    producers.insert(writer.task);
902                }
903                if let Some(writers) = program_writes.get(&path) {
904                    producers.extend(writers.iter().cloned());
905                }
906                if listed {
907                    for (key, writer) in txn.scan::<LastWriter>(&path_prefix(&path))? {
908                        if key.0.parent() == Some(path.as_path()) {
909                            producers.insert(writer.task);
910                        }
911                    }
912                    for (written, writers) in &program_writes {
913                        if written.parent() == Some(path.as_path()) {
914                            producers.extend(writers.iter().cloned());
915                        }
916                    }
917                }
918            }
919            producers.remove(task);
920            learned.push((task.clone(), producers));
921        }
922    }
923    let mut txn = store.write()?;
924    for (task, producers) in learned {
925        if producers.is_empty() {
926            txn.delete::<LearnedOrder>(&task)?;
927        } else {
928            txn.put(&task, &LearnedOrder { producers })?;
929        }
930    }
931    txn.commit()
932}
933
934/// Unit tests for the order of tasks and the pass limit.
935#[cfg(test)]
936#[allow(
937    clippy::disallowed_macros,
938    clippy::disallowed_methods,
939    reason = "test code: the tests assert and lock"
940)]
941mod tests {
942    use super::{learned_order, pass_limit};
943
944    /// Without producers, the tasks keep the default order.
945    #[test]
946    fn without_producers_the_default_order_holds() {
947        assert_eq!(learned_order(&[vec![], vec![], vec![]]), vec![0, 1, 2]);
948        assert_eq!(learned_order(&[]), Vec::<usize>::new());
949    }
950
951    /// Producers run before their consumers, and every other task keeps its
952    /// default place.
953    #[test]
954    fn producers_run_first_and_the_default_order_holds_elsewhere() {
955        // Task 0 consumes task 2's outputs; task 1 has no producers.
956        assert_eq!(learned_order(&[vec![2], vec![], vec![]]), vec![2, 0, 1]);
957        // A chain: 0 consumes 1, which consumes 3; 2 is free.
958        assert_eq!(learned_order(&[vec![1], vec![3], vec![], vec![]]), vec![
959            3, 1, 0, 2
960        ]);
961        // Several producers, all before the consumer, in their default order.
962        assert_eq!(learned_order(&[vec![3, 2], vec![], vec![], vec![]]), vec![
963            2, 3, 0, 1
964        ]);
965        // A producer that already ran keeps its place.
966        assert_eq!(learned_order(&[vec![], vec![0], vec![]]), vec![0, 1, 2]);
967    }
968
969    /// Unknown producers and a task naming itself are ignored, and a cycle is
970    /// broken where it closes.
971    #[test]
972    fn cycles_and_unknown_producers_are_broken_or_ignored() {
973        assert_eq!(learned_order(&[vec![0, 9], vec![]]), vec![0, 1]);
974        assert_eq!(learned_order(&[vec![1], vec![0]]), vec![1, 0]);
975        assert_eq!(learned_order(&[vec![2], vec![0], vec![1], vec![]]), vec![
976            1, 2, 0, 3
977        ]);
978    }
979
980    /// The pass limit is one more than the number of tasks.
981    #[test]
982    fn the_pass_limit_is_one_more_than_the_number_of_tasks() {
983        assert_eq!(pass_limit(0), 1);
984        assert_eq!(pass_limit(2), 3);
985        assert_eq!(pass_limit(usize::MAX), usize::MAX);
986    }
987}