const SCORE_MATCH: i16 = 16;
const SCORE_GAP_START: i16 = -3;
const SCORE_GAP_EXTENSION: i16 = -1;
const BONUS_BOUNDARY: i16 = SCORE_MATCH / 2;
const BONUS_NON_WORD: i16 = SCORE_MATCH / 2;
const BONUS_CAMEL123: i16 = BONUS_BOUNDARY + SCORE_GAP_EXTENSION;
const BONUS_CONSECUTIVE: i16 = -(SCORE_GAP_START + SCORE_GAP_EXTENSION);
const BONUS_FIRST_CHAR_MULTIPLIER: i16 = 2;
const WHITE_CHARS: &str = " \t\n\u{b}\u{c}\r\u{85}\u{a0}";
#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Debug)]
#[repr(u8)]
enum CharClass {
White = 0,
NonWord = 1,
Delimiter = 2,
Lower = 3,
Upper = 4,
Letter = 5,
Number = 6,
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct Scheme {
bonus_boundary_white: i16,
bonus_boundary_delimiter: i16,
delimiter_chars: &'static str,
initial_char_class: CharClass,
matrix: [[i16; 7]; 7],
}
impl Default for Scheme {
fn default() -> Self {
Scheme::DEFAULT
}
}
impl Scheme {
pub const DEFAULT: Scheme = Scheme::build(
BONUS_BOUNDARY + 2,
BONUS_BOUNDARY + 1,
"/,:;|",
CharClass::White,
);
pub const PATH: Scheme = Scheme::build(
BONUS_BOUNDARY,
BONUS_BOUNDARY + 1,
"/",
CharClass::Delimiter,
);
pub const HISTORY: Scheme =
Scheme::build(BONUS_BOUNDARY, BONUS_BOUNDARY, "/,:;|", CharClass::White);
pub fn by_name(name: &str) -> Option<Scheme> {
match name {
"default" => Some(Scheme::DEFAULT),
"path" => Some(Scheme::PATH),
"history" => Some(Scheme::HISTORY),
_ => None,
}
}
const fn build(
white: i16,
delimiter: i16,
delimiter_chars: &'static str,
initial: CharClass,
) -> Scheme {
const CLASSES: [CharClass; 7] = [
CharClass::White,
CharClass::NonWord,
CharClass::Delimiter,
CharClass::Lower,
CharClass::Upper,
CharClass::Letter,
CharClass::Number,
];
let mut m = [[0i16; 7]; 7];
let mut i = 0;
while i < 7 {
let mut j = 0;
while j < 7 {
m[i][j] = bonus_for(CLASSES[i], CLASSES[j], white, delimiter);
j += 1;
}
i += 1;
}
Scheme {
bonus_boundary_white: white,
bonus_boundary_delimiter: delimiter,
delimiter_chars,
initial_char_class: initial,
matrix: m,
}
}
fn boundary_white(&self) -> i16 {
self.bonus_boundary_white
}
fn char_class_of_ascii(&self, c: u8) -> CharClass {
if c.is_ascii_lowercase() {
CharClass::Lower
} else if c.is_ascii_uppercase() {
CharClass::Upper
} else if c.is_ascii_digit() {
CharClass::Number
} else if WHITE_CHARS.contains(c as char) {
CharClass::White
} else if self.delimiter_chars.contains(c as char) {
CharClass::Delimiter
} else {
CharClass::NonWord
}
}
fn char_class_of_non_ascii(&self, c: char) -> CharClass {
if c.is_lowercase() {
CharClass::Lower
} else if c.is_uppercase() {
CharClass::Upper
} else if c.is_numeric() {
CharClass::Number
} else if c.is_alphabetic() {
CharClass::Letter
} else if c.is_whitespace() {
CharClass::White
} else if self.delimiter_chars.contains(c) {
CharClass::Delimiter
} else {
CharClass::NonWord
}
}
fn char_class_of(&self, c: char) -> CharClass {
match c.is_ascii() {
true => self.char_class_of_ascii(c as u8),
false => self.char_class_of_non_ascii(c),
}
}
fn bonus_of(&self, prev: CharClass, class: CharClass) -> i16 {
self.matrix[prev as usize][class as usize]
}
}
const fn bonus_for(prev: CharClass, class: CharClass, white: i16, delimiter: i16) -> i16 {
if class as u8 >= CharClass::NonWord as u8 {
match prev {
CharClass::White => return white,
CharClass::Delimiter => return delimiter,
CharClass::NonWord => return BONUS_BOUNDARY,
_ => {}
}
}
if (matches!(prev, CharClass::Lower) && matches!(class, CharClass::Upper))
|| (!matches!(prev, CharClass::Number) && matches!(class, CharClass::Number))
{
return BONUS_CAMEL123;
}
match class {
CharClass::NonWord | CharClass::Delimiter => BONUS_NON_WORD,
CharClass::White => white,
_ => 0,
}
}
pub enum Text<'a> {
Ascii(&'a [u8]),
Runes(Vec<char>),
}
impl<'a> Text<'a> {
pub fn new(s: &'a str) -> Self {
match s.is_ascii() {
true => Text::Ascii(s.as_bytes()),
false => Text::Runes(s.chars().collect()),
}
}
fn len(&self) -> usize {
match self {
Text::Ascii(b) => b.len(),
Text::Runes(r) => r.len(),
}
}
fn get(&self, i: usize) -> char {
match self {
Text::Ascii(b) => b[i] as char,
Text::Runes(r) => r[i],
}
}
fn is_bytes(&self) -> bool {
matches!(self, Text::Ascii(_))
}
fn bytes(&self) -> &[u8] {
match self {
Text::Ascii(b) => b,
Text::Runes(_) => &[],
}
}
fn leading_whitespaces(&self) -> usize {
(0..self.len())
.take_while(|i| self.get(*i).is_whitespace())
.count()
}
fn trailing_whitespaces(&self) -> usize {
(0..self.len())
.take_while(|i| self.get(self.len() - 1 - *i).is_whitespace())
.count()
}
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Match {
pub start: usize,
pub end: usize,
pub score: i32,
}
fn try_skip(input: &[u8], case_sensitive: bool, b: u8, from: usize) -> Option<usize> {
let hay = &input[from..];
let hit = match !case_sensitive && b.is_ascii_lowercase() {
true => memchr::memchr2(b, b - 32, hay),
false => memchr::memchr(b, hay),
};
hit.map(|i| from + i)
}
fn ascii_fuzzy_index(
input: &Text,
pattern: &[char],
case_sensitive: bool,
) -> Option<(usize, usize)> {
if !input.is_bytes() {
return Some((0, input.len()));
}
if !pattern.iter().all(char::is_ascii) {
return None;
}
let bytes = input.bytes();
let (mut first_idx, mut idx, mut last_idx) = (0usize, 0usize, 0usize);
let mut b = 0u8;
for (pidx, pc) in pattern.iter().enumerate() {
b = *pc as u8;
idx = try_skip(bytes, case_sensitive, b, idx)?;
if pidx == 0 && idx > 0 {
first_idx = idx - 1;
}
last_idx = idx;
idx += 1;
}
let scope = &bytes[last_idx..];
if scope.len() > 1 {
let tail = &scope[1..];
let end = if !case_sensitive && b.is_ascii_lowercase() {
let up = b - 32;
tail.iter().rposition(|c| *c == b || *c == up)
} else {
tail.iter().rposition(|c| *c == b)
};
if let Some(end) = end {
return Some((first_idx, last_idx + 1 + end + 1));
}
}
Some((first_idx, last_idx + 1))
}
pub fn fuzzy_match_v2(
scheme: &Scheme,
case_sensitive: bool,
forward: bool,
input: &Text,
pattern: &[char],
with_pos: bool,
) -> Option<(Match, Option<Vec<usize>>)> {
let m = pattern.len();
if m == 0 {
return Some((
Match {
start: 0,
end: 0,
score: 0,
},
with_pos.then(Vec::new),
));
}
if m > input.len() {
return None;
}
let (min_idx, max_idx) = ascii_fuzzy_index(input, pattern, case_sensitive)?;
let n = max_idx - min_idx;
if n == 0 {
return None;
}
SCRATCH.with(|s| {
let s = &mut *s.borrow_mut();
s.resize(n, m);
let (h0, c0, b, f, t, hm, cm) = s.buffers();
fuzzy_match_v2_inner(
scheme,
case_sensitive,
forward,
input,
pattern,
with_pos,
min_idx,
n,
m,
h0,
c0,
b,
f,
t,
hm,
cm,
)
})
}
struct Scratch {
h0: Vec<i16>,
c0: Vec<i16>,
b: Vec<i16>,
f: Vec<usize>,
t: Vec<char>,
h: Vec<i16>,
c: Vec<i16>,
}
impl Scratch {
fn new() -> Self {
Scratch {
h0: Vec::new(),
c0: Vec::new(),
b: Vec::new(),
f: Vec::new(),
t: Vec::new(),
h: Vec::new(),
c: Vec::new(),
}
}
fn resize(&mut self, n: usize, m: usize) {
self.h0.clear();
self.h0.resize(n, 0);
self.c0.clear();
self.c0.resize(n, 0);
self.b.clear();
self.b.resize(n, 0);
self.f.clear();
self.f.resize(m, 0);
self.t.clear();
}
#[allow(clippy::type_complexity)]
fn buffers(
&mut self,
) -> (
&mut Vec<i16>,
&mut Vec<i16>,
&mut Vec<i16>,
&mut Vec<usize>,
&mut Vec<char>,
&mut Vec<i16>,
&mut Vec<i16>,
) {
(
&mut self.h0,
&mut self.c0,
&mut self.b,
&mut self.f,
&mut self.t,
&mut self.h,
&mut self.c,
)
}
}
thread_local! {
static SCRATCH: std::cell::RefCell<Scratch> = std::cell::RefCell::new(Scratch::new());
}
#[allow(clippy::too_many_arguments)]
fn fuzzy_match_v2_inner(
scheme: &Scheme,
case_sensitive: bool,
forward: bool,
input: &Text,
pattern: &[char],
with_pos: bool,
min_idx: usize,
n: usize,
m: usize,
h0: &mut [i16],
c0: &mut [i16],
b: &mut [i16],
f: &mut [usize],
t: &mut Vec<char>,
h: &mut Vec<i16>,
c: &mut Vec<i16>,
) -> Option<(Match, Option<Vec<usize>>)> {
t.extend((min_idx..min_idx + n).map(|i| input.get(i)));
let (mut max_score, mut max_score_pos) = (0i16, 0usize);
let (mut pidx, mut last_idx) = (0usize, 0usize);
let pchar0 = pattern[0];
let mut pchar = pattern[0];
let mut prev_h0 = 0i16;
let mut prev_class = scheme.initial_char_class;
let mut in_gap = false;
for off in 0..n {
let mut ch = t[off];
let class = if ch.is_ascii() {
let cl = scheme.char_class_of_ascii(ch as u8);
if !case_sensitive && cl == CharClass::Upper {
ch = ((ch as u8) + 32) as char;
t[off] = ch;
}
cl
} else {
let cl = scheme.char_class_of_non_ascii(ch);
if !case_sensitive && cl == CharClass::Upper {
ch = ch.to_lowercase().next().unwrap_or(ch);
}
t[off] = ch;
cl
};
let bonus = scheme.bonus_of(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_score_pos = off;
if forward && bonus >= BONUS_BOUNDARY {
break;
}
}
in_gap = false;
} else {
h0[off] = match in_gap {
true => (prev_h0 + SCORE_GAP_EXTENSION).max(0),
false => (prev_h0 + SCORE_GAP_START).max(0),
};
c0[off] = 0;
in_gap = true;
}
prev_h0 = h0[off];
}
if pidx != m {
return None;
}
if m == 1 {
let start = min_idx + max_score_pos;
return Some((
Match {
start,
end: start + 1,
score: max_score as i32,
},
with_pos.then(|| vec![start]),
));
}
let f0 = f[0];
let width = last_idx - f0 + 1;
h.clear();
h.resize(width * m, 0);
h[..width].copy_from_slice(&h0[f0..=last_idx]);
c.clear();
c.resize(width * m, 0);
c[..width].copy_from_slice(&c0[f0..=last_idx]);
for (off, &fv) 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 + fv - f0 - 1] = 0;
for (k, &ch) in t[fv..=last_idx].iter().enumerate() {
let col = k + fv;
let (mut s1, s2, mut consecutive) = (
0i16,
{
let left = h[row + fv - f0 - 1 + k];
match in_gap {
true => left + SCORE_GAP_EXTENSION,
false => left + SCORE_GAP_START,
}
},
0i16,
);
if pchar == ch {
s1 = h[row + fv - f0 - 1 - width + k] + SCORE_MATCH;
let mut bo = b[col];
consecutive = c[row + fv - f0 - 1 - width + k] + 1;
if consecutive > 1 {
let fb = b[col + 1 - consecutive as usize];
if bo >= BONUS_BOUNDARY && bo > fb {
consecutive = 1;
} else {
bo = bo.max(BONUS_CONSECUTIVE.max(fb));
}
}
if s1 + bo < s2 {
s1 += b[col];
consecutive = 0;
} else {
s1 += bo;
}
}
c[row + fv - f0 + k] = 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_score_pos = col;
}
h[row + fv - f0 + k] = score;
}
}
let mut pos = with_pos.then(|| Vec::with_capacity(m));
let mut j = f0;
if let Some(pos) = pos.as_mut() {
let mut i = m - 1;
j = max_score_pos;
let mut prefer_match = true;
loop {
let idx = i * width;
let j0 = j - f0;
let s = h[idx + j0];
let mut s1 = 0i16;
let mut s2 = 0i16;
if i > 0 && j >= f[i] {
s1 = h[idx - width + j0 - 1];
}
if j > f[i] {
s2 = h[idx + j0 - 1];
}
if s > s1 && (s > s2 || s == s2 && prefer_match) {
pos.push(j + min_idx);
if i == 0 {
break;
}
i -= 1;
}
prefer_match =
c[idx + j0] > 1 || idx + width + j0 + 1 < c.len() && c[idx + width + j0 + 1] > 0;
if j == 0 {
break;
}
j -= 1;
}
}
Some((
Match {
start: min_idx + j,
end: min_idx + max_score_pos + 1,
score: max_score as i32,
},
pos,
))
}
fn calculate_score(
scheme: &Scheme,
case_sensitive: bool,
text: &Text,
pattern: &[char],
sidx: usize,
eidx: usize,
with_pos: bool,
) -> (i32, Option<Vec<usize>>) {
let (mut pidx, mut score, mut in_gap, mut consecutive, mut first_bonus) =
(0usize, 0i32, false, 0i32, 0i16);
let mut pos = with_pos.then(|| Vec::with_capacity(pattern.len()));
let mut prev_class = scheme.initial_char_class;
if sidx > 0 {
prev_class = scheme.char_class_of(text.get(sidx - 1));
}
for idx in sidx..eidx {
let mut ch = text.get(idx);
let class = scheme.char_class_of(ch);
if !case_sensitive {
ch = ch.to_lowercase().next().unwrap_or(ch);
}
if pidx < pattern.len() && ch == pattern[pidx] {
if let Some(p) = pos.as_mut() {
p.push(idx);
}
score += SCORE_MATCH as i32;
let mut bonus = scheme.bonus_of(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) as i32
} else {
bonus as i32
};
in_gap = false;
consecutive += 1;
pidx += 1;
} else {
score += match in_gap {
true => SCORE_GAP_EXTENSION as i32,
false => SCORE_GAP_START as i32,
};
in_gap = true;
consecutive = 0;
first_bonus = 0;
}
prev_class = class;
}
(score, pos)
}
pub fn fuzzy_match_v1(
scheme: &Scheme,
case_sensitive: bool,
forward: bool,
input: &Text,
pattern: &[char],
with_pos: bool,
) -> Option<(Match, Option<Vec<usize>>)> {
if pattern.is_empty() {
return Some((
Match {
start: 0,
end: 0,
score: 0,
},
with_pos.then(Vec::new),
));
}
ascii_fuzzy_index(input, pattern, case_sensitive)?;
let len_runes = input.len();
let len_pattern = pattern.len();
let at = |i: usize, max: usize| -> usize {
match forward {
true => i,
false => max - i - 1,
}
};
let fold = |c: char| -> char {
match case_sensitive {
true => c,
false => c.to_lowercase().next().unwrap_or(c),
}
};
let mut pidx = 0usize;
let mut sidx: Option<usize> = None;
let mut eidx: Option<usize> = None;
for index in 0..len_runes {
let ch = fold(input.get(at(index, len_runes)));
if ch == pattern[at(pidx, len_pattern)] {
if sidx.is_none() {
sidx = Some(index);
}
pidx += 1;
if pidx == len_pattern {
eidx = Some(index + 1);
break;
}
}
}
let (mut sidx, eidx) = (sidx?, eidx?);
pidx -= 1;
for index in (sidx..eidx).rev() {
let tidx = at(index, len_runes);
let ch = fold(input.get(tidx));
if ch == pattern[at(pidx, len_pattern)] {
match pidx.checked_sub(1) {
Some(p) => pidx = p,
None => {
sidx = index;
break;
}
}
}
}
let (sidx, eidx) = match forward {
true => (sidx, eidx),
false => (len_runes - eidx, len_runes - sidx),
};
let (score, pos) =
calculate_score(scheme, case_sensitive, input, pattern, sidx, eidx, with_pos);
Some((
Match {
start: sidx,
end: eidx,
score,
},
pos,
))
}
pub fn exact_match_naive(
scheme: &Scheme,
case_sensitive: bool,
forward: bool,
input: &Text,
pattern: &[char],
with_pos: bool,
) -> Option<(Match, Option<Vec<usize>>)> {
exact_match(
scheme,
case_sensitive,
forward,
false,
input,
pattern,
with_pos,
)
}
pub fn exact_match_boundary(
scheme: &Scheme,
case_sensitive: bool,
forward: bool,
input: &Text,
pattern: &[char],
with_pos: bool,
) -> Option<(Match, Option<Vec<usize>>)> {
exact_match(
scheme,
case_sensitive,
forward,
true,
input,
pattern,
with_pos,
)
}
fn exact_match(
scheme: &Scheme,
case_sensitive: bool,
forward: bool,
boundary_check: bool,
input: &Text,
pattern: &[char],
with_pos: bool,
) -> Option<(Match, Option<Vec<usize>>)> {
if pattern.is_empty() {
return Some((
Match {
start: 0,
end: 0,
score: 0,
},
with_pos.then(Vec::new),
));
}
let len_runes = input.len();
let len_pattern = pattern.len();
if len_runes < len_pattern {
return None;
}
ascii_fuzzy_index(input, pattern, case_sensitive)?;
let mut pidx = 0usize;
let mut best_pos: Option<usize> = None;
let mut bonus = 0i16;
let mut bbonus = 0i16;
let mut best_bonus = -1i16;
let mut index: isize = 0;
let at = |i: isize, max: usize| -> usize {
match forward {
true => i as usize,
false => max - i as usize - 1,
}
};
while index < len_runes as isize {
let index_ = at(index, len_runes);
let mut ch = input.get(index_);
if !case_sensitive {
ch = ch.to_lowercase().next().unwrap_or(ch);
}
let pidx_ = at(pidx as isize, len_pattern);
let mut ok = ch == pattern[pidx_];
if ok {
if pidx_ == 0 {
bonus = bonus_at(scheme, input, index_);
}
if boundary_check {
if forward && pidx_ == 0 {
bbonus = bonus;
} else if !forward && pidx_ == len_pattern - 1 {
bbonus = match index_ < len_runes - 1 {
true => bonus_at(scheme, input, index_ + 1),
false => scheme.boundary_white(),
};
}
ok = bbonus >= BONUS_BOUNDARY;
if ok && pidx_ == 0 {
ok = index_ == 0
|| scheme.char_class_of(input.get(index_ - 1)) <= CharClass::Delimiter;
}
if ok && pidx_ == len_pattern - 1 {
ok = index_ == len_runes - 1
|| scheme.char_class_of(input.get(index_ + 1)) <= CharClass::Delimiter;
}
}
}
if ok {
pidx += 1;
if pidx == len_pattern {
if bonus > best_bonus {
best_pos = Some(index as usize);
best_bonus = bonus;
}
if bonus >= BONUS_BOUNDARY {
break;
}
index -= pidx as isize - 1;
pidx = 0;
bonus = 0;
}
} else {
index -= pidx as isize;
pidx = 0;
bonus = 0;
}
index += 1;
}
let best_pos = best_pos?;
let (sidx, eidx) = match forward {
true => (best_pos + 1 - len_pattern, best_pos + 1),
false => (
len_runes - (best_pos + 1),
len_runes - (best_pos + 1 - len_pattern),
),
};
let (score, pos) = match boundary_check {
true => {
let mut score = best_bonus as i32;
let mut deduct = (best_bonus - BONUS_BOUNDARY) as i32 + 1;
if sidx > 0 && input.get(sidx - 1) == '_' {
score -= deduct + 1;
deduct = 1;
}
if eidx < len_runes && input.get(eidx) == '_' {
score -= deduct;
}
score += SCORE_MATCH as i32 * len_pattern as i32
+ scheme.boundary_white() as i32 * (len_pattern as i32 + 1);
(score, with_pos.then(|| (sidx..eidx).collect()))
}
false => calculate_score(scheme, case_sensitive, input, pattern, sidx, eidx, with_pos),
};
Some((
Match {
start: sidx,
end: eidx,
score,
},
pos,
))
}
pub fn prefix_match(
scheme: &Scheme,
case_sensitive: bool,
_forward: bool,
input: &Text,
pattern: &[char],
with_pos: bool,
) -> Option<(Match, Option<Vec<usize>>)> {
if pattern.is_empty() {
return Some((
Match {
start: 0,
end: 0,
score: 0,
},
with_pos.then(Vec::new),
));
}
let trimmed = match pattern[0].is_whitespace() {
true => 0,
false => input.leading_whitespaces(),
};
if input.len() - trimmed < pattern.len() {
return None;
}
for (i, p) in pattern.iter().enumerate() {
let mut ch = input.get(trimmed + i);
if !case_sensitive {
ch = ch.to_lowercase().next().unwrap_or(ch);
}
if ch != *p {
return None;
}
}
let (sidx, eidx) = (trimmed, trimmed + pattern.len());
let (score, pos) =
calculate_score(scheme, case_sensitive, input, pattern, sidx, eidx, with_pos);
Some((
Match {
start: sidx,
end: eidx,
score,
},
pos,
))
}
pub fn suffix_match(
scheme: &Scheme,
case_sensitive: bool,
_forward: bool,
input: &Text,
pattern: &[char],
with_pos: bool,
) -> Option<(Match, Option<Vec<usize>>)> {
let len_runes = input.len();
let trim_trailing = match pattern.last() {
Some(c) => !c.is_whitespace(),
None => true,
};
let trimmed = match trim_trailing {
true => len_runes - input.trailing_whitespaces(),
false => len_runes,
};
if pattern.is_empty() {
return Some((
Match {
start: trimmed,
end: trimmed,
score: 0,
},
with_pos.then(Vec::new),
));
}
let diff = trimmed.checked_sub(pattern.len())?;
for (i, p) in pattern.iter().enumerate() {
let mut ch = input.get(i + diff);
if !case_sensitive {
ch = ch.to_lowercase().next().unwrap_or(ch);
}
if ch != *p {
return None;
}
}
let (sidx, eidx) = (trimmed - pattern.len(), trimmed);
let (score, pos) =
calculate_score(scheme, case_sensitive, input, pattern, sidx, eidx, with_pos);
Some((
Match {
start: sidx,
end: eidx,
score,
},
pos,
))
}
pub fn equal_match(
scheme: &Scheme,
case_sensitive: bool,
_forward: bool,
input: &Text,
pattern: &[char],
with_pos: bool,
) -> Option<(Match, Option<Vec<usize>>)> {
let len_pattern = pattern.len();
if len_pattern == 0 {
return None;
}
let trimmed_start = match pattern[0].is_whitespace() {
true => 0,
false => input.leading_whitespaces(),
};
let trimmed_end = match pattern[len_pattern - 1].is_whitespace() {
true => 0,
false => input.trailing_whitespaces(),
};
if input.len().checked_sub(trimmed_start + trimmed_end)? != len_pattern {
return None;
}
for (i, p) in pattern.iter().enumerate() {
let mut ch = input.get(trimmed_start + i);
if !case_sensitive {
ch = ch.to_lowercase().next().unwrap_or(ch);
}
if ch != *p {
return None;
}
}
let score = (SCORE_MATCH as i32 + scheme.boundary_white() as i32) * len_pattern as i32
+ (BONUS_FIRST_CHAR_MULTIPLIER as i32 - 1) * scheme.boundary_white() as i32;
Some((
Match {
start: trimmed_start,
end: trimmed_start + len_pattern,
score,
},
with_pos.then(|| (trimmed_start..trimmed_start + len_pattern).collect()),
))
}
fn bonus_at(scheme: &Scheme, input: &Text, idx: usize) -> i16 {
if idx == 0 {
return scheme.boundary_white();
}
scheme.bonus_of(
scheme.char_class_of(input.get(idx - 1)),
scheme.char_class_of(input.get(idx)),
)
}
pub fn prepare_pattern(pattern: &str) -> (Vec<char>, bool) {
prepare_pattern_case(pattern, crate::fzf::Case::Smart)
}
pub fn prepare_pattern_case(pattern: &str, case: crate::fzf::Case) -> (Vec<char>, bool) {
let case_sensitive = match case {
crate::fzf::Case::Smart => pattern.chars().any(char::is_uppercase),
crate::fzf::Case::Ignore => false,
crate::fzf::Case::Respect => true,
};
let chars = match case_sensitive {
true => pattern.chars().collect(),
false => pattern.chars().flat_map(char::to_lowercase).collect(),
};
(chars, case_sensitive)
}
#[cfg(test)]
mod tests {
use super::*;
fn score(text: &str, pat: &str) -> Option<i32> {
let (p, cs) = prepare_pattern(pat);
fuzzy_match_v2(&Scheme::DEFAULT, cs, true, &Text::new(text), &p, false)
.map(|(m, _)| m.score)
}
fn positions(text: &str, pat: &str) -> Option<Vec<usize>> {
let (p, cs) = prepare_pattern(pat);
fuzzy_match_v2(&Scheme::DEFAULT, cs, true, &Text::new(text), &p, true).map(|(_, pos)| {
let mut v = pos.unwrap();
v.sort_unstable();
v
})
}
#[test]
fn scores_match_fzfs_own_test_vectors() {
let p: Vec<char> = "obz".chars().collect();
let (m, _) = fuzzy_match_v2(
&Scheme::DEFAULT,
false,
true,
&Text::new("fooBarbaz1"),
&p,
true,
)
.unwrap();
assert_eq!((m.start, m.end), (2, 9));
assert_eq!(
m.score,
(SCORE_MATCH * 3 + BONUS_CAMEL123 + SCORE_GAP_START + SCORE_GAP_EXTENSION * 3) as i32
);
let (p, cs) = prepare_pattern("fbb");
let (m, _) = fuzzy_match_v2(
&Scheme::DEFAULT,
cs,
true,
&Text::new("foo bar baz"),
&p,
true,
)
.unwrap();
assert_eq!((m.start, m.end), (0, 9));
assert_eq!(
m.score,
(SCORE_MATCH * 3
+ Scheme::DEFAULT.boundary_white() * BONUS_FIRST_CHAR_MULTIPLIER
+ Scheme::DEFAULT.boundary_white() * 2
+ 2 * SCORE_GAP_START
+ 4 * SCORE_GAP_EXTENSION) as i32
);
}
#[test]
fn consecutive_chunks_beat_scattered_ones() {
assert!(score("foobar", "foob").unwrap() > score("foo-bar", "foob").unwrap());
assert!(score("foo/bar", "bar").unwrap() > score("foobar", "bar").unwrap());
}
#[test]
fn smart_case_and_non_matches() {
assert!(score("Foo Bar", "foo").is_some());
assert!(score("foo bar", "Foo").is_none()); assert!(score("foo", "bar").is_none());
assert!(score("ab", "abc").is_none()); }
#[test]
fn positions_cover_every_pattern_char() {
assert_eq!(positions("fooBarbaz", "oBz"), Some(vec![2, 3, 8]));
assert_eq!(positions("/usr/bin/env", "usbe"), Some(vec![1, 2, 5, 9]));
}
#[test]
fn exact_prefers_the_boundary_occurrence() {
let (p, cs) = prepare_pattern("bar");
let (m, _) = exact_match_naive(
&Scheme::DEFAULT,
cs,
true,
&Text::new("foobar bar"),
&p,
false,
)
.unwrap();
assert_eq!((m.start, m.end), (7, 10));
assert!(
exact_match_naive(&Scheme::DEFAULT, cs, true, &Text::new("br"), &p, false).is_none()
);
}
#[test]
fn non_ascii_lines_still_match() {
assert!(score("caffè latte", "cafez").is_none());
assert!(score("caffè latte", "cffl").is_some());
assert_eq!(positions("αβγ delta", "dl"), Some(vec![4, 6]));
}
}