executables.rs
raw
//! Discovery of runnable commands from `$PATH`.
use std::collections::BTreeMap;
use std::env;
use std::fs;
use std::os::unix::fs::PermissionsExt;
use std::path::Path;
/// The set of executable command names found on `$PATH`.
///
/// Names are held sorted alphabetically and deduplicated, so a prefix match is
/// a contiguous range the binary search can find. Each carries the position of
/// the `$PATH` directory it came from, which is what results are ordered by —
/// see [`search_order`].
pub struct Executables {
entries: Vec<Entry>,
}
impl Executables {
/// Scan every directory on `$PATH` for executable files, collecting their
/// names. A name that appears in several directories is listed once,
/// belonging to the first (highest-priority) directory that has it — the
/// copy a shell would actually run.
pub fn from_path() -> Self {
let path = env::var_os("PATH").unwrap_or_default();
Self::from_dirs(env::split_paths(&path))
}
/// Build the command set from an explicit sequence of directories, in
/// search order. Split out from [`Executables::from_path`] so the scanning
/// logic is testable against a fixture tree without touching the process
/// environment.
pub fn from_dirs<I, P>(dirs: I) -> Self
where
I: IntoIterator<Item = P>,
P: AsRef<Path>,
{
// Keyed by name, so a name found more than once is kept once. The rank
// counts every directory on the way, readable or not, so it stays a
// true `$PATH` position.
let mut found: BTreeMap<String, usize> = BTreeMap::new();
for (rank, dir) in dirs.into_iter().enumerate() {
let entries = match fs::read_dir(dir.as_ref()) {
Ok(entries) => entries,
Err(_) => continue,
};
for entry in entries.flatten() {
if !is_executable_file(&entry) {
continue;
}
if let Ok(name) = entry.file_name().into_string() {
// Only the earliest directory's rank is kept: later copies
// are shadowed by it, exactly as they are when executing.
found.entry(name).or_insert(rank);
}
}
}
Self {
// A `BTreeMap` iterates in key order, so this comes out sorted by
// name — the invariant the prefix search depends on.
entries: found
.into_iter()
.map(|(name, rank)| Entry { name, rank })
.collect(),
}
}
/// The command names matching `query`, in [`search_order`], found by
/// falling back through progressively looser criteria:
///
/// 1. **prefix** — names beginning with `query`;
/// 2. **substring** — names containing `query` (case-sensitive);
/// 3. **case-insensitive substring** — names containing `query` ignoring case.
///
/// Each looser tier is consulted only when the tighter one finds nothing, so
/// an exact prefix is never diluted by substring hits. An empty query matches
/// nothing: the launcher shows suggestions only once the user has begun
/// typing, and never launches an arbitrary first-on-`$PATH` command.
///
/// Because the backing vector is sorted by name, the prefix tier is a
/// contiguous slice located with two binary searches; the fallback tiers
/// scan (cheap for a `$PATH`-sized list, and only reached when nothing
/// simpler matched). Whichever tier answers is then put into search order.
pub fn matching(&self, query: &str) -> Vec<&str> {
if query.is_empty() {
return Vec::new();
}
// Tier 1: prefix, as a contiguous range of the by-name ordering.
let start = self
.entries
.partition_point(|entry| entry.name.as_str() < query);
let end =
start + self.entries[start..].partition_point(|entry| entry.name.starts_with(query));
if end > start {
return search_order(self.entries[start..end].iter().collect(), |name| {
name == query
});
}
// Tier 2: case-sensitive substring.
let substring: Vec<&Entry> = self
.entries
.iter()
.filter(|entry| entry.name.contains(query))
.collect();
if !substring.is_empty() {
return search_order(substring, |name| name == query);
}
// Tier 3: case-insensitive substring. Exactness folds case the same way
// the matching does, so a typed `steam` promotes `Steam`.
let needle = query.to_lowercase();
search_order(
self.entries
.iter()
.filter(|entry| entry.name.to_lowercase().contains(&needle))
.collect(),
|name| name.to_lowercase() == needle,
)
}
/// The first command name matching `query` under the
/// [`matching`](Self::matching) fallback and ordering — the command whose
/// whole name was typed, if there is one, otherwise the candidate earliest
/// on `$PATH` and alphabetically first among its neighbours there — or
/// `None` when nothing matches. This is the command the launcher commits to
/// on space and runs on enter when the first candidate is highlighted.
pub fn first_match(&self, query: &str) -> Option<&str> {
self.matching(query).into_iter().next()
}
/// Total number of distinct commands discovered.
pub fn len(&self) -> usize {
self.entries.len()
}
/// Whether no commands were discovered at all.
pub fn is_empty(&self) -> bool {
self.entries.is_empty()
}
}
/// One discovered command.
struct Entry {
name: String,
/// Position on `$PATH` of the first directory holding this name — the copy
/// that would actually run, and what orders it among the results.
rank: usize,
}
/// Put candidates into the order the launcher lists them: an exact match for
/// what was typed first, then by `$PATH` position, then alphabetically within a
/// directory.
///
/// Typing a command's whole name says plainly which one you mean, so it leads
/// however late on `$PATH` it sits — without that, `git` from `/usr/bin` would
/// be displaced by `gitk` from a directory ahead of it.
///
/// What counts as exact is the caller's to decide, because it has to be judged
/// on the same terms the tier matched on: the case-sensitive tiers want an
/// identical name, while the case-insensitive one should promote `Steam` for a
/// typed `steam`. That tier is also the only one that can turn up more than one
/// exact match (`Steam` and `STEAM` both answer to `steam`); they simply fall
/// through to the same `$PATH` and alphabetical ordering as everything else.
///
/// `candidates` is drawn from a vector sorted by name and so arrives in
/// alphabetical order already; sorting it *stably* therefore leaves
/// same-directory names alphabetical, and that tie-break costs nothing.
fn search_order<'e>(
mut candidates: Vec<&'e Entry>,
is_exact: impl Fn(&str) -> bool,
) -> Vec<&'e str> {
// `false` orders before `true`, so the exact matches come first. The keys
// are cached rather than recomputed as the sort compares, since folding
// case allocates.
candidates.sort_by_cached_key(|entry| (!is_exact(&entry.name), entry.rank));
candidates
.into_iter()
.map(|entry| entry.name.as_str())
.collect()
}
/// Whether a directory entry is a file we would be willing to exec: a regular
/// file (or a symlink resolving to one) carrying an execute bit.
///
/// The metadata is resolved *through* symlinks ([`fs::metadata`] rather than
/// [`fs::DirEntry::metadata`], which stats the link itself). PATH entries are
/// very often symlinks to the real binary — flatpak app exports like
/// `com.valvesoftware.Steam`, or wrappers such as `/usr/bin/vi -> vim` — and we
/// want the target's file type and permissions, not the link's. A broken link
/// yields an error and is correctly rejected.
fn is_executable_file(entry: &fs::DirEntry) -> bool {
let metadata = match fs::metadata(entry.path()) {
Ok(metadata) => metadata,
Err(_) => return false,
};
metadata.is_file() && metadata.permissions().mode() & 0o111 != 0
}
#[cfg(test)]
mod tests {
use super::*;
use std::fs::{self, File};
use std::io::Write;
use std::os::unix::fs::PermissionsExt;
use std::path::PathBuf;
/// Create a throwaway directory tree under the scratch dir and populate it
/// with the named executables (and, optionally, plain files) so scanning
/// runs against real filesystem metadata rather than mocks.
struct Fixture {
root: PathBuf,
}
impl Fixture {
fn new(tag: &str) -> Self {
let root = std::env::temp_dir().join(format!("liftoff-test-{tag}"));
let _ = fs::remove_dir_all(&root);
fs::create_dir_all(&root).unwrap();
Fixture { root }
}
fn dir(&self, name: &str) -> PathBuf {
let dir = self.root.join(name);
fs::create_dir_all(&dir).unwrap();
dir
}
fn executable(&self, dir: &Path, name: &str) {
let path = dir.join(name);
let mut file = File::create(&path).unwrap();
file.write_all(b"#!/bin/sh\n").unwrap();
let mut perms = fs::metadata(&path).unwrap().permissions();
perms.set_mode(0o755);
fs::set_permissions(&path, perms).unwrap();
}
fn plain_file(&self, dir: &Path, name: &str) {
let path = dir.join(name);
let mut file = File::create(&path).unwrap();
file.write_all(b"not runnable\n").unwrap();
let mut perms = fs::metadata(&path).unwrap().permissions();
perms.set_mode(0o644);
fs::set_permissions(&path, perms).unwrap();
}
fn symlink(&self, dir: &Path, name: &str, target: &Path) {
std::os::unix::fs::symlink(target, dir.join(name)).unwrap();
}
}
impl Drop for Fixture {
fn drop(&mut self) {
let _ = fs::remove_dir_all(&self.root);
}
}
#[test]
fn collects_only_executables_deduped() {
let fx = Fixture::new("collect");
let bin = fx.dir("bin");
let usr_bin = fx.dir("usr-bin");
fx.executable(&bin, "firefox");
fx.executable(&bin, "git");
fx.executable(&usr_bin, "firejail");
fx.executable(&usr_bin, "git"); // duplicate name across dirs
fx.plain_file(&bin, "README"); // non-executable, ignored
let execs = Executables::from_dirs([&bin, &usr_bin]);
assert_eq!(execs.len(), 3);
assert_eq!(execs.matching("fir"), vec!["firefox", "firejail"]);
// "git" appears once despite being in both directories.
assert_eq!(execs.matching("git"), vec!["git"]);
}
/// Search order beats alphabetical order: a command in an earlier `$PATH`
/// directory is listed first even when its name sorts later.
#[test]
fn earlier_directories_are_listed_first() {
let fx = Fixture::new("path-order");
let first = fx.dir("first");
let second = fx.dir("second");
fx.executable(&first, "tool-z");
fx.executable(&second, "tool-a");
let execs = Executables::from_dirs([&first, &second]);
assert_eq!(execs.matching("tool"), vec!["tool-z", "tool-a"]);
assert_eq!(execs.first_match("tool"), Some("tool-z"));
}
/// Within one directory the tie is broken alphabetically, so the listing is
/// grouped by directory and sorted inside each group.
#[test]
fn names_from_one_directory_are_alphabetical() {
let fx = Fixture::new("tie-break");
let first = fx.dir("first");
let second = fx.dir("second");
fx.executable(&first, "tool-d");
fx.executable(&first, "tool-b");
fx.executable(&second, "tool-c");
fx.executable(&second, "tool-a");
let execs = Executables::from_dirs([&first, &second]);
assert_eq!(
execs.matching("tool"),
vec!["tool-b", "tool-d", "tool-a", "tool-c"]
);
}
/// A name in several directories is ranked by the first one that has it —
/// the copy that would actually run — not by the last one seen.
#[test]
fn a_shadowed_name_keeps_its_earliest_position() {
let fx = Fixture::new("shadowed");
let first = fx.dir("first");
let second = fx.dir("second");
fx.executable(&first, "tool-z"); // also in `second`, shadowing it
fx.executable(&second, "tool-a");
fx.executable(&second, "tool-z");
let execs = Executables::from_dirs([&first, &second]);
assert_eq!(execs.len(), 2);
assert_eq!(execs.matching("tool"), vec!["tool-z", "tool-a"]);
}
/// An unreadable directory still occupies its place on `$PATH`, so it does
/// not shift the ranks of the directories after it.
#[test]
fn a_missing_directory_does_not_shift_later_ranks() {
let fx = Fixture::new("missing-rank");
let first = fx.dir("first");
let second = fx.dir("second");
fx.executable(&first, "tool-z");
fx.executable(&second, "tool-a");
let with_gap =
Executables::from_dirs([first.as_path(), Path::new("/no/such/dir"), second.as_path()]);
assert_eq!(with_gap.matching("tool"), vec!["tool-z", "tool-a"]);
}
/// The fallback tiers list their hits in search order too, not just the
/// prefix tier.
#[test]
fn substring_fallbacks_use_search_order() {
let fx = Fixture::new("fallback-order");
let first = fx.dir("first");
let second = fx.dir("second");
fx.executable(&first, "zzz-tool"); // substring hit, earlier directory
fx.executable(&second, "aaa-tool"); // substring hit, later directory
let execs = Executables::from_dirs([&first, &second]);
// Nothing begins with "tool", so both are found by the substring tier.
assert_eq!(execs.matching("tool"), vec!["zzz-tool", "aaa-tool"]);
}
#[test]
fn follows_symlinks_to_executables() {
let fx = Fixture::new("symlinks");
let real = fx.dir("real");
let bin = fx.dir("bin");
fx.executable(&real, "steam-wrapper");
// Flatpak exports apps under dotted ids as symlinks to the real binary.
fx.symlink(&bin, "com.valvesoftware.Steam", &real.join("steam-wrapper"));
let execs = Executables::from_dirs([&bin]);
assert_eq!(execs.matching("com."), vec!["com.valvesoftware.Steam"]);
assert_eq!(execs.first_match("com"), Some("com.valvesoftware.Steam"));
}
#[test]
fn broken_symlinks_are_skipped() {
let fx = Fixture::new("broken-symlinks");
let bin = fx.dir("bin");
fx.symlink(&bin, "dangling", &bin.join("does-not-exist"));
let execs = Executables::from_dirs([&bin]);
assert!(execs.matching("dang").is_empty());
}
#[test]
fn missing_directories_are_skipped() {
let fx = Fixture::new("missing");
let bin = fx.dir("bin");
fx.executable(&bin, "vim");
let execs = Executables::from_dirs([bin.as_path(), Path::new("/no/such/dir")]);
assert_eq!(execs.matching("v"), vec!["vim"]);
}
#[test]
fn empty_prefix_matches_nothing() {
let fx = Fixture::new("empty");
let bin = fx.dir("bin");
fx.executable(&bin, "alpha");
fx.executable(&bin, "beta");
let execs = Executables::from_dirs([&bin]);
assert!(execs.matching("").is_empty());
assert_eq!(execs.first_match(""), None);
}
#[test]
fn an_exact_name_is_listed_first() {
let fx = Fixture::new("first");
let bin = fx.dir("bin");
// Typing a whole command name and hitting space commits that name, not a
// sibling that merely extends it.
fx.executable(&bin, "git");
fx.executable(&bin, "gitk");
fx.executable(&bin, "git-lfs");
let execs = Executables::from_dirs([&bin]);
assert_eq!(execs.first_match("git"), Some("git"));
assert_eq!(execs.matching("git"), vec!["git", "git-lfs", "gitk"]);
}
/// An exact name outranks `$PATH` position: it leads even when a directory
/// ahead of it holds a longer name that also matches.
#[test]
fn an_exact_name_outranks_an_earlier_directory() {
let fx = Fixture::new("exact-beats-path");
let local = fx.dir("local");
let usr = fx.dir("usr");
fx.executable(&local, "gitk"); // earlier directory, longer name
fx.executable(&usr, "git"); // later directory, exactly what was typed
let execs = Executables::from_dirs([&local, &usr]);
assert_eq!(execs.first_match("git"), Some("git"));
assert_eq!(execs.matching("git"), vec!["git", "gitk"]);
}
/// Promoting the exact name does not otherwise disturb the ordering: the
/// rest stay in `$PATH` order behind it.
#[test]
fn the_remaining_matches_keep_search_order() {
let fx = Fixture::new("exact-then-path");
let first = fx.dir("first");
let second = fx.dir("second");
fx.executable(&first, "tool-z");
fx.executable(&second, "tool"); // exact, but last on `$PATH`
fx.executable(&second, "tool-a");
let execs = Executables::from_dirs([&first, &second]);
assert_eq!(execs.matching("tool"), vec!["tool", "tool-z", "tool-a"]);
}
#[test]
fn prefix_range_excludes_non_matches() {
let fx = Fixture::new("range");
let bin = fx.dir("bin");
fx.executable(&bin, "cargo");
fx.executable(&bin, "cat");
fx.executable(&bin, "curl");
fx.executable(&bin, "dd");
let execs = Executables::from_dirs([&bin]);
assert_eq!(execs.matching("ca"), vec!["cargo", "cat"]);
assert_eq!(execs.first_match("cu"), Some("curl"));
assert!(execs.matching("z").is_empty());
}
#[test]
fn falls_back_to_substring_when_no_prefix_matches() {
let fx = Fixture::new("substring");
let bin = fx.dir("bin");
fx.executable(&bin, "com.valvesoftware.Steam");
fx.executable(&bin, "gnome-software");
let execs = Executables::from_dirs([&bin]);
// Nothing begins with "soft", but both names contain it; from the same
// directory, so the alphabetical tie-break orders them.
assert_eq!(
execs.matching("soft"),
vec!["com.valvesoftware.Steam", "gnome-software"]
);
}
#[test]
fn prefix_matches_win_over_substring_matches() {
let fx = Fixture::new("prefix-wins");
let bin = fx.dir("bin");
fx.executable(&bin, "steamcmd"); // prefix match for "steam"
fx.executable(&bin, "com.valvesoftware.Steam"); // only a substring match
let execs = Executables::from_dirs([&bin]);
// A prefix hit exists, so the substring-only candidate is not diluted in.
assert_eq!(execs.matching("steam"), vec!["steamcmd"]);
}
#[test]
fn falls_back_to_case_insensitive_substring_last() {
let fx = Fixture::new("case-insensitive");
let bin = fx.dir("bin");
fx.executable(&bin, "com.valvesoftware.Steam");
let execs = Executables::from_dirs([&bin]);
// Sanity: the correctly-cased "Steam" is found by the case-sensitive tier.
assert_eq!(execs.matching("Steam"), vec!["com.valvesoftware.Steam"]);
// "steam" is neither a prefix nor a case-sensitive substring (the S is
// capitalized), so only the case-insensitive tier finds it.
assert_eq!(execs.matching("steam"), vec!["com.valvesoftware.Steam"]);
assert_eq!(execs.first_match("steam"), Some("com.valvesoftware.Steam"));
}
/// In the case-insensitive tier, exactness folds case too: typing the whole
/// name in the wrong case still promotes it over a mere substring hit from
/// an earlier directory.
#[test]
fn a_case_insensitive_exact_name_is_promoted() {
let fx = Fixture::new("exact-ignoring-case");
let first = fx.dir("first");
let second = fx.dir("second");
fx.executable(&first, "com.valvesoftware.Steam"); // substring hit only
fx.executable(&second, "Steam"); // the whole name, wrongly cased
let execs = Executables::from_dirs([&first, &second]);
// Neither name begins with "steam", and neither contains it with that
// casing, so only the case-insensitive tier answers.
assert_eq!(
execs.matching("steam"),
vec!["Steam", "com.valvesoftware.Steam"]
);
assert_eq!(execs.first_match("steam"), Some("Steam"));
}
/// Several names can be exact once case is folded away. They lead together,
/// ordered among themselves by the usual `$PATH` rule.
#[test]
fn case_insensitive_exact_matches_tie_break_by_path_order() {
let fx = Fixture::new("exact-ignoring-case-tie");
let first = fx.dir("first");
let second = fx.dir("second");
fx.executable(&first, "STEAM");
fx.executable(&second, "Steam");
// Matches once case is folded, but is not the whole name.
fx.executable(&second, "run-Steam");
let execs = Executables::from_dirs([&first, &second]);
assert_eq!(execs.matching("steam"), vec!["STEAM", "Steam", "run-Steam"]);
}
#[test]
fn case_sensitive_substring_is_preferred_over_case_insensitive() {
let fx = Fixture::new("case-precedence");
let bin = fx.dir("bin");
fx.executable(&bin, "myTOOL"); // contains "TOOL" exactly
fx.executable(&bin, "othertool"); // contains "tool" only when lowercased
let execs = Executables::from_dirs([&bin]);
// "TOOL" matches case-sensitively, so the case-insensitive tier (which
// would also pull in "othertool") is never reached.
assert_eq!(execs.matching("TOOL"), vec!["myTOOL"]);
}
}