0xDEADBEEF

[RSS]
««« »»»

Java, Scala a regulární výrazy #5 - posesivní regexy a StackOverflowError

28. 7. 2018

Minule jsem psal o hla­do­vých a líných re­gexech, na­zna­čil jejich im­ple­men­taci a ukázal případ, kdy líný regex může pře­de­jít pře­te­čení zá­sob­níku a StackOverflowError.

V java im­ple­men­taci regexů exis­tuje ještě třetí druh opa­ko­vání, vedle greedylazy (hla­do­vých a líných), jsou ještě posse­sive regexy. Za­pi­sují se jako .*+, .++, .?+.{m,n}+, jsou hla­dové, nikdy ne­dě­lají backtrac­king a v pří­pa­dech, kdy by oby­čejné hla­dové opa­ko­vání backtrac­ko­valo, selžou.

Na­pří­klad regex (ve Scale string se třemi uvo­zov­kami je brán jak je, není třeba v něm skoro nic es­ca­po­vat, ide­ální pro regexy)

"""(?x)  " ( \\" | [^"] )++ "  """.r

začne hledat od první dvo­jité uvo­zovky, hla­dově kon­zu­muje všechno, co je es­ca­po­vaná uvo­zovka nebo ja­ký­koli jiný znak kromě uvo­zovky, až narazí na ukon­čo­vací uvo­zovku a když ji najde, nikdy ne­u­stoupí o krok zpět. Chová se tedy do jisté míry ato­micky (kdo neví, tak (?x) na za­čátku zna­mená, že mezery se ig­no­rují).

Po­sesivní regexy mohou vést k od­mít­nutí ně­kte­rých stringů, které by hla­dové nebo líné regexy při­jaly. Ale na druhou stranu regex selže brzo a nebude zkou­šet všechny per­mu­tace. Jde tedy o druh op­ti­ma­li­zace.

Často právě po­sesivní regexy jsou to, co člověk chce. Hodí se, když chci hledat až do ur­či­tého sym­bolu, který jasně in­di­kuje, kde po­sesivní regex skončí. Často mívají formu a [^a]++ a.

Pro­tože ne­dě­lají backtrac­king jsou im­ple­men­to­vány ite­ra­tivně a ne­mů­žou skon­čit Stac­kO­ver­flowError.

Na­pří­klad ná­sle­du­jící dva regexy tes­tují to samé.

("a " * 1000000).matches("(a+ )+")
("a " * 1000000).matches("(a+ )++")

První skončí Stac­kO­ver­flowError, ale druhý do­běhne v po­řádku. (Kdo neví, tak ná­so­bení stringu ve Scale ho opa­kuje.)

Navíc: Pro­tože ne­dě­lají backtrac­king, lo­gicky u nich ne­hrozí pří­pady ka­ta­stro­fic­kého backtrac­kingu.

Opět dva pří­pady: První je oby­čejný hla­dový regex, druhý je posse­sive regex.

"ACCCCCCCCCCCCCCCCCCCCCCCCCCCCCCX".matches("A(B|C+)+D")
"ACCCCCCCCCCCCCCCCCCCCCCCCCCCCCCX".matches("A(B|C++)+D")

Druhý dojede v mi­k­ro­sekundě, ale první bude trvat celou věč­nost právě proto, že začne zkou­šet všechny mož­nosti a dojde ke kom­bi­na­to­rické ex­plozi.

Po­sesivní regex bude vy­hod­no­co­ván takto: A pasuje, zkusí B, nic, C++ sedne a sebere všechna C, zkusí D, selže, ++ za­jistí, že ne­vrátí žádné C zpátky, ne­zkusí další va­ri­anty a celý regex selže.


Pozn:

píše k47 (@kaja47, k47)