Onigmo 5.10.2 で、Unicode 以外のエンコーディング利用時に、\p{} が (?a) の影響を受けるバグが判明。
これとは別に、オリジナルの Oniguruma は、ISO-8859-1 などを利用時に、[[:word:]], \p{Word} が ASCII 範囲外の文字（例えば Ä など）にマッチしないことに気付いた。\w は、Ä などにもマッチする。
Perl ではどうかというと、unicode フラグが立っている文字列であれば、\p{Word}, [[:word:]], \w はいずれも ASCII 範囲外の文字にもマッチする。(?a) オプションを指定すると、[[:word:]], \w は、マッチが ASCII 範囲内に制限されるが、\p{Word} は影響を受けない。Perl での動作に合わせた方がいいだろう。
Shift_JIS や EUC-JP での \p{Word} の動作は、多バイト文字は全てマッチするという大ざっぱな動作だが、これを完全に Unicode に合わせる（例えば全角記号類をマッチしないようにする）のは正直やり過ぎだろう。そういえば、Shift_JIS だと半角カタカナが \w にマッチしない。Unicode に合わせるならこれもマッチすべきだがどうすべきか。
Oniguruma で .* で始まる一部のパターンが遅い問題を引き続き調査。
.* をマッチ処理する際、通常は文字を 1つ進めるたびに、バックトラックできるように状態をスタックにプッシュしていく。
.* の次の文字が固定文字列ならば、少なくとも 2つの最適化処理が働く。1つ目は、その固定文字列で検索対象の文字列を高速検索（BM法）し、見つからなければマッチ処理を行わない。2つ目は、マッチ処理を行う際に、文字を 1つ進めるたびに、その次の文字をチェックし、文字が一致しないならば状態をスタックにプッシュしない。これによりバックトラックの回数を大幅に減らせる可能性がある。
.*[Aa]4 のようなパターンの場合、検索対象に 4 が無ければそもそもマッチ処理を行う必要がないが、そのような最適化は行われていない。.* で文字を １つ進める際に次の文字が A でも a でもなければ、状態をプッシュする必要はない。
.*(?:あ|い) や .*[あい] のようなパターンの場合、.* の次の 1byte は Shift_JIS ならば 0x82 に決まる。UTF-16LE であれば、バイト単位で扱えば .*[\x42\44]\x30 と同じこととなり、.*[Aa]4 が最適化できるならば、これも最適化できる可能性がある。
How to Implement World Fastest Grep. の正規表現の速度比較で、Oniguruma がダントツの最下位となった (Python|Perl|Pascall|Prolog|PHP|Ruby|Haskell|Lisp|Scheme) というパターンについても少し調べてみた。詳説正規表現では、このようなパターンの高速化方法として、(?=[PRHLS]) を頭に付けてマッチ開始位置を限定する方法が紹介されていたが、同等の機能はすでに Oniguruma に実装されていることが判明した。そうなると、どうすれば高速化できるのだろう。このような場合の高速なアルゴリズムがあると聞いたが名前を忘れた。再度調べないと・・・Commentz-Walter法だった。他にも色々あるらしい。
Onigmo 5.10.2 で実装した暗黙のアンカーによる最適化に問題が発覚。.*a を ^.*a に置き換えてしまうと、行の途中から検索を始めたときの動作が異なってしまう。
よく見ると、暗黙のアンカーによる最適化は、（Perl で言うところの）シングルラインモードの時の処理は既に Oniguruma に入っていた。この処理に対して、非シングルラインモードでの最適化処理を追加する方法を考えてみたが、いい方法が思い浮かばない。結局、非シングルラインモードの場合は、昨日作った部分の処理に手を加えて、/.*a/ ==> /(^|\G).*a/ と変換すれば良さそうな気がする。
暗黙のアンカーによる最適化が、シングルラインモードと非シングルラインモードで全く別のやり方で実装することになってしまったのが気に入らない。何かうまい方法はないだろうか。
Onigmo 5.10.1 で Unicode 以外のエンコーディング利用時に、(?a) が \d, \h, \s に対して有効になっていないバグが判明。修正した。
暗黙のアンカーによる最適化を実装してみた。サクラエディタふぁんくらぶ part14 の >>536 に記載されている通り、zenkoku.csv の , を a に置換したデータに対して、(?i).*a4 で検索する場合は大幅に速度が向上した。ただ、>>527 は元々が ^.*=code0 ということで先頭に ^ がついていることから速度向上は期待できそうにない。
自動強欲化はオリジナルの Oniguruma で実装済みだった。
条件式 (?(cond)yes|no) で、条件として先読みや戻り読みも使えるようにすべきか？ 詳説正規表現によれば、多くの実装では後方参照と先読み・戻り読みが条件として使えるようになっているらしい。ちなみに、SkRegExp でも先読み・戻り読みが条件として使える。対応したいが難しそう。
Oniguruma が特定のパターンで遅い問題を調査中。Oniguruma の regint.h の中にある ONIG_DEBUG_MATCH の定義を有効化してコンパイルし、動作中の様子を確認することにした。遅くなるパターンでは、非常に無駄な動きをしていることが判明。
.* で始まる一部のパターンが遅い問題は、詳説正規表現 第3版 6.4.5.2 (p.242) に記載されている暗黙のアンカーによる最適化 (Implicit-anchor optimization) を使えば、高速化できそう。しかし、これでもまだ Bregexp.dll より遅そう。
1文字の文字クラスに対して最適化が行われていないことも判明。例えば、[a] は a と同じ意味だが、[a] は固定文字列として扱われず、最適化が行われない。
詳説正規表現に自動強欲化という最適化が記載されていた。これを実装してみるのもおもしろそう。
2ch のサクラエディタスレで bregonig.dll が Bregexp.dll に比べて異常に遅いという報告があった。普通の使い方では、bregonig.dll の方が高速なはずだが、いったいどんなデータなんだろう。手元では再現できず。
住所データCSV【住所.jp】の csv_zenkoku.zip に入っている zenkoku.csv を編集し、, を a に置換したデータに対して、(?i).*a4 で検索を行うと、非常に遅いことが判明。詳細は後で調べよう。
Onigmo 5.10.1 を公開。何とか (?(cond)yes|no) に対応できた。ただし、(cond) に使えるものは後方参照のみで、先読み・戻り読みなどは使えない。
(?<=a).*b が aab にマッチしないのを修正するために、.* の最適化が無効化されていたのも修正した。パターンの中に戻り読みが含まれている場合は、.* の最適化を行わず、それ以外の場合は最適化を行うようにした。bregonig.dll が遅いパターンがこれで改善されればと思ったのだが、残念ながら今回は関係なかった。
Onigmo 5.10.0 を正式版として公開。GitHub では好きなバージョンをアーカイブファイルで取得できるので、正式版とそうでないものの違いはあまり明確ではない気がするが、タグ付けされているかどうかが一応の目安だろう。
Oniguruma 5.9.2 で Perl 5.14 に比べて不足している機能の内、自分が欲しいと思っていた機能はだいたい実装できた。あとは、(?|...), (?(cond)yes|no) も実装したいが、難しそうなので当分放置かもしれない。\h, \H, \v, \V, \o{nnn} は、あまり有用性を感じていないので、今のところ予定無し。さらに char type のビットを使い切ってしまっているという点で \h, H, \v, \V の実装方法は悩ましい。
Oniguruma for Java (onig4j) や Ruby の改造のマージも課題。onig4j の改行コード部分の処理はコンパイルオプションで切り替えるようになっているが、実行時のオプションで切り替えられるようにしたいところ。Ruby は、不足していた終端チェックを追加しているが、修正箇所があまりに多くてどうしたものだか。エンコーディング周りにもかなり手が加えられている。
partial matching もできることなら対応したいが、全く理解できていない。
bregonig.dll のβ版も 2.50 beta6 に更新。新規 API を 2つ追加し、従来のパラメータ解析の処理を大幅書き換え。新規 API では ANSI 版で UTF-8 も使えるようになった。
今後の拡張性を考えると、もうちょっと仕様を練った方がよいか？ 例えば partial matching とか。
先日作った、AviUtl のジャンプウィンドウプラグインでマウスホイールの横スクロールを使えるようにするプラグインを使って CM カットしたが、これは便利だ。何でもっと早く思いつかなかったのだろう。
おもしろそうなイベントがあることを知ったが、申し込もうかと思ったときには既に満員だった。（Shibuya Perl Mongersテクニカルトーク#16 夏の正規表現祭り） 発表者に豪華な顔ぶれがそろっている。
Git の改行コードの扱いが悩ましい。Windows の CRLF 改行のファイルに git am コマンドを使ってパッチを当てようとすると、エラーになってしまう。基本的には、Git で扱うファイルは全て LF 改行とし、Windows で CRLF 改行として扱いたい場合は git config core.autocrlf true としろということか。一部のファイルを LF で扱い、一部のファイルを CRLF で扱うにはどうすればよいのか？
やはり Linux 開発用に作られただけあって、Windows 向けのサポートはおざなりな印象を受ける。
Onigmo (Oniguruma-mod) を改良中。Shift_JIS, EUC-JP で、\p{Han}, \p{Latin}, \p{Greek}, \p{Cyrillic} が使えるようになった。Shift_JIS で 85区以降の漢字の扱いをどうするかという問題があったが、とりあえず Shift_JIS と CP932 に分離することにした。EUC-JP についてはよく分かっていない。特に、JIS 第三水準や第四水準がどうなっているのやら。
実装方法を悩んでいた (?R), (?0), (?+n) も使えるようになった。気付いてしまえばそれほど難しいことではなかった。
Onigmo (Oniguruma-mod) を改良中。Shift_JIS, EUC-JP で、全角アルファベット、ギリシャ文字、キリル文字を大文字小文字同一視検索ができるようになった。これで、SpringM 機能強化パッチの migemo でも全角の大文字小文字同一視検索ができるようになるはず。
鬼車の改造版を Onigmo (Oniguruma-mod) として GitHub に公開した。日本語表記はどうするかまだ決めていない。オニク゚モ、オニグモ、鬼蜘蛛、鬼雲、……。
鬼車の改造版のバージョン管理ツールとして Git を使い始めた。ローカルで履歴をきれいに清書した上で外部に公開できるのは便利である。また、1つのファイル内の複数の修正を別々にコミットすることもできるのが便利である。今まで Subversion で、「ここの変更は今回の修正とは関係ないので今回はコミットしたくない」ということが何度もあった。
GitHub に登録してみた。鬼車の改造版のソースを公開するのによい場所を探していた。バージョン管理ツールとして何を使うかが、どのサービスを選ぶかに影響するが、Git を使い始めたので、それが使えるサイトということで、GitHub にしてみた。
Perl 5.14 の正規表現（特に character set modifier）の動作をいろいろ調べてみた。
(?i) を指定すると、(?adlu) の指定に関わらず、全角アルファベットの大文字小文字を区別しない。キリル文字、ギリシャ文字も同様。\p{Word} は、(?au) の指定の影響を受けず、常に ASCII 外の文字にもマッチする。\w, [:word:] は受けて (?a) を指定した場合は ASCII 外の文字にはマッチしなくなる。他の POSIX ブラケットも同様。
(?dl) の動作はよく分からない。Unicode 文字列を扱う分には (?u) と変わらないのか？
Perl と Java で (?du) の意味が異なるのが悩ましい。
鬼車の改造版で、(?adlu) を使えるようにしてみた。特に (?a) が使えるようになったのは個人的に嬉しい。
bregonig.dll のβ版を公開した。空文字列を受け付けるように仕様変更したほか、\R, \K, \X に対応した。
鬼車で Perl の \X を使えるように改造してみた。Unicode 系エンコーディングならば (?:\P{M}\p{M}*)、それ以外ならば (?s:.) 相当の構文木に置き換えるようにした。一応ちゃんと動いているようだ。
\K にも対応させたいが、こちらはパーサだけでなく regexec.c の修正も必要になる。しかし、まだ中身を全く理解していない。
いろいろいじっていたら、どうやら \K も使えるようになったようだ。バックトラックが発生したときの動作など、よく分からない部分もあったが、何とか動いている。一旦、bregonig.dll のβ版という形で公開しようかと考えている。
おっと、\R の動作がおかしい。何とか修正完了。
今まで、マウスのホイールを使ったときに、マウスポインタがあるウィンドウがスクロールするようにするためのソフトとして、Wheel Redirector を使っていたが、更新が停止しており、横スクロールに対応していないなどの問題があるので、代わりのソフトがないか探してみた。
かざぐるマウスというソフトが良さそうなので試してみた。
横スクロールだけでなく、Let's note の円形タッチパッドによるホイール操作が、Wheel Redirector ではリダイレクトできないという問題があったが、かざぐるマウスではリダイレクトできているようだ。
AviUtl のジャンプウィンドウプラグインで、マウスホイールの横スクロールが使えないのが以前から不便に思っていた。メッセージをフックして、WM_MOUSEHWHEEL をスクロールバーのメッセージに置き換えてしまえば良さそうだと思い、早速試してみた。
ジャンプウィンドウ YUV2 Wrapper のソースを参考にして作ってみた。とりあえず意図したとおりに動作するようになった。しかし、まだあまり使っていない。
昨日の、鬼車で \R を使えるようにするための改造があまりにも場当たり的なので、もう少しまともな方法として、(?>\x0D\x0A|[\x0A-\x0D\x{85}\x{2028}\x{2029}]) に相当する構文木をプログラムで組み立てるようにしてみた。時間が掛かったが、何とかできあがった。
\R 以外に \X も同様に、(?:\P{M}\p{M}*) 相当の構文木に置き換えればよいはずなので、パーサの改造で対応できそう。
\R, \X のように同等の記述がある場合、パーサでそれに置き換えてしまうのがよいのか、それとも専用のオペコードを用意した方がよいのか。
鬼車で、Perl 5.10 で導入された \R を使えるようにしようと、改造してみた。何とか \R が使えるようになった。構文解析の途中で \R が見つかったら、代わりにあらかじめ用意してある "(?>\x0D\x0A|[\x0A-\x0D\x{85}\x{2028}\x{2029}])" という文字列を構文解析するという、その場しのぎの方法。
python から bregonig.dll の Unicode 版 API を呼び出そうとしてはまった。BSubstW() で \n 以降が切り捨てられる？と思ったが、ctypes を使っているため、長さをバイト数で指定しないといけないのに、文字数で指定していたのが原因だった。（普通に C/C++ から呼び出す場合は、WCHAR に対するポインタ演算をすればよいので、文字数でよい。）
Perl 5.14 の perlre を読んでいるが、モディファイヤが 4つも増えている。/a, /u は、bregonig.dll にも欲しい。Unicode モードで、\w や \d が ASCII 外の文字にもマッチするのは正直鬱陶しかった。