2016年3月3日

私がどのようにしてAtomの奇妙なバグを修正したか : 正規表現が暴走を起こすとき

Atomは、今注目の最新テキストエディタです。私は、このエディタをソフトウェア開発に使用しているのですが、オープンソースになっているので、少しでも貢献できればとAtomが抱えるIssuesについて検証してみることにしました。私は、ある奇妙なバグを見つけました。それは、Atomのユーザspeterがテキストを1行書き、行末でEnterを押した時に起こりました。新たな行が書けるようになるまで、Atomは30分も計算していたのです。私は、そんな単純かつよくあるオペレーションもろくにできないことに大きな衝撃を受け、早速その原因を探ることにしました。

検索

これが、問題のテキストです。

vVar.Type().Name() == "" && vVar.Kind() == reflect.Ptr && vVar.Type().Elem().Name() == "" && vVar.Type().Elem().Kind() == reflect.Slice

これは、Googleが作った新しいプログラミング言語であるGoで書かれたコードです。これで何が起こるのかよく分かりませんが、問題はコードの内容ではありません。私の関心は、行末でEnterを押すと、なぜAtomが固まってしまうのかという点だけです。

すぐにコードベース全体に対して”newline”という語の検索を始めました。原因に結び付かないものがいくつかあった後、Enterが押されると新しい行に移行する関数を見つけました。text-editor.coffeeというファイルに入っているinsertNewlineと呼ばれる関数です。これがその内容です。

insertNewline: -> 
  @insertText('\n')

Atomは、CoffeeScriptで書かれています。CoffeeScriptは、キーワードや丸括弧、角括弧がほとんどないJavascriptのようなものです。Pythonのようにスコープを定義するためにスペースを使い、クラスもサポートしています。上記2行は、insertNewlineと呼ばれるTextEditorクラスのメソッドの1つを定義しています。insertNewlineは、改行文字に関するクラスメソッドinsertTextを呼び出すだけです。私の考えが正しいことを確認するために、このメソッドにちょっとした微調整をしました。

insertNewline: ->
  console.log "Hello!"
  @insertText('\n')
  console.log "Goodbye"

この変更によって、EnterとタイプするたびにHello!とGoodbyeがAtomのコンソールに現れるのが見えます。しかし、遅いGoのコードの最後にEnterとタイプすると、Hello!は確認できましたが、Goodbyeは表示されませんでした。その理由は、プログラムが、insertTextで固まってしまって、console.log "Goodbye"の行にたどりつけないからです。これを見て、insertTextメソッドの中に動きを遅くしている原因があると分かりました。

そこで、TextEditorのinsertTextメソッドを確認しました。TextEditorは、選択中のテキストを記録するSelectionと呼ばれるオブジェクトを保持しており、TextEditorのinsertTextメソッドは、単にこのSelectionのinsertTextメソッドを呼び出します。（Atomは、実際複数選択をサポートしていて、Selectionオブジェクトがいくつあっても大丈夫ですが、私の事例では1つだけでした）。

Selection.insertTextは、非常に長いメソッドですが、Hello/Goodbyeロギングを使って、最終的にこれらの行で起こる問題を突き止めました。

if options.autoIndentNewline and text is '\n'
  @editor.autoIndentBufferRow(newBufferRange.end.row, preserveLeadingWhitespace: true, skipBlankLines: false)

新しい行を書くと、このコードは新しい行のインデントを決定するためにTextEditorにコールバックします。Atomは、新しい行のインデントをスコープに基づいて計算します。もし新しい行が前の行と全く同じスコープであれば、同じインデントということになります。新しいスコープを入力すると、タブ1つ分多くインデントされ、スコープを終了すると、1つ分少ないインデントになります。

TextEditorは、編集されているファイルに使われているプログラミング言語を管理するLanguageModeと呼ばれるオブジェクトを持っています。LanguageModeは、各言語のスコープの開始と終了の仕組みを知っているので、TextEditorのautoIndentBufferRowメソッドが、LanguageModeのautoIndentBufferRowメソッドを呼び出すのです。

LanguageModeのautoIndentBufferRowメソッドは、インデントレベルを計測するために、LanguageModeの長ったらしい名前のsuggestedIndentForTokenizedLineAtBufferRowメソッドを呼び出します。Hello/Goodbyeのロギングは、これが遅延の原因だと教えてくれていました。以下は、suggestedIndentForTokenizedLineAtBufferRowをスリム化したものです。

suggestedIndentForTokenizedLineAtBufferRow: (bufferRow, line, tokenizedLine, options) ->
  iterator = tokenizedLine.getTokenIterator()
  iterator.next()
  scopeDescriptor = new ScopeDescriptor(scopes: iterator.getScopes())

  increaseIndentRegex = @increaseIndentRegexForScopeDescriptor(scopeDescriptor)
  decreaseNextIndentRegex = @decreaseNextIndentRegexForScopeDescriptor(scopeDescriptor)

  precedingRow = bufferRow - 1
  desiredIndentLevel = @editor.indentationForBufferRow(precedingRow)

  unless @editor.isBufferRowCommented(precedingRow)
    precedingLine = @buffer.lineForRow(precedingRow)
    desiredIndentLevel += 1 if increaseIndentRegex?.testSync(precedingLine)
    desiredIndentLevel -= 1 if decreaseNextIndentRegex?.testSync(precedingLine)

  Math.max(desiredIndentLevel, 0)

まず、現在の行のスコープ情報をカプセル化しているScopeDescriptorというオブジェクトを構築します。このScopeDescriptorに基づいて、正規表現のincreaseIndentRegexとdecreaseNextIndentRegexを取得します。increaseIndentRegexは、スコープを開始しようとしている行にマッチし、decreaseNextIndentRegexは、スコープが終了している行にマッチします。つまり、新しい行が新しいスコープを開始しようとしたとき、increaseIndentRegex?.testSync(precedingLine)は真になるので、desiredIndentLevelがインクリメントされます。新しい行がスコープを終了するときは、decreaseNextIndentRegex?.testSync(precedingLine)が真になるので、desiredIndentLevelがデクリメントされます。最後に、Hello/Goodbyeは、decreaseNextIndentRegex?.testSync(precedingLine)がパフォーマンス障害を引き起こす最大の要因だと教えてくれました。

正規表現

decreaseNextIndentRegexは、正規表現です。正規表現はパターンを定義するもので、そのtestメソッドは文字列の引数を取り、文字列がパターンにマッチしているかを教えてくれます。正規表現の構文は少し不安定ですが、非常に強力です。

肩慣らしに、簡単な例を挙げましょう。

^[b]+

この正規表現は、”bananas（バナナ）”のようにbで始まる文字列にマッチします。細かく見ていきましょう。最初の^は”文字列の1文字目”を意味します。^がないと、正規表現は”abacus”(そろばん)といったように、位置に関係なくbが含まれる文字列にマッチしてしまいます。次に[b]は、bの文字を探し、最後の+は、”最低1つ”を意味します。つまり、この正規表現は”bananas”や”bbbananas”といったように、含まれる数に関係なくbで始まる文字列にマッチしますが、”abacus”といったようにbで始まらない文字列にはマッチしません。

decreaseNextIndentRegexの目的は、(よりも)が多くある、不平衡な括弧が含まれる行にマッチすることです。以下はその例です。

someObject.someFunction(arg1,
  arg2,
  arg3) // <--- この行は"("よりも")"が多くあるのでdecreaseNextIndentRegexにマッチします

このように、1行に対して1つの引数を書くスタイルは、かなり一般的です。arg1などと違い、引数の名前が長い場合は特にです。arg2やarg3)の行がインデントされているのは、この行が引数のリストの一部であることを明確にするためです。arg3)は閉じ括弧を持ち、不平衡です。つまり、decreaseNextIndentRegexにマッチするということです。この行の最後でEnterを押せば、Atomは新しい行をsomeObject.someFunction(arg1,と同じラインにインデントするでしょう。

decreaseNextIndentRegexを使用する準備はできましたか？　いえ、まだ誰もdecreaseNextIndentRegexを使える段階ではありません。でも深呼吸をしてください。私はこんなものを見つけました。

^\s*[^\s()}]+(?<m>[^()]*\((?:\g<m>|[^()]*)\)[^()]*)*[^()]*\)[,]?$

正直に言いましょう。この何だか訳の分からないコードを見たとき、もう止めようと思いました。しかし、ここまでやってこれたんだから、これも何とかなると考えたんです。では、分かりやすいところで区切って少しずつ見ていきましょう。

^\s*

「^は文字列の1文字目を意味する」と先程説明しました。\sは、スペースを意味し、タブ文字とスペースにマッチします。*は”最低でもゼロ個”の意味になります。つまり、これはarg3の行の最初にある2つのスペースのように、文字列の最初にある全てのスペースにマッチします。

    [^\s()}]+

[^がありますが、これは”どの文字でもない”を意味します。つまり、[^\s()}]は、スペースではない、もしくは(や)、}でもない文字を探します。+は、先程と同じく”最低1つ”の意味です。結果として、これは上の例にあるarg3にマッチします。

             (?<m>[^()]*\((?:\g<m>|[^()]*)\)[^()]*)*

引き締めて行きましょう。もし、最後の引数がarg3)といった単純なものではなく、関数の評価結果や関数だった場合はどうでしょう？例えば以下のように。

someObject.someFunction(arg1,
  arg2,
  f1(f2(xyz), abc).def) // <--- ) のほうが ( より多いので、まだdecreaseNextIndentRegexにマッチ

大きな塊であるdecreaseNextIndentRegexの目的は、ネストの深さを問わずf1(f2(xyz), abc),などの関数呼び出しにマッチさせることです。では、これをもっと細かく見て行きましょう。

             (?<m>

これは、名前付きキャプチャグループ<m>を定義します。<m>はdecreaseNextIndentRegexの塊全体の名前で、あらゆる深さの関数呼び出しにマッチしようとします。

                  [^()]*

[^()]*は、任意の個数の、括弧ではない文字にマッチします。上の例ではf1です。

\(

これは、f1の後ろにあるような(にマッチします。(は関数呼び出しを意味するので、関数の引数のように見える文字列にマッチさせなくてはなりません。

                          (?:\g<m>|[^()]*)

関数の引数はf2に対する引数xyzのような、単純な文字のリスト、またはf1に対する引数f2(xyz)のように、関数呼び出しそのものです。xyzのような単純な文字のリストの場合は、もう1つの[^()]*で機能しますが、<m>はどのように関数呼び出しにマッチするのでしょうか？　それに、この関数呼び出しは、引数として別の関数呼び出しを持っているかもしれません。この場合に使う表現は、深層部に対する関数呼び出しにマッチする必要があります。しかし、深層部に対する関数呼び出しにマッチする表現はありましたよね。そうです、<m>です！

これが、(?:\g<m>|[^()]*)を関数の引数にマッチさせる方法です。|は選択子で、”左もしくは右にあるものどちらか”という意味を持ちます。|の左側は\g<m>で、関数に対する引数が関数呼び出しである場合の<m>に対する再帰的な参照です。|の右側は、引数が単純な文字列である場合の[^()]*です。少しは理解してもらえたら幸いです。私は全てを理解するまでに、かなり長い時間考え込みました。

\)

これは、引数のリストを閉じることを意味する)にマッチします。

                                            [^()]*

<m>の説明の最後は、f1のように、1つは関数呼び出しで、もう1つが文字列といった、複数の引数を持つ関数の場合です。(?:\g<m>|[^()]*)は、関数呼び出しの引数であるf2(xyz),にマッチし、追加の[^()]*は文字列abcにマッチします。

<m>については以上です。ここまでくれば後は楽勝です。

                                                    [^()]*

<m>の後ろには、別の[^()]*があります。これは、<m>がマッチした関数呼び出しと行の最後の間に表示される文字にマッチします。例では、[^()]*は.defにマッチします。

                                                          \)[,]?$

decreaseNextIndentRegexの塊の最後は、もう1つの\)で始まります。この余分な)は、行を挿入句的に不平衡にします。覚えていますか？　decreaseNextIndentRegexの目的は、(よりも)が多い行を見つけることでしたよね？　次に、[,]?はゼロもしくは1つのカンマにマッチし、$は文字列の最後にマッチします。)を不平衡にした後に、decreaseNextIndentRegexにマッチするために許可された文字列内の唯一の文字は、オプショナルのカンマです。

ふぅ～。decreaseNextIndentRegexをやり遂げました。頑張りましたね！

大惨事の襲来

ここまでやってきたのには理由があります。それは、vVar.Type().Name() == "" && vVar.Kind() == reflect.Ptr && vVar.Type().Elem().Name() == "" && vVar.Type().Elem().Kind() == reflect.Sliceにマッチさせるのが恐ろしく遅いという、decreaseNextIndentRegexの何かが問題だったからですよね。私には原因が全く分からないので、Googleで”正規表現のパフォーマンス”と検索してみました。行き着いた先は、https://regex101.com/という、とても素晴らしいサイトで、正規表現を直接入力して文字列をテストすることができるのです。また、マッチングプロセスを細分化して説明してくれています。decreaseNextIndentRegexと文字列を入力してみたら、Catastrophic backtracking detected（壊滅的なバックトラッキングが検出されました）と返ってきました。これは良くないですね。

regex101.comは、壊滅的なバックトラッキング現象について、詳細な説明をしてくれました。ここでは今回の例の原因について深く言及するつもりはありませんが、*演算子の取り扱いがぞんざいな正規表現を悩ます問題です。基本的には、「*演算子を内部に持つ文字列自体に対して*を用いたことにより、ネストされて*を使われた表現の両方が同じ文字列にマッチしてしまう」ということにより起こります。このケースでは、「正規表現全体にはマッチしないが、*を用いた部分式2つにはともにマッチする文字列」を特定するコストが、文字列の長さに対して指数関数的になります。

簡単な例を挙げましょう。正規表現である([a]*[ab]*)*cは、aaaaaaaaaaaaaaaaaaのような文字列を与えた場合、壊滅的なバックトラッキングに出くわすでしょう。というのも[a]*あるいは[ab]*のどちらかが、aの1つ1つにマッチしてしまうからです。

それでは、壊滅的なバックトラッキングが、どのようにdecreaseNextIndentRegexに影響を及ぼすかを見ていきましょう。問題を簡略化するため、壊滅的なバックトラッキングを引き起こした最小の設定を見つけるまで、かなりの量のdecreaseNextIndentRegexを取り除きました。

^([^()]*\(\)[^()]*)*\)$

これは、<m>のうち、\(と\(の間から(?:\g<m>|[^()]*)を引き、不平衡さのために別の\(を加えたものです。この最小限の問題表現で、壊滅的なバックトラッキングが起こることが分かりました。2つの[^()]*を含むパターンで*を使っています。[^()]と[^()]は、全く同じ表現なので、同じ文字列にマッチし、*付きの表現の*付き部分式であることから、壊滅的なバックトラッキングを引き起こします。この2つの間は()なので、たくさんの()を持つ文字列では、vvVar.Type().Name()…の文字列で見られたように、壊滅的なバックトラッキングにぶつかるだけです。

修正

壊滅的なバックトラッキングを避けるために、<m>を成す[^()]*のうちの1つを取る必要がありましたが、decreaseNextIndentRegexがマッチする、もともとの文字列を変更することなく、取り出すことはできませんでした。これは好ましいことではありません。なぜ、2つめの[^()]*がここにあるのか思い出してください。関数が複数の引数(1つは関数呼び出しで、もう1つは文字列)を持つ場合を網羅するためです。関数呼び出しの引数の後に書かれた文字列にマッチさせるためにこの表現があるのです。しかし、現在の位置では、全ての関数呼び出しの後のテキストに適用されます。<m>の外側の[^()]*がトップレベルの関数呼び出しの後に続くテキストを扱っているので、必要なのは、それ自体が関数の引数である関数呼び出しを行うテキストのチェックだけです。

<m>の再帰的な参照で、入れ子された関数の呼び出しを見つけました。そこで、2つめの[^()]*がネストされた関数の呼び出しのみに適用されるよう、\g<m>のすぐ後に動かしました。移動させた[^()]*は必要のあるテキストとマッチするかどうか試そうとしますが、すでに別の[^()]*がカバーしているテキストとのマッチを試行することはありません。冗長性を取り除いたので、壊滅的なトラッキングはもはや起こりません。最終的なdecreaseNextIndentRegexは次のようになりました。

^\s*[^\s()}]+(?<m>[^()]*\((?:\g<m>[^()]*|[^()]*)\))*[^()]*\)[,]?$

この変更といくつかの追加のテストをプルリクエストとまとめ、プッシュしました。このプロジェクト協力者のsvanharmelenは、私の評価と修正に同意してくれました。私のコミットは、間もなく実行されるでしょう。このように、Atomの修正が終わりました！

この修正は間違いなく、私が今までオープンソースの世界でやってきた中で、最も骨の折れる取り組みでした。当初はCofeeScriptを見たことが全くありませんでしたし、数年前、バークレーのCS 164で2週間ほど正規表現を学びましたが、うろ覚え程度しか頭に残っていませんでした。最終的には、これでもかという量のCofeeScriptの行を読むことになり、存在を知っていた以上の正規表現を学ぶことができました。何より、自分のお気に入りのテキストエディタの奇妙バグを修正できたのです。とてもいい経験になりました！