fn is_cancelled() -> bool {
crate::mcp::budget::current_cancel_flag()
.is_some_and(|f| f.load(std::sync::atomic::Ordering::Relaxed))
}
#[allow(clippy::needless_range_loop)]
pub fn levenshtein_distance(a: &str, b: &str) -> usize {
levenshtein_distance_with_limit(a, b, 10000)
}
pub fn levenshtein_distance_with_limit(a: &str, b: &str, max_len: usize) -> usize {
let mut a_chars: Vec<char> = a.chars().collect();
let mut b_chars: Vec<char> = b.chars().collect();
let mut a_len = a_chars.len();
let mut b_len = b_chars.len();
if a_len > max_len || b_len > max_len {
return std::cmp::max(a_len, b_len);
}
if a_len == 0 {
return b_len;
}
if b_len == 0 {
return a_len;
}
if a == b {
return 0;
}
if b_len > a_len {
std::mem::swap(&mut a_chars, &mut b_chars);
std::mem::swap(&mut a_len, &mut b_len);
}
if (a_len as u64).saturating_mul(b_len as u64) > DIFF_SPANS_MAX_CELLS {
return std::cmp::max(a_len, b_len);
}
let mut prev = vec![0usize; b_len + 1];
let mut curr = vec![0usize; b_len + 1];
for (j, v) in prev.iter_mut().enumerate() {
*v = j;
}
for i in 1..=a_len {
if is_cancelled() {
return std::cmp::max(a_len, b_len);
}
curr[0] = i;
for j in 1..=b_len {
let cost = if a_chars[i - 1] == b_chars[j - 1] {
0
} else {
1
};
curr[j] = std::cmp::min(
std::cmp::min(prev[j] + 1, curr[j - 1] + 1),
prev[j - 1] + cost,
);
}
std::mem::swap(&mut prev, &mut curr);
}
prev[b_len]
}
#[derive(Debug, serde::Serialize)]
pub struct DiffSpan {
pub a_start: usize,
pub a_end: usize,
pub b_start: usize,
pub b_end: usize,
pub kind: String,
pub a_text: String,
pub b_text: String,
}
fn char_offsets(s: &str) -> Vec<usize> {
let mut offsets: Vec<usize> = s.char_indices().map(|(offset, _)| offset).collect();
offsets.push(s.len());
offsets
}
fn char_slice(s: &str, offsets: &[usize], start: usize, end: usize) -> String {
if start >= end {
return String::new();
}
let byte_start = offsets.get(start).copied().unwrap_or(s.len());
let byte_end = offsets.get(end).copied().unwrap_or(s.len());
s[byte_start..byte_end].to_string()
}
const DIFF_SPANS_MAX_CELLS: u64 = 4_000_000;
pub fn diff_spans(a: &str, b: &str, max_diffs: usize) -> Vec<DiffSpan> {
if a.is_empty() && b.is_empty() {
return vec![];
}
if a == b {
return vec![];
}
let a_chars: Vec<char> = a.chars().collect();
let b_chars: Vec<char> = b.chars().collect();
let a_offsets = char_offsets(a);
let b_offsets = char_offsets(b);
let a_len = a_chars.len();
let b_len = b_chars.len();
if (a_len as u64).saturating_mul(b_len as u64) > DIFF_SPANS_MAX_CELLS {
return coarse_diff_spans(a, &a_chars, b, &b_chars, max_diffs);
}
let stride = b_len + 1;
let mut dp = vec![0u32; (a_len + 1) * stride];
for i in 1..=a_len {
if is_cancelled() {
return coarse_diff_spans(a, &a_chars, b, &b_chars, max_diffs);
}
for j in 1..=b_len {
if a_chars[i - 1] == b_chars[j - 1] {
dp[i * stride + j] = dp[(i - 1) * stride + (j - 1)] + 1;
} else {
dp[i * stride + j] = dp[(i - 1) * stride + j]
.max(dp[i * stride + (j - 1)])
.max(dp[(i - 1) * stride + (j - 1)]);
}
}
}
let mut match_positions_rev: Vec<(usize, usize)> = vec![];
let mut i = a_len;
let mut j = b_len;
while i > 0 && j > 0 {
if a_chars[i - 1] == b_chars[j - 1] {
match_positions_rev.push((i - 1, j - 1));
i -= 1;
j -= 1;
} else if dp[(i - 1) * stride + j] >= dp[i * stride + (j - 1)] {
i -= 1;
} else {
j -= 1;
}
}
match_positions_rev.reverse();
let mut blocks: Vec<(usize, usize, usize, usize)> = vec![];
for (ai, bj) in &match_positions_rev {
if let Some(last) = blocks.last_mut() {
if last.1 == *ai && last.3 == *bj {
last.1 = ai + 1;
last.3 = bj + 1;
continue;
}
}
blocks.push((*ai, ai + 1, *bj, bj + 1));
}
let mut spans: Vec<DiffSpan> = vec![];
let mut prev_a_end = 0;
let mut prev_b_end = 0;
for (a_start, a_end, b_start, b_end) in &blocks {
if prev_a_end < *a_start || prev_b_end < *b_start {
let kind = if prev_a_end < *a_start && prev_b_end < *b_start {
"replace"
} else if prev_b_end < *b_start {
"insert"
} else {
"delete"
};
spans.push(DiffSpan {
a_start: prev_a_end,
a_end: *a_start,
b_start: prev_b_end,
b_end: *b_start,
kind: kind.to_string(),
a_text: char_slice(a, &a_offsets, prev_a_end, *a_start),
b_text: char_slice(b, &b_offsets, prev_b_end, *b_start),
});
if spans.len() >= max_diffs {
break;
}
}
prev_a_end = *a_end;
prev_b_end = *b_end;
}
if spans.len() < max_diffs && (prev_a_end < a_len || prev_b_end < b_len) {
let kind = if prev_a_end < a_len && prev_b_end < b_len {
"replace"
} else if prev_b_end < b_len {
"insert"
} else {
"delete"
};
spans.push(DiffSpan {
a_start: prev_a_end,
a_end: a_len,
b_start: prev_b_end,
b_end: b_len,
kind: kind.to_string(),
a_text: char_slice(a, &a_offsets, prev_a_end, a_len),
b_text: char_slice(b, &b_offsets, prev_b_end, b_len),
});
}
spans
}
fn coarse_diff_spans(
a: &str,
a_chars: &[char],
b: &str,
b_chars: &[char],
max_diffs: usize,
) -> Vec<DiffSpan> {
if max_diffs == 0 {
return vec![];
}
let a_len = a_chars.len();
let b_len = b_chars.len();
let a_offsets = char_offsets(a);
let b_offsets = char_offsets(b);
let min_len = a_len.min(b_len);
let mut prefix = 0;
while prefix < min_len && a_chars[prefix] == b_chars[prefix] {
prefix += 1;
}
let mut suffix = 0;
while suffix < min_len - prefix && a_chars[a_len - 1 - suffix] == b_chars[b_len - 1 - suffix] {
suffix += 1;
}
let a_mid = prefix..a_len - suffix;
let b_mid = prefix..b_len - suffix;
if a_mid.is_empty() && b_mid.is_empty() {
return vec![];
}
debug_assert!(!a_mid.is_empty() || !b_mid.is_empty());
let kind = if !a_mid.is_empty() && !b_mid.is_empty() {
"replace"
} else if !b_mid.is_empty() {
"insert"
} else {
"delete"
};
vec![DiffSpan {
a_start: a_mid.start,
a_end: a_mid.end,
b_start: b_mid.start,
b_end: b_mid.end,
kind: kind.to_string(),
a_text: char_slice(a, &a_offsets, a_mid.start, a_mid.end),
b_text: char_slice(b, &b_offsets, b_mid.start, b_mid.end),
}]
}
#[derive(Debug, Clone, PartialEq, serde::Serialize, serde::Deserialize)]
pub struct FirstDiff {
pub a_index: usize,
pub b_index: usize,
pub a_char: String,
pub b_char: String,
pub a_codepoint: String,
pub b_codepoint: String,
}
#[derive(Debug, Clone, serde::Serialize, serde::Deserialize)]
pub struct CommonPrefixSuffix {
pub common_prefix_len: usize,
pub common_suffix_len: usize,
}
pub fn first_diff(a: &str, b: &str) -> Option<FirstDiff> {
let a_chars: Vec<char> = a.chars().collect();
let b_chars: Vec<char> = b.chars().collect();
let min_len = a_chars.len().min(b_chars.len());
for i in 0..min_len {
if a_chars[i] != b_chars[i] {
return Some(FirstDiff {
a_index: i,
b_index: i,
a_char: a_chars[i].to_string(),
b_char: b_chars[i].to_string(),
a_codepoint: format!("U+{:04X}", a_chars[i] as u32),
b_codepoint: format!("U+{:04X}", b_chars[i] as u32),
});
}
}
if a_chars.len() != b_chars.len() {
let idx = min_len;
let a_char = if a_chars.len() > min_len {
a_chars[min_len].to_string()
} else {
String::new()
};
let b_char = if b_chars.len() > min_len {
b_chars[min_len].to_string()
} else {
String::new()
};
let a_codepoint = if a_chars.len() > min_len {
format!("U+{:04X}", a_chars[min_len] as u32)
} else {
String::new()
};
let b_codepoint = if b_chars.len() > min_len {
format!("U+{:04X}", b_chars[min_len] as u32)
} else {
String::new()
};
return Some(FirstDiff {
a_index: idx,
b_index: idx,
a_char,
b_char,
a_codepoint,
b_codepoint,
});
}
None
}
pub fn common_prefix_suffix(a: &str, b: &str) -> CommonPrefixSuffix {
let a_chars: Vec<char> = a.chars().collect();
let b_chars: Vec<char> = b.chars().collect();
let min_len = a_chars.len().min(b_chars.len());
let mut prefix_len = 0;
while prefix_len < min_len && a_chars[prefix_len] == b_chars[prefix_len] {
prefix_len += 1;
}
let mut suffix_len = 0;
while suffix_len < min_len - prefix_len
&& a_chars[a_chars.len() - 1 - suffix_len] == b_chars[b_chars.len() - 1 - suffix_len]
{
suffix_len += 1;
}
CommonPrefixSuffix {
common_prefix_len: prefix_len,
common_suffix_len: suffix_len,
}
}