0xDEADBEEF

[RSS]
««« »»»

Java, Scala a regulární výrazy #4 - líné regexy a StackOverflowError

19. 12. 2017

Jednou z nepříjemných vlastností regexů v Javě je to, že můžou snadno skončit přetečením zásobníku a StackOverflowError. Regexy dělají backtracking, jsou implementovány rekurzivně a proto jde o nevyhnutelnou eventualitu.

Nejběžnější druhy opakování .*, .+.{m,n} jsou greedy (lakomé, hladové nebo jak je to česky) a snaží se pojmout co nejdelší vstup. Když následující část regexu selže, začnou s backtrackingem a postupně upouštějí z požraného vstupu, dokud následující část uspěje. Aby to fungovalo, potřebují si pamatovat kam skočit zpátky a tato pozice je (často) uchována na zásobníku při rekurzivním volání.

Když mám například regex .+.{5}, první část .+ pojme celý vstup, pak zjistí, že následující regex .{5} pro pět libovolných znaků nepasuje, ustoupí o jeden znak, zkusí znovu, nepasuje, opět ustoupí a tak dále dokud nepojme všechno kromě pěti posledních znaků. Teprve potom .{5} sedne a celý regex skončí úspěchem.

Naproti tomu líné (anglicky lazy nebo také reluctant) opakování .*?, .+?.{m,n}? se snaží pojmout jen absolutní minimum, ideálně nic. V případě nouze, kdy následující regex selže, pojme jedno další opakování a pak otestuje následující část regexu.

V regexu .+?.{5} první část .+? nejprve nepožere nic, otestuje následující část, když ta selže, požere jedno opakování víc, zkusí znovu a tak dále.

Hladová a líná opakování nezmění jestli regex selže nebo ne, může změnit jen jak bude vstupní string rozdělen mezi uzávorkované skupiny.

Z výše popsaných důvodů vyplývá, že hladové regexy někdy můžou skončit výjimkou StackOverflowError, zatímco líné proběhnou úspěšně.

Například toto

("\uD83D\uDC09 "*100000).matches(".*")

skončí StackOverflowError. Vstupem je řetězec, ve kterém se sto tisíckrát opakuje symbol draka, který je hned následovaný mezerou. Naproti tomu varianty

("\uD83D\uDC09 "*100000).matches(".*?")
("\uD83D\uDC09 "*100000).matches(".*+")

skončí úspěšně, protože se liší způsobem, jakým je regex prováděn.

Java obsahuje optimalizaci, že když jedno opakování regexu pojme stejný počet znaků jako minulé opakování, nevolá se rekurzivně, ale ve smyčce. Symbol \uD83D\uDC09 zabírá dva chary a je hned následovaný jednocharovou mezerou. . tedy střídavě matchuje jeden a dva chary a proto vždy dělá rekurzivní volání a eventuálně přeteče zásobník (kód ve třídě Curly, metody match0, match1, match2).

Líná varianta si nemusí pamatovat, kam skočit zpátky a proto je implementována smyčkou, která nevyčerpá zásobník a neselže.

Tohle se týká jen případů, kdy se opakuje jednoduchý neuzávorkovaný vzor (jako třeba ., \W, \S atd.) a je to problém/řešení jen pro stringy obsahující několikabajtové znaky. Ale ty nejsou zas tak vzácné v pro texty s emoji.

Něco jako (a|b+)+? se vykonává vždy rekurzivně. Vnitřní implementace regexů je komplikovaná a aktivně se snaží předejít mnoha případům katastrofického backtrackingu. Proto se někdy jednoduchý vzor provádí poměrně překvapivě.

Co přetečení a katastrofickému backtrackingu předchází mnohem spolehlivěji jsou takzvané posesivní regexy, ale o nich něco napíšu příště.

píše k47 (@kaja47, k47)