まもなくgrep 2.23リリース - 気ままなブログ

GNU grep 2.23が近日中にリリースされる見込みとなりました。

GNU grep 2.23は、GNU grep 2.22に続いてバグフィックスリリースです。GNU grep 2.23では、入力データがテキストかバイナリかを判定するロジックが強化されています。GNU grep 2.21で同様の強化が行われたものの、仕様レベルの問題があり、入力データに少しでも現在のロケールに存在しないバイト列が含まれているとバイナリと判定されてしまっていました。

GNU grep 2.23における改善/バグフィックス

入力データを判定するロジックの強化

GNU grepには、入力データがテキストかバイナリかを判定し、入力データがバイナリだった場合はマッチした行を出力する代わりに「Binary file ... matches」を出力して検索を打ち切る機能が実装されています。この機能により、ユーザが誤ったバイナリファイルをgrepした場合でも、出力した制御コード等によって端末がハングしたりする問題を回避できます。

GNU grep 2.20以前では、入力データがテキストかバイナリかを入力データ中にNUL文字(文字コードが0x00)が含まれているか否かで判定しています。この実装方法は、オーバヘッドが少なく高速に動作する反面で精度が悪く、ユーザが誤ったバイナリファイルをgrepしてしまうと端末がハングしてしまう可能性があります。

そこで、GNU grep 2.21では、入力データの先頭部分(通常は最初の32768バイト)がロケールに適合していないバイトが含まれているかどうかチェックし、含まれていた場合にバイナリと判定するように変更されました。しかし、この変更によって入力データの先頭部分に1バイトでもロケールに適合しないバイトが含まれているとバイナリと判定されてしまうようになりました。例えば、入力データの先頭部分に非英語圏の人名が含まれている場合がこのようなケースに該当します。また、Javaのインストーラのように、ファイルの先頭部分だけテキスト(シェルスクリプト)で、本体部分がバイナリ(圧縮ファイル)となっているファイルをgrepした場合、相変わらず端末がハングしてしまう可能性があります。

そこで、GNU grep 2.23では、入力データではなく出力データに対してチェックを行い、出力データにロケールに適合しないバイトが含まれている場合にバイナリと判定されるように変更されました。これにより、ユーザが誤ったバイナリファイルをgrepして端末がハングしてしまう可能性はなくなると思われます。また、入力データがパターンに全くマッチしないケースではチェックが行われないため、非常に高速に結果を返すことができます。*1

grep -P/grep -Pcの不整合に対する修正

先述の通り、GNU grep 2.21、GNU grep 2.22では、入力データの先頭部分(通常は最初の32768バイト)がロケールに適合していないバイトが含まれているかどうかチェックし、含まれていた場合にバイナリと判定しています。ここで、バイナリと判定されなかった場合は、-Pオプションが指定されていない場合は、その入力データをテキストとみなしています。他方、-Pオプションが指定されている場合は、最初にパターンにマッチする行を見つける時点までチェックを続け、その時点までにロケールに適合しないバイトが見つからなかった場合にテキストと判定するようになっています。-Pオプションが指定されている場合の他と異なる振る舞いは、-Pで使用されるpcreライブラリで実装されている入力データがUTF-8に適合しているかどうかチェックする機能の性能の低さを、可能な限りGNU grep側で補うするためになされています。

ところが、後者のロジックには問題がありました。下記は、GNU grep 2.22で実行した結果です。-cオプションを指定しなかった場合は2行返されています。他方、-cオプションを指定した場合は、1が返されています。

$ printf 'a\n%032768d\nb\x0\n%032768d\na\n' | LC_ALL=C grep -P a
a
a
$ printf 'a\n%032768d\nb\x0\n%032768d\na\n' | LC_ALL=C grep -Pc a
1

まず、前者について見てみましょう。まず、最初の32768バイトにはロケールに適合しないバイトは含まれていません。次に、入力データの先頭が「a」なので、最初の行はパターンにマッチします。この時点で入力データはテキストとみなされます。その後も入力データはテキストとして処理され、最後の行がパターンにマッチします。従って、2行返されます。

次に、後者について見てみましょう。まず、最初の32768バイトにはロケールに適合しないバイトは含まれていません。次に、入力データの先頭が「a」なので、最初の行はパターンにマッチしますが、-cオプションは入力データの最後まで検索した後にマッチした件数を出力するため、この時点では出力がありません。その結果、この時点では入力データがテキストかバイナリか判定されません。
その後「\x0」が見つかり、この時点で入力データはバイナリとみなされます。既に入力データへの1行以上のマッチが確定しているため、検索を打ち切り、この時点までにマッチした行数「1」を出力します。*2

GNU grep 2.23では、-cオプションが指定された場合には、入力データがバイナリとみなされても、検索を打ち切らないように変更されています。

printf 'a\n%032768d\nb\x0\n%032768d\na\n' | LC_ALL=C grep -Pc a
2
||<<

ただし、この変更は、-cオプションを指定した場合が、指定しなかった場合よりも遅くなる可能性がある点に注意する必要があります。

*** grep -oPが無限ループする可能性がある不具合の修正

GNU grep 2.22で下記を実行してみてください。

>||
printf '\201_\0' | LC_ALL=en_US.UTF-8 grep -aoP _

永遠に「_」が出力され続けると思います。UTF-8において、内部でコールされているpcre_exec()は、入力データがUTF-8に適合していない場合にマッチした場所を示す変数が負数を返すことがありますが、GNU grep 2.22がそれが正しくハンドリングされておらず、入力データに対するポインタが行ったり来たりすることによって発生します。GNU grep 2.23では、マッチした場所を示す変数が負数だった場合には、入力データに対するポインタを戻さないように修正されています。

知られている問題

巨大なパターンによるgrep -Fiが遅い問題

下記のように、GNU grep 2.19以降で、マルチバイトロケールにおける巨大なパターンによるgrep -Fiが遅い問題が複数報告されています。

$ ls -adFl /usr/share/dict/linux.words
-rw-r--r-- 1 root root 4950996  2月 27  2009 /usr/share/dict/linux.words
$ grep -Fif /usr/share/dict/words in

これは、GNU grep 2.19以降、入力データが長い場合の検索性能を改善するため、grep -Fiに対してgrep -iと同じアルゴリズムを使用するように変更されたためです。grep -iはDFAを使用しますが、DFAはパターンのコンパイルに要する時間やリソースがパターンの長さに対して指数関数的に増大するため、大きく性能に影響します。*3

ところで、変更前はパターンと入力データの両方を小文字に変換してからBoyer-Moore法やCommentz-Walter法を使用して検索していました。しかし、マルチバイトロケールにおいては長い入力データを小文字に変換コストが大きい、変換後のデータを格納するための余分なバッファが必要、大文字と小文字のバイト数が異なるロケールではパターンにマッチした位置を正確に判断できないなどといった問題がありました。その上、マルチバイトロケールにおけるgrep -Fiが遅いなら、LC_ALL=Cでgrepすればよいこともあるため、不具合報告が複数上がっているものの、対処はさほど急がれていないようです。

*1:入力データがパターンに全くマッチしないケースでは出力がなくプログラムの実装による性能への影響が大きくなるため、GNU grepではこのようなケースに対して最適化されています。

*2:入力データがバイナリだった場合はマッチした行を出力する代わりに「Binary file ... matches」を出力して検索を打ち切ります。-cオプションが指定されている場合は、「Binary file ... matches」を出力しません。

*3:GNU grepでは、DFAの状態の生成を最大限に遅延させることによって、この影響を小さくする工夫がなされていますが、条件によってはパターンのコンパイルに時間を要したり、リソースを多く消費したりします。