Regexp verursacht unendlich hängen

Question

Ich habe folgende regexp, die auswertet nie und hängt unendlich:

import java.util.regex.Matcher 
String AUTOGENERATED_HEADER = "#-=-=-= AUTOGENERATED HEADER =-=-=-" 
String AUTOGENERATED_FOOTER = "#-=-=-= AUTOGENERATED FOOTER =-=-=-" 

String messages = '''#-=-=-= AUTOGENERATED HEADER =-=-=- 
a=b 
c=d 
x=y 
#-=-=-= AUTOGENERATED FOOTER =-=-=- 
''' 


Matcher matcher = messages =~ /${AUTOGENERATED_HEADER}[\r\n]+((.*[\r\n]*)*)${AUTOGENERATED_FOOTER}/ 
matcher.find()​ 

Das Problem mit einem Teil ist (.*[\r\n]*). Wenn ich es zu (.*[\r\n]+) ändere, funktioniert es.

Sie können mit Regexp here experimentieren. Kann mir jemand erklären, wie es möglich ist?

Answer 1

Was Sie hier haben, ist ein Fall von einem katastrophalen Backtracking. Siehe your regex demo. Der Schuldige ist der (.*[\r\n]*)* Teil, der mit anderen Untermustern eingeschlossen ist. Die verschachtelten Quantifizierer verursachen zu viel Rückverfolgung, die Sie auf der Regex-Debugger-Seite bei regex101.com sehen können.

A Lösung ist entweder zu faul Punktanpassung: replace [\r\n]+((.*[\r\n]*)*) mit .*? und füge einen (?s) Modifikator zu Beginn des Musters oder eine abgerollt Version verwenden (die für lange Eingaben viel besser ist, erfordert aber einige Hardcoding).

Siehe (?s)#-=-=-= AUTOGENERATED HEADER =-=-=-.*?#-=-=-= AUTOGENERATED FOOTER =-=-=- in Aktion. Verwenden Sie

Matcher matcher = messages =~ /(?s)${AUTOGENERATED_HEADER}.*?${AUTOGENERATED_FOOTER}/