俺の正規表現は長い

この記事は株式会社ACCESS Advent Calendar 2019の7日目の記事です。が、内容は個人的なものです。

まえがき

皆さん正規表現は好きですか？僕は嫌いです。

そんなある日、「7の倍数」を表す正規表現 という記事を見つけました。
ちょっと分かりづらかったですが、「7の倍数」という言語を受理するDFAを作り、そこから機械的に正規表現を作っていったわけですね。

DFA -> 正規表現 の変換は StackExchange のこの質問ページの図で分かりやすく表現されています。

しかし、なんとこの正規表現、期待通りに動いてくれません。Chrome DevTool で (問題の正規表現).test('7') を評価すると false になってしまいました。

正規表現自体は正しいはずなのに。

僕がいつも使ってる Elixir くんならうまくやってくれるはず…

$ iex
Erlang/OTP 20 [erts-9.3.3.3] [source] [64-bit] [smp:4:4] [ds:4:4:10] [async-threads:10] [hipe] [kernel-poll:false]

Interactive Elixir (1.9.4) - press Ctrl+C to exit (type h() ENTER for help)
iex(1)> ~R/\A((...中略...))+\z/ \
...(1)> |> Regex.match?("7")
** (Regex.CompileError) regular expression is too large at position 19647
    (elixir) lib/regex.ex:209: Regex.compile!/2
    (elixir) expanding macro: Kernel.sigil_R/2
    iex:1: (file)
    (elixir) expanding macro: Kernel.|>/2
    iex:1: (file)

regular expression is too large と悲鳴を上げて死んでしまいました。

JavaScriptでダメだったのも実は正規表現が長すぎたためかもしれません。

こうなると悪戯心に火が付きます。

正規表現の長さの限界は？

僕の検索力が足りず、明確にいくつみたいなのが書いてあるドキュメントが見つかりませんでした。
(Elixir -> Erlang の re -> PCRE という依存までは見えましたがPCREでの制限がどうなってるのかよく分からず…)

なのでテキトーに二分探索してみます。結果は環境に依存する可能性があります。

JavaScript

const testN = (n) => {
  const source = Array(n).fill('a').join``;
  try {
    return new RegExp(source).test(source);
  } catch(_) {
    return false;
  }
};

testN(50000);
// false

const tryAndContinue = (previousN, currentN) => {
  const diff = Math.abs(currentN - previousN);
  if (diff <= 1) {
    return [previousN, currentN];
  }
  const nextN = currentN + (testN(currentN) ? 1 : -1) * (diff >> 1);
  return () => tryAndContinue(currentN, nextN);
}

let continuation = tryAndContinue(50000, 25000);

while(typeof continuation === 'function') {
  continuation = continuation();
}

continuation
// (2) [32765, 32766]

testN(32766);
// true
testN(32767);
// true
testN(32768);
// false

a を 32768個並べるだけでアウト、ということが分かりました。

Elixir

test_n = fn n ->
  source = String.duplicate("a", n)
  case Regex.compile(source) do
    {:ok, regex} -> Regex.match?(regex, source)
    _            -> false
  end
end

Stream.unfold({50000, 25000}, fn {previous_n, current_n} ->
  diff = abs(current_n - previous_n)
  cond do
    diff <= 1 ->
      nil
    test_n.(current_n) ->
      next_n = current_n + div(diff, 2)
      {next_n, {current_n, next_n}}
    :else ->
      next_n = current_n - div(diff, 2)
      {next_n, {current_n, next_n}}
  end
end) \
|> Enum.take(-3)
# => [32768, 32765, 32764]

test_n.(32764)
# => true

こちらは a を 32765個並べるとアウト。JavaScriptに近いですがちょっとだけ違いがありますね。

もっと短く壊す

((((((((((a)))))))))) みたいな感じで () を多用したりして複雑にすると上限がもっと短くなります。
最初の正規表現は () だけでなく | や [、 *、+ も使っているのでダメだった感じですね。

追記: Elixirだと ~R/(){8192}/ が知る限り最短でこのエラーを出せるようでした。

みなさんもぜひお気に入りの言語で試してみてください。

---

QAの人に前後を挟まれたためか、奇しくも「コーナーケースのテスト」みたいな話になりました。明日の記事は @illypong さんが数多のバグをワンパンしてくれそうな雰囲気です。お楽しみに！