#[derive(Debug, Clone, PartialEq, Eq)]
pub struct FuzzyMatch {
pub score: i32,
pub positions: Vec<usize>,
}
const WORD_START_BONUS: i32 = 12;
const CONSECUTIVE_BONUS: i32 = 8;
const FIRST_CHARACTER_BONUS: i32 = 10;
const EXACT_CASE_BONUS: i32 = 2;
const SKIP_PENALTY: i32 = 1;
const MATCH_SCORE: i32 = 6;
pub fn fuzzy_match(query: &str, candidate: &str) -> Option<FuzzyMatch> {
if query.trim().is_empty() {
return Some(FuzzyMatch {
score: 0,
positions: Vec::new(),
});
}
let query_chars: Vec<char> = query.chars().filter(|c| !c.is_whitespace()).collect();
if query_chars.is_empty() {
return Some(FuzzyMatch {
score: 0,
positions: Vec::new(),
});
}
let candidate_chars: Vec<(usize, char)> = candidate.char_indices().collect();
if query_chars.len() > candidate_chars.len() {
return None;
}
let mut positions = Vec::with_capacity(query_chars.len());
let mut score = 0i32;
let mut candidate_index = 0usize;
let mut previous_match: Option<usize> = None;
for wanted in query_chars {
let mut found = None;
for index in candidate_index..candidate_chars.len() {
let (offset, actual) = candidate_chars[index];
if !actual.eq_ignore_ascii_case(&wanted) {
continue;
}
let mut character_score = MATCH_SCORE;
if index == 0 {
character_score += FIRST_CHARACTER_BONUS;
} else {
let (_, previous) = candidate_chars[index - 1];
let after_separator = !previous.is_alphanumeric();
let camel_boundary = previous.is_lowercase() && actual.is_uppercase();
if after_separator || camel_boundary {
character_score += WORD_START_BONUS;
}
}
if previous_match.is_some_and(|previous| previous + 1 == index) {
character_score += CONSECUTIVE_BONUS;
}
if actual == wanted {
character_score += EXACT_CASE_BONUS;
}
let skipped = i32::try_from(index - candidate_index).unwrap_or(i32::MAX);
character_score -= skipped.saturating_mul(SKIP_PENALTY);
found = Some((index, offset, character_score));
break;
}
let (index, offset, character_score) = found?;
score += character_score;
positions.push(offset);
previous_match = Some(index);
candidate_index = index + 1;
}
let coverage = (positions.len() * 100 / candidate_chars.len().max(1)) as i32;
score += coverage / 10;
Some(FuzzyMatch { score, positions })
}
pub fn rank<'a, I>(query: &str, candidates: I) -> Vec<(usize, FuzzyMatch)>
where
I: IntoIterator<Item = &'a str>,
{
let mut matches: Vec<(usize, FuzzyMatch)> = candidates
.into_iter()
.enumerate()
.filter_map(|(index, candidate)| fuzzy_match(query, candidate).map(|found| (index, found)))
.collect();
matches.sort_by(|left, right| {
right
.1
.score
.cmp(&left.1.score)
.then_with(|| left.0.cmp(&right.0))
});
matches
}
#[cfg(test)]
mod tests {
use super::*;
use crate::command::Command;
fn score(query: &str, candidate: &str) -> Option<i32> {
fuzzy_match(query, candidate).map(|found| found.score)
}
#[test]
fn an_empty_query_matches_everything_equally() {
assert_eq!(score("", "anything"), Some(0));
assert_eq!(score(" ", "anything"), Some(0));
}
#[test]
fn an_exact_match_scores() {
assert!(score("run", "Run").is_some());
assert!(score("Run", "Run").unwrap() >= score("run", "Run").unwrap());
}
#[test]
fn a_subsequence_matches_and_a_non_subsequence_does_not() {
assert!(score("sov", "Step over").is_some());
assert!(score("vos", "Step over").is_none(), "order matters");
assert!(score("xyz", "Step over").is_none());
}
#[test]
fn a_query_longer_than_the_candidate_cannot_match() {
assert_eq!(score("stepping", "step"), None);
}
#[test]
fn word_starts_beat_letters_buried_mid_word() {
let initials = score("sa", "Save as").expect("matches");
let buried = score("sa", "Disassembly syntax").expect("matches");
assert!(
initials > buried,
"initials {initials} should beat buried {buried}"
);
}
#[test]
fn consecutive_characters_beat_scattered_ones() {
let consecutive = score("step", "Step over").expect("matches");
let scattered = score("step", "Set the pace").expect("matches");
assert!(
consecutive > scattered,
"consecutive {consecutive} should beat scattered {scattered}"
);
}
#[test]
fn matching_is_case_insensitive_but_exact_case_ranks_higher() {
assert!(score("STEP", "Step over").is_some());
let exact = score("Step", "Step over").expect("matches");
let inexact = score("step", "Step over").expect("matches");
assert!(exact > inexact);
}
#[test]
fn positions_point_at_the_matched_characters() {
let found = fuzzy_match("so", "Step over").expect("matches");
assert_eq!(found.positions.len(), 2);
let text = "Step over";
let matched: String = found
.positions
.iter()
.map(|offset| text[*offset..].chars().next().unwrap_or('?'))
.collect();
assert_eq!(matched.to_lowercase(), "so");
}
#[test]
fn positions_are_byte_offsets_valid_for_slicing() {
let candidate = "Ölçüm göster";
let found = fuzzy_match("gs", candidate).expect("matches");
for offset in found.positions {
assert!(
candidate.is_char_boundary(offset),
"offset {offset} is not a character boundary"
);
}
}
#[test]
fn ranking_puts_the_best_match_first() {
let candidates = ["Step out", "Step over", "Stop the program", "Save"];
let ranked = rank("sov", candidates);
assert_eq!(
ranked.first().map(|(index, _)| candidates[*index]),
Some("Step over")
);
}
#[test]
fn ranking_an_empty_query_preserves_the_original_order() {
let candidates = ["one", "two", "three"];
let ranked = rank("", candidates);
let order: Vec<usize> = ranked.iter().map(|(index, _)| *index).collect();
assert_eq!(order, vec![0, 1, 2]);
}
#[test]
fn ranking_drops_candidates_that_do_not_match() {
let ranked = rank("zzz", ["Step over", "Run", "Build"]);
assert!(ranked.is_empty());
}
#[test]
fn typing_a_command_identifier_finds_its_command() {
let commands = Command::all();
let texts: Vec<String> = commands.iter().map(Command::search_text).collect();
let ranked = rank("debug.step-over", texts.iter().map(String::as_str));
assert_eq!(
ranked.first().map(|(index, _)| commands[*index].id()),
Some("debug.step-over".to_owned())
);
}
#[test]
fn common_abbreviations_find_the_expected_command() {
let commands = Command::all();
let texts: Vec<String> = commands.iter().map(Command::search_text).collect();
for (query, expected) in [
("toggle break", "debug.toggle-breakpoint"),
("save as", "file.save-as"),
("syscall", "app.syscalls"),
("go to address", "navigate.go-to-address"),
("theme", "view.cycle-theme"),
] {
let ranked = rank(query, texts.iter().map(String::as_str));
let best = ranked
.first()
.map(|(index, _)| commands[*index].id())
.unwrap_or_default();
assert_eq!(best, expected, "query {query:?} found {best}");
}
}
#[test]
fn every_command_is_findable_by_its_own_title() {
let commands = Command::all();
let texts: Vec<String> = commands.iter().map(Command::search_text).collect();
for command in &commands {
let ranked = rank(&command.title(), texts.iter().map(String::as_str));
assert!(
ranked
.first()
.is_some_and(|(index, _)| commands[*index] == *command),
"{} was not the top hit for its own title",
command.id()
);
}
}
#[test]
fn scoring_a_long_query_against_a_long_candidate_terminates() {
let query = "a".repeat(500);
let candidate = "ab".repeat(500);
assert!(fuzzy_match(&query, &candidate).is_some());
assert!(fuzzy_match(&query, "short").is_none());
}
}