use super::MatchQuality;
use crate::text_offsets::Offsets;
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub(crate) struct Place {
pub(crate) start: usize,
pub(crate) end: usize,
}
fn occurrences(offsets: &Offsets<'_>, words: &str) -> Vec<usize> {
let text = offsets.text();
let mut found = Vec::new();
let Some(step) = words.chars().next().map(char::len_utf8) else {
return found;
};
let mut from = 0;
while let Some(index) = text
.get(from..)
.and_then(|rest| rest.find(words))
.map(|at| from + at)
{
found.extend(offsets.offset_at(index));
from = index + step;
}
found
}
pub(crate) fn places_of(offsets: &Offsets<'_>, words: &str) -> Vec<Place> {
let length = words.chars().count();
occurrences(offsets, words)
.into_iter()
.map(|start| Place {
start,
end: start + length,
})
.collect()
}
struct Changed {
text: String,
origins: Vec<usize>,
}
impl Changed {
fn places_of(&self, words: &str) -> Vec<Place> {
let length = words.chars().count();
occurrences(&Offsets::of(&self.text), words)
.into_iter()
.filter_map(|at| {
Some(Place {
start: *self.origins.get(at)?,
end: self.origins.get((at + length).checked_sub(1)?)? + 1,
})
})
.collect()
}
}
fn normalized(text: &str) -> Changed {
let (mut plain, mut origins) = (String::new(), Vec::new());
let mut run: Option<usize> = None;
for (offset, character) in text.chars().enumerate() {
if character.is_whitespace() {
run.get_or_insert(offset);
continue;
}
if let Some(began) = run.take()
&& !plain.is_empty()
{
plain.push(' ');
origins.push(began);
}
let written = match character {
'\u{2018}' | '\u{2019}' => "'",
'\u{201C}' | '\u{201D}' => "\"",
'\u{2014}' => "--",
'\u{2013}' => "-",
_ => {
plain.push(character);
origins.push(offset);
continue;
}
};
plain.push_str(written);
origins.extend(std::iter::repeat_n(offset, written.len()));
}
Changed {
text: plain,
origins,
}
}
fn lower_cased(text: &str) -> Changed {
let lowered = text.to_lowercase();
let origins: Vec<usize> = text
.chars()
.enumerate()
.flat_map(|(offset, character)| {
std::iter::repeat_n(offset, character.to_lowercase().count())
})
.collect();
debug_assert_eq!(origins.len(), lowered.chars().count());
Changed {
text: lowered,
origins,
}
}
fn distances_from(wanted: &[char], text: &[char], allowance: usize) -> Option<Vec<usize>> {
let mut row: Vec<usize> = (0..=text.len()).collect();
for (taken, want) in wanted.iter().enumerate() {
let mut next = Vec::with_capacity(row.len());
next.push(taken + 1);
for (n, had) in text.iter().enumerate() {
let replaced = row[n] + usize::from(want != had);
next.push(replaced.min(row[n + 1] + 1).min(next[n] + 1));
}
if next.iter().all(|distance| *distance > allowance) {
return None;
}
row = next;
}
Some(row)
}
fn nearest_stretch(text: &[char], wanted: &[char]) -> Option<Place> {
let allowance = wanted.len() / 20;
if allowance == 0 {
return None;
}
let shortest = wanted.len() - allowance;
let mut nearest: Option<(Place, usize)> = None;
for start in 0..=text.len().checked_sub(shortest)? {
let longest = (wanted.len() + allowance).min(text.len() - start);
let Some(distances) = distances_from(wanted, &text[start..start + longest], allowance)
else {
continue;
};
for away in 0..=allowance {
let lengths = [
Some(wanted.len() - away),
(away > 0).then_some(wanted.len() + away),
];
for length in lengths.into_iter().flatten() {
let Some(distance) = distances.get(length).copied() else {
continue;
};
if distance <= allowance && nearest.is_none_or(|(_, least)| distance < least) {
let end = start + length;
nearest = Some((Place { start, end }, distance));
}
}
}
}
nearest.map(|(place, _)| place)
}
pub(crate) fn places_like(text: &str, words: &str) -> Option<(Vec<Place>, MatchQuality)> {
let places = normalized(text).places_of(&normalized(words).text);
if !places.is_empty() {
return Some((places, MatchQuality::Normalized));
}
let places = lower_cased(text).places_of(&words.to_lowercase());
if !places.is_empty() {
return Some((places, MatchQuality::CaseInsensitive));
}
let (text, wanted): (Vec<char>, Vec<char>) = (text.chars().collect(), words.chars().collect());
nearest_stretch(&text, &wanted).map(|place| (vec![place], MatchQuality::Fuzzy))
}
const CONTEXT: usize = 64;
const LENGTHENING: usize = 32;
fn is_boundary(character: char) -> bool {
character.is_whitespace()
|| matches!(
character,
'.' | ','
| ';'
| ':'
| '!'
| '?'
| '\''
| '"'
| '('
| ')'
| '['
| ']'
| '{'
| '}'
| '<'
| '>'
| '/'
| '\\'
)
}
pub(crate) fn context_of<'t>(
offsets: &Offsets<'t>,
place: Place,
) -> (Option<&'t str>, Option<&'t str>) {
let length = offsets.len();
let boundary_at = |offset: usize| offsets.char_at(offset).is_some_and(is_boundary);
let prefix = if place.start == 0 {
None
} else {
let mut from = place.start.saturating_sub(CONTEXT);
let least = from.saturating_sub(LENGTHENING);
while from > least && !boundary_at(from - 1) {
from -= 1;
}
offsets.between(from, place.start)
};
let suffix = if place.end >= length {
None
} else {
let mut to = (place.end + CONTEXT).min(length);
let most = (to + LENGTHENING).min(length);
while to < most && !boundary_at(to) {
to += 1;
}
offsets.between(place.end, to)
};
(prefix, suffix)
}