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::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,
}

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>>>;

// ── 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));
    }
}