鬼車さんのバグかも?No.08030
秀まるお さん 13/08/29 19:52
 
 HmJre.dllの新バージョンを今作ってていろいろテストしてる所で、鬼車さん
との性能比較とかもやってるんですが、1つ、鬼車さんがハングアップするパ
ターンを見つけてしまいました。

(a?|bb)+xyz

 の正規表現パターンが、

aaaaaaaaaaaaaaaaaaaxyz

 の全体にマッチしたり、

aaaaaaaaaaaaaaaaaaacxyz

 のxyz部分にマッチしたりするんですが、後者の方が、"aaa"部分が長くなって
いくとあるところから急に遅くなっていって、100文字くらいにしたりすると、
ほぼハングアップします。

 これって鬼車さんのバグだったりしないでしょうか。

 って、ここに書いても仕方が無いんですが…。一応書いてみたりします。

 ちなみにHmJre.dllでも、例えば ((a+)+)+ みたいなので"aaaa...aaaa"の長い
やつに検索したりするとハングアップするんですが、これの解決策が今のところ
無いです。鬼車さんは、こういう意地悪なのでもことごとく高速に処理してくれ
るんですけど、なぜか上記のパターンが苦手みたいなので、これだけバグのよう
な気がしないでもないです。

[ ]
RE:08030 鬼車さんのバグかも?No.08031
h-tom さん 13/08/29 23:59
 

h-tom です。

> HmJre.dllの新バージョンを今作ってていろいろテストしてる所で、鬼車さん
>との性能比較とかもやってるんですが、1つ、鬼車さんがハングアップするパ
>ターンを見つけてしまいました。
<省 略>
> これって鬼車さんのバグだったりしないでしょうか。

括弧部分を、キャプチャしないようにすると、問題ないですね。
(a?|bb)+xyz → (?:a?|bb)+xyz

現在、鬼車は更新停止中で、K.Takata氏が、改良版の鬼雲 (Onigmo, Oniguruma-mod)
を公開しています。
K.Takata氏は、Twitterのアカウントも持っているので、ちょっと聞いてみるとか?

[ ]
RE:08031 鬼車さんのバグかも?No.08032
秀まるお さん 13/08/30 10:21
 
 TwitterはIKKIさんのツイートを見る用にしか使ってなかったのですが、試し
につぶやいてみました。

[ ]
RE:08032 鬼車さんのバグかも?No.08033
秀まるお さん 13/08/31 23:59
 
 Twitterで「@」付きでつぶやいたらお気に入り登録されました。ということは、
見てくれたようです。(その後どうなったかは分かりませんが)

 あともう1つバグと思わしき現象を見つけました。

    ((ab)*)+\1

 って正規表現パターンは、これはこれで、「(ab)*\1」と同じ意味になって、
これはつまり、「abab」または「ababab」のように、"ab"が2つ以上連続した文
字列にヒットしないといけないです。これが、鬼車さんだと単独の"ab"にヒット
してしまいます。

 実はHmJre.dllのV3.54も同様に"ab"にヒットしてしまいます。

 現在開発中のV4.00では"ab"にはヒットしないようになってます。

 ということでこれも鬼車さんのバグのような気がします。

 この辺、完璧に対応するのは難しいし、正直、上記のような正規表現パターン
を使うことは実質的にはありえないのですけども…。

 というか、ここに書いても仕方ない訳ですけども。

 またつぶやこうかな…

[ ]
RE:08033 鬼車さんのバグかも?No.08034
colder さん 13/09/01 00:31
 
colderです
> あともう1つバグと思わしき現象を見つけました。
>
>    ((ab)*)+\1
>
> って正規表現パターンは、これはこれで、「(ab)*\1」と同じ意味になって、
>これはつまり、「abab」または「ababab」のように、"ab"が2つ以上連続した文
>字列にヒットしないといけないです。これが、鬼車さんだと単独の"ab"にヒット
>してしまいます。

これはバグではないです
(ab)* が0文字にもヒットすることに注意する必要があります
+による繰返しでは、一回目で"ab"にヒットし、二回目で空文字列にヒットして、\1
に空文字列が格納されています。
その結果、単独の"ab"にもヒットすることになります

[ ]
RE:08034 鬼車さんのバグかも?No.08035
秀まるお さん 13/09/01 12:02
 
 colderさんどうもです。たしかにその解釈だとOKのような気がします。

 手元のV4.00だと"ab"単独にはヒットしないんですが、これも解釈的にはOK扱
いでいいような気がしますけど、いいですよね。つまり、

   ((ab)*)+

 のヒットの仕方的に、

 鬼車、HmJre.dll 3.54 = 外側の「+」が、"ab"に1回、""に
                        1回ヒットで合計2回ヒットした扱い。
 HmJre.dll 4.00       = 外側の「+」が"ab"に1回ヒットしたのみ扱い

 ということで、どっちの解釈でも間違いでは無いのかなぁと思います。

 ついでに似たような式で、

    (ab|)+\1

 ってのも考えついたんですが、これだと、

 鬼車             ... "ab"にもヒットする。
 HmJre.dll V3, V4 ... "ab"にはヒットしない。

 って結果になりました。これもよしとしとこうと思います。

 ということで、他にもいろいろテストデータを追加していってみます。

[ ]
RE:08035 鬼車さんのバグかも?No.08036
colder さん 13/09/02 13:56
 
colderです

> のヒットの仕方的に、
>
> 鬼車、HmJre.dll 3.54 = 外側の「+」が、"ab"に1回、""に
>                        1回ヒットで合計2回ヒットした扱い。
> HmJre.dll 4.00       = 外側の「+」が"ab"に1回ヒットしたのみ扱い
>
> ということで、どっちの解釈でも間違いでは無いのかなぁと思います。

ダメな気がします。
鬼車でも\1に"ab"が入っていないと正規表現全体がヒットしなくなるようなパターン
と文字列に対して使えば、一回のみヒットしているように扱われるし、
正規表現を書き換えて、
((ab)*)((ab)*)((ab)*)…
((ab)*)を連ねて書けば、((ab)*)が幾つあろうとヒットするのに、
まとめて((ab)*)+とか書くと、二回目以降がヒットしなくなるというのは、解釈とし
て間違っている気がします。
少なくとも、((ab)*)+\1が"ab"にヒットしない正規表現は調べた範囲内では一つもあ
りません。(もちろん\1とかがサポートされていないものは除いて)

[ ]
RE:08036 鬼車さんのバグかも?No.08037
秀まるお さん 13/09/02 14:59
 
 colderさんどうもです。最初からやれば良かったことですが、今さらながらデ
バッガーでトレースして追っかけてみたら、やはりHmJre.dll側がバグってまし
た。

 おかげさまでまた1つバグを見つけていただいてしまいました。修正させてい
ただきますとともに、似たようなミスが無いか他も探してみます。



 トレースした結果:
 (a|)+\1で"a"に検索させた場合:

   patternAが (a|) で、\2がpatternBとして、マッチングさせる関数を仮に

  trymatch( パターン, 文字列, x座標, 長さ ) --> 返り値=ヒットした長さ

 とすると、

patternAの1巡目:

   trymatch( patternA, "a", 0, 0 ) --> OK, length=0
      trymatch( patternB, "a", 1, 0 ) --> OK, length=0
                                        --> 結果候補 x=0,len=0

   trymatch( patternA, "a", 0, 1 ) --> OK, length=1
      trymatch( patternB, "a", 1, 0 ) --> NG

patternAの2巡目:

   trymatch( patternA, "a", 1, 0 ) --> OK, length=0
      trymatch( patternB, "a", 1, 0 ) --> OK, length=0
                                         --> 結果候補 x=0, len=1

 となるべき所が、HmJre.dll内部に過去のマッチング履歴を再利用する処理が
あって、上記例だと、

    trymatch( patternB, "a", 1, 0 )

 が以前NGだったということでヒットしない扱いにしてしまってました。
patternBがpatternAに依存するタグを使ってる場合は例外扱いする必要がありま
した。

[ ]
RE:08037 鬼車さんのバグかも?No.08038
秀まるお さん 13/09/02 15:06
 
 よくみたら間違えてました。書き直します。

patternAの1巡目:

   trymatch( patternA, "a", 0, 0 ) --> OK, length=0
      trymatch( patternB, "a", 0, 0 ) --> OK, length=0
                                        --> 結果候補 x=0,len=0

   trymatch( patternA, "a", 0, 1 ) --> OK, length=1
      trymatch( patternB, "a", 1, 0 ) --> NG

patternAの2巡目:

   trymatch( patternA, "a", 1, 0 ) --> OK, length=0
      trymatch( patternB, "a", 1, 0 ) --> OK, length=0
                                         --> 結果候補 x=0, len=1

[ ]
RE:08038 鬼車さんのバグかも?No.08039
colder さん 13/09/03 00:24
 
colderです

最初の例を少し変形した(a?|bb)+xyz\1という正規表現を試したところ
hmjreのバグを見つけてしまいました

aaaaaaxyz
"xyz" の部分にしかヒットしない セーフモードだとどの部分もヒットしない(鬼車だ
と全体にヒット(正しい動作))

aaaaaaxyzaa
"aaxyzaa" の部分にヒットしてしまう セーフモードだと"aaaaaaxyza" にヒット(正
しい動作)(鬼車だと"aaaaaaxyz"にヒット(hmjreとはヒットする部分が異なるがこれ
は解釈の仕方が異なるため))

hmjre ver3.54


[ ]
RE:08039 鬼車さんのバグかも?No.08040
秀まるお さん 13/09/03 08:47
 
 バグ情報ありがとうございます。一応、今の手元のHmJre V4.00だとうまく動
くようでしたけども、今回のcolderさんから教えていただいたバグの関係でソー
スコードをいろいろ見直したら、タグの処理でまだ不完全な所があって、これか
ら直そうと思っていた所です。

 繰り返しパターンの中や(?:...|...)の中とかにタグ対象のカッコがある場合
(特にその部分がどこにもヒットしない場合)の処理が不完全な所があるような
ので、その辺ちゃんと安全に処理されるように修正させていただきます。

[ ]