const CUTOFF: f64 = 0.6;
const LIMIT: usize = 3;
pub(crate) fn close_matches<'a>(
word: &str,
candidates: impl IntoIterator<Item = &'a str>,
) -> Vec<&'a str> {
let target = word.chars().collect::<Vec<_>>();
let mut scored = candidates
.into_iter()
.filter_map(|candidate| {
let ratio = ratio(&candidate.chars().collect::<Vec<_>>(), &target);
(ratio >= CUTOFF).then_some((ratio, candidate))
})
.collect::<Vec<_>>();
scored.sort_by(|left, right| {
right
.0
.partial_cmp(&left.0)
.unwrap_or(std::cmp::Ordering::Equal)
.then_with(|| right.1.cmp(left.1))
});
scored.truncate(LIMIT);
scored.into_iter().map(|(_, candidate)| candidate).collect()
}
fn ratio(a: &[char], b: &[char]) -> f64 {
let total = a.len() + b.len();
if total == 0 {
return 1.0;
}
2.0 * matched(a, b) as f64 / total as f64
}
fn matched(a: &[char], b: &[char]) -> usize {
let mut total = 0;
let mut queue = vec![(0, a.len(), 0, b.len())];
while let Some((alo, ahi, blo, bhi)) = queue.pop() {
let (i, j, size) = longest_match(a, b, alo, ahi, blo, bhi);
if size == 0 {
continue;
}
total += size;
if alo < i && blo < j {
queue.push((alo, i, blo, j));
}
if i + size < ahi && j + size < bhi {
queue.push((i + size, ahi, j + size, bhi));
}
}
total
}
fn longest_match(
a: &[char],
b: &[char],
alo: usize,
ahi: usize,
blo: usize,
bhi: usize,
) -> (usize, usize, usize) {
let (mut best_i, mut best_j, mut best_size) = (alo, blo, 0usize);
let mut previous = vec![0usize; b.len() + 1];
let mut current = vec![0usize; b.len() + 1];
for (i, left) in a.iter().enumerate().take(ahi).skip(alo) {
current[blo..bhi].fill(0);
for j in blo..bhi {
if *left != b[j] {
continue;
}
let run = if j == blo { 1 } else { previous[j - 1] + 1 };
current[j] = run;
if run > best_size {
best_i = i + 1 - run;
best_j = j + 1 - run;
best_size = run;
}
}
std::mem::swap(&mut previous, &mut current);
}
(best_i, best_j, best_size)
}
#[cfg(test)]
mod tests {
use super::{close_matches, ratio};
fn score(a: &str, b: &str) -> f64 {
ratio(
&a.chars().collect::<Vec<_>>(),
&b.chars().collect::<Vec<_>>(),
)
}
#[test]
fn ratio_matches_the_python_reference_values() {
let cases = [
("qwen3_8b", "qwen3-8b", 0.875),
("qwen3_8b", "qwen3_8b", 1.0),
("llama_31_8b", "llama_3_8b", 0.9523809523809523),
("gpt_oss_120b", "kimi_k3", 0.10526315789473684),
("abcd", "dcba", 0.25),
("", "abc", 0.0),
];
for (left, right, expected) in cases {
let observed = score(left, right);
assert!(
(observed - expected).abs() < 1e-12,
"{left} vs {right}: {observed} != {expected}"
);
}
}
#[test]
fn suggestions_are_ranked_and_capped() {
let families = [
"bert_base_cased",
"deepseek_v3",
"gpt_oss_120b",
"kimi_k3",
"llama_31_8b",
"qwen3_8b",
];
assert_eq!(close_matches("qwen3-8b", families), vec!["qwen3_8b"]);
assert_eq!(close_matches("llama31_8b", families), vec!["llama_31_8b"]);
assert!(close_matches("zzzzzzzz", families).is_empty());
assert!(close_matches("bert_base", families).len() <= 3);
}
#[test]
fn the_shipped_roster_answers_typos_the_way_python_does() {
let families = [
"deepseek_v3",
"deepseek_v4_flash",
"glm_5_2",
"gpt_oss_120b",
"hy3",
"kimi_k3",
"laguna_s_2_1",
"ling_3_0_flash",
"llama_3_1_8b",
"minimax_m3",
"ministral_3_8b",
"nemotron_3_nano_4b",
"olmo_3_7b",
"qwen3_5_08b",
"qwen3_8b",
];
let cases: [(&str, Vec<&str>); 22] = [
("qwen3-8b", vec!["qwen3_8b", "qwen3_5_08b"]),
("qwen38b", vec!["qwen3_8b", "qwen3_5_08b"]),
("Qwen3_8B", vec!["qwen3_8b", "qwen3_5_08b"]),
("llama_31_8b", vec!["llama_3_1_8b", "olmo_3_7b"]),
("llama3_1_8b", vec!["llama_3_1_8b"]),
("deepseek", vec!["deepseek_v3", "deepseek_v4_flash"]),
("deepseekv3", vec!["deepseek_v3", "deepseek_v4_flash"]),
("kimi", vec!["kimi_k3"]),
("kimi_k2", vec!["kimi_k3"]),
("gpt-oss-120b", vec!["gpt_oss_120b"]),
("minimax", vec!["minimax_m3"]),
("ministral", vec!["ministral_3_8b"]),
("nemotron", vec!["nemotron_3_nano_4b"]),
("olmo3_7b", vec!["olmo_3_7b"]),
("glm52", vec!["glm_5_2"]),
("hy", vec!["hy3"]),
("ling_3_0", vec!["ling_3_0_flash"]),
("laguna", vec!["laguna_s_2_1"]),
("zzzz", vec![]),
("qwen", vec!["qwen3_8b"]),
("qwen3_5_8b", vec!["qwen3_5_08b", "qwen3_8b"]),
("bert_base_cased", vec![]),
];
for (query, expected) in cases {
assert_eq!(close_matches(query, families), expected, "{query}");
}
}
#[test]
fn equal_scores_rank_the_larger_id_first() {
let observed = close_matches("aab", ["aac", "aad"]);
assert_eq!(observed, vec!["aad", "aac"]);
}
}