DynamoDB 向け PartiQL パーサーを手書きした理由

DynamoDB が受け付けるのは PartiQL のごく狭い一部です。GROUP BY、ステートメントレベルの LIMIT、* による乗算、CAST、サブクエリは、どれも正しい SQL に見えます。そしてどれも AWS まで送られ、ValidationException になって返ってきます。

DynoTable のクエリエディターは CodeMirror の上に作られています。そのリンター、つまり入力中にミスへ下線を引くコードは、これらの大半をキーワードで捕まえていました。しかし構造は見えませんでした。そこで私たちは DynamoDB の PartiQL 方言のためのパーサーを手書きしました。

正確な下線にも、安全なクイックフィックスにも、その構造が必要です。8 月に、このパーサーを dynamodb-partiql-parser としてオープンソースにしました。TypeScript 製で、依存関係はゼロ、ライセンスは MIT です。

CodeMirror との統合は codemirror-lang-partiql として別に公開しています。

正規表現のリンターは乗算と `SELECT *` を区別できない

DynoTable の最初の PartiQL リンターは、およそ 650 行の正規表現とトークンスキャンでした。これは実際のミスを捕まえていました。GROUP BY、DISTINCT、CASE、WHERE 内の集計関数、そして DynamoDB にない文字列関数です。

最もよくあるうっかりミスも捕まえていました。DynamoDB では IN リストを WHERE OrderID IN [100, 300, 234] のように角括弧で書きます。リンターは、SQL の癖で丸括弧を書いた箇所を指摘していました。

クイックフィックスはわずかでした。たとえば、ダブルクォートで囲んだ文字列値をシングルクォートに変えるものです。

弱点は構造でした。SELECT price * quantity の * は乗算で、DynamoDB はこれを拒否します。SELECT * では、すべての属性を意味します。この 2 つを見分けるにはパーサーが必要です。

範囲も近似でした。WHERE 内の集計関数を検出するルールは、一致を見つけたあと、その位置を知るためにテキストをもう一度検索していました。行を指すには十分でしたが、正確な位置のテキストを置き換えるクイックフィックスには粗すぎました。

新しいルールはどれも、他のルールを避けて動く必要がありました。エイリアスのルールは、同じ範囲を二重に指摘しないよう、CAST(...) の中の一致を飛ばしていました。

SELECT リスト内の集計関数を検出するルールは、サブクエリを含むリストをすべて飛ばしていました。その正規表現が間違った FROM をつかんでしまうからです。

DynamoDB の方言を話すパーサーは npm になかった

この問題には以前にも出会っていました。DynoTable の SQL Workbench はテーブルに対して本物の SQL を実行しますが、その最初のパーサー構成は間違った答えを返しました。私たちはそれを具象構文木のパーサーに置き換えました。

その置き換えから、どの木を作るべきかを学びました。具象構文木（CST）は、すべてのトークンとその位置を保持します。抽象構文木（AST）は、意味だけを保持します。クイックフィックスはソースを編集するので、CST が必要です。

ただし、SQL の文法は PartiQL に合いません。DynamoDB の方言には、角括弧の IN リスト、バッグリテラル（<<'a', 'b'>>）、引用符付きキーのマップリテラル（{'rating': 5}）、リストインデックス付きのドキュメントパス（Devices.FireStick.DateWatched[0]）があります。

さらに、アイテムにない属性を表す MISSING リテラルや、書き込みでの RETURNING ALL OLD * もあります。SQL の文法はこれらをどれも知りません。逆に、DynamoDB が拒否するものを多く受け付けます。

npm で見つかった PartiQL パーサーは汎用のものでした。@aws/lsp-partiql は、PartiQL チームの Rust パーサーを WebAssembly でビルドしたものを同梱しています。partiql-js と piqel は、独立した Rust 実装を公開しています。

どれも DynamoDB が何を拒否するかをモデル化しておらず、DynamoDB の方言のためのパーサーは npm にありませんでした。そこで、小さなレキサーと再帰下降パーサーを書きました。形は Workbench の新しいパーサーにならっています。

木のすべてのノードがソースオフセット、つまりクエリテキスト内でそのノードが始まる位置と終わる位置を持ちます。

このパッケージにはランタイム依存がゼロで、依存が 1 つでも現れれば CI がビルドを失敗させます。そのため、ブラウザーのページにも自分のプロジェクトにも、簡単に組み込めます。

リンターのパーサーは、ほとんどの時間を壊れた入力に費やす

文法は簡単なほうの半分でした。リンターがパースするのは、たいてい書きかけのコードです。キー入力途中のステートメント、閉じていない括弧、3 番目の句のタイプミスなどです。最初のエラーで止まるパーサーは、その後ろを何もリントできません。

そのため、このパーサーは回復します。壊れた式はエラーノードと診断になり、パースは続きます。壊れたステートメントがあると、パーサーは次の ; かステートメントのキーワードまで読み飛ばすので、前後のステートメントはそのままリントされます。

正確なオフセットがあれば、診断に編集を持たせられます。IN (1, 2) には、丸括弧を角括弧に入れ替える修正が付きます。Title LIKE '%foo%' には contains(Title, 'foo') への書き換え、Title LIKE 'foo%' には begins_with(Title, 'foo') への書き換えが付きます。

仕様フィクスチャはすべて、元にした AWS のページを引用する

方言のルールは AWS の PartiQL リファレンスから来ています。ドキュメントから導いた振る舞いは、ずれることがあります。ドキュメントが変わり、コードは変わらず、誰も気づかないのです。

仕様コーパスは、各ルールをその出典までたどれるようにします。103 個のフィクスチャがあり、それぞれが期待される診断付きのクエリファイルです。そしてすべてが、そのルールを取った AWS ドキュメントの URL で始まります。

カバレッジ表は、文書化された各ルールを少なくとも 1 つのフィクスチャに対応付けます。フィクスチャのないルールがあるか、表にないフィクスチャがあれば、スイートは失敗します。

コーパスはドキュメントの変更をそれ自体では検出しません。誰かが気づく必要は残ります。そのとき、引用された URL が再確認すべきフィクスチャを示し、更新は出典付きのフィクスチャの差分として入ります。

文書化されたルールの中には、リンターが持たないコンテキストを必要とするものがあります。AWS の operators ページは、IN リストの上限をパーティションキーでは 50 個、キーでない属性では 100 個としています。

テーブルのスキーマがなければ、リンターはどちらの上限がカラムに当てはまるかを判別できません。そこでリストが 100 個を超えた時点で警告し、その警告で両方の上限を示します。

貼り付けたゴミでパーサーがオーバーフローまたはフリーズしうる

リリース前のコードレビューで見つかったバグのうち 2 つは、実際のクエリでは一度も起きていないもので、今ではストレステストで固定しています。深いネストはコールスタックをオーバーフローさせました。100 KB のゴミを貼り付けると、私たちのマシンでレキサーが 15.8 秒フリーズしました。

CodeMirror は、入力が少し止まったあとにリンターを実行します。エディターはまた、クエリを実行するボタンを有効にするかどうかを決めるため、変更のたびに同期的にエラーを確認します。

そこで例外が起きるとパーサーの外へ抜け出し、エディターのエラー状態が誤ったままになりました。

再帰下降パーサーは、それ自体がコールスタックを通じて例外を投げうるものです。ネストの各レベルが 1 つのスタックフレームになります。何千段もネストした [ や長い NOT NOT NOT の連鎖は、最後に V8 の RangeError: Maximum call stack size exceeded になります。

現在、式の再帰は 500 段で止まります。人が書くどんなものよりはるかに深く、スタックの予算には十分収まる値です。それを超えると、パーサーは例外を投げる代わりに 1 つの診断を出します。NOT の連鎖は、今ではループでパースします。

貼り付けた入力は、はるかに深く連鎖します。たとえば、何千もの腕を持つ A UNION B UNION C です。こうした連鎖は今ではフラットなリストです。パーサーは腕ごとに 1 フレームを使うのではなく、1 つのフレームと集合演算の配列を持ちます。

ゴミに対するレキサーのコストは、入力の 2 乗で増えていました。今では出力するエラーの数に上限があり、同じマシンで 100 KB の貼り付けを 22 ミリ秒で字句解析します。

ストレステストはビルドのたびに実行されます。パーサーに 100 KB のゴミ、30,000 段の演算子の連鎖、5,000 本の腕を持つ UNION を与えます。

公開されている lint() エントリーポイントも、あらゆる例外を捕捉して 1 つの診断を返します。次にこのパーサーを組み込むエディターには、リンターの上でエラーを受け止めるものが何もないかもしれないからです。

凍結した正規表現リンターが差し替えを審判した

パーサーが完成するころには、他のコードが正規表現リンターに依存していました。その関数の 1 つは、ステートメントを自動実行しても安全かどうかを決めていました。そこが黙って変われば、エディターは以前は実行していたクエリを拒否するようになります。

そこで古いリンターをその場で凍結し、新しいリンターに同じ 4 つの関数を持たせました。53 個のフィクスチャからなるパリティコーパスが、すべてのクエリを両方のリンターに通し、結果を比較します。

比較するのは、各診断の重大度とメッセージの最初の単語だけです。2 つのリンターはメッセージの言い回しが違うからです。

違いがあればテストは失敗します。ただし、フィクスチャにその理由が記録されている場合は別です。53 個のうち 15 個に理由があります。14 個はパーサーのほうが厳しいケース、1 個は意図的な変更として記録されています。

古いリンターは今もアプリの中で凍結されています。パリティコーパスは今、アプリが取り込むパッケージのアップグレードのたびに、それと照らし合わせて確認しています。

自分で作るなら応用できること

小さな方言なら、パーサーを手書きすること。 私たちのレキサーと再帰下降パーサーは 1 週間もかからず、すべてのエラーメッセージを自分たちのものにできました。
CST を作ること。 すべてのノードにソースオフセットがあれば、診断がクイックフィックスになります。ソースを捨てる木では、ソースを編集できません。
エラーから回復すること。 最初のエラーで止まるパーサーは、その後ろを何もリントしません。
凍結したインターフェースの背後でエンジンを差し替えること。 パリティコーパスで旧実装と新実装を突き合わせて固定し、許容する違いにはすべて理由を書かせます。
再帰の深さに上限を設け、連鎖を平坦にすること。 入力がネストしうる場所では、クエリだけでなくゴミでもテストします。
テストの中で出典を引用すること。 元にしたドキュメントページを名指しするフィクスチャは、そのページが変わったときに確認し直せます。

パーサーは GitHub と npm（npm install dynamodb-partiql-parser）にあります。エディター統合は codemirror-lang-partiql です。

方言そのものについては、PartiQL vs SQL が DynamoDB のサブセットにできることとできないことを扱い、PartiQL の例が実際のステートメントを順に説明しています。

これらすべてがそのために作られたエディターは DynoTable の中にあり、無料で試せます。