Java Pattern.matcher() friert ein, wenn die passende Zeile \ n

Question

Ich stieß auf ein Problem, das ich ziemlich interessant finde. Ich mache einige grundlegende Parsing von Textdateien, meist durch regex und es friert immer, wenn diese Zeile passend

ftrect 0.7031 57.0313 9.8561 55.5313 "FREIGABE \nQ09_SV01" 

keine Ausnahme ausgelöst wird; Das Programm hängt einfach. Ich poste das Snippet des Programms, das die Situation nachbildet; die kommentierte ist mögliche Standardsituation, aber die andere ist die Problematik. Wenn du das löschst \ n funktioniert es, aber diese geparsten Dateien kommen so aus dem "Blackbox" -System.

Ich kann sicherlich eine Abhilfe schaffen, ich fand es nur interessant, dass es tatsächlich einfriert und hoffte, dass jemand erklären könnte, was passiert. Ich versuchte es auf JDK6u22 und JDK7u21 ...

public static Pattern FTRECT_PATTERN = Pattern.compile(
    "\\s*([\\w]+)?\\:?\\s*ftrect\\s+((\\d*\\.?\\d*\\s?)+)\\s*\"?([\\w\\s\\.\\%\\/\\=]*)?\"?\\s*" 
); 

public static void main(String[] args) { 

// Matcher m = FTRECT_PATTERN.matcher("FOX_BACKGROUND: ftrect 46.1719 18.0556 54.8633 16.5556 \"Schicht\" "); 
    Matcher m = FTRECT_PATTERN.matcher("ftrect 0.7031 57.0313 9.8561 55.5313 \"FREIGABE \\nQ09_SV01\""); 
    System.out.println(m.matches()); 

    for (int i = 0; i <= m.groupCount(); i++) { 
     String string = m.group(i); 
     System.out.println(string); 
    } 
} 

---

Nun, ich entdeckte, dass, wenn ich die Regex diese (durch die \\\\ zur letzten Gruppe) ändern:

public static Pattern FTRECT_PATTERN = Pattern.compile(
    "\\s*([\\w]+)?\\:?\\s*ftrect\\s+((\\d*\\.?\\d*\\s?)+)\\s*\"?([\\w\\\\\\s\\.\\%\\/\\=]*)?\"?\\s*" 
); 

I weiß immer noch nicht, warum keine Ausnahme ausgelöst wird.

Answer 1

Dies geschieht wegen catastrophic backtracking. Ihre Testzeichenfolge enthält einen umgekehrten Schrägstrich (in "...\\n..."), der nicht mit der Zeichenklasse [\w\s\.\%\/\=]* übereinstimmt.

Dies bedeutet, dass die Regex-Engine alle möglichen Permutationen der Zeichenkette "FREIGABE vor dem betreffenden Zeichen ausprobieren muss, bevor sie sich für eine Nicht-Übereinstimmung entscheiden kann.

Das ist eine sehr hohe Zahl, wahrscheinlich für ein paar Stunden den Motor beschäftigt. Nachdem Sie der Zeichenklasse den umgekehrten Schrägstrich hinzugefügt haben, kann die Regex übereinstimmen.

Prävention: Verwendung possessive Quantoren (*+ und ++) nicht hilfreich Rückzieher zu vermeiden:

public static Pattern FTRECT_PATTERN = Pattern.compile("\\s*(\\w*):?\\s*ftrect\\s+((\\b\\d*(?:\\.\\d+)?\\b\\s?)+)\\s*\"?([\\\\\\w\\s.%/=]*+)?\"?\\s*");