„Dviejų problemų“ paradoksas ir penktadienio 16:58 hieroglifai
1997 metais programuotojas ir „Netscape“ inžinierius Jamie Zawinski kompiuterių mokslo istorijoje įrašė nemirtingą sentenciją: „Kai kurie žmonės, susidūrę su problema, pagalvoja: 'Aš žinau, panaudosiu reguliariuosius reiškinius'. Dabar jie turi dvi problemas.“
Praėjus beveik trims dešimtmečiams, ši ciniška įžvalga išlieka geležiniu programinės įrangos inžinerijos dėsniu. Kiekvienas patyręs sistemų architektas bent kartą gyvenime matė šią siaubo dramą: penktadienis, 16:58, iki darbo pabaigos lieka dvi minutės, gamybinėje sistemoje staiga prireikia patikrinti tarptautinio telefono numerio formatą arba naudotojo el. pašto adresą. Entuziazmo apimtas jaunesnysis programuotojas parašo 200 simbolių neperskaitomą hieroglifą, primenantį sprogimą ASCII šriftų gamykloje, ir ramia sąžine išsiunčia kodą į pagrindinę šaką.
Pirmadienio rytą autorius jau nebeatsimena, ką tie pasvirieji brūkšniai ir skliausteliai reiškia, vyresnysis programuotojas per kodo peržiūrą ima svarstyti apie karjeros keitimą, o testavimo aplinka pakimba gavusi visiškai teisėtą įvestį, pavyzdžiui, "vardas@localhost". Negana to, norėdami greitai išbandyti šabloną internete, inžinieriai susiduria su kita nelaime: lėtais, reklamomis apkrautais įrankiais su 15 nereikalingų skydelių, kurie ryja šimtus megabaitų operatyviosios atminties vien tam, kad patikrintų kablelį. TOOL GIGA platformoje mes atsisakome šio cirko. Inžinerinis įrankis privalo būti žaibiškas, lengvas, subtilus ir veikti be jokių vėlavimų ar duomenų siuntimo į trečiųjų šalių serverius.
Nuo Stepheno Kleene žvaigždutės (1951 m.) iki Keno Thompsono Unix „ed“ (1968 m.)
Reguliarieji reiškiniai gimė ne komercinėse Silicio slėnio laboratorijose ir ne korporatyviniuose IT skyriuose. Jų šaknys slypi grynojoje matematinėje logikoje ir ankstyvojoje neurofiziologijoje. 1951 metais JAV matematikas Stephenas Cole Kleene, dirbdamas RAND korporacijoje, publikavo istorinį darbą „Representation of Events in Nerve Nets and Finite Automata“. Jis siekė matematiškai aprašyti biologinių neuronų tinklų elgseną, kurią anksčiau modeliavo Warrenas McCullochas ir Walteris Pittsas. Šiame tyrime Kleene formalizavo reguliariąsias aibes ir sukūrė garsiąją „Kleene žvaigždutę“ (*), reiškiančią nulinį arba begalinį elemento pasikartojimą.
Tiltą iš abstrakčiosios algebros į praktinį programavimą 1968 metais nutiesė legendinis Kenas Thompsonas – vienas iš „Unix“ operacinės sistemos ir B kalbos kūrėjų „Bell Labs“. Thompsonas pritaikė Kleene algebrą teksto redagavimui QED programoje, o vėliau įdiegė ją tiesiai į standartinį „Unix“ redaktorių ed ir paieškos komandą grep (pavadinimas kilo tiesiai iš ed komandos g/re/p: Globally search a Regular Expression and Print). Thompsonas taip pat sukūrė pirmąjį pasaulyje JIT kompiliatorių reguliariesiems reiškiniams, transliuodamas šablonus tiesiai į IBM 7094 procesoriaus mašininį kodą realiu laiku.
1987 metais Larry Wallas pristatė „Perl“ programavimo kalbą, paversdamas reguliariuosius reiškinius pamatiniu programavimo elementu. „Perl“ įvedė nefiksavimo grupes, sąlyginius patikrinimus į priekį bei atgal (lookahead/lookbehind) ir tingiuosius kvantifikatorius, suformuodamas PCRE standartą, kuriuo šiandien remiasi „JavaScript“ (ECMAScript RegExp), PHP, „Python“, „Go“ ir kitos šiuolaikinės kalbos.
Katastrofiškas grįžtamasis ryšys (ReDoS) ir procesorių termodinamika
Nors reguliarieji reiškiniai atrodo kaip paprastos eilučių apdorojimo taisyklės, po jų gaubtu sukasi nedeterministiniai baigtiniai automatai (NFA). NFA mechanikos nesupratimas yra tiesiausias kelias į gamybinių sistemų perkaitimą ir paslaugos trikdymo atakas (ReDoS – Regular Expression Denial of Service).
Populiariausi varikliai (pvz., V8 naršyklėse ar PCRE serveryje) naudoja grįžtamuoju ryšiu (angl. backtracking) paremtą NFA algoritmą. Kai šablonas turi įdėtus arba persidengiančius kartojimus – pavyzdžiui, vadovėlinę klaidą (a+)+$ – variklis privalo išbandyti visus įmanomus simbolių grupavimo variantus. Jei pateiksite eilutę "aaaaaaaaaaaaaaaaaaaaX", variklis lengvai sugers visus „a“ simbolius, tačiau ties paskutiniuoju „X“ simboliu kils nesuderinamumas su pabaigos inkaru $.
Štai čia prasideda eksponentinis algoritminis pragaras: variklis nepasiduoda, o pradeda žingsnis po žingsnio grįžti atgal. Jis atima vieną simbolį iš vidinės grupės, perskaičiuoja išorinę grupę ir vėl bando pasiekti pabaigą. Algoritminis sudėtingumas nuo tiesinio $O(N)$ sprogsta iki eksponentinio $O(2^N)$.
Procesoriaus tranzistoriams tai reiškia gryną termodinaminį stresą. Vos 30–35 simbolių netinkama eilutė verčia procesorių atlikti šimtus milijonų bergždžių bandymų. Vieno piktybiško vartotojo užklausa akimirksniu apkrauna CPU branduolį 100%, serverių aušintuvai ima kaukti, o automatinis debesijos resursų plėtimas („AWS Lambda“ ar „Google Cloud Run“) gali per kelias valandas sugeneruoti tūkstantines sąskaitas. Mūsų TOOL GIGA tikrintuve įdiegtas griežtas 100 ms vykdymo saugiklis, kuris nutraukia skaičiavimus vos pajutęs ReDoS grėsmę.
Cthulhu prakeiksmas: kodėl HTML kodo niekada negalima doroti su RegEx
2009 metais portale „Stack Overflow“ pasirodė nekaltas klausimas: „Kaip naudojant reguliariuosius reiškinius išvalyti HTML žymes?“ Atsakymas į šį klausimą tapo pačiu žymiausiu programavimo folkloro perlu: pamišėliškas, H. P. Lovecrafto stiliumi parašytas manifestas, perspėjantis, jog bandymai regexu doroti HTML pažadina senovės demoną Cthulhu ir sugriauna visatos audinį („NEBANDYKITE DOROTI HTML SU REGEX... JIS ATEINA“).
Už šio sarkazmo slypi griežtas matematinis faktas – Noamo Chomsky formaliųjų gramatikų hierarchija (1956 m.):
- 3 tipo gramatika (Reguliarioji): Atpažįstama baigtiniais automatais (RegEx). Tinka tiesinėms sekoms, skaičių formatams ar identifikatoriams, tačiau visiškai neturi atminties gylio fiksavimui.
- 2 tipo gramatika (Bekontekstė): Reikalauja automato su steku (magazinu). Tai yra HTML, XML, JSON ir dauguma programavimo kalbų, kur atidarymo žymė privalo turėti atitinkamą uždarymo žymę bet kokiame įdėtame gylyje (
<div><div>...</div></div>). - 1 ir 0 tipo gramatikos: Kontekstinės ir Tiuringo pilnos sistemos.
Kadangi reguliarieji reiškiniai neturi steko atminties, jie matematiškai negali suskaičiuoti, ar visos atidarytos žymės buvo teisingai uždarytos esant lizdinei struktūrai. Bandant HTML kodą karpyti primityviais šablonais, anksčiau ar vėliau kils klaidos dėl komentarų, atributų reikšmių su kabutėmis ar netikėtų skliaustų. RegEx yra tobulas chirurginis skalpelis atominiams duomenims (UUID, el. paštui, datoms), tačiau struktūrizuotam žymėjimui visada privaloma naudoti tikrus sintaksės medžių analizatorius („DOMDocument“, „Cheerio“ ar specializuotus XML parserius).