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 enum Hint {
Name(String),
Attr { suggestion: String, wrong: String },
Raw(String),
}
fn escaped(s: &str, prefix: &str) -> String {
let ascii = crate::host::ascii_of(&crate::host::quote_str(s));
format!("'{prefix}{s}' ({ascii})")
}
pub fn with_hint(line: &str, hint: Option<Hint>) -> String {
match hint {
Some(Hint::Name(s)) if s.is_ascii() => format!("{line}. Did you mean: '{s}'?"),
Some(Hint::Name(s)) => format!("{line}. Did you mean: {}?", escaped(&s, "")),
Some(Hint::Attr { suggestion, wrong }) if suggestion.is_ascii() => {
format!("{line}. Did you mean '.{suggestion}' instead of '.{wrong}'?")
}
Some(Hint::Attr { suggestion, wrong }) => format!(
"{line}. Did you mean {} instead of {}?",
escaped(&suggestion, "."),
escaped(&wrong, ".")
),
Some(Hint::Raw(hint)) => format!("{line}. {hint}"),
None => line.to_string(),
}
}
type CrossLanguageHint = (&'static str, &'static str, bool);
const CROSS_LANGUAGE_HINTS: &[(&str, &[CrossLanguageHint])] = &[
("push", &[("list", "append", false)]),
("concat", &[("list", "extend", false)]),
("addAll", &[("list", "extend", false)]),
("contains", &[("list", "Use 'x in list'.", true)]),
(
"add",
&[
("list", "Did you mean to use a 'set' object?", true),
("frozenset", "Did you mean to use a 'set' object?", true),
],
),
("toUpperCase", &[("str", "upper", false)]),
("toLowerCase", &[("str", "lower", false)]),
("trimStart", &[("str", "lstrip", false)]),
("trimEnd", &[("str", "rstrip", false)]),
("keySet", &[("dict", "keys", false)]),
("entrySet", &[("dict", "items", false)]),
("entries", &[("dict", "items", false)]),
("putAll", &[("dict", "update", false)]),
("put", &[("dict", "Use d[k] = v.", true)]),
(
"append",
&[("tuple", "Did you mean to use a 'list' object?", true)],
),
(
"extend",
&[("tuple", "Did you mean to use a 'list' object?", true)],
),
(
"insert",
&[("tuple", "Did you mean to use a 'list' object?", true)],
),
(
"remove",
&[
("tuple", "Did you mean to use a 'list' object?", true),
("frozenset", "Did you mean to use a 'set' object?", true),
],
),
(
"discard",
&[("frozenset", "Did you mean to use a 'set' object?", true)],
),
(
"update",
&[
("frozenset", "Did you mean to use a 'set' object?", true),
("frozendict", "Did you mean to use a 'dict' object?", true),
],
),
("__or__", &[("float", FLOAT_BITWISE, true)]),
("__and__", &[("float", FLOAT_BITWISE, true)]),
("__xor__", &[("float", FLOAT_BITWISE, true)]),
("__lshift__", &[("float", FLOAT_BITWISE, true)]),
("__rshift__", &[("float", FLOAT_BITWISE, true)]),
];
const FLOAT_BITWISE: &str =
"Did you mean to use an 'int' object? Bitwise operators are not supported by 'float'.";
pub fn cross_language_hint(wrong: &str, is_instance: impl Fn(&str) -> bool) -> Option<String> {
let (_, entries) = CROSS_LANGUAGE_HINTS
.iter()
.find(|(name, _)| *name == wrong)?;
let (_, hint, raw) = entries.iter().find(|(ty, _, _)| is_instance(ty))?;
Some(if *raw {
hint.to_string()
} else {
format!("Did you mean '.{hint}'?")
})
}
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}'?")
}
}
const KEYWORD_TYPO_TOKENS: usize = 10;
const KEYWORD_TYPO_MAX_SOURCE: usize = 1024;
pub fn keyword_typo(
msg: &str,
pos: &crate::parser::SyntaxPos,
) -> Option<(crate::parser::SyntaxPos, String)> {
use crate::builtins::str_splitlines;
if msg != "invalid syntax" && !msg.contains("Perhaps you forgot a comma") {
return None;
}
let meta = pos.metadata.as_ref()?;
let mut line = meta.lineno;
let mut end_line = pos.lineno.unwrap_or(0);
let mut from_filename = false;
let lines: Vec<String> = match &meta.source {
Some(source) => str_splitlines(source, false),
None => {
let read = pos
.filename
.as_deref()
.and_then(|f| std::fs::read_to_string(f).ok());
match read {
Some(file) => {
from_filename = true;
str_splitlines(&file, false)
}
None => {
if pos.filename.is_some() {
(line, end_line) = (0, 1);
}
str_splitlines(pos.text.as_deref()?, false)
}
}
}
};
let start = if line > 0 { line - 1 } else { 0 } as usize;
let stop = usize::try_from(end_line).unwrap_or(0).min(lines.len());
let excerpt = lines
.get(start..stop.max(start))
.unwrap_or_default()
.join("\n");
let error_code = dedent(&excerpt);
if error_code.chars().count() > KEYWORD_TYPO_MAX_SOURCE {
return None;
}
let error_lines = str_splitlines(&error_code, false);
let physical: Vec<&str> = error_code.split_inclusive('\n').collect();
let tokens = name_tokens(&error_code)?;
let keywords: Vec<String> = crate::parser::KEYWORDS
.iter()
.map(|k| k.to_string())
.collect();
let mut tokens_left = KEYWORD_TYPO_TOKENS;
for token in tokens {
let row = token.line as i64;
let the_end = if line == 0 { end_line } else { end_line + 1 };
if from_filename && row + line != the_end {
continue;
}
let token_line = *physical.get(token.line as usize - 1)?;
let (col, end_col) = (token.col as usize, token.end_col as usize);
let wrong_name: String = token_line.chars().skip(col).take(end_col - col).collect();
if crate::parser::is_keyword(&wrong_name) {
continue;
}
if tokens_left == 0 {
break;
}
tokens_left -= 1;
let mut matches: Vec<String> = closest(&keywords, &wrong_name).into_iter().collect();
matches.extend(get_close_matches(&wrong_name, &keywords, 3, 0.5));
matches.truncate(3);
for suggestion in matches {
if suggestion.is_empty() || suggestion == wrong_name {
continue;
}
let mut the_lines = error_lines.clone();
let chars: Vec<char> = the_lines.get(token.line as usize - 1)?.chars().collect();
let (a, b) = (col.min(chars.len()), end_col.min(chars.len()));
let replaced: String = chars[..a]
.iter()
.chain(suggestion.chars().collect::<Vec<_>>().iter())
.chain(chars[b.max(a)..].iter())
.collect();
the_lines[token.line as usize - 1] = replaced;
if !compiles_as_command(&the_lines.join("\n")) {
continue;
}
let mut typo_pos = pos.clone();
typo_pos.text = Some(token_line.to_string());
typo_pos.offset = Some(col as i64 + 1);
typo_pos.end_offset = Some(end_col as i64 + 1);
typo_pos.lineno = Some(row);
typo_pos.end_lineno = Some(row);
return Some((
typo_pos,
format!("invalid syntax. Did you mean '{suggestion}'?"),
));
}
}
None
}
struct NameAt {
line: u32,
col: u32,
end_col: u32,
}
fn name_tokens(code: &str) -> Option<Vec<NameAt>> {
use crate::lexer::Tok;
let chars: Vec<char> = code.chars().collect();
let starts = line_starts(&chars);
let mut names = Vec::new();
for token in crate::lexer::lex(code).ok()?.toks {
match &token.tok {
Tok::Name(_) | Tok::Ident(_) => names.push(NameAt {
line: token.line,
col: token.col,
end_col: token.end_col,
}),
Tok::FString(raw, is_raw) | Tok::TString(raw, is_raw) => {
let end = starts[token.line as usize - 1] + token.end_col as usize;
let body = string_body_start(&chars, end, raw)?;
let line = starts.partition_point(|&s| s <= body);
let body =
FieldScan::new(raw, *is_raw, line as u32, (body - starts[line - 1]) as u32);
if !body.literal(0, body.chars.len(), false, &mut names) {
break;
}
}
_ => {}
}
}
Some(names)
}
fn line_starts(chars: &[char]) -> Vec<usize> {
std::iter::once(0)
.chain(
chars
.iter()
.enumerate()
.filter(|&(_, &c)| c == '\n')
.map(|(i, _)| i + 1),
)
.collect()
}
fn string_body_start(chars: &[char], end: usize, raw: &str) -> Option<usize> {
let quote = *chars.get(end.checked_sub(1)?)?;
let triple = end >= 3 && chars[end - 3..end].iter().all(|&c| c == quote);
let body_end = end - if triple { 3 } else { 1 };
body_end.checked_sub(raw.chars().count())
}
struct FieldScan {
chars: Vec<char>,
at: Vec<(u32, u32)>,
is_raw: bool,
}
impl FieldScan {
fn new(raw: &str, is_raw: bool, line: u32, col: u32) -> Self {
let chars: Vec<char> = raw.chars().collect();
let mut at = Vec::with_capacity(chars.len() + 1);
let (mut line, mut col) = (line, col);
for &c in &chars {
at.push((line, col));
if c == '\n' {
(line, col) = (line + 1, 0);
} else {
col += 1;
}
}
at.push((line, col));
FieldScan { chars, at, is_raw }
}
fn literal(&self, from: usize, to: usize, in_spec: bool, names: &mut Vec<NameAt>) -> bool {
let mut i = from;
let mut literal_start = from;
while i < to {
match self.chars[i] {
'{' if !in_spec && self.chars.get(i + 1) == Some(&'{') => i += 2,
'}' if !in_spec && self.chars.get(i + 1) == Some(&'}') => i += 2,
'{' => {
let lead: String = self.chars[literal_start..i].iter().collect();
if crate::lexer::ends_with_named_escape_lead(&lead, self.is_raw) {
while i < to && self.chars[i] != '}' {
i += 1;
}
i += 1;
continue;
}
let close = self.field_end(i + 1, to);
if !self.field(i + 1, close, names) {
return false;
}
i = close + 1;
literal_start = i;
}
_ => i += 1,
}
}
true
}
fn field_end(&self, from: usize, to: usize) -> usize {
self.top_level(from, to, |c, _| c == '}').unwrap_or(to)
}
fn top_level(
&self,
from: usize,
to: usize,
hit: impl Fn(char, Option<char>) -> bool,
) -> Option<usize> {
let mut depth = 0i32;
let mut quote: Option<char> = None;
let mut i = from;
while i < to {
let c = self.chars[i];
if let Some(q) = quote {
if c == '\\' {
i += 1;
} else if c == q {
quote = None;
}
i += 1;
continue;
}
match c {
'\'' | '"' => quote = Some(c),
'(' | '[' | '{' => depth += 1,
')' | ']' if depth > 0 => depth -= 1,
'}' if depth > 0 => depth -= 1,
_ if depth == 0 && hit(c, self.chars.get(i + 1).copied()) => return Some(i),
_ => {}
}
i += 1;
}
None
}
fn field(&self, from: usize, to: usize, names: &mut Vec<NameAt>) -> bool {
let spec = self.top_level(from, to, |c, _| c == ':');
let expr_end = spec.unwrap_or(to);
let conv = self.top_level(from, expr_end, |c, next| c == '!' && next != Some('='));
if !self.expression_names(from, conv.unwrap_or(expr_end), names) {
return false;
}
if let Some(bang) = conv {
let start = (bang + 1..expr_end)
.find(|&j| !self.chars[j].is_whitespace())
.unwrap_or(expr_end);
let mut end = start;
while end < expr_end && (self.chars[end].is_alphanumeric() || self.chars[end] == '_') {
end += 1;
}
if end > start {
let (line, col) = self.at[start];
names.push(NameAt {
line,
col,
end_col: col + (end - start) as u32,
});
}
}
match spec {
Some(colon) => self.literal(colon + 1, to, true, names),
None => true,
}
}
fn expression_names(&self, from: usize, to: usize, names: &mut Vec<NameAt>) -> bool {
use crate::lexer::Tok;
let text: String = std::iter::once('(')
.chain(self.chars[from..to].iter().copied())
.chain(std::iter::once(')'))
.collect();
let Ok(lexed) = crate::lexer::lex(&text) else {
return false;
};
let text_chars: Vec<char> = text.chars().collect();
let starts = line_starts(&text_chars);
for token in lexed.toks {
let index = starts[token.line as usize - 1] + token.col as usize;
match &token.tok {
Tok::Name(_) | Tok::Ident(_) => {
let (line, col) = self.at[from + index - 1];
names.push(NameAt {
line,
col,
end_col: col + token.end_col - token.col,
});
}
Tok::FString(raw, is_raw) | Tok::TString(raw, is_raw) => {
let end = starts[token.line as usize - 1] + token.end_col as usize;
let Some(body) = string_body_start(&text_chars, end, raw) else {
return false;
};
let start = from + body - 1;
let nested = FieldScan {
chars: raw.chars().collect(),
at: self.at[start..=start + raw.chars().count()].to_vec(),
is_raw: *is_raw,
};
if !nested.literal(0, nested.chars.len(), false, names) {
return false;
}
}
_ => {}
}
}
true
}
}
fn compiles_as_command(code: &str) -> bool {
crate::compile(code).is_ok() || crate::parser::is_incomplete_input(code)
}
fn dedent(text: &str) -> String {
use crate::builtins::is_py_space;
let lines: Vec<&str> = text.split('\n').collect();
let blank = |l: &str| !l.is_empty() && l.chars().all(is_py_space);
let non_blank: Vec<&str> = lines
.iter()
.copied()
.filter(|l| !l.is_empty() && !blank(l))
.collect();
let l1 = non_blank.iter().min().copied().unwrap_or("");
let l2 = non_blank.iter().max().copied().unwrap_or("");
let mut margin = 0;
for (i, (c, d)) in l1
.chars()
.zip(l2.chars().chain(std::iter::repeat('\0')))
.enumerate()
{
margin = i;
if c != d || !matches!(c, ' ' | '\t') {
break;
}
}
lines
.iter()
.map(|l| {
if blank(l) {
String::new()
} else {
l.chars().skip(margin).collect()
}
})
.collect::<Vec<_>>()
.join("\n")
}
fn get_close_matches(word: &str, possibilities: &[String], n: usize, cutoff: f64) -> Vec<String> {
let b: Vec<char> = word.chars().collect();
let matcher = SequenceMatcher::new(&b);
let mut result: Vec<(f64, &String)> = Vec::new();
for x in possibilities {
let a: Vec<char> = x.chars().collect();
if matcher.real_quick_ratio(&a) >= cutoff
&& matcher.quick_ratio(&a) >= cutoff
&& matcher.ratio(&a) >= cutoff
{
result.push((matcher.ratio(&a), x));
}
}
result.sort_by(|p, q| q.0.total_cmp(&p.0).then_with(|| q.1.cmp(p.1)));
result.into_iter().take(n).map(|(_, x)| x.clone()).collect()
}
struct SequenceMatcher<'b> {
b: &'b [char],
b2j: std::collections::HashMap<char, Vec<usize>>,
fullbcount: std::collections::HashMap<char, usize>,
}
fn calculate_ratio(matches: usize, length: usize) -> f64 {
if length > 0 {
2.0 * matches as f64 / length as f64
} else {
1.0
}
}
impl<'b> SequenceMatcher<'b> {
fn new(b: &'b [char]) -> Self {
let mut b2j: std::collections::HashMap<char, Vec<usize>> = std::collections::HashMap::new();
let mut fullbcount = std::collections::HashMap::new();
for (i, &elt) in b.iter().enumerate() {
b2j.entry(elt).or_default().push(i);
*fullbcount.entry(elt).or_insert(0) += 1;
}
if b.len() >= 200 {
let ntest = b.len() / 100 + 1;
b2j.retain(|_, idxs| idxs.len() <= ntest);
}
SequenceMatcher { b, b2j, fullbcount }
}
fn find_longest_match(
&self,
a: &[char],
alo: usize,
ahi: usize,
blo: usize,
bhi: usize,
) -> (usize, usize, usize) {
let b = self.b;
let (mut besti, mut bestj, mut bestsize) = (alo, blo, 0);
let mut j2len: std::collections::HashMap<usize, usize> = std::collections::HashMap::new();
for (i, elt) in a.iter().enumerate().take(ahi).skip(alo) {
let mut newj2len = std::collections::HashMap::new();
for &j in self.b2j.get(elt).map(Vec::as_slice).unwrap_or_default() {
if j < blo {
continue;
}
if j >= bhi {
break;
}
let k = j
.checked_sub(1)
.and_then(|p| j2len.get(&p))
.copied()
.unwrap_or(0)
+ 1;
newj2len.insert(j, k);
if k > bestsize {
(besti, bestj, bestsize) = (i + 1 - k, j + 1 - k, k);
}
}
j2len = newj2len;
}
while besti > alo && bestj > blo && a[besti - 1] == b[bestj - 1] {
(besti, bestj, bestsize) = (besti - 1, bestj - 1, bestsize + 1);
}
while besti + bestsize < ahi
&& bestj + bestsize < bhi
&& a[besti + bestsize] == b[bestj + bestsize]
{
bestsize += 1;
}
(besti, bestj, bestsize)
}
fn matching_size(&self, a: &[char]) -> usize {
let mut queue = vec![(0, a.len(), 0, self.b.len())];
let mut total = 0;
while let Some((alo, ahi, blo, bhi)) = queue.pop() {
let (i, j, k) = self.find_longest_match(a, alo, ahi, blo, bhi);
if k > 0 {
total += k;
if alo < i && blo < j {
queue.push((alo, i, blo, j));
}
if i + k < ahi && j + k < bhi {
queue.push((i + k, ahi, j + k, bhi));
}
}
}
total
}
fn ratio(&self, a: &[char]) -> f64 {
calculate_ratio(self.matching_size(a), a.len() + self.b.len())
}
fn quick_ratio(&self, a: &[char]) -> f64 {
let mut avail: std::collections::HashMap<char, i64> = std::collections::HashMap::new();
let mut matches = 0;
for elt in a {
let numb = match avail.get(elt) {
Some(&n) => n,
None => self.fullbcount.get(elt).copied().unwrap_or(0) as i64,
};
avail.insert(*elt, numb - 1);
if numb > 0 {
matches += 1;
}
}
calculate_ratio(matches, a.len() + self.b.len())
}
fn real_quick_ratio(&self, a: &[char]) -> f64 {
calculate_ratio(a.len().min(self.b.len()), a.len() + self.b.len())
}
}