Scala のパーサコンビネータで罠にはまった

最近 Scala のパーサコンビネータを弄ってるんだけど、ちょっと罠にはまったのでメモ。ちなみに Scala 2.7.7 final。

まず

識別子をパースするパーサを作ろうと思った。識別子を Java 互換にしようと思い、以下のようにした。

def ident =
  elem("JavaIdentifierStart", Character.isJavaIdentifierStart(_)) ~
  elem("JavaIdentifierPart", Character.isJavaIdentifierPart(_)).*

ところが

Scanner で処理しようとしたところ、いつまで経っても処理が終わらず、最終的には OutOfMemoryError で止まってしまった。

// 最低限のコード
import scala.util.parsing.combinator.lexical.StdLexical

object Main {
  def main(args: Array[String]) {
    val s = new StdLexical {
      override def token = ident ^^ Identifier

      def ident =
        elem("JavaIdentifierStart", Character.isJavaIdentifierStart(_)) ~
        elem("JavaIdentifierPart", Character.isJavaIdentifierPart(_)).* ^^
        { case start ~ part => new String((start :: part).toArray) }
      }

    new s.Scanner("variable")
  }
}

原因

scala.util.parsing.combinator.lexical.Scanners.Scanner は入力として scala.util.parsing.input.CharSequenceReader を使う。こいつは入力の最後に到達すると、次の入力として内部で定義されている EofCh(実体は'\032'==0x1A) を無限に返す。

で、一方 JavaIdentifierPart の定義はと言うと…

文字 (Unicode コードポイント) を Java 識別子の最初の文字以外に使用可能かどうかを判定します。
次のどれかが true の場合にだけ、その文字を Java 識別子の一部に指定できます。

汎用文字である

通貨記号である ('$' など)

連結句読点文字である ('_' など)

数字である

数値汎用文字である (ローマ数字文字など)

連結マークである

非スペーシングマークである

isIdentifierIgnorable(codePoint) がその文字について true を返す

http://java.sun.com/javase/ja/6/docs/ja/api/java/lang/Character.html#isJavaIdentifierPart(int)

指定された文字 (Unicode コードポイント) が、Java 識別子または Unicode 識別子内で無視可能な文字かどうかを判定します。
次の Unicode 文字は、Java 識別子や Unicode 識別子内で無視できます。

空白以外の ISO 制御文字

「\u0000」〜「\u0008」

「\u000E」〜「\u001B」

「\u007F」〜「\u009F」

汎用カテゴリ値 FORMAT を保持するすべての文字

http://java.sun.com/javase/ja/6/docs/ja/api/java/lang/Character.html#isIdentifierIgnorable(int)

「\u000E」〜「\u001B」

!!!!

というか、

次の Unicode 文字は、Java 識別子や Unicode 識別子内で無視できます。

これ自体初耳。し、知らんかった。

つまり、CharSequenceReader が最後に無限に返す EofCh は Java 識別子の一部としてマッチしてしまうため、永遠にマッチし続けて OutOfMemoryError になってしまった模様。なんという罠。

対応策

とりあえず今回に限っては EofCh が識別子の一部に入ってくれなくても一向に構わないので、以下のようにした。

def ident =
  elem("JavaIdentifierStart", Character.isJavaIdentifierStart(_)) ~
  elem("JavaIdentifierPart", {x => x != CharSequenceReader.EofCh && Character.isJavaIdentifierPart(x)}).*

でも

今回はこれでいいとして、これって根本的な解決になってない気がする。例えば完全に Java 互換の識別子を使いたい場合は一体どうすればいいのだろうか。
ところで、Parser の入力である Reader クラスの rest メソッドの scaladoc には以下のように書かれている。

Returns

If atEnd is true, the result will be this'; otherwise, it's a Reader containing more elements.
http://www.scala-lang.org/docu/files/api/scala/util/parsing/input/Reader.html#rest

つまり、Reader#rest は Reader#atEnd が true の時は普通の実装なら自分自身を返す。と言う事は、入力の最後を受け付けるパーサが存在する場合、Reader#atEnd を調べない限り無限に読めてしまう。
一方、繰り返しのパーサを作る標準のメソッドの中でも最終的に呼ばれる Parsers#rep1 を見ると、Reader#atEnd は一切呼ばすにパースが成功するかのみを見ている。
それに繰り返しの部分以外でも Reader#atEnd をチェックしないといけないパターンはありそうな気がする。何かこのパーサコンビネータ自体の設計ミスのような気すらしてきてしまうのだけれど…。
これは一体どうすればいいのだろう。教えてすごい人！

ちなみに現時点での最新のParsers#rep1を見てみたけど、実装こそすっきりしたものの*1、Reader#atEnd を見てないのは同じ模様。
他の部分の変更を確認してないのでもしかしたら別の個所で別のアプローチにより解決しているかも知れないけど、まだ調べてない。その辺りもご存じの方いましたら教えてください！

*1:そしてよく見たらこの変更が行われたのは1時間くらい前だった。何とタイムリー!