Skip to main content

kizz_trace/
lib.rs

1// Copyright (c) 2026 Sakura Industries LLC.
2//
3// SPDX-License-Identifier: AGPL-3.0-only
4
5//! The kizz tracer interface.
6//!
7//! The engine never starts a process itself and knows nothing about system calls.
8//! It describes one command in a [`RunRequest`]: the exact program, the argument
9//! vector, the exact environment, the absolute working directory, the `stdin`
10//! content, the capture mode, and whether output is echoed live. A [`Tracer`] runs
11//! the command and returns a [`RunResult`]: how the command ended, its raw captured
12//! output, every path its process tree touched with the combined [`AccessKinds`]
13//! for each path, the [`FirstReads`] of the run, the system calls of the run that
14//! the tracer does not know, the [`Connection`]s of the run, and a report when the
15//! trace is incomplete.
16//!
17//! The first reads hold, for each path whose first read or run of a regular file
18//! came before any write of that path in the run, the file's [`FileMetadata`] at
19//! that moment. The engine compares them with the final state of each path, so a
20//! file that changed after the command read it, whether the command rewrote it or
21//! something else changed it while the command ran, keeps the result out of the
22//! cache.
23//!
24//! A system call that the tracer does not know is not a reason for an incomplete
25//! trace: the tracer reports its number in [`RunResult::unknown_system_calls`], and
26//! the engine decides whether such a run is cached.
27//!
28//! A connection to an IPv4 or IPv6 address, or to a Unix socket by path or abstract
29//! name, is an input that the tracer cannot see: the tracer reports it in
30//! [`RunResult::connections`], and the engine records it, warns about it and still
31//! caches the result.
32//!
33//! A request can also ask, with [`RunRequest::tree`], for the [`ProcessTree`] of the
34//! run, which the result then holds besides the combined accesses: each traced
35//! process, a thread group whose threads fold into it, with its number, its process
36//! ID, the number of the process that created it, the programs it ran and the
37//! status it ended with. Each [`Program`] holds what the tracer attributes to it:
38//! its [`Observations`], each path with its access kinds and each kind with its
39//! [`Outcome`]s, `ok`, the name of an error such as `ENOENT`, or `unknown`, and its
40//! connections, unknown system calls and every reason that the trace is incomplete.
41//! The kinds of each path in the tree, combined over every program, are exactly
42//! that path's kinds in the combined accesses. The request flag is off by default,
43//! and builds never set it, so a build's tracer does no more work than before, and
44//! a failed start carries the tree in its [`TraceError`] only when it is set.
45//!
46//! A request runs in one of two ways. A command of a build runs in a process
47//! group of its own, with pipes or `/dev/null` as its standard streams, so its
48//! output is captured and a terminal's Ctrl-C reaches only kizz, which interrupts
49//! the command exactly once through [`Cancellation`]. A command that keeps the
50//! terminal, which a request asks for with [`RunRequest::terminal`], as
51//! `kizz execute` does, uses the standard input, output and error of the process
52//! that runs the tracer, and stays in that process's process group and session, so
53//! a terminal's input and signals reach it as they would without kizz; nothing of
54//! its output is captured. In both ways the command starts with an empty signal
55//! mask and the default action for `SIGPIPE`, and every other disposition is
56//! inherited, so a signal that kizz ignores stays ignored in the command.
57//!
58//! The caller can forward a termination [`Signal`] to a running request with
59//! [`Cancellation::forward`], which the tracer delivers once: to the command's first
60//! process while it lives, and afterwards to each live process of the tree. A
61//! signal sent to the whole process group of a command that keeps the terminal
62//! reaches it directly, and once more if the caller forwards it, since the caller
63//! cannot tell it from a signal sent to the caller alone.
64//!
65//! A tracer may not keep a traced process stopped: the Linux tracer resumes a
66//! process that a stop signal stopped, because with `PTRACE_TRACEME` it cannot learn
67//! when `SIGCONT` would end the stop. A terminal's Ctrl-Z therefore stops kizz
68//! itself, which keeps the default action of `SIGTSTP`, `SIGTTIN` and `SIGTTOU`,
69//! and each traced process then waits at its next traced system call or signal
70//! until kizz goes on; a stop signal sent to one traced process alone does not keep
71//! it stopped.
72//!
73//! Through the same interface, the engine reads what the standard library cannot:
74//! the extended attributes of a path, with [`Tracer::extended_attributes`], the
75//! [`MachineState`] that a command starts with, with [`Tracer::machine_state`], and
76//! the name of an error number, with [`Tracer::error_name`], whose default answer
77//! is `errno` and the number, [`unnamed_error`].
78//!
79//! Version 1 has one tracer, for Linux, in `kizz_trace_linux`; tests of the engine
80//! implement [`Tracer`] with a fake, which notes first reads with
81//! [`FirstReads::note_at`] as it reads or runs files, as the Linux tracer does,
82//! answers the attribute query from attributes that the test sets and the machine
83//! query with a state that the test scripts, and builds the tree of one process
84//! that a request asks for with [`ProcessTree::of_request`]. A fake whose run a
85//! test builds an observation report from builds the tree of each of its results
86//! with [`ProcessTree::of_run`] instead, which also puts the run's reason, unknown
87//! system calls and connections on the one program, as the Linux tracer puts them
88//! on the program that made them, so the report says what the run reported.
89//! Nothing in the engine changes when the tracer does.
90
91use std::{
92    collections::{BTreeMap, BTreeSet, btree_map},
93    ffi::OsString,
94    fmt, fs,
95    io::{self, Write},
96    net::SocketAddr,
97    ops::{BitOr, BitOrAssign},
98    os::unix::fs::MetadataExt as _,
99    path::{Path, PathBuf},
100    sync::{
101        Arc,
102        atomic::{AtomicBool, AtomicU8, Ordering},
103    },
104};
105
106/// One way a command touched a path.
107///
108/// A path touched in several ways has every one of them recorded, combined in
109/// [`AccessKinds`].
110#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
111pub enum AccessKind {
112    /// The path's content was read.
113    Read,
114    /// The path's existence or metadata was checked, including a lookup that found
115    /// nothing (`ENOENT`).
116    Probe,
117    /// The entries of a directory were read.
118    List,
119    /// The path was created, modified, renamed, removed, or had its metadata
120    /// changed.
121    Write,
122    /// The path was run as a program.
123    Exec,
124    /// The path's extended attributes were read or listed, including a read that
125    /// found no such attribute (`ENODATA`), a buffer too small for the answer
126    /// (`ERANGE`), or a file system without attributes (`EOPNOTSUPP`).
127    Xattr,
128}
129
130impl AccessKind {
131    /// Every access kind, in the order [`AccessKinds`] lists them.
132    pub const ALL: [Self; 6] = [
133        Self::Read,
134        Self::Probe,
135        Self::List,
136        Self::Write,
137        Self::Exec,
138        Self::Xattr,
139    ];
140
141    /// The bit that represents this kind in [`AccessKinds`].
142    const fn bit(self) -> u8 {
143        match self {
144            Self::Read => 0b0000_0001,
145            Self::Probe => 0b0000_0010,
146            Self::List => 0b0000_0100,
147            Self::Write => 0b0000_1000,
148            Self::Exec => 0b0001_0000,
149            Self::Xattr => 0b0010_0000,
150        }
151    }
152
153    /// The lowercase name of this kind, as explanations show it.
154    #[must_use]
155    pub const fn name(self) -> &'static str {
156        match self {
157            Self::Read => "read",
158            Self::Probe => "probe",
159            Self::List => "list",
160            Self::Write => "write",
161            Self::Exec => "exec",
162            Self::Xattr => "xattr",
163        }
164    }
165}
166
167impl fmt::Display for AccessKind {
168    fn fmt(
169        &self,
170        f: &mut fmt::Formatter<'_>,
171    ) -> fmt::Result {
172        f.write_str(self.name())
173    }
174}
175
176/// The combined access kinds of one path.
177///
178/// Combining is a set union: recording the same kind twice changes nothing, and
179/// the order in which kinds are recorded does not matter.
180#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Default)]
181pub struct AccessKinds {
182    /// One bit per [`AccessKind`], as [`AccessKind::bit`] assigns them.
183    bits: u8,
184}
185
186impl AccessKinds {
187    /// No access kinds.
188    pub const EMPTY: Self = Self { bits: 0 };
189
190    /// The set that holds only `kind`.
191    #[must_use]
192    pub const fn only(kind: AccessKind) -> Self {
193        Self { bits: kind.bit() }
194    }
195
196    /// Whether the set holds `kind`.
197    #[must_use]
198    pub const fn contains(
199        self,
200        kind: AccessKind,
201    ) -> bool {
202        self.bits & kind.bit() != 0
203    }
204
205    /// Whether the set holds no kind.
206    #[must_use]
207    pub const fn is_empty(self) -> bool {
208        self.bits == 0
209    }
210
211    /// Add `kind` to the set.
212    pub const fn insert(
213        &mut self,
214        kind: AccessKind,
215    ) {
216        self.bits |= kind.bit();
217    }
218
219    /// The set with `kind` added.
220    #[must_use]
221    pub const fn with(
222        self,
223        kind: AccessKind,
224    ) -> Self {
225        Self {
226            bits: self.bits | kind.bit(),
227        }
228    }
229
230    /// The union of both sets.
231    #[must_use]
232    pub const fn union(
233        self,
234        other: Self,
235    ) -> Self {
236        Self {
237            bits: self.bits | other.bits,
238        }
239    }
240
241    /// The kinds in the set, in the order of [`AccessKind::ALL`].
242    pub fn iter(self) -> impl Iterator<Item = AccessKind> {
243        AccessKind::ALL
244            .into_iter()
245            .filter(move |kind| self.contains(*kind))
246    }
247}
248
249impl From<AccessKind> for AccessKinds {
250    fn from(kind: AccessKind) -> Self {
251        Self::only(kind)
252    }
253}
254
255impl FromIterator<AccessKind> for AccessKinds {
256    fn from_iter<I: IntoIterator<Item = AccessKind>>(kinds: I) -> Self {
257        kinds.into_iter().fold(Self::EMPTY, Self::with)
258    }
259}
260
261impl BitOr for AccessKinds {
262    type Output = Self;
263
264    fn bitor(
265        self,
266        other: Self,
267    ) -> Self {
268        self.union(other)
269    }
270}
271
272impl BitOr<AccessKind> for AccessKinds {
273    type Output = Self;
274
275    fn bitor(
276        self,
277        kind: AccessKind,
278    ) -> Self {
279        self.with(kind)
280    }
281}
282
283impl BitOrAssign for AccessKinds {
284    fn bitor_assign(
285        &mut self,
286        other: Self,
287    ) {
288        *self = self.union(other);
289    }
290}
291
292impl BitOrAssign<AccessKind> for AccessKinds {
293    fn bitor_assign(
294        &mut self,
295        kind: AccessKind,
296    ) {
297        self.insert(kind);
298    }
299}
300
301impl fmt::Display for AccessKinds {
302    /// Lists the kinds joined with `+`, such as `read+probe`, or `none`.
303    fn fmt(
304        &self,
305        f: &mut fmt::Formatter<'_>,
306    ) -> fmt::Result {
307        if self.is_empty() {
308            return f.write_str("none");
309        }
310        for (position, kind) in self.iter().enumerate() {
311            if position != 0 {
312                f.write_str("+")?;
313            }
314            f.write_str(kind.name())?;
315        }
316        Ok(())
317    }
318}
319
320/// The error for a path that must be absolute but is not.
321#[derive(Debug, Clone, PartialEq, Eq, thiserror::Error)]
322#[error("path is not absolute: {}", .path.display())]
323pub struct NotAbsoluteError {
324    /// The path that was given.
325    pub path: PathBuf,
326}
327
328/// An absolute path, normalized as the tracer reports touched paths.
329///
330/// Normalizing removes `.` components, repeated separators, and a trailing
331/// separator. It keeps `..` components, because collapsing them is wrong when an
332/// earlier component is a symbolic link. The path is never resolved against the
333/// file system.
334#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
335pub struct AbsolutePath {
336    /// The normalized absolute path.
337    path: PathBuf,
338}
339
340impl AbsolutePath {
341    /// Normalize an absolute path.
342    ///
343    /// # Errors
344    ///
345    /// Returns [`NotAbsoluteError`] when `path` is relative.
346    pub fn new(path: impl AsRef<Path>) -> Result<Self, NotAbsoluteError> {
347        let path = path.as_ref();
348        if path.is_absolute() {
349            Ok(Self {
350                path: path.components().collect(),
351            })
352        } else {
353            Err(NotAbsoluteError {
354                path: path.to_path_buf(),
355            })
356        }
357    }
358
359    /// Resolve `path` against this path, as a relative path resolves against a
360    /// working directory or a directory descriptor, and normalize the result.
361    ///
362    /// An absolute `path` replaces this path.
363    #[must_use]
364    pub fn join(
365        &self,
366        path: impl AsRef<Path>,
367    ) -> Self {
368        Self {
369            path: self.path.join(path).components().collect(),
370        }
371    }
372
373    /// The path as a [`Path`].
374    #[must_use]
375    pub fn as_path(&self) -> &Path {
376        &self.path
377    }
378
379    /// The path as a [`PathBuf`].
380    #[must_use]
381    pub fn into_path_buf(self) -> PathBuf {
382        self.path
383    }
384}
385
386impl AsRef<Path> for AbsolutePath {
387    fn as_ref(&self) -> &Path {
388        &self.path
389    }
390}
391
392impl TryFrom<PathBuf> for AbsolutePath {
393    type Error = NotAbsoluteError;
394
395    fn try_from(path: PathBuf) -> Result<Self, Self::Error> {
396        Self::new(path)
397    }
398}
399
400impl fmt::Display for AbsolutePath {
401    fn fmt(
402        &self,
403        f: &mut fmt::Formatter<'_>,
404    ) -> fmt::Result {
405        self.path.display().fmt(f)
406    }
407}
408
409/// Every path a command's process tree touched, each with its combined access
410/// kinds, in sorted path order.
411#[derive(Debug, Clone, PartialEq, Eq, Default)]
412pub struct Accesses {
413    /// The combined access kinds of each touched path.
414    paths: BTreeMap<AbsolutePath, AccessKinds>,
415}
416
417impl Accesses {
418    /// No accesses.
419    #[must_use]
420    pub fn new() -> Self {
421        Self::default()
422    }
423
424    /// Record one access, combining it with earlier accesses to the same path.
425    pub fn record(
426        &mut self,
427        path: AbsolutePath,
428        kind: AccessKind,
429    ) {
430        self.record_kinds(path, AccessKinds::only(kind));
431    }
432
433    /// Record several kinds of access to one path, combining them with earlier
434    /// accesses to the same path.
435    pub fn record_kinds(
436        &mut self,
437        path: AbsolutePath,
438        kinds: AccessKinds,
439    ) {
440        *self.paths.entry(path).or_default() |= kinds;
441    }
442
443    /// Combine every access of `other` into this set.
444    pub fn merge(
445        &mut self,
446        other: Self,
447    ) {
448        for (path, kinds) in other.paths {
449            self.record_kinds(path, kinds);
450        }
451    }
452
453    /// The combined access kinds of `path`, if it was touched.
454    #[must_use]
455    pub fn get(
456        &self,
457        path: &AbsolutePath,
458    ) -> Option<AccessKinds> {
459        self.paths.get(path).copied()
460    }
461
462    /// The number of touched paths.
463    #[must_use]
464    pub fn len(&self) -> usize {
465        self.paths.len()
466    }
467
468    /// Whether no path was touched.
469    #[must_use]
470    pub fn is_empty(&self) -> bool {
471        self.paths.is_empty()
472    }
473
474    /// The touched paths with their combined access kinds, in sorted path order.
475    pub fn iter(&self) -> btree_map::Iter<'_, AbsolutePath, AccessKinds> {
476        self.paths.iter()
477    }
478}
479
480impl<'a> IntoIterator for &'a Accesses {
481    type IntoIter = btree_map::Iter<'a, AbsolutePath, AccessKinds>;
482    type Item = (&'a AbsolutePath, &'a AccessKinds);
483
484    fn into_iter(self) -> Self::IntoIter {
485        self.paths.iter()
486    }
487}
488
489impl IntoIterator for Accesses {
490    type IntoIter = btree_map::IntoIter<AbsolutePath, AccessKinds>;
491    type Item = (AbsolutePath, AccessKinds);
492
493    fn into_iter(self) -> Self::IntoIter {
494        self.paths.into_iter()
495    }
496}
497
498impl FromIterator<(AbsolutePath, AccessKind)> for Accesses {
499    fn from_iter<I: IntoIterator<Item = (AbsolutePath, AccessKind)>>(accesses: I) -> Self {
500        let mut combined = Self::new();
501        for (path, kind) in accesses {
502            combined.record(path, kind);
503        }
504        combined
505    }
506}
507
508/// Nanoseconds in a second.
509const NANOS_PER_SECOND: i64 = 1_000_000_000;
510
511/// A time in nanoseconds since the Unix epoch from its seconds and nanoseconds.
512const fn nanos(
513    seconds: i64,
514    nanoseconds: i64,
515) -> i64 {
516    seconds
517        .saturating_mul(NANOS_PER_SECOND)
518        .saturating_add(nanoseconds)
519}
520
521/// The metadata of a regular file at one moment, as a tracer notes it when a
522/// command first reads or runs the file.
523///
524/// It holds what a change to the file changes: the device and inode that identify
525/// it, its size, its modification and change times, its mode, and its owner.
526#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
527pub struct FileMetadata {
528    /// The device that holds the file.
529    pub device: u64,
530    /// The file's inode number on its device.
531    pub inode: u64,
532    /// The size in bytes.
533    pub size: u64,
534    /// The modification time, in nanoseconds since the Unix epoch.
535    pub mtime_nanos: i64,
536    /// The change time, in nanoseconds since the Unix epoch.
537    pub ctime_nanos: i64,
538    /// The mode: the file type and the permission bits.
539    pub mode: u32,
540    /// The user number of the owner.
541    pub uid: u32,
542    /// The group number of the owner.
543    pub gid: u32,
544}
545
546impl FileMetadata {
547    /// The metadata that `metadata` describes, or `None` when it does not describe
548    /// a regular file.
549    #[must_use]
550    pub fn of(metadata: &fs::Metadata) -> Option<Self> {
551        metadata.file_type().is_file().then(|| {
552            Self {
553                device: metadata.dev(),
554                inode: metadata.ino(),
555                size: metadata.size(),
556                mtime_nanos: nanos(metadata.mtime(), metadata.mtime_nsec()),
557                ctime_nanos: nanos(metadata.ctime(), metadata.ctime_nsec()),
558                mode: metadata.mode(),
559                uid: metadata.uid(),
560                gid: metadata.gid(),
561            }
562        })
563    }
564
565    /// The metadata of the regular file at `path` now, following symbolic links, or
566    /// `None` when `path` names no regular file or its metadata cannot be read.
567    #[must_use]
568    pub fn at(path: &Path) -> Option<Self> {
569        fs::metadata(path).ok().as_ref().and_then(Self::of)
570    }
571}
572
573/// The first reads of a run: for each path whose first read or run of a regular
574/// file came before any write of that path in the run, the file's
575/// [`FileMetadata`] at that moment, in sorted path order.
576///
577/// A tracer notes a file when the command opens it for reading or runs it, and the
578/// kernel's loads of interpreters and loaders count as runs. It notes nothing for
579/// a path that the command wrote earlier in the run, for a path it already noted,
580/// and for a call that created or truncated the file, which writes it first.
581#[derive(Debug, Clone, PartialEq, Eq, Default)]
582pub struct FirstReads {
583    /// The first-read metadata of each noted path.
584    files: BTreeMap<AbsolutePath, FileMetadata>,
585}
586
587impl FirstReads {
588    /// No first reads.
589    #[must_use]
590    pub fn new() -> Self {
591        Self::default()
592    }
593
594    /// Whether a read or run of `path` now would be its first read: the path has
595    /// no note yet, and `accesses`, every access recorded earlier in the run, shows
596    /// no write of it.
597    #[must_use]
598    pub fn is_first(
599        &self,
600        path: &AbsolutePath,
601        accesses: &Accesses,
602    ) -> bool {
603        !self.files.contains_key(path)
604            && !accesses
605                .get(path)
606                .is_some_and(|kinds| kinds.contains(AccessKind::Write))
607    }
608
609    /// Note `metadata` as the first-read metadata of `path`, which the command is
610    /// reading or running now, when that is its first read by
611    /// [`FirstReads::is_first`]; return whether it was noted.
612    pub fn note(
613        &mut self,
614        path: &AbsolutePath,
615        metadata: FileMetadata,
616        accesses: &Accesses,
617    ) -> bool {
618        if !self.is_first(path, accesses) {
619            return false;
620        }
621        self.files.insert(path.clone(), metadata);
622        true
623    }
624
625    /// Note the metadata of the regular file at `path`, read now with
626    /// [`FileMetadata::at`], under the rules of [`FirstReads::note`]; nothing is
627    /// noted when `path` names no regular file. Return whether it was noted.
628    ///
629    /// A tracer calls it when the command reads or runs `path`, before it records
630    /// that access in `accesses`.
631    pub fn note_at(
632        &mut self,
633        path: &AbsolutePath,
634        accesses: &Accesses,
635    ) -> bool {
636        if !self.is_first(path, accesses) {
637            return false;
638        }
639        FileMetadata::at(path.as_path()).is_some_and(|metadata| self.note(path, metadata, accesses))
640    }
641
642    /// The first-read metadata of `path`, if it was noted.
643    #[must_use]
644    pub fn get(
645        &self,
646        path: &AbsolutePath,
647    ) -> Option<&FileMetadata> {
648        self.files.get(path)
649    }
650
651    /// The number of noted paths.
652    #[must_use]
653    pub fn len(&self) -> usize {
654        self.files.len()
655    }
656
657    /// Whether no path was noted.
658    #[must_use]
659    pub fn is_empty(&self) -> bool {
660        self.files.is_empty()
661    }
662
663    /// The noted paths with their first-read metadata, in sorted path order.
664    pub fn iter(&self) -> btree_map::Iter<'_, AbsolutePath, FileMetadata> {
665        self.files.iter()
666    }
667}
668
669impl<'a> IntoIterator for &'a FirstReads {
670    type IntoIter = btree_map::Iter<'a, AbsolutePath, FileMetadata>;
671    type Item = (&'a AbsolutePath, &'a FileMetadata);
672
673    fn into_iter(self) -> Self::IntoIter {
674        self.files.iter()
675    }
676}
677
678/// How a command's standard output and standard error are captured.
679///
680/// Output is always captured for a request that does not keep the terminal; the
681/// mode only decides how. A request that keeps the terminal
682/// ([`RunRequest::terminal`]) captures nothing, and its output is only the empty
683/// output in the shape of the mode.
684#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Default)]
685pub enum CaptureMode {
686    /// Standard output and standard error are captured separately.
687    #[default]
688    Split,
689    /// Both streams go through one pipe, so their order is exact.
690    Merged,
691}
692
693/// One command for a [`Tracer`] to run.
694///
695/// The request is exact: the tracer adds nothing to it and looks nothing up.
696#[derive(Debug, Clone, PartialEq, Eq)]
697pub struct RunRequest {
698    /// The exact path of the program to run. The engine has already resolved a
699    /// bare program name through the task's `PATH`.
700    pub program: AbsolutePath,
701    /// The argument vector the program receives, starting with its `argv[0]`.
702    pub args: Vec<OsString>,
703    /// The exact environment of the process; nothing else is inherited.
704    pub env: BTreeMap<OsString, OsString>,
705    /// The absolute working directory of the process.
706    pub cwd: AbsolutePath,
707    /// The content written to standard input, or `None` to connect `/dev/null`;
708    /// a request that keeps the terminal ([`RunRequest::terminal`]) connects
709    /// neither, and its command reads the standard input of the process that runs
710    /// the tracer.
711    pub stdin: Option<Vec<u8>>,
712    /// How standard output and standard error are captured.
713    pub capture: CaptureMode,
714    /// Whether output is also echoed live, through the [`EchoSink`] given to
715    /// [`Tracer::run`], while it is captured.
716    pub echo: bool,
717    /// Whether the result also holds the [`ProcessTree`] of the run, and a failed
718    /// start the tree of its one process. Off unless set: builds never set it, so the
719    /// tracer does not read the arguments of `exec` calls or keep each program's
720    /// observations for them.
721    pub tree: bool,
722    /// Whether the command keeps the terminal: it uses the standard input, output
723    /// and error of the process that runs the tracer, and stays in that process's
724    /// process group and session, so a terminal's input and signals reach it as they
725    /// would without kizz. Nothing is captured or echoed, the result's output is
726    /// empty, and [`RunRequest::stdin`], [`RunRequest::capture`] and
727    /// [`RunRequest::echo`] mean nothing: the output stays in the empty shape of the
728    /// capture mode. Off unless set: builds never set it, so a command of a build
729    /// runs in a process group of its own, with pipes or `/dev/null` as its
730    /// standard streams, and a terminal's Ctrl-C reaches only kizz.
731    pub terminal: bool,
732}
733
734/// The stream a chunk of live output came from.
735#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
736pub enum OutputStream {
737    /// Standard output, with [`CaptureMode::Split`].
738    Stdout,
739    /// Standard error, with [`CaptureMode::Split`].
740    Stderr,
741    /// The one interleaved stream of [`CaptureMode::Merged`].
742    Merged,
743}
744
745/// Where live output goes when a request asks for echo.
746///
747/// The tracer calls [`EchoSink::echo`] with each chunk as it arrives, in order,
748/// and only when [`RunRequest::echo`] is set. Tests observe echo by implementing
749/// this trait.
750pub trait EchoSink: Send + Sync {
751    /// Echo one chunk of output.
752    ///
753    /// # Errors
754    ///
755    /// Returns the error of the underlying write. A failed echo never fails the
756    /// run, and the captured output stays complete.
757    fn echo(
758        &self,
759        stream: OutputStream,
760        bytes: &[u8],
761    ) -> io::Result<()>;
762}
763
764/// Echoes live output to the terminal: standard error to standard error, and
765/// everything else to standard output.
766///
767/// It writes with `Write::write_all` and `Write::flush` on the locked stream, which
768/// return the error of a write that fails, such as one to a closed pipe, where the
769/// `print!` macros would panic ("Kizz never panics"); the tracer drops that error,
770/// so the run goes on and its captured output stays complete.
771#[derive(Debug, Clone, Copy, Default)]
772pub struct StdioEcho;
773
774impl EchoSink for StdioEcho {
775    fn echo(
776        &self,
777        stream: OutputStream,
778        bytes: &[u8],
779    ) -> io::Result<()> {
780        match stream {
781            OutputStream::Stderr => {
782                let mut stderr = io::stderr().lock();
783                stderr.write_all(bytes)?;
784                stderr.flush()
785            },
786            OutputStream::Stdout | OutputStream::Merged => {
787                let mut stdout = io::stdout().lock();
788                stdout.write_all(bytes)?;
789                stdout.flush()
790            },
791        }
792    }
793}
794
795/// A termination signal that the caller can forward to a running request, with
796/// [`Cancellation::forward`].
797#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
798pub enum Signal {
799    /// The hangup signal, `SIGHUP`.
800    Hangup,
801    /// The termination signal, `SIGTERM`.
802    Terminate,
803}
804
805impl Signal {
806    /// Every signal that can be forwarded, in the order the tracer delivers those
807    /// that are pending together.
808    pub const ALL: [Self; 2] = [Self::Hangup, Self::Terminate];
809
810    /// The bit of the signal in the pending set of a [`Cancellation`].
811    const fn bit(self) -> u8 {
812        match self {
813            Self::Hangup => 0b01,
814            Self::Terminate => 0b10,
815        }
816    }
817}
818
819impl fmt::Display for Signal {
820    /// The signal's name, `SIGHUP` or `SIGTERM`.
821    fn fmt(
822        &self,
823        f: &mut fmt::Formatter<'_>,
824    ) -> fmt::Result {
825        f.write_str(match self {
826            Self::Hangup => "SIGHUP",
827            Self::Terminate => "SIGTERM",
828        })
829    }
830}
831
832/// A shared handle that cancels a running request, or forwards signals to it.
833///
834/// Clones share the handle, so the engine keeps one clone and hands another to the
835/// tracer. When the flag is set, the tracer interrupts the request's process tree,
836/// kills whatever remains of it after a grace period, and returns its result once
837/// the whole tree has exited. The result reports how the command ended: by a
838/// signal, or with an exit code that the command chose after it handled the
839/// interrupt.
840///
841/// The caller can also forward a [`Signal`] with [`Cancellation::forward`], as
842/// `kizz execute` forwards the `SIGTERM` and `SIGHUP` that kizz receives. A tracer
843/// takes each forwarded signal with [`Cancellation::take_forwarded`] while the
844/// request runs, and delivers it once: to the command's first process while that
845/// process lives, and afterwards to each live process of the tree. A signal that
846/// is forwarded again before the tracer takes it is delivered once, as a pending
847/// signal of the operating system is, and one forwarded while no request runs
848/// waits for the next request that holds a clone. Once the request is cancelled,
849/// the tracer forwards nothing more. Builds never forward a signal.
850///
851/// A signal sent to the whole process group of a command that keeps the terminal
852/// ([`RunRequest::terminal`]) reaches the command directly, and once more when the
853/// caller, which received it too, forwards it: neither the caller nor the tracer can
854/// tell such a signal from one sent to the caller alone.
855///
856/// The handle uses only atomic operations, so the caller can forward a signal
857/// from anywhere, a signal handler included.
858#[derive(Debug, Clone, Default)]
859pub struct Cancellation {
860    /// Whether cancellation was requested.
861    cancelled: Arc<AtomicBool>,
862    /// The forwarded signals that the tracer has not taken yet, one bit for each
863    /// [`Signal`], as `Signal::bit` assigns them.
864    forwarded: Arc<AtomicU8>,
865}
866
867impl Cancellation {
868    /// A flag that is not set, with no signal forwarded.
869    #[must_use]
870    pub fn new() -> Self {
871        Self::default()
872    }
873
874    /// Request cancellation of every request that holds a clone of this flag.
875    pub fn cancel(&self) {
876        self.cancelled.store(true, Ordering::SeqCst);
877    }
878
879    /// Whether cancellation was requested.
880    #[must_use]
881    pub fn is_cancelled(&self) -> bool {
882        self.cancelled.load(Ordering::SeqCst)
883    }
884
885    /// Forward `signal` to the request that holds a clone of this handle, for its
886    /// tracer to deliver once, as the type's documentation says.
887    pub fn forward(
888        &self,
889        signal: Signal,
890    ) {
891        self.forwarded.fetch_or(signal.bit(), Ordering::SeqCst);
892    }
893
894    /// Take every signal forwarded since the last call, in the order of
895    /// [`Signal::ALL`], so each one is delivered once.
896    #[must_use]
897    pub fn take_forwarded(&self) -> Vec<Signal> {
898        let pending = self.forwarded.swap(0, Ordering::SeqCst);
899        Signal::ALL
900            .into_iter()
901            .filter(|signal| pending & signal.bit() != 0)
902            .collect()
903    }
904}
905
906/// How a command ended.
907#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
908pub enum Termination {
909    /// The command exited with this exit code.
910    Exited(i32),
911    /// A signal with this number killed the command.
912    Signaled(i32),
913}
914
915impl Termination {
916    /// The exit code, or `None` when a signal killed the command.
917    #[must_use]
918    pub const fn code(self) -> Option<i32> {
919        match self {
920            Self::Exited(code) => Some(code),
921            Self::Signaled(_) => None,
922        }
923    }
924
925    /// The terminating signal, or `None` when the command exited.
926    #[must_use]
927    pub const fn signal(self) -> Option<i32> {
928        match self {
929            Self::Exited(_) => None,
930            Self::Signaled(signal) => Some(signal),
931        }
932    }
933}
934
935impl fmt::Display for Termination {
936    fn fmt(
937        &self,
938        f: &mut fmt::Formatter<'_>,
939    ) -> fmt::Result {
940        match self {
941            Self::Exited(code) => write!(f, "exit code {code}"),
942            Self::Signaled(signal) => write!(f, "killed by signal {signal}"),
943        }
944    }
945}
946
947/// A command's raw captured output, exactly as the process wrote it.
948#[derive(Debug, Clone, PartialEq, Eq)]
949pub enum CapturedOutput {
950    /// Output captured with [`CaptureMode::Split`].
951    Split {
952        /// The bytes written to standard output.
953        stdout: Vec<u8>,
954        /// The bytes written to standard error.
955        stderr: Vec<u8>,
956    },
957    /// Output captured with [`CaptureMode::Merged`]: both streams, in exact order.
958    Merged {
959        /// The bytes written to either stream.
960        output: Vec<u8>,
961    },
962}
963
964impl CapturedOutput {
965    /// No output yet, in the shape of `mode`.
966    #[must_use]
967    pub const fn empty(mode: CaptureMode) -> Self {
968        match mode {
969            CaptureMode::Split => {
970                Self::Split {
971                    stdout: Vec::new(),
972                    stderr: Vec::new(),
973                }
974            },
975            CaptureMode::Merged => Self::Merged { output: Vec::new() },
976        }
977    }
978
979    /// The capture mode this output was captured with.
980    #[must_use]
981    pub const fn mode(&self) -> CaptureMode {
982        match self {
983            Self::Split { .. } => CaptureMode::Split,
984            Self::Merged { .. } => CaptureMode::Merged,
985        }
986    }
987}
988
989/// Why a run was traced incompletely.
990///
991/// An incompletely traced run is never cached, and kizz warns loudly about it.
992#[derive(Debug, Clone, PartialEq, Eq, Hash)]
993pub enum IncompleteReason {
994    /// A process made a system call through a non-native interface, such as the
995    /// 32-bit `int 0x80` interface or x32, which the tracer does not decode.
996    NonNativeSystemCall {
997        /// A description of the interface and the call.
998        detail: String,
999    },
1000    /// A process made a system call that can change what a path means, such as
1001    /// `chroot`, `mount` or a change of mount namespace, or that uses a path in a way
1002    /// the tracer does not record, such as `uselib` or `swapon`.
1003    UntraceableSystemCall {
1004        /// The process and the call, named in backticks.
1005        detail: String,
1006    },
1007    /// Any other reason the tracer could not observe every access.
1008    Other {
1009        /// A description of what the tracer could not observe.
1010        detail: String,
1011    },
1012}
1013
1014impl fmt::Display for IncompleteReason {
1015    fn fmt(
1016        &self,
1017        f: &mut fmt::Formatter<'_>,
1018    ) -> fmt::Result {
1019        match self {
1020            Self::NonNativeSystemCall { detail } => {
1021                write!(f, "a system call used a non-native interface: {detail}")
1022            },
1023            Self::UntraceableSystemCall { detail } => {
1024                write!(f, "a system call that kizz cannot trace: {detail}")
1025            },
1026            Self::Other { detail } => f.write_str(detail),
1027        }
1028    }
1029}
1030
1031/// A connection that a process of the run made to a service outside the trace,
1032/// whose answer is an input that the tracer cannot see.
1033///
1034/// Connections are ordered by their kind, then by address or path, so a set of
1035/// them is sorted and without repeats.
1036#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
1037pub enum Connection {
1038    /// An IPv4 or IPv6 address and port. An IPv6 address keeps its scope, and its
1039    /// flow information is zero, because it does not name a destination.
1040    Ip(SocketAddr),
1041    /// A Unix socket by its path, absolute and normalized like every recorded
1042    /// path.
1043    UnixPath(AbsolutePath),
1044    /// A Unix socket in the abstract namespace, by its name without the zero byte
1045    /// that starts it; the name may hold more zero bytes.
1046    UnixAbstract(Vec<u8>),
1047}
1048
1049impl fmt::Display for Connection {
1050    /// An IP address with its port, such as `127.0.0.1:80` or `[fe80::1%2]:80`;
1051    /// `Unix socket /path`; or `abstract Unix socket @name`, with each byte of the
1052    /// name that is not printable ASCII escaped, such as `\x00`.
1053    fn fmt(
1054        &self,
1055        f: &mut fmt::Formatter<'_>,
1056    ) -> fmt::Result {
1057        match self {
1058            Self::Ip(address) => write!(f, "{address}"),
1059            Self::UnixPath(path) => write!(f, "Unix socket {path}"),
1060            Self::UnixAbstract(name) => {
1061                write!(f, "abstract Unix socket @{}", name.escape_ascii())
1062            },
1063        }
1064    }
1065}
1066
1067/// The answer of [`Tracer::error_name`] for an error number that has no name, and
1068/// its default answer for every number: `errno` and the number, such as
1069/// `errno 200`.
1070#[must_use]
1071pub fn unnamed_error(errno: i32) -> String {
1072    format!("errno {errno}")
1073}
1074
1075/// How the calls that touched a path in one way ended.
1076///
1077/// Outcomes sort with [`Outcome::Ok`] first, then the errors in the byte order of
1078/// their names, then [`Outcome::Unknown`], so a set of them lists them in that
1079/// order, each once.
1080#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
1081pub enum Outcome {
1082    /// The call succeeded.
1083    Ok,
1084    /// The call failed with the error of this name, such as `ENOENT`, or with an
1085    /// error without a name, written as [`unnamed_error`] writes it.
1086    Error(String),
1087    /// The tracer never saw the call's result, because its thread was killed during
1088    /// the call.
1089    Unknown,
1090}
1091
1092impl fmt::Display for Outcome {
1093    /// `ok`, the error's name, or `unknown`.
1094    fn fmt(
1095        &self,
1096        f: &mut fmt::Formatter<'_>,
1097    ) -> fmt::Result {
1098        match self {
1099            Self::Ok => f.write_str("ok"),
1100            Self::Error(name) => f.write_str(name),
1101            Self::Unknown => f.write_str("unknown"),
1102        }
1103    }
1104}
1105
1106/// The outcomes of one access kind of one path, in the order of [`Outcome`].
1107pub type Outcomes = BTreeSet<Outcome>;
1108
1109/// The access kinds of one observed path, each with its outcomes, in the order of
1110/// [`AccessKind::ALL`].
1111pub type KindOutcomes = BTreeMap<AccessKind, Outcomes>;
1112
1113/// The paths that a program touched, each with its access kinds and each kind with
1114/// its outcomes, in sorted path order.
1115///
1116/// Recording and merging are set unions: a path keeps every kind recorded for it,
1117/// and a kind every outcome, each once, whatever the order.
1118#[derive(Debug, Clone, PartialEq, Eq, Default)]
1119pub struct Observations {
1120    /// The kinds and outcomes of each observed path.
1121    paths: BTreeMap<AbsolutePath, KindOutcomes>,
1122}
1123
1124impl Observations {
1125    /// No observations.
1126    #[must_use]
1127    pub fn new() -> Self {
1128        Self::default()
1129    }
1130
1131    /// The observations of every path of `accesses`, each of its kinds with
1132    /// `outcome` alone.
1133    #[must_use]
1134    pub fn from_accesses(
1135        accesses: &Accesses,
1136        outcome: &Outcome,
1137    ) -> Self {
1138        let mut observations = Self::new();
1139        for (path, kinds) in accesses {
1140            observations.record_kinds(path.clone(), *kinds, outcome);
1141        }
1142        observations
1143    }
1144
1145    /// Record that a call with `outcome` touched `path` in the way `kind` names.
1146    pub fn record(
1147        &mut self,
1148        path: AbsolutePath,
1149        kind: AccessKind,
1150        outcome: Outcome,
1151    ) {
1152        self.paths
1153            .entry(path)
1154            .or_default()
1155            .entry(kind)
1156            .or_default()
1157            .insert(outcome);
1158    }
1159
1160    /// Record that a call with `outcome` touched `path` in every way of `kinds`.
1161    /// The path is observed even when `kinds` is empty, as [`Accesses::record_kinds`]
1162    /// records it.
1163    pub fn record_kinds(
1164        &mut self,
1165        path: AbsolutePath,
1166        kinds: AccessKinds,
1167        outcome: &Outcome,
1168    ) {
1169        let entry = self.paths.entry(path).or_default();
1170        for kind in kinds.iter() {
1171            entry.entry(kind).or_default().insert(outcome.clone());
1172        }
1173    }
1174
1175    /// Combine every observation of `other` into these.
1176    pub fn merge(
1177        &mut self,
1178        other: &Self,
1179    ) {
1180        for (path, kinds) in &other.paths {
1181            let entry = self.paths.entry(path.clone()).or_default();
1182            for (kind, outcomes) in kinds {
1183                entry
1184                    .entry(*kind)
1185                    .or_default()
1186                    .extend(outcomes.iter().cloned());
1187            }
1188        }
1189    }
1190
1191    /// The kinds of `path`, each with its outcomes, if it was observed.
1192    #[must_use]
1193    pub fn get(
1194        &self,
1195        path: &AbsolutePath,
1196    ) -> Option<&KindOutcomes> {
1197        self.paths.get(path)
1198    }
1199
1200    /// The combined access kinds of `path`, if it was observed.
1201    #[must_use]
1202    pub fn kinds(
1203        &self,
1204        path: &AbsolutePath,
1205    ) -> Option<AccessKinds> {
1206        self.paths
1207            .get(path)
1208            .map(|kinds| kinds.keys().copied().collect())
1209    }
1210
1211    /// The number of observed paths.
1212    #[must_use]
1213    pub fn len(&self) -> usize {
1214        self.paths.len()
1215    }
1216
1217    /// Whether no path was observed.
1218    #[must_use]
1219    pub fn is_empty(&self) -> bool {
1220        self.paths.is_empty()
1221    }
1222
1223    /// The observed paths with their kinds and outcomes, in sorted path order.
1224    pub fn iter(&self) -> btree_map::Iter<'_, AbsolutePath, KindOutcomes> {
1225        self.paths.iter()
1226    }
1227
1228    /// Every observed path with its combined access kinds, without the outcomes.
1229    #[must_use]
1230    pub fn accesses(&self) -> Accesses {
1231        let mut accesses = Accesses::new();
1232        for (path, kinds) in &self.paths {
1233            accesses.record_kinds(path.clone(), kinds.keys().copied().collect());
1234        }
1235        accesses
1236    }
1237}
1238
1239impl<'a> IntoIterator for &'a Observations {
1240    type IntoIter = btree_map::Iter<'a, AbsolutePath, KindOutcomes>;
1241    type Item = (&'a AbsolutePath, &'a KindOutcomes);
1242
1243    fn into_iter(self) -> Self::IntoIter {
1244        self.paths.iter()
1245    }
1246}
1247
1248/// One program that a traced process ran, with everything the tracer attributes to
1249/// it.
1250///
1251/// A program is the path that an `exec` call named, resolved as its observation is,
1252/// with the arguments that the call passed; a process that a fork, a vfork or a
1253/// clone created first runs its creator's program, which it lists as inherited.
1254/// Everything the process does while it runs the program belongs to the program,
1255/// and so does a successful `exec` that starts it: its own path, its interpreters
1256/// and its ELF loader. A failed `exec` belongs to the program that made the call.
1257#[derive(Debug, Clone, PartialEq, Eq)]
1258pub struct Program {
1259    /// The path of the program.
1260    pub path: AbsolutePath,
1261    /// The argument vector that the program received, starting with its
1262    /// `argv[0]`, or empty when the tracer could not read it.
1263    pub args: Vec<OsString>,
1264    /// Whether the process runs the program because its creator ran it, rather than
1265    /// through an `exec` of its own.
1266    pub inherited: bool,
1267    /// The paths that the program touched, with their kinds and outcomes.
1268    pub observations: Observations,
1269    /// The connections that the program made.
1270    pub connections: BTreeSet<Connection>,
1271    /// The native numbers of the system calls that the program made and that the
1272    /// tracer does not know.
1273    pub unknown_system_calls: BTreeSet<u32>,
1274    /// Every reason that the program made the trace incomplete, in the order the
1275    /// tracer found them.
1276    pub incomplete: Vec<IncompleteReason>,
1277}
1278
1279impl Program {
1280    /// The program at `path` with `args`, inherited or not, to which nothing is
1281    /// attributed yet.
1282    #[must_use]
1283    pub const fn new(
1284        path: AbsolutePath,
1285        args: Vec<OsString>,
1286        inherited: bool,
1287    ) -> Self {
1288        Self {
1289            path,
1290            args,
1291            inherited,
1292            observations: Observations {
1293                paths: BTreeMap::new(),
1294            },
1295            connections: BTreeSet::new(),
1296            unknown_system_calls: BTreeSet::new(),
1297            incomplete: Vec::new(),
1298        }
1299    }
1300
1301    /// Whether nothing is attributed to the program: no observation, connection,
1302    /// unknown system call or incomplete reason.
1303    #[must_use]
1304    pub fn is_empty(&self) -> bool {
1305        self.observations.is_empty()
1306            && self.connections.is_empty()
1307            && self.unknown_system_calls.is_empty()
1308            && self.incomplete.is_empty()
1309    }
1310}
1311
1312/// One traced process: a thread group, whose threads fold into it.
1313#[derive(Debug, Clone, PartialEq, Eq)]
1314pub struct Process {
1315    /// The number of the process, unique within the run: processes are numbered
1316    /// from 1 in the order the tracer saw them start, and process 1 is the command.
1317    pub number: u32,
1318    /// The process ID that the system gave it, or `None` when none is known, as
1319    /// for a fake tracer or a command whose process never started.
1320    pub pid: Option<u32>,
1321    /// The number of the process that created it, or `None` for the command and
1322    /// for a process whose creation the tracer never saw.
1323    pub parent: Option<u32>,
1324    /// The programs it ran, in order.
1325    pub programs: Vec<Program>,
1326    /// How it ended, or `None` when the tracer did not see it end, or the command
1327    /// could not start.
1328    pub status: Option<Termination>,
1329}
1330
1331/// The processes of a run, in the order the tracer saw them start, each with its
1332/// programs and their observations.
1333///
1334/// A process ID that the system gives to a new process within the run starts a new
1335/// process, so two processes never merge. The kinds of each path, combined over
1336/// every program, are exactly its kinds in the run's combined accesses.
1337#[derive(Debug, Clone, PartialEq, Eq, Default)]
1338pub struct ProcessTree {
1339    /// The processes, numbered from 1, in order.
1340    pub processes: Vec<Process>,
1341}
1342
1343impl ProcessTree {
1344    /// The tree of one process, the command of `request`, without a process ID,
1345    /// whose one program is the request's program with its arguments, which
1346    /// touched every path of `accesses` with its kinds, each with the outcome
1347    /// `ok`, and which ended as `status` says. Fake tracers build their trees
1348    /// with it.
1349    #[must_use]
1350    pub fn of_request(
1351        request: &RunRequest,
1352        accesses: &Accesses,
1353        status: Option<Termination>,
1354    ) -> Self {
1355        let mut program = Program::new(request.program.clone(), request.args.clone(), false);
1356        program.observations = Observations::from_accesses(accesses, &Outcome::Ok);
1357        Self {
1358            processes: vec![Process {
1359                number: 1,
1360                pid: None,
1361                parent: None,
1362                programs: vec![program],
1363                status,
1364            }],
1365        }
1366    }
1367
1368    /// The tree of one process, the command of `request`, built from the run's
1369    /// whole `result`, as [`ProcessTree::of_request`] builds it from the result's
1370    /// accesses and termination, with the result's reason that the trace is
1371    /// incomplete, when it has one, its unknown system calls and its connections
1372    /// on the one program, where the Linux tracer puts them: on the program that
1373    /// made them. So the tree carries everything that the run reports, and a report
1374    /// built from it says what the run says. Fake tracers whose runs a test builds a
1375    /// report from build their trees with it; the tree of a failed start, which
1376    /// reports none of these, keeps the shape that `of_request` gives it.
1377    #[must_use]
1378    pub fn of_run(
1379        request: &RunRequest,
1380        result: &RunResult,
1381    ) -> Self {
1382        let mut tree = Self::of_request(request, &result.accesses, Some(result.termination));
1383        for process in &mut tree.processes {
1384            for program in &mut process.programs {
1385                program.incomplete.extend(result.incomplete.iter().cloned());
1386                program
1387                    .unknown_system_calls
1388                    .extend(result.unknown_system_calls.iter().copied());
1389                program
1390                    .connections
1391                    .extend(result.connections.iter().cloned());
1392            }
1393        }
1394        tree
1395    }
1396
1397    /// The process numbered `number`, if there is one.
1398    #[must_use]
1399    pub fn process(
1400        &self,
1401        number: u32,
1402    ) -> Option<&Process> {
1403        self.processes
1404            .iter()
1405            .find(|process| process.number == number)
1406    }
1407
1408    /// Every program of every process, with its process, in order.
1409    pub fn programs(&self) -> impl Iterator<Item = (&Process, &Program)> {
1410        self.processes.iter().flat_map(|process| {
1411            process
1412                .programs
1413                .iter()
1414                .map(move |program| (process, program))
1415        })
1416    }
1417
1418    /// The observations of every program, combined.
1419    #[must_use]
1420    pub fn observations(&self) -> Observations {
1421        let mut combined = Observations::new();
1422        for (_, program) in self.programs() {
1423            combined.merge(&program.observations);
1424        }
1425        combined
1426    }
1427
1428    /// The access kinds of every path of every program, combined, without the
1429    /// outcomes.
1430    #[must_use]
1431    pub fn accesses(&self) -> Accesses {
1432        self.observations().accesses()
1433    }
1434
1435    /// The connections of every program, combined.
1436    #[must_use]
1437    pub fn connections(&self) -> BTreeSet<Connection> {
1438        self.programs()
1439            .flat_map(|(_, program)| program.connections.iter().cloned())
1440            .collect()
1441    }
1442
1443    /// The unknown system calls of every program, combined.
1444    #[must_use]
1445    pub fn unknown_system_calls(&self) -> BTreeSet<u32> {
1446        self.programs()
1447            .flat_map(|(_, program)| program.unknown_system_calls.iter().copied())
1448            .collect()
1449    }
1450}
1451
1452/// The result of a request that started.
1453#[derive(Debug, Clone, PartialEq, Eq)]
1454pub struct RunResult {
1455    /// How the command ended.
1456    pub termination: Termination,
1457    /// The raw captured output, in the shape of the request's capture mode.
1458    pub output: CapturedOutput,
1459    /// Every path the process tree touched, absolute and normalized, with its
1460    /// combined access kinds.
1461    pub accesses: Accesses,
1462    /// Why the trace is incomplete, or `None` when every access was observed.
1463    pub incomplete: Option<IncompleteReason>,
1464    /// The first-read metadata of the regular files the process tree read or ran
1465    /// before it wrote them, as [`FirstReads`] describes.
1466    pub first_reads: FirstReads,
1467    /// The native numbers of the system calls that the tracer does not know, as
1468    /// the filter saw them, which a process of the tree made, sorted and without
1469    /// repeats. They do not make the trace incomplete: the engine decides whether a
1470    /// run that made any is cached.
1471    pub unknown_system_calls: BTreeSet<u32>,
1472    /// The connections that a process of the tree made, sorted and without
1473    /// repeats, as [`Connection`] describes them. They do not make the trace
1474    /// incomplete: the engine records them and warns about them.
1475    pub connections: BTreeSet<Connection>,
1476    /// The process tree of the run when the request asked for it with
1477    /// [`RunRequest::tree`], and `None` otherwise.
1478    pub tree: Option<ProcessTree>,
1479}
1480
1481impl RunResult {
1482    /// Whether the tracer observed every access of the run.
1483    #[must_use]
1484    pub const fn is_complete(&self) -> bool {
1485        self.incomplete.is_none()
1486    }
1487}
1488
1489/// A request that did not produce a [`RunResult`].
1490///
1491/// The variants keep three cases apart, because the engine treats them
1492/// differently: a missing or non-executable program fails its task and is recorded
1493/// like any other failure; another failure to start is not cached; and a failure
1494/// of the tracer itself is neither the command's fault nor cached.
1495#[derive(Debug, thiserror::Error)]
1496pub enum TraceError {
1497    /// The program does not exist.
1498    #[error("program not found: {program}")]
1499    ProgramNotFound {
1500        /// The program of the request.
1501        program: AbsolutePath,
1502        /// The paths touched while trying to start the program.
1503        accesses: Accesses,
1504        /// The tree of the one process that tried to start the program, when the
1505        /// request asked for it with [`RunRequest::tree`].
1506        tree: Option<ProcessTree>,
1507    },
1508    /// The program exists but cannot be executed.
1509    #[error("program is not executable: {program}: {source}")]
1510    ProgramNotExecutable {
1511        /// The program of the request.
1512        program: AbsolutePath,
1513        /// The error that starting the program reported.
1514        source: io::Error,
1515        /// The paths touched while trying to start the program.
1516        accesses: Accesses,
1517        /// The tree of the one process that tried to start the program, when the
1518        /// request asked for it with [`RunRequest::tree`].
1519        tree: Option<ProcessTree>,
1520    },
1521    /// The command could not start for a reason other than a missing or
1522    /// non-executable program.
1523    #[error("could not start {program}: {source}")]
1524    StartFailed {
1525        /// The program of the request.
1526        program: AbsolutePath,
1527        /// The error that starting the program reported.
1528        source: io::Error,
1529        /// The paths touched while trying to start the program.
1530        accesses: Accesses,
1531        /// The tree of the one process that tried to start the program, when the
1532        /// request asked for it with [`RunRequest::tree`].
1533        tree: Option<ProcessTree>,
1534    },
1535    /// The tracer itself failed, independently of the command.
1536    #[error("tracer failure: {message}")]
1537    Tracer {
1538        /// What the tracer was doing when it failed.
1539        message: String,
1540        /// The underlying error, if there is one.
1541        source: Option<io::Error>,
1542    },
1543}
1544
1545impl TraceError {
1546    /// Whether the program is missing or not executable, the one failure to start
1547    /// that is recorded like any other task failure.
1548    #[must_use]
1549    pub const fn is_missing_program(&self) -> bool {
1550        matches!(
1551            self,
1552            Self::ProgramNotFound { .. } | Self::ProgramNotExecutable { .. }
1553        )
1554    }
1555
1556    /// Whether the tracer itself failed, rather than the command.
1557    #[must_use]
1558    pub const fn is_tracer_failure(&self) -> bool {
1559        matches!(self, Self::Tracer { .. })
1560    }
1561
1562    /// The paths touched while trying to start the program, if the error is a
1563    /// failure to start.
1564    #[must_use]
1565    pub const fn accesses(&self) -> Option<&Accesses> {
1566        match self {
1567            Self::ProgramNotFound { accesses, .. }
1568            | Self::ProgramNotExecutable { accesses, .. }
1569            | Self::StartFailed { accesses, .. } => Some(accesses),
1570            Self::Tracer { .. } => None,
1571        }
1572    }
1573
1574    /// The tree of the one process that tried to start the program, if the error is
1575    /// a failure to start and the request asked for the tree.
1576    #[must_use]
1577    pub const fn tree(&self) -> Option<&ProcessTree> {
1578        match self {
1579            Self::ProgramNotFound { tree, .. }
1580            | Self::ProgramNotExecutable { tree, .. }
1581            | Self::StartFailed { tree, .. } => tree.as_ref(),
1582            Self::Tracer { .. } => None,
1583        }
1584    }
1585}
1586
1587/// The kernel that runs a command, as `uname` reports it.
1588#[derive(Debug, Clone, PartialEq, Eq, Hash)]
1589pub struct Kernel {
1590    /// The kernel release, such as `6.12.0`.
1591    pub release: String,
1592    /// The kernel version, such as `#1 SMP PREEMPT_DYNAMIC`.
1593    pub version: String,
1594}
1595
1596/// One resource limit of a process, soft and hard.
1597#[derive(Debug, Clone, PartialEq, Eq, Hash)]
1598pub struct ResourceLimit {
1599    /// The resource, as `prlimit` names it, such as `nofile`.
1600    pub resource: String,
1601    /// The soft limit, or `None` when it is unlimited.
1602    pub soft: Option<u64>,
1603    /// The hard limit, or `None` when it is unlimited.
1604    pub hard: Option<u64>,
1605}
1606
1607/// The memory of the machine, in bytes.
1608#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
1609pub struct Memory {
1610    /// The total memory.
1611    pub total: u64,
1612    /// The memory available to start new work without swapping.
1613    pub available: u64,
1614}
1615
1616/// The file system that holds a working directory.
1617#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
1618pub struct FileSystem {
1619    /// The type of the file system, as the platform numbers it.
1620    pub kind: u64,
1621    /// The mount flags, as the platform numbers them.
1622    pub flags: u64,
1623}
1624
1625/// The size and free space of the file system that holds a working directory, in
1626/// bytes.
1627#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
1628pub struct Disk {
1629    /// The size of the file system.
1630    pub size: u64,
1631    /// The free space that a process without privileges may use.
1632    pub free: u64,
1633}
1634
1635/// The machine and process state that a command inherits when it starts, in six
1636/// parts. A part that could not be read is `None`.
1637///
1638/// Kizz records it with every step that runs, and compares only the parts that a
1639/// step names with `run(..., machine = [...])`.
1640#[derive(Debug, Clone, PartialEq, Eq, Hash, Default)]
1641pub struct MachineState {
1642    /// `kernel`: the kernel release and version.
1643    pub kernel: Option<Kernel>,
1644    /// `limits`: every resource limit, soft and hard, in the platform's order.
1645    pub limits: Option<Vec<ResourceLimit>>,
1646    /// `affinity`: the CPUs the command may run on, by number, sorted.
1647    pub affinity: Option<Vec<u32>>,
1648    /// `memory`: the total and the available memory.
1649    pub memory: Option<Memory>,
1650    /// `filesystem`: the type and mount flags of the file system that holds the
1651    /// working directory.
1652    pub filesystem: Option<FileSystem>,
1653    /// `disk`: the size and free space of that file system.
1654    pub disk: Option<Disk>,
1655}
1656
1657/// The extended attributes of one path: each name with its value, as bytes, sorted
1658/// by name.
1659pub type ExtendedAttributes = BTreeMap<Vec<u8>, Vec<u8>>;
1660
1661/// Runs and traces commands, and answers the platform queries of the core.
1662///
1663/// The Linux tracer implements it with `ptrace` and seccomp, and tests implement it
1664/// with a fake that performs scripted file operations and reports them, and that
1665/// answers the queries from values the test sets.
1666pub trait Tracer: Send + Sync {
1667    /// Run one command, wait for its whole process tree to finish, and report what
1668    /// it did.
1669    ///
1670    /// When [`RunRequest::echo`] is set, output also goes to `echo` live. When
1671    /// `cancel` is set while the command runs, the tracer interrupts the whole
1672    /// process tree, kills whatever remains of it after a grace period, and returns
1673    /// the result once the tree has exited; the command may then have ended by a
1674    /// signal or with an exit code. A signal that the caller forwards through
1675    /// `cancel` with [`Cancellation::forward`] while the command runs goes once to
1676    /// the command's first process while it lives, and afterwards to each live
1677    /// process of the tree; a fake tracer may ignore it. When
1678    /// [`RunRequest::terminal`] is set, the command keeps the terminal and the
1679    /// result's output is empty.
1680    ///
1681    /// # Errors
1682    ///
1683    /// Returns a [`TraceError`] when the command could not start or the tracer
1684    /// failed.
1685    fn run(
1686        &self,
1687        request: &RunRequest,
1688        echo: &dyn EchoSink,
1689        cancel: &Cancellation,
1690    ) -> Result<RunResult, TraceError>;
1691
1692    /// Run a command without tracing its dependencies. The engine never reuses its
1693    /// result. Implementations must preserve the request's environment, streams and
1694    /// cancellation. The result must mark observation incomplete, including any
1695    /// forced stream closure, and must not claim unobserved dependencies.
1696    ///
1697    /// # Errors
1698    ///
1699    /// Returns an error when untraced execution is unsupported or the command cannot
1700    /// start.
1701    fn run_untraced(
1702        &self,
1703        _request: &RunRequest,
1704        _echo: &dyn EchoSink,
1705        _cancel: &Cancellation,
1706    ) -> Result<RunResult, TraceError> {
1707        Err(TraceError::Tracer {
1708            message: "this runner does not support untraced execution".to_owned(),
1709            source: None,
1710        })
1711    }
1712
1713    /// The extended attributes of `path`, each name with its value, sorted by name,
1714    /// following a final symbolic link when `follow` is set, or not when it is not.
1715    /// A file system that keeps no extended attributes has none.
1716    ///
1717    /// The core reads extended attributes only through this query, because the
1718    /// standard library cannot read them.
1719    ///
1720    /// # Errors
1721    ///
1722    /// Returns the error of reading the attributes, such as
1723    /// [`io::ErrorKind::NotFound`] when nothing is at the path.
1724    fn extended_attributes(
1725        &self,
1726        path: &Path,
1727        follow: bool,
1728    ) -> io::Result<ExtendedAttributes>;
1729
1730    /// The machine and process state that a command started in `cwd` inherits: the
1731    /// kernel, the resource limits, the CPUs it may run on, the memory, and the file
1732    /// system that holds `cwd`, with its size and free space. A part that cannot be
1733    /// read is `None`.
1734    ///
1735    /// The core reads machine state only through this query, because the standard
1736    /// library cannot read it.
1737    fn machine_state(
1738        &self,
1739        cwd: &Path,
1740    ) -> MachineState;
1741
1742    /// The name of the error number `errno` on the platform, such as `ENOENT`, which
1743    /// the core uses to report a failed check of its own as the tracer reports a
1744    /// failed call.
1745    ///
1746    /// The default answer is [`unnamed_error`], `errno` and the number, so a tracer
1747    /// that knows no names, such as a fake, needs no implementation.
1748    fn error_name(
1749        &self,
1750        errno: i32,
1751    ) -> String {
1752        unnamed_error(errno)
1753    }
1754}
1755
1756/// Unit tests for the logic of the tracer interface.
1757#[cfg(test)]
1758#[allow(
1759    clippy::disallowed_macros,
1760    clippy::disallowed_methods,
1761    reason = "test code: the tests assert and lock"
1762)]
1763mod tests {
1764    use std::{
1765        collections::{BTreeMap, BTreeSet},
1766        ffi::OsString,
1767        fs, io,
1768        path::Path,
1769    };
1770
1771    use super::{
1772        AbsolutePath, AccessKind, AccessKinds, Accesses, Cancellation, CaptureMode, CapturedOutput,
1773        Connection, EchoSink, ExtendedAttributes, FileMetadata, FirstReads, IncompleteReason,
1774        MachineState, NotAbsoluteError, Observations, Outcome, Process, ProcessTree, Program,
1775        RunRequest, RunResult, Signal, Termination, TraceError, Tracer, unnamed_error,
1776    };
1777
1778    /// Build an absolute path for a test.
1779    fn path(text: &str) -> AbsolutePath {
1780        AbsolutePath::new(text).unwrap()
1781    }
1782
1783    /// Combining kinds is a set union that ignores order and repetition.
1784    #[test]
1785    fn access_kinds_combine_as_a_set() {
1786        let mut kinds = AccessKinds::EMPTY;
1787        assert!(kinds.is_empty() && kinds.iter().next().is_none());
1788        kinds.insert(AccessKind::Write);
1789        kinds |= AccessKind::Read;
1790        kinds |= AccessKind::Write;
1791        assert!(kinds.contains(AccessKind::Read));
1792        assert!(kinds.contains(AccessKind::Write));
1793        assert!(!kinds.contains(AccessKind::Probe));
1794        assert_eq!(kinds.iter().collect::<Vec<_>>(), vec![
1795            AccessKind::Read,
1796            AccessKind::Write
1797        ]);
1798
1799        let reversed: AccessKinds = [AccessKind::Write, AccessKind::Read, AccessKind::Read]
1800            .into_iter()
1801            .collect();
1802        assert_eq!(kinds, reversed);
1803        assert_eq!(
1804            AccessKinds::only(AccessKind::Read) | AccessKinds::only(AccessKind::Write),
1805            kinds
1806        );
1807        assert_eq!(kinds.union(AccessKinds::EMPTY), kinds);
1808        assert_eq!(
1809            AccessKinds::from(AccessKind::Exec),
1810            AccessKinds::only(AccessKind::Exec)
1811        );
1812    }
1813
1814    /// Every kind has its own bit, so the full set holds all six.
1815    #[test]
1816    fn every_access_kind_is_distinct() {
1817        let all: AccessKinds = AccessKind::ALL.into_iter().collect();
1818        assert_eq!(all.iter().collect::<Vec<_>>(), AccessKind::ALL.to_vec());
1819        for kind in AccessKind::ALL {
1820            assert_eq!(AccessKinds::only(kind).iter().collect::<Vec<_>>(), vec![
1821                kind
1822            ]);
1823        }
1824    }
1825
1826    /// Kinds display by name, joined with `+`.
1827    #[test]
1828    fn access_kinds_display() {
1829        assert_eq!(AccessKinds::EMPTY.to_string(), "none");
1830        assert_eq!(AccessKind::List.to_string(), "list");
1831        let kinds = AccessKinds::only(AccessKind::Exec)
1832            .with(AccessKind::Probe)
1833            .with(AccessKind::Read);
1834        assert_eq!(kinds.to_string(), "read+probe+exec");
1835    }
1836
1837    /// The extended-attribute kind is named `xattr`, comes after `exec`, and has its
1838    /// own bit.
1839    #[test]
1840    fn the_xattr_kind_follows_exec() {
1841        assert_eq!(AccessKind::Xattr.to_string(), "xattr");
1842        assert_eq!(AccessKind::ALL.last(), Some(&AccessKind::Xattr));
1843        let kinds = AccessKinds::only(AccessKind::Xattr).with(AccessKind::Exec);
1844        assert_eq!(kinds.to_string(), "exec+xattr");
1845        assert!(!AccessKinds::only(AccessKind::Exec).contains(AccessKind::Xattr));
1846    }
1847
1848    /// Accesses to the same path combine into one entry, in sorted path order.
1849    #[test]
1850    fn accesses_combine_per_path() {
1851        let mut accesses = Accesses::new();
1852        assert!(accesses.is_empty() && accesses.iter().next().is_none());
1853        accesses.record(path("/b"), AccessKind::Read);
1854        accesses.record(path("/a"), AccessKind::Probe);
1855        accesses.record(path("/b/"), AccessKind::Write);
1856        accesses.record(path("/a"), AccessKind::Probe);
1857        assert_eq!(accesses.len(), 2);
1858        assert_eq!(
1859            accesses.get(&path("/b")),
1860            Some(AccessKinds::only(AccessKind::Read).with(AccessKind::Write))
1861        );
1862        assert_eq!(accesses.get(&path("/c")), None);
1863        let order: Vec<String> = accesses.iter().map(|(path, _)| path.to_string()).collect();
1864        assert_eq!(order, vec!["/a", "/b"]);
1865
1866        let mut other = Accesses::new();
1867        other.record(path("/a"), AccessKind::List);
1868        other.record(path("/c"), AccessKind::Exec);
1869        accesses.merge(other);
1870        assert_eq!(accesses.len(), 3);
1871        assert_eq!(
1872            accesses.get(&path("/a")),
1873            Some(AccessKinds::only(AccessKind::Probe).with(AccessKind::List))
1874        );
1875
1876        let collected: Accesses = [
1877            (path("/x"), AccessKind::Read),
1878            (path("/x"), AccessKind::Exec),
1879        ]
1880        .into_iter()
1881        .collect();
1882        let owned: Vec<_> = collected.into_iter().collect();
1883        assert_eq!(owned, vec![(
1884            path("/x"),
1885            AccessKinds::only(AccessKind::Read).with(AccessKind::Exec)
1886        )]);
1887    }
1888
1889    /// Normalizing removes `.` and repeated separators and keeps `..`.
1890    #[test]
1891    fn absolute_paths_normalize() {
1892        assert_eq!(path("/a/./b//c/").as_path(), Path::new("/a/b/c"));
1893        assert_eq!(path("/a/../b").as_path(), Path::new("/a/../b"));
1894        assert_eq!(path("//a").to_string(), "/a");
1895        assert_eq!(path("/").as_path(), Path::new("/"));
1896        assert_eq!(
1897            AbsolutePath::new("a/b"),
1898            Err(NotAbsoluteError { path: "a/b".into() })
1899        );
1900        assert_eq!(
1901            AbsolutePath::try_from(std::path::PathBuf::from("/x/."))
1902                .map(AbsolutePath::into_path_buf),
1903            Ok("/x".into())
1904        );
1905    }
1906
1907    /// Relative paths resolve against a base, and absolute ones replace it.
1908    #[test]
1909    fn absolute_paths_join() {
1910        let base = path("/work/dir");
1911        assert_eq!(
1912            base.join("./src//main.rs").as_path(),
1913            Path::new("/work/dir/src/main.rs")
1914        );
1915        assert_eq!(base.join("../up").as_path(), Path::new("/work/dir/../up"));
1916        assert_eq!(
1917            base.join("/etc/./passwd").as_path(),
1918            Path::new("/etc/passwd")
1919        );
1920        assert_eq!(base.join("").as_path(), Path::new("/work/dir"));
1921    }
1922
1923    /// Clones of a cancellation flag share it.
1924    #[test]
1925    fn cancellation_is_shared() {
1926        let cancel = Cancellation::new();
1927        let clone = cancel.clone();
1928        assert!(!clone.is_cancelled());
1929        cancel.cancel();
1930        assert!(clone.is_cancelled());
1931    }
1932
1933    /// A forwarded signal is taken once, through any clone, and a signal forwarded
1934    /// twice before it is taken is taken once, in the order of `Signal::ALL`.
1935    #[test]
1936    fn forwarded_signals_are_taken_once() {
1937        let cancel = Cancellation::new();
1938        let tracer = cancel.clone();
1939        assert_eq!(tracer.take_forwarded(), Vec::new());
1940        cancel.forward(Signal::Terminate);
1941        assert_eq!(tracer.take_forwarded(), vec![Signal::Terminate]);
1942        assert_eq!(tracer.take_forwarded(), Vec::new());
1943        cancel.forward(Signal::Terminate);
1944        cancel.forward(Signal::Hangup);
1945        cancel.forward(Signal::Terminate);
1946        assert_eq!(tracer.take_forwarded(), vec![
1947            Signal::Hangup,
1948            Signal::Terminate
1949        ]);
1950        assert_eq!(cancel.take_forwarded(), Vec::new());
1951    }
1952
1953    /// Forwarding a signal does not cancel, and cancelling forwards no signal.
1954    #[test]
1955    fn forwarding_and_cancellation_are_apart() {
1956        let cancel = Cancellation::new();
1957        cancel.forward(Signal::Hangup);
1958        assert!(!cancel.is_cancelled());
1959        assert_eq!(cancel.take_forwarded(), vec![Signal::Hangup]);
1960        cancel.cancel();
1961        assert_eq!(cancel.take_forwarded(), Vec::new());
1962    }
1963
1964    /// A forwarded signal is named as the operating system names it.
1965    #[test]
1966    fn signals_are_named() {
1967        assert_eq!(Signal::Hangup.to_string(), "SIGHUP");
1968        assert_eq!(Signal::Terminate.to_string(), "SIGTERM");
1969    }
1970
1971    /// A termination reports either an exit code or a signal.
1972    #[test]
1973    fn termination_reports_code_or_signal() {
1974        assert_eq!(Termination::Exited(3).code(), Some(3));
1975        assert_eq!(Termination::Exited(3).signal(), None);
1976        assert_eq!(Termination::Signaled(9).code(), None);
1977        assert_eq!(Termination::Signaled(9).signal(), Some(9));
1978        assert_eq!(Termination::Exited(0).to_string(), "exit code 0");
1979        assert_eq!(Termination::Signaled(2).to_string(), "killed by signal 2");
1980    }
1981
1982    /// Captured output keeps the shape of its capture mode.
1983    #[test]
1984    fn captured_output_matches_mode() {
1985        for mode in [CaptureMode::Split, CaptureMode::Merged] {
1986            assert_eq!(CapturedOutput::empty(mode).mode(), mode);
1987        }
1988        assert_eq!(CaptureMode::default(), CaptureMode::Split);
1989    }
1990
1991    /// The metadata of a regular file holds what `stat` reports, and nothing else
1992    /// has metadata.
1993    #[test]
1994    fn file_metadata_describes_only_regular_files() {
1995        let manifest = Path::new(env!("CARGO_MANIFEST_DIR")).join("Cargo.toml");
1996        let metadata = FileMetadata::at(&manifest).unwrap();
1997        let stat = fs::metadata(&manifest).unwrap();
1998        assert_eq!(FileMetadata::of(&stat), Some(metadata));
1999        assert_eq!(metadata.size, stat.len());
2000        assert!(metadata.mtime_nanos > 0 && metadata.ctime_nanos > 0);
2001        assert_eq!(metadata.mode & 0o170_000, 0o100_000);
2002        assert_eq!(
2003            FileMetadata::at(Path::new(env!("CARGO_MANIFEST_DIR"))),
2004            None
2005        );
2006        assert_eq!(
2007            FileMetadata::at(&Path::new(env!("CARGO_MANIFEST_DIR")).join("no-such-file")),
2008            None
2009        );
2010    }
2011
2012    /// A first read is noted once, and never after a write of the same path;
2013    /// a write of another path does not matter.
2014    #[test]
2015    fn first_reads_are_noted_before_any_write() {
2016        let metadata = |inode| {
2017            FileMetadata {
2018                device: 1,
2019                inode,
2020                size: 2,
2021                mtime_nanos: 3,
2022                ctime_nanos: 4,
2023                mode: 0o100_644,
2024                uid: 5,
2025                gid: 6,
2026            }
2027        };
2028        let mut accesses = Accesses::new();
2029        let mut reads = FirstReads::new();
2030        assert!(reads.is_empty());
2031        accesses.record(path("/other"), AccessKind::Write);
2032        assert!(reads.note(&path("/in"), metadata(1), &accesses));
2033        accesses.record(path("/in"), AccessKind::Read);
2034        // A later read keeps the first note, even after a write.
2035        accesses.record(path("/in"), AccessKind::Write);
2036        assert!(!reads.note(&path("/in"), metadata(2), &accesses));
2037        assert_eq!(reads.get(&path("/in")), Some(&metadata(1)));
2038        // A path written before its first read is never noted.
2039        accesses.record(path("/out"), AccessKind::Write);
2040        assert!(!reads.is_first(&path("/out"), &accesses));
2041        assert!(!reads.note(&path("/out"), metadata(3), &accesses));
2042        assert!(!reads.note_at(&path("/out"), &accesses));
2043        assert_eq!(reads.len(), 1);
2044        let noted: Vec<String> = reads.iter().map(|(path, _)| path.to_string()).collect();
2045        assert_eq!(noted, ["/in"]);
2046        assert_eq!((&reads).into_iter().count(), 1);
2047    }
2048
2049    /// Noting a path reads its metadata now, following links, and notes nothing for
2050    /// a path that names no regular file.
2051    #[test]
2052    fn first_reads_read_the_metadata_of_regular_files() {
2053        let manifest = Path::new(env!("CARGO_MANIFEST_DIR")).join("Cargo.toml");
2054        let file = AbsolutePath::new(&manifest).unwrap();
2055        let directory = AbsolutePath::new(env!("CARGO_MANIFEST_DIR")).unwrap();
2056        let missing = directory.join("no-such-file");
2057        let accesses = Accesses::new();
2058        let mut reads = FirstReads::new();
2059        assert!(reads.note_at(&file, &accesses));
2060        assert!(!reads.note_at(&directory, &accesses));
2061        assert!(!reads.note_at(&missing, &accesses));
2062        assert_eq!(reads.get(&file).copied(), FileMetadata::at(&manifest));
2063        assert_eq!(reads.len(), 1);
2064    }
2065
2066    /// A result is complete only without an incomplete-trace report.
2067    #[test]
2068    fn incomplete_results_are_reported() {
2069        let mut result = RunResult {
2070            termination: Termination::Exited(0),
2071            output: CapturedOutput::empty(CaptureMode::Merged),
2072            accesses: Accesses::new(),
2073            incomplete: None,
2074            first_reads: FirstReads::new(),
2075            unknown_system_calls: BTreeSet::new(),
2076            connections: BTreeSet::new(),
2077            tree: None,
2078        };
2079        assert!(result.is_complete());
2080        result.incomplete = Some(IncompleteReason::NonNativeSystemCall {
2081            detail: "int 0x80 open".to_owned(),
2082        });
2083        assert!(!result.is_complete());
2084        assert_eq!(
2085            result.incomplete.as_ref().map(ToString::to_string),
2086            Some("a system call used a non-native interface: int 0x80 open".to_owned())
2087        );
2088        assert_eq!(
2089            IncompleteReason::Other {
2090                detail: "lost a process".to_owned()
2091            }
2092            .to_string(),
2093            "lost a process"
2094        );
2095        assert_eq!(
2096            IncompleteReason::UntraceableSystemCall {
2097                detail: "process 7 made `chroot`".to_owned()
2098            }
2099            .to_string(),
2100            "a system call that kizz cannot trace: process 7 made `chroot`"
2101        );
2102        // Unknown system calls alone leave the trace complete.
2103        result.incomplete = None;
2104        result.unknown_system_calls = BTreeSet::from([400, 1_000_000]);
2105        assert!(result.is_complete());
2106        // Connections alone leave the trace complete too.
2107        result.connections = BTreeSet::from([Connection::UnixAbstract(b"kizz".to_vec())]);
2108        assert!(result.is_complete());
2109    }
2110
2111    /// Connections read as an address and port, or as a Unix socket by path or
2112    /// abstract name with its unprintable bytes escaped, and sort by kind, then by
2113    /// address, path or name, without repeats.
2114    #[test]
2115    fn connections_display_and_sort() {
2116        let v4 = Connection::Ip("127.0.0.1:80".parse().unwrap());
2117        let v6 = Connection::Ip(std::net::SocketAddr::V6(std::net::SocketAddrV6::new(
2118            "fe80::1".parse().unwrap(),
2119            443,
2120            0,
2121            2,
2122        )));
2123        let unix = Connection::UnixPath(path("/run/kizz.sock"));
2124        let abstract_name = Connection::UnixAbstract(b"kizz\0x".to_vec());
2125        assert_eq!(v4.to_string(), "127.0.0.1:80");
2126        assert_eq!(v6.to_string(), "[fe80::1%2]:443");
2127        assert_eq!(unix.to_string(), "Unix socket /run/kizz.sock");
2128        assert_eq!(
2129            abstract_name.to_string(),
2130            "abstract Unix socket @kizz\\x00x"
2131        );
2132        let set = BTreeSet::from([
2133            abstract_name.clone(),
2134            unix.clone(),
2135            v6.clone(),
2136            v4.clone(),
2137            v4.clone(),
2138        ]);
2139        assert_eq!(set.into_iter().collect::<Vec<_>>(), [
2140            v4,
2141            v6,
2142            unix,
2143            abstract_name
2144        ]);
2145    }
2146
2147    /// Errors tell a missing program, another failure to start, and a tracer
2148    /// failure apart.
2149    #[test]
2150    fn trace_errors_are_classified() {
2151        let program = path("/bin/missing");
2152        let mut accesses = Accesses::new();
2153        accesses.record(program.clone(), AccessKind::Exec);
2154
2155        let not_found = TraceError::ProgramNotFound {
2156            program: program.clone(),
2157            accesses: accesses.clone(),
2158            tree: None,
2159        };
2160        assert!(not_found.is_missing_program());
2161        assert!(!not_found.is_tracer_failure());
2162        assert_eq!(not_found.accesses(), Some(&accesses));
2163        assert_eq!(not_found.to_string(), "program not found: /bin/missing");
2164
2165        let not_executable = TraceError::ProgramNotExecutable {
2166            program: program.clone(),
2167            source: io::Error::from(io::ErrorKind::PermissionDenied),
2168            accesses: accesses.clone(),
2169            tree: None,
2170        };
2171        assert!(not_executable.is_missing_program());
2172        assert!(!not_executable.is_tracer_failure());
2173
2174        let start_failed = TraceError::StartFailed {
2175            program,
2176            source: io::Error::from(io::ErrorKind::OutOfMemory),
2177            accesses,
2178            tree: None,
2179        };
2180        assert!(!start_failed.is_missing_program());
2181        assert!(!start_failed.is_tracer_failure());
2182        assert!(start_failed.accesses().is_some());
2183
2184        let tracer = TraceError::Tracer {
2185            message: "seccomp filter rejected".to_owned(),
2186            source: None,
2187        };
2188        assert!(tracer.is_tracer_failure());
2189        assert!(!tracer.is_missing_program());
2190        assert_eq!(tracer.accesses(), None);
2191        assert_eq!(
2192            tracer.to_string(),
2193            "tracer failure: seccomp filter rejected"
2194        );
2195    }
2196
2197    /// A request for `/bin/tool` with two arguments.
2198    fn tool_request() -> RunRequest {
2199        RunRequest {
2200            program: path("/bin/tool"),
2201            args: vec![OsString::from("tool"), OsString::from("--flag")],
2202            env: BTreeMap::new(),
2203            cwd: path("/work"),
2204            stdin: None,
2205            capture: CaptureMode::Split,
2206            echo: false,
2207            tree: true,
2208            terminal: false,
2209        }
2210    }
2211
2212    /// Outcomes sort with `ok` first, then the error names in byte order, then
2213    /// `unknown`, and a set keeps each once; they display by name.
2214    #[test]
2215    fn outcomes_sort_and_merge_as_sets() {
2216        let error = |name: &str| Outcome::Error(name.to_owned());
2217        let outcomes: BTreeSet<Outcome> = [
2218            Outcome::Unknown,
2219            error("errno 200"),
2220            error("ERESTART_RESTARTBLOCK"),
2221            error("ENOENT"),
2222            Outcome::Ok,
2223            error("ERESTARTSYS"),
2224            error("EACCES"),
2225            error("ENOENT"),
2226            Outcome::Ok,
2227        ]
2228        .into_iter()
2229        .collect();
2230        let names: Vec<String> = outcomes.iter().map(ToString::to_string).collect();
2231        assert_eq!(names, [
2232            "ok",
2233            "EACCES",
2234            "ENOENT",
2235            "ERESTARTSYS",
2236            "ERESTART_RESTARTBLOCK",
2237            "errno 200",
2238            "unknown"
2239        ]);
2240
2241        let mut observations = Observations::new();
2242        assert!(observations.is_empty());
2243        observations.record(path("/a"), AccessKind::Probe, error("ENOENT"));
2244        observations.record(path("/a"), AccessKind::Probe, Outcome::Ok);
2245        observations.record(path("/a"), AccessKind::Probe, error("ENOENT"));
2246        observations.record_kinds(
2247            path("/a"),
2248            AccessKinds::only(AccessKind::Read).with(AccessKind::Probe),
2249            &Outcome::Unknown,
2250        );
2251        let mut other = Observations::new();
2252        other.record(path("/a"), AccessKind::Read, Outcome::Ok);
2253        other.record_kinds(path("/b"), AccessKinds::EMPTY, &Outcome::Ok);
2254        observations.merge(&other);
2255        let a = observations.get(&path("/a")).unwrap();
2256        assert_eq!(
2257            a.get(&AccessKind::Probe).unwrap(),
2258            &BTreeSet::from([Outcome::Ok, error("ENOENT"), Outcome::Unknown])
2259        );
2260        assert_eq!(
2261            a.get(&AccessKind::Read).unwrap(),
2262            &BTreeSet::from([Outcome::Ok, Outcome::Unknown])
2263        );
2264        assert_eq!(
2265            observations.kinds(&path("/a")),
2266            Some(AccessKinds::only(AccessKind::Read).with(AccessKind::Probe))
2267        );
2268        // A path recorded without kinds is observed, as the combined accesses
2269        // record it.
2270        assert_eq!(observations.kinds(&path("/b")), Some(AccessKinds::EMPTY));
2271        assert_eq!(observations.len(), 2);
2272        assert_eq!(
2273            observations.accesses().get(&path("/b")),
2274            Some(AccessKinds::EMPTY)
2275        );
2276        let order: Vec<String> = (&observations)
2277            .into_iter()
2278            .map(|(path, _)| path.to_string())
2279            .collect();
2280        assert_eq!(order, ["/a", "/b"]);
2281    }
2282
2283    /// The observations of two programs combine into the union of their kinds and,
2284    /// for each kind, of their outcomes; so do their connections and unknown system
2285    /// calls.
2286    #[test]
2287    fn the_observations_of_two_programs_combine() {
2288        let mut shell = Program::new(path("/bin/sh"), vec![OsString::from("sh")], false);
2289        shell
2290            .observations
2291            .record(path("/in"), AccessKind::Read, Outcome::Ok);
2292        shell.observations.record(
2293            path("/missing"),
2294            AccessKind::Probe,
2295            Outcome::Error("ENOENT".to_owned()),
2296        );
2297        shell.unknown_system_calls.insert(400);
2298        let mut inherited = Program::new(path("/bin/sh"), vec![OsString::from("sh")], true);
2299        assert!(inherited.is_empty());
2300        inherited
2301            .observations
2302            .record(path("/in"), AccessKind::Write, Outcome::Ok);
2303        inherited
2304            .observations
2305            .record(path("/missing"), AccessKind::Probe, Outcome::Unknown);
2306        inherited
2307            .connections
2308            .insert(Connection::UnixAbstract(b"kizz".to_vec()));
2309        assert!(!inherited.is_empty());
2310        let mut cat = Program::new(path("/bin/cat"), vec![OsString::from("cat")], false);
2311        cat.observations
2312            .record(path("/other"), AccessKind::Read, Outcome::Ok);
2313        cat.incomplete.push(IncompleteReason::Other {
2314            detail: "lost".to_owned(),
2315        });
2316        let tree = ProcessTree {
2317            processes: vec![
2318                Process {
2319                    number: 1,
2320                    pid: Some(10),
2321                    parent: None,
2322                    programs: vec![shell],
2323                    status: Some(Termination::Exited(0)),
2324                },
2325                Process {
2326                    number: 2,
2327                    pid: Some(11),
2328                    parent: Some(1),
2329                    programs: vec![inherited, cat],
2330                    status: Some(Termination::Signaled(9)),
2331                },
2332            ],
2333        };
2334        let combined = tree.observations();
2335        assert_eq!(
2336            combined.kinds(&path("/in")),
2337            Some(AccessKinds::only(AccessKind::Read).with(AccessKind::Write))
2338        );
2339        assert_eq!(
2340            combined
2341                .get(&path("/missing"))
2342                .and_then(|kinds| kinds.get(&AccessKind::Probe)),
2343            Some(&BTreeSet::from([
2344                Outcome::Error("ENOENT".to_owned()),
2345                Outcome::Unknown
2346            ]))
2347        );
2348        assert_eq!(combined.len(), 3);
2349        let mut expected = Accesses::new();
2350        expected.record(path("/in"), AccessKind::Read);
2351        expected.record(path("/in"), AccessKind::Write);
2352        expected.record(path("/missing"), AccessKind::Probe);
2353        expected.record(path("/other"), AccessKind::Read);
2354        assert_eq!(tree.accesses(), expected);
2355        assert_eq!(tree.unknown_system_calls(), BTreeSet::from([400]));
2356        assert_eq!(
2357            tree.connections(),
2358            BTreeSet::from([Connection::UnixAbstract(b"kizz".to_vec())])
2359        );
2360        assert_eq!(tree.programs().count(), 3);
2361        assert_eq!(tree.process(2).map(|process| process.parent), Some(Some(1)));
2362        assert!(tree.process(3).is_none());
2363    }
2364
2365    /// The helper's tree of one process combines to exactly the accesses it was
2366    /// given, each with `ok`, under the request's program and arguments.
2367    #[test]
2368    fn the_helper_tree_combines_to_its_accesses() {
2369        let request = tool_request();
2370        let mut accesses = Accesses::new();
2371        accesses.record(path("/bin/tool"), AccessKind::Exec);
2372        accesses.record(path("/work/in"), AccessKind::Read);
2373        accesses.record(path("/work/in"), AccessKind::Probe);
2374        accesses.record(path("/work/out"), AccessKind::Write);
2375        let tree = ProcessTree::of_request(&request, &accesses, Some(Termination::Exited(3)));
2376        assert_eq!(tree.accesses(), accesses);
2377        let [process] = tree.processes.as_slice() else {
2378            panic!("expected one process, got {tree:?}");
2379        };
2380        assert_eq!(
2381            (process.number, process.pid, process.parent, process.status),
2382            (1, None, None, Some(Termination::Exited(3)))
2383        );
2384        let [program] = process.programs.as_slice() else {
2385            panic!("expected one program, got {process:?}");
2386        };
2387        assert_eq!(program.path, request.program);
2388        assert_eq!(program.args, request.args);
2389        assert!(!program.inherited);
2390        for (_, kinds) in &program.observations {
2391            for outcomes in kinds.values() {
2392                assert_eq!(outcomes, &BTreeSet::from([Outcome::Ok]));
2393            }
2394        }
2395        let empty = ProcessTree::of_request(&request, &Accesses::new(), None);
2396        assert!(empty.accesses().is_empty());
2397        assert_eq!(empty.process(1).map(|process| process.status), Some(None));
2398    }
2399
2400    /// The tree that the helper builds from a whole run holds the run's reason,
2401    /// unknown system calls and connections on its one program, so its unknown
2402    /// system calls and connections equal the run's, and its observations combine
2403    /// to the run's accesses, each with `ok`; a run without them gives the tree of
2404    /// `of_request`.
2405    #[test]
2406    fn the_helper_tree_of_a_run_holds_what_the_run_reports() {
2407        let request = tool_request();
2408        let mut accesses = Accesses::new();
2409        accesses.record(path("/bin/tool"), AccessKind::Exec);
2410        accesses.record(path("/work/in"), AccessKind::Read);
2411        accesses.record(path("/work/out"), AccessKind::Write);
2412        let reason = IncompleteReason::Other {
2413            detail: "the tracer lost a process".to_owned(),
2414        };
2415        let connections = BTreeSet::from([
2416            Connection::Ip("127.0.0.1:80".parse().unwrap()),
2417            Connection::UnixAbstract(b"kizz".to_vec()),
2418        ]);
2419        let result = RunResult {
2420            termination: Termination::Exited(4),
2421            output: CapturedOutput::empty(CaptureMode::Split),
2422            accesses: accesses.clone(),
2423            incomplete: Some(reason.clone()),
2424            first_reads: FirstReads::new(),
2425            unknown_system_calls: BTreeSet::from([400, 1_000_000]),
2426            connections: connections.clone(),
2427            tree: None,
2428        };
2429        let tree = ProcessTree::of_run(&request, &result);
2430        assert_eq!(tree.accesses(), accesses);
2431        assert_eq!(tree.unknown_system_calls(), result.unknown_system_calls);
2432        assert_eq!(tree.connections(), connections);
2433        let [process] = tree.processes.as_slice() else {
2434            panic!("expected one process, got {tree:?}");
2435        };
2436        assert_eq!(
2437            (process.number, process.pid, process.parent, process.status),
2438            (1, None, None, Some(Termination::Exited(4)))
2439        );
2440        let [program] = process.programs.as_slice() else {
2441            panic!("expected one program, got {process:?}");
2442        };
2443        assert_eq!(program.incomplete, vec![reason]);
2444        for (_, kinds) in &program.observations {
2445            for outcomes in kinds.values() {
2446                assert_eq!(outcomes, &BTreeSet::from([Outcome::Ok]));
2447            }
2448        }
2449        let plain = RunResult {
2450            incomplete: None,
2451            unknown_system_calls: BTreeSet::new(),
2452            connections: BTreeSet::new(),
2453            ..result
2454        };
2455        assert_eq!(
2456            ProcessTree::of_run(&request, &plain),
2457            ProcessTree::of_request(&request, &accesses, Some(Termination::Exited(4)))
2458        );
2459    }
2460
2461    /// A tracer that runs nothing and implements only the required methods, so the
2462    /// error-name query gives its default answer.
2463    struct Unnamed;
2464
2465    impl Tracer for Unnamed {
2466        fn run(
2467            &self,
2468            _request: &RunRequest,
2469            _echo: &dyn EchoSink,
2470            _cancel: &Cancellation,
2471        ) -> Result<RunResult, TraceError> {
2472            Err(TraceError::Tracer {
2473                message: "the test tracer runs nothing".to_owned(),
2474                source: None,
2475            })
2476        }
2477
2478        fn extended_attributes(
2479            &self,
2480            _path: &Path,
2481            _follow: bool,
2482        ) -> io::Result<ExtendedAttributes> {
2483            Ok(ExtendedAttributes::new())
2484        }
2485
2486        fn machine_state(
2487            &self,
2488            _cwd: &Path,
2489        ) -> MachineState {
2490            MachineState::default()
2491        }
2492    }
2493
2494    /// The default error name is `errno` and the number.
2495    #[test]
2496    fn the_default_error_name_is_errno_and_the_number() {
2497        assert_eq!(Unnamed.error_name(2), "errno 2");
2498        assert_eq!(Unnamed.error_name(200), "errno 200");
2499        assert_eq!(Unnamed.error_name(-1), "errno -1");
2500        assert_eq!(unnamed_error(512), "errno 512");
2501    }
2502
2503    /// A failed start carries the tree of its one process when it has one, and a
2504    /// failure of the tracer has none.
2505    #[test]
2506    fn failed_starts_carry_their_tree() {
2507        let request = tool_request();
2508        let mut accesses = Accesses::new();
2509        accesses.record(request.program.clone(), AccessKind::Probe);
2510        let tree = ProcessTree::of_request(&request, &accesses, None);
2511        let not_found = TraceError::ProgramNotFound {
2512            program: request.program.clone(),
2513            accesses: accesses.clone(),
2514            tree: Some(tree.clone()),
2515        };
2516        assert_eq!(not_found.tree(), Some(&tree));
2517        let not_executable = TraceError::ProgramNotExecutable {
2518            program: request.program.clone(),
2519            source: io::Error::from(io::ErrorKind::PermissionDenied),
2520            accesses: accesses.clone(),
2521            tree: Some(tree.clone()),
2522        };
2523        assert_eq!(not_executable.tree(), Some(&tree));
2524        let start_failed = TraceError::StartFailed {
2525            program: request.program,
2526            source: io::Error::from(io::ErrorKind::OutOfMemory),
2527            accesses,
2528            tree: None,
2529        };
2530        assert_eq!(start_failed.tree(), None);
2531        let tracer = TraceError::Tracer {
2532            message: "failed".to_owned(),
2533            source: None,
2534        };
2535        assert_eq!(tracer.tree(), None);
2536    }
2537}