Java, Scala a regulární výrazy #5 - posesivní regexy a StackOverflowError
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 greedy
a lazy (hladových a líných), jsou ještě possesive regexy. Zapisují se jako
.*+
, .++
, .?+
a .{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:
- Jak jsem četl zdrojové kódy regexů, myslím, že by nebylo těžké napsat knihovnu, které provádí reguláry nad libovolnými kolekcemi a ne jen řetězci stringů.