Skip to main content

kizz_store/
step.rs

1// Copyright (c) 2026 Sakura Industries LLC.
2//
3// SPDX-License-Identifier: AGPL-3.0-only
4
5//! The contents of step records.
6//!
7//! A [`StepRecord`] holds what kizz knows about one run of a step: the full step
8//! specification, every [`Observation`] with its recorded [`PathState`], how the
9//! command ended, its raw captured output, how long it ran, when it ran, why it
10//! ran, and the tasks that own it.
11//!
12//! Every type here is encoded by the rules of "Step keys": definite lengths, fields
13//! in a fixed order, and maps sorted by key. Paths and names are byte strings, so
14//! paths that are not UTF-8 survive unchanged.
15
16use std::{
17    collections::{BTreeMap, BTreeSet},
18    fmt,
19    path::{Path, PathBuf},
20};
21
22use minicbor::{Decode, Decoder, Encode, Encoder, bytes::ByteArray, decode, encode};
23
24use crate::{
25    machine::{MachineChange, MachineStateRecord},
26    records::{Family, Record, StepKey, TaskId},
27};
28
29/// Encodes and decodes a path as a CBOR byte string of its bytes.
30pub(crate) mod path_bytes {
31    use std::{
32        ffi::OsStr,
33        os::unix::ffi::OsStrExt as _,
34        path::{Path, PathBuf},
35    };
36
37    use minicbor::{Decoder, Encoder, decode::Error as DecodeError, encode::Error as EncodeError};
38
39    /// Encodes `path` as a byte string.
40    pub fn encode<C, W: minicbor::encode::Write, P: AsRef<Path>>(
41        path: &P,
42        e: &mut Encoder<W>,
43        _ctx: &mut C,
44    ) -> Result<(), EncodeError<W::Error>> {
45        e.bytes(path.as_ref().as_os_str().as_bytes())?.ok()
46    }
47
48    /// Decodes a path from a byte string.
49    pub fn decode<C>(
50        d: &mut Decoder<'_>,
51        _ctx: &mut C,
52    ) -> Result<PathBuf, DecodeError> {
53        Ok(PathBuf::from(OsStr::from_bytes(d.bytes()?)))
54    }
55}
56
57/// Encodes and decodes a list of paths as a definite-length CBOR array of byte
58/// strings, one per path.
59pub(crate) mod path_list {
60    use std::{ffi::OsStr, os::unix::ffi::OsStrExt as _, path::PathBuf};
61
62    use minicbor::{Decoder, Encoder, decode::Error as DecodeError, encode::Error as EncodeError};
63
64    /// Encodes `paths` as an array of byte strings.
65    pub fn encode<C, W: minicbor::encode::Write, P: AsRef<[PathBuf]>>(
66        paths: &P,
67        e: &mut Encoder<W>,
68        _ctx: &mut C,
69    ) -> Result<(), EncodeError<W::Error>> {
70        let paths = paths.as_ref();
71        e.array(u64::try_from(paths.len()).unwrap_or(u64::MAX))?;
72        for path in paths {
73            e.bytes(path.as_os_str().as_bytes())?;
74        }
75        Ok(())
76    }
77
78    /// Decodes a list of paths from an array of byte strings.
79    pub fn decode<C>(
80        d: &mut Decoder<'_>,
81        _ctx: &mut C,
82    ) -> Result<Vec<PathBuf>, DecodeError> {
83        let Some(len) = d.array()? else {
84            return Err(DecodeError::message("a path list has a definite length"));
85        };
86        let mut paths = Vec::new();
87        for _ in 0..len {
88            paths.push(PathBuf::from(OsStr::from_bytes(d.bytes()?)));
89        }
90        Ok(paths)
91    }
92}
93
94/// A BLAKE3 hash: of a file's content, of a directory's entries, or of a task
95/// program.
96#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
97pub struct ContentHash(pub [u8; 32]);
98
99impl fmt::Display for ContentHash {
100    fn fmt(
101        &self,
102        f: &mut fmt::Formatter<'_>,
103    ) -> fmt::Result {
104        for byte in self.0 {
105            write!(f, "{byte:02x}")?;
106        }
107        Ok(())
108    }
109}
110
111impl<C> Encode<C> for ContentHash {
112    fn encode<W: encode::Write>(
113        &self,
114        e: &mut Encoder<W>,
115        _ctx: &mut C,
116    ) -> Result<(), encode::Error<W::Error>> {
117        e.bytes(&self.0)?.ok()
118    }
119}
120
121impl<'b, C> Decode<'b, C> for ContentHash {
122    fn decode(
123        d: &mut Decoder<'b>,
124        ctx: &mut C,
125    ) -> Result<Self, decode::Error> {
126        ByteArray::<32>::decode(d, ctx).map(|bytes| Self(bytes.into()))
127    }
128}
129
130/// How a step captured its output, as its specification gave it.
131#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Encode, Decode)]
132#[cbor(index_only)]
133pub enum Capture {
134    /// Standard output and standard error separately.
135    #[n(0)]
136    Split,
137    /// Both streams through one pipe, in exact order.
138    #[n(1)]
139    Merged,
140}
141
142/// The full specification of a step, as its `run()` call gave it, with the values
143/// that place it in its task: the task program hash and the occurrence number.
144#[derive(Debug, Clone, PartialEq, Eq, Encode, Decode)]
145#[allow(
146    clippy::struct_excessive_bools,
147    reason = "independent command options mirror the Starlark API"
148)]
149pub struct StepSpecRecord {
150    /// The hash of the task program: its block and every module it loads.
151    #[n(0)]
152    pub program_hash: ContentHash,
153    /// The absolute working directory.
154    #[cbor(n(1), with = "path_bytes")]
155    pub cwd: PathBuf,
156    /// The argument vector as run: the program, then its arguments, each string as
157    /// written, after the expansion of any lists and tuples.
158    #[n(2)]
159    pub argv: Vec<String>,
160    /// The exact environment passed to the process, sorted by name.
161    #[n(3)]
162    pub env: BTreeMap<String, String>,
163    /// The text for standard input, or `None` for `/dev/null`.
164    #[n(4)]
165    pub stdin: Option<String>,
166    /// How the output was captured.
167    #[n(5)]
168    pub capture: Capture,
169    /// Whether output was also echoed live.
170    #[n(6)]
171    pub stream: bool,
172    /// Whether the step runs on every build.
173    #[n(7)]
174    pub always: bool,
175    /// The ignore patterns, as written.
176    #[n(8)]
177    pub ignore: Vec<String>,
178    /// The `track` patterns, as written.
179    #[n(9)]
180    pub track: Vec<String>,
181    /// The acceptable exit codes, or `None` when the exit status never fails the
182    /// task.
183    #[n(10)]
184    pub expect: Option<Vec<i32>>,
185    /// The number of identical commands earlier in the same task run.
186    #[n(11)]
187    pub occurrence: u32,
188    /// Whether a different modification or change time of a file or directory that
189    /// the step read, ran, listed, or checked is a change.
190    #[n(12)]
191    pub timestamps: bool,
192    /// The names of the parts of the machine state that count as an input of the
193    /// step, as `run(..., machine = [...])` gave them, sorted and without repeats.
194    #[n(13)]
195    pub machine: Vec<String>,
196    /// Whether dependency tracing was explicitly disabled. Such steps are never cache
197    /// hits.
198    #[n(14)]
199    pub untraced: bool,
200}
201
202/// The combined kinds of access a step made to one path, one bit per kind.
203///
204/// The bits follow the order of the tracer interface's access kinds: read, probe,
205/// list, write, exec, xattr.
206#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Default, Encode, Decode)]
207#[cbor(transparent)]
208pub struct AccessBits(#[n(0)] pub u8);
209
210impl AccessBits {
211    /// The path was run as a program.
212    pub const EXEC: u8 = 0b0001_0000;
213    /// A directory's entries were read.
214    pub const LIST: u8 = 0b0000_0100;
215    /// Existence or metadata was checked, including a lookup that found nothing.
216    pub const PROBE: u8 = 0b0000_0010;
217    /// Content was read.
218    pub const READ: u8 = 0b0000_0001;
219    /// The path was created, modified, renamed, removed, or had its metadata changed.
220    pub const WRITE: u8 = 0b0000_1000;
221    /// The path's extended attributes were read or listed.
222    pub const XATTR: u8 = 0b0010_0000;
223
224    /// Whether every bit of `bit` is set.
225    #[must_use]
226    pub const fn contains(
227        self,
228        bit: u8,
229    ) -> bool {
230        self.0 & bit == bit
231    }
232}
233
234/// The permission bits of a mode: the low twelve bits, the set-user-ID,
235/// set-group-ID, and sticky bits included.
236pub const PERMISSION_BITS: u32 = 0o7777;
237
238/// The permission bits of `mode`, without its file type.
239#[must_use]
240pub const fn permission_bits(mode: u32) -> u32 {
241    mode & PERMISSION_BITS
242}
243
244/// The owner of a file or directory: its user and group numbers.
245#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Encode, Decode)]
246pub struct Owner {
247    /// The user number.
248    #[n(0)]
249    pub uid: u32,
250    /// The group number.
251    #[n(1)]
252    pub gid: u32,
253}
254
255impl fmt::Display for Owner {
256    fn fmt(
257        &self,
258        f: &mut fmt::Formatter<'_>,
259    ) -> fmt::Result {
260        write!(f, "{}:{}", self.uid, self.gid)
261    }
262}
263
264/// The modification and change times of a regular file or a directory, in
265/// nanoseconds since the Unix epoch. Access times are never recorded.
266#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Encode, Decode)]
267pub struct Times {
268    /// The modification time.
269    #[n(0)]
270    pub mtime_nanos: i64,
271    /// The change time.
272    #[n(1)]
273    pub ctime_nanos: i64,
274}
275
276/// Write a time in nanoseconds since the Unix epoch as seconds with nine decimals.
277fn write_time(
278    f: &mut fmt::Formatter<'_>,
279    nanos: i64,
280) -> fmt::Result {
281    let sign = if nanos < 0 { "-" } else { "" };
282    let magnitude = nanos.unsigned_abs();
283    write!(
284        f,
285        "{sign}{}.{:09}",
286        magnitude / 1_000_000_000,
287        magnitude % 1_000_000_000
288    )
289}
290
291/// The metadata of a regular file that a cache check compares.
292#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Encode, Decode)]
293pub struct FileMeta {
294    /// The size in bytes.
295    #[n(0)]
296    pub size: u64,
297    /// The modification time, in nanoseconds since the Unix epoch.
298    #[n(1)]
299    pub mtime_nanos: i64,
300    /// The change time, in nanoseconds since the Unix epoch.
301    #[n(2)]
302    pub ctime_nanos: i64,
303    /// The inode number.
304    #[n(3)]
305    pub inode: u64,
306    /// The device number.
307    #[n(4)]
308    pub device: u64,
309    /// The mode: the file type and permission bits.
310    #[n(5)]
311    pub mode: u32,
312    /// The owner.
313    #[n(6)]
314    pub owner: Owner,
315}
316
317impl FileMeta {
318    /// The modification and change times.
319    #[must_use]
320    pub const fn times(&self) -> Times {
321        Times {
322            mtime_nanos: self.mtime_nanos,
323            ctime_nanos: self.ctime_nanos,
324        }
325    }
326}
327
328/// The type of a directory entry, as the listing reports it, without following
329/// symbolic links.
330#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Encode, Decode)]
331#[cbor(index_only)]
332pub enum EntryKind {
333    /// A regular file.
334    #[n(0)]
335    File,
336    /// A directory.
337    #[n(1)]
338    Directory,
339    /// A symbolic link.
340    #[n(2)]
341    Symlink,
342    /// A block device.
343    #[n(3)]
344    BlockDevice,
345    /// A character device.
346    #[n(4)]
347    CharDevice,
348    /// A FIFO.
349    #[n(5)]
350    Fifo,
351    /// A socket.
352    #[n(6)]
353    Socket,
354    /// A type the listing could not determine.
355    #[n(7)]
356    Unknown,
357}
358
359impl EntryKind {
360    /// The byte that stands for this kind in a listing hash.
361    #[must_use]
362    pub const fn code(self) -> u8 {
363        match self {
364            Self::File => 0,
365            Self::Directory => 1,
366            Self::Symlink => 2,
367            Self::BlockDevice => 3,
368            Self::CharDevice => 4,
369            Self::Fifo => 5,
370            Self::Socket => 6,
371            Self::Unknown => 7,
372        }
373    }
374}
375
376/// One entry of a listed directory.
377#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Encode, Decode)]
378pub struct DirEntry {
379    /// The entry's name, as bytes.
380    #[cbor(n(0), with = "minicbor::bytes")]
381    pub name: Vec<u8>,
382    /// The entry's type.
383    #[n(1)]
384    pub kind: EntryKind,
385}
386
387/// The recorded contents of a listed directory, in the order the file system
388/// returned its entries when kizz read it. Entry inode numbers are not recorded.
389#[derive(Debug, Clone, PartialEq, Eq, Encode, Decode)]
390pub struct Listing {
391    /// The hash of the entry names and types, in the order the file system
392    /// returned them.
393    #[n(0)]
394    pub hash: ContentHash,
395    /// The entries, in the order the file system returned them, when there are at
396    /// most [`MAX_LISTED_NAMES`]; `None` above that.
397    #[n(1)]
398    pub entries: Option<Vec<DirEntry>>,
399    /// The hash of the same entries sorted by name and type, which tells a change
400    /// of order alone from a change of entries, in a directory of any size.
401    #[n(2)]
402    pub sorted_hash: ContentHash,
403}
404
405/// The most entries a listed directory may have for its names to be kept.
406pub const MAX_LISTED_NAMES: usize = 1_000;
407
408/// A device, FIFO, or socket, which is recorded by type only.
409#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Encode, Decode)]
410#[cbor(index_only)]
411pub enum SpecialKind {
412    /// A block device.
413    #[n(0)]
414    BlockDevice,
415    /// A character device.
416    #[n(1)]
417    CharDevice,
418    /// A FIFO.
419    #[n(2)]
420    Fifo,
421    /// A socket.
422    #[n(3)]
423    Socket,
424    /// A type that is none of the others.
425    #[n(4)]
426    Other,
427}
428
429/// The state of a touched path when its step finished.
430#[derive(Debug, Clone, PartialEq, Eq, Encode, Decode)]
431pub enum PathState {
432    /// Nothing exists at the path.
433    #[n(0)]
434    Absent,
435    /// A regular file: its metadata, and the hash of its content when it was read
436    /// or run as a program. A file that was only checked or written is never
437    /// hashed.
438    #[n(1)]
439    File {
440        /// The metadata.
441        #[n(0)]
442        meta: FileMeta,
443        /// The hash of the content, when the file was read or run.
444        #[n(1)]
445        hash: Option<ContentHash>,
446    },
447    /// A directory: its mode, owner, and times, and its listing, in the order the
448    /// file system returned its entries, when it was listed.
449    #[n(2)]
450    Directory {
451        /// The mode: the file type and permission bits.
452        #[n(0)]
453        mode: u32,
454        /// The owner.
455        #[n(1)]
456        owner: Owner,
457        /// The listing, when the directory was listed.
458        #[n(2)]
459        listing: Option<Listing>,
460        /// The modification and change times.
461        #[n(3)]
462        times: Times,
463    },
464    /// A symbolic link: its target, and the state of what it points to.
465    #[n(3)]
466    Symlink {
467        /// The link's target, as stored in the link.
468        #[cbor(n(0), with = "path_bytes")]
469        target: PathBuf,
470        /// The state of what the link points to, following every link.
471        #[n(1)]
472        pointee: Box<PathState>,
473    },
474    /// A device, FIFO, or socket: its type only.
475    #[n(4)]
476    Special {
477        /// The type.
478        #[n(0)]
479        kind: SpecialKind,
480    },
481    /// A path under `/proc` or `/sys` that no `track` pattern matched: the access is
482    /// recorded, but its state is not, and it is never compared.
483    #[n(5)]
484    Untracked,
485    /// The path exists but its state could not be read.
486    #[n(6)]
487    Inaccessible {
488        /// The operating system's error number.
489        #[n(0)]
490        errno: i32,
491    },
492}
493
494/// One extended attribute of a path: its name, and a BLAKE3 hash of its value.
495#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Encode, Decode)]
496pub struct Attribute {
497    /// The attribute's name, as bytes, such as `user.origin`.
498    #[cbor(n(0), with = "minicbor::bytes")]
499    pub name: Vec<u8>,
500    /// The BLAKE3 hash of the attribute's value.
501    #[n(1)]
502    pub hash: ContentHash,
503}
504
505/// The extended attributes recorded with a path whose attributes a step read or
506/// listed: those of the path itself and, for a symbolic link, those of what it
507/// points to, each sorted by name. A file system without attributes records none.
508#[derive(Debug, Clone, PartialEq, Eq, Hash, Encode, Decode)]
509pub struct Attributes {
510    /// The path's own attributes, without following a final symbolic link, sorted
511    /// by name, or `None` when they could not be read, as when nothing is at the
512    /// path.
513    #[n(0)]
514    pub own: Option<Vec<Attribute>>,
515    /// For a symbolic link, the attributes of what it points to, following every
516    /// link, sorted by name; `None` for a path that is not a symbolic link, or when
517    /// they could not be read, as for a link that points to nothing.
518    #[n(1)]
519    pub pointee: Option<Vec<Attribute>>,
520}
521
522/// One path a step touched, how it touched it, and its state when the step
523/// finished.
524#[derive(Debug, Clone, PartialEq, Eq, Encode, Decode)]
525pub struct Observation {
526    /// The absolute path.
527    #[cbor(n(0), with = "path_bytes")]
528    pub path: PathBuf,
529    /// The combined kinds of access.
530    #[n(1)]
531    pub access: AccessBits,
532    /// Whether the path is under `/proc` or `/sys` and a `track` pattern matched it,
533    /// so its content counts as an input.
534    #[n(2)]
535    pub tracked: bool,
536    /// The state of the path when the step finished.
537    #[n(3)]
538    pub state: PathState,
539    /// The extended attributes of the path when the step finished, part of its
540    /// state, recorded when the step read or listed them (the xattr kind); `None`
541    /// for any other path, and for a path under `/proc` or `/sys` that no `track`
542    /// pattern matched.
543    #[n(4)]
544    pub attributes: Option<Attributes>,
545}
546
547/// How a recorded step ended.
548#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Encode, Decode)]
549pub enum StepExit {
550    /// The command exited with this exit code.
551    #[n(0)]
552    Exited {
553        /// The exit code.
554        #[n(0)]
555        code: i32,
556    },
557    /// A signal with this number killed the command.
558    #[n(1)]
559    Signaled {
560        /// The signal number.
561        #[n(0)]
562        signal: i32,
563    },
564    /// The program was not found, so the command never started.
565    #[n(2)]
566    ProgramNotFound,
567    /// The program exists but is not executable, so the command never started.
568    #[n(3)]
569    ProgramNotExecutable,
570    /// The command could not start, for a reason other than a missing or
571    /// non-executable program, so its result is not cached.
572    #[n(4)]
573    NotStarted,
574}
575
576/// A step's raw captured output, exactly as the command wrote it.
577#[derive(Debug, Clone, PartialEq, Eq, Encode, Decode)]
578pub enum RecordedOutput {
579    /// Standard output and standard error separately.
580    #[n(0)]
581    Split {
582        /// Standard output.
583        #[cbor(n(0), with = "minicbor::bytes")]
584        stdout: Vec<u8>,
585        /// Standard error.
586        #[cbor(n(1), with = "minicbor::bytes")]
587        stderr: Vec<u8>,
588    },
589    /// Both streams, in exact order.
590    #[n(1)]
591    Merged {
592        /// The interleaved output.
593        #[cbor(n(0), with = "minicbor::bytes")]
594        output: Vec<u8>,
595    },
596}
597
598/// What changed about one recorded path, as a cache check found it.
599#[derive(Debug, Clone, PartialEq, Eq, Hash, Encode, Decode)]
600pub enum Change {
601    /// Something exists where nothing did.
602    #[n(0)]
603    Appeared,
604    /// Nothing exists where something did.
605    #[n(1)]
606    Disappeared,
607    /// The type changed, such as a file that became a directory, or the path can or
608    /// can no longer be read.
609    #[n(2)]
610    Type,
611    /// A regular file's or a directory's permission bits changed, found without
612    /// hashing.
613    #[n(8)]
614    Permissions {
615        /// The recorded permission bits.
616        #[n(0)]
617        old: u32,
618        /// The current permission bits.
619        #[n(1)]
620        new: u32,
621    },
622    /// A regular file's or a directory's owner changed, found without hashing.
623    #[n(9)]
624    Owner {
625        /// The recorded owner.
626        #[n(0)]
627        old: Owner,
628        /// The current owner.
629        #[n(1)]
630        new: Owner,
631    },
632    /// A regular file's or a directory's modification or change time changed, found
633    /// without hashing, for a step run with `timestamps`.
634    #[n(10)]
635    Timestamps {
636        /// The recorded times.
637        #[n(0)]
638        old: Times,
639        /// The current times.
640        #[n(1)]
641        new: Times,
642    },
643    /// A regular file's size changed, found without hashing.
644    #[n(3)]
645    Size {
646        /// The recorded size in bytes.
647        #[n(0)]
648        old: u64,
649        /// The current size in bytes.
650        #[n(1)]
651        new: u64,
652    },
653    /// A regular file that was read has the same size and different content, found
654    /// by hashing.
655    #[n(4)]
656    Content,
657    /// A regular file that was not read, and so has no hash, has the same size and
658    /// different metadata.
659    #[n(5)]
660    Metadata,
661    /// The entries of a listed directory changed. The entries that appeared,
662    /// disappeared, or changed type are named when both listings kept their
663    /// entries; otherwise all three lists are empty.
664    #[n(6)]
665    Entries {
666        /// The entries that appeared, sorted by name.
667        #[n(0)]
668        appeared: Vec<DirEntry>,
669        /// The entries that disappeared, as recorded, sorted by name.
670        #[n(1)]
671        disappeared: Vec<DirEntry>,
672        /// The entries whose type changed, with their current type, sorted by name.
673        #[n(2)]
674        retyped: Vec<DirEntry>,
675    },
676    /// A listed directory has the same entries in a different order.
677    #[n(11)]
678    Order,
679    /// The extended attributes of a path whose attributes were recorded changed,
680    /// for the path itself or, for a symbolic link, for what it points to: the
681    /// attributes that appeared, disappeared, or changed value, each sorted by
682    /// name. All three lists are empty when only whether the attributes could be
683    /// read changed.
684    #[n(12)]
685    Attributes {
686        /// The attributes that appeared, with their current hash.
687        #[n(0)]
688        appeared: Vec<Attribute>,
689        /// The attributes that disappeared, as recorded.
690        #[n(1)]
691        disappeared: Vec<Attribute>,
692        /// The attributes whose value changed, with their current hash.
693        #[n(2)]
694        changed: Vec<Attribute>,
695    },
696    /// A symbolic link points somewhere else.
697    #[n(7)]
698    LinkTarget {
699        /// The recorded target.
700        #[cbor(n(0), with = "path_bytes")]
701        old: PathBuf,
702        /// The current target.
703        #[cbor(n(1), with = "path_bytes")]
704        new: PathBuf,
705    },
706}
707
708impl fmt::Display for Change {
709    fn fmt(
710        &self,
711        f: &mut fmt::Formatter<'_>,
712    ) -> fmt::Result {
713        match self {
714            Self::Appeared => f.write_str("appeared"),
715            Self::Disappeared => f.write_str("disappeared"),
716            Self::Type => f.write_str("type changed"),
717            Self::Permissions { old, new } => {
718                write!(f, "permissions changed from {old:04o} to {new:04o}")
719            },
720            Self::Owner { old, new } => write!(f, "owner changed from {old} to {new}"),
721            Self::Timestamps { old, new } => write_timestamps(f, old, new),
722            Self::Size { old, new } => write!(f, "size changed from {old} to {new} bytes"),
723            Self::Content => f.write_str("content changed"),
724            Self::Metadata => f.write_str("metadata changed"),
725            Self::Entries {
726                appeared,
727                disappeared,
728                retyped,
729            } => write_entries(f, appeared, disappeared, retyped),
730            Self::Order => f.write_str("the order of its entries changed"),
731            Self::Attributes {
732                appeared,
733                disappeared,
734                changed,
735            } => write_attributes(f, appeared, disappeared, changed),
736            Self::LinkTarget { old, new } => {
737                write!(
738                    f,
739                    "link target changed from {} to {}",
740                    old.display(),
741                    new.display()
742                )
743            },
744        }
745    }
746}
747
748/// The most entry names an entries change shows for each of appeared,
749/// disappeared, and changed type; the rest are counted.
750const SHOWN_ENTRY_NAMES: usize = 10;
751
752/// Write an entries change: the entries that appeared, disappeared, and changed
753/// type, each group when it is not empty, with at most [`SHOWN_ENTRY_NAMES`] names
754/// each.
755fn write_entries(
756    f: &mut fmt::Formatter<'_>,
757    appeared: &[DirEntry],
758    disappeared: &[DirEntry],
759    retyped: &[DirEntry],
760) -> fmt::Result {
761    f.write_str("directory entries changed")?;
762    let mut separator = ": ";
763    for (entries, what) in [
764        (appeared, "appeared"),
765        (disappeared, "disappeared"),
766        (retyped, "changed type"),
767    ] {
768        if entries.is_empty() {
769            continue;
770        }
771        f.write_str(separator)?;
772        separator = "; ";
773        for (index, entry) in entries.iter().take(SHOWN_ENTRY_NAMES).enumerate() {
774            if index > 0 {
775                f.write_str(", ")?;
776            }
777            write!(f, "`{}`", String::from_utf8_lossy(&entry.name))?;
778        }
779        let more = entries.len().saturating_sub(SHOWN_ENTRY_NAMES);
780        if more > 0 {
781            write!(f, " and {more} more")?;
782        }
783        write!(f, " {what}")?;
784    }
785    Ok(())
786}
787
788/// Write an extended-attribute change: the attributes that appeared, disappeared,
789/// and changed value, each group when it is not empty, with at most
790/// [`SHOWN_ENTRY_NAMES`] names each.
791fn write_attributes(
792    f: &mut fmt::Formatter<'_>,
793    appeared: &[Attribute],
794    disappeared: &[Attribute],
795    changed: &[Attribute],
796) -> fmt::Result {
797    f.write_str("extended attributes changed")?;
798    let mut separator = ": ";
799    for (attributes, what) in [
800        (appeared, "appeared"),
801        (disappeared, "disappeared"),
802        (changed, "changed"),
803    ] {
804        if attributes.is_empty() {
805            continue;
806        }
807        f.write_str(separator)?;
808        separator = "; ";
809        for (index, attribute) in attributes.iter().take(SHOWN_ENTRY_NAMES).enumerate() {
810            if index > 0 {
811                f.write_str(", ")?;
812            }
813            write!(f, "`{}`", String::from_utf8_lossy(&attribute.name))?;
814        }
815        let more = attributes.len().saturating_sub(SHOWN_ENTRY_NAMES);
816        if more > 0 {
817            write!(f, " and {more} more")?;
818        }
819        write!(f, " {what}")?;
820    }
821    Ok(())
822}
823
824/// Write a timestamp change: each time that differs, old and new, or both times
825/// when neither differs.
826fn write_timestamps(
827    f: &mut fmt::Formatter<'_>,
828    old: &Times,
829    new: &Times,
830) -> fmt::Result {
831    let mtime = old.mtime_nanos != new.mtime_nanos;
832    let ctime = old.ctime_nanos != new.ctime_nanos;
833    f.write_str("timestamps changed: ")?;
834    if mtime || !ctime {
835        f.write_str("modification time from ")?;
836        write_time(f, old.mtime_nanos)?;
837        f.write_str(" to ")?;
838        write_time(f, new.mtime_nanos)?;
839    }
840    if mtime && ctime {
841        f.write_str(", ")?;
842    }
843    if ctime || !mtime {
844        f.write_str("change time from ")?;
845        write_time(f, old.ctime_nanos)?;
846        f.write_str(" to ")?;
847        write_time(f, new.ctime_nanos)?;
848    }
849    Ok(())
850}
851
852/// One recorded path that a cache check found changed.
853#[derive(Debug, Clone, PartialEq, Eq, Hash, Encode, Decode)]
854pub struct Difference {
855    /// The absolute path.
856    #[cbor(n(0), with = "path_bytes")]
857    pub path: PathBuf,
858    /// What changed about it.
859    #[n(1)]
860    pub change: Change,
861}
862
863impl fmt::Display for Difference {
864    fn fmt(
865        &self,
866        f: &mut fmt::Formatter<'_>,
867    ) -> fmt::Result {
868        write!(f, "{}: {}", self.path.display(), self.change)
869    }
870}
871
872/// A file that changed during a run after the command first read it or ran it.
873#[derive(Debug, Clone, PartialEq, Eq, Hash, Encode, Decode)]
874pub struct ChangedRead {
875    /// The absolute path that the command read or ran.
876    #[cbor(n(0), with = "path_bytes")]
877    pub path: PathBuf,
878    /// Whether the command wrote the path, as its access kinds show; when it did
879    /// not, something else changed the file while the command ran.
880    #[n(1)]
881    pub written: bool,
882}
883
884impl ChangedRead {
885    /// Who changed the file, as explanations say it.
886    #[must_use]
887    pub const fn changed_by(&self) -> &'static str {
888        if self.written {
889            "the command wrote it"
890        } else {
891            "something else changed it while the command ran"
892        }
893    }
894}
895
896/// The reason for files that changed during a run after the command first read
897/// them, with each path shown by `path`: how many files changed, then each file
898/// with who changed it, such as `a file changed after the command read it: in.txt
899/// (the command wrote it)`.
900#[must_use]
901pub fn changed_reads_text(
902    files: &[ChangedRead],
903    path: impl Fn(&Path) -> String,
904) -> String {
905    let shown: Vec<String> = files
906        .iter()
907        .map(|file| format!("{} ({})", path(&file.path), file.changed_by()))
908        .collect();
909    let head = if files.len() == 1 {
910        "a file changed after the command read it".to_owned()
911    } else {
912        format!("{} files changed after the command read them", files.len())
913    };
914    format!("{head}: {}", shown.join(", "))
915}
916
917/// The numbers of system calls that the tracer does not know, as text: `system
918/// call 400`, or `system calls 400 and 1000000` for several, in the order given.
919#[must_use]
920pub fn system_call_numbers(numbers: &[u32]) -> String {
921    let shown: Vec<String> = numbers.iter().map(ToString::to_string).collect();
922    match shown.split_last() {
923        None => "no system call".to_owned(),
924        Some((only, [])) => format!("system call {only}"),
925        Some((last, rest)) => format!("system calls {} and {last}", rest.join(", ")),
926    }
927}
928
929/// A connection that a command made to a service outside the trace: an IPv4 or
930/// IPv6 address and port, or a Unix socket by path or abstract name. What came back
931/// is an input that kizz cannot see, so it warns about the connection, and the
932/// result is still cached.
933///
934/// Connections are ordered by their kind, then by address or path, as a record
935/// keeps them: sorted and without repeats.
936#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Encode, Decode)]
937pub enum Connection {
938    /// An IPv4 address and port.
939    #[n(0)]
940    Ipv4 {
941        /// The four bytes of the address, in network order.
942        #[cbor(n(0), with = "minicbor::bytes")]
943        address: [u8; 4],
944        /// The port.
945        #[n(1)]
946        port: u16,
947    },
948    /// An IPv6 address and port, with the scope of the address, 0 for none.
949    #[n(1)]
950    Ipv6 {
951        /// The sixteen bytes of the address, in network order.
952        #[cbor(n(0), with = "minicbor::bytes")]
953        address: [u8; 16],
954        /// The port.
955        #[n(1)]
956        port: u16,
957        /// The scope of the address, such as the index of a network interface.
958        #[n(2)]
959        scope: u32,
960    },
961    /// A Unix socket by its absolute path.
962    #[n(2)]
963    UnixPath {
964        /// The absolute path.
965        #[cbor(n(0), with = "path_bytes")]
966        path: PathBuf,
967    },
968    /// A Unix socket in the abstract namespace, by its name without the zero byte
969    /// that starts it.
970    #[n(3)]
971    UnixAbstract {
972        /// The name, which may hold more zero bytes.
973        #[cbor(n(0), with = "minicbor::bytes")]
974        name: Vec<u8>,
975    },
976}
977
978impl Connection {
979    /// The connection as text, with a Unix socket's path shown by `path`: an
980    /// address with its port, such as `127.0.0.1:80` or `[fe80::1%2]:80`;
981    /// `Unix socket PATH`; or `abstract Unix socket @NAME`, with each byte of the
982    /// name that is not printable ASCII escaped, such as `\x00`.
983    #[must_use]
984    pub fn text(
985        &self,
986        path: impl Fn(&Path) -> String,
987    ) -> String {
988        match self {
989            Self::Ipv4 { address, port } => {
990                std::net::SocketAddrV4::new((*address).into(), *port).to_string()
991            },
992            Self::Ipv6 {
993                address,
994                port,
995                scope,
996            } => std::net::SocketAddrV6::new((*address).into(), *port, 0, *scope).to_string(),
997            Self::UnixPath { path: socket } => format!("Unix socket {}", path(socket.as_path())),
998            Self::UnixAbstract { name } => {
999                format!("abstract Unix socket @{}", name.escape_ascii())
1000            },
1001        }
1002    }
1003}
1004
1005impl fmt::Display for Connection {
1006    fn fmt(
1007        &self,
1008        f: &mut fmt::Formatter<'_>,
1009    ) -> fmt::Result {
1010        f.write_str(&self.text(|path| path.display().to_string()))
1011    }
1012}
1013
1014/// The connections `connections` as text, each shown by [`Connection::text`] with
1015/// `path`, in the order given: `127.0.0.1:80`, `127.0.0.1:80 and Unix socket
1016/// /run/s`, or `a, b and c` for several, and `no connection` for none.
1017#[must_use]
1018pub fn connections_text(
1019    connections: &[Connection],
1020    path: impl Fn(&Path) -> String,
1021) -> String {
1022    let shown: Vec<String> = connections
1023        .iter()
1024        .map(|connection| connection.text(&path))
1025        .collect();
1026    match shown.split_last() {
1027        None => "no connection".to_owned(),
1028        Some((only, [])) => only.clone(),
1029        Some((last, rest)) => format!("{} and {last}", rest.join(", ")),
1030    }
1031}
1032
1033/// Why the result of a run was not cached.
1034#[derive(Debug, Clone, PartialEq, Eq, Hash, Encode, Decode)]
1035pub enum NotCachedReason {
1036    /// A signal killed the command.
1037    #[n(0)]
1038    Signaled {
1039        /// The signal number.
1040        #[n(0)]
1041        signal: i32,
1042    },
1043    /// The build was interrupted, and a signal stopped the command.
1044    #[n(1)]
1045    Interrupted {
1046        /// The signal number.
1047        #[n(0)]
1048        signal: i32,
1049    },
1050    /// The tracer could not observe every access of the run.
1051    #[n(2)]
1052    Incomplete {
1053        /// What the tracer could not observe.
1054        #[n(0)]
1055        detail: String,
1056    },
1057    /// The command could not start, for a reason other than a missing or
1058    /// non-executable program.
1059    #[n(3)]
1060    StartFailed {
1061        /// The error that starting the command reported.
1062        #[n(0)]
1063        message: String,
1064    },
1065    /// The build was interrupted, and the command exited with a code that it chose,
1066    /// for example after it handled the interrupt.
1067    #[n(4)]
1068    InterruptedExited {
1069        /// The exit code.
1070        #[n(0)]
1071        code: i32,
1072    },
1073    /// Files changed during the run after the command first read them or ran them,
1074    /// so the recorded states may not be what the command consumed.
1075    #[n(5)]
1076    ChangedAfterRead {
1077        /// Each changed file, sorted by path.
1078        #[n(0)]
1079        files: Vec<ChangedRead>,
1080    },
1081    /// The command made system calls that the tracer does not know, and the build
1082    /// did not ask to cache such results with `kizz build --cache-unknown-syscalls`.
1083    #[n(6)]
1084    UnknownSystemCalls {
1085        /// The number of each such call, as the tracer's filter saw it, sorted and
1086        /// without repeats.
1087        #[n(0)]
1088        numbers: Vec<u32>,
1089    },
1090}
1091
1092impl fmt::Display for NotCachedReason {
1093    fn fmt(
1094        &self,
1095        f: &mut fmt::Formatter<'_>,
1096    ) -> fmt::Result {
1097        match self {
1098            Self::Signaled { signal } => write!(f, "killed by signal {signal}"),
1099            Self::Interrupted { signal } => {
1100                write!(f, "interrupted, and stopped by signal {signal}")
1101            },
1102            Self::InterruptedExited { code } => {
1103                write!(f, "interrupted, and exited with code {code}")
1104            },
1105            Self::Incomplete { detail } => write!(f, "incompletely traced: {detail}"),
1106            Self::StartFailed { message } => write!(f, "could not start: {message}"),
1107            Self::ChangedAfterRead { files } => {
1108                f.write_str(&changed_reads_text(files, |path| {
1109                    path.display().to_string()
1110                }))
1111            },
1112            Self::UnknownSystemCalls { numbers } => {
1113                write!(
1114                    f,
1115                    "the command made {}, which the tracer does not know",
1116                    system_call_numbers(numbers)
1117                )
1118            },
1119        }
1120    }
1121}
1122
1123/// Why a step ran.
1124///
1125/// The explanations add the reasons that compare a step's specification with the
1126/// one its task used last time at the same position.
1127#[derive(Debug, Clone, PartialEq, Eq, Hash, Encode, Decode)]
1128pub enum RunReason {
1129    /// There was no record for the step key: the step never ran with this exact
1130    /// specification.
1131    #[n(0)]
1132    NeverRun,
1133    /// The step is marked `always`, and this was its one run in the build.
1134    #[n(1)]
1135    Always,
1136    /// A record existed, and the cache check found these recorded paths changed,
1137    /// or these values of the machine state that the step names.
1138    #[n(2)]
1139    InputsChanged {
1140        /// Every difference, sorted by path.
1141        #[n(0)]
1142        differences: Vec<Difference>,
1143        /// Every value of the machine state that the step names and that changed, in
1144        /// the order of the step's names; empty when the check compared none, or
1145        /// none changed.
1146        #[n(1)]
1147        machine: Vec<MachineChange>,
1148    },
1149    /// The step's previous run could not be cached, and the cache check found these
1150    /// paths it touched changed since. In the build of that run, the check compares
1151    /// the paths with their states after it; in a later build, with the states the
1152    /// record of that run holds.
1153    #[n(3)]
1154    NotCached {
1155        /// Why the previous run was not cached.
1156        #[n(0)]
1157        why: NotCachedReason,
1158        /// Every difference, sorted by path.
1159        #[n(1)]
1160        differences: Vec<Difference>,
1161    },
1162    /// The step's task is marked `cache=never`, so every command of the task runs as
1163    /// if it were marked `always`, and this was its one run in the build.
1164    #[n(4)]
1165    TaskCacheNever,
1166    /// `kizz run --no-cache` was given, so the step ran although its record may
1167    /// have been a cache hit, and this was its one run in the run of the task.
1168    #[n(5)]
1169    RunNoCache,
1170    /// Tracing is disabled, so this command runs once per build and is never reused.
1171    #[n(6)]
1172    Untraced,
1173}
1174
1175/// What is recorded about one run of a step, by step key, and the tasks that own
1176/// the record.
1177#[derive(Debug, Clone, PartialEq, Eq, Encode, Decode)]
1178pub struct StepRecord {
1179    /// The full step specification.
1180    #[n(0)]
1181    pub spec: StepSpecRecord,
1182    /// The program that ran, after the lookup through `PATH`, or `None` when no
1183    /// program was found.
1184    #[n(1)]
1185    pub program: Option<ProgramPath>,
1186    /// Every touched path that no ignore pattern matched, sorted by path, with its
1187    /// state when the step finished, or when a cache check last refreshed it.
1188    #[n(2)]
1189    pub observations: Vec<Observation>,
1190    /// The number of touched paths that ignore patterns left out.
1191    #[n(3)]
1192    pub ignored: u64,
1193    /// How the command ended.
1194    #[n(4)]
1195    pub exit: StepExit,
1196    /// The raw captured output.
1197    #[n(5)]
1198    pub output: RecordedOutput,
1199    /// How long the command ran, in nanoseconds.
1200    #[n(6)]
1201    pub duration_nanos: u64,
1202    /// When the command ran, in nanoseconds since the Unix epoch.
1203    #[n(7)]
1204    pub ran_at_nanos: u64,
1205    /// Why the step ran.
1206    #[n(8)]
1207    pub reason: RunReason,
1208    /// When kizz began writing the observations, before it read the state of any
1209    /// path, in nanoseconds since the Unix epoch. A cache check that refreshes the
1210    /// observations moves it to when that check began. A recorded modification time
1211    /// within two seconds of it cannot prove a file unchanged.
1212    #[n(9)]
1213    pub recorded_at_nanos: u64,
1214    /// For a program that was missing or not executable, the message of the task
1215    /// failure, which a cache hit fails with again; for a command that could not
1216    /// start, the message of its task failure.
1217    #[n(10)]
1218    pub failure: Option<String>,
1219    /// Why the result of the run was not cached, or `None` when it was.
1220    ///
1221    /// A record with a reason here is never a cache hit: it replaces any older
1222    /// record of the step key, so no older result is replayed, and the next build
1223    /// runs the step again with this reason.
1224    #[n(11)]
1225    pub not_cached: Option<NotCachedReason>,
1226    /// The tasks that own the record, without repeats: every task that produced it
1227    /// or used it, by its [`TaskId`], the absolute path of its `kizz.md` and the
1228    /// index of its block in the file.
1229    ///
1230    /// The owners belong to the record of the step key, not to one run: a run of a
1231    /// task whose identity the engine knows adds the task and keeps the owners of
1232    /// the record it replaces, and a step that its task notes as cached adds the
1233    /// task. A path reset (`kizz cache reset PATH`) removes the record only when
1234    /// every owner is a task under the path, and otherwise only takes those tasks
1235    /// out; `kizz cache clean` takes out the tasks whose `kizz.md` no longer exists.
1236    /// A record with no owner is no task's entry, so no path reset changes it.
1237    #[n(12)]
1238    pub owners: BTreeSet<TaskId>,
1239    /// The number of each system call that the command made and that the tracer
1240    /// does not know, sorted and without repeats, whether the result was cached or
1241    /// not: `kizz build --cache-unknown-syscalls` caches such a result, and without it
1242    /// the record is marked with [`NotCachedReason::UnknownSystemCalls`] unless
1243    /// another reason applies.
1244    #[n(13)]
1245    pub unknown_system_calls: Vec<u32>,
1246    /// Every connection that the command made to an IPv4 or IPv6 address or to a
1247    /// Unix socket, sorted and without repeats, whether the result was cached or
1248    /// not. Connections never keep a result out of the cache.
1249    #[n(14)]
1250    pub connections: Vec<Connection>,
1251    /// The machine and process state that the command started with, which the
1252    /// engine queries right before it looks the program up and runs it, whether or
1253    /// not the step names any part of it.
1254    #[n(15)]
1255    pub machine: MachineStateRecord,
1256}
1257
1258impl Record for StepRecord {
1259    type Key = StepKey;
1260
1261    const FAMILY: Family = Family::Step;
1262}
1263
1264/// The absolute path of a program that a step ran.
1265#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
1266pub struct ProgramPath(pub PathBuf);
1267
1268impl<C> Encode<C> for ProgramPath {
1269    fn encode<W: encode::Write>(
1270        &self,
1271        e: &mut Encoder<W>,
1272        ctx: &mut C,
1273    ) -> Result<(), encode::Error<W::Error>> {
1274        path_bytes::encode(&self.0, e, ctx)
1275    }
1276}
1277
1278impl<'b, C> Decode<'b, C> for ProgramPath {
1279    fn decode(
1280        d: &mut Decoder<'b>,
1281        ctx: &mut C,
1282    ) -> Result<Self, decode::Error> {
1283        path_bytes::decode(d, ctx).map(Self)
1284    }
1285}
1286
1287/// Unit tests for the encoding of step records.
1288#[cfg(test)]
1289#[allow(
1290    clippy::disallowed_macros,
1291    clippy::disallowed_methods,
1292    reason = "test code: the tests assert and lock"
1293)]
1294mod tests {
1295    use super::*;
1296    use crate::machine::{DiskRecord, FileSystemRecord, KernelRecord, LimitRecord, MemoryRecord};
1297
1298    /// One path state of each kind, with both kinds of directory state.
1299    fn states() -> Vec<PathState> {
1300        let meta = FileMeta {
1301            size: 3,
1302            mtime_nanos: -1,
1303            ctime_nanos: 2,
1304            inode: 4,
1305            device: 5,
1306            mode: 0o100_644,
1307            owner: Owner {
1308                uid: 1_000,
1309                gid: 100,
1310            },
1311        };
1312        vec![
1313            PathState::Absent,
1314            PathState::File {
1315                meta,
1316                hash: Some(ContentHash([1; 32])),
1317            },
1318            PathState::File { meta, hash: None },
1319            PathState::Directory {
1320                mode: 0o041_777,
1321                owner: Owner { uid: 0, gid: 0 },
1322                listing: None,
1323                times: Times {
1324                    mtime_nanos: -3,
1325                    ctime_nanos: 4,
1326                },
1327            },
1328            PathState::Directory {
1329                mode: 0o040_750,
1330                owner: Owner {
1331                    uid: 1_000,
1332                    gid: 1_000,
1333                },
1334                listing: Some(Listing {
1335                    hash: ContentHash([2; 32]),
1336                    entries: Some(vec![
1337                        DirEntry {
1338                            name: b"a\xff".to_vec(),
1339                            kind: EntryKind::Symlink,
1340                        },
1341                        DirEntry {
1342                            name: b"0".to_vec(),
1343                            kind: EntryKind::File,
1344                        },
1345                    ]),
1346                    sorted_hash: ContentHash([3; 32]),
1347                }),
1348                times: Times {
1349                    mtime_nanos: 5,
1350                    ctime_nanos: 6,
1351                },
1352            },
1353            PathState::Symlink {
1354                target: PathBuf::from("../x"),
1355                pointee: Box::new(PathState::Absent),
1356            },
1357            PathState::Special {
1358                kind: SpecialKind::Fifo,
1359            },
1360            PathState::Untracked,
1361            PathState::Inaccessible { errno: 13 },
1362        ]
1363    }
1364
1365    /// The recorded attributes of a symbolic link with one attribute of its own and
1366    /// two of what it points to, one with a name that is not UTF-8.
1367    fn attributes() -> Attributes {
1368        Attributes {
1369            own: Some(vec![Attribute {
1370                name: b"user.link".to_vec(),
1371                hash: ContentHash([6; 32]),
1372            }]),
1373            pointee: Some(vec![
1374                Attribute {
1375                    name: b"security.selinux".to_vec(),
1376                    hash: ContentHash([7; 32]),
1377                },
1378                Attribute {
1379                    name: b"user.\xff".to_vec(),
1380                    hash: ContentHash([8; 32]),
1381                },
1382            ]),
1383        }
1384    }
1385
1386    /// A step record with one observation of each state, two of them with recorded
1387    /// extended attributes.
1388    fn record() -> StepRecord {
1389        let states = states();
1390        StepRecord {
1391            spec: StepSpecRecord {
1392                program_hash: ContentHash([9; 32]),
1393                cwd: PathBuf::from("/work"),
1394                argv: vec!["cc".to_owned(), "-c".to_owned()],
1395                env: [
1396                    ("B".to_owned(), "2".to_owned()),
1397                    ("A".to_owned(), "1".to_owned()),
1398                ]
1399                .into(),
1400                stdin: Some("in".to_owned()),
1401                capture: Capture::Merged,
1402                stream: true,
1403                always: false,
1404                untraced: false,
1405                ignore: vec!["re:x".to_owned()],
1406                track: vec!["/proc/cpuinfo".to_owned()],
1407                timestamps: true,
1408                expect: Some(vec![0, 1]),
1409                occurrence: 2,
1410                machine: vec!["kernel".to_owned(), "memory".to_owned()],
1411            },
1412            program: Some(ProgramPath(PathBuf::from("/usr/bin/cc"))),
1413            observations: states
1414                .into_iter()
1415                .enumerate()
1416                .map(|(index, state)| {
1417                    let xattr = matches!(index, 1 | 5);
1418                    let bits = if xattr { AccessBits::XATTR } else { 0 };
1419                    Observation {
1420                        path: PathBuf::from(format!("/p/{index}")),
1421                        access: AccessBits(AccessBits::READ | AccessBits::PROBE | bits),
1422                        tracked: index == 1,
1423                        state,
1424                        attributes: xattr.then(attributes),
1425                    }
1426                })
1427                .collect(),
1428            ignored: 7,
1429            exit: StepExit::Signaled { signal: 9 },
1430            output: RecordedOutput::Split {
1431                stdout: b"out".to_vec(),
1432                stderr: vec![0xFF],
1433            },
1434            duration_nanos: 10,
1435            ran_at_nanos: 11,
1436            reason: RunReason::NeverRun,
1437            recorded_at_nanos: 12,
1438            failure: Some("program `cc` is not executable".to_owned()),
1439            not_cached: Some(NotCachedReason::Signaled { signal: 9 }),
1440            owners: [
1441                TaskId {
1442                    file: PathBuf::from("/b/kizz.md"),
1443                    index: 0,
1444                },
1445                TaskId {
1446                    file: PathBuf::from("/a\u{e9}/kizz.md"),
1447                    index: 3,
1448                },
1449                TaskId {
1450                    file: PathBuf::from("/a\u{e9}/kizz.md"),
1451                    index: 1,
1452                },
1453            ]
1454            .into(),
1455            unknown_system_calls: vec![400, 1_000_000],
1456            connections: connections(),
1457            machine: machine_state(),
1458        }
1459    }
1460
1461    /// A machine state with every part.
1462    fn machine_state() -> MachineStateRecord {
1463        MachineStateRecord {
1464            kernel: Some(KernelRecord {
1465                release: "6.12.0".to_owned(),
1466                version: "#1 SMP".to_owned(),
1467            }),
1468            limits: Some(vec![LimitRecord {
1469                resource: "nofile".to_owned(),
1470                soft: Some(1_024),
1471                hard: None,
1472            }]),
1473            affinity: Some(vec![0, 1]),
1474            memory: Some(MemoryRecord {
1475                total: 8_000,
1476                available: 4_000,
1477            }),
1478            filesystem: Some(FileSystemRecord {
1479                kind: 0xEF53,
1480                flags: 0x1020,
1481            }),
1482            disk: Some(DiskRecord {
1483                size: 100_000,
1484                free: 40_000,
1485            }),
1486        }
1487    }
1488
1489    /// A change of the kernel release.
1490    fn kernel_change() -> MachineChange {
1491        MachineChange {
1492            value: "kernel release".to_owned(),
1493            old: "6.12.0".to_owned(),
1494            new: "6.13.0".to_owned(),
1495        }
1496    }
1497
1498    /// One run reason of each kind, with one difference of each kind.
1499    fn reasons() -> Vec<RunReason> {
1500        let differences: Vec<Difference> = [
1501            Change::Appeared,
1502            Change::Disappeared,
1503            Change::Type,
1504            Change::Permissions {
1505                old: 0o4755,
1506                new: 0o644,
1507            },
1508            Change::Owner {
1509                old: Owner {
1510                    uid: 1_000,
1511                    gid: 1_000,
1512                },
1513                new: Owner { uid: 0, gid: 0 },
1514            },
1515            Change::Timestamps {
1516                old: Times {
1517                    mtime_nanos: 1,
1518                    ctime_nanos: -2,
1519                },
1520                new: Times {
1521                    mtime_nanos: 3,
1522                    ctime_nanos: 4,
1523                },
1524            },
1525            Change::Size { old: 1, new: 2 },
1526            Change::Content,
1527            Change::Metadata,
1528            Change::Entries {
1529                appeared: Vec::new(),
1530                disappeared: Vec::new(),
1531                retyped: Vec::new(),
1532            },
1533            Change::Entries {
1534                appeared: vec![DirEntry {
1535                    name: b"new\xff".to_vec(),
1536                    kind: EntryKind::Directory,
1537                }],
1538                disappeared: vec![DirEntry {
1539                    name: b"old".to_vec(),
1540                    kind: EntryKind::File,
1541                }],
1542                retyped: vec![DirEntry {
1543                    name: b"kind".to_vec(),
1544                    kind: EntryKind::Symlink,
1545                }],
1546            },
1547            Change::Order,
1548            attributes_change(),
1549            Change::Attributes {
1550                appeared: Vec::new(),
1551                disappeared: Vec::new(),
1552                changed: Vec::new(),
1553            },
1554            Change::LinkTarget {
1555                old: PathBuf::from("a"),
1556                new: PathBuf::from("b\u{e9}"),
1557            },
1558        ]
1559        .into_iter()
1560        .map(|change| {
1561            Difference {
1562                path: PathBuf::from("/in"),
1563                change,
1564            }
1565        })
1566        .collect();
1567        let whys = [
1568            NotCachedReason::Signaled { signal: 9 },
1569            NotCachedReason::Interrupted { signal: 2 },
1570            NotCachedReason::InterruptedExited { code: 130 },
1571            NotCachedReason::Incomplete {
1572                detail: "int 0x80".to_owned(),
1573            },
1574            NotCachedReason::StartFailed {
1575                message: "out of memory".to_owned(),
1576            },
1577            changed_after_read(),
1578            unknown_system_calls(),
1579        ];
1580        let mut reasons = vec![
1581            RunReason::NeverRun,
1582            RunReason::Always,
1583            RunReason::TaskCacheNever,
1584            RunReason::InputsChanged {
1585                differences: differences.clone(),
1586                machine: vec![kernel_change()],
1587            },
1588            RunReason::InputsChanged {
1589                differences: differences.clone(),
1590                machine: Vec::new(),
1591            },
1592        ];
1593        reasons.extend(whys.into_iter().map(|why| {
1594            RunReason::NotCached {
1595                why,
1596                differences: differences.clone(),
1597            }
1598        }));
1599        reasons
1600    }
1601
1602    #[test]
1603    fn run_reasons_round_trip() {
1604        for reason in reasons() {
1605            let mut record = record();
1606            record.reason = reason;
1607            let bytes = minicbor::to_vec(&record).unwrap();
1608            assert_eq!(minicbor::decode::<StepRecord>(&bytes).unwrap(), record);
1609        }
1610    }
1611
1612    /// The reason of a step whose task is marked `cache=never` encodes differently
1613    /// from every other run reason, and a record that holds it round-trips.
1614    #[test]
1615    fn the_task_cache_never_reason_encodes_and_round_trips() {
1616        let reasons = reasons();
1617        let encoded: Vec<Vec<u8>> = reasons
1618            .iter()
1619            .map(|reason| minicbor::to_vec(reason).unwrap())
1620            .collect();
1621        let never = minicbor::to_vec(&RunReason::TaskCacheNever).unwrap();
1622        assert_eq!(
1623            minicbor::decode::<RunReason>(&never).unwrap(),
1624            RunReason::TaskCacheNever
1625        );
1626        let matching: Vec<&RunReason> = reasons
1627            .iter()
1628            .zip(&encoded)
1629            .filter(|(_, bytes)| **bytes == never)
1630            .map(|(reason, _)| reason)
1631            .collect();
1632        assert_eq!(matching, [&RunReason::TaskCacheNever]);
1633        let mut record = record();
1634        record.reason = RunReason::TaskCacheNever;
1635        let bytes = minicbor::to_vec(&record).unwrap();
1636        assert_eq!(minicbor::decode::<StepRecord>(&bytes).unwrap(), record);
1637    }
1638
1639    /// The reason of a step that ran because `kizz run --no-cache` was given encodes
1640    /// differently from every other run reason, and a record that holds it
1641    /// round-trips.
1642    #[test]
1643    fn the_run_no_cache_reason_encodes_and_round_trips() {
1644        let no_cache = minicbor::to_vec(&RunReason::RunNoCache).unwrap();
1645        assert_eq!(
1646            minicbor::decode::<RunReason>(&no_cache).unwrap(),
1647            RunReason::RunNoCache
1648        );
1649        for reason in reasons() {
1650            assert_ne!(minicbor::to_vec(&reason).unwrap(), no_cache, "{reason:?}");
1651        }
1652        let mut record = record();
1653        record.reason = RunReason::RunNoCache;
1654        let bytes = minicbor::to_vec(&record).unwrap();
1655        assert_eq!(minicbor::decode::<StepRecord>(&bytes).unwrap(), record);
1656    }
1657
1658    #[test]
1659    fn exits_and_not_cached_markers_round_trip() {
1660        let exits = [
1661            StepExit::Exited { code: -1 },
1662            StepExit::Signaled { signal: 2 },
1663            StepExit::ProgramNotFound,
1664            StepExit::ProgramNotExecutable,
1665            StepExit::NotStarted,
1666        ];
1667        let markers = [
1668            None,
1669            Some(NotCachedReason::Interrupted { signal: 2 }),
1670            Some(NotCachedReason::InterruptedExited { code: 130 }),
1671            Some(NotCachedReason::Incomplete {
1672                detail: "int 0x80".to_owned(),
1673            }),
1674            Some(NotCachedReason::StartFailed {
1675                message: "out of memory".to_owned(),
1676            }),
1677            Some(changed_after_read()),
1678            Some(unknown_system_calls()),
1679        ];
1680        for exit in exits {
1681            for not_cached in markers.clone() {
1682                let mut record = record();
1683                record.exit = exit;
1684                record.not_cached = not_cached;
1685                let bytes = minicbor::to_vec(&record).unwrap();
1686                assert_eq!(minicbor::decode::<StepRecord>(&bytes).unwrap(), record);
1687            }
1688        }
1689    }
1690
1691    /// A timestamp change names each time that changed, old and new, in seconds
1692    /// with nine decimals.
1693    #[test]
1694    fn timestamp_changes_display() {
1695        let times = |mtime_nanos, ctime_nanos| {
1696            Times {
1697                mtime_nanos,
1698                ctime_nanos,
1699            }
1700        };
1701        let shown: Vec<String> = [
1702            (
1703                times(1_700_000_000_000_000_000, 1_700_000_000_000_000_000),
1704                times(1_700_000_001_500_000_000, 1_700_000_000_000_000_000),
1705            ),
1706            (times(1, 2), times(1, -1_000_000_001)),
1707            (times(0, 0), times(1, 2)),
1708        ]
1709        .into_iter()
1710        .map(|(old, new)| Change::Timestamps { old, new }.to_string())
1711        .collect();
1712        assert_eq!(shown, [
1713            "timestamps changed: modification time from 1700000000.000000000 to \
1714             1700000001.500000000",
1715            "timestamps changed: change time from 0.000000002 to -1.000000001",
1716            "timestamps changed: modification time from 0.000000000 to 0.000000001, change \
1717             time from 0.000000000 to 0.000000002",
1718        ]);
1719    }
1720
1721    #[test]
1722    fn changes_and_reasons_display() {
1723        let shown: Vec<String> = [
1724            Change::Appeared,
1725            Change::Disappeared,
1726            Change::Type,
1727            Change::Permissions {
1728                old: 0o755,
1729                new: 0o644,
1730            },
1731            Change::Permissions {
1732                old: 0o7777,
1733                new: 0,
1734            },
1735            Change::Owner {
1736                old: Owner {
1737                    uid: 1_000,
1738                    gid: 1_000,
1739                },
1740                new: Owner { uid: 0, gid: 0 },
1741            },
1742            Change::Size { old: 1, new: 2 },
1743            Change::Content,
1744            Change::Metadata,
1745            Change::Entries {
1746                appeared: Vec::new(),
1747                disappeared: Vec::new(),
1748                retyped: Vec::new(),
1749            },
1750            Change::Order,
1751            Change::LinkTarget {
1752                old: PathBuf::from("a"),
1753                new: PathBuf::from("b"),
1754            },
1755        ]
1756        .iter()
1757        .map(ToString::to_string)
1758        .collect();
1759        assert_eq!(shown, [
1760            "appeared",
1761            "disappeared",
1762            "type changed",
1763            "permissions changed from 0755 to 0644",
1764            "permissions changed from 7777 to 0000",
1765            "owner changed from 1000:1000 to 0:0",
1766            "size changed from 1 to 2 bytes",
1767            "content changed",
1768            "metadata changed",
1769            "directory entries changed",
1770            "the order of its entries changed",
1771            "link target changed from a to b",
1772        ]);
1773        let difference = Difference {
1774            path: PathBuf::from("/in"),
1775            change: Change::Content,
1776        };
1777        assert_eq!(difference.to_string(), "/in: content changed");
1778        let whys: Vec<String> = [
1779            NotCachedReason::Signaled { signal: 9 },
1780            NotCachedReason::Interrupted { signal: 2 },
1781            NotCachedReason::InterruptedExited { code: 130 },
1782            NotCachedReason::Incomplete {
1783                detail: "lost a process".to_owned(),
1784            },
1785            NotCachedReason::StartFailed {
1786                message: "out of memory".to_owned(),
1787            },
1788            changed_after_read(),
1789            NotCachedReason::ChangedAfterRead {
1790                files: vec![ChangedRead {
1791                    path: PathBuf::from("/p/in"),
1792                    written: false,
1793                }],
1794            },
1795            unknown_system_calls(),
1796            NotCachedReason::UnknownSystemCalls { numbers: vec![400] },
1797            NotCachedReason::UnknownSystemCalls {
1798                numbers: vec![1, 2, 3],
1799            },
1800        ]
1801        .iter()
1802        .map(ToString::to_string)
1803        .collect();
1804        assert_eq!(whys, [
1805            "killed by signal 9",
1806            "interrupted, and stopped by signal 2",
1807            "interrupted, and exited with code 130",
1808            "incompletely traced: lost a process",
1809            "could not start: out of memory",
1810            "2 files changed after the command read them: /p/a\u{e9} (the command wrote it), \
1811             /p/b (something else changed it while the command ran)",
1812            "a file changed after the command read it: /p/in (something else changed it while \
1813             the command ran)",
1814            "the command made system calls 400 and 1000000, which the tracer does not know",
1815            "the command made system call 400, which the tracer does not know",
1816            "the command made system calls 1, 2 and 3, which the tracer does not know",
1817        ]);
1818        assert_eq!(system_call_numbers(&[]), "no system call");
1819    }
1820
1821    #[test]
1822    fn step_records_round_trip_with_stable_bytes() {
1823        let record = record();
1824        let first = minicbor::to_vec(&record).unwrap();
1825        let second = minicbor::to_vec(record.clone()).unwrap();
1826        assert_eq!(first, second);
1827        assert_eq!(minicbor::decode::<StepRecord>(&first).unwrap(), record);
1828    }
1829
1830    #[test]
1831    fn records_use_definite_lengths() {
1832        let bytes = minicbor::to_vec(record()).unwrap();
1833        // A definite-length array of sixteen fields, then the specification as a
1834        // definite-length array of fifteen.
1835        assert_eq!(bytes.get(..2), Some(&[0x90, 0x8F][..]));
1836        // The environment is a definite-length map of two entries, sorted by name
1837        // whatever the insertion order.
1838        let encoded_env = minicbor::to_vec(&record().spec.env).unwrap();
1839        assert_eq!(encoded_env, b"\xa2\x61A\x611\x61B\x612");
1840    }
1841
1842    #[test]
1843    fn owners_round_trip_sorted_and_without_repeats() {
1844        let record = record();
1845        let bytes = minicbor::to_vec(&record).unwrap();
1846        let decoded = minicbor::decode::<StepRecord>(&bytes).unwrap();
1847        assert_eq!(decoded.owners, record.owners);
1848        let order: Vec<(&str, u32)> = decoded
1849            .owners
1850            .iter()
1851            .map(|owner| (owner.file.to_str().unwrap(), owner.index))
1852            .collect();
1853        assert_eq!(order, [
1854            ("/a\u{e9}/kizz.md", 1),
1855            ("/a\u{e9}/kizz.md", 3),
1856            ("/b/kizz.md", 0)
1857        ]);
1858        // The owners come before the unknown system calls, the connections and the
1859        // machine state, a definite-length array of three task identities, each an
1860        // array of the file's bytes and the block index.
1861        let owners = minicbor::to_vec(&record.owners).unwrap();
1862        let numbers = minicbor::to_vec(&record.unknown_system_calls).unwrap();
1863        let connections = minicbor::to_vec(&record.connections).unwrap();
1864        let machine = minicbor::to_vec(&record.machine).unwrap();
1865        assert!(
1866            bytes.ends_with(
1867                &[
1868                    owners.as_slice(),
1869                    numbers.as_slice(),
1870                    connections.as_slice(),
1871                    machine.as_slice()
1872                ]
1873                .concat()
1874            )
1875        );
1876        assert_eq!(owners.first(), Some(&0x83));
1877        // A record with no owner keeps an empty set.
1878        let mut unowned = record;
1879        unowned.owners.clear();
1880        let bytes = minicbor::to_vec(&unowned).unwrap();
1881        assert!(
1882            bytes.ends_with(
1883                &[
1884                    &[0x80_u8][..],
1885                    numbers.as_slice(),
1886                    connections.as_slice(),
1887                    machine.as_slice()
1888                ]
1889                .concat()
1890            )
1891        );
1892        assert_eq!(minicbor::decode::<StepRecord>(&bytes).unwrap(), unowned);
1893    }
1894
1895    #[test]
1896    fn access_bits_report_their_kinds() {
1897        let bits = AccessBits(AccessBits::READ | AccessBits::EXEC);
1898        assert!(bits.contains(AccessBits::READ));
1899        assert!(bits.contains(AccessBits::EXEC));
1900        assert!(!bits.contains(AccessBits::PROBE));
1901        assert_eq!(minicbor::to_vec(bits).unwrap(), [0x11]);
1902    }
1903
1904    /// File states carry the owner as the last field of their metadata, directory
1905    /// states carry their mode, owner, and times whether or not they were listed,
1906    /// and both encode deterministically and round-trip.
1907    #[test]
1908    fn file_and_directory_states_carry_mode_owner_and_times() {
1909        let owner = Owner {
1910            uid: 1_000,
1911            gid: 100,
1912        };
1913        let meta = FileMeta {
1914            size: 3,
1915            mtime_nanos: 1,
1916            ctime_nanos: 2,
1917            inode: 4,
1918            device: 5,
1919            mode: 0o104_755,
1920            owner,
1921        };
1922        let owner_bytes = minicbor::to_vec(owner).unwrap();
1923        assert_eq!(owner_bytes, [0x82, 0x19, 0x03, 0xE8, 0x18, 0x64]);
1924        let meta_bytes = minicbor::to_vec(meta).unwrap();
1925        // A definite-length array of seven fields, ending with the owner.
1926        assert_eq!(meta_bytes.first(), Some(&0x87));
1927        assert!(meta_bytes.ends_with(&owner_bytes));
1928        let times = meta.times();
1929        assert_eq!(times, Times {
1930            mtime_nanos: 1,
1931            ctime_nanos: 2,
1932        });
1933        let times_bytes = minicbor::to_vec(times).unwrap();
1934        // A definite-length array of the modification and change times.
1935        assert_eq!(times_bytes, [0x82, 0x01, 0x02]);
1936
1937        let file = PathState::File {
1938            meta,
1939            hash: Some(ContentHash([1; 32])),
1940        };
1941        let checked = PathState::Directory {
1942            mode: 0o041_777,
1943            owner,
1944            listing: None,
1945            times,
1946        };
1947        let listed = PathState::Directory {
1948            mode: 0o040_755,
1949            owner,
1950            listing: Some(Listing {
1951                hash: ContentHash([2; 32]),
1952                entries: Some(Vec::new()),
1953                sorted_hash: ContentHash([2; 32]),
1954            }),
1955            times,
1956        };
1957        for state in [file, checked.clone(), listed] {
1958            let first = minicbor::to_vec(&state).unwrap();
1959            assert_eq!(first, minicbor::to_vec(&state).unwrap());
1960            assert_eq!(minicbor::decode::<PathState>(&first).unwrap(), state);
1961        }
1962        // The mode, the owner, and each time reach the bytes of a directory state,
1963        // whose times are its last field.
1964        let other_owner = PathState::Directory {
1965            mode: 0o041_777,
1966            owner: Owner { uid: 0, gid: 100 },
1967            listing: None,
1968            times,
1969        };
1970        let other_mode = PathState::Directory {
1971            mode: 0o040_777,
1972            owner,
1973            listing: None,
1974            times,
1975        };
1976        let later_modification = PathState::Directory {
1977            mode: 0o041_777,
1978            owner,
1979            listing: None,
1980            times: Times {
1981                mtime_nanos: 7,
1982                ..times
1983            },
1984        };
1985        let later_change = PathState::Directory {
1986            mode: 0o041_777,
1987            owner,
1988            listing: None,
1989            times: Times {
1990                ctime_nanos: 7,
1991                ..times
1992            },
1993        };
1994        let checked = minicbor::to_vec(&checked).unwrap();
1995        assert!(checked.ends_with(&times_bytes));
1996        for other in [other_owner, other_mode, later_modification, later_change] {
1997            assert_ne!(checked, minicbor::to_vec(&other).unwrap());
1998        }
1999        assert_eq!(permission_bits(meta.mode), 0o4755);
2000        assert_eq!(PERMISSION_BITS, 0o7777);
2001    }
2002
2003    /// The `timestamps` option precedes the `machine` names and untraced flag;
2004    /// both timestamp option values round-trip.
2005    #[test]
2006    fn the_timestamps_option_encodes_deterministically_and_round_trips() {
2007        for timestamps in [false, true] {
2008            let mut spec = record().spec;
2009            spec.timestamps = timestamps;
2010            spec.machine = Vec::new();
2011            let first = minicbor::to_vec(&spec).unwrap();
2012            assert_eq!(first, minicbor::to_vec(&spec).unwrap());
2013            let expected = [if timestamps { 0xF5 } else { 0xF4 }, 0x80, 0xF4];
2014            assert_eq!(
2015                first.get(first.len().saturating_sub(3)..),
2016                Some(&expected[..])
2017            );
2018            assert_eq!(minicbor::decode::<StepSpecRecord>(&first).unwrap(), spec);
2019        }
2020    }
2021
2022    /// The `machine` names precede the untraced flag in the specification encoding,
2023    /// as an array of text strings; and the machine state is the last field of the
2024    /// record. Both encode deterministically and round-trip, a state whose parts
2025    /// could not be read included.
2026    #[test]
2027    fn machine_names_and_state_encode_deterministically_and_round_trip() {
2028        let mut spec = record().spec;
2029        let first = minicbor::to_vec(&spec).unwrap();
2030        assert_eq!(first, minicbor::to_vec(&spec).unwrap());
2031        assert!(
2032            first.ends_with(b"\x82\x66kernel\x66memory\xF4"),
2033            "{first:x?}"
2034        );
2035        assert_eq!(minicbor::decode::<StepSpecRecord>(&first).unwrap(), spec);
2036        spec.machine = vec!["disk".to_owned()];
2037        let other = minicbor::to_vec(&spec).unwrap();
2038        assert!(other.ends_with(b"\x81\x64disk\xF4"), "{other:x?}");
2039
2040        let state = minicbor::to_vec(machine_state()).unwrap();
2041        let mut record = record();
2042        let bytes = minicbor::to_vec(&record).unwrap();
2043        assert!(bytes.ends_with(&state));
2044        assert_eq!(minicbor::decode::<StepRecord>(&bytes).unwrap(), record);
2045        record.machine = MachineStateRecord::default();
2046        let unknown = minicbor::to_vec(&record).unwrap();
2047        assert_eq!(unknown, minicbor::to_vec(&record).unwrap());
2048        assert_eq!(minicbor::decode::<StepRecord>(&unknown).unwrap(), record);
2049    }
2050
2051    /// An entries change names what appeared, disappeared, and changed type, each
2052    /// group only when it is not empty and with at most ten names, and an order
2053    /// change says that only the order changed.
2054    #[test]
2055    fn entries_and_order_changes_display() {
2056        let entry = |name: &str| {
2057            DirEntry {
2058                name: name.as_bytes().to_vec(),
2059                kind: EntryKind::File,
2060            }
2061        };
2062        let many: Vec<DirEntry> = (0..12)
2063            .map(|index| entry(&format!("f{index:02}")))
2064            .collect();
2065        let shown: Vec<String> = [
2066            Change::Entries {
2067                appeared: vec![entry("b.txt")],
2068                disappeared: vec![entry("a.txt"), entry("c.txt")],
2069                retyped: vec![entry("d")],
2070            },
2071            Change::Entries {
2072                appeared: Vec::new(),
2073                disappeared: vec![entry("gone")],
2074                retyped: Vec::new(),
2075            },
2076            Change::Entries {
2077                appeared: many,
2078                disappeared: Vec::new(),
2079                retyped: vec![DirEntry {
2080                    name: b"x\xff".to_vec(),
2081                    kind: EntryKind::Directory,
2082                }],
2083            },
2084            Change::Order,
2085        ]
2086        .iter()
2087        .map(ToString::to_string)
2088        .collect();
2089        let many_and_invalid = format!(
2090            "directory entries changed: `f00`, `f01`, `f02`, `f03`, `f04`, `f05`, `f06`, `f07`, \
2091             `f08`, `f09` and 2 more appeared; `x{}` changed type",
2092            char::REPLACEMENT_CHARACTER
2093        );
2094        assert_eq!(shown, [
2095            "directory entries changed: `b.txt` appeared; `a.txt`, `c.txt` disappeared; `d` \
2096             changed type",
2097            "directory entries changed: `gone` disappeared",
2098            many_and_invalid.as_str(),
2099            "the order of its entries changed",
2100        ]);
2101    }
2102
2103    /// A listing keeps its entries in the order given, encodes deterministically as
2104    /// a definite-length array of the ordered hash, the entries, and the sorted
2105    /// hash, and round-trips, with or without its entries.
2106    #[test]
2107    fn listings_keep_their_order_encode_deterministically_and_round_trip() {
2108        let entries = vec![
2109            DirEntry {
2110                name: b"z".to_vec(),
2111                kind: EntryKind::File,
2112            },
2113            DirEntry {
2114                name: b"a".to_vec(),
2115                kind: EntryKind::Directory,
2116            },
2117        ];
2118        let listed = Listing {
2119            hash: ContentHash([4; 32]),
2120            entries: Some(entries.clone()),
2121            sorted_hash: ContentHash([5; 32]),
2122        };
2123        let large = Listing {
2124            entries: None,
2125            ..listed.clone()
2126        };
2127        for listing in [&listed, &large] {
2128            let first = minicbor::to_vec(listing).unwrap();
2129            assert_eq!(first, minicbor::to_vec(listing).unwrap());
2130            assert_eq!(first.first(), Some(&0x83));
2131            assert!(first.ends_with(&minicbor::to_vec(ContentHash([5; 32])).unwrap()));
2132            assert_eq!(&minicbor::decode::<Listing>(&first).unwrap(), listing);
2133        }
2134        let decoded = minicbor::decode::<Listing>(&minicbor::to_vec(&listed).unwrap()).unwrap();
2135        assert_eq!(decoded.entries, Some(entries.clone()));
2136        // The same entries in another order encode differently.
2137        let reversed = Listing {
2138            entries: Some(entries.into_iter().rev().collect()),
2139            ..listed.clone()
2140        };
2141        assert_ne!(
2142            minicbor::to_vec(&listed).unwrap(),
2143            minicbor::to_vec(&reversed).unwrap()
2144        );
2145    }
2146
2147    /// The reason of a run in which two files changed after the command read them:
2148    /// one that the command wrote, with a path that is not ASCII, and one that
2149    /// something else changed.
2150    fn changed_after_read() -> NotCachedReason {
2151        NotCachedReason::ChangedAfterRead {
2152            files: vec![
2153                ChangedRead {
2154                    path: PathBuf::from("/p/a\u{e9}"),
2155                    written: true,
2156                },
2157                ChangedRead {
2158                    path: PathBuf::from("/p/b"),
2159                    written: false,
2160                },
2161            ],
2162        }
2163    }
2164
2165    /// The reason of a run that made the system calls 400 and 1,000,000, which the
2166    /// tracer does not know.
2167    fn unknown_system_calls() -> NotCachedReason {
2168        NotCachedReason::UnknownSystemCalls {
2169            numbers: vec![400, 1_000_000],
2170        }
2171    }
2172
2173    /// The reason for unknown system calls encodes deterministically, as variant 6
2174    /// with a definite-length array of the numbers, and round-trips, alone and as a
2175    /// record's marker; the numbers of a record encode as its field 13, after the
2176    /// owners, and round-trip with a marker and without one.
2177    #[test]
2178    fn unknown_system_calls_encode_deterministically_and_round_trip() {
2179        let why = unknown_system_calls();
2180        let first = minicbor::to_vec(&why).unwrap();
2181        assert_eq!(first, minicbor::to_vec(why.clone()).unwrap());
2182        // The variant index, then its one field: an array of 400 and 1,000,000.
2183        assert_eq!(first, [
2184            0x82, 0x06, 0x81, 0x82, 0x19, 0x01, 0x90, 0x1A, 0x00, 0x0F, 0x42, 0x40
2185        ]);
2186        assert_eq!(minicbor::decode::<NotCachedReason>(&first).unwrap(), why);
2187        let numbers = minicbor::to_vec(vec![400_u32, 1_000_000]).unwrap();
2188        let connections = minicbor::to_vec(connections()).unwrap();
2189        let machine = minicbor::to_vec(machine_state()).unwrap();
2190        for not_cached in [Some(why), None] {
2191            let mut record = record();
2192            record.not_cached = not_cached;
2193            let bytes = minicbor::to_vec(&record).unwrap();
2194            assert_eq!(bytes, minicbor::to_vec(&record).unwrap());
2195            assert!(
2196                bytes.ends_with(
2197                    &[
2198                        numbers.as_slice(),
2199                        connections.as_slice(),
2200                        machine.as_slice()
2201                    ]
2202                    .concat()
2203                )
2204            );
2205            let decoded = minicbor::decode::<StepRecord>(&bytes).unwrap();
2206            assert_eq!(decoded, record);
2207            assert_eq!(decoded.unknown_system_calls, [400, 1_000_000]);
2208        }
2209        let mut none = record();
2210        none.unknown_system_calls = Vec::new();
2211        let bytes = minicbor::to_vec(&none).unwrap();
2212        assert_eq!(minicbor::decode::<StepRecord>(&bytes).unwrap(), none);
2213    }
2214
2215    /// One connection of each kind, sorted: an IPv4 address, an IPv6 address with a
2216    /// scope, a Unix socket by path, and an abstract name with a zero byte.
2217    fn connections() -> Vec<Connection> {
2218        vec![
2219            Connection::Ipv4 {
2220                address: [127, 0, 0, 1],
2221                port: 80,
2222            },
2223            Connection::Ipv6 {
2224                address: [0xFE, 0x80, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
2225                port: 443,
2226                scope: 2,
2227            },
2228            Connection::UnixPath {
2229                path: PathBuf::from("/run/s"),
2230            },
2231            Connection::UnixAbstract {
2232                name: b"k\0x".to_vec(),
2233            },
2234        ]
2235    }
2236
2237    /// Each connection encodes deterministically, as its variant index with a
2238    /// definite-length array of its fields, addresses, paths and names as byte
2239    /// strings, and round-trips; the connections of a record encode as its field
2240    /// 14, after the unknown system calls, and round-trip with a marker and
2241    /// without one, and with no connection at all.
2242    #[test]
2243    fn connections_encode_deterministically_and_round_trip() {
2244        let [ipv4, ipv6, path, abstract_name] = connections().try_into().unwrap();
2245        let expected: [(&Connection, Vec<u8>); 4] = [
2246            (&ipv4, vec![
2247                0x82, 0x00, 0x82, 0x44, 0x7F, 0x00, 0x00, 0x01, 0x18, 0x50,
2248            ]),
2249            (&ipv6, {
2250                let mut bytes = vec![0x82, 0x01, 0x83, 0x50, 0xFE, 0x80];
2251                bytes.extend([0; 13]);
2252                bytes.extend([0x01, 0x19, 0x01, 0xBB, 0x02]);
2253                bytes
2254            }),
2255            (&path, vec![
2256                0x82, 0x02, 0x81, 0x46, b'/', b'r', b'u', b'n', b'/', b's',
2257            ]),
2258            (&abstract_name, vec![
2259                0x82, 0x03, 0x81, 0x43, b'k', 0x00, b'x',
2260            ]),
2261        ];
2262        for (connection, bytes) in expected {
2263            let first = minicbor::to_vec(connection).unwrap();
2264            assert_eq!(first, minicbor::to_vec(connection.clone()).unwrap());
2265            assert_eq!(first, bytes, "{connection}");
2266            assert_eq!(minicbor::decode::<Connection>(&first).unwrap(), *connection);
2267        }
2268        let listed = minicbor::to_vec(connections()).unwrap();
2269        assert_eq!(listed.first(), Some(&0x84));
2270        let machine = minicbor::to_vec(machine_state()).unwrap();
2271        for not_cached in [Some(NotCachedReason::Signaled { signal: 9 }), None] {
2272            let mut record = record();
2273            record.not_cached = not_cached;
2274            let bytes = minicbor::to_vec(&record).unwrap();
2275            assert_eq!(bytes, minicbor::to_vec(&record).unwrap());
2276            assert!(bytes.ends_with(&[listed.as_slice(), machine.as_slice()].concat()));
2277            let decoded = minicbor::decode::<StepRecord>(&bytes).unwrap();
2278            assert_eq!(decoded, record);
2279            assert_eq!(decoded.connections, connections());
2280        }
2281        let mut none = record();
2282        none.connections = Vec::new();
2283        let bytes = minicbor::to_vec(&none).unwrap();
2284        assert!(bytes.ends_with(&[&[0x80][..], machine.as_slice()].concat()));
2285        assert_eq!(minicbor::decode::<StepRecord>(&bytes).unwrap(), none);
2286    }
2287
2288    /// Connections read as an address and port, or as a Unix socket by path or
2289    /// abstract name with its unprintable bytes escaped, alone and in lists.
2290    #[test]
2291    fn connections_read_as_text() {
2292        let shown: Vec<String> = connections().iter().map(ToString::to_string).collect();
2293        assert_eq!(shown, [
2294            "127.0.0.1:80",
2295            "[fe80::1%2]:443",
2296            "Unix socket /run/s",
2297            "abstract Unix socket @k\\x00x",
2298        ]);
2299        let relative = |path: &Path| {
2300            path.strip_prefix("/run")
2301                .unwrap_or(path)
2302                .display()
2303                .to_string()
2304        };
2305        assert_eq!(connections_text(&[], relative), "no connection");
2306        assert_eq!(
2307            connections_text(&connections()[2..3], relative),
2308            "Unix socket s"
2309        );
2310        assert_eq!(
2311            connections_text(&connections()[..2], relative),
2312            "127.0.0.1:80 and [fe80::1%2]:443"
2313        );
2314        assert_eq!(
2315            connections_text(&connections(), relative),
2316            "127.0.0.1:80, [fe80::1%2]:443, Unix socket s and abstract Unix socket @k\\x00x"
2317        );
2318    }
2319
2320    /// The reason for files that changed after the command read them encodes
2321    /// deterministically, as variant 5 with a definite-length array of the files,
2322    /// each a path as a byte string and whether the command wrote it, and
2323    /// round-trips, alone and as a record's marker.
2324    #[test]
2325    fn changed_after_read_encodes_deterministically_and_round_trips() {
2326        let why = changed_after_read();
2327        let first = minicbor::to_vec(&why).unwrap();
2328        assert_eq!(first, minicbor::to_vec(why.clone()).unwrap());
2329        let file = minicbor::to_vec(ChangedRead {
2330            path: PathBuf::from("/p/b"),
2331            written: false,
2332        })
2333        .unwrap();
2334        assert_eq!(file, b"\x82\x44/p/b\xf4");
2335        // The variant index, then its one field: an array of two files.
2336        assert_eq!(first.get(..3), Some(&[0x82, 0x05, 0x81][..]));
2337        assert_eq!(first.get(3), Some(&0x82));
2338        assert!(first.ends_with(&file));
2339        assert_eq!(minicbor::decode::<NotCachedReason>(&first).unwrap(), why);
2340        let mut record = record();
2341        record.not_cached = Some(why);
2342        let bytes = minicbor::to_vec(&record).unwrap();
2343        assert_eq!(bytes, minicbor::to_vec(&record).unwrap());
2344        assert_eq!(minicbor::decode::<StepRecord>(&bytes).unwrap(), record);
2345    }
2346
2347    /// An attribute named `name` whose value hashes to `byte` repeated.
2348    fn attribute(
2349        name: &[u8],
2350        byte: u8,
2351    ) -> Attribute {
2352        Attribute {
2353            name: name.to_vec(),
2354            hash: ContentHash([byte; 32]),
2355        }
2356    }
2357
2358    /// An attribute change in which one attribute appeared, one disappeared, and
2359    /// one, whose name is not UTF-8, changed value.
2360    fn attributes_change() -> Change {
2361        Change::Attributes {
2362            appeared: vec![attribute(b"user.new", 1)],
2363            disappeared: vec![attribute(b"user.old", 2)],
2364            changed: vec![attribute(b"user.\xff", 3)],
2365        }
2366    }
2367
2368    /// Recorded attributes encode deterministically, each attribute as a
2369    /// definite-length array of its name as a byte string and its hash, and
2370    /// round-trip; attributes that could not be read differ from no attributes; and
2371    /// the attribute change encodes as variant 12 and round-trips, alone and in a
2372    /// record, as do observations with and without attributes.
2373    #[test]
2374    fn attributes_and_their_changes_encode_deterministically_and_round_trip() {
2375        let mut expected = vec![0x82, 0x46];
2376        expected.extend_from_slice(b"user.a");
2377        expected.extend_from_slice(&[0x58, 0x20]);
2378        expected.extend_from_slice(&[9; 32]);
2379        assert_eq!(minicbor::to_vec(attribute(b"user.a", 9)).unwrap(), expected);
2380        let none = Attributes {
2381            own: Some(Vec::new()),
2382            pointee: None,
2383        };
2384        let unreadable = Attributes {
2385            own: None,
2386            pointee: None,
2387        };
2388        for recorded in [attributes(), none.clone(), unreadable.clone()] {
2389            let first = minicbor::to_vec(&recorded).unwrap();
2390            assert_eq!(first, minicbor::to_vec(recorded.clone()).unwrap());
2391            assert_eq!(minicbor::decode::<Attributes>(&first).unwrap(), recorded);
2392        }
2393        assert_ne!(
2394            minicbor::to_vec(&none).unwrap(),
2395            minicbor::to_vec(&unreadable).unwrap()
2396        );
2397
2398        let change = attributes_change();
2399        let first = minicbor::to_vec(&change).unwrap();
2400        assert_eq!(first, minicbor::to_vec(change.clone()).unwrap());
2401        assert_eq!(first.get(..3), Some(&[0x82, 0x0C, 0x83][..]));
2402        assert_eq!(minicbor::decode::<Change>(&first).unwrap(), change);
2403
2404        let record = record();
2405        let bytes = minicbor::to_vec(&record).unwrap();
2406        assert_eq!(bytes, minicbor::to_vec(&record).unwrap());
2407        let decoded = minicbor::decode::<StepRecord>(&bytes).unwrap();
2408        assert_eq!(decoded, record);
2409        assert_eq!(decoded.observations[5].attributes, Some(attributes()));
2410        assert!(decoded.observations[5].access.contains(AccessBits::XATTR));
2411        assert_eq!(decoded.observations[0].attributes, None);
2412    }
2413
2414    /// An attribute change names what appeared, disappeared, and changed value,
2415    /// each group only when it is not empty and with at most ten names, and says
2416    /// only that the attributes changed when it names none.
2417    #[test]
2418    fn attribute_changes_display() {
2419        let many: Vec<Attribute> = (0..12)
2420            .map(|index| attribute(format!("user.{index:02}").as_bytes(), 0))
2421            .collect();
2422        let shown: Vec<String> = [
2423            attributes_change(),
2424            Change::Attributes {
2425                appeared: Vec::new(),
2426                disappeared: Vec::new(),
2427                changed: Vec::new(),
2428            },
2429            Change::Attributes {
2430                appeared: Vec::new(),
2431                disappeared: many,
2432                changed: vec![attribute(b"user.x", 1)],
2433            },
2434        ]
2435        .iter()
2436        .map(ToString::to_string)
2437        .collect();
2438        let not_utf8 = format!(
2439            "extended attributes changed: `user.new` appeared; `user.old` disappeared; `user.{}` \
2440             changed",
2441            char::REPLACEMENT_CHARACTER
2442        );
2443        assert_eq!(shown, [
2444            not_utf8.as_str(),
2445            "extended attributes changed",
2446            "extended attributes changed: `user.00`, `user.01`, `user.02`, `user.03`, `user.04`, \
2447             `user.05`, `user.06`, `user.07`, `user.08`, `user.09` and 2 more disappeared; \
2448             `user.x` changed",
2449        ]);
2450        assert_eq!(AccessBits::XATTR, 0b0010_0000);
2451    }
2452
2453    #[test]
2454    fn entry_kinds_have_distinct_codes() {
2455        let kinds = [
2456            EntryKind::File,
2457            EntryKind::Directory,
2458            EntryKind::Symlink,
2459            EntryKind::BlockDevice,
2460            EntryKind::CharDevice,
2461            EntryKind::Fifo,
2462            EntryKind::Socket,
2463            EntryKind::Unknown,
2464        ];
2465        let codes: std::collections::BTreeSet<u8> = kinds.iter().map(|kind| kind.code()).collect();
2466        assert_eq!(codes.len(), kinds.len());
2467        assert_eq!(ContentHash([0xAB; 32]).to_string(), "ab".repeat(32));
2468    }
2469}