El interior de un motor de expresiones regulares como biblioteca

 (blog.burntsushi.net)
1 puntos por GN⁺ 2023-07-06 | 1 comentarios | Compartir por WhatsApp
  • El crate regex de Rust, tras años de reescritura, expuso gran parte de sus motores internos como la API de un crate versionado aparte, regex-automata, y la transición se completó en regex 1.9
  • La reescritura partió de la dificultad para combinar estrategias de búsqueda, la complejidad de probar cada motor interno, la demanda de una API multipatrón más granular que RegexSet y la necesidad de compartir DFA completamente compilados
  • regex-automata organiza el procesamiento de expresiones regulares con el flujo Ast → Hir → extracción de literales/Prefilter → Thompson NFA → PikeVM·BoundedBacktracker·DFA one-pass·DFA·DFA lazy → meta engine
  • El rendimiento se obtiene usando primero, siempre que sea posible, la búsqueda de literales y motores de la familia DFA, y complementándolos con PikeVM, bounded backtracker o DFA one-pass cuando hay grupos de captura o casos excepcionales
  • La API pública y las abstracciones reutilizables facilitaron las pruebas y la experimentación, pero aumentaron la cantidad de código, el tamaño del binario y el tiempo de compilación; los DFA completamente compilados quedaron como opt-in y regex-lite se agregó como alternativa ligera

Reescritura de regex y publicación de regex-automata

  • El regex crate de Rust fue reescrito durante varios años para mejorar su composición interna y facilitar la incorporación de optimizaciones, manteniendo la corrección
  • En ese proceso se creó regex-automata, que expone como una API separada una parte considerable de la implementación interna del crate regex
  • regex-automata se presenta como el primer caso en que el interior de una biblioteca de expresiones regulares se publica a este nivel como una biblioteca versionada aparte
  • regex 1.9 se lanzó el 5 de julio de 2023 y completó esta reescritura
  • Está dirigido a programadores de Rust y a personas interesadas en implementar motores de expresiones regulares basados en autómatas finitos, y presupone experiencia con expresiones regulares

Problemas antes de la reescritura

  • El crate regex existente seguía la tradición de RE2 y usaba internamente varias estrategias de búsqueda, pero esas estrategias se fueron agregando de forma orgánica y se volvieron difíciles de combinar
    • PikeVM, al haber sido diseñado como la primera estrategia, carecía del manejo necesario para iniciar e interrumpir búsquedas sobre subslices al combinarlo con un DFA lazy
    • Era difícil inferir qué estrategia se usaba para cada expresión regular
    • Varias expresiones match implementaban repetidamente la misma lógica, lo que facilitaba que quedaran desincronizadas
    • Incluso en expresiones regulares donde bastaba con usar Aho-Corasick, podía crearse innecesariamente un Thompson NFA que no se usaría
  • Probar los motores internos también era complicado
    • La API pública parece un único motor de expresiones regulares, pero por dentro hay varias estrategias que deben comportarse igual ante la misma entrada
    • Antes de regex 1.9, las estrategias internas no formaban parte de la API pública, por lo que era difícil probar cada motor de manera independiente
    • Las pruebas existentes tenían una estructura cercana a un hack: dependían de exponer APIs internas, implementaciones de From no documentadas, macros y targets de prueba específicos por motor
  • Varias solicitudes de APIs de nicho también eran difíciles de encajar en la superficie de la API existente
    • RegexSet solo indica qué patrones hicieron match en algún lugar del haystack, pero no proporciona offsets de matches ni offsets de grupos de captura
    • Se necesitaba una función para ejecutar búsquedas anchored sin insertar ^ en el patrón
    • Se solicitaba una función para pasar directamente un mutable scratch space durante la búsqueda, sin sincronización interna
    • También se pidió ejecutar expresiones regulares sobre haystacks no contiguos, como streams o ropes
  • Publicar los componentes internos como un crate versionado aparte permite experimentar con APIs para expertos con un ciclo de breaking changes más rápido, sin complicar la API general de regex

La frontera de abstracción creada por el DFA completamente compilado

  • La motivación inicial de regex-automata fue crear un DFA completamente compilado y serializado, y luego ofrecer un runtime mínimo que buscara mediante deserialización zero-copy
  • El primer regex-automata se usó para crear los DFA de la implementación de algoritmos Unicode en bstr
  • Al construir el DFA, se necesitaban una estructura de datos NFA y un compilador similares a los del crate regex; a medida que ese código se volvió más complejo, creció la necesidad de compartirlo
  • Al principio se consideró un crate separado como regex-nfa, pero más código, incluido el proceso de determinization, podía compartirse entre regex y regex-automata
  • La frontera de abstracción estaba más cerca de un motor de expresiones regulares que de un “NFA”, y finalmente regex-automata se redefinió como un conjunto de varios motores
  • El plan a largo plazo era poner todos los motores de expresiones regulares en regex-automata y convertir el crate regex en un wrapper delgado encima de él

Revisar la estructura interna con regex-cli

  • regex-cli es un programa mantenido en el repositorio del crate regex y proporciona acceso por línea de comandos a varias APIs de regex-syntax, regex-automata y regex
  • Se puede instalar con el siguiente comando
cargo install regex-cli
  • regex-cli debug puede imprimir AST, HIR, literales, Thompson NFA, DFA one-pass, DFA dense, DFA sparse, entre otros
  • La expresión regular . con Unicode activado crea un Thompson NFA mucho más complejo para manejar UTF-8 scalar values, mientras que (?-u:.), con Unicode desactivado, crea un NFA más simple
  • regex-cli find puede ejecutar búsquedas ad hoc, y con el meta engine también permite búsquedas multipatrón y salida de grupos de captura

Flujo de datos del procesamiento de expresiones regulares

  • La cadena de patrón pasada a Regex::new primero se parsea como Ast
  • Ast se transforma en Hir
    • Hir tiene menos detalles que Ast, y el Unicode case folding y las referencias a Unicode character classes se expanden durante la transformación
  • A partir de Hir se crean dos cosas
    • Secuencias de literales usadas para optimizar la búsqueda
    • Thompson NFA
  • El NFA se convierte en la base para crear varios motores
    • PikeVM: maneja todas las expresiones regulares parseables y reporta offsets de grupos de captura
    • BoundedBacktracker: reporta offsets de grupos de captura mediante bounded backtracking
    • DFA one-pass: reporta rápidamente offsets de grupos de captura en expresiones regulares restringidas
    • DFA dense: es muy rápido, pero solo reporta el inicio y el fin del match completo; su construcción requiere, en el peor caso, tiempo y espacio O(2^m)
    • DFA lazy: crea el DFA a partir del NFA durante la búsqueda; normalmente es tan rápido como un full DFA y evita el costo exponencial de construcción de un full DFA
  • Estos motores y Prefilter se combinan en un único meta regex engine, y el crate regex es un wrapper delgado sobre ese meta engine

Optimización de literales

  • La extracción de literales es una optimización clave dentro de regex
    • Por ejemplo, toda coincidencia de (foo|bar|quux)(\s+\w+) empieza con uno de foo, bar o quux
  • Los literales son importantes porque los algoritmos de búsqueda para una sola cadena o unas pocas cadenas son muy rápidos
    • Con instrucciones vectoriales se pueden procesar varios bytes del haystack a la vez
    • Los algoritmos generales de matching con expresiones regulares son difíciles de acelerar de forma consistente de la misma manera
  • Una búsqueda de substring bien optimizada a menudo era al menos un orden de magnitud más rápida que un motor general de expresiones regulares
  • La extracción de literales es heurística
    • Debe reducir la tasa de falsos positivos de las coincidencias candidatas
    • También debe reducir el impacto del prefilter en la latencia total
    • Ambas condiciones dependen del haystack, pero analizarlo antes de la búsqueda puede empeorar el tiempo total de búsqueda
  • Una secuencia de literales no es un conjunto, sino una secuencia ordenada
    • El crate regex sigue semántica tipo Perl de leftmost-first, por lo que | no es conmutativo
    • De sam|samwise solo puede extraerse sam, pero en samwise|sam se consideran ambos
  • Para la búsqueda de una sola cadena se usa el módulo memmem del crate memchr
    • El algoritmo principal es Two-Way, con tiempo O(n) en el peor caso y espacio constante
    • Para needles y haystacks cortos se usa Rabin-Karp
    • En x86_64 se aprovecha una variante SIMD genérica
  • Para la búsqueda de múltiples cadenas, el algoritmo principal es Teddy, portado desde Hyperscan, y en algunos casos también se usa Aho-Corasick

Thompson NFA y optimización

  • La estructura de datos central dentro del crate regex es un Thompson NFA
  • Thompson’s construction crea un NFA a partir de una representación estructurada de la expresión regular en tiempo O(m), donde m es proporcional al tamaño de la expresión regular después de expandir las repeticiones contadas
  • El NFA puede usarse directamente como motor de expresiones regulares, y también se usa como base para otros motores al convertirlo a otros tipos, como un DFA
  • La optimización principal del nuevo compilador de NFA se concentra en reducir las transiciones epsilon
    • Un Thompson NFA tiene buen tiempo de construcción, pero usa muchas transiciones epsilon
    • El cálculo de epsilon closure puede generar costos repetidos durante la búsqueda o la construcción del DFA
  • La optimización de estado sparse representa varias transiciones de rango en un solo estado y reduce múltiples instrucciones Split existentes
    • Elimina transiciones epsilon innecesarias en expresiones regulares como [A-Za-z0-9]
    • En la representación actual, por la indirección, puede afectar el caché y aumentar el uso de memoria heap
  • La optimización de autómatas UTF-8 mínimos reduce mucho el tamaño del NFA en clases Unicode grandes
    • En el antiguo NFA orientado a bytes, \w podía generar 3,564 estados
    • El nuevo compilador usa Daciuk’s algorithm para crear una estructura con muchos menos estados y cero transiciones epsilon
    • La reducción del NFA inverso está desactivada por defecto por su costo en tiempo de compilación
  • La optimización de trie de literales compila alternaciones de literales como zap|z|zapper y abc|xyz en un trie con estructura compartida para reducir transiciones epsilon
    • Para preservar la semántica leftmost-first, divide los chunks de transición en cada punto donde aparece una coincidencia
  • Como trabajo futuro para NFA se están evaluando Glushkov NFA y el almacenamiento en una sola asignación contigua
    • Glushkov NFA no tiene transiciones epsilon, pero su complejidad de tiempo de compilación es peor
    • La asignación contigua podría aportar cache friendliness y serialización/deserialización zero-copy, pero puede aumentar la complejidad del código y el uso de unsafe

Motores individuales de expresiones regulares

  • Los motores de regex-automata comparten APIs similares
    • Input: configura el haystack, el rango de búsqueda, si es anchored y si hay early stop
    • Match: contiene el byte span coincidente y el PatternID
    • MatchError: representa un error en el que no se puede determinar el resultado de la búsqueda

  • PikeVM

    • Soporta todas las funciones que regex-syntax puede parsear y funciona con haystacks de cualquier longitud
    • Rastrea las posiciones de los grupos de captura y calcula los estados activos en lock-step, lo que garantiza tiempo O(m * n) en el peor caso
    • Su principal debilidad es el rendimiento, porque debe rastrear muchos estados y posiciones de grupos de captura
    • Tiene la característica única entre los motores de regex-automata de no devolver errores durante la búsqueda

  • BoundedBacktracker

    • Usa backtracking sobre un Thompson NFA, pero emplea estado adicional para no volver a rastrear trabajo ya realizado
    • Garantiza tiempo O(m * n) en el peor caso, pero usa espacio O(m * n)
    • En experimentos aproximados, suele ser alrededor de 2 veces más rápido que PikeVM
    • Puede fallar si la longitud del haystack y el tamaño de la expresión regular superan la visited capacity configurada

  • one-pass DFA

    • Reporta offsets de grupos de captura muy rápido en NFA one-pass limitados
    • Se considera la forma más rápida de reportar grupos de captura
    • Solo soporta búsqueda anchored, y muchas expresiones regulares no son one-pass
    • En modo Unicode, una expresión regular que no era one-pass por solapamiento de transiciones a nivel de byte puede volverse one-pass al desactivar Unicode

  • fully compiled DFA

    • Consta de dos DFA, uno forward y uno reverse, para encontrar el final y el inicio de la coincidencia completa
    • Su construcción toma tiempo y espacio O(2^m) en el peor caso, y un dense DFA usa mucha memoria
    • El motor full DFA está desactivado por defecto en el crate regex y debe habilitarse explícitamente con la feature perf-dfa-full
    • Funciona sin Cache mutable y puede serializarse como bytes raw para usar el runtime de búsqueda incluso en entornos que solo tienen core

  • hybrid NFA/DFA, lazy DFA

    • Es similar a un full DFA, pero construye la tabla de transiciones durante la búsqueda
    • Si una transición ya calculada está en el caché, la reutiliza; si no, calcula solo esa transición con la powerset construction del NFA
    • El tiempo de búsqueda en el peor caso es O(m * n), y el espacio está limitado por la cache capacity definida al construirlo
    • En los casos comunes, la mayoría de estados y transiciones se cachean y se comporta como O(n) en promedio; en la práctica, para muchas expresiones regulares muestra un rendimiento de búsqueda similar al full DFA
    • Si el caché se llena repetidamente y se vuelve ineficiente, devuelve un error, y en el meta engine normalmente se reintenta con otro motor

El rol del meta regex engine

  • El meta regex engine busca agrupar varios motores en uno y ofrecer al llamador una API infallible
  • El llamador no tiene que crear y pasar manualmente un Cache en cada búsqueda
    • El meta engine administra internamente un pool de caché thread-safe
    • Si se quiere evitar el costo de sincronización, también ofrece una API de menor nivel que permite pasar explícitamente un Cache
  • regex::Regex, regex::RegexSet, regex::bytes::Regex y regex::bytes::RegexSet son todos wrappers delgados del meta engine
  • La estrategia interna del meta engine es, a grandes rasgos, la siguiente
    • Si se puede resolver solo con búsqueda de substrings únicos o múltiples, sin motor de expresiones regulares, también evita construir el NFA
    • Cuando es posible, extrae una secuencia de literales de prefijo y la usa como Prefilter
    • Si el prefijo no es adecuado, intenta optimizaciones de reverse anchored, reverse suffix y reverse inner
    • En los demás casos, hace fallback a una core strategy que incluye PikeVM, bounded backtracker, one-pass DFA, lazy DFA y full DFA
  • La estrategia completa se puede resumir en dos frases
    • Buscar literales tanto como sea posible
    • Evitar usar PikeVM tanto como sea posible
  • Las optimizaciones reverse suffix y reverse inner, si se aplican mal, pueden caer en el peor caso O(m * n^2) respecto del tamaño del haystack
    • El meta engine detecta cuando un reverse scan intenta avanzar más allá del final del match de sufijo anterior y hace fallback a la core strategy para mantener la garantía de complejidad temporal

Diferencias con RE2

  • El crate regex y RE2 tienen muchas similitudes
    • RE2 también tiene un NFA equivalente a PikeVM, bitstate backtracker, one-pass NFA, lazy DFA y una estructura que combina varios motores
    • De los motores anteriores, el que RE2 no tiene es el fully compiled DFA
  • Las principales diferencias son las siguientes
    • Además de leftmost-first, RE2 admite como opción semántica POSIX de leftmost-longest
    • RE2 tiene soporte Unicode más limitado y no tiene una opción para usar \w, \s, \d y \b con definiciones Unicode
    • RE2 tiene soporte limitado para operaciones de conjuntos en character classes, aparte de union
    • Es posible que el PikeVM de RE2 sea más eficiente en memoria
    • Las optimizaciones de literales de RE2 son limitadas, mientras que el crate regex realiza más optimizaciones de literales
    • El lazy DFA de RE2 comparte la misma transition cache entre varios threads y requiere sincronización, mientras que el crate regex exige una caché separada por thread y usa más memoria
    • El crate regex publica regex-syntax y regex-automata como bibliotecas versionadas por separado, pero RE2 no ofrece esto
    • regex-automata admite regex multi-pattern de primera clase en todos los motores y también puede reportar el match y los offsets de capture groups de cada patrón coincidente

Estrategia de pruebas y benchmarks

  • La nueva estrategia de pruebas consiste en convertir los motores internos en APIs independientes de primera clase y probar cada motor directamente
  • Todas las pruebas de expresiones regulares se especifican en archivos TOML
  • El crate regex-test lee las pruebas TOML y las convierte en una representación estructurada
  • Para cada configuración de motor hay un Rust unit test, que ejecuta todas las pruebas TOML aplicables a ese motor
  • Como el Rust unit test framework no es extensible, se agregó una infraestructura propia basada en environment variables para filtrar pruebas específicas
  • Solo regex-automata tiene más de 450 documentation tests
  • Durante la preparación de regex 1.9 también se agregaron muchos targets de fuzz testing y, con ayuda de Addison Crump, se encontraron algunos bugs
  • Los benchmarks se publican con un regex barometer llamado rebar
    • rebar benchmarkea no solo el crate regex, sino también varios motores de expresiones regulares
    • En 242 benchmarks, regex 1.9 es en promedio 1.5 veces más rápido que regex 1.7.3 en tiempo de búsqueda
    • El tiempo para compilar expresiones regulares tuvo cierta regresión
    • Como 1.8 fue una transition release que incluyó parte del trabajo de transición, se usó 1.7 como base de comparación

Costos y alternativa ligera

  • La reescritura consumió la mayor parte del tiempo libre del autor durante los últimos años, y proyectos como ripgrep no pudieron tener releases durante un tiempo
  • Las abstracciones públicas reutilizables tienden a requerir más código que las abstracciones solo internas
    • Como consecuencia, aumentan el tamaño del binario y el tiempo de compilación
  • Al publicarse la API interna de motores con versionado separado, romper la API requiere un breaking change release adecuado de regex-automata
  • Para mitigar los costos, se aplicaron dos medidas
    • El motor fully compiled DFA queda desactivado por defecto y se deja como feature opt-in
    • Se publicó regex-lite como un crate nuevo
  • regex-lite apunta a ser un reemplazo casi drop-in del crate regex, pero se enfoca en optimizar el tamaño del binario y el tiempo de compilación
    • Renuncia a funcionalidades relacionadas con Unicode y rendimiento
    • Mantiene la garantía de complejidad temporal O(m * n)
    • No tiene dependencias e incluye su propio parser de expresiones regulares, sin compartir código con el crate regex
  • regex-lite todavía es una mitigación experimental, pero muestra que, incluso desactivando optimizaciones y funciones Unicode mediante features del crate regex, es difícil acercarse al tamaño de binario y al tiempo de compilación de regex-lite

Lecturas relacionadas

1 comentarios

 
GN⁺ 2023-07-06
Opiniones de Hacker News

  • Solo le di una mirada rápida, pero el crate regex de Rust es realmente impresionante
    BurntSushi ha hecho muchas cosas excelentes, pero el crate regex de Rust es legendario, y que el ecosistema de Rust haya tenido desde hace mucho una biblioteca de expresiones regulares rápida y fácil de usar ha sido una gran bendición para la comunidad
    La serie de artículos de Russ Cox sobre expresiones regulares también es excelente, y la usé como referencia durante un verano en el que construí un motor de expresiones regulares, justo cuando empecé a sentir que las expresiones regulares eran la intersección perfecta entre teoría y práctica
    Los cambios más profundos de pruebas en este artículo también son interesantes, y siendo un crate clave del ecosistema, se agradece una explicación sobre un tema tan profundo
    Las expresiones regulares a veces son difíciles de leer y se abusa de ellas para cosas como validar correos electrónicos, pero siguen siendo una de las herramientas más densas en casi cualquier lenguaje
    Como libro práctico, solo conozco bien Mastering Regular Expressions de Jeffrey Friedl, y del lado teórico lo cubren los libros de compiladores; el Dragon Book también estaba bien desde la perspectiva de implementación. Me da curiosidad si alguien recomienda otros libros sobre expresiones regulares

    • https://www.cs.princeton.edu/courses/archive/fall19/cos226/l... y https://kean.blog/post/lets-build-regex son excelentes como introducción a una implementación simplificada de un motor de expresiones regulares
      La idea es construir un autómata finito no determinista para la expresión regular y luego recorrer el grafo dirigido resultante; si es posible llegar a un vértice que corresponda a un estado de aceptación, entonces hay coincidencia
      Si usas expresiones regulares, este ejercicio ayuda a entender que hay menos magia de la que parece, y si imaginas pelotitas rebotando sobre el NFA, incluso los bugs de backtracking catastrófico con los que terminas topándote en producción adquieren un sentido físico
      En relación con el artículo original, el último comentario de BurntSushi en https://github.com/rust-lang/regex/issues/822 agrega contexto útil a la sección sobre APIs de nicho https://blog.burntsushi.net/regex-internals/#problem-request.... Buscar varias expresiones regulares a la vez en un texto es muy complejo, pero muy útil, así que tengo curiosidad por ver qué construye la comunidad con este patrón
    • Un caso representativo en el que las expresiones regulares brillan para tareas parecidas al parsing es cuando manejas formatos con delimitadores variados
      Por ejemplo, en formatos con un número fijo de campos como header:field1,field2,field3\"data\"hash, o en formatos donde la mayoría de los elementos son opcionales, como suite~split/test1,test2@opt1:opt2^hw1^hw2#flags1#flags2, herramientas básicas como split no alcanzan y una expresión regular encaja muy bien
      También por eso las expresiones regulares se vuelven difíciles de leer tan rápido. En una sola expresión se mezclan el delimitador entre campos, la validez de cada campo y cuáles campos son opcionales
      En realidad son tres preocupaciones separadas, pero la mayoría de las APIs de expresiones regulares no permiten separarlas por etapas y solo aceptan una única cadena combinada
    • Me pregunto si esta biblioteca RegEx usa JIT, como la mayoría de las implementaciones de JavaScript. Si no, podría ser un caso en el que JavaScript le gane a Rust
    • Revisé este artículo por encima mientras hacía un poco de trabajo reciente con RegEx, y por el hecho de que el lenguaje usado no devuelve errores, parece que usa PikeVM, a diferencia de otros motores
      Por las restricciones del lenguaje y el estado de protección por copyright, tuve que implementar por mi cuenta la funcionalidad de RegEx, y a veces las expresiones regulares realmente se sienten como vudú
      No sé con qué frecuencia se usan otros motores, pero si muchos lenguajes de programación usan PikeVM, entiendo por qué Google hizo su propio SO para servidores y recurrió a motores más rápidos en ciertos casos para ahorrarse aunque fuera unos cuantos ciclos de reloj
      Sé bien que agregar apenas unos caracteres más a la cadena de búsqueda puede volver mucho más lento el pattern matching. El dicho de “cuida los centavos y los pesos se cuidan solos” aplica muy bien a RegEx y a los ciclos de reloj, y viendo las conversaciones de los 90 sobre procesar millones de registros por segundo, esto probablemente hizo muy ricos a algunos programadores
    • Mi mayor queja son las pequeñas diferencias entre dialectos de expresiones regulares
      Sobre todo porque, entre dialectos y contextos, la forma de manejar comillas o terminar la expresión cambia demasiado; ya renuncié a memorizarlo y termino buscando ejemplos cada vez que lo necesito

  • En ActiveState me encargaron, junto con un colega recién graduado, crear un depurador de expresiones regulares para el editor Komodo
    Contratamos al legendario experto en Perl Mark Jason Dominus para que metiera hooks en el motor de expresiones regulares de Perl, y expusimos esos hooks en la UI para que los usuarios pudieran ver la ejecución paso a paso
    Hoy en día las herramientas web son mejores, pero en 2001 el Rx Debugger de Komodo era de vanguardia y además fue muy divertido trabajar en eso

    • En el pasado necesité un depurador de expresiones regulares offline
      Estaba trabajando con una red aislada, así que la gente que necesitaba usar la herramienta no podía acceder a sitios en línea, y bajo ningún diseño se permitía siquiera pensar en poner datos de trabajo en una herramienta online
      Pero la mayoría del esfuerzo se concentra en herramientas en línea, y las offline son raras e insuficientes comparadas con algo como https://regex101.com/
    • Me gustaría saber si alguien puede recomendar herramientas web concretas que sirvan para este propósito

  • Me pregunto si esto se puede usar también con listas y no solo con cadenas
    Siempre me frustró que existan herramientas potentes para buscar y modificar listas de caracteres, pero en cuanto pasan a ser listas de números o fechas, todo eso desaparece
    Por ejemplo, si quisiera encontrar todas las secuencias en una lista de fechas de intentos de inicio de sesión donde, después de 5 o más fallos, viene un éxito, con una regex sería sencillo, pero en la práctica hay que armar manualmente bucles, flags y listas temporales
    Se podría convertir la lista a cadena, procesarla y luego revertirla, pero las desventajas son obvias. Aunque no fuera tan rápido como una regex basada en cadenas, no entiendo por qué no debería existir una regex para tipos de lista arbitrarios
    También encontré un prototipo en Python que hice hace tiempo: https://github.com/boppreh/listregex
    Es muy lento, pero como experimento de API quedó satisfactorio, y además ofrece herramientas que las regex no tienen, como inversión de patrones, intersección y emparejamiento

    • No. Esta librería de regex está fuertemente acoplada a la búsqueda en cadenas, y esa es una decisión de diseño intencional
      Hacer que un motor de regex así tenga un alfabeto genérico es forzar demasiado las cosas desde el principio. Sobre todo, es demasiado difícil hacerlo de una forma que no perjudique el diseño de la API ni el rendimiento en sus casos de uso principales
      No es difícil hacer un motor de regex de ese tipo si no te importa el rendimiento. Por ejemplo, puedes tomar el crate regex-lite que publiqué y volverlo tan genérico como quieras, y en el proceso te encontrarás con obstáculos interesantes
      Tampoco es que esto no exista en absoluto. La gente ha intentado hacerlo[1]. Pero parece que suelen exagerar un poco su utilidad general y por eso normalmente no logran mucha tracción :-)
      [1]: https://docs.rs/automata/latest/automata/trait.Alphabet.html
    • std::basic_regex de la biblioteca estándar de C++ intenta algo así al exponer una clase plantilla para tipos de carácter definidos por el usuario: https://en.cppreference.com/w/cpp/regex/basic_regex
      Se puede proporcionar una clase trait que defina el comportamiento necesario para un “carácter” definido por el usuario
      Pero el rendimiento cae muchísimo, y probablemente funcione tan bien como meter objetos arbitrarios no textuales en un std::basic_string definido por el usuario
    • De algún modo habría que definir una API que haga matching sobre una ventana deslizante de valores
      No es imposible, pero la mayoría de los lenguajes no tienen una buena interfaz para eso

  • Uso Ripgrep todos los días para buscar cosas en código o archivos de texto, y cada vez que lo uso en Windows, Linux, Mac, VSCode o Vim, me siento agradecido
    Es uno de esos programas que cambiaron mi vida y mi forma de trabajar
    Cuando me veo obligado a usar grep, siento que volví a una época en la que todo corría en una CPU de un solo núcleo y los datos estaban en discos duros mecánicos lentísimos PATA/IDE
    BurntSushi merece de sobra el respeto que se les da a los grandes programadores

    • ripgrep tiene un linaje. Antes estuvo ag, y antes de eso ack, y todos intentaron ofrecer una interfaz mucho mejor que la simple de grep

  • Por un problema de trabajo tuve que crear un RegexSet con más de 10 millones de regex muy largas
    Ningún motor podía manejarlo con la configuración predeterminada, y el RegexSet de Rust tampoco alcanzaba con los valores por defecto
    Aun así, usar regex-automata y regex-syntax, y leer el código, fue un material de aprendizaje muy valioso incluso en 2018
    Al final, el proyecto laboral tomó como modelo la API de Lucene, pero solo fue posible después de aprender los fundamentos con los crates de regex

    • 10 millones de regex es una escala enorme. Incluso Aho-Corasick apenas puede lidiar con 10 millones de literales
      El trabajo a futuro es hacer que los motores de regex escalen mejor con una mayor cantidad de patrones. Ahora mismo colapsarían mucho antes de llegar a 10 millones de regex, y ni siquiera es fácil estar seguro de que ese objetivo sea realmente posible
      Aun así, claramente se puede mejorar respecto al estado actual
      Claro, en búsqueda multipatrón, Hyperscan es prácticamente el patrón oro. Aunque no sé qué tan bien manejaría 10 millones de patrones
    • Como no lo describiste en detalle desde el principio, supongo que la respuesta será “no”, pero si se puede, me da curiosidad si podrías compartir más sobre ese problema o proyecto

  • Hace tiempo probé el crate regex-automata, y fue la única librería que pude usar en un editor de texto porque permitía acceso directo al DFA interno
    Las APIs de bibliotecas de regex normales esperan que la entrada sea una sola cadena continua, pero este enfoque es compatible con cualquier estructura de datos de texto

  • Me apareció este artículo mientras estaba escribiendo código con regex-automata, y encima usando el release inicial 0.2.0
    Parece que ya toca revisar otra vez las nuevas estructuras internas
    Todavía no pude leer el artículo, pero se ve muy interesante y con un timing perfecto
    Unos minutos después vi que la respuesta era más bien “puede ser”, pero al ser un release formal tal vez incluso me permita simplificar bastante el código
    Otros 10 minutos después, fue bastante painless, y el nuevo método Builder::patch fue una mejora total
    Posdata: todavía me tienes bloqueado en todos tus repositorios de GitHub, y considerando que muchos crates se usan ampliamente, me parece un poco injusto. No recuerdo el incidente original. Parece que el crate regex en sí ahora está bajo la organización rust-lang, pero todavía hay cosas con las que no puedo interactuar

    • La documentación de regex-automata 0.2.0 tenía una gran advertencia sobre eso, y recomendaba enfáticamente usar 0.1: https://docs.rs/regex-automata/0.2.0/regex_automata/
      Yo tampoco recuerdo el incidente original. Bloqueo a mucha gente por varias razones, pero ya te desbloqueé

  • BioJulia publicó Automa.jl, un motor de expresiones regulares escrito completamente en Julia que puede insertar código arbitrario de Julia en tiempo de compilación
    No es por restarle mérito a que regex de Rust está mucho más avanzado que Automa, pero me cuesta estar de acuerdo con la afirmación de que es el primer caso de exponer el interior de una expresión regular como biblioteca

    • Esto suena a dos cosas distintas
      Por ejemplo, PCRE2 tiene soporte de “callout” que suena parecido a lo que se menciona: https://www.pcre.org/current/doc/html/pcre2callout.html
      Cosas como ragel o re2c también han venido haciendo algo similar
      Lo que dice este blog es tomar el interior de la propia biblioteca de expresiones regulares, convertirlo en una biblioteca aparte con versionado independiente y hacer posible que otros la combinen
      En los backtrackers esto suele ser menos natural porque el motor normalmente solo tiene un backtracker, pero las bibliotecas basadas en autómatas a menudo combinan varios motores de distintas maneras
      Aun así, incluso los backtrackers podrían exponer cosas que en la práctica no suelen exponer, como el parser de expresiones regulares o el AST