Bestätigte Umgebung

Java 8（jdk1.8.0_202）
Java 9（jdk-9+181）
Java11（jdk11.0.2）

Phänomen

Ein StackOverflowError tritt auf, wenn ein langer Satz verarbeitet wird, der einen bestimmten regulären Ausdruck erfüllt.

`Test.java`


public class Test {
    public static void main(final String[] args) {
        final StringBuilder input = new StringBuilder();
        for (int i = 0; i < 5000; i++) {
            input.append("a ");
        }
        System.out.println(input.toString().replaceAll("(a|\\s)+", ""));
    }
}

Exception in thread "main" java.lang.StackOverflowError
	at java.base/java.util.regex.Pattern$GroupHead.match(Pattern.java:4786)
	at java.base/java.util.regex.Pattern$Loop.match(Pattern.java:4923)
	at java.base/java.util.regex.Pattern$GroupTail.match(Pattern.java:4845)
	at java.base/java.util.regex.Pattern$BranchConn.match(Pattern.java:4695)
...

Ursache

Reguläre Ausdrücke werden als rekursive Struktur behandelt
Rekursive Methodenaufrufe werden fortgesetzt, solange die zu verarbeitende Zeichenfolge die Bedingung erfüllt.

Ursache Details

Erstens ist der reguläre Ausdruck, der als Zeichenfolge angegeben wird, das Muster der inneren Klasse von [Muster](https://docs.oracle.com/javase/jp/9/docs/api/java/util/regex/Pattern.html). Es wird in Unterklassen von $ Node zerlegt. Dies dient zur Verarbeitung von Pattern.compile Äquivalent. Beispielsweise hat der oben erwähnte reguläre Ausdruck "(a | \ s) +" die folgende Struktur.

Start
  ---> Prolog
      ---> Loop  "+"
           ---> GroupHead "("
                 ---> Branch "|"
                     ---> BmpCharProperty "a"
                           ---> BranchConn
                                ---> GroupTail
                     ---> BmpCharProperty "\\s"
                           ---> BranchConn
                                ---> GroupTail
           ---> GroupTail ")"
                 ---> Loop

Dann wird gemäß der interpretierten Struktur bestätigt, ob die Bedingung vom Beginn der zu verarbeitenden Zeichenfolge nacheinander erfüllt ist, und die Beurteilungsmethode wird rekursiv aufgerufen, solange die Bedingung erfüllt ist.

Loop
GroupHead
Branch
BmpCharProperty
BranchConn
GroupTail
Loop
... Wiederholen

Reproduktionsmuster

Wiedergabe mit den folgenden Kombinationen.

Geben Sie ein Zahlenquantum (* + {2,} usw.) an, das nach den Klammern keine Obergrenze angibt.
Verwenden Sie "|" oder "?" Für Bedingungen in Klammern

Zum Beispiel haben reguläre Ausdrücke wie (a \\ s?) + Das gleiche Problem.

Gegenmaßnahmen

Vermeiden Sie lange Sätze
Entwickeln Sie eine Möglichkeit, reguläre Ausdrücke so zu schreiben, dass sie nicht als "Pattern $ Loop" interpretiert werden

Verwenden Sie die Zeichenklasse

Wenn Sie nicht in Klammern gruppieren müssen, erstellen Sie eine ODER-Bedingung mit der Zeichenklasse (eckige Klammern). Wenn Sie im Beispiel "[a \ s] +" setzen, tritt kein Fehler auf.

Verwenden Sie nicht das Quantum mit der längsten Übereinstimmungsnummer

Für Muster, die nur durch Leerzeichen ersetzt werden, ist die zu vergleichende Einheit nicht besonders wichtig. Selbst wenn Sie einfach "a | \ s" ausführen, ohne "*" oder "+" (das längste Übereinstimmungsnummernquantum) anzugeben, sind alle Sie können Zeichen ersetzen (Verarbeitungszeit um einige Millisekunden erhöht).

Oder das kürzeste Übereinstimmungsnummernquantum(a|\\s)+?Oder ein gieriges Zahlenquantum(a|\\s)++Wenn Sie verwenden, wird es als eine andere Struktur interpretiert, sodass kein Fehler auftritt.

Bemerkungen

Seien Sie vorsichtig, außer replaceAll

Da es sich um ein strukturelles Problem handelt, das einen regulären Ausdruck darstellt, tritt ein ähnliches Problem bei der Verarbeitung auf, bei der ein regulärer Ausdruck verwendet wird.

String

Matcher

Verhalten in Android-Apps

Die Android-App hatte dieses Problem nicht. Die Java-Implementierung basiert auf OpenJDK und reguläre Ausdrücke basieren auf nativem Code von icu Es ist implementiert und ist für eine ganz andere Sache.

Über das Phänomen, dass StackOverflowError bei der Verarbeitung mit regulären Java-Ausdrücken auftritt