POSTD PRODUCED BY NIJIBOX

POSTD PRODUCED BY NIJIBOX

ニジボックスが運営する
エンジニアに向けた
キュレーションメディア

2016年3月3日

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

Dave Galbraith
How I fixed Atom

(2016-01-28)by Dave Galbraith

本記事は、原著者の許諾のもとに翻訳・掲載しております。

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の行を読むことになり、存在を知っていた以上の正規表現を学ぶことができました。何より、自分のお気に入りのテキストエディタの奇妙バグを修正できたのです。とてもいい経験になりました！