Penguji Regex

Yang tidak bisa dilakukan regular expression

Regular expression mencocokkan pola, bukan struktur. Regex tidak mengingat seberapa dalam posisinya di dalam sesuatu, yang berarti apa pun yang bisa bersarang tanpa batas benar-benar di luar kemampuannya: kurung yang berpasangan, tanda kutip bersarang, HTML, JSON, kode sumber.

Pola yang tampak berhasil untuk hal-hal ini sebenarnya hanya cocok dengan kasus umum dan gagal di kasus lain, biasanya tanpa suara. Pola tag HTML yang bekerja sampai sebuah atribut berisi >. Penghapus komentar yang memakan bagian tengah string literal. Pemisah CSV yang rusak di koma pertama yang diapit tanda kutip. Masing-masing adalah bug yang muncul berbulan-bulan kemudian di data orang lain.

Patokannya: jika hal yang ingin dicocokkan bisa berisi dirinya sendiri, Anda butuh parser. Regex sangat baik di lapisan di bawahnya: memvalidasi field, mengambil nilai dari format log yang sudah dikenal, mencari dan mengganti di seluruh basis kode, memisahkan dengan pembatas yang tidak mungkin muncul di dalam bagiannya.

Greedy, lazy, dan asal-usul backtracking

Quantifier bersifat greedy secara bawaan: .* mengambil sebanyak mungkin lalu mengembalikan karakter satu per satu sampai sisa pola cocok. Jadi <.+> terhadap <b>text</b> cocok dengan seluruh string, bukan tag pertama, karena .+ yang greedy menelan semuanya dan > terakhir terpenuhi oleh > terakhir di input.

Menambahkan tanda tanya membuat quantifier menjadi lazy - <.+?> mengambil sesedikit mungkin dan hanya cocok dengan <b>. Lazy biasanya yang dimaksud orang, dan character class biasanya lebih baik dari keduanya: <[^>]+> menyatakan persis apa yang Anda mau, sama sekali tidak bisa melewati batas tag, dan tidak melakukan backtracking.

Poin terakhir itulah alasan praktis untuk peduli. Backtracking yang membuat pola lambat, dan menaruh satu quantifier di dalam quantifier lain - (a+)+, (\s*\w+)* - membuat jumlah jalur yang dijelajahi engine tumbuh secara eksponensial. Pada input yang hampir cocok, pola seperti itu bisa berjalan bermenit-menit. Penguji ini menjalankan pencocokan di worker dan menghentikannya setelah satu setengah detik justru karena menulis pola seperti itu secara tidak sengaja adalah hal yang biasa.

Perbedaan dialek yang bisa menjebak

Engine yang dipakai di sini adalah milik browser Anda, jadi hasilnya sama persis dengan JavaScript. Hasilnya belum tentu sama dengan bahasa tempat Anda akan menempelkan pola itu.

Named group ditulis (?<name>...) di JavaScript, .NET, dan PCRE modern, tetapi Python juga menerima (?P<name>...) dan tool lama hanya memahami bentuk terakhir. Lookbehind tersedia di JavaScript terbaru, .NET, dan PCRE, tetapi harus berpanjang tetap di Python dan sama sekali tidak ada di Go. RE2 milik Go dan crate regex milik Rust sengaja tidak menyertakan backreference dan lookaround, dan itulah yang memungkinkan keduanya menjamin waktu linear - pola yang bergantung pada salah satunya tidak akan bisa dikompilasi.

Arti kelas singkatan juga bergeser. Di JavaScript \d hanya digit ASCII, di .NET secara bawaan cocok dengan digit dari aksara apa pun, dan di Python bergantung pada apakah polanya str atau bytes. Flag u di JavaScript-lah yang membuat . dan quantifier bekerja pada code point utuh, bukan code unit; tanpa flag itu, pola akan rusak pada emoji dan karakter apa pun di luar Basic Multilingual Plane.

Uji di runtime Anda sendiri sebelum merilis pola yang penting.

Menulis pola yang masih bisa dibaca nanti

Pasang anchor. Pola tanpa ^ dan $ yang dipakai untuk memvalidasi field akan dengan senang hati mencocokkan substring, sehingga pola email tanpa anchor menerima apa saja yang di dalamnya terselip alamat valid. Ini sumber celah validasi yang terus berulang.

Utamakan character class daripada alternasi jika keduanya bisa: [abc] lebih jelas dan lebih cepat daripada (a|b|c), dan [^,]+ menyatakan "tidak melewati koma" dengan tepat, sesuatu yang hanya didekati oleh .+?. Beri nama pada group alih-alih menghitungnya, karena (?<year>...) tetap benar ketika seseorang menyisipkan group di depannya, sedangkan $3 tidak.

Lalu uji kasus negatif. Kebanyakan pola ditulis dengan mencoba input yang seharusnya cocok sampai berhasil, yang hampir pasti menghasilkan pola yang terlalu longgar. Latihan yang lebih berguna adalah menempelkan input yang tidak boleh cocok dan memastikan memang tidak cocok - alamat yang formatnya salah, nilai yang berisi pembatas, baris yang hampir tetapi tidak persis sesuai format log yang Anda harapkan.

Membaca pola sungguhan sepotong demi sepotong

Ambil sebuah pola untuk baris log yang umum: ^(\S+) \S+ \S+ \[([^\]]+)\] "(\w+) ([^"]*)" (\d{3}) (\d+)$. Kelihatannya padat, tetapi bisa diurai dengan rapi. Tanda sisipan di depan mengunci pencocokan di awal baris. (\S+) menangkap deretan karakter bukan spasi, yaitu alamat klien, dan dua \S+ tanpa penangkapan sesudahnya melewati kolom identity dan user yang tidak dipakai siapa pun.

\[([^\]]+)\] menangkap stempel waktu: sebuah kurung siku yang di-escape, lalu segala sesuatu yang bukan kurung siku penutup, lalu kurung siku penutupnya. Yang membuat bagian ini kokoh adalah kelas karakter negatif, karena ia tidak mungkin melewati ujung kolom seperti yang akan dilakukan .+. Bagian permintaan yang diapit tanda kutip memakai gagasan yang sama dengan tanda kutip, lalu dipecah menjadi metode dan path.

(\d{3}) menangkap tepat tiga digit untuk kode status dan (\d+) menangkap jumlah byte, sedangkan tanda dolar mengunci ujung baris. Pelajarannya bisa digeneralisasi: pola yang disusun dari kelas karakter negatif dan jumlah pengulangan yang eksplisit lebih mudah dibaca dan berjalan lebih cepat daripada pola yang sama yang disusun dari titik dan kuantifier malas.

Backtracking katastrofik dan cara menghindarinya

Mesin yang memakai backtracking - dan sebagian besar memang begitu - akan mencoba kemungkinan lain ketika pencocokan gagal. Menyarangkan satu kuantifier di dalam kuantifier lain memberi mesin cara membagi masukan yang jumlahnya eksponensial, sehingga pola seperti (a+)+$ yang diadu dengan deretan panjang karakter a lalu diakhiri sebuah b bisa berjalan lebih lama daripada usia alam semesta.

Ini celah penolakan layanan yang nyata, terdaftar dengan nama ReDoS, dan sudah pernah menjatuhkan layanan produksi: satu ekspresi reguler di jalur pemrosesan permintaan, jika diberi masukan yang dirancang khusus, akan membuat satu inti CPU sibuk tanpa henti. Gangguan global Cloudflare pada 2019 disebabkan persis oleh pola berbentuk seperti ini.

Tiga pertahanan sudah menutup sebagian besar kasus. Hindari menyarangkan kuantifier dan pilih kelas karakter negatif daripada titik - [^"]* tidak mungkin tumpang tindih dengan apa yang mengikutinya, jadi tidak ada yang perlu dirunut balik. Gunakan grup atomik atau kuantifier posesif jika mesinnya mendukung. Dan kalau polanya datang dari pengguna, jalankan di worker dengan batas waktu, seperti yang dilakukan alat penguji ini, atau pakai mesin berwaktu linear seperti RE2.

Unicode, dan mengapa \w saja tidak cukup

Kelas singkat itu dulu didefinisikan untuk ASCII dan sampai sekarang sebagian besar masih begitu. Di JavaScript, \d hanya cocok dengan 0-9 dan \w hanya cocok dengan huruf ASCII, angka, dan garis bawah, sehingga pola yang memvalidasi nama dengan \w+ akan menolak José, Zoë, dan semua nama yang tidak ditulis dengan abjad Latin.

Escape properti Unicode menyelesaikan masalah ini dengan benar. Dengan flag u, \p{L} cocok dengan huruf apa pun dari aksara mana pun, \p{N} dengan karakter angka apa pun, dan \p{Script=Han} dengan satu sistem tulisan tertentu. Semua itu jauh lebih presisi daripada melebarkan kelas karakter secara manual, dan tetap bekerja seiring Unicode menambahkan karakter baru.

Ada alasan kedua untuk menyalakan flag u: tanpa flag itu mesin bekerja pada unit kode UTF-16, bukan titik kode, sehingga titik bisa cocok dengan separuh emoji dan kelas karakter bisa membelah pasangan pengganti. Bahkan dengan flag itu, satu karakter yang terlihat bisa terdiri atas beberapa titik kode - bendera, gambar keluarga, atau huruf beraksen yang ditulis sebagai huruf dasar ditambah tanda gabungan - jadi menghitung karakter dengan ekspresi reguler tetap memerlukan notasi himpunan dari flag v atau pustaka yang paham grafem.

Kapan sebaiknya tidak memakai ekspresi reguler

Untuk teks yang tetap, metode string biasa lebih jelas dan lebih cepat: startsWith, includes, split. Menarik keluar sebuah pola hanya untuk memeriksa apakah sebuah string berakhiran .json adalah kebiasaan yang layak ditinggalkan, karena versi sederhananya tidak perlu dijelaskan lagi di kemudian hari.

Untuk apa pun yang bersarang - HTML, JSON, kode sumber, kurung yang berpasangan - pakailah parser. Ekspresi reguler tidak bisa menghitung kedalaman, jadi setiap pola yang tampak sanggup menangani hal-hal ini sebenarnya hanya kebetulan kena pada kasus yang umum dan diam-diam gagal pada sisanya. Jawaban Stack Overflow yang terkenal tentang mengurai HTML dengan ekspresi reguler itu lucu justru karena inti argumennya tepat.

Untuk data terstruktur biasanya sudah ada alat yang dibuat khusus: parser CSV yang paham koma di dalam tanda kutip, parser URL yang paham userinfo dan nomor port, pustaka tanggal yang paham zona waktu. Semuanya ada karena versi ekspresi regulernya sudah ditulis ribuan kali dan setiap kali salah secara halus.

Pola yang akan Anda pakai berulang kali

Merapikan dan menormalkan spasi: \s+ yang diganti dengan satu spasi akan memampatkan deretan spasi, dan ^\s+|\s+$ memangkas kedua ujungnya pada bahasa yang tidak punya fungsi trim. Mengambil nilai di dalam tanda kutip: "([^"]*)". Memecah berdasarkan pembatas yang tidak muncul di dalam isi kolom: pakai kelas karakter negatif, bukan titik yang malas.

Ada dua pola yang sebaiknya tidak Anda tulis. Memvalidasi alamat surel dengan ekspresi reguler adalah jebakan - tata bahasa pada RFC 5322 memang benar-benar rumit, dan pemeriksaan yang masuk akal cukup memastikan bagian lokalnya tidak kosong, ada tanda at, dan ada titik di bagian domain, lalu mengirim pesan konfirmasi, karena itulah satu-satunya validasi yang sesungguhnya. Validasi URL punya bentuk masalah yang sama, dan kini setiap bahasa sudah menyertakan parser URL yang menjawab pertanyaan itu dengan benar.

Kalau sebuah pola sudah cukup panjang sampai perlu dijelaskan, gunakan grup bernama dan, pada bahasa yang mendukungnya, flag extended yang membolehkan spasi serta komentar di dalam pola. Pola yang masih bisa Anda baca enam bulan lagi sepadan dengan dua baris tambahan hari ini.