sqleibniz は SQLite 方言 SQL の構文、テーブル・カラム・関数の存在有無、ランタイム条件を確認するための静的解析ツールであり、そのためにトークン化とパースが中核的な段階になる- Rust の
macro_rules! は、AST ノード構造体、Node トレイト実装、Go 風のテーブル駆動テストを、繰り返しなしで作れるようにしてくれる
matches! と match パターンを使うと、SQLite の数値リテラル、識別子、シンボル、EXPLAIN QUERY PLAN のような文法分岐をコードに近い形で移せるOption の is_some_and、map、map_or と ? 演算子は、入力・トークンストリーム処理における値の存在有無、変換、デフォルト値、エラー伝播を簡潔にする- Rust のイテレータは、数値リテラルからの
_ の除去、blob 内部の16進文字検証、エラー位置計算に活用され、トークン化・パースのコードをより読みやすくする利点につながる
sqleibniz の解析フロー
sqleibniz は SQLite 方言を対象に作成中の SQL 解析ツール- SQL 入力に対して構文チェック、テーブル・カラム・関数の存在有無の確認、組み込み SQLite ランタイムと組み合わせた条件検証を行おうとしている
- エラーメッセージは文脈と説明を提供し、特定の診断を無視できる形を目指している
- 解析フローは字句解析/トークン化から始まり、SQLite ドキュメントに従った SQL のパース、結果構造の解析へと続く
- 静的解析部分を終えた後は、SQL 用 LSP サーバーの作成も計画されている
マクロで AST ノードの繰り返しを削減
sqleibniz の AST ノードは Token を含む構造体であり、すべてのノードは Node トレイトを実装する必要があるNode トレイトは std::fmt::Debug をスーパートレイトとして使い、Debug を満たす型だけが Node を実装できる- 各ノードごとに構造体定義と
fn token(&self) -> &Token 実装を繰り返さないよう、node! マクロがこれを生成する
- ノード名は
ident メタ変数として受け取る
- ドキュメント文字列は
literal メタ変数として受け取る
- 追加フィールドは
$($field_name:ident:$field_type:ty),* 形式で繰り返し処理する
Literal ノードはトークンフィールドだけを持ち、Explain ノードは child: Option<Box<dyn Node>> フィールドを追加で持つ- ドキュメントコメントは
/// の代わりに #[doc = $documentation] 形式でマクロ引数をコンパイラに渡す
Go 風テーブル駆動テストを Rust マクロで実装
- Go のテーブル駆動テストのように、入力ケース配列を回しながら各ケースが独立したテストとして実行される方式を Rust マクロで再現する
- レキサーテストは
test_group_pass_assert! と test_group_fail! マクロを使う
- 成功テストは入力を
Lexer に入れ、Lexer.run() 結果のトークン型一覧を期待値と比較する
- 失敗テストは結果のトークンベクターが空で、
Lexer.errors に1つ以上のエラーがあるか確認する
cargo test 実行時、各ケースが別個のテスト関数のように ok または fail のフィードバックを出す
- パーサーテストも同じ構造に従うが、レキサー実行後に
Parser を初期化し、parse() 結果を検査する
EXPLAIN VACUUM; と EXPLAIN QUERY PLAN VACUUM; は成功ケースEXPLAIN; と EXPLAIN QUERY PLAN; は失敗ケース- 失敗ケースは SQLite の
sql-stmt 文法上、EXPLAIN の後に文が必要という条件を確認する
macro_rules! の不便な点
macro_rules! 内部では rust-analyzer のサポートが限定的
- 実際のインテリセンスがない
- 定義へ移動がない
- リテラルと言語構造シグネチャの hover がない
cargo fmt は macro_rules! 内部とマクロ呼び出し部分をフォーマットしたりインデントしたりしないtreesitter と chroma は macro_rules! の構文ハイライトで時々苦戦する- マクロのドキュメントも不足気味
文字マッチングで光る matches! と match
- レキサーの文字比較は他の処理の基盤であり、Rust の
matches! マクロと match パターンがこの部分を簡潔にしてくれる
- SQLite の数値判定は
matches! で書かれている
+, -_.a..=f, A..=F0..=9
- 識別子判定も
matches!(c, 'a'..='z' | 'A'..='Z' | '_' | '0'..='9') のように表現する
- レキサーのメインループは現在の文字を
match で分岐する
- 空白文字はスキップする
*, ;, ,, % などは、それぞれ対応するトークンを生成する- 不明なシンボル処理の例は省略され、
panic!("whoops") として示されている
トークンマッチングで SQL 文法構造を処理
- レキサーは文字ストリームを位置情報と型情報を持つ
Token 構造体のストリームに変換し、パーサーはそれを消費して AST を作る
Type enum は Keyword、Ident、Number、String、Blob、Boolean、ParamName、Param、Dot、Asteriks、Semicolon、Percent、Comma、Eof などを含むsql_stmt_prefix は SQLite ドキュメントの EXPLAIN 文を処理するパーサー関数
- 現在のトークンが
Type::Keyword(Keyword::EXPLAIN) なら Explain ノードを生成し、EXPLAIN を消費する
- 次のトークンが
QUERY なら QUERY と PLAN を連続して消費する
- その後、実際の SQL 文を
child としてパースする
EXPLAIN でなければ通常の sql_stmt 処理を呼び出す
literal_value は文字列、数値、blob、boolean とともに、NULL、CURRENT_TIME、CURRENT_DATE、CURRENT_TIMESTAMP のようなキーワードリテラルを Literal ノードにする
エラー表示と Option 活用
- レキサーとパーサーは、SQL 文末のセミコロン欠落のような場合をユーザーにエラーとして表示する
- Rust の
? 演算子はエラー処理と伝播に使われる
Option::is_some_and は、次の文字または現在の文字が存在し、かつ条件を満たすかを確認するときに使われる
self.source.get(self.pos + 1).is_some_and(...)self.source.get(self.pos).is_some_and(...)
Option::map は Vec<u8> 入力で次のバイトを char に変えるために活用されるOption::map_or は、現在のトークンまたは次のトークンがあるときだけ型比較を行い、なければ false を返す形で使われる
イテレータで数値と blob を処理
- SQLite の数値パースは
_ を許可するが、Rust の数値パースは _ を許可しないため、レキサーは _ を含めて消費した後、パース前に除去する
- この処理はイテレータチェーンで書かれている
- バイトスライスを取得する
- 各バイトを
char に変換する
_ ではない文字だけをフィルタリングするString として収集する
- この状況では
unwrap_or_default() を使うが、空文字列は数値として有効ではないため、いずれにせよパーサーが失敗する
- Go では同じ処理のために文字リストを走査し、
strings.Builder にバイトを書き込んだ後、再び文字列を作る必要がある
- SQLite blob は
x'<hex>' 形式の16進データを許可するため、文字列の各文字を chars().enumerate() で走査し、is_ascii_hexdigit() かどうかを確認する
enumerate は不正な文字の位置情報をエラー表示用に得るために使われる- 有効でない16進文字に出会うと、エラーを生成して処理を中断する
1件のコメント
Hacker News のコメント
2か月前なら筆者と同じ考えだったと思うが、Rust の厳格な境界である借用チェッカーに何度もぶつかった。
代数的データ型、たとえば Enum とパターンマッチングは本当に良かったが、借用チェッカーと低レベルのメモリ考慮のせいで、プロジェクトの核心であるプログラミング言語の問題よりも、借用チェッカーと格闘する時間のほうが多くなった。
そのため、トークン化とパースは問題なかったが、インタプリタと型検査は苦痛になり、より適した言語を探して F#、Zig/C、Go を検討した末に OCaml を見つけた。
構文は親切な Haskell のようで、ライフタイムのない Rust のように見えたので納得できたし、最初の Rust コンパイラも OCaml で書かれており、プログラミング言語の分野ではよく知られている。
まだ学習中なので公平な評価は難しいが、今のところ、まさに探していたものに近い。
実用的で速く、本当の低レベルというわけではなく、コンパイルも速く、何より人気が高いのでライブラリも揃っており、使うべきだとは思う。
しかし言語そのものがほとんど理不尽なほど嫌いで、あらゆる面が醜いと感じる。
2009年に C 寄りの人たちが作った言語だが、当時の基準で見ても、その前の20年間のプログラミング言語設計で興味深かったものを知らないように見える。
2009年の PHP でさえ Go より現代的で、よりよく設計された言語だったし、Go はその後も大きく良くなっていないという感覚を拭えない。
代わりに、静的文字列ライブラリのように cheap clone と interning が可能なものを使い、テキスト上の位置はインデックスだけを使うのがよい。
可能なら参照の保存は絶対に避けるべきだ。
cheap/free clone できるものとしてより多く保持するほど、借用チェッカーと格闘することが減り、必要なら clone に逃げられる。
実際のインタプリタ側では、arena のような方式でメモリ管理を助けるライブラリがかなり有用だ。
非常に特化した領域だが、性能と使いやすさを同時に提供し、Ruffle のようなプロジェクトもこうしたパターンを多用している。
ただし OCaml と Haskell は、組み込みの参照カウントとガベージコレクションのおかげで、こうしたことを「無料で」やってくれる。それでも Rust で非常に高速に進めるというアイデアは気に入っている。
Go は現代化された C に近く、提供するモデルは非常に単純だ。
C# から来ると、その単純さのせいでむしろ学ぶのが難しく、概念的な負担が低いことが利点であり、冗長さというトレードオフを受け入れられる、小さく集中したアプリケーションに向いている。
勧めるなら F#、あるいは最近の C# も悪くないと思う。
Microsoft が関わってはいるが、邪悪な大企業が作ったものは一切使わないという世界で生きようとすると大変になる。
Java、Go、Python、TypeScript/JavaScript、Swift もすべてこれに当てはまり、そうなると選択肢はほとんど残らない。
1年ほど OCaml を使った後の感想が気になる。
Haskell 系は興味深いが、Haskell 自体は学習曲線に対する見返りが自分には良くなかったし、Rust も似ている。
C# では型システムを深く掘り下げて熟達したが、Rust で同じくらい深く入り込む時間はない。
もちろんバイナリとメモリ使用量に10〜20MBほど上乗せされるが、今の基準ではほとんど何でもない。
たとえば Tailscale は、モバイルとデスクトップアプリでクロスプラットフォームの WireGuard レイヤーとして Go を使っているようで、うまく動いているように見える。
Go でネイティブ UI を作ることはないだろうが、低レベルの作業には優れている。
TinyGo はマイクロコントローラや WebAssembly 向けの Go 記述も可能にしてくれ、サポートされていないものも多いが、標準ライブラリのかなりの部分は使える。
たとえば Go コンパイラも Go で書かれている。
クロスコンパイルと比較的小さなバイナリのおかげで、デプロイは非常に簡単だ。
ただし構文糖が不足している点は確かで、関数型スタイルのパターンマッチングにはあまり向いていない。
パースへのアプローチとしては少し奇妙に見え、筆者は Rust と、その基盤となるプログラミング言語の概念に比較的慣れていないという印象を受ける。
いくつか挙げると、AST は代数的データ型として定義すればずっと単純になりそうだ。
sqlite の文法が突然新しいノードを大量に増やし、複雑なエンコーディングが必要になるような形で拡張されるとは思えない。
現在のエンコーディングは、オブジェクト指向には慣れているが代数的データ型には慣れていない人が思いつきそうな形に見える。
「マクロはほとんどの言語で異なる動作をするが、主な理由はコード重複の除去と反復の削減だ」という言い方は、関数のようなあらゆる抽象化メカニズムにも言える。
マクロを定義づける特徴は、コンパイル時に実行されることだ。
パーサーをきれいに構造化する方法を見るには、パーサーコンビネータの研究がよい出発点になるかもしれない。
ブログのタイトルも「Why I love ...」であり、指摘自体は妥当に見えるが、経験不足を指摘する必要は特にないように思う。
誰かがプログラミングを好きだというのは良いことだし、経験は後からついてくる。
これは関数ではできない。
Forsyth-Edwardsチェス記法用の小さなパーサー [0]を書いた立場からすると、単純さと可読性の面ではHaskellが圧倒的だと思う
ほとんどBNFのように読め、技術的な儀式的手順がほとんどないので、実際にパースしたい文法に集中できる
[0] https://github.com/ryandv/chesskell/blob/master/src/Chess/Fa...
[1] https://en.wikipedia.org/wiki/Forsyth%E2%80%93Edwards_Notati...
Rustで似たアプローチができない明確な理由があるのか気になる
例えば winnow [1] は十分に宣言的なスタイルを提供しているように見えるし、Rustには他にもパーサーコンビネータライブラリがいくつもある
[1]: https://docs.rs/winnow/latest/winnow/
単一のループを持つ簡単な関数で実装できるからだ
数日前、実験的なquad-bitboard実装用のFEN「パーサー」を書いたが、ほとんど自然に書けた
付け加えると、HackageのchessIOの作者でもある
RustでeBPF逆アセンブラと半分ほど作ったエミュレータを書いたが、パース系の作業をするにはRustはかなり気持ちのいい言語だった
ただ、筆者がケーススタディの1/6も進まないうちにマクロが必要になる時点で、自分の主張を弱めているように思う
マクロは完全なコード生成ではないが、言語の中で慣用的に作業している感覚もそれほど強くはない
非難したいわけではなく、Rustが実際かなり強い領域だと思う
例えば文脈自由規則
S ::= abc|aabbcc|aaabbbccc|...はa^Nb^Nc^Nを効果的にパースでき、これは文脈依存文法の例である単純な例だが、実際にも似たものが見られ、言語が演算子定義を許す場合がその一例だ
Rustはこうしたものをどう扱うのか
かっこよさそう
Ragelでパーサーとレキサーを書き、Go、Java、C++、Cを使ってきた経験からすると、ある程度のボイラープレート生成器さえあれば、純粋なCでも筆者が説明したRustコードと同じくらい良い
単純さのために、むしろ良いかもしれない
例えばJSONパーサーに必要なコードは大半がこの程度だ
https://github.com/gritzko/librdx/blob/master/JSON.lex
実際、あのeBNFはレキサーだけを作っており、パーサー部分もそれほど印象的ではなく、120行でかなり反復的だ
https://github.com/gritzko/librdx/blob/master/JSON.c
結局、パーサー基盤はeBNFさえあればパーサーを作れる地点まで進化し、そこが飽和点だと思う
Rustの代数的データ型は、生成された構文木を扱うのをずっと容易にしてくれると感じる
ただし、多少のコード生成やマクロの魔法でCをかなり扱いやすくできるという点には同意する
ただ、ここのコードは
https://github.com/gritzko/librdx/blob/master/JSON.lex
[を有効なJSONとして受け入れてしまわないかdelimiter = OpenObject | CloseObject | OpenArray | CloseArray | Comma | Colon;primitive = Number | String | Literal;JSON = ws* ( primitive? ( ws* delimiter ws* primitive? )* ) ws*;Root = JSON;JSONでdelimiterを1つだけ選び、残りはすべて0個にできるように見える
普通はRFCから見始める
https://datatracker.ietf.org/doc/html/rfc4627#autoid-3
RagelでJSONを実装できるのかも確かではない
Ragelは正規言語だけを処理でき、JSONは文脈自由言語だと理解している
https://en.wikipedia.org/wiki/Cloudbleed
関連して、Rob PikeのGoにおける語彙スキャンの講演が好き
教育的でエレガントなアプローチだと思う
https://www.youtube.com/watch?v=HxaD_trXwRE
理由はゴルーチンのスケジューリングオーバーヘッドや、非効率なメモリ割り当てパターンだったように思う
見つけた中で最も良い議論は[1]
効率的なレキサーとパーサーを作るもう一つの優れた講演は、Andrew Kelleyの「Practical Data Oriented Design」[2]
要約すると、プログラムのメモリ使用量を減らしつつキャッシュフレンドリーにして、スループットを高める複数の戦略を説明している
1: https://news.ycombinator.com/item?id=31649617
2: https://www.youtube.com/watch?v=IroPQ150F6c
自分には驚くような経験が一つあった
高水準コンパイラのパーサーに使っていたパーサーコンビネータライブラリをそのままno-std環境で使い、マイクロコントローラ向けにコンパイルして、組み込み環境の高性能プロトコルパーサーとしてデプロイできた
同じライブラリをそのまま使ったということ
違いはStringを減らし、
&'static strをより多く使う程度なのでコンパイラで遊ぶことは、組み込みプロトコルパーサーを作る能力にかなりうまくつながる
RustでASTパーサー全体を書いたときに難しかったのは、具体的なAST型の階層をアップキャストとダウンキャスト込みで表現することだった
方法は見つけたが、
PhantomDataのような奇妙な型遊びとマクロが必要だったここでもかなり大げさなマクロが必要だったように思う
関連する先行事例がどんな形なのか気になる
アップキャスト/ダウンキャストに到達するまでは、だが
Rust経験が十分ではないので、良い扱い方があるのかは分からない
動的トレイトなら可能かもしれない
こういうマクロコードはどうデバッグするのか、またコードベースに新しく入ってきた人はどう理解するのか
node!マクロの使用箇所とマクロ定義を見ても、実際にどんなコードが生成されるのか把握しにくそう例を動かしてどんな型ヒントが出るか確認すればよいのか、IDEでhoverすると展開後の版を見られるのか、それとも確実にするにはコンパイル後のコードを参照する必要があるのか気になる
JS/TSだけで仕事をしていてマクロを触らないので、こういうワークフローが気になる
$ cargo expandを実行すれば結果のコードを見られるRustは実際には複数の言語に近く、「vanilla」Rust、宣言的マクロ、手続き的マクロがそれぞれ少しずつ異なる能力と方言を持つ
時間が経つとそれぞれの扱いに慣れてくる
ユニットテストも、マクロ修正の影響を理解するのに良い実験場所になる
それほど悪くはないが、コードベース内の手続き的マクロは少ないほど良い
宣言的マクロはやや理解しやすく、保守とテストはずっと容易
他の言語の不透明なコード生成についても同じように感じる
sqlite構文のパースは幸運を祈るしかない
数年前、仕事でsqliteのかなり小さなサブセットのパーサーを書かなければならなかった
sqliteは本当に好きで、いつもインスピレーションの源だ
鉄道図は非常に有用
https://www.sqlite.org/syntaxdiagrams.html
lemonパーサージェネレータは十分に評価されていないと思う
https://sqlite.org/src/doc/trunk/doc/lemon.html
言語選択の面では、代数的データ型のある言語なら何でもよく合う
TypeScriptでさえ、この用途には素晴らしいものになり得る
以前、Rustで手書きパーサーを書く小さな入門記事も書いた
https://www.nhatcher.com/post/a-rustic-invitation-to-parsing...