sergio/takana

1//! Coincidencia de patrones POSIX (§2.13) y expansión de rutas. Propio, sin `regex` ni `glob`:
2//! son ~150 líneas y evitan dos deps en la raíz de confianza del arranque.
3//!
4//! Sirve para dos cosas distintas con las mismas reglas: expandir `*.txt` a ficheros, y decidir
5//! si `abc` encaja en el patrón de una rama de `case`.
6
7/// ¿`texto` encaja en `patron`? `*`, `?`, `[abc]`, `[!abc]`, `[a-z]`, y `\` escapa.
8pub fn encaja(patron: &str, texto: &str) -> bool {
9    coincide(&patron.chars().collect::<Vec<_>>(), &texto.chars().collect::<Vec<_>>())
10}
11
12fn coincide(p: &[char], t: &[char]) -> bool {
13    if p.is_empty() {
14        return t.is_empty();
15    }
16    match p[0] {
17        '*' => {
18            // voraz con retroceso: `*` puede comerse de 0 a todo
19            for corte in 0..=t.len() {
20                if coincide(&p[1..], &t[corte..]) {
21                    return true;
22                }
23            }
24            false
25        }
26        '?' => !t.is_empty() && coincide(&p[1..], &t[1..]),
27        '[' => {
28            if t.is_empty() {
29                return false;
30            }
31            match clase(p) {
32                Some((acepta, largo)) => acepta(t[0]) && coincide(&p[largo..], &t[1..]),
33                // `[` sin cerrar es un literal
34                None => t[0] == '[' && coincide(&p[1..], &t[1..]),
35            }
36        }
37        '\\' if p.len() > 1 => !t.is_empty() && t[0] == p[1] && coincide(&p[2..], &t[1..]),
38        c => !t.is_empty() && t[0] == c && coincide(&p[1..], &t[1..]),
39    }
40}
41
42/// Analiza `[…]` desde `p[0] == '['`. Devuelve `(predicado, cuántos chars ocupa)`.
43#[allow(clippy::type_complexity)]
44fn clase(p: &[char]) -> Option<(Box<dyn Fn(char) -> bool>, usize)> {
45    let mut i = 1;
46    let negada = matches!(p.get(i), Some('!') | Some('^'));
47    if negada {
48        i += 1;
49    }
50    let mut sueltos: Vec<char> = Vec::new();
51    let mut rangos: Vec<(char, char)> = Vec::new();
52    let mut primero = true;
53    loop {
54        let mut c = *p.get(i)?;
55        if c == ']' && !primero {
56            i += 1;
57            break;
58        }
59        primero = false;
60        // `\` dentro de la clase escapa: `[\\\`\"\$]` es el conjunto de los cuatro caracteres,
61        // y es literalmente el que usa el `config.status` que genera cualquier `configure`.
62        if c == '\\' {
63            if let Some(d) = p.get(i + 1) {
64                c = *d;
65                sueltos.push(c);
66                i += 2;
67                continue;
68            }
69        }
70        if p.get(i + 1) == Some(&'-') && p.get(i + 2).is_some_and(|d| *d != ']') {
71            rangos.push((c, p[i + 2]));
72            i += 3;
73        } else {
74            sueltos.push(c);
75            i += 1;
76        }
77    }
78    let pred = move |c: char| {
79        let dentro = sueltos.contains(&c) || rangos.iter().any(|(a, b)| c >= *a && c <= *b);
80        dentro != negada
81    };
82    Some((Box::new(pred), i))
83}
84
85/// ¿La palabra tiene algún metacarácter de ruta sin escapar? Si no, no hay nada que expandir.
86pub fn tiene_meta(s: &str) -> bool {
87    let cs: Vec<char> = s.chars().collect();
88    let mut i = 0;
89    while i < cs.len() {
90        match cs[i] {
91            '\\' => i += 2,
92            '*' | '?' | '[' => return true,
93            _ => i += 1,
94        }
95    }
96    false
97}
98
99/// Expande un patrón de ruta. Devuelve las coincidencias ORDENADAS, o vacío si no hay ninguna
100/// (quien llama deja entonces la palabra tal cual, que es lo que manda POSIX).
101pub fn expandir(patron: &str) -> Vec<String> {
102    let absoluto = patron.starts_with('/');
103    let partes: Vec<&str> = patron.split('/').filter(|p| !p.is_empty()).collect();
104    let mut actuales: Vec<String> = vec![if absoluto { "/".into() } else { String::new() }];
105    for (n, parte) in partes.iter().enumerate() {
106        let ultima = n + 1 == partes.len();
107        let mut siguientes = Vec::new();
108        for base in &actuales {
109            if !tiene_meta(parte) {
110                let cand = unir(base, parte);
111                let existe = std::path::Path::new(&cand).symlink_metadata().is_ok();
112                if existe || !ultima {
113                    // sin meta, no hace falta listar el directorio
114                    if existe {
115                        siguientes.push(cand);
116                    }
117                }
118                continue;
119            }
120            let dir = if base.is_empty() { ".".to_string() } else { base.clone() };
121            let Ok(entradas) = std::fs::read_dir(&dir) else { continue };
122            let mut nombres: Vec<String> = entradas
123                .filter_map(|e| e.ok())
124                .map(|e| e.file_name().to_string_lossy().into_owned())
125                .filter(|n| {
126                    // un patrón no matchea los que empiezan con punto salvo que el patrón lo diga
127                    !(n.starts_with('.') && !parte.starts_with('.'))
128                })
129                .filter(|n| encaja(parte, n))
130                .collect();
131            nombres.sort();
132            for n in nombres {
133                let cand = unir(base, &n);
134                if ultima || std::path::Path::new(&cand).is_dir() {
135                    siguientes.push(cand);
136                }
137            }
138        }
139        actuales = siguientes;
140        if actuales.is_empty() {
141            return Vec::new();
142        }
143    }
144    actuales
145}
146
147fn unir(base: &str, hoja: &str) -> String {
148    if base.is_empty() {
149        hoja.to_string()
150    } else if base == "/" {
151        format!("/{hoja}")
152    } else {
153        format!("{base}/{hoja}")
154    }
155}
156
157#[cfg(test)]
158mod pruebas {
159    use super::*;
160
161    #[test]
162    fn asterisco_y_signo() {
163        assert!(encaja("*.txt", "a.txt"));
164        assert!(encaja("*", ""));
165        assert!(!encaja("*.txt", "a.txtx"));
166        assert!(encaja("a?c", "abc"));
167        assert!(!encaja("a?c", "ac"));
168        assert!(encaja("loop*", "loop0"));
169    }
170
171    #[test]
172    fn clases() {
173        assert!(encaja("[abc]x", "bx"));
174        assert!(!encaja("[abc]x", "dx"));
175        assert!(encaja("[!abc]x", "dx"));
176        assert!(encaja("[a-f]1", "c1"));
177        assert!(!encaja("[a-f]1", "g1"));
178        // `]` como primer carácter es literal
179        assert!(encaja("[]a]", "]"));
180    }
181
182    #[test]
183    fn el_patron_de_case_del_init() {
184        // `case $n in proc|sys|dev|run|tmp|store|init) continue ;;` — patrones sin meta
185        for n in ["proc", "sys", "dev"] {
186            assert!(encaja(n, n));
187        }
188        assert!(!encaja("proc", "procfs"));
189    }
190
191    #[test]
192    fn barra_escapa() {
193        assert!(encaja(r"a\*b", "a*b"));
194        assert!(!encaja(r"a\*b", "axb"));
195    }
196
197    #[test]
198    fn sin_coincidencia_devuelve_vacio() {
199        assert!(expandir("/no-existe-jamas-*/x").is_empty());
200    }
201
202    #[test]
203    fn expande_en_el_arbol_real() {
204        let hits = expandir("/dev/nul*");
205        assert_eq!(hits, vec!["/dev/null".to_string()]);
206    }
207}