tawasuyu/llimphi

1//! Búsqueda sobre el `Scrollback` — base de Ctrl+F del SDD-TERMINAL §Fase 3.
2//!
3//! Diseño: barata pero correcta. Recorre todas las líneas del store y
4//! reporta los rangos `(line, start_byte, end_byte)` de cada ocurrencia.
5//! Sin streaming, sin índice — para los típicos cientos de miles de líneas
6//! del shell es suficiente (un `memmem` por línea, lineal en el contenido).
7//!
8//! Para infinitos masivos (millones de líneas), el `find` ya es O(N) en el
9//! contenido, no en el render — el scroll y la pintada siguen siendo O(1).
10//! Si en algún momento aprieta, se puede pre-indexar n-gramas; no hoy.
11//!
12//! Case-insensitive: lowercase ambos lados (sin Unicode-aware folding por
13//! ahora — ASCII alcanza para el caso shell típico).
14
15use crate::store::Scrollback;
16
17/// Una coincidencia de búsqueda en el scrollback. `start`/`end` son offsets
18/// **en bytes** UTF-8 del texto de la línea (slice-safe: el caller puede
19/// hacer `&text[start..end]` sin clampear).
20#[derive(Debug, Clone, Copy, PartialEq, Eq)]
21pub struct FindMatch {
22    pub line: usize,
23    pub start: usize,
24    pub end: usize,
25}
26
27/// Opciones de búsqueda. Defaults: case-sensitive, query literal (sin regex).
28#[derive(Debug, Clone, Copy, Default)]
29pub struct FindOpts {
30    /// `true` = lowercase ambos lados antes de comparar (ASCII fold).
31    pub case_insensitive: bool,
32}
33
34/// Busca todas las ocurrencias **no superpuestas** de `query` en el `store`,
35/// línea por línea, en orden. Empty query → `Vec::new()` (paridad con la
36/// barra de find de la mayoría de editores: vacío = "no hay nada que
37/// resaltar"). El consumo es O(total_bytes) en el contenido del store.
38///
39/// Las coincidencias caen siempre en límites de char UTF-8 (vienen del
40/// scanner de bytes y se snap-ean al borde más cercano hacia abajo si la
41/// query atraviesa una codepoint, que con `find` literal no debería pasar).
42pub fn find_matches(store: &Scrollback, query: &str, opts: FindOpts) -> Vec<FindMatch> {
43    if query.is_empty() {
44        return Vec::new();
45    }
46    let needle = if opts.case_insensitive {
47        query.to_ascii_lowercase()
48    } else {
49        query.to_string()
50    };
51    let mut out = Vec::new();
52    for line in 0..store.len() {
53        let Some(text) = store.line(line) else { continue };
54        let haystack_owned;
55        let haystack: &str = if opts.case_insensitive {
56            haystack_owned = text.to_ascii_lowercase();
57            &haystack_owned
58        } else {
59            text
60        };
61        let mut cursor = 0usize;
62        while cursor < haystack.len() {
63            let Some(rel) = haystack[cursor..].find(&needle) else {
64                break;
65            };
66            let start = cursor + rel;
67            let end = start + needle.len();
68            out.push(FindMatch { line, start, end });
69            // Avance no-superposición: una ocurrencia consume su rango, la
70            // siguiente arranca DESPUÉS. Si la query es vacía no llegamos
71            // aquí (ya filtrado arriba), así que `end > start` siempre.
72            cursor = end;
73        }
74    }
75    out
76}
77
78/// Avanza al siguiente match desde `current` (envuelve al primero si está
79/// al final). Si `matches` está vacío devuelve `None`. `None` en `current`
80/// equivale a "no hay actual" → arranca por el primero.
81pub fn next_match(matches: &[FindMatch], current: Option<usize>) -> Option<usize> {
82    if matches.is_empty() {
83        return None;
84    }
85    Some(match current {
86        None => 0,
87        Some(i) => (i + 1) % matches.len(),
88    })
89}
90
91/// Retrocede al match previo desde `current` (envuelve al último si está
92/// al principio). Mismas semánticas que [`next_match`].
93pub fn prev_match(matches: &[FindMatch], current: Option<usize>) -> Option<usize> {
94    if matches.is_empty() {
95        return None;
96    }
97    Some(match current {
98        None => matches.len() - 1,
99        Some(i) => (i + matches.len() - 1) % matches.len(),
100    })
101}
102
103#[cfg(test)]
104mod tests {
105    use super::*;
106
107    fn store_of(lines: &[&str]) -> Scrollback {
108        let mut s = Scrollback::new(0);
109        for l in lines {
110            s.push_line(l);
111        }
112        s
113    }
114
115    #[test]
116    fn query_vacia_no_devuelve_nada() {
117        let s = store_of(&["foo", "bar"]);
118        assert_eq!(find_matches(&s, "", FindOpts::default()), Vec::new());
119    }
120
121    #[test]
122    fn una_ocurrencia_por_linea() {
123        let s = store_of(&["foo bar baz", "qux foo quux"]);
124        let m = find_matches(&s, "foo", FindOpts::default());
125        assert_eq!(
126            m,
127            vec![
128                FindMatch { line: 0, start: 0, end: 3 },
129                FindMatch { line: 1, start: 4, end: 7 },
130            ]
131        );
132    }
133
134    #[test]
135    fn varias_ocurrencias_en_la_misma_linea_no_se_superponen() {
136        // "aaa" → en "aaaaa" hay 1 match en 0..3 y otro en 3..6 (no en 1..4).
137        let s = store_of(&["aaaaaa"]);
138        let m = find_matches(&s, "aaa", FindOpts::default());
139        assert_eq!(
140            m,
141            vec![
142                FindMatch { line: 0, start: 0, end: 3 },
143                FindMatch { line: 0, start: 3, end: 6 },
144            ]
145        );
146    }
147
148    #[test]
149    fn case_sensitive_por_defecto() {
150        let s = store_of(&["Foo", "FOO", "foo"]);
151        let m = find_matches(&s, "foo", FindOpts::default());
152        assert_eq!(m, vec![FindMatch { line: 2, start: 0, end: 3 }]);
153    }
154
155    #[test]
156    fn case_insensitive_matchea_todas_las_variantes() {
157        let s = store_of(&["Foo", "FOO", "foo"]);
158        let m = find_matches(&s, "foo", FindOpts { case_insensitive: true });
159        assert_eq!(m.len(), 3);
160        assert_eq!(m[0].line, 0);
161        assert_eq!(m[1].line, 1);
162        assert_eq!(m[2].line, 2);
163    }
164
165    #[test]
166    fn no_match_devuelve_vec_vacio() {
167        let s = store_of(&["uno", "dos"]);
168        assert!(find_matches(&s, "xyz", FindOpts::default()).is_empty());
169    }
170
171    #[test]
172    fn match_utf8_funciona_al_ser_busqueda_literal_byte_a_byte() {
173        // "café" tiene 'é' = 2 bytes. Buscamos "afé" — match en bytes 1..5.
174        let s = store_of(&["café"]);
175        let m = find_matches(&s, "afé", FindOpts::default());
176        assert_eq!(m, vec![FindMatch { line: 0, start: 1, end: 5 }]);
177    }
178
179    #[test]
180    fn next_match_envuelve_al_primero() {
181        let m = vec![
182            FindMatch { line: 0, start: 0, end: 1 },
183            FindMatch { line: 1, start: 0, end: 1 },
184        ];
185        assert_eq!(next_match(&m, None), Some(0));
186        assert_eq!(next_match(&m, Some(0)), Some(1));
187        assert_eq!(next_match(&m, Some(1)), Some(0));
188    }
189
190    #[test]
191    fn prev_match_envuelve_al_ultimo() {
192        let m = vec![
193            FindMatch { line: 0, start: 0, end: 1 },
194            FindMatch { line: 1, start: 0, end: 1 },
195        ];
196        assert_eq!(prev_match(&m, None), Some(1));
197        assert_eq!(prev_match(&m, Some(0)), Some(1));
198        assert_eq!(prev_match(&m, Some(1)), Some(0));
199    }
200
201    #[test]
202    fn next_y_prev_en_lista_vacia_son_none() {
203        let m: Vec<FindMatch> = Vec::new();
204        assert_eq!(next_match(&m, None), None);
205        assert_eq!(next_match(&m, Some(0)), None);
206        assert_eq!(prev_match(&m, None), None);
207    }
208}