use crate::domain::SourcePosition;
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub enum SearchDirection {
Forward,
Backward,
}
impl SearchDirection {
#[must_use]
pub fn prompt(self) -> char {
match self {
Self::Forward => '/',
Self::Backward => '?',
}
}
#[must_use]
pub fn reversed(self) -> Self {
match self {
Self::Forward => Self::Backward,
Self::Backward => Self::Forward,
}
}
}
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub(crate) enum SearchScope {
Substring,
WholeWord,
}
impl SearchScope {
const fn requires_word_boundaries(self) -> bool {
matches!(self, Self::WholeWord)
}
}
#[derive(Clone, Copy)]
enum CaseSensitivity {
Sensitive,
Insensitive,
}
impl CaseSensitivity {
fn for_query(query: &str) -> Self {
if query.chars().any(char::is_uppercase) {
Self::Sensitive
} else {
Self::Insensitive
}
}
}
#[derive(Clone, Copy)]
enum AnchorInclusion {
Include,
Exclude,
}
impl AnchorInclusion {
const fn includes_anchor(self) -> bool {
matches!(self, Self::Include)
}
}
#[derive(Debug)]
struct SearchPrompt {
direction: SearchDirection,
input: String,
}
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
enum HighlightVisibility {
Hidden,
Visible,
}
impl HighlightVisibility {
const fn from_selection(selection: Option<usize>) -> Self {
if selection.is_some() {
Self::Visible
} else {
Self::Hidden
}
}
const fn is_visible(self) -> bool {
matches!(self, Self::Visible)
}
}
#[derive(Debug)]
pub(crate) struct SearchState {
prompt: Option<SearchPrompt>,
query: String,
direction: SearchDirection,
scope: SearchScope,
matches: Vec<SearchMatch>,
current: Option<usize>,
highlight_visibility: HighlightVisibility,
}
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
struct SearchMatch {
line: usize,
byte_column: usize,
byte_end: usize,
}
impl SearchMatch {
fn position(self) -> SourcePosition {
SourcePosition::new(
u32::try_from(self.line).unwrap_or(u32::MAX),
self.byte_column,
)
}
}
impl SearchState {
pub(crate) fn new() -> Self {
Self {
prompt: None,
query: String::new(),
direction: SearchDirection::Forward,
scope: SearchScope::Substring,
matches: Vec::new(),
current: None,
highlight_visibility: HighlightVisibility::Hidden,
}
}
pub(crate) fn begin(&mut self, direction: SearchDirection) {
self.prompt = Some(SearchPrompt {
direction,
input: String::new(),
});
}
pub(crate) fn push(&mut self, character: char) {
if let Some(prompt) = &mut self.prompt {
prompt.input.push(character);
}
}
pub(crate) fn pop(&mut self) {
if let Some(prompt) = &mut self.prompt
&& prompt.input.pop().is_none()
{
self.cancel_input();
}
}
pub(crate) fn cancel_input(&mut self) {
self.prompt = None;
}
pub(crate) fn clear(&mut self) {
self.prompt = None;
self.query.clear();
self.scope = SearchScope::Substring;
self.matches.clear();
self.current = None;
self.highlight_visibility = HighlightVisibility::Hidden;
}
pub(crate) fn is_input_active(&self) -> bool {
self.prompt.is_some()
}
pub(crate) fn prompt_text(&self) -> Option<(SearchDirection, &str)> {
self.prompt
.as_ref()
.map(|prompt| (prompt.direction, prompt.input.as_str()))
}
pub(crate) fn query(&self) -> &str {
&self.query
}
pub(crate) fn direction(&self) -> SearchDirection {
self.direction
}
pub(crate) fn match_count(&self) -> usize {
self.matches.len()
}
pub(crate) fn current_ordinal(&self) -> Option<usize> {
self.current.map(|index| index.saturating_add(1))
}
pub(crate) fn current_line(&self) -> Option<usize> {
self.current
.and_then(|index| self.matches.get(index).map(|found| found.line))
}
pub(crate) fn current_position(&self) -> Option<SourcePosition> {
self.current
.and_then(|index| self.matches.get(index).copied())
.map(SearchMatch::position)
}
pub(crate) fn has_highlights(&self) -> bool {
self.highlight_visibility.is_visible() && !self.matches.is_empty()
}
pub(crate) fn dismiss_highlights(&mut self) -> bool {
let dismissed = self.has_highlights();
self.highlight_visibility = HighlightVisibility::Hidden;
dismissed
}
pub(crate) fn highlighted_ranges(
&self,
line: usize,
) -> impl Iterator<Item = (std::ops::Range<usize>, bool)> + '_ {
let start = self.matches.partition_point(|found| found.line < line);
self.matches[start..]
.iter()
.enumerate()
.take_while(move |(_, found)| self.has_highlights() && found.line == line)
.map(move |(offset, found)| {
(
found.byte_column..found.byte_end,
self.current == Some(start + offset),
)
})
}
pub(crate) fn confirm<'a>(
&mut self,
values: impl IntoIterator<Item = &'a str>,
anchor: usize,
) -> Option<usize> {
let prompt = self.prompt.take()?;
self.direction = prompt.direction;
if !prompt.input.is_empty() {
self.query = prompt.input;
self.scope = SearchScope::Substring;
}
self.matches = matching_positions(values, &self.query, self.scope);
self.current = select_match(
&self.matches,
(
anchor,
if self.direction == SearchDirection::Backward {
usize::MAX
} else {
0
},
),
self.direction,
AnchorInclusion::Include,
);
self.highlight_visibility = HighlightVisibility::from_selection(self.current);
self.current_line()
}
pub(crate) fn confirm_position<'a>(
&mut self,
values: impl IntoIterator<Item = &'a str>,
anchor: SourcePosition,
) -> Option<SourcePosition> {
let prompt = self.prompt.take()?;
self.direction = prompt.direction;
if !prompt.input.is_empty() {
self.query = prompt.input;
self.scope = SearchScope::Substring;
}
self.matches = matching_positions(values, &self.query, self.scope);
self.current = select_match(
&self.matches,
(
usize::try_from(anchor.line()).unwrap_or(usize::MAX),
anchor.byte_column(),
),
self.direction,
AnchorInclusion::Exclude,
);
self.highlight_visibility = HighlightVisibility::from_selection(self.current);
self.current_position()
}
pub(crate) fn select_next(&mut self, direction: SearchDirection) -> Option<usize> {
self.select_next_position(direction, 1)
.map(|position| usize::try_from(position.line()).unwrap_or(usize::MAX))
}
pub(crate) fn select_next_position(
&mut self,
direction: SearchDirection,
count: usize,
) -> Option<SourcePosition> {
let anchor = self.current_position().unwrap_or(SourcePosition::new(0, 0));
self.select_from(anchor, direction, count)
}
pub(crate) fn repeat_position<'a>(
&mut self,
values: impl IntoIterator<Item = &'a str>,
anchor: SourcePosition,
direction: SearchDirection,
count: usize,
) -> Option<SourcePosition> {
self.matches = matching_positions(values, &self.query, self.scope);
self.select_from(anchor, direction, count)
}
fn select_from(
&mut self,
anchor: SourcePosition,
direction: SearchDirection,
count: usize,
) -> Option<SourcePosition> {
let anchor = (
usize::try_from(anchor.line()).unwrap_or(usize::MAX),
anchor.byte_column(),
);
self.current = select_match(&self.matches, anchor, direction, AnchorInclusion::Exclude);
if let Some(first) = self.current {
let len = self.matches.len();
let offset = count.max(1).saturating_sub(1) % len;
self.current = Some(match direction {
SearchDirection::Forward => (first + offset) % len,
SearchDirection::Backward => (first + len - offset) % len,
});
}
self.highlight_visibility = HighlightVisibility::from_selection(self.current);
self.current_position()
}
pub(crate) fn search_word<'a>(
&mut self,
values: impl IntoIterator<Item = &'a str>,
query: &str,
scope: SearchScope,
anchor: SourcePosition,
direction: SearchDirection,
count: usize,
) -> Option<SourcePosition> {
self.prompt = None;
query.clone_into(&mut self.query);
self.direction = direction;
self.scope = scope;
self.matches = matching_positions(values, query, scope);
self.select_from(anchor, direction, count)
}
}
#[cfg(test)]
fn matching_indices<'a>(
values: impl IntoIterator<Item = &'a str>,
query: &str,
) -> Vec<SearchMatch> {
matching_positions(values, query, SearchScope::Substring)
}
fn matching_positions<'a>(
values: impl IntoIterator<Item = &'a str>,
query: &str,
scope: SearchScope,
) -> Vec<SearchMatch> {
if query.is_empty() {
return Vec::new();
}
let case_sensitivity = CaseSensitivity::for_query(query);
values
.into_iter()
.enumerate()
.flat_map(|(line, value)| {
match_starts(value, query, case_sensitivity)
.into_iter()
.filter(move |(start, end)| {
!scope.requires_word_boundaries() || is_whole_word(value, *start, *end)
})
.map(move |(byte_column, byte_end)| SearchMatch {
line,
byte_column,
byte_end,
})
})
.collect()
}
fn match_starts(
value: &str,
query: &str,
case_sensitivity: CaseSensitivity,
) -> Vec<(usize, usize)> {
if matches!(case_sensitivity, CaseSensitivity::Sensitive) {
return overlapping_matches(value, query);
}
let folded_query = query.to_lowercase();
if value.is_ascii() {
return overlapping_matches(&value.to_ascii_lowercase(), &folded_query);
}
let mut folded = String::with_capacity(value.len());
let mut boundaries = Vec::new();
for (byte, character) in value.char_indices() {
boundaries.push((folded.len(), byte));
folded.extend(character.to_lowercase());
}
boundaries.push((folded.len(), value.len()));
overlapping_matches(&folded, &folded_query)
.into_iter()
.filter_map(|(start, end)| {
let start = boundaries
.binary_search_by_key(&start, |(folded, _)| *folded)
.ok()?;
let end = boundaries
.binary_search_by_key(&end, |(folded, _)| *folded)
.ok()?;
Some((boundaries[start].1, boundaries[end].1))
})
.collect()
}
fn overlapping_matches(value: &str, query: &str) -> Vec<(usize, usize)> {
let mut matches = Vec::new();
let mut offset = 0;
while let Some(found) = value[offset..].find(query) {
let start = offset + found;
matches.push((start, start + query.len()));
offset = start + value[start..].chars().next().map_or(1, char::len_utf8);
if offset >= value.len() {
break;
}
}
matches
}
fn is_whole_word(value: &str, start: usize, end: usize) -> bool {
let before = value[..start].chars().next_back();
let after = value[end..].chars().next();
before.is_none_or(|character| !is_keyword(character))
&& after.is_none_or(|character| !is_keyword(character))
}
fn is_keyword(character: char) -> bool {
character.is_alphanumeric() || character == '_'
}
fn select_match(
matches: &[SearchMatch],
anchor: (usize, usize),
direction: SearchDirection,
anchor_inclusion: AnchorInclusion,
) -> Option<usize> {
if matches.is_empty() {
return None;
}
match direction {
SearchDirection::Forward => matches
.iter()
.position(|found| {
let found = (found.line, found.byte_column);
if anchor_inclusion.includes_anchor() {
found >= anchor
} else {
found > anchor
}
})
.or(Some(0)),
SearchDirection::Backward => matches
.iter()
.rposition(|found| {
let found = (found.line, found.byte_column);
if anchor_inclusion.includes_anchor() {
found <= anchor
} else {
found < anchor
}
})
.or_else(|| matches.len().checked_sub(1)),
}
}
#[cfg(test)]
mod tests {
use super::{CaseSensitivity, SearchDirection, SearchScope, SearchState, matching_indices};
#[test]
fn matching_is_case_insensitive_unless_the_query_contains_uppercase() {
let values = ["alpha", "ALPHA", "Alpha"];
assert_eq!(
matching_indices(values, "alpha")
.into_iter()
.map(|found| found.line)
.collect::<Vec<_>>(),
vec![0, 1, 2]
);
assert_eq!(
matching_indices(values, "Alpha")
.into_iter()
.map(|found| found.line)
.collect::<Vec<_>>(),
vec![2]
);
}
#[test]
fn forward_and_backward_search_wrap_and_repeat() {
let values = ["zero", "match one", "two", "match three"];
let mut search = SearchState::new();
search.begin(SearchDirection::Forward);
for character in "match".chars() {
search.push(character);
}
assert_eq!(search.confirm(values, 2), Some(3));
assert_eq!(search.select_next(SearchDirection::Forward), Some(1));
assert_eq!(search.select_next(SearchDirection::Backward), Some(3));
}
#[test]
fn an_empty_prompt_repeats_the_previous_query() {
let values = ["first hit", "second hit"];
let mut search = SearchState::new();
search.begin(SearchDirection::Forward);
for character in "hit".chars() {
search.push(character);
}
assert_eq!(search.confirm(values, 0), Some(0));
search.begin(SearchDirection::Backward);
assert_eq!(search.confirm(values, 1), Some(1));
assert_eq!(search.query(), "hit");
}
#[test]
fn backspace_cancels_only_when_the_prompt_was_already_empty() {
for direction in [SearchDirection::Forward, SearchDirection::Backward] {
for input in ["a", "日本 /?", " ", "/", "?"] {
let mut search = SearchState::new();
search.begin(direction);
for character in input.chars() {
search.push(character);
}
let mut remaining = input.to_owned();
while !remaining.is_empty() {
remaining.pop();
search.pop();
assert_eq!(search.prompt_text(), Some((direction, remaining.as_str())));
}
search.push('新');
assert_eq!(search.prompt_text(), Some((direction, "新")));
search.pop();
assert!(search.is_input_active());
search.pop();
assert!(!search.is_input_active());
assert!(search.query().is_empty());
assert_eq!(search.match_count(), 0);
}
}
}
#[test]
fn positional_search_starts_after_or_before_the_cursor() {
let values = ["cat cat"];
let mut search = SearchState::new();
search.begin(SearchDirection::Forward);
for character in "cat".chars() {
search.push(character);
}
assert_eq!(
search.confirm_position(values, crate::domain::SourcePosition::new(0, 0)),
Some(crate::domain::SourcePosition::new(0, 4))
);
search.begin(SearchDirection::Backward);
assert_eq!(
search.confirm_position(values, crate::domain::SourcePosition::new(0, 4)),
Some(crate::domain::SourcePosition::new(0, 0))
);
}
#[test]
fn oversized_search_counts_wrap_without_iterating_the_count() {
let mut search = SearchState::new();
assert_eq!(
search.search_word(
["cat cat cat"],
"cat",
SearchScope::WholeWord,
crate::domain::SourcePosition::new(0, 0),
SearchDirection::Forward,
usize::MAX
),
Some(crate::domain::SourcePosition::new(0, (usize::MAX % 3) * 4))
);
assert_eq!(
search.repeat_position(
["cat cat cat"],
crate::domain::SourcePosition::new(0, 0),
SearchDirection::Backward,
usize::MAX
),
Some(crate::domain::SourcePosition::new(
0,
((3 - usize::MAX % 3) % 3) * 4
))
);
}
#[test]
fn smart_case_matches_keep_unicode_offsets_and_overlapping_hits() {
assert_eq!(
super::match_starts("界İ cat CAT", "cat", CaseSensitivity::Insensitive,),
vec![(6, 9), (10, 13)]
);
assert_eq!(
super::match_starts("İi", "i\u{307}", CaseSensitivity::Insensitive),
vec![(0, 2)]
);
assert_eq!(
super::match_starts("aaa", "aa", CaseSensitivity::Insensitive),
vec![(0, 2), (1, 3)]
);
assert_eq!(
super::match_starts("AAA", "AA", CaseSensitivity::Sensitive),
vec![(0, 2), (1, 3)]
);
let line = "a".repeat(100_000);
let query = format!("{}b", "a".repeat(1_000));
assert!(super::match_starts(&line, &query, CaseSensitivity::Insensitive).is_empty());
}
#[test]
fn word_search_distinguishes_same_line_matches_and_word_boundaries() {
let values = ["cat concatenate cat", "CAT"];
let mut search = SearchState::new();
assert_eq!(
search.search_word(
values,
"cat",
SearchScope::WholeWord,
crate::domain::SourcePosition::new(0, 0),
SearchDirection::Forward,
1,
),
Some(crate::domain::SourcePosition::new(0, 16))
);
assert_eq!(
search.select_next_position(SearchDirection::Forward, 1),
Some(crate::domain::SourcePosition::new(1, 0))
);
assert_eq!(
search.search_word(
values,
"cat",
SearchScope::Substring,
crate::domain::SourcePosition::new(0, 0),
SearchDirection::Forward,
1,
),
Some(crate::domain::SourcePosition::new(0, 7))
);
}
}