0xDEADBEEF (⇉english edition⇉)

[RSS] [odkazy]
««« »»»

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

14. 7. 2020

Regexy na­bí­zejí mnoho moc­ných a uži­teč­ných kon­strukcí a jednou z nich je zero width po­si­tive lo­o­kbehind. Regex (?<=x)y uspěje, pokud na­lezne y, kte­rému před­chází x. Výskyt x přitom nebude „zkon­zu­mo­ván“ a za­hr­nut do vý­sledku (proto zero width – nijak ne­o­vlivní délku shody).

Má to jen ten pro­blém, že když si nedáte pozor, lo­o­kbehind může být, pokud nemá ome­ze­nou ma­xi­mální délku, velice pomalý. Java se při matcho­vání podívá nejmenší možný počet znaků nazpět a zkusí od toho místa na­pa­so­vat lo­o­kbehind. Pokud ne­u­spěje, podívá se o jeden znak víc zpět a proces opa­kuje, dokud ne­u­spěje nebo dokud ne­zkusí ma­xi­mum znaků dá­va­jící smysl. Může jít o konec před­chozí shody nebo za­čá­tek stringu a to, jak se říká, není ide­ální.

Lo­o­kbehind má na sta­rosti metoda Behind.match a hlavně ná­sle­du­jící smyčka:

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

j-- je vidět, že regex po­stupně couvá.

Regexu níže, který hledá de­kla­race ve zdro­já­cích Scaly (název, jemuž před­chází klí­čové slovo val, var nebo def) trvala kon­t­rola 50 kB zdro­jáku 400 ms.

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

Když omezím ma­xi­mální délku lo­o­kbehind, kon­krétní případ se zrychlí 10×.

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

Java je do­sta­tečně chytrá, aby po­znala, že v tomto pří­padě činí ma­xi­mální délka 9 znaků, mi­ni­málně 4 znaky a stačí vy­hod­no­tit po­si­tive lo­o­kbehind vzor na­nej­výš 6×.

Ide­ální by bylo, kdyby regex engine lo­o­kbehind vy­hod­no­co­val po­zpátku. Pak by vždy sta­čilo li­bo­volný vzor vy­hod­no­tit jen jednou, ale nevím, jestli to nějaká im­ple­men­tace regexů dělá. Dost by to zkom­pli­ko­valo im­ple­men­taci, pro­tože by bylo po­třeba všechnu logiku napsat dva­krát – jednou vpřed a po­druhé po­zpátku.

PCRE im­ple­men­tace (po­u­žitá mimo jiné v PHP) přímo vy­ža­duje, aby délka lo­o­kbehind byla do­předu známá. Jde o ome­zení síly regexů, ale aspoň ne­hrozí ne­pří­jemné pře­kva­pení, že se jinak celkem svižný regex na ur­či­tém vstupu začne bez va­ro­vání ne­u­vě­ři­telně courat.

píše k47 (@kaja47, k47)