Mengapa kami menulis sendiri parser PartiQL untuk DynamoDB

DynamoDB hanya menerima sepotong kecil dari PartiQL dan menolak selebihnya pada saat permintaan dikirim. GROUP BY? ValidationException. LIMIT di tingkat pernyataan? ValidationException. Operator *, CAST, sebuah subkueri? Semuanya terurai dengan mulus di kepala Anda, melintasi jaringan, lalu mati di server. Satu-satunya tempat pengetahuan itu tersimpan adalah dokumentasi AWS dan pesan kesalahannya, yang berarti setiap editor untuk DynamoDB — termasuk milik kami, untuk sementara waktu — dengan senang hati membiarkan Anda menyusun pernyataan yang dijamin akan ditolak mesinnya.

Kami ingin penolakan itu terjadi di dalam editor, pada saat tombol ditekan, dengan garis merah bergelombang tepat di klausa yang bermasalah dan perbaikan sekali klik bila memang ada penulisan ulangnya. Kebutuhan editor itu berubah menjadi lexer dan parser CST tulisan tangan untuk dialek PartiQL milik DynamoDB, dan minggu ini kami membukanya sebagai sumber terbuka: dynamodb-partiql-parser, murni TypeScript, tanpa dependensi, MIT, dengan integrasi CodeMirror yang diterbitkan terpisah sebagai codemirror-lang-partiql. Tulisan ini adalah alasan mengapa parser itu ditulis tangan, apa yang keliru pada linter pertama, dan dua bug yang baru muncul ketika seseorang menempelkan sampah.

Regex sudah cukup, sampai akhirnya tidak lagi

Linter PartiQL pertama di DynoTable terdiri dari sekitar 650 baris regex dan pemindaian token, dan itu benar-benar berguna: sembilan belas pemeriksaan berbeda, perbaikan cepat untuk jebakan umum (IN (...) menjadi [...], LIKE menjadi contains(), IS NULL menjadi attribute_not_exists()). Ia dirilis, ia menangkap kesalahan nyata, pengguna berhenti mengirim tiket "kenapa kueri saya gagal" untuk kasus-kasus yang ia tangani.

Tetapi linter berbasis regex mengenal pola, bukan struktur. Ia tidak bisa melihat bahwa * dalam SELECT price * quantity adalah aritmetika yang ditolak DynamoDB, karena * juga berarti "semua kolom" dan membedakan keduanya menuntut parsing yang sesungguhnya. Rentang diagnostiknya hanyalah perkiraan — cukup dekat untuk menunjuk sebuah baris, terlalu kasar untuk menggerakkan perbaikan cepat yang menyisipkan teks pada offset yang persis. Dan setiap pemeriksaan baru membuat tumpukannya makin rapuh, karena setiap regex harus bertahan terhadap asumsi semua regex lainnya.

Solusi untuk "linter butuh struktur" adalah parser. Pertanyaannya adalah parser yang mana.

Belum ada yang pernah membuatnya

Untuk sisi SQL asli di Meja Kerja, kami sudah melewati hal ini: parser SQL siap pakai yang berbohong kepada kami, digantikan oleh sql-parser-cst, yang membawa rentang sumber pada setiap simpul dan mempertahankan perbedaan pengidentifikasi yang dikutip versus yang tidak. Pengalaman itu menetapkan standar untuk apa yang dibutuhkan sisi PartiQL — pohon sintaksis konkret yang lossless, bukan AST yang lossy.

Namun PartiQL bukanlah SQL pada bagian yang penting bagi sebuah parser. Dialek DynamoDB menulis daftar IN dengan kurung siku (WHERE OrderID IN [100, 300, 234]), punya literal bag (<<'a', 'b'>>), literal map dengan kunci berkutip ({'rating': 5}), literal MISSING, jalur dokumen dengan indeks list (Devices.FireStick.DateWatched[0]), dan RETURNING ALL OLD * — tidak satu pun dikenal oleh tata bahasa SQL. Sebaliknya, ia tidak memiliki separuh dari apa yang diwajibkan tata bahasa SQL. Saat itu, parser yang tersedia di npm adalah build WebAssembly dari implementasi Rust milik AWS untuk PartiQL generik, tanpa pengetahuan apa pun tentang apa yang secara spesifik ditolak DynamoDB.

Jadi kami menulisnya sendiri: sebuah lexer kecil dan parser recursive-descent, dibentuk mengikuti pola yang diajarkan sql-parser-cst untuk kami inginkan. Setiap simpul membawa rentang bytenya. Keseluruhannya nol dependensi runtime — properti yang kini ditegaskan oleh CI, karena itulah yang membuat parser ini bisa ditanamkan di mana saja, termasuk di browser, termasuk di proyek Anda.

Tata bahasanya adalah separuh yang mudah. Parser milik sebuah linter menghabiskan seluruh hidupnya mengurai kode yang rusak. Di tengah pengetikan, setengah pernyataan, salah ketik di klausa ketiga. Berhenti pada kesalahan pertama akan membuat editor tidak berguna, maka parsernya toleran terhadap kesalahan: ia mencatat diagnostik, melakukan resinkronisasi, dan terus berjalan, sehingga klausa keempat tetap dilint sementara klausa kedua masih belum lengkap.

Mengganti mesin tanpa menjatuhkan pesawat

Ketika parsernya siap, empat fungsi milik linter regex sudah menjadi penopang di seluruh editor — termasuk fungsi yang memutuskan apakah sebuah pernyataan aman untuk dieksekusi otomatis. Mengubah perilaku itu secara diam-diam akan muncul sebagai "editornya tidak mau menjalankan kueri saya", jenis bug yang tidak dilaporkan pengguna melainkan membuat mereka pergi.

Maka pergantiannya dilakukan ala strangler: linter lama diganti namanya, dibekukan, dan tetap disimpan di dalam repositori. Linter baru berbasis parser mengekspor ulang empat fungsi yang persis sama. Dan sebuah korpus paritas menjalankan setiap fixture melalui kedua linter dan menyematkan keluarannya satu sama lain — setiap diagnostik yang dihasilkan versi regex harus juga dihasilkan versi parser, sebelum ia boleh menghasilkan yang lebih banyak. Linter lama masih ada sampai hari ini, dibekukan, sebagai dokumentasi yang dapat dieksekusi tentang apa yang dijanjikan pergantian itu.

Bug yang hanya bisa ditemukan sampah

Dua kegagalan tidak pernah muncul pada kueri nyata mana pun dan keduanya akan menjatuhkan editor.

Linter CodeMirror berjalan secara sinkron di atas dokumen, pada setiap perubahan, tanpa penampung kesalahan di atasnya. Satu eksepsi yang tidak tertangkap bukan sekadar menggagalkan lint — ia membuat editor jadi layar putih. Dan parser recursive-descent punya eksepsi tak tertangkap bawaan secara alami: tumpukan pemanggilan. Tempelkan [[[[[[… sedalam beberapa ribu kurung, atau rantai NOT NOT NOT …, dan setiap tingkat penyarangan adalah satu stack frame; V8 pada akhirnya melempar RangeError: Maximum call stack size exceeded langsung menembus linter.

Perbaikannya sengaja dibuat membosankan. Rekursi ekspresi punya batas kedalaman keras — lima ratus tingkat, jauh melampaui apa pun yang ditulis manusia, jauh di bawah anggaran tumpukan — yang setelah dilewati parser memancarkan satu diagnostik alih-alih melempar eksepsi. Dan konstruksi yang realistis akan berantai saat ditempel, seperti A UNION B UNION C … sepanjang ribuan lengan, ditulis ulang dari rekursi menjadi daftar datar: satu frame parseSelect dan sebuah array operasi himpunan, bukan satu frame per lengan. Rangkaian uji tekan kini menempelkan 100 KB sampah dan rantai operator sedalam 30.000 pada setiap build, dan paket publiknya membungkus seluruh alurnya dalam entry point lint() yang tidak pernah melempar eksepsi, karena editor berikutnya yang menanamkan ini akan punya masalah tanpa-penampung-kesalahan yang sama seperti kami.

Test suite yang bisa Anda audit terhadap dokumen AWS

Aturan dialeknya — apa yang diterima DynamoDB, apa yang ditolaknya, penulisan ulang mana yang memperbaiki apa — semuanya berasal dari referensi PartiQL milik AWS. Perilaku yang diturunkan dari dokumentasi punya mode kegagalan yang khas: dokumennya berubah, kodenya tidak, dan tidak ada yang menyadarinya.

Maka korpusnya disusun mengikuti dokumen itu. Dua ratus delapan fixture, dan setiap satunya diawali dengan URL halaman dokumentasi AWS asal aturannya. Sebuah tabel cakupan memetakan setiap aturan terdokumentasi ke fixture-nya, dan rangkaian ujinya gagal bila sebuah aturan kehilangan fixture-nya. Ketika AWS mengubah dialeknya, diff-nya adalah diff fixture yang membawa kutipan sumbernya.

Disiplin itu terbayar pada minggu kami merilisnya sebagai sumber terbuka. Peringatan daftar IN pada linter menyebut dua batas: 50 nilai pada kolom kunci partisi, 100 pada kolom non-kunci. Saat memverifikasi ulang setiap angka sebelum publikasi, kami bisa memastikan angka 100 di dokumentasi AWS saat ini — dan tidak dapat menemukan angka 50 di mana pun dalam dokumen yang berlaku. Angka itu bertahan di banyak posting blog dan jawaban forum lama, tetapi sumber primernya sudah bergerak maju. Linternya kebetulan benar (ia hanya memperingatkan setelah lewat 100, karena tanpa skema Anda ia tidak bisa tahu kasus mana yang berlaku), dan komentarnya kini menyebut dengan tepat separuh mana dari klaim itu yang terdokumentasi dan separuh mana yang sekadar cerita rakyat.

Apa yang ditransfer jika Anda sedang membangunnya

• Parser recursive-descent tulisan tangan untuk dialek kecil adalah pekerjaan berhari-hari, bukan berbulan-bulan, dan Anda memiliki setiap pesan kesalahannya. Versi menakutkan dari "tulis sebuah parser" mengandaikan tata bahasa yang besar.
• Bangun CST, bukan AST. Rentang byte pada setiap simpul adalah yang mengubah diagnostik menjadi perbaikan cepat; pohon yang lossy tidak bisa menyisipkan teks.
• Jika parsernya memberi makan sebuah linter, toleransi kesalahan adalah fiturnya. Pulihkan dan lanjutkan; parser yang berhenti pada kesalahan pertama tidak melint apa pun sesudahnya.
• Ganti mesin di balik antarmuka yang dibekukan dengan korpus paritas yang menyematkan yang lama terhadap yang baru. Implementasi lama adalah spesifikasi yang sudah Anda sepakati.
• Di mana pun masukan bisa bersarang, akan ada yang menempelkan sesuatu yang bersarang secara absurd. Batasi kedalaman rekursinya dan ratakan rantainya; uji dengan sampah, bukan hanya dengan kueri.
• Kutip sumber Anda di dalam pengujian. Fixture yang menyebut halaman dokumen yang dikodekannya adalah pengujian yang bisa diaudit ketika dokumennya berubah — dan dokumennya pasti akan berubah.

Parsernya ada di GitHub dan npm (npm install dynamodb-partiql-parser), dengan integrasi editornya di codemirror-lang-partiql. Jika yang Anda inginkan adalah dialeknya sendiri alih-alih parsernya, PartiQL vs SQL membahas apa yang bisa dan tidak bisa dilakukan subset milik DynamoDB dan contoh PartiQL adalah panduan praktisnya; editor yang menjadi alasan semua ini dibangun ada di DynoTable, dan Anda bisa mencobanya gratis.