なぜ私たちは DynamoDB 向けの PartiQL パーサーを手書きしたのか

DynamoDB はのごく狭い一部だけを受け付け、それ以外はすべてリクエスト時に拒否します。GROUP BY? ValidationException。ステートメントレベルの LIMIT? ValidationException。* 演算子、CAST、サブクエリ? どれもあなたの頭の中では問題なくパースでき、ワイヤーを渡っていき、サーバー上で死にます。その知識が存在する唯一の場所は AWS のドキュメントとエラーメッセージでした。つまり DynamoDB のどのエディターも — 一時期は私たちのものも含めて — エンジンが確実に拒否するステートメントを、平気で書かせてしまっていたのです。

私たちは、その拒否をエディターの中で、キーストロークのたびに、問題のある句のちょうどその位置に赤い波線を出し、書き換えが存在するならワンクリックの修正つきで起こしてほしいと考えました。そのエディター上の必要が、DynamoDB の PartiQL 方言のための手書きのレキサーと CST パーサーになり、今週それをオープンソースにしました: dynamodb-partiql-parser、純粋な TypeScript、依存関係ゼロ、MIT、そして CodeMirror への配線は codemirror-lang-partiql として別途公開しています。この記事は、なぜそれが手書きなのか、最初のリンターは何を取りこぼしていたのか、そして誰かがゴミを貼り付けたときにだけ現れた 2 つのバグについてです。

正規表現で足りていた、足りなくなるまでは

DynoTable の最初の PartiQL リンターは、およそ 650 行の正規表現とトークンスキャンでできていて、本当に役に立っていました: 19 個の個別のチェックと、よくある罠に対するクイックフィックス（IN (...) を [...] へ、LIKE を contains() へ、IS NULL を attribute_not_exists() へ）。それは出荷され、実際のミスを捕まえ、それがカバーするケースについては「なぜ私のクエリは失敗するのか」というチケットをユーザーが出さなくなりました。

しかし正規表現のリンターが知っているのはパターンであって、構造ではありません。SELECT price * quantity の * が DynamoDB の拒否する算術だということを、それは見抜けませんでした。* は「すべてのカラム」も意味し、その 2 つを見分けるには実際にパースするしかないからです。診断の範囲は近似でした — 行を指すには十分近いけれど、正確なオフセットでテキストを継ぎ足すクイックフィックスを駆動するには粗すぎたのです。そして新しいチェックを加えるたびに、その山はより脆くなりました。それぞれの正規表現が、他のすべての正規表現の前提から身を守らなければならなかったからです。

「リンターには構造が必要だ」への答えはパーサーです。問題は、どのパーサーか、でした。

誰も作っていなかった

Workbench の本物の SQL 側では、私たちはすでにこれを通り抜けていました — 私たちに嘘をついた既製の SQL パーサーがあり、それを sql-parser-cst に置き換えたのです。こちらはすべてのノードにソース範囲を持ち、引用符つきと引用符なしの識別子を保持します。その経験が、PartiQL 側に必要なものの基準を決めました — 情報を失う AST ではなく、無損失の具象構文木です。

しかし PartiQL は、パーサーにとって重要な部分で SQL ではありません。DynamoDB の方言は IN のリストを角括弧で書き（WHERE OrderID IN [100, 300, 234]）、バッグリテラル（<<'a', 'b'>>）、引用符つきキーのマップリテラル（{'rating': 5}）、MISSING リテラル、リストインデックスつきのドキュメントパス（Devices.FireStick.DateWatched[0]）、そして RETURNING ALL OLD * を持ちます — そのどれも SQL の文法は知りません。逆方向では、SQL の文法が要求するものの半分を欠いています。当時 npm にあったパーサーは、汎用の PartiQL 向けの AWS の Rust 実装を WebAssembly でビルドしたもので、DynamoDB が具体的に何を拒否するのかという概念を持っていませんでした。

そこで私たちは自分たちで書きました: 小さなレキサーと再帰下降パーサーで、sql-parser-cst が私たちに欲しがることを教えてくれた形を手本にしています。すべてのノードが自身のバイト範囲を持ちます。全体としてランタイム依存はゼロです — 今では CI がその性質を検証しています。それこそが、このパーサーをブラウザーを含め、あなたのプロジェクトを含め、どこにでも埋め込めるものにしているからです。

文法は簡単なほうの半分でした。リンターのパーサーは、その生涯を壊れたコードのパースに費やします。キーストロークの途中、半分だけのステートメント、3 番目の句のタイプミス。最初のエラーで止まってしまえばエディターは使い物にならないので、このパーサーはエラー耐性を持ちます — 診断を記録し、再同期し、そのまま進むのです。だから 2 番目の句が不完全なままでも、4 番目の句はなおリントされます。

飛行機を壊さずにエンジンを交換する

パーサーが仕上がるころには、正規表現リンターの 4 つの関数がエディター全体で耐力を担っていました — ステートメントを自動実行しても安全かどうかを決めるものも含めて。その振る舞いを静かに変えれば、「エディターが私のクエリを実行してくれない」という形で現れます。それは、ユーザーが報告するというより、そのまま去っていく類のバグです。

だから差し替えはストラングラー方式にしました — 古いリンターは名前を変え、凍結し、ツリーの中に残したのです。新しいパーサー駆動のリンターは、まったく同じ 4 つの関数を再エクスポートします。そしてパリティコーパスがすべてのフィクスチャを両方のリンターに通し、その出力を互いに突き合わせて固定しました — 正規表現版が出したすべての診断を、パーサー版もまた出さなければならず、それができて初めて、それ以上のものを出すことが許されるのです。古いリンターは今日も凍結されたままそこにあり、この差し替えが何を約束したのかを示す実行可能なドキュメントになっています。

ゴミだけが見つけるバグ

2 つの障害は、どの実際のクエリにも現れないものでしたが、そのどちらもエディターを落としたはずのものでした。

CodeMirror のリンターは、変更のたびにドキュメントに対して同期的に走り、その上にエラーの受け皿はありません。捕捉されない例外が 1 つあれば、リントが失敗するのではなく — エディターがホワイトスクリーンになります。そして再帰下降パーサーには、捕捉されない例外が生まれつき組み込まれています: コールスタックです。[[[[[[… を数千段の括弧の深さで貼り付けるか、NOT NOT NOT … の連鎖を貼り付けると、ネストの各レベルがスタックフレームになります。やがて V8 が RangeError: Maximum call stack size exceeded を投げ、それがリンターをまっすぐ突き抜けます。

修正はあえて退屈です。式の再帰には固い深さの上限があります — 500 段、人間が書くどんなものよりはるかに深く、スタックの予算にはじゅうぶん収まる値です — それを超えると、パーサーは例外を投げる代わりに 1 つの診断を出します。そして、貼り付けが現実に連鎖する構文 — 何千もの腕を持つ A UNION B UNION C … のようなもの — は、再帰からフラットなリストへ書き換えました: 腕ごとに 1 フレームではなく、parseSelect のフレーム 1 つと集合演算の配列です。ストレススイートは今やビルドのたびに 100 KB のゴミと 30,000 段の深さの演算子連鎖を貼り付けますし、公開パッケージはパイプライン全体を決して例外を投げない lint() のエントリーポイントで包んでいます。次にこれを埋め込むエディターも、私たちと同じ「エラーの受け皿がない」問題を抱えることになるからです。

AWS のドキュメントに照らして監査できるテストスイート

方言のルール — DynamoDB が何を受け付け、何を拒否し、どの書き換えが何を直すのか — はすべて AWS の PartiQL リファレンスから来ています。ドキュメント由来の振る舞いには、特有の壊れ方があります: ドキュメントが動き、コードは動かず、誰も気づかない、というものです。

だからコーパスはそれに合わせて構造化してあります。208 個のフィクスチャがあり、そのどれもが、ルールの出どころである AWS のドキュメントページの URL で始まります。カバレッジ表が、文書化された各ルールをそのフィクスチャに対応づけ、あるルールがフィクスチャを失えばスイートは失敗します。AWS が方言を変えたとき、その差分は出典の付いたフィクスチャの差分になります。

その規律は、オープンソース化した週に元が取れました。リンターの IN リストの警告は、2 つの上限を引用していました — パーティションキーのカラムでは 50 個、キーでないカラムでは 100 個です。公開前にすべての数字を再検証したところ、100 のほうは AWS の現行ドキュメントで確認できました — そして 50 のほうは、有効なドキュメントのどこにも見つけられませんでした。それはブログ記事や古いフォーラムの回答のあちこちで生き延びていますが、一次情報のほうは先へ進んでいたのです。リンターはたまたま正しい振る舞いをしていて（あなたの schema がなければどちらのケースに当たるか判別できないので、100 を超えたときにしか警告しません）、コメントには今、この主張のどの半分が文書化されていて、どの半分が言い伝えなのかが正確に書かれています。

あなたが 1 つ構築しているなら、何が応用できるか

小さな方言のための手書きの再帰下降パーサーは、数か月ではなく数日の仕事であり、すべてのエラーメッセージを自分のものにできる。「パーサーを書く」の恐ろしいほうの版は、大きな文法を前提にしている。
AST ではなく CST を作れ。診断をクイックフィックスに変えるのは、すべてのノードに付いたバイト範囲だ。情報を失う木ではテキストを継ぎ足せない。
パーサーがリンターに供給するなら、エラー耐性こそが機能だ。回復して続けよ。最初のエラーで止まるパーサーは、その先を何もリントしない。
エンジンの差し替えは、凍結したインターフェースの背後で、新旧を突き合わせて固定するパリティコーパスとともに行え。古い実装は、あなたがすでに合意した仕様だ。
入力がネストできる場所ならどこでも、誰かがばかげた深さでネストするものを貼り付ける。再帰に深さの上限をかけ、連鎖を平坦にせよ。クエリだけでなく、ゴミでテストせよ。
テストの中で出典を引用せよ。自分が符号化しているドキュメントページを名指しするフィクスチャは、ドキュメントが変わったときに監査できるテストだ — そして、それは変わる。

パーサーは GitHub と npm（npm install dynamodb-partiql-parser）にあり、エディター統合は codemirror-lang-partiql にあります。パーサーではなく方言そのものが知りたいなら、PartiQL vs SQL が DynamoDB のサブセットにできることとできないことを扱っていて、PartiQL の例が実践的な手引きです。これらすべてがそのために作られたエディターは DynoTable の中にあり、無料で試すことができます。