jsongrep : Un outil de requête JSON basé sur un DFA qui surpasse jq dans les benchmarks

Ce que fait jsongrep

jsongrep (binaire jg) prend une requête et une entrée JSON et affiche chaque valeur dont le chemin à travers le document correspond à la requête. Il traite les documents JSON comme des arbres où les objets et les tableaux se ramifient, les scalaires sont des feuilles, et les clés et indices étiquettent les arêtes. Le langage de requête est un langage régulier sur l'alphabet des clés et indices.

Fonctionnalités du langage de requête

Les chemins par points sélectionnent les champs imbriqués par nom : jg 'roommates[0].name' retourne roommates.[0].name: "Alice".

Les caractères génériques correspondent à n'importe quelle clé unique (*) ou n'importe quel indice de tableau ([*]) : jg 'favorite_drinks[*]' retourne tous les éléments du tableau.

L'alternance (|) correspond à l'une ou l'autre branche : jg 'name | roommates' retourne les deux champs.

La descente récursive utilise * et [*] à l'intérieur d'une étoile de Kleene pour parcourir arbitrairement en profondeur : jg '(* | [*])*.name' trouve chaque champ name à n'importe quelle profondeur. Le drapeau -F fournit un raccourci : jg -F name fait la même chose.

L'optionnel (?) correspond à zéro ou une occurrence : jg 'roommates[0].favorite_food?' retourne à la fois l'objet parent et la valeur du champ.

Approche technique

jsongrep compile les requêtes en automates finis déterministes (DFA) en utilisant un pipeline qui inclut : l'analyse de la requête, le traitement du JSON comme un arbre, la construction d'un NFA avec l'algorithme de Glushkov, la déterminisation via la construction par sous-ensembles, et la recherche en utilisant DFS avec transitions DFA. Cela permet un traitement en une seule passe avec un travail O(1) par symbole d'entrée, évitant le retour en arrière, les piles de récursion et l'explosion exponentielle sur les requêtes pathologiques.

L'auteur note que cela diffère fondamentalement des outils comme jq, jmespath, ou jsonpath-rust, qui interprètent les expressions de chemin, évaluent les requêtes à chaque nœud, vérifient les prédicats et descendent récursivement—potentiellement revisitant des sous-arbres ou maintenant des listes de travail avec des requêtes de descente récursive.

Installation et disponibilité

Installez depuis crates.io : cargo install jsongrep. Comme ripgrep (qui a inspiré le projet), jsongrep est multiplateforme avec des binaires disponibles et écrit en Rust.

L'outil détecte si la sortie est redirigée vers des commandes comme less ou sort et omet les chemins JSON par défaut (remplacez avec l'option --with-path).