Por que usar Rust para tokenização e análise sintática

 (xnacly.me)
2 pontos por GN⁺ 2024-11-09 | 1 comentários | Compartilhar no WhatsApp
  • sqleibniz é uma ferramenta de análise estática que busca verificar a sintaxe do SQL no dialeto SQLite, a existência de tabelas, colunas e funções, e condições em tempo de execução; para isso, tokenização e parsing são etapas centrais
  • O macro_rules! do Rust ajuda a criar estruturas de nós de AST, implementações do trait Node e testes baseados em tabela no estilo Go sem repetição
  • Usando padrões com matches! e match, é possível transportar para o código, de forma próxima, ramificações gramaticais como literais numéricos do SQLite, identificadores, símbolos e EXPLAIN QUERY PLAN
  • is_some_and, map e map_or de Option, junto com o operador ?, tornam concisos o tratamento da presença de valores, transformações, valores padrão e propagação de erros ao processar entradas e fluxos de tokens
  • Iteradores de Rust são usados para remover _ de literais numéricos, validar caracteres hexadecimais dentro de blobs e calcular posições de erro, o que torna o código de tokenização e parsing mais legível

Fluxo de análise do sqleibniz

  • sqleibniz é uma ferramenta de análise SQL em desenvolvimento voltada ao dialeto SQLite
  • Para uma entrada SQL, ela pretende realizar verificação de sintaxe, confirmar a existência de tabelas, colunas e funções, e validar condições em conjunto com o runtime SQLite embutido
  • As mensagens de erro têm como objetivo oferecer contexto e explicações, além de permitir ignorar diagnósticos específicos
  • O fluxo de análise começa com análise léxica/tokenização, segue para o parsing de SQL conforme a documentação do SQLite e depois para a análise da estrutura resultante
  • Depois de concluir a parte de análise estática, também está planejada a criação de um servidor LSP para SQL

Removendo repetição em nós de AST com macros

  • Os nós de AST do sqleibniz são estruturas que contêm um Token, e todos os nós precisam implementar o trait Node
  • O trait Node usa std::fmt::Debug como supertrait, de modo que apenas tipos que satisfazem Debug podem implementar Node
  • Para evitar repetir, em cada nó, a definição da estrutura e a implementação de fn token(&self) -> &Token, a macro node! gera esses elementos
    • O nome do nó é recebido pela metavariável ident
    • A string de documentação é recebida pela metavariável literal
    • Campos adicionais são tratados de forma repetida no formato $($field_name:ident:$field_type:ty),*
  • O nó Literal tem apenas o campo de token, enquanto o nó Explain tem também o campo child: Option<Box<dyn Node>>
  • Comentários de documentação são passados ao compilador como argumento da macro na forma #[doc = $documentation], em vez de ///

Implementando testes baseados em tabela no estilo Go com macros Rust

  • O padrão de testes baseados em tabela do Go, em que se percorre um array de casos de entrada e cada caso é executado como um teste independente, é reproduzido em Rust com macros
  • Os testes do lexer usam as macros test_group_pass_assert! e test_group_fail!
    • Os testes que passam inserem a entrada no Lexer e comparam a lista de tipos de token do resultado de Lexer.run() com o valor esperado
    • Os testes que falham verificam se o vetor de tokens resultante está vazio e se há um ou mais erros em Lexer.errors
    • Ao executar cargo test, cada caso produz feedback ok ou fail como se fosse uma função de teste separada
  • Os testes do parser seguem a mesma estrutura, mas inicializam o Parser depois de executar o lexer e verificam o resultado de parse()
    • EXPLAIN VACUUM; e EXPLAIN QUERY PLAN VACUUM; são casos de sucesso
    • EXPLAIN; e EXPLAIN QUERY PLAN; são casos de falha
    • Os casos de falha verificam a condição de que, pela gramática sql-stmt do SQLite, é necessária uma instrução depois de EXPLAIN

Pontos incômodos do macro_rules!

  • Dentro de macro_rules!, o suporte do rust-analyzer é limitado
    • Não há IntelliSense real
    • Não há navegação para definição
    • Não há hover para assinaturas de literais e estruturas da linguagem
  • O cargo fmt não formata nem indenta o interior de macro_rules! nem os locais de chamada de macros
  • treesitter e chroma às vezes têm dificuldade com realce de sintaxe de macro_rules!
  • A documentação sobre macros também é relativamente insuficiente

matches! e match se destacam na correspondência de caracteres

  • A comparação de caracteres do lexer é a base de outros processamentos, e a macro matches! e os padrões com match do Rust tornam essa parte concisa
  • A identificação de números do SQLite é escrita com matches!
    • +, -
    • _
    • .
    • a..=f, A..=F
    • 0..=9
  • A identificação de identificadores também é expressa como matches!(c, 'a'..='z' | 'A'..='Z' | '_' | '0'..='9')
  • O loop principal do lexer divide o caractere atual com match
    • Caracteres de espaço em branco são ignorados
    • *, ;, ,, % etc. geram seus tokens correspondentes
    • O exemplo de tratamento de símbolos desconhecidos é omitido e marcado com panic!("whoops")

Tratando estruturas gramaticais SQL por correspondência de tokens

  • O lexer transforma o fluxo de caracteres em um fluxo de estruturas Token com informações de posição e tipo, e o parser consome isso para criar a AST
  • O enum Type inclui Keyword, Ident, Number, String, Blob, Boolean, ParamName, Param, Dot, Asteriks, Semicolon, Percent, Comma, Eof etc.
  • sql_stmt_prefix é uma função do parser que trata a instrução EXPLAIN da documentação do SQLite
    • Se o token atual for Type::Keyword(Keyword::EXPLAIN), ela cria um nó Explain e consome EXPLAIN
    • Se o próximo token for QUERY, consome QUERY e PLAN em sequência
    • Depois disso, faz o parsing da instrução SQL real como child
    • Se não for EXPLAIN, chama o tratamento normal de sql_stmt
  • literal_value cria nós Literal para strings, números, blobs e booleanos, bem como para literais de palavra-chave como NULL, CURRENT_TIME, CURRENT_DATE e CURRENT_TIMESTAMP

Exibição de erros e uso de Option

  • O lexer e o parser mostram erros ao usuário em casos como ausência de ponto e vírgula no fim de uma instrução SQL
  • O operador ? do Rust é usado para tratamento e propagação de erros
  • Option::is_some_and é usado para verificar se o próximo caractere ou o caractere atual existe e satisfaz uma condição
    • self.source.get(self.pos + 1).is_some_and(...)
    • self.source.get(self.pos).is_some_and(...)
  • Option::map é usado para converter o próximo byte de uma entrada Vec<u8> em char
  • Option::map_or é usado para comparar o tipo apenas quando há um token atual ou próximo token; caso contrário, retorna false

Tratando números e blobs com iteradores

  • O parsing de números do SQLite permite _, mas o parsing de números em Rust não permite _; portanto, o lexer consome o valor incluindo _ e remove esse caractere antes do parsing
  • Esse tratamento é escrito como uma cadeia de iteradores
    • Obtém uma fatia de bytes
    • Converte cada byte em char
    • Filtra apenas os caracteres que não são _
    • Coleta tudo em uma String
  • Nesse caso, usa-se unwrap_or_default(), mas uma string vazia não é um número válido, então o parser falhará de qualquer forma
  • Em Go, para fazer o mesmo processamento, seria necessário percorrer a lista de caracteres, escrever bytes em um strings.Builder e então criar a string novamente
  • Blobs SQLite permitem dados hexadecimais no formato x'<hex>', então cada caractere da string é percorrido com chars().enumerate() para verificar se é is_ascii_hexdigit()
    • enumerate é usado para obter a posição do caractere inválido para exibição do erro
    • Ao encontrar um caractere hexadecimal inválido, um erro é criado e o processamento é interrompido

Leituras relacionadas

1 comentários

 
GN⁺ 2024-11-09
Comentários do Hacker News

  • Até dois meses atrás eu provavelmente pensaria como o autor, mas continuei esbarrando na fronteira rígida do Rust, o borrow checker.
    Tipos de dados algébricos, como Enum e pattern matching, eram realmente ótimos, mas por causa do borrow checker e das considerações de memória de baixo nível, acabei passando mais tempo brigando com o borrow checker do que com o problema de linguagem de programação que era o núcleo do projeto.
    Então tokenização e parsing foram OK, mas o interpretador e a verificação de tipos viraram um sofrimento; procurando uma linguagem mais adequada, avaliei F#, Zig/C e Go até descobrir OCaml.
    A sintaxe parecia um Haskell amigável e algo como Rust sem lifetimes, o que me convenceu; além disso, o primeiro compilador de Rust foi escrito em OCaml, e ela é bem conhecida na área de linguagens de programação.
    Ainda estou aprendendo, então é difícil fazer uma avaliação justa, mas até agora parece muito próximo do que eu estava procurando.

    • Quando Go entra na conversa, por algum motivo sempre fico irritado.
      Ele é prático e rápido, não é realmente de baixo nível, compila rápido e, acima de tudo, é popular, então tem todas as bibliotecas, o que faz parecer que eu deveria usá-lo.
      Mas eu detesto a linguagem em si de um jeito quase irracional, e sinto que tudo nela é feio.
      É uma linguagem criada em 2009 por pessoas do lado do C e, mesmo para os padrões da época, parece ignorar as coisas interessantes que aconteceram no design de linguagens de programação nos 20 anos anteriores.
      Mesmo o PHP de 2009 era uma linguagem mais moderna e mais bem projetada que Go, e não consigo me livrar da sensação de que Go não melhorou muito desde então.
    • Ao lidar com uma árvore sintática abstrata em Rust, acho que o ponto central é não armazenar coisas como strings na árvore.
      Em vez disso, é melhor usar algo como uma biblioteca de strings estáticas que permita clone barato e interning, e usar apenas índices para posições no texto.
      Se possível, deve-se evitar a todo custo armazenar referências.
      Quanto mais você guardar coisas que tenham clone barato/gratuito, menos vai brigar com o borrow checker e, se necessário, pode simplesmente recorrer a clone.
      Na parte do interpretador em si, bibliotecas que ajudam no gerenciamento de memória, como arenas, são bastante úteis.
      É um domínio muito especializado, mas oferece desempenho e usabilidade ao mesmo tempo, e projetos como o Ruffle usam bastante esse padrão.
      Dito isso, OCaml e Haskell fazem essas coisas “de graça” graças à contagem de referências e à coleta de lixo embutidas, mas ainda gosto da ideia de ir muito rápido com Rust.
    • Usei bastante Go no último ano, mas acho que não o usaria para escrever parsers.
      Go está mais próximo de um C modernizado, e o modelo que ele oferece é muito simples.
      Vindo de C#, essa simplicidade na verdade tornou o aprendizado mais difícil para mim; a baixa carga conceitual é uma vantagem, e ele se encaixa bem em aplicações pequenas e focadas, em que se aceita o trade-off da verbosidade.
      Se fosse recomendar, eu diria F#, ou até C# moderno.
      A Microsoft está envolvida, sim, mas fica difícil viver em um mundo em que você não usa absolutamente nada feito por uma megacorporação maligna.
      Java, Go, Python, TypeScript/JavaScript e Swift também caem nessa categoria; aí quase não sobra opção.
      Tenho curiosidade sobre o que você vai achar depois de usar OCaml por mais ou menos um ano.
      Linguagens do tipo Haskell são interessantes, mas o Haskell em si não me trouxe uma boa relação entre curva de aprendizado e benefício, e Rust é parecido.
      Em C#, eu me aprofundei bastante no sistema de tipos e fiquei proficiente, mas não tenho tempo para mergulhar nesse nível em Rust.
    • Go também é muito usado no lado cliente, e no mobile tem um suporte bem decente graças ao go-mobile.
      Claro, isso adiciona algo como 10–20 MB ao binário e ao uso de memória, mas pelos padrões de hoje isso é quase nada.
      Por exemplo, o Tailscale parece usar Go como camada WireGuard multiplataforma em seus apps mobile e desktop, e parece funcionar bem.
      Eu não criaria uma UI nativa em Go, mas para tarefas de baixo nível ele é excelente.
      O TinyGo também permite escrever Go para microcontroladores ou WebAssembly; há muita coisa sem suporte, mas boa parte da biblioteca padrão pode ser usada.
    • Eu não chamaria Go de linguagem server-side.
      Por exemplo, o compilador de Go também é escrito em Go.
      Graças à compilação cruzada e aos binários relativamente pequenos, a distribuição é muito fácil.
      Dito isso, é verdade que falta açúcar sintático, e ele não se encaixa bem em pattern matching no estilo funcional.

  • Como abordagem para parsing, parece meio estranha, e fico com a impressão de que o autor não está muito familiarizado com Rust e com os conceitos de linguagens de programação que o fundamentam.
    Para citar alguns pontos: a AST provavelmente ficaria muito mais simples se fosse definida como tipos de dados algébricos.
    Não parece provável que a gramática do sqlite se expanda de repente criando um monte de novos nós a ponto de exigir uma codificação complexa.
    A codificação atual parece algo que uma pessoa acostumada a orientação a objetos, mas não a tipos de dados algébricos, imaginaria.
    A afirmação de que “macros funcionam de forma diferente na maioria das linguagens, mas o principal motivo é eliminar duplicação de código e reduzir repetição” também poderia ser feita sobre qualquer mecanismo de abstração, como funções.
    A característica definidora de macros é que elas são executadas em tempo de compilação.
    Para ver maneiras de estruturar um parser de forma limpa, a pesquisa sobre combinadores de parser pode ser um bom ponto de partida.

    • O autor nunca afirmou ser um programador experiente.
      O título do blog também é “Why I love ...”, e embora as críticas pareçam válidas, não parece necessário apontar falta de experiência.
      É bom que alguém goste de programar, e a experiência virá com o tempo.
    • No contexto do post do blog, ele quer gerar definições de structs.
      Isso não dá para fazer com funções.

  • Como alguém que já escreveu um pequeno parser [0] para a notação de xadrez Forsyth-Edwards, acho que Haskell é imbatível em termos de simplicidade e legibilidade
    Ele é lido quase como BNF e tem pouquíssima cerimônia técnica, então dá para focar na gramática que você está realmente tentando fazer o parsing
    [0] https://github.com/ryandv/chesskell/blob/master/src/Chess/Fa...
    [1] https://en.wikipedia.org/wiki/Forsyth%E2%80%93Edwards_Notati...

    • Haskell certamente é excelente quando se trata de usar parser combinators, mas para lidar com o resultado você ainda precisa ficar com Haskell
    • Isso não foi feito só com Haskell puro, mas com uma biblioteca de parser combinators, não?
      Fico curioso se há algum motivo claro para uma abordagem parecida não funcionar em Rust
      Por exemplo, winnow [1] parece oferecer um estilo bastante declarativo, e há várias outras bibliotecas de parser combinators em Rust
      [1]: https://docs.rs/winnow/latest/winnow/
    • Não vejo FEN como um ótimo exemplo de parsing
      Porque dá para implementá-lo como uma função simples com um único loop
      Alguns dias atrás escrevi um “parser” de FEN para uma implementação experimental de quad-bitboard, e ele praticamente se escreveu sozinho
      A propósito, sou o autor de chessIO no Hackage

  • Escrevi um disassembler de eBPF e um emulador meio inacabado em Rust, e Rust foi uma linguagem bem agradável para trabalhos do tipo parsing
    Dito isso, quando o autor precisa de macros antes mesmo de passar por 1/6 do estudo de caso, isso parece enfraquecer o argumento dele
    Macros não são geração completa de código, mas também não dão uma sensação muito forte de estar trabalhando idiomaticamente dentro da linguagem
    Não estou tentando criticar; acho que Rust é, de fato, bem forte nessa área

    • Como dá para definir gramáticas infinitas em Rust?
      Por exemplo, a regra livre de contexto S ::= abc|aabbcc|aaabbbccc|... consegue fazer parsing efetivo de a^Nb^Nc^N, e isso é um exemplo de gramática sensível ao contexto
      É um exemplo simples, mas coisas parecidas aparecem na prática; um caso é quando a linguagem permite definições de operadores
      Como Rust lida com isso?
    • Se possível, seria legal compartilhar o link do disassembler de eBPF
      Parece interessante

  • Pela minha experiência escrevendo parsers e lexers com Ragel e usando Go, Java, C++ e C, se você tiver pelo menos um gerador de boilerplate, C puro fica tão bom quanto o código Rust descrito pelo autor
    Talvez até melhor, pela simplicidade
    Por exemplo, o código necessário para um parser de JSON é basicamente isto
    https://github.com/gritzko/librdx/blob/master/JSON.lex
    Na verdade, esse eBNF só cria o lexer; a parte do parser também não é tão impressionante, tem 120 linhas e é bem repetitiva
    https://github.com/gritzko/librdx/blob/master/JSON.c
    No fim, acho que a infraestrutura de parsers evolui até o ponto em que é possível criar um parser só com eBNF, e esse é o ponto de saturação

    • Essa repetição pode ser vista como uma desvantagem, não uma vantagem
      Sinto que os tipos algébricos de dados de Rust tornam muito mais fácil lidar com a árvore sintática gerada
      Ainda assim, concordo que um pouco de geração de código ou magia de macros pode tornar C bastante manejável
    • Gosto muito de Ragel
      Mas este código aqui
      https://github.com/gritzko/librdx/blob/master/JSON.lex
      não aceita [ 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 dá para escolher apenas um delimiter em JSON e todo o resto como zero ocorrências
      Normalmente começo olhando pela RFC
      https://datatracker.ietf.org/doc/html/rfc4627#autoid-3
      Nem tenho certeza se é possível implementar JSON com Ragel
      Pelo que sei, Ragel só consegue lidar com linguagens regulares, e JSON é uma linguagem livre de contexto
    • A causa do Cloudbleed foi um bug em C/Ragel, e esse também foi o motivo de a Cloudflare migrar para Rust
      https://en.wikipedia.org/wiki/Cloudbleed

  • Sobre isso, gosto da palestra de Rob Pike sobre varredura léxica em Go
    É uma abordagem didática e elegante
    https://www.youtube.com/watch?v=HxaD_trXwRE

    • Essa palestra é ótima, mas me lembro de ter visto depois uma discussão dizendo que, na prática, o Go não usa essa técnica
      Acho que o motivo era o overhead do escalonamento de goroutines ou padrões ineficientes de alocação de memória
      A melhor discussão que encontrei é [1]
      Outra excelente palestra sobre como criar lexers e parsers eficientes é “Practical Data Oriented Design”, de Andrew Kelley [2]
      Em resumo, ela explica várias estratégias para aumentar o throughput reduzindo o uso de memória do programa e tornando-o mais amigável ao cache
      1: https://news.ycombinator.com/item?id=31649617
      2: https://www.youtube.com/watch?v=IroPQ150F6c
    • Essa palestra parece estar mais relacionada à forma de expressar concorrência em problemas nos quais a concorrência vem naturalmente à mente, do que ao lexing em si

  • Tive uma experiência surpreendente
    Consegui usar, sem mudanças, uma biblioteca de combinadores de parser que eu usava em parsers de compiladores de alto nível em um ambiente no-std, compilá-la para microcontroladores e implantá-la como um parser de protocolo de alta performance em ambiente embarcado
    Usei exatamente a mesma biblioteca
    A diferença foi basicamente reduzir o uso de String e usar mais &'static str
    Então brincar com compiladores acaba se transferindo muito bem para a capacidade de criar parsers de protocolos embarcados

  • A dificuldade que tive ao escrever um parser de AST completo em Rust foi representar uma hierarquia de tipos concretos de AST, incluindo upcasting e downcasting
    Encontrei uma forma de fazer isso, mas precisei de brincadeiras estranhas com tipos, como PhantomData, e macros
    Acho que aqui também foram necessárias macros bem exageradas
    Tenho curiosidade sobre como são os trabalhos anteriores relacionados

    • Os tipos de dados algébricos e a sintaxe de matching do Rust parecem bons
      Pelo menos até chegar a upcasting/downcasting
      Não tenho experiência suficiente com Rust para saber se há uma boa forma de lidar com isso
      Talvez traits dinâmicas funcionem
    • Se for open source, tenho curiosidade para saber se há um repositório público

  • Como se depura esse tipo de código de macro, ou como alguém recém-chegado à codebase entende isso?
    Mesmo olhando os usos da macro node! e a definição da macro, parece difícil entender que código é realmente gerado
    Fico curioso se basta rodar exemplos e ver que dicas de tipo aparecem, se o IDE mostra a versão expandida ao passar o mouse, ou se, para ter certeza, é preciso consultar o código compilado
    Como só trabalho com JS/TS e não mexo com macros, tenho curiosidade sobre esse fluxo de trabalho

    • Ao executar $ cargo expand, você consegue ver o código resultante
      Rust, na verdade, é quase várias linguagens: Rust “vanilla”, macros declarativas e macros procedurais, cada uma com capacidades e dialetos um pouco diferentes
      Com o tempo, você se acostuma a lidar com cada uma delas
      Testes unitários também são um bom espaço de experimentação para entender o impacto de mudanças em macros
    • O rust-analyzer, o LSP de Rust usado no VSCode e afins, consegue expandir recursivamente macros declarativas e procedurais
      Não é tão ruim, mas, quanto menos macros procedurais houver em uma codebase, melhor
      Macros declarativas são um pouco mais fáceis de entender, e muito mais fáceis de manter e testar
      Sinto algo parecido em relação à geração de código opaca em outras linguagens

  • Boa sorte ao fazer parsing da sintaxe do sqlite
    Alguns anos atrás, tive que escrever no trabalho um parser para um subconjunto bem pequeno do sqlite
    Gosto muito do sqlite e ele sempre é uma fonte de inspiração
    Diagramas ferroviários são extremamente úteis
    https://www.sqlite.org/syntaxdiagrams.html
    Acho que o gerador de parser lemon não recebe o devido reconhecimento
    https://sqlite.org/src/doc/trunk/doc/lemon.html
    Em termos de escolha de linguagem, qualquer linguagem com tipos de dados algébricos se encaixa bem
    Até TypeScript pode ser excelente para esse uso
    Há algum tempo também escrevi um pequeno texto introdutório sobre criar um parser à mão em Rust
    https://www.nhatcher.com/post/a-rustic-invitation-to-parsing...