Ich benutze diese Regex, um den Inhalt eines Tags in einer Datei zu erhalten.Javascript Regex hängt (mit v8)
var regex = new RegExp("<tag:main>((?:.|\\s)*)</tag:main>");
Dies führt dazu, dass die v8-Engine auf unbestimmte Zeit hängen bleibt.
Jetzt, wenn ich new RegExp("<tag:main>([\s\S]*)</tag:main>") verwende, ist alles gut.
Hat jemand eine Idee, warum der erste zu lange dauert?
Diese katastrophale Backtracks auf lange Sequenzen von Leerzeichen, die nach dem letzten schließenden </tag:main> Tag auftreten. Betrachten Sie den Fall, in dem die Betreffzeile mit 100 Leerzeichen endet. Zuerst passt sie alle mit der . auf der linken Seite der Abwechslung. Das scheitert, weil es kein schließendes Tag gibt, also versucht es, das letzte Zeichen mit dem \s zu vergleichen. Das scheitert auch, also versucht es, das vorletzte Leerzeichen als \s und das letzte Leerzeichen als . zu vergleichen. Das scheitert (immer noch kein schließendes Tag), also versucht es das letzte Leerzeichen als \s. Wenn dies fehlschlägt, wird das drittletzte Leerzeichen als \s abgeglichen und alle vier Möglichkeiten zum Abgleich der letzten beiden Leerzeichen werden verwendet. Wenn das fehlschlägt, versucht es das viertletzte Leerzeichen als \s und alle 8 Wege auf den letzten 3 Leerzeichen. Dann 16, 32 usw. Das Universum endet, bevor es zum 100.letzten Raum kommt.
Verschiedene VMs reagieren unterschiedlich auf Regexp-Matches, die wegen katastrophaler Rückverfolgung ewig dauern. Einige werden einfach "keine Übereinstimmung" melden. In V8 ist es wie das Schreiben einer anderen unendlichen oder nahezu unendlichen Schleife.
Die Verwendung von nicht-gierigen * wird tun, was Sie wollen (wollen Sie bei der ersten </tag:main> zu stoppen, nicht die letzte), wird aber immer noch katastrophal Rückzieher für lange Ketten von Räumen, in denen die Schließfolge fehlt.
Wenn sichergestellt wird, dass die gleichen Zeichen in der inneren Klammer nicht mit beiden Seiten der Alternation übereinstimmen, verringert sich das Problem von einer exponentiellen Eins zu eins, die in der Länge der Zeichenfolge linear ist. Verwenden Sie eine Zeichenklasse anstelle einer Alternation oder setzen Sie \n auf die rechte Seite der Alternationsleiste. \n ist disjunkt mit ., also, wenn Sie eine lange Folge von Leerzeichen treffen, versucht die Regexp-Engine nicht alle Links-rechts-links-Kombinationen vor dem Beenden.
Gute Erklärung. Wissen Sie, ob dot auch \ r enthält? –
@Martin: in JavaScript, '.' ist äquivalent zu' [^ \ r \ n \ u2028 \ u2029] ' –
@Alan - Danke! –
Ich vermute, dass es katastrophal zurück Tracking ist.
Ich denke, dass ein Teil des Problems gut sein kann, dass der Punkt und \ s sich nicht gegenseitig ausschließen.
Wenn ich Ihren Ausdruck zu
<tag:main>((?:.|[\r\n])*)</tag:main>
und führen Sie es im Debugger Regex Buddy ändern schlägt es viel schneller in dem Fall, dass der Test-String kein Spiel ist.
. | \ S entspricht allen Zeichen. Weil . passt alle Zeichen außer neue Zeile. – Engwan
Ich glaube nicht, dass es das tun wird. Ich habe Ihren Regex in RegexBuddy eingefügt und seinen Kommentarbaum in meinen Beitrag eingefügt. –
Sie sollten das Extra vor dem Einfügen in RegexBuddy entfernen. Das \\ wird verwendet, weil es eine JavaScript-Zeichenfolge ist, die an den RegExp-Konstruktor übergeben wird. – Engwan
Anstelle von (?:.|\s)* können Sie [^]* verwenden, um jedes Zeichen einschließlich verschiedener Formen von Newline zu finden.
Es gibt keinen Wechsel, also kein Risiko von katastrophalem Backtracking.
die Erstellung der Regex hängt oder die Anwendung von ihm? Die Zeile, die Sie gepostet haben, funktioniert gut für mich – cobbal
Die Erstellung hängt nicht, nur über Test oder Match. mit langen Strings – Engwan
Haben Sie ein nicht-gieriges Spiel ausprobiert?'var regex = new RegExp (" ((?:. | \\ s) *?) ");'. Ihre Regexp-Datei kann Probleme verursachen, wenn mehrere Tag-Elemente im Dokument vorhanden sind. –