jsongrep: Ein DFA-basiertes JSON-Abfragewerkzeug, das jq in Benchmarks übertrifft

Was jsongrep tut

jsongrep (jg-Binary) nimmt eine Abfrage und eine JSON-Eingabe und gibt jeden Wert aus, dessen Pfad durch das Dokument der Abfrage entspricht. Es behandelt JSON-Dokumente als Bäume, in denen Objekte und Arrays verzweigen, Skalare Blätter sind und Schlüssel sowie Indizes die Kanten beschriften. Die Abfragesprache ist eine reguläre Sprache über dem Alphabet von Schlüsseln und Indizes.

Merkmale der Abfragesprache

Punktpfade wählen verschachtelte Felder nach Namen aus: jg 'roommates[0].name' gibt roommates.[0].name: "Alice" zurück.

Wildcards passen auf jeden einzelnen Schlüssel (*) oder jeden Array-Index ([*]): jg 'favorite_drinks[*]' gibt alle Array-Elemente zurück.

Alternation (|) passt auf einen von zwei Zweigen: jg 'name | roommates' gibt beide Felder zurück.

Rekursiver Abstieg verwendet * und [*] innerhalb eines Kleene-Sterns, um beliebig tief zu gehen: jg '(* | [*])*.name' findet jedes Namensfeld in beliebiger Tiefe. Das Flag -F bietet eine Kurzform: jg -F name tut dasselbe.

Optional (?) passt auf null oder ein Vorkommen: jg 'roommates[0].favorite_food?' gibt sowohl das Elternobjekt als auch den Feldwert zurück.

Technischer Ansatz

jsongrep kompiliert Abfragen in deterministische endliche Automaten (DFA) mithilfe einer Pipeline, die umfasst: Parsen der Abfrage, Behandeln von JSON als Baum, Konstruieren eines NFA mit Glushkovs Algorithmus, Determinierung durch Subset-Konstruktion und Suche mit DFS und DFA-Übergängen. Dies ermöglicht die Verarbeitung in einem einzigen Durchlauf mit O(1)-Arbeit pro Eingabesymbol, wodurch Backtracking, Rekursionsstapel und exponentielles Anwachsen bei pathologischen Abfragen vermieden werden.

Der Autor weist darauf hin, dass sich dies grundlegend von Tools wie jq, jmespath oder jsonpath-rust unterscheidet, die Pfadausdrücke interpretieren, Abfragen an jedem Knoten auswerten, Prädikate prüfen und rekursiv absteigen – wobei möglicherweise Teilbäume erneut besucht oder Arbeitslisten mit rekursiven Abstiegsabfragen verwaltet werden.

Installation und Verfügbarkeit

Installation von crates.io: cargo install jsongrep. Wie ripgrep (das das Projekt inspiriert hat) ist jsongrep plattformübergreifend mit verfügbaren Binärdateien und in Rust geschrieben.

Das Tool erkennt, ob die Ausgabe an Befehle wie less oder sort weitergeleitet wird, und lässt JSON-Pfade standardmäßig weg (überschreibbar mit der Option --with-path).