正規表現を使ってCPUを100%にする

Google Chromeのコンソールを開いて以下を実行する。すると処理が終わらなくてChromeがCPU100%を使う。

/(0+)+1/.test('000000000000000000000000000000000000000000000000000000');

これを見つけたとき、なんとなく得意になってchroniumのissueで報告したんだけど、

You know what also leads to freeze? An endless loop, or recursive fibonacci with a large argument.
Using regexp doesn't mean the runtime complexity magically goes away, and regexp is not always the right tool.
What you are observing is commonly known as backtracking hell. Yes, there are ways to solve pathological cases, at the cost of added complexity and performance penalty elsewhere.
https://code.google.com/p/chromium/issues/detail?id=544123

と言われた。カオから血が出るほど恥ずかった。ちなみにFirefoxも100%になる（「スクリプトの実行を中断するか」と聞かれる）。Safariはfalseをすぐに返してくる。Node.jsでも100%になる。

この事象は、文字列中のURLを取得するために、https://mathiasbynens.be/demo/url-regex に列挙されている一番網羅的な diegoperini のを使ってみたときに見つけたんだけど、そのときのコードが下記のようなもの（現在サイトに載っている正規表現は問題ない）。

/(?:(?:(?:https?|ftp):)?\/\/)(?:\S+(?::\S*)?@)?(?:(?!(?:10|127)(?:\.\d{1,3}){3})(?!(?:169\.254|192\.168)(?:\.\d{1,3}){2})(?!172\.(?:1[6-9]|2\d|3[0-1])(?:\.\d{1,3}){2})(?:[1-9]\d?|1\d\d|2[01]\d|22[0-3])(?:\.(?:1?\d{1,2}|2[0-4]\d|25[0-5])){2}(?:\.(?:[1-9]\d?|1\d\d|2[0-4]\d|25[0-4]))|(?:(?:[a-z\u00a1-\uffff0-9]+-?)*[a-z\u00a1-\uffff0-9]+)(?:\.(?:[a-z\u00a1-\uffff0-9]+-?)*[a-z\u00a1-\uffff0-9]+)*(?:\.(?:[a-z\u00a1-\uffff]{2,})))/

ビジュアライズ版
http://regexper.com/#%2F(%3F%3A(%3F%3A(%3F%3Ahttps%3F%7Cftp)%3A)%3F%5C%2F%5C%2F)(%3F%3A%5CS%2B(%3F%3A%3A%5CS*)%3F%40)%3F(%3F%3A(%3F!(%3F%3A10%7C127)(%3F%3A%5C.%5Cd%7B1%2C3%7D)%7B3%7D)(%3F!(%3F%3A169%5C.254%7C192%5C.168)(%3F%3A%5C.%5Cd%7B1%2C3%7D)%7B2%7D)(%3F!172%5C.(%3F%3A1%5B6-9%5D%7C2%5Cd%7C3%5B0-1%5D)(%3F%3A%5C.%5Cd%7B1%2C3%7D)%7B2%7D)(%3F%3A%5B1-9%5D%5Cd%3F%7C1%5Cd%5Cd%7C2%5B01%5D%5Cd%7C22%5B0-3%5D)(%3F%3A%5C.(%3F%3A1%3F%5Cd%7B1%2C2%7D%7C2%5B0-4%5D%5Cd%7C25%5B0-5%5D))%7B2%7D(%3F%3A%5C.(%3F%3A%5B1-9%5D%5Cd%3F%7C1%5Cd%5Cd%7C2%5B0-4%5D%5Cd%7C25%5B0-4%5D))%7C(%3F%3A(%3F%3A%5Ba-z%5Cu00a1-%5Cuffff0-9%5D%2B-%3F)*%5Ba-z%5Cu00a1-%5Cuffff0-9%5D%2B)(%3F%3A%5C.(%3F%3A%5Ba-z%5Cu00a1-%5Cuffff0-9%5D%2B-%3F)*%5Ba-z%5Cu00a1-%5Cuffff0-9%5D%2B)*(%3F%3A%5C.(%3F%3A%5Ba-z%5Cu00a1-%5Cuffff%5D%7B2%2C%7D)))%2F

複雑。だがそれがいい。しかしこれだとたとえば「//123456789012345678901234567890123456789012345678901234」みたいな文字列がくると正規表現の実行が終わらなくなる...そして正規表現が複雑すぎるがゆえに現象を把握するのにかなり時間を要してしまった。なぜオレはあんなムダな時間を...

なので、いまは stephenhay @^(https?|ftp)://[^\s/$.?#].[^\s]*$@iS のシンプルで網羅性も良いのを参考にしている。

正規表現の術に頼りすぎるとイザナミのループから抜け出せなくなるということがわかった。シンプル大事。理解しないで使うの危ない（でもオレはあきらめの悪い男...）。