//! Approximate ("fuzzy") string matching (port of `src/ui/fuzzy.ts`).
//!
//! A query matches when every one of its characters can be found in the target
//! in relative order (a subsequence match). Each match gets an `f64` score;
//! smaller is a tighter, more relevant match.
//!
//! Parity-critical constants (`DEFAULT_FUZZY_CONFIG`) and the
//! `WORD_BOUNDARY = /[\s\-_./:\\@~]/` set are load-bearing. Scores must be
//! `f64` because of `late_match_penalty = 0.15`.

/// Result of a single fuzzy comparison (port of TS `FuzzyMatch`).
#[derive(Debug, Clone, Copy, PartialEq)]
pub struct FuzzyMatch {
    pub matches: bool,
    pub score: f64,
}

/// Tunable scoring weights (port of TS `FuzzyScoringConfig`).
///
/// The defaults are the indus-tuned constants and must match exactly:
/// `gap_penalty: 3, consecutive_reward: 4, word_boundary_reward: 12,
/// late_match_penalty: 0.15, swapped_token_penalty: 6`.
#[derive(Debug, Clone, Copy, PartialEq)]
pub struct FuzzyScoringConfig {
    pub gap_penalty: f64,
    pub consecutive_reward: f64,
    pub word_boundary_reward: f64,
    pub late_match_penalty: f64,
    pub swapped_token_penalty: f64,
}

impl Default for FuzzyScoringConfig {
    fn default() -> Self {
        // Mirror DEFAULT_FUZZY_CONFIG exactly.
        Self {
            gap_penalty: 3.0,
            consecutive_reward: 4.0,
            word_boundary_reward: 12.0,
            late_match_penalty: 0.15,
            swapped_token_penalty: 6.0,
        }
    }
}

/// The indus-tuned scoring constants, exposed as a `const` mirror of the TS
/// `DEFAULT_FUZZY_CONFIG` object for tests and external callers.
pub const DEFAULT_FUZZY_CONFIG: FuzzyScoringConfig = FuzzyScoringConfig {
    gap_penalty: 3.0,
    consecutive_reward: 4.0,
    word_boundary_reward: 12.0,
    late_match_penalty: 0.15,
    swapped_token_penalty: 6.0,
};

/// Characters that, when they precede a matched character, mark the start of a
/// fresh "word" within the target string. Mirrors TS `WORD_BOUNDARY`:
/// `/[\s\-_./:\\@~]/`. The `\s` class here matches the JS regex `\s` semantics
/// closely enough for the strings this tool ranks — we treat any Unicode
/// whitespace as a boundary plus the explicit punctuation set.
fn is_word_boundary(ch: char) -> bool {
    ch.is_whitespace() || matches!(ch, '-' | '_' | '.' | '/' | ':' | '\\' | '@' | '~')
}

/// Locates each query character inside the target (in order) and reports the
/// column where it landed. Returns `None` the moment a query character cannot
/// be placed, which signals a non-match. Port of TS `locateMatchColumns`.
///
/// `query_lower` / `text_lower` are pre-lowercased char vectors so that column
/// indices line up with character positions exactly as the TS code uses string
/// indices.
fn locate_match_columns(query_lower: &[char], text_lower: &[char]) -> Option<Vec<usize>> {
    let mut columns: Vec<usize> = Vec::with_capacity(query_lower.len());
    let mut cursor: usize = 0;
    for &wanted in query_lower {
        let mut found: Option<usize> = None;
        while cursor < text_lower.len() {
            let here = cursor;
            cursor += 1;
            if text_lower[here] == wanted {
                found = Some(here);
                break;
            }
        }
        match found {
            Some(idx) => columns.push(idx),
            None => return None,
        }
    }
    Some(columns)
}

/// Turns an ordered list of matched columns into a relevance score. The reward
/// and penalty terms are accumulated per column relative to the previous hit.
/// Port of TS `scoreMatchColumns`.
fn score_match_columns(text_lower: &[char], columns: &[usize], config: &FuzzyScoringConfig) -> f64 {
    let mut total: f64 = 0.0;
    // TS uses `previous = -1`; model it as a signed cursor.
    let mut previous: i64 = -1;
    let mut streak: f64 = 0.0;

    for &column in columns {
        let col_i = column as i64;
        let adjacent = previous == col_i - 1;
        if adjacent {
            streak += 1.0;
            total -= streak * config.consecutive_reward;
        } else {
            streak = 0.0;
            if previous >= 0 {
                // (column - previous - 1) gaps between the two hits.
                total += ((col_i - previous - 1) as f64) * config.gap_penalty;
            }
        }

        let starts_word = column == 0 || is_word_boundary(text_lower[column - 1]);
        if starts_word {
            total -= config.word_boundary_reward;
        }

        total += (column as f64) * config.late_match_penalty;
        previous = col_i;
    }

    total
}

/// Sequential subsequence scan (port of TS `SequentialScanEngine.match`),
/// operating on pre-lowercased char slices.
fn sequential_match(
    query_lower: &[char],
    text_lower: &[char],
    config: &FuzzyScoringConfig,
) -> FuzzyMatch {
    if query_lower.is_empty() {
        return FuzzyMatch {
            matches: true,
            score: 0.0,
        };
    }
    if query_lower.len() > text_lower.len() {
        return FuzzyMatch {
            matches: false,
            score: 0.0,
        };
    }

    match locate_match_columns(query_lower, text_lower) {
        None => FuzzyMatch {
            matches: false,
            score: 0.0,
        },
        Some(columns) => FuzzyMatch {
            matches: true,
            score: score_match_columns(text_lower, &columns, config),
        },
    }
}

/// Convenience over `sequential_match` that lowercases `&str` inputs, mirroring
/// TS `SequentialFuzzyStrategy.match` (`query.toLowerCase()` / `text.toLowerCase()`).
fn match_with_config(query: &str, text: &str, config: &FuzzyScoringConfig) -> FuzzyMatch {
    let query_lower: Vec<char> = query.to_lowercase().chars().collect();
    let text_lower: Vec<char> = text.to_lowercase().chars().collect();
    sequential_match(&query_lower, &text_lower, config)
}

/// When a query is a single run of letters glued to a single run of digits (or
/// vice-versa), produce the variant with the two runs swapped. Anything else
/// yields `None`, meaning "no alternative to try". Port of TS
/// `FuzzyQuerySwapResolver.toSwappedQuery` (`^[a-z]+[0-9]+$` / `^[0-9]+[a-z]+$`
/// on the lowercased query).
fn to_swapped_query(query: &str) -> Option<String> {
    let normalized = query.to_lowercase();
    let chars: Vec<char> = normalized.chars().collect();
    if chars.is_empty() {
        return None;
    }

    // Split into a single leading run and a single trailing run, requiring the
    // first run to be one class and the second the other (a..z vs 0..9), with
    // no other characters present.
    let is_letter = |c: char| c.is_ascii_lowercase();
    let is_digit = |c: char| c.is_ascii_digit();

    // letters-then-digits
    if try_two_runs(&chars, &is_letter, &is_digit) {
        let split = chars.iter().take_while(|&&c| is_letter(c)).count();
        let letters: String = chars[..split].iter().collect();
        let digits: String = chars[split..].iter().collect();
        return Some(format!("{digits}{letters}"));
    }

    // digits-then-letters
    if try_two_runs(&chars, &is_digit, &is_letter) {
        let split = chars.iter().take_while(|&&c| is_digit(c)).count();
        let digits: String = chars[..split].iter().collect();
        let letters: String = chars[split..].iter().collect();
        return Some(format!("{letters}{digits}"));
    }

    None
}

/// Returns true when `chars` is exactly one non-empty run satisfying `first`
/// followed by exactly one non-empty run satisfying `second`, with nothing
/// else. Equivalent to the anchored `^(first+)(second+)$` regexes in TS.
fn try_two_runs(
    chars: &[char],
    first: &dyn Fn(char) -> bool,
    second: &dyn Fn(char) -> bool,
) -> bool {
    let n = chars.len();
    let head = chars.iter().take_while(|&&c| first(c)).count();
    if head == 0 || head == n {
        return false;
    }
    chars[head..].iter().all(|&c| second(c))
}

/// Split a query into whitespace-separated tokens (port of TS
/// `FuzzyTokenMatcher.tokenize`). An all-whitespace or empty query yields `[]`.
fn tokenize(query: &str) -> Vec<&str> {
    let trimmed = query.trim();
    if trimmed.is_empty() {
        return Vec::new();
    }
    trimmed
        .split_whitespace()
        .filter(|p| !p.is_empty())
        .collect()
}

/// Compute a single fuzzy match (port of TS `fuzzyMatch`).
///
/// Tries a direct subsequence match first; on failure, retries with the
/// digit/letter token-swap variant (`^[a-z]+[0-9]+$` / `^[0-9]+[a-z]+$`),
/// adding `swapped_token_penalty` to the score.
pub fn fuzzy_match(query: &str, text: &str) -> FuzzyMatch {
    let config = DEFAULT_FUZZY_CONFIG;

    let direct = match_with_config(query, text, &config);
    if direct.matches {
        return direct;
    }

    let alternative = match to_swapped_query(query) {
        Some(alt) => alt,
        None => return direct,
    };

    let swapped = match_with_config(&alternative, text, &config);
    if !swapped.matches {
        return direct;
    }

    FuzzyMatch {
        matches: true,
        score: swapped.score + config.swapped_token_penalty,
    }
}

/// Keep only items whose text matches the query, best matches first
/// (port of TS `fuzzyFilter`). The query may contain several whitespace-
/// separated tokens; an item is retained only when it matches **all** of them,
/// with per-token scores summed and a stable ascending sort.
pub fn fuzzy_filter<T>(items: Vec<T>, query: &str, get_text: impl Fn(&T) -> String) -> Vec<T> {
    let tokens = tokenize(query);
    if tokens.is_empty() {
        return items;
    }

    // For each item, sum the per-token scores; a missing token drops the item.
    let mut ranked: Vec<(T, f64)> = Vec::new();
    for item in items {
        let text = get_text(&item);
        let mut aggregate: f64 = 0.0;
        let mut qualifies = true;
        for token in &tokens {
            let outcome = fuzzy_match(token, &text);
            if !outcome.matches {
                qualifies = false;
                break;
            }
            aggregate += outcome.score;
        }
        if qualifies {
            ranked.push((item, aggregate));
        }
    }

    // Stable ascending sort by rank (TS `Array.prototype.sort` is stable, and
    // Rust's `sort_by` is stable, so equal-rank items keep input order).
    ranked.sort_by(|a, b| a.1.partial_cmp(&b.1).unwrap_or(std::cmp::Ordering::Equal));
    ranked.into_iter().map(|(item, _)| item).collect()
}

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

    // Floating-point comparison helper mirroring pytest.approx's default
    // tolerance for the small magnitudes used here.
    fn approx(a: f64, b: f64) {
        assert!(
            (a - b).abs() < 1e-9,
            "expected {b}, got {a} (diff {})",
            (a - b).abs()
        );
    }

    // ---------------------------------------------------------------------
    // Config constants (mirror test_config_constants_match_ts).
    // ---------------------------------------------------------------------

    #[test]
    fn config_constants_match_ts() {
        assert_eq!(DEFAULT_FUZZY_CONFIG.gap_penalty, 3.0);
        assert_eq!(DEFAULT_FUZZY_CONFIG.consecutive_reward, 4.0);
        assert_eq!(DEFAULT_FUZZY_CONFIG.word_boundary_reward, 12.0);
        assert_eq!(DEFAULT_FUZZY_CONFIG.late_match_penalty, 0.15);
        assert_eq!(DEFAULT_FUZZY_CONFIG.swapped_token_penalty, 6.0);
        // Default impl agrees with the const mirror.
        assert_eq!(FuzzyScoringConfig::default(), DEFAULT_FUZZY_CONFIG);
    }

    // ---------------------------------------------------------------------
    // Match / no-match semantics.
    // ---------------------------------------------------------------------

    #[test]
    fn empty_query_matches_everything_with_zero_score() {
        assert_eq!(
            fuzzy_match("", "anything"),
            FuzzyMatch {
                matches: true,
                score: 0.0
            }
        );
        assert_eq!(
            fuzzy_match("", ""),
            FuzzyMatch {
                matches: true,
                score: 0.0
            }
        );
    }

    #[test]
    fn query_longer_than_text_never_matches() {
        assert_eq!(
            fuzzy_match("abcd", "abc"),
            FuzzyMatch {
                matches: false,
                score: 0.0
            }
        );
    }

    #[test]
    fn subsequence_must_preserve_order() {
        assert!(fuzzy_match("ac", "abc").matches);
        assert!(!fuzzy_match("ca", "abc").matches);
        assert!(!fuzzy_match("xyz", "abc").matches);
    }

    #[test]
    fn case_insensitive() {
        let lower = fuzzy_match("foo", "barfoo");
        let upper = fuzzy_match("FOO", "BarFoo");
        assert!(upper.matches);
        approx(upper.score, lower.score);
    }

    // ---------------------------------------------------------------------
    // Hand-computed score fixtures (TS scorer). Golden values taken from the
    // Python port's hand-derived fixtures.
    // ---------------------------------------------------------------------

    #[test]
    fn score_fixtures() {
        let cases: &[(&str, &str, f64)] = &[
            ("a", "abc", -16.0),
            ("abc", "abc", -35.55),
            ("oo", "foo", -3.55),
            ("foo", "barfoo", -10.2),
            ("foo", "f_o_o", -33.1),
        ];
        for &(query, text, score) in cases {
            let result = fuzzy_match(query, text);
            assert!(result.matches, "{query:?} in {text:?} should match");
            approx(result.score, score);
        }
    }

    #[test]
    fn first_column_adjacency_quirk() {
        // previous starts at -1, so a hit at column 0 is treated as "adjacent"
        // and earns the streak reward on top of the boundary reward.
        approx(fuzzy_match("a", "a").score, -16.0);
        // A hit at column 1 gets neither: late penalty only.
        approx(fuzzy_match("b", "ab").score, 0.15);
    }

    #[test]
    fn word_boundary_characters() {
        for sep in ['-', '_', '.', '/', ':', '\\', '@', '~', ' '] {
            let text = format!("a{sep}x");
            // x at column 2 preceded by a boundary char: -12 + 2*0.15 = -11.7
            approx(fuzzy_match("x", &text).score, -11.7);
        }
    }

    #[test]
    fn non_boundary_predecessor_gets_no_reward() {
        // x at column 2 preceded by a letter: just the late penalty.
        approx(fuzzy_match("x", "abx").score, 0.3);
    }

    #[test]
    fn tight_match_beats_scattered_match() {
        let tight = fuzzy_match("foo", "foo").score;
        let boundary = fuzzy_match("foo", "f_o_o").score;
        let scattered = fuzzy_match("foo", "barfoo").score;
        assert!(
            tight < boundary,
            "tight {tight} should beat boundary {boundary}"
        );
        assert!(
            boundary < scattered,
            "boundary {boundary} should beat scattered {scattered}"
        );
    }

    // ---------------------------------------------------------------------
    // Digit/letter swap fallback.
    // ---------------------------------------------------------------------

    #[test]
    fn swapped_query_matches_with_penalty() {
        // "foo12" fails on "12foo" directly; the swapped "12foo" matches with
        // contiguous columns 0..4 = -70.5, plus the +6 swap penalty = -64.5.
        let result = fuzzy_match("foo12", "12foo");
        assert!(result.matches);
        approx(result.score, -64.5);
        // The mirror direction uses the digits+letters regex.
        let result = fuzzy_match("12foo", "foo12");
        assert!(result.matches);
        approx(result.score, -64.5);
    }

    #[test]
    fn swap_penalty_makes_swapped_worse_than_direct() {
        let direct = fuzzy_match("12foo", "12foo");
        let swapped = fuzzy_match("foo12", "12foo");
        approx(swapped.score, direct.score + 6.0);
    }

    #[test]
    fn no_swap_for_interleaved_queries() {
        // "a1b" is neither letters+digits nor digits+letters: no fallback.
        assert!(!fuzzy_match("a1b", "1ab").matches);
        assert!(!fuzzy_match("f1o2", "12fo").matches);
    }

    #[test]
    fn direct_match_wins_over_swap() {
        // When the direct query already matches, the swap is never consulted.
        let result = fuzzy_match("foo12", "foo12bar");
        assert!(result.matches);
        // Direct columns 0..4 contiguous from a word start: deterministic.
        approx(result.score, fuzzy_match("foo12", "foo12bar").score);
    }

    // ---------------------------------------------------------------------
    // fuzzy_filter — ranking and multi-token AND semantics.
    // ---------------------------------------------------------------------

    #[test]
    fn filter_orders_by_ascending_score() {
        let items = vec!["barfoo", "f_o_o", "foo", "xyz"];
        // Scores: foo -35.55 < f_o_o -33.1 < barfoo -10.2; xyz drops out.
        let out = fuzzy_filter(items, "foo", |s| s.to_string());
        assert_eq!(out, vec!["foo", "f_o_o", "barfoo"]);
    }

    #[test]
    fn filter_empty_or_whitespace_query_returns_items_unchanged() {
        let items = vec!["b", "a", "c"];
        assert_eq!(
            fuzzy_filter(items.clone(), "", |s| s.to_string()),
            vec!["b", "a", "c"]
        );
        assert_eq!(
            fuzzy_filter(items, "   ", |s| s.to_string()),
            vec!["b", "a", "c"]
        );
    }

    #[test]
    fn filter_requires_every_token() {
        let items = vec!["foo bar", "bar baz", "foo baz"];
        let out = fuzzy_filter(items, "foo baz", |s| s.to_string());
        assert_eq!(out, vec!["foo baz"]);
    }

    #[test]
    fn filter_multi_token_aggregate_ranking() {
        // Hand-computed aggregates from the Python port:
        //   "baz foo":     foo @4,5,6 = -21.75; baz @0,1,2 = -35.55 -> -57.3
        //   "foo bar baz": foo @0,1,2 = -35.55; baz @4,5,10 = -1.15 -> -36.7
        let items = vec!["foo bar baz", "baz foo"];
        let out = fuzzy_filter(items, "foo baz", |s| s.to_string());
        assert_eq!(out, vec!["baz foo", "foo bar baz"]);
    }

    #[test]
    fn filter_with_accessor_objects() {
        #[derive(Clone, PartialEq, Debug)]
        struct Named {
            name: &'static str,
        }
        let items = vec![
            Named {
                name: "session-restore",
            },
            Named {
                name: "restore-session",
            },
            Named { name: "unrelated" },
        ];
        let out = fuzzy_filter(items, "restore", |d| d.name.to_string());
        // "restore-session" starts at column 0 (boundary + contiguous run) so
        // it outranks the mid-string hit in "session-restore".
        let names: Vec<&str> = out.iter().map(|d| d.name).collect();
        assert_eq!(names, vec!["restore-session", "session-restore"]);
    }

    #[test]
    fn filter_token_with_swap_fallback() {
        let items = vec!["12foo", "nope"];
        let out = fuzzy_filter(items, "foo12", |s| s.to_string());
        assert_eq!(out, vec!["12foo"]);
    }

    #[test]
    fn filter_preserves_input_on_no_tokens_and_drops_all_on_no_match() {
        let items = vec!["alpha", "beta"];
        let out = fuzzy_filter(items, "zzz", |s| s.to_string());
        assert!(out.is_empty());
    }

    // ---------------------------------------------------------------------
    // Extra unit coverage for the helper used by the swap fallback.
    // ---------------------------------------------------------------------

    #[test]
    fn to_swapped_query_variants() {
        assert_eq!(to_swapped_query("foo12").as_deref(), Some("12foo"));
        assert_eq!(to_swapped_query("12foo").as_deref(), Some("foo12"));
        // Mixed-case is lowercased first.
        assert_eq!(to_swapped_query("Foo12").as_deref(), Some("12foo"));
        // No swap for interleaved or single-class queries.
        assert_eq!(to_swapped_query("a1b"), None);
        assert_eq!(to_swapped_query("abc"), None);
        assert_eq!(to_swapped_query("123"), None);
        assert_eq!(to_swapped_query(""), None);
    }
}
