Regular Expressions
Retour en arrière

Qu'est-ce qui cause le retour en arrière?

Pour trouver une correspondance, le moteur regex consommera des caractères un par un. Lorsqu'un match partiel commence, le moteur se souviendra de la position de départ afin de pouvoir revenir en arrière si les personnages suivants ne terminent pas le match.

• Si le match est terminé, il n'y a pas de retour en arrière
• Si le match n'est pas terminé, le moteur va revenir en arrière sur la chaîne (comme lorsque vous rembobinez une vieille bande) pour essayer de trouver une correspondance complète.

Par exemple: \d{3}[az]{2} contre la chaîne abc123def sera parcouru comme tel:

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

Modifions maintenant le regex à \d{2}[az]{2} contre la même chaîne ( 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

Pourquoi le retour en arrière peut-il être un piège?

Le backtracking peut être provoqué par des quantificateurs optionnels ou des constructions alternées, car le moteur regex essaiera d'explorer tous les chemins. Si vous exécutez la regex a+b contre aaaaaaaaaaaaaa il n'y a pas de correspondance et le moteur le trouvera assez rapidement.

Mais si vous modifiez le regex à (aa*)+b le nombre de combinaisons augmentera assez rapidement et la plupart des moteurs (non optimisés) tenteront d'explorer tous les chemins et prendront une éternité pour essayer de trouver une correspondance ou exception de délai d'attente. Cela s'appelle un retour en arrière catastrophique .

Bien sûr, (aa*)+b semble être une erreur de débutant mais il est là pour illustrer ce point et parfois vous vous retrouverez avec le même problème mais avec des modèles plus compliqués.

Un cas plus extrême de retour en arrière catastrophique se produit avec le regex (x+x+)+y (vous l'avez probablement déjà vu ici et ici ), qui nécessite un temps exponentiel pour déterminer qu'une chaîne contenant x s et rien d'autre (par exemple, xxxxxxxxxxxxxxxxxxxx ) ne correspondent pas.

Comment l'éviter

Soyez aussi précis que possible, réduisez autant que possible les chemins possibles. Notez que certains appariements de regex ne sont pas vulnérables au backtracking, comme ceux inclus dans awk ou grep car ils sont basés sur Thompson NFA .