Regular Expressions
backa

Vad orsakar Backtracking?

För att hitta en matchning kommer regex-motorn att konsumera tecken en efter en. När en partiell matchning börjar kommer motoren att komma ihåg startpositionen så att den kan gå tillbaka om följande tecken inte slutför matchen.

• Om matchen är klar är det ingen backtracking
• Om matchen inte är fullständig kommer motorn att spåra strängen (som när du spolar tillbaka ett gammalt band) för att försöka hitta en hel matchning.

Till exempel: \d{3}[az]{2} mot strängen abc123def bläddras som sådan:

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

Nu kan vi ändra regex till \d{2}[az]{2} mot samma sträng ( 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

Varför kan backtracking vara en fälla?

Backtracking kan orsakas av valfria kvantifierare eller växelkonstruktioner, eftersom regex-motorn kommer att försöka utforska varje väg. Om du kör regex a+b mot aaaaaaaaaaaaaa finns det ingen match och motorn kommer att hitta det ganska snabbt.

Men om du ändrar regex till (aa*)+b antalet kombinationer att växa ganska snabbt, och de flesta (inte optimerade) motorer kommer att försöka utforska alla vägar och tar en evighet för att försöka hitta en match eller kasta en timeout undantag. Detta kallas katastrofal backtracking .

Naturligtvis verkar (aa*)+b ett nybörjarfel men det är här för att illustrera poängen och ibland kommer du att sluta med samma problem men med mer komplicerade mönster.

Ett mer extremt fall av katastrofal backtracking inträffar med regex (x+x+)+y (du har förmodligen sett det förut här och här ), som behöver exponentiell tid för att räkna ut att en sträng som innehåller x s och inget annat (t.ex. xxxxxxxxxxxxxxxxxxxx ) matchar inte det.

Hur undviks det?

Var så specifik som möjligt, minska så mycket som möjligt de möjliga vägarna. Observera att vissa regex-matchare inte är sårbara för backtracking, till exempel de som ingår i awk eller grep eftersom de är baserade på Thompson NFA .