Skip to content

The ultimate harness for coding agents and beyond. All your agents. All your machines. One command center. Start with code, then follow your curiosity and build across disciplines: CAD, circuits, robots, games and music.

38.5 KB
Raw Blame
//! fzf's matcher, ported from fzf 0.67.0 (src/algo/algo.go, src/pattern.go, src/result.go): the
//! extended-search syntax, FuzzyMatchV2's scores and the characters it lights, the exact, prefix,
//! suffix and equal matches, and the tiebreak — so a list ranks and lights as fzf ranks and lights
//! the same lines.

const SCORE_MATCH: i32 = 16;
const SCORE_GAP_START: i32 = -3;
const SCORE_GAP_EXTENSION: i32 = -1;
const BONUS_BOUNDARY: i32 = SCORE_MATCH / 2;
const BONUS_NON_WORD: i32 = SCORE_MATCH / 2;
const BONUS_CAMEL123: i32 = BONUS_BOUNDARY + SCORE_GAP_EXTENSION;
const BONUS_CONSECUTIVE: i32 = -(SCORE_GAP_START + SCORE_GAP_EXTENSION);
const BONUS_FIRST_CHAR_MULTIPLIER: i32 = 2;
/// --scheme (algo.Init): default, path or history — 0, 1, 2.
static SCHEME: std::sync::atomic::AtomicU8 = std::sync::atomic::AtomicU8::new(0);

/// The scoring scheme --scheme names (an unknown one leaves the default).
pub fn set_scheme(name: &str) {
    let n = match name { "path" => 1, "history" => 2, _ => 0 };
    SCHEME.store(n, std::sync::atomic::Ordering::Relaxed);
}
fn scheme() -> u8 { SCHEME.load(std::sync::atomic::Ordering::Relaxed) }

/// bonusBoundaryWhite: after whitespace (the default scheme's +2, path's and history's +0).
fn bonus_boundary_white() -> i32 { if scheme() == 0 { BONUS_BOUNDARY + 2 } else { BONUS_BOUNDARY } }
/// bonusBoundaryDelimiter: after a delimiter (+1; history's +0).
fn bonus_boundary_delimiter() -> i32 { if scheme() == 2 { BONUS_BOUNDARY } else { BONUS_BOUNDARY + 1 } }
/// initialCharClass: before the first character (a delimiter under the path scheme).
fn initial_class() -> Class { if scheme() == 1 { Class::Delimiter } else { Class::White } }

#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Debug)]
enum Class { White, NonWord, Delimiter, Lower, Upper, Letter, Number }

fn class_of(c: char) -> Class {
    if c.is_ascii() {
        return match c {
            'a'..='z' => Class::Lower,
            'A'..='Z' => Class::Upper,
            '0'..='9' => Class::Number,
            ' ' | '\t' | '\n' | '\x0b' | '\x0c' | '\r' => Class::White,
            '/' => Class::Delimiter,
            // (The path scheme's delimiters are the path separator alone.)
            ',' | ':' | ';' | '|' if scheme() != 1 => Class::Delimiter,
            _ => Class::NonWord,
        };
    }
    if c.is_lowercase() { Class::Lower }
    else if c.is_uppercase() { Class::Upper }
    else if c.is_numeric() { Class::Number }
    else if c.is_alphabetic() { Class::Letter }
    else if c.is_whitespace() { Class::White }
    else { Class::NonWord }
}

fn bonus_for(prev: Class, class: Class) -> i32 {
    if class > Class::NonWord {
        match prev {
            Class::White => return bonus_boundary_white(),
            Class::Delimiter => return bonus_boundary_delimiter(),
            Class::NonWord => return BONUS_BOUNDARY,
            _ => {}
        }
    }
    if (prev == Class::Lower && class == Class::Upper) || (prev != Class::Number && class == Class::Number) { return BONUS_CAMEL123 }
    match class {
        Class::NonWord | Class::Delimiter => BONUS_NON_WORD,
        Class::White => bonus_boundary_white(),
        _ => 0,
    }
}

fn bonus_at(text: &[char], idx: usize) -> i32 {
    if idx == 0 { return bonus_boundary_white() }
    bonus_for(class_of(text[idx - 1]), class_of(text[idx]))
}

/// Go's unicode.To(LowerCase, c): one character.
fn lower(c: char) -> char { if c.is_ascii() { c.to_ascii_lowercase() } else { c.to_lowercase().next().unwrap_or(c) } }

/// A character as a term compares it: folded when the term ignores case, normalized when it does.
fn fold(c: char, case_sensitive: bool, normalize: bool) -> char {
    let c = if case_sensitive { c } else if c.is_ascii_uppercase() { c.to_ascii_lowercase() } else if !c.is_ascii() { lower(c) } else { c };
    if normalize { normalize_char(c) } else { c }
}

/// FuzzyMatchV2: the best-scoring alignment of `pattern` in `text` — (start, end, score, the
/// matched positions) — or None. Not `forward` (--tiebreak=end or pathname): of equal scores the
/// last one wins, as fzf searches from the end.
fn fuzzy_v2(case_sensitive: bool, normalize: bool, forward: bool, text: &[char], pattern: &[char]) -> Option<(usize, usize, i32, Vec<usize>)> {
    let m = pattern.len();
    if m == 0 { return Some((0, 0, 0, Vec::new())) }
    let n = text.len();
    if m > n { return None }
    // Phase 2: each character's bonus, the first place of each pattern character, row 0.
    let mut t: Vec<char> = Vec::with_capacity(n);
    let (mut h0, mut c0, mut b) = (vec![0i32; n], vec![0i32; n], vec![0i32; n]);
    let mut f = vec![0usize; m];
    let (mut max_score, mut max_pos) = (0i32, 0usize);
    let (mut pidx, mut last_idx) = (0usize, 0usize);
    let (pchar0, mut pchar) = (pattern[0], pattern[0]);
    let (mut prev_h0, mut prev_class, mut in_gap) = (0i32, initial_class(), false);
    for off in 0..n {
        let mut ch = text[off];
        let class = class_of(ch);
        if ch.is_ascii() {
            if !case_sensitive && class == Class::Upper { ch = ch.to_ascii_lowercase() }
        } else {
            if !case_sensitive && class == Class::Upper { ch = lower(ch) }
            if normalize { ch = normalize_char(ch) }
        }
        t.push(ch);
        let bonus = bonus_for(prev_class, class);
        b[off] = bonus;
        prev_class = class;
        if ch == pchar {
            if pidx < m { f[pidx] = off; pidx += 1; pchar = pattern[pidx.min(m - 1)] }
            last_idx = off;
        }
        if ch == pchar0 {
            let score = SCORE_MATCH + bonus * BONUS_FIRST_CHAR_MULTIPLIER;
            h0[off] = score;
            c0[off] = 1;
            if m == 1 && (forward && score > max_score || !forward && score >= max_score) {
                max_score = score;
                max_pos = off;
                if forward && bonus >= BONUS_BOUNDARY { break }
            }
            in_gap = false;
        } else {
            h0[off] = (prev_h0 + if in_gap { SCORE_GAP_EXTENSION } else { SCORE_GAP_START }).max(0);
            c0[off] = 0;
            in_gap = true;
        }
        prev_h0 = h0[off];
    }
    if pidx != m { return None }
    if m == 1 { return Some((max_pos, max_pos + 1, max_score, vec![max_pos])) }
    // Phase 3: the score matrix, rows 1.., from each row's first possible column.
    let f0 = f[0];
    let width = last_idx - f0 + 1;
    let mut h = vec![0i32; width * m];
    h[..width].copy_from_slice(&h0[f0..=last_idx]);
    let mut c = vec![0i32; width * m];
    c[..width].copy_from_slice(&c0[f0..=last_idx]);
    for (off, &fi) in f[1..].iter().enumerate() {
        let pchar = pattern[off + 1];
        let pidx = off + 1;
        let row = pidx * width;
        let mut in_gap = false;
        h[row + fi - f0 - 1] = 0;
        for col in fi..=last_idx {
            let j = col - f0;
            let s2 = h[row + j - 1] + if in_gap { SCORE_GAP_EXTENSION } else { SCORE_GAP_START };
            let (mut s1, mut consecutive) = (0i32, 0i32);
            if pchar == t[col] {
                s1 = h[row - width + j - 1] + SCORE_MATCH;
                let mut bb = b[col];
                consecutive = c[row - width + j - 1] + 1;
                if consecutive > 1 {
                    let fb = b[col + 1 - consecutive as usize];
                    if bb >= BONUS_BOUNDARY && bb > fb { consecutive = 1 } else { bb = bb.max(BONUS_CONSECUTIVE.max(fb)) }
                }
                if s1 + bb < s2 { s1 += b[col]; consecutive = 0 } else { s1 += bb }
            }
            c[row + j] = consecutive;
            in_gap = s1 < s2;
            let score = s1.max(s2).max(0);
            if pidx == m - 1 && (forward && score > max_score || !forward && score >= max_score) { max_score = score; max_pos = col }
            h[row + j] = score;
        }
    }
    // Phase 4: back from the best end, the positions.
    let mut pos = Vec::with_capacity(m);
    let (mut i, mut j) = (m - 1, max_pos);
    let mut prefer_match = true;
    loop {
        let ii = i * width;
        let j0 = j - f0;
        let s = h[ii + j0];
        let s1 = if i > 0 && j >= f[i] { h[ii - width + j0 - 1] } else { 0 };
        let s2 = if j > f[i] { h[ii + j0 - 1] } else { 0 };
        if s > s1 && (s > s2 || (s == s2 && prefer_match)) {
            pos.push(j);
            if i == 0 { break }
            i -= 1;
        }
        prefer_match = c[ii + j0] > 1 || (ii + width + j0 + 1 < c.len() && c[ii + width + j0 + 1] > 0);
        if j == 0 || j <= f0 { break }
        j -= 1;
    }
    Some((j, max_pos + 1, max_score, pos))
}

/// FuzzyMatchV1: where the pattern's characters first come in order (from the start, or from the
/// end when not [forward]), narrowed back from that end to the last start that still holds them
/// all, scored as calculateScore scores a fixed alignment.
fn fuzzy_v1(case_sensitive: bool, normalize: bool, forward: bool, text: &[char], pattern: &[char]) -> Option<(usize, usize, i32, Vec<usize>)> {
    let (m, n) = (pattern.len(), text.len());
    if m == 0 { return Some((0, 0, 0, Vec::new())) }
    let at = |i: usize, len: usize| if forward { i } else { len - 1 - i };
    let (mut pidx, mut sidx, mut eidx) = (0usize, None, None);
    for index in 0..n {
        if fold(text[at(index, n)], case_sensitive, normalize) == pattern[at(pidx, m)] {
            if sidx.is_none() { sidx = Some(index) }
            pidx += 1;
            if pidx == m { eidx = Some(index + 1); break }
        }
    }
    let (mut s, e) = (sidx?, eidx?);
    let mut p = m as i64 - 1;
    let mut index = e as i64 - 1;
    while index >= s as i64 {
        if fold(text[at(index as usize, n)], case_sensitive, normalize) == pattern[at(p as usize, m)] {
            p -= 1;
            if p < 0 { s = index as usize; break }
        }
        index -= 1;
    }
    let (s, e) = if forward { (s, e) } else { (n - e, n - s) };
    let score = calculate_score(case_sensitive, normalize, text, pattern, s, e);
    let mut pos = Vec::with_capacity(m);
    for (i, &c) in text.iter().enumerate().take(e).skip(s) { if pos.len() < m && fold(c, case_sensitive, normalize) == pattern[pos.len()] { pos.push(i) } }
    Some((s, e, score, pos))
}

/// fzf's calculateScore: a fixed alignment scored as V2 scores it.
fn calculate_score(case_sensitive: bool, normalize: bool, text: &[char], pattern: &[char], sidx: usize, eidx: usize) -> i32 {
    let (mut pidx, mut score, mut in_gap, mut consecutive, mut first_bonus) = (0usize, 0i32, false, 0i32, 0i32);
    let mut prev_class = if sidx > 0 { class_of(text[sidx - 1]) } else { initial_class() };
    for &raw in &text[sidx..eidx] {
        let class = class_of(raw);
        let ch = fold(raw, case_sensitive, normalize);
        if pidx < pattern.len() && ch == pattern[pidx] {
            score += SCORE_MATCH;
            let mut bonus = bonus_for(prev_class, class);
            if consecutive == 0 { first_bonus = bonus } else {
                if bonus >= BONUS_BOUNDARY && bonus > first_bonus { first_bonus = bonus }
                bonus = bonus.max(first_bonus).max(BONUS_CONSECUTIVE);
            }
            score += if pidx == 0 { bonus * BONUS_FIRST_CHAR_MULTIPLIER } else { bonus };
            in_gap = false;
            consecutive += 1;
            pidx += 1;
        } else {
            score += if in_gap { SCORE_GAP_EXTENSION } else { SCORE_GAP_START };
            in_gap = true;
            consecutive = 0;
            first_bonus = 0;
        }
        prev_class = class;
    }
    score
}

/// ExactMatchNaive / ExactMatchBoundary: the occurrence with the best bonus at its start — looked
/// for from the end when not `forward` (--tiebreak=end or pathname), as fzf does.
fn exact(case_sensitive: bool, normalize: bool, forward: bool, boundary: bool, text: &[char], pattern: &[char]) -> Option<(usize, usize, i32)> {
    let m = pattern.len();
    if m == 0 { return Some((0, 0, 0)) }
    let n = text.len();
    if n < m { return None }
    // indexAt: an index counted from the end when searching backward.
    let at = |i: usize, max: usize| if forward { i } else { max - i - 1 };
    let (mut pidx, mut best_pos, mut bonus, mut bbonus, mut best_bonus) = (0usize, None::<usize>, 0i32, 0i32, -1i32);
    let mut index = 0isize;
    while (index as usize) < n {
        let idx = at(index as usize, n);
        let ch = fold(text[idx], case_sensitive, normalize);
        let p = at(pidx, m);
        let mut ok = pattern[p] == ch;
        if ok {
            if p == 0 { bonus = bonus_at(text, idx) }
            if boundary {
                if forward && p == 0 { bbonus = bonus }
                else if !forward && p == m - 1 { bbonus = if idx < n - 1 { bonus_at(text, idx + 1) } else { bonus_boundary_white() } }
                ok = bbonus >= BONUS_BOUNDARY;
                if ok && p == 0 { ok = idx == 0 || class_of(text[idx - 1]) <= Class::Delimiter }
                if ok && p == m - 1 { ok = idx == n - 1 || class_of(text[idx + 1]) <= Class::Delimiter }
            }
        }
        if ok {
            pidx += 1;
            if pidx == m {
                if bonus > best_bonus { best_pos = Some(index as usize); best_bonus = bonus }
                if bonus >= BONUS_BOUNDARY { break }
                index -= (pidx - 1) as isize;
                pidx = 0;
                bonus = 0;
            }
        } else {
            index -= pidx as isize;
            pidx = 0;
            bonus = 0;
        }
        index += 1;
    }
    let best = best_pos?;
    let (sidx, eidx) = if forward { (best + 1 - m, best + 1) } else { (n - (best + 1), n - (best + 1 - m)) };
    let score = if boundary {
        // As fzf: the bonus the loop ended on; underscore boundaries rank below the others.
        let mut score = bonus;
        let mut deduct = bonus - BONUS_BOUNDARY + 1;
        if sidx > 0 && text[sidx - 1] == '_' { score -= deduct + 1; deduct = 1 }
        if eidx < n && text[eidx] == '_' { score -= deduct }
        score + SCORE_MATCH * m as i32 + bonus_boundary_white() * (m as i32 + 1)
    } else { calculate_score(case_sensitive, normalize, text, pattern, sidx, eidx) };
    Some((sidx, eidx, score))
}

fn leading_ws(text: &[char]) -> usize { text.iter().take_while(|c| c.is_whitespace()).count() }
fn trailing_ws(text: &[char]) -> usize { text.iter().rev().take_while(|c| c.is_whitespace()).count() }

/// PrefixMatch (`^term`): at the start, past leading spaces.
fn prefix(case_sensitive: bool, normalize: bool, text: &[char], pattern: &[char]) -> Option<(usize, usize, i32)> {
    let m = pattern.len();
    if m == 0 { return Some((0, 0, 0)) }
    let trimmed = if !pattern[0].is_whitespace() { leading_ws(text) } else { 0 };
    if text.len() < trimmed + m { return None }
    for (i, &r) in pattern.iter().enumerate() {
        let mut ch = text[trimmed + i];
        if !case_sensitive { ch = lower(ch) }
        if normalize { ch = normalize_char(ch) }
        if ch != r { return None }
    }
    Some((trimmed, trimmed + m, calculate_score(case_sensitive, normalize, text, pattern, trimmed, trimmed + m)))
}

/// SuffixMatch (`term$`): at the end, before trailing spaces.
fn suffix(case_sensitive: bool, normalize: bool, text: &[char], pattern: &[char]) -> Option<(usize, usize, i32)> {
    let m = pattern.len();
    let mut trimmed = text.len();
    if m == 0 || !pattern[m - 1].is_whitespace() { trimmed -= trailing_ws(text) }
    if m == 0 { return Some((trimmed, trimmed, 0)) }
    if trimmed < m { return None }
    let diff = trimmed - m;
    for (i, &r) in pattern.iter().enumerate() {
        let mut ch = text[diff + i];
        if !case_sensitive { ch = lower(ch) }
        if normalize { ch = normalize_char(ch) }
        if ch != r { return None }
    }
    Some((diff, trimmed, calculate_score(case_sensitive, normalize, text, pattern, diff, trimmed)))
}

/// EqualMatch (`^term$`): the whole line, spaces around it aside.
fn equal(case_sensitive: bool, normalize: bool, text: &[char], pattern: &[char]) -> Option<(usize, usize, i32)> {
    let m = pattern.len();
    if m == 0 { return None }
    let lead = if !pattern[0].is_whitespace() { leading_ws(text) } else { 0 };
    let trail = if !pattern[m - 1].is_whitespace() { trailing_ws(text) } else { 0 };
    if text.len() as isize - lead as isize - trail as isize != m as isize { return None }
    let same = (0..m).all(|i| {
        let ch = if case_sensitive { text[lead + i] } else { lower(text[lead + i]) };
        if normalize { normalize_char(pattern[i]) == normalize_char(ch) } else { pattern[i] == ch }
    });
    same.then(|| (lead, lead + m, (SCORE_MATCH + bonus_boundary_white()) * m as i32 + (BONUS_FIRST_CHAR_MULTIPLIER - 1) * bonus_boundary_white()))
}

// ── the query (pattern.go) ──────────────────────────────────────────────────

#[derive(Clone, Copy, PartialEq, Eq, Debug)]
enum Kind { Fuzzy, Exact, ExactBoundary, Prefix, Suffix, Equal }

#[derive(Clone, Debug)]
struct Term { kind: Kind, inv: bool, text: Vec<char>, case_sensitive: bool, normalize: bool }

/// How a term's case is read: fzf's --smart-case (the default), +i, -i.
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub enum Case { Smart, Respect, Ignore }

/// A query in fzf's extended-search syntax: terms that must all match, `|` between the ones any
/// of which will do.
#[derive(Clone, Debug)]
pub struct Query { sets: Vec<Vec<Term>>, forward: bool, v1: bool }

/// A line's match: its score, where the terms matched (for the tiebreaks: the first begin, the
/// first and the last end), and the characters lit.
pub struct Hit { pub score: i32, pub begin: usize, pub min_end: usize, pub end: usize, pub positions: Vec<usize> }

impl Query {
    /// fzf's parseTerms. `fuzzy`: false under --exact; `normalize`: false under --literal.
    pub fn parse(query: &str, case: Case, fuzzy: bool, normalize: bool) -> Query {
        let mut s = query.trim_start_matches(' ').to_string();
        while s.ends_with(' ') && !s.ends_with("\\ ") { s.pop(); }
        let s = s.replace("\\ ", "\t");
        let (mut sets, mut set): (Vec<Vec<Term>>, Vec<Term>) = (Vec::new(), Vec::new());
        let (mut switch_set, mut after_bar) = (false, false);
        for token in s.split(' ').filter(|t| !t.is_empty()) {
            let mut text = token.replace('\t', " ");
            let lower_text = text.to_lowercase();
            let case_sensitive = case == Case::Respect || (case == Case::Smart && text != lower_text);
            let normalize_term = normalize && lower_text.chars().map(normalize_char).collect::<String>() == lower_text;
            if !case_sensitive { text = lower_text }
            let mut kind = if fuzzy { Kind::Fuzzy } else { Kind::Exact };
            if !set.is_empty() && !after_bar && text == "|" { switch_set = false; after_bar = true; continue }
            after_bar = false;
            let mut inv = false;
            if let Some(rest) = text.strip_prefix('!') { inv = true; kind = Kind::Exact; text = rest.to_string() }
            if text != "$" && text.ends_with('$') { kind = Kind::Suffix; text.pop(); }
            if text.len() > 2 && text.starts_with('\'') && text.ends_with('\'') {
                kind = Kind::ExactBoundary;
                text = text[1..text.len() - 1].to_string();
            } else if let Some(rest) = text.strip_prefix('\'') {
                kind = if fuzzy && !inv { Kind::Exact } else { Kind::Fuzzy };
                text = rest.to_string();
            } else if let Some(rest) = text.strip_prefix('^') {
                kind = if kind == Kind::Suffix { Kind::Equal } else { Kind::Prefix };
                text = rest.to_string();
            }
            if !text.is_empty() {
                if switch_set { sets.push(std::mem::take(&mut set)) }
                let mut chars: Vec<char> = text.chars().collect();
                if normalize_term { chars = chars.into_iter().map(normalize_char).collect() }
                set.push(Term { kind, inv, text: chars, case_sensitive, normalize: normalize_term });
                switch_set = true;
            }
        }
        if !set.is_empty() { sets.push(set) }
        Query { sets, forward: true, v1: false }
    }

    /// The direction fzf searches in for these tiebreaks (core.go): backward when the first of
    /// end, begin and pathname given is end or pathname.
    pub fn searching(mut self, criteria: &[Tiebreak]) -> Query {
        for c in criteria.iter().rev() {
            match c { Tiebreak::End | Tiebreak::Pathname => self.forward = false, Tiebreak::Begin => self.forward = true, _ => {} }
        }
        self
    }

    /// +x (--no-extended): the whole query one term — its blanks and `^ $ ! ' |` its own
    /// characters — fuzzy (exact under -e), its case and normalization read from all of it.
    pub fn plain(query: &str, case: Case, fuzzy: bool, normalize: bool) -> Query {
        let lower = query.to_lowercase();
        let normalize = normalize && lower.chars().map(normalize_char).collect::<String>() == lower;
        let case_sensitive = case == Case::Respect || (case == Case::Smart && lower != query);
        let text = if case_sensitive { query.to_string() } else { lower };
        let mut chars: Vec<char> = text.chars().collect();
        if normalize { chars = chars.into_iter().map(normalize_char).collect() }
        let sets = if chars.is_empty() { Vec::new() } else { vec![vec![Term { kind: if fuzzy { Kind::Fuzzy } else { Kind::Exact }, inv: false, text: chars, case_sensitive, normalize }]] };
        Query { sets, forward: true, v1: false }
    }

    /// --algo=v1: fuzzy terms matched by FuzzyMatchV1.
    pub fn v1(mut self, on: bool) -> Query { self.v1 = on; self }

    /// Some term asks for something (not only `!x`): fzf sorts only then.
    pub fn sortable(&self) -> bool { self.sets.iter().any(|s| s.iter().any(|t| !t.inv)) }

    /// Match the same Boolean groups against a line and optional unanchored metadata.
    /// Extra fields may satisfy a term, including the term an inverse match excludes.
    pub fn matches_with_extra(&self, line: &[char], extra: impl Fn(&str, bool, bool) -> bool) -> bool {
        self.sets.iter().all(|set| set.iter().any(|term| {
            let unanchored = !matches!(term.kind, Kind::Prefix | Kind::Suffix | Kind::Equal);
            let found = run(term, line, self.forward, self.v1).is_some()
                || unanchored && extra(&term.text.iter().collect::<String>(), term.case_sensitive, term.inv);
            found != term.inv
        }))
    }

    pub fn positive_terms(&self) -> Vec<String> {
        self.sets.iter().flatten().filter(|t| !t.inv).map(|t| t.text.iter().collect()).collect()
    }

    /// The index accepts ANDed words, not fzf syntax. A required positive term discovers
    /// candidates for every branch; otherwise ask each alternative of a positive OR group.
    /// The complete expression must still filter the returned candidates.
    pub fn discovery_queries(&self) -> Vec<String> {
        let text = |term: &Term| term.text.iter().collect::<String>();
        let usable = |term: &Term| !term.inv && text(term).split(|c: char| !c.is_alphanumeric()).any(|w| w.chars().count() >= 2);
        let required: Vec<String> = self.sets.iter().filter(|s| s.len() == 1 && usable(&s[0])).map(|s| text(&s[0])).collect();
        if !required.is_empty() { return vec![required.join(" ")] }
        let terms: Vec<&Term> = match self.sets.iter().filter(|s| s.iter().all(&usable)).min_by_key(|s| s.len()) {
            Some(set) => set.iter().collect(),
            None => self.sets.iter().flatten().filter(|t| usable(t)).collect(),
        };
        let mut queries = Vec::new();
        for term in terms { let q = text(term); if !queries.contains(&q) { queries.push(q) } }
        queries
    }

    /// fzf's extendedMatch over one line: every set satisfied (a set by its first term that
    /// matches; a `!term` by its absence), the scores summed.
    pub fn matches(&self, line: &[char]) -> Option<Hit> {
        let (mut total, mut positions) = (0i32, Vec::new());
        let (mut begin, mut min_end, mut end, mut valid) = (usize::MAX, usize::MAX, 0usize, false);
        for set in &self.sets {
            let mut matched = false;
            let (mut score, mut off, mut pos): (i32, (usize, usize), Vec<usize>) = (0, (0, 0), Vec::new());
            for term in set {
                match run(term, line, self.forward, self.v1) {
                    Some((s, e, sc, p)) => {
                        if term.inv { continue }
                        score = sc;
                        off = (s, e);
                        pos = p.unwrap_or_else(|| (s..e).collect());
                        matched = true;
                        break;
                    }
                    None if term.inv => { score = 0; off = (0, 0); pos.clear(); matched = true; }
                    None => {}
                }
            }
            if !matched { return None }
            total += score;
            positions.extend(pos);
            if off.0 < off.1 { begin = begin.min(off.0); min_end = min_end.min(off.1); end = end.max(off.1); valid = true }
        }
        positions.sort_unstable();
        positions.dedup();
        Some(Hit { score: total, begin: if valid { begin } else { 0 }, min_end: if valid { min_end } else { 0 }, end: if valid { end } else { 0 }, positions })
    }
}

/// One term against a line: (start, end, score, positions when the algorithm knows them).
fn run(term: &Term, line: &[char], forward: bool, v1: bool) -> Option<(usize, usize, i32, Option<Vec<usize>>)> {
    let (cs, nz, p) = (term.case_sensitive, term.normalize, &term.text[..]);
    match term.kind {
        Kind::Fuzzy if v1 => fuzzy_v1(cs, nz, forward, line, p).map(|(s, e, sc, pos)| (s, e, sc, Some(pos))),
        Kind::Fuzzy => fuzzy_v2(cs, nz, forward, line, p).map(|(s, e, sc, pos)| (s, e, sc, Some(pos))),
        Kind::Exact => exact(cs, nz, forward, false, line, p).map(|(s, e, sc)| (s, e, sc, None)),
        Kind::ExactBoundary => exact(cs, nz, forward, true, line, p).map(|(s, e, sc)| (s, e, sc, None)),
        Kind::Prefix => prefix(cs, nz, line, p).map(|(s, e, sc)| (s, e, sc, None)),
        Kind::Suffix => suffix(cs, nz, line, p).map(|(s, e, sc)| (s, e, sc, None)),
        Kind::Equal => equal(cs, nz, line, p).map(|(s, e, sc)| (s, e, sc, None)),
    }
}

/// fzf's --tiebreak criteria after the score.
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub enum Tiebreak { Length, Chunk, Pathname, Begin, End }

/// The rank fzf gives a matched line: lower first — buildResult's points (each a uint16, as fzf
/// keeps them), then the input order.
pub fn rank(hit: &Hit, line: &[char], criteria: &[Tiebreak]) -> Vec<i64> {
    const MAX: i64 = u16::MAX as i64;
    let u16 = |v: i64| v.clamp(0, MAX);
    let mut out = vec![MAX - u16(hit.score as i64)];
    let n = line.len();
    let trim_len = || { let l = leading_ws(line); if l == n { 0 } else { (n - l - trailing_ws(line)) as i64 } };
    let valid = hit.begin < hit.end;
    for c in criteria {
        out.push(match c {
            Tiebreak::Length => u16(trim_len()),
            Tiebreak::Chunk if valid => {
                let mut b = hit.begin;
                while b >= 1 && !line[b - 1].is_whitespace() { b -= 1 }
                let mut e = hit.end;
                while e < n && !line[e].is_whitespace() { e += 1 }
                u16((e - b) as i64)
            }
            // The last delimiter as fzf finds it: a byte index in the line's text.
            Tiebreak::Pathname if valid => {
                let text: String = line.iter().collect();
                let last = text.bytes().rposition(|b| b == b'/' || b == b'\\').map(|i| i as i64).unwrap_or(-1);
                if last <= hit.begin as i64 { u16(hit.begin as i64 - last) } else { MAX }
            }
            Tiebreak::Begin | Tiebreak::End if valid => {
                // Leading blanks don't count (up to where the match begins).
                let mut white = 0usize;
                for (idx, ch) in line.iter().enumerate() { white = idx; if idx == hit.begin || !ch.is_whitespace() { break } }
                if *c == Tiebreak::Begin { u16(hit.min_end as i64 - white as i64) } else { u16(MAX - MAX * (hit.end as i64 - white as i64) / (trim_len() + 1)) }
            }
            _ => MAX,
        });
    }
    out
}

/// fzf's latin-script normalization (src/algo/normalize.go): an accented letter matches its base.
fn normalize_char(c: char) -> char {
    let n = c as u32;
    if !(0x00C0..=0xFF61).contains(&n) { return c }
    match n {
        0xFF01 => '!',
        0xFF02 => '"',
        0xFF03 => '#',
        0xFF04 => '$',
        0xFF05 => '%',
        0xFF06 => '&',
        0xFF08 => '(',
        0xFF09 => ')',
        0xFF0A => '*',
        0xFF0B => '+',
        0xFF0C => ',',
        0xFF0D => '-',
        0xFF0E | 0xFF61 => '.',
        0xFF0F => '/',
        0xFF10 => '0',
        0xFF11 => '1',
        0xFF12 => '2',
        0xFF13 => '3',
        0xFF14 => '4',
        0xFF15 => '5',
        0xFF16 => '6',
        0xFF17 => '7',
        0xFF18 => '8',
        0xFF19 => '9',
        0xFF1A => ':',
        0xFF1B => ';',
        0xFF1C => '<',
        0xFF1D => '=',
        0xFF1E => '>',
        0xFF1F => '?',
        0xFF20 => '@',
        0x00C0 | 0x00C1 | 0x00C2 | 0x00C3 | 0x00C4 | 0x00C5 | 0x023A | 0x1D00 | 0xFF21 => 'A',
        0x0181 | 0x0243 | 0x0299 | 0x1D03 | 0xFF22 => 'B',
        0x00C7 | 0x023B | 0x1D04 | 0xFF23 => 'C',
        0x0189 | 0x018A | 0x1D05 | 0xFF24 => 'D',
        0x00C8 | 0x00C9 | 0x00CA | 0x00CB | 0x018E | 0x0190 | 0x0246 | 0x1D07 | 0xFF25 => 'E',
        0xFF26 => 'F',
        0x0193 | 0x0262 | 0x029B | 0xFF27 => 'G',
        0x029C | 0xFF28 => 'H',
        0x00CC | 0x00CD | 0x00CE | 0x00CF | 0x0130 | 0x0197 | 0x026A | 0xFF29 => 'I',
        0x0248 | 0x1D0A | 0xFF2A => 'J',
        0x1D0B | 0xFF2B => 'K',
        0x023D | 0x029F | 0x1D0C | 0xFF2C => 'L',
        0x019C | 0x1D0D | 0xFF2D => 'M',
        0x00D1 | 0x019D | 0x0220 | 0x0274 | 0x1D0E | 0xFF2E => 'N',
        0x00D2 | 0x00D3 | 0x00D4 | 0x00D5 | 0x00D6 | 0x00D8 | 0x0186 | 0x019F | 0x1D0F | 0x1D10 | 0xFF2F => 'O',
        0x1D18 | 0xFF30 => 'P',
        0x024A | 0xFF31 => 'Q',
        0x024C | 0x0280 | 0x0281 | 0x1D19 | 0x1D1A | 0xFF32 => 'R',
        0xFF33 => 'S',
        0x01AE | 0x023E | 0x1D1B | 0xFF34 => 'T',
        0x00D9 | 0x00DA | 0x00DB | 0x00DC | 0x0244 | 0x1D1C | 0xFF35 => 'U',
        0x01B2 | 0x0245 | 0x1D20 | 0xFF36 => 'V',
        0x1D21 | 0xFF37 => 'W',
        0xFF38 => 'X',
        0x00DD | 0x0178 | 0x024E | 0x028F | 0xFF39 => 'Y',
        0x1D22 | 0xFF3A => 'Z',
        0xFF3B => '[',
        0xFF07 => '\'',
        0xFF3C => '\\',
        0xFF3D => ']',
        0xFF3E => '^',
        0xFF3F => '_',
        0xFF40 => '`',
        0x00E0 | 0x00E1 | 0x00E2 | 0x00E3 | 0x00E4 | 0x00E5 | 0x0101 | 0x0103 | 0x0105 | 0x01CE | 0x0201 | 0x0203 | 0x0227 | 0x0250 | 0x0251 | 0x0363 | 0x1E01 | 0x1E9A | 0x1EA1 | 0x1EA3 | 0xFF41 => 'a',
        0x0180 | 0x0183 | 0x0253 | 0x1E03 | 0x1E05 | 0x1E07 | 0xFF42 => 'b',
        0x00E7 | 0x0107 | 0x0109 | 0x010B | 0x010D | 0x0188 | 0x023C | 0x0255 | 0x0297 | 0x0368 | 0x2184 | 0xFF43 => 'c',
        0x010F | 0x0111 | 0x018C | 0x0221 | 0x0256 | 0x0257 | 0x0369 | 0x1E0B | 0x1E0D | 0x1E0F | 0x1E11 | 0x1E13 | 0xFF44 => 'd',
        0x00E8 | 0x00E9 | 0x00EA | 0x00EB | 0x0113 | 0x0115 | 0x0117 | 0x0119 | 0x011B | 0x01DD | 0x0205 | 0x0207 | 0x0229 | 0x0247 | 0x0258 | 0x025B | 0x025C | 0x025D | 0x025E | 0x029A | 0x0364 | 0x1D08 | 0x1E19 | 0x1E1B | 0x1EB9 | 0x1EBB | 0x1EBD | 0xFF45 => 'e',
        0x0192 | 0x1E1F | 0xFF46 => 'f',
        0x011D | 0x011F | 0x0121 | 0x0123 | 0x01E5 | 0x01E7 | 0x01F5 | 0x0260 | 0x0261 | 0x1E21 | 0xFF47 => 'g',
        0x0125 | 0x0127 | 0x021F | 0x0265 | 0x0266 | 0x02AE | 0x036A | 0x1E23 | 0x1E25 | 0x1E27 | 0x1E29 | 0x1E2B | 0x1E96 | 0x2095 | 0xFF48 => 'h',
        0x00EC | 0x00ED | 0x00EE | 0x00EF | 0x0129 | 0x012B | 0x012D | 0x012F | 0x0131 | 0x01D0 | 0x0209 | 0x020B | 0x0268 | 0x0365 | 0x1D09 | 0x1D62 | 0x1E2D | 0x1EC9 | 0x1ECB | 0x2071 | 0xFF49 => 'i',
        0x0135 | 0x01F0 | 0x0237 | 0x0249 | 0x025F | 0x029D | 0xFF4A => 'j',
        0x0137 | 0x0199 | 0x01E9 | 0x029E | 0x1E31 | 0x1E33 | 0x1E35 | 0x2096 | 0xFF4B => 'k',
        0x013A | 0x013C | 0x013E | 0x0140 | 0x0142 | 0x019A | 0x0234 | 0x026B | 0x026C | 0x026D | 0x1E37 | 0x1E3B | 0x1E3D | 0x2097 | 0xFF4C => 'l',
        0x026F | 0x0270 | 0x0271 | 0x036B | 0x1D1F | 0x1E3F | 0x1E41 | 0x1E43 | 0x2098 | 0xFF4D => 'm',
        0x00F1 | 0x0144 | 0x0146 | 0x0148 | 0x019E | 0x01F9 | 0x0235 | 0x0272 | 0x0273 | 0x1E45 | 0x1E47 | 0x1E49 | 0x1E4B | 0x2099 | 0xFF4E => 'n',
        0x00F2 | 0x00F3 | 0x00F4 | 0x00F5 | 0x00F6 | 0x00F8 | 0x014D | 0x014F | 0x0151 | 0x01A1 | 0x01D2 | 0x01EB | 0x020D | 0x020F | 0x022F | 0x0254 | 0x0275 | 0x0366 | 0x1D11 | 0x1D12 | 0x1D13 | 0x1D16 | 0x1D17 | 0x1ECD | 0x1ECF | 0xFF4F => 'o',
        0x01A5 | 0x1E55 | 0x1E57 | 0x209A | 0xFF50 => 'p',
        0x024B | 0x02A0 | 0xFF51 => 'q',
        0x0155 | 0x0157 | 0x0159 | 0x0211 | 0x0213 | 0x024D | 0x0279 | 0x027A | 0x027B | 0x027C | 0x027D | 0x027E | 0x027F | 0x036C | 0x1D63 | 0x1E59 | 0x1E5B | 0x1E5F | 0xFF52 => 'r',
        0x00DF | 0x015B | 0x015D | 0x015F | 0x0161 | 0x017F | 0x0219 | 0x023F | 0x0282 | 0x1E61 | 0x1E63 | 0x1E9B | 0x209B | 0xFF53 => 's',
        0x0163 | 0x0165 | 0x0167 | 0x01AB | 0x01AD | 0x021B | 0x0236 | 0x0287 | 0x0288 | 0x036D | 0x1E6B | 0x1E6D | 0x1E6F | 0x1E71 | 0x1E97 | 0x209C | 0xFF54 => 't',
        0x00F9 | 0x00FA | 0x00FB | 0x00FC | 0x0169 | 0x016B | 0x016D | 0x016F | 0x0171 | 0x0173 | 0x01B0 | 0x01D4 | 0x0215 | 0x0217 | 0x0289 | 0x0367 | 0x1D1D | 0x1D1E | 0x1D64 | 0x1E73 | 0x1E75 | 0x1E77 | 0x1EE5 | 0x1EE7 | 0xFF55 => 'u',
        0x028B | 0x028C | 0x036E | 0x1D65 | 0x1E7D | 0x1E7F | 0xFF56 => 'v',
        0x0175 | 0x028D | 0x1E81 | 0x1E83 | 0x1E85 | 0x1E87 | 0x1E89 | 0x1E98 | 0xFF57 => 'w',
        0x036F | 0x1E8B | 0x1E8D | 0xFF58 => 'x',
        0x00FD | 0x00FF | 0x0177 | 0x01B4 | 0x0233 | 0x024F | 0x028E | 0x1E8F | 0x1E99 | 0x1EF3 | 0x1EF5 | 0x1EF7 | 0x1EF9 | 0xFF59 => 'y',
        0x017A | 0x017C | 0x017E | 0x01B6 | 0x0225 | 0x0240 | 0x0290 | 0x0291 | 0x1E91 | 0x1E93 | 0x1E95 | 0xFF5A => 'z',
        0xFF5B => '{',
        0xFF5C => '|',
        0xFF5D => '}',
        0xFF5E => '~',
        _ => c,
    }
}

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

    fn hit(q: &str, line: &str) -> Option<Hit> { Query::parse(q, Case::Smart, true, true).matches(&line.chars().collect::<Vec<_>>()) }

    #[test]
    fn ties_light_the_first_occurrence_as_fzf_does() {
        // "copy" in `C-b [  copy-mode  Enter copy mode`: fzf lights copy-mode, not the note.
        let line = "C-b [  copy-mode  Enter copy mode";
        let h = hit("copy", line).unwrap();
        assert_eq!(h.positions, vec![7, 8, 9, 10]);
    }

    #[test]
    fn one_letter_on_a_line_with_a_middle_dot() {
        // Word starts count after `·` too (nucleo lost them on non-ASCII lines).
        let h = hit("e", "Train tokenizer on the new corpus  ml-lab · exp/tokenizer-v3").unwrap();
        let line: Vec<char> = "Train tokenizer on the new corpus  ml-lab · exp/tokenizer-v3".chars().collect();
        assert_eq!(line[h.positions[0]], 'e');
        assert_eq!(h.positions[0], 44);
    }

    /// Real fzf 0.67's order for 30 queries over 186 lines (tests/fixtures/fzf: `fzf --filter`).
    #[test]
    fn ranks_as_fzf_does() {
        use Tiebreak::*;
        // fzf 0.67's own --filter output over the same lines, for each --tiebreak.
        let fixtures: [(&str, &[Tiebreak]); 11] = [
            (include_str!("../tests/fixtures/fzf/expected.txt"), &[Length]),
            (include_str!("../tests/fixtures/fzf/expected-end.txt"), &[End]),
            (include_str!("../tests/fixtures/fzf/expected-begin.txt"), &[Begin]),
            (include_str!("../tests/fixtures/fzf/expected-pathname.txt"), &[Pathname]),
            (include_str!("../tests/fixtures/fzf/expected-chunk.txt"), &[Chunk]),
            (include_str!("../tests/fixtures/fzf/expected-index.txt"), &[]),
            (include_str!("../tests/fixtures/fzf/expected-end-length.txt"), &[End, Length]),
            (include_str!("../tests/fixtures/fzf/expected-begin-length.txt"), &[Begin, Length]),
            (include_str!("../tests/fixtures/fzf/expected-length-end.txt"), &[Length, End]),
            (include_str!("../tests/fixtures/fzf/expected-pathname-length.txt"), &[Pathname, Length]),
            (include_str!("../tests/fixtures/fzf/expected-chunk-begin.txt"), &[Chunk, Begin]),
        ];
        let lines: Vec<&str> = include_str!("../tests/fixtures/fzf/lines.txt").lines().collect();
        let mut wrong = Vec::new();
        for (fixture, criteria) in fixtures {
            for block in fixture.split("### ").filter(|b| !b.is_empty()) {
                let mut it = block.lines();
                let q = it.next().unwrap_or("");
                let want: Vec<&str> = it.collect();
                let query = Query::parse(q, Case::Smart, true, true).searching(criteria);
                let mut got: Vec<(Vec<i64>, &str)> = lines.iter().enumerate().filter_map(|(i, l)| {
                    let chars: Vec<char> = l.chars().collect();
                    query.matches(&chars).map(|h| { let mut r = rank(&h, &chars, criteria); r.push(i as i64); (r, *l) })
                }).collect();
                if query.sortable() { got.sort_by(|a, b| a.0.cmp(&b.0)) }
                let got: Vec<&str> = got.into_iter().map(|(_, l)| l).collect();
                if got != want { wrong.push(format!("{criteria:?} {q:?}: fzf {} lines, hn {}; first difference at {}", want.len(), got.len(), got.iter().zip(&want).position(|(a, b)| a != b).unwrap_or(got.len().min(want.len())))) }
            }
        }
        assert!(wrong.is_empty(), "{}", wrong.join("\n"));
    }

    /// The characters fzf lights when it searches from the end (--tiebreak=end): the last of the
    /// best, as fzf 0.67 draws them.
    #[test]
    fn lights_from_the_end_for_tiebreak_end() {
        let lit = |q: &str, line: &str, criteria: &[Tiebreak]| { let chars: Vec<char> = line.chars().collect(); Query::parse(q, Case::Smart, true, true).searching(criteria).matches(&chars).unwrap().positions };
        let line = "C-b E  select-layout -E  Spread panes out evenly";
        assert_eq!(lit("e", line, &[Tiebreak::End]), vec![42]);
        assert_eq!(lit("e", line, &[Tiebreak::Length]), vec![4]);
        assert_eq!(lit("'lay", line, &[Tiebreak::End]), vec![14, 15, 16]);
    }

    #[test]
    fn extended_search() {
        assert!(hit("'site", "docs site").is_some());
        assert!(hit("!docs", "docs site").is_none());
        assert!(hit("^docs", "docs site").is_some() && hit("^site", "docs site").is_none());
        assert!(hit("site$", "docs site").is_some() && hit("docs$", "docs site").is_none());
        // Two terms, as fzf reads it: ^docs and site$.
        assert!(hit("^docs site$", "docs site").is_some());
        assert!(hit("docs | nope", "docs site").is_some() && hit("nope | none", "docs site").is_none());
        assert!(hit("Docs", "docs site").is_none() && hit("docs", "Docs site").is_some());
        assert!(hit("cafe", "Café").is_some());
    }
}