jsongrep: A DFA-Based JSON Query Tool That Outperforms jq in Benchmarks

What jsongrep Does

jsongrep (jg binary) takes a query and a JSON input and prints every value whose path through the document matches the query. It treats JSON documents as trees where objects and arrays branch, scalars are leaves, and keys and indices label the edges. The query language is a regular language over the alphabet of keys and indices.

Query Language Features

Dot paths select nested fields by name: jg 'roommates[0].name' returns roommates.[0].name: "Alice".

Wildcards match any single key (*) or any array index ([*]): jg 'favorite_drinks[*]' returns all array elements.

Alternation (|) matches either branch: jg 'name | roommates' returns both fields.

Recursive descent uses * and [*] inside a Kleene star to walk arbitrarily deep: jg '(* | [*])*.name' finds every name field at any depth. The -F flag provides shorthand: jg -F name does the same.

Optional (?) matches zero or one occurrence: jg 'roommates[0].favorite_food?' returns both the parent object and the field value.

Technical Approach

jsongrep compiles queries into deterministic finite automata (DFA) using a pipeline that includes: parsing the query, treating JSON as a tree, constructing an NFA using Glushkov's algorithm, determinizing via subset construction, and searching using DFS with DFA transitions. This allows processing in a single pass with O(1) work per input symbol, avoiding backtracking, recursion stacks, and exponential blowup on pathological queries.

The author notes this differs fundamentally from tools like jq, jmespath, or jsonpath-rust, which interpret path expressions, evaluate queries at each node, check predicates, and recursively descend—potentially revisiting subtrees or maintaining worklists with recursive descent queries.

Installation and Availability

Install from crates.io: cargo install jsongrep. Like ripgrep (which inspired the project), jsongrep is cross-platform with binaries available and written in Rust.

The tool detects if output is piped to commands like less or sort and omits JSON paths by default (override with --with-path option).