Skip to main content

kizz_core/
lookup.rs

1// Copyright (c) 2026 Sakura Industries LLC.
2//
3// SPDX-License-Identifier: AGPL-3.0-only
4
5//! Program lookup through an environment's `PATH`.
6//!
7//! A program name without `/` is looked up in the `PATH` of the environment that
8//! the program gets: for a step, the task environment, never kizz's own; for
9//! `kizz execute`, the caller's. Each directory of `PATH` is tried in order, as
10//! `execvp` does: an empty entry means the working directory, and a relative entry
11//! resolves against it. Every location checked is reported as a probe, so it
12//! becomes a dependency of the step and a program that appears earlier in `PATH`
13//! re-runs the step. The first location that holds a regular file with an execute
14//! bit is the program.
15//!
16//! A program name with `/` is not looked up: it resolves against the working
17//! directory, and the tracer reports whether it can be run.
18//!
19//! [`search_program`] is the lookup itself, for any name and `PATH` of bytes, and
20//! reports each checked location with its outcome: `ok` when something is there,
21//! and otherwise the name of the error, which it gets from the caller, such as the
22//! tracer's error-name query ([`kizz_trace::Tracer::error_name`]).
23//! [`find_program`] is the lookup of `run()`, for a task environment of strings,
24//! with the checked locations as accesses; [`search_step_program`] is the same
25//! lookup with each checked location's outcome, for the report of `kizz run
26//! --output`. [`check_path`] is the check that such a lookup can be made at all,
27//! from the program name and the environment alone, which the engine makes before
28//! the cache check.
29
30use std::{
31    collections::BTreeMap,
32    ffi::OsStr,
33    fs,
34    os::unix::{ffi::OsStrExt as _, fs::PermissionsExt as _},
35};
36
37use kizz_trace::{AbsolutePath, AccessKind, Accesses, Observations, Outcome};
38
39/// The variable that lists the directories to search for programs.
40pub const PATH_VARIABLE: &str = "PATH";
41
42/// The permission bits that make a file executable by someone.
43const EXECUTE_BITS: u32 = 0o111;
44
45/// The result of looking up a program.
46#[derive(Debug, Clone, PartialEq, Eq)]
47pub enum ProgramLookup {
48    /// The program was found.
49    Found {
50        /// The absolute path of the program.
51        program: AbsolutePath,
52        /// Every location checked, the program's included, as probes.
53        checked: Accesses,
54    },
55    /// No location holds the program.
56    NotFound {
57        /// Every location checked, as probes.
58        checked: Accesses,
59    },
60    /// A location holds the program, but it is not an executable regular file, and
61    /// no later location holds an executable one.
62    NotExecutable {
63        /// The first location that holds the program.
64        candidate: AbsolutePath,
65        /// Every location checked, as probes.
66        checked: Accesses,
67    },
68}
69
70impl ProgramLookup {
71    /// Every location checked, as probes.
72    #[must_use]
73    pub const fn checked(&self) -> &Accesses {
74        match self {
75            Self::Found { checked, .. }
76            | Self::NotFound { checked }
77            | Self::NotExecutable { checked, .. } => checked,
78        }
79    }
80}
81
82/// The result of [`search_program`]: the result of a lookup, with every location
83/// that it checked as a probe with its outcome.
84#[derive(Debug, Clone, PartialEq, Eq)]
85pub enum ProgramSearch {
86    /// The program was found.
87    Found {
88        /// The absolute path of the program.
89        program: AbsolutePath,
90        /// Every location checked, the program's included, as probes.
91        checked: Observations,
92    },
93    /// No location holds the program.
94    NotFound {
95        /// Every location checked, as probes.
96        checked: Observations,
97    },
98    /// A location holds the program, but it is not an executable regular file, and
99    /// no later location holds an executable one.
100    NotExecutable {
101        /// The first location that holds the program.
102        candidate: AbsolutePath,
103        /// Every location checked, as probes.
104        checked: Observations,
105    },
106}
107
108impl ProgramSearch {
109    /// Every location checked, as probes with their outcomes.
110    #[must_use]
111    pub const fn checked(&self) -> &Observations {
112        match self {
113            Self::Found { checked, .. }
114            | Self::NotFound { checked }
115            | Self::NotExecutable { checked, .. } => checked,
116        }
117    }
118
119    /// The same result as a [`ProgramLookup`], whose checked locations are
120    /// accesses without outcomes.
121    #[must_use]
122    pub fn into_lookup(self) -> ProgramLookup {
123        match self {
124            Self::Found { program, checked } => {
125                ProgramLookup::Found {
126                    program,
127                    checked: checked.accesses(),
128                }
129            },
130            Self::NotFound { checked } => {
131                ProgramLookup::NotFound {
132                    checked: checked.accesses(),
133                }
134            },
135            Self::NotExecutable { candidate, checked } => {
136                ProgramLookup::NotExecutable {
137                    candidate,
138                    checked: checked.accesses(),
139                }
140            },
141        }
142    }
143}
144
145/// A bare program name in a task environment without `PATH`.
146#[derive(Debug, Clone, PartialEq, Eq, thiserror::Error)]
147#[error(
148    "cannot run `{program}`: a program name without `/` is looked up in the task \
149     environment's PATH, but the task environment has no PATH; set it with \
150     env.set(\"PATH\", ...) or inherit it with env.inherit(\"PATH\")"
151)]
152pub struct NoPathError {
153    /// The program name.
154    pub program: String,
155}
156
157/// Check that the program `name` of a step whose environment is `env` can be
158/// looked up: a name with `/` needs no lookup, and any other name needs a `PATH`
159/// in `env`. The check reads only these two values, so it gives the same answer
160/// every time, as [`search_step_program`] does for a missing `PATH`.
161///
162/// # Errors
163///
164/// Returns [`NoPathError`] when `name` has no `/` and `env` has no `PATH`.
165pub fn check_path(
166    name: &str,
167    env: &BTreeMap<String, String>,
168) -> Result<(), NoPathError> {
169    if name.contains('/') || env.contains_key(PATH_VARIABLE) {
170        Ok(())
171    } else {
172        Err(NoPathError {
173            program: name.to_owned(),
174        })
175    }
176}
177
178/// Look up the program `name` for a step whose environment is `env` and whose
179/// working directory is `cwd`, with [`search_program`].
180///
181/// # Errors
182///
183/// Returns [`NoPathError`] when `name` has no `/` and `env` has no `PATH`.
184pub fn find_program(
185    name: &str,
186    env: &BTreeMap<String, String>,
187    cwd: &AbsolutePath,
188) -> Result<ProgramLookup, NoPathError> {
189    search_step_program(name, env, cwd, kizz_trace::unnamed_error).map(ProgramSearch::into_lookup)
190}
191
192/// Look up the program `name` for a step whose environment is `env` and whose
193/// working directory is `cwd`, as [`find_program`] does, keeping the outcome of
194/// each checked location, whose error `error_name` names, for the observation
195/// report of `kizz run --output`.
196///
197/// # Errors
198///
199/// Returns [`NoPathError`] when `name` has no `/` and `env` has no `PATH`.
200pub fn search_step_program(
201    name: &str,
202    env: &BTreeMap<String, String>,
203    cwd: &AbsolutePath,
204    error_name: impl Fn(i32) -> String,
205) -> Result<ProgramSearch, NoPathError> {
206    let search = env.get(PATH_VARIABLE).map(OsStr::new);
207    search_program(OsStr::new(name), search, cwd, error_name).ok_or_else(|| {
208        NoPathError {
209            program: name.to_owned(),
210        }
211    })
212}
213
214/// Look up the program `name` in `search`, the value of `PATH`, or `None` when the
215/// environment has no `PATH`, for a program whose working directory is `cwd`.
216/// Each checked location is a probe whose outcome is `ok` when something is there,
217/// and otherwise the name that `error_name` gives the error number of the failed
218/// check, or `unknown` when the failure has no number.
219///
220/// A name with `/` is found at once, resolved against `cwd`, with nothing checked.
221/// An empty name is not found, with nothing checked.
222///
223/// Returns `None` when `name` has no `/` and `search` is `None`, since such a name
224/// cannot be looked up.
225pub fn search_program(
226    name: &OsStr,
227    search: Option<&OsStr>,
228    cwd: &AbsolutePath,
229    error_name: impl Fn(i32) -> String,
230) -> Option<ProgramSearch> {
231    if name.as_bytes().contains(&b'/') {
232        return Some(ProgramSearch::Found {
233            program: cwd.join(name),
234            checked: Observations::new(),
235        });
236    }
237    let search = search?;
238    let mut checked = Observations::new();
239    if name.is_empty() {
240        return Some(ProgramSearch::NotFound { checked });
241    }
242    let mut not_executable = None;
243    for entry in search.as_bytes().split(|byte| *byte == b':') {
244        let candidate = cwd.join(OsStr::from_bytes(entry)).join(name);
245        let metadata = match fs::metadata(candidate.as_path()) {
246            Ok(metadata) => metadata,
247            Err(error) => {
248                let outcome = error
249                    .raw_os_error()
250                    .map_or(Outcome::Unknown, |errno| Outcome::Error(error_name(errno)));
251                checked.record(candidate, AccessKind::Probe, outcome);
252                continue;
253            },
254        };
255        checked.record(candidate.clone(), AccessKind::Probe, Outcome::Ok);
256        if metadata.is_file() && metadata.permissions().mode() & EXECUTE_BITS != 0 {
257            return Some(ProgramSearch::Found {
258                program: candidate,
259                checked,
260            });
261        }
262        not_executable.get_or_insert(candidate);
263    }
264    Some(match not_executable {
265        Some(candidate) => ProgramSearch::NotExecutable { candidate, checked },
266        None => ProgramSearch::NotFound { checked },
267    })
268}
269
270/// Unit tests of the lookup.
271#[cfg(test)]
272#[allow(clippy::disallowed_macros, reason = "test code: the tests assert")]
273mod tests {
274    use std::{
275        collections::BTreeMap, ffi::OsStr, fs, os::unix::fs::PermissionsExt as _, path::Path,
276    };
277
278    use kizz_trace::{AbsolutePath, AccessKind, Observations, Outcome};
279
280    use super::{
281        NoPathError, ProgramLookup, ProgramSearch, check_path, find_program, search_program,
282        search_step_program,
283    };
284
285    /// The name that the tests give each error number.
286    fn named(errno: i32) -> String {
287        format!("E{errno}")
288    }
289
290    /// A temporary directory with `bin/tool`, executable, and `text/tool`, not
291    /// executable, and the directory as an absolute path.
292    fn fixture() -> Result<(tempfile::TempDir, AbsolutePath), Box<dyn std::error::Error>> {
293        let dir = tempfile::tempdir()?;
294        let root = AbsolutePath::new(dir.path().canonicalize()?)?;
295        for (sub, mode) in [("bin", 0o755), ("text", 0o644)] {
296            fs::create_dir(root.as_path().join(sub))?;
297            let tool = root.as_path().join(sub).join("tool");
298            fs::write(&tool, "#!/bin/sh\n")?;
299            fs::set_permissions(&tool, fs::Permissions::from_mode(mode))?;
300        }
301        Ok((dir, root))
302    }
303
304    /// The probe of `path` with the outcome `outcome`, added to `observations`.
305    fn probe(
306        observations: &mut Observations,
307        path: &Path,
308        outcome: Outcome,
309    ) {
310        observations.record(AbsolutePath::new(path).unwrap(), AccessKind::Probe, outcome);
311    }
312
313    /// The search reports each checked location with its outcome: the error's name
314    /// for a location where nothing is, and `ok` for one where something is, the
315    /// found program's included; `find_program` gives the same locations as
316    /// accesses.
317    #[test]
318    fn each_checked_location_has_its_outcome() -> Result<(), Box<dyn std::error::Error>> {
319        let (_dir, root) = fixture()?;
320        let missing = root.as_path().join("missing");
321        let bin = root.as_path().join("bin");
322        let search = format!("{}:{}", missing.display(), bin.display());
323        let found = search_program(OsStr::new("tool"), Some(OsStr::new(&search)), &root, named);
324        let mut checked = Observations::new();
325        probe(
326            &mut checked,
327            &missing.join("tool"),
328            Outcome::Error(named(2)),
329        );
330        probe(&mut checked, &bin.join("tool"), Outcome::Ok);
331        let program = AbsolutePath::new(bin.join("tool"))?;
332        assert_eq!(
333            found,
334            Some(ProgramSearch::Found {
335                program: program.clone(),
336                checked: checked.clone(),
337            })
338        );
339        let env = BTreeMap::from([("PATH".to_owned(), search)]);
340        assert_eq!(find_program("tool", &env, &root)?, ProgramLookup::Found {
341            program,
342            checked: checked.accesses(),
343        });
344        Ok(())
345    }
346
347    /// A location that holds a file without execute permission is checked with `ok`
348    /// and gives a program that is not executable; a name that no location holds is
349    /// not found; an empty name and a name with `/` check nothing; and a name
350    /// without `/` cannot be looked up without `PATH`.
351    #[test]
352    fn other_results_of_the_search() -> Result<(), Box<dyn std::error::Error>> {
353        let (_dir, root) = fixture()?;
354        let text = root.as_path().join("text");
355        let search = text.display().to_string();
356        let mut checked = Observations::new();
357        probe(&mut checked, &text.join("tool"), Outcome::Ok);
358        assert_eq!(
359            search_program(OsStr::new("tool"), Some(OsStr::new(&search)), &root, named),
360            Some(ProgramSearch::NotExecutable {
361                candidate: AbsolutePath::new(text.join("tool"))?,
362                checked,
363            })
364        );
365        let mut absent = Observations::new();
366        probe(&mut absent, &text.join("other"), Outcome::Error(named(2)));
367        assert_eq!(
368            search_program(OsStr::new("other"), Some(OsStr::new(&search)), &root, named),
369            Some(ProgramSearch::NotFound { checked: absent })
370        );
371        assert_eq!(
372            search_program(OsStr::new(""), Some(OsStr::new(&search)), &root, named),
373            Some(ProgramSearch::NotFound {
374                checked: Observations::new(),
375            })
376        );
377        assert_eq!(
378            search_program(OsStr::new("./tool"), None, &root, named),
379            Some(ProgramSearch::Found {
380                program: root.join("tool"),
381                checked: Observations::new(),
382            })
383        );
384        assert_eq!(search_program(OsStr::new("tool"), None, &root, named), None);
385        Ok(())
386    }
387
388    /// A bare name needs `PATH` in the environment, as the lookup itself does,
389    /// with the same error; a name with `/` and a name in an environment with
390    /// `PATH`, even an empty one, pass the check.
391    #[test]
392    fn the_check_for_path_agrees_with_the_lookup() -> Result<(), Box<dyn std::error::Error>> {
393        let (_dir, root) = fixture()?;
394        let none = BTreeMap::new();
395        let missing = NoPathError {
396            program: "tool".to_owned(),
397        };
398        assert_eq!(check_path("tool", &none), Err(missing.clone()));
399        assert_eq!(
400            search_step_program("tool", &none, &root, named),
401            Err(missing)
402        );
403        assert_eq!(
404            check_path("", &none),
405            Err(NoPathError {
406                program: String::new(),
407            })
408        );
409        assert_eq!(check_path("./tool", &none), Ok(()));
410        assert_eq!(check_path("bin/tool", &none), Ok(()));
411        let empty = BTreeMap::from([("PATH".to_owned(), String::new())]);
412        assert_eq!(check_path("tool", &empty), Ok(()));
413        assert!(search_step_program("tool", &empty, &root, named).is_ok());
414        Ok(())
415    }
416}