私たちはこのオープンソースプロジェクトを世界中の人々に提供したいと考えています。このチュートリアルの内容をあなたが知っている言語に翻訳するのを手伝ってください。
購入するEPUB/PDF
チュートリアルマップ
  1. チュートリアル
  2. 正規表現
2020年12月13日

破壊的なバックトラック(Catastrophic backtracking)

一部の正規表現は、一見すると単純に見えますが、実行時間が非常に長く JavaScript エンジンを “ハング” させることがあります。

遅かれ早かれ、多くの開発者はこのような振る舞いに直面することがあります。典型的な症状は、正規表現は概ねうまく機能しますが、特定の文字の場合 “ハング” し、CPUを 100% 消費します。

このような場合、Webブラウザはスクリプトを停止し、ページをリロードするよう提案します。これは確かに良いことではありません。

サーバサイド JavaScript では、このような正規表現はサーバプロセスをハングさせる可能性があり、より深刻です。そのため、絶対に見ておくべきことです。

例

文字列があり、それぞれの文字の後に任意のスペース \s? を持つ文字 \w+ から構成されるかを確認したいとしましょう。

正規表現を組み立てる明白な方法は、文字の後に任意のスペース \w+\s? を取り、それを * で繰り返すことです。

これで、正規表現 ^(\w+\s?)*$ ができ、先頭 ^ から始まり、行末で終わる $、ゼロ個以上の単語を指します。

動作:

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

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

正規表現は動作しているように見え、結果も正しいです。ですが、特定の文字列の場合には非常に時間がかかります。それはJavaScript エンジンが CPU 100% 消費で “ハング” するほどの長さです。

以下の例を実行した場合、JavaScript が “ハング” し恐らくなにも表示されないでしょう。Webブラウザがイベントへ反応するのをやめ、UI は機能しなくなります（ほとんどのブラウザはスクロールだけ許可します）。しばらくすると、ページのリロードを提案するでしょう。そのため、この実行には気をつけてください。

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

// 非常に時間がかかります
alert( regexp.test(str) );

公平を期するために、正規表現のエンジンによってはこのような検索も効果的に扱えることに留意してください。ですが、それらの多くはできません。通常、ブラウザエンジンはハングします。

分かりやすい例

何がおきているのでしょう。なぜ正規表現がハングするのでしょう？

これを理解するために、分かりやすい例にしましょう: スペース \s? を除きます。すると、^(\w+)*$ になります。

そして、より物事を明確にするために、\w を \d に置き換えます。結果の正規表現は依然としてハングします。たとえば:

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

let str = "012345678901234567890123456789z";

// 非常に時間がかかります (注意してください!)
alert( regexp.test(str) );

では、この正規表現の何が問題になっているでしょうか。

まず、正規表現 (\d+)* は少しおかしいことに気づくかもしれません。量指定子 * は無関係に見えます。数字が必要な場合は、\d+ が使えます。

前の例を単純化することで得たものなので、確かに正規表現は不自然です。ですが、遅い理由は同じなので、これで理解していきましょう。そうすれば、前の例も明らかになります。

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

これは、正規表現エンジンが行っていることです:

  1. 最初に、正規表現エンジンは括弧の内容を見つけようとします: 数値 \d+ です。プラス + はデフォルトでは貪欲なので、これはすべての数値を消費します:

    \d+.......
(123456789)z

    すべての数値が消費された後、\d+ は見つけられたと判断されます（123456789）。

    次に、アスタリスク量指定子 (\d+)* が適用されます。が、テキストにはもう数値はないので、アスタリスクは何もとりません。

    パターンの次の文字は文字列の終わり $ です。しかし、テキストには代わりに z があるのでマッチしません。

               X
\d+........$
(123456789)z

  2. 一致しなかったので、貪欲量指定子 + は繰り返しの数を減らし、1文字戻ります。

    いま、 \d+ は最後の1つを除いた全ての数値を取ります (12345678):

    \d+.......
(12345678)9z

  3. 次に、エンジンは次の位置(12345678の直後)から検索を続けようとします。

    アスタリスク (\d+)* が適用されます – \d+ のもう1つの一致、数値 9 が与えられます。:

    \d+.......\d+
(12345678)(9)z

    エンジンは 再び $ への一致を試みますが、代わりに z があるので失敗します。:

                 X
\d+.......\d+
(12345678)(9)z

  4. 一致しないので、エンジンはバックトラッキングを続け、繰り返しの回数を減らしていきます。バックトラッキングは一般的にはこのように機能します: 最後の貪欲量指定子が、可能な限り繰り返し回数を減らします。次に、前の貪欲な量指定子が減少していきます。

    可能なすべての組み合わせが試行されます。これがその例です。

    最初の数値 \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

    …etc

数値の並び 123456789 を数値に分割する方法は多くあります。正確には、2n-1 で、n は数字列の長さです。

  • 123456789 の場合、n=9 であり、 511 の組み合わせになります。
  • n=20 のより長い並びの場合、約 100万（1048575）の組み合わせになります。
  • n=30 なら、1000倍以上(1073741823 の組み合わせ)になります。

それらを1つずつを試みることが、検索に時間がかかる理由です。

単語と文字に戻ります

最初の例、文字列 An input that hangs! に対してパターン ^(\w+\s?)*$ で文字を探すときにも同様のことが起こっています。

理由は単語は１つ以上の \w+ で表現されるためです。:

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

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

正規表現 (\w+\s?)* が文字列を “消費” しうるすべての組み合わせを試みます。それには、スペース (\w+\s?)* があるパターン、スペースがない (\w+)* パターン（スペース \s? は任意なので）が含まれます。（数字でみてきたように）多くの組み合わせがあるので、検索には時間がかかります。

何をすべきでしょう？

怠惰モード(lazy mode)を有効にすべきですか？

残念ながら、それは役に立ちません: もし \w+ を \w+? に置き換えても、正規表現は依然としてハングするでしょう。組み合わせ順は変わりますが、トータルの数は変わらないからです。

正規表現エンジンによっては、巧妙なテストや有限の仕組みがあり、すべての組み合わせの実施を回避したり、はるかに高速にすることができますが、ほとんどのエンジンはそうではなく、また常にその仕組みが有効に働くとは限りません。

修正方法は?

問題を解決するために、大きく２つのアプローチがあります。

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

正規表現を ^(\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 to hang!";

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

なぜ問題が解消されたのでしょう？

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

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

したがって、input は次のように \w+ の2つの繰り返しとして一致することになります。:

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

新しいパターンは違います: (\w+\s)* は単語文字の繰返にスペースが続きます! スペースは必須なので、input 文字列は \w+\s の2つの繰り返しとしては一致しません。

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

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

ですが、正規表現の書き直しが常にやりやすいとは限りません。上の例では簡単でしたが、その方法が常に明らかなわけではありません。

その上、書き直した正規表現はたいていより複雑になりがちです。正規表現はただでさえ十分に複雑です。

幸いなことに、別のアプローチがあります。量指定子のバックトラッキングを禁止することができます。

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

例. 正規表現 (\d+)*$ では、 + がバックトラックすべきでないことは人間にとっては明らかです。単一の \d+ を2つの \d+\d+ に置き換えても何も変わりません。:

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

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

また、元の例 ^(\w+\s?)*$ では、\w+ ではバックトラックを禁止したい場合があります。つまり: \w+ は可能な最大長で単語全体にマッチする必要があります。\w+ では繰り返し数を減らしたり、それを2つの単語 \w+\w+ に分割したりする必要はありません。

モダンな正規表現エンジンはそのための所有量指定子（強欲な量指定子、または絶対最大量指定子、possessive quantifiers ）をサポートしています。通常の量指定子のあとに + を追加すると、強欲になります。つまり、\d+ の代わりに \d++ を使い、+ のバックトラックを停止します。

所有量指定子は実際には “通常の” 量指定子よりもシンプルです。それらはバックトラックなしでできるだけ多く一致するだけです。バックトラックなしの検索処理はよりシンプルです。

また、いわゆる “アトミックグループ (atomic capturing groups)”、括弧内でのバックトラックを無効にする方法もあります。

…ですが、残念ながら 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
  1. 1つ目のパターンでは、\w+ が最初に単語全体 JavaScript をキャプチャしますが、+ は1文字ずつバックトラックし、最終的に成功するまで（\w+ が Java に一致するまで）パターンの残りの部分との一致を試みます。
  2. 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 to hang!";

alert( regexp.test(str) ); // false, うまく動作し、かつ早いです!

ここで \2 は \1 の代わりに使用しています。理由は、追加の外部の括弧があるためです。数字を間違えるのを避けるために、括弧に名前をつけることができます。例: (?<word>\w+)

//括弧は ?<word> で名前付けされ、\k<word> で参照できます。
let regexp = /^((?=(?<word>\w+))\k<word>\s?)*$/;

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

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

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

この記事で説明している問題は、“catastrophic backtracking (破壊的なバックトラック)” と呼ばれるものです。

その問題を解決する2つの方法を取り上げました:

  • できるだけ組み合わせ数を減らすよう正規表現を書き直す
  • バックトラックを防止する
前のレッスン次のレッスン
チュートリアルマップ

コメント

コメントをする前に読んでください…
  • 自由に記事への追加や質問を投稿をしたり、それらに回答してください。
  • 数語のコードを挿入するには、<code> タグを使ってください。複数行の場合は <pre> を、10行を超える場合にはサンドボックスを使ってください(plnkr, JSBin, codepen…)。
  • 記事の中で理解できないことがあれば、詳しく説明してください。

チャプター

レッスンナビゲーション

シェア
GitHubで編集