Rubyの正規表現内の部分式呼び出し再帰による無限ループ

はじめに

Rubyのリファレンスを読んでいたら、以下のような記述が目に入りました

ただし、再帰的な正規表現を書く場合は、無限ループに陥る可能性があるため、停止条件に注意してこの機能を使ってください。

こういうことを言われると無限ループを引き起こしたくなるので、実際にやってみました。

正規表現についてあまり詳しくないため、誤り等があったらご指摘をお願いします。

一般的な正規表現には、Catastrophic Backtracking Regexpと呼ばれる、計算量が指数的に増加してしまうものがある。(今回の主題とは異なる)

一番単純な例を以下に示す。

/(.*)*^/

この正規表現の計算量は、文字列の長さをnとして、O(2^n)で表されるらしい。(参考)
実際に手元で実行してみたところ、

"1234567890abcdefg".match /(.*)*^/

程度までが限界であり、これ以上は現実的な時間では結果が返って来なくなった。

このように、一般的な正規表現の仕様として、計算量が爆発する例があるらしい。

Rubyの正規表現は、一般的な正規表現を拡張している。
その一つが部分式呼び出しと呼ばれる仕様で、リファレンスにも無限ループの可能性が示唆されている。

部分式呼び出しを用いた無限ループの正規表現を、実際に作ってみたのがこちら。

/(?<hoge>\g<hoge>)/

単純な表現だが、これを実行すると、SyntaxError: never ending recursion: /(?<hoge>\g<hoge>)/) という例外が投げられる。
簡単にこの正規表現を説明すると、

(?<hoge>\fuga) で、fugaの意味する正規表現にhogeという名前をつける。
上のfugaに相当する部分で、hogeという名前をつけた正規表現を\g<hoge>で呼び出している。

これだけである。メソッドとのアナロジーで考えると、

def hoge
  hoge
end

という、停止条件を明示していない再帰呼び出しメソッドに例えられる。

正規表現については普通に使う程度の知識しかなかったのですが、この記事を書くために少し調べただけで、かなり面白そうなトピックが色々見つかりました。
今まさに正規表現の本をポチってしまったので、勉強していこうと思います。

f:id:betit0919:20190901134101p:plain