diff options
author | Mathias <mathias@spray.io> | 2014-09-18 13:33:50 +0200 |
---|---|---|
committer | Mathias <mathias@spray.io> | 2014-09-19 14:23:10 +0200 |
commit | 43a2319910f1c58c044aadbbb726bdc8a9f9229c (patch) | |
tree | fd83858231a90ac03b0f0b403c354a3202e28022 /src/main/scala/spray/json | |
parent | 73345dea51d62c50d2c09efb5ef0afddc77dbf25 (diff) | |
download | spray-json-43a2319910f1c58c044aadbbb726bdc8a9f9229c.tar.gz spray-json-43a2319910f1c58c044aadbbb726bdc8a9f9229c.tar.bz2 spray-json-43a2319910f1c58c044aadbbb726bdc8a9f9229c.zip |
Switch to fast, hand-written parser, remove parboiled dependency
Closes #86, #108
Diffstat (limited to 'src/main/scala/spray/json')
-rw-r--r-- | src/main/scala/spray/json/JsValue.scala | 2 | ||||
-rw-r--r-- | src/main/scala/spray/json/JsonParser.scala | 335 |
2 files changed, 269 insertions, 68 deletions
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 |