jsongrep, plus rapide que jq

• Outil CLI Rust pour parcourir des documents JSON par chemin, avec une vitesse de recherche supérieure à celle de jq, jmespath, jsonpath-rust et jql
• Les requêtes sont exprimées comme un langage régulier et compilées en DFA, puis l’arbre JSON est parcouru en un seul passage, pour un traitement en temps O(n)
• S’appuie sur serde_json_borrow, qui prend en charge le parsing zero-copy, afin de minimiser les allocations mémoire, et a été conçu en s’inspirant de la philosophie de performance de ripgrep
• Selon les benchmarks, il offre les meilleures performances end-to-end, y compris sur de gros JSON, avec un langage de requête simple centré sur la recherche
• Publié sous licence MIT, avec un moteur de requête basé sur DFA réutilisable comme bibliothèque Rust

---

Présentation de jsongrep

• jsongrep est un outil CLI en Rust qui recherche des valeurs dans des documents JSON à partir de chemins, avec l’objectif d’être plus rapide que jq, jmespath, jsonpath-rust et jql
• Il considère un document JSON comme un arbre, exprime les chemins (path) comme un langage régulier (regular language), les compile en DFA (Deterministic Finite Automaton), puis effectue l’exploration en un seul passage
• Le langage de requête est simple, conçu autour de la recherche, sans fonctions de transformation ni de calcul
• Le parsing zero-copy via serde_json_borrow minimise les allocations mémoire
• Son développement s’inspire de la philosophie de conception et de l’approche performance de ripgrep

Exemples d’utilisation de jsongrep

• La commande jg prend une requête et une entrée JSON, puis affiche toutes les valeurs dont le chemin correspond à la requête
• Accès aux champs imbriqués avec la notation par points (dot path)
  • jg 'roommates[0].name' → "Alice"
• Les wildcards (*, [*]) permettent de faire correspondre toutes les clés ou tous les index
• L’alternation (|) permet de choisir l’un de plusieurs chemins
• La recherche récursive ((* | [*])*) permet de trouver des champs à profondeur arbitraire
• L’optional (?) permet une correspondance en 0 ou 1 occurrence
• L’option -F permet de rechercher rapidement un nom de champ spécifique
• Lors de l’utilisation de pipes (| less, | sort), l’affichage du chemin est automatiquement omis ; on peut forcer son affichage avec --with-path

Concepts clés de jsongrep

• Un JSON est une structure arborescente, où les clés d’objet et les index de tableau jouent le rôle d’arêtes (edges)
• Une requête définit un ensemble de chemins entre la racine et certains nœuds
• Le langage de requête est conçu comme un langage régulier, ce qui permet sa conversion en DFA
• Le DFA ne lit l’entrée qu’une seule fois et explore en temps O(n), sans backtracking
• Les outils existants (jq, jmespath, etc.) interprètent les requêtes et explorent récursivement, tandis que jsongrep s’appuie sur un DFA précompilé pour une exploration en un seul passage

Architecture du moteur de requête basé sur DFA

• Le pipeline se compose de 5 étapes
  1. Parsing du JSON en arbre avec serde_json_borrow
  2. Parsing de la requête en AST
  3. Construction d’un NFA avec l’algorithme de Glushkov
  4. Conversion en DFA par Subset Construction
  5. Exploration de l’arbre JSON en un seul DFS en suivant les transitions du DFA

• Parsing des requêtes

  • Une grammaire PEG (avec la bibliothèque pest) convertit la requête en AST Query
  • Principaux éléments syntaxiques : Field, Index, Range, FieldWildcard, ArrayWildcard, Optional, KleeneStar, Disjunction, Sequence
  • Exemple : roommates[*].name → Sequence(Field("roommates"), ArrayWildcard, Field("name"))

• Modèle d’arbre JSON

  • Les clés d’objet et les index de tableau sont des arêtes, les valeurs sont des nœuds
  • Exemple : roommates[*].name parcourt le chemin roommates → [0] → name

• Construction du NFA (algorithme de Glushkov)

  • Génère un NFA sans transition ε
  • Étapes
    1. Attribution d’un numéro de position aux symboles de la requête
    2. Calcul des ensembles First/Last/Follows
    3. Construction des transitions entre positions
  • Pour la requête roommates[*].name, le NFA obtenu est une structure linéaire simple de 4 états

• Conversion en DFA (Subset Construction)

  • Génère un DFA déterministe à partir d’ensembles d’états du NFA
  • Chaque état correspond à un ensemble d’états du NFA
  • Ajoute un symbole Other pour ignorer efficacement les clés non pertinentes
  • Pour les requêtes simples, on obtient un DFA de structure identique à celle du NFA

• Exploration basée sur DFS

  • En partant de la racine, les transitions du DFA sont suivies le long de chaque arête
  • S’il n’y a pas de transition, le sous-arbre correspondant est élagué (prune)
  • Quand l’état du DFA est accepting, le chemin et la valeur sont enregistrés
  • Chaque nœud est visité au plus une fois, donc l’exploration complète reste en O(n)
  • serde_json_borrow permet de référencer le buffer d’origine sans recopier les chaînes

Méthodologie des benchmarks

• Benchmarks statistiques réalisés avec Criterion.rs

• Jeux de données

  • simple.json (106B), kubernetes-definitions.json (~992KB), kestra-0.19.0.json (~7.6MB), citylots.json (~190MB)

• Outils comparés

  • jsongrep, jsonpath-rust, jmespath, jaq, jql

• Groupes de benchmarks

  1. document_parse : vitesse de parsing JSON
  2. query_compile : temps de compilation des requêtes
  3. query_search : recherche seule
  4. end_to_end : pipeline complet

• Considérations d’équité

  • L’avantage du parsing zero-copy est mesuré séparément
  • Le coût de compilation du DFA est mesuré à part
  • Les outils sans fonctionnalité correspondante sont exclus des tests concernés
  • Le coût de duplication des données est traité séparément

Résultats des benchmarks

• Temps de parsing du document : serde_json_borrow est le plus rapide
• Temps de compilation des requêtes : jsongrep a le coût le plus élevé en raison de la génération du DFA ; jmespath est bien plus rapide
• Temps de recherche : jsongrep est le plus rapide de tous les outils comparés
• Performances end-to-end : même sur le jeu de données de 190MB, il est nettement plus rapide que jq, jmespath, jsonpath-rust et jql
• Tous les résultats sont disponibles sur le site de benchmark en direct

Licence et usages

• Logiciel open source sous licence MIT
• Disponible sur GitHub, Crates.io et Docs.rs
• Le moteur de requête basé sur DFA est réutilisable sous forme de bibliothèque, directement intégrable dans des projets Rust

Références

• Glushkov, V. M. (1961), The Abstract Theory of Automata
• Rabin, M. O., & Scott, D. (1959), Finite Automata and Their Decision Problems