tastty-driver 0.1.0

//! Content search across the viewport and scrollback.
//!
//! [`Session::find`](crate::Session::find) walks the
//! [`Screen::logical_lines`](tastty::Screen::logical_lines) iterator
//! exposed by `tastty-core`, so wrap-handling stays in one place and
//! match positions are keyed by [`AbsolutePosition`] -- the same
//! coordinate space used by the selection API and
//! [`WaitMatch::position`](crate::WaitMatch).
//!
//! # Anchors
//!
//! When the search pattern is a regex, anchors operate on logical
//! lines: `^` matches the first column of a logical line, `$` matches
//! the last. Soft-wrapped physical rows are joined into a single
//! logical line before anchor matching, so a pattern like
//! `^TIMESTAMP` will match at the start of the wrapped logical line,
//! not at the start of every continuation row. The scan runs against
//! one logical line at a time; a `\n` literal in the pattern never
//! matches across logical-line boundaries.
//!
//! # Column semantics
//!
//! Match positions count cells, not bytes. A wide character (CJK,
//! emoji, ...) sits in one cell whose column is the lead-half cell's
//! column; the trailing continuation cell is skipped. Combining marks
//! attached to a base cell stay with the base cell's column. This is
//! the same column-counting convention as
//! [`Screen::cells`](tastty::Screen::cells) and the selection API.

mod options;
mod pattern;
mod result;
mod scan;

pub use options::{SearchDirection, SearchOptions};
pub use pattern::{DEFAULT_NFA_SIZE_LIMIT, RegexPattern, SearchPattern};
pub use result::{Capture, SearchError, SearchMatch};

use std::time::{Duration, Instant};

use regex::Regex;
use tastty::{LogicalLineOptions, Screen};

use scan::{build_span_haystack, scan_span};

/// Run the search against a borrowed [`Screen`]. Crate-internal entry
/// point used by [`Session::find`](crate::Session::find).
pub(crate) fn find(
    screen: &Screen,
    pattern: &SearchPattern,
    opts: SearchOptions,
) -> Result<Vec<SearchMatch>, SearchError> {
    let start = Instant::now();
    let line_opts = LogicalLineOptions {
        include_scrollback: opts.include_scrollback,
        join_wrapped: true,
        trim_trailing_blanks: true,
    };
    let spans: Vec<_> = screen.logical_lines(line_opts).collect();
    if spans.is_empty() {
        return Ok(Vec::new());
    }

    let regex = compile_for_search(pattern, &opts)?;
    let names: Vec<Option<String>> = regex
        .capture_names()
        .map(|n| n.map(str::to_owned))
        .collect();

    let mut matches: Vec<SearchMatch> = Vec::new();
    for span in &spans {
        let haystack = build_span_haystack(span);
        if let Some(cap) = opts.max_logical_line_bytes
            && haystack.text.len() > cap
        {
            check_deadline(opts.deadline, start)?;
            continue;
        }
        scan_span(&regex, &haystack, &names, &mut matches);
        check_deadline(opts.deadline, start)?;
    }

    if matches!(opts.direction, SearchDirection::Backward) {
        matches.reverse();
    }

    if let Some(pivot) = opts.start_from {
        matches.retain(|m| match opts.direction {
            SearchDirection::Forward => m.start >= pivot,
            SearchDirection::Backward => m.start <= pivot,
        });
    }

    if let Some(cap) = opts.max_results {
        matches.truncate(cap);
    }

    Ok(matches)
}

fn check_deadline(deadline: Option<Duration>, start: Instant) -> Result<(), SearchError> {
    let Some(budget) = deadline else {
        return Ok(());
    };
    let elapsed = start.elapsed();
    if elapsed >= budget {
        return Err(SearchError::DeadlineExceeded { budget, elapsed });
    }
    Ok(())
}

fn compile_for_search(pattern: &SearchPattern, opts: &SearchOptions) -> Result<Regex, SearchError> {
    match pattern {
        SearchPattern::Regex(r) => {
            if opts.nfa_size_limit.is_none() && opts.cache_capacity.is_none() {
                return Ok((*r.re).clone());
            }
            let mut b = regex::RegexBuilder::new(&r.src);
            b.multi_line(true);
            if let Some(n) = opts.nfa_size_limit {
                b.size_limit(n);
            }
            if let Some(n) = opts.cache_capacity {
                b.dfa_size_limit(n);
            }
            b.build().map_err(|err| SearchError::InvalidRegex {
                pattern: r.src.to_string(),
                source: err.into(),
            })
        }
        SearchPattern::Literal(needle) => {
            if needle.is_empty() {
                return Err(SearchError::EmptyPattern);
            }
            let escaped = regex::escape(needle);
            let mut b = regex::RegexBuilder::new(&escaped);
            b.multi_line(true)
                .case_insensitive(!opts.case_sensitive)
                .size_limit(opts.nfa_size_limit.unwrap_or(DEFAULT_NFA_SIZE_LIMIT));
            if let Some(n) = opts.cache_capacity {
                b.dfa_size_limit(n);
            }
            b.build().map_err(|err| SearchError::InvalidRegex {
                pattern: needle.clone(),
                source: err.into(),
            })
        }
    }
}

#[cfg(test)]
mod tests {
    use std::time::Duration;

    use super::*;
    use tastty::{AbsolutePosition, Parser, Position, TerminalSize};

    fn parse(rows: u16, cols: u16, scrollback: usize, input: &[u8]) -> Parser {
        let mut parser = Parser::new(TerminalSize { rows, cols }, scrollback);
        parser.process(input);
        parser
    }

    fn abs(parser: &Parser, row: u16, col: u16) -> AbsolutePosition {
        parser
            .screen()
            .visible_to_absolute(Position { row, col })
            .expect("viewport row/col maps to absolute position")
    }

    #[test]
    fn literal_match_in_viewport() {
        let parser = parse(4, 20, 0, b"hello world\r\nfoo bar baz");
        let pattern = SearchPattern::literal("world");
        let matches = find(parser.screen(), &pattern, SearchOptions::default())
            .expect("find succeeds for non-empty literal");

        assert_eq!(matches.len(), 1);
        let m = &matches[0];
        assert_eq!(m.start, abs(&parser, 0, 6));
        assert_eq!(m.end, abs(&parser, 0, 10));
        assert_eq!(m.text, "world");
        assert!(m.captures.is_empty());
    }

    #[test]
    fn regex_match_with_named_capture() {
        let parser = parse(4, 30, 0, b"err code 4242 at boot");
        let pattern = SearchPattern::regex(r"code (?P<num>\d+)").expect("compiles");
        let matches = find(parser.screen(), &pattern, SearchOptions::default()).expect("ok");

        assert_eq!(matches.len(), 1);
        let m = &matches[0];
        assert_eq!(m.text, "code 4242");
        assert_eq!(m.captures.len(), 1);
        let cap = &m.captures[0];
        assert_eq!(cap.name.as_deref(), Some("num"));
        assert_eq!(cap.index, 1);
        assert_eq!(cap.text, "4242");
        assert_eq!(cap.start, abs(&parser, 0, 9));
        assert_eq!(cap.end, abs(&parser, 0, 12));
    }

    #[test]
    fn match_in_scrollback_when_opted_in() {
        let mut parser = Parser::new(TerminalSize { rows: 3, cols: 16 }, 100);
        for line in 0..6u32 {
            parser.process(format!("line{line} abc\r\n").as_bytes());
        }
        assert!(parser.screen().scrollback_available() >= 3);

        let pattern = SearchPattern::literal("line1");

        let viewport_only = find(parser.screen(), &pattern, SearchOptions::default()).expect("ok");
        assert!(
            viewport_only.is_empty(),
            "line1 has scrolled out of the viewport"
        );

        let with_scrollback = find(
            parser.screen(),
            &pattern,
            SearchOptions::default().include_scrollback(),
        )
        .expect("ok");
        assert_eq!(with_scrollback.len(), 1);
        let m = &with_scrollback[0];
        assert_eq!(m.text, "line1");
        let oldest = parser.screen().scrollback_origin_row();
        assert_eq!(m.start.row, oldest + 1);
        assert_eq!(m.start.col, 0);
    }

    #[test]
    fn match_across_soft_wrap_boundary() {
        let parser = parse(4, 8, 0, b"abcdefghIJKL");
        let pattern = SearchPattern::literal("ghIJ");
        let matches = find(parser.screen(), &pattern, SearchOptions::default()).expect("ok");

        assert_eq!(matches.len(), 1);
        let m = &matches[0];
        assert_eq!(m.text, "ghIJ");
        assert_eq!(m.start, abs(&parser, 0, 6));
        assert_eq!(m.end, abs(&parser, 1, 1));
    }

    #[test]
    fn regex_newline_does_not_cross_logical_lines() {
        // The scan runs against one logical line at a time, so a
        // `\n` literal in the pattern never matches a logical-line
        // boundary. This is the documented per-line semantics --
        // soft-wrap boundaries are still joined into a single
        // logical line, so wrapped-line matches still work.
        let parser = parse(4, 20, 0, b"first line\r\nsecond line");
        let pattern = SearchPattern::regex(r"line\nsecond").expect("ok");
        let matches = find(parser.screen(), &pattern, SearchOptions::default()).expect("ok");
        assert!(matches.is_empty());
    }

    #[test]
    fn anchored_regex_honors_logical_line_boundaries() {
        let parser = parse(4, 20, 0, b"foo bar\r\nbar baz");
        let pattern = SearchPattern::regex(r"^bar").expect("ok");
        let matches = find(parser.screen(), &pattern, SearchOptions::default()).expect("ok");

        assert_eq!(
            matches.len(),
            1,
            "^bar must match only the bar at the start of line 2"
        );
        assert_eq!(matches[0].start, abs(&parser, 1, 0));
        assert_eq!(matches[0].text, "bar");
    }

    #[test]
    fn backward_search_returns_matches_in_reverse_reading_order() {
        let parser = parse(4, 30, 0, b"alpha alpha alpha");
        let pattern = SearchPattern::literal("alpha");
        let backward = find(
            parser.screen(),
            &pattern,
            SearchOptions::default().backward(),
        )
        .expect("ok");

        assert_eq!(backward.len(), 3);
        assert_eq!(backward[0].start.col, 12);
        assert_eq!(backward[1].start.col, 6);
        assert_eq!(backward[2].start.col, 0);
    }

    #[test]
    fn max_results_caps_the_returned_count() {
        let parser = parse(4, 30, 0, b"x x x x x x");
        let pattern = SearchPattern::literal("x");
        let matches = find(
            parser.screen(),
            &pattern,
            SearchOptions::default().max_results(2),
        )
        .expect("ok");

        assert_eq!(matches.len(), 2);
        assert_eq!(matches[0].start.col, 0);
        assert_eq!(matches[1].start.col, 2);
    }

    #[test]
    fn start_from_skips_earlier_matches_in_forward_walk() {
        let parser = parse(4, 30, 0, b"a a a a a");
        let pattern = SearchPattern::literal("a");
        let pivot = abs(&parser, 0, 4);
        let matches = find(
            parser.screen(),
            &pattern,
            SearchOptions::default().start_from(pivot),
        )
        .expect("ok");

        let cols: Vec<u16> = matches.iter().map(|m| m.start.col).collect();
        assert_eq!(cols, vec![4, 6, 8]);
    }

    #[test]
    fn case_insensitive_literal_matches_mixed_case_input() {
        let parser = parse(4, 30, 0, b"Error: FATAL warning ERROR");
        let pattern = SearchPattern::literal("error");

        let strict = find(parser.screen(), &pattern, SearchOptions::default()).expect("ok");
        assert!(
            strict.is_empty(),
            "case-sensitive default must not match Error/ERROR"
        );

        let folded = find(
            parser.screen(),
            &pattern,
            SearchOptions::default().case_insensitive(),
        )
        .expect("ok");
        let texts: Vec<&str> = folded.iter().map(|m| m.text.as_str()).collect();
        assert_eq!(texts, vec!["Error", "ERROR"]);
    }

    #[test]
    fn case_insensitive_flag_is_ignored_for_regex_patterns() {
        let parser = parse(4, 30, 0, b"Error and ERROR");
        let pattern = SearchPattern::regex("Error").expect("ok");
        let matches = find(
            parser.screen(),
            &pattern,
            SearchOptions::default().case_insensitive(),
        )
        .expect("ok");

        let texts: Vec<&str> = matches.iter().map(|m| m.text.as_str()).collect();
        assert_eq!(
            texts,
            vec!["Error"],
            "regex case is governed by (?i), not SearchOptions::case_sensitive"
        );
    }

    #[test]
    fn match_after_wide_character_keys_to_correct_cell_column() {
        let parser = parse(4, 20, 0, "漢字 hello".as_bytes());
        let pattern = SearchPattern::literal("hello");
        let matches = find(parser.screen(), &pattern, SearchOptions::default()).expect("ok");

        assert_eq!(matches.len(), 1);
        let m = &matches[0];
        assert_eq!(m.text, "hello");
        assert_eq!(m.start, abs(&parser, 0, 5));
        assert_eq!(m.end, abs(&parser, 0, 9));
    }

    #[test]
    fn empty_literal_pattern_is_rejected_at_find_time() {
        let parser = parse(4, 20, 0, b"hello");
        let pattern = SearchPattern::literal("");
        let err = find(parser.screen(), &pattern, SearchOptions::default())
            .expect_err("empty literal must error");
        assert!(matches!(err, SearchError::EmptyPattern));
    }

    #[test]
    fn empty_regex_pattern_is_rejected_at_construction() {
        let err = SearchPattern::regex("").expect_err("empty regex must error");
        assert!(matches!(err, SearchError::EmptyPattern));
    }

    #[test]
    fn invalid_regex_pattern_surfaces_compile_error() {
        let err = SearchPattern::regex("(unclosed").expect_err("malformed regex must error");
        match err {
            SearchError::InvalidRegex { pattern, source: _ } => {
                assert_eq!(pattern, "(unclosed");
            }
            other => panic!("expected InvalidRegex, got {other:?}"),
        }
    }

    #[test]
    fn find_without_deadline_runs_to_completion() {
        let parser = parse(4, 30, 0, b"alpha alpha alpha");
        let pattern = SearchPattern::literal("alpha");
        let matches =
            find(parser.screen(), &pattern, SearchOptions::default()).expect("default ok");
        assert_eq!(matches.len(), 3);
    }

    #[test]
    fn find_with_generous_deadline_returns_results() {
        let parser = parse(4, 30, 0, b"alpha alpha alpha");
        let pattern = SearchPattern::literal("alpha");
        let opts = SearchOptions::default().deadline(Duration::from_secs(1));
        let matches = find(parser.screen(), &pattern, opts).expect("generous deadline ok");
        assert_eq!(matches.len(), 3);
    }

    #[test]
    fn find_returns_deadline_exceeded_when_budget_zero() {
        // A zero budget cannot survive even a single per-line scan.
        // The check fires immediately after the first logical-line
        // scan completes with a non-negative elapsed time.
        let parser = parse(4, 30, 0, b"alpha alpha alpha");
        let pattern = SearchPattern::literal("alpha");
        let opts = SearchOptions::default().deadline(Duration::from_nanos(0));
        let err = find(parser.screen(), &pattern, opts).expect_err("zero-budget search must error");
        match err {
            SearchError::DeadlineExceeded { budget, elapsed: _ } => {
                assert_eq!(budget, Duration::from_nanos(0));
            }
            other => panic!("expected DeadlineExceeded, got {other:?}"),
        }
    }

    #[test]
    fn find_deadline_does_not_apply_when_no_matches() {
        // An empty screen yields no logical lines (the trailing-blank
        // trim strips the unwritten rows), so find short-circuits
        // before any per-line deadline check could fire. A zero
        // budget must therefore not error: there is no work to bound.
        let parser = parse(4, 20, 0, b"");
        let pattern = SearchPattern::literal("anything");
        let opts = SearchOptions::default().deadline(Duration::from_nanos(0));
        let matches = find(parser.screen(), &pattern, opts)
            .expect("zero deadline does not fire when there is no work");
        assert!(matches.is_empty());
    }

    #[test]
    fn find_per_line_deadline_short_circuits_after_line_boundary() {
        // With per-logical-line deadline checks, a tight budget
        // surfaces DeadlineExceeded after the first line scan
        // completes; the elapsed reading is the wall-clock time
        // between the find() entry and the first inter-line check.
        // A multi-line haystack is required: a single logical line
        // completes in one scan, so the deadline is checked once at
        // that scan's end. Here we feed dozens of lines so even a
        // very fast scanner must cross at least one line boundary.
        let mut parser = Parser::new(TerminalSize { rows: 4, cols: 80 }, 1000);
        for i in 0..50u32 {
            parser.process(format!("line{i} alpha\r\n").as_bytes());
        }
        let pattern = SearchPattern::regex("alpha").expect("ok");
        let opts = SearchOptions::default()
            .include_scrollback()
            .deadline(Duration::from_nanos(1));
        let err = find(parser.screen(), &pattern, opts).expect_err("budget too tight");
        match err {
            SearchError::DeadlineExceeded { budget, elapsed } => {
                assert_eq!(budget, Duration::from_nanos(1));
                assert!(elapsed >= budget);
            }
            other => panic!("expected DeadlineExceeded, got {other:?}"),
        }
    }

    #[test]
    fn find_empty_pattern_resyncs() {
        // Patterns that yield zero-width matches must not stall the
        // scanner. The resync state machine advances the search
        // cursor by one codepoint past every empty match, so the
        // total work is bounded by the haystack length even for
        // adversarial patterns.
        let parser = parse(4, 20, 0, b"abcdefgh");
        let pattern = SearchPattern::regex(r"(?:)?").expect("ok");
        let matches = find(parser.screen(), &pattern, SearchOptions::default())
            .expect("empty-yielding pattern must not infinite-loop");
        assert!(
            matches.is_empty(),
            "zero-width matches are skipped, but the loop must terminate"
        );
    }

    #[test]
    fn find_empty_pattern_with_optional_capture_resyncs() {
        // `(.*)?` matches the entire line non-empty plus a trailing
        // empty match. The empty match at end-of-haystack must
        // terminate the scan rather than re-yield indefinitely, and
        // the non-empty matches are recorded.
        let parser = parse(4, 30, 0, b"hello\r\nworld");
        let pattern = SearchPattern::regex(r"(.*)?").expect("ok");
        let matches = find(parser.screen(), &pattern, SearchOptions::default()).expect("ok");
        let texts: Vec<&str> = matches.iter().map(|m| m.text.as_str()).collect();
        assert_eq!(texts, vec!["hello", "world"]);
    }

    #[test]
    fn find_nfa_size_limit_rejects_compiled_too_big() {
        // \w is Unicode-aware and compiles to roughly 50 KB and fits
        // under the 256 KB construction-time ceiling. A 1 KB
        // SearchOptions override forces the per-find recompile path
        // and must surface InvalidRegex carrying CompiledTooBig.
        let parser = parse(4, 20, 0, b"hello");
        let pattern = SearchPattern::regex(r"\w+").expect("compiles under default limit");
        let opts = SearchOptions::default().nfa_size_limit(1024);
        let err = find(parser.screen(), &pattern, opts).expect_err("tight cap must reject");
        match err {
            SearchError::InvalidRegex { pattern: p, source } => {
                assert_eq!(p, r"\w+");
                let message = source.to_string();
                assert!(
                    message.contains("size limit"),
                    "expected compiled-size-limit diagnostic, got {message:?}",
                );
            }
            other => panic!("expected InvalidRegex, got {other:?}"),
        }
    }

    #[test]
    fn find_nfa_size_limit_override_can_lift_construction_default() {
        // The construction default (256 KB) already accommodates \w.
        // A higher SearchOptions override must not break previously-
        // working patterns; the recompile from source applies the
        // override in place of the default ceiling.
        let parser = parse(4, 30, 0, b"hello world");
        let pattern = SearchPattern::regex(r"\w+").expect("ok");
        let opts = SearchOptions::default().nfa_size_limit(4 * 1024 * 1024);
        let matches = find(parser.screen(), &pattern, opts).expect("ok");
        let texts: Vec<&str> = matches.iter().map(|m| m.text.as_str()).collect();
        assert_eq!(texts, vec!["hello", "world"]);
    }

    #[test]
    fn regex_with_limit_lifts_construction_cap() {
        // SearchPattern::regex applies the 256 KB default cap; a
        // hypothetical pattern that compiled larger would be rejected
        // there. SearchPattern::regex_with_limit lets a caller raise
        // the ceiling when the pattern source is trusted. We exercise
        // both directions: a trivial pattern always compiles under
        // any positive ceiling, and a tight 1 KB ceiling rejects \w.
        let _trivial =
            SearchPattern::regex_with_limit("alpha", 1024).expect("trivial pattern fits");

        let err = SearchPattern::regex_with_limit(r"\w+", 1024)
            .expect_err("\\w+ exceeds 1 KB compiled NFA");
        match err {
            SearchError::InvalidRegex { source, .. } => {
                let message = source.to_string();
                assert!(
                    message.contains("size limit"),
                    "expected compiled-size-limit diagnostic, got {message:?}",
                );
            }
            other => panic!("expected InvalidRegex, got {other:?}"),
        }
    }

    #[test]
    fn default_options_use_cached_regex_compile() {
        // SearchOptions::default carries no nfa/cache override, so
        // find() must use the cached Arc<Regex> built at
        // SearchPattern::regex construction time. We can't observe
        // the cache hit directly, but we can pin the contract by
        // exercising a search whose default-options run succeeds and
        // verifying the matched text round-trips correctly.
        let parser = parse(4, 30, 0, b"alpha beta alpha");
        let pattern = SearchPattern::regex(r"alpha|beta").expect("ok");
        let matches = find(parser.screen(), &pattern, SearchOptions::default()).expect("ok");
        let texts: Vec<&str> = matches.iter().map(|m| m.text.as_str()).collect();
        assert_eq!(texts, vec!["alpha", "beta", "alpha"]);
    }

    #[test]
    fn find_cache_capacity_does_not_break_normal_search() {
        // Setting cache_capacity is opt-in; a generous value must
        // not change observable matches for a normal pattern.
        let parser = parse(4, 30, 0, b"alpha alpha alpha");
        let pattern = SearchPattern::literal("alpha");
        let opts = SearchOptions::default().cache_capacity(1 << 20);
        let matches = find(parser.screen(), &pattern, opts).expect("ok");
        assert_eq!(matches.len(), 3);
    }

    #[test]
    fn find_max_logical_line_bytes_skips_oversize_lines() {
        // One short logical line containing the needle; one long
        // logical line also containing the needle. With
        // max_logical_line_bytes set just above the short line's
        // haystack length, the long line is skipped wholesale --
        // not truncated -- so we don't spuriously match across a
        // half-line boundary.
        let mut parser = Parser::new(TerminalSize { rows: 4, cols: 200 }, 100);
        parser.process(b"short FIND\r\n");
        let mut filler = vec![b'x'; 150];
        filler.extend_from_slice(b" FIND\r\n");
        parser.process(&filler);
        let pattern = SearchPattern::literal("FIND");
        let opts = SearchOptions::default()
            .include_scrollback()
            .max_logical_line_bytes(20);
        let matches = find(parser.screen(), &pattern, opts).expect("ok");
        assert_eq!(
            matches.len(),
            1,
            "only the short-line FIND should match; the long line is skipped"
        );
        assert_eq!(matches[0].text, "FIND");
    }

    #[test]
    fn find_max_logical_line_bytes_unset_scans_everything() {
        // Without the cap, both the short and the long line match.
        // Verifies the skip is opt-in.
        let mut parser = Parser::new(TerminalSize { rows: 4, cols: 200 }, 100);
        parser.process(b"short FIND\r\n");
        let mut filler = vec![b'x'; 150];
        filler.extend_from_slice(b" FIND\r\n");
        parser.process(&filler);
        let pattern = SearchPattern::literal("FIND");
        let opts = SearchOptions::default().include_scrollback();
        let matches = find(parser.screen(), &pattern, opts).expect("ok");
        assert_eq!(matches.len(), 2);
    }

    #[test]
    fn pathological_input_does_not_panic() {
        let mut parser = Parser::new(TerminalSize { rows: 4, cols: 8 }, 64);
        for _ in 0..256 {
            parser.process(b"\x1b[31mfoo\x1b[0m bar\r\n");
        }
        let pattern = SearchPattern::regex(r"(foo|bar)+").expect("ok");
        let result = find(
            parser.screen(),
            &pattern,
            SearchOptions::default().include_scrollback().max_results(8),
        );
        let matches = result.expect("ok");
        assert!(matches.len() <= 8);
    }
}