Im en utilisant cette regex pour obtenir le contenu d'un tag dans un fichier.Javascript regex se bloque (en utilisant v8)
var regex = new RegExp("<tag:main>((?:.|\\s)*)</tag:main>");
Cela provoque le blocage du moteur v8 indéfiniment. Maintenant, si j'utilise new RegExp("<tag:main>([\s\S]*)</tag:main>"), tout va bien.
Quelqu'un a une idée pourquoi le premier prend trop de temps?
Ce retour en arrière catastrophique sur de longues séquences d'espaces se produisant après la dernière étiquette </tag:main> de fermeture. Considérons le cas où la chaîne en question se termine par 100 espaces. Tout d'abord, il correspond à tous avec le . sur la gauche de l'alternance. Cela échoue parce qu'il n'y a pas de balise de fermeture, donc il essaie de faire correspondre le dernier caractère avec le \s à la place. Cela échoue aussi, donc il essaie de faire correspondre l'avant-dernier espace comme \s et le dernier espace comme .. Cela échoue (toujours pas de balise de fermeture) donc il essaie le dernier espace comme \s. Lorsque cela échoue, il correspond à l'espace avant-dernier en tant que \s et essaie les 4 façons de faire correspondre les deux derniers espaces. Lorsque cela échoue, il essaie l'espace avant-dernier comme \s et les 8 façons sur les 3 dernières cases. Puis 16, 32 etc. L'univers se termine avant qu'il n'atteigne l'espace du 100ème jusqu'au dernier.
Différentes machines virtuelles ont des réactions différentes aux correspondances d'expression rationnelle qui prennent une éternité en raison d'un retour arrière catastrophique. Certains signaleront simplement «pas de correspondance». En V8, c'est comme écrire n'importe quelle autre boucle infinie ou quasi-infinie.
L'utilisation non gourmande * fera ce que vous voulez (vous voulez arrêter au premier </tag:main>, pas le dernier), mais encore faire marche arrière catastrophique pour les longues chaînes d'espaces où la séquence de fermeture est manquante. S'assurer que les mêmes caractères dans la parenthèse intérieure ne peuvent pas correspondre aux deux côtés de l'alternance réduira le problème d'une exponentielle à une qui est linéaire dans la longueur de la chaîne. Utilisez une classe de caractères au lieu d'une alternance ou placez \n sur le côté droit de la barre d'alternance. \n est disjoint avec . donc si vous frappez une longue séquence d'espaces, le moteur regexp n'essaie pas toutes les combinaisons gauche-droite-gauche etc. avant de terminer.
Bonne explication. Savez-vous si le point comprend aussi? –
@Martin: en JavaScript, '.' est équivalent à' [^ \ r \ n \ u2028 \ u2029] ' –
@Alan - Merci! –
Je présume qu'il s'agit d'un suivi catastrophique.
Je pense que cette partie du problème pourrait bien être que le point et \ s ne sont pas mutuellement exclusifs.
Si je change votre expression
<tag:main>((?:.|[\r\n])*)</tag:main>
et l'exécuter dans le débogueur copain Regex il échoue beaucoup plus rapide dans le cas où la chaîne de test n'est pas un match.
. | \ S doit correspondre à tous les caractères. Car . correspond à tous les caractères sauf la nouvelle ligne. – Engwan
Je ne pense pas que ça va faire ça. J'ai collé votre Regex dans RegexBuddy et j'ai collé son arbre de commentaires dans mon post. –
Vous devez supprimer l'extra \ avant de coller à RegexBuddy. Le \\ est utilisé car il s'agit d'une chaîne javascript transmise au constructeur RegExp. – Engwan
Au lieu de (?:.|\s)*, vous pouvez utiliser [^]* pour faire correspondre n'importe quel caractère, y compris les différentes formes de saut de ligne.
Il n'y a pas d'alternance, donc pas de risque de retour en arrière catastrophique.
la création de la regex se bloque ou l'application de celui-ci? La ligne que vous avez posté fonctionne bien pour moi – cobbal
La création ne se bloque pas, seulement en l'utilisant via test ou match. Utilisation de longues chaînes – Engwan
Avez-vous essayé un jeu non gourmand?'var regex = new RegExp (" ((?:. | \\ s) *?) ");'. Votre expression rationnelle peut provoquer des problèmes s'il existe plusieurs éléments de balise dans le document. –