bmrk 0.4.0

//! Background-built, persisted index of directory paths, consulted by both quick jump (`Tab`)
//! and search (`/`) as a fast synchronous lookup ("Phase 1.5") between their existing in-memory
//! scan (Phase 1) and their existing live disk scan (Phase 2). See `.debug/BDP.md` Part 3 for
//! the full design rationale.

use crate::search::SearchResult;
use crossbeam_channel::{unbounded, Receiver, Sender};
use fuzzy_matcher::skim::SkimMatcherV2;
use fuzzy_matcher::FuzzyMatcher;
use std::collections::{HashSet, VecDeque};
use std::fs;
use std::io::{BufRead, BufReader, Write};
use std::path::{Path, PathBuf};
use std::thread::{self, JoinHandle};
use std::time::Duration;

/// One indexed directory: absolute path plus data cheap to recompute but wasteful to redo on
/// every query.
struct IndexEntry {
    /// Lowercased basename, used for both prefix and substring/fuzzy matching.
    name_lower: String,
    /// Full absolute path.
    path: PathBuf,
    /// Component count of `path` — a stand-in for tree depth, used only to rank matches
    /// shallowest-first within a single lookup's (small) result set.
    depth: u32,
}

/// A background-built, persisted index of directory paths, rooted at `index.roots` (the user's
/// home directory by default). Both `Tab` (quick jump) and `/` (search) consult it as a
/// synchronous in-memory lookup before falling back to their existing live disk scan; the index
/// can only ever make a lookup faster or more complete, never regress a case that worked before
/// this feature existed.
pub struct DirIndex {
    /// Sorted by `name_lower` ascending — enables `partition_point` binary search for prefix
    /// lookups. Substring/fuzzy lookups do a full linear scan instead.
    entries: Vec<IndexEntry>,
}

impl Default for DirIndex {
    fn default() -> Self {
        Self::empty()
    }
}

impl DirIndex {
    /// An empty index — the safe default before the first build completes, or when disabled.
    pub fn empty() -> Self {
        Self {
            entries: Vec::new(),
        }
    }

    /// Build a sorted `DirIndex` from a flat list of paths, recomputing `name_lower`/`depth` for
    /// each. The single constructor both `load_from_disk` and the builder's result funnel
    /// through, so the two never risk producing differently-sorted data (`prefix_matches`'s
    /// binary search silently returns garbage on an unsorted `entries`).
    pub(crate) fn from_paths(paths: Vec<PathBuf>) -> Self {
        let mut entries: Vec<IndexEntry> = paths
            .into_iter()
            .map(|path| {
                let name_lower = path
                    .file_name()
                    .and_then(|n| n.to_str())
                    .unwrap_or_default()
                    .to_lowercase();
                let depth = path.components().count() as u32;
                IndexEntry {
                    name_lower,
                    path,
                    depth,
                }
            })
            .collect();
        entries.sort_by(|a, b| a.name_lower.cmp(&b.name_lower));
        Self { entries }
    }

    /// Load the persisted index from disk. **Infallible**: any I/O or parse problem (missing
    /// file, permission denied, invalid UTF-8 line) is treated identically to "no index yet" and
    /// yields an empty index rather than a propagated error — the app must never fail to start
    /// because this optional performance cache is missing or damaged.
    pub fn load_from_disk(path: &Path) -> Self {
        let file = match fs::File::open(path) {
            Ok(f) => f,
            Err(_) => return Self::empty(),
        };
        let paths: Vec<PathBuf> = BufReader::new(file)
            .lines()
            .map_while(Result::ok)
            .filter(|line| !line.is_empty())
            .map(PathBuf::from)
            .collect();
        Self::from_paths(paths)
    }

    /// Write `paths` to `path`, one absolute path per line, creating the parent directory if
    /// needed. Called from the background builder thread, never the main thread.
    fn save_to_disk(paths: &[PathBuf], path: &Path) -> std::io::Result<()> {
        if let Some(parent) = path.parent() {
            fs::create_dir_all(parent)?;
        }
        let mut file = fs::File::create(path)?;
        for p in paths {
            writeln!(file, "{}", p.display())?;
        }
        Ok(())
    }

    /// Whether the index file is missing, unreadable, or older than `refresh_hours`. Any
    /// `metadata`/`modified` error is treated as "stale" — a safe default that triggers a
    /// rebuild rather than silently never refreshing.
    pub fn is_stale(path: &Path, refresh_hours: u64) -> bool {
        let metadata = match fs::metadata(path) {
            Ok(m) => m,
            Err(_) => return true,
        };
        let modified = match metadata.modified() {
            Ok(m) => m,
            Err(_) => return true,
        };
        match modified.elapsed() {
            Ok(elapsed) => elapsed > Duration::from_secs(refresh_hours.saturating_mul(3600)),
            Err(_) => true,
        }
    }

    /// Default on-disk location: `dirs::config_dir()/bmrk/dir_index.txt` — same directory
    /// family as `config.toml`/`bookmarks.json`.
    pub fn dir_index_path() -> Option<PathBuf> {
        dirs::config_dir().map(|p| p.join("bmrk").join("dir_index.txt"))
    }

    /// True if every path component of `path` below `root` is visible under `show_hidden` (i.e.
    /// no component starts with `.`, unless `show_hidden` is true). Mirrors how the live scans
    /// (`quick_jump::find_in_loaded_nodes`, `deep_scan_bfs`, `search_loaded_nodes`,
    /// `deep_search_recursive`) only ever skip *descendants* of the scan root, never the root
    /// itself — computing hidden-ness relative to the query's own root (not the index's root)
    /// keeps this correct even when `nav.root` sits below a hidden directory.
    fn visible_under(path: &Path, root: &Path, show_hidden: bool) -> bool {
        if show_hidden {
            return true;
        }
        match path.strip_prefix(root) {
            Ok(rel) => !rel
                .components()
                .any(|c| c.as_os_str().to_str().is_some_and(|s| s.starts_with('.'))),
            Err(_) => true,
        }
    }

    /// Case-insensitive **prefix** match, scoped to `root`'s subtree, shallowest match first —
    /// the same contract `quick_jump::find_in_loaded_nodes` already provides. Binary-searches
    /// into the name-sorted `entries` to find the start of the matching range, then linearly
    /// scans forward while the name still starts with `prefix_lower` (this range is normally
    /// tiny), filtering by scope (`root`) and `show_hidden`, then stable-sorts the small result
    /// set by depth ascending before capping at `limit`.
    pub fn prefix_matches(
        &self,
        root: &Path,
        prefix_lower: &str,
        show_hidden: bool,
        limit: usize,
    ) -> Vec<PathBuf> {
        if prefix_lower.is_empty() {
            return Vec::new();
        }

        let start = self
            .entries
            .partition_point(|e| e.name_lower.as_str() < prefix_lower);

        let mut matches: Vec<&IndexEntry> = Vec::new();
        for entry in &self.entries[start..] {
            if !entry.name_lower.starts_with(prefix_lower) {
                break;
            }
            if !entry.path.starts_with(root) {
                continue;
            }
            if !Self::visible_under(&entry.path, root, show_hidden) {
                continue;
            }
            matches.push(entry);
        }

        matches.sort_by_key(|e| e.depth);
        matches
            .into_iter()
            .take(limit)
            .map(|e| e.path.clone())
            .collect()
    }

    /// Case-insensitive **substring** (or fuzzy, when `fuzzy` is true) match, scoped to `root`'s
    /// subtree. A full linear scan over `entries` (no binary search possible for
    /// substring/fuzzy) — on the order of milliseconds even for a few hundred thousand short
    /// strings, entirely in memory. Stops once `cap` results are collected.
    pub fn substring_or_fuzzy_matches(
        &self,
        root: &Path,
        query_lower: &str,
        fuzzy: bool,
        matcher: Option<&SkimMatcherV2>,
        show_hidden: bool,
        cap: usize,
    ) -> Vec<SearchResult> {
        if cap == 0 || query_lower.is_empty() {
            return Vec::new();
        }

        let mut results = Vec::new();
        for entry in &self.entries {
            if results.len() >= cap {
                break;
            }
            if !entry.path.starts_with(root) {
                continue;
            }
            if !Self::visible_under(&entry.path, root, show_hidden) {
                continue;
            }

            if fuzzy {
                if let Some(m) = matcher {
                    if let Some((score, indices)) = m.fuzzy_indices(&entry.name_lower, query_lower)
                    {
                        results.push(SearchResult {
                            path: entry.path.clone(),
                            is_dir: true,
                            score: Some(score),
                            match_indices: Some(indices),
                        });
                    }
                }
            } else if entry.name_lower.contains(query_lower) {
                results.push(SearchResult {
                    path: entry.path.clone(),
                    is_dir: true,
                    score: None,
                    match_indices: None,
                });
            }
        }

        results
    }

    /// Spawn a background thread that loads the persisted index if it's still fresh, or builds a
    /// new one from `roots` if it's missing/stale — the `is_stale` branch used to run on the main
    /// thread inside `App::new`, blocking startup on the full size of the persisted file even
    /// when nothing needed the index until the first `Tab`/`/` (`.debug/BDP.md` Part 5, Finding
    /// #7). Folding both branches into one spawn means there's a single code path (and a single
    /// channel item type, `DirIndex`) regardless of which branch fires, instead of `App` needing
    /// to know the difference. Not cancellable either way — this is a fire-and-forget background
    /// job with no UI attached to cancel it from; see `.debug/BDP.md` Part 3.
    pub fn spawn_load_or_build(
        index_path: PathBuf,
        refresh_hours: u64,
        roots: Vec<PathBuf>,
        ignore_dirs: HashSet<String>,
    ) -> (JoinHandle<()>, Receiver<DirIndex>) {
        let (tx, rx): (Sender<DirIndex>, Receiver<DirIndex>) = unbounded();

        let handle = thread::spawn(move || {
            if !Self::is_stale(&index_path, refresh_hours) {
                let _ = tx.send(Self::load_from_disk(&index_path));
                return;
            }
            let paths = build_index(&roots, &ignore_dirs);
            let _ = Self::save_to_disk(&paths, &index_path);
            let _ = tx.send(Self::from_paths(paths));
        });

        (handle, rx)
    }
}

/// Iteratively walks `roots` (an explicit worklist, not recursion — avoids stack depth concerns
/// on pathologically deep trees), collecting every directory found. Skips a directory's
/// contents entirely when its basename is in `ignore_dirs`, and never follows symlinks
/// (hardcoded, not tied to `config.behavior.follow_symlinks` — see `.debug/BDP.md` Part 3). The
/// roots themselves are never pushed into the result, only their descendants — matching the
/// convention already used by `quick_jump::find_in_loaded_nodes`/`deep_scan_bfs` of never
/// matching the scan root itself.
fn build_index(roots: &[PathBuf], ignore_dirs: &HashSet<String>) -> Vec<PathBuf> {
    let mut result = Vec::new();
    let mut queue: VecDeque<PathBuf> = roots.iter().cloned().collect();

    while let Some(dir) = queue.pop_front() {
        let entries = match fs::read_dir(&dir) {
            Ok(e) => e,
            Err(_) => continue,
        };

        for entry in entries.flatten() {
            let path = entry.path();

            if let Ok(metadata) = fs::symlink_metadata(&path) {
                if metadata.is_symlink() {
                    continue;
                }
            }

            if !path.is_dir() {
                continue;
            }

            // Invalid UTF-8 in the path would come back lossy (replacement characters) after a
            // `save_to_disk`/`load_from_disk` round trip (`save_to_disk` writes via
            // `Path::display()`), silently corrupting the entry into a dead jump target on the
            // next launch. Skip indexing (and descending into) it entirely rather than risk that
            // asymmetry between the fresh in-memory index and the reloaded one.
            if path.to_str().is_none() {
                continue;
            }

            if let Some(name) = path.file_name().and_then(|n| n.to_str()) {
                if ignore_dirs.contains(name) {
                    continue;
                }
            }

            result.push(path.clone());
            queue.push_back(path);
        }
    }

    result
}

#[cfg(test)]
mod tests {
    use super::*;
    use tempfile::TempDir;

    fn paths_set(paths: &[PathBuf]) -> HashSet<PathBuf> {
        paths.iter().cloned().collect()
    }

    // --- build_index ---

    #[test]
    fn build_index_skips_ignored_dir_and_its_contents_but_not_siblings() {
        let tmp = TempDir::new().unwrap();
        let ignored = tmp.path().join("node_modules");
        std::fs::create_dir(&ignored).unwrap();
        std::fs::create_dir(ignored.join("some_pkg")).unwrap();
        let sibling = tmp.path().join("src");
        std::fs::create_dir(&sibling).unwrap();

        let mut ignore_dirs = HashSet::new();
        ignore_dirs.insert("node_modules".to_string());

        let found = build_index(&[tmp.path().to_path_buf()], &ignore_dirs);

        assert!(!found.contains(&ignored), "ignored dir must not be indexed");
        assert!(
            !found.contains(&ignored.join("some_pkg")),
            "contents of an ignored dir must not be indexed either"
        );
        assert!(
            found.contains(&sibling),
            "non-ignored sibling must still be indexed"
        );
    }

    #[test]
    fn build_index_skips_symlinked_directories_entirely() {
        let tmp = TempDir::new().unwrap();
        let real_target = tmp.path().join("real_target");
        std::fs::create_dir(&real_target).unwrap();
        std::fs::create_dir(real_target.join("inner")).unwrap();

        let link = tmp.path().join("link_to_target");
        #[cfg(unix)]
        let made_link = std::os::unix::fs::symlink(&real_target, &link).is_ok();
        #[cfg(windows)]
        let made_link = std::os::windows::fs::symlink_dir(&real_target, &link).is_ok();
        #[cfg(not(any(unix, windows)))]
        let made_link = false;

        if !made_link {
            eprintln!(
                "build_index_skips_symlinked_directories_entirely: SKIPPED (no symlink support)"
            );
            return;
        }

        let found = build_index(&[tmp.path().to_path_buf()], &HashSet::new());

        assert!(
            found.contains(&real_target.join("inner")),
            "the real target's contents must still be indexed"
        );
        assert!(
            !found.contains(&link),
            "the symlink path itself must not be indexed"
        );
    }

    // --- prefix_matches ---

    #[test]
    fn prefix_matches_returns_shallowest_first_and_respects_show_hidden() {
        // The motivating case from the Goal section of `.debug/BDP.md` Part 3: a shallow hidden
        // match (~/.config/bmrk) and a deep non-hidden match (~/github.com/holgertkey/bmrk).
        let tmp = TempDir::new().unwrap();
        let root = tmp.path().to_path_buf();
        let hidden_match = root.join(".config").join("bmrk");
        let deep_match = root.join("github.com").join("holgertkey").join("bmrk");

        let index = DirIndex::from_paths(vec![hidden_match.clone(), deep_match.clone()]);

        let visible_only = index.prefix_matches(&root, "bmrk", false, 20);
        assert_eq!(
            visible_only,
            vec![deep_match.clone()],
            "with show_hidden=false, the entry under a hidden component must be dropped"
        );

        let with_hidden = index.prefix_matches(&root, "bmrk", true, 20);
        assert_eq!(
            with_hidden,
            vec![hidden_match, deep_match],
            "with show_hidden=true, the shallower (hidden) match must be returned first"
        );
    }

    #[test]
    fn prefix_matches_is_scoped_to_root() {
        let tmp = TempDir::new().unwrap();
        let in_scope_root = tmp.path().join("scope_a");
        let out_of_scope = tmp.path().join("scope_b").join("docs");
        let in_scope = in_scope_root.join("docs");

        let index = DirIndex::from_paths(vec![out_of_scope, in_scope.clone()]);

        let matches = index.prefix_matches(&in_scope_root, "doc", false, 20);
        assert_eq!(matches, vec![in_scope]);
    }

    #[test]
    fn prefix_matches_is_prefix_not_substring() {
        let tmp = TempDir::new().unwrap();
        let root = tmp.path().to_path_buf();
        let xdocs = root.join("xdocs");

        let index = DirIndex::from_paths(vec![xdocs]);
        assert!(index.prefix_matches(&root, "docs", false, 20).is_empty());
    }

    #[test]
    fn prefix_matches_respects_limit() {
        let tmp = TempDir::new().unwrap();
        let root = tmp.path().to_path_buf();
        let paths: Vec<PathBuf> = (0..10).map(|i| root.join(format!("doc{i}"))).collect();
        let index = DirIndex::from_paths(paths);

        let matches = index.prefix_matches(&root, "doc", false, 3);
        assert_eq!(matches.len(), 3);
    }

    // --- substring_or_fuzzy_matches ---

    #[test]
    fn substring_matches_finds_non_fuzzy_substring() {
        let tmp = TempDir::new().unwrap();
        let root = tmp.path().to_path_buf();
        let target = root.join("my_documents");
        let index = DirIndex::from_paths(vec![target.clone()]);

        let results = index.substring_or_fuzzy_matches(&root, "docu", false, None, false, 10);
        assert_eq!(results.len(), 1);
        assert_eq!(results[0].path, target);
        assert!(results[0].is_dir);
    }

    #[test]
    fn substring_matches_respects_cap() {
        let tmp = TempDir::new().unwrap();
        let root = tmp.path().to_path_buf();
        let paths: Vec<PathBuf> = (0..10).map(|i| root.join(format!("doc{i}"))).collect();
        let index = DirIndex::from_paths(paths);

        let results = index.substring_or_fuzzy_matches(&root, "doc", false, None, false, 4);
        assert_eq!(results.len(), 4);
    }

    // --- persistence ---

    #[test]
    fn save_and_load_round_trip_preserves_path_set() {
        let tmp = TempDir::new().unwrap();
        let index_path = tmp.path().join("dir_index.txt");
        let paths = vec![
            tmp.path().join("a"),
            tmp.path().join("b").join("c"),
            tmp.path().join("d"),
        ];

        DirIndex::save_to_disk(&paths, &index_path).unwrap();
        let loaded = DirIndex::load_from_disk(&index_path);
        let loaded_paths: Vec<PathBuf> = loaded.entries.iter().map(|e| e.path.clone()).collect();

        assert_eq!(paths_set(&loaded_paths), paths_set(&paths));
    }

    #[test]
    fn load_from_disk_missing_file_returns_empty() {
        let tmp = TempDir::new().unwrap();
        let missing = tmp.path().join("does_not_exist.txt");
        let index = DirIndex::load_from_disk(&missing);
        assert!(index.entries.is_empty());
    }

    // --- staleness ---

    #[test]
    fn is_stale_true_for_missing_file() {
        let tmp = TempDir::new().unwrap();
        let missing = tmp.path().join("does_not_exist.txt");
        assert!(DirIndex::is_stale(&missing, 24));
    }

    #[test]
    fn is_stale_true_for_old_mtime() {
        let tmp = TempDir::new().unwrap();
        let path = tmp.path().join("dir_index.txt");
        std::fs::write(&path, "x").unwrap();

        let old_time = std::time::SystemTime::now() - Duration::from_secs(48 * 3600);
        // Windows `SetFileTime` needs a write-capable handle; `File::open` is read-only and
        // fails with "Access is denied". Open for write so `set_modified` works cross-platform.
        let file = std::fs::OpenOptions::new().write(true).open(&path).unwrap();
        file.set_modified(old_time).unwrap();

        assert!(DirIndex::is_stale(&path, 24));
    }

    #[test]
    fn is_stale_false_for_fresh_file() {
        let tmp = TempDir::new().unwrap();
        let path = tmp.path().join("dir_index.txt");
        std::fs::write(&path, "x").unwrap();

        assert!(!DirIndex::is_stale(&path, 24));
    }

    // --- spawn_load_or_build (.debug/BDP.md Part 5, Finding #7) ---
    //
    // These test `spawn_load_or_build` directly with a temp `index_path`, deliberately not
    // through `App::start_background_index` — that resolves its path via the real
    // `DirIndex::dir_index_path()` (the user's actual `~/.config/bmrk/dir_index.txt`), so a test
    // going through it would either read or, on the stale branch, silently overwrite the user's
    // real cache. `spawn_load_or_build` takes the path as a parameter specifically so it can be
    // tested in isolation from that.

    fn recv_with_timeout(rx: &Receiver<DirIndex>) -> DirIndex {
        rx.recv_timeout(Duration::from_secs(5))
            .expect("spawn_load_or_build did not report back in time")
    }

    #[test]
    fn spawn_load_or_build_loads_fresh_cache_without_rebuilding() {
        let tmp = TempDir::new().unwrap();
        let index_path = tmp.path().join("dir_index.txt");
        // The cached paths deliberately do NOT exist under `roots` on disk — if the stale branch
        // fired instead of the load branch, the rebuild would find none of these, proving which
        // branch actually ran.
        let cached_paths = vec![
            PathBuf::from("/cached/from/disk/one"),
            PathBuf::from("/cached/from/disk/two"),
        ];
        DirIndex::save_to_disk(&cached_paths, &index_path).unwrap();

        let scan_root = TempDir::new().unwrap();
        std::fs::create_dir(scan_root.path().join("on_disk_only")).unwrap();

        let (_handle, rx) = DirIndex::spawn_load_or_build(
            index_path,
            24, // refresh_hours: the file was just written, so it's fresh
            vec![scan_root.path().to_path_buf()],
            HashSet::new(),
        );
        let index = recv_with_timeout(&rx);

        let loaded_paths: Vec<PathBuf> = index.entries.iter().map(|e| e.path.clone()).collect();
        assert_eq!(
            paths_set(&loaded_paths),
            paths_set(&cached_paths),
            "a fresh cache must be loaded as-is, not rebuilt from roots"
        );
    }

    #[test]
    fn spawn_load_or_build_rebuilds_when_stale() {
        let tmp = TempDir::new().unwrap();
        let index_path = tmp.path().join("dir_index.txt");
        // A stale (old-mtime) cache with paths that must NOT survive into the result.
        let stale_paths = vec![PathBuf::from("/stale/entry")];
        DirIndex::save_to_disk(&stale_paths, &index_path).unwrap();
        let old_time = std::time::SystemTime::now() - Duration::from_secs(48 * 3600);
        // Write-capable handle: Windows `set_modified` rejects a read-only `File::open` handle.
        std::fs::OpenOptions::new()
            .write(true)
            .open(&index_path)
            .unwrap()
            .set_modified(old_time)
            .unwrap();

        let scan_root = TempDir::new().unwrap();
        let fresh_dir = scan_root.path().join("built_fresh");
        std::fs::create_dir(&fresh_dir).unwrap();

        let (_handle, rx) = DirIndex::spawn_load_or_build(
            index_path.clone(),
            24, // refresh_hours: 48h-old file exceeds this, so it's stale
            vec![scan_root.path().to_path_buf()],
            HashSet::new(),
        );
        let index = recv_with_timeout(&rx);

        let result_paths: Vec<PathBuf> = index.entries.iter().map(|e| e.path.clone()).collect();
        assert!(
            result_paths.contains(&fresh_dir),
            "a stale cache must be rebuilt from roots, not loaded as-is"
        );
        assert!(
            !result_paths
                .iter()
                .any(|p| p == &PathBuf::from("/stale/entry")),
            "the stale cache's own entries must not leak into the rebuilt result"
        );

        // The rebuild must also have persisted the fresh result back to disk (same as the old
        // `spawn_build` always did), so the next run's load branch has something current to use.
        let reloaded = DirIndex::load_from_disk(&index_path);
        let reloaded_paths: Vec<PathBuf> =
            reloaded.entries.iter().map(|e| e.path.clone()).collect();
        assert!(reloaded_paths.contains(&fresh_dir));
    }
}