唯物是真 @Scaled_Wurm

プログラミング(主にPython2.7)とか機械学習とか

Dartsの仕様につまづいた話――あるいはMeCabに些細なバグを見つけた話

Double ArrayによるTrieのライブラリDartsのcommonPrefixSearch関数は次のような戻り値と引数になっています。
size_t commonPrefixSearch(const key_type *key, T* result, size_t result_len, size_t len = 0, size_t node_pos = 0);

ここでresult_lenは結果を返すための第2引数で渡した配列result[]のサイズとなっています。
また戻り値はマッチした要素の数numです。

このことから勝手にnum <= result_lenであると思い込んでいました。
しかし、よくよくソースを見るとnum > result_lenの時は配列resultに代入しないだけで、numはどんどん増加していきます。

戻り値numの数だけループを回すコードを書いていたので、配列の範囲外にアクセスして死んでしまいました。
当然num <= result_lenだと思ったのですが、よく考えるとそんなことどこにも書いていませんね……。

個人的にはバグに近いものだと感じるのですが、マッチした数がresult_lenより大きいのがわかるのも必要なのかなぁ……。
ちなみにdarts-cloneのcommonPrefixSearchも同様の動作をしますね。

Dartsの大本であるMeCab 0.994でも私のミスと同様のミス(commonPrefixSearchの戻り値の数だけループ)をしているので、kResultsSize = 512を大きく超える個数のマッチを返すとバグるはずです(あまり現実的な状況ではありませんが)
試しにa, aa, aaa, ...(たくさん) を辞書に登録してすごく長いaaa...aaaをMeCabに入力として与えたらsegmentation faultとなりました。

範囲外のデータを読み込むだけのため危険性は低そう(?)ですが……。
やっぱりC/C++の配列・ポインタ関係は怖いですね。

-->