Por qué usar Rust para la tokenización y el análisis sintáctico

 (xnacly.me)
2 puntos por GN⁺ 2024-11-09 | 1 comentarios | Compartir por WhatsApp
  • sqleibniz es una herramienta de análisis estático que busca verificar la sintaxis de SQL en el dialecto de SQLite, la existencia de tablas, columnas y funciones, y condiciones en tiempo de ejecución; para ello, la tokenización y el parsing son pasos clave
  • macro_rules! de Rust ayuda a crear sin repetición las estructuras de nodos del AST, las implementaciones del trait Node y pruebas basadas en tablas al estilo de Go
  • Usar patrones con matches! y match permite trasladar casi directamente al código las ramificaciones gramaticales como los literales numéricos de SQLite, identificadores, símbolos y casos como EXPLAIN QUERY PLAN
  • Los operadores is_some_and, map, map_or de Option y ? hacen más conciso el manejo de la presencia de valores, transformaciones, valores por defecto y propagación de errores en el procesamiento de entrada y flujos de tokens
  • Los iteradores de Rust se aprovechan para quitar _ de literales numéricos, validar caracteres hexadecimales dentro de blobs y calcular posiciones de error, lo que termina haciendo más legible el código de tokenización y parsing

Flujo de análisis de sqleibniz

  • sqleibniz es una herramienta de análisis SQL en desarrollo orientada al dialecto SQLite
  • Sobre una entrada SQL, busca realizar validación sintáctica, verificación de existencia de tablas, columnas y funciones, y validación de condiciones acopladas al runtime integrado de SQLite
  • Los mensajes de error apuntan a ofrecer contexto y explicación, y a permitir ignorar diagnósticos específicos
  • El flujo de análisis comienza con el análisis léxico/tokenización, sigue con el parsing de SQL según la documentación de SQLite y continúa con el análisis de la estructura resultante
  • Después de terminar la parte de análisis estático, también está planeado crear un servidor LSP para SQL

Eliminar repetición en nodos AST con macros

  • Los nodos AST de sqleibniz son estructuras que contienen un Token, y todos los nodos deben implementar el trait Node
  • El trait Node usa std::fmt::Debug como supertrait, así que solo los tipos que satisfacen Debug pueden implementar Node
  • Para no repetir en cada nodo la definición de la estructura y la implementación de fn token(&self) -> &Token, el macro node! genera ambas cosas
    • El nombre del nodo se recibe como metavariable ident
    • La cadena de documentación se recibe como metavariable literal
    • Los campos adicionales se procesan repetidamente con la forma $($field_name:ident:$field_type:ty),*
  • El nodo Literal solo tiene el campo token, mientras que Explain agrega además el campo child: Option<Box<dyn Node>>
  • Los comentarios de documentación se pasan al compilador como argumentos del macro mediante #[doc = $documentation] en vez de ///

Implementar pruebas basadas en tablas al estilo de Go con macros de Rust

  • Se reproduce con macros de Rust el estilo de pruebas basadas en tablas de Go, donde se recorre un arreglo de casos de entrada y cada caso se ejecuta como una prueba independiente
  • Las pruebas del lexer usan los macros test_group_pass_assert! y test_group_fail!
    • Las pruebas exitosas pasan la entrada a Lexer y comparan la lista de tipos de tokens resultante de Lexer.run() con el valor esperado
    • Las pruebas fallidas verifican que el vector de tokens resultante esté vacío y que Lexer.errors contenga uno o más errores
    • Al ejecutar cargo test, cada caso produce feedback ok o fail como si fuera una función de prueba separada
  • Las pruebas del parser siguen la misma estructura, pero después de ejecutar el lexer inicializan Parser y revisan el resultado de parse()
    • EXPLAIN VACUUM; y EXPLAIN QUERY PLAN VACUUM; son casos exitosos
    • EXPLAIN; y EXPLAIN QUERY PLAN; son casos fallidos
    • Los casos fallidos verifican la condición de la gramática sql-stmt de SQLite de que después de EXPLAIN debe venir una sentencia

Incomodidades de macro_rules!

  • El soporte de rust-analyzer dentro de macro_rules! es limitado
    • No hay IntelliSense real
    • No existe ir a definición
    • No hay hover con firmas para literales ni estructuras del lenguaje
  • cargo fmt no formatea ni indenta el interior de macro_rules! ni los sitios donde se invoca el macro
  • treesitter y chroma a veces tienen dificultades con el resaltado de sintaxis de macro_rules!
  • La documentación sobre macros también tiende a ser escasa

matches! y match brillan al comparar caracteres

  • La comparación de caracteres en el lexer es la base de otros procesos, y los patrones de matches! y match de Rust vuelven esta parte más concisa
  • La detección de números en SQLite se escribe con matches!
    • +, -
    • _
    • .
    • a..=f, A..=F
    • 0..=9
  • La detección de identificadores también se expresa como matches!(c, 'a'..='z' | 'A'..='Z' | '_' | '0'..='9')
  • El bucle principal del lexer divide por match el carácter actual
    • Omite los espacios en blanco
    • *, ;, ,, % y otros generan cada uno el token correspondiente
    • El ejemplo de manejo de símbolos desconocidos se omite y aparece como panic!("whoops")

Manejo de la estructura gramatical de SQL mediante coincidencia de tokens

  • El lexer convierte el flujo de caracteres en un flujo de estructuras Token con información de posición y tipo, y el parser las consume para construir el AST
  • El enum Type incluye Keyword, Ident, Number, String, Blob, Boolean, ParamName, Param, Dot, Asteriks, Semicolon, Percent, Comma, Eof y otros
  • sql_stmt_prefix es la función del parser que maneja las sentencias EXPLAIN según la documentación de SQLite
    • Si el token actual es Type::Keyword(Keyword::EXPLAIN), crea un nodo Explain y consume EXPLAIN
    • Si el siguiente token es QUERY, consume consecutivamente QUERY y PLAN
    • Después parsea la sentencia SQL real como child
    • Si no es EXPLAIN, llama al manejo normal de sql_stmt
  • literal_value crea nodos Literal para cadenas, números, blobs, booleanos y también para literales de palabra clave como NULL, CURRENT_TIME, CURRENT_DATE y CURRENT_TIMESTAMP

Mostrar errores y usar Option

  • El lexer y el parser muestran errores al usuario en casos como la falta del punto y coma al final de una sentencia SQL
  • El operador ? de Rust se usa para manejar y propagar errores
  • Option::is_some_and se usa para comprobar si el siguiente carácter o el actual existe y además cumple una condición
    • self.source.get(self.pos + 1).is_some_and(...)
    • self.source.get(self.pos).is_some_and(...)
  • Option::map se aprovecha para convertir el siguiente byte a char en entradas Vec<u8>
  • Option::map_or se usa para comparar tipos solo cuando existe el token actual o el siguiente; si no, devuelve false

Procesar números y blobs con iteradores

  • El parsing de números en SQLite permite _, pero el parsing numérico de Rust no lo permite, así que el lexer consume el literal incluyendo _ y luego lo elimina antes de parsearlo
  • Este proceso se escribe como una cadena de iteradores
    • Se toma un slice de bytes
    • Cada byte se convierte a char
    • Se filtran solo los caracteres distintos de _
    • Se recolecta en un String
  • En esta situación se usa unwrap_or_default(), pero una cadena vacía de todos modos no es válida como número, así que el parser terminará fallando
  • En Go, para hacer lo mismo, habría que recorrer la lista de caracteres, escribir los bytes en un strings.Builder y luego volver a crear una cadena
  • Los blobs de SQLite permiten datos hexadecimales con forma x'<hex>', así que se recorre cada carácter de la cadena con chars().enumerate() y se verifica si es is_ascii_hexdigit()
    • enumerate se usa para obtener información de posición del carácter inválido para mostrar el error
    • Si aparece un carácter hexadecimal no válido, se genera un error y se detiene el procesamiento

Lecturas relacionadas

1 comentarios

 
GN⁺ 2024-11-09
Comentarios de Hacker News

  • Hace apenas dos meses habría pensado igual que el autor, pero seguía chocando con el límite rígido de Rust: el borrow checker
    Los tipos algebraicos, por ejemplo los enum y el pattern matching, me encantaban, pero por el borrow checker y las consideraciones de memoria de bajo nivel terminé pasando más tiempo peleándome con el borrow checker que con el problema de lenguajes de programación que era el núcleo del proyecto
    Así que la tokenización y el parsing estuvieron bien, pero el intérprete y el chequeo de tipos se volvieron dolorosos; buscando un lenguaje más adecuado, evalué F#, Zig/C y Go, y finalmente descubrí OCaml
    Me convenció porque se ve como un Haskell con una sintaxis más amigable, o como Rust sin lifetimes; además, el primer compilador de Rust fue escrito en OCaml y es muy conocido en el ámbito de los lenguajes de programación
    Todavía lo estoy aprendiendo, así que es difícil hacer una evaluación justa, pero hasta ahora se acerca mucho a lo que estaba buscando

    • Cuando sale el tema de Go, por alguna razón siempre me irrita
      Es práctico y rápido, no es realmente de bajo nivel, compila rápido y, sobre todo, es popular, así que tiene todas las librerías y siento que debería usarlo
      Pero el lenguaje en sí me disgusta de una forma casi irracional, y siento que todo en él es feo
      Es un lenguaje creado en 2009 por gente del mundo de C, y parece que no conocieran, ni siquiera para los estándares de la época, las cosas interesantes que habían pasado en diseño de lenguajes de programación durante los 20 años anteriores
      Incluso PHP en 2009 era un lenguaje más moderno y mejor diseñado que Go, y no puedo quitarme la sensación de que Go tampoco ha mejorado mucho desde entonces
    • Creo que la clave al trabajar con un árbol de sintaxis abstracta en Rust es no guardar cosas como strings dentro del árbol
      En su lugar, conviene usar algo que permita cheap clone e interning, como una biblioteca de strings estáticos, y para las ubicaciones en el texto usar solo índices
      Si es posible, hay que evitar por completo guardar referencias
      Cuantas más cosas puedas mantener como objetos de clonación barata/gratuita, menos pelearás con el borrow checker, y si hace falta puedes pasar a clone
      Para la parte real del intérprete, las bibliotecas que ayudan con la gestión de memoria mediante enfoques como arenas son bastante útiles
      Es un dominio muy especializado, pero ofrece rendimiento y usabilidad a la vez, y proyectos como Ruffle usan mucho estos patrones
      Dicho eso, OCaml y Haskell hacen estas cosas “gratis” gracias al conteo de referencias y la recolección de basura incorporados, aunque igual me gusta la idea de ir muy rápido con Rust
    • He usado bastante Go durante el último año, pero no creo que lo usaría para escribir parsers
      Go se parece más a un C modernizado, y el modelo que ofrece es muy simple
      Viniendo de C#, esa simplicidad hizo que me costara más aprenderlo; la baja carga conceptual es una ventaja, y encaja bien en aplicaciones pequeñas y enfocadas donde se puede aceptar el compromiso de la verbosidad
      Si tuviera que recomendar algo, diría F#, o incluso C# moderno
      Aunque Microsoft esté involucrada, vivir en un mundo donde no se usa absolutamente nada hecho por una gran empresa malvada se vuelve difícil
      Java, Go, Python, TypeScript/JavaScript y Swift también caen en esa categoría, y entonces casi no quedan opciones
      Me interesa saber qué opinas después de usar OCaml durante más o menos un año
      Los lenguajes tipo Haskell son interesantes, pero en mi caso Haskell en sí no compensó su curva de aprendizaje, y Rust es parecido
      En C# profundicé bastante en el sistema de tipos y lo dominé, pero no tengo tiempo para meterme con Rust al mismo nivel
    • Go también se usa mucho del lado del cliente, y en móviles tiene un soporte bastante bueno gracias a go-mobile
      Claro que agrega unos 10 a 20 MB al binario y al uso de memoria, pero para los estándares actuales eso no es casi nada
      Por ejemplo, parece que Tailscale usa Go como capa WireGuard multiplataforma en sus apps móviles y de escritorio, y aparentemente funciona bien
      No haría una UI nativa en Go, pero es excelente para tareas de bajo nivel
      TinyGo también permite escribir Go para microcontroladores o WebAssembly; hay muchas cosas no soportadas, pero se puede usar una parte considerable de la biblioteca estándar
    • No llamaría a Go un lenguaje del lado del servidor
      Por ejemplo, el compilador de Go también está escrito en Go
      Gracias a la compilación cruzada y a binarios relativamente pequeños, el despliegue es muy fácil
      Eso sí, es cierto que le falta azúcar sintáctica, y no encaja bien con el pattern matching de estilo funcional

  • La forma de abordar el parsing me parece algo extraña, y me da la impresión de que el autor no está demasiado familiarizado con Rust ni con los conceptos de lenguajes de programación en los que se basa
    Por mencionar algunas cosas, el AST probablemente sería mucho más simple si se definiera con tipos algebraicos
    No parece probable que la gramática de sqlite vaya a expandirse de pronto agregando un montón de nodos nuevos que exijan una codificación compleja
    La codificación actual parece el tipo de forma que se le ocurriría a alguien familiarizado con la orientación a objetos, pero no con los tipos algebraicos
    La frase “los macros funcionan de forma distinta en la mayoría de los lenguajes, pero su razón principal es eliminar duplicación de código y reducir repetición” también podría decirse de cualquier mecanismo de abstracción, como las funciones
    La característica que define a los macros es que se ejecutan en tiempo de compilación
    Si quieres ver cómo estructurar un parser de forma prolija, la investigación sobre parser combinators puede ser un buen punto de partida

    • El autor nunca afirmó ser un programador con mucha experiencia
      El título del blog también es “Why I love ...”, y aunque las observaciones parecen válidas, señalar su falta de experiencia no me parece realmente necesario
      Que a alguien le guste programar es algo bueno, y la experiencia llegará con el tiempo
    • En el contexto del post, lo que quiere es generar definiciones de structs
      Eso no se puede hacer con funciones

  • Desde la perspectiva de haber escrito un pequeño parser [0] para la notación de ajedrez Forsyth-Edwards, creo que Haskell es abrumadoramente superior en términos de simplicidad y legibilidad
    Se lee casi como BNF y casi no hay ceremonia técnica, así que puedes enfocarte en la gramática que realmente quieres parsear
    [0] https://github.com/ryandv/chesskell/blob/master/src/Chess/Fa...
    [1] https://en.wikipedia.org/wiki/Forsyth%E2%80%93Edwards_Notati...

    • Haskell definitivamente es lo mejor para aprovechar combinadores de parsers, pero para trabajar con el resultado todavía tienes que quedarte con Haskell
    • ¿No es que esto no usa solo Haskell puro, sino una biblioteca de combinadores de parsers?
      Me pregunto si hay alguna razón clara por la que no se pueda aplicar un enfoque similar en Rust
      Por ejemplo, winnow [1] parece ofrecer un estilo suficientemente declarativo, y Rust también tiene varias otras bibliotecas de combinadores de parsers
      [1]: https://docs.rs/winnow/latest/winnow/
    • No considero que FEN sea un gran ejemplo de parsing
      Porque se puede implementar con una función simple que tenga un solo bucle
      Hace unos días escribí un “parser” de FEN para una implementación experimental de quad-bitboard y prácticamente se escribió solo
      Además, soy el autor de chessIO en Hackage

  • Escribí un desensamblador de eBPF y un emulador a medio hacer en Rust, y Rust me pareció un lenguaje bastante agradable para tareas de parsing
    Dicho eso, cuando el autor necesita macros antes de haber avanzado siquiera 1/6 del caso de estudio, siento que eso debilita su argumento
    Las macros no son generación de código completa, pero tampoco se sienten del todo como trabajar de manera idiomática dentro del lenguaje
    No lo digo como crítica; de hecho creo que Rust es bastante fuerte en esta área

    • ¿Cómo se puede definir una gramática infinita en Rust?
      Por ejemplo, la regla libre de contexto S ::= abc|aabbcc|aaabbbccc|... puede parsear efectivamente a^Nb^Nc^N, y eso es un ejemplo de gramática sensible al contexto
      Es un ejemplo simple, pero en la práctica se ven cosas parecidas; un caso es cuando un lenguaje permite definir operadores
      ¿Cómo maneja Rust ese tipo de cosas?
    • Si es posible, estaría bueno que compartieras el enlace al desensamblador de eBPF
      Se ve interesante

  • Por experiencia escribiendo parsers y lexers con Ragel y usando Go, Java, C++ y C, con algún generador de boilerplate suficientemente bueno, incluso C puro es tan bueno como el código Rust que describe el autor
    Tal vez incluso mejor por su simplicidad
    Por ejemplo, la mayor parte del código necesario para un parser de JSON es más o menos esto
    https://github.com/gritzko/librdx/blob/master/JSON.lex
    En realidad, ese eBNF solo crea el lexer, y la parte del parser tampoco es tan impresionante: son 120 líneas y bastante repetitivas
    https://github.com/gritzko/librdx/blob/master/JSON.c
    Al final, creo que la infraestructura de parsers evoluciona hasta el punto en que puedes crear un parser solo con eBNF, y ese es el punto de saturación

    • Esa repetitividad puede verse como una desventaja, no como una ventaja
      Siento que los tipos de datos algebraicos de Rust hacen que sea mucho más fácil trabajar con el árbol sintáctico generado
      Aun así, estoy de acuerdo en que un poco de generación de código o magia con macros puede hacer que C sea bastante manejable
    • Me gusta mucho Ragel
      Pero este código
      https://github.com/gritzko/librdx/blob/master/JSON.lex
      ¿no acepta [ como JSON válido?
      delimiter = OpenObject | CloseObject | OpenArray | CloseArray | Comma | Colon;
      primitive = Number | String | Literal;
      JSON = ws* ( primitive? ( ws* delimiter ws* primitive? )* ) ws*;
      Root = JSON;
      Parece que en JSON puedes elegir solo un delimiter y luego elegir cero de todo lo demás
      Normalmente empiezo mirando el RFC
      https://datatracker.ietf.org/doc/html/rfc4627#autoid-3
      Ni siquiera estoy seguro de que se pueda implementar JSON con Ragel
      Ragel solo puede procesar lenguajes regulares, y entiendo que JSON es un lenguaje libre de contexto
    • La causa de Cloudbleed fue un bug en C/Ragel, y también fue una de las razones por las que Cloudflare migró a Rust
      https://en.wikipedia.org/wiki/Cloudbleed

  • En relación con esto, me gusta la charla de Rob Pike sobre escaneo léxico en Go
    Es un enfoque educativo y elegante
    https://www.youtube.com/watch?v=HxaD_trXwRE

    • Esa charla es excelente, pero recuerdo haber visto después una discusión sobre que Go en realidad no usa esa técnica
      Creo que la razón era la sobrecarga de planificación de goroutines o patrones ineficientes de asignación de memoria
      La mejor discusión que encontré es [1]
      Otra gran charla sobre cómo crear lexers y parsers eficientes es “Practical Data Oriented Design” de Andrew Kelley [2]
      En resumen, explica varias estrategias para aumentar el throughput haciendo que el programa sea más amigable con la caché, a la vez que se reduce su uso de memoria
      1: https://news.ycombinator.com/item?id=31649617
      2: https://www.youtube.com/watch?v=IroPQ150F6c
    • Esa charla parece tener más que ver con la forma de expresar concurrencia en problemas donde la concurrencia surge de manera natural, que con el lexing en sí

  • Tuve una experiencia sorprendente
    Pude usar tal cual una biblioteca de combinadores de parser que usaba para un parser de compilador de alto nivel, llevarla a un entorno no-std, compilarla para microcontroladores y desplegarla como un parser de protocolo de alto rendimiento en un entorno embebido
    Era exactamente la misma biblioteca
    La diferencia fue más o menos reducir el uso de String y usar más &'static str
    Así que jugar con compiladores se transfiere bastante bien a la capacidad de crear parsers de protocolos embebidos

  • Lo que me resultó difícil al escribir un parser de AST completo en Rust fue representar una jerarquía de tipos AST concretos, incluyendo upcasting y downcasting
    Encontré una forma de hacerlo, pero requirió trucos raros de tipos como PhantomData y macros
    Creo que también aquí hicieron falta macros bastante excesivas
    Me da curiosidad cómo se ve el trabajo previo relacionado

    • Los tipos de datos algebraicos de Rust y la sintaxis de matching parecen buenos
      Hasta que llegas al upcasting/downcasting, claro
      No tengo suficiente experiencia con Rust como para saber si hay una buena forma de manejarlo
      Tal vez sea posible con traits dinámicos
    • Si es open source, me pregunto si hay un repositorio público

  • ¿Cómo se depura este tipo de código con macros, o cómo lo entiende alguien que acaba de entrar al codebase?
    Aunque vea los usos de la macro node! y su definición, parece difícil entender qué código se genera realmente
    Me pregunto si basta con ejecutar ejemplos y ver qué sugerencias de tipos aparecen, si al hacer hover en el IDE se puede ver la versión expandida, o si para estar seguro hay que consultar el código compilado
    Como solo trabajo con JS/TS y no toco macros, me da curiosidad ese flujo de trabajo

    • Si ejecutas $ cargo expand, puedes ver el código resultante
      Rust en realidad es casi varios lenguajes: Rust “vanilla”, macros declarativas y macros procedurales tienen cada una capacidades y dialectos un poco distintos
      Con el tiempo te acostumbras a manejar cada una
      Las pruebas unitarias también son un buen espacio de experimentación para entender el impacto de modificar macros
    • rust-analyzer, el LSP de Rust que se usa en VSCode y otros editores, puede expandir recursivamente macros declarativas y procedurales
      No está tan mal, pero mientras menos macros procedurales haya en un codebase, mejor
      Las macros declarativas son un poco más fáciles de entender, y mucho más fáciles de mantener y probar
      Siento algo parecido con la generación de código opaca en otros lenguajes

  • Para parsear la sintaxis de sqlite, mucha suerte
    Hace unos años tuve que escribir por trabajo un parser para un subconjunto bastante pequeño de sqlite
    Me encanta sqlite y siempre es una fuente de inspiración
    Los diagramas de ferrocarril son tremendamente útiles
    https://www.sqlite.org/syntaxdiagrams.html
    Creo que el generador de parsers lemon no recibe suficiente reconocimiento
    https://sqlite.org/src/doc/trunk/doc/lemon.html
    En cuanto a elección de lenguaje, cualquier lenguaje con tipos de datos algebraicos encaja bien
    Incluso TypeScript puede ser excelente para este propósito
    Hace tiempo también escribí un pequeño artículo introductorio sobre escribir parsers a mano en Rust
    https://www.nhatcher.com/post/a-rustic-invitation-to-parsing...