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}