ScalaのRegexParsersで書いたパーサのチューニング方法 #1

注記: 各テストで、[ScalaのRegexParsersがすごく遅くなる件の原因と対策 - Qiita](http://qiita.com/rubyu/items/2832c1967a71ab83a4d4)の対策を施したCharSequenceをParserに与えています。

---

## CSVパーサを書きます。

まず素直に定義してみます。

```Parser.scala
import util.parsing.combinator.RegexParsers

trait Parser extends RegexParsers {
  override val skipWhitespace = false

  lazy val line          : Parser[Result.Element] = ls  ^^^ Result.Row(Nil) | row <~ ls
  lazy val lastLine      : Parser[Result.Element] = eof ^^^ Result.Row(Nil) | row <~ eof | invalidString
  lazy val row           : Parser[Result.Element] = repsep( field, fs ) ^^ { Result.Row(_) }
  lazy val invalidString : Parser[Result.Element] = """.+""".r ^^ { Result.InvalidString(_) }

  def field : Parser[String]
  def fs    : Parser[String]
  def ls    : Parser[String]
  val eof   : Parser[String] = """\z""".r
}
```

```Parser1.scala
class Parser1 extends Parser {

  lazy val fs : Parser[String] = "\t"
  lazy val ls : Parser[String] = "(\r\n|\r|\n)".r

  //長さ0以上の文字列。
  lazy val field             = quoted_field | raw_value

  //QUOTEに囲まれていること。前後にスペースによるパディングが存在してもよい。
  lazy val quoted_field      = padding ~> quote ~> quoted_value <~ quote <~ padding

  //QUOTE以外の文字, エスケープされたQUOTEからなる長さ0以上の文字列。
  lazy val quoted_value      = rep( escaped_quote | not_quote | ls | fs ) ^^ { _.mkString }

  //QUOTE, fs, ls以外から開始し、fs, ls以外が後続する、長さ0以上の文字列。
  lazy val raw_value         = ( not_quote_and_fs ~ rep( not_fs )).? ^^ { case Some(head ~ tail) => head :: tail mkString; case None => "" }

  lazy val padding           = rep( space )
  lazy val escaped_quote     = quote ~ quote ^^^ quote
  lazy val not_quote         = not( quote ) ~> char
  lazy val not_fs            = not( fs ) ~> char
  lazy val not_quote_and_fs  = not( guard(quote) | fs ) ~> char

  lazy val char            = ".".r
  lazy val space           = ' '
  lazy val quote           = '"'
}
```

1文字1文字をParserがチェックしてていて、想像がつくとおり、すごく遅いです。

```bat
> sbt "run Reader3WithParser1 test2.tsv"
total row: 12000
total field: 36000
total char: 47448571
total sec: 39.3310
row (per/sec): 305.1028
field (per/sec): 915.3085
char (per/sec): 1206391.1250
```

![874ea2d7645b7a61d572cf377dba9926.png](https://qiita-image-store.s3.amazonaws.com/0/47014/d4186826-9259-69db-9c4a-6b8e9c7b62a9.png)

## パフォーマンスを改善するためには、
なるべくParserが文字列をチェックする回数を減らすことが重要です。つまり、正規表現で表現可能できる部分をなるべくRegexで定義してしまいます。

```Parser2.scala

class Parser2 extends Parser {

  lazy val fs : Parser[String] = "\t"
  lazy val ls : Parser[String] = "(\r\n|\r|\n)".r

  //長さ0以上の文字列。
  lazy val field        : Parser[String] = quoted_field | raw_value

  //QUOTEに囲まれていること。前後にスペースによるパディングが存在してもよい。
  lazy val quoted_field : Parser[String] = " *\"".r ~> quoted_value <~ "\" *".r

  //QUOTE以外の文字, エスケープされたQUOTEからなる長さ0以上の文字列。
  lazy val quoted_value : Parser[String] = rep( "\"\"" ^^^ "\"" | "[^\"]+".r ) ^^ { _.mkString }

  //QUOTE, fs, ls以外から開始し、fs, ls以外が後続する、長さ0以上の文字列。
  lazy val raw_value    : Parser[String] = "([^\t\"\r\n][^\t\r\n]*)?".r
}
```

```bat
> sbt "run Reader3WithParser2 test2.tsv"
total row: 12000
total field: 36000
total char: 47448571
total sec: 3.3910
row (per/sec): 3538.7791
field (per/sec): 10616.3369
char (per/sec): 13992501.0000
```

![4a041a322599451f674bd11761ba3d82.png](https://qiita-image-store.s3.amazonaws.com/0/47014/5195f45f-9bef-6f14-fd81-64645f070f23.png)

いきなり爆速になりました。CSVはルールが単純で、raw_value, quoted_valueをシンプルに記述できたことが効きました。

VS [OrangeSignal CSV](https://github.com/orangesignal/orangesignal-csv) で 17% 高速です!!

```bat
> sbt "run OrangeSignal test2.tsv"
total row: 12001
total field: 36001
total char: 47448571
total sec: 3.9770
row (per/sec): 3017.6013
field (per/sec): 9052.3008
char (per/sec): 11930745.0000
```

![d84cd129dae7b361b440ac09920ff83b.png](https://qiita-image-store.s3.amazonaws.com/0/47014/6257b676-d584-9e9d-f3e9-49e6b1002760.png)

## Parserを定義するRegexをハードコードしてしまうと、
可読性や柔軟性がかなり損なわれますが、後者については正規表現を使いこなすことでなんとかなることが多いです。
例えばここのCSVパーサの例において、任意のパターンをフィールドや行の区切りとして与えることは、正規表現のNegative Lookaheadを使えば可能です。

```Parser3.scala
class Parser3 extends Parser {

  val LS = "(\r\n|\r|\n)"
  val FS = "\t"

  val ls : Parser[String] = new Regex(LS)
  val fs : Parser[String] = new Regex(FS)

  //長さ0以上の文字列。
  lazy val field        : Parser[String] = quoted_field | raw_field

  //QUOTEに囲まれていること。前後にスペースによるパディングが存在してもよい。
  lazy val quoted_field : Parser[String] = " *\"".r ~> quoted_value <~ "\" *".r

  //QUOTE以外の文字, エスケープされたQUOTEからなる長さ0以上の文字列。
  lazy val quoted_value : Parser[String] = rep( "\"\"" ^^^ "\"" | """[^"]+""".r ) ^^ { _.mkString }

  //QUOTE, fs, ls以外から開始し、fs, ls以外が後続する、長さ0以上の文字列。
  lazy val raw_field    : Parser[String] = s"""(((?!$FS)(?!$LS)[^"])((?!$FS)(?!$LS).)*)?""".r
}
```

ここで注意しなければいけないことは、先読み否定の`((?!ab)(?!b).)+`は、`ab`と`ｂ`にはマッチしますが、`a`にはマッチしないことです。Parser3.LSの定義が`(\r\n|\r|\n)`になっているのはそのためで、もしこれが`(\r\n|\n)`だった場合、Parser3.raw_fieldの定義は`(((?!\t)(?!(\r\n|\n))[^"])((?!\t)(?!(\r\n|\n)).)*)?`になってしまい、Parser.lineだと`\r\r\n`のようなパターン、Parser.lastLineだとCSVファイルが`\r`で終わっている場合に、フィールド値に`\r`が紛れ込むバグが発生します。

どうですか？　簡単ですね！

## 正規表現にはその他様々な機能が備わっています。
どんどんBNFから正規表現に置き換えていきましょう！　楽しくなってきますよ