0xDEADBEEF

[RSS]
««« »»»

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

19. 12. 2017

Jednou z ne­pří­jem­ných vlast­ností regexů v Javě je to, že můžou snadno skon­čit pře­te­če­ním zá­sob­níku a Stac­kO­ver­flowError. Regexy dělají backtrac­king, jsou im­ple­men­to­vány re­kur­zivně a proto jde o ne­vy­hnu­tel­nou even­tu­a­litu.

Nej­běž­nější druhy opa­ko­vání .*, .+.{m,n} jsou greedy (lakomé, hla­dové nebo jak je to česky) a snaží se po­jmout co nejdelší vstup. Když ná­sle­du­jící část regexu selže, začnou s backtrac­kin­gem a po­stupně upouš­tějí z po­žra­ného vstupu, dokud ná­sle­du­jící část uspěje. Aby to fun­go­valo, po­tře­bují si pa­ma­to­vat kam skočit zpátky a tato pozice je (často) ucho­vána na zá­sob­níku při re­kur­ziv­ním volání.

Když mám na­pří­klad regex .+.{5}, první část .+ pojme celý vstup, pak zjistí, že ná­sle­du­jící regex .{5} pro pět li­bo­vol­ných znaků ne­pa­suje, ustoupí o jeden znak, zkusí znovu, ne­pa­suje, opět ustoupí a tak dále dokud ne­po­jme všechno kromě pěti po­sled­ních znaků. Teprve potom .{5} sedne a celý regex skončí úspě­chem.

Na­proti tomu líné (an­g­licky lazy nebo také re­luctant) opa­ko­vání .*?, .+?.{m,n}? se snaží po­jmout jen ab­so­lutní mi­ni­mum, ide­álně nic. V pří­padě nouze, kdy ná­sle­du­jící regex selže, pojme jedno další opa­ko­vání a pak otes­tuje ná­sle­du­jící část regexu.

V regexu .+?.{5} první část .+? nej­prve ne­po­žere nic, otes­tuje ná­sle­du­jící část, když ta selže, požere jedno opa­ko­vání víc, zkusí znovu a tak dále.

Hla­dová a líná opa­ko­vání ne­změní jestli regex selže nebo ne, může změnit jen jak bude vstupní string roz­dě­len mezi uzá­vor­ko­vané sku­piny.

Z výše po­psa­ných důvodů vy­plývá, že hla­dové regexy někdy můžou skon­čit vý­jim­kou Stac­kO­ver­flowError, za­tímco líné pro­běh­nou úspěšně.

Na­pří­klad toto

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

skončí Stac­kO­ver­flowError. Vstu­pem je ře­tě­zec, ve kterém se sto ti­síc­krát opa­kuje symbol draka, který je hned ná­sle­do­vaný me­ze­rou. Na­proti tomu va­ri­anty

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

skončí úspěšně, pro­tože se liší způ­so­bem, jakým je regex pro­vá­děn.

Java ob­sa­huje op­ti­ma­li­zaci, že když jedno opa­ko­vání regexu pojme stejný počet znaků jako minulé opa­ko­vání, nevolá se re­kur­zivně, ale ve smyčce. Symbol \uD83D\uDC09 zabírá dva chary a je hned ná­sle­do­vaný jednocharovou me­ze­rou. . tedy stří­davě matchuje jeden a dva chary a proto vždy dělá re­kur­zivní volání a even­tu­álně pře­teče zá­sob­ník (kód ve třídě Curly, metody match0, match1, match2).

Líná va­ri­anta si nemusí pa­ma­to­vat, kam skočit zpátky a proto je im­ple­men­to­vána smyč­kou, která ne­vy­čerpá zá­sob­ník a ne­selže.

Tohle se týká jen pří­padů, kdy se opa­kuje jed­no­du­chý ne­u­zá­vor­ko­vaný vzor (jako třeba ., \W, \S atd.) a je to pro­blém/řešení jen pro stringy ob­sa­hu­jící ně­ko­li­ka­baj­tové znaky. Ale ty nejsou zas tak vzácné v pro texty s emoji.

Něco jako (a|b+)+? se vy­ko­nává vždy re­kur­zivně. Vnitřní im­ple­men­tace regexů je kom­pli­ko­vaná a ak­tivně se snaží pře­de­jít mnoha pří­pa­dům ka­ta­stro­fic­kého backtrac­kingu. Proto se někdy jed­no­du­chý vzor pro­vádí po­měrně pře­kva­pivě.

Co pře­te­čení a ka­ta­stro­fic­kému backtrac­kingu před­chází mnohem spo­leh­li­věji jsou tak­zvané po­sesivní regexy, ale o nich něco napíšu příště.

píše k47 (@kaja47, k47)