1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
|
/*
* 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.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
package spray.json
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
/**
* Fast, no-dependency parser for JSON as defined by http://tools.ietf.org/html/rfc4627.
*/
object JsonParser {
def apply(input: ParserInput): JsValue = new JsonParser(input).parseJsValue()
class ParsingException(val summary: String, val detail: String = "")
extends RuntimeException(if (summary.isEmpty) detail else if (detail.isEmpty) summary else summary + ": " + detail)
}
class JsonParser(input: ParserInput) {
import JsonParser.ParsingException
private[this] val sb = new JStringBuilder
private[this] var cursorChar: Char = input.nextChar()
private[this] var jsValue: JsValue = _
def parseJsValue(): JsValue = {
ws()
`value`()
jsValue
}
////////////////////// GRAMMAR ////////////////////////
private final val EOI = '\uFFFF' // compile-time constant
// 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")
}
}
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')
// http://tools.ietf.org/html/rfc4627#section-2.2
private def `object`(): Unit = {
ws()
var map = Map.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)
}
// http://tools.ietf.org/html/rfc4627#section-2.3
private def `array`(): Unit = {
ws()
var list = Vector.newBuilder[JsValue]
@tailrec def values(): Unit = {
`value`()
list += jsValue
if (ws(',')) values()
}
if (cursorChar != ']') values()
require(']')
ws()
jsValue = JsArray(list.result())
}
// 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()
}
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()
private def oneOrMoreDigits(): Unit = if (DIGIT()) zeroOrMoreDigits() else fail("DIGIT")
@tailrec private def zeroOrMoreDigits(): Unit = if (DIGIT()) zeroOrMoreDigits()
private def DIGIT(): Boolean = cursorChar >= '0' && cursorChar <= '9' && advance()
// http://tools.ietf.org/html/rfc4627#section-2.5
private def `string`(): Unit = {
require('"')
sb.setLength(0)
while (`char`()) cursorChar = input.nextUtf8Char()
require('"')
ws()
}
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")
}
}
@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() }
////////////////////////// HELPERS //////////////////////////
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'")
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 {
/**
* Advance the cursor and get the next char.
* Since the char is required to be a 7-Bit ASCII char no decoding is required.
*/
def nextChar(): Char
/**
* 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 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")
/**
* 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.
*/
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)
}
}
|