awkで正規表現をレコード区切りにするときの制約

awkではFS変数によってフィールド（カラム）の区切り文字を変えることができるが、これには正規表現を使うこともできる。レコード（行）の区切りを変更するためにはRS変数を使う。オリジナルのawkではこちらには正規表現を使えない。PerlのRS変数でも使えない。

でもmawkやgawkではRS変数に正規表現を書いてもよい。たとえばRSを「\n\n+」にすれば複数の改行文字をレコード区切りにできる。

mawkで次のような実験をしてみよう。RSに指定する正規表現を「(bc)+」（1回以上の「bc」の繰り返し）とする。これは「abcbcd」という文字列を「a」と「d」の2レコードに分割する（ex.1）

$ echo "abcbcd" | mawk 'BEGIN{RS="(bc)+";}{print;}' # ex.1
a
d

「(bc)+」という正規表現は「bc」の数を（1以上であれば）問わない。もっとbcの数を増やしたらどうだろうか。（ex.2～4）

$ perl -e 'print "a" . ("bc")x2046 . "d";' > abcd # ex.2
$ mawk 'BEGIN{RS="(bc)+";}{print;}' < abcd
a
d
$ perl -e 'print "a" . ("bc")x2047 . "d";' > abcd # ex.3
$ mawk 'BEGIN{RS="(bc)+";}{print;}' < abcd
a
d
$ perl -e 'print "a" . ("bc")x2048 . "d";' > abcd # ex.4
$ mawk 'BEGIN{RS="(bc)+";}{print;}' < abcd
a

d

3つ目の結果は期待したものではない。この例ではmawkはあたかもaとdの間に「2つのレコード区切り」があるかのようにふるまってしまっている。

もうちょっと試してみよう。今度は「bc」の数は2048回のままで、頭の「a」の数を変えてみる。（ex.5～6）

$ perl -e 'print "aa" . ("bc")x2048 . "d";' > abcd # ex.5
$ mawk 'BEGIN{RS="(bc)+";}{print;}' < abcd
aa
d
$ perl -e 'print "aaa" . ("bc")x2048 . "d";' > abcd # ex.6
$ mawk 'BEGIN{RS="(bc)+";}{print;}' < abcd
aaa

d

なぜこんなことになるのか。mawkは次のような処理で入力ファイルからレコードを切り出している。

1. 4096バイトのバッファに入力ファイルから読み込む
2. バッファに対して正規表現のマッチを行う。

マッチしなかった場合はバッファを拡張してさらに読み込んで再度2を行う。これは特に問題ない。

マッチした場合に問題がある。単純に考えれば、マッチしたらマッチしたところまでの文字列をレコードとして切り出せばよい。でもこの考え方は固定文字列の区切りには有効だけど、正規表現の場合は間違っている。
バッファはあくまでも入力ファイルの途中までの内容を表すに過ぎないのだから、「もうちょっと読み込めばもっと長い文字列にマッチするかもしれない」という可能性を排除できないのだ。

mawkはその辺を少し考慮していて、fin.cのFINgets関数（ファイルからレコードを切り出す関数）には次のようなコメントが付与された処理がある。

/* if the match is at the end, there might still be
   more to match in the file */

つまり正規表現のマッチ範囲がバッファの終わりまで到達していたら「もうちょっと読み込めばもっと長い文字列にマッチするかもしれない」。mawkはこのようなケースではバッファを拡張し、さらに入力ファイルから読み込んで再度2のマッチを行う。

ex.5の例で、最初4096バイトのバッファには「aa」と「bc」の2047回分が入っていて、最後の「bcd」はまだ読まれていない。「(bc)+」はバッファの3文字目から2047回目の「bc」までマッチする。マッチはしたのだがバッファの最後まで到達してしまったのでバッファを拡張して「bcd」を読み込む。再度のマッチで2048回目の「bc」までマッチし、期待通りの結果を得る。

ex.4とex.6はなぜうまくいかないのか。それはバッファの拡張を判断する条件が「バッファの終わりまでマッチしたか」では不十分だからだ。

ex.4の例で、最初バッファには「a」と「bc」の2047回分、そして「b」が入っている。「cd」がまだ読まれていない。このような例で、「(bc)+」はバッファの2文字目から2047回目の「bc」までマッチする。これはバッファの最後までマッチしていない。「b」が残っているからだ。したがってmawkはそこまでをレコード区切りと認識する。次のレコードを読み込むときはマッチしないのでレコードを拡張し、「bcd」を余計な空レコードと「d」に切り出す。

本当は最初のバッファに対するマッチで最後の「b」が残ったとき、本当は「このbに対して次にcが来るとしたらもっと長い文字列にマッチするかもしれない」と考えるべきだったのだ。

とはいえこれは簡単な話ではない。mawkはglibcのregcomp/regexecを使っているが、これには「ここまでマッチはしましたけど、後続の文字列は最後まで来たところでバックトラックしたんで、もうちょっと文字列を足せばもっとマッチするかもしれませんね」ということを報告してくれる機能を持たないからだ。

ちょっと調査したみたところではPCREも鬼車もこういう機能を持たない（ちがってたらすみません）。Henry SpencerのTcl向けの正規表現エンジンはREG_EXPECTという独自のフラグを持っていて、どうもあやしいのだがドキュメントが不十分で確信が持てない。

そのような機能を持つ正規表現エンジンを使わない限り、「任意の正規表現のレコード区切りと任意の入力に対して正しいレコードを切り出す」には入力ファイルを全部読み込むしかないだろう。