ちょっとしたことがGroovy「あっという間に死んでしまう正規表現を検証する」

注意！ 以下のコードには、JVMを暴走させる恐れのあるコードが含まれています。

まず、このコード。
対象の文字列が長くなると、その実行時間は爆発的に増えます。

hangup_regex.groovy

@Grab(group='org.spockframework', module='spock-core', version='0.7-groovy-2.0')

import spock.lang.*
import java.util.regex.Matcher
import java.util.regex.Pattern

class SlowRegexTest extends Specification {

  def stopWatch = {c->
    def s = System.nanoTime()
    c()
    def w = System.nanoTime() - s
    if(w <      1000000)
        "${w /  1000} [microsec]"
    else if(w < 1000000000)
        "${w /  1000000} [millsec]"
    else
        "${w /  1000000000} [sec]"
  }
  
  def p = Pattern.compile(/(([0-9a-zA-Z]+[\s.]*)+)$/)
  def trim = { name ->  
    def matcher = p.matcher(name)
    println stopWatch { matcher.find() }
    println matcher.start()
    name.substring(0, matcher.start())
  }
  
  @Timeout(10)
  def '末尾のトリムに10秒以上かからないか'(){
    expect:
    trim(target) == result
    
    where:
        target                                                |    result
    "******${"A"* 1}BC  DEF  GHI  JKL  MNO  PQR  STU_  VWX."  | "******${"A"* 1}BC  DEF  GHI  JKL  MNO  PQR  STU_  "
    "******${"A"* 3}BC  DEF  GHI  JKL  MNO  PQR  STU_  VWX."  | "******${"A"* 3}BC  DEF  GHI  JKL  MNO  PQR  STU_  "
    "******${"A"* 5}BC  DEF  GHI  JKL  MNO  PQR  STU_  VWX."  | "******${"A"* 5}BC  DEF  GHI  JKL  MNO  PQR  STU_  "
    "******${"A"* 7}BC  DEF  GHI  JKL  MNO  PQR  STU_  VWX."  | "******${"A"* 7}BC  DEF  GHI  JKL  MNO  PQR  STU_  "
    "******${"A"* 9}BC  DEF  GHI  JKL  MNO  PQR  STU_  VWX."  | "******${"A"* 9}BC  DEF  GHI  JKL  MNO  PQR  STU_  "
    "******${"A"*11}BC  DEF  GHI  JKL  MNO  PQR  STU_  VWX."  | "******${"A"*11}BC  DEF  GHI  JKL  MNO  PQR  STU_  "
  }
}

この原因も、前に言った通り翻って検索してしまうのが原因です。
ただ、この程度で暴走状態にまでなってしまうのは何かしらJavaの正規表現エンジンの実装には問題がありそうですね。。。

この正規表現を修正するには次のようにします。

no_hungup.groovy

  def p = Pattern.compile(/(([0-9a-zA-Z]++[\s.]*)+)$/)

違いは、英数字のグループの連続を探す+が++になっていること。

++はJavaの正規表現では貪欲マッチを行います。

貪欲マッチは、後ろに続くパターンが出現しようがしまいがマッチを続ける性質があります。
そのため、

greedy.groovy

assert  ('abcd' ==~ /.+d/)
assert !('abcd' ==~ /.++d/)

のようになります。
後者ではdは、すでに.++に含まれてしまっているため評価はfalseとなるのです。

貪欲マッチでは後ろに続く表現を検索しないため、条件によっては正規表現を非常に高速化させることができます。

今回例示したケースでは、英数字パターンと、後に続くパターンが被らないためこのように修正することができました。

ちなみに、一般的に

(パターン+)+

という正規表現は遅いです。すぐ死にます。