//! 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"]);
    }
}