sergio/takana
> Una distribución Linux construida con un laboratorio funcional y hermético en el > sótano, y una terminal mutable, clásica y anárquica en el piso de arriba — diseñada > desde el suelo para que una IA programadora entienda, modifique y co…
el awk se llama akllay: `qillqa` estaba TOMADO en tawasuyu, y no lo comprobé
1//! Motor de expresiones regulares ERE (POSIX.1-2024 §9.4), propio.
2//!
3//! # Por qué propio y no un crate
4//!
5//! La semántica de POSIX es **leftmost-longest**: entre todas las coincidencias que empiezan en la
6//! posición más a la izquierda, gana la MÁS LARGA. La familia Perl —y con ella el crate `regex` en
7//! su modo por defecto— usa leftmost-first: para `a|ab` sobre `"ab"`, POSIX devuelve `ab` y Perl
8//! devuelve `a`. En un awk eso no es un detalle académico: decide qué borra un `sub()`, dónde parte
9//! un `split()` y qué valen `RSTART`/`RLENGTH`. Adoptar un motor ajeno sería adoptar su semántica.
10//!
11//! # Cómo funciona
12//!
13//! Construcción de Thompson: el patrón se compila a un programa de instrucciones y se simula con un
14//! CONJUNTO de hilos que avanzan a la vez, un carácter por paso. No hay retroceso, así que no hay
15//! explosión exponencial —`(a*)*b` contra sesenta `a` termina igual de rápido que cualquier otra
16//! cosa— y quedarse con el final más lejano alcanzado da el «más largo» de POSIX sin esfuerzo extra.
17//!
18//! Trabaja sobre `char`, no sobre bytes: en awk los índices de `substr`, `index`, `match` y
19//! `RSTART` se cuentan en caracteres, y con UTF-8 en el fichero de entrada contar bytes daría
20//! posiciones que no se pueden usar para cortar.
21
22/// Una instrucción del programa compilado.
23#[derive(Debug, Clone)]
24enum Inst {
25 /// Consume exactamente este carácter.
26 Char(char),
27 /// Consume cualquier carácter (`.`). En awk `.` SÍ casa con `\n` (no hay modo multilínea).
28 Any,
29 /// Consume un carácter si pertenece (o no, si `negada`) al conjunto.
30 Clase { partes: Vec<Parte>, negada: bool },
31 /// Bifurca: sigue por las dos ramas. El orden no importa porque no hay preferencia (longest).
32 Split(usize, usize),
33 /// Salta.
34 Jmp(usize),
35 /// Ancla de principio de cadena (`^`).
36 Bol,
37 /// Ancla de final de cadena (`$`).
38 Eol,
39 /// Aceptación.
40 Match,
41}
42
43/// Un trozo de una clase `[...]`.
44#[derive(Debug, Clone)]
45enum Parte {
46 Uno(char),
47 Rango(char, char),
48 /// `[:alpha:]` y compañía, resueltas por función para no materializar Unicode entero.
49 Nombrada(Nombrada),
50}
51
52#[derive(Debug, Clone, Copy, PartialEq)]
53enum Nombrada {
54 Alpha, Digit, Alnum, Upper, Lower, Space, Blank, Punct, Print, Graph, Cntrl, Xdigit,
55}
56
57impl Nombrada {
58 fn de(nombre: &str) -> Option<Nombrada> {
59 Some(match nombre {
60 "alpha" => Nombrada::Alpha, "digit" => Nombrada::Digit, "alnum" => Nombrada::Alnum,
61 "upper" => Nombrada::Upper, "lower" => Nombrada::Lower, "space" => Nombrada::Space,
62 "blank" => Nombrada::Blank, "punct" => Nombrada::Punct, "print" => Nombrada::Print,
63 "graph" => Nombrada::Graph, "cntrl" => Nombrada::Cntrl, "xdigit" => Nombrada::Xdigit,
64 _ => return None,
65 })
66 }
67 fn casa(self, c: char) -> bool {
68 match self {
69 Nombrada::Alpha => c.is_alphabetic(),
70 Nombrada::Digit => c.is_ascii_digit(),
71 Nombrada::Alnum => c.is_alphanumeric(),
72 Nombrada::Upper => c.is_uppercase(),
73 Nombrada::Lower => c.is_lowercase(),
74 Nombrada::Space => c.is_whitespace(),
75 Nombrada::Blank => c == ' ' || c == '\t',
76 Nombrada::Punct => c.is_ascii_punctuation(),
77 Nombrada::Print => !c.is_control(),
78 Nombrada::Graph => !c.is_control() && !c.is_whitespace(),
79 Nombrada::Cntrl => c.is_control(),
80 Nombrada::Xdigit => c.is_ascii_hexdigit(),
81 }
82 }
83}
84
85/// Árbol del patrón, paso intermedio entre el texto y el programa.
86#[derive(Debug, Clone)]
87enum Nodo {
88 Vacio,
89 Char(char),
90 Any,
91 Clase { partes: Vec<Parte>, negada: bool },
92 Bol,
93 Eol,
94 Cat(Box<Nodo>, Box<Nodo>),
95 Alt(Box<Nodo>, Box<Nodo>),
96 Estrella(Box<Nodo>),
97 Mas(Box<Nodo>),
98 Opcional(Box<Nodo>),
99 /// `{n,m}`: se expande al compilar. `hasta = None` es `{n,}`.
100 Repite(Box<Nodo>, u32, Option<u32>),
101}
102
103pub struct Regex {
104 prog: Vec<Inst>,
105 /// El patrón original, para mensajes de error y para `Regex::fuente`.
106 fuente: String,
107}
108
109struct Analizador<'a> {
110 p: &'a [char],
111 i: usize,
112}
113
114impl<'a> Analizador<'a> {
115 fn fin(&self) -> bool { self.i >= self.p.len() }
116 fn ver(&self) -> Option<char> { self.p.get(self.i).copied() }
117 fn tomar(&mut self) -> Option<char> { let c = self.ver(); if c.is_some() { self.i += 1; } c }
118
119 /// alternancia := concatenación ('|' concatenación)*
120 fn alternancia(&mut self) -> Result<Nodo, String> {
121 let mut izq = self.concatenacion()?;
122 while self.ver() == Some('|') {
123 self.i += 1;
124 let der = self.concatenacion()?;
125 izq = Nodo::Alt(Box::new(izq), Box::new(der));
126 }
127 Ok(izq)
128 }
129
130 /// concatenación := repetición*
131 fn concatenacion(&mut self) -> Result<Nodo, String> {
132 let mut acc: Option<Nodo> = None;
133 while !self.fin() && self.ver() != Some('|') && self.ver() != Some(')') {
134 let n = self.repeticion()?;
135 acc = Some(match acc {
136 None => n,
137 Some(a) => Nodo::Cat(Box::new(a), Box::new(n)),
138 });
139 }
140 Ok(acc.unwrap_or(Nodo::Vacio))
141 }
142
143 /// repetición := átomo ('*' | '+' | '?' | '{n,m}')*
144 fn repeticion(&mut self) -> Result<Nodo, String> {
145 let mut n = self.atomo()?;
146 loop {
147 match self.ver() {
148 Some('*') => { self.i += 1; n = Nodo::Estrella(Box::new(n)); }
149 Some('+') => { self.i += 1; n = Nodo::Mas(Box::new(n)); }
150 Some('?') => { self.i += 1; n = Nodo::Opcional(Box::new(n)); }
151 Some('{') => {
152 // Sólo es intervalo si lo que sigue es un dígito: en ERE un `{` suelto es
153 // literal, y hay guiones que escriben `/x{/` sin escapar.
154 if !matches!(self.p.get(self.i + 1), Some(c) if c.is_ascii_digit()) { break; }
155 let guardado = self.i;
156 self.i += 1;
157 match self.intervalo() {
158 Ok((desde, hasta)) => n = Nodo::Repite(Box::new(n), desde, hasta),
159 Err(_) => { self.i = guardado; break; }
160 }
161 }
162 _ => break,
163 }
164 }
165 Ok(n)
166 }
167
168 fn intervalo(&mut self) -> Result<(u32, Option<u32>), String> {
169 let mut desde = String::new();
170 while matches!(self.ver(), Some(c) if c.is_ascii_digit()) { desde.push(self.tomar().unwrap()); }
171 if desde.is_empty() { return Err("intervalo sin mínimo".into()); }
172 let d: u32 = desde.parse().map_err(|_| "intervalo demasiado grande".to_string())?;
173 match self.ver() {
174 Some('}') => { self.i += 1; Ok((d, Some(d))) }
175 Some(',') => {
176 self.i += 1;
177 let mut hasta = String::new();
178 while matches!(self.ver(), Some(c) if c.is_ascii_digit()) { hasta.push(self.tomar().unwrap()); }
179 if self.ver() != Some('}') { return Err("intervalo sin cerrar".into()); }
180 self.i += 1;
181 if hasta.is_empty() { Ok((d, None)) }
182 else {
183 let h: u32 = hasta.parse().map_err(|_| "intervalo demasiado grande".to_string())?;
184 if h < d { return Err("intervalo con máximo menor que el mínimo".into()); }
185 Ok((d, Some(h)))
186 }
187 }
188 _ => Err("intervalo mal formado".into()),
189 }
190 }
191
192 fn atomo(&mut self) -> Result<Nodo, String> {
193 match self.tomar() {
194 None => Ok(Nodo::Vacio),
195 Some('(') => {
196 let dentro = self.alternancia()?;
197 if self.tomar() != Some(')') { return Err("falta `)`".into()); }
198 Ok(dentro)
199 }
200 Some('[') => self.clase(),
201 Some('.') => Ok(Nodo::Any),
202 Some('^') => Ok(Nodo::Bol),
203 Some('$') => Ok(Nodo::Eol),
204 Some('\\') => match self.tomar() {
205 None => Err("`\\` al final del patrón".into()),
206 // Los escapes de C que awk reconoce dentro de una ERE.
207 Some('n') => Ok(Nodo::Char('\n')),
208 Some('t') => Ok(Nodo::Char('\t')),
209 Some('r') => Ok(Nodo::Char('\r')),
210 Some('f') => Ok(Nodo::Char('\x0c')),
211 Some('b') => Ok(Nodo::Char('\x08')),
212 Some('v') => Ok(Nodo::Char('\x0b')),
213 Some('a') => Ok(Nodo::Char('\x07')),
214 Some('/') => Ok(Nodo::Char('/')),
215 Some(c) => Ok(Nodo::Char(c)),
216 },
217 Some(c) => Ok(Nodo::Char(c)),
218 }
219 }
220
221 /// `[abc]`, `[^a-z]`, `[[:digit:]]`. Un `]` justo tras el `[` (o tras `[^`) es LITERAL.
222 fn clase(&mut self) -> Result<Nodo, String> {
223 let mut negada = false;
224 if self.ver() == Some('^') { negada = true; self.i += 1; }
225 let mut partes: Vec<Parte> = Vec::new();
226 let mut primero = true;
227 loop {
228 let c = match self.tomar() {
229 None => return Err("clase `[` sin cerrar".into()),
230 Some(']') if !primero => break,
231 Some(c) => c,
232 };
233 primero = false;
234 // `[:alpha:]` dentro de la clase.
235 if c == '[' && self.ver() == Some(':') {
236 let guardado = self.i;
237 self.i += 1;
238 let mut nombre = String::new();
239 while matches!(self.ver(), Some(c) if c != ':' && c != ']') { nombre.push(self.tomar().unwrap()); }
240 if self.ver() == Some(':') && self.p.get(self.i + 1) == Some(&']') {
241 self.i += 2;
242 match Nombrada::de(&nombre) {
243 Some(n) => { partes.push(Parte::Nombrada(n)); continue; }
244 None => return Err(format!("clase de caracteres desconocida: [:{nombre}:]")),
245 }
246 }
247 self.i = guardado; // no era una clase nombrada: el `[` es literal
248 }
249 let c = if c == '\\' {
250 match self.tomar() {
251 None => return Err("`\\` al final de una clase".into()),
252 Some('n') => '\n', Some('t') => '\t', Some('r') => '\r',
253 Some('f') => '\x0c', Some('b') => '\x08', Some('v') => '\x0b', Some('a') => '\x07',
254 Some(o) => o,
255 }
256 } else { c };
257 // Rango `a-z`, salvo que el `-` sea el último carácter de la clase.
258 if self.ver() == Some('-') && self.p.get(self.i + 1).map_or(false, |&d| d != ']') {
259 self.i += 1;
260 let hasta = match self.tomar() {
261 None => return Err("rango sin final".into()),
262 Some('\\') => self.tomar().ok_or("`\\` al final de un rango")?,
263 Some(d) => d,
264 };
265 partes.push(Parte::Rango(c, hasta));
266 } else {
267 partes.push(Parte::Uno(c));
268 }
269 }
270 Ok(Nodo::Clase { partes, negada })
271 }
272}
273
274/// Emite el programa. Devuelve el índice de la primera instrucción del fragmento.
275fn emitir(prog: &mut Vec<Inst>, n: &Nodo) {
276 match n {
277 Nodo::Vacio => {}
278 Nodo::Char(c) => prog.push(Inst::Char(*c)),
279 Nodo::Any => prog.push(Inst::Any),
280 Nodo::Bol => prog.push(Inst::Bol),
281 Nodo::Eol => prog.push(Inst::Eol),
282 Nodo::Clase { partes, negada } => prog.push(Inst::Clase { partes: partes.clone(), negada: *negada }),
283 Nodo::Cat(a, b) => { emitir(prog, a); emitir(prog, b); }
284 Nodo::Alt(a, b) => {
285 let split = prog.len();
286 prog.push(Inst::Jmp(0)); // reservado, se reescribe como Split
287 emitir(prog, a);
288 let jmp = prog.len();
289 prog.push(Inst::Jmp(0));
290 let inicio_b = prog.len();
291 emitir(prog, b);
292 let fin = prog.len();
293 prog[split] = Inst::Split(split + 1, inicio_b);
294 prog[jmp] = Inst::Jmp(fin);
295 }
296 Nodo::Estrella(a) => {
297 let split = prog.len();
298 prog.push(Inst::Jmp(0));
299 emitir(prog, a);
300 prog.push(Inst::Jmp(split));
301 let fin = prog.len();
302 prog[split] = Inst::Split(split + 1, fin);
303 }
304 Nodo::Mas(a) => {
305 let inicio = prog.len();
306 emitir(prog, a);
307 let split = prog.len();
308 prog.push(Inst::Jmp(0));
309 let fin = prog.len();
310 prog[split] = Inst::Split(inicio, fin);
311 }
312 Nodo::Opcional(a) => {
313 let split = prog.len();
314 prog.push(Inst::Jmp(0));
315 emitir(prog, a);
316 let fin = prog.len();
317 prog[split] = Inst::Split(split + 1, fin);
318 }
319 Nodo::Repite(a, desde, hasta) => {
320 // Se expande: `x{2,4}` es `xx(x(x)?)?`. Es lo que hace cualquier motor sin contadores, y
321 // el coste es lineal en `hasta`, que en la práctica es un número pequeño.
322 for _ in 0..*desde { emitir(prog, a); }
323 match hasta {
324 None => emitir(prog, &Nodo::Estrella(a.clone())),
325 Some(h) => {
326 let opcionales = h.saturating_sub(*desde);
327 let mut splits = Vec::new();
328 for _ in 0..opcionales {
329 let s = prog.len();
330 prog.push(Inst::Jmp(0));
331 splits.push(s);
332 emitir(prog, a);
333 }
334 let fin = prog.len();
335 for s in splits { prog[s] = Inst::Split(s + 1, fin); }
336 }
337 }
338 }
339 }
340}
341
342impl Regex {
343 pub fn nueva(patron: &str) -> Result<Regex, String> {
344 let chars: Vec<char> = patron.chars().collect();
345 let mut an = Analizador { p: &chars, i: 0 };
346 let nodo = an.alternancia()?;
347 if !an.fin() {
348 return Err(format!("basura al final del patrón: `{}`", chars[an.i..].iter().collect::<String>()));
349 }
350 let mut prog = Vec::new();
351 emitir(&mut prog, &nodo);
352 prog.push(Inst::Match);
353 Ok(Regex { prog, fuente: patron.to_string() })
354 }
355
356 pub fn fuente(&self) -> &str { &self.fuente }
357
358 /// Añade un hilo y todos los alcanzables sin consumir (cierre-epsilon).
359 fn agregar(&self, lista: &mut Vec<usize>, visto: &mut [bool], pc: usize, pos: usize, largo: usize) {
360 if visto[pc] { return; }
361 visto[pc] = true;
362 match self.prog[pc] {
363 Inst::Jmp(d) => self.agregar(lista, visto, d, pos, largo),
364 Inst::Split(a, b) => {
365 self.agregar(lista, visto, a, pos, largo);
366 self.agregar(lista, visto, b, pos, largo);
367 }
368 Inst::Bol => { if pos == 0 { self.agregar(lista, visto, pc + 1, pos, largo); } }
369 Inst::Eol => { if pos == largo { self.agregar(lista, visto, pc + 1, pos, largo); } }
370 _ => lista.push(pc),
371 }
372 }
373
374 /// El final del match MÁS LARGO que empieza exactamente en `desde`, si lo hay.
375 pub fn casa_en(&self, s: &[char], desde: usize) -> Option<usize> {
376 let largo = s.len();
377 let mut visto = vec![false; self.prog.len()];
378 let mut actual: Vec<usize> = Vec::new();
379 self.agregar(&mut actual, &mut visto, 0, desde, largo);
380 let mut mejor: Option<usize> = None;
381 let mut pos = desde;
382 loop {
383 // ¿Alguno acepta aquí? Nos quedamos con el más lejano: eso es «longest».
384 if actual.iter().any(|&pc| matches!(self.prog[pc], Inst::Match)) {
385 mejor = Some(pos);
386 }
387 if pos >= largo || actual.is_empty() { break; }
388 let c = s[pos];
389 let mut siguiente: Vec<usize> = Vec::new();
390 let mut visto2 = vec![false; self.prog.len()];
391 for &pc in &actual {
392 let avanza = match &self.prog[pc] {
393 Inst::Char(x) => *x == c,
394 Inst::Any => true,
395 Inst::Clase { partes, negada } => {
396 let dentro = partes.iter().any(|p| match p {
397 Parte::Uno(u) => *u == c,
398 Parte::Rango(a, b) => *a <= c && c <= *b,
399 Parte::Nombrada(n) => n.casa(c),
400 });
401 dentro != *negada
402 }
403 _ => false,
404 };
405 if avanza { self.agregar(&mut siguiente, &mut visto2, pc + 1, pos + 1, largo); }
406 }
407 actual = siguiente;
408 pos += 1;
409 }
410 mejor
411 }
412
413 /// Primera coincidencia a partir de `desde`: la más a la izquierda y, entre ésas, la más larga.
414 /// Devuelve `(inicio, fin)` en índices de CARÁCTER, con `fin` exclusivo.
415 pub fn buscar(&self, s: &[char], desde: usize) -> Option<(usize, usize)> {
416 for i in desde..=s.len() {
417 if let Some(fin) = self.casa_en(s, i) { return Some((i, fin)); }
418 }
419 None
420 }
421
422 /// ¿Casa en algún sitio? Es lo que piden `~`, los patrones de regla y `split`.
423 pub fn casa(&self, s: &str) -> bool {
424 let v: Vec<char> = s.chars().collect();
425 self.buscar(&v, 0).is_some()
426 }
427}