use crate::{Anchor, ByteRange, Rung, Window};
use similar::TextDiff;
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Found {
pub range: ByteRange,
pub rung: Rung,
pub indent: Option<(String, String)>,
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum Located {
Found(Vec<Found>),
Missing(Option<Window>),
}
const NEAREST_BUDGET: usize = 2_000_000;
#[must_use]
pub fn locate(text: &str, anchor: &Anchor) -> Located {
let offset = match &anchor.after {
Some(after) => match text.find(after.as_str()) {
Some(at) => at + after.len(),
None => return Located::Missing(None),
},
None => 0,
};
let region = &text[offset..];
let found = exact(region, anchor)
.or_else(|| by_lines(region, &anchor.text, Rung::TrailingWhitespace))
.or_else(|| by_lines(region, &anchor.text, Rung::Indentation))
.or_else(|| by_lines(region, &anchor.text, Rung::Trimmed));
match found {
Some(found) => Located::Found(found.into_iter().map(|f| shift(f, offset)).collect()),
None => Located::Missing(nearest(text, &anchor.text)),
}
}
fn shift(mut found: Found, offset: usize) -> Found {
found.range.start += offset;
found.range.end += offset;
found
}
fn exact(text: &str, anchor: &Anchor) -> Option<Vec<Found>> {
let needle = anchor.text.as_str();
let found: Vec<_> = text
.match_indices(needle)
.map(|(start, _)| ByteRange {
start,
end: start + needle.len(),
})
.filter(|range| !anchor.whole_lines || on_line_bounds(text, *range))
.map(|range| Found {
range,
rung: Rung::Exact,
indent: None,
})
.collect();
(!found.is_empty()).then_some(found)
}
fn on_line_bounds(text: &str, range: ByteRange) -> bool {
let starts = range.start == 0 || text.as_bytes()[range.start - 1] == b'\n';
let ends = range.end == text.len()
|| text.as_bytes()[range.end] == b'\n'
|| text[..range.end].ends_with('\n');
starts && ends
}
fn line_spans(text: &str) -> Vec<ByteRange> {
let mut spans = Vec::new();
let mut start = 0;
for (at, _) in text.match_indices('\n') {
spans.push(ByteRange { start, end: at });
start = at + 1;
}
if start < text.len() {
spans.push(ByteRange {
start,
end: text.len(),
});
}
spans
}
fn needle_lines(needle: &str) -> Vec<&str> {
needle.trim_end_matches('\n').split('\n').collect()
}
fn by_lines(text: &str, needle: &str, rung: Rung) -> Option<Vec<Found>> {
let wanted = needle_lines(needle);
let spans = line_spans(text);
if wanted.is_empty() || spans.len() < wanted.len() {
return None;
}
let lines: Vec<&str> = spans.iter().map(|s| &text[s.start..s.end]).collect();
let found: Vec<_> = (0..=lines.len() - wanted.len())
.filter_map(|at| {
let window = &lines[at..at + wanted.len()];
let matched = window_matches(window, &wanted, rung)?;
Some(Found {
range: ByteRange {
start: spans[at].start,
end: spans[at + wanted.len() - 1].end,
},
rung,
indent: matched.indent,
})
})
.collect();
(!found.is_empty()).then_some(found)
}
struct Matched {
indent: Option<(String, String)>,
}
fn window_matches(window: &[&str], wanted: &[&str], rung: Rung) -> Option<Matched> {
let mut pairs = window.iter().zip(wanted);
let have_indent = common_indent(window);
let want_indent = common_indent(wanted);
let matched = match rung {
Rung::TrailingWhitespace => {
return pairs
.all(|(have, want)| have.trim_end() == want.trim_end())
.then_some(Matched { indent: None });
}
Rung::Indentation => {
pairs.all(|(have, want)| dedent(have, &have_indent) == dedent(want, &want_indent))
}
Rung::Trimmed => pairs.all(|(have, want)| have.trim() == want.trim()),
_ => false,
};
matched.then_some(Matched {
indent: Some((want_indent, have_indent)),
})
}
pub fn common_indent(lines: &[&str]) -> String {
lines
.iter()
.filter(|line| !line.trim().is_empty())
.map(|line| &line[..line.len() - line.trim_start().len()])
.reduce(|left, right| {
let shared = left
.chars()
.zip(right.chars())
.take_while(|(a, b)| a == b)
.map(|(a, _)| a.len_utf8())
.sum();
&left[..shared]
})
.unwrap_or_default()
.to_string()
}
fn dedent<'a>(line: &'a str, indent: &str) -> &'a str {
if line.trim().is_empty() {
return "";
}
line.strip_prefix(indent).unwrap_or(line).trim_end()
}
fn nearest(text: &str, needle: &str) -> Option<Window> {
let wanted = needle_lines(needle).len();
let spans = line_spans(text);
if spans.is_empty() || wanted == 0 {
return None;
}
let size = wanted.min(spans.len());
let windows = spans.len() - size + 1;
if windows.saturating_mul(needle.len().max(1)) > NEAREST_BUDGET {
return None;
}
(0..windows)
.map(|at| {
let slice = &text[spans[at].start..spans[at + size - 1].end];
let score = TextDiff::from_chars(needle.trim_end_matches('\n'), slice).ratio();
(score, at, slice)
})
.max_by(|left, right| left.0.total_cmp(&right.0).then(right.1.cmp(&left.1)))
.filter(|(score, _, _)| *score > 0.0)
.map(|(_, at, slice)| Window {
line: at + 1,
text: slice.to_string(),
})
}
#[must_use]
pub fn line_of(text: &str, at: usize) -> usize {
text.as_bytes()[..at.min(text.len())]
.split(|byte| *byte == b'\n')
.count()
}