Pattern.matches() dà StackOverflowError

Question

sto usando Pattern.matches di java per abbinare un blocco di dati ad una regex. Il blocco di dati può essere una singola riga o più righe. Il problema è che una volta che i miei dati diventano più di 15 righe (in genere più di 17-18 linee), inizio a ottenere stackoverflowerror. Per i dati inferiori a 15 righe, la regex funziona correttamente.

l'espressione regolare è di questo formato:
domainname -> spazio ->, -> spazio -> Numero -> spazio ->, -> spazio -> Numero -> nuova linea

String regex = "^(([a-zA-Z0-9][a-zA-Z0-9\\-]*\\.)+([a-zA-Z]{2,})\\s*,\\s*\\d+\\s*,\\s*\\d+(\\r?\\n)?)+$"; 

I dati blocco io uso di prova contro questa regex questo

abc.com, 123, 456 
abc.com, 123, 456 
abc.com, 123, 456 
abc.com, 123, 456 
abc.com, 123, 456 
abc.com, 123, 456 
abc.com, 123, 456 
abc.com, 123, 456 
abc.com, 123, 456 
abc.com, 123, 456 
abc.com, 123, 456 
abc.com, 123, 456 
abc.com, 123, 456 
abc.com, 123, 456 
abc.com, 123, 456 
abc.com, 123, 456 
abc.com, 123, 456 
abc.com, 123, 456 

questo è il codice:

String regex = "^(([a-zA-Z0-9][a-zA-Z0-9\\-]*\\.)+([a-zA-Z]{2,})\\s*,\\s*\\d+\\s*,\\s*\\d+(\\r?\\n)?)+$"; 
boolean valid = Pattern.matches(regex, data); //fails here 

Answer 1

Non riesco a spiegarti il ​​motivo di questo errore; la regex stessa va bene e non è soggetta a backtracking catastrofico o qualsiasi altro errore ovvio.

forse si può ridurre il numero di posizioni backtracking motore regex salva utilizzando possessive quantifiers (++ invece di +, *+ invece di *, {2,}+ invece di {2,} etc.). Inoltre, non è necessario ai gruppi di cattura (grazie Thomas), in modo che io ho cambiato in quelli non-cattura:

"(?:(?:[a-zA-Z0-9][a-zA-Z0-9-]*+\\.)++([a-zA-Z]{2,}+)\\s*+,\\s*+\\d++\\s*+,\\s*+\\d++(\r?+\n)?+)++" 

Questo non cambierà il comportamento del regex (tranne che per la rimozione di gli ancoraggi non necessari dal momento che stai usando Pattern.matches()), ma forse aiuta ad evitare StackOverflow. Non ho un Java SDK installato, quindi non posso testarlo da solo, però.

Answer 2

Ho riprodotto questo problema, ma solo per le stringhe molto più grandi.

$ java -version 
java version "1.6.0_22" 
OpenJDK Runtime Environment (IcedTea6 1.10.2) (6b22-1.10.2-0ubuntu1~11.04.1) 
OpenJDK 64-Bit Server VM (build 20.0-b11, mixed mode) 

mio codice di prova:

public class Testje 
{ 
    public static void main(String... args) 
    { 
     String regex = "^(([a-zA-Z0-9][a-zA-Z0-9\\-]*\\.)+([a-zA-Z]{2,})\\s*,\\s*\\d+\\s*,\\s*\\d+(\\r?\\n)?)+$"; 
     String data = ""; 
     for (int i = 0; i<224; i++) data += "abc.com, 123, 456\n"; 
     System.out.println(data.matches(regex)); 
    } 
} 

Per qualcosa di più piccolo di 224 in quella per ciclo, il codice viene eseguito bene. Per 224 e più copie di quella linea, ottengo un'enorme traccia di stack.

Oh, si noti che l'uso? (: I gruppi non cambia la dimensione della stringa che funziona ancora

Answer 3

Si potrebbe provare a utilizzare i gruppi atomici ((?>expression)) per evitare il backtracking:.

Ecco un test che non è riuscito con un blocco di 1000 linee utilizzando il regex ma riesce ora (vuole un po ', quindi solo ho provato con 20000 :)):

String regex = "(?>(?>[a-zA-Z0-9][a-zA-Z0-9\\-]*\\.)+(?>[a-zA-Z]{2,})\\s*,\\s*\\d+\\s*,\\s*\\d+(?>\\r?\\n)?)+"; 

StringBuilder input = new StringBuilder(); 

for(int i = 0; i < 1000000; ++i) { 
    input.append("abc.com, 123, 456\n"); 
} 

Pattern p = Pattern.compile(regex); 
Matcher m = p.matcher(input); 

System.out.println(m.matches()); 

Così, dopo tutto, potrebbe ancora essere una marcia indietro problema.

Aggiornamento: basta lasciare che la corsa di prova con 20000 righe e ancora non sicuro. Questo è almeno 20 volte più di prima. :)

Aggiornamento 2: guardando di nuovo il mio test ho trovato la parte lenta, la concatenazione di stringhe. (O..O).Ho aggiornato il test e usato 1 milione di linee, ancora non esito negativo. :)

Answer 4

Il problema è che la tua espressione regolare è troppo complicata. Ogni riga di input elaborata produce (credo) 10 punti di backtrack, e almeno alcuni di questi sembrano essere gestiti dal ricircolo del motore regex. Potrebbero essere alcune centinaia di frame di stack che sarebbero sufficienti per darti StackOverflowError.

IMO, è necessario modificare il modello in modo che possa corrispondere a un gruppo/linea di dati. Quindi chiamare più volte Matcher.find per analizzare ogni riga. Mi aspetto che scoprirai che questo è più veloce.

---

Ottimizzare l'espressione regolare in altri modi, pur cercando di abbinare l'intero blocco in una sola volta, probabilmente non funzionerà. Potresti riuscire a far corrispondere N volte più righe di dati, ma man mano che aumenti il ​​numero di righe nell'input potresti ricorrere nuovamente allo stesso problema.

E anche se si riesce a farlo funzionare come espressione regolare su più righe, è possibile che non funzioni con altre implementazioni delle librerie di espressioni regolari di Java; per esempio. nei vecchi JRE Oracle o implementazioni non Oracle.

---

Sono d'accordo con le altre risposte che questo non è un esempio di "backtracking catastrofico". Piuttosto si tratta di un'interazione tra il modo in cui il motore regex gestisce i punti di backtrack e il fatto che ce ne sono semplicemente troppi quando si danno più righe di input.