Katastrofální backtracking

Některé regulární výrazy vypadají jednoduše, ale mohou vykonat velmi dlouhou dobu a dokonce „zavěsit“ engine JavaScript.

Dříve nebo později se s takovým chováním občas setká většina vývojářů. Typický příznak – regulární výraz někdy funguje dobře, ale u určitých řetězců se „zasekne“ a spotřebovává 100 % CPU.

V takovém případě webový prohlížeč navrhne skript zabít a stránku znovu načíst. Určitě to není dobrá věc.

U JavaScriptu na straně serveru může takový regulární výraz zastavit proces serveru, to je ještě horší. Takže bychom se na to rozhodně měli podívat.

Příklad

Řekněme, že máme řetězec a chtěli bychom zkontrolovat, zda se skládá ze slov \w+ s volitelnou mezerou \s? po každém.

Zřejmým způsobem, jak vytvořit regulární výraz, by bylo vzít slovo následované nepovinnou mezerou \w+\s? a pak to zopakujte s * .

To nás vede k regulárnímu výrazu ^(\w+\s?)*$ , specifikuje nula nebo více takových slov, která začínají na začátku ^ a skončit na konci $ řádku.

V akci:

let regexp = /^(\w+\s?)*$/;

alert( regexp.test("A good string") ); // true
alert( regexp.test("Bad characters: $@#") ); // false

Zdá se, že regulární výraz funguje. Výsledek je správný. I když na určitých strunách to zabere hodně času. Tak dlouho, že JavaScript engine „visí“ se 100% spotřebou CPU.

Pokud spustíte příklad níže, pravděpodobně nic neuvidíte, protože JavaScript se jen „zasekne“. Webový prohlížeč přestane reagovat na události, přestane fungovat uživatelské rozhraní (většina prohlížečů umožňuje pouze rolování). Po nějaké době doporučí stránku znovu načíst. Takže buďte opatrní:

let regexp = /^(\w+\s?)*$/;
let str = "An input string that takes a long time or even makes this regexp hang!";

// will take a very long time
alert( regexp.test(str) );

Abychom byli spravedliví, poznamenejme, že některé motory regulárních výrazů dokážou takové vyhledávání efektivně zpracovat, například verze motoru V8 od 8.8 to dokáže (takže Google Chrome 88 zde nevisí), zatímco prohlížeč Firefox ano.

Zjednodušený příklad

Co se děje? Proč regulární výraz přestává reagovat?

Abychom to pochopili, zjednodušíme příklad:odstraňte mezery \s? . Pak se změní na ^(\w+)*$ .

A aby byly věci jasnější, nahradíme \w s \d . Výsledný regulární výraz stále visí, například:

let regexp = /^(\d+)*$/;

let str = "012345678901234567890123456789z";

// will take a very long time (careful!)
alert( regexp.test(str) );

Co je tedy na regulárním výrazu špatného?

Nejprve si můžete všimnout, že regulární výraz (\d+)* je trochu zvláštní. Kvantifikátor * vypadá cize. Pokud chceme číslo, můžeme použít \d+ .

Ve skutečnosti je regulární výraz umělý; získali jsme to zjednodušením předchozího příkladu. Ale důvod, proč je pomalý, je stejný. Pojďme to tedy pochopit a předchozí příklad bude zřejmý.

Co se stane během vyhledávání ^(\d+)*$ v řádku 123456789z (pro srozumitelnost trochu zkráceno, poznamenejte si prosím nečíselný znak z na konci, je to důležité), proč to trvá tak dlouho?

Modul regulárních výrazů dělá toto:

  1. Nejprve se motor regulárních výrazů pokusí najít obsah závorek:číslo \d+ . Plus + je ve výchozím nastavení chamtivý, takže spotřebovává všechny číslice:

    \d+.......
    (123456789)z

    Po spotřebování všech číslic \d+ je považován za nalezený (jako 123456789 ).

    Poté hvězdicový kvantifikátor (\d+)* platí. Ale v textu už nejsou žádné číslice, takže hvězdička nic neříká.

    Dalším znakem ve vzoru je konec řetězce $ . Ale v textu máme z místo toho, takže neexistuje žádná shoda:

               X
    \d+........$
    (123456789)z
  2. Protože neexistuje žádná shoda, nenasytný kvantifikátor + snižuje počet opakování, vrací jeden znak zpět.

    Nyní \d+ přebírá všechny číslice kromě poslední (12345678 ):

    \d+.......
    (12345678)9z
  3. Poté se engine pokusí pokračovat v hledání od další pozice (hned za 12345678 ).

    Hvězdička (\d+)* lze použít – dává ještě jednu shodu \d+ , číslo 9 :

    \d+.......\d+
    (12345678)(9)z

    Motor se pokusí najít shodu s $ znovu, ale selže, protože splňuje z místo toho:

                 X
    \d+.......\d+
    (12345678)(9)z
  4. Neexistuje žádná shoda, takže motor bude pokračovat v couvání a sníží počet opakování. Backtracking obecně funguje takto:poslední chamtivý kvantifikátor snižuje počet opakování, dokud nedosáhne minima. Potom se předchozí chamtivý kvantifikátor sníží a tak dále.

    Zkouší se všechny možné kombinace. Zde jsou jejich příklady.

    První číslo \d+ má 7 číslic a potom číslo 2 číslice:

                 X
    \d+......\d+
    (1234567)(89)z

    První číslo má 7 číslic a poté dvě čísla po 1 číslici:

                   X
    \d+......\d+\d+
    (1234567)(8)(9)z

    První číslo má 6 číslic a poté číslo 3 číslice:

                 X
    \d+.......\d+
    (123456)(789)z

    První číslo má 6 číslic a poté 2 čísla:

                   X
    \d+.....\d+ \d+
    (123456)(78)(9)z

    …a tak dále.

Existuje mnoho způsobů, jak rozdělit sekvenci číslic 123456789 do čísel. Přesněji řečeno, existuje 2n-1 , kde n je délka sekvence.

  • Pro 123456789 máme n=9 , což dává 511 kombinací.
  • Pro delší sekvenci s n=20 existuje asi jeden milion (1048575) kombinací.
  • Pro n=30 – tisíckrát více (1073741823 kombinací).

Vyzkoušení každého z nich je přesně ten důvod, proč hledání trvá tak dlouho.

Zpět ke slovům a řetězcům

Podobná věc se stane v našem prvním příkladu, když hledáme slova podle vzoru ^(\w+\s?)*$ v řetězci An input that hangs! .

Důvodem je, že slovo může být reprezentováno jako jeden \w+ nebo mnoho:

(input)
(inpu)(t)
(inp)(u)(t)
(in)(p)(ut)
...

Pro člověka je zřejmé, že nemusí existovat žádná shoda, protože řetězec končí vykřičníkem ! , ale regulární výraz očekává slovní znak \w nebo mezeru \s na konci. Ale motor to neví.

Zkouší všechny kombinace toho, jak regulární výraz (\w+\s?)* může „spotřebovat“ řetězec, včetně variant s mezerami (\w+\s)* a bez nich (\w+)* (protože mezery \s? jsou volitelné). Protože existuje mnoho takových kombinací (viděli jsme to s číslicemi), vyhledávání zabere spoustu času.

Co dělat?

Máme zapnout líný režim?

Bohužel to nepomůže:pokud nahradíme \w+ s \w+? , regulární výraz bude stále viset. Pořadí kombinací se změní, ale ne jejich celkový počet.

Některé motory regulárních výrazů mají složité testy a konečnou automatizaci, které umožňují vyhnout se procházení všemi kombinacemi nebo je výrazně zrychlit, ale většina motorů ne a ne vždy to pomůže.

Jak to opravit?

Existují dva hlavní přístupy k vyřešení problému.

První je snížit počet možných kombinací.

Udělejme mezeru jako nepovinnou přepsáním regulárního výrazu na ^(\w+\s)*\w*$ – vyhledáme libovolný počet slov následovaných mezerou (\w+\s)* a pak (volitelně) poslední slovo \w* .

Tento regulární výraz je ekvivalentní předchozímu (odpovídá stejnému) a funguje dobře:

let regexp = /^(\w+\s)*\w*$/;
let str = "An input string that takes a long time or even makes this regex hang!";

alert( regexp.test(str) ); // false

Proč problém zmizel?

Je to proto, že nyní je místo povinné.

Předchozí regulární výraz, pokud vynecháme mezeru, se stane (\w+)* , což vede k mnoha kombinacím \w+ v rámci jednoho slova

Takže input by mohla být shodná jako dvě opakování \w+ , takto:

\w+  \w+
(inp)(ut)

Nový vzor je jiný:(\w+\s)* určuje opakování slov, za nimiž následuje mezera! input řetězec nelze porovnat jako dvě opakování \w+\s , protože mezera je povinná.

Čas potřebný k vyzkoušení mnoha (ve skutečnosti většiny) kombinací je nyní ušetřen.

Zabránění zpětnému sledování

Není však vždy vhodné přepisovat regulární výraz. Ve výše uvedeném příkladu to bylo snadné, ale není vždy zřejmé, jak to udělat.

Kromě toho je přepsaný regulární výraz obvykle složitější a to není dobré. Regexpy jsou dostatečně složité bez zvláštního úsilí.

Naštěstí existuje alternativní přístup. Můžeme zakázat zpětné sledování pro kvantifikátor.

Kořenem problému je, že motor regulárních výrazů zkouší mnoho kombinací, které jsou pro člověka zjevně špatné.

Např. v regulárním výrazu (\d+)*$ pro člověka je zřejmé, že + by neměl ustupovat. Pokud nahradíme jeden \d+ se dvěma samostatnými \d+\d+ , nic se nemění:

\d+........
(123456789)!

\d+...\d+....
(1234)(56789)!

A v původním příkladu ^(\w+\s?)*$ můžeme chtít zakázat zpětné sledování v \w+ . To je:\w+ by měl odpovídat celému slovu s maximální možnou délkou. Není třeba snižovat počet opakování v \w+ nebo jej rozdělit na dvě slova \w+\w+ a tak dále.

Moderní motory regulárních výrazů k tomu podporují přivlastňovací kvantifikátory. Běžné kvantifikátory se stanou přivlastňovacími, pokud přidáme + po nich. To znamená, že používáme \d++ místo \d+ zastavit + od zpětného sledování.

Přivlastňovací kvantifikátory jsou ve skutečnosti jednodušší než „běžné“. Shodují se s tolika, kolik jen mohou, bez jakéhokoli ustupování. Proces vyhledávání bez zpětného sledování je jednodušší.

Existují také takzvané „skupiny atomového zachycení“ – způsob, jak zakázat zpětné sledování v závorkách.

...Ale špatná zpráva je, že bohužel v JavaScriptu nejsou podporovány.

Můžeme je však emulovat pomocí „dopředné transformace“.

Očekávejte záchranu!

Takže jsme se dostali ke skutečně pokročilým tématům. Chtěli bychom kvantifikátor, například + necouvat, protože ustupovat někdy nemá smysl.

Vzor, který zabere tolik opakování \w pokud možno bez zpětného sledování je:(?=(\w+))\1 . Samozřejmě bychom mohli použít jiný vzor místo \w .

To se může zdát zvláštní, ale ve skutečnosti je to velmi jednoduchá transformace.

Pojďme to dešifrovat:

  • Lookahead ?= očekává nejdelší slovo \w+ počínaje aktuální pozicí.
  • Obsah závorek s ?=... neukládá motor do paměti, takže zabalte \w+ do závorek. Poté si motor zapamatuje jejich obsah
  • …A dovolte nám na to odkazovat ve vzoru jako \1 .

To znamená:díváme se dopředu – a pokud je tam slovo \w+ , pak jej přiřaďte jako \1 .

Proč? Je to proto, že dopředný dotaz najde slovo \w+ jako celek a zachytíme jej do vzoru pomocí \1 . Takže jsme v podstatě implementovali přivlastňovací plus + kvantifikátor. Zachycuje pouze celé slovo \w+ , není jeho součástí.

Například ve slově JavaScript nemusí odpovídat pouze Java , ale vynechejte Script aby odpovídal zbytku vzoru.

Zde je srovnání dvou vzorů:

alert( "JavaScript".match(/\w+Script/)); // JavaScript
alert( "JavaScript".match(/(?=(\w+))\1Script/)); // null
  1. V první variantě \w+ nejprve zachytí celé slovo JavaScript ale pak + vrací zpět znak po znaku, aby se pokusil porovnat zbytek vzoru, dokud to nakonec neuspěje (když \w+ odpovídá Java ).
  2. Ve druhé variantě (?=(\w+)) podívá se dopředu a najde slovo JavaScript , který je zahrnut do vzoru jako celku pomocí \1 , takže nezbývá žádný způsob, jak najít Script po něm.

Do (?=(\w+))\1 můžeme vložit složitější regulární výraz místo \w , když potřebujeme zakázat zpětné sledování pro + po něm.

Poznámka:

Více o vztahu mezi přivlastňovacími kvantifikátory a dopřednou orientací naleznete v článcích Regex:Emulate Atomic Grouping (and Possessive Quantifiers) with LookAhead a Mimicking Atomic Groups.

Pojďme přepsat první příklad pomocí dopředného vyhledávání, abychom zabránili zpětnému sledování:

let regexp = /^((?=(\w+))\2\s?)*$/;

alert( regexp.test("A good string") ); // true

let str = "An input string that takes a long time or even makes this regex hang!";

alert( regexp.test(str) ); // false, works and fast!

Zde \2 se používá místo \1 , protože existují další vnější závorky. Abychom se nepletli s čísly, můžeme závorce pojmenovat, např. (?<word>\w+) .

// parentheses are named ?<word>, referenced as \k<word>
let regexp = /^((?=(?<word>\w+))\k<word>\s?)*$/;

let str = "An input string that takes a long time or even makes this regex hang!";

alert( regexp.test(str) ); // false

alert( regexp.test("A correct string") ); // true

Problém popsaný v tomto článku se nazývá „katastrofický backtracking“.

Probrali jsme dva způsoby, jak to vyřešit:

  • Přepište regulární výraz, abyste snížili počet možných kombinací.
  • Zabraňte zpětnému sledování.