正規表現のバックトラッキングによるCPU負荷問題と対策
TypeScript
正規表現で .+? や .+ を使用すると、マッチ失敗時に大量のバックトラッキングが発生し、CPU負荷が高くなる。
問題となるパターン
.+?keyword- 任意の文字にマッチするため、文字列全体をスキャンしながらバックトラッキング.+?<.+?>- ネストした.+?は組み合わせで指数関数的に処理が増加- 行頭
^がないパターン - 文字列の各位置からマッチを試行
対策
.+?を[^\n]+に置き換える(改行以外の文字に限定)<.+?>を<[^>]+>に置き換える(特定文字以外に限定)- 行頭
^を追加してマッチ開始位置を限定 - 複数のパターンを
|で結合して1回のマッチングで済ませる
例
効果
10,000文字の文字列に60パターンを適用する場合:
- Before: 最大60万回の試行
- After: 約100回の試行(行数分)