use crate::algo::{self, Match, Text};
use crate::fzf::Case;
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub enum TermType {
Fuzzy,
Exact,
ExactBoundary,
Prefix,
Suffix,
Equal,
}
#[derive(Clone, Debug)]
pub struct Term {
pub typ: TermType,
pub inv: bool,
pub text: Vec<char>,
pub case_sensitive: bool,
}
impl Term {
fn run(
&self,
scheme: &crate::algo::Scheme,
forward: bool,
algo_v1: bool,
input: &Text,
with_pos: bool,
) -> Option<(Match, Option<Vec<usize>>)> {
let f = match self.typ {
TermType::Fuzzy => match algo_v1 {
true => algo::fuzzy_match_v1,
false => algo::fuzzy_match_v2,
},
TermType::Exact => algo::exact_match_naive,
TermType::ExactBoundary => algo::exact_match_boundary,
TermType::Prefix => algo::prefix_match,
TermType::Suffix => algo::suffix_match,
TermType::Equal => algo::equal_match,
};
f(
scheme,
self.case_sensitive,
forward,
input,
&self.text,
with_pos,
)
}
}
#[derive(Clone, Debug)]
pub struct Pattern {
fuzzy: bool,
extended: bool,
text: Vec<char>,
case_sensitive: bool,
term_sets: Vec<Vec<Term>>,
pub sortable: bool,
pub cacheable: bool,
pub scheme: crate::algo::Scheme,
forward: bool,
with_pos: bool,
algo_v1: bool,
}
impl Pattern {
pub fn build(query: &str, exact: bool, extended: bool, case: Case) -> Pattern {
Pattern::build_with(query, exact, extended, case, crate::algo::Scheme::DEFAULT)
}
pub fn build_with(
query: &str,
exact: bool,
extended: bool,
case: Case,
scheme: crate::algo::Scheme,
) -> Pattern {
Pattern::build_ranked(
query,
exact,
extended,
case,
scheme,
&scheme_criteria(&scheme),
)
}
pub fn build_ranked(
query: &str,
exact: bool,
extended: bool,
case: Case,
scheme: crate::algo::Scheme,
criteria: &[Criterion],
) -> Pattern {
Pattern::build_full(query, exact, extended, case, scheme, criteria, false)
}
#[allow(clippy::too_many_arguments)]
pub fn build_full(
query: &str,
exact: bool,
extended: bool,
case: Case,
scheme: crate::algo::Scheme,
criteria: &[Criterion],
algo_v1: bool,
) -> Pattern {
let (forward, with_pos) = scan_direction(criteria);
let fuzzy = !exact;
let as_string = match extended {
true => {
let mut s = query.trim_start_matches(' ');
while s.ends_with(' ') && !s.ends_with("\\ ") {
s = &s[..s.len() - 1];
}
s.to_string()
}
false => query.to_string(),
};
if !extended {
let lower = as_string.to_lowercase();
let case_sensitive = match case {
Case::Respect => true,
Case::Ignore => false,
Case::Smart => lower != as_string,
};
let text = match case_sensitive {
true => as_string.chars().collect(),
false => lower.chars().collect(),
};
return Pattern {
fuzzy,
extended,
text,
case_sensitive,
term_sets: Vec::new(),
sortable: true,
cacheable: true,
scheme,
forward,
with_pos,
algo_v1,
};
}
let term_sets = parse_terms(fuzzy, case, &as_string);
let mut sortable = false;
let mut cacheable = true;
for set in &term_sets {
for (idx, term) in set.iter().enumerate() {
if !term.inv {
sortable = true;
}
let plain = match fuzzy {
true => term.typ == TermType::Fuzzy,
false => term.typ == TermType::Exact,
};
if idx > 0 || term.inv || !plain {
cacheable = false;
}
}
}
Pattern {
fuzzy,
extended,
text: Vec::new(),
case_sensitive: true,
term_sets,
sortable,
cacheable,
scheme,
forward,
with_pos,
algo_v1,
}
}
pub fn is_empty(&self) -> bool {
match self.extended {
true => self.term_sets.is_empty(),
false => self.text.is_empty(),
}
}
pub fn score(&self, line: &str) -> Option<i32> {
if self.is_empty() {
return Some(0);
}
let text = Text::new(line);
match self.extended {
true => self.extended_match(&text, false).map(|(s, _)| s),
false => self.basic_match(&text, false).map(|(m, _)| m.score),
}
}
pub fn positions(&self, line: &str) -> Vec<usize> {
if self.is_empty() {
return Vec::new();
}
let text = Text::new(line);
let mut pos = match self.extended {
true => self.extended_match(&text, true).and_then(|(_, p)| p),
false => self.basic_match(&text, true).and_then(|(_, p)| p),
}
.unwrap_or_default();
pos.sort_unstable();
pos.dedup();
pos
}
pub fn match_line(&self, line: &str) -> Option<Bounds> {
if self.is_empty() {
return Some(Bounds::empty(0));
}
let text = Text::new(line);
match self.extended {
true => self.extended_bounds(&text),
false => self.basic_match(&text, self.with_pos).map(|(m, _)| {
let mut b = Bounds::empty(m.score);
b.add(m.start, m.end);
b
}),
}
}
fn basic_match(&self, text: &Text, with_pos: bool) -> Option<(Match, Option<Vec<usize>>)> {
match self.fuzzy {
true if self.algo_v1 => algo::fuzzy_match_v1(
&self.scheme,
self.case_sensitive,
self.forward,
text,
&self.text,
with_pos,
),
true => algo::fuzzy_match_v2(
&self.scheme,
self.case_sensitive,
self.forward,
text,
&self.text,
with_pos,
),
false => algo::exact_match_naive(
&self.scheme,
self.case_sensitive,
self.forward,
text,
&self.text,
with_pos,
),
}
}
fn extended_bounds(&self, text: &Text) -> Option<Bounds> {
let mut bounds = Bounds::empty(0);
for set in &self.term_sets {
let mut matched = false;
let mut current = 0i32;
let mut offset = (0usize, 0usize);
for term in set {
match term.run(
&self.scheme,
self.forward,
self.algo_v1,
text,
self.with_pos,
) {
Some((m, _)) => {
if term.inv {
continue;
}
current = m.score;
offset = (m.start, m.end);
matched = true;
break;
}
None if term.inv => {
current = 0;
offset = (0, 0);
matched = true;
continue;
}
None => {}
}
}
if !matched {
return None;
}
bounds.score += current;
bounds.add(offset.0, offset.1);
}
Some(bounds)
}
fn extended_match(&self, text: &Text, with_pos: bool) -> Option<(i32, Option<Vec<usize>>)> {
let mut total = 0i32;
let mut all_pos = with_pos.then(Vec::new);
for set in &self.term_sets {
let mut matched = false;
let mut current = 0i32;
for term in set {
match term.run(&self.scheme, self.forward, self.algo_v1, text, with_pos) {
Some((m, pos)) => {
if term.inv {
continue;
}
current = m.score;
matched = true;
if let Some(all) = all_pos.as_mut() {
match pos {
Some(p) => all.extend(p),
None => all.extend(m.start..m.end),
}
}
break;
}
None if term.inv => {
current = 0;
matched = true;
continue;
}
None => {}
}
}
if !matched {
return None;
}
total += current;
}
Some((total, all_pos))
}
}
fn parse_terms(fuzzy: bool, case: Case, query: &str) -> Vec<Vec<Term>> {
let escaped = query.replace("\\ ", "\t");
let mut sets: Vec<Vec<Term>> = Vec::new();
let mut set: Vec<Term> = Vec::new();
let mut switch_set = false;
let mut after_bar = false;
for token in escaped.split(' ').filter(|t| !t.is_empty()) {
let mut typ = TermType::Fuzzy;
let mut inv = false;
let mut text = token.replace('\t', " ");
let lower = text.to_lowercase();
let case_sensitive = match case {
Case::Respect => true,
Case::Ignore => false,
Case::Smart => text != lower,
};
if !case_sensitive {
text = lower;
}
if !fuzzy {
typ = TermType::Exact;
}
if !set.is_empty() && !after_bar && text == "|" {
switch_set = false;
after_bar = true;
continue;
}
after_bar = false;
if let Some(rest) = text.strip_prefix('!') {
inv = true;
typ = TermType::Exact;
text = rest.to_string();
}
if text != "$" {
if let Some(rest) = text.strip_suffix('$') {
typ = TermType::Suffix;
text = rest.to_string();
}
}
if text.len() > 2 && text.starts_with('\'') && text.ends_with('\'') {
typ = TermType::ExactBoundary;
text = text[1..text.len() - 1].to_string();
} else if let Some(rest) = text.strip_prefix('\'') {
typ = match fuzzy && !inv {
true => TermType::Exact,
false => TermType::Fuzzy,
};
text = rest.to_string();
} else if let Some(rest) = text.strip_prefix('^') {
typ = match typ == TermType::Suffix {
true => TermType::Equal,
false => TermType::Prefix,
};
text = rest.to_string();
}
if text.is_empty() {
continue;
}
if switch_set {
sets.push(std::mem::take(&mut set));
}
set.push(Term {
typ,
inv,
text: text.chars().collect(),
case_sensitive,
});
switch_set = true;
}
if !set.is_empty() {
sets.push(set);
}
sets
}
#[cfg(test)]
mod tests {
use super::*;
fn terms(query: &str) -> Vec<Vec<Term>> {
parse_terms(true, Case::Smart, query)
}
#[test]
fn space_separated_terms_are_anded() {
let p = Pattern::build("usr bin", false, true, Case::Smart);
assert_eq!(p.term_sets.len(), 2);
assert!(p.score("/usr/local/bin").is_some());
assert!(p.score("/usr/local/lib").is_none());
assert!(p.score("/opt/bin").is_none());
}
#[test]
fn bar_makes_an_or_set() {
let p = Pattern::build("^/usr | ^/opt", false, true, Case::Smart);
assert_eq!(p.term_sets.len(), 1);
assert_eq!(p.term_sets[0].len(), 2);
assert!(p.score("/usr/bin").is_some());
assert!(p.score("/opt/bin").is_some());
assert!(p.score("/var/bin").is_none());
}
#[test]
fn sigils_select_the_term_type() {
assert_eq!(terms("'abc")[0][0].typ, TermType::Exact);
assert_eq!(terms("^abc")[0][0].typ, TermType::Prefix);
assert_eq!(terms("abc$")[0][0].typ, TermType::Suffix);
assert_eq!(terms("^abc$")[0][0].typ, TermType::Equal);
assert_eq!(terms("'abc'")[0][0].typ, TermType::ExactBoundary);
assert!(terms("!abc")[0][0].inv);
assert_eq!(terms("!abc")[0][0].typ, TermType::Exact);
assert_eq!(terms("!'abc")[0][0].typ, TermType::Fuzzy);
assert_eq!(terms("!^abc")[0][0].typ, TermType::Prefix);
assert_eq!(terms("$")[0][0].typ, TermType::Fuzzy);
}
#[test]
fn inverse_term_rejects_only_what_it_matches() {
let p = Pattern::build("!log", false, true, Case::Smart);
assert!(p.score("main.rs").is_some());
assert!(p.score("main.log").is_none());
assert!(!p.sortable);
assert!(!p.cacheable);
}
#[test]
fn prefix_and_suffix_anchor() {
let p = Pattern::build("^src", false, true, Case::Smart);
assert!(p.score("src/main.rs").is_some());
assert!(p.score("lib/src/main.rs").is_none());
let p = Pattern::build("rs$", false, true, Case::Smart);
assert!(p.score("src/main.rs").is_some());
assert!(p.score("src/main.rs.bak").is_none());
}
#[test]
fn equal_matches_the_whole_line_only() {
let p = Pattern::build("^main.rs$", false, true, Case::Smart);
assert!(p.score("main.rs").is_some());
assert!(p.score(" main.rs ").is_some()); assert!(p.score("src/main.rs").is_none());
}
#[test]
fn escaped_space_stays_in_the_term() {
let p = Pattern::build("my\\ file", false, true, Case::Smart);
assert_eq!(p.term_sets.len(), 1);
assert_eq!(p.term_sets[0][0].text.iter().collect::<String>(), "my file");
}
#[test]
fn cacheable_only_for_plain_and_terms() {
assert!(Pattern::build("abc", false, true, Case::Smart).cacheable);
assert!(Pattern::build("abc def", false, true, Case::Smart).cacheable);
assert!(!Pattern::build("abc | def", false, true, Case::Smart).cacheable);
assert!(!Pattern::build("!abc", false, true, Case::Smart).cacheable);
assert!(!Pattern::build("^abc", false, true, Case::Smart).cacheable);
assert!(!Pattern::build("'abc", false, true, Case::Smart).cacheable);
}
#[test]
fn non_extended_treats_the_query_as_one_term() {
let p = Pattern::build("usr bin", false, false, Case::Smart);
assert!(p.term_sets.is_empty());
assert!(p.score("usr x bin").is_some());
assert!(p.score("/usr/local/bin").is_none());
}
#[test]
fn smart_case_is_per_term() {
let p = Pattern::build("readme Cargo", false, true, Case::Smart);
assert!(!p.term_sets[0][0].case_sensitive);
assert!(p.term_sets[1][0].case_sensitive);
assert!(p.score("README / Cargo.toml").is_some());
assert!(p.score("README / cargo.toml").is_none());
}
#[test]
fn empty_query_matches_everything() {
let p = Pattern::build("", false, true, Case::Smart);
assert!(p.is_empty());
assert_eq!(p.score("anything"), Some(0));
}
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct Bounds {
pub score: i32,
pub min_begin: usize,
pub min_end: usize,
pub max_end: usize,
pub valid: bool,
}
impl Bounds {
fn empty(score: i32) -> Bounds {
Bounds {
score,
min_begin: u16::MAX as usize,
min_end: u16::MAX as usize,
max_end: 0,
valid: false,
}
}
fn add(&mut self, begin: usize, end: usize) {
if begin >= end {
return;
}
self.min_begin = self.min_begin.min(begin);
self.min_end = self.min_end.min(end);
self.max_end = self.max_end.max(end);
self.valid = true;
}
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Criterion {
Score,
Chunk,
Length,
Begin,
End,
Pathname,
}
pub fn parse_tiebreak(spec: &str) -> Option<Vec<Criterion>> {
let lowered = spec.to_lowercase();
let mut out = vec![Criterion::Score];
let mut seen: Vec<&str> = Vec::new();
let mut has_index = false;
for name in lowered.split(',') {
if seen.contains(&name) || has_index {
return None;
}
seen.push(name);
match name {
"index" => has_index = true,
"chunk" => out.push(Criterion::Chunk),
"pathname" => out.push(Criterion::Pathname),
"length" => out.push(Criterion::Length),
"begin" => out.push(Criterion::Begin),
"end" => out.push(Criterion::End),
_ => return None,
}
}
match out.len() > 4 {
true => None,
false => Some(out),
}
}
pub fn scheme_criteria(scheme: &crate::algo::Scheme) -> Vec<Criterion> {
if *scheme == crate::algo::Scheme::PATH {
return vec![Criterion::Score, Criterion::Pathname, Criterion::Length];
}
if *scheme == crate::algo::Scheme::HISTORY {
return vec![Criterion::Score];
}
vec![Criterion::Score, Criterion::Length]
}
pub fn points(item: &str, key: &str, b: &Bounds, criteria: &[Criterion]) -> [u16; 4] {
let needs_chars = criteria
.iter()
.any(|c| matches!(c, Criterion::Chunk | Criterion::Begin | Criterion::End));
let text: Vec<char> = match needs_chars {
true => key.chars().collect(),
false => Vec::new(),
};
let num_chars = text.len();
let as_u16 = |v: i64| v.clamp(0, u16::MAX as i64) as u16;
let mut pts = [0u16; 4];
for (idx, criterion) in criteria.iter().enumerate().take(4) {
let val = match criterion {
Criterion::Score => u16::MAX - as_u16(b.score as i64),
Criterion::Chunk if b.valid => {
let mut s = b.min_begin;
while s >= 1 && !text[s - 1].is_whitespace() {
s -= 1;
}
let mut e = b.max_end;
while e < num_chars && !text[e].is_whitespace() {
e += 1;
}
as_u16((e - s) as i64)
}
Criterion::Length => as_u16(trim_length(item) as i64),
Criterion::Pathname if b.valid => {
let bytes = key.as_bytes();
let last_delim = bytes
.iter()
.rposition(|c| *c == b'/' || *c == b'\\')
.map(|i| i as i64)
.unwrap_or(-1);
match last_delim <= b.min_begin as i64 {
true => as_u16(b.min_begin as i64 - last_delim),
false => u16::MAX,
}
}
Criterion::Begin | Criterion::End if b.valid => {
let mut white_prefix = 0usize;
for (i, r) in text.iter().enumerate() {
white_prefix = i;
if i == b.min_begin || !r.is_whitespace() {
break;
}
}
let trim = trim_length(key) as i64;
match criterion {
Criterion::Begin => as_u16(b.min_end as i64 - white_prefix as i64),
_ => as_u16(
u16::MAX as i64
- (u16::MAX as i64 * (b.max_end as i64 - white_prefix as i64))
/ (trim + 1),
),
}
}
_ => u16::MAX,
};
pts[3 - idx] = val;
}
pts
}
pub fn compare_points(a: &[u16; 4], b: &[u16; 4]) -> std::cmp::Ordering {
for i in (0..4).rev() {
match a[i].cmp(&b[i]) {
std::cmp::Ordering::Equal => continue,
other => return other,
}
}
std::cmp::Ordering::Equal
}
fn trim_length(s: &str) -> usize {
s.trim().chars().count()
}
pub fn scan_direction(criteria: &[Criterion]) -> (bool, bool) {
let mut forward = true;
let mut with_pos = false;
for c in criteria.iter().skip(1).rev() {
match c {
Criterion::Chunk => with_pos = true,
Criterion::End => forward = false,
Criterion::Begin => forward = true,
Criterion::Pathname => {
with_pos = true;
forward = false;
}
_ => {}
}
}
(forward, with_pos)
}