リリース

4.2.1をリリースしようとしたが、ジオシティーズに接続できない。
もう少し待ってからやり直そう。

指数関数的発散(1)

繰り返しがネストして計算時間が指数関数的に発散するパターンについて、対応するかどうかは決めていない。しかし、対応方法については今日考えてみた。

まず、問題のパターンは、以下のようになっている。

/(A*...B*|...)*/

ここでAとBは、両方で共通にマッチ可能な文字(列)が存在するパターンである。上記のパターンでは、AとBが同じ選択肢にあるとして書いたが、別の選択肢の中にあっても、同じ問題は起きる。

AとBが縮退して、最も単純化された場合には、以下のようになる。

/(A*)*/

これらのパターンで問題が起きる。

ついでに書いておくと、上記でグループのキャプチャがない以下のような場合には、自動的に無駄な繰り返しを省くようになっているので、問題は起きない。

/(?:A*)*/

リリース今日は無理？

まだ繋がらない。ひょとしてこちらの環境が変なのか？

指数関数的発散(2)

PCREでは、どのように対応しているのか簡単に調べてみた。
問題の起こるパターンと文字列で実行してみると、一秒以内に終了し、戻り値としてMISMATCHではなく、あるエラーを示す値を返してきた。
ソースコードを見ると、マッチング処理を行う再帰的関数match()の中で、関数が呼び出される毎にカウンターをインクリメントして、カウンターの値が10,000,000を超えるとエラーとして終了しているようだ。(10,000,000という値は、検索オプションで変更することもできる)
この方法は、パターンを全く考慮していない。しかし、実際にはこれで十分ということなのだろうか。