0xDEADBEEF

RSS odkazy english edition
««« »»»

Java, Scala a regulární výrazy #7 - zero width positive lookbehind

14. 7. 2020

Regexy nabízejí mnoho mocných a užitečných konstrukcí a jednou z nich je zero width positive lookbehind. Regex (?<=x)y uspěje, pokud nalezne y, kterému předchází x. Výskyt x přitom nebude "zkonzumován" a zahrnut do výsledku (proto zero width - nijak neovlivní délku shody).

Má to jen ten problém, že když si nedáte pozor, lookbehind může být, pokud nemá omezenou maximální délku, velice pomalý. Java se při matchování podívá nejmenší možný počet znaků nazpět a zkusí od toho místa napasovat lookbehind. Pokud neuspěje, podívá se o jeden znak víc zpět a proces opakuje, dokud neuspěje nebo dokud nezkusí maximum znaků dávající smysl. Může jít o konec předchozí shody nebo začátek stringu a to, jak se říká, není ideální.

Lookbehind má na starosti metoda Behind.match a hlavně následující smyčka:

for (int j = i - rmin; !conditionMatched && j >= from; j--) {
    conditionMatched = cond.match(matcher, j, seq);
}

Z j-- je vidět, že regex postupně couvá.

Regexu níže, který hledá deklarace ve zdrojácích Scaly (název, jemuž předchází klíčové slovo val, var nebo def) trvala kontrola 50 kB zdrojáku 400 ms.

(?x)  (?<=(?:val|var|def)\s+)  [a-z][\w$]*

Když omezím maximální délku lookbehind, konkrétní případ se zrychlí 10x.

(?x)  (?<=(?:val|var|def)\s{1,6})  [a-z][\w$]*

Java je dostatečně chytrá, aby poznala, že v tomto případě činí maximální délka 9 znaků, minimálně 4 znaky a stačí vyhodnotit positive lookbehind vzor nanejvýš 6x.

Ideální by bylo, kdyby regex engine lookbehind vyhodnocoval pozpátku. Pak by vždy stačilo libovolný vzor vyhodnotit jen jednou, ale nevím, jestli to nějaká implementace regexů dělá. Dost by to zkomplikovalo implementaci, protože by bylo potřeba všechnu logiku napsat dvakrát - jednou vpřed a podruhé pozpátku.

PCRE implementace (použitá mimo jiné v PHP) přímo vyžaduje, aby délka lookbehind byla dopředu známá. Jde o omezení síly regexů, ale aspoň nehrozí nepříjemné překvapení, že se jinak celkem svižný regex na určitém vstupu začne bez varování neuvěřitelně courat.


+1: Vyhodnocování pozpátku je zmíněno tady.

píše k47 (@kaja47, k47)