Perlだと一瞬で帰ってくる正規表現がNodeだと永久に帰ってこなかった件

正規表現エンジンの違いで実行時間に大きな差が出た

私はJavaScriptで正規表現でHTMLタグを置換する処理を書いていました^[1]。これを実行すると絶望的に帰ってきません。

html = "<a href=\"http://example.com\" target=\"_blank\"                                        >"
console.log(html.replace(/<a(\s+[^>]+)*\s+href="([^"]*)"[^>]+>/ig, "\n$2\n"));

一方で、Perlで書き直してみると一瞬で終わります。

$html = "<a href=\"http://example.com\" target=\"_blank\"                                        >";
$html =~ s/<a(\s+[^>]+)*\s+href="([^"]*)"[^>]+>/$2/ig;
print $html;

何が起きていたか？

毎度おなじみ破滅的バックトラック（Catastrophic Backtracking）が起きていました。これは、正規表現中の量指定子（* や +）が入れ子になっている場合などに発生し、可能なマッチの組み合わせが指数関数的に増加することで、処理が極端に遅くなる現象です。

今回のケースでは、タグ内で空白文字が連続した場合に(\s+[^>]+)*\s+ のマッチで組み合わせ爆発が起こります。本来なら (\s+[^>\s]+)*\s+ と書くべきでした。

改めて見直してみると、Perl正規表現エンジンが頭良すぎる気もしますね。Perlでもあまり良くない正規表現だと思います。

まとめ

正規表現エンジンによって挙動は大きく異なるんだな、という話でした。

脚注

1. オリジナルはNodeではなくGASスクリプトだったのでDOMパース関数が使えなかったとか言い訳はあります