Regular Expressions
backtracking

Wat veroorzaakt Backtracking?

Om een match te vinden, verbruikt de regex-engine tekens één voor één. Wanneer een gedeeltelijke wedstrijd begint, onthoudt de motor de startpositie zodat deze terug kan gaan als de volgende tekens de wedstrijd niet voltooien.

• Als de wedstrijd is voltooid, is er geen backtracking
• Als de wedstrijd niet compleet is, zal de motor de reeks terugdraaien (zoals wanneer je een oude band terugspoelt) om te proberen een hele wedstrijd te vinden.

Bijvoorbeeld: \d{3}[az]{2} tegen de string abc123def wordt als zodanig doorzocht:

abc123def
^ Does not match \d
abc123def
 ^ Does not match \d
abc123def
  ^ Does not match \d
abc123def
   ^ Does match \d (first one)
abc123def
    ^ Does match \d (second one)
abc123def
     ^ Does match \d (third one)
abc123def
      ^ Does match [a-z] (first one)
abc123def
       ^ Does match [a-z] (second one)
           MATCH FOUND

Laten we nu de regex wijzigen in \d{2}[az]{2} tegen dezelfde string ( abc123def ):

abc123def
^ Does not match \d
abc123def
 ^ Does not match \d
abc123def
  ^ Does not match \d
abc123def
   ^ Does match \d (first one)
abc123def
    ^ Does match \d (second one)
abc123def
     ^ Does not match [a-z]
abc123def
    ^ BACKTRACK to catch \d{2} => (23)
abc123def
      ^ Does match [a-z] (first one)
abc123def
       ^ Does match [a-z] (second one)
           MATCH FOUND

Waarom kan backtracking een valstrik zijn?

Backtracking kan worden veroorzaakt door optionele kwantificators of alternatieconstructies, omdat de regex-engine elk pad probeert te verkennen. Als je de regex a+b tegen aaaaaaaaaaaaaa uitvoert, is er geen match en zal de motor het behoorlijk snel vinden.

Maar als je de regex wijzigt in (aa*)+b het aantal combinaties behoorlijk snel groeien, en de meeste (niet geoptimaliseerde) motoren zullen proberen alle paden te verkennen en zullen een eeuwigheid duren om te proberen een match te vinden of een te gooien time-out uitzondering. Dit wordt catastrofale backtracking genoemd .

Natuurlijk lijkt (aa*)+b een newbie-fout, maar het is hier om het punt te illustreren en soms krijg je hetzelfde probleem, maar met ingewikkelder patronen.

Een meer extreem geval van catastrofale backtracking treedt op met de regex (x+x+)+y (je hebt het waarschijnlijk hier en hier eerder gezien ), die exponentiële tijd nodig heeft om erachter te komen dat een string die x s bevat en niets anders (bijv. xxxxxxxxxxxxxxxxxxxx ) komen niet overeen.

Hoe het te vermijden?

Wees zo specifiek mogelijk, verminder zoveel mogelijk de mogelijke paden. Merk op dat sommige regex-matchers niet kwetsbaar zijn voor backtracking, zoals die opgenomen in awk of grep omdat ze gebaseerd zijn op Thompson NFA .