jqjq

jq implementation of jq

Why? It started when researching how to write decoders in jq for fq which ended up involving some AST rewriting and walking and then it escalated a bit.

It's also a great way to show that jq is a very expressive, capable and neat language!

There is a jqplay snippet with jqjq if you want to play around.

Use via jqjq wrapper

$ ./jqjq -n 'def f: 1,8; [f,f] | map(.+105) | implode'
"jqjq"

$ ./jqjq '.+. | map(.+105) | implode' <<< '[1,8]'
"jqjq"

# eval example above using jqjq in jqjq. will take some time.
# eval the concatenation of jqjq.jq as a string and the example
$ ./jqjq "eval($(jq -Rs . jqjq.jq)+.)" <<< '"eval(\"def f: 1,8; [f,f] | map(.+105) | implode\")"'
"jqjq"

# jqjq has a REPL
$ ./jqjq --repl
> 1,2,3 | .*2
2
4
6
> "jqjq" | explode | map(.-32) | implode
"JQJQ"
> "jqjq" | [eval("explode[] | .-32")] | implode
"JQJQ"
> ^D

# run 01mf02's adaptation of itchyny's bf.jq running fib.bf
$ ./jqjq -n "\"$(cat fib.bf)\" | $(cat bf.jq)"
"1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233"

Use with jq

$ jq -n -L . 'include "jqjq"; eval("def f: 1,8; [f,f] | map(.+105) | implode")'
"jqjq"

$ jq -L . 'include "jqjq"; eval("(.+.) | map(.+105) | implode")' <<< '[1,8]'
"jqjq"

# can be used as path expression (only gojq for now because of jq issue)
$ gojq -cn -L . 'include "jqjq"; {a:0, b:1} | eval(".a, .b") += 1'
{"a":1,"b":2}

Run tests

make test

Note that the tests are meant to be used with jq 1.7.1.

Progress

• 123, .123, 1.23, 1.23e2, 1.23e+2, "abc", true, false, null Scalar literals
  • Unicode codepoint escape "\ud83d\ude03"
  • Handle surrogate pairs \ud800-\udfff, should translate to codepoint.
  • Control code and quote escape "\"\n\r\t\f\b\\\/"
• "abc \(123)" String interpolation
• {key: "value"} Object literal
  • {key}
  • {"key"}
  • {$key}
  • {(f): f}
  • {("a","b"): (1,2), c: 2} Multiple key/value outputs
  • {"\("abc")": 123} Key string interpolation
  • {key: 1 | .} Multi value queries
• [1,2,3] Array literal, collect
• 1, 2 Comma operator
• 1 | 2 Pipe operator
• +, -, *, /, % Arithmetic operators
• +123, -1 Unary operators
• ==, !=, <, <=, >, >= Comparison operators
• 123 as $a | ... Binding
  • (1,2,3) as $a | ... Binding per output
  • {a: [123]} as {a: [$v]} Destructuring binding
• . Identity
• .a, ."a", .[1], .[f] Index
• .key[123]."key"[f] Suffix expressions
  • .a.b Multi index
  • .a.b? Optional index
  • .a[] Iterate index
  • .[]? Try iterate
• .[] Iterate
• .[start:stop], .[:stop], .[start:] Array slicing
  • .[{start: 123, stop: 123}] Slice using object
  • Slice and path tracking path(.[1:2]) -> [{"start":1,"end":2}]
• try f, Shorthand for try f catch empty
• f? Shorthand for try f catch empty
• and, or operators
• not operator
• if f then 2 else 3 end Conditional
  • if f then 2 end Optional else
  • if f then 2 elif f then 3 end Else if clauses
  • if true,false then "a" else "b" end Multiple condition outputs
• reduce f as $a (init; update) Reduce outputs from f into one output
• foreach f as $a (init; update; extract) Foreach outputs of f update state and output extracted value
  • Optional extract
• f = v Assignment
• f |= v, f += Update assignment
• +=, -=, *=, /=, %= Arithmetic update assignment
• eval($expr) (jqjq specific)
• path(f) Output paths for f
• input, inputs
• Builtins / standard library
  • add
  • all, all(cond), all(gen; cond)
  • any, any(cond), any(gen; cond)
  • bsearch($target)
  • capture($val), capture(re; mods)
  • debug (passthrough)
  • debug(msgs)
  • del(f)
  • delpaths($paths) (passthrough)
  • empty (passthrough)
  • endswith($s)
  • env
  • error($v) (passthrough)
  • error (passthrough)
  • explode (passthrough)
  • first(f)
  • first
  • flatten, flatten($depth)
  • from_entries
  • fromjson
  • getpath(path) (passthrough)
  • group, group_by(f)
  • gsub($regex; f) (passthrough)
  • gsub($regex; f; $flags) (passthrough)
  • halt_error, halt_error($exit_code)
  • has($key) (passthrough)
  • implode (passthrough)
  • in(xs)
  • index($i)
  • indices($i)
  • isempty
  • join($s)
  • last(f)
  • last
  • length (passthrough)
  • limit($n; f)
  • map(f)
  • match($regex; $flags) (passthrough)
  • match($val)
  • max, max_by(f)
  • min, min_by(f)
  • nth($n; f); nth($n)
  • paths
  • range($to), range($from; $to), range($from; $to; $by)
  • recurse, recurse(f)
  • repeat
  • reverse
  • rindex($i)
  • scalars
  • select(f)
  • setpath (passthrough)
  • sort, sort_by(f)
  • split($s)
  • split($re; flags)
  • splits($re), splits($re; flags)
  • startswith($s)
  • test($val)
  • test($regex; $flags) (passthrough)
  • to_entries
  • tojson
  • tonumber (passthrough)
  • tostring (passthrough)
  • transpose
  • type (passthrough)
  • unique, unique_by(f)
  • until(cond; next)
  • while(cond; update)
  • with_entries
  • Math functions, sin/0, ... atan/2, ...
  • More...
• def f: . Function declaration
  • def f(lambda): lambda Lambda argument
  • (def f: 123; f) | . Closure function
  • def f: def _f: 123; _f; f Local function
  • def f($binding): $binding Binding arguments
  • def f: f; Recursion
• .. Recurse input, same as recurse
• // Alternative operator
• ?// Alternative destructuring operator
• $ENV
• @format "abc \(.)" Format string
  • @base32
  • @base64
  • @csv
  • @html
  • @sh
  • @tsv
  • @uri
  • @json
  • @text
• label $out | break $out Break out
• include "f", import "f" Include
• CLI options
  • --help / -h
  • --null-input / -n
  • --raw-input / -R
  • --slurp / -s
  • --compact-output / -c
  • --raw-output / -r
  • --raw-output0
  • --join-output / -j
  • --color-output / -C
  • --monochrome-output / -M
  • --tab
  • --indent n
  • --unbuffered
  • --from-file / -f
  • -L directory
  • --arg name value
  • --argjson name text
  • --rawfile name filename
  • --slurpfile name filename
  • --args
  • --jsonargs
  • --run-tests
  • --run-tests [filename]
  • --
  • More...
  • Non-standard CLI options
    • --jq
    • --lex
    • --parse
    • --repl
    • --no-builtins
• Host jq
  • jq
  • gojq
  • jqjq
    • Used to work but runs out of memory on my laptop
  • jaq
    • Fails on missing destructing support
  • xq
    • Fails on missing debug, maths, jqjq lex returns empty (regexp issues?)
• Bugs

jq's test suite

$ ./jqjq --run-tests < ../jq/tests/jq.test | grep passed
312 of 469 tests passed

Note that expected test values are based on stedolan's jq. If you run with a different jq implementation like gojq some tests might fail because of different error messages, support for arbitrary precision integers etc.

Design overview

jqjq has the common lex, parse, eval design.

Lex

Lexer gets a string and chews off parts from left to right producing an array of tokens [{<name>: ...}, ...]. Each chew is done by testing regex:s in a priority order to make sure to match longer prefixes first, ex: += is matched before +. For a match a lambda is evaluated, usually {<token-name>: .}, but in some cases like for quoted strings it is a bit more complicated.

The lexer also has a stack to keep track of balance of seen (, ) and \( to properly know how to chop of a string with interpolation into tokens. e.g. is ) a right parenthesis or continuation of a string as in "abc \(123) def"?

You can use ./jqjq --lex '...' to lex and see the tokens.

Parse

Parser takes an array of tokens and uses a left-to-right (LR) parser with backtracking in combination with precedence climbing for infix operators to not end up in an infinite loop (ex parser rule E -> E + E). Backtracking is done by outputting empty for non-match and // to try the next rule, ex: a // b // ... // error where a and b are functions that try to match a rule. When a rule has matched it returns an array with the pair [<tokens left>, <ast>]. <ast> uses the same AST design as gojq.

You can use ./jqjq --parse '...' to lex and parse and see the AST tree.

Eval

Eval is done by traversing the AST tree and evaluates each AST node and also keeps track of the current path and environment.

Path is used in jq to keep track of current path to where you are in the input. The tracking can be done as long as you only operate on the input and don't create and output new values. I.e path(.a[1]), .b outputs ["a",1] and ["b"]. This is also used to implement assignment and some other operators.

Environment is an object with current functions and bindings. Functions have the key name <name>/<arity> and the value is a function AST. Bindings use the key name $<name>/0 and the value is {value: <value>} where value is normal jq value.

When evaluating the AST eval function get the current AST node, path and environment and will output zero, one or more arrays with the pair [<path>, <value>]. Path can be [null] if the evaluation produced a "new" value etc so that path tracking is not possible.

Problems, TODOs, issues and unknowns

• Better error messages.
• The "environment" pass around is not very efficient and also it makes support recursion a bit awkward (called function is injected in the env at call time).
• "," operator in jq (and gojq) is left associate but for the way jqjq parses it creates the correct parse tree when it's right associate. Don't know why.
• Suffix with multiple [] outputs values in wrong order.
• String literal using interpolation that has more than one generator outputs in wrong order. Ex: "\(1,2) \(3,4)".
• Non-associative operators like == should fail, ex: 1 == 2 == 3.
• Objects are parsed differently compared to gojq. gojq has a list of pipe queries, jqjq will only have one that might be pipe op.
• Less "passthrough" piggyback on jq features:
  • reduce/foreach via recursive function? similar to if or {}-literal?
  • try/catch via some backtrack return value? change [path, value] to include an error somehow?
• How to support label/break?
• How to support delpaths (usd by del etc). Have to keep paths the same while deleting a group of paths? use sentinel value? work with paths instead?
• Rewrite AST before eval, currently if and some others do rewrite (optional parts etc) while evaluating.
• Rethink invalid path handling, current [null] is used as sentinel value.
• {a:123} | .a |= empty should remove the key.
• Lookup ident and bindings during parse, ex def f(no_used): 123; f(does_not_exist) and def f: $does_not_exist, does_not_exist; 123 should fail.
• Add a AST re-write stage between parse and eval? some rewrite done during eval can probably happen before
• Test arguments, env, $ENV/$ARGS somehow? extend the test format?
• Refactor to share more between filter mode and REPL (globals etc)
• Move lookup of env, args etc to builtin_undefined_func

Useful references

• jq - Command-line JSON processor
• jq's builtin.jq
• jq Language Description
• jq simplified grammar
• gojq - Pure Go implementation of jq
• jaq - A jq clone focused on correctness, speed, and simplicity
• xq - Pure rust implementation of jq
• wsjq - Whitespace interpreter in jq, which can run with jqjq
• jq wiki: jq as a PEG engine by pkoppstein
• Precedence climbing

Tools and tricks

• jq -n --debug-dump-disasm '...' show jq byte code
• jq -n --debug-trace=all '...' show jq byte code run trace
• jq -n '{a: "hello"} | debug' 2> >(jq -R 'gsub("\u001b\\[.*?m";"") | fromjson' >&2) pretty print debug messages
• GOJQ_DEBUG=1 go run -tags gojq_debug cmd/gojq/main.go -n '...' run gojq in debug mode
• fq -n '".a.b" | _query_fromstring' gojq parse tree for string
• fq -n '{...} | _query_tostring' jq expression string for gojq parse tree
• For a convenient jq development experience:
  • jq-dash-docset
  • vscode-jq
  • jq-lsp

Thanks to

• stedolan for jq and got me interested in generator/backtracking based languages.
• pkoppstein for writing about jq and PEG parsing.
• itchyny for jqjq fixes and gojq from which i learned a lot and is also from where most of jqjq's AST design comes from. Sharing AST design made it easier to compare parser output (ex via fq's _query_fromstring). gojq also fixes some confusing jq bugs and has better error messages which saves a lot of time.
• Michael Färber @01mf02 for jaq and where I also learned about precedence climbing.
• Thalia Archibald @thaliaarchi for correctness fixes, builtins, more CLI arguments, fancy and colorful output and more.

License

Copyright (c) 2022 Mattias Wadman

jqjq is distributed under the terms of the MIT License.

See the LICENSE file for license details.