RE#: Resolviendo el Problema Cuadrático de 'Todas las Coincidencias' en Motores de Expresiones Regulares

El problema fundamental que aborda este trabajo es la ineficiencia inherente (O(n²)) en la operación de 'encontrar todas las coincidencias' en la mayoría de los motores de expresiones regulares, incluso aquellos optimizados para tiempo lineal en una sola coincidencia. Esta limitación ha persistido desde los años 70, a menudo ignorada por la academia que se enfoca en la semántica de 'match/no-match', y por la industria que asume que la iteración sobre coincidencias es trivialmente lineal. La relevancia actual radica en la creciente necesidad de procesar grandes volúmenes de datos (logs, texto, tráfico de red) donde una complejidad cuadrática puede transformar una operación de segundos en horas, afectando directamente la latencia y el throughput de sistemas distribuidos a gran escala. La solución propuesta, RE#, busca cerrar esta brecha entre la teoría y la práctica, ofreciendo un rendimiento predecible y lineal para la extracción de datos a escala.

Históricamente, la mayoría de los motores de regex se han dividido en dos categorías: los basados en backtracking (como Perl, PCRE, Python, JavaScript), que ofrecen gran flexibilidad (incluyendo lookarounds y backreferences) pero sufren de complejidad exponencial (ReDoS), y los basados en autómatas finitos (NFA/DFA, como RE2, Go, Rust), que garantizan tiempo lineal para una sola coincidencia. Sin embargo, la iteración para encontrar todas las coincidencias ha sido un punto ciego, donde incluso los motores basados en autómatas recurren a un bucle ingenuo que reinicia la búsqueda en cada posición, llevando a la temida complejidad cuadrática. Este problema es distinto pero complementario a las vulnerabilidades de ReDoS, ya que afecta a motores 'seguros' y se manifiesta como una degradación silenciosa del rendimiento en lugar de un fallo catastrófico.

Arquitectura del Sistema

RE# resuelve el problema de la complejidad cuadrática en la búsqueda de todas las coincidencias mediante un algoritmo de dos pasadas. La primera pasada utiliza un Deterministic Finite Automaton (DFA) inverso para marcar todas las posiciones en el input donde una coincidencia podría comenzar. Esta pasada es lineal y precalcula los posibles puntos de inicio, eliminando la necesidad de reiniciar la búsqueda en cada carácter. La segunda pasada, un DFA directo, se ejecuta desde estas posiciones marcadas para resolver la coincidencia más larga (leftmost-longest, semántica POSIX). Al combinar la información de ambas pasadas, el motor puede determinar los límites exactos de todas las coincidencias sin realizar rescaneos redundantes, logrando así una complejidad O(n) para el conjunto completo de coincidencias.

El 'hardened mode' de RE# aborda patrones patológicos que, incluso con el algoritmo de dos pasadas, podrían causar trabajo cuadrático debido a límites de coincidencia ambiguos. Este modo reemplaza la segunda pasada con un escaneo O(n * S), donde S es el número de estados DFA activos simultáneamente. Esto garantiza una complejidad lineal estricta incluso con entradas adversarias, aunque con un factor constante de ralentización. La implementación de RE# se basa en DFAs derivados (derivative-based DFAs), que se construyen de forma perezosa y son más compactos que los autómatas completos, mejorando el comportamiento de la caché y reduciendo las fallas de predicción de rama. Para optimizaciones de rendimiento en patrones con literales, RE# incorpora aceleración de saltos utilizando intrinsics de CPU (AVX2, NEON) para búsquedas de bytes raros (rare byte search), matching multiposición (teddy multi-position matching) y escaneo de clases de caracteres por rango, lo que permite saltar grandes porciones del input y alcanzar throughputs de decenas de GB/s.

let re = Regex::with_options(
    pattern,
    EngineOptions::default().hardened(true)
)?;

Fundamentos Teóricos

El problema de encontrar todas las coincidencias de patrones en texto tiene raíces profundas en la ciencia de la computación. Para cadenas fijas, el algoritmo Aho-Corasick (Aho y Corasick, 1975) es un clásico que resuelve el problema en tiempo lineal O(n) mediante la construcción de un autómata de trie con 'failure links'. Este algoritmo es eficiente porque la longitud de cada patrón es conocida de antemano, eliminando la ambigüedad sobre dónde termina una coincidencia. RE# extiende esta idea al dominio de las expresiones regulares completas, donde las longitudes de las coincidencias no son fijas, utilizando un enfoque de dos pasadas que emula la eficiencia de Aho-Corasick para patrones complejos.

La distinción entre la semántica 'earliest match' (utilizada por motores como Hyperscan para detección de intrusiones) y 'leftmost-longest' (POSIX, esperada por usuarios de grep y editores) es crucial y ha sido objeto de estudio en la teoría de lenguajes formales. Mientras que 'earliest match' simplifica la implementación de motores de streaming al no requerir lookahead, 'leftmost-longest' introduce la complejidad de determinar el final de la coincidencia más larga, lo que históricamente ha llevado a la complejidad cuadrática. El trabajo de Russ Cox en 2009 sobre la implementación de expresiones regulares y la descripción del problema cuadrático en la iteración de coincidencias, incluso en motores basados en autómatas, subraya la persistencia de este desafío. RE# aborda directamente esta limitación, demostrando que es posible lograr la semántica POSIX con rendimiento lineal.