RubyKaigi 2023での発表の「2進数の足し算を計算する正規表現」の解説
RubyKaigi 2023で「Make Regexp#match much faster」という発表をします、@makenowjust です。この発表では、ReDoS対策のためにRuby 3.2で導入された、正規表現マッチング (Regexp#match) の メモ化による最適化 について解説します。
さて、発表の中に次のようなスライドがあります。
このスライドはRubyの正規表現がいかに強力かを説明するためのもので、例として「2進数の足し算を計算する正規表現」を示しています。
また、このツイートで使っている正規表現も、実はこの正規表現です。
今回の記事では、この「2進数の足し算を計算する正規表現」の解説をしていきたいと思います。
「2進数の足し算を計算する正規表現」
コピペがしやすいように、スライドの画像ではなくテキストのコードで上の正規表現を出しておきます。
RE = /(?<s>[01](?=(?:(?<l0>(?<=0))|(?<l1>(?<=1)))[01]*\+(?<r>(?:\k<r-1>|(?!\k<r-1>))[01])(?:(?<r0>(?<=0))|(?<r1>(?<=1)))[01]*=(?<a>(?:\k<a-1>|(?!\k<a-1>))[01])(?:(?<a0>(?<=0))|(?<a1>(?<=1)))[01]*\z(?:(?<c>\k<l0+0>\k<r0+0>\k<a1+0>|\k<l1+0>\k<r0+0>\k<a0+0>|\k<l0+0>\k<r1+0>\k<a0+0>|\k<l1+0>\k<r1+0>\k<a1+0>)|\k<l0+0>\k<r0+0>\k<a0+0>|\k<l1+0>\k<r0+0>\k<a1+0>|\k<l0+0>\k<r1+0>\k<a1+0>|\k<l1+0>\k<r1+0>\k<a0+0>)(?:\k<l0+0>(?:\k<r0+0>(?:\k<a0+0>(?!\k<c-1>)|\k<a1+0>(?!\k<c-1>))|\k<r1+0>(?:\k<a0+0>\k<c-1>|\k<a1+0>(?!\k<c-1>)))|\k<l1+0>(?:\k<r0+0>(?:\k<a0+0>\k<c-1>|\k<a1+0>(?!\k<c-1>))|\k<r1+0>(?:\k<a0+0>\k<c-1>|\k<a1+0>\k<c-1>))))\g<s>|(?!\k<c-1>)\+\k<r-1>=\k<a-1>){0}\A\g<s>\z/
このコードを irb に貼り付けて実行することで、動作を確認できます。
irb(main):002:0> RE =~ "01+01=10"
=> 0
irb(main):003:0> RE =~ "110+001=111"
=> 0
irb(main):004:0> RE =~ "01+01=00"
=> nil
0 が返ってきているときがマッチした (2進数の足し算が正しい) ときで、nil が返ってきているときはマッチしていない (2進数の足し算が間違っている) ときです。
この正規表現の仕様をまとめます。
- まず、
/\A(?<left>[01]+)\+(?<right>[01]+)=(?<answer>[01]+)\z/にマッチする必要がある
(以下、各キャプチャで捕縛した文字列をleft,right,answerで参照します) -
left,right,answerの長さが等しい
(left.size == right.size && right.size == answer.size) -
left.to_i(2) + right.to_i(2) == answer.to_i(2)となっている - これらの条件を満たす文字列にのみマッチする
Rubyのプログラムで書くとこんな感じです。
def check_bin_sum(str)
return false unless str =~ /\A(?<left>[01]+)\+(?<right>[01]+)=(?<answer>[01]+)\z/
$~ => { left: , right:, answer: }
return false unless left.size == right.size && right.size == answer.size
left.to_i(2) + right.to_i(2) == answer.to_i(2)
end
check_bin_sum("01+01=10") # => true
check_bin_sum("110+001=111") # => true
check_bin_sum("01+01=00") # => false
ちなみに、この正規表現の表す言語 (文字列の集合) は正規言語と文脈自由言語のどちらでもありません[1]。これはRubyの正規表現 (Regexp) の表現力の高さを表しているのではないかと思います。
一体、どのようにして単一の正規表現で、2進数の足し算の計算を実現しているのでしょうか。
上位桁からの2進数の足し算の計算
正規表現は通常、文字列の左から右にマッチングしていきます。また、Rubyの正規表現の後読みアサーションは事前に長さの分かる正規表現しか利用できないので、後読みでマッチングの方向を右か左にする、ということも難しいです。一方で、2進数の足し算は普通、下位桁から繰り上がりを考慮して計算していきます。2進数の下位桁は文字列の右側にあるため、素朴に2進数の足し算をすることを考えると、マッチングの方向と2進数の桁の上下が逆になってしまいます。
しかし、今回の問題は足し算の左右の値だけでなく計算結果まで渡されて、それが正しいのかを検証する、といったものです。そのため、左右の桁の値と計算結果の桁の値を比較することで、前の桁で繰り上がりが起こったかどうかを確認することができます。例えば、現在注目している左の桁が 0 で右の桁が 1 にも関わらず計算結果の桁が 0 だった場合、前の桁で繰り上がりが起こっていることが分かります。
このように、上位の桁から前の桁でキャリーが起こっていたかどうかを推測して、計算結果が正しいかを確認していくことはできます。このアイディアをRubyのコードにすると、次のようになります。
def check_bin_sum_digits(left, right, answer)
carry, prev_carry = false, false
left.chars.zip(right.chars, answer.chars) do |l, r, a|
prev_carry = (l.to_i + r.to_i) % 2 != a.to_i
return false unless (l.to_i + r.to_i + (prev_carry ? 1 : 0) >= 0b10) == carry
carry = prev_carry
end
return false if carry
true
end
check_bin_sum_digits("01", "01", "10") # => true
check_bin_sum_digits("110", "001", "111") # => true
check_bin_sum_digits("01", "01", "00") # => false
3箇所の部分を並列に読み進める正規表現
正規表現のマッチングとして自然な処理順で2進数の足し算を計算していく方法は分かりました。それでは、この処理を正規表現に落とし込むにはどうすればいいでしょうか？
まず1つ目の問題として、どうやって3箇所 (左右・計算結果の2進数) を並列に1文字ずつマッチングしていくか、があります。これを解決するために、部分式の呼び出しとレベル指定の後方参照が利用できます。
次の正規表現 RE1 を見てください。
RE1 = %r{
(?<s>
[01]
(?=
[01]*
\+
(?<r>(?:\k<r-1>|(?!\k<r-1>))[01])
[01]*
=
(?<a>(?:\k<a-1>|(?!\k<a-1>))[01])
[01]*
\z
)
\g<s>
|
\+\k<r-1>=\k<a-1>
){0}
\A\g<s>\z
}x
この正規表現は左右と計算結果の2進数の文字数 (桁数) が同じ場合にマッチします。どのようにしてこれを実現しているのでしょうか？
そのカラクリは先読みと部分式の呼び出しとレベル付き後方参照にあります。
部分式の呼び出しは部分式 (名前付きキャプチャ) (?<xxx>...) の内容を、\g<xxx> で呼び出すことのできる機能です。部分式の定義をそのまま書くと普通に名前付きキャプチャとして扱われてマッチングされてしまうので、それを防ぐために {0} を付けてマッチングが行なわれないようにするのが定石です。
レベル付き後方参照は部分式の中で使える後方参照の機能で、\k<xxx+n> あるいは \k<xxx-n> の形式で、n 個先の呼び出し、あるいは n 個前の呼び出しでの名前付きキャプチャの内容に対して後方参照できます。
RE1 では冒頭で (?<s>...){0} と部分式を定義して、その直後の \A\g<s>\z で呼び出しています。また、この部分式 (?<s>...){0} では、1回の呼び出しで、先頭から3箇所を並列に1文字ずつマッチングしていきます。
左側に関しては通常の正規表現のように、1文字ずつマッチしていくことができます。そして、右側や計算結果の部分は先読みの中で読み進めることで、位置が進みすぎてしまうことを防いでいます。
しかし、先読みを使うと次の呼び出しのときに、前にどこまで読んだのかが分からなくなってしまいます。そこで、これまでに読んだ文字列をキャプチャ (後方参照) を使って記録する、という方法を取ります。それが (?<r>(?:\k<r-1>|(?!\k<r-1>))[01]) と (?<a>(?:\k<a-1>|(?!\k<a-1>))[01]) の部分です。これは、前の呼び出しでマッチした分に1文字追加してマッチして、さらにそれをキャプチャに保存します。よって、1文字ずつ読み進められるわけです。
条件分岐でキャリーを計算
ここまで分かれば、必要な道具はほとんど揃っています。あとは、今回の呼び出しで読んだ文字 (桁) が何だったかをキャプチャに記録して、それを参照してキャリーを計算するだけです。
というわけで、完成系の正規表現 RE2 は次のようになります。
RE2 = %r{
(?<s>
[01]
(?=
(?:(?<l0>(?<=0))|(?<l1>(?<=1)))
[01]*
\+
(?<r>(?:\k<r-1>|(?!\k<r-1>))[01])
(?:(?<r0>(?<=0))|(?<r1>(?<=1)))
[01]*
=
(?<a>(?:\k<a-1>|(?!\k<a-1>))[01])
(?:(?<a0>(?<=0))|(?<a1>(?<=1)))
[01]*
\z
(?:(?<c>\k<l0+0>\k<r0+0>\k<a1+0>
|\k<l1+0>\k<r0+0>\k<a0+0>
|\k<l0+0>\k<r1+0>\k<a0+0>
|\k<l1+0>\k<r1+0>\k<a1+0>)
|
\k<l0+0>\k<r0+0>\k<a0+0>
|\k<l1+0>\k<r0+0>\k<a1+0>
|\k<l0+0>\k<r1+0>\k<a1+0>
|\k<l1+0>\k<r1+0>\k<a0+0>)
(?:\k<l0+0>(?:\k<r0+0>(?:\k<a0+0>(?!\k<c-1>)
|\k<a1+0>(?!\k<c-1>))
|\k<r1+0>(?:\k<a0+0>\k<c-1>
|\k<a1+0>(?!\k<c-1>)))
|\k<l1+0>(?:\k<r0+0>(?:\k<a0+0>\k<c-1>
|\k<a1+0>(?!\k<c-1>))
|\k<r1+0>(?:\k<a0+0>\k<c-1>
|\k<a1+0>\k<c-1>)))
)
\g<s>
|
(?!\k<c-1>)\+\k<r-1>=\k<a-1>
){0}
\A\g<s>\z
}x
これの空白を消したものが、最初の正規表現 RE になります。
RE2 では、後読みを使って \k<l0+0>, \k<l1+0>, \k<r0+0>, \k<r1+0>, \k<a0+0>, \k<a1+0> に現在注目している桁が 0 か 1 かを空文字列で後方参照できるようにしています。よって、これを使って、前の桁でキャリーしているかどうかの条件を書き ((?<c>...))、その後に整合性が取れているかをチェックしています。
空文字列をキャプチャしているので、否定先読みで条件の否定が記述できるのがポイントです。
あとがき
今回は「2進数の足し算を計算する正規表現」について解説しました。普段の開発では部分式の呼び出しやレベル付きの後方参照といった機能を使うことはあまり無いかもしれませんが、上手く使うことで面白いことができる、ということが示せたのではないかと思います。
この正規表現を書くにあたって、Rubyの正規表現実装 (Onigmo) のかなり細かい挙動 (キャプチャされていない場合の後方参照や部分式呼び出しが使える条件など) に詳しくなりました。この経験はRubyにコントリビュートしていく上でいずれ役に立つかもしれません。‥‥立たないかもしれません。
また、複雑な正規表現の内部的な挙動を調べるには、ruby のソースコードを取ってきて regint.h の冒頭にあるコメントアウトされた ONIG_DEBUG_... というマクロを有効にするのが便利です。そこまでして正規表現を書かなければいけない時点で、何か間違っているかもしれませんが。
それでは、記事の最後まで目を通していただきありがとうございました。RubyKaigiもお楽しみください。
-
証明はPumping lemmaを使うだけです。 ↩︎
Discussion