Java Pattern.matcher() zawiesza się podczas dopasowywania wiersza zawierającego \ n

Question

Natknąłem się na problem, który uważam za interesujący. Robię kilka podstawowych parsowanie plików tekstowych głównie przez regex i zawsze zawiesza się podczas dopasowania tej linii

ftrect 0.7031 57.0313 9.8561 55.5313 "FREIGABE \nQ09_SV01" 

Nie wyjątek spowodowany; program się zawiesił. Publikuję fragment programu, który odtwarza sytuację; komentowana jedna możliwa sytuacja standardowa, ale druga jest problematyczna. Jeśli usuniesz \ n to działa, ale te sparsowane pliki przychodzą w ten sposób z systemu "blackbox".

Z pewnością mogę obejść ten problem, ale uznałem za interesujące tylko to, że faktycznie zawiesza się i miał nadzieję, że ktoś może wyjaśnić, co się dzieje. Próbowałem go na JDK6u22 i 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); 
    } 
} 

---

Dobrze, odkryłem, że jeśli będę modyfikować regex do tego (dodając \\\\ do ostatniej grupy):

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

I wciąż nie wiem, dlaczego nie został zgłoszony wyjątek.

Answer 1

Dzieje się tak z powodu catastrophic backtracking. Twój ciąg testowy zawiera literowy ukośnik odwrotny (w "...\\n..."), który nie jest zgodny z klasą znaków [\w\s\.\%\/\=]*.

Oznacza to, że silnik regex musi wypróbować wszystkie możliwe permutacje ciągu "FREIGABE, które poprzedza znak przestępczy, zanim będzie mógł zdecydować o braku zgodności.

To bardzo duża liczba, prawdopodobnie utrzymująca silnik zajęty przez kilka godzin. Po dodaniu odwrotnego ukośnika do klasy znaków, wyrażenie regularne może się równać.

Zapobieganie: Stosować dzierżawcze kwantyfikatorów (*+ i ++), aby uniknąć unhelpful Backtracking:

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

Lepszym, oczyszczone-up rozwiązanie byłoby:

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