//! Motor de expresiones regulares ERE (POSIX.1-2024 §9.4), propio.
//!
//! # Por qué propio y no un crate
//!
//! La semántica de POSIX es **leftmost-longest**: entre todas las coincidencias que empiezan en la
//! posición más a la izquierda, gana la MÁS LARGA. La familia Perl —y con ella el crate `regex` en
//! su modo por defecto— usa leftmost-first: para `a|ab` sobre `"ab"`, POSIX devuelve `ab` y Perl
//! devuelve `a`. En un awk eso no es un detalle académico: decide qué borra un `sub()`, dónde parte
//! un `split()` y qué valen `RSTART`/`RLENGTH`. Adoptar un motor ajeno sería adoptar su semántica.
//!
//! # Cómo funciona
//!
//! Construcción de Thompson: el patrón se compila a un programa de instrucciones y se simula con un
//! CONJUNTO de hilos que avanzan a la vez, un carácter por paso. No hay retroceso, así que no hay
//! explosión exponencial —`(a*)*b` contra sesenta `a` termina igual de rápido que cualquier otra
//! cosa— y quedarse con el final más lejano alcanzado da el «más largo» de POSIX sin esfuerzo extra.
//!
//! Trabaja sobre `char`, no sobre bytes: en awk los índices de `substr`, `index`, `match` y
//! `RSTART` se cuentan en caracteres, y con UTF-8 en el fichero de entrada contar bytes daría
//! posiciones que no se pueden usar para cortar.

/// Una instrucción del programa compilado.
#[derive(Debug, Clone)]
enum Inst {
    /// Consume exactamente este carácter.
    Char(char),
    /// Consume cualquier carácter (`.`). En awk `.` SÍ casa con `\n` (no hay modo multilínea).
    Any,
    /// Consume un carácter si pertenece (o no, si `negada`) al conjunto.
    Clase { partes: Vec<Parte>, negada: bool },
    /// Bifurca: sigue por las dos ramas. El orden no importa porque no hay preferencia (longest).
    Split(usize, usize),
    /// Salta.
    Jmp(usize),
    /// Ancla de principio de cadena (`^`).
    Bol,
    /// Ancla de final de cadena (`$`).
    Eol,
    /// Aceptación.
    Match,
}

/// Un trozo de una clase `[...]`.
#[derive(Debug, Clone)]
enum Parte {
    Uno(char),
    Rango(char, char),
    /// `[:alpha:]` y compañía, resueltas por función para no materializar Unicode entero.
    Nombrada(Nombrada),
}

#[derive(Debug, Clone, Copy, PartialEq)]
enum Nombrada {
    Alpha, Digit, Alnum, Upper, Lower, Space, Blank, Punct, Print, Graph, Cntrl, Xdigit,
}

impl Nombrada {
    fn de(nombre: &str) -> Option<Nombrada> {
        Some(match nombre {
            "alpha" => Nombrada::Alpha, "digit" => Nombrada::Digit, "alnum" => Nombrada::Alnum,
            "upper" => Nombrada::Upper, "lower" => Nombrada::Lower, "space" => Nombrada::Space,
            "blank" => Nombrada::Blank, "punct" => Nombrada::Punct, "print" => Nombrada::Print,
            "graph" => Nombrada::Graph, "cntrl" => Nombrada::Cntrl, "xdigit" => Nombrada::Xdigit,
            _ => return None,
        })
    }
    fn casa(self, c: char) -> bool {
        match self {
            Nombrada::Alpha => c.is_alphabetic(),
            Nombrada::Digit => c.is_ascii_digit(),
            Nombrada::Alnum => c.is_alphanumeric(),
            Nombrada::Upper => c.is_uppercase(),
            Nombrada::Lower => c.is_lowercase(),
            Nombrada::Space => c.is_whitespace(),
            Nombrada::Blank => c == ' ' || c == '\t',
            Nombrada::Punct => c.is_ascii_punctuation(),
            Nombrada::Print => !c.is_control(),
            Nombrada::Graph => !c.is_control() && !c.is_whitespace(),
            Nombrada::Cntrl => c.is_control(),
            Nombrada::Xdigit => c.is_ascii_hexdigit(),
        }
    }
}

/// Árbol del patrón, paso intermedio entre el texto y el programa.
#[derive(Debug, Clone)]
enum Nodo {
    Vacio,
    Char(char),
    Any,
    Clase { partes: Vec<Parte>, negada: bool },
    Bol,
    Eol,
    Cat(Box<Nodo>, Box<Nodo>),
    Alt(Box<Nodo>, Box<Nodo>),
    Estrella(Box<Nodo>),
    Mas(Box<Nodo>),
    Opcional(Box<Nodo>),
    /// `{n,m}`: se expande al compilar. `hasta = None` es `{n,}`.
    Repite(Box<Nodo>, u32, Option<u32>),
}

pub struct Regex {
    prog: Vec<Inst>,
    /// El patrón original, para mensajes de error y para `Regex::fuente`.
    fuente: String,
}

struct Analizador<'a> {
    p: &'a [char],
    i: usize,
}

impl<'a> Analizador<'a> {
    fn fin(&self) -> bool { self.i >= self.p.len() }
    fn ver(&self) -> Option<char> { self.p.get(self.i).copied() }
    fn tomar(&mut self) -> Option<char> { let c = self.ver(); if c.is_some() { self.i += 1; } c }

    /// alternancia := concatenación ('|' concatenación)*
    fn alternancia(&mut self) -> Result<Nodo, String> {
        let mut izq = self.concatenacion()?;
        while self.ver() == Some('|') {
            self.i += 1;
            let der = self.concatenacion()?;
            izq = Nodo::Alt(Box::new(izq), Box::new(der));
        }
        Ok(izq)
    }

    /// concatenación := repetición*
    fn concatenacion(&mut self) -> Result<Nodo, String> {
        let mut acc: Option<Nodo> = None;
        while !self.fin() && self.ver() != Some('|') && self.ver() != Some(')') {
            let n = self.repeticion()?;
            acc = Some(match acc {
                None => n,
                Some(a) => Nodo::Cat(Box::new(a), Box::new(n)),
            });
        }
        Ok(acc.unwrap_or(Nodo::Vacio))
    }

    /// repetición := átomo ('*' | '+' | '?' | '{n,m}')*
    fn repeticion(&mut self) -> Result<Nodo, String> {
        let mut n = self.atomo()?;
        loop {
            match self.ver() {
                Some('*') => { self.i += 1; n = Nodo::Estrella(Box::new(n)); }
                Some('+') => { self.i += 1; n = Nodo::Mas(Box::new(n)); }
                Some('?') => { self.i += 1; n = Nodo::Opcional(Box::new(n)); }
                Some('{') => {
                    // Sólo es intervalo si lo que sigue es un dígito: en ERE un `{` suelto es
                    // literal, y hay guiones que escriben `/x{/` sin escapar.
                    if !matches!(self.p.get(self.i + 1), Some(c) if c.is_ascii_digit()) { break; }
                    let guardado = self.i;
                    self.i += 1;
                    match self.intervalo() {
                        Ok((desde, hasta)) => n = Nodo::Repite(Box::new(n), desde, hasta),
                        Err(_) => { self.i = guardado; break; }
                    }
                }
                _ => break,
            }
        }
        Ok(n)
    }

    fn intervalo(&mut self) -> Result<(u32, Option<u32>), String> {
        let mut desde = String::new();
        while matches!(self.ver(), Some(c) if c.is_ascii_digit()) { desde.push(self.tomar().unwrap()); }
        if desde.is_empty() { return Err("intervalo sin mínimo".into()); }
        let d: u32 = desde.parse().map_err(|_| "intervalo demasiado grande".to_string())?;
        match self.ver() {
            Some('}') => { self.i += 1; Ok((d, Some(d))) }
            Some(',') => {
                self.i += 1;
                let mut hasta = String::new();
                while matches!(self.ver(), Some(c) if c.is_ascii_digit()) { hasta.push(self.tomar().unwrap()); }
                if self.ver() != Some('}') { return Err("intervalo sin cerrar".into()); }
                self.i += 1;
                if hasta.is_empty() { Ok((d, None)) }
                else {
                    let h: u32 = hasta.parse().map_err(|_| "intervalo demasiado grande".to_string())?;
                    if h < d { return Err("intervalo con máximo menor que el mínimo".into()); }
                    Ok((d, Some(h)))
                }
            }
            _ => Err("intervalo mal formado".into()),
        }
    }

    fn atomo(&mut self) -> Result<Nodo, String> {
        match self.tomar() {
            None => Ok(Nodo::Vacio),
            Some('(') => {
                let dentro = self.alternancia()?;
                if self.tomar() != Some(')') { return Err("falta `)`".into()); }
                Ok(dentro)
            }
            Some('[') => self.clase(),
            Some('.') => Ok(Nodo::Any),
            Some('^') => Ok(Nodo::Bol),
            Some('$') => Ok(Nodo::Eol),
            Some('\\') => match self.tomar() {
                None => Err("`\\` al final del patrón".into()),
                // Los escapes de C que awk reconoce dentro de una ERE.
                Some('n') => Ok(Nodo::Char('\n')),
                Some('t') => Ok(Nodo::Char('\t')),
                Some('r') => Ok(Nodo::Char('\r')),
                Some('f') => Ok(Nodo::Char('\x0c')),
                Some('b') => Ok(Nodo::Char('\x08')),
                Some('v') => Ok(Nodo::Char('\x0b')),
                Some('a') => Ok(Nodo::Char('\x07')),
                Some('/') => Ok(Nodo::Char('/')),
                Some(c) => Ok(Nodo::Char(c)),
            },
            Some(c) => Ok(Nodo::Char(c)),
        }
    }

    /// `[abc]`, `[^a-z]`, `[[:digit:]]`. Un `]` justo tras el `[` (o tras `[^`) es LITERAL.
    fn clase(&mut self) -> Result<Nodo, String> {
        let mut negada = false;
        if self.ver() == Some('^') { negada = true; self.i += 1; }
        let mut partes: Vec<Parte> = Vec::new();
        let mut primero = true;
        loop {
            let c = match self.tomar() {
                None => return Err("clase `[` sin cerrar".into()),
                Some(']') if !primero => break,
                Some(c) => c,
            };
            primero = false;
            // `[:alpha:]` dentro de la clase.
            if c == '[' && self.ver() == Some(':') {
                let guardado = self.i;
                self.i += 1;
                let mut nombre = String::new();
                while matches!(self.ver(), Some(c) if c != ':' && c != ']') { nombre.push(self.tomar().unwrap()); }
                if self.ver() == Some(':') && self.p.get(self.i + 1) == Some(&']') {
                    self.i += 2;
                    match Nombrada::de(&nombre) {
                        Some(n) => { partes.push(Parte::Nombrada(n)); continue; }
                        None => return Err(format!("clase de caracteres desconocida: [:{nombre}:]")),
                    }
                }
                self.i = guardado; // no era una clase nombrada: el `[` es literal
            }
            let c = if c == '\\' {
                match self.tomar() {
                    None => return Err("`\\` al final de una clase".into()),
                    Some('n') => '\n', Some('t') => '\t', Some('r') => '\r',
                    Some('f') => '\x0c', Some('b') => '\x08', Some('v') => '\x0b', Some('a') => '\x07',
                    Some(o) => o,
                }
            } else { c };
            // Rango `a-z`, salvo que el `-` sea el último carácter de la clase.
            if self.ver() == Some('-') && self.p.get(self.i + 1).map_or(false, |&d| d != ']') {
                self.i += 1;
                let hasta = match self.tomar() {
                    None => return Err("rango sin final".into()),
                    Some('\\') => self.tomar().ok_or("`\\` al final de un rango")?,
                    Some(d) => d,
                };
                partes.push(Parte::Rango(c, hasta));
            } else {
                partes.push(Parte::Uno(c));
            }
        }
        Ok(Nodo::Clase { partes, negada })
    }
}

/// Emite el programa. Devuelve el índice de la primera instrucción del fragmento.
fn emitir(prog: &mut Vec<Inst>, n: &Nodo) {
    match n {
        Nodo::Vacio => {}
        Nodo::Char(c) => prog.push(Inst::Char(*c)),
        Nodo::Any => prog.push(Inst::Any),
        Nodo::Bol => prog.push(Inst::Bol),
        Nodo::Eol => prog.push(Inst::Eol),
        Nodo::Clase { partes, negada } => prog.push(Inst::Clase { partes: partes.clone(), negada: *negada }),
        Nodo::Cat(a, b) => { emitir(prog, a); emitir(prog, b); }
        Nodo::Alt(a, b) => {
            let split = prog.len();
            prog.push(Inst::Jmp(0)); // reservado, se reescribe como Split
            emitir(prog, a);
            let jmp = prog.len();
            prog.push(Inst::Jmp(0));
            let inicio_b = prog.len();
            emitir(prog, b);
            let fin = prog.len();
            prog[split] = Inst::Split(split + 1, inicio_b);
            prog[jmp] = Inst::Jmp(fin);
        }
        Nodo::Estrella(a) => {
            let split = prog.len();
            prog.push(Inst::Jmp(0));
            emitir(prog, a);
            prog.push(Inst::Jmp(split));
            let fin = prog.len();
            prog[split] = Inst::Split(split + 1, fin);
        }
        Nodo::Mas(a) => {
            let inicio = prog.len();
            emitir(prog, a);
            let split = prog.len();
            prog.push(Inst::Jmp(0));
            let fin = prog.len();
            prog[split] = Inst::Split(inicio, fin);
        }
        Nodo::Opcional(a) => {
            let split = prog.len();
            prog.push(Inst::Jmp(0));
            emitir(prog, a);
            let fin = prog.len();
            prog[split] = Inst::Split(split + 1, fin);
        }
        Nodo::Repite(a, desde, hasta) => {
            // Se expande: `x{2,4}` es `xx(x(x)?)?`. Es lo que hace cualquier motor sin contadores, y
            // el coste es lineal en `hasta`, que en la práctica es un número pequeño.
            for _ in 0..*desde { emitir(prog, a); }
            match hasta {
                None => emitir(prog, &Nodo::Estrella(a.clone())),
                Some(h) => {
                    let opcionales = h.saturating_sub(*desde);
                    let mut splits = Vec::new();
                    for _ in 0..opcionales {
                        let s = prog.len();
                        prog.push(Inst::Jmp(0));
                        splits.push(s);
                        emitir(prog, a);
                    }
                    let fin = prog.len();
                    for s in splits { prog[s] = Inst::Split(s + 1, fin); }
                }
            }
        }
    }
}

impl Regex {
    pub fn nueva(patron: &str) -> Result<Regex, String> {
        let chars: Vec<char> = patron.chars().collect();
        let mut an = Analizador { p: &chars, i: 0 };
        let nodo = an.alternancia()?;
        if !an.fin() {
            return Err(format!("basura al final del patrón: `{}`", chars[an.i..].iter().collect::<String>()));
        }
        let mut prog = Vec::new();
        emitir(&mut prog, &nodo);
        prog.push(Inst::Match);
        Ok(Regex { prog, fuente: patron.to_string() })
    }

    pub fn fuente(&self) -> &str { &self.fuente }

    /// Añade un hilo y todos los alcanzables sin consumir (cierre-epsilon).
    fn agregar(&self, lista: &mut Vec<usize>, visto: &mut [bool], pc: usize, pos: usize, largo: usize) {
        if visto[pc] { return; }
        visto[pc] = true;
        match self.prog[pc] {
            Inst::Jmp(d) => self.agregar(lista, visto, d, pos, largo),
            Inst::Split(a, b) => {
                self.agregar(lista, visto, a, pos, largo);
                self.agregar(lista, visto, b, pos, largo);
            }
            Inst::Bol => { if pos == 0 { self.agregar(lista, visto, pc + 1, pos, largo); } }
            Inst::Eol => { if pos == largo { self.agregar(lista, visto, pc + 1, pos, largo); } }
            _ => lista.push(pc),
        }
    }

    /// El final del match MÁS LARGO que empieza exactamente en `desde`, si lo hay.
    pub fn casa_en(&self, s: &[char], desde: usize) -> Option<usize> {
        let largo = s.len();
        let mut visto = vec![false; self.prog.len()];
        let mut actual: Vec<usize> = Vec::new();
        self.agregar(&mut actual, &mut visto, 0, desde, largo);
        let mut mejor: Option<usize> = None;
        let mut pos = desde;
        loop {
            // ¿Alguno acepta aquí? Nos quedamos con el más lejano: eso es «longest».
            if actual.iter().any(|&pc| matches!(self.prog[pc], Inst::Match)) {
                mejor = Some(pos);
            }
            if pos >= largo || actual.is_empty() { break; }
            let c = s[pos];
            let mut siguiente: Vec<usize> = Vec::new();
            let mut visto2 = vec![false; self.prog.len()];
            for &pc in &actual {
                let avanza = match &self.prog[pc] {
                    Inst::Char(x) => *x == c,
                    Inst::Any => true,
                    Inst::Clase { partes, negada } => {
                        let dentro = partes.iter().any(|p| match p {
                            Parte::Uno(u) => *u == c,
                            Parte::Rango(a, b) => *a <= c && c <= *b,
                            Parte::Nombrada(n) => n.casa(c),
                        });
                        dentro != *negada
                    }
                    _ => false,
                };
                if avanza { self.agregar(&mut siguiente, &mut visto2, pc + 1, pos + 1, largo); }
            }
            actual = siguiente;
            pos += 1;
        }
        mejor
    }

    /// Primera coincidencia a partir de `desde`: la más a la izquierda y, entre ésas, la más larga.
    /// Devuelve `(inicio, fin)` en índices de CARÁCTER, con `fin` exclusivo.
    pub fn buscar(&self, s: &[char], desde: usize) -> Option<(usize, usize)> {
        for i in desde..=s.len() {
            if let Some(fin) = self.casa_en(s, i) { return Some((i, fin)); }
        }
        None
    }

    /// ¿Casa en algún sitio? Es lo que piden `~`, los patrones de regla y `split`.
    pub fn casa(&self, s: &str) -> bool {
        let v: Vec<char> = s.chars().collect();
        self.buscar(&v, 0).is_some()
    }
}