Düzenli ifade motorunun içini bir kütüphane olarak sunmak

 (blog.burntsushi.net)
1 puan yazan GN⁺ 2023-07-06 | 1 yorum | WhatsApp'ta paylaş
  • Rust regex crate’i, yıllar süren yeniden yazımın ardından iç motorlarının önemli bir bölümünü ayrı sürümlenen regex-automata crate API’si olarak yayımladı; geçiş regex 1.9 ile tamamlandı
  • Yeniden yazım; arama stratejilerini birleştirme zorluğu, iç motorlara göre test etmenin güçlüğü, RegexSet’ten daha ayrıntılı çoklu desen API’si ihtiyacı ve tam derlenmiş DFA paylaşma gereksiniminden doğdu
  • regex-automata, düzenli ifade işlemeyi Ast → Hir → literal çıkarımı/Prefilter → Thompson NFA → PikeVM·BoundedBacktracker·one-pass DFA·DFA·lazy DFA → meta engine akışıyla kuruyor
  • Performans, mümkün olduğunda önce literal arama ve DFA ailesi motorları kullanılarak; capture group’lar veya istisnai durumlarda ise PikeVM·bounded backtracker·one-pass DFA ile tamamlanarak sağlanıyor
  • Açık API ve yeniden kullanılabilir soyutlamalar test ve deneyi kolaylaştırdı; ancak kod miktarı, ikili dosya boyutu ve derleme süresi arttı. Tam derlenmiş DFA opt-in bırakıldı ve regex-lite hafif bir alternatif olarak eklendi

regex yeniden yazımı ve regex-automatanın yayımlanması

  • Rust’ın regex crate’i, iç bileşimi iyileştirip optimizasyonları daha kolay eklerken doğruluğu korumak için yıllar boyunca yeniden yazıldı
  • Bu süreçte regex-automata oluşturuldu ve regex crate’inin iç uygulamasının önemli bir kısmı ayrı bir API olarak açığa çıkarıldı
  • regex-automata, bir düzenli ifade kütüphanesinin içini bu ölçüde ayrı sürümlenen bir kütüphane olarak yayımlayan ilk örnek olarak tanıtılıyor
  • regex 1.9, 5 Temmuz 2023’te yayımlandı ve bu yeniden yazımı tamamladı
  • Hedef kitle, Rust programcıları ve sonlu otomat tabanlı düzenli ifade motorlarının uygulanmasıyla ilgilenen kişiler; düzenli ifade deneyimi ön kabul olarak alınıyor

Yeniden yazımdan önceki sorunlar

  • Mevcut regex crate’i, RE2 geleneğini izleyerek içeride birden fazla arama stratejisi kullanıyordu; ancak stratejiler zamanla organik biçimde eklendikçe birleştirilmesi zorlaştı
    • PikeVM, ilk strateji olarak tasarlandığından lazy DFA ile birleştirildiğinde gereken kısmi slice araması başlatma ve durdurma işlemlerinde eksikti
    • Hangi düzenli ifadede hangi stratejinin kullanıldığını çıkarsamak zordu
    • Birden fazla match ifadesi aynı mantığı tekrar tekrar uyguluyor, bu da senkronizasyonun kolayca bozulmasına yol açıyordu
    • Sadece Aho-Corasick yeterli olan düzenli ifadelerde bile kullanılmayacak Thompson NFA gereksiz yere oluşturulabiliyordu
  • İç motorları test etmek de zordu
    • Açık API tek bir düzenli ifade motoru gibi görünse de içeride birden çok strateji var ve bunların aynı girdide aynı şekilde çalışması gerekiyor
    • regex 1.9 öncesinde iç stratejiler açık API değildi; bu yüzden her motoru bağımsız test etmek zordu
    • Mevcut testler, iç API açığa çıkarma, belgelenmemiş From implementasyonları, makrolar ve motor bazlı test hedeflerine dayanan, hack’e yakın bir yapıya sahipti
  • Çeşitli niş API taleplerini de mevcut API yüzeyine eklemek zordu
    • RegexSet, yalnızca hangi desenlerin haystack’in herhangi bir yerinde eşleştiğini bildiriyor; eşleşme ofsetlerini veya capture group ofsetlerini vermiyor
    • Desene ^ eklemeden anchored arama çalıştırma işlevine ihtiyaç vardı
    • Arama sırasında iç senkronizasyon olmadan mutable scratch space’i doğrudan iletme özelliği talep ediliyordu
    • Stream veya rope gibi süreksiz haystack üzerinde düzenli ifade çalıştırma işlevi de istendi
  • İç yapının ayrı sürümlenen bir crate olarak açılması, genel amaçlı regex API’sini karmaşıklaştırmadan uzmanlara yönelik API’lerin daha hızlı bir breaking change döngüsüyle denenmesini mümkün kılıyor

Tam derlenmiş DFA’nın oluşturduğu soyutlama sınırı

  • regex-automatanın ilk motivasyonu, tam derlenmiş bir DFA oluşturup bunu serileştirdikten sonra zero-copy deserileştirme ile arama yapan en küçük çalışma zamanı altyapısını sunmaktı
  • İlk regex-automata, bstr için Unicode algoritmalarını uygulayan DFA’lar üretmekte kullanıldı
  • DFA oluşturulurken, regex crate’ine benzer NFA veri yapıları ve derleyicilere ihtiyaç duyuldu; bu kod karmaşıklaştıkça paylaşım ihtiyacı büyüdü
  • Başta regex-nfa gibi ayrı bir crate düşünülse de determinization süreci gibi daha fazla kod regex ile regex-automata arasında paylaşılabilirdi
  • Soyutlama sınırı “NFA”dan çok düzenli ifade motoruna yakındı ve sonunda regex-automata birden fazla motorun kümesi olarak yeniden tanımlandı
  • Uzun vadeli plan, tüm düzenli ifade motorlarını regex-automata içine koyup regex crate’ini bunun üzerinde ince bir wrapper’a dönüştürmekti

regex-cli ile iç yapıyı incelemek

  • regex-cli, regex crate deposunda yönetilen bir programdır ve regex-syntax, regex-automata, regex için çeşitli API’lere komut satırından erişim sağlar
  • Kurulum şu komutla yapılabilir
cargo install regex-cli
  • regex-cli debug, AST, HIR, literal’lar, Thompson NFA, one-pass DFA, dense DFA, sparse DFA ve benzerlerini çıktıya dökebilir
  • Unicode açıkken kullanılan . düzenli ifadesi, UTF-8 scalar value’ları işlemek için çok daha karmaşık bir Thompson NFA üretirken; Unicode kapalı (?-u:.) daha basit bir NFA oluşturur
  • regex-cli find, geçici aramalar çalıştırabilir; ayrıca meta engine ile çoklu desen araması ve capture group çıktısı da verebilir

Düzenli ifade işleme veri akışı

  • Regex::new içine verilen desen dizgesi önce Ast olarak parse edilir
  • Ast, ardından Hir biçimine dönüştürülür
    • Hir, Ast’ye göre daha az ayrıntı içerir; Unicode case folding ve Unicode character class referansları bu dönüşüm sırasında genişletilir
  • Hir’den iki şey üretilir
    • Arama optimizasyonunda kullanılan literal dizileri
    • Thompson NFA
  • NFA, çeşitli motorları üretmenin temelini oluşturur
    • PikeVM: parse edilebilen tüm düzenli ifadeleri işler ve capture group ofsetlerini bildirir
    • BoundedBacktracker: bounded backtracking ile capture group ofsetlerini bildirir
    • one-pass DFA: sınırlı düzenli ifadelerde capture group ofsetlerini hızlıca bildirir
    • dense DFA: çok hızlıdır, ancak yalnızca tüm eşleşmenin başlangıç ve bitişini bildirir; oluşturulması en kötü durumda O(2^m) zaman ve alan gerektirir
    • lazy DFA: arama sırasında NFA’den DFA oluşturur; genellikle full DFA kadar hızlıdır ve full DFA’nın üstel oluşturma maliyetinden kaçınır
  • Bu motorlar ile Prefilter, tek bir meta regex engine içinde birleştirilir; regex crate’i de bu meta engine’in ince bir wrapper’ıdır

Literal optimizasyonu

  • Literal çıkarımı, regex içindeki temel optimizasyonlardan biridir
    • Örneğin (foo|bar|quux)(\s+\w+) için tüm eşleşmeler foo, bar veya quux ile başlar
  • Literal'lerin önemli olmasının nedeni, tek bir veya az sayıda dizge arama algoritmasının çok hızlı olmasıdır
    • Vektör komutlarıyla haystack içindeki birden çok bayt aynı anda işlenebilir
    • Genel düzenli ifade eşleştirme algoritmalarını aynı şekilde tutarlı biçimde hızlandırmak zordur
  • İyi optimize edilmiş substring araması, genel bir düzenli ifade motorundan çoğu zaman en az tek haneli katlar düzeyinde daha hızlı olmuştur
  • Literal çıkarımı bir heuristictir
    • Aday eşleşmelerin false positive oranını düşürmek gerekir
    • Prefilter'ın toplam gecikmeye etkisi de düşük tutulmalıdır
    • Her iki koşul da haystack'e bağlıdır, ancak aramadan önce haystack'i analiz etmek toplam arama süresini kötüleştirebilir
  • Literal dizisi bir küme değil, sıralı bir dizidir
    • regex crate'i Perl benzeri leftmost-first semantiğini izlediği için | için değişme özelliği geçerli değildir
    • sam|samwise için yalnızca sam çıkarılabilirken, samwise|sam için ikisi de dikkate alınır
  • Tek dizge araması için memchr crate'inin memmem modülü kullanılır
    • Ana algoritma, en kötü durumda O(n) zaman ve sabit alan kullanan Two-Way'dir
    • Kısa needle ve haystack için Rabin-Karp kullanılır
    • x86_64 üzerinde generic SIMD varyantı kullanılır
  • Çoklu dizge aramasında ana algoritma olarak Hyperscan'den taşınan Teddy kullanılır; bazı durumlarda Aho-Corasick de kullanılır

Thompson NFA ve optimizasyonlar

  • regex crate'i içindeki merkezi veri yapısı Thompson NFA'dir
  • Thompson’s construction, düzenli ifadenin yapılandırılmış gösteriminden O(m) zamanda bir NFA üretir; burada m, counted repetition genişletildikten sonraki düzenli ifade boyutuyla orantılıdır
  • NFA doğrudan bir düzenli ifade motoru olarak kullanılabilir ve DFA gibi başka türlere dönüştürülerek diğer motorların temeli de olabilir
  • Yeni NFA derleyicisindeki başlıca optimizasyon, epsilon transition sayısını azaltmaya odaklanır
    • Thompson NFA'nin kurulum maliyeti iyidir, ancak çok sayıda epsilon transition kullanır
    • Epsilon closure hesaplaması, arama veya DFA oluşturma sırasında tekrarlayan bir maliyet yaratabilir
  • sparse state optimizasyonu, birden fazla aralık geçişini tek bir durumda ifade ederek mevcut çok sayıdaki Split instruction'ı azaltır
    • [A-Za-z0-9] gibi düzenli ifadelerde gereksiz epsilon transition'ları kaldırır
    • Mevcut gösterimde indirection nedeniyle cache etkisi ve heap memory artışı ihtimali vardır
  • Minimal UTF-8 automata optimizasyonu, büyük Unicode class'larda NFA boyutunu önemli ölçüde küçültür
    • Eski byte-oriented NFA'de \w, 3.564 state oluşturabiliyordu
    • Yeni derleyici, Daciuk’s algorithm kullanarak çok daha az state ve sıfır epsilon transition içeren bir yapı oluşturur
    • Reverse NFA'nin küçültülmesi, compile time maliyeti nedeniyle varsayılan olarak devre dışıdır
  • Literal trie optimizasyonu, zap|z|zapper, abc|xyz gibi literal alternation'larda ortak yapıyı trie olarak derleyip epsilon transition'ları azaltır
    • Leftmost-first semantiğini korumak için eşleşmenin göründüğü her noktada transition chunk'ları bölünür
  • Gelecekteki NFA çalışmaları arasında Glushkov NFA ve tek bir contiguous allocation içinde depolama değerlendirilmektedir
    • Glushkov NFA'de epsilon transition yoktur, ancak compile time karmaşıklığı daha kötüdür
    • Contiguous allocation, cache dostu yapı ve zero-copy serileştirme/deserialize etme imkânı sunabilir; ancak kod karmaşıklığı ve unsafe kullanımı ihtimali vardır

Ayrı düzenli ifade motorları

  • regex-automata motorları benzer API'leri paylaşır
    • Input: haystack, arama aralığı, anchored olup olmadığı ve early stop ayarlanır
    • Match: eşleşen byte span'ini ve PatternID içerir
    • MatchError: arama sonucunun belirlenemediği hataları gösterir

  • PikeVM

    • regex-syntax tarafından ayrıştırılabilen tüm özellikleri destekler ve her uzunluktaki haystack üzerinde çalışır
    • Capture group konumlarını izler ve etkin state'leri lock-step olarak hesaplayarak en kötü durumda O(m * n) zamanı garanti eder
    • Çok sayıda state ve capture group konumunun izlenmesi gerektiğinden performans temel zayıf noktasıdır
    • regex-automata motorları arasında, arama sırasında hata döndürmeyen tek motordur

  • BoundedBacktracker

    • Thompson NFA üzerinde backtracking kullanır, ancak daha önce yapılan işi yeniden izlememek için ek state kullanır
    • En kötü durumda O(m * n) zamanı garanti eder, ancak O(m * n) alan kullanır
    • Kabaca yapılan deneylerde genellikle PikeVM'den yaklaşık 2 kat daha hızlıdır
    • Haystack uzunluğu ve düzenli ifade boyutu, ayarlanan visited capacity'yi aşarsa başarısız olabilir

  • one-pass DFA

    • Kısıtlı bir one-pass NFA üzerinde capture group offset'lerini çok hızlı raporlar
    • Capture group'ları raporlamanın en hızlı yolu olarak görülür
    • Yalnızca anchored search desteklenir ve birçok düzenli ifade one-pass değildir
    • Unicode modunda byte düzeyi transition çakışmaları nedeniyle one-pass olmayan bir düzenli ifade, Unicode kapatıldığında one-pass olabilir

  • fully compiled DFA

    • Bir eşleşmenin sonunu ve başlangıcını bulmak için bir forward DFA ve bir reverse DFA'den oluşur
    • Oluşturma en kötü durumda O(2^m) zaman ve alan gerektirir; dense DFA ise çok bellek kullanır
    • Full DFA motoru, regex crate'inde varsayılan olarak devre dışıdır; perf-dfa-full feature'ı ile isteğe bağlı olarak etkinleştirilmelidir
    • Değiştirilebilir bir Cache olmadan çalışır ve ham baytlara serileştirilerek yalnızca core bulunan ortamlarda da arama çalışma zamanı kullanılabilir

  • hybrid NFA/DFA, lazy DFA

    • Full DFA'ye benzer, ancak transition table'ı arama sırasında oluşturur
    • Cache'te önceden hesaplanmış bir transition varsa yeniden kullanır; yoksa NFA powerset construction ile yalnızca ilgili transition'ı hesaplar
    • En kötü arama süresi O(m * n), alan kullanımı ise oluşturma sırasında belirlenen cache capacity ile sınırlıdır
    • Genel durumda state ve transition'ların çoğu cache'lendiği için ortalamada O(n) gibi çalışır ve pratikte birçok düzenli ifadede full DFA'ye benzer arama performansı gösterir
    • Cache tekrar tekrar dolup verimsiz hâle gelirse hata döndürür; meta engine içinde ise genellikle başka bir motorla yeniden denenir

meta regex enginein rolü

  • meta regex engine, birden çok motoru tek bir yapıda birleştirir ve çağırana hatasız bir API sunmayı amaçlar
  • Çağıranın her arama için doğrudan Cache oluşturup geçirmesi gerekmez
    • meta engine, dahili thread-safe bir cache havuzunu yönetir
    • senkronizasyon maliyetinden kaçınmak istenirse, açıkça Cache geçirilen daha alt seviye bir API de sunulur
  • regex::Regex, regex::RegexSet, regex::bytes::Regex, regex::bytes::RegexSet yapılarının tümü meta engine için ince birer sarmalayıcıdır
  • meta engine'in dahili stratejisi kabaca şöyledir
    • Regex motoru olmadan yalnızca tekli veya çoklu substring aramasıyla çözülebiliyorsa NFA kurulumundan da kaçınır
    • Mümkünse prefix literal dizilerini çıkarıp bunları Prefilter olarak kullanır
    • Prefix uygun değilse reverse anchored, reverse suffix ve reverse inner optimizasyonlarını dener
    • Bunların dışında PikeVM, bounded backtracker, one-pass DFA, lazy DFA ve full DFA içeren çekirdek stratejiye geri düşer
  • Genel strateji iki cümlede özetlenebilir
    • Mümkün olduğunca literal ara
    • Mümkün olduğunca PikeVM kullanımından kaçın
  • reverse suffix ve reverse inner optimizasyonları yanlış uygulanırsa haystack boyutu için en kötü durumda O(m * n^2) olabilir
    • meta engine, reverse scan'in önceki suffix eşleşmesinin sonunu aşmaya çalıştığı durumu tespit eder ve zaman karmaşıklığı garantisini korumak için çekirdek stratejiye geri döner

RE2 ile farklar

  • regex crate'i ile RE2 arasında birçok benzerlik vardır
    • RE2'de de PikeVM karşılığı bir NFA, bitstate backtracker, one-pass NFA, lazy DFA ve birden çok motoru birleştiren bir yapı bulunur
    • Yukarıdaki motorlar arasında RE2'de olmayan tek şey fully compiled DFA'dır
  • Başlıca farklar şunlardır
    • RE2, leftmost-first'e ek olarak POSIX tarzı leftmost-longest anlambilimini de isteğe bağlı olarak destekler
    • RE2'nin Unicode desteği daha sınırlıdır ve \w, \s, \d, \b için Unicode tanımlarını kullanma seçeneği yoktur
    • RE2, character class set operation işlemlerinde union dışındaki destek konusunda sınırlıdır
    • RE2'nin PikeVM uygulaması bellek açısından daha verimli olabilir
    • RE2'nin literal optimizasyonları sınırlıdır; regex crate'i daha fazla literal optimizasyonu yapar
    • RE2 lazy DFA'sında birden çok thread aynı transition cache'i paylaşır, bu yüzden senkronizasyon gerekir; regex crate'i ise thread başına ayrı cache ister ve bu nedenle daha fazla bellek kullanır
    • regex crate'i, regex-syntax ve regex-automatayı ayrı sürümlenen kütüphaneler olarak yayımlar, RE2 ise bunu desteklemez
    • regex-automata, tüm motorlarda birinci sınıf multi-pattern regex desteği sunar ve eşleşen her pattern için match ile capture group offset'lerini de raporlayabilir

Test stratejisi ve benchmark'lar

  • Yeni test stratejisi, dahili motorları bağımsız birer birinci sınıf API haline getirip her motoru doğrudan test etmeye dayanır
  • Tüm regex testleri TOML dosyalarıyla tanımlanır
  • regex-test crate'i, TOML testlerini okuyup yapılandırılmış bir gösterime dönüştürür
  • Her motor yapılandırması için bir Rust unit test'i bulunur ve o motora uygulanabilen tüm TOML testleri çalıştırılır
  • Rust unit test çerçevesi genişletilebilir olmadığından, belirli testleri filtrelemek için özel environment variable altyapısı eklenmiştir
  • Yalnızca regex-automata içinde 450'den fazla documentation test bulunur
  • regex 1.9 hazırlıkları sırasında çok sayıda fuzz testing hedefi de eklendi ve Addison Crump'ın yardımıyla birkaç hata bulundu
  • Benchmark'lar, rebar adlı regex barometer ile yayımlanır
    • rebar, yalnızca regex crate'ini değil, çeşitli regex motorlarını da benchmark eder
    • 242 benchmark'ta regex 1.9, arama süresi açısından regex 1.7.3e göre ortalama 1,5 kat daha hızlıdır
    • Regex derleme süresi ise bir miktar gerilemiştir
    • 1.8, bazı geçiş çalışmalarını içeren bir transition release olduğundan karşılaştırma temeli olarak 1.7 kullanılmıştır

Maliyet ve hafif alternatifler

  • Yeniden yazım için son birkaç yılda yazarın boş zamanının büyük kısmı harcandı ve ripgrep gibi projeler bir süre yayımlanamadı
  • Yeniden kullanılabilir kamuya açık soyutlamalar, yalnızca dahili kullanıma yönelik soyutlamalara göre daha fazla kod gerektirme eğilimindedir
    • Bunun sonucunda binary boyutu ve derleme süresi artar
  • Dahili motor API'si ayrı sürümlenen şekilde yayımlandığından, API'yi bozmak için regex-automata tarafında uygun bir breaking change release gerekir
  • Maliyeti hafifletmek için iki önlem uygulanmıştır
    • fully compiled DFA motoru varsayılan olarak devre dışıdır ve isteğe bağlı bir feature olarak bırakılmıştır
    • regex-lite yeni bir crate olarak yayımlanmıştır
  • regex-lite, regex crate'inin neredeyse drop-in replacement'ı olmayı hedefler; ancak odağı binary boyutu ve derleme süresini optimize etmektir
    • Unicode ve performans tarafındaki bazı özelliklerden vazgeçer
    • O(m * n) zaman karmaşıklığı garantisini korur
    • Hiç bağımlılığı yoktur, kendi regex parser'ını içerir ve regex crate'iyle kod paylaşmaz
  • regex-lite şimdilik deneysel bir hafifletme yöntemi olsa da, regex crate'inde feature'lar üzerinden optimizasyon ve Unicode işlevleri kapatılsa bile binary boyutu ve derleme süresinde regex-lite seviyesine yaklaşmanın zor olduğunu gösterir

İlgili okumalar

1 yorum

 
GN⁺ 2023-07-06
Hacker News yorumları

  • Sadece kabaca göz atmış olsam da Rust regex crate gerçekten çok etkileyici
    BurntSushi'nin yaptığı harika işler çok ama Rust'ın regex crate'i efsanevi; Rust ekosisteminin uzun zamandır performanslı ve kullanımı kolay bir düzenli ifade kütüphanesine sahip olması topluluk için büyük bir nimet
    Russ Cox'un düzenli ifadeler üzerine yazı dizisi de harika; düzenli ifadeler teoriyle pratiğin kusursuz kesişim noktası gibi gelmeye başladığında yaz boyunca bir düzenli ifade motoru yaparken ona başvurmuştum
    Bu yazıdaki daha derin test değişiklikleri de ilginç ve ekosistem için çekirdek bir crate olduğu düşünülürse bu kadar derin konuların açıklanması takdire değer
    Düzenli ifadeler bazen okunması zor olabilir ve e-posta doğrulama gibi yerlerde fazla kullanılabilir ama neredeyse her dilde en yoğun araçlardan biridir
    Pratik tarafta Jeffrey Friedl'in Mastering Regular Expressions kitabını iyi biliyorum; teori tarafınıysa derleyici kitapları ele alıyor ve Dragon Book da uygulama perspektifinden fena değildi. Başka düzenli ifade kitabı önerilerini merak ediyorum

    • https://www.cs.princeton.edu/courses/archive/fall19/cos226/l... ve https://kean.blog/post/lets-build-regex basitleştirilmiş bir düzenli ifade motoru gerçekleştirimine giriş için harika
      Yaklaşım, düzenli ifade için bir deterministik olmayan sonlu otomat kurup ortaya çıkan yönlü grafikte arama yapmak ve son durumlara karşılık gelen düğümlere ulaşılabiliyorsa bunu eşleşme saymak
      Düzenli ifade kullanan biri için bu alıştırma işin sanıldığından daha az sihirli olduğunu anlamaya yardımcı oluyor; NFA üzerinde sekip duran topları hayal edince üretimde eninde sonunda karşınıza çıkan felaket düzeyinde backtracking hataları da fiziksel bir anlam kazanıyor
      Asıl yazıyla ilgili olarak, https://github.com/rust-lang/regex/issues/822 içindeki son BurntSushi yorumu, niş API paragrafına https://blog.burntsushi.net/regex-internals/#problem-request... faydalı bir bağlam ekliyor. Birden fazla düzenli ifadeyi metin üzerinde aynı anda aramak çok karmaşık ama çok faydalı; topluluğun bu kalıpla neler inşa edeceğini merakla bekliyorum
    • Düzenli ifadelerin ayrıştırmaya benzer işlerde parladığı tipik örnek, ayraçları çeşitlenen biçimler ile uğraşmaktır
      Örneğin header:field1,field2,field3"data"hash gibi alan sayısı sabit biçimlerde ya da suite~split/test1,test2@opt1:opt2^hw1^hw2#flags1#flags2 gibi öğelerin çoğunun isteğe bağlı olduğu biçimlerde split gibi temel araçlar yetersiz kalır ve düzenli ifadeler iyi oturur
      Düzenli ifadelerin neden hızla okunamaz hâle geldiğinin sebebi de budur. Tek bir düzenli ifadeye alanlar arası ayraçlar, her alanın geçerliliği ve hangi alanların isteğe bağlı olduğu birden yüklenir
      Oysa bunlar aslında üç ayrı ilgidir ama çoğu regex API'si bunları aşamalı olarak ayırmaya izin vermez, her şeyi birleştiren tek bir string vermenizi ister
    • Bu RegEx kütüphanesinin, çoğu JavaScript gerçekleştiriminde olduğu gibi JIT kullanıp kullanmadığını merak ediyorum. Kullanmıyorsa JavaScript'in Rust'ı geçtiği örneklerden biri olabilir
    • Yakın zamanda biraz RegEx işi yaparken bu yazıya göz gezdirdim; kullanılan dilin diğer motorlardan farklı olarak hata döndürmemesine bakılırsa sanırım PikeVM kullanıyor
      Dil kısıtları ve telif hakkı koruması nedeniyle RegEx işlevini doğrudan yeniden yapmak zorunda kaldım ve düzenli ifadeler gerçekten bazen büyü gibi hissettiriyor
      Diğer motorların ne kadar sık kullanıldığını bilmiyorum ama pek çok programlama dili PikeVM kullanıyorsa, Google'ın sunucuları için kendi işletim sistemini yapıp belirli durumlarda daha hızlı motorları devreye sokarak birkaç clock cycle bile kazanmaya çalışmasını anlayabiliyorum
      Arama string'ine birkaç karakter eklemenin bile pattern matching'i ciddi biçimde yavaşlatabildiğini gayet iyi biliyorum. “Damlaya damlaya göl olur” sözü RegEx ve clock cycle için de çok uygun; saniyede milyonlarca kaydın işlendiği 90'lar sohbetlerine bakınca bunun bazı kodlayıcıları epey zengin etmiş olabileceğini düşünmeden edemiyorum
    • En büyük şikâyetim düzenli ifade lehçeleri arasındaki küçük farklar
      Özellikle lehçeye ve bağlama göre tırnak işleme ya da ifadenin nasıl sonlandığı o kadar değişiyor ki ezberlemeye çalışmayı bıraktım; ihtiyaç oldukça örnek arıyorum

  • ActiveState'de okuldan yeni mezun olmuş bir çalışma arkadaşımla birlikte Komodo editörü için bir düzenli ifade hata ayıklayıcısı yapma görevi almıştım
    Efsanevi Perl uzmanı Mark Jason Dominus'u işe alıp Perl düzenli ifade motoruna hook'lar eklettik ve bu hook'ları UI'da görünür kılarak kullanıcının düzenli ifade çalışmasını adım adım izlemesini sağladık
    Bugünlerde web tabanlı araçlar daha iyi olsa da 2001'de Komodo'nun Rx Debugger'ı son teknoloji sayılırdı ve üzerinde çalışması da çok eğlenceliydi

    • Geçmişte çevrimdışı bir düzenli ifade hata ayıklayıcısına ihtiyaç duymuştum
      Air-gap ağlarla çalışıyordum; bu yüzden araçları kullanması gereken kişiler çevrimiçi sitelere erişemiyordu ve hangi tasarım olursa olsun iş verilerini çevrimiçi araçlara koymak düşünülemezdi
      Ama çabaların çoğu çevrimiçi araçlara gidiyor; çevrimdışı araçlar ise https://regex101.com/ gibi şeylerle karşılaştırıldığında nadir ve yetersiz kalıyor
    • Bu amaç için kullanılabilecek belirli web tabanlı araç önerilerini merak ediyorum

  • Bunun string olmayan listelerde de kullanılıp kullanılamayacağını merak ediyorum
    Karakter listelerini arayıp değiştirmek için güçlü araçlar var ama konu sayı ya da tarih listelerine gelince hepsinin bir anda ortadan kaybolması hep can sıkıcı gelmiştir
    Örneğin giriş denemesi tarihleri listesindeki, 5 veya daha fazla başarısız denemenin ardından başarı gelen tüm dizileri bulmak istesem, regex ile bu basit olurdu; ama pratikte elle döngü, bayraklar ve geçici listeler kurmak gerekiyor
    Listeleri string'e çevirip işledikten sonra geri dönüştürmek de mümkün, ama bunun dezavantajları açık. String tabanlı regex kadar hızlı olmasa bile, rastgele liste türleri için bir regex neden olmasın anlamıyorum
    Eskiden yaptığım Python prototipini de buldum: https://github.com/boppreh/listregex
    Çok yavaş ama API deneyi olarak tatmin edici ve desen tersleme, kesişim, eşleştirme gibi regex'te olmayan araçlar da sunuyor

    • Olmaz. Bu regex kütüphanesi string aramaya sıkı sıkıya bağlı ve bu kasıtlı bir tasarım kararı
      Böyle bir regex motoruna jenerik bir alfabe kazandırmak en baştan gerçekçi değil. Özellikle de API tasarımına ve ana kullanım senaryolarındaki performansa zarar vermeden bunu yapmak pratikte fazlasıyla zor
      Performansı önemsemeyen böyle bir regex motoru yapmak zor değil. Örneğin yayımladığım regex-lite crate'ini alıp istediğiniz kadar jenerik hale getirebilirsiniz; bu süreçte de ilginç zorluklarla karşılaşırsınız
      Böyle şeyler tamamen yok değil. İnsanlar bunu yapmaya çalışıyor[1]. Ancak genel faydasını biraz abarttıkları için genelde büyük traction elde edemiyor gibi görünüyor :-)
      [1]: https://docs.rs/automata/latest/automata/trait.Alphabet.html
    • C++ standart kütüphanesindeki std::basic_regex, kullanıcı tanımlı karakter tipleri için bir şablon sınıfı sunarak bunu deniyor: https://en.cppreference.com/w/cpp/regex/basic_regex
      Kullanıcı tanımlı “karakter” için gerekli davranışları tanımlayan trait sınıfları sağlayabiliyorsunuz
      Ama performans ciddi biçimde düşüyor ve bu yaklaşım muhtemelen karakter olmayan rastgele nesneleri kullanıcı tanımlı bir std::basic_string içine koymak kadar iyi çalışıyor
    • Değerlerin sliding window'ları üzerinde eşleşen bir API'yi bir şekilde tanımlamak gerekir
      İmkansız değil ama çoğu dil bunun için iyi bir arayüz sunmuyor

  • Kodda ya da metin dosyalarında bir şey ararken Ripgrep'i her gün kullanıyorum; Windows, Linux, Mac, VSCode, Vim fark etmeksizin her kullandığımda minnet duyuyorum
    Hayatımı ve çalışma biçimimi değiştiren yazılımlardan biri
    Zorla grep kullanmak zorunda kaldığımda, her şeyin tek çekirdekli CPU'da çalıştığı ve verilerin yavaş PATA/IDE döner disklerde bulunduğu döneme geri dönmüşüm gibi geliyor
    BurntSushi, büyük programcılar arasında fazlasıyla saygıyı hak ediyor

    • ripgrep'in bir soyu var. Ondan önce ag, ondan önce de ack vardı ve hepsi basit grepten çok daha iyi bir arayüz sunmaya çalışıyordu

  • İşle ilgili bir problem yüzünden 10 milyondan fazla çok uzun regex ile bir RegexSet oluşturmam gerekti
    Hiçbir motor varsayılan ayarlarla bununla başa çıkamadı; Rust'ın RegexSeti de varsayılan haliyle yeterli değildi
    Yine de regex-automata ve regex-syntax kullanmak ve kodu okumak, 2018'de bile çok faydalı bir öğrenme kaynağıydı
    Sonunda iş projesi Lucene API'sini model aldı ama bunu yapabilmemin temeli regex crate'lerinden öğrendiklerimdi

    • 10 milyon regex muazzam bir ölçek. Aho-Corasick bile 10 milyon literal'i ancak kaldırır
      Bundan sonraki iş, regex motorlarını daha fazla desenle daha iyi ölçeklenecek hale getirmek. Şu anda 10 milyon regex'e gelmeden çok önce çökerdi ve bu hedefin gerçekten mümkün olup olmadığından bile emin olmak zor
      Yine de bugünkünden daha iyi olabilir
      Elbette çoklu desen aramada Hyperscan fiilen altın standart. Ama 10 milyon deseni ne kadar iyi işler, bilmiyorum
    • En başta ayrıntılı yazılmamış olmasına bakılırsa cevap muhtemelen “hayır”; ama mümkünse bunun ne tür bir sorun ya da proje olduğunu biraz daha paylaşabilir misiniz merak ediyorum

  • Eskiden regex-automata crate'iyle denemeler yapmıştım; iç DFA'ya doğrudan erişim verdiği için bir metin editöründe kullanabildiğim tek kütüphaneydi
    Tipik regex kütüphanesi API'leri girdinin tek ve kesintisiz bir string olduğunu varsayar, ama bu yaklaşım herhangi bir metin veri yapısıyla uyumlu

  • regex-automata crate'inin kodunu, üstelik ilk 0.2.0 sürümünü kullanan kod yazarken bu yazı çıktı
    Görünüşe göre yeni iç yapıyı yeniden inceleme zamanı gelmiş
    Yazıyı henüz okumadım ama çok ilginç ve zamanlaması da kusursuz bir yazı gibi görünüyor
    Birkaç dakika sonra bakınca cevap “olabilir”e daha yakındı, ama resmi sürüm olduğu için kodu ciddi ölçüde sadeleştirebileceğim gibi duruyordu
    Bir 10 dakika daha sonra geçiş oldukça painless oldu ve yeni Builder::patch metodu tam bir yükseltmeydi
    Not olarak, hâlâ tüm GitHub depolarınızda engelliyim; pek çok crate'in yaygın kullanıldığı düşünülürse bu biraz haksız geliyor. Asıl olayı hatırlamıyorum. regex crate'lerinin kendisi artık rust-lang organizasyonu altında gibi görünüyor ama yine de etkileşime giremediğim şeyler var

    • regex-automata 0.2.0 belgelerinde bununla ilgili büyük bir uyarı vardı ve 0.1 kullanılması şiddetle tavsiye ediliyordu: https://docs.rs/regex-automata/0.2.0/regex_automata/
      Ben de asıl olayı hatırlamıyorum. Çeşitli nedenlerle birçok kişiyi engelliyorum ama şimdi engeli kaldırdım

  • BioJulia, derleme zamanında rastgele Julia kodu ekleyebilen saf Julia regex motoru Automa.jl'yi yayımladı
    Rust'un regex'inin Automa'dan çok daha gelişmiş olduğu gerçeğini küçümsemek istemiyorum, ancak regex'in iç yapısını bir kütüphane olarak dışa açan ilk örnek olduğu ifadesine katılmak zor

    • Bunlar kulağa iki farklı şey gibi geliyor
      Örneğin PCRE2'de, söylenene benzer gelen “callout” desteği var: https://www.pcre.org/current/doc/html/pcre2callout.html
      ragel ve re2c gibi araçlar da benzer şeyler yapıyordu
      Bu blog yazısında kastedilen, regex kütüphanesinin kendi iç yapısını çıkarıp ayrı sürümlenen bir kütüphane haline getirmek ve başkalarının bunları birleştirebilmesini sağlamak
      Backtracking yapanlarda genelde yalnızca tek bir backtracker motoru olduğu için bu yaklaşım daha az doğal, ancak otomaton tabanlı kütüphaneler çoğu zaman birden fazla motoru çeşitli şekillerde birleştiriyor
      Yine de backtracking yapanlar da pratikte dışa açılmayan regex ayrıştırıcısı veya AST gibi şeyleri dışa açabilir