カタストロフィックバックトラッキング

一見単純に見える正規表現の中には、非常に長い時間実行され、JavaScriptエンジンを「ハングアップ」させるものがあります。

多くの開発者は、早かれ遅かれそのような動作に遭遇します。典型的な症状は、正規表現が時には正常に動作するが、特定の文字列に対しては「ハングアップ」し、CPUの100％を消費することです。

そのような場合、ウェブブラウザはスクリプトを強制終了してページをリロードすることを提案します。もちろん、良いことではありません。

サーバーサイドJavaScriptの場合、そのような正規表現はサーバープロセスをハングアップさせる可能性があり、それはさらに深刻です。そのため、必ず調べてみる必要があります。

例

文字列があり、それが\w+で表される単語と、その後に続くオプションのスペース\s?で構成されているかどうかを確認したいとします。

正規表現を作成する明白な方法は、単語の後にオプションのスペース\w+\s?を付け、それを*で繰り返すことです。

これにより、正規表現^(\w+\s?)*$が得られます。これは、行の先頭^で始まり、行の末尾$で終わる、そのような単語を0個以上指定します。

動作

let regexp = /^(\w+\s?)*$/;

alert( regexp.test("A good string") ); // true
alert( regexp.test("Bad characters: $@#") ); // false

正規表現は動作しているように見えます。結果は正しいです。ただし、特定の文字列では非常に時間がかかります。JavaScriptエンジンがCPU使用率100％で「ハングアップ」するほどです。

以下の例を実行すると、JavaScriptが「ハングアップ」するため、何も表示されない可能性があります。ウェブブラウザはイベントに反応しなくなり、UIは動作しなくなります（ほとんどのブラウザではスクロールのみが許可されます）。しばらくすると、ページをリロードすることを提案します。注意して使用してください。

let regexp = /^(\w+\s?)*$/;
let str = "An input string that takes a long time or even makes this regexp hang!";

// will take a very long time
alert( regexp.test(str) );

公平を期すために、一部の正規表現エンジンは、たとえば8.8以降のバージョンのV8エンジン（そのためGoogle Chrome 88ではここでハングしません）は効果的にこのような検索を処理できますが、Firefoxブラウザはハングします。

簡略化された例

何が問題なのでしょうか？正規表現がハングアップする理由は何ですか？

それを理解するために、例を簡素化しましょう。スペース\s?を削除します。すると^(\w+)*$になります。

\wを\dに置き換えて、さらに分かりやすくしましょう。結果の正規表現は、例えば以下のように、まだハングアップします。

let regexp = /^(\d+)*$/;

let str = "012345678901234567890123456789z";

// will take a very long time (careful!)
alert( regexp.test(str) );

では、正規表現の何が間違っているのでしょうか？

まず、正規表現(\d+)*はやや奇妙であることに気付くかもしれません。*修飾子は余分に見えます。数字が必要な場合は、\d+を使用できます。

実際、正規表現は人工的なものです。前の例を簡素化することで得られました。しかし、それが遅い理由は同じです。それを理解すれば、前の例は明らかになります。

行123456789z（分かりやすくするために少し短縮しました。末尾の非数字文字zに注意してください。重要です）で^(\d+)*$の検索中に何が起こり、なぜこれほど時間がかかるのでしょうか？

正規表現エンジンが行う処理を説明します。

まず、正規表現エンジンは括弧の内容である数字\d+を見つけようとします。+はデフォルトで貪欲なので、すべての数字を消費します。
```
\d+.......
(123456789)z
```
すべての数字が消費されると、\d+が見つかったとみなされます（123456789として）。

次に、星印修飾子(\d+)*が適用されます。しかし、テキストにはもう数字がないため、星印は何も生成しません。

パターン内の次の文字は文字列の終端$です。しかし、テキストにはzがあるため、一致しません。
```
           X
\d+........$
(123456789)z
```
一致しないため、貪欲修飾子+は繰り返し数を減らし、1文字後ろにバックトラックします。

これで\d+は最後の数字を除くすべての数字を取得します（12345678）。
```
\d+.......
(12345678)9z
```
次に、エンジンは次の位置（12345678のすぐ後）から検索を続行しようとします。

星印(\d+)*を適用できます。これにより、\d+、つまり数字9がさらに1つ一致することになります。
```
\d+.......\d+
(12345678)(9)z
```
エンジンは再び$との一致を試みますが、代わりにzに遭遇するため失敗します。
```
             X
\d+.......\d+
(12345678)(9)z
```
一致しないため、エンジンはバックトラックを続行し、繰り返し数を減らします。バックトラックは一般的に、最後の貪欲修飾子が最小値に達するまで繰り返し数を減らすことで機能します。次に、前の貪欲修飾子が減少し、以下同様です。

すべての可能な組み合わせが試行されます。その例を以下に示します。

最初の数字\d+は7桁で、その後に2桁の数字が続きます。
```
             X
\d+......\d+
(1234567)(89)z
```
最初の数字は7桁で、その後に1桁の数字が2つ続きます。
```
               X
\d+......\d+\d+
(1234567)(8)(9)z
```
最初の数字は6桁で、その後に3桁の数字が続きます。
```
             X
\d+.......\d+
(123456)(789)z
```
最初の数字は6桁で、その後に2つの数字が続きます。
```
               X
\d+.....\d+ \d+
(123456)(78)(9)z
```
…以下同様です。

数字のシーケンス123456789を数字に分割する方法は多数あります。正確には、2ⁿ-1個あり、ここでnはシーケンスの長さです。

123456789の場合、n=9なので、511個の組み合わせがあります。
n=20のより長いシーケンスの場合、約100万（1048575）個の組み合わせがあります。
n=30の場合、1000倍以上です（1073741823個の組み合わせ）。

それぞれを試行することが、検索に非常に時間がかかる理由です。

単語と文字列に戻る

同様のことが、文字列An input that hangs!でパターン^(\w+\s?)*$によって単語を検索する場合にも発生します。

その理由は、単語が1つの\w+として表すことも、複数で表すこともできるためです。

          (input)
(inpu)(t)
(inp)(u)(t)
(in)(p)(ut)
...
        

人間にとって、文字列は感嘆符!で終わっているため一致しない可能性があることは明らかですが、正規表現は末尾に単語文字\wまたはスペース\sを期待しています。しかし、エンジンはそのことを知りません。

エンジンは、正規表現(\w+\s?)*が文字列を「消費」できる方法のすべての組み合わせを試行します。スペース(\w+\s)*を含むものと、スペース(\w+)*を含まないもの（スペース\s?はオプションであるため）を含みます。そのような組み合わせが多数あるため（数字で見たとおり）、検索に時間がかかります。

対処法

遅延モードをオンにするべきでしょうか？

残念ながら、それは役に立ちません。\w+を\w+?に置き換えても、正規表現はハングアップしたままです。組み合わせの順序は変わりますが、総数は変わりません。

一部の正規表現エンジンには、すべての組み合わせを回避したり、大幅に高速化したりできる巧妙なテストと有限オートマトンがありますが、ほとんどのエンジンにはそれがないため、常に役立つわけではありません。

修正方法

この問題を解決するには、主に2つのアプローチがあります。

1つ目は、可能な組み合わせの数を減らすことです。

正規表現を^(\w+\s)*\w*$のように書き直して、スペースをオプション以外にすることで、単語の後にスペースが続くものを任意の数だけ検索し(\w+\s)*、その後（オプションで）最終的な単語\w*を検索します。

この正規表現は前の正規表現と同等であり（同じものを一致させる）、正常に動作します。

let regexp = /^(\w+\s)*\w*$/;
let str = "An input string that takes a long time or even makes this regex hang!";

alert( regexp.test(str) ); // false

なぜ問題が解決したのでしょうか？

それは、スペースが必須になったためです。

前の正規表現でスペースを省略すると(\w+)*になり、1つの単語内で\w+の多くの組み合わせにつながります。

そのためinputは、次のように\w+の2つの繰り返しとして一致させることができます。

          \w+  \w+
(inp)(ut)
        

新しいパターンは異なります。(\w+\s)*は、スペースの後に続く単語の繰り返しを指定します！input文字列は、スペースが必須であるため、\w+\sの2つの繰り返しとして一致させることはできません。

多数の（実際にはほとんどの）組み合わせを試行するために必要な時間が節約されます。

バックトラッキングの防止

ただし、正規表現を書き直すのが常に便利なわけではありません。上記の例では簡単でしたが、常にどのように行うのが簡単とは限りません。

さらに、書き直された正規表現は通常より複雑になり、それは良くありません。正規表現は、余分な労力をかけることなく、十分に複雑です。

幸いにも、代替アプローチがあります。修飾子のバックトラッキングを禁止できます。

問題の根本原因は、正規表現エンジンが人間にとって明らかに間違っている多くの組み合わせを試行することです。

たとえば、正規表現(\d+)*$では、人間にとって+はバックトラックする必要がないことは明らかです。1つの\d+を2つの独立した\d+\d+に置き換えても、何も変わりません。

          \d+........
(123456789)!

\d+...\d+....
(1234)(56789)!
        

元の例^(\w+\s?)*$では、\w+でのバックトラッキングを禁止したい場合があります。つまり、\w+はできるだけ長い単語全体と一致する必要があります。\w+の繰り返し回数を減らす必要はありません。\w+\w+のように2つの単語に分割する必要もありません。

最新の正規表現エンジンは、そのためには所有格修飾子をサポートしています。修飾子を+を追加することで、正規の修飾子が所有格になります。つまり、\d+の代わりに\d++を使用して、+のバックトラッキングを停止します。

所有格修飾子は実際には「通常の」修飾子よりも単純です。バックトラッキングなしで、可能な限り多くのものを一致させます。バックトラッキングのない検索プロセスはより単純です。

いわゆる「アトミックキャプチャグループ」もあります。これは、括弧内のバックトラッキングを無効にする方法です。

…しかし、残念なことに、JavaScriptではサポートされていません。

ただし、「先行参照変換」を使用してエミュレートできます。

先行参照が救世主！

さて、高度なトピックに入ってきました。+のような限定子について、バックトラックさせない方法を検討しましょう。なぜなら、バックトラックが無意味になる場合があるからです。

バックトラックせずに\wをできるだけ多く繰り返すパターンは、(?=(\w+))\1です。\wの代わりに他のパターンを使用することももちろん可能です。

奇妙に思えるかもしれませんが、実際は非常にシンプルな変換です。

解読してみましょう

先行読み?=は、現在の位置から始まる最長の単語\w+を前方で探します。
?=...付きの括弧内の内容はエンジンによって記憶されないため、\w+を括弧で囲みます。そうすることで、エンジンはその内容を記憶します。
…そして、パターン内で\1として参照できるようになります。

つまり、先行読みを行い、単語\w+があれば、\1として一致させます。

なぜそうなるのでしょうか？それは、先行読みが単語\w+全体を見つけて、それを\1でパターンにキャプチャするためです。そのため、本質的に、所有格プラス+限定子を実装したことになります。これは、単語\w+の一部ではなく、全体のみをキャプチャします。

例えば、「JavaScript」という単語では、「Java」に一致するだけでなく、「Script」を残してパターンの残りの部分に一致することがあります。

2つのパターンの比較を示します。

alert( "JavaScript".match(/\w+Script/)); // JavaScript
alert( "JavaScript".match(/(?=(\w+))\1Script/)); // null

最初のバリアント\w+では、最初に「JavaScript」という単語全体をキャプチャしますが、その後+が文字単位でバックトラックし、パターンが残りの部分に一致するまで試行します（\w+がJavaに一致する場合）。
2番目のバリアント(?=(\w+))は先行読みを行い、「JavaScript」という単語を見つけ、それを\1によってパターン全体に含めるため、「Script」をその後に見つける方法がありません。

\wの代わりに、(?=(\w+))\1にさらに複雑な正規表現を入れることができます。これは、その後の+のバックトラックを禁止したい場合です。

所有格限定子と先行読みの関係については、記事Regex: Emulate Atomic Grouping (and Possessive Quantifiers) with LookAheadとMimicking Atomic Groupsで詳しく説明されています。

バックトラックを防ぐために、先行読みを使用して最初の例を書き直してみましょう。

let regexp = /^((?=(\w+))\2\s?)*$/;

alert( regexp.test("A good string") ); // true

let str = "An input string that takes a long time or even makes this regex hang!";

alert( regexp.test(str) ); // false, works and fast!

ここでは、追加の外側の括弧があるため、\1の代わりに\2が使用されています。番号を混乱させないために、括弧に名前を付けることができます。例えば、(?<word>\w+)です。

// parentheses are named ?<word>, referenced as \k<word>
let regexp = /^((?=(?<word>\w+))\k<word>\s?)*$/;

let str = "An input string that takes a long time or even makes this regex hang!";

alert( regexp.test(str) ); // false

alert( regexp.test("A correct string") ); // true

この記事で説明されている問題は、「カタストロフィックバックトラッキング」と呼ばれています。

解決策を2つ説明しました。

可能な組み合わせ数を減らすために正規表現を書き直す。
バックトラッキングを防ぐ。