În timp ce cuantificatorii lacomi (greedy: *, +) consumă cât mai mult text posibil dar sunt dispuși să cedeze caractere înapoi dacă restul expresiei o cere (făcând backtracking), cuantificatorii posesivi (notați cu un plus suplimentar: *+, ++, ?+, {m,n}+) consumă tot ce pot și nu cedează niciodată caracterele consumate!
Comparație practică: Greedy vs. Possessive
// Text de test: "12345a"
// Șablon Greedy: \d+5
// 1. \d+ consumă "12345"
// 2. Motorul vrea '5', dar a ajuns la 'a'.
// 3. Backtracking: \d+ cedează caracterul '5', iar '5' se potrivește! Meci reușit.
// Șablon Posesiv: \d++5
// 1. \d++ consumă "12345"
// 2. Motorul vrea '5', dar a ajuns la 'a'.
// 3. Deoarece \d++ este POSESIV, refuză să facă backtracking!
// 4. Meciul eșuează INSTANTANEU, economisind zeci de mii de cicluri CPU!De ce sunt esențiali cuantificatorii posesivi împotriva ReDoS?
Când parsați șiruri ghilimate sau tag-uri cu expresii de forma "[^"]*", un șir de intrare invalid cu mii de caractere care nu are ghilimeaua de închidere poate duce la blocarea completă a procesorului. Folosind un cuantificator posesiv:
" [^"\\]*+ "motorul consumă tot textul dintr-o singură trecere. Dacă ghilimeaua finală lipsește, eșuează imediat în timp $O(n)$, fără a încerca combinații inutile în buclă!
Tabelul Cuantificatorilor Posesivi
| Cuantificator Greedy | Echivalent Posesiv | Comportament |
|---|---|---|
* (0 sau mai multe) |
*+ |
Consumă toate potrivirile și nu cedează niciun caracter înapoi. |
+ (1 sau mai multe) |
++ |
Consumă minim 1 caracter și păstrează tot ce găsește fără backtracking. |
? (0 sau 1) |
?+ |
Consumă caracterul opțional dacă există și nu permite renunțarea la el. |
{min,max} |
{min,max}+ |
Se potrivește în intervalul dat fără a reduce numărul de elemente la eșec. |