1use crate::algo::{self, Match, Text};
24use crate::fzf::Case;
25
26#[derive(Clone, Copy, PartialEq, Eq, Debug)]
28pub enum TermType {
29 Fuzzy,
30 Exact,
31 ExactBoundary,
32 Prefix,
33 Suffix,
34 Equal,
35}
36
37#[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 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#[derive(Clone, Debug)]
81pub struct Pattern {
82 fuzzy: bool,
85 extended: bool,
86 text: Vec<char>,
88 case_sensitive: bool,
89 term_sets: Vec<Vec<Term>>,
91 pub sortable: bool,
95 pub cacheable: bool,
101 pub scheme: crate::algo::Scheme,
105 forward: bool,
110 with_pos: bool,
111 algo_v1: bool,
113}
114
115impl Pattern {
116 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 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 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 #[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 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 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 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 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 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 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 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 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 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 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 if !matched {
411 return None;
412 }
413 total += current;
414 }
415 Some((total, all_pos))
416 }
417}
418
419fn 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 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 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 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 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 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()); 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 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 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#[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 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#[derive(Clone, Copy, Debug, PartialEq, Eq)]
663pub enum Criterion {
664 Score,
665 Chunk,
666 Length,
667 Begin,
668 End,
669 Pathname,
670}
671
672pub 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 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 match out.len() > 4 {
699 true => None,
700 false => Some(out),
701 }
702}
703
704pub 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
716pub fn points(item: &str, key: &str, b: &Bounds, criteria: &[Criterion]) -> [u16; 4] {
726 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 Criterion::Score => u16::MAX - as_u16(b.score as i64),
743 Criterion::Chunk if b.valid => {
744 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 Criterion::Length => as_u16(trim_length(item) as i64),
759 Criterion::Pathname if b.valid => {
760 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 Criterion::Begin => as_u16(b.min_end as i64 - white_prefix as i64),
787 _ => 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 _ => u16::MAX,
798 };
799 pts[3 - idx] = val;
800 }
801 pts
802}
803
804pub 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
816fn trim_length(s: &str) -> usize {
819 s.trim().chars().count()
820}
821
822pub 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}