Javaの正規表現を使った処理でStackOverflowErrorになる現象について 

# 確認した環境
* Java 8（jdk1.8.0_202）
* Java 9（jdk-9+181）
* Java11（jdk11.0.2）

# 現象
特定の正規表現を満たす長文を処理するとStackOverflowErrorが生じる。

```java: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)+", ""));
    }
}
```

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

# 原因
1. 正規表現が再帰的な構造として扱われる
2. 処理対象の文字列が条件を満たすうちは再帰的なメソッドの呼び出しが続く

## 原因の詳細
まず、文字列として与えた正規表現は[Pattern](https://docs.oracle.com/javase/jp/9/docs/api/java/util/regex/Pattern.html)の内部クラスの`Pattern$Node`のサブクラスに分解されます。これは[Pattern.compile](https://docs.oracle.com/javase/jp/9/docs/api/java/util/regex/Pattern.html#compile-java.lang.String-)の処理に相当します。例えば、前述の正規表現`(a|\\s)+`は以下のような構造になります。

```java
Start
  ---> Prolog
      ---> Loop  "+"
           ---> GroupHead "("
                 ---> Branch "|"
                     ---> BmpCharProperty "a"
                           ---> BranchConn
                                ---> GroupTail
                     ---> BmpCharProperty "\\s"
                           ---> BranchConn
                                ---> GroupTail
           ---> GroupTail ")"
                 ---> Loop
```
そして解釈された構造に従って、処理対象の文字列の先頭から一文字ずつ条件を満たすか確認し、条件を満たす限り再帰的に判定用メソッドが呼び出されることになります。

1. Loop
2. GroupHead
3. Branch
4. BmpCharProperty
5. BranchConn
6. GroupTail
7. Loop
8. ... 繰り返し


## 再現パターン
以下の組み合わせで再現しました。

* 丸括弧の後に上限を指定しない数量子（`* + {2, }`など）を指定する
* 丸括弧内の条件に`|`または`?`を使う

例えば、`(a\\s?)+`のような正規表現でも同じ問題が発生します。


# 対策
* 長文を入力されないようにする
* 正規表現の書き方を工夫して`Pattern$Loop`として解釈されないようにする

## 文字クラスを使う
丸括弧でグループ化する必要がない場合は、文字クラス（角括弧）でOR条件を作ります。
例の場合だと`[a\\s]+`とするとエラーは発生しません。

## 最長一致数量子を使わない
空白に置き換えるだけのようなパターンは、一致させる単位が特に重要ではないので`*`や`+`（最長一致数量子）を指定せずに単純に`a|\\s`としても全ての文字を置換できます（処理時間は数ミリ秒増加）。

または、最短一致数量子`(a|\\s)+?`か、強欲な数量子`(a|\\s)++`を使うと別の構造として解釈されるので、エラーは発生しません。

## 備考
### replaceAll以外にも注意する
正規表現を表す構造上の問題なので、正規表現を利用する処理には同様の問題が発生します。

#### String

* [split](https://docs.oracle.com/javase/jp/9/docs/api/java/lang/String.html#split-java.lang.String-)
* [replaceFirst](https://docs.oracle.com/javase/jp/9/docs/api/java/lang/String.html#replaceFirst-java.lang.String-java.lang.String-)
* [replaceAll](https://docs.oracle.com/javase/jp/9/docs/api/java/lang/String.html#replaceAll-java.lang.String-java.lang.String-)

#### Matcher
* [matches](https://docs.oracle.com/javase/jp/9/docs/api/java/util/regex/Matcher.html#matches--)
* [find](https://docs.oracle.com/javase/jp/9/docs/api/java/util/regex/Matcher.html#find--)
* [lookingAt](https://docs.oracle.com/javase/jp/9/docs/api/java/util/regex/Matcher.html#lookingAt--)
* [replaceAll](https://docs.oracle.com/javase/jp/9/docs/api/java/util/regex/Matcher.html#replaceAll-java.lang.String-)


### Androidアプリでの挙動
Androidアプリではこの問題は生じませんでした。Javaの実装は[OpenJDK](https://github.com/openjdk/jdk)がベースで、正規表現は[icu](https://github.com/unicode-org/icu)ベースのネイティブコードで実装されており、全く別物のためです。