jsongrep: Uma Ferramenta de Consulta JSON Baseada em DFA Que Supera o jq em Benchmarks

O que o jsongrep faz

jsongrep (binário jg) recebe uma consulta e uma entrada JSON e imprime cada valor cujo caminho através do documento corresponda à consulta. Ele trata documentos JSON como árvores onde objetos e arrays são ramificações, escalares são folhas, e chaves e índices rotulam as arestas. A linguagem de consulta é uma linguagem regular sobre o alfabeto de chaves e índices.

Recursos da Linguagem de Consulta

Caminhos com ponto selecionam campos aninhados por nome: jg 'roommates[0].name' retorna roommates.[0].name: "Alice".

Curingas correspondem a qualquer chave única (*) ou qualquer índice de array ([*]): jg 'favorite_drinks[*]' retorna todos os elementos do array.

Alternância (|) corresponde a qualquer ramificação: jg 'name | roommates' retorna ambos os campos.Descida recursiva usa * e [*] dentro de uma estrela de Kleene para percorrer arbitrariamente profundamente: jg '(* | [*])*.name' encontra cada campo name em qualquer profundidade. A flag -F fornece uma abreviação: jg -F name faz o mesmo.

Opcional (?) corresponde a zero ou uma ocorrência: jg 'roommates[0].favorite_food?' retorna tanto o objeto pai quanto o valor do campo.

Abordagem Técnica

jsongrep compila consultas em autômatos finitos determinísticos (DFA) usando um pipeline que inclui: análise da consulta, tratamento do JSON como uma árvore, construção de um NFA usando o algoritmo de Glushkov, determinização via construção de subconjuntos, e busca usando DFS com transições DFA. Isso permite processamento em uma única passagem com trabalho O(1) por símbolo de entrada, evitando retrocesso, pilhas de recursão e explosão exponencial em consultas patológicas.

O autor observa que isso difere fundamentalmente de ferramentas como jq, jmespath ou jsonpath-rust, que interpretam expressões de caminho, avaliam consultas em cada nó, verificam predicados e descem recursivamente—potencialmente revisitando subárvores ou mantendo listas de trabalho com consultas de descida recursiva.

Instalação e Disponibilidade

Instale do crates.io: cargo install jsongrep. Como ripgrep (que inspirou o projeto), jsongrep é multiplataforma com binários disponíveis e escrito em Rust.

A ferramenta detecta se a saída é canalizada para comandos como less ou sort e omite caminhos JSON por padrão (substitua com a opção --with-path).