Backtracking : notions

Lorsqu'un quantificateur gourmand « en fait trop », le moteur fait marche arrière : revenez en arrière, essayez une autre configuration, réessayez. Allez les motifs simples sont invisibles ; sur des patrons mal écrits cela peut devenir exponentiel et bloquez le navigateur pendant quelques secondes. C'est la racine de ReDoS (expression régulière déni de service).

Pattern: .*\d
Sample:  abc123def
Steps:
  1.  .*  consuma tutto: "abc123def"
  2.  \d  fallisce (fine stringa).
  3.  Backtrack: .* lascia 'f' -> "abc123de", \d fallisce su 'f'.
  4.  Backtrack: .* lascia 'ef' -> "abc123d", \d fallisce su 'e'.
  5.  ... e cosi' via finche' \d trova una cifra: match = "abc123" + "?"... in realta'
       il pattern matcha "abc123" perche' .* lascia "def" e \d cerca su '3'? No: il backtrack
       continua e .* finisce per essere "abc12", \d=3.  Match finale: "abc123".

Le moteur y arrive toujours, mais si le quantificateur gourmand l'a dedans un autre quantificateur glouton (par exemple (a+)+), le nombre de les configurations à essayer peuvent exploser.

Modèles catastrophiques

Pattern: (a+)+b
Sample:  aaaaaaaaaaaaaaaaaaaaa

Rien de final b → le motif échoue, mais le moteur essaie d'y arriver toutes les partitions possibles de a. Croissance exponentielle : avec 30 a vous pouvez attendre des heures.

Dangers du retour en arrière et du ReDoS

Lorsqu'un modèle comprend des quantificateurs superposés ou imbriqués (par exemple (a+)+), le moteur évalue un nombre exponentiel de combinaisons avant d'échouer. Le remplacement des caractères génériques par l'exclusion de classes de caractères réduit considérablement les chemins de retour en arrière.

Essayez-le vous-même

Exercice de révision

Défi supplémentaire