💡

Quartz v3のリリース: ClosureとInterface、それとテスト

2023/10/12に公開

コンパイラ

tech

前回のリリースノート

Quartz v3をリリースした

今回のリリースでは多くの言語機能を追加したので、かなりボリュームのあるリリースとなった。
追加した機能は例えば以下の通り。

Closure
Interface
メモリダンプツールの開発
FFIサポート

バージョンごとに、やったことなどを振り返りがてらみていく。

ランタイムの依存を減らし、全面的にWASIへ移行 (v2.2)

元々自前で用意が難しい関数などはランタイム側で用意してFFIでWASM側から呼ぶ、というような作りになっていた。
そのため環境変数・引数などの取得や、i64::to_stringなどの一部関数がランタイムに残ってしまっていた。

これらを剥がし、環境変数などに関するものはWASIに移行、i64::to_stringは自前で実装などを行って、今はランタイムから用意しているものは debug と abort の2つだけとなった。

余談だが、abortのようなものを実装するためにexception handlingを使いたいなあとなっている。ブラウザなどでは実装もあるが、今メインで使っているランタイムのwasmerがサポートしていないので、今は使えていない状態になっている。

関数のFFI機能のサポート (v2.4)

RustとWebAssemblyによるゲーム開発(以下にリンク)という面白い本があり、これをQuartzで移植する作業をやってみたくなった。

しかしそのためにはRustでいうところのweb_sysに相当するものが必要で、それにはFFIでWeb APIなどを扱えるようにする必要がある。
WASIは常に使うのでコンパイラからビルトインで良いが、Web APIはブラウザでしか当然動かないのでコンパイラ側で組み込むわけにはいかない。そのため、これを後から(ユーザーランドで)拡張したりできるようにする必要があるので、FFI関数を宣言できるような拡張を行った。

使用するときは、例えば以下のような宣言を行う。
これにより、fd_closeとそのラッパー関数が生成され、間のやりとりをコンパイラがよしなにやってくれるようになる。
Quartzのi32はWasm側のi64に相当するため(型タグなどが付与されていることによる)、この辺りを変換する部分としてコンパイラが間に立つ仕組みになっている。

@[build_if(version == "2.6.0"), declare_params(fd as wasm_i32, result as wasm_i32), declare_namespace("wasi_snapshot_preview1")]
declare fun fd_close(fd: i32): i32;

また、この辺りでwasiのバージョンをunstableからsnapshot_preview1に移行するなども行った(それまで、unstableが最新だと思い込んでいたがp1の方が新しいことを知ったため)。
wasmerの実装と、wasiのドキュメントで食い違うところなどがあって悩んでいたがwasiのバージョンが古いからということがわかって一安心した。

In-Source testingの導入 (v2.5)

In-Source testingを入れて、以下のようにソースコード中に自由にテストを書けるようになった。quartzをテストモードでコンパイルすると、test attributeがついた関数を集めてきてそれを順次呼ぶようにmainを書き換えるというような動作になる。

このあたりは、v2までに入れていたattributeの機能などが活用されている。

@[test]
fun test_i32_max() {
    assert_eq(1234.max(5678), 5678);
    assert_eq(5678.max(1234), 5678);
    assert_eq(1234.max(1234), 1234);
}

統合テストの導入 (v2.10)

v2.5で単体テストはかなり簡単に行えるようになったが、コンパイラに関するテストはそれだけでは十分とは到底言えない。特にこの頃GCに関するバグなどをたくさん出していたことなどもあり、実際のコンパイラを使った統合テストを導入することにした。

RustコンパイラのUIテストを参考とした。ファイルにプログラムを書いておき、それをコンパイルして実行した時の標準出力などを実際のものと比較してテストするようにした。
これによりGCで変なバグが起きておかしくなるなどもテストをかけるようになり、デグレに気がつける体制ができたのでかなり安心感が得られてよかった。

メモリダンプツールの開発 (v2.11)

GC関連のバグを調査・修正する過程で、バグがメモリが変に書き換えられてしまうタイプのものであったことも相まって、どうしてもメモリをダンプして眺める作業が必要になった。

最初の頃はテキストファイルに書き出してhexdumpなどで読もうとしたが4GBもあると変換に時間がかかりすぎる、かといって分割してしまうと後から4ファイル目の2400行目が元のどんなアドレスだったかを簡単に復元するのが難しくなってしまうので、悩んだ結果メモリダンプを読むためのツールを自作した。

見た目はほぼhexdumpだが、4GBあるメモリダンプを適当なチャンクに区切って分割し、分割後はオフセットを考慮してhuman-readableな形式に変換をしてくれるようになっている。

ダンプ結果の一例:

40006ab0  01 00 00 00 28 17 ff 3f 01 00 00 00 b8 16 ff 3f  |....(..?.......?|
40006ac0  01 00 00 00 38 16 ff 3f 01 00 00 00 b0 15 ff 3f  |....8..?.......?|
40006ad0  01 00 00 00 30 15 ff 3f 01 00 00 00 b8 14 ff 3f  |....0..?.......?|
40006ae0  01 00 00 00 40 14 ff 3f 01 00 00 00 c8 13 ff 3f  |....@..?.......?|
40006af0  01 00 00 00 50 13 ff 3f 01 00 00 00 d8 12 ff 3f  |....P..?.......?|
40006b00  00
...
4e200000  00

最初は楽しようとしてshell scriptでhexdumpやsplitを使ったコマンドの組み合わせでどうにかしていたが、不便すぎてPythonに移行し、速度が足りなくて最終的にGoで実装し直した。Goで書いた後もpprofなどでボトルネックを探して修正したりgoroutineを入れてconcurrentに動くようにしたりなど地味に手をかけたりした。
完全にyak shavingだなと思いながらやっていたが、とりあえず最初のPython実装の頃からすると1/10程度にはなったのでまあ全然よかったかなという気持ち。

おかげでGC関連のバグもひたすらダンプと格闘して修正ができた。
(厳密にはGCのバグではなく、実行時の型表現に関する処理がおかしかったのがGCを契機にトリガーされてメモリがめちゃくちゃになるというバグだった)

配列などのindexing専用構文の追加 (v2.13)

元々Quartzでは、例えば配列的なもの(ポインタやvectorなど)のi番目にアクセスするには v.at(i) のような関数を使った表現を使っていた。

これを代入時にも濫用し、 v.at(i) = 10; のような文でも動くようにできると思っていたが、これは私が左辺値と右辺値を正しく理解していなかった頃のミスであることがわかった。

上記のようなコードでは一度IR上で (assign (call at v i) 10) のような形式にコンパイルされることになる。
これはvがポインタやvectorのような、コンパイラ組み込みの型であればある程度特別扱いができるが一般的な状況で関数の中にある左辺値をどうコンパイルするかというのは簡単ではない。

Rustでは v[i] = 10; のような左辺値はindexメソッドを呼ぶことになっているが、これは *v.index(i) = 10; と脱糖(？)され、さらに *P = v; はアドレスPにvを代入するということで (store P v) のようなコードに落ちる。
このように、代入文では最終的に左辺値の一番外側がdereferenceになることが期待され、それを外してメモリへの書き込みに変えることになる。そしてこれをやるためには、一番外側が関数呼び出しだと困るので、indexingにはやはり専用の構文が必要であると思い直した。

このため、Quartzでは v.(i) = 10; のような構文でindexingをサポートした。 v[i] の表記にしなかったのは貴重なbracketを型のための構文として使いたかったからだが、この辺りはかなり好みも分かれるし思想がでるところだな〜という感じ。

interfaceのサポート (v2.14)

インターフェイスをサポートし、以下のようなコードが動くようになった。

interface Output {
    fun output(self): i32;
}

struct Impl1 {
}

module Impl1: Output {
    fun output(self): i32 {
        return 17;
    }
}


fun main(): i32 {
    let v = make[vec[Output]]();
    v.push(Impl1{});
    v.push(Impl1{});

    let s = 0;
    for i in v {
        s = s + i.output();
    }

    return s;
}

実装としてはほぼGoのパクリとなっている。型ごと(ここではImpl1)にITableというテーブルを生成し、ここにそれぞれのメソッドごと(ここではoutput)への関数ポインタを保持しておく。
また、構造体→インターフェイスにキャストしている部分(ここではImpl1→Outputへのキャスト)で、ITableへのポインタと元々の構造体のペアにキャストするような変換を行うようにした。

Goの実装でよく出てくるような仕組みをほぼ記憶頼りに作ってみたが、問題なく動作しやはりGoは参考になるな〜と思った(他にも、Quartzはかなり多くの影響をGoから受けている)。

また、余談だがWasmでは関数ポインタはサポートされておらず、線型メモリに関数を乗せることができない。代わりにテーブルというものを宣言して、そこに対して特別な呼び出し命令 call_indirect を使うことで関数を動的に呼び出すことができる。
ITableではテーブルのindexを保持することで、これを実現している。

Closureのサポート (v3.0)

RustとWebAssemblyによるゲーム開発などの実装をやっていて思ったが、GUIなどはやはりcallbackの嵐になるのでその際にClosureがないとかなり困ることになる。

ということでこのタイミングでClosureをサポートすることにした。

実装としては、Closureがcaptureしている変数を探しておき、それらを全てheapに退避させるという方法をとった。
(最近翻訳本もでたところである)CraftingInterpretersではUpvalueというテクニックが紹介されていたがあまりよくわからず、実装も難しそうだったので断念した。

とはいえやはりClosureは覚悟していた程度には難しく、そもそも上記の「captureしている変数を探しておく」のも「それらを全てheapに退避させる」のも実装はそれなりに大変ではあった。
さらに、heapに退避させるためには変数宣言をheap allocationに書き換え、変数を利用している箇所をポインタのdereferenceに書き換えるなどの作業が必要で、コンパイラのパスがまた1つ増えてしまったのも敗北感がある。

とりあえず、それらしく動いているので個人的には満足。

おわりに

いい加減ジェネリクスをサポートしようと思っている。
また、Language Serverの実装をもう少し手を入れて、安定化を目指したい所存。本当はサーバーが立てられると良いのだが、wasiだけだと難しいのでFFI側から手を入れるか、あるいは場合によってはwasixを使うということも必要かもしれない。

加えて、RustとWebAssemblyによるゲーム開発の移植も進めていきたい。