0xDEADBEEF

RSS
««« »»»

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

28. 7. 2018

Minule jsem psal o hladových a líných regexech, naznačil jejich implementaci a ukázal případ, kdy líný regex může předejít přetečení zásobníku a StackOverflowError.

V java implementaci regexů existuje ještě třetí druh opakování, vedle greedylazy (hladových a líných), jsou ještě possesive regexy. Zapisují se jako .*+, .++, .?+.{m,n}+, jsou hladové, nikdy nedělají backtracking a v případech, kdy by obyčejné hladové opakování backtrackovalo, selžou.

Například regex (ve Scale string se třemi uvozovkami je brán jak je, není třeba v něm skoro nic escapovat, ideální pro regexy)

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

začne hledat od první dvojité uvozovky, hladově konzumuje všechno, co je escapovaná uvozovka nebo jakýkoli jiný znak kromě uvozovky, až narazí na ukončovací uvozovku a když ji najde, nikdy neustoupí o krok zpět. Chová se tedy do jisté míry atomicky (kdo neví, tak (?x) na začátku znamená, že mezery se ignorují).

Posesivní regexy mohou vést k odmítnutí některých stringů, které by hladové nebo líné regexy přijaly. Ale na druhou stranu regex selže brzo a nebude zkoušet všechny permutace. Jde tedy o druh optimalizace.

Často právě posesivní regexy jsou to, co člověk chce. Hodí se, když chci hledat až do určitého symbolu, který jasně indikuje, kde posesivní regex skončí. Často mívají formu a [^a]++ a.

Protože nedělají backtracking jsou implementovány iterativně a nemůžou skončit StackOverflowError.

Například následující dva regexy testují to samé.

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

První skončí StackOverflowError, ale druhý doběhne v pořádku. (Kdo neví, tak násobení stringu ve Scale ho opakuje.)

Navíc: Protože nedělají backtracking, logicky u nich nehrozí případy katastrofického backtrackingu.

Opět dva případy: První je obyčejný hladový regex, druhý je possesive regex.

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

Druhý dojede v mikrosekundě, ale první bude trvat celou věčnost právě proto, že začne zkoušet všechny možnosti a dojde ke kombinatorické explozi.

Posesivní regex bude vyhodnocován takto: A pasuje, zkusí B, nic, C++ sedne a sebere všechna C, zkusí D, selže, ++ zajistí, že nevrátí žádné C zpátky, nezkusí další varianty a celý regex selže.


Pozn:

píše k47 (@kaja47, k47)