Environnement confirmé

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

phénomène

Une StackOverflowError se produit lors du traitement d'une longue phrase qui satisfait une expression régulière spécifique.

`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)
...

Cause

Les expressions régulières sont traitées comme une structure récursive
Les appels de méthode récursifs se poursuivent tant que la chaîne de caractères à traiter satisfait à la condition.

Détails de la cause

Tout d'abord, l'expression régulière donnée sous forme de chaîne de caractères est le Pattern de la classe interne de [Pattern](https://docs.oracle.com/javase/jp/9/docs/api/java/util/regex/Pattern.html). Il est décomposé en sous-classes de $ Node. Ceci est destiné au traitement de Pattern.compile Équivalent. Par exemple, l'expression régulière mentionnée ci-dessus (a | \\ s) + a la structure suivante.

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

Ensuite, selon la structure interprétée, il est confirmé si la condition est satisfaite une à une depuis le début de la chaîne de caractères à traiter, et la méthode de jugement est appelée récursivement tant que la condition est satisfaite.

Loop
GroupHead
Branch
BmpCharProperty
BranchConn
GroupTail
Loop
... Répéter

Modèle de reproduction

Reproduit avec les combinaisons suivantes.

Spécifiez un quantum numérique (* + {2,}, etc.) qui ne spécifie pas de limite supérieure après les parenthèses.
Utilisez «|» ou «?» Pour les conditions entre parenthèses

Par exemple, les expressions régulières comme (a \\ s?) + Posent le même problème.

Contre-mesures

Évitez de taper de longues phrases
Concevoir un moyen d'écrire des expressions régulières afin qu'elles ne soient pas interprétées comme Pattern $ Loop

Utiliser la classe de caractères

Si vous n'avez pas besoin de regrouper par parenthèses, créez une condition OR avec la classe de caractères (crochets). Dans le cas de l'exemple, si vous définissez [a \\ s] +, aucune erreur ne se produira.

N'utilisez pas le quantum de numéro de correspondance le plus long

Pour les motifs qui sont simplement remplacés par des blancs, l'unité à mettre en correspondance n'est pas particulièrement importante, donc même si vous simplement ʻa | \ ssans spécifier*ou+` (quantum de numéro de correspondance le plus long), tout Vous pouvez remplacer des caractères (temps de traitement augmenté de quelques millisecondes).

Ou le quantum de numéro de correspondance le plus court(a|\\s)+?Ou un quantum de nombre gourmand(a|\\s)++Si vous utilisez, il sera interprété comme une structure différente, donc aucune erreur ne se produira.

Remarques

Attention autre que de remplacer

Puisqu'il s'agit d'un problème structurel qui représente une expression régulière, un problème similaire se produit dans le traitement qui utilise une expression régulière.

String

Matcher

Comportement dans les applications Android

L'application Android n'a pas rencontré ce problème. L'implémentation Java est basée sur OpenJDK et les expressions régulières sont basées sur le code natif icu Il a été mis en œuvre et est pour une chose complètement différente.

À propos du phénomène que StackOverflowError se produit lors du traitement à l'aide d'expressions régulières Java