May 02, 2008

XUL/Migemoで正規表現検索をできるようにするにあたって、正規表現で後方検索する方法を考えてみたよ

好きなように正規表現で検索できるようになりました。XUL/Migemo 0.8.0からの新機能ということになります。というかAPIとしては持ってたのにUI上から利用する手段が今までなかった。

「普通の検索」と「正規表現」と「Migemo」の3モードが排他的な切り替えということになるので、UIをどうするか迷って、チェックボックスを増やしてみたりドロップダウンリストを置いたり色々試してみたけど、最終的にはラジオボタンを並べる形に落ち着いた。

使う側としてはややこしくなってしまったので、せめてちょっとでも使い勝手をよくしておきたいと思って、キーボード操作だけで検索モードを切り替えたり、入力内容が /ほげほげ/ みたいな正規表現リテラルっぽい形だったら自動的に正規表現検索に切り替えたり(判別にはNarcissus由来の正規表現を使わせてもらいました)、という風な工夫も入れてみたけど、実際の所どうだろう。

という外見でよく分かる変更の他に変わった所では、後方検索の仕組みを今までとガラッと変えてみた。

元々の作者のplus7さんはどうされていたかというと、正規表現のマッチングで後方検索ができないから、「正規表現の内容を前後逆にひっくり返して」「検索対象の範囲のテキストも全部反転して」その上でマッチングを行う、という方法を採っていて、僕が引き継いだ後もそこは変わりなかった。

var regexp = /(ほげ|hoge|foo|bar)/;
var text = 'ほげほげ、hogehoge。foo? bar。';
// ここで、「bar」「foo」「hoge」「hoge」
// 「ほげ」「ほげ」の順に検索したい

regexp = regexp.compile(
     regexp.source
          .split('')
          .reverse().join('')
          .replace(/\)/g, '[[')
          .replace(/\(/g, ')')
          .replace(/\[\[/g, '(')
   );
text = text.split('').reverse().join('');

var found;
while(text.match(regexp))
{
  found = RegExp.lastMatch.split('').reverse().join('');
  alert(found);
  text = RegExp.rightContext;
}

(なんでこんなややこしいことをするのかについてはplus7さんの技術解説を参照のこと)

しかし、この度正規表現検索機能を表に出すにあたって重大な問題が発覚した。元の「正規表現を反転する処理」は、反転しなきゃいけない正規表現がXUL/Migemo自身の生成したごく単純なパターンの物だけだから、かなり簡単な作りになっていた。でも、ユーザが手入力で凝った正規表現を入力すると、途端に処理がうまくいかなくなってしまう。

これは非常にまずい。ということでなんとかならないかと考えてみた。

まず、正規表現を反転する処理をもっと改善する事を考えてみた。でもこれは早々に諦めた。調べてみればみるほど、正規表現という物は複雑怪奇な書き方ができるようで、その全部の記法に対応するなんでのはとてもじゃないけど僕の頭じゃ無理。

となると残された道としては、正規表現も検索対象の範囲のテキストも反転せずにどうにかして後方からマッチングを行う方法を見つけるしかない。

んでJavaScriptのリファレンスを見ながらうんうん考えてたんだけど、ふと思いついた方法を試してみたらなんとバッチリうまくいった。そのやり方というのは、「g」フラグを使うというもの。

gフラグを付けてマッチングを行うと、「最後にヒットした箇所」はマッチングの結果の配列の最後の要素として取得できる、というのは当たり前。でもそれだけじゃなくて、実験して確認してみたら、この時のRegExp.leftContextRegExp.rightContextは、gフラグ無しの時は最初にマッチした箇所から見た「それより前」と「それより後」だったのが、今度は、最後にマッチした箇所に対する物になっていた(よく考えてみれば当たり前のことだけど、今まで全然気付いてなかった)。

ということは、このleftContextを次の検索のマッチング対象にし、そこでもまたgフラグを使って、さらにその時のleftContextを次の検索のマッチング対象にして……という風に繰り返していけば、「正規表現で後ろから検索」するのと同じ結果が得られるわけだ。

var regexp = /(ほげ|hoge|foo|bar)/;
var text = 'ほげほげ、hogehoge。foo? bar。';

regexp = regexp.compile(regexp.source, 'g');
var found;
while(text.match(regexp))
{
  found = RegExp.lastMatch;
  alert(found);
  text = RegExp.leftContext;
}

というわけで無事、どんな正規表現でも問題なく後方検索にかけることができるようになった次第です。しかも文字列の分割とか連結とか配列の反転とかいろんな処理がゴッソリ不要になったから、長いページでは後方検索がちょっと高速になったんじゃないかと思う。

エントリを編集します。

wikieditish message: Ready to edit this entry.











拡張機能