jsongrep: ベンチマークでjqを上回るDFAベースのJSONクエリツール

jsongrepの機能

jsongrep（jgバイナリ）は、クエリとJSON入力を取り、ドキュメント内のパスがクエリに一致するすべての値を出力します。JSONドキュメントを、オブジェクトと配列が分岐し、スカラー値が葉となり、キーとインデックスがエッジをラベル付けするツリーとして扱います。クエリ言語は、キーとインデックスのアルファベット上の正規言語です。

クエリ言語の機能

ドットパスは名前でネストされたフィールドを選択します：jg 'roommates[0].name'はroommates.[0].name: "Alice"を返します。

ワイルドカードは任意の単一キー（*）または任意の配列インデックス（[*]）に一致します：jg 'favorite_drinks[*]'はすべての配列要素を返します。

代替（|）はどちらかの分岐に一致します：jg 'name | roommates'は両方のフィールドを返します。

再帰的下降は、任意の深さを歩くためにクリーネ閉包内で*と[*]を使用します：jg '(* | [*])*.name'は任意の深さにあるすべてのnameフィールドを見つけます。-Fフラグは短縮形を提供します：jg -F nameは同じことを行います。

オプション（?）は0回または1回の出現に一致します：jg 'roommates[0].favorite_food?'は親オブジェクトとフィールド値の両方を返します。

技術的アプローチ

jsongrepは、クエリを決定性有限オートマトン（DFA）にコンパイルします。パイプラインには以下が含まれます：クエリの解析、JSONをツリーとして扱う、Glushkovのアルゴリズムを使用したNFAの構築、部分集合構成による決定化、DFA遷移を使用したDFSによる検索。これにより、入力シンボルごとにO(1)の作業で単一パスでの処理が可能になり、バックトラッキング、再帰スタック、および病的なクエリでの指数的爆発を回避します。

著者は、これがjq、jmespath、jsonpath-rustなどのツールとは根本的に異なると指摘しています。これらのツールはパス式を解釈し、各ノードでクエリを評価し、述語をチェックし、再帰的に下降します。これにより、サブツリーの再訪問や再帰的下降クエリでのワークリストの維持が発生する可能性があります。

インストールと利用可能性

crates.ioからインストール：cargo install jsongrep。このプロジェクトにインスピレーションを与えたripgrepと同様に、jsongrepはクロスプラットフォームでバイナリが利用可能であり、Rustで書かれています。

このツールは、出力がlessやsortなどのコマンドにパイプされているかどうかを検出し、デフォルトではJSONパスを省略します（--with-pathオプションで上書き可能）。