Java, Scala a regulární výrazy #4 - líné regexy a StackOverflowError
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í .*
, .+
a .{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í .*?
,
.+?
a .{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 char
y a je hned následovaný jednochar
ovou
mezerou. .
tedy střídavě matchuje jeden a dva char
y 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ě.