Switch to fast, hand-written parser, remove parboiled dependency

Closes #86, #108

5 files changed, 295 insertions, 91 deletions

diff --git a/build.sbt b/build.sbt
index 0c4c7ef..8ec4857 100644
--- a/build.sbt
+++ b/build.sbt
@@ -21,7 +21,6 @@ scalacOptions ++= Seq("-feature", "-language:_", "-unchecked", "-deprecation", "
 resolvers += Opts.resolver.sonatypeReleases
 
 libraryDependencies ++= Seq(
-  "org.parboiled" %% "parboiled-scala" % "1.1.6" % "compile",
   "org.specs2" %% "specs2" % "2.4.2" % "test",
   "org.scalacheck" %% "scalacheck" % "1.11.5" % "test"
 )
diff --git a/src/main/scala/spray/json/JsValue.scala b/src/main/scala/spray/json/JsValue.scala
index 8b25c98..7dfb06f 100644
--- a/src/main/scala/spray/json/JsValue.scala
+++ b/src/main/scala/spray/json/JsValue.scala
@@ -20,7 +20,6 @@ package spray.json
 
 import collection.immutable.ListMap
 
-
 /**
   * The general type of a JSON AST node.
  */
@@ -89,6 +88,7 @@ object JsNumber {
   }
   def apply(n: BigInt) = new JsNumber(BigDecimal(n))
   def apply(n: String) = new JsNumber(BigDecimal(n))
+  def apply(n: Array[Char]) = new JsNumber(BigDecimal(n))
 }
 
 /**
diff --git a/src/main/scala/spray/json/JsonParser.scala b/src/main/scala/spray/json/JsonParser.scala
index 0b408e8..36aa338 100644
--- a/src/main/scala/spray/json/JsonParser.scala
+++ b/src/main/scala/spray/json/JsonParser.scala
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2009-2011 Mathias Doenitz
+ * Copyright (C) 2014 Mathias Doenitz
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
@@ -16,106 +16,307 @@
 
 package spray.json
 
-import org.parboiled.scala._
-import org.parboiled.errors.{ErrorUtils, ParsingException}
-import org.parboiled.Context
-import java.lang.StringBuilder
+import java.lang.{StringBuilder => JStringBuilder}
+import java.nio.{CharBuffer, ByteBuffer}
+import java.nio.charset.Charset
+import scala.annotation.{switch, tailrec}
+import scala.collection.immutable.ListMap
 
 /**
- * This JSON parser is the almost direct implementation of the JSON grammar
- * presented at http://www.json.org as a parboiled PEG parser.
+ * Fast, no-dependency parser for JSON as defined by http://tools.ietf.org/html/rfc4627.
  */
-object JsonParser extends Parser {
+object JsonParser {
+  def apply(input: ParserInput): JsValue = new JsonParser(input).parseJsValue()
 
-  // the root rule
-  lazy val Json = rule { WhiteSpace ~ Value ~ EOI }
+  class ParsingException(val summary: String, val detail: String = "")
+    extends RuntimeException(if (summary.isEmpty) detail else if (detail.isEmpty) summary else summary + ": " + detail)
+}
 
-  def JsonObject: Rule1[JsObject] = rule {
-    "{ " ~ zeroOrMore(Pair, separator = ", ") ~ "} " ~~> (JsObject(_ :_*))
-  }
+class JsonParser(input: ParserInput) {
+  import JsonParser.ParsingException
 
-  def Pair = rule { JsonStringUnwrapped ~ ": " ~ Value ~~> ((_, _)) }
+  private[this] val sb = new JStringBuilder
+  private[this] var cursorChar: Char = input.nextChar()
+  private[this] var jsValue: JsValue = _
 
-  def Value: Rule1[JsValue] = rule {
-    JsonString | JsonNumber | JsonObject | JsonArray | JsonTrue | JsonFalse | JsonNull
+  def parseJsValue(): JsValue = {
+    ws()
+    `value`()
+    jsValue
   }
 
-  def JsonString = rule { JsonStringUnwrapped ~~> (JsString(_)) }
-  
-  def JsonStringUnwrapped = rule { "\"" ~ Characters ~ "\" " ~~> (_.toString) }
+  ////////////////////// GRAMMAR ////////////////////////
 
-  def JsonNumber = rule { group(Integer ~ optional(Frac) ~ optional(Exp)) ~> (JsNumber(_)) ~ WhiteSpace }
+  private final val EOI = '\uFFFF' // compile-time constant
 
-  def JsonArray = rule { "[ " ~ zeroOrMore(Value, separator = ", ") ~ "] " ~~> (JsArray(_)) }
+  // http://tools.ietf.org/html/rfc4627#section-2.1
+  private def `value`(): Unit = {
+    val mark = input.cursor
+    def simpleValue(matched: Boolean, value: JsValue) = if (matched) jsValue = value else fail("JSON Value", mark)
+    (cursorChar: @switch) match {
+      case 'f' => simpleValue(`false`(), JsFalse)
+      case 'n' => simpleValue(`null`(), JsNull)
+      case 't' => simpleValue(`true`(), JsTrue)
+      case '{' => advance(); `object`()
+      case '[' => advance(); `array`()
+      case '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' | '-' => `number`()
+      case '"' => `string`(); jsValue = JsString(sb.toString)
+      case _ => fail("JSON Value")
+    }
+  }
 
-  def Characters = rule { push(new StringBuilder) ~ zeroOrMore("\\" ~ EscapedChar | NormalChar) }
-  
-  def EscapedChar = rule (
-       anyOf("\"\\/") ~:% withContext(appendToSb(_)(_)) 
-    | "b" ~ appendToSb('\b')
-    | "f" ~ appendToSb('\f')
-    | "n" ~ appendToSb('\n')
-    | "r" ~ appendToSb('\r')
-    | "t" ~ appendToSb('\t')
-    | Unicode ~~% withContext((code, ctx) => appendToSb(code.asInstanceOf[Char])(ctx)) 
-  )
+  private def `false`() = advance() && ch('a') && ch('l') && ch('s') && ws('e')
+  private def `null`() = advance() && ch('u') && ch('l') && ws('l')
+  private def `true`() = advance() && ch('r') && ch('u') && ws('e')
 
-  def NormalChar = rule { !anyOf("\"\\") ~ ANY ~:% (withContext(appendToSb(_)(_))) }
+  // http://tools.ietf.org/html/rfc4627#section-2.2
+  private def `object`(): Unit = {
+    ws()
+    var map = ListMap.empty[String, JsValue]
+    @tailrec def members(): Unit = {
+      `string`()
+      require(':')
+      ws()
+      val key = sb.toString
+      `value`()
+      map = map.updated(key, jsValue)
+      if (ws(',')) members()
+    }
+    if (cursorChar != '}') members()
+    require('}')
+    ws()
+    jsValue = JsObject(map)
+  }
 
-  def Unicode = rule { "u" ~ group(HexDigit ~ HexDigit ~ HexDigit ~ HexDigit) ~> (java.lang.Integer.parseInt(_, 16)) }
+  // http://tools.ietf.org/html/rfc4627#section-2.3
+  private def `array`(): Unit = {
+    ws()
+    var list = List.newBuilder[JsValue]
+    @tailrec def values(): Unit = {
+      `value`()
+      list += jsValue
+      if (ws(',')) values()
+    }
+    if (cursorChar != ']') values()
+    require(']')
+    ws()
+    jsValue = JsArray(list.result())
+  }
 
-  def Integer = rule { optional("-") ~ (("1" - "9") ~ Digits | Digit) }
+  // http://tools.ietf.org/html/rfc4627#section-2.4
+  private def `number`() = {
+    val start = input.cursor
+    ch('-')
+    `int`()
+    `frac`()
+    `exp`()
+    jsValue = JsNumber(input.sliceCharArray(start, input.cursor))
+    ws()
+  }
 
-  def Digits = rule { oneOrMore(Digit) }
+  private def `int`(): Unit = if (!ch('0')) oneOrMoreDigits()
+  private def `frac`(): Unit = if (ch('.')) oneOrMoreDigits()
+  private def `exp`(): Unit = if ((ch('e') || ch('E')) && (ch('-') || ch('+') || true)) oneOrMoreDigits()
 
-  def Digit = rule { "0" - "9" }
+  private def oneOrMoreDigits(): Unit = if (DIGIT()) zeroOrMoreDigits() else fail("DIGIT")
+  @tailrec private def zeroOrMoreDigits(): Unit = if (DIGIT()) zeroOrMoreDigits()
 
-  def HexDigit = rule { "0" - "9" | "a" - "f" | "A" - "F" }
+  private def DIGIT(): Boolean = cursorChar >= '0' && cursorChar <= '9' && advance()
 
-  def Frac = rule { "." ~ Digits }
+  // http://tools.ietf.org/html/rfc4627#section-2.5
+  private def `string`(): Unit = {
+    require('"')
+    sb.setLength(0)
+    while (`char`()) cursorChar = input.nextUtf8Char()
+    require('"')
+    ws()
+  }
 
-  def Exp = rule { ignoreCase("e") ~ optional(anyOf("+-")) ~ Digits }
+  private def `char`() =
+    cursorChar match {
+      case '"' => false
+      case '\\' => advance(); `escaped`()
+      case c if cursorChar >= ' ' => appendSB(cursorChar)
+      case _ => false 
+    }
+
+  private def `escaped`() = {
+    def hexValue(c: Char): Int =
+      if ('0' <= c && c <= '9') c - '0'
+      else if ('a' <= c && c <= 'f') c - 87
+      else if ('A' <= c && c <= 'F') c - 55
+      else fail("hex digit")
+    def unicode() = {
+      var value = hexValue(cursorChar)
+      advance()
+      value = (value << 4) + hexValue(cursorChar)
+      advance()
+      value = (value << 4) + hexValue(cursorChar)
+      advance()
+      value = (value << 4) + hexValue(cursorChar)
+      appendSB(value.toChar)
+    }
+    (cursorChar: @switch) match {
+      case '"' | '/' | '\\' => appendSB(cursorChar)
+      case 'b' => appendSB('\b')
+      case 'f' => appendSB('\f')
+      case 'n' => appendSB('\n')
+      case 'r' => appendSB('\r')
+      case 't' => appendSB('\t')
+      case 'u' => advance(); unicode()
+      case _ => fail("JSON escape sequence")
+    }
+  }
 
-  def JsonTrue = rule { "true " ~ push(JsTrue) }
+  @tailrec private def ws(): Unit =
+    // fast test whether cursorChar is one of " \n\r\t"
+    if (((1L << cursorChar) & ((cursorChar - 64) >> 31) & 0x100002600L) != 0L) { advance(); ws() }
 
-  def JsonFalse = rule { "false " ~ push(JsFalse) }
+  ////////////////////////// HELPERS //////////////////////////
 
-  def JsonNull = rule { "null " ~ push(JsNull) }
+  private def ch(c: Char): Boolean = if (cursorChar == c) { advance(); true } else false
+  private def ws(c: Char): Boolean = if (ch(c)) { ws(); true } else false
+  private def advance(): Boolean = { cursorChar = input.nextChar(); true }
+  private def appendSB(c: Char): Boolean = { sb.append(c); true }
+  private def require(c: Char): Unit = if (!ch(c)) fail(s"'$c'")
 
-  def WhiteSpace: Rule0 = rule { zeroOrMore(anyOf(" \n\r\t\f")) }
-    
-  // helper method for fast string building
-  // for maximum performance we use a somewhat unorthodox parsing technique that is a bit more verbose (and somewhat
-  // less readable) but reduces object allocations during the parsing run to a minimum:
-  // the Characters rules pushes a StringBuilder object onto the stack which is then directly fed with matched
-  // and unescaped characters in the sub rules (i.e. no string allocations and value stack operation required)
-  def appendToSb(c: Char): Context[Any] => Unit = { ctx =>
-    ctx.getValueStack.peek.asInstanceOf[StringBuilder].append(c)
-    ()
+  private def fail(target: String, cursor: Int = input.cursor, errorChar: Char = cursorChar): Nothing = {
+    val ParserInput.Line(lineNr, col, text) = input.getLine(cursor)
+    val summary = {
+      val unexpected =
+        if (errorChar != EOI) {
+          val c = if (Character.isISOControl(errorChar)) "\\u%04x" format errorChar.toInt else errorChar.toString
+          s"character '$c'"
+        } else "end-of-input"
+      s"Unexpected $unexpected at input index $cursor (line $lineNr, position $col), expected $target"
+    }
+    val detail = {
+      val sanitizedText = text.map(c ⇒ if (Character.isISOControl(c)) '?' else c)
+      s"\n$sanitizedText\n${" " * col}^\n"
+    }
+    throw new ParsingException(summary, detail)
   }
+}
 
+trait ParserInput {
   /**
-   * We redefine the default string-to-rule conversion to also match trailing whitespace if the string ends with
-   * a blank, this keeps the rules free from most whitespace matching clutter
+   * Advance the cursor and get the next char.
+   * Since the char is required to be a 7-Bit ASCII char no decoding is required.
    */
-  override implicit def toRule(string: String) = {
-    if (string.endsWith(" ")) str(string.trim) ~ WhiteSpace
-    else str(string)
-  }
+  def nextChar(): Char
 
   /**
-   * The main parsing method. Uses a ReportingParseRunner (which only reports the first error) for simplicity.
+   * Advance the cursor and get the next char, which could potentially be outside
+   * of the 7-Bit ASCII range. Therefore decoding might be required.
    */
-  def apply(json: String): JsValue = apply(json.toCharArray)
-  
+  def nextUtf8Char(): Char
+
+  def cursor: Int
+  def length: Int
+  def sliceString(start: Int, end: Int): String
+  def sliceCharArray(start: Int, end: Int): Array[Char]
+  def getLine(index: Int): ParserInput.Line
+}
+
+object ParserInput {
+  private final val EOI = '\uFFFF' // compile-time constant
+  private final val ErrorChar = '\uFFFD' // compile-time constant, universal UTF-8 replacement character '�'
+
+  implicit def apply(string: String): StringBasedParserInput = new StringBasedParserInput(string)
+  implicit def apply(chars: Array[Char]): CharArrayBasedParserInput = new CharArrayBasedParserInput(chars)
+  implicit def apply(bytes: Array[Byte]): ByteArrayBasedParserInput = new ByteArrayBasedParserInput(bytes)
+
+  case class Line(lineNr: Int, column: Int, text: String)
+
+  abstract class DefaultParserInput extends ParserInput {
+    protected var _cursor: Int = -1
+    def cursor = _cursor
+    def getLine(index: Int): Line = {
+      val sb = new java.lang.StringBuilder
+      @tailrec def rec(ix: Int, lineStartIx: Int, lineNr: Int): Line =
+        nextUtf8Char() match {
+          case '\n' if index > ix => sb.setLength(0); rec(ix + 1, ix + 1, lineNr + 1)
+          case '\n' | EOI => Line(lineNr, index - lineStartIx, sb.toString)
+          case c => sb.append(c); rec(ix + 1, lineStartIx, lineNr)
+        }
+      val savedCursor = _cursor
+      _cursor = 0
+      val line = rec(ix = 0, lineStartIx = 0, lineNr = 1)
+      _cursor = savedCursor
+      line
+    }
+  }
+
+  private val UTF8 = Charset.forName("UTF-8")
+
   /**
-   * The main parsing method. Uses a ReportingParseRunner (which only reports the first error) for simplicity.
+   * ParserInput reading directly off a byte array which is assumed to contain the UTF-8 encoded represenation
+   * of the JSON input, without requiring a separate decoding step.
    */
-  def apply(json: Array[Char]): JsValue = {
-    val parsingResult = ReportingParseRunner(Json).run(json)
-    parsingResult.result.getOrElse {
-      throw new ParsingException("Invalid JSON source:\n" + ErrorUtils.printParseErrors(parsingResult)) 
+  class ByteArrayBasedParserInput(bytes: Array[Byte]) extends DefaultParserInput {
+    private val byteBuffer = ByteBuffer.allocate(4)
+    private val charBuffer = CharBuffer.allocate(1) // we currently don't support surrogate pairs!
+    private val decoder = UTF8.newDecoder()
+    def nextChar() = {
+      _cursor += 1
+      if (_cursor < bytes.length) (bytes(_cursor) & 0xFF).toChar else EOI
+    }
+    def nextUtf8Char() = {
+      @tailrec def decode(byte: Byte, remainingBytes: Int): Char = {
+        byteBuffer.put(byte)
+        if (remainingBytes > 0) {
+          _cursor += 1
+          if (_cursor < bytes.length) decode(bytes(_cursor), remainingBytes - 1) else ErrorChar
+        } else {
+          byteBuffer.flip()
+          val coderResult = decoder.decode(byteBuffer, charBuffer, false)
+          charBuffer.flip()
+          val result = if (coderResult.isUnderflow & charBuffer.hasRemaining) charBuffer.get() else ErrorChar
+          byteBuffer.clear()
+          charBuffer.clear()
+          result
+        }
+      }
+
+      _cursor += 1
+      if (_cursor < bytes.length) {
+        val byte = bytes(_cursor)
+        if (byte >= 0) byte.toChar // 7-Bit ASCII
+        else if ((byte & 0xE0) == 0xC0) decode(byte, 1) // 2-byte UTF-8 sequence
+        else if ((byte & 0xF0) == 0xE0) decode(byte, 2) // 3-byte UTF-8 sequence
+        else if ((byte & 0xF8) == 0xF0) decode(byte, 3) // 4-byte UTF-8 sequence, will probably produce an (unsupported) surrogate pair
+        else ErrorChar
+      } else EOI
+    }
+    def length = bytes.length
+    def sliceString(start: Int, end: Int) = new String(bytes, start, end - start, UTF8)
+    def sliceCharArray(start: Int, end: Int) =
+      UTF8.decode(ByteBuffer.wrap(java.util.Arrays.copyOfRange(bytes, start, end))).array()
+  }
+
+  class StringBasedParserInput(string: String) extends DefaultParserInput {
+    def nextChar(): Char = {
+      _cursor += 1
+      if (_cursor < string.length) string.charAt(_cursor) else EOI
+    }
+    def nextUtf8Char() = nextChar()
+    def length = string.length
+    def sliceString(start: Int, end: Int) = string.substring(start, end)
+    def sliceCharArray(start: Int, end: Int) = {
+      val chars = new Array[Char](end - start)
+      string.getChars(start, end, chars, 0)
+      chars
     }
   }
 
+  class CharArrayBasedParserInput(chars: Array[Char]) extends DefaultParserInput {
+    def nextChar(): Char = {
+      _cursor += 1
+      if (_cursor < chars.length) chars(_cursor) else EOI
+    }
+    def nextUtf8Char() = nextChar()
+    def length = chars.length
+    def sliceString(start: Int, end: Int) = new String(chars, start, end - start)
+    def sliceCharArray(start: Int, end: Int) = java.util.Arrays.copyOfRange(chars, start, end)
+  }
 }
\ No newline at end of file
diff --git a/src/test/scala/spray/json/JsonParserSpec.scala b/src/test/scala/spray/json/JsonParserSpec.scala
index c6c1589..608898f 100644
--- a/src/test/scala/spray/json/JsonParserSpec.scala
+++ b/src/test/scala/spray/json/JsonParserSpec.scala
@@ -17,55 +17,61 @@
 package spray.json
 
 import org.specs2.mutable._
-import org.parboiled.common.FileUtils
 
 class JsonParserSpec extends Specification {
 
   "The JsonParser" should {
     "parse 'null' to JsNull" in {
-      JsonParser("null") mustEqual JsNull
+      JsonParser("null") === JsNull
     }
     "parse 'true' to JsTrue" in {
-      JsonParser("true") mustEqual JsTrue
+      JsonParser("true") === JsTrue
     }
     "parse 'false' to JsFalse" in {
-      JsonParser("false") mustEqual JsFalse
+      JsonParser("false") === JsFalse
     }
     "parse '0' to JsNumber" in {
-      JsonParser("0") mustEqual JsNumber(0)
+      JsonParser("0") === JsNumber(0)
     }
     "parse '1.23' to JsNumber" in {
-      JsonParser("1.23") mustEqual JsNumber(1.23)
+      JsonParser("1.23") === JsNumber(1.23)
     }
     "parse '-1E10' to JsNumber" in {
-      JsonParser("-1E10") mustEqual JsNumber("-1E+10")
+      JsonParser("-1E10") === JsNumber("-1E+10")
     }
     "parse '12.34e-10' to JsNumber" in {
-      JsonParser("12.34e-10") mustEqual JsNumber("1.234E-9")
+      JsonParser("12.34e-10") === JsNumber("1.234E-9")
     }
     "parse \"xyz\" to JsString" in {
-      JsonParser("\"xyz\"") mustEqual JsString("xyz")
+      JsonParser("\"xyz\"") === JsString("xyz")
     }
     "parse escapes in a JsString" in {
-      JsonParser(""""\"\\/\b\f\n\r\t"""") mustEqual JsString("\"\\/\b\f\n\r\t")
-      JsonParser("\"L\\" + "u00e4nder\"") mustEqual JsString("Länder")
+      JsonParser(""""\"\\/\b\f\n\r\t"""") === JsString("\"\\/\b\f\n\r\t")
+      JsonParser("\"L\\" + "u00e4nder\"") === JsString("Länder")
     }
     "parse all representations of the slash (SOLIDUS) character in a JsString" in {
-      JsonParser( "\"" + "/\\/\\u002f" + "\"") mustEqual JsString("///")
+      JsonParser( "\"" + "/\\/\\u002f" + "\"") === JsString("///")
     }
-    "properly parse a simple JsObject" in (
-      JsonParser(""" { "key" :42, "key2": "value" }""") mustEqual
+    "parse a simple JsObject" in (
+      JsonParser(""" { "key" :42, "key2": "value" }""") ===
               JsObject("key" -> JsNumber(42), "key2" -> JsString("value"))
     )
-    "properly parse a simple JsArray" in (
-      JsonParser("""[null, 1.23 ,{"key":true } ] """) mustEqual
-              JsArray(JsNull, JsNumber(1.23), JsObject("key" -> JsBoolean(true)))
+    "parse a simple JsArray" in (
+      JsonParser("""[null, 1.23 ,{"key":true } ] """) ===
+              JsArray(JsNull, JsNumber(1.23), JsObject("key" -> JsTrue))
     )
+    "parse directly from UTF-8 encoded bytes" in {
+      val json = JsObject(
+        "7-bit" -> JsString("This is regular 7-bit ASCII text."),
+        "2-bytes" -> JsString("2-byte UTF-8 chars like £, æ or Ö"),
+        "3-bytes" -> JsString("3-byte UTF-8 chars like ﾖ, ᄅ or ᐁ."))
+      JsonParser(json.prettyPrint.getBytes("UTF-8")) === json
+    }
     "be reentrant" in {
-      val largeJsonSource = FileUtils.readAllCharsFromResource("test.json")
+      val largeJsonSource = scala.io.Source.fromInputStream(getClass.getResourceAsStream("/test.json")).mkString
       List.fill(20)(largeJsonSource).par.map(JsonParser(_)).toList.map {
           _.asInstanceOf[JsObject].fields("questions").asInstanceOf[JsArray].elements.size
-      } mustEqual List.fill(20)(100)
+      } === List.fill(20)(100)
     }
   }
 
diff --git a/src/test/scala/spray/json/RoundTripSpecs.scala b/src/test/scala/spray/json/RoundTripSpecs.scala
index 51df48d..d9e16c1 100644
--- a/src/test/scala/spray/json/RoundTripSpecs.scala
+++ b/src/test/scala/spray/json/RoundTripSpecs.scala
@@ -8,9 +8,7 @@ object JsValueGenerators {
   import Gen._
   import Arbitrary.arbitrary
 
-  // some characters have special meaning in parboiled
-  // see org.parboiled.support.Chars, we have to exclude those
-  val parseableString: Gen[String] = arbitrary[String].map(_.filterNot(_ > 0xfd00))
+  val parseableString: Gen[String] = arbitrary[String]
   val genString: Gen[JsString] = parseableString.map(JsString(_))
   val genBoolean: Gen[JsBoolean] = oneOf(JsFalse, JsTrue)
   val genLongNumber: Gen[JsNumber] = arbitrary[Long].map(JsNumber(_))