pub type Quality = i32;
pub const NONE: Quality = -1;
pub const WHOLE: Quality = 0;
pub const PREFIX: Quality = 100;
pub const WORD_START: Quality = 60;
pub const WORD_PREFIX: Quality = 40;
pub const SUBSEQUENCE: Quality = 10;
pub fn quality(candidate: &str, typed: &str) -> Quality {
if typed.is_empty() {
return WHOLE;
}
if candidate.len() < typed.len() {
return NONE;
}
let candidate = candidate.as_bytes();
let typed = typed.as_bytes();
if starts_with_folded(candidate, typed) {
return PREFIX;
}
match word_quality(candidate, typed) {
Some(quality) => quality,
None if is_subsequence(candidate, typed) => SUBSEQUENCE,
None => NONE,
}
}
fn starts_with_folded(candidate: &[u8], typed: &[u8]) -> bool {
candidate
.get(..typed.len())
.is_some_and(|head| head.eq_ignore_ascii_case(typed))
}
fn is_subsequence(candidate: &[u8], typed: &[u8]) -> bool {
let mut wanted = typed.iter();
let mut next = wanted.next();
for have in candidate {
let Some(want) = next else { return true };
if have.to_ascii_lowercase() == *want {
next = wanted.next();
}
}
next.is_none()
}
fn word_quality(candidate: &[u8], typed: &[u8]) -> Option<Quality> {
let first_word = (0..candidate.len()).find(|index| begins_a_word(candidate, *index))?;
let starts_the_name = candidate
.get(first_word)
.is_some_and(|have| have.to_ascii_lowercase() == typed[0]);
if every_character_begins_a_word(candidate, typed, false) {
return Some(if starts_the_name {
WORD_START
} else {
WORD_PREFIX
});
}
if starts_the_name && one_continuation_allowed(candidate, typed) {
return Some(WORD_START);
}
None
}
fn one_continuation_allowed(candidate: &[u8], typed: &[u8]) -> bool {
let mut at = 0usize;
let mut continuations = 0usize;
let last = typed.len().saturating_sub(1);
for (position, wanted) in typed.iter().enumerate() {
match next_at_a_word_start(candidate, *wanted, at) {
Some(found) => at = found + 1,
None => {
if position == 0 || position > last {
return false;
}
let Some(follows) = candidate.get(at) else {
return false;
};
if follows.to_ascii_lowercase() != *wanted {
return false;
}
continuations += 1;
at += 1;
}
}
}
continuations == 1
}
fn next_at_a_word_start(candidate: &[u8], wanted: u8, from: usize) -> Option<usize> {
(from..candidate.len()).find(|index| {
candidate[*index].to_ascii_lowercase() == wanted && begins_a_word(candidate, *index)
})
}
fn every_character_begins_a_word(candidate: &[u8], typed: &[u8], last_is_free: bool) -> bool {
let Some((last, leading)) = typed.split_last() else {
return false;
};
let mut at = 0usize;
for wanted in leading {
let Some(found) = next_at_a_word_start(candidate, *wanted, at) else {
return false;
};
at = found + 1;
}
match next_at_a_word_start(candidate, *last, at) {
Some(_) => true,
None if last_is_free => candidate
.get(at)
.is_some_and(|have| have.to_ascii_lowercase() == *last),
None => false,
}
}
fn begins_a_word(name: &[u8], index: usize) -> bool {
let Some(¤t) = name.get(index) else {
return false;
};
if index == 0 {
return current != b'_';
}
let previous = name[index - 1];
if previous == b'_' {
return current != b'_';
}
if current == b'_' {
return false;
}
if current.is_ascii_uppercase() {
return !previous.is_ascii_uppercase()
|| name.get(index + 1).is_some_and(u8::is_ascii_lowercase);
}
if current.is_ascii_digit() {
return !previous.is_ascii_digit();
}
previous.is_ascii_digit()
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn an_empty_prefix_matches_everything_equally() {
assert_eq!(quality("anything", ""), WHOLE);
assert_eq!(quality("", ""), WHOLE);
}
#[test]
fn a_literal_prefix_is_the_strongest_match() {
assert_eq!(quality("string", "str"), PREFIX);
assert_eq!(quality("string", "STRING"), PREFIX);
assert_eq!(quality("String", "str"), PREFIX);
const _: () = assert!(PREFIX > WORD_START);
}
#[test]
fn the_initials_of_underscored_words_match() {
assert!(
quality("basic_string", "bsc") >= SUBSEQUENCE,
"the letters are in there and it is offered"
);
assert_eq!(quality("get_parent_id", "gpid"), WORD_START);
assert_eq!(quality("small_vector", "sv"), WORD_START);
assert!(quality("basic_string", "b_s") >= SUBSEQUENCE);
}
#[test]
fn the_initials_of_camel_case_words_match() {
assert_eq!(quality("getPid", "gp"), WORD_START);
assert_eq!(quality("stringView", "sv"), WORD_START);
assert_eq!(quality("HTTPServer", "hs"), WORD_START);
}
#[test]
fn a_prefix_that_starts_a_later_word_is_weaker_than_one_that_starts_the_name() {
assert!(quality("to_string", "string") <= WORD_PREFIX);
assert_eq!(quality("to_string", "to"), PREFIX);
const _: () = assert!(WORD_PREFIX < WORD_START);
}
#[test]
fn the_initials_of_the_words_are_what_is_ranked_highest() {
assert_eq!(quality("get_parent_id", "gpid"), WORD_START);
assert!(quality("gather_pid", "gpid") >= SUBSEQUENCE);
assert!(quality("getpid", "gpid") >= SUBSEQUENCE);
assert!(quality("mapping_pid", "gpd") < WORD_START);
assert_eq!(quality("gather_pid", "xyz"), NONE);
}
#[test]
fn a_candidate_without_the_characters_does_not_match_at_all() {
assert_eq!(quality("string", "xyz"), NONE);
assert_eq!(quality("get", "getters"), NONE);
assert_eq!(quality("ge", "get"), NONE);
}
#[test]
fn a_prefix_must_beat_a_word_match_for_the_same_typed_text() {
let string = quality("string", "str");
let to_string = quality("to_string", "str");
let sort = quality("sort", "str");
assert!(string > to_string, "{string} vs {to_string}");
assert!(string > sort, "{string} vs {sort}");
assert_eq!(string, PREFIX);
assert_eq!(sort, NONE);
assert!(to_string <= WORD_PREFIX);
}
#[test]
fn words_are_found_by_both_conventions_at_once() {
for (name, initials) in [
("get_pid", "gp"),
("getPid", "gp"),
("GetPid", "gp"),
("HTTPServer", "hs"),
("utf8Decode", "ud"),
("_private_helper", "ph"),
] {
assert_eq!(
quality(name, initials),
WORD_START,
"{name} should answer {initials} as its words"
);
}
assert!(quality("get_pid", "gq") < WORD_START);
}
#[test]
fn a_digit_begins_a_word_and_a_letter_after_one_does_too() {
assert_eq!(quality("utf8Decode", "ud"), WORD_START);
assert_eq!(quality("utf8Decode", "8d"), WORD_PREFIX);
}
}