"İki Problem" paradoksu ve Cuma günü 16:58 hiyeroglifleri
1997 yılında Netscape mühendisi ve kıdemli hacker Jamie Zawinski, bilgisayar bilimleri tarihine altın harflerle kazınan şu meşhur vecizeyi kaleme aldı: "Bazı insanlar bir sorunla karşılaştıklarında 'Biliyorum, düzenli ifadeler (regex) kullanacağım' diye düşünür. Artık iki sorunları vardır."
Aradan geçen neredeyse otuz yıla rağmen bu cüretkar tespit, yazılım dünyasının en sarsılmaz doğa kanunlarından biri olmayı sürdürüyor. Kıdemli her sistem mimarı şu trajikomik sahneye en az bir kez tanıklık etmiştir: bunaltıcı bir Cuma günü saat tam 16:58'dir, mesainin bitmesine iki dakika kala üretim ortamına acil bir bilet düşer; uluslararası telefon numaralarının veya e-posta adreslerinin doğrulanması gerekmektedir. Aşırı kafein yüklenmiş hevesli bir stajyer ya da genç yazılımcı, ASCII karakter dökümhanesinde patlama olmuş gibi görünen 200 karakterlik anlamsız bir hiyeroglif yazar ve kodu doğrudan ana dala gönderir.
Pazartesi sabahı geldiğinde hiyeroglifin yazarı ne yaptığını tamamen unutmuştur, kod incelemesini yapan kıdemli mühendis mesleği bırakmayı düşünür ve sürekli entegrasyon (CI) hattı "kullanici@localhost" gibi son derece meşru bir girdide çuvallar. Üstelik bu ifadeleri internette test etmek isteyen geliştiriciler başka bir eziyetle karşılaşır: basit bir virgülü test etmek için bile yüzlerce megabayt bellek yutan, 15 gereksiz panelle donatılmış, reklamlarla boğulmuş ve kullanıcı verilerini izleyen hantal web araçları. TOOL GIGA platformunda biz bu şaklabanlığı reddediyoruz. Bir yazılımcı aracı cerrahi bir neşter gibi olmalıdır: sıfır gecikmeli, hafif, girdileri milisaniyenin altında değerlendiren ve gizli verilerinizi asla harici sunuculara sızdırmayan bir mühendislik motoru.
Stephen Kleene'in yıldızından (1951) Ken Thompson'ın Unix ed editörüne (1968)
Düzenli ifadeler ne Silikon Vadisi'nin parlak ofislerinde ne de kurumsal sunucu odalarında doğdu. Onların kökeni, yirminci yüzyılın ortalarındaki saf matematiksel mantığa ve nörofizyolojiye dayanır. 1951 yılında Amerikalı matematikçi Stephen Cole Kleene, RAND Corporation bünyesinde çalışırken "Representation of Events in Nerve Nets and Finite Automata" başlıklı çığır açan bir makale yayımladı. Amacı, Warren McCulloch ve Walter Pitts tarafından önerilen biyolojik sinir ağlarının matematiksel modellerini cebirsel bir gösterimle formalize etmekti. Bu tarihi çalışmada Kleene, düzenli kümeler kavramını tanımladı ve bir elemanın sıfır ya da sonsuz tekrarını temsil eden meşhur "Kleene yıldızını" (*) icat etti.
Soyut cebirden pratik yazılım mühendisliğine uzanan köprüyü ise 1968 yılında Bell Labs'ta Unix'in ve B dilinin ortak yaratıcısı Ken Thompson kurdu. Thompson, Kleene'in kuramını QED metin editöründe metin aramayı hızlandırmak için uyguladı ve ardından bu motoru Unix'in temel editörü ed ile efsanevi grep komutuna entegre etti (komutun adı doğrudan ed editörünün g/re/p: Globally search a Regular Expression and Print yönergesinden türemiştir). Thompson ayrıca ifadeleri IBM 7094 makine koduna doğrudan çeviren tarihin ilk Just-In-Time (JIT) derleyicisini tasarladı.
Yirmi yıl sonra, 1987'de Larry Wall, Perl (Practical Extraction and Report Language) dilini piyasaya sürerek düzenli ifadeleri mütevazı bir yardımcı programdan modern programlamanın birinci sınıf vatandaşına dönüştürdü. Perl; yakalama yapmayan grupları, lookahead ve lookbehind denetimlerini ve tembel niceleyicileri ekleyerek günümüzde JavaScript (ECMAScript RegExp), PHP, Python, Go ve Rust tarafından kullanılan PCRE (Perl Compatible Regular Expressions) standardının temelini attı.
Felaket geri izleme (ReDoS) ve işlemci termodinamiği
Düzenli ifadeler zararsız metin kalıpları gibi görünse de, motorun kaputunun altında Belirsiz Sonlu Otomatlar (NFA) hüküm sürer. NFA çalışma mekanizmasını anlamamak, sunucuların çökmesine ve düzenli ifade hizmet reddi saldırılarına (ReDoS – Regular Expression Denial of Service) davetiye çıkarmaktır.
V8 veya PCRE gibi çağdaş motorlar, geri izleme (backtracking) prensibiyle çalışan NFA algoritmaları kullanır. Bir desen iç içe geçmiş niceleyiciler veya belirsiz alternatifler barındırdığında —klasik ders kitabı tuzağı olan (a+)+$ veya (x+x+)+y gibi— motor, girdiyi doğrulamak için tüm permütasyon kombinasyonlarını dener. Eğer motora "aaaaaaaaaaaaaaaaaaaaX" dizesini verirseniz, tüm "a" harflerini hevesle yutar; ancak sondaki "X" karakterine ulaştığında sondaki $ çapa koşulu başarısız olur.
İşte bu anda algoritmik bir yangın başlar: motor pes etmez, geriye doğru adım atar (backtrack). İç gruptan bir karakter eksiltir, dış grubu yeniden hesaplar ve tekrar dener. Bu kısır döngü, hesaplama karmaşıklığını doğrusal $O(N)$ seviyesinden $O(2^N)$ büyüklüğündeki üstel bir cehenneme fırlatır.
İşlemci transistörleri açısından bu durum saf termodinamik strestir. Yalnızca 30–35 karakterlik kötü niyetli bir girdi, işlemciyi yüz milyonlarca gereksiz deneme yapmaya zorlar. Tek bir kötü amaçlı HTTP isteği bir CPU çekirdeğini %100 yükle kilitler, olay döngüsünü felç eder, sunucu fanlarını son devirde haykırtır ve AWS Lambda gibi sunucusuz platformların kontrolsüzce ölçeklenmesine yol açarak saatler içinde binlerce dolarlık bulut faturası çıkarır. Bu nedenle TOOL GIGA test aracımızda 100 ms çalışma tavanı ve güvenlik sigortası yer alır; ReDoS şüphesi doğduğu anda işlemci kilitlenmeden yürütme derhal sonlandırılır.
Cthulhu laneti: HTML neden asla düzenli ifadelerle ayrıştırılamaz?
2009 yılında Stack Overflow sitesinde masum bir soru belirdi: "Düzenli ifadeler kullanarak HTML etiketlerini nasıl ayıklayabilirim?" Bu soruya verilen yanıt, yazılım folklorunun en efsanevi şaheserine dönüştü: H. P. Lovecraft tarzında yazılmış, HTML'i regex ile ayrıştırmaya çalışmanın antik iblis Cthulhu'yu uyandıracağını ve aklın sınırlarını parçalayacağını haykıran mizahi bir manifesto ("O GELİYOR... HTML'İ ASLA REGEX İLE AYRIŞTIRMAYIN").
Bu hicvin arkasında Noam Chomsky'nin Biçimsel Diller Hiyerarşisi (1956) ile kanıtlanmış katı bir matematiksel gerçek yatar:
- Tip 3: Düzenli Diller (Sonlu Otomatlar / RegEx ile çözülür). Doğrusal desenleri, sayı dizilerini ve belirteçleri tanıyabilir; fakat derinlik sayma hafızası kesinlikle yoktur.
- Tip 2: Bağlamdan Bağımsız Diller (Yığınlı Otomatlar gerektirir). HTML, XML, JSON ve programlama dilleri bu sınıftadır; her açılış etiketi, keyfi bir iç içe derinlikte kapanış etiketiyle eşleşmelidir (
<div><div>...</div></div>). - Tip 1 ve Tip 0: Bağlama duyarlı gramerler ve Turing makineleri.
Düzenli ifadelerin bir yığın (stack) hafızası bulunmadığından, iç içe geçmiş etiketlerin doğru sırada kapanıp kapanmadığını matematiksel olarak takip edemezler. HTML kodunu regex ile temizlemeye kalkışmak; yorum satırları, tırnak içindeki etiket benzeri metinler ve bozuk sözdizimleri karşısında kaçınılmaz olarak çöker. RegEx, atomik dizgileri (UUID, e-posta, tarih) doğrulamak için mükemmel bir neşterdir; ancak hiyerarşik HTML için daima gerçek DOM ayrıştırıcıları (DOMDocument, Cheerio) kullanılmalıdır.