Java Pattern.matcher() si blocca quando corrisponde alla riga che contiene \ n

Question

Mi sono imbattuto in un problema che trovo molto interessante. Sto facendo alcune analisi di base di file di testo per lo più da regex e si blocca sempre quando corrispondenza di questa linea

ftrect 0.7031 57.0313 9.8561 55.5313 "FREIGABE \nQ09_SV01" 

Non viene generata un'eccezione; il programma si blocca. Sto postando il frammento del programma che ricrea la situazione; il commento è possibile situazione standard, ma l'altro è il problematico. Se cancelli il \ n funziona, ma questi file analizzati vengono in questo modo dal sistema "blackbox".

Sicuramente posso fare una soluzione, ho solo trovato interessante il fatto che in realtà si congela e spera che qualcuno possa spiegare cosa sta succedendo. Ho provato su JDK6u22 e 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); 
    } 
} 

---

Beh, ho scoperto che se modifico la regex a questo (aggiungendo il \\\\ all'ultimo gruppo):

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

I ancora non so perché non viene lanciata alcuna eccezione.

Answer 1

Questo succede a causa di catastrophic backtracking. La stringa di test contiene una barra rovesciata letterale (in "...\\n...") a cui non corrisponde la classe di caratteri [\w\s\.\%\/\=]*.

Ciò significa che il motore regex deve provare tutte le possibili permutazioni della stringa "FREIGABE che precede il carattere incriminato prima di poter decidere su una non corrispondenza.

Questo è un numero molto elevato, mantenendo il motore occupato per alcune ore, probabilmente. Una volta aggiunta la barra rovesciata alla classe di caratteri, la regex può corrispondere.

Prevenzione: Usa quantificatori possessivi (*+ e ++) per evitare inutili backtracking:

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

Una migliore soluzione ripulita sarebbe:

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