Skip to main content

arb/
pattern.rs

1//! A port of fzf's query language — `src/pattern.go` from fzf 0.74.3.
2//!
3//! fzf's default search mode is EXTENDED: a query is a space-separated list of
4//! terms that must all match (AND), `|` between terms makes an OR set, and a
5//! term can carry a sigil that changes how it matches:
6//!
7//! ```text
8//! fuzzy      'exact      ^prefix      suffix$      ^equal$      'boundary'
9//! !inverse   !'inverse-fuzzy          !^inverse-prefix          !inverse-suffix$
10//! ```
11//!
12//! Everything here is a PORT, not an approximation — `parseTerms`, the term
13//! type flips, `extendedMatch`'s OR/AND/inverse walk and the `sortable` /
14//! `cacheable` flags all follow the Go source, so `arb --fzf` answers a query
15//! the way `fzf` answers it. `-x`/`--extended` and `+x`/`--no-extended` select
16//! the mode; extended is the default, as in fzf.
17//!
18//! A [`Pattern`] is built ONCE per query and scored against every line. That is
19//! deliberate: the pattern's `Vec<char>` and case decision are per-QUERY work,
20//! and doing them per line (as arb did before this module existed) cost more
21//! than the match itself on a query that rejects most of the corpus.
22
23use crate::algo::{self, Match, Text};
24use crate::fzf::Case;
25
26/// How one term matches — fzf's `termType` (pattern.go:22).
27#[derive(Clone, Copy, PartialEq, Eq, Debug)]
28pub enum TermType {
29    Fuzzy,
30    Exact,
31    ExactBoundary,
32    Prefix,
33    Suffix,
34    Equal,
35}
36
37/// One term of a query: the text to look for, how to look for it, and whether
38/// finding it DISQUALIFIES the line (`!`).
39#[derive(Clone, Debug)]
40pub struct Term {
41    pub typ: TermType,
42    pub inv: bool,
43    pub text: Vec<char>,
44    pub case_sensitive: bool,
45}
46
47impl Term {
48    /// Run this term's matcher against one line.
49    fn run(
50        &self,
51        scheme: &crate::algo::Scheme,
52        forward: bool,
53        algo_v1: bool,
54        input: &Text,
55        with_pos: bool,
56    ) -> Option<(Match, Option<Vec<usize>>)> {
57        let f = match self.typ {
58            TermType::Fuzzy => match algo_v1 {
59                true => algo::fuzzy_match_v1,
60                false => algo::fuzzy_match_v2,
61            },
62            TermType::Exact => algo::exact_match_naive,
63            TermType::ExactBoundary => algo::exact_match_boundary,
64            TermType::Prefix => algo::prefix_match,
65            TermType::Suffix => algo::suffix_match,
66            TermType::Equal => algo::equal_match,
67        };
68        f(
69            scheme,
70            self.case_sensitive,
71            forward,
72            input,
73            &self.text,
74            with_pos,
75        )
76    }
77}
78
79/// A parsed query, ready to score any number of lines.
80#[derive(Clone, Debug)]
81pub struct Pattern {
82    /// `false` under `-e`/`--exact`, which turns every bare term into a
83    /// substring match (fzf's `fuzzy` flag, inverted from arb's `exact`).
84    fuzzy: bool,
85    extended: bool,
86    /// Non-extended state: the whole query as one term.
87    text: Vec<char>,
88    case_sensitive: bool,
89    /// Extended state: AND across the outer Vec, OR within each inner one.
90    term_sets: Vec<Vec<Term>>,
91    /// fzf's `sortable` (pattern.go:100): a query of nothing but inverse terms
92    /// scores every survivor 0, so fzf leaves them in input order instead of
93    /// letting the tiebreak reshuffle them.
94    pub sortable: bool,
95    /// fzf's `cacheable` (pattern.go:115): every term set is a single plain,
96    /// non-inverse term, so extending the query can only ever NARROW the result
97    /// set. This is what makes the picker's incremental re-filter sound — an
98    /// inverse term or an `|` can WIDEN it, and then the old hit set is not a
99    /// superset of the new one.
100    pub cacheable: bool,
101    /// `--scheme`: which characters count as boundaries and what a match just
102    /// after one is worth. Carried on the pattern so the scorer never depends on
103    /// a process-wide setting.
104    pub scheme: crate::algo::Scheme,
105    /// Scan direction, and whether the matchers must backtrack for an accurate
106    /// begin offset. Neither is a user option: fzf derives both from the
107    /// `--tiebreak` criteria (core.go:215), because `end` and `pathname` want
108    /// the LAST best match and `chunk`/`pathname` need to know where it starts.
109    forward: bool,
110    with_pos: bool,
111    /// `--algo=v1`: use fzf's older greedy matcher instead of the score matrix.
112    algo_v1: bool,
113}
114
115impl Pattern {
116    /// fzf's `BuildPattern` (pattern.go:79). `exact` is `-e`/`--exact`,
117    /// `extended` is `-x`/`+x`, `case` is `-i`/`+i`/`--smart-case`.
118    pub fn build(query: &str, exact: bool, extended: bool, case: Case) -> Pattern {
119        Pattern::build_with(query, exact, extended, case, crate::algo::Scheme::DEFAULT)
120    }
121
122    /// [`Pattern::build`] under an explicit `--scheme`.
123    pub fn build_with(
124        query: &str,
125        exact: bool,
126        extended: bool,
127        case: Case,
128        scheme: crate::algo::Scheme,
129    ) -> Pattern {
130        Pattern::build_ranked(
131            query,
132            exact,
133            extended,
134            case,
135            scheme,
136            &scheme_criteria(&scheme),
137        )
138    }
139
140    /// [`Pattern::build_with`] told which `--tiebreak` criteria the ranking will
141    /// use, so the matchers can scan in the direction those criteria need.
142    pub fn build_ranked(
143        query: &str,
144        exact: bool,
145        extended: bool,
146        case: Case,
147        scheme: crate::algo::Scheme,
148        criteria: &[Criterion],
149    ) -> Pattern {
150        Pattern::build_full(query, exact, extended, case, scheme, criteria, false)
151    }
152
153    /// [`Pattern::build_ranked`] with `--algo` chosen too.
154    #[allow(clippy::too_many_arguments)]
155    pub fn build_full(
156        query: &str,
157        exact: bool,
158        extended: bool,
159        case: Case,
160        scheme: crate::algo::Scheme,
161        criteria: &[Criterion],
162        algo_v1: bool,
163    ) -> Pattern {
164        let (forward, with_pos) = scan_direction(criteria);
165        let fuzzy = !exact;
166        // Extended mode trims the query's outer spaces (they are term
167        // separators, not text) — but an escaped `\ ` at the end is real.
168        let as_string = match extended {
169            true => {
170                let mut s = query.trim_start_matches(' ');
171                while s.ends_with(' ') && !s.ends_with("\\ ") {
172                    s = &s[..s.len() - 1];
173                }
174                s.to_string()
175            }
176            false => query.to_string(),
177        };
178
179        if !extended {
180            let lower = as_string.to_lowercase();
181            let case_sensitive = match case {
182                Case::Respect => true,
183                Case::Ignore => false,
184                Case::Smart => lower != as_string,
185            };
186            let text = match case_sensitive {
187                true => as_string.chars().collect(),
188                false => lower.chars().collect(),
189            };
190            return Pattern {
191                fuzzy,
192                extended,
193                text,
194                case_sensitive,
195                term_sets: Vec::new(),
196                sortable: true,
197                cacheable: true,
198                scheme,
199                forward,
200                with_pos,
201                algo_v1,
202            };
203        }
204
205        let term_sets = parse_terms(fuzzy, case, &as_string);
206        // A query of only inverse terms is not sortable; one plain term per set
207        // (and nothing inverted) is cacheable.
208        let mut sortable = false;
209        let mut cacheable = true;
210        for set in &term_sets {
211            for (idx, term) in set.iter().enumerate() {
212                if !term.inv {
213                    sortable = true;
214                }
215                let plain = match fuzzy {
216                    true => term.typ == TermType::Fuzzy,
217                    false => term.typ == TermType::Exact,
218                };
219                if idx > 0 || term.inv || !plain {
220                    cacheable = false;
221                }
222            }
223        }
224        Pattern {
225            fuzzy,
226            extended,
227            text: Vec::new(),
228            case_sensitive: true,
229            term_sets,
230            sortable,
231            cacheable,
232            scheme,
233            forward,
234            with_pos,
235            algo_v1,
236        }
237    }
238
239    /// fzf's `Pattern.IsEmpty` (pattern.go:252) — an empty query matches
240    /// everything, and the picker shows the stream untouched.
241    pub fn is_empty(&self) -> bool {
242        match self.extended {
243            true => self.term_sets.is_empty(),
244            false => self.text.is_empty(),
245        }
246    }
247
248    /// The score for one line, or `None` when the line does not match. This is
249    /// fzf's `MatchItem` (pattern.go:388) reduced to the score — the offsets it
250    /// also returns drive highlighting, which [`Pattern::positions`] handles.
251    pub fn score(&self, line: &str) -> Option<i32> {
252        if self.is_empty() {
253            return Some(0);
254        }
255        let text = Text::new(line);
256        match self.extended {
257            true => self.extended_match(&text, false).map(|(s, _)| s),
258            false => self.basic_match(&text, false).map(|(m, _)| m.score),
259        }
260    }
261
262    /// The character indices this pattern matched, for fzf's highlight. Sorted
263    /// and deduplicated: an OR set can match overlapping runs.
264    pub fn positions(&self, line: &str) -> Vec<usize> {
265        if self.is_empty() {
266            return Vec::new();
267        }
268        let text = Text::new(line);
269        let mut pos = match self.extended {
270            true => self.extended_match(&text, true).and_then(|(_, p)| p),
271            false => self.basic_match(&text, true).and_then(|(_, p)| p),
272        }
273        .unwrap_or_default();
274        pos.sort_unstable();
275        pos.dedup();
276        pos
277    }
278
279    /// The score AND the match bounds for one line — fzf's `MatchItem` in full.
280    /// [`Pattern::score`] is this with the bounds dropped; the tiebreak criteria
281    /// need them, because `begin`, `end`, `chunk` and `pathname` all rank by
282    /// WHERE the match landed rather than how well it scored.
283    pub fn match_line(&self, line: &str) -> Option<Bounds> {
284        if self.is_empty() {
285            return Some(Bounds::empty(0));
286        }
287        let text = Text::new(line);
288        match self.extended {
289            true => self.extended_bounds(&text),
290            false => self.basic_match(&text, self.with_pos).map(|(m, _)| {
291                let mut b = Bounds::empty(m.score);
292                b.add(m.start, m.end);
293                b
294            }),
295        }
296    }
297
298    /// fzf's `basicMatch` (pattern.go:403) — `+x`: the whole query is one term.
299    fn basic_match(&self, text: &Text, with_pos: bool) -> Option<(Match, Option<Vec<usize>>)> {
300        match self.fuzzy {
301            true if self.algo_v1 => algo::fuzzy_match_v1(
302                &self.scheme,
303                self.case_sensitive,
304                self.forward,
305                text,
306                &self.text,
307                with_pos,
308            ),
309            true => algo::fuzzy_match_v2(
310                &self.scheme,
311                self.case_sensitive,
312                self.forward,
313                text,
314                &self.text,
315                with_pos,
316            ),
317            false => algo::exact_match_naive(
318                &self.scheme,
319                self.case_sensitive,
320                self.forward,
321                text,
322                &self.text,
323                with_pos,
324            ),
325        }
326    }
327
328    /// [`Pattern::extended_match`] keeping the offsets instead of the positions,
329    /// so the tiebreak criteria can see where each term set matched.
330    fn extended_bounds(&self, text: &Text) -> Option<Bounds> {
331        let mut bounds = Bounds::empty(0);
332        for set in &self.term_sets {
333            let mut matched = false;
334            let mut current = 0i32;
335            let mut offset = (0usize, 0usize);
336            for term in set {
337                match term.run(
338                    &self.scheme,
339                    self.forward,
340                    self.algo_v1,
341                    text,
342                    self.with_pos,
343                ) {
344                    Some((m, _)) => {
345                        if term.inv {
346                            continue;
347                        }
348                        current = m.score;
349                        offset = (m.start, m.end);
350                        matched = true;
351                        break;
352                    }
353                    None if term.inv => {
354                        // A satisfied inverse term contributes an EMPTY offset,
355                        // which `Bounds::add` ignores — it locates nothing.
356                        current = 0;
357                        offset = (0, 0);
358                        matched = true;
359                        continue;
360                    }
361                    None => {}
362                }
363            }
364            if !matched {
365                return None;
366            }
367            bounds.score += current;
368            bounds.add(offset.0, offset.1);
369        }
370        Some(bounds)
371    }
372
373    /// fzf's `extendedMatch` (pattern.go:416). Every term set must produce a
374    /// match; within a set the FIRST matching term wins and the rest are
375    /// skipped, which is what makes `|` an OR. An inverse term matching kills
376    /// the set unless a later term in it matches; an inverse term NOT matching
377    /// satisfies the set with a score of zero.
378    fn extended_match(&self, text: &Text, with_pos: bool) -> Option<(i32, Option<Vec<usize>>)> {
379        let mut total = 0i32;
380        let mut all_pos = with_pos.then(Vec::new);
381        for set in &self.term_sets {
382            let mut matched = false;
383            let mut current = 0i32;
384            for term in set {
385                match term.run(&self.scheme, self.forward, self.algo_v1, text, with_pos) {
386                    Some((m, pos)) => {
387                        if term.inv {
388                            continue;
389                        }
390                        current = m.score;
391                        matched = true;
392                        if let Some(all) = all_pos.as_mut() {
393                            match pos {
394                                Some(p) => all.extend(p),
395                                None => all.extend(m.start..m.end),
396                            }
397                        }
398                        break;
399                    }
400                    None if term.inv => {
401                        current = 0;
402                        matched = true;
403                        continue;
404                    }
405                    None => {}
406                }
407            }
408            // One unsatisfied set is enough to reject the line (fzf compares
409            // the offset count against the term-set count).
410            if !matched {
411                return None;
412            }
413            total += current;
414        }
415        Some((total, all_pos))
416    }
417}
418
419/// fzf's `parseTerms` (pattern.go:166). `\ ` escapes a space into the term
420/// rather than splitting on it, so it is swapped for a tab across the split and
421/// swapped back after.
422fn parse_terms(fuzzy: bool, case: Case, query: &str) -> Vec<Vec<Term>> {
423    let escaped = query.replace("\\ ", "\t");
424    let mut sets: Vec<Vec<Term>> = Vec::new();
425    let mut set: Vec<Term> = Vec::new();
426    let mut switch_set = false;
427    let mut after_bar = false;
428
429    for token in escaped.split(' ').filter(|t| !t.is_empty()) {
430        let mut typ = TermType::Fuzzy;
431        let mut inv = false;
432        let mut text = token.replace('\t', " ");
433        let lower = text.to_lowercase();
434        let case_sensitive = match case {
435            Case::Respect => true,
436            Case::Ignore => false,
437            Case::Smart => text != lower,
438        };
439        if !case_sensitive {
440            text = lower;
441        }
442        if !fuzzy {
443            typ = TermType::Exact;
444        }
445
446        // A bare `|` joins the previous term into an OR set instead of starting
447        // a new one. Two in a row is not an operator, it is a term.
448        if !set.is_empty() && !after_bar && text == "|" {
449            switch_set = false;
450            after_bar = true;
451            continue;
452        }
453        after_bar = false;
454
455        if let Some(rest) = text.strip_prefix('!') {
456            inv = true;
457            typ = TermType::Exact;
458            text = rest.to_string();
459        }
460
461        if text != "$" {
462            if let Some(rest) = text.strip_suffix('$') {
463                typ = TermType::Suffix;
464                text = rest.to_string();
465            }
466        }
467
468        if text.len() > 2 && text.starts_with('\'') && text.ends_with('\'') {
469            typ = TermType::ExactBoundary;
470            text = text[1..text.len() - 1].to_string();
471        } else if let Some(rest) = text.strip_prefix('\'') {
472            // `'` flips exactness: it makes a fuzzy search exact, and an exact
473            // search (`--exact`, or an inverse term) fuzzy.
474            typ = match fuzzy && !inv {
475                true => TermType::Exact,
476                false => TermType::Fuzzy,
477            };
478            text = rest.to_string();
479        } else if let Some(rest) = text.strip_prefix('^') {
480            typ = match typ == TermType::Suffix {
481                true => TermType::Equal,
482                false => TermType::Prefix,
483            };
484            text = rest.to_string();
485        }
486
487        if text.is_empty() {
488            continue;
489        }
490        if switch_set {
491            sets.push(std::mem::take(&mut set));
492        }
493        set.push(Term {
494            typ,
495            inv,
496            text: text.chars().collect(),
497            case_sensitive,
498        });
499        switch_set = true;
500    }
501    if !set.is_empty() {
502        sets.push(set);
503    }
504    sets
505}
506
507#[cfg(test)]
508mod tests {
509    use super::*;
510
511    fn terms(query: &str) -> Vec<Vec<Term>> {
512        parse_terms(true, Case::Smart, query)
513    }
514
515    #[test]
516    fn space_separated_terms_are_anded() {
517        let p = Pattern::build("usr bin", false, true, Case::Smart);
518        assert_eq!(p.term_sets.len(), 2);
519        assert!(p.score("/usr/local/bin").is_some());
520        assert!(p.score("/usr/local/lib").is_none());
521        assert!(p.score("/opt/bin").is_none());
522    }
523
524    #[test]
525    fn bar_makes_an_or_set() {
526        let p = Pattern::build("^/usr | ^/opt", false, true, Case::Smart);
527        assert_eq!(p.term_sets.len(), 1);
528        assert_eq!(p.term_sets[0].len(), 2);
529        assert!(p.score("/usr/bin").is_some());
530        assert!(p.score("/opt/bin").is_some());
531        assert!(p.score("/var/bin").is_none());
532    }
533
534    #[test]
535    fn sigils_select_the_term_type() {
536        assert_eq!(terms("'abc")[0][0].typ, TermType::Exact);
537        assert_eq!(terms("^abc")[0][0].typ, TermType::Prefix);
538        assert_eq!(terms("abc$")[0][0].typ, TermType::Suffix);
539        assert_eq!(terms("^abc$")[0][0].typ, TermType::Equal);
540        assert_eq!(terms("'abc'")[0][0].typ, TermType::ExactBoundary);
541        // `!` alone is an exact inverse; `!'` is a FUZZY inverse.
542        assert!(terms("!abc")[0][0].inv);
543        assert_eq!(terms("!abc")[0][0].typ, TermType::Exact);
544        assert_eq!(terms("!'abc")[0][0].typ, TermType::Fuzzy);
545        assert_eq!(terms("!^abc")[0][0].typ, TermType::Prefix);
546        // A lone `$` is a term, not a suffix marker.
547        assert_eq!(terms("$")[0][0].typ, TermType::Fuzzy);
548    }
549
550    #[test]
551    fn inverse_term_rejects_only_what_it_matches() {
552        let p = Pattern::build("!log", false, true, Case::Smart);
553        assert!(p.score("main.rs").is_some());
554        assert!(p.score("main.log").is_none());
555        // Only inverse terms → fzf keeps input order rather than ranking.
556        assert!(!p.sortable);
557        assert!(!p.cacheable);
558    }
559
560    #[test]
561    fn prefix_and_suffix_anchor() {
562        let p = Pattern::build("^src", false, true, Case::Smart);
563        assert!(p.score("src/main.rs").is_some());
564        assert!(p.score("lib/src/main.rs").is_none());
565        let p = Pattern::build("rs$", false, true, Case::Smart);
566        assert!(p.score("src/main.rs").is_some());
567        assert!(p.score("src/main.rs.bak").is_none());
568    }
569
570    #[test]
571    fn equal_matches_the_whole_line_only() {
572        let p = Pattern::build("^main.rs$", false, true, Case::Smart);
573        assert!(p.score("main.rs").is_some());
574        assert!(p.score("  main.rs  ").is_some()); // surrounding space is trimmed
575        assert!(p.score("src/main.rs").is_none());
576    }
577
578    #[test]
579    fn escaped_space_stays_in_the_term() {
580        let p = Pattern::build("my\\ file", false, true, Case::Smart);
581        assert_eq!(p.term_sets.len(), 1);
582        assert_eq!(p.term_sets[0][0].text.iter().collect::<String>(), "my file");
583    }
584
585    #[test]
586    fn cacheable_only_for_plain_and_terms() {
587        // Plain terms can only narrow as the query grows — the picker's
588        // incremental re-filter depends on this being right.
589        assert!(Pattern::build("abc", false, true, Case::Smart).cacheable);
590        assert!(Pattern::build("abc def", false, true, Case::Smart).cacheable);
591        assert!(!Pattern::build("abc | def", false, true, Case::Smart).cacheable);
592        assert!(!Pattern::build("!abc", false, true, Case::Smart).cacheable);
593        assert!(!Pattern::build("^abc", false, true, Case::Smart).cacheable);
594        assert!(!Pattern::build("'abc", false, true, Case::Smart).cacheable);
595    }
596
597    #[test]
598    fn non_extended_treats_the_query_as_one_term() {
599        let p = Pattern::build("usr bin", false, false, Case::Smart);
600        assert!(p.term_sets.is_empty());
601        // The space is part of the pattern, so it must appear in the line.
602        assert!(p.score("usr x bin").is_some());
603        assert!(p.score("/usr/local/bin").is_none());
604    }
605
606    #[test]
607    fn smart_case_is_per_term() {
608        let p = Pattern::build("readme Cargo", false, true, Case::Smart);
609        assert!(!p.term_sets[0][0].case_sensitive);
610        assert!(p.term_sets[1][0].case_sensitive);
611        assert!(p.score("README / Cargo.toml").is_some());
612        assert!(p.score("README / cargo.toml").is_none());
613    }
614
615    #[test]
616    fn empty_query_matches_everything() {
617        let p = Pattern::build("", false, true, Case::Smart);
618        assert!(p.is_empty());
619        assert_eq!(p.score("anything"), Some(0));
620    }
621}
622
623/// Where a pattern matched a line, folded across every term set — fzf's
624/// `buildResult` inputs (result.go:32). `min_begin`/`min_end`/`max_end` are
625/// character indices; a term that located nothing (a satisfied `!term`)
626/// contributes an empty offset and is skipped.
627#[derive(Clone, Copy, Debug, PartialEq, Eq)]
628pub struct Bounds {
629    pub score: i32,
630    pub min_begin: usize,
631    pub min_end: usize,
632    pub max_end: usize,
633    /// False when nothing located a position — every position-based criterion
634    /// then scores the worst possible value, as in fzf.
635    pub valid: bool,
636}
637
638impl Bounds {
639    fn empty(score: i32) -> Bounds {
640        Bounds {
641            score,
642            min_begin: u16::MAX as usize,
643            min_end: u16::MAX as usize,
644            max_end: 0,
645            valid: false,
646        }
647    }
648    fn add(&mut self, begin: usize, end: usize) {
649        if begin >= end {
650            return;
651        }
652        self.min_begin = self.min_begin.min(begin);
653        self.min_end = self.min_end.min(end);
654        self.max_end = self.max_end.max(end);
655        self.valid = true;
656    }
657}
658
659/// One ranking criterion — fzf's `criterion` (options.go:268). `Score` is
660/// always first; the rest are the `--tiebreak` list, applied in order, with the
661/// item's input index as the final, implicit tiebreak.
662#[derive(Clone, Copy, Debug, PartialEq, Eq)]
663pub enum Criterion {
664    Score,
665    Chunk,
666    Length,
667    Begin,
668    End,
669    Pathname,
670}
671
672/// fzf's `parseTiebreak` (options.go:1349). `index` adds no criterion — it IS
673/// the implicit final one — but it must come last, and no name may repeat.
674/// `None` for a spec fzf would reject, which keeps the caller's default.
675pub fn parse_tiebreak(spec: &str) -> Option<Vec<Criterion>> {
676    let lowered = spec.to_lowercase();
677    let mut out = vec![Criterion::Score];
678    let mut seen: Vec<&str> = Vec::new();
679    let mut has_index = false;
680    for name in lowered.split(',') {
681        // A repeat is an error, and `index` must be last — it is the implicit
682        // final criterion, so nothing may follow it.
683        if seen.contains(&name) || has_index {
684            return None;
685        }
686        seen.push(name);
687        match name {
688            "index" => has_index = true,
689            "chunk" => out.push(Criterion::Chunk),
690            "pathname" => out.push(Criterion::Pathname),
691            "length" => out.push(Criterion::Length),
692            "begin" => out.push(Criterion::Begin),
693            "end" => out.push(Criterion::End),
694            _ => return None,
695        }
696    }
697    // fzf's points vector is four slots wide: score plus at most three tiebreaks.
698    match out.len() > 4 {
699        true => None,
700        false => Some(out),
701    }
702}
703
704/// The criteria a `--scheme` implies when `--tiebreak` is not given — fzf's
705/// `parseScheme` (options.go:1336).
706pub fn scheme_criteria(scheme: &crate::algo::Scheme) -> Vec<Criterion> {
707    if *scheme == crate::algo::Scheme::PATH {
708        return vec![Criterion::Score, Criterion::Pathname, Criterion::Length];
709    }
710    if *scheme == crate::algo::Scheme::HISTORY {
711        return vec![Criterion::Score];
712    }
713    vec![Criterion::Score, Criterion::Length]
714}
715
716/// fzf's `buildResultFromBounds` (result.go:54): pack the criteria into four
717/// `u16` slots, best-first, so ordering is one integer comparison per pair.
718///
719/// The slots fill from the END (`points[3 - idx]`), which is what makes the
720/// packed comparison in [`compare_points`] read criteria in declaration order.
721/// `item` is the WHOLE line and `key` is what the query matched against — the
722/// two differ under `--nth`. fzf measures `length` on the item (`item.TrimLength`,
723/// result.go:81) while the match offsets are relative to the matched token, so
724/// each criterion has to be told which of the two it is about.
725pub fn points(item: &str, key: &str, b: &Bounds, criteria: &[Criterion]) -> [u16; 4] {
726    // Only `chunk`, `begin` and `end` index the line by character, and this runs
727    // once per MATCHING line — so decoding every line up front would spend an
728    // allocation per hit for the default criteria, which never look at it.
729    let needs_chars = criteria
730        .iter()
731        .any(|c| matches!(c, Criterion::Chunk | Criterion::Begin | Criterion::End));
732    let text: Vec<char> = match needs_chars {
733        true => key.chars().collect(),
734        false => Vec::new(),
735    };
736    let num_chars = text.len();
737    let as_u16 = |v: i64| v.clamp(0, u16::MAX as i64) as u16;
738    let mut pts = [0u16; 4];
739    for (idx, criterion) in criteria.iter().enumerate().take(4) {
740        let val = match criterion {
741            // Higher score sorts first, so it is stored inverted.
742            Criterion::Score => u16::MAX - as_u16(b.score as i64),
743            Criterion::Chunk if b.valid => {
744                // Widen the match to the whitespace-delimited chunk holding it;
745                // the shorter that chunk, the better the match fits.
746                let mut s = b.min_begin;
747                while s >= 1 && !text[s - 1].is_whitespace() {
748                    s -= 1;
749                }
750                let mut e = b.max_end;
751                while e < num_chars && !text[e].is_whitespace() {
752                    e += 1;
753                }
754                as_u16((e - s) as i64)
755            }
756            // The ITEM, not the matched field: a `--nth` projection narrows what
757            // the query sees, not how long the line is.
758            Criterion::Length => as_u16(trim_length(item) as i64),
759            Criterion::Pathname if b.valid => {
760                // Prefer a match in the last path segment. fzf scans BYTES here
761                // while `min_begin` counts characters; the two agree on the
762                // ASCII paths this criterion exists for, and the port keeps the
763                // comparison as fzf makes it.
764                let bytes = key.as_bytes();
765                let last_delim = bytes
766                    .iter()
767                    .rposition(|c| *c == b'/' || *c == b'\\')
768                    .map(|i| i as i64)
769                    .unwrap_or(-1);
770                match last_delim <= b.min_begin as i64 {
771                    true => as_u16(b.min_begin as i64 - last_delim),
772                    false => u16::MAX,
773                }
774            }
775            Criterion::Begin | Criterion::End if b.valid => {
776                let mut white_prefix = 0usize;
777                for (i, r) in text.iter().enumerate() {
778                    white_prefix = i;
779                    if i == b.min_begin || !r.is_whitespace() {
780                        break;
781                    }
782                }
783                let trim = trim_length(key) as i64;
784                match criterion {
785                    // Earlier match first.
786                    Criterion::Begin => as_u16(b.min_end as i64 - white_prefix as i64),
787                    // Later END first — the match reaching further into the line
788                    // is the better one, normalized by the line's own length.
789                    _ => as_u16(
790                        u16::MAX as i64
791                            - (u16::MAX as i64 * (b.max_end as i64 - white_prefix as i64))
792                                / (trim + 1),
793                    ),
794                }
795            }
796            // A criterion with nothing to measure scores the worst value.
797            _ => u16::MAX,
798        };
799        pts[3 - idx] = val;
800    }
801    pts
802}
803
804/// fzf's `compareRanks` (result_x86.go): the four slots read as one integer,
805/// most significant first, then the item's input index breaks a full tie.
806pub fn compare_points(a: &[u16; 4], b: &[u16; 4]) -> std::cmp::Ordering {
807    for i in (0..4).rev() {
808        match a[i].cmp(&b[i]) {
809            std::cmp::Ordering::Equal => continue,
810            other => return other,
811        }
812    }
813    std::cmp::Ordering::Equal
814}
815
816/// The length fzf's `length` criterion compares — `Chars.TrimLength`, the
817/// character count with surrounding whitespace removed.
818fn trim_length(s: &str) -> usize {
819    s.trim().chars().count()
820}
821
822/// fzf's `core.go:215`: the `--tiebreak` criteria decide how the matchers scan.
823/// Returns `(forward, with_pos)`.
824///
825/// `end` and `pathname` want the LAST best match rather than the first, so they
826/// scan backwards. `chunk` and `pathname` rank by WHERE the match begins, and
827/// the begin offset is only accurate when the matcher backtracks — fzf skips
828/// that work otherwise, and says so at the bottom of `FuzzyMatchV2`.
829///
830/// The walk starts at the LAST criterion, so an earlier one wins a conflict.
831/// `Score` (always first) is skipped, as in fzf.
832pub fn scan_direction(criteria: &[Criterion]) -> (bool, bool) {
833    let mut forward = true;
834    let mut with_pos = false;
835    for c in criteria.iter().skip(1).rev() {
836        match c {
837            Criterion::Chunk => with_pos = true,
838            Criterion::End => forward = false,
839            Criterion::Begin => forward = true,
840            Criterion::Pathname => {
841                with_pos = true;
842                forward = false;
843            }
844            _ => {}
845        }
846    }
847    (forward, with_pos)
848}