確認した環境

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

現象

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

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

原因

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

原因の詳細

まず、文字列として与えた正規表現はPatternの内部クラスのPattern$Nodeのサブクラスに分解されます。これはPattern.compileの処理に相当します。例えば、前述の正規表現(a|\\s)+は以下のような構造になります。

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

そして解釈された構造に従って、処理対象の文字列の先頭から一文字ずつ条件を満たすか確認し、条件を満たす限り再帰的に判定用メソッドが呼び出されることになります。

Loop
GroupHead
Branch
BmpCharProperty
BranchConn
GroupTail
Loop
... 繰り返し

再現パターン

以下の組み合わせで再現しました。

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

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

対策

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

文字クラスを使う

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

最長一致数量子を使わない

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

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

備考

replaceAll以外にも注意する

正規表現を表す構造上の問題なので、正規表現を利用する処理には同様の問題が発生します。

String

Matcher

Androidアプリでの挙動

Androidアプリではこの問題は生じませんでした。Javaの実装はOpenJDKがベースで、正規表現はicuベースのネイティブコードで実装されており、全く別物のためです。

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