我們為什麼為 DynamoDB 手寫了一個 PartiQL 解析器
DynamoDB 只接受 中很窄的一個切片，其餘的一律在請求時拒絕。GROUP BY？ValidationException。語句級別的 LIMIT？ValidationException。* 運算子、CAST、一個子查詢？在你腦子裡它們全都解析得好好的，一路傳過網路，然後死在伺服器上。那份知識唯一存在的地方就是 AWS 的文件和錯誤訊息，這意味著每一個 DynamoDB 編輯器 —— 包括我們的，有一段時間也是如此 —— 都會樂呵呵地讓你寫出一條引擎保證會拒絕的語句。
我們希望這個拒絕發生在編輯器裡、發生在按鍵的當下，在出問題的那個子句下畫一條紅色波浪線，並在存在改寫方案時提供一鍵修復。那個編輯器層面的需求，最終變成了一個為 DynamoDB 的 PartiQL 方言手寫的詞法分析器和 CST 解析器，而這週我們把它開源了：dynamodb-partiql-parser，純 TypeScript、零依賴、MIT 授權，配套的 CodeMirror 接線則單獨發布為 codemirror-lang-partiql。這篇文章講的是它為什麼是手寫的、第一版 linter 錯在哪裡，以及那兩個只有在有人貼進一堆垃圾時才會冒出來的 bug。
正規表示式曾經夠用，直到它不夠用
DynoTable 裡的第一個 PartiQL linter 大約是 650 行的正規表示式和 token 掃描，而它確實有用：十九項各自獨立的檢查、針對常見陷阱的快速修復（IN (...) 改成 [...]、LIKE 改成 contains()、IS NULL 改成 attribute_not_exists()）。它發布了，抓到了真實的錯誤，在它覆蓋到的那些情形上，使用者不再提交“為什麼我的查詢會失敗”的工單。
但一個正規表示式 linter 懂的是模式，不是結構。它看不出 SELECT price * quantity 裡的 * 是 DynamoDB 會拒絕的算術運算，因為 * 同時也表示“所有列”，而要分辨這兩者，就得真的去做解析。它的診斷範圍是近似值 —— 準到足以指向某一行，卻粗到無法驅動一個要在精確偏移量處拼接文字的快速修復。而每加一項新檢查，這一堆東西就更脆弱一分，因為每一條正規表示式都得防著其他每一條正規表示式的假設。
“linter 需要結構”的解法是一個解析器。問題在於用哪一個。
沒有人構建過這樣的東西
在工作臺的真 SQL 那一側，我們已經經歷過這一遭：一個對我們撒謊的現成 SQL 解析器，後來被 sql-parser-cst 取代，後者在每個節點上都攜帶一個原始碼範圍，並保留識別符號帶引號與不帶引號的區別。那段經歷為 PartiQL 這一側該有什麼定下了標準 —— 一棵無損的具體語法樹，而不是一棵有損的 AST。
但在對解析器而言最要緊的地方，PartiQL 並不是 SQL。DynamoDB 的方言用方括號寫 IN 列表（WHERE OrderID IN [100, 300, 234]），有 bag 字面量（<<'a', 'b'>>）、帶引號鍵的 map 字面量（{'rating': 5}）、一個 MISSING 字面量、帶列表索引的文件路徑（Devices.FireStick.DateWatched[0]），以及 RETURNING ALL OLD * —— 這些沒有一樣是 SQL 語法認得的。反過來看，它又缺了 SQL 語法堅持要有的那一半東西。當時 npm 上的那些解析器，都是 AWS 那個面向通用 PartiQL 的 Rust 實現的 WebAssembly 構建版，對 DynamoDB 具體會拒絕什麼毫無概念。
於是我們寫了一個：一個小小的詞法分析器和一個遞迴下降解析器，其形態照著 sql-parser-cst 教會我們去想要的樣子來。每個節點都攜帶自己的位元組範圍。整個東西有零個執行時依賴 —— 這是一項如今由 CI 來斷言的性質，因為正是它讓這個解析器能被嵌到任何地方，包括瀏覽器裡，也包括你的專案裡。
語法是簡單的那一半。一個 linter 的解析器，一輩子都在解析壞掉的程式碼。打字打到一半、只有半條語句、第三個子句裡有個拼寫錯誤。在第一個錯誤處就停下來會讓編輯器變得毫無用處，所以這個解析器是容錯的：它記下一條診斷、重新同步、然後繼續往下走，於是在第二個子句還不完整時，第四個子句照樣會被檢查。
在不把飛機弄壞的情況下換掉引擎
等到解析器準備就緒時，那個正規表示式 linter 的四個函式已經在整個編輯器裡承重了 —— 其中包括決定一條語句是否可以安全自動執行的那一個。悄無聲息地改掉那個行為，表現出來就是“編輯器不肯執行我的查詢”，而這類 bug 使用者與其說會回報，不如說會直接因此離開。
所以這次替換走的是絞殺者路線：舊的 linter 被改名、凍結，並留在程式碼樹裡。新的、由解析器驅動的 linter 重新匯出了一模一樣的那四個函式。而一套對等語料庫（parity corpus）會把每一個測試夾具同時餵給兩個 linter，並把兩邊的輸出互相釘死 —— 正規表示式版本產生的每一條診斷，解析器版本都必須也產生出來，然後才被允許產生更多。舊的 linter 今天依然在那裡、依然凍結著，作為這次替換所許下的承諾的可執行文件。
只有垃圾輸入才找得到的 bug
有兩個故障從未在任何真實查詢中出現過，而它們都足以把編輯器整個放倒。
一個 CodeMirror linter 會在每一次變更時對文件同步執行，而它上方沒有任何錯誤接收層。一個未被捕獲的例外不會只是讓一次檢查失敗 —— 它會讓編輯器白屏。而一個遞迴下降解析器天生就內建了一個未捕獲例外的來源：呼叫堆疊。貼進幾千層深的 [[[[[[…，或者一條 NOT NOT NOT … 鏈，每一層巢狀就是一個堆疊幀；V8 最終會丟擲 RangeError: Maximum call stack size exceeded，直接穿過 linter。
這些修復是刻意做得無聊的。表示式的遞迴有一個硬性的深度上限 —— 五百層，遠遠超出任何人手寫的量，又遠低於堆疊預算 —— 超過之後，解析器發出一條診斷，而不是丟擲例外。而那些貼上時現實中真會連成串的構造，比如幾千個分支長的 A UNION B UNION C …，則從遞迴改寫成了扁平列表：一個 parseSelect 幀加上一個集合運算的陣列，而不是每個分支一個幀。如今壓力測試套件會在每一次構建時貼進 100 KB 的垃圾和 30,000 層深的運算子鏈，而公開的套件把整條流水線包在一個永不丟擲例外的 lint() 入口點後面，因為下一個嵌入這東西的編輯器，會遇到和我們一樣的“沒有錯誤接收層”的問題。
一套可以對照 AWS 文件審計的測試套件
這些方言規則 —— DynamoDB 接受什麼、拒絕什麼、哪一種改寫能修好哪一種問題 —— 全都來自 AWS 的 PartiQL 參考文件。從文件推導出來的行為有一種特定的失效模式：文件變了，程式碼沒變，而且沒有人注意到。
所以整個語料庫就是照著它來組織的。兩百零八個測試夾具，每一個開頭都寫著該規則所出自的那個 AWS 文件頁面的 URL。一張覆蓋表把每一條有文件記載的規則對映到它的夾具，而一旦某條規則失去了它的夾具，測試套件就會失敗。當 AWS 改動方言時，那個 diff 就是一個帶著出處引用的夾具 diff。
這份紀律在我們開源的那一週就回本了。linter 的 IN 列表警告引用了兩個上限：分割區索引鍵列上 50 個值，非鍵列上 100 個。在發布前重新核實每一個數字時，我們能在 AWS 當前的文件裡確認那個 100 —— 卻在任何一份現行文件裡都找不到那個 50。它在部落格文章和陳年論壇回答裡到處活著，但一手來源早已不是那樣了。linter 是誤打誤撞才做對的（它只在超過 100 時才警告，因為在沒有你的 schema 的情況下，它無從判斷適用的是哪一種情形），而現在那條註解會明確說出這個說法裡哪一半是有文件依據的、哪一半是民間傳說。
如果你也在構建一個，有哪些經驗可以遷移
- 為一個小方言手寫一個遞迴下降解析器，是以天計的工作量，不是以月計，而且每一條錯誤訊息都由你自己掌控。“寫一個解析器”那個嚇人的版本，預設的是一套龐大的語法。
- 構建一棵 CST，而不是一棵 AST。每個節點上的位元組範圍，正是把診斷變成快速修復的東西；一棵有損的樹沒辦法拼接文字。
- 如果解析器要餵給一個 linter，容錯就是那個功能本身。要恢復並繼續；一個在第一個錯誤處就停下的解析器，它後面的東西一條都檢查不到。
- 在一個凍結的介面背後替換引擎，並用一套對等語料庫把新舊兩者釘在一起。舊的實現就是你早已同意過的那份規格。
- 任何輸入可以巢狀的地方，都會有人貼進某個巢狀得荒謬的東西。給遞迴設深度上限、把鏈條扁平化；拿垃圾去測試，而不只是拿查詢。
- 在測試裡註明你的出處。一個寫明了自己所編碼的那個文件頁面的夾具，是一個在文件變動時可以被審計的測試 —— 而它一定會變。
這個解析器在 GitHub 上，也在 npm 上（npm install dynamodb-partiql-parser），編輯器整合則在 codemirror-lang-partiql。如果你想要的是方言本身而不是解析器，PartiQL 與 SQL 的對比講了 DynamoDB 的這個子集能做什麼、不能做什麼，而 PartiQL 範例則是實作的逐步演練；這一切為之而建的那個編輯器就在 DynoTable 裡，你可以免費試用。