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'는 모든 깊이의 모든 이름 필드를 찾습니다. -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 옵션으로 재정의 가능).