Backtracking: o privire de ansamblu

Când un cuantificator lacom „depășește”, motorul efectuează backtracking: se dă înapoi, încearcă o altă configurație, reîncearcă. Pe modele simple ea este invizibil; pe modele prost scrise poate deveni exponenţial şi înghețați browserul pentru câteva secunde. Este rădăcina lui ReDoS (Regular expresia Refuzarea serviciului).

Pattern: .*\d
Sample:  abc123def
Steps:
  1.  .*  consumes everything: "abc123def"
  2.  \d  fails (end of string).
  3.  Backtrack: .* drops 'f' -> "abc123de", \d fails on 'f'.
  4.  Backtrack: .* drops 'ef' -> "abc123d", \d fails on 'e'.
  5.  ... and so on until \d finds a digit: match = "abc123" + "?"... actually
       the pattern matches "abc123" because .* leaves "def" and \d looks at '3'? No: the
       backtrack continues and .* ends up being "abc12", \d=3.  Final match: "abc123".

Motorul ajunge mereu acolo, dar dacă un cuantificator lacom conține un alt cuantificator lacom (de exemplu, (a+)+), numărul de configurații a încerca poate exploda.

Tipare catastrofale

Pattern: (a+)+b
Sample:  aaaaaaaaaaaaaaaaaaaaa

Fără urmă b → modelul eșuează, dar pentru a ajunge acolo motorul încearcă fiecare posibilă partiție a a-urilor. Creștere exponențială: cu 30 as puteți așteptați ore întregi.

Pericole de backtracking și ReDoS

Când un model conține cuantificatori suprapusi sau imbricați (de exemplu, (a+)+), motorul evaluează un număr exponențial de căi înainte de a eșua. Înlocuirea wildcard-urilor generice cu excluderea claselor de caractere reduce dramatic căile de întoarcere.

Încearcă

Exercițiu de revizuire

Provocare suplimentară