Upgrade to Pro — share decks privately, control downloads, hide ads and more …

正規表現のテストカバレッジを測りたかった話

 正規表現のテストカバレッジを測りたかった話

※社内LT用につくったもの

yubessy

May 29, 2017
Tweet

More Decks by yubessy

Other Decks in Programming

Transcript

  1. Golang の正規表現エンジン NFA( 非決定性有限オー トマン) ベー ス アルゴリズムが理解しやすい 計算量が文字数に対して線形 平均的には遅い

    Pure Go で実装 自分でも読める コー ド量が手頃( エンジン部分は数100 行) https://github.com/golang/go/tree/master/src/regexp
  2. Golang の正規表現エンジン re := regexp.MustCompile("/[a-z]+\.(co|ne)\.jp/") re.MatchString("hoge.co.jp") 内部では 1. 正規表現の構文木を作成 (

    syntax/parse.go ) 2. 構文木からプログラムを作成 ( syntax/compile.go ) 3. 文字列を入力としてプログラムを実行 ( exec.go )
  3. 正規表現プログラムの内部表現 プログラム = 文字を1コずつ処理する命令の列 syntax/prog.go type Prog struct { Inst

    []Inst ... } type Inst struct { Op InstOp // 命令の種類 Out uint32 // 成功時のジャンプ先の命令番号 Arg uint32 // 失敗時のジャンプ先の命令番号( など) Rune []rune // マッチする文字( 文字マッチ命令のみ) }
  4. プログラムの内部表現 0: InstFail 0 0 [] // 失敗( 最初はスキップ) 1:

    InstRune 2 0 ['a', 'z'] // 'a' - 'z' 2: InstAlt 1 3 [] // 命令1, 3 のいずれか 3: InstRune1 4 0 ['.'] // '.' 4: InstCapture 9 2 [] // グルー ピング開始 5: InstRune1 6 0 ['c'] // 'c' 6: InstRune1 10 0 ['o'] // 'o' 7: InstRune1 8 0 ['n'] // 'n' 8: InstRune1 10 0 ['e'] // 'e' 9: InstAlt 5 7 [] // 命令5, 7 のいずれか 10: InstCapture 11 3 [] // グルー ピング終了 11: InstRune1 12 0 ['.'] // '.' 12: InstRune1 13 0 ['j'] // 'j' 13: InstRune1 14 0 ['p'] // 'p' 14: InstMatch 0 0 [] // 成功
  5. カバレッジの計算 マッチの実行時に通った命令をマー キングしておく // 文字マッチ命令を1 つ実行する関数 (exec.go) func (m *machine)

    step(...) { ... switch i.Op { ... case syntax.InstRune: add = i.MatchRune(c) case syntax.InstRune1: add = c == i.Rune[0] ... if add { i.Flag = true // マッチが成功したらフラグを立てる } ... }
  6. カバレッジの計算 テストケー スを食わせてフラグの立った命令を数える func (re *Regexp) Coverage() (int, int) {

    s, a := 0, 0 for _, x := range re.prog.Inst { if x.Op == syntax.InstRune || ... { a++ if x.Flag { s++ } } } return s, a }
  7. カバレッジの計算 できた!!! func main() { re := regexp.MustCompile(`[a-z]+\.(co|ne)\.jp`) re.MatchString("hoge.co.jp") c,

    a := re.Coverage() fmt.Printf("%d / %d", c, a) } 7 / 9 ※ 文字マッチ命令の 成功 / 全部 を数えた場合