const MAX_CANDIDATE_ITEMS: usize = 750;
const MAX_STRING_SIZE: usize = 40;
const MOVE_COST: i64 = 2;
const CASE_COST: i64 = 1;
fn substitution_cost(a: char, b: char) -> i64 {
if a == b {
return 0;
}
if a.to_lowercase().eq(b.to_lowercase()) {
return CASE_COST;
}
MOVE_COST
}
fn levenshtein(a: &str, b: &str, max_cost: i64) -> i64 {
if a == b {
return 0;
}
let av: Vec<char> = a.chars().collect();
let bv: Vec<char> = b.chars().collect();
let mut lo = 0;
while lo < av.len() && lo < bv.len() && av[lo] == bv[lo] {
lo += 1;
}
let (mut ahi, mut bhi) = (av.len(), bv.len());
while ahi > lo && bhi > lo && av[ahi - 1] == bv[bhi - 1] {
ahi -= 1;
bhi -= 1;
}
let mut a = &av[lo..ahi];
let mut b = &bv[lo..bhi];
if a.is_empty() || b.is_empty() {
return MOVE_COST * (a.len() + b.len()) as i64;
}
if a.len() > MAX_STRING_SIZE || b.len() > MAX_STRING_SIZE {
return max_cost + 1;
}
if b.len() < a.len() {
std::mem::swap(&mut a, &mut b);
}
if (b.len() - a.len()) as i64 * MOVE_COST > max_cost {
return max_cost + 1;
}
let mut row: Vec<i64> = (1..=a.len() as i64).map(|i| i * MOVE_COST).collect();
let mut result = 0;
for (bindex, &bchar) in b.iter().enumerate() {
let mut distance = bindex as i64 * MOVE_COST;
result = distance;
let mut minimum = i64::MAX;
for (index, &achar) in a.iter().enumerate() {
let substitute = distance + substitution_cost(bchar, achar);
distance = row[index];
let insert_delete = result.min(distance) + MOVE_COST;
result = insert_delete.min(substitute);
row[index] = result;
minimum = minimum.min(result);
}
if minimum > max_cost {
return max_cost + 1;
}
}
result
}
pub fn closest(candidates: &[String], wrong: &str) -> Option<String> {
if candidates.len() >= MAX_CANDIDATE_ITEMS {
return None;
}
let wrong_len = wrong.chars().count() as i64;
let mut best_distance = i64::MAX;
let mut suggestion: Option<&String> = None;
for candidate in candidates {
if candidate == wrong {
continue;
}
let budget = (candidate.chars().count() as i64 + wrong_len + 3) * MOVE_COST / 6;
let max_distance = budget.min(best_distance - 1);
let distance = levenshtein(wrong, candidate, max_distance);
if distance > max_distance {
continue;
}
if suggestion.is_none() || distance < best_distance {
suggestion = Some(candidate);
best_distance = distance;
}
}
suggestion.cloned()
}
pub fn with_hint(line: &str, suggestion: Option<String>) -> String {
match suggestion {
Some(s) => format!("{line}. Did you mean: '{s}'?"),
None => line.to_string(),
}
}
fn name_error_subject(line: &str) -> Option<&str> {
let rest = line.strip_prefix("NameError: name '")?;
let end = rest.find('\'')?;
rest[end..]
.starts_with("' is not defined")
.then_some(&rest[..end])
}
pub fn with_import_hint(line: String, is_stdlib_module: impl Fn(&str) -> bool) -> String {
let subject = match name_error_subject(&line) {
Some(s) if is_stdlib_module(s) => s.to_string(),
_ => return line,
};
if line.contains(". Did you mean: '") {
format!("{line} Or did you forget to import '{subject}'?")
} else {
format!("{line}. Did you forget to import '{subject}'?")
}
}