jqはとても便利なコマンドです。
JSONを返すAPIを実装するときや、SaaSのAPIから特定の情報を抜き出してシェル変数に代入するときなど、web開発や運用には欠かせないツールとなっています。
しかし、私にとってjqのクエリを一発で書くのは容易ではなく、思い通りの出力が得られないことがよくありました。
難しいエラーメッセージに悩まされて、jqで書くのを諦めて別の言語で書き直すこともありました。
jqの十八番と思える場面で使いこなせないのは、なかなか悔しいものがあります。
ツールを使うのが難しいなら、同じものを作ってしまえばよいのです。
- jqの全ての機能を実装する
- jqを言語としてきちんと書けるようになる
- jqを完全に理解する
jqの全ての機能を自分で実装してしまえば、jqがどういうものか、クエリがどのように処理されるのか、詳しくなれるはずです。
jqを得意な言語と言えるようになって、クエリを自由自在に書けるようになるはず。
そう考えた私は、Go言語でjqを実装することにしました。
すでにjqの大部分の機能は実装し終わり、わりと満足しています。
おそらくjqの機能をここまでカバーした別実装は他にはないと思います。
jqのかなり深いところまで理解できましたし、ビルトイン関数も全て頭に入ったので、リファレンスを見なくても複雑なクエリをすばやく書けるようになりました。
しかし、gojqを実装する過程では、処理系の設計ミスによる書き直しやjqならではのスタックの難しさなど、様々な困難がありました。
jqの言語としての特徴を説明した上で、gojqの実装過程で学んだことについて説明していきたいと思います。
jqの特徴
多くの人は、JSONを絞り込むツールとしてjqを使っていると思います *1。
% echo '{"foo":{"bar":42}}' | jq '.foo.bar'
42
% echo '[{"id":1,"name":"alice"}, {"id":2,"name":"bob"}, {"id":3,"name":"charlie"}]' \
| jq -r '.[] | select(.id == 2) | .name'
bob
jqはJSONを絞り込むだけではなく、JSONのイテレータを出力することもできます。
% jq -n '1, 2, [3], {"foo":4}'
1
2
[
3
]
{
"foo": 4
}
% echo '{"foo":[1,2,3]}' | jq '.foo[]'
1
2
3
% echo '{"foo":[1,2,3]}' | jq -c '..'
{"foo":[1,2,3]}
[1,2,3]
1
2
3
いきなり出力がたくさんのJSONになって手に負えなくなる、そういう経験はないでしょうか。
そうなった場合は、いかなるときでも [ ] で囲うことで配列に戻すことができます。
% echo '{"foo":[1,2,3]}' | jq -c '[..]'
[{"foo":[1,2,3]},[1,2,3],1,2,3]
% echo '{"foo":[1,2,3]}' | jq -c '[.foo[]]'
[1,2,3]
実は、jqには配列そのものの構文はありません。
[1,2,3] は配列に見えますが、これは 1,2,3 というイテレータに、[ ] という配列構築子を適用させているに過ぎません *2。
% jq -n '1,2,3'
1
2
3
% jq -n -c '[1,2,3]'
[1,2,3]
% echo '{"foo":[1,2,3]}' | jq -c '[.foo[], 4, 5]'
[1,2,3,4,5]
jqは、JSONのイテレータを扱う言語です。
jqのクエリのあらゆるもの、null、false、true、{}、1,2,3、(1, 2) * (3, 4) など、全てJSONのイテレータとして捉える事ができます。
"hello, world" のように一つの文字列を返すイテレータもあれば、empty のように何も返さないイテレータ、def f: 1, f; f のように無限に 1 を返すイテレータなど、様々なものがあります。
% jq -n '(1, 2) * (3, 4)'
3
6
4
8
% jq -n -c '[range(1;5) * range(1;5)]'
[1,2,3,4,2,4,6,8,3,6,9,12,4,8,12,16]
% jq -n -c 'def f: 1, f; [limit(10; f)]'
[1,1,1,1,1,1,1,1,1,1]
% jq -n -c '[[0,1] | while(.[0]<100; [.[1], .[0]+.[1]]) | .[0]]'
[0,1,1,2,3,5,8,13,21,34,55,89]
(1, 2) * (3, 4) が 3, 6, 4, 8 になる、こんなに面白い言語は他にあるでしょうか。
jqで最も大事な演算子は何でしょうか。
それは , (コンマ演算子) です。
jqを理解すること、それはすなわちコンマ演算子を理解することであり、それが生み出すイテレータがどのように評価されていくかを理解することです。
JSONのイテレータを処理する言語であるという認識がないと、jqのコードを書くことはできません。
イテレータの話は少し置いておいて、関数の話をしておこうと思います。
これまでも例に出していますが、jqでは関数を定義できます。
% echo '[1,2]' | jq 'def f(a; b): a * 10 + b; f(.[]; .[])'
11
21
12
22
% jq -n -c 'def f($n): if $n == 0 then empty else $n, f($n - 1) end; [f(10)]'
[10,9,8,7,6,5,4,3,2,1]
クエリには、常に入力があることに気をつけてください。
n倍するという関数は、次のように書けます。
% echo '1 2 3' | jq 'def ntimes($n): . * $n; ntimes(3)'
3
6
9
平均値を取る関数は、次のように書けます。
% echo '[1, 3, 6]' | jq 'def mean: add / length; mean'
3.3333333333333335
引数をとらないように見える関数でも、常に入力があることを意識する必要があります *3。
たかがJSONを処理するだけのツールなのに関数定義なんて必要なのか、そのように思われるかもしれません。
しかし、map や select という絞り込みの必需品たちは、jqの関数として実装されています。
def map(f): [.[] | f];
def select(f): if f then . else empty end;
keys や tostring のようにC言語で実装されている関数もありますが、map や select、first、all、map_values、subなど、多くのビルトイン関数がjqで実装されています (参考)。
.. というすべての要素を辿って出力するフィルターさえ、次のように定義されるrecurse関数へのエイリアスとなっています。
def recurse: recurse(.[]?);
def recurse(f): def r: ., (f | r); r;
多くのビルトイン関数がjqで実装されているという事実は大切なことです。
C言語で書く関数や構文をできるだけ限定し、メモリーリークなどのCで書くことに起因するバグを減らすのみならず、ビルトイン関数自体が処理系のテストケースとなっています。
jq .. と書いただけでも、上記のrecurse関数のコンパイル、関数内の関数定義、引数 f の処理、 .[]? の処理など、様々なことが処理系の中で起きているのです。
jqクエリの処理系を作ること、それはjqのビルトイン関数がきちんと動く処理系を実装することでもあるのです。
そして、jqで書かれたビルトイン関数のパフォーマンスを改善することが、すなわち言語処理系としてのパフォーマンスを改善することにつながるのです。
channelによる実装と挫折
3月にjoのGo実装を作ってまもなく、jqをGoに移植したいという気持ちが高まっていました。
網羅的にjqの機能を知りたい、プログラミング言語としてきちんとjqのコードを書けるようになりたい、そのためには自分で処理系を作らずにはいられないと思い至ったのです。
jqがJSONのイテレータを扱う言語であるという淡い認識ができた頃、Goのchannelで実装できるのではないかと考えるようになりました。
JSONをデコードしたものは絶対にchannelにならないので、channelを使えばJSONとイテレータを区別できます。
言語の処理系を、全く別の言語の機能を用いて作るというのは興味深いことだと思いませんか *4。
Go言語の特徴の一つであるchannelを用いたインタープリタが、jqのテストケースを全てパスしたら面白いに違いない。
どうせ実用上はそこまでパフォーマンスは求められないだろうし、Go言語で書いたらそこまで酷い速度にはならないだろう。
そう考えた私は、構文木を直接評価する形の素朴なインタープリタを実装していきました *5。
"hello, world" は文字列を一つ返すイテレータといいましたが、何らかの値をイテレータに変換するには次のような関数を用いて変換できます。
func unitIterator(v interface{}) <-chan interface{} {
c := make(chan interface{}, 1)
defer func() {
defer close(c)
c <- v
}()
return c
}
配列構築子は、中のクエリを全て消費して一つの配列を返します (エラーハンドリングは省略しています)。
func (env *env) applyArray(x *Array, c <-chan interface{}) <-chan interface{} {
a := []interface{}{}
for v := range env.applyQuery(x.Query, c) {
a = append(a, v)
}
return unitIterator(a)
}
for文でイテレートできるのは、channelを使ったイテレータの良いところだと思います。
二項演算子の評価は、両辺をイテレートして関数の評価結果をイテレータに流すといった具合です。
func binopIterator(l <-chan interface{}, r <-chan interface{}, fn func(l, r interface{}) interface{}) <-chan interface{} {
d := make(chan interface{}, 1)
go func() {
defer close(d)
ls := reuseIterator(l)
for r := range r {
for l := range ls() {
d <- fn(l, r)
}
}
}()
return d
}
左辺をイテレートするときに reuseIterator なるものを使っていることに注意してください。
例えば (1, 2) * (3, 4) では、初回のループで 3, 6、次のループで 4, 8 を出力するので、左辺のイテレータは何度もイテレートしないといけないのです。
このためには、左辺は何度も最初から消費し直せるようにしなければなりません。
reuseIterator を実装するのは楽しいので、読者への課題とします *6。
channelベースのイテレータを使った実装は、ある時点まではかなりうまく行っていました。
reduce や foreach というjq特有のシンタックスも実装できたときには満足していましたが、徐々にある問題が見えてきました。
パフォーマンスがあまりにもひどいのです。
jq -n 'range(10000)' は0.1秒もかかりませんが、gojqだと4分もかかってしまうのです。
なぜ数字を順番に出力するだけなのにこんなにかかるのかと思われるかもしれませんが、range関数は次のように定義されており、この関数を実行しないといけません。
def range($n): 0 | while(. < $n; . + 1);
def while(cond; update):
def _while: if cond then ., (update | _while) else empty end;
_while;
このwhile関数というのは面白い関数です。
jqにはループ構文がありませんが、再帰を使えばループを表現できます *7。
つまりjqが反復処理ができる言語であることの証左となっているわけです *8。
こんなにパフォーマンスが悪いのは、channelを使ったのが良くなかったのでしょうか。
イテレータはchannelを使わずとも次の値を返すメソッドを持つ構造体で実装できます。
全てのchannelをやめて構造体に実装を変更してみましたが、それでも40秒ほどまでしか縮まりませんでした *9。
4分と比較すればchannelを使うのをやめた分パフォーマンスは良くなっていますが、それでも0.1秒もかからない本家を思い出したら比べ物になりません。
gojqの実装を始めた当初、jqの全てがJSONのイテレータであるというセマンティクスは、Go言語のchannelによって直接表現できるに違いないという思いがありました。
それは概ね当たっており、jqの多くのテストケースをパスする処理系を作ることができました。
しかし、評価時にあらゆるものをchannelで扱うのは相当なオーバーヘッドがあることが明らかになってきました。
channelをやめることで数倍の速度改善が得られましたが、jqと比較したら何千倍も遅い処理系です。
実際のユースケースではこのような複雑なクエリは評価されないとは言え、特定のケースで何千倍も遅い後発のインタープリタはどう頑張っても魅力的には思えません。
構文木を直接たどって実行する評価器は大きなオーバーヘッドを伴います。
変数も実行時に名前で探さなくてはいけませんし、構文をたどるときに多くの分岐処理が必要になります。
構文が複雑になるほど、つまり構文木が深くなればなるほど、実行時のパフォーマンスは落ちていきます。
関数の実行処理も複雑になりますし、構文上のエラーを素早く返すこともできません。
このパフォーマンスの問題には、ずいぶん悩まされました *10。
何週間もかけて作った処理系のパフォーマンスがあまりに酷くて、参ってしまったのです。
また一から処理系部分を書き直すのか、それともgojqプロジェクトをここで諦めるのか。
せっかく積み上げてきたコードを捨てるのも忍びなく、かと言ってここまで作ってきた処理系を見放すのもできず、落ち込んで二週間ほどgojqのコードを触れない時期がありました。
スタックマシンによる実装
実行時に構文木をたどっていては、jqの速さには到底追いつけません。
そもそも追いつけないとかそういうレベルですらなく、range(10000)に何十秒もかかっているようではお話になりません。
やはりインタープリタの処理系は、構文木を実行時にたどっているようでは速度が出ないのです。
私はそれまでに書いてきた評価器を捨てて、スタックマシン方式のインタープリタに書き直す決心をしました。
仮想マシンの簡単な説明をしておきます。
例えば 1 * 2 + 3 * 4 を評価したいとしましょう。
スタックマシン方式のインタープリタでは、この式の構文木を次のような命令列に変換します。
0: push 1
1: push 2
2: call multiply
3: push 3
4: push 4
5: call multiply
6: call add
7: ret
実行時には、スタックを用意して命令を順番に解釈していきます。
[]
[ 1 ]
[ 1, 2 ]
[ 2 ]
[ 2, 3 ]
[ 2, 3, 4 ]
[ 2, 12 ]
[ 14 ]
[]
とてもシンプルな例ですが、全てのスタックマシン方式のインタープリタ言語はこの延長にあるものです。
Ruby (YARV) もPython (CPython) もJVMもWebAssemblyも、みんなスタックマシンを使っています *11。
仮想マシンの命令セットをどう設計するかが、そのインタープリタ言語を特徴づけています。
jqもスタックマシン方式のインタープリタ言語です。
他の言語と大きく違うのは、スタックの状態を保存して復帰できるということです。
例えば (1, 2) * (3, 4) を評価することを考えましょう。
まずjqが面白いのは、右辺を先に評価するということです *12。
そして、jqではカンマ演算子を fork という命令にコンパイルします *13。
0: fork 3
1: push 3
2: jump 4
3: push 4
4: fork 7
5: push 1
6: jump 8
7: push 2
8: call multiply
9: ret
この命令列を実行すると、次のようにスタックは変化します。
[]
[]
[ 3 ]
[ 3 ]
[ 3 ]
[ 3, 1 ]
[ 3, 1 ]
[ 3 ]
[]
[ 3 ]
[ 3, 2 ]
[ 6 ]
[]
[]
[ 4 ]
[ 4 ]
[ 4, 1 ]
[ 4, 1 ]
[ 4 ]
[]
[ 4 ]
[ 4, 2 ]
[ 8 ]
[]
[]
fork命令はオペランドに復帰時のプログラムカウンタ (pc) の位置を持っており、実行時にはスタックの状態と一緒に保存します。
この状態は値のスタックとは別のスタックにpushされます。
バイトコードのいちばん最後まで来たら、forkされた状態を復帰してpcをセットします。
復帰すべき状態がなくなったらプログラムを終了します。
コンマ演算子はfork命令にコンパイルされます。
この命令の実行時には、スタックの保存と復帰、pcの移動が行われます。
これによって、 (1, 2) * (3, 4) が 3, 6, 4, 8 となるという挙動を実装しているのです。
問題は、スタックの状態をどのように保存するかということです。
プログラムにもよりますが、スタックは長く伸びることがあります。
fork命令のたびにスタックを深くコピーしていては、良いパフォーマンスが出るようには思えません。
保存と復帰できるスタックは、片方向連結リスト (singly-linked list) によって実装できます。
スタック上に連結リストを構築し、先頭の index と、forkによって後で使われるかもしれない最大のindex (ここでは limit と呼ぶことにします) を持っておきます。
値をpushするときは、 index が limit よりも大きければ index + 1 に、そうでなければ limit + 1 に値を保存します。
fork時は、 limit を index に更新して、 index と limit の組をforkのスタックに保存します。
index と limit を戻すだけでスタックの状態は復帰します。
このスタックの実装はjqとgojqで少し異なるので、ぜひ見比べてみてください。
jqにおいて最も大事な演算子は , (コンマ演算子) であると述べたのを覚えているでしょうか。
この演算子は、そのまま fork命令にコンパイルされます。
この命令こそがjqの処理系の要であり、そしてjqをjqたらしてめているのです。
この演算子の実装を理解してようやくjqを理解したと言えるのだと思います。
gojqをスタックマシン方式のインタープリタに書き換えた結果、range(10000)の実行時間が0.2秒ほどになりました。
40秒から0.2秒ですから、200倍の改善、channelを使った実装と比べると1000倍の改善です。
jqが0.1秒程度ですから悪くありません。
rangeのパフォーマンス改善はすなわちwhile関数のチューニングであり、末尾再帰の最適化も必須でした。
このような最適化を行うのは私も初めてのことであり、とても勉強になりました。
ビルトイン関数の事前パース
jqは多くのビルトイン関数を持っています。
これらの関数は、jqがクエリを実行するときに必ずパースされています。
jq .foo のような簡単なクエリだとしても、必ず全てのビルトイン関数のパースが行われています。
gojqを作る前から、これは無駄ではないかという思いを持っていました。
jqの実際のユースケースを考えると、関数の九割九分は使われていないと思います。
jqのパーサーがいくらパフォーマンスがよくても、実行時に常にパースされるという性質があると、関数は増やさないでおこうという方向に動いてもおかしくありません。
便利な関数はどんどん増えてほしいものです。
gojqでは、コンパイル前にビルトイン関数をパースしてしまい、構文木をバイナリに埋め込むようにしています。
ここで問題になるのが、どのように構文木をバイナリに埋め込むかということです。
当初は構文木を何らかのデータフォーマットに変換して埋め込み、実行時にdecodeするという方式を考えていました。
しかしこれではjqに抱いていた問題をあまり解決できていません。
そしてあまり良さそうなフォーマットが見つかりませんでした。
gobはこういうことをするのには良いフォーマットだと思いますが、0 (数値) や空文字へのポインタをうまく扱えないので諦めました。
結局、ビルトイン関数の構文木をGo言語のソースコードとして出力し、コンパイルすることにしました。
そのためにastgenというライブラリを作って使っています。
package main
import (
"go/printer"
"go/token"
"os"
"github.com/itchyny/astgen-go"
)
type X struct {
X int
Y *Y
Z Z
}
type Y struct {
M string
}
type Z struct {
S string
I int
B bool
}
func main() {
x := &X{
Y: &Y{"hello"},
Z: Z{B: true},
}
n, err := astgen.Build(x)
if err != nil {
panic(err)
}
printer.Fprint(os.Stdout, token.NewFileSet(), n)
}
&X{Y: &Y{M: "hello"}, Z: Z{B: true}}
値へのポインタは次のように出力されます。
type X struct {
S *string
I *int
B *bool
}
func main() {
s := "hello"
i := 42
b := true
x := X{&s, &i, &b}
n, err := astgen.Build(x)
if err != nil {
panic(err)
}
printer.Fprint(os.Stdout, token.NewFileSet(), n)
}
(func(h string, x int, t bool) X {
return X{S: &h, I: &x, B: &t}
})("hello", 42, true)
関数やチャンネルはもちろん扱えませんが、gojqの構文木程度ならばかなりうまく扱えています (生成コードはこちらです)。
gobと異なり、組み込み型へのポインタやポインタへのポインタなどもうまく扱えます *14。
func main() {
s := "hello"
p := &s
pp := &p
for _, x := range []interface{}{s, p, pp, &pp} {
n, err := astgen.Build(x)
if err != nil {
panic(err)
}
printer.Fprint(os.Stdout, token.NewFileSet(), n)
fmt.Println()
}
}
"hello"
(func(h string) *string {
return &h
})("hello")
(func(h string) **string {
h1 := &h
return &h1
})("hello")
(func(h string) ***string {
h1 := &h
h11 := &h1
return &h11
})("hello")
go generateでコード生成を行うのは、Go言語ならではです。
コード生成はGoの楽しみの一つですね。
処理系を書き換えたことで、ビルトイン関数をコンパイルしたバイトコードをバイナリ埋め込んでしまうという最適化もありえます。
ただ、これは行き過ぎた最適化ではないかと感じており踏み切れていません。
構文木をコードで埋め込むくらいがいいバランスではないかと思っています。
jqを超えて次のステージへ
gojqは、jqの完全なクローンを目指しているわけではありません。
jqの良くない部分は修正し、より良いcliツールを目指していきたいと思っています。
jqの数字の実装は64bit浮動小数点数であり、任意精度整数をサポートしていません。
JSONを絞り込むだけのツールに任意精度の整数なんていらないでしょうと思われるかもしれませんが、17桁を超えるIDの数字や、ナノ秒の情報など、数字の精度が落ちては困る場面はたまによくあります *15。
gojqは任意精度の整数をサポートしています。
入力のJSONの中の整数の精度を保持するだけではなく、任意精度整数での演算をサポートしています。
% echo '{"foo": 4722366482869645213696}' | jq .foo
4722366482869645000000
% echo '{"foo": 4722366482869645213696}' | gojq .foo
4722366482869645213696
% jq -n '123456789 * 987654321'
121932631112635260
% gojq -n '123456789 * 987654321'
121932631112635269
% gojq -n '123456789123456789 * 987654321987654321'
121932631356500531347203169112635269
% gojq -n '987654321987654321 % 123456789123456789'
9000000009
% gojq -n -r 'def fact($n): if $n < 1 then 1 else $n * fact($n - 1) end; range(40;51) | "\(.)! = \(fact(.))"'
40! = 815915283247897734345611269596115894272000000000
41! = 33452526613163807108170062053440751665152000000000
42! = 1405006117752879898543142606244511569936384000000000
43! = 60415263063373835637355132068513997507264512000000000
44! = 2658271574788448768043625811014615890319638528000000000
45! = 119622220865480194561963161495657715064383733760000000000
46! = 5502622159812088949850305428800254892961651752960000000000
47! = 258623241511168180642964355153611979969197632389120000000000
48! = 12413915592536072670862289047373375038521486354677760000000000
49! = 608281864034267560872252163321295376887552831379210240000000000
50! = 30414093201713378043612608166064768844377641568960512000000000000
現在は四則演算と剰余、比較演算子しかサポートしていませんが *16、わりと楽しめるのではないかと思います。
例えば Project EulerのProblem 16 は 
の各桁の和を求めよという問題ですが、gojqを使うと次のように解くことができます。
% gojq -n 'def pow2($n): if $n < 1 then 1 else 2 * pow2($n - 1) end;
pow2(1000) | tostring | explode | map(. - 48) | add'
Project EulerのProblem 20 は 
の各桁の和ですね。
% gojq -n 'def fact($n): if $n < 1 then 1 else $n * fact($n - 1) end;
fact(100) | tostring | explode | map(. - 48) | add'
オーバーフローを心配することなく整数を自由に計算できるのは安心感がありますね。
Project Eulerをjqで解くチャレンジをした人はこれまでいたのでしょうか。
私もjqのポテンシャルを証明するために、何問か解いてみようと思います。
まとめ
jqのGo言語実装を作りました。
ほぼ全ての関数を実装しており、エイリアスを貼ってもほとんどの人は気が付かないと思います。
クエリが誤ったときのエラーメッセージを改善しており、クエリを書いたりjqを理解するための手助けになるのではないかと思っています。
jqは完全に理解しました。
もう自信を持ってjqのクエリを書けるようになったのです。
数か月前はjqのエラーメッセージに悩まされていたので、gojqを作ってよかったと思います。
バイトコードへのコンパイルは、本質的には再帰関数を一つのループに変換することです。
再帰的に構文木をたどって評価を行う処理系は、実装はわかりやすくて楽ですが後々に大きな禍根を残すことになります。
セマンティクスを正確に分析し、バイトコードと評価器に落とすのは、楽しい作業です。
JSONのイテレータというセマンティクスは、保存と復帰のできるスタックとforkという命令に対応していることがわかりました。
インタープリタを実装する上で最も大事なことは、スタックとバイトコードをデバッグできるようにしておくことです。
特にjqにはforkというスタックの保存と復帰という複雑な動きがあります。
出力コードが間違っているとスタックがめちゃくちゃになったりクラッシュしたりするので、デバッグできるようにしておくことは大事です。
プログラミング言語の処理系を作るのは、とても楽しいことだと思います。
インタープリタ言語を一つ触っていれば、大まかな構造はどの言語も同じなので、処理系のコードが読みやすくなります。
みなさんもぜひ、言語処理系に挑戦してみてください。
itchyny.hatenablog.com
itchyny.hatenablog.com
