jsongrep: инструмент для запросов к JSON на основе DFA, превосходящий jq в тестах производительности

Что делает 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 делает то же самое.

Опциональный элемент (?) соответствует нулю или одному вхождению: jg 'roommates[0].favorite_food?' возвращает как родительский объект, так и значение поля.

Технический подход

jsongrep компилирует запросы в детерминированные конечные автоматы (ДКА) с использованием конвейера, который включает: разбор запроса, рассмотрение JSON как дерева, построение НКА с помощью алгоритма Глушкова, детерминизацию через построение подмножеств и поиск с использованием DFS с переходами ДКА. Это позволяет обрабатывать данные за один проход с O(1) работой на каждый входной символ, избегая возвратов, рекурсивных стеков и экспоненциального взрыва на проблемных запросах.

Автор отмечает, что это фундаментально отличается от таких инструментов, как jq, jmespath или jsonpath-rust, которые интерпретируют выражения путей, вычисляют запросы в каждом узле, проверяют предикаты и рекурсивно спускаются — потенциально повторно посещая поддеревья или поддерживая списки задач с рекурсивными запросами спуска.

Установка и доступность

Установите из crates.io: cargo install jsongrep. Как и ripgrep (который вдохновил проект), jsongrep является кроссплатформенным, с доступными бинарными файлами и написан на Rust.

Инструмент определяет, направлен ли вывод в команды типа less или sort, и по умолчанию опускает пути JSON (можно переопределить с помощью опции --with-path).