正規表現を試す

正規表現がどこに一致したかを、色と「何文字目から」の両方で示します。打った文字はどこにも送りません。時間がかかりすぎる正規表現は、画面が固まる前に打ち切ります。

⭐ 正規表現でブラウザが固まることがあります。しかもエラーは出ません

正規表現には時間の制限がありません。書き方によっては、 答えを出すのに何時間もかかることがあります。困るのはそのときの様子で、エラーも出ず、警告も出ず、落ちもしません。 画面が動かなくなるだけです。押しても反応がないので、正規表現のせいだと気づく手がかりが、どこにもありません。

これは知られた問題で、ReDoS（正規表現を使ったサービス妨害）という名前が 付いています。OWASP の解説（新しいタブで開きます）は、こうなる正規表現をEvil Regex（意地の悪い正規表現）と呼び、 条件を3つに分けて書いています ──「かっこに繰り返しが付いている」、そしてその中に「繰り返しがある」か「重なっている『または』がある」。

なぜ遅くなるのかは、分け方を数えると分かります。(a+)+ は「a が1個以上のかたまり」の繰り返しなので、aaa を aaa と読むことも、aa ＋ a と読むことも、a ＋ a ＋ a と読むこともできます。 どう分けても同じ aaa に一致するので、ふだんは気になりません。

ところが最後に一致しない文字を1つ置くと話が変わります。 どの分け方でも最後で外れるので、正規表現は「別の分け方ならうまくいくかもしれない」と、全部の分け方を試します。 これをバックトラッキング（後戻り）といいます。

1文字増えるごとに、ちょうど倍になります。8文字ならすぐ終わりますが、32文字で42億通りです。 文字が32個並んでいるだけの、なんでもない文字列なのに、答えが返ってきません。 OWASP も ^(a+)+$ について「aaaaX には16通りの経路があるが、aaaaaaaaaaaaaaaaX には65,536通りあり、 a が1つ増えるごとに倍になる」と書いています。

上の表の数と OWASP の数は、数え方が少し違います。 ここで数えているのは「a の分け方」、OWASP が数えているのは「状態の図をたどる道すじ」です。どちらかが誤りなのではなく、 何を1つと数えるかが違います。倍々に増えるという肝心なところは同じなので、 自分で数え直せるほうを表に出しました（この数は単体テストで、 小さい数について全部の分け方を実際に並べて確かめています）。

時間を計って止める、ができません

では、時間を計って長すぎたら止めればよいのでしょうか。それができません。JavaScript は1つの担当が、1度に1つのことしかしない作りになっています。 正規表現が走っているあいだ、その担当はそれだけをしているので、タイマーの番がいつまでも回ってきません。

止めるには、計算を別の担当にやってもらうしかありません。 これを Worker といいます。別の担当なら、 こちらの担当は空いているので時計を見ていられますし、 遅ければ担当ごと打ち切れます。MDN の説明（新しいタブで開きます）は、この打ち切り（terminate()）を「Worker をただちに終了させる。処理を終える機会は与えられず、その場で停止する」と書いています。途中で止められるのがここの肝で、 だからこの道具は正規表現を自分では走らせません。

この画面は、打ってから少し待って別の担当に投げ、400ミリ秒たっても答えが返らなければ打ち切ります。 上の「わざと止まらなくする」を押すと、実際に打ち切られる様子が見られます。止めたことと、なぜそうなるかを画面に出すところまでが、この道具の仕事です。

ドット（.）は改行を除く文字に一致します

. は「どんな文字にも一致する」と説明されることが多いのですが、改行にだけは一致しません。 ECMAScript の仕様が、. を「行の終わりを表す文字を除く、どの文字にも一致する」と定義しているためです。

なぜ改行だけ別扱いなのかというと、正規表現がもともと行を1つずつ読む道具の中で育ったからです。 1行を読んで、その中を探して、 次の行へ。その世界では改行は文字ではなく、行の区切りでした。 いまは文章全体をまとめて扱えますが、. の意味だけが当時のまま残っています。

改行にも一致させたいときは s フラグを付けます。 仕様での名前は dotAll── 「ドットが本当にすべてに一致する」という意味です。わざわざ「すべて」と名前を付け直していることが、 ふだんの . がすべてではないことを言っています。

u を付けないと、絵文字は1文字として扱われません

. に g だけを付けて絵文字2つを探すと、4件見つかります。しかも1件ずつは画面に出せない半分なので、四角に見えます。

JavaScript の文字列は、16ビットぶんの区切りが並んだものとして作られました。 当時は世界中の文字がその範囲に収まると考えられていたからです。 ところがそれでは足りなくなり、2つぶんの区切りを組にして1文字を表す仕組みが足されました。 絵文字や、一部の漢字がこれに当たります。

u フラグは、この組を1文字として読むための指定です。 付けなければ、正規表現は区切りを1つずつ見るので、. は組の半分だけに一致します。 半分だけの文字は表示できないので、画面には四角が出ます。 上の「絵文字が2つに割れる」を押して、u を付けたり外したりすると確かめられます。

この道具が「何文字目から」と言うときの1文字も、この16ビットの区切りで数えています。 絵文字が入ると、 目で数えた文字数とずれます。道具の都合ではなく、正規表現がその単位で動いているためで、 ここをずらして書くと u フラグの話がそもそも通じなくなります。

g を付けた正規表現は、次にどこから探すかを覚えています

g を付けた正規表現は、「次はここから探す」という場所を自分の中に持ちます。 1つ見つけるたびにその場所が進むので、続きから探せるわけです。

便利なのですが、これが2つの困りごとを生みます。

その1: 同じ正規表現を使い回すと、2回目から答えが変わる

場所を覚えているということは、使い終わってもその場所が残るということです。 同じ正規表現を別の文字列にもう一度使うと、前回の続きから探し始めます。 同じものを同じように渡したのに、1回目と2回目で答えが違う ── いちばん気づきにくい壊れ方のひとつです。 この道具は、探すたびに正規表現を作り直してこの経路を断っています。

その2: 長さ0の一致で、終わらなくなる

正規表現は長さ0の一致をすることがあります。 たとえば a* は「a が0個以上」なので、a が1つも無いところにも一致します。 この道具で a* を bbb に当てると、4件見つかるのはそのためです（文字と文字のあいだ、そして両端）。

ここで問題が起きます。長さ0の一致では、探す場所が1つも進みません。 進めるのは見つかった長さのぶんだけだからです。すると次も同じ場所で同じものが見つかり、同じところを永久に返し続けます。 この道具は、長さ0だったときだけ自分で場所を1つ進めています。 しかも u を付けているときは2つぶん進めます ── 1つだけ進めると、絵文字の真ん中で止まってしまうからです。

色だけで示すと、伝わらない人がいます

一致したところに色を付けるのは分かりやすい方法ですが、色が見分けられない人には何も伝わりません。 ウェブアクセシビリティの基準（WCAG の 1.4.1）は、色だけを情報の伝え方にしてはいけないと定めています。

そこでこの道具は、色と一緒に下線（形）と通し番号（数）を付け、 下の一覧に「何文字目から何文字目まで」を文字で出しています。 色が見えなくても、番号と位置で同じことが分かります。長さ0の一致のように、そもそも色を付ける中身が無いものもあるので、 位置を文字で言えることには別の意味もあります。

打った文字は、この機器から出ません

正規表現を試すとき、人は手元にある本物を貼ります。 うまく動かないから試すのであって、そういうときに貼るのは実際のログや、名前や住所の混ざった一覧です。 これはとても自然なことです。

だからこの道具は、打った文字を一切送りません。 計算を別の担当（Worker）に渡してはいますが、これは同じ機器の中の担当で、通信ではありません。 ブラウザの開発者ツールで通信の様子を見ながら文字を打っても、新しい通信は1件も増えません。確かめられる形になっています。

出どころ: 破滅的バックトラッキングの条件と例はOWASP の ReDoS の解説（新しいタブで開きます）、terminate() の効き方はMDN（新しいタブで開きます）、フラグの働き・. の定義・探す場所が残る決まりはECMAScript 仕様の正規表現の章（新しいタブで開きます）から取っています。分け方の数だけは他所の数字を写さず、小さい数について全部を並べて数え直したものを載せています。