Wie Endlosschleifen in .NET RegEx Klasse zu vermeiden?

StackOverflow https://stackoverflow.com/questions/1200655

  •  05-07-2019
  •  | 
  •  

Frage

Haben Sie eine einfache Aufgabe, einen XPath-Ausdruck und gibt einen Präfix zu erhalten, die die Eltern des Knotens übereinstimmt, (könnte) ausgewählt.

Beispiel: 

/aaa/bbb       =>   /aaa
/aaa/bbb/ccc   =>   /aaa/bbb
/aaa/bbb/ccc[@x='1' and @y="/aaa[name='z']"] => /aaa/bbb

Da die Muster in den eckigen Klammern können Klammern in Anführungszeichen enthalten, habe ich beschlossen, zu versuchen, dieses von regulären Ausdrücken mit der Nutzung zu erreichen. Hier ist ein Code-Snippet: 

string input =
    "/aaa/bbb/ccc[@x='1' and @y=\"/aaa[name='z'] \"]";
                                            //  ^-- remove space for no loop
string pattern = @"/[a-zA-Z0-9]+(\[([^]]*(]"")?)+])?$";

System.Text.RegularExpressions.Regex re =
    new System.Text.RegularExpressions.Regex(pattern);
bool ismatch = re.IsMatch(input); // <== Infinite loop in here
// some code based on the match

Da die Muster ziemlich regelmäßig sind, suchte ich nach ‚/‘ gefolgt von indentifier durch eine optionale Gruppe gefolgt, die am Ende der Zeichenfolge entspricht (....)? $

Der Code arbeiten seemd aber mit unterschiedlichen Werten für die Eingabezeichenfolge zu spielen, fand ich, dass einfach durch ein Leerzeichen eingefügt (in der Stelle im Kommentar angezeigt), die .NET IsMatch Funktion in eine Endlosschleife wird, wobei alle CPU wird es.

Nun, unabhängig davon, ob diese Muster eines regulären Ausdrucks ist das beste (I komplexer hatte aber vereinfacht es, das Problem zu zeigen), dies scheint, dass RegEx zu zeigen, indem mit irgendetwas nicht trivial kann sehr riskant sein.

Bin ich etwas fehlt? Gibt es eine Möglichkeit zum Schutz vor Endlosschleifen in regulärem Ausdruck?

War es hilfreich?

Lösung

Ok, lassen Sie uns dies brechen dann: 

Input: /aaa/bbb/ccc[@x='1' and @y="/aaa[name='z'] "]
Pattern: /[a-zA-Z0-9]+(\[([^]]*(]")?)+])?$

(ich nehme an, Sie bedeuten \“in Ihrem C # -escaped Zeichenfolge, nicht "" ... Übersetzung von VB.NET?)

Zuerst / [a-zA-Z0-9] + wird durch die erste eckige Klammer verschlingen, so dass: 

Input: [@x='1' and @y="/aaa[name='z'] "]

Die äußere Gruppe (\ [([^]] * (] "")?) +])? $“Sollten übereinstimmen, wenn es 0 oder 1 Instanz vor dem EOL. Der Innenseite So lassen brechen und sehen, ob es passt alles.

Das "[" sofort verschlungen wird, uns mit dem Ausscheiden aus: 

Input: @x='1' and @y="/aaa[name='z'] "]
Pattern: ([^]]*(]")?)+]

Breaking das Muster nach unten: Spiel 0 oder mehr nicht ] Zeichen und dann passen "] 0 oder 1 Mal, und dies zu tun, bis Sie können es nicht. dann versuchen Sie ein ] zu finden und verschlingen danach.

Das Muster Spiele basierend auf [^]] * , bis es erreicht die ] .

Da gibt es einen Raum zwischen ] und ", kann sie nicht eine dieser beiden Zeichen verschlingen, aber die ? nach (] ") erlaubt es wahr sowieso zurückzukehren.

Jetzt haben wir erfolgreich angepasst ([^]] * (] ")?) einmal, aber die + sagt sollten wir zu halten versuchen, es beliebig viele passende mal wir können.

Dies lässt uns mit: 

Input: ] "]

Das Problem hierbei ist, dass dieser Eingang kann Übereinstimmen ([^]] * (] ")?) ein unendlich Mal ohne jemals verschlungen zu werden, und" +“wird es nur zwingen, immer wieder versuchen.

Sie sind im Wesentlichen „1 oder mehr“ Situationen passend zu dem Sie mit „0 oder 1“ etwas anderes „0 oder 1“ von etwas gefolgt entsprechen. Da keiner der beiden Teilmuster in dem verbleibenden Eingang vorhanden ist, hält sie passende 0 von [^]] \ * und 0 von (] ")? in einer Endlosschleife.

Der Eingang nie geschluckt wird, und der Rest des Musters nach dem „+“ wird nie ausgewertet.

(Hoffentlich habe ich die SO-Flucht-of-regex-escape rechts oben).

Andere Tipps

  

Das Problem hierbei ist, dass diese Eingabe übereinstimmen kann ([^]] * (] ")?) Unendlich oft ohne jemals verschlungen zu werden, und‚+‘wird es nur zwingen, immer wieder versuchen.

Das ist eine Hölle eines Fehlers in .NET der RegEx-Implementierung. Reguläre Ausdrücke funktionieren einfach nicht so. Wenn man sie in Automaten drehen, erhalten Sie automatisch die Tatsache erhalten, dass eine unendliche Wiederholung eines leeren String ist immer noch eine leere Zeichenkette.

Mit anderen Worten, jede nicht-Buggy Regex-Engine werden diese Endlosschleife sofort ausführen und mit dem Rest des Regex weiter.

Wenn Sie es vorziehen, reguläre Ausdrücke sind so eine begrenzte Sprache, dass es möglich ist (und einfach) solche Endlosschleifen zu erkennen und zu vermeiden.

Es zeigt, dass mit Code mit etwas nicht trivial riskant sein kann. Sie erstellten Code, der in einer Endlosschleife und der RegEx Compiler verpflichtet führen kann. Nichts Neues, die nicht seit den ersten 20 IF X = 0 THEN GOTO 10.

getan hat

Wenn Sie diese Sorgen sind in einem bestimmten Rande Fall könnten Sie einen Thread für RegEx laichen und tötet sie dann nach einiger vernünftigen Ausführungszeit.

die ursprüngliche Frage zu beantworten (das heißt, wie mit regex Endlosschleife zu vermeiden), hat sich diese einfach geworden mit .Net 4.5, wie Sie einfach eine Auszeit an die Regex Methoden weitergeben können. Es gibt einen internen Zeitgeber, der die Regex Schleife zu stoppen, wenn die Zeit abgelaufen und wirft eine RegexMatchTimeoutException

Zum Beispiel würden Sie tun das folgende 

string input = "/aaa/bbb/ccc[@x='1' and @y=\"/aaa[name='z'] \"]";
string pattern = @"/[a-zA-Z0-9]+(\[([^]]*(]"")?)+])?$";
bool ismatch = Regex.IsMatch(input, pattern, RegexOptions.None, TimeSpan.FromSeconds(5));

Sie können überprüfen MSDN weitere Details

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top