oo_ide/

file_index.rs

//! Background file indexer and fuzzy search engine for the file selector.
//!
//! Key design points:
//!
//! * [`FileIndex`] is built once at startup by [`spawn_indexer`] in a
//!   `tokio::task::spawn_blocking` thread.
//! * The result is stored in a [`SharedFileIndex`] which is an
//!   `Arc<ArcSwap<Option<FileIndex>>>`.  Reads are **lock-free** (`ArcSwap::load`);
//!   writes are atomic pointer swaps.
//! * [`spawn_watcher`] keeps the index live: it watches the project root with
//!   `notify-debouncer-mini`, and rebuilds the full index (in a background
//!   blocking task) whenever files change.  A 200 ms burst-coalescing sleep
//!   prevents rebuild storms during e.g. `git checkout`.
//! * [`NucleoSearch`] wraps `nucleo_matcher` for fast fuzzy matching.
//!   [`NucleoSearch::search_top`] uses a bounded min-heap (size = `max`) so
//!   only the top-K entries are ever kept in memory, avoiding a full sort of
//!   potentially millions of candidates.
//! * [`FileIndex`] carries a **trigram prefilter**: for queries of ≥ 3 bytes,
//!   only files whose path contains the first trigram of the (lowercased) query
//!   are passed to the matcher, reducing matcher calls by 10–50×.

use std::cmp::Reverse;
use std::collections::BinaryHeap;
use std::collections::HashMap;
use std::collections::HashSet;
use std::path::{Path, PathBuf};
use std::sync::Arc;

use arc_swap::ArcSwap;
use ignore::WalkBuilder;
use ignore::gitignore::GitignoreBuilder;

use nucleo_matcher::pattern::{CaseMatching, Normalization, Pattern};
use nucleo_matcher::{Config, Matcher, Utf32String};
use notify::Watcher;


// ── Data structures ───────────────────────────────────────────────────────────

pub struct FileEntry {
    /// Relative path from the project root.
    pub path: PathBuf,
    /// Pre-computed UTF-32 representation for nucleo — avoids per-query allocs.
    utf32: Utf32String,
}

/// A single entry in a directory listing produced by [`ProjectFileRegistry`].
#[derive(Debug, Clone)]
pub struct DirEntry {
    /// Relative path from the project root.
    pub path: PathBuf,
    pub is_dir: bool,
}

pub struct FileIndex {
    files: Vec<FileEntry>,
    /// Maps each 3-byte lowercase trigram to the indices of files whose
    /// lowercased path contains that trigram.  Used as a fast prefilter.
    trigrams: HashMap<[u8; 3], Vec<usize>>,
}

impl std::fmt::Debug for FileIndex {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "FileIndex({} files)", self.files.len())
    }
}

impl FileIndex {
    /// Walk `root` using `ignore` (respects `.gitignore`) and build the index.
    ///
    /// `max_depth` can be provided for shallow indexing (None = full).
    pub fn build_with_max_depth(root: &Path, max_depth: Option<usize>) -> Self {
        let mut files = Vec::with_capacity(4096);
        let mut trigrams: HashMap<[u8; 3], Vec<usize>> = HashMap::new();

        let mut builder = WalkBuilder::new(root);
        builder
            .hidden(false) // show dotfiles (.gitignore, .env, …)
            .git_ignore(true) // respect .gitignore — handles target/, node_modules/, …
            .git_exclude(true)
            .parents(true);

        if let Some(d) = max_depth {
            builder.max_depth(Some(d));
        }

        for result in builder.build() {
            let Ok(entry) = result else { continue };
            let Some(ft) = entry.file_type() else {
                continue;
            };
            if !ft.is_file() {
                continue;
            }

            let path = entry.path();
            let rel = path.strip_prefix(root).unwrap_or(path);

            // Belt-and-suspenders: skip common build dirs even when they're not
            // in .gitignore (e.g. freshly-cloned repos without Cargo.lock).
            if rel.components().any(|c| {
                c.as_os_str()
                    .to_str()
                    .map(|s| matches!(s, "target" | "node_modules" | "__pycache__"))
                    .unwrap_or(false)
            }) {
                continue;
            }

            let s = rel.to_string_lossy().replace('\\', "/");
            let idx = files.len();
            index_trigrams(s.as_bytes(), idx, &mut trigrams);
            files.push(FileEntry {
                path: rel.to_path_buf(),
                utf32: Utf32String::from(s.as_str()),
            });
        }

        FileIndex { files, trigrams }
    }

    /// Convenience wrapper for the former behaviour: full walk (no depth limit).
    pub fn build(root: &Path) -> Self {
        Self::build_with_max_depth(root, None)
    }

    /// Build from an already-known list of relative paths — used in tests and
    /// benchmarks where no real filesystem walk is needed.
    #[allow(dead_code)]
    pub fn from_paths(paths: Vec<PathBuf>) -> Self {
        let mut files = Vec::with_capacity(paths.len());
        let mut trigrams: HashMap<[u8; 3], Vec<usize>> = HashMap::new();

        for path in paths {
            let s = path.to_string_lossy().replace('\\', "/");
            let idx = files.len();
            index_trigrams(s.as_bytes(), idx, &mut trigrams);
            files.push(FileEntry {
                utf32: Utf32String::from(s.as_str()),
                path,
            });
        }

        FileIndex { files, trigrams }
    }

    #[allow(dead_code)]
    pub fn files(&self) -> &[FileEntry] {
        &self.files
    }

    /// Return the indices (into `self.files`) of files whose lowercased path
    /// contains the first trigram (first 3 ASCII bytes, lowercased) of `query`.
    ///
    /// Returns `None` when the query is shorter than 3 bytes — callers should
    /// fall back to scanning all files in that case.
    fn trigram_candidate_indices(&self, query: &str) -> Option<Vec<usize>> {
        // Strip spaces before computing trigrams: spaces can't appear in
        // indexed paths, so a trigram like ['i', ' ', 'v'] (from "multi v")
        // would never match anything and incorrectly empty the candidate set.
        let q: Vec<u8> = query.bytes().filter(|&b| b != b' ').collect();
        if q.len() < 3 {
            return None;
        }

        let first = [
            q[0].to_ascii_lowercase(),
            q[1].to_ascii_lowercase(),
            q[2].to_ascii_lowercase(),
        ];

        let a = self.trigrams.get(&first)?;

        // If query is short we just use the first trigram.
        if q.len() < 6 {
            return Some(a.clone());
        }

        let last = [
            q[q.len() - 3].to_ascii_lowercase(),
            q[q.len() - 2].to_ascii_lowercase(),
            q[q.len() - 1].to_ascii_lowercase(),
        ];

        let b = match self.trigrams.get(&last) {
            Some(v) => v,
            None => return Some(vec![]),
        };

        // Intersect the two candidate lists
        let mut out = Vec::with_capacity(a.len().min(b.len()));
        let set: std::collections::HashSet<_> = b.iter().copied().collect();

        for &idx in a {
            if set.contains(&idx) {
                out.push(idx);
            }
        }

        Some(out)
    }
}

/// Insert all trigrams from `bytes` (lowercased) into `map`, pointing to `idx`.
fn index_trigrams(bytes: &[u8], idx: usize, map: &mut HashMap<[u8; 3], Vec<usize>>) {
    use std::collections::HashSet;
    let mut seen = HashSet::new();
    for tri in bytes.windows(3) {
        let key = [
            tri[0].to_ascii_lowercase(),
            tri[1].to_ascii_lowercase(),
            tri[2].to_ascii_lowercase(),
        ];
        if seen.insert(key) {
            map.entry(key).or_default().push(idx);
        }
    }
}

// ── Shared index type ─────────────────────────────────────────────────────────

/// Lock-free shared index.  `None` while the initial walk is still in progress.
///
/// Use `index.load()` for reads (returns a `Guard` — no lock taken).
/// Use `index.store(Arc::new(Some(new_idx)))` for writes (atomic swap).
pub type SharedFileIndex = Arc<ArcSwap<Option<FileIndex>>>;

// ── ProjectFileRegistry ───────────────────────────────────────────────────────

/// Unified project index built in a single filesystem walk.
///
/// Holds everything callers need:
/// - `files` / trigrams for fuzzy search (same as [`FileIndex`])
/// - `dir_children` for O(1) file-tree expansion
/// - `file_set` for O(1) existence checks
pub struct ProjectFileRegistry {
    inner: FileIndex,
    /// Maps each relative directory path → its immediate children, pre-sorted
    /// (dirs first, then alphabetically).
    dir_children: HashMap<PathBuf, Vec<DirEntry>>,
    /// Set of all relative file paths for O(1) existence checks.
    file_set: HashSet<PathBuf>,
}

impl std::fmt::Debug for ProjectFileRegistry {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "ProjectFileRegistry({} files)", self.inner.files.len())
    }
}

impl Default for ProjectFileRegistry {
    fn default() -> Self {
        ProjectFileRegistry {
            inner: FileIndex { files: vec![], trigrams: HashMap::new() },
            dir_children: HashMap::new(),
            file_set: HashSet::new(),
        }
    }
}

impl ProjectFileRegistry {
    /// Walk `root` and build the full registry in a single pass.
    pub fn build(root: &Path) -> Self {
        let mut files = Vec::with_capacity(4096);
        let mut trigrams: HashMap<[u8; 3], Vec<usize>> = HashMap::new();
        let mut dir_map: HashMap<PathBuf, Vec<DirEntry>> = HashMap::new();
        let mut file_set: HashSet<PathBuf> = HashSet::new();

        for result in WalkBuilder::new(root)
            .hidden(false)
            .git_ignore(true)
            .git_exclude(true)
            .parents(true)
            .build()
        {
            let Ok(entry) = result else { continue };
            let Some(ft) = entry.file_type() else { continue };

            let path = entry.path();
            let rel = path.strip_prefix(root).unwrap_or(path);

            // Skip the root directory entry itself — we don't want an empty
            // relative path stored as a child of the project root.
            if rel.as_os_str().is_empty() {
                continue;
            }

            // Belt-and-suspenders: skip build dirs even when not in .gitignore.
            if rel.components().any(|c| {
                c.as_os_str()
                    .to_str()
                    .map(|s| matches!(s, "target" | "node_modules" | "__pycache__"))
                    .unwrap_or(false)
            }) {
                continue;
            }

            let is_dir = ft.is_dir();

            // Populate dir_children for this entry's parent. Use an empty
            // relative path for project-root children so root_children() works
            // reliably regardless of Path::parent() semantics.
            let parent = rel.parent().unwrap_or(Path::new(""));
            dir_map.entry(parent.to_path_buf()).or_default().push(DirEntry { path: rel.to_path_buf(), is_dir });

            if !is_dir {
                let s = rel.to_string_lossy().replace('\\', "/");
                let idx = files.len();
                index_trigrams(s.as_bytes(), idx, &mut trigrams);
                file_set.insert(rel.to_path_buf());
                files.push(FileEntry {
                    path: rel.to_path_buf(),
                    utf32: Utf32String::from(s.as_str()),
                });
            }
        }

        // Sort each dir's children: dirs first, then alphabetically.
        for children in dir_map.values_mut() {
            children.sort_unstable_by(|a, b| {
                b.is_dir.cmp(&a.is_dir).then_with(|| a.path.cmp(&b.path))
            });
        }

        let file_count = files.len();
        let reg = ProjectFileRegistry {
            inner: FileIndex { files, trigrams },
            dir_children: dir_map,
            file_set,
        };
        log::info!("project registry built ({file_count} files)");
        reg
    }

    /// All indexed files (for fuzzy search).
    pub fn files(&self) -> &[FileEntry] {
        &self.inner.files
    }

    /// Access the inner [`FileIndex`] for use with [`NucleoSearch`].
    pub fn file_index(&self) -> &FileIndex {
        &self.inner
    }

    /// Immediate children of `rel_dir` (relative path), pre-sorted
    /// (dirs first, then alphabetically).
    ///
    /// Returns an empty slice when the directory is empty or not indexed.
    pub fn children_of(&self, rel_dir: &Path) -> &[DirEntry] {
        self.dir_children.get(rel_dir).map(|v| v.as_slice()).unwrap_or(&[])
    }

    /// Root-level entries (children of the project root itself).
    pub fn root_children(&self) -> &[DirEntry] {
        self.children_of(Path::new(""))
    }

    /// All relative file paths whose prefix matches `rel_dir`.
    ///
    /// Allocates a `Vec`; intended for batch use (e.g. project-search seed list).
    pub fn files_under(&self, rel_dir: &Path) -> Vec<&Path> {
        self.inner
            .files
            .iter()
            .filter(|e| e.path.starts_with(rel_dir))
            .map(|e| e.path.as_path())
            .collect()
    }

    /// Whether a relative path exists in the index.  O(1).
    pub fn contains(&self, rel: &Path) -> bool {
        self.file_set.contains(rel)
    }
}

/// Lock-free shared registry. Clone freely — it is an `Arc<ArcSwap<…>>`.
///
/// Use `registry.load()` for reads (returns a `Guard` — no lock taken).
/// Use `registry.store(Arc::new(new_reg))` for writes (atomic swap).
pub type SharedRegistry = Arc<ArcSwap<Option<ProjectFileRegistry>>>;

/// Spawn the indexer and watcher for `root`. Returns the shared handle
/// immediately; the registry is populated asynchronously.
pub fn spawn_registry(root: PathBuf) -> SharedRegistry {
    let shared: SharedRegistry = Arc::new(ArcSwap::from_pointee(None));

    // Initial build in a background blocking task.
    {
        let out = shared.clone();
        let r = root.clone();
        tokio::task::spawn_blocking(move || {
            out.store(Arc::new(Some(ProjectFileRegistry::build(&r))));
        });
    }

    // Filesystem watcher — same debounce strategy as spawn_watcher.
    let (trigger_tx, mut trigger_rx) = tokio::sync::mpsc::unbounded_channel::<()>();
    {
        let root_clone = root.clone();
        let trigger_tx_clone = trigger_tx.clone();

        fn build_gitignore_registry(root: &Path) -> ignore::gitignore::Gitignore {
            let mut gbuilder = GitignoreBuilder::new(root);
            let mut walker = WalkBuilder::new(root);
            walker.hidden(false).git_ignore(false).git_exclude(false);
            for entry in walker.build().filter_map(|r| r.ok()) {
                if entry.path().file_name().and_then(|n| n.to_str()) == Some(".gitignore") {
                    let _ = gbuilder.add(entry.path());
                }
            }
            let git_info_exclude = root.join(".git").join("info").join("exclude");
            if git_info_exclude.is_file() {
                let _ = gbuilder.add(git_info_exclude);
            }
            match gbuilder.build() {
                Ok(g) => g,
                Err(_) => ignore::gitignore::Gitignore::empty(),
            }
        }

        let cached_gi = std::sync::Arc::new(std::sync::Mutex::new(
            build_gitignore_registry(&root_clone),
        ));

        std::thread::spawn(move || {
            let watcher_root = root_clone.clone();
            let cached_gi_clone = cached_gi.clone();
            let mut watcher = match notify::RecommendedWatcher::new(
                move |res: Result<notify::Event, notify::Error>| match res {
                    Ok(event) => {
                        let mut rebuild_gi = false;
                        for p in &event.paths {
                            if p.file_name().and_then(|n| n.to_str()) == Some(".gitignore")
                                || p.to_string_lossy().ends_with(".git/info/exclude")
                            {
                                rebuild_gi = true;
                                break;
                            }
                        }
                        if rebuild_gi {
                            let new_gi = build_gitignore_registry(&watcher_root);
                            if let Ok(mut g) = cached_gi_clone.lock() {
                                *g = new_gi;
                            }
                        }
                        let mut any_relevant = false;
                        for p in &event.paths {
                            let is_dir = p.metadata().map(|md| md.is_dir()).unwrap_or(false);
                            let g = cached_gi_clone.lock().unwrap();
                            if !g.matched(p, is_dir).is_ignore() {
                                any_relevant = true;
                                break;
                            }
                        }
                        if any_relevant && should_trigger_notify_event(&event.kind) {
                            let _ = trigger_tx_clone.send(());
                        }
                    }
                    Err(e) => log::warn!("registry watcher error: {e}"),
                },
                notify::Config::default(),
            ) {
                Ok(w) => w,
                Err(e) => {
                    log::warn!("failed to create registry watcher: {e}");
                    return;
                }
            };

            if let Err(e) = watcher.watch(&root_clone, notify::RecursiveMode::Recursive) {
                log::warn!("registry watcher failed to watch {root_clone:?}: {e}");
                return;
            }

            // Keep the thread (and the watcher) alive indefinitely.
            let (_tx, rx) = std::sync::mpsc::channel::<()>();
            let _ = rx.recv();
        });
    }

    let index = shared.clone();
    tokio::spawn(async move {
        let mut rebuild: Option<tokio::task::JoinHandle<()>> = None;
        while trigger_rx.recv().await.is_some() {
            while trigger_rx.try_recv().is_ok() {}
            tokio::time::sleep(std::time::Duration::from_millis(200)).await;
            while trigger_rx.try_recv().is_ok() {}
            if let Some(h) = rebuild.take() {
                h.abort();
            }
            let reg = index.clone();
            let r = root.clone();
            rebuild = Some(tokio::task::spawn_blocking(move || {
                reg.store(Arc::new(Some(ProjectFileRegistry::build(&r))));
            }));
        }
    });

    shared
}

// ── Initial indexer ───────────────────────────────────────────────────────────

/// Spawn a background blocking task that builds the index for `root`, then
/// atomically stores it.  Returns immediately.
pub fn spawn_indexer(root: PathBuf) -> SharedFileIndex {
    let shared: SharedFileIndex = Arc::new(ArcSwap::from_pointee(None));
    let out = shared.clone();
    tokio::task::spawn_blocking(move || {
        let idx = FileIndex::build(&root);
        log::info!("file index built ({} files)", idx.files.len());
        out.store(Arc::new(Some(idx)));
    });
    shared
}

fn should_trigger_notify_event(kind: &notify::EventKind) -> bool {
    match kind {
        notify::EventKind::Create(_) => true,
        notify::EventKind::Remove(_) => true,
        notify::EventKind::Modify(mod_kind) => {
            // Only trigger on name changes (renames) — ignore data/metadata writes.
            matches!(mod_kind, notify::event::ModifyKind::Name(_))
        }
        _ => false,
    }
}

// ── Filesystem watcher ────────────────────────────────────────────────────────

/// Determine whether a single path from a notify::Event should be treated as
/// relevant (i.e., not ignored) according to the repository's .gitignore
/// semantics. This uses `ignore::WalkBuilder` configured the same way as the
/// indexer to ensure consistent behavior with FileIndex::build.
#[cfg(test)]
fn is_path_relevant(root: &Path, path: &Path) -> bool {
    // Only consider paths under the repo root; treat external paths as
    // relevant to be conservative.
    if let Ok(_rel) = path.strip_prefix(root) {
        // Build a Gitignore matcher by discovering all .gitignore files in
        // the repository. This is more expensive than a single WalkBuilder
        // check but ensures nested .gitignore files are respected exactly
        // the same way the indexer would.
        let mut gbuilder = GitignoreBuilder::new(root);

        let mut walker = WalkBuilder::new(root);
        walker.hidden(false).git_ignore(false).git_exclude(false);

        for result in walker.build() {
            if let Ok(entry) = result
                && let Some(name_os) = entry.path().file_name()
                    && let Some(name) = name_os.to_str()
                        && name == ".gitignore" {
                            let _ = gbuilder.add(entry.path());
                        }
        }

        // Also include .git/info/exclude when present
        let git_info_exclude = root.join(".git").join("info").join("exclude");
        if git_info_exclude.is_file() {
            let _ = gbuilder.add(git_info_exclude);
        }

        let gi = match gbuilder.build() {
            Ok(g) => g,
            Err(_) => ignore::gitignore::Gitignore::empty(),
        };

        let is_dir = match path.metadata() {
            Ok(md) => md.is_dir(),
            Err(_) => path.extension().is_none(),
        };

        !gi.matched(path, is_dir).is_ignore()
    } else {
        true
    }
}

/// Returns true if any path in the event is relevant (not ignored).
#[cfg(test)]
fn is_event_relevant(root: &Path, event: &notify::Event) -> bool {
    event.paths.iter().any(|p| is_path_relevant(root, p))
}

/// Watch `root` for file-system changes and rebuild the index automatically.
///
/// Uses `notify-debouncer-mini` (500 ms window) to collapse burst events from
/// the OS layer.  The async loop adds a further 200 ms coalescing sleep so that
/// rapid cascades (e.g. `git checkout`) are collapsed into a single rebuild.
/// Each rebuild is run in a `spawn_blocking` task; a new trigger aborts any
/// in-progress rebuild so only the latest one runs.
pub fn spawn_watcher(root: PathBuf, index: SharedFileIndex) {
    let (trigger_tx, mut trigger_rx) = tokio::sync::mpsc::unbounded_channel::<()>();

    // Dedicated OS thread owns the raw notify watcher. `trigger_tx` is
    // cloned into the callback so the async task can coalesce triggers. Keep
    // the thread alive by blocking on a local receiver instead of repeatedly
    // parking the thread.
    {
        let root = root.clone();
        let trigger_tx_clone = trigger_tx.clone();

        // Build initial Gitignore matcher once and cache it to avoid a full
        // WalkBuilder scan on every notify event. Rebuild the matcher only when
        // a .gitignore (or .git/info/exclude) file changes.
        fn build_gitignore_for_root(root: &Path) -> ignore::gitignore::Gitignore {
            let mut gbuilder = GitignoreBuilder::new(root);
            let mut walker = WalkBuilder::new(root);
            walker.hidden(false).git_ignore(false).git_exclude(false);
            for entry in walker.build().filter_map(|r| r.ok()) {
                if entry.path().file_name().and_then(|n| n.to_str()) == Some(".gitignore") {
                    let _ = gbuilder.add(entry.path());
                }
            }
            // Also include .git/info/exclude when present
            let git_info_exclude = root.join(".git").join("info").join("exclude");
            if git_info_exclude.is_file() {
                let _ = gbuilder.add(git_info_exclude);
            }
            match gbuilder.build() {
                Ok(g) => g,
                Err(_) => ignore::gitignore::Gitignore::empty(),
            }
        }

        let cached_gi = std::sync::Arc::new(std::sync::Mutex::new(build_gitignore_for_root(&root)));

        std::thread::spawn(move || {
            // Create a raw notify watcher with a callback that forwards only
            // structural events for non-ignored paths. Sending into the async
            // channel is cheap; the async task implements the debounce/batching
            // semantics.
            let watcher_root = root.clone();
            let cached_gi = cached_gi.clone();
            let mut watcher = match notify::RecommendedWatcher::new(
                move |res: Result<notify::Event, notify::Error>| {
                    match res {
                        Ok(event) => {
                            // If a .gitignore or .git/info/exclude changed, rebuild cached matcher.
                            let mut rebuild = false;
                            for p in &event.paths {
                                if p.file_name().and_then(|n| n.to_str()) == Some(".gitignore") {
                                    rebuild = true;
                                    break;
                                }
                                if p.to_string_lossy().ends_with(".git/info/exclude") {
                                    rebuild = true;
                                    break;
                                }
                            }
                            if rebuild {
                                let new_gi = build_gitignore_for_root(&watcher_root);
                                if let Ok(mut guard) = cached_gi.lock() {
                                    *guard = new_gi;
                                }
                            }

                            // Use cached matcher to decide relevance without a full walk.
                            let mut any_relevant = false;
                            for p in &event.paths {
                                let is_dir = match p.metadata() {
                                    Ok(md) => md.is_dir(),
                                    Err(_) => p.extension().is_none(),
                                };
                                let guard = cached_gi.lock().unwrap();
                                if !guard.matched(p, is_dir).is_ignore() {
                                    any_relevant = true;
                                    break;
                                }
                            }
                            if !any_relevant {
                                return;
                            }

                            if should_trigger_notify_event(&event.kind) {
                                // best-effort send; ignore errors (receiver closed)
                                let _ = trigger_tx_clone.send(());
                            }
                        }
                        Err(e) => log::warn!("file watcher error: {e}"),
                    }
                },
                notify::Config::default(),
            ) {
                Ok(w) => w,
                Err(e) => {
                    log::warn!("file watcher: failed to create watcher: {e}");
                    return;
                }
            };

            if let Err(e) = watcher.watch(&root, notify::RecursiveMode::Recursive) {
                log::warn!("file watcher: failed to watch {root:?}: {e}");
                return;
            }

            // Block the thread indefinitely. Keeping the watcher value in
            // scope keeps the underlying watcher active.
            let (_tx_keepalive, rx_keepalive) = std::sync::mpsc::channel::<()>();
            let _ = rx_keepalive.recv();
        });
    }

    // Async task coalesces triggers and schedules index rebuilds. This
    // implements the "Option B" debounce strategy: drain any already queued
    // triggers, wait briefly for the filesystem to settle, drain again, then
    // perform a single rebuild for the burst.
    tokio::spawn(async move {
        let mut rebuild: Option<tokio::task::JoinHandle<()>> = None;
        while trigger_rx.recv().await.is_some() {
            // Drain any triggers that were queued before we woke up.
            while trigger_rx.try_recv().is_ok() {}

            // Wait briefly so related events (rename/create/remove etc.) can
            // arrive — this collapses bursts into a single rebuild.
            tokio::time::sleep(std::time::Duration::from_millis(200)).await;

            // Drain anything that arrived while we were sleeping.
            while trigger_rx.try_recv().is_ok() {}

            // Abort any in-progress rebuild and request a fresh one for the
            // current filesystem snapshot.
            if let Some(h) = rebuild.take() {
                h.abort();
            }
            let idx = index.clone();
            let r = root.clone();
            rebuild = Some(tokio::task::spawn_blocking(move || {
                idx.store(Arc::new(Some(FileIndex::build(&r))));
            }));
        }
    });
}

// ── Fuzzy search ─────────────────────────────────────────────────────────────

/// Stateful fuzzy search engine backed by `nucleo_matcher`.
///
/// Create one instance per search task; the `Matcher`'s internal scratch
/// buffer is reused across calls to `search_top` within the same task.
pub struct NucleoSearch {
    matcher: Matcher,
}

impl std::fmt::Debug for NucleoSearch {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        f.write_str("NucleoSearch")
    }
}

impl Default for NucleoSearch {
    fn default() -> Self {
        Self::new()
    }
}

impl NucleoSearch {
    pub fn new() -> Self {
        Self {
            matcher: Matcher::new(Config::DEFAULT),
        }
    }

    /// Fuzzy-search `index` for `query`, returning at most `max` entries
    /// sorted best-first.
    ///
    /// Uses a trigram prefilter to reduce the candidate set, then maintains a
    /// bounded min-heap of size `max` so the full candidate list is never
    /// sorted — only the final top-K are extracted and sorted once.
    pub fn search_top<'a>(
        &mut self,
        index: &'a FileIndex,
        query: &str,
        max: usize,
    ) -> Vec<&'a FileEntry> {
        if query.is_empty() {
            return index.files.iter().take(max).collect();
        }

        let pattern = Pattern::parse(query, CaseMatching::Ignore, Normalization::Smart);

        let mut heap: BinaryHeap<(Reverse<u32>, usize)> = BinaryHeap::with_capacity(max);

        // Helper closure to score a candidate file index.
        let mut process_candidate = |fi: usize| {
            let entry = &index.files[fi];

            let Some(score) = pattern.score(entry.utf32.slice(..), &mut self.matcher) else {
                return;
            };

            if heap.len() < max {
                heap.push((Reverse(score), fi));
            } else if let Some(&(Reverse(min_score), _)) = heap.peek()
                && score > min_score {
                    heap.pop();
                    heap.push((Reverse(score), fi));
                }
        };

        // Use trigram prefilter when possible
        if let Some(indices) = index.trigram_candidate_indices(query) {
            for fi in indices {
                process_candidate(fi);
            }
        } else {
            for fi in 0..index.files.len() {
                process_candidate(fi);
            }
        }

        // Extract and sort results
        let mut results: Vec<(u32, usize)> = heap
            .into_iter()
            .map(|(Reverse(score), idx)| (score, idx))
            .collect();

        results.sort_unstable_by_key(|b| std::cmp::Reverse(b.0));

        results
            .into_iter()
            .map(|(_, idx)| &index.files[idx])
            .collect()
    }

    /// Convenience wrapper returning all results.
    #[allow(dead_code)]
    pub fn search<'a>(&mut self, index: &'a FileIndex, query: &str) -> Vec<&'a FileEntry> {
        self.search_top(index, query, usize::MAX)
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use notify::event::{CreateKind, DataChange, ModifyKind, RenameMode};
    use notify::Event;
    use std::path::PathBuf;
    use tempfile::tempdir;
    use std::fs::{create_dir_all, write};

    #[test]
    fn should_trigger_on_create() {
        let ev = Event { kind: notify::EventKind::Create(CreateKind::File), paths: vec![PathBuf::from("a")], attrs: Default::default() };
        assert!(should_trigger_notify_event(&ev.kind));
    }

    #[test]
    fn should_ignore_modify_data() {
        let ev = Event { kind: notify::EventKind::Modify(ModifyKind::Data(DataChange::Content)), paths: vec![PathBuf::from("a")], attrs: Default::default() };
        assert!(!should_trigger_notify_event(&ev.kind));
    }

    #[test]
    fn should_trigger_rename() {
        let ev = Event { kind: notify::EventKind::Modify(ModifyKind::Name(RenameMode::Both)), paths: vec![PathBuf::from("a")], attrs: Default::default() };
        assert!(should_trigger_notify_event(&ev.kind));
    }

    #[test]
    fn shallow_build_limits_depth() {
        let td = tempdir().unwrap();
        let root = td.path();
        create_dir_all(root.join("a/b")).unwrap();
        write(root.join("file1.txt"), b"").unwrap();
        write(root.join("a").join("file2.txt"), b"").unwrap();
        write(root.join("a").join("b").join("file3.txt"), b"").unwrap();

        let idx_full = FileIndex::build_with_max_depth(root, None);
        let paths_full: Vec<String> = idx_full.files.iter().map(|e| e.path.to_string_lossy().replace('\\', "/").to_string()).collect();
        assert!(paths_full.iter().any(|p| p == "file1.txt"));
        assert!(paths_full.iter().any(|p| p == "a/file2.txt"));
        assert!(paths_full.iter().any(|p| p == "a/b/file3.txt"));

        let idx_shallow = FileIndex::build_with_max_depth(root, Some(1));
        let paths_shallow: Vec<String> = idx_shallow.files.iter().map(|e| e.path.to_string_lossy().replace('\\', "/").to_string()).collect();
        assert!(paths_shallow.iter().any(|p| p == "file1.txt"));
        assert!(!paths_shallow.iter().any(|p| p == "a/file2.txt"));
        assert!(!paths_shallow.iter().any(|p| p == "a/b/file3.txt"));
    }

    #[test]
    fn walkbuilder_respects_gitignore() {
        let td = tempdir().unwrap();
        let root = td.path();
        // create .gitignore listing ignored.txt
        write(root.join(".gitignore"), b"ignored.txt\n").unwrap();
        write(root.join("ignored.txt"), b"").unwrap();
        write(root.join("not_ignored.txt"), b"").unwrap();

        // event for ignored file should be filtered out
        let ev_ignored = Event { kind: notify::EventKind::Create(CreateKind::File), paths: vec![root.join("ignored.txt")], attrs: Default::default() };
        assert!(!is_event_relevant(root, &ev_ignored));

        // event for not ignored file should be relevant
        let ev_not = Event { kind: notify::EventKind::Create(CreateKind::File), paths: vec![root.join("not_ignored.txt")], attrs: Default::default() };
        assert!(is_event_relevant(root, &ev_not));
    }

    // ── ProjectFileRegistry tests ─────────────────────────────────────────────

    fn make_registry_fixture(root: &std::path::Path) {
        // Layout:
        //   root/
        //     .git/           (makes ignore crate treat this as a git root)
        //     src/
        //       main.rs
        //       lib.rs
        //     docs/
        //       guide.md
        //     Cargo.toml
        //     .gitignore  (ignores "ignored/")
        //     ignored/
        //       secret.txt
        create_dir_all(root.join(".git")).unwrap(); // needed for gitignore to be applied
        create_dir_all(root.join("src")).unwrap();
        create_dir_all(root.join("docs")).unwrap();
        create_dir_all(root.join("ignored")).unwrap();
        write(root.join("src/main.rs"), b"fn main() {}").unwrap();
        write(root.join("src/lib.rs"), b"").unwrap();
        write(root.join("docs/guide.md"), b"# guide").unwrap();
        write(root.join("Cargo.toml"), b"[package]").unwrap();
        write(root.join(".gitignore"), b"ignored/\n").unwrap();
        write(root.join("ignored/secret.txt"), b"").unwrap();
    }

    #[test]
    fn registry_build_single_pass() {
        let td = tempdir().unwrap();
        let root = td.path();
        make_registry_fixture(root);

        let reg = ProjectFileRegistry::build(root);

        // Basic file list
        let file_paths: Vec<String> = reg
            .files()
            .iter()
            .map(|e| e.path.to_string_lossy().replace('\\', "/").to_string())
            .collect();

        assert!(file_paths.iter().any(|p| p == "src/main.rs"), "expected src/main.rs");
        assert!(file_paths.iter().any(|p| p == "src/lib.rs"), "expected src/lib.rs");
        assert!(file_paths.iter().any(|p| p == "docs/guide.md"), "expected docs/guide.md");
        assert!(file_paths.iter().any(|p| p == "Cargo.toml"), "expected Cargo.toml");

        // Gitignored file must be absent
        assert!(
            !file_paths.iter().any(|p| p.contains("secret")),
            "gitignored file must not appear"
        );
    }

    #[test]
    fn registry_children_of_returns_sorted_entries() {
        let td = tempdir().unwrap();
        let root = td.path();
        make_registry_fixture(root);

        let reg = ProjectFileRegistry::build(root);

        // children of "src": lib.rs and main.rs (both files, sorted alpha)
        let src_children = reg.children_of(Path::new("src"));
        assert_eq!(src_children.len(), 2, "src should have 2 children");
        assert!(!src_children[0].is_dir);
        assert!(!src_children[1].is_dir);
        let names: Vec<&str> = src_children
            .iter()
            .map(|e| e.path.file_name().unwrap().to_str().unwrap())
            .collect();
        assert_eq!(names, vec!["lib.rs", "main.rs"], "should be alphabetically sorted");
    }

    #[test]
    fn registry_root_children_dirs_before_files() {
        let td = tempdir().unwrap();
        let root = td.path();
        make_registry_fixture(root);

        let reg = ProjectFileRegistry::build(root);
        let root_ch = reg.root_children();

        // Dirs come before files
        let mut saw_file = false;
        for entry in root_ch {
            if entry.is_dir {
                assert!(!saw_file, "all dirs must appear before any file");
            } else {
                saw_file = true;
            }
        }
        assert!(saw_file, "root should contain at least one file");

        // The dirs (docs, src) must be present; ignored/ must not
        let dir_names: Vec<&str> = root_ch
            .iter()
            .filter(|e| e.is_dir)
            .map(|e| e.path.file_name().unwrap().to_str().unwrap())
            .collect();
        assert!(dir_names.contains(&"src"));
        assert!(dir_names.contains(&"docs"));
        assert!(!dir_names.contains(&"ignored"), "gitignored dir must not appear");
    }

    #[test]
    fn registry_files_under_returns_only_prefix_matches() {
        let td = tempdir().unwrap();
        let root = td.path();
        make_registry_fixture(root);

        let reg = ProjectFileRegistry::build(root);

        let under_src = reg.files_under(Path::new("src"));
        assert_eq!(under_src.len(), 2, "only src/* files");
        for p in &under_src {
            assert!(p.starts_with("src"), "all paths must start with src");
        }

        let under_docs = reg.files_under(Path::new("docs"));
        assert_eq!(under_docs.len(), 1);
        assert!(under_docs[0].ends_with("guide.md"));

        // Sibling dir must not appear in under_src
        assert!(!under_src.iter().any(|p| p.starts_with("docs")));
    }

    #[test]
    fn registry_children_of_nonexistent_dir_returns_empty() {
        let td = tempdir().unwrap();
        let root = td.path();
        make_registry_fixture(root);

        let reg = ProjectFileRegistry::build(root);
        // "nonexistent" is not an indexed directory
        let ch = reg.children_of(Path::new("nonexistent"));
        assert!(ch.is_empty(), "must return empty slice, not panic");
    }

    #[test]
    fn registry_contains_is_o1() {
        let td = tempdir().unwrap();
        let root = td.path();
        make_registry_fixture(root);

        let reg = ProjectFileRegistry::build(root);
        assert!(reg.contains(Path::new("src/main.rs")));
        assert!(reg.contains(Path::new("Cargo.toml")));
        assert!(!reg.contains(Path::new("does/not/exist.rs")));
        // gitignored file must not be present
        assert!(!reg.contains(Path::new("ignored/secret.txt")));
    }
}