はじめに
こんにちは、Go界のコリン・ファースです。この記事はGo Advent Calendar 2014の21日目の記事です。昨日初サバゲーしたら、左手の薬指の爪のどまんなか含め、ピンポイントに左手の薬指3箇所を撃たれて、めっちゃ痛いです。
ところで今年のGo Advent Calendarではすでに2本の記事が正規表現に関する記事が上がっています。
- Go で Language Benchmark Game に挑戦して惨敗した - Qiita by @methane
- Go - Luceneで使われてるFSTを実装してみた（正規表現マッチ：VMアプローチへの招待） - Qiita by @ikawaha
@methane さんの記事の中では「Goの正規表現エンジンが遅い」という話が出ていました。また @ikawaha さんの記事では丁寧にVirtual Machine Approachな正規表現エンジンを実装する方法について書かれています。*1
本エントリでは実際にGoの正規表現エンジンはどういう実装になってるのかを簡単に触れて、そこで使われているVMを再利用してファジング用ツールを書いてみます。
TL;DR
Goの正規表現エンジン内で使っているバイトコードを利用して、ファジングなどで使えそうな正規表現パターンに合致するランダムな文字列を生成するツールを書いてみた。
Goでの正規表現エンジンの実装
Russ Coxによるアプローチ
Goのregexpパッケージの実装に大きくかかわっているRuss Coxは、Goのコアチームであり、RE2の実装をした本人です。そういった経緯からGoでの正規表現エンジンの実装もRE2で使われている手法と同様の、VMを使った実装になっています。すでに @ikawaha さんのエントリの中でも説明されていますが、雑に言えば有限オートマトンの状態をバイトコードの命令に落としこんでやるというものです。
詳しい話はRuss Coxの記事にボリューム満載に書いてあるのでぜひご一読されることをおすすめします。
- Regular Expression Matching Can Be Simple And Fast
- Regular Expression Matching: the Virtual Machine Approach
- Regular Expression Matching in the Wild
- 上記のアプローチがRE2内でどのように使われているかを説明した話。状況に応じてNFAやDFAを使い分けています。
- Regular Expression Matching with a Trigram Index
regexp
そもそもGoのregexpパッケージを使うときはどのようにしていたか、ここでおさらいしてみます。Goの正規表現パッケージでは次の2段階となっています。使用方法のサンプルはドキュメントにあるもので確認してください。
この順番で見ていけばどうなってるのか分かりそうなので中を細かく見て行きたいところですが、本題に入る前に長くなってしまうので割愛。後日Qiitaにまとめてみます。
1.の段階、つまりCompile()を実行すると、中ではregexp/syntaxパッケージのParse()が呼ばれ、syntax.Regexpのインスタンスが作成され、それがVMのバイトコードに変換されています。そのバイトコード全体がsyntax.Progです。
2.の段階で、実際にマッチングをはじめると、regexp.doExecute()内で1.で作成されたバイトコードを実行し始めます。このときに、生成されるのが @ikawaha さんのエントリにあったmachine構造体のインスタンスです。
ということで、まとめると、次の二段階がそのままパッケージに反映されていることがわかります。
今回は普段あまり触れられることがないであろう1のregexp/syntaxについて見てみます。
regexp/syntax
これは先に挙げたRuss Coxの2番目の記事の方法がそのまま反映された実装になっています。大きく分けて3つの構造体があります。
- Regexp（regexp.Regexpと同じ名前なので要注意。こちらはあくまでパターンをVMの実行形式に変換したまとまり）
- Prog（VMのバイトコード全体を保持する構造体）
- Inst（各命令を表す構造体）
さきほど、「regexp.Compile()でバイトコードにする」と書いていましたが、その内部ではsyntax.Regexp.Parse()メソッドを呼んで、さらにsyntax.Regexp.Simplify()メソッドを呼んでから実際のCompile()を行っています。このSimplify()によってPCREの複雑なパターンを次の4つだけを使った形式に変換しています。
- e1e2 （2つの状態が結合している）
- e1|e2 （2つの状態に分岐している）
- e1? （空またはe1の状態に分岐している）
- e1* （e1?と同様の分岐だがループしている）
イメージは先に挙げたRuss Coxの記事の"Converting Regular Expressions to NFAs"の節を読んでください。ためしに次のコードを実行してみましょう。
package main import ( "fmt" "regexp/syntax" ) func main() { pattern := `aa+bb*[c-z]{1,3}` exp, _ := syntax.Parse(pattern, syntax.Perl) fmt.Println(exp.Simplify()) }
結果は次の通り
aa+bb*[c-z](?:[c-z][c-z]?)?
このSimplifyしたパターンをバイトコードに変換するのがsyntax.Compile()です。実際にどのような形式になるのか、Compile()関数を呼んで、表示してみましょう。
package main import ( "fmt" "regexp/syntax" ) func main() { pattern := `aa+bb*[c-z]{1,3}` exp, _ := syntax.Parse(pattern, syntax.Perl) prog, _ := syntax.Compile(exp.Simplify()) fmt.Println(prog) }
次のように表示されました。
0 fail 1* rune1 "a" -> 2 2 rune1 "a" -> 3 3 alt -> 2, 4 4 rune1 "b" -> 6 5 rune1 "b" -> 6 6 alt -> 5, 7 7 rune "cz" -> 11 8 rune "cz" -> 10 9 rune "cz" -> 12 10 alt -> 9, 12 11 alt -> 8, 12 12 match
いかにもバイトコードらしい出力が得られました。各命令（状態）に関してはsyntax.InstOpに列挙されています。ドキュメントに各定数が何を表しているかの記載がないので、自分でざっとコード読んでみたり動かした感じだとこんなかんじです。（InstEmptyやInstEmptyMatchらへんはまだそうなるパターンを見てません）
- InstFail: 失敗状態
- InstMatch: 受領状態
- InstAlt: 分岐
- InstAltMatch: 分岐または受領
- InstRune1: 指定された1文字で遷移
- InstRune: 指定された範囲のなかから1文字で遷移
- InstCapture: 括弧の開始または終了
正規表現のマッチングではこのバイトコードを使って、入力された文字列を先頭から一文字ずつマッチしていくか見ていくわけですが、これを逆に使えば、正規表現のパターンに合致する文字列を生成することができそうです。
regexp/syntaxを使って正規表現パターンに合致する文字列を生成する
というわけで、実験的に作ってみました。
やっていることは非常に簡単で、正規表現のマッチングをするときに行うCompileまでは同じで、そこでできたバイトコードで、分岐が出たらランダムに遷移するというもの。InstRuneの場合は範囲の中から任意の文字をやはりランダムに出力しています。*2
試しに動かしてみます。
package main import ( "fmt" "regexp/syntax" fuzz "github.com/ymotongpoo/fuzzingo" ) func main() { generator, err := fuzz.NewGenerator("aa+bb*[c-z]{1,3}", syntax.Perl) if err != nil { panic(err) } for i := 0; i < 10; i++ { str, err := generator.Gen() if err != nil { fmt.Println(i, err) } else { fmt.Println(i, str) } } }
するとこういう結果が出力されます。
0 aabbbje 1 aabbbs 2 aaaaabbbbbr 3 aaabbbqye 4 aaaaabjh 5 aabbeqc 6 aabr 7 aabbho 8 aaaaabbblo 9 aabesh
パターンに対して正しい結果が出力されていますね！いまは非常に乱暴な実装をしていますが、もうちょっとちゃんと実装したらそこそこ使えるツールになるんじゃないでしょうか。
次は @hogedigo さんです。
