Mesin regex internal sebagai library

 (blog.burntsushi.net)
1 poin oleh GN⁺ 2023-07-06 | 1 komentar | Bagikan ke WhatsApp
  • Crate Rust regex setelah bertahun-tahun penulisan ulang membuka sebagian besar mesin internalnya sebagai API crate regex-automata versi terpisah, dan transisi ini selesai di regex 1.9
  • Penulisan ulang ini berangkat dari sulitnya mengombinasikan strategi pencarian, sulitnya pengujian tiap mesin internal, kebutuhan akan API multi-pattern yang lebih rinci daripada RegexSet, serta perlunya berbagi DFA hasil kompilasi penuh
  • regex-automata menyusun pemrosesan regex dengan alur Ast → Hir → ekstraksi literal/Prefilter → Thompson NFA → PikeVM·BoundedBacktracker·one-pass DFA·DFA·lazy DFA → meta engine
  • Kinerja diperoleh dengan sebisa mungkin mengutamakan pencarian literal dan mesin keluarga DFA, lalu dilengkapi dengan PikeVM, bounded backtracker, atau one-pass DFA saat ada capture group atau kasus pengecualian
  • API publik dan abstraksi yang dapat digunakan ulang mempermudah pengujian dan eksperimen, tetapi jumlah kode, ukuran biner, dan waktu kompilasi meningkat; DFA hasil kompilasi penuh dijadikan opt-in, dan regex-lite ditambahkan sebagai alternatif ringan

Penulisan ulang regex dan publikasi regex-automata

  • regex crate di Rust ditulis ulang selama bertahun-tahun untuk memperbaiki komposisi internal, memudahkan penambahan optimisasi, dan tetap menjaga ketepatan
  • Dalam proses ini, regex-automata dibuat dan mengekspos sebagian besar implementasi internal crate regex sebagai API terpisah
  • regex-automata diperkenalkan sebagai kasus pertama yang membuka bagian internal library regex sejauh ini sebagai library berversi terpisah
  • regex 1.9 dirilis pada 5 Juli 2023 dan menuntaskan penulisan ulang ini
  • Ditujukan untuk programmer Rust dan orang-orang yang tertarik pada implementasi mesin regex berbasis finite automata, dengan asumsi sudah memiliki pengalaman regex

Masalah-masalah sebelum penulisan ulang

  • Crate regex lama mengikuti tradisi RE2 dan secara internal memakai beberapa strategi pencarian, tetapi karena strategi-strategi itu ditambahkan secara organik, kombinasinya menjadi sulit
    • PikeVM dirancang sebagai strategi pertama, sehingga kurang memiliki penanganan mulai/berhenti pencarian partial slice yang dibutuhkan saat dikombinasikan dengan lazy DFA
    • Sulit menalar strategi mana yang dipakai untuk regex tertentu
    • Beberapa ekspresi match mengimplementasikan logika yang sama berulang kali sehingga mudah tidak sinkron
    • Bahkan untuk regex yang cukup memakai Aho-Corasick saja, Thompson NFA yang tidak akan dipakai bisa tetap dibuat secara tidak perlu
  • Pengujian mesin internal juga rumit
    • API publik terlihat seperti satu mesin regex, tetapi di dalamnya ada banyak strategi yang harus berperilaku sama untuk input yang sama
    • Sebelum regex 1.9, strategi internal bukan API publik sehingga sulit menguji tiap mesin secara terpisah
    • Pengujian lama memiliki struktur yang nyaris berupa hack, bergantung pada eksposur API internal, implementasi From yang tidak didokumentasikan, macro, dan target pengujian per mesin
  • Ada juga banyak permintaan API niche yang sulit dimasukkan ke permukaan API lama
    • RegexSet hanya memberi tahu pola mana yang cocok di suatu bagian haystack, tetapi tidak menyediakan offset match maupun offset capture group
    • Diperlukan kemampuan menjalankan pencarian anchored tanpa menambahkan ^ ke pola
    • Ada kebutuhan untuk mengirim mutable scratch space secara langsung tanpa sinkronisasi internal selama pencarian
    • Ada pula permintaan menjalankan regex pada haystack tidak kontinu seperti stream atau rope
  • Dengan membuka internal sebagai crate berversi terpisah, API regex serbaguna tidak perlu dibuat lebih rumit, sementara API untuk pengguna ahli bisa dieksperimenkan dengan siklus breaking change yang lebih cepat

Batas abstraksi yang dibentuk DFA hasil kompilasi penuh

  • Motivasi awal regex-automata adalah menyediakan runtime minimal yang bisa membuat DFA hasil kompilasi penuh, menserialisasinya, lalu melakukan pencarian lewat deserialisasi zero-copy
  • regex-automata awalnya dipakai untuk membuat DFA bagi implementasi algoritme Unicode di bstr
  • Saat membangun DFA, ternyata dibutuhkan struktur data NFA dan compiler yang mirip dengan crate regex, dan ketika kode ini makin kompleks, kebutuhan untuk berbagi pun meningkat
  • Awalnya sempat dipertimbangkan crate terpisah seperti regex-nfa, tetapi lebih banyak kode—termasuk proses determinisasi—ternyata bisa dibagi antara regex dan regex-automata
  • Batas abstraksinya lebih dekat ke mesin regex daripada sekadar “NFA”, dan pada akhirnya regex-automata didefinisikan ulang sebagai kumpulan beberapa mesin
  • Rencana jangka panjangnya adalah menempatkan semua mesin regex di regex-automata dan menjadikan crate regex sebagai wrapper tipis di atasnya

Melihat struktur internal dengan regex-cli

  • regex-cli adalah program yang dikelola di repositori crate regex, dan menyediakan akses baris perintah ke berbagai API dari regex-syntax, regex-automata, dan regex
  • Instalasinya dapat dilakukan dengan perintah berikut
cargo install regex-cli
  • regex-cli debug dapat menampilkan AST, HIR, literal, Thompson NFA, one-pass DFA, dense DFA, sparse DFA, dan lain-lain
  • Regex . dengan Unicode aktif membuat Thompson NFA yang jauh lebih kompleks untuk menangani UTF-8 scalar value, sedangkan (?-u:.) dengan Unicode nonaktif membuat NFA yang lebih sederhana
  • regex-cli find bisa menjalankan pencarian sementara, dan dengan meta engine juga dapat melakukan pencarian multi-pattern serta menampilkan capture group

Alur data pemrosesan regex

  • String pola yang diberikan ke Regex::new pertama-tama diparse menjadi Ast
  • Ast kemudian diubah menjadi Hir
    • Hir memiliki detail lebih sedikit daripada Ast, dan Unicode case folding serta referensi Unicode character class diperluas selama proses konversi
  • Dari Hir, ada dua hal yang dihasilkan
    • Urutan literal yang dipakai untuk optimisasi pencarian
    • Thompson NFA
  • NFA menjadi dasar untuk membangun berbagai mesin
    • PikeVM: menangani semua regex yang bisa diparse dan melaporkan offset capture group
    • BoundedBacktracker: melaporkan offset capture group dengan bounded backtracking
    • one-pass DFA: pada regex yang terbatas, dapat melaporkan offset capture group dengan cepat
    • dense DFA: sangat cepat tetapi hanya melaporkan awal/akhir full match, dan pembentukannya dalam kasus terburuk memerlukan waktu dan ruang O(2^m)
    • lazy DFA: membangun DFA dari NFA selama pencarian, biasanya secepat full DFA sambil menghindari biaya konstruksi eksponensial dari full DFA
  • Mesin-mesin ini bersama Prefilter digabung menjadi satu meta regex engine, dan crate regex adalah wrapper tipis di atas meta engine tersebut

Optimisasi literal

  • Ekstraksi literal adalah optimisasi inti di dalam regex
    • Misalnya, semua kecocokan dari (foo|bar|quux)(\s+\w+) dimulai dengan salah satu dari foo, bar, atau quux
  • Alasan literal penting adalah karena algoritme pencarian satu string atau sejumlah kecil string sangat cepat
    • Dengan instruksi vektor, beberapa byte dari haystack dapat diproses sekaligus
    • Algoritme pencocokan regex umum sulit dipercepat secara konsisten dengan cara yang sama
  • Pencarian substring yang dioptimalkan dengan baik sering kali setidaknya satu orde magnitudo lebih cepat daripada mesin regex umum
  • Ekstraksi literal bersifat heuristik
    • False positive rate dari kandidat kecocokan harus dikurangi
    • Dampak prefilter terhadap latensi total juga harus rendah
    • Kedua kondisi ini sama-sama bergantung pada haystack, tetapi menganalisis haystack sebelum pencarian dapat memperburuk waktu pencarian total
  • Urutan literal bukan himpunan, melainkan sekuens berurutan
    • crate regex mengikuti semantik leftmost-first ala Perl, sehingga | tidak memenuhi sifat komutatif
    • sam|samwise mungkin hanya mengekstrak sam, tetapi samwise|sam mempertimbangkan keduanya
  • Untuk pencarian satu string, digunakan modul memmem dari crate memchr
    • Algoritme utamanya adalah Two-Way dengan waktu terburuk O(n) dan ruang konstan
    • Rabin-Karp digunakan untuk needle dan haystack yang pendek
    • Pada x86_64, digunakan varian SIMD generik
  • Untuk pencarian banyak string, Teddy yang di-port dari Hyperscan digunakan sebagai algoritme utama, dan dalam beberapa kasus Aho-Corasick juga dipakai

Thompson NFA dan optimisasi

  • Struktur data utama di dalam crate regex adalah Thompson NFA
  • Thompson’s construction membangun NFA dari representasi terstruktur regex dalam waktu O(m), dengan m sebanding dengan ukuran regex setelah ekspansi counted repetition
  • NFA dapat digunakan langsung sebagai mesin regex, dan juga dapat dikonversi ke tipe lain seperti DFA sebagai dasar bagi mesin lain
  • Optimisasi utama pada kompiler NFA baru berfokus pada pengurangan epsilon transition
    • Thompson NFA bagus dari sisi waktu konstruksi, tetapi banyak menggunakan epsilon transition
    • Perhitungan epsilon closure dapat menimbulkan biaya berulang saat pencarian atau selama konstruksi DFA
  • Optimisasi state sparse merepresentasikan banyak transisi rentang dalam satu state untuk mengurangi beberapa instruction Split yang sebelumnya diperlukan
    • Ini menghilangkan epsilon transition yang tidak perlu pada regex seperti [A-Za-z0-9]
    • Dalam representasi saat ini, ada kemungkinan dampak pada cache dan peningkatan heap memory karena indirection
  • Optimisasi minimal UTF-8 automata sangat mengurangi ukuran NFA pada Unicode class yang besar
    • Pada NFA berorientasi byte lama, \w dapat menghasilkan 3.564 state
    • Kompiler baru menggunakan Daciuk’s algorithm untuk membuat struktur dengan jauh lebih sedikit state dan tanpa epsilon transition
    • Penyusutan reverse NFA saat ini dinonaktifkan secara default karena biaya compile time
  • Optimisasi literal trie mengompilasi alternation literal seperti zap|z|zapper, abc|xyz ke trie untuk mengurangi epsilon transition dengan memanfaatkan struktur bersama
    • Untuk mempertahankan semantik leftmost-first, transition chunk dibagi di setiap titik tempat match dapat muncul
  • Pekerjaan NFA ke depan mencakup kajian terhadap Glushkov NFA dan penyimpanan dalam satu contiguous allocation
    • Glushkov NFA tidak memiliki epsilon transition, tetapi kompleksitas compile time-nya lebih buruk
    • Contiguous allocation dapat memberikan cache friendliness dan kemungkinan serialisasi/deserialisasi zero-copy, tetapi ada potensi kompleksitas kode dan penggunaan unsafe

Mesin regex individual

  • Mesin-mesin di regex-automata berbagi API yang serupa
    • Input: mengatur haystack, rentang pencarian, apakah anchored, dan apakah early stop diaktifkan
    • Match: berisi span byte yang cocok dan PatternID
    • MatchError: menunjukkan error ketika hasil pencarian tidak dapat ditentukan

  • PikeVM

    • Mendukung seluruh fitur yang dapat di-parse oleh regex-syntax, dan bekerja pada haystack dengan panjang berapa pun
    • Melacak posisi grup tangkapan dan menghitung state aktif secara lock-step untuk menjamin waktu terburuk O(m * n)
    • Kelemahan utamanya adalah performa, karena harus melacak banyak state dan posisi grup tangkapan
    • Memiliki sifat unik di antara mesin regex-automata, yaitu tidak mengembalikan error selama pencarian

  • BoundedBacktracker

    • Menggunakan backtracking di atas Thompson NFA, tetapi memakai state tambahan agar pekerjaan yang sudah dilakukan tidak dilacak ulang
    • Menjamin waktu terburuk O(m * n), tetapi menggunakan ruang O(m * n)
    • Dalam eksperimen kasar, biasanya sekitar 2 kali lebih cepat daripada PikeVM
    • Dapat gagal jika panjang haystack dan ukuran regex melebihi visited capacity yang telah ditetapkan

  • one-pass DFA

    • Melaporkan offset grup tangkapan dengan sangat cepat pada one-pass NFA yang terbatas
    • Dianggap sebagai cara tercepat untuk melaporkan grup tangkapan
    • Hanya mendukung anchored search, dan banyak regex bukan one-pass
    • Dalam mode Unicode, regex yang bukan one-pass karena overlap transisi level byte dapat menjadi one-pass jika Unicode dimatikan

  • fully compiled DFA

    • Terdiri dari dua DFA, forward DFA dan reverse DFA, untuk menemukan akhir dan awal kecocokan penuh
    • Konstruksinya memiliki waktu dan ruang terburuk O(2^m), dan dense DFA menggunakan banyak memori
    • Mesin full DFA dinonaktifkan secara default di crate regex dan harus diaktifkan secara opt-in melalui feature perf-dfa-full
    • Berjalan tanpa Cache yang mutable, dan dapat diserialisasi sebagai raw bytes sehingga runtime pencarian bisa dipakai bahkan di lingkungan yang hanya memiliki core

  • hybrid NFA/DFA, lazy DFA

    • Mirip dengan full DFA, tetapi membangun transition table selama pencarian
    • Jika transition yang sudah dihitung ada di cache, transition itu digunakan kembali; jika tidak, hanya transition tersebut yang dihitung melalui NFA powerset construction
    • Waktu pencarian terburuk adalah O(m * n), dan ruang dibatasi oleh cache capacity yang ditentukan saat konstruksi
    • Dalam kasus umum, sebagian besar state dan transition tersimpan di cache sehingga perilakunya rata-rata seperti O(n), dan pada praktiknya menunjukkan performa pencarian yang mirip dengan full DFA untuk banyak regex
    • Jika cache berulang kali penuh dan menjadi tidak efisien, mesin ini mengembalikan error, dan pada meta engine biasanya pencarian dicoba ulang dengan mesin lain

Peran meta regex engine

  • meta regex engine bertujuan menyatukan beberapa engine menjadi satu dan menyediakan API yang infallible kepada pemanggil
  • Pemanggil tidak perlu membuat dan meneruskan Cache secara langsung untuk setiap pencarian
    • meta engine mengelola pool cache internal yang thread-safe
    • jika ingin menghindari biaya sinkronisasi, tersedia juga API level lebih rendah yang secara eksplisit menerima Cache
  • regex::Regex, regex::RegexSet, regex::bytes::Regex, regex::bytes::RegexSet semuanya merupakan wrapper tipis dari meta engine
  • Strategi internal meta engine secara garis besar adalah sebagai berikut
    • jika bisa ditangani hanya dengan pencarian substring tunggal atau jamak tanpa regex engine, maka pembuatan NFA juga dihindari
    • jika memungkinkan, mengekstrak urutan literal prefix untuk digunakan sebagai Prefilter
    • jika prefix tidak cocok, mencoba optimisasi reverse anchored, reverse suffix, dan reverse inner
    • selain itu, fallback ke strategi inti yang mencakup PikeVM, bounded backtracker, one-pass DFA, lazy DFA, dan full DFA
  • Seluruh strategi dapat diringkas menjadi dua kalimat
    • sebisa mungkin mencari literal
    • sebisa mungkin menghindari penggunaan PikeVM
  • Optimisasi reverse suffix dan reverse inner dapat menjadi kasus terburuk O(m * n^2) terhadap ukuran haystack jika salah diterapkan
    • meta engine mendeteksi situasi ketika reverse scan hendak melewati akhir match suffix sebelumnya, lalu fallback ke strategi inti untuk mempertahankan jaminan kompleksitas waktu

Perbedaan dengan RE2

  • regex crate dan RE2 memiliki banyak kemiripan
    • RE2 juga memiliki NFA yang setara dengan PikeVM, bitstate backtracker, one-pass NFA, lazy DFA, serta struktur yang menggabungkan beberapa engine
    • dari engine di atas, yang tidak ada di RE2 adalah fully compiled DFA
  • Perbedaan utamanya adalah sebagai berikut
    • RE2 mendukung semantik leftmost-longest ala POSIX sebagai opsi selain leftmost-first
    • dukungan Unicode di RE2 lebih terbatas, dan tidak ada opsi untuk menggunakan \w, \s, \d, \b dengan definisi Unicode
    • dukungan RE2 untuk operasi himpunan character class selain union terbatas
    • PikeVM milik RE2 mungkin lebih efisien dalam penggunaan memori
    • optimisasi literal di RE2 terbatas, dan regex crate melakukan lebih banyak optimisasi literal
    • lazy DFA RE2 membuat beberapa thread berbagi transition cache yang sama sehingga memerlukan sinkronisasi, sedangkan regex crate mewajibkan cache terpisah per thread sehingga memakai lebih banyak memori
    • regex crate merilis regex-syntax dan regex-automata sebagai library terpisah dengan versi sendiri, tetapi RE2 tidak mendukung ini
    • regex-automata mendukung multi-pattern regex sebagai first-class di semua engine, dan juga dapat melaporkan match serta offset capture group dari setiap pola yang cocok

Strategi pengujian dan benchmark

  • Strategi pengujian baru menjadikan engine internal sebagai API first-class yang independen dan menguji setiap engine secara langsung
  • Semua pengujian regex ditentukan dalam file TOML
  • crate regex-test membaca pengujian TOML dan mengubahnya menjadi representasi terstruktur
  • Untuk setiap konfigurasi engine, ada satu Rust unit test yang menjalankan semua pengujian TOML yang berlaku untuk engine tersebut
  • Karena framework Rust unit test tidak dapat diperluas, ditambahkan infrastruktur environment variable khusus untuk memfilter pengujian tertentu
  • Hanya di regex-automata saja ada lebih dari 450 documentation test
  • Dalam persiapan regex 1.9, banyak target fuzz testing juga ditambahkan, dan dengan bantuan Addison Crump ditemukan beberapa bug
  • Benchmark dipublikasikan melalui regex barometer bernama rebar
    • rebar membenchmark tidak hanya regex crate tetapi juga berbagai regex engine lain
    • pada 242 benchmark, regex 1.9 rata-rata 1,5 kali lebih cepat daripada regex 1.7.3 berdasarkan waktu pencarian
    • waktu untuk membangun regex sedikit mengalami regresi
    • 1.8 adalah transition release yang mencakup sebagian pekerjaan migrasi, sehingga 1.7 digunakan sebagai titik pembanding

Biaya dan alternatif ringan

  • Penulisan ulang ini menghabiskan sebagian besar waktu luang penulis selama beberapa tahun terakhir, dan proyek seperti ripgrep sempat tidak bisa dirilis untuk sementara waktu
  • Abstraksi publik yang dapat digunakan ulang cenderung menghasilkan lebih banyak kode dibanding abstraksi yang hanya untuk internal
    • akibatnya, ukuran biner dan waktu kompilasi meningkat
  • Karena API engine internal dipublikasikan sebagai versi terpisah, untuk memecahkan API diperlukan breaking change release yang sesuai dari regex-automata
  • Untuk meredakan biaya, dua langkah diterapkan
    • engine fully compiled DFA dinonaktifkan secara default dan dijadikan feature opt-in
    • regex-lite dirilis sebagai crate baru
  • regex-lite menargetkan hampir menjadi drop-in replacement untuk regex crate, tetapi berfokus pada optimisasi ukuran biner dan waktu kompilasi
    • mengorbankan fitur Unicode dan performa
    • tetap mempertahankan jaminan kompleksitas waktu O(m * n)
    • tidak memiliki dependensi, menyertakan parser regex sendiri, dan tidak berbagi kode dengan regex crate
  • regex-lite masih merupakan langkah mitigasi yang eksperimental, tetapi menunjukkan bahwa meskipun optimisasi dan fitur Unicode dimatikan lewat feature di regex crate, hasilnya tetap sulit mendekati ukuran biner dan waktu kompilasi milik regex-lite

Bacaan terkait

1 komentar

 
GN⁺ 2023-07-06
Komentar Hacker News

  • Baru sekilas membaca saja, crate regex Rust sudah terasa sangat mengesankan
    BurntSushi punya banyak karya hebat, tetapi crate regex Rust itu benar-benar legendaris, dan fakta bahwa ekosistem Rust sudah lama punya pustaka regex yang cepat dan mudah dipakai adalah berkah besar bagi komunitas
    Seri tulisan regex dari Russ Cox juga luar biasa, jadi ketika regex mulai terasa seperti persimpangan sempurna antara teori dan praktik, saya menjadikannya rujukan saat membuat mesin regex selama musim panas
    Perubahan pengujian yang lebih mendalam di tulisan ini juga menarik, dan karena ini crate yang krusial bagi ekosistem, penjelasan tentang topik sedalam ini sangat diapresiasi
    Regex kadang sulit dibaca dan juga sering disalahgunakan untuk hal seperti validasi email, tetapi tetap menjadi salah satu alat paling padat guna di hampir semua bahasa
    Untuk buku praktis, yang saya kenal baik hanya Mastering Regular Expressions karya Jeffrey Friedl, sedangkan sisi teorinya dibahas di buku-buku compiler, dan Dragon Book juga lumayan dari sudut pandang implementasi. Saya penasaran dengan rekomendasi buku regex lainnya

    • https://www.cs.princeton.edu/courses/archive/fall19/cos226/l... dan https://kean.blog/post/lets-build-regex sangat bagus sebagai pengantar implementasi mesin regex yang disederhanakan
      Pendekatannya adalah membuat nondeterministic finite automaton untuk regex, lalu menelusuri graf berarah hasilnya dan menganggapnya cocok jika bisa mencapai simpul yang sesuai dengan keadaan akhir
      Bagi orang yang memakai regex, latihan ini membantu memahami bahwa sebenarnya tidak terlalu banyak “sihir” di baliknya, dan jika membayangkan bola-bola memantul di atas NFA, bug catastrophic backtracking yang akhirnya ditemui di production juga jadi terasa punya makna fisik
      Terkait tulisan aslinya, komentar terakhir BurntSushi di https://github.com/rust-lang/regex/issues/822 menambahkan konteks yang berguna pada paragraf API niche https://blog.burntsushi.net/regex-internals/#problem-request.... Mencari banyak regex sekaligus dalam teks itu sangat rumit tetapi juga sangat berguna, jadi saya menantikan apa yang akan dibangun komunitas dengan pola ini
    • Salah satu contoh khas regex bersinar untuk pekerjaan mirip parsing adalah saat menangani format dengan delimiter yang beragam
      Misalnya format dengan jumlah field tetap seperti header:field1,field2,field3\"data\"hash, atau format seperti suite~split/test1,test2@opt1:opt2^hw1^hw2#flags1#flags2 di mana sebagian besar elemennya opsional; alat dasar seperti split tidak memadai dan regex jauh lebih cocok
      Di sinilah alasan regex cepat menjadi sulit dibaca. Dalam satu regex, delimiter antar-field, validitas tiap field, dan field mana yang opsional semuanya bercampur
      Padahal itu sebenarnya tiga perhatian terpisah, tetapi kebanyakan API regex tidak memungkinkan pemisahan bertahap seperti itu dan hanya menerima satu string gabungan saja
    • Saya penasaran apakah pustaka RegEx ini memakai JIT seperti kebanyakan implementasi JavaScript. Jika tidak, ini bisa jadi salah satu kasus JavaScript mengalahkan Rust
    • Saya baru-baru ini mengerjakan sedikit hal terkait RegEx dan sempat menelusuri tulisan ini; dari fakta bahwa bahasa yang dipakai tampaknya tidak mengembalikan error seperti mesin lain, sepertinya ini memakai PikeVM
      Karena keterbatasan bahasa dan status perlindungan hak cipta, saya harus membangun sendiri fitur RegEx, dan regex kadang benar-benar terasa seperti ilmu voodoo
      Saya tidak tahu seberapa sering mesin lain dipakai, tetapi jika banyak bahasa pemrograman menggunakan PikeVM, saya bisa mengerti mengapa Google membuat OS khusus internal untuk server dan mengerahkan mesin yang lebih cepat dalam situasi tertentu demi menghemat beberapa clock cycle saja
      Saya sangat paham bahwa menambahkan hanya beberapa karakter pada string pencarian bisa sangat memperlambat pattern matching. Pepatah “jaga recehan, nanti uang besarnya menjaga dirinya sendiri” juga sangat cocok untuk RegEx dan clock cycle, dan jika melihat kembali percakapan era 90-an tentang memproses jutaan record per detik, ini mungkin telah membuat beberapa coder menjadi sangat kaya
    • Keluhan terbesar saya adalah perbedaan kecil antar-dialek regex
      Terutama karena cara menangani tanda kutip atau mengakhiri ekspresi sangat berbeda tergantung dialek dan konteksnya, saya sudah menyerah untuk menghafalnya dan memilih mencari contoh setiap kali diperlukan

  • Di ActiveState, saya pernah diberi tugas bersama rekan yang baru lulus kuliah untuk membuat debugger regex bagi editor Komodo
    Kami mempekerjakan pakar Perl legendaris Mark Jason Dominus untuk menanamkan hook ke mesin regex Perl, lalu mengekspos hook itu ke UI agar pengguna bisa melihat eksekusi regex langkah demi langkah
    Sekarang alat berbasis web memang lebih unggul, tetapi pada 2001 Rx Debugger milik Komodo adalah yang terdepan, dan proyek itu juga sangat menyenangkan untuk dikerjakan

    • Saya pernah butuh debugger regex offline
      Saya menangani jaringan air-gapped, jadi orang-orang yang perlu memakai alat ini tidak bisa mengakses situs online, dan dalam desain apa pun, memasukkan data kerja ke alat online sama sekali tidak bisa diterima
      Namun sebagian besar upaya tampaknya terfokus pada alat online, sementara alat offline jarang dan tertinggal dibandingkan yang seperti https://regex101.com/
    • Saya penasaran apakah ada rekomendasi spesifik untuk alat berbasis web yang layak dipakai untuk kebutuhan ini

  • Saya penasaran apakah ini bisa dipakai juga pada list, bukan hanya string
    Ada perangkat yang kuat untuk mencari dan memodifikasi list karakter, tetapi begitu menjadi list angka atau tanggal, semuanya selalu hilang, dan itu terasa menjengkelkan
    Misalnya, jika ingin menemukan semua urutan pada daftar tanggal percobaan login di mana setelah 5 kali atau lebih kegagalan lalu datang keberhasilan, dengan regex itu sederhana, tetapi dalam praktiknya kita harus membuat loop, flag, dan list sementara sendiri
    Kita memang bisa mengubah list menjadi string lalu memprosesnya dan mengembalikannya lagi, tetapi kekurangannya sudah jelas. Meski tidak secepat regex berbasis string, saya tidak mengerti kenapa tidak boleh ada regex untuk tipe list arbitrer
    Saya juga menemukan prototipe Python yang pernah saya buat dulu: https://github.com/boppreh/listregex
    Sangat lambat, tetapi cukup memuaskan sebagai eksperimen API, dan juga menyediakan alat yang tidak ada di regex seperti inversi pola, irisan, dan pencocokan pasangan

    • Tidak bisa. Library regex ini terikat kuat pada pencarian string, dan itu adalah keputusan desain yang disengaja
      Membuat engine regex seperti ini memiliki alfabet generik sejak awal memang terlalu berat. Terutama karena secara realistis sangat sulit dilakukan tanpa merusak desain API dan performa untuk kasus penggunaan utamanya
      Engine regex seperti itu yang tidak terlalu memedulikan performa sebenarnya tidak sulit dibuat. Misalnya, Anda bisa mengambil crate regex-lite yang saya rilis dan mengubahnya menjadi segenerik yang Anda mau, dan dalam prosesnya Anda akan menemui berbagai tantangan menarik
      Bukan berarti hal seperti ini sama sekali tidak ada. Orang-orang pernah mencoba membuatnya[1]. Hanya saja mereka agak melebih-lebihkan kegunaan umumnya, jadi tampaknya biasanya tidak mendapat traction yang besar :-)
      [1]: https://docs.rs/automata/latest/automata/trait.Alphabet.html
    • std::basic_regex di pustaka standar C++ mencoba pendekatan seperti ini dengan mengekspos kelas templat untuk tipe karakter buatan pengguna: https://en.cppreference.com/w/cpp/regex/basic_regex
      Anda bisa menyediakan kelas trait yang mendefinisikan perilaku yang dibutuhkan untuk “karakter” buatan pengguna
      Namun performanya turun drastis, dan kemungkinan hasilnya hanya akan bekerja sebaik memasukkan objek non-karakter arbitrer ke dalam std::basic_string buatan pengguna
    • Entah bagaimana, kita harus mendefinisikan API untuk melakukan matching di atas sliding window dari nilai-nilai
      Ini bukan hal yang mustahil, tetapi kebanyakan bahasa tidak punya antarmuka yang bagus untuk itu

  • Saya memakai Ripgrep setiap hari saat mencari sesuatu di kode atau file teks, dan setiap kali memakainya di Windows, Linux, Mac, VSCode, atau Vim, saya selalu bersyukur
    Ini salah satu perangkat lunak yang mengubah hidup dan cara saya bekerja
    Saat terpaksa memakai grep, rasanya seperti kembali ke masa ketika semua berjalan di CPU satu inti dan datanya ada di hard disk berputar PATA/IDE yang lambat
    BurntSushi pantas mendapat banyak penghormatan di antara para programmer hebat

    • ripgrep punya silsilah. Sebelumnya ada ag, dan sebelumnya lagi ada ack, dan semuanya berusaha menawarkan antarmuka yang jauh lebih baik daripada grep biasa

  • Saya pernah harus membuat RegexSet dengan lebih dari 10 juta regex untuk masalah pekerjaan
    Tidak ada engine yang mampu menanganinya dalam keadaan default, dan RegexSet milik Rust pun tidak cukup dengan pengaturan bawaan
    Meski begitu, menggunakan regex-automata dan regex-syntax sambil membaca kodenya merupakan bahan belajar yang sangat bermanfaat pada 2018
    Pada akhirnya proyek kerja itu dimodelkan dari API Lucene, tetapi hal itu baru mungkin setelah saya mempelajari dasar-dasarnya dari crate regex

    • 10 juta regex adalah skala yang luar biasa. Bahkan Aho-Corasick pun nyaris hanya sanggup menangani 10 juta literal
      Pekerjaan ke depan adalah membuat engine regex bisa melakukan scale dengan lebih baik untuk lebih banyak pola. Saat ini, ia akan runtuh jauh sebelum 10 juta regex, dan saya pun sulit yakin apakah target itu benar-benar memungkinkan
      Meski begitu, jelas masih bisa dibuat lebih baik daripada sekarang
      Tentu saja, untuk pencarian multi-pola, Hyperscan pada dasarnya seperti standar emas. Hanya saja saya tidak tahu seberapa baik ia menangani 10 juta pola
    • Karena Anda tidak menuliskannya dengan detail sejak awal, saya menduga jawabannya “tidak”, tetapi kalau memungkinkan saya penasaran apakah Anda bisa berbagi lebih banyak tentang masalah atau proyek itu

  • Saya pernah bereksperimen dengan crate regex-automata, dan itu satu-satunya library yang bisa dipakai untuk editor teks karena memberi akses langsung ke DFA internal
    API library regex biasa mengasumsikan inputnya adalah satu string kontinu, tetapi pendekatan ini kompatibel dengan struktur data teks apa pun

  • Saya sedang menulis kode yang memakai regex-automata, tepatnya rilisan awal 0.2.0, ketika tulisan ini muncul
    Sepertinya sudah waktunya memeriksa apakah saya perlu menggali ulang struktur internal yang baru
    Saya belum sempat membaca tulisannya, tetapi ini terlihat seperti tulisan yang sangat menarik dengan timing yang pas sekali
    Beberapa menit kemudian, jawabannya tampaknya lebih dekat ke “mungkin”, tetapi karena ini rilisan resmi, sepertinya justru bisa sangat menyederhanakan kode saya
    Sepuluh menit kemudian lagi, ternyata cukup painless, dan metode Builder::patch yang baru adalah peningkatan total
    Sebagai catatan tambahan, saya masih diblokir di semua repositori GitHub Anda, dan mengingat banyak crate Anda dipakai luas, saya rasa itu agak tidak adil. Saya tidak ingat kejadian awalnya. Crate regex itu sendiri tampaknya sekarang berada di bawah organisasi rust-lang, tetapi masih ada hal-hal yang tidak bisa saya interaksikan

    • Dokumentasi regex-automata 0.2.0 punya peringatan besar tentang ini, dan sangat menyarankan memakai 0.1: https://docs.rs/regex-automata/0.2.0/regex_automata/
      Saya juga tidak ingat kejadian awalnya. Saya memblokir banyak orang karena berbagai alasan, tetapi sekarang blokirnya sudah saya buka

  • BioJulia merilis Automa.jl, mesin regex murni Julia yang dapat menyisipkan kode Julia arbitrer pada waktu kompilasi
    Bukan untuk meremehkan fakta bahwa regex milik Rust jauh lebih maju daripada Automa, tetapi saya sulit setuju dengan ungkapan bahwa ini adalah kasus pertama yang mengekspos bagian dalam regex sebagai pustaka

    • Ini terdengar seperti dua hal yang berbeda
      Misalnya, PCRE2 memiliki dukungan “callout” yang terdengar mirip dengan yang dimaksud: https://www.pcre.org/current/doc/html/pcre2callout.html
      Hal seperti ragel atau re2c juga sudah melakukan hal serupa
      Yang dibicarakan blog ini adalah mengambil bagian internal dari pustaka regex itu sendiri, menjadikannya pustaka terpisah yang dikelola versinya secara terpisah, lalu memungkinkan orang lain mengombinasikannya
      Untuk backtracker, pendekatan ini biasanya kurang alami karena mesinnya umumnya hanya punya satu backtracker, tetapi pustaka berbasis automaton sering menggabungkan beberapa mesin dengan berbagai cara
      Meski begitu, bahkan backtracker pun sebenarnya bisa mengekspos hal-hal seperti parser regex atau AST yang biasanya tidak diekspos