概要
田中哲さん(@tanaka_akr)が以前提案された「非包含オペレータ」というものを（実験的に）鬼雲に実装しました。これを使うと例えば C 言語のコメントにマッチする正規表現などが簡単に書けるようになります。
ここでは、非包含オペレータとは何か、また今後の見通しなどについて説明します。
非包含オペレータとは？
非包含オペレータは田中さんが約 9 年前に発表された、正規表現の拡張です。理論的背景と実装例は以下のスライドと論文に示されています。
従来の正規表現では、「特定の文字以外の 1 文字にマッチする正規表現」は文字クラスの否定を使って [^x] のように書くことができますが、それに対して「特定の文字列を含まない文字列にマッチする正規表現」は簡単に書くことはできませんでした。
（[^(str)] などと書いて、str 以外の文字列にマッチすると思ってしまうのは初心者によくある間違いです。もちろんこれは (, s, t, r, ) 以外の任意の 1 文字を意味します。）
例えば、C 言語のコメントは /* で始まり、*/ で終わる文字列で、その中に */ を含むことはできませんが、それにマッチする正規表現は次のようになります。
\/\*[^\*]*\*+(([^\*\/][^\*]*)\*+)*\/
エスケープを簡単にするため、/, * を a, b に置き換えると以下のようになります。
ab[^b]*b+(([^ba][^b]*)b+)*a
非包含オペレータを使うとこれを簡単に記述することが可能になります。
文法
論文では、非包含オペレータに !r という表記を使用していますが、鬼雲では既存の文法との互換性のため、(?~subexp) という表記を使うこととしました。
（Perl の流れをくむ正規表現では、文法を拡張する際には、\ + アルファベット 1 文字 あるいは、(?...) 形式のいずれかを使うことになっています。）
(?~subexp) は、subexp にマッチする文字列を含まない任意の文字列にマッチします。
例えば (?~abc) は、"", "ab", "aab", "ccdd" 等にマッチしますが、"abc", "aabc", "ccabcdd" 等（の文字列全体）にはマッチしません。
先ほどの C 言語のコメントの例は、非包含オペレータを使うと以下のように書くことができます。
\/\*(?~\*\/)\*\/ab(?~ba)ba
従来の簡易的な記述
「特定の文字列を含まない文字列」を正規表現で記述するのは非常に困難であるため、以下のような簡易的な記述が使われることがよくあります。
最短一致の繰り返し:
\/\*.*?\*\/ab.*?ba
バックトラックの抑制:
\/\*(?>.*?\*\/)ab(?>.*?ba)
否定先読み:
\/\*((?!\*\/).)*\*\/ab((?!ba).)*ba
ただ、論文に示されているとおり、いずれの記述にも欠点があり、正しくマッチしない場合があったり、理論的な扱いに難があったりします。
非包含オペレータは、いずれの記述と比べても簡単で、理論的な扱いにも問題がありません。
なお、非包含オペレータは否定先読みを使ったものと似たように動作しますが、全く同じという訳ではありません。例えば、^((?!abc).)*c$ は "abc" にはマッチしませんが、^(?~abc)c$ は "abc" にマッチします。なぜなら (?~abc) は "ab" にマッチするからです。
実装
論文における実装例では、以下のようなシンプルな例が示されています。
def try_absent(r, str, pos)
limit = str.length
pos2 = pos
while pos2 <= limit
try(r, str, pos2) {|pos3|
limit = pos3-1 if pos3-1 < limit
}
pos2 += 1
end
limit.downto(pos) {|pos4|
yield pos4
}
end
while と try() {} の 2 重ループで、非包含オペレータのマッチ終端となり得る場所を探し出し、その後、limit.downto() {} のループで、非包含オペレータ以降のパターンのマッチを試みます。（動作の詳細は、スライドの 26, 27 ページや、論文を参照。）
鬼雲は VM 型であるため、複数のオペコードを組み合わせて同様のループを構成しています。実際の実装は以下のコミットで確認できます。
鬼雲の実装に興味がある方は、拙著「正規表現技術入門」第 5 章も合わせてご確認ください。
速度
現時点では速度の評価は行っていません。非包含オペレータは、不定長の文字列にマッチするオペレータであり、前述のように 2 重ループと 1 重ループの組み合わせとして実装されていることから、決して速くはないと予想されます。
否定先読みを使った記述との速度比較等は今後の課題です。
今後の見通し
非包含オペレータに対応した鬼雲の正式版は、大きな問題がなければ数週間から数ヶ月のうちに Ver. 6.1.0 としてリリースされる予定です。
同時に、bregonig.dll でも非包含オペレータを実験的に使えるようにする予定です。（ただ、もし今後 Perl が (?~...) を別の意味で使うようなことがあると、困ったことになりますが…。）
その後、2017年の年末頃にリリースされる予定の Ruby 2.5 にもマージされることになるはずです。
（Perl や他の言語でも同じ機能を採用してもらえるとうれしいですね。）
2017/01/17 追記: Onigmo 6.1.0, bregonig.dll 4.10 をリリースしました。
2017/02/12 追記: Onigmo 6.1.1 が Ruby にマージされました。
2017/03/16 追記: Onigmo 6.1.1 が Ruby 2.4 向けブランチにもマージされました。Ruby 2.4.1 から使えるようになると思われます。
2017/03/23 追記: Ruby 2.4.1 がリリースされました。このバージョンから非包含オペレータが使えるようになっているはずです。
参考リンク
非包含オペレータに関する記事がいくつか出ています。
- The New ‘Absent Operator’ in Ruby’s Regular Expressions – Ruby Inside – Medium
- Ruby 2.4.1新機能: Onigmo正規表現の非包含演算子(?~ )をチェック
雑感
非包含オペレータの提案については、2011 年の段階でいったん認識していたのですが、当時は鬼車の実装をまだよく理解していなかったため、実装できるスキルもなく、その後完全に忘れ去っていました。
以下のツイートを見たことで、再度その存在を認識して、今回の実装に至りました。
昔田中さんが提案してた正規表現の非包含オペレーターって鬼雲に入らんのだろうか
— Urabe, Shyouhei (@shyouhei) 2016年12月14日
提案から実装まで 9 年も掛かってしまいましたが、鬼車の中の人と Ruby の間の確執がなければとっくの昔に実装されていたのだろうかと思ったり思わなかったり。