正規表現の実装の難しさ

正規表現POSIXで定義されています。しかし、POSIXで定義されている正規表現POSIXロケール(LANG=C)しか考慮していないため、POSIX以外のロケールをサポートしようとすると様々な問題に遭遇します。それらについて見ていくことにしたいと思います。

不適切な位置でのマッチ

マルチバイトロケールでは、不適切な位置(マルチバイト文字の途中)でマッチした場合に、そのマッチは排除されなければなりません。たとえば、SJISにおいて「\」は0x5c、「表」は0x95 0x5cで定義されています。したがって、下記はPOSIXロケールであればマッチします。しかし、ja_JP.sjisでは、2バイト目(文字の途中)でマッチしていることになるため排除されなければなりません。

$ LANG=ja_JP.sjis; export LANG
$ echo 表マーク | grep '\マーク'
$

同様に、EUC-JPにおいて、「海」は0xb3 0xa4、「こ」は0xa4 0xb3で定義されています。したがって、下記はPOSIXロケールであればマッチします。しかし、ja_JP.eucJPでは、2バイト目(文字の途中)でマッチしていることになるため排除されなければなりません。

$ LANG=ja_JP.eucJP; export LANG
$ echo ここ | grep '海'
$

UTF-8以外のマルチバイトロケールにおいて不正な位置でのマッチを見つけるには、入力文字列を最初から各文字の区切りがどの位置にあるかをチェックしていく必要があります。libcのAPIには、マルチバイト文字のバイト数を取得する関数としてmbrtowc(3)やmbrlen(3)が用意されているため、これを使用してチェックできます。ただし、これらの関数は非常に負荷が高いため、高速化するためには工夫が必要です。

GNU grepでは、この負荷を低くするため、一般的な入力文字列が多くのシングルバイト文字で構成されていることに着目し、256個の各バイト表現が対象のロケールにおいてシングルバイト文字であるかどうかをあらかじめ配列上にキャッシュします。たとえば、ja_JP.eucJPでは、0x00-0x99はシングルバイト文字であることをキャッシュします。そして、シングルバイト文字ではない文字列に遭遇した場合のみmbrtowc(3)やmbrlen(3)を使用してバイト数をチェックします。

ピリオド表現「.」へのマッチ

シングルバイトロケールの場合、1文字は常に1バイトで表現されるため、「.」はいつも1バイトにマッチします。それに対して、マルチバイトロケールでは、1文字が複数バイトで表現されることもあるため、「.」も複数バイトにマッチする可能性があります。

$ LANG=ja_JP.utf8; export LANG
$ echo B | od -tx1
0000000 ef bc a2 0a
0000004
$ echo B | grep '^.$'
B
$

このため、マルチバイトロケールでは「.」を含む正規表現を事前に完全にコンパイルしておくことは難しく、事前にコンパイルできなかった部分は実行時にコンパイルする必要があります。しかし、それは実行時の性能劣化をもたらし、入力文字列が長ければ長いほど顕著になります。

GNU grepでは、「.」を含む正規表現の性能劣化を回避するため、汎用的とされるUTF-8においては、「.」を下記のパターンに置き換えています。これにより、「.」を含む正規表現であっても事前に完全にコンパイルできます。

([0x00-0x7f]|[0xc2-0xdf][0x80-0xbf]|[0xe0-0xef[0x80-0xbf][0x80-0xbf]|[0xf0-f7][0x80-0xbf][0x80-0xbf][0x80-0xbf])

ただ、これだけではUTF-8以外のマルチバイトロケールに対しては遅いままです。*1そこで、「.」が常に決まった文字列にマッチすることに着目し、「.」にマッチした場合の状態遷移と「.」にマッチしなかった場合の状態遷移をキャッシュすることで高速化を実現するパッチがリクエストされています。

ブラケット表現へのマッチ

ブラケット表現とは、[abc]、[A-Z]といった表現です。ブラケット表現もピリオド表現と同様にマルチバイトロケールでは複数バイトにマッチする可能性があります。

$ LANG=ja_JP.utf8; export LANG
$ echo B | od -tx1
0000000 ef bc a2 0a
0000004
$ echo B | grep '^[A-C]$'
B
$

他方、ブラケット表現はシングルバイトロケールにおいても複数文字からなる照合要素が定義されているロケールでは複数バイトにマッチする可能性があります。*2

たとえば、スペイン語ロケール(es)では、「c」と「d」の間に「cH」、「ch」といった複数文字からなる照合要素が定義されています。そのため、ブラケット表現は「ch」という2文字にマッチする可能性があります。

$ LANG=es_US.iso88591; export LANG
$ echo ch | grep '^[a-z]$'
ch
$

また、POSIXロケールではc < cg < ch < ci < dとなるところ、スペイン語ロケールでは複数文字からなる照合要素が定義されていることによりc < cg < ci < ch < dとなります。なぜなら、「cg」は「c」+「g」、「ci」は「c」+「i」と分解され最初の文字は「c」であるのに対して、「ch」は複数文字からなる照合要素が定義されているため分解されず最初の文字は「ch」として比較されるため、「cg」と「ci」が「ch」よりも前に位置すると解釈されるからです。

加えて、ブラケット表現では文字クラス(:alpha:など)や等価クラス(=a=など)も既定されており、POSIX以外のロケールをサポートする正規表現の実装の難易度を一段と高くしています。

これらに対するマッチを実現するためには、libcで定義されているロケールの情報にアクセスするか、自身でサポートするロケールの情報や文字コードの変換テーブルを実装する必要があります。
しかし、前者についてはlibcで定義されているロケールの情報にアクセスできるAPIは非常に限られており、後者についてはlibcと同レベルのロケールをサポートしようとすると実装が極めて困難なため、POSIX以外のロケールでもブラケット表現を厳密に取り扱える正規表現を実装することは現実的ではありません。そこで、ブラケット表現を含む正規表現に対しては、libcが用意しているregex(3)ライブラリに頼るのが無難な選択といえるでしょう。

GNU grepは高速化のため独自のDFAエンジンを使用しますが、ブラケット表現に対してはregex(3)を使用します。しかし、regex(3)はブラケット表現や後方参照(\1, \2, ...)をきっちりサポートしていることで、性能面で大きなペナルティを負っています。そこで、GNU grepでは、先にブラケット表現以外の部分がマッチするかどうかをチェックし、マッチした行に対してのみregex(3)を使用します。*3

大文字/小文字の区別の無視

「大文字/小文字の区別の無視」とは、grepを-iオプション付きで起動する場合に相当します。POSIXや日本語ロケールでは、ある小文字について大文字の小文字は元の小文字に一致し、ある大文字について小文字の大文字は元の大文字に一致します。しかし、一部のロケールでは必ずしもそうではありません。

たとえば、トルコ語では、「I」と「i」にそれぞれ2つのバージョンがあります。1つはドットなし(POSIXロケールで定義されているものと同じもの)で、もう1つはドットあり(POSIXロケールでは定義されていないもの)です。

ケース 大文字 小文字
ドットなし U+0049 U+0069
ドットあり U+0130 U+0131

そして、大文字/小文字の変換ルールは下記のように定義されています。

文字 toupper tolower
U+0049 U+0049 U+0069
U+0069 U+0049 U+0069
U+0130 U+0130 U+0069
U+0131 U+0049 U+0131

すなわち、ドットあり「I」(U+130)の小文字はドットなし「i」(U+0069)で、その大文字はドットなし「I」(U+0049)となり、元の文字には一致しません。同様に、ドットあり「i」(U+131)の大文字はドットなし「I」(U+0049)で、その小文字はドットなし「i」(U+0069)となり、元の文字には一致しません。

POSIXロケールではこのような状況は発生しないため、regexを定義しているPOSIXでもこのような点まで考慮されておらず、グレーゾーンとなっています。

また、UTF-8には合字と呼ばれる文字が存在します。たとえば、「LJ」(U01C7)であり、これで1文字を構成します。そして、これらの文字には、大文字(LJ)と小文字(lj)以外に、タイトルケース(Lj)が存在します。これについても、POSIXロケールには存在ないため、どのように扱うべきか定義されていません。グレーゾーンです。

まとめ

正規表現POSIXで定義されています。しかし、POSIXで定義されている正規表現POSIXロケール(LANG=C)しか考慮していないため、POSIX以外のロケールをサポートしようとすると様々な問題に遭遇します。本記事を読んでいただいて、POSIX以外のロケールをサポートする正規表現の実装の難しさのみならず、ロケールの奥深さや面白さを感じ取っていただければ幸いです。

*1:全てのロケールに対してパターンの置き換えを行えばよいのではないかと思われるかもしれません。しかし、OSもしくはlibcによって定義されているロケールの種類や内容には差異があります。そのため、汎用的ではないロケールまで決め打ちしてしまうと、移植性や互換性、ロケールの拡張性が失われてしまうリスクが生じます。

*2:ピリオド表現はシングルバイトロケールにおいて複数バイトにマッチすることはありません。

*3:以前は独自のDFAエンジンでマルチバイトロケールにおけるブラケット表現を部分的にサポートしていました。しかし、マルチバイトロケールにおけるブラケット表現の完全なサポートが不可能であることや、マルチバイトロケールにおけるブラケット表現のサポートが高速性が売りであるDFAエンジンの足かせになることから、現在のリリースでは残骸を除いて削除されています。