typ_buffer/
search.rs

1//! Literal, line-scoped search.
2//!
3//! Line-scoped on purpose: a match never spans a line break, so every result
4//! is expressible as `(line, grapheme)` without a second coordinate system,
5//! and that is what a user typing into a search box means anyway. Regex
6//! belongs behind this same `SearchQuery` type later, not beside it.
7
8use unicode_segmentation::UnicodeSegmentation;
9
10#[derive(Debug, Clone, PartialEq, Eq)]
11pub struct SearchQuery {
12    pub needle: String,
13    pub case_sensitive: bool,
14}
15
16impl SearchQuery {
17    pub fn new(needle: impl Into<String>, case_sensitive: bool) -> Self {
18        Self {
19            needle: needle.into(),
20            case_sensitive,
21        }
22    }
23}
24
25/// Compare two graphemes, optionally folding case, without allocating.
26///
27/// `to_lowercase` on a `char` yields an iterator precisely so this can be done
28/// lazily — folding into `String`s first would allocate twice per comparison,
29/// which on a long line is thousands of allocations for one keystroke.
30fn grapheme_eq(a: &str, b: &str, case_sensitive: bool) -> bool {
31    if case_sensitive {
32        return a == b;
33    }
34    a.chars()
35        .flat_map(char::to_lowercase)
36        .eq(b.chars().flat_map(char::to_lowercase))
37}
38
39/// Grapheme index pairs of every non-overlapping match in one line.
40///
41/// Indices come out in graphemes directly, so nothing has to map byte offsets
42/// back afterwards — and case folding, which can change a string's byte length,
43/// never gets the chance to shift them.
44pub fn find_in_line(line: &str, query: &SearchQuery) -> Vec<(usize, usize)> {
45    if query.needle.is_empty() {
46        return Vec::new();
47    }
48    let needle: Vec<&str> = query.needle.graphemes(true).collect();
49    find_in_line_with(line, &needle, query)
50}
51
52/// `find_in_line` with the needle already split.
53///
54/// Splitting it is per-search work, not per-line work: a whole-buffer scan calls
55/// this once per line, and rebuilding the needle each time was one allocation
56/// per line for a value that never changes. That, plus collecting the haystack
57/// into a `Vec<&str>`, was what put a 50k-line search at 141 ms against a 16 ms
58/// keystroke budget. Neither allocation survives here.
59pub(crate) fn find_in_line_with(
60    line: &str,
61    needle: &[&str],
62    query: &SearchQuery,
63) -> Vec<(usize, usize)> {
64    if needle.is_empty() {
65        return Vec::new();
66    }
67
68    // A byte-level containment check, memchr-backed and allocation-free. Most
69    // lines in a real search hold no match at all, and this retires them before
70    // any grapheme segmentation happens. Case-sensitive only: folding can change
71    // a string's byte length, so the bytes of a case-insensitive needle are not
72    // a sound precondition for its matches.
73    if query.case_sensitive && !line.contains(query.needle.as_str()) {
74        return Vec::new();
75    }
76
77    // Segmenting the line once and indexing the result beats re-segmenting from
78    // each candidate position: building a `Graphemes` iterator per position cost
79    // more than the single `Vec` of borrowed slices it was meant to avoid,
80    // measured at 190 ms against 141 ms on a 50k-line scan.
81    let haystack: Vec<&str> = line.graphemes(true).collect();
82    if needle.len() > haystack.len() {
83        return Vec::new();
84    }
85
86    let mut hits = Vec::new();
87    let mut i = 0usize;
88    while i + needle.len() <= haystack.len() {
89        let matched = haystack[i..i + needle.len()]
90            .iter()
91            .zip(needle)
92            .all(|(h, n)| grapheme_eq(h, n, query.case_sensitive));
93        if matched {
94            hits.push((i, i + needle.len()));
95            // Advance past the match. Overlapping hits would let a replace-all
96            // rewrite text it had already rewritten.
97            i += needle.len();
98        } else {
99            i += 1;
100        }
101    }
102    hits
103}
typ_buffer/search.rs

typ_buffer/
search.rs
