Skip to main content

kizz_core/
observe.rs

1// Copyright (c) 2026 Sakura Industries LLC.
2//
3// SPDX-License-Identifier: AGPL-3.0-only
4
5//! The state of every path a step touched, recorded when the step finishes.
6//!
7//! [`observe`] turns the accesses a tracer reported into observations, recording
8//! the paths concurrently. Paths that an ignore pattern matches are left out and
9//! counted. Each other path gets the [`PathState`] that "Path states" specifies:
10//!
11//! * absent paths: [`PathState::Absent`];
12//! * regular files: size, modification and change times in nanoseconds, inode, device,
13//!   mode, and owner, plus a BLAKE3 hash of the content only when the file was read or
14//!   run, hashed with several threads for large files, through the build's
15//!   [`FileStates`], so a file is hashed once per build;
16//! * directories: mode, owner, and modification and change times, and when they were
17//!   listed, also a hash of the entry names and types in the order the file system
18//!   returned them, a hash of the same entries sorted, and the entries in that order when
19//!   there are at most [`MAX_LISTED_NAMES`]; entry inode numbers are not recorded;
20//! * symbolic links: the target, plus the state of what the link points to;
21//! * devices, FIFOs, and sockets: type only.
22//!
23//! A path whose extended attributes the step read or listed, the xattr kind, also
24//! records them with its state (see [`record_attributes`]): each name with a BLAKE3
25//! hash of its value, sorted by name, for the path itself and, for a symbolic link,
26//! for what it points to. Kizz reads them only through the attribute query of the
27//! tracer interface, [`Tracer::extended_attributes`], because the standard library
28//! cannot read them.
29//!
30//! Paths under `/proc` and `/sys` are recorded as [`PathState::Untracked`] unless a
31//! `track` pattern matches them; a tracked one gets its state, with the content of
32//! a regular file read and hashed again whatever the access, never from the cache.
33//! A path that symbolic links lead into `/proc` or `/sys`, such as `/dev/fd/3` or
34//! `/dev/stdin`, leaves only that final object untracked (see [`kernel_links`]): the
35//! links on the way stay ordinary dependencies, each recorded with its target, so
36//! retargeting, removing, or replacing one of them changes the step. A final link is
37//! recorded as [`PathState::Symlink`] with an untracked pointee, and every other link
38//! on the way is recorded as such a link too, as a probe.
39//!
40//! [`changed_after_read`] compares the first-read metadata that the tracer noted
41//! with the recorded states, to find the files that changed during the run after
42//! the command first read them or ran them.
43
44use std::{
45    collections::{BTreeMap, VecDeque},
46    ffi::OsString,
47    fs::{self, FileType, Metadata},
48    io,
49    os::unix::{
50        ffi::OsStringExt as _,
51        fs::{FileTypeExt as _, MetadataExt as _},
52    },
53    path::{Component, Path, PathBuf},
54    sync::atomic::{AtomicU64, Ordering},
55};
56
57use kizz_store::{
58    AccessBits, Attribute, Attributes, ChangedRead, ContentHash, DirEntry, EntryKind, FileMeta,
59    Listing, MAX_LISTED_NAMES, Observation, Owner, PathState, SpecialKind, Times,
60};
61use kizz_trace::{
62    AbsolutePath, AccessKind, AccessKinds, Accesses, ExtendedAttributes, FileMetadata, FirstReads,
63    Tracer,
64};
65use rayon::iter::{IntoParallelRefIterator as _, ParallelIterator as _};
66
67use crate::{patterns::PathPatterns, states::FileStates};
68
69/// The context string from which directory listing hashes are derived, both the
70/// hash of the entries in the order the file system returned them and the hash of
71/// the same entries sorted.
72const LISTING_CONTEXT: &str = "kizz directory listing, version 2";
73
74/// The kernel interfaces whose paths are recorded but not compared unless tracked.
75const KERNEL_ROOTS: [&str; 2] = ["/proc", "/sys"];
76
77/// Nanoseconds in a second.
78const NANOS_PER_SECOND: i64 = 1_000_000_000;
79
80/// The most symbolic links [`kernel_links`] follows, as many as a Linux path lookup
81/// follows.
82const MAX_LINKS: usize = 40;
83
84/// Whether `path` is under `/proc` or `/sys`, or is one of them.
85#[must_use]
86pub fn is_kernel_path(path: &Path) -> bool {
87    KERNEL_ROOTS.iter().any(|root| path.starts_with(root))
88}
89
90/// Whether `path` is under `/proc` or `/sys`, or the symbolic links on the way to it
91/// lead there, as `/dev/fd` leads to `/proc/self/fd` and `/dev/stdin` to
92/// `/proc/self/fd/0` (see [`kernel_links`]).
93#[must_use]
94pub fn reaches_kernel(path: &Path) -> bool {
95    kernel_links(path).is_some()
96}
97
98/// The symbolic links outside `/proc` and `/sys`, each with its target, that lead
99/// `path` into `/proc` or `/sys`, in the order a path lookup follows them; `None`
100/// when `path` does not reach `/proc` or `/sys`, and no links when it is under one
101/// of them already.
102///
103/// A path that reaches `/proc` or `/sys` describes whichever process looks at it:
104/// read when kizz records or checks a step, it would describe kizz, not the
105/// command, so the object it reaches is recorded like any other `/proc` or `/sys`
106/// path. The links that lead there are ordinary files of the project or the
107/// system, so they are not. The lookup resolves each component in turn, follows
108/// at most 40 links, and stops at the first component under `/proc` or `/sys`,
109/// never reading anything there. A path that cannot be resolved, such as a missing
110/// one, is judged by its own form.
111#[must_use]
112pub fn kernel_links(path: &Path) -> Option<Vec<(PathBuf, PathBuf)>> {
113    kernel_route(path).map(|route| route.links)
114}
115
116/// How a path reaches `/proc` or `/sys`.
117#[derive(Debug, Default)]
118struct KernelRoute {
119    /// The symbolic links outside `/proc` and `/sys` on the way, each with its
120    /// target, in lookup order.
121    links: Vec<(PathBuf, PathBuf)>,
122    /// The target of the path's own final component, when that is a symbolic link
123    /// outside `/proc` and `/sys`.
124    own_target: Option<PathBuf>,
125}
126
127/// How `path` reaches `/proc` or `/sys`, or `None` when it does not, as
128/// [`kernel_links`] describes.
129fn kernel_route(path: &Path) -> Option<KernelRoute> {
130    let mut route = KernelRoute::default();
131    if is_kernel_path(path) {
132        return Some(route);
133    }
134    // Each name to look up, marked when it is the path's own final component.
135    let mut pending: VecDeque<(OsString, bool)> = VecDeque::new();
136    push_components(&mut pending, path, true);
137    let mut resolved = PathBuf::from("/");
138    while let Some((name, own)) = pending.pop_front() {
139        if name == ".." {
140            resolved.pop();
141            continue;
142        }
143        let candidate = resolved.join(&name);
144        if is_kernel_path(&candidate) {
145            return Some(route);
146        }
147        let metadata = fs::symlink_metadata(&candidate).ok()?;
148        if !metadata.file_type().is_symlink() {
149            resolved = candidate;
150            continue;
151        }
152        if route.links.len() >= MAX_LINKS {
153            return None;
154        }
155        let target = fs::read_link(&candidate).ok()?;
156        if target.is_absolute() {
157            resolved = PathBuf::from("/");
158        }
159        let mut rest = VecDeque::new();
160        push_components(&mut rest, &target, false);
161        rest.append(&mut pending);
162        pending = rest;
163        if own {
164            route.own_target = Some(target.clone());
165        }
166        route.links.push((candidate, target));
167    }
168    is_kernel_path(&resolved).then_some(route)
169}
170
171/// Append the names and `..` components of `path` to `pending`, leaving out the
172/// root and `.`, and marking the last one with `own`.
173fn push_components(
174    pending: &mut VecDeque<(OsString, bool)>,
175    path: &Path,
176    own: bool,
177) {
178    for component in path.components() {
179        match component {
180            Component::Normal(name) => pending.push_back((name.to_os_string(), false)),
181            Component::ParentDir => pending.push_back((OsString::from(".."), false)),
182            Component::RootDir | Component::CurDir | Component::Prefix(_) => {},
183        }
184    }
185    if let Some(last) = pending.back_mut() {
186        last.1 = own;
187    }
188}
189
190/// Counts the files whose content was hashed, so tests can observe hashing.
191#[derive(Debug, Default)]
192pub struct HashCounter {
193    /// The number of files hashed.
194    files: AtomicU64,
195}
196
197impl HashCounter {
198    /// A counter at zero.
199    #[must_use]
200    pub fn new() -> Self {
201        Self::default()
202    }
203
204    /// The number of files hashed so far.
205    #[must_use]
206    pub fn files(&self) -> u64 {
207        self.files.load(Ordering::Relaxed)
208    }
209
210    /// Count one hashed file.
211    pub(crate) fn count(&self) {
212        self.files.fetch_add(1, Ordering::Relaxed);
213    }
214}
215
216/// The observations of one step.
217#[derive(Debug, Clone, PartialEq, Eq, Default)]
218pub struct Observed {
219    /// Every touched path that no ignore pattern matched, sorted by path, with its
220    /// state.
221    pub observations: Vec<Observation>,
222    /// The number of touched paths that ignore patterns left out.
223    pub ignored: u64,
224}
225
226/// The access kinds `kinds` as the store records them.
227#[must_use]
228pub fn access_bits(kinds: AccessKinds) -> AccessBits {
229    AccessBits(kinds.iter().fold(0, |bits, kind| {
230        bits | match kind {
231            AccessKind::Read => AccessBits::READ,
232            AccessKind::Probe => AccessBits::PROBE,
233            AccessKind::List => AccessBits::LIST,
234            AccessKind::Write => AccessBits::WRITE,
235            AccessKind::Exec => AccessBits::EXEC,
236            AccessKind::Xattr => AccessBits::XATTR,
237        }
238    }))
239}
240
241/// Record the state of every path in `accesses`, concurrently on the worker pool of
242/// `states`, leaving out and counting the paths that `ignore` matches, and hashing
243/// the `/proc` and `/sys` paths that `track` matches. Hashes go through `states`, and
244/// the extended attributes of the paths whose attributes were read or listed come
245/// from the attribute query of `tracer`.
246#[must_use]
247pub fn observe(
248    accesses: &Accesses,
249    ignore: &PathPatterns,
250    track: &PathPatterns,
251    states: &FileStates,
252    tracer: &dyn Tracer,
253) -> Observed {
254    let (kept, ignored): (Vec<_>, Vec<_>) = accesses
255        .iter()
256        .map(|(path, kinds)| (path, *kinds))
257        .partition(|(path, _)| !ignore.matches(path));
258    let recorded: Vec<(Observation, Vec<Observation>)> = states.pool().install(|| {
259        kept.par_iter()
260            .map(|&(path, kinds)| observation(path, kinds, track, states, tracer))
261            .collect()
262    });
263    let mut observations = BTreeMap::new();
264    let mut links = Vec::new();
265    for (observation, on_the_way) in recorded {
266        links.extend(on_the_way);
267        observations.insert(observation.path.clone(), observation);
268    }
269    for link in links {
270        let ignored_link = AbsolutePath::new(&link.path).is_ok_and(|path| ignore.matches(&path));
271        if !ignored_link {
272            observations.entry(link.path.clone()).or_insert(link);
273        }
274    }
275    Observed {
276        observations: observations.into_values().collect(),
277        ignored: u64::try_from(ignored.len()).unwrap_or(u64::MAX),
278    }
279}
280
281/// The observation of one path that a step touched with `kinds`, and the
282/// observations of the symbolic links that lead it into `/proc` or `/sys`. A path
283/// whose extended attributes were read or listed records them, unless it leads
284/// into `/proc` or `/sys` and no `track` pattern matched it.
285fn observation(
286    path: &AbsolutePath,
287    kinds: AccessKinds,
288    track: &PathPatterns,
289    states: &FileStates,
290    tracer: &dyn Tracer,
291) -> (Observation, Vec<Observation>) {
292    let route = kernel_route(path.as_path());
293    let tracked = route.is_some() && track.matches(path);
294    let attributes = || {
295        kinds
296            .contains(AccessKind::Xattr)
297            .then(|| record_attributes(path.as_path(), tracer))
298    };
299    let Some(route) = route else {
300        let observation = Observation {
301            path: path.as_path().to_path_buf(),
302            access: access_bits(kinds),
303            tracked,
304            state: path_state(path.as_path(), kinds, false, states),
305            attributes: attributes(),
306        };
307        return (observation, Vec::new());
308    };
309    let state = if tracked {
310        path_state(path.as_path(), kinds, true, states)
311    } else {
312        // Only the object under `/proc` or `/sys` is untracked: a final link outside
313        // them keeps its target.
314        route
315            .own_target
316            .map_or(PathState::Untracked, untracked_link)
317    };
318    let on_the_way = route
319        .links
320        .into_iter()
321        .map(|(link, target)| {
322            Observation {
323                path: link,
324                access: AccessBits(AccessBits::PROBE),
325                tracked: false,
326                state: untracked_link(target),
327                attributes: None,
328            }
329        })
330        .collect();
331    let observation = Observation {
332        path: path.as_path().to_path_buf(),
333        access: access_bits(kinds),
334        tracked,
335        state,
336        attributes: if tracked { attributes() } else { None },
337    };
338    (observation, on_the_way)
339}
340
341/// The extended attributes of `path` now, as a path whose attributes were read or
342/// listed records them, read through the attribute query of `tracer`: those of the
343/// path itself, without following a final symbolic link, and, when the path is a
344/// symbolic link, those of what it points to. Each list holds every name with a
345/// BLAKE3 hash of its value, sorted by name, or is `None` when the query fails, as
346/// it does when nothing is at the path; a file system without attributes has none.
347///
348/// A cache check reads them again the same way and compares the two.
349#[must_use]
350pub fn record_attributes(
351    path: &Path,
352    tracer: &dyn Tracer,
353) -> Attributes {
354    let hashed = |follow: bool| tracer.extended_attributes(path, follow).ok().map(hashes);
355    let link = fs::symlink_metadata(path).is_ok_and(|metadata| metadata.file_type().is_symlink());
356    Attributes {
357        own: hashed(false),
358        pointee: if link { hashed(true) } else { None },
359    }
360}
361
362/// Each attribute of `attributes` with a BLAKE3 hash of its value, sorted by name.
363fn hashes(attributes: ExtendedAttributes) -> Vec<Attribute> {
364    attributes
365        .into_iter()
366        .map(|(name, value)| {
367            Attribute {
368                name,
369                hash: ContentHash(*blake3::hash(&value).as_bytes()),
370            }
371        })
372        .collect()
373}
374
375/// The state of a symbolic link to `target`, which leads into `/proc` or `/sys`:
376/// the target, with an untracked pointee.
377fn untracked_link(target: PathBuf) -> PathState {
378    PathState::Symlink {
379        target,
380        pointee: Box::new(PathState::Untracked),
381    }
382}
383
384/// The state of `path`, which a step touched with `kinds`, without following a
385/// final symbolic link. A regular file is hashed when it was read or run, through
386/// the cache `states`, or when `force_hash` is set, read again without the cache.
387#[must_use]
388pub fn path_state(
389    path: &Path,
390    kinds: AccessKinds,
391    force_hash: bool,
392    states: &FileStates,
393) -> PathState {
394    let metadata = match fs::symlink_metadata(path) {
395        Ok(metadata) => metadata,
396        Err(error) => return failed(&error),
397    };
398    if !metadata.file_type().is_symlink() {
399        return state_of(path, &metadata, kinds, force_hash, states);
400    }
401    let target = match fs::read_link(path) {
402        Ok(target) => target,
403        Err(error) => return failed(&error),
404    };
405    let pointee = match fs::metadata(path) {
406        Ok(metadata) => state_of(path, &metadata, kinds, force_hash, states),
407        Err(error) => failed(&error),
408    };
409    PathState::Symlink {
410        target,
411        pointee: Box::new(pointee),
412    }
413}
414
415/// The state for an error from reading a path's state: absent when nothing is
416/// there, otherwise inaccessible.
417pub(crate) fn failed(error: &io::Error) -> PathState {
418    match error.kind() {
419        io::ErrorKind::NotFound | io::ErrorKind::NotADirectory => PathState::Absent,
420        _ => {
421            PathState::Inaccessible {
422                errno: error.raw_os_error().unwrap_or(0),
423            }
424        },
425    }
426}
427
428/// The state of `path`, whose metadata, with links followed or not, is `metadata`.
429fn state_of(
430    path: &Path,
431    metadata: &Metadata,
432    kinds: AccessKinds,
433    force_hash: bool,
434    states: &FileStates,
435) -> PathState {
436    let file_type = metadata.file_type();
437    if file_type.is_file() {
438        let meta = file_meta(metadata);
439        let hash = if force_hash {
440            Some(states.hash_uncached(path))
441        } else if kinds.contains(AccessKind::Read) || kinds.contains(AccessKind::Exec) {
442            Some(states.hash(path, &meta))
443        } else {
444            None
445        };
446        let hash = match hash.transpose() {
447            Ok(hash) => hash,
448            Err(error) => return failed(&error),
449        };
450        PathState::File { meta, hash }
451    } else if file_type.is_dir() {
452        let listing = if kinds.contains(AccessKind::List) {
453            match list(path) {
454                Ok(listing) => Some(listing),
455                Err(error) => return failed(&error),
456            }
457        } else {
458            None
459        };
460        PathState::Directory {
461            mode: metadata.mode(),
462            owner: owner(metadata),
463            listing,
464            times: times(metadata),
465        }
466    } else {
467        PathState::Special {
468            kind: special_kind(file_type),
469        }
470    }
471}
472
473/// The type of a path that is neither a regular file, a directory, nor a link.
474pub(crate) fn special_kind(file_type: FileType) -> SpecialKind {
475    if file_type.is_block_device() {
476        SpecialKind::BlockDevice
477    } else if file_type.is_char_device() {
478        SpecialKind::CharDevice
479    } else if file_type.is_fifo() {
480        SpecialKind::Fifo
481    } else if file_type.is_socket() {
482        SpecialKind::Socket
483    } else {
484        SpecialKind::Other
485    }
486}
487
488/// A time in nanoseconds since the Unix epoch from its seconds and nanoseconds.
489const fn nanos(
490    seconds: i64,
491    nanoseconds: i64,
492) -> i64 {
493    seconds
494        .saturating_mul(NANOS_PER_SECOND)
495        .saturating_add(nanoseconds)
496}
497
498/// The modification and change times of a regular file or a directory whose
499/// metadata is `metadata`.
500pub(crate) fn times(metadata: &Metadata) -> Times {
501    Times {
502        mtime_nanos: nanos(metadata.mtime(), metadata.mtime_nsec()),
503        ctime_nanos: nanos(metadata.ctime(), metadata.ctime_nsec()),
504    }
505}
506
507/// The metadata of a regular file that a cache check compares.
508pub(crate) fn file_meta(metadata: &Metadata) -> FileMeta {
509    let Times {
510        mtime_nanos,
511        ctime_nanos,
512    } = times(metadata);
513    FileMeta {
514        size: metadata.size(),
515        mtime_nanos,
516        ctime_nanos,
517        inode: metadata.ino(),
518        device: metadata.dev(),
519        mode: metadata.mode(),
520        owner: owner(metadata),
521    }
522}
523
524/// The owner of a file or directory whose metadata is `metadata`.
525pub(crate) fn owner(metadata: &Metadata) -> Owner {
526    Owner {
527        uid: metadata.uid(),
528        gid: metadata.gid(),
529    }
530}
531
532/// The type of a directory entry.
533fn entry_kind(file_type: FileType) -> EntryKind {
534    if file_type.is_file() {
535        EntryKind::File
536    } else if file_type.is_dir() {
537        EntryKind::Directory
538    } else if file_type.is_symlink() {
539        EntryKind::Symlink
540    } else if file_type.is_block_device() {
541        EntryKind::BlockDevice
542    } else if file_type.is_char_device() {
543        EntryKind::CharDevice
544    } else if file_type.is_fifo() {
545        EntryKind::Fifo
546    } else if file_type.is_socket() {
547        EntryKind::Socket
548    } else {
549        EntryKind::Unknown
550    }
551}
552
553/// The listing of the directory at `path`, with its entries in the order the file
554/// system returns them (see [`listing`]).
555pub(crate) fn list(path: &Path) -> io::Result<Listing> {
556    let mut entries = Vec::new();
557    for entry in fs::read_dir(path)? {
558        let entry = entry?;
559        let kind = entry.file_type().map_or(EntryKind::Unknown, entry_kind);
560        entries.push(DirEntry {
561            name: entry.file_name().into_vec(),
562            kind,
563        });
564    }
565    Ok(listing(entries))
566}
567
568/// The listing of `entries`, in the order given: the hash of their names and types
569/// in that order, the hash of the same entries sorted by name and type, and the
570/// entries in that order when there are at most [`MAX_LISTED_NAMES`].
571#[must_use]
572pub fn listing(entries: Vec<DirEntry>) -> Listing {
573    let mut sorted: Vec<&DirEntry> = entries.iter().collect();
574    sorted.sort();
575    let sorted_hash = listing_hash(sorted);
576    Listing {
577        hash: listing_hash(&entries),
578        sorted_hash,
579        entries: (entries.len() <= MAX_LISTED_NAMES).then_some(entries),
580    }
581}
582
583/// The hash of `entries`, in the order given: for each entry, the length of its
584/// name as eight little-endian bytes, the name, and the code of its type.
585fn listing_hash<'a>(entries: impl IntoIterator<Item = &'a DirEntry>) -> ContentHash {
586    let mut hasher = blake3::Hasher::new_derive_key(LISTING_CONTEXT);
587    for entry in entries {
588        let length = u64::try_from(entry.name.len()).unwrap_or(u64::MAX);
589        hasher.update(&length.to_le_bytes());
590        hasher.update(&entry.name);
591        hasher.update(&[entry.kind.code()]);
592    }
593    ContentHash(*hasher.finalize().as_bytes())
594}
595
596/// The files that changed during a run after the command first read them or ran
597/// them, sorted by path: each path in `first_reads` whose recorded state in
598/// `observations`, following a final symbolic link, is not a regular file with the
599/// noted device, inode, size, modification and change times, mode, and owner.
600/// No file, another type, and an inaccessible path are changes too. Each says
601/// whether the command wrote the path, as its access kinds show.
602///
603/// A path that no observation holds, because an ignore pattern matched it, is not
604/// compared, and neither is a path under `/proc` or `/sys`, or one that symbolic
605/// links lead there, tracked or not.
606#[must_use]
607pub fn changed_after_read(
608    observations: &[Observation],
609    first_reads: &FirstReads,
610) -> Vec<ChangedRead> {
611    first_reads
612        .iter()
613        .filter_map(|(path, noted)| {
614            let path = path.as_path();
615            let index = observations
616                .binary_search_by(|observation| observation.path.as_path().cmp(path))
617                .ok()?;
618            let observation = observations.get(index)?;
619            if observation.tracked || is_kernel_path(path) {
620                return None;
621            }
622            let unchanged = same_file(&observation.state, noted)?;
623            (!unchanged).then(|| {
624                ChangedRead {
625                    path: path.to_path_buf(),
626                    written: observation.access.contains(AccessBits::WRITE),
627                }
628            })
629        })
630        .collect()
631}
632
633/// Whether the recorded `state`, following a final symbolic link, is the regular
634/// file that `noted` describes, unchanged; `None` when the state is untracked, so
635/// it is not compared.
636fn same_file(
637    state: &PathState,
638    noted: &FileMetadata,
639) -> Option<bool> {
640    match state {
641        PathState::Untracked => None,
642        PathState::Symlink { pointee, .. } => same_file(pointee, noted),
643        PathState::File { meta, .. } => {
644            Some(
645                meta.device == noted.device
646                    && meta.inode == noted.inode
647                    && meta.size == noted.size
648                    && meta.mtime_nanos == noted.mtime_nanos
649                    && meta.ctime_nanos == noted.ctime_nanos
650                    && meta.mode == noted.mode
651                    && meta.owner
652                        == (Owner {
653                            uid: noted.uid,
654                            gid: noted.gid,
655                        }),
656            )
657        },
658        PathState::Absent
659        | PathState::Directory { .. }
660        | PathState::Special { .. }
661        | PathState::Inaccessible { .. } => Some(false),
662    }
663}
664
665/// Unit tests for listing hashes, for recognizing paths that lead into `/proc` and
666/// `/sys`, and for comparing first reads with recorded states.
667#[cfg(test)]
668#[allow(
669    clippy::disallowed_macros,
670    clippy::disallowed_methods,
671    reason = "test code: the tests assert and lock"
672)]
673mod tests {
674    use std::os::unix::fs::symlink;
675
676    use super::*;
677
678    /// A regular-file entry named `name`.
679    fn entry(name: &str) -> DirEntry {
680        DirEntry {
681            name: name.as_bytes().to_vec(),
682            kind: EntryKind::File,
683        }
684    }
685
686    /// The noted metadata of a regular file with `inode`.
687    fn noted(inode: u64) -> FileMetadata {
688        FileMetadata {
689            device: 1,
690            inode,
691            size: 2,
692            mtime_nanos: 3,
693            ctime_nanos: 4,
694            mode: 0o100_644,
695            uid: 5,
696            gid: 6,
697        }
698    }
699
700    /// The recorded state of the regular file that `noted(inode)` describes.
701    fn file(inode: u64) -> PathState {
702        PathState::File {
703            meta: FileMeta {
704                size: 2,
705                mtime_nanos: 3,
706                ctime_nanos: 4,
707                inode,
708                device: 1,
709                mode: 0o100_644,
710                owner: Owner { uid: 5, gid: 6 },
711            },
712            hash: None,
713        }
714    }
715
716    /// An observation of `path` with `access` and `state`.
717    fn observed(
718        path: &str,
719        access: u8,
720        tracked: bool,
721        state: PathState,
722    ) -> Observation {
723        Observation {
724            path: PathBuf::from(path),
725            access: AccessBits(access),
726            tracked,
727            state,
728            attributes: None,
729        }
730    }
731
732    /// Each noted file is compared with its final state through a final link; any
733    /// differing field, another type, or no file is a change, with whether the
734    /// command wrote the path; ignored, untracked and tracked kernel paths are not
735    /// compared.
736    #[test]
737    fn first_reads_are_compared_with_the_recorded_states() {
738        let read = AccessBits::READ;
739        let written = AccessBits::READ | AccessBits::WRITE;
740        let link = |state| {
741            PathState::Symlink {
742                target: PathBuf::from("t"),
743                pointee: Box::new(state),
744            }
745        };
746        let mut moved = file(1);
747        if let PathState::File { meta, .. } = &mut moved {
748            meta.mode = 0o100_600;
749        }
750        let observations = vec![
751            observed("/p/absent", written, false, PathState::Absent),
752            observed("/p/dir", read, false, PathState::Directory {
753                mode: 0o040_755,
754                owner: Owner { uid: 5, gid: 6 },
755                listing: None,
756                times: Times {
757                    mtime_nanos: 3,
758                    ctime_nanos: 4,
759                },
760            }),
761            observed("/p/link-other", written, false, link(file(9))),
762            observed("/p/link-same", read, false, link(file(1))),
763            observed("/p/mode", read, false, moved),
764            observed("/p/same", read, false, file(1)),
765            observed("/proc/version", read, true, file(9)),
766            observed("/sys/kernel", read, false, PathState::Untracked),
767            observed("/x/untracked", read, false, link(PathState::Untracked)),
768        ];
769        let mut first_reads = FirstReads::new();
770        let accesses = Accesses::new();
771        for path in [
772            "/p/absent",
773            "/p/dir",
774            "/p/ignored",
775            "/p/link-other",
776            "/p/link-same",
777            "/p/mode",
778            "/p/same",
779            "/proc/version",
780            "/sys/kernel",
781            "/x/untracked",
782        ] {
783            first_reads.note(&AbsolutePath::new(path).unwrap(), noted(1), &accesses);
784        }
785        let changed: Vec<(String, bool)> = changed_after_read(&observations, &first_reads)
786            .into_iter()
787            .map(|file| (file.path.display().to_string(), file.written))
788            .collect();
789        assert_eq!(changed, [
790            ("/p/absent".to_owned(), true),
791            ("/p/dir".to_owned(), false),
792            ("/p/link-other".to_owned(), true),
793            ("/p/mode".to_owned(), false),
794        ]);
795    }
796
797    /// The same entries in two orders have different listing hashes and the same
798    /// sorted hash, and the same entries in the same order have the same hashes.
799    #[test]
800    fn order_changes_the_listing_hash_and_not_the_sorted_hash() {
801        let forward = listing(vec![entry("a"), entry("b"), entry("c")]);
802        let backward = listing(vec![entry("c"), entry("b"), entry("a")]);
803        assert_ne!(forward.hash, backward.hash);
804        assert_eq!(forward.sorted_hash, backward.sorted_hash);
805        let again = listing(vec![entry("a"), entry("b"), entry("c")]);
806        assert_eq!(again, forward);
807        // Sorted entries hash the same both ways; other entries hash differently.
808        assert_eq!(forward.hash, forward.sorted_hash);
809        let other = listing(vec![entry("a"), entry("b")]);
810        assert_ne!(other.sorted_hash, forward.sorted_hash);
811        // A type is part of an entry.
812        let retyped = listing(vec![entry("a"), entry("b"), DirEntry {
813            name: b"c".to_vec(),
814            kind: EntryKind::Directory,
815        }]);
816        assert_ne!(retyped.sorted_hash, forward.sorted_hash);
817        assert_eq!(
818            backward.entries,
819            Some(vec![entry("c"), entry("b"), entry("a")])
820        );
821    }
822
823    /// A listing keeps the entries in the order the file system returns them, and
824    /// keeps them only up to the limit, while both hashes cover every entry.
825    #[test]
826    fn listings_keep_the_file_system_order_up_to_the_limit() {
827        let dir = tempfile::tempdir().unwrap();
828        for name in ["m", "a", "z", "k"] {
829            fs::write(dir.path().join(name), "").unwrap();
830        }
831        fs::create_dir(dir.path().join("d")).unwrap();
832        let returned: Vec<DirEntry> = fs::read_dir(dir.path())
833            .unwrap()
834            .map(|entry| {
835                let entry = entry.unwrap();
836                DirEntry {
837                    name: entry.file_name().into_vec(),
838                    kind: entry_kind(entry.file_type().unwrap()),
839                }
840            })
841            .collect();
842        let listed = list(dir.path()).unwrap();
843        assert_eq!(listed, listing(returned.clone()));
844        assert_eq!(listed.entries, Some(returned));
845
846        let many: Vec<DirEntry> = (0..=MAX_LISTED_NAMES)
847            .map(|index| entry(&index.to_string()))
848            .collect();
849        let large = listing(many.clone());
850        assert_eq!(large.entries, None);
851        let fewer = listing(many.iter().skip(1).cloned().collect());
852        assert_ne!(large.hash, fewer.hash);
853        assert_ne!(large.sorted_hash, fewer.sorted_hash);
854    }
855
856    /// Paths under `/proc` and `/sys`, and the standard links into them, reach a
857    /// kernel interface.
858    #[test]
859    fn kernel_paths_and_the_standard_links_into_them_reach_the_kernel() {
860        for path in ["/proc/version", "/sys/kernel", "/dev/fd/0", "/dev/stdin"] {
861            assert!(reaches_kernel(Path::new(path)), "{path}");
862        }
863    }
864
865    /// A directory link, a final link, a chain of links, and a relative link that
866    /// lead into `/proc` or `/sys` reach a kernel interface.
867    #[test]
868    fn links_that_lead_into_proc_or_sys_reach_the_kernel() {
869        let dir = tempfile::tempdir().unwrap();
870        let root = dir.path().canonicalize().unwrap();
871        symlink("/proc/self/fd", root.join("fd")).unwrap();
872        symlink("/proc/self/fd/0", root.join("stdin")).unwrap();
873        symlink("stdin", root.join("chain")).unwrap();
874        let up = "../".repeat(root.components().count().saturating_sub(1));
875        symlink(format!("{up}sys/kernel"), root.join("relative")).unwrap();
876        for name in ["fd/0", "fd/1", "stdin", "chain", "relative"] {
877            assert!(reaches_kernel(&root.join(name)), "{name}");
878        }
879    }
880
881    /// Files, links to files, missing paths, dangling links, and link loops do not
882    /// reach a kernel interface, and the loop ends.
883    #[test]
884    fn other_paths_do_not_reach_the_kernel() {
885        let dir = tempfile::tempdir().unwrap();
886        let root = dir.path().canonicalize().unwrap();
887        fs::write(root.join("file"), "content").unwrap();
888        symlink("file", root.join("to-file")).unwrap();
889        symlink("missing", root.join("dangling")).unwrap();
890        symlink("loop-b", root.join("loop-a")).unwrap();
891        symlink("loop-a", root.join("loop-b")).unwrap();
892        for name in [
893            "file",
894            "to-file",
895            "missing",
896            "missing/below",
897            "dangling",
898            "loop-a",
899        ] {
900            assert!(!reaches_kernel(&root.join(name)), "{name}");
901        }
902        assert!(!reaches_kernel(Path::new("/")));
903    }
904
905    /// The links that lead a path into `/proc` or `/sys` are listed with their
906    /// targets, in lookup order, at the places a lookup finds them, and no link
907    /// under `/proc` or `/sys` is among them.
908    #[test]
909    fn the_links_that_lead_into_proc_or_sys_are_listed() {
910        let dir = tempfile::tempdir().unwrap();
911        let root = dir.path().canonicalize().unwrap();
912        fs::create_dir(root.join("real")).unwrap();
913        symlink("/proc/self/fd", root.join("real/fd")).unwrap();
914        symlink("real", root.join("alias")).unwrap();
915        symlink("/proc/self/fd/0", root.join("stdin")).unwrap();
916        symlink("stdin", root.join("chain")).unwrap();
917        let link = |path: &Path, target: &str| (path.to_path_buf(), PathBuf::from(target));
918        assert_eq!(kernel_links(Path::new("/proc/self/fd/0")), Some(Vec::new()));
919        assert_eq!(
920            kernel_links(&root.join("real/fd/1")),
921            Some(vec![link(&root.join("real/fd"), "/proc/self/fd")])
922        );
923        assert_eq!(
924            kernel_links(&root.join("alias/fd/1")),
925            Some(vec![
926                link(&root.join("alias"), "real"),
927                link(&root.join("real/fd"), "/proc/self/fd"),
928            ])
929        );
930        assert_eq!(
931            kernel_links(&root.join("chain")),
932            Some(vec![
933                link(&root.join("chain"), "stdin"),
934                link(&root.join("stdin"), "/proc/self/fd/0"),
935            ])
936        );
937        assert_eq!(kernel_links(&root.join("real")), None);
938    }
939
940    /// Only a path whose own final component is a link outside `/proc` and `/sys`
941    /// keeps a link target: a path reached through a directory link into them, such
942    /// as `/dev/fd/0`, is the `/proc` object itself, even though that is a link too.
943    #[test]
944    fn only_a_final_link_outside_proc_and_sys_keeps_its_target() {
945        let dir = tempfile::tempdir().unwrap();
946        let root = dir.path().canonicalize().unwrap();
947        fs::create_dir(root.join("real")).unwrap();
948        symlink("/proc/self/fd", root.join("real/fd")).unwrap();
949        symlink("real", root.join("alias")).unwrap();
950        symlink("/proc/self/fd/0", root.join("real/stdin")).unwrap();
951        let own = |path: &Path| kernel_route(path).map(|route| route.own_target);
952        assert_eq!(own(Path::new("/proc/self/fd/0")), Some(None));
953        assert_eq!(own(&root.join("real/fd/0")), Some(None));
954        assert_eq!(own(&root.join("alias/fd/0")), Some(None));
955        assert_eq!(
956            own(&root.join("real/fd")),
957            Some(Some(PathBuf::from("/proc/self/fd")))
958        );
959        assert_eq!(
960            own(&root.join("alias/stdin")),
961            Some(Some(PathBuf::from("/proc/self/fd/0")))
962        );
963        assert_eq!(own(&root.join("alias")), None);
964    }
965}