fff_search/

grep.rs

//! High-performance grep engine for live content search.
//!
//! Searches file contents using the `grep-searcher` crate with mmap-backed
//! file access. Files are searched in frecency order for optimal pagination
//! performance — the most relevant files are searched first, enabling early
//! termination once enough results are collected.

use crate::constraints::apply_constraints;
use crate::sort_buffer::sort_with_buffer;
use crate::types::FileItem;
use aho_corasick::AhoCorasick;
use fff_grep::lines::{self, LineStep};
use fff_grep::{Searcher, SearcherBuilder, Sink, SinkMatch};
use fff_query_parser::{Constraint, FFFQuery, GrepConfig, QueryParser};
use grep_matcher::{Match, Matcher, NoCaptures, NoError};
use rayon::prelude::*;
use smallvec::SmallVec;
use std::sync::atomic::{AtomicBool, Ordering};
use tracing::Level;

/// Detect if a line looks like a code definition (struct, fn, class, etc.).
///
/// Used at match time to tag `GrepMatch::is_definition` so that output
/// formatters can sort/annotate definitions without re-scanning lines.
///
/// Hand-rolled keyword scanner — avoids regex overhead entirely.
/// Strips optional visibility/modifier keywords, then checks if the next
/// token is a definition keyword followed by a word boundary.
pub fn is_definition_line(line: &str) -> bool {
    let s = line.trim_start().as_bytes();
    let s = skip_modifiers(s);
    is_definition_keyword(s)
}

/// Modifier keywords that can precede a definition keyword.
/// Each must be followed by whitespace to be consumed.
const MODIFIERS: &[&[u8]] = &[
    b"pub",
    b"export",
    b"default",
    b"async",
    b"abstract",
    b"unsafe",
    b"static",
    b"protected",
    b"private",
    b"public",
];

/// Definition keywords to detect.
const DEF_KEYWORDS: &[&[u8]] = &[
    b"struct",
    b"fn",
    b"enum",
    b"trait",
    b"impl",
    b"class",
    b"interface",
    b"function",
    b"def",
    b"func",
    b"type",
    b"module",
    b"object",
];

/// Skip zero or more modifier keywords (including `pub(crate)` style visibility).
fn skip_modifiers(mut s: &[u8]) -> &[u8] {
    loop {
        // Handle `pub(...)` — e.g. `pub(crate)`, `pub(super)`
        if s.starts_with(b"pub(")
            && let Some(end) = s.iter().position(|&b| b == b')')
        {
            s = skip_ws(&s[end + 1..]);
            continue;
        }
        let mut matched = false;
        for &kw in MODIFIERS {
            if s.starts_with(kw) {
                let rest = &s[kw.len()..];
                if rest.first().is_some_and(|b| b.is_ascii_whitespace()) {
                    s = skip_ws(rest);
                    matched = true;
                    break;
                }
            }
        }
        if !matched {
            return s;
        }
    }
}

/// Check if `s` starts with a definition keyword followed by a word boundary.
fn is_definition_keyword(s: &[u8]) -> bool {
    for &kw in DEF_KEYWORDS {
        if s.starts_with(kw) {
            let after = s.get(kw.len());
            // Word boundary: end of input, or next byte is not alphanumeric/underscore
            if after.is_none_or(|b| !b.is_ascii_alphanumeric() && *b != b'_') {
                return true;
            }
        }
    }
    false
}

/// Skip ASCII whitespace.
#[inline]
fn skip_ws(s: &[u8]) -> &[u8] {
    let n = s
        .iter()
        .position(|b| !b.is_ascii_whitespace())
        .unwrap_or(s.len());
    &s[n..]
}

/// Detect import/use lines — lower value than definitions or usages.
///
/// Checks if the line (after leading whitespace) starts with a common
/// import statement prefix. Pure byte-level checks, no regex.
pub fn is_import_line(line: &str) -> bool {
    let s = line.trim_start().as_bytes();
    s.starts_with(b"import ")
        || s.starts_with(b"import\t")
        || (s.starts_with(b"from ") && s.get(5).is_some_and(|&b| b == b'\'' || b == b'"'))
        || s.starts_with(b"use ")
        || s.starts_with(b"use\t")
        || starts_with_require(s)
        || starts_with_include(s)
}

/// Match `require(` or `require (`.
#[inline]
fn starts_with_require(s: &[u8]) -> bool {
    if !s.starts_with(b"require") {
        return false;
    }
    let rest = &s[b"require".len()..];
    rest.first() == Some(&b'(') || (rest.first() == Some(&b' ') && rest.get(1) == Some(&b'('))
}

/// Match `# include ` (with optional spaces after `#`).
#[inline]
fn starts_with_include(s: &[u8]) -> bool {
    if s.first() != Some(&b'#') {
        return false;
    }
    let rest = skip_ws(&s[1..]);
    rest.starts_with(b"include ") || rest.starts_with(b"include\t")
}

/// Determine whether `text` contains any regex metacharacters.
///
/// Uses `regex::escape` from the regex crate as the source of truth — if the
/// escaped form differs from the original, the text contains characters that
/// would be interpreted as regex syntax. This is deterministic and always in
/// sync with the regex engine (no hand-rolled heuristic to maintain).
///
/// Callers can use this to choose between `GrepMode::Regex` and
/// `GrepMode::PlainText`. When `Regex` mode is chosen and the pattern turns
/// out to be invalid, `grep_search` already falls back to plain-text matching
/// and populates `regex_fallback_error`.
pub fn has_regex_metacharacters(text: &str) -> bool {
    regex::escape(text) != text
}

/// Check if `text` contains `\n` that is NOT preceded by another `\`.
///
/// `\n` → true (user wants multiline search)
/// `\\n` → false (escaped backslash followed by literal `n`, e.g. `\\nvim-data`)
#[inline]
fn has_unescaped_newline_escape(text: &str) -> bool {
    let bytes = text.as_bytes();
    let mut i = 0;
    while i < bytes.len().saturating_sub(1) {
        if bytes[i] == b'\\' {
            if bytes[i + 1] == b'n' {
                // Count consecutive backslashes ending at position i
                let mut backslash_count = 1;
                while backslash_count <= i && bytes[i - backslash_count] == b'\\' {
                    backslash_count += 1;
                }
                // Odd number of backslashes before 'n' → real \n escape
                if backslash_count % 2 == 1 {
                    return true;
                }
            }
            // Skip past the escaped character
            i += 2;
        } else {
            i += 1;
        }
    }
    false
}

/// Replace only unescaped `\n` sequences with real newlines.
///
/// `\n` → newline character
/// `\\n` → preserved as-is (literal backslash + `n`)
fn replace_unescaped_newline_escapes(text: &str) -> String {
    let bytes = text.as_bytes();
    let mut result = Vec::with_capacity(bytes.len());
    let mut i = 0;
    while i < bytes.len() {
        if bytes[i] == b'\\' && i + 1 < bytes.len() {
            if bytes[i + 1] == b'n' {
                let mut backslash_count = 1;
                while backslash_count <= i && bytes[i - backslash_count] == b'\\' {
                    backslash_count += 1;
                }
                if backslash_count % 2 == 1 {
                    result.push(b'\n');
                    i += 2;
                    continue;
                }
            }
            result.push(bytes[i]);
            i += 1;
        } else {
            result.push(bytes[i]);
            i += 1;
        }
    }
    String::from_utf8(result).unwrap_or_else(|_| text.to_string())
}

/// Controls how the grep pattern is interpreted.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
pub enum GrepMode {
    /// Default mode: the query is treated as literal text.
    /// The pattern is searched using SIMD-accelerated `memchr::memmem`.
    /// Special regex characters in the query have no special meaning.
    #[default]
    PlainText,
    /// Regex mode: the query is treated as a regular expression.
    /// Uses the same `grep-matcher` / `regex::bytes::Regex` engine.
    /// Invalid regex patterns will return zero results (not an error).
    Regex,
    /// Fuzzy mode: the query is treated as a fuzzy needle matched against
    /// each line using neo_frizbee's Smith-Waterman scoring. Lines are ranked
    /// by match score. Individual matched character positions are reported
    /// as highlight ranges.
    Fuzzy,
}

/// A single content match within a file.
#[derive(Debug, Clone)]
pub struct GrepMatch {
    /// Index into the deduplicated `files` vec of the GrepResult.
    pub file_index: usize,
    /// 1-based line number.
    pub line_number: u64,
    /// 0-based byte column of first match start within the line.
    pub col: usize,
    /// Absolute byte offset of the matched line from the start of the file.
    /// Can be used by the preview to seek directly without scanning from the top.
    pub byte_offset: u64,
    /// The matched line text, truncated to `MAX_LINE_DISPLAY_LEN`.
    pub line_content: String,
    /// Byte offsets `(start, end)` within `line_content` for each match.
    /// Stack-allocated for the common case of ≤4 spans per line.
    pub match_byte_offsets: SmallVec<[(u32, u32); 4]>,
    /// Fuzzy match score from neo_frizbee (only set in Fuzzy grep mode).
    pub fuzzy_score: Option<u16>,
    /// Whether the matched line looks like a definition (struct, fn, class, etc.).
    /// Computed at match time so output formatters don't need to re-scan.
    pub is_definition: bool,
    /// Lines before the match (for context display). Empty when context is 0.
    pub context_before: Vec<String>,
    /// Lines after the match (for context display). Empty when context is 0.
    pub context_after: Vec<String>,
}

/// Result of a grep search.
#[derive(Debug, Clone, Default)]
pub struct GrepResult<'a> {
    pub matches: Vec<GrepMatch>,
    /// Deduplicated file references for the returned matches.
    pub files: Vec<&'a FileItem>,
    /// Number of files actually searched in this call.
    pub total_files_searched: usize,
    /// Total number of indexed files (before filtering).
    pub total_files: usize,
    /// Total number of searchable files (after filtering out binary, too-large, etc.).
    pub filtered_file_count: usize,
    /// The file offset to pass for the next page. `0` if there are no more files.
    /// Callers should store this and pass it as `file_offset` in the next call.
    pub next_file_offset: usize,
    /// When regex mode fails to compile the pattern, the search falls back to
    /// literal matching and this field contains the compilation error message.
    /// The UI can display this to inform the user their regex was invalid.
    pub regex_fallback_error: Option<String>,
}

/// Options for grep search.
#[derive(Debug, Clone)]
pub struct GrepSearchOptions {
    pub max_file_size: u64,
    pub max_matches_per_file: usize,
    pub smart_case: bool,
    /// File-based pagination offset: index into the sorted/filtered file list
    /// to start searching from. Pass 0 for the first page, then use
    /// `GrepResult::next_file_offset` for subsequent pages.
    pub file_offset: usize,
    /// Maximum number of matches to collect before stopping.
    pub page_limit: usize,
    /// How to interpret the search pattern. Defaults to `PlainText`.
    pub mode: GrepMode,
    /// Maximum time in milliseconds to spend searching before returning partial
    /// results. Prevents UI freezes on pathological queries. 0 = no limit.
    pub time_budget_ms: u64,
    /// Number of context lines to include before each match. 0 = disabled.
    pub before_context: usize,
    /// Number of context lines to include after each match. 0 = disabled.
    pub after_context: usize,
    /// Whether to classify each match as a definition line. Adds ~2% overhead
    /// on large repos; disable for interactive grep where it is not needed.
    pub classify_definitions: bool,
}

/// Lightweight wrapper around `regex::bytes::Regex` implementing the
/// `grep_matcher::Matcher` trait required by `grep-searcher`.
///
/// When `is_multiline` is false (the common case), we report `\n` as the
/// line terminator. This enables the **fast** search path in `fff-searcher`:
/// instead of calling `shortest_match()` on every single line (slow path),
/// the searcher calls `find_candidate_line()` once on the entire remaining
/// buffer, letting the regex DFA skip non-matching content in a single pass.
///
/// For multiline patterns we must NOT report a line terminator — the regex
/// can match across line boundaries, so the searcher needs the `MultiLine`
/// strategy.
struct RegexMatcher<'r> {
    regex: &'r regex::bytes::Regex,
    is_multiline: bool,
}

impl Matcher for RegexMatcher<'_> {
    type Captures = NoCaptures;
    type Error = NoError;

    #[inline]
    fn find_at(&self, haystack: &[u8], at: usize) -> Result<Option<Match>, NoError> {
        Ok(self
            .regex
            .find_at(haystack, at)
            .map(|m| Match::new(m.start(), m.end())))
    }

    #[inline]
    fn new_captures(&self) -> Result<NoCaptures, NoError> {
        Ok(NoCaptures::new())
    }

    #[inline]
    fn line_terminator(&self) -> Option<grep_matcher::LineTerminator> {
        if self.is_multiline {
            None
        } else {
            Some(grep_matcher::LineTerminator::byte(b'\n'))
        }
    }
}

/// A `grep_matcher::Matcher` backed by `memchr::memmem` for literal search.
///
/// This is used in `PlainText` mode and is significantly faster than regex
/// for literal patterns: memchr uses SIMD (AVX2/NEON) two-way substring
/// search internally, avoiding the overhead of regex compilation and DFA
/// state transitions.
///
/// Always reports `\n` as line terminator so the searcher uses the fast
/// candidate-line path (plain text can never span lines unless `\n` is
/// literally in the needle, which we handle separately).
struct PlainTextMatcher<'a> {
    /// Case-folded needle bytes for case-insensitive matching.
    /// When case-sensitive, this is the original pattern bytes.
    needle: &'a [u8],
    case_insensitive: bool,
}

impl Matcher for PlainTextMatcher<'_> {
    type Captures = NoCaptures;
    type Error = NoError;

    #[inline]
    fn find_at(&self, haystack: &[u8], at: usize) -> Result<Option<Match>, NoError> {
        let hay = &haystack[at..];

        let found = if self.case_insensitive {
            // ASCII case-insensitive: lowercase the haystack slice on the fly.
            // We scan with a rolling window to avoid allocating a full copy.
            ascii_case_insensitive_find(hay, self.needle)
        } else {
            memchr::memmem::find(hay, self.needle)
        };

        Ok(found.map(|pos| Match::new(at + pos, at + pos + self.needle.len())))
    }

    #[inline]
    fn new_captures(&self) -> Result<NoCaptures, NoError> {
        Ok(NoCaptures::new())
    }

    #[inline]
    fn line_terminator(&self) -> Option<grep_matcher::LineTerminator> {
        Some(grep_matcher::LineTerminator::byte(b'\n'))
    }
}

/// ASCII case-insensitive substring search.
///
/// Uses a SIMD-accelerated two-byte scan (first + last byte of needle) via
/// `memchr2_iter`, then verifies candidates with a fast byte comparison that
/// leverages the fact that ASCII case differs only in bit 0x20.
#[inline]
fn ascii_case_insensitive_find(haystack: &[u8], needle_lower: &[u8]) -> Option<usize> {
    let nlen = needle_lower.len();
    if nlen == 0 {
        return Some(0);
    }

    if haystack.len() < nlen {
        return None;
    }

    let first_lo = needle_lower[0];
    let first_hi = first_lo.to_ascii_uppercase();

    // Single-byte needle: just find either case variant.
    if nlen == 1 {
        return memchr::memchr2(first_lo, first_hi, haystack);
    }

    let tail = &needle_lower[1..];
    let end = haystack.len() - nlen;

    // Scan for candidates where the first byte matches (either case).
    for pos in memchr::memchr2_iter(first_lo, first_hi, &haystack[..=end]) {
        // Verify the remaining bytes with bitwise ASCII case-insensitive compare.
        // For ASCII letters, (a ^ b) & ~0x20 == 0 when they match ignoring case.
        // For non-letters, exact equality is required; OR-ing with 0x20 maps both
        // cases to lowercase and is correct for non-alpha bytes that are already equal.
        let candidate = unsafe { haystack.get_unchecked(pos + 1..pos + nlen) };
        if ascii_case_eq(candidate, tail) {
            return Some(pos);
        }
    }
    None
}

/// Fast ASCII case-insensitive byte slice comparison.
///
/// Returns true if `a` and `b` are equal when compared case-insensitively
/// for ASCII bytes. Both slices must have the same length.
#[inline]
fn ascii_case_eq(a: &[u8], b: &[u8]) -> bool {
    debug_assert_eq!(a.len(), b.len());
    // Process 8 bytes at a time using u64 bitwise operations.
    // For each byte: (x | 0x20) maps uppercase ASCII to lowercase.
    // This is correct for letters. For non-letter bytes where the original
    // values are equal, OR-ing with 0x20 preserves equality. For non-letter
    // bytes where values differ, this can produce false positives only when
    // they differ exactly by 0x20 — we do a fast exact-match check first
    // to catch those rare cases.
    let len = a.len();
    let mut i = 0;

    // Fast path: compare 8 bytes at a time
    while i + 8 <= len {
        let va = u64::from_ne_bytes(unsafe { *(a.as_ptr().add(i) as *const [u8; 8]) });
        let vb = u64::from_ne_bytes(unsafe { *(b.as_ptr().add(i) as *const [u8; 8]) });

        // Quick exact-match shortcut (common for non-alpha content)
        if va != vb {
            // Case-insensitive: OR each byte with 0x20 to fold case
            const MASK: u64 = 0x2020_2020_2020_2020;
            if (va | MASK) != (vb | MASK) {
                return false;
            }
        }
        i += 8;
    }

    // Handle remaining bytes
    while i < len {
        let ha = unsafe { *a.get_unchecked(i) };
        let hb = unsafe { *b.get_unchecked(i) };
        if ha != hb && (ha | 0x20) != (hb | 0x20) {
            return false;
        }
        i += 1;
    }

    true
}

/// Maximum bytes of a matched line to keep for display. Prevents minified
/// JS or huge single-line files from blowing up memory.
const MAX_LINE_DISPLAY_LEN: usize = 512;

struct SinkState {
    file_index: usize,
    matches: Vec<GrepMatch>,
    max_matches: usize,
    before_context: usize,
    after_context: usize,
    classify_definitions: bool,
}

impl SinkState {
    #[inline]
    fn prepare_line<'a>(line_bytes: &'a [u8], mat: &SinkMatch<'_>) -> (&'a [u8], u32, u64, u64) {
        let line_number = mat.line_number().unwrap_or(0);
        let byte_offset = mat.absolute_byte_offset();

        // Trim trailing newline/CR directly on bytes to avoid UTF-8 conversion.
        let trimmed_len = {
            let mut len = line_bytes.len();
            while len > 0 && matches!(line_bytes[len - 1], b'\n' | b'\r') {
                len -= 1;
            }
            len
        };
        let trimmed_bytes = &line_bytes[..trimmed_len];

        // Truncate for display (floor to a char boundary).
        let display_bytes = truncate_display_bytes(trimmed_bytes);

        let display_len = display_bytes.len() as u32;
        (display_bytes, display_len, line_number, byte_offset)
    }

    #[inline]
    #[allow(clippy::too_many_arguments)]
    fn push_match(
        &mut self,
        line_number: u64,
        col: usize,
        byte_offset: u64,
        line_content: String,
        match_byte_offsets: SmallVec<[(u32, u32); 4]>,
        context_before: Vec<String>,
        context_after: Vec<String>,
    ) {
        let is_definition = self.classify_definitions && is_definition_line(&line_content);
        self.matches.push(GrepMatch {
            file_index: self.file_index,
            line_number,
            col,
            byte_offset,
            line_content,
            match_byte_offsets,
            fuzzy_score: None,
            is_definition,
            context_before,
            context_after,
        });
    }

    /// Extract context lines from the full buffer around a matched region.
    fn extract_context(&self, mat: &SinkMatch<'_>) -> (Vec<String>, Vec<String>) {
        if self.before_context == 0 && self.after_context == 0 {
            return (Vec::new(), Vec::new());
        }

        let buffer = mat.buffer();
        let range = mat.bytes_range_in_buffer();

        let mut before = Vec::new();
        if self.before_context > 0 && range.start > 0 {
            // Walk backward from the start of the match line to find preceding lines
            let mut pos = range.start;
            let mut lines_found = 0;
            while lines_found < self.before_context && pos > 0 {
                // Skip the newline just before our current position
                pos -= 1;
                // Find the previous newline
                let line_start = match memchr::memrchr(b'\n', &buffer[..pos]) {
                    Some(nl) => nl + 1,
                    None => 0,
                };
                let line = &buffer[line_start..pos];
                // Trim trailing \r
                let line = if line.last() == Some(&b'\r') {
                    &line[..line.len() - 1]
                } else {
                    line
                };
                let truncated = truncate_display_bytes(line);
                before.push(String::from_utf8_lossy(truncated).into_owned());
                pos = line_start;
                lines_found += 1;
            }
            before.reverse();
        }

        let mut after = Vec::new();
        if self.after_context > 0 && range.end < buffer.len() {
            let mut pos = range.end;
            let mut lines_found = 0;
            while lines_found < self.after_context && pos < buffer.len() {
                // Find the next newline
                let line_end = match memchr::memchr(b'\n', &buffer[pos..]) {
                    Some(nl) => pos + nl,
                    None => buffer.len(),
                };
                let line = &buffer[pos..line_end];
                // Trim trailing \r
                let line = if line.last() == Some(&b'\r') {
                    &line[..line.len() - 1]
                } else {
                    line
                };
                let truncated = truncate_display_bytes(line);
                after.push(String::from_utf8_lossy(truncated).into_owned());
                pos = if line_end < buffer.len() {
                    line_end + 1 // skip past \n
                } else {
                    buffer.len()
                };
                lines_found += 1;
            }
        }

        (before, after)
    }
}

/// Truncate a byte slice for display, respecting UTF-8 char boundaries.
#[inline]
fn truncate_display_bytes(bytes: &[u8]) -> &[u8] {
    if bytes.len() <= MAX_LINE_DISPLAY_LEN {
        bytes
    } else {
        let mut end = MAX_LINE_DISPLAY_LEN;
        while end > 0 && !is_utf8_char_boundary(bytes[end]) {
            end -= 1;
        }
        &bytes[..end]
    }
}

/// Sink for `PlainText` mode.
///
/// Highlights are extracted with SIMD-accelerated `memchr::memmem::Finder`.
/// Case-insensitive matching lowercases the line into a stack buffer before
/// searching, keeping positions 1:1 for ASCII.
/// No regex engine is involved at any point.
struct PlainTextSink<'r> {
    state: SinkState,
    finder: &'r memchr::memmem::Finder<'r>,
    pattern_len: u32,
    case_insensitive: bool,
}

impl Sink for PlainTextSink<'_> {
    type Error = std::io::Error;

    fn matched(&mut self, _searcher: &Searcher, mat: &SinkMatch<'_>) -> Result<bool, Self::Error> {
        if self.state.max_matches != 0 && self.state.matches.len() >= self.state.max_matches {
            return Ok(false);
        }

        let line_bytes = mat.bytes();
        let (display_bytes, display_len, line_number, byte_offset) =
            SinkState::prepare_line(line_bytes, mat);

        let line_content = String::from_utf8_lossy(display_bytes).into_owned();
        let mut match_byte_offsets: SmallVec<[(u32, u32); 4]> = SmallVec::new();
        let mut col = 0usize;
        let mut first = true;

        if self.case_insensitive {
            // Lowercase the display bytes into a stack buffer; positions are 1:1
            // for ASCII so no mapping is needed.
            let mut lowered = [0u8; MAX_LINE_DISPLAY_LEN];
            let len = display_bytes.len().min(MAX_LINE_DISPLAY_LEN);
            for (dst, &src) in lowered[..len].iter_mut().zip(display_bytes) {
                *dst = src.to_ascii_lowercase();
            }

            let mut start_pos = 0usize;
            while let Some(pos) = self.finder.find(&lowered[start_pos..len]) {
                let abs_start = (start_pos + pos) as u32;
                let abs_end = (abs_start + self.pattern_len).min(display_len);
                if first {
                    col = abs_start as usize;
                    first = false;
                }
                match_byte_offsets.push((abs_start, abs_end));
                start_pos += pos + 1;
            }
        } else {
            let mut start_pos = 0usize;
            while let Some(pos) = self.finder.find(&display_bytes[start_pos..]) {
                let abs_start = (start_pos + pos) as u32;
                let abs_end = (abs_start + self.pattern_len).min(display_len);
                if first {
                    col = abs_start as usize;
                    first = false;
                }
                match_byte_offsets.push((abs_start, abs_end));
                start_pos += pos + 1;
            }
        }

        let (context_before, context_after) = self.state.extract_context(mat);
        self.state.push_match(
            line_number,
            col,
            byte_offset,
            line_content,
            match_byte_offsets,
            context_before,
            context_after,
        );
        Ok(true)
    }

    fn finish(&mut self, _: &Searcher, _: &fff_grep::SinkFinish) -> Result<(), Self::Error> {
        Ok(())
    }
}

/// Sink for `Regex` mode.
///
/// Uses the compiled regex to extract precise variable-length highlight spans
/// from each matched line. No `memmem` finder is involved.
struct RegexSink<'r> {
    state: SinkState,
    re: &'r regex::bytes::Regex,
}

impl Sink for RegexSink<'_> {
    type Error = std::io::Error;

    fn matched(
        &mut self,
        _searcher: &Searcher,
        sink_match: &SinkMatch<'_>,
    ) -> Result<bool, Self::Error> {
        if self.state.max_matches != 0 && self.state.matches.len() >= self.state.max_matches {
            return Ok(false);
        }

        let line_bytes = sink_match.bytes();
        let (display_bytes, display_len, line_number, byte_offset) =
            SinkState::prepare_line(line_bytes, sink_match);

        let line_content = String::from_utf8_lossy(display_bytes).into_owned();
        let mut match_byte_offsets: SmallVec<[(u32, u32); 4]> = SmallVec::new();
        let mut col = 0usize;
        let mut first = true;

        for m in self.re.find_iter(display_bytes) {
            let abs_start = m.start() as u32;
            let abs_end = (m.end() as u32).min(display_len);
            if first {
                col = abs_start as usize;
                first = false;
            }
            match_byte_offsets.push((abs_start, abs_end));
        }

        let (context_before, context_after) = self.state.extract_context(sink_match);
        self.state.push_match(
            line_number,
            col,
            byte_offset,
            line_content,
            match_byte_offsets,
            context_before,
            context_after,
        );
        Ok(true)
    }

    fn finish(&mut self, _: &Searcher, _: &fff_grep::SinkFinish) -> Result<(), Self::Error> {
        Ok(())
    }
}

/// A `grep_matcher::Matcher` backed by Aho-Corasick for multi-pattern search.
///
/// Finds the first occurrence of any pattern starting at the given offset.
/// Always reports `\n` as the line terminator for the fast candidate-line path.
struct AhoCorasickMatcher<'a> {
    ac: &'a AhoCorasick,
}

impl Matcher for AhoCorasickMatcher<'_> {
    type Captures = NoCaptures;
    type Error = NoError;

    #[inline]
    fn find_at(&self, haystack: &[u8], at: usize) -> std::result::Result<Option<Match>, NoError> {
        let hay = &haystack[at..];
        let found: Option<aho_corasick::Match> = self.ac.find(hay);
        Ok(found.map(|m| Match::new(at + m.start(), at + m.end())))
    }

    #[inline]
    fn new_captures(&self) -> Result<NoCaptures, NoError> {
        Ok(NoCaptures::new())
    }

    #[inline]
    fn line_terminator(&self) -> Option<grep_matcher::LineTerminator> {
        Some(grep_matcher::LineTerminator::byte(b'\n'))
    }
}

/// Sink for Aho-Corasick multi-pattern mode.
///
/// Collects all pattern match positions on each matched line for highlighting.
struct AhoCorasickSink<'a> {
    state: SinkState,
    ac: &'a AhoCorasick,
}

impl Sink for AhoCorasickSink<'_> {
    type Error = std::io::Error;

    fn matched(&mut self, _searcher: &Searcher, mat: &SinkMatch<'_>) -> Result<bool, Self::Error> {
        if self.state.max_matches != 0 && self.state.matches.len() >= self.state.max_matches {
            return Ok(false);
        }

        let line_bytes = mat.bytes();
        let (display_bytes, display_len, line_number, byte_offset) =
            SinkState::prepare_line(line_bytes, mat);

        let line_content = String::from_utf8_lossy(display_bytes).into_owned();
        let mut match_byte_offsets: SmallVec<[(u32, u32); 4]> = SmallVec::new();
        let mut col = 0usize;
        let mut first = true;

        for m in self.ac.find_iter(display_bytes as &[u8]) {
            let abs_start = m.start() as u32;
            let abs_end = (m.end() as u32).min(display_len);
            if first {
                col = abs_start as usize;
                first = false;
            }
            match_byte_offsets.push((abs_start, abs_end));
        }

        let (context_before, context_after) = self.state.extract_context(mat);
        self.state.push_match(
            line_number,
            col,
            byte_offset,
            line_content,
            match_byte_offsets,
            context_before,
            context_after,
        );
        Ok(true)
    }

    fn finish(&mut self, _: &Searcher, _: &fff_grep::SinkFinish) -> Result<(), Self::Error> {
        Ok(())
    }
}

/// Multi-pattern OR search using Aho-Corasick.
///
/// Builds a single automaton from all patterns and searches each file in one
/// pass. This is significantly faster than regex alternation for literal text
/// searches because Aho-Corasick uses SIMD-accelerated multi-needle matching.
///
/// Returns the same `GrepResult` type as `grep_search`.
pub fn multi_grep_search<'a>(
    files: &'a [FileItem],
    patterns: &[&str],
    constraints: &[fff_query_parser::Constraint<'_>],
    options: &GrepSearchOptions,
) -> GrepResult<'a> {
    let total_files = files.len();

    if patterns.is_empty() || patterns.iter().all(|p| p.is_empty()) {
        return GrepResult {
            total_files,
            filtered_file_count: total_files,
            ..Default::default()
        };
    }

    let (mut files_to_search, mut filtered_file_count) =
        prepare_files_to_search(files, constraints, options);

    // If constraints yielded 0 files and we had FilePath constraints,
    // retry without them (the path token was likely part of the search text).
    if files_to_search.is_empty()
        && let Some(stripped) = strip_file_path_constraints(constraints)
    {
        let (retry_files, retry_count) = prepare_files_to_search(files, &stripped, options);
        files_to_search = retry_files;
        filtered_file_count = retry_count;
    }

    if files_to_search.is_empty() {
        return GrepResult {
            total_files,
            filtered_file_count,
            ..Default::default()
        };
    }

    // Smart case: case-insensitive when all patterns are lowercase
    let case_insensitive = if options.smart_case {
        !patterns.iter().any(|p| p.chars().any(|c| c.is_uppercase()))
    } else {
        false
    };

    let ac = aho_corasick::AhoCorasickBuilder::new()
        .ascii_case_insensitive(case_insensitive)
        .build(patterns)
        .expect("Aho-Corasick build should not fail for literal patterns");

    let searcher = {
        let mut b = SearcherBuilder::new();
        b.line_number(true);
        b
    }
    .build();

    let ac_matcher = AhoCorasickMatcher { ac: &ac };
    run_file_search(
        &files_to_search,
        options,
        total_files,
        filtered_file_count,
        None,
        |file_bytes: &[u8], max_matches: usize| {
            let state = SinkState {
                file_index: 0,
                matches: Vec::with_capacity(4),
                max_matches,
                before_context: options.before_context,
                after_context: options.after_context,
                classify_definitions: options.classify_definitions,
            };

            let mut sink = AhoCorasickSink { state, ac: &ac };

            if let Err(e) = searcher.search_slice(&ac_matcher, file_bytes, &mut sink) {
                tracing::error!(error = %e, "Grep (aho-corasick multi) search failed");
            }

            sink.state.matches
        },
    )
}

// copied from the rust u8 private method
#[inline]
const fn is_utf8_char_boundary(b: u8) -> bool {
    (b as i8) >= -0x40
}

/// Build a regex from the user's grep text.
///
/// In `PlainText` mode:
/// - Escapes the input for literal matching (users type text, not regex)
/// - Applies smart case: case-insensitive unless query has uppercase
/// - Detects `\n` for multiline
///
/// In `Regex` mode:
/// - The input is passed directly to the regex engine without escaping
/// - Smart case still applies
/// - Returns `None` for invalid regex patterns — the caller falls back to literal mode
fn build_regex(pattern: &str, smart_case: bool) -> Result<regex::bytes::Regex, String> {
    if pattern.is_empty() {
        return Err("empty pattern".to_string());
    }

    let regex_pattern = if pattern.contains("\\n") {
        pattern.replace("\\n", "\n")
    } else {
        pattern.to_string()
    };

    let case_insensitive = if smart_case {
        !pattern.chars().any(|c| c.is_uppercase())
    } else {
        false
    };

    regex::bytes::RegexBuilder::new(&regex_pattern)
        .case_insensitive(case_insensitive)
        .multi_line(true)
        .unicode(false)
        .build()
        .map_err(|e| e.to_string())
}

/// Convert character-position indices from neo_frizbee into byte-offset
/// pairs (start, end) suitable for `match_byte_offsets`.
///
/// frizbee returns character positions (0-based index into the char
/// iterator). We need byte ranges because the UI renderer and Lua layer
/// use byte offsets for extmark highlights.
///
/// Each matched character becomes its own (byte_start, byte_end) pair.
/// Adjacent characters are merged into a single contiguous range.
fn char_indices_to_byte_offsets(line: &str, char_indices: &[usize]) -> SmallVec<[(u32, u32); 4]> {
    if char_indices.is_empty() {
        return SmallVec::new();
    }

    // Build a map: char_index -> (byte_start, byte_end) for all chars.
    // Iterating all chars is O(n) in the line length which is bounded by MAX_LINE_DISPLAY_LEN (512).
    let char_byte_ranges: Vec<(usize, usize)> = line
        .char_indices()
        .map(|(byte_pos, ch)| (byte_pos, byte_pos + ch.len_utf8()))
        .collect();

    // Convert char indices to byte ranges, merging adjacent ranges
    let mut result: SmallVec<[(u32, u32); 4]> = SmallVec::with_capacity(char_indices.len());

    for &ci in char_indices {
        if ci >= char_byte_ranges.len() {
            continue; // out of bounds (shouldn't happen with valid data)
        }
        let (start, end) = char_byte_ranges[ci];
        // Merge with previous range if adjacent
        if let Some(last) = result.last_mut()
            && last.1 == start as u32
        {
            last.1 = end as u32;
            continue;
        }
        result.push((start as u32, end as u32));
    }

    result
}

#[tracing::instrument(skip_all, level = Level::DEBUG)]
fn run_file_search<'a, F>(
    files_to_search: &[&'a FileItem],
    options: &GrepSearchOptions,
    total_files: usize,
    filtered_file_count: usize,
    regex_fallback_error: Option<String>,
    search_file: F,
) -> GrepResult<'a>
where
    F: Fn(&[u8], usize) -> Vec<GrepMatch> + Sync,
{
    let time_budget = if options.time_budget_ms > 0 {
        Some(std::time::Duration::from_millis(options.time_budget_ms))
    } else {
        None
    };

    let search_start = std::time::Instant::now();
    let budget_exceeded = AtomicBool::new(false);

    // Parallel phase: search all files concurrently using rayon.
    // Every file is visited (no early-exit gaps), so per_file_results is a
    // contiguous, order-preserving subset — pagination offsets stay correct.
    // The time budget acts as the work bound; there is no separate file cap.
    let per_file_results: Vec<(usize, &'a FileItem, Vec<GrepMatch>)> = files_to_search
        .par_iter()
        .enumerate()
        .filter_map(|(idx, file)| {
            // Time budget check (relaxed — checked once per file, not per line).
            if let Some(budget) = time_budget
                && search_start.elapsed() > budget
            {
                budget_exceeded.store(true, Ordering::Relaxed);
                return None;
            }

            let content = file.get_mmap()?;
            let file_matches = search_file(content, options.max_matches_per_file);

            if file_matches.is_empty() {
                return None;
            }

            Some((idx, *file, file_matches))
        })
        .collect();

    collect_grep_results(
        per_file_results,
        files_to_search.len(),
        options,
        total_files,
        filtered_file_count,
        regex_fallback_error,
        budget_exceeded.load(Ordering::Relaxed),
    )
}

/// Flatten per-file results into the final `GrepResult`.
///
/// Shared post-processing for both `run_file_search` (simple closure) and
/// `fuzzy_grep_search` (which uses `map_init` for per-thread matcher reuse).
fn collect_grep_results<'a>(
    per_file_results: Vec<(usize, &'a FileItem, Vec<GrepMatch>)>,
    files_to_search_len: usize,
    options: &GrepSearchOptions,
    total_files: usize,
    filtered_file_count: usize,
    regex_fallback_error: Option<String>,
    budget_exceeded: bool,
) -> GrepResult<'a> {
    let page_limit = options.page_limit;

    // Each match stores a `file_index` pointing into `result_files` so that
    // consumers (FFI JSON, Lua) can look up file metadata without duplicating
    // it across every match from the same file.
    let mut result_files: Vec<&'a FileItem> = Vec::new();
    let mut all_matches: Vec<GrepMatch> = Vec::new();
    // files_consumed tracks how far into files_to_search we have advanced,
    // counting every file whose results were emitted (with or without matches).
    // We use the batch_idx of the last consumed file + 1, which is correct
    // because per_file_results only contains files that had matches, and
    // files between them that had no matches were still searched and can be
    // safely skipped on the next page.
    let mut files_consumed: usize = 0;

    for (batch_idx, file, file_matches) in per_file_results {
        // batch_idx is the 0-based position in files_to_search.
        // Advance files_consumed to include this file and all no-match files before it.
        files_consumed = batch_idx + 1;

        let file_result_idx = result_files.len();
        result_files.push(file);

        for mut m in file_matches {
            m.file_index = file_result_idx;
            all_matches.push(m);
        }

        // page_limit is a soft cap: we always finish the current file before
        // stopping, so no matches are dropped. A page may return up to
        // page_limit + max_matches_per_file - 1 matches in the worst case.
        if all_matches.len() >= page_limit {
            break;
        }
    }

    // If no file had any match, we searched the entire slice.
    if result_files.is_empty() {
        files_consumed = files_to_search_len;
    }

    let has_more = budget_exceeded
        || (all_matches.len() >= page_limit && files_consumed < files_to_search_len);

    let next_file_offset = if has_more {
        options.file_offset + files_consumed
    } else {
        0
    };

    GrepResult {
        matches: all_matches,
        files: result_files,
        total_files_searched: files_consumed,
        total_files,
        filtered_file_count,
        next_file_offset,
        regex_fallback_error,
    }
}

/// Filter files by constraints and size/binary checks, sort by frecency,
/// and apply file-based pagination.
///
/// Returns `(paginated_files, filtered_file_count)`. The paginated slice
/// is empty if the offset is past the end of available files.
fn prepare_files_to_search<'a>(
    files: &'a [FileItem],
    constraints: &[fff_query_parser::Constraint<'_>],
    options: &GrepSearchOptions,
) -> (Vec<&'a FileItem>, usize) {
    let prefiltered: Vec<&FileItem> = if constraints.is_empty() {
        files
            .iter()
            .filter(|f| !f.is_binary && f.size > 0 && f.size <= options.max_file_size)
            .collect()
    } else {
        match apply_constraints(files, constraints) {
            Some(constrained) => constrained
                .into_iter()
                .filter(|f| !f.is_binary && f.size > 0 && f.size <= options.max_file_size)
                .collect(),
            None => files
                .iter()
                .filter(|f| !f.is_binary && f.size > 0 && f.size <= options.max_file_size)
                .collect(),
        }
    };

    let total_count = prefiltered.len();

    // Sort by frecency (files are stored by path, not frecency)
    let mut sorted_files = prefiltered;
    sort_with_buffer(&mut sorted_files, |a, b| {
        b.total_frecency_score
            .cmp(&a.total_frecency_score)
            .then(b.modified.cmp(&a.modified))
    });

    if options.file_offset < total_count {
        let sorted_files = sorted_files.split_off(options.file_offset);
        (sorted_files, total_count)
    } else {
        (Vec::new(), total_count)
    }
}

/// Fuzzy grep search using SIMD-accelerated `neo_frizbee::match_list`.
///
/// # Why this doesn't use `grep-searcher` / `GrepSink`
///
/// PlainText and Regex modes use the `grep-searcher` pipeline: a `Matcher`
/// finds candidate lines, and a `Sink` collects them one at a time. This
/// works well because memchr/regex can *skip* non-matching lines in O(n)
/// without scoring every one.
///
/// Fuzzy matching is fundamentally different. Every line is a candidate —
/// the Smith-Waterman score determines whether it passes, not a substring
/// or pattern test. The `Matcher::find_at` trait forces per-line calls to
/// the *reference* (scalar) smith-waterman, which is O(needle × line_len)
/// per line. For a 10k-line file that's 10k sequential reference calls.
///
/// `neo_frizbee::match_list` solves this by batching lines into
/// fixed-width SIMD buckets (4, 8, 12 … 512 bytes) and scoring 16+
/// haystacks per SIMD invocation. A single `match_list` call over the
/// entire file replaces 10k individual `match_indices` calls. We then
/// call `match_indices` *only* on the ~5-20 lines that pass `min_score`
/// to extract character highlight positions.
///
/// Line splitting uses `memchr::memchr` (the same SIMD-accelerated byte
/// search that `grep-searcher` and `bstr::ByteSlice::find_byte` use
/// internally) to locate `\n` terminators. This gives us the same
/// performance as the searcher's `LineStep` iterator without pulling in
/// the full searcher machinery.
///
/// For each file:
///   1. mmap the file, split lines via memchr '\n' (tracking line numbers + byte offsets)
///   2. Batch all lines through `match_list` (SIMD smith-waterman)
///   3. Filter results by `min_score`
///   4. Call `match_indices` only on passing lines to get character highlight offsets
fn fuzzy_grep_search<'a>(
    grep_text: &str,
    files_to_search: &[&'a FileItem],
    options: &GrepSearchOptions,
    total_files: usize,
    filtered_file_count: usize,
    case_insensitive: bool,
) -> GrepResult<'a> {
    // max_typos controls how many *needle* characters can be unmatched.
    // A transposition (e.g. "shcema" → "schema") costs ~1 typo with
    // default gap penalties. We scale max_typos by needle length:
    //   1-2 chars → 0 typos (exact subsequence only)
    //   3-5 chars → 1 typo
    //   6+  chars → 2 typos
    let max_typos = (grep_text.len() / 3).min(2);
    let scoring = neo_frizbee::Scoring {
        // Use default gap penalties. Higher values (e.g. 20) cause
        // smith-waterman to prefer *dropping needle chars* over paying
        // gap costs, which inflates the typo count and breaks
        // transposition matching ("shcema" → "schema" becomes 3 typos
        // instead of 1). Scattered matches are filtered by max_typos
        // and the match span check below instead.
        exact_match_bonus: 100,
        // gap_open_penalty: 4,
        // gap_extend_penalty: 2,
        prefix_bonus: 0,
        capitalization_bonus: if case_insensitive { 0 } else { 4 },
        ..neo_frizbee::Scoring::default()
    };

    let matcher = neo_frizbee::Matcher::new(
        grep_text,
        &neo_frizbee::Config {
            // Use the real max_typos so frizbee's SIMD prefilter actually rejects non-matching lines (~2 SIMD instructions per line vs full SW scoring).
            max_typos: Some(max_typos as u16),
            sort: false,
            scoring,
        },
    );

    // Minimum score threshold: 50% of a perfect contiguous match.
    // With default scoring (match_score=12, matching_case_bonus=4 = 16/char),
    // a transposition costs ~5 from a gap, keeping the score well above 50%.
    let perfect_score = (grep_text.len() as u16) * 16;
    let min_score = (perfect_score * 50) / 100;

    // Maximum allowed span of matched characters in the haystack, relative
    // to needle length.
    //
    // We allow up to needle_len * 2 to accommodate fuzzy subsequence
    // matches in longer identifiers (e.g. "SortedMap" → "SortedArrayMap"
    // has span 13 for needle 9). Quality is enforced by the density and
    // gap checks below, not just span alone.
    let max_match_span = grep_text.len() * 2;
    let needle_len = grep_text.len();

    // We scale by needle_len: longer needles tolerate more gaps.
    let max_gaps = (needle_len / 4).max(1);

    // File-level prefilter: collect unique needle chars (both cases) for
    // a fast memchr scan.  If a file doesn't contain enough distinct
    // needle characters, skip it entirely — no line splitting needed.
    let needle_bytes = grep_text.as_bytes();
    let mut unique_needle_chars: Vec<u8> = Vec::new();
    for &b in needle_bytes {
        let lo = b.to_ascii_lowercase();
        let hi = b.to_ascii_uppercase();
        if !unique_needle_chars.contains(&lo) {
            unique_needle_chars.push(lo);
        }
        if lo != hi && !unique_needle_chars.contains(&hi) {
            unique_needle_chars.push(hi);
        }
    }
    // How many distinct needle chars must appear in the file.
    // With max_typos allowed, we need at least (unique_count - max_typos).
    let unique_count = {
        let mut seen = [false; 256];
        for &b in needle_bytes {
            seen[b.to_ascii_lowercase() as usize] = true;
        }
        seen.iter().filter(|&&v| v).count()
    };
    let min_chars_required = unique_count.saturating_sub(max_typos);

    let time_budget = if options.time_budget_ms > 0 {
        Some(std::time::Duration::from_millis(options.time_budget_ms))
    } else {
        None
    };
    let search_start = std::time::Instant::now();
    let budget_exceeded = AtomicBool::new(false);
    let max_matches_per_file = options.max_matches_per_file;

    // Parallel phase with `map_init`: each rayon worker thread clones the
    // matcher once and reuses it across all files that thread processes.
    // This avoids per-file clone overhead (CPUID detection + matrix alloc).
    let per_file_results: Vec<(usize, &'a FileItem, Vec<GrepMatch>)> = files_to_search
        .par_iter()
        .enumerate()
        .map_init(
            || matcher.clone(),
            |matcher, (idx, file)| {
                if let Some(budget) = time_budget
                    && search_start.elapsed() > budget
                {
                    budget_exceeded.store(true, Ordering::Relaxed);
                    return None;
                }

                let file_bytes = file.get_mmap()?;

                // File-level prefilter: check if enough distinct needle chars
                // exist anywhere in the file bytes.  Uses memchr for speed.
                if min_chars_required > 0 {
                    let mut chars_found = 0usize;
                    for &ch in &unique_needle_chars {
                        if memchr::memchr(ch, file_bytes).is_some() {
                            chars_found += 1;
                            if chars_found >= min_chars_required {
                                break;
                            }
                        }
                    }
                    if chars_found < min_chars_required {
                        return None;
                    }
                }

                // Validate the whole file as UTF-8 once upfront. Source code
                // files are virtually always valid UTF-8; this single check
                // replaces per-line from_utf8 calls (~8% of fuzzy grep time).
                let file_is_utf8 = std::str::from_utf8(file_bytes).is_ok();

                // Reuse grep-searcher's LineStep for SIMD-accelerated line iteration.
                let mut stepper = LineStep::new(b'\n', 0, file_bytes.len());
                let estimated_lines = (file_bytes.len() / 40).max(64);
                let mut file_lines: Vec<&str> = Vec::with_capacity(estimated_lines);
                let mut line_meta: Vec<(u64, u64)> = Vec::with_capacity(estimated_lines);
                let line_term_lf = grep_matcher::LineTerminator::byte(b'\n');
                let line_term_cr = grep_matcher::LineTerminator::byte(b'\r');

                let mut line_number: u64 = 1;
                while let Some(line_match) = stepper.next_match(file_bytes) {
                    let byte_offset = line_match.start() as u64;

                    // Strip line terminators (\n, \r).
                    let trimmed = lines::without_terminator(
                        lines::without_terminator(&file_bytes[line_match], line_term_lf),
                        line_term_cr,
                    );

                    if !trimmed.is_empty() {
                        // SAFETY: when the whole file is valid UTF-8, every
                        // sub-slice split on ASCII byte boundaries (\n, \r)
                        // is also valid UTF-8.
                        let line_str = if file_is_utf8 {
                            unsafe { std::str::from_utf8_unchecked(trimmed) }
                        } else if let Ok(s) = std::str::from_utf8(trimmed) {
                            s
                        } else {
                            line_number += 1;
                            continue;
                        };
                        file_lines.push(line_str);
                        line_meta.push((line_number, byte_offset));
                    }

                    line_number += 1;
                }

                if file_lines.is_empty() {
                    return None;
                }

                // Single-pass: score + indices in one Smith-Waterman run per line.
                let matches_with_indices = matcher.match_list_indices(&file_lines);
                let mut file_matches: Vec<GrepMatch> = Vec::new();

                for mut match_indices in matches_with_indices {
                    if match_indices.score < min_score {
                        continue;
                    }

                    let idx = match_indices.index as usize;
                    let raw_line = file_lines[idx];

                    let truncated = truncate_display_bytes(raw_line.as_bytes());
                    let display_line = if truncated.len() < raw_line.len() {
                        // SAFETY: truncate_display_bytes preserves UTF-8 char boundaries
                        &raw_line[..truncated.len()]
                    } else {
                        raw_line
                    };

                    // If the line was truncated, re-compute indices on the shorter string.
                    if display_line.len() < raw_line.len() {
                        let Some(re_indices) = matcher
                            .match_list_indices(&[display_line])
                            .into_iter()
                            .next()
                        else {
                            continue;
                        };
                        match_indices = re_indices;
                    }

                    // upstream returns indices in reverse order, sort ascending
                    match_indices.indices.sort_unstable();

                    // Minimum matched chars: at least (needle_len - 1) characters
                    // must appear in the match indices. This allows one missing
                    // char (a single typo/transposition) but rejects matches that
                    // only hit a partial substring (e.g. "HashMap" for "shcema").
                    let min_matched = needle_len.saturating_sub(1).max(1);
                    if match_indices.indices.len() < min_matched {
                        continue;
                    }

                    let indices = &match_indices.indices;

                    if let (Some(&first), Some(&last)) = (indices.first(), indices.last()) {
                        // Span check: reject widely scattered matches.
                        let span = last - first + 1;
                        if span > max_match_span {
                            continue;
                        }

                        // Density check: matched chars / span must be dense enough.
                        // Relaxed for perfect subsequence matches (all needle chars
                        // present), stricter when typos are involved.
                        let density = (indices.len() * 100) / span;
                        let min_density = if indices.len() >= needle_len {
                            50 // Perfect subsequence — relaxed
                        } else {
                            70 // Has typos — stricter
                        };
                        if density < min_density {
                            continue;
                        }

                        // Gap count check: count discontinuities in the indices.
                        let gap_count = indices.windows(2).filter(|w| w[1] != w[0] + 1).count();
                        if gap_count > max_gaps {
                            continue;
                        }
                    }

                    let (ln, bo) = line_meta[idx];
                    let match_byte_offsets =
                        char_indices_to_byte_offsets(display_line, &match_indices.indices);
                    let col = match_byte_offsets
                        .first()
                        .map(|r| r.0 as usize)
                        .unwrap_or(0);

                    file_matches.push(GrepMatch {
                        file_index: 0,
                        line_number: ln,
                        col,
                        byte_offset: bo,
                        is_definition: options.classify_definitions
                            && is_definition_line(display_line),
                        line_content: display_line.to_string(),
                        match_byte_offsets,
                        fuzzy_score: Some(match_indices.score),
                        context_before: Vec::new(),
                        context_after: Vec::new(),
                    });

                    if max_matches_per_file != 0 && file_matches.len() >= max_matches_per_file {
                        break;
                    }
                }

                if file_matches.is_empty() {
                    return None;
                }

                Some((idx, *file, file_matches))
            },
        )
        .flatten()
        .collect();

    collect_grep_results(
        per_file_results,
        files_to_search.len(),
        options,
        total_files,
        filtered_file_count,
        None,
        budget_exceeded.load(Ordering::Relaxed),
    )
}

/// Perform a grep search across all indexed files.
///
/// When `query` is empty, returns git-modified/untracked files sorted by
/// frecency for the "welcome state" UI.
pub fn grep_search<'a>(
    files: &'a [FileItem],
    query: &FFFQuery<'_>,
    options: &GrepSearchOptions,
) -> GrepResult<'a> {
    let total_files = files.len();

    // Extract the grep text and file constraints from the parsed query.
    // For grep, the search pattern is the original query with constraint tokens
    // removed. All non-constraint text tokens are collected and joined with
    // spaces to form the grep pattern:
    //   "name = *.rs someth" -> grep "name = someth" with constraint Extension("rs")
    let constraints_from_query = &query.constraints[..];

    let grep_text = if !matches!(query.fuzzy_query, fff_query_parser::FuzzyQuery::Empty) {
        query.grep_text()
    } else {
        // Constraint-only or empty query — use raw_query for backslash-escape handling.
        let t = query.raw_query.trim();
        if t.starts_with('\\') && t.len() > 1 {
            let suffix = &t[1..];
            let parser = QueryParser::new(GrepConfig);
            if !parser.parse(suffix).constraints.is_empty() {
                suffix.to_string()
            } else {
                t.to_string()
            }
        } else {
            t.to_string()
        }
    };

    if grep_text.is_empty() {
        return GrepResult {
            total_files,
            filtered_file_count: total_files,
            next_file_offset: 0,
            matches: Vec::with_capacity(4),
            files: Vec::new(),
            ..Default::default()
        };
    }

    // Filter, sort, and paginate files (shared across all modes)
    let (mut files_to_search, mut filtered_file_count) =
        prepare_files_to_search(files, constraints_from_query, options);

    // If constraints yielded 0 files and we had a FilePath constraint,
    // retry without it — the filename may not exist in this repo.
    // Keep the original grep_text (e.g. "ActorAuth") rather than restoring
    // the raw query ("nonexistent.rs ActorAuth"), since the search term
    // was correctly extracted by the parser.
    if files_to_search.is_empty()
        && let Some(stripped) = strip_file_path_constraints(constraints_from_query)
    {
        let (retry_files, retry_count) = prepare_files_to_search(files, &stripped, options);
        files_to_search = retry_files;
        filtered_file_count = retry_count;
    }

    if files_to_search.is_empty() {
        return GrepResult {
            total_files,
            filtered_file_count,
            next_file_offset: 0,
            ..Default::default()
        };
    }

    let case_insensitive = if options.smart_case {
        !grep_text.chars().any(|c| c.is_uppercase())
    } else {
        false
    };

    let mut regex_fallback_error: Option<String> = None;
    let regex = match options.mode {
        GrepMode::PlainText => None,
        GrepMode::Fuzzy => {
            return fuzzy_grep_search(
                &grep_text,
                &files_to_search,
                options,
                total_files,
                filtered_file_count,
                case_insensitive,
            );
        }
        GrepMode::Regex => build_regex(&grep_text, options.smart_case)
            .inspect_err(|err| {
                tracing::warn!("Regex compilation failed for {}. Error {}", grep_text, err);

                regex_fallback_error = Some(err.to_string());
            })
            .ok(),
    };

    let is_multiline = has_unescaped_newline_escape(&grep_text);

    let effective_pattern = if is_multiline {
        replace_unescaped_newline_escapes(&grep_text)
    } else {
        grep_text.to_string()
    };

    // Build the finder pattern once — used by PlainTextSink (and as a
    // literal-needle fallback anchor when regex compilation fell back to plain).
    let finder_pattern: Vec<u8> = if case_insensitive {
        effective_pattern.as_bytes().to_ascii_lowercase()
    } else {
        effective_pattern.as_bytes().to_vec()
    };
    let finder = memchr::memmem::Finder::new(&finder_pattern);
    let pattern_len = finder_pattern.len() as u32;

    // `PlainTextMatcher` is used by the grep-searcher engine for line detection.
    // `PlainTextSink` / `RegexSink` handle highlight extraction independently.
    let plain_matcher = PlainTextMatcher {
        needle: &finder_pattern,
        case_insensitive,
    };

    let searcher = {
        let mut b = SearcherBuilder::new();
        b.line_number(true).multi_line(is_multiline);
        b
    }
    .build();

    // Dispatch to the appropriate sink type at the boundary — zero runtime
    // branching inside the per-line hot path.
    run_file_search(
        &files_to_search,
        options,
        total_files,
        filtered_file_count,
        regex_fallback_error,
        |file_bytes: &[u8], max_matches: usize| {
            let state = SinkState {
                file_index: 0, // set by run_file_search
                matches: Vec::with_capacity(4),
                max_matches,
                before_context: options.before_context,
                after_context: options.after_context,
                classify_definitions: options.classify_definitions,
            };

            match regex {
                Some(ref re) => {
                    let regex_matcher = RegexMatcher {
                        regex: re,
                        is_multiline,
                    };
                    let mut sink = RegexSink { state, re };
                    if let Err(e) = searcher.search_slice(&regex_matcher, file_bytes, &mut sink) {
                        tracing::error!(error = %e, "Grep (regex) search failed");
                    }
                    sink.state.matches
                }
                None => {
                    let mut sink = PlainTextSink {
                        state,
                        finder: &finder,
                        pattern_len,
                        case_insensitive,
                    };
                    if let Err(e) = searcher.search_slice(&plain_matcher, file_bytes, &mut sink) {
                        tracing::error!(error = %e, "Grep (plain text) search failed");
                    }
                    sink.state.matches
                }
            }
        },
    )
}

/// Parse a grep query using the GrepConfig parser.
pub fn parse_grep_query(query: &str) -> FFFQuery<'_> {
    let parser = QueryParser::new(GrepConfig);
    parser.parse(query)
}

fn strip_file_path_constraints<'a>(
    constraints: &[Constraint<'a>],
) -> Option<fff_query_parser::ConstraintVec<'a>> {
    if !constraints
        .iter()
        .any(|c| matches!(c, Constraint::FilePath(_)))
    {
        return None;
    }

    let filtered: fff_query_parser::ConstraintVec<'a> = constraints
        .iter()
        .filter(|c| !matches!(c, Constraint::FilePath(_)))
        .cloned()
        .collect();

    Some(filtered)
}

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

    #[test]
    fn test_unescaped_newline_detection() {
        // Single \n → multiline
        assert!(has_unescaped_newline_escape("foo\\nbar"));
        // \\n → escaped backslash + literal n, NOT multiline
        // (this is what the user types when grepping Rust source with `\\nvim`)
        assert!(!has_unescaped_newline_escape("foo\\\\nvim-data"));
        // Real-world: source file has literal \\AppData\\Local\\nvim-data
        // (double backslash in the file, so user types double backslash)
        assert!(!has_unescaped_newline_escape(
            r#"format!("{}\\AppData\\Local\\nvim-data","#
        ));
        // No \n at all
        assert!(!has_unescaped_newline_escape("hello world"));
        // \\\\n → even number of backslashes before n → NOT multiline
        assert!(!has_unescaped_newline_escape("foo\\\\\\\\nbar"));
        // \\\n → 3 backslashes: first two pair up, third + n = \n → multiline
        assert!(has_unescaped_newline_escape("foo\\\\\\nbar"));
    }

    #[test]
    fn test_replace_unescaped_newline() {
        // \n → real newline
        assert_eq!(replace_unescaped_newline_escapes("foo\\nbar"), "foo\nbar");
        // \\n → preserved as-is
        assert_eq!(
            replace_unescaped_newline_escapes("foo\\\\nvim"),
            "foo\\\\nvim"
        );
    }

    #[test]
    fn test_fuzzy_typo_scoring() {
        // Mirror the config from fuzzy_grep_search
        let needle = "schema";
        let max_typos = (needle.len() / 3).min(2); // 2
        let config = neo_frizbee::Config {
            max_typos: Some(max_typos as u16),
            sort: false,
            scoring: neo_frizbee::Scoring {
                exact_match_bonus: 100,
                ..neo_frizbee::Scoring::default()
            },
        };
        let min_matched = needle.len().saturating_sub(1).max(1); // 5
        let max_match_span = needle.len() + 4; // 10

        // Helper: check if a match would pass our post-filters
        let passes = |n: &str, h: &str| -> bool {
            let Some(mut mi) = neo_frizbee::match_list_indices(n, &[h], &config)
                .into_iter()
                .next()
            else {
                return false;
            };
            // upstream returns indices in reverse order, sort ascending
            mi.indices.sort_unstable();
            if mi.indices.len() < min_matched {
                return false;
            }
            if let (Some(&first), Some(&last)) = (mi.indices.first(), mi.indices.last()) {
                let span = last - first + 1;
                if span > max_match_span {
                    return false;
                }
                let density = (mi.indices.len() * 100) / span;
                if density < 70 {
                    return false;
                }
            }
            true
        };

        // Exact match: must pass
        assert!(passes("schema", "schema"));
        // Exact in longer line: must pass
        assert!(passes("schema", "  schema: String,"));
        // In identifier: must pass
        assert!(passes("schema", "pub fn validate_schema() {}"));
        // Transposition: must pass
        assert!(passes("shcema", "schema"));
        // Partial "ema" only line: must NOT pass
        assert!(!passes("schema", "it has ema in it"));
        // Completely unrelated: must NOT pass
        assert!(!passes("schema", "hello world foo bar"));
    }

    #[test]
    fn test_multi_grep_search() {
        use crate::types::FileItem;
        use std::io::Write;

        // Create temp files with known content
        let dir = tempfile::tempdir().unwrap();

        // File 1: has "GrepMode" and "GrepMatch"
        let file1_path = dir.path().join("grep.rs");
        {
            let mut f = std::fs::File::create(&file1_path).unwrap();
            writeln!(f, "pub enum GrepMode {{").unwrap();
            writeln!(f, "    PlainText,").unwrap();
            writeln!(f, "    Regex,").unwrap();
            writeln!(f, "}}").unwrap();
            writeln!(f, "pub struct GrepMatch {{").unwrap();
            writeln!(f, "    pub line_number: u64,").unwrap();
            writeln!(f, "}}").unwrap();
        }

        // File 2: has "PlainTextMatcher" only
        let file2_path = dir.path().join("matcher.rs");
        {
            let mut f = std::fs::File::create(&file2_path).unwrap();
            writeln!(f, "struct PlainTextMatcher {{").unwrap();
            writeln!(f, "    needle: Vec<u8>,").unwrap();
            writeln!(f, "}}").unwrap();
        }

        // File 3: no matches
        let file3_path = dir.path().join("other.rs");
        {
            let mut f = std::fs::File::create(&file3_path).unwrap();
            writeln!(f, "fn main() {{").unwrap();
            writeln!(f, "    println!(\"hello\");").unwrap();
            writeln!(f, "}}").unwrap();
        }

        let meta1 = std::fs::metadata(&file1_path).unwrap();
        let meta2 = std::fs::metadata(&file2_path).unwrap();
        let meta3 = std::fs::metadata(&file3_path).unwrap();

        let files = vec![
            FileItem::new_raw(
                file1_path,
                "grep.rs".to_string(),
                "grep.rs".to_string(),
                meta1.len(),
                0,
                None,
                false,
            ),
            FileItem::new_raw(
                file2_path,
                "matcher.rs".to_string(),
                "matcher.rs".to_string(),
                meta2.len(),
                0,
                None,
                false,
            ),
            FileItem::new_raw(
                file3_path,
                "other.rs".to_string(),
                "other.rs".to_string(),
                meta3.len(),
                0,
                None,
                false,
            ),
        ];

        let options = super::GrepSearchOptions {
            max_file_size: 10 * 1024 * 1024,
            max_matches_per_file: 0,
            smart_case: true,
            file_offset: 0,
            page_limit: 100,
            mode: super::GrepMode::PlainText,
            time_budget_ms: 0,
            before_context: 0,
            after_context: 0,
            classify_definitions: false,
        };

        // Test with 3 patterns
        let result = super::multi_grep_search(
            &files,
            &["GrepMode", "GrepMatch", "PlainTextMatcher"],
            &[],
            &options,
        );

        // Should find matches from file1 (GrepMode, GrepMatch) and file2 (PlainTextMatcher)
        assert!(
            result.matches.len() >= 3,
            "Expected at least 3 matches, got {}",
            result.matches.len()
        );

        // Verify all 3 patterns are found
        let has_grep_mode = result
            .matches
            .iter()
            .any(|m| m.line_content.contains("GrepMode"));
        let has_grep_match = result
            .matches
            .iter()
            .any(|m| m.line_content.contains("GrepMatch"));
        let has_plain_text_matcher = result
            .matches
            .iter()
            .any(|m| m.line_content.contains("PlainTextMatcher"));

        assert!(has_grep_mode, "Should find GrepMode");
        assert!(has_grep_match, "Should find GrepMatch");
        assert!(has_plain_text_matcher, "Should find PlainTextMatcher");

        // File 3 should have no matches
        assert_eq!(result.files.len(), 2, "Should match exactly 2 files");

        // Test with single pattern
        let result2 = super::multi_grep_search(&files, &["PlainTextMatcher"], &[], &options);
        assert_eq!(
            result2.matches.len(),
            1,
            "Single pattern should find 1 match"
        );

        // Test with empty patterns
        let result3 = super::multi_grep_search(&files, &[], &[], &options);
        assert_eq!(
            result3.matches.len(),
            0,
            "Empty patterns should find nothing"
        );
    }
}